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" |
| 10 | "sort" |
| 11 | "strings" |
| 12 | "sync" |
| 13 | "sync/atomic" |
| 14 | "unsafe" |
| 15 | |
Alan Donovan | 6beab7e | 2018-10-31 17:53:09 -0400 | [diff] [blame^] | 16 | "go.starlark.net/starlark" |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 17 | ) |
| 18 | |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 19 | // ExampleExecFile demonstrates a simple embedding |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 20 | // of the Starlark interpreter into a Go program. |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 21 | func ExampleExecFile() { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 22 | const data = ` |
| 23 | print(greeting + ", world") |
| 24 | |
| 25 | squares = [x*x for x in range(10)] |
| 26 | ` |
| 27 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 28 | thread := &starlark.Thread{ |
| 29 | Print: func(_ *starlark.Thread, msg string) { fmt.Println(msg) }, |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 30 | } |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 31 | predeclared := starlark.StringDict{ |
| 32 | "greeting": starlark.String("hello"), |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 33 | } |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 34 | globals, err := starlark.ExecFile(thread, "apparent/filename.star", data, predeclared) |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 35 | if err != nil { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 36 | if evalErr, ok := err.(*starlark.EvalError); ok { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 58 | // squares (list) = [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] |
| 59 | } |
| 60 | |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 61 | // ExampleThread_Load_sequential demonstrates a simple caching |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 62 | // implementation of 'load' that works sequentially. |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 63 | func ExampleThread_Load_sequential() { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 64 | fakeFilesystem := map[string]string{ |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 65 | "c.star": `load("b.star", "b"); c = b + "!"`, |
| 66 | "b.star": `load("a.star", "a"); b = a + ", world"`, |
| 67 | "a.star": `a = "Hello"`, |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 68 | } |
| 69 | |
| 70 | type entry struct { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 71 | globals starlark.StringDict |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 72 | err error |
| 73 | } |
| 74 | |
| 75 | cache := make(map[string]*entry) |
| 76 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 77 | var load func(_ *starlark.Thread, module string) (starlark.StringDict, error) |
| 78 | load = func(_ *starlark.Thread, module string) (starlark.StringDict, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 79 | 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 Donovan | 6c3fcb8 | 2017-10-10 15:47:38 -0400 | [diff] [blame] | 89 | // Load and initialize the module in a new thread. |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 90 | data := fakeFilesystem[module] |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 91 | thread := &starlark.Thread{Load: load} |
| 92 | globals, err := starlark.ExecFile(thread, module, data, nil) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 93 | e = &entry{globals, err} |
| 94 | |
| 95 | // Update the cache. |
| 96 | cache[module] = e |
| 97 | } |
| 98 | return e.globals, e.err |
| 99 | } |
| 100 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 101 | thread := &starlark.Thread{Load: load} |
| 102 | globals, err := load(thread, "c.star") |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 103 | if err != nil { |
| 104 | log.Fatal(err) |
| 105 | } |
| 106 | fmt.Println(globals["c"]) |
| 107 | |
| 108 | // Output: |
| 109 | // "Hello, world!" |
| 110 | } |
| 111 | |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 112 | // ExampleThread_Load_parallel demonstrates a parallel implementation |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 113 | // of 'load' with caching, duplicate suppression, and cycle detection. |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 114 | func ExampleThread_Load_parallel() { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 115 | cache := &cache{ |
| 116 | cache: make(map[string]*entry), |
| 117 | fakeFilesystem: map[string]string{ |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 118 | "c.star": `load("a.star", "a"); c = a * 2`, |
| 119 | "b.star": `load("a.star", "a"); b = a * 3`, |
| 120 | "a.star": `a = 1; print("loaded a")`, |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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) { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 132 | globals, err := cache.Load(name + ".star") |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 | |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 149 | // ExampleThread_Load_parallelCycle demonstrates detection |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 150 | // of cycles during parallel loading. |
Nick Santos | 572cea2 | 2018-05-25 16:41:09 -0400 | [diff] [blame] | 151 | func ExampleThread_Load_parallelCycle() { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 152 | cache := &cache{ |
| 153 | cache: make(map[string]*entry), |
| 154 | fakeFilesystem: map[string]string{ |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 155 | "c.star": `load("b.star", "b"); c = b * 2`, |
| 156 | "b.star": `load("a.star", "a"); b = a * 3`, |
| 157 | "a.star": `load("c.star", "c"); a = c * 5; print("loaded a")`, |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 158 | }, |
| 159 | } |
| 160 | |
| 161 | ch := make(chan string) |
| 162 | for _, name := range "bc" { |
| 163 | name := string(name) |
| 164 | go func() { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 165 | _, err := cache.Load(name + ".star") |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 166 | if err == nil { |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 167 | log.Fatalf("Load of %s.star succeeded unexpectedly", name) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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: |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 177 | // cannot load a.star: cannot load c.star: cycle in load graph |
| 178 | // cannot load b.star: cannot load a.star: cannot load c.star: cycle in load graph |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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. |
| 185 | type cache struct { |
| 186 | cacheMu sync.Mutex |
| 187 | cache map[string]*entry |
| 188 | |
| 189 | fakeFilesystem map[string]string |
| 190 | } |
| 191 | |
| 192 | type entry struct { |
| 193 | owner unsafe.Pointer // a *cycleChecker; see cycleCheck |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 194 | globals starlark.StringDict |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 195 | err error |
| 196 | ready chan struct{} |
| 197 | } |
| 198 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 199 | func (c *cache) Load(module string) (starlark.StringDict, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 200 | return c.get(new(cycleChecker), module) |
| 201 | } |
| 202 | |
| 203 | // get loads and returns an entry (if not already loaded). |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 204 | func (c *cache) get(cc *cycleChecker, module string) (starlark.StringDict, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 | |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 236 | func (c *cache) doLoad(cc *cycleChecker, module string) (starlark.StringDict, error) { |
| 237 | thread := &starlark.Thread{ |
| 238 | Print: func(_ *starlark.Thread, msg string) { fmt.Println(msg) }, |
| 239 | Load: func(_ *starlark.Thread, module string) (starlark.StringDict, error) { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 240 | // Tunnel the cycle-checker state for this "thread of loading". |
| 241 | return c.get(cc, module) |
| 242 | }, |
| 243 | } |
| 244 | data := c.fakeFilesystem[module] |
Alan Donovan | e3deafe | 2018-10-23 11:05:09 -0400 | [diff] [blame] | 245 | return starlark.ExecFile(thread, module, data, nil) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 246 | } |
| 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. |
| 254 | type cycleChecker struct { |
| 255 | waitsFor unsafe.Pointer // an *entry; see cycleCheck |
| 256 | } |
| 257 | |
| 258 | func (cc *cycleChecker) setWaitsFor(e *entry) { |
| 259 | atomic.StorePointer(&cc.waitsFor, unsafe.Pointer(e)) |
| 260 | } |
| 261 | |
| 262 | func (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. |
| 279 | func 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 | } |