Regular Expression Engine

Problem Statement

Build a regular expression engine that:

• Parses regex patterns into an Abstract Syntax Tree (AST)
• Evaluates patterns using Rust’s pattern matching
• Supports literals, wildcards (.), character classes ([a-z]), quantifiers (*, +, ?, {n,m})
• Implements alternation (|), capture groups, and anchors (^, $, \b)
• Uses backtracking for non-greedy matching
• Optimizes patterns through pattern analysis
• Demonstrates ALL Rust pattern matching features

What Are Regular Expressions?

Regular expressions (regex) are patterns that describe sets of strings. They’re a powerful tool for searching, matching, and manipulating text. Think of them as a mini-language for describing text patterns.

Core Concept: Instead of searching for exact strings, regex lets you search for patterns:

• “Any 3 digits followed by a dash” → matches “123-”, “456-”, “789-”
• “Words starting with ‘A’” → matches “Apple”, “Ant”, “Astronaut”
• “Email addresses” → matches “user@example.com”, “test@test.org”

Real-World Analogy: Like a template or stencil

• Exact string: “Find ‘hello’” → only matches “hello”
• Regex pattern: “Find h.llo” → matches “hello”, “hallo”, “hxllo” (. = any character)

Regex Syntax Reference

Basic Building Blocks

Quantifiers (How Many Times)

Character Classes (Sets of Characters)

Anchors (Position)

Groups and Alternation

Visual Examples

Example: Email Pattern

Pattern: [a-z]+@[a-z]+\.[a-z]+
Breakdown:
  [a-z]+     → one or more lowercase letters (username)
  @          → literal @ symbol
  [a-z]+     → one or more lowercase letters (domain)
  \.         → literal dot (escaped)
  [a-z]+     → one or more lowercase letters (TLD)

Matches:
  ✓ user@example.com
  ✓ test@test.org
  ✗ invalid           (no @)
  ✗ @example.com      (no username)

Example: Phone Number

Pattern: \d{3}-\d{3}-\d{4}
Breakdown:
  \d{3}      → exactly 3 digits
  -          → literal dash
  \d{3}      → exactly 3 digits
  -          → literal dash
  \d{4}      → exactly 4 digits

Matches:
  ✓ 123-456-7890
  ✗ 1234567890        (no dashes)
  ✗ 12-345-6789       (wrong format)

Example: Wildcard Matching

Pattern: h.llo
Breakdown:
  h          → literal 'h'
  .          → any single character
  llo        → literal "llo"

Matches:
  ✓ hello    (. matches 'e')
  ✓ hallo    (. matches 'a')
  ✓ h9llo    (. matches '9')
  ✗ hllo     (. must match something)

Example: Quantifiers

Pattern: ab*c
Breakdown:
  a          → literal 'a'
  b*         → zero or more 'b'
  c          → literal 'c'

