ported/text_more

fn is_word_char(ch: char) -> bool {
    // Fn3 retains Mn and Pc membership; the PCRE2 pattern specification describes
    // these additions to Unicode word characters. Keep one predicate for boundaries too.
    ch.is_alphanumeric()
        || calc_value::is_nonspacing_mark(ch)
        || calc_value::is_connector_punctuation(ch)
}

fn chars_equal(lhs: char, rhs: char, case_sensitive: bool) -> bool {
    if case_sensitive {
        lhs == rhs
    } else {
        calc_value::unicode_simple_case_fold(lhs) == calc_value::unicode_simple_case_fold(rhs)
    }
}

fn range_contains(ch: char, start: char, end: char, folded: &Option<Vec<char>>, case_sensitive: bool) -> bool {
    if case_sensitive {
        ch >= start && ch <= end
    } else {
        folded.as_ref().is_some_and(|range|
            range.binary_search(&calc_value::unicode_simple_case_fold(ch)).is_ok())
    }
}

fn folded_range(start: char, end: char) -> Option<Vec<char>> {
    if end < start || end as u32 - start as u32 > 4096 {
        return None;
    }
    let mut folded: Vec<_> = (start as u32..=end as u32)
        .filter_map(char::from_u32)
        .map(calc_value::unicode_simple_case_fold)
        .collect();
    folded.sort_unstable();
    folded.dedup();
    Some(folded)
}

fn class_item_matches(item: &RegexClassItem, ch: char, case_sensitive: bool) -> bool {
    match item {
        RegexClassItem::Single(expected) => chars_equal(ch, *expected, case_sensitive),
        RegexClassItem::Range(start, end, folded) => range_contains(ch, *start, *end, folded, case_sensitive),
        RegexClassItem::Digit => ch.is_ascii_digit(),
        RegexClassItem::Word => is_word_char(ch),
        RegexClassItem::Space => ch.is_whitespace(),
        RegexClassItem::HorizontalSpace => ch == ' ' || ch == '\t',
    }
}

fn is_word_boundary(chars: &[char], position: usize) -> bool {
    let before = position
        .checked_sub(1)
        .and_then(|index| chars.get(index))
        .copied()
        .is_some_and(is_word_char);
    let after = chars.get(position).copied().is_some_and(is_word_char);
    before != after
}

fn zero_width_atom_matches(atom: &RegexAtom, chars: &[char], position: usize) -> Option<bool> {
    Some(match atom {
        RegexAtom::StartOfText => position == 0,
        RegexAtom::EndOfText => position == chars.len(),
        RegexAtom::WordBoundary => is_word_boundary(chars, position),
        RegexAtom::NotWordBoundary => !is_word_boundary(chars, position),
        _ => return None,
    })
}

fn atom_consumes_input(atom: &RegexAtom) -> bool {
    !matches!(
        atom,
        RegexAtom::StartOfText
            | RegexAtom::EndOfText
            | RegexAtom::WordBoundary
            | RegexAtom::NotWordBoundary
    )
}

fn consuming_atom_matches(atom: &RegexAtom, ch: char, case_sensitive: bool) -> bool {
    match atom {
        RegexAtom::Literal(expected) => chars_equal(ch, *expected, case_sensitive),
        RegexAtom::Any => ch != '\n' && ch != '\r',
        RegexAtom::Digit => ch.is_ascii_digit(),
        RegexAtom::NotDigit => !ch.is_ascii_digit(),
        RegexAtom::Word => is_word_char(ch),
        RegexAtom::NotWord => !is_word_char(ch),
        RegexAtom::Space => ch.is_whitespace(),
        RegexAtom::NotSpace => !ch.is_whitespace(),
        RegexAtom::HorizontalSpace => ch == ' ' || ch == '\t',
        RegexAtom::Class(class) => {
            let found = class
                .items
                .iter()
                .any(|item| class_item_matches(item, ch, case_sensitive));
            if class.negated { !found } else { found }
        }
        RegexAtom::StartOfText
        | RegexAtom::EndOfText
        | RegexAtom::WordBoundary
        | RegexAtom::NotWordBoundary => false,
    }
}

fn match_atom_once(
    token: &RegexToken,
    chars: &[char],
    position: usize,
    case_sensitive: bool,
) -> Option<usize> {
    if let Some(matches) = zero_width_atom_matches(&token.atom, chars, position) {
        return matches.then_some(position);
    }
    let ch = *chars.get(position)?;
    if consuming_atom_matches(&token.atom, ch, case_sensitive) {
        Some(position + 1)
    } else {
        None
    }
}

