tpt-pattern

Composable, linear-time, safe-by-default pattern matching.

tpt-pattern replaces fragile regex strings with a typed, composable token AST that compiles to a Deterministic Finite Automaton (DFA), guaranteeing strict O(n) linear-time execution and mathematical immunity to ReDoS (Regular Expression Denial of Service).

See GUIDE.md for a full usage guide (builder API, PCRE bridge, captures, iteration), spec.txt for the full design document, and todo.md for the phased roadmap.

Example

use tpt_pattern::{CharClass, Compiled, Pattern};

// Instead of: r"^[a-zA-Z0-9._%+-]+@[a-zA-Z0-9.-]+\.[a-zA-Z]{2,}$"
let email_pattern = Pattern::builder()
    .start_anchor()
    .one_or_more(CharClass::alphanumeric() | CharClass::any_of("._%+-"))
    .literal("@")
    .one_or_more(CharClass::alphanumeric() | CharClass::any_of(".-"))
    .literal(".")
    .repeat(CharClass::alphabetic(), 2..=u32::MAX)
    .end_anchor()
    .build()
    .unwrap();

let compiled = Compiled::new(&email_pattern).unwrap();
assert!(compiled.is_match("user.name@example.com"));
assert!(!compiled.is_match("not an email"));

A common subset of PCRE-style regex strings is also accepted via the bridge, translating directly into the same safe AST:

let re = tpt_pattern::regex(r"^\d{3}-\d{4}$").unwrap();
assert!(re.is_match("123-4567"));

Why not backtracking?

Regex engines built on backtracking (PCRE, Python's re, JavaScript's RegExp, Java's Pattern, ...) can take exponential time on certain input/pattern combinations — a vulnerability class known as ReDoS. A pattern like (a+)+b run against a long string of as with no trailing b forces a backtracking engine to explore an exponential number of ways to partition the string, hanging or crashing the process on untrusted input.

tpt-pattern never backtracks. Every pattern compiles to a DFA (or, when captures/lookahead are requested, a Thompson/Pike NFA simulation that tracks all live states in parallel rather than trying them one at a time). Both execution strategies are strict O(n) in the length of the input, regardless of the pattern — so (a+)+b against an adversarial input completes in the same asymptotic time as against ordinary text. See the re_dos_immunity and redos_adversarial_patterns_stay_fast tests in crates/tpt-pattern/tests/integration.rs for concrete timing assertions, and benches/vs_regex.rs for scanning-throughput comparisons against the (also linear-time) regex crate.

Comparison with the regex crate

The regex crate is also backtracking-free and ReDoS-immune — it compiles to a lazily-constructed DFA under the hood, similar in spirit to tpt-pattern's compiler. The difference is mainly in the surface API and scope:

	tpt-pattern	regex
Pattern authoring	Typed builder API (no strings) + optional PCRE-string bridge	Regex strings only
Capture strategy	Pike VM (NFA simulation) fallback when captures/lookahead are used	Pike VM / lazy DFA hybrid
Bounded lookahead	Supported ((?=...) / (?!...))	Not supported
Backreferences	Rejected at parse time with a clear diagnostic	Not supported
Unicode properties	A documented, hand-picked subset (\p{L}, \p{Nd}, ...)	Full UCD-backed support
SIMD acceleration	Planned (Phase 7)	Yes (memchr, literal prefilters)

Choose tpt-pattern when a typed, string-free pattern API and a fixed-width lookahead construct matter more than full PCRE/Unicode coverage; choose regex for broad ecosystem support and SIMD-accelerated literal scanning today.

Status

This is an early-stage workspace. The typed AST builder, the NFA/DFA compiler, the linear-time runtime, and the PCRE bridge are implemented and tested. See todo.md for the remaining phases (conformance suites, SIMD acceleration, and the v1.0 release).

License

Licensed under either of Apache License, Version 2.0 or MIT license at your option.

Copyright TPT Solutions.