Debian Codegraph @

libcextract/FunctionDepsFinder.cpp

raw
1 //===- ExpansionPolicy.cpp - Construct Closure of Symbols --- *- C++ -*-===//
2 //
3 // This project is licensed under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file
10 /// Implements the closure algorithm for symbols.
11 //
12 //===----------------------------------------------------------------------===//
13
14 /* Author: Giuliano Belinassi */
15
16 #include <sstream>
17 #include <vector>
18 #include "FunctionDepsFinder.hh"
19 #include "ClangCompat.hh"
20 #include "PrettyPrint.hh"
21 #include "Error.hh"
22 #include "LLVMMisc.hh"
23
24 /** FunctionDependencyFinder class methods implementation. */
25 FunctionDependencyFinder::FunctionDependencyFinder(PassManager::Context *ctx)
26 : AST(ctx->AST.get()),
27 IT(AST, ctx->IncExpansionPolicy, ctx->HeadersToExpand, ctx->HeadersToNotExpand),
28 KeepIncludes(ctx->KeepIncludes),
29 Visitor(AST)
30 {
31 }
32
33 bool FunctionDependencyFinder::Find_Functions_Required(
34 std::vector<std::string> const &funcnames)
35 {
36 std::unordered_set<std::string> matched_names;
37 Visitor.Compute_Closure_Of_Symbols(funcnames, &matched_names);
38
39 /* Find which names did not match any declaration name. */
40 for (const std::string &funcname : funcnames) {
41 if (matched_names.find(funcname) == matched_names.end()) {
42 DiagsClass::Emit_Error("Requested symbol not found: " + funcname);
43 return false;
44 }
45 }
46
47 return true;
48 }
49
50 void FunctionDependencyFinder::Print(void)
51 {
52 ClosureSet &closure = Visitor.Get_Closure();
53 RecursivePrint(AST, closure.Get_Set(), IT, KeepIncludes).Print();
54 }
55
56 void FunctionDependencyFinder::Remove_Redundant_Decls(void)
57 {
58 ClosureSet &closure = Visitor.Get_Closure();
59 std::unordered_set<Decl *> &closure_set = closure.Get_Set();
60 bool inc;
61
62 for (auto it = closure_set.begin(); it != closure_set.end(); inc ? ++it : it) {
63 inc = true;
64 /* Handle the case where a enum or struct is declared as:
65
66 typedef enum Hand {
67 LEFT,
68 RIGHT
69 } Hand;
70
71 which is then broken as
72
73 enum Hand {
74 LEFT,
75 RIGHT
76 };
77
78 typedef enum Hand Hand;
79
80 but when printing, we track the typedef declaration to what the user
81 wrote and it will be transformed into
82
83 enum Hand {
84 LEFT,
85 RIGHT
86 };
87
88 typedef enum Hand {
89 LEFT,
90 RIGHT
91 } Hand;
92
93 which is a redeclaration of enum Hand. Hence we have to remove the
94 first `enum Hand` from the closure. See typedef-7.c testcase. */
95 if (TypedefDecl *decl = dyn_cast<TypedefDecl>(*it)) {
96 SourceRange range = decl->getSourceRange();
97
98 const clang::Type *type = decl->getTypeForDecl();
99 if (type) {
100 /* We must be careful with pointers, the user can define things like:
101 *
102 * typedef struct _fakestr {
103 * struct _fakestr *pNext;
104 * int type;
105 * } FAKE, *PFAKE;
106 *
107 * which in this case PFAKE is a pointer and we need to deference it
108 * to reach _fakestr.
109 */
110 while (type->isPointerType()) {
111 type = type->getPointeeOrArrayElementType();
112 }
113
114 TagDecl *typedecl = type->getAsTagDecl();
115
116 if (typedecl && closure.Is_Decl_Marked(typedecl)) {
117 SourceRange type_range = typedecl->getSourceRange();
118
119 /* Check if the strings regarding an decl empty. In that case we
120 can not delete the decl from list. */
121 if (PrettyPrint::Get_Source_Text(range) != "" &&
122 PrettyPrint::Get_Source_Text(type_range) != "") {
123
124 /* Using .fullyContains() fails in some declarations. */
125 if (PrettyPrint::Contains_From_LineCol(range, type_range)) {
126 closure.Remove_Decl(typedecl);
127 }
128 }
129 }
130 }
131 }
132 /* Handle the case where an enum is declared as:
133 extern enum system_states {
134 SYSTEM_BOOTING,
135 SYSTEM_SCHEDULING,
136 SYSTEM_FREEING_INITMEM,
137 SYSTEM_RUNNING,
138 SYSTEM_HALT,
139 SYSTEM_POWER_OFF,
140 SYSTEM_RESTART,
141 SYSTEM_SUSPEND,
142 } system_state;
143
144 In which will be broken down into:
145
146 enum system_states {
147 ...
148 };
149
150 enum system_states system_state;
151
152 this will remove the first enum declaration because the location
153 tracking will correctly include the enum system_states. */
154
155 else if (DeclaratorDecl *decl = dyn_cast<DeclaratorDecl>(*it)) {
156 SourceRange range = decl->getSourceRange();
157
158 const clang::Type *type = ClangCompat::getTypePtr(decl->getType());
159 /* There are some cases where a variable is declared as follows:
160
161 static const struct mount_opts
162 {
163 int token;
164 int mount_opts;
165 int flags;
166 } ext4_mount_opts[] = {
167 {1, 1, 1}
168 };
169
170 in this case, the `ext4_mount_opts` array is declared together with its
171 type, thus resulting in Clang splitting this into two decls in its AST:
172
173 struct mount_opts
174 {
175 int token;
176 int mount_opts;
177 int flags;
178 };
179
180 static const struct ext4_mount_opts[] = {
181 {1, 1, 1}
182 };
183
184 but since we try to get what the user wrote, it results in two declarations
185 of `struct mount_opts`, thus clang-extract fails because of a redeclaration
186 error. But since `ext4_mount_opts` is an array, geting its type returns
187 an array type, not the struct declaration itself, hence check for this
188 case as well. */
189 if (type->isArrayType() || type->isPointerType()) {
190 type = type->getBaseElementTypeUnsafe();
191 }
192
193 TagDecl *typedecl = type ? type->getAsTagDecl() : nullptr;
194 if (typedecl && closure.Is_Decl_Marked(typedecl)) {
195 SourceRange type_range = typedecl->getSourceRange();
196
197 /* Using .fullyContains() fails in some declarations. */
198 if (PrettyPrint::Contains_From_LineCol(range, type_range)) {
199 closure.Remove_Decl(typedecl);
200 }
201 }
202 }
203
204 /* Try to remove any decls in the main file which are
205 redundant, which means that have equivalent previous decl. */
206 Decl *decl = *it;
207
208 if (AST->isInMainFileID(decl->getBeginLoc()) &&
209 AST->isInMainFileID(decl->getEndLoc())) {
210
211 for (Decl *prev = decl->getPreviousDecl();
212 prev != nullptr;
213 prev = prev->getPreviousDecl()) {
214 if (closure.Is_Decl_Marked(prev) && Is_Decl_Equivalent_To(decl, prev)) {
215 ++it;
216 inc = false;
217 closure.Remove_Decl(decl);
218 break;
219 }
220 }
221 }
222 }
223
224 ASTUnit::top_level_iterator it;
225 Decl *prev = nullptr;
226 for (it = AST->top_level_begin(); it != AST->top_level_end(); ++it) {
227 Decl *decl = *it;
228 if (isa<TypedefDecl>(decl) || isa<DeclaratorDecl>(decl) || isa<TagDecl>(decl)) {
229 if (!closure.Is_Decl_Marked(decl))
230 continue;
231
232 // Set prev and exit, since we don't have anything to compare agains't
233 if (!prev) {
234 prev = decl;
235 continue;
236 }
237
238 /*
239 * Check if there wasn't any symbol that is being defined in the same
240 * interval and remove it. Otherwise we might clash the types.
241 *
242 * One example of how this can happen is then we have something like
243 *
244 * typedef struct {
245 * ...
246 * } x, y;
247 *
248 * In the process of creating the closure we might reach the following
249 * situation:
250 *
251 * typdef struct {
252 * ...
253 * } x;
254 *
255 * typedef struct {
256 *
257 * } x, y;
258 *
259 * Which then breaks the one-definition-rule. In such cases, remove the
260 * previous declaration in the same code range, since the later will
261 * contain both definitions either way.
262 *
263 * Also be careful to make sure those declarations will be print as
264 * based on the source text and not in AST dump. In the later case
265 * we don't want to remove it.
266 */
267 if (PrettyPrint::Get_Source_Text(decl->getSourceRange()) != "" &&
268 PrettyPrint::Get_Source_Text(prev->getSourceRange()) != "" &&
269 PrettyPrint::Contains_From_LineCol(decl->getSourceRange(),
270 prev->getSourceRange())) {
271 /*
272 * If the prev and the current decl have the same start LoC, but
273 * different ending, remove the prev from the closure and set the
274 * new prev.
275 */
276 closure.Remove_Decl(prev);
277 }
278
279 prev = decl;
280 }
281 }
282 }
283
284 void FunctionDependencyFinder::Insert_Decls_From_Non_Expanded_Includes(void)
285 {
286 ASTUnit::top_level_iterator it;
287 for (it = AST->top_level_begin(); it != AST->top_level_end(); ++it) {
288 Decl *decl = *it;
289
290 const SourceLocation &loc = decl->getLocation();
291 IncludeNode *node = IT.Get(loc);
292
293 if (node && node->Has_Parent_Marked_For_Output()) {
294 Visitor.TraverseDecl(decl);
295 }
296 }
297 }
298
299 bool FunctionDependencyFinder::Run_Analysis(std::vector<std::string> const &functions)
300 {
301 bool ret = true;
302 /* Step 1: Compute the closure. */
303 ret &= Find_Functions_Required(functions);
304
305 /* Step 2: Expand the closure to include Decls in non-expanded includes. */
306 if (KeepIncludes) {
307 /* TODO: Guarding this with KeepIncludes should actually not be necessary,
308 but we still have bugs when processing the kernel and the closure is not
309 perfect. By not adding those declarations we avoid hitting cases where
310 it would hang because of a declaration that would be removed in the
311 future anyway. It also speeds up analysis considerably when the user do
312 not want to keep the includes. */
313 Insert_Decls_From_Non_Expanded_Includes();
314 }
315
316 /* Step 3: Remove any declaration that may have been declared twice. This
317 is required because of the `enum-5.c` testcase (struct declared inside
318 a typedef). */
319 Remove_Redundant_Decls();
320
321 return ret;
322 }