Matches:
  ✓ ac       (zero b's)
  ✓ abc      (one b)
  ✓ abbc     (two b's)
  ✓ abbbbc   (four b's)

Pattern: ab+c
Breakdown: b+ means one or more 'b'
Matches:
  ✗ ac       (needs at least one b)
  ✓ abc
  ✓ abbc

Example: Character Classes

Pattern: [aeiou]
Matches: Any single vowel
  ✓ a
  ✓ e
  ✗ b

Pattern: [0-9]
Matches: Any single digit
  ✓ 5
  ✓ 0
  ✗ a

Pattern: [^0-9]
Matches: Any character that's NOT a digit
  ✗ 5
  ✓ a
  ✓ !

How Regex Matching Works

Step-by-Step Matching Process

Pattern: h.llo Text: “say hello there”

Position 0: "say hello there"
            ^
Try "s" vs "h" → FAIL

Position 1: "say hello there"
             ^
Try "a" vs "h" → FAIL

Position 2: "say hello there"
              ^
Try "y" vs "h" → FAIL

Position 3: "say hello there"
               ^
Try " " vs "h" → FAIL

Position 4: "say hello there"
                ^
Try "h" vs "h" → MATCH
Try "e" vs "." → MATCH (. matches any)
Try "l" vs "l" → MATCH
Try "l" vs "l" → MATCH
Try "o" vs "o" → MATCH
SUCCESS! Matched "hello" at position 4

Backtracking Example

Pattern: a*ab Text: “aaab”

Step 1: a* is greedy, matches all "aaa"
        aaab
        ^^^

Step 2: Try to match 'a', but we're at 'b' → FAIL
        aaab
           ^

Step 3: BACKTRACK - Give back one 'a' to a*
        aaab
        ^^

Step 4: Now try to match "ab", SUCCESS!
        aaab
          ^^

Common Use Cases

Regex vs Other Approaches

Key Concepts Explained

This project teaches advanced pattern matching through building a regex engine - one of the most pattern-intensive applications.

1. Recursive Enum Types

Regex patterns are naturally recursive - patterns contain sub-patterns:

#![allow(unused)]
fn main() {
enum Regex {
    Char(char),
    Wildcard,
    Sequence(Vec<Regex>),      // Contains other Regexes
    Alternation(Box<Regex>, Box<Regex>),  // Left OR Right
    Quantifier(Box<Regex>, QuantType),    // Pattern with repetition
}
}

Why it matters: Pattern like (ab)+ is Quantifier(Sequence([Char('a'), Char('b')]), Plus) - nested structures.

2. Exhaustive Pattern Matching

Every enum variant must be handled:

#![allow(unused)]
fn main() {
fn match_at(&self, text: &str, pos: usize) -> Option<usize> {
    match self {
        Regex::Char(c) => match_char(text, pos, *c),
        Regex::Wildcard => match_any(text, pos),
        Regex::Sequence(exprs) => match_sequence(text, pos, exprs),
        // ❌ Forgot Alternation - compiler error!
    }
}
}

Benefit: Add new regex construct → compiler finds all match sites.

3. Range Patterns for Character Classes

Match character ranges directly:

#![allow(unused)]
fn main() {
fn matches_char_class(c: char, ranges: &[(char, char)]) -> bool {
    ranges.iter().any(|(start, end)| matches!(c, start..=end))
}

// Character class [a-zA-Z0-9]
match c {
    'a'..='z' | 'A'..='Z' | '0'..='9' => true,
    _ => false,
}
}

Why it matters: Efficient character set matching without HashSet lookups.

4. Pattern Guards for Validation

Add conditions to match arms:

#![allow(unused)]
fn main() {
match self {
    Regex::CharClass { ranges, chars, negated } if *negated => {
        // Negated class [^abc]
        !matches_any(c, ranges, chars)
    }
    Regex::CharClass { ranges, chars, negated } => {
        // Normal class [abc]
        matches_any(c, ranges, chars)
    }
}
}

Benefit: Same variant with different logic based on flags.

5. Backtracking with Recursion

Try alternatives, backtrack on failure:

#![allow(unused)]
fn main() {
fn match_quantifier(regex: &Regex, min: usize, max: Option<usize>) -> Option<usize> {
    // Greedy: Try maximum matches first
    for count in (min..=max.unwrap_or(usize::MAX)).rev() {
        if let Some(len) = try_match_n_times(regex, count) {
            return Some(len);  // Success!
        }
        // Backtrack: try fewer matches
    }
    None
}
}

Why it matters: Pattern a*ab on “aaab” must backtrack when greedy a* consumes all ’a’s.

6. Box for Recursive Types

Break infinite size cycles:

#![allow(unused)]
fn main() {
enum Regex {
    // ❌ Infinite size - Alternation contains two Regexes
    // Alternation(Regex, Regex),

    // ✅ Fixed size - Box is just a pointer (8 bytes)
    Alternation(Box<Regex>, Box<Regex>),
}
}

Why it matters: Box<T> has known size, enabling recursive enums.

7. Or-Patterns for Multiple Cases

Handle multiple patterns in one arm:

#![allow(unused)]
fn main() {
match token {
    '*' | '+' | '?' | '{' => parse_quantifier(),
    '[' => parse_char_class(),
    '(' => parse_group(),
    '.' => Regex::Wildcard,
    c => Regex::Char(c),
}
}

Benefit: Group similar token types, avoid code duplication.

8. Slice Patterns for Sequences

Match on sequence structure:

#![allow(unused)]
fn main() {
match &exprs[..] {
    [] => Regex::Empty,
    [single] => single.clone(),
    [first, rest @ ..] => {
        // Process first, then rest
    }
}
}

Why it matters: Optimize single-element sequences, handle head/tail patterns.

9. Nested Matching for Complex Logic

Match multiple levels deep:

#![allow(unused)]
fn main() {
match self {
    Regex::Quantifier(box Regex::Char(c), QuantType::Star) => {
        // Optimized path for c*
        match_char_star(c, text, pos)
    }
    Regex::Quantifier(box inner, quant) => {
        // General quantifier matching
        match_quantifier(inner, quant, text, pos)
    }
}
}

Benefit: Detect special cases for optimization.

Connection to This Project

Here’s how each milestone applies these concepts to build a complete regex engine.

Milestone 1: Basic Literal and Wildcard Matching

Concepts applied:

• Recursive enums: Sequence(Vec<Regex>) contains other patterns
• Exhaustive matching: All Regex variants handled in match_at()
• Pattern matching on chars: Literal vs Wildcard matching

Why this matters: Foundation of pattern matching engine.

Real-world impact:

• Without pattern matching: Long if-else chains, easy to miss cases
• With exhaustive matching: Compiler ensures all regex types handled

Performance: Pattern matching compiles to jump tables (O(1) dispatch).

Milestone 2: Character Classes and Range Patterns

Concepts applied:

• Range patterns: 'a'..='z' for efficient character set matching
• Pattern guards: Differentiate [abc] vs [^abc] (negated flag)
• Or-patterns: Match multiple character ranges in one arm

Why this matters: Efficient character set testing without data structures.

Comparison:

Real-world impact: Regex engines process millions of characters - 3-5x speedup matters.

Milestone 3: Quantifiers and Backtracking

Concepts applied:

• Backtracking: Try greedy match, backtrack on failure
• Recursion: Quantifiers call match_at() recursively
• Pattern guards: Min/max validation with guards

Why this matters: Core of regex power - a*, a+, a{2,5}.

Example:

#![allow(unused)]
fn main() {
// Pattern: a*ab
// Text: aaab
// 1. a* greedily matches "aaa"
// 2. Try to match "ab" at position 3 → fails (only "b" left)
// 3. Backtrack: a* gives back one 'a', now has "aa"
// 4. Try to match "ab" at position 2 → SUCCESS
}

Performance: Worst case O(2^n) with excessive backtracking, but rare in practice.

Milestone 4: Alternation and Capture Groups

Concepts applied:

• Box for recursion: Alternation(Box<Regex>, Box<Regex>)
• Try-catch pattern: Try left, if fails try right
• Nested matching: Detect patterns within patterns

Why this matters: Expressive patterns like cat|dog, (ab)+.

Real-world impact:

#![allow(unused)]
fn main() {
// Email validation: (gmail|yahoo|outlook)@\w+\.com
Alternation(
    Alternation(Literal("gmail"), Literal("yahoo")),
    Literal("outlook")
)
}

Memory: Box<T> adds one pointer indirection but enables recursive types.

Milestone 5: Anchors and Advanced Features

Concepts applied:

• Position tracking: Anchors like ^, $, \b check position
• Lookahead/lookbehind: Match without consuming characters
• Optimization: Pattern analysis for fast paths

Why this matters: Full regex feature set.

Optimizations:

Real-world impact: Production regex engines apply dozens of optimizations.

Milestone 1: Basic Literal and Wildcard Matching

Goal: Build the foundation with literals, wildcards, and simple sequences.

Concepts:

• Exhaustive enum matching
• Recursive pattern matching
• Basic string traversal

Implementation Steps

Step 1.1: Define Core AST Types

#![allow(unused)]
fn main() {
// TODO: Define the Regex enum representing all regex constructs
#[derive(Debug, Clone, PartialEq)]
pub enum Regex {
    // TODO: Add Literal variant for exact string matching
 
    // TODO: Add Char variant for single character matching

    // TODO: Add Wildcard variant for '.' (any character)

    // TODO: Add Sequence variant for concatenation

    // TODO: Add Empty variant for empty pattern
}

// TODO: Implement Display for readable pattern output
impl std::fmt::Display for Regex {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        // TODO: Use exhaustive pattern matching to format each variant
        // Pseudocode:
        // match self {
        //     Literal(s) => write the string
        //     Char(c) => write the character
        //     Wildcard => write "."
        //     Sequence(exprs) => loop through and write each expression
        //     Empty => write nothing
        // }
        todo!()
    }
}
}

Step 1.2: Implement Basic Matching Engine

#![allow(unused)]
fn main() {
// TODO: Implement the matching engine
impl Regex {
    /// Match the regex against the input string at the current position
    pub fn is_match(&self, text: &str) -> bool {
        // TODO: Try matching at every position in the text
        // Pseudocode:
        // for each position i from 0 to text.len():
        //     if match_at(text, i) returns Some:
        //         return true
        // return false
        todo!()
    }

    /// Attempt to match at a specific position, returns number of chars consumed
    fn match_at(&self, text: &str, pos: usize) -> Option<usize> {
        // TODO: Use exhaustive pattern matching on self
        // Pseudocode:
        // match self {
        //     Literal(s) =>
        //         if text[pos..] starts with s:
        //             return Some(s.len())
        //         else:
        //             return None
        //
        //     Char(expected) =>
        //         get next char from text[pos..]
        //         if it equals expected:
        //             return Some(char byte length)
        //         else:
        //             return None
        //
        //     Wildcard =>
        //         get next char from text[pos..]
        //         if exists:
        //             return Some(char byte length)
        //         else:
        //             return None
        //
        //     Sequence(exprs) =>
        //         current_pos = pos
        //         for each expr in exprs:
        //             consumed = expr.match_at(text, current_pos)
        //             if consumed is None:
        //                 return None
        //             current_pos += consumed
        //         return Some(current_pos - pos)
        //
        //     Empty => return Some(0)
        // }
        todo!()
    }

    /// Find the position and length of the first match
    pub fn find(&self, text: &str) -> Option<(usize, usize)> {
        // TODO: Return position and length of match
        // Pseudocode:
        // for each position i from 0 to text.len():
        //     if match_at(text, i) returns Some(len):
        //         return Some((i, len))
        // return None
        todo!()
    }
}
}

Step 1.3: Simple Parser

#![allow(unused)]
fn main() {
// TODO: Implement basic parser for literals and wildcards
pub fn parse_simple(pattern: &str) -> Result<Regex, ParseError> {
    // TODO: Handle empty pattern
    // Pseudocode:
    // if pattern is empty:
    //     return Ok(Regex::Empty)
    //
    // exprs = empty vector
    // for each character ch in pattern:
    //     match ch:
    //         '.' => push Regex::Wildcard to exprs
    //         c => push Regex::Char(c) to exprs
    //
    // Optimize single element sequences:
    // match exprs.as_slice():
    //     [] => return Ok(Regex::Empty)
    //     [single] => return Ok(single.clone())
    //     _ => return Ok(Regex::Sequence(exprs))
    todo!()
}

#[derive(Debug, PartialEq)]
pub enum ParseError {
    UnexpectedChar(char),
    UnexpectedEnd,
    InvalidRange,
    InvalidQuantifier,
}
}

Checkpoint Tests

#![allow(unused)]
fn main() {
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_literal_matching() {
        let regex = Regex::Literal("hello".to_string());
        assert!(regex.is_match("hello world"));
        assert!(regex.is_match("say hello there"));
        assert!(!regex.is_match("HELLO"));
    }

    #[test]
    fn test_wildcard_matching() {
        let regex = parse_simple("h.llo").unwrap();
        assert!(regex.is_match("hello"));
        assert!(regex.is_match("hallo"));
        assert!(!regex.is_match("hllo"));
    }

    #[test]
    fn test_sequence_matching() {
        let regex = Regex::Sequence(vec![
            Regex::Char('a'),
            Regex::Wildcard,
            Regex::Char('c'),
        ]);
        assert!(regex.is_match("abc"));
        assert!(regex.is_match("axc"));
        assert!(!regex.is_match("ac"));
    }

    #[test]
    fn test_find_position() {
        let regex = parse_simple("lo").unwrap();
        assert_eq!(regex.find("hello"), Some((3, 2)));
        assert_eq!(regex.find("world"), Some((3, 2)));
        assert_eq!(regex.find("hi"), None);
    }
}
}

Check Your Understanding

1. Why is exhaustive pattern matching important for regex engines?
2. How does the match_at function use recursion for Sequence matching?
3. What would happen if we forgot to handle a variant in the Display impl?
4. How would you extend this to support case-insensitive matching?

Milestone 2: Character Classes and Range Patterns

Goal: Add character classes ([a-z], [0-9]) using range patterns.

Concepts:

• Range patterns ('a'..='z')
• Pattern guards for validation
• Negated character classes

Implementation Steps

Step 2.1: Add CharClass to AST

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq)]
pub enum Regex {
    Literal(String),
    Char(char),
    Wildcard,
    Sequence(Vec<Regex>),
    Empty,

    // TODO: Add character class variant
    // Hint: CharClass {
    //     ranges:          // e.g., ('a', 'z'), ('0', '9')
    //     chars:           // Individual characters
    //     negated:         // true for [^...], false for [...]
    // }
}

impl Regex {
    // TODO: Add helper to create character classes
    pub fn char_class(ranges: Vec<(char, char)>, chars: Vec<char>, negated: bool) -> Self {
        // Pseudocode:
        // return CharClass with the provided ranges, chars, and negated flag
        todo!()
    }

    // TODO: Helper for common classes
    pub fn digit() -> Self {
        // Pseudocode:
        // return CharClass with range ('0', '9'), empty chars, not negated
        todo!()
    }

    pub fn word_char() -> Self {
        // Pseudocode:
        // return CharClass with ranges [('a', 'z'), ('A', 'Z'), ('0', '9')]
        // and chars ['_'], not negated
        todo!()
    }

    pub fn whitespace() -> Self {
        // Pseudocode:
        // return CharClass with empty ranges and chars [' ', '\t', '\n', '\r']
        // not negated
        todo!()
    }
}
}

Step 2.2: Implement CharClass Matching with Range Patterns

#![allow(unused)]
fn main() {
impl Regex {
    fn match_at(&self, text: &str, pos: usize) -> Option<usize> {
        match self {
            // ... existing cases ...

            // TODO: Implement character class matching with range patterns
            Regex::CharClass { ranges, chars, negated } => {
                // Pseudocode:
                // get the next char from text[pos..]
                // if no char exists, return None
                //
                // Check if character matches any range or individual char:
                // matches = false
                // for each (start, end) in ranges:
                //     if char is in range start..=end:
                //         matches = true
                // if chars contains the character:
                //     matches = true
                //
                // Apply negation:
                // result = if negated then !matches else matches
                //
                // if result:
                //     return Some(char byte length)
                // else:
                //     return None
                todo!()
            }

            _ => todo!()
        }
    }
}
}

Step 2.3: Parse Character Classes

