rexile 0.5.7

//! # ReXile 🦎
//!
//! **A blazing-fast regex engine with 10-100x faster compilation speed**
//!
//! ReXile is a lightweight regex alternative optimized for fast compilation while maintaining
//! competitive matching performance.

#![allow(dead_code)]
#![allow(clippy::clone_on_copy)]
#![allow(clippy::match_like_matches_macro)]
#![allow(clippy::type_complexity)]
#![allow(clippy::upper_case_acronyms)]
#![allow(clippy::redundant_closure)]
#![allow(clippy::len_without_is_empty)]
#![allow(clippy::too_many_arguments)]
#![allow(clippy::comparison_chain)]
#![allow(clippy::manual_range_contains)]
#![allow(clippy::large_enum_variant)]
#![allow(clippy::manual_strip)]
#![allow(clippy::needless_range_loop)]
#![allow(clippy::string_slice)]
#![allow(clippy::needless_late_init)]
#![allow(clippy::manual_is_ascii_check)]
#![allow(clippy::sliced_string_as_bytes)]
//!
//! ## Quick Start
//!
//! ```rust
//! use rexile::Pattern;
//!
//! // Literal matching with SIMD acceleration
//! let pattern = Pattern::new("hello").unwrap();
//! assert!(pattern.is_match("hello world"));
//!
//! // Digit matching (1.4-1.9x faster than regex!)
//! let digits = Pattern::new(r"\d+").unwrap();
//! let matches = digits.find_all("Order #12345 costs $67.89");
//! assert_eq!(matches, vec![(7, 12), (20, 22), (23, 25)]);
//!
//! // Dot wildcard with backtracking
//! let quoted = Pattern::new(r#""[^"]+""#).unwrap();
//! assert!(quoted.is_match(r#"say "hello world""#));
//! ```
//!
//! ## Performance Highlights
//!
//! **Compilation Speed** (vs regex crate):
//! **Compilation Speed** (vs regex crate):
//! - Pattern `[a-zA-Z_]\w*`: **104.7x faster** compilation
//! - Pattern `\d+`: **46.5x faster** compilation
//! - Average: **10-100x faster compilation**
//!
//! **Memory Usage**:
//! - Compilation: **15x less memory** (128 KB vs 1920 KB)
//! - Compilation time: **10-100x faster** on average
//! - Peak memory: **5x less** in stress tests
//!
//! ## Fast Path Optimizations
//!
//! ReXile uses **10 specialized fast paths** for common patterns:
//!
//! | Pattern | Fast Path | Performance |
//! |---------|-----------|-------------|
//! | `\d+` | DigitRun | 1.4-1.9x faster |
//! | `"[^"]+"` | QuotedString | 2.44x faster |
//! | `[a-zA-Z_]\w*` | IdentifierRun | 104.7x faster compilation |
//! | `\w+` | WordRun | Competitive |
//! | `foo\|bar\|baz` | Alternation (aho-corasick) | 2x slower (acceptable) |
//!
//! ## Supported Features
//!
//! - ✅ Literal searches with SIMD acceleration
//! - ✅ Multi-pattern matching (alternations)
//! - ✅ Character classes with negation (`[a-z]`, `[^abc]`)
//! - ✅ Quantifiers (`*`, `+`, `?`, `{n}`, `{n,m}`)
//! - ✅ Range quantifiers (`{n}`, `{n,}`, `{n,m}`)
//! - ✅ Case-insensitive flag (`(?i)`)
//! - ✅ Escape sequences (`\d`, `\w`, `\s`, etc.)
//! - ✅ Sequences and groups
//! - ✅ Word boundaries (`\b`, `\B`)
//! - ✅ Anchoring (`^`, `$`)
//!
//! ## Use Cases
//!
//! ReXile is production-ready for:
//!
//! - ✅ **Parsers & lexers** - 10-100x faster compilation, instant startup
//! - ✅ **Rule engines** - Original use case (GRL parsing)
//! - ✅ **Log processing** - Fast keyword extraction
//! - ✅ **Dynamic patterns** - Applications that compile patterns at runtime
//! - ✅ **Memory-constrained environments** - 15x less compilation memory
//! - ✅ **Low-latency applications** - Predictable performance
//!
//! ## Cached API
//!
//! For patterns used repeatedly in hot loops:
//!
//! ```rust
//! use rexile;
//!
//! // Automatically cached - compile once, reuse forever
//! assert!(rexile::is_match("test", "this is a test").unwrap());
//! assert_eq!(rexile::find("world", "hello world").unwrap(), Some((6, 11)));
//! ```
//!
//! ## Architecture
//!
//! ```text
//! Pattern → Parser → AST → Fast Path Detection → Specialized Matcher
//!                                                        ↓
//!                                     DigitRun (memchr SIMD)
//!                                     IdentifierRun (direct bytes)
//!                                     QuotedString (memchr + validation)
//!                                     Alternation (aho-corasick)
//!                                     ... 6 more fast paths
//! ```
//!
//! **Dependencies:** Only `memchr` and `aho-corasick` for SIMD primitives
//!
//! ## When to Use ReXile vs regex
//!
//! **Choose ReXile for:**
//! - Digit extraction (`\d+`) - 3.57x faster
//! - Quoted strings (`"[^"]+"`) - 2.44x faster
//! - Identifiers (`[a-zA-Z_]\w*`) - Much faster
//! - Dynamic pattern compilation - 21x faster
//! - Memory-constrained environments - 15x less memory
//!
//! **Choose regex crate for:**
//! - Complex alternations (ReXile 2x slower)
//! - Unicode properties (`\p{L}` - not yet supported)
//! - Advanced features (lookahead, backreferences - not yet supported)
//!
//! ## License
//!
//! Licensed under either of MIT or Apache-2.0 at your option.

// Module organization
mod advanced; // Advanced features: captures, lookaround
mod engine; // Matching engines: NFA, DFA, Lazy DFA
pub mod optimization; // Fast paths and optimizations
mod parser; // Pattern parsing: escape, charclass, quantifier, etc.

// External dependencies
use aho_corasick::AhoCorasick;
use memchr::memmem;
use std::collections::HashMap;
use std::sync::{Mutex, OnceLock};

// Internal imports using new module structure
use advanced::{Lookaround, LookaroundType};
use engine::DFA;
use parser::{
    is_sequence_pattern, parse_escape, parse_quantified_pattern, parse_sequence,
    starts_with_escape, BoundaryType, CharClass, Flags, Group, QuantifiedPattern, Sequence,
};

// Re-export public types
pub use advanced::{CaptureGroup, Captures};
pub use optimization::{literal, prefilter};

/// Main ReXile pattern type
#[derive(Debug, Clone)]
pub struct Pattern {
    matcher: Matcher,
    prefilter: Option<(
        optimization::prefilter::Prefilter,
        optimization::literal::LiteralKind,
    )>,
    fast_path: Option<optimization::fast_path::FastPath>, // JIT-style fast path
    #[allow(dead_code)]
    flags: Flags,                  // Regex flags: (?i), (?m), (?s)
}

/// Type alias for convenience
pub type ReXile = Pattern;

// Helper functions for safe Unicode string slicing
#[inline]
fn safe_slice(text: &str, start: usize) -> Option<&str> {
    text.get(start..)
}

#[inline]
fn safe_slice_range(text: &str, start: usize, end: usize) -> Option<&str> {
    text.get(start..end)
}

/// Get all valid char boundary positions in a string slice from start_pos to end
#[inline]
#[allow(dead_code)]
fn char_boundaries(text: &str, start_pos: usize) -> impl Iterator<Item = usize> + '_ {
    (start_pos..=text.len()).filter(|&i| text.is_char_boundary(i))
}

impl Pattern {
    pub fn new(pattern: &str) -> Result<Self, PatternError> {
        // Parse inline flags like (?i), (?m), (?s) at the start of the pattern
        let (flags, effective_pattern) =
            if let Some((parsed_flags, rest)) = Flags::parse_from_pattern(pattern) {
                (parsed_flags, rest)
            } else {
                (Flags::new(), pattern)
            };

        // Check for anchors
        let has_start_anchor = effective_pattern.starts_with('^');
        let has_end_anchor =
            effective_pattern.ends_with('$') && !effective_pattern.ends_with("\\$");

        // Strip anchors to get inner pattern
        let inner_pattern = {
            let mut p = effective_pattern;
            if has_start_anchor {
                p = p.strip_prefix('^').unwrap_or(p);
            }
            if has_end_anchor {
                p = p.strip_suffix('$').unwrap_or(p);
            }
            p
        };

        // Check for capture groups, but exclude special patterns like (?:...), (?=...), (?!...), etc.
        let has_captures = inner_pattern.contains('(')
            && !inner_pattern.contains("(?:")
            && !inner_pattern.contains("(?=")
            && !inner_pattern.contains("(?!")
            && !inner_pattern.contains("(?<=")
            && !inner_pattern.contains("(?<!");

        // Parse the inner pattern (without anchors)
        let inner_ast = if has_captures {
            parse_pattern_with_captures_with_flags(inner_pattern, &flags)?
        } else {
            parse_pattern_with_flags(inner_pattern, &flags)?
        };

        // Wrap with anchor constraints if needed
        let ast = if has_start_anchor || has_end_anchor {
            Ast::AnchoredPattern {
                inner: Box::new(inner_ast),
                start: has_start_anchor,
                end: has_end_anchor,
            }
        } else {
            inner_ast
        };
        let mut matcher = compile_ast(&ast)?;

        // Apply flags to matcher (avoid double-wrapping if AST already wrapped)
        if flags.case_insensitive && !matches!(matcher, Matcher::CaseInsensitive(_)) {
            matcher = Matcher::CaseInsensitive(Box::new(matcher));
        }

        // Try to detect fast path first (JIT-style optimization)
        // Note: fast path supports case_insensitive flag but not multiline/dot_matches_newline
        // Skip fast-path only if multiline or dot_matches_newline flags are set
        let fast_path = if flags.multiline || flags.dot_matches_newline {
            None
        } else {
            // First check if we can compile a CaptureDFA for patterns with captures
            if let Matcher::PatternWithCaptures { ref elements, .. } = matcher {
                // Try to compile DFA
                if let Some(dfa) = engine::capture_dfa::compile_capture_pattern(elements) {
                    // Successfully compiled DFA - use it as fast path
                    Some(optimization::fast_path::FastPath::CaptureDFA(
                        std::sync::Arc::new(dfa),
                    ))
                } else {
                    // DFA compilation failed - fall back to normal fast path detection
                    let fast_path_pattern = if flags.case_insensitive {
                        pattern
                    } else {
                        effective_pattern
                    };
                    optimization::fast_path::detect_fast_path(fast_path_pattern)
                }
            } else {
                // Not a capture pattern - use normal fast path detection
                let fast_path_pattern = if flags.case_insensitive {
                    pattern
                } else {
                    effective_pattern
                };
                optimization::fast_path::detect_fast_path(fast_path_pattern)
            }
        };

        // Extract literals and create prefilter
        let literals = optimization::literal::extract_from_pattern(effective_pattern);

        // Only use prefilter for Prefix literals and patterns without groups
        // Groups can cause incorrect literal extraction that breaks leftmost-first semantics
        // Inner literals require expensive bounded verification
        // Also disable prefilter when multiline or dot_matches_newline flags are set
        // (case_insensitive is OK for prefilter)
        let has_groups = effective_pattern.contains("(?:")
            || (effective_pattern.contains('(') && !effective_pattern.contains("(?"));
        let prefilter = if !literals.is_empty()
            && literals.kind == optimization::literal::LiteralKind::Prefix
            && !has_groups
            && !flags.multiline
            && !flags.dot_matches_newline
        {
            let pf = optimization::prefilter::Prefilter::from_literals(&literals);
            if pf.is_available() {
                Some((pf, literals.kind))
            } else {
                None
            }
        } else {
            None
        };

        Ok(Pattern {
            matcher,
            prefilter,
            fast_path,
            flags,
        })
    }

    pub fn is_match(&self, text: &str) -> bool {
        // Fast path for common patterns (JIT-style)
        if let Some(ref fp) = self.fast_path {
            return fp.find(text).is_some();
        }

        // Use prefilter if available for faster scanning
        if let Some((ref prefilter, literal_kind)) = self.prefilter {
            return self.is_match_with_prefilter(text, prefilter, literal_kind);
        }

        // No prefilter: use matcher's is_match directly
        self.matcher.is_match(text)
    }

    /// Match with prefilter using bounded verification strategy
    fn is_match_with_prefilter(
        &self,
        text: &str,
        prefilter: &prefilter::Prefilter,
        literal_kind: literal::LiteralKind,
    ) -> bool {
        let bytes = text.as_bytes();

        // Determine lookback window based on literal kind
        let max_lookback = match literal_kind {
            literal::LiteralKind::Prefix => 10, // Prefix: small window (e.g., https?)
            literal::LiteralKind::Inner => 30,  // Inner: medium window (e.g., \w+@)
            literal::LiteralKind::Suffix => 50, // Suffix: larger window
            literal::LiteralKind::None => return self.matcher.is_match(text),
        };

        for candidate_pos in prefilter.candidates(bytes) {
            let lookback = candidate_pos.min(max_lookback);

            for offset in 0..=lookback {
                let start_pos = candidate_pos - offset;
                if self
                    .matcher
                    .is_match(safe_slice(text, start_pos).unwrap_or(""))
                {
                    return true;
                }
            }
        }

        false
    }

    pub fn find(&self, text: &str) -> Option<(usize, usize)> {
        // Fast path for common patterns (JIT-style)
        if let Some(ref fp) = self.fast_path {
            return fp.find(text);
        }

        // Use prefilter if available for faster scanning
        if let Some((ref prefilter, literal_kind)) = self.prefilter {
            return self.find_with_prefilter(text, prefilter, literal_kind);
        }

        // No prefilter: use matcher's find directly
        self.matcher.find(text)
    }

    /// Find with prefilter using bounded verification strategy
    fn find_with_prefilter(
        &self,
        text: &str,
        prefilter: &prefilter::Prefilter,
        literal_kind: literal::LiteralKind,
    ) -> Option<(usize, usize)> {
        let bytes = text.as_bytes();
        let mut earliest_match: Option<(usize, usize)> = None;

        // Determine lookback window based on literal kind
        let max_lookback = match literal_kind {
            literal::LiteralKind::Prefix => 10,
            literal::LiteralKind::Inner => 30,
            literal::LiteralKind::Suffix => 50,
            literal::LiteralKind::None => return self.matcher.find(text),
        };

        // For each candidate position found by prefilter
        for candidate_pos in prefilter.candidates(bytes) {
            // If we already found a match before this candidate, return it
            if let Some((start, _)) = earliest_match {
                if start < candidate_pos {
                    return earliest_match;
                }
            }

            let lookback = candidate_pos.min(max_lookback);

            for offset in 0..=lookback {
                let start_pos = candidate_pos - offset;

                // Try to find match from this position
                if let Some((match_start, match_end)) =
                    self.matcher.find(safe_slice(text, start_pos).unwrap_or(""))
                {
                    let abs_start = start_pos + match_start;
                    let abs_end = start_pos + match_end;

                    // Update earliest match if this is earlier
                    if earliest_match.is_none() || abs_start < earliest_match.unwrap().0 {
                        earliest_match = Some((abs_start, abs_end));
                    }
                    break;
                }
            }
        }

        earliest_match
    }

    pub fn find_all(&self, text: &str) -> Vec<(usize, usize)> {
        // Fast path for common patterns (JIT-style)
        if let Some(ref fp) = self.fast_path {
            return fp.find_all(text);
        }

        // OPTIMIZED: Fast path for Literal using memchr's find_iter
        match &self.matcher {
            Matcher::Literal(lit) => {
                // Use memmem::find_iter for direct SIMD iteration
                memmem::find_iter(text.as_bytes(), lit.as_bytes())
                    .map(|pos| (pos, pos + lit.len()))
                    .collect()
            }
            Matcher::MultiLiteral(ac) => {
                // AhoCorasick already has find_iter
                ac.find_iter(text)
                    .map(|mat| (mat.start(), mat.end()))
                    .collect()
            }
            Matcher::Sequence(seq) => {
                // OPTIMIZED: Use specialized sequence iterator with cached Finder
                seq.find_all(text)
            }
            Matcher::Quantified(qp) => qp.find_all(text),
            Matcher::AnchoredLiteral { .. }
            | Matcher::AnchoredGroup { .. }
            | Matcher::AnchoredPattern { .. } => self.matcher.find_all(text),
            _ => {
                // Complex patterns: use general iterator
                self.find_iter(text).map(|m| (m.start(), m.end())).collect()
            }
        }
    }

    /// Create an iterator over all matches
    pub fn find_iter<'a>(&'a self, text: &'a str) -> FindIter<'a> {
        FindIter {
            matcher: &self.matcher,
            fast_path: &self.fast_path,
            text,
            pos: 0,
        }
    }

