regexr 0.1.2

A high-performance regex engine built from scratch with JIT compilation and SIMD acceleration
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

//! Backtracking engine module.
//!
//! A PCRE-style backtracking engine that supports backreferences.
//! Uses bytecode compilation for efficient execution.
//!
//! ## Structure
//!
//! - `shared.rs` - Op bytecode enum and helpers (decode_utf8, is_word_byte)
//! - `interpreter/` - Pure Rust execution
//! - `jit/` - JIT-compiled execution (x86-64 only, feature-gated)
//! - `engine.rs` - Engine facade that selects the best backend
//!
//! ## Algorithm
//!
//! This is a traditional backtracking engine with explicit choice points.
//! It supports backreferences which cannot be handled by NFA-based engines.

mod engine;
pub mod interpreter;
pub(crate) mod shared;

#[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
pub mod jit;

// Re-exports
pub use engine::BacktrackingEngine;
pub use interpreter::BacktrackingVm;

#[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
pub use jit::{compile_backtracking, BacktrackingJit};

#[cfg(test)]
mod tests {
    use super::*;
    use crate::hir::translate;
    use crate::parser::parse;

    fn make_engine(pattern: &str) -> BacktrackingEngine {
        let ast = parse(pattern).unwrap();
        let hir = translate(&ast).unwrap();
        BacktrackingEngine::new(&hir)
    }

    #[test]
    fn test_simple_literal() {
        let engine = make_engine("hello");
        assert_eq!(engine.find(b"hello world"), Some((0, 5)));
        assert_eq!(engine.find(b"say hello"), Some((4, 9)));
        assert_eq!(engine.find(b"goodbye"), None);
    }

    #[test]
    fn test_alternation() {
        let engine = make_engine("a|b");
        assert_eq!(engine.find(b"a"), Some((0, 1)));
        assert_eq!(engine.find(b"b"), Some((0, 1)));
        assert_eq!(engine.find(b"c"), None);
    }

    #[test]
    fn test_backref() {
        let engine = make_engine(r"(a)\1");
        assert!(engine.is_match(b"aa"));
        assert!(!engine.is_match(b"ab"));
    }

    #[test]
    fn test_captures() {
        let engine = make_engine(r"(a)(b)(c)");
        let caps = engine.captures(b"abc").unwrap();
        assert_eq!(caps[0], Some((0, 3)));
        assert_eq!(caps[1], Some((0, 1)));
        assert_eq!(caps[2], Some((1, 2)));
        assert_eq!(caps[3], Some((2, 3)));
    }

    #[cfg(all(feature = "jit", any(target_arch = "x86_64", target_arch = "aarch64")))]
    mod jit_tests {
        use super::*;
        use crate::vm::backtracking::jit::compile_backtracking;

        fn make_jit(pattern: &str) -> Option<BacktrackingJit> {
            let ast = parse(pattern).ok()?;
            let hir = translate(&ast).ok()?;
            compile_backtracking(&hir).ok()
        }

        #[test]
        fn test_jit_simple_backref() {
            let jit = make_jit(r"(a)\1").unwrap();
            assert!(jit.is_match(b"aa"));
            assert!(!jit.is_match(b"ab"));
        }

        #[test]
        fn test_jit_quoted_string() {
            let jit = make_jit(r#"(['"])[^'"]*\1"#).unwrap();
            assert!(jit.is_match(br#""hello""#));
            assert!(jit.is_match(b"'world'"));
            assert!(!jit.is_match(br#""mixed'"#));
        }
    }
}