fzf.ts

const SCORE_MATCH = 16;
const SCORE_GAP_START = -3;
const SCORE_GAP_EXTENSION = -1;
const BONUS_BOUNDARY = SCORE_MATCH / 2;
const BONUS_BOUNDARY_WHITE = BONUS_BOUNDARY + 2;
const BONUS_BOUNDARY_DELIMITER = BONUS_BOUNDARY + 1;
const BONUS_CAMEL_OR_NUMBER = BONUS_BOUNDARY + SCORE_GAP_EXTENSION;
const BONUS_CONSECUTIVE = -(SCORE_GAP_START + SCORE_GAP_EXTENSION);
const BONUS_FIRST_CHAR_MULTIPLIER = 2;

type FzfMatch = {
  score: number;
  start: number;
  end: number;
};

type CharClass = 'white' | 'delimiter' | 'lower' | 'upper' | 'number' | 'letter' | 'nonWord';

function normalizeSearchText(value: string) {
  return value
    .normalize('NFKD')
    .replace(/[\u0300-\u036f]/g, '')
    .toLowerCase()
    .replace(/[^a-z0-9]+/g, ' ')
    .trim()
    .replace(/\s+/g, ' ');
}

function charClassOf(char: string): CharClass {
  if (/\s/.test(char)) return 'white';
  if (/[/,:;|_\-.]/.test(char)) return 'delimiter';
  if (/[a-z]/.test(char)) return 'lower';
  if (/[A-Z]/.test(char)) return 'upper';
  if (/[0-9]/.test(char)) return 'number';
  if (/\p{L}/u.test(char)) return 'letter';
  return 'nonWord';
}

function bonusFor(prevClass: CharClass, charClass: CharClass) {
  if (charClass !== 'white') {
    if (prevClass === 'white') return BONUS_BOUNDARY_WHITE;
    if (prevClass === 'delimiter') return BONUS_BOUNDARY_DELIMITER;
    if (prevClass === 'nonWord') return BONUS_BOUNDARY;
  }

  if (
    (prevClass === 'lower' && charClass === 'upper') ||
    (prevClass !== 'number' && charClass === 'number')
  ) {
    return BONUS_CAMEL_OR_NUMBER;
  }

  if (charClass === 'white') return BONUS_BOUNDARY_WHITE;
  if (charClass === 'delimiter' || charClass === 'nonWord') return BONUS_BOUNDARY;
  return 0;
}

function bonusAt(value: string, index: number) {
  if (index === 0) return BONUS_BOUNDARY_WHITE;
  return bonusFor(charClassOf(value[index - 1]), charClassOf(value[index]));
}

function gapPenalty(gap: number) {
  if (gap <= 0) return 0;
  return SCORE_GAP_START + SCORE_GAP_EXTENSION * (gap - 1);
}

function fzfScore(value: string, query: string): FzfMatch | null {
  const normalizedValue = normalizeSearchText(value);
  const normalizedQuery = normalizeSearchText(query);

  if (!normalizedQuery) {
    return { score: 0, start: 0, end: 0 };
  }
  if (!normalizedValue || normalizedQuery.length > normalizedValue.length) {
    return null;
  }

  type Cell = {
    score: number;
    start: number;
  };

  let previousRow: Array<Cell | null> = [];

  for (let queryIndex = 0; queryIndex < normalizedQuery.length; queryIndex += 1) {
    const row: Array<Cell | null> = Array.from({ length: normalizedValue.length }, () => null);
    const queryChar = normalizedQuery[queryIndex];

    for (let valueIndex = queryIndex; valueIndex < normalizedValue.length; valueIndex += 1) {
      if (normalizedValue[valueIndex] !== queryChar) continue;

      const boundaryBonus = bonusAt(normalizedValue, valueIndex);

      if (queryIndex === 0) {
        row[valueIndex] = {
          score: SCORE_MATCH + boundaryBonus * BONUS_FIRST_CHAR_MULTIPLIER,
          start: valueIndex,
        };
        continue;
      }

      let best: Cell | null = null;
      for (let previousIndex = queryIndex - 1; previousIndex < valueIndex; previousIndex += 1) {
        const previous = previousRow[previousIndex];
        if (!previous) continue;

        const isConsecutive = previousIndex === valueIndex - 1;
        const score =
          previous.score +
          SCORE_MATCH +
          (isConsecutive ? Math.max(boundaryBonus, BONUS_CONSECUTIVE) : boundaryBonus) +
          gapPenalty(valueIndex - previousIndex - 1);

        if (
          !best ||
          score > best.score ||
          (score === best.score && valueIndex - previous.start < valueIndex - best.start)
        ) {
          best = {
            score,
            start: previous.start,
          };
        }
      }

      row[valueIndex] = best;
    }

    if (!row.some(Boolean)) return null;
    previousRow = row;
  }

  let bestMatch: FzfMatch | null = null;
  for (let valueIndex = 0; valueIndex < previousRow.length; valueIndex += 1) {
    const cell = previousRow[valueIndex];
    if (!cell) continue;

    const match = {
      score: cell.score,
      start: cell.start,
      end: valueIndex + 1,
    };
    const matchSpan = match.end - match.start;
    const bestSpan = bestMatch ? bestMatch.end - bestMatch.start : Infinity;

    if (
      !bestMatch ||
      match.score > bestMatch.score ||
      (match.score === bestMatch.score && matchSpan < bestSpan) ||
      (match.score === bestMatch.score && matchSpan === bestSpan && match.start < bestMatch.start)
    ) {
      bestMatch = match;
    }
  }

  return bestMatch;
}

export function getFuzzyTextScore(value: string, query: string) {
  return fzfScore(value, query)?.score ?? null;
}

export function matchesFuzzyText(value: string, query: string) {
  return getFuzzyTextScore(value, query) !== null;
}

export function rankFuzzyMatches<T>(items: T[], query: string, getValue: (item: T) => string) {
  return items
    .map((item, index) => ({ item, index, match: fzfScore(getValue(item), query) }))
    .filter((entry): entry is { item: T; index: number; match: FzfMatch } => entry.match !== null)
    .sort((a, b) => {
      const aSpan = a.match.end - a.match.start;
      const bSpan = b.match.end - b.match.start;
      return (
        b.match.score - a.match.score ||
        aSpan - bSpan ||
        a.match.start - b.match.start ||
        a.index - b.index
      );
    })
    .map((entry) => entry.item);
}