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/ErrorHandling.h"
18 #include "llvm/Support/Capacity.h"
19 
20 using namespace clang;
21 
22 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }
23 
24 
25 InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
26                                        InclusionKind Kind,
27                                        StringRef FileName,
28                                        bool InQuotes, const FileEntry *File,
29                                        SourceRange Range)
30   : PreprocessingDirective(InclusionDirectiveKind, Range),
31     InQuotes(InQuotes), Kind(Kind), File(File)
32 {
33   char *Memory
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());
38 }
39 
40 PreprocessingRecord::PreprocessingRecord(SourceManager &SM,
41                                          bool RecordConditionalDirectives)
42   : SourceMgr(SM),
43     RecordCondDirectives(RecordConditionalDirectives), CondDirectiveNextIdx(0),
44     ExternalSource(0)
45 {
46   if (RecordCondDirectives)
47     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
48 }
49 
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());
56 
57   if (CachedRangeQuery.Range == Range) {
58     return std::make_pair(iterator(this, CachedRangeQuery.Result.first),
59                           iterator(this, CachedRangeQuery.Result.second));
60   }
61 
62   std::pair<PPEntityID, PPEntityID>
63     Res = getPreprocessedEntitiesInRangeSlow(Range);
64 
65   CachedRangeQuery.Range = Range;
66   CachedRangeQuery.Result = Res;
67 
68   return std::make_pair(iterator(this, Res.first), iterator(this, Res.second));
69 }
70 
71 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
72                                            SourceManager &SM) {
73   assert(!FID.isInvalid());
74   if (!PPE)
75     return false;
76 
77   SourceLocation Loc = PPE->getSourceRange().getBegin();
78   if (Loc.isInvalid())
79     return false;
80 
81   if (SM.isInFileID(SM.getFileLoc(Loc), FID))
82     return true;
83   else
84     return false;
85 }
86 
87 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
88 /// points to is coming from the file \arg FID.
89 ///
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) {
95   if (FID.isInvalid())
96     return false;
97 
98   PPEntityID PPID = PPEI.Position;
99   if (PPID < 0) {
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);
106 
107     // See if the external source can see if the entity is in the file without
108     // deserializing it.
109     llvm::Optional<bool>
110       IsInFile = ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
111     if (IsInFile.hasValue())
112       return IsInFile.getValue();
113 
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),
118                                           FID, SourceMgr);
119   }
120 
121   assert(unsigned(PPID) < PreprocessedEntities.size() &&
122          "Out-of bounds local preprocessed entity");
123   return isPreprocessedEntityIfInFileID(PreprocessedEntities[PPID],
124                                         FID, SourceMgr);
125 }
126 
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()));
133 
134   std::pair<unsigned, unsigned>
135     Local = findLocalPreprocessedEntitiesInRange(Range);
136 
137   // Check if range spans local entities.
138   if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
139     return std::make_pair(Local.first, Local.second);
140 
141   std::pair<unsigned, unsigned>
142     Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
143 
144   // Check if range spans local entities.
145   if (Loaded.first == Loaded.second)
146     return std::make_pair(Local.first, Local.second);
147 
148   unsigned TotalLoaded = LoadedPreprocessedEntities.size();
149 
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);
154 
155   // Range spands loaded and local entities.
156   return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
157 }
158 
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()));
165 
166   unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
167   unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
168   return std::make_pair(Begin, End);
169 }
170 
171 namespace {
172 
173 template <SourceLocation (SourceRange::*getRangeLoc)() const>
174 struct PPEntityComp {
175   const SourceManager &SM;
176 
177   explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
178 
179   bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
180     SourceLocation LHS = getLoc(L);
181     SourceLocation RHS = getLoc(R);
182     return SM.isBeforeInTranslationUnit(LHS, RHS);
183   }
184 
185   bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
186     SourceLocation LHS = getLoc(L);
187     return SM.isBeforeInTranslationUnit(LHS, RHS);
188   }
189 
190   bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
191     SourceLocation RHS = getLoc(R);
192     return SM.isBeforeInTranslationUnit(LHS, RHS);
193   }
194 
195   SourceLocation getLoc(PreprocessedEntity *PPE) const {
196     SourceRange Range = PPE->getSourceRange();
197     return (Range.*getRangeLoc)();
198   }
199 };
200 
201 }
202 
203 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
204                                                      SourceLocation Loc) const {
205   if (SourceMgr.isLoadedSourceLocation(Loc))
206     return 0;
207 
208   size_t Count = PreprocessedEntities.size();
209   size_t Half;
210   std::vector<PreprocessedEntity *>::const_iterator
211     First = PreprocessedEntities.begin();
212   std::vector<PreprocessedEntity *>::const_iterator I;
213 
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.
218   while (Count > 0) {
219     Half = Count/2;
220     I = First;
221     std::advance(I, Half);
222     if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
223                                             Loc)){
224       First = I;
225       ++First;
226       Count = Count - Half - 1;
227     } else
228       Count = Half;
229   }
230 
231   return First - PreprocessedEntities.begin();
232 }
233 
234 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
235                                                      SourceLocation Loc) const {
236   if (SourceMgr.isLoadedSourceLocation(Loc))
237     return 0;
238 
239   std::vector<PreprocessedEntity *>::const_iterator
240   I = std::upper_bound(PreprocessedEntities.begin(),
241                        PreprocessedEntities.end(),
242                        Loc,
243                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));
244   return I - PreprocessedEntities.begin();
245 }
246 
247 void PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
248   assert(Entity);
249   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
250 
251   // Check normal case, this entity begin location is after the previous one.
252   if (PreprocessedEntities.empty() ||
253       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
254                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
255     PreprocessedEntities.push_back(Entity);
256     return;
257   }
258 
259   // The entity's location is not after the previous one; this can happen rarely
260   // e.g. with "#include MACRO".
261   // Iterate the entities vector in reverse until we find the right place to
262   // insert the new entity.
263   for (std::vector<PreprocessedEntity *>::iterator
264          RI = PreprocessedEntities.end(), Begin = PreprocessedEntities.begin();
265        RI != Begin; --RI) {
266     std::vector<PreprocessedEntity *>::iterator I = RI;
267     --I;
268     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
269                                            (*I)->getSourceRange().getBegin())) {
270       PreprocessedEntities.insert(RI, Entity);
271       return;
272     }
273   }
274 }
275 
276 void PreprocessingRecord::SetExternalSource(
277                                     ExternalPreprocessingRecordSource &Source) {
278   assert(!ExternalSource &&
279          "Preprocessing record already has an external source");
280   ExternalSource = &Source;
281 }
282 
283 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
284   unsigned Result = LoadedPreprocessedEntities.size();
285   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
286                                     + NumEntities);
287   return Result;
288 }
289 
290 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
291                                                   PPEntityID PPID) {
292   MacroDefinitions[Macro] = PPID;
293 }
294 
295 /// \brief Retrieve the preprocessed entity at the given ID.
296 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
297   if (PPID < 0) {
298     assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
299            "Out-of bounds loaded preprocessed entity");
300     return getLoadedPreprocessedEntity(LoadedPreprocessedEntities.size()+PPID);
301   }
302   assert(unsigned(PPID) < PreprocessedEntities.size() &&
303          "Out-of bounds local preprocessed entity");
304   return PreprocessedEntities[PPID];
305 }
306 
307 /// \brief Retrieve the loaded preprocessed entity at the given index.
308 PreprocessedEntity *
309 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
310   assert(Index < LoadedPreprocessedEntities.size() &&
311          "Out-of bounds loaded preprocessed entity");
312   assert(ExternalSource && "No external source to load from");
313   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
314   if (!Entity) {
315     Entity = ExternalSource->ReadPreprocessedEntity(Index);
316     if (!Entity) // Failed to load.
317       Entity = new (*this)
318          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
319   }
320   return Entity;
321 }
322 
323 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
324   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
325     = MacroDefinitions.find(MI);
326   if (Pos == MacroDefinitions.end())
327     return 0;
328 
329   PreprocessedEntity *Entity = getPreprocessedEntity(Pos->second);
330   if (Entity->isInvalid())
331     return 0;
332   return cast<MacroDefinition>(Entity);
333 }
334 
335 void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
336                                        SourceRange Range) {
337   // We don't record nested macro expansions.
338   if (Id.getLocation().isMacroID())
339     return;
340 
341   if (MI->isBuiltinMacro())
342     addPreprocessedEntity(
343                       new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
344   else if (MacroDefinition *Def = findMacroDefinition(MI))
345     addPreprocessedEntity(
346                        new (*this) MacroExpansion(Def, Range));
347 }
348 
349 void PreprocessingRecord::MacroDefined(const Token &Id,
350                                        const MacroInfo *MI) {
351   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
352   MacroDefinition *Def
353       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
354   addPreprocessedEntity(Def);
355   MacroDefinitions[MI] = getPPEntityID(PreprocessedEntities.size()-1,
356                                        /*isLoaded=*/false);
357 }
358 
359 void PreprocessingRecord::MacroUndefined(const Token &Id,
360                                          const MacroInfo *MI) {
361   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
362     = MacroDefinitions.find(MI);
363   if (Pos != MacroDefinitions.end())
364     MacroDefinitions.erase(Pos);
365 }
366 
367 void PreprocessingRecord::InclusionDirective(
368     SourceLocation HashLoc,
369     const clang::Token &IncludeTok,
370     StringRef FileName,
371     bool IsAngled,
372     const FileEntry *File,
373     clang::SourceLocation EndLoc,
374     StringRef SearchPath,
375     StringRef RelativePath) {
376   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
377 
378   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
379   case tok::pp_include:
380     Kind = InclusionDirective::Include;
381     break;
382 
383   case tok::pp_import:
384     Kind = InclusionDirective::Import;
385     break;
386 
387   case tok::pp_include_next:
388     Kind = InclusionDirective::IncludeNext;
389     break;
390 
391   case tok::pp___include_macros:
392     Kind = InclusionDirective::IncludeMacros;
393     break;
394 
395   default:
396     llvm_unreachable("Unknown include directive kind");
397   }
398 
399   clang::InclusionDirective *ID
400     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
401                                             File, SourceRange(HashLoc, EndLoc));
402   addPreprocessedEntity(ID);
403 }
404 
405 bool PreprocessingRecord::rangeIntersectsConditionalDirective(
406                                                       SourceRange Range) const {
407   if (Range.isInvalid())
408     return false;
409 
410   CondDirectiveLocsTy::const_iterator
411     low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
412                            Range.getBegin(), CondDirectiveLoc::Comp(SourceMgr));
413   if (low == CondDirectiveLocs.end())
414     return false;
415 
416   if (SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), low->getLoc()))
417     return false;
418 
419   CondDirectiveLocsTy::const_iterator
420     upp = std::upper_bound(low, CondDirectiveLocs.end(),
421                            Range.getEnd(), CondDirectiveLoc::Comp(SourceMgr));
422   unsigned uppIdx;
423   if (upp != CondDirectiveLocs.end())
424     uppIdx = upp->getIdx();
425   else
426     uppIdx = 0;
427 
428   return low->getIdx() != uppIdx;
429 }
430 
431 unsigned PreprocessingRecord::findCondDirectiveIdx(SourceLocation Loc) const {
432   if (Loc.isInvalid())
433     return 0;
434 
435   CondDirectiveLocsTy::const_iterator
436     low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
437                            Loc, CondDirectiveLoc::Comp(SourceMgr));
438   if (low == CondDirectiveLocs.end())
439     return 0;
440   return low->getIdx();
441 }
442 
443 void PreprocessingRecord::addCondDirectiveLoc(CondDirectiveLoc DirLoc) {
444   // Ignore directives in system headers.
445   if (SourceMgr.isInSystemHeader(DirLoc.getLoc()))
446     return;
447 
448   assert(CondDirectiveLocs.empty() ||
449          SourceMgr.isBeforeInTranslationUnit(CondDirectiveLocs.back().getLoc(),
450                                              DirLoc.getLoc()));
451   CondDirectiveLocs.push_back(DirLoc);
452 }
453 
454 void PreprocessingRecord::If(SourceLocation Loc, SourceRange ConditionRange) {
455   if (RecordCondDirectives) {
456     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
457     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
458   }
459 }
460 
461 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok) {
462   if (RecordCondDirectives) {
463     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
464     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
465   }
466 }
467 
468 void PreprocessingRecord::Ifndef(SourceLocation Loc,const Token &MacroNameTok) {
469   if (RecordCondDirectives) {
470     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
471     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
472   }
473 }
474 
475 void PreprocessingRecord::Elif(SourceLocation Loc, SourceRange ConditionRange,
476                                SourceLocation IfLoc) {
477   if (RecordCondDirectives)
478     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
479 }
480 
481 void PreprocessingRecord::Else(SourceLocation Loc, SourceLocation IfLoc) {
482   if (RecordCondDirectives)
483     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
484 }
485 
486 void PreprocessingRecord::Endif(SourceLocation Loc, SourceLocation IfLoc) {
487   if (RecordCondDirectives) {
488     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
489     assert(!CondDirectiveStack.empty());
490     CondDirectiveStack.pop_back();
491   }
492 }
493 
494 size_t PreprocessingRecord::getTotalMemory() const {
495   return BumpAlloc.getTotalMemory()
496     + llvm::capacity_in_bytes(MacroDefinitions)
497     + llvm::capacity_in_bytes(PreprocessedEntities)
498     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
499 }
500