diff options
| -rw-r--r-- | third_party/nix/src/libexpr/attr-set.cc | 146 | ||||
| -rw-r--r-- | third_party/nix/src/libexpr/attr-set.hh | 20 |
2 files changed, 150 insertions, 16 deletions
diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc index 3d1005fd0f7f..053d7d6f6c5e 100644 --- a/third_party/nix/src/libexpr/attr-set.cc +++ b/third_party/nix/src/libexpr/attr-set.cc @@ -7,25 +7,56 @@ #include <glog/logging.h> #include "libexpr/eval-inline.hh" +#include "libutil/visitor.hh" namespace nix { BindingsIterator& BindingsIterator::operator++() { - _iterator++; + std::visit(util::overloaded{ + [](AttributeMap::iterator& iter) { ++iter; }, + [](AttributeVector::iterator& iter) { ++iter; }, + }, + _iterator); return *this; } + BindingsIterator BindingsIterator::operator++(int) { - ++_iterator; + std::visit(util::overloaded{ + [](AttributeMap::iterator& iter) { iter++; }, + [](AttributeVector::iterator& iter) { iter++; }, + }, + _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; + 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 { @@ -33,7 +64,7 @@ class BTreeBindings : public Bindings { size_t size() override; bool empty() override; void push_back(const Attr& attr) override; - void insert_or_assign(const Attr& attr) override; + void insert_or_assign(Attr& attr) override; Bindings::iterator find(const Symbol& name) override; Bindings::iterator begin() override; Bindings::iterator end() override; @@ -44,8 +75,6 @@ class BTreeBindings : public Bindings { 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. @@ -66,7 +95,7 @@ void BTreeBindings::push_back(const Attr& attr) { } // Insert or assign (i.e. replace) a value in the attribute set. -void BTreeBindings::insert_or_assign(const Attr& attr) { +void BTreeBindings::insert_or_assign(Attr& attr) { attributes_.insert_or_assign(attr.name, attr); } @@ -106,7 +135,9 @@ void BTreeBindings::merge(Bindings& other) { void EvalState::mkAttrs(Value& v, size_t capacity) { clearValue(v); v.type = tAttrs; - v.attrs = BTreeBindings::NewGC(); + v.attrs = Bindings::NewGC(); + assert(v.attrs->begin() == v.attrs->begin()); + assert(v.attrs->end() == v.attrs->end()); nrAttrsets++; nrAttrsInAttrsets += capacity; } @@ -120,4 +151,103 @@ Value* EvalState::allocAttr(Value& vAttrs, const Symbol& name) { return v; } +class VectorBindings : public Bindings { + public: + size_t size() override; + bool empty() override; + void push_back(const Attr& attr) override; + void insert_or_assign(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: + AttributeVector attributes_; +}; + +size_t VectorBindings::size() { return attributes_.size(); } + +bool VectorBindings::empty() { return attributes_.empty(); } + +// Insert or assign (i.e. replace) a value in the attribute set. +void VectorBindings::insert_or_assign(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) { + // TODO convert to BTreeMap if we get big enough + attributes_.emplace(it, attr.name, attr); + return; + } + } + + attributes_.emplace_back(attr.name, attr); +} + +void VectorBindings::merge(Bindings& other) { + AttributeVector new_attributes; + new_attributes.reserve(size() + other.size()); + + auto m_it = attributes_.begin(); + auto other_it = other.begin(); + + while (other_it != other.end() && m_it != attributes_.end()) { + if (other_it->first < m_it->first) { + new_attributes.push_back(*(m_it++)); + } else { + if (m_it->first == other_it->first) { + ++m_it; + } + new_attributes.push_back(*(other_it++)); + } + } + + if (m_it != attributes_.end()) { + std::copy(m_it, attributes_.end(), std::back_inserter(new_attributes)); + } + + if (other_it != other.end()) { + std::copy(other_it, other.end(), std::back_inserter(new_attributes)); + } + + new_attributes.shrink_to_fit(); + + attributes_ = new_attributes; +} + +void VectorBindings::push_back(const Attr& attr) { + attributes_.emplace_back(attr.name, attr); +} + +std::vector<const Attr*> VectorBindings::lexicographicOrder() { + std::vector<const Attr*> result(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()}; +} + +// TODO pick what to do based on size +Bindings* Bindings::NewGC() { return new (GC) BTreeBindings; } +// Bindings* Bindings::NewGC() { return new (GC) VectorBindings; } + } // namespace nix diff --git a/third_party/nix/src/libexpr/attr-set.hh b/third_party/nix/src/libexpr/attr-set.hh index 06ae8f4b0723..3834eac419e1 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 |