feat(3p/nix): Add vector-backed impl for Bindings r/1284

Add an alternative impl of the now-abstract Bindings base class that is
backed by a std::vector, somewhat similar but stylistically a little
superior to the array-backed implementation in upstream nix. The
underlying iterator type in BindingsIterator is now backed by a
std::variant that we std::visit an overload over in order to implement
the various bits of the iterator interface.

Paired-With: Luke Granger-Brown <git@lukegb.com>
Paired-With: Vincent Ambo <mail@tazj.in>
Paired-With: Perry Lorier <isomer@tvl.fyi>
Change-Id: I7fbd1f4d5c449e2f9b82102a701b0bacd5e80672
Reviewed-on: https://cl.tvl.fyi/c/depot/+/1123
Tested-by: BuildkiteCI
Reviewed-by: tazjin <mail@tazj.in>

2 files changed, 150 insertions, 16 deletions

diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc
index 3d1005fd0f..053d7d6f6c 100644
--- a/third_party/nix/src/libexpr/attr-set.cc
+++ b/third_party/nix/src/libexpr/attr-set.cc
@@ -7,25 +7,56 @@
 #include <glog/logging.h>
 
 #include "libexpr/eval-inline.hh"
+#include "libutil/visitor.hh"
 
 namespace nix {
 
 BindingsIterator& BindingsIterator::operator++() {
-  _iterator++;
+  std::visit(util::overloaded{
+                 [](AttributeMap::iterator& iter) { ++iter; },
+                 [](AttributeVector::iterator& iter) { ++iter; },
+             },
+             _iterator);
   return *this;
 }
+
 BindingsIterator BindingsIterator::operator++(int) {
-  ++_iterator;
+  std::visit(util::overloaded{
+                 [](AttributeMap::iterator& iter) { iter++; },
+                 [](AttributeVector::iterator& iter) { iter++; },
+             },
+             _iterator);
   return *this;
 }
+
 bool BindingsIterator::operator==(const BindingsIterator& other) const {
   return _iterator == other._iterator;
 }
+
 bool BindingsIterator::operator!=(const BindingsIterator& other) const {
   return _iterator != other._iterator;
 }
+
 BindingsIterator::reference BindingsIterator::operator*() const {
-  return *_iterator;
+  return std::visit(
+      util::overloaded{
+          [](AttributeMap::iterator iter) -> std::pair<const Symbol, Attr>& {
+            return *iter;
+          },
+          [](AttributeVector::iterator iter) -> std::pair<const Symbol, Attr>& {
+            // this cast is effectively upcasting the left-hand side of the
+            // pair, which in the vector case *must* be const so that insert and
+            // friends can shift it around, but in the map case *must not* be
+            // const so that the key ordering semantics don't change out from
+            // under the map. So we pick const as the LUB of the two types and
+            // then upcast here. The static_assert, per the docs for
+            // reinterpret_cast, is proving that this is safe
+            static_assert(
+                std::is_standard_layout<std::pair<const Symbol, Attr>>::value);
+            return *reinterpret_cast<std::pair<const Symbol, Attr>*>(&*iter);
+          },
+      },
+      _iterator);
 }
 
 class BTreeBindings : public Bindings {
@@ -33,7 +64,7 @@ class BTreeBindings : public Bindings {
   size_t size() override;
   bool empty() override;
   void push_back(const Attr& attr) override;
-  void insert_or_assign(const Attr& attr) override;
+  void insert_or_assign(Attr& attr) override;
   Bindings::iterator find(const Symbol& name) override;
   Bindings::iterator begin() override;
   Bindings::iterator end() override;
@@ -44,8 +75,6 @@ class BTreeBindings : public Bindings {
   AttributeMap attributes_;
 };
 
-Bindings* Bindings::NewGC() { return new (GC) BTreeBindings; }
-
 // This function inherits its name from previous implementations, in
 // which Bindings was backed by an array of elements which was scanned
 // linearly.
@@ -66,7 +95,7 @@ void BTreeBindings::push_back(const Attr& attr) {
 }
 
 // Insert or assign (i.e. replace) a value in the attribute set.
-void BTreeBindings::insert_or_assign(const Attr& attr) {
+void BTreeBindings::insert_or_assign(Attr& attr) {
   attributes_.insert_or_assign(attr.name, attr);
 }
 
@@ -106,7 +135,9 @@ void BTreeBindings::merge(Bindings& other) {
 void EvalState::mkAttrs(Value& v, size_t capacity) {
   clearValue(v);
   v.type = tAttrs;
-  v.attrs = BTreeBindings::NewGC();
+  v.attrs = Bindings::NewGC();
+  assert(v.attrs->begin() == v.attrs->begin());
+  assert(v.attrs->end() == v.attrs->end());
   nrAttrsets++;
   nrAttrsInAttrsets += capacity;
 }
@@ -120,4 +151,103 @@ Value* EvalState::allocAttr(Value& vAttrs, const Symbol& name) {
   return v;
 }
 
+class VectorBindings : public Bindings {
+ public:
+  size_t size() override;
+  bool empty() override;
+  void push_back(const Attr& attr) override;
+  void insert_or_assign(Attr& attr) override;
+  Bindings::iterator find(const Symbol& name) override;
+  Bindings::iterator begin() override;
+  Bindings::iterator end() override;
+  void merge(Bindings& other) override;
+  [[deprecated]] virtual std::vector<const Attr*> lexicographicOrder() override;
+
+ private:
+  AttributeVector attributes_;
+};
+
+size_t VectorBindings::size() { return attributes_.size(); }
+
+bool VectorBindings::empty() { return attributes_.empty(); }
+
+// Insert or assign (i.e. replace) a value in the attribute set.
+void VectorBindings::insert_or_assign(Attr& attr) {
+  for (auto it = attributes_.begin(); it != attributes_.end(); ++it) {
+    if (it->first == attr.name) {
+      it->second = attr;
+      return;
+    } else if (attr.name < it->first) {
+      // TODO convert to BTreeMap if we get big enough
+      attributes_.emplace(it, attr.name, attr);
+      return;
+    }
+  }
+
+  attributes_.emplace_back(attr.name, attr);
+}
+
+void VectorBindings::merge(Bindings& other) {
+  AttributeVector new_attributes;
+  new_attributes.reserve(size() + other.size());
+
+  auto m_it = attributes_.begin();
+  auto other_it = other.begin();
+
+  while (other_it != other.end() && m_it != attributes_.end()) {
+    if (other_it->first < m_it->first) {
+      new_attributes.push_back(*(m_it++));
+    } else {
+      if (m_it->first == other_it->first) {
+        ++m_it;
+      }
+      new_attributes.push_back(*(other_it++));
+    }
+  }
+
+  if (m_it != attributes_.end()) {
+    std::copy(m_it, attributes_.end(), std::back_inserter(new_attributes));
+  }
+
+  if (other_it != other.end()) {
+    std::copy(other_it, other.end(), std::back_inserter(new_attributes));
+  }
+
+  new_attributes.shrink_to_fit();
+
+  attributes_ = new_attributes;
+}
+
+void VectorBindings::push_back(const Attr& attr) {
+  attributes_.emplace_back(attr.name, attr);
+}
+
+std::vector<const Attr*> VectorBindings::lexicographicOrder() {
+  std::vector<const Attr*> result(attributes_.size());
+
+  for (auto& [_, attr] : attributes_) {
+    result.push_back(&attr);
+  }
+
+  return result;
+}
+
+Bindings::iterator VectorBindings::find(const Symbol& name) {
+  return BindingsIterator{
+      std::find_if(attributes_.begin(), attributes_.end(),
+                   [&name](const auto& pair) { return pair.first == name; })};
+}
+
+Bindings::iterator VectorBindings::begin() {
+  return BindingsIterator{attributes_.begin()};
+}
+
+Bindings::iterator VectorBindings::end() {
+  return BindingsIterator{attributes_.end()};
+}
+
+// TODO pick what to do based on size
+Bindings* Bindings::NewGC() { return new (GC) BTreeBindings; }
+// Bindings* Bindings::NewGC() { return new (GC) VectorBindings; }
+
 }  // namespace nix
diff --git a/third_party/nix/src/libexpr/attr-set.hh b/third_party/nix/src/libexpr/attr-set.hh
index 06ae8f4b07..3834eac419 100644
--- a/third_party/nix/src/libexpr/attr-set.hh
+++ b/third_party/nix/src/libexpr/attr-set.hh
@@ -26,14 +26,17 @@ struct Attr {
 
 // Convenience alias for the backing map, with the garbage-collecting
 // allocator explicitly specified.
-using AttributeMap =
-    absl::btree_map<Symbol, Attr, std::less<Symbol>,
-                    gc_allocator<std::pair<const Symbol, Attr>>>;
+using AttributeMap = absl::btree_map<Symbol, Attr, std::less<Symbol>,
+                                     gc_allocator<std::pair<Symbol, Attr>>>;
+
+using AttributeVector =
+    std::vector<std::pair<Symbol, Attr>, gc_allocator<std::pair<Symbol, Attr>>>;
 
 class BindingsIterator : public std::iterator<std::forward_iterator_tag,
                                               std::pair<const Symbol, Attr>> {
   friend class Bindings;
   friend class BTreeBindings;
+  friend class VectorBindings;
 
  public:
   BindingsIterator() : _iterator(){};
@@ -43,6 +46,7 @@ class BindingsIterator : public std::iterator<std::forward_iterator_tag,
   bool operator!=(const BindingsIterator& other) const;
   reference operator*() const;
   pointer operator->() const { return &operator*(); }
+
   BindingsIterator& operator=(const BindingsIterator& other) {
     _iterator = other._iterator;
     return *this;
@@ -52,8 +56,11 @@ class BindingsIterator : public std::iterator<std::forward_iterator_tag,
   explicit BindingsIterator(AttributeMap::iterator&& iterator)
       : _iterator(iterator){};
 
+  explicit BindingsIterator(AttributeVector::iterator&& iterator)
+      : _iterator(iterator){};
+
  private:
-  AttributeMap::iterator _iterator;
+  std::variant<AttributeMap::iterator, AttributeVector::iterator> _iterator;
 };
 
 class Bindings {
@@ -78,7 +85,7 @@ class Bindings {
   virtual void push_back(const Attr& attr) = 0;
 
   // Insert a value, or replace an existing one.
-  virtual void insert_or_assign(const Attr& attr) = 0;
+  virtual void insert_or_assign(Attr& attr) = 0;
 
   // Look up a specific element of the attribute set.
   virtual iterator find(const Symbol& name) = 0;
@@ -95,9 +102,6 @@ class Bindings {
 
   // oh no
   friend class EvalState;
-
- private:
-  AttributeMap attributes_;
 };
 
 }  // namespace nix