Skip to main content

sas_plus/
random.rs

1//! Tiny deterministic random task generator for property tests across the
2//! workspace (no external RNG dependency).
3
4use alloc::format;
5use alloc::vec::Vec;
6
7use crate::{Axiom, Effect, Fact, Operator, State, Task, Variable};
8
9/// xorshift64* — good enough for test-case generation.
10#[derive(Clone, Debug)]
11pub struct Rng(u64);
12
13impl Rng {
14    pub fn new(seed: u64) -> Self {
15        Self(seed.wrapping_mul(0x9E37_79B9_7F4A_7C15) | 1)
16    }
17    pub fn next_u64(&mut self) -> u64 {
18        self.0 ^= self.0 >> 12;
19        self.0 ^= self.0 << 25;
20        self.0 ^= self.0 >> 27;
21        self.0.wrapping_mul(0x2545_F491_4F6C_DD1D)
22    }
23    /// Uniform in `lo..=hi`.
24    pub fn range(&mut self, lo: u64, hi: u64) -> u64 {
25        lo + self.next_u64() % (hi - lo + 1)
26    }
27    fn distinct_vars(&mut self, n: usize, k: usize) -> Vec<usize> {
28        let mut vars: Vec<usize> = (0..n).collect();
29        for i in 0..k.min(n) {
30            let j = self.range(i as u64, n as u64 - 1) as usize;
31            vars.swap(i, j);
32        }
33        vars.truncate(k.min(n));
34        vars
35    }
36}
37
38#[derive(Clone, Copy, Debug)]
39pub struct RandomTaskParams {
40    pub num_vars: usize,
41    pub max_domain: u32,
42    pub num_ops: usize,
43    pub max_cost: u32,
44    /// Up to this many conditions per effect; `0` means no conditional effects.
45    pub max_conditions: usize,
46    /// Number of binary derived variables, each in its own axiom layer, with
47    /// one or two rules apiece. Goals and preconditions may then mention them.
48    pub num_derived: usize,
49}
50
51impl Default for RandomTaskParams {
52    fn default() -> Self {
53        Self {
54            num_vars: 4,
55            max_domain: 3,
56            num_ops: 10,
57            max_cost: 5,
58            max_conditions: 0,
59            num_derived: 0,
60        }
61    }
62}
63
64pub fn random_task(seed: u64, p: RandomTaskParams) -> Task {
65    let mut rng = Rng::new(seed);
66    let variables: Vec<Variable> = (0..p.num_vars)
67        .map(|i| {
68            Variable::new(
69                format!("v{i}"),
70                rng.range(2, u64::from(p.max_domain.max(2))) as u32,
71            )
72        })
73        .collect();
74    let fact = |rng: &mut Rng, var: usize| {
75        Fact::new(
76            var,
77            rng.range(0, u64::from(variables[var].domain_size) - 1) as u32,
78        )
79    };
80    let mut operators: Vec<Operator> = (0..p.num_ops)
81        .map(|i| {
82            let n_pre = rng.range(0, 2) as usize;
83            let n_eff = rng.range(1, 2) as usize;
84            let pre = rng
85                .distinct_vars(p.num_vars, n_pre)
86                .into_iter()
87                .map(|v| fact(&mut rng, v))
88                .collect();
89            let eff = rng
90                .distinct_vars(p.num_vars, n_eff)
91                .into_iter()
92                .map(|v| {
93                    let head = fact(&mut rng, v);
94                    // No draw without conditions, so seeds keep their tasks.
95                    let conditions = if p.max_conditions == 0 {
96                        Vec::new()
97                    } else {
98                        let n = rng.range(0, p.max_conditions as u64) as usize;
99                        rng.distinct_vars(p.num_vars, n)
100                            .into_iter()
101                            .map(|c| fact(&mut rng, c))
102                            .collect()
103                    };
104                    Effect {
105                        conditions,
106                        fact: head,
107                    }
108                })
109                .collect();
110            Operator {
111                name: format!("op{i}"),
112                pre,
113                eff,
114                cost: rng.range(1, u64::from(p.max_cost.max(1))) as u32,
115            }
116        })
117        .collect();
118    let mut initial = State((0..p.num_vars).map(|v| fact(&mut rng, v).value).collect());
119    let n_goal = rng.range(1, 2) as usize;
120    let mut goal: Vec<Fact> = rng
121        .distinct_vars(p.num_vars, n_goal)
122        .into_iter()
123        .map(|v| fact(&mut rng, v))
124        .collect();
125
126    // Derived variables come last, so tasks without them stay the same per seed.
127    let mut variables = variables;
128    let mut axioms = Vec::new();
129    for layer in 0..p.num_derived {
130        let var = variables.len();
131        for _ in 0..rng.range(1, 2) {
132            // Conditions on state variables and lower layers (at any value, which
133            // includes negation as failure).
134            let n = rng.range(1, 2) as usize;
135            let conditions = rng
136                .distinct_vars(var, n)
137                .into_iter()
138                .map(|c| {
139                    let domain = variables[c].domain_size;
140                    Fact::new(c, rng.range(0, u64::from(domain) - 1) as u32)
141                })
142                .collect();
143            axioms.push(Axiom {
144                conditions,
145                head: Fact::new(var, 1),
146            });
147        }
148        variables.push(Variable {
149            axiom_layer: Some(layer as u32),
150            ..Variable::new(format!("d{layer}"), 2)
151        });
152        initial.0.push(0);
153        let derived = Fact::new(var, rng.range(0, 1) as u32);
154        if rng.range(0, 1) == 0 {
155            goal.push(derived);
156        } else {
157            let op = rng.range(0, p.num_ops.max(1) as u64 - 1) as usize;
158            if let Some(op) = operators.get_mut(op) {
159                op.pre.push(derived);
160            }
161        }
162    }
163    Task {
164        variables,
165        operators,
166        initial,
167        goal,
168        axioms,
169    }
170}