blob: 115256db480958828b2d549ac6276af68d1a0ec4 [file] [log] [blame]
//===- 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/Optional.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Support/Capacity.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstring>
#include <iterator>
#include <utility>
#include <vector>
using namespace clang;
ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() =
default;
InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
InclusionKind Kind, StringRef FileName,
bool InQuotes, bool ImportedModule,
const FileEntry *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.
Optional<bool> IsInFile =
ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
if (IsInFile.hasValue())
return IsInFile.getValue();
// 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) {
llvm::DenseMap<const MacroInfo *, MacroDefinitionRecord *>::iterator Pos =
MacroDefinitions.find(MI);
if (Pos == MacroDefinitions.end())
return nullptr;
return Pos->second;
}
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::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::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,
const FileEntry *File,
StringRef SearchPath,
StringRef RelativePath,
const Module *Imported,
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,
(bool)Imported, 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);
}