Introduce Property-Based Testing to Validate Engine Invariants #14

New issue

Closed

opened 2026-03-11 18:10:17 +03:00 by NiXTheDev · 0 comments

NiXTheDev commented

2026-03-11 18:10:17 +03:00

(Migrated from github.com)

Goal: Increase test coverage by generating random regex patterns and inputs to verify core properties.

Current unit tests cover specific cases but may miss edge cases. Property-based testing can automatically explore a wide range of inputs and check invariants.

Proposed Approach:
Use the proptest crate to generate random regex ASTs (or patterns) and random input strings, then verify properties like:

If regex.is_match(input) is true, then regex.find(input) should return a match with correct start/end.
find_all should return non-overlapping matches in order.
Backreferences should match the captured text exactly.
Transpilation round-trip (if implemented) should produce a pattern that behaves the same.

Implementation Steps:

Add proptest as a dev-dependency.
Create strategies to generate valid regex patterns (may be complex; start with a subset of features).
Write tests that run proptest to check invariants.
For backreferences, ensure the referenced group exists and the match is consistent.

Example:

proptest! {
    #[test]
    fn test_find_all_non_overlapping(pattern in regex_strategy(), input in ".*") {
        let re = Regex::new(&pattern).unwrap();
        let matches = re.find_all(&input);
        let mut last_end = 0;
        for m in matches {
            assert!(m.start >= last_end);
            last_end = m.end;
        }
    }
}

Benefits:

Catch subtle bugs that unit tests might miss.
Increase confidence in the engine's correctness.

**Goal**: Increase test coverage by generating random regex patterns and inputs to verify core properties. Current unit tests cover specific cases but may miss edge cases. Property-based testing can automatically explore a wide range of inputs and check invariants. **Proposed Approach**: Use the `proptest` crate to generate random regex ASTs (or patterns) and random input strings, then verify properties like: - If `regex.is_match(input)` is true, then `regex.find(input)` should return a match with correct start/end. - `find_all` should return non-overlapping matches in order. - Backreferences should match the captured text exactly. - Transpilation round-trip (if implemented) should produce a pattern that behaves the same. **Implementation Steps**: 1. Add `proptest` as a dev-dependency. 2. Create strategies to generate valid regex patterns (may be complex; start with a subset of features). 3. Write tests that run proptest to check invariants. 4. For backreferences, ensure the referenced group exists and the match is consistent. **Example**: ```rust proptest! { #[test] fn test_find_all_non_overlapping(pattern in regex_strategy(), input in ".*") { let re = Regex::new(&pattern).unwrap(); let matches = re.find_all(&input); let mut last_end = 0; for m in matches { assert!(m.start >= last_end); last_end = m.end; } } } ``` **Benefits**: - Catch subtle bugs that unit tests might miss. - Increase confidence in the engine's correctness.