1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367

package fileedit

import (
	"fmt"
	"strings"
)

// op is what happened to a line. The values are the characters of the unified
// format, which saves a conversion table.
type op byte

const (
	keep op = ' '
	del  op = '-'
	add  op = '+'
)

// line is one line of the diff. oldNo and newNo are 1-based, 0 when the line
// does not exist on that side.
type line struct {
	op    op
	text  string
	oldNo int
	newNo int
}

// comparison is a diff ready to render: the lines, and what splitting into
// lines cannot say — whether each side ended with a newline. Two files that
// differ only there are two different files, and `git apply` refuses a patch
// that ignores it.
type comparison struct {
	lines        []line
	oldNL, newNL bool
}

// compare splits, compares, and returns what is needed to display and to patch.
func compare(old, new string) comparison {
	oldLines, oldNL := splitLines(old)
	newLines, newNL := splitLines(new)
	r := comparison{lines: diffLines(oldLines, newLines), oldNL: oldNL, newNL: newNL}

	// Edge case: identical line by line, only the final newline moved. Nothing
	// is marked changed and the patch would be empty while the file changes.
	// The last line is replayed — deleted then added — which is exactly what
	// `git diff` prints.
	if oldNL != newNL && !changed(r.lines) && len(r.lines) > 0 {
		last := r.lines[len(r.lines)-1]
		r.lines = append(r.lines[:len(r.lines)-1],
			line{del, last.text, last.oldNo, 0},
			line{add, last.text, 0, last.newNo},
		)
	}
	return r
}

func (r comparison) changed() bool { return changed(r.lines) }

// firstChanged is the number, in the NEW version, of the first touched line —
// 0 when nothing changed. Enough to open the file at the right place, or to
// say "it starts at line 42" rather than "done".
func (r comparison) firstChanged() int {
	for _, l := range r.lines {
		switch l.op {
		case add:
			return l.newNo
		case del:
			// A deletion has no line in the new version: point at where it
			// happened.
			return max(1, newNoBefore(r.lines, l))
		}
	}
	return 0
}

func (r comparison) stat() (added, deleted int) {
	for _, l := range r.lines {
		switch l.op {
		case add:
			added++
		case del:
			deleted++
		}
	}
	return added, deleted
}

// splitLines splits a body into lines and says whether it ended with a
// newline. Both matter: a file without a final newline is a different file,
// and the unified patch has to say so.
func splitLines(body string) (lines []string, finalNewline bool) {
	if body == "" {
		return nil, true
	}
	finalNewline = strings.HasSuffix(body, "\n")
	if finalNewline {
		body = body[:len(body)-1]
	}
	return strings.Split(body, "\n"), finalNewline
}

// maxCells caps the LCS table. Past it, a line-by-line comparison would cost
// hundreds of megabytes for a diff nobody will read: the middle block is then
// rendered as a block (all deleted, all added), still exact — only coarser.
const maxCells = 4 << 20

// diffLines compares two sequences of lines.
//
// Common prefix and suffix are removed BEFORE the LCS: a targeted edit touches
// a few lines in the middle of a file, and without that cut the table would be
// the size of the file squared.
func diffLines(old, new []string) []line {
	var out []line

	head := 0
	for head < len(old) && head < len(new) && old[head] == new[head] {
		out = append(out, line{keep, old[head], head + 1, head + 1})
		head++
	}
	tail := 0
	for tail < len(old)-head && tail < len(new)-head &&
		old[len(old)-1-tail] == new[len(new)-1-tail] {
		tail++
	}

	midOld, midNew := old[head:len(old)-tail], new[head:len(new)-tail]
	out = append(out, middle(midOld, midNew, head)...)

	for i := len(old) - tail; i < len(old); i++ {
		out = append(out, line{keep, old[i], i + 1, i + 1 - len(old) + len(new)})
	}
	return out
}

// middle compares what remains after trimming the edges. `off` is the number
// of lines already consumed, to number correctly.
func middle(old, new []string, off int) []line {
	if len(old) == 0 && len(new) == 0 {
		return nil
	}
	if len(old)*len(new) > maxCells {
		out := make([]line, 0, len(old)+len(new))
		for i, l := range old {
			out = append(out, line{del, l, off + i + 1, 0})
		}
		for j, l := range new {
			out = append(out, line{add, l, 0, off + j + 1})
		}
		return out
	}

	// Classic LCS: length table, then walk. Files edited by an agent fit in it
	// comfortably.
	lcs := make([][]int, len(old)+1)
	for i := range lcs {
		lcs[i] = make([]int, len(new)+1)
	}
	for i := len(old) - 1; i >= 0; i-- {
		for j := len(new) - 1; j >= 0; j-- {
			if old[i] == new[j] {
				lcs[i][j] = lcs[i+1][j+1] + 1
			} else {
				lcs[i][j] = max(lcs[i+1][j], lcs[i][j+1])
			}
		}
	}

	var out []line
	i, j := 0, 0
	for i < len(old) && j < len(new) {
		switch {
		case old[i] == new[j]:
			out = append(out, line{keep, old[i], off + i + 1, off + j + 1})
			i, j = i+1, j+1
		case lcs[i+1][j] >= lcs[i][j+1]:
			// Deletion first on a tie: a replacement then reads "- old" then
			// "+ new", the order one expects.
			out = append(out, line{del, old[i], off + i + 1, 0})
			i++
		default:
			out = append(out, line{add, new[j], 0, off + j + 1})
			j++
		}
	}
	for ; i < len(old); i++ {
		out = append(out, line{del, old[i], off + i + 1, 0})
	}
	for ; j < len(new); j++ {
		out = append(out, line{add, new[j], 0, off + j + 1})
	}
	return out
}

