| 1 | import { diffArrays, structuredPatch } from "diff"; |
| 2 | import { fromUtf8 } from "./bytes.js"; |
| 3 | import { isTreeMode, serializeTree, type TreeEntry } from "./objects.js"; |
| 4 | import { mustRead, readTree, type ObjectReader, type ObjectStore } from "./store.js"; |
| 5 | |
| 6 | export type ChangeStatus = "added" | "modified" | "deleted"; |
| 7 | |
| 8 | export interface TreeChange { |
| 9 | path: string; |
| 10 | status: ChangeStatus; |
| 11 | oldOid?: string; |
| 12 | newOid?: string; |
| 13 | oldMode?: string; |
| 14 | newMode?: string; |
| 15 | } |
| 16 | |
| 17 | /** Recursive diff between two trees (either may be null for an empty tree). */ |
| 18 | export async function diffTrees(store: ObjectReader, oldTree: string | null, newTree: string | null, prefix = ""): Promise<TreeChange[]> { |
| 19 | if (oldTree === newTree) return []; |
| 20 | const a = new Map((oldTree ? await readTree(store, oldTree) : []).map((e) => [e.name, e])); |
| 21 | const b = new Map((newTree ? await readTree(store, newTree) : []).map((e) => [e.name, e])); |
| 22 | const names = [...new Set([...a.keys(), ...b.keys()])].sort(); |
| 23 | const out: TreeChange[] = []; |
| 24 | for (const name of names) { |
| 25 | const ea = a.get(name); |
| 26 | const eb = b.get(name); |
| 27 | const path = prefix ? `${prefix}/${name}` : name; |
| 28 | if (ea && eb && ea.oid === eb.oid && ea.mode === eb.mode) continue; |
| 29 | const aDir = ea && isTreeMode(ea.mode); |
| 30 | const bDir = eb && isTreeMode(eb.mode); |
| 31 | if (aDir || bDir) { |
| 32 | out.push(...(await diffTrees(store, aDir ? ea!.oid : null, bDir ? eb!.oid : null, path))); |
| 33 | if (ea && !aDir) out.push({ path, status: "deleted", oldOid: ea.oid, oldMode: ea.mode }); |
| 34 | if (eb && !bDir) out.push({ path, status: "added", newOid: eb.oid, newMode: eb.mode }); |
| 35 | continue; |
| 36 | } |
| 37 | if (!ea) out.push({ path, status: "added", newOid: eb!.oid, newMode: eb!.mode }); |
| 38 | else if (!eb) out.push({ path, status: "deleted", oldOid: ea.oid, oldMode: ea.mode }); |
| 39 | else out.push({ path, status: "modified", oldOid: ea.oid, newOid: eb.oid, oldMode: ea.mode, newMode: eb.mode }); |
| 40 | } |
| 41 | return out.sort((x, y) => (x.path < y.path ? -1 : x.path > y.path ? 1 : 0)); |
| 42 | } |
| 43 | |
| 44 | export function isBinary(content: Uint8Array): boolean { |
| 45 | const n = Math.min(content.length, 8000); |
| 46 | for (let i = 0; i < n; i++) if (content[i] === 0) return true; |
| 47 | return false; |
| 48 | } |
| 49 | |
| 50 | export interface Hunk { |
| 51 | oldStart: number; |
| 52 | oldLines: number; |
| 53 | newStart: number; |
| 54 | newLines: number; |
| 55 | lines: string[]; // prefixed with ' ', '+', '-' |
| 56 | } |
| 57 | |
| 58 | export interface FileDiff extends TreeChange { |
| 59 | binary: boolean; |
| 60 | additions: number; |
| 61 | deletions: number; |
| 62 | hunks: Hunk[]; |
| 63 | /** Set when the diff was too large to render. */ |
| 64 | truncated?: boolean; |
| 65 | } |
| 66 | |
| 67 | const MAX_DIFF_BYTES = 1024 * 1024; |
| 68 | |
| 69 | /** |
| 70 | * Myers' diff costs about the square of the number of changed lines, so a file pair with nothing in |
| 71 | * common could hold a repository's Durable Object for minutes. Past this many changed lines the |
| 72 | * change is shown as one replaced block instead, which costs one pass over the lines. |
| 73 | */ |
| 74 | export const MAX_EDIT_LENGTH = 1000; |
| 75 | |
| 76 | /** Work left for one diff request (a commit, a comparison or a pull request), shared by its files. */ |
| 77 | export class DiffBudget { |
| 78 | constructor( |
| 79 | /** Bytes of file content still to diff; later files are listed as too large. */ |
| 80 | public bytes = 16 * 1024 * 1024, |
| 81 | /** Myers' work left, in squared changed lines. */ |
| 82 | public work = 4 * MAX_EDIT_LENGTH * MAX_EDIT_LENGTH, |
| 83 | ) {} |
| 84 | } |
| 85 | |
| 86 | export async function fileDiff(store: ObjectReader, change: TreeChange, context = 3, budget = new DiffBudget()): Promise<FileDiff> { |
| 87 | const oldC = change.oldOid ? (await mustRead(store, change.oldOid)).content : new Uint8Array(0); |
| 88 | const newC = change.newOid ? (await mustRead(store, change.newOid)).content : new Uint8Array(0); |
| 89 | if (isBinary(oldC) || isBinary(newC)) return { ...change, binary: true, additions: 0, deletions: 0, hunks: [] }; |
| 90 | const size = oldC.length + newC.length; |
| 91 | if (size > MAX_DIFF_BYTES || size > budget.bytes) return { ...change, binary: false, additions: 0, deletions: 0, hunks: [], truncated: true }; |
| 92 | budget.bytes -= size; |
| 93 | const oldS = fromUtf8(oldC); |
| 94 | const newS = fromUtf8(newC); |
| 95 | const maxEditLength = Math.min(MAX_EDIT_LENGTH, Math.floor(Math.sqrt(Math.max(0, budget.work)))); |
| 96 | const patch = structuredPatch(change.path, change.path, oldS, newS, "", "", { context, maxEditLength }); |
| 97 | const hunks: Hunk[] = patch ? patch.hunks.map((h) => ({ oldStart: h.oldStart, oldLines: h.oldLines, newStart: h.newStart, newLines: h.newLines, lines: h.lines })) : replacedBlock(oldS, newS, context); |
| 98 | let additions = 0; |
| 99 | let deletions = 0; |
| 100 | for (const h of hunks) { |
| 101 | for (const l of h.lines) { |
| 102 | if (l.startsWith("+")) additions++; |
| 103 | else if (l.startsWith("-")) deletions++; |
| 104 | } |
| 105 | } |
| 106 | budget.work -= patch ? (additions + deletions) ** 2 : maxEditLength ** 2; |
| 107 | return { ...change, binary: false, additions, deletions, hunks }; |
| 108 | } |
| 109 | |
| 110 | /** |
| 111 | * The cheap diff for a change too large for Myers: the lines the two sides share at the start and the |
| 112 | * end stay as context, and everything between is removed and added as one block. |
| 113 | */ |
| 114 | function replacedBlock(oldS: string, newS: string, context: number): Hunk[] { |
| 115 | const a = splitLines(oldS); |
| 116 | const b = splitLines(newS); |
| 117 | let p = 0; |
| 118 | while (p < a.length && p < b.length && a[p] === b[p]) p++; |
| 119 | let s = 0; |
| 120 | while (s < a.length - p && s < b.length - p && a[a.length - 1 - s] === b[b.length - 1 - s]) s++; |
| 121 | if (p === a.length && p === b.length) return []; |
| 122 | const from = Math.max(0, p - context); |
| 123 | const after = Math.min(s, context); |
| 124 | const lines: string[] = []; |
| 125 | const push = (mark: string, line: string) => { |
| 126 | lines.push(mark + (line.endsWith("\n") ? line.slice(0, -1) : line)); |
| 127 | if (!line.endsWith("\n")) lines.push("\\ No newline at end of file"); |
| 128 | }; |
| 129 | for (let i = from; i < p; i++) push(" ", a[i]!); |
| 130 | for (let i = p; i < a.length - s; i++) push("-", a[i]!); |
| 131 | for (let i = p; i < b.length - s; i++) push("+", b[i]!); |
| 132 | for (let i = a.length - s; i < a.length - s + after; i++) push(" ", a[i]!); |
| 133 | return [{ oldStart: from + 1, oldLines: a.length - s + after - from, newStart: from + 1, newLines: b.length - s + after - from, lines }]; |
| 134 | } |
| 135 | |
| 136 | export function formatUnified(d: FileDiff): string { |
| 137 | const a = d.status === "added" ? "/dev/null" : `a/${d.path}`; |
| 138 | const b = d.status === "deleted" ? "/dev/null" : `b/${d.path}`; |
| 139 | const head = `diff --git a/${d.path} b/${d.path}\n--- ${a}\n+++ ${b}\n`; |
| 140 | if (d.binary) return `${head}Binary files differ\n`; |
| 141 | return head + d.hunks.map((h) => `@@ -${h.oldStart},${h.oldLines} +${h.newStart},${h.newLines} @@\n${h.lines.join("\n")}\n`).join(""); |
| 142 | } |
| 143 | |
| 144 | // ---------------------------------------------------------------- three-way merge |
| 145 | |
| 146 | interface Edit { |
| 147 | start: number; // base line index |
| 148 | end: number; // exclusive |
| 149 | lines: string[]; |
| 150 | } |
| 151 | |
| 152 | function edits(base: string[], other: string[]): Edit[] | null { |
| 153 | const parts = diffArrays(base, other, { maxEditLength: 2 * MAX_EDIT_LENGTH }); |
| 154 | if (!parts) return null; |
| 155 | const out: Edit[] = []; |
| 156 | let bi = 0; |
| 157 | let cur: Edit | null = null; |
| 158 | for (const part of parts) { |
| 159 | if (part.removed) { |
| 160 | cur ??= { start: bi, end: bi, lines: [] }; |
| 161 | cur.end += part.count ?? part.value.length; |
| 162 | bi += part.count ?? part.value.length; |
| 163 | } else if (part.added) { |
| 164 | cur ??= { start: bi, end: bi, lines: [] }; |
| 165 | cur.lines.push(...part.value); |
| 166 | } else { |
| 167 | if (cur) out.push(cur); |
| 168 | cur = null; |
| 169 | bi += part.count ?? part.value.length; |
| 170 | } |
| 171 | } |
| 172 | if (cur) out.push(cur); |
| 173 | return out; |
| 174 | } |
| 175 | |
| 176 | const splitLines = (s: string): string[] => (s === "" ? [] : s.split(/(?<=\n)/)); |
| 177 | |
| 178 | /** Line-based diff3. Returns merged text, or null when the sides conflict. */ |
| 179 | export function mergeText(base: string, ours: string, theirs: string): string | null { |
| 180 | if (ours === theirs) return ours; |
| 181 | if (base === ours) return theirs; |
| 182 | if (base === theirs) return ours; |
| 183 | const b = splitLines(base); |
| 184 | const ea = edits(b, splitLines(ours)); |
| 185 | const eb = edits(b, splitLines(theirs)); |
| 186 | // A side too different from the base to diff cheaply is left for a person to merge. |
| 187 | if (!ea || !eb) return null; |
| 188 | const out: string[] = []; |
| 189 | let pos = 0; |
| 190 | let i = 0; |
| 191 | let j = 0; |
| 192 | while (i < ea.length || j < eb.length) { |
| 193 | const a = ea[i]; |
| 194 | const c = eb[j]; |
| 195 | let take: Edit; |
| 196 | if (a && c && a.start < c.end + (c.start === c.end ? 1 : 0) && c.start < a.end + (a.start === a.end ? 1 : 0)) { |
| 197 | // Overlapping edits: fine only when identical. |
| 198 | if (a.start === c.start && a.end === c.end && a.lines.join("") === c.lines.join("")) { |
| 199 | take = a; |
| 200 | i++; |
| 201 | j++; |
| 202 | } else return null; |
| 203 | } else if (a && (!c || a.start < c.start || (a.start === c.start && a.end <= c.end))) { |
| 204 | take = a; |
| 205 | i++; |
| 206 | } else { |
| 207 | take = c!; |
| 208 | j++; |
| 209 | } |
| 210 | out.push(...b.slice(pos, take.start), ...take.lines); |
| 211 | pos = take.end; |
| 212 | } |
| 213 | out.push(...b.slice(pos)); |
| 214 | return out.join(""); |
| 215 | } |
| 216 | |
| 217 | export interface MergeResult { |
| 218 | tree: string | null; |
| 219 | conflicts: string[]; |
| 220 | } |
| 221 | |
| 222 | /** Three-way merge of trees. File-level with line-level diff3 for text files. */ |
| 223 | export async function mergeTrees(store: ObjectStore, base: string | null, ours: string, theirs: string): Promise<MergeResult> { |
| 224 | const conflicts: string[] = []; |
| 225 | const mergeDir = async (b: string | null, o: string | null, t: string | null, prefix: string): Promise<string | null> => { |
| 226 | if (o === t) return o; |
| 227 | if (b === o) return t; |
| 228 | if (b === t) return o; |
| 229 | const mb = new Map((b ? await readTree(store, b) : []).map((e) => [e.name, e])); |
| 230 | const mo = new Map((o ? await readTree(store, o) : []).map((e) => [e.name, e])); |
| 231 | const mt = new Map((t ? await readTree(store, t) : []).map((e) => [e.name, e])); |
| 232 | const result: TreeEntry[] = []; |
| 233 | for (const name of new Set([...mb.keys(), ...mo.keys(), ...mt.keys()])) { |
| 234 | const eb = mb.get(name); |
| 235 | const eo = mo.get(name); |
| 236 | const et = mt.get(name); |
| 237 | const path = prefix ? `${prefix}/${name}` : name; |
| 238 | const same = (x?: TreeEntry, y?: TreeEntry) => (!x && !y) || (!!x && !!y && x.oid === y.oid && x.mode === y.mode); |
| 239 | if (same(eo, et)) { |
| 240 | if (eo) result.push(eo); |
| 241 | continue; |
| 242 | } |
| 243 | if (same(eb, eo)) { |
| 244 | if (et) result.push(et); |
| 245 | continue; |
| 246 | } |
| 247 | if (same(eb, et)) { |
| 248 | if (eo) result.push(eo); |
| 249 | continue; |
| 250 | } |
| 251 | const dir = (e?: TreeEntry) => (e && isTreeMode(e.mode) ? e.oid : null); |
| 252 | if ((!eo || isTreeMode(eo.mode)) && (!et || isTreeMode(et.mode)) && (!eb || isTreeMode(eb.mode))) { |
| 253 | const merged = await mergeDir(dir(eb), dir(eo), dir(et), path); |
| 254 | if (merged) result.push({ mode: "40000", name, oid: merged }); |
| 255 | continue; |
| 256 | } |
| 257 | if (eo && et && !isTreeMode(eo.mode) && !isTreeMode(et.mode) && eo.mode === et.mode) { |
| 258 | const [cb, co, ct] = await Promise.all([ |
| 259 | eb && !isTreeMode(eb.mode) ? mustRead(store, eb.oid) : null, |
| 260 | mustRead(store, eo.oid), |
| 261 | mustRead(store, et.oid), |
| 262 | ]); |
| 263 | if (!isBinary(co.content) && !isBinary(ct.content) && (!cb || !isBinary(cb.content))) { |
| 264 | const merged = mergeText(cb ? fromUtf8(cb.content) : "", fromUtf8(co.content), fromUtf8(ct.content)); |
| 265 | if (merged !== null) { |
| 266 | const oid = await store.write("blob", new TextEncoder().encode(merged)); |
| 267 | result.push({ mode: eo.mode, name, oid }); |
| 268 | continue; |
| 269 | } |
| 270 | } |
| 271 | } |
| 272 | conflicts.push(path); |
| 273 | if (eo) result.push(eo); |
| 274 | } |
| 275 | if (!result.length) return null; |
| 276 | return store.write("tree", serializeTree(result)); |
| 277 | }; |
| 278 | const tree = await mergeDir(base, ours, theirs, ""); |
| 279 | return { tree, conflicts }; |
| 280 | } |