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