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.
9 // All interpreter values are "boxed" in the empty interface, value.
10 // The range of possible dynamic types within value are:
13 // - numbers (all built-in int/float/complex types are distinguished)
15 // - map[value]value --- maps for which usesBuiltinMap(keyType)
16 // *hashmap --- maps for which !usesBuiltinMap(keyType)
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.
24 // *ssa.Builtin } --- functions. A nil 'func' is always of type *ssa.Function.
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
31 // Note that nil is not on this list.
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.
46 "golang.org/x/tools/go/ssa"
47 "golang.org/x/tools/go/types/typeutil"
50 type value interface{}
57 t types.Type // never an "untyped" type
61 type structure []value
63 // For map, array, *array, slice, string or channel.
65 // next returns a Tuple (key, value, ok).
66 // key and value are unaliased, e.g. copies of the sequence element.
81 // Hash functions and equivalence relation:
83 // hashString computes the FNV hash of s.
84 func hashString(s string) int {
86 for i := 0; i < len(s); i++ {
95 hasher = typeutil.MakeHasher()
98 // hashType returns a hash for t such that
99 // types.Identical(x, y) => hashType(x) == hashType(y).
100 func hashType(t types.Type) int {
102 h := int(hasher.Hash(t))
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.
112 // usesBuiltinMap returns false for types that require a custom map
113 // implementation: interfaces, arrays and structs.
115 // Panic ensues if t is an invalid map key type: function, map or slice.
116 func usesBuiltinMap(t types.Type) bool {
117 switch t := t.(type) {
118 case *types.Basic, *types.Chan, *types.Pointer:
121 return usesBuiltinMap(t.Underlying())
122 case *types.Interface, *types.Array, *types.Struct:
125 panic(fmt.Sprintf("invalid map key type: %T", t))
128 func (x array) eq(t types.Type, _y interface{}) bool {
130 tElt := t.Underlying().(*types.Array).Elem()
131 for i, xi := range x {
132 if !equals(tElt, xi, y[i]) {
139 func (x array) hash(t types.Type) int {
141 tElt := t.Underlying().(*types.Array).Elem()
142 for _, xi := range x {
148 func (x structure) eq(t types.Type, _y interface{}) bool {
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]) {
161 func (x structure) hash(t types.Type) int {
162 tStruct := t.Underlying().(*types.Struct)
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])
172 // nil-tolerant variant of types.Identical.
173 func sameType(x, y types.Type) bool {
177 return y != nil && types.Identical(x, y)
180 func (x iface) eq(t types.Type, _y interface{}) bool {
182 return sameType(x.t, y.t) && (x.t == nil || equals(x.t, x.v, y.v))
185 func (x iface) hash(_ types.Type) int {
186 return hashType(x.t)*8581 + hash(x.t, x.v)
189 func (x rtype) hash(_ types.Type) int {
193 func (x rtype) eq(_ types.Type, y interface{}) bool {
194 return types.Identical(x.t, y.(rtype).t)
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
201 func equals(t types.Type, x, y value) bool {
202 switch x := x.(type) {
210 return x == y.(int16)
212 return x == y.(int32)
214 return x == y.(int64)
218 return x == y.(uint8)
220 return x == y.(uint16)
222 return x == y.(uint32)
224 return x == y.(uint64)
226 return x == y.(uintptr)
228 return x == y.(float32)
230 return x == y.(float64)
232 return x == y.(complex64)
234 return x == y.(complex128)
236 return x == y.(string)
238 return x == y.(*value)
240 return x == y.(chan value)
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))
257 // Returns an integer hash of x such that equals(x, y) => hash(x) == hash(y).
258 func hash(t types.Type, x value) int {
259 switch x := x.(type) {
298 return int(uintptr(unsafe.Pointer(x)))
300 return int(uintptr(reflect.ValueOf(x).Pointer()))
310 panic(fmt.Sprintf("%T is unhashable", x))
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.)
320 // load returns the value of type T in *addr.
321 func load(T types.Type, addr *value) value {
322 switch T := T.Underlying().(type) {
324 v := (*addr).(structure)
325 a := make(structure, len(v))
327 a[i] = load(T.Field(i).Type(), &v[i])
332 a := make(array, len(v))
334 a[i] = load(T.Elem(), &v[i])
342 // store stores value v of type T into *addr.
343 func store(T types.Type, addr *value, v value) {
344 switch T := T.Underlying().(type) {
346 lhs := (*addr).(structure)
349 store(T.Field(i).Type(), &lhs[i], rhs[i])
352 lhs := (*addr).(array)
355 store(T.Elem(), &lhs[i], rhs[i])
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)).)
365 func 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)
370 case map[value]value:
371 buf.WriteString("map[")
373 for k, e := range v {
383 buf.WriteString("map[")
385 for _, e := range v.entries() {
389 writeValue(buf, e.key)
391 writeValue(buf, e.value)
398 fmt.Fprintf(buf, "%v", v) // (an address)
402 buf.WriteString("<nil>")
404 fmt.Fprintf(buf, "%p", v)
408 fmt.Fprintf(buf, "(%s, ", v.t)
414 for i, e := range v {
424 for i, e := range v {
434 for i, e := range v {
442 case *ssa.Function, *ssa.Builtin, *closure:
443 fmt.Fprintf(buf, "%p", v) // (an address)
446 buf.WriteString(v.t.String())
449 // Unreachable in well-formed Go programs
451 for i, e := range v {
453 buf.WriteString(", ")
460 fmt.Fprintf(buf, "<%T>", v)
464 // Implements printing of Go values in the style of built-in println.
465 func toString(v value) string {
471 // ------------------------------------------------------------------------
474 type stringIter struct {
479 func (it *stringIter) next() tuple {
480 okv := make(tuple, 3)
481 ch, n, err := it.ReadRune()
492 type mapIter struct {
493 iter *reflect.MapIter
497 func (it *mapIter) next() tuple {
498 it.ok = it.iter.Next()
500 return []value{false, nil, nil}
502 k, v := it.iter.Key().Interface(), it.iter.Value().Interface()
503 return []value{true, k, v}
506 type hashmapIter struct {
507 iter *reflect.MapIter
512 func (it *hashmapIter) next() tuple {
515 k, v := it.cur.key, it.cur.value
517 return []value{true, k, v}
519 it.ok = it.iter.Next()
521 return []value{false, nil, nil}
523 it.cur = it.iter.Value().Interface().(*entry)