Skip to content

An open source design system that's fully customizable and agent ready

TypeScript
16.4 KB
Raw Blame
// Copyright (c) Meta Platforms, Inc. and affiliates.

/**
 * @file Order the suggestions a failed lookup prints, best first.
 *
 * A failed `component`, `template` or `docs` lookup already knows which
 * entries to suggest; this module decides their order, so the entry the
 * caller most likely meant comes first. Asked for the closest entries only,
 * it also cuts a list where the matches get weaker. It never makes a list
 * longer.
 *
 * Names are compared as words: `DropdownMenuItem`, `dropdown-menu-item` and
 * `Dropdown Menu Items` all read as `dropdown menu item`.
 *
 * @input  the name the caller typed and the candidate entries
 * @output the entries, reordered, and cut when asked
 * @position lib: shared by the component, template and docs lookup errors
 */

import {levenshteinDistance} from './levenshtein.mjs';

/**
 * The score of a near name (nearNameSlips), less a little per slip: above any
 * name that carries only some of the typed words, below one that carries all
 * of them.
 */
const NEAR_NAME_SCORE = 19.6;
/** The score a synonym match gets: an exact keyword's. */
const SYNONYM_SCORE = 90;
/** The score a name with exactly the typed words gets: an exact name's. */
const SAME_WORDS_SCORE = 100;

/**
 * A word with one trailing plural `s` removed (`tabs` → `tab`), leaving short
 * words and `ss` endings alone.
 * @param {string} word
 * @returns {string}
 */
function singular(word) {
  return word.length > 3 && word.endsWith('s') && !word.endsWith('ss')
    ? word.slice(0, -1)
    : word;
}

/**
 * A name's words, lowercase and singular: camelCase, PascalCase, kebab-case,
 * snake_case, slashes and spaces all split.
 * @param {string} text
 * @returns {string[]}
 */
export function nameWords(text) {
  /** @type {string[]} */
  const words = [];
  for (const part of String(text ?? '').split(/[^A-Za-z0-9]+/)) {
    if (!part) continue;
    const found =
      part.match(/[A-Z]+(?=[A-Z][a-z])|[A-Z]?[a-z]+|[A-Z]+|[0-9]+/g) ?? [];
    for (const w of found) words.push(singular(w.toLowerCase()));
  }
  return words;
}

/**
 * How closely one candidate name matches what the caller typed; higher is
 * closer. Tiers, best first: the same words; every typed word present; some
 * typed word present; none. Within a tier, more of the typed words and more of
 * the candidate's own words matched rank higher, and a name that starts with
 * the typed name (or the reverse) gets a small lift. With `typos`, a near name
 * (one or two slips from the typed name) ranks just below the names that
 * carry every typed word.
 * @param {string[]} typed - {@link nameWords} of the typed name
 * @param {string} name
 * @param {{typos?: boolean}} [options]
 * @returns {number}
 */
function affinityOf(typed, name, {typos = false} = {}) {
  const words = nameWords(name);
  if (typed.length === 0 || words.length === 0) return 0;
  const typedJoined = typed.join('');
  const joined = words.join('');
  if (joined === typedJoined) return 40;
  const slips = typos ? nearNameSlips(typedJoined, joined) : 0;
  const near = slips > 0 ? NEAR_NAME_SCORE - slips * 0.2 : 0;
  const have = new Set(words);
  const want = new Set(typed);
  const covered = typed.filter(w => have.has(w)).length / typed.length;
  const precise = words.filter(w => want.has(w)).length / words.length;
  const prefix =
    joined.startsWith(typedJoined) || typedJoined.startsWith(joined) ? 1 : 0;
  const tier = covered === 1 ? 2 : covered > 0 ? 1 : 0;
  // A near name keeps its word score when that is higher: a name that also
  // carries every typed word ranks among the other full matches.
  return Math.max(
    near,
    tier * 10 + covered * 4 + precise * 2 + prefix + precise * 0.01,
  );
}

/**
 * How many slips separate a typed name from a candidate, both with their
 * words joined, when it is a near name: an edit or two adjacent letters
 * swapped count as one slip, one slip is allowed from five letters and two from
 * eight. Zero when it is not a near name.
 * @param {string} typed
 * @param {string} name
 * @returns {number}
 */
