Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 1 | // 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 Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 5 | package starlark_test |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 6 | |
| 7 | import ( |
| 8 | "fmt" |
| 9 | "log" |
alandonovan | 4765c97 | 2018-11-20 13:58:46 -0500 | [diff] [blame] | 10 | "reflect" |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 11 | "sort" |
| 12 | "strings" |
| 13 | "sync" |
| 14 | "sync/atomic" |
alandonovan | 4765c97 | 2018-11-20 13:58:46 -0500 | [diff] [blame] | 15 | "testing" |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 16 | "unsafe" |
| 17 | |
Alan Donovan | 6beab7e | 2018-10-31 17:53:09 -0400 | [diff] [blame] | 18 | "go.starlark.net/starlark" |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 19 | ) |
| 20 | |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 21 | // ExampleExecFile demonstrates a simple embedding |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 22 | // of the Starlark interpreter into a Go program. |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 23 | func ExampleExecFile() { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 24 | const data = ` |
| 25 | print(greeting + ", world") |
alandonovan | dbbb761 | 2019-07-02 15:30:00 -0400 | [diff] [blame^] | 26 | print(repeat("one")) |
| 27 | print(repeat("mur", 2)) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 28 | squares = [x*x for x in range(10)] |
| 29 | ` |
| 30 | |
alandonovan | dbbb761 | 2019-07-02 15:30:00 -0400 | [diff] [blame^] | 31 | // repeat(str, n=1) is a Go function called from Starlark. |
| 32 | // It behaves like the 'string * int' operation. |
| 33 | repeat := func(thread *starlark.Thread, b *starlark.Builtin, args starlark.Tuple, kwargs []starlark.Tuple) (starlark.Value, error) { |
| 34 | var s string |
| 35 | var n int = 1 |
| 36 | if err := starlark.UnpackArgs(b.Name(), args, kwargs, "s", &s, "n?", &n); err != nil { |
| 37 | return nil, err |
| 38 | } |
| 39 | return starlark.String(strings.Repeat(s, n)), nil |
| 40 | } |
| 41 | |
| 42 | // The Thread defines the behavior of the built-in 'print' function. |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 43 | thread := &starlark.Thread{ |
alandonovan | 2c1f362 | 2018-12-17 13:10:16 -0500 | [diff] [blame] | 44 | Name: "example", |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 45 | Print: func(_ *starlark.Thread, msg string) { fmt.Println(msg) }, |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 46 | } |
alandonovan | dbbb761 | 2019-07-02 15:30:00 -0400 | [diff] [blame^] | 47 | |
| 48 | // This dictionary defines the pre-declared environment. |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 49 | predeclared := starlark.StringDict{ |
| 50 | "greeting": starlark.String("hello"), |
alandonovan | dbbb761 | 2019-07-02 15:30:00 -0400 | [diff] [blame^] | 51 | "repeat": starlark.NewBuiltin("repeat", repeat), |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 52 | } |
alandonovan | dbbb761 | 2019-07-02 15:30:00 -0400 | [diff] [blame^] | 53 | |
| 54 | // Execute a program. |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 55 | globals, err := starlark.ExecFile(thread, "apparent/filename.star", data, predeclared) |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 56 | if err != nil { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 57 | if evalErr, ok := err.(*starlark.EvalError); ok { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 58 | log.Fatal(evalErr.Backtrace()) |
| 59 | } |
| 60 | log.Fatal(err) |
| 61 | } |
| 62 | |
| 63 | // Print the global environment. |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 64 | fmt.Println("\nGlobals:") |
alandonovan | 0ed7e5b | 2019-01-03 16:11:58 -0500 | [diff] [blame] | 65 | for _, name := range globals.Keys() { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 66 | v := globals[name] |
| 67 | fmt.Printf("%s (%s) = %s\n", name, v.Type(), v.String()) |
| 68 | } |
| 69 | |
| 70 | // Output: |
| 71 | // hello, world |
alandonovan | dbbb761 | 2019-07-02 15:30:00 -0400 | [diff] [blame^] | 72 | // one |
| 73 | // murmur |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 74 | // |
| 75 | // Globals: |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 76 | // squares (list) = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] |
| 77 | } |
| 78 | |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 79 | // ExampleThread_Load_sequential demonstrates a simple caching |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 80 | // implementation of 'load' that works sequentially. |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 81 | func ExampleThread_Load_sequential() { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 82 | fakeFilesystem := map[string]string{ |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 83 | "c.star": `load("b.star", "b"); c = b + "!"`, |
| 84 | "b.star": `load("a.star", "a"); b = a + ", world"`, |
| 85 | "a.star": `a = "Hello"`, |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 86 | } |
| 87 | |
| 88 | type entry struct { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 89 | globals starlark.StringDict |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 90 | err error |
| 91 | } |
| 92 | |
| 93 | cache := make(map[string]*entry) |
| 94 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 95 | var load func(_ *starlark.Thread, module string) (starlark.StringDict, error) |
| 96 | load = func(_ *starlark.Thread, module string) (starlark.StringDict, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 97 | e, ok := cache[module] |
| 98 | if e == nil { |
| 99 | if ok { |
| 100 | // request for package whose loading is in progress |
| 101 | return nil, fmt.Errorf("cycle in load graph") |
| 102 | } |
| 103 | |
| 104 | // Add a placeholder to indicate "load in progress". |
| 105 | cache[module] = nil |
| 106 | |
Alan Donovan | 6c3fcb8 | 2017-10-10 15:47:38 -0400 | [diff] [blame] | 107 | // Load and initialize the module in a new thread. |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 108 | data := fakeFilesystem[module] |
alandonovan | 2c1f362 | 2018-12-17 13:10:16 -0500 | [diff] [blame] | 109 | thread := &starlark.Thread{Name: "exec " + module, Load: load} |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 110 | globals, err := starlark.ExecFile(thread, module, data, nil) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 111 | e = &entry{globals, err} |
| 112 | |
| 113 | // Update the cache. |
| 114 | cache[module] = e |
| 115 | } |
| 116 | return e.globals, e.err |
| 117 | } |
| 118 | |
alandonovan | 2c1f362 | 2018-12-17 13:10:16 -0500 | [diff] [blame] | 119 | thread := &starlark.Thread{Name: "exec c.star", Load: load} |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 120 | globals, err := load(thread, "c.star") |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 121 | if err != nil { |
| 122 | log.Fatal(err) |
| 123 | } |
| 124 | fmt.Println(globals["c"]) |
| 125 | |
| 126 | // Output: |
| 127 | // "Hello, world!" |
| 128 | } |
| 129 | |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 130 | // ExampleThread_Load_parallel demonstrates a parallel implementation |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 131 | // of 'load' with caching, duplicate suppression, and cycle detection. |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 132 | func ExampleThread_Load_parallel() { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 133 | cache := &cache{ |
| 134 | cache: make(map[string]*entry), |
| 135 | fakeFilesystem: map[string]string{ |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 136 | "c.star": `load("a.star", "a"); c = a * 2`, |
| 137 | "b.star": `load("a.star", "a"); b = a * 3`, |
| 138 | "a.star": `a = 1; print("loaded a")`, |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 139 | }, |
| 140 | } |
| 141 | |
| 142 | // We load modules b and c in parallel by concurrent calls to |
| 143 | // cache.Load. Both of them load module a, but a is executed |
| 144 | // only once, as witnessed by the sole output of its print |
| 145 | // statement. |
| 146 | |
| 147 | ch := make(chan string) |
| 148 | for _, name := range []string{"b", "c"} { |
| 149 | go func(name string) { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 150 | globals, err := cache.Load(name + ".star") |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 151 | if err != nil { |
| 152 | log.Fatal(err) |
| 153 | } |
| 154 | ch <- fmt.Sprintf("%s = %s", name, globals[name]) |
| 155 | }(name) |
| 156 | } |
| 157 | got := []string{<-ch, <-ch} |
| 158 | sort.Strings(got) |
| 159 | fmt.Println(strings.Join(got, "\n")) |
| 160 | |
| 161 | // Output: |
| 162 | // loaded a |
| 163 | // b = 3 |
| 164 | // c = 2 |
| 165 | } |
| 166 | |
alandonovan | 4765c97 | 2018-11-20 13:58:46 -0500 | [diff] [blame] | 167 | // TestThread_Load_parallelCycle demonstrates detection |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 168 | // of cycles during parallel loading. |
alandonovan | 4765c97 | 2018-11-20 13:58:46 -0500 | [diff] [blame] | 169 | func TestThreadLoad_ParallelCycle(t *testing.T) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 170 | cache := &cache{ |
| 171 | cache: make(map[string]*entry), |
| 172 | fakeFilesystem: map[string]string{ |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 173 | "c.star": `load("b.star", "b"); c = b * 2`, |
| 174 | "b.star": `load("a.star", "a"); b = a * 3`, |
| 175 | "a.star": `load("c.star", "c"); a = c * 5; print("loaded a")`, |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 176 | }, |
| 177 | } |
| 178 | |
| 179 | ch := make(chan string) |
| 180 | for _, name := range "bc" { |
| 181 | name := string(name) |
| 182 | go func() { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 183 | _, err := cache.Load(name + ".star") |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 184 | if err == nil { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 185 | log.Fatalf("Load of %s.star succeeded unexpectedly", name) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 186 | } |
| 187 | ch <- err.Error() |
| 188 | }() |
| 189 | } |
| 190 | got := []string{<-ch, <-ch} |
| 191 | sort.Strings(got) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 192 | |
alandonovan | 4765c97 | 2018-11-20 13:58:46 -0500 | [diff] [blame] | 193 | // Typically, the c goroutine quickly blocks behind b; |
| 194 | // b loads a, and a then fails to load c because it forms a cycle. |
| 195 | // The errors observed by the two goroutines are: |
| 196 | want1 := []string{ |
| 197 | "cannot load a.star: cannot load c.star: cycle in load graph", // from b |
| 198 | "cannot load b.star: cannot load a.star: cannot load c.star: cycle in load graph", // from c |
| 199 | } |
| 200 | // But if the c goroutine is slow to start, b loads a, |
| 201 | // and a loads c; then c fails to load b because it forms a cycle. |
| 202 | // The errors this time are: |
| 203 | want2 := []string{ |
| 204 | "cannot load a.star: cannot load c.star: cannot load b.star: cycle in load graph", // from b |
| 205 | "cannot load b.star: cycle in load graph", // from c |
| 206 | } |
| 207 | if !reflect.DeepEqual(got, want1) && !reflect.DeepEqual(got, want2) { |
| 208 | t.Error(got) |
| 209 | } |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 210 | } |
| 211 | |
| 212 | // cache is a concurrency-safe, duplicate-suppressing, |
| 213 | // non-blocking cache of the doLoad function. |
| 214 | // See Section 9.7 of gopl.io for an explanation of this structure. |
| 215 | // It also features online deadlock (load cycle) detection. |
| 216 | type cache struct { |
| 217 | cacheMu sync.Mutex |
| 218 | cache map[string]*entry |
| 219 | |
| 220 | fakeFilesystem map[string]string |
| 221 | } |
| 222 | |
| 223 | type entry struct { |
| 224 | owner unsafe.Pointer // a *cycleChecker; see cycleCheck |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 225 | globals starlark.StringDict |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 226 | err error |
| 227 | ready chan struct{} |
| 228 | } |
| 229 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 230 | func (c *cache) Load(module string) (starlark.StringDict, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 231 | return c.get(new(cycleChecker), module) |
| 232 | } |
| 233 | |
| 234 | // get loads and returns an entry (if not already loaded). |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 235 | func (c *cache) get(cc *cycleChecker, module string) (starlark.StringDict, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 236 | c.cacheMu.Lock() |
| 237 | e := c.cache[module] |
| 238 | if e != nil { |
| 239 | c.cacheMu.Unlock() |
| 240 | // Some other goroutine is getting this module. |
| 241 | // Wait for it to become ready. |
| 242 | |
| 243 | // Detect load cycles to avoid deadlocks. |
| 244 | if err := cycleCheck(e, cc); err != nil { |
| 245 | return nil, err |
| 246 | } |
| 247 | |
| 248 | cc.setWaitsFor(e) |
| 249 | <-e.ready |
| 250 | cc.setWaitsFor(nil) |
| 251 | } else { |
| 252 | // First request for this module. |
| 253 | e = &entry{ready: make(chan struct{})} |
| 254 | c.cache[module] = e |
| 255 | c.cacheMu.Unlock() |
| 256 | |
| 257 | e.setOwner(cc) |
| 258 | e.globals, e.err = c.doLoad(cc, module) |
| 259 | e.setOwner(nil) |
| 260 | |
| 261 | // Broadcast that the entry is now ready. |
| 262 | close(e.ready) |
| 263 | } |
| 264 | return e.globals, e.err |
| 265 | } |
| 266 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 267 | func (c *cache) doLoad(cc *cycleChecker, module string) (starlark.StringDict, error) { |
| 268 | thread := &starlark.Thread{ |
alandonovan | 2c1f362 | 2018-12-17 13:10:16 -0500 | [diff] [blame] | 269 | Name: "exec " + module, |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 270 | Print: func(_ *starlark.Thread, msg string) { fmt.Println(msg) }, |
| 271 | Load: func(_ *starlark.Thread, module string) (starlark.StringDict, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 272 | // Tunnel the cycle-checker state for this "thread of loading". |
| 273 | return c.get(cc, module) |
| 274 | }, |
| 275 | } |
| 276 | data := c.fakeFilesystem[module] |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 277 | return starlark.ExecFile(thread, module, data, nil) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 278 | } |
| 279 | |
| 280 | // -- concurrent cycle checking -- |
| 281 | |
| 282 | // A cycleChecker is used for concurrent deadlock detection. |
| 283 | // Each top-level call to Load creates its own cycleChecker, |
| 284 | // which is passed to all recursive calls it makes. |
| 285 | // It corresponds to a logical thread in the deadlock detection literature. |
| 286 | type cycleChecker struct { |
| 287 | waitsFor unsafe.Pointer // an *entry; see cycleCheck |
| 288 | } |
| 289 | |
| 290 | func (cc *cycleChecker) setWaitsFor(e *entry) { |
| 291 | atomic.StorePointer(&cc.waitsFor, unsafe.Pointer(e)) |
| 292 | } |
| 293 | |
| 294 | func (e *entry) setOwner(cc *cycleChecker) { |
| 295 | atomic.StorePointer(&e.owner, unsafe.Pointer(cc)) |
| 296 | } |
| 297 | |
| 298 | // cycleCheck reports whether there is a path in the waits-for graph |
| 299 | // from resource 'e' to thread 'me'. |
| 300 | // |
| 301 | // The waits-for graph (WFG) is a bipartite graph whose nodes are |
| 302 | // alternately of type entry and cycleChecker. Each node has at most |
| 303 | // one outgoing edge. An entry has an "owner" edge to a cycleChecker |
| 304 | // while it is being readied by that cycleChecker, and a cycleChecker |
| 305 | // has a "waits-for" edge to an entry while it is waiting for that entry |
| 306 | // to become ready. |
| 307 | // |
| 308 | // Before adding a waits-for edge, the cache checks whether the new edge |
| 309 | // would form a cycle. If so, this indicates that the load graph is |
| 310 | // cyclic and that the following wait operation would deadlock. |
| 311 | func cycleCheck(e *entry, me *cycleChecker) error { |
| 312 | for e != nil { |
| 313 | cc := (*cycleChecker)(atomic.LoadPointer(&e.owner)) |
| 314 | if cc == nil { |
| 315 | break |
| 316 | } |
| 317 | if cc == me { |
| 318 | return fmt.Errorf("cycle in load graph") |
| 319 | } |
| 320 | e = (*entry)(atomic.LoadPointer(&cc.waitsFor)) |
| 321 | } |
| 322 | return nil |
| 323 | } |