Fuzzy Match Input

"use client";

import {
  useEffect,
  useId,
  useLayoutEffect,
  useMemo,
  useRef,
  useState,
  type CSSProperties,
} from "react";

type Match = { indices: number[]; score: number } | null;

/**
 * Subsequence matcher. Returns the matched INDICES as well as a score -
 * returning only a boolean is why most "fuzzy search" fields cannot highlight
 * what actually matched.
 */
export function fuzzyMatch(query: string, target: string): Match {
  if (!query) return { indices: [], score: 0 };
  const q = query.toLowerCase();
  const t = target.toLowerCase();

  const indices: number[] = [];
  let score = 0;
  let run = 0;
  let ti = 0;

  for (let qi = 0; qi < q.length; qi++) {
    const ch = q.charAt(qi);
    if (ch === " ") continue;

    let found = -1;
    while (ti < t.length) {
      if (t.charAt(ti) === ch) {
        found = ti;
        break;
      }
      ti++;
    }
    if (found === -1) return null; // a query char is missing -> no match

    // Consecutive hits are worth far more than scattered ones, so "cmd"
    // prefers a contiguous run over three letters spread across the string.
    const prev = indices.length > 0 ? (indices[indices.length - 1] ?? -2) : -2;
    indices.push(found);
    run = found === prev + 1 ? run + 1 : 0;
    score += 1 + run * 4;
    // Word starts are a strong signal of intent.
    if (found === 0 || t.charAt(found - 1) === " " || t.charAt(found - 1) === "-") score += 6;
    ti = found + 1;
  }

  return { indices, score };
}

export type FuzzyMatchInputProps = {
  rows: readonly string[];
  /** Most rows shown at once. */
  limit?: number;
  placeholder?: string;
  /** Print each row's match score (and a small bar), which makes the ranking legible. */
  showScore?: boolean;
  /** "dark" paints a near-black panel, "light" a white one. */
  tone?: "dark" | "light";
  /** Highlight colour (any CSS colour). Defaults to blue. */
  accent?: string;
  /** Controlled query. */
  value?: string;
  /** Initial query when uncontrolled. */
  defaultValue?: string;
  onValueChange?: (value: string) => void;
  /** Fires on Enter or click/tap on a row. */
  onSelect?: (row: string) => void;
  /** Accessible name of the field. */
  label?: string;
  /** Headline of the no-match state. */
  emptyText?: string;
  className?: string;
  style?: CSSProperties;
};

