| //===- PreprocessingRecord.cpp - Record of Preprocessing ------------------===// | |
| // | |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |
| // See https://llvm.org/LICENSE.txt for license information. | |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |
| // | |
| //===----------------------------------------------------------------------===// | |
| // | |
| // This file implements the PreprocessingRecord class, which maintains a record | |
| // of what occurred during preprocessing, and its helpers. | |
| // | |
| //===----------------------------------------------------------------------===// | |
| #include "clang/Lex/PreprocessingRecord.h" | |
| #include "clang/Basic/IdentifierTable.h" | |
| #include "clang/Basic/LLVM.h" | |
| #include "clang/Basic/SourceLocation.h" | |
| #include "clang/Basic/SourceManager.h" | |
| #include "clang/Basic/TokenKinds.h" | |
| #include "clang/Lex/MacroInfo.h" | |
| #include "clang/Lex/Token.h" | |
| #include "llvm/ADT/DenseMap.h" | |
| #include "llvm/ADT/iterator_range.h" | |
| #include "llvm/Support/Capacity.h" | |
| #include "llvm/Support/ErrorHandling.h" | |
| #include <cassert> | |
| #include <cstddef> | |
| #include <cstring> | |
| #include <iterator> | |
| #include <optional> | |
| #include <utility> | |
| #include <vector> | |
| using namespace clang; | |
| ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() = | |
| default; | |
| InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec, | |
| InclusionKind Kind, StringRef FileName, | |
| bool InQuotes, bool ImportedModule, | |
| OptionalFileEntryRef File, | |
| SourceRange Range) | |
| : PreprocessingDirective(InclusionDirectiveKind, Range), InQuotes(InQuotes), | |
| Kind(Kind), ImportedModule(ImportedModule), File(File) { | |
| char *Memory = (char *)PPRec.Allocate(FileName.size() + 1, alignof(char)); | |
| memcpy(Memory, FileName.data(), FileName.size()); | |
| Memory[FileName.size()] = 0; | |
| this->FileName = StringRef(Memory, FileName.size()); | |
| } | |
| PreprocessingRecord::PreprocessingRecord(SourceManager &SM) : SourceMgr(SM) {} | |
| /// Returns a pair of [Begin, End) iterators of preprocessed entities | |
| /// that source range \p Range encompasses. | |
| llvm::iterator_range<PreprocessingRecord::iterator> | |
| PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) { | |
| if (Range.isInvalid()) | |
| return llvm::make_range(iterator(), iterator()); | |
| if (CachedRangeQuery.Range == Range) { | |
| return llvm::make_range(iterator(this, CachedRangeQuery.Result.first), | |
| iterator(this, CachedRangeQuery.Result.second)); | |
| } | |
| std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range); | |
| CachedRangeQuery.Range = Range; | |
| CachedRangeQuery.Result = Res; | |
| return llvm::make_range(iterator(this, Res.first), | |
| iterator(this, Res.second)); | |
| } | |
| static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID, | |
| SourceManager &SM) { | |
| assert(FID.isValid()); | |
| if (!PPE) | |
| return false; | |
| SourceLocation Loc = PPE->getSourceRange().getBegin(); | |
| if (Loc.isInvalid()) | |
| return false; | |
| return SM.isInFileID(SM.getFileLoc(Loc), FID); | |
| } | |
| /// Returns true if the preprocessed entity that \arg PPEI iterator | |
| /// points to is coming from the file \arg FID. | |
| /// | |
| /// Can be used to avoid implicit deserializations of preallocated | |
| /// preprocessed entities if we only care about entities of a specific file | |
| /// and not from files \#included in the range given at | |
| /// \see getPreprocessedEntitiesInRange. | |
| bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) { | |
| if (FID.isInvalid()) | |
| return false; | |
| int Pos = std::distance(iterator(this, 0), PPEI); | |
| if (Pos < 0) { | |
| if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) { | |
| assert(0 && "Out-of bounds loaded preprocessed entity"); | |
| return false; | |
| } | |
| assert(ExternalSource && "No external source to load from"); | |
| unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos; | |
| if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex]) | |
| return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr); | |
| // See if the external source can see if the entity is in the file without | |
| // deserializing it. | |
| if (std::optional<bool> IsInFile = | |
| ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID)) | |
| return *IsInFile; | |
| // The external source did not provide a definite answer, go and deserialize | |
| // the entity to check it. | |
| return isPreprocessedEntityIfInFileID( | |
| getLoadedPreprocessedEntity(LoadedIndex), | |
| FID, SourceMgr); | |
| } | |
| if (unsigned(Pos) >= PreprocessedEntities.size()) { | |
| assert(0 && "Out-of bounds local preprocessed entity"); | |
| return false; | |
| } | |
| return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos], | |
| FID, SourceMgr); | |
| } | |
| /// Returns a pair of [Begin, End) iterators of preprocessed entities | |
| /// that source range \arg R encompasses. | |
| std::pair<int, int> | |
| PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) { | |
| assert(Range.isValid()); | |
| assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin())); | |
| std::pair<unsigned, unsigned> | |
| Local = findLocalPreprocessedEntitiesInRange(Range); | |
| // Check if range spans local entities. | |
| if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin())) | |
| return std::make_pair(Local.first, Local.second); | |
| std::pair<unsigned, unsigned> | |
| Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range); | |
| // Check if range spans local entities. | |
| if (Loaded.first == Loaded.second) | |
| return std::make_pair(Local.first, Local.second); | |
| unsigned TotalLoaded = LoadedPreprocessedEntities.size(); | |
| // Check if range spans loaded entities. | |
| if (Local.first == Local.second) | |
| return std::make_pair(int(Loaded.first)-TotalLoaded, | |
| int(Loaded.second)-TotalLoaded); | |
| // Range spands loaded and local entities. | |
| return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second); | |
| } | |
| std::pair<unsigned, unsigned> | |
| PreprocessingRecord::findLocalPreprocessedEntitiesInRange( | |
| SourceRange Range) const { | |
| if (Range.isInvalid()) | |
| return std::make_pair(0,0); | |
| assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin())); | |
| unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin()); | |
| unsigned End = findEndLocalPreprocessedEntity(Range.getEnd()); | |
| return std::make_pair(Begin, End); | |
| } | |
| namespace { | |
| template <SourceLocation (SourceRange::*getRangeLoc)() const> | |
| struct PPEntityComp { | |
| const SourceManager &SM; | |
| explicit PPEntityComp(const SourceManager &SM) : SM(SM) {} | |
| bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const { | |
| SourceLocation LHS = getLoc(L); | |
| SourceLocation RHS = getLoc(R); | |
| return SM.isBeforeInTranslationUnit(LHS, RHS); | |
| } | |
| bool operator()(PreprocessedEntity *L, SourceLocation RHS) const { | |
| SourceLocation LHS = getLoc(L); | |
| return SM.isBeforeInTranslationUnit(LHS, RHS); | |
| } | |
| bool operator()(SourceLocation LHS, PreprocessedEntity *R) const { | |
| SourceLocation RHS = getLoc(R); | |
| return SM.isBeforeInTranslationUnit(LHS, RHS); | |
| } | |
| SourceLocation getLoc(PreprocessedEntity *PPE) const { | |
| SourceRange Range = PPE->getSourceRange(); | |
| return (Range.*getRangeLoc)(); | |
| } | |
| }; | |
| } // namespace | |
| unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity( | |
| SourceLocation Loc) const { | |
| if (SourceMgr.isLoadedSourceLocation(Loc)) | |
| return 0; | |
| size_t Count = PreprocessedEntities.size(); | |
| size_t Half; | |
| std::vector<PreprocessedEntity *>::const_iterator | |
| First = PreprocessedEntities.begin(); | |
| std::vector<PreprocessedEntity *>::const_iterator I; | |
| // Do a binary search manually instead of using std::lower_bound because | |
| // The end locations of entities may be unordered (when a macro expansion | |
| // is inside another macro argument), but for this case it is not important | |
| // whether we get the first macro expansion or its containing macro. | |
| while (Count > 0) { | |
| Half = Count/2; | |
| I = First; | |
| std::advance(I, Half); | |
| if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(), | |
| Loc)){ | |
| First = I; | |
| ++First; | |
| Count = Count - Half - 1; | |
| } else | |
| Count = Half; | |
| } | |
| return First - PreprocessedEntities.begin(); | |
| } | |
| unsigned | |
| PreprocessingRecord::findEndLocalPreprocessedEntity(SourceLocation Loc) const { | |
| if (SourceMgr.isLoadedSourceLocation(Loc)) | |
| return 0; | |
| auto I = llvm::upper_bound(PreprocessedEntities, Loc, | |
| PPEntityComp<&SourceRange::getBegin>(SourceMgr)); | |
| return I - PreprocessedEntities.begin(); | |
| } | |
| PreprocessingRecord::PPEntityID | |
| PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) { | |
| assert(Entity); | |
| SourceLocation BeginLoc = Entity->getSourceRange().getBegin(); | |
| if (isa<MacroDefinitionRecord>(Entity)) { | |
| assert((PreprocessedEntities.empty() || | |
| !SourceMgr.isBeforeInTranslationUnit( | |
| BeginLoc, | |
| PreprocessedEntities.back()->getSourceRange().getBegin())) && | |
| "a macro definition was encountered out-of-order"); | |
| PreprocessedEntities.push_back(Entity); | |
| return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false); | |
| } | |
| // Check normal case, this entity begin location is after the previous one. | |
| if (PreprocessedEntities.empty() || | |
| !SourceMgr.isBeforeInTranslationUnit(BeginLoc, | |
| PreprocessedEntities.back()->getSourceRange().getBegin())) { | |
| PreprocessedEntities.push_back(Entity); | |
| return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false); | |
| } | |
| // The entity's location is not after the previous one; this can happen with | |
| // include directives that form the filename using macros, e.g: | |
| // "#include MACRO(STUFF)" | |
| // or with macro expansions inside macro arguments where the arguments are | |
| // not expanded in the same order as listed, e.g: | |
| // \code | |
| // #define M1 1 | |
| // #define M2 2 | |
| // #define FM(x,y) y x | |
| // FM(M1, M2) | |
| // \endcode | |
| using pp_iter = std::vector<PreprocessedEntity *>::iterator; | |
| // Usually there are few macro expansions when defining the filename, do a | |
| // linear search for a few entities. | |
| unsigned count = 0; | |
| for (pp_iter RI = PreprocessedEntities.end(), | |
| Begin = PreprocessedEntities.begin(); | |
| RI != Begin && count < 4; --RI, ++count) { | |
| pp_iter I = RI; | |
| --I; | |
| if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc, | |
| (*I)->getSourceRange().getBegin())) { | |
| pp_iter insertI = PreprocessedEntities.insert(RI, Entity); | |
| return getPPEntityID(insertI - PreprocessedEntities.begin(), | |
| /*isLoaded=*/false); | |
| } | |
| } | |
| // Linear search unsuccessful. Do a binary search. | |
| pp_iter I = | |
| llvm::upper_bound(PreprocessedEntities, BeginLoc, | |
| PPEntityComp<&SourceRange::getBegin>(SourceMgr)); | |
| pp_iter insertI = PreprocessedEntities.insert(I, Entity); | |
| return getPPEntityID(insertI - PreprocessedEntities.begin(), | |
| /*isLoaded=*/false); | |
| } | |
| void PreprocessingRecord::SetExternalSource( | |
| ExternalPreprocessingRecordSource &Source) { | |
| assert(!ExternalSource && | |
| "Preprocessing record already has an external source"); | |
| ExternalSource = &Source; | |
| } | |
| unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) { | |
| unsigned Result = LoadedPreprocessedEntities.size(); | |
| LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size() | |
| + NumEntities); | |
| return Result; | |
| } | |
| unsigned PreprocessingRecord::allocateSkippedRanges(unsigned NumRanges) { | |
| unsigned Result = SkippedRanges.size(); | |
| SkippedRanges.resize(SkippedRanges.size() + NumRanges); | |
| SkippedRangesAllLoaded = false; | |
| return Result; | |
| } | |
| void PreprocessingRecord::ensureSkippedRangesLoaded() { | |
| if (SkippedRangesAllLoaded || !ExternalSource) | |
| return; | |
| for (unsigned Index = 0; Index != SkippedRanges.size(); ++Index) { | |
| if (SkippedRanges[Index].isInvalid()) | |
| SkippedRanges[Index] = ExternalSource->ReadSkippedRange(Index); | |
| } | |
| SkippedRangesAllLoaded = true; | |
| } | |
| void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro, | |
| MacroDefinitionRecord *Def) { | |
| MacroDefinitions[Macro] = Def; | |
| } | |
| /// Retrieve the preprocessed entity at the given ID. | |
| PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){ | |
| if (PPID.ID < 0) { | |
| unsigned Index = -PPID.ID - 1; | |
| assert(Index < LoadedPreprocessedEntities.size() && | |
| "Out-of bounds loaded preprocessed entity"); | |
| return getLoadedPreprocessedEntity(Index); | |
| } | |
| if (PPID.ID == 0) | |
| return nullptr; | |
| unsigned Index = PPID.ID - 1; | |
| assert(Index < PreprocessedEntities.size() && | |
| "Out-of bounds local preprocessed entity"); | |
| return PreprocessedEntities[Index]; | |
| } | |
| /// Retrieve the loaded preprocessed entity at the given index. | |
| PreprocessedEntity * | |
| PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) { | |
| assert(Index < LoadedPreprocessedEntities.size() && | |
| "Out-of bounds loaded preprocessed entity"); | |
| assert(ExternalSource && "No external source to load from"); | |
| PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index]; | |
| if (!Entity) { | |
| Entity = ExternalSource->ReadPreprocessedEntity(Index); | |
| if (!Entity) // Failed to load. | |
| Entity = new (*this) | |
| PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange()); | |
| } | |
| return Entity; | |
| } | |
| MacroDefinitionRecord * | |
| PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) { | |
| return MacroDefinitions.lookup(MI); | |
| } | |
| void PreprocessingRecord::addMacroExpansion(const Token &Id, | |
| const MacroInfo *MI, | |
| SourceRange Range) { | |
| // We don't record nested macro expansions. | |
| if (Id.getLocation().isMacroID()) | |
| return; | |
| if (MI->isBuiltinMacro()) | |
| addPreprocessedEntity(new (*this) | |
| MacroExpansion(Id.getIdentifierInfo(), Range)); | |
| else if (MacroDefinitionRecord *Def = findMacroDefinition(MI)) | |
| addPreprocessedEntity(new (*this) MacroExpansion(Def, Range)); | |
| } | |
| void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok, | |
| const MacroDefinition &MD) { | |
| // This is not actually a macro expansion but record it as a macro reference. | |
| if (MD) | |
| addMacroExpansion(MacroNameTok, MD.getMacroInfo(), | |
| MacroNameTok.getLocation()); | |
| } | |
| void PreprocessingRecord::Elifdef(SourceLocation Loc, const Token &MacroNameTok, | |
| const MacroDefinition &MD) { | |
| // This is not actually a macro expansion but record it as a macro reference. | |
| if (MD) | |
| addMacroExpansion(MacroNameTok, MD.getMacroInfo(), | |
| MacroNameTok.getLocation()); | |
| } | |
| void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok, | |
| const MacroDefinition &MD) { | |
| // This is not actually a macro expansion but record it as a macro reference. | |
| if (MD) | |
| addMacroExpansion(MacroNameTok, MD.getMacroInfo(), | |
| MacroNameTok.getLocation()); | |
| } | |
| void PreprocessingRecord::Elifndef(SourceLocation Loc, | |
| const Token &MacroNameTok, | |
| const MacroDefinition &MD) { | |
| // This is not actually a macro expansion but record it as a macro reference. | |
| if (MD) | |
| addMacroExpansion(MacroNameTok, MD.getMacroInfo(), | |
| MacroNameTok.getLocation()); | |
| } | |
| void PreprocessingRecord::Defined(const Token &MacroNameTok, | |
| const MacroDefinition &MD, | |
| SourceRange Range) { | |
| // This is not actually a macro expansion but record it as a macro reference. | |
| if (MD) | |
| addMacroExpansion(MacroNameTok, MD.getMacroInfo(), | |
| MacroNameTok.getLocation()); | |
| } | |
| void PreprocessingRecord::SourceRangeSkipped(SourceRange Range, | |
| SourceLocation EndifLoc) { | |
| assert(Range.isValid()); | |
| SkippedRanges.emplace_back(Range.getBegin(), EndifLoc); | |
| } | |
| void PreprocessingRecord::MacroExpands(const Token &Id, | |
| const MacroDefinition &MD, | |
| SourceRange Range, | |
| const MacroArgs *Args) { | |
| addMacroExpansion(Id, MD.getMacroInfo(), Range); | |
| } | |
| void PreprocessingRecord::MacroDefined(const Token &Id, | |
| const MacroDirective *MD) { | |
| const MacroInfo *MI = MD->getMacroInfo(); | |
| SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc()); | |
| MacroDefinitionRecord *Def = | |
| new (*this) MacroDefinitionRecord(Id.getIdentifierInfo(), R); | |
| addPreprocessedEntity(Def); | |
| MacroDefinitions[MI] = Def; | |
| } | |
| void PreprocessingRecord::MacroUndefined(const Token &Id, | |
| const MacroDefinition &MD, | |
| const MacroDirective *Undef) { | |
| MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); }); | |
| } | |
| void PreprocessingRecord::InclusionDirective( | |
| SourceLocation HashLoc, const Token &IncludeTok, StringRef FileName, | |
| bool IsAngled, CharSourceRange FilenameRange, OptionalFileEntryRef File, | |
| StringRef SearchPath, StringRef RelativePath, const Module *SuggestedModule, | |
| bool ModuleImported, SrcMgr::CharacteristicKind FileType) { | |
| InclusionDirective::InclusionKind Kind = InclusionDirective::Include; | |
| switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) { | |
| case tok::pp_include: | |
| Kind = InclusionDirective::Include; | |
| break; | |
| case tok::pp_import: | |
| Kind = InclusionDirective::Import; | |
| break; | |
| case tok::pp_include_next: | |
| Kind = InclusionDirective::IncludeNext; | |
| break; | |
| case tok::pp___include_macros: | |
| Kind = InclusionDirective::IncludeMacros; | |
| break; | |
| default: | |
| llvm_unreachable("Unknown include directive kind"); | |
| } | |
| SourceLocation EndLoc; | |
| if (!IsAngled) { | |
| EndLoc = FilenameRange.getBegin(); | |
| } else { | |
| EndLoc = FilenameRange.getEnd(); | |
| if (FilenameRange.isCharRange()) | |
| EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects | |
| // a token range. | |
| } | |
| clang::InclusionDirective *ID = new (*this) clang::InclusionDirective( | |
| *this, Kind, FileName, !IsAngled, ModuleImported, File, | |
| SourceRange(HashLoc, EndLoc)); | |
| addPreprocessedEntity(ID); | |
| } | |
| size_t PreprocessingRecord::getTotalMemory() const { | |
| return BumpAlloc.getTotalMemory() | |
| + llvm::capacity_in_bytes(MacroDefinitions) | |
| + llvm::capacity_in_bytes(PreprocessedEntities) | |
| + llvm::capacity_in_bytes(LoadedPreprocessedEntities) | |
| + llvm::capacity_in_bytes(SkippedRanges); | |
| } |