+++ /dev/null
-// Copyright 2013 The Go Authors. All rights reserved.
-// Use of this source code is governed by a BSD-style
-// license that can be found in the LICENSE file.
-
-package interp
-
-// Values
-//
-// All interpreter values are "boxed" in the empty interface, value.
-// The range of possible dynamic types within value are:
-//
-// - bool
-// - numbers (all built-in int/float/complex types are distinguished)
-// - string
-// - map[value]value --- maps for which usesBuiltinMap(keyType)
-// *hashmap --- maps for which !usesBuiltinMap(keyType)
-// - chan value
-// - []value --- slices
-// - iface --- interfaces.
-// - structure --- structs. Fields are ordered and accessed by numeric indices.
-// - array --- arrays.
-// - *value --- pointers. Careful: *value is a distinct type from *array etc.
-// - *ssa.Function \
-// *ssa.Builtin } --- functions. A nil 'func' is always of type *ssa.Function.
-// *closure /
-// - tuple --- as returned by Return, Next, "value,ok" modes, etc.
-// - iter --- iterators from 'range' over map or string.
-// - bad --- a poison pill for locals that have gone out of scope.
-// - rtype -- the interpreter's concrete implementation of reflect.Type
-//
-// Note that nil is not on this list.
-//
-// Pay close attention to whether or not the dynamic type is a pointer.
-// The compiler cannot help you since value is an empty interface.
-
-import (
- "bytes"
- "fmt"
- "go/types"
- "io"
- "reflect"
- "strings"
- "sync"
- "unsafe"
-
- "golang.org/x/tools/go/ssa"
- "golang.org/x/tools/go/types/typeutil"
-)
-
-type value interface{}
-
-type tuple []value
-
-type array []value
-
-type iface struct {
- t types.Type // never an "untyped" type
- v value
-}
-
-type structure []value
-
-// For map, array, *array, slice, string or channel.
-type iter interface {
- // next returns a Tuple (key, value, ok).
- // key and value are unaliased, e.g. copies of the sequence element.
- next() tuple
-}
-
-type closure struct {
- Fn *ssa.Function
- Env []value
-}
-
-type bad struct{}
-
-type rtype struct {
- t types.Type
-}
-
-// Hash functions and equivalence relation:
-
-// hashString computes the FNV hash of s.
-func hashString(s string) int {
- var h uint32
- for i := 0; i < len(s); i++ {
- h ^= uint32(s[i])
- h *= 16777619
- }
- return int(h)
-}
-
-var (
- mu sync.Mutex
- hasher = typeutil.MakeHasher()
-)
-
-// hashType returns a hash for t such that
-// types.Identical(x, y) => hashType(x) == hashType(y).
-func hashType(t types.Type) int {
- mu.Lock()
- h := int(hasher.Hash(t))
- mu.Unlock()
- return h
-}
-
-// usesBuiltinMap returns true if the built-in hash function and
-// equivalence relation for type t are consistent with those of the
-// interpreter's representation of type t. Such types are: all basic
-// types (bool, numbers, string), pointers and channels.
-//
-// usesBuiltinMap returns false for types that require a custom map
-// implementation: interfaces, arrays and structs.
-//
-// Panic ensues if t is an invalid map key type: function, map or slice.
-func usesBuiltinMap(t types.Type) bool {
- switch t := t.(type) {
- case *types.Basic, *types.Chan, *types.Pointer:
- return true
- case *types.Named:
- return usesBuiltinMap(t.Underlying())
- case *types.Interface, *types.Array, *types.Struct:
- return false
- }
- panic(fmt.Sprintf("invalid map key type: %T", t))
-}
-
-func (x array) eq(t types.Type, _y interface{}) bool {
- y := _y.(array)
- tElt := t.Underlying().(*types.Array).Elem()
- for i, xi := range x {
- if !equals(tElt, xi, y[i]) {
- return false
- }
- }
- return true
-}
-
-func (x array) hash(t types.Type) int {
- h := 0
- tElt := t.Underlying().(*types.Array).Elem()
- for _, xi := range x {
- h += hash(tElt, xi)
- }
- return h
-}
-
-func (x structure) eq(t types.Type, _y interface{}) bool {
- y := _y.(structure)
- tStruct := t.Underlying().(*types.Struct)
- for i, n := 0, tStruct.NumFields(); i < n; i++ {
- if f := tStruct.Field(i); !f.Anonymous() {
- if !equals(f.Type(), x[i], y[i]) {
- return false
- }
- }
- }
- return true
-}
-
-func (x structure) hash(t types.Type) int {
- tStruct := t.Underlying().(*types.Struct)
- h := 0
- for i, n := 0, tStruct.NumFields(); i < n; i++ {
- if f := tStruct.Field(i); !f.Anonymous() {
- h += hash(f.Type(), x[i])
- }
- }
- return h
-}
-
-// nil-tolerant variant of types.Identical.
-func sameType(x, y types.Type) bool {
- if x == nil {
- return y == nil
- }
- return y != nil && types.Identical(x, y)
-}
-
-func (x iface) eq(t types.Type, _y interface{}) bool {
- y := _y.(iface)
- return sameType(x.t, y.t) && (x.t == nil || equals(x.t, x.v, y.v))
-}
-
-func (x iface) hash(_ types.Type) int {
- return hashType(x.t)*8581 + hash(x.t, x.v)
-}
-
-func (x rtype) hash(_ types.Type) int {
- return hashType(x.t)
-}
-
-func (x rtype) eq(_ types.Type, y interface{}) bool {
- return types.Identical(x.t, y.(rtype).t)
-}
-
-// equals returns true iff x and y are equal according to Go's
-// linguistic equivalence relation for type t.
-// In a well-typed program, the dynamic types of x and y are
-// guaranteed equal.
-func equals(t types.Type, x, y value) bool {
- switch x := x.(type) {
- case bool:
- return x == y.(bool)
- case int:
- return x == y.(int)
- case int8:
- return x == y.(int8)
- case int16:
- return x == y.(int16)
- case int32:
- return x == y.(int32)
- case int64:
- return x == y.(int64)
- case uint:
- return x == y.(uint)
- case uint8:
- return x == y.(uint8)
- case uint16:
- return x == y.(uint16)
- case uint32:
- return x == y.(uint32)
- case uint64:
- return x == y.(uint64)
- case uintptr:
- return x == y.(uintptr)
- case float32:
- return x == y.(float32)
- case float64:
- return x == y.(float64)
- case complex64:
- return x == y.(complex64)
- case complex128:
- return x == y.(complex128)
- case string:
- return x == y.(string)
- case *value:
- return x == y.(*value)
- case chan value:
- return x == y.(chan value)
- case structure:
- return x.eq(t, y)
- case array:
- return x.eq(t, y)
- case iface:
- return x.eq(t, y)
- case rtype:
- return x.eq(t, y)
- }
-
- // Since map, func and slice don't support comparison, this
- // case is only reachable if one of x or y is literally nil
- // (handled in eqnil) or via interface{} values.
- panic(fmt.Sprintf("comparing uncomparable type %s", t))
-}
-
-// Returns an integer hash of x such that equals(x, y) => hash(x) == hash(y).
-func hash(t types.Type, x value) int {
- switch x := x.(type) {
- case bool:
- if x {
- return 1
- }
- return 0
- case int:
- return x
- case int8:
- return int(x)
- case int16:
- return int(x)
- case int32:
- return int(x)
- case int64:
- return int(x)
- case uint:
- return int(x)
- case uint8:
- return int(x)
- case uint16:
- return int(x)
- case uint32:
- return int(x)
- case uint64:
- return int(x)
- case uintptr:
- return int(x)
- case float32:
- return int(x)
- case float64:
- return int(x)
- case complex64:
- return int(real(x))
- case complex128:
- return int(real(x))
- case string:
- return hashString(x)
- case *value:
- return int(uintptr(unsafe.Pointer(x)))
- case chan value:
- return int(uintptr(reflect.ValueOf(x).Pointer()))
- case structure:
- return x.hash(t)
- case array:
- return x.hash(t)
- case iface:
- return x.hash(t)
- case rtype:
- return x.hash(t)
- }
- panic(fmt.Sprintf("%T is unhashable", x))
-}
-
-// reflect.Value struct values don't have a fixed shape, since the
-// payload can be a scalar or an aggregate depending on the instance.
-// So store (and load) can't simply use recursion over the shape of the
-// rhs value, or the lhs, to copy the value; we need the static type
-// information. (We can't make reflect.Value a new basic data type
-// because its "structness" is exposed to Go programs.)
-
-// load returns the value of type T in *addr.
-func load(T types.Type, addr *value) value {
- switch T := T.Underlying().(type) {
- case *types.Struct:
- v := (*addr).(structure)
- a := make(structure, len(v))
- for i := range a {
- a[i] = load(T.Field(i).Type(), &v[i])
- }
- return a
- case *types.Array:
- v := (*addr).(array)
- a := make(array, len(v))
- for i := range a {
- a[i] = load(T.Elem(), &v[i])
- }
- return a
- default:
- return *addr
- }
-}
-
-// store stores value v of type T into *addr.
-func store(T types.Type, addr *value, v value) {
- switch T := T.Underlying().(type) {
- case *types.Struct:
- lhs := (*addr).(structure)
- rhs := v.(structure)
- for i := range lhs {
- store(T.Field(i).Type(), &lhs[i], rhs[i])
- }
- case *types.Array:
- lhs := (*addr).(array)
- rhs := v.(array)
- for i := range lhs {
- store(T.Elem(), &lhs[i], rhs[i])
- }
- default:
- *addr = v
- }
-}
-
-// Prints in the style of built-in println.
-// (More or less; in gc println is actually a compiler intrinsic and
-// can distinguish println(1) from println(interface{}(1)).)
-func writeValue(buf *bytes.Buffer, v value) {
- switch v := v.(type) {
- case nil, bool, int, int8, int16, int32, int64, uint, uint8, uint16, uint32, uint64, uintptr, float32, float64, complex64, complex128, string:
- fmt.Fprintf(buf, "%v", v)
-
- case map[value]value:
- buf.WriteString("map[")
- sep := ""
- for k, e := range v {
- buf.WriteString(sep)
- sep = " "
- writeValue(buf, k)
- buf.WriteString(":")
- writeValue(buf, e)
- }
- buf.WriteString("]")
-
- case *hashmap:
- buf.WriteString("map[")
- sep := " "
- for _, e := range v.entries() {
- for e != nil {
- buf.WriteString(sep)
- sep = " "
- writeValue(buf, e.key)
- buf.WriteString(":")
- writeValue(buf, e.value)
- e = e.next
- }
- }
- buf.WriteString("]")
-
- case chan value:
- fmt.Fprintf(buf, "%v", v) // (an address)
-
- case *value:
- if v == nil {
- buf.WriteString("<nil>")
- } else {
- fmt.Fprintf(buf, "%p", v)
- }
-
- case iface:
- fmt.Fprintf(buf, "(%s, ", v.t)
- writeValue(buf, v.v)
- buf.WriteString(")")
-
- case structure:
- buf.WriteString("{")
- for i, e := range v {
- if i > 0 {
- buf.WriteString(" ")
- }
- writeValue(buf, e)
- }
- buf.WriteString("}")
-
- case array:
- buf.WriteString("[")
- for i, e := range v {
- if i > 0 {
- buf.WriteString(" ")
- }
- writeValue(buf, e)
- }
- buf.WriteString("]")
-
- case []value:
- buf.WriteString("[")
- for i, e := range v {
- if i > 0 {
- buf.WriteString(" ")
- }
- writeValue(buf, e)
- }
- buf.WriteString("]")
-
- case *ssa.Function, *ssa.Builtin, *closure:
- fmt.Fprintf(buf, "%p", v) // (an address)
-
- case rtype:
- buf.WriteString(v.t.String())
-
- case tuple:
- // Unreachable in well-formed Go programs
- buf.WriteString("(")
- for i, e := range v {
- if i > 0 {
- buf.WriteString(", ")
- }
- writeValue(buf, e)
- }
- buf.WriteString(")")
-
- default:
- fmt.Fprintf(buf, "<%T>", v)
- }
-}
-
-// Implements printing of Go values in the style of built-in println.
-func toString(v value) string {
- var b bytes.Buffer
- writeValue(&b, v)
- return b.String()
-}
-
-// ------------------------------------------------------------------------
-// Iterators
-
-type stringIter struct {
- *strings.Reader
- i int
-}
-
-func (it *stringIter) next() tuple {
- okv := make(tuple, 3)
- ch, n, err := it.ReadRune()
- ok := err != io.EOF
- okv[0] = ok
- if ok {
- okv[1] = it.i
- okv[2] = ch
- }
- it.i += n
- return okv
-}
-
-type mapIter struct {
- iter *reflect.MapIter
- ok bool
-}
-
-func (it *mapIter) next() tuple {
- it.ok = it.iter.Next()
- if !it.ok {
- return []value{false, nil, nil}
- }
- k, v := it.iter.Key().Interface(), it.iter.Value().Interface()
- return []value{true, k, v}
-}
-
-type hashmapIter struct {
- iter *reflect.MapIter
- ok bool
- cur *entry
-}
-
-func (it *hashmapIter) next() tuple {
- for {
- if it.cur != nil {
- k, v := it.cur.key, it.cur.value
- it.cur = it.cur.next
- return []value{true, k, v}
- }
- it.ok = it.iter.Next()
- if !it.ok {
- return []value{false, nil, nil}
- }
- it.cur = it.iter.Value().Interface().(*entry)
- }
-}