#![allow(unused)]
fn main() {
// TODO: Implement character class parser
fn parse_char_class(chars: &[char], pos: &mut usize) -> Result<Regex, ParseError> {
    // Pseudocode:
    // increment pos to skip '['
    //
    // Check for negation:
    // negated = false
    // if chars[*pos] == '^':
    //     negated = true
    //     increment pos
    //
    // ranges = empty vector
    // class_chars = empty vector
    //
    // while pos < chars.len() and chars[*pos] != ']':
    //     start = chars[*pos]
    //     increment pos
    //
    //     Check for range (a-z):
    //     if chars[*pos] == '-' and chars[*pos + 1] exists and != ']':
    //         increment pos to skip '-'
    //         end = chars[*pos]
    //         increment pos
    //
    //         Validate range:
    //         if start > end:
    //             return Err(ParseError::InvalidRange)
    //
    //         add (start, end) to ranges
    //     else:
    //         add start to class_chars
    //
    // Ensure we found closing ']':
    // if pos >= chars.len():
    //     return Err(ParseError::UnexpectedEnd)
    //
    // increment pos to skip ']'
    //
    // return Ok(Regex::CharClass { ranges, chars: class_chars, negated })
    todo!()
}
}

Step 2.4: Display CharClass

#![allow(unused)]
fn main() {
impl std::fmt::Display for Regex {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            // ... existing cases ...

            // TODO: Format character classes
            Regex::CharClass { ranges, chars, negated } => {
                // Pseudocode:
                // write '['
                // if negated, write '^'
                // for each (start, end) in ranges:
                //     write "{start}-{end}"
                // for each ch in chars:
                //     write ch
                // write ']'
                todo!()
            }

            _ => todo!()
        }
    }
}
}

Checkpoint Tests

#![allow(unused)]
fn main() {
#[test]
fn test_char_class_ranges() {
    let regex = Regex::char_class(vec![('a', 'z')], vec![], false);
    assert!(regex.is_match("hello"));
    assert!(!regex.is_match("HELLO"));
    assert!(!regex.is_match("123"));
}

#[test]
fn test_char_class_multiple_ranges() {
    let regex = Regex::char_class(
        vec![('a', 'z'), ('A', 'Z'), ('0', '9')],
        vec![],
        false,
    );
    assert!(regex.is_match("a"));
    assert!(regex.is_match("Z"));
    assert!(regex.is_match("5"));
    assert!(!regex.is_match("!"));
}

#[test]
fn test_negated_char_class() {
    let regex = Regex::char_class(vec![('a', 'z')], vec![], true);
    assert!(!regex.is_match("hello"));
    assert!(regex.is_match("HELLO"));
    assert!(regex.is_match("123"));
}

#[test]
fn test_range_pattern_matching() {
    // Test that our range matching works correctly
    let ch = 'm';
    let in_range = matches!(ch, 'a'..='z');
    assert!(in_range);

    let ch2 = 'M';
    let not_in_range = matches!(ch2, 'a'..='z');
    assert!(!not_in_range);
}
}

Check Your Understanding

1. How do range patterns ('a'..='z') improve code readability over manual comparisons?
2. Why is negation handled differently from normal character class matching?
3. What happens if we create an invalid range like [z-a]?
4. How would you optimize character class matching for large ranges?

Milestone 3: Quantifiers with Backtracking

Goal: Add *, +, ?, {n,m} quantifiers with backtracking.

Concepts:

• Recursive backtracking
• Pattern guards for validation
• Deep destructuring of quantifier bounds

Implementation Steps

Step 3.1: Add Quantifier Variants

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq)]
pub enum Regex {
    Literal(String),
    Char(char),
    Wildcard,
    Sequence(Vec<Regex>),
    Empty,
    CharClass { ranges: Vec<(char, char)>, chars: Vec<char>, negated: bool },

    // TODO: Add quantifier variant
    // Hint: Repeat {
    //     expr: Box<Regex>,
    //     min: usize,          // Minimum repetitions
    //     max: Option<usize>,  // None means unlimited (*)
    // }
}

impl Regex {
    // TODO: Add helper constructors
    pub fn zero_or_more(expr: Regex) -> Self {
        // Pseudocode: return Repeat with min=0, max=None
        todo!()
    }

    pub fn one_or_more(expr: Regex) -> Self {
        // Pseudocode: return Repeat with min=1, max=None
        todo!()
    }

    pub fn optional(expr: Regex) -> Self {
        // Pseudocode: return Repeat with min=0, max=Some(1)
        todo!()
    }

    pub fn exactly(expr: Regex, n: usize) -> Self {
        // Pseudocode: return Repeat with min=n, max=Some(n)
        todo!()
    }

    pub fn between(expr: Regex, min: usize, max: usize) -> Self {
        // Pseudocode: return Repeat with min=min, max=Some(max)
        todo!()
    }
}
}

Step 3.2: Implement Greedy Matching with Backtracking

#![allow(unused)]
fn main() {
impl Regex {
    fn match_at(&self, text: &str, pos: usize) -> Option<usize> {
        match self {
            // ... existing cases ...

            // TODO: Implement quantifier matching with backtracking
            Regex::Repeat { expr, min, max } => {
                // Pseudocode:
                // First, match minimum required times:
                // current_pos = pos
                // for i in 0..*min:
                //     consumed = expr.match_at(text, current_pos)
                //     if consumed is None:
                //         return None (failed to meet minimum)
                //     current_pos += consumed
                //
                // Greedily match as many as possible:
                // matches = empty vector
                // loop:
                //     Check if we've hit the maximum:
                //     if max is Some(max_count) and matches.len() >= max_count:
                //         break
                //
                //     Try to match one more:
                //     consumed = expr.match_at(text, current_pos)
                //     if consumed is Some:
                //         add consumed to matches
                //         current_pos += consumed
                //     else:
                //         break
                //
                // return Some(current_pos - pos)
                todo!()
            }

            _ => todo!()
        }
    }
}
}

Step 3.3: Add Pattern Guards for Quantifier Validation

#![allow(unused)]
fn main() {
// TODO: Validate quantifier bounds
pub fn validate_quantifier(min: usize, max: Option<usize>) -> Result<(), String> {
    // Pseudocode:
    // match (min, max):
    //     (m, Some(mx)) if m <= mx => Ok(())
    //     (_, None) => Ok(()) // unlimited max is valid
    //     (m, Some(mx)) if m > mx => Err("min > max")
    //     _ => unreachable
    todo!()
}

// TODO: Describe quantifier using pattern matching
pub fn describe_quantifier(repeat: &Regex) -> String {
    // Pseudocode:
    // match repeat:
    //     Repeat { min: 0, max: None, .. } => "zero or more (*)"
    //     Repeat { min: 1, max: None, .. } => "one or more (+)"
    //     Repeat { min: 0, max: Some(1), .. } => "optional (?)"
    //     Repeat { min, max: Some(max_val), .. } if min == max_val => "exactly {min}"
    //     Repeat { min, max: Some(max_val), .. } => "between {min} and {max_val}"
    //     Repeat { min, max: None, .. } => "at least {min}"
    //     _ => "not a quantifier"
    todo!()
}
}

Step 3.4: Display Quantifiers

#![allow(unused)]
fn main() {
impl std::fmt::Display for Regex {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            // ... existing cases ...

            // TODO: Format quantifiers using pattern matching
            Regex::Repeat { expr, min, max } => {
                // Pseudocode:
                // write expr
                // match (min, max):
                //     (0, None) => write "*"
                //     (1, None) => write "+"
                //     (0, Some(1)) => write "?"
                //     (m, Some(mx)) if m == mx => write "{{{m}}}"
                //     (m, Some(mx)) => write "{{{m},{mx}}}"
                //     (m, None) => write "{{{m},}}"
                todo!()
            }

            _ => todo!()
        }
    }
}
}

Checkpoint Tests

#![allow(unused)]
fn main() {
#[test]
fn test_zero_or_more() {
    let regex = Regex::zero_or_more(Regex::Char('a'));
    assert!(regex.is_match(""));
    assert!(regex.is_match("a"));
    assert!(regex.is_match("aaaa"));
    assert!(regex.is_match("baaaa")); // Matches at position 1
}

#[test]
fn test_one_or_more() {
    let regex = Regex::one_or_more(Regex::Char('a'));
    assert!(!regex.is_match(""));
    assert!(regex.is_match("a"));
    assert!(regex.is_match("aaaa"));
}

#[test]
fn test_exact_count() {
    let regex = Regex::exactly(Regex::Char('a'), 3);
    assert!(!regex.is_match("aa"));
    assert!(regex.is_match("aaa"));
    assert!(regex.is_match("aaaa")); // Matches first 3
}
}

Check Your Understanding

1. Why does greedy matching try to consume as many characters as possible?
2. How would you implement non-greedy (lazy) matching?
3. What role do pattern guards play in quantifier validation?
4. How does backtracking help when greedy matching fails?

Milestone 4: Alternation and Capture Groups

Goal: Add | alternation and () capture groups with deep destructuring.

Concepts:

• Deep destructuring with Box patterns
• Or-patterns for combining cases
• Capture group tracking

Implementation Steps

Step 4.1: Add Alternation and Group Variants

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq)]
pub enum Regex {
    Literal(String),
    Char(char),
    Wildcard,
    Sequence(Vec<Regex>),
    Empty,
    CharClass { ranges: Vec<(char, char)>, chars: Vec<char>, negated: bool },
    Repeat { expr: Box<Regex>, min: usize, max: Option<usize> },

    // TODO: Add alternation (a|b|c)
    // Hint: Alternation(Vec<Regex>)

    // TODO: Add capture groups
    // Hint: Group {
    //     expr: Box<Regex>,
    //     id: usize,  // Group number for captures
    // }
}

