Source file src/go.starlark.net/internal/compile/compile.go

Documentation: go.starlark.net/internal/compile

     1  // Package compile defines the Starlark bytecode compiler.
     2  // It is an internal package of the Starlark interpreter and is not directly accessible to clients.
     3  //
     4  // The compiler generates byte code with optional uint32 operands for a
     5  // virtual machine with the following components:
     6  //   - a program counter, which is an index into the byte code array.
     7  //   - an operand stack, whose maximum size is computed for each function by the compiler.
     8  //   - an stack of active iterators.
     9  //   - an array of local variables.
    10  //     The number of local variables and their indices are computed by the resolver.
    11  //     Locals (possibly including parameters) that are shared with nested functions
    12  //     are 'cells': their locals array slot will contain a value of type 'cell',
    13  //     an indirect value in a box that is explicitly read/updated by instructions.
    14  //   - an array of free variables, for nested functions.
    15  //     Free variables are a subset of the ancestors' cell variables.
    16  //     As with locals and cells, these are computed by the resolver.
    17  //   - an array of global variables, shared among all functions in the same module.
    18  //     All elements are initially nil.
    19  //   - two maps of predeclared and universal identifiers.
    20  //
    21  // Each function has a line number table that maps each program counter
    22  // offset to a source position, including the column number.
    23  //
    24  // Operands, logically uint32s, are encoded using little-endian 7-bit
    25  // varints, the top bit indicating that more bytes follow.
    26  //
    27  package compile // import "go.starlark.net/internal/compile"
    28  
    29  import (
    30  	"bytes"
    31  	"fmt"
    32  	"log"
    33  	"os"
    34  	"path/filepath"
    35  	"strconv"
    36  	"strings"
    37  	"sync"
    38  
    39  	"go.starlark.net/resolve"
    40  	"go.starlark.net/syntax"
    41  )
    42  
    43  // Disassemble causes the assembly code for each function
    44  // to be printed to stderr as it is generated.
    45  var Disassemble = false
    46  
    47  const debug = false // make code generation verbose, for debugging the compiler
    48  
    49  // Increment this to force recompilation of saved bytecode files.
    50  const Version = 13
    51  
    52  type Opcode uint8
    53  
    54  // "x DUP x x" is a "stack picture" that describes the state of the
    55  // stack before and after execution of the instruction.
    56  //
    57  // OP<index> indicates an immediate operand that is an index into the
    58  // specified table: locals, names, freevars, constants.
    59  const (
    60  	NOP Opcode = iota // - NOP -
    61  
    62  	// stack operations
    63  	DUP  //   x DUP x x
    64  	DUP2 // x y DUP2 x y x y
    65  	POP  //   x POP -
    66  	EXCH // x y EXCH y x
    67  
    68  	// binary comparisons
    69  	// (order must match Token)
    70  	LT
    71  	GT
    72  	GE
    73  	LE
    74  	EQL
    75  	NEQ
    76  
    77  	// binary arithmetic
    78  	// (order must match Token)
    79  	PLUS
    80  	MINUS
    81  	STAR
    82  	SLASH
    83  	SLASHSLASH
    84  	PERCENT
    85  	AMP
    86  	PIPE
    87  	CIRCUMFLEX
    88  	LTLT
    89  	GTGT
    90  
    91  	IN
    92  
    93  	// unary operators
    94  	UPLUS  // x UPLUS x
    95  	UMINUS // x UMINUS -x
    96  	TILDE  // x TILDE ~x
    97  
    98  	NONE      // - NONE None
    99  	TRUE      // - TRUE True
   100  	FALSE     // - FALSE False
   101  	MANDATORY // - MANDATORY Mandatory	     [sentinel value for required kwonly args]
   102  
   103  	ITERPUSH     //       iterable ITERPUSH     -  [pushes the iterator stack]
   104  	ITERPOP      //              - ITERPOP      -    [pops the iterator stack]
   105  	NOT          //          value NOT          bool
   106  	RETURN       //          value RETURN       -
   107  	SETINDEX     //        a i new SETINDEX     -
   108  	INDEX        //            a i INDEX        elem
   109  	SETDICT      // dict key value SETDICT      -
   110  	SETDICTUNIQ  // dict key value SETDICTUNIQ  -
   111  	APPEND       //      list elem APPEND       -
   112  	SLICE        //   x lo hi step SLICE        slice
   113  	INPLACE_ADD  //            x y INPLACE_ADD  z      where z is x+y or x.extend(y)
   114  	INPLACE_PIPE //            x y INPLACE_PIPE z      where z is x|y
   115  	MAKEDICT     //              - MAKEDICT     dict
   116  
   117  	// --- opcodes with an argument must go below this line ---
   118  
   119  	// control flow
   120  	JMP     //            - JMP<addr>     -
   121  	CJMP    //         cond CJMP<addr>    -
   122  	ITERJMP //            - ITERJMP<addr> elem   (and fall through) [acts on topmost iterator]
   123  	//       or:          - ITERJMP<addr> -      (and jump)
   124  
   125  	CONSTANT     //                 - CONSTANT<constant>  value
   126  	MAKETUPLE    //         x1 ... xn MAKETUPLE<n>        tuple
   127  	MAKELIST     //         x1 ... xn MAKELIST<n>         list
   128  	MAKEFUNC     // defaults+freevars MAKEFUNC<func>      fn
   129  	LOAD         //   from1 ... fromN module LOAD<n>      v1 ... vN
   130  	SETLOCAL     //             value SETLOCAL<local>     -
   131  	SETGLOBAL    //             value SETGLOBAL<global>   -
   132  	LOCAL        //                 - LOCAL<local>        value
   133  	FREE         //                 - FREE<freevar>       cell
   134  	FREECELL     //                 - FREECELL<freevar>   value       (content of FREE cell)
   135  	LOCALCELL    //                 - LOCALCELL<local>    value       (content of LOCAL cell)
   136  	SETLOCALCELL //             value SETLOCALCELL<local> -           (set content of LOCAL cell)
   137  	GLOBAL       //                 - GLOBAL<global>      value
   138  	PREDECLARED  //                 - PREDECLARED<name>   value
   139  	UNIVERSAL    //                 - UNIVERSAL<name>     value
   140  	ATTR         //                 x ATTR<name>          y           y = x.name
   141  	SETFIELD     //               x y SETFIELD<name>      -           x.name = y
   142  	UNPACK       //          iterable UNPACK<n>           vn ... v1
   143  
   144  	// n>>8 is #positional args and n&0xff is #named args (pairs).
   145  	CALL        // fn positional named                CALL<n>        result
   146  	CALL_VAR    // fn positional named *args          CALL_VAR<n>    result
   147  	CALL_KW     // fn positional named       **kwargs CALL_KW<n>     result
   148  	CALL_VAR_KW // fn positional named *args **kwargs CALL_VAR_KW<n> result
   149  
   150  	OpcodeArgMin = JMP
   151  	OpcodeMax    = CALL_VAR_KW
   152  )
   153  
   154  // TODO(adonovan): add dynamic checks for missing opcodes in the tables below.
   155  
   156  var opcodeNames = [...]string{
   157  	AMP:          "amp",
   158  	APPEND:       "append",
   159  	ATTR:         "attr",
   160  	CALL:         "call",
   161  	CALL_KW:      "call_kw ",
   162  	CALL_VAR:     "call_var",
   163  	CALL_VAR_KW:  "call_var_kw",
   164  	CIRCUMFLEX:   "circumflex",
   165  	CJMP:         "cjmp",
   166  	CONSTANT:     "constant",
   167  	DUP2:         "dup2",
   168  	DUP:          "dup",
   169  	EQL:          "eql",
   170  	EXCH:         "exch",
   171  	FALSE:        "false",
   172  	FREE:         "free",
   173  	FREECELL:     "freecell",
   174  	GE:           "ge",
   175  	GLOBAL:       "global",
   176  	GT:           "gt",
   177  	GTGT:         "gtgt",
   178  	IN:           "in",
   179  	INDEX:        "index",
   180  	INPLACE_ADD:  "inplace_add",
   181  	INPLACE_PIPE: "inplace_pipe",
   182  	ITERJMP:      "iterjmp",
   183  	ITERPOP:      "iterpop",
   184  	ITERPUSH:     "iterpush",
   185  	JMP:          "jmp",
   186  	LE:           "le",
   187  	LOAD:         "load",
   188  	LOCAL:        "local",
   189  	LOCALCELL:    "localcell",
   190  	LT:           "lt",
   191  	LTLT:         "ltlt",
   192  	MAKEDICT:     "makedict",
   193  	MAKEFUNC:     "makefunc",
   194  	MAKELIST:     "makelist",
   195  	MAKETUPLE:    "maketuple",
   196  	MANDATORY:    "mandatory",
   197  	MINUS:        "minus",
   198  	NEQ:          "neq",
   199  	NONE:         "none",
   200  	NOP:          "nop",
   201  	NOT:          "not",
   202  	PERCENT:      "percent",
   203  	PIPE:         "pipe",
   204  	PLUS:         "plus",
   205  	POP:          "pop",
   206  	PREDECLARED:  "predeclared",
   207  	RETURN:       "return",
   208  	SETDICT:      "setdict",
   209  	SETDICTUNIQ:  "setdictuniq",
   210  	SETFIELD:     "setfield",
   211  	SETGLOBAL:    "setglobal",
   212  	SETINDEX:     "setindex",
   213  	SETLOCAL:     "setlocal",
   214  	SETLOCALCELL: "setlocalcell",
   215  	SLASH:        "slash",
   216  	SLASHSLASH:   "slashslash",
   217  	SLICE:        "slice",
   218  	STAR:         "star",
   219  	TILDE:        "tilde",
   220  	TRUE:         "true",
   221  	UMINUS:       "uminus",
   222  	UNIVERSAL:    "universal",
   223  	UNPACK:       "unpack",
   224  	UPLUS:        "uplus",
   225  }
   226  
   227  const variableStackEffect = 0x7f
   228  
   229  // stackEffect records the effect on the size of the operand stack of
   230  // each kind of instruction. For some instructions this requires computation.
   231  var stackEffect = [...]int8{
   232  	AMP:          -1,
   233  	APPEND:       -2,
   234  	ATTR:         0,
   235  	CALL:         variableStackEffect,
   236  	CALL_KW:      variableStackEffect,
   237  	CALL_VAR:     variableStackEffect,
   238  	CALL_VAR_KW:  variableStackEffect,
   239  	CIRCUMFLEX:   -1,
   240  	CJMP:         -1,
   241  	CONSTANT:     +1,
   242  	DUP2:         +2,
   243  	DUP:          +1,
   244  	EQL:          -1,
   245  	FALSE:        +1,
   246  	FREE:         +1,
   247  	FREECELL:     +1,
   248  	GE:           -1,
   249  	GLOBAL:       +1,
   250  	GT:           -1,
   251  	GTGT:         -1,
   252  	IN:           -1,
   253  	INDEX:        -1,
   254  	INPLACE_ADD:  -1,
   255  	INPLACE_PIPE: -1,
   256  	ITERJMP:      variableStackEffect,
   257  	ITERPOP:      0,
   258  	ITERPUSH:     -1,
   259  	JMP:          0,
   260  	LE:           -1,
   261  	LOAD:         -1,
   262  	LOCAL:        +1,
   263  	LOCALCELL:    +1,
   264  	LT:           -1,
   265  	LTLT:         -1,
   266  	MAKEDICT:     +1,
   267  	MAKEFUNC:     0,
   268  	MAKELIST:     variableStackEffect,
   269  	MAKETUPLE:    variableStackEffect,
   270  	MANDATORY:    +1,
   271  	MINUS:        -1,
   272  	NEQ:          -1,
   273  	NONE:         +1,
   274  	NOP:          0,
   275  	NOT:          0,
   276  	PERCENT:      -1,
   277  	PIPE:         -1,
   278  	PLUS:         -1,
   279  	POP:          -1,
   280  	PREDECLARED:  +1,
   281  	RETURN:       -1,
   282  	SETLOCALCELL: -1,
   283  	SETDICT:      -3,
   284  	SETDICTUNIQ:  -3,
   285  	SETFIELD:     -2,
   286  	SETGLOBAL:    -1,
   287  	SETINDEX:     -3,
   288  	SETLOCAL:     -1,
   289  	SLASH:        -1,
   290  	SLASHSLASH:   -1,
   291  	SLICE:        -3,
   292  	STAR:         -1,
   293  	TRUE:         +1,
   294  	UMINUS:       0,
   295  	UNIVERSAL:    +1,
   296  	UNPACK:       variableStackEffect,
   297  	UPLUS:        0,
   298  }
   299  
   300  func (op Opcode) String() string {
   301  	if op < OpcodeMax {
   302  		if name := opcodeNames[op]; name != "" {
   303  			return name
   304  		}
   305  	}
   306  	return fmt.Sprintf("illegal op (%d)", op)
   307  }
   308  
   309  // A Program is a Starlark file in executable form.
   310  //
   311  // Programs are serialized by the Program.Encode method,
   312  // which must be updated whenever this declaration is changed.
   313  type Program struct {
   314  	Loads     []Binding     // name (really, string) and position of each load stmt
   315  	Names     []string      // names of attributes and predeclared variables
   316  	Constants []interface{} // = string | int64 | float64 | *big.Int | Bytes
   317  	Functions []*Funcode
   318  	Globals   []Binding // for error messages and tracing
   319  	Toplevel  *Funcode  // module initialization function
   320  }
   321  
   322  // The type of a bytes literal value, to distinguish from text string.
   323  type Bytes string
   324  
   325  // A Funcode is the code of a compiled Starlark function.
   326  //
   327  // Funcodes are serialized by the encoder.function method,
   328  // which must be updated whenever this declaration is changed.
   329  type Funcode struct {
   330  	Prog                  *Program
   331  	Pos                   syntax.Position // position of def or lambda token
   332  	Name                  string          // name of this function
   333  	Doc                   string          // docstring of this function
   334  	Code                  []byte          // the byte code
   335  	pclinetab             []uint16        // mapping from pc to linenum
   336  	Locals                []Binding       // locals, parameters first
   337  	Cells                 []int           // indices of Locals that require cells
   338  	Freevars              []Binding       // for tracing
   339  	MaxStack              int
   340  	NumParams             int
   341  	NumKwonlyParams       int
   342  	HasVarargs, HasKwargs bool
   343  
   344  	// -- transient state --
   345  
   346  	lntOnce sync.Once
   347  	lnt     []pclinecol // decoded line number table
   348  }
   349  
   350  type pclinecol struct {
   351  	pc        uint32
   352  	line, col int32
   353  }
   354  
   355  // A Binding is the name and position of a binding identifier.
   356  type Binding struct {
   357  	Name string
   358  	Pos  syntax.Position
   359  }
   360  
   361  // A pcomp holds the compiler state for a Program.
   362  type pcomp struct {
   363  	prog *Program // what we're building
   364  
   365  	names     map[string]uint32
   366  	constants map[interface{}]uint32
   367  	functions map[*Funcode]uint32
   368  }
   369  
   370  // An fcomp holds the compiler state for a Funcode.
   371  type fcomp struct {
   372  	fn *Funcode // what we're building
   373  
   374  	pcomp *pcomp
   375  	pos   syntax.Position // current position of generated code
   376  	loops []loop
   377  	block *block
   378  }
   379  
   380  type loop struct {
   381  	break_, continue_ *block
   382  }
   383  
   384  type block struct {
   385  	insns []insn
   386  
   387  	// If the last insn is a RETURN, jmp and cjmp are nil.
   388  	// If the last insn is a CJMP or ITERJMP,
   389  	//  cjmp and jmp are the "true" and "false" successors.
   390  	// Otherwise, jmp is the sole successor.
   391  	jmp, cjmp *block
   392  
   393  	initialstack int // for stack depth computation
   394  
   395  	// Used during encoding
   396  	index int // -1 => not encoded yet
   397  	addr  uint32
   398  }
   399  
   400  type insn struct {
   401  	op        Opcode
   402  	arg       uint32
   403  	line, col int32
   404  }
   405  
   406  // Position returns the source position for program counter pc.
   407  func (fn *Funcode) Position(pc uint32) syntax.Position {
   408  	fn.lntOnce.Do(fn.decodeLNT)
   409  
   410  	// Binary search to find last LNT entry not greater than pc.
   411  	// To avoid dynamic dispatch, this is a specialization of
   412  	// sort.Search using this predicate:
   413  	//   !(i < len(fn.lnt)-1 && fn.lnt[i+1].pc <= pc)
   414  	n := len(fn.lnt)
   415  	i, j := 0, n
   416  	for i < j {
   417  		h := int(uint(i+j) >> 1)
   418  		if !(h >= n-1 || fn.lnt[h+1].pc > pc) {
   419  			i = h + 1
   420  		} else {
   421  			j = h
   422  		}
   423  	}
   424  
   425  	var line, col int32
   426  	if i < n {
   427  		line = fn.lnt[i].line
   428  		col = fn.lnt[i].col
   429  	}
   430  
   431  	pos := fn.Pos // copy the (annoyingly inaccessible) filename
   432  	pos.Col = col
   433  	pos.Line = line
   434  	return pos
   435  }
   436  
   437  // decodeLNT decodes the line number table and populates fn.lnt.
   438  // It is called at most once.
   439  func (fn *Funcode) decodeLNT() {
   440  	// Conceptually the table contains rows of the form
   441  	// (pc uint32, line int32, col int32), sorted by pc.
   442  	// We use a delta encoding, since the differences
   443  	// between successive pc, line, and column values
   444  	// are typically small and positive (though line and
   445  	// especially column differences may be negative).
   446  	// The delta encoding starts from
   447  	// {pc: 0, line: fn.Pos.Line, col: fn.Pos.Col}.
   448  	//
   449  	// Each entry is packed into one or more 16-bit values:
   450  	//    Δpc        uint4
   451  	//    Δline      int5
   452  	//    Δcol       int6
   453  	//    incomplete uint1
   454  	// The top 4 bits are the unsigned delta pc.
   455  	// The next 5 bits are the signed line number delta.
   456  	// The next 6 bits are the signed column number delta.
   457  	// The bottom bit indicates that more rows follow because
   458  	// one of the deltas was maxed out.
   459  	// These field widths were chosen from a sample of real programs,
   460  	// and allow >97% of rows to be encoded in a single uint16.
   461  
   462  	fn.lnt = make([]pclinecol, 0, len(fn.pclinetab)) // a minor overapproximation
   463  	entry := pclinecol{
   464  		pc:   0,
   465  		line: fn.Pos.Line,
   466  		col:  fn.Pos.Col,
   467  	}
   468  	for _, x := range fn.pclinetab {
   469  		entry.pc += uint32(x) >> 12
   470  		entry.line += int32((int16(x) << 4) >> (16 - 5)) // sign extend Δline
   471  		entry.col += int32((int16(x) << 9) >> (16 - 6))  // sign extend Δcol
   472  		if (x & 1) == 0 {
   473  			fn.lnt = append(fn.lnt, entry)
   474  		}
   475  	}
   476  }
   477  
   478  // bindings converts resolve.Bindings to compiled form.
   479  func bindings(bindings []*resolve.Binding) []Binding {
   480  	res := make([]Binding, len(bindings))
   481  	for i, bind := range bindings {
   482  		res[i].Name = bind.First.Name
   483  		res[i].Pos = bind.First.NamePos
   484  	}
   485  	return res
   486  }
   487  
   488  // Expr compiles an expression to a program whose toplevel function evaluates it.
   489  func Expr(expr syntax.Expr, name string, locals []*resolve.Binding) *Program {
   490  	pos := syntax.Start(expr)
   491  	stmts := []syntax.Stmt{&syntax.ReturnStmt{Result: expr}}
   492  	return File(stmts, pos, name, locals, nil)
   493  }
   494  
   495  // File compiles the statements of a file into a program.
   496  func File(stmts []syntax.Stmt, pos syntax.Position, name string, locals, globals []*resolve.Binding) *Program {
   497  	pcomp := &pcomp{
   498  		prog: &Program{
   499  			Globals: bindings(globals),
   500  		},
   501  		names:     make(map[string]uint32),
   502  		constants: make(map[interface{}]uint32),
   503  		functions: make(map[*Funcode]uint32),
   504  	}
   505  	pcomp.prog.Toplevel = pcomp.function(name, pos, stmts, locals, nil)
   506  
   507  	return pcomp.prog
   508  }
   509  
   510  func (pcomp *pcomp) function(name string, pos syntax.Position, stmts []syntax.Stmt, locals, freevars []*resolve.Binding) *Funcode {
   511  	fcomp := &fcomp{
   512  		pcomp: pcomp,
   513  		pos:   pos,
   514  		fn: &Funcode{
   515  			Prog:     pcomp.prog,
   516  			Pos:      pos,
   517  			Name:     name,
   518  			Doc:      docStringFromBody(stmts),
   519  			Locals:   bindings(locals),
   520  			Freevars: bindings(freevars),
   521  		},
   522  	}
   523  
   524  	// Record indices of locals that require cells.
   525  	for i, local := range locals {
   526  		if local.Scope == resolve.Cell {
   527  			fcomp.fn.Cells = append(fcomp.fn.Cells, i)
   528  		}
   529  	}
   530  
   531  	if debug {
   532  		fmt.Fprintf(os.Stderr, "start function(%s @ %s)\n", name, pos)
   533  	}
   534  
   535  	// Convert AST to a CFG of instructions.
   536  	entry := fcomp.newBlock()
   537  	fcomp.block = entry
   538  	fcomp.stmts(stmts)
   539  	if fcomp.block != nil {
   540  		fcomp.emit(NONE)
   541  		fcomp.emit(RETURN)
   542  	}
   543  
   544  	var oops bool // something bad happened
   545  
   546  	setinitialstack := func(b *block, depth int) {
   547  		if b.initialstack == -1 {
   548  			b.initialstack = depth
   549  		} else if b.initialstack != depth {
   550  			fmt.Fprintf(os.Stderr, "%d: setinitialstack: depth mismatch: %d vs %d\n",
   551  				b.index, b.initialstack, depth)
   552  			oops = true
   553  		}
   554  	}
   555  
   556  	// Linearize the CFG:
   557  	// compute order, address, and initial
   558  	// stack depth of each reachable block.
   559  	var pc uint32
   560  	var blocks []*block
   561  	var maxstack int
   562  	var visit func(b *block)
   563  	visit = func(b *block) {
   564  		if b.index >= 0 {
   565  			return // already visited
   566  		}
   567  		b.index = len(blocks)
   568  		b.addr = pc
   569  		blocks = append(blocks, b)
   570  
   571  		stack := b.initialstack
   572  		if debug {
   573  			fmt.Fprintf(os.Stderr, "%s block %d: (stack = %d)\n", name, b.index, stack)
   574  		}
   575  		var cjmpAddr *uint32
   576  		var isiterjmp int
   577  		for i, insn := range b.insns {
   578  			pc++
   579  
   580  			// Compute size of argument.
   581  			if insn.op >= OpcodeArgMin {
   582  				switch insn.op {
   583  				case ITERJMP:
   584  					isiterjmp = 1
   585  					fallthrough
   586  				case CJMP:
   587  					cjmpAddr = &b.insns[i].arg
   588  					pc += 4
   589  				default:
   590  					pc += uint32(argLen(insn.arg))
   591  				}
   592  			}
   593  
   594  			// Compute effect on stack.
   595  			se := insn.stackeffect()
   596  			if debug {
   597  				fmt.Fprintln(os.Stderr, "\t", insn.op, stack, stack+se)
   598  			}
   599  			stack += se
   600  			if stack < 0 {
   601  				fmt.Fprintf(os.Stderr, "After pc=%d: stack underflow\n", pc)
   602  				oops = true
   603  			}
   604  			if stack+isiterjmp > maxstack {
   605  				maxstack = stack + isiterjmp
   606  			}
   607  		}
   608  
   609  		if debug {
   610  			fmt.Fprintf(os.Stderr, "successors of block %d (start=%d):\n",
   611  				b.addr, b.index)
   612  			if b.jmp != nil {
   613  				fmt.Fprintf(os.Stderr, "jmp to %d\n", b.jmp.index)
   614  			}
   615  			if b.cjmp != nil {
   616  				fmt.Fprintf(os.Stderr, "cjmp to %d\n", b.cjmp.index)
   617  			}
   618  		}
   619  
   620  		// Place the jmp block next.
   621  		if b.jmp != nil {
   622  			// jump threading (empty cycles are impossible)
   623  			for b.jmp.insns == nil {
   624  				b.jmp = b.jmp.jmp
   625  			}
   626  
   627  			setinitialstack(b.jmp, stack+isiterjmp)
   628  			if b.jmp.index < 0 {
   629  				// Successor is not yet visited:
   630  				// place it next and fall through.
   631  				visit(b.jmp)
   632  			} else {
   633  				// Successor already visited;
   634  				// explicit backward jump required.
   635  				pc += 5
   636  			}
   637  		}
   638  
   639  		// Then the cjmp block.
   640  		if b.cjmp != nil {
   641  			// jump threading (empty cycles are impossible)
   642  			for b.cjmp.insns == nil {
   643  				b.cjmp = b.cjmp.jmp
   644  			}
   645  
   646  			setinitialstack(b.cjmp, stack)
   647  			visit(b.cjmp)
   648  
   649  			// Patch the CJMP/ITERJMP, if present.
   650  			if cjmpAddr != nil {
   651  				*cjmpAddr = b.cjmp.addr
   652  			}
   653  		}
   654  	}
   655  	setinitialstack(entry, 0)
   656  	visit(entry)
   657  
   658  	fn := fcomp.fn
   659  	fn.MaxStack = maxstack
   660  
   661  	// Emit bytecode (and position table).
   662  	if Disassemble {
   663  		fmt.Fprintf(os.Stderr, "Function %s: (%d blocks, %d bytes)\n", name, len(blocks), pc)
   664  	}
   665  	fcomp.generate(blocks, pc)
   666  
   667  	if debug {
   668  		fmt.Fprintf(os.Stderr, "code=%d maxstack=%d\n", fn.Code, fn.MaxStack)
   669  	}
   670  
   671  	// Don't panic until we've completed printing of the function.
   672  	if oops {
   673  		panic("internal error")
   674  	}
   675  
   676  	if debug {
   677  		fmt.Fprintf(os.Stderr, "end function(%s @ %s)\n", name, pos)
   678  	}
   679  
   680  	return fn
   681  }
   682  
   683  func docStringFromBody(body []syntax.Stmt) string {
   684  	if len(body) == 0 {
   685  		return ""
   686  	}
   687  	expr, ok := body[0].(*syntax.ExprStmt)
   688  	if !ok {
   689  		return ""
   690  	}
   691  	lit, ok := expr.X.(*syntax.Literal)
   692  	if !ok {
   693  		return ""
   694  	}
   695  	if lit.Token != syntax.STRING {
   696  		return ""
   697  	}
   698  	return lit.Value.(string)
   699  }
   700  
   701  func (insn *insn) stackeffect() int {
   702  	se := int(stackEffect[insn.op])
   703  	if se == variableStackEffect {
   704  		arg := int(insn.arg)
   705  		switch insn.op {
   706  		case CALL, CALL_KW, CALL_VAR, CALL_VAR_KW:
   707  			se = -int(2*(insn.arg&0xff) + insn.arg>>8)
   708  			if insn.op != CALL {
   709  				se--
   710  			}
   711  			if insn.op == CALL_VAR_KW {
   712  				se--
   713  			}
   714  		case ITERJMP:
   715  			// Stack effect differs by successor:
   716  			// +1 for jmp/false/ok
   717  			//  0 for cjmp/true/exhausted
   718  			// Handled specially in caller.
   719  			se = 0
   720  		case MAKELIST, MAKETUPLE:
   721  			se = 1 - arg
   722  		case UNPACK:
   723  			se = arg - 1
   724  		default:
   725  			panic(insn.op)
   726  		}
   727  	}
   728  	return se
   729  }
   730  
   731  // generate emits the linear instruction stream from the CFG,
   732  // and builds the PC-to-line number table.
   733  func (fcomp *fcomp) generate(blocks []*block, codelen uint32) {
   734  	code := make([]byte, 0, codelen)
   735  	var pclinetab []uint16
   736  	prev := pclinecol{
   737  		pc:   0,
   738  		line: fcomp.fn.Pos.Line,
   739  		col:  fcomp.fn.Pos.Col,
   740  	}
   741  
   742  	for _, b := range blocks {
   743  		if Disassemble {
   744  			fmt.Fprintf(os.Stderr, "%d:\n", b.index)
   745  		}
   746  		pc := b.addr
   747  		for _, insn := range b.insns {
   748  			if insn.line != 0 {
   749  				// Instruction has a source position.  Delta-encode it.
   750  				// See Funcode.Position for the encoding.
   751  				for {
   752  					var incomplete uint16
   753  
   754  					// Δpc, uint4
   755  					deltapc := pc - prev.pc
   756  					if deltapc > 0x0f {
   757  						deltapc = 0x0f
   758  						incomplete = 1
   759  					}
   760  					prev.pc += deltapc
   761  
   762  					// Δline, int5
   763  					deltaline, ok := clip(insn.line-prev.line, -0x10, 0x0f)
   764  					if !ok {
   765  						incomplete = 1
   766  					}
   767  					prev.line += deltaline
   768  
   769  					// Δcol, int6
   770  					deltacol, ok := clip(insn.col-prev.col, -0x20, 0x1f)
   771  					if !ok {
   772  						incomplete = 1
   773  					}
   774  					prev.col += deltacol
   775  
   776  					entry := uint16(deltapc<<12) | uint16(deltaline&0x1f)<<7 | uint16(deltacol&0x3f)<<1 | incomplete
   777  					pclinetab = append(pclinetab, entry)
   778  					if incomplete == 0 {
   779  						break
   780  					}
   781  				}
   782  
   783  				if Disassemble {
   784  					fmt.Fprintf(os.Stderr, "\t\t\t\t\t; %s:%d:%d\n",
   785  						filepath.Base(fcomp.fn.Pos.Filename()), insn.line, insn.col)
   786  				}
   787  			}
   788  			if Disassemble {
   789  				PrintOp(fcomp.fn, pc, insn.op, insn.arg)
   790  			}
   791  			code = append(code, byte(insn.op))
   792  			pc++
   793  			if insn.op >= OpcodeArgMin {
   794  				if insn.op == CJMP || insn.op == ITERJMP {
   795  					code = addUint32(code, insn.arg, 4) // pad arg to 4 bytes
   796  				} else {
   797  					code = addUint32(code, insn.arg, 0)
   798  				}
   799  				pc = uint32(len(code))
   800  			}
   801  		}
   802  
   803  		if b.jmp != nil && b.jmp.index != b.index+1 {
   804  			addr := b.jmp.addr
   805  			if Disassemble {
   806  				fmt.Fprintf(os.Stderr, "\t%d\tjmp\t\t%d\t; block %d\n",
   807  					pc, addr, b.jmp.index)
   808  			}
   809  			code = append(code, byte(JMP))
   810  			code = addUint32(code, addr, 4)
   811  		}
   812  	}
   813  	if len(code) != int(codelen) {
   814  		panic("internal error: wrong code length")
   815  	}
   816  
   817  	fcomp.fn.pclinetab = pclinetab
   818  	fcomp.fn.Code = code
   819  }
   820  
   821  // clip returns the value nearest x in the range [min...max],
   822  // and whether it equals x.
   823  func clip(x, min, max int32) (int32, bool) {
   824  	if x > max {
   825  		return max, false
   826  	} else if x < min {
   827  		return min, false
   828  	} else {
   829  		return x, true
   830  	}
   831  }
   832  
   833  // addUint32 encodes x as 7-bit little-endian varint.
   834  // TODO(adonovan): opt: steal top two bits of opcode
   835  // to encode the number of complete bytes that follow.
   836  func addUint32(code []byte, x uint32, min int) []byte {
   837  	end := len(code) + min
   838  	for x >= 0x80 {
   839  		code = append(code, byte(x)|0x80)
   840  		x >>= 7
   841  	}
   842  	code = append(code, byte(x))
   843  	// Pad the operand with NOPs to exactly min bytes.
   844  	for len(code) < end {
   845  		code = append(code, byte(NOP))
   846  	}
   847  	return code
   848  }
   849  
   850  func argLen(x uint32) int {
   851  	n := 0
   852  	for x >= 0x80 {
   853  		n++
   854  		x >>= 7
   855  	}
   856  	return n + 1
   857  }
   858  
   859  // PrintOp prints an instruction.
   860  // It is provided for debugging.
   861  func PrintOp(fn *Funcode, pc uint32, op Opcode, arg uint32) {
   862  	if op < OpcodeArgMin {
   863  		fmt.Fprintf(os.Stderr, "\t%d\t%s\n", pc, op)
   864  		return
   865  	}
   866  
   867  	var comment string
   868  	switch op {
   869  	case CONSTANT:
   870  		switch x := fn.Prog.Constants[arg].(type) {
   871  		case string:
   872  			comment = strconv.Quote(x)
   873  		case Bytes:
   874  			comment = "b" + strconv.Quote(string(x))
   875  		default:
   876  			comment = fmt.Sprint(x)
   877  		}
   878  	case MAKEFUNC:
   879  		comment = fn.Prog.Functions[arg].Name
   880  	case SETLOCAL, LOCAL:
   881  		comment = fn.Locals[arg].Name
   882  	case SETGLOBAL, GLOBAL:
   883  		comment = fn.Prog.Globals[arg].Name
   884  	case ATTR, SETFIELD, PREDECLARED, UNIVERSAL:
   885  		comment = fn.Prog.Names[arg]
   886  	case FREE:
   887  		comment = fn.Freevars[arg].Name
   888  	case CALL, CALL_VAR, CALL_KW, CALL_VAR_KW:
   889  		comment = fmt.Sprintf("%d pos, %d named", arg>>8, arg&0xff)
   890  	default:
   891  		// JMP, CJMP, ITERJMP, MAKETUPLE, MAKELIST, LOAD, UNPACK:
   892  		// arg is just a number
   893  	}
   894  	var buf bytes.Buffer
   895  	fmt.Fprintf(&buf, "\t%d\t%-10s\t%d", pc, op, arg)
   896  	if comment != "" {
   897  		fmt.Fprint(&buf, "\t; ", comment)
   898  	}
   899  	fmt.Fprintln(&buf)
   900  	os.Stderr.Write(buf.Bytes())
   901  }
   902  
   903  // newBlock returns a new block.
   904  func (fcomp) newBlock() *block {
   905  	return &block{index: -1, initialstack: -1}
   906  }
   907  
   908  // emit emits an instruction to the current block.
   909  func (fcomp *fcomp) emit(op Opcode) {
   910  	if op >= OpcodeArgMin {
   911  		panic("missing arg: " + op.String())
   912  	}
   913  	insn := insn{op: op, line: fcomp.pos.Line, col: fcomp.pos.Col}
   914  	fcomp.block.insns = append(fcomp.block.insns, insn)
   915  	fcomp.pos.Line = 0
   916  	fcomp.pos.Col = 0
   917  }
   918  
   919  // emit1 emits an instruction with an immediate operand.
   920  func (fcomp *fcomp) emit1(op Opcode, arg uint32) {
   921  	if op < OpcodeArgMin {
   922  		panic("unwanted arg: " + op.String())
   923  	}
   924  	insn := insn{op: op, arg: arg, line: fcomp.pos.Line, col: fcomp.pos.Col}
   925  	fcomp.block.insns = append(fcomp.block.insns, insn)
   926  	fcomp.pos.Line = 0
   927  	fcomp.pos.Col = 0
   928  }
   929  
   930  // jump emits a jump to the specified block.
   931  // On return, the current block is unset.
   932  func (fcomp *fcomp) jump(b *block) {
   933  	if b == fcomp.block {
   934  		panic("self-jump") // unreachable: Starlark has no arbitrary looping constructs
   935  	}
   936  	fcomp.block.jmp = b
   937  	fcomp.block = nil
   938  }
   939  
   940  // condjump emits a conditional jump (CJMP or ITERJMP)
   941  // to the specified true/false blocks.
   942  // (For ITERJMP, the cases are jmp/f/ok and cjmp/t/exhausted.)
   943  // On return, the current block is unset.
   944  func (fcomp *fcomp) condjump(op Opcode, t, f *block) {
   945  	if !(op == CJMP || op == ITERJMP) {
   946  		panic("not a conditional jump: " + op.String())
   947  	}
   948  	fcomp.emit1(op, 0) // fill in address later
   949  	fcomp.block.cjmp = t
   950  	fcomp.jump(f)
   951  }
   952  
   953  // nameIndex returns the index of the specified name
   954  // within the name pool, adding it if necessary.
   955  func (pcomp *pcomp) nameIndex(name string) uint32 {
   956  	index, ok := pcomp.names[name]
   957  	if !ok {
   958  		index = uint32(len(pcomp.prog.Names))
   959  		pcomp.names[name] = index
   960  		pcomp.prog.Names = append(pcomp.prog.Names, name)
   961  	}
   962  	return index
   963  }
   964  
   965  // constantIndex returns the index of the specified constant
   966  // within the constant pool, adding it if necessary.
   967  func (pcomp *pcomp) constantIndex(v interface{}) uint32 {
   968  	index, ok := pcomp.constants[v]
   969  	if !ok {
   970  		index = uint32(len(pcomp.prog.Constants))
   971  		pcomp.constants[v] = index
   972  		pcomp.prog.Constants = append(pcomp.prog.Constants, v)
   973  	}
   974  	return index
   975  }
   976  
   977  // functionIndex returns the index of the specified function
   978  // AST the nestedfun pool, adding it if necessary.
   979  func (pcomp *pcomp) functionIndex(fn *Funcode) uint32 {
   980  	index, ok := pcomp.functions[fn]
   981  	if !ok {
   982  		index = uint32(len(pcomp.prog.Functions))
   983  		pcomp.functions[fn] = index
   984  		pcomp.prog.Functions = append(pcomp.prog.Functions, fn)
   985  	}
   986  	return index
   987  }
   988  
   989  // string emits code to push the specified string.
   990  func (fcomp *fcomp) string(s string) {
   991  	fcomp.emit1(CONSTANT, fcomp.pcomp.constantIndex(s))
   992  }
   993  
   994  // setPos sets the current source position.
   995  // It should be called prior to any operation that can fail dynamically.
   996  // All positions are assumed to belong to the same file.
   997  func (fcomp *fcomp) setPos(pos syntax.Position) {
   998  	fcomp.pos = pos
   999  }
  1000  
  1001  // set emits code to store the top-of-stack value
  1002  // to the specified local, cell, or global variable.
  1003  func (fcomp *fcomp) set(id *syntax.Ident) {
  1004  	bind := id.Binding.(*resolve.Binding)
  1005  	switch bind.Scope {
  1006  	case resolve.Local:
  1007  		fcomp.emit1(SETLOCAL, uint32(bind.Index))
  1008  	case resolve.Cell:
  1009  		fcomp.emit1(SETLOCALCELL, uint32(bind.Index))
  1010  	case resolve.Global:
  1011  		fcomp.emit1(SETGLOBAL, uint32(bind.Index))
  1012  	default:
  1013  		log.Panicf("%s: set(%s): not global/local/cell (%d)", id.NamePos, id.Name, bind.Scope)
  1014  	}
  1015  }
  1016  
  1017  // lookup emits code to push the value of the specified variable.
  1018  func (fcomp *fcomp) lookup(id *syntax.Ident) {
  1019  	bind := id.Binding.(*resolve.Binding)
  1020  	if bind.Scope != resolve.Universal { // (universal lookup can't fail)
  1021  		fcomp.setPos(id.NamePos)
  1022  	}
  1023  	switch bind.Scope {
  1024  	case resolve.Local:
  1025  		fcomp.emit1(LOCAL, uint32(bind.Index))
  1026  	case resolve.Free:
  1027  		fcomp.emit1(FREECELL, uint32(bind.Index))
  1028  	case resolve.Cell:
  1029  		fcomp.emit1(LOCALCELL, uint32(bind.Index))
  1030  	case resolve.Global:
  1031  		fcomp.emit1(GLOBAL, uint32(bind.Index))
  1032  	case resolve.Predeclared:
  1033  		fcomp.emit1(PREDECLARED, fcomp.pcomp.nameIndex(id.Name))
  1034  	case resolve.Universal:
  1035  		fcomp.emit1(UNIVERSAL, fcomp.pcomp.nameIndex(id.Name))
  1036  	default:
  1037  		log.Panicf("%s: compiler.lookup(%s): scope = %d", id.NamePos, id.Name, bind.Scope)
  1038  	}
  1039  }
  1040  
  1041  func (fcomp *fcomp) stmts(stmts []syntax.Stmt) {
  1042  	for _, stmt := range stmts {
  1043  		fcomp.stmt(stmt)
  1044  	}
  1045  }
  1046  
  1047  func (fcomp *fcomp) stmt(stmt syntax.Stmt) {
  1048  	switch stmt := stmt.(type) {
  1049  	case *syntax.ExprStmt:
  1050  		if _, ok := stmt.X.(*syntax.Literal); ok {
  1051  			// Opt: don't compile doc comments only to pop them.
  1052  			return
  1053  		}
  1054  		fcomp.expr(stmt.X)
  1055  		fcomp.emit(POP)
  1056  
  1057  	case *syntax.BranchStmt:
  1058  		// Resolver invariant: break/continue appear only within loops.
  1059  		switch stmt.Token {
  1060  		case syntax.PASS:
  1061  			// no-op
  1062  		case syntax.BREAK:
  1063  			b := fcomp.loops[len(fcomp.loops)-1].break_
  1064  			fcomp.jump(b)
  1065  			fcomp.block = fcomp.newBlock() // dead code
  1066  		case syntax.CONTINUE:
  1067  			b := fcomp.loops[len(fcomp.loops)-1].continue_
  1068  			fcomp.jump(b)
  1069  			fcomp.block = fcomp.newBlock() // dead code
  1070  		}
  1071  
  1072  	case *syntax.IfStmt:
  1073  		// Keep consistent with CondExpr.
  1074  		t := fcomp.newBlock()
  1075  		f := fcomp.newBlock()
  1076  		done := fcomp.newBlock()
  1077  
  1078  		fcomp.ifelse(stmt.Cond, t, f)
  1079  
  1080  		fcomp.block = t
  1081  		fcomp.stmts(stmt.True)
  1082  		fcomp.jump(done)
  1083  
  1084  		fcomp.block = f
  1085  		fcomp.stmts(stmt.False)
  1086  		fcomp.jump(done)
  1087  
  1088  		fcomp.block = done
  1089  
  1090  	case *syntax.AssignStmt:
  1091  		switch stmt.Op {
  1092  		case syntax.EQ:
  1093  			// simple assignment: x = y
  1094  			fcomp.expr(stmt.RHS)
  1095  			fcomp.assign(stmt.OpPos, stmt.LHS)
  1096  
  1097  		case syntax.PLUS_EQ,
  1098  			syntax.MINUS_EQ,
  1099  			syntax.STAR_EQ,
  1100  			syntax.SLASH_EQ,
  1101  			syntax.SLASHSLASH_EQ,
  1102  			syntax.PERCENT_EQ,
  1103  			syntax.AMP_EQ,
  1104  			syntax.PIPE_EQ,
  1105  			syntax.CIRCUMFLEX_EQ,
  1106  			syntax.LTLT_EQ,
  1107  			syntax.GTGT_EQ:
  1108  			// augmented assignment: x += y
  1109  
  1110  			var set func()
  1111  
  1112  			// Evaluate "address" of x exactly once to avoid duplicate side-effects.
  1113  			switch lhs := unparen(stmt.LHS).(type) {
  1114  			case *syntax.Ident:
  1115  				// x = ...
  1116  				fcomp.lookup(lhs)
  1117  				set = func() {
  1118  					fcomp.set(lhs)
  1119  				}
  1120  
  1121  			case *syntax.IndexExpr:
  1122  				// x[y] = ...
  1123  				fcomp.expr(lhs.X)
  1124  				fcomp.expr(lhs.Y)
  1125  				fcomp.emit(DUP2)
  1126  				fcomp.setPos(lhs.Lbrack)
  1127  				fcomp.emit(INDEX)
  1128  				set = func() {
  1129  					fcomp.setPos(lhs.Lbrack)
  1130  					fcomp.emit(SETINDEX)
  1131  				}
  1132  
  1133  			case *syntax.DotExpr:
  1134  				// x.f = ...
  1135  				fcomp.expr(lhs.X)
  1136  				fcomp.emit(DUP)
  1137  				name := fcomp.pcomp.nameIndex(lhs.Name.Name)
  1138  				fcomp.setPos(lhs.Dot)
  1139  				fcomp.emit1(ATTR, name)
  1140  				set = func() {
  1141  					fcomp.setPos(lhs.Dot)
  1142  					fcomp.emit1(SETFIELD, name)
  1143  				}
  1144  
  1145  			default:
  1146  				panic(lhs)
  1147  			}
  1148  
  1149  			fcomp.expr(stmt.RHS)
  1150  
  1151  			// In-place x+=y and x|=y have special semantics:
  1152  			// the resulting x aliases the original x.
  1153  			switch stmt.Op {
  1154  			case syntax.PLUS_EQ:
  1155  				fcomp.setPos(stmt.OpPos)
  1156  				fcomp.emit(INPLACE_ADD)
  1157  			case syntax.PIPE_EQ:
  1158  				fcomp.setPos(stmt.OpPos)
  1159  				fcomp.emit(INPLACE_PIPE)
  1160  			default:
  1161  				fcomp.binop(stmt.OpPos, stmt.Op-syntax.PLUS_EQ+syntax.PLUS)
  1162  			}
  1163  			set()
  1164  		}
  1165  
  1166  	case *syntax.DefStmt:
  1167  		fcomp.function(stmt.Function.(*resolve.Function))
  1168  		fcomp.set(stmt.Name)
  1169  
  1170  	case *syntax.ForStmt:
  1171  		// Keep consistent with ForClause.
  1172  		head := fcomp.newBlock()
  1173  		body := fcomp.newBlock()
  1174  		tail := fcomp.newBlock()
  1175  
  1176  		fcomp.expr(stmt.X)
  1177  		fcomp.setPos(stmt.For)
  1178  		fcomp.emit(ITERPUSH)
  1179  		fcomp.jump(head)
  1180  
  1181  		fcomp.block = head
  1182  		fcomp.condjump(ITERJMP, tail, body)
  1183  
  1184  		fcomp.block = body
  1185  		fcomp.assign(stmt.For, stmt.Vars)
  1186  		fcomp.loops = append(fcomp.loops, loop{break_: tail, continue_: head})
  1187  		fcomp.stmts(stmt.Body)
  1188  		fcomp.loops = fcomp.loops[:len(fcomp.loops)-1]
  1189  		fcomp.jump(head)
  1190  
  1191  		fcomp.block = tail
  1192  		fcomp.emit(ITERPOP)
  1193  
  1194  	case *syntax.WhileStmt:
  1195  		head := fcomp.newBlock()
  1196  		body := fcomp.newBlock()
  1197  		done := fcomp.newBlock()
  1198  
  1199  		fcomp.jump(head)
  1200  		fcomp.block = head
  1201  		fcomp.ifelse(stmt.Cond, body, done)
  1202  
  1203  		fcomp.block = body
  1204  		fcomp.loops = append(fcomp.loops, loop{break_: done, continue_: head})
  1205  		fcomp.stmts(stmt.Body)
  1206  		fcomp.loops = fcomp.loops[:len(fcomp.loops)-1]
  1207  		fcomp.jump(head)
  1208  
  1209  		fcomp.block = done
  1210  
  1211  	case *syntax.ReturnStmt:
  1212  		if stmt.Result != nil {
  1213  			fcomp.expr(stmt.Result)
  1214  		} else {
  1215  			fcomp.emit(NONE)
  1216  		}
  1217  		fcomp.emit(RETURN)
  1218  		fcomp.block = fcomp.newBlock() // dead code
  1219  
  1220  	case *syntax.LoadStmt:
  1221  		for i := range stmt.From {
  1222  			fcomp.string(stmt.From[i].Name)
  1223  		}
  1224  		module := stmt.Module.Value.(string)
  1225  		fcomp.pcomp.prog.Loads = append(fcomp.pcomp.prog.Loads, Binding{
  1226  			Name: module,
  1227  			Pos:  stmt.Module.TokenPos,
  1228  		})
  1229  		fcomp.string(module)
  1230  		fcomp.setPos(stmt.Load)
  1231  		fcomp.emit1(LOAD, uint32(len(stmt.From)))
  1232  		for i := range stmt.To {
  1233  			fcomp.set(stmt.To[len(stmt.To)-1-i])
  1234  		}
  1235  
  1236  	default:
  1237  		start, _ := stmt.Span()
  1238  		log.Panicf("%s: exec: unexpected statement %T", start, stmt)
  1239  	}
  1240  }
  1241  
  1242  // assign implements lhs = rhs for arbitrary expressions lhs.
  1243  // RHS is on top of stack, consumed.
  1244  func (fcomp *fcomp) assign(pos syntax.Position, lhs syntax.Expr) {
  1245  	switch lhs := lhs.(type) {
  1246  	case *syntax.ParenExpr:
  1247  		// (lhs) = rhs
  1248  		fcomp.assign(pos, lhs.X)
  1249  
  1250  	case *syntax.Ident:
  1251  		// x = rhs
  1252  		fcomp.set(lhs)
  1253  
  1254  	case *syntax.TupleExpr:
  1255  		// x, y = rhs
  1256  		fcomp.assignSequence(pos, lhs.List)
  1257  
  1258  	case *syntax.ListExpr:
  1259  		// [x, y] = rhs
  1260  		fcomp.assignSequence(pos, lhs.List)
  1261  
  1262  	case *syntax.IndexExpr:
  1263  		// x[y] = rhs
  1264  		fcomp.expr(lhs.X)
  1265  		fcomp.emit(EXCH)
  1266  		fcomp.expr(lhs.Y)
  1267  		fcomp.emit(EXCH)
  1268  		fcomp.setPos(lhs.Lbrack)
  1269  		fcomp.emit(SETINDEX)
  1270  
  1271  	case *syntax.DotExpr:
  1272  		// x.f = rhs
  1273  		fcomp.expr(lhs.X)
  1274  		fcomp.emit(EXCH)
  1275  		fcomp.setPos(lhs.Dot)
  1276  		fcomp.emit1(SETFIELD, fcomp.pcomp.nameIndex(lhs.Name.Name))
  1277  
  1278  	default:
  1279  		panic(lhs)
  1280  	}
  1281  }
  1282  
  1283  func (fcomp *fcomp) assignSequence(pos syntax.Position, lhs []syntax.Expr) {
  1284  	fcomp.setPos(pos)
  1285  	fcomp.emit1(UNPACK, uint32(len(lhs)))
  1286  	for i := range lhs {
  1287  		fcomp.assign(pos, lhs[i])
  1288  	}
  1289  }
  1290  
  1291  func (fcomp *fcomp) expr(e syntax.Expr) {
  1292  	switch e := e.(type) {
  1293  	case *syntax.ParenExpr:
  1294  		fcomp.expr(e.X)
  1295  
  1296  	case *syntax.Ident:
  1297  		fcomp.lookup(e)
  1298  
  1299  	case *syntax.Literal:
  1300  		// e.Value is int64, float64, *bigInt, string
  1301  		v := e.Value
  1302  		if e.Token == syntax.BYTES {
  1303  			v = Bytes(v.(string))
  1304  		}
  1305  		fcomp.emit1(CONSTANT, fcomp.pcomp.constantIndex(v))
  1306  
  1307  	case *syntax.ListExpr:
  1308  		for _, x := range e.List {
  1309  			fcomp.expr(x)
  1310  		}
  1311  		fcomp.emit1(MAKELIST, uint32(len(e.List)))
  1312  
  1313  	case *syntax.CondExpr:
  1314  		// Keep consistent with IfStmt.
  1315  		t := fcomp.newBlock()
  1316  		f := fcomp.newBlock()
  1317  		done := fcomp.newBlock()
  1318  
  1319  		fcomp.ifelse(e.Cond, t, f)
  1320  
  1321  		fcomp.block = t
  1322  		fcomp.expr(e.True)
  1323  		fcomp.jump(done)
  1324  
  1325  		fcomp.block = f
  1326  		fcomp.expr(e.False)
  1327  		fcomp.jump(done)
  1328  
  1329  		fcomp.block = done
  1330  
  1331  	case *syntax.IndexExpr:
  1332  		fcomp.expr(e.X)
  1333  		fcomp.expr(e.Y)
  1334  		fcomp.setPos(e.Lbrack)
  1335  		fcomp.emit(INDEX)
  1336  
  1337  	case *syntax.SliceExpr:
  1338  		fcomp.setPos(e.Lbrack)
  1339  		fcomp.expr(e.X)
  1340  		if e.Lo != nil {
  1341  			fcomp.expr(e.Lo)
  1342  		} else {
  1343  			fcomp.emit(NONE)
  1344  		}
  1345  		if e.Hi != nil {
  1346  			fcomp.expr(e.Hi)
  1347  		} else {
  1348  			fcomp.emit(NONE)
  1349  		}
  1350  		if e.Step != nil {
  1351  			fcomp.expr(e.Step)
  1352  		} else {
  1353  			fcomp.emit(NONE)
  1354  		}
  1355  		fcomp.emit(SLICE)
  1356  
  1357  	case *syntax.Comprehension:
  1358  		if e.Curly {
  1359  			fcomp.emit(MAKEDICT)
  1360  		} else {
  1361  			fcomp.emit1(MAKELIST, 0)
  1362  		}
  1363  		fcomp.comprehension(e, 0)
  1364  
  1365  	case *syntax.TupleExpr:
  1366  		fcomp.tuple(e.List)
  1367  
  1368  	case *syntax.DictExpr:
  1369  		fcomp.emit(MAKEDICT)
  1370  		for _, entry := range e.List {
  1371  			entry := entry.(*syntax.DictEntry)
  1372  			fcomp.emit(DUP)
  1373  			fcomp.expr(entry.Key)
  1374  			fcomp.expr(entry.Value)
  1375  			fcomp.setPos(entry.Colon)
  1376  			fcomp.emit(SETDICTUNIQ)
  1377  		}
  1378  
  1379  	case *syntax.UnaryExpr:
  1380  		fcomp.expr(e.X)
  1381  		fcomp.setPos(e.OpPos)
  1382  		switch e.Op {
  1383  		case syntax.MINUS:
  1384  			fcomp.emit(UMINUS)
  1385  		case syntax.PLUS:
  1386  			fcomp.emit(UPLUS)
  1387  		case syntax.NOT:
  1388  			fcomp.emit(NOT)
  1389  		case syntax.TILDE:
  1390  			fcomp.emit(TILDE)
  1391  		default:
  1392  			log.Panicf("%s: unexpected unary op: %s", e.OpPos, e.Op)
  1393  		}
  1394  
  1395  	case *syntax.BinaryExpr:
  1396  		switch e.Op {
  1397  		// short-circuit operators
  1398  		// TODO(adonovan): use ifelse to simplify conditions.
  1399  		case syntax.OR:
  1400  			// x or y  =>  if x then x else y
  1401  			done := fcomp.newBlock()
  1402  			y := fcomp.newBlock()
  1403  
  1404  			fcomp.expr(e.X)
  1405  			fcomp.emit(DUP)
  1406  			fcomp.condjump(CJMP, done, y)
  1407  
  1408  			fcomp.block = y
  1409  			fcomp.emit(POP) // discard X
  1410  			fcomp.expr(e.Y)
  1411  			fcomp.jump(done)
  1412  
  1413  			fcomp.block = done
  1414  
  1415  		case syntax.AND:
  1416  			// x and y  =>  if x then y else x
  1417  			done := fcomp.newBlock()
  1418  			y := fcomp.newBlock()
  1419  
  1420  			fcomp.expr(e.X)
  1421  			fcomp.emit(DUP)
  1422  			fcomp.condjump(CJMP, y, done)
  1423  
  1424  			fcomp.block = y
  1425  			fcomp.emit(POP) // discard X
  1426  			fcomp.expr(e.Y)
  1427  			fcomp.jump(done)
  1428  
  1429  			fcomp.block = done
  1430  
  1431  		case syntax.PLUS:
  1432  			fcomp.plus(e)
  1433  
  1434  		default:
  1435  			// all other strict binary operator (includes comparisons)
  1436  			fcomp.expr(e.X)
  1437  			fcomp.expr(e.Y)
  1438  			fcomp.binop(e.OpPos, e.Op)
  1439  		}
  1440  
  1441  	case *syntax.DotExpr:
  1442  		fcomp.expr(e.X)
  1443  		fcomp.setPos(e.Dot)
  1444  		fcomp.emit1(ATTR, fcomp.pcomp.nameIndex(e.Name.Name))
  1445  
  1446  	case *syntax.CallExpr:
  1447  		fcomp.call(e)
  1448  
  1449  	case *syntax.LambdaExpr:
  1450  		fcomp.function(e.Function.(*resolve.Function))
  1451  
  1452  	default:
  1453  		start, _ := e.Span()
  1454  		log.Panicf("%s: unexpected expr %T", start, e)
  1455  	}
  1456  }
  1457  
  1458  type summand struct {
  1459  	x       syntax.Expr
  1460  	plusPos syntax.Position
  1461  }
  1462  
  1463  // plus emits optimized code for ((a+b)+...)+z that avoids naive
  1464  // quadratic behavior for strings, tuples, and lists,
  1465  // and folds together adjacent literals of the same type.
  1466  func (fcomp *fcomp) plus(e *syntax.BinaryExpr) {
  1467  	// Gather all the right operands of the left tree of plusses.
  1468  	// A tree (((a+b)+c)+d) becomes args=[a +b +c +d].
  1469  	args := make([]summand, 0, 2) // common case: 2 operands
  1470  	for plus := e; ; {
  1471  		args = append(args, summand{unparen(plus.Y), plus.OpPos})
  1472  		left := unparen(plus.X)
  1473  		x, ok := left.(*syntax.BinaryExpr)
  1474  		if !ok || x.Op != syntax.PLUS {
  1475  			args = append(args, summand{x: left})
  1476  			break
  1477  		}
  1478  		plus = x
  1479  	}
  1480  	// Reverse args to syntactic order.
  1481  	for i, n := 0, len(args)/2; i < n; i++ {
  1482  		j := len(args) - 1 - i
  1483  		args[i], args[j] = args[j], args[i]
  1484  	}
  1485  
  1486  	// Fold sums of adjacent literals of the same type: ""+"", []+[], ()+().
  1487  	out := args[:0] // compact in situ
  1488  	for i := 0; i < len(args); {
  1489  		j := i + 1
  1490  		if code := addable(args[i].x); code != 0 {
  1491  			for j < len(args) && addable(args[j].x) == code {
  1492  				j++
  1493  			}
  1494  			if j > i+1 {
  1495  				args[i].x = add(code, args[i:j])
  1496  			}
  1497  		}
  1498  		out = append(out, args[i])
  1499  		i = j
  1500  	}
  1501  	args = out
  1502  
  1503  	// Emit code for an n-ary sum (n > 0).
  1504  	fcomp.expr(args[0].x)
  1505  	for _, summand := range args[1:] {
  1506  		fcomp.expr(summand.x)
  1507  		fcomp.setPos(summand.plusPos)
  1508  		fcomp.emit(PLUS)
  1509  	}
  1510  
  1511  	// If len(args) > 2, use of an accumulator instead of a chain of
  1512  	// PLUS operations may be more efficient.
  1513  	// However, no gain was measured on a workload analogous to Bazel loading;
  1514  	// TODO(adonovan): opt: re-evaluate on a Bazel analysis-like workload.
  1515  	//
  1516  	// We cannot use a single n-ary SUM operation
  1517  	//    a b c SUM<3>
  1518  	// because we need to report a distinct error for each
  1519  	// individual '+' operation, so three additional operations are
  1520  	// needed:
  1521  	//
  1522  	//   ACCSTART => create buffer and append to it
  1523  	//   ACCUM    => append to buffer
  1524  	//   ACCEND   => get contents of buffer
  1525  	//
  1526  	// For string, list, and tuple values, the interpreter can
  1527  	// optimize these operations by using a mutable buffer.
  1528  	// For all other types, ACCSTART and ACCEND would behave like
  1529  	// the identity function and ACCUM behaves like PLUS.
  1530  	// ACCUM must correctly support user-defined operations
  1531  	// such as list+foo.
  1532  	//
  1533  	// fcomp.emit(ACCSTART)
  1534  	// for _, summand := range args[1:] {
  1535  	// 	fcomp.expr(summand.x)
  1536  	// 	fcomp.setPos(summand.plusPos)
  1537  	// 	fcomp.emit(ACCUM)
  1538  	// }
  1539  	// fcomp.emit(ACCEND)
  1540  }
  1541  
  1542  // addable reports whether e is a statically addable
  1543  // expression: a [s]tring, [b]ytes, [l]ist, or [t]uple.
  1544  func addable(e syntax.Expr) rune {
  1545  	switch e := e.(type) {
  1546  	case *syntax.Literal:
  1547  		// TODO(adonovan): opt: support INT/FLOAT/BIGINT constant folding.
  1548  		switch e.Token {
  1549  		case syntax.STRING:
  1550  			return 's'
  1551  		case syntax.BYTES:
  1552  			return 'b'
  1553  		}
  1554  	case *syntax.ListExpr:
  1555  		return 'l'
  1556  	case *syntax.TupleExpr:
  1557  		return 't'
  1558  	}
  1559  	return 0
  1560  }
  1561  
  1562  // add returns an expression denoting the sum of args,
  1563  // which are all addable values of the type indicated by code.
  1564  // The resulting syntax is degenerate, lacking position, etc.
  1565  func add(code rune, args []summand) syntax.Expr {
  1566  	switch code {
  1567  	case 's', 'b':
  1568  		var buf strings.Builder
  1569  		for _, arg := range args {
  1570  			buf.WriteString(arg.x.(*syntax.Literal).Value.(string))
  1571  		}
  1572  		tok := syntax.STRING
  1573  		if code == 'b' {
  1574  			tok = syntax.BYTES
  1575  		}
  1576  		return &syntax.Literal{Token: tok, Value: buf.String()}
  1577  	case 'l':
  1578  		var elems []syntax.Expr
  1579  		for _, arg := range args {
  1580  			elems = append(elems, arg.x.(*syntax.ListExpr).List...)
  1581  		}
  1582  		return &syntax.ListExpr{List: elems}
  1583  	case 't':
  1584  		var elems []syntax.Expr
  1585  		for _, arg := range args {
  1586  			elems = append(elems, arg.x.(*syntax.TupleExpr).List...)
  1587  		}
  1588  		return &syntax.TupleExpr{List: elems}
  1589  	}
  1590  	panic(code)
  1591  }
  1592  
  1593  func unparen(e syntax.Expr) syntax.Expr {
  1594  	if p, ok := e.(*syntax.ParenExpr); ok {
  1595  		return unparen(p.X)
  1596  	}
  1597  	return e
  1598  }
  1599  
  1600  func (fcomp *fcomp) binop(pos syntax.Position, op syntax.Token) {
  1601  	// TODO(adonovan): simplify by assuming syntax and compiler constants align.
  1602  	fcomp.setPos(pos)
  1603  	switch op {
  1604  	// arithmetic
  1605  	case syntax.PLUS:
  1606  		fcomp.emit(PLUS)
  1607  	case syntax.MINUS:
  1608  		fcomp.emit(MINUS)
  1609  	case syntax.STAR:
  1610  		fcomp.emit(STAR)
  1611  	case syntax.SLASH:
  1612  		fcomp.emit(SLASH)
  1613  	case syntax.SLASHSLASH:
  1614  		fcomp.emit(SLASHSLASH)
  1615  	case syntax.PERCENT:
  1616  		fcomp.emit(PERCENT)
  1617  	case syntax.AMP:
  1618  		fcomp.emit(AMP)
  1619  	case syntax.PIPE:
  1620  		fcomp.emit(PIPE)
  1621  	case syntax.CIRCUMFLEX:
  1622  		fcomp.emit(CIRCUMFLEX)
  1623  	case syntax.LTLT:
  1624  		fcomp.emit(LTLT)
  1625  	case syntax.GTGT:
  1626  		fcomp.emit(GTGT)
  1627  	case syntax.IN:
  1628  		fcomp.emit(IN)
  1629  	case syntax.NOT_IN:
  1630  		fcomp.emit(IN)
  1631  		fcomp.emit(NOT)
  1632  
  1633  		// comparisons
  1634  	case syntax.EQL,
  1635  		syntax.NEQ,
  1636  		syntax.GT,
  1637  		syntax.LT,
  1638  		syntax.LE,
  1639  		syntax.GE:
  1640  		fcomp.emit(Opcode(op-syntax.EQL) + EQL)
  1641  
  1642  	default:
  1643  		log.Panicf("%s: unexpected binary op: %s", pos, op)
  1644  	}
  1645  }
  1646  
  1647  func (fcomp *fcomp) call(call *syntax.CallExpr) {
  1648  	// TODO(adonovan): opt: Use optimized path for calling methods
  1649  	// of built-ins: x.f(...) to avoid materializing a closure.
  1650  	// if dot, ok := call.Fcomp.(*syntax.DotExpr); ok {
  1651  	// 	fcomp.expr(dot.X)
  1652  	// 	fcomp.args(call)
  1653  	// 	fcomp.emit1(CALL_ATTR, fcomp.name(dot.Name.Name))
  1654  	// 	return
  1655  	// }
  1656  
  1657  	// usual case
  1658  	fcomp.expr(call.Fn)
  1659  	op, arg := fcomp.args(call)
  1660  	fcomp.setPos(call.Lparen)
  1661  	fcomp.emit1(op, arg)
  1662  }
  1663  
  1664  // args emits code to push a tuple of positional arguments
  1665  // and a tuple of named arguments containing alternating keys and values.
  1666  // Either or both tuples may be empty (TODO(adonovan): optimize).
  1667  func (fcomp *fcomp) args(call *syntax.CallExpr) (op Opcode, arg uint32) {
  1668  	var callmode int
  1669  	// Compute the number of each kind of parameter.
  1670  	var p, n int // number of  positional, named arguments
  1671  	var varargs, kwargs syntax.Expr
  1672  	for _, arg := range call.Args {
  1673  		if binary, ok := arg.(*syntax.BinaryExpr); ok && binary.Op == syntax.EQ {
  1674  
  1675  			// named argument (name, value)
  1676  			fcomp.string(binary.X.(*syntax.Ident).Name)
  1677  			fcomp.expr(binary.Y)
  1678  			n++
  1679  			continue
  1680  		}
  1681  		if unary, ok := arg.(*syntax.UnaryExpr); ok {
  1682  			if unary.Op == syntax.STAR {
  1683  				callmode |= 1
  1684  				varargs = unary.X
  1685  				continue
  1686  			} else if unary.Op == syntax.STARSTAR {
  1687  				callmode |= 2
  1688  				kwargs = unary.X
  1689  				continue
  1690  			}
  1691  		}
  1692  
  1693  		// positional argument
  1694  		fcomp.expr(arg)
  1695  		p++
  1696  	}
  1697  
  1698  	// Python2 and Python3 both permit named arguments
  1699  	// to appear both before and after a *args argument:
  1700  	//   f(1, 2, x=3, *[4], y=5, **dict(z=6))
  1701  	//
  1702  	// They also differ in their evaluation order:
  1703  	//  Python2: 1 2 3 5 4 6 (*args and **kwargs evaluated last)
  1704  	//  Python3: 1 2 4 3 5 6 (positional args evaluated before named args)
  1705  	// Starlark-in-Java historically used a third order:
  1706  	//  Lexical: 1 2 3 4 5 6 (all args evaluated left-to-right)
  1707  	//
  1708  	// After discussion in github.com/bazelbuild/starlark#13, the
  1709  	// spec now requires Starlark to statically reject named
  1710  	// arguments after *args (e.g. y=5), and to use Python2-style
  1711  	// evaluation order. This is both easy to implement and
  1712  	// consistent with lexical order:
  1713  	//
  1714  	//   f(1, 2, x=3, *[4], **dict(z=6)) # 1 2 3 4 6
  1715  
  1716  	// *args
  1717  	if varargs != nil {
  1718  		fcomp.expr(varargs)
  1719  	}
  1720  
  1721  	// **kwargs
  1722  	if kwargs != nil {
  1723  		fcomp.expr(kwargs)
  1724  	}
  1725  
  1726  	// TODO(adonovan): avoid this with a more flexible encoding.
  1727  	if p >= 256 || n >= 256 {
  1728  		// resolve already checked this; should be unreachable
  1729  		panic("too many arguments in call")
  1730  	}
  1731  
  1732  	return CALL + Opcode(callmode), uint32(p<<8 | n)
  1733  }
  1734  
  1735  func (fcomp *fcomp) tuple(elems []syntax.Expr) {
  1736  	for _, elem := range elems {
  1737  		fcomp.expr(elem)
  1738  	}
  1739  	fcomp.emit1(MAKETUPLE, uint32(len(elems)))
  1740  }
  1741  
  1742  func (fcomp *fcomp) comprehension(comp *syntax.Comprehension, clauseIndex int) {
  1743  	if clauseIndex == len(comp.Clauses) {
  1744  		fcomp.emit(DUP) // accumulator
  1745  		if comp.Curly {
  1746  			// dict: {k:v for ...}
  1747  			// Parser ensures that body is of form k:v.
  1748  			// Python-style set comprehensions {body for vars in x}
  1749  			// are not supported.
  1750  			entry := comp.Body.(*syntax.DictEntry)
  1751  			fcomp.expr(entry.Key)
  1752  			fcomp.expr(entry.Value)
  1753  			fcomp.setPos(entry.Colon)
  1754  			fcomp.emit(SETDICT)
  1755  		} else {
  1756  			// list: [body for vars in x]
  1757  			fcomp.expr(comp.Body)
  1758  			fcomp.emit(APPEND)
  1759  		}
  1760  		return
  1761  	}
  1762  
  1763  	clause := comp.Clauses[clauseIndex]
  1764  	switch clause := clause.(type) {
  1765  	case *syntax.IfClause:
  1766  		t := fcomp.newBlock()
  1767  		done := fcomp.newBlock()
  1768  		fcomp.ifelse(clause.Cond, t, done)
  1769  
  1770  		fcomp.block = t
  1771  		fcomp.comprehension(comp, clauseIndex+1)
  1772  		fcomp.jump(done)
  1773  
  1774  		fcomp.block = done
  1775  		return
  1776  
  1777  	case *syntax.ForClause:
  1778  		// Keep consistent with ForStmt.
  1779  		head := fcomp.newBlock()
  1780  		body := fcomp.newBlock()
  1781  		tail := fcomp.newBlock()
  1782  
  1783  		fcomp.expr(clause.X)
  1784  		fcomp.setPos(clause.For)
  1785  		fcomp.emit(ITERPUSH)
  1786  		fcomp.jump(head)
  1787  
  1788  		fcomp.block = head
  1789  		fcomp.condjump(ITERJMP, tail, body)
  1790  
  1791  		fcomp.block = body
  1792  		fcomp.assign(clause.For, clause.Vars)
  1793  		fcomp.comprehension(comp, clauseIndex+1)
  1794  		fcomp.jump(head)
  1795  
  1796  		fcomp.block = tail
  1797  		fcomp.emit(ITERPOP)
  1798  		return
  1799  	}
  1800  
  1801  	start, _ := clause.Span()
  1802  	log.Panicf("%s: unexpected comprehension clause %T", start, clause)
  1803  }
  1804  
  1805  func (fcomp *fcomp) function(f *resolve.Function) {
  1806  	// Evaluation of the defaults may fail, so record the position.
  1807  	fcomp.setPos(f.Pos)
  1808  
  1809  	// To reduce allocation, we emit a combined tuple
  1810  	// for the defaults and the freevars.
  1811  	// The function knows where to split it at run time.
  1812  
  1813  	// Generate tuple of parameter defaults. For:
  1814  	//  def f(p1, p2=dp2, p3=dp3, *, k1, k2=dk2, k3, **kwargs)
  1815  	// the tuple is:
  1816  	//  (dp2, dp3, MANDATORY, dk2, MANDATORY).
  1817  	ndefaults := 0
  1818  	seenStar := false
  1819  	for _, param := range f.Params {
  1820  		switch param := param.(type) {
  1821  		case *syntax.BinaryExpr:
  1822  			fcomp.expr(param.Y)
  1823  			ndefaults++
  1824  		case *syntax.UnaryExpr:
  1825  			seenStar = true // * or *args (also **kwargs)
  1826  		case *syntax.Ident:
  1827  			if seenStar {
  1828  				fcomp.emit(MANDATORY)
  1829  				ndefaults++
  1830  			}
  1831  		}
  1832  	}
  1833  
  1834  	// Capture the cells of the function's
  1835  	// free variables from the lexical environment.
  1836  	for _, freevar := range f.FreeVars {
  1837  		// Don't call fcomp.lookup because we want
  1838  		// the cell itself, not its content.
  1839  		switch freevar.Scope {
  1840  		case resolve.Free:
  1841  			fcomp.emit1(FREE, uint32(freevar.Index))
  1842  		case resolve.Cell:
  1843  			fcomp.emit1(LOCAL, uint32(freevar.Index))
  1844  		}
  1845  	}
  1846  
  1847  	fcomp.emit1(MAKETUPLE, uint32(ndefaults+len(f.FreeVars)))
  1848  
  1849  	funcode := fcomp.pcomp.function(f.Name, f.Pos, f.Body, f.Locals, f.FreeVars)
  1850  
  1851  	if debug {
  1852  		// TODO(adonovan): do compilations sequentially not as a tree,
  1853  		// to make the log easier to read.
  1854  		// Simplify by identifying Toplevel and functionIndex 0.
  1855  		fmt.Fprintf(os.Stderr, "resuming %s @ %s\n", fcomp.fn.Name, fcomp.pos)
  1856  	}
  1857  
  1858  	// def f(a, *, b=1) has only 2 parameters.
  1859  	numParams := len(f.Params)
  1860  	if f.NumKwonlyParams > 0 && !f.HasVarargs {
  1861  		numParams--
  1862  	}
  1863  
  1864  	funcode.NumParams = numParams
  1865  	funcode.NumKwonlyParams = f.NumKwonlyParams
  1866  	funcode.HasVarargs = f.HasVarargs
  1867  	funcode.HasKwargs = f.HasKwargs
  1868  	fcomp.emit1(MAKEFUNC, fcomp.pcomp.functionIndex(funcode))
  1869  }
  1870  
  1871  // ifelse emits a Boolean control flow decision.
  1872  // On return, the current block is unset.
  1873  func (fcomp *fcomp) ifelse(cond syntax.Expr, t, f *block) {
  1874  	switch cond := cond.(type) {
  1875  	case *syntax.UnaryExpr:
  1876  		if cond.Op == syntax.NOT {
  1877  			// if not x then goto t else goto f
  1878  			//    =>
  1879  			// if x then goto f else goto t
  1880  			fcomp.ifelse(cond.X, f, t)
  1881  			return
  1882  		}
  1883  
  1884  	case *syntax.BinaryExpr:
  1885  		switch cond.Op {
  1886  		case syntax.AND:
  1887  			// if x and y then goto t else goto f
  1888  			//    =>
  1889  			// if x then ifelse(y, t, f) else goto f
  1890  			fcomp.expr(cond.X)
  1891  			y := fcomp.newBlock()
  1892  			fcomp.condjump(CJMP, y, f)
  1893  
  1894  			fcomp.block = y
  1895  			fcomp.ifelse(cond.Y, t, f)
  1896  			return
  1897  
  1898  		case syntax.OR:
  1899  			// if x or y then goto t else goto f
  1900  			//    =>
  1901  			// if x then goto t else ifelse(y, t, f)
  1902  			fcomp.expr(cond.X)
  1903  			y := fcomp.newBlock()
  1904  			fcomp.condjump(CJMP, t, y)
  1905  
  1906  			fcomp.block = y
  1907  			fcomp.ifelse(cond.Y, t, f)
  1908  			return
  1909  		case syntax.NOT_IN:
  1910  			// if x not in y then goto t else goto f
  1911  			//    =>
  1912  			// if x in y then goto f else goto t
  1913  			copy := *cond
  1914  			copy.Op = syntax.IN
  1915  			fcomp.expr(&copy)
  1916  			fcomp.condjump(CJMP, f, t)
  1917  			return
  1918  		}
  1919  	}
  1920  
  1921  	// general case
  1922  	fcomp.expr(cond)
  1923  	fcomp.condjump(CJMP, t, f)
  1924  }
  1925  

View as plain text