+++ /dev/null
-// Copyright 2013 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-// Package ssa/interp defines an interpreter for the SSA
-// representation of Go programs.
-//
-// This interpreter is provided as an adjunct for testing the SSA
-// construction algorithm. Its purpose is to provide a minimal
-// metacircular implementation of the dynamic semantics of each SSA
-// instruction. It is not, and will never be, a production-quality Go
-// interpreter.
-//
-// The following is a partial list of Go features that are currently
-// unsupported or incomplete in the interpreter.
-//
-// * Unsafe operations, including all uses of unsafe.Pointer, are
-// impossible to support given the "boxed" value representation we
-// have chosen.
-//
-// * The reflect package is only partially implemented.
-//
-// * The "testing" package is no longer supported because it
-// depends on low-level details that change too often.
-//
-// * "sync/atomic" operations are not atomic due to the "boxed" value
-// representation: it is not possible to read, modify and write an
-// interface value atomically. As a consequence, Mutexes are currently
-// broken.
-//
-// * recover is only partially implemented. Also, the interpreter
-// makes no attempt to distinguish target panics from interpreter
-// crashes.
-//
-// * the sizes of the int, uint and uintptr types in the target
-// program are assumed to be the same as those of the interpreter
-// itself.
-//
-// * all values occupy space, even those of types defined by the spec
-// to have zero size, e.g. struct{}. This can cause asymptotic
-// performance degradation.
-//
-// * os.Exit is implemented using panic, causing deferred functions to
-// run.
-package interp // import "golang.org/x/tools/go/ssa/interp"
-
-import (
- "fmt"
- "go/token"
- "go/types"
- "os"
- "reflect"
- "runtime"
- "sync/atomic"
-
- "golang.org/x/tools/go/ssa"
-)
-
-type continuation int
-
-const (
- kNext continuation = iota
- kReturn
- kJump
-)
-
-// Mode is a bitmask of options affecting the interpreter.
-type Mode uint
-
-const (
- DisableRecover Mode = 1 << iota // Disable recover() in target programs; show interpreter crash instead.
- EnableTracing // Print a trace of all instructions as they are interpreted.
-)
-
-type methodSet map[string]*ssa.Function
-
-// State shared between all interpreted goroutines.
-type interpreter struct {
- osArgs []value // the value of os.Args
- prog *ssa.Program // the SSA program
- globals map[ssa.Value]*value // addresses of global variables (immutable)
- mode Mode // interpreter options
- reflectPackage *ssa.Package // the fake reflect package
- errorMethods methodSet // the method set of reflect.error, which implements the error interface.
- rtypeMethods methodSet // the method set of rtype, which implements the reflect.Type interface.
- runtimeErrorString types.Type // the runtime.errorString type
- sizes types.Sizes // the effective type-sizing function
- goroutines int32 // atomically updated
-}
-
-type deferred struct {
- fn value
- args []value
- instr *ssa.Defer
- tail *deferred
-}
-
-type frame struct {
- i *interpreter
- caller *frame
- fn *ssa.Function
- block, prevBlock *ssa.BasicBlock
- env map[ssa.Value]value // dynamic values of SSA variables
- locals []value
- defers *deferred
- result value
- panicking bool
- panic interface{}
-}
-
-func (fr *frame) get(key ssa.Value) value {
- switch key := key.(type) {
- case nil:
- // Hack; simplifies handling of optional attributes
- // such as ssa.Slice.{Low,High}.
- return nil
- case *ssa.Function, *ssa.Builtin:
- return key
- case *ssa.Const:
- return constValue(key)
- case *ssa.Global:
- if r, ok := fr.i.globals[key]; ok {
- return r
- }
- }
- if r, ok := fr.env[key]; ok {
- return r
- }
- panic(fmt.Sprintf("get: no value for %T: %v", key, key.Name()))
-}
-
-// runDefer runs a deferred call d.
-// It always returns normally, but may set or clear fr.panic.
-//
-func (fr *frame) runDefer(d *deferred) {
- if fr.i.mode&EnableTracing != 0 {
- fmt.Fprintf(os.Stderr, "%s: invoking deferred function call\n",
- fr.i.prog.Fset.Position(d.instr.Pos()))
- }
- var ok bool
- defer func() {
- if !ok {
- // Deferred call created a new state of panic.
- fr.panicking = true
- fr.panic = recover()
- }
- }()
- call(fr.i, fr, d.instr.Pos(), d.fn, d.args)
- ok = true
-}
-
-// runDefers executes fr's deferred function calls in LIFO order.
-//
-// On entry, fr.panicking indicates a state of panic; if
-// true, fr.panic contains the panic value.
-//
-// On completion, if a deferred call started a panic, or if no
-// deferred call recovered from a previous state of panic, then
-// runDefers itself panics after the last deferred call has run.
-//
-// If there was no initial state of panic, or it was recovered from,
-// runDefers returns normally.
-//
-func (fr *frame) runDefers() {
- for d := fr.defers; d != nil; d = d.tail {
- fr.runDefer(d)
- }
- fr.defers = nil
- if fr.panicking {
- panic(fr.panic) // new panic, or still panicking
- }
-}
-
-// lookupMethod returns the method set for type typ, which may be one
-// of the interpreter's fake types.
-func lookupMethod(i *interpreter, typ types.Type, meth *types.Func) *ssa.Function {
- switch typ {
- case rtypeType:
- return i.rtypeMethods[meth.Id()]
- case errorType:
- return i.errorMethods[meth.Id()]
- }
- return i.prog.LookupMethod(typ, meth.Pkg(), meth.Name())
-}
-
-// visitInstr interprets a single ssa.Instruction within the activation
-// record frame. It returns a continuation value indicating where to
-// read the next instruction from.
-func visitInstr(fr *frame, instr ssa.Instruction) continuation {
- switch instr := instr.(type) {
- case *ssa.DebugRef:
- // no-op
-
- case *ssa.UnOp:
- fr.env[instr] = unop(instr, fr.get(instr.X))
-
- case *ssa.BinOp:
- fr.env[instr] = binop(instr.Op, instr.X.Type(), fr.get(instr.X), fr.get(instr.Y))
-
- case *ssa.Call:
- fn, args := prepareCall(fr, &instr.Call)
- fr.env[instr] = call(fr.i, fr, instr.Pos(), fn, args)
-
- case *ssa.ChangeInterface:
- fr.env[instr] = fr.get(instr.X)
-
- case *ssa.ChangeType:
- fr.env[instr] = fr.get(instr.X) // (can't fail)
-
- case *ssa.Convert:
- fr.env[instr] = conv(instr.Type(), instr.X.Type(), fr.get(instr.X))
-
- case *ssa.MakeInterface:
- fr.env[instr] = iface{t: instr.X.Type(), v: fr.get(instr.X)}
-
- case *ssa.Extract:
- fr.env[instr] = fr.get(instr.Tuple).(tuple)[instr.Index]
-
- case *ssa.Slice:
- fr.env[instr] = slice(fr.get(instr.X), fr.get(instr.Low), fr.get(instr.High), fr.get(instr.Max))
-
- case *ssa.Return:
- switch len(instr.Results) {
- case 0:
- case 1:
- fr.result = fr.get(instr.Results[0])
- default:
- var res []value
- for _, r := range instr.Results {
- res = append(res, fr.get(r))
- }
- fr.result = tuple(res)
- }
- fr.block = nil
- return kReturn
-
- case *ssa.RunDefers:
- fr.runDefers()
-
- case *ssa.Panic:
- panic(targetPanic{fr.get(instr.X)})
-
- case *ssa.Send:
- fr.get(instr.Chan).(chan value) <- fr.get(instr.X)
-
- case *ssa.Store:
- store(deref(instr.Addr.Type()), fr.get(instr.Addr).(*value), fr.get(instr.Val))
-
- case *ssa.If:
- succ := 1
- if fr.get(instr.Cond).(bool) {
- succ = 0
- }
- fr.prevBlock, fr.block = fr.block, fr.block.Succs[succ]
- return kJump
-
- case *ssa.Jump:
- fr.prevBlock, fr.block = fr.block, fr.block.Succs[0]
- return kJump
-
- case *ssa.Defer:
- fn, args := prepareCall(fr, &instr.Call)
- fr.defers = &deferred{
- fn: fn,
- args: args,
- instr: instr,
- tail: fr.defers,
- }
-
- case *ssa.Go:
- fn, args := prepareCall(fr, &instr.Call)
- atomic.AddInt32(&fr.i.goroutines, 1)
- go func() {
- call(fr.i, nil, instr.Pos(), fn, args)
- atomic.AddInt32(&fr.i.goroutines, -1)
- }()
-
- case *ssa.MakeChan:
- fr.env[instr] = make(chan value, asInt(fr.get(instr.Size)))
-
- case *ssa.Alloc:
- var addr *value
- if instr.Heap {
- // new
- addr = new(value)
- fr.env[instr] = addr
- } else {
- // local
- addr = fr.env[instr].(*value)
- }
- *addr = zero(deref(instr.Type()))
-
- case *ssa.MakeSlice:
- slice := make([]value, asInt(fr.get(instr.Cap)))
- tElt := instr.Type().Underlying().(*types.Slice).Elem()
- for i := range slice {
- slice[i] = zero(tElt)
- }
- fr.env[instr] = slice[:asInt(fr.get(instr.Len))]
-
- case *ssa.MakeMap:
- reserve := 0
- if instr.Reserve != nil {
- reserve = asInt(fr.get(instr.Reserve))
- }
- fr.env[instr] = makeMap(instr.Type().Underlying().(*types.Map).Key(), reserve)
-
- case *ssa.Range:
- fr.env[instr] = rangeIter(fr.get(instr.X), instr.X.Type())
-
- case *ssa.Next:
- fr.env[instr] = fr.get(instr.Iter).(iter).next()
-
- case *ssa.FieldAddr:
- fr.env[instr] = &(*fr.get(instr.X).(*value)).(structure)[instr.Field]
-
- case *ssa.Field:
- fr.env[instr] = fr.get(instr.X).(structure)[instr.Field]
-
- case *ssa.IndexAddr:
- x := fr.get(instr.X)
- idx := fr.get(instr.Index)
- switch x := x.(type) {
- case []value:
- fr.env[instr] = &x[asInt(idx)]
- case *value: // *array
- fr.env[instr] = &(*x).(array)[asInt(idx)]
- default:
- panic(fmt.Sprintf("unexpected x type in IndexAddr: %T", x))
- }
-
- case *ssa.Index:
- fr.env[instr] = fr.get(instr.X).(array)[asInt(fr.get(instr.Index))]
-
- case *ssa.Lookup:
- fr.env[instr] = lookup(instr, fr.get(instr.X), fr.get(instr.Index))
-
- case *ssa.MapUpdate:
- m := fr.get(instr.Map)
- key := fr.get(instr.Key)
- v := fr.get(instr.Value)
- switch m := m.(type) {
- case map[value]value:
- m[key] = v
- case *hashmap:
- m.insert(key.(hashable), v)
- default:
- panic(fmt.Sprintf("illegal map type: %T", m))
- }
-
- case *ssa.TypeAssert:
- fr.env[instr] = typeAssert(fr.i, instr, fr.get(instr.X).(iface))
-
- case *ssa.MakeClosure:
- var bindings []value
- for _, binding := range instr.Bindings {
- bindings = append(bindings, fr.get(binding))
- }
- fr.env[instr] = &closure{instr.Fn.(*ssa.Function), bindings}
-
- case *ssa.Phi:
- for i, pred := range instr.Block().Preds {
- if fr.prevBlock == pred {
- fr.env[instr] = fr.get(instr.Edges[i])
- break
- }
- }
-
- case *ssa.Select:
- var cases []reflect.SelectCase
- if !instr.Blocking {
- cases = append(cases, reflect.SelectCase{
- Dir: reflect.SelectDefault,
- })
- }
- for _, state := range instr.States {
- var dir reflect.SelectDir
- if state.Dir == types.RecvOnly {
- dir = reflect.SelectRecv
- } else {
- dir = reflect.SelectSend
- }
- var send reflect.Value
- if state.Send != nil {
- send = reflect.ValueOf(fr.get(state.Send))
- }
- cases = append(cases, reflect.SelectCase{
- Dir: dir,
- Chan: reflect.ValueOf(fr.get(state.Chan)),
- Send: send,
- })
- }
- chosen, recv, recvOk := reflect.Select(cases)
- if !instr.Blocking {
- chosen-- // default case should have index -1.
- }
- r := tuple{chosen, recvOk}
- for i, st := range instr.States {
- if st.Dir == types.RecvOnly {
- var v value
- if i == chosen && recvOk {
- // No need to copy since send makes an unaliased copy.
- v = recv.Interface().(value)
- } else {
- v = zero(st.Chan.Type().Underlying().(*types.Chan).Elem())
- }
- r = append(r, v)
- }
- }
- fr.env[instr] = r
-
- default:
- panic(fmt.Sprintf("unexpected instruction: %T", instr))
- }
-
- // if val, ok := instr.(ssa.Value); ok {
- // fmt.Println(toString(fr.env[val])) // debugging
- // }
-
- return kNext
-}
-
-// prepareCall determines the function value and argument values for a
-// function call in a Call, Go or Defer instruction, performing
-// interface method lookup if needed.
-//
-func prepareCall(fr *frame, call *ssa.CallCommon) (fn value, args []value) {
- v := fr.get(call.Value)
- if call.Method == nil {
- // Function call.
- fn = v
- } else {
- // Interface method invocation.
- recv := v.(iface)
- if recv.t == nil {
- panic("method invoked on nil interface")
- }
- if f := lookupMethod(fr.i, recv.t, call.Method); f == nil {
- // Unreachable in well-typed programs.
- panic(fmt.Sprintf("method set for dynamic type %v does not contain %s", recv.t, call.Method))
- } else {
- fn = f
- }
- args = append(args, recv.v)
- }
- for _, arg := range call.Args {
- args = append(args, fr.get(arg))
- }
- return
-}
-
-// call interprets a call to a function (function, builtin or closure)
-// fn with arguments args, returning its result.
-// callpos is the position of the callsite.
-//
-func call(i *interpreter, caller *frame, callpos token.Pos, fn value, args []value) value {
- switch fn := fn.(type) {
- case *ssa.Function:
- if fn == nil {
- panic("call of nil function") // nil of func type
- }
- return callSSA(i, caller, callpos, fn, args, nil)
- case *closure:
- return callSSA(i, caller, callpos, fn.Fn, args, fn.Env)
- case *ssa.Builtin:
- return callBuiltin(caller, callpos, fn, args)
- }
- panic(fmt.Sprintf("cannot call %T", fn))
-}
-
-func loc(fset *token.FileSet, pos token.Pos) string {
- if pos == token.NoPos {
- return ""
- }
- return " at " + fset.Position(pos).String()
-}
-
-// callSSA interprets a call to function fn with arguments args,
-// and lexical environment env, returning its result.
-// callpos is the position of the callsite.
-//
-func callSSA(i *interpreter, caller *frame, callpos token.Pos, fn *ssa.Function, args []value, env []value) value {
- if i.mode&EnableTracing != 0 {
- fset := fn.Prog.Fset
- // TODO(adonovan): fix: loc() lies for external functions.
- fmt.Fprintf(os.Stderr, "Entering %s%s.\n", fn, loc(fset, fn.Pos()))
- suffix := ""
- if caller != nil {
- suffix = ", resuming " + caller.fn.String() + loc(fset, callpos)
- }
- defer fmt.Fprintf(os.Stderr, "Leaving %s%s.\n", fn, suffix)
- }
- fr := &frame{
- i: i,
- caller: caller, // for panic/recover
- fn: fn,
- }
- if fn.Parent() == nil {
- name := fn.String()
- if ext := externals[name]; ext != nil {
- if i.mode&EnableTracing != 0 {
- fmt.Fprintln(os.Stderr, "\t(external)")
- }
- return ext(fr, args)
- }
- if fn.Blocks == nil {
- panic("no code for function: " + name)
- }
- }
- fr.env = make(map[ssa.Value]value)
- fr.block = fn.Blocks[0]
- fr.locals = make([]value, len(fn.Locals))
- for i, l := range fn.Locals {
- fr.locals[i] = zero(deref(l.Type()))
- fr.env[l] = &fr.locals[i]
- }
- for i, p := range fn.Params {
- fr.env[p] = args[i]
- }
- for i, fv := range fn.FreeVars {
- fr.env[fv] = env[i]
- }
- for fr.block != nil {
- runFrame(fr)
- }
- // Destroy the locals to avoid accidental use after return.
- for i := range fn.Locals {
- fr.locals[i] = bad{}
- }
- return fr.result
-}
-
-// runFrame executes SSA instructions starting at fr.block and
-// continuing until a return, a panic, or a recovered panic.
-//
-// After a panic, runFrame panics.
-//
-// After a normal return, fr.result contains the result of the call
-// and fr.block is nil.
-//
-// A recovered panic in a function without named return parameters
-// (NRPs) becomes a normal return of the zero value of the function's
-// result type.
-//
-// After a recovered panic in a function with NRPs, fr.result is
-// undefined and fr.block contains the block at which to resume
-// control.
-//
-func runFrame(fr *frame) {
- defer func() {
- if fr.block == nil {
- return // normal return
- }
- if fr.i.mode&DisableRecover != 0 {
- return // let interpreter crash
- }
- fr.panicking = true
- fr.panic = recover()
- if fr.i.mode&EnableTracing != 0 {
- fmt.Fprintf(os.Stderr, "Panicking: %T %v.\n", fr.panic, fr.panic)
- }
- fr.runDefers()
- fr.block = fr.fn.Recover
- }()
-
- for {
- if fr.i.mode&EnableTracing != 0 {
- fmt.Fprintf(os.Stderr, ".%s:\n", fr.block)
- }
- block:
- for _, instr := range fr.block.Instrs {
- if fr.i.mode&EnableTracing != 0 {
- if v, ok := instr.(ssa.Value); ok {
- fmt.Fprintln(os.Stderr, "\t", v.Name(), "=", instr)
- } else {
- fmt.Fprintln(os.Stderr, "\t", instr)
- }
- }
- switch visitInstr(fr, instr) {
- case kReturn:
- return
- case kNext:
- // no-op
- case kJump:
- break block
- }
- }
- }
-}
-
-// doRecover implements the recover() built-in.
-func doRecover(caller *frame) value {
- // recover() must be exactly one level beneath the deferred
- // function (two levels beneath the panicking function) to
- // have any effect. Thus we ignore both "defer recover()" and
- // "defer f() -> g() -> recover()".
- if caller.i.mode&DisableRecover == 0 &&
- caller != nil && !caller.panicking &&
- caller.caller != nil && caller.caller.panicking {
- caller.caller.panicking = false
- p := caller.caller.panic
- caller.caller.panic = nil
-
- // TODO(adonovan): support runtime.Goexit.
- switch p := p.(type) {
- case targetPanic:
- // The target program explicitly called panic().
- return p.v
- case runtime.Error:
- // The interpreter encountered a runtime error.
- return iface{caller.i.runtimeErrorString, p.Error()}
- case string:
- // The interpreter explicitly called panic().
- return iface{caller.i.runtimeErrorString, p}
- default:
- panic(fmt.Sprintf("unexpected panic type %T in target call to recover()", p))
- }
- }
- return iface{}
-}
-
-// setGlobal sets the value of a system-initialized global variable.
-func setGlobal(i *interpreter, pkg *ssa.Package, name string, v value) {
- if g, ok := i.globals[pkg.Var(name)]; ok {
- *g = v
- return
- }
- panic("no global variable: " + pkg.Pkg.Path() + "." + name)
-}
-
-// Interpret interprets the Go program whose main package is mainpkg.
-// mode specifies various interpreter options. filename and args are
-// the initial values of os.Args for the target program. sizes is the
-// effective type-sizing function for this program.
-//
-// Interpret returns the exit code of the program: 2 for panic (like
-// gc does), or the argument to os.Exit for normal termination.
-//
-// The SSA program must include the "runtime" package.
-//
-func Interpret(mainpkg *ssa.Package, mode Mode, sizes types.Sizes, filename string, args []string) (exitCode int) {
- i := &interpreter{
- prog: mainpkg.Prog,
- globals: make(map[ssa.Value]*value),
- mode: mode,
- sizes: sizes,
- goroutines: 1,
- }
- runtimePkg := i.prog.ImportedPackage("runtime")
- if runtimePkg == nil {
- panic("ssa.Program doesn't include runtime package")
- }
- i.runtimeErrorString = runtimePkg.Type("errorString").Object().Type()
-
- initReflect(i)
-
- i.osArgs = append(i.osArgs, filename)
- for _, arg := range args {
- i.osArgs = append(i.osArgs, arg)
- }
-
- for _, pkg := range i.prog.AllPackages() {
- // Initialize global storage.
- for _, m := range pkg.Members {
- switch v := m.(type) {
- case *ssa.Global:
- cell := zero(deref(v.Type()))
- i.globals[v] = &cell
- }
- }
- }
-
- // Top-level error handler.
- exitCode = 2
- defer func() {
- if exitCode != 2 || i.mode&DisableRecover != 0 {
- return
- }
- switch p := recover().(type) {
- case exitPanic:
- exitCode = int(p)
- return
- case targetPanic:
- fmt.Fprintln(os.Stderr, "panic:", toString(p.v))
- case runtime.Error:
- fmt.Fprintln(os.Stderr, "panic:", p.Error())
- case string:
- fmt.Fprintln(os.Stderr, "panic:", p)
- default:
- fmt.Fprintf(os.Stderr, "panic: unexpected type: %T: %v\n", p, p)
- }
-
- // TODO(adonovan): dump panicking interpreter goroutine?
- // buf := make([]byte, 0x10000)
- // runtime.Stack(buf, false)
- // fmt.Fprintln(os.Stderr, string(buf))
- // (Or dump panicking target goroutine?)
- }()
-
- // Run!
- call(i, nil, token.NoPos, mainpkg.Func("init"), nil)
- if mainFn := mainpkg.Func("main"); mainFn != nil {
- call(i, nil, token.NoPos, mainFn, nil)
- exitCode = 0
- } else {
- fmt.Fprintln(os.Stderr, "No main function.")
- exitCode = 1
- }
- return
-}
-
-// deref returns a pointer's element type; otherwise it returns typ.
-// TODO(adonovan): Import from ssa?
-func deref(typ types.Type) types.Type {
- if p, ok := typ.Underlying().(*types.Pointer); ok {
- return p.Elem()
- }
- return typ
-}
projects / dotfiles / .git / blobdiff