function nearNameSlips(typed, name) {
  const shorter = Math.min(typed.length, name.length);
  const cap = shorter >= 8 ? 2 : shorter >= 5 ? 1 : 0;
  if (cap === 0 || Math.abs(typed.length - name.length) > cap) return 0;
  const slips = levenshteinDistance(typed, name, cap, {swaps: true});
  return slips <= cap ? slips : 0;
}

/**
 * The items scored against the typed name, closest first; equal matches keep
 * their original order.
 * @template T
 * @param {string} typedName
 * @param {T[]} items
 * @param {(item: T) => Array<string | undefined>} namesOf
 * @param {{typos?: boolean}} [options]
 * @returns {Array<{item: T, best: number}>}
 */
function scoreByAffinity(typedName, items, namesOf, options = {}) {
  const typed = nameWords(typedName);
  const scored = items.map((item, index) => {
    let best = 0;
    for (const name of namesOf(item)) {
      if (name) best = Math.max(best, affinityOf(typed, name, options));
    }
    return {item, index, best};
  });
  scored.sort((a, b) => b.best - a.best || a.index - b.index);
  return scored;
}

/**
 * The same items, closest to the typed name first; each item is as close as
 * its closest name. Equal matches keep their original order.
 *
 * With `closest`, the list also stops where the matches get weaker. Only
 * typed words longer than one character count here. When the best item
 * carries every such word, only the items that carry every one of them stay;
 * when it carries some of them, the items that carry none are left out. When
 * no item carries one, nothing is left out. The list only ever gets shorter,
 * and its order does not change.
 *
 * With `typos`, a near name (one or two slips from the typed name, as
 * `ButonGroup` or `ButtonGorup` for ButtonGroup) ranks just below the names
 * that carry every typed word and above the rest. With `closest` too, near
 * names stay in the list whatever the cut leaves out, and the list is never
 * longer than it is without `typos`.
 * @template T
 * @param {string} typedName
 * @param {T[]} items
 * @param {(item: T) => Array<string | undefined>} namesOf
 * @param {{closest?: boolean, typos?: boolean}} [options]
 * @returns {T[]}
 */
export function orderByAffinity(typedName, items, namesOf, options = {}) {
  if (!options.typos) return orderByWords(typedName, items, namesOf, options);
  const scored = scoreByAffinity(typedName, items, namesOf, {typos: true});
  if (!options.closest) return scored.map(s => s.item);
  const kept = new Set(orderByWords(typedName, items, namesOf, options));
  return scored
    .filter(s => kept.has(s.item) || isNearScore(s.best))
    .slice(0, kept.size)
    .map(s => s.item);
}

/**
 * Whether a score is a near name's.
 * @param {number} score
 */
const isNearScore = score => score < 20 && score > NEAR_NAME_SCORE - 1;

/**
 * {@link orderByAffinity} without `typos`.
 * @template T
 * @param {string} typedName
 * @param {T[]} items
 * @param {(item: T) => Array<string | undefined>} namesOf
 * @param {{closest?: boolean}} options
 * @returns {T[]}
 */
function orderByWords(typedName, items, namesOf, options) {
  const scored = scoreByAffinity(typedName, items, namesOf);
  if (!options.closest) return scored.map(s => s.item);
  // One-letter words (`a` in `a11y`, `use-a-theme`) say nothing about which
  // entry was meant, so the cut counts only the longer typed words.
  const words = nameWords(typedName).filter(w => w.length > 1);
  const tierOf = (/** @type {T} */ item) => {
    let best = 0;
    for (const name of namesOf(item)) {
      if (name) best = Math.max(best, affinityOf(words, name));
    }
    // Tiers: 1 some typed word, 2 every typed word, 4 the same words.
    return Math.floor(best / 10);
  };
  const tiers = scored.map(s => tierOf(s.item));
  const top = Math.max(0, ...tiers);
  if (top === 0) return scored.map(s => s.item);
  const need = Math.min(top, 2);
  return scored.filter((_, i) => tiers[i] >= need).map(s => s.item);
}

/**
 * Docs route suggestions, closest to the typed route first. When every
 * suggestion sits under one namespace the typed route also starts with, that
 * shared part is left out of the comparison: it says nothing about which page
 * was meant. Equal matches keep their order. `closest` stops the list where
 * the matches get weaker, as in {@link orderByAffinity}.
 * @template {{name: string}} T
 * @param {string} topic - the typed route
 * @param {T[]} suggestions
 * @param {{closest?: boolean}} [options]
 * @returns {T[]}
 */
