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