refactor(tvix/eval): remove use of imbl::Vector r/8520

This vector type has served us well for now, but it contains internal refcounts
which are incompatible with upcoming changes related to garbage collection.

The performance impact of this change within all benchmarks I ran was within the
margin of error:

[nix-shell:/tmp/perf]$ hyperfine "./before -E '(import <nixpkgs> {}).firefox.outPath' --log-level ERROR --no-warnings"
Benchmark 1: ./u64 -E '(import <nixpkgs> {}).firefox.outPath' --log-level ERROR --no-warnings
  Time (mean ± σ):      7.528 s ±  0.272 s    [User: 6.578 s, System: 0.631 s]
  Range (min … max):    7.160 s …  8.012 s    10 runs

nix-shell:/tmp/perf]$ hyperfine "./std-vec -E '(import <nixpkgs> {}).firefox.outPath' --log-level ERROR --no-warnings"
Benchmark 1: ./std-vec -E '(import <nixpkgs> {}).firefox.outPath' --log-level ERROR --no-warnings
  Time (mean ± σ):      7.515 s ±  0.178 s    [User: 6.508 s, System: 0.652 s]
  Range (min … max):    7.276 s …  7.861 s    10 runs

Change-Id: Ib95f871956e336a1e5771f6293583854b1efb276
Reviewed-on: https://cl.tvl.fyi/c/depot/+/12197
Reviewed-by: aspen <root@gws.fyi>
Tested-by: BuildkiteCI

4 files changed, 46 insertions, 47 deletions