// newNoBefore finds the number of the kept line that precedes `target`.
func newNoBefore(lines []line, target line) int {
	last := 0
	for _, l := range lines {
		if l == target {
			break
		}
		if l.newNo > 0 {
			last = l.newNo
		}
	}
	return last + 1
}

func changed(lines []line) bool {
	for _, l := range lines {
		if l.op != keep {
			return true
		}
	}
	return false
}

// noNewline is the line the unified format requires when a file does not end
// with a newline. `git apply` reads it; without it, it adds a newline nobody
// asked for.
const noNewline = `\ No newline at end of file`

// contextLines is how many unchanged lines are kept around each change. Three
// is the value of `diff -u` and of git.
const contextLines = 3

// unified renders a unified patch, applicable as-is by `patch -p1` or
// `git apply`. Paths are prefixed a/ and b/ like git does.
func (r comparison) unified(path string) string {
	if !changed(r.lines) {
		return ""
	}
	var b strings.Builder
	fmt.Fprintf(&b, "--- a/%s\n+++ b/%s\n", path, path)

	lastOld, lastNew := 0, 0
	for _, l := range r.lines {
		lastOld, lastNew = max(lastOld, l.oldNo), max(lastNew, l.newNo)
	}
	for _, h := range hunks(r.lines) {
		oldStart, oldCount, newStart, newCount := h.ranges()
		fmt.Fprintf(&b, "@@ -%d,%d +%d,%d @@\n", oldStart, oldCount, newStart, newCount)
		for _, l := range h {
			b.WriteByte(byte(l.op))
			b.WriteString(l.text)
			b.WriteByte('\n')
			// The marker follows the LAST line of each version, and a kept
			// line belongs to both: it may carry it for both at once.
			if (!r.oldNL && l.oldNo == lastOld && l.op != add) ||
				(!r.newNL && l.newNo == lastNew && l.op != del) {
				b.WriteString(noNewline + "\n")
			}
		}
	}
	return b.String()
}

// hunk is a group of contiguous lines shown together.
type hunk []line

// hunks cuts the diff into pieces: each change plus `contextLines` on both
// sides. Touching pieces are merged — otherwise two neighbouring changes would
// produce overlapping @@ headers, and the patch would be refused.
func hunks(lines []line) []hunk {
	var out []hunk
	i := 0
	for i < len(lines) {
		if lines[i].op == keep {
			i++
			continue
		}
		start := max(0, i-contextLines)
		if n := len(out); n > 0 {
			if prevEnd := indexAfter(lines, out[n-1]); prevEnd >= start {
				out[n-1] = append(out[n-1], lines[prevEnd:hunkEnd(lines, i)]...)
				i = hunkEnd(lines, i)
				continue
			}
		}
		out = append(out, append(hunk(nil), lines[start:hunkEnd(lines, i)]...))
		i = hunkEnd(lines, i)
	}
	return out
}

// hunkEnd finds the end of the piece opened at `i`: advance while a change
// occurs within `contextLines` lines, then keep the trailing context.
func hunkEnd(lines []line, i int) int {
	last := i
	for j := i; j < len(lines); j++ {
		if lines[j].op != keep {
			last = j
			continue
		}
		if j-last > contextLines {
			break
		}
	}
	return min(len(lines), last+contextLines+1)
}

// indexAfter returns the position, in `lines`, of the line following the last
// element of `h`.
func indexAfter(lines []line, h hunk) int {
	if len(h) == 0 {
		return 0
	}
	target := h[len(h)-1]
	for i, l := range lines {
		if l == target {
			return i + 1
		}
	}
	return 0
}

// ranges computes the @@ header of the piece.
func (h hunk) ranges() (oldStart, oldCount, newStart, newCount int) {
	for _, l := range h {
		if l.op != add {
			if oldStart == 0 {
				oldStart = l.oldNo
			}
			oldCount++
		}
		if l.op != del {
			if newStart == 0 {
				newStart = l.newNo
			}
			newCount++
		}
	}
	if oldCount == 0 {
		oldStart = 0
	}
	if newCount == 0 {
		newStart = 0
	}
	return oldStart, oldCount, newStart, newCount
}

// render formats the diff for the screen and for the model: a line number, a
// sign, the text. No colours here at all — the same text goes back to the
// model, and ANSI codes in a tool result only get in its way; the screen gets
// its grey from the caller's preview mechanism.
//
// The number shown is ALWAYS the new version's: the one to look at after the
// edit. A deleted line no longer exists there, so it gets the number of the
// place where it vanished — a replacement shows "-" and "+" on the SAME number
// and the column never goes backwards.
func (r comparison) render() string {
	if !changed(r.lines) {
		return ""
	}
	var b strings.Builder
	for _, h := range hunks(r.lines) {
		current := 0
		for _, l := range h {
			no := l.newNo
			if no > 0 {
				current = no
			} else {
				no = current + 1
			}
			fmt.Fprintf(&b, "%4d %c %s\n", no, l.op, l.text)
		}
	}
	return b.String()
}