starlark/interp.go - platform/external/starlark-go - Git at Google

 package starlark

 // This file defines the bytecode interpreter.

 import (
 	"fmt"
 	"os"
 	"sync/atomic"
 	"unsafe"

 	"go.starlark.net/internal/compile"
 	"go.starlark.net/internal/spell"
 	"go.starlark.net/resolve"
 	"go.starlark.net/syntax"
 )

 const vmdebug = false // TODO(adonovan): use a bitfield of specific kinds of error.

 // TODO(adonovan):
 // - optimize position table.
 // - opt: record MaxIterStack during compilation and preallocate the stack.

 func (fn *Function) CallInternal(thread *Thread, args Tuple, kwargs []Tuple) (Value, error) {
 	// Postcondition: args is not mutated. This is stricter than required by Callable,
 	// but allows CALL to avoid a copy.

 	if !resolve.AllowRecursion {
 		// detect recursion
 		for _, fr := range thread.stack[:len(thread.stack)-1] {
 			// We look for the same function code,
 			// not function value, otherwise the user could
 			// defeat the check by writing the Y combinator.
 			if frfn, ok := fr.Callable().(*Function); ok && frfn.funcode == fn.funcode {
 				return nil, fmt.Errorf("function %s called recursively", fn.Name())
 			}
 		}
 	}

 	f := fn.funcode
 	fr := thread.frameAt(0)

 	// Allocate space for stack and locals.
 	// Logically these do not escape from this frame
 	// (See https://github.com/golang/go/issues/20533.)
 	//
 	// This heap allocation looks expensive, but I was unable to get
 	// more than 1% real time improvement in a large alloc-heavy
 	// benchmark (in which this alloc was 8% of alloc-bytes)
 	// by allocating space for 8 Values in each frame, or
 	// by allocating stack by slicing an array held by the Thread
 	// that is expanded in chunks of min(k, nspace), for k=256 or 1024.
 	nlocals := len(f.Locals)
 	nspace := nlocals + f.MaxStack
 	space := make([]Value, nspace)
 	locals := space[:nlocals:nlocals] // local variables, starting with parameters
 	stack := space[nlocals:]          // operand stack

 	// Digest arguments and set parameters.
 	err := setArgs(locals, fn, args, kwargs)
 	if err != nil {
 		return nil, thread.evalError(err)
 	}

 	fr.locals = locals

 	if vmdebug {
 		fmt.Printf("Entering %s @ %s\n", f.Name, f.Position(0))
 		fmt.Printf("%d stack, %d locals\n", len(stack), len(locals))
 		defer fmt.Println("Leaving ", f.Name)
 	}

 	// Spill indicated locals to cells.
 	// Each cell is a separate alloc to avoid spurious liveness.
 	for _, index := range f.Cells {
 		locals[index] = &cell{locals[index]}
 	}

 	// TODO(adonovan): add static check that beneath this point
 	// - there is exactly one return statement
 	// - there is no redefinition of 'err'.

 	var iterstack []Iterator // stack of active iterators

 	sp := 0
 	var pc uint32
 	var result Value
 	code := f.Code
 loop:
 	for {
 		thread.steps++
 		if thread.steps >= thread.maxSteps {
 			thread.Cancel("too many steps")
 		}
 		if reason := atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&thread.cancelReason))); reason != nil {
 			err = fmt.Errorf("Starlark computation cancelled: %s", *(*string)(reason))
 			break loop
 		}

 		fr.pc = pc

 		op := compile.Opcode(code[pc])
 		pc++
 		var arg uint32
 		if op >= compile.OpcodeArgMin {
 			// TODO(adonovan): opt: profile this.
 			// Perhaps compiling big endian would be less work to decode?
 			for s := uint(0); ; s += 7 {
 				b := code[pc]
 				pc++
 				arg |= uint32(b&0x7f) << s
 				if b < 0x80 {
 					break
 				}
 			}
 		}
 		if vmdebug {
 			fmt.Fprintln(os.Stderr, stack[:sp]) // very verbose!
 			compile.PrintOp(f, fr.pc, op, arg)
 		}

 		switch op {
 		case compile.NOP:
 			// nop

 		case compile.DUP:
 			stack[sp] = stack[sp-1]
 			sp++

 		case compile.DUP2:
 			stack[sp] = stack[sp-2]
 			stack[sp+1] = stack[sp-1]
 			sp += 2

 		case compile.POP:
 			sp--

 		case compile.EXCH:
 			stack[sp-2], stack[sp-1] = stack[sp-1], stack[sp-2]

 		case compile.EQL, compile.NEQ, compile.GT, compile.LT, compile.LE, compile.GE:
 			op := syntax.Token(op-compile.EQL) + syntax.EQL
 			y := stack[sp-1]
 			x := stack[sp-2]
 			sp -= 2
 			ok, err2 := Compare(op, x, y)
 			if err2 != nil {
 				err = err2
 				break loop
 			}
 			stack[sp] = Bool(ok)
 			sp++

 		case compile.PLUS,
 			compile.MINUS,
 			compile.STAR,
 			compile.SLASH,
 			compile.SLASHSLASH,
 			compile.PERCENT,
 			compile.AMP,
 			compile.PIPE,
 			compile.CIRCUMFLEX,
 			compile.LTLT,
 			compile.GTGT,
 			compile.IN:
 			binop := syntax.Token(op-compile.PLUS) + syntax.PLUS
 			if op == compile.IN {
 				binop = syntax.IN // IN token is out of order
 			}
 			y := stack[sp-1]
 			x := stack[sp-2]
 			sp -= 2
 			z, err2 := Binary(binop, x, y)
 			if err2 != nil {
 				err = err2
 				break loop
 			}
 			stack[sp] = z
 			sp++

 		case compile.UPLUS, compile.UMINUS, compile.TILDE:
 			var unop syntax.Token
 			if op == compile.TILDE {
 				unop = syntax.TILDE
 			} else {
 				unop = syntax.Token(op-compile.UPLUS) + syntax.PLUS
 			}
 			x := stack[sp-1]
 			y, err2 := Unary(unop, x)
 			if err2 != nil {
 				err = err2
 				break loop
 			}
 			stack[sp-1] = y

 		case compile.INPLACE_ADD:
 			y := stack[sp-1]
 			x := stack[sp-2]
 			sp -= 2

 			// It's possible that y is not Iterable but
 			// nonetheless defines x+y, in which case we
 			// should fall back to the general case.
 			var z Value
 			if xlist, ok := x.(*List); ok {
 				if yiter, ok := y.(Iterable); ok {
 					if err = xlist.checkMutable("apply += to"); err != nil {
 						break loop
 					}
 					listExtend(xlist, yiter)
 					z = xlist
 				}
 			}
 			if z == nil {
 				z, err = Binary(syntax.PLUS, x, y)
 				if err != nil {
 					break loop
 				}
 			}

 			stack[sp] = z
 			sp++

 		case compile.NONE:
 			stack[sp] = None
 			sp++

 		case compile.TRUE:
 			stack[sp] = True
 			sp++

 		case compile.FALSE:
 			stack[sp] = False
 			sp++

 		case compile.MANDATORY:
 			stack[sp] = mandatory{}
 			sp++

 		case compile.JMP:
 			pc = arg

 		case compile.CALL, compile.CALL_VAR, compile.CALL_KW, compile.CALL_VAR_KW:
 			var kwargs Value
 			if op == compile.CALL_KW || op == compile.CALL_VAR_KW {
 				kwargs = stack[sp-1]
 				sp--
 			}

 			var args Value
 			if op == compile.CALL_VAR || op == compile.CALL_VAR_KW {
 				args = stack[sp-1]
 				sp--
 			}

 			// named args (pairs)
 			var kvpairs []Tuple
 			if nkvpairs := int(arg & 0xff); nkvpairs > 0 {
 				kvpairs = make([]Tuple, 0, nkvpairs)
 				kvpairsAlloc := make(Tuple, 2*nkvpairs) // allocate a single backing array
 				sp -= 2 * nkvpairs
 				for i := 0; i < nkvpairs; i++ {
 					pair := kvpairsAlloc[:2:2]
 					kvpairsAlloc = kvpairsAlloc[2:]
 					pair[0] = stack[sp+2*i]   // name
 					pair[1] = stack[sp+2*i+1] // value
 					kvpairs = append(kvpairs, pair)
 				}
 			}
 			if kwargs != nil {
 				// Add key/value items from **kwargs dictionary.
 				dict, ok := kwargs.(IterableMapping)
 				if !ok {
 					err = fmt.Errorf("argument after ** must be a mapping, not %s", kwargs.Type())
 					break loop
 				}
 				items := dict.Items()
 				for _, item := range items {
 					if _, ok := item[0].(String); !ok {
 						err = fmt.Errorf("keywords must be strings, not %s", item[0].Type())
 						break loop
 					}
 				}
 				if len(kvpairs) == 0 {
 					kvpairs = items
 				} else {
 					kvpairs = append(kvpairs, items...)
 				}
 			}

 			// positional args
 			var positional Tuple
 			if npos := int(arg >> 8); npos > 0 {
 				positional = stack[sp-npos : sp]
 				sp -= npos

 				// Copy positional arguments into a new array,
 				// unless the callee is another Starlark function,
 				// in which case it can be trusted not to mutate them.
 				if _, ok := stack[sp-1].(*Function); !ok || args != nil {
 					positional = append(Tuple(nil), positional...)
 				}
 			}
 			if args != nil {
 				// Add elements from *args sequence.
 				iter := Iterate(args)
 				if iter == nil {
 					err = fmt.Errorf("argument after * must be iterable, not %s", args.Type())
 					break loop
 				}
 				var elem Value
 				for iter.Next(&elem) {
 					positional = append(positional, elem)
 				}
 				iter.Done()
 			}

 			function := stack[sp-1]

 			if vmdebug {
 				fmt.Printf("VM call %s args=%s kwargs=%s @%s\n",
 					function, positional, kvpairs, f.Position(fr.pc))
 			}

 			thread.endProfSpan()
 			z, err2 := Call(thread, function, positional, kvpairs)
 			thread.beginProfSpan()
 			if err2 != nil {
 				err = err2
 				break loop
 			}
 			if vmdebug {
 				fmt.Printf("Resuming %s @ %s\n", f.Name, f.Position(0))
 			}
 			stack[sp-1] = z

 		case compile.ITERPUSH:
 			x := stack[sp-1]
 			sp--
 			iter := Iterate(x)
 			if iter == nil {
 				err = fmt.Errorf("%s value is not iterable", x.Type())
 				break loop
 			}
 			iterstack = append(iterstack, iter)

 		case compile.ITERJMP:
 			iter := iterstack[len(iterstack)-1]
 			if iter.Next(&stack[sp]) {
 				sp++
 			} else {
 				pc = arg
 			}

 		case compile.ITERPOP:
 			n := len(iterstack) - 1
 			iterstack[n].Done()
 			iterstack = iterstack[:n]

 		case compile.NOT:
 			stack[sp-1] = !stack[sp-1].Truth()

 		case compile.RETURN:
 			result = stack[sp-1]
 			break loop

 		case compile.SETINDEX:
 			z := stack[sp-1]
 			y := stack[sp-2]
 			x := stack[sp-3]
 			sp -= 3
 			err = setIndex(x, y, z)
 			if err != nil {
 				break loop
 			}

 		case compile.INDEX:
 			y := stack[sp-1]
 			x := stack[sp-2]
 			sp -= 2
 			z, err2 := getIndex(x, y)
 			if err2 != nil {
 				err = err2
 				break loop
 			}
 			stack[sp] = z
 			sp++

 		case compile.ATTR:
 			x := stack[sp-1]
 			name := f.Prog.Names[arg]
 			y, err2 := getAttr(x, name)
 			if err2 != nil {
 				err = err2
 				break loop
 			}
 			stack[sp-1] = y

 		case compile.SETFIELD:
 			y := stack[sp-1]
 			x := stack[sp-2]
 			sp -= 2
 			name := f.Prog.Names[arg]
 			if err2 := setField(x, name, y); err2 != nil {
 				err = err2
 				break loop
 			}

 		case compile.MAKEDICT:
 			stack[sp] = new(Dict)
 			sp++

 		case compile.SETDICT, compile.SETDICTUNIQ:
 			dict := stack[sp-3].(*Dict)
 			k := stack[sp-2]
 			v := stack[sp-1]
 			sp -= 3
 			oldlen := dict.Len()
 			if err2 := dict.SetKey(k, v); err2 != nil {
 				err = err2
 				break loop
 			}
 			if op == compile.SETDICTUNIQ && dict.Len() == oldlen {
 				err = fmt.Errorf("duplicate key: %v", k)
 				break loop
 			}

 		case compile.APPEND:
 			elem := stack[sp-1]
 			list := stack[sp-2].(*List)
 			sp -= 2
 			list.elems = append(list.elems, elem)

 		case compile.SLICE:
 			x := stack[sp-4]
 			lo := stack[sp-3]
 			hi := stack[sp-2]
 			step := stack[sp-1]
 			sp -= 4
 			res, err2 := slice(x, lo, hi, step)
 			if err2 != nil {
 				err = err2
 				break loop
 			}
 			stack[sp] = res
 			sp++

 		case compile.UNPACK:
 			n := int(arg)
 			iterable := stack[sp-1]
 			sp--
 			iter := Iterate(iterable)
 			if iter == nil {
 				err = fmt.Errorf("got %s in sequence assignment", iterable.Type())
 				break loop
 			}
 			i := 0
 			sp += n
 			for i < n && iter.Next(&stack[sp-1-i]) {
 				i++
 			}
 			var dummy Value
 			if iter.Next(&dummy) {
 				// NB: Len may return -1 here in obscure cases.
 				err = fmt.Errorf("too many values to unpack (got %d, want %d)", Len(iterable), n)
 				break loop
 			}
 			iter.Done()
 			if i < n {
 				err = fmt.Errorf("too few values to unpack (got %d, want %d)", i, n)
 				break loop
 			}

 		case compile.CJMP:
 			if stack[sp-1].Truth() {
 				pc = arg
 			}
 			sp--

 		case compile.CONSTANT:
 			stack[sp] = fn.module.constants[arg]
 			sp++

 		case compile.MAKETUPLE:
 			n := int(arg)
 			tuple := make(Tuple, n)
 			sp -= n
 			copy(tuple, stack[sp:])
 			stack[sp] = tuple
 			sp++

 		case compile.MAKELIST:
 			n := int(arg)
 			elems := make([]Value, n)
 			sp -= n
 			copy(elems, stack[sp:])
 			stack[sp] = NewList(elems)
 			sp++

 		case compile.MAKEFUNC:
 			funcode := f.Prog.Functions[arg]
 			tuple := stack[sp-1].(Tuple)
 			n := len(tuple) - len(funcode.Freevars)
 			defaults := tuple[:n:n]
 			freevars := tuple[n:]
 			stack[sp-1] = &Function{
 				funcode:  funcode,
 				module:   fn.module,
 				defaults: defaults,
 				freevars: freevars,
 			}

 		case compile.LOAD:
 			n := int(arg)
 			module := string(stack[sp-1].(String))
 			sp--

 			if thread.Load == nil {
 				err = fmt.Errorf("load not implemented by this application")
 				break loop
 			}

 			thread.endProfSpan()
 			dict, err2 := thread.Load(thread, module)
 			thread.beginProfSpan()
 			if err2 != nil {
 				err = wrappedError{
 					msg:   fmt.Sprintf("cannot load %s: %v", module, err2),
 					cause: err2,
 				}
 				break loop
 			}

 			for i := 0; i < n; i++ {
 				from := string(stack[sp-1-i].(String))
 				v, ok := dict[from]
 				if !ok {
 					err = fmt.Errorf("load: name %s not found in module %s", from, module)
 					if n := spell.Nearest(from, dict.Keys()); n != "" {
 						err = fmt.Errorf("%s (did you mean %s?)", err, n)
 					}
 					break loop
 				}
 				stack[sp-1-i] = v
 			}

 		case compile.SETLOCAL:
 			locals[arg] = stack[sp-1]
 			sp--

 		case compile.SETLOCALCELL:
 			locals[arg].(*cell).v = stack[sp-1]
 			sp--

 		case compile.SETGLOBAL:
 			fn.module.globals[arg] = stack[sp-1]
 			sp--

 		case compile.LOCAL:
 			x := locals[arg]
 			if x == nil {
 				err = fmt.Errorf("local variable %s referenced before assignment", f.Locals[arg].Name)
 				break loop
 			}
 			stack[sp] = x
 			sp++

 		case compile.FREE:
 			stack[sp] = fn.freevars[arg]
 			sp++

 		case compile.LOCALCELL:
 			v := locals[arg].(*cell).v
 			if v == nil {
 				err = fmt.Errorf("local variable %s referenced before assignment", f.Locals[arg].Name)
 				break loop
 			}
 			stack[sp] = v
 			sp++

 		case compile.FREECELL:
 			v := fn.freevars[arg].(*cell).v
 			if v == nil {
 				err = fmt.Errorf("local variable %s referenced before assignment", f.Freevars[arg].Name)
 				break loop
 			}
 			stack[sp] = v
 			sp++

 		case compile.GLOBAL:
 			x := fn.module.globals[arg]
 			if x == nil {
 				err = fmt.Errorf("global variable %s referenced before assignment", f.Prog.Globals[arg].Name)
 				break loop
 			}
 			stack[sp] = x
 			sp++

 		case compile.PREDECLARED:
 			name := f.Prog.Names[arg]
 			x := fn.module.predeclared[name]
 			if x == nil {
 				err = fmt.Errorf("internal error: predeclared variable %s is uninitialized", name)
 				break loop
 			}
 			stack[sp] = x
 			sp++

 		case compile.UNIVERSAL:
 			stack[sp] = Universe[f.Prog.Names[arg]]
 			sp++

 		default:
 			err = fmt.Errorf("unimplemented: %s", op)
 			break loop
 		}
 	}

 	// ITERPOP the rest of the iterator stack.
 	for _, iter := range iterstack {
 		iter.Done()
 	}

 	fr.locals = nil

 	return result, err
 }

 type wrappedError struct {
 	msg   string
 	cause error
 }

 func (e wrappedError) Error() string {
 	return e.msg
 }

 // Implements the xerrors.Wrapper interface
 // https://godoc.org/golang.org/x/xerrors#Wrapper
 func (e wrappedError) Unwrap() error {
 	return e.cause
 }

 // mandatory is a sentinel value used in a function's defaults tuple
 // to indicate that a (keyword-only) parameter is mandatory.
 type mandatory struct{}

 func (mandatory) String() string        { return "mandatory" }
 func (mandatory) Type() string          { return "mandatory" }
 func (mandatory) Freeze()               {} // immutable
 func (mandatory) Truth() Bool           { return False }
 func (mandatory) Hash() (uint32, error) { return 0, nil }

 // A cell is a box containing a Value.
 // Local variables marked as cells hold their value indirectly
 // so that they may be shared by outer and inner nested functions.
 // Cells are always accessed using indirect {FREE,LOCAL,SETLOCAL}CELL instructions.
 // The FreeVars tuple contains only cells.
 // The FREE instruction always yields a cell.
 type cell struct{ v Value }

 func (c *cell) String() string { return "cell" }
 func (c *cell) Type() string   { return "cell" }
 func (c *cell) Freeze() {
 	if c.v != nil {
 		c.v.Freeze()
 	}
 }
 func (c *cell) Truth() Bool           { panic("unreachable") }
 func (c *cell) Hash() (uint32, error) { panic("unreachable") }
	package starlark

	// This file defines the bytecode interpreter.

	import (
	"fmt"
	"os"
	"sync/atomic"
	"unsafe"

	"go.starlark.net/internal/compile"
	"go.starlark.net/internal/spell"
	"go.starlark.net/resolve"
	"go.starlark.net/syntax"
	)

	const vmdebug = false // TODO(adonovan): use a bitfield of specific kinds of error.

	// TODO(adonovan):
	// - optimize position table.
	// - opt: record MaxIterStack during compilation and preallocate the stack.

	func (fn Function) CallInternal(thread Thread, args Tuple, kwargs []Tuple) (Value, error) {
	// Postcondition: args is not mutated. This is stricter than required by Callable,
	// but allows CALL to avoid a copy.

	if !resolve.AllowRecursion {
	// detect recursion
	for _, fr := range thread.stack[:len(thread.stack)-1] {
	// We look for the same function code,
	// not function value, otherwise the user could
	// defeat the check by writing the Y combinator.
	if frfn, ok := fr.Callable().(*Function); ok && frfn.funcode == fn.funcode {
	return nil, fmt.Errorf("function %s called recursively", fn.Name())
	}
	}
	}

	f := fn.funcode
	fr := thread.frameAt(0)

	// Allocate space for stack and locals.
	// Logically these do not escape from this frame
	// (See https://github.com/golang/go/issues/20533.)
	//
	// This heap allocation looks expensive, but I was unable to get
	// more than 1% real time improvement in a large alloc-heavy
	// benchmark (in which this alloc was 8% of alloc-bytes)
	// by allocating space for 8 Values in each frame, or
	// by allocating stack by slicing an array held by the Thread
	// that is expanded in chunks of min(k, nspace), for k=256 or 1024.
	nlocals := len(f.Locals)
	nspace := nlocals + f.MaxStack
	space := make([]Value, nspace)
	locals := space[:nlocals:nlocals] // local variables, starting with parameters
	stack := space[nlocals:] // operand stack

	// Digest arguments and set parameters.
	err := setArgs(locals, fn, args, kwargs)
	if err != nil {
	return nil, thread.evalError(err)
	}

	fr.locals = locals

	if vmdebug {
	fmt.Printf("Entering %s @ %s\n", f.Name, f.Position(0))
	fmt.Printf("%d stack, %d locals\n", len(stack), len(locals))
	defer fmt.Println("Leaving ", f.Name)
	}

	// Spill indicated locals to cells.
	// Each cell is a separate alloc to avoid spurious liveness.
	for _, index := range f.Cells {
	locals[index] = &cell{locals[index]}
	}

	// TODO(adonovan): add static check that beneath this point
	// - there is exactly one return statement
	// - there is no redefinition of 'err'.

	var iterstack []Iterator // stack of active iterators

	sp := 0
	var pc uint32
	var result Value
	code := f.Code
	loop:
	for {
	thread.steps++
	if thread.steps >= thread.maxSteps {
	thread.Cancel("too many steps")
	}
	if reason := atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&thread.cancelReason))); reason != nil {
	err = fmt.Errorf("Starlark computation cancelled: %s", (string)(reason))
	break loop
	}

	fr.pc = pc

	op := compile.Opcode(code[pc])
	pc++
	var arg uint32
	if op >= compile.OpcodeArgMin {
	// TODO(adonovan): opt: profile this.
	// Perhaps compiling big endian would be less work to decode?
	for s := uint(0); ; s += 7 {
	b := code[pc]
	pc++
	arg \|= uint32(b&0x7f) << s
	if b < 0x80 {
	break
	}
	}
	}
	if vmdebug {
	fmt.Fprintln(os.Stderr, stack[:sp]) // very verbose!
	compile.PrintOp(f, fr.pc, op, arg)
	}

	switch op {
	case compile.NOP:
	// nop

	case compile.DUP:
	stack[sp] = stack[sp-1]
	sp++

	case compile.DUP2:
	stack[sp] = stack[sp-2]
	stack[sp+1] = stack[sp-1]
	sp += 2

	case compile.POP:
	sp--

	case compile.EXCH:
	stack[sp-2], stack[sp-1] = stack[sp-1], stack[sp-2]

	case compile.EQL, compile.NEQ, compile.GT, compile.LT, compile.LE, compile.GE:
	op := syntax.Token(op-compile.EQL) + syntax.EQL
	y := stack[sp-1]
	x := stack[sp-2]
	sp -= 2
	ok, err2 := Compare(op, x, y)
	if err2 != nil {
	err = err2
	break loop
	}
	stack[sp] = Bool(ok)
	sp++

	case compile.PLUS,
	compile.MINUS,
	compile.STAR,
	compile.SLASH,
	compile.SLASHSLASH,
	compile.PERCENT,
	compile.AMP,
	compile.PIPE,
	compile.CIRCUMFLEX,
	compile.LTLT,
	compile.GTGT,
	compile.IN:
	binop := syntax.Token(op-compile.PLUS) + syntax.PLUS
	if op == compile.IN {
	binop = syntax.IN // IN token is out of order
	}
	y := stack[sp-1]
	x := stack[sp-2]
	sp -= 2
	z, err2 := Binary(binop, x, y)
	if err2 != nil {
	err = err2
	break loop
	}
	stack[sp] = z
	sp++

	case compile.UPLUS, compile.UMINUS, compile.TILDE:
	var unop syntax.Token
	if op == compile.TILDE {
	unop = syntax.TILDE
	} else {
	unop = syntax.Token(op-compile.UPLUS) + syntax.PLUS
	}
	x := stack[sp-1]
	y, err2 := Unary(unop, x)
	if err2 != nil {
	err = err2
	break loop
	}
	stack[sp-1] = y

	case compile.INPLACE_ADD:
	y := stack[sp-1]
	x := stack[sp-2]
	sp -= 2

	// It's possible that y is not Iterable but
	// nonetheless defines x+y, in which case we
	// should fall back to the general case.
	var z Value
	if xlist, ok := x.(*List); ok {
	if yiter, ok := y.(Iterable); ok {
	if err = xlist.checkMutable("apply += to"); err != nil {
	break loop
	}
	listExtend(xlist, yiter)
	z = xlist
	}
	}
	if z == nil {
	z, err = Binary(syntax.PLUS, x, y)
	if err != nil {
	break loop
	}
	}

	stack[sp] = z
	sp++

	case compile.NONE:
	stack[sp] = None
	sp++

	case compile.TRUE:
	stack[sp] = True
	sp++

	case compile.FALSE:
	stack[sp] = False
	sp++

	case compile.MANDATORY:
	stack[sp] = mandatory{}
	sp++

	case compile.JMP:
	pc = arg

	case compile.CALL, compile.CALL_VAR, compile.CALL_KW, compile.CALL_VAR_KW:
	var kwargs Value
	if op == compile.CALL_KW \|\| op == compile.CALL_VAR_KW {
	kwargs = stack[sp-1]
	sp--
	}

	var args Value
	if op == compile.CALL_VAR \|\| op == compile.CALL_VAR_KW {
	args = stack[sp-1]
	sp--
	}

	// named args (pairs)
	var kvpairs []Tuple
	if nkvpairs := int(arg & 0xff); nkvpairs > 0 {
	kvpairs = make([]Tuple, 0, nkvpairs)
	kvpairsAlloc := make(Tuple, 2*nkvpairs) // allocate a single backing array
	sp -= 2 * nkvpairs
	for i := 0; i < nkvpairs; i++ {
	pair := kvpairsAlloc[:2:2]
	kvpairsAlloc = kvpairsAlloc[2:]
	pair[0] = stack[sp+2*i] // name
	pair[1] = stack[sp+2*i+1] // value
	kvpairs = append(kvpairs, pair)
	}
	}
	if kwargs != nil {
	// Add key/value items from **kwargs dictionary.
	dict, ok := kwargs.(IterableMapping)
	if !ok {
	err = fmt.Errorf("argument after ** must be a mapping, not %s", kwargs.Type())
	break loop
	}
	items := dict.Items()
	for _, item := range items {
	if _, ok := item[0].(String); !ok {
	err = fmt.Errorf("keywords must be strings, not %s", item[0].Type())
	break loop
	}
	}
	if len(kvpairs) == 0 {
	kvpairs = items
	} else {
	kvpairs = append(kvpairs, items...)
	}
	}

	// positional args
	var positional Tuple
	if npos := int(arg >> 8); npos > 0 {
	positional = stack[sp-npos : sp]
	sp -= npos

	// Copy positional arguments into a new array,
	// unless the callee is another Starlark function,
	// in which case it can be trusted not to mutate them.
	if _, ok := stack[sp-1].(*Function); !ok \|\| args != nil {
	positional = append(Tuple(nil), positional...)
	}
	}
	if args != nil {
	// Add elements from *args sequence.
	iter := Iterate(args)
	if iter == nil {
	err = fmt.Errorf("argument after * must be iterable, not %s", args.Type())
	break loop
	}
	var elem Value
	for iter.Next(&elem) {
	positional = append(positional, elem)
	}
	iter.Done()
	}

	function := stack[sp-1]

	if vmdebug {
	fmt.Printf("VM call %s args=%s kwargs=%s @%s\n",
	function, positional, kvpairs, f.Position(fr.pc))
	}

	thread.endProfSpan()
	z, err2 := Call(thread, function, positional, kvpairs)
	thread.beginProfSpan()
	if err2 != nil {
	err = err2
	break loop
	}
	if vmdebug {
	fmt.Printf("Resuming %s @ %s\n", f.Name, f.Position(0))
	}
	stack[sp-1] = z

	case compile.ITERPUSH:
	x := stack[sp-1]
	sp--
	iter := Iterate(x)
	if iter == nil {
	err = fmt.Errorf("%s value is not iterable", x.Type())
	break loop
	}
	iterstack = append(iterstack, iter)

	case compile.ITERJMP:
	iter := iterstack[len(iterstack)-1]
	if iter.Next(&stack[sp]) {
	sp++
	} else {
	pc = arg
	}

	case compile.ITERPOP:
	n := len(iterstack) - 1
	iterstack[n].Done()
	iterstack = iterstack[:n]

	case compile.NOT:
	stack[sp-1] = !stack[sp-1].Truth()

	case compile.RETURN:
	result = stack[sp-1]
	break loop

	case compile.SETINDEX:
	z := stack[sp-1]
	y := stack[sp-2]
	x := stack[sp-3]
	sp -= 3
	err = setIndex(x, y, z)
	if err != nil {
	break loop
	}

	case compile.INDEX:
	y := stack[sp-1]
	x := stack[sp-2]
	sp -= 2
	z, err2 := getIndex(x, y)
	if err2 != nil {
	err = err2
	break loop
	}
	stack[sp] = z
	sp++

	case compile.ATTR:
	x := stack[sp-1]
	name := f.Prog.Names[arg]
	y, err2 := getAttr(x, name)
	if err2 != nil {
	err = err2
	break loop
	}
	stack[sp-1] = y

	case compile.SETFIELD:
	y := stack[sp-1]
	x := stack[sp-2]
	sp -= 2
	name := f.Prog.Names[arg]
	if err2 := setField(x, name, y); err2 != nil {
	err = err2
	break loop
	}

	case compile.MAKEDICT:
	stack[sp] = new(Dict)
	sp++

	case compile.SETDICT, compile.SETDICTUNIQ:
	dict := stack[sp-3].(*Dict)
	k := stack[sp-2]
	v := stack[sp-1]
	sp -= 3
	oldlen := dict.Len()
	if err2 := dict.SetKey(k, v); err2 != nil {
	err = err2
	break loop
	}
	if op == compile.SETDICTUNIQ && dict.Len() == oldlen {
	err = fmt.Errorf("duplicate key: %v", k)
	break loop
	}

	case compile.APPEND:
	elem := stack[sp-1]
	list := stack[sp-2].(*List)
	sp -= 2
	list.elems = append(list.elems, elem)

	case compile.SLICE:
	x := stack[sp-4]
	lo := stack[sp-3]
	hi := stack[sp-2]
	step := stack[sp-1]
	sp -= 4
	res, err2 := slice(x, lo, hi, step)
	if err2 != nil {
	err = err2
	break loop
	}
	stack[sp] = res
	sp++

	case compile.UNPACK:
	n := int(arg)
	iterable := stack[sp-1]
	sp--
	iter := Iterate(iterable)
	if iter == nil {
	err = fmt.Errorf("got %s in sequence assignment", iterable.Type())
	break loop
	}
	i := 0
	sp += n
	for i < n && iter.Next(&stack[sp-1-i]) {
	i++
	}
	var dummy Value
	if iter.Next(&dummy) {
	// NB: Len may return -1 here in obscure cases.
	err = fmt.Errorf("too many values to unpack (got %d, want %d)", Len(iterable), n)
	break loop
	}
	iter.Done()
	if i < n {
	err = fmt.Errorf("too few values to unpack (got %d, want %d)", i, n)
	break loop
	}

	case compile.CJMP:
	if stack[sp-1].Truth() {
	pc = arg
	}
	sp--

	case compile.CONSTANT:
	stack[sp] = fn.module.constants[arg]
	sp++

	case compile.MAKETUPLE:
	n := int(arg)
	tuple := make(Tuple, n)
	sp -= n
	copy(tuple, stack[sp:])
	stack[sp] = tuple
	sp++

	case compile.MAKELIST:
	n := int(arg)
	elems := make([]Value, n)
	sp -= n
	copy(elems, stack[sp:])
	stack[sp] = NewList(elems)
	sp++

	case compile.MAKEFUNC:
	funcode := f.Prog.Functions[arg]
	tuple := stack[sp-1].(Tuple)
	n := len(tuple) - len(funcode.Freevars)
	defaults := tuple[:n:n]
	freevars := tuple[n:]
	stack[sp-1] = &Function{
	funcode: funcode,
	module: fn.module,
	defaults: defaults,
	freevars: freevars,
	}

	case compile.LOAD:
	n := int(arg)
	module := string(stack[sp-1].(String))
	sp--

	if thread.Load == nil {
	err = fmt.Errorf("load not implemented by this application")
	break loop
	}

	thread.endProfSpan()
	dict, err2 := thread.Load(thread, module)
	thread.beginProfSpan()
	if err2 != nil {
	err = wrappedError{
	msg: fmt.Sprintf("cannot load %s: %v", module, err2),
	cause: err2,
	}
	break loop
	}

	for i := 0; i < n; i++ {
	from := string(stack[sp-1-i].(String))
	v, ok := dict[from]
	if !ok {
	err = fmt.Errorf("load: name %s not found in module %s", from, module)
	if n := spell.Nearest(from, dict.Keys()); n != "" {
	err = fmt.Errorf("%s (did you mean %s?)", err, n)
	}
	break loop
	}
	stack[sp-1-i] = v
	}

	case compile.SETLOCAL:
	locals[arg] = stack[sp-1]
	sp--

	case compile.SETLOCALCELL:
	locals[arg].(*cell).v = stack[sp-1]
	sp--

	case compile.SETGLOBAL:
	fn.module.globals[arg] = stack[sp-1]
	sp--

	case compile.LOCAL:
	x := locals[arg]
	if x == nil {
	err = fmt.Errorf("local variable %s referenced before assignment", f.Locals[arg].Name)
	break loop
	}
	stack[sp] = x
	sp++

	case compile.FREE:
	stack[sp] = fn.freevars[arg]
	sp++

	case compile.LOCALCELL:
	v := locals[arg].(*cell).v
	if v == nil {
	err = fmt.Errorf("local variable %s referenced before assignment", f.Locals[arg].Name)
	break loop
	}
	stack[sp] = v
	sp++

	case compile.FREECELL:
	v := fn.freevars[arg].(*cell).v
	if v == nil {
	err = fmt.Errorf("local variable %s referenced before assignment", f.Freevars[arg].Name)
	break loop
	}
	stack[sp] = v
	sp++

	case compile.GLOBAL:
	x := fn.module.globals[arg]
	if x == nil {
	err = fmt.Errorf("global variable %s referenced before assignment", f.Prog.Globals[arg].Name)
	break loop
	}
	stack[sp] = x
	sp++

	case compile.PREDECLARED:
	name := f.Prog.Names[arg]
	x := fn.module.predeclared[name]
	if x == nil {
	err = fmt.Errorf("internal error: predeclared variable %s is uninitialized", name)
	break loop
	}
	stack[sp] = x
	sp++

	case compile.UNIVERSAL:
	stack[sp] = Universe[f.Prog.Names[arg]]
	sp++

	default:
	err = fmt.Errorf("unimplemented: %s", op)
	break loop
	}
	}

	// ITERPOP the rest of the iterator stack.
	for _, iter := range iterstack {
	iter.Done()
	}

	fr.locals = nil

	return result, err
	}

	type wrappedError struct {
	msg string
	cause error
	}

	func (e wrappedError) Error() string {
	return e.msg
	}

	// Implements the xerrors.Wrapper interface
	// https://godoc.org/golang.org/x/xerrors#Wrapper
	func (e wrappedError) Unwrap() error {
	return e.cause
	}

	// mandatory is a sentinel value used in a function's defaults tuple
	// to indicate that a (keyword-only) parameter is mandatory.
	type mandatory struct{}

	func (mandatory) String() string { return "mandatory" }
	func (mandatory) Type() string { return "mandatory" }
	func (mandatory) Freeze() {} // immutable
	func (mandatory) Truth() Bool { return False }
	func (mandatory) Hash() (uint32, error) { return 0, nil }

	// A cell is a box containing a Value.
	// Local variables marked as cells hold their value indirectly
	// so that they may be shared by outer and inner nested functions.
	// Cells are always accessed using indirect {FREE,LOCAL,SETLOCAL}CELL instructions.
	// The FreeVars tuple contains only cells.
	// The FREE instruction always yields a cell.
	type cell struct{ v Value }

	func (c *cell) String() string { return "cell" }
	func (c *cell) Type() string { return "cell" }
	func (c *cell) Freeze() {
	if c.v != nil {
	c.v.Freeze()
	}
	}
	func (c *cell) Truth() Bool { panic("unreachable") }
	func (c *cell) Hash() (uint32, error) { panic("unreachable") }