From 91bd7ce73ab7eacaf995090014f67391624531c1 Mon Sep 17 00:00:00 2001
From: Vincent Ambo <mail@tazj.in>
Date: Thu, 6 Aug 2020 03:01:57 +0100
Subject: refactor(tvix): Use absl::btree_map for DerivationOutputs

This container implementation is much faster than std::map. We have
stuck to an ordered container because it's unclear whether the
accesses of this field (of which there are *many*) are actually
ordering dependent.

Also includes an Arbitrary implementation for absl::btree_map (for any
K, V that are also Arbitrary).

Change-Id: I04f58ca0ce32b9ae1759313b01508b0e44bae793
Reviewed-on: https://cl.tvl.fyi/c/depot/+/1683
Reviewed-by: glittershark <grfn@gws.fyi>
Tested-by: BuildkiteCI
---
 third_party/nix/src/tests/attr-set.cc         |  1 +
 third_party/nix/src/tests/derivations_test.cc | 11 +++++++++++
 2 files changed, 12 insertions(+)

(limited to 'third_party/nix/src/tests')

diff --git a/third_party/nix/src/tests/attr-set.cc b/third_party/nix/src/tests/attr-set.cc
index ae323e6bd3d3..17234f6b316b 100644
--- a/third_party/nix/src/tests/attr-set.cc
+++ b/third_party/nix/src/tests/attr-set.cc
@@ -5,6 +5,7 @@
 #include <string>
 #include <vector>
 
+#include <absl/container/btree_map.h>
 #include <bits/stdint-intn.h>
 #include <gc/gc_cpp.h>
 #include <gtest/gtest.h>
diff --git a/third_party/nix/src/tests/derivations_test.cc b/third_party/nix/src/tests/derivations_test.cc
index 1e2719addaf1..63e2c3070e3e 100644
--- a/third_party/nix/src/tests/derivations_test.cc
+++ b/third_party/nix/src/tests/derivations_test.cc
@@ -22,6 +22,17 @@ namespace rc {
 using nix::Derivation;
 using nix::DerivationOutput;
 
+template <class K, class V>
+struct Arbitrary<absl::btree_map<K, V>> {
+  static Gen<absl::btree_map<K, V>> arbitrary() {
+    return gen::map(gen::arbitrary<std::map<K, V>>(), [](std::map<K, V> map) {
+      absl::btree_map<K, V> out_map;
+      out_map.insert(map.begin(), map.end());
+      return out_map;
+    });
+  }
+};
+
 template <>
 struct Arbitrary<nix::Base> {
   static Gen<nix::Base> arbitrary() {
-- 
cgit 1.4.1