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