1// The code index: every text file on a repo's default branch in a SQLite FTS52// trigram index, /<owner>/<repo>/code.db, which the browser queries over HTTP3// range requests (site/assets/codesearch.ts) without downloading it.4//5// file(id, path, source) source: line anchors are on the /source/ page6// chunk(id, file, line, text) CHUNK lines of a file from line `line`7// code fts5 over chunk.text: trigram, detail=full8//9// Rows are chunks of lines rather than lines: an index of lines is about the10// same size but has eight times the rows, and the browser finds the matching11// line inside a chunk itself. detail=full keeps positions, which substring12// (phrase) queries need; columnsize=0 drops the docsize table that only13// ranking reads (results come in path order). After the inserts, 'optimize'14// merges the index into one segment and VACUUM lays each table out in order,15// so a doclist or a run of chunks is a run of pages, one range request.16//17// Skipped: binary files (a NUL in the first 8000 bytes, as git decides),18// files over the highlight cap, lockfiles, minified files and source maps,19// images, symlinks and submodules.20//21// Each index is kept in $FORGE_CACHE/code/<owner>/<repo>/<tree>.<key>.db and22// hard-linked into the pages, so a push that leaves the default branch's tree23// alone reuses the file. A new tree starts from the previous index: chunks of24// files whose blob is unchanged are kept, the rest are deleted and inserted.25import fs from 'node:fs';26import path from 'node:path';27import { createHash } from 'node:crypto';28import { createRequire } from 'node:module';29import type { DatabaseSync } from 'node:sqlite';30import { isBinary } from './git.ts';31import { MAX_HIGHLIGHT } from './highlight.ts';32import { IMAGE } from './repo.ts';33import type { Config, Repo, TreeEntry } from './types.ts';3435// Bump when the schema or what gets indexed changes.36const VERSION = 1;37export const CHUNK = 8;38// 16K pages keep every table at two levels (its root, then leaves) up to39// some 25M, so the browser can tell which page a row is on from the root.40const PAGE = 16384;41const MARKDOWN = /\.(md|markdown|mdown|mkd)$/i;42const LOCKFILES = new Set([43 'package-lock.json', 'npm-shrinkwrap.json', 'yarn.lock', 'pnpm-lock.yaml', 'bun.lock', 'deno.lock', 'composer.lock', 'gemfile.lock',44 'cargo.lock', 'go.sum', 'poetry.lock', 'pipfile.lock', 'uv.lock', 'pdm.lock', 'flake.lock', 'mix.lock', 'podfile.lock', 'packages.lock.json',45 'pubspec.lock', 'gradle.lockfile', 'package.resolved',46]);47const NOISE = /\.(min\.(js|css|mjs)|map)$/i;4849const require = createRequire(import.meta.url);50let sqlite: typeof import('node:sqlite') | null = null;51// node:sqlite warns that it is experimental on first use; builds stay quiet.52function db(file: string): DatabaseSync {53 if (!sqlite) {54 const emit = process.emitWarning;55 process.emitWarning = ((w: string | Error, ...rest: never[]) => (/SQLite/.test(String(w)) ? undefined : emit.call(process, w, ...rest))) as typeof emit;56 try {57 sqlite = require('node:sqlite') as typeof import('node:sqlite');58 } finally {59 process.emitWarning = emit;60 }61 }62 return new sqlite.DatabaseSync(file);63}6465export type Skip = 'binary' | 'large' | 'lockfile' | 'generated' | 'image' | 'link';6667// Why a file isn't indexed, from its tree entry alone; binary needs the bytes.68export function skipEntry(e: TreeEntry): Skip | null {69 if (e.mode === '120000' || e.mode === '160000') return 'link';70 if ((e.size ?? Infinity) > MAX_HIGHLIGHT) return 'large';71 const base = e.name.toLowerCase();72 if (LOCKFILES.has(base)) return 'lockfile';73 if (NOISE.test(base)) return 'generated';74 if (IMAGE.test(base)) return 'image';75 return null;76}7778export interface CodeStats {79 files: number;80 chunks: number;81 bytes: number;82 reused: number;83 skipped: Partial<Record<Skip, number>>;84 ms: number;85}8687// One file's place in the index, so the next tree can keep its chunks.88type Layout = Record<string, [oid: string, id: number, first: number, count: number]>;8990const key = (cfg: Config): string => createHash('sha1').update(`${VERSION} ${CHUNK} ${PAGE} ${cfg.maxFiles}`).digest('hex').slice(0, 8);9192// The index of the default branch's tree, built if it isn't cached, or null93// when the branch has no tree. Older indexes of the repo are removed (pages94// still being swapped out keep theirs: they are hard links).95export function codeIndex(cfg: Config, repo: Repo): { file: string; stats: CodeStats | null } | null {96 const tree = repo.trees.get(repo.defaultBranch);97 const oid = tree?.dirOids.get('');98 if (!tree || !oid) return null;99 const dir = path.join(cfg.cacheDir, 'code', repo.slug);100 const name = `${oid}.${key(cfg)}`;101 const file = path.join(dir, `${name}.db`);102 if (fs.existsSync(file)) return { file, stats: null };103 fs.mkdirSync(dir, { recursive: true });104 const old = fs.readdirSync(dir).filter((f) => f.endsWith('.db') && f !== `${name}.db`);105 // The newest earlier index of this schema, to start from.106 const base = old.filter((f) => f.endsWith(`.${key(cfg)}.db`) && fs.existsSync(path.join(dir, f.replace(/\.db$/, '.json'))))107 .map((f) => ({ f, t: fs.statSync(path.join(dir, f)).mtimeMs })).sort((a, b) => b.t - a.t)[0]?.f;108 const tmp = `${file}.${process.pid}`;109 const stats = build(repo, tree.blobs, tmp, base ? path.join(dir, base) : null);110 fs.writeFileSync(file.replace(/\.db$/, '.json'), JSON.stringify(stats.layout));111 fs.renameSync(tmp, file);112 // Earlier indexes, and scratch files of builds that died.113 for (const f of fs.readdirSync(dir)) if (f !== `${name}.db` && f !== `${name}.json`) fs.rmSync(path.join(dir, f), { force: true });114 return { file, stats: stats.stats };115}116117function build(repo: Repo, entries: TreeEntry[], out: string, base: string | null): { stats: CodeStats; layout: Layout } {118 const t0 = performance.now();119 const stats: CodeStats = { files: 0, chunks: 0, bytes: 0, reused: 0, skipped: {}, ms: 0 };120 const skip = (why: Skip): void => void (stats.skipped[why] = (stats.skipped[why] ?? 0) + 1);121 const want = entries.filter((e) => {122 const why = skipEntry(e);123 if (why) skip(why);124 return !why;125 });126 // Unchanged files keep their rows when there is an earlier index to start from.127 let prev: Layout = {};128 fs.rmSync(out, { force: true });129 if (base) {130 try {131 prev = JSON.parse(fs.readFileSync(base.replace(/\.db$/, '.json'), 'utf8'));132 fs.copyFileSync(base, out);133 } catch {134 prev = {};135 fs.rmSync(out, { force: true });136 }137 }138 const layout: Layout = {};139 const d = db(out);140 try {141 if (!fs.statSync(out).size) {142 d.exec(`pragma page_size = ${PAGE};143 create table file(id integer primary key, path text not null, source integer not null);144 create table chunk(id integer primary key, file integer not null, line integer not null, text text not null);145 create virtual table code using fts5(text, content='chunk', content_rowid='id', tokenize='trigram', detail=full, columnsize=0);`);146 }147 // A scratch file until it is renamed into place: no journal, no syncs.148 d.exec('pragma journal_mode = off; pragma synchronous = off; pragma temp_store = memory; begin');149 const keep = new Set(want.filter((e) => prev[e.path]?.[0] === e.oid).map((e) => e.path));150 // Rows of files that changed or went: out of the index, then the tables.151 const delFts = d.prepare(`insert into code(code, rowid, text) select 'delete', id, text from chunk where file = ?`);152 const delChunks = d.prepare('delete from chunk where file = ?');153 const delFile = d.prepare('delete from file where id = ?');154 for (const [p, [, id]] of Object.entries(prev)) {155 if (keep.has(p)) continue;156 delFts.run(id);157 delChunks.run(id);158 delFile.run(id);159 }160 // New rows go after the kept ones; ids are never reused.161 let nextFile = Math.max(0, ...Object.values(prev).map((v) => v[1])) + 1;162 let nextChunk = Math.max(0, ...Object.values(prev).map((v) => v[2] + v[3] - 1)) + 1;163 const insFile = d.prepare('insert into file(id, path, source) values (?, ?, ?)');164 const insChunk = d.prepare('insert into chunk(id, file, line, text) values (?, ?, ?, ?)');165 const insFts = d.prepare('insert into code(rowid, text) values (?, ?)');166 for (const e of want) {167 if (!keep.has(e.path)) continue;168 layout[e.path] = prev[e.path];169 stats.bytes += e.size ?? 0;170 }171 stats.reused = stats.files = keep.size;172 const todo = want.filter((e) => !keep.has(e.path));173 // Read blobs in batches so a big tree never sits in memory at once.174 for (let i = 0; i < todo.length;) {175 const batch: TreeEntry[] = [];176 for (let size = 0; i < todo.length && size < 32 << 20; i++) {177 batch.push(todo[i]);178 size += todo[i].size ?? 0;179 }180 const blobs = repo.loadBlobs(batch.map((e) => e.oid));181 for (const e of batch) {182 const data = blobs.get(e.oid)?.data;183 if (!data) continue;184 if (isBinary(data)) {185 skip('binary');186 continue;187 }188 const lines = data.toString('utf8').split('\n');189 if (lines.at(-1) === '') lines.pop();190 const id = nextFile++;191 const first = nextChunk;192 insFile.run(id, e.path, MARKDOWN.test(e.path) ? 1 : 0);193 for (let l = 0; l < lines.length; l += CHUNK) {194 const text = lines.slice(l, l + CHUNK).join('\n');195 insChunk.run(nextChunk, id, l + 1, text);196 insFts.run(nextChunk, text);197 nextChunk++;198 }199 layout[e.path] = [e.oid, id, first, nextChunk - first];200 stats.files++;201 stats.bytes += data.length;202 }203 }204 d.exec('commit');205 d.exec(`insert into code(code) values ('optimize')`);206 d.exec('vacuum');207 stats.chunks = (d.prepare('select count(*) n from chunk').get() as { n: number }).n;208 } finally {209 d.close();210 }211 stats.ms = Math.round(performance.now() - t0);212 return { stats, layout };213}