fn match_tokens_from(
    tokens: &[RegexToken],
    token_index: usize,
    chars: &[char],
    position: usize,
    case_sensitive: bool,
) -> Option<usize> {
    if token_index >= tokens.len() {
        return Some(position);
    }

    let token = &tokens[token_index];
    match token.quantifier {
        RegexQuantifier::One => {
            match_atom_once(token, chars, position, case_sensitive).and_then(|next| {
                match_tokens_from(tokens, token_index + 1, chars, next, case_sensitive)
            })
        }
        RegexQuantifier::ZeroOrOne => {
            if let Some(next) =
                match_atom_once(token, chars, position, case_sensitive).and_then(|next| {
                    match_tokens_from(tokens, token_index + 1, chars, next, case_sensitive)
                })
            {
                return Some(next);
            }
            match_tokens_from(tokens, token_index + 1, chars, position, case_sensitive)
        }
        RegexQuantifier::ZeroOrMore | RegexQuantifier::OneOrMore => {
            let minimum = if matches!(token.quantifier, RegexQuantifier::OneOrMore) {
                1usize
            } else {
                0usize
            };
            let mut positions = vec![position];
            let mut cursor = position;
            while let Some(next) = match_atom_once(token, chars, cursor, case_sensitive) {
                positions.push(next);
                cursor = next;
            }
            if positions.len().saturating_sub(1) < minimum {
                return None;
            }
            for count in (minimum..positions.len()).rev() {
                if let Some(end) = match_tokens_from(
                    tokens,
                    token_index + 1,
                    chars,
                    positions[count],
                    case_sensitive,
                ) {
                    return Some(end);
                }
            }
            None
        }
    }
}

fn find_first_match_from(
    chars: &[char],
    tokens: &[RegexToken],
    start_index: usize,
    case_sensitive: bool,
) -> Option<(usize, usize)> {
    for start in start_index..=chars.len() {
        if let Some(end) = match_tokens_from(tokens, 0, chars, start, case_sensitive) {
            if end >= start {
                return Some((start, end));
            }
        }
    }
    None
}

fn find_all_matches(
    chars: &[char],
    tokens: &[RegexToken],
    case_sensitive: bool,
) -> Vec<(usize, usize)> {
    let mut matches = Vec::new();
    let mut cursor = 0usize;
    while cursor <= chars.len() {
        let Some((start, end)) = find_first_match_from(chars, tokens, cursor, case_sensitive)
        else {
            break;
        };
        matches.push((start, end));
        cursor = end.max(start + 1);
    }
    matches
}

fn escaped_literal_char(ch: char) -> Option<char> {
    Some(match ch {
        'n' => '\n',
        't' => '\t',
        'r' => '\r',
        'f' => '\u{000c}',
        'v' => '\u{000b}',
        'e' => '\u{001b}',
        '\\' | '.' | '*' | '+' | '?' | '[' | ']' | '(' | ')' | '|' | '^' | '$' | '/' => ch,
        _ => return None,
    })
}

fn parse_escape_atom(chars: &[char], index: &mut usize) -> Result<RegexAtom, Unsupported> {
    let Some(ch) = chars.get(*index).copied() else {
        return Err(Unsupported);
    };
    *index += 1;
    Ok(match ch {
        'd' => RegexAtom::Digit,
        'D' => RegexAtom::NotDigit,
        'w' => RegexAtom::Word,
        'W' => RegexAtom::NotWord,
        's' => RegexAtom::Space,
        'S' => RegexAtom::NotSpace,
        'h' => RegexAtom::HorizontalSpace,
        'A' => RegexAtom::StartOfText,
        'Z' | 'z' => RegexAtom::EndOfText,
        'b' => RegexAtom::WordBoundary,
        'B' => RegexAtom::NotWordBoundary,
        ch => {
            let Some(literal) = escaped_literal_char(ch) else {
                // Any other escape sequence is not part of the admitted slice; produce #VALUE!
                // so the caller gets a hard error rather than a silently wrong literal match.
                return Err(Unsupported);
            };
            RegexAtom::Literal(literal)
        }
    })
}

