Debian Codegraph @

share/analysis-scripts/function_finder.py

raw
1 # -*- coding: utf-8 -*-
2 ##########################################################################
3 # #
4 # This file is part of Frama-C. #
5 # #
6 # Copyright (C) 2007-2021 #
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 """Exports find_function_in_file, to be used by other scripts"""
25
26 import bisect
27 import os
28 import re
29
30 # To minimize the amount of false positives, we try to match the following:
31 # - the line must begin with a C identifier (declarations and definitions in C
32 # rarely start with spaces in the line), or with the function name itself
33 # (supposing the return type is in the previous line)
34 # - any number of identifiers are allowed (to allow for 'struct', 'volatile',
35 # 'extern', etc)
36 # - asterisks are allowed both before and after identifiers, except for the
37 # first one (to allow for 'char *', 'struct **ptr', etc)
38 # - identifiers are allowed after the parentheses, to allow for some macros/
39 # modifiers
40
41 # auxiliary regexes
42 c_identifier = "[a-zA-Z_][a-zA-Z0-9_]*"
43 c_id_maybe_pointer = c_identifier + "[*]*"
44 optional_c_id = "(?:" + c_identifier + ")?"
45 non_empty_whitespace = r"[ \t\r\n]+" # includes newline/CR
46 whitespace = "[ \t\r\n]*" # includes newline/CR
47 type_prefix = (
48 c_id_maybe_pointer + r"(?:\s+[*]*" + c_id_maybe_pointer + ")*" + non_empty_whitespace + "[*]*"
49 )
50 optional_type_prefix = "(?:" + type_prefix + whitespace + ")?"
51 argument_list = r"\([^)]*\)"
52
53 debug = os.getenv("DEBUG", False)
54
55 # Precomputes the regex for 'fname'
56 def prepare_re_specific_name(fname):
57 re_fun = re.compile(
58 "^"
59 + optional_type_prefix
60 + fname
61 + whitespace
62 + argument_list
63 + whitespace
64 + optional_c_id
65 + whitespace
66 + "(;|{)",
67 flags=re.DOTALL | re.MULTILINE,
68 )
69 return re_fun
70
71
72 # Returns 0 if not found, 1 if declaration, 2 if definition
73 def find_specific_name(prepared_re, f):
74 with open(f, encoding="ascii", errors="ignore") as data:
75 file_content = data.read()
76 has_decl_or_def = prepared_re.search(file_content)
77 if has_decl_or_def is None:
78 return 0
79 else:
80 is_decl = has_decl_or_def.group(1) == ";"
81 return 1 if is_decl else 2
82
83
84 # matches function definitions or declarations
85 # if funcname is not None, only matches for the specified
86 # function name
87 def compute_re_def_or_decl(funcname):
88 ident = funcname if funcname else c_identifier
89 return re.compile(
90 "^"
91 + optional_type_prefix
92 + "("
93 + ident
94 + ")"
95 + whitespace
96 + argument_list
97 + whitespace
98 + optional_c_id
99 + whitespace
100 + "(;|{)",
101 flags=re.DOTALL | re.MULTILINE,
102 )
103
104
105 # matches function calls
106 re_funcall = re.compile("(" + c_identifier + ")" + whitespace + r"\(")
107
108 # Computes the offset (in bytes) of each '\n' in the file,
109 # returning them as a list
110 def compute_newline_offsets(file_lines):
111 offsets = []
112 current = 0
113 for line in file_lines:
114 current += len(line)
115 offsets.append(current)
116 return offsets
117
118
119 # Returns the line number (starting at 1) containing the character
120 # of offset [offset].
121 # [offsets] is the sorted list of offsets for newline characters in the file.
122 def line_of_offset(offsets, offset):
123 return bisect.bisect_right(offsets, offset) + 1
124
125
126 # Returns the line number (starting at 1) of each line starting with '}'
127 # as its first character.
128 #
129 # This is a heuristic to attempt to detect function closing braces:
130 # it assumes that the first '}' (without preceding whitespace) after a
131 # function definition denotes its closing brace.
132 def compute_closing_braces(file_lines):
133 braces = []
134 for i, line in enumerate(file_lines, start=1):
135 # note: lines contain '\n', so they are never empty
136 if line[0] == "}":
137 braces.append(i)
138 # Special heuristics: if the last line contains whitespace + '}',
139 # assume it closes a function.
140 last_line_number = len(file_lines) + 1
141 if file_lines != [] and last_line_number not in braces:
142 last_line = file_lines[-1].lstrip()
143 if len(last_line) >= 1 and last_line[0] == "}":
144 braces.append(last_line_number)
145 return braces
146
147
148 # Returns the first element of [line_numbers] greater than [n], or [None]
149 # if all numbers are smaller than [n] (this may happen e.g. when no
150 # closing braces were found).
151 #
152 # [line_numbers] must be sorted in ascending order.
153 def get_first_line_after(line_numbers, n):
154 try:
155 return line_numbers[bisect.bisect_left(line_numbers, n)]
156 except IndexError:
157 # could not find line (e.g. for closing braces); return None
158 return None
159
160
161 # Returns a list of tuples (fname, is_def, line_start, line_end, terminator_offset)
162 # for each function definition or declaration.
163 # If [want_defs] is True, definitions are included.
164 # If [want_decls] is True, declarations are included.
165 # [terminator_offset] is the byte offset of the `{` or `;`.
166 # The list is sorted w.r.t. line numbers (in ascending order).
167 #
168 # [terminator_offset] is used by the caller to filter the function prototype
169 # itself and avoid considering it as a call. For function definitions,
170 # this is the opening brace; for function declarations, this is the semicolon.
171 def find_definitions_and_declarations(
172 want_defs, want_decls, filename, file_content, file_lines, newlines, funcname=None
173 ):
174 braces = compute_closing_braces(file_lines)
175 res = []
176 re_fundef_or_decl = compute_re_def_or_decl(funcname)
177 for match in re.finditer(re_fundef_or_decl, file_content):
178 funcname = match.group(1)
179 terminator = match.group(2)
180 terminator_offset = match.start(2)
181 is_def = terminator == "{"
182 is_decl = terminator == ";"
183 assert is_def or is_decl
184 start = line_of_offset(newlines, match.start(1))
185 if is_decl:
186 if not want_decls:
187 continue
188 end = line_of_offset(newlines, terminator_offset)
189 else:
190 if not want_defs:
191 continue
192 definition = file_content[match.start(1) : newlines[start - 1]]
193 # try "single-line function heuristic":
194 # assume the function is defined as 'type f(...) { code; }',
195 # in a single line
196 if definition.strip().endswith("}"):
197 end = line_of_offset(newlines, terminator_offset)
198 else:
199 end = get_first_line_after(braces, start)
200 if not end:
201 # no closing braces found; try again the "single-line function heuristic"
202 line_of_opening_brace = line_of_offset(newlines, terminator_offset)
203 if start == line_of_opening_brace and definition.rstrip()[-1] == "}":
204 # assume the '}' is closing the '{' from the same line
205 end = line_of_opening_brace
206 else:
207 # no opening brace; assume a false positive and skip definition
208 print(
209 f"{os.path.relpath(filename)}:{start}:closing brace not found, "
210 f"skipping potential definition of '{funcname}'"
211 )
212 continue
213 if debug:
214 print(
215 f"function_finder: {'def' if is_def else 'decl'} of "
216 f"{funcname} between {start} and {end}"
217 )
218 res.append((funcname, is_def, start, end, terminator_offset))
219 return res
220
221
222 # list of identifiers which are never function calls
223 calls_blacklist = ["if", "while", "for", "return", "sizeof", "switch", "_Alignas"]
224
225 # Returns a list of tuples (fname, line, offset) for each function call.
226 #
227 # Note: this may include the function prototype itself;
228 # it must be filtered by the caller.
229 def find_calls(file_content, newlines):
230 # create a list of Match objects that fit "pattern" regex
231 res = []
232 for match in re.finditer(re_funcall, file_content):
233 funcname = match.group(1)
234 offset = match.start(1)
235 line = line_of_offset(newlines, offset)
236 if funcname not in calls_blacklist:
237 res.append((funcname, line, offset))
238 return res
239
240
241 # Returns the caller of [call], that is, the function whose definition
242 # contains the line where [call] happens.
243 # Returns [None] if there is no function at such line (i.e. a false positive).
244 #
245 # [defs] must be sorted in ascending order.
246 def find_caller(defs, call):
247 (_called, line, offset) = call
248 for (fname, _is_def, start, end, brace_offset) in defs:
249 if start <= line <= end and offset > brace_offset:
250 return fname
251 elif start > line:
252 return None
253 return None