Introduce the mechanism for building an AST on-disk hash table for name lookup inside a DeclContext but don't use it yet.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@111635 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 294 insertions, 6 deletions

diff --git a/lib/Serialization/ASTReader.cpp b/lib/Serialization/ASTReader.cpp
index 040277074c..05fa7cd115 100644
--- a/lib/Serialization/ASTReader.cpp
+++ b/lib/Serialization/ASTReader.cpp
@@ -704,6 +704,148 @@ public:
 typedef OnDiskChainedHashTable<ASTIdentifierLookupTrait>
   ASTIdentifierLookupTable;
 
+namespace {
+class ASTDeclContextNameLookupTrait {
+  ASTReader &Reader;
+
+public:
+  /// \brief Pair of begin/end iterators for DeclIDs.
+  typedef std::pair<DeclID *, DeclID *> data_type;
+
+  /// \brief Special internal key for declaration names.
+  /// The hash table creates keys for comparison; we do not create
+  /// a DeclarationName for the internal key to avoid deserializing types.
+  struct DeclNameKey {
+    DeclarationName::NameKind Kind;
+    uint64_t Data;
+    DeclNameKey() : Kind((DeclarationName::NameKind)0), Data(0) { }
+  };
+
+  typedef DeclarationName external_key_type;
+  typedef DeclNameKey internal_key_type;
+
+  explicit ASTDeclContextNameLookupTrait(ASTReader &Reader) : Reader(Reader) { }
+
+  static bool EqualKey(const internal_key_type& a,
+                       const internal_key_type& b) {
+    return a.Kind == b.Kind && a.Data == b.Data;
+  }
+
+  unsigned ComputeHash(const DeclNameKey &Key) const {
+    llvm::FoldingSetNodeID ID;
+    ID.AddInteger(Key.Kind);
+
+    switch (Key.Kind) {
+    case DeclarationName::Identifier:
+    case DeclarationName::CXXLiteralOperatorName:
+      ID.AddString(((IdentifierInfo*)Key.Data)->getName());
+      break;
+    case DeclarationName::ObjCZeroArgSelector:
+    case DeclarationName::ObjCOneArgSelector:
+    case DeclarationName::ObjCMultiArgSelector:
+      ID.AddInteger(serialization::ComputeHash(Selector(Key.Data)));
+      break;
+    case DeclarationName::CXXConstructorName:
+    case DeclarationName::CXXDestructorName:
+    case DeclarationName::CXXConversionFunctionName:
+      ID.AddInteger((TypeID)Key.Data);
+      break;
+    case DeclarationName::CXXOperatorName:
+      ID.AddInteger((OverloadedOperatorKind)Key.Data);
+      break;
+    case DeclarationName::CXXUsingDirective:
+      break;
+    }
+
+    return ID.ComputeHash();
+  }
+
+  internal_key_type GetInternalKey(const external_key_type& Name) const {
+    DeclNameKey Key;
+    Key.Kind = Name.getNameKind();
+    switch (Name.getNameKind()) {
+    case DeclarationName::Identifier:
+      Key.Data = (uint64_t)Name.getAsIdentifierInfo();
+      break;
+    case DeclarationName::ObjCZeroArgSelector:
+    case DeclarationName::ObjCOneArgSelector:
+    case DeclarationName::ObjCMultiArgSelector:
+      Key.Data = (uint64_t)Name.getObjCSelector().getAsOpaquePtr();
+      break;
+    case DeclarationName::CXXConstructorName:
+    case DeclarationName::CXXDestructorName:
+    case DeclarationName::CXXConversionFunctionName:
+      Key.Data = Reader.GetTypeID(Name.getCXXNameType());
+      break;
+    case DeclarationName::CXXOperatorName:
+      Key.Data = Name.getCXXOverloadedOperator();
+      break;
+    case DeclarationName::CXXLiteralOperatorName:
+      Key.Data = (uint64_t)Name.getCXXLiteralIdentifier();
+      break;
+    case DeclarationName::CXXUsingDirective:
+      break;
+    }
+    
+    return Key;
+  }
+
+  static std::pair<unsigned, unsigned>
+  ReadKeyDataLength(const unsigned char*& d) {
+    using namespace clang::io;
+    unsigned KeyLen = ReadUnalignedLE16(d);
+    unsigned DataLen = ReadUnalignedLE16(d);
+    return std::make_pair(KeyLen, DataLen);
+  }
+
+  internal_key_type ReadKey(const unsigned char* d, unsigned) {
+    using namespace clang::io;
+
+    DeclNameKey Key;
+    Key.Kind = (DeclarationName::NameKind)*d++;
+    switch (Key.Kind) {
+    case DeclarationName::Identifier:
+      Key.Data = (uint64_t)Reader.DecodeIdentifierInfo(ReadUnalignedLE32(d));
+      break;
+    case DeclarationName::ObjCZeroArgSelector:
+    case DeclarationName::ObjCOneArgSelector:
+    case DeclarationName::ObjCMultiArgSelector:
+      Key.Data = 
+         (uint64_t)Reader.DecodeSelector(ReadUnalignedLE32(d)).getAsOpaquePtr();
+      break;
+    case DeclarationName::CXXConstructorName:
+    case DeclarationName::CXXDestructorName:
+    case DeclarationName::CXXConversionFunctionName:
+      Key.Data = ReadUnalignedLE32(d); // TypeID
+      break;
+    case DeclarationName::CXXOperatorName:
+      Key.Data = *d++; // OverloadedOperatorKind
+      break;
+    case DeclarationName::CXXLiteralOperatorName:
+      Key.Data = (uint64_t)Reader.DecodeIdentifierInfo(ReadUnalignedLE32(d));
+      break;
+    case DeclarationName::CXXUsingDirective:
+      break;
+    }
+    
+    return Key;
+  }
+
+  data_type ReadData(internal_key_type, const unsigned char* d,
+                     unsigned DataLen) {
+    using namespace clang::io;
+    unsigned NumDecls = ReadUnalignedLE16(d);
+    DeclID *Start = (DeclID *)d;
+    return std::make_pair(Start, Start + NumDecls);
+  }
+};
+
+} // end anonymous namespace
+
+/// \brief The on-disk hash table used for the DeclContext's Name lookup table.
+typedef OnDiskChainedHashTable<ASTDeclContextNameLookupTrait>
+  ASTDeclContextNameLookupTable;
+
 void ASTReader::Error(const char *Msg) {
   Diag(diag::err_fe_pch_malformed) << Msg;
 }