diff --git a/tvix/eval/src/builtins/mod.rs b/tvix/eval/src/builtins/mod.rs
index e961738e3653..5fc995dc15c1 100644
--- a/tvix/eval/src/builtins/mod.rs
+++ b/tvix/eval/src/builtins/mod.rs
@@ -85,7 +85,6 @@ mod pure_builtins {
     use std::ffi::OsString;
 
     use bstr::{BString, ByteSlice, B};
-    use imbl::Vector;
     use itertools::Itertools;
     use os_str_bytes::OsStringBytes;
     use rustc_hash::FxHashSet;
@@ -246,7 +245,7 @@ mod pure_builtins {
 
     #[builtin("concatLists")]
     async fn builtin_concat_lists(co: GenCo, lists: Value) -> Result<Value, ErrorKind> {
-        let mut out = imbl::Vector::new();
+        let mut out = Vec::new();
 
         for value in lists.to_list()? {
             let list = try_value!(generators::request_force(&co, value).await).to_list()?;
@@ -259,7 +258,7 @@ mod pure_builtins {
     #[builtin("concatMap")]
     async fn builtin_concat_map(co: GenCo, f: Value, list: Value) -> Result<Value, ErrorKind> {
         let list = list.to_list()?;
-        let mut res = imbl::Vector::new();
+        let mut res = Vec::new();
         for val in list {
             let out = generators::request_call_with(&co, f.clone(), [val]).await;
             let out = try_value!(generators::request_force(&co, out).await);
@@ -387,13 +386,13 @@ mod pure_builtins {
     #[builtin("filter")]
     async fn builtin_filter(co: GenCo, pred: Value, list: Value) -> Result<Value, ErrorKind> {
         let list: NixList = list.to_list()?;
-        let mut out = imbl::Vector::new();
+        let mut out = Vec::new();
 
         for value in list {
             let result = generators::request_call_with(&co, pred.clone(), [value.clone()]).await;
             let verdict = try_value!(generators::request_force(&co, result).await);
             if verdict.as_bool()? {
-                out.push_back(value);
+                out.push(value);
             }
         }
 
@@ -481,7 +480,7 @@ mod pure_builtins {
 
         let operator = attrs.select_required("operator")?;
 
-        let mut res = imbl::Vector::new();
+        let mut res = Vec::new();
         let mut done_keys: Vec<Value> = vec![];
 
         while let Some(val) = work_set.pop_front() {
@@ -499,7 +498,7 @@ mod pure_builtins {
                 continue;
             }
 
-            res.push_back(val.clone());
+            res.push(val.clone());
 
             let op_result = generators::request_force(
                 &co,
@@ -520,14 +519,18 @@ mod pure_builtins {
         #[lazy] generator: Value,
         length: Value,
     ) -> Result<Value, ErrorKind> {
-        let mut out = imbl::Vector::<Value>::new();
         let len = length.as_int()?;
+        let mut out = Vec::with_capacity(
+            len.try_into()
+                .map_err(|_| ErrorKind::Abort(format!("can not create list of size {}", len)))?,
+        );
+
         // the best span we can get…
         let span = generators::request_span(&co).await;
 
         for i in 0..len {
             let val = Value::Thunk(Thunk::new_suspended_call(generator.clone(), i.into(), span));
-            out.push_back(val);
+            out.push(val);
         }
 
         Ok(Value::List(out.into()))
@@ -548,7 +551,7 @@ mod pure_builtins {
 
     #[builtin("groupBy")]
     async fn builtin_group_by(co: GenCo, f: Value, list: Value) -> Result<Value, ErrorKind> {
-        let mut res: BTreeMap<NixString, imbl::Vector<Value>> = BTreeMap::new();
+        let mut res: BTreeMap<NixString, Vec<Value>> = BTreeMap::new();
         for val in list.to_list()? {
             let key = try_value!(
                 generators::request_force(
@@ -559,7 +562,7 @@ mod pure_builtins {
             )
             .to_str()?;
 
-            res.entry(key).or_default().push_back(val);
+            res.entry(key).or_default().push(val);
         }
         Ok(Value::attrs(NixAttrs::from_iter(
             res.into_iter()
@@ -625,7 +628,7 @@ mod pure_builtins {
         let elements = groups
             .into_iter()
             .map(|(key, group)| {
-                let mut outputs: Vector<NixString> = Vector::new();
+                let mut outputs: Vec<NixString> = Vec::new();
                 let mut is_path = false;
                 let mut all_outputs = false;
 
@@ -638,7 +641,7 @@ mod pure_builtins {
 
                         NixContextElement::Single { name, derivation } => {
                             debug_assert!(derivation == key, "Unexpected group containing mixed keys, expected: {:?}, encountered {:?}", key, derivation);
-                            outputs.push_back(name.clone().into());
+                            outputs.push(name.clone().into());
                         }
 
                         NixContextElement::Derivation(drv_path) => {
@@ -665,7 +668,7 @@ mod pure_builtins {
                     vec_attrs.push(("outputs", Value::List(outputs
                                 .into_iter()
                                 .map(|s| s.into())
-                                .collect::<Vector<Value>>()
+                                .collect::<Vec<Value>>()
                                 .into()
                     )));
                 }
@@ -973,15 +976,16 @@ mod pure_builtins {
     }
 
     #[builtin("map")]
-    async fn builtin_map(co: GenCo, #[lazy] f: Value, list: Value) -> Result<Value, ErrorKind> {
-        let mut out = imbl::Vector::<Value>::new();
+    async fn builtin_map(co: GenCo, #[lazy] f: Value, list_val: Value) -> Result<Value, ErrorKind> {
+        let list = list_val.to_list()?;
+        let mut out = Vec::with_capacity(list.len());
 
         // the best span we can get…
         let span = generators::request_span(&co).await;
 
-        for val in list.to_list()? {
+        for val in list {
             let result = Value::Thunk(Thunk::new_suspended_call(f.clone(), val, span));
-            out.push_back(result)
+            out.push(result)
         }
 
         Ok(Value::List(out.into()))
@@ -1040,7 +1044,7 @@ mod pure_builtins {
                         // and then a compressor name will be extracted from that.
                         grp.map(|g| Value::from(g.as_str())).unwrap_or(Value::Null)
                     })
-                    .collect::<imbl::Vector<Value>>()
+                    .collect::<Vec<Value>>()
                     .into(),
             )),
             None => Ok(Value::Null),
@@ -1083,17 +1087,17 @@ mod pure_builtins {
 
     #[builtin("partition")]
     async fn builtin_partition(co: GenCo, pred: Value, list: Value) -> Result<Value, ErrorKind> {
-        let mut right: imbl::Vector<Value> = Default::default();
-        let mut wrong: imbl::Vector<Value> = Default::default();
+        let mut right: Vec<Value> = Default::default();
+        let mut wrong: Vec<Value> = Default::default();
 
         let list: NixList = list.to_list()?;
         for elem in list {
             let result = generators::request_call_with(&co, pred.clone(), [elem.clone()]).await;
 
             if try_value!(generators::request_force(&co, result).await).as_bool()? {
-                right.push_back(elem);
+                right.push(elem);
             } else {
-                wrong.push_back(elem);
+                wrong.push(elem);
             };
         }
 
@@ -1248,12 +1252,12 @@ mod pure_builtins {
         let re = Regex::new(re.to_str()?).unwrap();
         let mut capture_locations = re.capture_locations();
         let num_captures = capture_locations.len();
-        let mut ret = imbl::Vector::new();
+        let mut ret = Vec::new();
         let mut pos = 0;
 
         while let Some(thematch) = re.captures_read_at(&mut capture_locations, text, pos) {
             // push the unmatched characters preceding the match
-            ret.push_back(Value::from(NixString::new_inherit_context_from(
+            ret.push(Value::from(NixString::new_inherit_context_from(
                 &s,
                 &text[pos..thematch.start()],
             )));
@@ -1262,7 +1266,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: imbl::Vector<Value> = (1..num_captures)
+            let v: Vec<Value> = (1..num_captures)
                 .map(|i| capture_locations.get(i))
                 .map(|o| {
                     o.map(|(start, end)| {
@@ -1273,7 +1277,7 @@ mod pure_builtins {
                     .unwrap_or(Value::Null)
                 })
                 .collect();
-            ret.push_back(Value::List(NixList::from(v)));
+            ret.push(Value::List(NixList::from(v)));
             if pos == text.len() {
                 break;
             }
@@ -1283,7 +1287,7 @@ mod pure_builtins {
         // push the unmatched characters following the last match
         // Here, a surprising thing happens: we silently discard the original
         // context. This is as intended, Nix does the same.
-        ret.push_back(Value::from(&text[pos..]));
+        ret.push(Value::from(&text[pos..]));
 
         Ok(Value::List(NixList::from(ret)))
     }
diff --git a/tvix/eval/src/value/arbitrary.rs b/tvix/eval/src/value/arbitrary.rs
index bf53f4fcb28a..380eda0d9601 100644
--- a/tvix/eval/src/value/arbitrary.rs
+++ b/tvix/eval/src/value/arbitrary.rs
@@ -1,6 +1,7 @@
 //! Support for configurable generation of arbitrary nix values
 
-use imbl::proptest::{ord_map, vector};
+use imbl::proptest::ord_map;
+use proptest::collection::vec;
 use proptest::{prelude::*, strategy::BoxedStrategy};
 use std::ffi::OsString;
 
@@ -53,7 +54,7 @@ impl Arbitrary for NixList {
     type Strategy = BoxedStrategy<Self>;
 
     fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
-        vector(<Value as Arbitrary>::arbitrary_with(args), 0..100)
+        vec(<Value as Arbitrary>::arbitrary_with(args), 0..100)
             .prop_map(NixList::from)
             .boxed()
     }
diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs
index 2b8b3de28d19..3e4b23a93f42 100644
--- a/tvix/eval/src/value/list.rs
+++ b/tvix/eval/src/value/list.rs
@@ -2,8 +2,6 @@
 use std::ops::Index;
 use std::rc::Rc;
 
-use imbl::{vector, Vector};
-
 use serde::Deserialize;
 
 use super::thunk::ThunkSet;
@@ -12,7 +10,7 @@ use super::Value;
 
 #[repr(transparent)]
 #[derive(Clone, Debug, Deserialize)]
-pub struct NixList(Rc<Vector<Value>>);
+pub struct NixList(Rc<Vec<Value>>);
 
 impl TotalDisplay for NixList {
     fn total_fmt(&self, f: &mut std::fmt::Formatter<'_>, set: &mut ThunkSet) -> std::fmt::Result {
@@ -27,8 +25,8 @@ impl TotalDisplay for NixList {
     }
 }
 
-impl From<Vector<Value>> for NixList {
-    fn from(vs: Vector<Value>) -> Self {
+impl From<Vec<Value>> for NixList {
+    fn from(vs: Vec<Value>) -> Self {
         Self(Rc::new(vs))
     }
 }
@@ -54,10 +52,10 @@ impl NixList {
             stack_slice.len(),
         );
 
-        NixList(Rc::new(Vector::from_iter(stack_slice)))
+        NixList(Rc::new(stack_slice))
     }
 
-    pub fn iter(&self) -> vector::Iter<Value> {
+    pub fn iter(&self) -> std::slice::Iter<Value> {
         self.0.iter()
     }
 
@@ -65,19 +63,14 @@ impl NixList {
         Rc::ptr_eq(&self.0, &other.0)
     }
 
-    pub fn into_inner(self) -> Vector<Value> {
+    pub fn into_inner(self) -> Vec<Value> {
         Rc::try_unwrap(self.0).unwrap_or_else(|rc| (*rc).clone())
     }
-
-    #[deprecated(note = "callers should avoid constructing from Vec")]
-    pub fn from_vec(vs: Vec<Value>) -> Self {
-        Self(Rc::new(Vector::from_iter(vs)))
-    }
 }
 
 impl IntoIterator for NixList {
     type Item = Value;
-    type IntoIter = imbl::vector::ConsumingIter<Value>;
+    type IntoIter = std::vec::IntoIter<Value>;
 
     fn into_iter(self) -> Self::IntoIter {
         self.into_inner().into_iter()
@@ -86,7 +79,7 @@ impl IntoIterator for NixList {
 
 impl<'a> IntoIterator for &'a NixList {
     type Item = &'a Value;
-    type IntoIter = imbl::vector::Iter<'a, Value>;
+    type IntoIter = std::slice::Iter<'a, Value>;
 
     fn into_iter(self) -> Self::IntoIter {
         self.0.iter()
diff --git a/tvix/eval/src/vm/mod.rs b/tvix/eval/src/vm/mod.rs
index 7ac6d493fa1f..8d89020363e2 100644
--- a/tvix/eval/src/vm/mod.rs
+++ b/tvix/eval/src/vm/mod.rs
@@ -779,8 +779,9 @@ where
                 Op::Concat => lifted_pop! {
                     self(rhs, lhs) => {
                         let rhs = rhs.to_list().with_span(&frame, self)?.into_inner();
-                        let lhs = lhs.to_list().with_span(&frame, self)?.into_inner();
-                        self.stack.push(Value::List(NixList::from(lhs + rhs)))
+                        let mut lhs = lhs.to_list().with_span(&frame, self)?.into_inner();
+                        lhs.extend(rhs.into_iter());
+                        self.stack.push(Value::List(lhs.into()))
                     }
                 },