1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45 package interp
46
47 import (
48 "fmt"
49 "go/token"
50 "go/types"
51 "os"
52 "reflect"
53 "runtime"
54 "sync/atomic"
55
56 "golang.org/x/tools/go/ssa"
57 )
58
59 type continuation int
60
61 const (
62 kNext continuation = iota
63 kReturn
64 kJump
65 )
66
67
68 type Mode uint
69
70 const (
71 DisableRecover Mode = 1 << iota
72 EnableTracing
73 )
74
75 type methodSet map[string]*ssa.Function
76
77
78 type interpreter struct {
79 osArgs []value
80 prog *ssa.Program
81 globals map[*ssa.Global]*value
82 mode Mode
83 reflectPackage *ssa.Package
84 errorMethods methodSet
85 rtypeMethods methodSet
86 runtimeErrorString types.Type
87 sizes types.Sizes
88 goroutines int32
89 }
90
91 type deferred struct {
92 fn value
93 args []value
94 instr *ssa.Defer
95 tail *deferred
96 }
97
98 type frame struct {
99 i *interpreter
100 caller *frame
101 fn *ssa.Function
102 block, prevBlock *ssa.BasicBlock
103 env map[ssa.Value]value
104 locals []value
105 defers *deferred
106 result value
107 panicking bool
108 panic interface{}
109 }
110
111 func (fr *frame) get(key ssa.Value) value {
112 switch key := key.(type) {
113 case nil:
114
115
116 return nil
117 case *ssa.Function, *ssa.Builtin:
118 return key
119 case *ssa.Const:
120 return constValue(key)
121 case *ssa.Global:
122 if r, ok := fr.i.globals[key]; ok {
123 return r
124 }
125 }
126 if r, ok := fr.env[key]; ok {
127 return r
128 }
129 panic(fmt.Sprintf("get: no value for %T: %v", key, key.Name()))
130 }
131
132
133
134 func (fr *frame) runDefer(d *deferred) {
135 if fr.i.mode&EnableTracing != 0 {
136 fmt.Fprintf(os.Stderr, "%s: invoking deferred function call\n",
137 fr.i.prog.Fset.Position(d.instr.Pos()))
138 }
139 var ok bool
140 defer func() {
141 if !ok {
142
143 fr.panicking = true
144 fr.panic = recover()
145 }
146 }()
147 call(fr.i, fr, d.instr.Pos(), d.fn, d.args)
148 ok = true
149 }
150
151
152
153
154
155
156
157
158
159
160
161
162 func (fr *frame) runDefers() {
163 for d := fr.defers; d != nil; d = d.tail {
164 fr.runDefer(d)
165 }
166 fr.defers = nil
167 if fr.panicking {
168 panic(fr.panic)
169 }
170 }
171
172
173
174 func lookupMethod(i *interpreter, typ types.Type, meth *types.Func) *ssa.Function {
175 switch typ {
176 case rtypeType:
177 return i.rtypeMethods[meth.Id()]
178 case errorType:
179 return i.errorMethods[meth.Id()]
180 }
181 return i.prog.LookupMethod(typ, meth.Pkg(), meth.Name())
182 }
183
184
185
186
187 func visitInstr(fr *frame, instr ssa.Instruction) continuation {
188 switch instr := instr.(type) {
189 case *ssa.DebugRef:
190
191
192 case *ssa.UnOp:
193 fr.env[instr] = unop(instr, fr.get(instr.X))
194
195 case *ssa.BinOp:
196 fr.env[instr] = binop(instr.Op, instr.X.Type(), fr.get(instr.X), fr.get(instr.Y))
197
198 case *ssa.Call:
199 fn, args := prepareCall(fr, &instr.Call)
200 fr.env[instr] = call(fr.i, fr, instr.Pos(), fn, args)
201
202 case *ssa.ChangeInterface:
203 fr.env[instr] = fr.get(instr.X)
204
205 case *ssa.ChangeType:
206 fr.env[instr] = fr.get(instr.X)
207
208 case *ssa.Convert:
209 fr.env[instr] = conv(instr.Type(), instr.X.Type(), fr.get(instr.X))
210
211 case *ssa.SliceToArrayPointer:
212 fr.env[instr] = sliceToArrayPointer(instr.Type(), instr.X.Type(), fr.get(instr.X))
213
214 case *ssa.MakeInterface:
215 fr.env[instr] = iface{t: instr.X.Type(), v: fr.get(instr.X)}
216
217 case *ssa.Extract:
218 fr.env[instr] = fr.get(instr.Tuple).(tuple)[instr.Index]
219
220 case *ssa.Slice:
221 fr.env[instr] = slice(fr.get(instr.X), fr.get(instr.Low), fr.get(instr.High), fr.get(instr.Max))
222
223 case *ssa.Return:
224 switch len(instr.Results) {
225 case 0:
226 case 1:
227 fr.result = fr.get(instr.Results[0])
228 default:
229 var res []value
230 for _, r := range instr.Results {
231 res = append(res, fr.get(r))
232 }
233 fr.result = tuple(res)
234 }
235 fr.block = nil
236 return kReturn
237
238 case *ssa.RunDefers:
239 fr.runDefers()
240
241 case *ssa.Panic:
242 panic(targetPanic{fr.get(instr.X)})
243
244 case *ssa.Send:
245 fr.get(instr.Chan).(chan value) <- fr.get(instr.X)
246
247 case *ssa.Store:
248 store(deref(instr.Addr.Type()), fr.get(instr.Addr).(*value), fr.get(instr.Val))
249
250 case *ssa.If:
251 succ := 1
252 if fr.get(instr.Cond).(bool) {
253 succ = 0
254 }
255 fr.prevBlock, fr.block = fr.block, fr.block.Succs[succ]
256 return kJump
257
258 case *ssa.Jump:
259 fr.prevBlock, fr.block = fr.block, fr.block.Succs[0]
260 return kJump
261
262 case *ssa.Defer:
263 fn, args := prepareCall(fr, &instr.Call)
264 fr.defers = &deferred{
265 fn: fn,
266 args: args,
267 instr: instr,
268 tail: fr.defers,
269 }
270
271 case *ssa.Go:
272 fn, args := prepareCall(fr, &instr.Call)
273 atomic.AddInt32(&fr.i.goroutines, 1)
274 go func() {
275 call(fr.i, nil, instr.Pos(), fn, args)
276 atomic.AddInt32(&fr.i.goroutines, -1)
277 }()
278
279 case *ssa.MakeChan:
280 fr.env[instr] = make(chan value, asInt64(fr.get(instr.Size)))
281
282 case *ssa.Alloc:
283 var addr *value
284 if instr.Heap {
285
286 addr = new(value)
287 fr.env[instr] = addr
288 } else {
289
290 addr = fr.env[instr].(*value)
291 }
292 *addr = zero(deref(instr.Type()))
293
294 case *ssa.MakeSlice:
295 slice := make([]value, asInt64(fr.get(instr.Cap)))
296 tElt := instr.Type().Underlying().(*types.Slice).Elem()
297 for i := range slice {
298 slice[i] = zero(tElt)
299 }
300 fr.env[instr] = slice[:asInt64(fr.get(instr.Len))]
301
302 case *ssa.MakeMap:
303 var reserve int64
304 if instr.Reserve != nil {
305 reserve = asInt64(fr.get(instr.Reserve))
306 }
307 if !fitsInt(reserve, fr.i.sizes) {
308 panic(fmt.Sprintf("ssa.MakeMap.Reserve value %d does not fit in int", reserve))
309 }
310 fr.env[instr] = makeMap(instr.Type().Underlying().(*types.Map).Key(), reserve)
311
312 case *ssa.Range:
313 fr.env[instr] = rangeIter(fr.get(instr.X), instr.X.Type())
314
315 case *ssa.Next:
316 fr.env[instr] = fr.get(instr.Iter).(iter).next()
317
318 case *ssa.FieldAddr:
319 fr.env[instr] = &(*fr.get(instr.X).(*value)).(structure)[instr.Field]
320
321 case *ssa.Field:
322 fr.env[instr] = fr.get(instr.X).(structure)[instr.Field]
323
324 case *ssa.IndexAddr:
325 x := fr.get(instr.X)
326 idx := fr.get(instr.Index)
327 switch x := x.(type) {
328 case []value:
329 fr.env[instr] = &x[asInt64(idx)]
330 case *value:
331 fr.env[instr] = &(*x).(array)[asInt64(idx)]
332 default:
333 panic(fmt.Sprintf("unexpected x type in IndexAddr: %T", x))
334 }
335
336 case *ssa.Index:
337 x := fr.get(instr.X)
338 idx := fr.get(instr.Index)
339
340 switch x := x.(type) {
341 case array:
342 fr.env[instr] = x[asInt64(idx)]
343 case string:
344 fr.env[instr] = x[asInt64(idx)]
345 default:
346 panic(fmt.Sprintf("unexpected x type in Index: %T", x))
347 }
348
349 case *ssa.Lookup:
350 fr.env[instr] = lookup(instr, fr.get(instr.X), fr.get(instr.Index))
351
352 case *ssa.MapUpdate:
353 m := fr.get(instr.Map)
354 key := fr.get(instr.Key)
355 v := fr.get(instr.Value)
356 switch m := m.(type) {
357 case map[value]value:
358 m[key] = v
359 case *hashmap:
360 m.insert(key.(hashable), v)
361 default:
362 panic(fmt.Sprintf("illegal map type: %T", m))
363 }
364
365 case *ssa.TypeAssert:
366 fr.env[instr] = typeAssert(fr.i, instr, fr.get(instr.X).(iface))
367
368 case *ssa.MakeClosure:
369 var bindings []value
370 for _, binding := range instr.Bindings {
371 bindings = append(bindings, fr.get(binding))
372 }
373 fr.env[instr] = &closure{instr.Fn.(*ssa.Function), bindings}
374
375 case *ssa.Phi:
376 for i, pred := range instr.Block().Preds {
377 if fr.prevBlock == pred {
378 fr.env[instr] = fr.get(instr.Edges[i])
379 break
380 }
381 }
382
383 case *ssa.Select:
384 var cases []reflect.SelectCase
385 if !instr.Blocking {
386 cases = append(cases, reflect.SelectCase{
387 Dir: reflect.SelectDefault,
388 })
389 }
390 for _, state := range instr.States {
391 var dir reflect.SelectDir
392 if state.Dir == types.RecvOnly {
393 dir = reflect.SelectRecv
394 } else {
395 dir = reflect.SelectSend
396 }
397 var send reflect.Value
398 if state.Send != nil {
399 send = reflect.ValueOf(fr.get(state.Send))
400 }
401 cases = append(cases, reflect.SelectCase{
402 Dir: dir,
403 Chan: reflect.ValueOf(fr.get(state.Chan)),
404 Send: send,
405 })
406 }
407 chosen, recv, recvOk := reflect.Select(cases)
408 if !instr.Blocking {
409 chosen--
410 }
411 r := tuple{chosen, recvOk}
412 for i, st := range instr.States {
413 if st.Dir == types.RecvOnly {
414 var v value
415 if i == chosen && recvOk {
416
417 v = recv.Interface().(value)
418 } else {
419 v = zero(st.Chan.Type().Underlying().(*types.Chan).Elem())
420 }
421 r = append(r, v)
422 }
423 }
424 fr.env[instr] = r
425
426 default:
427 panic(fmt.Sprintf("unexpected instruction: %T", instr))
428 }
429
430
431
432
433
434 return kNext
435 }
436
437
438
439
440 func prepareCall(fr *frame, call *ssa.CallCommon) (fn value, args []value) {
441 v := fr.get(call.Value)
442 if call.Method == nil {
443
444 fn = v
445 } else {
446
447 recv := v.(iface)
448 if recv.t == nil {
449 panic("method invoked on nil interface")
450 }
451 if f := lookupMethod(fr.i, recv.t, call.Method); f == nil {
452
453 panic(fmt.Sprintf("method set for dynamic type %v does not contain %s", recv.t, call.Method))
454 } else {
455 fn = f
456 }
457 args = append(args, recv.v)
458 }
459 for _, arg := range call.Args {
460 args = append(args, fr.get(arg))
461 }
462 return
463 }
464
465
466
467
468 func call(i *interpreter, caller *frame, callpos token.Pos, fn value, args []value) value {
469 switch fn := fn.(type) {
470 case *ssa.Function:
471 if fn == nil {
472 panic("call of nil function")
473 }
474 return callSSA(i, caller, callpos, fn, args, nil)
475 case *closure:
476 return callSSA(i, caller, callpos, fn.Fn, args, fn.Env)
477 case *ssa.Builtin:
478 return callBuiltin(caller, callpos, fn, args)
479 }
480 panic(fmt.Sprintf("cannot call %T", fn))
481 }
482
483 func loc(fset *token.FileSet, pos token.Pos) string {
484 if pos == token.NoPos {
485 return ""
486 }
487 return " at " + fset.Position(pos).String()
488 }
489
490
491
492
493 func callSSA(i *interpreter, caller *frame, callpos token.Pos, fn *ssa.Function, args []value, env []value) value {
494 if i.mode&EnableTracing != 0 {
495 fset := fn.Prog.Fset
496
497 fmt.Fprintf(os.Stderr, "Entering %s%s.\n", fn, loc(fset, fn.Pos()))
498 suffix := ""
499 if caller != nil {
500 suffix = ", resuming " + caller.fn.String() + loc(fset, callpos)
501 }
502 defer fmt.Fprintf(os.Stderr, "Leaving %s%s.\n", fn, suffix)
503 }
504 fr := &frame{
505 i: i,
506 caller: caller,
507 fn: fn,
508 }
509 if fn.Parent() == nil {
510 name := fn.String()
511 if ext := externals[name]; ext != nil {
512 if i.mode&EnableTracing != 0 {
513 fmt.Fprintln(os.Stderr, "\t(external)")
514 }
515 return ext(fr, args)
516 }
517 if fn.Blocks == nil {
518 panic("no code for function: " + name)
519 }
520 }
521
522
523 if fn.TypeParams().Len() > 0 && len(fn.TypeArgs()) == 0 {
524 panic("interp requires ssa.BuilderMode to include InstantiateGenerics to execute generics")
525 }
526
527 fr.env = make(map[ssa.Value]value)
528 fr.block = fn.Blocks[0]
529 fr.locals = make([]value, len(fn.Locals))
530 for i, l := range fn.Locals {
531 fr.locals[i] = zero(deref(l.Type()))
532 fr.env[l] = &fr.locals[i]
533 }
534 for i, p := range fn.Params {
535 fr.env[p] = args[i]
536 }
537 for i, fv := range fn.FreeVars {
538 fr.env[fv] = env[i]
539 }
540 for fr.block != nil {
541 runFrame(fr)
542 }
543
544 for i := range fn.Locals {
545 fr.locals[i] = bad{}
546 }
547 return fr.result
548 }
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565 func runFrame(fr *frame) {
566 defer func() {
567 if fr.block == nil {
568 return
569 }
570 if fr.i.mode&DisableRecover != 0 {
571 return
572 }
573 fr.panicking = true
574 fr.panic = recover()
575 if fr.i.mode&EnableTracing != 0 {
576 fmt.Fprintf(os.Stderr, "Panicking: %T %v.\n", fr.panic, fr.panic)
577 }
578 fr.runDefers()
579 fr.block = fr.fn.Recover
580 }()
581
582 for {
583 if fr.i.mode&EnableTracing != 0 {
584 fmt.Fprintf(os.Stderr, ".%s:\n", fr.block)
585 }
586 block:
587 for _, instr := range fr.block.Instrs {
588 if fr.i.mode&EnableTracing != 0 {
589 if v, ok := instr.(ssa.Value); ok {
590 fmt.Fprintln(os.Stderr, "\t", v.Name(), "=", instr)
591 } else {
592 fmt.Fprintln(os.Stderr, "\t", instr)
593 }
594 }
595 switch visitInstr(fr, instr) {
596 case kReturn:
597 return
598 case kNext:
599
600 case kJump:
601 break block
602 }
603 }
604 }
605 }
606
607
608 func doRecover(caller *frame) value {
609
610
611
612
613 if caller.i.mode&DisableRecover == 0 &&
614 caller != nil && !caller.panicking &&
615 caller.caller != nil && caller.caller.panicking {
616 caller.caller.panicking = false
617 p := caller.caller.panic
618 caller.caller.panic = nil
619
620
621 switch p := p.(type) {
622 case targetPanic:
623
624 return p.v
625 case runtime.Error:
626
627 return iface{caller.i.runtimeErrorString, p.Error()}
628 case string:
629
630 return iface{caller.i.runtimeErrorString, p}
631 default:
632 panic(fmt.Sprintf("unexpected panic type %T in target call to recover()", p))
633 }
634 }
635 return iface{}
636 }
637
638
639 func setGlobal(i *interpreter, pkg *ssa.Package, name string, v value) {
640 if g, ok := i.globals[pkg.Var(name)]; ok {
641 *g = v
642 return
643 }
644 panic("no global variable: " + pkg.Pkg.Path() + "." + name)
645 }
646
647
648
649
650
651
652
653
654
655
656
657
658
659 func Interpret(mainpkg *ssa.Package, mode Mode, sizes types.Sizes, filename string, args []string) (exitCode int) {
660 i := &interpreter{
661 prog: mainpkg.Prog,
662 globals: make(map[*ssa.Global]*value),
663 mode: mode,
664 sizes: sizes,
665 goroutines: 1,
666 }
667 runtimePkg := i.prog.ImportedPackage("runtime")
668 if runtimePkg == nil {
669 panic("ssa.Program doesn't include runtime package")
670 }
671 i.runtimeErrorString = runtimePkg.Type("errorString").Object().Type()
672
673 initReflect(i)
674
675 i.osArgs = append(i.osArgs, filename)
676 for _, arg := range args {
677 i.osArgs = append(i.osArgs, arg)
678 }
679
680 for _, pkg := range i.prog.AllPackages() {
681
682 for _, m := range pkg.Members {
683 switch v := m.(type) {
684 case *ssa.Global:
685 cell := zero(deref(v.Type()))
686 i.globals[v] = &cell
687 }
688 }
689 }
690
691
692 exitCode = 2
693 defer func() {
694 if exitCode != 2 || i.mode&DisableRecover != 0 {
695 return
696 }
697 switch p := recover().(type) {
698 case exitPanic:
699 exitCode = int(p)
700 return
701 case targetPanic:
702 fmt.Fprintln(os.Stderr, "panic:", toString(p.v))
703 case runtime.Error:
704 fmt.Fprintln(os.Stderr, "panic:", p.Error())
705 case string:
706 fmt.Fprintln(os.Stderr, "panic:", p)
707 default:
708 fmt.Fprintf(os.Stderr, "panic: unexpected type: %T: %v\n", p, p)
709 }
710
711
712
713
714
715
716 }()
717
718
719 call(i, nil, token.NoPos, mainpkg.Func("init"), nil)
720 if mainFn := mainpkg.Func("main"); mainFn != nil {
721 call(i, nil, token.NoPos, mainFn, nil)
722 exitCode = 0
723 } else {
724 fmt.Fprintln(os.Stderr, "No main function.")
725 exitCode = 1
726 }
727 return
728 }
729
730
731
732 func deref(typ types.Type) types.Type {
733 if p, ok := typ.Underlying().(*types.Pointer); ok {
734 return p.Elem()
735 }
736 return typ
737 }
738
View as plain text