about summary refs log tree commit diff
diff options
context:
space:
mode:
authorVincent Ambo <mail@tazj.in>2020-07-13T23·33+0100
committertazjin <mail@tazj.in>2020-07-13T23·51+0000
commitc5de35ee62b3eb85cfc9aeaf4cdf0b510d69c6fa (patch)
treed635a3b29d2fd0fe82fd165b1f29a4abb094ab1b
parent6166c9daf2bf5bc280125d602a7bd372043a58f4 (diff)
refactor(3p/nix/libexpr): Backport upstream VectorBindings merge sort r/1289
Since one of the two implementations essentially uses the same shape
as the upstream Bindings, we backport their merge sort implementation
to ensure that we're doing the same thing semantically.

Paired-With: Luke Granger-Brown <git@lukegb.com>
Paired-With: Vincent Ambo <mail@tazj.in>
Paired-With: Perry Lorier <isomer@tvl.fyi>
Change-Id: I0d865897991eec0c4dd84d9bd0415cd1ca437792
Reviewed-on: https://cl.tvl.fyi/c/depot/+/1162
Tested-by: BuildkiteCI
Reviewed-by: lukegb <lukegb@tvl.fyi>
Reviewed-by: glittershark <grfn@gws.fyi>
-rw-r--r--third_party/nix/src/libexpr/attr-set.cc45
1 files changed, 28 insertions, 17 deletions
diff --git a/third_party/nix/src/libexpr/attr-set.cc b/third_party/nix/src/libexpr/attr-set.cc
index 31b5bdcef3b1..ddfdbef36147 100644
--- a/third_party/nix/src/libexpr/attr-set.cc
+++ b/third_party/nix/src/libexpr/attr-set.cc
@@ -158,39 +158,51 @@ 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++));
+  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 {
-      if (m_it->first == other_it->first) {
-        ++m_it;
-      }
-      new_attributes.push_back(*(other_it++));
+      new_attributes.push_back(*rhs++);
     }
   }
 
-  if (m_it != attributes_.end()) {
-    std::copy(m_it, attributes_.end(), std::back_inserter(new_attributes));
+  while (lhs != attributes_.end()) {
+    new_attributes.push_back(*lhs++);
   }
 
-  if (other_it != other.end()) {
-    std::copy(other_it, other.end(), std::back_inserter(new_attributes));
+  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(attributes_.size());
+  std::vector<const Attr*> result;
+  result.reserve(attributes_.size());
 
   for (auto& [_, attr] : attributes_) {
     result.push_back(&attr);
@@ -240,5 +252,4 @@ Value* EvalState::allocAttr(Value& vAttrs, const Symbol& name) {
   return v;
 }
 
-
 }  // namespace nix