fuzzy.rs•7.96 kB
// Copyright (c) Microsoft Corporation.
// Licensed under the MIT License.
//! Fuzzy search algorithm based on the one used in VS Code (`/src/vs/base/common/fuzzyScorer.ts`).
//! Other algorithms exist, such as Sublime Text's, or the one used in `fzf`,
//! but I figured that this one is what lots of people may be familiar with.
use std::vec;
use crate::arena::{Arena, scratch_arena};
use crate::icu;
const NO_MATCH: i32 = 0;
pub fn score_fuzzy<'a>(
arena: &'a Arena,
haystack: &str,
needle: &str,
allow_non_contiguous_matches: bool,
) -> (i32, Vec<usize, &'a Arena>) {
if haystack.is_empty() || needle.is_empty() {
// return early if target or query are empty
return (NO_MATCH, Vec::new_in(arena));
}
let scratch = scratch_arena(Some(arena));
let target = map_chars(&scratch, haystack);
let query = map_chars(&scratch, needle);
if target.len() < query.len() {
// impossible for query to be contained in target
return (NO_MATCH, Vec::new_in(arena));
}
let target_lower = icu::fold_case(&scratch, haystack);
let query_lower = icu::fold_case(&scratch, needle);
let target_lower = map_chars(&scratch, &target_lower);
let query_lower = map_chars(&scratch, &query_lower);
let area = query.len() * target.len();
let mut scores = vec::from_elem_in(0, area, &*scratch);
let mut matches = vec::from_elem_in(0, area, &*scratch);
//
// Build Scorer Matrix:
//
// The matrix is composed of query q and target t. For each index we score
// q[i] with t[i] and compare that with the previous score. If the score is
// equal or larger, we keep the match. In addition to the score, we also keep
// the length of the consecutive matches to use as boost for the score.
//
// t a r g e t
// q
// u
// e
// r
// y
//
for query_index in 0..query.len() {
let query_index_offset = query_index * target.len();
let query_index_previous_offset =
if query_index > 0 { (query_index - 1) * target.len() } else { 0 };
for target_index in 0..target.len() {
let current_index = query_index_offset + target_index;
let diag_index = if query_index > 0 && target_index > 0 {
query_index_previous_offset + target_index - 1
} else {
0
};
let left_score = if target_index > 0 { scores[current_index - 1] } else { 0 };
let diag_score =
if query_index > 0 && target_index > 0 { scores[diag_index] } else { 0 };
let matches_sequence_len =
if query_index > 0 && target_index > 0 { matches[diag_index] } else { 0 };
// If we are not matching on the first query character anymore, we only produce a
// score if we had a score previously for the last query index (by looking at the diagScore).
// This makes sure that the query always matches in sequence on the target. For example
// given a target of "ede" and a query of "de", we would otherwise produce a wrong high score
// for query[1] ("e") matching on target[0] ("e") because of the "beginning of word" boost.
let score = if diag_score == 0 && query_index != 0 {
0
} else {
compute_char_score(
query[query_index],
query_lower[query_index],
if target_index != 0 { Some(target[target_index - 1]) } else { None },
target[target_index],
target_lower[target_index],
matches_sequence_len,
)
};
// We have a score and its equal or larger than the left score
// Match: sequence continues growing from previous diag value
// Score: increases by diag score value
let is_valid_score = score != 0 && diag_score + score >= left_score;
if is_valid_score
&& (
// We don't need to check if it's contiguous if we allow non-contiguous matches
allow_non_contiguous_matches ||
// We must be looking for a contiguous match.
// Looking at an index above 0 in the query means we must have already
// found out this is contiguous otherwise there wouldn't have been a score
query_index > 0 ||
// lastly check if the query is completely contiguous at this index in the target
target_lower[target_index..].starts_with(&query_lower)
)
{
matches[current_index] = matches_sequence_len + 1;
scores[current_index] = diag_score + score;
} else {
// We either have no score or the score is lower than the left score
// Match: reset to 0
// Score: pick up from left hand side
matches[current_index] = NO_MATCH;
scores[current_index] = left_score;
}
}
}
// Restore Positions (starting from bottom right of matrix)
let mut positions = Vec::new_in(arena);
if !query.is_empty() && !target.is_empty() {
let mut query_index = query.len() - 1;
let mut target_index = target.len() - 1;
loop {
let current_index = query_index * target.len() + target_index;
if matches[current_index] == NO_MATCH {
if target_index == 0 {
break;
}
target_index -= 1; // go left
} else {
positions.push(target_index);
// go up and left
if query_index == 0 || target_index == 0 {
break;
}
query_index -= 1;
target_index -= 1;
}
}
positions.reverse();
}
(scores[area - 1], positions)
}
fn compute_char_score(
query: char,
query_lower: char,
target_prev: Option<char>,
target_curr: char,
target_curr_lower: char,
matches_sequence_len: i32,
) -> i32 {
let mut score = 0;
if !consider_as_equal(query_lower, target_curr_lower) {
return score; // no match of characters
}
// Character match bonus
score += 1;
// Consecutive match bonus
if matches_sequence_len > 0 {
score += matches_sequence_len * 5;
}
// Same case bonus
if query == target_curr {
score += 1;
}
if let Some(target_prev) = target_prev {
// After separator bonus
let separator_bonus = score_separator_at_pos(target_prev);
if separator_bonus > 0 {
score += separator_bonus;
}
// Inside word upper case bonus (camel case). We only give this bonus if we're not in a contiguous sequence.
// For example:
// NPE => NullPointerException = boost
// HTTP => HTTP = not boost
else if target_curr != target_curr_lower && matches_sequence_len == 0 {
score += 2;
}
} else {
// Start of word bonus
score += 8;
}
score
}
fn consider_as_equal(a: char, b: char) -> bool {
// Special case path separators: ignore platform differences
a == b || (a == '/' && b == '\\') || (a == '\\' && b == '/')
}
fn score_separator_at_pos(ch: char) -> i32 {
match ch {
'/' | '\\' => 5, // prefer path separators...
'_' | '-' | '.' | ' ' | '\'' | '"' | ':' => 4, // ...over other separators
_ => 0,
}
}
fn map_chars<'a>(arena: &'a Arena, s: &str) -> Vec<char, &'a Arena> {
let mut chars = Vec::with_capacity_in(s.len(), arena);
chars.extend(s.chars());
chars.shrink_to_fit();
chars
}