Something went wrong. Try again.
A Tangled knot on CF Workers, backed by CF Artifacts
Something went wrong. Try again.
21 kB · 606 lines
TypeScript
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607import { boundedJsonResponse } from './wire';import { comparisonRevision } from './git-diff-revision';import { comparisonCommits, nativeHiddenFrontier, nativeMergeBase, CommitPriority,} from './git-merge-base';import { Buffer } from 'node:buffer';import { histogramHunks } from './git-histogram';import { deflateSync } from 'node:zlib';import type { ArtifactStore } from './artifacts';import { GitTransport } from './git-transport';import type { GitObject } from './git-objects';import { historyCommit } from './git-history';import { fail, publicRef, type RepoRecord } from './types';const ZERO = '0'.repeat(40);type Entry = { oid: string; mode: string };type Fragment = { Comment: string; OldPosition: number; OldLines: number; NewPosition: number; NewLines: number; LinesAdded: number; LinesDeleted: number; LeadingContext: number; TrailingContext: number; Lines: { Op: number; Line: string }[];};export interface FilePatch { path: string; old?: Entry; next?: Entry; binary: boolean; oldSize: number; newSize: number; fragments: Fragment[]; binaryText?: string;}function object( objects: Map<string, GitObject>, oid: string, type?: GitObject['type'],) { const value = objects.get(oid); if (!value || (type && value.type !== type)) fail(502, 'InvalidObject', 'missing or invalid Git graph object'); return value;}function flattened(objects: Map<string, GitObject>, tree: string) { const result = new Map<string, Entry>(), active = new Set<string>(); function walk(oid: string, prefix: string, depth: number) { if (depth > 64 || active.has(oid)) fail(413, 'OperationTooLarge', 'tree depth exceeds limit'); active.add(oid); const data = Buffer.from(object(objects, oid, 'tree').data); let position = 0; while (position < data.length) { const space = data.indexOf(32, position), nul = data.indexOf(0, space); if (space < position || nul < space || nul + 21 > data.length) fail(502, 'InvalidTree', 'malformed tree'); const mode = data.subarray(position, space).toString(), name = data.subarray(space + 1, nul).toString(); if (!name || name.includes('/') || name === '.' || name === '..') fail(502, 'InvalidTree', 'unsafe tree name'); const hash = data.subarray(nul + 1, nul + 21).toString('hex'), path = prefix + name; position = nul + 21; if (mode === '40000') walk(hash, path + '/', depth + 1); else { if ( !['100644', '100664', '100755', '120000', '160000'].includes(mode) || result.has(path) ) fail(502, 'InvalidTree', 'invalid tree mode or duplicate'); result.set(path, { oid: hash, mode }); if (result.size > 2000) fail(413, 'OperationTooLarge', 'file inventory exceeds limit'); } } active.delete(oid); } walk(tree, '', 0); return result;}function content(objects: Map<string, GitObject>, entry?: Entry): Buffer { if (!entry) return Buffer.alloc(0); if (entry.mode === '160000') return Buffer.from(`Subproject commit ${entry.oid}\n`); return Buffer.from(object(objects, entry.oid, 'blob').data);}export interface BinaryBudget { remaining: number; omitted: boolean;}const BASE85 = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~';export function binaryLiteral(data: Uint8Array) { const compressed = deflateSync(data, { level: 1 }); let output = `literal ${data.length}\n`; for (let offset = 0; offset < compressed.length; offset += 52) { const chunk = compressed.subarray(offset, offset + 52); output += String.fromCharCode( chunk.length <= 26 ? 64 + chunk.length : 96 + chunk.length - 26, ); for (let start = 0; start < chunk.length; start += 4) { let number = 0; for (let index = 0; index < 4; index++) number = number * 256 + (chunk[start + index] ?? 0); let encoded = ''; for (let digit = 0; digit < 5; digit++) { encoded = BASE85[number % 85] + encoded; number = Math.floor(number / 85); } output += encoded; } output += '\n'; } return output + '\n';}export function binaryWireBound(oldSize: number, newSize: number) { const block = (size: number) => { const deflated = size + Math.ceil(size / 8) + Math.ceil(size / 64) + 11; return Math.ceil(deflated / 4) * 5 + Math.ceil(deflated / 52) * 2 + 30; }; return block(oldSize) + block(newSize) + 17;}export function treePatches( objects: Map<string, GitObject>, base: string | undefined, head: string, budget?: BinaryBudget,): FilePatch[] { const old = base ? flattened(objects, historyCommit(object(objects, base, 'commit')).tree) : new Map<string, Entry>(); const next = flattened( objects, historyCommit(object(objects, head, 'commit')).tree, ), paths = [...new Set([...old.keys(), ...next.keys()])].sort((a, b) => Buffer.compare(Buffer.from(a), Buffer.from(b)), ); const patches: FilePatch[] = []; let textBudget = 0; for (const path of paths) { const before = old.get(path), after = next.get(path); if (before?.oid === after?.oid && before?.mode === after?.mode) continue; const a = content(objects, before), b = content(objects, after); textBudget += a.length + b.length; if (textBudget > 16 * 1024 * 1024) fail(413, 'OperationTooLarge', 'diff content exceeds limit'); const binary = a.subarray(0, 8000).includes(0) || b.subarray(0, 8000).includes(0); const fragments: Fragment[] = []; if (!binary && before?.oid !== after?.oid) { const diff = histogramHunks(a, b); for (const hunk of diff) { const lines = hunk.lines; const leading = lines.findIndex((line) => line.Op !== 0); let trailing = 0; for (let i = lines.length - 1; i >= 0 && lines[i].Op === 0; i--) trailing++; fragments.push({ Comment: '', OldPosition: hunk.oldStart, OldLines: hunk.oldLines, NewPosition: hunk.newStart, NewLines: hunk.newLines, LinesAdded: lines.filter((line) => line.Op === 2).length, LinesDeleted: lines.filter((line) => line.Op === 1).length, LeadingContext: leading < 0 ? lines.length : leading, TrailingContext: leading < 0 ? 0 : trailing, Lines: lines, }); } } let binaryText: string | undefined; if (binary && before?.oid !== after?.oid && budget) { const bound = binaryWireBound(a.length, b.length); if (bound <= budget.remaining) { binaryText = 'GIT binary patch\n' + binaryLiteral(b) + binaryLiteral(a); budget.remaining -= bound; } else budget.omitted = true; } patches.push({ path, old: before, next: after, binary, oldSize: a.length, newSize: b.length, fragments, binaryText, }); } return patches;}export function fileWire(patch: FilePatch) { return { OldName: patch.old ? patch.path : '', NewName: patch.next ? patch.path : '', IsNew: !patch.old, IsDelete: !patch.next, IsCopy: false, IsRename: false, OldMode: patch.old ? parseInt(patch.old.mode, 8) : 0, NewMode: patch.next && patch.old?.mode !== patch.next.mode ? parseInt(patch.next.mode, 8) : 0, OldOIDPrefix: patch.old?.oid ?? ZERO, NewOIDPrefix: patch.next?.oid ?? ZERO, Score: 0, TextFragments: patch.fragments.length ? patch.fragments : null, IsBinary: patch.binary, BinaryFragment: null, ReverseBinaryFragment: null, };}export function quotePath(path: string): string { const data = Buffer.from(path); if ( ![...data].some( (byte) => byte < 32 || byte === 34 || byte === 92 || byte >= 127, ) ) return path; return ( '"' + [...data] .map((byte) => byte === 34 ? '\\"' : byte === 92 ? '\\\\' : byte === 9 ? '\\t' : byte === 10 ? '\\n' : byte === 13 ? '\\r' : byte < 32 || byte >= 127 ? '\\' + byte.toString(8).padStart(3, '0') : String.fromCharCode(byte), ) .join('') + '"' );}export function renderPatches(patches: FilePatch[]) { let output = ''; const span = (start: number, count: number) => count === 1 ? String(start) : `${start},${count}`; for (const patch of patches) { const a = quotePath('a/' + patch.path), b = quotePath('b/' + patch.path), index = `index ${patch.old?.oid ?? ZERO}..${patch.next?.oid ?? ZERO}`, mode = (entry?: Entry) => entry?.mode.padStart(6, '0') ?? ''; output += `diff --git ${a} ${b}\n`; if (!patch.old) output += `new file mode ${mode(patch.next)}\n${index}\n`; else if (!patch.next) output += `deleted file mode ${mode(patch.old)}\n${index}\n`; else if (patch.old.mode === patch.next.mode) output += `${index} ${mode(patch.old)}\n`; else { output += `old mode ${mode(patch.old)}\nnew mode ${mode(patch.next)}\n`; if (patch.old.oid !== patch.next.oid) output += index + '\n'; } const oldLabel = patch.old ? a : '/dev/null', newLabel = patch.next ? b : '/dev/null'; if (patch.binary) { if (patch.binaryText) output += patch.binaryText; else if (patch.old?.oid !== patch.next?.oid) output += `Binary files ${oldLabel} and ${newLabel} differ\n`; continue; } if (!patch.fragments.length) continue; output += `--- ${oldLabel}\n+++ ${newLabel}\n`; for (const hunk of patch.fragments) { output += `@@ -${span(hunk.OldPosition, hunk.OldLines)} +${span(hunk.NewPosition, hunk.NewLines)} @@\n`; for (const line of hunk.Lines) { output += (line.Op === 2 ? '+' : line.Op === 1 ? '-' : ' ') + line.Line; if (!line.Line.endsWith('\n')) output += '\n\\ No newline at end of file\n'; } } } return output;}function counts(patches: FilePatch[]) { return { insertions: patches.reduce( (total, patch) => total + patch.fragments.reduce((n, h) => n + h.LinesAdded, 0), 0, ), deletions: patches.reduce( (total, patch) => total + patch.fragments.reduce((n, h) => n + h.LinesDeleted, 0), 0, ), files_changed: patches.length, };}function diffstat(patches: FilePatch[]) { const width = Math.max(0, ...patches.map((p) => quotePath(p.path).length)); let output = ''; for (const patch of patches) { const stat = counts([patch]), total = stat.insertions + stat.deletions, graph = total > 60 ? '+'.repeat(Math.floor((stat.insertions * 60) / total)) + '-'.repeat(Math.floor((stat.deletions * 60) / total)) : '+'.repeat(stat.insertions) + '-'.repeat(stat.deletions); output += ` ${quotePath(patch.path).padEnd(width)} | ${patch.binary ? (patch.old?.oid === patch.next?.oid ? 'Bin' : `Bin ${patch.oldSize} -> ${patch.newSize} bytes`) : `${total} ${graph}`}\n`; } const stat = counts(patches); output += ` ${patches.length} file${patches.length === 1 ? '' : 's'} changed`; if (stat.insertions) output += `, ${stat.insertions} insertion${stat.insertions === 1 ? '' : 's'}(+)`; if (stat.deletions) output += `, ${stat.deletions} deletion${stat.deletions === 1 ? '' : 's'}(-)`; output += '\n'; for (const patch of patches) { if (!patch.old) output += ` create mode ${patch.next!.mode.padStart(6, '0')} ${quotePath(patch.path)}\n`; else if (!patch.next) output += ` delete mode ${patch.old.mode.padStart(6, '0')} ${quotePath(patch.path)}\n`; else if (patch.old.mode !== patch.next.mode) output += ` mode change ${patch.old.mode.padStart(6, '0')} => ${patch.next.mode.padStart(6, '0')} ${quotePath(patch.path)}\n`; } return output;}function normalize(message: string) { return message .split('\n') .map((line) => line.trimEnd()) .join('\n') .trim() .replace(/\n{3,}/g, '\n\n');}export function formatPatch( objects: Map<string, GitObject>, oid: string, patches: FilePatch[],) { const commit = historyCommit(object(objects, oid, 'commit')), split = commit.message.indexOf('\n\n'), title = (split < 0 ? commit.message : commit.message.slice(0, split)) .split('\n') .filter(Boolean) .map((line) => line.trimEnd()) .join(' '), body = split < 0 ? '' : commit.message.slice(split + 2).replace(/^\n+|\n+$/g, ''); const when = commit.author.When, local = when.slice(0, 19), date = new Date(local + 'Z'), offset = when.endsWith('Z') ? '+0000' : when.slice(-6).replace(':', ''), rfcdate = `${['Sun', 'Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat'][date.getUTCDay()]}, ${date.getUTCDate()} ${['Jan', 'Feb', 'Mar', 'Apr', 'May', 'Jun', 'Jul', 'Aug', 'Sep', 'Oct', 'Nov', 'Dec'][date.getUTCMonth()]} ${date.getUTCFullYear()} ${local.slice(11)} ${offset}`; const headers: Record<string, string[]> = { From: [`${commit.author.Name} <${commit.author.Email}>`], Date: [rfcdate], Subject: ['[PATCH] ' + title], }; if (commit.change_id) headers['Change-Id'] = [commit.change_id]; const appendix = diffstat(patches); const raw = `From ${oid} Mon Sep 17 00:00:00 2001\n` + Object.entries(headers) .map(([key, values]) => `${key}: ${values[0]}\n`) .join('') + '\n' + (body ? body + '\n' : '') + '---\n' + appendix + '\n' + renderPatches(patches) + '-- \nknot\n\n'; return { wire: { Files: patches.length ? patches.map(fileWire) : null, SHA: oid, Author: { Name: commit.author.Name, Email: commit.author.Email }, AuthorDate: when, Committer: null, CommitterDate: '0001-01-01T00:00:00Z', Title: title, Body: normalize(body), SubjectPrefix: '[PATCH] ', BodyAppendix: normalize(appendix), RawHeaders: headers, Raw: raw.trim(), }, raw, };}export function comparisonGraph( objects: Map<string, GitObject>, base: string, head: string,) { const graph = comparisonCommits(objects, [base, head]), mergeBase = nativeMergeBase(graph, base, head), hidden = nativeHiddenFrontier(graph, head, base), ordered: string[] = [], seen = new Set<string>(), queue = new CommitPriority(); if (!hidden.has(head)) { seen.add(head); queue.push(head, graph.get(head)!.time); } while (queue.length) { const next = queue.pop(); ordered.push(next); for (const parent of graph.get(next)!.parents) if (!hidden.has(parent) && !seen.has(parent)) { seen.add(parent); queue.push(parent, graph.get(parent)!.time); } } if (ordered.length > 500) fail( 400, 'CompareError', 'comparison spans more than maximum of 500 commits', ); return { mergeBase, commits: ordered .reverse() .filter((oid) => graph.get(oid)!.parents.length <= 1), };}export async function diffSnapshot( store: ArtifactStore, repo: RepoRecord, revisions: string[],) { const transport = new GitTransport(store, repo.artifact), advertisement = await transport.advertisement(), objects = new Map<string, GitObject>(), resolved: string[] = []; let bytes = 0; const refs = Object.keys(advertisement.refs).filter( (name) => name === 'HEAD' || publicRef(name), ); if (refs.length > 2000) fail(413, 'OperationTooLarge', 'ref inventory exceeds limit'); for (let start = 0; start < refs.length; start += 64) { const names = refs.slice(start, start + 64), graph = await transport.fetchRefs(names); for (const name of names) if (graph.refs[name] !== advertisement.refs[name]) fail(409, 'RepositoryChanged', 'repository changed during diff'); for (const [oid, value] of graph.objects) if (!objects.has(oid)) { bytes += value.data.length; if (bytes > 16 * 1024 * 1024 || objects.size >= 2000) fail(413, 'OperationTooLarge', 'repository snapshot exceeds limit'); objects.set(oid, value); } } const publicObjects = new Set(objects.keys()), hidden = new Set<string>(); for (const revision of revisions) { const name = revision.startsWith('refs/') ? revision : 'refs/' + revision; if (name.startsWith('refs/hidden/') && advertisement.refs[name]) hidden.add(name); } for (const name of hidden) { const graph = await transport.fetchRefs([name]); if (graph.refs[name] !== advertisement.refs[name]) fail(409, 'RepositoryChanged', 'repository changed during diff'); for (const [oid, value] of graph.objects) if (!objects.has(oid)) { bytes += value.data.length; if (bytes > 16 * 1024 * 1024 || objects.size >= 2000) fail(413, 'OperationTooLarge', 'repository snapshot exceeds limit'); objects.set(oid, value); } } const visibleRefs = Object.fromEntries( [...refs, ...hidden].map((name) => [name, advertisement.refs[name]]), ); for (const revision of revisions) { const metadataRevision = revision.startsWith(':/') || revision.includes('^{/') || revision.includes('^{tag}'); const oid = metadataRevision ? (await store.log(repo.artifact, revision, 1))[0]?.hash : comparisonRevision(objects, visibleRefs, revision), name = revision.startsWith('refs/') ? revision : 'refs/' + revision; if (!oid) fail(400, 'RevisionNotFound', `error resolving revision ${revision}`); if (!publicObjects.has(oid) && !hidden.has(name)) fail(400, 'RevisionNotFound', `error resolving revision ${revision}`); resolved.push(oid); } return { objects, resolved };}const boundedJson = (value: unknown) => boundedJsonResponse(value, 'diff');export async function gitDiff( method: string, repo: RepoRecord, store: ArtifactStore, url: URL,): Promise<Response> { const comparing = method === 'sh.tangled.repo.compare'; for (const name of comparing ? ['rev1', 'rev2'] : ['ref']) { if (url.searchParams.getAll(name).length > 1) fail(400, 'InvalidRequest', `duplicate ${name} parameter`); const value = url.searchParams.get(name) ?? ''; if (Buffer.byteLength(value) > 4096 || /\p{Cc}/u.test(value)) fail(400, 'InvalidRequest', 'invalid revision'); } const first = comparing ? (url.searchParams.get('rev1') ?? '') : url.searchParams.get('ref') || 'HEAD', second = url.searchParams.get('rev2') ?? ''; if (comparing && !first) fail(400, 'InvalidRequest', 'missing rev1 parameter'); if (comparing && !second) fail(400, 'InvalidRequest', 'missing rev2 parameter'); const { objects, resolved } = await diffSnapshot( store, repo, comparing ? [first, second] : [first], ); if (!comparing) { const commit = historyCommit(object(objects, resolved[0], 'commit')), patches = treePatches(objects, commit.parent, resolved[0]), diffs = patches.map((patch) => ({ name: { old: patch.old ? patch.path : '', new: patch.next ? patch.path : '', }, text_fragments: patch.fragments.length ? patch.fragments : null, is_binary: patch.binary, is_new: !patch.old, is_delete: !patch.next, is_copy: false, is_rename: false, })); return boundedJson({ ...(url.searchParams.get('ref') ? { ref: first } : {}), diff: { commit, stat: counts(patches), diff: diffs.length ? diffs : null, }, }); } const [base, head] = resolved, graph = comparisonGraph(objects, base, head), seriesBudget: BinaryBudget = { remaining: Math.floor((5 * 1024 * 1024) / 12), omitted: false, }, combinedBudget: BinaryBudget = { ...seriesBudget }, entries = graph.commits.map((oid) => { const commit = historyCommit(object(objects, oid, 'commit')), patches = treePatches(objects, commit.parent, oid, seriesBudget); return { ...formatPatch(objects, oid, patches), binary: patches.some( (patch) => patch.binary && patch.old?.oid !== patch.next?.oid, ), }; }); const combined = graph.commits.length >= 2 && graph.mergeBase ? treePatches(objects, graph.mergeBase, head, combinedBudget) : undefined; const result = { rev1: base, rev2: head, ...(graph.mergeBase ? { merge_base: graph.mergeBase } : {}), ...(entries.length ? { format_patch: entries.map((entry) => entry.wire), patch: entries.map((entry) => entry.raw + '\n').join(''), } : {}), ...(combined ? { combined_patch: combined.map(fileWire), combined_patch_raw: renderPatches(combined), } : {}), ...(seriesBudget.omitted || combinedBudget.omitted ? { binary_omitted: true } : {}), }; return boundedJson(result);}