blob: 8fa5f60ceca359b6b0fb290d8c2e79275cb1b5f4 [file] [log] [blame]
Alan Donovan312d1a52017-10-02 10:10:28 -04001// Copyright 2017 The Bazel Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package skylark_test
6
7import (
8 "fmt"
9 "log"
10 "sort"
11 "strings"
12 "sync"
13 "sync/atomic"
14 "unsafe"
15
16 "github.com/google/skylark"
17)
18
19// ExampleEmbedding demonstrates a simple embedding
20// of the Skylark interpreter into a Go program.
21func ExampleEmbedding() {
22 const data = `
23print(greeting + ", world")
24
25squares = [x*x for x in range(10)]
26`
27
28 thread := &skylark.Thread{
29 Print: func(_ *skylark.Thread, msg string) { fmt.Println(msg) },
30 }
alandonovana1b28d82018-03-13 10:59:24 -040031 predeclared := skylark.StringDict{
Alan Donovan312d1a52017-10-02 10:10:28 -040032 "greeting": skylark.String("hello"),
33 }
alandonovana1b28d82018-03-13 10:59:24 -040034 globals, err := skylark.ExecFile(thread, "apparent/filename.sky", data, predeclared)
35 if err != nil {
Alan Donovan312d1a52017-10-02 10:10:28 -040036 if evalErr, ok := err.(*skylark.EvalError); ok {
37 log.Fatal(evalErr.Backtrace())
38 }
39 log.Fatal(err)
40 }
41
42 // Print the global environment.
43 var names []string
44 for name := range globals {
45 names = append(names, name)
46 }
47 sort.Strings(names)
48 fmt.Println("\nGlobals:")
49 for _, name := range names {
50 v := globals[name]
51 fmt.Printf("%s (%s) = %s\n", name, v.Type(), v.String())
52 }
53
54 // Output:
55 // hello, world
56 //
57 // Globals:
Alan Donovan312d1a52017-10-02 10:10:28 -040058 // squares (list) = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
59}
60
61// ExampleLoadSequential demonstrates a simple caching
62// implementation of 'load' that works sequentially.
63func ExampleLoadSequential() {
64 fakeFilesystem := map[string]string{
65 "c.sky": `load("b.sky", "b"); c = b + "!"`,
66 "b.sky": `load("a.sky", "a"); b = a + ", world"`,
67 "a.sky": `a = "Hello"`,
68 }
69
70 type entry struct {
71 globals skylark.StringDict
72 err error
73 }
74
75 cache := make(map[string]*entry)
76
Alan Donovan6c3fcb82017-10-10 15:47:38 -040077 var load func(_ *skylark.Thread, module string) (skylark.StringDict, error)
78 load = func(_ *skylark.Thread, module string) (skylark.StringDict, error) {
Alan Donovan312d1a52017-10-02 10:10:28 -040079 e, ok := cache[module]
80 if e == nil {
81 if ok {
82 // request for package whose loading is in progress
83 return nil, fmt.Errorf("cycle in load graph")
84 }
85
86 // Add a placeholder to indicate "load in progress".
87 cache[module] = nil
88
Alan Donovan6c3fcb82017-10-10 15:47:38 -040089 // Load and initialize the module in a new thread.
Alan Donovan312d1a52017-10-02 10:10:28 -040090 data := fakeFilesystem[module]
Alan Donovan6c3fcb82017-10-10 15:47:38 -040091 thread := &skylark.Thread{Load: load}
alandonovana1b28d82018-03-13 10:59:24 -040092 globals, err := skylark.ExecFile(thread, module, data, nil)
Alan Donovan312d1a52017-10-02 10:10:28 -040093 e = &entry{globals, err}
94
95 // Update the cache.
96 cache[module] = e
97 }
98 return e.globals, e.err
99 }
100
101 thread := &skylark.Thread{Load: load}
102 globals, err := load(thread, "c.sky")
103 if err != nil {
104 log.Fatal(err)
105 }
106 fmt.Println(globals["c"])
107
108 // Output:
109 // "Hello, world!"
110}
111
112// ExampleLoadParallel demonstrates a parallel implementation
113// of 'load' with caching, duplicate suppression, and cycle detection.
114func ExampleLoadParallel() {
115 cache := &cache{
116 cache: make(map[string]*entry),
117 fakeFilesystem: map[string]string{
118 "c.sky": `load("a.sky", "a"); c = a * 2`,
119 "b.sky": `load("a.sky", "a"); b = a * 3`,
120 "a.sky": `a = 1; print("loaded a")`,
121 },
122 }
123
124 // We load modules b and c in parallel by concurrent calls to
125 // cache.Load. Both of them load module a, but a is executed
126 // only once, as witnessed by the sole output of its print
127 // statement.
128
129 ch := make(chan string)
130 for _, name := range []string{"b", "c"} {
131 go func(name string) {
132 globals, err := cache.Load(name + ".sky")
133 if err != nil {
134 log.Fatal(err)
135 }
136 ch <- fmt.Sprintf("%s = %s", name, globals[name])
137 }(name)
138 }
139 got := []string{<-ch, <-ch}
140 sort.Strings(got)
141 fmt.Println(strings.Join(got, "\n"))
142
143 // Output:
144 // loaded a
145 // b = 3
146 // c = 2
147}
148
149// ExampleLoadParallelCycle demonstrates detection
150// of cycles during parallel loading.
151func ExampleLoadParallelCycle() {
152 cache := &cache{
153 cache: make(map[string]*entry),
154 fakeFilesystem: map[string]string{
155 "c.sky": `load("b.sky", "b"); c = b * 2`,
156 "b.sky": `load("a.sky", "a"); b = a * 3`,
157 "a.sky": `load("c.sky", "c"); a = c * 5; print("loaded a")`,
158 },
159 }
160
161 ch := make(chan string)
162 for _, name := range "bc" {
163 name := string(name)
164 go func() {
165 _, err := cache.Load(name + ".sky")
166 if err == nil {
167 log.Fatalf("Load of %s.sky succeeded unexpectedly", name)
168 }
169 ch <- err.Error()
170 }()
171 }
172 got := []string{<-ch, <-ch}
173 sort.Strings(got)
174 fmt.Println(strings.Join(got, "\n"))
175
176 // Output:
177 // cannot load a.sky: cannot load c.sky: cycle in load graph
178 // cannot load b.sky: cannot load a.sky: cannot load c.sky: cycle in load graph
179}
180
181// cache is a concurrency-safe, duplicate-suppressing,
182// non-blocking cache of the doLoad function.
183// See Section 9.7 of gopl.io for an explanation of this structure.
184// It also features online deadlock (load cycle) detection.
185type cache struct {
186 cacheMu sync.Mutex
187 cache map[string]*entry
188
189 fakeFilesystem map[string]string
190}
191
192type entry struct {
193 owner unsafe.Pointer // a *cycleChecker; see cycleCheck
194 globals skylark.StringDict
195 err error
196 ready chan struct{}
197}
198
199func (c *cache) Load(module string) (skylark.StringDict, error) {
200 return c.get(new(cycleChecker), module)
201}
202
203// get loads and returns an entry (if not already loaded).
204func (c *cache) get(cc *cycleChecker, module string) (skylark.StringDict, error) {
205 c.cacheMu.Lock()
206 e := c.cache[module]
207 if e != nil {
208 c.cacheMu.Unlock()
209 // Some other goroutine is getting this module.
210 // Wait for it to become ready.
211
212 // Detect load cycles to avoid deadlocks.
213 if err := cycleCheck(e, cc); err != nil {
214 return nil, err
215 }
216
217 cc.setWaitsFor(e)
218 <-e.ready
219 cc.setWaitsFor(nil)
220 } else {
221 // First request for this module.
222 e = &entry{ready: make(chan struct{})}
223 c.cache[module] = e
224 c.cacheMu.Unlock()
225
226 e.setOwner(cc)
227 e.globals, e.err = c.doLoad(cc, module)
228 e.setOwner(nil)
229
230 // Broadcast that the entry is now ready.
231 close(e.ready)
232 }
233 return e.globals, e.err
234}
235
236func (c *cache) doLoad(cc *cycleChecker, module string) (skylark.StringDict, error) {
237 thread := &skylark.Thread{
238 Print: func(_ *skylark.Thread, msg string) { fmt.Println(msg) },
239 Load: func(_ *skylark.Thread, module string) (skylark.StringDict, error) {
240 // Tunnel the cycle-checker state for this "thread of loading".
241 return c.get(cc, module)
242 },
243 }
244 data := c.fakeFilesystem[module]
alandonovana1b28d82018-03-13 10:59:24 -0400245 return skylark.ExecFile(thread, module, data, nil)
Alan Donovan312d1a52017-10-02 10:10:28 -0400246}
247
248// -- concurrent cycle checking --
249
250// A cycleChecker is used for concurrent deadlock detection.
251// Each top-level call to Load creates its own cycleChecker,
252// which is passed to all recursive calls it makes.
253// It corresponds to a logical thread in the deadlock detection literature.
254type cycleChecker struct {
255 waitsFor unsafe.Pointer // an *entry; see cycleCheck
256}
257
258func (cc *cycleChecker) setWaitsFor(e *entry) {
259 atomic.StorePointer(&cc.waitsFor, unsafe.Pointer(e))
260}
261
262func (e *entry) setOwner(cc *cycleChecker) {
263 atomic.StorePointer(&e.owner, unsafe.Pointer(cc))
264}
265
266// cycleCheck reports whether there is a path in the waits-for graph
267// from resource 'e' to thread 'me'.
268//
269// The waits-for graph (WFG) is a bipartite graph whose nodes are
270// alternately of type entry and cycleChecker. Each node has at most
271// one outgoing edge. An entry has an "owner" edge to a cycleChecker
272// while it is being readied by that cycleChecker, and a cycleChecker
273// has a "waits-for" edge to an entry while it is waiting for that entry
274// to become ready.
275//
276// Before adding a waits-for edge, the cache checks whether the new edge
277// would form a cycle. If so, this indicates that the load graph is
278// cyclic and that the following wait operation would deadlock.
279func cycleCheck(e *entry, me *cycleChecker) error {
280 for e != nil {
281 cc := (*cycleChecker)(atomic.LoadPointer(&e.owner))
282 if cc == nil {
283 break
284 }
285 if cc == me {
286 return fmt.Errorf("cycle in load graph")
287 }
288 e = (*entry)(atomic.LoadPointer(&cc.waitsFor))
289 }
290 return nil
291}