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

main
ts 459 lines 17.7 KB
Raw
1 /**
2 * Pure recursive tree diff (the server-side diff surface, DESIGN.md §5).
3 *
4 * Compares two trees keyed by entry **name** (NOT a two-pointer merge —
5 * git's canonical sort treats directories as `name/`, so a name that is a
6 * blob in one tree and a tree in the other would mis-pair). Only descends
7 * into subtree pairs whose oids differ; identical oids (with identical
8 * modes) are skipped without reading the subtree at all. That pruning is
9 * what makes a 12k-file tree cost O(changed) — a commit touching k files
10 * opens only the ~k·depth trees on the changed root-to-leaf paths (each a
11 * single SQLite row read + inflate of a few KB).
12 *
13 * Worst case (root commit: everything added) is bounded by the caps:
14 * recursion **stops descending** once {@link MAX_DIFF_FILES} entries are
15 * emitted (it does not enumerate-then-truncate) and
16 * {@link MAX_DIFF_TREE_READS} bounds tree opens defensively.
17 *
18 * Like the rest of `src/Protocol/`, this module depends only on data-shaped
19 * store contracts so it stays unit-testable with in-memory fakes.
20 */
21 import * as Effect from "effect/Effect";
22 import {
23 encodeTree,
24 GITLINK_MODE,
25 hashObject,
26 ObjectType,
27 parseTree,
28 TREE_MODE,
29 treeEntryKind,
30 type Oid,
31 type TreeEntry,
32 } from "./ObjectCodec.ts";
33 import { StoreError } from "./Store.ts";
34
35 /** Max files emitted by a tree diff before `truncated: true`. */
36 export const MAX_DIFF_FILES = 1000;
37
38 /**
39 * Defensive bound on tree objects opened per diff (a 12k-file repo with
40 * identical-subtree pruning opens O(changed-paths · depth), typically <50).
41 */
42 export const MAX_DIFF_TREE_READS = 5000;
43
44 /** One changed file (see the REST `DiffEntry` schema). */
45 export interface DiffEntryData {
46 readonly path: string;
47 readonly status: "added" | "removed" | "modified";
48 readonly oldOid?: string | undefined;
49 readonly newOid?: string | undefined;
50 readonly oldMode?: string | undefined;
51 readonly newMode?: string | undefined;
52 readonly oldSize?: number | undefined;
53 readonly newSize?: number | undefined;
54 }
55
56 /** Result of {@link diffTrees}. */
57 export interface TreeDiffResult {
58 readonly files: Array<DiffEntryData>;
59 readonly truncated: boolean;
60 }
61
62 /**
63 * The read surface {@link diffTrees} needs — a structural subset of
64 * `ObjectStore` (`readContent` + `getMetaBatch`).
65 */
66 export interface TreeDiffObjects {
67 /** Reads and inflates the full object content. */
68 readonly readContent: (oid: Oid) => Effect.Effect<Uint8Array, StoreError>;
69 /** Batched metadata; missing oids are simply absent from the map. */
70 readonly getMetaBatch: (
71 oids: ReadonlyArray<Oid>,
72 ) => Effect.Effect<ReadonlyMap<Oid, { readonly size: number }>, StoreError>;
73 }
74
75 /**
76 * Recursive tree diff. `oldTree`/`newTree` are tree oids; `undefined`
77 * means the empty tree on that side (a root commit diffs against
78 * `undefined` and every file comes out `added`).
79 *
80 * Mode-only changes (same blob oid, different mode) still report
81 * `modified`. Kind changes (blob↔tree, gitlink↔tree) emit the removal of
82 * everything on the old side and the addition of everything on the new
83 * side. Gitlink (mode `160000`) entries are leaves whose oids are commit
84 * oids — they carry no sizes.
85 */
86 export const diffTrees = (
87 objects: TreeDiffObjects,
88 oldTree: Oid | undefined,
89 newTree: Oid | undefined,
90 ): Effect.Effect<TreeDiffResult, StoreError> =>
91 Effect.gen(function* () {
92 const files: Array<DiffEntryData> = [];
93 let treeReads = 0;
94 let truncated = false;
95
96 const readTree = Effect.fn(function* (oid: Oid) {
97 if (++treeReads > MAX_DIFF_TREE_READS) {
98 truncated = true;
99 return [] as ReadonlyArray<TreeEntry>;
100 }
101 const content = yield* objects.readContent(oid);
102 return yield* parseTree(content).pipe(
103 Effect.mapError((e) => StoreError.make({ reason: e.reason })),
104 );
105 });
106
107 const emit = (entry: DiffEntryData): boolean => {
108 if (files.length >= MAX_DIFF_FILES) {
109 truncated = true;
110 return false;
111 }
112 files.push(entry);
113 return true;
114 };
115
116 /** Emit every blob/gitlink under `tree` as added or removed. */
117 const emitAll = (
118 tree: Oid,
119 prefix: string,
120 side: "added" | "removed",
121 ): Effect.Effect<void, StoreError> =>
122 Effect.gen(function* () {
123 if (truncated) return;
124 const entries = yield* readTree(tree);
125 for (const e of entries) {
126 if (truncated) return;
127 const path = prefix + e.name;
128 const kind = treeEntryKind(e.mode);
129 if (kind === "tree") {
130 yield* emitAll(e.oid, `${path}/`, side);
131 continue;
132 }
133 // blob or gitlink — a leaf either way
134 emit(
135 side === "added"
136 ? { path, status: "added", newOid: e.oid, newMode: e.mode }
137 : { path, status: "removed", oldOid: e.oid, oldMode: e.mode },
138 );
139 }
140 });
141
142 const walk = (
143 oldOid: Oid | undefined,
144 newOid: Oid | undefined,
145 prefix: string,
146 ): Effect.Effect<void, StoreError> =>
147 Effect.gen(function* () {
148 if (truncated) return;
149 if (oldOid === newOid) return; // identical-subtree prune (root incl.)
150 if (oldOid === undefined) {
151 if (newOid !== undefined) yield* emitAll(newOid, prefix, "added");
152 return;
153 }
154 if (newOid === undefined) {
155 yield* emitAll(oldOid, prefix, "removed");
156 return;
157 }
158 const oldEntries = yield* readTree(oldOid);
159 const newEntries = yield* readTree(newOid);
160 const oldByName = new Map(oldEntries.map((e) => [e.name, e]));
161 const newByName = new Map(newEntries.map((e) => [e.name, e]));
162 const names = Array.from(new Set([...oldByName.keys(), ...newByName.keys()])).sort(); // deterministic output order
163 for (const name of names) {
164 if (truncated) return;
165 const o = oldByName.get(name);
166 const n = newByName.get(name);
167 const path = prefix + name;
168 if (o === undefined) {
169 // added on the new side
170 const kind = treeEntryKind(n!.mode);
171 if (kind === "tree") yield* emitAll(n!.oid, `${path}/`, "added");
172 else {
173 emit({ path, status: "added", newOid: n!.oid, newMode: n!.mode });
174 }
175 continue;
176 }
177 if (n === undefined) {
178 const kind = treeEntryKind(o.mode);
179 if (kind === "tree") yield* emitAll(o.oid, `${path}/`, "removed");
180 else {
181 emit({ path, status: "removed", oldOid: o.oid, oldMode: o.mode });
182 }
183 continue;
184 }
185 if (o.oid === n.oid && o.mode === n.mode) continue; // untouched — prune
186 const oKind = treeEntryKind(o.mode);
187 const nKind = treeEntryKind(n.mode);
188 if (oKind === "tree" && nKind === "tree") {
189 yield* walk(o.oid, n.oid, `${path}/`); // descend: oids differ
190 } else if (oKind === "tree" || nKind === "tree") {
191 // kind change (blob↔tree, gitlink↔tree): removed + added
192 if (oKind === "tree") yield* emitAll(o.oid, `${path}/`, "removed");
193 else {
194 emit({ path, status: "removed", oldOid: o.oid, oldMode: o.mode });
195 }
196 if (nKind === "tree") yield* emitAll(n.oid, `${path}/`, "added");
197 else {
198 emit({ path, status: "added", newOid: n.oid, newMode: n.mode });
199 }
200 } else {
201 // blob/gitlink on both sides: content and/or mode change.
202 // Mode-only change (o.oid === n.oid) still reports `modified`.
203 emit({
204 path,
205 status: "modified",
206 oldOid: o.oid,
207 newOid: n.oid,
208 oldMode: o.mode,
209 newMode: n.mode,
210 });
211 }
212 }
213 });
214
215 yield* walk(oldTree, newTree, "");
216
217 // Fill sizes for blob entries in ONE chunked metadata query so clients
218 // can gate binary/oversize files without fetching. Gitlink oids won't
219 // be in `objects` and simply stay size-less.
220 const blobOids = new Set<Oid>();
221 for (const f of files) {
222 if (f.oldOid !== undefined && f.oldMode !== GITLINK_MODE) {
223 blobOids.add(f.oldOid);
224 }
225 if (f.newOid !== undefined && f.newMode !== GITLINK_MODE) {
226 blobOids.add(f.newOid);
227 }
228 }
229 const metas = yield* objects.getMetaBatch(Array.from(blobOids));
230 const sized = files.map((f): DiffEntryData => ({
231 ...f,
232 oldSize: f.oldOid !== undefined ? metas.get(f.oldOid)?.size : undefined,
233 newSize: f.newOid !== undefined ? metas.get(f.newOid)?.size : undefined,
234 }));
235 return { files: sized, truncated };
236 });
237
238 // ─────────────────────────────────────────────────────────────────────────────
239 // conflictingPaths — the trivial-merge admissibility test
240 // ─────────────────────────────────────────────────────────────────────────────
241
242 /** `true` when both sides made the identical change (same result). */
243 const identicalChange = (a: DiffEntryData, b: DiffEntryData): boolean =>
244 a.status === b.status && a.newOid === b.newOid && a.newMode === b.newMode;
245
246 /**
247 * The paths that make a three-way merge non-trivial: changed on **both**
248 * sides relative to the merge base (minus paths where both sides made the
249 * identical change — same new oid+mode, or both deleted), plus
250 * directory/file collisions where a leaf now occupies `p` on one side
251 * while the other side changed something under `p/`. Sorted.
252 */
253 export const conflictingPaths = (
254 baseChanges: ReadonlyArray<DiffEntryData>,
255 headChanges: ReadonlyArray<DiffEntryData>,
256 ): Array<string> => {
257 const conflicts = new Set<string>();
258 const baseBy = new Map(baseChanges.map((f) => [f.path, f]));
259 const headBy = new Map(headChanges.map((f) => [f.path, f]));
260 for (const [path, head] of headBy) {
261 const base = baseBy.get(path);
262 if (base !== undefined && !identicalChange(base, head)) {
263 conflicts.add(path);
264 }
265 }
266 // Directory/file collision: one side's add/modify puts a *leaf* at `dir`
267 // while the other side changes a path under `dir/` — the leaf and the
268 // directory cannot both exist. (A `removed` ancestor never collides: at
269 // the merge base a name is either a leaf or a directory, never both.)
270 const addAncestorConflicts = (
271 leaves: ReadonlyMap<string, DiffEntryData>,
272 others: ReadonlyMap<string, DiffEntryData>,
273 ) => {
274 for (const path of others.keys()) {
275 let idx = path.lastIndexOf("/");
276 while (idx > 0) {
277 const dir = path.slice(0, idx);
278 const leaf = leaves.get(dir);
279 if (leaf !== undefined && leaf.newOid !== undefined) {
280 conflicts.add(path);
281 }
282 idx = dir.lastIndexOf("/");
283 }
284 }
285 };
286 addAncestorConflicts(baseBy, headBy);
287 addAncestorConflicts(headBy, baseBy);
288 return Array.from(conflicts).sort();
289 };
290
291 // ─────────────────────────────────────────────────────────────────────────────
292 // applyTreeChanges — the trivial-merge tree builder
293 // ─────────────────────────────────────────────────────────────────────────────
294
295 /** A tree object created by {@link applyTreeChanges} (bottom-up order). */
296 export interface NewTreeObject {
297 readonly oid: Oid;
298 readonly content: Uint8Array;
299 }
300
301 /** Result of {@link applyTreeChanges}. */
302 export interface ApplyTreeChangesResult {
303 /** Root tree oid after the changes (may equal `baseTree` on a no-op). */
304 readonly root: Oid;
305 /**
306 * Every tree object whose content was (re)built, bottom-up. Some may
307 * already exist in the store — staging is idempotent, so callers just
308 * stage them all.
309 */
310 readonly newTrees: ReadonlyArray<NewTreeObject>;
311 }
312
313 /** One directory level of the nested change tree. */
314 interface ChangeNode {
315 /** Leaf change addressed exactly at this name. */
316 leaf?: DiffEntryData;
317 /** Changes below this name (it is a directory on some side). */
318 children?: Map<string, ChangeNode>;
319 }
320
321 /**
322 * Applies leaf-level changes (a {@link diffTrees} file list, e.g. the
323 * mergeBase→head changes of a trivial three-way merge) onto `baseTree`,
324 * rebuilding every touched directory bottom-up with the canonical
325 * {@link encodeTree}. Directories that become empty are dropped from their
326 * parent (git has no empty trees in practice).
327 *
328 * Kind changes compose from the diff's leaf pairs without special cases:
329 * dir→file arrives as deletions under `p/` plus a leaf add at `p` (the
330 * emptied subtree is dropped, then the blob wins); file→dir is the mirror
331 * (the rebuilt subtree replaces the removed blob).
332 *
333 * **No blob is ever created** — every blob/gitlink oid referenced by an
334 * add/modify must already exist in the store (it came in with the head
335 * push). Gitlink oids are commit oids and are exempt from the existence
336 * assertion; any missing *blob* fails with {@link StoreError} (connectivity
337 * invariant).
338 */
339 export const applyTreeChanges = (
340 objects: TreeDiffObjects,
341 baseTree: Oid,
342 changes: ReadonlyArray<DiffEntryData>,
343 ): Effect.Effect<ApplyTreeChangesResult, StoreError> =>
344 Effect.gen(function* () {
345 // Connectivity invariant: referenced blobs must already exist.
346 const requiredBlobs = new Set<Oid>();
347 for (const change of changes) {
348 if (
349 change.newOid !== undefined &&
350 change.newMode !== undefined &&
351 treeEntryKind(change.newMode) !== "commit"
352 ) {
353 requiredBlobs.add(change.newOid);
354 }
355 }
356 if (requiredBlobs.size > 0) {
357 const metas = yield* objects.getMetaBatch(Array.from(requiredBlobs));
358 for (const oid of requiredBlobs) {
359 if (!metas.has(oid)) {
360 return yield* StoreError.make({
361 reason: `applyTreeChanges: referenced blob ${oid} is missing from the store`,
362 });
363 }
364 }
365 }
366
367 // Build the nested change tree keyed by path segment.
368 const rootNode: ChangeNode = { children: new Map() };
369 for (const change of changes) {
370 const segments = change.path.split("/");
371 let node = rootNode;
372 for (let i = 0; i < segments.length; i++) {
373 node.children ??= new Map();
374 const name = segments[i]!;
375 let next = node.children.get(name);
376 if (next === undefined) {
377 next = {};
378 node.children.set(name, next);
379 }
380 node = next;
381 }
382 node.leaf = change;
383 }
384
385 const newTrees: Array<NewTreeObject> = [];
386
387 const readEntries = Effect.fn(function* (oid: Oid) {
388 const content = yield* objects.readContent(oid);
389 return yield* parseTree(content).pipe(
390 Effect.mapError((e) => StoreError.make({ reason: e.reason })),
391 );
392 });
393
394 /**
395 * Rebuilds one directory: `baseOid` is the base-side subtree (absent
396 * when the directory is new), `node.children` the changes below it.
397 * Returns the resulting tree oid, or `undefined` when it came out
398 * empty.
399 */
400 const build = (
401 baseOid: Oid | undefined,
402 children: Map<string, ChangeNode>,
403 ): Effect.Effect<Oid | undefined, StoreError> =>
404 Effect.gen(function* () {
405 const baseEntries = baseOid === undefined ? [] : yield* readEntries(baseOid);
406 const byName = new Map(baseEntries.map((e) => [e.name, e]));
407 for (const [name, node] of children) {
408 const base = byName.get(name);
409 // 1. children first: rebuild the subtree below this name.
410 let subtree: Oid | undefined;
411 if (node.children !== undefined) {
412 const subtreeBase =
413 base !== undefined && treeEntryKind(base.mode) === "tree" ? base.oid : undefined;
414 subtree = yield* build(subtreeBase, node.children);
415 }
416 // 2. the leaf op at this exact name decides the entry.
417 if (
418 node.leaf !== undefined &&
419 node.leaf.newOid !== undefined &&
420 node.leaf.newMode !== undefined
421 ) {
422 // added/modified blob or gitlink — the leaf wins.
423 byName.set(name, {
424 mode: node.leaf.newMode,
425 name,
426 oid: node.leaf.newOid,
427 });
428 } else if (node.children !== undefined) {
429 // subtree result (also covers file→dir: the removed blob is
430 // replaced by the rebuilt subtree, or dropped when empty).
431 if (subtree === undefined) byName.delete(name);
432 else byName.set(name, { mode: TREE_MODE, name, oid: subtree });
433 } else if (node.leaf !== undefined) {
434 // removed leaf
435 byName.delete(name);
436 }
437 }
438 const entries = Array.from(byName.values());
439 if (entries.length === 0) return undefined;
440 const content = yield* encodeTree(entries).pipe(
441 Effect.mapError((e) => StoreError.make({ reason: e.reason })),
442 );
443 const oid = yield* hashObject(ObjectType.tree, content);
444 if (oid !== baseOid) {
445 newTrees.push({ oid, content });
446 }
447 return oid;
448 });
449
450 const root = yield* build(baseTree, rootNode.children ?? new Map());
451 if (root === undefined) {
452 // Everything was deleted: the canonical empty tree.
453 const content = new Uint8Array(0);
454 const oid = yield* hashObject(ObjectType.tree, content);
455 newTrees.push({ oid, content });
456 return { root: oid, newTrees };
457 }
458 return { root, newTrees };
459 });