learning-website-nextjs1-9  Exercise 1: A Search That Runs in the Browser, and the Plain Text It Searches
==========================================================================================================

There is no search server and no database: the site is made of files. So search is a FILE too: when the site is built, an index of
every page is written out as one JSON file, and the browser fetches it the first time somebody searches, then looks words up in it.

Three jobs, in a package of plain functions (@lw/search) so they can be tested without a browser:
1. htmlToText: the words a person would read on a page.
2. buildSearchIndex: for every word, the pages it is on (and how often).
3. search: a query against the index.

The package has two doors, because a browser must never load code that reads files: the main one (for the build) and "@lw/search/client"
(prepare and search only, which the page imports).

Save as packages/search/package.json:

{
  "name": "@lw/search",
  "version": "0.1.0",
  "private": true,
  "type": "module",
  "exports": {
    ".": "./src/index.ts",
    "./client": "./src/client.ts"
  },
  "dependencies": {
    "@lw/content": "*"
  },
  "scripts": {
    "test": "node --test \"src/**/*.test.ts\"",
    "typecheck": "tsc --noEmit"
  }
}

Save as packages/search/src/text.ts:

import { decodeEntities } from "@lw/content";

/** Japanese: hiragana, katakana (with the long mark), and the common kanji blocks. The same ranges as the Django project. */
const CJK_CHAR = /[぀-ヿ㐀-䶿一-鿿豈-﫿]/;
export const hasCjk = (text: string): boolean => CJK_CHAR.test(text);

// Code and styling are not content. An opening <script> or <style> with no closing tag swallows the REST of the page, in a browser
// and in Python's HTML parser alike, so it does here too (two real pages have one written by mistake in their text).
const SKIP = /<(script|style)\b[^>]*>(?:[\s\S]*?<\/\1\s*>|[\s\S]*$)/gi;
const COMMENTS = /<!--[\s\S]*?-->|<!\[CDATA\[[\s\S]*?\]\]>|<![^>]*>|<\?[\s\S]*?\?>|<\/>/g;      // also the empty closing tag </>, which a parser ignores
const BLOCK_TAGS = new Set(["p", "div", "li", "tr", "td", "th", "br", "h1", "h2", "h3", "h4", "section", "details", "summary"]);

/**
 * Turn a page's HTML into the plain text a person would read: tags removed, script and style dropped, a space at every
 * block tag so table cells do not run together, character references decoded, white space collapsed.
 * The same rules as the Django project's, so the two indexes see the same words.
 */
export function htmlToText(fragment: string): string {
  const html = fragment.replace(SKIP, "").replace(COMMENTS, "");
  let out = "";
  let last = 0;
  for (const match of html.matchAll(/<\/?([a-zA-Z][a-zA-Z0-9]*)\b[^>]*>/g)) {
    out += decodeEntities(html.slice(last, match.index));
    out += BLOCK_TAGS.has((match[1] ?? "").toLowerCase()) ? " " : "";
    last = (match.index ?? 0) + match[0].length;
  }
  out += decodeEntities(html.slice(last));
  return out.replace(/\s+/g, " ").trim();
}

Save as packages/search/src/tokenize.ts:

/**
 * Splitting text into the units that are searched for.
 *
 *  - Words (anything that is not Japanese): lower case, accents removed, so "Szeretnék" and "szeretnek" are the same word.
 *  - Japanese has no spaces, so there are no words to find. Each run of Japanese is stored as single characters, as every
 *    pair and as every group of three neighbouring characters. A search needs every group of three in the query (or the pair,
 *    or the character, for a shorter query), which is almost the same as needing the exact text.
 */

const CJK_RUN = /[぀-ヿ㐀-䶿一-鿿豈-﫿]+/g;
const WORD = /[\p{L}\p{N}]+/gu;

/** Lower case, with accents taken off (NFD splits "ő" into "o" and a mark, and the mark is removed). */
export function fold(text: string): string {
  return text.normalize("NFD").replace(/\p{M}/gu, "").toLowerCase();
}

export interface Units {
  /** Words, in order, with repeats. */
  readonly words: string[];
  /** Japanese characters and pairs of characters, with repeats. */
  readonly cjk: string[];
}

