refactor(3p/nix): Revert VectorBindings implementation r/1298

This reverts parts of the CLs splitting the backing implementation for
Bindings and moves back to only the BTreeMap-backed implementation.

Our evaluation has indicated that the Vector-backed implementation
does not match the performance of the plain array used upstream, and
in my view the complexity introduced by it is not worth the relatively
small (single-digit percentage) performance increase with a
pivot-point close to the number of attributes yielded by
stdenv.mkDerivation.

Going forward we will trial implementations of attribute sets backed
by HAMTs, and investigate other mechanisms of speeding up the language.

Some changes from the previous CLs are retained, for example the
removal of insert_or_assign and the passing of capacity.

Change-Id: I6eb4b075b453949583360755055c21a29d7ff642
Reviewed-on: https://cl.tvl.fyi/c/depot/+/1172
Reviewed-by: glittershark <grfn@gws.fyi>
Tested-by: BuildkiteCI

1 files changed, 17 insertions, 49 deletions

diff --git a/third_party/nix/src/libexpr/attr-set.hh b/third_party/nix/src/libexpr/attr-set.hh
index 795ee2337f..f0b1448ba2 100644
--- a/third_party/nix/src/libexpr/attr-set.hh
+++ b/third_party/nix/src/libexpr/attr-set.hh
@@ -1,8 +1,6 @@
 // This file implements the underlying structure of Nix attribute sets.
 #pragma once
 
-#include <cstddef>
-
 #include <absl/container/btree_map.h>
 #include <gc/gc_allocator.h>
 
@@ -26,75 +24,45 @@ 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<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(){};
-  BindingsIterator& operator++();
-  BindingsIterator operator++(int);
-  bool operator==(const BindingsIterator& other) const;
-  bool operator!=(const BindingsIterator& other) const;
-  reference operator*() const;
-  pointer operator->() const { return &operator*(); }
-
-  BindingsIterator& operator=(const BindingsIterator& other) {
-    _iterator = other._iterator;
-    return *this;
-  }
-
- protected:
-  explicit BindingsIterator(AttributeMap::iterator&& iterator)
-      : _iterator(iterator){};
-
-  explicit BindingsIterator(AttributeVector::iterator&& iterator)
-      : _iterator(iterator){};
-
- private:
-  std::variant<AttributeMap::iterator, AttributeVector::iterator> _iterator;
-};
+using AttributeMap =
+    absl::btree_map<Symbol, Attr, std::less<Symbol>,
+                    gc_allocator<std::pair<const Symbol, Attr>>>;
 
 class Bindings {
  public:
-  typedef BindingsIterator iterator;
+  typedef AttributeMap::iterator iterator;
 
-  // Allocate a new attribute set with a static capacity that is visible to the
-  // garbage collector.
+  // Allocate a new attribute set that is visible to the garbage
+  // collector.
   static Bindings* NewGC(size_t capacity = 0);
 
   // Return the number of contained elements.
-  virtual size_t size() = 0;
+  size_t size();
 
   // Is this attribute set empty?
-  virtual bool empty() = 0;
+  bool empty();
 
   // Insert, but do not replace, values in the attribute set.
-  virtual void push_back(const Attr& attr) = 0;
+  void push_back(const Attr& attr);
 
   // Look up a specific element of the attribute set.
-  virtual iterator find(const Symbol& name) = 0;
+  iterator find(const Symbol& name);
 
   // TODO
-  virtual iterator begin() = 0;
-  virtual iterator end() = 0;
+  iterator begin();
+  iterator end();
 
   // Merge values from other into this attribute set.
-  virtual void merge(Bindings& other) = 0;
+  void merge(const Bindings& other);
 
   // TODO: can callers just iterate?
-  [[deprecated]] virtual std::vector<const Attr*> lexicographicOrder() = 0;
+  [[deprecated]] std::vector<const Attr*> lexicographicOrder();
 
   // oh no
   friend class EvalState;
+
+ private:
+  AttributeMap attributes_;
 };
 
 }  // namespace nix