refactor(3p/nix): Abstract away concrete bindings impl r/1283

To pave the way for the thing we want to do eventually which is use a
linear-time array for bindings (aka attribute sets) that are statically
known to be small enough to get a performance benefit from doing so,
make the Bindings class abstract, and define a BTreeBindings class that
inherits from it and is (currently always) returned from the static
initializer. The idea is that we'll have an ArrayBindings class as well
later that we can dispatch to conditionally based on an optional
"capacity" parameter or something like that.

There was some difficulty here in getting the iterator to work - the
approach we settled on ended up making a concrete BindingsIterator class
which will wrap a std::variant of either a btree iterator or something
else later, but right now just wraps a btree iterator.

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

1 files changed, 52 insertions, 14 deletions

diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc
index 42ebe629b2..3d1005fd0f 100644
--- a/third_party/nix/src/libexpr/attr-set.cc
+++ b/third_party/nix/src/libexpr/attr-set.cc
@@ -10,6 +10,42 @@
 
 namespace nix {
 
+BindingsIterator& BindingsIterator::operator++() {
+  _iterator++;
+  return *this;
+}
+BindingsIterator BindingsIterator::operator++(int) {
+  ++_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;
+}
+
+class BTreeBindings : public Bindings {
+ public:
+  size_t size() override;
+  bool empty() override;
+  void push_back(const Attr& attr) override;
+  void insert_or_assign(const 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:
+  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.
@@ -20,7 +56,7 @@ namespace nix {
 //
 // This behaviour is mimicked by using .insert(), which will *not*
 // override existing values.
-void Bindings::push_back(const Attr& attr) {
+void BTreeBindings::push_back(const Attr& attr) {
   auto [_, inserted] = attributes_.insert({attr.name, attr});
 
   if (!inserted) {
@@ -30,15 +66,15 @@ void Bindings::push_back(const Attr& attr) {
 }
 
 // Insert or assign (i.e. replace) a value in the attribute set.
-void Bindings::insert_or_assign(const Attr& attr) {
+void BTreeBindings::insert_or_assign(const Attr& attr) {
   attributes_.insert_or_assign(attr.name, attr);
 }
 
-size_t Bindings::size() { return attributes_.size(); }
+size_t BTreeBindings::size() { return attributes_.size(); }
 
-bool Bindings::empty() { return attributes_.empty(); }
+bool BTreeBindings::empty() { return attributes_.empty(); }
 
-std::vector<const Attr*> Bindings::lexicographicOrder() {
+std::vector<const Attr*> BTreeBindings::lexicographicOrder() {
   std::vector<const Attr*> res;
   res.reserve(attributes_.size());
 
@@ -49,26 +85,28 @@ std::vector<const Attr*> Bindings::lexicographicOrder() {
   return res;
 }
 
-Bindings::iterator Bindings::find(const Symbol& name) {
-  return attributes_.find(name);
+Bindings::iterator BTreeBindings::find(const Symbol& name) {
+  return BindingsIterator{attributes_.find(name)};
 }
 
-Bindings::iterator Bindings::begin() { return attributes_.begin(); }
+Bindings::iterator BTreeBindings::begin() {
+  return BindingsIterator{attributes_.begin()};
+}
 
-Bindings::iterator Bindings::end() { return attributes_.end(); }
+Bindings::iterator BTreeBindings::end() {
+  return BindingsIterator{attributes_.end()};
+}
 
-void Bindings::merge(const Bindings& other) {
-  for (auto& [key, value] : other.attributes_) {
+void BTreeBindings::merge(Bindings& other) {
+  for (auto& [key, value] : other) {
     this->attributes_.insert_or_assign(key, value);
   }
 }
 
-Bindings* Bindings::NewGC() { return new (GC) Bindings; }
-
 void EvalState::mkAttrs(Value& v, size_t capacity) {
   clearValue(v);
   v.type = tAttrs;
-  v.attrs = Bindings::NewGC();
+  v.attrs = BTreeBindings::NewGC();
   nrAttrsets++;
   nrAttrsInAttrsets += capacity;
 }