/**
 * Both kinds of unit in a piece of text. Japanese runs are cut out FIRST and never folded: removing "marks" from が
 * (which NFD splits into か and a voicing mark) would turn it into か, a different letter.
 */
export function units(text: string): Units {
  const words: string[] = [];
  const cjk: string[] = [];
  let last = 0;
  const addWords = (piece: string) => { for (const match of fold(piece).matchAll(WORD)) words.push(match[0]); };
  for (const match of text.matchAll(CJK_RUN)) {
    addWords(text.slice(last, match.index));
    last = (match.index ?? 0) + match[0].length;
    const chars = Array.from(match[0].normalize("NFC"));
    for (let i = 0; i < chars.length; i++) {
      cjk.push(chars[i] as string);
      if (i + 1 < chars.length) cjk.push((chars[i] as string) + (chars[i + 1] as string));
      if (i + 2 < chars.length) cjk.push((chars[i] as string) + (chars[i + 1] as string) + (chars[i + 2] as string));
    }
  }
  addWords(text.slice(last));
  return { words, cjk };
}

/** The units a SEARCH needs: whole words, and for Japanese only what is needed to find the exact text. */
export interface QueryUnits {
  /** Words that must be present. The LAST one may be the beginning of a word. */
  readonly words: string[];
  /** Japanese units that must all be present: a character, a pair, or every group of three of a longer run. */
  readonly cjk: string[];
}

export const MAX_QUERY_TERMS = 8;

export function queryUnits(text: string): QueryUnits {
  const q = text.slice(0, 100);
  const words: string[] = [];
  const cjk: string[] = [];
  let last = 0;
  const addWords = (piece: string) => { for (const match of fold(piece).matchAll(WORD)) words.push(match[0]); };
  for (const match of q.matchAll(CJK_RUN)) {
    addWords(q.slice(last, match.index));
    last = (match.index ?? 0) + match[0].length;
    const chars = Array.from(match[0].normalize("NFC"));
    // the longest unit the index holds that fits: one character, one pair, or every group of three
    const size = Math.min(3, chars.length);
    for (let i = 0; i + size <= chars.length; i++) cjk.push(chars.slice(i, i + size).join(""));
  }
  addWords(q.slice(last));
  return { words: words.slice(0, MAX_QUERY_TERMS), cjk: [...new Set(cjk)].slice(0, 4 * MAX_QUERY_TERMS) };
}

Save as packages/search/src/indexer.ts:

import { units } from "./tokenize.ts";

/** What the index needs to know about a page. */
export interface SearchDoc {
  readonly path: string;
  readonly title: string;
  /** A line to show under the title in the results. */
  readonly summary: string;
  /** The page's plain text (see htmlToText). */
  readonly text: string;
}

/**
 * The search index, as it travels to the browser. Each unit (a word, or a Japanese character group) maps to the pages that
 * contain it, in increasing order of page number. A page number is written as the DIFFERENCE from the one before, in base 36,
 * and (for words) followed by ":" and how many times the word occurs when that is more than once: the pages 3, 10 and 11, the
 * last containing the word twice, are written "3,7,1:2". That is much smaller than a list of numbers.
 */
export interface SearchIndex {
  readonly v: 2;
  /** [path, title, summary, number of words] for each page, in path order: a page's number is its place in this list. */
  readonly docs: readonly (readonly [string, string, string, number])[];
  /** Words in the page's title or text, with how often. */
  readonly words: Readonly<Record<string, string>>;
  /** Words in the page's TITLE only (used to rank a title match first). */
  readonly titleWords: Readonly<Record<string, string>>;
  /** Japanese characters, pairs and groups of three. */
  readonly cjk: Readonly<Record<string, string>>;
}

export type Posting = readonly [id: number, count: number];

export function encodePostings(postings: readonly Posting[]): string {
  let previous = 0;
  return postings.map(([id, count]) => {
    const out = (id - previous).toString(36) + (count > 1 ? `:${count.toString(36)}` : "");
    previous = id;
    return out;
  }).join(",");
}

