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