chunking.ts · Source

chunking.tspackages/search/src/chunking.tsraw ← src7,751 B← Back to the app
1/**
2 * @factory/search — content chunking for the indexer (ARCHITECTURE.md §6,
3 * ai-architecture §6 "content chunker").
4 *
5 * Pure, deterministic: same input → same chunks. Rules (recorded decisions):
6 *  1. Split on blank lines (paragraph boundaries) first; fenced code blocks
7 *     (``` / ~~~) are never split, and blank lines inside a fence do not
8 *     split. A paragraph larger than `maxChars` is hard-split on word
9 *     boundaries at ≤ `maxChars`.
10 *  2. Adjacent over-small pieces are merged up to `maxChars` (no 3-word chunks).
11 *  3. Consecutive chunks overlap by `overlapChars` (the tail of the previous
12 *     chunk is copied to the front of the next) so matches near boundaries
13 *     are not lost.
14 *  4. Token estimate = ceil(words / 0.75) (≈ 4 chars/token on English text);
15 *     the estimate is for budgeting only — the real count comes from the
16 *     embedding provider's usage.
17 */
18 
19import type { Chunk, ChunkOptions } from "./types.js";
20 
21export const DEFAULT_CHUNK_OPTIONS: Required<ChunkOptions> = {
22  maxChars: 800,
23  overlapChars: 120,
24};
25 
26/** Rough token estimate for budgeting (not billed). */
27export function estimateTokens(text: string): number {
28  const words = text.split(/\s+/).filter((w) => w.length > 0);
29  return Math.ceil(words.length / 0.75);
30}
31 
32/** True when a line starts a fenced code block (``` or ~~~). */
33function isFenceLine(line: string): boolean {
34  return /^\s*(```|~~~)/.test(line);
35}
36 
37interface Span {
38  text: string;
39  /** Offset of `text` inside the ORIGINAL source string. */
40  start: number;
41}
42 
43/**
44 * Split `text` into paragraph spans on blank lines. Fence pairs stay intact;
45 * blank lines inside a fence are ignored.
46 */
47function splitParagraphs(text: string): Span[] {
48  const out: Span[] = [];
49  const lines = text.split("\n");
50  const lineOffsets: number[] = [];
51  let cursor = 0;
52  for (const line of lines) {
53    lineOffsets.push(cursor);
54    cursor += line.length + 1;
55  }
56  let paraStartLine = 0;
57  let inFence = false;
58  for (let i = 0; i <= lines.length; i++) {
59    const atEnd = i === lines.length;
60    const line = atEnd ? "" : (lines[i] ?? "");
61    if (!atEnd && isFenceLine(line)) {
62      inFence = !inFence;
63      continue;
64    }
65    if (!atEnd && inFence && line.trim() === "") continue; // blank inside fence
66    const closes = atEnd || line.trim() === "";
67    if (closes) {
68      const s = lineOffsets[paraStartLine]!;
69      const e = atEnd ? text.length : lineOffsets[i]!;
70      const seg = text.slice(s, e);
71      const trimmed = seg.replace(/^\s+|\s+$/g, "");
72      if (trimmed.length > 0) {
73        out.push({ text: trimmed, start: s + (seg.length - seg.trimStart().length) });
74      }
75      paraStartLine = i + 1;
76    }
77  }
78  return out;
79}
80 
81/**
82 * Hard-split `paragraph` (a span inside `source`) into word-bounded pieces of
83 * ≤ maxChars, with exact offsets into `source`.
84 */
85function hardSplit(source: string, para: Span, maxChars: number): Span[] {
86  const out: Span[] = [];
87  let restStart = para.start;
88  const rest = () => source.slice(restStart, para.start + para.text.length);
89  while (rest().length > maxChars) {
90    let cut = rest().lastIndexOf(" ", maxChars);
91    if (cut < Math.floor(maxChars / 2)) cut = maxChars; // no space: hard cut
92    out.push({ text: rest().slice(0, cut).trimEnd(), start: restStart });
93    restStart += cut;
94    // skip the whitespace separator consumed between pieces
95    while (
96      restStart < para.start + para.text.length &&
97      (source[restStart] === " " || source[restStart] === "\t" || source[restStart] === "\n")
98    ) {
99      restStart++;
100    }
101  }
102  if (rest().length > 0) out.push({ text: rest(), start: restStart });
103  return out;
104}
105 
106/**
107 * Chunk `text` into pieces for indexing/embedding.
108 *
109 * Offsets (into the ORIGINAL, trimmed, CRLF-normalized text): every chunk —
110 * single-piece or merged — satisfies `source.slice(charStart, charEnd) ===
111 * text` exactly (the merge separator is the original gap between pieces).
112 * With overlap enabled, `text` additionally carries the previous chunk's
113 * tail at its front; the span still bounds the chunk's own content.
114 */
115export function chunkText(text: string, options?: ChunkOptions): Chunk[] {
116  const maxChars = options?.maxChars ?? DEFAULT_CHUNK_OPTIONS.maxChars;
117  let overlap = options?.overlapChars ?? DEFAULT_CHUNK_OPTIONS.overlapChars;
118  if (overlap <= 0) overlap = 0;
119  if (overlap > Math.floor(maxChars / 4)) overlap = Math.floor(maxChars / 4);
120 
121  const source = text.replace(/\r\n/g, "\n").trim();
122  if (source.length === 0) return [];
123 
124  // 1) paragraphs (fences intact) → 2) hard-split the oversized ones.
125  //    When an oversized fence must be split, each chunk is re-bracketed with
126  //    the ORIGINAL opening line (```ts keeps its info string) and the last
127  //    chunk carries the closing line, so no chunk is left with an unbalanced
128  //    fence. Recorded decision: re-bracketed fence chunks may exceed
129  //    maxChars by the fence line(s) — the integrity guarantee (balanced
130  //    fences per chunk) outranks the exact size budget.
131  const pieces: Span[] = [];
132  for (const para of splitParagraphs(source)) {
133    if (para.text.length <= maxChars) {
134      pieces.push(para);
135      continue;
136    }
137    const hp = hardSplit(source, para, maxChars);
138    const fenceMark = para.text.match(/^\s*(```|~~~)/)?.[1];
139    if (!fenceMark) {
140      pieces.push(...hp);
141      continue;
142    }
143    const openLine = para.text.slice(0, para.text.indexOf("\n") === -1 ? para.text.length : para.text.indexOf("\n"));
144    const trimmedEnd = para.text.replace(/\s+$/, "");
145    const closed = trimmedEnd.endsWith(fenceMark);
146    const closeLine = closed ? trimmedEnd.slice(trimmedEnd.lastIndexOf("\n") + 1) : "";
147    let index = 0;
148    for (const piece of hp) {
149      const first = index === 0;
150      const last = index === hp.length - 1;
151      let text = piece.text;
152      if (!first && !/^\s*(```|~~~)/.test(text)) text = openLine + "\n" + text;
153      if (last && closed && !/(```|~~~)\s*$/.test(text)) text = text + "\n" + closeLine;
154      pieces.push({ ...piece, text });
155      index++;
156    }
157  }
158 
159  // 3) merge adjacent over-small pieces up to maxChars (track exact end).
160  //    The separator is the ORIGINAL gap between the pieces in the source, so
161  //    the merged text is byte-identical to source.slice(start, end).
162  const merged: (Span & { end: number })[] = [];
163  for (const piece of pieces) {
164    const last = merged[merged.length - 1];
165    if (last) {
166      const gap = source.slice(last.end, piece.start);
167      if (last.text.length + gap.length + piece.text.length <= maxChars) {
168        last.text = last.text + gap + piece.text;
169        last.end = piece.start + piece.text.length;
170        continue;
171      }
172    }
173    merged.push({ ...piece, end: piece.start + piece.text.length });
174  }
175 
176  // 4) overlap: copy the tail (last `overlap` chars) of the previous chunk
177  //    to the front of the next one.
178  const chunks: Chunk[] = [];
179  let prevTail: string | null = null;
180  for (const piece of merged) {
181    let body = piece.text;
182    if (prevTail) {
183      body = prevTail + "\n" + piece.text;
184      if (body.length > maxChars) {
185        // overlap overflowed the budget: shrink the copied tail
186        const budget = maxChars - piece.text.length - 1;
187        body = budget > 0 ? prevTail.slice(Math.max(0, prevTail.length - budget)) + "\n" + piece.text : piece.text;
188      }
189    }
190    chunks.push({
191      chunkIndex: chunks.length,
192      text: body,
193      charStart: piece.start,
194      charEnd: piece.end,
195      tokens: estimateTokens(piece.text),
196    });
197    // NOTE: slice(-0) === slice(0) === whole string, so gate on overlap > 0
198    prevTail = overlap > 0 ? piece.text.slice(-overlap) || null : null;
199  }
200  return chunks;
201}
202