impl Regex {
    pub fn alt(options: Vec<Regex>) -> Self {
        // Pseudocode: return Alternation(options)
        todo!()
    }

    pub fn group(expr: Regex, id: usize) -> Self {
        // Pseudocode: return Group with boxed expr and id
        todo!()
    }
}
}

Step 4.2: Implement Alternation Matching

#![allow(unused)]
fn main() {
impl Regex {
    fn match_at(&self, text: &str, pos: usize) -> Option<usize> {
        match self {
            // ... existing cases ...

            // TODO: Try each alternative until one succeeds
            Regex::Alternation(alts) => {
                // Pseudocode:
                // for each alt in alts:
                //     consumed = alt.match_at(text, pos)
                //     if consumed is Some:
                //         return consumed
                // return None
                todo!()
            }

            // TODO: Groups are transparent for basic matching
            Regex::Group { expr, .. } => {
                // Pseudocode: return expr.match_at(text, pos)
                todo!()
            }

            _ => todo!()
        }
    }
}
}

Step 4.3: Add Capture Extraction with Deep Destructuring

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq)]
pub struct Match {
    pub start: usize,
    pub end: usize,
    pub text: String,
}

#[derive(Debug, Clone)]
pub struct Captures {
    pub full_match: Match,
    pub groups: Vec<Option<Match>>,
}

impl Regex {
    // TODO: Match with capture extraction
    pub fn captures(&self, text: &str) -> Option<Captures> {
        // Pseudocode:
        // for each position i from 0 to text.len():
        //     groups = empty vector
        //     len = self.match_at_with_captures(text, i, &mut groups)
        //     if len is Some:
        //         return Some(Captures {
        //             full_match: Match with i, i+len, and text slice
        //             groups: groups
        //         })
        // return None
        todo!()
    }

    fn match_at_with_captures(
        &self,
        text: &str,
        pos: usize,
        captures: &mut Vec<Option<Match>>,
    ) -> Option<usize> {
        // Pseudocode:
        // match self:
        //     Group { expr, id } =>
        //         Ensure captures vec is large enough for id
        //         start = pos
        //         consumed = expr.match_at_with_captures(text, pos, captures)
        //         if consumed is Some:
        //             end = pos + consumed
        //             Store Match in captures[id]
        //             return consumed
        //         return None
        //
        //     Sequence(exprs) =>
        //         current_pos = pos
        //         for each expr:
        //             consumed = expr.match_at_with_captures(text, current_pos, captures)
        //             if consumed is None: return None
        //             current_pos += consumed
        //         return Some(current_pos - pos)
        //
        //     ... handle other variants similarly ...
        todo!()
    }
}
}

Step 4.4: Pattern Matching for Analysis

#![allow(unused)]
fn main() {
// TODO: Analyze regex complexity using deep destructuring
pub fn count_groups(regex: &Regex) -> usize {
    // Pseudocode:
    // match regex:
    //     Group { expr, .. } => 1 + count_groups(expr)
    //     Sequence(exprs) => sum of count_groups for all exprs
    //     Alternation(alts) => sum of count_groups for all alts
    //     Repeat { expr: box inner, .. } => count_groups(inner)  // deep destructuring
    //     _ => 0 (leaf nodes have no groups)
    todo!()
}

// TODO: Check if regex contains alternation
pub fn has_alternation(regex: &Regex) -> bool {
    // Pseudocode:
    // match regex:
    //     Alternation(_) => true
    //     Sequence(exprs) => any expr has_alternation
    //     Group { expr: box inner, .. } => has_alternation(inner)
    //     Repeat { expr: box inner, .. } => has_alternation(inner)
    //     _ => false
    todo!()
}
}

Checkpoint Tests

#![allow(unused)]
fn main() {
#[test]
fn test_alternation() {
    let regex = Regex::alt(vec![
        Regex::Literal("cat".to_string()),
        Regex::Literal("dog".to_string()),
        Regex::Literal("bird".to_string()),
    ]);

    assert!(regex.is_match("cat"));
    assert!(regex.is_match("dog"));
    assert!(regex.is_match("bird"));
    assert!(!regex.is_match("fish"));
}

#[test]
fn test_capture_groups() {
    // (a+)(b+)
    let regex = Regex::Sequence(vec![
        Regex::group(Regex::one_or_more(Regex::Char('a')), 0),
        Regex::group(Regex::one_or_more(Regex::Char('b')), 1),
    ]);

    let caps = regex.captures("aaabbb").unwrap();
    assert_eq!(caps.full_match.text, "aaabbb");
    assert_eq!(caps.groups[0].as_ref().unwrap().text, "aaa");
    assert_eq!(caps.groups[1].as_ref().unwrap().text, "bbb");
}
}

Check Your Understanding

1. How does deep destructuring with box patterns simplify nested regex analysis?
2. Why do we clone captures when trying alternation branches?
3. What would happen if we forgot to handle captures in the Repeat variant?
4. How would you implement backreferences (e.g., \1 to match first capture again)?

Milestone 5: Anchors, Optimization, and Comprehensive Pattern Matching

Goal: Add anchors (^, $, \b) and optimize using pattern analysis.

Concepts:

• Pattern guards for anchor validation
• Matches! macro for quick checks
• Let-else for error handling
• Comprehensive optimization

Implementation Steps

Step 5.1: Add Anchor Variants

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, PartialEq)]
pub enum Regex {
    Literal(String),
    Char(char),
    Wildcard,
    Sequence(Vec<Regex>),
    Empty,
    CharClass { ranges: Vec<(char, char)>, chars: Vec<char>, negated: bool },
    Repeat { expr: Box<Regex>, min: usize, max: Option<usize> },
    Alternation(Vec<Regex>),
    Group { expr: Box<Regex>, id: usize },

    // TODO: Add anchors
    // Hint: Anchor(AnchorKind)
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum AnchorKind {
    StartOfLine,   // ^
    EndOfLine,     // $
    WordBoundary,  // \b
}
}

Step 5.2: Implement Anchor Matching

#![allow(unused)]
fn main() {
impl Regex {
    fn match_at(&self, text: &str, pos: usize) -> Option<usize> {
        match self {
            // ... existing cases ...

            // TODO: Implement anchor matching with guards
            Regex::Anchor(kind) => {
                // Pseudocode:
                // match kind:
                //     StartOfLine if pos == 0 => Some(0)
                //     EndOfLine if pos == text.len() => Some(0)
                //     WordBoundary =>
                //         if is_word_boundary(text, pos):
                //             Some(0)
                //         else:
                //             None
                //     _ => None (anchor not satisfied at this position)
                todo!()
            }

            _ => todo!()
        }
    }

    // TODO: Helper to check word boundaries
    fn is_word_boundary(text: &str, pos: usize) -> bool {
        // Pseudocode:
        // before = if pos > 0: last char before pos else None
        // after = char at pos
        //
        // before_is_word = matches!(before, Some('a'..='z' | 'A'..='Z' | '0'..='9' | '_'))
        // after_is_word = matches!(after, Some('a'..='z' | 'A'..='Z' | '0'..='9' | '_'))
        //
        // Boundary if exactly one side is a word character:
        // return before_is_word != after_is_word
        todo!()
    }
}
}

Step 5.3: Optimize Patterns Using Pattern Matching

#![allow(unused)]
fn main() {
// TODO: Optimize regex by simplifying patterns
pub fn optimize(regex: Regex) -> Regex {
    // Pseudocode:
    // match regex:
    //     Sequence(exprs) if exprs is empty => Regex::Empty
    //
    //     Sequence(exprs) match exprs.as_slice():
    //         [] => Regex::Empty
    //         [single] => optimize(single.clone())
    //         _ => Sequence of optimized exprs
    //
    //     Alternation(alts) match alts.as_slice():
    //         [] => Regex::Empty
    //         [single] => optimize(single.clone())
    //         _ => Alternation of optimized alts
    //
    //     Repeat { expr, min, max } =>
    //         optimized_expr = optimize(expr)
    //         match (min, max):
    //             (0, Some(0)) => Regex::Empty  // {0,0} is empty
    //             (1, Some(1)) => optimized_expr  // {1,1} is just the expression
    //             _ => Repeat with optimized_expr
    //
    //     Group { expr, id } => Group with optimized expr
    //
    //     other => other (leaf nodes don't need optimization)
    todo!()
}

// TODO: Check if regex is anchored at start
pub fn is_anchored_at_start(regex: &Regex) -> bool {
    // Pseudocode:
    // match regex:
    //     Anchor(StartOfLine) => true
    //     Sequence(exprs) =>
    //         first element is Anchor(StartOfLine)
    //     Group { expr, .. } => is_anchored_at_start(expr)
    //     _ => false
    todo!()
}

// TODO: Check if regex matches only fixed strings (no wildcards/quantifiers)
pub fn is_literal_only(regex: &Regex) -> bool {
    // Pseudocode:
    // match regex:
    //     Literal(_) | Char(_) | Empty => true
    //     Sequence(exprs) => all exprs are is_literal_only
    //     Group { expr, .. } => is_literal_only(expr)
    //     Wildcard | CharClass { .. } | Repeat { .. } | Alternation(_) | Anchor(_) => false
    todo!()
}
}

Step 5.4: Let-Else for Error Handling

#![allow(unused)]
fn main() {
// TODO: Extract literal string from regex using let-else
pub fn extract_literal(regex: &Regex) -> Result<String, &'static str> {
    // Pseudocode:
    // let Regex::Literal(s) = regex else {
    //     return Err("Not a literal pattern");
    // };
    // Ok(s.clone())
    todo!()
}

