519 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements the PreprocessingRecord class, which maintains a record10// 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 34using namespace clang;35 36ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() =37 default;38 39InclusionDirective::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 52PreprocessingRecord::PreprocessingRecord(SourceManager &SM) : SourceMgr(SM) {}53 54/// Returns a pair of [Begin, End) iterators of preprocessed entities55/// that source range \p Range encompasses.56llvm::iterator_range<PreprocessingRecord::iterator>57PreprocessingRecord::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 75static 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 iterator89/// points to is coming from the file \arg FID.90///91/// Can be used to avoid implicit deserializations of preallocated92/// preprocessed entities if we only care about entities of a specific file93/// and not from files \#included in the range given at94/// \see getPreprocessedEntitiesInRange.95bool 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 without111 // 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 deserialize117 // 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 entities132/// that source range \arg R encompasses.133std::pair<int, int>134PreprocessingRecord::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 163std::pair<unsigned, unsigned>164PreprocessingRecord::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 175namespace {176 177template <SourceLocation (SourceRange::*getRangeLoc)() const>178struct 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} // namespace206 207unsigned 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_iterator215 First = PreprocessedEntities.begin();216 std::vector<PreprocessedEntity *>::const_iterator I;217 218 // Do a binary search manually instead of using std::lower_bound because219 // The end locations of entities may be unordered (when a macro expansion220 // is inside another macro argument), but for this case it is not important221 // 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 } else232 Count = Half;233 }234 235 return First - PreprocessedEntities.begin();236}237 238unsigned239PreprocessingRecord::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 248PreprocessingRecord::PPEntityID249PreprocessingRecord::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 with272 // 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 are275 // not expanded in the same order as listed, e.g:276 // \code277 // #define M1 1278 // #define M2 2279 // #define FM(x,y) y x280 // FM(M1, M2)281 // \endcode282 283 using pp_iter = std::vector<PreprocessedEntity *>::iterator;284 285 // Usually there are few macro expansions when defining the filename, do a286 // 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 310void PreprocessingRecord::SetExternalSource(311 ExternalPreprocessingRecordSource &Source) {312 assert(!ExternalSource &&313 "Preprocessing record already has an external source");314 ExternalSource = &Source;315}316 317unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {318 unsigned Result = LoadedPreprocessedEntities.size();319 LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()320 + NumEntities);321 return Result;322}323 324unsigned PreprocessingRecord::allocateSkippedRanges(unsigned NumRanges) {325 unsigned Result = SkippedRanges.size();326 SkippedRanges.resize(SkippedRanges.size() + NumRanges);327 SkippedRangesAllLoaded = false;328 return Result;329}330 331void 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 341void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,342 MacroDefinitionRecord *Def) {343 MacroDefinitions[Macro] = Def;344}345 346/// Retrieve the preprocessed entity at the given ID.347PreprocessedEntity *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.364PreprocessedEntity *365PreprocessingRecord::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 379MacroDefinitionRecord *380PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {381 return MacroDefinitions.lookup(MI);382}383 384void 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 398void 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 406void 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 414void 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 422void 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 431void 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 440void PreprocessingRecord::SourceRangeSkipped(SourceRange Range,441 SourceLocation EndifLoc) {442 assert(Range.isValid());443 SkippedRanges.emplace_back(Range.getBegin(), EndifLoc);444}445 446void PreprocessingRecord::MacroExpands(const Token &Id,447 const MacroDefinition &MD,448 SourceRange Range,449 const MacroArgs *Args) {450 addMacroExpansion(Id, MD.getMacroInfo(), Range);451}452 453void 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 463void PreprocessingRecord::MacroUndefined(const Token &Id,464 const MacroDefinition &MD,465 const MacroDirective *Undef) {466 MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });467}468 469void 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 expects504 // 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 512size_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