1 //===- PreprocessingRecord.h - Record of Preprocessing ----------*- C++ -*-===//
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 defines the PreprocessingRecord class, which maintains a record
10 // of what occurred during preprocessing.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #ifndef LLVM_CLANG_LEX_PREPROCESSINGRECORD_H
15 #define LLVM_CLANG_LEX_PREPROCESSINGRECORD_H
16
17 #include "clang/Basic/IdentifierTable.h"
18 #include "clang/Basic/LLVM.h"
19 #include "clang/Basic/SourceLocation.h"
20 #include "clang/Lex/PPCallbacks.h"
21 #include "llvm/ADT/DenseMap.h"
22 #include "llvm/ADT/None.h"
23 #include "llvm/ADT/Optional.h"
24 #include "llvm/ADT/PointerUnion.h"
25 #include "llvm/ADT/StringRef.h"
26 #include "llvm/ADT/iterator.h"
27 #include "llvm/ADT/iterator_range.h"
28 #include "llvm/Support/Allocator.h"
29 #include "llvm/Support/Compiler.h"
30 #include <cassert>
31 #include <cstddef>
32 #include <iterator>
33 #include <utility>
34 #include <vector>
35
36 namespace clang {
37
38 class PreprocessingRecord;
39
40 } // namespace clang
41
42 /// Allocates memory within a Clang preprocessing record.
43 void *operator new(size_t bytes, clang::PreprocessingRecord &PR,
44 unsigned alignment = 8) noexcept;
45
46 /// Frees memory allocated in a Clang preprocessing record.
47 void operator delete(void *ptr, clang::PreprocessingRecord &PR,
48 unsigned) noexcept;
49
50 namespace clang {
51
52 class FileEntry;
53 class IdentifierInfo;
54 class MacroInfo;
55 class SourceManager;
56 class Token;
57
58 /// Base class that describes a preprocessed entity, which may be a
59 /// preprocessor directive or macro expansion.
60 class PreprocessedEntity {
61 public:
62 /// The kind of preprocessed entity an object describes.
63 enum EntityKind {
64 /// Indicates a problem trying to load the preprocessed entity.
65 InvalidKind,
66
67 /// A macro expansion.
68 MacroExpansionKind,
69
70 /// \defgroup Preprocessing directives
71 /// @{
72
73 /// A macro definition.
74 MacroDefinitionKind,
75
76 /// An inclusion directive, such as \c \#include, \c
77 /// \#import, or \c \#include_next.
78 InclusionDirectiveKind,
79
80 /// @}
81
82 FirstPreprocessingDirective = MacroDefinitionKind,
83 LastPreprocessingDirective = InclusionDirectiveKind
84 };
85
86 private:
87 /// The kind of preprocessed entity that this object describes.
88 EntityKind Kind;
89
90 /// The source range that covers this preprocessed entity.
91 SourceRange Range;
92
93 protected:
94 friend class PreprocessingRecord;
95
PreprocessedEntity(EntityKind Kind,SourceRange Range)96 PreprocessedEntity(EntityKind Kind, SourceRange Range)
97 : Kind(Kind), Range(Range) {}
98
99 public:
100 /// Retrieve the kind of preprocessed entity stored in this object.
getKind()101 EntityKind getKind() const { return Kind; }
102
103 /// Retrieve the source range that covers this entire preprocessed
104 /// entity.
getSourceRange()105 SourceRange getSourceRange() const LLVM_READONLY { return Range; }
106
107 /// Returns true if there was a problem loading the preprocessed
108 /// entity.
isInvalid()109 bool isInvalid() const { return Kind == InvalidKind; }
110
111 // Only allow allocation of preprocessed entities using the allocator
112 // in PreprocessingRecord or by doing a placement new.
113 void *operator new(size_t bytes, PreprocessingRecord &PR,
114 unsigned alignment = 8) noexcept {
115 return ::operator new(bytes, PR, alignment);
116 }
117
new(size_t bytes,void * mem)118 void *operator new(size_t bytes, void *mem) noexcept { return mem; }
119
delete(void * ptr,PreprocessingRecord & PR,unsigned alignment)120 void operator delete(void *ptr, PreprocessingRecord &PR,
121 unsigned alignment) noexcept {
122 return ::operator delete(ptr, PR, alignment);
123 }
124
delete(void *,std::size_t)125 void operator delete(void *, std::size_t) noexcept {}
delete(void *,void *)126 void operator delete(void *, void *) noexcept {}
127
128 private:
129 // Make vanilla 'new' and 'delete' illegal for preprocessed entities.
130 void *operator new(size_t bytes) noexcept;
131 void operator delete(void *data) noexcept;
132 };
133
134 /// Records the presence of a preprocessor directive.
135 class PreprocessingDirective : public PreprocessedEntity {
136 public:
PreprocessingDirective(EntityKind Kind,SourceRange Range)137 PreprocessingDirective(EntityKind Kind, SourceRange Range)
138 : PreprocessedEntity(Kind, Range) {}
139
140 // Implement isa/cast/dyncast/etc.
classof(const PreprocessedEntity * PD)141 static bool classof(const PreprocessedEntity *PD) {
142 return PD->getKind() >= FirstPreprocessingDirective &&
143 PD->getKind() <= LastPreprocessingDirective;
144 }
145 };
146
147 /// Record the location of a macro definition.
148 class MacroDefinitionRecord : public PreprocessingDirective {
149 /// The name of the macro being defined.
150 const IdentifierInfo *Name;
151
152 public:
MacroDefinitionRecord(const IdentifierInfo * Name,SourceRange Range)153 explicit MacroDefinitionRecord(const IdentifierInfo *Name,
154 SourceRange Range)
155 : PreprocessingDirective(MacroDefinitionKind, Range), Name(Name) {}
156
157 /// Retrieve the name of the macro being defined.
getName()158 const IdentifierInfo *getName() const { return Name; }
159
160 /// Retrieve the location of the macro name in the definition.
getLocation()161 SourceLocation getLocation() const { return getSourceRange().getBegin(); }
162
163 // Implement isa/cast/dyncast/etc.
classof(const PreprocessedEntity * PE)164 static bool classof(const PreprocessedEntity *PE) {
165 return PE->getKind() == MacroDefinitionKind;
166 }
167 };
168
169 /// Records the location of a macro expansion.
170 class MacroExpansion : public PreprocessedEntity {
171 /// The definition of this macro or the name of the macro if it is
172 /// a builtin macro.
173 llvm::PointerUnion<IdentifierInfo *, MacroDefinitionRecord *> NameOrDef;
174
175 public:
MacroExpansion(IdentifierInfo * BuiltinName,SourceRange Range)176 MacroExpansion(IdentifierInfo *BuiltinName, SourceRange Range)
177 : PreprocessedEntity(MacroExpansionKind, Range),
178 NameOrDef(BuiltinName) {}
179
MacroExpansion(MacroDefinitionRecord * Definition,SourceRange Range)180 MacroExpansion(MacroDefinitionRecord *Definition, SourceRange Range)
181 : PreprocessedEntity(MacroExpansionKind, Range), NameOrDef(Definition) {
182 }
183
184 /// True if it is a builtin macro.
isBuiltinMacro()185 bool isBuiltinMacro() const { return NameOrDef.is<IdentifierInfo *>(); }
186
187 /// The name of the macro being expanded.
getName()188 const IdentifierInfo *getName() const {
189 if (MacroDefinitionRecord *Def = getDefinition())
190 return Def->getName();
191 return NameOrDef.get<IdentifierInfo *>();
192 }
193
194 /// The definition of the macro being expanded. May return null if
195 /// this is a builtin macro.
getDefinition()196 MacroDefinitionRecord *getDefinition() const {
197 return NameOrDef.dyn_cast<MacroDefinitionRecord *>();
198 }
199
200 // Implement isa/cast/dyncast/etc.
classof(const PreprocessedEntity * PE)201 static bool classof(const PreprocessedEntity *PE) {
202 return PE->getKind() == MacroExpansionKind;
203 }
204 };
205
206 /// Record the location of an inclusion directive, such as an
207 /// \c \#include or \c \#import statement.
208 class InclusionDirective : public PreprocessingDirective {
209 public:
210 /// The kind of inclusion directives known to the
211 /// preprocessor.
212 enum InclusionKind {
213 /// An \c \#include directive.
214 Include,
215
216 /// An Objective-C \c \#import directive.
217 Import,
218
219 /// A GNU \c \#include_next directive.
220 IncludeNext,
221
222 /// A Clang \c \#__include_macros directive.
223 IncludeMacros
224 };
225
226 private:
227 /// The name of the file that was included, as written in
228 /// the source.
229 StringRef FileName;
230
231 /// Whether the file name was in quotation marks; otherwise, it was
232 /// in angle brackets.
233 unsigned InQuotes : 1;
234
235 /// The kind of inclusion directive we have.
236 ///
237 /// This is a value of type InclusionKind.
238 unsigned Kind : 2;
239
240 /// Whether the inclusion directive was automatically turned into
241 /// a module import.
242 unsigned ImportedModule : 1;
243
244 /// The file that was included.
245 const FileEntry *File;
246
247 public:
248 InclusionDirective(PreprocessingRecord &PPRec,
249 InclusionKind Kind, StringRef FileName,
250 bool InQuotes, bool ImportedModule,
251 const FileEntry *File, SourceRange Range);
252
253 /// Determine what kind of inclusion directive this is.
getKind()254 InclusionKind getKind() const { return static_cast<InclusionKind>(Kind); }
255
256 /// Retrieve the included file name as it was written in the source.
getFileName()257 StringRef getFileName() const { return FileName; }
258
259 /// Determine whether the included file name was written in quotes;
260 /// otherwise, it was written in angle brackets.
wasInQuotes()261 bool wasInQuotes() const { return InQuotes; }
262
263 /// Determine whether the inclusion directive was automatically
264 /// turned into a module import.
importedModule()265 bool importedModule() const { return ImportedModule; }
266
267 /// Retrieve the file entry for the actual file that was included
268 /// by this directive.
getFile()269 const FileEntry *getFile() const { return File; }
270
271 // Implement isa/cast/dyncast/etc.
classof(const PreprocessedEntity * PE)272 static bool classof(const PreprocessedEntity *PE) {
273 return PE->getKind() == InclusionDirectiveKind;
274 }
275 };
276
277 /// An abstract class that should be subclassed by any external source
278 /// of preprocessing record entries.
279 class ExternalPreprocessingRecordSource {
280 public:
281 virtual ~ExternalPreprocessingRecordSource();
282
283 /// Read a preallocated preprocessed entity from the external source.
284 ///
285 /// \returns null if an error occurred that prevented the preprocessed
286 /// entity from being loaded.
287 virtual PreprocessedEntity *ReadPreprocessedEntity(unsigned Index) = 0;
288
289 /// Returns a pair of [Begin, End) indices of preallocated
290 /// preprocessed entities that \p Range encompasses.
291 virtual std::pair<unsigned, unsigned>
292 findPreprocessedEntitiesInRange(SourceRange Range) = 0;
293
294 /// Optionally returns true or false if the preallocated preprocessed
295 /// entity with index \p Index came from file \p FID.
isPreprocessedEntityInFileID(unsigned Index,FileID FID)296 virtual Optional<bool> isPreprocessedEntityInFileID(unsigned Index,
297 FileID FID) {
298 return None;
299 }
300
301 /// Read a preallocated skipped range from the external source.
302 virtual SourceRange ReadSkippedRange(unsigned Index) = 0;
303 };
304
305 /// A record of the steps taken while preprocessing a source file,
306 /// including the various preprocessing directives processed, macros
307 /// expanded, etc.
308 class PreprocessingRecord : public PPCallbacks {
309 SourceManager &SourceMgr;
310
311 /// Allocator used to store preprocessing objects.
312 llvm::BumpPtrAllocator BumpAlloc;
313
314 /// The set of preprocessed entities in this record, in order they
315 /// were seen.
316 std::vector<PreprocessedEntity *> PreprocessedEntities;
317
318 /// The set of preprocessed entities in this record that have been
319 /// loaded from external sources.
320 ///
321 /// The entries in this vector are loaded lazily from the external source,
322 /// and are referenced by the iterator using negative indices.
323 std::vector<PreprocessedEntity *> LoadedPreprocessedEntities;
324
325 /// The set of ranges that were skipped by the preprocessor,
326 std::vector<SourceRange> SkippedRanges;
327
328 bool SkippedRangesAllLoaded = true;
329
330 /// Global (loaded or local) ID for a preprocessed entity.
331 /// Negative values are used to indicate preprocessed entities
332 /// loaded from the external source while non-negative values are used to
333 /// indicate preprocessed entities introduced by the current preprocessor.
334 /// Value -1 corresponds to element 0 in the loaded entities vector,
335 /// value -2 corresponds to element 1 in the loaded entities vector, etc.
336 /// Value 0 is an invalid value, the index to local entities is 1-based,
337 /// value 1 corresponds to element 0 in the local entities vector,
338 /// value 2 corresponds to element 1 in the local entities vector, etc.
339 class PPEntityID {
340 friend class PreprocessingRecord;
341
342 int ID = 0;
343
PPEntityID(int ID)344 explicit PPEntityID(int ID) : ID(ID) {}
345
346 public:
347 PPEntityID() = default;
348 };
349
getPPEntityID(unsigned Index,bool isLoaded)350 static PPEntityID getPPEntityID(unsigned Index, bool isLoaded) {
351 return isLoaded ? PPEntityID(-int(Index)-1) : PPEntityID(Index+1);
352 }
353
354 /// Mapping from MacroInfo structures to their definitions.
355 llvm::DenseMap<const MacroInfo *, MacroDefinitionRecord *> MacroDefinitions;
356
357 /// External source of preprocessed entities.
358 ExternalPreprocessingRecordSource *ExternalSource = nullptr;
359
360 /// Retrieve the preprocessed entity at the given ID.
361 PreprocessedEntity *getPreprocessedEntity(PPEntityID PPID);
362
363 /// Retrieve the loaded preprocessed entity at the given index.
364 PreprocessedEntity *getLoadedPreprocessedEntity(unsigned Index);
365
366 /// Determine the number of preprocessed entities that were
367 /// loaded (or can be loaded) from an external source.
getNumLoadedPreprocessedEntities()368 unsigned getNumLoadedPreprocessedEntities() const {
369 return LoadedPreprocessedEntities.size();
370 }
371
372 /// Returns a pair of [Begin, End) indices of local preprocessed
373 /// entities that \p Range encompasses.
374 std::pair<unsigned, unsigned>
375 findLocalPreprocessedEntitiesInRange(SourceRange Range) const;
376 unsigned findBeginLocalPreprocessedEntity(SourceLocation Loc) const;
377 unsigned findEndLocalPreprocessedEntity(SourceLocation Loc) const;
378
379 /// Allocate space for a new set of loaded preprocessed entities.
380 ///
381 /// \returns The index into the set of loaded preprocessed entities, which
382 /// corresponds to the first newly-allocated entity.
383 unsigned allocateLoadedEntities(unsigned NumEntities);
384
385 /// Allocate space for a new set of loaded preprocessed skipped
386 /// ranges.
387 ///
388 /// \returns The index into the set of loaded preprocessed ranges, which
389 /// corresponds to the first newly-allocated range.
390 unsigned allocateSkippedRanges(unsigned NumRanges);
391
392 /// Ensures that all external skipped ranges have been loaded.
393 void ensureSkippedRangesLoaded();
394
395 /// Register a new macro definition.
396 void RegisterMacroDefinition(MacroInfo *Macro, MacroDefinitionRecord *Def);
397
398 public:
399 /// Construct a new preprocessing record.
400 explicit PreprocessingRecord(SourceManager &SM);
401
402 /// Allocate memory in the preprocessing record.
403 void *Allocate(unsigned Size, unsigned Align = 8) {
404 return BumpAlloc.Allocate(Size, Align);
405 }
406
407 /// Deallocate memory in the preprocessing record.
Deallocate(void * Ptr)408 void Deallocate(void *Ptr) {}
409
410 size_t getTotalMemory() const;
411
getSourceManager()412 SourceManager &getSourceManager() const { return SourceMgr; }
413
414 /// Iteration over the preprocessed entities.
415 ///
416 /// In a complete iteration, the iterator walks the range [-M, N),
417 /// where negative values are used to indicate preprocessed entities
418 /// loaded from the external source while non-negative values are used to
419 /// indicate preprocessed entities introduced by the current preprocessor.
420 /// However, to provide iteration in source order (for, e.g., chained
421 /// precompiled headers), dereferencing the iterator flips the negative
422 /// values (corresponding to loaded entities), so that position -M
423 /// corresponds to element 0 in the loaded entities vector, position -M+1
424 /// corresponds to element 1 in the loaded entities vector, etc. This
425 /// gives us a reasonably efficient, source-order walk.
426 ///
427 /// We define this as a wrapping iterator around an int. The
428 /// iterator_adaptor_base class forwards the iterator methods to basic
429 /// integer arithmetic.
430 class iterator : public llvm::iterator_adaptor_base<
431 iterator, int, std::random_access_iterator_tag,
432 PreprocessedEntity *, int, PreprocessedEntity *,
433 PreprocessedEntity *> {
434 friend class PreprocessingRecord;
435
436 PreprocessingRecord *Self;
437
iterator(PreprocessingRecord * Self,int Position)438 iterator(PreprocessingRecord *Self, int Position)
439 : iterator::iterator_adaptor_base(Position), Self(Self) {}
440
441 public:
iterator()442 iterator() : iterator(nullptr, 0) {}
443
444 PreprocessedEntity *operator*() const {
445 bool isLoaded = this->I < 0;
446 unsigned Index = isLoaded ?
447 Self->LoadedPreprocessedEntities.size() + this->I : this->I;
448 PPEntityID ID = Self->getPPEntityID(Index, isLoaded);
449 return Self->getPreprocessedEntity(ID);
450 }
451 PreprocessedEntity *operator->() const { return **this; }
452 };
453
454 /// Begin iterator for all preprocessed entities.
begin()455 iterator begin() {
456 return iterator(this, -(int)LoadedPreprocessedEntities.size());
457 }
458
459 /// End iterator for all preprocessed entities.
end()460 iterator end() {
461 return iterator(this, PreprocessedEntities.size());
462 }
463
464 /// Begin iterator for local, non-loaded, preprocessed entities.
local_begin()465 iterator local_begin() {
466 return iterator(this, 0);
467 }
468
469 /// End iterator for local, non-loaded, preprocessed entities.
local_end()470 iterator local_end() {
471 return iterator(this, PreprocessedEntities.size());
472 }
473
474 /// iterator range for the given range of loaded
475 /// preprocessed entities.
getIteratorsForLoadedRange(unsigned start,unsigned count)476 llvm::iterator_range<iterator> getIteratorsForLoadedRange(unsigned start,
477 unsigned count) {
478 unsigned end = start + count;
479 assert(end <= LoadedPreprocessedEntities.size());
480 return llvm::make_range(
481 iterator(this, int(start) - LoadedPreprocessedEntities.size()),
482 iterator(this, int(end) - LoadedPreprocessedEntities.size()));
483 }
484
485 /// Returns a range of preprocessed entities that source range \p R
486 /// encompasses.
487 ///
488 /// \param R the range to look for preprocessed entities.
489 llvm::iterator_range<iterator>
490 getPreprocessedEntitiesInRange(SourceRange R);
491
492 /// Returns true if the preprocessed entity that \p PPEI iterator
493 /// points to is coming from the file \p FID.
494 ///
495 /// Can be used to avoid implicit deserializations of preallocated
496 /// preprocessed entities if we only care about entities of a specific file
497 /// and not from files \#included in the range given at
498 /// \see getPreprocessedEntitiesInRange.
499 bool isEntityInFileID(iterator PPEI, FileID FID);
500
501 /// Add a new preprocessed entity to this record.
502 PPEntityID addPreprocessedEntity(PreprocessedEntity *Entity);
503
504 /// Set the external source for preprocessed entities.
505 void SetExternalSource(ExternalPreprocessingRecordSource &Source);
506
507 /// Retrieve the external source for preprocessed entities.
getExternalSource()508 ExternalPreprocessingRecordSource *getExternalSource() const {
509 return ExternalSource;
510 }
511
512 /// Retrieve the macro definition that corresponds to the given
513 /// \c MacroInfo.
514 MacroDefinitionRecord *findMacroDefinition(const MacroInfo *MI);
515
516 /// Retrieve all ranges that got skipped while preprocessing.
getSkippedRanges()517 const std::vector<SourceRange> &getSkippedRanges() {
518 ensureSkippedRangesLoaded();
519 return SkippedRanges;
520 }
521
522 private:
523 friend class ASTReader;
524 friend class ASTWriter;
525
526 void MacroExpands(const Token &Id, const MacroDefinition &MD,
527 SourceRange Range, const MacroArgs *Args) override;
528 void MacroDefined(const Token &Id, const MacroDirective *MD) override;
529 void MacroUndefined(const Token &Id, const MacroDefinition &MD,
530 const MacroDirective *Undef) override;
531 void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
532 StringRef FileName, bool IsAngled,
533 CharSourceRange FilenameRange,
534 const FileEntry *File, StringRef SearchPath,
535 StringRef RelativePath, const Module *Imported,
536 SrcMgr::CharacteristicKind FileType) override;
537 void Ifdef(SourceLocation Loc, const Token &MacroNameTok,
538 const MacroDefinition &MD) override;
539 void Ifndef(SourceLocation Loc, const Token &MacroNameTok,
540 const MacroDefinition &MD) override;
541
542 using PPCallbacks::Elifdef;
543 using PPCallbacks::Elifndef;
544 void Elifdef(SourceLocation Loc, const Token &MacroNameTok,
545 const MacroDefinition &MD) override;
546 void Elifndef(SourceLocation Loc, const Token &MacroNameTok,
547 const MacroDefinition &MD) override;
548
549 /// Hook called whenever the 'defined' operator is seen.
550 void Defined(const Token &MacroNameTok, const MacroDefinition &MD,
551 SourceRange Range) override;
552
553 void SourceRangeSkipped(SourceRange Range,
554 SourceLocation EndifLoc) override;
555
556 void addMacroExpansion(const Token &Id, const MacroInfo *MI,
557 SourceRange Range);
558
559 /// Cached result of the last \see getPreprocessedEntitiesInRange
560 /// query.
561 struct {
562 SourceRange Range;
563 std::pair<int, int> Result;
564 } CachedRangeQuery;
565
566 std::pair<int, int> getPreprocessedEntitiesInRangeSlow(SourceRange R);
567 };
568
569 } // namespace clang
570
new(size_t bytes,clang::PreprocessingRecord & PR,unsigned alignment)571 inline void *operator new(size_t bytes, clang::PreprocessingRecord &PR,
572 unsigned alignment) noexcept {
573 return PR.Allocate(bytes, alignment);
574 }
575
delete(void * ptr,clang::PreprocessingRecord & PR,unsigned)576 inline void operator delete(void *ptr, clang::PreprocessingRecord &PR,
577 unsigned) noexcept {
578 PR.Deallocate(ptr);
579 }
580
581 #endif // LLVM_CLANG_LEX_PREPROCESSINGRECORD_H
582