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 }