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 const FileEntry *File, SourceRange Range) 46 : PreprocessingDirective(InclusionDirectiveKind, Range), InQuotes(InQuotes), 47 Kind(Kind), ImportedModule(ImportedModule), File(File) { 48 char *Memory = (char *)PPRec.Allocate(FileName.size() + 1, alignof(char)); 49 memcpy(Memory, FileName.data(), FileName.size()); 50 Memory[FileName.size()] = 0; 51 this->FileName = StringRef(Memory, FileName.size()); 52 } 53 54 PreprocessingRecord::PreprocessingRecord(SourceManager &SM) : SourceMgr(SM) {} 55 56 /// Returns a pair of [Begin, End) iterators of preprocessed entities 57 /// that source range \p Range encompasses. 58 llvm::iterator_range<PreprocessingRecord::iterator> 59 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) { 60 if (Range.isInvalid()) 61 return llvm::make_range(iterator(), iterator()); 62 63 if (CachedRangeQuery.Range == Range) { 64 return llvm::make_range(iterator(this, CachedRangeQuery.Result.first), 65 iterator(this, CachedRangeQuery.Result.second)); 66 } 67 68 std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range); 69 70 CachedRangeQuery.Range = Range; 71 CachedRangeQuery.Result = Res; 72 73 return llvm::make_range(iterator(this, Res.first), 74 iterator(this, Res.second)); 75 } 76 77 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID, 78 SourceManager &SM) { 79 assert(FID.isValid()); 80 if (!PPE) 81 return false; 82 83 SourceLocation Loc = PPE->getSourceRange().getBegin(); 84 if (Loc.isInvalid()) 85 return false; 86 87 return SM.isInFileID(SM.getFileLoc(Loc), FID); 88 } 89 90 /// Returns true if the preprocessed entity that \arg PPEI iterator 91 /// points to is coming from the file \arg FID. 92 /// 93 /// Can be used to avoid implicit deserializations of preallocated 94 /// preprocessed entities if we only care about entities of a specific file 95 /// and not from files \#included in the range given at 96 /// \see getPreprocessedEntitiesInRange. 97 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) { 98 if (FID.isInvalid()) 99 return false; 100 101 int Pos = std::distance(iterator(this, 0), PPEI); 102 if (Pos < 0) { 103 if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) { 104 assert(0 && "Out-of bounds loaded preprocessed entity"); 105 return false; 106 } 107 assert(ExternalSource && "No external source to load from"); 108 unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos; 109 if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex]) 110 return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr); 111 112 // See if the external source can see if the entity is in the file without 113 // deserializing it. 114 Optional<bool> IsInFile = 115 ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID); 116 if (IsInFile.hasValue()) 117 return IsInFile.getValue(); 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::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::Defined(const Token &MacroNameTok, 423 const MacroDefinition &MD, 424 SourceRange Range) { 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::SourceRangeSkipped(SourceRange Range, 432 SourceLocation EndifLoc) { 433 assert(Range.isValid()); 434 SkippedRanges.emplace_back(Range.getBegin(), EndifLoc); 435 } 436 437 void PreprocessingRecord::MacroExpands(const Token &Id, 438 const MacroDefinition &MD, 439 SourceRange Range, 440 const MacroArgs *Args) { 441 addMacroExpansion(Id, MD.getMacroInfo(), Range); 442 } 443 444 void PreprocessingRecord::MacroDefined(const Token &Id, 445 const MacroDirective *MD) { 446 const MacroInfo *MI = MD->getMacroInfo(); 447 SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc()); 448 MacroDefinitionRecord *Def = 449 new (*this) MacroDefinitionRecord(Id.getIdentifierInfo(), R); 450 addPreprocessedEntity(Def); 451 MacroDefinitions[MI] = Def; 452 } 453 454 void PreprocessingRecord::MacroUndefined(const Token &Id, 455 const MacroDefinition &MD, 456 const MacroDirective *Undef) { 457 MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); }); 458 } 459 460 void PreprocessingRecord::InclusionDirective( 461 SourceLocation HashLoc, 462 const Token &IncludeTok, 463 StringRef FileName, 464 bool IsAngled, 465 CharSourceRange FilenameRange, 466 const FileEntry *File, 467 StringRef SearchPath, 468 StringRef RelativePath, 469 const Module *Imported, 470 SrcMgr::CharacteristicKind FileType) { 471 InclusionDirective::InclusionKind Kind = InclusionDirective::Include; 472 473 switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) { 474 case tok::pp_include: 475 Kind = InclusionDirective::Include; 476 break; 477 478 case tok::pp_import: 479 Kind = InclusionDirective::Import; 480 break; 481 482 case tok::pp_include_next: 483 Kind = InclusionDirective::IncludeNext; 484 break; 485 486 case tok::pp___include_macros: 487 Kind = InclusionDirective::IncludeMacros; 488 break; 489 490 default: 491 llvm_unreachable("Unknown include directive kind"); 492 } 493 494 SourceLocation EndLoc; 495 if (!IsAngled) { 496 EndLoc = FilenameRange.getBegin(); 497 } else { 498 EndLoc = FilenameRange.getEnd(); 499 if (FilenameRange.isCharRange()) 500 EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects 501 // a token range. 502 } 503 clang::InclusionDirective *ID = 504 new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled, 505 (bool)Imported, File, 506 SourceRange(HashLoc, EndLoc)); 507 addPreprocessedEntity(ID); 508 } 509 510 size_t PreprocessingRecord::getTotalMemory() const { 511 return BumpAlloc.getTotalMemory() 512 + llvm::capacity_in_bytes(MacroDefinitions) 513 + llvm::capacity_in_bytes(PreprocessedEntities) 514 + llvm::capacity_in_bytes(LoadedPreprocessedEntities) 515 + llvm::capacity_in_bytes(SkippedRanges); 516 } 517