export function decodePostings(text: string): Posting[] {
  let total = 0;
  return text.split(",").map((part) => {
    const [delta = "0", count] = part.split(":");
    total += parseInt(delta, 36);
    return [total, count === undefined ? 1 : parseInt(count, 36)] as const;
  });
}

function invert(postings: Map<string, Map<number, number>>): Record<string, string> {
  const out: Record<string, string> = {};
  for (const [term, ids] of [...postings.entries()].sort(([a], [b]) => (a < b ? -1 : 1))) {
    out[term] = encodePostings([...ids.entries()].sort(([x], [y]) => x - y));
  }
  return out;
}

/** Build the index of one site's pages. Pages are put in path order, so the same pages always give the same index. */
export function buildSearchIndex(documents: readonly SearchDoc[]): SearchIndex {
  const docs = [...documents].sort((a, b) => (a.path < b.path ? -1 : 1));
  const words = new Map<string, Map<number, number>>();
  const titleWords = new Map<string, Map<number, number>>();
  const cjk = new Map<string, Map<number, number>>();
  const add = (map: Map<string, Map<number, number>>, term: string, id: number) => {
    const counts = map.get(term) ?? new Map<number, number>();
    counts.set(id, (counts.get(id) ?? 0) + 1);
    map.set(term, counts);
  };
  const lengths: number[] = [];
  docs.forEach((doc, id) => {
    const title = units(doc.title);
    const body = units(doc.text);
    for (const word of title.words) { add(titleWords, word, id); add(words, word, id); }
    for (const word of body.words) add(words, word, id);
    for (const unit of [...new Set([...title.cjk, ...body.cjk])]) add(cjk, unit, id);          // for Japanese only whether it occurs
    lengths.push(title.words.length + body.words.length);
  });
  return {
    v: 2,
    docs: docs.map((doc, id) => [doc.path, doc.title, doc.summary, lengths[id] as number] as const),
    words: invert(words),
    titleWords: invert(titleWords),
    cjk: invert(cjk),
  };
}

Save as packages/search/src/query.ts:

import { decodePostings, type Posting, type SearchIndex } from "./indexer.ts";
import { queryUnits } from "./tokenize.ts";

export interface SearchResult {
  readonly path: string;
  readonly title: string;
  readonly summary: string;
  readonly score: number;
}

/** An index made ready for searching: the terms are sorted, so the words that begin with something can be found quickly. */
export interface PreparedIndex {
  readonly index: SearchIndex;
  readonly wordKeys: readonly string[];
  readonly titleKeys: readonly string[];
  readonly decoded: Map<string, Posting[]>;
  readonly averageLength: number;
}

export function prepare(index: SearchIndex): PreparedIndex {
  const total = index.docs.reduce((sum, doc) => sum + doc[3], 0);
  return {
    index,
    wordKeys: Object.keys(index.words).sort(),
    titleKeys: Object.keys(index.titleWords).sort(),
    decoded: new Map(),
    averageLength: index.docs.length ? total / index.docs.length : 1,
  };
}

function postings(prepared: PreparedIndex, table: "words" | "titleWords" | "cjk", term: string): Posting[] {
  const key = `${table}:${term}`;
  let found = prepared.decoded.get(key);
  if (!found) {
    const text = Object.hasOwn(prepared.index[table], term) ? prepared.index[table][term] : undefined;
    found = text ? decodePostings(text) : [];
    prepared.decoded.set(key, found);
  }
  return found;
}

/** The index of the first key that is >= prefix, in a sorted list. */
function lowerBound(keys: readonly string[], prefix: string): number {
  let low = 0;
  let high = keys.length;
  while (low < high) {
    const middle = (low + high) >> 1;
    if ((keys[middle] as string) < prefix) low = middle + 1;
    else high = middle;
  }
  return low;
}

/** For each page that contains the word (or, when `prefix`, any word that begins with it): how often it occurs in all. */
function counts(prepared: PreparedIndex, table: "words" | "titleWords", word: string, prefix: boolean): Map<number, number> {
  const out = new Map<number, number>();
  const take = (term: string) => { for (const [id, count] of postings(prepared, table, term)) out.set(id, (out.get(id) ?? 0) + count); };
  if (!prefix) { take(word); return out; }
  const keys = table === "words" ? prepared.wordKeys : prepared.titleKeys;
  for (let i = lowerBound(keys, word); i < keys.length && (keys[i] as string).startsWith(word); i++) take(keys[i] as string);
  return out;
}

