-Implement proper name lookup for namespaces.

-identifierResolver exposes an iterator interface to get all decls through the scope chain.
-The semantic staff (checking IdentifierNamespace and Doug's checking for shadowed tags were moved out of IdentifierResolver and back into Sema. IdentifierResolver just gives an iterator for all reachable decls of an identifier.

llvm-svn: 50923

1 files changed, 331 insertions, 14 deletions

diff --git a/clang/lib/Sema/IdentifierResolver.h b/clang/lib/Sema/IdentifierResolver.h
index 34b4764d147..da1327be485 100644
--- a/clang/lib/Sema/IdentifierResolver.h
+++ b/clang/lib/Sema/IdentifierResolver.h
@@ -15,37 +15,354 @@
 #ifndef LLVM_CLANG_AST_SEMA_IDENTIFIERRESOLVER_H
 #define LLVM_CLANG_AST_SEMA_IDENTIFIERRESOLVER_H
 
+#include "clang/Basic/IdentifierTable.h"
+#include "clang/Parse/Scope.h"
+#include "clang/AST/Decl.h"
+
 namespace clang {
-  class IdentifierInfo;
-  class NamedDecl;
-  class Scope;
 
 /// IdentifierResolver - Keeps track of shadowed decls on enclosing scopes.
 /// It manages the shadowing chains of identifiers and implements efficent decl
 /// lookup based on an identifier.
 class IdentifierResolver {
+
+  /// LookupContext - A wrapper for DeclContext. DeclContext is only part of
+  /// ScopedDecls, LookupContext can be used with all decls (assumes
+  /// translation unit context for non ScopedDecls).
+  class LookupContext {
+    DeclContext *Ctx;
+
+    /// TUCtx - Provides a common value for translation unit context for all
+    /// decls.
+    /// FIXME: When (if ?) all decls can point to their translation unit context
+    /// remove this hack.
+    static inline DeclContext *TUCtx() {
+      return reinterpret_cast<DeclContext*>(-1);
+    }
+
+    /// getContext - Returns translation unit context for non ScopedDecls and
+    /// for EnumConstantDecls returns the parent context of their EnumDecl.
+    static DeclContext *getContext(Decl *D) {
+      DeclContext *Ctx;
+
+      if (EnumConstantDecl *EnumD = dyn_cast<EnumConstantDecl>(D)) {
+        Ctx = EnumD->getDeclContext()->getParent();
+      } else if (ScopedDecl *SD = dyn_cast<ScopedDecl>(D))
+        Ctx = SD->getDeclContext();
+      else
+        return TUCtx();
+
+      if (isa<TranslationUnitDecl>(Ctx))
+        return TUCtx();
+
+      return Ctx;
+    }
+
+  public:
+    LookupContext(Decl *D) {
+      Ctx = getContext(D);
+    }
+    LookupContext(DeclContext *DC) {
+      if (!DC || isa<TranslationUnitDecl>(DC))
+        Ctx = TUCtx();
+      else
+        Ctx = DC;
+    }
+
+    bool isTU() const {
+      return (Ctx == TUCtx());
+    }
+
+    /// getParent - Returns the parent context. This should not be called for
+    /// a translation unit context.
+    LookupContext getParent() const {
+      assert(!isTU() && "TU has no parent!");
+      return LookupContext(Ctx->getParent());
+    }
+
+    /// isEqOrContainedBy - Returns true of the given context is the same or a
+    /// parent of this one.
+    bool isEqOrContainedBy(const LookupContext &PC) const {
+      if (PC.isTU()) return true;
+
+      for (LookupContext Next = *this; !Next.isTU();  Next = Next.getParent())
+        if (Next.Ctx == PC.Ctx) return true;
+
+      return false;
+    }
+
+    bool operator==(const LookupContext &RHS) const {
+      return Ctx == RHS.Ctx;
+    }
+    bool operator!=(const LookupContext &RHS) const {
+      return Ctx != RHS.Ctx;
+    }
+  };
+
+  /// IdDeclInfo - Keeps track of information about decls associated to a
+  /// particular identifier. IdDeclInfos are lazily constructed and assigned
+  /// to an identifier the first time a decl with that identifier is shadowed
+  /// in some scope.
+  class IdDeclInfo {
+  public:
+    typedef llvm::SmallVector<NamedDecl*, 2> DeclsTy;
+
+    inline DeclsTy::iterator decls_begin() { return Decls.begin(); }
+    inline DeclsTy::iterator decls_end() { return Decls.end(); }
+
+    /// FindContext - Returns an iterator pointing just after the decl that is
+    /// in the given context or in a parent of it. The search is in reverse
+    /// order, from end to begin.
+    DeclsTy::iterator FindContext(const LookupContext &Ctx) {
+      return FindContext(Ctx, Decls.end());
+    }
+
+    /// FindContext - Returns an iterator pointing just after the decl that is
+    /// in the given context or in a parent of it. The search is in reverse
+    /// order, from end to begin.
+    DeclsTy::iterator FindContext(const LookupContext &Ctx,
+                                  const DeclsTy::iterator &Start) {
+      for (DeclsTy::iterator I = Start; I != Decls.begin(); --I) {
+        if (Ctx.isEqOrContainedBy(LookupContext(*(I-1))))
+          return I;
+      }
+
+      return Decls.begin();
+    }
+
+    /// iterator - Iterate over the decls by walking their parent contexts too.
+    class iterator {
+    public:
+      typedef DeclsTy::iterator BaseIter;
+
+      iterator(const BaseIter &DeclIt) : DI(DeclIt) {}
+      const BaseIter &getBase() { return DI; }
+
+      NamedDecl *&operator*() const {
+        return *(DI-1);
+      }
+      
+      bool operator==(const iterator &RHS) const {
+        return DI == RHS.DI;
+      }
+      bool operator!=(const iterator &RHS) const {
+        return DI != RHS.DI;
+      }
+      
+      // Preincrement.
+      iterator& operator++() {
+        NamedDecl *D = **this;
+        void *Ptr = D->getIdentifier()->getFETokenInfo<void>();
+        assert(!isDeclPtr(Ptr) && "Decl with wrong id ?");
+        DI = toIdDeclInfo(Ptr)->FindContext(LookupContext(D), DI-1);
+        return *this;
+      }
+
+    private:
+      BaseIter DI;
+    };
+
+    /// ctx_iterator - Iterator over the decls of a specific context only.
+    class ctx_iterator {
+    public:
+      typedef DeclsTy::iterator BaseIter;
+
+      ctx_iterator(const BaseIter &DeclIt) : DI(DeclIt) {}
+      const BaseIter &getBase() { return DI; }
+
+      NamedDecl *&operator*() const {
+        return *(DI-1);
+      }
+      
+      bool operator==(const ctx_iterator &RHS) const {
+        return DI == RHS.DI;
+      }
+      bool operator!=(const ctx_iterator &RHS) const {
+        return DI != RHS.DI;
+      }
+      
+      // Preincrement.
+      ctx_iterator& operator++() {
+        NamedDecl *D = **this;
+        void *Ptr = D->getIdentifier()->getFETokenInfo<void>();
+        assert(!isDeclPtr(Ptr) && "Decl with wrong id ?");
+        IdDeclInfo *Info = toIdDeclInfo(Ptr);
+        
+        --DI;
+        if (DI != Info->Decls.begin() &&
+            LookupContext(D) != LookupContext(**this))
+          DI = Info->Decls.begin();
+        return *this;
+      }
+
+    private:
+      BaseIter DI;
+    };
+
+    void AddDecl(NamedDecl *D) {
+      Decls.insert(FindContext(LookupContext(D)), D);
+    }
+
+    /// AddShadowed - Add a decl by putting it directly above the 'Shadow' decl.
+    /// Later lookups will find the 'Shadow' decl first. The 'Shadow' decl must
+    /// be already added to the scope chain and must be in the same context as
+    /// the decl that we want to add.
+    void AddShadowed(NamedDecl *D, NamedDecl *Shadow) {
+      assert(LookupContext(D) == LookupContext(Shadow) &&
+             "Decl and Shadow not in same context!");
+
+      for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
+        if (Shadow == *(I-1)) {
+          Decls.insert(I-1, D);
+          return;
+        }
+      }
+
+      assert(0 && "Shadow wasn't in scope chain!");
+    }
+
+    /// RemoveDecl - Remove the decl from the scope chain.
+    /// The decl must already be part of the decl chain.
+    void RemoveDecl(NamedDecl *D) {
+      for (DeclsTy::iterator I = Decls.end(); I != Decls.begin(); --I) {
+        if (D == *(I-1)) {
+          Decls.erase(I-1);
+          return;
+        }
+      }
+
+      assert(0 && "Didn't find this decl on its identifier's chain!");
+    }
+
+  private:
+    DeclsTy Decls;
+  };
+
+  /// SwizzledIterator - Can be instantiated either with a single NamedDecl*
+  /// (the common case where only one decl is associated with an identifier) or
+  /// with an 'Iter' iterator, when there are more than one decls to lookup.
+  template<typename Iter>
+  class SwizzledIterator {
+    uintptr_t Ptr;
+
+    SwizzledIterator() : Ptr(0) {}
+    SwizzledIterator(NamedDecl *D) {
+      Ptr = reinterpret_cast<uintptr_t>(D);
+    }
+    SwizzledIterator(Iter I) {
+      Ptr = reinterpret_cast<uintptr_t>(I.getBase()) | 0x1;
+    }
+
+    bool isIterator() const { return (Ptr & 0x1); }
+
+    Iter getIterator() const {
+      assert(isIterator() && "Ptr not an iterator.");
+      return reinterpret_cast<typename Iter::BaseIter>(Ptr & ~0x1);
+    }
+
+    friend class IdentifierResolver;
+  public:
+    NamedDecl *operator*() const {
+      if (isIterator())
+        return *getIterator();
+      else
+        return reinterpret_cast<NamedDecl*>(Ptr);
+    }
+    
+    bool operator==(const SwizzledIterator &RHS) const {
+      return Ptr == RHS.Ptr;
+    }
+    bool operator!=(const SwizzledIterator &RHS) const {
+      return Ptr != RHS.Ptr;
+    }
+
+    // Preincrement.
+    SwizzledIterator& operator++() {
+      if (isIterator()) {
+        Iter I = getIterator();
+        ++I;
+        Ptr = reinterpret_cast<uintptr_t>(I.getBase()) | 0x1;
+      }
+      else  // This is a single NamedDecl*.
+        Ptr = 0;
+
+      return *this;
+    }
+  };
+
 public:
-  IdentifierResolver();
-  ~IdentifierResolver();
+
+  typedef SwizzledIterator<IdDeclInfo::iterator> iterator;
+  typedef SwizzledIterator<IdDeclInfo::ctx_iterator> ctx_iterator;
+
+  /// begin - Returns an iterator for all decls, starting at the given
+  /// declaration context.
+  static iterator begin(const IdentifierInfo *II, DeclContext *Ctx);
+
+  static iterator end(const IdentifierInfo *II) {
+    void *Ptr = II->getFETokenInfo<void>();
+    if (!Ptr || isDeclPtr(Ptr))
+      return iterator();
+
+    IdDeclInfo *IDI = toIdDeclInfo(Ptr);
+    return iterator(IDI->decls_begin());
+  }
+
+  /// ctx_begin - Returns an iterator for only decls that belong to the given
+  /// declaration context.
+  static ctx_iterator ctx_begin(const IdentifierInfo *II, DeclContext *Ctx);
+
+  static ctx_iterator ctx_end(const IdentifierInfo *II) {
+    void *Ptr = II->getFETokenInfo<void>();
+    if (!Ptr || isDeclPtr(Ptr))
+      return ctx_iterator();
+
+    IdDeclInfo *IDI = toIdDeclInfo(Ptr);
+    return ctx_iterator(IDI->decls_begin());
+  }
+
+  /// isDeclInScope - If 'Ctx' is a function/method, isDeclInScope returns true

+  /// if 'D' is in Scope 'S', otherwise 'S' is ignored and isDeclInScope returns

+  /// true if 'D' belongs to the given declaration context.

+  static bool isDeclInScope(Decl *D, DeclContext *Ctx, Scope *S = 0) {
+    if (Ctx->isFunctionOrMethod())

+      return S->isDeclScope(D);

+

+    return LookupContext(D) == LookupContext(Ctx);
+  }
 
   /// AddDecl - Link the decl to its shadowed decl chain.
-  void AddDecl(NamedDecl *D, Scope *S);
+  void AddDecl(NamedDecl *D);
 
-  /// AddGlobalDecl - Link the decl at the top of the shadowed decl chain.
-  void AddGlobalDecl(NamedDecl *D);
+  /// AddShadowedDecl - Link the decl to its shadowed decl chain putting it
+  /// after the decl that the iterator points to, thus the 'CIT' decl will be
+  /// encountered before the 'D' decl.
+  void AddShadowedDecl(NamedDecl *D, NamedDecl *Shadow);
 
   /// RemoveDecl - Unlink the decl from its shadowed decl chain.
   /// The decl must already be part of the decl chain.
   void RemoveDecl(NamedDecl *D);
 
-  /// Lookup - Find the non-shadowed decl that belongs to one or more
-  /// of the specified Decl::IdentifierNamespaces.
-  NamedDecl *Lookup(const IdentifierInfo *II, unsigned NSI);
+  IdentifierResolver();
+  ~IdentifierResolver();
 
 private:
-  // An instance of IdDeclInfoMap class, that's hidden away in the
-  // implementation file.
-  void *IdDeclInfos;
+  class IdDeclInfoMap;
+  IdDeclInfoMap *IdDeclInfos;
+
+  /// Identifier's FETokenInfo contains a Decl pointer if lower bit == 0.
+  static inline bool isDeclPtr(void *Ptr) {
+    return (reinterpret_cast<uintptr_t>(Ptr) & 0x1) == 0;
+  }
+
+  /// Identifier's FETokenInfo contains a IdDeclInfo pointer if lower bit == 1.
+  static inline IdDeclInfo *toIdDeclInfo(void *Ptr) {
+    assert((reinterpret_cast<uintptr_t>(Ptr) & 0x1) == 1
+          && "Ptr not a IdDeclInfo* !");
+    return reinterpret_cast<IdDeclInfo*>(
+                    reinterpret_cast<uintptr_t>(Ptr) & ~0x1
+                                                            );
+  }
 };
 
 } // end namespace clang