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