1 // Copyright 2013 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Package ssa/interp defines an interpreter for the SSA
6 // representation of Go programs.
8 // This interpreter is provided as an adjunct for testing the SSA
9 // construction algorithm. Its purpose is to provide a minimal
10 // metacircular implementation of the dynamic semantics of each SSA
11 // instruction. It is not, and will never be, a production-quality Go
14 // The following is a partial list of Go features that are currently
15 // unsupported or incomplete in the interpreter.
17 // * Unsafe operations, including all uses of unsafe.Pointer, are
18 // impossible to support given the "boxed" value representation we
21 // * The reflect package is only partially implemented.
23 // * The "testing" package is no longer supported because it
24 // depends on low-level details that change too often.
26 // * "sync/atomic" operations are not atomic due to the "boxed" value
27 // representation: it is not possible to read, modify and write an
28 // interface value atomically. As a consequence, Mutexes are currently
31 // * recover is only partially implemented. Also, the interpreter
32 // makes no attempt to distinguish target panics from interpreter
35 // * the sizes of the int, uint and uintptr types in the target
36 // program are assumed to be the same as those of the interpreter
39 // * all values occupy space, even those of types defined by the spec
40 // to have zero size, e.g. struct{}. This can cause asymptotic
41 // performance degradation.
43 // * os.Exit is implemented using panic, causing deferred functions to
45 package interp // import "golang.org/x/tools/go/ssa/interp"
56 "golang.org/x/tools/go/ssa"
62 kNext continuation = iota
67 // Mode is a bitmask of options affecting the interpreter.
71 DisableRecover Mode = 1 << iota // Disable recover() in target programs; show interpreter crash instead.
72 EnableTracing // Print a trace of all instructions as they are interpreted.
75 type methodSet map[string]*ssa.Function
77 // State shared between all interpreted goroutines.
78 type interpreter struct {
79 osArgs []value // the value of os.Args
80 prog *ssa.Program // the SSA program
81 globals map[ssa.Value]*value // addresses of global variables (immutable)
82 mode Mode // interpreter options
83 reflectPackage *ssa.Package // the fake reflect package
84 errorMethods methodSet // the method set of reflect.error, which implements the error interface.
85 rtypeMethods methodSet // the method set of rtype, which implements the reflect.Type interface.
86 runtimeErrorString types.Type // the runtime.errorString type
87 sizes types.Sizes // the effective type-sizing function
88 goroutines int32 // atomically updated
91 type deferred struct {
102 block, prevBlock *ssa.BasicBlock
103 env map[ssa.Value]value // dynamic values of SSA variables
111 func (fr *frame) get(key ssa.Value) value {
112 switch key := key.(type) {
114 // Hack; simplifies handling of optional attributes
115 // such as ssa.Slice.{Low,High}.
117 case *ssa.Function, *ssa.Builtin:
120 return constValue(key)
122 if r, ok := fr.i.globals[key]; ok {
126 if r, ok := fr.env[key]; ok {
129 panic(fmt.Sprintf("get: no value for %T: %v", key, key.Name()))
132 // runDefer runs a deferred call d.
133 // It always returns normally, but may set or clear fr.panic.
135 func (fr *frame) runDefer(d *deferred) {
136 if fr.i.mode&EnableTracing != 0 {
137 fmt.Fprintf(os.Stderr, "%s: invoking deferred function call\n",
138 fr.i.prog.Fset.Position(d.instr.Pos()))
143 // Deferred call created a new state of panic.
148 call(fr.i, fr, d.instr.Pos(), d.fn, d.args)
152 // runDefers executes fr's deferred function calls in LIFO order.
154 // On entry, fr.panicking indicates a state of panic; if
155 // true, fr.panic contains the panic value.
157 // On completion, if a deferred call started a panic, or if no
158 // deferred call recovered from a previous state of panic, then
159 // runDefers itself panics after the last deferred call has run.
161 // If there was no initial state of panic, or it was recovered from,
162 // runDefers returns normally.
164 func (fr *frame) runDefers() {
165 for d := fr.defers; d != nil; d = d.tail {
170 panic(fr.panic) // new panic, or still panicking
174 // lookupMethod returns the method set for type typ, which may be one
175 // of the interpreter's fake types.
176 func lookupMethod(i *interpreter, typ types.Type, meth *types.Func) *ssa.Function {
179 return i.rtypeMethods[meth.Id()]
181 return i.errorMethods[meth.Id()]
183 return i.prog.LookupMethod(typ, meth.Pkg(), meth.Name())
186 // visitInstr interprets a single ssa.Instruction within the activation
187 // record frame. It returns a continuation value indicating where to
188 // read the next instruction from.
189 func visitInstr(fr *frame, instr ssa.Instruction) continuation {
190 switch instr := instr.(type) {
195 fr.env[instr] = unop(instr, fr.get(instr.X))
198 fr.env[instr] = binop(instr.Op, instr.X.Type(), fr.get(instr.X), fr.get(instr.Y))
201 fn, args := prepareCall(fr, &instr.Call)
202 fr.env[instr] = call(fr.i, fr, instr.Pos(), fn, args)
204 case *ssa.ChangeInterface:
205 fr.env[instr] = fr.get(instr.X)
207 case *ssa.ChangeType:
208 fr.env[instr] = fr.get(instr.X) // (can't fail)
211 fr.env[instr] = conv(instr.Type(), instr.X.Type(), fr.get(instr.X))
213 case *ssa.MakeInterface:
214 fr.env[instr] = iface{t: instr.X.Type(), v: fr.get(instr.X)}
217 fr.env[instr] = fr.get(instr.Tuple).(tuple)[instr.Index]
220 fr.env[instr] = slice(fr.get(instr.X), fr.get(instr.Low), fr.get(instr.High), fr.get(instr.Max))
223 switch len(instr.Results) {
226 fr.result = fr.get(instr.Results[0])
229 for _, r := range instr.Results {
230 res = append(res, fr.get(r))
232 fr.result = tuple(res)
241 panic(targetPanic{fr.get(instr.X)})
244 fr.get(instr.Chan).(chan value) <- fr.get(instr.X)
247 store(deref(instr.Addr.Type()), fr.get(instr.Addr).(*value), fr.get(instr.Val))
251 if fr.get(instr.Cond).(bool) {
254 fr.prevBlock, fr.block = fr.block, fr.block.Succs[succ]
258 fr.prevBlock, fr.block = fr.block, fr.block.Succs[0]
262 fn, args := prepareCall(fr, &instr.Call)
263 fr.defers = &deferred{
271 fn, args := prepareCall(fr, &instr.Call)
272 atomic.AddInt32(&fr.i.goroutines, 1)
274 call(fr.i, nil, instr.Pos(), fn, args)
275 atomic.AddInt32(&fr.i.goroutines, -1)
279 fr.env[instr] = make(chan value, asInt(fr.get(instr.Size)))
289 addr = fr.env[instr].(*value)
291 *addr = zero(deref(instr.Type()))
294 slice := make([]value, asInt(fr.get(instr.Cap)))
295 tElt := instr.Type().Underlying().(*types.Slice).Elem()
296 for i := range slice {
297 slice[i] = zero(tElt)
299 fr.env[instr] = slice[:asInt(fr.get(instr.Len))]
303 if instr.Reserve != nil {
304 reserve = asInt(fr.get(instr.Reserve))
306 fr.env[instr] = makeMap(instr.Type().Underlying().(*types.Map).Key(), reserve)
309 fr.env[instr] = rangeIter(fr.get(instr.X), instr.X.Type())
312 fr.env[instr] = fr.get(instr.Iter).(iter).next()
315 fr.env[instr] = &(*fr.get(instr.X).(*value)).(structure)[instr.Field]
318 fr.env[instr] = fr.get(instr.X).(structure)[instr.Field]
322 idx := fr.get(instr.Index)
323 switch x := x.(type) {
325 fr.env[instr] = &x[asInt(idx)]
326 case *value: // *array
327 fr.env[instr] = &(*x).(array)[asInt(idx)]
329 panic(fmt.Sprintf("unexpected x type in IndexAddr: %T", x))
333 fr.env[instr] = fr.get(instr.X).(array)[asInt(fr.get(instr.Index))]
336 fr.env[instr] = lookup(instr, fr.get(instr.X), fr.get(instr.Index))
339 m := fr.get(instr.Map)
340 key := fr.get(instr.Key)
341 v := fr.get(instr.Value)
342 switch m := m.(type) {
343 case map[value]value:
346 m.insert(key.(hashable), v)
348 panic(fmt.Sprintf("illegal map type: %T", m))
351 case *ssa.TypeAssert:
352 fr.env[instr] = typeAssert(fr.i, instr, fr.get(instr.X).(iface))
354 case *ssa.MakeClosure:
356 for _, binding := range instr.Bindings {
357 bindings = append(bindings, fr.get(binding))
359 fr.env[instr] = &closure{instr.Fn.(*ssa.Function), bindings}
362 for i, pred := range instr.Block().Preds {
363 if fr.prevBlock == pred {
364 fr.env[instr] = fr.get(instr.Edges[i])
370 var cases []reflect.SelectCase
372 cases = append(cases, reflect.SelectCase{
373 Dir: reflect.SelectDefault,
376 for _, state := range instr.States {
377 var dir reflect.SelectDir
378 if state.Dir == types.RecvOnly {
379 dir = reflect.SelectRecv
381 dir = reflect.SelectSend
383 var send reflect.Value
384 if state.Send != nil {
385 send = reflect.ValueOf(fr.get(state.Send))
387 cases = append(cases, reflect.SelectCase{
389 Chan: reflect.ValueOf(fr.get(state.Chan)),
393 chosen, recv, recvOk := reflect.Select(cases)
395 chosen-- // default case should have index -1.
397 r := tuple{chosen, recvOk}
398 for i, st := range instr.States {
399 if st.Dir == types.RecvOnly {
401 if i == chosen && recvOk {
402 // No need to copy since send makes an unaliased copy.
403 v = recv.Interface().(value)
405 v = zero(st.Chan.Type().Underlying().(*types.Chan).Elem())
413 panic(fmt.Sprintf("unexpected instruction: %T", instr))
416 // if val, ok := instr.(ssa.Value); ok {
417 // fmt.Println(toString(fr.env[val])) // debugging
423 // prepareCall determines the function value and argument values for a
424 // function call in a Call, Go or Defer instruction, performing
425 // interface method lookup if needed.
427 func prepareCall(fr *frame, call *ssa.CallCommon) (fn value, args []value) {
428 v := fr.get(call.Value)
429 if call.Method == nil {
433 // Interface method invocation.
436 panic("method invoked on nil interface")
438 if f := lookupMethod(fr.i, recv.t, call.Method); f == nil {
439 // Unreachable in well-typed programs.
440 panic(fmt.Sprintf("method set for dynamic type %v does not contain %s", recv.t, call.Method))
444 args = append(args, recv.v)
446 for _, arg := range call.Args {
447 args = append(args, fr.get(arg))
452 // call interprets a call to a function (function, builtin or closure)
453 // fn with arguments args, returning its result.
454 // callpos is the position of the callsite.
456 func call(i *interpreter, caller *frame, callpos token.Pos, fn value, args []value) value {
457 switch fn := fn.(type) {
460 panic("call of nil function") // nil of func type
462 return callSSA(i, caller, callpos, fn, args, nil)
464 return callSSA(i, caller, callpos, fn.Fn, args, fn.Env)
466 return callBuiltin(caller, callpos, fn, args)
468 panic(fmt.Sprintf("cannot call %T", fn))
471 func loc(fset *token.FileSet, pos token.Pos) string {
472 if pos == token.NoPos {
475 return " at " + fset.Position(pos).String()
478 // callSSA interprets a call to function fn with arguments args,
479 // and lexical environment env, returning its result.
480 // callpos is the position of the callsite.
482 func callSSA(i *interpreter, caller *frame, callpos token.Pos, fn *ssa.Function, args []value, env []value) value {
483 if i.mode&EnableTracing != 0 {
485 // TODO(adonovan): fix: loc() lies for external functions.
486 fmt.Fprintf(os.Stderr, "Entering %s%s.\n", fn, loc(fset, fn.Pos()))
489 suffix = ", resuming " + caller.fn.String() + loc(fset, callpos)
491 defer fmt.Fprintf(os.Stderr, "Leaving %s%s.\n", fn, suffix)
495 caller: caller, // for panic/recover
498 if fn.Parent() == nil {
500 if ext := externals[name]; ext != nil {
501 if i.mode&EnableTracing != 0 {
502 fmt.Fprintln(os.Stderr, "\t(external)")
506 if fn.Blocks == nil {
507 panic("no code for function: " + name)
510 fr.env = make(map[ssa.Value]value)
511 fr.block = fn.Blocks[0]
512 fr.locals = make([]value, len(fn.Locals))
513 for i, l := range fn.Locals {
514 fr.locals[i] = zero(deref(l.Type()))
515 fr.env[l] = &fr.locals[i]
517 for i, p := range fn.Params {
520 for i, fv := range fn.FreeVars {
523 for fr.block != nil {
526 // Destroy the locals to avoid accidental use after return.
527 for i := range fn.Locals {
533 // runFrame executes SSA instructions starting at fr.block and
534 // continuing until a return, a panic, or a recovered panic.
536 // After a panic, runFrame panics.
538 // After a normal return, fr.result contains the result of the call
539 // and fr.block is nil.
541 // A recovered panic in a function without named return parameters
542 // (NRPs) becomes a normal return of the zero value of the function's
545 // After a recovered panic in a function with NRPs, fr.result is
546 // undefined and fr.block contains the block at which to resume
549 func runFrame(fr *frame) {
552 return // normal return
554 if fr.i.mode&DisableRecover != 0 {
555 return // let interpreter crash
559 if fr.i.mode&EnableTracing != 0 {
560 fmt.Fprintf(os.Stderr, "Panicking: %T %v.\n", fr.panic, fr.panic)
563 fr.block = fr.fn.Recover
567 if fr.i.mode&EnableTracing != 0 {
568 fmt.Fprintf(os.Stderr, ".%s:\n", fr.block)
571 for _, instr := range fr.block.Instrs {
572 if fr.i.mode&EnableTracing != 0 {
573 if v, ok := instr.(ssa.Value); ok {
574 fmt.Fprintln(os.Stderr, "\t", v.Name(), "=", instr)
576 fmt.Fprintln(os.Stderr, "\t", instr)
579 switch visitInstr(fr, instr) {
591 // doRecover implements the recover() built-in.
592 func doRecover(caller *frame) value {
593 // recover() must be exactly one level beneath the deferred
594 // function (two levels beneath the panicking function) to
595 // have any effect. Thus we ignore both "defer recover()" and
596 // "defer f() -> g() -> recover()".
597 if caller.i.mode&DisableRecover == 0 &&
598 caller != nil && !caller.panicking &&
599 caller.caller != nil && caller.caller.panicking {
600 caller.caller.panicking = false
601 p := caller.caller.panic
602 caller.caller.panic = nil
604 // TODO(adonovan): support runtime.Goexit.
605 switch p := p.(type) {
607 // The target program explicitly called panic().
610 // The interpreter encountered a runtime error.
611 return iface{caller.i.runtimeErrorString, p.Error()}
613 // The interpreter explicitly called panic().
614 return iface{caller.i.runtimeErrorString, p}
616 panic(fmt.Sprintf("unexpected panic type %T in target call to recover()", p))
622 // setGlobal sets the value of a system-initialized global variable.
623 func setGlobal(i *interpreter, pkg *ssa.Package, name string, v value) {
624 if g, ok := i.globals[pkg.Var(name)]; ok {
628 panic("no global variable: " + pkg.Pkg.Path() + "." + name)
631 // Interpret interprets the Go program whose main package is mainpkg.
632 // mode specifies various interpreter options. filename and args are
633 // the initial values of os.Args for the target program. sizes is the
634 // effective type-sizing function for this program.
636 // Interpret returns the exit code of the program: 2 for panic (like
637 // gc does), or the argument to os.Exit for normal termination.
639 // The SSA program must include the "runtime" package.
641 func Interpret(mainpkg *ssa.Package, mode Mode, sizes types.Sizes, filename string, args []string) (exitCode int) {
644 globals: make(map[ssa.Value]*value),
649 runtimePkg := i.prog.ImportedPackage("runtime")
650 if runtimePkg == nil {
651 panic("ssa.Program doesn't include runtime package")
653 i.runtimeErrorString = runtimePkg.Type("errorString").Object().Type()
657 i.osArgs = append(i.osArgs, filename)
658 for _, arg := range args {
659 i.osArgs = append(i.osArgs, arg)
662 for _, pkg := range i.prog.AllPackages() {
663 // Initialize global storage.
664 for _, m := range pkg.Members {
665 switch v := m.(type) {
667 cell := zero(deref(v.Type()))
673 // Top-level error handler.
676 if exitCode != 2 || i.mode&DisableRecover != 0 {
679 switch p := recover().(type) {
684 fmt.Fprintln(os.Stderr, "panic:", toString(p.v))
686 fmt.Fprintln(os.Stderr, "panic:", p.Error())
688 fmt.Fprintln(os.Stderr, "panic:", p)
690 fmt.Fprintf(os.Stderr, "panic: unexpected type: %T: %v\n", p, p)
693 // TODO(adonovan): dump panicking interpreter goroutine?
694 // buf := make([]byte, 0x10000)
695 // runtime.Stack(buf, false)
696 // fmt.Fprintln(os.Stderr, string(buf))
697 // (Or dump panicking target goroutine?)
701 call(i, nil, token.NoPos, mainpkg.Func("init"), nil)
702 if mainFn := mainpkg.Func("main"); mainFn != nil {
703 call(i, nil, token.NoPos, mainFn, nil)
706 fmt.Fprintln(os.Stderr, "No main function.")
712 // deref returns a pointer's element type; otherwise it returns typ.
713 // TODO(adonovan): Import from ssa?
714 func deref(typ types.Type) types.Type {
715 if p, ok := typ.Underlying().(*types.Pointer); ok {