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