Debian Codegraph @

share/analysis-scripts/build_callgraph.py

raw
1 # -*- coding: utf-8 -*-
2 ##########################################################################
3 # #
4 # This file is part of Frama-C. #
5 # #
6 # Copyright (C) 2007-2022 #
7 # CEA (Commissariat à l'énergie atomique et aux énergies #
8 # alternatives) #
9 # #
10 # you can redistribute it and/or modify it under the terms of the GNU #
11 # Lesser General Public License as published by the Free Software #
12 # Foundation, version 2.1. #
13 # #
14 # It is distributed in the hope that it will be useful, #
15 # but WITHOUT ANY WARRANTY; without even the implied warranty of #
16 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the #
17 # GNU Lesser General Public License for more details. #
18 # #
19 # See the GNU Lesser General Public License version 2.1 #
20 # for more details (enclosed in the file licenses/LGPLv2.1). #
21 # #
22 ##########################################################################
23
24 """This script finds files containing likely declarations and definitions
25 for a given function name, via heuristic syntactic matching."""
26
27 import os
28 import sys
29
30 import function_finder
31 import source_filter
32
33 under_test = os.getenv("PTESTS_TESTING")
34
35 debug = os.getenv("DEBUG")
36
37
38 class Callgraph:
39 """
40 Heuristics-based callgraphs.
41 Nodes are function names. Edges (caller, callee, locations) contain the source
42 and target nodes, plus a list of locations (file, line) where calls from
43 [caller] to [callee] occur.
44 """
45
46 # maps each caller to the list of its callees
47 succs = {}
48
49 # maps (caller, callee) to the list of call locations
50 edges = {}
51
52 def add_edge(self, caller, callee, loc):
53 if (caller, callee) in self.edges:
54 # edge already exists
55 self.edges[(caller, callee)].append(loc)
56 else:
57 # new edge: check if caller exists
58 if not caller in self.succs:
59 self.succs[caller] = []
60 # add callee as successor of caller
61 self.succs[caller].append(callee)
62 # add call location to edge information
63 self.edges[(caller, callee)] = [loc]
64
65 def nodes(self):
66 return self.succs.keys()
67
68 def __repr__(self):
69 return f"Callgraph({self.succs}, {self.edges})"
70
71
72 def compute(files):
73 cg = Callgraph()
74 for f in files:
75 file_content = source_filter.open_and_filter(f, not under_test)
76 file_lines = file_content.splitlines(keepends=True)
77 newlines = function_finder.compute_newline_offsets(file_lines)
78 defs = function_finder.find_definitions_and_declarations(
79 True, False, f, file_content, file_lines, newlines
80 )
81 calls = function_finder.find_calls(file_content, newlines)
82 for call in calls:
83 caller = function_finder.find_caller(defs, call)
84 if caller:
85 called, line, _ = call
86 loc = (f, line)
87 if debug:
88 print(f"build_callgraph: {f}:{line}: {caller} -> {called}")
89 cg.add_edge(caller, called, loc)
90 return cg
91
92
93 def print_edge(cg, caller, called, padding="", end="\n"):
94 locs = cg.edges[(caller, called)]
95 for (filename, line) in locs:
96 print(
97 f"{padding}{os.path.relpath(filename)}:{line}: {caller} -> {called}",
98 end=end,
99 )
100
101
102 def print_cg(cg):
103 for (caller, called) in cg.edges:
104 print_edge(cg, caller, called)
105
106
107 # note: out _must_ exist (the caller must create it if needed)
108 def print_cg_dot(cg, out=sys.stdout):
109 print("digraph callgraph {", file=out)
110 for (caller, called) in cg.edges:
111 print(f" {caller} -> {called};", file=out)
112 print("}", file=out)
113
114
115 # succs: dict, input, not modified
116 # visited: set, input-output, modified
117 # just_visited: set, input-output, modified
118 # n: input, not modified
119 #
120 # The difference between visited and just_visited is that the latter refers
121 # to the current bfs; nodes visited in previous bfs already had their cycles
122 # reported, so we do not report them multiple times.
123 def cycle_bfs(cg, visited, just_visited, n):
124 if debug:
125 print(f"cycle_bfs: visited = {visited}, just_visited = {just_visited}, n = {n}")
126 just_visited.add(n)
127 if n not in cg.succs:
128 return []
129 fifo = []
130 for succ in cg.succs[n]:
131 if succ in just_visited:
132 return [(n, succ)]
133 elif succ in visited:
134 # already reported in a previous iteration
135 continue
136 fifo.append(succ)
137 # no cycle found with direct successors, go to next level
138 for succ in fifo:
139 my_just_visited = just_visited.copy()
140 res = cycle_bfs(cg, visited, my_just_visited, succ)
141 if res:
142 # note that other cycles may not be reported
143 caller = res[0][0]
144 return [(n, caller)] + res
145 return []
146
147
148 def compute_recursive_cycles(cg, acc):
149 to_visit = set(cg.nodes())
150 if not to_visit: # empty graph -> no recursion
151 return
152 visited = set()
153 while to_visit:
154 just_visited = set()
155 n = sorted(list(to_visit))[0]
156 cycle = cycle_bfs(cg, visited, just_visited, n)
157 visited = visited.union(just_visited)
158 if cycle:
159 (fst, snd) = cycle[0]
160 cycle_start_loc = cg.edges[(fst, snd)][0]
161 acc.append((cycle_start_loc, cycle))
162 to_visit -= visited
163
164
165 def detect_recursion(cg):
166 to_visit = set(cg.nodes())
167 if not to_visit: # empty graph -> no recursion
168 return False
169 visited = set()
170 has_cycle = False
171 while to_visit:
172 just_visited = set()
173 n = sorted(list(to_visit))[0]
174 cycle = cycle_bfs(cg, visited, just_visited, n)
175 visited = visited.union(just_visited)
176 if cycle:
177 has_cycle = True
178 print("recursive cycle detected: ")
179 for (caller, called) in cycle:
180 print_edge(cg, caller, called, padding=" ")
181 to_visit -= visited
182 if not has_cycle:
183 print("no recursive calls detected")