contrib/llvm/tools/clang/include/clang/Lex/PreprocessingRecord.h

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