From 91465dc78ec7b4a8c9b651657bb8ad5f25c556a7 Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Thu, 29 Dec 2022 17:08:14 +0300 Subject: refactor(tvix/eval): persistent, memory-sharing OrdMap for NixAttrs This uses the `im::OrdMap` for `NixAttrs` to enable sharing of memory between different iterations of a map. This slightly speeds up eval, but not significantly. Future work might include benchmarking whether using a `HashMap` and only ordering in cases where order is actually required would help. This switches to a fork of `im` that fixes some bugs with its OrdMap implementation. Change-Id: I2f6a5ff471b6d508c1e8a98b13f889f49c0d9537 Reviewed-on: https://cl.tvl.fyi/c/depot/+/7676 Reviewed-by: sterni Tested-by: BuildkiteCI --- corp/tvixbolt/Cargo.lock | 43 ++++----- tvix/Cargo.lock | 37 ++++---- tvix/Cargo.nix | 89 ++++++++---------- tvix/eval/Cargo.toml | 2 +- tvix/eval/src/builtins/mod.rs | 24 ++--- .../tests/tvix_tests/eval-okay-functionargs.nix | 10 +- tvix/eval/src/value/attrs.rs | 101 ++++++++++----------- tvix/eval/src/value/attrs/tests.rs | 2 +- tvix/eval/src/value/list.rs | 6 +- tvix/eval/src/value/mod.rs | 2 +- 10 files changed, 144 insertions(+), 172 deletions(-) diff --git a/corp/tvixbolt/Cargo.lock b/corp/tvixbolt/Cargo.lock index 41bd8a315f4a..8225e059fa17 100644 --- a/corp/tvixbolt/Cargo.lock +++ b/corp/tvixbolt/Cargo.lock @@ -36,12 +36,9 @@ checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" [[package]] name = "bitmaps" -version = "2.1.0" +version = "3.2.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "031043d04099746d8db04daf1fa424b2bc8bd69d92b25962dcde24da39ab64a2" -dependencies = [ - "typenum", -] +checksum = "703642b98a00b3b90513279a8ede3fcfa479c126c5fb46e78f3051522f021403" [[package]] name = "boolinator" @@ -283,19 +280,27 @@ dependencies = [ ] [[package]] -name = "im" -version = "15.1.0" +name = "imbl" +version = "2.0.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d0acd33ff0285af998aaf9b57342af478078f53492322fafc47450e09397e0e9" +checksum = "c2806b69cd9f4664844027b64465eacb444c67c1db9c778e341adff0c25cdb0d" dependencies = [ "bitmaps", + "imbl-sized-chunks", "rand_core", "rand_xoshiro", - "sized-chunks", - "typenum", "version_check", ] +[[package]] +name = "imbl-sized-chunks" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6957ea0b2541c5ca561d3ef4538044af79f8a05a1eb3a3b148936aaceaa1076" +dependencies = [ + "bitmaps", +] + [[package]] name = "indexmap" version = "1.9.1" @@ -570,16 +575,6 @@ dependencies = [ "serde", ] -[[package]] -name = "sized-chunks" -version = "0.6.5" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "16d69225bde7a69b235da73377861095455d298f2b970996eec25ddbb42b3d1e" -dependencies = [ - "bitmaps", - "typenum", -] - [[package]] name = "slab" version = "0.4.7" @@ -660,7 +655,7 @@ dependencies = [ "codemap", "codemap-diagnostic", "dirs", - "im", + "imbl", "path-clean", "regex", "rnix", @@ -696,12 +691,6 @@ dependencies = [ "yew-router", ] -[[package]] -name = "typenum" -version = "1.16.0" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "497961ef93d974e23eb6f433eb5fe1b7930b659f06d12dec6fc44a8f554c0bba" - [[package]] name = "unicode-ident" version = "1.0.4" diff --git a/tvix/Cargo.lock b/tvix/Cargo.lock index a3b91e534f33..f2c0e391caf3 100644 --- a/tvix/Cargo.lock +++ b/tvix/Cargo.lock @@ -185,12 +185,9 @@ checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" [[package]] name = "bitmaps" -version = "2.1.0" +version = "3.2.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "031043d04099746d8db04daf1fa424b2bc8bd69d92b25962dcde24da39ab64a2" -dependencies = [ - "typenum", -] +checksum = "703642b98a00b3b90513279a8ede3fcfa479c126c5fb46e78f3051522f021403" [[package]] name = "blake3" @@ -829,19 +826,27 @@ dependencies = [ ] [[package]] -name = "im" -version = "15.1.0" +name = "imbl" +version = "2.0.0" source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "d0acd33ff0285af998aaf9b57342af478078f53492322fafc47450e09397e0e9" +checksum = "c2806b69cd9f4664844027b64465eacb444c67c1db9c778e341adff0c25cdb0d" dependencies = [ "bitmaps", + "imbl-sized-chunks", "rand_core 0.6.4", "rand_xoshiro", - "sized-chunks", - "typenum", "version_check", ] +[[package]] +name = "imbl-sized-chunks" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e6957ea0b2541c5ca561d3ef4538044af79f8a05a1eb3a3b148936aaceaa1076" +dependencies = [ + "bitmaps", +] + [[package]] name = "indexmap" version = "1.9.2" @@ -1635,16 +1640,6 @@ dependencies = [ "serde", ] -[[package]] -name = "sized-chunks" -version = "0.6.5" -source = "registry+https://github.com/rust-lang/crates.io-index" -checksum = "16d69225bde7a69b235da73377861095455d298f2b970996eec25ddbb42b3d1e" -dependencies = [ - "bitmaps", - "typenum", -] - [[package]] name = "slab" version = "0.4.7" @@ -2083,7 +2078,7 @@ dependencies = [ "codemap-diagnostic", "criterion", "dirs", - "im", + "imbl", "itertools", "path-clean", "pretty_assertions", diff --git a/tvix/Cargo.nix b/tvix/Cargo.nix index fdc93f248b2d..a72a8d3277f0 100644 --- a/tvix/Cargo.nix +++ b/tvix/Cargo.nix @@ -656,18 +656,12 @@ rec { }; "bitmaps" = rec { crateName = "bitmaps"; - version = "2.1.0"; - edition = "2018"; - sha256 = "18k4mcwxl96yvii5kcljkpb8pg5j4jj1zbsdn26nsx4r83846403"; + version = "3.2.0"; + edition = "2021"; + sha256 = "00ql08pm4l9hizkldyy54v0pk96g7zg8x6i72c2vkcq0iawl4dkh"; authors = [ "Bodil Stokke " ]; - dependencies = [ - { - name = "typenum"; - packageId = "typenum"; - } - ]; features = { "default" = [ "std" ]; }; @@ -2423,19 +2417,24 @@ rec { ]; }; - "im" = rec { - crateName = "im"; - version = "15.1.0"; + "imbl" = rec { + crateName = "imbl"; + version = "2.0.0"; edition = "2018"; - sha256 = "1sg0jy9y0l3lqjpjyclj6kspi027mx177dgrmacgjni8y0zx7b6h"; + sha256 = "03fvbk1g1pqs6j77g76vq5klqi6bx9jl9di782268ilzrmlnp062"; authors = [ "Bodil Stokke " + "Joe Neeman " ]; dependencies = [ { name = "bitmaps"; packageId = "bitmaps"; } + { + name = "imbl-sized-chunks"; + packageId = "imbl-sized-chunks"; + } { name = "rand_core"; packageId = "rand_core 0.6.4"; @@ -2444,14 +2443,6 @@ rec { name = "rand_xoshiro"; packageId = "rand_xoshiro"; } - { - name = "sized-chunks"; - packageId = "sized-chunks"; - } - { - name = "typenum"; - packageId = "typenum"; - } ]; buildDependencies = [ { @@ -2468,6 +2459,31 @@ rec { "serde" = [ "dep:serde" ]; }; }; + "imbl-sized-chunks" = rec { + crateName = "imbl-sized-chunks"; + version = "0.1.1"; + edition = "2021"; + sha256 = "0xhhmb7aldl92hxkmsx10n59zxsa0hw4bvykc6jmq72lnah7x5g6"; + authors = [ + "Bodil Stokke " + "Joe Neeman " + ]; + dependencies = [ + { + name = "bitmaps"; + packageId = "bitmaps"; + usesDefaultFeatures = false; + } + ]; + features = { + "arbitrary" = [ "dep:arbitrary" ]; + "array-ops" = [ "dep:array-ops" ]; + "default" = [ "std" ]; + "refpool" = [ "dep:refpool" ]; + "ringbuffer" = [ "array-ops" ]; + }; + resolvedDefaultFeatures = [ "default" "std" ]; + }; "indexmap" = rec { crateName = "indexmap"; version = "1.9.2"; @@ -4712,33 +4728,6 @@ rec { }; resolvedDefaultFeatures = [ "default" "std" ]; }; - "sized-chunks" = rec { - crateName = "sized-chunks"; - version = "0.6.5"; - edition = "2018"; - sha256 = "07ix5fsdnpf2xsb0k5rbiwlmsicm2237fcx7blirp9p7pljr5mhn"; - authors = [ - "Bodil Stokke " - ]; - dependencies = [ - { - name = "bitmaps"; - packageId = "bitmaps"; - } - { - name = "typenum"; - packageId = "typenum"; - } - ]; - features = { - "arbitrary" = [ "dep:arbitrary" ]; - "array-ops" = [ "dep:array-ops" ]; - "default" = [ "std" ]; - "refpool" = [ "dep:refpool" ]; - "ringbuffer" = [ "array-ops" ]; - }; - resolvedDefaultFeatures = [ "default" "std" ]; - }; "slab" = rec { crateName = "slab"; version = "0.4.7"; @@ -6185,8 +6174,8 @@ rec { packageId = "dirs"; } { - name = "im"; - packageId = "im"; + name = "imbl"; + packageId = "imbl"; } { name = "path-clean"; diff --git a/tvix/eval/Cargo.toml b/tvix/eval/Cargo.toml index dac605f3e1ae..b866ec2c715c 100644 --- a/tvix/eval/Cargo.toml +++ b/tvix/eval/Cargo.toml @@ -14,7 +14,7 @@ builtin-macros = { path = "./builtin-macros", package = "tvix-eval-builtin-macro codemap = "0.1.3" codemap-diagnostic = "0.1.1" dirs = "4.0.0" -im = "15.1" +imbl = "2.0" path-clean = "0.1" proptest = { version = "1.0.0", default_features = false, features = ["std", "alloc", "break-dead-code", "tempfile"], optional = true } regex = "1.6.0" diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs index 3708ed04d8ba..9f03cd85b8e4 100644 --- a/tvix/eval/src/builtins/mod.rs +++ b/tvix/eval/src/builtins/mod.rs @@ -187,14 +187,14 @@ mod pure_builtins { .collect::, ErrorKind>>()?; Ok(Value::List(NixList::from( - lists.into_iter().flatten().collect::>(), + lists.into_iter().flatten().collect::>(), ))) } #[builtin("concatMap")] fn builtin_concat_map(vm: &mut VM, f: Value, list: Value) -> Result { let list = list.to_list()?; - let mut res = im::Vector::new(); + let mut res = imbl::Vector::new(); for val in list { res.extend(vm.call_with(&f, [val])?.force(vm)?.to_list()?); } @@ -295,7 +295,7 @@ mod pure_builtins { result }) - .collect::, _>>() + .collect::, _>>() .map(|list| Value::List(NixList::from(list))) .map_err(Into::into) } @@ -356,7 +356,7 @@ mod pure_builtins { let operator = attrs.select_required("operator")?; - let mut res = im::Vector::new(); + let mut res = imbl::Vector::new(); let mut done_keys: Vec = vec![]; let mut insert_key = |k: Value, vm: &mut VM| -> Result { @@ -391,7 +391,7 @@ mod pure_builtins { let len = length.as_int()?; (0..len) .map(|i| vm.call_with(&generator, [i.into()])) - .collect::, _>>() + .collect::, _>>() .map(|list| Value::List(NixList::from(list))) .map_err(Into::into) } @@ -411,11 +411,11 @@ mod pure_builtins { #[builtin("groupBy")] fn builtin_group_by(vm: &mut VM, f: Value, list: Value) -> Result { - let mut res: BTreeMap> = BTreeMap::new(); + let mut res: BTreeMap> = BTreeMap::new(); for val in list.to_list()? { let key = vm.call_with(&f, [val.clone()])?.force(vm)?.to_str()?; res.entry(key) - .or_insert_with(im::Vector::new) + .or_insert_with(imbl::Vector::new) .push_back(val); } Ok(Value::attrs(NixAttrs::from_iter( @@ -550,7 +550,7 @@ mod pure_builtins { list.into_iter() .map(|val| vm.call_with(&f, [val])) - .collect::, _>>() + .collect::, _>>() .map(|list| Value::List(NixList::from(list))) .map_err(Into::into) } @@ -744,7 +744,7 @@ mod pure_builtins { let re: Regex = Regex::new(re.as_str()).unwrap(); let mut capture_locations = re.capture_locations(); let num_captures = capture_locations.len(); - let mut ret = im::Vector::new(); + let mut ret = imbl::Vector::new(); let mut pos = 0; while let Some(thematch) = re.captures_read_at(&mut capture_locations, text, pos) { @@ -755,7 +755,7 @@ mod pure_builtins { // group in the regex, containing the characters // matched by that capture group, or null if no match. // We skip capture 0; it represents the whole match. - let v: im::Vector = (1..num_captures) + let v: imbl::Vector = (1..num_captures) .map(|i| capture_locations.get(i)) .map(|o| { o.map(|(start, end)| Value::from(&text[start..end])) @@ -775,7 +775,7 @@ mod pure_builtins { #[builtin("sort")] fn builtin_sort(vm: &mut VM, comparator: Value, list: Value) -> Result { // TODO: the bound on the sort function in - // `im::Vector::sort_by` is `Fn(...)`, which means that we can + // `imbl::Vector::sort_by` is `Fn(...)`, which means that we can // not use the mutable VM inside of its closure, hence the // dance via `Vec`. I think this is just an unnecessarily // restrictive bound in `im`, not a functional requirement. @@ -810,7 +810,7 @@ mod pure_builtins { }); match error { - #[allow(deprecated)] // im::Vector usage prevented by its API + #[allow(deprecated)] // imbl::Vector usage prevented by its API None => Ok(Value::List(NixList::from_vec(list))), Some(e) => Err(e), } diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-functionargs.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-functionargs.nix index 68dca62ee18d..cd95b971f8a9 100644 --- a/tvix/eval/src/tests/tvix_tests/eval-okay-functionargs.nix +++ b/tvix/eval/src/tests/tvix_tests/eval-okay-functionargs.nix @@ -6,7 +6,7 @@ let atermFun = { stdenv, fetchurl }: { name = "aterm-${stdenv.name}"; }; aterm2Fun = { stdenv, fetchurl }: { name = "aterm2-${stdenv.name}"; }; nixFun = { stdenv, fetchurl, aterm }: { name = "nix-${stdenv.name}-${aterm.name}"; }; - + mplayerFun = { stdenv, fetchurl, enableX11 ? false, xorg ? null, enableFoo ? true, foo ? null }: assert stdenv.name == "stdenv2"; @@ -18,7 +18,7 @@ let { override = newArgs: makeOverridable f (origArgs // (if builtins.isFunction newArgs then newArgs origArgs else newArgs)); }; - + callPackage_ = pkgs: f: args: makeOverridable f ((builtins.intersectAttrs (builtins.functionArgs f) pkgs) // args); @@ -42,7 +42,7 @@ let libX11Fun = { stdenv, fetchurl }: { name = "libX11"; }; libX11_2Fun = { stdenv, fetchurl }: { name = "libX11_2"; }; libXvFun = { stdenv, fetchurl, libX11 }: { name = "libXv"; }; - + xorgFun = { pkgs }: let callPackage = callPackage_ (pkgs // pkgs.xorg); in @@ -56,7 +56,7 @@ in let pkgs = allPackages { }; - + pkgs2 = allPackages { overrides = pkgs: pkgsPrev: { stdenv = pkgs.stdenv2; @@ -64,7 +64,7 @@ let xorg = pkgsPrev.xorg // { libX11 = libX11_2Fun { inherit (pkgs) stdenv fetchurl; }; }; }; }; - + in [ pkgs.stdenv.name diff --git a/tvix/eval/src/value/attrs.rs b/tvix/eval/src/value/attrs.rs index 833cb2fd6045..adf56567fb0d 100644 --- a/tvix/eval/src/value/attrs.rs +++ b/tvix/eval/src/value/attrs.rs @@ -5,10 +5,10 @@ //! //! Due to this, construction and management of attribute sets has //! some peculiarities that are encapsulated within this module. -use std::collections::btree_map; -use std::collections::BTreeMap; use std::iter::FromIterator; +use imbl::{ordmap, OrdMap}; + use crate::errors::ErrorKind; use crate::vm::VM; @@ -23,7 +23,8 @@ mod tests; #[derive(Clone, Debug)] enum AttrsRep { Empty, - Map(BTreeMap), + + Im(OrdMap), /// Warning: this represents a **two**-attribute attrset, with /// attribute names "name" and "value", like `{name="foo"; @@ -43,20 +44,21 @@ impl Default for AttrsRep { impl AttrsRep { /// Retrieve reference to a mutable map inside of an attrs, /// optionally changing the representation if required. - fn map_mut(&mut self) -> &mut BTreeMap { + fn map_mut(&mut self) -> &mut OrdMap { match self { - AttrsRep::Map(m) => m, + AttrsRep::Im(m) => m, AttrsRep::Empty => { - *self = AttrsRep::Map(BTreeMap::new()); + *self = AttrsRep::Im(OrdMap::new()); self.map_mut() } AttrsRep::KV { name, value } => { - *self = AttrsRep::Map(BTreeMap::from([ - (NixString::NAME, name.clone()), - (NixString::VALUE, value.clone()), - ])); + *self = AttrsRep::Im(ordmap! { + NixString::NAME => name.clone(), + NixString::VALUE => value.clone() + }); + self.map_mut() } } @@ -72,7 +74,7 @@ impl AttrsRep { _ => None, }, - AttrsRep::Map(map) => map.get(&key.into()), + AttrsRep::Im(map) => map.get(&key.into()), } } @@ -80,7 +82,7 @@ impl AttrsRep { match self { AttrsRep::Empty => false, AttrsRep::KV { .. } => key == "name" || key == "value", - AttrsRep::Map(map) => map.contains_key(&key.into()), + AttrsRep::Im(map) => map.contains_key(&key.into()), } } } @@ -98,7 +100,7 @@ where where T: IntoIterator, { - NixAttrs(AttrsRep::Map( + NixAttrs(AttrsRep::Im( iter.into_iter() .map(|(k, v)| (k.into(), v.into())) .collect(), @@ -121,7 +123,7 @@ impl TotalDisplay for NixAttrs { f.write_str("; ")?; } - AttrsRep::Map(map) => { + AttrsRep::Im(map) => { for (name, value) in map { write!(f, "{} = ", name.ident_str())?; value.total_fmt(f, set)?; @@ -139,6 +141,7 @@ impl TotalDisplay for NixAttrs { #[cfg(feature = "arbitrary")] mod arbitrary { use super::*; + use std::collections::BTreeMap; use proptest::prelude::*; use proptest::prop_oneof; @@ -158,7 +161,7 @@ mod arbitrary { ) .prop_map(|(name, value)| Self(AttrsRep::KV { name, value })), any_with::>(args) - .prop_map(|map| Self(AttrsRep::Map(map))) + .prop_map(|map| Self::from_iter(map.into_iter())) ] .boxed() } @@ -183,44 +186,41 @@ impl NixAttrs { // Explicitly handle all branches instead of falling // through, to ensure that we get at least some compiler // errors if variants are modified. - (AttrsRep::Map(_), AttrsRep::Map(_)) - | (AttrsRep::Map(_), AttrsRep::KV { .. }) - | (AttrsRep::KV { .. }, AttrsRep::Map(_)) => {} + (AttrsRep::Im(_), AttrsRep::Im(_)) + | (AttrsRep::Im(_), AttrsRep::KV { .. }) + | (AttrsRep::KV { .. }, AttrsRep::Im(_)) => {} }; // Slightly more advanced, but still optimised updates match (self.0, other.0) { - (AttrsRep::Map(mut m), AttrsRep::KV { name, value }) => { + (AttrsRep::Im(mut m), AttrsRep::KV { name, value }) => { m.insert(NixString::NAME, name); m.insert(NixString::VALUE, value); - NixAttrs(AttrsRep::Map(m)) + NixAttrs(AttrsRep::Im(m)) } - (AttrsRep::KV { name, value }, AttrsRep::Map(mut m)) => { + (AttrsRep::KV { name, value }, AttrsRep::Im(mut m)) => { match m.entry(NixString::NAME) { - btree_map::Entry::Vacant(e) => { + imbl::ordmap::Entry::Vacant(e) => { e.insert(name); } - btree_map::Entry::Occupied(_) => { /* name from `m` has precedence */ } + imbl::ordmap::Entry::Occupied(_) => { /* name from `m` has precedence */ } }; match m.entry(NixString::VALUE) { - btree_map::Entry::Vacant(e) => { + imbl::ordmap::Entry::Vacant(e) => { e.insert(value); } - btree_map::Entry::Occupied(_) => { /* value from `m` has precedence */ } + imbl::ordmap::Entry::Occupied(_) => { /* value from `m` has precedence */ } }; - NixAttrs(AttrsRep::Map(m)) + NixAttrs(AttrsRep::Im(m)) } // Plain merge of maps. - (AttrsRep::Map(mut m1), AttrsRep::Map(mut m2)) => { - m1.append(&mut m2); - NixAttrs(AttrsRep::Map(m1)) - } + (AttrsRep::Im(m1), AttrsRep::Im(m2)) => NixAttrs(AttrsRep::Im(m2.union(m1))), // Cases handled above by the borrowing match: _ => unreachable!(), @@ -230,7 +230,7 @@ impl NixAttrs { /// Return the number of key-value entries in an attrset. pub fn len(&self) -> usize { match &self.0 { - AttrsRep::Map(map) => map.len(), + AttrsRep::Im(map) => map.len(), AttrsRep::Empty => 0, AttrsRep::KV { .. } => 2, } @@ -256,7 +256,7 @@ impl NixAttrs { #[allow(clippy::needless_lifetimes)] pub fn iter<'a>(&'a self) -> Iter> { Iter(match &self.0 { - AttrsRep::Map(map) => KeyValue::Map(map.iter()), + AttrsRep::Im(map) => KeyValue::Im(map.iter()), AttrsRep::Empty => KeyValue::Empty, AttrsRep::KV { @@ -280,7 +280,7 @@ impl NixAttrs { ] .into_iter(), )), - AttrsRep::Map(map) => IntoIter(IntoIterRepr::Map(map.into_iter())), + AttrsRep::Im(map) => IntoIter(IntoIterRepr::Im(map.into_iter())), } } @@ -294,7 +294,7 @@ impl NixAttrs { pub fn keys(&self) -> Keys { Keys(match &self.0 { AttrsRep::Empty => KeysInner::Empty, - AttrsRep::Map(m) => KeysInner::Map(m.keys()), + AttrsRep::Im(m) => KeysInner::Im(m.keys()), AttrsRep::KV { .. } => KeysInner::KV(IterKV::default()), }) } @@ -321,7 +321,7 @@ impl NixAttrs { } } - let mut attrs = NixAttrs(AttrsRep::Map(BTreeMap::new())); + let mut attrs = NixAttrs(AttrsRep::Im(OrdMap::new())); for _ in 0..count { let value = stack_slice.pop().unwrap(); @@ -363,7 +363,7 @@ impl NixAttrs { // elements after key construction). In practice this // probably does not happen, so it's better to just bite // the bullet and implement this branch. - (AttrsRep::Empty, AttrsRep::Map(map)) | (AttrsRep::Map(map), AttrsRep::Empty) => { + (AttrsRep::Empty, AttrsRep::Im(map)) | (AttrsRep::Im(map), AttrsRep::Empty) => { Ok(map.is_empty()) } @@ -382,8 +382,8 @@ impl NixAttrs { }, ) => Ok(n1.nix_eq(n2, vm)? && v1.nix_eq(v2, vm)?), - (AttrsRep::Map(map), AttrsRep::KV { name, value }) - | (AttrsRep::KV { name, value }, AttrsRep::Map(map)) => { + (AttrsRep::Im(map), AttrsRep::KV { name, value }) + | (AttrsRep::KV { name, value }, AttrsRep::Im(map)) => { if map.len() != 2 { return Ok(false); } @@ -397,7 +397,7 @@ impl NixAttrs { Ok(false) } - (AttrsRep::Map(m1), AttrsRep::Map(m2)) => { + (AttrsRep::Im(m1), AttrsRep::Im(m2)) => { if m1.len() != m2.len() { return Ok(false); } @@ -462,11 +462,11 @@ fn attempt_optimise_kv(slice: &mut [Value]) -> Option { /// checking against duplicate keys. fn set_attr(attrs: &mut NixAttrs, key: NixString, value: Value) -> Result<(), ErrorKind> { match attrs.0.map_mut().entry(key) { - btree_map::Entry::Occupied(entry) => Err(ErrorKind::DuplicateAttrsKey { + imbl::ordmap::Entry::Occupied(entry) => Err(ErrorKind::DuplicateAttrsKey { key: entry.key().as_str().to_string(), }), - btree_map::Entry::Vacant(entry) => { + imbl::ordmap::Entry::Vacant(entry) => { entry.insert(value); Ok(()) } @@ -495,7 +495,6 @@ impl IterKV { /// Iterator representation over the keys *and* values of an attribute /// set. -#[derive(Debug)] pub enum KeyValue<'a> { Empty, @@ -505,7 +504,7 @@ pub enum KeyValue<'a> { at: IterKV, }, - Map(btree_map::Iter<'a, NixString, Value>), + Im(imbl::ordmap::Iter<'a, NixString, Value>), } /// Iterator over a Nix attribute set. @@ -519,7 +518,7 @@ impl<'a> Iterator for Iter> { fn next(&mut self) -> Option { match &mut self.0 { - KeyValue::Map(inner) => inner.next(), + KeyValue::Im(inner) => inner.next(), KeyValue::Empty => None, KeyValue::KV { name, value, at } => match at { @@ -544,7 +543,7 @@ impl<'a> ExactSizeIterator for Iter> { match &self.0 { KeyValue::Empty => 0, KeyValue::KV { .. } => 2, - KeyValue::Map(inner) => inner.len(), + KeyValue::Im(inner) => inner.len(), } } } @@ -552,7 +551,7 @@ impl<'a> ExactSizeIterator for Iter> { enum KeysInner<'a> { Empty, KV(IterKV), - Map(btree_map::Keys<'a, NixString, Value>), + Im(imbl::ordmap::Keys<'a, NixString, Value>), } pub struct Keys<'a>(KeysInner<'a>); @@ -572,7 +571,7 @@ impl<'a> Iterator for Keys<'a> { Some(NixString::VALUE_REF) } KeysInner::KV(IterKV::Done) => None, - KeysInner::Map(m) => m.next(), + KeysInner::Im(m) => m.next(), } } } @@ -592,7 +591,7 @@ impl<'a> ExactSizeIterator for Keys<'a> { match &self.0 { KeysInner::Empty => 0, KeysInner::KV(_) => 2, - KeysInner::Map(m) => m.len(), + KeysInner::Im(m) => m.len(), } } } @@ -601,7 +600,7 @@ impl<'a> ExactSizeIterator for Keys<'a> { pub enum IntoIterRepr { Empty, Finite(std::vec::IntoIter<(NixString, Value)>), - Map(std::collections::btree_map::IntoIter), + Im(imbl::ordmap::ConsumingIter<(NixString, Value)>), } #[repr(transparent)] @@ -613,8 +612,8 @@ impl Iterator for IntoIter { fn next(&mut self) -> Option { match &mut self.0 { IntoIterRepr::Empty => None, - IntoIterRepr::Map(inner) => inner.next(), IntoIterRepr::Finite(inner) => inner.next(), + IntoIterRepr::Im(inner) => inner.next(), } } } @@ -623,8 +622,8 @@ impl ExactSizeIterator for IntoIter { fn len(&self) -> usize { match &self.0 { IntoIterRepr::Empty => 0, - IntoIterRepr::Map(inner) => inner.len(), IntoIterRepr::Finite(inner) => inner.len(), + IntoIterRepr::Im(inner) => inner.len(), } } } diff --git a/tvix/eval/src/value/attrs/tests.rs b/tvix/eval/src/value/attrs/tests.rs index 2e80fa6f2308..2039c509fd56 100644 --- a/tvix/eval/src/value/attrs/tests.rs +++ b/tvix/eval/src/value/attrs/tests.rs @@ -56,7 +56,7 @@ fn test_simple_attrs() { .expect("simple attr construction should succeed"); assert!( - matches!(attrs, NixAttrs(AttrsRep::Map(_))), + matches!(attrs, NixAttrs(AttrsRep::Im(_))), "simple attribute set should use map representation", ) } diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs index 0ab180a341e9..fa1f266c8779 100644 --- a/tvix/eval/src/value/list.rs +++ b/tvix/eval/src/value/list.rs @@ -1,7 +1,7 @@ //! This module implements Nix lists. use std::ops::Index; -use im::{vector, Vector}; +use imbl::{vector, Vector}; use crate::errors::ErrorKind; use crate::vm::VM; @@ -119,7 +119,7 @@ impl NixList { impl IntoIterator for NixList { type Item = Value; - type IntoIter = im::vector::ConsumingIter; + type IntoIter = imbl::vector::ConsumingIter; fn into_iter(self) -> Self::IntoIter { self.0.into_iter() @@ -128,7 +128,7 @@ impl IntoIterator for NixList { impl<'a> IntoIterator for &'a NixList { type Item = &'a Value; - type IntoIter = im::vector::Iter<'a, Value>; + type IntoIter = imbl::vector::Iter<'a, Value>; fn into_iter(self) -> Self::IntoIter { self.0.iter() diff --git a/tvix/eval/src/value/mod.rs b/tvix/eval/src/value/mod.rs index 1c6d104bd864..7791a4a8c33d 100644 --- a/tvix/eval/src/value/mod.rs +++ b/tvix/eval/src/value/mod.rs @@ -601,7 +601,7 @@ fn type_error(expected: &'static str, actual: &Value) -> ErrorKind { #[cfg(test)] mod tests { use super::*; - use im::vector; + use imbl::vector; mod nix_eq { use crate::observer::NoOpObserver; -- cgit 1.4.1