@@ -2825,6 +2967,7 @@ QualType ASTReader::GetType(TypeID ID) {
   if (TypesLoaded[Index].isNull()) {
     TypesLoaded[Index] = ReadTypeRecord(Index);
     TypesLoaded[Index]->setFromAST();
+    TypeIdxs[TypesLoaded[Index]] = TypeIdx::fromTypeID(ID);
     if (DeserializationListener)
       DeserializationListener->TypeRead(TypeIdx::fromTypeID(ID),
                                         TypesLoaded[Index]);
@@ -2833,6 +2976,27 @@ QualType ASTReader::GetType(TypeID ID) {
   return TypesLoaded[Index].withFastQualifiers(FastQuals);
 }
 
+TypeID ASTReader::GetTypeID(QualType T) const {
+  return MakeTypeID(T,
+              std::bind1st(std::mem_fun(&ASTReader::GetTypeIdx), this));
+}
+
+TypeIdx ASTReader::GetTypeIdx(QualType T) const {
+  if (T.isNull())
+    return TypeIdx();
+  assert(!T.getLocalFastQualifiers());
+
+  TypeIdxMap::const_iterator I = TypeIdxs.find(T);
+  // GetTypeIdx is mostly used for computing the hash of DeclarationNames and
+  // comparing keys of ASTDeclContextNameLookupTable.
+  // If the type didn't come from the AST file use a specially marked index
+  // so that any hash/key comparison fail since no such index is stored
+  // in a AST file.
+  if (I == TypeIdxs.end())
+    return TypeIdx(-1);
+  return I->second;
+}
+
 TemplateArgumentLocInfo
 ASTReader::GetTemplateArgumentLocInfo(TemplateArgument::ArgKind Kind,
                                       llvm::BitstreamCursor &DeclsCursor,
diff --git a/lib/Serialization/ASTWriter.cpp b/lib/Serialization/ASTWriter.cpp
index 716abde892..94be24ad2c 100644
--- a/lib/Serialization/ASTWriter.cpp
+++ b/lib/Serialization/ASTWriter.cpp
@@ -1653,6 +1653,7 @@ void ASTWriter::WriteSelectors(Sema &SemaRef) {
   // Create and write out the blob that contains selectors and the method pool.
   {
     OnDiskChainedHashTableGenerator<ASTMethodPoolTrait> Generator;
+    ASTMethodPoolTrait Trait(*this);
 
     // Create the on-disk hash table representation. We walk through every
     // selector we've seen and look it up in the method pool.
@@ -1692,7 +1693,7 @@ void ASTWriter::WriteSelectors(Sema &SemaRef) {
         // A new method pool entry.
         ++NumTableEntries;
       }
-      Generator.insert(S, Data);
+      Generator.insert(S, Data, Trait);
     }
 
     // Create the on-disk hash table in a buffer.
@@ -1877,6 +1878,7 @@ void ASTWriter::WriteIdentifierTable(Preprocessor &PP) {
   // strings.
   {
     OnDiskChainedHashTableGenerator<ASTIdentifierTableTrait> Generator;
+    ASTIdentifierTableTrait Trait(*this, PP);
 
     // Look for any identifiers that were named while processing the
     // headers, but are otherwise not needed. We add these to the hash
@@ -1896,7 +1898,7 @@ void ASTWriter::WriteIdentifierTable(Preprocessor &PP) {
          ID != IDEnd; ++ID) {
       assert(ID->first && "NULL identifier in identifier table");
       if (!Chain || !ID->first->isFromAST())
-        Generator.insert(ID->first, ID->second);
+        Generator.insert(ID->first, ID->second, Trait);
     }
 
     // Create the on-disk hash table in a buffer.
@@ -1940,6 +1942,127 @@ void ASTWriter::WriteIdentifierTable(Preprocessor &PP) {
 }
 
 //===----------------------------------------------------------------------===//
+// DeclContext's Name Lookup Table Serialization
+//===----------------------------------------------------------------------===//
+
+namespace {
+// Trait used for the on-disk hash table used in the method pool.
+class ASTDeclContextNameLookupTrait {
+  ASTWriter &Writer;
+
+public:
+  typedef DeclarationName key_type;
+  typedef key_type key_type_ref;
+
+  typedef DeclContext::lookup_result data_type;
+  typedef const data_type& data_type_ref;
+
+  explicit ASTDeclContextNameLookupTrait(ASTWriter &Writer) : Writer(Writer) { }
+
+  unsigned ComputeHash(DeclarationName Name) {
+    llvm::FoldingSetNodeID ID;
+    ID.AddInteger(Name.getNameKind());
+
+    switch (Name.getNameKind()) {
+    case DeclarationName::Identifier:
+      ID.AddString(Name.getAsIdentifierInfo()->getName());
+      break;
+    case DeclarationName::ObjCZeroArgSelector:
+    case DeclarationName::ObjCOneArgSelector:
+    case DeclarationName::ObjCMultiArgSelector:
+      ID.AddInteger(serialization::ComputeHash(Name.getObjCSelector()));
+      break;
+    case DeclarationName::CXXConstructorName:
+    case DeclarationName::CXXDestructorName:
+    case DeclarationName::CXXConversionFunctionName:
+      ID.AddInteger(Writer.GetOrCreateTypeID(Name.getCXXNameType()));
+      break;
+    case DeclarationName::CXXOperatorName:
+      ID.AddInteger(Name.getCXXOverloadedOperator());
+      break;
+    case DeclarationName::CXXLiteralOperatorName:
+      ID.AddString(Name.getCXXLiteralIdentifier()->getName());
+    case DeclarationName::CXXUsingDirective:
+      break;
+    }
+
+    return ID.ComputeHash();
+  }
+
+  std::pair<unsigned,unsigned>
+    EmitKeyDataLength(llvm::raw_ostream& Out, DeclarationName Name,
+                      data_type_ref Lookup) {
+    unsigned KeyLen = 1;
+    switch (Name.getNameKind()) {
+    case DeclarationName::Identifier:
+    case DeclarationName::ObjCZeroArgSelector:
+    case DeclarationName::ObjCOneArgSelector:
+    case DeclarationName::ObjCMultiArgSelector:
+    case DeclarationName::CXXConstructorName:
+    case DeclarationName::CXXDestructorName:
+    case DeclarationName::CXXConversionFunctionName:
+    case DeclarationName::CXXLiteralOperatorName:
+      KeyLen += 4;
+      break;
+    case DeclarationName::CXXOperatorName:
+      KeyLen += 1;
+      break;
+    case DeclarationName::CXXUsingDirective:
+      break;
+    }
+    clang::io::Emit16(Out, KeyLen);
+
+    // 2 bytes for num of decls and 4 for each DeclID.
+    unsigned DataLen = 2 + 4 * (Lookup.second - Lookup.first);
+    clang::io::Emit16(Out, DataLen);
+
+    return std::make_pair(KeyLen, DataLen);
+  }
+
+  void EmitKey(llvm::raw_ostream& Out, DeclarationName Name, unsigned) {
+    using namespace clang::io;
+
+    assert(Name.getNameKind() < 0x100 && "Invalid name kind ?");
+    Emit8(Out, Name.getNameKind());
+    switch (Name.getNameKind()) {
+    case DeclarationName::Identifier:
+      Emit32(Out, Writer.getIdentifierRef(Name.getAsIdentifierInfo()));
+      break;
+    case DeclarationName::ObjCZeroArgSelector:
+    case DeclarationName::ObjCOneArgSelector:
+    case DeclarationName::ObjCMultiArgSelector:
+      Emit32(Out, Writer.getSelectorRef(Name.getObjCSelector()));
+      break;
+    case DeclarationName::CXXConstructorName:
+    case DeclarationName::CXXDestructorName:
+    case DeclarationName::CXXConversionFunctionName:
+      Emit32(Out, Writer.getTypeID(Name.getCXXNameType()));
+      break;
+    case DeclarationName::CXXOperatorName:
+      assert(Name.getCXXOverloadedOperator() < 0x100 && "Invalid operator ?");
+      Emit8(Out, Name.getCXXOverloadedOperator());
+      break;
+    case DeclarationName::CXXLiteralOperatorName:
+      Emit32(Out, Writer.getIdentifierRef(Name.getCXXLiteralIdentifier()));
+      break;
+    case DeclarationName::CXXUsingDirective:
+      break;
+    }
+  }
+
+  void EmitData(llvm::raw_ostream& Out, key_type_ref,
+                data_type Lookup, unsigned DataLen) {
+    uint64_t Start = Out.tell(); (void)Start;
+    clang::io::Emit16(Out, Lookup.second - Lookup.first);
+    for (; Lookup.first != Lookup.second; ++Lookup.first)
+      clang::io::Emit32(Out, Writer.GetDeclRef(*Lookup.first));
+
+    assert(Out.tell() - Start == DataLen && "Data length is wrong");
+  }
+};
+} // end anonymous namespace
+
+//===----------------------------------------------------------------------===//
 // General Serialization Routines
 //===----------------------------------------------------------------------===//
 
@@ -2587,7 +2710,7 @@ TypeID ASTWriter::GetOrCreateTypeID(QualType T) {
               std::bind1st(std::mem_fun(&ASTWriter::GetOrCreateTypeIdx), this));
 }
 
-TypeID ASTWriter::getTypeID(QualType T) {
+TypeID ASTWriter::getTypeID(QualType T) const {
   return MakeTypeID(T,
               std::bind1st(std::mem_fun(&ASTWriter::getTypeIdx), this));
 }
@@ -2607,13 +2730,14 @@ TypeIdx ASTWriter::GetOrCreateTypeIdx(QualType T) {
   return Idx;
 }
 
-TypeIdx ASTWriter::getTypeIdx(QualType T) {
+TypeIdx ASTWriter::getTypeIdx(QualType T) const {
   if (T.isNull())
     return TypeIdx();
   assert(!T.getLocalFastQualifiers());
 
-  assert(TypeIdxs.find(T) != TypeIdxs.end() && "Type not emitted!");
-  return TypeIdxs[T];
+  TypeIdxMap::const_iterator I = TypeIdxs.find(T);
+  assert(I != TypeIdxs.end() && "Type not emitted!");
+  return I->second;
 }
 
 void ASTWriter::AddDeclRef(const Decl *D, RecordData &Record) {