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