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
242 PreprocessingRecord::findEndLocalPreprocessedEntity(SourceLocation Loc) const {
243   if (SourceMgr.isLoadedSourceLocation(Loc))
244     return 0;
245 
246   auto I = llvm::upper_bound(PreprocessedEntities, Loc,
247                              PPEntityComp<&SourceRange::getBegin>(SourceMgr));
248   return I - PreprocessedEntities.begin();
249 }
250 
251 PreprocessingRecord::PPEntityID
252 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
253   assert(Entity);
254   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
255 
256   if (isa<MacroDefinitionRecord>(Entity)) {
257     assert((PreprocessedEntities.empty() ||
258             !SourceMgr.isBeforeInTranslationUnit(
259                 BeginLoc,
260                 PreprocessedEntities.back()->getSourceRange().getBegin())) &&
261            "a macro definition was encountered out-of-order");
262     PreprocessedEntities.push_back(Entity);
263     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
264   }
265 
266   // Check normal case, this entity begin location is after the previous one.
267   if (PreprocessedEntities.empty() ||
268       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
269                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
270     PreprocessedEntities.push_back(Entity);
271     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
272   }
273 
274   // The entity's location is not after the previous one; this can happen with
275   // include directives that form the filename using macros, e.g:
276   // "#include MACRO(STUFF)"
277   // or with macro expansions inside macro arguments where the arguments are
278   // not expanded in the same order as listed, e.g:
279   // \code
280   //  #define M1 1
281   //  #define M2 2
282   //  #define FM(x,y) y x
283   //  FM(M1, M2)
284   // \endcode
285 
286   using pp_iter = std::vector<PreprocessedEntity *>::iterator;
287 
288   // Usually there are few macro expansions when defining the filename, do a
289   // linear search for a few entities.
290   unsigned count = 0;
291   for (pp_iter RI    = PreprocessedEntities.end(),
292                Begin = PreprocessedEntities.begin();
293        RI != Begin && count < 4; --RI, ++count) {
294     pp_iter I = RI;
295     --I;
296     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
297                                            (*I)->getSourceRange().getBegin())) {
298       pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
299       return getPPEntityID(insertI - PreprocessedEntities.begin(),
300                            /*isLoaded=*/false);
301     }
302   }
303 
304   // Linear search unsuccessful. Do a binary search.
305   pp_iter I =
306       llvm::upper_bound(PreprocessedEntities, BeginLoc,
307                         PPEntityComp<&SourceRange::getBegin>(SourceMgr));
308   pp_iter insertI = PreprocessedEntities.insert(I, Entity);
309   return getPPEntityID(insertI - PreprocessedEntities.begin(),
310                        /*isLoaded=*/false);
311 }
312 
313 void PreprocessingRecord::SetExternalSource(
314                                     ExternalPreprocessingRecordSource &Source) {
315   assert(!ExternalSource &&
316          "Preprocessing record already has an external source");
317   ExternalSource = &Source;
318 }
319 
320 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
321   unsigned Result = LoadedPreprocessedEntities.size();
322   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
323                                     + NumEntities);
324   return Result;
325 }
326 
327 unsigned PreprocessingRecord::allocateSkippedRanges(unsigned NumRanges) {
328   unsigned Result = SkippedRanges.size();
329   SkippedRanges.resize(SkippedRanges.size() + NumRanges);
330   SkippedRangesAllLoaded = false;
331   return Result;
332 }
333 
334 void PreprocessingRecord::ensureSkippedRangesLoaded() {
335   if (SkippedRangesAllLoaded || !ExternalSource)
336     return;
337   for (unsigned Index = 0; Index != SkippedRanges.size(); ++Index) {
338     if (SkippedRanges[Index].isInvalid())
339       SkippedRanges[Index] = ExternalSource->ReadSkippedRange(Index);
340   }
341   SkippedRangesAllLoaded = true;
342 }
343 
344 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
345                                                   MacroDefinitionRecord *Def) {
346   MacroDefinitions[Macro] = Def;
347 }
348 
349 /// Retrieve the preprocessed entity at the given ID.
350 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
351   if (PPID.ID < 0) {
352     unsigned Index = -PPID.ID - 1;
353     assert(Index < LoadedPreprocessedEntities.size() &&
354            "Out-of bounds loaded preprocessed entity");
355     return getLoadedPreprocessedEntity(Index);
356   }
357 
358   if (PPID.ID == 0)
359     return nullptr;
360   unsigned Index = PPID.ID - 1;
361   assert(Index < PreprocessedEntities.size() &&
362          "Out-of bounds local preprocessed entity");
363   return PreprocessedEntities[Index];
364 }
365 
366 /// Retrieve the loaded preprocessed entity at the given index.
367 PreprocessedEntity *
368 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
369   assert(Index < LoadedPreprocessedEntities.size() &&
370          "Out-of bounds loaded preprocessed entity");
371   assert(ExternalSource && "No external source to load from");
372   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
373   if (!Entity) {
374     Entity = ExternalSource->ReadPreprocessedEntity(Index);
375     if (!Entity) // Failed to load.
376       Entity = new (*this)
377          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
378   }
379   return Entity;
380 }
381 
382 MacroDefinitionRecord *
383 PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
384   llvm::DenseMap<const MacroInfo *, MacroDefinitionRecord *>::iterator Pos =
385       MacroDefinitions.find(MI);
386   if (Pos == MacroDefinitions.end())
387     return nullptr;
388 
389   return Pos->second;
390 }
391 
392 void PreprocessingRecord::addMacroExpansion(const Token &Id,
393                                             const MacroInfo *MI,
394                                             SourceRange Range) {
395   // We don't record nested macro expansions.
396   if (Id.getLocation().isMacroID())
397     return;
398 
399   if (MI->isBuiltinMacro())
400     addPreprocessedEntity(new (*this)
401                               MacroExpansion(Id.getIdentifierInfo(), Range));
402   else if (MacroDefinitionRecord *Def = findMacroDefinition(MI))
403     addPreprocessedEntity(new (*this) MacroExpansion(Def, Range));
404 }
405 
406 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,
407                                 const MacroDefinition &MD) {
408   // This is not actually a macro expansion but record it as a macro reference.
409   if (MD)
410     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
411                       MacroNameTok.getLocation());
412 }
413 
414 void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
415                                  const MacroDefinition &MD) {
416   // This is not actually a macro expansion but record it as a macro reference.
417   if (MD)
418     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
419                       MacroNameTok.getLocation());
420 }
421 
422 void PreprocessingRecord::Defined(const Token &MacroNameTok,
423                                   const MacroDefinition &MD,
424                                   SourceRange Range) {
425   // This is not actually a macro expansion but record it as a macro reference.
426   if (MD)
427     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
428                       MacroNameTok.getLocation());
429 }
430 
431 void PreprocessingRecord::SourceRangeSkipped(SourceRange Range,
432                                              SourceLocation EndifLoc) {
433   assert(Range.isValid());
434   SkippedRanges.emplace_back(Range.getBegin(), EndifLoc);
435 }
436 
437 void PreprocessingRecord::MacroExpands(const Token &Id,
438                                        const MacroDefinition &MD,
439                                        SourceRange Range,
440                                        const MacroArgs *Args) {
441   addMacroExpansion(Id, MD.getMacroInfo(), Range);
442 }
443 
444 void PreprocessingRecord::MacroDefined(const Token &Id,
445                                        const MacroDirective *MD) {
446   const MacroInfo *MI = MD->getMacroInfo();
447   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
448   MacroDefinitionRecord *Def =
449       new (*this) MacroDefinitionRecord(Id.getIdentifierInfo(), R);
450   addPreprocessedEntity(Def);
451   MacroDefinitions[MI] = Def;
452 }
453 
454 void PreprocessingRecord::MacroUndefined(const Token &Id,
455                                          const MacroDefinition &MD,
456                                          const MacroDirective *Undef) {
457   MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });
458 }
459 
460 void PreprocessingRecord::InclusionDirective(
461     SourceLocation HashLoc,
462     const Token &IncludeTok,
463     StringRef FileName,
464     bool IsAngled,
465     CharSourceRange FilenameRange,
466     const FileEntry *File,
467     StringRef SearchPath,
468     StringRef RelativePath,
469     const Module *Imported,
470     SrcMgr::CharacteristicKind FileType) {
471   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
472 
473   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
474   case tok::pp_include:
475     Kind = InclusionDirective::Include;
476     break;
477 
478   case tok::pp_import:
479     Kind = InclusionDirective::Import;
480     break;
481 
482   case tok::pp_include_next:
483     Kind = InclusionDirective::IncludeNext;
484     break;
485 
486   case tok::pp___include_macros:
487     Kind = InclusionDirective::IncludeMacros;
488     break;
489 
490   default:
491     llvm_unreachable("Unknown include directive kind");
492   }
493 
494   SourceLocation EndLoc;
495   if (!IsAngled) {
496     EndLoc = FilenameRange.getBegin();
497   } else {
498     EndLoc = FilenameRange.getEnd();
499     if (FilenameRange.isCharRange())
500       EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
501                                             // a token range.
502   }
503   clang::InclusionDirective *ID =
504       new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
505                                             (bool)Imported, File,
506                                             SourceRange(HashLoc, EndLoc));
507   addPreprocessedEntity(ID);
508 }
509 
510 size_t PreprocessingRecord::getTotalMemory() const {
511   return BumpAlloc.getTotalMemory()
512     + llvm::capacity_in_bytes(MacroDefinitions)
513     + llvm::capacity_in_bytes(PreprocessedEntities)
514     + llvm::capacity_in_bytes(LoadedPreprocessedEntities)
515     + llvm::capacity_in_bytes(SkippedRanges);
516 }
517