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.

1 files changed, 38 insertions, 11 deletions

diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc
index fe1bf080edcb..8b2af8639eff 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