An open source design system that's fully customizable and agent ready
TypeScript
// Copyright (c) Meta Platforms, Inc. and affiliates.
/**
* @file build's block picker: ranks every block in the catalog for a request
* by meaning, from each block's own docs, and keeps build's own count.
*
* @input The request, build's signals for it (`kitSignals`: the blocks the kit
* names, search's block results with their scores and coverage, the block
* catalog and the components), and the picker weights
* (`blocks.weights.json` beside this file, read by the adapter): a
* vocabulary of stemmed words and word pairs with their idf (x1024), two
* signed byte matrices that map request words and doc words into one space, the
* lexical weight, the blocks the matrices were fitted with, and the ranking
* coefficients.
* @output `pickBlocks(...)`: block names, best first, as many as build's own
* list, and an entry (real score and reason) for each listed block search
* did not return.
* @position api/build/blocks; tree.mjs's main searcher calls it between
* kitSignals (kit/signals.mjs) and kitAnswer (kit/answer.mjs). Pure: no file,
* network, or environment access.
*
* How it scores. A block is described by its own docs only: its name, display
* name and description, and its component's name and keywords. The request
* and each block's docs become weighted word vectors (stemmed content words
* and adjacent pairs, (1 + ln count) x idf, unit length). Their match is the
* request's vector through the request matrix, against the docs' vector
* through the doc matrix, plus the lexical weight times their plain overlap
* (cosine), so a block the weights were never fitted with, such as a new one,
* is scored from its docs the same way. The candidates are the best matches,
* build's own blocks, search's first results, and the best plain overlaps.
* Each candidate's final score adds the ranking coefficients times: its match
* relative to the best, its place among the matches, its lead over the
* second-best match, whether the weights know it, its plain overlap,
* search's score and share of the request matched and place, whether build
* names it and where, how strongly the request names its component, and
* whether it is its component's general example. A block the request writes
* out by its exact name, and a block whose package is not Core's, keep the
* slot build gave them; the best of the others fill the remaining slots.
*/
import {STOPWORDS} from '../../search/_query.mjs';
/**
* @typedef {object} BlockPickerWeights
* @property {string[]} vocab stemmed words and `a_b` word pairs
* @property {number[]} idf one per vocab entry, x1024
* @property {number} dims the width of the shared space
* @property {string} request base64 bytes, vocab.length x dims, row-major, each a signed weight offset by 128
* @property {number} requestScale
* @property {string} doc base64 bytes, vocab.length x dims, row-major, each a signed weight offset by 128
* @property {number} docScale
* @property {number} lexical the weight of the plain overlap
* @property {string[]} known the blocks the matrices were fitted with
* @property {Record<string, number>} theta the ranking coefficients
*
* @typedef {import('../kit/signals.mjs').BlockScore} BlockScore
* @typedef {{name: string, package?: string, displayName?: string, description?: string, command?: string}} CatalogBlock
* @typedef {{name: string, keywords?: string[]}} CatalogComponent
* @typedef {import('../../search/search.type.mjs').SearchResultEntry} SearchResultEntry
*/
/**
* Generic English function words, search's stopwords, and words every build
* request or block shares: never a reason to tie a block to a request.
*/
const STOP = new Set([
...STOPWORDS,
...(
'about above across after again against all along already also although ' +
'always am among amongst an and another any anyone anything anywhere are ' +
'around as at be because been before behind being below beneath beside ' +
'besides between beyond both but by can could despite did do does doing ' +
'down during each either else enough even ever every everyone everything ' +
'everywhere except few following for from further had has have having he ' +
'her here hers herself him himself his how however if in inside instead ' +
'into is it its itself just least less little lot lots many may maybe me ' +
'might more most much must my myself near neither never no nobody none ' +
'nor not nothing now nowhere of off often on once one ones only onto or ' +
'other others ought our ours ourselves out outside over own past per ' +
'perhaps quite rather same several shall she should since so some someone ' +
'something sometimes somewhat somewhere still such than that the their ' +
'theirs them themselves then there these they this those though through ' +
'throughout thus till to together too toward towards under underneath ' +
'unless unlike until up upon usually very via was we were what whatever ' +
'when whenever where whereas whether which whichever while who whoever ' +
'whom whomever whose why will with within without would yet you your ' +
'yours yourself yourselves'
).split(' '),
...(
'a an the and or of for to in on with by at from as is are be this that ' +
'it its my our your their me we you i into via per each all any some page ' +
'app screen ui view build make create need want like show shows showing ' +
'using use one two new add list item items basic simple showcase example ' +
'default variant'
).split(' '),
]);
/**
* Words after which the rest of a request is where the new piece goes, not
* the piece itself ("a filter bar ABOVE the table").
*/
const CONTEXT = new Set(
(
'in on inside within into above below under beneath next beside to for ' +
'with and from of near over across along around after before at'
).split(' '),
);
/** How many of each kind of candidate the picker weighs. */
const POOL = {matches: 60, searched: 60, overlaps: 20};
/** How many matches carry a place; the rest share the last one's match. */
const TOP = 80;
/**
* A word with a plural or verb ending removed (words over four letters):
* "-ies" becomes "-y"; "-es" goes only after s, x, z, ch, or sh; otherwise a
* final "s" goes, but never after another "s"; then "-ing" or "-ed".
* @param {string} w
* @returns {string}
*/
export function stemOf(w) {
if (w.length <= 4) return w;
if (w.endsWith('ies')) return `${w.slice(0, -3)}y`;
if (/(?:s|x|z|ch|sh)es$/.test(w)) return w.slice(0, -2);
if (w.endsWith('s') && !w.endsWith('ss')) return w.slice(0, -1);
if (w.endsWith('ing')) return w.slice(0, -3);
if (w.endsWith('ed')) return w.slice(0, -2);
return w;
}
/**
* An identifier's words, lowercase: "SideNavNestedItems" -> side, nav,
* nested, items.
* @param {string} text
* @returns {string[]}
*/
export function wordsOf(text) {
return String(text)
.replace(/([a-z0-9])([A-Z])/g, '$1 $2')
.replace(/([A-Z])([A-Z][a-z])/g, '$1 $2')
.toLowerCase()
.split(/[^a-z0-9]+/)
.filter(Boolean);
}
/**
* A text's stemmed content words, then its adjacent pairs as `a_b`.
* @param {string} text
* @returns {string[]}
*/
export function termsOf(text) {
const words = (
String(text)
.toLowerCase()
.match(/[a-z0-9]{2,}/g) ?? []
)
.filter(w => !STOP.has(w))
.map(stemOf);
const out = [...words];
for (let i = 0; i + 1 < words.length; i++)
out.push(`${words[i]}_${words[i + 1]}`);
return out;
}
/**
* A text's sparse unit vector over the vocabulary: (1 + ln count) x idf.
* @param {string[]} terms
* @param {{index: Map<string, number>, idf: Float64Array}} d
* @returns {Map<number, number>}
*/
function vectorOf(terms, d) {
/** @type {Map<number, number>} */
const counts = new Map();
for (const t of terms) {
const i = d.index.get(t);
if (i !== undefined) counts.set(i, (counts.get(i) ?? 0) + 1);
}
/** @type {Map<number, number>} */
const v = new Map();
let sq = 0;
for (const [i, c] of counts) {
const x = (1 + Math.log(c)) * d.idf[i];
v.set(i, x);
sq += x * x;
}
const norm = Math.sqrt(sq) || 1;
for (const [i, x] of v) v.set(i, x / norm);
return v;
}
/**
* The vocabulary index and idf, read once per weights object, and each matrix
* row decoded when a side first uses it.
* @type {WeakMap<BlockPickerWeights, {index: Map<string, number>, idf: Float64Array, rows: Map<string, Int8Array>}>}
*/
const vocabularies = new WeakMap();
/** @param {BlockPickerWeights} weights */
function vocabularyOf(weights) {
let v = vocabularies.get(weights);
if (!v) {
v = {
index: new Map(weights.vocab.map((w, i) => [w, i])),
idf: Float64Array.from(weights.idf, x => x / 1024),
rows: new Map(),
};
vocabularies.set(weights, v);
}
return v;
}
/**
* One row of a byte matrix, decoded from the base64 text alone: four
* characters hold three bytes, so the row's bytes sit inside the characters
* from its first byte's group to its last byte's group.
* @param {BlockPickerWeights} weights
* @param {'request' | 'doc'} matrix
* @param {number} i
* @returns {Int8Array}
*/
function rowOf(weights, matrix, i) {
const {rows} = vocabularyOf(weights);
const key = `${matrix}:${i}`;
let row = rows.get(key);
if (!row) {
const {dims} = weights;
const first = Math.floor((i * dims) / 3);
const last = Math.ceil(((i + 1) * dims) / 3);
const bytes = Buffer.from(
weights[matrix].slice(first * 4, last * 4),
'base64',
).subarray(i * dims - first * 3, i * dims - first * 3 + dims);
// Each byte is a signed weight stored offset by 128.
row = Int8Array.from(bytes, b => b - 128);
rows.set(key, row);
}
return row;
}
/**
* A text's side for `matchOf` through one matrix: its word vector, and that
* vector times the matrix rows its words use, scaled.
* @param {string} text
* @param {BlockPickerWeights} weights
* @param {'request' | 'doc'} matrix
* @param {number} scale
* @returns {{vector: Map<number, number>, projected: Float64Array}}
*/
function sideOf(text, weights, matrix, scale) {
const vector = vectorOf(termsOf(text), vocabularyOf(weights));
const {dims} = weights;
const projected = new Float64Array(dims);
for (const [i, x] of vector) {
const row = rowOf(weights, matrix, i);
for (let k = 0; k < dims; k++) projected[k] += x * row[k];
}
for (let k = 0; k < dims; k++) projected[k] *= scale;
return {vector, projected};
}
/**
* A text's docs side for `matchOf`: its word vector and that vector through
* the doc matrix. Search scores its entries' own docs with it.
* @param {string} text
* @param {BlockPickerWeights} weights
* @returns {{vector: Map<number, number>, projected: Float64Array}}
*/
export function docSideOf(text, weights) {
return sideOf(text, weights, 'doc', weights.docScale);
}
/**
* A request's side for `matchOf`: its word vector and that vector through the
* request matrix.
* @param {string} request
* @param {BlockPickerWeights} weights
* @returns {{vector: Map<number, number>, projected: Float64Array}}
*/
export function requestSideOf(request, weights) {
return sideOf(request, weights, 'request', weights.requestScale);
}
/**
* The picker's match of a request to a docs text: their projections' dot
* product plus the lexical weight times their plain overlap (the cosine of
* their word vectors). Build's ranking also reads the overlap alone.
* @param {{vector: Map<number, number>, projected: Float64Array}} request
* @param {{vector: Map<number, number>, projected: Float64Array}} doc
* @param {BlockPickerWeights} weights
* @returns {{match: number, overlap: number}}
*/
export function matchOf(request, doc, weights) {
let s = 0;
for (let k = 0; k < weights.dims; k++)
s += request.projected[k] * doc.projected[k];
let overlap = 0;
for (const [i, x] of request.vector) {
const y = doc.vector.get(i);
if (y !== undefined) overlap += x * y;
}
return {match: s + weights.lexical * overlap, overlap};
}
/**
* Each block's component: the longest component name its name starts with,
* else the display name's part before " — ", without spaces.
* @param {CatalogBlock} block
* @param {string[]} componentNames longest first
*/
function componentOf(block, componentNames) {
for (const c of componentNames) if (block.name.startsWith(c)) return c;
const display = block.displayName ?? block.name;
return display.split(' — ')[0].replace(/ /g, '');
}
/**
* The catalog, read once per weights and catalog contents: each block's
* component, docs vector and projection, and each component's name phrases.
* @type {WeakMap<BlockPickerWeights, {key: string, blocks: Map<string, {component: string, vector: Map<number, number>, projected: Float64Array}>, phrases: Map<string, [string[], number][]>}>}
*/
const catalogs = new WeakMap();
/**
* @param {CatalogBlock[]} catalog
* @param {CatalogComponent[]} components
* @param {BlockPickerWeights} weights
*/
function readCatalog(catalog, components, weights) {
const key = JSON.stringify([
catalog.map(b => [b.name, b.displayName, b.description]),
components.map(c => [c.name, c.keywords]),
]);
const cached = catalogs.get(weights);
if (cached && cached.key === key) return cached;
const names = components.map(c => c.name).sort((a, b) => b.length - a.length);
const keywords = new Map(components.map(c => [c.name, c.keywords ?? []]));
/** @type {Map<string, {component: string, vector: Map<number, number>, projected: Float64Array}>} */
const blocks = new Map();
for (const b of catalog) {
if (blocks.has(b.name)) continue;
const component = componentOf(b, names);
const text = [
wordsOf(b.name).join(' '),
b.displayName ?? '',
b.description ?? '',
wordsOf(component).join(' '),
(keywords.get(component) ?? []).join(' '),
].join(' ');
blocks.set(b.name, {component, ...docSideOf(text, weights)});
}
// A component is named by its own words, or by a keyword at most three
// components share (weighted by how few share it).
/** @type {Map<string, number>} */
const shared = new Map();
for (const c of components)
for (const k of new Set((c.keywords ?? []).map(k => k.replace(/-/g, ' '))))
shared.set(k, (shared.get(k) ?? 0) + 1);
const phrase = (/** @type {string} */ s) =>
s.toLowerCase().split(/\s+/).filter(Boolean).map(stemOf);
/** @type {Map<string, [string[], number][]>} */
const phrases = new Map();
const withBlocks = new Set([...blocks.values()].map(b => b.component));
for (const c of withBlocks) {
/** @type {[string[], number][]} */
const list = [[phrase(wordsOf(c).join(' ')), 3]];
for (const k of (keywords.get(c) ?? []).map(k => k.replace(/-/g, ' ')))
if ((shared.get(k) ?? 0) <= 3)
list.push([phrase(k), 1 / (shared.get(k) ?? 1)]);
phrases.set(c, list);
}
const read = {key, blocks, phrases};
catalogs.set(weights, read);
return read;
}
/**
* How strongly the request names each component: its best phrase, longer
* phrases and earlier ones stronger, and half as strong once the request has
* moved on to where the piece goes.
* @param {string} request
* @param {Map<string, [string[], number][]>} phrases
* @returns {Map<string, number>}
*/
function namedComponents(request, phrases) {
const raw =
String(request)
.toLowerCase()
.match(/[a-z0-9]+/g) ?? [];
const stems = raw.map(stemOf);
let context = raw.findIndex((w, k) => k > 0 && CONTEXT.has(w));
if (context < 0) context = raw.length;
/** @type {Map<string, number>} */
const out = new Map();
for (const [c, list] of phrases) {
let best = 0;
for (const [p, w] of list) {
if (p.length === 0) continue;
let at = -1;
for (let i = 0; i + p.length <= stems.length && at < 0; i++)
if (p.every((x, k) => stems[i + k] === x)) at = i;
if (at < 0) continue;
const s =
w *
(1 + 0.3 * (p.length - 1)) *
(at < context ? 1 : 0.5) *
(1 - 0.01 * at);
if (s > best) best = s;
}
if (best) out.set(c, best);
}
return out;
}
/**
* Whether the request writes out the block's exact name (its words joined).
* @param {string[]} words the request's identifier words
* @param {string} block
*/
function writesName(words, block) {
const name = block.toLowerCase();
const length = wordsOf(block).length;
for (let i = 0; i < words.length; i++) {
let run = '';
for (let n = 0; n < length && i + n < words.length; n++) {
run += words[i + n];
if (run === name) return true;
}
}
return false;
}
/**
* The blocks build names for a request, ranked by the picker.
* @param {string} request
* @param {{kitBlocks: string[], searched: BlockScore[], foreign: string[], catalog: CatalogBlock[], components: CatalogComponent[]}} signals
* @param {BlockPickerWeights} weights
* @returns {{names: string[], entries: Map<string, SearchResultEntry>}} as
* many names as build's own list, best first; an entry for each listed
* block search did not return
*/
export function pickBlocks(request, signals, weights) {
const own = signals.kitBlocks;
/** @type {Map<string, SearchResultEntry>} */
const entries = new Map();
if (own.length === 0) return {names: [], entries};
const cat = readCatalog(signals.catalog, signals.components, weights);
const side = requestSideOf(request, weights);
/** @type {Map<string, {match: number, overlap: number}>} */
const scored = new Map();
for (const [name, b] of cat.blocks)
scored.set(name, matchOf(side, b, weights));
const get = (/** @type {string} */ b) =>
scored.get(b) ?? {match: -Infinity, overlap: 0};
const ranked = [...scored.keys()].sort((a, b) => get(b).match - get(a).match);
const top = ranked.slice(0, TOP);
const best = top.length ? get(top[0]).match : 0;
const second = top.length > 1 ? get(top[1]).match : 0;
const floor = top.length ? get(top[top.length - 1]).match : 0;
const place = new Map(top.map((b, k) => [b, k]));
/** @type {Map<string, [BlockScore, number]>} */
const found = new Map();
signals.searched.forEach((s, k) => {
if (!found.has(s[0])) found.set(s[0], [s, k]);
});
const overlaps = [...scored.keys()]
.filter(b => get(b).overlap > 0)
.sort((a, b) => get(b).overlap - get(a).overlap || (a < b ? -1 : 1));
const pool = [
...new Set([
...own,
...top.slice(0, POOL.matches),
...signals.searched.slice(0, POOL.searched).map(s => s[0]),
...overlaps.slice(0, POOL.overlaps),
]),
].filter(b => scored.has(b) || found.has(b));
const known = new Set(weights.known);
const named = namedComponents(request, cat.phrases);
const t = weights.theta;
const final = pool.map((b, pos) => {
const m = place.has(b) ? get(b).match : floor;
const f = found.get(b);
const s = f?.[0];
const component = cat.blocks.get(b)?.component;
const score =
t.g * (m - best) +
t.grank * (place.get(b) ?? 99) +
t.gmargin * (m - second) +
t.seen * (known.has(b) ? 1 : 0) +
t.lex * get(b).overlap +
t.sscore * (s ? s[1] / 100 : 0) +
t.scov * (s ? (s[2] ?? 0) / Math.max(s[3] ?? 0, 1) : 0) +
t.srank * (f ? f[1] : 300) +
t.inkit * (own.includes(b) ? 1 : 0) +
t.kitpos * (own.includes(b) ? own.indexOf(b) : 9) +
t.mention * (component ? (named.get(component) ?? 0) : 0) +
t.show * (/Showcase|Basic/.test(b) ? 1 : 0);
return {b, pos, score};
});
final.sort((a, b) => b.score - a.score || a.pos - b.pos);
const foreign = new Set(signals.foreign);
const words = wordsOf(request);
const keeps = own.map(b => foreign.has(b) || writesName(words, b));
const kept = new Set(own.filter((_, k) => keeps[k]));
const order = [
...final.map(x => x.b).filter(b => !kept.has(b) && !foreign.has(b)),
...own.filter(b => !kept.has(b)),
];
/** @type {string[]} */
const out = [];
let next = 0;
for (let k = 0; k < own.length; k++) {
if (keeps[k]) {
out.push(own[k]);
continue;
}
while (out.includes(order[next])) next++;
out.push(order[next++]);
}
// A listed block search did not return gets the picker's own entry: its
// score (100 for the best candidate, less by how far it trails, never
// below 1) and the request words that tie it to its docs.
const max = Math.max(...final.map(x => x.score));
const byName = new Map(signals.catalog.map(b => [b.name, b]));
for (const name of out) {
if (found.has(name) || own.includes(name)) continue;
const block = byName.get(name);
const x = final.find(f => f.b === name);
if (!block || !x) continue;
entries.set(name, {
domain: 'template',
name,
package: block.package ?? '',
score: Math.max(1, Math.round(100 * Math.exp(x.score - max))),
reason: reasonFor(request, side, cat.blocks.get(name), weights),
description: block.description ?? '',
displayName: block.displayName,
kind: 'block',
command: block.command ?? '',
});
}
return {names: out, entries};
}
/**
* Why a block fits: the request words that tie it to its docs most.
* @param {string} request
* @param {{vector: Map<number, number>, projected: Float64Array}} side the request's side
* @param {{vector: Map<number, number>, projected: Float64Array} | undefined} block
* @param {BlockPickerWeights} weights
*/
function reasonFor(request, side, block, weights) {
if (!block) return 'fits by meaning';
const raw =
String(request)
.toLowerCase()
.match(/[a-z0-9]{2,}/g) ?? [];
/** @type {Map<string, string>} */
const wordOf = new Map();
for (const w of raw)
if (!STOP.has(w) && !wordOf.has(stemOf(w))) wordOf.set(stemOf(w), w);
/** @type {[string, number][]} */
const parts = [];
for (const [i, x] of side.vector) {
const term = weights.vocab[i];
if (term.includes('_')) continue;
const row = rowOf(weights, 'request', i);
let s = 0;
for (let k = 0; k < weights.dims; k++) s += row[k] * block.projected[k];
s =
x * s * weights.requestScale +
weights.lexical * x * (block.vector.get(i) ?? 0);
if (s > 0) parts.push([wordOf.get(term) ?? term, s]);
}
parts.sort((a, b) => b[1] - a[1]);
const top = parts.slice(0, 3).map(p => p[0]);
return top.length ? `fits by meaning: ${top.join(', ')}` : 'fits by meaning';
}