From 28e347effe1ba4325fc485e920bda45c838e0450 Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Thu, 21 May 2020 19:20:24 +0100 Subject: refactor(3p/nix/libexpr): Use absl::btree_map for AttrSets This is the first step towards replacing the implementation of attribute sets with an absl::btree_map. Currently many access are done using array offsets and pointer arithmetic, so this change is currently causing Nix to fail in various ways. --- third_party/nix/meson.build | 1 + third_party/nix/src/libexpr/attr-set.cc | 49 ++++++++++++++----- third_party/nix/src/libexpr/attr-set.hh | 83 ++++++++++++++------------------- third_party/nix/src/libexpr/eval.cc | 16 ++++--- third_party/nix/src/libexpr/eval.hh | 2 +- third_party/nix/src/libexpr/nixexpr.cc | 2 +- 6 files changed, 85 insertions(+), 68 deletions(-) (limited to 'third_party') diff --git a/third_party/nix/meson.build b/third_party/nix/meson.build index 1b5e030bde82..8e845c20e281 100644 --- a/third_party/nix/meson.build +++ b/third_party/nix/meson.build @@ -354,6 +354,7 @@ absl_deps = [ absl.dependency('algorithm_container'), absl.dependency('base'), absl.dependency('bits'), + absl.dependency('btree'), absl.dependency('city'), absl.dependency('config'), absl.dependency('container_common'), diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc index fe1bf080edcb..8b2af8639eff 100644 --- a/third_party/nix/src/libexpr/attr-set.cc +++ b/third_party/nix/src/libexpr/attr-set.cc @@ -1,22 +1,49 @@ #include "attr-set.hh" -#include +#include #include "eval-inline.hh" namespace nix { -/* Allocate a new array of attributes for an attribute set with a specific - capacity. The space is implicitly reserved after the Bindings - structure. */ -Bindings* EvalState::allocBindings(size_t capacity) { - if (capacity > std::numeric_limits::max()) { - throw Error("attribute set of size %d is too big", capacity); +// TODO: using insert_or_assign might break existing Nix code because +// of the weird ordering situation. Need to investigate. +void Bindings::push_back(const Attr& attr) { + attributes_.insert_or_assign(attr.name, attr); +} + +size_t Bindings::size() { return attributes_.size(); } + +void Bindings::sort() {} +size_t Bindings::capacity() { return 0; } + +bool Bindings::empty() { return attributes_.empty(); } + +std::vector Bindings::lexicographicOrder() { + std::vector res; + res.reserve(attributes_.size()); + + for (const auto& [key, value] : attributes_) { + res.emplace_back(&value); } - return new (allocBytes(sizeof(Bindings) + sizeof(Attr) * capacity)) - Bindings((Bindings::size_t)capacity); + + return res; +} + +Bindings::iterator Bindings::find(const Symbol& name) { + return &attributes_[name]; } +Bindings::iterator Bindings::begin() { return &(attributes_.begin()->second); } + +Bindings::iterator Bindings::end() { return &(attributes_.end()->second); } + +// /* Allocate a new array of attributes for an attribute set with a specific +// capacity. The space is implicitly reserved after the Bindings structure. +// */ +Bindings* EvalState::allocBindings(size_t _capacity) { return new Bindings; } + +// TODO(tazjin): What's Value? What's going on here? void EvalState::mkAttrs(Value& v, size_t capacity) { if (capacity == 0) { v = vEmptySet; @@ -24,7 +51,7 @@ void EvalState::mkAttrs(Value& v, size_t capacity) { } clearValue(v); v.type = tAttrs; - v.attrs = allocBindings(capacity); + v.attrs = new Bindings; nrAttrsets++; nrAttrsInAttrsets += capacity; } @@ -38,6 +65,6 @@ Value* EvalState::allocAttr(Value& vAttrs, const Symbol& name) { return v; } -void Bindings::sort() { std::sort(begin(), end()); } +// void Bindings::sort() { std::sort(begin(), end()); } } // namespace nix diff --git a/third_party/nix/src/libexpr/attr-set.hh b/third_party/nix/src/libexpr/attr-set.hh index 5357e58a1dec..551cddaae4eb 100644 --- a/third_party/nix/src/libexpr/attr-set.hh +++ b/third_party/nix/src/libexpr/attr-set.hh @@ -1,12 +1,13 @@ +// This file implements the underlying structure of Nix attribute sets. #pragma once -#include +#include #include "nixexpr.hh" #include "symbol-table.hh" #include "types.hh" // TODO(tazjin): audit this include -namespace nix { +namespace nix { // TODO(tazjin): ::expr class EvalState; struct Value; @@ -22,65 +23,49 @@ struct Attr { bool operator<(const Attr& a) const { return name < a.name; } }; -/* Bindings contains all the attributes of an attribute set. It is defined - by its size and its capacity, the capacity being the number of Attr - elements allocated after this structure, while the size corresponds to - the number of elements already inserted in this structure. */ -class Bindings { - public: - typedef uint32_t size_t; - - private: - size_t size_, capacity_; - Attr attrs[0]; - - Bindings(size_t capacity) : size_(0), capacity_(capacity) {} - Bindings(const Bindings& bindings) = delete; +// TODO: remove this, it only exists briefly while I get rid of the +// current Attr struct +inline bool operator==(const Attr& lhs, const Attr& rhs) { + return lhs.name == rhs.name; +} +class Bindings { public: - size_t size() const { return size_; } + typedef Attr* iterator; // TODO: type, and also 'using'? - bool empty() const { return !size_; } + // Return the number of contained elements. + size_t size(); - typedef Attr* iterator; + // Is this attribute set empty? + bool empty(); - void push_back(const Attr& attr) { - assert(size_ < capacity_); - attrs[size_++] = attr; - } + // TODO(tazjin): rename + // TODO(tazjin): does this need to copy? + void push_back(const Attr& attr); - iterator find(const Symbol& name) { - Attr key(name, 0); - iterator i = std::lower_bound(begin(), end(), key); - if (i != end() && i->name == name) { - return i; - } - return end(); - } + // Look up a specific element of the attribute set. + iterator find(const Symbol& name); - iterator begin() { return &attrs[0]; } - iterator end() { return &attrs[size_]; } + // TODO + iterator begin(); + iterator end(); - Attr& operator[](size_t pos) { return attrs[pos]; } + // ??? + [[deprecated]] void sort(); - void sort(); + // ??? + [[deprecated]] size_t capacity(); - size_t capacity() { return capacity_; } + // oh no + // Attr& operator[](size_t pos); // { return attrs[pos]; } - /* Returns the attributes in lexicographically sorted order. */ - std::vector lexicographicOrder() const { - std::vector res; - res.reserve(size_); - for (size_t n = 0; n < size_; n++) { - res.emplace_back(&attrs[n]); - } - std::sort(res.begin(), res.end(), [](const Attr* a, const Attr* b) { - return (const std::string&)a->name < (const std::string&)b->name; - }); - return res; - } + // TODO: can callers just iterate? + [[deprecated]] std::vector lexicographicOrder(); + // oh no friend class EvalState; -}; + private: + absl::btree_map attributes_; +}; } // namespace nix diff --git a/third_party/nix/src/libexpr/eval.cc b/third_party/nix/src/libexpr/eval.cc index 875dab2ee709..760bada7b0bf 100644 --- a/third_party/nix/src/libexpr/eval.cc +++ b/third_party/nix/src/libexpr/eval.cc @@ -827,7 +827,8 @@ void ExprAttrs::eval(EvalState& state, Env& env, Value& v) { env2.up = &env; dynamicEnv = &env2; - auto overrides = attrs.find(state.sOverrides); + // TODO(tazjin): contains? + AttrDefs::iterator overrides = attrs.find(state.sOverrides); bool hasOverrides = overrides != attrs.end(); /* The recursive attributes are evaluated in the new @@ -855,17 +856,19 @@ void ExprAttrs::eval(EvalState& state, Env& env, Value& v) { been substituted into the bodies of the other attributes. Hence we need __overrides.) */ if (hasOverrides) { - Value* vOverrides = (*v.attrs)[overrides->second.displ].value; + Value* vOverrides = + v.attrs->find(overrides->first) + ->value; //(*v.attrs)[overrides->second.displ].value; state.forceAttrs(*vOverrides); - Bindings* newBnds = - state.allocBindings(v.attrs->capacity() + vOverrides->attrs->size()); - for (auto& i : *v.attrs) { + Bindings* newBnds = state.allocBindings(/* capacity = */ 0); + for (auto& i : *v.attrs) { // TODO(tazjin): copy constructor? newBnds->push_back(i); } for (auto& i : *vOverrides->attrs) { auto j = attrs.find(i.name); if (j != attrs.end()) { - (*newBnds)[j->second.displ] = i; + newBnds->push_back(i); + // (*newBnds)[j->second.displ] = i; env2.values[j->second.displ] = i.value; } else { newBnds->push_back(i); @@ -875,6 +878,7 @@ void ExprAttrs::eval(EvalState& state, Env& env, Value& v) { v.attrs = newBnds; } } else { + // TODO(tazjin): insert range for (auto& i : attrs) { v.attrs->push_back( Attr(i.first, i.second.e->maybeThunk(state, env), &i.second.pos)); diff --git a/third_party/nix/src/libexpr/eval.hh b/third_party/nix/src/libexpr/eval.hh index 055c4fda3702..bc07f9507087 100644 --- a/third_party/nix/src/libexpr/eval.hh +++ b/third_party/nix/src/libexpr/eval.hh @@ -258,7 +258,7 @@ class EvalState { Value* allocAttr(Value& vAttrs, const Symbol& name); - static Bindings* allocBindings(size_t capacity); + [[deprecated]] static Bindings* allocBindings(size_t capacity); void mkList(Value& v, size_t size); void mkAttrs(Value& v, size_t capacity); diff --git a/third_party/nix/src/libexpr/nixexpr.cc b/third_party/nix/src/libexpr/nixexpr.cc index 49b4a7ea419b..3d454d266ff0 100644 --- a/third_party/nix/src/libexpr/nixexpr.cc +++ b/third_party/nix/src/libexpr/nixexpr.cc @@ -285,7 +285,7 @@ void ExprOpHasAttr::bindVars(const StaticEnv& env) { void ExprAttrs::bindVars(const StaticEnv& env) { const StaticEnv* dynamicEnv = &env; - StaticEnv newEnv(false, &env); + StaticEnv newEnv(/* isWith = */ false, &env); if (recursive) { dynamicEnv = &newEnv; -- cgit 1.4.1