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)
46 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
47 /// that source range \p Range encompasses.
48 std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
49 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
50 if (Range.isInvalid())
51 return std::make_pair(iterator(), iterator());
53 if (CachedRangeQuery.Range == Range) {
54 return std::make_pair(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 std::make_pair(iterator(this, Res.first), iterator(this, Res.second));
66 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
68 assert(!FID.isInvalid());
72 SourceLocation Loc = PPE->getSourceRange().getBegin();
76 if (SM.isInFileID(SM.getFileLoc(Loc), FID))
82 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
83 /// points to is coming from the file \arg FID.
85 /// Can be used to avoid implicit deserializations of preallocated
86 /// preprocessed entities if we only care about entities of a specific file
87 /// and not from files \#included in the range given at
88 /// \see getPreprocessedEntitiesInRange.
89 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
93 int Pos = PPEI.Position;
95 if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) {
96 assert(0 && "Out-of bounds loaded preprocessed entity");
99 assert(ExternalSource && "No external source to load from");
100 unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;
101 if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
102 return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);
104 // See if the external source can see if the entity is in the file without
106 Optional<bool> IsInFile =
107 ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
108 if (IsInFile.hasValue())
109 return IsInFile.getValue();
111 // The external source did not provide a definite answer, go and deserialize
112 // the entity to check it.
113 return isPreprocessedEntityIfInFileID(
114 getLoadedPreprocessedEntity(LoadedIndex),
118 if (unsigned(Pos) >= PreprocessedEntities.size()) {
119 assert(0 && "Out-of bounds local preprocessed entity");
122 return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
126 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
127 /// that source range \arg R encompasses.
129 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
130 assert(Range.isValid());
131 assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
133 std::pair<unsigned, unsigned>
134 Local = findLocalPreprocessedEntitiesInRange(Range);
136 // Check if range spans local entities.
137 if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
138 return std::make_pair(Local.first, Local.second);
140 std::pair<unsigned, unsigned>
141 Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
143 // Check if range spans local entities.
144 if (Loaded.first == Loaded.second)
145 return std::make_pair(Local.first, Local.second);
147 unsigned TotalLoaded = LoadedPreprocessedEntities.size();
149 // Check if range spans loaded entities.
150 if (Local.first == Local.second)
151 return std::make_pair(int(Loaded.first)-TotalLoaded,
152 int(Loaded.second)-TotalLoaded);
154 // Range spands loaded and local entities.
155 return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
158 std::pair<unsigned, unsigned>
159 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
160 SourceRange Range) const {
161 if (Range.isInvalid())
162 return std::make_pair(0,0);
163 assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
165 unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
166 unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
167 return std::make_pair(Begin, End);
172 template <SourceLocation (SourceRange::*getRangeLoc)() const>
173 struct PPEntityComp {
174 const SourceManager &SM;
176 explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
178 bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
179 SourceLocation LHS = getLoc(L);
180 SourceLocation RHS = getLoc(R);
181 return SM.isBeforeInTranslationUnit(LHS, RHS);
184 bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
185 SourceLocation LHS = getLoc(L);
186 return SM.isBeforeInTranslationUnit(LHS, RHS);
189 bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
190 SourceLocation RHS = getLoc(R);
191 return SM.isBeforeInTranslationUnit(LHS, RHS);
194 SourceLocation getLoc(PreprocessedEntity *PPE) const {
195 SourceRange Range = PPE->getSourceRange();
196 return (Range.*getRangeLoc)();
202 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
203 SourceLocation Loc) const {
204 if (SourceMgr.isLoadedSourceLocation(Loc))
207 size_t Count = PreprocessedEntities.size();
209 std::vector<PreprocessedEntity *>::const_iterator
210 First = PreprocessedEntities.begin();
211 std::vector<PreprocessedEntity *>::const_iterator I;
213 // Do a binary search manually instead of using std::lower_bound because
214 // The end locations of entities may be unordered (when a macro expansion
215 // is inside another macro argument), but for this case it is not important
216 // whether we get the first macro expansion or its containing macro.
220 std::advance(I, Half);
221 if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
225 Count = Count - Half - 1;
230 return First - PreprocessedEntities.begin();
233 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
234 SourceLocation Loc) const {
235 if (SourceMgr.isLoadedSourceLocation(Loc))
238 std::vector<PreprocessedEntity *>::const_iterator
239 I = std::upper_bound(PreprocessedEntities.begin(),
240 PreprocessedEntities.end(),
242 PPEntityComp<&SourceRange::getBegin>(SourceMgr));
243 return I - PreprocessedEntities.begin();
246 PreprocessingRecord::PPEntityID
247 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
249 SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
251 if (isa<MacroDefinition>(Entity)) {
252 assert((PreprocessedEntities.empty() ||
253 !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
254 PreprocessedEntities.back()->getSourceRange().getBegin())) &&
255 "a macro definition was encountered out-of-order");
256 PreprocessedEntities.push_back(Entity);
257 return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
260 // Check normal case, this entity begin location is after the previous one.
261 if (PreprocessedEntities.empty() ||
262 !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
263 PreprocessedEntities.back()->getSourceRange().getBegin())) {
264 PreprocessedEntities.push_back(Entity);
265 return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
268 // The entity's location is not after the previous one; this can happen with
269 // include directives that form the filename using macros, e.g:
270 // "#include MACRO(STUFF)"
271 // or with macro expansions inside macro arguments where the arguments are
272 // not expanded in the same order as listed, e.g:
276 // #define FM(x,y) y x
280 typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
282 // Usually there are few macro expansions when defining the filename, do a
283 // linear search for a few entities.
285 for (pp_iter RI = PreprocessedEntities.end(),
286 Begin = PreprocessedEntities.begin();
287 RI != Begin && count < 4; --RI, ++count) {
290 if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
291 (*I)->getSourceRange().getBegin())) {
292 pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
293 return getPPEntityID(insertI - PreprocessedEntities.begin(),
298 // Linear search unsuccessful. Do a binary search.
299 pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
300 PreprocessedEntities.end(),
302 PPEntityComp<&SourceRange::getBegin>(SourceMgr));
303 pp_iter insertI = PreprocessedEntities.insert(I, Entity);
304 return getPPEntityID(insertI - PreprocessedEntities.begin(),
308 void PreprocessingRecord::SetExternalSource(
309 ExternalPreprocessingRecordSource &Source) {
310 assert(!ExternalSource &&
311 "Preprocessing record already has an external source");
312 ExternalSource = &Source;
315 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
316 unsigned Result = LoadedPreprocessedEntities.size();
317 LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
322 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
323 MacroDefinition *Def) {
324 MacroDefinitions[Macro] = Def;
327 /// \brief Retrieve the preprocessed entity at the given ID.
328 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
330 unsigned Index = -PPID.ID - 1;
331 assert(Index < LoadedPreprocessedEntities.size() &&
332 "Out-of bounds loaded preprocessed entity");
333 return getLoadedPreprocessedEntity(Index);
338 unsigned Index = PPID.ID - 1;
339 assert(Index < PreprocessedEntities.size() &&
340 "Out-of bounds local preprocessed entity");
341 return PreprocessedEntities[Index];
344 /// \brief Retrieve the loaded preprocessed entity at the given index.
346 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
347 assert(Index < LoadedPreprocessedEntities.size() &&
348 "Out-of bounds loaded preprocessed entity");
349 assert(ExternalSource && "No external source to load from");
350 PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
352 Entity = ExternalSource->ReadPreprocessedEntity(Index);
353 if (!Entity) // Failed to load.
355 PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
360 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
361 llvm::DenseMap<const MacroInfo *, MacroDefinition *>::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(
378 new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
379 else if (MacroDefinition *Def = findMacroDefinition(MI))
380 addPreprocessedEntity(
381 new (*this) MacroExpansion(Def, Range));
384 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,
385 const MacroDirective *MD) {
386 // This is not actually a macro expansion but record it as a macro reference.
388 addMacroExpansion(MacroNameTok, MD->getMacroInfo(),
389 MacroNameTok.getLocation());
392 void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
393 const MacroDirective *MD) {
394 // This is not actually a macro expansion but record it as a macro reference.
396 addMacroExpansion(MacroNameTok, MD->getMacroInfo(),
397 MacroNameTok.getLocation());
400 void PreprocessingRecord::Defined(const Token &MacroNameTok,
401 const MacroDirective *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::MacroExpands(const Token &Id,const MacroDirective *MD,
410 addMacroExpansion(Id, MD->getMacroInfo(), Range);
413 void PreprocessingRecord::MacroDefined(const Token &Id,
414 const MacroDirective *MD) {
415 const MacroInfo *MI = MD->getMacroInfo();
416 SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
418 = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
419 addPreprocessedEntity(Def);
420 MacroDefinitions[MI] = Def;
423 void PreprocessingRecord::MacroUndefined(const Token &Id,
424 const MacroDirective *MD) {
425 // Note: MI may be null (when #undef'ining an undefined macro).
427 MacroDefinitions.erase(MD->getMacroInfo());
430 void PreprocessingRecord::InclusionDirective(
431 SourceLocation HashLoc,
432 const clang::Token &IncludeTok,
435 CharSourceRange FilenameRange,
436 const FileEntry *File,
437 StringRef SearchPath,
438 StringRef RelativePath,
439 const Module *Imported) {
440 InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
442 switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
443 case tok::pp_include:
444 Kind = InclusionDirective::Include;
448 Kind = InclusionDirective::Import;
451 case tok::pp_include_next:
452 Kind = InclusionDirective::IncludeNext;
455 case tok::pp___include_macros:
456 Kind = InclusionDirective::IncludeMacros;
460 llvm_unreachable("Unknown include directive kind");
463 SourceLocation EndLoc;
465 EndLoc = FilenameRange.getBegin();
467 EndLoc = FilenameRange.getEnd();
468 if (FilenameRange.isCharRange())
469 EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
472 clang::InclusionDirective *ID
473 = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
475 File, SourceRange(HashLoc, EndLoc));
476 addPreprocessedEntity(ID);
479 size_t PreprocessingRecord::getTotalMemory() const {
480 return BumpAlloc.getTotalMemory()
481 + llvm::capacity_in_bytes(MacroDefinitions)
482 + llvm::capacity_in_bytes(PreprocessedEntities)
483 + llvm::capacity_in_bytes(LoadedPreprocessedEntities);