example_test.go

Documentation: go.starlark.net/starlark

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