export function orderRouteSuggestions(topic, suggestions, options = {}) {
  let shared = suggestions.length > 0 ? suggestions[0].name : '';
  for (const {name} of suggestions) {
    while (shared && !name.startsWith(shared)) shared = shared.slice(0, -1);
  }
  const namespace = shared.slice(0, shared.lastIndexOf('/') + 1);
  return namespace && topic.startsWith(namespace)
    ? orderByAffinity(
        topic.slice(namespace.length),
        suggestions,
        s => [s.name.slice(namespace.length)],
        options,
      )
    : orderByAffinity(topic, suggestions, s => [s.name], options);
}

/** Library names a synonym may start with (`MUI TextField`). */
const LIBRARY_WORDS = new Set([
  'mui',
  'material',
  'chakra',
  'ant',
  'antd',
  'radix',
  'bootstrap',
  'mantine',
  'shadcn',
  'headless',
  'aria',
  'react',
]);

/**
 * The components whose synonyms name what was typed. A synonym matches when
 * its words, with or without a leading library name, are the typed words
 * (`MUI TextField` matches `MUI TextField`, `TextField` and `text-field`).
 * @param {string} needle
 * @param {Record<string, {synonyms?: string[]}>} cards - component name → its search card
 * @returns {Set<string>}
 */
export function synonymMatches(needle, cards) {
  const typed = nameWords(needle).join('');
  /** @type {Set<string>} */
  const found = new Set();
  if (!typed) return found;
  for (const [name, card] of Object.entries(cards ?? {})) {
    for (const synonym of card?.synonyms ?? []) {
      const words = nameWords(synonym);
      const whole = words.join('');
      while (words.length > 1 && LIBRARY_WORDS.has(words[0])) words.shift();
      if (whole === typed || words.join('') === typed) {
        found.add(name);
        break;
      }
    }
  }
  return found;
}

/** Words that name a structural part of a component (`<Family>Footer`). */
const PART_WORDS = new Set([
  'header',
  'footer',
  'body',
  'content',
  'title',
  'heading',
  'description',
  'item',
  'trigger',
  'action',
  'close',
  'group',
  'cell',
  'row',
  'column',
  'label',
  'icon',
  'root',
  'wrapper',
]);

/** Part words that name the same slot of a component family. */
const SAME_PART = /** @type {Record<string, string[]>} */ ({
  item: ['item', 'option'],
  option: ['option', 'item'],
  header: ['header', 'heading', 'title'],
  heading: ['heading', 'header', 'title'],
  title: ['title', 'heading', 'header'],
});

/**
 * A suggestion score for a component whose name shares the typed compound
 * name's words, on the same scale as `searchComponents`, or null. It covers
 * part names that do not exist: the family part named with other words
 * (`PickerItem` → `PickerOption`), the part named without its family's
 * first word (`RailItem` → `SideRailItem`), the part named without its family's
 * middle word (`FactItem` → `FactListItem`), and the parent of a structural
 * part that is not its own component (`SheetFooter` → `Sheet`, but not
 * `SheetMusic`).
 * @param {string[]} typed - {@link nameWords} of the typed name
 * @param {string} name
 * @returns {{score: number, reason: string} | null}
 */
function compoundMatch(typed, name) {
  if (typed.length < 2) return null;
  const words = nameWords(name);
  const n = words.length;
  const t = typed.length;
  const same = (/** @type {string[]} */ a, /** @type {string[]} */ b) =>
    a.length === b.length && a.every((w, i) => w === b[i]);
  if (
    n >= 2 &&
    same(words.slice(0, -1), typed.slice(0, -1)) &&
    (SAME_PART[typed[t - 1]] ?? []).includes(words[n - 1])
  ) {
    return {score: 79, reason: 'same part of the family'};
  }
  if (n > t && same(words.slice(n - t), typed)) {
    return {score: 78, reason: 'name ends with the words typed'};
  }
  if (n > t && words[0] === typed[0] && words[n - 1] === typed[t - 1]) {
    return {score: 77, reason: 'same part of the family'};
  }
  if (
    n < t &&
    same(typed.slice(0, n), words) &&
    typed.slice(n).every(w => PART_WORDS.has(w))
  ) {
    return {score: 72, reason: 'the family this part belongs to'};
  }
  return null;
}

