Revamp our representation of C++ nested-name-specifiers. We now have a

uniqued representation that should both save some memory and make it
far easier to properly build canonical types for types involving
dependent nested-name-specifiers, e.g., "typename T::Nested::type".

This approach will greatly simplify the representation of
CXXScopeSpec. That'll be next.

llvm-svn: 67799

6 files changed, 149 insertions, 123 deletions

diff --git a/clang/lib/AST/ASTContext.cpp b/clang/lib/AST/ASTContext.cpp
index c656d966db3..84976a02944 100644
--- a/clang/lib/AST/ASTContext.cpp
+++ b/clang/lib/AST/ASTContext.cpp
@@ -33,9 +33,9 @@ ASTContext::ASTContext(const LangOptions& LOpts, SourceManager &SM,
                        TargetInfo &t,
                        IdentifierTable &idents, SelectorTable &sels,
                        bool FreeMem, unsigned size_reserve) : 
-  CFConstantStringTypeDecl(0), ObjCFastEnumerationStateTypeDecl(0),
-  SourceMgr(SM), LangOpts(LOpts), FreeMemory(FreeMem), Target(t), 
-  Idents(idents), Selectors(sels)
+  GlobalNestedNameSpecifier(0), CFConstantStringTypeDecl(0), 
+  ObjCFastEnumerationStateTypeDecl(0), SourceMgr(SM), LangOpts(LOpts), 
+  FreeMemory(FreeMem), Target(t), Idents(idents), Selectors(sels)
 {  
   if (size_reserve > 0) Types.reserve(size_reserve);    
   InitBuiltinTypes();
@@ -77,7 +77,18 @@ ASTContext::~ASTContext() {
     }
   }
 
+  // Destroy nested-name-specifiers.
+  for (llvm::FoldingSet<NestedNameSpecifier>::iterator 
+         NNS = NestedNameSpecifiers.begin(),
+         NNSEnd = NestedNameSpecifiers.end(); 
+       NNS != NNSEnd; ++NNS)
+    NNS->Destroy(*this);
+
+  if (GlobalNestedNameSpecifier)
+    GlobalNestedNameSpecifier->Destroy(*this);
+
   TUDecl->Destroy(*this);
