.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/pointer/solve.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 defines a naive Andersen-style solver for the inclusion
   8 // constraint system.
   9
  10 import (
  11         "fmt"
  12         "go/types"
  13 )
  14
  15 type solverState struct {
  16         complex []constraint // complex constraints attached to this node
  17         copyTo  nodeset      // simple copy constraint edges
  18         pts     nodeset      // points-to set of this node
  19         prevPTS nodeset      // pts(n) in previous iteration (for difference propagation)
  20 }
  21
  22 func (a *analysis) solve() {
  23         start("Solving")
  24         if a.log != nil {
  25                 fmt.Fprintf(a.log, "\n\n==== Solving constraints\n\n")
  26         }
  27
  28         // Solver main loop.
  29         var delta nodeset
  30         for {
  31                 // Add new constraints to the graph:
  32                 // static constraints from SSA on round 1,
  33                 // dynamic constraints from reflection thereafter.
  34                 a.processNewConstraints()
  35
  36                 var x int
  37                 if !a.work.TakeMin(&x) {
  38                         break // empty
  39                 }
  40                 id := nodeid(x)
  41                 if a.log != nil {
  42                         fmt.Fprintf(a.log, "\tnode n%d\n", id)
  43                 }
  44
  45                 n := a.nodes[id]
  46
  47                 // Difference propagation.
  48                 delta.Difference(&n.solve.pts.Sparse, &n.solve.prevPTS.Sparse)
  49                 if delta.IsEmpty() {
  50                         continue
  51                 }
  52                 if a.log != nil {
  53                         fmt.Fprintf(a.log, "\t\tpts(n%d : %s) = %s + %s\n",
  54                                 id, n.typ, &delta, &n.solve.prevPTS)
  55                 }
  56                 n.solve.prevPTS.Copy(&n.solve.pts.Sparse)
  57
  58                 // Apply all resolution rules attached to n.
  59                 a.solveConstraints(n, &delta)
  60
  61                 if a.log != nil {
  62                         fmt.Fprintf(a.log, "\t\tpts(n%d) = %s\n", id, &n.solve.pts)
  63                 }
  64         }
  65
  66         if !a.nodes[0].solve.pts.IsEmpty() {
  67                 panic(fmt.Sprintf("pts(0) is nonempty: %s", &a.nodes[0].solve.pts))
  68         }
  69
  70         // Release working state (but keep final PTS).
  71         for _, n := range a.nodes {
  72                 n.solve.complex = nil
  73                 n.solve.copyTo.Clear()
  74                 n.solve.prevPTS.Clear()
  75         }
  76
  77         if a.log != nil {
  78                 fmt.Fprintf(a.log, "Solver done\n")
  79
  80                 // Dump solution.
  81                 for i, n := range a.nodes {
  82                         if !n.solve.pts.IsEmpty() {
  83                                 fmt.Fprintf(a.log, "pts(n%d) = %s : %s\n", i, &n.solve.pts, n.typ)
  84                         }
  85                 }
  86         }
  87         stop("Solving")
  88 }
  89
  90 // processNewConstraints takes the new constraints from a.constraints
  91 // and adds them to the graph, ensuring
  92 // that new constraints are applied to pre-existing labels and
  93 // that pre-existing constraints are applied to new labels.
  94 //
  95 func (a *analysis) processNewConstraints() {
  96         // Take the slice of new constraints.
  97         // (May grow during call to solveConstraints.)
  98         constraints := a.constraints
  99         a.constraints = nil
 100
 101         // Initialize points-to sets from addr-of (base) constraints.
 102         for _, c := range constraints {
 103                 if c, ok := c.(*addrConstraint); ok {
 104                         dst := a.nodes[c.dst]
 105                         dst.solve.pts.add(c.src)
 106
 107                         // Populate the worklist with nodes that point to
 108                         // something initially (due to addrConstraints) and
 109                         // have other constraints attached.
 110                         // (A no-op in round 1.)
 111                         if !dst.solve.copyTo.IsEmpty() || len(dst.solve.complex) > 0 {
 112                                 a.addWork(c.dst)
 113                         }
 114                 }
 115         }
 116
 117         // Attach simple (copy) and complex constraints to nodes.
 118         var stale nodeset
 119         for _, c := range constraints {
 120                 var id nodeid
 121                 switch c := c.(type) {
 122                 case *addrConstraint:
 123                         // base constraints handled in previous loop
 124                         continue
 125                 case *copyConstraint:
 126                         // simple (copy) constraint
 127                         id = c.src
 128                         a.nodes[id].solve.copyTo.add(c.dst)
 129                 default:
 130                         // complex constraint
 131                         id = c.ptr()
 132                         solve := a.nodes[id].solve
 133                         solve.complex = append(solve.complex, c)
 134                 }
 135
 136                 if n := a.nodes[id]; !n.solve.pts.IsEmpty() {
 137                         if !n.solve.prevPTS.IsEmpty() {
 138                                 stale.add(id)
 139                         }
 140                         a.addWork(id)
 141                 }
 142         }
 143         // Apply new constraints to pre-existing PTS labels.
 144         var space [50]int
 145         for _, id := range stale.AppendTo(space[:0]) {
 146                 n := a.nodes[nodeid(id)]
 147                 a.solveConstraints(n, &n.solve.prevPTS)
 148         }
 149 }
 150
 151 // solveConstraints applies each resolution rule attached to node n to
 152 // the set of labels delta.  It may generate new constraints in
 153 // a.constraints.
 154 //
 155 func (a *analysis) solveConstraints(n *node, delta *nodeset) {
 156         if delta.IsEmpty() {
 157                 return
 158         }
 159
 160         // Process complex constraints dependent on n.
 161         for _, c := range n.solve.complex {
 162                 if a.log != nil {
 163                         fmt.Fprintf(a.log, "\t\tconstraint %s\n", c)
 164                 }
 165                 c.solve(a, delta)
 166         }
 167
 168         // Process copy constraints.
 169         var copySeen nodeset
 170         for _, x := range n.solve.copyTo.AppendTo(a.deltaSpace) {
 171                 mid := nodeid(x)
 172                 if copySeen.add(mid) {
 173                         if a.nodes[mid].solve.pts.addAll(delta) {
 174                                 a.addWork(mid)
 175                         }
 176                 }
 177         }
 178 }
 179
 180 // addLabel adds label to the points-to set of ptr and reports whether the set grew.
 181 func (a *analysis) addLabel(ptr, label nodeid) bool {
 182         b := a.nodes[ptr].solve.pts.add(label)
 183         if b && a.log != nil {
 184                 fmt.Fprintf(a.log, "\t\tpts(n%d) += n%d\n", ptr, label)
 185         }
 186         return b
 187 }
 188
 189 func (a *analysis) addWork(id nodeid) {
 190         a.work.Insert(int(id))
 191         if a.log != nil {
 192                 fmt.Fprintf(a.log, "\t\twork: n%d\n", id)
 193         }
 194 }
 195
 196 // onlineCopy adds a copy edge.  It is called online, i.e. during
 197 // solving, so it adds edges and pts members directly rather than by
 198 // instantiating a 'constraint'.
 199 //
 200 // The size of the copy is implicitly 1.
 201 // It returns true if pts(dst) changed.
 202 //
 203 func (a *analysis) onlineCopy(dst, src nodeid) bool {
 204         if dst != src {
 205                 if nsrc := a.nodes[src]; nsrc.solve.copyTo.add(dst) {
 206                         if a.log != nil {
 207                                 fmt.Fprintf(a.log, "\t\t\tdynamic copy n%d <- n%d\n", dst, src)
 208                         }
 209                         // TODO(adonovan): most calls to onlineCopy
 210                         // are followed by addWork, possibly batched
 211                         // via a 'changed' flag; see if there's a
 212                         // noticeable penalty to calling addWork here.
 213                         return a.nodes[dst].solve.pts.addAll(&nsrc.solve.pts)
 214                 }
 215         }
 216         return false
 217 }
 218
 219 // Returns sizeof.
 220 // Implicitly adds nodes to worklist.
 221 //
 222 // TODO(adonovan): now that we support a.copy() during solving, we
 223 // could eliminate onlineCopyN, but it's much slower.  Investigate.
 224 //
 225 func (a *analysis) onlineCopyN(dst, src nodeid, sizeof uint32) uint32 {
 226         for i := uint32(0); i < sizeof; i++ {
 227                 if a.onlineCopy(dst, src) {
 228                         a.addWork(dst)
 229                 }
 230                 src++
 231                 dst++
 232         }
 233         return sizeof
 234 }
 235
 236 func (c *loadConstraint) solve(a *analysis, delta *nodeset) {
 237         var changed bool
 238         for _, x := range delta.AppendTo(a.deltaSpace) {
 239                 k := nodeid(x)
 240                 koff := k + nodeid(c.offset)
 241                 if a.onlineCopy(c.dst, koff) {
 242                         changed = true
 243                 }
 244         }
 245         if changed {
 246                 a.addWork(c.dst)
 247         }
 248 }
 249
 250 func (c *storeConstraint) solve(a *analysis, delta *nodeset) {
 251         for _, x := range delta.AppendTo(a.deltaSpace) {
 252                 k := nodeid(x)
 253                 koff := k + nodeid(c.offset)
 254                 if a.onlineCopy(koff, c.src) {
 255                         a.addWork(koff)
 256                 }
 257         }
 258 }
 259
 260 func (c *offsetAddrConstraint) solve(a *analysis, delta *nodeset) {
 261         dst := a.nodes[c.dst]
 262         for _, x := range delta.AppendTo(a.deltaSpace) {
 263                 k := nodeid(x)
 264                 if dst.solve.pts.add(k + nodeid(c.offset)) {
 265                         a.addWork(c.dst)
 266                 }
 267         }
 268 }
 269
 270 func (c *typeFilterConstraint) solve(a *analysis, delta *nodeset) {
 271         for _, x := range delta.AppendTo(a.deltaSpace) {
 272                 ifaceObj := nodeid(x)
 273                 tDyn, _, indirect := a.taggedValue(ifaceObj)
 274                 if indirect {
 275                         // TODO(adonovan): we'll need to implement this
 276                         // when we start creating indirect tagged objects.
 277                         panic("indirect tagged object")
 278                 }
 279
 280                 if types.AssignableTo(tDyn, c.typ) {
 281                         if a.addLabel(c.dst, ifaceObj) {
 282                                 a.addWork(c.dst)
 283                         }
 284                 }
 285         }
 286 }
 287
 288 func (c *untagConstraint) solve(a *analysis, delta *nodeset) {
 289         predicate := types.AssignableTo
 290         if c.exact {
 291                 predicate = types.Identical
 292         }
 293         for _, x := range delta.AppendTo(a.deltaSpace) {
 294                 ifaceObj := nodeid(x)
 295                 tDyn, v, indirect := a.taggedValue(ifaceObj)
 296                 if indirect {
 297                         // TODO(adonovan): we'll need to implement this
 298                         // when we start creating indirect tagged objects.
 299                         panic("indirect tagged object")
 300                 }
 301
 302                 if predicate(tDyn, c.typ) {
 303                         // Copy payload sans tag to dst.
 304                         //
 305                         // TODO(adonovan): opt: if tDyn is
 306                         // nonpointerlike we can skip this entire
 307                         // constraint, perhaps.  We only care about
 308                         // pointers among the fields.
 309                         a.onlineCopyN(c.dst, v, a.sizeof(tDyn))
 310                 }
 311         }
 312 }
 313
 314 func (c *invokeConstraint) solve(a *analysis, delta *nodeset) {
 315         for _, x := range delta.AppendTo(a.deltaSpace) {
 316                 ifaceObj := nodeid(x)
 317                 tDyn, v, indirect := a.taggedValue(ifaceObj)
 318                 if indirect {
 319                         // TODO(adonovan): we may need to implement this if
 320                         // we ever apply invokeConstraints to reflect.Value PTSs,
 321                         // e.g. for (reflect.Value).Call.
 322                         panic("indirect tagged object")
 323                 }
 324
 325                 // Look up the concrete method.
 326                 fn := a.prog.LookupMethod(tDyn, c.method.Pkg(), c.method.Name())
 327                 if fn == nil {
 328                         panic(fmt.Sprintf("n%d: no ssa.Function for %s", c.iface, c.method))
 329                 }
 330                 sig := fn.Signature
 331
 332                 fnObj := a.globalobj[fn] // dynamic calls use shared contour
 333                 if fnObj == 0 {
 334                         // a.objectNode(fn) was not called during gen phase.
 335                         panic(fmt.Sprintf("a.globalobj[%s]==nil", fn))
 336                 }
 337
 338                 // Make callsite's fn variable point to identity of
 339                 // concrete method.  (There's no need to add it to
 340                 // worklist since it never has attached constraints.)
 341                 a.addLabel(c.params, fnObj)
 342
 343                 // Extract value and connect to method's receiver.
 344                 // Copy payload to method's receiver param (arg0).
 345                 arg0 := a.funcParams(fnObj)
 346                 recvSize := a.sizeof(sig.Recv().Type())
 347                 a.onlineCopyN(arg0, v, recvSize)
 348
 349                 src := c.params + 1 // skip past identity
 350                 dst := arg0 + nodeid(recvSize)
 351
 352                 // Copy caller's argument block to method formal parameters.
 353                 paramsSize := a.sizeof(sig.Params())
 354                 a.onlineCopyN(dst, src, paramsSize)
 355                 src += nodeid(paramsSize)
 356                 dst += nodeid(paramsSize)
 357
 358                 // Copy method results to caller's result block.
 359                 resultsSize := a.sizeof(sig.Results())
 360                 a.onlineCopyN(src, dst, resultsSize)
 361         }
 362 }
 363
 364 func (c *addrConstraint) solve(a *analysis, delta *nodeset) {
 365         panic("addr is not a complex constraint")
 366 }
 367
 368 func (c *copyConstraint) solve(a *analysis, delta *nodeset) {
 369         panic("copy is not a complex constraint")
 370 }