    /// Capture groups from the first match
    ///
    /// Returns a `Captures` object if the pattern matches, containing the full match
    /// and any captured groups. Returns None if no match is found.
    ///
    /// # Example
    /// ```
    /// use rexile::Pattern;
    ///
    /// let pattern = Pattern::new(r"(\w+)@(\w+)\.(\w+)").unwrap();
    /// if let Some(caps) = pattern.captures("email: test@example.com") {
    ///     println!("Full: {}", &caps[0]);    // test@example.com
    ///     println!("User: {}", &caps[1]);    // test
    ///     println!("Domain: {}", &caps[2]);  // example
    ///     println!("TLD: {}", &caps[3]);     // com
    /// }
    /// ```
    pub fn captures<'t>(&self, text: &'t str) -> Option<Captures<'t>> {
        // Check if this is a PatternWithCaptures matcher
        if let Matcher::PatternWithCaptures {
            elements,
            total_groups,
        } = &self.matcher
        {
            // Try matching with backtracking at any position
            for start_pos in 0..=text.len() {
                if let Some((end_pos, capture_list)) =
                    Matcher::match_elements_with_backtrack_and_captures(text, start_pos, elements)
                {
                    if end_pos > start_pos || elements.is_empty() {
                        // Create Captures with full match and capture groups
                        let mut caps = Captures::new(text, (start_pos, end_pos), *total_groups);

                        // Add each capture group
                        for (group_num, cap_start, cap_end) in capture_list {
                            caps.set(group_num, cap_start, cap_end);
                        }

                        return Some(caps);
                    }
                }
            }
            None
        } else if let Matcher::Capture(inner_matcher, group_index) = &self.matcher {
            // Single capture group - get total groups from inner matcher
            let total_groups =
                if let Matcher::PatternWithCaptures { total_groups, .. } = **inner_matcher {
                    total_groups
                } else {
                    *group_index // If inner is not PatternWithCaptures, just use group_index
                };

            if let Some((start, end)) = inner_matcher.find(text) {
                let mut caps = Captures::new(text, (start, end), total_groups);

                // Record the main capture
                caps.set(*group_index, start, end);

                // Extract all nested captures recursively
                let nested = inner_matcher.extract_nested_captures(text, start);
                for (group_num, cap_start, cap_end) in nested {
                    caps.set(group_num, cap_start, cap_end);
                }

                Some(caps)
            } else {
                None
            }
        } else if let Matcher::AnchoredPattern { inner, start, end } = &self.matcher {
            // Handle anchored patterns with captures
            // Delegate to inner matcher's captures logic, but with anchor constraints
            if let Matcher::PatternWithCaptures {
                elements,
                total_groups,
            } = inner.as_ref()
            {
                // For anchored captures, we need to respect anchor constraints
                let check_anchor = |match_start: usize, match_end: usize| -> bool {
                    let start_ok = !*start || match_start == 0;
                    let end_ok = !*end || match_end == text.len();
                    start_ok && end_ok
                };

                // Try matching with backtracking at any position
                for start_pos in 0..=text.len() {
                    // For start anchor, only try position 0
                    if *start && start_pos != 0 {
                        continue;
                    }

                    if let Some((end_pos, capture_list)) =
                        Matcher::match_elements_with_backtrack_and_captures(
                            text, start_pos, elements,
                        )
                    {
                        if (end_pos > start_pos || elements.is_empty())
                            && check_anchor(start_pos, end_pos)
                        {
                            // Create Captures with full match and capture groups
                            let mut caps = Captures::new(text, (start_pos, end_pos), *total_groups);

                            // Add each capture group
                            for (group_num, cap_start, cap_end) in capture_list {
                                caps.set(group_num, cap_start, cap_end);
                            }

                            return Some(caps);
                        }
                    }
                }
                None
            } else {
                // Simple pattern without captures - just return full match with anchor check
                self.find(text).map(|(match_start, match_end)| {
                    Captures::new(text, (match_start, match_end), 0)
                })
            }
        } else {
            // Simple pattern without explicit captures - just return full match
            self.find(text)
                .map(|(start, end)| Captures::new(text, (start, end), 0))
        }
    }

    /// Iterate over all captures in the text
    ///
    /// Returns an iterator that yields `Captures` for each match found.
    ///
    /// # Example
    /// ```
    /// use rexile::Pattern;
    ///
    /// let pattern = Pattern::new(r"(\w+)=(\d+)").unwrap();
    /// for caps in pattern.captures_iter("a=1 b=2 c=3") {
    ///     println!("{} = {}", &caps[1], &caps[2]);
    /// }
    /// ```
    pub fn captures_iter<'r, 't>(&'r self, text: &'t str) -> CapturesIter<'r, 't> {
        CapturesIter {
            pattern: self,
            text,
            pos: 0,
        }
    }

    /// Replace the first match with a replacement string
    ///
    /// Supports capture group references using $1, $2, etc.
    ///
    /// # Example
    /// ```
    /// use rexile::Pattern;
    ///
    /// let pattern = Pattern::new(r"(\w+)").unwrap();
    /// let result = pattern.replace("hello world", "goodbye");
    /// assert_eq!(result, "goodbye world");
    ///
    /// // With captures
    /// let pattern = Pattern::new(r"(\w+)=(\d+)").unwrap();
    /// let result = pattern.replace("a=1 b=2", "$1:[$2]");
    /// assert_eq!(result, "a:[1] b=2");
    /// ```
    pub fn replace(&self, text: &str, replacement: &str) -> String {
        // Check if replacement contains capture references like $1, $2
        let has_captures = replacement.contains('$');

        if !has_captures {
            // Simple literal replacement (fast path)
            if let Some((start, end)) = self.find(text) {
                let mut result = String::new();
                result.push_str(&text[..start]);
                result.push_str(replacement);
                result.push_str(&text[end..]);
                result
            } else {
                // No match, return original text
                text.to_string()
            }
        } else {
            // Replacement with capture groups
            if let Some(caps) = self.captures(text) {
                let match_start = caps.pos(0).unwrap().0;
                let match_end = caps.pos(0).unwrap().1;

                let mut result = String::new();
                result.push_str(&text[..match_start]);

                // Process replacement string with $1, $2, etc.
                let mut chars = replacement.chars().peekable();
                while let Some(ch) = chars.next() {
                    if ch == '$' {
                        // Check if next char is a digit
                        if let Some(&next_ch) = chars.peek() {
                            if next_ch.is_ascii_digit() {
                                chars.next(); // consume the digit
                                let group_num = next_ch.to_digit(10).unwrap() as usize;

                                // Insert the captured group
                                if let Some(group_text) = caps.get(group_num) {
                                    result.push_str(group_text);
                                }
                            } else {
                                result.push('$');
                            }
                        } else {
                            result.push('$');
                        }
                    } else {
                        result.push(ch);
                    }
                }

                result.push_str(&text[match_end..]);
                result
            } else {
                // No match, return original text
                text.to_string()
            }
        }
    }

    /// Replace all matches with a replacement string
    ///
    /// Supports capture group references using $1, $2, etc.
    ///
    /// # Example
    /// ```
    /// use rexile::Pattern;
    ///
    /// let pattern = Pattern::new(r"(\w+)=(\d+)").unwrap();
    /// let result = pattern.replace_all("a=1 b=2", "$1:[$2]");
    /// assert_eq!(result, "a:[1] b:[2]");
    /// ```
    pub fn replace_all(&self, text: &str, replacement: &str) -> String {
        // Check if replacement contains capture references like $1, $2
        let has_captures = replacement.contains('$');

        if !has_captures {
            // Simple literal replacement (fast path)
            let mut result = String::new();
            let mut last_end = 0;

            for (start, end) in self.find_all(text) {
                result.push_str(&text[last_end..start]);
                result.push_str(replacement);
                last_end = end;
            }
            result.push_str(&text[last_end..]);
            return result;
        }

        // Replacement with capture groups
        let mut result = String::new();
        let mut last_end = 0;

        for caps in self.captures_iter(text) {
            let _full_match = caps.get(0).unwrap();
            let match_start = caps.pos(0).unwrap().0;
            let match_end = caps.pos(0).unwrap().1;

            // Add text before this match
            result.push_str(&text[last_end..match_start]);

            // Process replacement string with $1, $2, etc.
            let mut chars = replacement.chars().peekable();
            while let Some(ch) = chars.next() {
                if ch == '$' {
                    // Check if next char is a digit
                    if let Some(&next_ch) = chars.peek() {
                        if next_ch.is_ascii_digit() {
                            chars.next(); // consume the digit
                            let group_num = next_ch.to_digit(10).unwrap() as usize;

                            // Insert the captured group
                            if let Some(group_text) = caps.get(group_num) {
                                result.push_str(group_text);
                            }
                            // If group doesn't exist, just skip (don't insert anything)
                        } else {
                            // $ not followed by digit, insert literal $
                            result.push('$');
                        }
                    } else {
                        // $ at end of string
                        result.push('$');
                    }
                } else {
                    result.push(ch);
                }
            }

            last_end = match_end;
        }

        // Add remaining text
        result.push_str(&text[last_end..]);
        result
    }

    /// Split text by matches of this pattern
    ///
    /// # Example
    /// ```
    /// use rexile::Pattern;
    ///
    /// let pattern = Pattern::new(r"\s+").unwrap();
    /// let parts: Vec<_> = pattern.split("a  b   c").collect();
    /// assert_eq!(parts, vec!["a", "b", "c"]);
    /// ```
    pub fn split<'r, 't>(&'r self, text: &'t str) -> SplitIter<'r, 't> {
        SplitIter {
            pattern: self,
            text,
            pos: 0,
            finished: false,
        }
    }
}

/// A single match in the haystack.
///
/// This is similar to `regex::Match` and provides access to
/// the matched text and its position.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Match<'t> {
    text: &'t str,
    start: usize,
    end: usize,
}

impl<'t> Match<'t> {
    /// Create a new Match
    #[inline]
    pub fn new(text: &'t str, start: usize, end: usize) -> Self {
        Self { text, start, end }
    }

    /// Returns the starting byte offset of the match.
    #[inline]
    pub fn start(&self) -> usize {
        self.start
    }

    /// Returns the ending byte offset of the match.
    #[inline]
    pub fn end(&self) -> usize {
        self.end
    }

    /// Returns the matched text.
    #[inline]
    pub fn as_str(&self) -> &'t str {
        &self.text[self.start..self.end]
    }

    /// Returns the range of byte offsets spanned by this match.
    #[inline]
    pub fn range(&self) -> std::ops::Range<usize> {
        self.start..self.end
    }

    /// Returns the length of the match in bytes.
    #[inline]
    pub fn len(&self) -> usize {
        self.end - self.start
    }

    /// Returns true if this is an empty match.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.start == self.end
    }
}

/// Iterator over pattern matches
pub struct FindIter<'a> {
    matcher: &'a Matcher,
    fast_path: &'a Option<optimization::fast_path::FastPath>,
    text: &'a str,
    pos: usize,
}

impl<'a> Iterator for FindIter<'a> {
    type Item = Match<'a>;

    fn next(&mut self) -> Option<Self::Item> {
        // TRUE LAZY EVALUATION: Find one match at a time
        if self.pos >= self.text.len() {
            return None;
        }

        // Use fast path if available - find_at() finds ONE match from position
        if let Some(ref fast_path) = self.fast_path {
            if let Some((start, end)) = fast_path.find_at(self.text, self.pos) {
                // Move position past this match
                self.pos = end.max(self.pos + 1);
                return Some(Match::new(self.text, start, end));
            } else {
                // No more matches
                return None;
            }
        }

        // Fallback: normal matcher iteration
        let remaining = &self.text[self.pos..];
        if let Some((rel_start, rel_end)) = self.matcher.find(remaining) {
            let abs_start = self.pos + rel_start;
            let abs_end = self.pos + rel_end;

            // Move position past this match to avoid infinite loop
            self.pos = abs_end.max(self.pos + 1);

            Some(Match::new(self.text, abs_start, abs_end))
        } else {
            None
        }
    }
}

/// Iterator over captures for each match
pub struct CapturesIter<'r, 't> {
    pattern: &'r Pattern,
    text: &'t str,
    pos: usize,
}

impl<'r, 't> Iterator for CapturesIter<'r, 't> {
    type Item = Captures<'t>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.pos >= self.text.len() {
            return None;
        }

        // Check if this is a PatternWithCaptures matcher
        if let Matcher::PatternWithCaptures {
            elements,
            total_groups,
        } = &self.pattern.matcher
        {
            // Find next match starting from current position and extract capture positions
            let remaining = &self.text[self.pos..];

            // Iterate over char boundaries, not arbitrary byte positions
            let char_indices: Vec<usize> = remaining.char_indices().map(|(i, _)| i).collect();
            let search_positions: Vec<usize> = if char_indices.is_empty() {
                vec![0]
            } else {
                char_indices
                    .into_iter()
                    .chain(std::iter::once(remaining.len()))
                    .collect()
            };

            for &start_offset in &search_positions {
                if start_offset >= remaining.len() {
                    break;
                }

                let mut pos = start_offset;
                let mut capture_positions: Vec<(usize, usize)> = Vec::new();
                let mut all_matched = true;

                for element in elements {
                    let (matcher, group_num_opt) = match element {
                        CompiledCaptureElement::Capture(m, num) => (m, Some(*num)),
                        CompiledCaptureElement::NonCapture(m) => (m, None),
                    };

                    if let Some((rel_start, rel_end)) = matcher.find(&remaining[pos..]) {
                        if rel_start != 0 {
                            // Element must match at current position
                            all_matched = false;
                            break;
                        }

                        let abs_start = pos;
                        let abs_end = pos + rel_end;

                        // If this is a capture group, record its position
                        if let Some(group_num) = group_num_opt {
                            // Ensure we have enough space
                            while capture_positions.len() < group_num {
                                capture_positions.push((0, 0));
                            }
                            capture_positions[group_num - 1] = (abs_start, abs_end);
                        }

                        pos = abs_end;
                    } else {
                        all_matched = false;
                        break;
                    }
                }

                if all_matched {
                    // Convert relative positions to absolute positions
                    let abs_start = self.pos + start_offset;
                    let abs_end = self.pos + pos;

                    // Move position past this match
                    self.pos = abs_end.max(self.pos + 1);

                    // Create Captures with full match and capture groups
                    let mut caps = Captures::new(self.text, (abs_start, abs_end), *total_groups);

                    // Add each capture group using the set method
                    for (i, &(start, end)) in capture_positions.iter().enumerate() {
                        caps.set(i + 1, self.pos - pos + start, self.pos - pos + end);
                    }

                    return Some(caps);
                }
            }
            None
        } else {
            // Simple pattern without explicit captures
            let remaining = &self.text[self.pos..];
            if let Some((rel_start, rel_end)) = self.pattern.matcher.find(remaining) {
                let abs_start = self.pos + rel_start;
                let abs_end = self.pos + rel_end;

                // Move position past this match
                self.pos = abs_end.max(self.pos + 1);

                // Create captures for this match
                Some(Captures::new(self.text, (abs_start, abs_end), 0))
            } else {
                None
            }
        }
    }
}

/// Iterator over text split by pattern matches
pub struct SplitIter<'r, 't> {
    pattern: &'r Pattern,
    text: &'t str,
    pos: usize,
    finished: bool,
}

impl<'r, 't> Iterator for SplitIter<'r, 't> {
    type Item = &'t str;

    fn next(&mut self) -> Option<Self::Item> {
        if self.finished {
            return None;
        }

        // Find next match starting from current position
        let remaining = &self.text[self.pos..];
        if let Some((rel_start, rel_end)) = self.pattern.matcher.find(remaining) {
            let abs_start = self.pos + rel_start;
            let abs_end = self.pos + rel_end;

            // Return text before the match
            let result = &self.text[self.pos..abs_start];
            self.pos = abs_end;

            Some(result)
        } else {
            // No more matches, return remaining text
            self.finished = true;
            Some(&self.text[self.pos..])
        }
    }
}

static CACHE: OnceLock<Mutex<HashMap<String, Pattern>>> = OnceLock::new();

fn get_cache() -> &'static Mutex<HashMap<String, Pattern>> {
    CACHE.get_or_init(|| Mutex::new(HashMap::new()))
}

pub fn get_pattern(pattern: &str) -> Result<Pattern, PatternError> {
    let mut cache = get_cache().lock().unwrap();
    if let Some(p) = cache.get(pattern) {
        return Ok(p.clone());
    }
    let compiled = Pattern::new(pattern)?;
    cache.insert(pattern.to_string(), compiled.clone());
    Ok(compiled)
}

pub fn is_match(pattern: &str, text: &str) -> Result<bool, PatternError> {
    Ok(get_pattern(pattern)?.is_match(text))
}

pub fn find(pattern: &str, text: &str) -> Result<Option<(usize, usize)>, PatternError> {
    Ok(get_pattern(pattern)?.find(text))
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum PatternError {
    ParseError(String),
    UnsupportedFeature(String),
}

impl std::fmt::Display for PatternError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            PatternError::ParseError(msg) => write!(f, "Parse error: {}", msg),
            PatternError::UnsupportedFeature(msg) => write!(f, "Unsupported: {}", msg),
        }
    }
}

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

#[derive(Debug, Clone, PartialEq)]
enum Ast {
    Literal(String),
    Dot,    // Matches any character except newline
    DotAll, // Matches any character INCLUDING newline (for (?s) flag)
    Alternation(Vec<String>),
    Anchored {
        literal: String,
        start: bool,
        end: bool,
    },
    AnchoredGroup {
        group: Group,
        start: bool,
        end: bool,
    },
    AnchoredPattern {
        inner: Box<Ast>,
        start: bool,
        end: bool,
    },
    CharClass(CharClass),
    Quantified(QuantifiedPattern),
    Sequence(Sequence),
    SequenceWithFlags(Sequence, Flags), // Sequence with flags applied
    Group(Group),
    Boundary(BoundaryType),   // Phase 6: Word boundary support
    Lookaround(Lookaround),   // Phase 7: Lookahead/lookbehind
    Capture(Box<Ast>, usize), // Phase 8: Capture group (pattern, group_index)
    QuantifiedCapture(Box<Ast>, parser::quantifier::Quantifier), // Capture with quantifier: (foo)+
    CombinedWithLookaround {
        prefix: Box<Ast>,
        lookaround: Lookaround,
    }, // Phase 7.2: foo(?=bar) - prefix with lookahead
    LookbehindWithSuffix {
        lookbehind: Lookaround,
        suffix: Box<Ast>,
    }, // Phase 7.3: (?<=foo)bar - lookbehind with suffix
    PatternWithCaptures {
        elements: Vec<CaptureElement>,
        total_groups: usize,
    }, // Phase 8.1: Hello (\w+)
    AlternationWithCaptures {
        branches: Vec<Ast>,
        total_groups: usize,
    }, // Alternation where branches may contain captures: (a)|(b) or (?:(a)|(b))
    Backreference(usize),     // Phase 9: Backreference to capture group (\1, \2, etc.)
    CaseInsensitive(Box<Ast>), // Wrap AST with case-insensitive matching
}

