748 Fundamental

748-property-based-testing — Property-Based Testing

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "748-property-based-testing — Property-Based Testing" functional Rust example. Difficulty level: Fundamental. Key concepts covered: Functional Programming. Example-based tests check specific inputs. Key difference from OCaml: 1. **Shrinking**: Rust's `proptest` uses a sophisticated strategy

Tutorial

The Problem

Example-based tests check specific inputs. Property-based testing checks invariants that must hold for all inputs by generating hundreds of random cases automatically. Pioneered by Haskell's QuickCheck (1999), this approach finds edge cases that humans miss: off-by-one errors, integer overflow, empty collections. The proptest and quickcheck Rust crates are production-grade; this example builds a minimal stdlib-only framework to teach the core ideas.

🎯 Learning Outcomes

• Implement a deterministic LCG (Linear Congruential Generator) for reproducible random testing

• Create an Arbitrary trait with arbitrary(rng) and shrink() methods

• Write a check function that runs N random cases and reports the smallest failing input

• Understand shrinking: when a failure is found, find the smallest input that still fails

• Formulate mathematical properties: sort idempotency, reverse involution, commutativity of addition

Code Example

pub trait Arbitrary: Sized + Clone + Debug {
    fn arbitrary(rng: &mut Lcg) -> Self;
    fn shrink(&self) -> Vec<Self> { vec![] }
}

fn forall<T: Arbitrary, F: FnMut(&T) -> bool>(
    name: &str, tests: usize, mut prop: F
) -> bool {
    let mut rng = Lcg::new(42);
    for _ in 0..tests {
        let input = T::arbitrary(&mut rng);
        if !prop(&input) {
            // Shrink to find minimal counterexample
            return false;
        }
    }
    true
}

let test_sort_idempotent =
  QCheck.Test.make ~count:1000
    QCheck.(list small_int)
    (fun l -> List.sort compare (List.sort compare l) = List.sort compare l)

let test_sort_preserves_length =
  QCheck.Test.make ~count:1000
    QCheck.(list small_int)
    (fun l -> List.length (List.sort compare l) = List.length l)

Key Differences

Shrinking: Rust's proptest uses a sophisticated strategy-based shrinker; OCaml's QCheck2 uses a similar but list-based approach. Both aim to find the minimal counterexample.

Type-driven generation: Rust derives Arbitrary implementations; OCaml's QCheck uses explicit generator values (combinators like QCheck.int, QCheck.list).

Reproducing failures: Both frameworks save the seed on failure so you can replay it; Rust uses PROPTEST_SEED env var, OCaml uses QCheck.Test.get_seed.

Integration: Rust's proptest! macro integrates naturally with cargo test; OCaml's QCheck requires an explicit runner call.

OCaml Approach

OCaml's QCheck2 is a mature property-based testing library. It provides a Gen.t type for generators, Test.make for properties, and automatic shrinking. QCheck.find_example searches for an input satisfying a predicate — useful for finding edge cases. The crowbar library integrates with AFL fuzzing for coverage-guided property testing.

Full Source

#![allow(clippy::all)]
//! # Property-Based Testing
//!
//! std-only QuickCheck-style framework for property testing.

/// Simple deterministic PRNG (Linear Congruential Generator)
pub struct Lcg(u64);

impl Lcg {
    /// Create a new LCG with the given seed
    pub fn new(seed: u64) -> Self {
        Lcg(seed)
    }

    /// Generate the next random u64
    pub fn next_u64(&mut self) -> u64 {
        self.0 = self
            .0
            .wrapping_mul(6364136223846793005)
            .wrapping_add(1442695040888963407);
        self.0
    }

    /// Generate a random i32 in the range [lo, hi]
    pub fn next_i32_in(&mut self, lo: i32, hi: i32) -> i32 {
        let range = (hi - lo + 1) as u64;
        lo + (self.next_u64() % range) as i32
    }

    /// Generate a random usize in the range [lo, hi]
    pub fn next_usize_in(&mut self, lo: usize, hi: usize) -> usize {
        let range = (hi - lo + 1) as u64;
        lo + (self.next_u64() % range) as usize
    }
}

/// Trait for generating arbitrary test values with shrinking
pub trait Arbitrary: Sized + Clone + std::fmt::Debug {
    /// Generate an arbitrary value
    fn arbitrary(rng: &mut Lcg) -> Self;

    /// Shrink to simpler values for counterexample minimization
    fn shrink(&self) -> Vec<Self> {
        vec![]
    }
}

impl Arbitrary for i32 {
    fn arbitrary(rng: &mut Lcg) -> Self {
        rng.next_i32_in(-1000, 1000)
    }

