PreprocessingRecord.cpp revision 263508 
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(0) {
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 0;
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 0;
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::MacroExpands(const Token &Id,const MacroDirective *MD,
410                                       SourceRange Range,
411                                       const MacroArgs *Args) {
412  addMacroExpansion(Id, MD->getMacroInfo(), Range);
413}
414
415void PreprocessingRecord::MacroDefined(const Token &Id,
416                                       const MacroDirective *MD) {
417  const MacroInfo *MI = MD->getMacroInfo();
418  SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
419  MacroDefinition *Def
420      = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
421  addPreprocessedEntity(Def);
422  MacroDefinitions[MI] = Def;
423}
424
425void PreprocessingRecord::MacroUndefined(const Token &Id,
426                                         const MacroDirective *MD) {
427  // Note: MI may be null (when #undef'ining an undefined macro).
428  if (MD)
429    MacroDefinitions.erase(MD->getMacroInfo());
430}
431
432void PreprocessingRecord::InclusionDirective(
433    SourceLocation HashLoc,
434    const clang::Token &IncludeTok,
435    StringRef FileName,
436    bool IsAngled,
437    CharSourceRange FilenameRange,
438    const FileEntry *File,
439    StringRef SearchPath,
440    StringRef RelativePath,
441    const Module *Imported) {
442  InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
443
444  switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
445  case tok::pp_include:
446    Kind = InclusionDirective::Include;
447    break;
448
449  case tok::pp_import:
450    Kind = InclusionDirective::Import;
451    break;
452
453  case tok::pp_include_next:
454    Kind = InclusionDirective::IncludeNext;
455    break;
456
457  case tok::pp___include_macros:
458    Kind = InclusionDirective::IncludeMacros;
459    break;
460
461  default:
462    llvm_unreachable("Unknown include directive kind");
463  }
464
465  SourceLocation EndLoc;
466  if (!IsAngled) {
467    EndLoc = FilenameRange.getBegin();
468  } else {
469    EndLoc = FilenameRange.getEnd();
470    if (FilenameRange.isCharRange())
471      EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
472                                            // a token range.
473  }
474  clang::InclusionDirective *ID
475    = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
476                                            (bool)Imported,
477                                            File, SourceRange(HashLoc, EndLoc));
478  addPreprocessedEntity(ID);
479}
480
481size_t PreprocessingRecord::getTotalMemory() const {
482  return BumpAlloc.getTotalMemory()
483    + llvm::capacity_in_bytes(MacroDefinitions)
484    + llvm::capacity_in_bytes(PreprocessedEntities)
485    + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
486}
487