oo-ide 0.0.4

//! Fuzzy matching for file paths.
//!
//! Strategy:
//!   - Split query on whitespace into tokens.
//!   - Each token must appear as a subsequence in the text
//!     (case-insensitive; `_`, `-`, `.`, `/`, `\` treated as spaces so
//!     "mul view" matches "multi_view_algorithm.cpp").
//!   - Score rewards consecutive character runs and early matches.
//!   - `filter_and_rank` tries the filename component first, falling back to
//!     the full path, so "main" ranks "src/main.rs" above "src/domain.rs".

/// Fuzzy-match `query` against `text`.
///
/// Returns `None` if any query token is not a subsequence of `text`,
/// otherwise `Some(score)` where a higher score means a better match.
pub fn fuzzy_match(query: &str, text: &str) -> Option<f64> {
    if query.is_empty() {
        return Some(0.0);
    }

    let norm = |s: &str| -> String {
        s.chars()
            .map(|c| match c {
                '_' | '-' | '.' | '/' | '\\' => ' ',
                c => c.to_ascii_lowercase(),
            })
            .collect()
    };

    let nq = norm(query);
    let nt = norm(text);
    let tokens: Vec<&str> = nq.split_whitespace().collect();
    if tokens.is_empty() {
        return Some(0.0);
    }

    let text_chars: Vec<char> = nt.chars().collect();
    let text_len = text_chars.len();
    let mut total_score = 0.0_f64;

    for token in &tokens {
        let token_chars: Vec<char> = token.chars().collect();
        let tlen = token_chars.len();
        let mut best: Option<(usize, usize)> = None;

        'outer: for start in 0..text_len {
            let mut ti = 0;
            let mut pos = start;
            while ti < tlen && pos < text_len {
                if text_chars[pos] == token_chars[ti] {
                    ti += 1;
                }
                pos += 1;
            }
            if ti == tlen {
                best = Some((start, pos));
                break 'outer;
            }
        }

        let (start, end) = best?;
        let span = (end - start) as f64;
        let tightness = tlen as f64 / span.max(1.0);
        let position_bonus = 1.0 / (1.0 + start as f64 * 0.05);
        total_score += tightness * position_bonus;
    }

    Some(total_score / tokens.len() as f64)
}

/// Filter and rank a slice of path strings against `query`.
///
/// Each item is matched against its filename component first; if that
/// misses, the full path is tried. Returns matched items sorted best-first.
/// When `query` is empty all items are returned in their original order.
use std::path::PathBuf;

pub fn filter_and_rank<'a>(items: &'a [PathBuf], query: &str) -> Vec<&'a PathBuf> {
    if query.is_empty() {
        return items.iter().collect();
    }

    // Collect matched items with scores
    let mut matched: Vec<(&PathBuf, f64)> = items
        .iter()
        .filter_map(|item| {
            let item_str = item.to_str().unwrap_or_default();
            // Count '/' separators as a cheap O(n-chars) depth proxy, avoiding
            // components().count() which re-parses every component.
            let depth = item_str.bytes().filter(|&b| b == b'/').count();

            let filename = item
                .file_name()
                .and_then(|s| s.to_str())
                .unwrap_or_default();

            let score = if let Some(score) = fuzzy_match(query, filename) {
                // Prefer filename matches and shallower paths.
                score + 1.0 + 1.0 / (depth as f64 + 1.0)
            } else {
                let score = fuzzy_match(query, item_str)?;
                score + 1.0 / (depth as f64 + 1.0)
            };
            Some((item, score))
        })
        .collect();

    // Unstable sort: no merge buffer, faster on random float scores.
    matched.sort_unstable_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));

    // Return references to PathBuf
    matched.into_iter().map(|(p, _)| p).collect()
}

