refactor(3p/nix/libexpr): Use absl::node_hash_set in SymbolTable r/794

This replaces the previous use of std::unordered_set with
absl::node_hash_set.

This type was chosen because the current implementation requires
pointer stability.

This does not yet touch the 'Attr' struct.

As a bonus, the implementation of the SymbolTable struct is now
consolidated into a single header/implementation file pair.

3 files changed, 39 insertions, 32 deletions

diff --git a/third_party/nix/src/libexpr/nixexpr.cc b/third_party/nix/src/libexpr/nixexpr.cc
index 22be923404..d7b1a0fdd5 100644
--- a/third_party/nix/src/libexpr/nixexpr.cc
+++ b/third_party/nix/src/libexpr/nixexpr.cc
@@ -413,14 +413,4 @@ string ExprLambda::showNamePos() const {
       .str();
 }
 
-/* Symbol table. */
-
-size_t SymbolTable::totalSize() const {
-  size_t n = 0;
-  for (auto& i : symbols) {
-    n += i.size();
-  }
-  return n;
-}
-
 }  // namespace nix
diff --git a/third_party/nix/src/libexpr/symbol-table.cc b/third_party/nix/src/libexpr/symbol-table.cc
new file mode 100644
index 0000000000..5b9fb27d59
--- /dev/null
+++ b/third_party/nix/src/libexpr/symbol-table.cc
@@ -0,0 +1,24 @@
+#include "symbol-table.hh"
+
+#include <absl/container/node_hash_set.h>
+#include <absl/strings/string_view.h>
+
+namespace nix {
+
+Symbol SymbolTable::Create(absl::string_view sym) {
+  auto it = symbols_.emplace(sym);
+  const string* ptr = &(*it.first);
+  return Symbol(ptr);
+}
+
+size_t SymbolTable::Size() const { return symbols_.size(); }
+
+size_t SymbolTable::TotalSize() const {
+  size_t n = 0;
+  for (auto& i : symbols_) {
+    n += i.size();
+  }
+  return n;
+}
+
+}  // namespace nix
diff --git a/third_party/nix/src/libexpr/symbol-table.hh b/third_party/nix/src/libexpr/symbol-table.hh
index 8c27cf8ec7..62c0b48a17 100644
--- a/third_party/nix/src/libexpr/symbol-table.hh
+++ b/third_party/nix/src/libexpr/symbol-table.hh
@@ -1,11 +1,11 @@
 #pragma once
 
-#include <map>
-#include <unordered_set>
+#include <absl/container/node_hash_set.h>
+#include <absl/strings/string_view.h>
 
 #include "types.hh"
 
-namespace nix {
+namespace nix {  // TODO(tazjin): ::expr
 
 /* Symbol table used by the parser and evaluator to represent and look
    up identifiers and attributes efficiently.  SymbolTable::create()
@@ -15,8 +15,8 @@ namespace nix {
 
 class Symbol {
  private:
-  const string* s;  // pointer into SymbolTable
-  Symbol(const string* s) : s(s){};
+  const std::string* s;  // pointer into SymbolTable
+  Symbol(const std::string* s) : s(s){};
   friend class SymbolTable;
 
  public:
@@ -28,7 +28,7 @@ class Symbol {
 
   bool operator<(const Symbol& s2) const { return s < s2.s; }
 
-  operator const string&() const { return *s; }
+  operator const std::string&() const { return *s; }
 
   bool set() const { return s; }
 
@@ -38,26 +38,19 @@ class Symbol {
 };
 
 class SymbolTable {
- private:
-  typedef std::unordered_set<string> Symbols;
-  Symbols symbols;
-
  public:
-  Symbol create(const string& s) {
-    std::pair<Symbols::iterator, bool> res = symbols.insert(s);
-    return Symbol(&*res.first);
-  }
+  Symbol Create(absl::string_view sym);
 
-  size_t size() const { return symbols.size(); }
+  // TODO(tazjin): two of these?
+  size_t Size() const;
 
-  size_t totalSize() const;
+  // Return the total size (in bytes)
+  size_t TotalSize() const;
 
-  template <typename T>
-  void dump(T callback) {
-    for (auto& s : symbols) {
-      callback(s);
-    }
-  }
+ private:
+  // flat_hash_set does not retain pointer stability on rehashing,
+  // hence "interned" strings/symbols are stored on the heap.
+  absl::node_hash_set<std::string> symbols_;
 };
 
 }  // namespace nix