@devries-cameron20 / t3code Mirror · read-only
Fork 0

The best way to control Claude Code, Codex and more from any computer or phone

Mirrored from https://github.com/Camo67/t3code.git

Synced Nov 21, 04:45 UTC

main
ts 504 lines 19.5 KB
Raw
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 */
21 import * as Effect from "effect/Effect";
22 import * as Schema from "effect/Schema";
23 import {
24 parseTag,
25 parseTree,
26 treeEntryKind,
27 type ObjectType,
28 type Oid,
29 type ParsedTag,
30 } from "../Protocol/ObjectCodec.ts";
31 import {
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";
40 import 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 */
51 export 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 */
59 export class ManifestTooLarge extends Schema.TaggedError<ManifestTooLarge>()("ManifestTooLarge", {
60 count: Schema.Number,
61 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 */
73 export 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 */
88 export 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
104 interface CommitNode {
105 readonly oid: Oid;
106 readonly tree: Oid;
107 readonly gen: number;
108 }
109
110 interface CommitNodeRow extends Record<string, string | number> {
111 readonly oid: string;
112 readonly tree: string;
113 readonly gen: number;
114 }
115
116 interface 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. */
123 const 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. */
143 const 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) => `SELECT oid, parent, ord FROM commit_parents WHERE oid IN (${ph})`,
154 oids,
155 );
156 const grouped = new Map<Oid, Array<ParentRow>>();
157 for (const row of rows) {
158 const list = grouped.get(row.oid);
159 if (list === undefined) {
160 grouped.set(row.oid, [row]);
161 } else {
162 list.push(row);
163 }
164 }
165 for (const [oid, list] of grouped) {
166 list.sort((a, b) => a.ord - b.ord);
167 map.set(
168 oid,
169 list.map((row) => row.parent),
170 );
171 }
172 return map;
173 });
174
175 // ─────────────────────────────────────────────────────────────────────────────
176 // Closure computation
177 // ─────────────────────────────────────────────────────────────────────────────
178
179 const dedup = (oids: ReadonlyArray<Oid>): Array<Oid> => Array.from(new Set(oids));
180
181 /** Maximum tag→target indirections tolerated before declaring corruption. */
182 const MAX_TAG_CHAIN = 16;
183
184 /**
185 * Computes the fetch closure (DESIGN.md §3.5) with the full error surface —
186 * {@link ManifestTooLarge} kept as its own tag so `UploadPack` can turn it
187 * into a clean in-band `ERR`. Use {@link makeClosureSource} when only the
188 * narrow `ClosureSource` contract is needed.
189 */
190 export const computeClosure = (options: ClosureOptions) =>
191 Effect.fn(function* (request: ClosureRequest) {
192 const { sql, objects } = options;
193 const cap = options.manifestCap ?? MANIFEST_CAP;
194 const depth = request.depth;
195
196 // ── 1. Classify wants (peeling tag chains) ──────────────────────────────
197 const commitSeeds: Array<Oid> = [];
198 const tagOrder: Array<Oid> = [];
199 const tagSet = new Set<Oid>();
200 const treeRoots: Array<Oid> = [];
201 const wantBlobs: Array<Oid> = [];
202
203 const wants = dedup(request.wants);
204 const wantMetas = yield* objects.getMetaBatch(wants);
205 for (const want of wants) {
206 const wantMeta = wantMetas.get(want);
207 if (wantMeta === undefined) {
208 return yield* StoreError.make({ reason: `want not found: ${want}` });
209 }
210 let meta: ObjectMeta = wantMeta;
211 let hops = 0;
212 let done = false;
213 while (!done) {
214 switch (meta.type as ObjectType) {
215 case 1:
216 commitSeeds.push(meta.oid);
217 done = true;
218 break;
219 case 2:
220 treeRoots.push(meta.oid);
221 done = true;
222 break;
223 case 3:
224 wantBlobs.push(meta.oid);
225 done = true;
226 break;
227 case 4: {
228 hops += 1;
229 if (hops > MAX_TAG_CHAIN) {
230 return yield* StoreError.make({ reason: `tag chain too deep at ${meta.oid}` });
231 }
232 if (!tagSet.has(meta.oid)) {
233 tagSet.add(meta.oid);
234 tagOrder.push(meta.oid);
235 }
236 const content: Uint8Array = yield* objects.readContent(meta.oid);
237 const parsed: ParsedTag = yield* parseTag(content).pipe(
238 Effect.mapError((error) =>
239 StoreError.make({
240 reason: `bad tag ${meta.oid}: ${error.reason}`,
241 }),
242 ),
243 );
244 const target: ObjectMeta | undefined = yield* objects.getMeta(parsed.object);
245 if (target === undefined) {
246 return yield* StoreError.make({
247 reason: `tag ${meta.oid} targets missing object ${parsed.object}`,
248 });
249 }
250 meta = target;
251 break;
252 }
253 }
254 }
255 }
256
257 // ── 2. Boundaries ───────────────────────────────────────────────────────
258 // Haves are boundaries only if we actually have them as commits.
259 const repoShallowSet = new Set<Oid>(request.repoShallow ?? []);
260 const haveNodes = yield* loadCommitNodes(sql, dedup(request.haves));
261 const haveSet = new Set<Oid>(haveNodes.keys());
262 const clientShallowSet = new Set<Oid>(request.clientShallow);
263 // Without a deepen request the client's existing shallow tips are hard
264 // walk boundaries (the client has the tips; keep its boundary in place).
265 // With `deepen <n>` we re-walk by depth from the tips so previously
266 // shallow history can be completed (→ `unshallow`).
267 const shallowStopsActive = depth === undefined && clientShallowSet.size > 0;
268
269 // ── 3. Want-BFS over the commit graph ───────────────────────────────────
270 const candidateOrder: Array<CommitNode> = [];
271 const candidateSet = new Set<Oid>();
272 const parentsOf = new Map<Oid, ReadonlyArray<Oid>>();
273 const depthOf = new Map<Oid, number>();
274 let minCandidateGen = Number.POSITIVE_INFINITY;
275
276 // A `have` normally implies the client holds its whole ancestry — but
277 // NOT when that have is one of the client's shallow boundary tips and
278 // this is a deepen request: the whole point of `deepen <n>` is to fetch
279 // commits BEHIND those tips. Such seeds are walked through (so their
280 // ancestors enter the manifest) but stay excluded from the output via
281 // the common set.
282 const walkThroughHave = (oid: Oid): boolean => depth !== undefined && clientShallowSet.has(oid);
283 let frontier = dedup(commitSeeds).filter((oid) => !haveSet.has(oid) || walkThroughHave(oid));
284 const visited = new Set<Oid>(frontier);
285 for (const oid of frontier) {
286 depthOf.set(oid, 1);
287 }
288 while (frontier.length > 0) {
289 const nodes = yield* loadCommitNodes(sql, frontier);
290 const parents = yield* loadParents(sql, frontier);
291 const next: Array<Oid> = [];
292 for (const oid of frontier) {
293 const node = nodes.get(oid);
294 if (node === undefined) {
295 return yield* StoreError.make({ reason: `commit graph missing commit ${oid}` });
296 }
297 candidateOrder.push(node);
298 candidateSet.add(oid);
299 if (node.gen < minCandidateGen) {
300 minCandidateGen = node.gen;
301 }
302 const ps = parents.get(oid) ?? [];
303 parentsOf.set(oid, ps);
304 const d = depthOf.get(oid) ?? 1;
305 if (depth !== undefined && d >= depth) {
306 continue; // depth cut — do not expand parents
307 }
308 if (repoShallowSet.has(oid)) {
309 continue; // repo-shallow boundary — parents were never ingested
310 }
311 for (const parent of ps) {
312 if (
313 visited.has(parent) ||
314 (haveSet.has(parent) && !walkThroughHave(parent)) ||
315 (shallowStopsActive && clientShallowSet.has(parent))
316 ) {
317 continue;
318 }
319 visited.add(parent);
320 depthOf.set(parent, d + 1);
321 next.push(parent);
322 }
323 }
324 if (candidateOrder.length > cap) {
325 return yield* ManifestTooLarge.make({ count: candidateOrder.length, cap });
326 }
327 frontier = next;
328 }
329
330 // ── 4. Common marking (have ancestry, generation-bounded) ───────────────
331 const common = new Set<Oid>(haveSet);
332 if (haveSet.size > 0 && candidateOrder.length > 0) {
333 // Client-shallow haves contribute themselves to `common` but NOT
334 // their ancestry — the client does not hold anything behind its
335 // shallow boundary (that is what a deepen fetches).
336 let hFrontier = Array.from(haveSet).filter((oid) => !clientShallowSet.has(oid));
337 while (hFrontier.length > 0) {
338 const parents = yield* loadParents(sql, hFrontier);
339 const discovered: Array<Oid> = [];
340 for (const oid of hFrontier) {
341 for (const parent of parents.get(oid) ?? []) {
342 if (!common.has(parent)) {
343 common.add(parent);
344 discovered.push(parent);
345 }
346 }
347 }
348 if (discovered.length === 0) {
349 break;
350 }
351 // Expand only ancestors that could still intersect the candidate
352 // set: everything below minCandidateGen can never be a candidate.
353 const nodes = yield* loadCommitNodes(sql, discovered);
354 hFrontier = discovered.filter((oid) => {
355 const node = nodes.get(oid);
356 return node !== undefined && node.gen >= minCandidateGen;
357 });
358 }
359 }
360
361 // ── 5. New commits & shallow bookkeeping ────────────────────────────────
362 const newCommits = candidateOrder.filter((c) => !common.has(c.oid));
363 const included = new Set<Oid>(newCommits.map((c) => c.oid));
364
365 const shallow: Array<Oid> = [];
366 const shallowSet = new Set<Oid>();
367 if (depth !== undefined || clientShallowSet.size > 0 || repoShallowSet.size > 0) {
368 for (const commit of newCommits) {
369 const ps = parentsOf.get(commit.oid) ?? [];
370 const cut = ps.some(
371 (parent) => !included.has(parent) && !common.has(parent) && !clientShallowSet.has(parent),
372 );
373 if (cut) {
374 shallow.push(commit.oid);
375 shallowSet.add(commit.oid);
376 }
377 }
378 }
379 // A previously-shallow tip unshallows when this walk covered it (as a
380 // new commit OR as a walked-through common have) and it is no longer a
381 // boundary.
382 const unshallow = Array.from(clientShallowSet).filter(
383 (oid) => (included.has(oid) || candidateSet.has(oid)) && !shallowSet.has(oid),
384 );
385
386 // ── 6. Tree/blob closure (shared visited set — the v1 fat) ──────────────
387 const treeOrder: Array<Oid> = [];
388 const blobOrder: Array<Oid> = [];
389 const visitedObjects = new Set<Oid>();
390 let total = newCommits.length + tagOrder.length;
391
392 const failIfOverCap = (count: number) =>
393 count > cap ? Effect.fail(ManifestTooLarge.make({ count, cap })) : Effect.void;
394
395 for (const blob of wantBlobs) {
396 if (!visitedObjects.has(blob)) {
397 visitedObjects.add(blob);
398 blobOrder.push(blob);
399 total += 1;
400 }
401 }
402 yield* failIfOverCap(total);
403
404 const treeQueue: Array<Oid> = [];
405 for (const commit of newCommits) {
406 treeQueue.push(commit.tree);
407 }
408 for (const root of treeRoots) {
409 treeQueue.push(root);
410 }
411 // Level-order BFS (DESIGN §22): each level's trees are read with ONE
412 // batched statement and inflated together, instead of one SQL round
413 // trip per tree. Visitation order — and therefore the manifest — is the
414 // same breadth-first order the queue produced.
415 let level: Array<Oid> = treeQueue;
416 while (level.length > 0) {
417 const batch: Array<Oid> = [];
418 for (const tree of level) {
419 if (visitedObjects.has(tree)) continue;
420 visitedObjects.add(tree);
421 treeOrder.push(tree);
422 total += 1;
423 batch.push(tree);
424 }
425 yield* failIfOverCap(total);
426 if (batch.length === 0) break;
427 const contents = yield* objects.readContentBatch(batch);
428 const next: Array<Oid> = [];
429 for (const tree of batch) {
430 const content = contents.get(tree);
431 if (content === undefined) {
432 return yield* StoreError.make({ reason: `tree ${tree} vanished during closure` });
433 }
434 const entries = yield* parseTree(content).pipe(
435 Effect.mapError((error) =>
436 StoreError.make({ reason: `bad tree ${tree}: ${error.reason}` }),
437 ),
438 );
439 for (const entry of entries) {
440 switch (treeEntryKind(entry.mode)) {
441 case "tree":
442 if (!visitedObjects.has(entry.oid)) {
443 next.push(entry.oid);
444 }
445 break;
446 case "blob":
447 if (!visitedObjects.has(entry.oid)) {
448 visitedObjects.add(entry.oid);
449 blobOrder.push(entry.oid);
450 total += 1;
451 }
452 break;
453 case "commit":
454 // gitlink (submodule) — the target commit lives in another repo
455 break;
456 }
457 }
458 }
459 yield* failIfOverCap(total);
460 level = next;
461 }
462
463 // ── 7. Materialize the manifest (commits → tags → trees → blobs) ────────
464 const orderedOids: Array<Oid> = [
465 ...newCommits.map((c) => c.oid),
466 ...tagOrder,
467 ...treeOrder,
468 ...blobOrder,
469 ];
470 const metas = yield* objects.getMetaBatch(orderedOids);
471 const entries: Array<ManifestEntry> = [];
472 for (const oid of orderedOids) {
473 const meta = metas.get(oid);
474 if (meta === undefined) {
475 return yield* StoreError.make({ reason: `object ${oid} vanished during closure` });
476 }
477 entries.push(meta);
478 }
479
480 const result: ClosureResult = { entries, shallow, unshallow };
481 return result;
482 });
483
484 /**
485 * Creates the git layer's `ClosureSource` for one repo.
486 * {@link ManifestTooLarge} is folded into `StoreError` here to fit the
487 * narrow contract; protocol code that wants the distinct tag should call
488 * {@link computeClosure} directly.
489 */
490 export const makeClosureSource = (options: ClosureOptions): ClosureSource => {
491 const compute = computeClosure(options);
492 return {
493 commitClosure: (request) =>
494 compute(request).pipe(
495 Effect.catchTag("ManifestTooLarge", (error) =>
496 Effect.fail(
497 StoreError.make({
498 reason: `manifest exceeds ${error.cap} objects (v1 cap; got ${error.count})`,
499 }),
500 ),
501 ),
502 ),
503 };
504 };