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