go.tools/pointer: use new callgraph API.
Also: pointer.Analyze now returns a pointer.Result object,
containing the callgraph and the results of ssa.Value queries.
The oracle has been updated to use the new call and pointer APIs.
R=crawshaw, gri
CC=golang-dev
https://golang.org/cl/13915043
diff --git a/pointer/TODO b/pointer/TODO
index d5f12bc..10afd49 100644
--- a/pointer/TODO
+++ b/pointer/TODO
@@ -32,12 +32,6 @@
dannyb recommends sparse bitmap.
API:
-- Rely less on callbacks and more on a 'result' type
- returned by Analyze().
-- Abstract the callgraph into a pure interface so that
- we can provide other implementations in future (e.g. RTA-based).
- Also provide the option to eliminate context-sensitivity
- in a callgraph to yield a smaller (less precise) callgraph.
- Some optimisations (e.g. LE, PE) may change the API.
Think about them sooner rather than later.
- Eliminate Print probe now that we can query specific ssa.Values.
diff --git a/pointer/analysis.go b/pointer/analysis.go
index b825bb1..d645365 100644
--- a/pointer/analysis.go
+++ b/pointer/analysis.go
@@ -173,13 +173,14 @@
nodes []*node // indexed by nodeid
flattenMemo map[types.Type][]*fieldInfo // memoization of flatten()
constraints []constraint // set of constraints
- callsites []*callsite // all callsites
+ cgnodes []*cgnode // all cgnodes
genq []*cgnode // queue of functions to generate constraints for
intrinsics map[*ssa.Function]intrinsic // non-nil values are summaries for intrinsic fns
funcObj map[*ssa.Function]nodeid // default function object for each func
probes map[*ssa.CallCommon]nodeid // maps call to print() to argument variable
valNode map[ssa.Value]nodeid // node for each ssa.Value
work worklist // solver's worklist
+ queries map[ssa.Value][]Pointer // same as Results.Queries
// Reflection:
hasher typemap.Hasher // cache of type hashes
@@ -229,7 +230,7 @@
// Analyze runs the pointer analysis with the scope and options
// specified by config, and returns the (synthetic) root of the callgraph.
//
-func Analyze(config *Config) CallGraphNode {
+func Analyze(config *Config) *Result {
a := &analysis{
config: config,
log: config.Log,
@@ -241,6 +242,7 @@
funcObj: make(map[*ssa.Function]nodeid),
probes: make(map[*ssa.CallCommon]nodeid),
work: makeMapWorklist(),
+ queries: make(map[ssa.Value][]Pointer),
}
if reflect := a.prog.ImportedPackage("reflect"); reflect != nil {
@@ -265,7 +267,7 @@
fmt.Fprintln(a.log, "======== NEW ANALYSIS ========")
}
- root := a.generate()
+ a.generate()
//a.optimize()
@@ -280,32 +282,33 @@
}
}
- // Notify the client of the callsites if they're interested.
- if CallSite := a.config.CallSite; CallSite != nil {
- for _, site := range a.callsites {
- CallSite(site)
- }
- }
+ // Visit discovered call graph.
+ for _, caller := range a.cgnodes {
+ for _, site := range caller.sites {
+ for nid := range a.nodes[site.targets].pts {
+ callee := a.nodes[nid].obj.cgn
- Call := a.config.Call
- for _, site := range a.callsites {
- for nid := range a.nodes[site.targets].pts {
- cgn := a.nodes[nid].obj.cgn
+ if a.config.BuildCallGraph {
+ site.callees = append(site.callees, callee)
+ }
- // Notify the client of the call graph, if
- // they're interested.
- if Call != nil {
- Call(site, cgn)
- }
-
- // Warn about calls to non-intrinsic external functions.
-
- if fn := cgn.fn; fn.Blocks == nil && a.findIntrinsic(fn) == nil {
- a.warnf(site.Pos(), "unsound call to unknown intrinsic: %s", fn)
- a.warnf(fn.Pos(), " (declared here)")
+ // TODO(adonovan): de-dup these messages.
+ // Warn about calls to non-intrinsic external functions.
+ if fn := callee.fn; fn.Blocks == nil && a.findIntrinsic(fn) == nil {
+ a.warnf(site.pos(), "unsound call to unknown intrinsic: %s", fn)
+ a.warnf(fn.Pos(), " (declared here)")
+ }
}
}
}
- return root
+ var callgraph *cgraph
+ if a.config.BuildCallGraph {
+ callgraph = &cgraph{a.cgnodes}
+ }
+
+ return &Result{
+ CallGraph: callgraph,
+ Queries: a.queries,
+ }
}
diff --git a/pointer/api.go b/pointer/api.go
index f1f4e47..3867b2a 100644
--- a/pointer/api.go
+++ b/pointer/api.go
@@ -9,6 +9,7 @@
"go/token"
"io"
+ "code.google.com/p/go.tools/call"
"code.google.com/p/go.tools/go/types/typemap"
"code.google.com/p/go.tools/ssa"
)
@@ -27,31 +28,12 @@
// has not yet been reduced by presolver optimisation.
Reflection bool
+ // BuildCallGraph determines whether to construct a callgraph.
+ // If enabled, the graph will be available in Result.CallGraph.
+ BuildCallGraph bool
+
// -------- Optional callbacks invoked by the analysis --------
- // Call is invoked for each discovered call-graph edge. The
- // call-graph is a multigraph over CallGraphNodes with edges
- // labelled by the CallSite that gives rise to the edge.
- // (The caller node is available as site.Caller())
- //
- // Clients that wish to construct a call graph may provide
- // CallGraph.AddEdge here.
- //
- // The callgraph may be context-sensitive, i.e. it may
- // distinguish separate calls to the same function depending
- // on the context.
- //
- Call func(site CallSite, callee CallGraphNode)
-
- // CallSite is invoked for each call-site encountered in the
- // program.
- //
- // The callgraph may be context-sensitive, i.e. it may
- // distinguish separate calls to the same function depending
- // on the context.
- //
- CallSite func(site CallSite)
-
// Warn is invoked for each warning encountered by the analysis,
// e.g. unknown external function, unsound use of unsafe.Pointer.
// pos may be zero if the position is not known.
@@ -71,8 +53,8 @@
//
Print func(site *ssa.CallCommon, p Pointer)
- // The client populates QueryValues[v] for each ssa.Value v
- // of interest.
+ // The client populates Queries[v] for each ssa.Value v of
+ // interest.
//
// The boolean (Indirect) indicates whether to compute the
// points-to set for v (false) or *v (true): the latter is
@@ -80,20 +62,16 @@
// lvalues, e.g. an *ssa.Global.
//
// The pointer analysis will populate the corresponding
- // QueryResults value when it creates the pointer variable
- // for v or *v. Upon completion the client can inspect the
+ // Results.Queries value when it creates the pointer variable
+ // for v or *v. Upon completion the client can inspect that
// map for the results.
//
// If a Value belongs to a function that the analysis treats
- // context-sensitively, the corresponding QueryResults slice
+ // context-sensitively, the corresponding Results.Queries slice
// may have multiple Pointers, one per distinct context. Use
// PointsToCombined to merge them.
//
- // TODO(adonovan): refactor the API: separate all results of
- // Analyze() into a dedicated Result struct.
- //
- QueryValues map[ssa.Value]Indirect
- QueryResults map[ssa.Value][]Pointer
+ Queries map[ssa.Value]Indirect
// -------- Other configuration options --------
@@ -111,10 +89,19 @@
panic("empty scope")
}
+// A Result contains the results of a pointer analysis.
+//
+// See Config for how to request the various Result components.
+//
+type Result struct {
+ CallGraph call.Graph // discovered call graph
+ Queries map[ssa.Value][]Pointer // points-to sets for queried ssa.Values
+}
+
// A Pointer is an equivalence class of pointerlike values.
//
// TODO(adonovan): add a method
-// Context() CallGraphNode
+// Context() call.GraphNode
// for pointers corresponding to local variables,
//
type Pointer interface {
diff --git a/pointer/callgraph.go b/pointer/callgraph.go
index af328a9..e3d8bce 100644
--- a/pointer/callgraph.go
+++ b/pointer/callgraph.go
@@ -4,116 +4,93 @@
package pointer
+// This file defines our implementation of the call.Graph API.
+
import (
"fmt"
"go/token"
+ "code.google.com/p/go.tools/call"
"code.google.com/p/go.tools/ssa"
)
-// TODO(adonovan): move the CallGraph, CallGraphNode, CallSite types
-// into a separate package 'callgraph', and make them pure interfaces
-// capable of supporting several implementations (context-sensitive
-// and insensitive PTA, RTA, etc).
-
-// ---------- CallGraphNode ----------
-
-// A CallGraphNode is a context-sensitive representation of a node in
-// the callgraph. In other words, there may be multiple nodes
-// representing a single *Function, depending on the contexts in which
-// it is called. The identity of the node is therefore important.
-//
-type CallGraphNode interface {
- Func() *ssa.Function // the function this node represents
- String() string // diagnostic description of this callgraph node
+// cgraph implements call.Graph.
+type cgraph struct {
+ nodes []*cgnode
}
+func (g *cgraph) Nodes() []call.GraphNode {
+ nodes := make([]call.GraphNode, len(g.nodes))
+ for i, node := range g.nodes {
+ nodes[i] = node
+ }
+ return nodes
+}
+
+func (g *cgraph) Root() call.GraphNode {
+ return g.nodes[0]
+}
+
+// cgnode implements call.GraphNode.
type cgnode struct {
- fn *ssa.Function
- obj nodeid // start of this contour's object block
+ fn *ssa.Function
+ obj nodeid // start of this contour's object block
+ sites []*callsite // ordered list of callsites within this function
}
func (n *cgnode) Func() *ssa.Function {
return n.fn
}
+func (n *cgnode) Sites() []ssa.CallInstruction {
+ sites := make([]ssa.CallInstruction, len(n.sites))
+ for i, site := range n.sites {
+ sites[i] = site.instr
+ }
+ return sites
+}
+
+func (n *cgnode) Edges() []call.Edge {
+ var numEdges int
+ for _, site := range n.sites {
+ numEdges += len(site.callees)
+ }
+ edges := make([]call.Edge, 0, numEdges)
+
+ for _, site := range n.sites {
+ for _, callee := range site.callees {
+ edges = append(edges, call.Edge{Caller: n, Site: site.instr, Callee: callee})
+ }
+ }
+ return edges
+}
+
func (n *cgnode) String() string {
return fmt.Sprintf("cg%d:%s", n.obj, n.fn)
}
-// ---------- CallSite ----------
-
-// A CallSite is a context-sensitive representation of a function call
-// site in the program.
-//
-type CallSite interface {
- Caller() CallGraphNode // the enclosing context of this call
- Pos() token.Pos // source position; token.NoPos for synthetic calls
- Description() string // UI description of call kind; see (*ssa.CallCommon).Description
- String() string // diagnostic description of this callsite
-}
-
-// A callsite represents a single function or method callsite within a
-// function. callsites never represent calls to built-ins; they are
-// handled as intrinsics.
+// A callsite represents a single call site within a cgnode;
+// it is implicitly context-sensitive.
+// callsites never represent calls to built-ins;
+// they are handled as intrinsics.
//
type callsite struct {
- caller *cgnode // the origin of the call
targets nodeid // pts(targets) contains identities of all called functions.
- instr ssa.CallInstruction // optional call instruction; provides IsInvoke, position, etc.
- pos token.Pos // position, if instr == nil, i.e. synthetic callsites.
+ instr ssa.CallInstruction // the call instruction; nil for synthetic/intrinsic
+ callees []*cgnode // unordered set of callees of this site
}
-// Caller returns the node in the callgraph from which this call originated.
-func (c *callsite) Caller() CallGraphNode {
- return c.caller
-}
-
-// Description returns a description of this kind of call, in the
-// manner of ssa.CallCommon.Description().
-//
-func (c *callsite) Description() string {
+func (c *callsite) String() string {
if c.instr != nil {
return c.instr.Common().Description()
}
return "synthetic function call"
}
-// Pos returns the source position of this callsite, or token.NoPos if implicit.
-func (c *callsite) Pos() token.Pos {
+// pos returns the source position of this callsite, or token.NoPos if implicit.
+func (c *callsite) pos() token.Pos {
if c.instr != nil {
return c.instr.Pos()
}
- return c.pos
-}
-
-func (c *callsite) String() string {
- // TODO(adonovan): provide more info, e.g. target of static
- // call, arguments, location.
- return c.Description()
-}
-
-// ---------- CallGraph ----------
-
-// CallGraph is a forward directed graph of functions labelled by an
-// arbitrary site within the caller.
-//
-// CallGraph.AddEdge may be used as the Context.Call callback for
-// clients that wish to construct a call graph.
-//
-// TODO(adonovan): this is just a starting point. Add options to
-// control whether we record no callsite, an arbitrary callsite, or
-// all callsites for a given graph edge. Also, this could live in
-// another package since it's just a client utility.
-//
-type CallGraph map[CallGraphNode]map[CallGraphNode]CallSite
-
-func (cg CallGraph) AddEdge(site CallSite, callee CallGraphNode) {
- caller := site.Caller()
- callees := cg[caller]
- if callees == nil {
- callees = make(map[CallGraphNode]CallSite)
- cg[caller] = callees
- }
- callees[callee] = site // save an arbitrary site
+ return token.NoPos
}
diff --git a/pointer/example_test.go b/pointer/example_test.go
index fae6195..bd86818a 100644
--- a/pointer/example_test.go
+++ b/pointer/example_test.go
@@ -10,6 +10,7 @@
"go/parser"
"sort"
+ "code.google.com/p/go.tools/call"
"code.google.com/p/go.tools/importer"
"code.google.com/p/go.tools/pointer"
"code.google.com/p/go.tools/ssa"
@@ -66,34 +67,23 @@
prog.BuildAll()
// Run the pointer analysis and build the complete callgraph.
- callgraph := make(pointer.CallGraph)
config := &pointer.Config{
- Mains: []*ssa.Package{mainPkg},
- Call: callgraph.AddEdge,
+ Mains: []*ssa.Package{mainPkg},
+ BuildCallGraph: true,
}
- root := pointer.Analyze(config)
+ result := pointer.Analyze(config)
- // Visit callgraph in depth-first order.
- //
- // There may be multiple nodes for the
- // same function due to context sensitivity.
- var edges []string // call edges originating from the main package.
- seen := make(map[pointer.CallGraphNode]bool)
- var visit func(cgn pointer.CallGraphNode)
- visit = func(cgn pointer.CallGraphNode) {
- if seen[cgn] {
- return // already seen
+ // Find edges originating from the main package.
+ // By converting to strings, we de-duplicate nodes
+ // representing the same function due to context sensitivity.
+ var edges []string
+ call.GraphVisitEdges(result.CallGraph, func(edge call.Edge) error {
+ caller := edge.Caller.Func()
+ if caller.Pkg == mainPkg {
+ edges = append(edges, fmt.Sprint(caller, " --> ", edge.Callee.Func()))
}
- seen[cgn] = true
- caller := cgn.Func()
- for callee := range callgraph[cgn] {
- if caller.Pkg == mainPkg {
- edges = append(edges, fmt.Sprint(caller, " --> ", callee.Func()))
- }
- visit(callee)
- }
- }
- visit(root)
+ return nil
+ })
// Print the edges in sorted order.
sort.Strings(edges)
diff --git a/pointer/gen.go b/pointer/gen.go
index 62fb103..cebeff5 100644
--- a/pointer/gen.go
+++ b/pointer/gen.go
@@ -72,18 +72,13 @@
}
// Record the (v, id) relation if the client has queried v.
- if indirect, ok := a.config.QueryValues[v]; ok {
+ if indirect, ok := a.config.Queries[v]; ok {
if indirect {
tmp := a.addNodes(v.Type(), "query.indirect")
a.load(tmp, id, a.sizeof(v.Type()))
id = tmp
}
- ptrs := a.config.QueryResults
- if ptrs == nil {
- ptrs = make(map[ssa.Value][]Pointer)
- a.config.QueryResults = ptrs
- }
- ptrs[v] = append(ptrs[v], ptr{a, id})
+ a.queries[v] = append(a.queries[v], ptr{a, id})
}
}
@@ -125,7 +120,7 @@
// obj is the function object (identity, params, results).
obj := a.nextNode()
- cgn := &cgnode{fn: fn, obj: obj}
+ cgn := a.makeCGNode(fn, obj)
sig := fn.Signature
a.addOneNode(sig, "func.cgnode", nil) // (scalar with Signature type)
if recv := sig.Recv(); recv != nil {
@@ -849,15 +844,12 @@
}
site := &callsite{
- caller: caller,
targets: targets,
instr: instr,
- pos: instr.Pos(),
}
- a.callsites = append(a.callsites, site)
+ caller.sites = append(caller.sites, site)
if a.log != nil {
- fmt.Fprintf(a.log, "\t%s to targets %s from %s\n",
- site.Description(), site.targets, site.caller)
+ fmt.Fprintf(a.log, "\t%s to targets %s from %s\n", site, site.targets, caller)
}
}
@@ -1061,6 +1053,12 @@
}
}
+func (a *analysis) makeCGNode(fn *ssa.Function, obj nodeid) *cgnode {
+ cgn := &cgnode{fn: fn, obj: obj}
+ a.cgnodes = append(a.cgnodes, cgn)
+ return cgn
+}
+
// genRootCalls generates the synthetic root of the callgraph and the
// initial calls from it to the analysis scope, such as main, a test
// or a library.
@@ -1070,7 +1068,7 @@
r.Prog = a.prog // hack.
r.Enclosing = r // hack, so Function.String() doesn't crash
r.String() // (asserts that it doesn't crash)
- root := &cgnode{fn: r}
+ root := a.makeCGNode(r, 0)
// For each main package, call main.init(), main.main().
for _, mainPkg := range a.config.Mains {
@@ -1080,11 +1078,8 @@
}
targets := a.addOneNode(main.Signature, "root.targets", nil)
- site := &callsite{
- caller: root,
- targets: targets,
- }
- a.callsites = append(a.callsites, site)
+ site := &callsite{targets: targets}
+ root.sites = append(root.sites, site)
for _, fn := range [2]*ssa.Function{mainPkg.Func("init"), main} {
if a.log != nil {
fmt.Fprintf(a.log, "\troot call to %s:\n", fn)
diff --git a/pointer/labels.go b/pointer/labels.go
index 6f33f1f..215d24c 100644
--- a/pointer/labels.go
+++ b/pointer/labels.go
@@ -9,6 +9,7 @@
"go/token"
"strings"
+ "code.google.com/p/go.tools/call"
"code.google.com/p/go.tools/go/types"
"code.google.com/p/go.tools/ssa"
)
@@ -46,7 +47,7 @@
// Context returns the analytic context in which this label's object was allocated,
// or nil for global objects: global, const, and shared contours for functions.
//
-func (l Label) Context() CallGraphNode {
+func (l Label) Context() call.GraphNode {
return l.obj.cgn
}
diff --git a/pointer/pointer_test.go b/pointer/pointer_test.go
index 8799e71..7f4a500 100644
--- a/pointer/pointer_test.go
+++ b/pointer/pointer_test.go
@@ -10,6 +10,7 @@
import (
"bytes"
+ "errors"
"fmt"
"go/build"
"go/parser"
@@ -21,6 +22,7 @@
"strings"
"testing"
+ "code.google.com/p/go.tools/call"
"code.google.com/p/go.tools/go/types"
"code.google.com/p/go.tools/go/types/typemap"
"code.google.com/p/go.tools/importer"
@@ -286,24 +288,22 @@
var warnings []string
var log bytes.Buffer
- callgraph := make(pointer.CallGraph)
-
// Run the analysis.
config := &pointer.Config{
- Reflection: true,
- Mains: []*ssa.Package{ptrmain},
- Log: &log,
+ Reflection: true,
+ BuildCallGraph: true,
+ Mains: []*ssa.Package{ptrmain},
+ Log: &log,
Print: func(site *ssa.CallCommon, p pointer.Pointer) {
probes = append(probes, probe{site, p})
},
- Call: callgraph.AddEdge,
Warn: func(pos token.Pos, format string, args ...interface{}) {
msg := fmt.Sprintf(format, args...)
fmt.Printf("%s: warning: %s\n", prog.Fset.Position(pos), msg)
warnings = append(warnings, msg)
},
}
- pointer.Analyze(config)
+ result := pointer.Analyze(config)
// Print the log is there was an error or a panic.
complete := false
@@ -341,7 +341,7 @@
}
case "calls":
- if !checkCallsExpectation(prog, e, callgraph) {
+ if !checkCallsExpectation(prog, e, result.CallGraph) {
ok = false
}
@@ -463,29 +463,33 @@
e.errorf("interface may additionally contain these types: %s", surplus.KeysString())
}
return ok
- return false
}
-func checkCallsExpectation(prog *ssa.Program, e *expectation, callgraph pointer.CallGraph) bool {
- // TODO(adonovan): this is inefficient and not robust against
- // typos. Better to convert strings to *Functions during
- // expectation parsing (somehow).
- for caller, callees := range callgraph {
- if caller.Func().String() == e.args[0] {
- found := make(map[string]struct{})
- for callee := range callees {
- s := callee.Func().String()
- found[s] = struct{}{}
- if s == e.args[1] {
- return true // expectation satisfied
- }
+var errOK = errors.New("OK")
+
+func checkCallsExpectation(prog *ssa.Program, e *expectation, callgraph call.Graph) bool {
+ found := make(map[string]struct{})
+ err := call.GraphVisitEdges(callgraph, func(edge call.Edge) error {
+ // Name-based matching is inefficient but it allows us to
+ // match functions whose names that would not appear in an
+ // index ("<root>") or which are not unique ("func@1.2").
+ if edge.Caller.Func().String() == e.args[0] {
+ calleeStr := edge.Callee.Func().String()
+ if calleeStr == e.args[1] {
+ return errOK // expectation satisified; stop the search
}
- e.errorf("found no call from %s to %s, but only to %s",
- e.args[0], e.args[1], join(found))
- return false
+ found[calleeStr] = struct{}{}
}
+ return nil
+ })
+ if err == errOK {
+ return true
}
- e.errorf("didn't find any calls from %s", e.args[0])
+ if len(found) == 0 {
+ e.errorf("didn't find any calls from %s", e.args[0])
+ }
+ e.errorf("found no call from %s to %s, but only to %s",
+ e.args[0], e.args[1], join(found))
return false
}
