datui_lib/home/

fuzzy.rs

//! Fuzzy matching scored as fzf scores it, so ranking matches the finder people already
//! know (`fzf`, `fzf-lua`, Telescope's fzf-native and `snacks.picker`, a port of
//! `fzf/src/algo/algo.go`, all agree). The scoring constants are fzf's:
//!
//! - a match right after `/` or `_` beats one mid-word
//! - consecutive characters beat scattered ones
//! - a match in the file name beats one in a directory
//! - the best alignment wins, not the first found (`revdetail` lands on `revenue`, not
//!   the `re` in `warehouse`)

/// Character classes, which is how fzf decides what counts as a boundary.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
enum Class {
    White = 0,
    NonWord = 1,
    Delimiter = 2,
    Lower = 3,
    Upper = 4,
    Number = 5,
}

// fzf's constants, unchanged. They are a calibrated set rather than independent
// knobs: the consecutive bonus is exactly what cancels a one-character gap, so
// "abc" and "a-b-c" differ by the boundary bonuses alone.
const SCORE_MATCH: i32 = 16;
const SCORE_GAP_START: i32 = -3;
const SCORE_GAP_EXTENSION: i32 = -1;
const BONUS_BOUNDARY: i32 = SCORE_MATCH / 2;
const BONUS_NON_WORD: i32 = SCORE_MATCH / 2;
const BONUS_CAMEL_123: i32 = BONUS_BOUNDARY - 1;
const BONUS_CONSECUTIVE: i32 = -(SCORE_GAP_START + SCORE_GAP_EXTENSION);
const BONUS_FIRST_CHAR_MULTIPLIER: i32 = 2;
/// Start-of-string and whitespace boundaries: fzf's path scheme value, not its
/// default's `+ 2`, so a match after `/` outranks one at the start (every haystack here
/// is a path; `report` should prefer `archive/old/report.csv`).
const BONUS_BOUNDARY_WHITE: i32 = BONUS_BOUNDARY;
const BONUS_BOUNDARY_DELIMITER: i32 = BONUS_BOUNDARY + 1;

/// Awarded when no path separator follows the match start (it landed in the file
/// name): fzf's `--scheme=path`, so `sales` finds `archive/old/sales.csv` over
/// `sales/2024/report.csv`.
const BONUS_FILENAME: i32 = BONUS_BOUNDARY - 2;

/// Added when the needle is the whole haystack, ignoring case. Not fzf's: it ranks an
/// exact name above the other matches, as no alignment of a name-length needle gains
/// this much over another.
const EXACT_BONUS: i32 = 1_000;

/// Where a needle sits in a name, for a list narrowed by substring: the whole name
/// (0), its start (1), or inside it (2). `None` when the name does not contain it.
/// Case-insensitive; an empty needle is inside every name.
pub fn substring_rank(needle: &str, haystack: &str) -> Option<u8> {
    let needle = needle.to_lowercase();
    let hay = haystack.to_lowercase();
    if needle.is_empty() {
        Some(2)
    } else if hay == needle {
        Some(0)
    } else if hay.starts_with(&needle) {
        Some(1)
    } else {
        hay.contains(&needle).then_some(2)
    }
}

fn class_of(c: char) -> Class {
    if c.is_whitespace() {
        Class::White
    } else if matches!(c, '/' | '\\' | ',' | ':' | ';' | '|') {
        Class::Delimiter
    } else if c.is_ascii_digit() {
        Class::Number
    } else if c.is_uppercase() {
        Class::Upper
    } else if c.is_lowercase() || c.is_alphabetic() {
        Class::Lower
    } else {
        Class::NonWord
    }
}

/// The bonus for matching a character of class `curr` when the one before it was
/// `prev`. This is where "start of a word" is expressed.
fn bonus_for(prev: Class, curr: Class) -> i32 {
    if curr > Class::NonWord {
        match prev {
            Class::White => return BONUS_BOUNDARY_WHITE,
            Class::Delimiter => return BONUS_BOUNDARY_DELIMITER,
            Class::NonWord => return BONUS_BOUNDARY,
            _ => {}
        }
    }
    // camelCase, and the digit that starts a run of them.
    if (prev == Class::Lower && curr == Class::Upper)
        || (prev != Class::Number && curr == Class::Number)
    {
        return BONUS_CAMEL_123;
    }
    match curr {
        Class::NonWord | Class::Delimiter => BONUS_NON_WORD,
        Class::White => BONUS_BOUNDARY_WHITE,
        _ => 0,
    }
}

