value.go

Documentation: golang.org/x/tools/go/ssa/interp

     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  
     5  package 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  
    36  import (
    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  
    50  type value interface{}
    51  
    52  type tuple []value
    53  
    54  type array []value
    55  
    56  type iface struct {
    57  	t types.Type // never an "untyped" type
    58  	v value
    59  }
    60  
    61  type structure []value
    62  
    63  // For map, array, *array, slice, string or channel.
    64  type 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  
    70  type closure struct {
    71  	Fn  *ssa.Function
    72  	Env []value
    73  }
    74  
    75  type bad struct{}
    76  
    77  type rtype struct {
    78  	t types.Type
    79  }
    80  
    81  // Hash functions and equivalence relation:
    82  
    83  // hashString computes the FNV hash of s.
    84  func 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  
    93  var (
    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).
   100  func 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.
   116  func 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  
   128  func (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  
   139  func (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  
   148  func (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  
   161  func (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.
   173  func 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  
   180  func (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  
   185  func (x iface) hash(_ types.Type) int {
   186  	return hashType(x.t)*8581 + hash(x.t, x.v)
   187  }
   188  
   189  func (x rtype) hash(_ types.Type) int {
   190  	return hashType(x.t)
   191  }
   192  
   193  func (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.
   201  func 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).
   258  func 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.
   321  func 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.
   343  func 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)).)
   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)
   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.
   465  func toString(v value) string {
   466  	var b bytes.Buffer
   467  	writeValue(&b, v)
   468  	return b.String()
   469  }
   470  
   471  // ------------------------------------------------------------------------
   472  // Iterators
   473  
   474  type stringIter struct {
   475  	*strings.Reader
   476  	i int
   477  }
   478  
   479  func (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  
   492  type mapIter struct {
   493  	iter *reflect.MapIter
   494  	ok   bool
   495  }
   496  
   497  func (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  
   506  type hashmapIter struct {
   507  	iter *reflect.MapIter
   508  	ok   bool
   509  	cur  *entry
   510  }
   511  
   512  func (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
View as plain text