guth 0.2.47

//! Bounded, case-insensitive search with offsets into the original preview text.

use std::ops::Range;

/// Keep search navigation and highlighted text layout responsive on large previews.
pub(crate) const FIND_MATCH_LIMIT: usize = 10_000;

#[derive(Clone, Debug, Eq, PartialEq)]
pub(crate) struct FindMatch {
    pub bytes: Range<usize>,
    pub chars: Range<usize>,
}

/// Find nonoverlapping matches using Unicode lowercase, not case folding or
/// normalization. Leading and trailing query whitespace is ignored.
///
/// A match within a lowercase expansion highlights the whole original scalar.
/// That scalar is consumed before searching again, so highlights never overlap.
/// Character offsets count Unicode scalar values, as egui's text cursors do.
pub(crate) fn find_matches(content: &str, query: &str) -> Vec<FindMatch> {
    let query = query.trim();
    if query.is_empty() || content.is_empty() {
        return Vec::new();
    }

    let query = query.to_lowercase();
    let lowercase = content.to_lowercase();

    if content.is_ascii() {
        return lowercase
            .match_indices(query.as_str())
            .take(FIND_MATCH_LIMIT)
            .map(|(start, matched)| {
                let range = start..start + matched.len();
                FindMatch {
                    bytes: range.clone(),
                    chars: range,
                }
            })
            .collect();
    }

    // Walk the original text only once, without allocating a mapping for every
    // byte or scalar. str::to_lowercase applies contextual final-sigma handling;
    // its sigma has the same UTF-8 length as char::to_lowercase's counterpart.
    let mut source = content.char_indices().enumerate();
    let mut lowercase_cursor = 0;
    let mut search_start = 0;
    let mut matches = Vec::new();

    while matches.len() < FIND_MATCH_LIMIT {
        let Some(relative_start) = lowercase[search_start..].find(query.as_str()) else {
            break;
        };
        let match_start = search_start + relative_start;
        let match_end = match_start + query.len();
        let mut source_start = None;
        let mut mapped_match = None;

        for (char_index, (byte_index, character)) in source.by_ref() {
            lowercase_cursor += character.to_lowercase().map(char::len_utf8).sum::<usize>();
            if lowercase_cursor <= match_start {
                continue;
            }

            let (byte_start, char_start) = *source_start.get_or_insert((byte_index, char_index));
            if lowercase_cursor >= match_end {
                mapped_match = Some(FindMatch {
                    bytes: byte_start..byte_index + character.len_utf8(),
                    chars: char_start..char_index + 1,
                });
                break;
            }
        }

        let Some(found) = mapped_match else {
            debug_assert!(false, "lowercase match must map to the original text");
            break;
        };
        matches.push(found);
        // Skip the rest of any expansion at the end of the match. Searching
        // from here also avoids losing later matches to an overlapping one.
        search_start = lowercase_cursor;
    }

    matches
}