fn parse_class_piece(
    chars: &[char],
    index: &mut usize,
) -> Result<RegexClassPiece, Unsupported> {
    let Some(ch) = chars.get(*index).copied() else {
        return Err(Unsupported);
    };
    if ch == '\\' {
        *index += 1;
        let Some(escaped) = chars.get(*index).copied() else {
            return Err(Unsupported);
        };
        *index += 1;
        return match escaped {
            'd' => Ok(RegexClassPiece::Digit),
            'w' => Ok(RegexClassPiece::Word),
            's' => Ok(RegexClassPiece::Space),
            'h' => Ok(RegexClassPiece::HorizontalSpace),
            // Negated shorthands are not supported inside character classes.
            'D' | 'W' | 'S' => Err(Unsupported),
            '-' => Ok(RegexClassPiece::Literal('-')),
            ch => {
                let Some(literal) = escaped_literal_char(ch) else {
                    // Unrecognized escape inside a character class: hard error, not silent literal.
                    return Err(Unsupported);
                };
                Ok(RegexClassPiece::Literal(literal))
            }
        };
    }
    *index += 1;
    Ok(RegexClassPiece::Literal(ch))
}

fn parse_char_class(chars: &[char], index: &mut usize) -> Result<RegexAtom, Unsupported> {
    let mut negated = false;
    if matches!(chars.get(*index), Some('^')) {
        negated = true;
        *index += 1;
    }

    let mut pieces = Vec::new();
    while let Some(ch) = chars.get(*index).copied() {
        if ch == ']' {
            break;
        }
        pieces.push(parse_class_piece(chars, index)?);
    }

    if !matches!(chars.get(*index), Some(']')) || pieces.is_empty() {
        return Err(Unsupported);
    }
    *index += 1;

    let mut items = Vec::new();
    let mut i = 0usize;
    while i < pieces.len() {
        if i + 2 < pieces.len() {
            if let (
                RegexClassPiece::Literal(start),
                RegexClassPiece::Literal('-'),
                RegexClassPiece::Literal(end),
            ) = (&pieces[i], &pieces[i + 1], &pieces[i + 2])
            {
                items.push(RegexClassItem::Range(*start, *end, folded_range(*start, *end)));
                i += 3;
                continue;
            }
        }
        match &pieces[i] {
            RegexClassPiece::Literal(ch) => items.push(RegexClassItem::Single(*ch)),
            RegexClassPiece::Digit => items.push(RegexClassItem::Digit),
            RegexClassPiece::Word => items.push(RegexClassItem::Word),
            RegexClassPiece::Space => items.push(RegexClassItem::Space),
            RegexClassPiece::HorizontalSpace => items.push(RegexClassItem::HorizontalSpace),
        }
        i += 1;
    }

    Ok(RegexAtom::Class(RegexClass { negated, items }))
}

fn parse_regex_pattern(pattern: &str) -> Result<Vec<RegexToken>, Unsupported> {
    let chars: Vec<char> = pattern.chars().collect();
    if chars.is_empty() {
        return Err(Unsupported);
    }

    let mut tokens = Vec::new();
    let mut index = 0usize;
    while let Some(ch) = chars.get(index).copied() {
        let atom = match ch {
            '.' => {
                index += 1;
                RegexAtom::Any
            }
            '\\' => {
                index += 1;
                parse_escape_atom(&chars, &mut index)?
            }
            '[' => {
                index += 1;
                parse_char_class(&chars, &mut index)?
            }
            '*' | '+' | '?' | '(' | ')' | '{' | '}' | '|' | '^' | '$' => {
                return Err(Unsupported);
            }
            other => {
                index += 1;
                RegexAtom::Literal(other)
            }
        };

        let quantifier = match chars.get(index).copied() {
            Some('*') => {
                index += 1;
                RegexQuantifier::ZeroOrMore
            }
            Some('+') => {
                index += 1;
                RegexQuantifier::OneOrMore
            }
            Some('?') => {
                index += 1;
                RegexQuantifier::ZeroOrOne
            }
            _ => RegexQuantifier::One,
        };

        if !atom_consumes_input(&atom) && quantifier != RegexQuantifier::One {
            return Err(Unsupported);
        }

        tokens.push(RegexToken { atom, quantifier });
    }

    if tokens.is_empty() {
        return Err(Unsupported);
    }
    Ok(tokens)
}

