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>

1 files changed, 12 insertions, 8 deletions

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