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, 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 
41 PreprocessingRecord::PreprocessingRecord(SourceManager &SM,
42                                          bool RecordConditionalDirectives)
43   : SourceMgr(SM),
44     RecordCondDirectives(RecordConditionalDirectives), CondDirectiveNextIdx(0),
45     ExternalSource(0)
46 {
47   if (RecordCondDirectives)
48     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
49 }
50 
51 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
52 /// that source range \p Range encompasses.
53 std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
54 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
55   if (Range.isInvalid())
56     return std::make_pair(iterator(), iterator());
57 
58   if (CachedRangeQuery.Range == Range) {
59     return std::make_pair(iterator(this, CachedRangeQuery.Result.first),
60                           iterator(this, CachedRangeQuery.Result.second));
61   }
62 
63   std::pair<PPEntityID, PPEntityID>
64     Res = getPreprocessedEntitiesInRangeSlow(Range);
65 
66   CachedRangeQuery.Range = Range;
67   CachedRangeQuery.Result = Res;
68 
69   return std::make_pair(iterator(this, Res.first), iterator(this, Res.second));
70 }
71 
72 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
73                                            SourceManager &SM) {
74   assert(!FID.isInvalid());
75   if (!PPE)
76     return false;
77 
78   SourceLocation Loc = PPE->getSourceRange().getBegin();
79   if (Loc.isInvalid())
80     return false;
81 
82   if (SM.isInFileID(SM.getFileLoc(Loc), FID))
83     return true;
84   else
85     return false;
86 }
87 
88 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
89 /// points to is coming from the file \arg FID.
90 ///
91 /// Can be used to avoid implicit deserializations of preallocated
92 /// preprocessed entities if we only care about entities of a specific file
93 /// and not from files \#included in the range given at
94 /// \see getPreprocessedEntitiesInRange.
95 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
96   if (FID.isInvalid())
97     return false;
98 
99   PPEntityID PPID = PPEI.Position;
100   if (PPID < 0) {
101     assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
102            "Out-of bounds loaded preprocessed entity");
103     assert(ExternalSource && "No external source to load from");
104     unsigned LoadedIndex = LoadedPreprocessedEntities.size()+PPID;
105     if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
106       return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);
107 
108     // See if the external source can see if the entity is in the file without
109     // deserializing it.
110     llvm::Optional<bool>
111       IsInFile = ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
112     if (IsInFile.hasValue())
113       return IsInFile.getValue();
114 
115     // The external source did not provide a definite answer, go and deserialize
116     // the entity to check it.
117     return isPreprocessedEntityIfInFileID(
118                                        getLoadedPreprocessedEntity(LoadedIndex),
119                                           FID, SourceMgr);
120   }
121 
122   assert(unsigned(PPID) < PreprocessedEntities.size() &&
123          "Out-of bounds local preprocessed entity");
124   return isPreprocessedEntityIfInFileID(PreprocessedEntities[PPID],
125                                         FID, SourceMgr);
126 }
127 
128 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
129 /// that source range \arg R encompasses.
130 std::pair<PreprocessingRecord::PPEntityID, PreprocessingRecord::PPEntityID>
131 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
132   assert(Range.isValid());
133   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
134 
135   std::pair<unsigned, unsigned>
136     Local = findLocalPreprocessedEntitiesInRange(Range);
137 
138   // Check if range spans local entities.
139   if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
140     return std::make_pair(Local.first, Local.second);
141 
142   std::pair<unsigned, unsigned>
143     Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
144 
145   // Check if range spans local entities.
146   if (Loaded.first == Loaded.second)
147     return std::make_pair(Local.first, Local.second);
148 
149   unsigned TotalLoaded = LoadedPreprocessedEntities.size();
150 
151   // Check if range spans loaded entities.
152   if (Local.first == Local.second)
153     return std::make_pair(int(Loaded.first)-TotalLoaded,
154                           int(Loaded.second)-TotalLoaded);
155 
156   // Range spands loaded and local entities.
157   return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
158 }
159 
160 std::pair<unsigned, unsigned>
161 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
162                                                       SourceRange Range) const {
163   if (Range.isInvalid())
164     return std::make_pair(0,0);
165   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
166 
167   unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
168   unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
169   return std::make_pair(Begin, End);
170 }
171 
172 namespace {
173 
174 template <SourceLocation (SourceRange::*getRangeLoc)() const>
175 struct PPEntityComp {
176   const SourceManager &SM;
177 
178   explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
179 
180   bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
181     SourceLocation LHS = getLoc(L);
182     SourceLocation RHS = getLoc(R);
183     return SM.isBeforeInTranslationUnit(LHS, RHS);
184   }
185 
186   bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
187     SourceLocation LHS = getLoc(L);
188     return SM.isBeforeInTranslationUnit(LHS, RHS);
189   }
190 
191   bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
192     SourceLocation RHS = getLoc(R);
193     return SM.isBeforeInTranslationUnit(LHS, RHS);
194   }
195 
196   SourceLocation getLoc(PreprocessedEntity *PPE) const {
197     SourceRange Range = PPE->getSourceRange();
198     return (Range.*getRangeLoc)();
199   }
200 };
201 
202 }
203 
204 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
205                                                      SourceLocation Loc) const {
206   if (SourceMgr.isLoadedSourceLocation(Loc))
207     return 0;
208 
209   size_t Count = PreprocessedEntities.size();
210   size_t Half;
211   std::vector<PreprocessedEntity *>::const_iterator
212     First = PreprocessedEntities.begin();
213   std::vector<PreprocessedEntity *>::const_iterator I;
214 
215   // Do a binary search manually instead of using std::lower_bound because
216   // The end locations of entities may be unordered (when a macro expansion
217   // is inside another macro argument), but for this case it is not important
218   // whether we get the first macro expansion or its containing macro.
219   while (Count > 0) {
220     Half = Count/2;
221     I = First;
222     std::advance(I, Half);
223     if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
224                                             Loc)){
225       First = I;
226       ++First;
227       Count = Count - Half - 1;
228     } else
229       Count = Half;
230   }
231 
232   return First - PreprocessedEntities.begin();
233 }
234 
235 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
236                                                      SourceLocation Loc) const {
237   if (SourceMgr.isLoadedSourceLocation(Loc))
238     return 0;
239 
240   std::vector<PreprocessedEntity *>::const_iterator
241   I = std::upper_bound(PreprocessedEntities.begin(),
242                        PreprocessedEntities.end(),
243                        Loc,
244                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));
245   return I - PreprocessedEntities.begin();
246 }
247 
248 PreprocessingRecord::PPEntityID
249 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
250   assert(Entity);
251   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
252 
253   if (!isa<class InclusionDirective>(Entity)) {
254     assert((PreprocessedEntities.empty() ||
255             !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
256                    PreprocessedEntities.back()->getSourceRange().getBegin())) &&
257            "a macro directive was encountered out-of-order");
258     PreprocessedEntities.push_back(Entity);
259     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
260   }
261 
262   // Check normal case, this entity begin location is after the previous one.
263   if (PreprocessedEntities.empty() ||
264       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
265                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
266     PreprocessedEntities.push_back(Entity);
267     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
268   }
269 
270   // The entity's location is not after the previous one; this can happen with
271   // include directives that form the filename using macros, e.g:
272   // "#include MACRO(STUFF)".
273 
274   typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
275 
276   // Usually there are few macro expansions when defining the filename, do a
277   // linear search for a few entities.
278   unsigned count = 0;
279   for (pp_iter RI    = PreprocessedEntities.end(),
280                Begin = PreprocessedEntities.begin();
281        RI != Begin && count < 4; --RI, ++count) {
282     pp_iter I = RI;
283     --I;
284     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
285                                            (*I)->getSourceRange().getBegin())) {
286       pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
287       return getPPEntityID(insertI - PreprocessedEntities.begin(),
288                            /*isLoaded=*/false);
289     }
290   }
291 
292   // Linear search unsuccessful. Do a binary search.
293   pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
294                                PreprocessedEntities.end(),
295                                BeginLoc,
296                                PPEntityComp<&SourceRange::getBegin>(SourceMgr));
297   pp_iter insertI = PreprocessedEntities.insert(I, Entity);
298   return getPPEntityID(insertI - PreprocessedEntities.begin(),
299                        /*isLoaded=*/false);
300 }
301 
302 void PreprocessingRecord::SetExternalSource(
303                                     ExternalPreprocessingRecordSource &Source) {
304   assert(!ExternalSource &&
305          "Preprocessing record already has an external source");
306   ExternalSource = &Source;
307 }
308 
309 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
310   unsigned Result = LoadedPreprocessedEntities.size();
311   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
312                                     + NumEntities);
313   return Result;
314 }
315 
316 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
317                                                   PPEntityID PPID) {
318   MacroDefinitions[Macro] = PPID;
319 }
320 
321 /// \brief Retrieve the preprocessed entity at the given ID.
322 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
323   if (PPID < 0) {
324     assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
325            "Out-of bounds loaded preprocessed entity");
326     return getLoadedPreprocessedEntity(LoadedPreprocessedEntities.size()+PPID);
327   }
328   assert(unsigned(PPID) < PreprocessedEntities.size() &&
329          "Out-of bounds local preprocessed entity");
330   return PreprocessedEntities[PPID];
331 }
332 
333 /// \brief Retrieve the loaded preprocessed entity at the given index.
334 PreprocessedEntity *
335 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
336   assert(Index < LoadedPreprocessedEntities.size() &&
337          "Out-of bounds loaded preprocessed entity");
338   assert(ExternalSource && "No external source to load from");
339   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
340   if (!Entity) {
341     Entity = ExternalSource->ReadPreprocessedEntity(Index);
342     if (!Entity) // Failed to load.
343       Entity = new (*this)
344          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
345   }
346   return Entity;
347 }
348 
349 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
350   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
351     = MacroDefinitions.find(MI);
352   if (Pos == MacroDefinitions.end())
353     return 0;
354 
355   PreprocessedEntity *Entity = getPreprocessedEntity(Pos->second);
356   if (Entity->isInvalid())
357     return 0;
358   return cast<MacroDefinition>(Entity);
359 }
360 
361 void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
362                                        SourceRange Range) {
363   // We don't record nested macro expansions.
364   if (Id.getLocation().isMacroID())
365     return;
366 
367   if (MI->isBuiltinMacro())
368     addPreprocessedEntity(
369                       new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
370   else if (MacroDefinition *Def = findMacroDefinition(MI))
371     addPreprocessedEntity(
372                        new (*this) MacroExpansion(Def, Range));
373 }
374 
375 void PreprocessingRecord::MacroDefined(const Token &Id,
376                                        const MacroInfo *MI) {
377   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
378   MacroDefinition *Def
379       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
380   MacroDefinitions[MI] = addPreprocessedEntity(Def);
381 }
382 
383 void PreprocessingRecord::MacroUndefined(const Token &Id,
384                                          const MacroInfo *MI) {
385   MacroDefinitions.erase(MI);
386 }
387 
388 void PreprocessingRecord::InclusionDirective(
389     SourceLocation HashLoc,
390     const clang::Token &IncludeTok,
391     StringRef FileName,
392     bool IsAngled,
393     CharSourceRange FilenameRange,
394     const FileEntry *File,
395     StringRef SearchPath,
396     StringRef RelativePath,
397     const Module *Imported) {
398   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
399 
400   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
401   case tok::pp_include:
402     Kind = InclusionDirective::Include;
403     break;
404 
405   case tok::pp_import:
406     Kind = InclusionDirective::Import;
407     break;
408 
409   case tok::pp_include_next:
410     Kind = InclusionDirective::IncludeNext;
411     break;
412 
413   case tok::pp___include_macros:
414     Kind = InclusionDirective::IncludeMacros;
415     break;
416 
417   default:
418     llvm_unreachable("Unknown include directive kind");
419   }
420 
421   SourceLocation EndLoc;
422   if (!IsAngled) {
423     EndLoc = FilenameRange.getBegin();
424   } else {
425     EndLoc = FilenameRange.getEnd();
426     if (FilenameRange.isCharRange())
427       EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
428                                             // a token range.
429   }
430   clang::InclusionDirective *ID
431     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
432                                             (bool)Imported,
433                                             File, SourceRange(HashLoc, EndLoc));
434   addPreprocessedEntity(ID);
435 }
436 
437 bool PreprocessingRecord::rangeIntersectsConditionalDirective(
438                                                       SourceRange Range) const {
439   if (Range.isInvalid())
440     return false;
441 
442   CondDirectiveLocsTy::const_iterator
443     low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
444                            Range.getBegin(), CondDirectiveLoc::Comp(SourceMgr));
445   if (low == CondDirectiveLocs.end())
446     return false;
447 
448   if (SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), low->getLoc()))
449     return false;
450 
451   CondDirectiveLocsTy::const_iterator
452     upp = std::upper_bound(low, CondDirectiveLocs.end(),
453                            Range.getEnd(), CondDirectiveLoc::Comp(SourceMgr));
454   unsigned uppIdx;
455   if (upp != CondDirectiveLocs.end())
456     uppIdx = upp->getIdx();
457   else
458     uppIdx = 0;
459 
460   return low->getIdx() != uppIdx;
461 }
462 
463 unsigned PreprocessingRecord::findCondDirectiveIdx(SourceLocation Loc) const {
464   if (Loc.isInvalid())
465     return 0;
466 
467   CondDirectiveLocsTy::const_iterator
468     low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
469                            Loc, CondDirectiveLoc::Comp(SourceMgr));
470   if (low == CondDirectiveLocs.end())
471     return 0;
472   return low->getIdx();
473 }
474 
475 void PreprocessingRecord::addCondDirectiveLoc(CondDirectiveLoc DirLoc) {
476   // Ignore directives in system headers.
477   if (SourceMgr.isInSystemHeader(DirLoc.getLoc()))
478     return;
479 
480   assert(CondDirectiveLocs.empty() ||
481          SourceMgr.isBeforeInTranslationUnit(CondDirectiveLocs.back().getLoc(),
482                                              DirLoc.getLoc()));
483   CondDirectiveLocs.push_back(DirLoc);
484 }
485 
486 void PreprocessingRecord::If(SourceLocation Loc, SourceRange ConditionRange) {
487   if (RecordCondDirectives) {
488     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
489     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
490   }
491 }
492 
493 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok) {
494   if (RecordCondDirectives) {
495     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
496     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
497   }
498 }
499 
500 void PreprocessingRecord::Ifndef(SourceLocation Loc,const Token &MacroNameTok) {
501   if (RecordCondDirectives) {
502     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
503     CondDirectiveStack.push_back(CondDirectiveNextIdx++);
504   }
505 }
506 
507 void PreprocessingRecord::Elif(SourceLocation Loc, SourceRange ConditionRange,
508                                SourceLocation IfLoc) {
509   if (RecordCondDirectives)
510     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
511 }
512 
513 void PreprocessingRecord::Else(SourceLocation Loc, SourceLocation IfLoc) {
514   if (RecordCondDirectives)
515     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
516 }
517 
518 void PreprocessingRecord::Endif(SourceLocation Loc, SourceLocation IfLoc) {
519   if (RecordCondDirectives) {
520     addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
521     assert(!CondDirectiveStack.empty());
522     CondDirectiveStack.pop_back();
523   }
524 }
525 
526 size_t PreprocessingRecord::getTotalMemory() const {
527   return BumpAlloc.getTotalMemory()
528     + llvm::capacity_in_bytes(MacroDefinitions)
529     + llvm::capacity_in_bytes(PreprocessedEntities)
530     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
531 }
532