    fn shrink(&self) -> Vec<i32> {
        if *self == 0 {
            return vec![];
        }
        vec![0, self / 2, self.abs() - 1]
            .into_iter()
            .filter(|&x| x.abs() < self.abs())
            .collect()
    }
}

impl Arbitrary for Vec<i32> {
    fn arbitrary(rng: &mut Lcg) -> Self {
        let len = rng.next_usize_in(0, 20);
        (0..len).map(|_| i32::arbitrary(rng)).collect()
    }

    fn shrink(&self) -> Vec<Vec<i32>> {
        let mut shrunk = vec![];
        if self.is_empty() {
            return shrunk;
        }
        shrunk.push(self[1..].to_vec());
        shrunk.push(self[..self.len() - 1].to_vec());
        shrunk.push(self[..self.len() / 2].to_vec());
        shrunk
    }
}

/// Run a property test with shrinking on failure
pub fn forall<T, F>(name: &str, tests: usize, mut prop: F) -> bool
where
    T: Arbitrary,
    F: FnMut(&T) -> bool,
{
    let mut rng = Lcg::new(42);
    for i in 0..tests {
        let input = T::arbitrary(&mut rng);
        if !prop(&input) {
            let mut minimal = input.clone();
            loop {
                let candidates = minimal.shrink();
                let smaller = candidates.into_iter().find(|c| !prop(c));
                match smaller {
                    Some(s) => minimal = s,
                    None => break,
                }
            }
            eprintln!(
                "✗ {} failed after {} tests. Counterexample: {:?}",
                name,
                i + 1,
                minimal
            );
            return false;
        }
    }
    true
}

/// Sort a vector (for testing)
pub fn my_sort(mut v: Vec<i32>) -> Vec<i32> {
    v.sort();
    v
}

/// Check if a slice is sorted
pub fn is_sorted(v: &[i32]) -> bool {
    v.windows(2).all(|w| w[0] <= w[1])
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lcg_produces_different_values() {
        let mut rng = Lcg::new(1);
        let a = rng.next_u64();
        let b = rng.next_u64();
        assert_ne!(a, b);
    }

    #[test]
    fn test_property_sort_idempotent() {
        assert!(forall::<Vec<i32>, _>("sort idempotent", 500, |v| {
            my_sort(my_sort(v.clone())) == my_sort(v.clone())
        }));
    }

    #[test]
    fn test_property_sort_length_preserved() {
        assert!(forall::<Vec<i32>, _>("sort length", 500, |v| {
            my_sort(v.clone()).len() == v.len()
        }));
    }

    #[test]
    fn test_property_sort_ordered() {
        assert!(forall::<Vec<i32>, _>("sort ordered", 500, |v| {
            is_sorted(&my_sort(v.clone()))
        }));
    }

    #[test]
    fn test_i32_shrink_produces_smaller() {
        for x in [100i32, -50, 17] {
            for smaller in x.shrink() {
                assert!(
                    smaller.abs() < x.abs(),
                    "{} should shrink below {}",
                    smaller,
                    x
                );
            }
        }
    }

    #[test]
    fn test_vec_shrink_shorter() {
        let v = vec![1, 2, 3, 4, 5];
        let shrunk = v.shrink();
        assert!(!shrunk.is_empty());
        for s in shrunk {
            assert!(
                s.len() < v.len(),
                "shrunk {:?} should be shorter than {:?}",
                s,
                v
            );
        }
    }

    #[test]
    fn test_lcg_range() {
        let mut rng = Lcg::new(12345);
        for _ in 0..100 {
            let v = rng.next_i32_in(-10, 10);
            assert!((-10..=10).contains(&v));
        }
    }
}

(* 748: Property-Based Testing — OCaml minimal QuickCheck *)

(* Simple LCG random number generator *)
let seed = ref 12345

let next_int () =
  seed := (!seed * 1664525 + 1013904223) land 0x7FFFFFFF;
  !seed

let rand_int lo hi =
  lo + (next_int () mod (hi - lo + 1))

let rand_list gen lo hi max_len =
  let len = rand_int 0 max_len in
  List.init len (fun _ -> gen lo hi)

(* Property: for all lists, sort is idempotent *)
let prop_sort_idempotent lst =
  let sorted1 = List.sort compare lst in
  let sorted2 = List.sort compare sorted1 in
  sorted1 = sorted2

(* Property: sort preserves length *)
let prop_sort_length lst =
  List.length (List.sort compare lst) = List.length lst

(* Property: sort result is ordered *)
let prop_sort_ordered lst =
  let sorted = List.sort compare lst in
  let rec check = function
    | [] | [_] -> true
    | x :: y :: rest -> x <= y && check (y :: rest)
  in
  check sorted