/// A match: its score and the characters that made it, from the same alignment, so
/// highlights show what was scored.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Match {
    /// Higher is better, as in fzf.
    pub score: i32,
    /// Character indices into the haystack, ascending.
    pub positions: Vec<usize>,
}

/// Score one alignment: the greedy forward walk starting at `start`, its positions
/// written into `positions`.
///
/// Returns `None` when the needle does not fit in what remains of the haystack.
fn score_from(
    hay: &[char],
    lower: &[char],
    needle: &[char],
    start: usize,
    positions: &mut Vec<usize>,
) -> Option<i32> {
    if lower[start] != needle[0] {
        return None;
    }

    positions.clear();
    let mut score = 0i32;
    let mut consecutive = 0usize;
    let mut first_bonus = 0i32;

    // A match sitting in the file name rather than in a directory along the way.
    if !hay[start..].iter().any(|c| *c == '/' || *c == '\\') {
        score += BONUS_FILENAME;
    }

    let mut prev_class = if start == 0 {
        Class::White
    } else {
        class_of(hay[start - 1])
    };
    let mut previous: Option<usize> = None;

    for (n, needle_char) in needle.iter().enumerate() {
        // Find this needle character at or after where the last one landed.
        let from = previous.map(|p| p + 1).unwrap_or(start);
        let pos = (from..lower.len()).find(|i| lower[*i] == *needle_char)?;

        let class = class_of(hay[pos]);
        let gap = previous.map(|p| pos - p - 1).unwrap_or(0);

        let bonus = if gap > 0 {
            prev_class = class_of(hay[pos - 1]);
            let b = bonus_for(prev_class, class);
            score += SCORE_GAP_START + (gap as i32 - 1) * SCORE_GAP_EXTENSION;
            consecutive = 0;
            first_bonus = 0;
            b
        } else {
            let b = bonus_for(prev_class, class);
            if consecutive == 0 {
                first_bonus = b;
                b
            } else {
                // A run that begins mid-word but crosses a boundary is credited for
                // the boundary: "sales" in "my_sales" should not be penalised for
                // having started one character early.
                if b >= BONUS_BOUNDARY && b > first_bonus {
                    first_bonus = b;
                }
                b.max(first_bonus).max(BONUS_CONSECUTIVE)
            }
        };

        // The first character of the needle is where the match is anchored, so its
        // bonus counts double.
        score += SCORE_MATCH
            + if n == 0 {
                bonus * BONUS_FIRST_CHAR_MULTIPLIER
            } else {
                bonus
            };

        consecutive += 1;
        prev_class = class;
        previous = Some(pos);
        positions.push(pos);
    }

    Some(score)
}

/// The best fuzzy match of `needle` in `haystack`, or `None`: every start is tried and
/// the highest alignment wins. Case-insensitive; an empty needle matches with score 0.
pub fn best_match(needle: &str, haystack: &str) -> Option<Match> {
    best_match_with(needle, haystack, |score, positions| Match {
        score,
        positions: positions.to_vec(),
    })
}

/// The buffers one scoring reuses, so a listing of thousands scores with no allocation
/// per name but its answer.
#[derive(Default)]
struct Scratch {
    hay: Vec<char>,
    lower: Vec<char>,
    needle: Vec<char>,
    trial: Vec<usize>,
    best: Vec<usize>,
}

thread_local! {
    static SCRATCH: std::cell::RefCell<Scratch> = std::cell::RefCell::new(Scratch::default());
}

/// [`best_match`], handing the score and positions to `answer` rather than allocating
/// a [`Match`].
pub fn best_match_with<T>(
    needle: &str,
    haystack: &str,
    answer: impl FnOnce(i32, &[usize]) -> T,
) -> Option<T> {
    if needle.is_empty() {
        return Some(answer(0, &[]));
    }
    // Most names in a long list do not match. For ASCII, which is most names, saying so
    // takes one pass over the bytes and no allocation; the search scores tens of
    // thousands of names per keystroke.
    let ascii = needle.is_ascii() && haystack.is_ascii();
    if ascii && !ascii_subsequence(haystack, needle) {
        return None;
    }
    SCRATCH.with(|scratch| match scratch.try_borrow_mut() {
        Ok(mut scratch) => score_best(&mut scratch, ascii, needle, haystack, answer),
        // Only if `answer` scores again; it gets buffers of its own.
        Err(_) => score_best(&mut Scratch::default(), ascii, needle, haystack, answer),
    })
}

