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, 06:00 UTC
| 1 | /** |
| 2 | * The partial-pack scanner (packages/git/src/Protocol/PartialScan.ts): the hashing |
| 3 | * Worker's unit of work. Entries are settled inside a buffer that starts |
| 4 | * at an entry boundary; the tail is carried; deltas whose base lies in an |
| 5 | * earlier buffer are reported unresolved. |
| 6 | */ |
| 7 | import { |
| 8 | hashObject, |
| 9 | encodeTypeSize, |
| 10 | makeSha1, |
| 11 | type Oid, |
| 12 | } from "@alchemy.run/git/Protocol/ObjectCodec"; |
| 13 | import { packHeader } from "@alchemy.run/git/Protocol/PackWriter"; |
| 14 | import { |
| 15 | findBoundary, |
| 16 | hashBounds, |
| 17 | scanBounds, |
| 18 | scanPart, |
| 19 | } from "@alchemy.run/git/Protocol/PartialScan"; |
| 20 | import * as Zlib from "@alchemy.run/git/Protocol/Zlib"; |
| 21 | import { describe, expect, test } from "@alchemy.run/test"; |
| 22 | import * as BunServices from "@effect/platform-bun/BunServices"; |
| 23 | import * as Effect from "effect/Effect"; |
| 24 | import * as FileSystem from "effect/FileSystem"; |
| 25 | import * as Path from "effect/Path"; |
| 26 | import { concat } from "./harness/pack.ts"; |
| 27 | |
| 28 | const buildPack = (n: number) => |
| 29 | Effect.gen(function* () { |
| 30 | const pieces: Array<Uint8Array> = [packHeader(n)]; |
| 31 | const oids: Array<Oid> = []; |
| 32 | for (let i = 0; i < n; i++) { |
| 33 | const size = 100 + ((i * 977) % 4900); |
| 34 | const content = new Uint8Array(size); |
| 35 | crypto.getRandomValues(content); |
| 36 | content[0] = i & 0xff; |
| 37 | oids.push(yield* hashObject(3, content)); |
| 38 | pieces.push(encodeTypeSize(3, size), yield* Zlib.deflate(content)); |
| 39 | } |
| 40 | const body = concat(pieces); |
| 41 | const sha = makeSha1(); |
| 42 | sha.update(body); |
| 43 | return { pack: concat([body, sha.digest()]), oids, count: n }; |
| 44 | }); |
| 45 | |
| 46 | /** Drives the scanner the way the pipeline does: parts + carry. */ |
| 47 | const scanInParts = (pack: Uint8Array, count: number, partSizes: (i: number) => number) => |
| 48 | Effect.gen(function* () { |
| 49 | // Parts run to the END of the pack (trailer included) so the last entry |
| 50 | // is followed by bytes, per the scanner's contract. |
| 51 | const end = pack.length; |
| 52 | let consumedTo = 12; // after the pack header |
| 53 | let remaining = count; |
| 54 | let cursor = 12; |
| 55 | const all: Array<Oid> = []; |
| 56 | const unresolved: Array<{ offset: number }> = []; |
| 57 | let i = 0; |
| 58 | let carry: Uint8Array = new Uint8Array(0); |
| 59 | while (cursor < end) { |
| 60 | const n = Math.min(partSizes(i++), end - cursor); |
| 61 | const payload = concat([carry, pack.subarray(cursor, cursor + n)]); |
| 62 | const base = consumedTo; |
| 63 | const result = yield* scanPart(payload, { base, remaining, maxObjectSize: 64 << 20 }); |
| 64 | for (const e of result.entries) all.push(e.oid); |
| 65 | for (const u of result.unresolved) unresolved.push(u); |
| 66 | remaining -= result.count; |
| 67 | cursor += n; |
| 68 | carry = payload.subarray(result.consumedTo - base); |
| 69 | consumedTo = result.consumedTo; |
| 70 | } |
| 71 | expect(remaining).toBe(0); |
| 72 | expect(carry.length).toBe(20); // exactly the trailer is left over |
| 73 | return { all, unresolved }; |
| 74 | }); |
| 75 | |
| 76 | describe("scanPart", { tags: ["unit", "local"] }, () => { |
| 77 | test("a pack split at arbitrary points, with carry, yields every entry exactly once", async () => { |
| 78 | await Effect.runPromise( |
| 79 | Effect.gen(function* () { |
| 80 | const { pack, oids, count } = yield* buildPack(400); |
| 81 | for (const sizes of [() => 1000, (i: number) => 100 + ((i * 7919) % 5000), () => 1 << 20]) { |
| 82 | const { all, unresolved } = yield* scanInParts(pack, count, sizes); |
| 83 | expect(all.length).toBe(count); |
| 84 | expect(new Set(all)).toEqual(new Set(oids)); |
| 85 | expect(unresolved).toEqual([]); |
| 86 | } |
| 87 | }), |
| 88 | ); |
| 89 | }); |
| 90 | |
| 91 | test("the ofs-delta fixture: whole-buffer scan resolves every delta; small parts report cross-part bases unresolved", async () => { |
| 92 | await Effect.runPromise( |
| 93 | Effect.gen(function* () { |
| 94 | const fs = yield* FileSystem.FileSystem; |
| 95 | const path = yield* Path.Path; |
| 96 | const dir = path.join(import.meta.dirname, "fixtures", "packs"); |
| 97 | const pack = yield* fs.readFile(path.join(dir, "ofs-delta.pack")); |
| 98 | const manifest = JSON.parse(yield* fs.readFileString(path.join(dir, "manifest.json"))) as { |
| 99 | packs: Record<string, { oids: ReadonlyArray<string> }>; |
| 100 | }; |
| 101 | const expected = new Set(manifest.packs["ofs-delta"]!.oids); |
| 102 | const count = new DataView(pack.buffer, pack.byteOffset).getUint32(8); |
| 103 | const whole = yield* scanPart(pack.subarray(12), { |
| 104 | base: 12, |
| 105 | remaining: count, |
| 106 | maxObjectSize: 64 << 20, |
| 107 | }); |
| 108 | expect(whole.unresolved).toEqual([]); |
| 109 | expect(whole.count).toBe(count); |
| 110 | expect(new Set(whole.entries.map((e) => e.oid))).toEqual(expected); |
| 111 | expect(whole.entries.some((e) => e.zdata !== undefined)).toBe(true); // delta-resolved ones carry fresh zdata |
| 112 | // Tiny parts: bases fall into earlier buffers. |
| 113 | const { all, unresolved } = yield* scanInParts(pack, count, () => 64); |
| 114 | expect(unresolved.length).toBeGreaterThan(0); |
| 115 | expect(all.length + unresolved.length).toBe(count); |
| 116 | for (const oid of all) expect(expected.has(oid)).toBe(true); |
| 117 | }).pipe(Effect.provide(BunServices.layer)), |
| 118 | ); |
| 119 | }); |
| 120 | }); |
| 121 | |
| 122 | describe( |
| 123 | "an entry ending exactly at the buffer edge is not consumed", |
| 124 | { tags: ["unit", "local"] }, |
| 125 | () => { |
| 126 | test("the scanner carries it until bytes follow", async () => { |
| 127 | await Effect.runPromise( |
| 128 | Effect.gen(function* () { |
| 129 | const { pack, count } = yield* buildPack(3); |
| 130 | const first = yield* scanPart(pack.subarray(12), { |
| 131 | base: 12, |
| 132 | remaining: count, |
| 133 | maxObjectSize: 1 << 20, |
| 134 | }); |
| 135 | expect(first.count).toBe(3); |
| 136 | const cut = first.entries[1]!.dataOffset + first.entries[1]!.span; |
| 137 | const partial = yield* scanPart(pack.subarray(12, cut), { |
| 138 | base: 12, |
| 139 | remaining: count, |
| 140 | maxObjectSize: 1 << 20, |
| 141 | }); |
| 142 | expect(partial.count).toBe(1); |
| 143 | expect(partial.consumedTo).toBeLessThan(cut); |
| 144 | expect(partial.consumedTo).toBe(first.entries[0]!.dataOffset + first.entries[0]!.span); |
| 145 | }), |
| 146 | ); |
| 147 | }); |
| 148 | }, |
| 149 | ); |
| 150 | |
| 151 | describe("scanBounds + hashBounds (DESIGN §22.8)", { tags: ["unit", "local"] }, () => { |
| 152 | test("boundary scan then known-span hashing equals the single-pass scan on a synthetic pack", async () => { |
| 153 | await Effect.runPromise( |
| 154 | Effect.gen(function* () { |
| 155 | const { pack, oids, count } = yield* buildPack(300); |
| 156 | const buf = pack.subarray(12); |
| 157 | const bounds = yield* scanBounds(buf, { |
| 158 | base: 12, |
| 159 | remaining: count, |
| 160 | maxObjectSize: 64 << 20, |
| 161 | }); |
| 162 | expect(bounds.entries.length).toBe(count); |
| 163 | expect(bounds.consumedTo).toBe(pack.length - 20); |
| 164 | const hashed = yield* hashBounds(buf, bounds.entries, { |
| 165 | base: 12, |
| 166 | maxObjectSize: 64 << 20, |
| 167 | }); |
| 168 | expect(hashed.entries.map((e) => e.oid)).toEqual(oids); |
| 169 | expect(hashed.unresolved).toEqual([]); |
| 170 | const single = yield* scanPart(buf, { |
| 171 | base: 12, |
| 172 | remaining: count, |
| 173 | maxObjectSize: 64 << 20, |
| 174 | }); |
| 175 | expect(hashed.entries.map((e) => [e.oid, e.offset, e.dataOffset, e.span])).toEqual( |
| 176 | single.entries.map((e) => [e.oid, e.offset, e.dataOffset, e.span]), |
| 177 | ); |
| 178 | }), |
| 179 | ); |
| 180 | }); |
| 181 | |
| 182 | test("the ofs-delta fixture: bounds carry base offsets; hashing resolves every in-buffer delta", async () => { |
| 183 | await Effect.runPromise( |
| 184 | Effect.gen(function* () { |
| 185 | const fs = yield* FileSystem.FileSystem; |
| 186 | const path = yield* Path.Path; |
| 187 | const dir = path.join(import.meta.dirname, "fixtures", "packs"); |
| 188 | const pack = yield* fs.readFile(path.join(dir, "ofs-delta.pack")); |
| 189 | const manifest = JSON.parse(yield* fs.readFileString(path.join(dir, "manifest.json"))) as { |
| 190 | packs: Record<string, { oids: ReadonlyArray<string> }>; |
| 191 | }; |
| 192 | const expected = new Set(manifest.packs["ofs-delta"]!.oids); |
| 193 | const count = new DataView(pack.buffer, pack.byteOffset).getUint32(8); |
| 194 | const buf = pack.subarray(12); |
| 195 | const bounds = yield* scanBounds(buf, { |
| 196 | base: 12, |
| 197 | remaining: count, |
| 198 | maxObjectSize: 64 << 20, |
| 199 | }); |
| 200 | expect(bounds.entries.length).toBe(count); |
| 201 | expect(bounds.entries.some((b) => b.type === 6 && b.baseOffset !== undefined)).toBe(true); |
| 202 | const hashed = yield* hashBounds(buf, bounds.entries, { |
| 203 | base: 12, |
| 204 | maxObjectSize: 64 << 20, |
| 205 | }); |
| 206 | expect(hashed.unresolved).toEqual([]); |
| 207 | expect(new Set(hashed.entries.map((e) => e.oid))).toEqual(expected); |
| 208 | // Hashing only the second half: bases in the first half are unresolved. |
| 209 | const half = bounds.entries.slice(Math.floor(count / 2)); |
| 210 | const partial = yield* hashBounds(buf, half, { base: 12, maxObjectSize: 64 << 20 }); |
| 211 | expect(partial.entries.length + partial.unresolved.length).toBe(half.length); |
| 212 | }).pipe(Effect.provide(BunServices.layer)), |
| 213 | ); |
| 214 | }); |
| 215 | }); |
| 216 | |
| 217 | describe("findBoundary (DESIGN §22.9)", { tags: ["unit", "local"] }, () => { |
| 218 | test("a boundary past the first MiB is found: the search covers the whole chunk", async () => { |
| 219 | await Effect.runPromise( |
| 220 | Effect.gen(function* () { |
| 221 | // One 1.5 MiB blob followed by small ones: a chunk starting inside |
| 222 | // the big blob has its first boundary ~1.5 MiB in. |
| 223 | const big = new Uint8Array(1_500_000); |
| 224 | crypto.getRandomValues(big); |
| 225 | const pieces: Array<Uint8Array> = [ |
| 226 | packHeader(4), |
| 227 | encodeTypeSize(3, big.length), |
| 228 | yield* Zlib.deflate(big), |
| 229 | ]; |
| 230 | for (let i = 0; i < 3; i++) { |
| 231 | const c = new Uint8Array(500); |
| 232 | crypto.getRandomValues(c); |
| 233 | pieces.push(encodeTypeSize(3, c.length), yield* Zlib.deflate(c)); |
| 234 | } |
| 235 | const body = concat(pieces); |
| 236 | const sha = makeSha1(); |
| 237 | sha.update(body); |
| 238 | const pack = concat([body, sha.digest()]); |
| 239 | const bigEnd = 12 + pieces[1]!.length + pieces[2]!.length; |
| 240 | const chunk = pack.subarray(100); |
| 241 | expect(findBoundary(chunk, { maxObjectSize: 1 << 24 })).toBe(bigEnd - 100); |
| 242 | expect(findBoundary(chunk, { maxObjectSize: 1 << 24, maxSearch: 1 << 20 })).toBeUndefined(); |
| 243 | }), |
| 244 | ); |
| 245 | }); |
| 246 | test("from arbitrary offsets in a synthetic pack, the first boundary found is a true entry start", async () => { |
| 247 | await Effect.runPromise( |
| 248 | Effect.gen(function* () { |
| 249 | const { pack, count } = yield* buildPack(200); |
| 250 | const truth = yield* scanBounds(pack.subarray(12), { |
| 251 | base: 12, |
| 252 | remaining: count, |
| 253 | maxObjectSize: 1 << 20, |
| 254 | }); |
| 255 | const starts = new Set(truth.entries.map((b) => b.offset)); |
| 256 | let seed = 3; |
| 257 | for (let i = 0; i < 60; i++) { |
| 258 | seed = (seed * 1103515245 + 12345) & 0x7fffffff; |
| 259 | const at = 12 + (seed % (pack.length - 40_000)); |
| 260 | const chunk = pack.subarray(at, at + 30_000); |
| 261 | const found = findBoundary(chunk, { maxObjectSize: 1 << 20 }); |
| 262 | expect(found).toBeDefined(); |
| 263 | expect(starts.has(at + found!)).toBe(true); |
| 264 | // And it is the FIRST true boundary at or after `at`. |
| 265 | const first = truth.entries.find((b) => b.offset >= at && b.offset + 10 < at + 30_000)!; |
| 266 | expect(at + found!).toBe(first.offset); |
| 267 | } |
| 268 | }), |
| 269 | ); |
| 270 | }); |
| 271 | |
| 272 | test("the ofs-delta fixture: resync from every byte offset lands on a true boundary", async () => { |
| 273 | await Effect.runPromise( |
| 274 | Effect.gen(function* () { |
| 275 | const fs = yield* FileSystem.FileSystem; |
| 276 | const path = yield* Path.Path; |
| 277 | const dir = path.join(import.meta.dirname, "fixtures", "packs"); |
| 278 | const pack = yield* fs.readFile(path.join(dir, "ofs-delta.pack")); |
| 279 | const count = new DataView(pack.buffer, pack.byteOffset).getUint32(8); |
| 280 | const truth = yield* scanBounds(pack.subarray(12), { |
| 281 | base: 12, |
| 282 | remaining: count, |
| 283 | maxObjectSize: 1 << 20, |
| 284 | }); |
| 285 | const starts = truth.entries.map((b) => b.offset); |
| 286 | // Skip the last two entries: a boundary needs a following entry. |
| 287 | const lastTestable = starts[starts.length - 2]!; |
| 288 | for (let at = 12; at < lastTestable; at++) { |
| 289 | const found = findBoundary(pack.subarray(at), { maxObjectSize: 1 << 20 }); |
| 290 | expect(found, `from ${at}`).toBeDefined(); |
| 291 | expect(starts.includes(at + found!), `from ${at} → ${at + found!}`).toBe(true); |
| 292 | } |
| 293 | }).pipe(Effect.provide(BunServices.layer)), |
| 294 | ); |
| 295 | }); |
| 296 | }); |