.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201105173854-bc9fc8d8c4bc/go/pointer/reflect.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 pointer
   6
   7 // This file implements the generation and resolution rules for
   8 // constraints arising from the use of reflection in the target
   9 // program.  See doc.go for explanation of the representation.
  10 //
  11 // For consistency, the names of all parameters match those of the
  12 // actual functions in the "reflect" package.
  13 //
  14 // To avoid proliferation of equivalent labels, intrinsics should
  15 // memoize as much as possible, like TypeOf and Zero do for their
  16 // tagged objects.
  17 //
  18 // TODO(adonovan): this file is rather subtle.  Explain how we derive
  19 // the implementation of each reflect operator from its spec,
  20 // including the subtleties of reflect.flag{Addr,RO,Indir}.
  21 // [Hint: our implementation is as if reflect.flagIndir was always
  22 // true, i.e. reflect.Values are pointers to tagged objects, there is
  23 // no inline allocation optimization; and indirect tagged objects (not
  24 // yet implemented) correspond to reflect.Values with
  25 // reflect.flagAddr.]
  26 // A picture would help too.
  27 //
  28 // TODO(adonovan): try factoring up the common parts of the majority of
  29 // these constraints that are single input, single output.
  30
  31 import (
  32         "fmt"
  33         "go/constant"
  34         "go/types"
  35         "reflect"
  36
  37         "golang.org/x/tools/go/ssa"
  38 )
  39
  40 func init() {
  41         for name, fn := range map[string]intrinsic{
  42                 // reflect.Value methods.
  43                 "(reflect.Value).Addr":            ext۰reflect۰Value۰Addr,
  44                 "(reflect.Value).Bool":            ext۰NoEffect,
  45                 "(reflect.Value).Bytes":           ext۰reflect۰Value۰Bytes,
  46                 "(reflect.Value).Call":            ext۰reflect۰Value۰Call,
  47                 "(reflect.Value).CallSlice":       ext۰reflect۰Value۰CallSlice,
  48                 "(reflect.Value).CanAddr":         ext۰NoEffect,
  49                 "(reflect.Value).CanInterface":    ext۰NoEffect,
  50                 "(reflect.Value).CanSet":          ext۰NoEffect,
  51                 "(reflect.Value).Cap":             ext۰NoEffect,
  52                 "(reflect.Value).Close":           ext۰NoEffect,
  53                 "(reflect.Value).Complex":         ext۰NoEffect,
  54                 "(reflect.Value).Convert":         ext۰reflect۰Value۰Convert,
  55                 "(reflect.Value).Elem":            ext۰reflect۰Value۰Elem,
  56                 "(reflect.Value).Field":           ext۰reflect۰Value۰Field,
  57                 "(reflect.Value).FieldByIndex":    ext۰reflect۰Value۰FieldByIndex,
  58                 "(reflect.Value).FieldByName":     ext۰reflect۰Value۰FieldByName,
  59                 "(reflect.Value).FieldByNameFunc": ext۰reflect۰Value۰FieldByNameFunc,
  60                 "(reflect.Value).Float":           ext۰NoEffect,
  61                 "(reflect.Value).Index":           ext۰reflect۰Value۰Index,
  62                 "(reflect.Value).Int":             ext۰NoEffect,
  63                 "(reflect.Value).Interface":       ext۰reflect۰Value۰Interface,
  64                 "(reflect.Value).InterfaceData":   ext۰NoEffect,
  65                 "(reflect.Value).IsNil":           ext۰NoEffect,
  66                 "(reflect.Value).IsValid":         ext۰NoEffect,
  67                 "(reflect.Value).Kind":            ext۰NoEffect,
  68                 "(reflect.Value).Len":             ext۰NoEffect,
  69                 "(reflect.Value).MapIndex":        ext۰reflect۰Value۰MapIndex,
  70                 "(reflect.Value).MapKeys":         ext۰reflect۰Value۰MapKeys,
  71                 "(reflect.Value).Method":          ext۰reflect۰Value۰Method,
  72                 "(reflect.Value).MethodByName":    ext۰reflect۰Value۰MethodByName,
  73                 "(reflect.Value).NumField":        ext۰NoEffect,
  74                 "(reflect.Value).NumMethod":       ext۰NoEffect,
  75                 "(reflect.Value).OverflowComplex": ext۰NoEffect,
  76                 "(reflect.Value).OverflowFloat":   ext۰NoEffect,
  77                 "(reflect.Value).OverflowInt":     ext۰NoEffect,
  78                 "(reflect.Value).OverflowUint":    ext۰NoEffect,
  79                 "(reflect.Value).Pointer":         ext۰NoEffect,
  80                 "(reflect.Value).Recv":            ext۰reflect۰Value۰Recv,
  81                 "(reflect.Value).Send":            ext۰reflect۰Value۰Send,
  82                 "(reflect.Value).Set":             ext۰reflect۰Value۰Set,
  83                 "(reflect.Value).SetBool":         ext۰NoEffect,
  84                 "(reflect.Value).SetBytes":        ext۰reflect۰Value۰SetBytes,
  85                 "(reflect.Value).SetComplex":      ext۰NoEffect,
  86                 "(reflect.Value).SetFloat":        ext۰NoEffect,
  87                 "(reflect.Value).SetInt":          ext۰NoEffect,
  88                 "(reflect.Value).SetLen":          ext۰NoEffect,
  89                 "(reflect.Value).SetMapIndex":     ext۰reflect۰Value۰SetMapIndex,
  90                 "(reflect.Value).SetPointer":      ext۰reflect۰Value۰SetPointer,
  91                 "(reflect.Value).SetString":       ext۰NoEffect,
  92                 "(reflect.Value).SetUint":         ext۰NoEffect,
  93                 "(reflect.Value).Slice":           ext۰reflect۰Value۰Slice,
  94                 "(reflect.Value).String":          ext۰NoEffect,
  95                 "(reflect.Value).TryRecv":         ext۰reflect۰Value۰Recv,
  96                 "(reflect.Value).TrySend":         ext۰reflect۰Value۰Send,
  97                 "(reflect.Value).Type":            ext۰NoEffect,
  98                 "(reflect.Value).Uint":            ext۰NoEffect,
  99                 "(reflect.Value).UnsafeAddr":      ext۰NoEffect,
 100
 101                 // Standalone reflect.* functions.
 102                 "reflect.Append":      ext۰reflect۰Append,
 103                 "reflect.AppendSlice": ext۰reflect۰AppendSlice,
 104                 "reflect.Copy":        ext۰reflect۰Copy,
 105                 "reflect.ChanOf":      ext۰reflect۰ChanOf,
 106                 "reflect.DeepEqual":   ext۰NoEffect,
 107                 "reflect.Indirect":    ext۰reflect۰Indirect,
 108                 "reflect.MakeChan":    ext۰reflect۰MakeChan,
 109                 "reflect.MakeFunc":    ext۰reflect۰MakeFunc,
 110                 "reflect.MakeMap":     ext۰reflect۰MakeMap,
 111                 "reflect.MakeSlice":   ext۰reflect۰MakeSlice,
 112                 "reflect.MapOf":       ext۰reflect۰MapOf,
 113                 "reflect.New":         ext۰reflect۰New,
 114                 "reflect.NewAt":       ext۰reflect۰NewAt,
 115                 "reflect.PtrTo":       ext۰reflect۰PtrTo,
 116                 "reflect.Select":      ext۰reflect۰Select,
 117                 "reflect.SliceOf":     ext۰reflect۰SliceOf,
 118                 "reflect.TypeOf":      ext۰reflect۰TypeOf,
 119                 "reflect.ValueOf":     ext۰reflect۰ValueOf,
 120                 "reflect.Zero":        ext۰reflect۰Zero,
 121                 "reflect.init":        ext۰NoEffect,
 122
 123                 // *reflect.rtype methods
 124                 "(*reflect.rtype).Align":           ext۰NoEffect,
 125                 "(*reflect.rtype).AssignableTo":    ext۰NoEffect,
 126                 "(*reflect.rtype).Bits":            ext۰NoEffect,
 127                 "(*reflect.rtype).ChanDir":         ext۰NoEffect,
 128                 "(*reflect.rtype).ConvertibleTo":   ext۰NoEffect,
 129                 "(*reflect.rtype).Elem":            ext۰reflect۰rtype۰Elem,
 130                 "(*reflect.rtype).Field":           ext۰reflect۰rtype۰Field,
 131                 "(*reflect.rtype).FieldAlign":      ext۰NoEffect,
 132                 "(*reflect.rtype).FieldByIndex":    ext۰reflect۰rtype۰FieldByIndex,
 133                 "(*reflect.rtype).FieldByName":     ext۰reflect۰rtype۰FieldByName,
 134                 "(*reflect.rtype).FieldByNameFunc": ext۰reflect۰rtype۰FieldByNameFunc,
 135                 "(*reflect.rtype).Implements":      ext۰NoEffect,
 136                 "(*reflect.rtype).In":              ext۰reflect۰rtype۰In,
 137                 "(*reflect.rtype).IsVariadic":      ext۰NoEffect,
 138                 "(*reflect.rtype).Key":             ext۰reflect۰rtype۰Key,
 139                 "(*reflect.rtype).Kind":            ext۰NoEffect,
 140                 "(*reflect.rtype).Len":             ext۰NoEffect,
 141                 "(*reflect.rtype).Method":          ext۰reflect۰rtype۰Method,
 142                 "(*reflect.rtype).MethodByName":    ext۰reflect۰rtype۰MethodByName,
 143                 "(*reflect.rtype).Name":            ext۰NoEffect,
 144                 "(*reflect.rtype).NumField":        ext۰NoEffect,
 145                 "(*reflect.rtype).NumIn":           ext۰NoEffect,
 146                 "(*reflect.rtype).NumMethod":       ext۰NoEffect,
 147                 "(*reflect.rtype).NumOut":          ext۰NoEffect,
 148                 "(*reflect.rtype).Out":             ext۰reflect۰rtype۰Out,
 149                 "(*reflect.rtype).PkgPath":         ext۰NoEffect,
 150                 "(*reflect.rtype).Size":            ext۰NoEffect,
 151                 "(*reflect.rtype).String":          ext۰NoEffect,
 152         } {
 153                 intrinsicsByName[name] = fn
 154         }
 155 }
 156
 157 // -------------------- (reflect.Value) --------------------
 158
 159 func ext۰reflect۰Value۰Addr(a *analysis, cgn *cgnode) {} // TODO(adonovan)
 160
 161 // ---------- func (Value).Bytes() Value ----------
 162
 163 // result = v.Bytes()
 164 type rVBytesConstraint struct {
 165         v      nodeid // (ptr)
 166         result nodeid // (indirect)
 167 }
 168
 169 func (c *rVBytesConstraint) ptr() nodeid { return c.v }
 170 func (c *rVBytesConstraint) presolve(h *hvn) {
 171         h.markIndirect(onodeid(c.result), "rVBytes.result")
 172 }
 173 func (c *rVBytesConstraint) renumber(mapping []nodeid) {
 174         c.v = mapping[c.v]
 175         c.result = mapping[c.result]
 176 }
 177
 178 func (c *rVBytesConstraint) String() string {
 179         return fmt.Sprintf("n%d = reflect n%d.Bytes()", c.result, c.v)
 180 }
 181
 182 func (c *rVBytesConstraint) solve(a *analysis, delta *nodeset) {
 183         changed := false
 184         for _, x := range delta.AppendTo(a.deltaSpace) {
 185                 vObj := nodeid(x)
 186                 tDyn, slice, indirect := a.taggedValue(vObj)
 187                 if indirect {
 188                         // TODO(adonovan): we'll need to implement this
 189                         // when we start creating indirect tagged objects.
 190                         panic("indirect tagged object")
 191                 }
 192
 193                 tSlice, ok := tDyn.Underlying().(*types.Slice)
 194                 if ok && types.Identical(tSlice.Elem(), types.Typ[types.Uint8]) {
 195                         if a.onlineCopy(c.result, slice) {
 196                                 changed = true
 197                         }
 198                 }
 199         }
 200         if changed {
 201                 a.addWork(c.result)
 202         }
 203 }
 204
 205 func ext۰reflect۰Value۰Bytes(a *analysis, cgn *cgnode) {
 206         a.addConstraint(&rVBytesConstraint{
 207                 v:      a.funcParams(cgn.obj),
 208                 result: a.funcResults(cgn.obj),
 209         })
 210 }
 211
 212 // ---------- func (Value).Call(in []Value) []Value ----------
 213
 214 // result = v.Call(in)
 215 type rVCallConstraint struct {
 216         cgn       *cgnode
 217         targets   nodeid // (indirect)
 218         v         nodeid // (ptr)
 219         arg       nodeid // = in[*]
 220         result    nodeid // (indirect)
 221         dotdotdot bool   // interpret last arg as a "..." slice
 222 }
 223
 224 func (c *rVCallConstraint) ptr() nodeid { return c.v }
 225 func (c *rVCallConstraint) presolve(h *hvn) {
 226         h.markIndirect(onodeid(c.targets), "rVCall.targets")
 227         h.markIndirect(onodeid(c.result), "rVCall.result")
 228 }
 229 func (c *rVCallConstraint) renumber(mapping []nodeid) {
 230         c.targets = mapping[c.targets]
 231         c.v = mapping[c.v]
 232         c.arg = mapping[c.arg]
 233         c.result = mapping[c.result]
 234 }
 235
 236 func (c *rVCallConstraint) String() string {
 237         return fmt.Sprintf("n%d = reflect n%d.Call(n%d)", c.result, c.v, c.arg)
 238 }
 239
 240 func (c *rVCallConstraint) solve(a *analysis, delta *nodeset) {
 241         if c.targets == 0 {
 242                 panic("no targets")
 243         }
 244
 245         changed := false
 246         for _, x := range delta.AppendTo(a.deltaSpace) {
 247                 vObj := nodeid(x)
 248                 tDyn, fn, indirect := a.taggedValue(vObj)
 249                 if indirect {
 250                         // TODO(adonovan): we'll need to implement this
 251                         // when we start creating indirect tagged objects.
 252                         panic("indirect tagged object")
 253                 }
 254
 255                 tSig, ok := tDyn.Underlying().(*types.Signature)
 256                 if !ok {
 257                         continue // not a function
 258                 }
 259                 if tSig.Recv() != nil {
 260                         panic(tSig) // TODO(adonovan): rethink when we implement Method()
 261                 }
 262
 263                 // Add dynamic call target.
 264                 if a.onlineCopy(c.targets, fn) {
 265                         a.addWork(c.targets)
 266                         // TODO(adonovan): is 'else continue' a sound optimisation here?
 267                 }
 268
 269                 // Allocate a P/R block.
 270                 tParams := tSig.Params()
 271                 tResults := tSig.Results()
 272                 params := a.addNodes(tParams, "rVCall.params")
 273                 results := a.addNodes(tResults, "rVCall.results")
 274
 275                 // Make a dynamic call to 'fn'.
 276                 a.store(fn, params, 1, a.sizeof(tParams))
 277                 a.load(results, fn, 1+a.sizeof(tParams), a.sizeof(tResults))
 278
 279                 // Populate P by type-asserting each actual arg (all merged in c.arg).
 280                 for i, n := 0, tParams.Len(); i < n; i++ {
 281                         T := tParams.At(i).Type()
 282                         a.typeAssert(T, params, c.arg, false)
 283                         params += nodeid(a.sizeof(T))
 284                 }
 285
 286                 // Use R by tagging and copying each actual result to c.result.
 287                 for i, n := 0, tResults.Len(); i < n; i++ {
 288                         T := tResults.At(i).Type()
 289                         // Convert from an arbitrary type to a reflect.Value
 290                         // (like MakeInterface followed by reflect.ValueOf).
 291                         if isInterface(T) {
 292                                 // (don't tag)
 293                                 if a.onlineCopy(c.result, results) {
 294                                         changed = true
 295                                 }
 296                         } else {
 297                                 obj := a.makeTagged(T, c.cgn, nil)
 298                                 a.onlineCopyN(obj+1, results, a.sizeof(T))
 299                                 if a.addLabel(c.result, obj) { // (true)
 300                                         changed = true
 301                                 }
 302                         }
 303                         results += nodeid(a.sizeof(T))
 304                 }
 305         }
 306         if changed {
 307                 a.addWork(c.result)
 308         }
 309 }
 310
 311 // Common code for direct (inlined) and indirect calls to (reflect.Value).Call.
 312 func reflectCallImpl(a *analysis, cgn *cgnode, site *callsite, recv, arg nodeid, dotdotdot bool) nodeid {
 313         // Allocate []reflect.Value array for the result.
 314         ret := a.nextNode()
 315         a.addNodes(types.NewArray(a.reflectValueObj.Type(), 1), "rVCall.ret")
 316         a.endObject(ret, cgn, nil)
 317
 318         // pts(targets) will be the set of possible call targets.
 319         site.targets = a.addOneNode(tInvalid, "rvCall.targets", nil)
 320
 321         // All arguments are merged since they arrive in a slice.
 322         argelts := a.addOneNode(a.reflectValueObj.Type(), "rVCall.args", nil)
 323         a.load(argelts, arg, 1, 1) // slice elements
 324
 325         a.addConstraint(&rVCallConstraint{
 326                 cgn:       cgn,
 327                 targets:   site.targets,
 328                 v:         recv,
 329                 arg:       argelts,
 330                 result:    ret + 1, // results go into elements of ret
 331                 dotdotdot: dotdotdot,
 332         })
 333         return ret
 334 }
 335
 336 func reflectCall(a *analysis, cgn *cgnode, dotdotdot bool) {
 337         // This is the shared contour implementation of (reflect.Value).Call
 338         // and CallSlice, as used by indirect calls (rare).
 339         // Direct calls are inlined in gen.go, eliding the
 340         // intermediate cgnode for Call.
 341         site := new(callsite)
 342         cgn.sites = append(cgn.sites, site)
 343         recv := a.funcParams(cgn.obj)
 344         arg := recv + 1
 345         ret := reflectCallImpl(a, cgn, site, recv, arg, dotdotdot)
 346         a.addressOf(cgn.fn.Signature.Results().At(0).Type(), a.funcResults(cgn.obj), ret)
 347 }
 348
 349 func ext۰reflect۰Value۰Call(a *analysis, cgn *cgnode) {
 350         reflectCall(a, cgn, false)
 351 }
 352
 353 func ext۰reflect۰Value۰CallSlice(a *analysis, cgn *cgnode) {
 354         // TODO(adonovan): implement.  Also, inline direct calls in gen.go too.
 355         if false {
 356                 reflectCall(a, cgn, true)
 357         }
 358 }
 359
 360 func ext۰reflect۰Value۰Convert(a *analysis, cgn *cgnode) {} // TODO(adonovan)
 361
 362 // ---------- func (Value).Elem() Value ----------
 363
 364 // result = v.Elem()
 365 type rVElemConstraint struct {
 366         cgn    *cgnode
 367         v      nodeid // (ptr)
 368         result nodeid // (indirect)
 369 }
 370
 371 func (c *rVElemConstraint) ptr() nodeid { return c.v }
 372 func (c *rVElemConstraint) presolve(h *hvn) {
 373         h.markIndirect(onodeid(c.result), "rVElem.result")
 374 }
 375 func (c *rVElemConstraint) renumber(mapping []nodeid) {
 376         c.v = mapping[c.v]
 377         c.result = mapping[c.result]
 378 }
 379
 380 func (c *rVElemConstraint) String() string {
 381         return fmt.Sprintf("n%d = reflect n%d.Elem()", c.result, c.v)
 382 }
 383
 384 func (c *rVElemConstraint) solve(a *analysis, delta *nodeset) {
 385         changed := false
 386         for _, x := range delta.AppendTo(a.deltaSpace) {
 387                 vObj := nodeid(x)
 388                 tDyn, payload, indirect := a.taggedValue(vObj)
 389                 if indirect {
 390                         // TODO(adonovan): we'll need to implement this
 391                         // when we start creating indirect tagged objects.
 392                         panic("indirect tagged object")
 393                 }
 394
 395                 switch t := tDyn.Underlying().(type) {
 396                 case *types.Interface:
 397                         if a.onlineCopy(c.result, payload) {
 398                                 changed = true
 399                         }
 400
 401                 case *types.Pointer:
 402                         obj := a.makeTagged(t.Elem(), c.cgn, nil)
 403                         a.load(obj+1, payload, 0, a.sizeof(t.Elem()))
 404                         if a.addLabel(c.result, obj) {
 405                                 changed = true
 406                         }
 407                 }
 408         }
 409         if changed {
 410                 a.addWork(c.result)
 411         }
 412 }
 413
 414 func ext۰reflect۰Value۰Elem(a *analysis, cgn *cgnode) {
 415         a.addConstraint(&rVElemConstraint{
 416                 cgn:    cgn,
 417                 v:      a.funcParams(cgn.obj),
 418                 result: a.funcResults(cgn.obj),
 419         })
 420 }
 421
 422 func ext۰reflect۰Value۰Field(a *analysis, cgn *cgnode)           {} // TODO(adonovan)
 423 func ext۰reflect۰Value۰FieldByIndex(a *analysis, cgn *cgnode)    {} // TODO(adonovan)
 424 func ext۰reflect۰Value۰FieldByName(a *analysis, cgn *cgnode)     {} // TODO(adonovan)
 425 func ext۰reflect۰Value۰FieldByNameFunc(a *analysis, cgn *cgnode) {} // TODO(adonovan)
 426
 427 // ---------- func (Value).Index() Value ----------
 428
 429 // result = v.Index()
 430 type rVIndexConstraint struct {
 431         cgn    *cgnode
 432         v      nodeid // (ptr)
 433         result nodeid // (indirect)
 434 }
 435
 436 func (c *rVIndexConstraint) ptr() nodeid { return c.v }
 437 func (c *rVIndexConstraint) presolve(h *hvn) {
 438         h.markIndirect(onodeid(c.result), "rVIndex.result")
 439 }
 440 func (c *rVIndexConstraint) renumber(mapping []nodeid) {
 441         c.v = mapping[c.v]
 442         c.result = mapping[c.result]
 443 }
 444
 445 func (c *rVIndexConstraint) String() string {
 446         return fmt.Sprintf("n%d = reflect n%d.Index()", c.result, c.v)
 447 }
 448
 449 func (c *rVIndexConstraint) solve(a *analysis, delta *nodeset) {
 450         changed := false
 451         for _, x := range delta.AppendTo(a.deltaSpace) {
 452                 vObj := nodeid(x)
 453                 tDyn, payload, indirect := a.taggedValue(vObj)
 454                 if indirect {
 455                         // TODO(adonovan): we'll need to implement this
 456                         // when we start creating indirect tagged objects.
 457                         panic("indirect tagged object")
 458                 }
 459
 460                 var res nodeid
 461                 switch t := tDyn.Underlying().(type) {
 462                 case *types.Array:
 463                         res = a.makeTagged(t.Elem(), c.cgn, nil)
 464                         a.onlineCopyN(res+1, payload+1, a.sizeof(t.Elem()))
 465
 466                 case *types.Slice:
 467                         res = a.makeTagged(t.Elem(), c.cgn, nil)
 468                         a.load(res+1, payload, 1, a.sizeof(t.Elem()))
 469
 470                 case *types.Basic:
 471                         if t.Kind() == types.String {
 472                                 res = a.makeTagged(types.Typ[types.Rune], c.cgn, nil)
 473                         }
 474                 }
 475                 if res != 0 && a.addLabel(c.result, res) {
 476                         changed = true
 477                 }
 478         }
 479         if changed {
 480                 a.addWork(c.result)
 481         }
 482 }
 483
 484 func ext۰reflect۰Value۰Index(a *analysis, cgn *cgnode) {
 485         a.addConstraint(&rVIndexConstraint{
 486                 cgn:    cgn,
 487                 v:      a.funcParams(cgn.obj),
 488                 result: a.funcResults(cgn.obj),
 489         })
 490 }
 491
 492 // ---------- func (Value).Interface() Value ----------
 493
 494 // result = v.Interface()
 495 type rVInterfaceConstraint struct {
 496         v      nodeid // (ptr)
 497         result nodeid // (indirect)
 498 }
 499
 500 func (c *rVInterfaceConstraint) ptr() nodeid { return c.v }
 501 func (c *rVInterfaceConstraint) presolve(h *hvn) {
 502         h.markIndirect(onodeid(c.result), "rVInterface.result")
 503 }
 504 func (c *rVInterfaceConstraint) renumber(mapping []nodeid) {
 505         c.v = mapping[c.v]
 506         c.result = mapping[c.result]
 507 }
 508
 509 func (c *rVInterfaceConstraint) String() string {
 510         return fmt.Sprintf("n%d = reflect n%d.Interface()", c.result, c.v)
 511 }
 512
 513 func (c *rVInterfaceConstraint) solve(a *analysis, delta *nodeset) {
 514         changed := false
 515         for _, x := range delta.AppendTo(a.deltaSpace) {
 516                 vObj := nodeid(x)
 517                 tDyn, payload, indirect := a.taggedValue(vObj)
 518                 if indirect {
 519                         // TODO(adonovan): we'll need to implement this
 520                         // when we start creating indirect tagged objects.
 521                         panic("indirect tagged object")
 522                 }
 523
 524                 if isInterface(tDyn) {
 525                         if a.onlineCopy(c.result, payload) {
 526                                 a.addWork(c.result)
 527                         }
 528                 } else {
 529                         if a.addLabel(c.result, vObj) {
 530                                 changed = true
 531                         }
 532                 }
 533         }
 534         if changed {
 535                 a.addWork(c.result)
 536         }
 537 }
 538
 539 func ext۰reflect۰Value۰Interface(a *analysis, cgn *cgnode) {
 540         a.addConstraint(&rVInterfaceConstraint{
 541                 v:      a.funcParams(cgn.obj),
 542                 result: a.funcResults(cgn.obj),
 543         })
 544 }
 545
 546 // ---------- func (Value).MapIndex(Value) Value ----------
 547
 548 // result = v.MapIndex(_)
 549 type rVMapIndexConstraint struct {
 550         cgn    *cgnode
 551         v      nodeid // (ptr)
 552         result nodeid // (indirect)
 553 }
 554
 555 func (c *rVMapIndexConstraint) ptr() nodeid { return c.v }
 556 func (c *rVMapIndexConstraint) presolve(h *hvn) {
 557         h.markIndirect(onodeid(c.result), "rVMapIndex.result")
 558 }
 559 func (c *rVMapIndexConstraint) renumber(mapping []nodeid) {
 560         c.v = mapping[c.v]
 561         c.result = mapping[c.result]
 562 }
 563
 564 func (c *rVMapIndexConstraint) String() string {
 565         return fmt.Sprintf("n%d = reflect n%d.MapIndex(_)", c.result, c.v)
 566 }
 567
 568 func (c *rVMapIndexConstraint) solve(a *analysis, delta *nodeset) {
 569         changed := false
 570         for _, x := range delta.AppendTo(a.deltaSpace) {
 571                 vObj := nodeid(x)
 572                 tDyn, m, indirect := a.taggedValue(vObj)
 573                 tMap, _ := tDyn.Underlying().(*types.Map)
 574                 if tMap == nil {
 575                         continue // not a map
 576                 }
 577                 if indirect {
 578                         // TODO(adonovan): we'll need to implement this
 579                         // when we start creating indirect tagged objects.
 580                         panic("indirect tagged object")
 581                 }
 582
 583                 obj := a.makeTagged(tMap.Elem(), c.cgn, nil)
 584                 a.load(obj+1, m, a.sizeof(tMap.Key()), a.sizeof(tMap.Elem()))
 585                 if a.addLabel(c.result, obj) {
 586                         changed = true
 587                 }
 588         }
 589         if changed {
 590                 a.addWork(c.result)
 591         }
 592 }
 593
 594 func ext۰reflect۰Value۰MapIndex(a *analysis, cgn *cgnode) {
 595         a.addConstraint(&rVMapIndexConstraint{
 596                 cgn:    cgn,
 597                 v:      a.funcParams(cgn.obj),
 598                 result: a.funcResults(cgn.obj),
 599         })
 600 }
 601
 602 // ---------- func (Value).MapKeys() []Value ----------
 603
 604 // result = v.MapKeys()
 605 type rVMapKeysConstraint struct {
 606         cgn    *cgnode
 607         v      nodeid // (ptr)
 608         result nodeid // (indirect)
 609 }
 610
 611 func (c *rVMapKeysConstraint) ptr() nodeid { return c.v }
 612 func (c *rVMapKeysConstraint) presolve(h *hvn) {
 613         h.markIndirect(onodeid(c.result), "rVMapKeys.result")
 614 }
 615 func (c *rVMapKeysConstraint) renumber(mapping []nodeid) {
 616         c.v = mapping[c.v]
 617         c.result = mapping[c.result]
 618 }
 619
 620 func (c *rVMapKeysConstraint) String() string {
 621         return fmt.Sprintf("n%d = reflect n%d.MapKeys()", c.result, c.v)
 622 }
 623
 624 func (c *rVMapKeysConstraint) solve(a *analysis, delta *nodeset) {
 625         changed := false
 626         for _, x := range delta.AppendTo(a.deltaSpace) {
 627                 vObj := nodeid(x)
 628                 tDyn, m, indirect := a.taggedValue(vObj)
 629                 tMap, _ := tDyn.Underlying().(*types.Map)
 630                 if tMap == nil {
 631                         continue // not a map
 632                 }
 633                 if indirect {
 634                         // TODO(adonovan): we'll need to implement this
 635                         // when we start creating indirect tagged objects.
 636                         panic("indirect tagged object")
 637                 }
 638
 639                 kObj := a.makeTagged(tMap.Key(), c.cgn, nil)
 640                 a.load(kObj+1, m, 0, a.sizeof(tMap.Key()))
 641                 if a.addLabel(c.result, kObj) {
 642                         changed = true
 643                 }
 644         }
 645         if changed {
 646                 a.addWork(c.result)
 647         }
 648 }
 649
 650 func ext۰reflect۰Value۰MapKeys(a *analysis, cgn *cgnode) {
 651         // Allocate an array for the result.
 652         obj := a.nextNode()
 653         T := types.NewSlice(a.reflectValueObj.Type())
 654         a.addNodes(sliceToArray(T), "reflect.MapKeys result")
 655         a.endObject(obj, cgn, nil)
 656         a.addressOf(T, a.funcResults(cgn.obj), obj)
 657
 658         a.addConstraint(&rVMapKeysConstraint{
 659                 cgn:    cgn,
 660                 v:      a.funcParams(cgn.obj),
 661                 result: obj + 1, // result is stored in array elems
 662         })
 663 }
 664
 665 func ext۰reflect۰Value۰Method(a *analysis, cgn *cgnode)       {} // TODO(adonovan)
 666 func ext۰reflect۰Value۰MethodByName(a *analysis, cgn *cgnode) {} // TODO(adonovan)
 667
 668 // ---------- func (Value).Recv(Value) Value ----------
 669
 670 // result, _ = v.Recv()
 671 type rVRecvConstraint struct {
 672         cgn    *cgnode
 673         v      nodeid // (ptr)
 674         result nodeid // (indirect)
 675 }
 676
 677 func (c *rVRecvConstraint) ptr() nodeid { return c.v }
 678 func (c *rVRecvConstraint) presolve(h *hvn) {
 679         h.markIndirect(onodeid(c.result), "rVRecv.result")
 680 }
 681 func (c *rVRecvConstraint) renumber(mapping []nodeid) {
 682         c.v = mapping[c.v]
 683         c.result = mapping[c.result]
 684 }
 685
 686 func (c *rVRecvConstraint) String() string {
 687         return fmt.Sprintf("n%d = reflect n%d.Recv()", c.result, c.v)
 688 }
 689
 690 func (c *rVRecvConstraint) solve(a *analysis, delta *nodeset) {
 691         changed := false
 692         for _, x := range delta.AppendTo(a.deltaSpace) {
 693                 vObj := nodeid(x)
 694                 tDyn, ch, indirect := a.taggedValue(vObj)
 695                 tChan, _ := tDyn.Underlying().(*types.Chan)
 696                 if tChan == nil {
 697                         continue // not a channel
 698                 }
 699                 if indirect {
 700                         // TODO(adonovan): we'll need to implement this
 701                         // when we start creating indirect tagged objects.
 702                         panic("indirect tagged object")
 703                 }
 704
 705                 tElem := tChan.Elem()
 706                 elemObj := a.makeTagged(tElem, c.cgn, nil)
 707                 a.load(elemObj+1, ch, 0, a.sizeof(tElem))
 708                 if a.addLabel(c.result, elemObj) {
 709                         changed = true
 710                 }
 711         }
 712         if changed {
 713                 a.addWork(c.result)
 714         }
 715 }
 716
 717 func ext۰reflect۰Value۰Recv(a *analysis, cgn *cgnode) {
 718         a.addConstraint(&rVRecvConstraint{
 719                 cgn:    cgn,
 720                 v:      a.funcParams(cgn.obj),
 721                 result: a.funcResults(cgn.obj),
 722         })
 723 }
 724
 725 // ---------- func (Value).Send(Value) ----------
 726
 727 // v.Send(x)
 728 type rVSendConstraint struct {
 729         cgn *cgnode
 730         v   nodeid // (ptr)
 731         x   nodeid
 732 }
 733
 734 func (c *rVSendConstraint) ptr() nodeid   { return c.v }
 735 func (c *rVSendConstraint) presolve(*hvn) {}
 736 func (c *rVSendConstraint) renumber(mapping []nodeid) {
 737         c.v = mapping[c.v]
 738         c.x = mapping[c.x]
 739 }
 740
 741 func (c *rVSendConstraint) String() string {
 742         return fmt.Sprintf("reflect n%d.Send(n%d)", c.v, c.x)
 743 }
 744
 745 func (c *rVSendConstraint) solve(a *analysis, delta *nodeset) {
 746         for _, x := range delta.AppendTo(a.deltaSpace) {
 747                 vObj := nodeid(x)
 748                 tDyn, ch, indirect := a.taggedValue(vObj)
 749                 tChan, _ := tDyn.Underlying().(*types.Chan)
 750                 if tChan == nil {
 751                         continue // not a channel
 752                 }
 753                 if indirect {
 754                         // TODO(adonovan): we'll need to implement this
 755                         // when we start creating indirect tagged objects.
 756                         panic("indirect tagged object")
 757                 }
 758
 759                 // Extract x's payload to xtmp, then store to channel.
 760                 tElem := tChan.Elem()
 761                 xtmp := a.addNodes(tElem, "Send.xtmp")
 762                 a.typeAssert(tElem, xtmp, c.x, false)
 763                 a.store(ch, xtmp, 0, a.sizeof(tElem))
 764         }
 765 }
 766
 767 func ext۰reflect۰Value۰Send(a *analysis, cgn *cgnode) {
 768         params := a.funcParams(cgn.obj)
 769         a.addConstraint(&rVSendConstraint{
 770                 cgn: cgn,
 771                 v:   params,
 772                 x:   params + 1,
 773         })
 774 }
 775
 776 func ext۰reflect۰Value۰Set(a *analysis, cgn *cgnode) {} // TODO(adonovan)
 777
 778 // ---------- func (Value).SetBytes(x []byte) ----------
 779
 780 // v.SetBytes(x)
 781 type rVSetBytesConstraint struct {
 782         cgn *cgnode
 783         v   nodeid // (ptr)
 784         x   nodeid
 785 }
 786
 787 func (c *rVSetBytesConstraint) ptr() nodeid   { return c.v }
 788 func (c *rVSetBytesConstraint) presolve(*hvn) {}
 789 func (c *rVSetBytesConstraint) renumber(mapping []nodeid) {
 790         c.v = mapping[c.v]
 791         c.x = mapping[c.x]
 792 }
 793
 794 func (c *rVSetBytesConstraint) String() string {
 795         return fmt.Sprintf("reflect n%d.SetBytes(n%d)", c.v, c.x)
 796 }
 797
 798 func (c *rVSetBytesConstraint) solve(a *analysis, delta *nodeset) {
 799         for _, x := range delta.AppendTo(a.deltaSpace) {
 800                 vObj := nodeid(x)
 801                 tDyn, slice, indirect := a.taggedValue(vObj)
 802                 if indirect {
 803                         // TODO(adonovan): we'll need to implement this
 804                         // when we start creating indirect tagged objects.
 805                         panic("indirect tagged object")
 806                 }
 807
 808                 tSlice, ok := tDyn.Underlying().(*types.Slice)
 809                 if ok && types.Identical(tSlice.Elem(), types.Typ[types.Uint8]) {
 810                         if a.onlineCopy(slice, c.x) {
 811                                 a.addWork(slice)
 812                         }
 813                 }
 814         }
 815 }
 816
 817 func ext۰reflect۰Value۰SetBytes(a *analysis, cgn *cgnode) {
 818         params := a.funcParams(cgn.obj)
 819         a.addConstraint(&rVSetBytesConstraint{
 820                 cgn: cgn,
 821                 v:   params,
 822                 x:   params + 1,
 823         })
 824 }
 825
 826 // ---------- func (Value).SetMapIndex(k Value, v Value) ----------
 827
 828 // v.SetMapIndex(key, val)
 829 type rVSetMapIndexConstraint struct {
 830         cgn *cgnode
 831         v   nodeid // (ptr)
 832         key nodeid
 833         val nodeid
 834 }
 835
 836 func (c *rVSetMapIndexConstraint) ptr() nodeid   { return c.v }
 837 func (c *rVSetMapIndexConstraint) presolve(*hvn) {}
 838 func (c *rVSetMapIndexConstraint) renumber(mapping []nodeid) {
 839         c.v = mapping[c.v]
 840         c.key = mapping[c.key]
 841         c.val = mapping[c.val]
 842 }
 843
 844 func (c *rVSetMapIndexConstraint) String() string {
 845         return fmt.Sprintf("reflect n%d.SetMapIndex(n%d, n%d)", c.v, c.key, c.val)
 846 }
 847
 848 func (c *rVSetMapIndexConstraint) solve(a *analysis, delta *nodeset) {
 849         for _, x := range delta.AppendTo(a.deltaSpace) {
 850                 vObj := nodeid(x)
 851                 tDyn, m, indirect := a.taggedValue(vObj)
 852                 tMap, _ := tDyn.Underlying().(*types.Map)
 853                 if tMap == nil {
 854                         continue // not a map
 855                 }
 856                 if indirect {
 857                         // TODO(adonovan): we'll need to implement this
 858                         // when we start creating indirect tagged objects.
 859                         panic("indirect tagged object")
 860                 }
 861
 862                 keysize := a.sizeof(tMap.Key())
 863
 864                 // Extract key's payload to keytmp, then store to map key.
 865                 keytmp := a.addNodes(tMap.Key(), "SetMapIndex.keytmp")
 866                 a.typeAssert(tMap.Key(), keytmp, c.key, false)
 867                 a.store(m, keytmp, 0, keysize)
 868
 869                 // Extract val's payload to vtmp, then store to map value.
 870                 valtmp := a.addNodes(tMap.Elem(), "SetMapIndex.valtmp")
 871                 a.typeAssert(tMap.Elem(), valtmp, c.val, false)
 872                 a.store(m, valtmp, keysize, a.sizeof(tMap.Elem()))
 873         }
 874 }
 875
 876 func ext۰reflect۰Value۰SetMapIndex(a *analysis, cgn *cgnode) {
 877         params := a.funcParams(cgn.obj)
 878         a.addConstraint(&rVSetMapIndexConstraint{
 879                 cgn: cgn,
 880                 v:   params,
 881                 key: params + 1,
 882                 val: params + 2,
 883         })
 884 }
 885
 886 func ext۰reflect۰Value۰SetPointer(a *analysis, cgn *cgnode) {} // TODO(adonovan)
 887
 888 // ---------- func (Value).Slice(v Value, i, j int) Value ----------
 889
 890 // result = v.Slice(_, _)
 891 type rVSliceConstraint struct {
 892         cgn    *cgnode
 893         v      nodeid // (ptr)
 894         result nodeid // (indirect)
 895 }
 896
 897 func (c *rVSliceConstraint) ptr() nodeid { return c.v }
 898 func (c *rVSliceConstraint) presolve(h *hvn) {
 899         h.markIndirect(onodeid(c.result), "rVSlice.result")
 900 }
 901 func (c *rVSliceConstraint) renumber(mapping []nodeid) {
 902         c.v = mapping[c.v]
 903         c.result = mapping[c.result]
 904 }
 905
 906 func (c *rVSliceConstraint) String() string {
 907         return fmt.Sprintf("n%d = reflect n%d.Slice(_, _)", c.result, c.v)
 908 }
 909
 910 func (c *rVSliceConstraint) solve(a *analysis, delta *nodeset) {
 911         changed := false
 912         for _, x := range delta.AppendTo(a.deltaSpace) {
 913                 vObj := nodeid(x)
 914                 tDyn, payload, indirect := a.taggedValue(vObj)
 915                 if indirect {
 916                         // TODO(adonovan): we'll need to implement this
 917                         // when we start creating indirect tagged objects.
 918                         panic("indirect tagged object")
 919                 }
 920
 921                 var res nodeid
 922                 switch t := tDyn.Underlying().(type) {
 923                 case *types.Pointer:
 924                         if tArr, ok := t.Elem().Underlying().(*types.Array); ok {
 925                                 // pointer to array
 926                                 res = a.makeTagged(types.NewSlice(tArr.Elem()), c.cgn, nil)
 927                                 if a.onlineCopy(res+1, payload) {
 928                                         a.addWork(res + 1)
 929                                 }
 930                         }
 931
 932                 case *types.Array:
 933                         // TODO(adonovan): implement addressable
 934                         // arrays when we do indirect tagged objects.
 935
 936                 case *types.Slice:
 937                         res = vObj
 938
 939                 case *types.Basic:
 940                         if t == types.Typ[types.String] {
 941                                 res = vObj
 942                         }
 943                 }
 944
 945                 if res != 0 && a.addLabel(c.result, res) {
 946                         changed = true
 947                 }
 948         }
 949         if changed {
 950                 a.addWork(c.result)
 951         }
 952 }
 953
 954 func ext۰reflect۰Value۰Slice(a *analysis, cgn *cgnode) {
 955         a.addConstraint(&rVSliceConstraint{
 956                 cgn:    cgn,
 957                 v:      a.funcParams(cgn.obj),
 958                 result: a.funcResults(cgn.obj),
 959         })
 960 }
 961
 962 // -------------------- Standalone reflect functions --------------------
 963
 964 func ext۰reflect۰Append(a *analysis, cgn *cgnode)      {} // TODO(adonovan)
 965 func ext۰reflect۰AppendSlice(a *analysis, cgn *cgnode) {} // TODO(adonovan)
 966 func ext۰reflect۰Copy(a *analysis, cgn *cgnode)        {} // TODO(adonovan)
 967
 968 // ---------- func ChanOf(ChanDir, Type) Type ----------
 969
 970 // result = ChanOf(dir, t)
 971 type reflectChanOfConstraint struct {
 972         cgn    *cgnode
 973         t      nodeid // (ptr)
 974         result nodeid // (indirect)
 975         dirs   []types.ChanDir
 976 }
 977
 978 func (c *reflectChanOfConstraint) ptr() nodeid { return c.t }
 979 func (c *reflectChanOfConstraint) presolve(h *hvn) {
 980         h.markIndirect(onodeid(c.result), "reflectChanOf.result")
 981 }
 982 func (c *reflectChanOfConstraint) renumber(mapping []nodeid) {
 983         c.t = mapping[c.t]
 984         c.result = mapping[c.result]
 985 }
 986
 987 func (c *reflectChanOfConstraint) String() string {
 988         return fmt.Sprintf("n%d = reflect.ChanOf(n%d)", c.result, c.t)
 989 }
 990
 991 func (c *reflectChanOfConstraint) solve(a *analysis, delta *nodeset) {
 992         changed := false
 993         for _, x := range delta.AppendTo(a.deltaSpace) {
 994                 tObj := nodeid(x)
 995                 T := a.rtypeTaggedValue(tObj)
 996
 997                 if typeTooHigh(T) {
 998                         continue
 999                 }
1000
1001                 for _, dir := range c.dirs {
1002                         if a.addLabel(c.result, a.makeRtype(types.NewChan(dir, T))) {
1003                                 changed = true
1004                         }
1005                 }
1006         }
1007         if changed {
1008                 a.addWork(c.result)
1009         }
1010 }
1011
1012 // dirMap maps reflect.ChanDir to the set of channel types generated by ChanOf.
1013 var dirMap = [...][]types.ChanDir{
1014         0:               {types.SendOnly, types.RecvOnly, types.SendRecv}, // unknown
1015         reflect.RecvDir: {types.RecvOnly},
1016         reflect.SendDir: {types.SendOnly},
1017         reflect.BothDir: {types.SendRecv},
1018 }
1019
1020 func ext۰reflect۰ChanOf(a *analysis, cgn *cgnode) {
1021         // If we have access to the callsite,
1022         // and the channel argument is a constant (as is usual),
1023         // only generate the requested direction.
1024         var dir reflect.ChanDir // unknown
1025         if site := cgn.callersite; site != nil {
1026                 if c, ok := site.instr.Common().Args[0].(*ssa.Const); ok {
1027                         v, _ := constant.Int64Val(c.Value)
1028                         if 0 <= v && v <= int64(reflect.BothDir) {
1029                                 dir = reflect.ChanDir(v)
1030                         }
1031                 }
1032         }
1033
1034         params := a.funcParams(cgn.obj)
1035         a.addConstraint(&reflectChanOfConstraint{
1036                 cgn:    cgn,
1037                 t:      params + 1,
1038                 result: a.funcResults(cgn.obj),
1039                 dirs:   dirMap[dir],
1040         })
1041 }
1042
1043 // ---------- func Indirect(v Value) Value ----------
1044
1045 // result = Indirect(v)
1046 type reflectIndirectConstraint struct {
1047         cgn    *cgnode
1048         v      nodeid // (ptr)
1049         result nodeid // (indirect)
1050 }
1051
1052 func (c *reflectIndirectConstraint) ptr() nodeid { return c.v }
1053 func (c *reflectIndirectConstraint) presolve(h *hvn) {
1054         h.markIndirect(onodeid(c.result), "reflectIndirect.result")
1055 }
1056 func (c *reflectIndirectConstraint) renumber(mapping []nodeid) {
1057         c.v = mapping[c.v]
1058         c.result = mapping[c.result]
1059 }
1060
1061 func (c *reflectIndirectConstraint) String() string {
1062         return fmt.Sprintf("n%d = reflect.Indirect(n%d)", c.result, c.v)
1063 }
1064
1065 func (c *reflectIndirectConstraint) solve(a *analysis, delta *nodeset) {
1066         changed := false
1067         for _, x := range delta.AppendTo(a.deltaSpace) {
1068                 vObj := nodeid(x)
1069                 tDyn, _, _ := a.taggedValue(vObj)
1070                 var res nodeid
1071                 if tPtr, ok := tDyn.Underlying().(*types.Pointer); ok {
1072                         // load the payload of the pointer's tagged object
1073                         // into a new tagged object
1074                         res = a.makeTagged(tPtr.Elem(), c.cgn, nil)
1075                         a.load(res+1, vObj+1, 0, a.sizeof(tPtr.Elem()))
1076                 } else {
1077                         res = vObj
1078                 }
1079
1080                 if a.addLabel(c.result, res) {
1081                         changed = true
1082                 }
1083         }
1084         if changed {
1085                 a.addWork(c.result)
1086         }
1087 }
1088
1089 func ext۰reflect۰Indirect(a *analysis, cgn *cgnode) {
1090         a.addConstraint(&reflectIndirectConstraint{
1091                 cgn:    cgn,
1092                 v:      a.funcParams(cgn.obj),
1093                 result: a.funcResults(cgn.obj),
1094         })
1095 }
1096
1097 // ---------- func MakeChan(Type) Value ----------
1098
1099 // result = MakeChan(typ)
1100 type reflectMakeChanConstraint struct {
1101         cgn    *cgnode
1102         typ    nodeid // (ptr)
1103         result nodeid // (indirect)
1104 }
1105
1106 func (c *reflectMakeChanConstraint) ptr() nodeid { return c.typ }
1107 func (c *reflectMakeChanConstraint) presolve(h *hvn) {
1108         h.markIndirect(onodeid(c.result), "reflectMakeChan.result")
1109 }
1110 func (c *reflectMakeChanConstraint) renumber(mapping []nodeid) {
1111         c.typ = mapping[c.typ]
1112         c.result = mapping[c.result]
1113 }
1114
1115 func (c *reflectMakeChanConstraint) String() string {
1116         return fmt.Sprintf("n%d = reflect.MakeChan(n%d)", c.result, c.typ)
1117 }
1118
1119 func (c *reflectMakeChanConstraint) solve(a *analysis, delta *nodeset) {
1120         changed := false
1121         for _, x := range delta.AppendTo(a.deltaSpace) {
1122                 typObj := nodeid(x)
1123                 T := a.rtypeTaggedValue(typObj)
1124                 tChan, ok := T.Underlying().(*types.Chan)
1125                 if !ok || tChan.Dir() != types.SendRecv {
1126                         continue // not a bidirectional channel type
1127                 }
1128
1129                 obj := a.nextNode()
1130                 a.addNodes(tChan.Elem(), "reflect.MakeChan.value")
1131                 a.endObject(obj, c.cgn, nil)
1132
1133                 // put its address in a new T-tagged object
1134                 id := a.makeTagged(T, c.cgn, nil)
1135                 a.addLabel(id+1, obj)
1136
1137                 // flow the T-tagged object to the result
1138                 if a.addLabel(c.result, id) {
1139                         changed = true
1140                 }
1141         }
1142         if changed {
1143                 a.addWork(c.result)
1144         }
1145 }
1146
1147 func ext۰reflect۰MakeChan(a *analysis, cgn *cgnode) {
1148         a.addConstraint(&reflectMakeChanConstraint{
1149                 cgn:    cgn,
1150                 typ:    a.funcParams(cgn.obj),
1151                 result: a.funcResults(cgn.obj),
1152         })
1153 }
1154
1155 func ext۰reflect۰MakeFunc(a *analysis, cgn *cgnode) {} // TODO(adonovan)
1156
1157 // ---------- func MakeMap(Type) Value ----------
1158
1159 // result = MakeMap(typ)
1160 type reflectMakeMapConstraint struct {
1161         cgn    *cgnode
1162         typ    nodeid // (ptr)
1163         result nodeid // (indirect)
1164 }
1165
1166 func (c *reflectMakeMapConstraint) ptr() nodeid { return c.typ }
1167 func (c *reflectMakeMapConstraint) presolve(h *hvn) {
1168         h.markIndirect(onodeid(c.result), "reflectMakeMap.result")
1169 }
1170 func (c *reflectMakeMapConstraint) renumber(mapping []nodeid) {
1171         c.typ = mapping[c.typ]
1172         c.result = mapping[c.result]
1173 }
1174
1175 func (c *reflectMakeMapConstraint) String() string {
1176         return fmt.Sprintf("n%d = reflect.MakeMap(n%d)", c.result, c.typ)
1177 }
1178
1179 func (c *reflectMakeMapConstraint) solve(a *analysis, delta *nodeset) {
1180         changed := false
1181         for _, x := range delta.AppendTo(a.deltaSpace) {
1182                 typObj := nodeid(x)
1183                 T := a.rtypeTaggedValue(typObj)
1184                 tMap, ok := T.Underlying().(*types.Map)
1185                 if !ok {
1186                         continue // not a map type
1187                 }
1188
1189                 mapObj := a.nextNode()
1190                 a.addNodes(tMap.Key(), "reflect.MakeMap.key")
1191                 a.addNodes(tMap.Elem(), "reflect.MakeMap.value")
1192                 a.endObject(mapObj, c.cgn, nil)
1193
1194                 // put its address in a new T-tagged object
1195                 id := a.makeTagged(T, c.cgn, nil)
1196                 a.addLabel(id+1, mapObj)
1197
1198                 // flow the T-tagged object to the result
1199                 if a.addLabel(c.result, id) {
1200                         changed = true
1201                 }
1202         }
1203         if changed {
1204                 a.addWork(c.result)
1205         }
1206 }
1207
1208 func ext۰reflect۰MakeMap(a *analysis, cgn *cgnode) {
1209         a.addConstraint(&reflectMakeMapConstraint{
1210                 cgn:    cgn,
1211                 typ:    a.funcParams(cgn.obj),
1212                 result: a.funcResults(cgn.obj),
1213         })
1214 }
1215
1216 // ---------- func MakeSlice(Type) Value ----------
1217
1218 // result = MakeSlice(typ)
1219 type reflectMakeSliceConstraint struct {
1220         cgn    *cgnode
1221         typ    nodeid // (ptr)
1222         result nodeid // (indirect)
1223 }
1224
1225 func (c *reflectMakeSliceConstraint) ptr() nodeid { return c.typ }
1226 func (c *reflectMakeSliceConstraint) presolve(h *hvn) {
1227         h.markIndirect(onodeid(c.result), "reflectMakeSlice.result")
1228 }
1229 func (c *reflectMakeSliceConstraint) renumber(mapping []nodeid) {
1230         c.typ = mapping[c.typ]
1231         c.result = mapping[c.result]
1232 }
1233
1234 func (c *reflectMakeSliceConstraint) String() string {
1235         return fmt.Sprintf("n%d = reflect.MakeSlice(n%d)", c.result, c.typ)
1236 }
1237
1238 func (c *reflectMakeSliceConstraint) solve(a *analysis, delta *nodeset) {
1239         changed := false
1240         for _, x := range delta.AppendTo(a.deltaSpace) {
1241                 typObj := nodeid(x)
1242                 T := a.rtypeTaggedValue(typObj)
1243                 if _, ok := T.Underlying().(*types.Slice); !ok {
1244                         continue // not a slice type
1245                 }
1246
1247                 obj := a.nextNode()
1248                 a.addNodes(sliceToArray(T), "reflect.MakeSlice")
1249                 a.endObject(obj, c.cgn, nil)
1250
1251                 // put its address in a new T-tagged object
1252                 id := a.makeTagged(T, c.cgn, nil)
1253                 a.addLabel(id+1, obj)
1254
1255                 // flow the T-tagged object to the result
1256                 if a.addLabel(c.result, id) {
1257                         changed = true
1258                 }
1259         }
1260         if changed {
1261                 a.addWork(c.result)
1262         }
1263 }
1264
1265 func ext۰reflect۰MakeSlice(a *analysis, cgn *cgnode) {
1266         a.addConstraint(&reflectMakeSliceConstraint{
1267                 cgn:    cgn,
1268                 typ:    a.funcParams(cgn.obj),
1269                 result: a.funcResults(cgn.obj),
1270         })
1271 }
1272
1273 func ext۰reflect۰MapOf(a *analysis, cgn *cgnode) {} // TODO(adonovan)
1274
1275 // ---------- func New(Type) Value ----------
1276
1277 // result = New(typ)
1278 type reflectNewConstraint struct {
1279         cgn    *cgnode
1280         typ    nodeid // (ptr)
1281         result nodeid // (indirect)
1282 }
1283
1284 func (c *reflectNewConstraint) ptr() nodeid { return c.typ }
1285 func (c *reflectNewConstraint) presolve(h *hvn) {
1286         h.markIndirect(onodeid(c.result), "reflectNew.result")
1287 }
1288 func (c *reflectNewConstraint) renumber(mapping []nodeid) {
1289         c.typ = mapping[c.typ]
1290         c.result = mapping[c.result]
1291 }
1292
1293 func (c *reflectNewConstraint) String() string {
1294         return fmt.Sprintf("n%d = reflect.New(n%d)", c.result, c.typ)
1295 }
1296
1297 func (c *reflectNewConstraint) solve(a *analysis, delta *nodeset) {
1298         changed := false
1299         for _, x := range delta.AppendTo(a.deltaSpace) {
1300                 typObj := nodeid(x)
1301                 T := a.rtypeTaggedValue(typObj)
1302
1303                 // allocate new T object
1304                 newObj := a.nextNode()
1305                 a.addNodes(T, "reflect.New")
1306                 a.endObject(newObj, c.cgn, nil)
1307
1308                 // put its address in a new *T-tagged object
1309                 id := a.makeTagged(types.NewPointer(T), c.cgn, nil)
1310                 a.addLabel(id+1, newObj)
1311
1312                 // flow the pointer to the result
1313                 if a.addLabel(c.result, id) {
1314                         changed = true
1315                 }
1316         }
1317         if changed {
1318                 a.addWork(c.result)
1319         }
1320 }
1321
1322 func ext۰reflect۰New(a *analysis, cgn *cgnode) {
1323         a.addConstraint(&reflectNewConstraint{
1324                 cgn:    cgn,
1325                 typ:    a.funcParams(cgn.obj),
1326                 result: a.funcResults(cgn.obj),
1327         })
1328 }
1329
1330 func ext۰reflect۰NewAt(a *analysis, cgn *cgnode) {
1331         ext۰reflect۰New(a, cgn)
1332
1333         // TODO(adonovan): also report dynamic calls to unsound intrinsics.
1334         if site := cgn.callersite; site != nil {
1335                 a.warnf(site.pos(), "unsound: %s contains a reflect.NewAt() call", site.instr.Parent())
1336         }
1337 }
1338
1339 // ---------- func PtrTo(Type) Type ----------
1340
1341 // result = PtrTo(t)
1342 type reflectPtrToConstraint struct {
1343         cgn    *cgnode
1344         t      nodeid // (ptr)
1345         result nodeid // (indirect)
1346 }
1347
1348 func (c *reflectPtrToConstraint) ptr() nodeid { return c.t }
1349 func (c *reflectPtrToConstraint) presolve(h *hvn) {
1350         h.markIndirect(onodeid(c.result), "reflectPtrTo.result")
1351 }
1352 func (c *reflectPtrToConstraint) renumber(mapping []nodeid) {
1353         c.t = mapping[c.t]
1354         c.result = mapping[c.result]
1355 }
1356
1357 func (c *reflectPtrToConstraint) String() string {
1358         return fmt.Sprintf("n%d = reflect.PtrTo(n%d)", c.result, c.t)
1359 }
1360
1361 func (c *reflectPtrToConstraint) solve(a *analysis, delta *nodeset) {
1362         changed := false
1363         for _, x := range delta.AppendTo(a.deltaSpace) {
1364                 tObj := nodeid(x)
1365                 T := a.rtypeTaggedValue(tObj)
1366
1367                 if typeTooHigh(T) {
1368                         continue
1369                 }
1370
1371                 if a.addLabel(c.result, a.makeRtype(types.NewPointer(T))) {
1372                         changed = true
1373                 }
1374         }
1375         if changed {
1376                 a.addWork(c.result)
1377         }
1378 }
1379
1380 func ext۰reflect۰PtrTo(a *analysis, cgn *cgnode) {
1381         a.addConstraint(&reflectPtrToConstraint{
1382                 cgn:    cgn,
1383                 t:      a.funcParams(cgn.obj),
1384                 result: a.funcResults(cgn.obj),
1385         })
1386 }
1387
1388 func ext۰reflect۰Select(a *analysis, cgn *cgnode) {} // TODO(adonovan)
1389
1390 // ---------- func SliceOf(Type) Type ----------
1391
1392 // result = SliceOf(t)
1393 type reflectSliceOfConstraint struct {
1394         cgn    *cgnode
1395         t      nodeid // (ptr)
1396         result nodeid // (indirect)
1397 }
1398
1399 func (c *reflectSliceOfConstraint) ptr() nodeid { return c.t }
1400 func (c *reflectSliceOfConstraint) presolve(h *hvn) {
1401         h.markIndirect(onodeid(c.result), "reflectSliceOf.result")
1402 }
1403 func (c *reflectSliceOfConstraint) renumber(mapping []nodeid) {
1404         c.t = mapping[c.t]
1405         c.result = mapping[c.result]
1406 }
1407
1408 func (c *reflectSliceOfConstraint) String() string {
1409         return fmt.Sprintf("n%d = reflect.SliceOf(n%d)", c.result, c.t)
1410 }
1411
1412 func (c *reflectSliceOfConstraint) solve(a *analysis, delta *nodeset) {
1413         changed := false
1414         for _, x := range delta.AppendTo(a.deltaSpace) {
1415                 tObj := nodeid(x)
1416                 T := a.rtypeTaggedValue(tObj)
1417
1418                 if typeTooHigh(T) {
1419                         continue
1420                 }
1421
1422                 if a.addLabel(c.result, a.makeRtype(types.NewSlice(T))) {
1423                         changed = true
1424                 }
1425         }
1426         if changed {
1427                 a.addWork(c.result)
1428         }
1429 }
1430
1431 func ext۰reflect۰SliceOf(a *analysis, cgn *cgnode) {
1432         a.addConstraint(&reflectSliceOfConstraint{
1433                 cgn:    cgn,
1434                 t:      a.funcParams(cgn.obj),
1435                 result: a.funcResults(cgn.obj),
1436         })
1437 }
1438
1439 // ---------- func TypeOf(v Value) Type ----------
1440
1441 // result = TypeOf(i)
1442 type reflectTypeOfConstraint struct {
1443         cgn    *cgnode
1444         i      nodeid // (ptr)
1445         result nodeid // (indirect)
1446 }
1447
1448 func (c *reflectTypeOfConstraint) ptr() nodeid { return c.i }
1449 func (c *reflectTypeOfConstraint) presolve(h *hvn) {
1450         h.markIndirect(onodeid(c.result), "reflectTypeOf.result")
1451 }
1452 func (c *reflectTypeOfConstraint) renumber(mapping []nodeid) {
1453         c.i = mapping[c.i]
1454         c.result = mapping[c.result]
1455 }
1456
1457 func (c *reflectTypeOfConstraint) String() string {
1458         return fmt.Sprintf("n%d = reflect.TypeOf(n%d)", c.result, c.i)
1459 }
1460
1461 func (c *reflectTypeOfConstraint) solve(a *analysis, delta *nodeset) {
1462         changed := false
1463         for _, x := range delta.AppendTo(a.deltaSpace) {
1464                 iObj := nodeid(x)
1465                 tDyn, _, _ := a.taggedValue(iObj)
1466                 if a.addLabel(c.result, a.makeRtype(tDyn)) {
1467                         changed = true
1468                 }
1469         }
1470         if changed {
1471                 a.addWork(c.result)
1472         }
1473 }
1474
1475 func ext۰reflect۰TypeOf(a *analysis, cgn *cgnode) {
1476         a.addConstraint(&reflectTypeOfConstraint{
1477                 cgn:    cgn,
1478                 i:      a.funcParams(cgn.obj),
1479                 result: a.funcResults(cgn.obj),
1480         })
1481 }
1482
1483 // ---------- func ValueOf(interface{}) Value ----------
1484
1485 func ext۰reflect۰ValueOf(a *analysis, cgn *cgnode) {
1486         // TODO(adonovan): when we start creating indirect tagged
1487         // objects, we'll need to handle them specially here since
1488         // they must never appear in the PTS of an interface{}.
1489         a.copy(a.funcResults(cgn.obj), a.funcParams(cgn.obj), 1)
1490 }
1491
1492 // ---------- func Zero(Type) Value ----------
1493
1494 // result = Zero(typ)
1495 type reflectZeroConstraint struct {
1496         cgn    *cgnode
1497         typ    nodeid // (ptr)
1498         result nodeid // (indirect)
1499 }
1500
1501 func (c *reflectZeroConstraint) ptr() nodeid { return c.typ }
1502 func (c *reflectZeroConstraint) presolve(h *hvn) {
1503         h.markIndirect(onodeid(c.result), "reflectZero.result")
1504 }
1505 func (c *reflectZeroConstraint) renumber(mapping []nodeid) {
1506         c.typ = mapping[c.typ]
1507         c.result = mapping[c.result]
1508 }
1509
1510 func (c *reflectZeroConstraint) String() string {
1511         return fmt.Sprintf("n%d = reflect.Zero(n%d)", c.result, c.typ)
1512 }
1513
1514 func (c *reflectZeroConstraint) solve(a *analysis, delta *nodeset) {
1515         changed := false
1516         for _, x := range delta.AppendTo(a.deltaSpace) {
1517                 typObj := nodeid(x)
1518                 T := a.rtypeTaggedValue(typObj)
1519
1520                 // TODO(adonovan): if T is an interface type, we need
1521                 // to create an indirect tagged object containing
1522                 // new(T).  To avoid updates of such shared values,
1523                 // we'll need another flag on indirect tagged objects
1524                 // that marks whether they are addressable or
1525                 // readonly, just like the reflect package does.
1526
1527                 // memoize using a.reflectZeros[T]
1528                 var id nodeid
1529                 if z := a.reflectZeros.At(T); false && z != nil {
1530                         id = z.(nodeid)
1531                 } else {
1532                         id = a.makeTagged(T, c.cgn, nil)
1533                         a.reflectZeros.Set(T, id)
1534                 }
1535                 if a.addLabel(c.result, id) {
1536                         changed = true
1537                 }
1538         }
1539         if changed {
1540                 a.addWork(c.result)
1541         }
1542 }
1543
1544 func ext۰reflect۰Zero(a *analysis, cgn *cgnode) {
1545         a.addConstraint(&reflectZeroConstraint{
1546                 cgn:    cgn,
1547                 typ:    a.funcParams(cgn.obj),
1548                 result: a.funcResults(cgn.obj),
1549         })
1550 }
1551
1552 // -------------------- (*reflect.rtype) methods --------------------
1553
1554 // ---------- func (*rtype) Elem() Type ----------
1555
1556 // result = Elem(t)
1557 type rtypeElemConstraint struct {
1558         cgn    *cgnode
1559         t      nodeid // (ptr)
1560         result nodeid // (indirect)
1561 }
1562
1563 func (c *rtypeElemConstraint) ptr() nodeid { return c.t }
1564 func (c *rtypeElemConstraint) presolve(h *hvn) {
1565         h.markIndirect(onodeid(c.result), "rtypeElem.result")
1566 }
1567 func (c *rtypeElemConstraint) renumber(mapping []nodeid) {
1568         c.t = mapping[c.t]
1569         c.result = mapping[c.result]
1570 }
1571
1572 func (c *rtypeElemConstraint) String() string {
1573         return fmt.Sprintf("n%d = (*reflect.rtype).Elem(n%d)", c.result, c.t)
1574 }
1575
1576 func (c *rtypeElemConstraint) solve(a *analysis, delta *nodeset) {
1577         // Implemented by *types.{Map,Chan,Array,Slice,Pointer}.
1578         type hasElem interface {
1579                 Elem() types.Type
1580         }
1581         changed := false
1582         for _, x := range delta.AppendTo(a.deltaSpace) {
1583                 tObj := nodeid(x)
1584                 T := a.nodes[tObj].obj.data.(types.Type)
1585                 if tHasElem, ok := T.Underlying().(hasElem); ok {
1586                         if a.addLabel(c.result, a.makeRtype(tHasElem.Elem())) {
1587                                 changed = true
1588                         }
1589                 }
1590         }
1591         if changed {
1592                 a.addWork(c.result)
1593         }
1594 }
1595
1596 func ext۰reflect۰rtype۰Elem(a *analysis, cgn *cgnode) {
1597         a.addConstraint(&rtypeElemConstraint{
1598                 cgn:    cgn,
1599                 t:      a.funcParams(cgn.obj),
1600                 result: a.funcResults(cgn.obj),
1601         })
1602 }
1603
1604 // ---------- func (*rtype) Field(int) StructField ----------
1605 // ---------- func (*rtype) FieldByName(string) (StructField, bool) ----------
1606
1607 // result = FieldByName(t, name)
1608 // result = Field(t, _)
1609 type rtypeFieldByNameConstraint struct {
1610         cgn    *cgnode
1611         name   string // name of field; "" for unknown
1612         t      nodeid // (ptr)
1613         result nodeid // (indirect)
1614 }
1615
1616 func (c *rtypeFieldByNameConstraint) ptr() nodeid { return c.t }
1617 func (c *rtypeFieldByNameConstraint) presolve(h *hvn) {
1618         h.markIndirect(onodeid(c.result+3), "rtypeFieldByName.result.Type")
1619 }
1620 func (c *rtypeFieldByNameConstraint) renumber(mapping []nodeid) {
1621         c.t = mapping[c.t]
1622         c.result = mapping[c.result]
1623 }
1624
1625 func (c *rtypeFieldByNameConstraint) String() string {
1626         return fmt.Sprintf("n%d = (*reflect.rtype).FieldByName(n%d, %q)", c.result, c.t, c.name)
1627 }
1628
1629 func (c *rtypeFieldByNameConstraint) solve(a *analysis, delta *nodeset) {
1630         // type StructField struct {
1631         // 0    __identity__
1632         // 1    Name      string
1633         // 2    PkgPath   string
1634         // 3    Type      Type
1635         // 4    Tag       StructTag
1636         // 5    Offset    uintptr
1637         // 6    Index     []int
1638         // 7    Anonymous bool
1639         // }
1640
1641         for _, x := range delta.AppendTo(a.deltaSpace) {
1642                 tObj := nodeid(x)
1643                 T := a.nodes[tObj].obj.data.(types.Type)
1644                 tStruct, ok := T.Underlying().(*types.Struct)
1645                 if !ok {
1646                         continue // not a struct type
1647                 }
1648
1649                 n := tStruct.NumFields()
1650                 for i := 0; i < n; i++ {
1651                         f := tStruct.Field(i)
1652                         if c.name == "" || c.name == f.Name() {
1653
1654                                 // a.offsetOf(Type) is 3.
1655                                 if id := c.result + 3; a.addLabel(id, a.makeRtype(f.Type())) {
1656                                         a.addWork(id)
1657                                 }
1658                                 // TODO(adonovan): StructField.Index should be non-nil.
1659                         }
1660                 }
1661         }
1662 }
1663
1664 func ext۰reflect۰rtype۰FieldByName(a *analysis, cgn *cgnode) {
1665         // If we have access to the callsite,
1666         // and the argument is a string constant,
1667         // return only that field.
1668         var name string
1669         if site := cgn.callersite; site != nil {
1670                 if c, ok := site.instr.Common().Args[0].(*ssa.Const); ok {
1671                         name = constant.StringVal(c.Value)
1672                 }
1673         }
1674
1675         a.addConstraint(&rtypeFieldByNameConstraint{
1676                 cgn:    cgn,
1677                 name:   name,
1678                 t:      a.funcParams(cgn.obj),
1679                 result: a.funcResults(cgn.obj),
1680         })
1681 }
1682
1683 func ext۰reflect۰rtype۰Field(a *analysis, cgn *cgnode) {
1684         // No-one ever calls Field with a constant argument,
1685         // so we don't specialize that case.
1686         a.addConstraint(&rtypeFieldByNameConstraint{
1687                 cgn:    cgn,
1688                 t:      a.funcParams(cgn.obj),
1689                 result: a.funcResults(cgn.obj),
1690         })
1691 }
1692
1693 func ext۰reflect۰rtype۰FieldByIndex(a *analysis, cgn *cgnode)    {} // TODO(adonovan)
1694 func ext۰reflect۰rtype۰FieldByNameFunc(a *analysis, cgn *cgnode) {} // TODO(adonovan)
1695
1696 // ---------- func (*rtype) In/Out(i int) Type ----------
1697
1698 // result = In/Out(t, i)
1699 type rtypeInOutConstraint struct {
1700         cgn    *cgnode
1701         t      nodeid // (ptr)
1702         result nodeid // (indirect)
1703         out    bool
1704         i      int // -ve if not a constant
1705 }
1706
1707 func (c *rtypeInOutConstraint) ptr() nodeid { return c.t }
1708 func (c *rtypeInOutConstraint) presolve(h *hvn) {
1709         h.markIndirect(onodeid(c.result), "rtypeInOut.result")
1710 }
1711 func (c *rtypeInOutConstraint) renumber(mapping []nodeid) {
1712         c.t = mapping[c.t]
1713         c.result = mapping[c.result]
1714 }
1715
1716 func (c *rtypeInOutConstraint) String() string {
1717         return fmt.Sprintf("n%d = (*reflect.rtype).InOut(n%d, %d)", c.result, c.t, c.i)
1718 }
1719
1720 func (c *rtypeInOutConstraint) solve(a *analysis, delta *nodeset) {
1721         changed := false
1722         for _, x := range delta.AppendTo(a.deltaSpace) {
1723                 tObj := nodeid(x)
1724                 T := a.nodes[tObj].obj.data.(types.Type)
1725                 sig, ok := T.Underlying().(*types.Signature)
1726                 if !ok {
1727                         continue // not a func type
1728                 }
1729
1730                 tuple := sig.Params()
1731                 if c.out {
1732                         tuple = sig.Results()
1733                 }
1734                 for i, n := 0, tuple.Len(); i < n; i++ {
1735                         if c.i < 0 || c.i == i {
1736                                 if a.addLabel(c.result, a.makeRtype(tuple.At(i).Type())) {
1737                                         changed = true
1738                                 }
1739                         }
1740                 }
1741         }
1742         if changed {
1743                 a.addWork(c.result)
1744         }
1745 }
1746
1747 func ext۰reflect۰rtype۰InOut(a *analysis, cgn *cgnode, out bool) {
1748         // If we have access to the callsite,
1749         // and the argument is an int constant,
1750         // return only that parameter.
1751         index := -1
1752         if site := cgn.callersite; site != nil {
1753                 if c, ok := site.instr.Common().Args[0].(*ssa.Const); ok {
1754                         v, _ := constant.Int64Val(c.Value)
1755                         index = int(v)
1756                 }
1757         }
1758         a.addConstraint(&rtypeInOutConstraint{
1759                 cgn:    cgn,
1760                 t:      a.funcParams(cgn.obj),
1761                 result: a.funcResults(cgn.obj),
1762                 out:    out,
1763                 i:      index,
1764         })
1765 }
1766
1767 func ext۰reflect۰rtype۰In(a *analysis, cgn *cgnode) {
1768         ext۰reflect۰rtype۰InOut(a, cgn, false)
1769 }
1770
1771 func ext۰reflect۰rtype۰Out(a *analysis, cgn *cgnode) {
1772         ext۰reflect۰rtype۰InOut(a, cgn, true)
1773 }
1774
1775 // ---------- func (*rtype) Key() Type ----------
1776
1777 // result = Key(t)
1778 type rtypeKeyConstraint struct {
1779         cgn    *cgnode
1780         t      nodeid // (ptr)
1781         result nodeid // (indirect)
1782 }
1783
1784 func (c *rtypeKeyConstraint) ptr() nodeid { return c.t }
1785 func (c *rtypeKeyConstraint) presolve(h *hvn) {
1786         h.markIndirect(onodeid(c.result), "rtypeKey.result")
1787 }
1788 func (c *rtypeKeyConstraint) renumber(mapping []nodeid) {
1789         c.t = mapping[c.t]
1790         c.result = mapping[c.result]
1791 }
1792
1793 func (c *rtypeKeyConstraint) String() string {
1794         return fmt.Sprintf("n%d = (*reflect.rtype).Key(n%d)", c.result, c.t)
1795 }
1796
1797 func (c *rtypeKeyConstraint) solve(a *analysis, delta *nodeset) {
1798         changed := false
1799         for _, x := range delta.AppendTo(a.deltaSpace) {
1800                 tObj := nodeid(x)
1801                 T := a.nodes[tObj].obj.data.(types.Type)
1802                 if tMap, ok := T.Underlying().(*types.Map); ok {
1803                         if a.addLabel(c.result, a.makeRtype(tMap.Key())) {
1804                                 changed = true
1805                         }
1806                 }
1807         }
1808         if changed {
1809                 a.addWork(c.result)
1810         }
1811 }
1812
1813 func ext۰reflect۰rtype۰Key(a *analysis, cgn *cgnode) {
1814         a.addConstraint(&rtypeKeyConstraint{
1815                 cgn:    cgn,
1816                 t:      a.funcParams(cgn.obj),
1817                 result: a.funcResults(cgn.obj),
1818         })
1819 }
1820
1821 // ---------- func (*rtype) Method(int) (Method, bool) ----------
1822 // ---------- func (*rtype) MethodByName(string) (Method, bool) ----------
1823
1824 // result = MethodByName(t, name)
1825 // result = Method(t, _)
1826 type rtypeMethodByNameConstraint struct {
1827         cgn    *cgnode
1828         name   string // name of method; "" for unknown
1829         t      nodeid // (ptr)
1830         result nodeid // (indirect)
1831 }
1832
1833 func (c *rtypeMethodByNameConstraint) ptr() nodeid { return c.t }
1834 func (c *rtypeMethodByNameConstraint) presolve(h *hvn) {
1835         h.markIndirect(onodeid(c.result+3), "rtypeMethodByName.result.Type")
1836         h.markIndirect(onodeid(c.result+4), "rtypeMethodByName.result.Func")
1837 }
1838 func (c *rtypeMethodByNameConstraint) renumber(mapping []nodeid) {
1839         c.t = mapping[c.t]
1840         c.result = mapping[c.result]
1841 }
1842
1843 func (c *rtypeMethodByNameConstraint) String() string {
1844         return fmt.Sprintf("n%d = (*reflect.rtype).MethodByName(n%d, %q)", c.result, c.t, c.name)
1845 }
1846
1847 // changeRecv returns sig with Recv prepended to Params().
1848 func changeRecv(sig *types.Signature) *types.Signature {
1849         params := sig.Params()
1850         n := params.Len()
1851         p2 := make([]*types.Var, n+1)
1852         p2[0] = sig.Recv()
1853         for i := 0; i < n; i++ {
1854                 p2[i+1] = params.At(i)
1855         }
1856         return types.NewSignature(nil, types.NewTuple(p2...), sig.Results(), sig.Variadic())
1857 }
1858
1859 func (c *rtypeMethodByNameConstraint) solve(a *analysis, delta *nodeset) {
1860         for _, x := range delta.AppendTo(a.deltaSpace) {
1861                 tObj := nodeid(x)
1862                 T := a.nodes[tObj].obj.data.(types.Type)
1863
1864                 isIface := isInterface(T)
1865
1866                 // We don't use Lookup(c.name) when c.name != "" to avoid
1867                 // ambiguity: >1 unexported methods could match.
1868                 mset := a.prog.MethodSets.MethodSet(T)
1869                 for i, n := 0, mset.Len(); i < n; i++ {
1870                         sel := mset.At(i)
1871                         if c.name == "" || c.name == sel.Obj().Name() {
1872                                 // type Method struct {
1873                                 // 0     __identity__
1874                                 // 1    Name    string
1875                                 // 2    PkgPath string
1876                                 // 3    Type    Type
1877                                 // 4    Func    Value
1878                                 // 5    Index   int
1879                                 // }
1880
1881                                 var sig *types.Signature
1882                                 var fn *ssa.Function
1883                                 if isIface {
1884                                         sig = sel.Type().(*types.Signature)
1885                                 } else {
1886                                         fn = a.prog.MethodValue(sel)
1887                                         // move receiver to params[0]
1888                                         sig = changeRecv(fn.Signature)
1889                                 }
1890
1891                                 // a.offsetOf(Type) is 3.
1892                                 if id := c.result + 3; a.addLabel(id, a.makeRtype(sig)) {
1893                                         a.addWork(id)
1894                                 }
1895                                 if fn != nil {
1896                                         // a.offsetOf(Func) is 4.
1897                                         if id := c.result + 4; a.addLabel(id, a.objectNode(nil, fn)) {
1898                                                 a.addWork(id)
1899                                         }
1900                                 }
1901                         }
1902                 }
1903         }
1904 }
1905
1906 func ext۰reflect۰rtype۰MethodByName(a *analysis, cgn *cgnode) {
1907         // If we have access to the callsite,
1908         // and the argument is a string constant,
1909         // return only that method.
1910         var name string
1911         if site := cgn.callersite; site != nil {
1912                 if c, ok := site.instr.Common().Args[0].(*ssa.Const); ok {
1913                         name = constant.StringVal(c.Value)
1914                 }
1915         }
1916
1917         a.addConstraint(&rtypeMethodByNameConstraint{
1918                 cgn:    cgn,
1919                 name:   name,
1920                 t:      a.funcParams(cgn.obj),
1921                 result: a.funcResults(cgn.obj),
1922         })
1923 }
1924
1925 func ext۰reflect۰rtype۰Method(a *analysis, cgn *cgnode) {
1926         // No-one ever calls Method with a constant argument,
1927         // so we don't specialize that case.
1928         a.addConstraint(&rtypeMethodByNameConstraint{
1929                 cgn:    cgn,
1930                 t:      a.funcParams(cgn.obj),
1931                 result: a.funcResults(cgn.obj),
1932         })
1933 }
1934
1935 // typeHeight returns the "height" of the type, which is roughly
1936 // speaking the number of chan, map, pointer and slice type constructors
1937 // at the root of T; these are the four type kinds that can be created
1938 // via reflection.  Chan and map constructors are counted as double the
1939 // height of slice and pointer constructors since they are less often
1940 // deeply nested.
1941 //
1942 // The solver rules for type constructors must somehow bound the set of
1943 // types they create to ensure termination of the algorithm in cases
1944 // where the output of a type constructor flows to its input, e.g.
1945 //
1946 //      func f(t reflect.Type) {
1947 //              f(reflect.PtrTo(t))
1948 //      }
1949 //
1950 // It does this by limiting the type height to k, but this still leaves
1951 // a potentially exponential (4^k) number of of types that may be
1952 // enumerated in pathological cases.
1953 //
1954 func typeHeight(T types.Type) int {
1955         switch T := T.(type) {
1956         case *types.Chan:
1957                 return 2 + typeHeight(T.Elem())
1958         case *types.Map:
1959                 k := typeHeight(T.Key())
1960                 v := typeHeight(T.Elem())
1961                 if v > k {
1962                         k = v // max(k, v)
1963                 }
1964                 return 2 + k
1965         case *types.Slice:
1966                 return 1 + typeHeight(T.Elem())
1967         case *types.Pointer:
1968                 return 1 + typeHeight(T.Elem())
1969         }
1970         return 0
1971 }
1972
1973 func typeTooHigh(T types.Type) bool {
1974         return typeHeight(T) > 3
1975 }