| 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") |