/// The matches' character positions, for REGEXEXTRACT, REGEXTEST and REGEXREPLACE.
pub(crate) fn regex_matches(
    text: &str,
    pattern: &str,
    case_sensitive: bool,
    first_only: bool,
) -> Result<(Vec<char>, Vec<(usize, usize)>), Unsupported> {
    let haystack: Vec<char> = text.chars().collect();
    let tokens = parse_regex_pattern(pattern)?;
    // The fn3 readings admit Unicode range closure through the same simple fold as
    // literals. A range beyond the bounded table remains a typed refusal.
    if !case_sensitive && tokens.iter().any(|token| match &token.atom {
        RegexAtom::Class(class) => class.items.iter().any(|item| {
            matches!(item, RegexClassItem::Range(_, _, None))
        }),
        _ => false,
    }) {
        return Err(Unsupported);
    }
    let found = if first_only {
        find_first_match_from(&haystack, &tokens, 0, case_sensitive)
            .into_iter()
            .collect()
    } else {
        find_all_matches(&haystack, &tokens, case_sensitive)
    };
    Ok((haystack, found))
}

fn fold_ascii_case(unit: u16) -> u16 {
    if (b'A' as u16..=b'Z' as u16).contains(&unit) {
        unit + 32
    } else {
        unit
    }
}

fn units_match(left: &[u16], right: &[u16], case_insensitive: bool) -> bool {
    left.len() == right.len()
        && left.iter().zip(right).all(|(l, r)| {
            if case_insensitive {
                fold_ascii_case(*l) == fold_ascii_case(*r)
            } else {
                l == r
            }
        })
}

/// TEXTBEFORE or TEXTAFTER over any of `delimiters` (the first found at each position).
pub(crate) fn delimited(
    side: Side,
    text: &ExcelText,
    delimiters: &[ExcelText],
    instance: isize,
    case_insensitive: bool,
    match_end: bool,
) -> Delimited {
    let requested = instance.unsigned_abs();
    // The first search of empty text is still a valid search, with no delimiter to find.
    // Excel 16.0.20430: TEXTBEFORE("","-") and TEXTAFTER("","-") are #N/A (the
    // recorded typed Value2 cases w111typed-00274 and w111typed-00266, dc-zsn.7).
    if instance == 0 || requested > text.len_utf16_code_units().max(1) {
        return Delimited::BadInstance;
    }
    let units = text.utf16_code_units();
    if delimiters.iter().any(|d| d.utf16_code_units().is_empty()) {
        let whole = match (side, instance < 0) {
            (Side::After, false) | (Side::Before, true) => text.clone(),
            _ => ExcelText::from_utf16_code_units(Vec::new()),
        };
        return Delimited::Text(whole);
    }
    // The boundaries: (start, length) of each delimiter found, left to right, not overlapping.
    let mut boundaries = Vec::new();
    let mut at = 0usize;
    while at < units.len() {
        let found = delimiters.iter().find_map(|delimiter| {
            let needle = delimiter.utf16_code_units();
            (at + needle.len() <= units.len()
                && units_match(&units[at..at + needle.len()], needle, case_insensitive))
            .then_some(needle.len())
        });
        match found {
            Some(length) => {
                boundaries.push((at, length));
                at += length;
            }
            None => at += 1,
        }
    }
    if match_end {
        if instance < 0 {
            boundaries.insert(0, (0, 0));
        } else {
            boundaries.push((units.len(), 0));
        }
    }
    let selected = if instance < 0 {
        boundaries
            .len()
            .checked_sub(requested)
            .and_then(|index| boundaries.get(index))
    } else {
        boundaries.get(requested - 1)
    };
    match selected {
        Some(&(start, length)) => Delimited::Text(ExcelText::from_utf16_code_units(match side {
            Side::Before => units[..start].to_vec(),
            Side::After => units[start + length..].to_vec(),
        })),
        None => Delimited::NotFound,
    }
}

/// A worksheet error's literal, as ARRAYTOTEXT and VALUETOTEXT write it.
pub(crate) fn error_literal(code: WorksheetErrorCode) -> &'static str {
    match code {
        WorksheetErrorCode::Null => "#NULL!",
        WorksheetErrorCode::Div0 => "#DIV/0!",
        WorksheetErrorCode::Value => "#VALUE!",
        WorksheetErrorCode::Ref => "#REF!",
        WorksheetErrorCode::Name => "#NAME?",
        WorksheetErrorCode::Num => "#NUM!",
        WorksheetErrorCode::NA => "#N/A",
        WorksheetErrorCode::Busy => "#BUSY!",
        WorksheetErrorCode::GettingData => "#GETTING_DATA",
        WorksheetErrorCode::Spill => "#SPILL!",
        WorksheetErrorCode::Calc => "#CALC!",
        WorksheetErrorCode::Field => "#FIELD!",
        WorksheetErrorCode::Blocked => "#BLOCKED!",
        WorksheetErrorCode::Connect => "#CONNECT!",
    }
}