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