refactor(3p/nix/libexpr): Use absl::btree_map for AttrSets r/799

This is the first step towards replacing the implementation of
attribute sets with an absl::btree_map.

Currently many access are done using array offsets and pointer
arithmetic, so this change is currently causing Nix to fail in various
ways.

6 files changed, 85 insertions, 68 deletions

diff --git a/third_party/nix/meson.build b/third_party/nix/meson.build
index 1b5e030bde..8e845c20e2 100644
--- a/third_party/nix/meson.build
+++ b/third_party/nix/meson.build
@@ -354,6 +354,7 @@ absl_deps = [
   absl.dependency('algorithm_container'),
   absl.dependency('base'),
   absl.dependency('bits'),
+  absl.dependency('btree'),
   absl.dependency('city'),
   absl.dependency('config'),
   absl.dependency('container_common'),
diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc
index fe1bf080ed..8b2af8639e 100644
--- a/third_party/nix/src/libexpr/attr-set.cc
+++ b/third_party/nix/src/libexpr/attr-set.cc
@@ -1,22 +1,49 @@
 #include "attr-set.hh"
 
-#include <algorithm>
+#include <absl/container/btree_map.h>
 
 #include "eval-inline.hh"
 
 namespace nix {
 
-/* Allocate a new array of attributes for an attribute set with a specific
-   capacity. The space is implicitly reserved after the Bindings
-   structure. */
-Bindings* EvalState::allocBindings(size_t capacity) {
-  if (capacity > std::numeric_limits<Bindings::size_t>::max()) {
-    throw Error("attribute set of size %d is too big", capacity);
+// TODO: using insert_or_assign might break existing Nix code because
+// of the weird ordering situation. Need to investigate.
+void Bindings::push_back(const Attr& attr) {
+  attributes_.insert_or_assign(attr.name, attr);
+}
+
+size_t Bindings::size() { return attributes_.size(); }
+
+void Bindings::sort() {}
+size_t Bindings::capacity() { return 0; }
+
+bool Bindings::empty() { return attributes_.empty(); }
+
+std::vector<const Attr*> Bindings::lexicographicOrder() {
+  std::vector<const Attr*> res;
+  res.reserve(attributes_.size());
+
+  for (const auto& [key, value] : attributes_) {
+    res.emplace_back(&value);
   }
-  return new (allocBytes(sizeof(Bindings) + sizeof(Attr) * capacity))
-      Bindings((Bindings::size_t)capacity);
+
+  return res;
+}
+
+Bindings::iterator Bindings::find(const Symbol& name) {
+  return &attributes_[name];
 }
 
+Bindings::iterator Bindings::begin() { return &(attributes_.begin()->second); }
+
+Bindings::iterator Bindings::end() { return &(attributes_.end()->second); }
+
+// /* Allocate a new array of attributes for an attribute set with a specific
+//    capacity. The space is implicitly reserved after the Bindings structure.
+//    */
+Bindings* EvalState::allocBindings(size_t _capacity) { return new Bindings; }
+
+// TODO(tazjin): What's Value? What's going on here?
 void EvalState::mkAttrs(Value& v, size_t capacity) {
   if (capacity == 0) {
     v = vEmptySet;
@@ -24,7 +51,7 @@ void EvalState::mkAttrs(Value& v, size_t capacity) {
   }
   clearValue(v);
   v.type = tAttrs;
-  v.attrs = allocBindings(capacity);
+  v.attrs = new Bindings;
   nrAttrsets++;
   nrAttrsInAttrsets += capacity;
 }
@@ -38,6 +65,6 @@ Value* EvalState::allocAttr(Value& vAttrs, const Symbol& name) {
   return v;
 }
 
-void Bindings::sort() { std::sort(begin(), end()); }
+// void Bindings::sort() { std::sort(begin(), end()); }
 
 }  // namespace nix
diff --git a/third_party/nix/src/libexpr/attr-set.hh b/third_party/nix/src/libexpr/attr-set.hh
index 5357e58a1d..551cddaae4 100644
--- a/third_party/nix/src/libexpr/attr-set.hh
+++ b/third_party/nix/src/libexpr/attr-set.hh
@@ -1,12 +1,13 @@
+// This file implements the underlying structure of Nix attribute sets.
 #pragma once
 
-#include <algorithm>
+#include <absl/container/btree_map.h>
 
 #include "nixexpr.hh"
 #include "symbol-table.hh"
 #include "types.hh"  // TODO(tazjin): audit this include
 
-namespace nix {
+namespace nix {  // TODO(tazjin): ::expr
 
 class EvalState;
 struct Value;
@@ -22,65 +23,49 @@ struct Attr {
   bool operator<(const Attr& a) const { return name < a.name; }
 };
 
-/* Bindings contains all the attributes of an attribute set. It is defined
-   by its size and its capacity, the capacity being the number of Attr
-   elements allocated after this structure, while the size corresponds to
-   the number of elements already inserted in this structure. */
-class Bindings {
- public:
-  typedef uint32_t size_t;
-
- private:
-  size_t size_, capacity_;
-  Attr attrs[0];
-
-  Bindings(size_t capacity) : size_(0), capacity_(capacity) {}
-  Bindings(const Bindings& bindings) = delete;
+// TODO: remove this, it only exists briefly while I get rid of the
+// current Attr struct
+inline bool operator==(const Attr& lhs, const Attr& rhs) {
+  return lhs.name == rhs.name;
+}
 
+class Bindings {
  public:
-  size_t size() const { return size_; }
+  typedef Attr* iterator;  // TODO: type, and also 'using'?
 
-  bool empty() const { return !size_; }
+  // Return the number of contained elements.
+  size_t size();
 
-  typedef Attr* iterator;
+  // Is this attribute set empty?
+  bool empty();
 
-  void push_back(const Attr& attr) {
-    assert(size_ < capacity_);
-    attrs[size_++] = attr;
-  }
+  // TODO(tazjin): rename
+  // TODO(tazjin): does this need to copy?
+  void push_back(const Attr& attr);
 
-  iterator find(const Symbol& name) {
-    Attr key(name, 0);
-    iterator i = std::lower_bound(begin(), end(), key);
-    if (i != end() && i->name == name) {
-      return i;
-    }
-    return end();
-  }
+  // Look up a specific element of the attribute set.
+  iterator find(const Symbol& name);
 
-  iterator begin() { return &attrs[0]; }
-  iterator end() { return &attrs[size_]; }
+  // TODO
+  iterator begin();
+  iterator end();
 
-  Attr& operator[](size_t pos) { return attrs[pos]; }
+  // ???
+  [[deprecated]] void sort();
 
-  void sort();
+  // ???
+  [[deprecated]] size_t capacity();
 
-  size_t capacity() { return capacity_; }
+  // oh no
+  // Attr& operator[](size_t pos); //  { return attrs[pos]; }
 
-  /* Returns the attributes in lexicographically sorted order. */
-  std::vector<const Attr*> lexicographicOrder() const {
-    std::vector<const Attr*> res;
-    res.reserve(size_);
-    for (size_t n = 0; n < size_; n++) {
-      res.emplace_back(&attrs[n]);
-    }
-    std::sort(res.begin(), res.end(), [](const Attr* a, const Attr* b) {
-      return (const std::string&)a->name < (const std::string&)b->name;
-    });
-    return res;
-  }
+  // TODO: can callers just iterate?
+  [[deprecated]] std::vector<const Attr*> lexicographicOrder();
 
+  // oh no
   friend class EvalState;
-};
 
+ private:
+  absl::btree_map<Symbol, Attr> attributes_;
+};
 }  // namespace nix
diff --git a/third_party/nix/src/libexpr/eval.cc b/third_party/nix/src/libexpr/eval.cc
index 875dab2ee7..760bada7b0 100644
--- a/third_party/nix/src/libexpr/eval.cc
+++ b/third_party/nix/src/libexpr/eval.cc
@@ -827,7 +827,8 @@ void ExprAttrs::eval(EvalState& state, Env& env, Value& v) {
     env2.up = &env;
     dynamicEnv = &env2;
 
-    auto overrides = attrs.find(state.sOverrides);
+    // TODO(tazjin): contains?
+    AttrDefs::iterator overrides = attrs.find(state.sOverrides);
     bool hasOverrides = overrides != attrs.end();
 
     /* The recursive attributes are evaluated in the new
@@ -855,17 +856,19 @@ void ExprAttrs::eval(EvalState& state, Env& env, Value& v) {
        been substituted into the bodies of the other attributes.
        Hence we need __overrides.) */
     if (hasOverrides) {
-      Value* vOverrides = (*v.attrs)[overrides->second.displ].value;
+      Value* vOverrides =
+          v.attrs->find(overrides->first)
+              ->value;  //(*v.attrs)[overrides->second.displ].value;
       state.forceAttrs(*vOverrides);
-      Bindings* newBnds =
-          state.allocBindings(v.attrs->capacity() + vOverrides->attrs->size());
-      for (auto& i : *v.attrs) {
+      Bindings* newBnds = state.allocBindings(/* capacity = */ 0);
+      for (auto& i : *v.attrs) {  // TODO(tazjin): copy constructor?
         newBnds->push_back(i);
       }
       for (auto& i : *vOverrides->attrs) {
         auto j = attrs.find(i.name);
         if (j != attrs.end()) {
-          (*newBnds)[j->second.displ] = i;
+          newBnds->push_back(i);
+          // (*newBnds)[j->second.displ] = i;
           env2.values[j->second.displ] = i.value;
         } else {
           newBnds->push_back(i);
@@ -875,6 +878,7 @@ void ExprAttrs::eval(EvalState& state, Env& env, Value& v) {
       v.attrs = newBnds;
     }
   } else {
+    // TODO(tazjin): insert range
     for (auto& i : attrs) {
       v.attrs->push_back(
           Attr(i.first, i.second.e->maybeThunk(state, env), &i.second.pos));
diff --git a/third_party/nix/src/libexpr/eval.hh b/third_party/nix/src/libexpr/eval.hh
index 055c4fda37..bc07f95070 100644
--- a/third_party/nix/src/libexpr/eval.hh
+++ b/third_party/nix/src/libexpr/eval.hh
@@ -258,7 +258,7 @@ class EvalState {
 
   Value* allocAttr(Value& vAttrs, const Symbol& name);
 
-  static Bindings* allocBindings(size_t capacity);
+  [[deprecated]] static Bindings* allocBindings(size_t capacity);
 
   void mkList(Value& v, size_t size);
   void mkAttrs(Value& v, size_t capacity);
diff --git a/third_party/nix/src/libexpr/nixexpr.cc b/third_party/nix/src/libexpr/nixexpr.cc
index 49b4a7ea41..3d454d266f 100644
--- a/third_party/nix/src/libexpr/nixexpr.cc
+++ b/third_party/nix/src/libexpr/nixexpr.cc
@@ -285,7 +285,7 @@ void ExprOpHasAttr::bindVars(const StaticEnv& env) {
 
 void ExprAttrs::bindVars(const StaticEnv& env) {
   const StaticEnv* dynamicEnv = &env;
-  StaticEnv newEnv(false, &env);
+  StaticEnv newEnv(/* isWith = */ false, &env);
 
   if (recursive) {
     dynamicEnv = &newEnv;