fix(cxx_indexer): use flat_hash_map, not unordered_map; fix rehashing (#6083)

* fix(cxx_indexer): use flat_hash_map, not unordered_map; fix rehashing

Also remove a bizarre constructor from NodeId.

* fix: lint

4 files changed, 19 insertions, 15 deletions

diff --git a/kythe/cxx/indexer/cxx/BUILD b/kythe/cxx/indexer/cxx/BUILD
index ab63fa613..873985b1c 100644
--- a/kythe/cxx/indexer/cxx/BUILD
+++ b/kythe/cxx/indexer/cxx/BUILD
@@ -263,7 +263,10 @@ cc_library(
     name = "type_map",
     srcs = ["type_map.cc"],
     hdrs = ["type_map.h"],
-    deps = ["@llvm-project//clang:ast"],
+    deps = [
+        "@com_google_absl//absl/container:flat_hash_map",
+        "@llvm-project//clang:ast",
+    ],
 )
 
 cc_library(
diff --git a/kythe/cxx/indexer/cxx/GraphObserver.h b/kythe/cxx/indexer/cxx/GraphObserver.h
index 30d9eb229..59fd9b8f4 100644
--- a/kythe/cxx/indexer/cxx/GraphObserver.h
+++ b/kythe/cxx/indexer/cxx/GraphObserver.h
@@ -106,7 +106,7 @@ class GraphObserver {
   /// made (thus making the token active), and so on.
   class ClaimToken {
    public:
-    virtual ~ClaimToken(){};
+    virtual ~ClaimToken() = default;
     /// \brief Returns a string representation of `Identity` stamped with this
     /// token.
     virtual std::string StampIdentity(const std::string& Identity) const = 0;
@@ -158,11 +158,6 @@ class GraphObserver {
    public:
     NodeId() {}
     NodeId(const NodeId& C) { *this = C; }
-    NodeId& operator=(const NodeId* C) {
-      Token = C->Token;
-      Identity = C->Identity;
-      return *this;
-    }
     static NodeId CreateUncompressed(const ClaimToken* Token,
                                      const std::string& Identity) {
       NodeId NewId(Token, "");
diff --git a/kythe/cxx/indexer/cxx/IndexerASTHooks.cc b/kythe/cxx/indexer/cxx/IndexerASTHooks.cc
index 5ddda9454..5f889a7de 100644
--- a/kythe/cxx/indexer/cxx/IndexerASTHooks.cc
+++ b/kythe/cxx/indexer/cxx/IndexerASTHooks.cc
@@ -4737,12 +4737,18 @@ NodeSet IndexerASTVisitor::BuildNodeSetForType(const clang::QualType& QT) {
   CHECK(!QT.isNull());
   TypeKey Key(Context, QT, QT.getTypePtr());
   auto [iter, inserted] = TypeNodes.insert({Key, NodeSet::Empty()});
-  if (inserted) {
-    iter->second = QT.hasLocalQualifiers()
-                       ? BuildNodeSetForTypeInternal(QT)
-                       : BuildNodeSetForTypeInternal(*QT.getTypePtr());
-  }
-  return iter->second;
+  if (!inserted) {
+    return iter->second;
+  }
+  // Note that `iter` may be invalidated if a recursive call causes TypeNodes to
+  // rehash. We'll still insert an empty set out of superstition about recursive
+  // types.
+  return TypeNodes
+      .insert_or_assign(Key,
+                        QT.hasLocalQualifiers()
+                            ? BuildNodeSetForTypeInternal(QT)
+                            : BuildNodeSetForTypeInternal(*QT.getTypePtr()))
+      .first->second;
 }
 
 NodeSet IndexerASTVisitor::BuildNodeSetForTypeInternal(
diff --git a/kythe/cxx/indexer/cxx/type_map.h b/kythe/cxx/indexer/cxx/type_map.h
index 6a40913ad..bfb44c38e 100644
--- a/kythe/cxx/indexer/cxx/type_map.h
+++ b/kythe/cxx/indexer/cxx/type_map.h
@@ -18,8 +18,8 @@
 
 #include <cstdint>
 #include <functional>
-#include <unordered_map>
 
+#include "absl/container/flat_hash_map.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Type.h"
 
@@ -55,7 +55,7 @@ class TypeKey {
 
 // An unordered map using the above as key.
 template <typename T>
-using TypeMap = std::unordered_map<TypeKey, T, TypeKey::Hash>;
+using TypeMap = absl::flat_hash_map<TypeKey, T, TypeKey::Hash>;
 
 }  // namespace kythe