Source file src/go.starlark.net/starlark/eval.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
     6  
     7  import (
     8  	"fmt"
     9  	"io"
    10  	"io/ioutil"
    11  	"log"
    12  	"math/big"
    13  	"sort"
    14  	"strings"
    15  	"sync/atomic"
    16  	"time"
    17  	"unicode"
    18  	"unicode/utf8"
    19  	"unsafe"
    20  
    21  	"go.starlark.net/internal/compile"
    22  	"go.starlark.net/internal/spell"
    23  	"go.starlark.net/resolve"
    24  	"go.starlark.net/syntax"
    25  )
    26  
    27  // A Thread contains the state of a Starlark thread,
    28  // such as its call stack and thread-local storage.
    29  // The Thread is threaded throughout the evaluator.
    30  type Thread struct {
    31  	// Name is an optional name that describes the thread, for debugging.
    32  	Name string
    33  
    34  	// stack is the stack of (internal) call frames.
    35  	stack []*frame
    36  
    37  	// Print is the client-supplied implementation of the Starlark
    38  	// 'print' function. If nil, fmt.Fprintln(os.Stderr, msg) is
    39  	// used instead.
    40  	Print func(thread *Thread, msg string)
    41  
    42  	// Load is the client-supplied implementation of module loading.
    43  	// Repeated calls with the same module name must return the same
    44  	// module environment or error.
    45  	// The error message need not include the module name.
    46  	//
    47  	// See example_test.go for some example implementations of Load.
    48  	Load func(thread *Thread, module string) (StringDict, error)
    49  
    50  	// OnMaxSteps is called when the thread reaches the limit set by SetMaxExecutionSteps.
    51  	// The default behavior is to call thread.Cancel("too many steps").
    52  	OnMaxSteps func(thread *Thread)
    53  
    54  	// Steps a count of abstract computation steps executed
    55  	// by this thread. It is incremented by the interpreter. It may be used
    56  	// as a measure of the approximate cost of Starlark execution, by
    57  	// computing the difference in its value before and after a computation.
    58  	//
    59  	// The precise meaning of "step" is not specified and may change.
    60  	Steps, maxSteps uint64
    61  
    62  	// cancelReason records the reason from the first call to Cancel.
    63  	cancelReason *string
    64  
    65  	// locals holds arbitrary "thread-local" Go values belonging to the client.
    66  	// They are accessible to the client but not to any Starlark program.
    67  	locals map[string]interface{}
    68  
    69  	// proftime holds the accumulated execution time since the last profile event.
    70  	proftime time.Duration
    71  }
    72  
    73  // ExecutionSteps returns the current value of Steps.
    74  func (thread *Thread) ExecutionSteps() uint64 {
    75  	return thread.Steps
    76  }
    77  
    78  // SetMaxExecutionSteps sets a limit on the number of Starlark
    79  // computation steps that may be executed by this thread. If the
    80  // thread's step counter exceeds this limit, the interpreter calls
    81  // the optional OnMaxSteps function or the default behavior
    82  // of calling thread.Cancel("too many steps").
    83  func (thread *Thread) SetMaxExecutionSteps(max uint64) {
    84  	thread.maxSteps = max
    85  }
    86  
    87  // Uncancel resets the cancellation state.
    88  //
    89  // Unlike most methods of Thread, it is safe to call Uncancel from any
    90  // goroutine, even if the thread is actively executing.
    91  func (thread *Thread) Uncancel() {
    92  	atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(&thread.cancelReason)), nil)
    93  }
    94  
    95  // Cancel causes execution of Starlark code in the specified thread to
    96  // promptly fail with an EvalError that includes the specified reason.
    97  // There may be a delay before the interpreter observes the cancellation
    98  // if the thread is currently in a call to a built-in function.
    99  //
   100  // Call [Uncancel] to reset the cancellation state.
   101  //
   102  // Unlike most methods of Thread, it is safe to call Cancel from any
   103  // goroutine, even if the thread is actively executing.
   104  func (thread *Thread) Cancel(reason string) {
   105  	// Atomically set cancelReason, preserving earlier reason if any.
   106  	atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&thread.cancelReason)), nil, unsafe.Pointer(&reason))
   107  }
   108  
   109  // SetLocal sets the thread-local value associated with the specified key.
   110  // It must not be called after execution begins.
   111  func (thread *Thread) SetLocal(key string, value interface{}) {
   112  	if thread.locals == nil {
   113  		thread.locals = make(map[string]interface{})
   114  	}
   115  	thread.locals[key] = value
   116  }
   117  
   118  // Local returns the thread-local value associated with the specified key.
   119  func (thread *Thread) Local(key string) interface{} {
   120  	return thread.locals[key]
   121  }
   122  
   123  // CallFrame returns a copy of the specified frame of the callstack.
   124  // It should only be used in built-ins called from Starlark code.
   125  // Depth 0 means the frame of the built-in itself, 1 is its caller, and so on.
   126  //
   127  // It is equivalent to CallStack().At(depth), but more efficient.
   128  func (thread *Thread) CallFrame(depth int) CallFrame {
   129  	return thread.frameAt(depth).asCallFrame()
   130  }
   131  
   132  func (thread *Thread) frameAt(depth int) *frame {
   133  	return thread.stack[len(thread.stack)-1-depth]
   134  }
   135  
   136  // CallStack returns a new slice containing the thread's stack of call frames.
   137  func (thread *Thread) CallStack() CallStack {
   138  	frames := make([]CallFrame, len(thread.stack))
   139  	for i, fr := range thread.stack {
   140  		frames[i] = fr.asCallFrame()
   141  	}
   142  	return frames
   143  }
   144  
   145  // CallStackDepth returns the number of frames in the current call stack.
   146  func (thread *Thread) CallStackDepth() int { return len(thread.stack) }
   147  
   148  // A StringDict is a mapping from names to values, and represents
   149  // an environment such as the global variables of a module.
   150  // It is not a true starlark.Value.
   151  type StringDict map[string]Value
   152  
   153  // Keys returns a new sorted slice of d's keys.
   154  func (d StringDict) Keys() []string {
   155  	names := make([]string, 0, len(d))
   156  	for name := range d {
   157  		names = append(names, name)
   158  	}
   159  	sort.Strings(names)
   160  	return names
   161  }
   162  
   163  func (d StringDict) String() string {
   164  	buf := new(strings.Builder)
   165  	buf.WriteByte('{')
   166  	sep := ""
   167  	for _, name := range d.Keys() {
   168  		buf.WriteString(sep)
   169  		buf.WriteString(name)
   170  		buf.WriteString(": ")
   171  		writeValue(buf, d[name], nil)
   172  		sep = ", "
   173  	}
   174  	buf.WriteByte('}')
   175  	return buf.String()
   176  }
   177  
   178  func (d StringDict) Freeze() {
   179  	for _, v := range d {
   180  		v.Freeze()
   181  	}
   182  }
   183  
   184  // Has reports whether the dictionary contains the specified key.
   185  func (d StringDict) Has(key string) bool { _, ok := d[key]; return ok }
   186  
   187  // A frame records a call to a Starlark function (including module toplevel)
   188  // or a built-in function or method.
   189  type frame struct {
   190  	callable  Callable // current function (or toplevel) or built-in
   191  	pc        uint32   // program counter (Starlark frames only)
   192  	locals    []Value  // local variables (Starlark frames only)
   193  	spanStart int64    // start time of current profiler span
   194  }
   195  
   196  // Position returns the source position of the current point of execution in this frame.
   197  func (fr *frame) Position() syntax.Position {
   198  	switch c := fr.callable.(type) {
   199  	case *Function:
   200  		// Starlark function
   201  		return c.funcode.Position(fr.pc)
   202  	case callableWithPosition:
   203  		// If a built-in Callable defines
   204  		// a Position method, use it.
   205  		return c.Position()
   206  	}
   207  	return syntax.MakePosition(&builtinFilename, 0, 0)
   208  }
   209  
   210  var builtinFilename = "<builtin>"
   211  
   212  // Function returns the frame's function or built-in.
   213  func (fr *frame) Callable() Callable { return fr.callable }
   214  
   215  // A CallStack is a stack of call frames, outermost first.
   216  type CallStack []CallFrame
   217  
   218  // At returns a copy of the frame at depth i.
   219  // At(0) returns the topmost frame.
   220  func (stack CallStack) At(i int) CallFrame { return stack[len(stack)-1-i] }
   221  
   222  // Pop removes and returns the topmost frame.
   223  func (stack *CallStack) Pop() CallFrame {
   224  	last := len(*stack) - 1
   225  	top := (*stack)[last]
   226  	*stack = (*stack)[:last]
   227  	return top
   228  }
   229  
   230  // String returns a user-friendly description of the stack.
   231  func (stack CallStack) String() string {
   232  	out := new(strings.Builder)
   233  	if len(stack) > 0 {
   234  		fmt.Fprintf(out, "Traceback (most recent call last):\n")
   235  	}
   236  	for _, fr := range stack {
   237  		fmt.Fprintf(out, "  %s: in %s\n", fr.Pos, fr.Name)
   238  	}
   239  	return out.String()
   240  }
   241  
   242  // An EvalError is a Starlark evaluation error and
   243  // a copy of the thread's stack at the moment of the error.
   244  type EvalError struct {
   245  	Msg       string
   246  	CallStack CallStack
   247  	cause     error
   248  }
   249  
   250  // A CallFrame represents the function name and current
   251  // position of execution of an enclosing call frame.
   252  type CallFrame struct {
   253  	Name string
   254  	Pos  syntax.Position
   255  }
   256  
   257  func (fr *frame) asCallFrame() CallFrame {
   258  	return CallFrame{
   259  		Name: fr.Callable().Name(),
   260  		Pos:  fr.Position(),
   261  	}
   262  }
   263  
   264  func (thread *Thread) evalError(err error) *EvalError {
   265  	return &EvalError{
   266  		Msg:       err.Error(),
   267  		CallStack: thread.CallStack(),
   268  		cause:     err,
   269  	}
   270  }
   271  
   272  func (e *EvalError) Error() string { return e.Msg }
   273  
   274  // Backtrace returns a user-friendly error message describing the stack
   275  // of calls that led to this error.
   276  func (e *EvalError) Backtrace() string {
   277  	// If the topmost stack frame is a built-in function,
   278  	// remove it from the stack and add print "Error in fn:".
   279  	stack := e.CallStack
   280  	suffix := ""
   281  	if last := len(stack) - 1; last >= 0 && stack[last].Pos.Filename() == builtinFilename {
   282  		suffix = " in " + stack[last].Name
   283  		stack = stack[:last]
   284  	}
   285  	return fmt.Sprintf("%sError%s: %s", stack, suffix, e.Msg)
   286  }
   287  
   288  func (e *EvalError) Unwrap() error { return e.cause }
   289  
   290  // A Program is a compiled Starlark program.
   291  //
   292  // Programs are immutable, and contain no Values.
   293  // A Program may be created by parsing a source file (see SourceProgram)
   294  // or by loading a previously saved compiled program (see CompiledProgram).
   295  type Program struct {
   296  	compiled *compile.Program
   297  }
   298  
   299  // CompilerVersion is the version number of the protocol for compiled
   300  // files. Applications must not run programs compiled by one version
   301  // with an interpreter at another version, and should thus incorporate
   302  // the compiler version into the cache key when reusing compiled code.
   303  const CompilerVersion = compile.Version
   304  
   305  // Filename returns the name of the file from which this program was loaded.
   306  func (prog *Program) Filename() string { return prog.compiled.Toplevel.Pos.Filename() }
   307  
   308  func (prog *Program) String() string { return prog.Filename() }
   309  
   310  // NumLoads returns the number of load statements in the compiled program.
   311  func (prog *Program) NumLoads() int { return len(prog.compiled.Loads) }
   312  
   313  // Load(i) returns the name and position of the i'th module directly
   314  // loaded by this one, where 0 <= i < NumLoads().
   315  // The name is unresolved---exactly as it appears in the source.
   316  func (prog *Program) Load(i int) (string, syntax.Position) {
   317  	id := prog.compiled.Loads[i]
   318  	return id.Name, id.Pos
   319  }
   320  
   321  // WriteTo writes the compiled module to the specified output stream.
   322  func (prog *Program) Write(out io.Writer) error {
   323  	data := prog.compiled.Encode()
   324  	_, err := out.Write(data)
   325  	return err
   326  }
   327  
   328  // ExecFile parses, resolves, and executes a Starlark file in the
   329  // specified global environment, which may be modified during execution.
   330  //
   331  // Thread is the state associated with the Starlark thread.
   332  //
   333  // The filename and src parameters are as for syntax.Parse:
   334  // filename is the name of the file to execute,
   335  // and the name that appears in error messages;
   336  // src is an optional source of bytes to use
   337  // instead of filename.
   338  //
   339  // predeclared defines the predeclared names specific to this module.
   340  // Execution does not modify this dictionary, though it may mutate
   341  // its values.
   342  //
   343  // If ExecFile fails during evaluation, it returns an *EvalError
   344  // containing a backtrace.
   345  func ExecFile(thread *Thread, filename string, src interface{}, predeclared StringDict) (StringDict, error) {
   346  	// Parse, resolve, and compile a Starlark source file.
   347  	_, mod, err := SourceProgram(filename, src, predeclared.Has)
   348  	if err != nil {
   349  		return nil, err
   350  	}
   351  
   352  	g, err := mod.Init(thread, predeclared)
   353  	g.Freeze()
   354  	return g, err
   355  }
   356  
   357  // SourceProgram produces a new program by parsing, resolving,
   358  // and compiling a Starlark source file.
   359  // On success, it returns the parsed file and the compiled program.
   360  // The filename and src parameters are as for syntax.Parse.
   361  //
   362  // The isPredeclared predicate reports whether a name is
   363  // a pre-declared identifier of the current module.
   364  // Its typical value is predeclared.Has,
   365  // where predeclared is a StringDict of pre-declared values.
   366  func SourceProgram(filename string, src interface{}, isPredeclared func(string) bool) (*syntax.File, *Program, error) {
   367  	f, err := syntax.Parse(filename, src, 0)
   368  	if err != nil {
   369  		return nil, nil, err
   370  	}
   371  	prog, err := FileProgram(f, isPredeclared)
   372  	return f, prog, err
   373  }
   374  
   375  // FileProgram produces a new program by resolving,
   376  // and compiling the Starlark source file syntax tree.
   377  // On success, it returns the compiled program.
   378  //
   379  // Resolving a syntax tree mutates it.
   380  // Do not call FileProgram more than once on the same file.
   381  //
   382  // The isPredeclared predicate reports whether a name is
   383  // a pre-declared identifier of the current module.
   384  // Its typical value is predeclared.Has,
   385  // where predeclared is a StringDict of pre-declared values.
   386  func FileProgram(f *syntax.File, isPredeclared func(string) bool) (*Program, error) {
   387  	if err := resolve.File(f, isPredeclared, Universe.Has); err != nil {
   388  		return nil, err
   389  	}
   390  
   391  	var pos syntax.Position
   392  	if len(f.Stmts) > 0 {
   393  		pos = syntax.Start(f.Stmts[0])
   394  	} else {
   395  		pos = syntax.MakePosition(&f.Path, 1, 1)
   396  	}
   397  
   398  	module := f.Module.(*resolve.Module)
   399  	compiled := compile.File(f.Stmts, pos, "<toplevel>", module.Locals, module.Globals)
   400  
   401  	return &Program{compiled}, nil
   402  }
   403  
   404  // CompiledProgram produces a new program from the representation
   405  // of a compiled program previously saved by Program.Write.
   406  func CompiledProgram(in io.Reader) (*Program, error) {
   407  	data, err := ioutil.ReadAll(in)
   408  	if err != nil {
   409  		return nil, err
   410  	}
   411  	compiled, err := compile.DecodeProgram(data)
   412  	if err != nil {
   413  		return nil, err
   414  	}
   415  	return &Program{compiled}, nil
   416  }
   417  
   418  // Init creates a set of global variables for the program,
   419  // executes the toplevel code of the specified program,
   420  // and returns a new, unfrozen dictionary of the globals.
   421  func (prog *Program) Init(thread *Thread, predeclared StringDict) (StringDict, error) {
   422  	toplevel := makeToplevelFunction(prog.compiled, predeclared)
   423  
   424  	_, err := Call(thread, toplevel, nil, nil)
   425  
   426  	// Convert the global environment to a map.
   427  	// We return a (partial) map even in case of error.
   428  	return toplevel.Globals(), err
   429  }
   430  
   431  // ExecREPLChunk compiles and executes file f in the specified thread
   432  // and global environment. This is a variant of ExecFile specialized to
   433  // the needs of a REPL, in which a sequence of input chunks, each
   434  // syntactically a File, manipulates the same set of module globals,
   435  // which are not frozen after execution.
   436  //
   437  // This function is intended to support only go.starlark.net/repl.
   438  // Its API stability is not guaranteed.
   439  func ExecREPLChunk(f *syntax.File, thread *Thread, globals StringDict) error {
   440  	var predeclared StringDict
   441  
   442  	// -- variant of FileProgram --
   443  
   444  	if err := resolve.REPLChunk(f, globals.Has, predeclared.Has, Universe.Has); err != nil {
   445  		return err
   446  	}
   447  
   448  	var pos syntax.Position
   449  	if len(f.Stmts) > 0 {
   450  		pos = syntax.Start(f.Stmts[0])
   451  	} else {
   452  		pos = syntax.MakePosition(&f.Path, 1, 1)
   453  	}
   454  
   455  	module := f.Module.(*resolve.Module)
   456  	compiled := compile.File(f.Stmts, pos, "<toplevel>", module.Locals, module.Globals)
   457  	prog := &Program{compiled}
   458  
   459  	// -- variant of Program.Init --
   460  
   461  	toplevel := makeToplevelFunction(prog.compiled, predeclared)
   462  
   463  	// Initialize module globals from parameter.
   464  	for i, id := range prog.compiled.Globals {
   465  		if v := globals[id.Name]; v != nil {
   466  			toplevel.module.globals[i] = v
   467  		}
   468  	}
   469  
   470  	_, err := Call(thread, toplevel, nil, nil)
   471  
   472  	// Reflect changes to globals back to parameter, even after an error.
   473  	for i, id := range prog.compiled.Globals {
   474  		if v := toplevel.module.globals[i]; v != nil {
   475  			globals[id.Name] = v
   476  		}
   477  	}
   478  
   479  	return err
   480  }
   481  
   482  func makeToplevelFunction(prog *compile.Program, predeclared StringDict) *Function {
   483  	// Create the Starlark value denoted by each program constant c.
   484  	constants := make([]Value, len(prog.Constants))
   485  	for i, c := range prog.Constants {
   486  		var v Value
   487  		switch c := c.(type) {
   488  		case int64:
   489  			v = MakeInt64(c)
   490  		case *big.Int:
   491  			v = MakeBigInt(c)
   492  		case string:
   493  			v = String(c)
   494  		case compile.Bytes:
   495  			v = Bytes(c)
   496  		case float64:
   497  			v = Float(c)
   498  		default:
   499  			log.Panicf("unexpected constant %T: %v", c, c)
   500  		}
   501  		constants[i] = v
   502  	}
   503  
   504  	return &Function{
   505  		funcode: prog.Toplevel,
   506  		module: &module{
   507  			program:     prog,
   508  			predeclared: predeclared,
   509  			globals:     make([]Value, len(prog.Globals)),
   510  			constants:   constants,
   511  		},
   512  	}
   513  }
   514  
   515  // Eval parses, resolves, and evaluates an expression within the
   516  // specified (predeclared) environment.
   517  //
   518  // Evaluation cannot mutate the environment dictionary itself,
   519  // though it may modify variables reachable from the dictionary.
   520  //
   521  // The filename and src parameters are as for syntax.Parse.
   522  //
   523  // If Eval fails during evaluation, it returns an *EvalError
   524  // containing a backtrace.
   525  func Eval(thread *Thread, filename string, src interface{}, env StringDict) (Value, error) {
   526  	expr, err := syntax.ParseExpr(filename, src, 0)
   527  	if err != nil {
   528  		return nil, err
   529  	}
   530  	f, err := makeExprFunc(expr, env)
   531  	if err != nil {
   532  		return nil, err
   533  	}
   534  	return Call(thread, f, nil, nil)
   535  }
   536  
   537  // EvalExpr resolves and evaluates an expression within the
   538  // specified (predeclared) environment.
   539  // Evaluating a comma-separated list of expressions yields a tuple value.
   540  //
   541  // Resolving an expression mutates it.
   542  // Do not call EvalExpr more than once for the same expression.
   543  //
   544  // Evaluation cannot mutate the environment dictionary itself,
   545  // though it may modify variables reachable from the dictionary.
   546  //
   547  // If Eval fails during evaluation, it returns an *EvalError
   548  // containing a backtrace.
   549  func EvalExpr(thread *Thread, expr syntax.Expr, env StringDict) (Value, error) {
   550  	fn, err := makeExprFunc(expr, env)
   551  	if err != nil {
   552  		return nil, err
   553  	}
   554  	return Call(thread, fn, nil, nil)
   555  }
   556  
   557  // ExprFunc returns a no-argument function
   558  // that evaluates the expression whose source is src.
   559  func ExprFunc(filename string, src interface{}, env StringDict) (*Function, error) {
   560  	expr, err := syntax.ParseExpr(filename, src, 0)
   561  	if err != nil {
   562  		return nil, err
   563  	}
   564  	return makeExprFunc(expr, env)
   565  }
   566  
   567  // makeExprFunc returns a no-argument function whose body is expr.
   568  func makeExprFunc(expr syntax.Expr, env StringDict) (*Function, error) {
   569  	locals, err := resolve.Expr(expr, env.Has, Universe.Has)
   570  	if err != nil {
   571  		return nil, err
   572  	}
   573  
   574  	return makeToplevelFunction(compile.Expr(expr, "<expr>", locals), env), nil
   575  }
   576  
   577  // The following functions are primitive operations of the byte code interpreter.
   578  
   579  // list += iterable
   580  func listExtend(x *List, y Iterable) {
   581  	if ylist, ok := y.(*List); ok {
   582  		// fast path: list += list
   583  		x.elems = append(x.elems, ylist.elems...)
   584  	} else {
   585  		iter := y.Iterate()
   586  		defer iter.Done()
   587  		var z Value
   588  		for iter.Next(&z) {
   589  			x.elems = append(x.elems, z)
   590  		}
   591  	}
   592  }
   593  
   594  // getAttr implements x.dot.
   595  func getAttr(x Value, name string) (Value, error) {
   596  	hasAttr, ok := x.(HasAttrs)
   597  	if !ok {
   598  		return nil, fmt.Errorf("%s has no .%s field or method", x.Type(), name)
   599  	}
   600  
   601  	var errmsg string
   602  	v, err := hasAttr.Attr(name)
   603  	if err == nil {
   604  		if v != nil {
   605  			return v, nil // success
   606  		}
   607  		// (nil, nil) => generic error
   608  		errmsg = fmt.Sprintf("%s has no .%s field or method", x.Type(), name)
   609  	} else if nsa, ok := err.(NoSuchAttrError); ok {
   610  		errmsg = string(nsa)
   611  	} else {
   612  		return nil, err // return error as is
   613  	}
   614  
   615  	// add spelling hint
   616  	if n := spell.Nearest(name, hasAttr.AttrNames()); n != "" {
   617  		errmsg = fmt.Sprintf("%s (did you mean .%s?)", errmsg, n)
   618  	}
   619  
   620  	return nil, fmt.Errorf("%s", errmsg)
   621  }
   622  
   623  // setField implements x.name = y.
   624  func setField(x Value, name string, y Value) error {
   625  	if x, ok := x.(HasSetField); ok {
   626  		err := x.SetField(name, y)
   627  		if _, ok := err.(NoSuchAttrError); ok {
   628  			// No such field: check spelling.
   629  			if n := spell.Nearest(name, x.AttrNames()); n != "" {
   630  				err = fmt.Errorf("%s (did you mean .%s?)", err, n)
   631  			}
   632  		}
   633  		return err
   634  	}
   635  
   636  	return fmt.Errorf("can't assign to .%s field of %s", name, x.Type())
   637  }
   638  
   639  // getIndex implements x[y].
   640  func getIndex(x, y Value) (Value, error) {
   641  	switch x := x.(type) {
   642  	case Mapping: // dict
   643  		z, found, err := x.Get(y)
   644  		if err != nil {
   645  			return nil, err
   646  		}
   647  		if !found {
   648  			return nil, fmt.Errorf("key %v not in %s", y, x.Type())
   649  		}
   650  		return z, nil
   651  
   652  	case Indexable: // string, list, tuple
   653  		n := x.Len()
   654  		i, err := AsInt32(y)
   655  		if err != nil {
   656  			return nil, fmt.Errorf("%s index: %s", x.Type(), err)
   657  		}
   658  		origI := i
   659  		if i < 0 {
   660  			i += n
   661  		}
   662  		if i < 0 || i >= n {
   663  			return nil, outOfRange(origI, n, x)
   664  		}
   665  		return x.Index(i), nil
   666  	}
   667  	return nil, fmt.Errorf("unhandled index operation %s[%s]", x.Type(), y.Type())
   668  }
   669  
   670  func outOfRange(i, n int, x Value) error {
   671  	if n == 0 {
   672  		return fmt.Errorf("index %d out of range: empty %s", i, x.Type())
   673  	} else {
   674  		return fmt.Errorf("%s index %d out of range [%d:%d]", x.Type(), i, -n, n-1)
   675  	}
   676  }
   677  
   678  // setIndex implements x[y] = z.
   679  func setIndex(x, y, z Value) error {
   680  	switch x := x.(type) {
   681  	case HasSetKey:
   682  		if err := x.SetKey(y, z); err != nil {
   683  			return err
   684  		}
   685  
   686  	case HasSetIndex:
   687  		n := x.Len()
   688  		i, err := AsInt32(y)
   689  		if err != nil {
   690  			return err
   691  		}
   692  		origI := i
   693  		if i < 0 {
   694  			i += n
   695  		}
   696  		if i < 0 || i >= n {
   697  			return outOfRange(origI, n, x)
   698  		}
   699  		return x.SetIndex(i, z)
   700  
   701  	default:
   702  		return fmt.Errorf("%s value does not support item assignment", x.Type())
   703  	}
   704  	return nil
   705  }
   706  
   707  // Unary applies a unary operator (+, -, ~, not) to its operand.
   708  func Unary(op syntax.Token, x Value) (Value, error) {
   709  	// The NOT operator is not customizable.
   710  	if op == syntax.NOT {
   711  		return !x.Truth(), nil
   712  	}
   713  
   714  	// Int, Float, and user-defined types
   715  	if x, ok := x.(HasUnary); ok {
   716  		// (nil, nil) => unhandled
   717  		y, err := x.Unary(op)
   718  		if y != nil || err != nil {
   719  			return y, err
   720  		}
   721  	}
   722  
   723  	return nil, fmt.Errorf("unknown unary op: %s %s", op, x.Type())
   724  }
   725  
   726  // Binary applies a strict binary operator (not AND or OR) to its operands.
   727  // For equality tests or ordered comparisons, use Compare instead.
   728  func Binary(op syntax.Token, x, y Value) (Value, error) {
   729  	switch op {
   730  	case syntax.PLUS:
   731  		switch x := x.(type) {
   732  		case String:
   733  			if y, ok := y.(String); ok {
   734  				return x + y, nil
   735  			}
   736  		case Int:
   737  			switch y := y.(type) {
   738  			case Int:
   739  				return x.Add(y), nil
   740  			case Float:
   741  				xf, err := x.finiteFloat()
   742  				if err != nil {
   743  					return nil, err
   744  				}
   745  				return xf + y, nil
   746  			}
   747  		case Float:
   748  			switch y := y.(type) {
   749  			case Float:
   750  				return x + y, nil
   751  			case Int:
   752  				yf, err := y.finiteFloat()
   753  				if err != nil {
   754  					return nil, err
   755  				}
   756  				return x + yf, nil
   757  			}
   758  		case *List:
   759  			if y, ok := y.(*List); ok {
   760  				z := make([]Value, 0, x.Len()+y.Len())
   761  				z = append(z, x.elems...)
   762  				z = append(z, y.elems...)
   763  				return NewList(z), nil
   764  			}
   765  		case Tuple:
   766  			if y, ok := y.(Tuple); ok {
   767  				z := make(Tuple, 0, len(x)+len(y))
   768  				z = append(z, x...)
   769  				z = append(z, y...)
   770  				return z, nil
   771  			}
   772  		}
   773  
   774  	case syntax.MINUS:
   775  		switch x := x.(type) {
   776  		case Int:
   777  			switch y := y.(type) {
   778  			case Int:
   779  				return x.Sub(y), nil
   780  			case Float:
   781  				xf, err := x.finiteFloat()
   782  				if err != nil {
   783  					return nil, err
   784  				}
   785  				return xf - y, nil
   786  			}
   787  		case Float:
   788  			switch y := y.(type) {
   789  			case Float:
   790  				return x - y, nil
   791  			case Int:
   792  				yf, err := y.finiteFloat()
   793  				if err != nil {
   794  					return nil, err
   795  				}
   796  				return x - yf, nil
   797  			}
   798  		}
   799  
   800  	case syntax.STAR:
   801  		switch x := x.(type) {
   802  		case Int:
   803  			switch y := y.(type) {
   804  			case Int:
   805  				return x.Mul(y), nil
   806  			case Float:
   807  				xf, err := x.finiteFloat()
   808  				if err != nil {
   809  					return nil, err
   810  				}
   811  				return xf * y, nil
   812  			case String:
   813  				return stringRepeat(y, x)
   814  			case Bytes:
   815  				return bytesRepeat(y, x)
   816  			case *List:
   817  				elems, err := tupleRepeat(Tuple(y.elems), x)
   818  				if err != nil {
   819  					return nil, err
   820  				}
   821  				return NewList(elems), nil
   822  			case Tuple:
   823  				return tupleRepeat(y, x)
   824  			}
   825  		case Float:
   826  			switch y := y.(type) {
   827  			case Float:
   828  				return x * y, nil
   829  			case Int:
   830  				yf, err := y.finiteFloat()
   831  				if err != nil {
   832  					return nil, err
   833  				}
   834  				return x * yf, nil
   835  			}
   836  		case String:
   837  			if y, ok := y.(Int); ok {
   838  				return stringRepeat(x, y)
   839  			}
   840  		case Bytes:
   841  			if y, ok := y.(Int); ok {
   842  				return bytesRepeat(x, y)
   843  			}
   844  		case *List:
   845  			if y, ok := y.(Int); ok {
   846  				elems, err := tupleRepeat(Tuple(x.elems), y)
   847  				if err != nil {
   848  					return nil, err
   849  				}
   850  				return NewList(elems), nil
   851  			}
   852  		case Tuple:
   853  			if y, ok := y.(Int); ok {
   854  				return tupleRepeat(x, y)
   855  			}
   856  
   857  		}
   858  
   859  	case syntax.SLASH:
   860  		switch x := x.(type) {
   861  		case Int:
   862  			xf, err := x.finiteFloat()
   863  			if err != nil {
   864  				return nil, err
   865  			}
   866  			switch y := y.(type) {
   867  			case Int:
   868  				yf, err := y.finiteFloat()
   869  				if err != nil {
   870  					return nil, err
   871  				}
   872  				if yf == 0.0 {
   873  					return nil, fmt.Errorf("floating-point division by zero")
   874  				}
   875  				return xf / yf, nil
   876  			case Float:
   877  				if y == 0.0 {
   878  					return nil, fmt.Errorf("floating-point division by zero")
   879  				}
   880  				return xf / y, nil
   881  			}
   882  		case Float:
   883  			switch y := y.(type) {
   884  			case Float:
   885  				if y == 0.0 {
   886  					return nil, fmt.Errorf("floating-point division by zero")
   887  				}
   888  				return x / y, nil
   889  			case Int:
   890  				yf, err := y.finiteFloat()
   891  				if err != nil {
   892  					return nil, err
   893  				}
   894  				if yf == 0.0 {
   895  					return nil, fmt.Errorf("floating-point division by zero")
   896  				}
   897  				return x / yf, nil
   898  			}
   899  		}
   900  
   901  	case syntax.SLASHSLASH:
   902  		switch x := x.(type) {
   903  		case Int:
   904  			switch y := y.(type) {
   905  			case Int:
   906  				if y.Sign() == 0 {
   907  					return nil, fmt.Errorf("floored division by zero")
   908  				}
   909  				return x.Div(y), nil
   910  			case Float:
   911  				xf, err := x.finiteFloat()
   912  				if err != nil {
   913  					return nil, err
   914  				}
   915  				if y == 0.0 {
   916  					return nil, fmt.Errorf("floored division by zero")
   917  				}
   918  				return floor(xf / y), nil
   919  			}
   920  		case Float:
   921  			switch y := y.(type) {
   922  			case Float:
   923  				if y == 0.0 {
   924  					return nil, fmt.Errorf("floored division by zero")
   925  				}
   926  				return floor(x / y), nil
   927  			case Int:
   928  				yf, err := y.finiteFloat()
   929  				if err != nil {
   930  					return nil, err
   931  				}
   932  				if yf == 0.0 {
   933  					return nil, fmt.Errorf("floored division by zero")
   934  				}
   935  				return floor(x / yf), nil
   936  			}
   937  		}
   938  
   939  	case syntax.PERCENT:
   940  		switch x := x.(type) {
   941  		case Int:
   942  			switch y := y.(type) {
   943  			case Int:
   944  				if y.Sign() == 0 {
   945  					return nil, fmt.Errorf("integer modulo by zero")
   946  				}
   947  				return x.Mod(y), nil
   948  			case Float:
   949  				xf, err := x.finiteFloat()
   950  				if err != nil {
   951  					return nil, err
   952  				}
   953  				if y == 0 {
   954  					return nil, fmt.Errorf("floating-point modulo by zero")
   955  				}
   956  				return xf.Mod(y), nil
   957  			}
   958  		case Float:
   959  			switch y := y.(type) {
   960  			case Float:
   961  				if y == 0.0 {
   962  					return nil, fmt.Errorf("floating-point modulo by zero")
   963  				}
   964  				return x.Mod(y), nil
   965  			case Int:
   966  				if y.Sign() == 0 {
   967  					return nil, fmt.Errorf("floating-point modulo by zero")
   968  				}
   969  				yf, err := y.finiteFloat()
   970  				if err != nil {
   971  					return nil, err
   972  				}
   973  				return x.Mod(yf), nil
   974  			}
   975  		case String:
   976  			return interpolate(string(x), y)
   977  		}
   978  
   979  	case syntax.NOT_IN:
   980  		z, err := Binary(syntax.IN, x, y)
   981  		if err != nil {
   982  			return nil, err
   983  		}
   984  		return !z.Truth(), nil
   985  
   986  	case syntax.IN:
   987  		switch y := y.(type) {
   988  		case *List:
   989  			for _, elem := range y.elems {
   990  				if eq, err := Equal(elem, x); err != nil {
   991  					return nil, err
   992  				} else if eq {
   993  					return True, nil
   994  				}
   995  			}
   996  			return False, nil
   997  		case Tuple:
   998  			for _, elem := range y {
   999  				if eq, err := Equal(elem, x); err != nil {
  1000  					return nil, err
  1001  				} else if eq {
  1002  					return True, nil
  1003  				}
  1004  			}
  1005  			return False, nil
  1006  		case Mapping: // e.g. dict
  1007  			// Ignore error from Get as we cannot distinguish true
  1008  			// errors (value cycle, type error) from "key not found".
  1009  			_, found, _ := y.Get(x)
  1010  			return Bool(found), nil
  1011  		case *Set:
  1012  			ok, err := y.Has(x)
  1013  			return Bool(ok), err
  1014  		case String:
  1015  			needle, ok := x.(String)
  1016  			if !ok {
  1017  				return nil, fmt.Errorf("'in <string>' requires string as left operand, not %s", x.Type())
  1018  			}
  1019  			return Bool(strings.Contains(string(y), string(needle))), nil
  1020  		case Bytes:
  1021  			switch needle := x.(type) {
  1022  			case Bytes:
  1023  				return Bool(strings.Contains(string(y), string(needle))), nil
  1024  			case Int:
  1025  				var b byte
  1026  				if err := AsInt(needle, &b); err != nil {
  1027  					return nil, fmt.Errorf("int in bytes: %s", err)
  1028  				}
  1029  				return Bool(strings.IndexByte(string(y), b) >= 0), nil
  1030  			default:
  1031  				return nil, fmt.Errorf("'in bytes' requires bytes or int as left operand, not %s", x.Type())
  1032  			}
  1033  		case rangeValue:
  1034  			i, err := NumberToInt(x)
  1035  			if err != nil {
  1036  				return nil, fmt.Errorf("'in <range>' requires integer as left operand, not %s", x.Type())
  1037  			}
  1038  			return Bool(y.contains(i)), nil
  1039  		}
  1040  
  1041  	case syntax.PIPE:
  1042  		switch x := x.(type) {
  1043  		case Int:
  1044  			if y, ok := y.(Int); ok {
  1045  				return x.Or(y), nil
  1046  			}
  1047  
  1048  		case *Dict: // union
  1049  			if y, ok := y.(*Dict); ok {
  1050  				return x.Union(y), nil
  1051  			}
  1052  
  1053  		case *Set: // union
  1054  			if y, ok := y.(*Set); ok {
  1055  				iter := Iterate(y)
  1056  				defer iter.Done()
  1057  				return x.Union(iter)
  1058  			}
  1059  		}
  1060  
  1061  	case syntax.AMP:
  1062  		switch x := x.(type) {
  1063  		case Int:
  1064  			if y, ok := y.(Int); ok {
  1065  				return x.And(y), nil
  1066  			}
  1067  		case *Set: // intersection
  1068  			if y, ok := y.(*Set); ok {
  1069  				set := new(Set)
  1070  				if x.Len() > y.Len() {
  1071  					x, y = y, x // opt: range over smaller set
  1072  				}
  1073  				for xe := x.ht.head; xe != nil; xe = xe.next {
  1074  					// Has, Insert cannot fail here.
  1075  					if found, _ := y.Has(xe.key); found {
  1076  						set.Insert(xe.key)
  1077  					}
  1078  				}
  1079  				return set, nil
  1080  			}
  1081  		}
  1082  
  1083  	case syntax.CIRCUMFLEX:
  1084  		switch x := x.(type) {
  1085  		case Int:
  1086  			if y, ok := y.(Int); ok {
  1087  				return x.Xor(y), nil
  1088  			}
  1089  		case *Set: // symmetric difference
  1090  			if y, ok := y.(*Set); ok {
  1091  				set := new(Set)
  1092  				for xe := x.ht.head; xe != nil; xe = xe.next {
  1093  					if found, _ := y.Has(xe.key); !found {
  1094  						set.Insert(xe.key)
  1095  					}
  1096  				}
  1097  				for ye := y.ht.head; ye != nil; ye = ye.next {
  1098  					if found, _ := x.Has(ye.key); !found {
  1099  						set.Insert(ye.key)
  1100  					}
  1101  				}
  1102  				return set, nil
  1103  			}
  1104  		}
  1105  
  1106  	case syntax.LTLT, syntax.GTGT:
  1107  		if x, ok := x.(Int); ok {
  1108  			y, err := AsInt32(y)
  1109  			if err != nil {
  1110  				return nil, err
  1111  			}
  1112  			if y < 0 {
  1113  				return nil, fmt.Errorf("negative shift count: %v", y)
  1114  			}
  1115  			if op == syntax.LTLT {
  1116  				if y >= 512 {
  1117  					return nil, fmt.Errorf("shift count too large: %v", y)
  1118  				}
  1119  				return x.Lsh(uint(y)), nil
  1120  			} else {
  1121  				return x.Rsh(uint(y)), nil
  1122  			}
  1123  		}
  1124  
  1125  	default:
  1126  		// unknown operator
  1127  		goto unknown
  1128  	}
  1129  
  1130  	// user-defined types
  1131  	// (nil, nil) => unhandled
  1132  	if x, ok := x.(HasBinary); ok {
  1133  		z, err := x.Binary(op, y, Left)
  1134  		if z != nil || err != nil {
  1135  			return z, err
  1136  		}
  1137  	}
  1138  	if y, ok := y.(HasBinary); ok {
  1139  		z, err := y.Binary(op, x, Right)
  1140  		if z != nil || err != nil {
  1141  			return z, err
  1142  		}
  1143  	}
  1144  
  1145  	// unsupported operand types
  1146  unknown:
  1147  	return nil, fmt.Errorf("unknown binary op: %s %s %s", x.Type(), op, y.Type())
  1148  }
  1149  
  1150  // It's always possible to overeat in small bites but we'll
  1151  // try to stop someone swallowing the world in one gulp.
  1152  const maxAlloc = 1 << 30
  1153  
  1154  func tupleRepeat(elems Tuple, n Int) (Tuple, error) {
  1155  	if len(elems) == 0 {
  1156  		return nil, nil
  1157  	}
  1158  	i, err := AsInt32(n)
  1159  	if err != nil {
  1160  		return nil, fmt.Errorf("repeat count %s too large", n)
  1161  	}
  1162  	if i < 1 {
  1163  		return nil, nil
  1164  	}
  1165  	// Inv: i > 0, len > 0
  1166  	sz := len(elems) * i
  1167  	if sz < 0 || sz >= maxAlloc { // sz < 0 => overflow
  1168  		// Don't print sz.
  1169  		return nil, fmt.Errorf("excessive repeat (%d * %d elements)", len(elems), i)
  1170  	}
  1171  	res := make([]Value, sz)
  1172  	// copy elems into res, doubling each time
  1173  	x := copy(res, elems)
  1174  	for x < len(res) {
  1175  		copy(res[x:], res[:x])
  1176  		x *= 2
  1177  	}
  1178  	return res, nil
  1179  }
  1180  
  1181  func bytesRepeat(b Bytes, n Int) (Bytes, error) {
  1182  	res, err := stringRepeat(String(b), n)
  1183  	return Bytes(res), err
  1184  }
  1185  
  1186  func stringRepeat(s String, n Int) (String, error) {
  1187  	if s == "" {
  1188  		return "", nil
  1189  	}
  1190  	i, err := AsInt32(n)
  1191  	if err != nil {
  1192  		return "", fmt.Errorf("repeat count %s too large", n)
  1193  	}
  1194  	if i < 1 {
  1195  		return "", nil
  1196  	}
  1197  	// Inv: i > 0, len > 0
  1198  	sz := len(s) * i
  1199  	if sz < 0 || sz >= maxAlloc { // sz < 0 => overflow
  1200  		// Don't print sz.
  1201  		return "", fmt.Errorf("excessive repeat (%d * %d elements)", len(s), i)
  1202  	}
  1203  	return String(strings.Repeat(string(s), i)), nil
  1204  }
  1205  
  1206  // Call calls the function fn with the specified positional and keyword arguments.
  1207  func Call(thread *Thread, fn Value, args Tuple, kwargs []Tuple) (Value, error) {
  1208  	c, ok := fn.(Callable)
  1209  	if !ok {
  1210  		return nil, fmt.Errorf("invalid call of non-function (%s)", fn.Type())
  1211  	}
  1212  
  1213  	// Allocate and push a new frame.
  1214  	var fr *frame
  1215  	// Optimization: use slack portion of thread.stack
  1216  	// slice as a freelist of empty frames.
  1217  	if n := len(thread.stack); n < cap(thread.stack) {
  1218  		fr = thread.stack[n : n+1][0]
  1219  	}
  1220  	if fr == nil {
  1221  		fr = new(frame)
  1222  	}
  1223  
  1224  	if thread.stack == nil {
  1225  		// one-time initialization of thread
  1226  		if thread.maxSteps == 0 {
  1227  			thread.maxSteps-- // (MaxUint64)
  1228  		}
  1229  	}
  1230  
  1231  	thread.stack = append(thread.stack, fr) // push
  1232  
  1233  	fr.callable = c
  1234  
  1235  	thread.beginProfSpan()
  1236  
  1237  	// Use defer to ensure that panics from built-ins
  1238  	// pass through the interpreter without leaving
  1239  	// it in a bad state.
  1240  	defer func() {
  1241  		thread.endProfSpan()
  1242  
  1243  		// clear out any references
  1244  		// TODO(adonovan): opt: zero fr.Locals and
  1245  		// reuse it if it is large enough.
  1246  		*fr = frame{}
  1247  
  1248  		thread.stack = thread.stack[:len(thread.stack)-1] // pop
  1249  	}()
  1250  
  1251  	result, err := c.CallInternal(thread, args, kwargs)
  1252  
  1253  	// Sanity check: nil is not a valid Starlark value.
  1254  	if result == nil && err == nil {
  1255  		err = fmt.Errorf("internal error: nil (not None) returned from %s", fn)
  1256  	}
  1257  
  1258  	// Always return an EvalError with an accurate frame.
  1259  	if err != nil {
  1260  		if _, ok := err.(*EvalError); !ok {
  1261  			err = thread.evalError(err)
  1262  		}
  1263  	}
  1264  
  1265  	return result, err
  1266  }
  1267  
  1268  func slice(x, lo, hi, step_ Value) (Value, error) {
  1269  	sliceable, ok := x.(Sliceable)
  1270  	if !ok {
  1271  		return nil, fmt.Errorf("invalid slice operand %s", x.Type())
  1272  	}
  1273  
  1274  	n := sliceable.Len()
  1275  	step := 1
  1276  	if step_ != None {
  1277  		var err error
  1278  		step, err = AsInt32(step_)
  1279  		if err != nil {
  1280  			return nil, fmt.Errorf("invalid slice step: %s", err)
  1281  		}
  1282  		if step == 0 {
  1283  			return nil, fmt.Errorf("zero is not a valid slice step")
  1284  		}
  1285  	}
  1286  
  1287  	// TODO(adonovan): opt: preallocate result array.
  1288  
  1289  	var start, end int
  1290  	if step > 0 {
  1291  		// positive stride
  1292  		// default indices are [0:n].
  1293  		var err error
  1294  		start, end, err = indices(lo, hi, n)
  1295  		if err != nil {
  1296  			return nil, err
  1297  		}
  1298  
  1299  		if end < start {
  1300  			end = start // => empty result
  1301  		}
  1302  	} else {
  1303  		// negative stride
  1304  		// default indices are effectively [n-1:-1], though to
  1305  		// get this effect using explicit indices requires
  1306  		// [n-1:-1-n:-1] because of the treatment of -ve values.
  1307  		start = n - 1
  1308  		if err := asIndex(lo, n, &start); err != nil {
  1309  			return nil, fmt.Errorf("invalid start index: %s", err)
  1310  		}
  1311  		if start >= n {
  1312  			start = n - 1
  1313  		}
  1314  
  1315  		end = -1
  1316  		if err := asIndex(hi, n, &end); err != nil {
  1317  			return nil, fmt.Errorf("invalid end index: %s", err)
  1318  		}
  1319  		if end < -1 {
  1320  			end = -1
  1321  		}
  1322  
  1323  		if start < end {
  1324  			start = end // => empty result
  1325  		}
  1326  	}
  1327  
  1328  	return sliceable.Slice(start, end, step), nil
  1329  }
  1330  
  1331  // From Hacker's Delight, section 2.8.
  1332  func signum64(x int64) int { return int(uint64(x>>63) | uint64(-x)>>63) }
  1333  func signum(x int) int     { return signum64(int64(x)) }
  1334  
  1335  // indices converts start_ and end_ to indices in the range [0:len].
  1336  // The start index defaults to 0 and the end index defaults to len.
  1337  // An index -len < i < 0 is treated like i+len.
  1338  // All other indices outside the range are clamped to the nearest value in the range.
  1339  // Beware: start may be greater than end.
  1340  // This function is suitable only for slices with positive strides.
  1341  func indices(start_, end_ Value, len int) (start, end int, err error) {
  1342  	start = 0
  1343  	if err := asIndex(start_, len, &start); err != nil {
  1344  		return 0, 0, fmt.Errorf("invalid start index: %s", err)
  1345  	}
  1346  	// Clamp to [0:len].
  1347  	if start < 0 {
  1348  		start = 0
  1349  	} else if start > len {
  1350  		start = len
  1351  	}
  1352  
  1353  	end = len
  1354  	if err := asIndex(end_, len, &end); err != nil {
  1355  		return 0, 0, fmt.Errorf("invalid end index: %s", err)
  1356  	}
  1357  	// Clamp to [0:len].
  1358  	if end < 0 {
  1359  		end = 0
  1360  	} else if end > len {
  1361  		end = len
  1362  	}
  1363  
  1364  	return start, end, nil
  1365  }
  1366  
  1367  // asIndex sets *result to the integer value of v, adding len to it
  1368  // if it is negative.  If v is nil or None, *result is unchanged.
  1369  func asIndex(v Value, len int, result *int) error {
  1370  	if v != nil && v != None {
  1371  		var err error
  1372  		*result, err = AsInt32(v)
  1373  		if err != nil {
  1374  			return err
  1375  		}
  1376  		if *result < 0 {
  1377  			*result += len
  1378  		}
  1379  	}
  1380  	return nil
  1381  }
  1382  
  1383  // setArgs sets the values of the formal parameters of function fn in
  1384  // based on the actual parameter values in args and kwargs.
  1385  func setArgs(locals []Value, fn *Function, args Tuple, kwargs []Tuple) error {
  1386  
  1387  	// This is the general schema of a function:
  1388  	//
  1389  	//   def f(p1, p2=dp2, p3=dp3, *args, k1, k2=dk2, k3, **kwargs)
  1390  	//
  1391  	// The p parameters are non-kwonly, and may be specified positionally.
  1392  	// The k parameters are kwonly, and must be specified by name.
  1393  	// The defaults tuple is (dp2, dp3, mandatory, dk2, mandatory).
  1394  	//
  1395  	// Arguments are processed as follows:
  1396  	// - positional arguments are bound to a prefix of [p1, p2, p3].
  1397  	// - surplus positional arguments are bound to *args.
  1398  	// - keyword arguments are bound to any of {p1, p2, p3, k1, k2, k3};
  1399  	//   duplicate bindings are rejected.
  1400  	// - surplus keyword arguments are bound to **kwargs.
  1401  	// - defaults are bound to each parameter from p2 to k3 if no value was set.
  1402  	//   default values come from the tuple above.
  1403  	//   It is an error if the tuple entry for an unset parameter is 'mandatory'.
  1404  
  1405  	// Nullary function?
  1406  	if fn.NumParams() == 0 {
  1407  		if nactual := len(args) + len(kwargs); nactual > 0 {
  1408  			return fmt.Errorf("function %s accepts no arguments (%d given)", fn.Name(), nactual)
  1409  		}
  1410  		return nil
  1411  	}
  1412  
  1413  	cond := func(x bool, y, z interface{}) interface{} {
  1414  		if x {
  1415  			return y
  1416  		}
  1417  		return z
  1418  	}
  1419  
  1420  	// nparams is the number of ordinary parameters (sans *args and **kwargs).
  1421  	nparams := fn.NumParams()
  1422  	var kwdict *Dict
  1423  	if fn.HasKwargs() {
  1424  		nparams--
  1425  		kwdict = new(Dict)
  1426  		locals[nparams] = kwdict
  1427  	}
  1428  	if fn.HasVarargs() {
  1429  		nparams--
  1430  	}
  1431  
  1432  	// nonkwonly is the number of non-kwonly parameters.
  1433  	nonkwonly := nparams - fn.NumKwonlyParams()
  1434  
  1435  	// Too many positional args?
  1436  	n := len(args)
  1437  	if len(args) > nonkwonly {
  1438  		if !fn.HasVarargs() {
  1439  			return fmt.Errorf("function %s accepts %s%d positional argument%s (%d given)",
  1440  				fn.Name(),
  1441  				cond(len(fn.defaults) > fn.NumKwonlyParams(), "at most ", ""),
  1442  				nonkwonly,
  1443  				cond(nonkwonly == 1, "", "s"),
  1444  				len(args))
  1445  		}
  1446  		n = nonkwonly
  1447  	}
  1448  
  1449  	// Bind positional arguments to non-kwonly parameters.
  1450  	for i := 0; i < n; i++ {
  1451  		locals[i] = args[i]
  1452  	}
  1453  
  1454  	// Bind surplus positional arguments to *args parameter.
  1455  	if fn.HasVarargs() {
  1456  		tuple := make(Tuple, len(args)-n)
  1457  		for i := n; i < len(args); i++ {
  1458  			tuple[i-n] = args[i]
  1459  		}
  1460  		locals[nparams] = tuple
  1461  	}
  1462  
  1463  	// Bind keyword arguments to parameters.
  1464  	paramIdents := fn.funcode.Locals[:nparams]
  1465  	for _, pair := range kwargs {
  1466  		k, v := pair[0].(String), pair[1]
  1467  		if i := findParam(paramIdents, string(k)); i >= 0 {
  1468  			if locals[i] != nil {
  1469  				return fmt.Errorf("function %s got multiple values for parameter %s", fn.Name(), k)
  1470  			}
  1471  			locals[i] = v
  1472  			continue
  1473  		}
  1474  		if kwdict == nil {
  1475  			return fmt.Errorf("function %s got an unexpected keyword argument %s", fn.Name(), k)
  1476  		}
  1477  		oldlen := kwdict.Len()
  1478  		kwdict.SetKey(k, v)
  1479  		if kwdict.Len() == oldlen {
  1480  			return fmt.Errorf("function %s got multiple values for parameter %s", fn.Name(), k)
  1481  		}
  1482  	}
  1483  
  1484  	// Are defaults required?
  1485  	if n < nparams || fn.NumKwonlyParams() > 0 {
  1486  		m := nparams - len(fn.defaults) // first default
  1487  
  1488  		// Report errors for missing required arguments.
  1489  		var missing []string
  1490  		var i int
  1491  		for i = n; i < m; i++ {
  1492  			if locals[i] == nil {
  1493  				missing = append(missing, paramIdents[i].Name)
  1494  			}
  1495  		}
  1496  
  1497  		// Bind default values to parameters.
  1498  		for ; i < nparams; i++ {
  1499  			if locals[i] == nil {
  1500  				dflt := fn.defaults[i-m]
  1501  				if _, ok := dflt.(mandatory); ok {
  1502  					missing = append(missing, paramIdents[i].Name)
  1503  					continue
  1504  				}
  1505  				locals[i] = dflt
  1506  			}
  1507  		}
  1508  
  1509  		if missing != nil {
  1510  			return fmt.Errorf("function %s missing %d argument%s (%s)",
  1511  				fn.Name(), len(missing), cond(len(missing) > 1, "s", ""), strings.Join(missing, ", "))
  1512  		}
  1513  	}
  1514  	return nil
  1515  }
  1516  
  1517  func findParam(params []compile.Binding, name string) int {
  1518  	for i, param := range params {
  1519  		if param.Name == name {
  1520  			return i
  1521  		}
  1522  	}
  1523  	return -1
  1524  }
  1525  
  1526  // https://github.com/google/starlark-go/blob/master/doc/spec.md#string-interpolation
  1527  func interpolate(format string, x Value) (Value, error) {
  1528  	buf := new(strings.Builder)
  1529  	index := 0
  1530  	nargs := 1
  1531  	if tuple, ok := x.(Tuple); ok {
  1532  		nargs = len(tuple)
  1533  	}
  1534  	for {
  1535  		i := strings.IndexByte(format, '%')
  1536  		if i < 0 {
  1537  			buf.WriteString(format)
  1538  			break
  1539  		}
  1540  		buf.WriteString(format[:i])
  1541  		format = format[i+1:]
  1542  
  1543  		if format != "" && format[0] == '%' {
  1544  			buf.WriteByte('%')
  1545  			format = format[1:]
  1546  			continue
  1547  		}
  1548  
  1549  		var arg Value
  1550  		if format != "" && format[0] == '(' {
  1551  			// keyword argument: %(name)s.
  1552  			format = format[1:]
  1553  			j := strings.IndexByte(format, ')')
  1554  			if j < 0 {
  1555  				return nil, fmt.Errorf("incomplete format key")
  1556  			}
  1557  			key := format[:j]
  1558  			if dict, ok := x.(Mapping); !ok {
  1559  				return nil, fmt.Errorf("format requires a mapping")
  1560  			} else if v, found, _ := dict.Get(String(key)); found {
  1561  				arg = v
  1562  			} else {
  1563  				return nil, fmt.Errorf("key not found: %s", key)
  1564  			}
  1565  			format = format[j+1:]
  1566  		} else {
  1567  			// positional argument: %s.
  1568  			if index >= nargs {
  1569  				return nil, fmt.Errorf("not enough arguments for format string")
  1570  			}
  1571  			if tuple, ok := x.(Tuple); ok {
  1572  				arg = tuple[index]
  1573  			} else {
  1574  				arg = x
  1575  			}
  1576  		}
  1577  
  1578  		// NOTE: Starlark does not support any of these optional Python features:
  1579  		// - optional conversion flags: [#0- +], etc.
  1580  		// - optional minimum field width (number or *).
  1581  		// - optional precision (.123 or *)
  1582  		// - optional length modifier
  1583  
  1584  		// conversion type
  1585  		if format == "" {
  1586  			return nil, fmt.Errorf("incomplete format")
  1587  		}
  1588  		switch c := format[0]; c {
  1589  		case 's', 'r':
  1590  			if str, ok := AsString(arg); ok && c == 's' {
  1591  				buf.WriteString(str)
  1592  			} else {
  1593  				writeValue(buf, arg, nil)
  1594  			}
  1595  		case 'd', 'i', 'o', 'x', 'X':
  1596  			i, err := NumberToInt(arg)
  1597  			if err != nil {
  1598  				return nil, fmt.Errorf("%%%c format requires integer: %v", c, err)
  1599  			}
  1600  			switch c {
  1601  			case 'd', 'i':
  1602  				fmt.Fprintf(buf, "%d", i)
  1603  			case 'o':
  1604  				fmt.Fprintf(buf, "%o", i)
  1605  			case 'x':
  1606  				fmt.Fprintf(buf, "%x", i)
  1607  			case 'X':
  1608  				fmt.Fprintf(buf, "%X", i)
  1609  			}
  1610  		case 'e', 'f', 'g', 'E', 'F', 'G':
  1611  			f, ok := AsFloat(arg)
  1612  			if !ok {
  1613  				return nil, fmt.Errorf("%%%c format requires float, not %s", c, arg.Type())
  1614  			}
  1615  			Float(f).format(buf, c)
  1616  		case 'c':
  1617  			switch arg := arg.(type) {
  1618  			case Int:
  1619  				// chr(int)
  1620  				r, err := AsInt32(arg)
  1621  				if err != nil || r < 0 || r > unicode.MaxRune {
  1622  					return nil, fmt.Errorf("%%c format requires a valid Unicode code point, got %s", arg)
  1623  				}
  1624  				buf.WriteRune(rune(r))
  1625  			case String:
  1626  				r, size := utf8.DecodeRuneInString(string(arg))
  1627  				if size != len(arg) || len(arg) == 0 {
  1628  					return nil, fmt.Errorf("%%c format requires a single-character string")
  1629  				}
  1630  				buf.WriteRune(r)
  1631  			default:
  1632  				return nil, fmt.Errorf("%%c format requires int or single-character string, not %s", arg.Type())
  1633  			}
  1634  		case '%':
  1635  			buf.WriteByte('%')
  1636  		default:
  1637  			return nil, fmt.Errorf("unknown conversion %%%c", c)
  1638  		}
  1639  		format = format[1:]
  1640  		index++
  1641  	}
  1642  
  1643  	if index < nargs {
  1644  		return nil, fmt.Errorf("too many arguments for format string")
  1645  	}
  1646  
  1647  	return String(buf.String()), nil
  1648  }
  1649  

View as plain text