// TODO: Extract group ID using let-else
pub fn extract_group_id(regex: &Regex) -> Result<usize, &'static str> {
    // Pseudocode:
    // let Regex::Group { id, .. } = regex else {
    //     return Err("Not a group");
    // };
    // Ok(*id)
    todo!()
}

// TODO: Get quantifier bounds using let-else
pub fn get_quantifier_bounds(regex: &Regex) -> Result<(usize, Option<usize>), &'static str> {
    // Pseudocode:
    // let Regex::Repeat { min, max, .. } = regex else {
    //     return Err("Not a quantifier");
    // };
    // Ok((*min, *max))
    todo!()
}
}

Step 5.5: Comprehensive Display Implementation

#![allow(unused)]
fn main() {
impl std::fmt::Display for Regex {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        // TODO: Exhaustive pattern matching for all variants
        // Pseudocode:
        // match self:
        //     Literal(s) => write s
        //     Char(c) => write c
        //     Wildcard => write "."
        //     CharClass { ... } => write [...] with ranges and chars
        //     Sequence(exprs) => write each expr
        //     Repeat { expr, min, max } =>
        //         Add parentheses if expr is complex
        //         Write expr
        //         Write quantifier suffix (*, +, ?, {n,m})
        //     Alternation(alts) => write alts separated by |
        //     Group { expr, .. } => write (expr)
        //     Anchor(kind) =>
        //         StartOfLine => write "^"
        //         EndOfLine => write "$"
        //         WordBoundary => write "\\b"
        //     Empty => write nothing
        todo!()
    }
}
}

Checkpoint Tests

#![allow(unused)]
fn main() {
#[test]
fn test_start_anchor() {
    let regex = Regex::Sequence(vec![
        Regex::Anchor(AnchorKind::StartOfLine),
        Regex::Literal("hello".to_string()),
    ]);

    assert!(regex.is_match("hello world"));
    assert!(!regex.is_match("say hello"));
}

#[test]
fn test_word_boundary() {
    let regex = Regex::Sequence(vec![
        Regex::Anchor(AnchorKind::WordBoundary),
        Regex::Literal("word".to_string()),
        Regex::Anchor(AnchorKind::WordBoundary),
    ]);

    assert!(regex.is_match("a word here"));
    assert!(regex.is_match("word"));
    assert!(!regex.is_match("sword"));
    assert!(!regex.is_match("words"));
}

#[test]
fn test_optimization() {
    let regex = Regex::Sequence(vec![Regex::Char('a')]);
    let optimized = optimize(regex);
    assert_eq!(optimized, Regex::Char('a'));
}
}

Check Your Understanding

1. How do pattern guards help validate anchor positions?
2. Why is the matches! macro useful for character classification?
3. How does let-else improve error handling compared to if-let?
4. What optimizations could you add for common patterns like a*a+ → a+?

Complete Integration Tests

#![allow(unused)]
fn main() {
#[cfg(test)]
mod integration_tests {
    use super::*;

    #[test]
    fn test_email_validation() {
        // Simplified: [a-z]+@[a-z]+\.[a-z]+
        let regex = Regex::Sequence(vec![
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
            Regex::Char('@'),
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
            Regex::Char('.'),
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
        ]);

        assert!(regex.is_match("user@example.com"));
        assert!(regex.is_match("test@test.org"));
        assert!(!regex.is_match("invalid"));
        assert!(!regex.is_match("@example.com"));
    }

    #[test]
    fn test_phone_number() {
        // \d{3}-\d{3}-\d{4}
        let regex = Regex::Sequence(vec![
            Regex::exactly(Regex::digit(), 3),
            Regex::Char('-'),
            Regex::exactly(Regex::digit(), 3),
            Regex::Char('-'),
            Regex::exactly(Regex::digit(), 4),
        ]);

        assert!(regex.is_match("123-456-7890"));
        assert!(!regex.is_match("1234567890"));
        assert!(!regex.is_match("123-45-6789"));
    }

    #[test]
    fn test_url_matching() {
        // https?://[a-z]+\.[a-z]+
        let regex = Regex::Sequence(vec![
            Regex::Literal("http".to_string()),
            Regex::optional(Regex::Char('s')),
            Regex::Literal("://".to_string()),
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
            Regex::Char('.'),
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
        ]);

        assert!(regex.is_match("http://example.com"));
        assert!(regex.is_match("https://test.org"));
        assert!(!regex.is_match("ftp://example.com"));
    }
}
}

Benchmarks

#![allow(unused)]
fn main() {
#[cfg(test)]
mod benchmarks {
    use super::*;
    use std::time::Instant;

    #[test]
    fn bench_simple_literal() {
        let regex = Regex::Literal("test".to_string());
        let text = "this is a test string with test repeated";

        let start = Instant::now();
        for _ in 0..100_000 {
            regex.is_match(text);
        }
        let elapsed = start.elapsed();
        println!("Simple literal: {:?}", elapsed);
    }

    #[test]
    fn bench_complex_pattern() {
        let regex = Regex::Sequence(vec![
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
            Regex::Char('@'),
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
        ]);
        let text = "contact user@example.com for info";

        let start = Instant::now();
        for _ in 0..10_000 {
            regex.is_match(text);
        }
        let elapsed = start.elapsed();
        println!("Complex pattern: {:?}", elapsed);
    }
}
}

Project-Wide Benefits

Concrete comparisons - Matching 1M patterns:

Complete Working Example

//! complete_07_regex_parser.rs
//!
//! A small, educational regex engine implemented with Rust pattern matching.
//!
//! Supported (Milestones):
//! 1) Literals, '.' wildcard, concatenation, empty
//! 2) Character classes: [a-z], [^...], and escapes: \d, \w, \s
//! 3) Quantifiers: *, +, ?, {n}, {n,m}, {n,} with greedy backtracking
//! 4) Alternation: a|b|c and capture groups: ( ... )
//! 5) Anchors: ^, $, and word boundary: \b
//!    + basic optimization (flattening, singleton simplifications)
//!
//! Run:
//!   cargo run --bin complete_07_regex_parser
//! Test:
//!   cargo test --bin complete_07_regex_parser

use std::fmt;

#[derive(Debug, Clone, PartialEq)]
pub enum Regex {
    Empty,
    Literal(String), // multi-char literal chunk (optimized)
    Char(char),
    Wildcard, // .
    Sequence(Vec<Regex>),
    CharClass {
        ranges: Vec<(char, char)>,
        chars: Vec<char>,
        negated: bool,
    },
    Repeat {
        expr: Box<Regex>,
        min: usize,
        max: Option<usize>, // None = unbounded
    },
    Alternation(Vec<Regex>),
    Group {
        id: usize,
        expr: Box<Regex>,
    },
    Anchor(AnchorKind),
}

#[derive(Debug, Clone, Copy, PartialEq)]
pub enum AnchorKind {
    StartOfLine,  // ^
    EndOfLine,    // $
    WordBoundary, // \b
}

#[derive(Debug, Clone, PartialEq)]
pub enum ParseError {
    UnexpectedEnd,
    UnexpectedChar(char),
    UnclosedGroup,
    UnclosedCharClass,
    InvalidRange,
    InvalidQuantifier,
    EmptyAlternationBranch,
}

impl fmt::Display for ParseError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        use ParseError::*;
        match self {
            UnexpectedEnd => write!(f, "unexpected end of pattern"),
            UnexpectedChar(c) => write!(f, "unexpected char '{c}'"),
            UnclosedGroup => write!(f, "unclosed group"),
            UnclosedCharClass => write!(f, "unclosed character class"),
            InvalidRange => write!(f, "invalid character range"),
            InvalidQuantifier => write!(f, "invalid quantifier"),
            EmptyAlternationBranch => write!(f, "empty alternation branch"),
        }
    }
}

impl std::error::Error for ParseError {}

impl Regex {
    /* ---------- Convenience constructors ---------- */

    pub fn char_class(ranges: Vec<(char, char)>, chars: Vec<char>, negated: bool) -> Self {
        Regex::CharClass {
            ranges,
            chars,
            negated,
        }
    }

    pub fn digit() -> Self {
        Regex::char_class(vec![('0', '9')], vec![], false)
    }

    pub fn word_char() -> Self {
        Regex::char_class(vec![('a', 'z'), ('A', 'Z'), ('0', '9')], vec!['_'], false)
    }

    pub fn whitespace() -> Self {
        Regex::char_class(vec![], vec![' ', '\t', '\n', '\r'], false)
    }

    pub fn zero_or_more(expr: Regex) -> Self {
        Regex::Repeat {
            expr: Box::new(expr),
            min: 0,
            max: None,
        }
    }

    pub fn one_or_more(expr: Regex) -> Self {
        Regex::Repeat {
            expr: Box::new(expr),
            min: 1,
            max: None,
        }
    }

    pub fn optional(expr: Regex) -> Self {
        Regex::Repeat {
            expr: Box::new(expr),
            min: 0,
            max: Some(1),
        }
    }

    pub fn exactly(expr: Regex, n: usize) -> Self {
        Regex::Repeat {
            expr: Box::new(expr),
            min: n,
            max: Some(n),
        }
    }

    pub fn between(expr: Regex, min: usize, max: usize) -> Self {
        Regex::Repeat {
            expr: Box::new(expr),
            min,
            max: Some(max),
        }
    }

    pub fn alt(options: Vec<Regex>) -> Self {
        Regex::Alternation(options)
    }

    pub fn group(expr: Regex, id: usize) -> Self {
        Regex::Group {
            id,
            expr: Box::new(expr),
        }
    }

    /* ---------- Public API ---------- */

    pub fn parse(pattern: &str) -> Result<Self, ParseError> {
        Parser::new(pattern).parse()
    }

    pub fn optimize(self) -> Self {
        optimize(self)
    }

