369 lines
16 KiB
TypeScript
369 lines
16 KiB
TypeScript
import { createSignal, createMemo, createEffect, onCleanup, For, Show } from "solid-js";
|
|
import { Portal } from "solid-js/web";
|
|
|
|
// ============================================================================
|
|
// Fuzzy matching (Sublime-style subsequence scoring)
|
|
// ============================================================================
|
|
// Port of Forrest Smith's fts_fuzzy_match. Every query char must appear in the
|
|
// target in order; the match is scored so that word-boundary / acronym hits
|
|
// ("nfcu" -> "Navy Federal Credit Union") outrank scattered ones. When a query
|
|
// char matches, we also recurse past it in case a later occurrence scores higher.
|
|
// The matcher functions are exported so other parts of the UI can rank/highlight
|
|
// without mounting the component.
|
|
|
|
export interface FuzzyMatchResult {
|
|
score: number;
|
|
positions: number[];
|
|
}
|
|
|
|
export interface FuzzySegment {
|
|
text: string;
|
|
match: boolean;
|
|
}
|
|
|
|
export interface FuzzyRankedItem {
|
|
value: string;
|
|
score: number;
|
|
segments: FuzzySegment[];
|
|
}
|
|
|
|
const FUZZY_SEQUENTIAL_BONUS = 15;
|
|
const FUZZY_SEPARATOR_BONUS = 30;
|
|
const FUZZY_CAMEL_BONUS = 30;
|
|
const FUZZY_FIRST_LETTER_BONUS = 15;
|
|
const FUZZY_LEADING_PENALTY = -5;
|
|
const FUZZY_MAX_LEADING_PENALTY = -15;
|
|
const FUZZY_UNMATCHED_PENALTY = -1;
|
|
const FUZZY_RECURSION_LIMIT = 10;
|
|
const FUZZY_TRANSPOSE_PENALTY = -20;
|
|
const FUZZY_EXACT_SUBSTRING_BONUS = 100;
|
|
// Per swapped "&" <-> "and" token. Each swap lengthens the matched run by two
|
|
// characters, worth up to 2*FUZZY_SEQUENTIAL_BONUS to the longer "and" spelling;
|
|
// penalize each swap by more than that so the literal spelling the user typed always
|
|
// ranks above the substituted one. (This lowers rank, not visibility — the
|
|
// substituted match still appears in the results.)
|
|
const FUZZY_AND_AMPERSAND_PENALTY = -(2 * FUZZY_SEQUENTIAL_BONUS + 20); // -50
|
|
|
|
// Options that turn on extra, penalized match passes. Off by default so the base
|
|
// matcher stays exact-only.
|
|
export interface FuzzyMatchOptions {
|
|
// Treat the word "and" and the symbol "&" as interchangeable, so "First Bank
|
|
// and Trust" also finds "First Bank & Trust" (and vice versa). The exact
|
|
// spelling still wins — the substituted form is penalized, not free.
|
|
andAmpersand?: boolean;
|
|
}
|
|
|
|
const isLower = (c: string) => c >= "a" && c <= "z";
|
|
const isUpper = (c: string) => c >= "A" && c <= "Z";
|
|
const isSeparator = (c: string) => c === " " || c === "_" || c === "-";
|
|
|
|
function fuzzyScore(target: string, matches: number[]): number {
|
|
let score = 100;
|
|
score += Math.max(FUZZY_MAX_LEADING_PENALTY, FUZZY_LEADING_PENALTY * matches[0]);
|
|
score += FUZZY_UNMATCHED_PENALTY * (target.length - matches.length);
|
|
|
|
for (let i = 0; i < matches.length; i++) {
|
|
const curr = matches[i];
|
|
if (i > 0 && curr === matches[i - 1] + 1) score += FUZZY_SEQUENTIAL_BONUS;
|
|
if (curr === 0) {
|
|
score += FUZZY_FIRST_LETTER_BONUS;
|
|
} else {
|
|
const prev = target[curr - 1];
|
|
if (isLower(prev) && isUpper(target[curr])) score += FUZZY_CAMEL_BONUS;
|
|
if (isSeparator(prev)) score += FUZZY_SEPARATOR_BONUS;
|
|
}
|
|
}
|
|
return score;
|
|
}
|
|
|
|
function fuzzyRecurse(query: string, target: string, qi: number, ti: number, matches: number[], rec: { count: number }): number[] | null {
|
|
if (++rec.count >= FUZZY_RECURSION_LIMIT) return null;
|
|
|
|
let best: number[] | null = null;
|
|
while (qi < query.length && ti < target.length) {
|
|
if (query[qi].toLowerCase() === target[ti].toLowerCase()) {
|
|
const skipped = fuzzyRecurse(query, target, qi, ti + 1, matches.slice(), rec);
|
|
if (skipped && (!best || fuzzyScore(target, skipped) > fuzzyScore(target, best))) best = skipped;
|
|
matches.push(ti);
|
|
qi++;
|
|
}
|
|
ti++;
|
|
}
|
|
|
|
if (qi < query.length) return best; // query not fully consumed -> this path failed
|
|
if (!best || fuzzyScore(target, matches) > fuzzyScore(target, best)) return matches;
|
|
return best;
|
|
}
|
|
|
|
export function fuzzyMatch(query: string, target: string): FuzzyMatchResult | null {
|
|
if (!query) return null;
|
|
const matches = fuzzyRecurse(query, target, 0, 0, [], { count: 0 });
|
|
if (!matches) return null;
|
|
let score = fuzzyScore(target, matches);
|
|
// A contiguous substring hit ("bankof" in "Bankof") should outrank a
|
|
// word-boundary match split across tokens ("Bank of America"). The bonus is
|
|
// constant per query/target, so it lives here rather than in the per-
|
|
// alignment scorer the recursion uses to pick match positions.
|
|
if (target.toLowerCase().includes(query.toLowerCase())) score += FUZZY_EXACT_SUBSTRING_BONUS;
|
|
return { score, positions: matches };
|
|
}
|
|
|
|
// An alternative spelling of the query plus the number of tokens swapped to
|
|
// produce it, so the penalty can scale with how far it strayed.
|
|
interface FuzzyVariant {
|
|
text: string;
|
|
swaps: number;
|
|
}
|
|
|
|
// Alternative spellings of `query` with the word "and" and the symbol "&" swapped
|
|
// for each other, excluding `query` itself. `\band\b` only rewrites a standalone
|
|
// "and", so "brand" and "island" are left alone. These are the candidates the
|
|
// matcher tries (penalized per swap) so "... and ..." can still hit a "... & ..."
|
|
// target and vice versa, while the exact spelling ranks first.
|
|
function andAmpersandVariants(query: string): FuzzyVariant[] {
|
|
const out: FuzzyVariant[] = [];
|
|
let ands = 0;
|
|
const amp = query.replace(/\band\b/gi, () => { ands++; return "&"; });
|
|
if (ands > 0) out.push({ text: amp, swaps: ands });
|
|
const amps = (query.match(/&/g) || []).length;
|
|
if (amps > 0) out.push({ text: query.replace(/&/g, "and"), swaps: amps });
|
|
return out;
|
|
}
|
|
|
|
// Subsequence matching can't tolerate a transposed typo ("teh" vs "the") because
|
|
// the swapped letters violate ordering. So also try every single adjacent-swap
|
|
// variant of the query and keep the best, penalizing transposed hits so exact
|
|
// matches still rank first. With `opts.andAmpersand`, the "and"/"&" spellings are
|
|
// tried the same way — an extra penalized pass, not a free substitution.
|
|
export function fuzzyMatchTypoTolerant(query: string, target: string, opts?: FuzzyMatchOptions): FuzzyMatchResult | null {
|
|
let best = fuzzyMatch(query, target);
|
|
for (let i = 0; i < query.length - 1; i++) {
|
|
const swapped = query.slice(0, i) + query[i + 1] + query[i] + query.slice(i + 2);
|
|
const m = fuzzyMatch(swapped, target);
|
|
if (!m) continue;
|
|
const score = m.score + FUZZY_TRANSPOSE_PENALTY;
|
|
if (!best || score > best.score) best = { score, positions: m.positions };
|
|
}
|
|
if (opts?.andAmpersand) {
|
|
for (const variant of andAmpersandVariants(query)) {
|
|
const m = fuzzyMatch(variant.text, target);
|
|
if (!m) continue;
|
|
const score = m.score + variant.swaps * FUZZY_AND_AMPERSAND_PENALTY;
|
|
if (!best || score > best.score) best = { score, positions: m.positions };
|
|
}
|
|
}
|
|
return best;
|
|
}
|
|
|
|
// Split `text` into alternating matched / unmatched runs for highlighting.
|
|
export function fuzzySegments(text: string, positions: number[]): FuzzySegment[] {
|
|
const matched = new Set(positions);
|
|
const segments: FuzzySegment[] = [];
|
|
let buf = "";
|
|
let bufMatch = matched.has(0);
|
|
for (let i = 0; i < text.length; i++) {
|
|
const isMatch = matched.has(i);
|
|
if (isMatch !== bufMatch) {
|
|
if (buf) segments.push({ text: buf, match: bufMatch });
|
|
buf = "";
|
|
bufMatch = isMatch;
|
|
}
|
|
buf += text[i];
|
|
}
|
|
if (buf) segments.push({ text: buf, match: bufMatch });
|
|
return segments;
|
|
}
|
|
|
|
// Rank `options` against `query`, best score first, with highlight segments.
|
|
// Returns [] for an empty query. This is the headless entry point.
|
|
export function rankFuzzyMatches(query: string, options: string[], maxResults?: number, opts?: FuzzyMatchOptions): FuzzyRankedItem[] {
|
|
const q = query.trim();
|
|
if (!q) return [];
|
|
const out: FuzzyRankedItem[] = [];
|
|
for (const value of options) {
|
|
const m = fuzzyMatchTypoTolerant(q, value, opts);
|
|
if (m) out.push({ value, score: m.score, segments: fuzzySegments(value, m.positions) });
|
|
}
|
|
out.sort((a, b) => b.score - a.score);
|
|
return maxResults != null ? out.slice(0, maxResults) : out;
|
|
}
|
|
|
|
// ============================================================================
|
|
// Component
|
|
// ============================================================================
|
|
|
|
export type FuzzyMatchDisplay = "list" | "dropdown" | "none";
|
|
|
|
export interface FuzzyMatchProps {
|
|
options: string[];
|
|
// "list": inline highlighted results below the input (default).
|
|
// "dropdown": ComboBox-style autocomplete popover.
|
|
// "none": render only the input and emit via onResults (headless).
|
|
display?: FuzzyMatchDisplay;
|
|
// Show each result's match score. Debug aid — off by default.
|
|
showScores?: boolean;
|
|
maxResults?: number;
|
|
// Treat "and" and "&" as interchangeable (see FuzzyMatchOptions.andAmpersand).
|
|
andAmpersand?: boolean;
|
|
placeholder?: string;
|
|
class?: string;
|
|
listClass?: string;
|
|
// Emit the ranked results on every change so other UI can consume them.
|
|
onResults?: (results: FuzzyRankedItem[]) => void;
|
|
onSelect?: (value: string, item: FuzzyRankedItem) => void;
|
|
onQueryChange?: (query: string) => void;
|
|
}
|
|
|
|
const INPUT_CLS = "bg-surface block w-full border border-line-strong rounded-default shadow-xs text-sm p-2 h-[38px] focus:outline-2 focus:outline-offset-1 focus:outline-sky-500";
|
|
|
|
// Mirror FormCombobox's dropdown styling (Forms.ts): neutral hover / highlight,
|
|
// not a colored one.
|
|
const DROPDOWN_CLS = "bg-surface border border-line-strong rounded-default shadow-lg max-h-60 overflow-auto";
|
|
const DROPDOWN_OPTION_CLS = "w-full text-left p-2 text-sm cursor-pointer flex items-center justify-between gap-2 bg-transparent border-none hover:bg-surface-raised whitespace-nowrap";
|
|
const DROPDOWN_OPTION_HIGHLIGHT_CLS = "bg-surface-raised";
|
|
|
|
function Highlight(props: { segments: FuzzySegment[] }) {
|
|
return <For each={props.segments}>
|
|
{(seg) => seg.match
|
|
? <span class="text-sky-700 dark:text-sky-400 font-semibold">{seg.text}</span>
|
|
: <span>{seg.text}</span>}
|
|
</For>;
|
|
}
|
|
|
|
export function FuzzyMatch(props: FuzzyMatchProps) {
|
|
const [query, setQuery] = createSignal("");
|
|
const [open, setOpen] = createSignal(false);
|
|
const [highlighted, setHighlighted] = createSignal(0);
|
|
const [pos, setPos] = createSignal({ top: 0, left: 0, width: 0 });
|
|
let containerRef: HTMLDivElement | undefined;
|
|
let inputRef: HTMLInputElement | undefined;
|
|
let dropdownRef: HTMLDivElement | undefined;
|
|
|
|
const display = () => props.display ?? "list";
|
|
const results = createMemo(() => rankFuzzyMatches(query(), props.options, props.maxResults, { andAmpersand: props.andAmpersand }));
|
|
|
|
// Show all options (unranked) in list mode before the user types anything,
|
|
// so the searchable set is visible up front.
|
|
const listItems = createMemo<FuzzyRankedItem[]>(() =>
|
|
query().trim()
|
|
? results()
|
|
: props.options.map((value) => ({ value, score: 0, segments: [{ text: value, match: false }] }))
|
|
);
|
|
|
|
// Emit results to the parent whenever they change (headless usage).
|
|
createEffect(() => props.onResults?.(results()));
|
|
|
|
const setQ = (v: string) => {
|
|
setQuery(v);
|
|
setHighlighted(0);
|
|
props.onQueryChange?.(v);
|
|
};
|
|
|
|
const select = (item: FuzzyRankedItem) => {
|
|
props.onSelect?.(item.value, item);
|
|
if (display() === "dropdown") {
|
|
setQ(item.value);
|
|
setOpen(false);
|
|
}
|
|
};
|
|
|
|
const updatePos = () => {
|
|
if (!inputRef) return;
|
|
const r = inputRef.getBoundingClientRect();
|
|
setPos({ top: r.bottom + 4, left: r.left, width: r.width });
|
|
};
|
|
|
|
// Position tracking + outside-click, only while the dropdown is open.
|
|
createEffect(() => {
|
|
if (display() !== "dropdown" || !open()) return;
|
|
updatePos();
|
|
const onDown = (e: MouseEvent) => {
|
|
const t = e.target as Node;
|
|
if (!containerRef?.contains(t) && !dropdownRef?.contains(t)) setOpen(false);
|
|
};
|
|
document.addEventListener("mousedown", onDown);
|
|
onCleanup(() => document.removeEventListener("mousedown", onDown));
|
|
});
|
|
|
|
const onKeyDown = (e: KeyboardEvent) => {
|
|
if (display() !== "dropdown") return;
|
|
const list = results();
|
|
if (e.key === "ArrowDown") {
|
|
e.preventDefault();
|
|
setOpen(true);
|
|
setHighlighted((i) => Math.min(i + 1, list.length - 1));
|
|
} else if (e.key === "ArrowUp") {
|
|
e.preventDefault();
|
|
setHighlighted((i) => Math.max(i - 1, 0));
|
|
} else if (e.key === "Enter") {
|
|
e.preventDefault();
|
|
const it = list[highlighted()];
|
|
if (it) select(it);
|
|
} else if (e.key === "Escape") {
|
|
setOpen(false);
|
|
}
|
|
};
|
|
|
|
const ScoreBadge = (p: { score: number }) =>
|
|
<Show when={props.showScores}>
|
|
<span class="ml-3 shrink-0 text-ss text-ink-faint">{p.score}</span>
|
|
</Show>;
|
|
|
|
return <div ref={containerRef} class={"relative " + (props.class ?? "")}>
|
|
<input
|
|
ref={inputRef}
|
|
type="text"
|
|
class={INPUT_CLS}
|
|
value={query()}
|
|
placeholder={props.placeholder ?? "Search..."}
|
|
oninput={(e) => { setQ(e.currentTarget.value); if (display() === "dropdown") setOpen(true); }}
|
|
onFocus={() => { if (display() === "dropdown" && results().length) setOpen(true); }}
|
|
onKeyDown={onKeyDown}
|
|
/>
|
|
|
|
<Show when={display() === "list"}>
|
|
<div class={"mt-3 " + (props.listClass ?? "h-72 overflow-y-auto")}>
|
|
<Show when={listItems().length > 0} fallback={
|
|
<Show when={query().trim()}>
|
|
<p class="text-sm text-ink-muted italic">No matches for "{query()}".</p>
|
|
</Show>
|
|
}>
|
|
<ul class="flex flex-col gap-0.5">
|
|
<For each={listItems()}>
|
|
{(r) => <li
|
|
class="flex items-center justify-between gap-3 px-2 py-1 rounded-default cursor-pointer hover:bg-surface-raised"
|
|
onclick={() => select(r)}
|
|
>
|
|
<span class="text-sm text-ink"><Highlight segments={r.segments} /></span>
|
|
<ScoreBadge score={r.score} />
|
|
</li>}
|
|
</For>
|
|
</ul>
|
|
</Show>
|
|
</div>
|
|
</Show>
|
|
|
|
<Show when={display() === "dropdown" && open() && results().length > 0}>
|
|
<Portal>
|
|
<div
|
|
ref={dropdownRef}
|
|
data-floating-content="true"
|
|
class={DROPDOWN_CLS}
|
|
style={`position:fixed;top:${pos().top}px;left:${pos().left}px;width:${pos().width}px;z-index:200;`}
|
|
>
|
|
<For each={results()}>
|
|
{(r, i) => <button
|
|
type="button"
|
|
onclick={() => select(r)}
|
|
onMouseEnter={() => setHighlighted(i())}
|
|
class={DROPDOWN_OPTION_CLS + (i() === highlighted() ? " " + DROPDOWN_OPTION_HIGHLIGHT_CLS : "")}
|
|
>
|
|
<span class="text-ink"><Highlight segments={r.segments} /></span>
|
|
<ScoreBadge score={r.score} />
|
|
</button>}
|
|
</For>
|
|
</div>
|
|
</Portal>
|
|
</Show>
|
|
</div>;
|
|
} |