interp.go

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/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.

	f := fn.funcode
	if !f.Prog.Recursion {
		// 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 == f {
				return nil, fmt.Errorf("function %s called recursively", fn.Name())
			}
		}
	}

	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

	// Use defer so that application panics can pass through
	// interpreter without leaving thread in a bad state.
	defer func() {
		// ITERPOP the rest of the iterator stack.
		for _, iter := range iterstack {
			iter.Done()
		}

		fr.locals = nil
	}()

	sp := 0
	var pc uint32
	var result Value
	code := f.Code
loop:
	for {
		thread.Steps++
		if thread.Steps >= thread.maxSteps {
			if thread.OnMaxSteps != nil {
				thread.OnMaxSteps(thread)
			} else {
				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.INPLACE_PIPE:
			y := stack[sp-1]
			x := stack[sp-2]
			sp -= 2

			// It's possible that y is not Dict but
			// nonetheless defines x|y, in which case we
			// should fall back to the general case.
			var z Value
			if xdict, ok := x.(*Dict); ok {
				if ydict, ok := y.(*Dict); ok {
					if err = xdict.ht.checkMutable("apply |= to"); err != nil {
						break loop
					}
					xdict.ht.addAll(&ydict.ht) // can't fail
					z = xdict
				}
			}
			if z == nil {
				z, err = Binary(syntax.PIPE, 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
		}
	}
	// (deferred cleanup runs here)
	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") }