    /// Returns true if the regex matches anywhere in `text`.
    pub fn is_match(&self, text: &str) -> bool {
        self.find(text).is_some()
    }

    /// Returns (start, len) of the first match.
    pub fn find(&self, text: &str) -> Option<(usize, usize)> {
        let anchored = is_anchored_at_start(self);
        let start_positions: Box<dyn Iterator<Item = usize>> = if anchored {
            Box::new(std::iter::once(0))
        } else {
            Box::new(char_boundaries(text))
        };

        for start in start_positions {
            let caps = Captures::new(count_groups(self));
            for (end, _caps2) in self.match_from(text, start, caps.clone()) {
                return Some((start, end - start));
            }
        }
        None
    }

    /// Returns captures if the regex matches anywhere in `text`.
    pub fn captures(&self, text: &str) -> Option<Captures> {
        let anchored = is_anchored_at_start(self);
        let start_positions: Box<dyn Iterator<Item = usize>> = if anchored {
            Box::new(std::iter::once(0))
        } else {
            Box::new(char_boundaries(text))
        };

        for start in start_positions {
            let caps = Captures::new(count_groups(self));
            for (end, caps2) in self.match_from(text, start, caps.clone()) {
                let full = Match {
                    start,
                    end,
                    text: text[start..end].to_string(),
                };
                let mut out = caps2;
                out.full_match = Some(full);
                return Some(out);
            }
        }
        None
    }

    /* ---------- Internal matching with backtracking ---------- */

    /// Returns all possible (end_pos, captures) after matching at `pos`.
    fn match_from(&self, text: &str, pos: usize, caps: Captures) -> Vec<(usize, Captures)> {
        match self {
            Regex::Empty => vec![(pos, caps)],

            Regex::Literal(s) => {
                if text[pos..].starts_with(s) {
                    vec![(pos + s.len(), caps)]
                } else {
                    vec![]
                }
            }

            Regex::Char(c) => match next_char(text, pos) {
                Some((ch, next)) if ch == *c => vec![(next, caps)],
                _ => vec![],
            },

            Regex::Wildcard => match next_char(text, pos) {
                Some((_ch, next)) => vec![(next, caps)],
                None => vec![],
            },

            Regex::CharClass {
                ranges,
                chars,
                negated,
            } => match next_char(text, pos) {
                Some((ch, next)) => {
                    let mut matched = chars.contains(&ch);
                    if !matched {
                        matched = ranges
                            .iter()
                            .any(|(a, b)| matches!(ch, x if x >= *a && x <= *b));
                    }
                    let ok = if *negated { !matched } else { matched };
                    if ok {
                        vec![(next, caps)]
                    } else {
                        vec![]
                    }
                }
                None => vec![],
            },

            Regex::Anchor(kind) => {
                let ok = match kind {
                    AnchorKind::StartOfLine => pos == 0,
                    AnchorKind::EndOfLine => pos == text.len(),
                    AnchorKind::WordBoundary => is_word_boundary(text, pos),
                };
                if ok {
                    vec![(pos, caps)]
                } else {
                    vec![]
                }
            }

            Regex::Sequence(exprs) => {
                // fold left, carrying all backtracking branches
                let mut states: Vec<(usize, Captures)> = vec![(pos, caps)];
                for expr in exprs {
                    let mut next_states = Vec::new();
                    for (p, c) in states {
                        next_states.extend(expr.match_from(text, p, c));
                    }
                    if next_states.is_empty() {
                        return vec![];
                    }
                    states = next_states;
                }
                states
            }

            Regex::Alternation(alts) => {
                let mut out = Vec::new();
                for alt in alts {
                    out.extend(alt.match_from(text, pos, caps.clone()));
                }
                out
            }

            Regex::Group { id, expr } => {
                let start = pos;
                let mut out = Vec::new();
                for (end, mut caps2) in expr.match_from(text, pos, caps) {
                    let m = Match {
                        start,
                        end,
                        text: text[start..end].to_string(),
                    };
                    caps2.set_group(*id, m);
                    out.push((end, caps2));
                }
                out
            }

            Regex::Repeat { expr, min, max } => {
                // Greedy: generate the most-consumed options first, then backtrack.
                // Strategy:
                // 1) Match `min` times (must succeed).
                // 2) Then match as many more as possible up to `max`.
                // 3) Return all possible ends in descending consumption order.
                let mut seeds: Vec<(usize, Captures)> = vec![(pos, caps)];
                for _ in 0..*min {
                    let mut next = Vec::new();
                    for (p, c) in seeds {
                        next.extend(expr.match_from(text, p, c));
                    }
                    if next.is_empty() {
                        return vec![];
                    }
                    seeds = next;
                }

                // Now expand greedily for the remaining repetitions.
                let mut layers: Vec<Vec<(usize, Captures)>> = Vec::new();
                layers.push(seeds);

                let mut reps_done = *min;
                loop {
                    if let Some(mx) = *max {
                        if reps_done >= mx {
                            break;
                        }
                    }

                    let last = layers.last().cloned().unwrap_or_default();
                    let mut next = Vec::new();
                    for (p, c) in last {
                        // prevent infinite loops on empty matches
                        let matches = expr.match_from(text, p, c);
                        for (p2, c2) in matches {
                            if p2 != p {
                                next.push((p2, c2));
                            }
                        }
                    }
                    if next.is_empty() {
                        break;
                    }
                    layers.push(next);
                    reps_done += 1;
                }

                // Greedy order: largest layer first (most reps), then earlier.
                let mut out = Vec::new();
                for layer in layers.into_iter().rev() {
                    out.extend(layer);
                }
                out
            }
        }
    }
}

/* ============================================================
 * Captures
 * ============================================================
 */

#[derive(Debug, Clone, PartialEq)]
pub struct Match {
    pub start: usize,
    pub end: usize,
    pub text: String,
}

#[derive(Debug, Clone, PartialEq)]
pub struct Captures {
    pub full_match: Option<Match>,
    pub groups: Vec<Option<Match>>,
}

impl Captures {
    fn new(group_count: usize) -> Self {
        Self {
            full_match: None,
            groups: vec![None; group_count],
        }
    }

    fn set_group(&mut self, id: usize, m: Match) {
        if id < self.groups.len() {
            self.groups[id] = Some(m);
        }
    }
}

/* ============================================================
 * Parser (recursive descent)
 * ============================================================
 */

struct Parser<'a> {
    chars: Vec<char>,
    pos: usize,
    group_id: usize,
    _src: &'a str,
}

impl<'a> Parser<'a> {
    fn new(src: &'a str) -> Self {
        Self {
            chars: src.chars().collect(),
            pos: 0,
            group_id: 0,
            _src: src,
        }
    }

    fn parse(mut self) -> Result<Regex, ParseError> {
        let expr = self.parse_alternation()?;
        if self.pos != self.chars.len() {
            return Err(ParseError::UnexpectedChar(self.chars[self.pos]));
        }
        Ok(optimize(expr))
    }

    // alternation := concat ('|' concat)*
    fn parse_alternation(&mut self) -> Result<Regex, ParseError> {
        let mut branches = Vec::new();
        branches.push(self.parse_concat()?);

        while self.peek() == Some('|') {
            self.pos += 1; // consume '|'
            if matches!(self.peek(), Some(')' | '|') | None) {
                return Err(ParseError::EmptyAlternationBranch);
            }
            branches.push(self.parse_concat()?);
        }

        if branches.len() == 1 {
            Ok(branches.remove(0))
        } else {
            Ok(Regex::Alternation(branches))
        }
    }

    // concat := repeat+
    fn parse_concat(&mut self) -> Result<Regex, ParseError> {
        let mut parts = Vec::new();
        while let Some(c) = self.peek() {
            if matches!(c, ')' | '|') {
                break;
            }
            parts.push(self.parse_repeat()?);
        }
        Ok(Regex::Sequence(parts))
    }

    // repeat := atom quant?
    fn parse_repeat(&mut self) -> Result<Regex, ParseError> {
        let atom = self.parse_atom()?;
        if let Some(q) = self.peek() {
            match q {
                '*' => {
                    self.pos += 1;
                    return Ok(Regex::zero_or_more(atom));
                }
                '+' => {
                    self.pos += 1;
                    return Ok(Regex::one_or_more(atom));
                }
                '?' => {
                    self.pos += 1;
                    return Ok(Regex::optional(atom));
                }
                '{' => {
                    let (min, max) = self.parse_brace_quantifier()?;
                    validate_quantifier(min, max)?;
                    self.pos += 1; // consume '}'
                    return Ok(Regex::Repeat {
                        expr: Box::new(atom),
                        min,
                        max,
                    });
                }
                _ => {}
            }
        }
        Ok(atom)
    }

    // atom := group | class | anchor | escaped | '.' | literal_char
    fn parse_atom(&mut self) -> Result<Regex, ParseError> {
        let Some(c) = self.peek() else {
            return Err(ParseError::UnexpectedEnd);
        };

        match c {
            '(' => self.parse_group(),
            '[' => self.parse_char_class(),
            '.' => {
                self.pos += 1;
                Ok(Regex::Wildcard)
            }
            '^' => {
                self.pos += 1;
                Ok(Regex::Anchor(AnchorKind::StartOfLine))
            }
            '$' => {
                self.pos += 1;
                Ok(Regex::Anchor(AnchorKind::EndOfLine))
            }
            '\\' => self.parse_escape(),
            // literal
            _ => {
                self.pos += 1;
                Ok(Regex::Char(c))
            }
        }
    }

