.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/ssa/interp/value.go

   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 }