export type FuzzyMatch = { path: string; score: number; positions: number[] };
const CONSECUTIVE_BONUS = 5;
const BOUNDARY_BONUS = 8;
const BASENAME_BONUS = 2;
const GAP_PENALTY = 1;
const BOUNDARY = /[/_\-. ]/;
/** Subsequence match favouring consecutive runs, segment starts and the file name; null when `query` is not a subsequence. */
export function fuzzyScore(query: string, path: string): FuzzyMatch | null {
const needle = query.toLowerCase().replace(/\s+/g, "");
if (!needle) return { path, score: 0, positions: [] };
const haystack = path.toLowerCase();
const basenameStart = path.lastIndexOf("/") + 1;
const positions: number[] = [];
let score = 0;
let from = 0;
for (const char of needle) {
const index = haystack.indexOf(char, from);
if (index < 0) return null;
const previous = positions[positions.length - 1];
if (previous !== undefined && index === previous + 1) score += CONSECUTIVE_BONUS;
else if (previous !== undefined) score -= Math.min(index - previous, 10) * GAP_PENALTY;
if (index === 0 || BOUNDARY.test(path[index - 1] ?? "")) score += BOUNDARY_BONUS;
if (index >= basenameStart) score += BASENAME_BONUS;
positions.push(index);
from = index + 1;
}
return { path, score: score - path.length / 100, positions };
}
export function fuzzyFilter(query: string, paths: string[], limit: number): FuzzyMatch[] {
const matches: FuzzyMatch[] = [];
for (const path of paths) {
const match = fuzzyScore(query, path);
if (match) matches.push(match);
}
return matches.sort((left, right) => right.score - left.score).slice(0, limit);
}