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/StringRef.h"
24 #include "llvm/ADT/iterator_range.h"
25 #include "llvm/Support/Capacity.h"
26 #include "llvm/Support/Casting.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include <algorithm>
29 #include <cassert>
30 #include <cstddef>
31 #include <cstring>
32 #include <iterator>
33 #include <optional>
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                                        OptionalFileEntryRef File,
46                                        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     if (std::optional<bool> IsInFile =
116             ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID))
117       return *IsInFile;
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::Elifdef(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::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
423                                  const MacroDefinition &MD) {
424   // This is not actually a macro expansion but record it as a macro reference.
425   if (MD)
426     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
427                       MacroNameTok.getLocation());
428 }
429 
430 void PreprocessingRecord::Elifndef(SourceLocation Loc,
431                                    const Token &MacroNameTok,
432                                    const MacroDefinition &MD) {
433   // This is not actually a macro expansion but record it as a macro reference.
434   if (MD)
435     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
436                       MacroNameTok.getLocation());
437 }
438 
439 void PreprocessingRecord::Defined(const Token &MacroNameTok,
440                                   const MacroDefinition &MD,
441                                   SourceRange Range) {
442   // This is not actually a macro expansion but record it as a macro reference.
443   if (MD)
444     addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
445                       MacroNameTok.getLocation());
446 }
447 
448 void PreprocessingRecord::SourceRangeSkipped(SourceRange Range,
449                                              SourceLocation EndifLoc) {
450   assert(Range.isValid());
451   SkippedRanges.emplace_back(Range.getBegin(), EndifLoc);
452 }
453 
454 void PreprocessingRecord::MacroExpands(const Token &Id,
455                                        const MacroDefinition &MD,
456                                        SourceRange Range,
457                                        const MacroArgs *Args) {
458   addMacroExpansion(Id, MD.getMacroInfo(), Range);
459 }
460 
461 void PreprocessingRecord::MacroDefined(const Token &Id,
462                                        const MacroDirective *MD) {
463   const MacroInfo *MI = MD->getMacroInfo();
464   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
465   MacroDefinitionRecord *Def =
466       new (*this) MacroDefinitionRecord(Id.getIdentifierInfo(), R);
467   addPreprocessedEntity(Def);
468   MacroDefinitions[MI] = Def;
469 }
470 
471 void PreprocessingRecord::MacroUndefined(const Token &Id,
472                                          const MacroDefinition &MD,
473                                          const MacroDirective *Undef) {
474   MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });
475 }
476 
477 void PreprocessingRecord::InclusionDirective(
478     SourceLocation HashLoc, const Token &IncludeTok, StringRef FileName,
479     bool IsAngled, CharSourceRange FilenameRange, OptionalFileEntryRef File,
480     StringRef SearchPath, StringRef RelativePath, const Module *Imported,
481     SrcMgr::CharacteristicKind FileType) {
482   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
483 
484   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
485   case tok::pp_include:
486     Kind = InclusionDirective::Include;
487     break;
488 
489   case tok::pp_import:
490     Kind = InclusionDirective::Import;
491     break;
492 
493   case tok::pp_include_next:
494     Kind = InclusionDirective::IncludeNext;
495     break;
496 
497   case tok::pp___include_macros:
498     Kind = InclusionDirective::IncludeMacros;
499     break;
500 
501   default:
502     llvm_unreachable("Unknown include directive kind");
503   }
504 
505   SourceLocation EndLoc;
506   if (!IsAngled) {
507     EndLoc = FilenameRange.getBegin();
508   } else {
509     EndLoc = FilenameRange.getEnd();
510     if (FilenameRange.isCharRange())
511       EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
512                                             // a token range.
513   }
514   clang::InclusionDirective *ID =
515       new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
516                                             (bool)Imported, File,
517                                             SourceRange(HashLoc, EndLoc));
518   addPreprocessedEntity(ID);
519 }
520 
521 size_t PreprocessingRecord::getTotalMemory() const {
522   return BumpAlloc.getTotalMemory()
523     + llvm::capacity_in_bytes(MacroDefinitions)
524     + llvm::capacity_in_bytes(PreprocessedEntities)
525     + llvm::capacity_in_bytes(LoadedPreprocessedEntities)
526     + llvm::capacity_in_bytes(SkippedRanges);
527 }
528