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
37using namespace clang;
38
39ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() =
40    default;
41
42InclusionDirective::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
54PreprocessingRecord::PreprocessingRecord(SourceManager &SM) : SourceMgr(SM) {}
55
56/// Returns a pair of [Begin, End) iterators of preprocessed entities
57/// that source range \p Range encompasses.
58llvm::iterator_range<PreprocessingRecord::iterator>
59PreprocessingRecord::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
77static 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.
97bool 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.
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::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
422void 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
431void PreprocessingRecord::SourceRangeSkipped(SourceRange Range,
432                                             SourceLocation EndifLoc) {
433  assert(Range.isValid());
434  SkippedRanges.emplace_back(Range.getBegin(), EndifLoc);
435}
436
437void PreprocessingRecord::MacroExpands(const Token &Id,
438                                       const MacroDefinition &MD,
439                                       SourceRange Range,
440                                       const MacroArgs *Args) {
441  addMacroExpansion(Id, MD.getMacroInfo(), Range);
442}
443
444void 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
454void PreprocessingRecord::MacroUndefined(const Token &Id,
455                                         const MacroDefinition &MD,
456                                         const MacroDirective *Undef) {
457  MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });
458}
459
460void 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
510size_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