/// Parse patterns that contain groups combined with other elements
/// Handles: ^(hello), (foo)(bar), prefix(foo|bar), (foo|bar)suffix, (http|https)://
fn parse_pattern_with_groups(pattern: &str) -> Result<Ast, PatternError> {
    // Case 1: Multiple consecutive groups: (foo)(bar) - CHECK FIRST!
    if pattern.matches('(').count() > 1 && !pattern.contains('|') {
        let mut combined_literals = Vec::new();
        let mut pos = 0;
        let mut all_parsed = true;

        while pos < pattern.len() && pattern[pos..].starts_with('(') {
            match parser::group::parse_group(&pattern[pos..]) {
                Ok((group, bytes_consumed)) => {
                    // Extract literals from this group
                    match &group.content {
                        parser::group::GroupContent::Single(s) => {
                            combined_literals.push(s.clone());
                        }
                        parser::group::GroupContent::Sequence(seq) => {
                            // Try to extract literal from sequence of chars
                            let mut literal = String::new();
                            let mut is_simple = true;

                            for elem in &seq.elements {
                                match elem {
                                    crate::parser::sequence::SequenceElement::Char(ch) => {
                                        literal.push(*ch);
                                    }
                                    crate::parser::sequence::SequenceElement::Literal(lit) => {
                                        literal.push_str(lit);
                                    }
                                    _ => {
                                        // Not a simple literal sequence
                                        is_simple = false;
                                        break;
                                    }
                                }
                            }

                            if is_simple {
                                combined_literals.push(literal);
                            } else {
                                all_parsed = false;
                                break;
                            }
                        }
                        parser::group::GroupContent::Alternation(_)
                        | parser::group::GroupContent::ParsedAlternation(_) => {
                            // Can't easily combine alternations
                            all_parsed = false;
                            break;
                        }
                    }
                    pos += bytes_consumed;
                }
                Err(_) => {
                    all_parsed = false;
                    break;
                }
            }
        }

        if all_parsed && pos == pattern.len() && !combined_literals.is_empty() {
            // All groups parsed successfully - build as sequence
            // Create a sequence of literal elements for consecutive matching
            use crate::parser::sequence::{Sequence, SequenceElement};

            let mut elements = Vec::new();
            for literal in combined_literals {
                // Each literal becomes a sequence element
                elements.push(SequenceElement::Literal(literal));
            }

            let seq = Sequence::new(elements);
            return Ok(Ast::Sequence(seq));
        }
    }

    // Case 2: Anchor + Group: ^(hello) or (world)$
    if pattern.starts_with("^(") || pattern.ends_with(")$") {
        let has_start = pattern.starts_with('^');
        let has_end = pattern.ends_with('$');

        // Strip anchors properly - need to handle chaining correctly
        let mut inner = pattern;
        if has_start {
            inner = &inner[1..]; // Remove '^'
        }
        if has_end {
            inner = &inner[..inner.len() - 1]; // Remove '$'
        }

        if inner.starts_with('(') {
            if let Ok((group, bytes_consumed)) = parser::group::parse_group(inner) {
                if bytes_consumed == inner.len() {
                    // Extract the actual pattern from group for anchored matching
                    let group_literal = match &group.content {
                        parser::group::GroupContent::Single(s) => Some(s.clone()),
                        parser::group::GroupContent::Sequence(seq) => {
                            // Try to extract literal from sequence of chars
                            let mut literal = String::new();
                            let mut is_simple = true;

                            for elem in &seq.elements {
                                match elem {
                                    crate::parser::sequence::SequenceElement::Char(ch) => {
                                        literal.push(*ch);
                                    }
                                    crate::parser::sequence::SequenceElement::Literal(lit) => {
                                        literal.push_str(lit);
                                    }
                                    _ => {
                                        // Not a simple literal - can't anchor
                                        is_simple = false;
                                        break;
                                    }
                                }
                            }

                            if is_simple {
                                Some(literal)
                            } else {
                                None
                            }
                        }
                        parser::group::GroupContent::Alternation(_)
                        | parser::group::GroupContent::ParsedAlternation(_) => {
                            // For alternation like ^(foo|bar), can't use simple Anchored
                            None
                        }
                    };

                    if let Some(lit) = group_literal {
                        return Ok(Ast::Anchored {
                            literal: lit,
                            start: has_start,
                            end: has_end,
                        });
                    } else {
                        // Complex group - use AnchoredGroup
                        return Ok(Ast::AnchoredGroup {
                            group,
                            start: has_start,
                            end: has_end,
                        });
                    }
                }
            }
        }
    }

    // Case 3: Just a single group
    if pattern.starts_with('(') {
        if let Ok((group, bytes_consumed)) = parser::group::parse_group(pattern) {
            if bytes_consumed == pattern.len() {
                return Ok(Ast::Group(group));
            }

            // Case 4: Group with suffix: (foo|bar)suffix, (http|https)://
            if bytes_consumed < pattern.len() {
                let suffix = &pattern[bytes_consumed..];
                // Build a combined pattern
                // For alternation groups, expand: (a|b)c -> ac|bc
                match &group.content {
                    parser::group::GroupContent::Alternation(parts) => {
                        let expanded: Vec<String> =
                            parts.iter().map(|p| format!("{}{}", p, suffix)).collect();
                        return Ok(Ast::Alternation(expanded));
                    }
                    parser::group::GroupContent::Sequence(seq) => {
                        // Group with sequence + suffix: (\w+)@ or (\d+).
                        // Need to append suffix to the sequence
                        use crate::parser::sequence::{Sequence, SequenceElement};

                        let mut new_elements = seq.elements.clone();
                        // Add suffix as literal elements
                        for ch in suffix.chars() {
                            new_elements.push(SequenceElement::Char(ch));
                        }

                        let combined_seq = Sequence::new(new_elements);
                        return Ok(Ast::Sequence(combined_seq));
                    }
                    parser::group::GroupContent::Single(s) => {
                        // Simple literal + suffix
                        let combined = format!("{}{}", s, suffix);
                        return Ok(Ast::Literal(combined));
                    }
                    parser::group::GroupContent::ParsedAlternation(_) => {
                        // Complex alternation with suffix - fall through
                    }
                }
            }
        }
    }

    // Case 5: Prefix + Group: prefix(foo|bar) - but NOT ^(hello) or $(hello)
    if let Some(group_start) = pattern.find('(') {
        if group_start > 0 {
            let prefix = &pattern[..group_start];
            // Skip if prefix is just an anchor
            if prefix != "^" && prefix != "$" {
                let group_part = &pattern[group_start..];

                if let Ok((group, bytes_consumed)) = parser::group::parse_group(group_part) {
                    if bytes_consumed == group_part.len() {
                        // prefix + group
                        match &group.content {
                            parser::group::GroupContent::Alternation(parts) => {
                                let expanded: Vec<String> =
                                    parts.iter().map(|p| format!("{}{}", prefix, p)).collect();
                                return Ok(Ast::Alternation(expanded));
                            }
                            _ => {
                                // Single pattern with prefix
                                return Ok(Ast::Group(group));
                            }
                        }
                    }
                }
            }
        }
    }

    Err(PatternError::ParseError(
        "Complex group pattern not fully supported".to_string(),
    ))
}

fn parse_pattern(pattern: &str) -> Result<Ast, PatternError> {
    parse_pattern_with_depth(pattern, 0)
}

const MAX_RECURSION_DEPTH: usize = 100;

fn parse_pattern_with_depth(pattern: &str, depth: usize) -> Result<Ast, PatternError> {
    if depth > MAX_RECURSION_DEPTH {
        return Err(PatternError::ParseError(
            "Pattern too complex: recursion depth exceeded".to_string(),
        ));
    }

    if pattern.is_empty() {
        return Ok(Ast::Literal(String::new()));
    }

    // Phase 7: Check for lookaround assertions (?=...), (?!...), (?<=...), (?<!...)
    if pattern.starts_with("(?=")
        || pattern.starts_with("(?!")
        || pattern.starts_with("(?<=")
        || pattern.starts_with("(?<!")
    {
        return parse_lookaround(pattern, depth);
    }

    // Phase 7.2: Check for combined patterns with lookaround: foo(?=bar), \d+(?!x)
    if pattern.contains("(?=")
        || pattern.contains("(?!")
        || pattern.contains("(?<=")
        || pattern.contains("(?<!")
    {
        // Try to parse as combined pattern with lookaround
        if let Ok(ast) = parse_combined_with_lookaround(pattern, depth) {
            return Ok(ast);
        }
    }

    // Phase 8: Check for capture groups (...) - but not (?:...) which is handled by group parser
    // Simple heuristic: if starts with ( but not (? or (?:, might be capture group
    if pattern.starts_with('(') && !pattern.starts_with("(?") {
        // Check if this is a simple capture group pattern (no nested captures inside)
        if let Some(close_idx) = find_matching_paren(pattern, 0) {
            if close_idx == pattern.len() - 1 {
                // Entire pattern is a capture group: (pattern)
                let inner = &pattern[1..close_idx];

                // If inner contains captures, let parse_pattern_with_captures handle it
                if !contains_unescaped_paren(inner) || inner.starts_with("(?") {
                    // Simple capture with no nesting
                    let inner_ast = parse_pattern_with_depth(inner, depth + 1)?;
                    return Ok(Ast::Capture(Box::new(inner_ast), 1)); // Group 1
                }
                // Else: fall through to parse_pattern_with_captures below
            }
        }
    }

    // Phase 8.1: Check for patterns with embedded captures: Hello (\w+), (\w+)=(\d+)
    // Phase 8.2: Also handles non-capturing groups: (?:Hello) (\w+)
    // But skip patterns starting with anchors - they need special handling below
    // Also skip quantified groups like (test)?, (foo)+, (bar)* - they're handled as quantified patterns
    let is_quantified_group = pattern.starts_with('(')
        && if let Some(close_idx) = find_matching_paren(pattern, 0) {
            close_idx == pattern.len() - 2
                && (pattern.ends_with('?') || pattern.ends_with('*') || pattern.ends_with('+'))
        } else {
            false
        };

    let is_bounded_quantified_group = pattern.starts_with('(')
        && if let Some(close_idx) = find_matching_paren(pattern, 0) {
            close_idx < pattern.len() - 1 && pattern[close_idx + 1..].starts_with('{')
        } else {
            false
        };

    if contains_unescaped_paren(pattern)
        && !pattern.starts_with('^')
        && !pattern.ends_with('$')
        && !is_quantified_group
        && !is_bounded_quantified_group
        && !pattern.contains("(?=")
        && !pattern.contains("(?!")
        && !pattern.contains("(?<=")
        && !pattern.contains("(?<!")
    {
        // Try to parse as pattern with captures (including non-capturing groups)
        if let Ok(ast) = parse_pattern_with_captures(pattern) {
            return Ok(ast);
        }
    }

    // Special handling for patterns with groups and other elements
    // e.g., ^(hello), (foo)(bar), prefix(foo|bar), (foo|bar)suffix
    if contains_unescaped_paren(pattern) {
        // Try to parse as complex pattern with groups
        if let Ok(ast) = parse_pattern_with_groups(pattern) {
            return Ok(ast);
        }
    }

    // Check for anchors (before sequences)
    let has_start_anchor = pattern.starts_with('^');
    let has_end_anchor = pattern.ends_with('$');

    if has_start_anchor || has_end_anchor {
        // Strip anchors properly - don't fall back to original pattern
        let mut literal = pattern;
        if has_start_anchor {
            literal = literal.strip_prefix('^').unwrap();
        }
        if has_end_anchor {
            literal = literal.strip_suffix('$').unwrap();
        }

        // Don't treat anchored patterns as sequences
        return Ok(Ast::Anchored {
            literal: literal.to_string(),
            start: has_start_anchor,
            end: has_end_anchor,
        });
    }

    // Check for alternation (|)
    if pattern.contains('|') && !pattern.contains('[') {
        let parts: Vec<String> = pattern.split('|').map(|s| s.to_string()).collect();
        return Ok(Ast::Alternation(parts));
    }

    // Check for sequence pattern (most complex)
    if is_sequence_pattern(pattern) {
        match parse_sequence(pattern) {
            Ok(seq) => return Ok(Ast::Sequence(seq)),
            Err(_) => {
                // Fall through to other parsers
            }
        }
    }

    // Check for escape sequences: \d, \w, \s, \b, \B, \., etc.
    if starts_with_escape(pattern) {
        match parse_escape(pattern) {
            Ok((seq, bytes_consumed)) => {
                // If it's the whole pattern
                if bytes_consumed == pattern.len() {
                    // Check for boundary first (since it doesn't convert to CharClass)
                    if let Some(boundary_type) = seq.to_boundary() {
                        return Ok(Ast::Boundary(boundary_type));
                    }
                    // Convert to CharClass if possible
                    if let Some(cc) = seq.to_char_class() {
                        return Ok(Ast::CharClass(cc));
                    }
                    // Or to literal char
                    if let Some(ch) = seq.to_char() {
                        return Ok(Ast::Literal(ch.to_string()));
                    }
                }
                // Otherwise, check for quantifier after escape
                let remaining = &pattern[bytes_consumed..];
                if !remaining.is_empty() {
                    if let Some(q_char) = remaining.chars().next() {
                        if q_char == '*' || q_char == '+' || q_char == '?' || q_char == '{' {
                            // This is an escape with quantifier: \d+, \w*, \d{4}, etc.
                            if let Ok(qp) = parse_quantified_pattern(pattern) {
                                return Ok(Ast::Quantified(qp));
                            }
                        }
                    }
                }
            }
            Err(e) => return Err(PatternError::ParseError(e)),
        }
    }

    // Check for quantified patterns: a+, [0-9]*, \d+, etc.
    let has_quantifier = pattern.ends_with('*')
        || pattern.ends_with('+')
        || pattern.ends_with('?')
        || (pattern.contains('{') && pattern.ends_with('}'));

    if has_quantifier {
        // Try to parse as quantified pattern
        match parse_quantified_pattern(pattern) {
            Ok(qp) => return Ok(Ast::Quantified(qp)),
            Err(_) => {
                if pattern.contains('{') {
                    return Err(PatternError::ParseError("Invalid quantifier".to_string()));
                }
                // Fall through to other parsers for non-brace suffixes.
            }
        }
    }

    if pattern.contains('{') {
        return Err(PatternError::ParseError("Invalid quantifier".to_string()));
    }

    // Check for character class [...]
    if pattern.starts_with('[') && pattern.contains(']') {
        let end_idx = pattern.find(']').unwrap();
        if end_idx == pattern.len() - 1 {
            // Pure character class pattern: [a-z]
            let class_content = &pattern[1..end_idx];
            let char_class = CharClass::parse(class_content).map_err(PatternError::ParseError)?;
            return Ok(Ast::CharClass(char_class));
        }
        // Character class with quantifier is handled above
    } else if pattern.starts_with('[') {
        return Err(PatternError::ParseError(
            "Unclosed character class".to_string(),
        ));
    }

    // Check for single dot wildcard
    if pattern == "." {
        return Ok(Ast::Dot);
    }

    // Check if pattern contains dots - needs sequence parsing
    if pattern.contains('.') {
        // Pattern like "a.c" needs to be parsed as sequence with dot wildcard
        use crate::parser::sequence::{Sequence, SequenceElement};
        let mut elements = Vec::new();

        for ch in pattern.chars() {
            if ch == '.' {
                elements.push(SequenceElement::Dot);
            } else {
                elements.push(SequenceElement::Char(ch));
            }
        }

        return Ok(Ast::Sequence(Sequence::new(elements)));
    }

    // Default: treat as literal
    Ok(Ast::Literal(pattern.to_string()))
}

/// Parse pattern with flags applied
/// This handles (?i) case-insensitive, (?m) multiline, (?s) dotall flags
fn parse_pattern_with_flags(pattern: &str, flags: &Flags) -> Result<Ast, PatternError> {
    // If dotall flag is set, we need to handle . differently
    // If case_insensitive is set, wrap result in CaseInsensitive

    if flags.dot_matches_newline {
        // Parse the pattern with dot matching newlines
        let ast = parse_pattern_dotall(pattern, flags)?;
        if flags.case_insensitive {
            return Ok(Ast::CaseInsensitive(Box::new(ast)));
        }
        return Ok(ast);
    }

    // Parse normally
    let ast = parse_pattern(pattern)?;
    if flags.case_insensitive {
        return Ok(Ast::CaseInsensitive(Box::new(ast)));
    }
    Ok(ast)
}

