PreprocessingRecord.cpp revision 243830 
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, 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                                         bool RecordConditionalDirectives)
43  : SourceMgr(SM),
44    RecordCondDirectives(RecordConditionalDirectives), CondDirectiveNextIdx(0),
45    ExternalSource(0)
46{
47  if (RecordCondDirectives)
48    CondDirectiveStack.push_back(CondDirectiveNextIdx++);
49}
50
51/// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
52/// that source range \p Range encompasses.
53std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
54PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
55  if (Range.isInvalid())
56    return std::make_pair(iterator(), iterator());
57
58  if (CachedRangeQuery.Range == Range) {
59    return std::make_pair(iterator(this, CachedRangeQuery.Result.first),
60                          iterator(this, CachedRangeQuery.Result.second));
61  }
62
63  std::pair<int, int> 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  int Pos = PPEI.Position;
99  if (Pos < 0) {
100    assert(unsigned(-Pos-1) < LoadedPreprocessedEntities.size() &&
101           "Out-of bounds loaded preprocessed entity");
102    assert(ExternalSource && "No external source to load from");
103    unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;
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(Pos) < PreprocessedEntities.size() &&
122         "Out-of bounds local preprocessed entity");
123  return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
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<int, int>
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.ID < 0) {
323    unsigned Index = -PPID.ID - 1;
324    assert(Index < LoadedPreprocessedEntities.size() &&
325           "Out-of bounds loaded preprocessed entity");
326    return getLoadedPreprocessedEntity(Index);
327  }
328
329  if (PPID.ID == 0)
330    return 0;
331  unsigned Index = PPID.ID - 1;
332  assert(Index < PreprocessedEntities.size() &&
333         "Out-of bounds local preprocessed entity");
334  return PreprocessedEntities[Index];
335}
336
337/// \brief Retrieve the loaded preprocessed entity at the given index.
338PreprocessedEntity *
339PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
340  assert(Index < LoadedPreprocessedEntities.size() &&
341         "Out-of bounds loaded preprocessed entity");
342  assert(ExternalSource && "No external source to load from");
343  PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
344  if (!Entity) {
345    Entity = ExternalSource->ReadPreprocessedEntity(Index);
346    if (!Entity) // Failed to load.
347      Entity = new (*this)
348         PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
349  }
350  return Entity;
351}
352
353MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
354  llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
355    = MacroDefinitions.find(MI);
356  if (Pos == MacroDefinitions.end())
357    return 0;
358
359  PreprocessedEntity *Entity = getPreprocessedEntity(Pos->second);
360  if (Entity->isInvalid())
361    return 0;
362  return cast<MacroDefinition>(Entity);
363}
364
365void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
366                                       SourceRange Range) {
367  // We don't record nested macro expansions.
368  if (Id.getLocation().isMacroID())
369    return;
370
371  if (MI->isBuiltinMacro())
372    addPreprocessedEntity(
373                      new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
374  else if (MacroDefinition *Def = findMacroDefinition(MI))
375    addPreprocessedEntity(
376                       new (*this) MacroExpansion(Def, Range));
377}
378
379void PreprocessingRecord::MacroDefined(const Token &Id,
380                                       const MacroInfo *MI) {
381  SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
382  MacroDefinition *Def
383      = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
384  MacroDefinitions[MI] = addPreprocessedEntity(Def);
385}
386
387void PreprocessingRecord::MacroUndefined(const Token &Id,
388                                         const MacroInfo *MI) {
389  MacroDefinitions.erase(MI);
390}
391
392void PreprocessingRecord::InclusionDirective(
393    SourceLocation HashLoc,
394    const clang::Token &IncludeTok,
395    StringRef FileName,
396    bool IsAngled,
397    CharSourceRange FilenameRange,
398    const FileEntry *File,
399    StringRef SearchPath,
400    StringRef RelativePath,
401    const Module *Imported) {
402  InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
403
404  switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
405  case tok::pp_include:
406    Kind = InclusionDirective::Include;
407    break;
408
409  case tok::pp_import:
410    Kind = InclusionDirective::Import;
411    break;
412
413  case tok::pp_include_next:
414    Kind = InclusionDirective::IncludeNext;
415    break;
416
417  case tok::pp___include_macros:
418    Kind = InclusionDirective::IncludeMacros;
419    break;
420
421  default:
422    llvm_unreachable("Unknown include directive kind");
423  }
424
425  SourceLocation EndLoc;
426  if (!IsAngled) {
427    EndLoc = FilenameRange.getBegin();
428  } else {
429    EndLoc = FilenameRange.getEnd();
430    if (FilenameRange.isCharRange())
431      EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
432                                            // a token range.
433  }
434  clang::InclusionDirective *ID
435    = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
436                                            (bool)Imported,
437                                            File, SourceRange(HashLoc, EndLoc));
438  addPreprocessedEntity(ID);
439}
440
441bool PreprocessingRecord::rangeIntersectsConditionalDirective(
442                                                      SourceRange Range) const {
443  if (Range.isInvalid())
444    return false;
445
446  CondDirectiveLocsTy::const_iterator
447    low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
448                           Range.getBegin(), CondDirectiveLoc::Comp(SourceMgr));
449  if (low == CondDirectiveLocs.end())
450    return false;
451
452  if (SourceMgr.isBeforeInTranslationUnit(Range.getEnd(), low->getLoc()))
453    return false;
454
455  CondDirectiveLocsTy::const_iterator
456    upp = std::upper_bound(low, CondDirectiveLocs.end(),
457                           Range.getEnd(), CondDirectiveLoc::Comp(SourceMgr));
458  unsigned uppIdx;
459  if (upp != CondDirectiveLocs.end())
460    uppIdx = upp->getIdx();
461  else
462    uppIdx = 0;
463
464  return low->getIdx() != uppIdx;
465}
466
467unsigned PreprocessingRecord::findCondDirectiveIdx(SourceLocation Loc) const {
468  if (Loc.isInvalid())
469    return 0;
470
471  CondDirectiveLocsTy::const_iterator
472    low = std::lower_bound(CondDirectiveLocs.begin(), CondDirectiveLocs.end(),
473                           Loc, CondDirectiveLoc::Comp(SourceMgr));
474  if (low == CondDirectiveLocs.end())
475    return 0;
476  return low->getIdx();
477}
478
479void PreprocessingRecord::addCondDirectiveLoc(CondDirectiveLoc DirLoc) {
480  // Ignore directives in system headers.
481  if (SourceMgr.isInSystemHeader(DirLoc.getLoc()))
482    return;
483
484  assert(CondDirectiveLocs.empty() ||
485         SourceMgr.isBeforeInTranslationUnit(CondDirectiveLocs.back().getLoc(),
486                                             DirLoc.getLoc()));
487  CondDirectiveLocs.push_back(DirLoc);
488}
489
490void PreprocessingRecord::If(SourceLocation Loc, SourceRange ConditionRange) {
491  if (RecordCondDirectives) {
492    addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
493    CondDirectiveStack.push_back(CondDirectiveNextIdx++);
494  }
495}
496
497void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok) {
498  if (RecordCondDirectives) {
499    addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
500    CondDirectiveStack.push_back(CondDirectiveNextIdx++);
501  }
502}
503
504void PreprocessingRecord::Ifndef(SourceLocation Loc,const Token &MacroNameTok) {
505  if (RecordCondDirectives) {
506    addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
507    CondDirectiveStack.push_back(CondDirectiveNextIdx++);
508  }
509}
510
511void PreprocessingRecord::Elif(SourceLocation Loc, SourceRange ConditionRange,
512                               SourceLocation IfLoc) {
513  if (RecordCondDirectives)
514    addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
515}
516
517void PreprocessingRecord::Else(SourceLocation Loc, SourceLocation IfLoc) {
518  if (RecordCondDirectives)
519    addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
520}
521
522void PreprocessingRecord::Endif(SourceLocation Loc, SourceLocation IfLoc) {
523  if (RecordCondDirectives) {
524    addCondDirectiveLoc(CondDirectiveLoc(Loc, CondDirectiveStack.back()));
525    assert(!CondDirectiveStack.empty());
526    CondDirectiveStack.pop_back();
527  }
528}
529
530size_t PreprocessingRecord::getTotalMemory() const {
531  return BumpAlloc.getTotalMemory()
532    + llvm::capacity_in_bytes(MacroDefinitions)
533    + llvm::capacity_in_bytes(PreprocessedEntities)
534    + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
535}
536