Use proptest's Strategy to generate expressions

5 files changed, 81 insertions, 52 deletions

diff --git a/rust/Cargo.toml b/rust/Cargo.toml
index 887bc41..1006d29 100644
--- a/rust/Cargo.toml
+++ b/rust/Cargo.toml
@@ -16,6 +16,7 @@ async-std = "1.13.0"
 reqwest = "0.12.8"
 tokio = { version = "1.40.0", features = ["rt", "macros", "rt-multi-thread"]}
 clap = { version = "4.5.19", features = ["derive"] }
+proptest = "1.0.0"
 
 [dependencies.uuid]
 version = "1.10.0"
@@ -26,9 +27,6 @@ features = [
     "serde"
 ]
 
-[dev-dependencies]
-proptest = "1.0.0"
-
 [lib]
 name = "lambda"
 path = "src/lib.rs"
diff --git a/rust/src/ast.rs b/rust/src/ast.rs
index dfb6862..3f8b772 100644
--- a/rust/src/ast.rs
+++ b/rust/src/ast.rs
@@ -1,6 +1,9 @@
-use std::fmt::{self, Display};
-
+use proptest::{
+    prelude::*,
+    string::{string_regex, RegexGeneratorStrategy},
+};
 use serde::{Deserialize, Serialize};
+use std::fmt::{self, Display};
 
 #[derive(Debug, PartialEq, Clone, Serialize, Deserialize)]
 pub enum Value {
@@ -26,3 +29,41 @@ impl Display for Value {
         }
     }
 }
+
+use Value::*;
+
+pub const IDENTIFIER: &str = "\\pL(\\pL|\\pN)*";
+
+pub fn identifier() -> RegexGeneratorStrategy<String> {
+    string_regex(IDENTIFIER).unwrap()
+}
+
+impl Arbitrary for Value {
+    type Parameters = ();
+    type Strategy = BoxedStrategy<Self>;
+
+    fn arbitrary_with(_args: ()) -> Self::Strategy {
+        let any_num = any::<i32>().prop_map(Num);
+        let any_bool = any::<bool>().prop_map(Bool);
+        let leaf = prop_oneof![
+            any_num,
+            any_bool,
+            // see https://unicode.org/reports/tr18/#General_Category_Property for one letter unicode categories
+            identifier().prop_map(Sym),
+        ];
+        let expr = leaf.prop_recursive(4, 128, 5, move |inner| {
+            prop_oneof![
+                (inner.clone(), inner.clone()).prop_map(|(l, r)| App(Box::new(l), Box::new(r))),
+                (identifier(), inner.clone()).prop_map(|(var, body)| Lam(var, Box::new(body))),
+                (identifier(), inner.clone(), inner.clone()).prop_map(|(var, body, expr)| {
+                    Value::Let(var, Box::new(body), Box::new(expr))
+                }),
+            ]
+        });
+        prop_oneof![
+            expr.clone(),
+            (identifier(), expr).prop_map(|(var, body)| Def(var, Box::new(body)))
+        ]
+        .boxed()
+    }
+}
diff --git a/rust/src/lambda.rs b/rust/src/lambda.rs
index d1ab5b5..9b7045f 100644
--- a/rust/src/lambda.rs
+++ b/rust/src/lambda.rs
@@ -1,3 +1,8 @@
+use proptest::{
+    arbitrary::{any, any_with, arbitrary_with},
+    strategy::{Strategy, ValueTree},
+    test_runner::TestRunner,
+};
 use rand::{rngs::SmallRng, Rng, RngCore, SeedableRng};
 use serde::{Deserialize, Serialize};
 use std::collections::HashMap;
@@ -98,12 +103,13 @@ fn gensym() -> String {
     format!("x_{}", n1)
 }
 
-pub fn generate_expr<R: Rng>(size: u32, rng: &mut R) -> Value {
+pub fn generate_expr(size: u32, runner: &mut TestRunner) -> Value {
     match size {
         0 | 1 => {
-            let n: u16 = rng.gen();
+            let n = any::<u16>().new_tree(runner).unwrap().current();
             Value::Num(n.into())
         }
+        2 => Value::Sym(identifier().new_tree(runner).unwrap().current()),
         _ => todo!(),
     }
 }
diff --git a/rust/src/parser.rs b/rust/src/parser.rs
index 2a5fef4..52aad5a 100644
--- a/rust/src/parser.rs
+++ b/rust/src/parser.rs
@@ -382,35 +382,6 @@ mod tests {
         );
     }
 