/// Parse pattern with DOTALL mode: . matches newlines
fn parse_pattern_dotall(pattern: &str, flags: &Flags) -> Result<Ast, PatternError> {
    if pattern.is_empty() {
        return Ok(Ast::Literal(String::new()));
    }

    // Check for single dot wildcard
    if pattern == "." {
        return Ok(Ast::DotAll);
    }

    // Check if pattern contains dots - needs sequence parsing with DotAll
    if pattern.contains('.') {
        // Check if this is a sequence pattern
        if is_sequence_pattern(pattern) {
            // Parse the sequence and apply DOTALL flag
            match parse_sequence(pattern) {
                Ok(seq) => return Ok(Ast::SequenceWithFlags(seq, *flags)),
                Err(_) => {
                    // Fall through to other parsers
                }
            }
        }

        // Pattern like "a.c" needs to be parsed as sequence with dot wildcard
        use crate::parser::sequence::{Sequence, SequenceElement};
        let mut elements = Vec::new();

        for ch in pattern.chars() {
            if ch == '.' {
                // Use DotAll element (will be handled by SequenceWithFlags)
                elements.push(SequenceElement::Dot);
            } else {
                elements.push(SequenceElement::Char(ch));
            }
        }

        return Ok(Ast::SequenceWithFlags(Sequence::new(elements), *flags));
    }

    // For non-dot patterns, delegate to normal parsing
    parse_pattern(pattern)
}

/// Parse patterns with captures and flags
fn parse_pattern_with_captures_with_flags(
    pattern: &str,
    flags: &Flags,
) -> Result<Ast, PatternError> {
    // For now, parse normally and wrap if case-insensitive
    // TODO: proper flags handling for captures
    let ast = parse_pattern_with_captures(pattern)?;

    if flags.case_insensitive {
        return Ok(Ast::CaseInsensitive(Box::new(ast)));
    }

    // If DOTALL flag is set and the pattern has sequences, we need special handling
    // For now, return as-is - full support requires more work
    Ok(ast)
}

#[derive(Debug, Clone)]
enum Matcher {
    Literal(String),
    MultiLiteral(AhoCorasick),
    AnchoredLiteral {
        literal: String,
        start: bool,
        end: bool,
    },
    AnchoredGroup {
        group: Group,
        start: bool,
        end: bool,
    },
    AnchoredPattern {
        inner: Box<Matcher>,
        start: bool,
        end: bool,
    },
    CharClass(CharClass),
    Quantified(QuantifiedPattern),
    Sequence(Sequence),
    SequenceWithFlags(Sequence, Flags), // Sequence with flags (e.g., DOTALL)
    Group(Group),
    DigitRun,                                  // Specialized fast path for \d+ pattern
    WordRun,                                   // Specialized fast path for \w+ pattern
    Boundary(BoundaryType),                    // Phase 6: Word boundary matcher
    Lookaround(Box<Lookaround>, Box<Matcher>), // Phase 7: Lookaround with compiled inner matcher
    Capture(Box<Matcher>, usize), // Phase 8: Capture matcher (inner pattern, group_index)
    QuantifiedCapture(Box<Matcher>, parser::quantifier::Quantifier), // Quantified capture: (foo)+
    CombinedWithLookaround {
        prefix: Box<Matcher>,
        lookaround: Box<Lookaround>,
        lookaround_matcher: Box<Matcher>,
    }, // Phase 7.2: foo(?=bar) - prefix with lookahead
    LookbehindWithSuffix {
        lookbehind: Box<Lookaround>,
        lookbehind_matcher: Box<Matcher>,
        suffix: Box<Matcher>,
    }, // Phase 7.3: (?<=foo)bar - lookbehind with suffix
    PatternWithCaptures {
        elements: Vec<CompiledCaptureElement>,
        total_groups: usize,
    }, // Phase 8.1
    AlternationWithCaptures {
        branches: Vec<Matcher>,
        #[allow(dead_code)]
        total_groups: usize,
    }, // Alternation where branches may contain captures: (a)|(b) or (?:(a)|(b))
    Backreference(usize),         // Phase 9: Backreference to capture group
    DFA(DFA),                     // Phase 9.2: DFA-optimized sequence matcher
    LazyDFA(engine::lazy_dfa::LazyDFA), // Phase 9.3: Lazy DFA for complex patterns
    CaseInsensitive(Box<Matcher>), // Case-insensitive wrapper for (?i)
}

/// Compiled capture element
#[derive(Debug, Clone)]
enum CompiledCaptureElement {
    Capture(Matcher, usize), // Compiled matcher, group number
    NonCapture(Matcher),     // Compiled matcher (non-capturing)
}

impl Matcher {
    fn is_match(&self, text: &str) -> bool {
        match self {
            Matcher::Literal(lit) => memmem::find(text.as_bytes(), lit.as_bytes()).is_some(),
            Matcher::MultiLiteral(ac) => ac.is_match(text),
            Matcher::AnchoredLiteral {
                literal,
                start,
                end,
            } => match (start, end) {
                (true, true) => text == literal,
                (true, false) => text.starts_with(literal),
                (false, true) => text.ends_with(literal),
                _ => unreachable!(),
            },
            Matcher::AnchoredGroup { group, start, end } => {
                // Check if group matches with anchor constraints
                match (start, end) {
                    (true, true) => {
                        // Must match entire text
                        group
                            .match_at(text, 0)
                            .map(|len| len == text.len())
                            .unwrap_or(false)
                    }
                    (true, false) => {
                        // Must match at start
                        group.match_at(text, 0).is_some()
                    }
                    (false, true) => {
                        // Must match at end
                        if let Some((_start_pos, end_pos)) = group.find(text) {
                            end_pos == text.len()
                        } else {
                            false
                        }
                    }
                    _ => unreachable!(),
                }
            }
            Matcher::AnchoredPattern { inner, start, end } => {
                // Check if inner pattern matches with anchor constraints
                match (start, end) {
                    (true, true) => {
                        // Must match entire text
                        if let Some((match_start, match_end)) = inner.find(text) {
                            match_start == 0 && match_end == text.len()
                        } else {
                            false
                        }
                    }
                    (true, false) => {
                        // Must match at start
                        if let Some((match_start, _)) = inner.find(text) {
                            match_start == 0
                        } else {
                            false
                        }
                    }
                    (false, true) => {
                        // Must match at end
                        if let Some((_, match_end)) = inner.find(text) {
                            match_end == text.len()
                        } else {
                            false
                        }
                    }
                    _ => unreachable!(),
                }
            }
            Matcher::CharClass(cc) => {
                // OPTIMIZED: Use SIMD-friendly find_first for ASCII text
                cc.find_first(text).is_some()
            }
            Matcher::Quantified(qp) => {
                if let crate::parser::quantifier::QuantifiedElement::CharClass(cc) = &qp.element {
                    if let Some(bitmap) = cc.get_ascii_bitmap() {
                        let negated = cc.negated;
                        let min = qp.quantifier.min_matches();
                        let bytes = text.as_bytes();

                        if min <= 1 {
                            // For +, *, ?, {0,N}, {1,N} - just find one matching byte
                            for &byte in bytes {
                                if byte < 128 {
                                    let idx = byte as usize;
                                    let bit_set = (bitmap[idx / 64] & (1u64 << (idx % 64))) != 0;
                                    if bit_set != negated {
                                        return true;
                                    }
                                }
                            }
                            return false;
                        } else {
                            // For {N}, {N,}, {N,M} where N >= 2 - find N consecutive matching bytes
                            let mut run = 0usize;
                            for &byte in bytes {
                                if byte < 128 {
                                    let idx = byte as usize;
                                    let bit_set = (bitmap[idx / 64] & (1u64 << (idx % 64))) != 0;
                                    if bit_set != negated {
                                        run += 1;
                                        if run >= min {
                                            return true;
                                        }
                                        continue;
                                    }
                                }
                                run = 0;
                            }
                            return false;
                        }
                    }
                }
                qp.is_match(text)
            }
            Matcher::Sequence(seq) => seq.is_match(text), // NEW: Early termination
            Matcher::Group(group) => group.is_match(text), // NEW: Early termination
            Matcher::DigitRun => Self::digit_run_is_match(text), // NEW: Specialized digit fast path
            Matcher::WordRun => Self::word_run_is_match(text), // NEW: Specialized word fast path
            Matcher::Boundary(boundary_type) => boundary_type.find_first(text).is_some(),
            Matcher::Lookaround(lookaround, inner_matcher) => {
                // Lookaround assertions are zero-width, check if they match at any position
                for pos in 0..=text.len() {
                    if lookaround.matches_at(text, pos, inner_matcher) {
                        return true;
                    }
                }
                false
            }
            Matcher::Capture(inner_matcher, _group_index) => {
                // Capture groups don't affect matching, just check inner pattern
                inner_matcher.is_match(text)
            }
            Matcher::QuantifiedCapture(inner_matcher, quantifier) => {
                // Quantified capture - match inner pattern with quantifier semantics
                Self::quantified_is_match(text, inner_matcher, quantifier)
            }
            Matcher::CombinedWithLookaround {
                prefix,
                lookaround,
                lookaround_matcher,
            } => {
                // Need to find where prefix matches, then check lookaround at that position
                if let Some((_start, end)) = prefix.find(text) {
                    // Check if lookaround succeeds at the end position of the prefix match
                    lookaround.matches_at(text, end, lookaround_matcher)
                } else {
                    false
                }
            }
            Matcher::LookbehindWithSuffix {
                lookbehind,
                lookbehind_matcher,
                suffix,
            } => {
                // Match suffix anywhere in text, then check if lookbehind matches at that position
                // Try to find suffix match
                if let Some((start, _end)) = suffix.find(text) {
                    // Check if lookbehind succeeds at the start position of the suffix match
                    lookbehind.matches_at(text, start, lookbehind_matcher)
                } else {
                    false
                }
            }
            Matcher::PatternWithCaptures { .. } => {
                // OPTIMIZATION: Delegate to find() for simplicity
                self.find(text).is_some()
            }
            Matcher::Backreference(_) => {
                // Backreferences cannot be matched without context
                // They need access to captured groups, which is_match doesn't have
                // Return false - backreferences only work in captures() method
                false
            }
            Matcher::DFA(dfa) => {
                // DFA-optimized sequence matching
                dfa.is_match(text)
            }
            Matcher::LazyDFA(lazy_dfa) => {
                // Lazy DFA is mutable, clone for is_match
                let mut dfa = lazy_dfa.clone();
                dfa.find(text).is_some()
            }
            Matcher::SequenceWithFlags(seq, flags) => {
                // Sequence matching with flags (e.g., DOTALL)
                seq.is_match_with_flags(text, flags)
            }
            Matcher::AlternationWithCaptures { branches, .. } => {
                // Try each branch - return true if ANY branch matches
                for branch in branches {
                    if branch.is_match(text) {
                        return true;
                    }
                }
                false
            }
            Matcher::CaseInsensitive(inner) => {
                // Fast path: literal case-insensitive search without allocation
                // Only for ASCII needle + ASCII text (XOR trick only works for A-Z/a-z)
                if let Matcher::Literal(needle) = inner.as_ref() {
                    let needle_bytes = needle.as_bytes();
                    let text_bytes = text.as_bytes();
                    let needle_is_ascii = needle_bytes.iter().all(|&b| b < 128);
                    if needle_is_ascii
                        && !needle_bytes.is_empty()
                        && needle_bytes.len() <= text_bytes.len()
                    {
                        let first_lower = needle_bytes[0];
                        let first_upper = if first_lower >= b'a' && first_lower <= b'z' {
                            first_lower - 32
                        } else {
                            first_lower
                        };
                        for i in 0..=(text_bytes.len() - needle_bytes.len()) {
                            let b = text_bytes[i];
                            if b == first_lower || b == first_upper {
                                let mut matched = true;
                                for j in 1..needle_bytes.len() {
                                    let tb = text_bytes[i + j];
                                    let nb = needle_bytes[j];
                                    // Skip non-ASCII bytes in text
                                    if tb >= 128 || nb >= 128 {
                                        matched = false;
                                        break;
                                    }
                                    if tb != nb && (tb ^ 32) != nb {
                                        matched = false;
                                        break;
                                    }
                                }
                                if matched {
                                    return true;
                                }
                            }
                        }
                        return false;
                    }
                }
                // Fast path: alternation of literals
                if let Matcher::MultiLiteral(ac) = inner.as_ref() {
                    let bytes = text.as_bytes();
                    let len = bytes.len();
                    if len <= 256 {
                        let mut buf = [0u8; 256];
                        let mut all_ascii = true;
                        for i in 0..len {
                            let b = bytes[i];
                            if b >= 128 {
                                all_ascii = false;
                                break;
                            }
                            buf[i] = if b >= b'A' && b <= b'Z' { b + 32 } else { b };
                        }
                        if all_ascii {
                            let lower = unsafe { std::str::from_utf8_unchecked(&buf[..len]) };
                            return ac.is_match(lower);
                        }
                    }
                }
                // General case: lowercase text then match
                let bytes = text.as_bytes();
                let len = bytes.len();
                if len <= 256 {
                    let mut buf = [0u8; 256];
                    let mut all_ascii = true;
                    for i in 0..len {
                        let b = bytes[i];
                        if b >= 128 {
                            all_ascii = false;
                            break;
                        }
                        buf[i] = if b >= b'A' && b <= b'Z' { b + 32 } else { b };
                    }
                    if all_ascii {
                        let lower = unsafe { std::str::from_utf8_unchecked(&buf[..len]) };
                        return inner.is_match(lower);
                    }
                }
                let lower_text = text.to_lowercase();
                inner.is_match(&lower_text)
            }
        }
    }

    /// Recursively extract all nested captures from a matched pattern
    /// Returns Vec<(group_num, start, end)> for all capture groups found
    fn extract_nested_captures(&self, text: &str, start_pos: usize) -> Vec<(usize, usize, usize)> {
        let mut captures = Vec::new();

        match self {
            Matcher::PatternWithCaptures { elements, .. } => {
                let mut pos = start_pos;

                for element in elements {
                    match element {
                        CompiledCaptureElement::Capture(inner_matcher, group_num) => {
                            if let Some((rel_start, rel_end)) =
                                inner_matcher.find(safe_slice(text, pos).unwrap_or(""))
                            {
                                if rel_start == 0 {
                                    let abs_start = pos;
                                    let abs_end = pos + rel_end;

                                    // Record this capture
                                    captures.push((*group_num, abs_start, abs_end));

                                    // Recursively extract nested captures
                                    let nested =
                                        inner_matcher.extract_nested_captures(text, abs_start);
                                    captures.extend(nested);

                                    pos = abs_end;
                                } else {
                                    break;
                                }
                            } else {
                                break;
                            }
                        }
                        CompiledCaptureElement::NonCapture(inner_matcher) => {
                            if let Some((rel_start, rel_end)) =
                                inner_matcher.find(safe_slice(text, pos).unwrap_or(""))
                            {
                                if rel_start == 0 {
                                    let abs_start = pos;

                                    // Even for non-capturing, extract nested captures
                                    let nested =
                                        inner_matcher.extract_nested_captures(text, abs_start);
                                    captures.extend(nested);

                                    pos += rel_end;
                                } else {
                                    break;
                                }
                            } else {
                                break;
                            }
                        }
                    }
                }
            }
            Matcher::Capture(inner_matcher, group_num) => {
                // This is a single capture - record it and check for nested
                if let Some((rel_start, rel_end)) =
                    inner_matcher.find(safe_slice(text, start_pos).unwrap_or(""))
                {
                    let abs_start = start_pos + rel_start;
                    let abs_end = start_pos + rel_end;

                    // Record this capture
                    captures.push((*group_num, abs_start, abs_end));

                    // Recursively extract nested captures
                    let nested = inner_matcher.extract_nested_captures(text, abs_start);
                    captures.extend(nested);
                }
            }
            Matcher::AlternationWithCaptures { branches, .. } => {
                // Try each branch to find which one matched
                for branch in branches {
                    if let Some((rel_start, _rel_end)) =
                        branch.find(safe_slice(text, start_pos).unwrap_or(""))
                    {
                        if rel_start == 0 {
                            let abs_start = start_pos;
                            // Extract captures from the matched branch
                            let nested = branch.extract_nested_captures(text, abs_start);
                            captures.extend(nested);
                            break; // Only one branch can match
                        }
                    }
                }
            }
            _ => {
                // Other matchers don't have nested captures
            }
        }

        captures
    }

    /// Match pattern with backreferences, tracking captures as we go
    /// Returns Some(end_pos) if match succeeds, None otherwise
    fn match_pattern_with_backreferences(
        text: &str,
        start_pos: usize,
        elements: &[CompiledCaptureElement],
    ) -> Option<usize> {
        let mut pos = start_pos;
        let mut capture_positions: Vec<(usize, usize)> = Vec::new();

        for element in elements {
            match element {
                CompiledCaptureElement::Capture(m, num) => {
                    if let Some((rel_start, rel_end)) = m.find(safe_slice(text, pos).unwrap_or(""))
                    {
                        if rel_start != 0 {
                            return None; // Must match at current position
                        }

                        let abs_start = pos;
                        let abs_end = pos + rel_end;

                        // Record capture position
                        while capture_positions.len() < *num {
                            capture_positions.push((0, 0));
                        }
                        capture_positions[*num - 1] = (abs_start, abs_end);
                        pos = abs_end;
                    } else {
                        return None;
                    }
                }
                CompiledCaptureElement::NonCapture(m) => {
                    // Check if this is a Backreference
                    if let Matcher::Backreference(ref_num) = m {
                        // Get the captured text for this backreference
                        if *ref_num > 0 && *ref_num <= capture_positions.len() {
                            let (cap_start, cap_end) = capture_positions[*ref_num - 1];
                            let captured_text = &text[cap_start..cap_end];

                            // Check if remaining text starts with the captured text
                            if text[pos..].starts_with(captured_text) {
                                pos += captured_text.len();
                            } else {
                                return None;
                            }
                        } else {
                            // Invalid backreference or not captured yet
                            return None;
                        }
                    } else {
                        // Normal non-capture element
                        if let Some((rel_start, rel_end)) =
                            m.find(safe_slice(text, pos).unwrap_or(""))
                        {
                            if rel_start != 0 {
                                return None;
                            }
                            pos += rel_end;
                        } else {
                            return None;
                        }
                    }
                }
            }
        }

        Some(pos)
    }