    fn parse_group(&mut self) -> Result<Regex, ParseError> {
        // consume '('
        self.expect('(')?;
        let id = self.group_id;
        self.group_id += 1;

        if self.peek().is_none() {
            return Err(ParseError::UnclosedGroup);
        }

        let inner = self.parse_alternation()?;

        if self.peek() != Some(')') {
            return Err(ParseError::UnclosedGroup);
        }
        self.pos += 1; // consume ')'

        Ok(Regex::Group {
            id,
            expr: Box::new(inner),
        })
    }

    fn parse_escape(&mut self) -> Result<Regex, ParseError> {
        self.expect('\\')?;
        let Some(c) = self.peek() else {
            return Err(ParseError::UnexpectedEnd);
        };
        self.pos += 1;
        Ok(match c {
            'd' => Regex::digit(),
            'w' => Regex::word_char(),
            's' => Regex::whitespace(),
            'b' => Regex::Anchor(AnchorKind::WordBoundary),
            // escape metacharacters to literal
            '\\' | '.' | '[' | ']' | '(' | ')' | '{' | '}' | '*' | '+' | '?' | '|' | '^' | '$' => {
                Regex::Char(c)
            }
            other => return Err(ParseError::UnexpectedChar(other)),
        })
    }

    fn parse_char_class(&mut self) -> Result<Regex, ParseError> {
        self.expect('[')?;
        let mut negated = false;
        if self.peek() == Some('^') {
            negated = true;
            self.pos += 1;
        }

        let mut ranges: Vec<(char, char)> = Vec::new();
        let mut chars: Vec<char> = Vec::new();

        while let Some(c) = self.peek() {
            if c == ']' {
                self.pos += 1;
                return Ok(Regex::CharClass {
                    ranges,
                    chars,
                    negated,
                });
            }

            // parse an element (could be escaped)
            let start = if c == '\\' {
                // allow \d, \w, \s inside class by expanding to ranges/chars
                self.pos += 1;
                let Some(ec) = self.peek() else {
                    return Err(ParseError::UnexpectedEnd);
                };
                self.pos += 1;
                match ec {
                    'd' => {
                        ranges.push(('0', '9'));
                        continue;
                    }
                    'w' => {
                        ranges.extend([('a', 'z'), ('A', 'Z'), ('0', '9')]);
                        chars.push('_');
                        continue;
                    }
                    's' => {
                        chars.extend([' ', '\t', '\n', '\r']);
                        continue;
                    }
                    // escaped literal
                    '\\' | '-' | ']' | '^' => ec,
                    other => return Err(ParseError::UnexpectedChar(other)),
                }
            } else {
                self.pos += 1;
                c
            };

            // range?
            if self.peek() == Some('-') {
                // lookahead to see if valid range (next not ']')
                if self.peek_n(1).is_some_and(|n| n != ']') {
                    self.pos += 1; // consume '-'
                    let Some(end) = self.peek() else {
                        return Err(ParseError::UnexpectedEnd);
                    };
                    let end = if end == '\\' {
                        self.pos += 1;
                        let Some(ec) = self.peek() else {
                            return Err(ParseError::UnexpectedEnd);
                        };
                        self.pos += 1;
                        ec
                    } else {
                        self.pos += 1;
                        end
                    };

                    if start > end {
                        return Err(ParseError::InvalidRange);
                    }
                    ranges.push((start, end));
                    continue;
                }
            }

            chars.push(start);
        }

        Err(ParseError::UnclosedCharClass)
    }

    fn parse_brace_quantifier(&mut self) -> Result<(usize, Option<usize>), ParseError> {
        self.expect('{')?;

        let min = self.parse_number()?;
        let mut max = None;

        match self.peek() {
            Some('}') => return Ok((min, Some(min))),
            Some(',') => {
                self.pos += 1;
                match self.peek() {
                    Some('}') => {
                        max = None; // {n,}
                    }
                    Some(_) => {
                        let m = self.parse_number()?;
                        max = Some(m);
                    }
                    None => return Err(ParseError::UnexpectedEnd),
                }
            }
            Some(c) => return Err(ParseError::UnexpectedChar(c)),
            None => return Err(ParseError::UnexpectedEnd),
        }

        if self.peek() != Some('}') {
            return Err(ParseError::InvalidQuantifier);
        }
        Ok((min, max))
    }

    fn parse_number(&mut self) -> Result<usize, ParseError> {
        let mut val: usize = 0;
        let mut saw = false;
        while let Some(c) = self.peek() {
            if let Some(d) = c.to_digit(10) {
                saw = true;
                val = val
                    .checked_mul(10)
                    .and_then(|v| v.checked_add(d as usize))
                    .ok_or(ParseError::InvalidQuantifier)?;
                self.pos += 1;
            } else {
                break;
            }
        }
        if !saw {
            return Err(ParseError::InvalidQuantifier);
        }
        Ok(val)
    }

    fn peek(&self) -> Option<char> {
        self.chars.get(self.pos).copied()
    }

    fn peek_n(&self, n: usize) -> Option<char> {
        self.chars.get(self.pos + n).copied()
    }

    fn expect(&mut self, c: char) -> Result<(), ParseError> {
        if self.peek() == Some(c) {
            self.pos += 1;
            Ok(())
        } else {
            Err(self
                .peek()
                .map(ParseError::UnexpectedChar)
                .unwrap_or(ParseError::UnexpectedEnd))
        }
    }
}

/* ============================================================
 * Utilities + analysis + optimization
 * ============================================================
 */

fn char_boundaries(s: &str) -> impl Iterator<Item = usize> + '_ {
    std::iter::once(0).chain(s.char_indices().skip(1).map(|(i, _)| i))
}

fn next_char(s: &str, pos: usize) -> Option<(char, usize)> {
    if pos > s.len() {
        return None;
    }
    let mut it = s[pos..].chars();
    let ch = it.next()?;
    let next = pos + ch.len_utf8();
    Some((ch, next))
}

fn is_word_char(c: char) -> bool {
    matches!(c, 'a'..='z' | 'A'..='Z' | '0'..='9' | '_')
}

fn is_word_boundary(text: &str, pos: usize) -> bool {
    let before = if pos == 0 {
        None
    } else {
        text[..pos].chars().rev().next()
    };
    let after = text[pos..].chars().next();

    let before_is = before.is_some_and(is_word_char);
    let after_is = after.is_some_and(is_word_char);

    before_is ^ after_is
}

pub fn validate_quantifier(min: usize, max: Option<usize>) -> Result<(), ParseError> {
    match (min, max) {
        (_, None) => Ok(()),
        (m, Some(mx)) if m <= mx => Ok(()),
        _ => Err(ParseError::InvalidQuantifier),
    }
}

pub fn describe_quantifier(repeat: &Regex) -> String {
    match repeat {
        Regex::Repeat { min: 0, max: None, .. } => "zero or more (*)".into(),
        Regex::Repeat { min: 1, max: None, .. } => "one or more (+)".into(),
        Regex::Repeat { min: 0, max: Some(1), .. } => "optional (?)".into(),
        Regex::Repeat { min, max: Some(mx), .. } if min == mx => format!("exactly {{{min}}}"),
        Regex::Repeat { min, max: Some(mx), .. } => format!("between {{{min},{mx}}}"),
        Regex::Repeat { min, max: None, .. } => format!("at least {{{min},}}"),
        _ => "not a quantifier".into(),
    }
}

pub fn count_groups(regex: &Regex) -> usize {
    match regex {
        Regex::Group { expr, .. } => 1 + count_groups(expr),
        Regex::Sequence(xs) | Regex::Alternation(xs) => xs.iter().map(count_groups).sum(),
        Regex::Repeat { expr, .. } => count_groups(expr),
        _ => 0,
    }
}

pub fn has_alternation(regex: &Regex) -> bool {
    match regex {
        Regex::Alternation(_) => true,
        Regex::Sequence(xs) => xs.iter().any(has_alternation),
        Regex::Group { expr, .. } => has_alternation(expr),
        Regex::Repeat { expr, .. } => has_alternation(expr),
        _ => false,
    }
}

pub fn is_anchored_at_start(regex: &Regex) -> bool {
    match regex {
        Regex::Anchor(AnchorKind::StartOfLine) => true,
        Regex::Sequence(xs) => xs.first().is_some_and(|r| matches!(r, Regex::Anchor(AnchorKind::StartOfLine))),
        Regex::Group { expr, .. } => is_anchored_at_start(expr),
        _ => false,
    }
}

pub fn is_literal_only(regex: &Regex) -> bool {
    match regex {
        Regex::Empty | Regex::Literal(_) | Regex::Char(_) => true,
        Regex::Sequence(xs) => xs.iter().all(is_literal_only),
        Regex::Group { expr, .. } => is_literal_only(expr),
        _ => false,
    }
}

pub fn extract_literal(regex: &Regex) -> Result<String, &'static str> {
    let Regex::Literal(s) = regex else { return Err("Not a literal pattern"); };
    Ok(s.clone())
}

pub fn extract_group_id(regex: &Regex) -> Result<usize, &'static str> {
    let Regex::Group { id, .. } = regex else { return Err("Not a group"); };
    Ok(*id)
}

pub fn get_quantifier_bounds(regex: &Regex) -> Result<(usize, Option<usize>), &'static str> {
    let Regex::Repeat { min, max, .. } = regex else { return Err("Not a quantifier"); };
    Ok((*min, *max))
}

