Skip to content

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

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

/**
 * @file How a searcher orders the lexical ranker's matches. Search answers
 * only with what the lexical ranker matched, each with its own score and
 * reason. A match never moves past one of another score band (BANDS below)
 * or another kind, doc or not; between runs the lexical order holds. A band
 * can be wide: 55–99 holds keyword matches beside one-word description hits,
 * and a synonym name match can score under 55, so inside a band a weaker match
 * can lead a stronger one when the weights favor it. Inside such a
 * run the learned order places the matches, with these exceptions: matches
 * that scored the same move as one block; an entry the query names leads; in a
 * query of one or two words, the matches on every word keep their lexical
 * order; and an integration's matches that scored the same keep theirs.
 * Below the first result, a block of one domain is ordered by fit (tiesByFit): a part of the first result, then rarer matched
 * words, then the lexical order.
 */

import {entryOf} from './_entries.mjs';
import {fold, nameWords, words} from './_query-words.mjs';
import {searchedComponentsOf} from './_result.mjs';

/** @typedef {import('./_entries.mjs').EntryTable} EntryTable */

/**
 * Where each lexical band starts, highest first: the whole query as a name,
 * as a keyword, as a phrase in a title, a title in the query, every word
 * matched, a strong partial match, a name or keyword match, and below that,
 * prose alone.
 */
const BANDS = [195, 188, 170, 160, 151, 100, 55];
/** The lowest score of the every-word top tier. */
const FULL_COVERAGE = 151;

/** @param {number} score */
export const bandOf = score => {
  const i = BANDS.findIndex(floor => score >= floor);
  return i === -1 ? BANDS.length : i;
};

/**
 * The search response: the lexical matches, each band in the learned order.
 * Nothing is added or dropped, so the count and the scores stay the lexical
 * ranker's; only the order inside a band, and so which matches fill the
 * limit, changes.
 * @param {EntryTable} table
 * @param {number[]} order entry positions, best first, by the searcher's weights
 * @param {import('./search.type.mjs').SearchResponse} lexical every lexical match
 * @param {string} query
 * @param {number} limit
 * @returns {import('./search.type.mjs').SearchResponse}
 */
export function orderMatches(table, order, lexical, query, limit) {
  const all = lexical.data.results;
  /** @type {Map<number, number>} */
  const place = new Map(order.map((k, i) => [k, i]));
  // Runs of consecutive lexical matches in one band and of one kind (doc or
  // not) are the only places the learned order acts: a match never crosses
  // into another band, or past a doc or a non-doc the lexical ranker placed.
  let run = -1;
  /** @type {string} */
  let last = '';
  const items = all.map((res, i) => {
    // Each match's own band: the lexical merge can place a weaker match
    // ahead of a stronger doc, and the two must never share a run.
    const key = `${bandOf(res.score ?? 0)}:${res.domain === 'doc'}`;
    if (key !== last) {
      run++;
      last = key;
    }
    const k = entryOf(table, res);
    return {
      res,
      i,
      band: run,
      learned: k === undefined ? Infinity : (place.get(k) ?? Infinity),
    };
  });
  const named = (/** @type {Item} */ it) =>
    (it.res.score ?? 0) >= 95 &&
    /^(exact name|plural of the name|name )/.test(it.res.reason ?? '');
  // Matches the lexical ranker scored the same move as one block, in its
  // order; the learned position of the block's first match places the block
  // in its run (not its best member's, which would let one strong member lift
  // a whole block of weak ones), and an entry the query names leads its run.
  // Moving each match on its own breaks search's existing rules for tied
  // matches (`file required` leads with Field, `ci` with the integration
  // check) and grows answers, so ties move together; where the block lands is
  // measured as spec:AST-083 FR6 requires.
  /** @type {Map<string, number>} */
  const block = new Map();
  const blockOf = (/** @type {Item} */ it) => `${it.band}:${it.res.score}`;
  for (const it of items) {
    const at = named(it) ? -1 : it.learned;
    const k = blockOf(it);
    if (!block.has(k) || at === -1) block.set(k, at);
  }
  let ranked = [...items].sort(
    (x, y) =>
      x.band - y.band ||
      (block.get(blockOf(x)) ?? 0) - (block.get(blockOf(y)) ?? 0) ||
      x.i - y.i,
  );
  if (words(query).length <= 2) {
    ranked = keepLexical(ranked, it => (it.res.score ?? 0) >= FULL_COVERAGE);
  }
  ranked = integrationTies(ranked);
  // Each whole tie is ordered by fit before the limit, so every limit shows
  // the top of one answer.
  const shown = tiesByFit(ranked, table, blockOf).slice(0, limit);
  const response = {
    ...lexical,
    data: {...lexical.data, results: shown.map(it => it.res)},
  };
  const searched = searchedComponentsOf.get(lexical);
  if (searched) searchedComponentsOf.set(response, searched);
  return /** @type {import('./search.type.mjs').SearchResponse} */ (response);
}

