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(this, 0), iterator(this, 0));
53   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
54 
55   std::pair<unsigned, unsigned>
56     Local = findLocalPreprocessedEntitiesInRange(Range);
57 
58   // Check if range spans local entities.
59   if (!ExternalSource || SourceMgr.isLocalSourceLocation(Range.getBegin()))
60     return std::make_pair(iterator(this, Local.first),
61                           iterator(this, Local.second));
62 
63   std::pair<unsigned, unsigned>
64     Loaded = ExternalSource->findPreprocessedEntitiesInRange(Range);
65 
66   // Check if range spans local entities.
67   if (Loaded.first == Loaded.second)
68     return std::make_pair(iterator(this, Local.first),
69                           iterator(this, Local.second));
70 
71   unsigned TotalLoaded = LoadedPreprocessedEntities.size();
72 
73   // Check if range spans loaded entities.
74   if (Local.first == Local.second)
75     return std::make_pair(iterator(this, int(Loaded.first)-TotalLoaded),
76                           iterator(this, int(Loaded.second)-TotalLoaded));
77 
78   // Range spands loaded and local entities.
79   return std::make_pair(iterator(this, int(Loaded.first)-TotalLoaded),
80                         iterator(this, Local.second));
81 }
82 
83 std::pair<unsigned, unsigned>
84 PreprocessingRecord::findLocalPreprocessedEntitiesInRange(
85                                                       SourceRange Range) const {
86   if (Range.isInvalid())
87     return std::make_pair(0,0);
88   assert(!SourceMgr.isBeforeInTranslationUnit(Range.getEnd(),Range.getBegin()));
89 
90   unsigned Begin = findBeginLocalPreprocessedEntity(Range.getBegin());
91   unsigned End = findEndLocalPreprocessedEntity(Range.getEnd());
92   return std::make_pair(Begin, End);
93 }
94 
95 namespace {
96 
97 template <SourceLocation (SourceRange::*getRangeLoc)() const>
98 struct PPEntityComp {
99   const SourceManager &SM;
100 
101   explicit PPEntityComp(const SourceManager &SM) : SM(SM) { }
102 
103   bool operator()(PreprocessedEntity *L, PreprocessedEntity *R) const {
104     SourceLocation LHS = getLoc(L);
105     SourceLocation RHS = getLoc(R);
106     return SM.isBeforeInTranslationUnit(LHS, RHS);
107   }
108 
109   bool operator()(PreprocessedEntity *L, SourceLocation RHS) const {
110     SourceLocation LHS = getLoc(L);
111     return SM.isBeforeInTranslationUnit(LHS, RHS);
112   }
113 
114   bool operator()(SourceLocation LHS, PreprocessedEntity *R) const {
115     SourceLocation RHS = getLoc(R);
116     return SM.isBeforeInTranslationUnit(LHS, RHS);
117   }
118 
119   SourceLocation getLoc(PreprocessedEntity *PPE) const {
120     SourceRange Range = PPE->getSourceRange();
121     return (Range.*getRangeLoc)();
122   }
123 };
124 
125 }
126 
127 unsigned PreprocessingRecord::findBeginLocalPreprocessedEntity(
128                                                      SourceLocation Loc) const {
129   if (SourceMgr.isLoadedSourceLocation(Loc))
130     return 0;
131 
132   size_t Count = PreprocessedEntities.size();
133   size_t Half;
134   std::vector<PreprocessedEntity *>::const_iterator
135     First = PreprocessedEntities.begin();
136   std::vector<PreprocessedEntity *>::const_iterator I;
137 
138   // Do a binary search manually instead of using std::lower_bound because
139   // The end locations of entities may be unordered (when a macro expansion
140   // is inside another macro argument), but for this case it is not important
141   // whether we get the first macro expansion or its containing macro.
142   while (Count > 0) {
143     Half = Count/2;
144     I = First;
145     std::advance(I, Half);
146     if (SourceMgr.isBeforeInTranslationUnit((*I)->getSourceRange().getEnd(),
147                                             Loc)){
148       First = I;
149       ++First;
150       Count = Count - Half - 1;
151     } else
152       Count = Half;
153   }
154 
155   return First - PreprocessedEntities.begin();
156 }
157 
158 unsigned PreprocessingRecord::findEndLocalPreprocessedEntity(
159                                                      SourceLocation Loc) const {
160   if (SourceMgr.isLoadedSourceLocation(Loc))
161     return 0;
162 
163   std::vector<PreprocessedEntity *>::const_iterator
164   I = std::upper_bound(PreprocessedEntities.begin(),
165                        PreprocessedEntities.end(),
166                        Loc,
167                        PPEntityComp<&SourceRange::getBegin>(SourceMgr));
168   return I - PreprocessedEntities.begin();
169 }
170 
171 void PreprocessingRecord::addPreprocessedEntity(PreprocessedEntity *Entity) {
172   assert(Entity);
173   SourceLocation BeginLoc = Entity->getSourceRange().getBegin();
174 
175   // Check normal case, this entity begin location is after the previous one.
176   if (PreprocessedEntities.empty() ||
177       !SourceMgr.isBeforeInTranslationUnit(BeginLoc,
178                    PreprocessedEntities.back()->getSourceRange().getBegin())) {
179     PreprocessedEntities.push_back(Entity);
180     return;
181   }
182 
183   // The entity's location is not after the previous one; this can happen rarely
184   // e.g. with "#include MACRO".
185   // Iterate the entities vector in reverse until we find the right place to
186   // insert the new entity.
187   for (std::vector<PreprocessedEntity *>::iterator
188          RI = PreprocessedEntities.end(), Begin = PreprocessedEntities.begin();
189        RI != Begin; --RI) {
190     std::vector<PreprocessedEntity *>::iterator I = RI;
191     --I;
192     if (!SourceMgr.isBeforeInTranslationUnit(BeginLoc,
193                                            (*I)->getSourceRange().getBegin())) {
194       PreprocessedEntities.insert(RI, Entity);
195       return;
196     }
197   }
198 }
199 
200 void PreprocessingRecord::SetExternalSource(
201                                     ExternalPreprocessingRecordSource &Source) {
202   assert(!ExternalSource &&
203          "Preprocessing record already has an external source");
204   ExternalSource = &Source;
205 }
206 
207 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
208   unsigned Result = LoadedPreprocessedEntities.size();
209   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
210                                     + NumEntities);
211   return Result;
212 }
213 
214 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
215                                                   PPEntityID PPID) {
216   MacroDefinitions[Macro] = PPID;
217 }
218 
219 /// \brief Retrieve the preprocessed entity at the given ID.
220 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
221   if (PPID < 0) {
222     assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
223            "Out-of bounds loaded preprocessed entity");
224     return getLoadedPreprocessedEntity(LoadedPreprocessedEntities.size()+PPID);
225   }
226   assert(unsigned(PPID) < PreprocessedEntities.size() &&
227          "Out-of bounds local preprocessed entity");
228   return PreprocessedEntities[PPID];
229 }
230 
231 /// \brief Retrieve the loaded preprocessed entity at the given index.
232 PreprocessedEntity *
233 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
234   assert(Index < LoadedPreprocessedEntities.size() &&
235          "Out-of bounds loaded preprocessed entity");
236   assert(ExternalSource && "No external source to load from");
237   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
238   if (!Entity) {
239     Entity = ExternalSource->ReadPreprocessedEntity(Index);
240     if (!Entity) // Failed to load.
241       Entity = new (*this)
242          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
243   }
244   return Entity;
245 }
246 
247 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
248   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
249     = MacroDefinitions.find(MI);
250   if (Pos == MacroDefinitions.end())
251     return 0;
252 
253   PreprocessedEntity *Entity = getPreprocessedEntity(Pos->second);
254   if (Entity->isInvalid())
255     return 0;
256   return cast<MacroDefinition>(Entity);
257 }
258 
259 void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
260                                        SourceRange Range) {
261   if (!IncludeNestedMacroExpansions && Id.getLocation().isMacroID())
262     return;
263 
264   if (MI->isBuiltinMacro())
265     addPreprocessedEntity(
266                       new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
267   else if (MacroDefinition *Def = findMacroDefinition(MI))
268     addPreprocessedEntity(
269                        new (*this) MacroExpansion(Def, Range));
270 }
271 
272 void PreprocessingRecord::MacroDefined(const Token &Id,
273                                        const MacroInfo *MI) {
274   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
275   MacroDefinition *Def
276       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
277   addPreprocessedEntity(Def);
278   MacroDefinitions[MI] = getPPEntityID(PreprocessedEntities.size()-1,
279                                        /*isLoaded=*/false);
280 }
281 
282 void PreprocessingRecord::MacroUndefined(const Token &Id,
283                                          const MacroInfo *MI) {
284   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
285     = MacroDefinitions.find(MI);
286   if (Pos != MacroDefinitions.end())
287     MacroDefinitions.erase(Pos);
288 }
289 
290 void PreprocessingRecord::InclusionDirective(
291     SourceLocation HashLoc,
292     const clang::Token &IncludeTok,
293     StringRef FileName,
294     bool IsAngled,
295     const FileEntry *File,
296     clang::SourceLocation EndLoc,
297     StringRef SearchPath,
298     StringRef RelativePath) {
299   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
300 
301   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
302   case tok::pp_include:
303     Kind = InclusionDirective::Include;
304     break;
305 
306   case tok::pp_import:
307     Kind = InclusionDirective::Import;
308     break;
309 
310   case tok::pp_include_next:
311     Kind = InclusionDirective::IncludeNext;
312     break;
313 
314   case tok::pp___include_macros:
315     Kind = InclusionDirective::IncludeMacros;
316     break;
317 
318   default:
319     llvm_unreachable("Unknown include directive kind");
320     return;
321   }
322 
323   clang::InclusionDirective *ID
324     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
325                                             File, SourceRange(HashLoc, EndLoc));
326   addPreprocessedEntity(ID);
327 }
328 
329 size_t PreprocessingRecord::getTotalMemory() const {
330   return BumpAlloc.getTotalMemory()
331     + llvm::capacity_in_bytes(MacroDefinitions)
332     + llvm::capacity_in_bytes(PreprocessedEntities)
333     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
334 }
335