vm.go

package tender

import (
	"errors"
	"fmt"
	"io"
	"os"
	"runtime/debug"
	"strings"
	"sync"
	"sync/atomic"

	"github.com/2dprototype/tender/parser"
	"github.com/2dprototype/tender/token"
)

// frame represents a function call frame.
type frame struct {
	fn          *CompiledFunction
	freeVars    []*ObjectPtr
	ip          int
	basePointer int
}

type vmChildCtl struct {
	sync.WaitGroup
	sync.Mutex
	vmMap  map[*VM]struct{}
	errors []error
}

// VM is a virtual machine that executes the bytecode compiled by Compiler.
type VM struct {
	constants   []Object
	stack       []Object
	sp          int
	globals     []Object
	fileSet     *parser.SourceFileSet
	frames      []*frame
	framesIndex int
	curFrame    *frame
	curInsts    []byte
	ip          int
	aborting    int64
	maxAllocs   int64
	allocs      int64
	err         error
	AbortChan   chan struct{}
	childCtl    vmChildCtl
	In          io.Reader
	Out         io.Writer
	Args        []string
}

const (
	initialStackSize = 64
	initialFrames    = 16
)

// NewVM creates a VM.
func NewVM(bytecode *Bytecode, globals []Object, maxAllocs int64) *VM {
	if globals == nil {
		globals = make([]Object, GlobalsSize)
	}
	v := &VM{
		constants:   bytecode.Constants,
		sp:          0,
		globals:     globals,
		fileSet:     bytecode.FileSet,
		frames:      make([]*frame, 0, initialFrames),
		framesIndex: 1,
		ip:          -1,
		maxAllocs:   maxAllocs,
		AbortChan:   make(chan struct{}),
		childCtl:    vmChildCtl{vmMap: make(map[*VM]struct{})},
		In:          os.Stdin,
		Out:         os.Stdout,
		Args:        os.Args,
	}
	frame := &frame{
		fn: bytecode.MainFunction,
		ip: -1,
	}
	v.frames = append(v.frames, frame)
	return v
}

// Run starts the execution.
func (v *VM) Run() (err error) {
	atomic.StoreInt64(&v.aborting, 0)
	_, err = v.RunCompiled(nil)
	if err == nil && atomic.LoadInt64(&v.aborting) == 1 {
		err = ErrVMAborted // root VM was aborted
	}
	return
}

func concatInsts(instructions ...[]byte) []byte {
	var concat []byte
	for _, i := range instructions {
		concat = append(concat, i...)
	}
	return concat
}

var emptyEntry = &CompiledFunction{
	Instructions: MakeInstruction(parser.OpSuspend),
}

// ShallowClone creates a shallow copy of the current VM, with separate stack and frame.
// The copy shares the underlying globals, constants with the original.
// ShallowClone is typically followed by RunCompiled to run user supplied compiled function.
func (v *VM) ShallowClone() *VM {
	vClone := &VM{
		constants:   v.constants,
		sp:          0,
		globals:     v.globals,
		fileSet:     v.fileSet,
		frames:      make([]*frame, 0, initialFrames),
		framesIndex: 1,
		ip:          -1,
		maxAllocs:   v.maxAllocs,
		AbortChan:   make(chan struct{}),
		childCtl:    vmChildCtl{vmMap: make(map[*VM]struct{})},
		In:          v.In,
		Out:         v.Out,
		Args:        v.Args,
	}
	frame := &frame{
		fn: emptyEntry,
		ip: -1,
	}
	vClone.frames = append(vClone.frames, frame)
	return vClone
}

// constract wrapper function func(fn, ...args){ return fn(args...) }
var funcWrapper = &CompiledFunction{
	Instructions: concatInsts(
		MakeInstruction(parser.OpGetLocal, 0),
		MakeInstruction(parser.OpGetLocal, 1),
		MakeInstruction(parser.OpCall, 1, 1),
		MakeInstruction(parser.OpReturn, 1),
	),
	NumLocals:     2,
	NumParameters: 2,
	VarArgs:       true,
}

func (v *VM) releaseSpace() {
	v.stack = nil
	v.frames = append(make([]*frame, 0, initialFrames), v.frames[0])
}

