...
1
2
3
4
5 package callgraph
6
7 import "golang.org/x/tools/go/ssa"
8
9
10
11
12
13
14 func CalleesOf(caller *Node) map[*Node]bool {
15 callees := make(map[*Node]bool)
16 for _, e := range caller.Out {
17 callees[e.Callee] = true
18 }
19 return callees
20 }
21
22
23
24
25
26 func GraphVisitEdges(g *Graph, edge func(*Edge) error) error {
27 seen := make(map[*Node]bool)
28 var visit func(n *Node) error
29 visit = func(n *Node) error {
30 if !seen[n] {
31 seen[n] = true
32 for _, e := range n.Out {
33 if err := visit(e.Callee); err != nil {
34 return err
35 }
36 if err := edge(e); err != nil {
37 return err
38 }
39 }
40 }
41 return nil
42 }
43 for _, n := range g.Nodes {
44 if err := visit(n); err != nil {
45 return err
46 }
47 }
48 return nil
49 }
50
51
52
53
54
55 func PathSearch(start *Node, isEnd func(*Node) bool) []*Edge {
56 stack := make([]*Edge, 0, 32)
57 seen := make(map[*Node]bool)
58 var search func(n *Node) []*Edge
59 search = func(n *Node) []*Edge {
60 if !seen[n] {
61 seen[n] = true
62 if isEnd(n) {
63 return stack
64 }
65 for _, e := range n.Out {
66 stack = append(stack, e)
67 if found := search(e.Callee); found != nil {
68 return found
69 }
70 stack = stack[:len(stack)-1]
71 }
72 }
73 return nil
74 }
75 return search(start)
76 }
77
78
79
80
81
82 func (g *Graph) DeleteSyntheticNodes() {
83
84
85
86
87
88
89
90
91
92
93
94
95 edges := make(map[Edge]bool)
96 for _, cgn := range g.Nodes {
97 for _, e := range cgn.Out {
98 edges[*e] = true
99 }
100 }
101 for fn, cgn := range g.Nodes {
102 if cgn == g.Root || fn.Synthetic == "" || isInit(cgn.Func) {
103 continue
104 }
105 for _, eIn := range cgn.In {
106 for _, eOut := range cgn.Out {
107 newEdge := Edge{eIn.Caller, eIn.Site, eOut.Callee}
108 if edges[newEdge] {
109 continue
110 }
111 AddEdge(eIn.Caller, eIn.Site, eOut.Callee)
112 edges[newEdge] = true
113 }
114 }
115 g.DeleteNode(cgn)
116 }
117 }
118
119 func isInit(fn *ssa.Function) bool {
120 return fn.Pkg != nil && fn.Pkg.Func("init") == fn
121 }
122
123
124
125 func (g *Graph) DeleteNode(n *Node) {
126 n.deleteIns()
127 n.deleteOuts()
128 delete(g.Nodes, n.Func)
129 }
130
131
132 func (n *Node) deleteIns() {
133 for _, e := range n.In {
134 removeOutEdge(e)
135 }
136 n.In = nil
137 }
138
139
140 func (n *Node) deleteOuts() {
141 for _, e := range n.Out {
142 removeInEdge(e)
143 }
144 n.Out = nil
145 }
146
147
148 func removeOutEdge(edge *Edge) {
149 caller := edge.Caller
150 n := len(caller.Out)
151 for i, e := range caller.Out {
152 if e == edge {
153
154 caller.Out[i] = caller.Out[n-1]
155 caller.Out[n-1] = nil
156 caller.Out = caller.Out[:n-1]
157 return
158 }
159 }
160 panic("edge not found: " + edge.String())
161 }
162
163
164 func removeInEdge(edge *Edge) {
165 caller := edge.Callee
166 n := len(caller.In)
167 for i, e := range caller.In {
168 if e == edge {
169
170 caller.In[i] = caller.In[n-1]
171 caller.In[n-1] = nil
172 caller.In = caller.In[:n-1]
173 return
174 }
175 }
176 panic("edge not found: " + edge.String())
177 }
178
View as plain text