blob: 94018b550fcc90b654557710f9d3a9a68de5fd4a [file] [log] [blame]
// 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)
}
}