// RunCompiled run the VM with user supplied function fn.
func (v *VM) RunCompiled(fn *CompiledFunction, args ...Object) (val Object, err error) {
	v.stack = make([]Object, initialStackSize)
	if fn == nil { // normal Run
		// reset VM states
		v.sp = 0
	} else { // run user supplied function
		entry := &CompiledFunction{
			Instructions: concatInsts(
				MakeInstruction(parser.OpCall, 1+len(args), 0),
				MakeInstruction(parser.OpSuspend),
			),
		}
		v.stack[0] = funcWrapper
		v.stack[1] = fn
		for i, arg := range args {
			v.stack[i+2] = arg
		}
		v.sp = 2 + len(args)
		v.frames[0].fn = entry
	}

	v.curFrame = v.frames[0]
	v.curInsts = v.curFrame.fn.Instructions
	v.framesIndex = 1
	v.ip = -1
	v.allocs = v.maxAllocs + 1

	defer func() {
		if perr := recover(); perr != nil {
			v.err = ErrPanic{perr, debug.Stack()}
			v.Abort() // run time panic should trigger abort chain
		}
		v.childCtl.Wait() // waits for all child VMs to exit
		err = v.postRun()
		if fn != nil && atomic.LoadInt64(&v.aborting) == 0 {
			val = v.stack[v.sp-1]
		}
		v.releaseSpace()
	}()

	val = NullValue
	v.run()
	return
}

// ErrPanic is an error where panic happended in the VM.
type ErrPanic struct {
	perr  interface{}
	stack []byte
}

func (e ErrPanic) Error() string {
	return fmt.Sprintf("panic: %v\n%s", e.perr, e.stack)
}

func (v *VM) addError(err error) {
	v.childCtl.Lock()
	v.childCtl.errors = append(v.childCtl.errors, err)
	v.childCtl.Unlock()
}

// Abort aborts the execution of current VM and all its descendant VMs.
func (v *VM) Abort() {
	if atomic.LoadInt64(&v.aborting) != 0 {
		return
	}
	v.childCtl.Lock()
	atomic.StoreInt64(&v.aborting, 1)
	close(v.AbortChan) // broadcast to all receivers
	for cvm := range v.childCtl.vmMap {
		cvm.Abort()
	}
	v.childCtl.Unlock()
}

func (v *VM) addChild(cvm *VM) error {
	v.childCtl.Lock()
	defer v.childCtl.Unlock()
	if atomic.LoadInt64(&v.aborting) != 0 {
		return ErrVMAborted
	}
	v.childCtl.Add(1)
	if cvm != nil {
		v.childCtl.vmMap[cvm] = struct{}{}
	}
	return nil
}

func (v *VM) delChild(cvm *VM) {
	if cvm != nil {
		v.childCtl.Lock()
		delete(v.childCtl.vmMap, cvm)
		v.childCtl.Unlock()
	}
	v.childCtl.Done()
}

func (v *VM) callers() (frames []frame) {
	curFrame := *v.curFrame
	curFrame.ip = v.ip - 1
	frames = append(frames, curFrame)
	for i := v.framesIndex - 1; i >= 1; i-- {
		curFrame = *v.frames[i-1]
		frames = append(frames, curFrame)
	}
	return frames
}

func (v *VM) callStack(frames []frame) string {
	if frames == nil {
		frames = v.callers()
	}

	var sb strings.Builder
	for _, f := range frames {
		filePos := v.fileSet.Position(f.fn.SourcePos(f.ip))
		fmt.Fprintf(&sb, "\n\tat %s", filePos)
	}
	return sb.String()
}

func (v *VM) postRun() (err error) {
	err = v.err
	// ErrVMAborted is user behavior thus it is not an actual runtime error
	if errors.Is(err, ErrVMAborted) {
		err = nil
	}
	if err != nil {
		var e ErrPanic
		if errors.As(err, &e) {
			err = fmt.Errorf("\nRuntime Panic: %v%s\n%s", e.perr, v.callStack(nil), e.stack)
		} else {
			err = fmt.Errorf("\nRuntime Error: %w%s", err, v.callStack(nil))
		}
	}

	var sb strings.Builder
	for _, cerr := range v.childCtl.errors {
		fmt.Fprintf(&sb, "%v\n", cerr)
	}
	cerrs := sb.String()

	if err != nil && len(cerrs) != 0 {
		err = fmt.Errorf("%w\n%s", err, cerrs)
		return
	}
	if len(cerrs) != 0 {
		err = fmt.Errorf("%s", cerrs)
	}
	return
}