/**
 * Rank component suggestions for a name that resolved to nothing.
 *
 * Every component `searchComponents` scored keeps its score. A component whose
 * name has exactly the typed words (`chat-messages` for `ChatMessage`) scores
 * like an exact name; one of whose synonyms is the typed name (see
 * {@link synonymMatches}) like an exact keyword; one whose name shares the
 * typed compound name's words (see {@link compoundMatch}) just below a
 * one-letter typo of a name. Equal scores put synonym matches first, then order by how many of the typed words the
 * name carries, then by how early the keyword that matched sits in the
 * component's keywords, then by edit distance, then by shared leading letters,
 * then by name. The caller decides how many to print.
 * @param {string} needle - the typed component name (no `XDS` prefix)
 * @param {Array<{name: string, score: number, reason: string, keywordAt?: number}>} results - `searchComponents` output
 * @param {string[]} allNames - every component name
 * @param {Set<string>} [synonyms] - {@link synonymMatches} for the typed name
 * @returns {Array<{name: string, score: number, reason: string}>}
 */
export function rankComponentSuggestions(
  needle,
  results,
  allNames,
  synonyms = new Set(),
) {
  const term = needle.toLowerCase();
  const typed = nameWords(needle);
  /** @type {Map<string, {name: string, score: number, reason: string, keywordAt: number}>} */
  const byName = new Map();
  for (const r of results) {
    byName.set(r.name, {
      name: r.name,
      score: r.score,
      reason: r.reason,
      keywordAt: r.keywordAt ?? Infinity,
    });
  }
  // The typed words are a name's words (`chat-messages` is `ChatMessage`):
  // that name is meant, ahead of every rule below.
  const joined = typed.join('');
  for (const name of allNames) {
    if (joined && nameWords(name).join('') === joined) {
      byName.set(name, {
        name,
        score: SAME_WORDS_SCORE,
        reason: 'same name',
        keywordAt: -1,
      });
    }
  }
  for (const name of synonyms) {
    if (!allNames.includes(name)) continue;
    const prior = byName.get(name);
    if (!prior || prior.score < SYNONYM_SCORE) {
      byName.set(name, {
        name,
        score: SYNONYM_SCORE,
        reason: 'another name for it',
        keywordAt: Infinity,
      });
    }
  }
  for (const name of allNames) {
    const match = compoundMatch(typed, name);
    if (!match) continue;
    const prior = byName.get(name);
    if (!prior || match.score > prior.score) {
      byName.set(name, {
        name,
        score: match.score,
        reason: match.reason,
        keywordAt: Infinity,
      });
    }
  }
  /** @param {string} name */
  const lead = name => {
    const lower = name.toLowerCase();
    let i = 0;
    while (i < term.length && i < lower.length && term[i] === lower[i]) i++;
    return i / Math.max(term.length, lower.length);
  };
  /**
   * How many typed words the name carries, whole or as a word's start; the
   * last typed word, the one a compound name is a kind of (`PlaceInput` is an
   * input), counts a little more.
   */
  const shared = (/** @type {string} */ name) => {
    const words = nameWords(name);
    const has = (/** @type {string} */ t) =>
      words.some(
        w =>
          w === t ||
          (Math.min(w.length, t.length) >= 3 &&
            (w.startsWith(t) || t.startsWith(w))),
      );
    const count = typed.filter(has).length;
    return typed.length > 1 && has(typed[typed.length - 1])
      ? count + 0.5
      : count;
  };
  return [...byName.values()]
    .map(r => ({
      ...r,
      synonym: synonyms.has(r.name) ? 1 : 0,
      shared: shared(r.name),
      distance: levenshteinDistance(term, r.name.toLowerCase()),
      lead: lead(r.name),
    }))
    .sort(
      (a, b) =>
        b.score - a.score ||
        b.synonym - a.synonym ||
        b.shared - a.shared ||
        a.keywordAt - b.keywordAt ||
        a.distance - b.distance ||
        b.lead - a.lead ||
        a.name.localeCompare(b.name),
    )
    .map(({name, score, reason}) => ({name, score, reason}));
}