X-Git-Url: https://git.josue.xyz/?a=blobdiff_plain;f=.config%2Fcoc%2Fextensions%2Fcoc-go-data%2Ftools%2Fpkg%2Fmod%2Fgolang.org%2Fx%2Ftools%40v0.0.0-20201028153306-37f0764111ff%2Fgo%2Fpointer%2Fsolve.go;fp=.config%2Fcoc%2Fextensions%2Fcoc-go-data%2Ftools%2Fpkg%2Fmod%2Fgolang.org%2Fx%2Ftools%40v0.0.0-20201028153306-37f0764111ff%2Fgo%2Fpointer%2Fsolve.go;h=0fdd098b0127ab600f5504343aef87f788e99933;hb=4d07c77cf4d78cab8639e13ddc3c22495e585b0b;hp=0000000000000000000000000000000000000000;hpb=b3950616b54221c40a7dab9099bda675007e5b6e;p=dotfiles%2F.git

diff --git a/.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/pointer/solve.go b/.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/pointer/solve.go
new file mode 100644
index 00000000..0fdd098b
--- /dev/null
+++ b/.config/coc/extensions/coc-go-data/tools/pkg/mod/golang.org/x/tools@v0.0.0-20201028153306-37f0764111ff/go/pointer/solve.go
@@ -0,0 +1,370 @@
+// Copyright 2013 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package pointer
+
+// This file defines a naive Andersen-style solver for the inclusion
+// constraint system.
+
+import (
+	"fmt"
+	"go/types"
+)
+
+type solverState struct {
+	complex []constraint // complex constraints attached to this node
+	copyTo  nodeset      // simple copy constraint edges
+	pts     nodeset      // points-to set of this node
+	prevPTS nodeset      // pts(n) in previous iteration (for difference propagation)
+}
+
+func (a *analysis) solve() {
+	start("Solving")
+	if a.log != nil {
+		fmt.Fprintf(a.log, "\n\n==== Solving constraints\n\n")
+	}
+
+	// Solver main loop.
+	var delta nodeset
+	for {
+		// Add new constraints to the graph:
+		// static constraints from SSA on round 1,
+		// dynamic constraints from reflection thereafter.
+		a.processNewConstraints()
+
+		var x int
+		if !a.work.TakeMin(&x) {
+			break // empty
+		}
+		id := nodeid(x)
+		if a.log != nil {
+			fmt.Fprintf(a.log, "\tnode n%d\n", id)
+		}
+
+		n := a.nodes[id]
+
+		// Difference propagation.
+		delta.Difference(&n.solve.pts.Sparse, &n.solve.prevPTS.Sparse)
+		if delta.IsEmpty() {
+			continue
+		}
+		if a.log != nil {
+			fmt.Fprintf(a.log, "\t\tpts(n%d : %s) = %s + %s\n",
+				id, n.typ, &delta, &n.solve.prevPTS)
+		}
+		n.solve.prevPTS.Copy(&n.solve.pts.Sparse)
+
+		// Apply all resolution rules attached to n.
+		a.solveConstraints(n, &delta)
+
+		if a.log != nil {
+			fmt.Fprintf(a.log, "\t\tpts(n%d) = %s\n", id, &n.solve.pts)
+		}
+	}
+
+	if !a.nodes[0].solve.pts.IsEmpty() {
+		panic(fmt.Sprintf("pts(0) is nonempty: %s", &a.nodes[0].solve.pts))
+	}
+
+	// Release working state (but keep final PTS).
+	for _, n := range a.nodes {
+		n.solve.complex = nil
+		n.solve.copyTo.Clear()
+		n.solve.prevPTS.Clear()
+	}
+
+	if a.log != nil {
+		fmt.Fprintf(a.log, "Solver done\n")
+
+		// Dump solution.
+		for i, n := range a.nodes {
+			if !n.solve.pts.IsEmpty() {
+				fmt.Fprintf(a.log, "pts(n%d) = %s : %s\n", i, &n.solve.pts, n.typ)
+			}
+		}
+	}
+	stop("Solving")
+}
+
+// processNewConstraints takes the new constraints from a.constraints
+// and adds them to the graph, ensuring
+// that new constraints are applied to pre-existing labels and
+// that pre-existing constraints are applied to new labels.
+//
+func (a *analysis) processNewConstraints() {
+	// Take the slice of new constraints.
+	// (May grow during call to solveConstraints.)
+	constraints := a.constraints
+	a.constraints = nil
+
+	// Initialize points-to sets from addr-of (base) constraints.
+	for _, c := range constraints {
+		if c, ok := c.(*addrConstraint); ok {
+			dst := a.nodes[c.dst]
+			dst.solve.pts.add(c.src)
+
+			// Populate the worklist with nodes that point to
+			// something initially (due to addrConstraints) and
+			// have other constraints attached.
+			// (A no-op in round 1.)
+			if !dst.solve.copyTo.IsEmpty() || len(dst.solve.complex) > 0 {
+				a.addWork(c.dst)
+			}
+		}
+	}
+
+	// Attach simple (copy) and complex constraints to nodes.
+	var stale nodeset
+	for _, c := range constraints {
+		var id nodeid
+		switch c := c.(type) {
+		case *addrConstraint:
+			// base constraints handled in previous loop
+			continue
+		case *copyConstraint:
+			// simple (copy) constraint
+			id = c.src
+			a.nodes[id].solve.copyTo.add(c.dst)
+		default:
+			// complex constraint
+			id = c.ptr()
+			solve := a.nodes[id].solve
+			solve.complex = append(solve.complex, c)
+		}
+
+		if n := a.nodes[id]; !n.solve.pts.IsEmpty() {
+			if !n.solve.prevPTS.IsEmpty() {
+				stale.add(id)
+			}
+			a.addWork(id)
+		}
+	}
+	// Apply new constraints to pre-existing PTS labels.
+	var space [50]int
+	for _, id := range stale.AppendTo(space[:0]) {
+		n := a.nodes[nodeid(id)]
+		a.solveConstraints(n, &n.solve.prevPTS)
+	}
+}
+
+// solveConstraints applies each resolution rule attached to node n to
+// the set of labels delta.  It may generate new constraints in
+// a.constraints.
+//
+func (a *analysis) solveConstraints(n *node, delta *nodeset) {
+	if delta.IsEmpty() {
+		return
+	}
+
+	// Process complex constraints dependent on n.
+	for _, c := range n.solve.complex {
+		if a.log != nil {
+			fmt.Fprintf(a.log, "\t\tconstraint %s\n", c)
+		}
+		c.solve(a, delta)
+	}
+
+	// Process copy constraints.
+	var copySeen nodeset
+	for _, x := range n.solve.copyTo.AppendTo(a.deltaSpace) {
+		mid := nodeid(x)
+		if copySeen.add(mid) {
+			if a.nodes[mid].solve.pts.addAll(delta) {
+				a.addWork(mid)
+			}
+		}
+	}
+}
+
+// addLabel adds label to the points-to set of ptr and reports whether the set grew.
+func (a *analysis) addLabel(ptr, label nodeid) bool {
+	b := a.nodes[ptr].solve.pts.add(label)
+	if b && a.log != nil {
+		fmt.Fprintf(a.log, "\t\tpts(n%d) += n%d\n", ptr, label)
+	}
+	return b
+}
+
+func (a *analysis) addWork(id nodeid) {
+	a.work.Insert(int(id))
+	if a.log != nil {
+		fmt.Fprintf(a.log, "\t\twork: n%d\n", id)
+	}
+}
+
+// onlineCopy adds a copy edge.  It is called online, i.e. during
+// solving, so it adds edges and pts members directly rather than by
+// instantiating a 'constraint'.
+//
+// The size of the copy is implicitly 1.
+// It returns true if pts(dst) changed.
+//
+func (a *analysis) onlineCopy(dst, src nodeid) bool {
+	if dst != src {
+		if nsrc := a.nodes[src]; nsrc.solve.copyTo.add(dst) {
+			if a.log != nil {
+				fmt.Fprintf(a.log, "\t\t\tdynamic copy n%d <- n%d\n", dst, src)
+			}
+			// TODO(adonovan): most calls to onlineCopy
+			// are followed by addWork, possibly batched
+			// via a 'changed' flag; see if there's a
+			// noticeable penalty to calling addWork here.
+			return a.nodes[dst].solve.pts.addAll(&nsrc.solve.pts)
+		}
+	}
+	return false
+}
+
+// Returns sizeof.
+// Implicitly adds nodes to worklist.
+//
+// TODO(adonovan): now that we support a.copy() during solving, we
+// could eliminate onlineCopyN, but it's much slower.  Investigate.
+//
+func (a *analysis) onlineCopyN(dst, src nodeid, sizeof uint32) uint32 {
+	for i := uint32(0); i < sizeof; i++ {
+		if a.onlineCopy(dst, src) {
+			a.addWork(dst)
+		}
+		src++
+		dst++
+	}
+	return sizeof
+}
+
+func (c *loadConstraint) solve(a *analysis, delta *nodeset) {
+	var changed bool
+	for _, x := range delta.AppendTo(a.deltaSpace) {
+		k := nodeid(x)
+		koff := k + nodeid(c.offset)
+		if a.onlineCopy(c.dst, koff) {
+			changed = true
+		}
+	}
+	if changed {
+		a.addWork(c.dst)
+	}
+}
+
+func (c *storeConstraint) solve(a *analysis, delta *nodeset) {
+	for _, x := range delta.AppendTo(a.deltaSpace) {
+		k := nodeid(x)
+		koff := k + nodeid(c.offset)
+		if a.onlineCopy(koff, c.src) {
+			a.addWork(koff)
+		}
+	}
+}
+
+func (c *offsetAddrConstraint) solve(a *analysis, delta *nodeset) {
+	dst := a.nodes[c.dst]
+	for _, x := range delta.AppendTo(a.deltaSpace) {
+		k := nodeid(x)
+		if dst.solve.pts.add(k + nodeid(c.offset)) {
+			a.addWork(c.dst)
+		}
+	}
+}
+
+func (c *typeFilterConstraint) solve(a *analysis, delta *nodeset) {
+	for _, x := range delta.AppendTo(a.deltaSpace) {
+		ifaceObj := nodeid(x)
+		tDyn, _, indirect := a.taggedValue(ifaceObj)
+		if indirect {
+			// TODO(adonovan): we'll need to implement this
+			// when we start creating indirect tagged objects.
+			panic("indirect tagged object")
+		}
+
+		if types.AssignableTo(tDyn, c.typ) {
+			if a.addLabel(c.dst, ifaceObj) {
+				a.addWork(c.dst)
+			}
+		}
+	}
+}
+
+func (c *untagConstraint) solve(a *analysis, delta *nodeset) {
+	predicate := types.AssignableTo
+	if c.exact {
+		predicate = types.Identical
+	}
+	for _, x := range delta.AppendTo(a.deltaSpace) {
+		ifaceObj := nodeid(x)
+		tDyn, v, indirect := a.taggedValue(ifaceObj)
+		if indirect {
+			// TODO(adonovan): we'll need to implement this
+			// when we start creating indirect tagged objects.
+			panic("indirect tagged object")
+		}
+
+		if predicate(tDyn, c.typ) {
+			// Copy payload sans tag to dst.
+			//
+			// TODO(adonovan): opt: if tDyn is
+			// nonpointerlike we can skip this entire
+			// constraint, perhaps.  We only care about
+			// pointers among the fields.
+			a.onlineCopyN(c.dst, v, a.sizeof(tDyn))
+		}
+	}
+}
+
+func (c *invokeConstraint) solve(a *analysis, delta *nodeset) {
+	for _, x := range delta.AppendTo(a.deltaSpace) {
+		ifaceObj := nodeid(x)
+		tDyn, v, indirect := a.taggedValue(ifaceObj)
+		if indirect {
+			// TODO(adonovan): we may need to implement this if
+			// we ever apply invokeConstraints to reflect.Value PTSs,
+			// e.g. for (reflect.Value).Call.
+			panic("indirect tagged object")
+		}
+
+		// Look up the concrete method.
+		fn := a.prog.LookupMethod(tDyn, c.method.Pkg(), c.method.Name())
+		if fn == nil {
+			panic(fmt.Sprintf("n%d: no ssa.Function for %s", c.iface, c.method))
+		}
+		sig := fn.Signature
+
+		fnObj := a.globalobj[fn] // dynamic calls use shared contour
+		if fnObj == 0 {
+			// a.objectNode(fn) was not called during gen phase.
+			panic(fmt.Sprintf("a.globalobj[%s]==nil", fn))
+		}
+
+		// Make callsite's fn variable point to identity of
+		// concrete method.  (There's no need to add it to
+		// worklist since it never has attached constraints.)
+		a.addLabel(c.params, fnObj)
+
+		// Extract value and connect to method's receiver.
+		// Copy payload to method's receiver param (arg0).
+		arg0 := a.funcParams(fnObj)
+		recvSize := a.sizeof(sig.Recv().Type())
+		a.onlineCopyN(arg0, v, recvSize)
+
+		src := c.params + 1 // skip past identity
+		dst := arg0 + nodeid(recvSize)
+
+		// Copy caller's argument block to method formal parameters.
+		paramsSize := a.sizeof(sig.Params())
+		a.onlineCopyN(dst, src, paramsSize)
+		src += nodeid(paramsSize)
+		dst += nodeid(paramsSize)
+
+		// Copy method results to caller's result block.
+		resultsSize := a.sizeof(sig.Results())
+		a.onlineCopyN(src, dst, resultsSize)
+	}
+}
+
+func (c *addrConstraint) solve(a *analysis, delta *nodeset) {
+	panic("addr is not a complex constraint")
+}
+
+func (c *copyConstraint) solve(a *analysis, delta *nodeset) {
+	panic("copy is not a complex constraint")
+}