diff options
Diffstat (limited to 'third_party/nix/src/libexpr')
| -rw-r--r-- | third_party/nix/src/libexpr/attr-set.cc | 199 | ||||
| -rw-r--r-- | third_party/nix/src/libexpr/attr-set.hh | 66 |
2 files changed, 30 insertions, 235 deletions
diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc index ddfdbef36147..c1b86387be8e 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 795ee2337fc7..f0b1448ba2f2 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 |