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