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 
20 using namespace clang;
21 
22 ExternalPreprocessingRecordSource::~ExternalPreprocessingRecordSource() { }
23 
24 
25 InclusionDirective::InclusionDirective(PreprocessingRecord &PPRec,
26                                        InclusionKind Kind,
27                                        StringRef FileName,
28                                        bool InQuotes, const FileEntry *File,
29                                        SourceRange Range)
30   : PreprocessingDirective(InclusionDirectiveKind, Range),
31     InQuotes(InQuotes), Kind(Kind), File(File)
32 {
33   char *Memory
34     = (char*)PPRec.Allocate(FileName.size() + 1, llvm::alignOf<char>());
35   memcpy(Memory, FileName.data(), FileName.size());
36   Memory[FileName.size()] = 0;
37   this->FileName = StringRef(Memory, FileName.size());
38 }
39 
40 PreprocessingRecord::PreprocessingRecord(SourceManager &SM,
41                                          bool IncludeNestedMacroExpansions)
42   : SourceMgr(SM), IncludeNestedMacroExpansions(IncludeNestedMacroExpansions),
43     ExternalSource(0)
44 {
45 }
46 
47 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
48 /// that source range \arg R encompasses.
49 std::pair<PreprocessingRecord::iterator, PreprocessingRecord::iterator>
50 PreprocessingRecord::getPreprocessedEntitiesInRange(SourceRange Range) {
51   if (Range.isInvalid())
52     return std::make_pair(iterator(), iterator());
53 
54   if (CachedRangeQuery.Range == Range) {
55     return std::make_pair(iterator(this, CachedRangeQuery.Result.first),
56                           iterator(this, CachedRangeQuery.Result.second));
57   }
58 
59   std::pair<PPEntityID, PPEntityID>
60     Res = getPreprocessedEntitiesInRangeSlow(Range);
61 
62   CachedRangeQuery.Range = Range;
63   CachedRangeQuery.Result = Res;
64 
65   return std::make_pair(iterator(this, Res.first), iterator(this, Res.second));
66 }
67 
68 static bool isPreprocessedEntityIfInFileID(PreprocessedEntity *PPE, FileID FID,
69                                            SourceManager &SM) {
70   assert(!FID.isInvalid());
71   if (!PPE)
72     return false;
73 
74   SourceLocation Loc = PPE->getSourceRange().getBegin();
75   if (Loc.isInvalid())
76     return false;
77 
78   if (SM.isInFileID(SM.getFileLoc(Loc), FID))
79     return true;
80   else
81     return false;
82 }
83 
84 /// \brief Returns true if the preprocessed entity that \arg PPEI iterator
85 /// points to is coming from the file \arg FID.
86 ///
87 /// Can be used to avoid implicit deserializations of preallocated
88 /// preprocessed entities if we only care about entities of a specific file
89 /// and not from files #included in the range given at
90 /// \see getPreprocessedEntitiesInRange.
91 bool PreprocessingRecord::isEntityInFileID(iterator PPEI, FileID FID) {
92   if (FID.isInvalid())
93     return false;
94 
95   PPEntityID PPID = PPEI.Position;
96   if (PPID < 0) {
97     assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
98            "Out-of bounds loaded preprocessed entity");
99     assert(ExternalSource && "No external source to load from");
100     unsigned LoadedIndex = LoadedPreprocessedEntities.size()+PPID;
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     llvm::Optional<bool>
107       IsInFile = 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   assert(unsigned(PPID) < PreprocessedEntities.size() &&
119          "Out-of bounds local preprocessed entity");
120   return isPreprocessedEntityIfInFileID(PreprocessedEntities[PPID],
121                                         FID, SourceMgr);
122 }
123 
124 /// \brief Returns a pair of [Begin, End) iterators of preprocessed entities
125 /// that source range \arg R encompasses.
126 std::pair<PreprocessingRecord::PPEntityID, PreprocessingRecord::PPEntityID>
127 PreprocessingRecord::getPreprocessedEntitiesInRangeSlow(SourceRange Range) {
128   assert(Range.isValid());
129   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
130 
131   std::pair<unsigned, unsigned>
132     Local = findLocalPreprocessedEntitiesInRange(Range);
133 
134   // Check if range spans local entities.
135   if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
136     return std::make_pair(Local.first, Local.second);
137 
138   std::pair<unsigned, unsigned>
139     Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
140 
141   // Check if range spans local entities.
142   if (Loaded.first == Loaded.second)
143     return std::make_pair(Local.first, Local.second);
144 
145   unsigned TotalLoaded = LoadedPreprocessedEntities.size();
146 
147   // Check if range spans loaded entities.
148   if (Local.first == Local.second)
149     return std::make_pair(int(Loaded.first)-TotalLoaded,
150                           int(Loaded.second)-TotalLoaded);
151 
152   // Range spands loaded and local entities.
153   return std::make_pair(int(Loaded.first)-TotalLoaded, Local.second);
154 }
155 
156 std::pair<unsigned, unsigned>
157 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
158                                                       SourceRange Range) const {
159   if (Range.isInvalid())
160     return std::make_pair(0,0);
161   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
162 
163   unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
164   unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
165   return std::make_pair(Begin, End);
166 }
167 
168 namespace {
169 
170 template <SourceLocation (SourceRange::*getRangeLoc)() const>
171 struct PPEntityComp {
172   const SourceManager &SM;
173 
174   explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
175 
176   bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
177     SourceLocation LHS = getLoc(L);
178     SourceLocation RHS = getLoc(R);
179     return SM.isBeforeInTranslationUnit(LHS, RHS);
180   }
181 
182   bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
183     SourceLocation LHS = getLoc(L);
184     return SM.isBeforeInTranslationUnit(LHS, RHS);
185   }
186 
187   bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
188     SourceLocation RHS = getLoc(R);
189     return SM.isBeforeInTranslationUnit(LHS, RHS);
190   }
191 
192   SourceLocation getLoc(PreprocessedEntity *PPE) const {
193     SourceRange Range = PPE->getSourceRange();
194     return (Range.*getRangeLoc)();
195   }
196 };
197 
198 }
199 
200 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
201                                                      SourceLocation Loc) const {
202   if (SourceMgr.isLoadedSourceLocation(Loc))
203     return 0;
204 
205   size_t Count = PreprocessedEntities.size();
206   size_t Half;
207   std::vector<PreprocessedEntity *>::const_iterator
208     First = PreprocessedEntities.begin();
209   std::vector<PreprocessedEntity *>::const_iterator I;
210 
211   // Do a binary search manually instead of using std::lower_bound because
212   // The end locations of entities may be unordered (when a macro expansion
213   // is inside another macro argument), but for this case it is not important
214   // whether we get the first macro expansion or its containing macro.
215   while (Count > 0) {
216     Half = Count/2;
217     I = First;
218     std::advance(I, Half);
219     if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
220                                             Loc)){
221       First = I;
222       ++First;
223       Count = Count - Half - 1;
224     } else
225       Count = Half;
226   }
227 
228   return First - PreprocessedEntities.begin();
229 }
230 
231 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
232                                                      SourceLocation Loc) const {
233   if (SourceMgr.isLoadedSourceLocation(Loc))
234     return 0;
235 
236   std::vector<PreprocessedEntity *>::const_iterator
237   I = std::upper_bound(PreprocessedEntities.begin(),
238                        PreprocessedEntities.end(),
239                        Loc,
240                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));
241   return I - PreprocessedEntities.begin();
242 }
243 
244 void PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
245   assert(Entity);
246   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
247 
248   // Check normal case, this entity begin location is after the previous one.
249   if (PreprocessedEntities.empty() ||
250       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
251                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
252     PreprocessedEntities.push_back(Entity);
253     return;
254   }
255 
256   // The entity's location is not after the previous one; this can happen rarely
257   // e.g. with "#include MACRO".
258   // Iterate the entities vector in reverse until we find the right place to
259   // insert the new entity.
260   for (std::vector<PreprocessedEntity *>::iterator
261          RI = PreprocessedEntities.end(), Begin = PreprocessedEntities.begin();
262        RI != Begin; --RI) {
263     std::vector<PreprocessedEntity *>::iterator I = RI;
264     --I;
265     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
266                                            (*I)->getSourceRange().getBegin())) {
267       PreprocessedEntities.insert(RI, Entity);
268       return;
269     }
270   }
271 }
272 
273 void PreprocessingRecord::SetExternalSource(
274                                     ExternalPreprocessingRecordSource &Source) {
275   assert(!ExternalSource &&
276          "Preprocessing record already has an external source");
277   ExternalSource = &Source;
278 }
279 
280 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
281   unsigned Result = LoadedPreprocessedEntities.size();
282   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
283                                     + NumEntities);
284   return Result;
285 }
286 
287 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
288                                                   PPEntityID PPID) {
289   MacroDefinitions[Macro] = PPID;
290 }
291 
292 /// \brief Retrieve the preprocessed entity at the given ID.
293 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
294   if (PPID < 0) {
295     assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
296            "Out-of bounds loaded preprocessed entity");
297     return getLoadedPreprocessedEntity(LoadedPreprocessedEntities.size()+PPID);
298   }
299   assert(unsigned(PPID) < PreprocessedEntities.size() &&
300          "Out-of bounds local preprocessed entity");
301   return PreprocessedEntities[PPID];
302 }
303 
304 /// \brief Retrieve the loaded preprocessed entity at the given index.
305 PreprocessedEntity *
306 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
307   assert(Index < LoadedPreprocessedEntities.size() &&
308          "Out-of bounds loaded preprocessed entity");
309   assert(ExternalSource && "No external source to load from");
310   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
311   if (!Entity) {
312     Entity = ExternalSource->ReadPreprocessedEntity(Index);
313     if (!Entity) // Failed to load.
314       Entity = new (*this)
315          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
316   }
317   return Entity;
318 }
319 
320 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
321   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
322     = MacroDefinitions.find(MI);
323   if (Pos == MacroDefinitions.end())
324     return 0;
325 
326   PreprocessedEntity *Entity = getPreprocessedEntity(Pos->second);
327   if (Entity->isInvalid())
328     return 0;
329   return cast<MacroDefinition>(Entity);
330 }
331 
332 void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
333                                        SourceRange Range) {
334   if (!IncludeNestedMacroExpansions && Id.getLocation().isMacroID())
335     return;
336 
337   if (MI->isBuiltinMacro())
338     addPreprocessedEntity(
339                       new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
340   else if (MacroDefinition *Def = findMacroDefinition(MI))
341     addPreprocessedEntity(
342                        new (*this) MacroExpansion(Def, Range));
343 }
344 
345 void PreprocessingRecord::MacroDefined(const Token &Id,
346                                        const MacroInfo *MI) {
347   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
348   MacroDefinition *Def
349       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
350   addPreprocessedEntity(Def);
351   MacroDefinitions[MI] = getPPEntityID(PreprocessedEntities.size()-1,
352                                        /*isLoaded=*/false);
353 }
354 
355 void PreprocessingRecord::MacroUndefined(const Token &Id,
356                                          const MacroInfo *MI) {
357   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
358     = MacroDefinitions.find(MI);
359   if (Pos != MacroDefinitions.end())
360     MacroDefinitions.erase(Pos);
361 }
362 
363 void PreprocessingRecord::InclusionDirective(
364     SourceLocation HashLoc,
365     const clang::Token &IncludeTok,
366     StringRef FileName,
367     bool IsAngled,
368     const FileEntry *File,
369     clang::SourceLocation EndLoc,
370     StringRef SearchPath,
371     StringRef RelativePath) {
372   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
373 
374   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
375   case tok::pp_include:
376     Kind = InclusionDirective::Include;
377     break;
378 
379   case tok::pp_import:
380     Kind = InclusionDirective::Import;
381     break;
382 
383   case tok::pp_include_next:
384     Kind = InclusionDirective::IncludeNext;
385     break;
386 
387   case tok::pp___include_macros:
388     Kind = InclusionDirective::IncludeMacros;
389     break;
390 
391   default:
392     llvm_unreachable("Unknown include directive kind");
393     return;
394   }
395 
396   clang::InclusionDirective *ID
397     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
398                                             File, SourceRange(HashLoc, EndLoc));
399   addPreprocessedEntity(ID);
400 }
401 
402 size_t PreprocessingRecord::getTotalMemory() const {
403   return BumpAlloc.getTotalMemory()
404     + llvm::capacity_in_bytes(MacroDefinitions)
405     + llvm::capacity_in_bytes(PreprocessedEntities)
406     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
407 }
408