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