const K1 = 1.2;
const B = 0.75;
/** A word in the title counts as if it occurred this many extra times (the Django project weights the title ten to one). */
const TITLE_WEIGHT = 10;

/**
 * Search one site's index. Every word must be present (in the title or the text), the last word may be the beginning of a
 * word, and Japanese is found by its characters. Results are ranked by BM25 (a page counts more when the word is rare and
 * occurs often, less when the page is long), with the title weighted. The text a visitor types is only ever split into units
 * and looked up in tables: it is never run as a query language, so no input can be an error or an injection.
 */
export function search(prepared: PreparedIndex, text: string, options: { limit?: number; offset?: number } = {}): { total: number; results: SearchResult[] } {
  const { words, cjk } = queryUnits(text);
  if (words.length === 0 && cjk.length === 0) return { total: 0, results: [] };

  const total = prepared.index.docs.length;
  const perWord = words.map((word, i) => ({
    body: counts(prepared, "words", word, i === words.length - 1),
    title: counts(prepared, "titleWords", word, i === words.length - 1),
  }));

  let candidates: Set<number> | null = null;
  const narrow = (ids: Iterable<number>) => {
    const set = new Set(ids);
    candidates = candidates === null ? set : new Set([...candidates].filter((id) => set.has(id)));
  };
  for (const { body } of perWord) narrow(body.keys());
  for (const unit of cjk) narrow(postings(prepared, "cjk", unit).map(([id]) => id));

  const found = [...(candidates ?? new Set<number>())].map((id) => {
    const [path, title, summary, length] = prepared.index.docs[id] as readonly [string, string, string, number];
    let score = 0;
    for (const { body, title: inTitle } of perWord) {
      const documents = body.size;
      const idf = Math.log(1 + (total - documents + 0.5) / (documents + 0.5));
      const frequency = (body.get(id) ?? 0) + TITLE_WEIGHT * (inTitle.has(id) ? 1 : 0);
      score += idf * ((frequency * (K1 + 1)) / (frequency + K1 * (1 - B + (B * length) / prepared.averageLength)));
    }
    return { id, path, title, summary, score: Math.round(score * 1000) / 1000 };
  });
  found.sort((a, b) => b.score - a.score || a.id - b.id);
  const limit = options.limit ?? 20;
  const offset = options.offset ?? 0;
  return { total: found.length, results: found.slice(offset, offset + limit).map(({ path, title, summary, score }) => ({ path, title, summary, score })) };
}

Save as packages/search/src/client.ts:

/**
 * What the BROWSER needs: preparing an index and searching it. Nothing here touches files or the content package, so it can be
 * bundled into a page. (The build-time half, which reads the pages and makes the index, is the package's main entry.)
 */
export { prepare, search } from "./query.ts";
export type { PreparedIndex, SearchResult } from "./query.ts";
export type { SearchIndex } from "./indexer.ts";

How it decides things:
- Words are lower-cased with their accents taken off, so "Szeretnék" and "szeretnek" are one word. Japanese has no spaces, so it is stored
  as single characters, pairs and groups of three (taking accents off が would turn it into か, so Japanese is cut out first and never folded).
- A search needs every word; the last word may be only the beginning of a word (so "polite cond" finds "conditional").
- The text a visitor types is only ever split into units and looked up in tables. It is never run as a query language, so no input can be an
  error or an injection.
- Results are ranked by BM25 (a word counts more when it is rare and frequent, less on a long page) with the title weighted ten to one,
  as in the Django project.
- The index is written compactly: each page number as the difference from the one before, in base 36 ("3,7,1:2" is pages 3, 10 and 11, the
  last with the word twice).

Save as packages/search/src/search.test.ts:

import assert from "node:assert/strict";
import { test } from "node:test";

