1 //===--- PreprocessingRecord.cpp - Record of Preprocessing ------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the PreprocessingRecord class, which maintains a record
11 // of what occurred during preprocessing, and its helpers.
13 //===----------------------------------------------------------------------===//
14 #include "clang/Lex/PreprocessingRecord.h"
15 #include "clang/Lex/MacroInfo.h"
16 #include "clang/Lex/Token.h"
17 #include "llvm/Support/Capacity.h"
18 #include "llvm/Support/ErrorHandling.h"
20 using namespace clang;
22 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }
25 InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
28 bool InQuotes, bool ImportedModule,
29 const FileEntry *File,
31 : PreprocessingDirective(InclusionDirectiveKind, Range),
32 InQuotes(InQuotes), Kind(Kind), ImportedModule(ImportedModule), File(File)
35 = (char*)PPRec.Allocate(FileName.size() + 1, llvm::alignOf<char>());
36 memcpy(Memory, FileName.data(), FileName.size());
37 Memory[FileName.size()] = 0;
38 this->FileName = StringRef(Memory, FileName.size());
41 PreprocessingRecord::PreprocessingRecord(SourceManager &SM)
43 ExternalSource(nullptr) {
46 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
47 /// that source range \p Range encompasses.
48 llvm::iterator_range<PreprocessingRecord::iterator>
49 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
50 if (Range.isInvalid())
51 return llvm::make_range(iterator(), iterator());
53 if (CachedRangeQuery.Range == Range) {
54 return llvm::make_range(iterator(this, CachedRangeQuery.Result.first),
55 iterator(this, CachedRangeQuery.Result.second));
58 std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range);
60 CachedRangeQuery.Range = Range;
61 CachedRangeQuery.Result = Res;
63 return llvm::make_range(iterator(this, Res.first),
64 iterator(this, Res.second));
67 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
69 assert(FID.isValid());
73 SourceLocation Loc = PPE->getSourceRange().getBegin();
77 return SM.isInFileID(SM.getFileLoc(Loc), FID);
80 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
81 /// points to is coming from the file \arg FID.
83 /// Can be used to avoid implicit deserializations of preallocated
84 /// preprocessed entities if we only care about entities of a specific file
85 /// and not from files \#included in the range given at
86 /// \see getPreprocessedEntitiesInRange.
87 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
91 int Pos = std::distance(iterator(this, 0), PPEI);
93 if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) {
94 assert(0 && "Out-of bounds loaded preprocessed entity");
97 assert(ExternalSource && "No external source to load from");
98 unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;
99 if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
100 return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);
102 // See if the external source can see if the entity is in the file without
104 Optional<bool> IsInFile =
105 ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
106 if (IsInFile.hasValue())
107 return IsInFile.getValue();
109 // The external source did not provide a definite answer, go and deserialize
110 // the entity to check it.
111 return isPreprocessedEntityIfInFileID(
112 getLoadedPreprocessedEntity(LoadedIndex),
116 if (unsigned(Pos) >= PreprocessedEntities.size()) {
117 assert(0 && "Out-of bounds local preprocessed entity");
120 return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
124 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
125 /// that source range \arg R encompasses.
127 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
128 assert(Range.isValid());
129 assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
131 std::pair<unsigned, unsigned>
132 Local = findLocalPreprocessedEntitiesInRange(Range);
134 // Check if range spans local entities.
135 if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
136 return std::make_pair(Local.first, Local.second);
138 std::pair<unsigned, unsigned>
139 Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
141 // Check if range spans local entities.
142 if (Loaded.first == Loaded.second)
143 return std::make_pair(Local.first, Local.second);
145 unsigned TotalLoaded = LoadedPreprocessedEntities.size();
147 // Check if range spans loaded entities.
148 if (Local.first == Local.second)
149 return std::make_pair(int(Loaded.first)-TotalLoaded,
150 int(Loaded.second)-TotalLoaded);
152 // Range spands loaded and local entities.
153 return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
156 std::pair<unsigned, unsigned>
157 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
158 SourceRange Range) const {
159 if (Range.isInvalid())
160 return std::make_pair(0,0);
161 assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
163 unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
164 unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
165 return std::make_pair(Begin, End);
170 template <SourceLocation (SourceRange::*getRangeLoc)() const>
171 struct PPEntityComp {
172 const SourceManager &SM;
174 explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
176 bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
177 SourceLocation LHS = getLoc(L);
178 SourceLocation RHS = getLoc(R);
179 return SM.isBeforeInTranslationUnit(LHS, RHS);
182 bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
183 SourceLocation LHS = getLoc(L);
184 return SM.isBeforeInTranslationUnit(LHS, RHS);
187 bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
188 SourceLocation RHS = getLoc(R);
189 return SM.isBeforeInTranslationUnit(LHS, RHS);
192 SourceLocation getLoc(PreprocessedEntity *PPE) const {
193 SourceRange Range = PPE->getSourceRange();
194 return (Range.*getRangeLoc)();
200 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
201 SourceLocation Loc) const {
202 if (SourceMgr.isLoadedSourceLocation(Loc))
205 size_t Count = PreprocessedEntities.size();
207 std::vector<PreprocessedEntity *>::const_iterator
208 First = PreprocessedEntities.begin();
209 std::vector<PreprocessedEntity *>::const_iterator I;
211 // Do a binary search manually instead of using std::lower_bound because
212 // The end locations of entities may be unordered (when a macro expansion
213 // is inside another macro argument), but for this case it is not important
214 // whether we get the first macro expansion or its containing macro.
218 std::advance(I, Half);
219 if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
223 Count = Count - Half - 1;
228 return First - PreprocessedEntities.begin();
231 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
232 SourceLocation Loc) const {
233 if (SourceMgr.isLoadedSourceLocation(Loc))
236 std::vector<PreprocessedEntity *>::const_iterator
237 I = std::upper_bound(PreprocessedEntities.begin(),
238 PreprocessedEntities.end(),
240 PPEntityComp<&SourceRange::getBegin>(SourceMgr));
241 return I - PreprocessedEntities.begin();
244 PreprocessingRecord::PPEntityID
245 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
247 SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
249 if (isa<MacroDefinitionRecord>(Entity)) {
250 assert((PreprocessedEntities.empty() ||
251 !SourceMgr.isBeforeInTranslationUnit(
253 PreprocessedEntities.back()->getSourceRange().getBegin())) &&
254 "a macro definition was encountered out-of-order");
255 PreprocessedEntities.push_back(Entity);
256 return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
259 // Check normal case, this entity begin location is after the previous one.
260 if (PreprocessedEntities.empty() ||
261 !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
262 PreprocessedEntities.back()->getSourceRange().getBegin())) {
263 PreprocessedEntities.push_back(Entity);
264 return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
267 // The entity's location is not after the previous one; this can happen with
268 // include directives that form the filename using macros, e.g:
269 // "#include MACRO(STUFF)"
270 // or with macro expansions inside macro arguments where the arguments are
271 // not expanded in the same order as listed, e.g:
275 // #define FM(x,y) y x
279 typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
281 // Usually there are few macro expansions when defining the filename, do a
282 // linear search for a few entities.
284 for (pp_iter RI = PreprocessedEntities.end(),
285 Begin = PreprocessedEntities.begin();
286 RI != Begin && count < 4; --RI, ++count) {
289 if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
290 (*I)->getSourceRange().getBegin())) {
291 pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
292 return getPPEntityID(insertI - PreprocessedEntities.begin(),
297 // Linear search unsuccessful. Do a binary search.
298 pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
299 PreprocessedEntities.end(),
301 PPEntityComp<&SourceRange::getBegin>(SourceMgr));
302 pp_iter insertI = PreprocessedEntities.insert(I, Entity);
303 return getPPEntityID(insertI - PreprocessedEntities.begin(),
307 void PreprocessingRecord::SetExternalSource(
308 ExternalPreprocessingRecordSource &Source) {
309 assert(!ExternalSource &&
310 "Preprocessing record already has an external source");
311 ExternalSource = &Source;
314 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
315 unsigned Result = LoadedPreprocessedEntities.size();
316 LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
321 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
322 MacroDefinitionRecord *Def) {
323 MacroDefinitions[Macro] = Def;
326 /// \brief Retrieve the preprocessed entity at the given ID.
327 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
329 unsigned Index = -PPID.ID - 1;
330 assert(Index < LoadedPreprocessedEntities.size() &&
331 "Out-of bounds loaded preprocessed entity");
332 return getLoadedPreprocessedEntity(Index);
337 unsigned Index = PPID.ID - 1;
338 assert(Index < PreprocessedEntities.size() &&
339 "Out-of bounds local preprocessed entity");
340 return PreprocessedEntities[Index];
343 /// \brief Retrieve the loaded preprocessed entity at the given index.
345 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
346 assert(Index < LoadedPreprocessedEntities.size() &&
347 "Out-of bounds loaded preprocessed entity");
348 assert(ExternalSource && "No external source to load from");
349 PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
351 Entity = ExternalSource->ReadPreprocessedEntity(Index);
352 if (!Entity) // Failed to load.
354 PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
359 MacroDefinitionRecord *
360 PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
361 llvm::DenseMap<const MacroInfo *, MacroDefinitionRecord *>::iterator Pos =
362 MacroDefinitions.find(MI);
363 if (Pos == MacroDefinitions.end())
369 void PreprocessingRecord::addMacroExpansion(const Token &Id,
372 // We don't record nested macro expansions.
373 if (Id.getLocation().isMacroID())
376 if (MI->isBuiltinMacro())
377 addPreprocessedEntity(new (*this)
378 MacroExpansion(Id.getIdentifierInfo(), Range));
379 else if (MacroDefinitionRecord *Def = findMacroDefinition(MI))
380 addPreprocessedEntity(new (*this) MacroExpansion(Def, Range));
383 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,
384 const MacroDefinition &MD) {
385 // This is not actually a macro expansion but record it as a macro reference.
387 addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
388 MacroNameTok.getLocation());
391 void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
392 const MacroDefinition &MD) {
393 // This is not actually a macro expansion but record it as a macro reference.
395 addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
396 MacroNameTok.getLocation());
399 void PreprocessingRecord::Defined(const Token &MacroNameTok,
400 const MacroDefinition &MD,
402 // This is not actually a macro expansion but record it as a macro reference.
404 addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
405 MacroNameTok.getLocation());
408 void PreprocessingRecord::SourceRangeSkipped(SourceRange Range) {
409 SkippedRanges.push_back(Range);
412 void PreprocessingRecord::MacroExpands(const Token &Id,
413 const MacroDefinition &MD,
415 const MacroArgs *Args) {
416 addMacroExpansion(Id, MD.getMacroInfo(), Range);
419 void PreprocessingRecord::MacroDefined(const Token &Id,
420 const MacroDirective *MD) {
421 const MacroInfo *MI = MD->getMacroInfo();
422 SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
423 MacroDefinitionRecord *Def =
424 new (*this) MacroDefinitionRecord(Id.getIdentifierInfo(), R);
425 addPreprocessedEntity(Def);
426 MacroDefinitions[MI] = Def;
429 void PreprocessingRecord::MacroUndefined(const Token &Id,
430 const MacroDefinition &MD) {
431 MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });
434 void PreprocessingRecord::InclusionDirective(
435 SourceLocation HashLoc,
436 const clang::Token &IncludeTok,
439 CharSourceRange FilenameRange,
440 const FileEntry *File,
441 StringRef SearchPath,
442 StringRef RelativePath,
443 const Module *Imported) {
444 InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
446 switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
447 case tok::pp_include:
448 Kind = InclusionDirective::Include;
452 Kind = InclusionDirective::Import;
455 case tok::pp_include_next:
456 Kind = InclusionDirective::IncludeNext;
459 case tok::pp___include_macros:
460 Kind = InclusionDirective::IncludeMacros;
464 llvm_unreachable("Unknown include directive kind");
467 SourceLocation EndLoc;
469 EndLoc = FilenameRange.getBegin();
471 EndLoc = FilenameRange.getEnd();
472 if (FilenameRange.isCharRange())
473 EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
476 clang::InclusionDirective *ID
477 = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
479 File, SourceRange(HashLoc, EndLoc));
480 addPreprocessedEntity(ID);
483 size_t PreprocessingRecord::getTotalMemory() const {
484 return BumpAlloc.getTotalMemory()
485 + llvm::capacity_in_bytes(MacroDefinitions)
486 + llvm::capacity_in_bytes(PreprocessedEntities)
487 + llvm::capacity_in_bytes(LoadedPreprocessedEntities);