1//===--- ExternalASTSource.h - Abstract External AST Interface --*- 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 ExternalASTSource interface, which enables
11//  construction of AST nodes from some external source.
12//
13//===----------------------------------------------------------------------===//
14#ifndef LLVM_CLANG_AST_EXTERNAL_AST_SOURCE_H
15#define LLVM_CLANG_AST_EXTERNAL_AST_SOURCE_H
16
17#include "clang/AST/CharUnits.h"
18#include "clang/AST/DeclBase.h"
19#include "llvm/ADT/DenseMap.h"
20
21namespace clang {
22
23class ASTConsumer;
24class CXXBaseSpecifier;
25class DeclarationName;
26class ExternalSemaSource; // layering violation required for downcasting
27class FieldDecl;
28class Module;
29class NamedDecl;
30class RecordDecl;
31class Selector;
32class Stmt;
33class TagDecl;
34
35/// \brief Enumeration describing the result of loading information from
36/// an external source.
37enum ExternalLoadResult {
38  /// \brief Loading the external information has succeeded.
39  ELR_Success,
40
41  /// \brief Loading the external information has failed.
42  ELR_Failure,
43
44  /// \brief The external information has already been loaded, and therefore
45  /// no additional processing is required.
46  ELR_AlreadyLoaded
47};
48
49/// \brief Abstract interface for external sources of AST nodes.
50///
51/// External AST sources provide AST nodes constructed from some
52/// external source, such as a precompiled header. External AST
53/// sources can resolve types and declarations from abstract IDs into
54/// actual type and declaration nodes, and read parts of declaration
55/// contexts.
56class ExternalASTSource : public RefCountedBase<ExternalASTSource> {
57  /// Generation number for this external AST source. Must be increased
58  /// whenever we might have added new redeclarations for existing decls.
59  uint32_t CurrentGeneration;
60
61  /// \brief Whether this AST source also provides information for
62  /// semantic analysis.
63  bool SemaSource;
64
65  friend class ExternalSemaSource;
66
67public:
68  ExternalASTSource() : CurrentGeneration(0), SemaSource(false) { }
69
70  virtual ~ExternalASTSource();
71
72  /// \brief RAII class for safely pairing a StartedDeserializing call
73  /// with FinishedDeserializing.
74  class Deserializing {
75    ExternalASTSource *Source;
76  public:
77    explicit Deserializing(ExternalASTSource *source) : Source(source) {
78      assert(Source);
79      Source->StartedDeserializing();
80    }
81    ~Deserializing() {
82      Source->FinishedDeserializing();
83    }
84  };
85
86  /// \brief Get the current generation of this AST source. This number
87  /// is incremented each time the AST source lazily extends an existing
88  /// entity.
89  uint32_t getGeneration() const { return CurrentGeneration; }
90
91  /// \brief Resolve a declaration ID into a declaration, potentially
92  /// building a new declaration.
93  ///
94  /// This method only needs to be implemented if the AST source ever
95  /// passes back decl sets as VisibleDeclaration objects.
96  ///
97  /// The default implementation of this method is a no-op.
98  virtual Decl *GetExternalDecl(uint32_t ID);
99
100  /// \brief Resolve a selector ID into a selector.
101  ///
102  /// This operation only needs to be implemented if the AST source
103  /// returns non-zero for GetNumKnownSelectors().
104  ///
105  /// The default implementation of this method is a no-op.
106  virtual Selector GetExternalSelector(uint32_t ID);
107
108  /// \brief Returns the number of selectors known to the external AST
109  /// source.
110  ///
111  /// The default implementation of this method is a no-op.
112  virtual uint32_t GetNumExternalSelectors();
113
114  /// \brief Resolve the offset of a statement in the decl stream into
115  /// a statement.
116  ///
117  /// This operation is meant to be used via a LazyOffsetPtr.  It only
118  /// needs to be implemented if the AST source uses methods like
119  /// FunctionDecl::setLazyBody when building decls.
120  ///
121  /// The default implementation of this method is a no-op.
122  virtual Stmt *GetExternalDeclStmt(uint64_t Offset);
123
124  /// \brief Resolve the offset of a set of C++ base specifiers in the decl
125  /// stream into an array of specifiers.
126  ///
127  /// The default implementation of this method is a no-op.
128  virtual CXXBaseSpecifier *GetExternalCXXBaseSpecifiers(uint64_t Offset);
129
130  /// \brief Update an out-of-date identifier.
131  virtual void updateOutOfDateIdentifier(IdentifierInfo &II) { }
132
133  /// \brief Find all declarations with the given name in the given context,
134  /// and add them to the context by calling SetExternalVisibleDeclsForName
135  /// or SetNoExternalVisibleDeclsForName.
136  /// \return \c true if any declarations might have been found, \c false if
137  /// we definitely have no declarations with tbis name.
138  ///
139  /// The default implementation of this method is a no-op returning \c false.
140  virtual bool
141  FindExternalVisibleDeclsByName(const DeclContext *DC, DeclarationName Name);
142
143  /// \brief Ensures that the table of all visible declarations inside this
144  /// context is up to date.
145  ///
146  /// The default implementation of this function is a no-op.
147  virtual void completeVisibleDeclsMap(const DeclContext *DC);
148
149  /// \brief Retrieve the module that corresponds to the given module ID.
150  virtual Module *getModule(unsigned ID) { return nullptr; }
151
152  /// \brief Finds all declarations lexically contained within the given
153  /// DeclContext, after applying an optional filter predicate.
154  ///
155  /// \param isKindWeWant a predicate function that returns true if the passed
156  /// declaration kind is one we are looking for. If NULL, all declarations
157  /// are returned.
158  ///
159  /// \return an indication of whether the load succeeded or failed.
160  ///
161  /// The default implementation of this method is a no-op.
162  virtual ExternalLoadResult FindExternalLexicalDecls(const DeclContext *DC,
163                                        bool (*isKindWeWant)(Decl::Kind),
164                                        SmallVectorImpl<Decl*> &Result);
165
166  /// \brief Finds all declarations lexically contained within the given
167  /// DeclContext.
168  ///
169  /// \return true if an error occurred
170  ExternalLoadResult FindExternalLexicalDecls(const DeclContext *DC,
171                                SmallVectorImpl<Decl*> &Result) {
172    return FindExternalLexicalDecls(DC, nullptr, Result);
173  }
174
175  template <typename DeclTy>
176  ExternalLoadResult FindExternalLexicalDeclsBy(const DeclContext *DC,
177                                  SmallVectorImpl<Decl*> &Result) {
178    return FindExternalLexicalDecls(DC, DeclTy::classofKind, Result);
179  }
180
181  /// \brief Get the decls that are contained in a file in the Offset/Length
182  /// range. \p Length can be 0 to indicate a point at \p Offset instead of
183  /// a range.
184  virtual void FindFileRegionDecls(FileID File, unsigned Offset,
185                                   unsigned Length,
186                                   SmallVectorImpl<Decl *> &Decls);
187
188  /// \brief Gives the external AST source an opportunity to complete
189  /// the redeclaration chain for a declaration. Called each time we
190  /// need the most recent declaration of a declaration after the
191  /// generation count is incremented.
192  virtual void CompleteRedeclChain(const Decl *D);
193
194  /// \brief Gives the external AST source an opportunity to complete
195  /// an incomplete type.
196  virtual void CompleteType(TagDecl *Tag);
197
198  /// \brief Gives the external AST source an opportunity to complete an
199  /// incomplete Objective-C class.
200  ///
201  /// This routine will only be invoked if the "externally completed" bit is
202  /// set on the ObjCInterfaceDecl via the function
203  /// \c ObjCInterfaceDecl::setExternallyCompleted().
204  virtual void CompleteType(ObjCInterfaceDecl *Class);
205
206  /// \brief Loads comment ranges.
207  virtual void ReadComments();
208
209  /// \brief Notify ExternalASTSource that we started deserialization of
210  /// a decl or type so until FinishedDeserializing is called there may be
211  /// decls that are initializing. Must be paired with FinishedDeserializing.
212  ///
213  /// The default implementation of this method is a no-op.
214  virtual void StartedDeserializing();
215
216  /// \brief Notify ExternalASTSource that we finished the deserialization of
217  /// a decl or type. Must be paired with StartedDeserializing.
218  ///
219  /// The default implementation of this method is a no-op.
220  virtual void FinishedDeserializing();
221
222  /// \brief Function that will be invoked when we begin parsing a new
223  /// translation unit involving this external AST source.
224  ///
225  /// The default implementation of this method is a no-op.
226  virtual void StartTranslationUnit(ASTConsumer *Consumer);
227
228  /// \brief Print any statistics that have been gathered regarding
229  /// the external AST source.
230  ///
231  /// The default implementation of this method is a no-op.
232  virtual void PrintStats();
233
234
235  /// \brief Perform layout on the given record.
236  ///
237  /// This routine allows the external AST source to provide an specific
238  /// layout for a record, overriding the layout that would normally be
239  /// constructed. It is intended for clients who receive specific layout
240  /// details rather than source code (such as LLDB). The client is expected
241  /// to fill in the field offsets, base offsets, virtual base offsets, and
242  /// complete object size.
243  ///
244  /// \param Record The record whose layout is being requested.
245  ///
246  /// \param Size The final size of the record, in bits.
247  ///
248  /// \param Alignment The final alignment of the record, in bits.
249  ///
250  /// \param FieldOffsets The offset of each of the fields within the record,
251  /// expressed in bits. All of the fields must be provided with offsets.
252  ///
253  /// \param BaseOffsets The offset of each of the direct, non-virtual base
254  /// classes. If any bases are not given offsets, the bases will be laid
255  /// out according to the ABI.
256  ///
257  /// \param VirtualBaseOffsets The offset of each of the virtual base classes
258  /// (either direct or not). If any bases are not given offsets, the bases will be laid
259  /// out according to the ABI.
260  ///
261  /// \returns true if the record layout was provided, false otherwise.
262  virtual bool layoutRecordType(
263      const RecordDecl *Record, uint64_t &Size, uint64_t &Alignment,
264      llvm::DenseMap<const FieldDecl *, uint64_t> &FieldOffsets,
265      llvm::DenseMap<const CXXRecordDecl *, CharUnits> &BaseOffsets,
266      llvm::DenseMap<const CXXRecordDecl *, CharUnits> &VirtualBaseOffsets);
267
268  //===--------------------------------------------------------------------===//
269  // Queries for performance analysis.
270  //===--------------------------------------------------------------------===//
271
272  struct MemoryBufferSizes {
273    size_t malloc_bytes;
274    size_t mmap_bytes;
275
276    MemoryBufferSizes(size_t malloc_bytes, size_t mmap_bytes)
277    : malloc_bytes(malloc_bytes), mmap_bytes(mmap_bytes) {}
278  };
279
280  /// Return the amount of memory used by memory buffers, breaking down
281  /// by heap-backed versus mmap'ed memory.
282  MemoryBufferSizes getMemoryBufferSizes() const {
283    MemoryBufferSizes sizes(0, 0);
284    getMemoryBufferSizes(sizes);
285    return sizes;
286  }
287
288  virtual void getMemoryBufferSizes(MemoryBufferSizes &sizes) const;
289
290protected:
291  static DeclContextLookupResult
292  SetExternalVisibleDeclsForName(const DeclContext *DC,
293                                 DeclarationName Name,
294                                 ArrayRef<NamedDecl*> Decls);
295
296  static DeclContextLookupResult
297  SetNoExternalVisibleDeclsForName(const DeclContext *DC,
298                                   DeclarationName Name);
299
300  /// \brief Increment the current generation.
301  uint32_t incrementGeneration(ASTContext &C);
302};
303
304/// \brief A lazy pointer to an AST node (of base type T) that resides
305/// within an external AST source.
306///
307/// The AST node is identified within the external AST source by a
308/// 63-bit offset, and can be retrieved via an operation on the
309/// external AST source itself.
310template<typename T, typename OffsT, T* (ExternalASTSource::*Get)(OffsT Offset)>
311struct LazyOffsetPtr {
312  /// \brief Either a pointer to an AST node or the offset within the
313  /// external AST source where the AST node can be found.
314  ///
315  /// If the low bit is clear, a pointer to the AST node. If the low
316  /// bit is set, the upper 63 bits are the offset.
317  mutable uint64_t Ptr;
318
319public:
320  LazyOffsetPtr() : Ptr(0) { }
321
322  explicit LazyOffsetPtr(T *Ptr) : Ptr(reinterpret_cast<uint64_t>(Ptr)) { }
323  explicit LazyOffsetPtr(uint64_t Offset) : Ptr((Offset << 1) | 0x01) {
324    assert((Offset << 1 >> 1) == Offset && "Offsets must require < 63 bits");
325    if (Offset == 0)
326      Ptr = 0;
327  }
328
329  LazyOffsetPtr &operator=(T *Ptr) {
330    this->Ptr = reinterpret_cast<uint64_t>(Ptr);
331    return *this;
332  }
333
334  LazyOffsetPtr &operator=(uint64_t Offset) {
335    assert((Offset << 1 >> 1) == Offset && "Offsets must require < 63 bits");
336    if (Offset == 0)
337      Ptr = 0;
338    else
339      Ptr = (Offset << 1) | 0x01;
340
341    return *this;
342  }
343
344  /// \brief Whether this pointer is non-NULL.
345  ///
346  /// This operation does not require the AST node to be deserialized.
347  LLVM_EXPLICIT operator bool() const { return Ptr != 0; }
348
349  /// \brief Whether this pointer is non-NULL.
350  ///
351  /// This operation does not require the AST node to be deserialized.
352  bool isValid() const { return Ptr != 0; }
353
354  /// \brief Whether this pointer is currently stored as an offset.
355  bool isOffset() const { return Ptr & 0x01; }
356
357  /// \brief Retrieve the pointer to the AST node that this lazy pointer
358  ///
359  /// \param Source the external AST source.
360  ///
361  /// \returns a pointer to the AST node.
362  T* get(ExternalASTSource *Source) const {
363    if (isOffset()) {
364      assert(Source &&
365             "Cannot deserialize a lazy pointer without an AST source");
366      Ptr = reinterpret_cast<uint64_t>((Source->*Get)(Ptr >> 1));
367    }
368    return reinterpret_cast<T*>(Ptr);
369  }
370};
371
372/// \brief A lazy value (of type T) that is within an AST node of type Owner,
373/// where the value might change in later generations of the external AST
374/// source.
375template<typename Owner, typename T, void (ExternalASTSource::*Update)(Owner)>
376struct LazyGenerationalUpdatePtr {
377  /// A cache of the value of this pointer, in the most recent generation in
378  /// which we queried it.
379  struct LazyData {
380    LazyData(ExternalASTSource *Source, T Value)
381        : ExternalSource(Source), LastGeneration(0), LastValue(Value) {}
382    ExternalASTSource *ExternalSource;
383    uint32_t LastGeneration;
384    T LastValue;
385  };
386
387  // Our value is represented as simply T if there is no external AST source.
388  typedef llvm::PointerUnion<T, LazyData*> ValueType;
389  ValueType Value;
390
391  LazyGenerationalUpdatePtr(ValueType V) : Value(V) {}
392
393  // Defined in ASTContext.h
394  static ValueType makeValue(const ASTContext &Ctx, T Value);
395
396public:
397  explicit LazyGenerationalUpdatePtr(const ASTContext &Ctx, T Value = T())
398      : Value(makeValue(Ctx, Value)) {}
399
400  /// Create a pointer that is not potentially updated by later generations of
401  /// the external AST source.
402  enum NotUpdatedTag { NotUpdated };
403  LazyGenerationalUpdatePtr(NotUpdatedTag, T Value = T())
404      : Value(Value) {}
405
406  /// Forcibly set this pointer (which must be lazy) as needing updates.
407  void markIncomplete() {
408    Value.template get<LazyData *>()->LastGeneration = 0;
409  }
410
411  /// Set the value of this pointer, in the current generation.
412  void set(T NewValue) {
413    if (LazyData *LazyVal = Value.template dyn_cast<LazyData*>()) {
414      LazyVal->LastValue = NewValue;
415      return;
416    }
417    Value = NewValue;
418  }
419
420  /// Set the value of this pointer, for this and all future generations.
421  void setNotUpdated(T NewValue) { Value = NewValue; }
422
423  /// Get the value of this pointer, updating its owner if necessary.
424  T get(Owner O) {
425    if (LazyData *LazyVal = Value.template dyn_cast<LazyData*>()) {
426      if (LazyVal->LastGeneration != LazyVal->ExternalSource->getGeneration()) {
427        LazyVal->LastGeneration = LazyVal->ExternalSource->getGeneration();
428        (LazyVal->ExternalSource->*Update)(O);
429      }
430      return LazyVal->LastValue;
431    }
432    return Value.template get<T>();
433  }
434
435  /// Get the most recently computed value of this pointer without updating it.
436  T getNotUpdated() const {
437    if (LazyData *LazyVal = Value.template dyn_cast<LazyData*>())
438      return LazyVal->LastValue;
439    return Value.template get<T>();
440  }
441
442  void *getOpaqueValue() { return Value.getOpaqueValue(); }
443  static LazyGenerationalUpdatePtr getFromOpaqueValue(void *Ptr) {
444    return LazyGenerationalUpdatePtr(ValueType::getFromOpaqueValue(Ptr));
445  }
446};
447} // end namespace clang
448
449/// Specialize PointerLikeTypeTraits to allow LazyGenerationalUpdatePtr to be
450/// placed into a PointerUnion.
451namespace llvm {
452template<typename Owner, typename T,
453         void (clang::ExternalASTSource::*Update)(Owner)>
454struct PointerLikeTypeTraits<
455    clang::LazyGenerationalUpdatePtr<Owner, T, Update>> {
456  typedef clang::LazyGenerationalUpdatePtr<Owner, T, Update> Ptr;
457  static void *getAsVoidPointer(Ptr P) { return P.getOpaqueValue(); }
458  static Ptr getFromVoidPointer(void *P) { return Ptr::getFromOpaqueValue(P); }
459  enum {
460    NumLowBitsAvailable = PointerLikeTypeTraits<T>::NumLowBitsAvailable - 1
461  };
462};
463}
464
465namespace clang {
466/// \brief Represents a lazily-loaded vector of data.
467///
468/// The lazily-loaded vector of data contains data that is partially loaded
469/// from an external source and partially added by local translation. The
470/// items loaded from the external source are loaded lazily, when needed for
471/// iteration over the complete vector.
472template<typename T, typename Source,
473         void (Source::*Loader)(SmallVectorImpl<T>&),
474         unsigned LoadedStorage = 2, unsigned LocalStorage = 4>
475class LazyVector {
476  SmallVector<T, LoadedStorage> Loaded;
477  SmallVector<T, LocalStorage> Local;
478
479public:
480  // Iteration over the elements in the vector.
481  class iterator {
482    LazyVector *Self;
483
484    /// \brief Position within the vector..
485    ///
486    /// In a complete iteration, the Position field walks the range [-M, N),
487    /// where negative values are used to indicate elements
488    /// loaded from the external source while non-negative values are used to
489    /// indicate elements added via \c push_back().
490    /// However, to provide iteration in source order (for, e.g., chained
491    /// precompiled headers), dereferencing the iterator flips the negative
492    /// values (corresponding to loaded entities), so that position -M
493    /// corresponds to element 0 in the loaded entities vector, position -M+1
494    /// corresponds to element 1 in the loaded entities vector, etc. This
495    /// gives us a reasonably efficient, source-order walk.
496    int Position;
497
498    friend class LazyVector;
499
500  public:
501    typedef T                   value_type;
502    typedef value_type&         reference;
503    typedef value_type*         pointer;
504    typedef std::random_access_iterator_tag iterator_category;
505    typedef int                 difference_type;
506
507    iterator() : Self(0), Position(0) { }
508
509    iterator(LazyVector *Self, int Position)
510      : Self(Self), Position(Position) { }
511
512    reference operator*() const {
513      if (Position < 0)
514        return Self->Loaded.end()[Position];
515      return Self->Local[Position];
516    }
517
518    pointer operator->() const {
519      if (Position < 0)
520        return &Self->Loaded.end()[Position];
521
522      return &Self->Local[Position];
523    }
524
525    reference operator[](difference_type D) {
526      return *(*this + D);
527    }
528
529    iterator &operator++() {
530      ++Position;
531      return *this;
532    }
533
534    iterator operator++(int) {
535      iterator Prev(*this);
536      ++Position;
537      return Prev;
538    }
539
540    iterator &operator--() {
541      --Position;
542      return *this;
543    }
544
545    iterator operator--(int) {
546      iterator Prev(*this);
547      --Position;
548      return Prev;
549    }
550
551    friend bool operator==(const iterator &X, const iterator &Y) {
552      return X.Position == Y.Position;
553    }
554
555    friend bool operator!=(const iterator &X, const iterator &Y) {
556      return X.Position != Y.Position;
557    }
558
559    friend bool operator<(const iterator &X, const iterator &Y) {
560      return X.Position < Y.Position;
561    }
562
563    friend bool operator>(const iterator &X, const iterator &Y) {
564      return X.Position > Y.Position;
565    }
566
567    friend bool operator<=(const iterator &X, const iterator &Y) {
568      return X.Position < Y.Position;
569    }
570
571    friend bool operator>=(const iterator &X, const iterator &Y) {
572      return X.Position > Y.Position;
573    }
574
575    friend iterator& operator+=(iterator &X, difference_type D) {
576      X.Position += D;
577      return X;
578    }
579
580    friend iterator& operator-=(iterator &X, difference_type D) {
581      X.Position -= D;
582      return X;
583    }
584
585    friend iterator operator+(iterator X, difference_type D) {
586      X.Position += D;
587      return X;
588    }
589
590    friend iterator operator+(difference_type D, iterator X) {
591      X.Position += D;
592      return X;
593    }
594
595    friend difference_type operator-(const iterator &X, const iterator &Y) {
596      return X.Position - Y.Position;
597    }
598
599    friend iterator operator-(iterator X, difference_type D) {
600      X.Position -= D;
601      return X;
602    }
603  };
604  friend class iterator;
605
606  iterator begin(Source *source, bool LocalOnly = false) {
607    if (LocalOnly)
608      return iterator(this, 0);
609
610    if (source)
611      (source->*Loader)(Loaded);
612    return iterator(this, -(int)Loaded.size());
613  }
614
615  iterator end() {
616    return iterator(this, Local.size());
617  }
618
619  void push_back(const T& LocalValue) {
620    Local.push_back(LocalValue);
621  }
622
623  void erase(iterator From, iterator To) {
624    if (From.Position < 0 && To.Position < 0) {
625      Loaded.erase(Loaded.end() + From.Position, Loaded.end() + To.Position);
626      return;
627    }
628
629    if (From.Position < 0) {
630      Loaded.erase(Loaded.end() + From.Position, Loaded.end());
631      From = begin(nullptr, true);
632    }
633
634    Local.erase(Local.begin() + From.Position, Local.begin() + To.Position);
635  }
636};
637
638/// \brief A lazy pointer to a statement.
639typedef LazyOffsetPtr<Stmt, uint64_t, &ExternalASTSource::GetExternalDeclStmt>
640  LazyDeclStmtPtr;
641
642/// \brief A lazy pointer to a declaration.
643typedef LazyOffsetPtr<Decl, uint32_t, &ExternalASTSource::GetExternalDecl>
644  LazyDeclPtr;
645
646/// \brief A lazy pointer to a set of CXXBaseSpecifiers.
647typedef LazyOffsetPtr<CXXBaseSpecifier, uint64_t,
648                      &ExternalASTSource::GetExternalCXXBaseSpecifiers>
649  LazyCXXBaseSpecifiersPtr;
650
651} // end namespace clang
652
653#endif // LLVM_CLANG_AST_EXTERNAL_AST_SOURCE_H
654