+
 }
 
 void ASTContext::PrintStats() const {
@@ -1376,11 +1387,10 @@ ASTContext::getClassTemplateSpecializationType(TemplateDecl *Template,
 }
 
 QualType 
-ASTContext::getQualifiedNameType(const NestedNameSpecifier *Components,
-                                 unsigned NumComponents,
+ASTContext::getQualifiedNameType(NestedNameSpecifier *NNS,
                                  QualType NamedType) {
   llvm::FoldingSetNodeID ID;
-  QualifiedNameType::Profile(ID, Components, NumComponents, NamedType);
+  QualifiedNameType::Profile(ID, NNS, NamedType);
 
   void *InsertPos = 0;
   QualifiedNameType *T 
@@ -1388,11 +1398,8 @@ ASTContext::getQualifiedNameType(const NestedNameSpecifier *Components,
   if (T)
     return QualType(T, 0);
 
-  void *Mem = Allocate((sizeof(QualifiedNameType) +
-                        sizeof(NestedNameSpecifier) * NumComponents), 
-                       8);
-  T = new (Mem) QualifiedNameType(Components, NumComponents, NamedType,
-                                  getCanonicalType(NamedType));
+  T = new (*this) QualifiedNameType(NNS, NamedType, 
+                                    getCanonicalType(NamedType));
   Types.push_back(T);
   QualifiedNameTypes.InsertNode(T, InsertPos);
   return QualType(T, 0);
diff --git a/clang/lib/AST/ExprCXX.cpp b/clang/lib/AST/ExprCXX.cpp
index 5a9de19254d..c2fcc5f9ee4 100644
--- a/clang/lib/AST/ExprCXX.cpp
+++ b/clang/lib/AST/ExprCXX.cpp
@@ -24,54 +24,6 @@ void CXXConditionDeclExpr::Destroy(ASTContext& C) {
   C.Deallocate(this);
 }
 
-QualifiedDeclRefExpr::QualifiedDeclRefExpr(NamedDecl *d, QualType t, 
-                                           SourceLocation l, bool TD, 
-                                           bool VD, SourceRange R,
-                                       const NestedNameSpecifier *Components,
-                                           unsigned NumComponents)
-  : DeclRefExpr(QualifiedDeclRefExprClass, d, t, l, TD, VD), 
-    QualifierRange(R), NumComponents(NumComponents) {
-  NestedNameSpecifier *Data 
-    = reinterpret_cast<NestedNameSpecifier *>(this + 1);
-  for (unsigned I = 0; I < NumComponents; ++I)
-    Data[I] = Components[I];
-}
-
-QualifiedDeclRefExpr *
-QualifiedDeclRefExpr::Create(ASTContext &Context, NamedDecl *d, QualType t, 
-                             SourceLocation l, bool TD, 
-                             bool VD, SourceRange R,
-                             const NestedNameSpecifier *Components,
-                             unsigned NumComponents) {
-  void *Mem = Context.Allocate((sizeof(QualifiedDeclRefExpr) +
-                                sizeof(NestedNameSpecifier) * NumComponents));
-  return new (Mem) QualifiedDeclRefExpr(d, t, l, TD, VD, R, Components, 
-                                        NumComponents);
-}
-
-UnresolvedDeclRefExpr::UnresolvedDeclRefExpr(DeclarationName N, QualType T,
-                                             SourceLocation L, SourceRange R,
-                                       const NestedNameSpecifier *Components,
-                                             unsigned NumComponents)
-  : Expr(UnresolvedDeclRefExprClass, T, true, true), 
-    Name(N), Loc(L), QualifierRange(R), NumComponents(NumComponents) {
-  NestedNameSpecifier *Data 
-    = reinterpret_cast<NestedNameSpecifier *>(this + 1);
-  for (unsigned I = 0; I < NumComponents; ++I)
-    Data[I] = Components[I];
-}
-
-UnresolvedDeclRefExpr *
-UnresolvedDeclRefExpr::Create(ASTContext &Context, DeclarationName N,
-                              SourceLocation L, SourceRange R,
-                              const NestedNameSpecifier *Components,
-                              unsigned NumComponents) {
-  void *Mem = Context.Allocate((sizeof(UnresolvedDeclRefExpr) +
-                                sizeof(NestedNameSpecifier) * NumComponents));
-  return new (Mem) UnresolvedDeclRefExpr(N, Context.DependentTy, L, R, 
-                                         Components, NumComponents);
-}
-
 //===----------------------------------------------------------------------===//
 //  Child Iterators for iterating over subexpressions/substatements
 //===----------------------------------------------------------------------===//
diff --git a/clang/lib/AST/NestedNameSpecifier.cpp b/clang/lib/AST/NestedNameSpecifier.cpp
index ea4b506e640..62e972efd57 100644
--- a/clang/lib/AST/NestedNameSpecifier.cpp
+++ b/clang/lib/AST/NestedNameSpecifier.cpp
@@ -16,46 +16,137 @@
 #include "clang/AST/Decl.h"
 #include "clang/AST/Type.h"
 #include "llvm/Support/raw_ostream.h"
+#include <cassert>
 
 using namespace clang;
 
-DeclContext *
-NestedNameSpecifier::computeDeclContext(ASTContext &Context) const {
-  // The simple case: we're storing a DeclContext
-  if ((Data & 0x01) == 0)
-    return reinterpret_cast<DeclContext *>(Data);
-
-  Type *T = getAsType();
-  if (!T)
-    return 0;
-
-  // Retrieve the DeclContext associated with this type.
-  const TagType *TagT = T->getAsTagType();
-  assert(TagT && "No DeclContext from a non-tag type");
-  return TagT->getDecl();
-}
-
-void NestedNameSpecifier::Print(llvm::raw_ostream &OS, 
-                                const NestedNameSpecifier *First,
-                                const NestedNameSpecifier *Last) {
-  for (; First != Last; ++First) {
-    if (Type *T = First->getAsType()) {
-      std::string TypeStr;
-
-      // If this is a qualified name type, suppress the qualification:
-      // it's part of our nested-name-specifier sequence anyway.
-      if (const QualifiedNameType *QualT = dyn_cast<QualifiedNameType>(T))
-        T = QualT->getNamedType().getTypePtr();
-
-      if (const TagType *TagT = dyn_cast<TagType>(T))
-        TagT->getAsStringInternal(TypeStr, true);
-      else
-        T->getAsStringInternal(TypeStr);
-      OS << TypeStr;
-    } else if (NamedDecl *NamedDC 
-                 = dyn_cast_or_null<NamedDecl>(First->getAsDeclContext()))
-      OS << NamedDC->getNameAsString();
+NestedNameSpecifier *
+NestedNameSpecifier::FindOrInsert(ASTContext &Context, 
+                                  const NestedNameSpecifier &Mockup) {
+  llvm::FoldingSetNodeID ID;
+  Mockup.Profile(ID);
+
+  void *InsertPos = 0;
+  NestedNameSpecifier *NNS 
+    = Context.NestedNameSpecifiers.FindNodeOrInsertPos(ID, InsertPos);
+  if (!NNS) {
+    NNS = new (Context) NestedNameSpecifier(Mockup);
+    Context.NestedNameSpecifiers.InsertNode(NNS, InsertPos);
+  }
+
+  return NNS;
+}
+
+NestedNameSpecifier *
+NestedNameSpecifier::Create(ASTContext &Context, NestedNameSpecifier *Prefix, 
+                            IdentifierInfo *II) {
+  assert(II && "Identifier cannot be NULL");
+  assert(Prefix && Prefix->isDependent() && "Prefix must be dependent");
+
+  NestedNameSpecifier Mockup;
+  Mockup.Prefix = Prefix;
+  Mockup.Specifier.setPointer(II);
+  Mockup.Specifier.setInt(Identifier);
+  return FindOrInsert(Context, Mockup);
+}
+
+NestedNameSpecifier *
+NestedNameSpecifier::Create(ASTContext &Context, NestedNameSpecifier *Prefix, 
+                            NamespaceDecl *NS) {
+  assert(NS && "Namespace cannot be NULL");
+  assert((!Prefix || 
+          (Prefix->getAsType() == 0 && Prefix->getAsIdentifier() == 0)) &&
+         "Broken nested name specifier");
+  NestedNameSpecifier Mockup;
+  Mockup.Prefix = Prefix;
+  Mockup.Specifier.setPointer(NS);
+  Mockup.Specifier.setInt(Namespace);
+  return FindOrInsert(Context, Mockup);
+}
+
+NestedNameSpecifier *
+NestedNameSpecifier::Create(ASTContext &Context, NestedNameSpecifier *Prefix,
+                            bool Template, Type *T) {
+  assert(T && "Type cannot be NULL");
+  NestedNameSpecifier Mockup;
+  Mockup.Prefix = Prefix;
+  Mockup.Specifier.setPointer(T);
+  Mockup.Specifier.setInt(Template? TypeSpecWithTemplate : TypeSpec);
+  return FindOrInsert(Context, Mockup);
+}
   
-    OS <<  "::";
+NestedNameSpecifier *NestedNameSpecifier::GlobalSpecifier(ASTContext &Context) {
+  if (!Context.GlobalNestedNameSpecifier)
+    Context.GlobalNestedNameSpecifier = new (Context) NestedNameSpecifier();
+  return Context.GlobalNestedNameSpecifier;
+}
+
+/// \brief Whether this nested name specifier refers to a dependent
+/// type or not.
+bool NestedNameSpecifier::isDependent() const {
+  switch (getKind()) {
+  case Identifier:
+    // Identifier specifiers always represent dependent types
+    return true;
+
+  case Namespace:
+  case Global:
+    return false;
+
+  case TypeSpec:
+  case TypeSpecWithTemplate:
+    return getAsType()->isDependentType();
   }
+
+  // Necessary to suppress a GCC warning.
+  return false;
+}
+
+/// \brief Print this nested name specifier to the given output
+/// stream.
+void NestedNameSpecifier::Print(llvm::raw_ostream &OS) const {
+  if (Prefix)
+    Prefix->Print(OS);
+
+  switch (getKind()) {
+  case Identifier:
+    OS << getAsIdentifier()->getName();
+    break;
+
+  case Namespace:
+    OS << getAsNamespace()->getIdentifier()->getName();
+    break;
+
+  case Global:
+    break;
+
+  case TypeSpecWithTemplate:
+    OS << "template ";
+    // Fall through to print the type.
+
+  case TypeSpec: {
+    std::string TypeStr;
+    Type *T = getAsType();
+
+    // If this is a qualified name type, suppress the qualification:
+    // it's part of our nested-name-specifier sequence anyway.  FIXME:
+    // We should be able to assert that this doesn't happen.
+    if (const QualifiedNameType *QualT = dyn_cast<QualifiedNameType>(T))
+      T = QualT->getNamedType().getTypePtr();
+    
+    if (const TagType *TagT = dyn_cast<TagType>(T))
+      TagT->getAsStringInternal(TypeStr, true);
+    else
+      T->getAsStringInternal(TypeStr);
+    OS << TypeStr;
+    break;
+  }
+  }
+
+  OS << "::";
+}
+
+void NestedNameSpecifier::Destroy(ASTContext &Context) {
+  this->~NestedNameSpecifier();
+  Context.Deallocate((void *)this);
 }
diff --git a/clang/lib/AST/StmtPrinter.cpp b/clang/lib/AST/StmtPrinter.cpp
index 60300ba04ea..bd5e22491e6 100644
--- a/clang/lib/AST/StmtPrinter.cpp
+++ b/clang/lib/AST/StmtPrinter.cpp
@@ -533,12 +533,12 @@ void StmtPrinter::VisitDeclRefExpr(DeclRefExpr *Node) {
 void StmtPrinter::VisitQualifiedDeclRefExpr(QualifiedDeclRefExpr *Node) {  
   NamedDecl *D = Node->getDecl();
 
-  NestedNameSpecifier::Print(OS, Node->begin(), Node->end());
+  Node->getQualifier()->Print(OS);
   OS << D->getNameAsString();
 }
 
 void StmtPrinter::VisitUnresolvedDeclRefExpr(UnresolvedDeclRefExpr *Node) {  
-  NestedNameSpecifier::Print(OS, Node->begin(), Node->end());
+  Node->getQualifier()->Print(OS);
   OS << Node->getDeclName().getAsString();
 }
 
diff --git a/clang/lib/AST/Type.cpp b/clang/lib/AST/Type.cpp
index 19a3f144234..103c0a91345 100644
--- a/clang/lib/AST/Type.cpp
+++ b/clang/lib/AST/Type.cpp
@@ -1047,28 +1047,6 @@ ClassTemplateSpecializationType::Profile(llvm::FoldingSetNodeID &ID,
     Args[Idx].Profile(ID);
 }
 
-QualifiedNameType::QualifiedNameType(const NestedNameSpecifier *Components,
-                                     unsigned NumComponents, 
-                                     QualType NamedType,
-                                     QualType CanonType)
-  : Type(QualifiedName, CanonType, NamedType->isDependentType()),
-    NumComponents(NumComponents), NamedType(NamedType) {
-  NestedNameSpecifier *InitComponents 
-    = reinterpret_cast<NestedNameSpecifier *>(this + 1);
-  for (unsigned I = 0; I < NumComponents; ++I)
-    new (InitComponents + I) NestedNameSpecifier(Components[I]);
-}
-
-void QualifiedNameType::Profile(llvm::FoldingSetNodeID &ID, 
-                                const NestedNameSpecifier *Components,
-                                unsigned NumComponents, 
-                                QualType NamedType) {
-  ID.AddInteger(NumComponents);
-  for (unsigned I = 0; I < NumComponents; ++I)
-    ID.AddPointer(Components[I].getAsOpaquePtr());
-  NamedType.Profile(ID);
-}
-
 //===----------------------------------------------------------------------===//
 // Type Printing
 //===----------------------------------------------------------------------===//
@@ -1440,7 +1418,7 @@ void QualifiedNameType::getAsStringInternal(std::string &InnerString) const {
 
   {
     llvm::raw_string_ostream OS(MyString);
-    NestedNameSpecifier::Print(OS, begin(), end());
+    NNS->Print(OS);
   }
   
   std::string TypeStr;
diff --git a/clang/lib/AST/TypeSerialization.cpp b/clang/lib/AST/TypeSerialization.cpp
index 6f93a1859fe..4490847a562 100644
--- a/clang/lib/AST/TypeSerialization.cpp
+++ b/clang/lib/AST/TypeSerialization.cpp
@@ -421,9 +421,7 @@ CreateImpl(ASTContext& Context, Deserializer& D) {
 // QualifiedNameType
 //===----------------------------------------------------------------------===//
 void QualifiedNameType::EmitImpl(llvm::Serializer& S) const {
-  S.EmitInt(NumComponents);
   // FIXME: Serialize the actual components
-  S.Emit(NamedType);
 }
 
 Type*