rexile 0.5.7

use crate::parser::quantifier::Quantifier;
/// Group support for regex patterns
///
/// Supports:
/// - Simple groups: (abc)
/// - Non-capturing groups: (?:abc)
/// - Alternation in groups: (a|b|c)
/// - Quantified groups: (abc)+
use crate::parser::sequence::Sequence;
use crate::parser::sequence_parser::{is_sequence_pattern, parse_sequence};

/// A group in a pattern
#[derive(Debug, Clone, PartialEq)]
pub struct Group {
    /// The content of the group (can be alternation or sequence)
    pub content: GroupContent,
    /// Whether this is a capturing group
    pub capturing: bool,
    /// Optional quantifier on the group
    pub quantifier: Option<Quantifier>,
}

/// Content inside a group
#[derive(Debug, Clone, PartialEq)]
pub enum GroupContent {
    /// Single pattern (like "abc" in (abc))
    Single(String),
    /// Alternation (like "a|b|c" in (a|b|c))
    Alternation(Vec<String>),
    /// Nested sequence
    Sequence(Sequence),
    /// Alternation with parsed sequences (for complex alternatives like "[a-z]+|\d+")
    ParsedAlternation(Vec<Sequence>),
}

impl Group {
    /// Create a new capturing group
    pub fn new_capturing(content: GroupContent) -> Self {
        Group {
            content,
            capturing: true,
            quantifier: None,
        }
    }

    /// Create a new non-capturing group
    pub fn new_non_capturing(content: GroupContent) -> Self {
        Group {
            content,
            capturing: false,
            quantifier: None,
        }
    }

    /// Add a quantifier to this group
    pub fn with_quantifier(mut self, quantifier: Quantifier) -> Self {
        self.quantifier = Some(quantifier);
        self
    }

    /// Check if text matches this group at a given position
    /// Returns bytes consumed if match
    pub fn match_at(&self, text: &str, pos: usize) -> Option<usize> {
        let base_consumed = self.match_base_at(text, pos)?;

        // Apply quantifier if present
        if let Some(quantifier) = &self.quantifier {
            self.match_with_quantifier(text, pos, base_consumed, quantifier)
        } else {
            Some(base_consumed)
        }
    }

    /// Match group base pattern (without quantifier) at position
    fn match_base_at(&self, text: &str, pos: usize) -> Option<usize> {
        let remaining = &text[pos..];

        match &self.content {
            GroupContent::Single(pattern) => {
                if remaining.starts_with(pattern) {
                    Some(pattern.len())
                } else {
                    None
                }
            }
            GroupContent::Alternation(patterns) => {
                // Try each alternative
                for pattern in patterns {
                    if remaining.starts_with(pattern) {
                        return Some(pattern.len());
                    }
                }
                None
            }
            GroupContent::Sequence(seq) => seq.match_at(remaining),
            GroupContent::ParsedAlternation(sequences) => {
                // Try each alternative sequence (leftmost first)
                for seq in sequences {
                    if let Some(consumed) = seq.match_at(remaining) {
                        return Some(consumed);
                    }
                }
                None
            }
        }
    }

    /// Match group with quantifier
    fn match_with_quantifier(
        &self,
        text: &str,
        start_pos: usize,
        _base_match_size: usize,
        quantifier: &Quantifier,
    ) -> Option<usize> {
        let (min, max) = quantifier_bounds(quantifier);

        let mut total_consumed = 0;
        let mut count = 0;
        let mut pos = start_pos;

        // Greedy: match as many times as possible
        while count < max {
            match self.match_base_at(text, pos) {
                Some(consumed) if consumed > 0 => {
                    total_consumed += consumed;
                    pos += consumed;
                    count += 1;
                }
                _ => break,
            }
        }

        if count >= min {
            Some(total_consumed)
        } else {
            None
        }
    }

    /// Check if group matches anywhere in text (optimized)
    /// Returns immediately on first match without computing position
    pub fn is_match(&self, text: &str) -> bool {
        // Fast path: Try match at start first
        if self.match_at(text, 0).is_some() {
            return true;
        }

        // Only scan forward if no match at start
        let byte_positions: Vec<usize> = text.char_indices().map(|(i, _)| i).collect();

        for &start_pos in &byte_positions {
            if start_pos == 0 {
                continue; // Already tried
            }
            if self.match_at(text, start_pos).is_some() {
                return true; // Early termination!
            }
        }

        false
    }

