1//===--- PreprocessingRecord.cpp - Record of Preprocessing ------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10//  This file implements the PreprocessingRecord class, which maintains a record
11//  of what occurred during preprocessing, and its helpers.
12//
13//===----------------------------------------------------------------------===//
14#include "clang/Lex/PreprocessingRecord.h"
15#include "clang/Lex/MacroInfo.h"
16#include "clang/Lex/Token.h"
17#include "llvm/Support/Capacity.h"
18#include "llvm/Support/ErrorHandling.h"
19
20using namespace clang;
21
22ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }
23
24
25InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
26                                       InclusionKind Kind,
27                                       StringRef FileName,
28                                       bool InQuotes, bool ImportedModule,
29                                       const FileEntry *File,
30                                       SourceRange Range)
31  : PreprocessingDirective(InclusionDirectiveKind, Range),
32    InQuotes(InQuotes), Kind(Kind), ImportedModule(ImportedModule), File(File)
33{
34  char *Memory
35    = (char*)PPRec.Allocate(FileName.size() + 1, llvm::alignOf<char>());
36  memcpy(Memory, FileName.data(), FileName.size());
37  Memory[FileName.size()] = 0;
38  this->FileName = StringRef(Memory, FileName.size());
39}
40
41PreprocessingRecord::PreprocessingRecord(SourceManager &SM)
42  : SourceMgr(SM),
43    ExternalSource(nullptr) {
44}
45
46/// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
47/// that source range \p Range encompasses.
48std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
49PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
50  if (Range.isInvalid())
51    return std::make_pair(iterator(), iterator());
52
53  if (CachedRangeQuery.Range == Range) {
54    return std::make_pair(iterator(this, CachedRangeQuery.Result.first),
55                          iterator(this, CachedRangeQuery.Result.second));
56  }
57
58  std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range);
59
60  CachedRangeQuery.Range = Range;
61  CachedRangeQuery.Result = Res;
62
63  return std::make_pair(iterator(this, Res.first), iterator(this, Res.second));
64}
65
66static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
67                                           SourceManager &SM) {
68  assert(!FID.isInvalid());
69  if (!PPE)
70    return false;
71
72  SourceLocation Loc = PPE->getSourceRange().getBegin();
73  if (Loc.isInvalid())
74    return false;
75
76  if (SM.isInFileID(SM.getFileLoc(Loc), FID))
77    return true;
78  else
79    return false;
80}
81
82/// \brief Returns true if the preprocessed entity that \arg PPEI iterator
83/// points to is coming from the file \arg FID.
84///
85/// Can be used to avoid implicit deserializations of preallocated
86/// preprocessed entities if we only care about entities of a specific file
87/// and not from files \#included in the range given at
88/// \see getPreprocessedEntitiesInRange.
89bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
90  if (FID.isInvalid())
91    return false;
92
93  int Pos = PPEI.Position;
94  if (Pos < 0) {
95    if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) {
96      assert(0 && "Out-of bounds loaded preprocessed entity");
97      return false;
98    }
99    assert(ExternalSource && "No external source to load from");
100    unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;
101    if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
102      return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);
103
104    // See if the external source can see if the entity is in the file without
105    // deserializing it.
106    Optional<bool> IsInFile =
107        ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
108    if (IsInFile.hasValue())
109      return IsInFile.getValue();
110
111    // The external source did not provide a definite answer, go and deserialize
112    // the entity to check it.
113    return isPreprocessedEntityIfInFileID(
114                                       getLoadedPreprocessedEntity(LoadedIndex),
115                                          FID, SourceMgr);
116  }
117
118  if (unsigned(Pos) >= PreprocessedEntities.size()) {
119    assert(0 && "Out-of bounds local preprocessed entity");
120    return false;
121  }
122  return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
123                                        FID, SourceMgr);
124}
125
126/// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
127/// that source range \arg R encompasses.
128std::pair<int, int>
129PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
130  assert(Range.isValid());
131  assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
132
133  std::pair<unsigned, unsigned>
134    Local = findLocalPreprocessedEntitiesInRange(Range);
135
136  // Check if range spans local entities.
137  if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
138    return std::make_pair(Local.first, Local.second);
139
140  std::pair<unsigned, unsigned>
141    Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
142
143  // Check if range spans local entities.
144  if (Loaded.first == Loaded.second)
145    return std::make_pair(Local.first, Local.second);
146
147  unsigned TotalLoaded = LoadedPreprocessedEntities.size();
148
149  // Check if range spans loaded entities.
150  if (Local.first == Local.second)
151    return std::make_pair(int(Loaded.first)-TotalLoaded,
152                          int(Loaded.second)-TotalLoaded);
153
154  // Range spands loaded and local entities.
155  return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
156}
157
158std::pair<unsigned, unsigned>
159PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
160                                                      SourceRange Range) const {
161  if (Range.isInvalid())
162    return std::make_pair(0,0);
163  assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
164
165  unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
166  unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
167  return std::make_pair(Begin, End);
168}
169
170namespace {
171
172template <SourceLocation (SourceRange::*getRangeLoc)() const>
173struct PPEntityComp {
174  const SourceManager &SM;
175
176  explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
177
178  bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
179    SourceLocation LHS = getLoc(L);
180    SourceLocation RHS = getLoc(R);
181    return SM.isBeforeInTranslationUnit(LHS, RHS);
182  }
183
184  bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
185    SourceLocation LHS = getLoc(L);
186    return SM.isBeforeInTranslationUnit(LHS, RHS);
187  }
188
189  bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
190    SourceLocation RHS = getLoc(R);
191    return SM.isBeforeInTranslationUnit(LHS, RHS);
192  }
193
194  SourceLocation getLoc(PreprocessedEntity *PPE) const {
195    SourceRange Range = PPE->getSourceRange();
196    return (Range.*getRangeLoc)();
197  }
198};
199
200}
201
202unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
203                                                     SourceLocation Loc) const {
204  if (SourceMgr.isLoadedSourceLocation(Loc))
205    return 0;
206
207  size_t Count = PreprocessedEntities.size();
208  size_t Half;
209  std::vector<PreprocessedEntity *>::const_iterator
210    First = PreprocessedEntities.begin();
211  std::vector<PreprocessedEntity *>::const_iterator I;
212
213  // Do a binary search manually instead of using std::lower_bound because
214  // The end locations of entities may be unordered (when a macro expansion
215  // is inside another macro argument), but for this case it is not important
216  // whether we get the first macro expansion or its containing macro.
217  while (Count > 0) {
218    Half = Count/2;
219    I = First;
220    std::advance(I, Half);
221    if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
222                                            Loc)){
223      First = I;
224      ++First;
225      Count = Count - Half - 1;
226    } else
227      Count = Half;
228  }
229
230  return First - PreprocessedEntities.begin();
231}
232
233unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
234                                                     SourceLocation Loc) const {
235  if (SourceMgr.isLoadedSourceLocation(Loc))
236    return 0;
237
238  std::vector<PreprocessedEntity *>::const_iterator
239  I = std::upper_bound(PreprocessedEntities.begin(),
240                       PreprocessedEntities.end(),
241                       Loc,
242                       PPEntityComp<&SourceRange::getBegin>(SourceMgr));
243  return I - PreprocessedEntities.begin();
244}
245
246PreprocessingRecord::PPEntityID
247PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
248  assert(Entity);
249  SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
250
251  if (isa<MacroDefinition>(Entity)) {
252    assert((PreprocessedEntities.empty() ||
253            !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
254                   PreprocessedEntities.back()->getSourceRange().getBegin())) &&
255           "a macro definition was encountered out-of-order");
256    PreprocessedEntities.push_back(Entity);
257    return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
258  }
259
260  // Check normal case, this entity begin location is after the previous one.
261  if (PreprocessedEntities.empty() ||
262      !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
263                   PreprocessedEntities.back()->getSourceRange().getBegin())) {
264    PreprocessedEntities.push_back(Entity);
265    return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
266  }
267
268  // The entity's location is not after the previous one; this can happen with
269  // include directives that form the filename using macros, e.g:
270  // "#include MACRO(STUFF)"
271  // or with macro expansions inside macro arguments where the arguments are
272  // not expanded in the same order as listed, e.g:
273  // \code
274  //  #define M1 1
275  //  #define M2 2
276  //  #define FM(x,y) y x
277  //  FM(M1, M2)
278  // \endcode
279
280  typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
281
282  // Usually there are few macro expansions when defining the filename, do a
283  // linear search for a few entities.
284  unsigned count = 0;
285  for (pp_iter RI    = PreprocessedEntities.end(),
286               Begin = PreprocessedEntities.begin();
287       RI != Begin && count < 4; --RI, ++count) {
288    pp_iter I = RI;
289    --I;
290    if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
291                                           (*I)->getSourceRange().getBegin())) {
292      pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
293      return getPPEntityID(insertI - PreprocessedEntities.begin(),
294                           /*isLoaded=*/false);
295    }
296  }
297
298  // Linear search unsuccessful. Do a binary search.
299  pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
300                               PreprocessedEntities.end(),
301                               BeginLoc,
302                               PPEntityComp<&SourceRange::getBegin>(SourceMgr));
303  pp_iter insertI = PreprocessedEntities.insert(I, Entity);
304  return getPPEntityID(insertI - PreprocessedEntities.begin(),
305                       /*isLoaded=*/false);
306}
307
308void PreprocessingRecord::SetExternalSource(
309                                    ExternalPreprocessingRecordSource &Source) {
310  assert(!ExternalSource &&
311         "Preprocessing record already has an external source");
312  ExternalSource = &Source;
313}
314
315unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
316  unsigned Result = LoadedPreprocessedEntities.size();
317  LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
318                                    + NumEntities);
319  return Result;
320}
321
322void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
323                                                  MacroDefinition *Def) {
324  MacroDefinitions[Macro] = Def;
325}
326
327/// \brief Retrieve the preprocessed entity at the given ID.
328PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
329  if (PPID.ID < 0) {
330    unsigned Index = -PPID.ID - 1;
331    assert(Index < LoadedPreprocessedEntities.size() &&
332           "Out-of bounds loaded preprocessed entity");
333    return getLoadedPreprocessedEntity(Index);
334  }
335
336  if (PPID.ID == 0)
337    return nullptr;
338  unsigned Index = PPID.ID - 1;
339  assert(Index < PreprocessedEntities.size() &&
340         "Out-of bounds local preprocessed entity");
341  return PreprocessedEntities[Index];
342}
343
344/// \brief Retrieve the loaded preprocessed entity at the given index.
345PreprocessedEntity *
346PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
347  assert(Index < LoadedPreprocessedEntities.size() &&
348         "Out-of bounds loaded preprocessed entity");
349  assert(ExternalSource && "No external source to load from");
350  PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
351  if (!Entity) {
352    Entity = ExternalSource->ReadPreprocessedEntity(Index);
353    if (!Entity) // Failed to load.
354      Entity = new (*this)
355         PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
356  }
357  return Entity;
358}
359
360MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
361  llvm::DenseMap<const MacroInfo *, MacroDefinition *>::iterator Pos
362    = MacroDefinitions.find(MI);
363  if (Pos == MacroDefinitions.end())
364    return nullptr;
365
366  return Pos->second;
367}
368
369void PreprocessingRecord::addMacroExpansion(const Token &Id,
370                                            const MacroInfo *MI,
371                                            SourceRange Range) {
372  // We don't record nested macro expansions.
373  if (Id.getLocation().isMacroID())
374    return;
375
376  if (MI->isBuiltinMacro())
377    addPreprocessedEntity(
378                      new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
379  else if (MacroDefinition *Def = findMacroDefinition(MI))
380    addPreprocessedEntity(
381                       new (*this) MacroExpansion(Def, Range));
382}
383
384void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,
385                                const MacroDirective *MD) {
386  // This is not actually a macro expansion but record it as a macro reference.
387  if (MD)
388    addMacroExpansion(MacroNameTok, MD->getMacroInfo(),
389                      MacroNameTok.getLocation());
390}
391
392void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
393                                 const MacroDirective *MD) {
394  // This is not actually a macro expansion but record it as a macro reference.
395  if (MD)
396    addMacroExpansion(MacroNameTok, MD->getMacroInfo(),
397                      MacroNameTok.getLocation());
398}
399
400void PreprocessingRecord::Defined(const Token &MacroNameTok,
401                                  const MacroDirective *MD,
402                                  SourceRange Range) {
403  // This is not actually a macro expansion but record it as a macro reference.
404  if (MD)
405    addMacroExpansion(MacroNameTok, MD->getMacroInfo(),
406                      MacroNameTok.getLocation());
407}
408
409void PreprocessingRecord::SourceRangeSkipped(SourceRange Range) {
410  SkippedRanges.push_back(Range);
411}
412
413void PreprocessingRecord::MacroExpands(const Token &Id,const MacroDirective *MD,
414                                       SourceRange Range,
415                                       const MacroArgs *Args) {
416  addMacroExpansion(Id, MD->getMacroInfo(), Range);
417}
418
419void PreprocessingRecord::MacroDefined(const Token &Id,
420                                       const MacroDirective *MD) {
421  const MacroInfo *MI = MD->getMacroInfo();
422  SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
423  MacroDefinition *Def
424      = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
425  addPreprocessedEntity(Def);
426  MacroDefinitions[MI] = Def;
427}
428
429void PreprocessingRecord::MacroUndefined(const Token &Id,
430                                         const MacroDirective *MD) {
431  // Note: MI may be null (when #undef'ining an undefined macro).
432  if (MD)
433    MacroDefinitions.erase(MD->getMacroInfo());
434}
435
436void PreprocessingRecord::InclusionDirective(
437    SourceLocation HashLoc,
438    const clang::Token &IncludeTok,
439    StringRef FileName,
440    bool IsAngled,
441    CharSourceRange FilenameRange,
442    const FileEntry *File,
443    StringRef SearchPath,
444    StringRef RelativePath,
445    const Module *Imported) {
446  InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
447
448  switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
449  case tok::pp_include:
450    Kind = InclusionDirective::Include;
451    break;
452
453  case tok::pp_import:
454    Kind = InclusionDirective::Import;
455    break;
456
457  case tok::pp_include_next:
458    Kind = InclusionDirective::IncludeNext;
459    break;
460
461  case tok::pp___include_macros:
462    Kind = InclusionDirective::IncludeMacros;
463    break;
464
465  default:
466    llvm_unreachable("Unknown include directive kind");
467  }
468
469  SourceLocation EndLoc;
470  if (!IsAngled) {
471    EndLoc = FilenameRange.getBegin();
472  } else {
473    EndLoc = FilenameRange.getEnd();
474    if (FilenameRange.isCharRange())
475      EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
476                                            // a token range.
477  }
478  clang::InclusionDirective *ID
479    = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
480                                            (bool)Imported,
481                                            File, SourceRange(HashLoc, EndLoc));
482  addPreprocessedEntity(ID);
483}
484
485size_t PreprocessingRecord::getTotalMemory() const {
486  return BumpAlloc.getTotalMemory()
487    + llvm::capacity_in_bytes(MacroDefinitions)
488    + llvm::capacity_in_bytes(PreprocessedEntities)
489    + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
490}
491