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 36c9cef50f..523264b32f 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 a27fe822f2..ca3165c1af 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 6974110290..24e6d33d0d 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 cd7629cfb9..f0bdc06fd5 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 6515fb515a..10d0717202 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 6d830b7283..5d1daf7c9c 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 af8627bf9b..9ab23043c5 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,