Unifies the name-lookup mechanisms used in various parts of the AST

and separates lexical name lookup from qualified name lookup. In
particular:
  * Make DeclContext the central data structure for storing and
    looking up declarations within existing declarations, e.g., members
    of structs/unions/classes, enumerators in C++0x enums, members of
    C++ namespaces, and (later) members of Objective-C
    interfaces/implementations. DeclContext uses a lazily-constructed
    data structure optimized for fast lookup (array for small contexts,
    hash table for larger contexts). 

  * Implement C++ qualified name lookup in terms of lookup into
    DeclContext.

  * Implement C++ unqualified name lookup in terms of
    qualified+unqualified name lookup (since unqualified lookup is not
    purely lexical in C++!)

  * Limit the use of the chains of declarations stored in
    IdentifierInfo to those names declared lexically.

  * Eliminate CXXFieldDecl, collapsing its behavior into
    FieldDecl. (FieldDecl is now a ScopedDecl).

  * Make RecordDecl into a DeclContext and eliminates its
    Members/NumMembers fields (since one can just iterate through the
    DeclContext to get the fields).

llvm-svn: 60878

9 files changed, 393 insertions, 128 deletions

diff --git a/clang/lib/AST/ASTContext.cpp b/clang/lib/AST/ASTContext.cpp
index 044106300cb..3455504fdb1 100644
--- a/clang/lib/AST/ASTContext.cpp
+++ b/clang/lib/AST/ASTContext.cpp
@@ -539,7 +539,7 @@ const ASTRecordLayout &ASTContext::getASTRecordLayout(const RecordDecl *D) {
   ASTRecordLayout *NewEntry = new ASTRecordLayout();
   Entry = NewEntry;
 
-  NewEntry->InitializeLayout(D->getNumMembers());
+  NewEntry->InitializeLayout(std::distance(D->field_begin(), D->field_end()));
   bool IsUnion = D->isUnion();
 
   unsigned StructPacking = 0;
@@ -552,10 +552,11 @@ const ASTRecordLayout &ASTContext::getASTRecordLayout(const RecordDecl *D) {
 
   // Layout each field, for now, just sequentially, respecting alignment.  In
   // the future, this will need to be tweakable by targets.
-  for (unsigned i = 0, e = D->getNumMembers(); i != e; ++i) {
-    const FieldDecl *FD = D->getMember(i);
-    NewEntry->LayoutField(FD, i, IsUnion, StructPacking, *this);
-  }
+  unsigned FieldIdx = 0;
+  for (RecordDecl::field_iterator Field = D->field_begin(),
+                               FieldEnd = D->field_end();
+       Field != FieldEnd; (void)++Field, ++FieldIdx)
+    NewEntry->LayoutField(*Field, FieldIdx, IsUnion, StructPacking, *this);
 
   // Finally, round the size of the total struct up to the alignment of the
   // struct itself.
@@ -996,12 +997,16 @@ QualType ASTContext::getTypeDeclType(TypeDecl *Decl, TypeDecl* PrevDecl) {
   return QualType(Decl->TypeForDecl, 0);
 }
 
-/// setTagDefinition - Used by RecordDecl::defineBody to inform ASTContext
-///  about which RecordDecl serves as the definition of a particular
-///  struct/union/class.  This will eventually be used by enums as well.
+/// setTagDefinition - Used by RecordDecl::completeDefinition and
+/// EnumDecl::completeDefinition to inform about which
+/// RecordDecl/EnumDecl serves as the definition of a particular
+/// struct/union/class/enum.
 void ASTContext::setTagDefinition(TagDecl* D) {
   assert (D->isDefinition());
-  cast<TagType>(D->TypeForDecl)->decl = D;  
+  if (!D->TypeForDecl)
+    getTypeDeclType(D);
+  else
+    cast<TagType>(D->TypeForDecl)->decl = D;  
 }
 
 /// getTypedefType - Return the unique reference to the type for the
@@ -1460,14 +1465,17 @@ QualType ASTContext::getCFConstantStringType() {
     FieldTypes[2] = getPointerType(CharTy.getQualifiedType(QualType::Const));  
     // long length;
     FieldTypes[3] = LongTy;  
-    // Create fields
-    FieldDecl *FieldDecls[4];
-  
-    for (unsigned i = 0; i < 4; ++i)
-      FieldDecls[i] = FieldDecl::Create(*this, SourceLocation(), 0,
-                                        FieldTypes[i]);
   
-    CFConstantStringTypeDecl->defineBody(*this, FieldDecls, 4);
+    // Create fields
+    for (unsigned i = 0; i < 4; ++i) {
+      FieldDecl *Field = FieldDecl::Create(*this, CFConstantStringTypeDecl, 
+                                           SourceLocation(), 0,
+                                           FieldTypes[i], /*BitWidth=*/0, 
+                                           /*Mutable=*/false, /*PrevDecl=*/0);
+      CFConstantStringTypeDecl->addDecl(*this, Field, true);
+    }
+
+    CFConstantStringTypeDecl->completeDefinition(*this);
   }
   
   return getTagDeclType(CFConstantStringTypeDecl);
@@ -1476,6 +1484,10 @@ QualType ASTContext::getCFConstantStringType() {
 QualType ASTContext::getObjCFastEnumerationStateType()
 {
   if (!ObjCFastEnumerationStateTypeDecl) {
+    ObjCFastEnumerationStateTypeDecl =
+      RecordDecl::Create(*this, TagDecl::TK_struct, TUDecl, SourceLocation(),
+                         &Idents.get("__objcFastEnumerationState"));
+    
     QualType FieldTypes[] = {
       UnsignedLongTy,
       getPointerType(ObjCIdType),
@@ -1484,16 +1496,16 @@ QualType ASTContext::getObjCFastEnumerationStateType()
                            llvm::APInt(32, 5), ArrayType::Normal, 0)
     };
     
-    FieldDecl *FieldDecls[4];
-    for (size_t i = 0; i < 4; ++i)
-      FieldDecls[i] = FieldDecl::Create(*this, SourceLocation(), 0, 
-                                        FieldTypes[i]);
-    
-    ObjCFastEnumerationStateTypeDecl =
-      RecordDecl::Create(*this, TagDecl::TK_struct, TUDecl, SourceLocation(),
-                         &Idents.get("__objcFastEnumerationState"));
+    for (size_t i = 0; i < 4; ++i) {
+      FieldDecl *Field = FieldDecl::Create(*this, 
+                                           ObjCFastEnumerationStateTypeDecl, 
+                                           SourceLocation(), 0, 
+                                           FieldTypes[i], /*BitWidth=*/0, 
+                                           /*Mutable=*/false, /*PrevDecl=*/0);
+      ObjCFastEnumerationStateTypeDecl->addDecl(*this, Field, true);
+    }
     
-    ObjCFastEnumerationStateTypeDecl->defineBody(*this, FieldDecls, 4);
+    ObjCFastEnumerationStateTypeDecl->completeDefinition(*this);
   }
   
   return getTagDeclType(ObjCFastEnumerationStateTypeDecl);
@@ -1745,16 +1757,17 @@ void ASTContext::getObjCEncodingForTypeImpl(QualType T, std::string& S,
     }
     if (ExpandStructures) {
       S += '=';
-      for (int i = 0; i < RDecl->getNumMembers(); i++) {
-        FieldDecl *FD = RDecl->getMember(i);
+      for (RecordDecl::field_iterator Field = RDecl->field_begin(),
+                                   FieldEnd = RDecl->field_end();
+           Field != FieldEnd; ++Field) {
         if (NameFields) {
           S += '"';
-          S += FD->getNameAsString();
+          S += Field->getNameAsString();
           S += '"';
         }
         
         // Special case bit-fields.
-        if (const Expr *E = FD->getBitWidth()) {
+        if (const Expr *E = Field->getBitWidth()) {
           // FIXME: Fix constness.
           ASTContext *Ctx = const_cast<ASTContext*>(this);
           unsigned N = E->getIntegerConstantExprValue(*Ctx).getZExtValue();
@@ -1763,7 +1776,8 @@ void ASTContext::getObjCEncodingForTypeImpl(QualType T, std::string& S,
           S += 'b';
           S += llvm::utostr(N);
         } else {
-          getObjCEncodingForTypeImpl(FD->getType(), S, false, true, NameFields);
+          getObjCEncodingForTypeImpl(Field->getType(), S, false, true, 
+                                     NameFields);
         }
       }
     }
diff --git a/clang/lib/AST/Decl.cpp b/clang/lib/AST/Decl.cpp
index 194f47f96c4..7643e4eda87 100644
--- a/clang/lib/AST/Decl.cpp
+++ b/clang/lib/AST/Decl.cpp
@@ -81,10 +81,11 @@ BlockDecl *BlockDecl::Create(ASTContext &C, DeclContext *DC, SourceLocation L) {
   return new (Mem) BlockDecl(DC, L);
 }
 
-FieldDecl *FieldDecl::Create(ASTContext &C, SourceLocation L,
-                             IdentifierInfo *Id, QualType T, Expr *BW) {
+FieldDecl *FieldDecl::Create(ASTContext &C, DeclContext *DC, SourceLocation L,
+                             IdentifierInfo *Id, QualType T, Expr *BW,
+                             bool Mutable, ScopedDecl *PrevDecl) {
   void *Mem = C.getAllocator().Allocate<FieldDecl>();
-  return new (Mem) FieldDecl(L, Id, T, BW);
+  return new (Mem) FieldDecl(Decl::Field, DC, L, Id, T, BW, Mutable, PrevDecl);
 }
 
 
@@ -118,10 +119,21 @@ EnumDecl *EnumDecl::Create(ASTContext &C, DeclContext *DC, SourceLocation L,
 }
 
 void EnumDecl::Destroy(ASTContext& C) {
-  if (getEnumConstantList()) getEnumConstantList()->Destroy(C);
+  DeclContext::DestroyDecls(C);
   Decl::Destroy(C);
 }
 
+void EnumDecl::completeDefinition(ASTContext &C, QualType NewType) {
+  assert(!isDefinition() && "Cannot redefine enums!");
+  setDefinition(true);
+
+  IntegerType = NewType;
+
+  // Let ASTContext know that this is the defining EnumDecl for this
+  // type.
+  C.setTagDefinition(this);
+}
+
 FileScopeAsmDecl *FileScopeAsmDecl::Create(ASTContext &C,
                                            SourceLocation L,
                                            StringLiteral *Str) {
@@ -248,12 +260,10 @@ TagDecl* TagDecl::getDefinition(ASTContext& C) const {
 
 RecordDecl::RecordDecl(Kind DK, TagKind TK, DeclContext *DC, SourceLocation L,
                        IdentifierInfo *Id)
-: TagDecl(DK, TK, DC, L, Id, 0) {
+  : TagDecl(DK, TK, DC, L, Id, 0), DeclContext(DK) {
   
   HasFlexibleArrayMember = false;
   assert(classof(static_cast<Decl*>(this)) && "Invalid Kind!");
-  Members = 0;
-  NumMembers = -1;  
 }
 
 RecordDecl *RecordDecl::Create(ASTContext &C, TagKind TK, DeclContext *DC,
@@ -267,46 +277,25 @@ RecordDecl *RecordDecl::Create(ASTContext &C, TagKind TK, DeclContext *DC,
 }
 
 RecordDecl::~RecordDecl() {
-  delete[] Members;
 }
 
 void RecordDecl::Destroy(ASTContext& C) {
-  if (isDefinition())
-    for (field_iterator I=field_begin(), E=field_end(); I!=E; ++I)
-      (*I)->Destroy(C);
-
+  DeclContext::DestroyDecls(C);
   TagDecl::Destroy(C);
 }
 
-/// defineBody - When created, RecordDecl's correspond to a forward declared
-/// record.  This method is used to mark the decl as being defined, with the
-/// specified contents.
-void RecordDecl::defineBody(ASTContext& C, FieldDecl **members,
-                            unsigned numMembers) {
+/// completeDefinition - Notes that the definition of this type is now
+/// complete.
+void RecordDecl::completeDefinition(ASTContext& C) {
   assert(!isDefinition() && "Cannot redefine record!");
+
   setDefinition(true);
-  NumMembers = numMembers;
-  if (numMembers) {
-    Members = new FieldDecl*[numMembers];
-    memcpy(Members, members, numMembers*sizeof(Decl*));
-  }
   
-  // Let ASTContext know that this is the defining RecordDecl this type.
+  // Let ASTContext know that this is the defining RecordDecl for this
+  // type.
   C.setTagDefinition(this);
 }
 
-
-FieldDecl *RecordDecl::getMember(IdentifierInfo *II) {
-  if (Members == 0 || NumMembers < 0)
-    return 0;
-  
-  // Linear search.  When C++ classes come along, will likely need to revisit.
-  for (int i = 0; i != NumMembers; ++i)
-    if (Members[i]->getIdentifier() == II)
-      return Members[i];
-  return 0;
-}
-
 //===----------------------------------------------------------------------===//
 // BlockDecl Implementation
 //===----------------------------------------------------------------------===//
diff --git a/clang/lib/AST/DeclBase.cpp b/clang/lib/AST/DeclBase.cpp
index 7b5df1c1945..3e0f158cbe1 100644
--- a/clang/lib/AST/DeclBase.cpp
+++ b/clang/lib/AST/DeclBase.cpp
@@ -15,6 +15,7 @@
 #include "clang/AST/DeclObjC.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/ASTContext.h"
+#include "clang/AST/Type.h"
 #include "llvm/ADT/DenseMap.h"
 using namespace clang;
 
@@ -34,7 +35,6 @@ static unsigned nNamespaces = 0;
 static unsigned nOverFuncs = 0;
 static unsigned nTypedef = 0;
 static unsigned nFieldDecls = 0;
-static unsigned nCXXFieldDecls = 0;
 static unsigned nInterfaceDecls = 0;
 static unsigned nClassDecls = 0;
 static unsigned nMethodDecls = 0;
@@ -95,7 +95,7 @@ bool Decl::CollectingStats(bool Enable) {
 void Decl::PrintStats() {
   fprintf(stderr, "*** Decl Stats:\n");
   fprintf(stderr, "  %d decls total.\n", 
-          int(nFuncs+nVars+nParmVars+nFieldDecls+nSUC+nCXXFieldDecls+nCXXSUC+
+          int(nFuncs+nVars+nParmVars+nFieldDecls+nSUC+nCXXSUC+
               nEnumDecls+nEnumConst+nTypedef+nInterfaceDecls+nClassDecls+
               nMethodDecls+nProtocolDecls+nCategoryDecls+nIvarDecls+
               nAtDefsFieldDecls+nNamespaces+nOverFuncs));
@@ -122,9 +122,6 @@ void Decl::PrintStats() {
   fprintf(stderr, "    %d struct/union/class decls, %d each (%d bytes)\n", 
           nSUC, (int)sizeof(RecordDecl),
           int(nSUC*sizeof(RecordDecl)));
-  fprintf(stderr, "    %d C++ field decls, %d each (%d bytes)\n", 
-          nCXXFieldDecls, (int)sizeof(CXXFieldDecl),
-          int(nCXXFieldDecls*sizeof(CXXFieldDecl)));
   fprintf(stderr, "    %d C++ struct/union/class decls, %d each (%d bytes)\n", 
           nCXXSUC, (int)sizeof(CXXRecordDecl),
           int(nCXXSUC*sizeof(CXXRecordDecl)));
@@ -183,7 +180,7 @@ void Decl::PrintStats() {
           int(nFuncs*sizeof(FunctionDecl)+
               nVars*sizeof(VarDecl)+nParmVars*sizeof(ParmVarDecl)+
               nFieldDecls*sizeof(FieldDecl)+nSUC*sizeof(RecordDecl)+
-              nCXXFieldDecls*sizeof(CXXFieldDecl)+nCXXSUC*sizeof(CXXRecordDecl)+
+              nCXXSUC*sizeof(CXXRecordDecl)+
               nEnumDecls*sizeof(EnumDecl)+nEnumConst*sizeof(EnumConstantDecl)+
               nTypedef*sizeof(TypedefDecl)+
               nInterfaceDecls*sizeof(ObjCInterfaceDecl)+
@@ -236,7 +233,6 @@ void Decl::addDeclKind(Kind k) {
   case ImplicitParam:
   case TranslationUnit:     break;
 
-  case CXXField:            nCXXFieldDecls++; break;
   case CXXRecord:           nCXXSUC++; break;
   // FIXME: Statistics for C++ decls.
   case TemplateTypeParm:
@@ -372,3 +368,269 @@ const DeclContext *DeclContext::getLexicalParent() const {
     return SD->getLexicalDeclContext();
   return getParent();
 }
+
+/// TwoNamedDecls - Stores up to two NamedDecls. The first
+/// declaration, if any, is in the ordinary identifier namespace, and
+/// corresponds to values (functions, variables, etc.). The second
+/// declaration, if any, is in the tag identifier namespace, and
+/// corresponds to tag types (classes, enums).
+struct TwoNamedDecls {
+  NamedDecl* Decls[2];
+};
+
+// FIXME: We really want to use a DenseSet here to eliminate the
+// redundant storage of the declaration names, but (1) it doesn't give
+// us the ability to search based on DeclarationName, (2) we really
+// need something more like a DenseMultiSet, and (3) it's
+// implemented in terms of DenseMap anyway.
+typedef llvm::DenseMap<DeclarationName, TwoNamedDecls> StoredDeclsMap;
+
+DeclContext::~DeclContext() {
+  unsigned Size = LookupPtr.getInt();
+  if (Size == LookupIsMap) {
+    StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
+    delete Map;
+  } else {
+    NamedDecl **Array = static_cast<NamedDecl**>(LookupPtr.getPointer());
+    delete [] Array;
+  }
+}
+
+void DeclContext::DestroyDecls(ASTContext &C) {
+  for (decl_iterator D = Decls.begin(); D != Decls.end(); ++D) {
+    if ((*D)->getLexicalDeclContext() == this)
+      (*D)->Destroy(C);
+  }
+}
+
+DeclContext *DeclContext::getPrimaryContext(ASTContext &Context) {
+  switch (DeclKind) {
+  case Decl::Block:
+  case Decl::TranslationUnit:
+    // There is only one DeclContext for these entities.
+    return this;
+
+  case Decl::Namespace:
+    // The original namespace is our primary context.
+    return static_cast<NamespaceDecl*>(this)->getOriginalNamespace();
+
+  case Decl::Enum:
+    // The declaration associated with the enumeration type is our
+    // primary context.
+    return Context.getTypeDeclType(static_cast<EnumDecl*>(this))
+             ->getAsEnumType()->getDecl();
+
+  case Decl::Record:
+  case Decl::CXXRecord: {
+    // The declaration associated with the type is be our primary
+    // context. 
+#if 0
+    // FIXME: This is what we expect to do. However, it doesn't work
+    // because ASTContext::setTagDefinition changes the result of
+    // Context.getTypeDeclType, meaning that our "primary" declaration
+    // of a RecordDecl/CXXRecordDecl will change, and we won't be able
+    // to find any values inserted into the earlier "primary"
+    // declaration. We need better tracking of redeclarations and
+    // definitions.
+    QualType Type = Context.getTypeDeclType(static_cast<RecordDecl*>(this));
+    return Type->getAsRecordType()->getDecl();
+#else
+    // FIXME: This hack will work for now, because the declaration we
+    // create when we're defining the record is the one we'll use as
+    // the definition later.
+    return this;
+#endif
+  }
+
+  case Decl::ObjCMethod:
+    return this;
+
+  case Decl::ObjCInterface:
+    // FIXME: Can Objective-C interfaces be forward-declared?
+    return this;
+
+  default:
+    assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast &&
+          "Unknown DeclContext kind");
+    return this;
+  }
+}
+
+DeclContext *DeclContext::getNextContext() {
+  switch (DeclKind) {
+  case Decl::Block:
+  case Decl::TranslationUnit:
+  case Decl::Enum:
+  case Decl::Record:
+  case Decl::CXXRecord:
+  case Decl::ObjCMethod:
+  case Decl::ObjCInterface:
+    // There is only one DeclContext for these entities.
+    return 0;
+
+  case Decl::Namespace:
+    // Return the next namespace
+    return static_cast<NamespaceDecl*>(this)->getNextNamespace();
+
+  default:
+    assert(DeclKind >= Decl::FunctionFirst && DeclKind <= Decl::FunctionLast &&
+          "Unknown DeclContext kind");
+    return 0;
+  }
+}
+
+void DeclContext::addDecl(ASTContext &Context, ScopedDecl *D, bool AllowLookup) {
+  Decls.push_back(D);
+  if (AllowLookup)
+    D->getDeclContext()->insert(Context, D);
+}
+
+DeclContext::lookup_result 
+DeclContext::lookup(ASTContext &Context, DeclarationName Name) {
+  DeclContext *PrimaryContext = getPrimaryContext(Context);
+  if (PrimaryContext != this)
+    return PrimaryContext->lookup(Context, Name);
+
+  /// If there is no lookup data structure, build one now by talking
+  /// all of the linked DeclContexts (in declaration order!) and
+  /// inserting their values.
+  if (LookupPtr.getPointer() == 0) {
+    for (DeclContext *DCtx = this; DCtx; DCtx = DCtx->getNextContext())
+      for (decl_iterator D = DCtx->decls_begin(); D != DCtx->decls_end(); ++D)
+        insertImpl(*D);
+  }
+
+  lookup_result Result(0, 0);
+  if (isLookupMap()) {
+    StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
+    StoredDeclsMap::iterator Pos = Map->find(Name);
+    if (Pos != Map->end()) {
+      Result.first = Pos->second.Decls[0]? &Pos->second.Decls[0] 
+                                        : &Pos->second.Decls[1];
+      Result.second = Pos->second.Decls[1]? &Pos->second.Decls[2]
+                                         : &Pos->second.Decls[1];
+    }
+    return Result;
+  } 
+
+  // We have a small array. Look into it.
+  unsigned Size = LookupPtr.getInt();
+  NamedDecl **Array = static_cast<NamedDecl**>(LookupPtr.getPointer());
+  for (unsigned Idx = 0; Idx < Size; ++Idx)
+    if (Array[Idx]->getDeclName() == Name) {
+      Result.first = &Array[Idx];
+      Result.second = Result.first + 1;
+      if (Idx + 1 < Size && Array[Idx + 1]->getDeclName() == Name)
+        ++Result.second;
+      break;
+    }
+
+  return Result;
+}
+
+DeclContext::lookup_const_result 
+DeclContext::lookup(ASTContext &Context, DeclarationName Name) const {
+  return const_cast<DeclContext*>(this)->lookup(Context, Name);
+}
+
+void DeclContext::insert(ASTContext &Context, NamedDecl *D) {
+  DeclContext *PrimaryContext = getPrimaryContext(Context);
+  if (PrimaryContext != this) {
+    PrimaryContext->insert(Context, D);
+    return;
+  }
+
+  // If we already have a lookup data structure, perform the insertion
+  // into it. Otherwise, be lazy and don't build that structure until
+  // someone asks for it.
+  if (LookupPtr.getPointer())
+    insertImpl(D);
+}
+
+void DeclContext::insertImpl(NamedDecl *D) {
+  if (!isLookupMap()) {
+    unsigned Size = LookupPtr.getInt();
+
+    // The lookup data is stored as an array. Search through the array
+    // to find the insertion location.
+    NamedDecl **Array;
+    if (Size == 0) {
+      Array = new NamedDecl*[LookupIsMap - 1];
+      LookupPtr.setPointer(Array);
+    } else {
+      Array = static_cast<NamedDecl **>(LookupPtr.getPointer());
+    }
+
+    // We always keep declarations of the same name next to each other
+    // in the array, so that it is easy to return multiple results
+    // from lookup(). There will be zero, one, or two declarations of
+    // the same name.
+    unsigned Match;
+    for (Match = 0; Match < Size; ++Match) {
+      if (Array[Match]->getDeclName() == D->getDeclName())
+       break;
+    }
+
+    if (Match < Size) {
+      // We found another declaration with the same name. If it's also
+      // in the same identifier namespace, update the declaration in
+      // place.
+      Decl::IdentifierNamespace NS = D->getIdentifierNamespace();
+      if (Array[Match]->getIdentifierNamespace() == NS) {
+       Array[Match] = D;
+       return;
+      }
+      if (Match + 1 < Size && Array[Match + 1]->getIdentifierNamespace() == NS) {
+       Array[Match + 1] = D;
+       return;
+      }
+
+      // If there is an existing declaration in the namespace of
+      // ordinary identifiers, then it must precede the tag
+      // declaration for C++ name lookup to operate properly. Therefore,
+      // if our match is an ordinary name and the new name is in the
+      // tag namespace, we'll insert the new declaration after it. 
+      if (Match < Size && (NS == Decl::IDNS_Tag) && 
+         (Array[Match]->getIdentifierNamespace() & Decl::IDNS_Ordinary))
+       ++Match;
+    }
+       
+    if (Size < LookupIsMap - 1) {
+      // The new declaration will fit in the array. Insert the new
+      // declaration at the position Match in the array. 
+      for (unsigned Idx = Size; Idx > Match; --Idx)
+       Array[Idx] = Array[Idx-1];
+      
+      Array[Match] = D;
+      LookupPtr.setInt(Size + 1);
+      return;
+    }
+
+    // We've reached capacity in this array. Create a map and copy in
+    // all of the declarations that were stored in the array.
+    StoredDeclsMap *Map = new StoredDeclsMap(16);
+    LookupPtr.setPointer(Map);
+    LookupPtr.setInt(LookupIsMap);
+    for (unsigned Idx = 0; Idx < LookupIsMap - 1; ++Idx) 
+      insertImpl(Array[Idx]);
+    delete [] Array;
+
+    // Fall through to perform insertion into the map.
+  } 
+
+  // Insert this declaration into the map.
+  StoredDeclsMap *Map = static_cast<StoredDeclsMap*>(LookupPtr.getPointer());
+  StoredDeclsMap::iterator Pos = Map->find(D->getDeclName());
+  unsigned IndexOfD = D->getIdentifierNamespace() & Decl::IDNS_Ordinary? 0 : 1;
+
+  if (Pos == Map->end()) {
+    // Put this declaration into the appropriate slot.
+    TwoNamedDecls Val;
+    Val.Decls[0] = 0;
+    Val.Decls[1] = 0;
+    Val.Decls[IndexOfD] = D;
+    Pos = Map->insert(std::make_pair(D->getDeclName(),Val)).first;
+  } else {
+    Pos->second.Decls[IndexOfD] = D;
+  }
+}
diff --git a/clang/lib/AST/DeclCXX.cpp b/clang/lib/AST/DeclCXX.cpp
index a26803caecb..3eaf301d7a8 100644
--- a/clang/lib/AST/DeclCXX.cpp
+++ b/clang/lib/AST/DeclCXX.cpp
@@ -36,16 +36,9 @@ NonTypeTemplateParmDecl::Create(ASTContext &C, DeclContext *DC,
   return new (Mem) NonTypeTemplateParmDecl(DC, L, Id, T, TypeSpecStartLoc);
 }
 
-CXXFieldDecl *CXXFieldDecl::Create(ASTContext &C, CXXRecordDecl *RD,
-                                   SourceLocation L, IdentifierInfo *Id,
-                                   QualType T, bool Mut, Expr *BW) {
-  void *Mem = C.getAllocator().Allocate<CXXFieldDecl>();
-  return new (Mem) CXXFieldDecl(RD, L, Id, T, Mut, BW);
-}
-
 CXXRecordDecl::CXXRecordDecl(TagKind TK, DeclContext *DC,
                              SourceLocation L, IdentifierInfo *Id) 
-  : RecordDecl(CXXRecord, TK, DC, L, Id), DeclContext(CXXRecord),
+  : RecordDecl(CXXRecord, TK, DC, L, Id),
     UserDeclaredConstructor(false), UserDeclaredCopyConstructor(false),
     Aggregate(true), Polymorphic(false), Bases(0), NumBases(0),
     Constructors(DC, DeclarationName()),
@@ -74,11 +67,6 @@ void CXXRecordDecl::Destroy(ASTContext &C) {
   if (isDefinition())
     Destructor->Destroy(C);
 
-  for (OverloadedFunctionDecl::function_iterator func 
-         = Conversions.function_begin();
-       func != Conversions.function_end(); ++func)
-    (*func)->Destroy(C);
-
   RecordDecl::Destroy(C);
 }
 
@@ -176,7 +164,7 @@ CXXBaseOrMemberInitializer(QualType BaseType, Expr **Args, unsigned NumArgs)
 }
 
 CXXBaseOrMemberInitializer::
-CXXBaseOrMemberInitializer(CXXFieldDecl *Member, Expr **Args, unsigned NumArgs)
+CXXBaseOrMemberInitializer(FieldDecl *Member, Expr **Args, unsigned NumArgs)
   : Args(0), NumArgs(0) {
   BaseOrMember = reinterpret_cast<uintptr_t>(Member);
   assert((BaseOrMember & 0x01) == 0 && "Invalid member pointer");  
diff --git a/clang/lib/AST/DeclObjC.cpp b/clang/lib/AST/DeclObjC.cpp
index 84f0d98bf2e..b9226318e39 100644
--- a/clang/lib/AST/DeclObjC.cpp
+++ b/clang/lib/AST/DeclObjC.cpp
@@ -95,10 +95,10 @@ ObjCIvarDecl *ObjCIvarDecl::Create(ASTContext &C, SourceLocation L,
 
 
 ObjCAtDefsFieldDecl
-*ObjCAtDefsFieldDecl::Create(ASTContext &C, SourceLocation L,
+*ObjCAtDefsFieldDecl::Create(ASTContext &C, DeclContext *DC, SourceLocation L,
                              IdentifierInfo *Id, QualType T, Expr *BW) {
   void *Mem = C.getAllocator().Allocate<ObjCAtDefsFieldDecl>();
-  return new (Mem) ObjCAtDefsFieldDecl(L, Id, T, BW);
+  return new (Mem) ObjCAtDefsFieldDecl(DC, L, Id, T, BW);
 }
 
 void ObjCAtDefsFieldDecl::Destroy(ASTContext& C) {
diff --git a/clang/lib/AST/DeclSerialization.cpp b/clang/lib/AST/DeclSerialization.cpp
index 29714c0125c..c0ffb0c4234 100644
--- a/clang/lib/AST/DeclSerialization.cpp
+++ b/clang/lib/AST/DeclSerialization.cpp
@@ -120,11 +120,29 @@ void Decl::ReadInRec(Deserializer& D, ASTContext& C) {
 //===----------------------------------------------------------------------===//
 
 void DeclContext::EmitOutRec(Serializer& S) const {
-  S.EmitPtr(DeclChain);
+  S.EmitInt(Decls.size());
+  for (decl_iterator D = decls_begin(); D != decls_end(); ++D) {
+    bool Owned = ((*D)->getLexicalDeclContext() == this &&
+                  DeclKind != Decl::TranslationUnit &&
+                  !isFunctionOrMethod());
+    S.EmitBool(Owned);
+    if (Owned)
+      S.EmitOwnedPtr(*D);
+    else
+      S.EmitPtr(*D);
+  }
 }
 
 void DeclContext::ReadOutRec(Deserializer& D, ASTContext& C) {
-  D.ReadPtr(DeclChain);
+  unsigned NumDecls = D.ReadInt();
+  Decls.resize(NumDecls);
+  for (unsigned Idx = 0; Idx < NumDecls; ++Idx) {
+    bool Owned = D.ReadBool();
+    if (Owned)
+      Decls[Idx] = cast_or_null<ScopedDecl>(D.ReadOwnedPtr<Decl>(C));
+    else
+      D.ReadPtr<ScopedDecl>(Decls[Idx]);
+  }
 }
 
 //===----------------------------------------------------------------------===//
@@ -205,14 +223,12 @@ void NamedDecl::ReadInRec(Deserializer& D, ASTContext& C) {
 
 void ScopedDecl::EmitInRec(Serializer& S) const {
   NamedDecl::EmitInRec(S);
-  S.EmitPtr(getNext());                     // From ScopedDecl.  
   S.EmitPtr(cast_or_null<Decl>(getDeclContext()));  // From ScopedDecl.
   S.EmitPtr(cast_or_null<Decl>(getLexicalDeclContext()));  // From ScopedDecl.
 }
 
 void ScopedDecl::ReadInRec(Deserializer& D, ASTContext& C) {
   NamedDecl::ReadInRec(D, C);
-  D.ReadPtr(Next);                                  // From ScopedDecl.
 
   assert(DeclCtx == 0);
 
@@ -394,8 +410,8 @@ ParmVarDecl* ParmVarDecl::CreateImpl(Deserializer& D, ASTContext& C) {
 void EnumDecl::EmitImpl(Serializer& S) const {
   ScopedDecl::EmitInRec(S);
   S.EmitBool(isDefinition());
-  S.Emit(IntegerType);  
-  S.BatchEmitOwnedPtrs(getEnumConstantList(),getNextDeclarator());
+  S.Emit(IntegerType);
+  S.EmitOwnedPtr(getNextDeclarator());
 }
 
 EnumDecl* EnumDecl::CreateImpl(Deserializer& D, ASTContext& C) {
@@ -406,12 +422,7 @@ EnumDecl* EnumDecl::CreateImpl(Deserializer& D, ASTContext& C) {
   decl->setDefinition(D.ReadBool());
   decl->IntegerType = QualType::ReadVal(D);
   
-  Decl* next_declarator;
-  Decl* Elist;
-  
-  D.BatchReadOwnedPtrs(Elist, next_declarator, C);
-  
-  decl->setDeclChain(cast_or_null<EnumConstantDecl>(Elist));
+  Decl* next_declarator = D.ReadOwnedPtr<Decl>(C);
   decl->setNextDeclarator(cast_or_null<ScopedDecl>(next_declarator));
   
   return decl;
@@ -451,14 +462,17 @@ EnumConstantDecl* EnumConstantDecl::CreateImpl(Deserializer& D, ASTContext& C) {
 //===----------------------------------------------------------------------===//
 
 void FieldDecl::EmitImpl(Serializer& S) const {
+  S.EmitBool(Mutable);
   S.Emit(getType());
-  NamedDecl::EmitInRec(S);
+  ScopedDecl::EmitInRec(S);
   S.EmitOwnedPtr(BitWidth);  
 }
 
 FieldDecl* FieldDecl::CreateImpl(Deserializer& D, ASTContext& C) {
   void *Mem = C.getAllocator().Allocate<FieldDecl>();
-  FieldDecl* decl = new (Mem) FieldDecl(SourceLocation(), NULL, QualType(), 0);
+  FieldDecl* decl = new (Mem) FieldDecl(Field, 0, SourceLocation(), NULL, 
+                                        QualType(), 0, false, 0);
+  decl->Mutable = D.ReadBool();
   decl->DeclType.ReadBackpatch(D);  
   decl->ReadInRec(D, C);
   decl->BitWidth = D.ReadOwnedPtr<Expr>(C);
@@ -579,13 +593,7 @@ void RecordDecl::EmitImpl(Serializer& S) const {
   ScopedDecl::EmitInRec(S);
   S.EmitBool(isDefinition());
   S.EmitBool(hasFlexibleArrayMember());
-  S.EmitSInt(getNumMembers());
-  if (getNumMembers() > 0) {
-    assert (Members);
-    S.BatchEmitOwnedPtrs((unsigned) getNumMembers(), (Decl**) &Members[0]);
-  }
-  else
-    ScopedDecl::EmitOutRec(S);
+  ScopedDecl::EmitOutRec(S);
 }
 
 RecordDecl* RecordDecl::CreateImpl(Deserializer& D, ASTContext& C) {
@@ -597,17 +605,8 @@ RecordDecl* RecordDecl::CreateImpl(Deserializer& D, ASTContext& C) {
   decl->ScopedDecl::ReadInRec(D, C);
   decl->setDefinition(D.ReadBool());
   decl->setHasFlexibleArrayMember(D.ReadBool());
-  decl->NumMembers = D.ReadSInt();
-  
-  if (decl->getNumMembers() > 0) {
-    decl->Members = new FieldDecl*[(unsigned) decl->getNumMembers()];
-                              
-    D.BatchReadOwnedPtrs((unsigned) decl->getNumMembers(),
-                         (Decl**) &decl->Members[0], C);
-  }
-  else
-    decl->ScopedDecl::ReadOutRec(D, C);
-  
+  decl->ScopedDecl::ReadOutRec(D, C);
+    
   return decl;
 }
 
diff --git a/clang/lib/AST/DeclarationName.cpp b/clang/lib/AST/DeclarationName.cpp
index 649b092db01..af983feed1e 100644
--- a/clang/lib/AST/DeclarationName.cpp
+++ b/clang/lib/AST/DeclarationName.cpp
@@ -311,3 +311,9 @@ DeclarationNameTable::getCXXOperatorName(OverloadedOperatorKind Op) {
   return DeclarationName(&CXXOperatorNames[(unsigned)Op]);
 }
 
+unsigned 
+llvm::DenseMapInfo<clang::DeclarationName>::
+getHashValue(clang::DeclarationName N) {
+  return DenseMapInfo<void*>::getHashValue(N.getAsOpaquePtr());
+}
+
diff --git a/clang/lib/AST/Expr.cpp b/clang/lib/AST/Expr.cpp
index 14db18c1345..b5f966d8621 100644
--- a/clang/lib/AST/Expr.cpp
+++ b/clang/lib/AST/Expr.cpp
@@ -353,7 +353,7 @@ static bool DeclCanBeLvalue(const NamedDecl *Decl, ASTContext &Ctx) {
         = dyn_cast<NonTypeTemplateParmDecl>(Decl))
     return NTTParm->getType()->isReferenceType();
 
-  return isa<VarDecl>(Decl) || isa<CXXFieldDecl>(Decl) ||
+  return isa<VarDecl>(Decl) || isa<FieldDecl>(Decl) ||
     // C++ 3.10p2: An lvalue refers to an object or function.
     (Ctx.getLangOptions().CPlusPlus &&
      (isa<FunctionDecl>(Decl) || isa<OverloadedFunctionDecl>(Decl)));
@@ -1222,10 +1222,15 @@ static int64_t evaluateOffsetOf(ASTContext& C, const Expr *E)
     const ASTRecordLayout &RL = C.getASTRecordLayout(RD);
     FieldDecl *FD = ME->getMemberDecl();
     
-    // FIXME: This is linear time.
-    unsigned i = 0, e = 0;
-    for (i = 0, e = RD->getNumMembers(); i != e; i++) {
-      if (RD->getMember(i) == FD)
+    // FIXME: This is linear time. And the fact that we're indexing
+    // into the layout by position in the record means that we're
+    // either stuck numbering the fields in the AST or we have to keep
+    // the linear search (yuck and yuck).
+    unsigned i = 0;
+    for (RecordDecl::field_iterator Field = RD->field_begin(),
+                                 FieldEnd = RD->field_end();
+         Field != FieldEnd; (void)++Field, ++i) {
+      if (*Field == FD)
         break;
     }
     
diff --git a/clang/lib/AST/ExprConstant.cpp b/clang/lib/AST/ExprConstant.cpp
index 341baeab85b..7a83d6c063d 100644
--- a/clang/lib/AST/ExprConstant.cpp
+++ b/clang/lib/AST/ExprConstant.cpp
@@ -156,9 +156,11 @@ APValue LValueExprEvaluator::VisitMemberExpr(MemberExpr *E) {
   FieldDecl *FD = E->getMemberDecl();
     
   // FIXME: This is linear time.
-  unsigned i = 0, e = 0;
-  for (i = 0, e = RD->getNumMembers(); i != e; i++) {
-    if (RD->getMember(i) == FD)
+  unsigned i = 0;
+  for (RecordDecl::field_iterator Field = RD->field_begin(),
+                               FieldEnd = RD->field_end();
+       Field != FieldEnd; (void)++Field, ++i) {
+    if (*Field == FD)
       break;
   }