clang  6.0.0svn
PreprocessingRecord.cpp
Go to the documentation of this file.
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 //===----------------------------------------------------------------------===//
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 
20 using namespace clang;
21 
23 
25  InclusionKind Kind, StringRef FileName,
26  bool InQuotes, bool ImportedModule,
27  const FileEntry *File, SourceRange Range)
28  : PreprocessingDirective(InclusionDirectiveKind, Range), InQuotes(InQuotes),
29  Kind(Kind), ImportedModule(ImportedModule), File(File) {
30  char *Memory = (char *)PPRec.Allocate(FileName.size() + 1, alignof(char));
31  memcpy(Memory, FileName.data(), FileName.size());
32  Memory[FileName.size()] = 0;
33  this->FileName = StringRef(Memory, FileName.size());
34 }
35 
37  : SourceMgr(SM),
38  ExternalSource(nullptr) {
39 }
40 
41 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
42 /// that source range \p Range encompasses.
43 llvm::iterator_range<PreprocessingRecord::iterator>
45  if (Range.isInvalid())
46  return llvm::make_range(iterator(), iterator());
47 
48  if (CachedRangeQuery.Range == Range) {
49  return llvm::make_range(iterator(this, CachedRangeQuery.Result.first),
50  iterator(this, CachedRangeQuery.Result.second));
51  }
52 
53  std::pair<int, int> Res = getPreprocessedEntitiesInRangeSlow(Range);
54 
55  CachedRangeQuery.Range = Range;
56  CachedRangeQuery.Result = Res;
57 
58  return llvm::make_range(iterator(this, Res.first),
59  iterator(this, Res.second));
60 }
61 
63  SourceManager &SM) {
64  assert(FID.isValid());
65  if (!PPE)
66  return false;
67 
68  SourceLocation Loc = PPE->getSourceRange().getBegin();
69  if (Loc.isInvalid())
70  return false;
71 
72  return SM.isInFileID(SM.getFileLoc(Loc), FID);
73 }
74 
75 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
76 /// points to is coming from the file \arg FID.
77 ///
78 /// Can be used to avoid implicit deserializations of preallocated
79 /// preprocessed entities if we only care about entities of a specific file
80 /// and not from files \#included in the range given at
81 /// \see getPreprocessedEntitiesInRange.
83  if (FID.isInvalid())
84  return false;
85 
86  int Pos = std::distance(iterator(this, 0), PPEI);
87  if (Pos < 0) {
88  if (unsigned(-Pos-1) >= LoadedPreprocessedEntities.size()) {
89  assert(0 && "Out-of bounds loaded preprocessed entity");
90  return false;
91  }
92  assert(ExternalSource && "No external source to load from");
93  unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;
94  if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
95  return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);
96 
97  // See if the external source can see if the entity is in the file without
98  // deserializing it.
99  Optional<bool> IsInFile =
100  ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
101  if (IsInFile.hasValue())
102  return IsInFile.getValue();
103 
104  // The external source did not provide a definite answer, go and deserialize
105  // the entity to check it.
107  getLoadedPreprocessedEntity(LoadedIndex),
108  FID, SourceMgr);
109  }
110 
111  if (unsigned(Pos) >= PreprocessedEntities.size()) {
112  assert(0 && "Out-of bounds local preprocessed entity");
113  return false;
114  }
115  return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
116  FID, SourceMgr);
117 }
118 
119 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
120 /// that source range \arg R encompasses.
121 std::pair<int, int>
122 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
123  assert(Range.isValid());
124  assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
125 
126  std::pair<unsigned, unsigned>
127  Local = findLocalPreprocessedEntitiesInRange(Range);
128 
129  // Check if range spans local entities.
130  if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
131  return std::make_pair(Local.first, Local.second);
132 
133  std::pair<unsigned, unsigned>
134  Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
135 
136  // Check if range spans local entities.
137  if (Loaded.first == Loaded.second)
138  return std::make_pair(Local.first, Local.second);
139 
140  unsigned TotalLoaded = LoadedPreprocessedEntities.size();
141 
142  // Check if range spans loaded entities.
143  if (Local.first == Local.second)
144  return std::make_pair(int(Loaded.first)-TotalLoaded,
145  int(Loaded.second)-TotalLoaded);
146 
147  // Range spands loaded and local entities.
148  return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
149 }
150 
151 std::pair<unsigned, unsigned>
152 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
153  SourceRange Range) const {
154  if (Range.isInvalid())
155  return std::make_pair(0,0);
156  assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
157 
158  unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
159  unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
160  return std::make_pair(Begin, End);
161 }
162 
163 namespace {
164 
165 template <SourceLocation (SourceRange::*getRangeLoc)() const>
166 struct PPEntityComp {
167  const SourceManager &SM;
168 
169  explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
170 
171  bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
172  SourceLocation LHS = getLoc(L);
173  SourceLocation RHS = getLoc(R);
174  return SM.isBeforeInTranslationUnit(LHS, RHS);
175  }
176 
177  bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
178  SourceLocation LHS = getLoc(L);
179  return SM.isBeforeInTranslationUnit(LHS, RHS);
180  }
181 
182  bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
183  SourceLocation RHS = getLoc(R);
184  return SM.isBeforeInTranslationUnit(LHS, RHS);
185  }
186 
187  SourceLocation getLoc(PreprocessedEntity *PPE) const {
188  SourceRange Range = PPE->getSourceRange();
189  return (Range.*getRangeLoc)();
190  }
191 };
192 
193 }
194 
195 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
196  SourceLocation Loc) const {
197  if (SourceMgr.isLoadedSourceLocation(Loc))
198  return 0;
199 
200  size_t Count = PreprocessedEntities.size();
201  size_t Half;
202  std::vector<PreprocessedEntity *>::const_iterator
203  First = PreprocessedEntities.begin();
204  std::vector<PreprocessedEntity *>::const_iterator I;
205 
206  // Do a binary search manually instead of using std::lower_bound because
207  // The end locations of entities may be unordered (when a macro expansion
208  // is inside another macro argument), but for this case it is not important
209  // whether we get the first macro expansion or its containing macro.
210  while (Count > 0) {
211  Half = Count/2;
212  I = First;
213  std::advance(I, Half);
214  if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
215  Loc)){
216  First = I;
217  ++First;
218  Count = Count - Half - 1;
219  } else
220  Count = Half;
221  }
222 
223  return First - PreprocessedEntities.begin();
224 }
225 
226 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
227  SourceLocation Loc) const {
228  if (SourceMgr.isLoadedSourceLocation(Loc))
229  return 0;
230 
231  std::vector<PreprocessedEntity *>::const_iterator
232  I = std::upper_bound(PreprocessedEntities.begin(),
233  PreprocessedEntities.end(),
234  Loc,
235  PPEntityComp<&SourceRange::getBegin>(SourceMgr));
236  return I - PreprocessedEntities.begin();
237 }
238 
239 PreprocessingRecord::PPEntityID
241  assert(Entity);
242  SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
243 
244  if (isa<MacroDefinitionRecord>(Entity)) {
245  assert((PreprocessedEntities.empty() ||
246  !SourceMgr.isBeforeInTranslationUnit(
247  BeginLoc,
248  PreprocessedEntities.back()->getSourceRange().getBegin())) &&
249  "a macro definition was encountered out-of-order");
250  PreprocessedEntities.push_back(Entity);
251  return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
252  }
253 
254  // Check normal case, this entity begin location is after the previous one.
255  if (PreprocessedEntities.empty() ||
256  !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
257  PreprocessedEntities.back()->getSourceRange().getBegin())) {
258  PreprocessedEntities.push_back(Entity);
259  return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
260  }
261 
262  // The entity's location is not after the previous one; this can happen with
263  // include directives that form the filename using macros, e.g:
264  // "#include MACRO(STUFF)"
265  // or with macro expansions inside macro arguments where the arguments are
266  // not expanded in the same order as listed, e.g:
267  // \code
268  // #define M1 1
269  // #define M2 2
270  // #define FM(x,y) y x
271  // FM(M1, M2)
272  // \endcode
273 
274  typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
275 
276  // Usually there are few macro expansions when defining the filename, do a
277  // linear search for a few entities.
278  unsigned count = 0;
279  for (pp_iter RI = PreprocessedEntities.end(),
280  Begin = PreprocessedEntities.begin();
281  RI != Begin && count < 4; --RI, ++count) {
282  pp_iter I = RI;
283  --I;
284  if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
285  (*I)->getSourceRange().getBegin())) {
286  pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
287  return getPPEntityID(insertI - PreprocessedEntities.begin(),
288  /*isLoaded=*/false);
289  }
290  }
291 
292  // Linear search unsuccessful. Do a binary search.
293  pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
294  PreprocessedEntities.end(),
295  BeginLoc,
296  PPEntityComp<&SourceRange::getBegin>(SourceMgr));
297  pp_iter insertI = PreprocessedEntities.insert(I, Entity);
298  return getPPEntityID(insertI - PreprocessedEntities.begin(),
299  /*isLoaded=*/false);
300 }
301 
304  assert(!ExternalSource &&
305  "Preprocessing record already has an external source");
306  ExternalSource = &Source;
307 }
308 
309 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
310  unsigned Result = LoadedPreprocessedEntities.size();
311  LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
312  + NumEntities);
313  return Result;
314 }
315 
316 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
317  MacroDefinitionRecord *Def) {
318  MacroDefinitions[Macro] = Def;
319 }
320 
321 /// \brief Retrieve the preprocessed entity at the given ID.
322 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
323  if (PPID.ID < 0) {
324  unsigned Index = -PPID.ID - 1;
325  assert(Index < LoadedPreprocessedEntities.size() &&
326  "Out-of bounds loaded preprocessed entity");
327  return getLoadedPreprocessedEntity(Index);
328  }
329 
330  if (PPID.ID == 0)
331  return nullptr;
332  unsigned Index = PPID.ID - 1;
333  assert(Index < PreprocessedEntities.size() &&
334  "Out-of bounds local preprocessed entity");
335  return PreprocessedEntities[Index];
336 }
337 
338 /// \brief Retrieve the loaded preprocessed entity at the given index.
340 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
341  assert(Index < LoadedPreprocessedEntities.size() &&
342  "Out-of bounds loaded preprocessed entity");
343  assert(ExternalSource && "No external source to load from");
344  PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
345  if (!Entity) {
346  Entity = ExternalSource->ReadPreprocessedEntity(Index);
347  if (!Entity) // Failed to load.
348  Entity = new (*this)
350  }
351  return Entity;
352 }
353 
356  llvm::DenseMap<const MacroInfo *, MacroDefinitionRecord *>::iterator Pos =
357  MacroDefinitions.find(MI);
358  if (Pos == MacroDefinitions.end())
359  return nullptr;
360 
361  return Pos->second;
362 }
363 
364 void PreprocessingRecord::addMacroExpansion(const Token &Id,
365  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(new (*this)
374  else if (MacroDefinitionRecord *Def = findMacroDefinition(MI))
375  addPreprocessedEntity(new (*this) MacroExpansion(Def, Range));
376 }
377 
378 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,
379  const MacroDefinition &MD) {
380  // This is not actually a macro expansion but record it as a macro reference.
381  if (MD)
382  addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
383  MacroNameTok.getLocation());
384 }
385 
386 void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
387  const MacroDefinition &MD) {
388  // This is not actually a macro expansion but record it as a macro reference.
389  if (MD)
390  addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
391  MacroNameTok.getLocation());
392 }
393 
394 void PreprocessingRecord::Defined(const Token &MacroNameTok,
395  const MacroDefinition &MD,
396  SourceRange Range) {
397  // This is not actually a macro expansion but record it as a macro reference.
398  if (MD)
399  addMacroExpansion(MacroNameTok, MD.getMacroInfo(),
400  MacroNameTok.getLocation());
401 }
402 
403 void PreprocessingRecord::SourceRangeSkipped(SourceRange Range,
404  SourceLocation EndifLoc) {
405  SkippedRanges.emplace_back(Range.getBegin(), EndifLoc);
406 }
407 
408 void PreprocessingRecord::MacroExpands(const Token &Id,
409  const MacroDefinition &MD,
410  SourceRange Range,
411  const MacroArgs *Args) {
412  addMacroExpansion(Id, MD.getMacroInfo(), Range);
413 }
414 
415 void PreprocessingRecord::MacroDefined(const Token &Id,
416  const MacroDirective *MD) {
417  const MacroInfo *MI = MD->getMacroInfo();
419  MacroDefinitionRecord *Def =
420  new (*this) MacroDefinitionRecord(Id.getIdentifierInfo(), R);
422  MacroDefinitions[MI] = Def;
423 }
424 
425 void PreprocessingRecord::MacroUndefined(const Token &Id,
426  const MacroDefinition &MD,
427  const MacroDirective *Undef) {
428  MD.forAllDefinitions([&](MacroInfo *MI) { MacroDefinitions.erase(MI); });
429 }
430 
431 void PreprocessingRecord::InclusionDirective(
432  SourceLocation HashLoc,
433  const clang::Token &IncludeTok,
434  StringRef FileName,
435  bool IsAngled,
436  CharSourceRange FilenameRange,
437  const FileEntry *File,
438  StringRef SearchPath,
439  StringRef RelativePath,
440  const Module *Imported) {
442 
443  switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
444  case tok::pp_include:
446  break;
447 
448  case tok::pp_import:
450  break;
451 
452  case tok::pp_include_next:
454  break;
455 
456  case tok::pp___include_macros:
458  break;
459 
460  default:
461  llvm_unreachable("Unknown include directive kind");
462  }
463 
464  SourceLocation EndLoc;
465  if (!IsAngled) {
466  EndLoc = FilenameRange.getBegin();
467  } else {
468  EndLoc = FilenameRange.getEnd();
469  if (FilenameRange.isCharRange())
470  EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
471  // a token range.
472  }
474  = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
475  (bool)Imported,
476  File, SourceRange(HashLoc, EndLoc));
478 }
479 
481  return BumpAlloc.getTotalMemory()
482  + llvm::capacity_in_bytes(MacroDefinitions)
483  + llvm::capacity_in_bytes(PreprocessedEntities)
484  + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
485 }
SourceLocation getLocWithOffset(int Offset) const
Return a source location with the specified offset from this SourceLocation.
bool isLocalSourceLocation(SourceLocation Loc) const
Returns true if Loc did not come from a PCH/Module.
bool isBeforeInTranslationUnit(SourceLocation LHS, SourceLocation RHS) const
Determines the order of 2 source locations in the translation unit.
Defines the clang::MacroInfo and clang::MacroDirective classes.
A description of the current definition of a macro.
Definition: MacroInfo.h:545
Indicates a problem trying to load the preprocessed entity.
Base class that describes a preprocessed entity, which may be a preprocessor directive or macro expan...
SourceRange getSourceRange() const LLVM_READONLY
Retrieve the source range that covers this entire preprocessed entity.
float __ovld __cnfn distance(float p0, float p1)
Returns the distance between p0 and p1.
Records the presence of a preprocessor directive.
SourceLocation getBegin() const
Iteration over the preprocessed entities.
Record the location of a macro definition.
Token - This structure provides full information about a lexed token.
Definition: Token.h:35
Describes a module or submodule.
Definition: Module.h:57
bool isInvalid() const
llvm::iterator_range< iterator > getPreprocessedEntitiesInRange(SourceRange R)
Returns a range of preprocessed entities that source range R encompasses.
A record of the steps taken while preprocessing a source file, including the various preprocessing di...
virtual std::pair< unsigned, unsigned > findPreprocessedEntitiesInRange(SourceRange Range)=0
Returns a pair of [Begin, End) indices of preallocated preprocessed entities that Range encompasses...
Records the location of a macro expansion.
PreprocessingRecord(SourceManager &SM)
Construct a new preprocessing record.
A GNU #include_next directive.
bool isValid() const
std::pair< int, int > Result
virtual Optional< bool > isPreprocessedEntityInFileID(unsigned Index, FileID FID)
Optionally returns true or false if the preallocated preprocessed entity with index Index came from f...
bool isInFileID(SourceLocation Loc, FileID FID, unsigned *RelativeOffset=nullptr) const
Given a specific FileID, returns true if Loc is inside that FileID chunk and sets relative offset (of...
void * Allocate(unsigned Size, unsigned Align=8)
Allocate memory in the preprocessing record.
SourceLocation End
Represents a character-granular source range.
int Id
Definition: ASTDiff.cpp:191
static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID, SourceManager &SM)
MacroArgs - An instance of this class captures information about the formal arguments specified to a ...
Definition: MacroArgs.h:30
SourceLocation getLocation() const
Return a source location identifier for the specified offset in the current file. ...
Definition: Token.h:124
SourceLocation Begin
bool isInvalid() const
Record the location of an inclusion directive, such as an #include or #import statement.
InclusionKind
The kind of inclusion directives known to the preprocessor.
SourceLocation getEnd() const
InclusionDirective(PreprocessingRecord &PPRec, InclusionKind Kind, StringRef FileName, bool InQuotes, bool ImportedModule, const FileEntry *File, SourceRange Range)
const SourceManager & SM
Definition: Format.cpp:1308
Encapsulates changes to the "macros namespace" (the location where the macro name became active...
Definition: MacroInfo.h:286
Kind
Encodes a location in the source.
IdentifierInfo * getIdentifierInfo() const
Definition: Token.h:177
Cached information about one file (either on disk or in the virtual file system). ...
Definition: FileManager.h:59
An abstract class that should be subclassed by any external source of preprocessing record entries...
SourceLocation getFileLoc(SourceLocation Loc) const
Given Loc, if it is a macro location return the expansion location or the spelling location...
bool isEntityInFileID(iterator PPEI, FileID FID)
Returns true if the preprocessed entity that PPEI iterator points to is coming from the file FID...
A Clang #__include_macros directive.
const MacroInfo * getMacroInfo() const
Definition: MacroInfo.h:382
An opaque identifier used by SourceManager which refers to a source file (MemoryBuffer) along with it...
Dataflow Directional Tag Classes.
tok::PPKeywordKind getPPKeywordID() const
Return the preprocessor keyword ID for this identifier.
bool isMacroID() const
Encapsulates the data about a macro definition (e.g.
Definition: MacroInfo.h:34
PPEntityID addPreprocessedEntity(PreprocessedEntity *Entity)
Add a new preprocessed entity to this record.
An Objective-C #import directive.
SourceLocation getEnd() const
SourceLocation getDefinitionLoc() const
Return the location that the macro was defined at.
Definition: MacroInfo.h:117
SourceLocation getDefinitionEndLoc() const
Return the location of the last token in the macro.
Definition: MacroInfo.h:123
bool isValid() const
bool isBuiltinMacro() const
Return true if this macro requires processing before expansion.
Definition: MacroInfo.h:209
MacroDefinitionRecord * findMacroDefinition(const MacroInfo *MI)
Retrieve the macro definition that corresponds to the given MacroInfo.
void forAllDefinitions(Fn F) const
Definition: MacroInfo.h:581
MacroInfo * getMacroInfo() const
Get the MacroInfo that should be used for this definition.
Definition: MacroInfo.h:561
void SetExternalSource(ExternalPreprocessingRecordSource &Source)
Set the external source for preprocessed entities.
A trivial tuple used to represent a source range.
SourceLocation getBegin() const
This class handles loading and caching of source files into memory.