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.
4
5package interp
6
7import (
8	"bytes"
9	"fmt"
10	"go/constant"
11	"go/token"
12	"go/types"
13	"os"
14	"strings"
15	"sync"
16	"unsafe"
17
18	"golang.org/x/tools/go/ssa"
19)
20
21// If the target program panics, the interpreter panics with this type.
22type targetPanic struct {
23	v value
24}
25
26func (p targetPanic) String() string {
27	return toString(p.v)
28}
29
30// If the target program calls exit, the interpreter panics with this type.
31type exitPanic int
32
33// constValue returns the value of the constant with the
34// dynamic type tag appropriate for c.Type().
35func constValue(c *ssa.Const) value {
36	if c.IsNil() {
37		return zero(c.Type()) // typed nil
38	}
39
40	if t, ok := c.Type().Underlying().(*types.Basic); ok {
41		// TODO(adonovan): eliminate untyped constants from SSA form.
42		switch t.Kind() {
43		case types.Bool, types.UntypedBool:
44			return constant.BoolVal(c.Value)
45		case types.Int, types.UntypedInt:
46			// Assume sizeof(int) is same on host and target.
47			return int(c.Int64())
48		case types.Int8:
49			return int8(c.Int64())
50		case types.Int16:
51			return int16(c.Int64())
52		case types.Int32, types.UntypedRune:
53			return int32(c.Int64())
54		case types.Int64:
55			return c.Int64()
56		case types.Uint:
57			// Assume sizeof(uint) is same on host and target.
58			return uint(c.Uint64())
59		case types.Uint8:
60			return uint8(c.Uint64())
61		case types.Uint16:
62			return uint16(c.Uint64())
63		case types.Uint32:
64			return uint32(c.Uint64())
65		case types.Uint64:
66			return c.Uint64()
67		case types.Uintptr:
68			// Assume sizeof(uintptr) is same on host and target.
69			return uintptr(c.Uint64())
70		case types.Float32:
71			return float32(c.Float64())
72		case types.Float64, types.UntypedFloat:
73			return c.Float64()
74		case types.Complex64:
75			return complex64(c.Complex128())
76		case types.Complex128, types.UntypedComplex:
77			return c.Complex128()
78		case types.String, types.UntypedString:
79			if c.Value.Kind() == constant.String {
80				return constant.StringVal(c.Value)
81			}
82			return string(rune(c.Int64()))
83		}
84	}
85
86	panic(fmt.Sprintf("constValue: %s", c))
87}
88
89// asInt converts x, which must be an integer, to an int suitable for
90// use as a slice or array index or operand to make().
91func asInt(x value) int {
92	switch x := x.(type) {
93	case int:
94		return x
95	case int8:
96		return int(x)
97	case int16:
98		return int(x)
99	case int32:
100		return int(x)
101	case int64:
102		return int(x)
103	case uint:
104		return int(x)
105	case uint8:
106		return int(x)
107	case uint16:
108		return int(x)
109	case uint32:
110		return int(x)
111	case uint64:
112		return int(x)
113	case uintptr:
114		return int(x)
115	}
116	panic(fmt.Sprintf("cannot convert %T to int", x))
117}
118
119// asUint64 converts x, which must be an unsigned integer, to a uint64
120// suitable for use as a bitwise shift count.
121func asUint64(x value) uint64 {
122	switch x := x.(type) {
123	case uint:
124		return uint64(x)
125	case uint8:
126		return uint64(x)
127	case uint16:
128		return uint64(x)
129	case uint32:
130		return uint64(x)
131	case uint64:
132		return x
133	case uintptr:
134		return uint64(x)
135	}
136	panic(fmt.Sprintf("cannot convert %T to uint64", x))
137}
138
139// zero returns a new "zero" value of the specified type.
140func zero(t types.Type) value {
141	switch t := t.(type) {
142	case *types.Basic:
143		if t.Kind() == types.UntypedNil {
144			panic("untyped nil has no zero value")
145		}
146		if t.Info()&types.IsUntyped != 0 {
147			// TODO(adonovan): make it an invariant that
148			// this is unreachable.  Currently some
149			// constants have 'untyped' types when they
150			// should be defaulted by the typechecker.
151			t = ssa.DefaultType(t).(*types.Basic)
152		}
153		switch t.Kind() {
154		case types.Bool:
155			return false
156		case types.Int:
157			return int(0)
158		case types.Int8:
159			return int8(0)
160		case types.Int16:
161			return int16(0)
162		case types.Int32:
163			return int32(0)
164		case types.Int64:
165			return int64(0)
166		case types.Uint:
167			return uint(0)
168		case types.Uint8:
169			return uint8(0)
170		case types.Uint16:
171			return uint16(0)
172		case types.Uint32:
173			return uint32(0)
174		case types.Uint64:
175			return uint64(0)
176		case types.Uintptr:
177			return uintptr(0)
178		case types.Float32:
179			return float32(0)
180		case types.Float64:
181			return float64(0)
182		case types.Complex64:
183			return complex64(0)
184		case types.Complex128:
185			return complex128(0)
186		case types.String:
187			return ""
188		case types.UnsafePointer:
189			return unsafe.Pointer(nil)
190		default:
191			panic(fmt.Sprint("zero for unexpected type:", t))
192		}
193	case *types.Pointer:
194		return (*value)(nil)
195	case *types.Array:
196		a := make(array, t.Len())
197		for i := range a {
198			a[i] = zero(t.Elem())
199		}
200		return a
201	case *types.Named:
202		return zero(t.Underlying())
203	case *types.Interface:
204		return iface{} // nil type, methodset and value
205	case *types.Slice:
206		return []value(nil)
207	case *types.Struct:
208		s := make(structure, t.NumFields())
209		for i := range s {
210			s[i] = zero(t.Field(i).Type())
211		}
212		return s
213	case *types.Tuple:
214		if t.Len() == 1 {
215			return zero(t.At(0).Type())
216		}
217		s := make(tuple, t.Len())
218		for i := range s {
219			s[i] = zero(t.At(i).Type())
220		}
221		return s
222	case *types.Chan:
223		return chan value(nil)
224	case *types.Map:
225		if usesBuiltinMap(t.Key()) {
226			return map[value]value(nil)
227		}
228		return (*hashmap)(nil)
229	case *types.Signature:
230		return (*ssa.Function)(nil)
231	}
232	panic(fmt.Sprint("zero: unexpected ", t))
233}
234
235// slice returns x[lo:hi:max].  Any of lo, hi and max may be nil.
236func slice(x, lo, hi, max value) value {
237	var Len, Cap int
238	switch x := x.(type) {
239	case string:
240		Len = len(x)
241	case []value:
242		Len = len(x)
243		Cap = cap(x)
244	case *value: // *array
245		a := (*x).(array)
246		Len = len(a)
247		Cap = cap(a)
248	}
249
250	l := 0
251	if lo != nil {
252		l = asInt(lo)
253	}
254
255	h := Len
256	if hi != nil {
257		h = asInt(hi)
258	}
259
260	m := Cap
261	if max != nil {
262		m = asInt(max)
263	}
264
265	switch x := x.(type) {
266	case string:
267		return x[l:h]
268	case []value:
269		return x[l:h:m]
270	case *value: // *array
271		a := (*x).(array)
272		return []value(a)[l:h:m]
273	}
274	panic(fmt.Sprintf("slice: unexpected X type: %T", x))
275}
276
277// lookup returns x[idx] where x is a map or string.
278func lookup(instr *ssa.Lookup, x, idx value) value {
279	switch x := x.(type) { // map or string
280	case map[value]value, *hashmap:
281		var v value
282		var ok bool
283		switch x := x.(type) {
284		case map[value]value:
285			v, ok = x[idx]
286		case *hashmap:
287			v = x.lookup(idx.(hashable))
288			ok = v != nil
289		}
290		if !ok {
291			v = zero(instr.X.Type().Underlying().(*types.Map).Elem())
292		}
293		if instr.CommaOk {
294			v = tuple{v, ok}
295		}
296		return v
297	case string:
298		return x[asInt(idx)]
299	}
300	panic(fmt.Sprintf("unexpected x type in Lookup: %T", x))
301}
302
303// binop implements all arithmetic and logical binary operators for
304// numeric datatypes and strings.  Both operands must have identical
305// dynamic type.
306//
307func binop(op token.Token, t types.Type, x, y value) value {
308	switch op {
309	case token.ADD:
310		switch x.(type) {
311		case int:
312			return x.(int) + y.(int)
313		case int8:
314			return x.(int8) + y.(int8)
315		case int16:
316			return x.(int16) + y.(int16)
317		case int32:
318			return x.(int32) + y.(int32)
319		case int64:
320			return x.(int64) + y.(int64)
321		case uint:
322			return x.(uint) + y.(uint)
323		case uint8:
324			return x.(uint8) + y.(uint8)
325		case uint16:
326			return x.(uint16) + y.(uint16)
327		case uint32:
328			return x.(uint32) + y.(uint32)
329		case uint64:
330			return x.(uint64) + y.(uint64)
331		case uintptr:
332			return x.(uintptr) + y.(uintptr)
333		case float32:
334			return x.(float32) + y.(float32)
335		case float64:
336			return x.(float64) + y.(float64)
337		case complex64:
338			return x.(complex64) + y.(complex64)
339		case complex128:
340			return x.(complex128) + y.(complex128)
341		case string:
342			return x.(string) + y.(string)
343		}
344
345	case token.SUB:
346		switch x.(type) {
347		case int:
348			return x.(int) - y.(int)
349		case int8:
350			return x.(int8) - y.(int8)
351		case int16:
352			return x.(int16) - y.(int16)
353		case int32:
354			return x.(int32) - y.(int32)
355		case int64:
356			return x.(int64) - y.(int64)
357		case uint:
358			return x.(uint) - y.(uint)
359		case uint8:
360			return x.(uint8) - y.(uint8)
361		case uint16:
362			return x.(uint16) - y.(uint16)
363		case uint32:
364			return x.(uint32) - y.(uint32)
365		case uint64:
366			return x.(uint64) - y.(uint64)
367		case uintptr:
368			return x.(uintptr) - y.(uintptr)
369		case float32:
370			return x.(float32) - y.(float32)
371		case float64:
372			return x.(float64) - y.(float64)
373		case complex64:
374			return x.(complex64) - y.(complex64)
375		case complex128:
376			return x.(complex128) - y.(complex128)
377		}
378
379	case token.MUL:
380		switch x.(type) {
381		case int:
382			return x.(int) * y.(int)
383		case int8:
384			return x.(int8) * y.(int8)
385		case int16:
386			return x.(int16) * y.(int16)
387		case int32:
388			return x.(int32) * y.(int32)
389		case int64:
390			return x.(int64) * y.(int64)
391		case uint:
392			return x.(uint) * y.(uint)
393		case uint8:
394			return x.(uint8) * y.(uint8)
395		case uint16:
396			return x.(uint16) * y.(uint16)
397		case uint32:
398			return x.(uint32) * y.(uint32)
399		case uint64:
400			return x.(uint64) * y.(uint64)
401		case uintptr:
402			return x.(uintptr) * y.(uintptr)
403		case float32:
404			return x.(float32) * y.(float32)
405		case float64:
406			return x.(float64) * y.(float64)
407		case complex64:
408			return x.(complex64) * y.(complex64)
409		case complex128:
410			return x.(complex128) * y.(complex128)
411		}
412
413	case token.QUO:
414		switch x.(type) {
415		case int:
416			return x.(int) / y.(int)
417		case int8:
418			return x.(int8) / y.(int8)
419		case int16:
420			return x.(int16) / y.(int16)
421		case int32:
422			return x.(int32) / y.(int32)
423		case int64:
424			return x.(int64) / y.(int64)
425		case uint:
426			return x.(uint) / y.(uint)
427		case uint8:
428			return x.(uint8) / y.(uint8)
429		case uint16:
430			return x.(uint16) / y.(uint16)
431		case uint32:
432			return x.(uint32) / y.(uint32)
433		case uint64:
434			return x.(uint64) / y.(uint64)
435		case uintptr:
436			return x.(uintptr) / y.(uintptr)
437		case float32:
438			return x.(float32) / y.(float32)
439		case float64:
440			return x.(float64) / y.(float64)
441		case complex64:
442			return x.(complex64) / y.(complex64)
443		case complex128:
444			return x.(complex128) / y.(complex128)
445		}
446
447	case token.REM:
448		switch x.(type) {
449		case int:
450			return x.(int) % y.(int)
451		case int8:
452			return x.(int8) % y.(int8)
453		case int16:
454			return x.(int16) % y.(int16)
455		case int32:
456			return x.(int32) % y.(int32)
457		case int64:
458			return x.(int64) % y.(int64)
459		case uint:
460			return x.(uint) % y.(uint)
461		case uint8:
462			return x.(uint8) % y.(uint8)
463		case uint16:
464			return x.(uint16) % y.(uint16)
465		case uint32:
466			return x.(uint32) % y.(uint32)
467		case uint64:
468			return x.(uint64) % y.(uint64)
469		case uintptr:
470			return x.(uintptr) % y.(uintptr)
471		}
472
473	case token.AND:
474		switch x.(type) {
475		case int:
476			return x.(int) & y.(int)
477		case int8:
478			return x.(int8) & y.(int8)
479		case int16:
480			return x.(int16) & y.(int16)
481		case int32:
482			return x.(int32) & y.(int32)
483		case int64:
484			return x.(int64) & y.(int64)
485		case uint:
486			return x.(uint) & y.(uint)
487		case uint8:
488			return x.(uint8) & y.(uint8)
489		case uint16:
490			return x.(uint16) & y.(uint16)
491		case uint32:
492			return x.(uint32) & y.(uint32)
493		case uint64:
494			return x.(uint64) & y.(uint64)
495		case uintptr:
496			return x.(uintptr) & y.(uintptr)
497		}
498
499	case token.OR:
500		switch x.(type) {
501		case int:
502			return x.(int) | y.(int)
503		case int8:
504			return x.(int8) | y.(int8)
505		case int16:
506			return x.(int16) | y.(int16)
507		case int32:
508			return x.(int32) | y.(int32)
509		case int64:
510			return x.(int64) | y.(int64)
511		case uint:
512			return x.(uint) | y.(uint)
513		case uint8:
514			return x.(uint8) | y.(uint8)
515		case uint16:
516			return x.(uint16) | y.(uint16)
517		case uint32:
518			return x.(uint32) | y.(uint32)
519		case uint64:
520			return x.(uint64) | y.(uint64)
521		case uintptr:
522			return x.(uintptr) | y.(uintptr)
523		}
524
525	case token.XOR:
526		switch x.(type) {
527		case int:
528			return x.(int) ^ y.(int)
529		case int8:
530			return x.(int8) ^ y.(int8)
531		case int16:
532			return x.(int16) ^ y.(int16)
533		case int32:
534			return x.(int32) ^ y.(int32)
535		case int64:
536			return x.(int64) ^ y.(int64)
537		case uint:
538			return x.(uint) ^ y.(uint)
539		case uint8:
540			return x.(uint8) ^ y.(uint8)
541		case uint16:
542			return x.(uint16) ^ y.(uint16)
543		case uint32:
544			return x.(uint32) ^ y.(uint32)
545		case uint64:
546			return x.(uint64) ^ y.(uint64)
547		case uintptr:
548			return x.(uintptr) ^ y.(uintptr)
549		}
550
551	case token.AND_NOT:
552		switch x.(type) {
553		case int:
554			return x.(int) &^ y.(int)
555		case int8:
556			return x.(int8) &^ y.(int8)
557		case int16:
558			return x.(int16) &^ y.(int16)
559		case int32:
560			return x.(int32) &^ y.(int32)
561		case int64:
562			return x.(int64) &^ y.(int64)
563		case uint:
564			return x.(uint) &^ y.(uint)
565		case uint8:
566			return x.(uint8) &^ y.(uint8)
567		case uint16:
568			return x.(uint16) &^ y.(uint16)
569		case uint32:
570			return x.(uint32) &^ y.(uint32)
571		case uint64:
572			return x.(uint64) &^ y.(uint64)
573		case uintptr:
574			return x.(uintptr) &^ y.(uintptr)
575		}
576
577	case token.SHL:
578		y := asUint64(y)
579		switch x.(type) {
580		case int:
581			return x.(int) << y
582		case int8:
583			return x.(int8) << y
584		case int16:
585			return x.(int16) << y
586		case int32:
587			return x.(int32) << y
588		case int64:
589			return x.(int64) << y
590		case uint:
591			return x.(uint) << y
592		case uint8:
593			return x.(uint8) << y
594		case uint16:
595			return x.(uint16) << y
596		case uint32:
597			return x.(uint32) << y
598		case uint64:
599			return x.(uint64) << y
600		case uintptr:
601			return x.(uintptr) << y
602		}
603
604	case token.SHR:
605		y := asUint64(y)
606		switch x.(type) {
607		case int:
608			return x.(int) >> y
609		case int8:
610			return x.(int8) >> y
611		case int16:
612			return x.(int16) >> y
613		case int32:
614			return x.(int32) >> y
615		case int64:
616			return x.(int64) >> y
617		case uint:
618			return x.(uint) >> y
619		case uint8:
620			return x.(uint8) >> y
621		case uint16:
622			return x.(uint16) >> y
623		case uint32:
624			return x.(uint32) >> y
625		case uint64:
626			return x.(uint64) >> y
627		case uintptr:
628			return x.(uintptr) >> y
629		}
630
631	case token.LSS:
632		switch x.(type) {
633		case int:
634			return x.(int) < y.(int)
635		case int8:
636			return x.(int8) < y.(int8)
637		case int16:
638			return x.(int16) < y.(int16)
639		case int32:
640			return x.(int32) < y.(int32)
641		case int64:
642			return x.(int64) < y.(int64)
643		case uint:
644			return x.(uint) < y.(uint)
645		case uint8:
646			return x.(uint8) < y.(uint8)
647		case uint16:
648			return x.(uint16) < y.(uint16)
649		case uint32:
650			return x.(uint32) < y.(uint32)
651		case uint64:
652			return x.(uint64) < y.(uint64)
653		case uintptr:
654			return x.(uintptr) < y.(uintptr)
655		case float32:
656			return x.(float32) < y.(float32)
657		case float64:
658			return x.(float64) < y.(float64)
659		case string:
660			return x.(string) < y.(string)
661		}
662
663	case token.LEQ:
664		switch x.(type) {
665		case int:
666			return x.(int) <= y.(int)
667		case int8:
668			return x.(int8) <= y.(int8)
669		case int16:
670			return x.(int16) <= y.(int16)
671		case int32:
672			return x.(int32) <= y.(int32)
673		case int64:
674			return x.(int64) <= y.(int64)
675		case uint:
676			return x.(uint) <= y.(uint)
677		case uint8:
678			return x.(uint8) <= y.(uint8)
679		case uint16:
680			return x.(uint16) <= y.(uint16)
681		case uint32:
682			return x.(uint32) <= y.(uint32)
683		case uint64:
684			return x.(uint64) <= y.(uint64)
685		case uintptr:
686			return x.(uintptr) <= y.(uintptr)
687		case float32:
688			return x.(float32) <= y.(float32)
689		case float64:
690			return x.(float64) <= y.(float64)
691		case string:
692			return x.(string) <= y.(string)
693		}
694
695	case token.EQL:
696		return eqnil(t, x, y)
697
698	case token.NEQ:
699		return !eqnil(t, x, y)
700
701	case token.GTR:
702		switch x.(type) {
703		case int:
704			return x.(int) > y.(int)
705		case int8:
706			return x.(int8) > y.(int8)
707		case int16:
708			return x.(int16) > y.(int16)
709		case int32:
710			return x.(int32) > y.(int32)
711		case int64:
712			return x.(int64) > y.(int64)
713		case uint:
714			return x.(uint) > y.(uint)
715		case uint8:
716			return x.(uint8) > y.(uint8)
717		case uint16:
718			return x.(uint16) > y.(uint16)
719		case uint32:
720			return x.(uint32) > y.(uint32)
721		case uint64:
722			return x.(uint64) > y.(uint64)
723		case uintptr:
724			return x.(uintptr) > y.(uintptr)
725		case float32:
726			return x.(float32) > y.(float32)
727		case float64:
728			return x.(float64) > y.(float64)
729		case string:
730			return x.(string) > y.(string)
731		}
732
733	case token.GEQ:
734		switch x.(type) {
735		case int:
736			return x.(int) >= y.(int)
737		case int8:
738			return x.(int8) >= y.(int8)
739		case int16:
740			return x.(int16) >= y.(int16)
741		case int32:
742			return x.(int32) >= y.(int32)
743		case int64:
744			return x.(int64) >= y.(int64)
745		case uint:
746			return x.(uint) >= y.(uint)
747		case uint8:
748			return x.(uint8) >= y.(uint8)
749		case uint16:
750			return x.(uint16) >= y.(uint16)
751		case uint32:
752			return x.(uint32) >= y.(uint32)
753		case uint64:
754			return x.(uint64) >= y.(uint64)
755		case uintptr:
756			return x.(uintptr) >= y.(uintptr)
757		case float32:
758			return x.(float32) >= y.(float32)
759		case float64:
760			return x.(float64) >= y.(float64)
761		case string:
762			return x.(string) >= y.(string)
763		}
764	}
765	panic(fmt.Sprintf("invalid binary op: %T %s %T", x, op, y))
766}
767
768// eqnil returns the comparison x == y using the equivalence relation
769// appropriate for type t.
770// If t is a reference type, at most one of x or y may be a nil value
771// of that type.
772//
773func eqnil(t types.Type, x, y value) bool {
774	switch t.Underlying().(type) {
775	case *types.Map, *types.Signature, *types.Slice:
776		// Since these types don't support comparison,
777		// one of the operands must be a literal nil.
778		switch x := x.(type) {
779		case *hashmap:
780			return (x != nil) == (y.(*hashmap) != nil)
781		case map[value]value:
782			return (x != nil) == (y.(map[value]value) != nil)
783		case *ssa.Function:
784			switch y := y.(type) {
785			case *ssa.Function:
786				return (x != nil) == (y != nil)
787			case *closure:
788				return true
789			}
790		case *closure:
791			return (x != nil) == (y.(*ssa.Function) != nil)
792		case []value:
793			return (x != nil) == (y.([]value) != nil)
794		}
795		panic(fmt.Sprintf("eqnil(%s): illegal dynamic type: %T", t, x))
796	}
797
798	return equals(t, x, y)
799}
800
801func unop(instr *ssa.UnOp, x value) value {
802	switch instr.Op {
803	case token.ARROW: // receive
804		v, ok := <-x.(chan value)
805		if !ok {
806			v = zero(instr.X.Type().Underlying().(*types.Chan).Elem())
807		}
808		if instr.CommaOk {
809			v = tuple{v, ok}
810		}
811		return v
812	case token.SUB:
813		switch x := x.(type) {
814		case int:
815			return -x
816		case int8:
817			return -x
818		case int16:
819			return -x
820		case int32:
821			return -x
822		case int64:
823			return -x
824		case uint:
825			return -x
826		case uint8:
827			return -x
828		case uint16:
829			return -x
830		case uint32:
831			return -x
832		case uint64:
833			return -x
834		case uintptr:
835			return -x
836		case float32:
837			return -x
838		case float64:
839			return -x
840		case complex64:
841			return -x
842		case complex128:
843			return -x
844		}
845	case token.MUL:
846		return load(deref(instr.X.Type()), x.(*value))
847	case token.NOT:
848		return !x.(bool)
849	case token.XOR:
850		switch x := x.(type) {
851		case int:
852			return ^x
853		case int8:
854			return ^x
855		case int16:
856			return ^x
857		case int32:
858			return ^x
859		case int64:
860			return ^x
861		case uint:
862			return ^x
863		case uint8:
864			return ^x
865		case uint16:
866			return ^x
867		case uint32:
868			return ^x
869		case uint64:
870			return ^x
871		case uintptr:
872			return ^x
873		}
874	}
875	panic(fmt.Sprintf("invalid unary op %s %T", instr.Op, x))
876}
877
878// typeAssert checks whether dynamic type of itf is instr.AssertedType.
879// It returns the extracted value on success, and panics on failure,
880// unless instr.CommaOk, in which case it always returns a "value,ok" tuple.
881//
882func typeAssert(i *interpreter, instr *ssa.TypeAssert, itf iface) value {
883	var v value
884	err := ""
885	if itf.t == nil {
886		err = fmt.Sprintf("interface conversion: interface is nil, not %s", instr.AssertedType)
887
888	} else if idst, ok := instr.AssertedType.Underlying().(*types.Interface); ok {
889		v = itf
890		err = checkInterface(i, idst, itf)
891
892	} else if types.Identical(itf.t, instr.AssertedType) {
893		v = itf.v // extract value
894
895	} else {
896		err = fmt.Sprintf("interface conversion: interface is %s, not %s", itf.t, instr.AssertedType)
897	}
898
899	if err != "" {
900		if !instr.CommaOk {
901			panic(err)
902		}
903		return tuple{zero(instr.AssertedType), false}
904	}
905	if instr.CommaOk {
906		return tuple{v, true}
907	}
908	return v
909}
910
911// If CapturedOutput is non-nil, all writes by the interpreted program
912// to file descriptors 1 and 2 will also be written to CapturedOutput.
913//
914// (The $GOROOT/test system requires that the test be considered a
915// failure if "BUG" appears in the combined stdout/stderr output, even
916// if it exits zero.  This is a global variable shared by all
917// interpreters in the same process.)
918//
919var CapturedOutput *bytes.Buffer
920var capturedOutputMu sync.Mutex
921
922// write writes bytes b to the target program's standard output.
923// The print/println built-ins and the write() system call funnel
924// through here so they can be captured by the test driver.
925func print(b []byte) (int, error) {
926	if CapturedOutput != nil {
927		capturedOutputMu.Lock()
928		CapturedOutput.Write(b) // ignore errors
929		capturedOutputMu.Unlock()
930	}
931	return os.Stdout.Write(b)
932}
933
934// callBuiltin interprets a call to builtin fn with arguments args,
935// returning its result.
936func callBuiltin(caller *frame, callpos token.Pos, fn *ssa.Builtin, args []value) value {
937	switch fn.Name() {
938	case "append":
939		if len(args) == 1 {
940			return args[0]
941		}
942		if s, ok := args[1].(string); ok {
943			// append([]byte, ...string) []byte
944			arg0 := args[0].([]value)
945			for i := 0; i < len(s); i++ {
946				arg0 = append(arg0, s[i])
947			}
948			return arg0
949		}
950		// append([]T, ...[]T) []T
951		return append(args[0].([]value), args[1].([]value)...)
952
953	case "copy": // copy([]T, []T) int or copy([]byte, string) int
954		src := args[1]
955		if _, ok := src.(string); ok {
956			params := fn.Type().(*types.Signature).Params()
957			src = conv(params.At(0).Type(), params.At(1).Type(), src)
958		}
959		return copy(args[0].([]value), src.([]value))
960
961	case "close": // close(chan T)
962		close(args[0].(chan value))
963		return nil
964
965	case "delete": // delete(map[K]value, K)
966		switch m := args[0].(type) {
967		case map[value]value:
968			delete(m, args[1])
969		case *hashmap:
970			m.delete(args[1].(hashable))
971		default:
972			panic(fmt.Sprintf("illegal map type: %T", m))
973		}
974		return nil
975
976	case "print", "println": // print(any, ...)
977		ln := fn.Name() == "println"
978		var buf bytes.Buffer
979		for i, arg := range args {
980			if i > 0 && ln {
981				buf.WriteRune(' ')
982			}
983			buf.WriteString(toString(arg))
984		}
985		if ln {
986			buf.WriteRune('\n')
987		}
988		print(buf.Bytes())
989		return nil
990
991	case "len":
992		switch x := args[0].(type) {
993		case string:
994			return len(x)
995		case array:
996			return len(x)
997		case *value:
998			return len((*x).(array))
999		case []value:
1000			return len(x)
1001		case map[value]value:
1002			return len(x)
1003		case *hashmap:
1004			return x.len()
1005		case chan value:
1006			return len(x)
1007		default:
1008			panic(fmt.Sprintf("len: illegal operand: %T", x))
1009		}
1010
1011	case "cap":
1012		switch x := args[0].(type) {
1013		case array:
1014			return cap(x)
1015		case *value:
1016			return cap((*x).(array))
1017		case []value:
1018			return cap(x)
1019		case chan value:
1020			return cap(x)
1021		default:
1022			panic(fmt.Sprintf("cap: illegal operand: %T", x))
1023		}
1024
1025	case "real":
1026		switch c := args[0].(type) {
1027		case complex64:
1028			return real(c)
1029		case complex128:
1030			return real(c)
1031		default:
1032			panic(fmt.Sprintf("real: illegal operand: %T", c))
1033		}
1034
1035	case "imag":
1036		switch c := args[0].(type) {
1037		case complex64:
1038			return imag(c)
1039		case complex128:
1040			return imag(c)
1041		default:
1042			panic(fmt.Sprintf("imag: illegal operand: %T", c))
1043		}
1044
1045	case "complex":
1046		switch f := args[0].(type) {
1047		case float32:
1048			return complex(f, args[1].(float32))
1049		case float64:
1050			return complex(f, args[1].(float64))
1051		default:
1052			panic(fmt.Sprintf("complex: illegal operand: %T", f))
1053		}
1054
1055	case "panic":
1056		// ssa.Panic handles most cases; this is only for "go
1057		// panic" or "defer panic".
1058		panic(targetPanic{args[0]})
1059
1060	case "recover":
1061		return doRecover(caller)
1062
1063	case "ssa:wrapnilchk":
1064		recv := args[0]
1065		if recv.(*value) == nil {
1066			recvType := args[1]
1067			methodName := args[2]
1068			panic(fmt.Sprintf("value method (%s).%s called using nil *%s pointer",
1069				recvType, methodName, recvType))
1070		}
1071		return recv
1072	}
1073
1074	panic("unknown built-in: " + fn.Name())
1075}
1076
1077func rangeIter(x value, t types.Type) iter {
1078	switch x := x.(type) {
1079	case map[value]value:
1080		// TODO(adonovan): fix: leaks goroutines and channels
1081		// on each incomplete map iteration.  We need to open
1082		// up an iteration interface using the
1083		// reflect.(Value).MapKeys machinery.
1084		it := make(mapIter)
1085		go func() {
1086			for k, v := range x {
1087				it <- [2]value{k, v}
1088			}
1089			close(it)
1090		}()
1091		return it
1092	case *hashmap:
1093		// TODO(adonovan): fix: leaks goroutines and channels
1094		// on each incomplete map iteration.  We need to open
1095		// up an iteration interface using the
1096		// reflect.(Value).MapKeys machinery.
1097		it := make(mapIter)
1098		go func() {
1099			for _, e := range x.entries() {
1100				for e != nil {
1101					it <- [2]value{e.key, e.value}
1102					e = e.next
1103				}
1104			}
1105			close(it)
1106		}()
1107		return it
1108	case string:
1109		return &stringIter{Reader: strings.NewReader(x)}
1110	}
1111	panic(fmt.Sprintf("cannot range over %T", x))
1112}
1113
1114// widen widens a basic typed value x to the widest type of its
1115// category, one of:
1116//   bool, int64, uint64, float64, complex128, string.
1117// This is inefficient but reduces the size of the cross-product of
1118// cases we have to consider.
1119//
1120func widen(x value) value {
1121	switch y := x.(type) {
1122	case bool, int64, uint64, float64, complex128, string, unsafe.Pointer:
1123		return x
1124	case int:
1125		return int64(y)
1126	case int8:
1127		return int64(y)
1128	case int16:
1129		return int64(y)
1130	case int32:
1131		return int64(y)
1132	case uint:
1133		return uint64(y)
1134	case uint8:
1135		return uint64(y)
1136	case uint16:
1137		return uint64(y)
1138	case uint32:
1139		return uint64(y)
1140	case uintptr:
1141		return uint64(y)
1142	case float32:
1143		return float64(y)
1144	case complex64:
1145		return complex128(y)
1146	}
1147	panic(fmt.Sprintf("cannot widen %T", x))
1148}
1149
1150// conv converts the value x of type t_src to type t_dst and returns
1151// the result.
1152// Possible cases are described with the ssa.Convert operator.
1153//
1154func conv(t_dst, t_src types.Type, x value) value {
1155	ut_src := t_src.Underlying()
1156	ut_dst := t_dst.Underlying()
1157
1158	// Destination type is not an "untyped" type.
1159	if b, ok := ut_dst.(*types.Basic); ok && b.Info()&types.IsUntyped != 0 {
1160		panic("oops: conversion to 'untyped' type: " + b.String())
1161	}
1162
1163	// Nor is it an interface type.
1164	if _, ok := ut_dst.(*types.Interface); ok {
1165		if _, ok := ut_src.(*types.Interface); ok {
1166			panic("oops: Convert should be ChangeInterface")
1167		} else {
1168			panic("oops: Convert should be MakeInterface")
1169		}
1170	}
1171
1172	// Remaining conversions:
1173	//    + untyped string/number/bool constant to a specific
1174	//      representation.
1175	//    + conversions between non-complex numeric types.
1176	//    + conversions between complex numeric types.
1177	//    + integer/[]byte/[]rune -> string.
1178	//    + string -> []byte/[]rune.
1179	//
1180	// All are treated the same: first we extract the value to the
1181	// widest representation (int64, uint64, float64, complex128,
1182	// or string), then we convert it to the desired type.
1183
1184	switch ut_src := ut_src.(type) {
1185	case *types.Pointer:
1186		switch ut_dst := ut_dst.(type) {
1187		case *types.Basic:
1188			// *value to unsafe.Pointer?
1189			if ut_dst.Kind() == types.UnsafePointer {
1190				return unsafe.Pointer(x.(*value))
1191			}
1192		}
1193
1194	case *types.Slice:
1195		// []byte or []rune -> string
1196		// TODO(adonovan): fix: type B byte; conv([]B -> string).
1197		switch ut_src.Elem().(*types.Basic).Kind() {
1198		case types.Byte:
1199			x := x.([]value)
1200			b := make([]byte, 0, len(x))
1201			for i := range x {
1202				b = append(b, x[i].(byte))
1203			}
1204			return string(b)
1205
1206		case types.Rune:
1207			x := x.([]value)
1208			r := make([]rune, 0, len(x))
1209			for i := range x {
1210				r = append(r, x[i].(rune))
1211			}
1212			return string(r)
1213		}
1214
1215	case *types.Basic:
1216		x = widen(x)
1217
1218		// integer -> string?
1219		// TODO(adonovan): fix: test integer -> named alias of string.
1220		if ut_src.Info()&types.IsInteger != 0 {
1221			if ut_dst, ok := ut_dst.(*types.Basic); ok && ut_dst.Kind() == types.String {
1222				return string(asInt(x))
1223			}
1224		}
1225
1226		// string -> []rune, []byte or string?
1227		if s, ok := x.(string); ok {
1228			switch ut_dst := ut_dst.(type) {
1229			case *types.Slice:
1230				var res []value
1231				// TODO(adonovan): fix: test named alias of rune, byte.
1232				switch ut_dst.Elem().(*types.Basic).Kind() {
1233				case types.Rune:
1234					for _, r := range []rune(s) {
1235						res = append(res, r)
1236					}
1237					return res
1238				case types.Byte:
1239					for _, b := range []byte(s) {
1240						res = append(res, b)
1241					}
1242					return res
1243				}
1244			case *types.Basic:
1245				if ut_dst.Kind() == types.String {
1246					return x.(string)
1247				}
1248			}
1249			break // fail: no other conversions for string
1250		}
1251
1252		// unsafe.Pointer -> *value
1253		if ut_src.Kind() == types.UnsafePointer {
1254			// TODO(adonovan): this is wrong and cannot
1255			// really be fixed with the current design.
1256			//
1257			// return (*value)(x.(unsafe.Pointer))
1258			// creates a new pointer of a different
1259			// type but the underlying interface value
1260			// knows its "true" type and so cannot be
1261			// meaningfully used through the new pointer.
1262			//
1263			// To make this work, the interpreter needs to
1264			// simulate the memory layout of a real
1265			// compiled implementation.
1266			//
1267			// To at least preserve type-safety, we'll
1268			// just return the zero value of the
1269			// destination type.
1270			return zero(t_dst)
1271		}
1272
1273		// Conversions between complex numeric types?
1274		if ut_src.Info()&types.IsComplex != 0 {
1275			switch ut_dst.(*types.Basic).Kind() {
1276			case types.Complex64:
1277				return complex64(x.(complex128))
1278			case types.Complex128:
1279				return x.(complex128)
1280			}
1281			break // fail: no other conversions for complex
1282		}
1283
1284		// Conversions between non-complex numeric types?
1285		if ut_src.Info()&types.IsNumeric != 0 {
1286			kind := ut_dst.(*types.Basic).Kind()
1287			switch x := x.(type) {
1288			case int64: // signed integer -> numeric?
1289				switch kind {
1290				case types.Int:
1291					return int(x)
1292				case types.Int8:
1293					return int8(x)
1294				case types.Int16:
1295					return int16(x)
1296				case types.Int32:
1297					return int32(x)
1298				case types.Int64:
1299					return int64(x)
1300				case types.Uint:
1301					return uint(x)
1302				case types.Uint8:
1303					return uint8(x)
1304				case types.Uint16:
1305					return uint16(x)
1306				case types.Uint32:
1307					return uint32(x)
1308				case types.Uint64:
1309					return uint64(x)
1310				case types.Uintptr:
1311					return uintptr(x)
1312				case types.Float32:
1313					return float32(x)
1314				case types.Float64:
1315					return float64(x)
1316				}
1317
1318			case uint64: // unsigned integer -> numeric?
1319				switch kind {
1320				case types.Int:
1321					return int(x)
1322				case types.Int8:
1323					return int8(x)
1324				case types.Int16:
1325					return int16(x)
1326				case types.Int32:
1327					return int32(x)
1328				case types.Int64:
1329					return int64(x)
1330				case types.Uint:
1331					return uint(x)
1332				case types.Uint8:
1333					return uint8(x)
1334				case types.Uint16:
1335					return uint16(x)
1336				case types.Uint32:
1337					return uint32(x)
1338				case types.Uint64:
1339					return uint64(x)
1340				case types.Uintptr:
1341					return uintptr(x)
1342				case types.Float32:
1343					return float32(x)
1344				case types.Float64:
1345					return float64(x)
1346				}
1347
1348			case float64: // floating point -> numeric?
1349				switch kind {
1350				case types.Int:
1351					return int(x)
1352				case types.Int8:
1353					return int8(x)
1354				case types.Int16:
1355					return int16(x)
1356				case types.Int32:
1357					return int32(x)
1358				case types.Int64:
1359					return int64(x)
1360				case types.Uint:
1361					return uint(x)
1362				case types.Uint8:
1363					return uint8(x)
1364				case types.Uint16:
1365					return uint16(x)
1366				case types.Uint32:
1367					return uint32(x)
1368				case types.Uint64:
1369					return uint64(x)
1370				case types.Uintptr:
1371					return uintptr(x)
1372				case types.Float32:
1373					return float32(x)
1374				case types.Float64:
1375					return float64(x)
1376				}
1377			}
1378		}
1379	}
1380
1381	panic(fmt.Sprintf("unsupported conversion: %s  -> %s, dynamic type %T", t_src, t_dst, x))
1382}
1383
1384// checkInterface checks that the method set of x implements the
1385// interface itype.
1386// On success it returns "", on failure, an error message.
1387//
1388func checkInterface(i *interpreter, itype *types.Interface, x iface) string {
1389	if meth, _ := types.MissingMethod(x.t, itype, true); meth != nil {
1390		return fmt.Sprintf("interface conversion: %v is not %v: missing method %s",
1391			x.t, itype, meth.Name())
1392	}
1393	return "" // ok
1394}
1395