fn score_best<T>(
    scratch: &mut Scratch,
    ascii: bool,
    needle: &str,
    haystack: &str,
    answer: impl FnOnce(i32, &[usize]) -> T,
) -> Option<T> {
    let Scratch {
        hay,
        lower,
        needle: need,
        trial,
        best,
    } = scratch;
    hay.clear();
    lower.clear();
    need.clear();
    hay.extend(haystack.chars());
    if ascii {
        lower.extend(hay.iter().map(char::to_ascii_lowercase));
        need.extend(needle.chars().map(|c| c.to_ascii_lowercase()));
    } else {
        lower.extend(haystack.to_lowercase().chars());
        need.extend(needle.to_lowercase().chars());
    }
    // Lowercasing can change length (ß, İ). Falling back keeps the indices honest
    // rather than highlighting the wrong characters.
    if lower.len() != hay.len() {
        return simple_match(hay, need).map(|m| answer(m.score, &m.positions));
    }
    if need.len() > hay.len() {
        return None;
    }
    // A single cheap pass in front of the exhaustive one. Most candidates in a long
    // list do not match at all, and those now cost O(n) instead of a scan from every
    // position the first character happens to sit at.
    if !subsequence(lower, need) {
        return None;
    }

    // The whole name typed is the answer: `hour` must find `hour` before `time_hour`,
    // which the boundary after `_` scores the same.
    if lower == need {
        let score = score_from(hay, lower, need, 0, best)?;
        return Some(answer(score + EXACT_BONUS, best));
    }

    let mut top: Option<i32> = None;
    for start in 0..hay.len() {
        // Only positions where the first needle character actually sits can start an
        // alignment, which is what keeps the exhaustive search cheap in practice.
        if lower[start] != need[0] {
            continue;
        }
        if let Some(score) = score_from(hay, lower, need, start, trial) {
            if top.is_none_or(|t| score > t) {
                top = Some(score);
                std::mem::swap(trial, best);
            }
        } else {
            // The needle no longer fits in what remains; no later start will fit
            // either.
            break;
        }
    }
    top.map(|score| answer(score, best))
}

/// A plain greedy subsequence walk, for haystacks whose lowercase form has a
/// different length than the original and so cannot be indexed in parallel.
fn simple_match(hay: &[char], needle: &[char]) -> Option<Match> {
    let mut positions = Vec::with_capacity(needle.len());
    let mut hi = 0usize;
    for nc in needle {
        let found =
            (hi..hay.len()).find(|i| hay[*i].to_lowercase().next().is_some_and(|c| c == *nc))?;
        positions.push(found);
        hi = found + 1;
    }
    Some(Match {
        score: (positions.len() as i32) * SCORE_MATCH,
        positions,
    })
}

/// Whether `needle` is a subsequence of `haystack`, ignoring ASCII case. Both ASCII.
fn ascii_subsequence(haystack: &str, needle: &str) -> bool {
    let mut hay = haystack.bytes();
    needle
        .bytes()
        .all(|n| hay.any(|h| h.eq_ignore_ascii_case(&n)))
}

/// Whether `needle` is a subsequence of an already-lowercased `haystack`.
fn subsequence(lower: &[char], needle: &[char]) -> bool {
    let mut hi = 0usize;
    for nc in needle {
        match (hi..lower.len()).find(|i| lower[*i] == *nc) {
            Some(found) => hi = found + 1,
            None => return false,
        }
    }
    true
}

/// Whether `needle` matches at all, without scoring: a one-pass gate before
/// `best_match`, since most candidates fail.
pub fn is_match(needle: &str, haystack: &str) -> bool {
    if needle.is_empty() {
        return true;
    }
    let mut chars = haystack.chars().flat_map(|c| c.to_lowercase());
    'outer: for nc in needle.chars().flat_map(|c| c.to_lowercase()) {
        for hc in chars.by_ref() {
            if hc == nc {
                continue 'outer;
            }
        }
        return false;
    }
    true
}

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

    #[test]
    fn an_exact_name_outranks_the_same_word_after_a_boundary() {
        let exact = best_match("hour", "hour").unwrap().score;
        let inside = best_match("hour", "time_hour").unwrap().score;
        assert!(exact > inside, "{exact} vs {inside}");
        assert!(best_match("HOUR", "hour").unwrap().score > inside);
        assert_eq!(best_match("hour", "hour").unwrap().positions, [0, 1, 2, 3]);
    }

    #[test]
    fn substring_rank_puts_the_name_then_its_start_then_the_rest() {
        assert_eq!(substring_rank("Hour", "hour"), Some(0));
        assert_eq!(substring_rank("hour", "hours"), Some(1));
        assert_eq!(substring_rank("hour", "time_hour"), Some(2));
        assert_eq!(substring_rank("hour", "minute"), None);
        assert_eq!(substring_rank("", "minute"), Some(2));
    }
}