/// Select the next/previous result, wrapping at either end. Missing or stale
/// indices begin at the first result when moving forward, or the last backward.
pub(crate) fn step_match(current: Option<usize>, len: usize, backwards: bool) -> Option<usize> {
    if len == 0 {
        return None;
    }
    let Some(current) = current.filter(|&index| index < len) else {
        return Some(if backwards { len - 1 } else { 0 });
    };
    Some(if backwards {
        if current == 0 {
            len - 1
        } else {
            current - 1
        }
    } else if current == len - 1 {
        0
    } else {
        current + 1
    })
}

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

    fn found(bytes: Range<usize>, chars: Range<usize>) -> FindMatch {
        FindMatch { bytes, chars }
    }

    #[test]
    fn ascii_matches_are_case_insensitive_and_nonoverlapping() {
        assert_eq!(
            find_matches("Alpha alpha ALPHA", "alpha"),
            vec![
                found(0..5, 0..5),
                found(6..11, 6..11),
                found(12..17, 12..17)
            ]
        );
        assert_eq!(
            find_matches("aaaaa", "AA"),
            vec![found(0..2, 0..2), found(2..4, 2..4)]
        );
    }

    #[test]
    fn empty_or_whitespace_query_has_no_matches() {
        assert!(find_matches("alpha", "").is_empty());
        assert!(find_matches("alpha", " \n\t\u{2003}").is_empty());
        assert!(find_matches("", "alpha").is_empty());
        assert!(find_matches("alpha", "omega").is_empty());
        assert_eq!(find_matches("alpha", "  ALPHA\n"), vec![found(0..5, 0..5)]);
    }

    #[test]
    fn unicode_ranges_use_original_bytes_and_scalar_indices() {
        assert_eq!(
            find_matches("🦀 Café CAFÉ café", "CAFÉ"),
            vec![
                found(5..10, 2..6),
                found(11..16, 7..11),
                found(17..22, 12..16)
            ]
        );
        // Kelvin sign lowercases to ASCII, even when the source is all ASCII.
        assert_eq!(
            find_matches("k K", "K"),
            vec![found(0..1, 0..1), found(2..3, 2..3)]
        );
        assert_eq!(
            find_matches("K k", "K"),
            vec![found(0..3, 0..1), found(4..5, 2..3)]
        );
    }

    #[test]
    fn lowercase_expansions_keep_original_scalar_boundaries() {
        let content = "İİ i\u{307}";
        assert_eq!(
            find_matches(content, "i"),
            vec![found(0..2, 0..1), found(2..4, 1..2), found(5..6, 3..4)]
        );
        assert_eq!(
            find_matches(content, "\u{307}"),
            vec![found(0..2, 0..1), found(2..4, 1..2), found(6..8, 4..5)]
        );
        assert_eq!(
            find_matches(content, "İ"),
            vec![found(0..2, 0..1), found(2..4, 1..2), found(5..8, 3..5)]
        );
    }

    #[test]
    fn expansion_crossing_matches_never_overlap_original_scalars() {
        assert_eq!(
            find_matches("İİİİİ", "\u{307}i"),
            vec![found(0..4, 0..2), found(4..8, 2..4)]
        );
        assert_eq!(
            find_matches("İiİi", "i\u{307}i"),
            vec![found(0..3, 0..2), found(3..6, 2..4)]
        );
    }

    #[test]
    fn preserves_contextual_lowercase_without_full_casefold_or_normalization() {
        assert_eq!(
            find_matches("ΟΣ ΟΣΑ ος οσα", "ΟΣ"),
            vec![found(0..4, 0..2), found(12..16, 7..9)]
        );
        assert_eq!(
            find_matches("Straße STRASSE", "strasse"),
            vec![found(8..15, 7..14)]
        );
        assert_eq!(find_matches("é e\u{301}", "é"), vec![found(0..2, 0..1)]);
    }

    #[test]
    fn matches_across_newlines_and_retains_blank_line_offsets() {
        assert_eq!(
            find_matches("α\n\nBeta\nGAMMA\nβ", "beta\ngamma"),
            vec![found(4..14, 3..13)]
        );
        assert_eq!(
            find_matches("a\nb\na\nb", "a\nb"),
            vec![found(0..3, 0..3), found(4..7, 4..7)]
        );
    }

    #[test]
    fn ascii_and_unicode_results_stop_at_the_navigation_limit() {
        for (content, query, byte_width) in [
            ("A".repeat(FIND_MATCH_LIMIT + 7), "a", 1),
            ("İ".repeat(FIND_MATCH_LIMIT + 7), "i", 2),
        ] {
            let matches = find_matches(&content, query);
            assert_eq!(matches.len(), FIND_MATCH_LIMIT);
            assert_eq!(
                matches.last(),
                Some(&found(
                    (FIND_MATCH_LIMIT - 1) * byte_width..FIND_MATCH_LIMIT * byte_width,
                    FIND_MATCH_LIMIT - 1..FIND_MATCH_LIMIT
                ))
            );
        }
    }

    #[test]
    fn next_and_previous_wrap_and_handle_missing_or_stale_indices() {
        assert_eq!(step_match(None, 0, false), None);
        assert_eq!(step_match(Some(0), 0, true), None);
        assert_eq!(step_match(None, 3, false), Some(0));
        assert_eq!(step_match(None, 3, true), Some(2));
        assert_eq!(step_match(Some(0), 3, false), Some(1));
        assert_eq!(step_match(Some(1), 3, true), Some(0));
        assert_eq!(step_match(Some(2), 3, false), Some(0));
        assert_eq!(step_match(Some(0), 3, true), Some(2));
        assert_eq!(step_match(Some(3), 3, false), Some(0));
        assert_eq!(step_match(Some(usize::MAX), 3, true), Some(2));
        assert_eq!(step_match(Some(0), 1, false), Some(0));
        assert_eq!(step_match(Some(0), 1, true), Some(0));
        assert_eq!(step_match(Some(usize::MAX - 1), usize::MAX, false), Some(0));
    }
}