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
7// Values
8//
9// All interpreter values are "boxed" in the empty interface, value.
10// The range of possible dynamic types within value are:
11//
12// - bool
13// - numbers (all built-in int/float/complex types are distinguished)
14// - string
15// - map[value]value --- maps for which  usesBuiltinMap(keyType)
16//   *hashmap        --- maps for which !usesBuiltinMap(keyType)
17// - chan value
18// - []value --- slices
19// - iface --- interfaces.
20// - structure --- structs.  Fields are ordered and accessed by numeric indices.
21// - array --- arrays.
22// - *value --- pointers.  Careful: *value is a distinct type from *array etc.
23// - *ssa.Function \
24//   *ssa.Builtin   } --- functions.  A nil 'func' is always of type *ssa.Function.
25//   *closure      /
26// - tuple --- as returned by Return, Next, "value,ok" modes, etc.
27// - iter --- iterators from 'range' over map or string.
28// - bad --- a poison pill for locals that have gone out of scope.
29// - rtype -- the interpreter's concrete implementation of reflect.Type
30//
31// Note that nil is not on this list.
32//
33// Pay close attention to whether or not the dynamic type is a pointer.
34// The compiler cannot help you since value is an empty interface.
35
36import (
37	"bytes"
38	"fmt"
39	"go/types"
40	"io"
41	"reflect"
42	"strings"
43	"sync"
44	"unsafe"
45
46	"golang.org/x/tools/go/ssa"
47	"golang.org/x/tools/go/types/typeutil"
48)
49
50type value interface{}
51
52type tuple []value
53
54type array []value
55
56type iface struct {
57	t types.Type // never an "untyped" type
58	v value
59}
60
61type structure []value
62
63// For map, array, *array, slice, string or channel.
64type iter interface {
65	// next returns a Tuple (key, value, ok).
66	// key and value are unaliased, e.g. copies of the sequence element.
67	next() tuple
68}
69
70type closure struct {
71	Fn  *ssa.Function
72	Env []value
73}
74
75type bad struct{}
76
77type rtype struct {
78	t types.Type
79}
80
81// Hash functions and equivalence relation:
82
83// hashString computes the FNV hash of s.
84func hashString(s string) int {
85	var h uint32
86	for i := 0; i < len(s); i++ {
87		h ^= uint32(s[i])
88		h *= 16777619
89	}
90	return int(h)
91}
92
93var (
94	mu     sync.Mutex
95	hasher = typeutil.MakeHasher()
96)
97
98// hashType returns a hash for t such that
99// types.Identical(x, y) => hashType(x) == hashType(y).
100func hashType(t types.Type) int {
101	mu.Lock()
102	h := int(hasher.Hash(t))
103	mu.Unlock()
104	return h
105}
106
107// usesBuiltinMap returns true if the built-in hash function and
108// equivalence relation for type t are consistent with those of the
109// interpreter's representation of type t.  Such types are: all basic
110// types (bool, numbers, string), pointers and channels.
111//
112// usesBuiltinMap returns false for types that require a custom map
113// implementation: interfaces, arrays and structs.
114//
115// Panic ensues if t is an invalid map key type: function, map or slice.
116func usesBuiltinMap(t types.Type) bool {
117	switch t := t.(type) {
118	case *types.Basic, *types.Chan, *types.Pointer:
119		return true
120	case *types.Named:
121		return usesBuiltinMap(t.Underlying())
122	case *types.Interface, *types.Array, *types.Struct:
123		return false
124	}
125	panic(fmt.Sprintf("invalid map key type: %T", t))
126}
127
128func (x array) eq(t types.Type, _y interface{}) bool {
129	y := _y.(array)
130	tElt := t.Underlying().(*types.Array).Elem()
131	for i, xi := range x {
132		if !equals(tElt, xi, y[i]) {
133			return false
134		}
135	}
136	return true
137}
138
139func (x array) hash(t types.Type) int {
140	h := 0
141	tElt := t.Underlying().(*types.Array).Elem()
142	for _, xi := range x {
143		h += hash(tElt, xi)
144	}
145	return h
146}
147
148func (x structure) eq(t types.Type, _y interface{}) bool {
149	y := _y.(structure)
150	tStruct := t.Underlying().(*types.Struct)
151	for i, n := 0, tStruct.NumFields(); i < n; i++ {
152		if f := tStruct.Field(i); !f.Anonymous() {
153			if !equals(f.Type(), x[i], y[i]) {
154				return false
155			}
156		}
157	}
158	return true
159}
160
161func (x structure) hash(t types.Type) int {
162	tStruct := t.Underlying().(*types.Struct)
163	h := 0
164	for i, n := 0, tStruct.NumFields(); i < n; i++ {
165		if f := tStruct.Field(i); !f.Anonymous() {
166			h += hash(f.Type(), x[i])
167		}
168	}
169	return h
170}
171
172// nil-tolerant variant of types.Identical.
173func sameType(x, y types.Type) bool {
174	if x == nil {
175		return y == nil
176	}
177	return y != nil && types.Identical(x, y)
178}
179
180func (x iface) eq(t types.Type, _y interface{}) bool {
181	y := _y.(iface)
182	return sameType(x.t, y.t) && (x.t == nil || equals(x.t, x.v, y.v))
183}
184
185func (x iface) hash(_ types.Type) int {
186	return hashType(x.t)*8581 + hash(x.t, x.v)
187}
188
189func (x rtype) hash(_ types.Type) int {
190	return hashType(x.t)
191}
192
193func (x rtype) eq(_ types.Type, y interface{}) bool {
194	return types.Identical(x.t, y.(rtype).t)
195}
196
197// equals returns true iff x and y are equal according to Go's
198// linguistic equivalence relation for type t.
199// In a well-typed program, the dynamic types of x and y are
200// guaranteed equal.
201func equals(t types.Type, x, y value) bool {
202	switch x := x.(type) {
203	case bool:
204		return x == y.(bool)
205	case int:
206		return x == y.(int)
207	case int8:
208		return x == y.(int8)
209	case int16:
210		return x == y.(int16)
211	case int32:
212		return x == y.(int32)
213	case int64:
214		return x == y.(int64)
215	case uint:
216		return x == y.(uint)
217	case uint8:
218		return x == y.(uint8)
219	case uint16:
220		return x == y.(uint16)
221	case uint32:
222		return x == y.(uint32)
223	case uint64:
224		return x == y.(uint64)
225	case uintptr:
226		return x == y.(uintptr)
227	case float32:
228		return x == y.(float32)
229	case float64:
230		return x == y.(float64)
231	case complex64:
232		return x == y.(complex64)
233	case complex128:
234		return x == y.(complex128)
235	case string:
236		return x == y.(string)
237	case *value:
238		return x == y.(*value)
239	case chan value:
240		return x == y.(chan value)
241	case structure:
242		return x.eq(t, y)
243	case array:
244		return x.eq(t, y)
245	case iface:
246		return x.eq(t, y)
247	case rtype:
248		return x.eq(t, y)
249	}
250
251	// Since map, func and slice don't support comparison, this
252	// case is only reachable if one of x or y is literally nil
253	// (handled in eqnil) or via interface{} values.
254	panic(fmt.Sprintf("comparing uncomparable type %s", t))
255}
256
257// Returns an integer hash of x such that equals(x, y) => hash(x) == hash(y).
258func hash(t types.Type, x value) int {
259	switch x := x.(type) {
260	case bool:
261		if x {
262			return 1
263		}
264		return 0
265	case int:
266		return x
267	case int8:
268		return int(x)
269	case int16:
270		return int(x)
271	case int32:
272		return int(x)
273	case int64:
274		return int(x)
275	case uint:
276		return int(x)
277	case uint8:
278		return int(x)
279	case uint16:
280		return int(x)
281	case uint32:
282		return int(x)
283	case uint64:
284		return int(x)
285	case uintptr:
286		return int(x)
287	case float32:
288		return int(x)
289	case float64:
290		return int(x)
291	case complex64:
292		return int(real(x))
293	case complex128:
294		return int(real(x))
295	case string:
296		return hashString(x)
297	case *value:
298		return int(uintptr(unsafe.Pointer(x)))
299	case chan value:
300		return int(uintptr(reflect.ValueOf(x).Pointer()))
301	case structure:
302		return x.hash(t)
303	case array:
304		return x.hash(t)
305	case iface:
306		return x.hash(t)
307	case rtype:
308		return x.hash(t)
309	}
310	panic(fmt.Sprintf("%T is unhashable", x))
311}
312
313// reflect.Value struct values don't have a fixed shape, since the
314// payload can be a scalar or an aggregate depending on the instance.
315// So store (and load) can't simply use recursion over the shape of the
316// rhs value, or the lhs, to copy the value; we need the static type
317// information.  (We can't make reflect.Value a new basic data type
318// because its "structness" is exposed to Go programs.)
319
320// load returns the value of type T in *addr.
321func load(T types.Type, addr *value) value {
322	switch T := T.Underlying().(type) {
323	case *types.Struct:
324		v := (*addr).(structure)
325		a := make(structure, len(v))
326		for i := range a {
327			a[i] = load(T.Field(i).Type(), &v[i])
328		}
329		return a
330	case *types.Array:
331		v := (*addr).(array)
332		a := make(array, len(v))
333		for i := range a {
334			a[i] = load(T.Elem(), &v[i])
335		}
336		return a
337	default:
338		return *addr
339	}
340}
341
342// store stores value v of type T into *addr.
343func store(T types.Type, addr *value, v value) {
344	switch T := T.Underlying().(type) {
345	case *types.Struct:
346		lhs := (*addr).(structure)
347		rhs := v.(structure)
348		for i := range lhs {
349			store(T.Field(i).Type(), &lhs[i], rhs[i])
350		}
351	case *types.Array:
352		lhs := (*addr).(array)
353		rhs := v.(array)
354		for i := range lhs {
355			store(T.Elem(), &lhs[i], rhs[i])
356		}
357	default:
358		*addr = v
359	}
360}
361
362// Prints in the style of built-in println.
363// (More or less; in gc println is actually a compiler intrinsic and
364// can distinguish println(1) from println(interface{}(1)).)
365func writeValue(buf *bytes.Buffer, v value) {
366	switch v := v.(type) {
367	case nil, bool, int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr, float32, float64, complex64, complex128, string:
368		fmt.Fprintf(buf, "%v", v)
369
370	case map[value]value:
371		buf.WriteString("map[")
372		sep := ""
373		for k, e := range v {
374			buf.WriteString(sep)
375			sep = " "
376			writeValue(buf, k)
377			buf.WriteString(":")
378			writeValue(buf, e)
379		}
380		buf.WriteString("]")
381
382	case *hashmap:
383		buf.WriteString("map[")
384		sep := " "
385		for _, e := range v.entries() {
386			for e != nil {
387				buf.WriteString(sep)
388				sep = " "
389				writeValue(buf, e.key)
390				buf.WriteString(":")
391				writeValue(buf, e.value)
392				e = e.next
393			}
394		}
395		buf.WriteString("]")
396
397	case chan value:
398		fmt.Fprintf(buf, "%v", v) // (an address)
399
400	case *value:
401		if v == nil {
402			buf.WriteString("<nil>")
403		} else {
404			fmt.Fprintf(buf, "%p", v)
405		}
406
407	case iface:
408		fmt.Fprintf(buf, "(%s, ", v.t)
409		writeValue(buf, v.v)
410		buf.WriteString(")")
411
412	case structure:
413		buf.WriteString("{")
414		for i, e := range v {
415			if i > 0 {
416				buf.WriteString(" ")
417			}
418			writeValue(buf, e)
419		}
420		buf.WriteString("}")
421
422	case array:
423		buf.WriteString("[")
424		for i, e := range v {
425			if i > 0 {
426				buf.WriteString(" ")
427			}
428			writeValue(buf, e)
429		}
430		buf.WriteString("]")
431
432	case []value:
433		buf.WriteString("[")
434		for i, e := range v {
435			if i > 0 {
436				buf.WriteString(" ")
437			}
438			writeValue(buf, e)
439		}
440		buf.WriteString("]")
441
442	case *ssa.Function, *ssa.Builtin, *closure:
443		fmt.Fprintf(buf, "%p", v) // (an address)
444
445	case rtype:
446		buf.WriteString(v.t.String())
447
448	case tuple:
449		// Unreachable in well-formed Go programs
450		buf.WriteString("(")
451		for i, e := range v {
452			if i > 0 {
453				buf.WriteString(", ")
454			}
455			writeValue(buf, e)
456		}
457		buf.WriteString(")")
458
459	default:
460		fmt.Fprintf(buf, "<%T>", v)
461	}
462}
463
464// Implements printing of Go values in the style of built-in println.
465func toString(v value) string {
466	var b bytes.Buffer
467	writeValue(&b, v)
468	return b.String()
469}
470
471// ------------------------------------------------------------------------
472// Iterators
473
474type stringIter struct {
475	*strings.Reader
476	i int
477}
478
479func (it *stringIter) next() tuple {
480	okv := make(tuple, 3)
481	ch, n, err := it.ReadRune()
482	ok := err != io.EOF
483	okv[0] = ok
484	if ok {
485		okv[1] = it.i
486		okv[2] = ch
487	}
488	it.i += n
489	return okv
490}
491
492type mapIter struct {
493	iter *reflect.MapIter
494	ok   bool
495}
496
497func (it *mapIter) next() tuple {
498	it.ok = it.iter.Next()
499	if !it.ok {
500		return []value{false, nil, nil}
501	}
502	k, v := it.iter.Key().Interface(), it.iter.Value().Interface()
503	return []value{true, k, v}
504}
505
506type hashmapIter struct {
507	iter *reflect.MapIter
508	ok   bool
509	cur  *entry
510}
511
512func (it *hashmapIter) next() tuple {
513	for {
514		if it.cur != nil {
515			k, v := it.cur.key, it.cur.value
516			it.cur = it.cur.next
517			return []value{true, k, v}
518		}
519		it.ok = it.iter.Next()
520		if !it.ok {
521			return []value{false, nil, nil}
522		}
523		it.cur = it.iter.Value().Interface().(*entry)
524	}
525}
526