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
35namespace clang {
36
37class PreprocessingRecord;
38
39} // namespace clang
40
41/// Allocates memory within a Clang preprocessing record.
42void *operator new(size_t bytes, clang::PreprocessingRecord &PR,
43                   unsigned alignment = 8) noexcept;
44
45/// Frees memory allocated in a Clang preprocessing record.
46void operator delete(void *ptr, clang::PreprocessingRecord &PR,
47                     unsigned) noexcept;
48
49namespace clang {
50
51class IdentifierInfo;
52class MacroInfo;
53class SourceManager;
54class 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
568inline void *operator new(size_t bytes, clang::PreprocessingRecord &PR,
569                          unsigned alignment) noexcept {
570  return PR.Allocate(bytes, alignment);
571}
572
573inline 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