blob: 1be9a6dff35dc67bb566602522e0c7284af698fb [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 }
31 globals := skylark.StringDict{
32 "greeting": skylark.String("hello"),
33 }
34 if err := skylark.ExecFile(thread, "apparent/filename.sky", data, globals); err != nil {
35 if evalErr, ok := err.(*skylark.EvalError); ok {
36 log.Fatal(evalErr.Backtrace())
37 }
38 log.Fatal(err)
39 }
40
41 // Print the global environment.
42 var names []string
43 for name := range globals {
44 names = append(names, name)
45 }
46 sort.Strings(names)
47 fmt.Println("\nGlobals:")
48 for _, name := range names {
49 v := globals[name]
50 fmt.Printf("%s (%s) = %s\n", name, v.Type(), v.String())
51 }
52
53 // Output:
54 // hello, world
55 //
56 // Globals:
57 // greeting (string) = "hello"
58 // 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}
Alan Donovan312d1a52017-10-02 10:10:28 -040092 globals := make(skylark.StringDict)
93 err := skylark.ExecFile(thread, module, data, globals)
94 e = &entry{globals, err}
95
96 // Update the cache.
97 cache[module] = e
98 }
99 return e.globals, e.err
100 }
101
102 thread := &skylark.Thread{Load: load}
103 globals, err := load(thread, "c.sky")
104 if err != nil {
105 log.Fatal(err)
106 }
107 fmt.Println(globals["c"])
108
109 // Output:
110 // "Hello, world!"
111}
112
113// ExampleLoadParallel demonstrates a parallel implementation
114// of 'load' with caching, duplicate suppression, and cycle detection.
115func ExampleLoadParallel() {
116 cache := &cache{
117 cache: make(map[string]*entry),
118 fakeFilesystem: map[string]string{
119 "c.sky": `load("a.sky", "a"); c = a * 2`,
120 "b.sky": `load("a.sky", "a"); b = a * 3`,
121 "a.sky": `a = 1; print("loaded a")`,
122 },
123 }
124
125 // We load modules b and c in parallel by concurrent calls to
126 // cache.Load. Both of them load module a, but a is executed
127 // only once, as witnessed by the sole output of its print
128 // statement.
129
130 ch := make(chan string)
131 for _, name := range []string{"b", "c"} {
132 go func(name string) {
133 globals, err := cache.Load(name + ".sky")
134 if err != nil {
135 log.Fatal(err)
136 }
137 ch <- fmt.Sprintf("%s = %s", name, globals[name])
138 }(name)
139 }
140 got := []string{<-ch, <-ch}
141 sort.Strings(got)
142 fmt.Println(strings.Join(got, "\n"))
143
144 // Output:
145 // loaded a
146 // b = 3
147 // c = 2
148}
149
150// ExampleLoadParallelCycle demonstrates detection
151// of cycles during parallel loading.
152func ExampleLoadParallelCycle() {
153 cache := &cache{
154 cache: make(map[string]*entry),
155 fakeFilesystem: map[string]string{
156 "c.sky": `load("b.sky", "b"); c = b * 2`,
157 "b.sky": `load("a.sky", "a"); b = a * 3`,
158 "a.sky": `load("c.sky", "c"); a = c * 5; print("loaded a")`,
159 },
160 }
161
162 ch := make(chan string)
163 for _, name := range "bc" {
164 name := string(name)
165 go func() {
166 _, err := cache.Load(name + ".sky")
167 if err == nil {
168 log.Fatalf("Load of %s.sky succeeded unexpectedly", name)
169 }
170 ch <- err.Error()
171 }()
172 }
173 got := []string{<-ch, <-ch}
174 sort.Strings(got)
175 fmt.Println(strings.Join(got, "\n"))
176
177 // Output:
178 // cannot load a.sky: cannot load c.sky: cycle in load graph
179 // cannot load b.sky: cannot load a.sky: cannot load c.sky: cycle in load graph
180}
181
182// cache is a concurrency-safe, duplicate-suppressing,
183// non-blocking cache of the doLoad function.
184// See Section 9.7 of gopl.io for an explanation of this structure.
185// It also features online deadlock (load cycle) detection.
186type cache struct {
187 cacheMu sync.Mutex
188 cache map[string]*entry
189
190 fakeFilesystem map[string]string
191}
192
193type entry struct {
194 owner unsafe.Pointer // a *cycleChecker; see cycleCheck
195 globals skylark.StringDict
196 err error
197 ready chan struct{}
198}
199
200func (c *cache) Load(module string) (skylark.StringDict, error) {
201 return c.get(new(cycleChecker), module)
202}
203
204// get loads and returns an entry (if not already loaded).
205func (c *cache) get(cc *cycleChecker, module string) (skylark.StringDict, error) {
206 c.cacheMu.Lock()
207 e := c.cache[module]
208 if e != nil {
209 c.cacheMu.Unlock()
210 // Some other goroutine is getting this module.
211 // Wait for it to become ready.
212
213 // Detect load cycles to avoid deadlocks.
214 if err := cycleCheck(e, cc); err != nil {
215 return nil, err
216 }
217
218 cc.setWaitsFor(e)
219 <-e.ready
220 cc.setWaitsFor(nil)
221 } else {
222 // First request for this module.
223 e = &entry{ready: make(chan struct{})}
224 c.cache[module] = e
225 c.cacheMu.Unlock()
226
227 e.setOwner(cc)
228 e.globals, e.err = c.doLoad(cc, module)
229 e.setOwner(nil)
230
231 // Broadcast that the entry is now ready.
232 close(e.ready)
233 }
234 return e.globals, e.err
235}
236
237func (c *cache) doLoad(cc *cycleChecker, module string) (skylark.StringDict, error) {
238 thread := &skylark.Thread{
239 Print: func(_ *skylark.Thread, msg string) { fmt.Println(msg) },
240 Load: func(_ *skylark.Thread, module string) (skylark.StringDict, error) {
241 // Tunnel the cycle-checker state for this "thread of loading".
242 return c.get(cc, module)
243 },
244 }
245 data := c.fakeFilesystem[module]
246 globals := make(skylark.StringDict)
247 err := skylark.ExecFile(thread, module, data, globals)
248 if err != nil {
249 return nil, err
250 }
251 return globals, nil
252}
253
254// -- concurrent cycle checking --
255
256// A cycleChecker is used for concurrent deadlock detection.
257// Each top-level call to Load creates its own cycleChecker,
258// which is passed to all recursive calls it makes.
259// It corresponds to a logical thread in the deadlock detection literature.
260type cycleChecker struct {
261 waitsFor unsafe.Pointer // an *entry; see cycleCheck
262}
263
264func (cc *cycleChecker) setWaitsFor(e *entry) {
265 atomic.StorePointer(&cc.waitsFor, unsafe.Pointer(e))
266}
267
268func (e *entry) setOwner(cc *cycleChecker) {
269 atomic.StorePointer(&e.owner, unsafe.Pointer(cc))
270}
271
272// cycleCheck reports whether there is a path in the waits-for graph
273// from resource 'e' to thread 'me'.
274//
275// The waits-for graph (WFG) is a bipartite graph whose nodes are
276// alternately of type entry and cycleChecker. Each node has at most
277// one outgoing edge. An entry has an "owner" edge to a cycleChecker
278// while it is being readied by that cycleChecker, and a cycleChecker
279// has a "waits-for" edge to an entry while it is waiting for that entry
280// to become ready.
281//
282// Before adding a waits-for edge, the cache checks whether the new edge
283// would form a cycle. If so, this indicates that the load graph is
284// cyclic and that the following wait operation would deadlock.
285func cycleCheck(e *entry, me *cycleChecker) error {
286 for e != nil {
287 cc := (*cycleChecker)(atomic.LoadPointer(&e.owner))
288 if cc == nil {
289 break
290 }
291 if cc == me {
292 return fmt.Errorf("cycle in load graph")
293 }
294 e = (*entry)(atomic.LoadPointer(&cc.waitsFor))
295 }
296 return nil
297}