about summary refs log tree commit diff
path: root/third_party
diff options
context:
space:
mode:
Diffstat (limited to 'third_party')
-rw-r--r--third_party/nix/src/libexpr/attr-set.cc199
-rw-r--r--third_party/nix/src/libexpr/attr-set.hh66
-rw-r--r--third_party/nix/tests/lang.sh2
3 files changed, 30 insertions, 237 deletions
diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc
index ddfdbef361..c1b86387be 100644
--- a/third_party/nix/src/libexpr/attr-set.cc
+++ b/third_party/nix/src/libexpr/attr-set.cc
@@ -7,76 +7,9 @@
 #include <glog/logging.h>
 
 #include "libexpr/eval-inline.hh"
-#include "libutil/visitor.hh"
 
 namespace nix {
 
-constexpr size_t ATTRS_CAPACITY_PIVOT = 32;
-
-BindingsIterator& BindingsIterator::operator++() {
-  std::visit(util::overloaded{
-                 [](AttributeMap::iterator& iter) { ++iter; },
-                 [](AttributeVector::iterator& iter) { ++iter; },
-             },
-             _iterator);
-  return *this;
-}
-
-BindingsIterator BindingsIterator::operator++(int) {
-  auto old = *this;
-  std::visit(util::overloaded{
-                 [](AttributeMap::iterator& iter) { iter++; },
-                 [](AttributeVector::iterator& iter) { iter++; },
-             },
-             _iterator);
-  return old;
-}
-
-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 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 {
- public:
-  size_t size() override;
-  bool empty() override;
-  void push_back(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_;
-};
-
 // This function inherits its name from previous implementations, in
 // which Bindings was backed by an array of elements which was scanned
 // linearly.
@@ -87,7 +20,7 @@ class BTreeBindings : public Bindings {
 //
 // This behaviour is mimicked by using .insert(), which will *not*
 // override existing values.
-void BTreeBindings::push_back(const Attr& attr) {
+void Bindings::push_back(const Attr& attr) {
   auto [_, inserted] = attributes_.insert({attr.name, attr});
 
   if (!inserted) {
@@ -96,11 +29,11 @@ void BTreeBindings::push_back(const Attr& attr) {
   }
 }
 
-size_t BTreeBindings::size() { return attributes_.size(); }
+size_t Bindings::size() { return attributes_.size(); }
 
-bool BTreeBindings::empty() { return attributes_.empty(); }
+bool Bindings::empty() { return attributes_.empty(); }
 
-std::vector<const Attr*> BTreeBindings::lexicographicOrder() {
+std::vector<const Attr*> Bindings::lexicographicOrder() {
   std::vector<const Attr*> res;
   res.reserve(attributes_.size());
 
@@ -111,134 +44,28 @@ std::vector<const Attr*> BTreeBindings::lexicographicOrder() {
   return res;
 }
 
-Bindings::iterator BTreeBindings::find(const Symbol& name) {
-  return BindingsIterator{attributes_.find(name)};
+Bindings::iterator Bindings::find(const Symbol& name) {
+  return attributes_.find(name);
 }
 
-Bindings::iterator BTreeBindings::begin() {
-  return BindingsIterator{attributes_.begin()};
-}
+Bindings::iterator Bindings::begin() { return attributes_.begin(); }
 
-Bindings::iterator BTreeBindings::end() {
-  return BindingsIterator{attributes_.end()};
-}
+Bindings::iterator Bindings::end() { return attributes_.end(); }
 
-void BTreeBindings::merge(Bindings& other) {
-  for (auto& [key, value] : other) {
+void Bindings::merge(const Bindings& other) {
+  for (auto& [key, value] : other.attributes_) {
     this->attributes_.insert_or_assign(key, value);
   }
 }
 
-class VectorBindings : public Bindings {
- public:
-  VectorBindings(size_t capacity) : attributes_() {
-    attributes_.reserve(capacity);
-  };
-
-  size_t size() override;
-  bool empty() override;
-  void push_back(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;
-
-  VectorBindings(VectorBindings&) = delete;
-
- private:
-  AttributeVector attributes_;
-};
-
-size_t VectorBindings::size() { return attributes_.size(); }
-
-bool VectorBindings::empty() { return attributes_.empty(); }
-
-void VectorBindings::merge(Bindings& other) {
-  AttributeVector new_attributes;
-  new_attributes.reserve(size() + other.size());
-
-  auto lhs = attributes_.begin();
-  auto rhs = other.begin();
-
-  while (lhs != attributes_.end() && rhs != other.end()) {
-    if (lhs->first == rhs->first) {
-      new_attributes.push_back(*rhs);
-      ++lhs;
-      ++rhs;
-    } else if (lhs->first < rhs->first) {
-      new_attributes.push_back(*lhs++);
-    } else {
-      new_attributes.push_back(*rhs++);
-    }
-  }
-
-  while (lhs != attributes_.end()) {
-    new_attributes.push_back(*lhs++);
-  }
-
-  while (rhs != other.end()) {
-    new_attributes.push_back(*rhs++);
-  }
-
-  new_attributes.shrink_to_fit();
-  attributes_ = new_attributes;
-}
-
-// Insert or assign (i.e. replace) a value in the attribute set.
-void VectorBindings::push_back(const 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) {
-      attributes_.emplace(it, attr.name, attr);
-      return;
-    }
-  }
-
-  attributes_.emplace_back(attr.name, attr);
-}
-
-std::vector<const Attr*> VectorBindings::lexicographicOrder() {
-  std::vector<const Attr*> result;
-  result.reserve(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()};
-}
-
-Bindings* Bindings::NewGC(size_t capacity) {
-  if (capacity > ATTRS_CAPACITY_PIVOT) {
-    return new (GC) BTreeBindings;
-  } else {
-    return new (GC) VectorBindings(capacity);
-  }
+Bindings* Bindings::NewGC(size_t _capacity) {
+  return new (GC) Bindings;
 }
 
 void EvalState::mkAttrs(Value& v, size_t capacity) {
   clearValue(v);
   v.type = tAttrs;
-  v.attrs = Bindings::NewGC(capacity);
-  assert(v.attrs->begin() == v.attrs->begin());
-  assert(v.attrs->end() == v.attrs->end());
+  v.attrs = Bindings::NewGC();
   nrAttrsets++;
   nrAttrsInAttrsets += capacity;
 }
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
diff --git a/third_party/nix/tests/lang.sh b/third_party/nix/tests/lang.sh
index c797a2a74e..151a713166 100644
--- a/third_party/nix/tests/lang.sh
+++ b/third_party/nix/tests/lang.sh
@@ -1,5 +1,3 @@
-source common.sh
-
 export TEST_VAR=foo # for eval-okay-getenv.nix
 
 nix-instantiate --eval -E 'builtins.trace "Hello" 123' 2>&1 | grep -q Hello
generated by cgit-pink 1.4.1 (git 2.44.0) at 2024-06-02T18ยท44+0000