    /// Specialized fast path for \d+ pattern
    #[inline(always)]
    fn digit_run_is_match(text: &str) -> bool {
        let bytes = text.as_bytes();
        if bytes.is_empty() {
            return false;
        }

        // Check if text starts with at least one digit
        bytes.iter().any(|&b| b.is_ascii_digit())
    }

    /// Specialized fast path for \w+ pattern  
    #[inline(always)]
    fn word_run_is_match(text: &str) -> bool {
        let bytes = text.as_bytes();
        if bytes.is_empty() {
            return false;
        }

        // Check if text contains at least one word char [a-zA-Z0-9_]
        bytes.iter().any(|&b| {
            b.is_ascii_lowercase() || b.is_ascii_uppercase() || b.is_ascii_digit() || b == b'_'
        })
    }

    /// Match quantified capture pattern
    fn quantified_is_match(
        text: &str,
        inner_matcher: &Matcher,
        quantifier: &parser::quantifier::Quantifier,
    ) -> bool {
        Self::quantified_find(text, inner_matcher, quantifier).is_some()
    }

    /// Find quantified capture pattern
    fn quantified_find(
        text: &str,
        inner_matcher: &Matcher,
        quantifier: &parser::quantifier::Quantifier,
    ) -> Option<(usize, usize)> {
        let (min, max) = quantifier_bounds(quantifier);

        // Special case: empty text can match if min is 0
        if text.is_empty() {
            return if min == 0 { Some((0, 0)) } else { None };
        }

        // Try to match at each position in text
        for start_pos in 0..text.len() {
            let mut pos = start_pos;
            let mut count = 0;

            // Match inner pattern as many times as possible (greedy)
            while count < max && pos < text.len() {
                if let Some((rel_start, rel_end)) =
                    inner_matcher.find(safe_slice(text, pos).unwrap_or(""))
                {
                    // Must match at current position
                    if rel_start != 0 {
                        break;
                    }
                    if rel_end == 0 {
                        break; // Avoid infinite loops on zero-width matches
                    }
                    pos += rel_end;
                    count += 1;
                } else {
                    break;
                }
            }

            if count >= min {
                return Some((start_pos, pos));
            }
        }

        None
    }

    /// Check if a matcher contains a quantified pattern that can match variable lengths
    /// This is used to determine if backtracking is needed
    fn contains_quantified(matcher: &Matcher) -> bool {
        match matcher {
            Matcher::Quantified(_) | Matcher::QuantifiedCapture(_, _) => true,
            Matcher::Capture(inner, _) => Self::contains_quantified(inner),
            Matcher::PatternWithCaptures { elements, .. } => {
                // Check if this is a simple sequence with quantified elements
                // But NOT if it's just wrapping an alternation
                elements.iter().any(|elem| match elem {
                    CompiledCaptureElement::Capture(m, _)
                    | CompiledCaptureElement::NonCapture(m) => {
                        // Don't recurse into AlternationWithCaptures - alternations are not quantified
                        match m {
                            Matcher::AlternationWithCaptures { .. } => false,
                            _ => Self::contains_quantified(m),
                        }
                    }
                })
            }
            // AlternationWithCaptures itself is NOT a quantified pattern
            // It's a choice between alternatives, each of which has a fixed match
            Matcher::AlternationWithCaptures { .. } => false,
            _ => false,
        }
    }

    /// Try to match sequence of elements with backtracking support AND extract captures
    /// Returns (end_pos, capture_positions) if successful
    fn match_elements_with_backtrack_and_captures(
        text: &str,
        start_pos: usize,
        elements: &[CompiledCaptureElement],
    ) -> Option<(usize, Vec<(usize, usize, usize)>)> {
        // Base case: no more elements
        if elements.is_empty() {
            return Some((start_pos, Vec::new()));
        }

        // Get first element
        let first_element = &elements[0];

        // Check if this element contains a quantified pattern that needs backtracking
        let needs_backtracking = if elements.len() <= 1 {
            false
        } else {
            match first_element {
                CompiledCaptureElement::Capture(m, _) | CompiledCaptureElement::NonCapture(m) => {
                    Self::contains_quantified(m)
                }
            }
        };

        if needs_backtracking {
            // Backtracking needed
            let remaining_text = safe_slice(text, start_pos).unwrap_or("");
            let remaining_len = remaining_text.len();

            // Try each possible length from longest to shortest, including 0 for zero-width matches
            // This is important for quantifiers with min=0 like * and ?
            for try_len in (0..=remaining_len).rev() {
                let next_pos = start_pos + try_len;

                // Try to match remaining elements
                if let Some((final_pos, mut remaining_caps)) =
                    Self::match_elements_with_backtrack_and_captures(text, next_pos, &elements[1..])
                {
                    // Handle zero-width matches (try_len == 0)
                    if try_len == 0 {
                        // For zero-width matches, check if the quantifier allows min=0
                        match first_element {
                            CompiledCaptureElement::Capture(m, num) => {
                                if let Some((rel_start, rel_end)) = m.find("") {
                                    if rel_start == 0 && rel_end == 0 {
                                        // Zero-width capture matched
                                        let mut caps = vec![(*num, start_pos, start_pos)];
                                        caps.append(&mut remaining_caps);
                                        return Some((final_pos, caps));
                                    }
                                }
                            }
                            CompiledCaptureElement::NonCapture(m) => {
                                if let Some((rel_start, rel_end)) = m.find("") {
                                    if rel_start == 0 && rel_end == 0 {
                                        // Zero-width non-capture matched
                                        return Some((final_pos, remaining_caps));
                                    }
                                }
                            }
                        }
                    } else {
                        // Non-zero width match
                        let substring = safe_slice_range(text, start_pos, next_pos).unwrap_or("");

                        // Check if first element matches exactly this substring
                        match first_element {
                            CompiledCaptureElement::Capture(m, num) => {
                                if let Some((rel_start, rel_end)) = m.find(substring) {
                                    if rel_start == 0 && rel_end == substring.len() {
                                        // Capture matched
                                        let mut caps = vec![(*num, start_pos, next_pos)];
                                        caps.append(&mut remaining_caps);
                                        return Some((final_pos, caps));
                                    }
                                }
                            }
                            CompiledCaptureElement::NonCapture(m) => {
                                if let Some((rel_start, rel_end)) = m.find(substring) {
                                    if rel_start == 0 && rel_end == substring.len() {
                                        // Extract any nested captures from this matcher
                                        let nested_caps =
                                            m.extract_nested_captures(text, start_pos);
                                        let mut all_caps = nested_caps;
                                        all_caps.extend(remaining_caps);
                                        return Some((final_pos, all_caps));
                                    }
                                }
                            }
                        }
                    }
                }
            }
            None
        } else {
            // No backtracking needed
            match first_element {
                CompiledCaptureElement::Capture(m, num) => {
                    if let Some((rel_start, rel_end)) =
                        m.find(safe_slice(text, start_pos).unwrap_or(""))
                    {
                        if rel_start == 0 {
                            let next_pos = start_pos + rel_end;
                            if let Some((final_pos, mut remaining_caps)) =
                                Self::match_elements_with_backtrack_and_captures(
                                    text,
                                    next_pos,
                                    &elements[1..],
                                )
                            {
                                let mut caps = vec![(*num, start_pos, next_pos)];
                                caps.append(&mut remaining_caps);
                                return Some((final_pos, caps));
                            }
                        }
                    }
                    None
                }
                CompiledCaptureElement::NonCapture(m) => {
                    if let Some((rel_start, rel_end)) =
                        m.find(safe_slice(text, start_pos).unwrap_or(""))
                    {
                        if rel_start == 0 {
                            let next_pos = start_pos + rel_end;
                            if let Some((final_pos, remaining_caps)) =
                                Self::match_elements_with_backtrack_and_captures(
                                    text,
                                    next_pos,
                                    &elements[1..],
                                )
                            {
                                // Extract nested captures
                                let nested_caps = m.extract_nested_captures(text, start_pos);
                                let mut all_caps = nested_caps;
                                all_caps.extend(remaining_caps);
                                return Some((final_pos, all_caps));
                            }
                        }
                    }
                    None
                }
            }
        }
    }

    /// Try to match sequence of elements with backtracking support
    /// Returns (start, end) if successful
    fn match_elements_with_backtrack(
        text: &str,
        start_pos: usize,
        elements: &[CompiledCaptureElement],
    ) -> Option<usize> {
        // Base case: no more elements
        if elements.is_empty() {
            return Some(start_pos);
        }

        // Get first element
        let first_element = &elements[0];
        let first_matcher = match first_element {
            CompiledCaptureElement::Capture(m, _) => m,
            CompiledCaptureElement::NonCapture(m) => m,
        };

        // Check if this element contains a quantified pattern that needs backtracking
        // This includes: Quantified, QuantifiedCapture, and Captures containing quantified patterns
        let needs_backtracking = if elements.len() <= 1 {
            false // No backtracking needed if this is the last element
        } else {
            // Check if first_matcher contains a quantified pattern
            Self::contains_quantified(first_matcher)
        };

        if needs_backtracking {
            // Quantified element followed by more elements - need backtracking
            // Strategy: Try matching with progressively shorter lengths from remaining text

            let remaining_text = safe_slice(text, start_pos).unwrap_or("");
            let remaining_len = remaining_text.len();

            // Try each possible length from longest to shortest, including 0 for zero-width matches
            // This is important for quantifiers with min=0 like * and ?
            for try_len in (0..=remaining_len).rev() {
                let next_pos = start_pos + try_len;

                // Try to match remaining elements FIRST
                if let Some(final_pos) =
                    Self::match_elements_with_backtrack(text, next_pos, &elements[1..])
                {
                    // Remaining elements matched! Now check if first element can match EXACTLY this length
                    let substring = safe_slice_range(text, start_pos, next_pos).unwrap_or("");

                    // Check if first element matches exactly this substring
                    // It must match from start (rel_start == 0) and consume the entire substring (rel_end == substring.len())
                    // For zero-width matches (try_len == 0), we need to check if the quantifier allows min=0
                    if try_len == 0 {
                        // Zero-width match - only valid for quantifiers with min=0 (*, ?)
                        // Check by seeing if the matcher can match empty string
                        if let Some((rel_start, rel_end)) = first_matcher.find("") {
                            if rel_start == 0 && rel_end == 0 {
                                return Some(final_pos);
                            }
                        }
                    } else {
                        // Non-zero match
                        if let Some((rel_start, rel_end)) = first_matcher.find(substring) {
                            if rel_start == 0 && rel_end == substring.len() {
                                return Some(final_pos);
                            }
                        }
                    }
                }
            }

            None
        } else {
            // Non-quantified element or last element - match normally

            // Special case: if first element is AlternationWithCaptures, try all branches
            if let Matcher::AlternationWithCaptures { branches, .. } = first_matcher {
                // Try each branch - return first one that leads to complete match
                for branch in branches {
                    if let Some((rel_start, rel_end)) =
                        branch.find(safe_slice(text, start_pos).unwrap_or(""))
                    {
                        if rel_start == 0 {
                            let next_pos = start_pos + rel_end;
                            // Try to match remaining elements with this branch
                            if let Some(final_pos) =
                                Self::match_elements_with_backtrack(text, next_pos, &elements[1..])
                            {
                                return Some(final_pos);
                            }
                            // This branch didn't lead to complete match, try next branch
                        }
                    }
                }
                return None;
            }

            // Regular case: non-alternation element
            if let Some((rel_start, rel_end)) =
                first_matcher.find(safe_slice(text, start_pos).unwrap_or(""))
            {
                if rel_start == 0 {
                    let next_pos = start_pos + rel_end;
                    // Match remaining elements
                    return Self::match_elements_with_backtrack(text, next_pos, &elements[1..]);
                }
            }
            None
        }
    }

    /// Find all quantified capture matches
    fn quantified_find_all(
        text: &str,
        inner_matcher: &Matcher,
        quantifier: &parser::quantifier::Quantifier,
    ) -> Vec<(usize, usize)> {
        let mut matches = Vec::new();
        let mut search_pos = 0;

        while search_pos < text.len() {
            if let Some((start, end)) =
                Self::quantified_find(&text[search_pos..], inner_matcher, quantifier)
            {
                matches.push((search_pos + start, search_pos + end));
                search_pos += start + 1; // Avoid overlapping
                if start == end {
                    search_pos += 1; // Avoid infinite loop on zero-width match
                }
            } else {
                break;
            }
        }

        matches
    }

    fn find(&self, text: &str) -> Option<(usize, usize)> {
        match self {
            Matcher::Literal(lit) => {
                let pos = memmem::find(text.as_bytes(), lit.as_bytes())?;
                Some((pos, pos + lit.len()))
            }
            Matcher::MultiLiteral(ac) => {
                let mat = ac.find(text)?;
                Some((mat.start(), mat.end()))
            }
            Matcher::AnchoredLiteral {
                literal,
                start,
                end,
            } => match (start, end) {
                (true, true) => (text == literal).then_some((0, text.len())),
                (true, false) => text.starts_with(literal).then_some((0, literal.len())),
                (false, true) => text
                    .ends_with(literal)
                    .then(|| (text.len() - literal.len(), text.len())),
                _ => unreachable!(),
            },
            Matcher::AnchoredGroup { group, start, end } => {
                match (start, end) {
                    (true, true) => {
                        // Must match entire text
                        group.match_at(text, 0).and_then(|len| {
                            if len == text.len() {
                                Some((0, len))
                            } else {
                                None
                            }
                        })
                    }
                    (true, false) => {
                        // Must match at start
                        group.match_at(text, 0).map(|len| (0, len))
                    }
                    (false, true) => {
                        // Must match at end
                        group.find(text).and_then(|(start_pos, end_pos)| {
                            if end_pos == text.len() {
                                Some((start_pos, end_pos))
                            } else {
                                None
                            }
                        })
                    }
                    _ => unreachable!(),
                }
            }
            Matcher::AnchoredPattern { inner, start, end } => {
                match (start, end) {
                    (true, true) => {
                        // Must match entire text: match at position 0 and cover full text
                        inner.find(text).and_then(|(match_start, match_end)| {
                            if match_start == 0 && match_end == text.len() {
                                Some((0, text.len()))
                            } else {
                                None
                            }
                        })
                    }
                    (true, false) => {
                        // Must match at start
                        inner.find(text).and_then(|(match_start, match_end)| {
                            if match_start == 0 {
                                Some((0, match_end))
                            } else {
                                None
                            }
                        })
                    }
                    (false, true) => {
                        // Must match at end
                        inner.find(text).and_then(|(match_start, match_end)| {
                            if match_end == text.len() {
                                Some((match_start, match_end))
                            } else {
                                None
                            }
                        })
                    }
                    _ => unreachable!(),
                }
            }
            Matcher::CharClass(cc) => {
                // Find first character matching the class
                for (idx, ch) in text.char_indices() {
                    if cc.matches(ch) {
                        return Some((idx, idx + ch.len_utf8()));
                    }
                }
                None
            }
            Matcher::Quantified(qp) => qp.find(text),
            Matcher::Sequence(seq) => seq.find(text),
            Matcher::Group(group) => group.find(text),
            Matcher::DigitRun => Self::digit_run_find(text), // NEW: Specialized digit find
            Matcher::WordRun => Self::word_run_find(text),   // NEW: Specialized word find
            Matcher::Boundary(boundary_type) => {
                // Boundary returns position, need to map to (pos, pos) range
                boundary_type.find_first(text).map(|pos| (pos, pos))
            }
            Matcher::Lookaround(lookaround, inner_matcher) => {
                // Find first position where lookaround succeeds
                for pos in 0..=text.len() {
                    if lookaround.matches_at(text, pos, inner_matcher) {
                        return Some((pos, pos)); // Zero-width match
                    }
                }
                None
            }
            Matcher::Capture(inner_matcher, _group_index) => {
                // Capture groups don't affect position, use inner matcher
                inner_matcher.find(text)
            }
            Matcher::QuantifiedCapture(inner_matcher, quantifier) => {
                // Find quantified capture pattern
                Self::quantified_find(text, inner_matcher, quantifier)
            }
            Matcher::CombinedWithLookaround {
                prefix,
                lookaround,
                lookaround_matcher,
            } => {
                // Find first position where prefix matches AND lookaround succeeds
                let mut search_pos = 0;
                while search_pos < text.len() {
                    let remaining = &text[search_pos..];
                    if let Some((rel_start, rel_end)) = prefix.find(remaining) {
                        let abs_start = search_pos + rel_start;
                        let abs_end = search_pos + rel_end;

                        // Check if lookaround succeeds at the end of the prefix match
                        if lookaround.matches_at(text, abs_end, lookaround_matcher) {
                            return Some((abs_start, abs_end));
                        }

                        // Move search position past this match to try next one
                        search_pos = abs_start + 1;
                    } else {
                        break;
                    }
                }
                None
            }
            Matcher::LookbehindWithSuffix {
                lookbehind,
                lookbehind_matcher,
                suffix,
            } => {
                // Find first position where suffix matches AND lookbehind succeeds before it
                let mut search_pos = 0;
                while search_pos < text.len() {
                    let remaining = &text[search_pos..];
                    if let Some((rel_start, rel_end)) = suffix.find(remaining) {
                        let abs_start = search_pos + rel_start;
                        let abs_end = search_pos + rel_end;

                        // Check if lookbehind succeeds at the start of the suffix match
                        if lookbehind.matches_at(text, abs_start, lookbehind_matcher) {
                            return Some((abs_start, abs_end));
                        }

                        // Move search position past this match to try next one
                        search_pos = abs_start + 1;
                    } else {
                        break;
                    }
                }
                None
            }
            Matcher::PatternWithCaptures { elements, .. } => {
                // Special case: single element can match anywhere
                if elements.len() == 1 {
                    let matcher = match &elements[0] {
                        CompiledCaptureElement::Capture(m, _) => m,
                        CompiledCaptureElement::NonCapture(m) => m,
                    };
                    return matcher.find(text);
                }

                // Check if pattern contains backreferences
                let has_backrefs = elements.iter().any(|elem| {
                    matches!(
                        elem,
                        CompiledCaptureElement::NonCapture(Matcher::Backreference(_))
                    )
                });

                if has_backrefs {
                    // Use backreference-aware matching
                    for start_pos in 0..=text.len() {
                        if let Some(end_pos) =
                            Self::match_pattern_with_backreferences(text, start_pos, elements)
                        {
                            if end_pos > start_pos || elements.is_empty() {
                                return Some((start_pos, end_pos));
                            }
                        }
                    }
                    return None;
                }

                // NEW: Try to compile to DFA for efficient single-pass matching
                if let Some(dfa) = crate::engine::capture_dfa::compile_capture_pattern(elements) {
                    return dfa.find(text);
                }

                // Fallback: Linear scan through all positions
                for start_pos in 0..=text.len() {
                    if let Some(end_pos) =
                        Self::match_elements_with_backtrack(text, start_pos, elements)
                    {
                        if end_pos > start_pos || elements.is_empty() {
                            return Some((start_pos, end_pos));
                        }
                    }
                }

                None
            }
            Matcher::Backreference(_) => {
                // Backreferences cannot find without capture context
                None
            }
            Matcher::DFA(dfa) => {
                // DFA-optimized find
                dfa.find(text)
            }
            Matcher::LazyDFA(lazy_dfa) => {
                // Lazy DFA requires mutable access, clone it
                let mut dfa = lazy_dfa.clone();
                dfa.find(text)
            }
            Matcher::SequenceWithFlags(seq, flags) => {
                // Find with flags (e.g., DOTALL mode where . matches newlines)
                seq.find_with_flags(text, flags)
            }
            Matcher::AlternationWithCaptures { branches, .. } => {
                // Try each branch in order (leftmost-first), return first match
                let mut best_match: Option<(usize, usize)> = None;

                for branch in branches {
                    if let Some((start, end)) = branch.find(text) {
                        // Keep the leftmost (earliest starting) match
                        if best_match.is_none() || start < best_match.unwrap().0 {
                            best_match = Some((start, end));
                        }
                    }
                }
                best_match
            }
            Matcher::CaseInsensitive(inner) => {
                let bytes = text.as_bytes();
                let len = bytes.len();
                if len <= 256 {
                    let mut buf = [0u8; 256];
                    let mut all_ascii = true;
                    for i in 0..len {
                        let b = bytes[i];
                        if b >= 128 {
                            all_ascii = false;
                            break;
                        }
                        buf[i] = if b >= b'A' && b <= b'Z' { b + 32 } else { b };
                    }
                    if all_ascii {
                        let lower = unsafe { std::str::from_utf8_unchecked(&buf[..len]) };
                        return inner.find(lower);
                    }
                }
                let lower_text = text.to_lowercase();
                inner.find(&lower_text)
            }
        }
    }

