Debian Codegraph @

libcextract/IncludeTree.cpp

raw
1 //===- IncludeTree.cpp - Tree of #include'd files -------------- *- 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 /// Tree of #include'd files.
11 //
12 //===----------------------------------------------------------------------===//
13
14 /* Author: Giuliano Belinassi */
15
16 #include "IncludeTree.hh"
17 #include "PrettyPrint.hh"
18 #include "ClangCompat.hh"
19 #include "Error.hh"
20
21 #include <stack>
22 #include <string>
23 #include <algorithm>
24
25 static bool In_Set(std::unordered_set<std::string> &set, const std::string &str,
26 bool remove_if_exists)
27 {
28 if (set.find(str) != set.end()) {
29 if (remove_if_exists) {
30 set.erase(str);
31 }
32 return true;
33 }
34
35 return false;
36 }
37
38 static bool In_Set(std::unordered_set<std::string> &set, const StringRef &str,
39 bool remove_if_exists)
40 {
41 return In_Set(set, str.str(), remove_if_exists);
42 }
43
44 /* ----- IncludeTree ------ */
45 IncludeTree::IncludeTree(Preprocessor &pp,
46 SourceManager &sm,
47 IncludeExpansionPolicy::Policy p,
48 std::vector<std::string> const &must_expand,
49 std::vector<std::string> const &must_not_expand)
50 : PP(pp),
51 SM(sm),
52 IEP(IncludeExpansionPolicy::Get_Expansion_Policy_Unique(p))
53 {
54 /* First step: create the barebones IncludeTree structure. If a node is
55 set to expansion, or not expansion, or can't be output because it is
56 unreachable from the main file, it is flagged here. */
57 Build_Header_Tree(must_expand, must_not_expand);
58
59 /* Second step: propagate the ShouldBeExpanded flag upwards on the tree,
60 which means sweeping through the tree post-order transversal to
61 propagate that flag upward. */
62 Set_Expansion_Attrs(Root);
63
64 /* Third step: now set and propagate the "ShouldBeOutput flag downards the
65 tree, iterating it using pre-order transversal. In the case a header
66 attempts to be set to be output but it would violate the
67 ShouldNotBeOutput flag, then it set the node for expansion and try
68 to set its children for output. */
69 Set_Output_Attrs();
70
71 /* Forth step: for headers that must NOT be expanded, we cut it from the
72 tree, which means we cancel out the 'expansion' flag even if the user
73 requested. In case the header cannot be set to output, we error out. */
74 Cut_Non_Expandable_Trees(Root, false);
75
76 /* Create a hash of FileEntry => IncludeNode for fast lookup. */
77 Build_Header_Map();
78 }
79
80 IncludeTree::~IncludeTree(void)
81 {
82 delete Root;
83 Root = nullptr;
84 }
85
86 void IncludeTree::Build_Header_Tree(std::vector<std::string> const &must_expand,
87 std::vector<std::string> const &must_not_expand)
88 {
89 /* Construct the IncludeTree. The algorithm works as follows:
90
91 Push the compiling file to the top of the stack.
92 1. Analyze the PreprocessingRecord in sequence for includes.
93 2. We wait for the first include comming from the main file. In
94 case there are -include commands in compilation, the origin file
95 will come as invalid and we need to be careful with this later.
96 3. Once we find an include, we check to see in which file this was
97 written, and rewind the stack until we find this file. This is
98 because the includes are parsed in a DFS fashion, hence the stack.
99 4. Add the found include as a child and update its parent. */
100
101
102 std::unordered_set<std::string> must_expand_set(must_expand.begin(),
103 must_expand.end());
104 std::unordered_set<std::string> must_not_expand_set(must_not_expand.begin(),
105 must_not_expand.end());
106
107 MacroWalker mw(PP);
108 bool already_seen_main = false;
109 OptionalFileEntryRef main = SM.getFileEntryRefForID(SM.getMainFileID());
110
111 std::stack<IncludeNode *> stack;
112 Root = new IncludeNode(this);
113
114 PreprocessingRecord *rec = PP.getPreprocessingRecord();
115 for (PreprocessedEntity *entity : *rec) {
116 if (InclusionDirective *id = dyn_cast<InclusionDirective>(entity)) {
117
118 /* In which file this include was written? */
119 SourceRange range = id->getSourceRange();
120 OptionalFileEntryRef this_file = PrettyPrint::Get_FileEntry(range.getBegin());
121
122 /* This is very confusing, but that is how clang handle things.
123 -include HEADER can be passed as a command line argument to clang. in
124 this case, the header do not come from a valid source location and
125 hence the `this_file` object will come without a value. Hence every
126 time we find such case we must discard the stack because we are
127 processing a new file.
128
129 However, when we find the main file this kind of analysis is not
130 needed anymore. But now we must have a way to check if the node on top
131 of the stack is the main file. Hence we create a node representing
132 the main file. */
133
134 if (!already_seen_main) {
135 if (!this_file.has_value()) {
136 // Discard stack and push root.
137 stack = std::stack<IncludeNode *>();
138 stack.push(Root);
139 } else if (this_file.has_value() && *this_file == *main) {
140 // Set the root FileEntry to the main file now.
141 Root->Set_FileEntry(main);
142
143 stack = std::stack<IncludeNode *>();
144 stack.push(Root);
145 already_seen_main = true;
146 }
147 }
148
149 /* Pop the stack until we find which HeaderNode we currently are. */
150 IncludeNode *current = stack.top();
151 while (!current->Is_Same_File(this_file)) {
152 stack.pop();
153 current = stack.top();
154 }
155
156 /* Check if the user or SymbolExternalizer requested a specific header to be
157 expanded. */
158 bool expand = In_Set(must_expand_set, id->getFileName(), /*remove=*/true) ||
159 In_Set(must_expand_set, id->getFile()->getName(), /*remove=*/true);
160
161 /* Starting from LLVM-18 and in some platforms (s390x), the behaviour of
162 * FileEntry::getName() changed. Now it returns the full path of the file
163 * rather than the relative path to it, so here we account it for now onwards.
164 */
165 expand |= In_Set(must_expand_set,
166 id->getFile()->getFileEntry().tryGetRealPathName(),
167 /*remove=*/true);
168
169 /* Check if the policy will request this header to be expanded. */
170 bool policy_expand = Run_Must_Expand_Policy(id);
171
172 bool not_expand = In_Set(must_not_expand_set, id->getFileName(), false) ||
173 In_Set(must_not_expand_set, id->getFile()->getName(), false) ||
174 In_Set(must_not_expand_set,
175 id->getFile()->getFileEntry().tryGetRealPathName(), false);
176
177 /* Now check what the Must_Not_Expand policy will say. If we have a conflict
178 with what the user or SymbolExternalizer is saying, we cannot continue. */
179 bool policy_not_expand = Run_Must_Not_Expand_Policy(id);
180
181 /* Check if its sane. If the user (or SymbolExternalizer) requested that
182 a must-not-expand header to be expanded, then error out. */
183 if (expand && policy_not_expand) {
184 std::string message = "Unable to expand header " + id->getFileName().str() +
185 ": denied by ExpansionPolicy.";
186 DiagsClass::Emit_Error(message, id->getSourceRange(), SM);
187 throw std::runtime_error("IncludeTree is unable to continue");
188 return;
189 }
190
191 if (expand && not_expand) {
192 std::string message = "Unable to expand header " + id->getFileName().str() +
193 ": denied by -DCE_NOT_EXPAND_INCLUDES.";
194 DiagsClass::Emit_Error(message, id->getSourceRange(), SM);
195 throw std::runtime_error("IncludeTree is unable to continue");
196 return;
197 }
198
199 bool can_be_output = Is_Reachable_From_Main(id);
200 bool is_from_minus_include = !already_seen_main;
201
202 /* Add child to tree. */
203 IncludeNode *child = new IncludeNode(this, id, is_from_minus_include,
204 false, expand | policy_expand,
205 !can_be_output,
206 not_expand | policy_not_expand);
207
208 current->Add_Child(child);
209 child->Set_Parent(current);
210
211 stack.push(child);
212 } else if (MacroDefinitionRecord *def = dyn_cast<MacroDefinitionRecord>(entity)) {
213 MacroInfo *info = mw.Get_Macro_Info(def);
214 if (info && info->isUsedForHeaderGuard()) {
215 const SourceRange &range = def->getSourceRange();
216 OptionalFileEntryRef this_file = PrettyPrint::Get_FileEntry(range.getBegin());
217
218 /* Pop the stack until we find which HeaderNode we currently are. */
219 IncludeNode *current = stack.top();
220 while (!current->Is_Same_File(this_file)) {
221 stack.pop();
222 current = stack.top();
223 }
224 current->Set_HeaderGuard(def);
225 }
226 }
227 }
228
229 /* In the case there is no includes, the Root node is never set to the main
230 file. Do it now. */
231 if (already_seen_main == false) {
232 Root->Set_FileEntry(main);
233 }
234
235 /* Root node should always be set to expand and not output. */
236 assert(Root->Should_Be_Expanded() && !Root->Should_Be_Output());
237
238 /* Check if the Root has a valid FileEntry. */
239 assert(Root->Get_FileEntry().has_value());
240 }
241
242 void IncludeTree::Build_Header_Map(void)
243 {
244 static bool warned = false;
245 std::stack<IncludeNode *> stack;
246
247 stack.push(Root);
248 while (!stack.empty()) {
249 IncludeNode *node = stack.top();
250 stack.pop();
251
252 /* For Files. */
253 OptionalFileEntryRef file = node->Get_FileEntry();
254 const FileEntryRef fentry = *file;
255 if (Map.find(fentry) != Map.end()) {
256 /* FIXME: Find a way to correcly map the FileEntry to the node instead of
257 discarding future appearances. */
258 if (warned == false) {
259 const SourceRange &range = node->Get_Include_Spelling_Range();
260 DiagsClass::Emit_Warn("project #include's the same file multiple times."
261 " Only the first is registered.", range, SM);
262 warned = true;
263 }
264 } else {
265 Map[fentry] = node;
266 }
267
268 /* For InclusionDirectives. */
269 if (node->ID != nullptr) {
270 IncMap[node->ID] = node;
271 }
272
273 int n = node->Get_Num_Childs();
274 while (n > 0) {
275 stack.push(node->Get_Child(--n));
276 }
277 }
278 }
279
280 void IncludeTree::Set_Expansion_Attrs(IncludeNode *node)
281 {
282 /* Because we need to propagate the ShouldBeExpanded upwards in the tree,
283 we iterate on it using post-order transversal. */
284 for (IncludeNode *child : node->Childs) {
285 Set_Expansion_Attrs(child);
286 }
287
288 /* We must not touch root. */
289 if (node->Is_Root())
290 return;
291
292 if (node->ShouldBeExpanded) {
293 IncludeNode *parent = node->Get_Parent();
294 parent->ShouldBeExpanded = true;
295 parent->ShouldBeOutput = false;
296 }
297 }
298
299 void IncludeTree::Set_Output_Attrs(void)
300 {
301 /* Because we need to propagate the ShouldBeOutput downwards in the tree,
302 we iterate on it using pre-order transversal by the aid of an stack. */
303 std::stack<IncludeNode *> stack;
304 stack.push(Root);
305 while (!stack.empty()) {
306 IncludeNode *node = stack.top(); stack.pop();
307 IncludeNode *parent = node->Get_Parent();
308
309 /* In case the parent is set to be expanded, we must output this
310 include. */
311 if (parent && parent->ShouldBeExpanded && !node->ShouldBeExpanded) {
312 if (!node->Is_From_Minus_Include() || !parent->Is_Root()) {
313 /* In the case this node can not be output, we need set it to
314 expansion and try later for its children. */
315 if (node->ShouldNotBeOutput) {
316 node->ShouldBeExpanded = true;
317 } else {
318 node->ShouldBeOutput = true;
319 }
320 }
321 }
322
323 /* Add children to the stack. */
324 for (IncludeNode *child : node->Childs) {
325 stack.push(child);
326 }
327 }
328 }
329
330 void IncludeTree::Cut_Non_Expandable_Trees(IncludeNode *node, bool cutting)
331 {
332 /* Because we need to propagate the ShouldBeOuput downwards in the tree,
333 we iterate on it using pre-order transversal recursively. */
334
335 /* If we are already cutting it from the tree. */
336 if (cutting) {
337 node->ShouldBeOutput = false;
338 node->ShouldBeExpanded = false;
339 } else if (node->ShouldNotBeExpanded) {
340 /* We need to start cutting it from the tree. */
341 node->ShouldBeOutput = true;
342 node->ShouldBeExpanded = false;
343
344 if (node->ShouldNotBeOutput) {
345 std::string message = "Unable to not expand header " +
346 node->ID->getFileName().str() +
347 ": header is not reachable from main file.";
348 DiagsClass::Emit_Error(message, node->ID->getSourceRange(), SM);
349 throw std::runtime_error("IncludeTree is unable to continue");
350 }
351 }
352
353 /* Propagate downards. */
354 bool cut = cutting || node->ShouldNotBeExpanded;
355 for (IncludeNode *child : node->Childs) {
356 Cut_Non_Expandable_Trees(child, cut);
357 }
358 }
359
360 IncludeNode *IncludeTree::Get(const SourceLocation &loc)
361 {
362 OptionalFileEntryRef fileref = PrettyPrint::Get_FileEntry(loc);
363
364 /* In case we could not find a FileRef, then try the ExpansionLoc. */
365 if (!fileref.has_value()) {
366 const SourceLocation &loc2 = SM.getExpansionLoc(loc);
367 fileref = PrettyPrint::Get_FileEntry(loc2);
368 }
369
370 if (fileref.has_value()) {
371 return Get(&fileref->getFileEntry());
372 }
373
374 /* Well, the declaration seems fuzzy, so return that we don't have a file. */
375 return nullptr;
376 }
377
378 IncludeNode *IncludeTree::Get(const FileEntry *file)
379 {
380 return Map[file];
381 }
382
383 bool IncludeTree::Is_Reachable_From_Main(InclusionDirective *ID)
384 {
385 HeaderSearch &incsrch = PP.getHeaderSearchInfo();
386
387 /* Get main file location. We will check if the include is reachable from
388 the main file. */
389 FileID main_file = SM.getMainFileID();
390 SourceLocation mainfileloc = SM.getLocForStartOfFile(main_file);
391
392 auto main_dir = ClangCompat::Get_Main_Directory_Arr(SM);
393
394 /* If we mark a file for output, this include must be reachable from the
395 main file, otherwise the generated file won't be able to find certain
396 includes. */
397 OptionalFileEntryRef ref = incsrch.LookupFile(ID->getFileName(),
398 mainfileloc,
399 !ID->wasInQuotes(),
400 nullptr,
401 nullptr,
402 main_dir,
403 nullptr,
404 nullptr,
405 nullptr,
406 nullptr,
407 nullptr,
408 nullptr);
409
410 if (ref.has_value()) {
411 /* File is reachable. */
412 return true;
413 } else {
414 /* File not reachable. */
415 return false;
416 }
417 }
418
419 void IncludeTree::Dump(llvm::raw_ostream &out)
420 {
421 Root->Dump(out);
422 }
423
424 void IncludeTree::Dump(void)
425 {
426 Root->Dump();
427 }
428
429 /* ----- IncludeNode ------ */
430
431 IncludeTree::IncludeNode::IncludeNode(IncludeTree *tree,
432 InclusionDirective *include,
433 bool is_from_minus_include,
434 bool output, bool expand,
435 bool not_output, bool not_expand)
436 : Tree(*tree),
437 ID(include),
438 File(ID->getFile()),
439 HeaderGuard(nullptr),
440 ShouldBeOutput(output),
441 ShouldBeExpanded(expand),
442 ShouldNotBeOutput(not_output),
443 ShouldNotBeExpanded(not_expand),
444 IsFromMinusInclude(is_from_minus_include),
445 Parent(nullptr)
446 {
447 }
448
449 IncludeTree::IncludeNode::IncludeNode(IncludeTree *tree)
450 : Tree(*tree),
451 ID(nullptr),
452 HeaderGuard(nullptr),
453 ShouldBeOutput(false),
454 ShouldBeExpanded(true),
455 ShouldNotBeOutput(false),
456 ShouldNotBeExpanded(false),
457 IsFromMinusInclude(false),
458 Parent(nullptr)
459 {
460 memset(&File, 0, sizeof(File));
461 }
462
463 IncludeTree::IncludeNode::~IncludeNode(void)
464 {
465 for (auto child : Childs) {
466 delete child;
467 }
468
469 Childs.clear();
470 }
471
472 OptionalFileEntryRef IncludeTree::IncludeNode::Get_FileEntry(void)
473 {
474 return File;
475 }
476
477 bool IncludeTree::IncludeNode::Is_Same_File(IncludeNode *node)
478 {
479 return (this == node) || Is_Same_File(node->Get_FileEntry());
480 }
481
482 bool IncludeTree::IncludeNode::Is_Same_File(OptionalFileEntryRef file)
483 {
484
485 /* It is possible that a header was included by no file, which can result
486 in a null FileEntry. Such cases are caused by the -include option during
487 compilation. In this case, we say that two null files are equal. */
488
489 if (!File.has_value()) {
490 if (!file.has_value()) {
491 return true;
492 }
493 return false;
494 } else if (!file.has_value()) {
495 return false;
496 }
497
498 return *File == *file;
499 }
500
501 void IncludeTree::IncludeNode::Add_Child(IncludeTree::IncludeNode *node)
502 {
503 Childs.push_back(node);
504 }
505
506 void IncludeTree::IncludeNode::Set_Parent(IncludeTree::IncludeNode *node)
507 {
508 Parent = node;
509 }
510
511 IncludeTree::IncludeNode *IncludeTree::IncludeNode::Get_Parent(void)
512 {
513 return Parent;
514 }
515
516 std::vector<IncludeTree::IncludeNode *> *IncludeTree::IncludeNode::Get_Childs(void)
517 {
518 return &Childs;
519 }
520
521 IncludeTree::IncludeNode *IncludeTree::IncludeNode::Get_Child(unsigned i)
522 {
523 return Childs[i];
524 }
525
526 unsigned IncludeTree::IncludeNode::Get_Num_Childs(void)
527 {
528 return Childs.size();
529 }
530
531 void IncludeTree::IncludeNode::Set_FileEntry(OptionalFileEntryRef file)
532 {
533 File = file;
534 }
535
536 SourceRange IncludeTree::IncludeNode::Get_File_Range(void)
537 {
538 SourceLocation start, end;
539 SourceManager &SM = Tree.SM;
540 FileID fid = SM.getOrCreateFileID(*File, SrcMgr::CharacteristicKind());
541 start = SM.getLocForStartOfFile(fid);
542 end = SM.getLocForEndOfFile(fid);
543
544 assert(start.isValid() && "Start of header is invalid.");
545 assert(end.isValid() && "End of header is invalid.");
546
547 return SourceRange(start, end);
548 }
549
550 SourceRange IncludeTree::IncludeNode::Get_Include_Spelling_Range(void)
551 {
552 if (ID) {
553 return ID->getSourceRange();
554 }
555
556 assert(false && "Attempt to take SourceRange of root node.");
557 }
558
559 StringRef IncludeTree::IncludeNode::Get_Filename(void)
560 {
561 if (ID) {
562 return ID->getFileName();
563 }
564
565 return StringRef("<Root node>");
566 }
567
568 std::unique_ptr<std::vector<IncludeNode *>> IncludeTree::Get_Non_Expand_Includes(void)
569 {
570 auto vec = new std::vector<IncludeNode *>();
571 std::stack<IncludeNode *> stack;
572
573 stack.push(Root);
574 while (!stack.empty()) {
575 IncludeNode *node = stack.top();
576 stack.pop();
577
578 bool should_output = node->Should_Be_Output();
579 bool should_expand = node->Should_Be_Expanded();
580
581 assert(!(should_output && should_expand) &&
582 "Include can can not be expanded and outputed at the same time!");
583
584 if (!should_expand) {
585 vec->push_back(node);
586 } else {
587 int n = node->Get_Num_Childs();
588 while (n > 0) {
589 stack.push(node->Get_Child(--n));
590 }
591 }
592 }
593
594 return std::unique_ptr<std::vector<IncludeNode *>>{vec};
595 }
596
597 std::unique_ptr<std::vector<IncludeNode *>> IncludeTree::Get_Includes(void)
598 {
599 auto vec = new std::vector<IncludeNode *>();
600 std::stack<IncludeNode *> stack;
601
602 stack.push(Root);
603 while (!stack.empty()) {
604 IncludeNode *node = stack.top();
605 stack.pop();
606
607 /* Nodes without InclusionDirective are just for making the algorithm easier. */
608 if (node->Get_InclusionDirective() != nullptr) {
609 vec->push_back(node);
610 }
611 int n = node->Get_Num_Childs();
612 while (n > 0) {
613 stack.push(node->Get_Child(--n));
614 }
615 }
616
617 return std::unique_ptr<std::vector<IncludeNode *>>{vec};
618 }
619
620 IncludeNode *IncludeTree::Get(const InclusionDirective *directive)
621 {
622 return IncMap[directive];
623 }
624
625 bool IncludeTree::Run_Expansion_Policy(InclusionDirective *ID,
626 SourceLocation inloc, PolicyRule p)
627 {
628 auto main_dir = ClangCompat::Get_Main_Directory_Arr(SM);
629 HeaderSearch &incsrch = PP.getHeaderSearchInfo();
630
631 /* If we mark a file for output, this include must be reachable from the
632 main file, otherwise the generated file won't be able to find certain
633 includes. */
634 OptionalFileEntryRef ref = incsrch.LookupFile(ID->getFileName(),
635 inloc,
636 !ID->wasInQuotes(),
637 nullptr,
638 nullptr,
639 main_dir,
640 nullptr,
641 nullptr,
642 nullptr,
643 nullptr,
644 nullptr,
645 nullptr);
646
647 if (ref.has_value()) {
648 const FileEntryRef &entry = *ref;
649 const FileEntry &fentry = ref->getFileEntry();
650 if (p == PolicyRule::MUST_EXPAND) {
651 return IEP->Must_Expand(fentry.tryGetRealPathName(), entry.getName());
652 } else if (p == PolicyRule::MUST_NOT_EXPAND) {
653 return IEP->Must_Not_Expand(fentry.tryGetRealPathName(), entry.getName());
654 }
655 }
656
657 return false;
658 }
659
660 bool IncludeNode::Has_Parent_Marked_For_Output(void)
661 {
662 IncludeNode *node = this;
663
664 do {
665 if (node->Should_Be_Output()) {
666 return true;
667 }
668 node = node->Get_Parent();
669 } while (node != nullptr);
670
671 return false;
672 }
673
674 bool IncludeNode::Is_Reachable_From_Main(void)
675 {
676 if (Is_Root()) {
677 /* Root is always reachable: is the main itself. */
678 return true;
679 }
680
681 return Tree.Is_Reachable_From_Main(ID);
682 }
683
684 void IncludeNode::Set_HeaderGuard(MacroDefinitionRecord *guard)
685 {
686 if (HeaderGuard == nullptr) {
687 HeaderGuard = guard;
688 } else {
689 std::string message = "Attempt to redefine headerguard of " + Get_Filename().str();
690 DiagsClass::Emit_Warn(message, guard->getSourceRange(), Tree.SM);
691 }
692 }
693
694 bool IncludeTree::IncludeNode::Can_Be_Expanded(void)
695 {
696 IncludeNode *node = this;
697 while (node) {
698 if (node->ShouldNotBeExpanded) {
699 return false;
700 }
701 node = node->Get_Parent();
702 }
703
704 return true;
705 }
706
707 void IncludeTree::IncludeNode::Dump_Single_Node(llvm::raw_ostream &out)
708 {
709 out << File->getName() << " Expand: " << ShouldBeExpanded <<
710 " Output: " << ShouldBeOutput << " NotExpand: " << ShouldNotBeExpanded <<
711 " NotOutput: " << ShouldNotBeOutput << " -include: " <<
712 IsFromMinusInclude << '\n';
713 }
714
715 void IncludeTree::IncludeNode::Dump_Single_Node(void)
716 {
717 Dump_Single_Node(llvm::outs());
718 }
719
720 void IncludeTree::IncludeNode::Dump(llvm::raw_ostream &out, unsigned ident)
721 {
722 out << std::string(ident*2, ' ');
723 Dump_Single_Node(out);
724
725 for (IncludeNode *child : Childs) {
726 child->Dump(out, ident + 1);
727 }
728 }
729
730 void IncludeTree::IncludeNode::Dump(void)
731 {
732 Dump(llvm::outs());
733 }