| 1 | // Package diff computes a line-level diff between two versions of a file and |
| 2 | // renders it as a unified diff, with added/removed line counts. It is a pure |
| 3 | // leaf package: the writer tools use it to preview a pending change (the new |
| 4 | // content a write_file / edit_file / multi_edit would produce) without touching |
| 5 | // disk, so a front-end can show an approval card or a changed-files panel before |
| 6 | // the call runs. |
| 7 | package diff |
| 8 | |
| 9 | import ( |
| 10 | "strconv" |
| 11 | "strings" |
| 12 | |
| 13 | udiff "github.com/aymanbagabas/go-udiff" |
| 14 | ) |
| 15 | |
| 16 | // Kind classifies what a change does to a file's existence, so a UI can label |
| 17 | // it ("new file", "modified", "deleted") without diffing to find out. |
| 18 | type Kind string |
| 19 | |
| 20 | const ( |
| 21 | // Create is a write to a path that did not previously exist. |
| 22 | Create Kind = "create" |
| 23 | // Modify edits or overwrites an existing file. |
| 24 | Modify Kind = "modify" |
| 25 | // Delete empties an existing file to nothing. |
| 26 | Delete Kind = "delete" |
| 27 | ) |
| 28 | |
| 29 | // Change is a previewed (not-yet-applied) edit to one file: the before/after |
| 30 | // text, the unified diff between them, and the line tallies a UI shows as |
| 31 | // "+N / -M". Binary is set when either side looks non-textual, in which case |
| 32 | // Diff is left empty (a byte-diff would be noise). |
| 33 | type Change struct { |
| 34 | Path string `json:"path"` |
| 35 | Kind Kind `json:"kind"` |
| 36 | OldText string `json:"old_text"` |
| 37 | NewText string `json:"new_text"` |
| 38 | Added int `json:"added"` // lines present in new but not old |
| 39 | Removed int `json:"removed"` // lines present in old but not new |
| 40 | Diff string `json:"diff"` // unified diff; "" when Binary |
| 41 | Binary bool `json:"binary"` |
| 42 | Mode string `json:"mode,omitempty"` // optional render mode metadata |
| 43 | Hunks int `json:"hunks,omitempty"` // unified diff hunk count when rendered |
| 44 | } |
| 45 | |
| 46 | type OutputMode string |
| 47 | |
| 48 | const ( |
| 49 | OutputModePatch OutputMode = "patch" |
| 50 | OutputModePreview OutputMode = "preview" |
| 51 | ) |
| 52 | |
| 53 | type BuildOptions struct { |
| 54 | ContextLines int |
| 55 | OldLabel string |
| 56 | NewLabel string |
| 57 | Mode OutputMode |
| 58 | } |
| 59 | |
| 60 | // defaultContext is how many unchanged lines surround each change in the |
| 61 | // unified diff, matching the conventional `diff -u` default. |
| 62 | const defaultContext = 3 |
| 63 | |
| 64 | // maxDiffEdits caps the changed window we will send to an exact line diff. A |
| 65 | // near-total rewrite of a large file is unreadable and can make LCS/Myers-style |
| 66 | // algorithms allocate heavily, so we fall back to tallies before calling the |
| 67 | // third-party renderer. |
| 68 | const maxDiffEdits = 2000 |
| 69 | |
| 70 | // Build computes the Change from old to new text for path. kind is supplied by |
| 71 | // the caller (it knows whether the file existed); Build fills the diff and the |
| 72 | // line tallies. When either side contains a NUL byte the file is treated as |
| 73 | // binary: the tallies are left zero and Diff is empty. |
| 74 | func Build(path, oldText, newText string, kind Kind) Change { |
| 75 | return BuildWithOptions(path, oldText, newText, kind, BuildOptions{ContextLines: -1}) |
| 76 | } |
| 77 | |
| 78 | // BuildWithOptions computes a Change like Build, with explicit render options |
| 79 | // for callers that need preview-style labels or non-default context lines. |
| 80 | func BuildWithOptions(path, oldText, newText string, kind Kind, opts BuildOptions) Change { |
| 81 | opts = normalizeBuildOptions(path, opts) |
| 82 | c := Change{Path: path, Kind: kind, OldText: oldText, NewText: newText} |
| 83 | if opts.Mode != "" && opts.Mode != OutputModePatch { |
| 84 | c.Mode = string(opts.Mode) |
| 85 | } |
| 86 | if isBinary(oldText) || isBinary(newText) { |
| 87 | c.Binary = true |
| 88 | return c |
| 89 | } |
| 90 | if oldText == newText { |
| 91 | return c // no-op change; empty diff, zero tallies |
| 92 | } |
| 93 | |
| 94 | oldLines, _ := splitLines(oldText) |
| 95 | newLines, _ := splitLines(newText) |
| 96 | if exactDiffTooLarge(oldLines, newLines) { |
| 97 | c.Added, c.Removed = approxTally(oldLines, newLines) |
| 98 | c.Diff = "(diff omitted: change too large to render — +" + itoa(c.Added) + " / -" + itoa(c.Removed) + " lines)" |
| 99 | return c |
| 100 | } |
| 101 | |
| 102 | edits := udiff.Lines(oldText, newText) |
| 103 | c.Added, c.Removed = tallyEdits(oldText, edits) |
| 104 | diff, err := udiff.ToUnified(opts.OldLabel, opts.NewLabel, oldText, edits, opts.ContextLines) |
| 105 | if err != nil { |
| 106 | c.Added, c.Removed = approxTally(oldLines, newLines) |
| 107 | c.Diff = "(diff omitted: failed to render — +" + itoa(c.Added) + " / -" + itoa(c.Removed) + " lines)" |
| 108 | return c |
| 109 | } |
| 110 | c.Diff = diff |
| 111 | c.Hunks = countUnifiedHunks(diff) |
| 112 | return c |
| 113 | } |
| 114 | |
| 115 | func normalizeBuildOptions(path string, opts BuildOptions) BuildOptions { |
| 116 | if opts.ContextLines < 0 { |
| 117 | opts.ContextLines = defaultContext |
| 118 | } |
| 119 | if opts.Mode == "" { |
| 120 | opts.Mode = OutputModePatch |
| 121 | } |
| 122 | if opts.OldLabel == "" { |
| 123 | prefix := "a/" |
| 124 | if opts.Mode == OutputModePreview { |
| 125 | prefix = "before/" |
| 126 | } |
| 127 | opts.OldLabel = prefix + path |
| 128 | } |
| 129 | if opts.NewLabel == "" { |
| 130 | prefix := "b/" |
| 131 | if opts.Mode == OutputModePreview { |
| 132 | prefix = "after/" |
| 133 | } |
| 134 | opts.NewLabel = prefix + path |
| 135 | } |
| 136 | return opts |
| 137 | } |
| 138 | |
| 139 | func countUnifiedHunks(diff string) int { |
| 140 | return strings.Count(diff, "\n@@ ") |
| 141 | } |
| 142 | |
| 143 | func exactDiffTooLarge(oldLines, newLines []string) bool { |
| 144 | return changedWindowSize(oldLines, newLines) > maxDiffEdits |
| 145 | } |
| 146 | |
| 147 | func changedWindowSize(oldLines, newLines []string) int { |
| 148 | start := 0 |
| 149 | for start < len(oldLines) && start < len(newLines) && oldLines[start] == newLines[start] { |
| 150 | start++ |
| 151 | } |
| 152 | oldEnd := len(oldLines) |
| 153 | newEnd := len(newLines) |
| 154 | for oldEnd > start && newEnd > start && oldLines[oldEnd-1] == newLines[newEnd-1] { |
| 155 | oldEnd-- |
| 156 | newEnd-- |
| 157 | } |
| 158 | return (oldEnd - start) + (newEnd - start) |
| 159 | } |
| 160 | |
| 161 | func tallyEdits(oldText string, edits []udiff.Edit) (added, removed int) { |
| 162 | for _, edit := range edits { |
| 163 | if edit.Start >= 0 && edit.End >= edit.Start && edit.End <= len(oldText) { |
| 164 | removed += logicalLineCount(oldText[edit.Start:edit.End]) |
| 165 | } |
| 166 | added += logicalLineCount(edit.New) |
| 167 | } |
| 168 | return added, removed |
| 169 | } |
| 170 | |
| 171 | func logicalLineCount(s string) int { |
| 172 | lines, _ := splitLines(s) |
| 173 | return len(lines) |
| 174 | } |
| 175 | |
| 176 | // approxTally counts added/removed lines by multiset difference — order- |
| 177 | // insensitive but O(n+m), used when the exact diff is skipped for being too large. |
| 178 | func approxTally(oldLines, newLines []string) (added, removed int) { |
| 179 | counts := make(map[string]int, len(oldLines)) |
| 180 | for _, l := range oldLines { |
| 181 | counts[l]++ |
| 182 | } |
| 183 | for _, l := range newLines { |
| 184 | if counts[l] > 0 { |
| 185 | counts[l]-- |
| 186 | } else { |
| 187 | added++ |
| 188 | } |
| 189 | } |
| 190 | for _, c := range counts { |
| 191 | removed += c |
| 192 | } |
| 193 | return added, removed |
| 194 | } |
| 195 | |
| 196 | // isBinary reports whether s looks non-textual. A NUL byte never appears in |
| 197 | // UTF-8 text, so it is a cheap, reliable signal — the same heuristic git uses. |
| 198 | func isBinary(s string) bool { return strings.IndexByte(s, 0) >= 0 } |
| 199 | |
| 200 | // splitLines breaks s into lines without their terminators and reports whether |
| 201 | // the text ended with a newline. An empty string yields no lines. A trailing |
| 202 | // newline does not produce a spurious empty final line. |
| 203 | func splitLines(s string) (lines []string, endsWithNewline bool) { |
| 204 | if s == "" { |
| 205 | return nil, true // vacuously: no missing-newline marker for empty content |
| 206 | } |
| 207 | endsWithNewline = strings.HasSuffix(s, "\n") |
| 208 | if endsWithNewline { |
| 209 | s = s[:len(s)-1] |
| 210 | } |
| 211 | return strings.Split(s, "\n"), endsWithNewline |
| 212 | } |
| 213 | |
| 214 | func itoa(n int) string { return strconv.Itoa(n) } |
| 215 |