// VMObj exports VM
type VMObj struct {
	ObjectImpl
	Value *VM
}

func (v *VM) selfObject() Object {
	return &VMObj{Value: v}
}

func (v *VM) run() {
	for atomic.LoadInt64(&v.aborting) == 0 {
		v.ip++

		switch v.curInsts[v.ip] {
		case parser.OpConstant:
			v.ip += 2
			cidx := int(v.curInsts[v.ip]) | int(v.curInsts[v.ip-1])<<8

			v.stack[v.sp] = v.constants[cidx]
			v.sp++
		case parser.OpNull:
			v.stack[v.sp] = NullValue
			v.sp++
		case parser.OpBinaryOp:
			v.ip++
			right := v.stack[v.sp-1]
			left := v.stack[v.sp-2]
			tok := token.Token(v.curInsts[v.ip])
			res, e := left.BinaryOp(tok, right)
			if e != nil {
				v.sp -= 2
				if e == ErrInvalidOperator {
					v.err = fmt.Errorf("invalid operation: %s %s %s",
						left.TypeName(), tok.String(), right.TypeName())
					return
				}
				v.err = e
				return
			}

			v.allocs--
			if v.allocs == 0 {
				v.err = ErrObjectAllocLimit
				return
			}

			v.stack[v.sp-2] = res
			v.sp--
		case parser.OpEqual:
			right := v.stack[v.sp-1]
			left := v.stack[v.sp-2]
			v.sp -= 2
			if left.Equals(right) {
				v.stack[v.sp] = TrueValue
			} else {
				v.stack[v.sp] = FalseValue
			}
			v.sp++
		case parser.OpNotEqual:
			right := v.stack[v.sp-1]
			left := v.stack[v.sp-2]
			v.sp -= 2
			if left.Equals(right) {
				v.stack[v.sp] = FalseValue
			} else {
				v.stack[v.sp] = TrueValue
			}
			v.sp++
		case parser.OpPop:
			v.sp--
		case parser.OpTrue:
			v.stack[v.sp] = TrueValue
			v.sp++
		case parser.OpFalse:
			v.stack[v.sp] = FalseValue
			v.sp++
		case parser.OpLNot:
			operand := v.stack[v.sp-1]
			v.sp--
			if operand.IsFalsy() {
				v.stack[v.sp] = TrueValue
			} else {
				v.stack[v.sp] = FalseValue
			}
			v.sp++
		case parser.OpBComplement:
			operand := v.stack[v.sp-1]
			v.sp--

			switch x := operand.(type) {
			case *Int:
				var res Object = &Int{Value: ^x.Value}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp] = res
				v.sp++
			default:
				v.err = fmt.Errorf("invalid operation: ^%s",
					operand.TypeName())
				return
			}
		case parser.OpMinus:
			operand := v.stack[v.sp-1]
			v.sp--

			switch x := operand.(type) {
			case *Int:
				var res Object = &Int{Value: -x.Value}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp] = res
				v.sp++
			case *Float:
				var res Object = &Float{Value: -x.Value}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp] = res
				v.sp++
			default:
				v.err = fmt.Errorf("invalid operation: -%s",
					operand.TypeName())
				return
			}
		case parser.OpJumpFalsy:
			v.ip += 2
			v.sp--
			if v.stack[v.sp].IsFalsy() {
				pos := int(v.curInsts[v.ip]) | int(v.curInsts[v.ip-1])<<8
				v.ip = pos - 1
			}
		case parser.OpAndJump:
			v.ip += 2
			if v.stack[v.sp-1].IsFalsy() {
				pos := int(v.curInsts[v.ip]) | int(v.curInsts[v.ip-1])<<8
				v.ip = pos - 1
			} else {
				v.sp--
			}
		case parser.OpOrJump:
			v.ip += 2
			if v.stack[v.sp-1].IsFalsy() {
				v.sp--
			} else {
				pos := int(v.curInsts[v.ip]) | int(v.curInsts[v.ip-1])<<8
				v.ip = pos - 1
			}
		case parser.OpJump:
			pos := int(v.curInsts[v.ip+2]) | int(v.curInsts[v.ip+1])<<8
			v.ip = pos - 1
		case parser.OpSetGlobal:
			v.ip += 2
			v.sp--
			globalIndex := int(v.curInsts[v.ip]) | int(v.curInsts[v.ip-1])<<8
			v.globals[globalIndex] = v.stack[v.sp]
		case parser.OpSetSelGlobal:
			v.ip += 3
			globalIndex := int(v.curInsts[v.ip-1]) | int(v.curInsts[v.ip-2])<<8
			numSelectors := int(v.curInsts[v.ip])

			// selectors and RHS value
			selectors := make([]Object, numSelectors)
			for i := 0; i < numSelectors; i++ {
				selectors[i] = v.stack[v.sp-numSelectors+i]
			}
			val := v.stack[v.sp-numSelectors-1]
			v.sp -= numSelectors + 1
			e := indexAssign(v.globals[globalIndex], val, selectors)
			if e != nil {
				v.err = e
				return
			}
		case parser.OpGetGlobal:
			v.ip += 2
			globalIndex := int(v.curInsts[v.ip]) | int(v.curInsts[v.ip-1])<<8
			val := v.globals[globalIndex]
			v.stack[v.sp] = val
			v.sp++
		case parser.OpArray:
			v.ip += 2
			numElements := int(v.curInsts[v.ip]) | int(v.curInsts[v.ip-1])<<8

			var elements []Object
			for i := v.sp - numElements; i < v.sp; i++ {
				elements = append(elements, v.stack[i])
			}
			v.sp -= numElements

			var arr Object = &Array{Value: elements}
			v.allocs--
			if v.allocs == 0 {
				v.err = ErrObjectAllocLimit
				return
			}

			v.stack[v.sp] = arr
			v.sp++
		case parser.OpMap:
			v.ip += 2
			numElements := int(v.curInsts[v.ip]) | int(v.curInsts[v.ip-1])<<8
			kv := make(map[string]Object)
			for i := v.sp - numElements; i < v.sp; i += 2 {
				key := v.stack[i]
				value := v.stack[i+1]
				kv[key.(*String).Value] = value
			}
			v.sp -= numElements

			var m Object = &Map{Value: kv}
			v.allocs--
			if v.allocs == 0 {
				v.err = ErrObjectAllocLimit
				return
			}
			v.stack[v.sp] = m
			v.sp++
		case parser.OpError:
			value := v.stack[v.sp-1]
			var e Object = &Error{
				Value: value,
			}
			v.allocs--
			if v.allocs == 0 {
				v.err = ErrObjectAllocLimit
				return
			}
			v.stack[v.sp-1] = e
		case parser.OpImmutable:
			value := v.stack[v.sp-1]
			switch value := value.(type) {
			case *Array:
				var immutableArray Object = &ImmutableArray{
					Value: value.Value,
				}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp-1] = immutableArray
			case *Map:
				var immutableMap Object = &ImmutableMap{
					Value: value.Value,
				}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp-1] = immutableMap
			}
		case parser.OpIndex:
			index := v.stack[v.sp-1]
			left := v.stack[v.sp-2]
			v.sp -= 2

			val, err := left.IndexGet(index)
			if err != nil {
				if err == ErrNotIndexable {
					v.err = fmt.Errorf("not indexable: %s", index.TypeName())
					return
				}
				if err == ErrInvalidIndexType {
					v.err = fmt.Errorf("invalid index type: %s", index.TypeName())
					return
				}
				v.err = err
				return
			}
			if val == nil {
				val = NullValue
			}
			v.stack[v.sp] = val
			v.sp++
		case parser.OpSliceIndex:
			high := v.stack[v.sp-1]
			low := v.stack[v.sp-2]
			left := v.stack[v.sp-3]
			v.sp -= 3

			var lowIdx int64
			if low != NullValue {
				if low, ok := low.(*Int); ok {
					lowIdx = low.Value
				} else {
					v.err = fmt.Errorf("invalid slice index type: %s",
						low.TypeName())
					return
				}
			}

			switch left := left.(type) {
			case *Array:
				numElements := int64(len(left.Value))
				var highIdx int64
				if high == NullValue {
					highIdx = numElements
				} else if high, ok := high.(*Int); ok {
					highIdx = high.Value
				} else {
					v.err = fmt.Errorf("invalid slice index type: %s",
						high.TypeName())
					return
				}
				if lowIdx > highIdx {
					v.err = fmt.Errorf("invalid slice index: %d > %d",
						lowIdx, highIdx)
					return
				}
				if lowIdx < 0 {
					lowIdx = 0
				} else if lowIdx > numElements {
					lowIdx = numElements
				}
				if highIdx < 0 {
					highIdx = 0
				} else if highIdx > numElements {
					highIdx = numElements
				}
				var val Object = &Array{
					Value: left.Value[lowIdx:highIdx],
				}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp] = val
				v.sp++
			case *ImmutableArray:
				numElements := int64(len(left.Value))
				var highIdx int64
				if high == NullValue {
					highIdx = numElements
				} else if high, ok := high.(*Int); ok {
					highIdx = high.Value
				} else {
					v.err = fmt.Errorf("invalid slice index type: %s",
						high.TypeName())
					return
				}
				if lowIdx > highIdx {
					v.err = fmt.Errorf("invalid slice index: %d > %d",
						lowIdx, highIdx)
					return
				}
				if lowIdx < 0 {
					lowIdx = 0
				} else if lowIdx > numElements {
					lowIdx = numElements
				}
				if highIdx < 0 {
					highIdx = 0
				} else if highIdx > numElements {
					highIdx = numElements
				}
				var val Object = &Array{
					Value: left.Value[lowIdx:highIdx],
				}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp] = val
				v.sp++
			case *String:
				numElements := int64(len(left.Value))
				var highIdx int64
				if high == NullValue {
					highIdx = numElements
				} else if high, ok := high.(*Int); ok {
					highIdx = high.Value
				} else {
					v.err = fmt.Errorf("invalid slice index type: %s",
						high.TypeName())
					return
				}
				if lowIdx > highIdx {
					v.err = fmt.Errorf("invalid slice index: %d > %d",
						lowIdx, highIdx)
					return
				}
				if lowIdx < 0 {
					lowIdx = 0
				} else if lowIdx > numElements {
					lowIdx = numElements
				}
				if highIdx < 0 {
					highIdx = 0
				} else if highIdx > numElements {
					highIdx = numElements
				}
				var val Object = &String{
					Value: left.Value[lowIdx:highIdx],
				}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp] = val
				v.sp++
			case *Bytes:
				numElements := int64(len(left.Value))
				var highIdx int64
				if high == NullValue {
					highIdx = numElements
				} else if high, ok := high.(*Int); ok {
					highIdx = high.Value
				} else {
					v.err = fmt.Errorf("invalid slice index type: %s",
						high.TypeName())
					return
				}
				if lowIdx > highIdx {
					v.err = fmt.Errorf("invalid slice index: %d > %d",
						lowIdx, highIdx)
					return
				}
				if lowIdx < 0 {
					lowIdx = 0
				} else if lowIdx > numElements {
					lowIdx = numElements
				}
				if highIdx < 0 {
					highIdx = 0
				} else if highIdx > numElements {
					highIdx = numElements
				}
				var val Object = &Bytes{
					Value: left.Value[lowIdx:highIdx],
				}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp] = val
				v.sp++
			}
		case parser.OpCall:
			numArgs := int(v.curInsts[v.ip+1])
			spread := int(v.curInsts[v.ip+2])
			v.ip += 2

			value := v.stack[v.sp-1-numArgs]
			if !value.CanCall() {
				v.err = fmt.Errorf("not callable: %s", value.TypeName())
				return
			}

			if spread == 1 {
				v.sp--
				switch arr := v.stack[v.sp].(type) {
				case *Array:
					v.checkGrowStack(len(arr.Value))
					for _, item := range arr.Value {
						v.stack[v.sp] = item
						v.sp++
					}
					numArgs += len(arr.Value) - 1
				case *ImmutableArray:
					v.checkGrowStack(len(arr.Value))
					for _, item := range arr.Value {
						v.stack[v.sp] = item
						v.sp++
					}
					numArgs += len(arr.Value) - 1
				default:
					v.err = fmt.Errorf("not an array: %s", arr.TypeName())
					return
				}
			}

			if callee, ok := value.(*CompiledFunction); ok {
				if callee.VarArgs {
					// if the closure is variadic,
					// roll up all variadic parameters into an array
					realArgs := callee.NumParameters - 1
					varArgs := numArgs - realArgs
					if varArgs >= 0 {
						numArgs = realArgs + 1
						args := make([]Object, varArgs)
						spStart := v.sp - varArgs
						for i := spStart; i < v.sp; i++ {
							args[i-spStart] = v.stack[i]
						}
						v.stack[spStart] = &Array{Value: args}
						v.sp = spStart + 1
					}
				}
				if numArgs != callee.NumParameters {
					if callee.VarArgs {
						v.err = fmt.Errorf(
							"wrong number of arguments: want>=%d, got=%d",
							callee.NumParameters-1, numArgs)
					} else {
						v.err = fmt.Errorf(
							"wrong number of arguments: want=%d, got=%d",
							callee.NumParameters, numArgs)
					}
					return
				}

				// test if it's tail-call
				if callee == v.curFrame.fn { // recursion
					nextOp := v.curInsts[v.ip+1]
					if nextOp == parser.OpReturn ||
						(nextOp == parser.OpPop &&
							parser.OpReturn == v.curInsts[v.ip+2]) {
						for p := 0; p < numArgs; p++ {
							v.stack[v.curFrame.basePointer+p] =
								v.stack[v.sp-numArgs+p]
						}
						v.sp -= numArgs + 1
						v.ip = -1 // reset IP to beginning of the frame
						continue
					}
				}
				if v.framesIndex >= MaxFrames {
					v.err = ErrStackOverflow
					return
				}

				// update call frame
				v.curFrame.ip = v.ip // store current ip before call
				if v.framesIndex >= len(v.frames) {
					v.frames = append(v.frames, &frame{})
				}
				v.curFrame = v.frames[v.framesIndex]
				v.curFrame.fn = callee
				v.curFrame.freeVars = callee.Free
				v.curFrame.basePointer = v.sp - numArgs
				v.curInsts = callee.Instructions
				v.ip = -1
				v.framesIndex++
				v.sp = v.sp - numArgs + callee.NumLocals
			} else {
				var args []Object
				if bltnfn, ok := value.(*BuiltinFunction); ok {
					if bltnfn.NeedVMObj {
						// pass VM as the first para to builtin functions
						args = append(args, v.selfObject())
					}
				}
				args = append(args, v.stack[v.sp-numArgs:v.sp]...)
				ret, e := value.Call(args...)
				// fmt.Println(ret)
				v.sp -= numArgs + 1

				// runtime error
				if e != nil {
					if e == ErrWrongNumArguments {
						v.err = fmt.Errorf(
							"wrong number of arguments in call to '%s'",
							value.TypeName())
						return
					}
					if e, ok := e.(ErrInvalidArgumentType); ok {
						v.err = fmt.Errorf(
							"invalid type for argument '%s' in call to '%s': "+
								"expected %s, found %s",
							e.Name, value.TypeName(), e.Expected, e.Found)
						return
					}
					v.err = e
					return
				}

				// nil return -> null
				if ret == nil {
					ret = NullValue
				}
				v.allocs--
				if v.allocs == 0 {
					v.err = ErrObjectAllocLimit
					return
				}
				v.stack[v.sp] = ret
				v.sp++
			}
		case parser.OpReturn:
			v.ip++
			var retVal Object
			if int(v.curInsts[v.ip]) == 1 {
				retVal = v.stack[v.sp-1]
			} else {
				retVal = NullValue
			}
			//v.sp--
			v.framesIndex--
			v.curFrame = v.frames[v.framesIndex-1]
			v.curInsts = v.curFrame.fn.Instructions
			v.ip = v.curFrame.ip
			//v.sp = lastFrame.basePointer - 1
			v.sp = v.frames[v.framesIndex].basePointer
			// skip stack overflow check because (newSP) <= (oldSP)
			v.stack[v.sp-1] = retVal
			//v.sp++
		case parser.OpDefineLocal:
			v.ip++
			localIndex := int(v.curInsts[v.ip])
			sp := v.curFrame.basePointer + localIndex

			// local variables can be mutated by other actions
			// so always store the copy of popped value
			val := v.stack[v.sp-1]
			v.sp--
			v.stack[sp] = val
		case parser.OpSetLocal:
			localIndex := int(v.curInsts[v.ip+1])
			v.ip++
			sp := v.curFrame.basePointer + localIndex

			// update pointee of v.stack[sp] instead of replacing the pointer
			// itself. this is needed because there can be free variables
			// referencing the same local variables.
			val := v.stack[v.sp-1]
			v.sp--
			if obj, ok := v.stack[sp].(*ObjectPtr); ok {
				*obj.Value = val
				val = obj
			}
			v.stack[sp] = val // also use a copy of popped value
		case parser.OpSetSelLocal:
			localIndex := int(v.curInsts[v.ip+1])
			numSelectors := int(v.curInsts[v.ip+2])
			v.ip += 2

			// selectors and RHS value
			selectors := make([]Object, numSelectors)
			for i := 0; i < numSelectors; i++ {
				selectors[i] = v.stack[v.sp-numSelectors+i]
			}
			val := v.stack[v.sp-numSelectors-1]
			v.sp -= numSelectors + 1
			dst := v.stack[v.curFrame.basePointer+localIndex]
			if obj, ok := dst.(*ObjectPtr); ok {
				dst = *obj.Value
			}
			if e := indexAssign(dst, val, selectors); e != nil {
				v.err = e
				return
			}
		case parser.OpGetLocal:
			v.ip++
			localIndex := int(v.curInsts[v.ip])
			val := v.stack[v.curFrame.basePointer+localIndex]
			if obj, ok := val.(*ObjectPtr); ok {
				val = *obj.Value
			}
			v.stack[v.sp] = val
			v.sp++
		case parser.OpGetBuiltin:
			v.ip++
			builtinIndex := int(v.curInsts[v.ip])
			v.stack[v.sp] = builtinFuncs[builtinIndex]
			v.sp++
		case parser.OpClosure:
			v.ip += 3
			constIndex := int(v.curInsts[v.ip-1]) | int(v.curInsts[v.ip-2])<<8
			numFree := int(v.curInsts[v.ip])
			fn, ok := v.constants[constIndex].(*CompiledFunction)
			if !ok {
				v.err = fmt.Errorf("not function: %s", fn.TypeName())
				return
			}
			free := make([]*ObjectPtr, numFree)
			for i := 0; i < numFree; i++ {
				switch freeVar := (v.stack[v.sp-numFree+i]).(type) {
				case *ObjectPtr:
					free[i] = freeVar
				default:
					free[i] = &ObjectPtr{
						Value: &v.stack[v.sp-numFree+i],
					}
				}
			}
			v.sp -= numFree
			cl := &CompiledFunction{
				Instructions:  fn.Instructions,
				NumLocals:     fn.NumLocals,
				NumParameters: fn.NumParameters,
				VarArgs:       fn.VarArgs,
				SourceMap:     fn.SourceMap,
				Free:          free,
			}
			v.allocs--
			if v.allocs == 0 {
				v.err = ErrObjectAllocLimit
				return
			}
			v.stack[v.sp] = cl
			v.sp++
		case parser.OpGetFreePtr:
			v.ip++
			freeIndex := int(v.curInsts[v.ip])
			val := v.curFrame.freeVars[freeIndex]
			v.stack[v.sp] = val
			v.sp++
		case parser.OpGetFree:
			v.ip++
			freeIndex := int(v.curInsts[v.ip])
			val := *v.curFrame.freeVars[freeIndex].Value
			v.stack[v.sp] = val
			v.sp++
		case parser.OpSetFree:
			v.ip++
			freeIndex := int(v.curInsts[v.ip])
			*v.curFrame.freeVars[freeIndex].Value = v.stack[v.sp-1]
			v.sp--
		case parser.OpGetLocalPtr:
			v.ip++
			localIndex := int(v.curInsts[v.ip])
			sp := v.curFrame.basePointer + localIndex
			val := v.stack[sp]
			var freeVar *ObjectPtr
			if obj, ok := val.(*ObjectPtr); ok {
				freeVar = obj
			} else {
				freeVar = &ObjectPtr{Value: &val}
				v.stack[sp] = freeVar
			}
			v.stack[v.sp] = freeVar
			v.sp++
		case parser.OpSetSelFree:
			v.ip += 2
			freeIndex := int(v.curInsts[v.ip-1])
			numSelectors := int(v.curInsts[v.ip])

			// selectors and RHS value
			selectors := make([]Object, numSelectors)
			for i := 0; i < numSelectors; i++ {
				selectors[i] = v.stack[v.sp-numSelectors+i]
			}
			val := v.stack[v.sp-numSelectors-1]
			v.sp -= numSelectors + 1
			e := indexAssign(*v.curFrame.freeVars[freeIndex].Value,
				val, selectors)
			if e != nil {
				v.err = e
				return
			}
		case parser.OpIteratorInit:
			var iterator Object
			dst := v.stack[v.sp-1]
			v.sp--
			if !dst.CanIterate() {
				v.err = fmt.Errorf("not iterable: %s", dst.TypeName())
				return
			}
			iterator = dst.Iterate()
			v.allocs--
			if v.allocs == 0 {
				v.err = ErrObjectAllocLimit
				return
			}
			v.stack[v.sp] = iterator
			v.sp++
		case parser.OpIteratorNext:
			iterator := v.stack[v.sp-1]
			v.sp--
			hasMore := iterator.(Iterator).Next()
			if hasMore {
				v.stack[v.sp] = TrueValue
			} else {
				v.stack[v.sp] = FalseValue
			}
			v.sp++
		case parser.OpIteratorKey:
			iterator := v.stack[v.sp-1]
			v.sp--
			val := iterator.(Iterator).Key()
			v.stack[v.sp] = val
			v.sp++
		case parser.OpIteratorValue:
			iterator := v.stack[v.sp-1]
			v.sp--
			val := iterator.(Iterator).Value()
			v.stack[v.sp] = val
			v.sp++
		case parser.OpSuspend:
			return
		default:
			v.err = fmt.Errorf("unknown opcode: %d", v.curInsts[v.ip])
			return
		}
		v.checkGrowStack(0)
	}
}