    /// Find first run of digits in text
    #[inline(always)]
    fn digit_run_find(text: &str) -> Option<(usize, usize)> {
        let bytes = text.as_bytes();

        // Find start: first digit
        let mut start = None;
        for (i, &b) in bytes.iter().enumerate() {
            if b.is_ascii_digit() {
                start = Some(i);
                break;
            }
        }

        let start_idx = start?;

        // Find end: first non-digit after start
        let mut end_idx = bytes.len();
        for (i, &b) in bytes[start_idx..].iter().enumerate() {
            if !b.is_ascii_digit() {
                end_idx = start_idx + i;
                break;
            }
        }

        Some((start_idx, end_idx))
    }

    /// Find first run of word characters in text
    #[inline(always)]
    fn word_run_find(text: &str) -> Option<(usize, usize)> {
        let bytes = text.as_bytes();

        // Find start: first word char
        let mut start = None;
        for (i, &b) in bytes.iter().enumerate() {
            if b.is_ascii_lowercase() || b.is_ascii_uppercase() || b.is_ascii_digit() || b == b'_' {
                start = Some(i);
                break;
            }
        }

        let start_idx = start?;

        // Find end: first non-word char after start
        let mut end_idx = bytes.len();
        for (i, &b) in bytes[start_idx..].iter().enumerate() {
            if !(b.is_ascii_lowercase()
                || b.is_ascii_uppercase()
                || b.is_ascii_digit()
                || b == b'_')
            {
                end_idx = start_idx + i;
                break;
            }
        }

        Some((start_idx, end_idx))
    }

    fn find_all(&self, text: &str) -> Vec<(usize, usize)> {
        match self {
            Matcher::Literal(lit) => {
                let finder = memmem::Finder::new(lit.as_bytes());
                finder
                    .find_iter(text.as_bytes())
                    .map(|pos| (pos, pos + lit.len()))
                    .collect()
            }
            Matcher::MultiLiteral(ac) => ac
                .find_iter(text)
                .map(|mat| (mat.start(), mat.end()))
                .collect(),
            Matcher::AnchoredLiteral { .. } => {
                if let Some(m) = self.find(text) {
                    vec![m]
                } else {
                    vec![]
                }
            }
            Matcher::AnchoredGroup { .. } => {
                // Anchored groups can only match once
                if let Some(m) = self.find(text) {
                    vec![m]
                } else {
                    vec![]
                }
            }
            Matcher::AnchoredPattern { .. } => {
                // Anchored patterns can only match once
                if let Some(m) = self.find(text) {
                    vec![m]
                } else {
                    vec![]
                }
            }
            Matcher::CharClass(cc) => {
                // Find all characters matching the class
                text.char_indices()
                    .filter(|(_, ch)| cc.matches(*ch))
                    .map(|(idx, ch)| (idx, idx + ch.len_utf8()))
                    .collect()
            }
            Matcher::Quantified(qp) => qp.find_all(text),
            Matcher::Sequence(seq) => seq.find_all(text),
            Matcher::Group(group) => group.find_all(text),
            Matcher::DigitRun => Self::digit_run_find_all(text), // NEW: Specialized digit find_all
            Matcher::WordRun => Self::word_run_find_all(text),   // NEW: Specialized word find_all
            Matcher::Boundary(boundary_type) => {
                // Boundary returns positions, map to (pos, pos) ranges
                boundary_type
                    .find_all(text)
                    .into_iter()
                    .map(|pos| (pos, pos))
                    .collect()
            }
            Matcher::Lookaround(lookaround, inner_matcher) => {
                // Find all positions where lookaround succeeds
                (0..=text.len())
                    .filter(|&pos| lookaround.matches_at(text, pos, inner_matcher))
                    .map(|pos| (pos, pos)) // Zero-width matches
                    .collect()
            }
            Matcher::Capture(inner_matcher, _group_index) => {
                // Capture groups don't affect find_all, use inner matcher
                inner_matcher.find_all(text)
            }
            Matcher::QuantifiedCapture(inner_matcher, quantifier) => {
                // Find all quantified capture matches
                Self::quantified_find_all(text, inner_matcher, quantifier)
            }
            Matcher::CombinedWithLookaround {
                prefix,
                lookaround,
                lookaround_matcher,
            } => {
                // Find all positions where prefix matches AND lookaround succeeds
                let mut matches = Vec::new();
                let mut search_pos = 0;

                while search_pos < text.len() {
                    let remaining = &text[search_pos..];
                    if let Some((rel_start, rel_end)) = prefix.find(remaining) {
                        let abs_start = search_pos + rel_start;
                        let abs_end = search_pos + rel_end;

                        // Check if lookaround succeeds at the end of the prefix match
                        if lookaround.matches_at(text, abs_end, lookaround_matcher) {
                            matches.push((abs_start, abs_end));
                        }

                        // Move search position past the start of this match
                        search_pos = abs_start + 1;
                    } else {
                        break;
                    }
                }

                matches
            }
            Matcher::LookbehindWithSuffix {
                lookbehind,
                lookbehind_matcher,
                suffix,
            } => {
                // Find all positions where suffix matches AND lookbehind succeeds before it
                let mut matches = Vec::new();
                let mut search_pos = 0;

                while search_pos < text.len() {
                    let remaining = &text[search_pos..];
                    if let Some((rel_start, rel_end)) = suffix.find(remaining) {
                        let abs_start = search_pos + rel_start;
                        let abs_end = search_pos + rel_end;

                        // Check if lookbehind succeeds at the start of the suffix match
                        if lookbehind.matches_at(text, abs_start, lookbehind_matcher) {
                            matches.push((abs_start, abs_end));
                        }

                        // Move search position past the start of this match
                        search_pos = abs_start + 1;
                    } else {
                        break;
                    }
                }

                matches
            }
            Matcher::PatternWithCaptures { elements, .. } => {
                // Find all matches of all elements in sequence
                let mut matches = Vec::new();
                let mut start_pos = 0;

                while start_pos < text.len() {
                    let mut pos = start_pos;
                    let mut all_matched = true;

                    for element in elements {
                        let matcher = match element {
                            CompiledCaptureElement::Capture(m, _) => m,
                            CompiledCaptureElement::NonCapture(m) => m,
                        };

                        if let Some((rel_start, rel_end)) =
                            matcher.find(safe_slice(text, pos).unwrap_or(""))
                        {
                            if rel_start != 0 {
                                // Element must match at current position
                                all_matched = false;
                                break;
                            }
                            pos += rel_end;
                        } else {
                            all_matched = false;
                            break;
                        }
                    }

                    if all_matched {
                        matches.push((start_pos, pos));
                        start_pos = pos.max(start_pos + 1); // Move past this match
                    } else {
                        start_pos += 1;
                    }
                }

                matches
            }
            Matcher::Backreference(_) => {
                // Backreferences cannot find_all without capture context
                vec![]
            }
            Matcher::DFA(dfa) => {
                // DFA find_all - multiple matches
                let mut matches = Vec::new();
                let mut search_start = 0;

                while search_start < text.len() {
                    if let Some((start, end)) = dfa.find(&text[search_start..]) {
                        let abs_start = search_start + start;
                        let abs_end = search_start + end;
                        matches.push((abs_start, abs_end));
                        search_start = abs_end.max(abs_start + 1);
                    } else {
                        break;
                    }
                }

                matches
            }
            Matcher::LazyDFA(lazy_dfa) => {
                // Lazy DFA find_all
                let mut dfa = lazy_dfa.clone();
                let mut matches = Vec::new();
                let mut search_start = 0;

                while search_start < text.len() {
                    if let Some((start, end)) = dfa.find(&text[search_start..]) {
                        let abs_start = search_start + start;
                        let abs_end = search_start + end;
                        matches.push((abs_start, abs_end));
                        search_start = abs_end.max(abs_start + 1);
                    } else {
                        break;
                    }
                }

                matches
            }
            Matcher::SequenceWithFlags(seq, flags) => {
                // Find all with flags
                let mut matches = Vec::new();
                let mut search_start = 0;

                while search_start < text.len() {
                    if let Some((start, end)) = seq.find_with_flags(&text[search_start..], flags) {
                        let abs_start = search_start + start;
                        let abs_end = search_start + end;
                        matches.push((abs_start, abs_end));
                        search_start = abs_end.max(abs_start + 1);
                    } else {
                        break;
                    }
                }

                matches
            }
            Matcher::AlternationWithCaptures { branches, .. } => {
                // Find all matches from any branch
                let mut matches = Vec::new();
                let mut search_start = 0;

                while search_start < text.len() {
                    // Try each branch and find the leftmost match
                    let mut best_match: Option<(usize, usize)> = None;

                    for branch in branches {
                        if let Some((start, end)) = branch.find(&text[search_start..]) {
                            let abs_start = search_start + start;
                            let abs_end = search_start + end;

                            if best_match.is_none() || abs_start < best_match.unwrap().0 {
                                best_match = Some((abs_start, abs_end));
                            }
                        }
                    }

                    if let Some((start, end)) = best_match {
                        matches.push((start, end));
                        search_start = end.max(start + 1);
                    } else {
                        break;
                    }
                }

                matches
            }
            Matcher::CaseInsensitive(inner) => {
                let bytes = text.as_bytes();
                let len = bytes.len();
                if len <= 256 {
                    let mut buf = [0u8; 256];
                    let mut all_ascii = true;
                    for i in 0..len {
                        let b = bytes[i];
                        if b >= 128 {
                            all_ascii = false;
                            break;
                        }
                        buf[i] = if b >= b'A' && b <= b'Z' { b + 32 } else { b };
                    }
                    if all_ascii {
                        let lower = unsafe { std::str::from_utf8_unchecked(&buf[..len]) };
                        return inner.find_all(lower);
                    }
                }
                let lower_text = text.to_lowercase();
                inner.find_all(&lower_text)
            }
        }
    }

    /// Find all runs of digits in text (optimized)
    #[inline]
    fn digit_run_find_all(text: &str) -> Vec<(usize, usize)> {
        let bytes = text.as_bytes();
        let mut matches = Vec::new();
        let mut i = 0;

        while i < bytes.len() {
            // Skip non-digits
            while i < bytes.len() && (bytes[i] < b'0' || bytes[i] > b'9') {
                i += 1;
            }

            if i >= bytes.len() {
                break;
            }

            // Found start of digit run
            let start = i;

            // Consume all digits
            while i < bytes.len() && bytes[i] >= b'0' && bytes[i] <= b'9' {
                i += 1;
            }

            matches.push((start, i));
        }

        matches
    }

    /// Find all runs of word characters in text (optimized)
    #[inline]
    fn word_run_find_all(text: &str) -> Vec<(usize, usize)> {
        let bytes = text.as_bytes();
        let mut matches = Vec::new();
        let mut i = 0;

        while i < bytes.len() {
            // Skip non-word chars
            while i < bytes.len() {
                let b = bytes[i];
                if b.is_ascii_lowercase()
                    || b.is_ascii_uppercase()
                    || b.is_ascii_digit()
                    || b == b'_'
                {
                    break;
                }
                i += 1;
            }

            if i >= bytes.len() {
                break;
            }

            // Found start of word run
            let start = i;

            // Consume all word chars
            while i < bytes.len() {
                let b = bytes[i];
                if !(b.is_ascii_lowercase()
                    || b.is_ascii_uppercase()
                    || b.is_ascii_digit()
                    || b == b'_')
                {
                    break;
                }
                i += 1;
            }

            matches.push((start, i));
        }

        matches
    }
}

