refactor(tvix/value): use proptest strategies from imbl crate r/5670

Instead of going through Vec/BTreeMap for generating our internal
types, use the proptest strategies from imbl.

The one thing I couldn't figure out in the previous implementation is
where the ranges/sizes of generated collections came from. The
strategies in proptest use different types (Range, with an unknown
default value, and SizeRange with 0..100). I've opted to specify
0..100 directly, but we can probably make it configurable.

Change-Id: I749bc4c703fe424099240cab822b1642e5216361
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7791
Autosubmit: tazjin <tazjin@tvl.su>
Tested-by: BuildkiteCI
Reviewed-by: flokli <flokli@flokli.de>

7 files changed, 211 insertions, 77 deletions

diff --git a/tvix/Cargo.lock b/tvix/Cargo.lock
index 36c9cef50f03..523264b32f84 100644
--- a/tvix/Cargo.lock
+++ b/tvix/Cargo.lock
@@ -178,6 +178,21 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "9e1b586273c5702936fe7b7d6896644d8be71e6314cfe09d3167c95f712589e8"
 
 [[package]]
+name = "bit-set"
+version = "0.5.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0700ddab506f33b20a03b13996eccd309a48e5ff77d0d95926aa0210fb4e95f1"
+dependencies = [
+ "bit-vec",
+]
+
+[[package]]
+name = "bit-vec"
+version = "0.6.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "349f9b6a179ed607305526ca489b34ad0a41aed5f7980fa90eb03160b69598fb"
+
+[[package]]
 name = "bitflags"
 version = "1.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -869,6 +884,7 @@ checksum = "c2806b69cd9f4664844027b64465eacb444c67c1db9c778e341adff0c25cdb0d"
 dependencies = [
  "bitmaps",
  "imbl-sized-chunks",
+ "proptest",
  "rand_core 0.6.4",
  "rand_xoshiro",
  "serde",
@@ -1353,15 +1369,17 @@ version = "1.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "1e0d9cc07f18492d879586c92b485def06bc850da3118075cd45d50e9c95b0e5"
 dependencies = [
+ "bit-set",
  "bitflags",
  "byteorder",
  "lazy_static",
  "num-traits",
- "quick-error",
+ "quick-error 2.0.1",
  "rand 0.8.5",
  "rand_chacha",
  "rand_xorshift",
  "regex-syntax",
+ "rusty-fork",
  "tempfile",
 ]
 
@@ -1422,6 +1440,12 @@ dependencies = [
 
 [[package]]
 name = "quick-error"
+version = "1.2.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a1d01941d82fa2ab50be1e79e6714289dd7cde78eba4c074bc5a4374f650dfe0"
+
+[[package]]
+name = "quick-error"
 version = "2.0.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "a993555f31e5a609f617c12db6250dedcac1b0a85076912c436e6fc9b2c8e6a3"
@@ -1663,6 +1687,18 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "97477e48b4cf8603ad5f7aaf897467cf42ab4218a38ef76fb14c2d6773a6d6a8"
 
 [[package]]
+name = "rusty-fork"
+version = "0.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cb3dcc6e454c328bb824492db107ab7c0ae8fcffe4ad210136ef014458c1bc4f"
+dependencies = [
+ "fnv",
+ "quick-error 1.2.3",
+ "tempfile",
+ "wait-timeout",
+]
+
+[[package]]
 name = "rustyline"
 version = "10.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2415,6 +2451,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "49874b5167b65d7193b8aba1567f5c7d93d001cafc34600cee003eda787e483f"
 
 [[package]]
+name = "wait-timeout"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9f200f5b12eb75f8c1ed65abd4b2db8a6e1b138a20de009dacee265a2498f3f6"
+dependencies = [
+ "libc",
+]
+
+[[package]]
 name = "walkdir"
 version = "2.3.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/tvix/Cargo.nix b/tvix/Cargo.nix
index a27fe822f200..ca3165c1afab 100644
--- a/tvix/Cargo.nix
+++ b/tvix/Cargo.nix
@@ -649,6 +649,43 @@ rec {
         };
         resolvedDefaultFeatures = [ "default" "std" ];
       };
+      "bit-set" = rec {
+        crateName = "bit-set";
+        version = "0.5.3";
+        edition = "2015";
+        sha256 = "1wcm9vxi00ma4rcxkl3pzzjli6ihrpn9cfdi0c5b4cvga2mxs007";
+        authors = [
+          "Alexis Beingessner <a.beingessner@gmail.com>"
+        ];
+        dependencies = [
+          {
+            name = "bit-vec";
+            packageId = "bit-vec";
+            usesDefaultFeatures = false;
+          }
+        ];
+        features = {
+          "default" = [ "std" ];
+          "std" = [ "bit-vec/std" ];
+        };
+        resolvedDefaultFeatures = [ "default" "std" ];
+      };
+      "bit-vec" = rec {
+        crateName = "bit-vec";
+        version = "0.6.3";
+        edition = "2015";
+        sha256 = "1ywqjnv60cdh1slhz67psnp422md6jdliji6alq0gmly2xm9p7rl";
+        authors = [
+          "Alexis Beingessner <a.beingessner@gmail.com>"
+        ];
+        features = {
+          "default" = [ "std" ];
+          "serde" = [ "dep:serde" ];
+          "serde_no_std" = [ "serde/alloc" ];
+          "serde_std" = [ "std" "serde/std" ];
+        };
+        resolvedDefaultFeatures = [ "std" ];
+      };
       "bitflags" = rec {
         crateName = "bitflags";
         version = "1.3.2";
@@ -2514,6 +2551,11 @@ rec {
             packageId = "imbl-sized-chunks";
           }
           {
+            name = "proptest";
+            packageId = "proptest";
+            optional = true;
+          }
+          {
             name = "rand_core";
             packageId = "rand_core 0.6.4";
           }
@@ -2535,6 +2577,10 @@ rec {
         ];
         devDependencies = [
           {
+            name = "proptest";
+            packageId = "proptest";
+          }
+          {
             name = "serde";
             packageId = "serde";
           }
@@ -2547,7 +2593,7 @@ rec {
           "refpool" = [ "dep:refpool" ];
           "serde" = [ "dep:serde" ];
         };
-        resolvedDefaultFeatures = [ "serde" ];
+        resolvedDefaultFeatures = [ "proptest" "serde" ];
       };
       "imbl-sized-chunks" = rec {
         crateName = "imbl-sized-chunks";
@@ -3790,6 +3836,11 @@ rec {
         ];
         dependencies = [
           {
+            name = "bit-set";
+            packageId = "bit-set";
+            optional = true;
+          }
+          {
             name = "bitflags";
             packageId = "bitflags";
           }
@@ -3810,7 +3861,7 @@ rec {
           }
           {
             name = "quick-error";
-            packageId = "quick-error";
+            packageId = "quick-error 2.0.1";
             optional = true;
           }
           {
@@ -3834,6 +3885,12 @@ rec {
             optional = true;
           }
           {
+            name = "rusty-fork";
+            packageId = "rusty-fork";
+            optional = true;
+            usesDefaultFeatures = false;
+          }
+          {
             name = "tempfile";
             packageId = "tempfile";
             optional = true;
@@ -3854,7 +3911,7 @@ rec {
           "timeout" = [ "fork" "rusty-fork/timeout" ];
           "x86" = [ "dep:x86" ];
         };
-        resolvedDefaultFeatures = [ "alloc" "break-dead-code" "lazy_static" "quick-error" "regex-syntax" "std" "tempfile" ];
+        resolvedDefaultFeatures = [ "alloc" "bit-set" "break-dead-code" "default" "fork" "lazy_static" "quick-error" "regex-syntax" "rusty-fork" "std" "tempfile" "timeout" ];
       };
       "prost" = rec {
         crateName = "prost";
@@ -4038,7 +4095,18 @@ rec {
         };
         resolvedDefaultFeatures = [ "default" "std" ];
       };
-      "quick-error" = rec {
+      "quick-error 1.2.3" = rec {
+        crateName = "quick-error";
+        version = "1.2.3";
+        edition = "2015";
+        sha256 = "1q6za3v78hsspisc197bg3g7rpc989qycy8ypr8ap8igv10ikl51";
+        authors = [
+          "Paul Colomiets <paul@colomiets.name>"
+          "Colin Kiegel <kiegel@gmx.de>"
+        ];
+
+      };
+      "quick-error 2.0.1" = rec {
         crateName = "quick-error";
         version = "2.0.1";
         edition = "2018";
@@ -4738,6 +4806,40 @@ rec {
         ];
 
       };
+      "rusty-fork" = rec {
+        crateName = "rusty-fork";
+        version = "0.3.0";
+        edition = "2018";
+        sha256 = "0kxwq5c480gg6q0j3bg4zzyfh2kwmc3v2ba94jw8ncjc8mpcqgfb";
+        authors = [
+          "Jason Lingle"
+        ];
+        dependencies = [
+          {
+            name = "fnv";
+            packageId = "fnv";
+          }
+          {
+            name = "quick-error";
+            packageId = "quick-error 1.2.3";
+          }
+          {
+            name = "tempfile";
+            packageId = "tempfile";
+          }
+          {
+            name = "wait-timeout";
+            packageId = "wait-timeout";
+            optional = true;
+          }
+        ];
+        features = {
+          "default" = [ "timeout" ];
+          "timeout" = [ "wait-timeout" ];
+          "wait-timeout" = [ "dep:wait-timeout" ];
+        };
+        resolvedDefaultFeatures = [ "timeout" "wait-timeout" ];
+      };
       "rustyline" = rec {
         crateName = "rustyline";
         version = "10.0.0";
@@ -6927,7 +7029,7 @@ rec {
           }
         ];
         features = {
-          "arbitrary" = [ "proptest" "test-strategy" ];
+          "arbitrary" = [ "proptest" "test-strategy" "imbl/proptest" ];
           "backtrace-on-stack-overflow" = [ "dep:backtrace-on-stack-overflow" ];
           "backtrace_overflow" = [ "backtrace-on-stack-overflow" ];
           "default" = [ "impure" "arbitrary" "nix_tests" "backtrace_overflow" ];
@@ -7216,6 +7318,24 @@ rec {
         ];
 
       };
+      "wait-timeout" = rec {
+        crateName = "wait-timeout";
+        version = "0.2.0";
+        edition = "2015";
+        crateBin = [ ];
+        sha256 = "1xpkk0j5l9pfmjfh1pi0i89invlavfrd9av5xp0zhxgb29dhy84z";
+        authors = [
+          "Alex Crichton <alex@alexcrichton.com>"
+        ];
+        dependencies = [
+          {
+            name = "libc";
+            packageId = "libc";
+            target = { target, features }: (target."unix" or false);
+          }
+        ];
+
+      };
       "walkdir" = rec {
         crateName = "walkdir";
         version = "2.3.2";
diff --git a/tvix/eval/Cargo.toml b/tvix/eval/Cargo.toml
index 6974110290bf..24e6d33d0d1c 100644
--- a/tvix/eval/Cargo.toml
+++ b/tvix/eval/Cargo.toml
@@ -50,7 +50,7 @@ nix_tests = []
 impure = []
 
 # Enables Arbitrary impls for internal types (required to run tests)
-arbitrary = [ "proptest", "test-strategy" ]
+arbitrary = [ "proptest", "test-strategy", "imbl/proptest" ]
 
 # For debugging use only; not appropriate for production use.
 backtrace_overflow = [ "backtrace-on-stack-overflow" ]
diff --git a/tvix/eval/src/value/arbitrary.rs b/tvix/eval/src/value/arbitrary.rs
index cd7629cfb923..f0bdc06fd51d 100644
--- a/tvix/eval/src/value/arbitrary.rs
+++ b/tvix/eval/src/value/arbitrary.rs
@@ -1,9 +1,10 @@
 //! Support for configurable generation of arbitrary nix values
 
+use imbl::proptest::{ord_map, vector};
 use proptest::{prelude::*, strategy::BoxedStrategy};
 use std::ffi::OsString;
 
-use super::{NixAttrs, NixList, NixString, Value};
+use super::{attrs::AttrsRep, NixAttrs, NixList, NixString, Value};
 
 #[derive(Clone)]
 pub enum Parameters {
@@ -25,6 +26,39 @@ impl Default for Parameters {
     }
 }
 
+impl Arbitrary for NixAttrs {
+    type Parameters = Parameters; // <BTreeMap<NixString, Value> as Arbitrary>::Parameters;
+    type Strategy = BoxedStrategy<Self>;
+
+    fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
+        prop_oneof![
+            // Empty attrs representation
+            Just(Self(AttrsRep::Empty)),
+            // KV representation (name/value pairs)
+            (
+                any_with::<Value>(args.clone()),
+                any_with::<Value>(args.clone())
+            )
+                .prop_map(|(name, value)| Self(AttrsRep::KV { name, value })),
+            // Map representation
+            ord_map(NixString::arbitrary(), Value::arbitrary_with(args), 0..100)
+                .prop_map(|map| Self(AttrsRep::Im(map)))
+        ]
+        .boxed()
+    }
+}
+
+impl Arbitrary for NixList {
+    type Parameters = <Value as Arbitrary>::Parameters;
+    type Strategy = BoxedStrategy<Self>;
+
+    fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
+        vector(<Value as Arbitrary>::arbitrary_with(args), 0..100)
+            .prop_map(NixList::from)
+            .boxed()
+    }
+}
+
 impl Arbitrary for Value {
     type Parameters = Parameters;
     type Strategy = BoxedStrategy<Self>;
@@ -65,14 +99,8 @@ fn leaf_value() -> impl Strategy<Value = Value> {
 fn non_internal_value() -> impl Strategy<Value = Value> {
     leaf_value().prop_recursive(3, 5, 5, |inner| {
         prop_oneof![
-            any_with::<NixAttrs>((
-                Default::default(),
-                Default::default(),
-                Parameters::Strategy(inner.clone())
-            ))
-            .prop_map(Value::attrs),
-            any_with::<NixList>((Default::default(), Parameters::Strategy(inner)))
-                .prop_map(Value::List)
+            NixAttrs::arbitrary_with(Parameters::Strategy(inner.clone())).prop_map(Value::attrs),
+            any_with::<NixList>(Parameters::Strategy(inner)).prop_map(Value::List)
         ]
     })
 }
diff --git a/tvix/eval/src/value/attrs.rs b/tvix/eval/src/value/attrs.rs
index 6515fb515a5d..10d071720219 100644
--- a/tvix/eval/src/value/attrs.rs
+++ b/tvix/eval/src/value/attrs.rs
@@ -24,7 +24,7 @@ use super::Value;
 mod tests;
 
 #[derive(Clone, Debug, Deserialize)]
-enum AttrsRep {
+pub(super) enum AttrsRep {
     Empty,
 
     Im(OrdMap<NixString, Value>),
@@ -92,7 +92,7 @@ impl AttrsRep {
 
 #[repr(transparent)]
 #[derive(Clone, Debug, Default)]
-pub struct NixAttrs(AttrsRep);
+pub struct NixAttrs(pub(super) AttrsRep);
 
 impl<K, V> FromIterator<(K, V)> for NixAttrs
 where
@@ -192,36 +192,6 @@ impl<'de> Deserialize<'de> for NixAttrs {
     }
 }
 
-#[cfg(feature = "arbitrary")]
-mod arbitrary {
-    use super::*;
-    use std::collections::BTreeMap;
-
-    use proptest::prelude::*;
-    use proptest::prop_oneof;
-    use proptest::strategy::{BoxedStrategy, Just, Strategy};
-
-    impl Arbitrary for NixAttrs {
-        type Parameters = <BTreeMap<NixString, Value> as Arbitrary>::Parameters;
-
-        type Strategy = BoxedStrategy<Self>;
-
-        fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
-            prop_oneof![
-                Just(Self(AttrsRep::Empty)),
-                (
-                    any_with::<Value>(args.2.clone()),
-                    any_with::<Value>(args.2.clone())
-                )
-                    .prop_map(|(name, value)| Self(AttrsRep::KV { name, value })),
-                any_with::<BTreeMap<NixString, Value>>(args)
-                    .prop_map(|map| Self::from_iter(map.into_iter()))
-            ]
-            .boxed()
-        }
-    }
-}
-
 impl NixAttrs {
     pub fn empty() -> Self {
         Self(AttrsRep::Empty)
diff --git a/tvix/eval/src/value/list.rs b/tvix/eval/src/value/list.rs
index 6d830b7283d0..5d1daf7c9c0b 100644
--- a/tvix/eval/src/value/list.rs
+++ b/tvix/eval/src/value/list.rs
@@ -35,29 +35,6 @@ impl From<Vector<Value>> for NixList {
     }
 }
 
-#[cfg(feature = "arbitrary")]
-mod arbitrary {
-    use proptest::{
-        prelude::{any_with, Arbitrary},
-        strategy::{BoxedStrategy, Strategy},
-    };
-
-    use super::*;
-
-    impl Arbitrary for NixList {
-        // TODO(tazjin): im seems to implement arbitrary instances,
-        // but I couldn't figure out how to enable them.
-        type Parameters = <Vec<Value> as Arbitrary>::Parameters;
-        type Strategy = BoxedStrategy<Self>;
-
-        fn arbitrary_with(args: Self::Parameters) -> Self::Strategy {
-            any_with::<Vec<Value>>(args)
-                .prop_map(NixList::from_vec)
-                .boxed()
-        }
-    }
-}
-
 impl NixList {
     pub fn len(&self) -> usize {
         self.0.len()
diff --git a/tvix/eval/src/value/mod.rs b/tvix/eval/src/value/mod.rs
index af8627bf9b76..9ab23043c523 100644
--- a/tvix/eval/src/value/mod.rs
+++ b/tvix/eval/src/value/mod.rs
@@ -556,12 +556,6 @@ impl From<PathBuf> for Value {
     }
 }
 
-impl From<Vec<Value>> for Value {
-    fn from(val: Vec<Value>) -> Self {
-        Self::List(NixList::from_vec(val))
-    }
-}
-
 fn type_error(expected: &'static str, actual: &Value) -> ErrorKind {
     ErrorKind::TypeError {
         expected,