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