| // 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 callgraph | |
| import "golang.org/x/tools/go/ssa" | |
| // This file provides various utilities over call graphs, such as | |
| // visitation and path search. | |
| // CalleesOf returns a new set containing all direct callees of the | |
| // caller node. | |
| func CalleesOf(caller *Node) map[*Node]bool { | |
| callees := make(map[*Node]bool) | |
| for _, e := range caller.Out { | |
| callees[e.Callee] = true | |
| } | |
| return callees | |
| } | |
| // GraphVisitEdges visits all the edges in graph g in depth-first order. | |
| // The edge function is called for each edge in postorder. If it | |
| // returns non-nil, visitation stops and GraphVisitEdges returns that | |
| // value. | |
| func GraphVisitEdges(g *Graph, edge func(*Edge) error) error { | |
| seen := make(map[*Node]bool) | |
| var visit func(n *Node) error | |
| visit = func(n *Node) error { | |
| if !seen[n] { | |
| seen[n] = true | |
| for _, e := range n.Out { | |
| if err := visit(e.Callee); err != nil { | |
| return err | |
| } | |
| if err := edge(e); err != nil { | |
| return err | |
| } | |
| } | |
| } | |
| return nil | |
| } | |
| for _, n := range g.Nodes { | |
| if err := visit(n); err != nil { | |
| return err | |
| } | |
| } | |
| return nil | |
| } | |
| // PathSearch finds an arbitrary path starting at node start and | |
| // ending at some node for which isEnd() returns true. On success, | |
| // PathSearch returns the path as an ordered list of edges; on | |
| // failure, it returns nil. | |
| func PathSearch(start *Node, isEnd func(*Node) bool) []*Edge { | |
| stack := make([]*Edge, 0, 32) | |
| seen := make(map[*Node]bool) | |
| var search func(n *Node) []*Edge | |
| search = func(n *Node) []*Edge { | |
| if !seen[n] { | |
| seen[n] = true | |
| if isEnd(n) { | |
| return stack | |
| } | |
| for _, e := range n.Out { | |
| stack = append(stack, e) // push | |
| if found := search(e.Callee); found != nil { | |
| return found | |
| } | |
| stack = stack[:len(stack)-1] // pop | |
| } | |
| } | |
| return nil | |
| } | |
| return search(start) | |
| } | |
| // DeleteSyntheticNodes removes from call graph g all nodes for | |
| // functions that do not correspond to source syntax. For historical | |
| // reasons, nodes for g.Root and package initializers are always | |
| // kept. | |
| // | |
| // As nodes are removed, edges are created to preserve the | |
| // reachability relation of the remaining nodes. | |
| func (g *Graph) DeleteSyntheticNodes() { | |
| // Measurements on the standard library and go.tools show that | |
| // resulting graph has ~15% fewer nodes and 4-8% fewer edges | |
| // than the input. | |
| // | |
| // Inlining a wrapper of in-degree m, out-degree n adds m*n | |
| // and removes m+n edges. Since most wrappers are monomorphic | |
| // (n=1) this results in a slight reduction. Polymorphic | |
| // wrappers (n>1), e.g. from embedding an interface value | |
| // inside a struct to satisfy some interface, cause an | |
| // increase in the graph, but they seem to be uncommon. | |
| // Hash all existing edges to avoid creating duplicates. | |
| edges := make(map[Edge]bool) | |
| for _, cgn := range g.Nodes { | |
| for _, e := range cgn.Out { | |
| edges[*e] = true | |
| } | |
| } | |
| for fn, cgn := range g.Nodes { | |
| if cgn == g.Root || isInit(cgn.Func) || fn.Syntax() != nil { | |
| continue // keep | |
| } | |
| for _, eIn := range cgn.In { | |
| for _, eOut := range cgn.Out { | |
| newEdge := Edge{eIn.Caller, eIn.Site, eOut.Callee} | |
| if edges[newEdge] { | |
| continue // don't add duplicate | |
| } | |
| AddEdge(eIn.Caller, eIn.Site, eOut.Callee) | |
| edges[newEdge] = true | |
| } | |
| } | |
| g.DeleteNode(cgn) | |
| } | |
| } | |
| func isInit(fn *ssa.Function) bool { | |
| return fn.Pkg != nil && fn.Pkg.Func("init") == fn | |
| } | |
| // DeleteNode removes node n and its edges from the graph g. | |
| // (NB: not efficient for batch deletion.) | |
| func (g *Graph) DeleteNode(n *Node) { | |
| n.deleteIns() | |
| n.deleteOuts() | |
| delete(g.Nodes, n.Func) | |
| } | |
| // deleteIns deletes all incoming edges to n. | |
| func (n *Node) deleteIns() { | |
| for _, e := range n.In { | |
| removeOutEdge(e) | |
| } | |
| n.In = nil | |
| } | |
| // deleteOuts deletes all outgoing edges from n. | |
| func (n *Node) deleteOuts() { | |
| for _, e := range n.Out { | |
| removeInEdge(e) | |
| } | |
| n.Out = nil | |
| } | |
| // removeOutEdge removes edge.Caller's outgoing edge 'edge'. | |
| func removeOutEdge(edge *Edge) { | |
| caller := edge.Caller | |
| n := len(caller.Out) | |
| for i, e := range caller.Out { | |
| if e == edge { | |
| // Replace it with the final element and shrink the slice. | |
| caller.Out[i] = caller.Out[n-1] | |
| caller.Out[n-1] = nil // aid GC | |
| caller.Out = caller.Out[:n-1] | |
| return | |
| } | |
| } | |
| panic("edge not found: " + edge.String()) | |
| } | |
| // removeInEdge removes edge.Callee's incoming edge 'edge'. | |
| func removeInEdge(edge *Edge) { | |
| caller := edge.Callee | |
| n := len(caller.In) | |
| for i, e := range caller.In { | |
| if e == edge { | |
| // Replace it with the final element and shrink the slice. | |
| caller.In[i] = caller.In[n-1] | |
| caller.In[n-1] = nil // aid GC | |
| caller.In = caller.In[:n-1] | |
| return | |
| } | |
| } | |
| panic("edge not found: " + edge.String()) | |
| } |