1 //===--- PreprocessingRecord.cpp - Record of Preprocessing ------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 //  This file implements the PreprocessingRecord class, which maintains a record
11 //  of what occurred during preprocessing, and its helpers.
12 //
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"
19 
20 using namespace clang;
21 
~ExternalPreprocessingRecordSource()22 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }
23 
24 
InclusionDirective(PreprocessingRecord & PPRec,InclusionKind Kind,StringRef FileName,bool InQuotes,bool ImportedModule,const FileEntry * File,SourceRange Range)25 InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
26                                        InclusionKind Kind,
27                                        StringRef FileName,
28                                        bool InQuotes, bool ImportedModule,
29                                        const FileEntry *File,
30                                        SourceRange Range)
31   : PreprocessingDirective(InclusionDirectiveKind, Range),
32     InQuotes(InQuotes), Kind(Kind), ImportedModule(ImportedModule), File(File)
33 {
34   char *Memory
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());
39 }
40 
PreprocessingRecord(SourceManager & SM)41 PreprocessingRecord::PreprocessingRecord(SourceManager &SM)
42   : SourceMgr(SM),
43     ExternalSource(nullptr) {
44 }
45 
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>
getPreprocessedEntitiesInRange(SourceRange Range)49 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
50   if (Range.isInvalid())
51     return llvm::make_range(iterator(), iterator());
52 
53   if (CachedRangeQuery.Range == Range) {
54     return llvm::make_range(iterator(this, CachedRangeQuery.Result.first),
55                             iterator(this, CachedRangeQuery.Result.second));
56   }
57 
58   std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range);
59 
60   CachedRangeQuery.Range = Range;
61   CachedRangeQuery.Result = Res;
62 
63   return llvm::make_range(iterator(this, Res.first),
64                           iterator(this, Res.second));
65 }
66 
isPreprocessedEntityIfInFileID(PreprocessedEntity * PPE,FileID FID,SourceManager & SM)67 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
68                                            SourceManager &SM) {
69   assert(FID.isValid());
70   if (!PPE)
71     return false;
72 
73   SourceLocation Loc = PPE->getSourceRange().getBegin();
74   if (Loc.isInvalid())
75     return false;
76 
77   return SM.isInFileID(SM.getFileLoc(Loc), FID);
78 }
79 
80 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
81 /// points to is coming from the file \arg FID.
82 ///
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.
isEntityInFileID(iterator PPEI,FileID FID)87 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
88   if (FID.isInvalid())
89     return false;
90 
91   int Pos = std::distance(iterator(this, 0), PPEI);
92   if (Pos < 0) {
93     if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) {
94       assert(0 && "Out-of bounds loaded preprocessed entity");
95       return false;
96     }
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);
101 
102     // See if the external source can see if the entity is in the file without
103     // deserializing it.
104     Optional<bool> IsInFile =
105         ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
106     if (IsInFile.hasValue())
107       return IsInFile.getValue();
108 
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),
113                                           FID, SourceMgr);
114   }
115 
116   if (unsigned(Pos) >= PreprocessedEntities.size()) {
117     assert(0 && "Out-of bounds local preprocessed entity");
118     return false;
119   }
120   return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
121                                         FID, SourceMgr);
122 }
123 
124 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
125 /// that source range \arg R encompasses.
126 std::pair<int, int>
getPreprocessedEntitiesInRangeSlow(SourceRange Range)127 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
128   assert(Range.isValid());
129   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
130 
131   std::pair<unsigned, unsigned>
132     Local = findLocalPreprocessedEntitiesInRange(Range);
133 
134   // Check if range spans local entities.
135   if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
136     return std::make_pair(Local.first, Local.second);
137 
138   std::pair<unsigned, unsigned>
139     Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
140 
141   // Check if range spans local entities.
142   if (Loaded.first == Loaded.second)
143     return std::make_pair(Local.first, Local.second);
144 
145   unsigned TotalLoaded = LoadedPreprocessedEntities.size();
146 
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);
151 
152   // Range spands loaded and local entities.
153   return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
154 }
155 
156 std::pair<unsigned, unsigned>
findLocalPreprocessedEntitiesInRange(SourceRange Range) const157 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()));
162 
163   unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
164   unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
165   return std::make_pair(Begin, End);
166 }
167 
168 namespace {
169 
170 template <SourceLocation (SourceRange::*getRangeLoc)() const>
171 struct PPEntityComp {
172   const SourceManager &SM;
173 
PPEntityComp__anonefde0c370111::PPEntityComp174   explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
175 
operator ()__anonefde0c370111::PPEntityComp176   bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
177     SourceLocation LHS = getLoc(L);
178     SourceLocation RHS = getLoc(R);
179     return SM.isBeforeInTranslationUnit(LHS, RHS);
180   }
181 
operator ()__anonefde0c370111::PPEntityComp182   bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
183     SourceLocation LHS = getLoc(L);
184     return SM.isBeforeInTranslationUnit(LHS, RHS);
185   }
186 
operator ()__anonefde0c370111::PPEntityComp187   bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
188     SourceLocation RHS = getLoc(R);
189     return SM.isBeforeInTranslationUnit(LHS, RHS);
190   }
191 
getLoc__anonefde0c370111::PPEntityComp192   SourceLocation getLoc(PreprocessedEntity *PPE) const {
193     SourceRange Range = PPE->getSourceRange();
194     return (Range.*getRangeLoc)();
195   }
196 };
197 
198 }
199 
findBeginLocalPreprocessedEntity(SourceLocation Loc) const200 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
201                                                      SourceLocation Loc) const {
202   if (SourceMgr.isLoadedSourceLocation(Loc))
203     return 0;
204 
205   size_t Count = PreprocessedEntities.size();
206   size_t Half;
207   std::vector<PreprocessedEntity *>::const_iterator
208     First = PreprocessedEntities.begin();
209   std::vector<PreprocessedEntity *>::const_iterator I;
210 
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.
215   while (Count > 0) {
216     Half = Count/2;
217     I = First;
218     std::advance(I, Half);
219     if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
220                                             Loc)){
221       First = I;
222       ++First;
223       Count = Count - Half - 1;
224     } else
225       Count = Half;
226   }
227 
228   return First - PreprocessedEntities.begin();
229 }
230 
findEndLocalPreprocessedEntity(SourceLocation Loc) const231 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
232                                                      SourceLocation Loc) const {
233   if (SourceMgr.isLoadedSourceLocation(Loc))
234     return 0;
235 
236   std::vector<PreprocessedEntity *>::const_iterator
237   I = std::upper_bound(PreprocessedEntities.begin(),
238                        PreprocessedEntities.end(),
239                        Loc,
240                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));
241   return I - PreprocessedEntities.begin();
242 }
243 
244 PreprocessingRecord::PPEntityID
addPreprocessedEntity(PreprocessedEntity * Entity)245 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
246   assert(Entity);
247   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
248 
249   if (isa<MacroDefinitionRecord>(Entity)) {
250     assert((PreprocessedEntities.empty() ||
251             !SourceMgr.isBeforeInTranslationUnit(
252                 BeginLoc,
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);
257   }
258 
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);
265   }
266 
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:
272   // \code
273   //  #define M1 1
274   //  #define M2 2
275   //  #define FM(x,y) y x
276   //  FM(M1, M2)
277   // \endcode
278 
279   typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
280 
281   // Usually there are few macro expansions when defining the filename, do a
282   // linear search for a few entities.
283   unsigned count = 0;
284   for (pp_iter RI    = PreprocessedEntities.end(),
285                Begin = PreprocessedEntities.begin();
286        RI != Begin && count < 4; --RI, ++count) {
287     pp_iter I = RI;
288     --I;
289     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
290                                            (*I)->getSourceRange().getBegin())) {
291       pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
292       return getPPEntityID(insertI - PreprocessedEntities.begin(),
293                            /*isLoaded=*/false);
294     }
295   }
296 
297   // Linear search unsuccessful. Do a binary search.
298   pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
299                                PreprocessedEntities.end(),
300                                BeginLoc,
301                                PPEntityComp<&SourceRange::getBegin>(SourceMgr));
302   pp_iter insertI = PreprocessedEntities.insert(I, Entity);
303   return getPPEntityID(insertI - PreprocessedEntities.begin(),
304                        /*isLoaded=*/false);
305 }
306 
SetExternalSource(ExternalPreprocessingRecordSource & Source)307 void PreprocessingRecord::SetExternalSource(
308                                     ExternalPreprocessingRecordSource &Source) {
309   assert(!ExternalSource &&
310          "Preprocessing record already has an external source");
311   ExternalSource = &Source;
312 }
313 
allocateLoadedEntities(unsigned NumEntities)314 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
315   unsigned Result = LoadedPreprocessedEntities.size();
316   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
317                                     + NumEntities);
318   return Result;
319 }
320 
RegisterMacroDefinition(MacroInfo * Macro,MacroDefinitionRecord * Def)321 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
322                                                   MacroDefinitionRecord *Def) {
323   MacroDefinitions[Macro] = Def;
324 }
325 
326 /// \brief Retrieve the preprocessed entity at the given ID.
getPreprocessedEntity(PPEntityID PPID)327 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
328   if (PPID.ID < 0) {
329     unsigned Index = -PPID.ID - 1;
330     assert(Index < LoadedPreprocessedEntities.size() &&
331            "Out-of bounds loaded preprocessed entity");
332     return getLoadedPreprocessedEntity(Index);
333   }
334 
335   if (PPID.ID == 0)
336     return nullptr;
337   unsigned Index = PPID.ID - 1;
338   assert(Index < PreprocessedEntities.size() &&
339          "Out-of bounds local preprocessed entity");
340   return PreprocessedEntities[Index];
341 }
342 
343 /// \brief Retrieve the loaded preprocessed entity at the given index.
344 PreprocessedEntity *
getLoadedPreprocessedEntity(unsigned 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];
350   if (!Entity) {
351     Entity = ExternalSource->ReadPreprocessedEntity(Index);
352     if (!Entity) // Failed to load.
353       Entity = new (*this)
354          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
355   }
356   return Entity;
357 }
358 
359 MacroDefinitionRecord *
findMacroDefinition(const MacroInfo * MI)360 PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
361   llvm::DenseMap<const MacroInfo *, MacroDefinitionRecord *>::iterator Pos =
362       MacroDefinitions.find(MI);
363   if (Pos == MacroDefinitions.end())
364     return nullptr;
365 
366   return Pos->second;
367 }
368 
addMacroExpansion(const Token & Id,const MacroInfo * MI,SourceRange Range)369 void PreprocessingRecord::addMacroExpansion(const Token &Id,
370                                             const MacroInfo *MI,
371                                             SourceRange Range) {
372   // We don't record nested macro expansions.
373   if (Id.getLocation().isMacroID())
374     return;
375 
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));
381 }
382 
Ifdef(SourceLocation Loc,const Token & MacroNameTok,const MacroDefinition & MD)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.
386   if (MD)
387     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
388                       MacroNameTok.getLocation());
389 }
390 
Ifndef(SourceLocation Loc,const Token & MacroNameTok,const MacroDefinition & MD)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.
394   if (MD)
395     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
396                       MacroNameTok.getLocation());
397 }
398 
Defined(const Token & MacroNameTok,const MacroDefinition & MD,SourceRange Range)399 void PreprocessingRecord::Defined(const Token &MacroNameTok,
400                                   const MacroDefinition &MD,
401                                   SourceRange Range) {
402   // This is not actually a macro expansion but record it as a macro reference.
403   if (MD)
404     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
405                       MacroNameTok.getLocation());
406 }
407 
SourceRangeSkipped(SourceRange Range)408 void PreprocessingRecord::SourceRangeSkipped(SourceRange Range) {
409   SkippedRanges.push_back(Range);
410 }
411 
MacroExpands(const Token & Id,const MacroDefinition & MD,SourceRange Range,const MacroArgs * Args)412 void PreprocessingRecord::MacroExpands(const Token &Id,
413                                        const MacroDefinition &MD,
414                                        SourceRange Range,
415                                        const MacroArgs *Args) {
416   addMacroExpansion(Id, MD.getMacroInfo(), Range);
417 }
418 
MacroDefined(const Token & Id,const MacroDirective * MD)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;
427 }
428 
MacroUndefined(const Token & Id,const MacroDefinition & MD)429 void PreprocessingRecord::MacroUndefined(const Token &Id,
430                                          const MacroDefinition &MD) {
431   MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });
432 }
433 
InclusionDirective(SourceLocation HashLoc,const clang::Token & IncludeTok,StringRef FileName,bool IsAngled,CharSourceRange FilenameRange,const FileEntry * File,StringRef SearchPath,StringRef RelativePath,const Module * Imported)434 void PreprocessingRecord::InclusionDirective(
435     SourceLocation HashLoc,
436     const clang::Token &IncludeTok,
437     StringRef FileName,
438     bool IsAngled,
439     CharSourceRange FilenameRange,
440     const FileEntry *File,
441     StringRef SearchPath,
442     StringRef RelativePath,
443     const Module *Imported) {
444   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
445 
446   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
447   case tok::pp_include:
448     Kind = InclusionDirective::Include;
449     break;
450 
451   case tok::pp_import:
452     Kind = InclusionDirective::Import;
453     break;
454 
455   case tok::pp_include_next:
456     Kind = InclusionDirective::IncludeNext;
457     break;
458 
459   case tok::pp___include_macros:
460     Kind = InclusionDirective::IncludeMacros;
461     break;
462 
463   default:
464     llvm_unreachable("Unknown include directive kind");
465   }
466 
467   SourceLocation EndLoc;
468   if (!IsAngled) {
469     EndLoc = FilenameRange.getBegin();
470   } else {
471     EndLoc = FilenameRange.getEnd();
472     if (FilenameRange.isCharRange())
473       EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
474                                             // a token range.
475   }
476   clang::InclusionDirective *ID
477     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
478                                             (bool)Imported,
479                                             File, SourceRange(HashLoc, EndLoc));
480   addPreprocessedEntity(ID);
481 }
482 
getTotalMemory() const483 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);
488 }
489