| 1 |
//===- IncludeTree.hh - 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 |
/** IncludeTree: Tree of include directives. |
| 17 |
* |
| 18 |
* A C or C++ source file often #include other files for prototypes of |
| 19 |
* functions, macros, and such to be used in the code. Those files also |
| 20 |
* include other files, which if we stand from the mainfile perspective |
| 21 |
* it can be seen as a tree. This file implement such tree. |
| 22 |
*/ |
| 23 |
|
| 24 |
#pragma once |
| 25 |
|
| 26 |
#include "ExpansionPolicy.hh" |
| 27 |
|
| 28 |
#include <clang/Tooling/Tooling.h> |
| 29 |
#include <vector> |
| 30 |
#include <unordered_map> |
| 31 |
#include <unordered_set> |
| 32 |
#include <memory> |
| 33 |
|
| 34 |
using namespace clang; |
| 35 |
|
| 36 |
|
| 37 |
/** @brief Tree of include directives. |
| 38 |
* |
| 39 |
* This tree holds information of all files that ends up included in the |
| 40 |
* source. |
| 41 |
*/ |
| 42 |
class IncludeTree |
| 43 |
{ |
| 44 |
public: |
| 45 |
|
| 46 |
/** @brief Node of #include representing a single file. |
| 47 |
* |
| 48 |
* A single included file may include several other files. This class |
| 49 |
* represent a single file in this inclusion tree. |
| 50 |
*/ |
| 51 |
class IncludeNode |
| 52 |
{ |
| 53 |
public: |
| 54 |
/** Build the IncludeNode from a single InclusionDirective taken from the |
| 55 |
PreprocessingDirective history. Set if header must be marked to `output` |
| 56 |
or `expanded` when printed. */ |
| 57 |
IncludeNode(IncludeTree *tree, InclusionDirective *include, |
| 58 |
bool is_from_minus_inclue = false, |
| 59 |
bool output = false, bool expand = false, |
| 60 |
bool not_output = false, bool not_expand = false); |
| 61 |
|
| 62 |
/** Build an IncludeNode to a null file, which is not #include'd |
| 63 |
anywhere but is the root of everything. */ |
| 64 |
IncludeNode(IncludeTree *tree); |
| 65 |
|
| 66 |
/* Destructor. */ |
| 67 |
~IncludeNode(void); |
| 68 |
|
| 69 |
/* Check if #include comes from -include, which is handled a little |
| 70 |
differently. */ |
| 71 |
inline bool Is_From_Minus_Include(void) |
| 72 |
{ |
| 73 |
return IsFromMinusInclude; |
| 74 |
} |
| 75 |
|
| 76 |
/** Get file which includes this file. If this is included in multiple |
| 77 |
locations you will have to transverse the tree to find the other |
| 78 |
occurence of the same file, once macros can control which part of the |
| 79 |
file is included or not, drastically changing its behavior. */ |
| 80 |
IncludeNode *Get_Parent(void); |
| 81 |
|
| 82 |
/** Get the i-th file that this file includs. */ |
| 83 |
IncludeNode *Get_Child(unsigned i); |
| 84 |
|
| 85 |
/** Get the number of includes in this file. */ |
| 86 |
unsigned Get_Num_Childs(void); |
| 87 |
|
| 88 |
/** Get all files this file includes. */ |
| 89 |
std::vector<IncludeTree::IncludeNode *> *Get_Childs(void); |
| 90 |
|
| 91 |
/* Get reference to FileEntry object. Used to check if two IncludeNodes |
| 92 |
references the same file. */ |
| 93 |
OptionalFileEntryRef Get_FileEntry(void); |
| 94 |
|
| 95 |
/** Check if two IncludeNodes references the same file. */ |
| 96 |
bool Is_Same_File(IncludeNode *); |
| 97 |
bool Is_Same_File(OptionalFileEntryRef file); |
| 98 |
|
| 99 |
/** Get a range in source location which belongs to the file included. */ |
| 100 |
SourceRange Get_File_Range(void); |
| 101 |
|
| 102 |
/** Get a range in source location which belongs to the #include, as the |
| 103 |
user spelled. */ |
| 104 |
SourceRange Get_Include_Spelling_Range(void); |
| 105 |
|
| 106 |
/** Get Filename. */ |
| 107 |
StringRef Get_Filename(void); |
| 108 |
|
| 109 |
inline InclusionDirective *Get_InclusionDirective(void) |
| 110 |
{ |
| 111 |
return ID; |
| 112 |
} |
| 113 |
|
| 114 |
inline bool Should_Be_Output(void) |
| 115 |
{ |
| 116 |
return ShouldBeOutput; |
| 117 |
} |
| 118 |
|
| 119 |
inline bool Should_Be_Expanded(void) |
| 120 |
{ |
| 121 |
return ShouldBeExpanded; |
| 122 |
} |
| 123 |
|
| 124 |
inline bool Should_Not_Be_Expand(void) |
| 125 |
{ |
| 126 |
return ShouldNotBeExpanded; |
| 127 |
} |
| 128 |
|
| 129 |
inline bool Should_Not_Be_Output(void) |
| 130 |
{ |
| 131 |
return ShouldNotBeOutput; |
| 132 |
} |
| 133 |
|
| 134 |
inline MacroDefinitionRecord *Get_HeaderGuard(void) |
| 135 |
{ |
| 136 |
return HeaderGuard; |
| 137 |
} |
| 138 |
|
| 139 |
/** Check if this node is reachable from the main file, i.e., including it |
| 140 |
in the program would not result in a file not found error. */ |
| 141 |
bool Is_Reachable_From_Main(void); |
| 142 |
|
| 143 |
/** Check if this node or any of its parents was marked for output. */ |
| 144 |
bool Has_Parent_Marked_For_Output(void); |
| 145 |
|
| 146 |
inline bool Is_Root(void) |
| 147 |
{ |
| 148 |
return this == Tree.Root; |
| 149 |
} |
| 150 |
|
| 151 |
/** Check if the node can be marked for expansion. */ |
| 152 |
bool Can_Be_Expanded(void); |
| 153 |
|
| 154 |
/** Dump, for debugging reasons. */ |
| 155 |
void Dump_Single_Node(llvm::raw_ostream &out); |
| 156 |
void Dump(llvm::raw_ostream &out, unsigned ident = 0); |
| 157 |
|
| 158 |
void Dump_Single_Node(void); |
| 159 |
void Dump(void); |
| 160 |
|
| 161 |
private: |
| 162 |
|
| 163 |
/** Add a #include to this file. */ |
| 164 |
void Add_Child(IncludeNode *); |
| 165 |
|
| 166 |
/** Set that this file was #include'd by that file. */ |
| 167 |
void Set_Parent(IncludeNode *that); |
| 168 |
|
| 169 |
/* Set the File referenced. Used when building the tree. */ |
| 170 |
void Set_FileEntry(OptionalFileEntryRef file); |
| 171 |
|
| 172 |
/* Set the macro defintion as the HeaderGuard. */ |
| 173 |
void Set_HeaderGuard(MacroDefinitionRecord *guard); |
| 174 |
|
| 175 |
/** The Tree this node belongs to. */ |
| 176 |
IncludeTree &Tree; |
| 177 |
|
| 178 |
/** Object from the PreprocessingRecord representing an #include. */ |
| 179 |
InclusionDirective *ID; |
| 180 |
|
| 181 |
/** Referece to the actual #include'd file. */ |
| 182 |
OptionalFileEntryRef File; |
| 183 |
|
| 184 |
/** Macro definition which happens to be the headerguard for this header. */ |
| 185 |
MacroDefinitionRecord *HeaderGuard; |
| 186 |
|
| 187 |
bool ShouldBeOutput : 1; |
| 188 |
bool ShouldBeExpanded : 1; |
| 189 |
bool ShouldNotBeOutput : 1; |
| 190 |
bool ShouldNotBeExpanded : 1; |
| 191 |
bool IsFromMinusInclude : 1; |
| 192 |
|
| 193 |
/** Who included me? */ |
| 194 |
IncludeNode *Parent; |
| 195 |
|
| 196 |
/** Which files did I include? */ |
| 197 |
std::vector<IncludeNode *> Childs; |
| 198 |
|
| 199 |
friend IncludeTree; |
| 200 |
}; |
| 201 |
|
| 202 |
/** Create the include tree from the Preprocessor history. */ |
| 203 |
IncludeTree(Preprocessor &pp, SourceManager &sm, |
| 204 |
IncludeExpansionPolicy::Policy p = IncludeExpansionPolicy::Policy::NOTHING, |
| 205 |
std::vector<std::string> const &must_expand = {}, |
| 206 |
std::vector<std::string> const &must_not_expand = {}); |
| 207 |
|
| 208 |
IncludeTree(ASTUnit *ast, |
| 209 |
IncludeExpansionPolicy::Policy p = IncludeExpansionPolicy::Policy::NOTHING, |
| 210 |
std::vector<std::string> const &must_expand = {}, |
| 211 |
std::vector<std::string> const &must_not_expand = {}) |
| 212 |
: IncludeTree(ast->getPreprocessor(), ast->getSourceManager(), p, |
| 213 |
must_expand, must_not_expand) |
| 214 |
{ |
| 215 |
} |
| 216 |
|
| 217 |
/** Default destructor. */ |
| 218 |
~IncludeTree(void); |
| 219 |
|
| 220 |
/** Get includes which is not marked to be expanded. */ |
| 221 |
std::unique_ptr<std::vector<IncludeNode *>> Get_Non_Expand_Includes(void); |
| 222 |
|
| 223 |
/** Get all includes. */ |
| 224 |
std::unique_ptr<std::vector<IncludeNode *>> Get_Includes(void); |
| 225 |
|
| 226 |
/* Get from SourceLocation. */ |
| 227 |
IncludeNode *Get(const SourceLocation &loc); |
| 228 |
|
| 229 |
/** Get from InclusionDirective. */ |
| 230 |
IncludeNode *Get(const InclusionDirective *); |
| 231 |
|
| 232 |
/** Get from FileEntry. */ |
| 233 |
IncludeNode *Get(const FileEntry *); |
| 234 |
|
| 235 |
/** Dump for debugging purposes. */ |
| 236 |
void Dump(llvm::raw_ostream &out); |
| 237 |
void Dump(void); |
| 238 |
|
| 239 |
private: |
| 240 |
|
| 241 |
/** Actually builds the header tree. */ |
| 242 |
void Build_Header_Tree(std::vector<std::string> const &must_expand, |
| 243 |
std::vector<std::string> const &must_not_expand); |
| 244 |
/** Build mapping from header path to IncludeNode. */ |
| 245 |
void Build_Header_Map(void); |
| 246 |
|
| 247 |
/** Set the ShouldBeExpanded flag after the barebones of the tree is built. */ |
| 248 |
void Set_Expansion_Attrs(IncludeNode *node); |
| 249 |
|
| 250 |
/** Set the ShouldBeOutput flag after the barebones of the tree is built |
| 251 |
and the ShouldBeOutput flag is correctly set. */ |
| 252 |
void Set_Output_Attrs(void); |
| 253 |
|
| 254 |
void Cut_Non_Expandable_Trees(IncludeNode *, bool cutting); |
| 255 |
|
| 256 |
enum PolicyRule { |
| 257 |
MUST_EXPAND, |
| 258 |
MUST_NOT_EXPAND, |
| 259 |
}; |
| 260 |
|
| 261 |
/** Run the IncludeExpansionPolicy to the include to figure out if it needs |
| 262 |
to be expanded or not. */ |
| 263 |
bool Run_Expansion_Policy(InclusionDirective *ID, SourceLocation incloc, PolicyRule p); |
| 264 |
|
| 265 |
/** Run the Must_Expand rule of IncludeExpansionPolicy to the include to |
| 266 |
figure out if it needs to be expanded or not. */ |
| 267 |
inline bool Run_Must_Expand_Policy(InclusionDirective *ID) |
| 268 |
{ |
| 269 |
return Run_Expansion_Policy(ID, ID->getSourceRange().getBegin(), MUST_EXPAND); |
| 270 |
} |
| 271 |
|
| 272 |
/** Run the Must_Not_Expand rule of IncludeExpansionPolicy to the include to |
| 273 |
figure out if it can be expanded or not. */ |
| 274 |
inline bool Run_Must_Not_Expand_Policy(InclusionDirective *ID) |
| 275 |
{ |
| 276 |
return Run_Expansion_Policy(ID, ID->getSourceRange().getBegin(), MUST_NOT_EXPAND); |
| 277 |
} |
| 278 |
|
| 279 |
/** Check if this node is reachable from the main file, i.e., including it |
| 280 |
in the program would not result in a file not found error. */ |
| 281 |
bool Is_Reachable_From_Main(InclusionDirective *id); |
| 282 |
|
| 283 |
/** Root of the tree. */ |
| 284 |
IncludeNode *Root; |
| 285 |
|
| 286 |
/* Hash mapping included file to IncludeNode. */ |
| 287 |
std::unordered_map<const FileEntry *, IncludeTree::IncludeNode *> Map; |
| 288 |
std::unordered_map<const InclusionDirective *, IncludeTree::IncludeNode *> IncMap; |
| 289 |
|
| 290 |
/** Reference to the preprocessor used by compilation. */ |
| 291 |
Preprocessor &PP; |
| 292 |
|
| 293 |
/** Reference to the SourceManager. */ |
| 294 |
SourceManager &SM; |
| 295 |
|
| 296 |
/** The Include Expansion Policy when expanding includes. */ |
| 297 |
std::unique_ptr<IncludeExpansionPolicy> IEP; |
| 298 |
}; |
| 299 |
|
| 300 |
typedef IncludeTree::IncludeNode IncludeNode; |