const ROW = 44;
const MAX_VISIBLE = 8;
const EMPTY_H = 136;
const COLOR_RE = /^(#[0-9a-f]{3,8}|(rgb|hsl)a?\([0-9\s.,%/]+\)|[a-z]{3,20})$/i;
const useIsoLayoutEffect = typeof window !== "undefined" ? useLayoutEffect : useEffect;

const CSS = [
  "@layer components {",
  ".fmi-root{--fmi-bg:#0b0c0f;--fmi-ring:rgba(255,255,255,.1);--fmi-ink:#f4f4f5;--fmi-mute:rgba(244,244,245,.56);--fmi-faint:rgba(244,244,245,.42);--fmi-pill:rgba(255,255,255,.065);--fmi-accent:#60a5fa;--fmi-shadow:0 30px 70px -28px rgba(0,0,0,.85),0 2px 0 rgba(255,255,255,.04) inset;--fmi-sheen:rgba(255,255,255,.2);position:relative;display:block;width:100%;isolation:isolate;overflow:hidden;border-radius:18px;background:var(--fmi-bg);color:var(--fmi-ink);box-shadow:0 0 0 1px var(--fmi-ring),var(--fmi-shadow);font-size:15px;line-height:1.35;text-align:left;-webkit-tap-highlight-color:transparent}",
  ".fmi-root[data-tone=light]{--fmi-bg:#ffffff;--fmi-ring:#e4e4e7;--fmi-ink:#18181b;--fmi-mute:#52525b;--fmi-faint:#71717a;--fmi-pill:rgba(24,24,27,.055);--fmi-accent:#2563eb;--fmi-shadow:0 26px 60px -30px rgba(24,24,27,.3);--fmi-sheen:rgba(255,255,255,0)}",
  ".fmi-root::before{content:'';position:absolute;left:12%;right:12%;top:0;height:1px;background:linear-gradient(90deg,transparent,var(--fmi-sheen),transparent);z-index:3;pointer-events:none}",
  ".fmi-root:focus-within{box-shadow:0 0 0 1px color-mix(in srgb,var(--fmi-accent) 55%,transparent),0 0 0 4px color-mix(in srgb,var(--fmi-accent) 16%,transparent),var(--fmi-shadow)}",
  ".fmi-glow{position:absolute;inset:0;z-index:0;pointer-events:none;opacity:0;transition:opacity .35s ease;background:radial-gradient(260px circle at var(--fmi-mx,50%) var(--fmi-my,0%),color-mix(in srgb,var(--fmi-accent) 11%,transparent),transparent 70%)}",
  "@media (hover:hover){.fmi-root:hover .fmi-glow{opacity:1}}",
  ".fmi-in{position:relative;z-index:1;display:flex;align-items:center;gap:10px;height:56px;padding:0 10px 0 18px;border-bottom:1px solid var(--fmi-ring)}",
  ".fmi-sweep{position:absolute;left:0;right:0;bottom:-1px;height:2px;background:var(--fmi-accent);transform:scaleX(0);transform-origin:left;transition:transform .55s cubic-bezier(.22,1,.36,1)}",
  ".fmi-root:focus-within .fmi-sweep{transform:scaleX(1)}",
  ".fmi-ico{flex:none;width:18px;height:18px;color:var(--fmi-faint);transition:color .2s ease,transform .3s cubic-bezier(.34,1.4,.5,1)}",
  ".fmi-root:focus-within .fmi-ico{color:var(--fmi-accent);transform:scale(1.08)}",
  ".fmi-input{flex:1;min-width:0;height:100%;background:transparent;border:0;color:var(--fmi-ink);font:inherit;font-size:16px;letter-spacing:-.005em;caret-color:var(--fmi-accent)}",
  ".fmi-input,.fmi-input:focus,.fmi-input:focus-visible{outline:0!important;box-shadow:none}",
  ".fmi-input::placeholder{color:var(--fmi-faint);opacity:1}",
  ".fmi-x{flex:none;display:grid;place-items:center;width:40px;height:40px;border:0;border-radius:10px;background:transparent;color:var(--fmi-faint);cursor:pointer;transition:background .15s ease,color .15s ease,opacity .2s ease,transform .25s cubic-bezier(.34,1.4,.5,1)}",
  ".fmi-x svg{width:16px;height:16px}",
  ".fmi-x:hover{background:var(--fmi-pill);color:var(--fmi-ink)}",
  ".fmi-x:active{transform:scale(.9)}",
  ".fmi-x[data-off]{opacity:0;pointer-events:none;transform:scale(.7)}",
  ".fmi-x:focus-visible,.fmi-clear:focus-visible{outline:2px solid var(--fmi-accent)!important;outline-offset:1px!important;border-radius:10px!important}",
  ".fmi-hd{position:relative;z-index:1;display:flex;align-items:center;justify-content:space-between;height:30px;padding:0 18px;font-size:11px;letter-spacing:.14em;text-transform:uppercase;color:var(--fmi-faint)}",
  ".fmi-hd b{font-weight:500;font-variant-numeric:tabular-nums}",
  ".fmi-wrap{position:relative;z-index:1;transition:height .3s cubic-bezier(.22,1,.36,1)}",
  ".fmi-list{position:relative;height:100%;overflow-y:auto;overflow-x:hidden;overscroll-behavior:contain;scrollbar-width:none}",
  ".fmi-list::-webkit-scrollbar{display:none}",
  ".fmi-pill{position:absolute;left:6px;right:6px;top:0;height:" + ROW + "px;border-radius:12px;background:var(--fmi-pill);pointer-events:none;transition:transform .32s cubic-bezier(.3,1.25,.5,1),opacity .2s ease,background .5s ease}",
  ".fmi-pill::before{content:'';position:absolute;left:0;top:13px;bottom:13px;width:2px;border-radius:2px;background:var(--fmi-accent)}",
  ".fmi-pill[data-flash]{background:color-mix(in srgb,var(--fmi-accent) 24%,transparent);transition:transform .32s cubic-bezier(.3,1.25,.5,1),background .08s ease}",
  ".fmi-row{position:relative;display:flex;align-items:center;gap:10px;height:" + ROW + "px;padding:0 18px;cursor:pointer;touch-action:manipulation}",
  ".fmi-lead{flex:none;width:14px;height:14px;display:grid;place-items:center;color:var(--fmi-faint)}",
  ".fmi-lead svg{width:14px;height:14px}",
  ".fmi-arrow{opacity:0;transform:translateX(-5px);transition:opacity .2s ease,transform .3s cubic-bezier(.22,1,.36,1);color:var(--fmi-accent)}",
  ".fmi-row[data-active] .fmi-arrow{opacity:1;transform:none}",
  ".fmi-text{flex:1;min-width:0;overflow:hidden;text-overflow:ellipsis;white-space:nowrap}",
  ".fmi-c{color:var(--fmi-ink);transition:color .18s ease,box-shadow .18s ease}",
  ".fmi-root[data-q='1'] .fmi-c{color:var(--fmi-mute)}",
  ".fmi-root[data-q='1'] .fmi-row[data-active] .fmi-c{color:color-mix(in srgb,var(--fmi-ink) 78%,transparent)}",
  ".fmi-root[data-q='1'] .fmi-c[data-hit]{color:var(--fmi-accent);box-shadow:inset 0 -1.5px 0 color-mix(in srgb,var(--fmi-accent) 70%,transparent);transition-delay:calc(var(--k,0)*18ms)}",
  ".fmi-score{flex:none;display:flex;align-items:center;gap:8px;font-family:ui-monospace,SFMono-Regular,Menlo,Consolas,monospace;font-size:11px;color:var(--fmi-faint);font-variant-numeric:tabular-nums}",
  ".fmi-bar{display:block;width:30px;height:3px;border-radius:3px;background:var(--fmi-pill);overflow:hidden}",
  ".fmi-bar i{display:block;height:100%;width:100%;border-radius:3px;background:var(--fmi-accent);opacity:.8;transform-origin:left;transition:transform .45s cubic-bezier(.22,1,.36,1)}",
  ".fmi-check{flex:none;width:18px;height:18px;color:var(--fmi-accent);animation:fmi-pop .45s cubic-bezier(.34,1.5,.5,1) both}",
  "@keyframes fmi-pop{from{opacity:0;transform:scale(.4)}to{opacity:1;transform:none}}",
  ".fmi-empty{position:relative;z-index:1;height:100%;display:flex;flex-direction:column;align-items:center;justify-content:center;gap:4px;padding:0 24px;text-align:center}",
  ".fmi-empty svg{width:22px;height:22px;color:var(--fmi-faint);margin-bottom:6px}",
  ".fmi-empty p{margin:0}",
  ".fmi-empty .t{font-size:14px;color:var(--fmi-ink);max-width:100%;overflow:hidden;text-overflow:ellipsis;white-space:nowrap}",
  ".fmi-empty .s{font-size:12.5px;color:var(--fmi-mute)}",
  ".fmi-clear{margin-top:10px;height:36px;min-width:40px;padding:0 14px;border:0;border-radius:10px;background:var(--fmi-pill);color:var(--fmi-ink);font:inherit;font-size:12.5px;cursor:pointer;transition:background .15s ease,transform .2s cubic-bezier(.34,1.4,.5,1)}",
  ".fmi-clear:hover{background:color-mix(in srgb,var(--fmi-accent) 20%,transparent)}",
  ".fmi-clear:active{transform:scale(.95)}",
  ".fmi-ft{position:relative;z-index:1;display:flex;align-items:center;gap:16px;height:38px;padding:0 18px;border-top:1px solid var(--fmi-ring);font-size:11.5px;color:var(--fmi-faint)}",
  ".fmi-ft span{display:inline-flex;align-items:center;gap:6px}",
  ".fmi-ft kbd{display:inline-grid;place-items:center;min-width:20px;height:20px;padding:0 5px;border-radius:6px;background:var(--fmi-pill);color:var(--fmi-mute);font:inherit;font-size:11px}",
  "@media (hover:none){.fmi-ft{display:none}}",
  ".fmi-sr{position:absolute;width:1px;height:1px;margin:-1px;padding:0;overflow:hidden;clip:rect(0 0 0 0);white-space:nowrap;border:0}",
  "@media (prefers-reduced-motion:reduce){.fmi-root *,.fmi-root *::before{transition-duration:.01ms!important;transition-delay:0s!important;animation-duration:.01ms!important}}",
  "}",
].join("\n");

const Svg = ({ d, className }: { d: string; className?: string }) => (
  <svg
    viewBox="0 0 24 24"
    fill="none"
    stroke="currentColor"
    strokeWidth="2"
    strokeLinecap="round"
    strokeLinejoin="round"
    aria-hidden="true"
    className={className}
  >
    <path d={d} />
  </svg>
);

type Item = { row: string; indices: number[]; score: number; recent: boolean };

export function FuzzyMatchInput({
  rows,
  limit = 5,
  placeholder = "Search…",
  showScore = true,
  tone = "dark",
  accent,
  value,
  defaultValue = "",
  onValueChange,
  onSelect,
  label = "Search",
  emptyText = "Nothing matches",
  className,
  style,
}: FuzzyMatchInputProps) {
  const uid = useId();
  const listId = uid + "-list";
  const [inner, setInner] = useState(defaultValue);
  const query = value ?? inner;
  const [active, setActive] = useState(0);
  const [recent, setRecent] = useState<string[]>([]);
  const [picked, setPicked] = useState<string | null>(null);
  const inputRef = useRef<HTMLInputElement>(null);
  const rootRef = useRef<HTMLDivElement>(null);
  const listRef = useRef<HTMLDivElement>(null);
  const prevPos = useRef<Map<string, number>>(new Map());
  const timer = useRef(0);

  const hasQuery = query.trim().length > 0;
  const max = Math.max(1, Math.floor(limit));

  const { items, total } = useMemo(() => {
    const uniq = Array.from(new Set(rows));
    if (!hasQuery) {
      const rec = recent.filter((r) => uniq.includes(r)).slice(0, 3);
      const list: Item[] = [
        ...rec.map((row) => ({ row, indices: [], score: 0, recent: true })),
        ...uniq.filter((r) => !rec.includes(r)).map((row) => ({ row, indices: [], score: 0, recent: false })),
      ];
      return { items: list.slice(0, max), total: uniq.length };
    }
    const scored: Item[] = [];
    for (const row of uniq) {
      const m = fuzzyMatch(query, row);
      if (m) scored.push({ row, indices: m.indices, score: m.score, recent: false });
    }
    // Ties: the shorter row is the closer match. Array.sort is stable, so
    // equal rows keep their input order.
    scored.sort((a, b) => b.score - a.score || a.row.length - b.row.length);
    return { items: scored.slice(0, max), total: scored.length };
  }, [rows, query, hasQuery, recent, max]);

  const n = items.length;
  const ai = Math.min(active, Math.max(0, n - 1));
  const topScore = items.reduce((m, it) => Math.max(m, it.score), 1);

  // Rows slide to their new rank and new rows rise in. Positions are measured
  // in layout pixels, so it also works inside a transform-scaled preview.
  useIsoLayoutEffect(() => {
    const list = listRef.current;
    if (!list) return;
    const calm = window.matchMedia("(prefers-reduced-motion: reduce)").matches;
    const next = new Map<string, number>();
    const els = list.querySelectorAll<HTMLElement>("[data-row]");
    els.forEach((el, idx) => {
      const k = el.dataset.row ?? "";
      const top = el.offsetTop;
      next.set(k, top);
      if (calm || typeof el.animate !== "function") return;
      const was = prevPos.current.get(k);
      if (was === undefined) {
        el.animate(
          [
            { opacity: 0, transform: "translateY(8px)" },
            { opacity: 1, transform: "none" },
          ],
          { duration: 260, delay: Math.min(idx, 6) * 28, easing: "cubic-bezier(.22,1,.36,1)", fill: "backwards" },
        );
      } else if (was !== top) {
        el.animate([{ transform: "translateY(" + (was - top) + "px)" }, { transform: "none" }], {
          duration: 340,
          easing: "cubic-bezier(.3,1.2,.5,1)",
        });
      }
    });
    prevPos.current = next;
  }, [items]);

  const setQuery = (v: string) => {
    if (value === undefined) setInner(v);
    onValueChange?.(v);
    setActive(0);
  };

  const choose = (row: string) => {
    setRecent((r) => [row, ...r.filter((x) => x !== row)].slice(0, 6));
    setPicked(row);
    window.clearTimeout(timer.current);
    timer.current = window.setTimeout(() => setPicked(null), 1100);
    onSelect?.(row);
  };

  const reveal = (i: number) => {
    const list = listRef.current;
    if (!list) return;
    const top = i * ROW;
    if (top < list.scrollTop) list.scrollTop = top;
    else if (top + ROW > list.scrollTop + list.clientHeight) list.scrollTop = top + ROW - list.clientHeight;
  };

  const onKeyDown = (e: React.KeyboardEvent<HTMLInputElement>) => {
    if (e.nativeEvent.isComposing) return;
    if ((e.key === "ArrowDown" || e.key === "ArrowUp") && n > 0) {
      e.preventDefault();
      const i = (ai + (e.key === "ArrowDown" ? 1 : n - 1)) % n;
      setActive(i);
      reveal(i);
    } else if (e.key === "Enter") {
      const it = items[ai];
      if (it) {
        e.preventDefault();
        choose(it.row);
      }
    } else if (e.key === "Escape") {
      if (query) {
        e.preventDefault();
        setQuery("");
      } else {
        e.currentTarget.blur();
      }
    }
  };

  const onPointerMove = (e: React.PointerEvent<HTMLDivElement>) => {
    const el = rootRef.current;
    if (!el || e.pointerType !== "mouse") return;
    const r = el.getBoundingClientRect();
    if (!r.width) return;
    const k = el.offsetWidth / r.width;
    el.style.setProperty("--fmi-mx", (e.clientX - r.left) * k + "px");
    el.style.setProperty("--fmi-my", (e.clientY - r.top) * k + "px");
  };

  const rootStyle = {
    ...(accent && COLOR_RE.test(accent.trim()) ? { "--fmi-accent": accent.trim() } : null),
    ...style,
  } as CSSProperties;
  const wrapH = n > 0 ? Math.min(n, MAX_VISIBLE) * ROW : EMPTY_H;
  const heading = hasQuery ? "Best matches" : recent.length > 0 ? "Recent" : "Suggested";
  const status = n > 0 ? (hasQuery ? total + (total === 1 ? " match" : " matches") : n + " suggestions") : "No matches";

  return (
    <div
      ref={rootRef}
      className={"fmi-root" + (className ? " " + className : "")}
      style={rootStyle}
      data-tone={tone === "light" ? "light" : "dark"}
      data-q={hasQuery ? "1" : "0"}
      onPointerMove={onPointerMove}
    >
      <style>{CSS}</style>
      <div className="fmi-glow" aria-hidden="true" />

      <div className="fmi-in">
        <svg
          className="fmi-ico"
          viewBox="0 0 24 24"
          fill="none"
          stroke="currentColor"
          strokeWidth="2"
          strokeLinecap="round"
          aria-hidden="true"
        >
          <circle cx="11" cy="11" r="7" />
          <path d="m20 20-3.6-3.6" />
        </svg>
        <input
          ref={inputRef}
          value={query}
          onChange={(e) => setQuery(e.target.value)}
          onKeyDown={onKeyDown}
          placeholder={placeholder}
          aria-label={label}
          role="combobox"
          aria-expanded={n > 0}
          aria-controls={listId}
          aria-autocomplete="list"
          aria-activedescendant={n > 0 ? uid + "-o" + ai : undefined}
          className="fmi-input"
          type="text"
          autoComplete="off"
          autoCorrect="off"
          autoCapitalize="off"
          spellCheck={false}
          enterKeyHint="go"
        />
        <button
          type="button"
          className="fmi-x"
          data-off={query ? undefined : ""}
          aria-label="Clear search"
          tabIndex={query ? 0 : -1}
          onClick={() => {
            setQuery("");
            inputRef.current?.focus();
          }}
        >
          <Svg d="M18 6 6 18M6 6l12 12" />
        </button>
        <span className="fmi-sweep" aria-hidden="true" />
      </div>

      <div className="fmi-hd" aria-hidden="true">
        <span>{heading}</span>
        <b>{hasQuery && n > 0 ? n + " of " + total : ""}</b>
      </div>

      <div className="fmi-wrap" style={{ height: wrapH }}>
        {n > 0 ? (
          <div className="fmi-list" ref={listRef} role="listbox" id={listId} aria-label={label + " results"}>
            <div className="fmi-pill" aria-hidden="true" data-flash={picked ? "" : undefined} style={{ transform: "translateY(" + ai * ROW + "px)" }} />
            {items.map((it, i) => {
              const hit = new Set(it.indices);
              let k = 0;
              return (
                <div
                  key={it.row}
                  id={uid + "-o" + i}
                  role="option"
                  aria-selected={i === ai}
                  aria-label={it.row}
                  data-row={it.row}
                  data-active={i === ai ? "" : undefined}
                  className="fmi-row"
                  onPointerMove={(e) => {
                    if (e.pointerType === "mouse" && i !== ai) setActive(i);
                  }}
                  onClick={() => {
                    setActive(i);
                    choose(it.row);
                  }}
                >
                  <span className="fmi-lead" aria-hidden="true">
                    {it.recent ? (
                      <Svg d="M12 7v5l3 2M21 12a9 9 0 1 1-18 0 9 9 0 0 1 18 0Z" />
                    ) : (
                      <Svg className="fmi-arrow" d="M5 12h14M13 6l6 6-6 6" />
                    )}
                  </span>
                  <span className="fmi-text" aria-hidden="true">
                    {it.row.split("").map((ch, ci) => {
                      const on = hit.has(ci);
                      return (
                        <span
                          key={ci}
                          className="fmi-c"
                          data-hit={on ? "" : undefined}
                          style={on ? ({ "--k": k++ } as CSSProperties) : undefined}
                        >
                          {ch}
                        </span>
                      );
                    })}
                  </span>
                  {picked === it.row ? (
                    <Svg className="fmi-check" d="m5 12.5 4.5 4.5L19 7.5" />
                  ) : showScore && hasQuery ? (
                    <span className="fmi-score" aria-hidden="true">
                      <span className="fmi-bar">
                        <i style={{ transform: "scaleX(" + Math.max(0.08, it.score / topScore) + ")" }} />
                      </span>
                      {it.score}
                    </span>
                  ) : null}
                </div>
              );
            })}
          </div>
        ) : (
          <div className="fmi-empty">
            <Svg d="M11 4a7 7 0 1 0 0 14 7 7 0 0 0 0-14ZM20 20l-4-4M8.5 8.5l5 5M13.5 8.5l-5 5" />
            <p className="t">
              {emptyText} “{query.trim()}”
            </p>
            <p className="s">Every letter has to appear in order. Try fewer.</p>
            <button
              type="button"
              className="fmi-clear"
              onClick={() => {
                setQuery("");
                inputRef.current?.focus();
              }}
            >
              Clear search
            </button>
          </div>
        )}
      </div>

      <div className="fmi-ft" aria-hidden="true">
        <span>
          <kbd>↑</kbd>
          <kbd>↓</kbd> move
        </span>
        <span>
          <kbd>↵</kbd> pick
        </span>
        <span>
          <kbd>esc</kbd> clear
        </span>
      </div>

      <div className="fmi-sr" role="status" aria-live="polite">
        {status}
      </div>
    </div>
  );
}