Debian Codegraph @

libcextract/Closure.cpp

raw
1 //===- Closure.hh - Compute dependencies of a given symbol *- 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 /// Compute a set of Decls that is necessary to compile a given symbol.
11 //
12 //===----------------------------------------------------------------------===//
13
14 /* Author: Giuliano Belinassi */
15
16 #include "Closure.hh"
17
18 /** Add a decl to the Dependencies set and all its previous declarations in the
19 AST. A function can have multiple definitions but its body may only be
20 defined later. */
21 bool ClosureSet::Add_Decl_And_Prevs(Decl *decl)
22 {
23 bool inserted = false;
24
25 /* Do not insert builtin decls. */
26 if (Is_Builtin_Decl(decl)) {
27 return false;
28 }
29
30 while (decl) {
31 if (!Is_Decl_Marked(decl)) {
32 Dependencies.insert(decl);
33 inserted = true;
34 }
35
36 decl = decl->getPreviousDecl();
37 }
38 return inserted;
39 }
40
41 void DeclClosureVisitor::Compute_Closure_Of_Symbols(const std::vector<std::string> &names,
42 std::unordered_set<std::string> *matched_names)
43 {
44 /* FIXME: clang has a mechanism (DeclContext::lookup) which is SUPPOSED TO
45 return the list of all Decls that matches the lookup name. However, this
46 method doesn't work as intented. In kernel (see github issue #20) it
47 results in the lookup_result set not having the Decl that has the body of
48 the function, which is the most important!
49
50 Hence, do our own thing here. Create a set and sweep the top level decls,
51 analyzing the symbol that matches the name in the set. */
52
53 std::unordered_set<std::string> setof_names(std::make_move_iterator(names.begin()),
54 std::make_move_iterator(names.end()));
55
56 for (auto it = AST->top_level_begin(); it != AST->top_level_end(); ++it) {
57 NamedDecl *decl = dyn_cast<NamedDecl>(*it);
58
59 if (!decl) {
60 /* Decl does not have a name, thus skip it. */
61 continue;
62 }
63
64 const std::string &decl_name = decl->getName().str();
65 /* If the symbol name is in the set... */
66 if (setof_names.find(decl_name) != setof_names.end()) {
67 /* Mark that name as matched. */
68 if (matched_names)
69 matched_names->insert(decl_name);
70 /* Find its dependencies. */
71 TraverseDecl(decl);
72 }
73 }
74 }
75
76 /* ------ DeclClosureVisitor methods ------ */
77
78 #define TRY_TO(CALL_EXPR) \
79 if ((CALL_EXPR) == VISITOR_STOP) \
80 return VISITOR_STOP
81
82 #define DO_NOT_RUN_IF_ALREADY_ANALYZED(decl) \
83 if (Already_Analyzed(decl) == true) \
84 return VISITOR_CONTINUE
85
86 bool DeclClosureVisitor::TraverseDecl(Decl *decl)
87 {
88 DO_NOT_RUN_IF_ALREADY_ANALYZED(decl);
89 Mark_As_Analyzed(decl);
90 Stack.push_back(decl);
91 bool ret = RecursiveASTVisitor::TraverseDecl(decl);
92 Stack.pop_back();
93 return ret;
94 }
95
96 bool DeclClosureVisitor::VisitFunctionDecl(FunctionDecl *decl)
97 {
98 if (decl->getBuiltinID() != 0) {
99 /* Do not redeclare compiler builtin functions. */
100 return VISITOR_CONTINUE;
101 }
102
103 /* If this function is actually a template function specialization, then
104 look into it. */
105 if (FunctionTemplateSpecializationInfo *ftsi =
106 decl->getTemplateSpecializationInfo()) {
107 TRY_TO(VisitFunctionTemplateDecl(ftsi->getTemplate()));
108 }
109
110 /* Mark function for output. */
111 FunctionDecl *to_mark = decl;
112 if (decl->isStatic()) {
113 FunctionDecl *definition = decl->getDefinition();
114 /* FIXME: Declared static function in closure without a body? */
115 if (definition != nullptr) {
116 to_mark = definition;
117 /* Make sure we parse the function version with a body. */
118 TRY_TO(TraverseDecl(to_mark));
119 }
120 }
121
122 /* Check if the return type of the function is a complete struct
123 definition, which in this case clang seems to ignore. */
124 const clang::Type *ret_type = to_mark->getReturnType().getTypePtr();
125 if (ret_type->isRecordType()) {
126 if (TagDecl *tag = ret_type->getAsTagDecl()) {
127 tag->setCompleteDefinitionRequired(true);
128 }
129 }
130
131 Closure.Add_Single_Decl(to_mark);
132
133 /* Also analyze the previous version of this function to make sure we are
134 not losing the version with body. */
135 TRY_TO(AnalyzePreviousDecls(to_mark));
136
137 return VISITOR_CONTINUE;
138 }
139
140 bool DeclClosureVisitor::VisitDeclaratorDecl(DeclaratorDecl *decl)
141 {
142 /* There are some types in which we lose the the typedef reference, for
143 * example:
144 *
145 * typedef void (*XtErrorHandler)(char *);
146 * extern void XtSetErrorHandler(XtErrorHandler __attribute((noreturn)));
147 *
148 * The type dump for this is:
149 *
150 * FunctionProtoType 0x5210000720e0 'void (void (*)(char *) __attribute__((noreturn)))' cdecl
151 * |-BuiltinType 0x521000014170 'void'
152 * `-PointerType 0x521000071fd0 'void (*)(char *) __attribute__((noreturn))'
153 * `-ParenType 0x521000071f70 'void (char *) __attribute__((noreturn))' sugar
154 * `-FunctionProtoType 0x521000071f30 'void (char *) __attribute__((noreturn))' noreturn cdecl
155 * |-BuiltinType 0x521000014170 'void'
156 * `-PointerType 0x521000014d10 'char *'
157 * `-BuiltinType 0x5210000141b0 'char'
158 *
159 * Notice that there is no reference for XtErrorHandler. Somehow clang was
160 * not able to identify that XtErrorHandler __attribute((noreturn)) is a
161 * XtErrorHandler. OTOH, if we drop __attribute((noreturn)) we get:
162 *
163 * FunctionProtoType 0x521000071ff0 'void (XtErrorHandler)' cdecl
164 * |-BuiltinType 0x521000014170 'void'
165 * `-ElaboratedType 0x521000071f00 'XtErrorHandler' sugar
166 * `-TypedefType 0x521000071ed0 'XtErrorHandler' sugar
167 * |-Typedef 0x521000071e78 'XtErrorHandler'
168 * `-PointerType 0x521000071e10 'void (*)(char *)'
169 * `-ParenType 0x521000071db0 'void (char *)' sugar
170 * `-FunctionProtoType 0x521000071d70 'void (char *)' cdecl
171 * |-BuiltinType 0x521000014170 'void'
172 * `-PointerType 0x521000014d10 'char *'
173 * `-BuiltinType 0x5210000141b0 'char'
174 *
175 * which is correct. Hence we get the SourceText and try to match to any
176 * decl that is in the symbol table with that name.
177 */
178
179 SourceManager &sm = AST->getSourceManager();
180 const LangOptions &lo = AST->getLangOpts();
181
182 const TypeSourceInfo *typeinfo = decl->getTypeSourceInfo();
183 const TypeLoc &tl = typeinfo->getTypeLoc();
184
185 /* Get the range of the token which we expect is the type of it. */
186 SourceLocation tok_begin = Lexer::GetBeginningOfToken(tl.getBeginLoc(), sm, lo);
187 SourceLocation tok_end = Lexer::getLocForEndOfToken(tl.getBeginLoc(), 0, sm, lo);
188
189 StringRef text = PrettyPrint::Get_Source_Text({tok_begin, tok_end});
190
191 /* Lookup in the symbol table for any Decl matching it. */
192 DeclContextLookupResult decls = Get_Decl_From_Symtab(AST, text);
193 for (auto decl_it : decls) {
194 TRY_TO(TraverseDecl(decl_it));
195 }
196
197 /* Also analyze the decls that have the same beginloc, for declarations
198 comming from comma-separated. */
199 TRY_TO(AnalyzeDeclsWithSameBeginlocHelper(decl));
200
201 return VISITOR_CONTINUE;
202 }
203
204 bool DeclClosureVisitor::VisitValueDecl(ValueDecl *decl)
205 {
206 TRY_TO(TraverseType(decl->getType()));
207 return VISITOR_CONTINUE;
208 }
209
210 bool DeclClosureVisitor::VisitRecordDecl(RecordDecl *decl)
211 {
212 /* If this is a C++ record decl, then analyze it as such. */
213 if (CXXRecordDecl *cxxdecl = dyn_cast<CXXRecordDecl>(decl)) {
214 TRY_TO(VisitCXXRecordDecl(cxxdecl));
215 }
216
217 if (TypedefNameDecl *typedecl = decl->getTypedefNameForAnonDecl()) {
218 /* In case this struct is defined without a name, such as:
219 struct {
220 int a;
221 };
222
223 then do not add it to the output. This can happen in the case where the
224 original code was declared as:
225
226 typedef struct { int a; } A; */
227 return VisitTypedefNameDecl(typedecl);
228 }
229
230 TRY_TO(ParentRecordDeclHelper(decl));
231
232 Closure.Add_Single_Decl(decl);
233 /* Also analyze the previous version of this decl for any version of it
234 that is nested-declared inside another record. */
235 TRY_TO(AnalyzePreviousDecls(decl));
236
237 return VISITOR_CONTINUE;
238 }
239
240 bool DeclClosureVisitor::VisitEnumDecl(EnumDecl *decl)
241 {
242 if (TypedefNameDecl *typedecl = decl->getTypedefNameForAnonDecl()) {
243 /* In case this enum is defined without a name, such as:
244 enum {
245 CONSTANT = 1,
246 };
247
248 then do not add it to the output. This can happen in the case where the
249 original code was declared as:
250
251 typedef enum { CONSTANT = 1 } A; */
252 return VisitTypedefNameDecl(typedecl);
253 }
254
255 TRY_TO(ParentRecordDeclHelper(decl));
256 Closure.Add_Single_Decl(decl);
257
258 /* Also analyze the previous version of this decl for any version of it
259 that is nested-declared inside another record. */
260 TRY_TO(AnalyzePreviousDecls(decl));
261
262 return VISITOR_CONTINUE;
263 }
264
265 bool DeclClosureVisitor::VisitTagDecl(TagDecl *decl)
266 {
267 DeclContext *parent = decl->getParent();
268 if (parent && parent->hasValidDeclKind()) {
269 /* Check if parent declaration is a namespace. If yes, then add it
270 as well BUT DO NOT add its children. */
271 if (parent->isNamespace()) {
272 NamespaceDecl *nm = cast<NamespaceDecl>(parent);
273 TRY_TO(VisitNamespaceDecl(nm));
274 }
275 }
276
277 return VISITOR_CONTINUE;
278 }
279
280 bool DeclClosureVisitor::VisitEnumConstantDecl(EnumConstantDecl *decl)
281 {
282 /* Add original EnumDecl it originated. */
283 EnumDecl *enum_decl = dyn_cast<EnumDecl>(decl->getLexicalDeclContext());
284 if (enum_decl) {
285 return TraverseDecl(enum_decl);
286 }
287
288 return VISITOR_CONTINUE;
289 }
290
291 /* Not called automatically by Transverse. */
292 bool DeclClosureVisitor::VisitTypedefNameDecl(TypedefNameDecl *decl)
293 {
294 // FIXME: Do we need to analyze the previous decls?
295 TRY_TO(TraverseType(decl->getUnderlyingType()));
296 Closure.Add_Single_Decl(decl);
297
298 TRY_TO(AnalyzeDeclsWithSameBeginlocHelper(decl));
299
300 return VISITOR_CONTINUE;
301 }
302
303 bool DeclClosureVisitor::VisitVarDecl(VarDecl *decl)
304 {
305 /* Avoid adding variables that are not global. */
306 // FIXME: Do we need to analyze every previous decl?
307 if (decl->hasGlobalStorage()) {
308 Closure.Add_Single_Decl(decl);
309 }
310
311 return VISITOR_CONTINUE;
312 }
313
314 bool DeclClosureVisitor::VisitFunctionTemplateDecl(FunctionTemplateDecl *decl)
315 {
316 Closure.Add_Decl_And_Prevs(decl);
317
318 return VISITOR_CONTINUE;
319 }
320
321 bool DeclClosureVisitor::VisitTemplateDecl(TemplateDecl *decl)
322 {
323 Closure.Add_Decl_And_Prevs(decl);
324
325 return VISITOR_CONTINUE;
326 }
327
328 bool DeclClosureVisitor::VisitNamespaceDecl(NamespaceDecl *decl)
329 {
330 Closure.Add_Decl_And_Prevs(decl);
331
332 return VISITOR_CONTINUE;
333 }
334
335 bool DeclClosureVisitor::VisitCXXRecordDecl(CXXRecordDecl *decl)
336 {
337 /* In case this is a ClassTemplateSpecialDecl, then analyze it as such. */
338 if (ClassTemplateSpecializationDecl *ctsd =
339 dyn_cast<ClassTemplateSpecializationDecl>(decl)) {
340 TRY_TO(VisitClassTemplateSpecializationDecl(ctsd));
341 }
342
343 Closure.Add_Decl_And_Prevs(decl);
344
345 return VISITOR_CONTINUE;
346 }
347
348 bool DeclClosureVisitor::VisitClassTemplateDecl(ClassTemplateDecl *decl)
349 {
350 Closure.Add_Decl_And_Prevs(decl);
351
352 return VISITOR_CONTINUE;
353 }
354
355 bool DeclClosureVisitor::VisitClassTemplateSpecializationDecl(
356 ClassTemplateSpecializationDecl *decl)
357 {
358 /* Assume
359 template<T>
360 class V{
361 T x;
362 };
363 struct A {int x; }
364
365 V<A> u;
366 This call will add the A to the closure. */
367 TRY_TO(TraverseTemplateArguments(decl->getTemplateArgs().asArray()));
368
369 /* This call will add the V to the closure. */
370 return VisitClassTemplateDecl(decl->getSpecializedTemplate());
371 }
372
373 /* ----------- Statements -------------- */
374
375 bool DeclClosureVisitor::VisitDeclRefExpr(DeclRefExpr *expr)
376 {
377 TRY_TO(TraverseDecl(expr->getDecl()));
378 /* For C++ we also need to analyze the name specifier. */
379 if (NestedNameSpecifier *nns = expr->getQualifier()) {
380 TRY_TO(TraverseNestedNameSpecifier(nns));
381 }
382
383 /* Analyze the decl it references to. */
384 return TraverseDecl(expr->getDecl());
385 }
386
387 bool DeclClosureVisitor::VisitOffsetOfExpr(OffsetOfExpr *expr)
388 {
389 /* Handle the following case:
390 *
391 * typedef struct {
392 * int x;
393 * int y;
394 * } Head;
395 *
396 * int x = __builtin_offsetof(Head, y);
397 */
398 unsigned num_components = expr->getNumComponents();
399 for (unsigned i = 0; i < num_components; i++) {
400 /* Get the RecordDecl referenced in the builtin_offsetof and add to the
401 dependency list. */
402 const OffsetOfNode &component = expr->getComponent(i);
403 if (component.getKind() == OffsetOfNode::Field) {
404 const FieldDecl *field = component.getField();
405
406 RecordDecl *record = (RecordDecl *)field->getParent();
407 TRY_TO(TraverseDecl(record));
408 }
409 }
410
411 return VISITOR_CONTINUE;
412 }
413
414 bool DeclClosureVisitor::VisitConvertVectorExpr(const ConvertVectorExpr *expr)
415 {
416 const TypeSourceInfo *tsi = expr->getTypeSourceInfo();
417 TRY_TO(TraverseTypeLoc(tsi->getTypeLoc()));
418
419 return VISITOR_CONTINUE;
420 }
421
422 bool DeclClosureVisitor::VisitUnaryOperator(const UnaryOperator *expr)
423 {
424 /* Fix cases where a copy of a struct is necessary but
425 * CompleteDefinitionRequired is somehow set to false by clang itself.
426 * see small/record-9.c for an example.
427 */
428 const clang::Type *type = expr->getType().getTypePtr();
429 if (TagDecl *tag = type->getAsTagDecl()) {
430 tag->setCompleteDefinitionRequired(true);
431 }
432
433 return VISITOR_CONTINUE;
434 }
435
436 /* --------- Attributes ----------- */
437
438 bool DeclClosureVisitor::VisitCleanupAttr(const CleanupAttr *attr)
439 {
440 TRY_TO(TraverseDecl(attr->getFunctionDecl()));
441 return VISITOR_CONTINUE;
442 }
443
444 /* -------- Types ----------------- */
445
446 bool DeclClosureVisitor::VisitTagType(const TagType *type)
447 {
448 TRY_TO(TraverseDecl(type->getDecl()));
449 return VISITOR_CONTINUE;
450 }
451
452 bool DeclClosureVisitor::VisitTypedefType(const TypedefType *type)
453 {
454 TRY_TO(TraverseDecl(type->getDecl()));
455 return VISITOR_CONTINUE;
456 }
457
458 /* -------- C++ Types ------------- */
459
460 bool DeclClosureVisitor::VisitTemplateSpecializationType(
461 const TemplateSpecializationType *type)
462 {
463 /* For some reason the Traverse do not run on the original template
464 C++ Record, only on its specializations. Hence do it here. */
465 return TraverseDecl(type->getAsCXXRecordDecl());
466 }
467
468 bool DeclClosureVisitor::VisitDeducedTemplateSpecializationType(
469 const DeducedTemplateSpecializationType *type)
470 {
471 TemplateName template_name = type->getTemplateName();
472 return TraverseDecl(template_name.getAsTemplateDecl());
473 }
474
475 /* ----------- Other C++ stuff ----------- */
476
477 bool DeclClosureVisitor::TraverseNestedNameSpecifier(NestedNameSpecifier *nns)
478 {
479 switch (nns->getKind()) {
480 case NestedNameSpecifier::Namespace:
481 /* Do not traverse to avoid adding unecessary childs. */
482 TRY_TO(VisitNamespaceDecl(nns->getAsNamespace()));
483 break;
484 case NestedNameSpecifier::NamespaceAlias:
485 TRY_TO(TraverseDecl(nns->getAsNamespaceAlias()));
486 break;
487
488 case NestedNameSpecifier::Super:
489 /* Something regarding MSVC, but lets put this here. */
490 TRY_TO(TraverseDecl(nns->getAsRecordDecl()));
491 break;
492
493 default:
494 break;
495 }
496 return RecursiveASTVisitor::TraverseNestedNameSpecifier(nns);
497 }
498
499 bool DeclClosureVisitor::TraverseCXXBaseSpecifier(const CXXBaseSpecifier base)
500 {
501 TRY_TO(TraverseType(base.getType()));
502 return RecursiveASTVisitor::TraverseCXXBaseSpecifier(base);
503 }
504
505 /* ------ Helper Functions ------ */
506
507 bool DeclClosureVisitor::ParentRecordDeclHelper(TagDecl *decl)
508 {
509 /* In case this references a struct/union defined inside a struct (nested
510 struct), then we also need to analyze the parent struct. */
511 RecordDecl *parent = dyn_cast<RecordDecl>(decl->getLexicalDeclContext());
512 Decl *analysis_parent = nullptr;
513
514 /* Check if we are not coming from an analysis from the RecordDecl, i.e. from
515 a stack perspective the Decl that is at the bottom of the Decl. */
516 if (Stack.size() >= 2) {
517 analysis_parent = Stack[Stack.size() - 2];
518 }
519
520 if (parent && analysis_parent != parent) {
521 /* If the parent struct is flagged as not needing a complete definition
522 then we need to set it to true, else the nested struct won't be
523 output as of only a partial definition of the parent struct is
524 output. */
525 parent->setCompleteDefinitionRequired(true);
526
527 /* Analyze parent struct. */
528 TRY_TO(TraverseDecl(parent));
529 }
530
531 return VISITOR_CONTINUE;
532 }
533
534 bool DeclClosureVisitor::AnalyzeDeclsWithSameBeginlocHelper(Decl *decl)
535 {
536 SourceManager &SM = AST->getSourceManager();
537 ArrayRef<Decl *> decls = Get_Toplev_Decls_With_Same_Beginloc(AST,
538 SM.getExpansionLoc(decl->getBeginLoc()));
539
540 for (auto it = decls.begin(); it != decls.end(); ++it) {
541 TRY_TO(TraverseDecl(*it));
542 }
543
544 return VISITOR_CONTINUE;
545 }
546
547 bool DeclClosureVisitor::AnalyzePreviousDecls(Decl *decl)
548 {
549 Decl *prev = decl->getPreviousDecl();
550 while (prev) {
551 TRY_TO(TraverseDecl(prev));
552 Closure.Add_Single_Decl(prev);
553 prev = prev->getPreviousDecl();
554 }
555
556 return VISITOR_CONTINUE;
557 }