| M | README.md | 17 | ++++++--- |
| M | site/ | 41 | ++++++++++++++++++---- |
| M | site/ | 54 | ++++++++++++++++++++++-------- |
| M | test/ | 2 | +- |
| M | test/ | 44 | +++++++++++++++++++++---- |
@@ -541,8 +541,8 @@ are cut to 240 characters and wiki pages to 2000, to keep the index small.
541541 Every section reads a query the same way (`site/assets/query.ts`): terms542542 split on whitespace, in any order, and a quoted phrase (`"fix the search"`)543543 is one term, spaces and all, that must appear as written, except that a run544-of whitespace in it counts as one space, as in the indexes, which collapse545-whitespace (`"fix the"` is `"fix the"`). Every term must544+of whitespace in it matches any run of whitespace: `"fix the"` finds545+`fix the`, and `"fix the"` finds `fix the`. Every term must546546 match, ignoring case, and results mark each match, a phrase as a whole. A547547 quote opens a phrase only at the start of a term (in `it's"` it is just a548548 character), an unclosed quote runs to the end of the query as a phrase, so a@@ -569,11 +569,16 @@ goes to a worker, and a Code section lists each line that has every word,
569569 ignoring case, as `path:line`, linked to that line of the file's page (the570570 source page for markdown). Its words are the terms the other sections read,571571 so a quoted phrase (`"import fs from"`) is one literal string, spaces and572-all, a run of whitespace as one space as everywhere (so it won't find code573-aligned with several spaces); a word inside another goes, since a line with574-the longer one has it.572+all, in which a run of whitespace matches any run, tabs and alignment too;573+a word inside another goes, since a line with the longer one has it.575574 Words of 3 characters or more are looked up576-in the index; shorter ones only filter the lines it finds. It loads nothing575+in the index; shorter ones only filter the lines it finds. A phrase is576+looked up by its pieces between whitespace, those of 3 characters or more,577+since no trigram may span whitespace that can be any length: all of them578+within `NEAR` distance of the phrase's length plus 32 characters per gap,579+and the lines found are checked with any run of whitespace for a space. A580+phrase without such a piece (`"x = 1"`) is looked up as written, so it finds581+only single-spaced lines. It loads nothing577582 until then: the first code query starts the worker, which loads578583 `sqlite3.wasm` and sqlite-wasm's script, both content-hashed assets. Results579584 come in path order; the first look reads 12 chunks, and "more" reads up to@@ -12,7 +12,7 @@
1212 // the index leaf of each term (from FTS5's small %_idx table), then the page1313 // of each matching chunk (from the chunk table's root page).1414 15-import { narrow, terms } from './query.ts';15+import { find, narrow, pieces, terms } from './query.ts';1616 1717 // Bytes [from, to) of url (from < 0: the last -from bytes), or the whole1818 // file if the server ignores ranges; where they start, the file's size, and@@ -418,17 +418,42 @@ export function cover(q: string): string[] {
418418 return at.map((i) => c.slice(i, i + 3).join(''));419419 }420420 421+// The strings the index looks up for a word: the word itself, but for a422+// phrase its pieces between whitespace of MIN characters or more, since a423+// space in a phrase stands for any run of whitespace and no trigram may span424+// one. A phrase without such a piece (`"x = 1"`) is looked up as written,425+// single spaces and all, so it finds only lines spaced that way.426+function lookups(w: string): string[] {427+ const ps = pieces(w).filter((p) => [...p].length >= MIN);428+ return ps.length ? ps : [w];429+}430+431+// Extra whitespace characters allowed per gap in a phrase: its pieces must432+// be near each other in the index, with this much room for runs of spaces433+// longer than one (alignment). Lines are checked afterwards anyway.434+const GAP = 32;435+421436 // The FTS5 query for a literal substring, ignoring case.422-export function match(q: string): string {437+function literal(q: string): string {423438 const n = [...q].length;424439 // NEAR counts the tokens between the first phrase and the last.425440 return n <= 5 ? str(q) : `NEAR(${cover(q).map(str).join(' ')}, ${n - 4})`;426441 }427442 443+// The FTS5 query for a word: a literal substring, ignoring case, but in a444+// phrase the trigrams of each piece, all within NEAR distance of the phrase445+// with GAP more characters per gap.446+export function match(w: string): string {447+ const ps = lookups(w);448+ if (ps.length === 1) return literal(ps[0]);449+ const gaps = pieces(w).length - 1;450+ return `NEAR(${ps.flatMap(cover).map(str).join(' ')}, ${[...w].length - 4 + GAP * gaps})`;451+}452+428453 // A query's words, lower case, its terms as query.ts reads them: split on429454 // whitespace, except that a quoted phrase ("like this") is one literal430-// string, spaces and all, a run of them as one (an unclosed quote runs to431-// the end).455+// string, spaces and all, a run of whitespace in it matching any run (an456+// unclosed quote runs to the end).432457 // A word that is part of another goes, since every line with the longer one433458 // has it, and so do NULs, which an FTS5 string can't hold.434459 export const words = (q: string): string[] => narrow(terms(q.replaceAll('\0', '')));@@ -444,9 +469,9 @@ export function lineMatch(line: string, ws: string[]): number {
444469 const low = line.toLowerCase();445470 let first = -1;446471 for (const w of ws) {447- const at = low.indexOf(w);448- if (at < 0) return -1;449- if (first < 0 || at < first) first = at;472+ const at = find(low, w);473+ if (!at) return -1;474+ if (first < 0 || at[0] < first) first = at[0];450475 }451476 return first;452477 }@@ -557,7 +582,7 @@ export class CodeIndex {
557582 // number; a doclist index's has bit 36 set too. Row 10 is the structure.558583 const enc = new TextEncoder();559584 const wanted = [1, 10];560- for (const t of new Set(indexed(ws).flatMap(cover))) {585+ for (const t of new Set(indexed(ws).flatMap(lookups).flatMap(cover))) {561586 const key = enc.encode('0' + t);562587 for (const seg of this.layout.segs) {563588 const first = (this.all('select pgno >> 1 from code_idx where segid = ? and term <= ? order by term desc limit 1', [seg, key])[0]?.[0] as number | undefined) ?? 1;@@ -2,15 +2,16 @@
22 // commits, reviews, wiki pages, file paths and repos, and codesearch.ts for33 // the lines of files. A query is terms split on whitespace, except that a44 // quoted phrase ("like this") is one term, spaces and all, which must appear5-// as written, except that a run of whitespace in it is one space, as in the6-// indexes (lib/search.ts flattens bodies and wiki text). A quote opens a7-// phrase only at the start of a term (in `it's"` or `a"b` it is just a8-// character), an unclosed one runs to the end of the query, and empty quotes9-// are no term. Every term must match, ignoring case. Nothing here touches10-// the page, so test/search-phrases.ts checks it in Node as the browser runs11-// it.5+// as written, except that a run of whitespace in it matches any run of6+// whitespace ("x = 1" finds `x = 1`, and the other way round). A quote7+// opens a phrase only at the start of a term (in `it's"` or `a"b` it is just8+// a character), an unclosed one runs to the end of the query, and empty9+// quotes are no term. Every term must match, ignoring case. Nothing here10+// touches the page, so test/search-phrases.ts checks it in Node as the11+// browser runs it.1212 13-// A query's terms, lower case, each once.13+// A query's terms, lower case, each once; a run of whitespace in a phrase14+// is kept as one space, which find() matches with any run.1415 export function terms(q: string): string[] {1516 const all = [...q.toLowerCase().matchAll(/"([^"]*)"?|(\S+)/g)].map((m) => m[2] ?? m[1].replace(/\s+/g, ' ')).filter((t) => t.trim());1617 return [...new Set(all)];@@ -20,10 +21,33 @@ export function terms(q: string): string[] {
2021 // since every line with the longer one has it.2122 export const narrow = (ts: string[]): string[] => ts.filter((t, i) => !ts.some((o, j) => j !== i && o.length > t.length && o.includes(t)));2223 24+// A term's pieces: a phrase's parts between whitespace (a word is one).25+export const pieces = (t: string): string[] => t.split(' ').filter(Boolean);26+27+// Where a term is in a lower case text, from `from` on: [start, end), or28+// null. A space in a term (only phrases have them) matches any run of29+// whitespace; terms without one are a plain indexOf.30+const patterns = new Map<string, RegExp>();31+export function find(low: string, t: string, from = 0): [number, number] | null {32+ if (!t.includes(' ')) {33+ const i = low.indexOf(t, from);34+ return i < 0 ? null : [i, i + t.length];35+ }36+ let re = patterns.get(t);37+ if (!re) {38+ if (patterns.size > 200) patterns.clear();39+ re = new RegExp(t.split(' ').map((p) => p.replace(/[.*+?^${}()|[\]\\]/g, '\\$&')).join('\\s+'), 'g');40+ patterns.set(t, re);41+ }42+ re.lastIndex = from;43+ const m = re.exec(low);44+ return m ? [m.index, m.index + m[0].length] : null;45+}46+2347 // Whether a text has every term, ignoring case.2448 export function hasAll(text: string, ts: string[]): boolean {2549 const low = text.toLowerCase();26- return ts.every((t) => low.includes(t));50+ return ts.every((t) => find(low, t));2751 }2852 2953 const wordStart = (s: string, i: number): boolean => i === 0 || /[^\p{L}\p{N}]/u.test(s[i - 1]);@@ -36,11 +60,11 @@ export function score(low: [string, string, string], key: string, ts: string[]):
3660 let s = 0;3761 let inText = false;3862 for (const t of ts) {39- const i = low[0].indexOf(t);40- if (i >= 0) s += wordStart(low[0], i) ? 6 : 4;63+ const at = find(low[0], t);64+ if (at) s += wordStart(low[0], at[0]) ? 6 : 4;4165 else if (t.length >= 4 && key.startsWith(t)) s += 5;42- else if (low[1].includes(t)) s += 2;43- else if (low[2].includes(t)) {66+ else if (find(low[1], t)) s += 2;67+ else if (find(low[2], t)) {4468 s += 1;4569 inText = true;4670 } else return null;@@ -55,7 +79,7 @@ export function marks(s: string, ts: string[]): [string, boolean][] {
5579 const low = s.toLowerCase();5680 if (low.length !== s.length) return [[s, false]];5781 const hit = new Uint8Array(s.length);58- for (const t of ts) for (let i = low.indexOf(t); i >= 0; i = low.indexOf(t, i + 1)) hit.fill(1, i, i + t.length);82+ for (const t of ts) for (let m = find(low, t); m; m = find(low, t, m[0] + 1)) hit.fill(1, m[0], m[1]);5983 const out: [string, boolean][] = [];6084 for (let i = 0, j = 0; i < s.length; i = j) {6185 while (j < s.length && hit[j] === hit[i]) j++;@@ -67,7 +91,7 @@ export function marks(s: string, ts: string[]): [string, boolean][] {
6791 // The part of a long text around its first match.6892 export function snippet(text: string, ts: string[]): string {6993 const low = text.toLowerCase();70- const at = Math.min(...ts.map((t) => low.indexOf(t)).filter((i) => i >= 0));94+ const at = Math.min(...ts.map((t) => find(low, t)?.[0] ?? -1).filter((i) => i >= 0));7195 const start = Math.max(0, at - 30);7296 return (start ? '…' : '') + text.slice(start, start + 120) + (start + 120 < text.length ? '…' : '');7397 }@@ -53,5 +53,5 @@ has "$T/assets" '^sqlite3\.[0-9A-Za-z_-]{10}\.wasm$'
5353 has "$FORGE_WWW/assets/versions.json" 'sqlite3\.[0-9A-Za-z_-]{10}\.wasm'5454 # The worker imports the query parser (query.ts) by its shipped, hashed name.5555 w=$(ls "$FORGE_WWW"/assets/codesearch.*.js)56-has "$w" "^import \{ narrow, terms \} from '\./query\.[0-9A-Za-z_-]{10}\.js';$"56+has "$w" "^import \{ [a-z, ]+ \} from '\./query\.[0-9A-Za-z_-]{10}\.js';$"5757 exists "$FORGE_WWW/assets/$(sed -n "s|^import .* from '\./\(query\.[^']*\)';\$|\1|p" "$w")"@@ -1,8 +1,9 @@
11 # The search reads a query the same way in every section: terms split on22 # whitespace, a quoted phrase is one term that must appear as written3-# (ignoring case), and every term must match. Commits, reviews, wiki pages4-# and repos match through site/assets/query.ts, as the browser does, and5-# code search's words come out the same.3+# (ignoring case, and a run of whitespace in it matching any run), and every4+# term must match. Commits, reviews, wiki pages and repos match through5+# site/assets/query.ts, as the browser does, and code search's words come6+# out the same and find lines the same way.67 . "$(dirname "$0")/../lib.sh"78 user dami89 repo dami/greet "say hello world"@@ -13,6 +14,8 @@ at "$T/w/dami" commit "Search fix for the box"
1314 tick1415 at "$T/w/dami" git commit -q --allow-empty -m "Tidy the box" -m "This is to fix the search for good."1516 at "$T/w/dami" commit "box search fix"17+printf 'width = height\ndepth = length\ntotal\tcount\nx = 1\ny = 2\n' >"$T/w/dami/sizes.txt"18+at "$T/w/dami" commit "Align the columns"1619 push_as dami "$T/w/dami" origin main1720 at "$T/w/dami" git switch -q -c dami/wide1821 at "$T/w/dami" commit "Make the search box wider"@@ -34,8 +37,8 @@ ok terms '"Fix the Search"'
3437 eq "$(output)" '"Fix the Search" => [fix the search] | code [fix the search]'3538 ok terms '"the search'3639 eq "$(output)" '"the search => [the search] | code [the search]'37-# A run of whitespace in a phrase is one space, as in the indexes; spaces38-# at its ends stay (one each).40+# A run of whitespace in a phrase is kept as one space, which matches any41+# run of whitespace (below); spaces at its ends stay, one each.3942 ok terms '"fix the search"' '" fix "'4043 eq "$(output)" '"fix the search" => [fix the search] | code [fix the search]4144 " fix " => [ fix ] | code [ fix ]'@@ -63,10 +66,18 @@ ok match "$ix" '"fix the search"'
6366 eq "$(output | grep '^Commits: ' | sed 's/ | .*//')" 'Commits: [Fix the search] box6467 Commits: Tidy the box'6568 has "$T_LOG" '^Commits: Tidy the box \| This is to \[fix the search\] for good\.$'66-# Spaced out, it is the same phrase.69+# A run of whitespace in a phrase matches any run, both ways: spaced out,70+# it finds single spaces, and single spaces find a spaced-out subject,71+# marked whole.6772 ok match "$ix" '"fix the search"'6873 eq "$(output | grep '^Commits: ' | sed 's/ | .*//')" 'Commits: [Fix the search] box6974 Commits: Tidy the box'75+ok match "$ix" '"align the columns"'76+eq "$(output | sed 's/ | .*//')" 'Commits: [Align the columns]'77+ok match "$ix" '"align the columns"'78+eq "$(output | sed 's/ | .*//')" 'Commits: [Align the columns]'79+ok match "$ix" '"align thecolumns"'80+eq "$(output)" ''7081 # Unclosed, it is the same phrase.7182 ok match "$ix" '"FIX THE SEARCH'7283 eq "$(output | grep '^Commits: ' | sed 's/ | .*//')" 'Commits: [Fix the search] box@@ -95,9 +106,28 @@ Repositories: dami/other | [hello] there, [world]'
95106 ok match "$FORGE_WWW/repos.json" '"hello world"'96107 eq "$(output)" 'Repositories: dami/greet | say [hello world]'97108 109+# Code search finds lines the same way, both ways, tabs too: the index110+# looks up each piece of 3 characters or more, near the others, and the111+# line check takes any run of whitespace for a space. A phrase without such112+# a piece is looked up as written, so it finds single-spaced lines only.113+db=$FORGE_WWW/dami/greet/code.db114+code() { node "$T_HOME/test/code-search-bench.ts" sql "$db" "$1"; }115+ok code '"width = height"'116+eq "$(output)" 'sizes.txt:1: width = height'117+ok code '"depth = length"'118+eq "$(output)" 'sizes.txt:2: depth = length'119+ok code '"total count"'120+eq "$(output)" "$(printf 'sizes.txt:3: total\tcount')"121+ok code '"WIDTH = height" "depth"'122+eq "$(output)" ''123+ok code '"x = 1"'124+eq "$(output)" 'sizes.txt:4: x = 1'125+ok code '"y = 2"'126+eq "$(output)" ''127+98128 # Pages load search.js as a module, which imports query.js by its shipped name.99129 has "$FORGE_WWW/dami/greet/index.html" '<script type="module" src="/assets/search\.[0-9A-Za-z_-]{10}\.js"></script>'100130 has "$FORGE_WWW/index.html" '<script type="module" src="/assets/search\.[0-9A-Za-z_-]{10}\.js"></script>'101131 s=$(ls "$FORGE_WWW"/assets/search.*.js)102-has "$s" "^import \{ hasAll, marks, narrow, score as match, snippet, terms \} from '\./query\.[0-9A-Za-z_-]{10}\.js';$"132+has "$s" "^import \{ [a-zA-Z, ]+ \} from '\./query\.[0-9A-Za-z_-]{10}\.js';$"103133 exists "$FORGE_WWW/assets/$(sed -n "s|^import .* from '\./\(query\.[^']*\)';\$|\1|p" "$s")"