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
36namespace clang {
37
38class PreprocessingRecord;
39
40} // namespace clang
41
42/// Allocates memory within a Clang preprocessing record.
43void *operator new(size_t bytes, clang::PreprocessingRecord &PR,
44                   unsigned alignment = 8) noexcept;
45
46/// Frees memory allocated in a Clang preprocessing record.
47void operator delete(void *ptr, clang::PreprocessingRecord &PR,
48                     unsigned) noexcept;
49
50namespace clang {
51
52class FileEntry;
53class IdentifierInfo;
54class MacroInfo;
55class SourceManager;
56class 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
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.
101    EntityKind getKind() const { return Kind; }
102
103    /// Retrieve the source range that covers this entire preprocessed
104    /// entity.
105    SourceRange getSourceRange() const LLVM_READONLY { return Range; }
106
107    /// Returns true if there was a problem loading the preprocessed
108    /// entity.
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
118    void *operator new(size_t bytes, void *mem) noexcept { return mem; }
119
120    void operator delete(void *ptr, PreprocessingRecord &PR,
121                         unsigned alignment) noexcept {
122      return ::operator delete(ptr, PR, alignment);
123    }
124
125    void operator delete(void *, std::size_t) noexcept {}
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:
137    PreprocessingDirective(EntityKind Kind, SourceRange Range)
138        : PreprocessedEntity(Kind, Range) {}
139
140    // Implement isa/cast/dyncast/etc.
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:
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.
158    const IdentifierInfo *getName() const { return Name; }
159
160    /// Retrieve the location of the macro name in the definition.
161    SourceLocation getLocation() const { return getSourceRange().getBegin(); }
162
163    // Implement isa/cast/dyncast/etc.
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:
176    MacroExpansion(IdentifierInfo *BuiltinName, SourceRange Range)
177        : PreprocessedEntity(MacroExpansionKind, Range),
178          NameOrDef(BuiltinName) {}
179
180    MacroExpansion(MacroDefinitionRecord *Definition, SourceRange Range)
181        : PreprocessedEntity(MacroExpansionKind, Range), NameOrDef(Definition) {
182    }
183
184    /// True if it is a builtin macro.
185    bool isBuiltinMacro() const { return NameOrDef.is<IdentifierInfo *>(); }
186
187    /// The name of the macro being expanded.
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.
196    MacroDefinitionRecord *getDefinition() const {
197      return NameOrDef.dyn_cast<MacroDefinitionRecord *>();
198    }
199
200    // Implement isa/cast/dyncast/etc.
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.
254    InclusionKind getKind() const { return static_cast<InclusionKind>(Kind); }
255
256    /// Retrieve the included file name as it was written in the source.
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.
261    bool wasInQuotes() const { return InQuotes; }
262
263    /// Determine whether the inclusion directive was automatically
264    /// turned into a module import.
265    bool importedModule() const { return ImportedModule; }
266
267    /// Retrieve the file entry for the actual file that was included
268    /// by this directive.
269    const FileEntry *getFile() const { return File; }
270
271    // Implement isa/cast/dyncast/etc.
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.
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
344      explicit PPEntityID(int ID) : ID(ID) {}
345
346    public:
347      PPEntityID() = default;
348    };
349
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.
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.
408    void Deallocate(void *Ptr) {}
409
410    size_t getTotalMemory() const;
411
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
438      iterator(PreprocessingRecord *Self, int Position)
439          : iterator::iterator_adaptor_base(Position), Self(Self) {}
440
441    public:
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.
455    iterator begin() {
456      return iterator(this, -(int)LoadedPreprocessedEntities.size());
457    }
458
459    /// End iterator for all preprocessed entities.
460    iterator end() {
461      return iterator(this, PreprocessedEntities.size());
462    }
463
464    /// Begin iterator for local, non-loaded, preprocessed entities.
465    iterator local_begin() {
466      return iterator(this, 0);
467    }
468
469    /// End iterator for local, non-loaded, preprocessed entities.
470    iterator local_end() {
471      return iterator(this, PreprocessedEntities.size());
472    }
473
474    /// iterator range for the given range of loaded
475    /// preprocessed entities.
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.
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.
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    /// Hook called whenever the 'defined' operator is seen.
543    void Defined(const Token &MacroNameTok, const MacroDefinition &MD,
544                 SourceRange Range) override;
545
546    void SourceRangeSkipped(SourceRange Range,
547                            SourceLocation EndifLoc) override;
548
549    void addMacroExpansion(const Token &Id, const MacroInfo *MI,
550                           SourceRange Range);
551
552    /// Cached result of the last \see getPreprocessedEntitiesInRange
553    /// query.
554    struct {
555      SourceRange Range;
556      std::pair<int, int> Result;
557    } CachedRangeQuery;
558
559    std::pair<int, int> getPreprocessedEntitiesInRangeSlow(SourceRange R);
560  };
561
562} // namespace clang
563
564inline void *operator new(size_t bytes, clang::PreprocessingRecord &PR,
565                          unsigned alignment) noexcept {
566  return PR.Allocate(bytes, alignment);
567}
568
569inline void operator delete(void *ptr, clang::PreprocessingRecord &PR,
570                            unsigned) noexcept {
571  PR.Deallocate(ptr);
572}
573
574#endif // LLVM_CLANG_LEX_PREPROCESSINGRECORD_H
575