blob: fc2fee0fec7d681cb91b05b8688dd0249692b94f [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
Alan Donovane3deafe2018-10-23 11:05:09 -04005package starlark_test
Alan Donovan312d1a52017-10-02 10:10:28 -04006
7import (
8 "fmt"
9 "log"
alandonovan4765c972018-11-20 13:58:46 -050010 "reflect"
Alan Donovan312d1a52017-10-02 10:10:28 -040011 "sort"
12 "strings"
13 "sync"
14 "sync/atomic"
alandonovan4765c972018-11-20 13:58:46 -050015 "testing"
Alan Donovan312d1a52017-10-02 10:10:28 -040016 "unsafe"
17
Alan Donovan6beab7e2018-10-31 17:53:09 -040018 "go.starlark.net/starlark"
Alan Donovan312d1a52017-10-02 10:10:28 -040019)
20
Nick Santos572cea22018-05-25 16:41:09 -040021// ExampleExecFile demonstrates a simple embedding
Alan Donovane3deafe2018-10-23 11:05:09 -040022// of the Starlark interpreter into a Go program.
Nick Santos572cea22018-05-25 16:41:09 -040023func ExampleExecFile() {
Alan Donovan312d1a52017-10-02 10:10:28 -040024 const data = `
25print(greeting + ", world")
26
27squares = [x*x for x in range(10)]
28`
29
Alan Donovane3deafe2018-10-23 11:05:09 -040030 thread := &starlark.Thread{
31 Print: func(_ *starlark.Thread, msg string) { fmt.Println(msg) },
Alan Donovan312d1a52017-10-02 10:10:28 -040032 }
Alan Donovane3deafe2018-10-23 11:05:09 -040033 predeclared := starlark.StringDict{
34 "greeting": starlark.String("hello"),
Alan Donovan312d1a52017-10-02 10:10:28 -040035 }
Alan Donovane3deafe2018-10-23 11:05:09 -040036 globals, err := starlark.ExecFile(thread, "apparent/filename.star", data, predeclared)
alandonovana1b28d82018-03-13 10:59:24 -040037 if err != nil {
Alan Donovane3deafe2018-10-23 11:05:09 -040038 if evalErr, ok := err.(*starlark.EvalError); ok {
Alan Donovan312d1a52017-10-02 10:10:28 -040039 log.Fatal(evalErr.Backtrace())
40 }
41 log.Fatal(err)
42 }
43
44 // Print the global environment.
45 var names []string
46 for name := range globals {
47 names = append(names, name)
48 }
49 sort.Strings(names)
50 fmt.Println("\nGlobals:")
51 for _, name := range names {
52 v := globals[name]
53 fmt.Printf("%s (%s) = %s\n", name, v.Type(), v.String())
54 }
55
56 // Output:
57 // hello, world
58 //
59 // Globals:
Alan Donovan312d1a52017-10-02 10:10:28 -040060 // squares (list) = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
61}
62
Nick Santos572cea22018-05-25 16:41:09 -040063// ExampleThread_Load_sequential demonstrates a simple caching
Alan Donovan312d1a52017-10-02 10:10:28 -040064// implementation of 'load' that works sequentially.
Nick Santos572cea22018-05-25 16:41:09 -040065func ExampleThread_Load_sequential() {
Alan Donovan312d1a52017-10-02 10:10:28 -040066 fakeFilesystem := map[string]string{
Alan Donovane3deafe2018-10-23 11:05:09 -040067 "c.star": `load("b.star", "b"); c = b + "!"`,
68 "b.star": `load("a.star", "a"); b = a + ", world"`,
69 "a.star": `a = "Hello"`,
Alan Donovan312d1a52017-10-02 10:10:28 -040070 }
71
72 type entry struct {
Alan Donovane3deafe2018-10-23 11:05:09 -040073 globals starlark.StringDict
Alan Donovan312d1a52017-10-02 10:10:28 -040074 err error
75 }
76
77 cache := make(map[string]*entry)
78
Alan Donovane3deafe2018-10-23 11:05:09 -040079 var load func(_ *starlark.Thread, module string) (starlark.StringDict, error)
80 load = func(_ *starlark.Thread, module string) (starlark.StringDict, error) {
Alan Donovan312d1a52017-10-02 10:10:28 -040081 e, ok := cache[module]
82 if e == nil {
83 if ok {
84 // request for package whose loading is in progress
85 return nil, fmt.Errorf("cycle in load graph")
86 }
87
88 // Add a placeholder to indicate "load in progress".
89 cache[module] = nil
90
Alan Donovan6c3fcb82017-10-10 15:47:38 -040091 // Load and initialize the module in a new thread.
Alan Donovan312d1a52017-10-02 10:10:28 -040092 data := fakeFilesystem[module]
Alan Donovane3deafe2018-10-23 11:05:09 -040093 thread := &starlark.Thread{Load: load}
94 globals, err := starlark.ExecFile(thread, module, data, nil)
Alan Donovan312d1a52017-10-02 10:10:28 -040095 e = &entry{globals, err}
96
97 // Update the cache.
98 cache[module] = e
99 }
100 return e.globals, e.err
101 }
102
Alan Donovane3deafe2018-10-23 11:05:09 -0400103 thread := &starlark.Thread{Load: load}
104 globals, err := load(thread, "c.star")
Alan Donovan312d1a52017-10-02 10:10:28 -0400105 if err != nil {
106 log.Fatal(err)
107 }
108 fmt.Println(globals["c"])
109
110 // Output:
111 // "Hello, world!"
112}
113
Nick Santos572cea22018-05-25 16:41:09 -0400114// ExampleThread_Load_parallel demonstrates a parallel implementation
Alan Donovan312d1a52017-10-02 10:10:28 -0400115// of 'load' with caching, duplicate suppression, and cycle detection.
Nick Santos572cea22018-05-25 16:41:09 -0400116func ExampleThread_Load_parallel() {
Alan Donovan312d1a52017-10-02 10:10:28 -0400117 cache := &cache{
118 cache: make(map[string]*entry),
119 fakeFilesystem: map[string]string{
Alan Donovane3deafe2018-10-23 11:05:09 -0400120 "c.star": `load("a.star", "a"); c = a * 2`,
121 "b.star": `load("a.star", "a"); b = a * 3`,
122 "a.star": `a = 1; print("loaded a")`,
Alan Donovan312d1a52017-10-02 10:10:28 -0400123 },
124 }
125
126 // We load modules b and c in parallel by concurrent calls to
127 // cache.Load. Both of them load module a, but a is executed
128 // only once, as witnessed by the sole output of its print
129 // statement.
130
131 ch := make(chan string)
132 for _, name := range []string{"b", "c"} {
133 go func(name string) {
Alan Donovane3deafe2018-10-23 11:05:09 -0400134 globals, err := cache.Load(name + ".star")
Alan Donovan312d1a52017-10-02 10:10:28 -0400135 if err != nil {
136 log.Fatal(err)
137 }
138 ch <- fmt.Sprintf("%s = %s", name, globals[name])
139 }(name)
140 }
141 got := []string{<-ch, <-ch}
142 sort.Strings(got)
143 fmt.Println(strings.Join(got, "\n"))
144
145 // Output:
146 // loaded a
147 // b = 3
148 // c = 2
149}
150
alandonovan4765c972018-11-20 13:58:46 -0500151// TestThread_Load_parallelCycle demonstrates detection
Alan Donovan312d1a52017-10-02 10:10:28 -0400152// of cycles during parallel loading.
alandonovan4765c972018-11-20 13:58:46 -0500153func TestThreadLoad_ParallelCycle(t *testing.T) {
Alan Donovan312d1a52017-10-02 10:10:28 -0400154 cache := &cache{
155 cache: make(map[string]*entry),
156 fakeFilesystem: map[string]string{
Alan Donovane3deafe2018-10-23 11:05:09 -0400157 "c.star": `load("b.star", "b"); c = b * 2`,
158 "b.star": `load("a.star", "a"); b = a * 3`,
159 "a.star": `load("c.star", "c"); a = c * 5; print("loaded a")`,
Alan Donovan312d1a52017-10-02 10:10:28 -0400160 },
161 }
162
163 ch := make(chan string)
164 for _, name := range "bc" {
165 name := string(name)
166 go func() {
Alan Donovane3deafe2018-10-23 11:05:09 -0400167 _, err := cache.Load(name + ".star")
Alan Donovan312d1a52017-10-02 10:10:28 -0400168 if err == nil {
Alan Donovane3deafe2018-10-23 11:05:09 -0400169 log.Fatalf("Load of %s.star succeeded unexpectedly", name)
Alan Donovan312d1a52017-10-02 10:10:28 -0400170 }
171 ch <- err.Error()
172 }()
173 }
174 got := []string{<-ch, <-ch}
175 sort.Strings(got)
Alan Donovan312d1a52017-10-02 10:10:28 -0400176
alandonovan4765c972018-11-20 13:58:46 -0500177 // Typically, the c goroutine quickly blocks behind b;
178 // b loads a, and a then fails to load c because it forms a cycle.
179 // The errors observed by the two goroutines are:
180 want1 := []string{
181 "cannot load a.star: cannot load c.star: cycle in load graph", // from b
182 "cannot load b.star: cannot load a.star: cannot load c.star: cycle in load graph", // from c
183 }
184 // But if the c goroutine is slow to start, b loads a,
185 // and a loads c; then c fails to load b because it forms a cycle.
186 // The errors this time are:
187 want2 := []string{
188 "cannot load a.star: cannot load c.star: cannot load b.star: cycle in load graph", // from b
189 "cannot load b.star: cycle in load graph", // from c
190 }
191 if !reflect.DeepEqual(got, want1) && !reflect.DeepEqual(got, want2) {
192 t.Error(got)
193 }
Alan Donovan312d1a52017-10-02 10:10:28 -0400194}
195
196// cache is a concurrency-safe, duplicate-suppressing,
197// non-blocking cache of the doLoad function.
198// See Section 9.7 of gopl.io for an explanation of this structure.
199// It also features online deadlock (load cycle) detection.
200type cache struct {
201 cacheMu sync.Mutex
202 cache map[string]*entry
203
204 fakeFilesystem map[string]string
205}
206
207type entry struct {
208 owner unsafe.Pointer // a *cycleChecker; see cycleCheck
Alan Donovane3deafe2018-10-23 11:05:09 -0400209 globals starlark.StringDict
Alan Donovan312d1a52017-10-02 10:10:28 -0400210 err error
211 ready chan struct{}
212}
213
Alan Donovane3deafe2018-10-23 11:05:09 -0400214func (c *cache) Load(module string) (starlark.StringDict, error) {
Alan Donovan312d1a52017-10-02 10:10:28 -0400215 return c.get(new(cycleChecker), module)
216}
217
218// get loads and returns an entry (if not already loaded).
Alan Donovane3deafe2018-10-23 11:05:09 -0400219func (c *cache) get(cc *cycleChecker, module string) (starlark.StringDict, error) {
Alan Donovan312d1a52017-10-02 10:10:28 -0400220 c.cacheMu.Lock()
221 e := c.cache[module]
222 if e != nil {
223 c.cacheMu.Unlock()
224 // Some other goroutine is getting this module.
225 // Wait for it to become ready.
226
227 // Detect load cycles to avoid deadlocks.
228 if err := cycleCheck(e, cc); err != nil {
229 return nil, err
230 }
231
232 cc.setWaitsFor(e)
233 <-e.ready
234 cc.setWaitsFor(nil)
235 } else {
236 // First request for this module.
237 e = &entry{ready: make(chan struct{})}
238 c.cache[module] = e
239 c.cacheMu.Unlock()
240
241 e.setOwner(cc)
242 e.globals, e.err = c.doLoad(cc, module)
243 e.setOwner(nil)
244
245 // Broadcast that the entry is now ready.
246 close(e.ready)
247 }
248 return e.globals, e.err
249}
250
Alan Donovane3deafe2018-10-23 11:05:09 -0400251func (c *cache) doLoad(cc *cycleChecker, module string) (starlark.StringDict, error) {
252 thread := &starlark.Thread{
253 Print: func(_ *starlark.Thread, msg string) { fmt.Println(msg) },
254 Load: func(_ *starlark.Thread, module string) (starlark.StringDict, error) {
Alan Donovan312d1a52017-10-02 10:10:28 -0400255 // Tunnel the cycle-checker state for this "thread of loading".
256 return c.get(cc, module)
257 },
258 }
259 data := c.fakeFilesystem[module]
Alan Donovane3deafe2018-10-23 11:05:09 -0400260 return starlark.ExecFile(thread, module, data, nil)
Alan Donovan312d1a52017-10-02 10:10:28 -0400261}
262
263// -- concurrent cycle checking --
264
265// A cycleChecker is used for concurrent deadlock detection.
266// Each top-level call to Load creates its own cycleChecker,
267// which is passed to all recursive calls it makes.
268// It corresponds to a logical thread in the deadlock detection literature.
269type cycleChecker struct {
270 waitsFor unsafe.Pointer // an *entry; see cycleCheck
271}
272
273func (cc *cycleChecker) setWaitsFor(e *entry) {
274 atomic.StorePointer(&cc.waitsFor, unsafe.Pointer(e))
275}
276
277func (e *entry) setOwner(cc *cycleChecker) {
278 atomic.StorePointer(&e.owner, unsafe.Pointer(cc))
279}
280
281// cycleCheck reports whether there is a path in the waits-for graph
282// from resource 'e' to thread 'me'.
283//
284// The waits-for graph (WFG) is a bipartite graph whose nodes are
285// alternately of type entry and cycleChecker. Each node has at most
286// one outgoing edge. An entry has an "owner" edge to a cycleChecker
287// while it is being readied by that cycleChecker, and a cycleChecker
288// has a "waits-for" edge to an entry while it is waiting for that entry
289// to become ready.
290//
291// Before adding a waits-for edge, the cache checks whether the new edge
292// would form a cycle. If so, this indicates that the load graph is
293// cyclic and that the following wait operation would deadlock.
294func cycleCheck(e *entry, me *cycleChecker) error {
295 for e != nil {
296 cc := (*cycleChecker)(atomic.LoadPointer(&e.owner))
297 if cc == nil {
298 break
299 }
300 if cc == me {
301 return fmt.Errorf("cycle in load graph")
302 }
303 e = (*entry)(atomic.LoadPointer(&cc.waitsFor))
304 }
305 return nil
306}