import {
  buildSearchIndex, decodePostings, encodePostings, fold, htmlToText, prepare, queryUnits, search, units, type SearchDoc,
} from "./index.ts";

const doc = (path: string, title: string, text: string): SearchDoc => ({ path, title, summary: text.slice(0, 20), text });

test("text: tags go, script and style go, blocks are separated, entities decode, white space collapses", () => {
  assert.equal(htmlToText("<p>Fit &amp; <b>Returns</b></p>"), "Fit & Returns");
  assert.equal(htmlToText("<style>.a{}</style><p>word</p><script>var secret = 1;</script>"), "word");
  assert.equal(htmlToText("<td>one</td><td>two</td><li>three</li>"), "one two three");
  assert.equal(htmlToText("a<!-- hidden -->b <!DOCTYPE html>c"), "ab c");
  assert.equal(htmlToText("<p>x&nbsp;&nbsp;y</p>\n\n  <p>z</p>"), "x y z");
  assert.equal(htmlToText("<p>React: &lt;&gt; and </> done</p>"), "React: <> and done");     // the empty closing tag </> is ignored
  assert.equal(htmlToText("<p>1 &frac12; &Delta;&delta; &Eacute;</p>"), "1 ½ Δδ É");
});

test("an unclosed <script> or <style> swallows the rest, as it does in a browser", () => {
  assert.equal(htmlToText("<p>before</p><p>the <style> block</p><p>after</p>"), "before the");
  assert.equal(htmlToText("<p>a</p><script src='x'>never closed"), "a");
});

test("fold: lower case, no accents; Japanese voicing marks survive", () => {
  assert.equal(fold("Szeretnék"), "szeretnek");
  assert.equal(fold("Brötchen ő"), "brotchen o");
  assert.equal(units("がく").cjk.includes("が"), true);        // が is kept as が, not turned into か
});

test("units: words and Japanese are told apart", () => {
  const u = units("Hallo, ありがとう world-wide 3rd");
  assert.deepEqual(u.words, ["hallo", "world", "wide", "3rd"]);
  assert.deepEqual(u.cjk.filter((x) => x.length === 3), ["ありが", "りがと", "がとう"]);
  assert.deepEqual(units("").words, []);
});

test("a query: the last word may be a beginning, Japanese uses the biggest unit that fits, nothing else is special", () => {
  assert.deepEqual(queryUnits("polite cond"), { words: ["polite", "cond"], cjk: [] });
  assert.deepEqual(queryUnits("水"), { words: [], cjk: ["水"] });
  assert.deepEqual(queryUnits("水を"), { words: [], cjk: ["水を"] });
  assert.deepEqual(queryUnits("ありがとう").cjk, ["ありが", "りがと", "がとう"]);
  assert.deepEqual(queryUnits('"; DROP TABLE x; -- OR NEAR(').words, ["drop", "table", "x", "or", "near"]);
  assert.equal(queryUnits("a b c d e f g h i j k l").words.length, 8);              // at most eight words
  assert.deepEqual(queryUnits("   !!! "), { words: [], cjk: [] });
});

test("postings are written as differences and survive a round trip", () => {
  const list = [[3, 1], [10, 1], [11, 2], [500, 36]] as const;
  assert.equal(encodePostings(list), "3,7,1:2,dl:10");
  assert.deepEqual(decodePostings("3,7,1:2,dl:10"), list);
  assert.deepEqual(decodePostings(encodePostings([[0, 1]])), [[0, 1]]);
});

const docs = [
  doc("hungary/a.html", "Buying clothes", "Szeretnék egy kabátot. The polite conditional."),
  doc("germany/b.html", "Beim Bäcker", "Ich möchte ein Brötchen, bitte. Brötchen sind gut."),
  doc("japan/c.html", "Greetings", "ありがとうございます。水をください。"),
  doc("japan/d.html", "Other", "あり abc りが abc pieces of the word, never together"),
  doc("misc/e.html", "Clothes", "about nothing much"),
  doc("misc/f.html", "Other", "clothes clothes clothes clothes and more clothes in a long page " + "filler ".repeat(40)),
];
const prepared = prepare(buildSearchIndex(docs));
const paths = (q: string) => search(prepared, q).results.map((r) => r.path);