/// Generic filter and rank for any type that can produce a `&str` for matching.
///
/// `text_of(item)` returns the string to match against. Items not matching
/// `query` are dropped; matching items are returned sorted best-first.
/// When `query` is empty, all items are returned in original order.
pub fn filter_and_rank_by<'a, T, F>(items: &'a [T], query: &str, text_of: F) -> Vec<&'a T>
where
    F: Fn(&T) -> String,
{
    if query.is_empty() {
        return items.iter().collect();
    }

    let mut matched: Vec<(&T, f64)> = items
        .iter()
        .filter_map(|item| {
            let text = text_of(item);
            let score = fuzzy_match(query, &text)?;
            Some((item, score))
        })
        .collect();

    matched.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
    matched.into_iter().map(|(item, _)| item).collect()
}

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

    #[test]
    fn empty_query_always_matches() {
        assert!(fuzzy_match("", "anything").is_some());
        assert!(fuzzy_match("", "").is_some());
    }

    #[test]
    fn exact_match_scores_highest() {
        let exact = fuzzy_match("main", "main").unwrap();
        let partial = fuzzy_match("main", "main.rs").unwrap();
        assert!(exact >= partial);
    }

    #[test]
    fn subsequence_match() {
        assert!(fuzzy_match("algo", "multi_view_algorithm.cpp").is_some());
        assert!(fuzzy_match("mvc", "multi_view_algorithm.cpp").is_some());
    }

    #[test]
    fn non_match_returns_none() {
        assert!(fuzzy_match("xyz", "multi_view_algorithm.cpp").is_none());
        assert!(fuzzy_match("zzz", "abc").is_none());
    }

    #[test]
    fn separator_treated_as_space() {
        // "mul view" should match "multi_view_algorithm.cpp"
        assert!(fuzzy_match("mul view", "multi_view_algorithm.cpp").is_some());
        assert!(fuzzy_match("src main", "src/main.rs").is_some());
    }

    #[test]
    fn case_insensitive() {
        assert!(fuzzy_match("MAIN", "main.rs").is_some());
        assert!(fuzzy_match("Main", "MAIN.RS").is_some());
    }

    #[test]
    fn multi_token_all_must_match() {
        // Both tokens must be present.
        assert!(fuzzy_match("app rs", "src/app.rs").is_some());
        assert!(fuzzy_match("app xyz", "src/app.rs").is_none());
    }

    #[test]
    fn consecutive_run_scores_higher_than_scattered() {
        let tight = fuzzy_match("abc", "abcdef").unwrap();
        let loose = fuzzy_match("abc", "axbxcdef").unwrap();
        assert!(tight > loose);
    }

    #[test]
    fn earlier_match_scores_higher() {
        let early = fuzzy_match("rs", "rs_parser.rs").unwrap();
        let late = fuzzy_match("rs", "some_file.rs").unwrap();
        assert!(early > late);
    }
    #[test]
    fn empty_query_returns_all_in_order() {
        let items = vec![
            PathBuf::from("src/main.rs"),
            PathBuf::from("src/app.rs"),
            PathBuf::from("README.md"),
        ];
        let result = filter_and_rank(&items, "");
        assert_eq!(result.len(), 3);
        assert_eq!(result[0], &items[0]);
        assert_eq!(result[1], &items[1]);
        assert_eq!(result[2], &items[2]);
    }

    #[test]
    fn filters_out_non_matching_items() {
        let items = vec![
            PathBuf::from("src/main.rs"),
            PathBuf::from("src/app.rs"),
            PathBuf::from("README.md"),
        ];
        let result = filter_and_rank(&items, "main");
        assert_eq!(result.len(), 1);
        assert_eq!(result[0].to_str().unwrap(), "src/main.rs");
    }

    #[test]
    fn filename_match_ranks_above_path_match() {
        let items = vec![
            PathBuf::from("src/domain.rs"), // "main" not in filename
            PathBuf::from("src/main.rs"),   // "main" in filename
        ];
        let result = filter_and_rank(&items, "main");
        assert_eq!(result[0].to_str().unwrap(), "src/main.rs");
    }

    #[test]
    fn results_sorted_best_first() {
        let items = vec![
            PathBuf::from("very/deep/path/to/app.rs"),
            PathBuf::from("app.rs"),
        ];
        let result = filter_and_rank(&items, "app");
        // Shorter / filename match should rank higher.
        assert_eq!(result[0].to_str().unwrap(), "app.rs");
    }

    #[test]
    fn empty_items_returns_empty() {
        let items: Vec<PathBuf> = vec![];
        assert!(filter_and_rank(&items, "anything").is_empty());
    }
}