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/ErrorHandling.h"
18 #include "llvm/Support/Capacity.h"
20 using namespace clang;
22 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }
25 InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
28 bool InQuotes, const FileEntry *File,
30 : PreprocessingDirective(InclusionDirectiveKind, Range),
31 InQuotes(InQuotes), Kind(Kind), File(File)
34 = (char*)PPRec.Allocate(FileName.size() + 1, llvm::alignOf<char>());
35 memcpy(Memory, FileName.data(), FileName.size());
36 Memory[FileName.size()] = 0;
37 this->FileName = StringRef(Memory, FileName.size());
40 PreprocessingRecord::PreprocessingRecord(SourceManager &SM,
41 bool RecordConditionalDirectives)
43 RecordCondDirectives(RecordConditionalDirectives), CondDirectiveNextIdx(0),
46 if (RecordCondDirectives)
47 CondDirectiveStack.push_back(CondDirectiveNextIdx++);
50 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
51 /// that source range \arg R encompasses.
52 std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
53 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
54 if (Range.isInvalid())
55 return std::make_pair(iterator(), iterator());
57 if (CachedRangeQuery.Range == Range) {
58 return std::make_pair(iterator(this, CachedRangeQuery.Result.first),
59 iterator(this, CachedRangeQuery.Result.second));
62 std::pair<PPEntityID, PPEntityID>
63 Res = getPreprocessedEntitiesInRangeSlow(Range);
65 CachedRangeQuery.Range = Range;
66 CachedRangeQuery.Result = Res;
68 return std::make_pair(iterator(this, Res.first), iterator(this, Res.second));
71 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
73 assert(!FID.isInvalid());
77 SourceLocation Loc = PPE->getSourceRange().getBegin();
81 if (SM.isInFileID(SM.getFileLoc(Loc), FID))
87 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
88 /// points to is coming from the file \arg FID.
90 /// Can be used to avoid implicit deserializations of preallocated
91 /// preprocessed entities if we only care about entities of a specific file
92 /// and not from files #included in the range given at
93 /// \see getPreprocessedEntitiesInRange.
94 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
98 PPEntityID PPID = PPEI.Position;
100 assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
101 "Out-of bounds loaded preprocessed entity");
102 assert(ExternalSource && "No external source to load from");
103 unsigned LoadedIndex = LoadedPreprocessedEntities.size()+PPID;
104 if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
105 return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);
107 // See if the external source can see if the entity is in the file without
110 IsInFile = ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
111 if (IsInFile.hasValue())
112 return IsInFile.getValue();
114 // The external source did not provide a definite answer, go and deserialize
115 // the entity to check it.
116 return isPreprocessedEntityIfInFileID(
117 getLoadedPreprocessedEntity(LoadedIndex),
121 assert(unsigned(PPID) < PreprocessedEntities.size() &&
122 "Out-of bounds local preprocessed entity");
123 return isPreprocessedEntityIfInFileID(PreprocessedEntities[PPID],
127 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
128 /// that source range \arg R encompasses.
129 std::pair<PreprocessingRecord::PPEntityID, PreprocessingRecord::PPEntityID>
130 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
131 assert(Range.isValid());
132 assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
134 std::pair<unsigned, unsigned>
135 Local = findLocalPreprocessedEntitiesInRange(Range);
137 // Check if range spans local entities.
138 if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
139 return std::make_pair(Local.first, Local.second);
141 std::pair<unsigned, unsigned>
142 Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
144 // Check if range spans local entities.
145 if (Loaded.first == Loaded.second)
146 return std::make_pair(Local.first, Local.second);
148 unsigned TotalLoaded = LoadedPreprocessedEntities.size();
150 // Check if range spans loaded entities.
151 if (Local.first == Local.second)
152 return std::make_pair(int(Loaded.first)-TotalLoaded,
153 int(Loaded.second)-TotalLoaded);
155 // Range spands loaded and local entities.
156 return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
159 std::pair<unsigned, unsigned>
160 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
161 SourceRange Range) const {
162 if (Range.isInvalid())
163 return std::make_pair(0,0);
164 assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
166 unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
167 unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
168 return std::make_pair(Begin, End);
173 template <SourceLocation (SourceRange::*getRangeLoc)() const>
174 struct PPEntityComp {
175 const SourceManager &SM;
177 explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
179 bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
180 SourceLocation LHS = getLoc(L);
181 SourceLocation RHS = getLoc(R);
182 return SM.isBeforeInTranslationUnit(LHS, RHS);
185 bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
186 SourceLocation LHS = getLoc(L);
187 return SM.isBeforeInTranslationUnit(LHS, RHS);
190 bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
191 SourceLocation RHS = getLoc(R);
192 return SM.isBeforeInTranslationUnit(LHS, RHS);
195 SourceLocation getLoc(PreprocessedEntity *PPE) const {
196 SourceRange Range = PPE->getSourceRange();
197 return (Range.*getRangeLoc)();
203 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
204 SourceLocation Loc) const {
205 if (SourceMgr.isLoadedSourceLocation(Loc))
208 size_t Count = PreprocessedEntities.size();
210 std::vector<PreprocessedEntity *>::const_iterator
211 First = PreprocessedEntities.begin();
212 std::vector<PreprocessedEntity *>::const_iterator I;
214 // Do a binary search manually instead of using std::lower_bound because
215 // The end locations of entities may be unordered (when a macro expansion
216 // is inside another macro argument), but for this case it is not important
217 // whether we get the first macro expansion or its containing macro.
221 std::advance(I, Half);
222 if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
226 Count = Count - Half - 1;
231 return First - PreprocessedEntities.begin();
234 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
235 SourceLocation Loc) const {
236 if (SourceMgr.isLoadedSourceLocation(Loc))
239 std::vector<PreprocessedEntity *>::const_iterator
240 I = std::upper_bound(PreprocessedEntities.begin(),
241 PreprocessedEntities.end(),
243 PPEntityComp<&SourceRange::getBegin>(SourceMgr));
244 return I - PreprocessedEntities.begin();
247 PreprocessingRecord::PPEntityID
248 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
250 SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
252 if (!isa<class InclusionDirective>(Entity)) {
253 assert((PreprocessedEntities.empty() ||
254 !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
255 PreprocessedEntities.back()->getSourceRange().getBegin())) &&
256 "a macro directive was encountered out-of-order");
257 PreprocessedEntities.push_back(Entity);
258 return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
261 // Check normal case, this entity begin location is after the previous one.
262 if (PreprocessedEntities.empty() ||
263 !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
264 PreprocessedEntities.back()->getSourceRange().getBegin())) {
265 PreprocessedEntities.push_back(Entity);
266 return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
269 // The entity's location is not after the previous one; this can happen with
270 // include directives that form the filename using macros, e.g:
271 // "#include MACRO(STUFF)".
273 typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
275 // Usually there are few macro expansions when defining the filename, do a
276 // linear search for a few entities.
278 for (pp_iter RI = PreprocessedEntities.end(),
279 Begin = PreprocessedEntities.begin();
280 RI != Begin && count < 4; --RI, ++count) {
283 if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
284 (*I)->getSourceRange().getBegin())) {
285 pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
286 return getPPEntityID(insertI - PreprocessedEntities.begin(),
291 // Linear search unsuccessful. Do a binary search.
292 pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
293 PreprocessedEntities.end(),
295 PPEntityComp<&SourceRange::getBegin>(SourceMgr));
296 pp_iter insertI = PreprocessedEntities.insert(I, Entity);
297 return getPPEntityID(insertI - PreprocessedEntities.begin(),
301 void PreprocessingRecord::SetExternalSource(
302 ExternalPreprocessingRecordSource &Source) {
303 assert(!ExternalSource &&
304 "Preprocessing record already has an external source");
305 ExternalSource = &Source;
308 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
309 unsigned Result = LoadedPreprocessedEntities.size();
310 LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
315 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
317 MacroDefinitions[Macro] = PPID;
320 /// \brief Retrieve the preprocessed entity at the given ID.
321 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
323 assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
324 "Out-of bounds loaded preprocessed entity");
325 return getLoadedPreprocessedEntity(LoadedPreprocessedEntities.size()+PPID);
327 assert(unsigned(PPID) < PreprocessedEntities.size() &&
328 "Out-of bounds local preprocessed entity");
329 return PreprocessedEntities[PPID];
332 /// \brief Retrieve the loaded preprocessed entity at the given index.
334 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
335 assert(Index < LoadedPreprocessedEntities.size() &&
336 "Out-of bounds loaded preprocessed entity");
337 assert(ExternalSource && "No external source to load from");
338 PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
340 Entity = ExternalSource->ReadPreprocessedEntity(Index);
341 if (!Entity) // Failed to load.
343 PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
348 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
349 llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
350 = MacroDefinitions.find(MI);
351 if (Pos == MacroDefinitions.end())
354 PreprocessedEntity *Entity = getPreprocessedEntity(Pos->second);
355 if (Entity->isInvalid())
357 return cast<MacroDefinition>(Entity);
360 void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
362 // We don't record nested macro expansions.
363 if (Id.getLocation().isMacroID())
366 if (MI->isBuiltinMacro())
367 addPreprocessedEntity(
368 new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
369 else if (MacroDefinition *Def = findMacroDefinition(MI))
370 addPreprocessedEntity(
371 new (*this) MacroExpansion(Def, Range));
374 void PreprocessingRecord::MacroDefined(const Token &Id,
375 const MacroInfo *MI) {
376 SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
378 = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
379 MacroDefinitions[MI] = addPreprocessedEntity(Def);
382 void PreprocessingRecord::MacroUndefined(const Token &Id,
383 const MacroInfo *MI) {
384 MacroDefinitions.erase(MI);
387 void PreprocessingRecord::InclusionDirective(
388 SourceLocation HashLoc,
389 const clang::Token &IncludeTok,
392 const FileEntry *File,
393 clang::SourceLocation EndLoc,
394 StringRef SearchPath,
395 StringRef RelativePath) {
396 InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
398 switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
399 case tok::pp_include:
400 Kind = InclusionDirective::Include;
404 Kind = InclusionDirective::Import;
407 case tok::pp_include_next:
408 Kind = InclusionDirective::IncludeNext;
411 case tok::pp___include_macros:
412 Kind = InclusionDirective::IncludeMacros;
416 llvm_unreachable("Unknown include directive kind");
419 clang::InclusionDirective *ID
420 = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
421 File, SourceRange(HashLoc, EndLoc));
422 addPreprocessedEntity(ID);
425 bool PreprocessingRecord::rangeIntersectsConditionalDirective(
426 SourceRange Range) const {
427 if (Range.isInvalid())
430 CondDirectiveLocsTy::const_iterator
431 low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
432 Range.getBegin(), CondDirectiveLoc::Comp(SourceMgr));
433 if (low == CondDirectiveLocs.end())
436 if (SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), low->getLoc()))
439 CondDirectiveLocsTy::const_iterator
440 upp = std::upper_bound(low, CondDirectiveLocs.end(),
441 Range.getEnd(), CondDirectiveLoc::Comp(SourceMgr));
443 if (upp != CondDirectiveLocs.end())
444 uppIdx = upp->getIdx();
448 return low->getIdx() != uppIdx;
451 unsigned PreprocessingRecord::findCondDirectiveIdx(SourceLocation Loc) const {
455 CondDirectiveLocsTy::const_iterator
456 low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
457 Loc, CondDirectiveLoc::Comp(SourceMgr));
458 if (low == CondDirectiveLocs.end())
460 return low->getIdx();
463 void PreprocessingRecord::addCondDirectiveLoc(CondDirectiveLoc DirLoc) {
464 // Ignore directives in system headers.
465 if (SourceMgr.isInSystemHeader(DirLoc.getLoc()))
468 assert(CondDirectiveLocs.empty() ||
469 SourceMgr.isBeforeInTranslationUnit(CondDirectiveLocs.back().getLoc(),
471 CondDirectiveLocs.push_back(DirLoc);
474 void PreprocessingRecord::If(SourceLocation Loc, SourceRange ConditionRange) {
475 if (RecordCondDirectives) {
476 addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
477 CondDirectiveStack.push_back(CondDirectiveNextIdx++);
481 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok) {
482 if (RecordCondDirectives) {
483 addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
484 CondDirectiveStack.push_back(CondDirectiveNextIdx++);
488 void PreprocessingRecord::Ifndef(SourceLocation Loc,const Token &MacroNameTok) {
489 if (RecordCondDirectives) {
490 addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
491 CondDirectiveStack.push_back(CondDirectiveNextIdx++);
495 void PreprocessingRecord::Elif(SourceLocation Loc, SourceRange ConditionRange,
496 SourceLocation IfLoc) {
497 if (RecordCondDirectives)
498 addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
501 void PreprocessingRecord::Else(SourceLocation Loc, SourceLocation IfLoc) {
502 if (RecordCondDirectives)
503 addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
506 void PreprocessingRecord::Endif(SourceLocation Loc, SourceLocation IfLoc) {
507 if (RecordCondDirectives) {
508 addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
509 assert(!CondDirectiveStack.empty());
510 CondDirectiveStack.pop_back();
514 size_t PreprocessingRecord::getTotalMemory() const {
515 return BumpAlloc.getTotalMemory()
516 + llvm::capacity_in_bytes(MacroDefinitions)
517 + llvm::capacity_in_bytes(PreprocessedEntities)
518 + llvm::capacity_in_bytes(LoadedPreprocessedEntities);