(* forall: run property on N random inputs *)
let forall n gen prop name =
  let failed = ref 0 in
  for _ = 1 to n do
    let input = gen (-100) 100 20 in
    if not (prop input) then incr failed
  done;
  if !failed = 0
  then Printf.printf "✓ %s: %d tests passed\n" name n
  else Printf.printf "✗ %s: %d/%d FAILED\n" name !failed n

let () =
  forall 1000 (rand_list rand_int) prop_sort_idempotent "sort is idempotent";
  forall 1000 (rand_list rand_int) prop_sort_length    "sort preserves length";
  forall 1000 (rand_list rand_int) prop_sort_ordered   "sort result is ordered"

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_lcg_produces_different_values() {
        let mut rng = Lcg::new(1);
        let a = rng.next_u64();
        let b = rng.next_u64();
        assert_ne!(a, b);
    }

    #[test]
    fn test_property_sort_idempotent() {
        assert!(forall::<Vec<i32>, _>("sort idempotent", 500, |v| {
            my_sort(my_sort(v.clone())) == my_sort(v.clone())
        }));
    }

    #[test]
    fn test_property_sort_length_preserved() {
        assert!(forall::<Vec<i32>, _>("sort length", 500, |v| {
            my_sort(v.clone()).len() == v.len()
        }));
    }

    #[test]
    fn test_property_sort_ordered() {
        assert!(forall::<Vec<i32>, _>("sort ordered", 500, |v| {
            is_sorted(&my_sort(v.clone()))
        }));
    }

    #[test]
    fn test_i32_shrink_produces_smaller() {
        for x in [100i32, -50, 17] {
            for smaller in x.shrink() {
                assert!(
                    smaller.abs() < x.abs(),
                    "{} should shrink below {}",
                    smaller,
                    x
                );
            }
        }
    }

    #[test]
    fn test_vec_shrink_shorter() {
        let v = vec![1, 2, 3, 4, 5];
        let shrunk = v.shrink();
        assert!(!shrunk.is_empty());
        for s in shrunk {
            assert!(
                s.len() < v.len(),
                "shrunk {:?} should be shorter than {:?}",
                s,
                v
            );
        }
    }

    #[test]
    fn test_lcg_range() {
        let mut rng = Lcg::new(12345);
        for _ in 0..100 {
            let v = rng.next_i32_in(-10, 10);
            assert!((-10..=10).contains(&v));
        }
    }
}

Deep Comparison

OCaml vs Rust: Property-Based Testing

QuickCheck-style Testing

OCaml (QCheck)

let test_sort_idempotent =
  QCheck.Test.make ~count:1000
    QCheck.(list small_int)
    (fun l -> List.sort compare (List.sort compare l) = List.sort compare l)

let test_sort_preserves_length =
  QCheck.Test.make ~count:1000
    QCheck.(list small_int)
    (fun l -> List.length (List.sort compare l) = List.length l)

Rust (std-only)

pub trait Arbitrary: Sized + Clone + Debug {
    fn arbitrary(rng: &mut Lcg) -> Self;
    fn shrink(&self) -> Vec<Self> { vec![] }
}

fn forall<T: Arbitrary, F: FnMut(&T) -> bool>(
    name: &str, tests: usize, mut prop: F
) -> bool {
    let mut rng = Lcg::new(42);
    for _ in 0..tests {
        let input = T::arbitrary(&mut rng);
        if !prop(&input) {
            // Shrink to find minimal counterexample
            return false;
        }
    }
    true
}

Shrinking Counterexamples

OCaml

(* QCheck provides automatic shrinking *)
QCheck.Shrink.list

Rust

impl Arbitrary for i32 {
    fn shrink(&self) -> Vec<i32> {
        if *self == 0 { return vec![]; }
        vec![0, self / 2, self.abs() - 1]
            .into_iter()
            .filter(|&x| x.abs() < self.abs())
            .collect()
    }
}

Key Differences

Aspect	OCaml	Rust
Library	QCheck (external)	Can be std-only
Shrinking	Built-in combinators	Manual implementation
Generator	`QCheck.Gen`	`Arbitrary` trait
Integration	Works with OUnit	Works with `#[test]`
Determinism	Seeded PRNG	Seeded PRNG

Exercises

Implement Arbitrary for HashMap<String, i32> and write a property test that verifies map.insert(k, v).get(k) == Some(v) for all random keys and values.

Add a check_stateful function that tests state machine properties: generate random sequences of operations and verify the invariant holds after each step.

Write a property test for the is_palindrome function from example 744: for any string s, verify is_palindrome(s + reverse(s)) is always true.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust