1/**
2 * Fetch closure computation over the commit graph (DESIGN.md §3.5).
3 *
4 * Implements the git layer's `ClosureSource`: BFS from wants over the
5 * `commits`/`commit_parents` tables stopping at negotiated haves,
6 * generation-bounded, depth-bounded when the client sent `deepen <n>`, then
7 * the full tree/blob closure of the new commits with one shared visited set.
8 *
9 * The v1 accepted fat (DESIGN.md §2.3): tree/blob closures of boundary
10 * (common) commits are **not** subtracted, so an incremental fetch may
11 * resend up to ~one snapshot's worth of trees/blobs — harmless to clients,
12 * cheap to compute. Generation numbers are used soundly in one place: the
13 * common-marking walk from haves never expands ancestors whose `gen` is
14 * below the minimum generation seen in the want walk (such commits can
15 * never be candidates, so the subtraction is unaffected).
16 *
17 * Manifest entries are ordered commits → tags → trees → blobs, and the
18 * total is capped at {@link MANIFEST_CAP} objects (the documented v1
19 * limit; larger repos wait for v1.1 whole-pack streaming).
20 */
21import * as Effect from "effect/Effect";
22import * as Schema from "effect/Schema";
23import {
24 parseTag,
25 parseTree,
26 treeEntryKind,
27 type ObjectType,
28 type Oid,
29 type ParsedTag,
30} from "../Protocol/ObjectCodec.ts";
31import {
32 StoreError,
33 type ClosureRequest,
34 type ClosureResult,
35 type ClosureSource,
36 type ManifestEntry,
37 type ObjectMeta,
38 type ObjectSource,
39} from "../Protocol/Store.ts";
40import type { SqlClient } from "./Sql.ts";
41
42// ─────────────────────────────────────────────────────────────────────────────
43// Constants & errors
44// ─────────────────────────────────────────────────────────────────────────────
45
46/**
47 * Maximum number of objects in one fetch manifest — 1 M for v1 (≈ 25 MB of
48 * visited-set memory; DESIGN.md §3.5). Larger repos are a documented v1
49 * limit until v1.1 whole-pack streaming.
50 */
51export const MANIFEST_CAP = 1_000_000;
52
53/**
54 * The fetch manifest exceeded {@link MANIFEST_CAP} objects. Surfaced to the
55 * protocol layer so it can send a clean in-band `ERR` pkt; folded into
56 * `StoreError` by {@link makeClosureSource} for callers that only speak the
57 * narrow `ClosureSource` contract.
58 */
59export class ManifestTooLarge extends Schema.TaggedError<ManifestTooLarge>()(
60 "ManifestTooLarge",
61 { count: Schema.Number, cap: Schema.Number },
62) {}
63
64// ─────────────────────────────────────────────────────────────────────────────
65// Options
66// ─────────────────────────────────────────────────────────────────────────────
67
68/**
69 * The object-store surface the closure walk needs: the read contract plus
70 * batched metadata (satisfied structurally by `ObjectStore`; trivial to fake
71 * in unit tests).
72 */
73export interface ClosureStore extends ObjectSource {
74 /** Batched metadata for many oids (live only; absent = missing). */
75 readonly getMetaBatch: (
76 oids: ReadonlyArray<Oid>,
77 ) => Effect.Effect<ReadonlyMap<Oid, ObjectMeta>, StoreError>;
78 /** Batched inflated content — one statement per tree LEVEL (DESIGN §22). */
79 readonly readContentBatch: (
80 oids: ReadonlyArray<Oid>,
81 ) => Effect.Effect<ReadonlyMap<Oid, Uint8Array>, StoreError>;
82}
83
84/**
85 * Dependencies of the closure computation. Plain values (not Layers) so
86 * `RepoObject.ts` wires it inside its inner per-instance effect.
87 */
88export interface ClosureOptions {
89 /** The repo DO's SQL client (commit-graph reads). */
90 readonly sql: SqlClient;
91 /** The repo's object store (tree/tag content reads + manifest metadata). */
92 readonly objects: ClosureStore;
93 /**
94 * Manifest object cap.
95 * @default MANIFEST_CAP
96 */
97 readonly manifestCap?: number | undefined;
98}
99
100// ─────────────────────────────────────────────────────────────────────────────
101// Commit-graph reads (batched, chunked-IN)
102// ─────────────────────────────────────────────────────────────────────────────
103
104interface CommitNode {
105 readonly oid: Oid;
106 readonly tree: Oid;
107 readonly gen: number;
108}
109
110interface CommitNodeRow extends Record<string, string | number> {
111 readonly oid: string;
112 readonly tree: string;
113 readonly gen: number;
114}
115
116interface ParentRow extends Record<string, string | number> {
117 readonly oid: string;
118 readonly parent: string;
119 readonly ord: number;
120}
121
122/** Loads `commits` rows for the given oids; missing oids are absent. */
123const loadCommitNodes = (
124 sql: SqlClient,
125 oids: ReadonlyArray<Oid>,
126): Effect.Effect<Map<Oid, CommitNode>, StoreError> =>
127 Effect.gen(function* () {
128 const map = new Map<Oid, CommitNode>();
129 if (oids.length === 0) {
130 return map;
131 }
132 const rows = yield* sql.inChunks<CommitNodeRow>(
133 (ph) => `SELECT oid, tree, gen FROM commits WHERE oid IN (${ph})`,
134 oids,
135 );
136 for (const row of rows) {
137 map.set(row.oid, { oid: row.oid, tree: row.tree, gen: row.gen });
138 }
139 return map;
140 });
141
142/** Loads ordered parent lists for the given oids; missing = no parents. */
143const loadParents = (
144 sql: SqlClient,
145 oids: ReadonlyArray<Oid>,
146): Effect.Effect<Map<Oid, Array<Oid>>, StoreError> =>
147 Effect.gen(function* () {
148 const map = new Map<Oid, Array<Oid>>();
149 if (oids.length === 0) {
150 return map;
151 }
152 const rows = yield* sql.inChunks<ParentRow>(
153 (ph) =>
154 `SELECT oid, parent, ord FROM commit_parents WHERE oid IN (${ph})`,
155 oids,
156 );
157 const grouped = new Map<Oid, Array<ParentRow>>();
158 for (const row of rows) {
159 const list = grouped.get(row.oid);
160 if (list === undefined) {
161 grouped.set(row.oid, [row]);
162 } else {
163 list.push(row);
164 }
165 }
166 for (const [oid, list] of grouped) {
167 list.sort((a, b) => a.ord - b.ord);
168 map.set(
169 oid,
170 list.map((row) => row.parent),
171 );
172 }
173 return map;
174 });
175
176// ─────────────────────────────────────────────────────────────────────────────
177// Closure computation
178// ─────────────────────────────────────────────────────────────────────────────
179
180const dedup = (oids: ReadonlyArray<Oid>): Array<Oid> =>
181 Array.from(new Set(oids));
182
183/** Maximum tag→target indirections tolerated before declaring corruption. */
184const MAX_TAG_CHAIN = 16;
185
186/**
187 * Computes the fetch closure (DESIGN.md §3.5) with the full error surface —
188 * {@link ManifestTooLarge} kept as its own tag so `UploadPack` can turn it
189 * into a clean in-band `ERR`. Use {@link makeClosureSource} when only the
190 * narrow `ClosureSource` contract is needed.
191 */
192export const computeClosure = (options: ClosureOptions) =>
193 Effect.fn(function* (request: ClosureRequest) {
194 const { sql, objects } = options;
195 const cap = options.manifestCap ?? MANIFEST_CAP;
196 const depth = request.depth;
197
198 // ── 1. Classify wants (peeling tag chains) ──────────────────────────────
199 const commitSeeds: Array<Oid> = [];
200 const tagOrder: Array<Oid> = [];
201 const tagSet = new Set<Oid>();
202 const treeRoots: Array<Oid> = [];
203 const wantBlobs: Array<Oid> = [];
204
205 const wants = dedup(request.wants);
206 const wantMetas = yield* objects.getMetaBatch(wants);
207 for (const want of wants) {
208 const wantMeta = wantMetas.get(want);
209 if (wantMeta === undefined) {
210 return yield* Effect.fail(
211 new StoreError({ reason: `want not found: ${want}` }),
212 );
213 }
214 let meta: ObjectMeta = wantMeta;
215 let hops = 0;
216 let done = false;
217 while (!done) {
218 switch (meta.type as ObjectType) {
219 case 1:
220 commitSeeds.push(meta.oid);
221 done = true;
222 break;
223 case 2:
224 treeRoots.push(meta.oid);
225 done = true;
226 break;
227 case 3:
228 wantBlobs.push(meta.oid);
229 done = true;
230 break;
231 case 4: {
232 hops += 1;
233 if (hops > MAX_TAG_CHAIN) {
234 return yield* Effect.fail(
235 new StoreError({ reason: `tag chain too deep at ${meta.oid}` }),
236 );
237 }
238 if (!tagSet.has(meta.oid)) {
239 tagSet.add(meta.oid);
240 tagOrder.push(meta.oid);
241 }
242 const content: Uint8Array = yield* objects.readContent(meta.oid);
243 const parsed: ParsedTag = yield* parseTag(content).pipe(
244 Effect.mapError(
245 (error) =>
246 new StoreError({
247 reason: `bad tag ${meta.oid}: ${error.reason}`,
248 }),
249 ),
250 );
251 const target: ObjectMeta | undefined = yield* objects.getMeta(
252 parsed.object,
253 );
254 if (target === undefined) {
255 return yield* Effect.fail(
256 new StoreError({
257 reason: `tag ${meta.oid} targets missing object ${parsed.object}`,
258 }),
259 );
260 }
261 meta = target;
262 break;
263 }
264 }
265 }
266 }
267
268 // ── 2. Boundaries ───────────────────────────────────────────────────────
269 // Haves are boundaries only if we actually have them as commits.
270 const repoShallowSet = new Set<Oid>(request.repoShallow ?? []);
271 const haveNodes = yield* loadCommitNodes(sql, dedup(request.haves));
272 const haveSet = new Set<Oid>(haveNodes.keys());
273 const clientShallowSet = new Set<Oid>(request.clientShallow);
274 // Without a deepen request the client's existing shallow tips are hard
275 // walk boundaries (the client has the tips; keep its boundary in place).
276 // With `deepen <n>` we re-walk by depth from the tips so previously
277 // shallow history can be completed (→ `unshallow`).
278 const shallowStopsActive = depth === undefined && clientShallowSet.size > 0;
279
280 // ── 3. Want-BFS over the commit graph ───────────────────────────────────
281 const candidateOrder: Array<CommitNode> = [];
282 const candidateSet = new Set<Oid>();
283 const parentsOf = new Map<Oid, ReadonlyArray<Oid>>();
284 const depthOf = new Map<Oid, number>();
285 let minCandidateGen = Number.POSITIVE_INFINITY;
286
287 // A `have` normally implies the client holds its whole ancestry — but
288 // NOT when that have is one of the client's shallow boundary tips and
289 // this is a deepen request: the whole point of `deepen <n>` is to fetch
290 // commits BEHIND those tips. Such seeds are walked through (so their
291 // ancestors enter the manifest) but stay excluded from the output via
292 // the common set.
293 const walkThroughHave = (oid: Oid): boolean =>
294 depth !== undefined && clientShallowSet.has(oid);
295 let frontier = dedup(commitSeeds).filter(
296 (oid) => !haveSet.has(oid) || walkThroughHave(oid),
297 );
298 const visited = new Set<Oid>(frontier);
299 for (const oid of frontier) {
300 depthOf.set(oid, 1);
301 }
302 while (frontier.length > 0) {
303 const nodes = yield* loadCommitNodes(sql, frontier);
304 const parents = yield* loadParents(sql, frontier);
305 const next: Array<Oid> = [];
306 for (const oid of frontier) {
307 const node = nodes.get(oid);
308 if (node === undefined) {
309 return yield* Effect.fail(
310 new StoreError({ reason: `commit graph missing commit ${oid}` }),
311 );
312 }
313 candidateOrder.push(node);
314 candidateSet.add(oid);
315 if (node.gen < minCandidateGen) {
316 minCandidateGen = node.gen;
317 }
318 const ps = parents.get(oid) ?? [];
319 parentsOf.set(oid, ps);
320 const d = depthOf.get(oid) ?? 1;
321 if (depth !== undefined && d >= depth) {
322 continue; // depth cut — do not expand parents
323 }
324 if (repoShallowSet.has(oid)) {
325 continue; // repo-shallow boundary — parents were never ingested
326 }
327 for (const parent of ps) {
328 if (
329 visited.has(parent) ||
330 (haveSet.has(parent) && !walkThroughHave(parent)) ||
331 (shallowStopsActive && clientShallowSet.has(parent))
332 ) {
333 continue;
334 }
335 visited.add(parent);
336 depthOf.set(parent, d + 1);
337 next.push(parent);
338 }
339 }
340 if (candidateOrder.length > cap) {
341 return yield* Effect.fail(
342 new ManifestTooLarge({ count: candidateOrder.length, cap }),
343 );
344 }
345 frontier = next;
346 }
347
348 // ── 4. Common marking (have ancestry, generation-bounded) ───────────────
349 const common = new Set<Oid>(haveSet);
350 if (haveSet.size > 0 && candidateOrder.length > 0) {
351 // Client-shallow haves contribute themselves to `common` but NOT
352 // their ancestry — the client does not hold anything behind its
353 // shallow boundary (that is what a deepen fetches).
354 let hFrontier = Array.from(haveSet).filter(
355 (oid) => !clientShallowSet.has(oid),
356 );
357 while (hFrontier.length > 0) {
358 const parents = yield* loadParents(sql, hFrontier);
359 const discovered: Array<Oid> = [];
360 for (const oid of hFrontier) {
361 for (const parent of parents.get(oid) ?? []) {
362 if (!common.has(parent)) {
363 common.add(parent);
364 discovered.push(parent);
365 }
366 }
367 }
368 if (discovered.length === 0) {
369 break;
370 }
371 // Expand only ancestors that could still intersect the candidate
372 // set: everything below minCandidateGen can never be a candidate.
373 const nodes = yield* loadCommitNodes(sql, discovered);
374 hFrontier = discovered.filter((oid) => {
375 const node = nodes.get(oid);
376 return node !== undefined && node.gen >= minCandidateGen;
377 });
378 }
379 }
380
381 // ── 5. New commits & shallow bookkeeping ────────────────────────────────
382 const newCommits = candidateOrder.filter((c) => !common.has(c.oid));
383 const included = new Set<Oid>(newCommits.map((c) => c.oid));
384
385 const shallow: Array<Oid> = [];
386 const shallowSet = new Set<Oid>();
387 if (
388 depth !== undefined ||
389 clientShallowSet.size > 0 ||
390 repoShallowSet.size > 0
391 ) {
392 for (const commit of newCommits) {
393 const ps = parentsOf.get(commit.oid) ?? [];
394 const cut = ps.some(
395 (parent) =>
396 !included.has(parent) &&
397 !common.has(parent) &&
398 !clientShallowSet.has(parent),
399 );
400 if (cut) {
401 shallow.push(commit.oid);
402 shallowSet.add(commit.oid);
403 }
404 }
405 }
406 // A previously-shallow tip unshallows when this walk covered it (as a
407 // new commit OR as a walked-through common have) and it is no longer a
408 // boundary.
409 const unshallow = Array.from(clientShallowSet).filter(
410 (oid) =>
411 (included.has(oid) || candidateSet.has(oid)) && !shallowSet.has(oid),
412 );
413
414 // ── 6. Tree/blob closure (shared visited set — the v1 fat) ──────────────
415 const treeOrder: Array<Oid> = [];
416 const blobOrder: Array<Oid> = [];
417 const visitedObjects = new Set<Oid>();
418 let total = newCommits.length + tagOrder.length;
419
420 const failIfOverCap = (count: number) =>
421 count > cap
422 ? Effect.fail(new ManifestTooLarge({ count, cap }))
423 : Effect.void;
424
425 for (const blob of wantBlobs) {
426 if (!visitedObjects.has(blob)) {
427 visitedObjects.add(blob);
428 blobOrder.push(blob);
429 total += 1;
430 }
431 }
432 yield* failIfOverCap(total);
433
434 const treeQueue: Array<Oid> = [];
435 for (const commit of newCommits) {
436 treeQueue.push(commit.tree);
437 }
438 for (const root of treeRoots) {
439 treeQueue.push(root);
440 }
441 // Level-order BFS (DESIGN §22): each level's trees are read with ONE
442 // batched statement and inflated together, instead of one SQL round
443 // trip per tree. Visitation order — and therefore the manifest — is the
444 // same breadth-first order the queue produced.
445 let level: Array<Oid> = treeQueue;
446 while (level.length > 0) {
447 const batch: Array<Oid> = [];
448 for (const tree of level) {
449 if (visitedObjects.has(tree)) continue;
450 visitedObjects.add(tree);
451 treeOrder.push(tree);
452 total += 1;
453 batch.push(tree);
454 }
455 yield* failIfOverCap(total);
456 if (batch.length === 0) break;
457 const contents = yield* objects.readContentBatch(batch);
458 const next: Array<Oid> = [];
459 for (const tree of batch) {
460 const content = contents.get(tree);
461 if (content === undefined) {
462 return yield* Effect.fail(
463 new StoreError({ reason: `tree ${tree} vanished during closure` }),
464 );
465 }
466 const entries = yield* parseTree(content).pipe(
467 Effect.mapError(
468 (error) =>
469 new StoreError({ reason: `bad tree ${tree}: ${error.reason}` }),
470 ),
471 );
472 for (const entry of entries) {
473 switch (treeEntryKind(entry.mode)) {
474 case "tree":
475 if (!visitedObjects.has(entry.oid)) {
476 next.push(entry.oid);
477 }
478 break;
479 case "blob":
480 if (!visitedObjects.has(entry.oid)) {
481 visitedObjects.add(entry.oid);
482 blobOrder.push(entry.oid);
483 total += 1;
484 }
485 break;
486 case "commit":
487 // gitlink (submodule) — the target commit lives in another repo
488 break;
489 }
490 }
491 }
492 yield* failIfOverCap(total);
493 level = next;
494 }
495
496 // ── 7. Materialize the manifest (commits → tags → trees → blobs) ────────
497 const orderedOids: Array<Oid> = [
498 ...newCommits.map((c) => c.oid),
499 ...tagOrder,
500 ...treeOrder,
501 ...blobOrder,
502 ];
503 const metas = yield* objects.getMetaBatch(orderedOids);
504 const entries: Array<ManifestEntry> = [];
505 for (const oid of orderedOids) {
506 const meta = metas.get(oid);
507 if (meta === undefined) {
508 return yield* Effect.fail(
509 new StoreError({ reason: `object ${oid} vanished during closure` }),
510 );
511 }
512 entries.push(meta);
513 }
514
515 const result: ClosureResult = { entries, shallow, unshallow };
516 return result;
517 });
518
519/**
520 * Creates the git layer's `ClosureSource` for one repo.
521 * {@link ManifestTooLarge} is folded into `StoreError` here to fit the
522 * narrow contract; protocol code that wants the distinct tag should call
523 * {@link computeClosure} directly.
524 */
525export const makeClosureSource = (options: ClosureOptions): ClosureSource => {
526 const compute = computeClosure(options);
527 return {
528 commitClosure: (request) =>
529 compute(request).pipe(
530 Effect.catchTag("ManifestTooLarge", (error) =>
531 Effect.fail(
532 new StoreError({
533 reason: `manifest exceeds ${error.cap} objects (v1 cap; got ${error.count})`,
534 }),
535 ),
536 ),
537 ),
538 };
539};