    /// Find the group pattern anywhere in text
    pub fn find(&self, text: &str) -> Option<(usize, usize)> {
        // OPTIMIZATION: For alternation groups with common prefix, use prefix search
        if let GroupContent::Alternation(alternatives) = &self.content {
            if let Some(prefix) = find_common_prefix(alternatives) {
                if prefix.len() >= 3 {
                    // Only worthwhile for longer prefixes
                    // Use memchr to find prefix quickly
                    use memchr::memmem;
                    let mut search_pos = 0;

                    while let Some(found) =
                        memmem::find(&text.as_bytes()[search_pos..], prefix.as_bytes())
                    {
                        let abs_pos = search_pos + found;

                        // Try to match the full pattern at this position
                        if let Some(consumed) = self.match_at(text, abs_pos) {
                            return Some((abs_pos, abs_pos + consumed));
                        }

                        search_pos = abs_pos + 1;
                    }

                    return None;
                }
            }
        }

        // Fallback: Original sequential search
        let byte_positions: Vec<usize> = text.char_indices().map(|(i, _)| i).collect();

        for &start_pos in &byte_positions {
            if let Some(consumed) = self.match_at(text, start_pos) {
                return Some((start_pos, start_pos + consumed));
            }
        }

        None
    }

    /// Find all occurrences of the group in text
    pub fn find_all(&self, text: &str) -> Vec<(usize, usize)> {
        let mut results = Vec::new();
        let byte_positions: Vec<usize> = text.char_indices().map(|(i, _)| i).collect();

        let mut i = 0;
        while i < byte_positions.len() {
            let start_pos = byte_positions[i];

            if let Some(consumed) = self.match_at(text, start_pos) {
                let end_pos = start_pos + consumed;
                results.push((start_pos, end_pos));

                // Skip past this match
                while i < byte_positions.len() && byte_positions[i] < end_pos {
                    i += 1;
                }
            } else {
                i += 1;
            }
        }

        results
    }
}

/// Find common prefix among alternation alternatives
fn find_common_prefix(alternatives: &[String]) -> Option<String> {
    if alternatives.is_empty() {
        return None;
    }

    let first = &alternatives[0];
    let mut prefix_len = first.len();

    for alt in &alternatives[1..] {
        let common = first
            .chars()
            .zip(alt.chars())
            .take_while(|(a, b)| a == b)
            .count();
        prefix_len = prefix_len.min(common);

        if prefix_len == 0 {
            return None;
        }
    }

    if prefix_len > 0 {
        Some(first.chars().take(prefix_len).collect())
    } else {
        None
    }
}

fn quantifier_bounds(q: &Quantifier) -> (usize, usize) {
    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),
    }
}

/// Parse a group from a pattern string
/// Returns (Group, bytes_consumed)
pub fn parse_group(pattern: &str) -> Result<(Group, usize), String> {
    if !pattern.starts_with('(') {
        return Err("Pattern must start with '('".to_string());
    }

    // Find matching closing paren
    let mut depth = 0;
    let mut close_idx = None;

    for (i, ch) in pattern.char_indices() {
        if ch == '(' {
            depth += 1;
        } else if ch == ')' {
            depth -= 1;
            if depth == 0 {
                close_idx = Some(i);
                break;
            }
        }
    }

    let close_idx = close_idx.ok_or("Unclosed group")?;

    // Extract group content
    let group_str = &pattern[1..close_idx];

    // Check if non-capturing group
    let (is_capturing, content_str) = if group_str.starts_with("?:") {
        (false, &group_str[2..])
    } else {
        (true, group_str)
    };

    // Parse group content
    let content = if content_str.contains('|') {
        // Alternation - check if each alternative is a sequence
        let parts: Vec<String> = content_str.split('|').map(|s| s.to_string()).collect();

        // Check if any part is a sequence pattern
        let has_sequences = parts
            .iter()
            .any(|p| is_sequence_pattern(p) || has_quantified_element(p));

        if has_sequences {
            // Parse each alternative as a potential sequence
            // For now, store as alternation of strings
            // TODO: Support sequences in alternation
            GroupContent::Alternation(parts)
        } else {
            GroupContent::Alternation(parts)
        }
    } else if is_sequence_pattern(content_str) || has_quantified_element(content_str) {
        // Sequence pattern like \d+, [a-z]+, ab+c*, or single quantified element
        match parse_sequence(content_str) {
            Ok(seq) => GroupContent::Sequence(seq),
            Err(_) => GroupContent::Single(content_str.to_string()),
        }
    } else {
        // Single literal pattern
        GroupContent::Single(content_str.to_string())
    };

    let group = if is_capturing {
        Group::new_capturing(content)
    } else {
        Group::new_non_capturing(content)
    };

    let mut bytes_consumed = close_idx + 1;

    // Check for quantifier after group
    if bytes_consumed < pattern.len() {
        let remaining = &pattern[bytes_consumed..];
        let (quantifier_opt, qlen) = parse_quantifier_with_lazy(remaining);
        if let Some(quantifier) = quantifier_opt {
            bytes_consumed += qlen;
            return Ok((group.with_quantifier(quantifier), bytes_consumed));
        }
    }

    Ok((group, bytes_consumed))
}