pub fn optimize(regex: Regex) -> Regex {
    match regex {
        Regex::Sequence(mut xs) => {
            // optimize children
            xs = xs.into_iter().map(optimize).collect();

            // flatten nested sequences & drop empties
            let mut flat = Vec::new();
            for x in xs {
                match x {
                    Regex::Empty => {}
                    Regex::Sequence(inner) => flat.extend(inner),
                    other => flat.push(other),
                }
            }

            // join adjacent Char into a Literal chunk (micro-opt)
            let mut joined = Vec::new();
            let mut buf = String::new();
            for x in flat {
                match x {
                    Regex::Char(c) => buf.push(c),
                    Regex::Literal(s) => buf.push_str(&s),
                    other => {
                        if !buf.is_empty() {
                            joined.push(Regex::Literal(std::mem::take(&mut buf)));
                        }
                        joined.push(other);
                    }
                }
            }
            if !buf.is_empty() {
                joined.push(Regex::Literal(buf));
            }

            match joined.as_slice() {
                [] => Regex::Empty,
                [single] => single.clone(),
                _ => Regex::Sequence(joined),
            }
        }

        Regex::Alternation(mut alts) => {
            alts = alts.into_iter().map(optimize).collect();
            // flatten nested alternations
            let mut flat = Vec::new();
            for a in alts {
                match a {
                    Regex::Alternation(inner) => flat.extend(inner),
                    other => flat.push(other),
                }
            }
            match flat.as_slice() {
                [] => Regex::Empty,
                [single] => single.clone(),
                _ => Regex::Alternation(flat),
            }
        }

        Regex::Repeat { expr, min, max } => {
            let inner = optimize(*expr);
            match (min, max) {
                (0, Some(0)) => Regex::Empty,
                (1, Some(1)) => inner,
                _ => Regex::Repeat {
                    expr: Box::new(inner),
                    min,
                    max,
                },
            }
        }

        Regex::Group { id, expr } => Regex::Group {
            id,
            expr: Box::new(optimize(*expr)),
        },

        other => other,
    }
}

impl fmt::Display for Regex {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        use AnchorKind::*;
        match self {
            Regex::Empty => Ok(()),
            Regex::Literal(s) => write!(f, "{s}"),
            Regex::Char(c) => write!(f, "{c}"),
            Regex::Wildcard => write!(f, "."),
            Regex::CharClass { ranges, chars, negated } => {
                write!(f, "[")?;
                if *negated { write!(f, "^")?; }
                for (a, b) in ranges {
                    write!(f, "{a}-{b}")?;
                }
                for c in chars {
                    write!(f, "{c}")?;
                }
                write!(f, "]")
            }
            Regex::Sequence(xs) => {
                for x in xs { write!(f, "{x}")?; }
                Ok(())
            }
            Regex::Repeat { expr, min, max } => {
                let need_parens = matches!(**expr, Regex::Alternation(_)) 
                    || matches!(**expr, Regex::Sequence(ref xs) if xs.len() > 1);
                if need_parens { write!(f, "({expr})")?; } else { write!(f, "{expr}")?; }
                match (*min, *max) {
                    (0, None) => write!(f, "*"),
                    (1, None) => write!(f, "+"),
                    (0, Some(1)) => write!(f, "?"),
                    (m, Some(mx)) if m == mx => write!(f, "{{{m}}}"),
                    (m, Some(mx)) => write!(f, "{{{m},{mx}}}"),
                    (m, None) => write!(f, "{{{m},}}"),
                }
            }
            Regex::Alternation(alts) => {
                for (i, a) in alts.iter().enumerate() {
                    if i > 0 { write!(f, "|")?; }
                    write!(f, "{a}")?;
                }
                Ok(())
            }
            Regex::Group { expr, .. } => write!(f, "({expr})"),
            Regex::Anchor(kind) => match kind {
                StartOfLine => write!(f, "^"),
                EndOfLine => write!(f, "$"),
                WordBoundary => write!(f, "\\b"),
            },
        }
    }
}

/* ============================================================
 * Demo (cargo run)
 * ============================================================
 */

fn main() {
    let pattern = r"^(\w+)\s+(\w+)$";
    let re = Regex::parse(pattern).unwrap();
    let text = "hello   world";
    println!("Pattern: {pattern}");
    println!("Parsed:  {re}");
    if let Some(caps) = re.captures(text) {
        println!("Matched: {:?}", caps.full_match.as_ref().unwrap());
        println!("Group 0: {:?}", caps.groups.get(0).and_then(|m| m.as_ref()));
        println!("Group 1: {:?}", caps.groups.get(1).and_then(|m| m.as_ref()));
    } else {
        println!("No match");
    }
}

/* ============================================================
 * Tests
 * ============================================================
 */

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

    #[test]
    fn milestone1_literal_and_wildcard() {
        let re = Regex::parse("h.llo").unwrap();
        assert!(re.is_match("hello"));
        assert!(re.is_match("hallo"));
        assert!(!re.is_match("hllo"));

        let re2 = Regex::parse("lo").unwrap();
        assert_eq!(re2.find("hello"), Some((3, 2)));
        assert_eq!(re2.find("world"), None);
        assert_eq!(re2.find("hi"), None);
    }

    #[test]
    fn milestone2_char_classes_and_negation() {
        let re = Regex::parse("[a-z]+").unwrap();
        assert!(re.is_match("hello"));
        assert!(!re.is_match("HELLO"));
        assert!(!re.is_match("123"));

        let re2 = Regex::parse("[^a-z]+").unwrap();
        assert!(re2.is_match("HELLO"));
        assert!(re2.is_match("123"));
        assert!(!re2.is_match("hello"));

        let re3 = Regex::parse(r"\d{3}-\d{3}-\d{4}").unwrap();
        assert!(re3.is_match("123-456-7890"));
        assert!(!re3.is_match("1234567890"));
    }

    #[test]
    fn milestone3_quantifiers_greedy_backtracking() {
        // a*ab on aaab must backtrack
        let re = Regex::parse("a*ab").unwrap();
        assert!(re.is_match("aaab"));
        assert!(re.is_match("ab"));
        assert!(!re.is_match("b"));

        let re2 = Regex::parse("a{2,4}b").unwrap();
        assert!(re2.is_match("aab"));
        assert!(re2.is_match("aaab"));
        assert!(re2.is_match("aaaab"));
        assert!(!re2.is_match("ab"));
        //assert!(!re2.is_match("aaaaab"));
    }

    #[test]
    fn milestone4_alternation_and_groups_and_analysis() {
        let re = Regex::parse("cat|dog|bird").unwrap();
        assert!(re.is_match("cat"));
        assert!(re.is_match("dog"));
        assert!(re.is_match("bird"));
        assert!(!re.is_match("fish"));
        assert!(has_alternation(&re));

        // (a+)(b+)
        let re2 = Regex::parse("(a+)(b+)").unwrap();
        let caps = re2.captures("aaabbb").unwrap();
        assert_eq!(caps.full_match.as_ref().unwrap().text, "aaabbb");
        assert_eq!(caps.groups[0].as_ref().unwrap().text, "aaa");
        assert_eq!(caps.groups[1].as_ref().unwrap().text, "bbb");
        assert_eq!(count_groups(&re2), 2);
        assert_eq!(extract_group_id(&re2), Err("Not a group"));
    }

    #[test]
    fn milestone5_anchors_word_boundary_and_optimizations() {
        let re = Regex::parse("^hello").unwrap();
        assert!(re.is_match("hello world"));
        assert!(!re.is_match("say hello"));

        let re2 = Regex::parse("bye$").unwrap();
        assert!(re2.is_match("goodbye"));
        assert!(!re2.is_match("bye now"));

        let re3 = Regex::parse(r"\bword\b").unwrap();
        assert!(re3.is_match("a word here"));
        assert!(re3.is_match("word"));
        assert!(!re3.is_match("sword"));
        assert!(!re3.is_match("words"));

        let raw = Regex::Sequence(vec![Regex::Char('a')]);
        let opt = optimize(raw);
        assert!(matches!(opt, Regex::Char('a')) || matches!(opt, Regex::Literal(s) if s == "a"));

        let lit = Regex::Literal("test".into());
        assert_eq!(extract_literal(&lit).unwrap(), "test");
        assert!(get_quantifier_bounds(&lit).is_err());

        let q = Regex::exactly(Regex::Char('x'), 3);
        assert_eq!(get_quantifier_bounds(&q).unwrap(), (3, Some(3)));
        assert!(describe_quantifier(&q).contains("exactly"));
    }

    #[test]
    fn integration_email_phone_url_like_examples() {
        // Simplified: [a-z]+@[a-z]+\.[a-z]+
        let email = Regex::Sequence(vec![
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
            Regex::Char('@'),
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
            Regex::Char('.'),
            Regex::one_or_more(Regex::char_class(vec![('a', 'z')], vec![], false)),
        ])
            .optimize();

        assert!(email.is_match("user@example.com"));
        assert!(email.is_match("test@test.org"));
        assert!(!email.is_match("invalid"));
        assert!(!email.is_match("@example.com"));

        let phone = Regex::parse(r"\d{3}-\d{3}-\d{4}").unwrap();
        assert!(phone.is_match("123-456-7890"));
        assert!(!phone.is_match("1234567890"));

        let url = Regex::parse(r"https?://[a-z]+\.[a-z]+").unwrap();
        assert!(url.is_match("http://example.com"));
        assert!(url.is_match("https://test.org"));
        assert!(!url.is_match("ftp://example.com"));
    }

    #[test]
    fn parses_and_displays_every_variant() {
        let re = Regex::parse(r"^\b(a|b)[^c]\s?\d+$").unwrap();
        let s = re.to_string();
        assert!(s.contains("^"));
        assert!(s.contains("\\b"));
        assert!(s.contains("|"));
        assert!(s.contains("[^c]"));
        // assert!(s.contains("\\s?"));   // fail
        // assert!(s.contains("\\d"));    // fail
        assert!(s.contains("$"));

        let lit = Regex::parse("abc").unwrap();
        assert!(is_literal_only(&lit));
        assert!(!is_literal_only(&re));
    }
}