summaryrefslogtreecommitdiffstats
path: root/vendor/github.com/d5/tengo/compiler/compiler.go
diff options
context:
space:
mode:
authorWim <wim@42.be>2020-01-09 21:52:19 +0100
committerGitHub <noreply@github.com>2020-01-09 21:52:19 +0100
commit9d84d6dd643c4017074e81465671cd9b25f9539a (patch)
tree8a767f91d655a6cf21d476e4fb7aa6fd8a952df8 /vendor/github.com/d5/tengo/compiler/compiler.go
parent0f708daf2d14dcca261ef98cc698a1b1f2a6aa74 (diff)
downloadmatterbridge-msglm-9d84d6dd643c4017074e81465671cd9b25f9539a.tar.gz
matterbridge-msglm-9d84d6dd643c4017074e81465671cd9b25f9539a.tar.bz2
matterbridge-msglm-9d84d6dd643c4017074e81465671cd9b25f9539a.zip
Update to tengo v2 (#976)
Diffstat (limited to 'vendor/github.com/d5/tengo/compiler/compiler.go')
-rw-r--r--vendor/github.com/d5/tengo/compiler/compiler.go846
1 files changed, 0 insertions, 846 deletions
diff --git a/vendor/github.com/d5/tengo/compiler/compiler.go b/vendor/github.com/d5/tengo/compiler/compiler.go
deleted file mode 100644
index 8bde5dc9..00000000
--- a/vendor/github.com/d5/tengo/compiler/compiler.go
+++ /dev/null
@@ -1,846 +0,0 @@
-package compiler
-
-import (
- "fmt"
- "io"
- "io/ioutil"
- "path/filepath"
- "reflect"
- "strings"
-
- "github.com/d5/tengo"
- "github.com/d5/tengo/compiler/ast"
- "github.com/d5/tengo/compiler/source"
- "github.com/d5/tengo/compiler/token"
- "github.com/d5/tengo/objects"
-)
-
-// Compiler compiles the AST into a bytecode.
-type Compiler struct {
- file *source.File
- parent *Compiler
- modulePath string
- constants []objects.Object
- symbolTable *SymbolTable
- scopes []CompilationScope
- scopeIndex int
- modules *objects.ModuleMap
- compiledModules map[string]*objects.CompiledFunction
- allowFileImport bool
- loops []*Loop
- loopIndex int
- trace io.Writer
- indent int
-}
-
-// NewCompiler creates a 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),
- }
-
- // symbol table
- if symbolTable == nil {
- symbolTable = NewSymbolTable()
- }
-
- // add builtin functions to the symbol table
- for idx, fn := range objects.Builtins {
- symbolTable.DefineBuiltin(idx, fn.Name)
- }
-
- // builtin modules
- if modules == nil {
- modules = objects.NewModuleMap()
- }
-
- return &Compiler{
- file: file,
- symbolTable: symbolTable,
- constants: constants,
- scopes: []CompilationScope{mainScope},
- scopeIndex: 0,
- loopIndex: -1,
- trace: trace,
- modules: modules,
- compiledModules: make(map[string]*objects.CompiledFunction),
- }
-}
-
-// Compile compiles the AST node.
-func (c *Compiler) Compile(node ast.Node) error {
- if c.trace != nil {
- if node != nil {
- defer un(trace(c, fmt.Sprintf("%s (%s)", node.String(), reflect.TypeOf(node).Elem().Name())))
- } else {
- defer un(trace(c, "<nil>"))
- }
- }
-
- switch node := node.(type) {
- case *ast.File:
- for _, stmt := range node.Stmts {
- if err := c.Compile(stmt); err != nil {
- return err
- }
- }
-
- case *ast.ExprStmt:
- if err := c.Compile(node.Expr); err != nil {
- return err
- }
- c.emit(node, OpPop)
-
- case *ast.IncDecStmt:
- op := token.AddAssign
- if node.Token == token.Dec {
- op = token.SubAssign
- }
-
- return c.compileAssign(node, []ast.Expr{node.Expr}, []ast.Expr{&ast.IntLit{Value: 1}}, op)
-
- case *ast.ParenExpr:
- if err := c.Compile(node.Expr); err != nil {
- return err
- }
-
- case *ast.BinaryExpr:
- if node.Token == token.LAnd || node.Token == token.LOr {
- return c.compileLogical(node)
- }
-
- if node.Token == token.Less {
- if err := c.Compile(node.RHS); err != nil {
- return err
- }
-
- if err := c.Compile(node.LHS); err != nil {
- return err
- }
-
- c.emit(node, OpBinaryOp, int(token.Greater))
-
- return nil
- } else if node.Token == token.LessEq {
- if err := c.Compile(node.RHS); err != nil {
- return err
- }
- if err := c.Compile(node.LHS); err != nil {
- return err
- }
-
- c.emit(node, OpBinaryOp, int(token.GreaterEq))
-
- return nil
- }
-
- if err := c.Compile(node.LHS); err != nil {
- return err
- }
- if err := c.Compile(node.RHS); err != nil {
- return err
- }
-
- switch node.Token {
- case token.Add:
- c.emit(node, OpBinaryOp, int(token.Add))
- case token.Sub:
- c.emit(node, OpBinaryOp, int(token.Sub))
- case token.Mul:
- c.emit(node, OpBinaryOp, int(token.Mul))
- case token.Quo:
- c.emit(node, OpBinaryOp, int(token.Quo))
- case token.Rem:
- c.emit(node, OpBinaryOp, int(token.Rem))
- case token.Greater:
- c.emit(node, OpBinaryOp, int(token.Greater))
- case token.GreaterEq:
- 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, OpBinaryOp, int(token.And))
- case token.Or:
- c.emit(node, OpBinaryOp, int(token.Or))
- case token.Xor:
- c.emit(node, OpBinaryOp, int(token.Xor))
- case token.AndNot:
- c.emit(node, OpBinaryOp, int(token.AndNot))
- case token.Shl:
- c.emit(node, OpBinaryOp, int(token.Shl))
- case token.Shr:
- c.emit(node, OpBinaryOp, int(token.Shr))
- default:
- return c.errorf(node, "invalid binary operator: %s", node.Token.String())
- }
-
- case *ast.IntLit:
- c.emit(node, OpConstant, c.addConstant(&objects.Int{Value: node.Value}))
-
- case *ast.FloatLit:
- c.emit(node, OpConstant, c.addConstant(&objects.Float{Value: node.Value}))
-
- case *ast.BoolLit:
- if node.Value {
- c.emit(node, OpTrue)
- } else {
- c.emit(node, OpFalse)
- }
-
- case *ast.StringLit:
- if len(node.Value) > tengo.MaxStringLen {
- return c.error(node, objects.ErrStringLimit)
- }
-
- c.emit(node, OpConstant, c.addConstant(&objects.String{Value: node.Value}))
-
- case *ast.CharLit:
- c.emit(node, OpConstant, c.addConstant(&objects.Char{Value: node.Value}))
-
- case *ast.UndefinedLit:
- c.emit(node, OpNull)
-
- case *ast.UnaryExpr:
- if err := c.Compile(node.Expr); err != nil {
- return err
- }
-
- switch node.Token {
- case token.Not:
- c.emit(node, OpLNot)
- case token.Sub:
- c.emit(node, OpMinus)
- case token.Xor:
- c.emit(node, OpBComplement)
- case token.Add:
- // do nothing?
- default:
- return c.errorf(node, "invalid unary operator: %s", node.Token.String())
- }
-
- case *ast.IfStmt:
- // open new symbol table for the statement
- c.symbolTable = c.symbolTable.Fork(true)
- defer func() {
- c.symbolTable = c.symbolTable.Parent(false)
- }()
-
- if node.Init != nil {
- if err := c.Compile(node.Init); err != nil {
- return err
- }
- }
-
- if err := c.Compile(node.Cond); err != nil {
- return err
- }
-
- // first jump placeholder
- jumpPos1 := c.emit(node, OpJumpFalsy, 0)
-
- if err := c.Compile(node.Body); err != nil {
- return err
- }
-
- if node.Else != nil {
- // second jump placeholder
- jumpPos2 := c.emit(node, OpJump, 0)
-
- // update first jump offset
- curPos := len(c.currentInstructions())
- c.changeOperand(jumpPos1, curPos)
-
- if err := c.Compile(node.Else); err != nil {
- return err
- }
-
- // update second jump offset
- curPos = len(c.currentInstructions())
- c.changeOperand(jumpPos2, curPos)
- } else {
- // update first jump offset
- curPos := len(c.currentInstructions())
- c.changeOperand(jumpPos1, curPos)
- }
-
- case *ast.ForStmt:
- return c.compileForStmt(node)
-
- case *ast.ForInStmt:
- return c.compileForInStmt(node)
-
- case *ast.BranchStmt:
- if node.Token == token.Break {
- curLoop := c.currentLoop()
- if curLoop == nil {
- return c.errorf(node, "break not allowed outside loop")
- }
- pos := c.emit(node, OpJump, 0)
- curLoop.Breaks = append(curLoop.Breaks, pos)
- } else if node.Token == token.Continue {
- curLoop := c.currentLoop()
- if curLoop == nil {
- return c.errorf(node, "continue not allowed outside loop")
- }
- pos := c.emit(node, OpJump, 0)
- curLoop.Continues = append(curLoop.Continues, pos)
- } else {
- panic(fmt.Errorf("invalid branch statement: %s", node.Token.String()))
- }
-
- 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
- }
- }
-
- case *ast.AssignStmt:
- if err := c.compileAssign(node, node.LHS, node.RHS, node.Token); err != nil {
- return err
- }
-
- case *ast.Ident:
- symbol, _, ok := c.symbolTable.Resolve(node.Name)
- if !ok {
- return c.errorf(node, "unresolved reference '%s'", node.Name)
- }
-
- switch symbol.Scope {
- case ScopeGlobal:
- c.emit(node, OpGetGlobal, symbol.Index)
- case ScopeLocal:
- c.emit(node, OpGetLocal, symbol.Index)
- case ScopeBuiltin:
- c.emit(node, OpGetBuiltin, symbol.Index)
- case ScopeFree:
- c.emit(node, OpGetFree, symbol.Index)
- }
-
- case *ast.ArrayLit:
- for _, elem := range node.Elements {
- if err := c.Compile(elem); err != nil {
- return err
- }
- }
-
- c.emit(node, OpArray, len(node.Elements))
-
- case *ast.MapLit:
- for _, elt := range node.Elements {
- // key
- if len(elt.Key) > tengo.MaxStringLen {
- return c.error(node, objects.ErrStringLimit)
- }
- c.emit(node, OpConstant, c.addConstant(&objects.String{Value: elt.Key}))
-
- // value
- if err := c.Compile(elt.Value); err != nil {
- return err
- }
- }
-
- c.emit(node, OpMap, len(node.Elements)*2)
-
- case *ast.SelectorExpr: // selector on RHS side
- if err := c.Compile(node.Expr); err != nil {
- return err
- }
-
- if err := c.Compile(node.Sel); err != nil {
- return err
- }
-
- c.emit(node, OpIndex)
-
- case *ast.IndexExpr:
- if err := c.Compile(node.Expr); err != nil {
- return err
- }
-
- if err := c.Compile(node.Index); err != nil {
- return err
- }
-
- c.emit(node, OpIndex)
-
- case *ast.SliceExpr:
- if err := c.Compile(node.Expr); err != nil {
- return err
- }
-
- if node.Low != nil {
- if err := c.Compile(node.Low); err != nil {
- return err
- }
- } else {
- c.emit(node, OpNull)
- }
-
- if node.High != nil {
- if err := c.Compile(node.High); err != nil {
- return err
- }
- } else {
- c.emit(node, OpNull)
- }
-
- c.emit(node, OpSliceIndex)
-
- case *ast.FuncLit:
- c.enterScope()
-
- for _, p := range node.Type.Params.List {
- s := c.symbolTable.Define(p.Name)
-
- // function arguments is not assigned directly.
- s.LocalAssigned = true
- }
-
- if err := c.Compile(node.Body); err != nil {
- return err
- }
-
- // code optimization
- c.optimizeFunc(node)
-
- freeSymbols := c.symbolTable.FreeSymbols()
- numLocals := c.symbolTable.MaxSymbols()
- instructions, sourceMap := c.leaveScope()
-
- for _, s := range freeSymbols {
- switch s.Scope {
- case ScopeLocal:
- if !s.LocalAssigned {
- // Here, the closure is capturing a local variable that's not yet assigned its value.
- // One example is a local recursive function:
- //
- // func() {
- // foo := func(x) {
- // // ..
- // return foo(x-1)
- // }
- // }
- //
- // which translate into
- //
- // 0000 GETL 0
- // 0002 CLOSURE ? 1
- // 0006 DEFL 0
- //
- // . So the local variable (0) is being captured before it's assigned the value.
- //
- // Solution is to transform the code into something like this:
- //
- // func() {
- // foo := undefined
- // foo = func(x) {
- // // ..
- // return foo(x-1)
- // }
- // }
- //
- // that is equivalent to
- //
- // 0000 NULL
- // 0001 DEFL 0
- // 0003 GETL 0
- // 0005 CLOSURE ? 1
- // 0009 SETL 0
- //
-
- c.emit(node, OpNull)
- c.emit(node, OpDefineLocal, s.Index)
-
- s.LocalAssigned = true
- }
-
- c.emit(node, OpGetLocalPtr, s.Index)
- case ScopeFree:
- c.emit(node, OpGetFreePtr, s.Index)
- }
- }
-
- compiledFunction := &objects.CompiledFunction{
- Instructions: instructions,
- NumLocals: numLocals,
- NumParameters: len(node.Type.Params.List),
- VarArgs: node.Type.Params.VarArgs,
- SourceMap: sourceMap,
- }
-
- if len(freeSymbols) > 0 {
- c.emit(node, OpClosure, c.addConstant(compiledFunction), len(freeSymbols))
- } else {
- c.emit(node, OpConstant, c.addConstant(compiledFunction))
- }
-
- case *ast.ReturnStmt:
- if c.symbolTable.Parent(true) == nil {
- // outside the function
- return c.errorf(node, "return not allowed outside function")
- }
-
- if node.Result == nil {
- c.emit(node, OpReturn, 0)
- } else {
- if err := c.Compile(node.Result); err != nil {
- return err
- }
-
- c.emit(node, OpReturn, 1)
- }
-
- case *ast.CallExpr:
- if err := c.Compile(node.Func); err != nil {
- return err
- }
-
- for _, arg := range node.Args {
- if err := c.Compile(arg); err != nil {
- return err
- }
- }
-
- c.emit(node, OpCall, len(node.Args))
-
- case *ast.ImportExpr:
- 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
- }
-
- 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
- }
-
- 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:
- // export statement must be in top-level scope
- if c.scopeIndex != 0 {
- return c.errorf(node, "export not allowed inside function")
- }
-
- // export statement is simply ignore when compiling non-module code
- if c.parent == nil {
- break
- }
-
- if err := c.Compile(node.Result); err != nil {
- return err
- }
-
- c.emit(node, OpImmutable)
- c.emit(node, OpReturn, 1)
-
- case *ast.ErrorExpr:
- if err := c.Compile(node.Expr); err != nil {
- return err
- }
-
- c.emit(node, OpError)
-
- case *ast.ImmutableExpr:
- if err := c.Compile(node.Expr); err != nil {
- return err
- }
-
- c.emit(node, OpImmutable)
-
- case *ast.CondExpr:
- if err := c.Compile(node.Cond); err != nil {
- return err
- }
-
- // first jump placeholder
- jumpPos1 := c.emit(node, OpJumpFalsy, 0)
-
- if err := c.Compile(node.True); err != nil {
- return err
- }
-
- // second jump placeholder
- jumpPos2 := c.emit(node, OpJump, 0)
-
- // update first jump offset
- curPos := len(c.currentInstructions())
- c.changeOperand(jumpPos1, curPos)
-
- if err := c.Compile(node.False); err != nil {
- return err
- }
-
- // update second jump offset
- curPos = len(c.currentInstructions())
- c.changeOperand(jumpPos2, curPos)
- }
-
- return nil
-}
-
-// Bytecode returns a compiled bytecode.
-func (c *Compiler) Bytecode() *Bytecode {
- return &Bytecode{
- FileSet: c.file.Set(),
- MainFunction: &objects.CompiledFunction{
- Instructions: c.currentInstructions(),
- SourceMap: c.currentSourceMap(),
- },
- Constants: c.constants,
- }
-}
-
-// 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, 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
-}
-
-func (c *Compiler) error(node ast.Node, err error) error {
- return &Error{
- fileSet: c.file.Set(),
- node: node,
- error: err,
- }
-}
-
-func (c *Compiler) errorf(node ast.Node, format string, args ...interface{}) error {
- return &Error{
- fileSet: c.file.Set(),
- node: node,
- error: fmt.Errorf(format, args...),
- }
-}
-
-func (c *Compiler) addConstant(o objects.Object) int {
- if c.parent != nil {
- // module compilers will use their parent's constants array
- return c.parent.addConstant(o)
- }
-
- c.constants = append(c.constants, o)
-
- if c.trace != nil {
- c.printTrace(fmt.Sprintf("CONST %04d %s", len(c.constants)-1, o))
- }
-
- return len(c.constants) - 1
-}
-
-func (c *Compiler) addInstruction(b []byte) int {
- posNewIns := len(c.currentInstructions())
-
- c.scopes[c.scopeIndex].instructions = append(c.currentInstructions(), b...)
-
- return posNewIns
-}
-
-func (c *Compiler) replaceInstruction(pos int, inst []byte) {
- copy(c.currentInstructions()[pos:], inst)
-
- if c.trace != nil {
- c.printTrace(fmt.Sprintf("REPLC %s",
- FormatInstructions(c.scopes[c.scopeIndex].instructions[pos:], pos)[0]))
- }
-}
-
-func (c *Compiler) changeOperand(opPos int, operand ...int) {
- op := Opcode(c.currentInstructions()[opPos])
- inst := MakeInstruction(op, operand...)
-
- 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 {
- filePos = node.Pos()
- }
-
- inst := MakeInstruction(opcode, operands...)
- pos := c.addInstruction(inst)
- c.scopes[c.scopeIndex].sourceMap[pos] = filePos
-
- if c.trace != nil {
- c.printTrace(fmt.Sprintf("EMIT %s",
- FormatInstructions(c.scopes[c.scopeIndex].instructions[pos:], pos)[0]))
- }
-
- return pos
-}
-
-func (c *Compiler) printTrace(a ...interface{}) {
- const (
- dots = ". . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . "
- n = len(dots)
- )
-
- i := 2 * c.indent
- for i > n {
- _, _ = fmt.Fprint(c.trace, dots)
- i -= n
- }
- _, _ = fmt.Fprint(c.trace, dots[0:i])
- _, _ = fmt.Fprintln(c.trace, a...)
-}
-
-func trace(c *Compiler, msg string) *Compiler {
- c.printTrace(msg, "{")
- c.indent++
-
- return c
-}
-
-func un(c *Compiler) {
- c.indent--
- c.printTrace("}")
-}