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
5package callgraph
6
7import "golang.org/x/tools/go/ssa"
8
9// This file provides various utilities over call graphs, such as
10// visitation and path search.
11
12// CalleesOf returns a new set containing all direct callees of the
13// caller node.
14//
15func CalleesOf(caller *Node) map[*Node]bool {
16	callees := make(map[*Node]bool)
17	for _, e := range caller.Out {
18		callees[e.Callee] = true
19	}
20	return callees
21}
22
23// GraphVisitEdges visits all the edges in graph g in depth-first order.
24// The edge function is called for each edge in postorder.  If it
25// returns non-nil, visitation stops and GraphVisitEdges returns that
26// value.
27//
28func GraphVisitEdges(g *Graph, edge func(*Edge) error) error {
29	seen := make(map[*Node]bool)
30	var visit func(n *Node) error
31	visit = func(n *Node) error {
32		if !seen[n] {
33			seen[n] = true
34			for _, e := range n.Out {
35				if err := visit(e.Callee); err != nil {
36					return err
37				}
38				if err := edge(e); err != nil {
39					return err
40				}
41			}
42		}
43		return nil
44	}
45	for _, n := range g.Nodes {
46		if err := visit(n); err != nil {
47			return err
48		}
49	}
50	return nil
51}
52
53// PathSearch finds an arbitrary path starting at node start and
54// ending at some node for which isEnd() returns true.  On success,
55// PathSearch returns the path as an ordered list of edges; on
56// failure, it returns nil.
57//
58func PathSearch(start *Node, isEnd func(*Node) bool) []*Edge {
59	stack := make([]*Edge, 0, 32)
60	seen := make(map[*Node]bool)
61	var search func(n *Node) []*Edge
62	search = func(n *Node) []*Edge {
63		if !seen[n] {
64			seen[n] = true
65			if isEnd(n) {
66				return stack
67			}
68			for _, e := range n.Out {
69				stack = append(stack, e) // push
70				if found := search(e.Callee); found != nil {
71					return found
72				}
73				stack = stack[:len(stack)-1] // pop
74			}
75		}
76		return nil
77	}
78	return search(start)
79}
80
81// DeleteSyntheticNodes removes from call graph g all nodes for
82// synthetic functions (except g.Root and package initializers),
83// preserving the topology.  In effect, calls to synthetic wrappers
84// are "inlined".
85//
86func (g *Graph) DeleteSyntheticNodes() {
87	// Measurements on the standard library and go.tools show that
88	// resulting graph has ~15% fewer nodes and 4-8% fewer edges
89	// than the input.
90	//
91	// Inlining a wrapper of in-degree m, out-degree n adds m*n
92	// and removes m+n edges.  Since most wrappers are monomorphic
93	// (n=1) this results in a slight reduction.  Polymorphic
94	// wrappers (n>1), e.g. from embedding an interface value
95	// inside a struct to satisfy some interface, cause an
96	// increase in the graph, but they seem to be uncommon.
97
98	// Hash all existing edges to avoid creating duplicates.
99	edges := make(map[Edge]bool)
100	for _, cgn := range g.Nodes {
101		for _, e := range cgn.Out {
102			edges[*e] = true
103		}
104	}
105	for fn, cgn := range g.Nodes {
106		if cgn == g.Root || fn.Synthetic == "" || isInit(cgn.Func) {
107			continue // keep
108		}
109		for _, eIn := range cgn.In {
110			for _, eOut := range cgn.Out {
111				newEdge := Edge{eIn.Caller, eIn.Site, eOut.Callee}
112				if edges[newEdge] {
113					continue // don't add duplicate
114				}
115				AddEdge(eIn.Caller, eIn.Site, eOut.Callee)
116				edges[newEdge] = true
117			}
118		}
119		g.DeleteNode(cgn)
120	}
121}
122
123func isInit(fn *ssa.Function) bool {
124	return fn.Pkg != nil && fn.Pkg.Func("init") == fn
125}
126
127// DeleteNode removes node n and its edges from the graph g.
128// (NB: not efficient for batch deletion.)
129func (g *Graph) DeleteNode(n *Node) {
130	n.deleteIns()
131	n.deleteOuts()
132	delete(g.Nodes, n.Func)
133}
134
135// deleteIns deletes all incoming edges to n.
136func (n *Node) deleteIns() {
137	for _, e := range n.In {
138		removeOutEdge(e)
139	}
140	n.In = nil
141}
142
143// deleteOuts deletes all outgoing edges from n.
144func (n *Node) deleteOuts() {
145	for _, e := range n.Out {
146		removeInEdge(e)
147	}
148	n.Out = nil
149}
150
151// removeOutEdge removes edge.Caller's outgoing edge 'edge'.
152func removeOutEdge(edge *Edge) {
153	caller := edge.Caller
154	n := len(caller.Out)
155	for i, e := range caller.Out {
156		if e == edge {
157			// Replace it with the final element and shrink the slice.
158			caller.Out[i] = caller.Out[n-1]
159			caller.Out[n-1] = nil // aid GC
160			caller.Out = caller.Out[:n-1]
161			return
162		}
163	}
164	panic("edge not found: " + edge.String())
165}
166
167// removeInEdge removes edge.Callee's incoming edge 'edge'.
168func removeInEdge(edge *Edge) {
169	caller := edge.Callee
170	n := len(caller.In)
171	for i, e := range caller.In {
172		if e == edge {
173			// Replace it with the final element and shrink the slice.
174			caller.In[i] = caller.In[n-1]
175			caller.In[n-1] = nil // aid GC
176			caller.In = caller.In[:n-1]
177			return
178		}
179	}
180	panic("edge not found: " + edge.String())
181}
182