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