diff options
Diffstat (limited to 'vendor/github.com/d5/tengo/v2/vm.go')
| -rw-r--r-- | vendor/github.com/d5/tengo/v2/vm.go | 883 |
1 files changed, 883 insertions, 0 deletions
diff --git a/vendor/github.com/d5/tengo/v2/vm.go b/vendor/github.com/d5/tengo/v2/vm.go new file mode 100644 index 00000000..783a54a9 --- /dev/null +++ b/vendor/github.com/d5/tengo/v2/vm.go @@ -0,0 +1,883 @@ +package tengo + +import ( + "fmt" + "sync/atomic" + + "github.com/d5/tengo/v2/parser" + "github.com/d5/tengo/v2/token" +) + +// frame represents a function call frame. +type frame struct { + fn *CompiledFunction + freeVars []*ObjectPtr + ip int + basePointer int +} + +// VM is a virtual machine that executes the bytecode compiled by Compiler. +type VM struct { + constants []Object + stack [StackSize]Object + sp int + globals []Object + fileSet *parser.SourceFileSet + frames [MaxFrames]frame + framesIndex int + curFrame *frame + curInsts []byte + ip int + aborting int64 + maxAllocs int64 + allocs int64 + err error +} + +// 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, + framesIndex: 1, + ip: -1, + maxAllocs: maxAllocs, + } + v.frames[0].fn = bytecode.MainFunction + v.frames[0].ip = -1 + v.curFrame = &v.frames[0] + v.curInsts = v.curFrame.fn.Instructions + return v +} + +// Abort aborts the execution. +func (v *VM) Abort() { + atomic.StoreInt64(&v.aborting, 1) +} + +// Run starts the execution. +func (v *VM) Run() (err error) { + // reset VM states + v.sp = 0 + v.curFrame = &(v.frames[0]) + v.curInsts = v.curFrame.fn.Instructions + v.framesIndex = 1 + v.ip = -1 + v.allocs = v.maxAllocs + 1 + + v.run() + atomic.StoreInt64(&v.aborting, 0) + err = v.err + if err != nil { + filePos := v.fileSet.Position( + v.curFrame.fn.SourcePos(v.ip - 1)) + err = fmt.Errorf("Runtime Error: %s\n\tat %s", + err.Error(), filePos) + for v.framesIndex > 1 { + v.framesIndex-- + v.curFrame = &v.frames[v.framesIndex-1] + filePos = v.fileSet.Position( + v.curFrame.fn.SourcePos(v.curFrame.ip - 1)) + err = fmt.Errorf("%s\n\tat %s", err.Error(), filePos) + } + return err + } + return nil +} + +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] = UndefinedValue + 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 = UndefinedValue + } + 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 != UndefinedValue { + 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 == UndefinedValue { + 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 == UndefinedValue { + 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 == UndefinedValue { + 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 == UndefinedValue { + 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]) + v.ip++ + value := v.stack[v.sp-1-numArgs] + if !value.CanCall() { + v.err = fmt.Errorf("not callable: %s", value.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 + 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 + args = append(args, v.stack[v.sp-numArgs:v.sp]...) + ret, e := value.Call(args...) + 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 -> undefined + if ret == nil { + ret = UndefinedValue + } + 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 = UndefinedValue + } + //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, + 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 + } + } +} + +// 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 +} |