From 115d20373c21b107a428a55247c64f900e116038 Mon Sep 17 00:00:00 2001 From: Wim Date: Sat, 6 Apr 2019 22:18:25 +0200 Subject: Update tengo vendor and load the stdlib. Fixes #789 (#792) --- vendor/github.com/d5/tengo/compiler/bytecode.go | 66 +---- .../d5/tengo/compiler/bytecode_decode.go | 97 +++++++ .../d5/tengo/compiler/bytecode_optimize.go | 129 ++++++++++ .../d5/tengo/compiler/compilation_scope.go | 7 +- vendor/github.com/d5/tengo/compiler/compiler.go | 268 +++++++++++++------- .../d5/tengo/compiler/compiler_assign.go | 22 +- .../d5/tengo/compiler/compiler_module.go | 87 ++----- .../github.com/d5/tengo/compiler/instructions.go | 13 + vendor/github.com/d5/tengo/compiler/opcodes.go | 282 +++++++++------------ .../github.com/d5/tengo/compiler/symbol_table.go | 4 +- 10 files changed, 594 insertions(+), 381 deletions(-) create mode 100644 vendor/github.com/d5/tengo/compiler/bytecode_decode.go create mode 100644 vendor/github.com/d5/tengo/compiler/bytecode_optimize.go (limited to 'vendor/github.com/d5/tengo/compiler') diff --git a/vendor/github.com/d5/tengo/compiler/bytecode.go b/vendor/github.com/d5/tengo/compiler/bytecode.go index 42527731..35f36c0a 100644 --- a/vendor/github.com/d5/tengo/compiler/bytecode.go +++ b/vendor/github.com/d5/tengo/compiler/bytecode.go @@ -17,32 +17,6 @@ type Bytecode struct { Constants []objects.Object } -// Decode reads Bytecode data from the reader. -func (b *Bytecode) Decode(r io.Reader) error { - dec := gob.NewDecoder(r) - - if err := dec.Decode(&b.FileSet); err != nil { - return err - } - // TODO: files in b.FileSet.File does not have their 'set' field properly set to b.FileSet - // as it's private field and not serialized by gob encoder/decoder. - - if err := dec.Decode(&b.MainFunction); err != nil { - return err - } - - if err := dec.Decode(&b.Constants); err != nil { - return err - } - - // replace Bool and Undefined with known value - for i, v := range b.Constants { - b.Constants[i] = cleanupObjects(v) - } - - return nil -} - // Encode writes Bytecode data to the writer. func (b *Bytecode) Encode(w io.Writer) error { enc := gob.NewEncoder(w) @@ -59,6 +33,17 @@ func (b *Bytecode) Encode(w io.Writer) error { return enc.Encode(b.Constants) } +// CountObjects returns the number of objects found in Constants. +func (b *Bytecode) CountObjects() int { + n := 0 + + for _, c := range b.Constants { + n += objects.CountObjects(c) + } + + return n +} + // FormatInstructions returns human readable string representations of // compiled instructions. func (b *Bytecode) FormatInstructions() []string { @@ -83,51 +68,22 @@ func (b *Bytecode) FormatConstants() (output []string) { return } -func cleanupObjects(o objects.Object) objects.Object { - switch o := o.(type) { - case *objects.Bool: - if o.IsFalsy() { - return objects.FalseValue - } - return objects.TrueValue - case *objects.Undefined: - return objects.UndefinedValue - case *objects.Array: - for i, v := range o.Value { - o.Value[i] = cleanupObjects(v) - } - case *objects.Map: - for k, v := range o.Value { - o.Value[k] = cleanupObjects(v) - } - } - - return o -} - func init() { gob.Register(&source.FileSet{}) gob.Register(&source.File{}) gob.Register(&objects.Array{}) - gob.Register(&objects.ArrayIterator{}) gob.Register(&objects.Bool{}) - gob.Register(&objects.Break{}) - gob.Register(&objects.BuiltinFunction{}) gob.Register(&objects.Bytes{}) gob.Register(&objects.Char{}) gob.Register(&objects.Closure{}) gob.Register(&objects.CompiledFunction{}) - gob.Register(&objects.Continue{}) gob.Register(&objects.Error{}) gob.Register(&objects.Float{}) gob.Register(&objects.ImmutableArray{}) gob.Register(&objects.ImmutableMap{}) gob.Register(&objects.Int{}) gob.Register(&objects.Map{}) - gob.Register(&objects.MapIterator{}) - gob.Register(&objects.ReturnValue{}) gob.Register(&objects.String{}) - gob.Register(&objects.StringIterator{}) gob.Register(&objects.Time{}) gob.Register(&objects.Undefined{}) gob.Register(&objects.UserFunction{}) diff --git a/vendor/github.com/d5/tengo/compiler/bytecode_decode.go b/vendor/github.com/d5/tengo/compiler/bytecode_decode.go new file mode 100644 index 00000000..b3b32a64 --- /dev/null +++ b/vendor/github.com/d5/tengo/compiler/bytecode_decode.go @@ -0,0 +1,97 @@ +package compiler + +import ( + "encoding/gob" + "fmt" + "io" + + "github.com/d5/tengo/objects" +) + +// Decode reads Bytecode data from the reader. +func (b *Bytecode) Decode(r io.Reader, modules *objects.ModuleMap) error { + if modules == nil { + modules = objects.NewModuleMap() + } + + dec := gob.NewDecoder(r) + + if err := dec.Decode(&b.FileSet); err != nil { + return err + } + // TODO: files in b.FileSet.File does not have their 'set' field properly set to b.FileSet + // as it's private field and not serialized by gob encoder/decoder. + + if err := dec.Decode(&b.MainFunction); err != nil { + return err + } + + if err := dec.Decode(&b.Constants); err != nil { + return err + } + for i, v := range b.Constants { + fv, err := fixDecoded(v, modules) + if err != nil { + return err + } + b.Constants[i] = fv + } + + return nil +} + +func fixDecoded(o objects.Object, modules *objects.ModuleMap) (objects.Object, error) { + switch o := o.(type) { + case *objects.Bool: + if o.IsFalsy() { + return objects.FalseValue, nil + } + return objects.TrueValue, nil + case *objects.Undefined: + return objects.UndefinedValue, nil + case *objects.Array: + for i, v := range o.Value { + fv, err := fixDecoded(v, modules) + if err != nil { + return nil, err + } + o.Value[i] = fv + } + case *objects.ImmutableArray: + for i, v := range o.Value { + fv, err := fixDecoded(v, modules) + if err != nil { + return nil, err + } + o.Value[i] = fv + } + case *objects.Map: + for k, v := range o.Value { + fv, err := fixDecoded(v, modules) + if err != nil { + return nil, err + } + o.Value[k] = fv + } + case *objects.ImmutableMap: + modName := moduleName(o) + if mod := modules.GetBuiltinModule(modName); mod != nil { + return mod.AsImmutableMap(modName), nil + } + + for k, v := range o.Value { + // encoding of user function not supported + if _, isUserFunction := v.(*objects.UserFunction); isUserFunction { + return nil, fmt.Errorf("user function not decodable") + } + + fv, err := fixDecoded(v, modules) + if err != nil { + return nil, err + } + o.Value[k] = fv + } + } + + return o, nil +} diff --git a/vendor/github.com/d5/tengo/compiler/bytecode_optimize.go b/vendor/github.com/d5/tengo/compiler/bytecode_optimize.go new file mode 100644 index 00000000..9526de2e --- /dev/null +++ b/vendor/github.com/d5/tengo/compiler/bytecode_optimize.go @@ -0,0 +1,129 @@ +package compiler + +import ( + "fmt" + + "github.com/d5/tengo/objects" +) + +// RemoveDuplicates finds and remove the duplicate values in Constants. +// Note this function mutates Bytecode. +func (b *Bytecode) RemoveDuplicates() { + var deduped []objects.Object + + indexMap := make(map[int]int) // mapping from old constant index to new index + ints := make(map[int64]int) + strings := make(map[string]int) + floats := make(map[float64]int) + chars := make(map[rune]int) + immutableMaps := make(map[string]int) // for modules + + for curIdx, c := range b.Constants { + switch c := c.(type) { + case *objects.CompiledFunction: + // add to deduped list + indexMap[curIdx] = len(deduped) + deduped = append(deduped, c) + case *objects.ImmutableMap: + modName := moduleName(c) + newIdx, ok := immutableMaps[modName] + if modName != "" && ok { + indexMap[curIdx] = newIdx + } else { + newIdx = len(deduped) + immutableMaps[modName] = newIdx + indexMap[curIdx] = newIdx + deduped = append(deduped, c) + } + case *objects.Int: + if newIdx, ok := ints[c.Value]; ok { + indexMap[curIdx] = newIdx + } else { + newIdx = len(deduped) + ints[c.Value] = newIdx + indexMap[curIdx] = newIdx + deduped = append(deduped, c) + } + case *objects.String: + if newIdx, ok := strings[c.Value]; ok { + indexMap[curIdx] = newIdx + } else { + newIdx = len(deduped) + strings[c.Value] = newIdx + indexMap[curIdx] = newIdx + deduped = append(deduped, c) + } + case *objects.Float: + if newIdx, ok := floats[c.Value]; ok { + indexMap[curIdx] = newIdx + } else { + newIdx = len(deduped) + floats[c.Value] = newIdx + indexMap[curIdx] = newIdx + deduped = append(deduped, c) + } + case *objects.Char: + if newIdx, ok := chars[c.Value]; ok { + indexMap[curIdx] = newIdx + } else { + newIdx = len(deduped) + chars[c.Value] = newIdx + indexMap[curIdx] = newIdx + deduped = append(deduped, c) + } + default: + panic(fmt.Errorf("unsupported top-level constant type: %s", c.TypeName())) + } + } + + // replace with de-duplicated constants + b.Constants = deduped + + // update CONST instructions with new indexes + // main function + updateConstIndexes(b.MainFunction.Instructions, indexMap) + // other compiled functions in constants + for _, c := range b.Constants { + switch c := c.(type) { + case *objects.CompiledFunction: + updateConstIndexes(c.Instructions, indexMap) + } + } +} + +func updateConstIndexes(insts []byte, indexMap map[int]int) { + i := 0 + for i < len(insts) { + op := insts[i] + numOperands := OpcodeOperands[op] + _, read := ReadOperands(numOperands, insts[i+1:]) + + switch op { + case OpConstant: + curIdx := int(insts[i+2]) | int(insts[i+1])<<8 + newIdx, ok := indexMap[curIdx] + if !ok { + panic(fmt.Errorf("constant index not found: %d", curIdx)) + } + copy(insts[i:], MakeInstruction(op, newIdx)) + case OpClosure: + curIdx := int(insts[i+2]) | int(insts[i+1])<<8 + numFree := int(insts[i+3]) + newIdx, ok := indexMap[curIdx] + if !ok { + panic(fmt.Errorf("constant index not found: %d", curIdx)) + } + copy(insts[i:], MakeInstruction(op, newIdx, numFree)) + } + + i += 1 + read + } +} + +func moduleName(mod *objects.ImmutableMap) string { + if modName, ok := mod.Value["__module_name__"].(*objects.String); ok { + return modName.Value + } + + return "" +} diff --git a/vendor/github.com/d5/tengo/compiler/compilation_scope.go b/vendor/github.com/d5/tengo/compiler/compilation_scope.go index dd198ae9..41e7876b 100644 --- a/vendor/github.com/d5/tengo/compiler/compilation_scope.go +++ b/vendor/github.com/d5/tengo/compiler/compilation_scope.go @@ -5,8 +5,7 @@ import "github.com/d5/tengo/compiler/source" // CompilationScope represents a compiled instructions // and the last two instructions that were emitted. type CompilationScope struct { - instructions []byte - lastInstructions [2]EmittedInstruction - symbolInit map[string]bool - sourceMap map[int]source.Pos + instructions []byte + symbolInit map[string]bool + sourceMap map[int]source.Pos } diff --git a/vendor/github.com/d5/tengo/compiler/compiler.go b/vendor/github.com/d5/tengo/compiler/compiler.go index d8bc05fd..4a3ec3ad 100644 --- a/vendor/github.com/d5/tengo/compiler/compiler.go +++ b/vendor/github.com/d5/tengo/compiler/compiler.go @@ -3,7 +3,10 @@ package compiler import ( "fmt" "io" + "io/ioutil" + "path/filepath" "reflect" + "strings" "github.com/d5/tengo" "github.com/d5/tengo/compiler/ast" @@ -16,14 +19,14 @@ import ( type Compiler struct { file *source.File parent *Compiler - moduleName string + modulePath string constants []objects.Object symbolTable *SymbolTable scopes []CompilationScope scopeIndex int - moduleLoader ModuleLoader - builtinModules map[string]bool + modules *objects.ModuleMap compiledModules map[string]*objects.CompiledFunction + allowFileImport bool loops []*Loop loopIndex int trace io.Writer @@ -31,12 +34,7 @@ type Compiler struct { } // NewCompiler creates a Compiler. -// User can optionally provide the symbol table if one wants to add or remove -// some global- or builtin- scope symbols. If not (nil), Compile will create -// a new symbol table and use the default builtin functions. Likewise, standard -// modules can be explicitly provided if user wants to add or remove some modules. -// By default, Compile will use all the standard modules otherwise. -func NewCompiler(file *source.File, symbolTable *SymbolTable, constants []objects.Object, builtinModules map[string]bool, trace io.Writer) *Compiler { +func NewCompiler(file *source.File, symbolTable *SymbolTable, constants []objects.Object, modules *objects.ModuleMap, trace io.Writer) *Compiler { mainScope := CompilationScope{ symbolInit: make(map[string]bool), sourceMap: make(map[int]source.Pos), @@ -45,15 +43,16 @@ func NewCompiler(file *source.File, symbolTable *SymbolTable, constants []object // symbol table if symbolTable == nil { symbolTable = NewSymbolTable() + } - for idx, fn := range objects.Builtins { - symbolTable.DefineBuiltin(idx, fn.Name) - } + // add builtin functions to the symbol table + for idx, fn := range objects.Builtins { + symbolTable.DefineBuiltin(idx, fn.Name) } // builtin modules - if builtinModules == nil { - builtinModules = make(map[string]bool) + if modules == nil { + modules = objects.NewModuleMap() } return &Compiler{ @@ -64,7 +63,7 @@ func NewCompiler(file *source.File, symbolTable *SymbolTable, constants []object scopeIndex: 0, loopIndex: -1, trace: trace, - builtinModules: builtinModules, + modules: modules, compiledModules: make(map[string]*objects.CompiledFunction), } } @@ -120,7 +119,7 @@ func (c *Compiler) Compile(node ast.Node) error { return err } - c.emit(node, OpGreaterThan) + c.emit(node, OpBinaryOp, int(token.Greater)) return nil } else if node.Token == token.LessEq { @@ -131,7 +130,7 @@ func (c *Compiler) Compile(node ast.Node) error { return err } - c.emit(node, OpGreaterThanEqual) + c.emit(node, OpBinaryOp, int(token.GreaterEq)) return nil } @@ -145,35 +144,35 @@ func (c *Compiler) Compile(node ast.Node) error { switch node.Token { case token.Add: - c.emit(node, OpAdd) + c.emit(node, OpBinaryOp, int(token.Add)) case token.Sub: - c.emit(node, OpSub) + c.emit(node, OpBinaryOp, int(token.Sub)) case token.Mul: - c.emit(node, OpMul) + c.emit(node, OpBinaryOp, int(token.Mul)) case token.Quo: - c.emit(node, OpDiv) + c.emit(node, OpBinaryOp, int(token.Quo)) case token.Rem: - c.emit(node, OpRem) + c.emit(node, OpBinaryOp, int(token.Rem)) case token.Greater: - c.emit(node, OpGreaterThan) + c.emit(node, OpBinaryOp, int(token.Greater)) case token.GreaterEq: - c.emit(node, OpGreaterThanEqual) + c.emit(node, OpBinaryOp, int(token.GreaterEq)) case token.Equal: c.emit(node, OpEqual) case token.NotEqual: c.emit(node, OpNotEqual) case token.And: - c.emit(node, OpBAnd) + c.emit(node, OpBinaryOp, int(token.And)) case token.Or: - c.emit(node, OpBOr) + c.emit(node, OpBinaryOp, int(token.Or)) case token.Xor: - c.emit(node, OpBXor) + c.emit(node, OpBinaryOp, int(token.Xor)) case token.AndNot: - c.emit(node, OpBAndNot) + c.emit(node, OpBinaryOp, int(token.AndNot)) case token.Shl: - c.emit(node, OpBShiftLeft) + c.emit(node, OpBinaryOp, int(token.Shl)) case token.Shr: - c.emit(node, OpBShiftRight) + c.emit(node, OpBinaryOp, int(token.Shr)) default: return c.errorf(node, "invalid binary operator: %s", node.Token.String()) } @@ -293,6 +292,15 @@ func (c *Compiler) Compile(node ast.Node) error { } case *ast.BlockStmt: + if len(node.Stmts) == 0 { + return nil + } + + c.symbolTable = c.symbolTable.Fork(true) + defer func() { + c.symbolTable = c.symbolTable.Parent(false) + }() + for _, stmt := range node.Stmts { if err := c.Compile(stmt); err != nil { return err @@ -405,10 +413,8 @@ func (c *Compiler) Compile(node ast.Node) error { return err } - // add OpReturn if function returns nothing - if !c.lastInstructionIs(OpReturnValue) && !c.lastInstructionIs(OpReturn) { - c.emit(node, OpReturn) - } + // code optimization + c.optimizeFunc(node) freeSymbols := c.symbolTable.FreeSymbols() numLocals := c.symbolTable.MaxSymbols() @@ -461,9 +467,9 @@ func (c *Compiler) Compile(node ast.Node) error { s.LocalAssigned = true } - c.emit(node, OpGetLocal, s.Index) + c.emit(node, OpGetLocalPtr, s.Index) case ScopeFree: - c.emit(node, OpGetFree, s.Index) + c.emit(node, OpGetFreePtr, s.Index) } } @@ -487,13 +493,13 @@ func (c *Compiler) Compile(node ast.Node) error { } if node.Result == nil { - c.emit(node, OpReturn) + c.emit(node, OpReturn, 0) } else { if err := c.Compile(node.Result); err != nil { return err } - c.emit(node, OpReturnValue) + c.emit(node, OpReturn, 1) } case *ast.CallExpr: @@ -510,21 +516,57 @@ func (c *Compiler) Compile(node ast.Node) error { c.emit(node, OpCall, len(node.Args)) case *ast.ImportExpr: - if c.builtinModules[node.ModuleName] { - if len(node.ModuleName) > tengo.MaxStringLen { - return c.error(node, objects.ErrStringLimit) + if node.ModuleName == "" { + return c.errorf(node, "empty module name") + } + + if mod := c.modules.Get(node.ModuleName); mod != nil { + v, err := mod.Import(node.ModuleName) + if err != nil { + return err } - c.emit(node, OpConstant, c.addConstant(&objects.String{Value: node.ModuleName})) - c.emit(node, OpGetBuiltinModule) - } else { - userMod, err := c.compileModule(node) + switch v := v.(type) { + case []byte: // module written in Tengo + compiled, err := c.compileModule(node, node.ModuleName, node.ModuleName, v) + if err != nil { + return err + } + c.emit(node, OpConstant, c.addConstant(compiled)) + c.emit(node, OpCall, 0) + case objects.Object: // builtin module + c.emit(node, OpConstant, c.addConstant(v)) + default: + panic(fmt.Errorf("invalid import value type: %T", v)) + } + } else if c.allowFileImport { + moduleName := node.ModuleName + if !strings.HasSuffix(moduleName, ".tengo") { + moduleName += ".tengo" + } + + modulePath, err := filepath.Abs(moduleName) if err != nil { + return c.errorf(node, "module file path error: %s", err.Error()) + } + + if err := c.checkCyclicImports(node, modulePath); err != nil { return err } - c.emit(node, OpConstant, c.addConstant(userMod)) + moduleSrc, err := ioutil.ReadFile(moduleName) + if err != nil { + return c.errorf(node, "module file read error: %s", err.Error()) + } + + compiled, err := c.compileModule(node, moduleName, modulePath, moduleSrc) + if err != nil { + return err + } + c.emit(node, OpConstant, c.addConstant(compiled)) c.emit(node, OpCall, 0) + } else { + return c.errorf(node, "module '%s' not found", node.ModuleName) } case *ast.ExportStmt: @@ -543,7 +585,7 @@ func (c *Compiler) Compile(node ast.Node) error { } c.emit(node, OpImmutable) - c.emit(node, OpReturnValue) + c.emit(node, OpReturn, 1) case *ast.ErrorExpr: if err := c.Compile(node.Expr); err != nil { @@ -602,18 +644,16 @@ func (c *Compiler) Bytecode() *Bytecode { } } -// SetModuleLoader sets or replaces the current module loader. -// Note that the module loader is used for user modules, -// not for the standard modules. -func (c *Compiler) SetModuleLoader(moduleLoader ModuleLoader) { - c.moduleLoader = moduleLoader +// EnableFileImport enables or disables module loading from local files. +// Local file modules are disabled by default. +func (c *Compiler) EnableFileImport(enable bool) { + c.allowFileImport = enable } -func (c *Compiler) fork(file *source.File, moduleName string, symbolTable *SymbolTable) *Compiler { - child := NewCompiler(file, symbolTable, nil, c.builtinModules, c.trace) - child.moduleName = moduleName // name of the module to compile - child.parent = c // parent to set to current compiler - child.moduleLoader = c.moduleLoader // share module loader +func (c *Compiler) fork(file *source.File, modulePath string, symbolTable *SymbolTable) *Compiler { + child := NewCompiler(file, symbolTable, nil, c.modules, c.trace) + child.modulePath = modulePath // module file path + child.parent = c // parent to set to current compiler return child } @@ -657,33 +697,6 @@ func (c *Compiler) addInstruction(b []byte) int { return posNewIns } -func (c *Compiler) setLastInstruction(op Opcode, pos int) { - c.scopes[c.scopeIndex].lastInstructions[1] = c.scopes[c.scopeIndex].lastInstructions[0] - - c.scopes[c.scopeIndex].lastInstructions[0].Opcode = op - c.scopes[c.scopeIndex].lastInstructions[0].Position = pos -} - -func (c *Compiler) lastInstructionIs(op Opcode) bool { - if len(c.currentInstructions()) == 0 { - return false - } - - return c.scopes[c.scopeIndex].lastInstructions[0].Opcode == op -} - -func (c *Compiler) removeLastInstruction() { - lastPos := c.scopes[c.scopeIndex].lastInstructions[0].Position - - if c.trace != nil { - c.printTrace(fmt.Sprintf("DELET %s", - FormatInstructions(c.scopes[c.scopeIndex].instructions[lastPos:], lastPos)[0])) - } - - c.scopes[c.scopeIndex].instructions = c.currentInstructions()[:lastPos] - c.scopes[c.scopeIndex].lastInstructions[0] = c.scopes[c.scopeIndex].lastInstructions[1] -} - func (c *Compiler) replaceInstruction(pos int, inst []byte) { copy(c.currentInstructions()[pos:], inst) @@ -700,6 +713,92 @@ func (c *Compiler) changeOperand(opPos int, operand ...int) { c.replaceInstruction(opPos, inst) } +// optimizeFunc performs some code-level optimization for the current function instructions +// it removes unreachable (dead code) instructions and adds "returns" instruction if needed. +func (c *Compiler) optimizeFunc(node ast.Node) { + // any instructions between RETURN and the function end + // or instructions between RETURN and jump target position + // are considered as unreachable. + + // pass 1. identify all jump destinations + dsts := make(map[int]bool) + iterateInstructions(c.scopes[c.scopeIndex].instructions, func(pos int, opcode Opcode, operands []int) bool { + switch opcode { + case OpJump, OpJumpFalsy, OpAndJump, OpOrJump: + dsts[operands[0]] = true + } + + return true + }) + + var newInsts []byte + + // pass 2. eliminate dead code + posMap := make(map[int]int) // old position to new position + var dstIdx int + var deadCode bool + iterateInstructions(c.scopes[c.scopeIndex].instructions, func(pos int, opcode Opcode, operands []int) bool { + switch { + case opcode == OpReturn: + if deadCode { + return true + } + deadCode = true + case dsts[pos]: + dstIdx++ + deadCode = false + case deadCode: + return true + } + + posMap[pos] = len(newInsts) + newInsts = append(newInsts, MakeInstruction(opcode, operands...)...) + return true + }) + + // pass 3. update jump positions + var lastOp Opcode + var appendReturn bool + endPos := len(c.scopes[c.scopeIndex].instructions) + iterateInstructions(newInsts, func(pos int, opcode Opcode, operands []int) bool { + switch opcode { + case OpJump, OpJumpFalsy, OpAndJump, OpOrJump: + newDst, ok := posMap[operands[0]] + if ok { + copy(newInsts[pos:], MakeInstruction(opcode, newDst)) + } else if endPos == operands[0] { + // there's a jump instruction that jumps to the end of function + // compiler should append "return". + appendReturn = true + } else { + panic(fmt.Errorf("invalid jump position: %d", newDst)) + } + } + lastOp = opcode + return true + }) + if lastOp != OpReturn { + appendReturn = true + } + + // pass 4. update source map + newSourceMap := make(map[int]source.Pos) + for pos, srcPos := range c.scopes[c.scopeIndex].sourceMap { + newPos, ok := posMap[pos] + if ok { + newSourceMap[newPos] = srcPos + } + } + + c.scopes[c.scopeIndex].instructions = newInsts + c.scopes[c.scopeIndex].sourceMap = newSourceMap + + // append "return" + if appendReturn { + c.emit(node, OpReturn, 0) + } +} + func (c *Compiler) emit(node ast.Node, opcode Opcode, operands ...int) int { filePos := source.NoPos if node != nil { @@ -709,7 +808,6 @@ func (c *Compiler) emit(node ast.Node, opcode Opcode, operands ...int) int { inst := MakeInstruction(opcode, operands...) pos := c.addInstruction(inst) c.scopes[c.scopeIndex].sourceMap[pos] = filePos - c.setLastInstruction(opcode, pos) if c.trace != nil { c.printTrace(fmt.Sprintf("EMIT %s", diff --git a/vendor/github.com/d5/tengo/compiler/compiler_assign.go b/vendor/github.com/d5/tengo/compiler/compiler_assign.go index 0e086c83..59296f6f 100644 --- a/vendor/github.com/d5/tengo/compiler/compiler_assign.go +++ b/vendor/github.com/d5/tengo/compiler/compiler_assign.go @@ -51,27 +51,27 @@ func (c *Compiler) compileAssign(node ast.Node, lhs, rhs []ast.Expr, op token.To switch op { case token.AddAssign: - c.emit(node, OpAdd) + c.emit(node, OpBinaryOp, int(token.Add)) case token.SubAssign: - c.emit(node, OpSub) + c.emit(node, OpBinaryOp, int(token.Sub)) case token.MulAssign: - c.emit(node, OpMul) + c.emit(node, OpBinaryOp, int(token.Mul)) case token.QuoAssign: - c.emit(node, OpDiv) + c.emit(node, OpBinaryOp, int(token.Quo)) case token.RemAssign: - c.emit(node, OpRem) + c.emit(node, OpBinaryOp, int(token.Rem)) case token.AndAssign: - c.emit(node, OpBAnd) + c.emit(node, OpBinaryOp, int(token.And)) case token.OrAssign: - c.emit(node, OpBOr) + c.emit(node, OpBinaryOp, int(token.Or)) case token.AndNotAssign: - c.emit(node, OpBAndNot) + c.emit(node, OpBinaryOp, int(token.AndNot)) case token.XorAssign: - c.emit(node, OpBXor) + c.emit(node, OpBinaryOp, int(token.Xor)) case token.ShlAssign: - c.emit(node, OpBShiftLeft) + c.emit(node, OpBinaryOp, int(token.Shl)) case token.ShrAssign: - c.emit(node, OpBShiftRight) + c.emit(node, OpBinaryOp, int(token.Shr)) } // compile selector expressions (right to left) diff --git a/vendor/github.com/d5/tengo/compiler/compiler_module.go b/vendor/github.com/d5/tengo/compiler/compiler_module.go index d069bfab..8a3671ce 100644 --- a/vendor/github.com/d5/tengo/compiler/compiler_module.go +++ b/vendor/github.com/d5/tengo/compiler/compiler_module.go @@ -1,72 +1,31 @@ package compiler import ( - "io/ioutil" - "strings" - "github.com/d5/tengo/compiler/ast" "github.com/d5/tengo/compiler/parser" "github.com/d5/tengo/objects" ) -func (c *Compiler) compileModule(expr *ast.ImportExpr) (*objects.CompiledFunction, error) { - compiledModule, exists := c.loadCompiledModule(expr.ModuleName) - if exists { - return compiledModule, nil +func (c *Compiler) checkCyclicImports(node ast.Node, modulePath string) error { + if c.modulePath == modulePath { + return c.errorf(node, "cyclic module import: %s", modulePath) + } else if c.parent != nil { + return c.parent.checkCyclicImports(node, modulePath) } - moduleName := expr.ModuleName - - // read module source from loader - var moduleSrc []byte - if c.moduleLoader == nil { - // default loader: read from local file - if !strings.HasSuffix(moduleName, ".tengo") { - moduleName += ".tengo" - } - - if err := c.checkCyclicImports(expr, moduleName); err != nil { - return nil, err - } - - var err error - moduleSrc, err = ioutil.ReadFile(moduleName) - if err != nil { - return nil, c.errorf(expr, "module file read error: %s", err.Error()) - } - } else { - if err := c.checkCyclicImports(expr, moduleName); err != nil { - return nil, err - } - - var err error - moduleSrc, err = c.moduleLoader(moduleName) - if err != nil { - return nil, err - } - } + return nil +} - compiledModule, err := c.doCompileModule(moduleName, moduleSrc) - if err != nil { +func (c *Compiler) compileModule(node ast.Node, moduleName, modulePath string, src []byte) (*objects.CompiledFunction, error) { + if err := c.checkCyclicImports(node, modulePath); err != nil { return nil, err } - c.storeCompiledModule(moduleName, compiledModule) - - return compiledModule, nil -} - -func (c *Compiler) checkCyclicImports(node ast.Node, moduleName string) error { - if c.moduleName == moduleName { - return c.errorf(node, "cyclic module import: %s", moduleName) - } else if c.parent != nil { - return c.parent.checkCyclicImports(node, moduleName) + compiledModule, exists := c.loadCompiledModule(modulePath) + if exists { + return compiledModule, nil } - return nil -} - -func (c *Compiler) doCompileModule(moduleName string, src []byte) (*objects.CompiledFunction, error) { modFile := c.file.Set().AddFile(moduleName, -1, len(src)) p := parser.NewParser(modFile, src, nil) file, err := p.ParseFile() @@ -85,36 +44,36 @@ func (c *Compiler) doCompileModule(moduleName string, src []byte) (*objects.Comp symbolTable = symbolTable.Fork(false) // compile module - moduleCompiler := c.fork(modFile, moduleName, symbolTable) + moduleCompiler := c.fork(modFile, modulePath, symbolTable) if err := moduleCompiler.Compile(file); err != nil { return nil, err } - // add OpReturn (== export undefined) if export is missing - if !moduleCompiler.lastInstructionIs(OpReturnValue) { - moduleCompiler.emit(nil, OpReturn) - } + // code optimization + moduleCompiler.optimizeFunc(node) compiledFunc := moduleCompiler.Bytecode().MainFunction compiledFunc.NumLocals = symbolTable.MaxSymbols() + c.storeCompiledModule(modulePath, compiledFunc) + return compiledFunc, nil } -func (c *Compiler) loadCompiledModule(moduleName string) (mod *objects.CompiledFunction, ok bool) { +func (c *Compiler) loadCompiledModule(modulePath string) (mod *objects.CompiledFunction, ok bool) { if c.parent != nil { - return c.parent.loadCompiledModule(moduleName) + return c.parent.loadCompiledModule(modulePath) } - mod, ok = c.compiledModules[moduleName] + mod, ok = c.compiledModules[modulePath] return } -func (c *Compiler) storeCompiledModule(moduleName string, module *objects.CompiledFunction) { +func (c *Compiler) storeCompiledModule(modulePath string, module *objects.CompiledFunction) { if c.parent != nil { - c.parent.storeCompiledModule(moduleName, module) + c.parent.storeCompiledModule(modulePath, module) } - c.compiledModules[moduleName] = module + c.compiledModules[modulePath] = module } diff --git a/vendor/github.com/d5/tengo/compiler/instructions.go b/vendor/github.com/d5/tengo/compiler/instructions.go index b04b2826..80c88d13 100644 --- a/vendor/github.com/d5/tengo/compiler/instructions.go +++ b/vendor/github.com/d5/tengo/compiler/instructions.go @@ -57,3 +57,16 @@ func FormatInstructions(b []byte, posOffset int) []string { return out } + +func iterateInstructions(b []byte, fn func(pos int, opcode Opcode, operands []int) bool) { + for i := 0; i < len(b); i++ { + numOperands := OpcodeOperands[Opcode(b[i])] + operands, read := ReadOperands(numOperands, b[i+1:]) + + if !fn(i, b[i], operands) { + break + } + + i += read + } +} diff --git a/vendor/github.com/d5/tengo/compiler/opcodes.go b/vendor/github.com/d5/tengo/compiler/opcodes.go index d4cf1ba2..d832ee17 100644 --- a/vendor/github.com/d5/tengo/compiler/opcodes.go +++ b/vendor/github.com/d5/tengo/compiler/opcodes.go @@ -5,173 +5,137 @@ type Opcode = byte // List of opcodes const ( - OpConstant Opcode = iota // Load constant - OpAdd // Add - OpSub // Sub - OpMul // Multiply - OpDiv // Divide - OpRem // Remainder - OpBAnd // bitwise AND - OpBOr // bitwise OR - OpBXor // bitwise XOR - OpBShiftLeft // bitwise shift left - OpBShiftRight // bitwise shift right - OpBAndNot // bitwise AND NOT - OpBComplement // bitwise complement - OpPop // Pop - OpTrue // Push true - OpFalse // Push false - OpEqual // Equal == - OpNotEqual // Not equal != - OpGreaterThan // Greater than >= - OpGreaterThanEqual // Greater than or equal to >= - OpMinus // Minus - - OpLNot // Logical not ! - OpJumpFalsy // Jump if falsy - OpAndJump // Logical AND jump - OpOrJump // Logical OR jump - OpJump // Jump - OpNull // Push null - OpArray // Array object - OpMap // Map object - OpError // Error object - OpImmutable // Immutable object - OpIndex // Index operation - OpSliceIndex // Slice operation - OpCall // Call function - OpReturn // Return - OpReturnValue // Return value - OpGetGlobal // Get global variable - OpSetGlobal // Set global variable - OpSetSelGlobal // Set global variable using selectors - OpGetLocal // Get local variable - OpSetLocal // Set local variable - OpDefineLocal // Define local variable - OpSetSelLocal // Set local variable using selectors - OpGetFree // Get free variables - OpSetFree // Set free variables - OpSetSelFree // Set free variables using selectors - OpGetBuiltin // Get builtin function - OpGetBuiltinModule // Get builtin module - OpClosure // Push closure - OpIteratorInit // Iterator init - OpIteratorNext // Iterator next - OpIteratorKey // Iterator key - OpIteratorValue // Iterator value + OpConstant Opcode = iota // Load constant + OpBComplement // bitwise complement + OpPop // Pop + OpTrue // Push true + OpFalse // Push false + OpEqual // Equal == + OpNotEqual // Not equal != + OpMinus // Minus - + OpLNot // Logical not ! + OpJumpFalsy // Jump if falsy + OpAndJump // Logical AND jump + OpOrJump // Logical OR jump + OpJump // Jump + OpNull // Push null + OpArray // Array object + OpMap // Map object + OpError // Error object + OpImmutable // Immutable object + OpIndex // Index operation + OpSliceIndex // Slice operation + OpCall // Call function + OpReturn // Return + OpGetGlobal // Get global variable + OpSetGlobal // Set global variable + OpSetSelGlobal // Set global variable using selectors + OpGetLocal // Get local variable + OpSetLocal // Set local variable + OpDefineLocal // Define local variable + OpSetSelLocal // Set local variable using selectors + OpGetFreePtr // Get free variable pointer object + OpGetFree // Get free variables + OpSetFree // Set free variables + OpGetLocalPtr // Get local variable as a pointer + OpSetSelFree // Set free variables using selectors + OpGetBuiltin // Get builtin function + OpClosure // Push closure + OpIteratorInit // Iterator init + OpIteratorNext // Iterator next + OpIteratorKey // Iterator key + OpIteratorValue // Iterator value + OpBinaryOp // Binary Operation ) // OpcodeNames is opcode names. var OpcodeNames = [...]string{ - OpConstant: "CONST", - OpPop: "POP", - OpTrue: "TRUE", - OpFalse: "FALSE", - OpAdd: "ADD", - OpSub: "SUB", - OpMul: "MUL", - OpDiv: "DIV", - OpRem: "REM", - OpBAnd: "AND", - OpBOr: "OR", - OpBXor: "XOR", - OpBAndNot: "ANDN", - OpBShiftLeft: "SHL", - OpBShiftRight: "SHR", - OpBComplement: "NEG", - OpEqual: "EQL", - OpNotEqual: "NEQ", - OpGreaterThan: "GTR", - OpGreaterThanEqual: "GEQ", - OpMinus: "NEG", - OpLNot: "NOT", - OpJumpFalsy: "JMPF", - OpAndJump: "ANDJMP", - OpOrJump: "ORJMP", - OpJump: "JMP", - OpNull: "NULL", - OpGetGlobal: "GETG", - OpSetGlobal: "SETG", - OpSetSelGlobal: "SETSG", - OpArray: "ARR", - OpMap: "MAP", - OpError: "ERROR", - OpImmutable: "IMMUT", - OpIndex: "INDEX", - OpSliceIndex: "SLICE", - OpCall: "CALL", - OpReturn: "RET", - OpReturnValue: "RETVAL", - OpGetLocal: "GETL", - OpSetLocal: "SETL", - OpDefineLocal: "DEFL", - OpSetSelLocal: "SETSL", - OpGetBuiltin: "BUILTIN", - OpGetBuiltinModule: "BLTMOD", - OpClosure: "CLOSURE", - OpGetFree: "GETF", - OpSetFree: "SETF", - OpSetSelFree: "SETSF", - OpIteratorInit: "ITER", - OpIteratorNext: "ITNXT", - OpIteratorKey: "ITKEY", - OpIteratorValue: "ITVAL", + OpConstant: "CONST", + OpPop: "POP", + OpTrue: "TRUE", + OpFalse: "FALSE", + OpBComplement: "NEG", + OpEqual: "EQL", + OpNotEqual: "NEQ", + OpMinus: "NEG", + OpLNot: "NOT", + OpJumpFalsy: "JMPF", + OpAndJump: "ANDJMP", + OpOrJump: "ORJMP", + OpJump: "JMP", + OpNull: "NULL", + OpGetGlobal: "GETG", + OpSetGlobal: "SETG", + OpSetSelGlobal: "SETSG", + OpArray: "ARR", + OpMap: "MAP", + OpError: "ERROR", + OpImmutable: "IMMUT", + OpIndex: "INDEX", + OpSliceIndex: "SLICE", + OpCall: "CALL", + OpReturn: "RET", + OpGetLocal: "GETL", + OpSetLocal: "SETL", + OpDefineLocal: "DEFL", + OpSetSelLocal: "SETSL", + OpGetBuiltin: "BUILTIN", + OpClosure: "CLOSURE", + OpGetFreePtr: "GETFP", + OpGetFree: "GETF", + OpSetFree: "SETF", + OpGetLocalPtr: "GETLP", + OpSetSelFree: "SETSF", + OpIteratorInit: "ITER", + OpIteratorNext: "ITNXT", + OpIteratorKey: "ITKEY", + OpIteratorValue: "ITVAL", + OpBinaryOp: "BINARYOP", } // OpcodeOperands is the number of operands. var OpcodeOperands = [...][]int{ - OpConstant: {2}, - OpPop: {}, - OpTrue: {}, - OpFalse: {}, - OpAdd: {}, - OpSub: {}, - OpMul: {}, - OpDiv: {}, - OpRem: {}, - OpBAnd: {}, - OpBOr: {}, - OpBXor: {}, - OpBAndNot: {}, - OpBShiftLeft: {}, - OpBShiftRight: {}, - OpBComplement: {}, - OpEqual: {}, - OpNotEqual: {}, - OpGreaterThan: {}, - OpGreaterThanEqual: {}, - OpMinus: {}, - OpLNot: {}, - OpJumpFalsy: {2}, - OpAndJump: {2}, - OpOrJump: {2}, - OpJump: {2}, - OpNull: {}, - OpGetGlobal: {2}, - OpSetGlobal: {2}, - OpSetSelGlobal: {2, 1}, - OpArray: {2}, - OpMap: {2}, - OpError: {}, - OpImmutable: {}, - OpIndex: {}, - OpSliceIndex: {}, - OpCall: {1}, - OpReturn: {}, - OpReturnValue: {}, - OpGetLocal: {1}, - OpSetLocal: {1}, - OpDefineLocal: {1}, - OpSetSelLocal: {1, 1}, - OpGetBuiltin: {1}, - OpGetBuiltinModule: {}, - OpClosure: {2, 1}, - OpGetFree: {1}, - OpSetFree: {1}, - OpSetSelFree: {1, 1}, - OpIteratorInit: {}, - OpIteratorNext: {}, - OpIteratorKey: {}, - OpIteratorValue: {}, + OpConstant: {2}, + OpPop: {}, + OpTrue: {}, + OpFalse: {}, + OpBComplement: {}, + OpEqual: {}, + OpNotEqual: {}, + OpMinus: {}, + OpLNot: {}, + OpJumpFalsy: {2}, + OpAndJump: {2}, + OpOrJump: {2}, + OpJump: {2}, + OpNull: {}, + OpGetGlobal: {2}, + OpSetGlobal: {2}, + OpSetSelGlobal: {2, 1}, + OpArray: {2}, + OpMap: {2}, + OpError: {}, + OpImmutable: {}, + OpIndex: {}, + OpSliceIndex: {}, + OpCall: {1}, + OpReturn: {1}, + OpGetLocal: {1}, + OpSetLocal: {1}, + OpDefineLocal: {1}, + OpSetSelLocal: {1, 1}, + OpGetBuiltin: {1}, + OpClosure: {2, 1}, + OpGetFreePtr: {1}, + OpGetFree: {1}, + OpSetFree: {1}, + OpGetLocalPtr: {1}, + OpSetSelFree: {1, 1}, + OpIteratorInit: {}, + OpIteratorNext: {}, + OpIteratorKey: {}, + OpIteratorValue: {}, + OpBinaryOp: {1}, } // ReadOperands reads operands from the bytecode. diff --git a/vendor/github.com/d5/tengo/compiler/symbol_table.go b/vendor/github.com/d5/tengo/compiler/symbol_table.go index fb029b31..94c868de 100644 --- a/vendor/github.com/d5/tengo/compiler/symbol_table.go +++ b/vendor/github.com/d5/tengo/compiler/symbol_table.go @@ -64,9 +64,7 @@ func (t *SymbolTable) Resolve(name string) (symbol *Symbol, depth int, ok bool) return } - if !t.block { - depth++ - } + depth++ // if symbol is defined in parent table and if it's not global/builtin // then it's free variable. -- cgit v1.2.3