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
37using namespace clang;
38
39ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() =
40    default;
41
42InclusionDirective::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
55PreprocessingRecord::PreprocessingRecord(SourceManager &SM) : SourceMgr(SM) {}
56
57/// Returns a pair of [Begin, End) iterators of preprocessed entities
58/// that source range \p Range encompasses.
59llvm::iterator_range<PreprocessingRecord::iterator>
60PreprocessingRecord::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
78static 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.
98bool 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.
136std::pair<int, int>
137PreprocessingRecord::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
166std::pair<unsigned, unsigned>
167PreprocessingRecord::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
178namespace {
179
180template <SourceLocation (SourceRange::*getRangeLoc)() const>
181struct 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
210unsigned 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
241unsigned
242PreprocessingRecord::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
251PreprocessingRecord::PPEntityID
252PreprocessingRecord::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
313void PreprocessingRecord::SetExternalSource(
314                                    ExternalPreprocessingRecordSource &Source) {
315  assert(!ExternalSource &&
316         "Preprocessing record already has an external source");
317  ExternalSource = &Source;
318}
319
320unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
321  unsigned Result = LoadedPreprocessedEntities.size();
322  LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
323                                    + NumEntities);
324  return Result;
325}
326
327unsigned PreprocessingRecord::allocateSkippedRanges(unsigned NumRanges) {
328  unsigned Result = SkippedRanges.size();
329  SkippedRanges.resize(SkippedRanges.size() + NumRanges);
330  SkippedRangesAllLoaded = false;
331  return Result;
332}
333
334void 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
344void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
345                                                  MacroDefinitionRecord *Def) {
346  MacroDefinitions[Macro] = Def;
347}
348
349/// Retrieve the preprocessed entity at the given ID.
350PreprocessedEntity *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.
367PreprocessedEntity *
368PreprocessingRecord::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
382MacroDefinitionRecord *
383PreprocessingRecord::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
392void 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
406void 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
414void 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
422void 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
430void 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
439void 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
448void PreprocessingRecord::SourceRangeSkipped(SourceRange Range,
449                                             SourceLocation EndifLoc) {
450  assert(Range.isValid());
451  SkippedRanges.emplace_back(Range.getBegin(), EndifLoc);
452}
453
454void PreprocessingRecord::MacroExpands(const Token &Id,
455                                       const MacroDefinition &MD,
456                                       SourceRange Range,
457                                       const MacroArgs *Args) {
458  addMacroExpansion(Id, MD.getMacroInfo(), Range);
459}
460
461void 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
471void PreprocessingRecord::MacroUndefined(const Token &Id,
472                                         const MacroDefinition &MD,
473                                         const MacroDirective *Undef) {
474  MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });
475}
476
477void 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
521size_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