fn compile_ast(ast: &Ast) -> Result<Matcher, PatternError> {
    match ast {
        Ast::Literal(lit) => Ok(Matcher::Literal(lit.clone())),
        Ast::Dot => {
            // Dot matches any character except newline
            // Parse as [^\n] character class
            use crate::parser::charclass::CharClass;
            let char_class = CharClass::parse(r"^\n")
                .map_err(|e| PatternError::ParseError(format!("Dot charclass: {}", e)))?;
            Ok(Matcher::CharClass(char_class))
        }
        Ast::Alternation(parts) => {
            use aho_corasick::MatchKind;
            let ac = AhoCorasick::builder()
                .match_kind(MatchKind::LeftmostFirst)
                .build(parts)
                .map_err(|e| PatternError::ParseError(format!("Aho-Corasick: {}", e)))?;
            Ok(Matcher::MultiLiteral(ac))
        }
        Ast::Anchored {
            literal,
            start,
            end,
        } => Ok(Matcher::AnchoredLiteral {
            literal: literal.clone(),
            start: *start,
            end: *end,
        }),
        Ast::AnchoredGroup { group, start, end } => Ok(Matcher::AnchoredGroup {
            group: group.clone(),
            start: *start,
            end: *end,
        }),
        Ast::AnchoredPattern { inner, start, end } => {
            if let Some(literal) = literal_from_ast(inner) {
                return Ok(Matcher::AnchoredLiteral {
                    literal,
                    start: *start,
                    end: *end,
                });
            }

            let inner_matcher = compile_ast(inner)?;
            Ok(Matcher::AnchoredPattern {
                inner: Box::new(inner_matcher),
                start: *start,
                end: *end,
            })
        }
        Ast::CharClass(cc) => Ok(Matcher::CharClass(cc.clone())),
        Ast::Quantified(qp) => {
            // OPTIMIZATION: Detect \d+ and \w+ patterns for specialized fast path
            if let crate::parser::quantifier::Quantifier::OneOrMore = qp.quantifier {
                if let crate::parser::quantifier::QuantifiedElement::CharClass(ref cc) = qp.element
                {
                    // Check if this is \d+ (digits)
                    if is_digit_charclass(cc) {
                        return Ok(Matcher::DigitRun);
                    }
                    // Check if this is \w+ (word chars)
                    if is_word_charclass(cc) {
                        return Ok(Matcher::WordRun);
                    }
                }
            }
            Ok(Matcher::Quantified(qp.clone()))
        }
        Ast::Sequence(seq) => {
            // Lazy DFA is experimental and currently slower - disabled for now
            // TODO: Optimize LazyDFA implementation
            // if let Some(lazy_dfa) = engine::lazy_dfa::LazyDFA::try_compile(seq) {
            //     return Ok(Matcher::LazyDFA(lazy_dfa));
            // }

            // Try to compile to DFA for better performance
            if let Some(dfa) = engine::dfa::DFA::try_compile(seq) {
                return Ok(Matcher::DFA(dfa));
            }
            // Fallback to regular sequence matcher
            Ok(Matcher::Sequence(seq.clone()))
        }
        Ast::Group(group) => Ok(Matcher::Group(group.clone())),
        Ast::Boundary(boundary_type) => Ok(Matcher::Boundary(*boundary_type)),
        Ast::Lookaround(lookaround) => {
            // Compile the inner pattern of the lookaround
            let inner_matcher = compile_ast(&lookaround.pattern)?;
            Ok(Matcher::Lookaround(
                Box::new(lookaround.clone()),
                Box::new(inner_matcher),
            ))
        }
        Ast::Capture(inner_ast, group_index) => {
            // Compile the inner pattern of the capture group
            let inner_matcher = compile_ast(inner_ast)?;
            Ok(Matcher::Capture(Box::new(inner_matcher), *group_index))
        }
        Ast::QuantifiedCapture(inner_ast, quantifier) => {
            // Compile the inner pattern and create a quantified capture matcher
            let inner_matcher = compile_ast(inner_ast)?;
            Ok(Matcher::QuantifiedCapture(
                Box::new(inner_matcher),
                quantifier.clone(),
            ))
        }
        Ast::CombinedWithLookaround { prefix, lookaround } => {
            // Compile both the prefix and the lookaround's inner pattern
            let prefix_matcher = compile_ast(prefix)?;
            let lookaround_inner = compile_ast(&lookaround.pattern)?;
            Ok(Matcher::CombinedWithLookaround {
                prefix: Box::new(prefix_matcher),
                lookaround: Box::new(lookaround.clone()),
                lookaround_matcher: Box::new(lookaround_inner),
            })
        }
        Ast::LookbehindWithSuffix { lookbehind, suffix } => {
            // Compile both the lookbehind and the suffix
            let lookbehind_inner = compile_ast(&lookbehind.pattern)?;
            let suffix_matcher = compile_ast(suffix)?;
            Ok(Matcher::LookbehindWithSuffix {
                lookbehind: Box::new(lookbehind.clone()),
                lookbehind_matcher: Box::new(lookbehind_inner),
                suffix: Box::new(suffix_matcher),
            })
        }
        Ast::PatternWithCaptures {
            elements,
            total_groups,
        } => {
            // Compile each element
            let mut compiled_elements = Vec::new();
            for elem in elements {
                match elem {
                    CaptureElement::Capture(ast, group_num) => {
                        let matcher = compile_ast(ast)?;
                        compiled_elements
                            .push(CompiledCaptureElement::Capture(matcher, *group_num));
                    }
                    CaptureElement::NonCapture(ast) => {
                        let matcher = compile_ast(ast)?;
                        compiled_elements.push(CompiledCaptureElement::NonCapture(matcher));
                    }
                }
            }
            Ok(Matcher::PatternWithCaptures {
                elements: compiled_elements,
                total_groups: *total_groups,
            })
        }
        Ast::AlternationWithCaptures {
            branches,
            total_groups,
        } => {
            // Compile each branch
            let mut compiled_branches = Vec::new();
            for branch_ast in branches {
                let branch_matcher = compile_ast(branch_ast)?;
                compiled_branches.push(branch_matcher);
            }
            Ok(Matcher::AlternationWithCaptures {
                branches: compiled_branches,
                total_groups: *total_groups,
            })
        }
        Ast::Backreference(group_num) => Ok(Matcher::Backreference(*group_num)),
        Ast::DotAll => {
            // DotAll matches ANY character including newline
            // Create a character class that matches everything
            use crate::parser::charclass::CharClass;
            // Use empty negated class which matches everything
            let mut char_class = CharClass::new();
            char_class.add_range('\0', char::MAX); // Match all unicode
            char_class.finalize();
            Ok(Matcher::CharClass(char_class))
        }
        Ast::SequenceWithFlags(seq, flags) => {
            // Compile sequence with flag awareness
            Ok(Matcher::SequenceWithFlags(seq.clone(), *flags))
        }
        Ast::CaseInsensitive(inner) => {
            // Lowercase the pattern before compiling
            let lowercased = lowercase_ast(inner);
            let inner_matcher = compile_ast(&lowercased)?;
            Ok(Matcher::CaseInsensitive(Box::new(inner_matcher)))
        }
    }
}

fn literal_from_ast(ast: &Ast) -> Option<String> {
    match ast {
        Ast::Literal(lit) => Some(lit.clone()),
        Ast::Sequence(seq) => {
            let mut literal = String::new();
            for element in &seq.elements {
                match element {
                    parser::sequence::SequenceElement::Char(ch) => literal.push(*ch),
                    parser::sequence::SequenceElement::Literal(lit) => literal.push_str(lit),
                    _ => return None,
                }
            }
            Some(literal)
        }
        _ => None,
    }
}

/// Lowercase all literals in an AST for case-insensitive matching
fn lowercase_ast(ast: &Ast) -> Ast {
    match ast {
        Ast::Literal(s) => Ast::Literal(s.to_lowercase()),
        Ast::Alternation(branches) => {
            Ast::Alternation(branches.iter().map(|s| s.to_lowercase()).collect())
        }
        Ast::Group(g) => {
            // Lowercase group content
            let mut new_group = g.clone();
            new_group.content = match &g.content {
                parser::group::GroupContent::Single(s) => {
                    parser::group::GroupContent::Single(s.to_lowercase())
                }
                parser::group::GroupContent::Alternation(branches) => {
                    parser::group::GroupContent::Alternation(
                        branches.iter().map(|s| s.to_lowercase()).collect(),
                    )
                }
                parser::group::GroupContent::Sequence(seq) => {
                    let mut new_seq = seq.clone();
                    new_seq.elements = new_seq
                        .elements
                        .into_iter()
                        .map(|elem| match elem {
                            parser::sequence::SequenceElement::Literal(s) => {
                                parser::sequence::SequenceElement::Literal(s.to_lowercase())
                            }
                            parser::sequence::SequenceElement::Char(c) => {
                                let lowered: String = c.to_lowercase().collect();
                                if lowered.len() == 1 {
                                    parser::sequence::SequenceElement::Char(
                                        lowered.chars().next().unwrap(),
                                    )
                                } else {
                                    parser::sequence::SequenceElement::Literal(lowered)
                                }
                            }
                            other => other,
                        })
                        .collect();
                    parser::group::GroupContent::Sequence(new_seq)
                }
                parser::group::GroupContent::ParsedAlternation(sequences) => {
                    let new_sequences: Vec<_> = sequences
                        .iter()
                        .map(|seq| {
                            let mut new_seq = seq.clone();
                            new_seq.elements = new_seq
                                .elements
                                .into_iter()
                                .map(|elem| match elem {
                                    parser::sequence::SequenceElement::Literal(s) => {
                                        parser::sequence::SequenceElement::Literal(s.to_lowercase())
                                    }
                                    parser::sequence::SequenceElement::Char(c) => {
                                        let lowered: String = c.to_lowercase().collect();
                                        if lowered.len() == 1 {
                                            parser::sequence::SequenceElement::Char(
                                                lowered.chars().next().unwrap(),
                                            )
                                        } else {
                                            parser::sequence::SequenceElement::Literal(lowered)
                                        }
                                    }
                                    other => other,
                                })
                                .collect();
                            new_seq
                        })
                        .collect();
                    parser::group::GroupContent::ParsedAlternation(new_sequences)
                }
            };
            Ast::Group(new_group)
        }
        Ast::Sequence(seq) => {
            // Lowercase literals in sequence elements and rebuild sequence
            // (must rebuild NFA table with lowered chars)
            let new_elements: Vec<_> = seq
                .elements
                .iter()
                .map(|elem| match elem {
                    parser::sequence::SequenceElement::Literal(s) => {
                        parser::sequence::SequenceElement::Literal(s.to_lowercase())
                    }
                    parser::sequence::SequenceElement::Char(c) => {
                        let lowered: String = c.to_lowercase().collect();
                        if lowered.len() == 1 {
                            parser::sequence::SequenceElement::Char(lowered.chars().next().unwrap())
                        } else {
                            parser::sequence::SequenceElement::Literal(lowered)
                        }
                    }
                    other => other.clone(),
                })
                .collect();
            Ast::Sequence(parser::sequence::Sequence::new(new_elements))
        }
        Ast::Anchored {
            literal,
            start,
            end,
        } => Ast::Anchored {
            literal: literal.to_lowercase(),
            start: *start,
            end: *end,
        },
        Ast::AnchoredPattern { inner, start, end } => Ast::AnchoredPattern {
            inner: Box::new(lowercase_ast(inner)),
            start: *start,
            end: *end,
        },
        Ast::SequenceWithFlags(seq, flags) => {
            let mut new_seq = seq.clone();
            new_seq.elements = new_seq
                .elements
                .into_iter()
                .map(|elem| match elem {
                    parser::sequence::SequenceElement::Literal(s) => {
                        parser::sequence::SequenceElement::Literal(s.to_lowercase())
                    }
                    parser::sequence::SequenceElement::Char(c) => {
                        let lowered: String = c.to_lowercase().collect();
                        if lowered.len() == 1 {
                            parser::sequence::SequenceElement::Char(lowered.chars().next().unwrap())
                        } else {
                            parser::sequence::SequenceElement::Literal(lowered)
                        }
                    }
                    other => other,
                })
                .collect();
            Ast::SequenceWithFlags(new_seq, *flags)
        }
        Ast::CaseInsensitive(inner) => {
            // Already case-insensitive, just lowercase inner
            Ast::CaseInsensitive(Box::new(lowercase_ast(inner)))
        }
        Ast::PatternWithCaptures {
            elements,
            total_groups,
        } => {
            // Lowercase literals in capture elements
            let new_elements = elements
                .iter()
                .map(|elem| match elem {
                    CaptureElement::NonCapture(ast) => {
                        CaptureElement::NonCapture(lowercase_ast(ast))
                    }
                    CaptureElement::Capture(ast, group_num) => {
                        CaptureElement::Capture(lowercase_ast(ast), *group_num)
                    }
                })
                .collect();
            Ast::PatternWithCaptures {
                elements: new_elements,
                total_groups: *total_groups,
            }
        }
        Ast::AlternationWithCaptures {
            branches,
            total_groups,
        } => Ast::AlternationWithCaptures {
            branches: branches.iter().map(lowercase_ast).collect(),
            total_groups: *total_groups,
        },
        Ast::Capture(inner, group_index) => {
            // Lowercase the inner AST of the capture group
            Ast::Capture(Box::new(lowercase_ast(inner)), *group_index)
        }
        // For other AST types that don't contain literals, just clone
        _ => ast.clone(),
    }
}

/// Get min and max repetitions for a quantifier
fn quantifier_bounds(q: &parser::quantifier::Quantifier) -> (usize, usize) {
    use parser::quantifier::Quantifier;
    match q {
        Quantifier::ZeroOrMore | Quantifier::ZeroOrMoreLazy => (0, usize::MAX),
        Quantifier::OneOrMore | Quantifier::OneOrMoreLazy => (1, usize::MAX),
        Quantifier::ZeroOrOne | Quantifier::ZeroOrOneLazy => (0, 1),
        Quantifier::Exactly(n) => (*n, *n),
        Quantifier::AtLeast(n) => (*n, usize::MAX),
        Quantifier::Between(n, m) => (*n, *m),
    }
}

/// Check if CharClass matches \d pattern (only [0-9])
fn is_digit_charclass(cc: &CharClass) -> bool {
    // Check if ranges contain exactly [0-9] and no other chars
    cc.ranges.len() == 1 && cc.ranges[0] == ('0', '9') && cc.chars.is_empty() && !cc.negated
}

/// Check if CharClass matches \w pattern ([a-zA-Z0-9_])
fn is_word_charclass(cc: &CharClass) -> bool {
    // Check if ranges contain [a-z], [A-Z], [0-9] and chars contain '_'
    if cc.negated || cc.ranges.len() != 3 {
        return false;
    }

    let mut has_lower = false;
    let mut has_upper = false;
    let mut has_digit = false;

    for &(start, end) in &cc.ranges {
        if start == 'a' && end == 'z' {
            has_lower = true;
        } else if start == 'A' && end == 'Z' {
            has_upper = true;
        } else if start == '0' && end == '9' {
            has_digit = true;
        }
    }

    has_lower && has_upper && has_digit && cc.chars.len() == 1 && cc.chars[0] == '_'
}

/// Parse lookaround assertion patterns: (?=...), (?!...), (?<=...), (?<!...)
fn parse_lookaround(pattern: &str, depth: usize) -> Result<Ast, PatternError> {
    let lookaround_type = if pattern.starts_with("(?=") {
        LookaroundType::PositiveLookahead
    } else if pattern.starts_with("(?!") {
        LookaroundType::NegativeLookahead
    } else if pattern.starts_with("(?<=") {
        LookaroundType::PositiveLookbehind
    } else if pattern.starts_with("(?<!") {
        LookaroundType::NegativeLookbehind
    } else {
        return Err(PatternError::ParseError(
            "Invalid lookaround syntax".to_string(),
        ));
    };

    // Find the matching closing parenthesis
    let prefix_len = if pattern.starts_with("(?<=") || pattern.starts_with("(?<!") {
        4 // "(?<=" or "(?<!"
    } else {
        3 // "(?=" or "(?!"
    };

    if let Some(close_idx) = find_matching_paren(pattern, 0) {
        let inner = &pattern[prefix_len..close_idx];
        let inner_ast = parse_pattern_with_depth(inner, depth + 1)?;

        // Check if there's a suffix after the lookaround
        if close_idx != pattern.len() - 1 {
            // This is a lookaround with suffix
            let suffix = &pattern[close_idx + 1..];
            let suffix_ast = parse_pattern_with_depth(suffix, depth + 1)?;

            // For lookbehind: (?<=foo)bar - match bar only if preceded by foo
            // For lookahead: (?=foo)bar - doesn't make semantic sense
            if matches!(
                lookaround_type,
                LookaroundType::PositiveLookbehind | LookaroundType::NegativeLookbehind
            ) {
                let lookbehind = Lookaround::new(lookaround_type, inner_ast);
                return Ok(Ast::LookbehindWithSuffix {
                    lookbehind,
                    suffix: Box::new(suffix_ast),
                });
            } else {
                return Err(PatternError::ParseError(
                    "Lookahead cannot have suffix pattern after it".to_string(),
                ));
            }
        }

        Ok(Ast::Lookaround(Lookaround::new(lookaround_type, inner_ast)))
    } else {
        Err(PatternError::ParseError(
            "Unmatched parenthesis in lookaround".to_string(),
        ))
    }
}

/// Parse combined patterns with lookaround: foo(?=bar), \d+(?!x), etc.
fn parse_combined_with_lookaround(pattern: &str, depth: usize) -> Result<Ast, PatternError> {
    // Find the lookaround position
    let lookaround_patterns = ["(?=", "(?!", "(?<=", "(?<!"];

    for lookaround_start in lookaround_patterns {
        if let Some(pos) = pattern.find(lookaround_start) {
            if pos == 0 {
                // This is a standalone lookaround, not combined
                continue;
            }

            // Split into prefix and lookaround
            let prefix = &pattern[..pos];
            let lookaround_part = &pattern[pos..];

            // Parse the prefix
            let prefix_ast = parse_pattern_with_depth(prefix, depth + 1)?;

            // Parse the lookaround
            let lookaround_type = if lookaround_start == "(?=" {
                LookaroundType::PositiveLookahead
            } else if lookaround_start == "(?!" {
                LookaroundType::NegativeLookahead
            } else if lookaround_start == "(?<=" {
                LookaroundType::PositiveLookbehind
            } else {
                LookaroundType::NegativeLookbehind
            };

            let prefix_len = lookaround_start.len();
            if let Some(close_idx) = find_matching_paren(lookaround_part, 0) {
                if close_idx != lookaround_part.len() - 1 {
                    return Err(PatternError::ParseError(
                        "Extra characters after lookaround".to_string(),
                    ));
                }

                let inner = &lookaround_part[prefix_len..close_idx];
                let inner_ast = parse_pattern_with_depth(inner, depth + 1)?;

                let lookaround = Lookaround::new(lookaround_type, inner_ast);

                return Ok(Ast::CombinedWithLookaround {
                    prefix: Box::new(prefix_ast),
                    lookaround,
                });
            } else {
                return Err(PatternError::ParseError(
                    "Unmatched parenthesis in lookaround".to_string(),
                ));
            }
        }
    }

    Err(PatternError::ParseError(
        "No lookaround found in pattern".to_string(),
    ))
}

