1 //===- PreprocessingRecord.cpp - Record of Preprocessing ------------------===// 2 // 3 // Part of the LLVM Project, 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 // This file implements the PreprocessingRecord class, which maintains a record 10 // of what occurred during preprocessing, and its helpers. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/Lex/PreprocessingRecord.h" 15 #include "clang/Basic/IdentifierTable.h" 16 #include "clang/Basic/LLVM.h" 17 #include "clang/Basic/SourceLocation.h" 18 #include "clang/Basic/SourceManager.h" 19 #include "clang/Basic/TokenKinds.h" 20 #include "clang/Lex/MacroInfo.h" 21 #include "clang/Lex/Token.h" 22 #include "llvm/ADT/DenseMap.h" 23 #include "llvm/ADT/iterator_range.h" 24 #include "llvm/Support/Capacity.h" 25 #include "llvm/Support/ErrorHandling.h" 26 #include <cassert> 27 #include <cstddef> 28 #include <cstring> 29 #include <iterator> 30 #include <optional> 31 #include <utility> 32 #include <vector> 33 34 using namespace clang; 35 36 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() = 37 default; 38 39 InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec, 40 InclusionKind Kind, StringRef FileName, 41 bool InQuotes, bool ImportedModule, 42 OptionalFileEntryRef File, 43 SourceRange Range) 44 : PreprocessingDirective(InclusionDirectiveKind, Range), InQuotes(InQuotes), 45 Kind(Kind), ImportedModule(ImportedModule), File(File) { 46 char *Memory = (char *)PPRec.Allocate(FileName.size() + 1, alignof(char)); 47 memcpy(Memory, FileName.data(), FileName.size()); 48 Memory[FileName.size()] = 0; 49 this->FileName = StringRef(Memory, FileName.size()); 50 } 51 52 PreprocessingRecord::PreprocessingRecord(SourceManager &SM) : SourceMgr(SM) {} 53 54 /// Returns a pair of [Begin, End) iterators of preprocessed entities 55 /// that source range \p Range encompasses. 56 llvm::iterator_range<PreprocessingRecord::iterator> 57 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) { 58 if (Range.isInvalid()) 59 return llvm::make_range(iterator(), iterator()); 60 61 if (CachedRangeQuery.Range == Range) { 62 return llvm::make_range(iterator(this, CachedRangeQuery.Result.first), 63 iterator(this, CachedRangeQuery.Result.second)); 64 } 65 66 std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range); 67 68 CachedRangeQuery.Range = Range; 69 CachedRangeQuery.Result = Res; 70 71 return llvm::make_range(iterator(this, Res.first), 72 iterator(this, Res.second)); 73 } 74 75 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID, 76 SourceManager &SM) { 77 assert(FID.isValid()); 78 if (!PPE) 79 return false; 80 81 SourceLocation Loc = PPE->getSourceRange().getBegin(); 82 if (Loc.isInvalid()) 83 return false; 84 85 return SM.isInFileID(SM.getFileLoc(Loc), FID); 86 } 87 88 /// Returns true if the preprocessed entity that \arg PPEI iterator 89 /// points to is coming from the file \arg FID. 90 /// 91 /// Can be used to avoid implicit deserializations of preallocated 92 /// preprocessed entities if we only care about entities of a specific file 93 /// and not from files \#included in the range given at 94 /// \see getPreprocessedEntitiesInRange. 95 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) { 96 if (FID.isInvalid()) 97 return false; 98 99 int Pos = std::distance(iterator(this, 0), PPEI); 100 if (Pos < 0) { 101 if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) { 102 assert(0 && "Out-of bounds loaded preprocessed entity"); 103 return false; 104 } 105 assert(ExternalSource && "No external source to load from"); 106 unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos; 107 if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex]) 108 return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr); 109 110 // See if the external source can see if the entity is in the file without 111 // deserializing it. 112 if (std::optional<bool> IsInFile = 113 ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID)) 114 return *IsInFile; 115 116 // The external source did not provide a definite answer, go and deserialize 117 // the entity to check it. 118 return isPreprocessedEntityIfInFileID( 119 getLoadedPreprocessedEntity(LoadedIndex), 120 FID, SourceMgr); 121 } 122 123 if (unsigned(Pos) >= PreprocessedEntities.size()) { 124 assert(0 && "Out-of bounds local preprocessed entity"); 125 return false; 126 } 127 return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos], 128 FID, SourceMgr); 129 } 130 131 /// Returns a pair of [Begin, End) iterators of preprocessed entities 132 /// that source range \arg R encompasses. 133 std::pair<int, int> 134 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) { 135 assert(Range.isValid()); 136 assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin())); 137 138 std::pair<unsigned, unsigned> 139 Local = findLocalPreprocessedEntitiesInRange(Range); 140 141 // Check if range spans local entities. 142 if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin())) 143 return std::make_pair(Local.first, Local.second); 144 145 std::pair<unsigned, unsigned> 146 Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range); 147 148 // Check if range spans local entities. 149 if (Loaded.first == Loaded.second) 150 return std::make_pair(Local.first, Local.second); 151 152 unsigned TotalLoaded = LoadedPreprocessedEntities.size(); 153 154 // Check if range spans loaded entities. 155 if (Local.first == Local.second) 156 return std::make_pair(int(Loaded.first)-TotalLoaded, 157 int(Loaded.second)-TotalLoaded); 158 159 // Range spands loaded and local entities. 160 return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second); 161 } 162 163 std::pair<unsigned, unsigned> 164 PreprocessingRecord::findLocalPreprocessedEntitiesInRange( 165 SourceRange Range) const { 166 if (Range.isInvalid()) 167 return std::make_pair(0,0); 168 assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin())); 169 170 unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin()); 171 unsigned End = findEndLocalPreprocessedEntity(Range.getEnd()); 172 return std::make_pair(Begin, End); 173 } 174 175 namespace { 176 177 template <SourceLocation (SourceRange::*getRangeLoc)() const> 178 struct PPEntityComp { 179 const SourceManager &SM; 180 181 explicit PPEntityComp(const SourceManager &SM) : SM(SM) {} 182 183 bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const { 184 SourceLocation LHS = getLoc(L); 185 SourceLocation RHS = getLoc(R); 186 return SM.isBeforeInTranslationUnit(LHS, RHS); 187 } 188 189 bool operator()(PreprocessedEntity *L, SourceLocation RHS) const { 190 SourceLocation LHS = getLoc(L); 191 return SM.isBeforeInTranslationUnit(LHS, RHS); 192 } 193 194 bool operator()(SourceLocation LHS, PreprocessedEntity *R) const { 195 SourceLocation RHS = getLoc(R); 196 return SM.isBeforeInTranslationUnit(LHS, RHS); 197 } 198 199 SourceLocation getLoc(PreprocessedEntity *PPE) const { 200 SourceRange Range = PPE->getSourceRange(); 201 return (Range.*getRangeLoc)(); 202 } 203 }; 204 205 } // namespace 206 207 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity( 208 SourceLocation Loc) const { 209 if (SourceMgr.isLoadedSourceLocation(Loc)) 210 return 0; 211 212 size_t Count = PreprocessedEntities.size(); 213 size_t Half; 214 std::vector<PreprocessedEntity *>::const_iterator 215 First = PreprocessedEntities.begin(); 216 std::vector<PreprocessedEntity *>::const_iterator I; 217 218 // Do a binary search manually instead of using std::lower_bound because 219 // The end locations of entities may be unordered (when a macro expansion 220 // is inside another macro argument), but for this case it is not important 221 // whether we get the first macro expansion or its containing macro. 222 while (Count > 0) { 223 Half = Count/2; 224 I = First; 225 std::advance(I, Half); 226 if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(), 227 Loc)){ 228 First = I; 229 ++First; 230 Count = Count - Half - 1; 231 } else 232 Count = Half; 233 } 234 235 return First - PreprocessedEntities.begin(); 236 } 237 238 unsigned 239 PreprocessingRecord::findEndLocalPreprocessedEntity(SourceLocation Loc) const { 240 if (SourceMgr.isLoadedSourceLocation(Loc)) 241 return 0; 242 243 auto I = llvm::upper_bound(PreprocessedEntities, Loc, 244 PPEntityComp<&SourceRange::getBegin>(SourceMgr)); 245 return I - PreprocessedEntities.begin(); 246 } 247 248 PreprocessingRecord::PPEntityID 249 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) { 250 assert(Entity); 251 SourceLocation BeginLoc = Entity->getSourceRange().getBegin(); 252 253 if (isa<MacroDefinitionRecord>(Entity)) { 254 assert((PreprocessedEntities.empty() || 255 !SourceMgr.isBeforeInTranslationUnit( 256 BeginLoc, 257 PreprocessedEntities.back()->getSourceRange().getBegin())) && 258 "a macro definition was encountered out-of-order"); 259 PreprocessedEntities.push_back(Entity); 260 return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false); 261 } 262 263 // Check normal case, this entity begin location is after the previous one. 264 if (PreprocessedEntities.empty() || 265 !SourceMgr.isBeforeInTranslationUnit(BeginLoc, 266 PreprocessedEntities.back()->getSourceRange().getBegin())) { 267 PreprocessedEntities.push_back(Entity); 268 return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false); 269 } 270 271 // The entity's location is not after the previous one; this can happen with 272 // include directives that form the filename using macros, e.g: 273 // "#include MACRO(STUFF)" 274 // or with macro expansions inside macro arguments where the arguments are 275 // not expanded in the same order as listed, e.g: 276 // \code 277 // #define M1 1 278 // #define M2 2 279 // #define FM(x,y) y x 280 // FM(M1, M2) 281 // \endcode 282 283 using pp_iter = std::vector<PreprocessedEntity *>::iterator; 284 285 // Usually there are few macro expansions when defining the filename, do a 286 // linear search for a few entities. 287 unsigned count = 0; 288 for (pp_iter RI = PreprocessedEntities.end(), 289 Begin = PreprocessedEntities.begin(); 290 RI != Begin && count < 4; --RI, ++count) { 291 pp_iter I = RI; 292 --I; 293 if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc, 294 (*I)->getSourceRange().getBegin())) { 295 pp_iter insertI = PreprocessedEntities.insert(RI, Entity); 296 return getPPEntityID(insertI - PreprocessedEntities.begin(), 297 /*isLoaded=*/false); 298 } 299 } 300 301 // Linear search unsuccessful. Do a binary search. 302 pp_iter I = 303 llvm::upper_bound(PreprocessedEntities, BeginLoc, 304 PPEntityComp<&SourceRange::getBegin>(SourceMgr)); 305 pp_iter insertI = PreprocessedEntities.insert(I, Entity); 306 return getPPEntityID(insertI - PreprocessedEntities.begin(), 307 /*isLoaded=*/false); 308 } 309 310 void PreprocessingRecord::SetExternalSource( 311 ExternalPreprocessingRecordSource &Source) { 312 assert(!ExternalSource && 313 "Preprocessing record already has an external source"); 314 ExternalSource = &Source; 315 } 316 317 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) { 318 unsigned Result = LoadedPreprocessedEntities.size(); 319 LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size() 320 + NumEntities); 321 return Result; 322 } 323 324 unsigned PreprocessingRecord::allocateSkippedRanges(unsigned NumRanges) { 325 unsigned Result = SkippedRanges.size(); 326 SkippedRanges.resize(SkippedRanges.size() + NumRanges); 327 SkippedRangesAllLoaded = false; 328 return Result; 329 } 330 331 void PreprocessingRecord::ensureSkippedRangesLoaded() { 332 if (SkippedRangesAllLoaded || !ExternalSource) 333 return; 334 for (unsigned Index = 0; Index != SkippedRanges.size(); ++Index) { 335 if (SkippedRanges[Index].isInvalid()) 336 SkippedRanges[Index] = ExternalSource->ReadSkippedRange(Index); 337 } 338 SkippedRangesAllLoaded = true; 339 } 340 341 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro, 342 MacroDefinitionRecord *Def) { 343 MacroDefinitions[Macro] = Def; 344 } 345 346 /// Retrieve the preprocessed entity at the given ID. 347 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){ 348 if (PPID.ID < 0) { 349 unsigned Index = -PPID.ID - 1; 350 assert(Index < LoadedPreprocessedEntities.size() && 351 "Out-of bounds loaded preprocessed entity"); 352 return getLoadedPreprocessedEntity(Index); 353 } 354 355 if (PPID.ID == 0) 356 return nullptr; 357 unsigned Index = PPID.ID - 1; 358 assert(Index < PreprocessedEntities.size() && 359 "Out-of bounds local preprocessed entity"); 360 return PreprocessedEntities[Index]; 361 } 362 363 /// Retrieve the loaded preprocessed entity at the given index. 364 PreprocessedEntity * 365 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) { 366 assert(Index < LoadedPreprocessedEntities.size() && 367 "Out-of bounds loaded preprocessed entity"); 368 assert(ExternalSource && "No external source to load from"); 369 PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index]; 370 if (!Entity) { 371 Entity = ExternalSource->ReadPreprocessedEntity(Index); 372 if (!Entity) // Failed to load. 373 Entity = new (*this) 374 PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange()); 375 } 376 return Entity; 377 } 378 379 MacroDefinitionRecord * 380 PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) { 381 return MacroDefinitions.lookup(MI); 382 } 383 384 void PreprocessingRecord::addMacroExpansion(const Token &Id, 385 const MacroInfo *MI, 386 SourceRange Range) { 387 // We don't record nested macro expansions. 388 if (Id.getLocation().isMacroID()) 389 return; 390 391 if (MI->isBuiltinMacro()) 392 addPreprocessedEntity(new (*this) 393 MacroExpansion(Id.getIdentifierInfo(), Range)); 394 else if (MacroDefinitionRecord *Def = findMacroDefinition(MI)) 395 addPreprocessedEntity(new (*this) MacroExpansion(Def, Range)); 396 } 397 398 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok, 399 const MacroDefinition &MD) { 400 // This is not actually a macro expansion but record it as a macro reference. 401 if (MD) 402 addMacroExpansion(MacroNameTok, MD.getMacroInfo(), 403 MacroNameTok.getLocation()); 404 } 405 406 void PreprocessingRecord::Elifdef(SourceLocation Loc, const Token &MacroNameTok, 407 const MacroDefinition &MD) { 408 // This is not actually a macro expansion but record it as a macro reference. 409 if (MD) 410 addMacroExpansion(MacroNameTok, MD.getMacroInfo(), 411 MacroNameTok.getLocation()); 412 } 413 414 void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok, 415 const MacroDefinition &MD) { 416 // This is not actually a macro expansion but record it as a macro reference. 417 if (MD) 418 addMacroExpansion(MacroNameTok, MD.getMacroInfo(), 419 MacroNameTok.getLocation()); 420 } 421 422 void PreprocessingRecord::Elifndef(SourceLocation Loc, 423 const Token &MacroNameTok, 424 const MacroDefinition &MD) { 425 // This is not actually a macro expansion but record it as a macro reference. 426 if (MD) 427 addMacroExpansion(MacroNameTok, MD.getMacroInfo(), 428 MacroNameTok.getLocation()); 429 } 430 431 void PreprocessingRecord::Defined(const Token &MacroNameTok, 432 const MacroDefinition &MD, 433 SourceRange Range) { 434 // This is not actually a macro expansion but record it as a macro reference. 435 if (MD) 436 addMacroExpansion(MacroNameTok, MD.getMacroInfo(), 437 MacroNameTok.getLocation()); 438 } 439 440 void PreprocessingRecord::SourceRangeSkipped(SourceRange Range, 441 SourceLocation EndifLoc) { 442 assert(Range.isValid()); 443 SkippedRanges.emplace_back(Range.getBegin(), EndifLoc); 444 } 445 446 void PreprocessingRecord::MacroExpands(const Token &Id, 447 const MacroDefinition &MD, 448 SourceRange Range, 449 const MacroArgs *Args) { 450 addMacroExpansion(Id, MD.getMacroInfo(), Range); 451 } 452 453 void PreprocessingRecord::MacroDefined(const Token &Id, 454 const MacroDirective *MD) { 455 const MacroInfo *MI = MD->getMacroInfo(); 456 SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc()); 457 MacroDefinitionRecord *Def = 458 new (*this) MacroDefinitionRecord(Id.getIdentifierInfo(), R); 459 addPreprocessedEntity(Def); 460 MacroDefinitions[MI] = Def; 461 } 462 463 void PreprocessingRecord::MacroUndefined(const Token &Id, 464 const MacroDefinition &MD, 465 const MacroDirective *Undef) { 466 MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); }); 467 } 468 469 void PreprocessingRecord::InclusionDirective( 470 SourceLocation HashLoc, const Token &IncludeTok, StringRef FileName, 471 bool IsAngled, CharSourceRange FilenameRange, OptionalFileEntryRef File, 472 StringRef SearchPath, StringRef RelativePath, const Module *SuggestedModule, 473 bool ModuleImported, SrcMgr::CharacteristicKind FileType) { 474 InclusionDirective::InclusionKind Kind = InclusionDirective::Include; 475 476 switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) { 477 case tok::pp_include: 478 Kind = InclusionDirective::Include; 479 break; 480 481 case tok::pp_import: 482 Kind = InclusionDirective::Import; 483 break; 484 485 case tok::pp_include_next: 486 Kind = InclusionDirective::IncludeNext; 487 break; 488 489 case tok::pp___include_macros: 490 Kind = InclusionDirective::IncludeMacros; 491 break; 492 493 default: 494 llvm_unreachable("Unknown include directive kind"); 495 } 496 497 SourceLocation EndLoc; 498 if (!IsAngled) { 499 EndLoc = FilenameRange.getBegin(); 500 } else { 501 EndLoc = FilenameRange.getEnd(); 502 if (FilenameRange.isCharRange()) 503 EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects 504 // a token range. 505 } 506 clang::InclusionDirective *ID = new (*this) clang::InclusionDirective( 507 *this, Kind, FileName, !IsAngled, ModuleImported, File, 508 SourceRange(HashLoc, EndLoc)); 509 addPreprocessedEntity(ID); 510 } 511 512 size_t PreprocessingRecord::getTotalMemory() const { 513 return BumpAlloc.getTotalMemory() 514 + llvm::capacity_in_bytes(MacroDefinitions) 515 + llvm::capacity_in_bytes(PreprocessedEntities) 516 + llvm::capacity_in_bytes(LoadedPreprocessedEntities) 517 + llvm::capacity_in_bytes(SkippedRanges); 518 } 519