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 
20 using namespace clang;
21 
22 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }
23 
24 
25 InclusionDirective::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 
41 PreprocessingRecord::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.
48 std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
49 PreprocessingRecord::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 
66 static 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.
89 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
90   if (FID.isInvalid())
91     return false;
92 
93   int Pos = PPEI.Position;
94   if (Pos < 0) {
95     assert(unsigned(-Pos-1) < LoadedPreprocessedEntities.size() &&
96            "Out-of bounds loaded preprocessed entity");
97     assert(ExternalSource && "No external source to load from");
98     unsigned LoadedIndex = LoadedPreprocessedEntities.size()+Pos;
99     if (PreprocessedEntity *PPE = LoadedPreprocessedEntities[LoadedIndex])
100       return isPreprocessedEntityIfInFileID(PPE, FID, SourceMgr);
101 
102     // See if the external source can see if the entity is in the file without
103     // deserializing it.
104     llvm::Optional<bool>
105       IsInFile = ExternalSource->isPreprocessedEntityInFileID(LoadedIndex, FID);
106     if (IsInFile.hasValue())
107       return IsInFile.getValue();
108 
109     // The external source did not provide a definite answer, go and deserialize
110     // the entity to check it.
111     return isPreprocessedEntityIfInFileID(
112                                        getLoadedPreprocessedEntity(LoadedIndex),
113                                           FID, SourceMgr);
114   }
115 
116   assert(unsigned(Pos) < PreprocessedEntities.size() &&
117          "Out-of bounds local preprocessed entity");
118   return isPreprocessedEntityIfInFileID(PreprocessedEntities[Pos],
119                                         FID, SourceMgr);
120 }
121 
122 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
123 /// that source range \arg R encompasses.
124 std::pair<int, int>
125 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
126   assert(Range.isValid());
127   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
128 
129   std::pair<unsigned, unsigned>
130     Local = findLocalPreprocessedEntitiesInRange(Range);
131 
132   // Check if range spans local entities.
133   if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
134     return std::make_pair(Local.first, Local.second);
135 
136   std::pair<unsigned, unsigned>
137     Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
138 
139   // Check if range spans local entities.
140   if (Loaded.first == Loaded.second)
141     return std::make_pair(Local.first, Local.second);
142 
143   unsigned TotalLoaded = LoadedPreprocessedEntities.size();
144 
145   // Check if range spans loaded entities.
146   if (Local.first == Local.second)
147     return std::make_pair(int(Loaded.first)-TotalLoaded,
148                           int(Loaded.second)-TotalLoaded);
149 
150   // Range spands loaded and local entities.
151   return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
152 }
153 
154 std::pair<unsigned, unsigned>
155 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
156                                                       SourceRange Range) const {
157   if (Range.isInvalid())
158     return std::make_pair(0,0);
159   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
160 
161   unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
162   unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
163   return std::make_pair(Begin, End);
164 }
165 
166 namespace {
167 
168 template <SourceLocation (SourceRange::*getRangeLoc)() const>
169 struct PPEntityComp {
170   const SourceManager &SM;
171 
172   explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
173 
174   bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
175     SourceLocation LHS = getLoc(L);
176     SourceLocation RHS = getLoc(R);
177     return SM.isBeforeInTranslationUnit(LHS, RHS);
178   }
179 
180   bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
181     SourceLocation LHS = getLoc(L);
182     return SM.isBeforeInTranslationUnit(LHS, RHS);
183   }
184 
185   bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
186     SourceLocation RHS = getLoc(R);
187     return SM.isBeforeInTranslationUnit(LHS, RHS);
188   }
189 
190   SourceLocation getLoc(PreprocessedEntity *PPE) const {
191     SourceRange Range = PPE->getSourceRange();
192     return (Range.*getRangeLoc)();
193   }
194 };
195 
196 }
197 
198 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
199                                                      SourceLocation Loc) const {
200   if (SourceMgr.isLoadedSourceLocation(Loc))
201     return 0;
202 
203   size_t Count = PreprocessedEntities.size();
204   size_t Half;
205   std::vector<PreprocessedEntity *>::const_iterator
206     First = PreprocessedEntities.begin();
207   std::vector<PreprocessedEntity *>::const_iterator I;
208 
209   // Do a binary search manually instead of using std::lower_bound because
210   // The end locations of entities may be unordered (when a macro expansion
211   // is inside another macro argument), but for this case it is not important
212   // whether we get the first macro expansion or its containing macro.
213   while (Count > 0) {
214     Half = Count/2;
215     I = First;
216     std::advance(I, Half);
217     if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
218                                             Loc)){
219       First = I;
220       ++First;
221       Count = Count - Half - 1;
222     } else
223       Count = Half;
224   }
225 
226   return First - PreprocessedEntities.begin();
227 }
228 
229 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
230                                                      SourceLocation Loc) const {
231   if (SourceMgr.isLoadedSourceLocation(Loc))
232     return 0;
233 
234   std::vector<PreprocessedEntity *>::const_iterator
235   I = std::upper_bound(PreprocessedEntities.begin(),
236                        PreprocessedEntities.end(),
237                        Loc,
238                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));
239   return I - PreprocessedEntities.begin();
240 }
241 
242 PreprocessingRecord::PPEntityID
243 PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
244   assert(Entity);
245   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
246 
247   if (!isa<class InclusionDirective>(Entity)) {
248     assert((PreprocessedEntities.empty() ||
249             !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
250                    PreprocessedEntities.back()->getSourceRange().getBegin())) &&
251            "a macro directive was encountered out-of-order");
252     PreprocessedEntities.push_back(Entity);
253     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
254   }
255 
256   // Check normal case, this entity begin location is after the previous one.
257   if (PreprocessedEntities.empty() ||
258       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
259                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
260     PreprocessedEntities.push_back(Entity);
261     return getPPEntityID(PreprocessedEntities.size()-1, /*isLoaded=*/false);
262   }
263 
264   // The entity's location is not after the previous one; this can happen with
265   // include directives that form the filename using macros, e.g:
266   // "#include MACRO(STUFF)".
267 
268   typedef std::vector<PreprocessedEntity *>::iterator pp_iter;
269 
270   // Usually there are few macro expansions when defining the filename, do a
271   // linear search for a few entities.
272   unsigned count = 0;
273   for (pp_iter RI    = PreprocessedEntities.end(),
274                Begin = PreprocessedEntities.begin();
275        RI != Begin && count < 4; --RI, ++count) {
276     pp_iter I = RI;
277     --I;
278     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
279                                            (*I)->getSourceRange().getBegin())) {
280       pp_iter insertI = PreprocessedEntities.insert(RI, Entity);
281       return getPPEntityID(insertI - PreprocessedEntities.begin(),
282                            /*isLoaded=*/false);
283     }
284   }
285 
286   // Linear search unsuccessful. Do a binary search.
287   pp_iter I = std::upper_bound(PreprocessedEntities.begin(),
288                                PreprocessedEntities.end(),
289                                BeginLoc,
290                                PPEntityComp<&SourceRange::getBegin>(SourceMgr));
291   pp_iter insertI = PreprocessedEntities.insert(I, Entity);
292   return getPPEntityID(insertI - PreprocessedEntities.begin(),
293                        /*isLoaded=*/false);
294 }
295 
296 void PreprocessingRecord::SetExternalSource(
297                                     ExternalPreprocessingRecordSource &Source) {
298   assert(!ExternalSource &&
299          "Preprocessing record already has an external source");
300   ExternalSource = &Source;
301 }
302 
303 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
304   unsigned Result = LoadedPreprocessedEntities.size();
305   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
306                                     + NumEntities);
307   return Result;
308 }
309 
310 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
311                                                   PPEntityID PPID) {
312   MacroDefinitions[Macro] = PPID;
313 }
314 
315 /// \brief Retrieve the preprocessed entity at the given ID.
316 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
317   if (PPID.ID < 0) {
318     unsigned Index = -PPID.ID - 1;
319     assert(Index < LoadedPreprocessedEntities.size() &&
320            "Out-of bounds loaded preprocessed entity");
321     return getLoadedPreprocessedEntity(Index);
322   }
323 
324   if (PPID.ID == 0)
325     return 0;
326   unsigned Index = PPID.ID - 1;
327   assert(Index < PreprocessedEntities.size() &&
328          "Out-of bounds local preprocessed entity");
329   return PreprocessedEntities[Index];
330 }
331 
332 /// \brief Retrieve the loaded preprocessed entity at the given index.
333 PreprocessedEntity *
334 PreprocessingRecord::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 
348 MacroDefinition *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 
360 void PreprocessingRecord::addMacroExpansion(const Token &Id,
361                                             const MacroInfo *MI,
362                                             SourceRange Range) {
363   // We don't record nested macro expansions.
364   if (Id.getLocation().isMacroID())
365     return;
366 
367   if (MI->isBuiltinMacro())
368     addPreprocessedEntity(
369                       new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
370   else if (MacroDefinition *Def = findMacroDefinition(MI))
371     addPreprocessedEntity(
372                        new (*this) MacroExpansion(Def, Range));
373 }
374 
375 void PreprocessingRecord::Ifdef(SourceLocation Loc, const Token &MacroNameTok,
376                                 const MacroInfo *MI) {
377   // This is not actually a macro expansion but record it as a macro reference.
378   if (MI)
379     addMacroExpansion(MacroNameTok, MI, MacroNameTok.getLocation());
380 }
381 
382 void PreprocessingRecord::Ifndef(SourceLocation Loc, const Token &MacroNameTok,
383                                  const MacroInfo *MI) {
384   // This is not actually a macro expansion but record it as a macro reference.
385   if (MI)
386     addMacroExpansion(MacroNameTok, MI, MacroNameTok.getLocation());
387 }
388 
389 void PreprocessingRecord::Defined(const Token &MacroNameTok,
390                                   const MacroInfo *MI) {
391   // This is not actually a macro expansion but record it as a macro reference.
392   if (MI)
393     addMacroExpansion(MacroNameTok, MI, MacroNameTok.getLocation());
394 }
395 
396 void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
397                                        SourceRange Range) {
398   addMacroExpansion(Id, MI, Range);
399 }
400 
401 void PreprocessingRecord::MacroDefined(const Token &Id,
402                                        const MacroInfo *MI) {
403   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
404   MacroDefinition *Def
405       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
406   MacroDefinitions[MI] = addPreprocessedEntity(Def);
407 }
408 
409 void PreprocessingRecord::MacroUndefined(const Token &Id,
410                                          const MacroInfo *MI) {
411   MacroDefinitions.erase(MI);
412 }
413 
414 void PreprocessingRecord::InclusionDirective(
415     SourceLocation HashLoc,
416     const clang::Token &IncludeTok,
417     StringRef FileName,
418     bool IsAngled,
419     CharSourceRange FilenameRange,
420     const FileEntry *File,
421     StringRef SearchPath,
422     StringRef RelativePath,
423     const Module *Imported) {
424   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
425 
426   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
427   case tok::pp_include:
428     Kind = InclusionDirective::Include;
429     break;
430 
431   case tok::pp_import:
432     Kind = InclusionDirective::Import;
433     break;
434 
435   case tok::pp_include_next:
436     Kind = InclusionDirective::IncludeNext;
437     break;
438 
439   case tok::pp___include_macros:
440     Kind = InclusionDirective::IncludeMacros;
441     break;
442 
443   default:
444     llvm_unreachable("Unknown include directive kind");
445   }
446 
447   SourceLocation EndLoc;
448   if (!IsAngled) {
449     EndLoc = FilenameRange.getBegin();
450   } else {
451     EndLoc = FilenameRange.getEnd();
452     if (FilenameRange.isCharRange())
453       EndLoc = EndLoc.getLocWithOffset(-1); // the InclusionDirective expects
454                                             // a token range.
455   }
456   clang::InclusionDirective *ID
457     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
458                                             (bool)Imported,
459                                             File, SourceRange(HashLoc, EndLoc));
460   addPreprocessedEntity(ID);
461 }
462 
463 size_t PreprocessingRecord::getTotalMemory() const {
464   return BumpAlloc.getTotalMemory()
465     + llvm::capacity_in_bytes(MacroDefinitions)
466     + llvm::capacity_in_bytes(PreprocessedEntities)
467     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
468 }
469