test("a word finds its page; accents and capitals do not matter", () => {
  assert.deepEqual(paths("conditional"), ["hungary/a.html"]);
  assert.deepEqual(paths("szeretnek"), ["hungary/a.html"]);
  assert.deepEqual(paths("SZERETNÉK"), ["hungary/a.html"]);
  assert.deepEqual(paths("brotchen"), ["germany/b.html"]);
  assert.deepEqual(paths("Backer"), ["germany/b.html"]);
});

test("every word must be there, and the last may be a beginning", () => {
  assert.deepEqual(paths("polite cond"), ["hungary/a.html"]);
  assert.deepEqual(paths("polite bitte"), []);
  assert.deepEqual(paths("cond polite"), []);                       // "cond" must be a whole word when it is not last
});

test("Japanese: found by its text, not merely by pieces of it", () => {
  assert.deepEqual(paths("ありがとう"), ["japan/c.html"]);
  assert.deepEqual(paths("ありが"), ["japan/c.html"]);               // d.html has あり and りが, but never ありが together: not found
  assert.deepEqual(paths("水"), ["japan/c.html"]);
  assert.deepEqual(paths("水を"), ["japan/c.html"]);
  assert.deepEqual(paths("水をくだ"), ["japan/c.html"]);
  assert.deepEqual(paths("がと"), ["japan/c.html"]);
});

test("ranking: a title match first, then a word that is frequent, long pages count less", () => {
  const ranked = search(prepared, "clothes").results;
  assert.deepEqual(ranked.map((r) => r.path).sort(), ["hungary/a.html", "misc/e.html", "misc/f.html"]);
  assert.equal(ranked[0]?.path, "misc/e.html");                      // "Clothes" in its title, in a short page
  assert.equal(ranked.at(-1)?.path, "misc/f.html");                  // the word repeated in a long page, but not in its title
  assert.deepEqual(ranked.map((r) => r.score), [...ranked.map((r) => r.score)].sort((x, y) => y - x));
});

test("hostile or empty input is a search, never an error", () => {
  for (const q of ['"', '" OR 1=1 --', "NEAR(", "a AND", "(((", "*", "title:x", "-x", "%", "_", "'", "", "   ", "<script>", "\u0000", "toString", "__proto__", "constructor"]) {
    const found = search(prepared, q);                              // must not throw
    assert.ok(found.total >= 0, q);
  }
  assert.deepEqual(search(prepared, "__proto__"), { total: 0, results: [] });
  assert.deepEqual(search(prepared, ""), { total: 0, results: [] });
});

test("paging", () => {
  const many = prepare(buildSearchIndex(Array.from({ length: 25 }, (_, n) => doc(`p/${String(n).padStart(2, "0")}.html`, `T${n}`, "shared keyword"))));
  const first = search(many, "keyword");
  assert.equal(first.total, 25);
  assert.equal(first.results.length, 20);
  assert.equal(search(many, "keyword", { offset: 20 }).results.length, 5);
  assert.equal(search(many, "keyword", { limit: 3 }).results.length, 3);
});

test("the same pages always give the same index, whatever order they come in", () => {
  const a = JSON.stringify(buildSearchIndex(docs));
  const b = JSON.stringify(buildSearchIndex([...docs].reverse()));
  assert.equal(a, b);
});

  npm test
ℹ tests 76
ℹ pass 76
ℹ fail 0
  (63 earlier and 13 new)

TWO MISTAKES OF MY OWN IN THESE TESTS, found by running them:
- I worked a base-36 number out in my head ("dx") and the real answer is "dl". Compute expected values with a tool, not by hand.
- My Japanese test page for "pieces that are not together" had the exact words in it ("ありが" written out), so it correctly matched. The test
  data has to be built so that the thing it is meant to prove really is absent.
Both were mistakes in the TEST, and the tests found them: the checks on the code stayed as they were.

WHY THIS WORKS AS AN ANSWER
---------------------------
The whole search is a few small tested functions with no server, and the one hard decision (never let typed text be a query language) is
enforced by how the code is built, not by remembering to escape.