/**
 * @typedef {{res: any, i: number, band: number, learned: number}} Item
 */

/** How many parts of the first result lead their ties, across an answer. */
const PARTS_FIRST = 2;

/**
 * Below the first result, matches the lexical ranker scored the same keep
 * their block but are no longer in name order inside it: a part or sibling of
 * the first result leads (TableRow after Table), then the match whose matched
 * words are rarer in the catalog, so a match on a common word alone sits
 * below one on the query's telling words. Nothing crosses a block.
 * @param {Item[]} ranked
 * @param {EntryTable} table
 * @param {(item: Item) => string} blockOf
 * @returns {Item[]}
 */
function tiesByFit(ranked, table, blockOf) {
  if (ranked.length < 3) return ranked;
  const first = nameWords(String(ranked[0].res.name ?? '')).map(fold);
  const idf = table.fields.desc.idf;
  const rarest = Math.max(0, ...idf.values());
  /** @param {Item} it */
  const related = it => {
    // A part's name words start with the first result's whole name words:
    // TableRow is a part of Table, Table is no part of Tab.
    const name = nameWords(String(it.res.name ?? '')).map(fold);
    return (
      (first.length > 0 &&
        name.length > first.length &&
        first.every((w, n) => name[n] === w)) ||
      /^member of /.test(it.res.reason ?? '')
    );
  };
  /** @param {Item} it */
  const rarity = it => {
    const m = /^matches \d+\/\d+ terms: (.*)$/.exec(it.res.reason ?? '');
    if (!m) return 0;
    let sum = 0;
    // A matched term counts by its alphanumeric parts (`three-dot`), and a
    // part the catalog never uses is as rare as a word can be.
    for (const t of m[1].split(', '))
      for (const part of words(t)) sum += idf.get(fold(part)) ?? rarest;
    return sum;
  };
  const out = [ranked[0]];
  let parts = 0;
  for (let i = 1; i < ranked.length;) {
    let j = i;
    const at = (/** @type {Item} */ it) => `${blockOf(it)}:${it.res.domain}`;
    while (j < ranked.length && at(ranked[j]) === at(ranked[i])) j++;
    const run = ranked.slice(i, j);
    if (run.length > 1) {
      const keyed = run.map((it, n) => {
        // At most PARTS_FIRST parts lead, across the answer, so a family
        // with many parts does not crowd out what else the query matched.
        const r = parts < PARTS_FIRST && related(it);
        if (r) parts++;
        return {it, n, r, f: rarity(it)};
      });
      keyed.sort((a, b) => Number(b.r) - Number(a.r) || b.f - a.f || a.n - b.n);
      out.push(...keyed.map(k => k.it));
    } else out.push(...run);
    i = j;
  }
  return out;
}

/**
 * The matches `pick` selects keep the places they hold, filled in lexical
 * order.
 * @param {Item[]} items
 * @param {(item: Item) => boolean} pick
 * @returns {Item[]}
 */
function keepLexical(items, pick) {
  /** @type {number[]} */
  const at = [];
  items.forEach((it, j) => pick(it) && at.push(j));
  if (at.length < 2) return items;
  const sorted = at.map(j => items[j]).sort((a, b) => a.i - b.i);
  const out = [...items];
  at.forEach((j, n) => (out[j] = sorted[n]));
  return out;
}

/**
 * An integration's matches that the lexical ranker scored the same keep its
 * order among themselves: they have no cards, so the learned order would only
 * guess between them.
 * @param {Item[]} items
 * @returns {Item[]}
 */
export function integrationTies(items) {
  /** @type {Map<number, number[]>} */
  const groups = new Map();
  items.forEach((it, j) => {
    const pkg = it.res.package ?? '';
    if (!pkg || pkg.startsWith('@astryxdesign/')) return;
    const key = it.res.score ?? 0;
    if (!groups.has(key)) groups.set(key, []);
    /** @type {number[]} */ (groups.get(key)).push(j);
  });
  const out = [...items];
  for (const at of groups.values()) {
    if (at.length < 2) continue;
    const sorted = at.map(j => items[j]).sort((a, b) => a.i - b.i);
    at.forEach((j, n) => (out[j] = sorted[n]));
  }
  return out;
}