func (v *VM) checkGrowStack(added int) {
	should := v.sp + added
	if should < len(v.stack) {
		return
	}
	if should >= StackSize {
		v.err = ErrStackOverflow
		return
	}
	roundup := initialStackSize
	newSize := len(v.stack) * 2
	if should > newSize {
		newSize = (should + roundup) / roundup * roundup
	}
	new := make([]Object, newSize)
	copy(new, v.stack)
	v.stack = new
}

// IsStackEmpty tests if the stack is empty or not.
func (v *VM) IsStackEmpty() bool {
	return v.sp == 0
}

func indexAssign(dst, src Object, selectors []Object) error {
	numSel := len(selectors)
	for sidx := numSel - 1; sidx > 0; sidx-- {
		next, err := dst.IndexGet(selectors[sidx])
		if err != nil {
			if err == ErrNotIndexable {
				return fmt.Errorf("not indexable: %s", dst.TypeName())
			}
			if err == ErrInvalidIndexType {
				return fmt.Errorf("invalid index type: %s",
					selectors[sidx].TypeName())
			}
			return err
		}
		dst = next
	}

	if err := dst.IndexSet(selectors[0], src); err != nil {
		if err == ErrNotIndexAssignable {
			return fmt.Errorf("not index-assignable: %s", dst.TypeName())
		}
		if err == ErrInvalidIndexValueType {
			return fmt.Errorf("invaid index value type: %s", src.TypeName())
		}
		return err
	}
	return nil
}