test(tvix/eval): Add proptests covering trait impls for String r/4894

Add a suite of proptests covering the laws of the handwritten stdlib
trait impls (Eq, Ord, and Hash) for String, generated from a new set of
macros for generating those tests which can be applied to other types.

Change-Id: Ib3276c9e96fca497aece094e5612707d3dc77ccd
Reviewed-on: https://cl.tvl.fyi/c/depot/+/6626
Autosubmit: grfn <grfn@gws.fyi>
Reviewed-by: sterni <sternenseemann@systemli.org>
Tested-by: BuildkiteCI

3 files changed, 153 insertions, 0 deletions

diff --git a/tvix/eval/src/lib.rs b/tvix/eval/src/lib.rs
index b0baf3c249..34bb3b57e9 100644
--- a/tvix/eval/src/lib.rs
+++ b/tvix/eval/src/lib.rs
@@ -11,6 +11,8 @@ mod vm;
 mod warnings;
 
 #[cfg(test)]
+mod properties;
+#[cfg(test)]
 mod tests;
 
 // Re-export the public interface used by other crates.
diff --git a/tvix/eval/src/properties.rs b/tvix/eval/src/properties.rs
new file mode 100644
index 0000000000..72a2fe29ef
--- /dev/null
+++ b/tvix/eval/src/properties.rs
@@ -0,0 +1,140 @@
+//! Macros that generate proptest test suites checking laws of stdlib traits
+
+/// Generate a suite of tests to check the laws of the [`Eq`] impl for the given type
+macro_rules! eq_laws {
+    ($ty: ty) => {
+        eq_laws!(
+            #[strategy(::proptest::arbitrary::any::<$ty>())]
+            $ty
+        );
+    };
+    (#[$meta: meta] $ty: ty) => {
+        #[allow(clippy::eq_op)]
+        mod eq {
+            use test_strategy::proptest;
+
+            use super::*;
+
+            #[proptest]
+            fn reflexive(#[$meta] x: $ty) {
+                assert!(x == x);
+            }
+
+            #[proptest]
+            fn symmetric(#[$meta] x: $ty, #[$meta] y: $ty) {
+                assert_eq!(x == y, y == x);
+            }
+
+            #[proptest]
+            fn transitive(#[$meta] x: $ty, #[$meta] y: $ty, #[$meta] z: $ty) {
+                if x == y && y == z {
+                    assert!(x == z);
+                }
+            }
+        }
+    };
+}
+
+/// Generate a suite of tests to check the laws of the [`Ord`] impl for the given type
+macro_rules! ord_laws {
+    ($ty: ty) => {
+        ord_laws!(
+            #[strategy(::proptest::arbitrary::any::<$ty>())]
+            $ty
+        );
+    };
+    (#[$meta: meta] $ty: ty) => {
+        mod ord {
+            use test_strategy::proptest;
+
+            use super::*;
+
+            #[proptest]
+            fn partial_cmp_matches_cmp(#[$meta] x: $ty, #[$meta] y: $ty) {
+                assert_eq!(x.partial_cmp(&y), Some(x.cmp(&y)));
+            }
+
+            #[proptest]
+            fn dual(#[$meta] x: $ty, #[$meta] y: $ty) {
+                if x < y {
+                    assert!(y > x);
+                }
+                if y < x {
+                    assert!(x > y);
+                }
+            }
+
+            #[proptest]
+            fn le_transitive(#[$meta] x: $ty, #[$meta] y: $ty, #[$meta] z: $ty) {
+                if x < y && y < z {
+                    assert!(x < z)
+                }
+            }
+
+            #[proptest]
+            fn gt_transitive(#[$meta] x: $ty, #[$meta] y: $ty, #[$meta] z: $ty) {
+                if x > y && y > z {
+                    assert!(x > z)
+                }
+            }
+
+            #[proptest]
+            fn trichotomy(#[$meta] x: $ty, #[$meta] y: $ty) {
+                let less = x < y;
+                let greater = x > y;
+                let eq = x == y;
+
+                if less {
+                    assert!(!greater);
+                    assert!(!eq);
+                }
+
+                if greater {
+                    assert!(!less);
+                    assert!(!eq);
+                }
+
+                if eq {
+                    assert!(!less);
+                    assert!(!greater);
+                }
+            }
+        }
+    };
+}
+
+/// Generate a test to check the laws of the [`Hash`] impl for the given type
+macro_rules! hash_laws {
+    ($ty: ty) => {
+        hash_laws!(
+            #[strategy(::proptest::arbitrary::any::<$ty>())]
+            $ty
+        );
+    };
+    (#[$meta: meta] $ty: ty) => {
+        mod hash {
+            use test_strategy::proptest;
+
+            use super::*;
+
+            #[proptest]
+            fn matches_eq(#[$meta] x: $ty, #[$meta] y: $ty) {
+                let hash = |x: &$ty| {
+                    use std::hash::Hasher;
+
+                    let mut hasher = ::std::collections::hash_map::DefaultHasher::new();
+                    x.hash(&mut hasher);
+                    hasher.finish()
+                };
+
+                if x == y {
+                    assert_eq!(hash(&x), hash(&y));
+                }
+            }
+        }
+    };
+}
+
+pub(crate) use eq_laws;
+pub(crate) use hash_laws;
+pub(crate) use ord_laws;
diff --git a/tvix/eval/src/value/string.rs b/tvix/eval/src/value/string.rs
index 2056465343..bfbaa815db 100644
--- a/tvix/eval/src/value/string.rs
+++ b/tvix/eval/src/value/string.rs
@@ -177,3 +177,14 @@ impl Display for NixString {
         f.write_str("\"")
     }
 }
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    use crate::properties::{eq_laws, hash_laws, ord_laws};
+
+    eq_laws!(NixString);
+    hash_laws!(NixString);
+    ord_laws!(NixString);
+}