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   assert((PreprocessedEntities.empty() ||
174        !SourceMgr.isBeforeInTranslationUnit(Entity->getSourceRange().getBegin(),
175                    PreprocessedEntities.back()->getSourceRange().getBegin())) &&
176          "Adding a preprocessed entity that is before the previous one in TU");
177   PreprocessedEntities.push_back(Entity);
178 }
179 
180 void PreprocessingRecord::SetExternalSource(
181                                     ExternalPreprocessingRecordSource &Source) {
182   assert(!ExternalSource &&
183          "Preprocessing record already has an external source");
184   ExternalSource = &Source;
185 }
186 
187 unsigned PreprocessingRecord::allocateLoadedEntities(unsigned NumEntities) {
188   unsigned Result = LoadedPreprocessedEntities.size();
189   LoadedPreprocessedEntities.resize(LoadedPreprocessedEntities.size()
190                                     + NumEntities);
191   return Result;
192 }
193 
194 void PreprocessingRecord::RegisterMacroDefinition(MacroInfo *Macro,
195                                                   PPEntityID PPID) {
196   MacroDefinitions[Macro] = PPID;
197 }
198 
199 /// \brief Retrieve the preprocessed entity at the given ID.
200 PreprocessedEntity *PreprocessingRecord::getPreprocessedEntity(PPEntityID PPID){
201   if (PPID < 0) {
202     assert(unsigned(-PPID-1) < LoadedPreprocessedEntities.size() &&
203            "Out-of bounds loaded preprocessed entity");
204     return getLoadedPreprocessedEntity(LoadedPreprocessedEntities.size()+PPID);
205   }
206   assert(unsigned(PPID) < PreprocessedEntities.size() &&
207          "Out-of bounds local preprocessed entity");
208   return PreprocessedEntities[PPID];
209 }
210 
211 /// \brief Retrieve the loaded preprocessed entity at the given index.
212 PreprocessedEntity *
213 PreprocessingRecord::getLoadedPreprocessedEntity(unsigned Index) {
214   assert(Index < LoadedPreprocessedEntities.size() &&
215          "Out-of bounds loaded preprocessed entity");
216   assert(ExternalSource && "No external source to load from");
217   PreprocessedEntity *&Entity = LoadedPreprocessedEntities[Index];
218   if (!Entity) {
219     Entity = ExternalSource->ReadPreprocessedEntity(Index);
220     if (!Entity) // Failed to load.
221       Entity = new (*this)
222          PreprocessedEntity(PreprocessedEntity::InvalidKind, SourceRange());
223   }
224   return Entity;
225 }
226 
227 MacroDefinition *PreprocessingRecord::findMacroDefinition(const MacroInfo *MI) {
228   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
229     = MacroDefinitions.find(MI);
230   if (Pos == MacroDefinitions.end())
231     return 0;
232 
233   PreprocessedEntity *Entity = getPreprocessedEntity(Pos->second);
234   if (Entity->isInvalid())
235     return 0;
236   return cast<MacroDefinition>(Entity);
237 }
238 
239 void PreprocessingRecord::MacroExpands(const Token &Id, const MacroInfo* MI,
240                                        SourceRange Range) {
241   if (!IncludeNestedMacroExpansions && Id.getLocation().isMacroID())
242     return;
243 
244   if (MI->isBuiltinMacro())
245     addPreprocessedEntity(
246                       new (*this) MacroExpansion(Id.getIdentifierInfo(),Range));
247   else if (MacroDefinition *Def = findMacroDefinition(MI))
248     addPreprocessedEntity(
249                        new (*this) MacroExpansion(Def, Range));
250 }
251 
252 void PreprocessingRecord::MacroDefined(const Token &Id,
253                                        const MacroInfo *MI) {
254   SourceRange R(MI->getDefinitionLoc(), MI->getDefinitionEndLoc());
255   MacroDefinition *Def
256       = new (*this) MacroDefinition(Id.getIdentifierInfo(), R);
257   addPreprocessedEntity(Def);
258   MacroDefinitions[MI] = getPPEntityID(PreprocessedEntities.size()-1,
259                                        /*isLoaded=*/false);
260 }
261 
262 void PreprocessingRecord::MacroUndefined(const Token &Id,
263                                          const MacroInfo *MI) {
264   llvm::DenseMap<const MacroInfo *, PPEntityID>::iterator Pos
265     = MacroDefinitions.find(MI);
266   if (Pos != MacroDefinitions.end())
267     MacroDefinitions.erase(Pos);
268 }
269 
270 void PreprocessingRecord::InclusionDirective(
271     SourceLocation HashLoc,
272     const clang::Token &IncludeTok,
273     StringRef FileName,
274     bool IsAngled,
275     const FileEntry *File,
276     clang::SourceLocation EndLoc,
277     StringRef SearchPath,
278     StringRef RelativePath) {
279   InclusionDirective::InclusionKind Kind = InclusionDirective::Include;
280 
281   switch (IncludeTok.getIdentifierInfo()->getPPKeywordID()) {
282   case tok::pp_include:
283     Kind = InclusionDirective::Include;
284     break;
285 
286   case tok::pp_import:
287     Kind = InclusionDirective::Import;
288     break;
289 
290   case tok::pp_include_next:
291     Kind = InclusionDirective::IncludeNext;
292     break;
293 
294   case tok::pp___include_macros:
295     Kind = InclusionDirective::IncludeMacros;
296     break;
297 
298   default:
299     llvm_unreachable("Unknown include directive kind");
300     return;
301   }
302 
303   clang::InclusionDirective *ID
304     = new (*this) clang::InclusionDirective(*this, Kind, FileName, !IsAngled,
305                                             File, SourceRange(HashLoc, EndLoc));
306   addPreprocessedEntity(ID);
307 }
308 
309 size_t PreprocessingRecord::getTotalMemory() const {
310   return BumpAlloc.getTotalMemory()
311     + llvm::capacity_in_bytes(MacroDefinitions)
312     + llvm::capacity_in_bytes(PreprocessedEntities)
313     + llvm::capacity_in_bytes(LoadedPreprocessedEntities);
314 }
315