-    impl Arbitrary for Value {
-        type Parameters = ();
-        type Strategy = BoxedStrategy<Self>;
-
-        fn arbitrary_with(_args: ()) -> Self::Strategy {
-            let identifier = "\\pL(\\pL|\\pN)*";
-            let leaf = prop_oneof![
-                any::<i32>().prop_map(Num),
-                any::<bool>().prop_map(Bool),
-                // see https://unicode.org/reports/tr18/#General_Category_Property for one letter unicode categories
-                identifier.prop_map(Sym),
-            ];
-            let expr = leaf.prop_recursive(4, 128, 5, move |inner| {
-                prop_oneof![
-                    (inner.clone(), inner.clone()).prop_map(|(l, r)| App(Box::new(l), Box::new(r))),
-                    (identifier, inner.clone()).prop_map(|(var, body)| Lam(var, Box::new(body))),
-                    (identifier, inner.clone(), inner.clone()).prop_map(|(var, body, expr)| {
-                        Value::Let(var, Box::new(body), Box::new(expr))
-                    }),
-                ]
-            });
-            prop_oneof![
-                expr.clone(),
-                (identifier, expr).prop_map(|(var, body)| Def(var, Box::new(body)))
-            ]
-            .boxed()
-        }
-    }
-
     proptest! {
             #[test]
             fn parse_is_inverse_to_display(values in any::<Vec<Value>>()) {
diff --git a/rust/src/web.rs b/rust/src/web.rs
index 6bc892b..5729083 100644
--- a/rust/src/web.rs
+++ b/rust/src/web.rs
@@ -7,6 +7,7 @@ use futures::try_join;
 use futures::{future::join_all, lock::Mutex};
 use lambda::ast::Value;
 use log::info;
+use proptest::test_runner::TestRunner;
 use rand::rngs::SmallRng;
 use rand::{Rng, SeedableRng};
 use serde::{Deserialize, Serialize};
@@ -38,12 +39,12 @@ enum RegistrationResult {
     UrlAlreadyRegistered { url: String },
 }
 
-#[derive(Debug, PartialEq, Clone)]
+#[derive(Debug, Clone)]
 struct Client {
     id: Uuid,
     url: String,
     grade: u8,
-    rng: SmallRng,
+    runner: TestRunner,
     seed: u64,
 }
 
@@ -59,7 +60,7 @@ impl Client {
     }
 
     fn generate_expr(&mut self) -> (String, String) {
-        let input = generate_expr(self.grade.into(), &mut self.rng);
+        let input = generate_expr(self.grade.into(), &mut self.runner);
         let expected = eval_whnf(&input, &mut Environment::new());
         (input.to_string(), expected.to_string())
     }
@@ -117,7 +118,7 @@ impl AppState for State {
                 url: registration.url.clone(),
                 grade: 1,
                 seed,
-                rng: SmallRng::seed_from_u64(seed),
+                runner: TestRunner::deterministic(),
             }));
             let client_s = client.clone();
             self.clients.insert(registration.url.clone(), client);
@@ -355,15 +356,19 @@ mod app_tests {
         );
     }
 
-    #[test]
-    async fn client_generates_constant_at_level_1() {
-        let mut client = Client {
+    fn client() -> Client {
+        Client {
             id: Uuid::new_v4(),
             url: "http://1.2.3.4".to_string(),
             grade: 1,
             seed: 42,
-            rng: SmallRng::seed_from_u64(42),
-        };
+            runner: TestRunner::deterministic(),
+        }
+    }
+
+    #[test]
+    async fn client_generates_constant_at_level_1() {
+        let mut client = client();
 
         let (input, _) = client.generate_expr();
 
@@ -375,17 +380,25 @@ mod app_tests {
 
     #[test]
     async fn client_generates_different_inputs_on_each_call() {
-        let mut client = Client {
-            id: Uuid::new_v4(),
-            url: "http://1.2.3.4".to_string(),
-            grade: 1,
-            seed: 42,
-            rng: SmallRng::seed_from_u64(42),
-        };
+        let mut client = client();
 
         let (input1, _) = client.generate_expr();
         let (input2, _) = client.generate_expr();
 
         assert_ne!(input1, input2);
     }
+
+    #[test]
+    async fn client_generates_variables_at_level_2() {
+        let mut client = client();
+        client.grade = 2;
+
+        let (input, _) = client.generate_expr();
+
+        let parsed = parse(&input);
+        match parsed[..] {
+            [Value::Sym(_)] => (),
+            _ => panic!("Expected symbol, got {:?}", parsed),
+        }
+    }
 }