| 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 | export async function fileDiff(store: ObjectReader, change: TreeChange, context = 3): Promise<FileDiff> { |
| 70 | const oldC = change.oldOid ? (await mustRead(store, change.oldOid)).content : new Uint8Array(0); |
| 71 | const newC = change.newOid ? (await mustRead(store, change.newOid)).content : new Uint8Array(0); |
| 72 | if (isBinary(oldC) || isBinary(newC)) return { ...change, binary: true, additions: 0, deletions: 0, hunks: [] }; |
| 73 | if (oldC.length + newC.length > MAX_DIFF_BYTES) return { ...change, binary: false, additions: 0, deletions: 0, hunks: [], truncated: true }; |
| 74 | const patch = structuredPatch(change.path, change.path, fromUtf8(oldC), fromUtf8(newC), "", "", { context }); |
| 75 | let additions = 0; |
| 76 | let deletions = 0; |
| 77 | const hunks = patch.hunks.map((h) => { |
| 78 | for (const l of h.lines) { |
| 79 | if (l.startsWith("+")) additions++; |
| 80 | else if (l.startsWith("-")) deletions++; |
| 81 | } |
| 82 | return { oldStart: h.oldStart, oldLines: h.oldLines, newStart: h.newStart, newLines: h.newLines, lines: h.lines }; |
| 83 | }); |
| 84 | return { ...change, binary: false, additions, deletions, hunks }; |
| 85 | } |
| 86 | |
| 87 | export function formatUnified(d: FileDiff): string { |
| 88 | const a = d.status === "added" ? "/dev/null" : `a/${d.path}`; |
| 89 | const b = d.status === "deleted" ? "/dev/null" : `b/${d.path}`; |
| 90 | const head = `diff --git a/${d.path} b/${d.path}\n--- ${a}\n+++ ${b}\n`; |
| 91 | if (d.binary) return `${head}Binary files differ\n`; |
| 92 | return head + d.hunks.map((h) => `@@ -${h.oldStart},${h.oldLines} +${h.newStart},${h.newLines} @@\n${h.lines.join("\n")}\n`).join(""); |
| 93 | } |
| 94 | |
| 95 | // ---------------------------------------------------------------- three-way merge |
| 96 | |
| 97 | interface Edit { |
| 98 | start: number; // base line index |
| 99 | end: number; // exclusive |
| 100 | lines: string[]; |
| 101 | } |
| 102 | |
| 103 | function edits(base: string[], other: string[]): Edit[] { |
| 104 | const out: Edit[] = []; |
| 105 | let bi = 0; |
| 106 | let cur: Edit | null = null; |
| 107 | for (const part of diffArrays(base, other)) { |
| 108 | if (part.removed) { |
| 109 | cur ??= { start: bi, end: bi, lines: [] }; |
| 110 | cur.end += part.count ?? part.value.length; |
| 111 | bi += part.count ?? part.value.length; |
| 112 | } else if (part.added) { |
| 113 | cur ??= { start: bi, end: bi, lines: [] }; |
| 114 | cur.lines.push(...part.value); |
| 115 | } else { |
| 116 | if (cur) out.push(cur); |
| 117 | cur = null; |
| 118 | bi += part.count ?? part.value.length; |
| 119 | } |
| 120 | } |
| 121 | if (cur) out.push(cur); |
| 122 | return out; |
| 123 | } |
| 124 | |
| 125 | const splitLines = (s: string): string[] => (s === "" ? [] : s.split(/(?<=\n)/)); |
| 126 | |
| 127 | /** Line-based diff3. Returns merged text, or null when the sides conflict. */ |
| 128 | export function mergeText(base: string, ours: string, theirs: string): string | null { |
| 129 | if (ours === theirs) return ours; |
| 130 | if (base === ours) return theirs; |
| 131 | if (base === theirs) return ours; |
| 132 | const b = splitLines(base); |
| 133 | const ea = edits(b, splitLines(ours)); |
| 134 | const eb = edits(b, splitLines(theirs)); |
| 135 | const out: string[] = []; |
| 136 | let pos = 0; |
| 137 | let i = 0; |
| 138 | let j = 0; |
| 139 | while (i < ea.length || j < eb.length) { |
| 140 | const a = ea[i]; |
| 141 | const c = eb[j]; |
| 142 | let take: Edit; |
| 143 | if (a && c && a.start < c.end + (c.start === c.end ? 1 : 0) && c.start < a.end + (a.start === a.end ? 1 : 0)) { |
| 144 | // Overlapping edits: fine only when identical. |
| 145 | if (a.start === c.start && a.end === c.end && a.lines.join("") === c.lines.join("")) { |
| 146 | take = a; |
| 147 | i++; |
| 148 | j++; |
| 149 | } else return null; |
| 150 | } else if (a && (!c || a.start < c.start || (a.start === c.start && a.end <= c.end))) { |
| 151 | take = a; |
| 152 | i++; |
| 153 | } else { |
| 154 | take = c!; |
| 155 | j++; |
| 156 | } |
| 157 | out.push(...b.slice(pos, take.start), ...take.lines); |
| 158 | pos = take.end; |
| 159 | } |
| 160 | out.push(...b.slice(pos)); |
| 161 | return out.join(""); |
| 162 | } |
| 163 | |
| 164 | export interface MergeResult { |
| 165 | tree: string | null; |
| 166 | conflicts: string[]; |
| 167 | } |
| 168 | |
| 169 | /** Three-way merge of trees. File-level with line-level diff3 for text files. */ |
| 170 | export async function mergeTrees(store: ObjectStore, base: string | null, ours: string, theirs: string): Promise<MergeResult> { |
| 171 | const conflicts: string[] = []; |
| 172 | const mergeDir = async (b: string | null, o: string | null, t: string | null, prefix: string): Promise<string | null> => { |
| 173 | if (o === t) return o; |
| 174 | if (b === o) return t; |
| 175 | if (b === t) return o; |
| 176 | const mb = new Map((b ? await readTree(store, b) : []).map((e) => [e.name, e])); |
| 177 | const mo = new Map((o ? await readTree(store, o) : []).map((e) => [e.name, e])); |
| 178 | const mt = new Map((t ? await readTree(store, t) : []).map((e) => [e.name, e])); |
| 179 | const result: TreeEntry[] = []; |
| 180 | for (const name of new Set([...mb.keys(), ...mo.keys(), ...mt.keys()])) { |
| 181 | const eb = mb.get(name); |
| 182 | const eo = mo.get(name); |
| 183 | const et = mt.get(name); |
| 184 | const path = prefix ? `${prefix}/${name}` : name; |
| 185 | const same = (x?: TreeEntry, y?: TreeEntry) => (!x && !y) || (!!x && !!y && x.oid === y.oid && x.mode === y.mode); |
| 186 | if (same(eo, et)) { |
| 187 | if (eo) result.push(eo); |
| 188 | continue; |
| 189 | } |
| 190 | if (same(eb, eo)) { |
| 191 | if (et) result.push(et); |
| 192 | continue; |
| 193 | } |
| 194 | if (same(eb, et)) { |
| 195 | if (eo) result.push(eo); |
| 196 | continue; |
| 197 | } |
| 198 | const dir = (e?: TreeEntry) => (e && isTreeMode(e.mode) ? e.oid : null); |
| 199 | if ((!eo || isTreeMode(eo.mode)) && (!et || isTreeMode(et.mode)) && (!eb || isTreeMode(eb.mode))) { |
| 200 | const merged = await mergeDir(dir(eb), dir(eo), dir(et), path); |
| 201 | if (merged) result.push({ mode: "40000", name, oid: merged }); |
| 202 | continue; |
| 203 | } |
| 204 | if (eo && et && !isTreeMode(eo.mode) && !isTreeMode(et.mode) && eo.mode === et.mode) { |
| 205 | const [cb, co, ct] = await Promise.all([ |
| 206 | eb && !isTreeMode(eb.mode) ? mustRead(store, eb.oid) : null, |
| 207 | mustRead(store, eo.oid), |
| 208 | mustRead(store, et.oid), |
| 209 | ]); |
| 210 | if (!isBinary(co.content) && !isBinary(ct.content) && (!cb || !isBinary(cb.content))) { |
| 211 | const merged = mergeText(cb ? fromUtf8(cb.content) : "", fromUtf8(co.content), fromUtf8(ct.content)); |
| 212 | if (merged !== null) { |
| 213 | const oid = await store.write("blob", new TextEncoder().encode(merged)); |
| 214 | result.push({ mode: eo.mode, name, oid }); |
| 215 | continue; |
| 216 | } |
| 217 | } |
| 218 | } |
| 219 | conflicts.push(path); |
| 220 | if (eo) result.push(eo); |
| 221 | } |
| 222 | if (!result.length) return null; |
| 223 | return store.write("tree", serializeTree(result)); |
| 224 | }; |
| 225 | const tree = await mergeDir(base, ours, theirs, ""); |
| 226 | return { tree, conflicts }; |
| 227 | } |