/// Parse quantifier including lazy variants (*, +, ?, *?, +?, ??)
/// Returns (Option<Quantifier>, bytes_consumed)
fn parse_quantifier_with_lazy(remaining: &str) -> (Option<Quantifier>, usize) {
    let chars: Vec<char> = remaining.chars().take(2).collect();
    if chars.is_empty() {
        return (None, 0);
    }

    let first = chars[0];
    let has_lazy = chars.len() > 1 && chars[1] == '?';

    match first {
        '*' if has_lazy => (Some(Quantifier::ZeroOrMoreLazy), 2),
        '*' => (Some(Quantifier::ZeroOrMore), 1),
        '+' if has_lazy => (Some(Quantifier::OneOrMoreLazy), 2),
        '+' => (Some(Quantifier::OneOrMore), 1),
        '?' if has_lazy => (Some(Quantifier::ZeroOrOneLazy), 2),
        '?' => (Some(Quantifier::ZeroOrOne), 1),
        _ => (None, 0),
    }
}

/// Check if pattern has quantified elements like \d+, [a-z]*, etc.
fn has_quantified_element(pattern: &str) -> bool {
    let chars: Vec<char> = pattern.chars().collect();
    let mut i = 0;

    while i < chars.len() {
        if chars[i] == '\\' && i + 1 < chars.len() {
            // Escape sequence - check for quantifier after
            i += 2;
            if i < chars.len() && matches!(chars[i], '*' | '+' | '?') {
                return true;
            }
        } else if chars[i] == '[' {
            // Character class - find end and check for quantifier
            while i < chars.len() && chars[i] != ']' {
                i += 1;
            }
            i += 1; // Skip ']'
            if i < chars.len() && matches!(chars[i], '*' | '+' | '?') {
                return true;
            }
        } else {
            i += 1;
        }
    }
    false
}

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

    #[test]
    fn test_parse_simple_group() {
        let (group, len) = parse_group("(abc)").unwrap();
        assert_eq!(len, 5);
        assert!(group.capturing);
        assert!(group.quantifier.is_none());
    }

    #[test]
    fn test_parse_non_capturing() {
        let (group, len) = parse_group("(?:abc)").unwrap();
        assert_eq!(len, 7);
        assert!(!group.capturing);
    }

    #[test]
    fn test_parse_alternation() {
        let (group, _) = parse_group("(a|b|c)").unwrap();
        match group.content {
            GroupContent::Alternation(parts) => {
                assert_eq!(parts.len(), 3);
                assert_eq!(parts, vec!["a", "b", "c"]);
            }
            _ => panic!("Expected alternation"),
        }
    }

    #[test]
    fn test_parse_quantified_group() {
        let (group, len) = parse_group("(abc)+").unwrap();
        assert_eq!(len, 6);
        assert!(group.quantifier.is_some());
    }

    #[test]
    fn test_match_simple() {
        let group = Group::new_capturing(GroupContent::Single("abc".to_string()));
        assert_eq!(group.match_at("abc", 0), Some(3));
        assert_eq!(group.match_at("xyzabc", 3), Some(3));
        assert_eq!(group.match_at("xyz", 0), None);
    }

    #[test]
    fn test_match_alternation() {
        let group = Group::new_capturing(GroupContent::Alternation(vec![
            "foo".to_string(),
            "bar".to_string(),
        ]));

        assert_eq!(group.match_at("foo", 0), Some(3));
        assert_eq!(group.match_at("bar", 0), Some(3));
        assert_eq!(group.match_at("baz", 0), None);
    }

    #[test]
    fn test_find() {
        let group = Group::new_capturing(GroupContent::Single("abc".to_string()));
        assert_eq!(group.find("xyzabcdef"), Some((3, 6)));
    }

    #[test]
    fn test_find_all() {
        let group = Group::new_capturing(GroupContent::Single("ab".to_string()));
        let matches = group.find_all("ab cd ab ef ab");
        assert_eq!(matches, vec![(0, 2), (6, 8), (12, 14)]);
    }
}