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

source code of clang/lib/Lex/PreprocessingRecord.cpp