/// Find the index of the matching closing parenthesis
/// Returns None if no match found
/// Check if a pattern contains unescaped parentheses (not \( or \) and not inside [...])
fn contains_unescaped_paren(pattern: &str) -> bool {
    let bytes = pattern.as_bytes();
    let mut i = 0;
    while i < bytes.len() {
        if bytes[i] == b'\\' && i + 1 < bytes.len() {
            i += 2; // Skip escaped character
        } else if bytes[i] == b'[' {
            // Skip character class to avoid counting parens inside it
            i += 1;
            if i < bytes.len() && bytes[i] == b'^' {
                i += 1;
            }
            while i < bytes.len() {
                if bytes[i] == b'\\' {
                    i += 2;
                } else if bytes[i] == b']' {
                    i += 1;
                    break;
                } else {
                    i += 1;
                }
            }
        } else if bytes[i] == b'(' || bytes[i] == b')' {
            return true;
        } else {
            i += 1;
        }
    }
    false
}

fn find_matching_paren(pattern: &str, start: usize) -> Option<usize> {
    let bytes = pattern.as_bytes();
    if start >= bytes.len() || bytes[start] != b'(' {
        return None;
    }

    let mut depth = 0;
    let mut i = 0;
    while i < bytes[start..].len() {
        match bytes[start + i] {
            b'\\' => {
                // Skip next character (could be escaped parenthesis)
                i += 2;
                continue;
            }
            b'[' => {
                // Skip character class [...] to avoid counting ) inside it
                i += 1;
                // Handle negation [^...]
                if i < bytes[start..].len() && bytes[start + i] == b'^' {
                    i += 1;
                }
                // Skip until closing ]
                while i < bytes[start..].len() {
                    if bytes[start + i] == b'\\' {
                        i += 2; // Skip escaped character
                    } else if bytes[start + i] == b']' {
                        i += 1;
                        break;
                    } else {
                        i += 1;
                    }
                }
                continue;
            }
            b'(' => depth += 1,
            b')' => {
                depth -= 1;
                if depth == 0 {
                    return Some(start + i);
                }
            }
            _ => {}
        }
        i += 1;
    }

    None // Unmatched
}

/// Parse patterns with embedded capture groups: Hello (\w+), (\w+)=(\d+), (\d{4})-(\d{2})-(\d{2})
/// Returns an AST that represents a sequence with captures
fn parse_pattern_with_captures(pattern: &str) -> Result<Ast, PatternError> {
    let mut group_counter = 1;
    let (ast, _total_groups) = parse_pattern_with_captures_inner(pattern, &mut group_counter)?;
    Ok(ast)
}

/// Split pattern by top-level '|' characters (not inside groups)
/// Returns None if no top-level alternation found
fn split_by_alternation(pattern: &str) -> Option<Vec<String>> {
    let mut branches = Vec::new();
    let mut current = String::new();
    let mut depth = 0;
    let mut chars = pattern.chars().peekable();

    while let Some(ch) = chars.next() {
        match ch {
            '\\' => {
                // Escape sequence - consume next char too
                current.push(ch);
                if let Some(next) = chars.next() {
                    current.push(next);
                }
            }
            '[' => {
                // Skip character class to avoid counting parens inside it
                current.push(ch);
                // Handle negation [^...]
                if chars.peek() == Some(&'^') {
                    current.push(chars.next().unwrap());
                }
                // Consume until closing ]
                while let Some(c) = chars.next() {
                    current.push(c);
                    if c == '\\' {
                        if let Some(next) = chars.next() {
                            current.push(next);
                        }
                    } else if c == ']' {
                        break;
                    }
                }
            }
            '(' => {
                depth += 1;
                current.push(ch);
            }
            ')' => {
                depth -= 1;
                current.push(ch);
            }
            '|' if depth == 0 => {
                // Top-level alternation found
                branches.push(current.clone());
                current.clear();
            }
            _ => {
                current.push(ch);
            }
        }
    }

    // Add the last branch
    if !current.is_empty() || !branches.is_empty() {
        branches.push(current);
    }

    // Only return Some if we found actual alternation (more than 1 branch)
    if branches.len() > 1 {
        Some(branches)
    } else {
        None
    }
}

/// Inner recursive parser that tracks group numbers across nested captures
fn parse_pattern_with_captures_inner(
    pattern: &str,
    group_counter: &mut usize,
) -> Result<(Ast, usize), PatternError> {
    // FIRST: Check if this pattern contains top-level alternation
    if let Some(branches) = split_by_alternation(pattern) {
        // This is an alternation pattern like (a)|(b) or foo|bar
        let _start_group = *group_counter;
        let mut parsed_branches = Vec::new();

        for branch in branches {
            // Parse each branch independently
            let (branch_ast, _) = parse_pattern_with_captures_inner(&branch, group_counter)?;
            parsed_branches.push(branch_ast);
        }

        let total_groups = *group_counter - 1;

        // Create an alternation AST
        // For now, we need to represent alternation with captures
        // We'll create a PatternWithCaptures that contains the alternation logic
        // But first check if all branches are simple literals
        let all_literals = parsed_branches
            .iter()
            .all(|ast| matches!(ast, Ast::Literal(_)));

        if all_literals {
            // Simple case: all branches are literals like "a"|"b"
            let literals: Vec<String> = parsed_branches
                .into_iter()
                .filter_map(|ast| {
                    if let Ast::Literal(s) = ast {
                        Some(s)
                    } else {
                        None
                    }
                })
                .collect();
            return Ok((Ast::Alternation(literals), total_groups));
        } else {
            // Complex case: branches contain captures or other complex patterns
            // Try to convert branches to sequences for ParsedAlternation
            let mut sequences = Vec::new();
            for branch_ast in &parsed_branches {
                // Try to extract a sequence from each branch
                if let Ast::Sequence(seq) = branch_ast {
                    sequences.push(seq.clone());
                } else {
                    // Can't use ParsedAlternation for non-sequence branches
                    break;
                }
            }

            if sequences.len() == parsed_branches.len() {
                // All branches are sequences - use ParsedAlternation
                use crate::parser::group::{Group, GroupContent};
                return Ok((
                    Ast::Group(Group::new_non_capturing(GroupContent::ParsedAlternation(
                        sequences,
                    ))),
                    total_groups,
                ));
            } else {
                // Mixed types or non-sequences (like Capture, Literal, etc.)
                // Use the new AlternationWithCaptures variant
                return Ok((
                    Ast::AlternationWithCaptures {
                        branches: parsed_branches,
                        total_groups,
                    },
                    total_groups,
                ));
            }
        }
    }

    // NO alternation at top level - parse as sequence
    let mut elements: Vec<CaptureElement> = Vec::new();
    let mut pos = 0;
    let start_group = *group_counter;

    while pos < pattern.len() {
        if pattern[pos..].starts_with("(?:") {
            // Found a non-capturing group (?:...)
            if let Some(close_idx) = find_matching_paren(pattern, pos) {
                // Parse the content as a non-capturing group (recursive)
                let inner = &pattern[pos + 3..close_idx]; // Skip "(?:"
                let (inner_ast, _) = parse_pattern_with_captures_inner(inner, group_counter)?;

                // Check for quantifier after the non-capturing group (same as capturing groups)
                let mut after_group = close_idx + 1;
                let mut quantifier: Option<parser::quantifier::Quantifier> = None;

                if after_group < pattern.len() {
                    let remaining = &pattern[after_group..];
                    let chars: Vec<char> = remaining.chars().take(2).collect();
                    if !chars.is_empty() {
                        let first = chars[0];
                        let has_lazy = chars.len() > 1 && chars[1] == '?';

                        match first {
                            '*' if has_lazy => {
                                quantifier = Some(parser::quantifier::Quantifier::ZeroOrMoreLazy);
                                after_group += 2;
                            }
                            '*' => {
                                quantifier = Some(parser::quantifier::Quantifier::ZeroOrMore);
                                after_group += 1;
                            }
                            '+' if has_lazy => {
                                quantifier = Some(parser::quantifier::Quantifier::OneOrMoreLazy);
                                after_group += 2;
                            }
                            '+' => {
                                quantifier = Some(parser::quantifier::Quantifier::OneOrMore);
                                after_group += 1;
                            }
                            '?' if has_lazy => {
                                quantifier = Some(parser::quantifier::Quantifier::ZeroOrOneLazy);
                                after_group += 2;
                            }
                            '?' => {
                                quantifier = Some(parser::quantifier::Quantifier::ZeroOrOne);
                                after_group += 1;
                            }
                            _ => {}
                        }
                    }
                }

                // Build the non-capture element with optional quantifier
                if let Some(q) = quantifier {
                    // Wrap the inner AST with a Quantified matcher
                    elements.push(CaptureElement::NonCapture(Ast::QuantifiedCapture(
                        Box::new(inner_ast),
                        q,
                    )));
                } else {
                    elements.push(CaptureElement::NonCapture(inner_ast));
                }
                pos = after_group;
            } else {
                return Err(PatternError::ParseError(
                    "Unmatched parenthesis".to_string(),
                ));
            }
        } else if pattern[pos..].starts_with('(') && !pattern[pos..].starts_with("(?") {
            // Found a capture group
            if let Some(close_idx) = find_matching_paren(pattern, pos) {
                let my_group_num = *group_counter;
                *group_counter += 1;

                // Parse the content of the capture (recursive, may have nested captures)
                let inner = &pattern[pos + 1..close_idx];
                let (inner_ast, _) = parse_pattern_with_captures_inner(inner, group_counter)?;

                // Check for quantifier after the group
                let mut after_group = close_idx + 1;
                let mut quantifier: Option<parser::quantifier::Quantifier> = None;

                if after_group < pattern.len() {
                    let remaining = &pattern[after_group..];
                    let chars: Vec<char> = remaining.chars().take(2).collect();
                    if !chars.is_empty() {
                        let first = chars[0];
                        let has_lazy = chars.len() > 1 && chars[1] == '?';

                        match first {
                            '*' if has_lazy => {
                                quantifier = Some(parser::quantifier::Quantifier::ZeroOrMoreLazy);
                                after_group += 2;
                            }
                            '*' => {
                                quantifier = Some(parser::quantifier::Quantifier::ZeroOrMore);
                                after_group += 1;
                            }
                            '+' if has_lazy => {
                                quantifier = Some(parser::quantifier::Quantifier::OneOrMoreLazy);
                                after_group += 2;
                            }
                            '+' => {
                                quantifier = Some(parser::quantifier::Quantifier::OneOrMore);
                                after_group += 1;
                            }
                            '?' if has_lazy => {
                                quantifier = Some(parser::quantifier::Quantifier::ZeroOrOneLazy);
                                after_group += 2;
                            }
                            '?' => {
                                quantifier = Some(parser::quantifier::Quantifier::ZeroOrOne);
                                after_group += 1;
                            }
                            _ => {}
                        }
                    }
                }

                // Build the capture AST with optional quantifier
                if let Some(q) = quantifier {
                    elements.push(CaptureElement::Capture(
                        Ast::QuantifiedCapture(Box::new(inner_ast), q),
                        my_group_num,
                    ));
                } else {
                    elements.push(CaptureElement::Capture(inner_ast, my_group_num));
                }
                pos = after_group;
            } else {
                return Err(PatternError::ParseError(
                    "Unmatched parenthesis".to_string(),
                ));
            }
        } else {
            // Check for backreference \1, \2, etc. AT CURRENT POSITION
            if pattern[pos..].starts_with('\\') && pos + 1 < pattern.len() {
                let next_char = pattern.chars().nth(pos + 1);
                if let Some(ch) = next_char {
                    if ch.is_ascii_digit() {
                        // This is a backreference like \1
                        let digit = ch.to_digit(10).unwrap() as usize;
                        elements.push(CaptureElement::NonCapture(Ast::Backreference(digit)));
                        pos += 2; // Skip \1
                        continue;
                    }
                }
            }

            // Find the next capture group, backreference, or end of pattern
            // Skip escaped parentheses and character classes when searching
            let next_paren = {
                let mut search_pos = pos;
                let mut result = pattern.len();
                let bytes = pattern.as_bytes();
                while search_pos < bytes.len() {
                    if bytes[search_pos] == b'\\' && search_pos + 1 < bytes.len() {
                        search_pos += 2; // Skip escaped character
                    } else if bytes[search_pos] == b'[' {
                        // Skip character class to avoid finding ( inside it
                        search_pos += 1;
                        if search_pos < bytes.len() && bytes[search_pos] == b'^' {
                            search_pos += 1;
                        }
                        while search_pos < bytes.len() {
                            if bytes[search_pos] == b'\\' {
                                search_pos += 2;
                            } else if bytes[search_pos] == b']' {
                                search_pos += 1;
                                break;
                            } else {
                                search_pos += 1;
                            }
                        }
                    } else if bytes[search_pos] == b'(' {
                        result = search_pos;
                        break;
                    } else {
                        search_pos += 1;
                    }
                }
                result
            };

            // Find next backreference \digit (search from current position + 1 to avoid finding current char)
            let mut search_pos = pos;
            let mut next_backref = pattern.len();

            while search_pos < pattern.len() {
                if pattern[search_pos..].starts_with('\\') && search_pos + 1 < pattern.len() {
                    let next_ch = pattern.chars().nth(search_pos + 1);
                    if next_ch.map(|c| c.is_ascii_digit()).unwrap_or(false) {
                        next_backref = search_pos;
                        break;
                    }
                    search_pos += 2; // Skip this escape
                } else {
                    search_pos += 1;
                }
            }

            // Take the minimum of next_paren and next_backref
            let next_boundary = next_paren.min(next_backref);

            if next_boundary > pos {
                // There's a literal or other pattern before the next capture/backref
                let segment = &pattern[pos..next_boundary];

                // Parse segment without going through capture detection
                let segment_ast = if segment.is_empty() {
                    Ast::Literal(String::new())
                } else {
                    // Use basic parsing for non-capture segments
                    parse_pattern(segment)?
                };

                elements.push(CaptureElement::NonCapture(segment_ast));
                pos = next_boundary;
            } else {
                // Move forward
                pos += 1;
            }
        }
    }

    let total_groups = *group_counter - 1;

    // If we only have one element and it's a single capture, return it directly
    if elements.len() == 1 {
        if let CaptureElement::Capture(ast, num) = &elements[0] {
            return Ok((Ast::Capture(Box::new(ast.clone()), *num), total_groups));
        }
    }

    // Build a PatternWithCaptures AST
    Ok((
        Ast::PatternWithCaptures {
            elements,
            total_groups,
        },
        *group_counter - start_group,
    ))
}

/// Element in a pattern with captures
#[derive(Debug, Clone, PartialEq)]
enum CaptureElement {
    Capture(Ast, usize), // (pattern), group_number
    NonCapture(Ast),     // literal or other pattern
}

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

    #[test]
    fn literal() {
        let p = Pattern::new("hello").unwrap();
        assert!(p.is_match("hello world"));
        assert!(!p.is_match("goodbye"));
    }

    #[test]
    fn alternation() {
        let p = Pattern::new("foo|bar|baz").unwrap();
        assert!(p.is_match("foo"));
        assert!(p.is_match("bar"));
        assert!(!p.is_match("qux"));
    }

    #[test]
    fn anchors() {
        let p = Pattern::new("^hello$").unwrap();
        assert!(p.is_match("hello"));
        assert!(!p.is_match("hello world"));
    }

    #[test]
    fn find_test() {
        let p = Pattern::new("world").unwrap();
        assert_eq!(p.find("hello world"), Some((6, 11)));
    }

    #[test]
    fn cached() {
        assert!(is_match("test", "this is a test").unwrap());
    }
}

#[test]
fn char_class_simple() {
    let p = Pattern::new("[abc]").unwrap();
    assert!(p.is_match("a"));
    assert!(p.is_match("apple"));
    assert!(p.is_match("cab"));
    assert!(!p.is_match("xyz"));
}

#[test]
fn char_class_range() {
    let p = Pattern::new("[a-z]").unwrap();
    assert!(p.is_match("hello"));
    assert!(p.is_match("xyz"));
    assert!(!p.is_match("HELLO"));
    assert!(!p.is_match("123"));
}

#[test]
fn char_class_multiple_ranges() {
    let p = Pattern::new("[a-zA-Z0-9]").unwrap();
    assert!(p.is_match("hello"));
    assert!(p.is_match("WORLD"));
    assert!(p.is_match("test123"));
    assert!(!p.is_match("!!!"));
}

#[test]
fn char_class_negated() {
    let p = Pattern::new("[^0-9]").unwrap();
    assert!(p.is_match("abc"));
    assert!(!p.is_match("123"));
    assert!(p.is_match("a1b")); // Contains non-digit
}

#[test]
fn char_class_find() {
    let p = Pattern::new("[0-9]").unwrap();
    assert_eq!(p.find("abc123"), Some((3, 4))); // Finds 1

    let matches = p.find_all("a1b2c3");
    assert_eq!(matches, vec![(1, 2), (3, 4), (5, 6)]);
}

#[test]
fn debug_parse_group() {
    let pattern = "(foo|bar)+";
    match parser::group::parse_group(pattern) {
        Ok((group, bytes_consumed)) => {
            eprintln!("bytes_consumed: {}", bytes_consumed);
            eprintln!("pattern.len(): {}", pattern.len());
            eprintln!("group: {:?}", group);
            assert_eq!(
                bytes_consumed,
                pattern.len(),
                "Group should consume entire pattern"
            );
        }
        Err(e) => {
            panic!("Error: {}", e);
        }
    }

    // Test actual matching
    eprintln!("\n--- Testing Pattern::new ---");
    let re = Pattern::new(pattern).unwrap();
    eprintln!("Pattern created: {:?}", re);
    eprintln!("is_match('foo'): {}", re.is_match("foo"));
    eprintln!("is_match('bar'): {}", re.is_match("bar"));
    eprintln!("is_match('foobar'): {}", re.is_match("foobar"));
}