summaryrefslogtreecommitdiff
path: root/src/hunks.zig
blob: 24aaf63de8a5bcb34d86ca932ff0f5461dbc8e5c (plain) (blame)
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
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
//! A unified diff (`.diff`, `.patch`, a paged `git show`) stacked as a
//! diff viewer shows it (Diff): each hunk under its `path:line`, the
//! declarations around it from tree-sitter as a result's context
//! (locations.zig), its lines behind their `+`/`-` markers drawn red and
//! green, coloured as their file, and the words a changed line changed on
//! a tinted ground as delta emphasises them (its edits.rs and align.rs, here as `inferEdits`
//! and `Alignment`).
const std = @import("std");
const pardes = @import("pardes.zig");
const diff = @import("diff.zig");
const syntax = @import("syntax.zig");
const locations = @import("locations.zig");

const Pardes = pardes.Pardes;
const Row = locations.Row;

/// The rows `content`, a diff, stacks to, for a pane in `dir`, with each
/// row's metadata (Output.fillRows). Text and rows are `p.gpa`'s; all else
/// is the step's scratch.
pub fn format(p: *Pardes, dir: []const u8, content: []const u8) !locations.Result {
    const arena = p.scratch.allocator();
    const styles = try syntax.highlightDiff(arena, content, 0, content.len);
    var out: Out = .{ .p = p, .text = .init(p.gpa) };
    errdefer out.deinit();
    var walk: diff.Walk = .{};
    var hunk: Hunk = .{};
    var source: SourceMemo = .{};
    var at: usize = 0;
    // The empty text after a last newline is no line.
    while (at < content.len) {
        const nl = std.mem.indexOfScalarPos(u8, content, at, '\n') orelse content.len;
        const raw = content[at..nl];
        const got = walk.step(raw);
        const line = std.mem.trimEnd(u8, raw, "\r");
        switch (got.kind) {
            .context, .added, .removed => {
                const skip = @intFromBool(line.len > 0 and std.mem.indexOfScalar(u8, " +-", line[0]) != null);
                try hunk.lines.append(arena, .{
                    .kind = got.kind,
                    .code = line[skip..],
                    .styles = styles[at + skip ..][0 .. line.len - skip],
                    .old = got.old,
                    .new = got.new,
                });
            },
            // A `\ No newline` belongs to the line above, as delta shows it.
            .no_newline => {},
            else => {
                try flush(&out, &hunk, &source, dir);
                switch (got.kind) {
                    .hunk => hunk = .{
                        .path = walk.path(),
                        .deleted = walk.deleted(),
                        .old_start = got.old,
                        .new_start = got.new,
                        .header = gitContext(line),
                    },
                    // What is said around the hunks, a mailed patch's
                    // headers, message and diffstat, as it was written.
                    .other => try out.row(line, "", .{ .kind = .context, .at = .{} }),
                    // A section's own words (a new file's mode, a rename,
                    // `Binary files ... differ`), muted; its `diff` and
                    // `index` lines say nothing the labels do not.
                    .meta => if (!std.mem.startsWith(u8, line, "diff ") and !std.mem.startsWith(u8, line, "index "))
                        try out.row(line, "", .{ .kind = .context, .declaration = true, .at = .{} }),
                    else => {},
                }
            },
        }
        at = nl + 1;
    }
    try flush(&out, &hunk, &source, dir);
    const rows = try out.rows.toOwnedSlice(p.gpa);
    errdefer locations.freeRows(p.gpa, rows);
    return .{ .content = try out.text.toOwnedSlice(), .rows = rows, .anchor = null };
}

const HunkLine = struct {
    kind: diff.Kind,
    code: []const u8,
    /// Its code's style bytes, as the diff pane paints them (syntax.zig
    /// highlightDiff), the emphasis bit added by `inferEdits`.
    styles: []u8,
    old: usize,
    new: usize,
    /// Paired with a line it changed (inferEdits): its words show that;
    /// unpaired, the whole line was added or removed.
    paired: bool = false,
};

const Hunk = struct {
    path: []const u8 = "",
    deleted: bool = false,
    old_start: usize = 0,
    new_start: usize = 0,
    /// What git wrote after the `@@`'s second marker (its function line).
    header: []const u8 = "",
    lines: std.ArrayList(HunkLine) = .empty,
};

/// `@@ -a,b +c,d @@ fn foo()`: `fn foo()`.
fn gitContext(line: []const u8) []const u8 {
    const close = std.mem.indexOfPos(u8, line, 2, "@@") orelse return "";
    return std.mem.trim(u8, line[close + 2 ..], " \t");
}

const Out = struct {
    p: *Pardes,
    text: std.Io.Writer.Allocating,
    rows: std.ArrayList(Row) = .empty,

    fn deinit(out: *Out) void {
        out.text.deinit();
        for (out.rows.items) |r| {
            out.p.gpa.free(r.path);
            out.p.gpa.free(r.colors);
        }
        out.rows.deinit(out.p.gpa);
    }

    const Meta = struct {
        kind: @FieldType(Row, "kind"),
        declaration: bool = false,
        at: @FieldType(Row, "at"),
        location_end: usize = 0,
        code_start: usize = 0,
        colors: []const u8 = &.{},
    };

    /// One row: its text, a newline, and its metadata.
    fn row(out: *Out, text: []const u8, path: []const u8, meta: Meta) !void {
        const gpa = out.p.gpa;
        try out.text.writer.writeAll(text);
        try out.text.writer.writeByte('\n');
        const owned_path = try gpa.dupe(u8, path);
        errdefer gpa.free(owned_path);
        const colors = try gpa.dupe(u8, meta.colors);
        errdefer gpa.free(colors);
        try out.rows.append(gpa, .{
            .kind = meta.kind,
            .declaration = meta.declaration,
            .path = owned_path,
            .at = meta.at,
            .location_end = meta.location_end,
            .code_start = meta.code_start,
            .colors = colors,
        });
    }
};

/// The file a diff section names, as found from the pane's directory or
/// one above it (a patch kept in a subdirectory of its repository).
const SourceMemo = struct {
    path: []const u8 = "",
    /// The name a look from the pane's directory resolves; null when the
    /// file is nowhere to be found.
    shown: ?[]const u8 = null,
    lines: []const []const u8 = &.{},
    declarations: []const syntax.ContextDeclaration = &.{},
};

/// Where a +Diff of `content`, a diff in `dir`, stands: the directory its
/// first file is found from (`dir` or one above it, as `findSource` looks),
/// so its rows name their files as the diff does; `dir` when none is found.
pub fn sourceRoot(p: *Pardes, dir: []const u8, content: []const u8) []const u8 {
    var walk: diff.Walk = .{};
    var lines = std.mem.splitScalar(u8, content, '\n');
    const path = while (lines.next()) |line| {
        if (walk.step(line).kind == .hunk and walk.path().len > 0) break walk.path();
    } else return dir;
    var base: []const u8 = dir;
    for (0..8) |_| {
        if (locations.sourceText(p, p.scratch.allocator(), base, path) != null) return base;
        base = std.fs.path.dirname(base) orelse return dir;
    }
    return dir;
}

fn findSource(p: *Pardes, memo: *SourceMemo, dir: []const u8, path: []const u8) !void {
    if (std.mem.eql(u8, memo.path, path)) return;
    const arena = p.scratch.allocator();
    memo.* = .{ .path = path };
    // ponytail: eight directories up; a repository deeper than that under
    // its patch is looked for from the patch's own directory only.
    var base: []const u8 = dir;
    for (0..8) |_| {
        if (locations.sourceText(p, arena, base, path)) |text| {
            memo.shown = if (base.ptr == dir.ptr) path else try std.fs.path.relativePosix(arena, "/", dir, text.path);
            var lines: std.ArrayList([]const u8) = .empty;
            var split = std.mem.splitScalar(u8, text.bytes, '\n');
            while (split.next()) |line| try lines.append(arena, std.mem.trimEnd(u8, line, "\r"));
            memo.lines = lines.items;
            var hit = p.locations_cache.get(p.tree_sitter_gpa, text.path, text.bytes, true, false) catch
                locations.Cache.Hit{ .analysis = syntax.analyzeSource(arena, text.path, text.bytes, true, false) catch .{} };
            defer hit.deinit(p.tree_sitter_gpa);
            // The cache's may go at its next use: kept for the section.
            memo.declarations = try arena.dupe(syntax.ContextDeclaration, hit.analysis.declarations);
            return;
        }
        base = std.fs.path.dirname(base) orelse return;
    }
}

/// Which side of the hunk the file on disk holds, the new one (the patch
/// applied) or the old one, and how far the file has moved it from where
/// the hunk says (`shift`, lines), as patch finds a hunk in a file edited
/// since. A file edited inside the hunk too still holds most of its lines:
/// the place holding the most of them wins (the nearer on a tie) if it
/// holds at least half. Only some, at the nearest place, could be a sibling
/// with the same lines (two functions with one signature's tail). The rows
/// are counted on that side, so moved.
const Side = enum { new, old, neither };
const OnDisk = struct { side: Side, shift: i64 = 0 };

/// ponytail: a hunk moved more than this many lines is not looked for;
/// each try compares the hunk's lines, so a wider search costs that more.
const max_shift = 200;

fn sideOnDisk(memo: *const SourceMemo, hunk: *const Hunk) OnDisk {
    if (memo.shown == null) return .{ .side = .neither };
    var best: OnDisk = .{ .side = .neither };
    var best_held: usize = 0;
    var best_of: usize = 1;
    var shift: i64 = 0;
    while (shift <= max_shift) : (shift += 1) {
        for ([2]i64{ shift, -shift }) |by| {
            inline for (.{ Side.new, Side.old }) |side| {
                const start: i64 = @as(i64, @intCast((if (side == .new) hunk.new_start else hunk.old_start) -| 1)) + by;
                if (start >= 0) {
                    const got = heldAt(memo, hunk, side, @intCast(start));
                    if (got.held == got.of) return .{ .side = side, .shift = by };
                    // A larger share only: the nearer keeps a tie.
                    if (got.held * best_of > best_held * got.of) {
                        best = .{ .side = side, .shift = by };
                        best_held = got.held;
                        best_of = got.of;
                    }
                }
            }
            if (shift == 0) break;
        }
    }
    return if (best_held > 0 and best_held * 2 >= best_of) best else .{ .side = .neither };
}

/// How many of the hunk's `side` lines the file holds from row `start` on,
/// of how many: blank lines, which match anywhere, count for neither.
fn heldAt(memo: *const SourceMemo, hunk: *const Hunk, comptime side: Side, start: usize) struct { held: usize, of: usize } {
    var row = start;
    var held: usize = 0;
    var of: usize = 0;
    for (hunk.lines.items) |line| {
        const skipped = if (side == .new) line.kind == .removed else line.kind == .added;
        if (skipped) continue;
        defer row += 1;
        if (std.mem.trim(u8, line.code, " \t").len == 0) continue;
        of += 1;
        if (row < memo.lines.len and std.mem.eql(u8, memo.lines[row], line.code)) held += 1;
    }
    return .{ .held = held, .of = @max(of, 1) };
}

fn flush(out: *Out, hunk: *Hunk, memo: *SourceMemo, dir: []const u8) !void {
    defer hunk.* = .{};
    if (hunk.path.len == 0 or hunk.lines.items.len == 0) return;
    const p = out.p;
    const arena = p.scratch.allocator();
    try findSource(p, memo, dir, hunk.path);
    const disk = sideOnDisk(memo, hunk);
    const side = disk.side;
    // A line number of the hunk's, where the file has it now.
    const moved = struct {
        fn by(n: usize, shift: i64) usize {
            return @intCast(@max(0, @as(i64, @intCast(n)) + shift));
        }
    }.by;
    const shown = if (side == .neither) hunk.path else memo.shown.?;
    const lines = hunk.lines.items;

    // Where the hunk changes something, on the side its rows count: the
    // place its label opens.
    const first_change = for (lines) |line| {
        if (line.kind != .context) break line;
    } else lines[0];
    const on_old = side == .old or (side == .neither and hunk.deleted);
    const start_row = moved(if (on_old) hunk.old_start else hunk.new_start, disk.shift) -| 1;
    const change_row = moved(if (on_old) first_change.old else first_change.new, disk.shift) -| 1;

    // The declarations it stands in, outermost first, as a result's
    // tree-sitter context: each one's header rows above the hunk.
    var depth: usize = 0;
    if (side != .neither) for (memo.declarations) |declaration| {
        if (declaration.start_line >= start_row) break;
        if (declaration.end_line < change_row) continue;
        depth += 1;
        var row = declaration.start_line;
        while (row <= declaration.header_end_line and row < start_row) : (row += 1) {
            const at: @FieldType(Row, "at") = .{ .line = row + 1 };
            if (row == declaration.start_line and p.locations_config.tslocations) {
                const label = try std.fmt.allocPrint(arena, "{s}:{d}", .{ shown, row + 1 });
                try out.row(label, shown, .{ .kind = .context, .declaration = true, .at = at, .location_end = label.len, .code_start = label.len });
            }
            // A blank where a hunk line has its marker: the code aligns.
            try out.row(try std.fmt.allocPrint(arena, " {s}", .{memo.lines[row]}), shown, .{ .kind = .context, .declaration = true, .at = at });
        }
    };

    // The hunk's label: a step for n and N, and a look's place.
    const line_no = change_row + 1;
    var label: std.Io.Writer.Allocating = .init(arena);
    try label.writer.print("{s}:{d}", .{ shown, line_no });
    const location_end = label.written().len;
    if (depth > 0) {
        try label.writer.writeByte(' ');
        try label.writer.splatByteAll('*', depth);
    }
    try out.row(label.written(), shown, .{ .kind = .match, .at = .{ .line = line_no }, .location_end = location_end, .code_start = label.written().len });
    // No file to read declarations from: git's own function line, muted
    // the same way. With one, git's guess (the last line before the hunk
    // that looked like a function) would only contradict it.
    if (side == .neither and hunk.header.len > 0)
        try out.row(try std.fmt.allocPrint(arena, " {s}", .{hunk.header}), shown, .{ .kind = .context, .declaration = true, .at = .{ .line = line_no } });

    // Each run of removed lines and the added lines after it: the words
    // they changed.
    var i: usize = 0;
    while (i < lines.len) {
        if (lines[i].kind == .context) {
            i += 1;
            continue;
        }
        const minus_start = i;
        while (i < lines.len and lines[i].kind == .removed) i += 1;
        const plus_start = i;
        while (i < lines.len and lines[i].kind == .added) i += 1;
        try inferEdits(arena, lines[minus_start..plus_start], lines[plus_start..i]);
    }

    // Each line behind its marker, `+`, `-` or a blank, as the diff
    // has it: the marker coloured, the line as its file's.
    for (lines) |line| {
        const flag: u8 = switch (line.kind) {
            .added => syntax.diff_added,
            .removed => syntax.diff_removed,
            else => 0,
        } | @as(u8, if (line.kind != .context and !line.paired) syntax.diff_whole else 0);
        const text = try std.fmt.allocPrint(arena, "{c}{s}", .{ @as(u8, switch (line.kind) {
            .added => '+',
            .removed => '-',
            else => ' ',
        }), line.code });
        const colors = try arena.alloc(u8, text.len);
        colors[0] = flag;
        @memcpy(colors[1..], line.styles);
        const on = moved(if (on_old) line.old else line.new, disk.shift);
        try out.row(text, shown, .{ .kind = .preview, .at = .{ .line = @max(1, on) }, .colors = colors });
    }
}

// ---- the words a changed line changed (delta's edits.rs) ----

/// delta's `max-line-distance`: a removed and an added line further apart
/// than this are not one line changed, and neither is emphasised.
const max_line_distance = 0.6;

/// ponytail: a run of more removed or added lines than this, or a pair
/// whose token table is bigger than `max_cells`, is shown unemphasised
/// rather than aligned at a quadratic cost (delta aligns them all).
const max_run = 256;
const max_cells = 1 << 16;
/// Pairs one hunk compares (each a table of up to `max_cells`): past it, the
/// rest of its lines are shown unemphasised. And the scratch each pair is
/// aligned in, reused by the next: its table and the ranges it marks.
const max_pairs = 4096;
const pair_scratch_bytes = 8 << 20;

/// Pair each removed line with the first added line after the last one
/// paired that is near enough to it, in order, and emphasise in both the
/// tokens one has and the other has not.
fn inferEdits(arena: std.mem.Allocator, minus: []HunkLine, plus: []HunkLine) !void {
    if (minus.len == 0 or plus.len == 0 or minus.len > max_run or plus.len > max_run) return;
    const plus_tokens = try arena.alloc([]const []const u8, plus.len);
    for (plus, plus_tokens) |line, *tokens| tokens.* = try tokenize(arena, line.code);
    var scratch: std.heap.FixedBufferAllocator = .init(try @import("memory.zig").unfilled(arena, pair_scratch_bytes));
    var pairs: usize = 0;
    var plus_index: usize = 0;
    for (minus) |*m| {
        const m_tokens = try tokenize(arena, m.code);
        var j = plus_index;
        while (j < plus.len) : (j += 1) {
            const p_tokens = plus_tokens[j];
            if ((m_tokens.len + 1) * (p_tokens.len + 1) > max_cells) continue;
            if (pairs == max_pairs) return;
            pairs += 1;
            scratch.reset();
            const pair = scratch.allocator();
            var alignment = Alignment.init(pair, m_tokens, p_tokens) catch continue;
            const marks = annotate(pair, &alignment, m.code, plus[j].code) catch continue;
            if (marks.distance > max_line_distance) continue;
            for (marks.minus) |r| for (m.styles[r[0]..r[1]]) |*b| {
                b.* |= syntax.diff_emph;
            };
            for (marks.plus) |r| for (plus[j].styles[r[0]..r[1]]) |*b| {
                b.* |= syntax.diff_emph;
            };
            m.paired = true;
            plus[j].paired = true;
            plus_index = j + 1;
            break;
        }
    }
}

/// delta's tokenize with its default `\w+`: a leading empty token, each
/// run of word characters one token, and every other character one. A
/// line starting with no word gets a second empty token, as delta's does.
/// ponytail: any byte past ASCII counts as a word character, close to
/// Unicode `\w` for letters; a non-ASCII punctuation mark joins a word.
fn tokenize(arena: std.mem.Allocator, line: []const u8) ![]const []const u8 {
    var tokens: std.ArrayList([]const u8) = .empty;
    try tokens.append(arena, "");
    if (line.len > 0 and !isWord(line[0])) try tokens.append(arena, "");
    var at: usize = 0;
    while (at < line.len) {
        var end = at + 1;
        // A byte past ASCII is a word's, so what is left is one byte.
        if (isWord(line[at])) while (end < line.len and isWord(line[end])) {
            end += 1;
        };
        try tokens.append(arena, line[at..end]);
        at = end;
    }
    return tokens.items;
}

fn isWord(c: u8) bool {
    return std.ascii.isAlphanumeric(c) or c == '_' or c >= 0x80;
}

const Op = enum(u2) { noop, deletion, insertion };

/// delta's align.rs: a Needleman-Wunsch table over two token lists, a
/// change costing more where it starts a new run, so changes group.
const Alignment = struct {
    x: []const []const u8,
    y: []const []const u8,
    cells: []Cell,
    width: usize,

    const Cell = struct { parent: u32, op: Op, cost: u32 };
    const deletion_cost = 2;
    const insertion_cost = 2;
    const initial_mismatch_penalty = 1;
    const never = std.math.maxInt(u32);

    fn init(arena: std.mem.Allocator, x: []const []const u8, y: []const []const u8) !Alignment {
        const width = x.len + 1;
        const cells = try arena.alloc(Cell, width * (y.len + 1));
        @memset(cells, .{ .parent = 0, .op = .noop, .cost = 0 });
        var a: Alignment = .{ .x = x, .y = y, .cells = cells, .width = width };
        for (1..width) |i| cells[i] = .{ .parent = 0, .op = .deletion, .cost = @intCast(i * deletion_cost + initial_mismatch_penalty) };
        for (1..y.len + 1) |j| cells[j * width] = .{ .parent = 0, .op = .insertion, .cost = @intCast(j * insertion_cost + initial_mismatch_penalty) };
        for (x, 0..) |x_i, i| for (y, 0..) |y_j, j| {
            const left = a.index(i, j + 1);
            const diag = a.index(i, j);
            const up = a.index(i + 1, j);
            // Ties go to the first: an insertion, then a deletion, then a
            // match, so a moved token reads as removed then added.
            const candidates = [3]Cell{
                .{ .parent = @intCast(up), .op = .insertion, .cost = a.mismatchCost(up, insertion_cost) },
                .{ .parent = @intCast(left), .op = .deletion, .cost = a.mismatchCost(left, deletion_cost) },
                .{ .parent = @intCast(diag), .op = .noop, .cost = if (std.mem.eql(u8, x_i, y_j)) cells[diag].cost else never },
            };
            var best = candidates[0];
            for (candidates[1..]) |c| if (c.cost < best.cost) {
                best = c;
            };
            cells[a.index(i + 1, j + 1)] = best;
        };
        return a;
    }

    fn mismatchCost(a: *const Alignment, parent: usize, basic: u32) u32 {
        const cell = a.cells[parent];
        return cell.cost +| basic +| @as(u32, if (cell.op == .noop) initial_mismatch_penalty else 0);
    }

    fn index(a: *const Alignment, i: usize, j: usize) usize {
        return j * a.width + i;
    }

    /// The operations read back from the table's far corner, in order,
    /// each run as one (op, count).
    fn coalesced(a: *const Alignment, arena: std.mem.Allocator) ![]const struct { Op, usize } {
        var ops: std.ArrayList(Op) = .empty;
        var cell = a.cells[a.index(a.x.len, a.y.len)];
        while (true) {
            try ops.append(arena, cell.op);
            if (cell.parent == 0) break;
            cell = a.cells[cell.parent];
        }
        std.mem.reverse(Op, ops.items);
        var runs: std.ArrayList(struct { Op, usize }) = .empty;
        for (ops.items) |op| {
            if (runs.items.len > 0 and runs.items[runs.items.len - 1][0] == op) {
                runs.items[runs.items.len - 1][1] += 1;
            } else try runs.append(arena, .{ op, 1 });
        }
        return runs.items;
    }
};

const Marks = struct {
    /// Byte ranges of the removed and the added line to emphasise.
    minus: []const [2]usize,
    plus: []const [2]usize,
    distance: f64,
};

/// delta's annotate: walk the alignment's runs over both lines, marking
/// what each deleted and inserted, and a run of blanks between two changes
/// with them; the distance is the changed width over the whole width (a
/// kept section counting on both lines).
fn annotate(arena: std.mem.Allocator, a: *const Alignment, minus_line: []const u8, plus_line: []const u8) !Marks {
    var minus: std.ArrayList([2]usize) = .empty;
    var plus: std.ArrayList([2]usize) = .empty;
    var x_off: usize = 0;
    var y_off: usize = 0;
    var m_byte: usize = 0;
    var p_byte: usize = 0;
    var numer: usize = 0;
    var denom: usize = 0;
    var minus_prev: Op = .noop;
    var plus_prev: Op = .noop;
    const Take = struct {
        fn section(tokens: []const []const u8, off: *usize, byte: *usize, n: usize, line: []const u8) [2]usize {
            const start = byte.*;
            const end_tok = @min(tokens.len, off.* + n);
            for (tokens[@min(off.*, end_tok)..end_tok]) |t| byte.* += t.len;
            off.* = end_tok;
            byte.* = @min(byte.*, line.len);
            return .{ start, byte.* };
        }
    };
    for (try a.coalesced(arena)) |run| {
        const op, const n = run;
        switch (op) {
            .deletion => {
                const r = Take.section(a.x, &x_off, &m_byte, n, minus_line);
                const w = trimmedWidth(minus_line[r[0]..r[1]]);
                numer += w;
                denom += w;
                try minus.append(arena, r);
                minus_prev = .deletion;
            },
            .noop => {
                const r = Take.section(a.x, &x_off, &m_byte, n, minus_line);
                const section = minus_line[r[0]..r[1]];
                denom += 2 * trimmedWidth(section);
                const is_space = std.mem.trim(u8, section, " \t").len == 0;
                const coalesce = is_space and
                    ((minus_prev == .deletion and plus_prev == .insertion and
                        (x_off < a.x.len -| 1 or y_off < a.y.len -| 1)) or
                        (minus_prev == .noop and plus_prev == .noop));
                if (coalesce and minus_prev == .deletion) try minus.append(arena, r);
                const pr = Take.section(a.y, &y_off, &p_byte, n, plus_line);
                if (coalesce and plus_prev == .insertion) try plus.append(arena, pr);
                minus_prev = .noop;
                plus_prev = .noop;
            },
            .insertion => {
                const r = Take.section(a.y, &y_off, &p_byte, n, plus_line);
                const w = trimmedWidth(plus_line[r[0]..r[1]]);
                numer += w;
                denom += w;
                try plus.append(arena, r);
                plus_prev = .insertion;
            },
        }
    }
    const distance: f64 = if (denom > 0) @as(f64, @floatFromInt(numer)) / @as(f64, @floatFromInt(denom)) else 0;
    return .{ .minus = minus.items, .plus = plus.items, .distance = distance };
}

fn trimmedWidth(section: []const u8) usize {
    return pardes.panes.File.displayWidth(std.mem.trim(u8, section, " \t"));
}

// ---- tests ----

const testing = std.testing;

fn emphasised(line: HunkLine) ![]const u8 {
    var out: std.ArrayList(u8) = .empty;
    for (line.code, line.styles) |c, s| try out.append(testing.allocator, if (s & syntax.diff_emph != 0) c else '.');
    return out.toOwnedSlice(testing.allocator);
}

fn expectEmphasis(minus: []const u8, plus: []const u8, want_minus: []const u8, want_plus: []const u8) !void {
    var arena_state: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();
    var m = [_]HunkLine{.{ .kind = .removed, .code = minus, .styles = try arena.alloc(u8, minus.len), .old = 1, .new = 1 }};
    var p = [_]HunkLine{.{ .kind = .added, .code = plus, .styles = try arena.alloc(u8, plus.len), .old = 2, .new = 1 }};
    @memset(m[0].styles, 0);
    @memset(p[0].styles, 0);
    try inferEdits(arena, &m, &p);
    const got_minus = try emphasised(m[0]);
    defer testing.allocator.free(got_minus);
    const got_plus = try emphasised(p[0]);
    defer testing.allocator.free(got_plus);
    try testing.expectEqualStrings(want_minus, got_minus);
    try testing.expectEqualStrings(want_plus, got_plus);
}

test "delta's emphasis: the word a line changed, in both lines" {
    try expectEmphasis("    let x = foo(1);", "    let x = bar(1);", "............foo....", "............bar....");
    try expectEmphasis("a b c", "a x c", "..b..", "..x..");
}

test "delta's emphasis: lines too far apart are no change of one another" {
    try expectEmphasis("completely different text", "nothing alike here at all", ".........................", ".........................");
}

test "delta's emphasis: a word added keeps the rest plain" {
    try expectEmphasis("fn run(a: u32)", "fn run(a: u32, b: u32)", "..............", "............., b: u32.");
}

test "delta's alignment: kitten to sitting, as align.rs has it" {
    var arena_state: std.heap.ArenaAllocator = .init(testing.allocator);
    defer arena_state.deinit();
    const arena = arena_state.allocator();
    // One token a letter, as delta's test splits them, behind the empty one.
    const x = [_][]const u8{ "", "k", "i", "t", "t", "e", "n" };
    const y = [_][]const u8{ "", "s", "i", "t", "t", "i", "n", "g" };
    const a = try Alignment.init(arena, &x, &y);
    var ops: std.ArrayList(Op) = .empty;
    for (try a.coalesced(arena)) |run| for (0..run[1]) |_| try ops.append(arena, run[0]);
    try testing.expectEqualSlices(Op, &.{ .noop, .deletion, .insertion, .noop, .noop, .noop, .deletion, .insertion, .noop, .insertion }, ops.items);
}

test "a diff stacks to a label a hunk and its lines, markers gone, tinted and stepped" {
    const p = try Pardes.init(testing.allocator, .{ .tty_only = true });
    defer p.deinit();
    const patch =
        \\diff --git a/nowhere/x.txt b/nowhere/x.txt
        \\--- a/nowhere/x.txt
        \\+++ b/nowhere/x.txt
        \\@@ -1,3 +1,3 @@ section one
        \\ keep
        \\-old value
        \\+new value
        \\ tail
        \\
    ;
    const result = try format(p, "/pardes-surely-missing-dir", patch);
    defer p.gpa.free(result.content);
    defer locations.freeRows(p.gpa, result.rows);
    try testing.expectEqualStrings("nowhere/x.txt:2\n section one\n keep\n-old value\n+new value\n tail\n", result.content);
    try testing.expectEqual(@as(usize, 6), result.rows.len);
    try testing.expectEqual(.match, result.rows[0].kind);
    try testing.expectEqual(@as(usize, "nowhere/x.txt:2".len), result.rows[0].location_end);
    try testing.expect(result.rows[1].declaration);
    const removed = result.rows[3];
    try testing.expect(removed.colors[0] & syntax.diff_removed != 0);
    // Paired with the line it changed: no whole-line tint.
    try testing.expect(removed.colors[0] & syntax.diff_whole == 0);
    try testing.expect(removed.colors[1] & syntax.diff_emph != 0);
    try testing.expect(removed.colors[5] & syntax.diff_emph == 0);
    try testing.expect(result.rows[4].colors[0] & syntax.diff_added != 0);
    try testing.expect(result.rows[2].colors[0] & (syntax.diff_added | syntax.diff_removed) == 0);
}

test "a hunk the file has moved since is found where it went, inside its declaration" {
    if (!syntax.supportsPath("a.zig")) return error.SkipZigTest;
    const p = try Pardes.init(testing.allocator, .{ .tty_only = true });
    defer p.deinit();
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    // Two lines more above it than the patch knows of.
    try tmp.dir.writeFile(testing.io, .{ .sub_path = "a.zig", .data = "// one\n// two\nconst S = struct {\n    fn f() void {\n        a();\n        b();\n    }\n};\n" });
    var buf: [std.fs.max_path_bytes]u8 = undefined;
    const dir = buf[0..try tmp.dir.realPath(testing.io, &buf)];
    const patch =
        \\--- a.zig
        \\+++ a.zig
        \\@@ -3,3 +3,3 @@ git's guess
        \\     fn f() void {
        \\-        c();
        \\+        a();
        \\         b();
        \\
    ;
    const result = try format(p, dir, patch);
    defer p.gpa.free(result.content);
    defer locations.freeRows(p.gpa, result.rows);
    try testing.expect(std.mem.indexOf(u8, result.content, "a.zig:3\n const S = struct {\na.zig:5 *\n") != null);
    try testing.expect(std.mem.indexOf(u8, result.content, "git's guess") == null);
}

test "a mailed patch keeps its headers, message and diffstat above its hunks" {
    const p = try Pardes.init(testing.allocator, .{ .tty_only = true });
    defer p.deinit();
    const patch =
        \\From 0123 Mon Sep 17 00:00:00 2001
        \\Subject: [PATCH] change x
        \\
        \\Why it changed.
        \\---
        \\ x.txt | 2 +-
        \\
        \\diff --git a/x.txt b/x.txt
        \\index 1..2 100644
        \\--- a/x.txt
        \\+++ b/x.txt
        \\@@ -1 +1 @@
        \\-a
        \\+b
        \\
    ;
    const result = try format(p, "/pardes-surely-missing-dir", patch);
    defer p.gpa.free(result.content);
    defer locations.freeRows(p.gpa, result.rows);
    try testing.expectEqualStrings("From 0123 Mon Sep 17 00:00:00 2001\nSubject: [PATCH] change x\n\nWhy it changed.\n---\n x.txt | 2 +-\n\nx.txt:1\n-a\n+b\n", result.content);
}

test "DiffLook hunks: a .patch looked at opens its +Diff; Diff goes to the text and back; DiffLook text opens the text" {
    const p = try Pardes.init(testing.allocator, .{ .tty_only = true });
    defer p.deinit();
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    try tmp.dir.writeFile(testing.io, .{ .sub_path = "x.txt", .data = "b\n" });
    try tmp.dir.writeFile(testing.io, .{ .sub_path = "c.patch", .data = "--- x.txt\n+++ x.txt\n@@ -1 +1 @@\n-a\n+b\n" });
    var buf: [std.fs.max_path_bytes]u8 = undefined;
    const dir = buf[0..try tmp.dir.realPath(testing.io, &buf)];
    const patch = try std.fs.path.join(testing.allocator, &.{ dir, "c.patch" });
    defer testing.allocator.free(patch);
    const hunks_path = try std.fs.path.join(testing.allocator, &.{ dir, "+Diff" });
    defer testing.allocator.free(hunks_path);
    const Count = struct {
        fn of(pp: *Pardes, path: []const u8) usize {
            var n: usize = 0;
            for (pp.panes) |slot| if (slot) |pane| if (pane.file) |f| {
                n += @intFromBool(std.mem.eql(u8, f.path, path));
            };
            return n;
        }
    };
    try testing.expectEqual(pardes.config.Runtime.DiffLook.hunks, p.settings.diff_look);
    pardes.look.lookAt(p, 0, patch);
    try testing.expectEqual(@as(usize, 1), Count.of(p, hunks_path));
    try testing.expectEqual(@as(usize, 0), Count.of(p, patch));
    const hid = p.active;
    try testing.expectEqualStrings(hunks_path, p.panes[hid].?.file.?.path);
    try testing.expectEqualStrings("x.txt:1\n-a\n+b\n", p.panes[hid].?.file.?.content);
    // Diff on it: the patch as text.
    try testing.expect(p.executeBuiltinLine(hid, "Diff"));
    try testing.expectEqual(@as(usize, 1), Count.of(p, patch));
    const raw = p.active;
    try testing.expectEqualStrings(patch, p.panes[raw].?.file.?.path);
    // Diff on the text: the +Diff again, refilled, not another.
    try testing.expect(p.executeBuiltinLine(raw, "Diff"));
    try testing.expectEqual(@as(usize, 1), Count.of(p, hunks_path));
    // DiffLook text: a look opens the text (here the pane already open).
    try testing.expect(p.executeBuiltinLine(0, "DiffLook text"));
    try p.removePane(raw, null);
    pardes.look.lookAt(p, 0, patch);
    try testing.expectEqual(@as(usize, 1), Count.of(p, patch));
}

test "a hunk edited since, beside siblings with its signature's tail, is found in its own function" {
    if (!syntax.supportsPath("a.rs")) return error.SkipZigTest;
    const p = try Pardes.init(testing.allocator, .{ .tty_only = true });
    defer p.deinit();
    var tmp = testing.tmpDir(.{});
    defer tmp.cleanup();
    // Three functions ending in one signature's tail; the patch is for the
    // third, which has moved down a line and had a line inside it edited.
    try tmp.dir.writeFile(testing.io, .{ .sub_path = "a.rs", .data =
        \\// moved
        \\fn one(
        \\    limit: usize,
        \\) -> u32 {
        \\    1
        \\}
        \\fn two(
        \\    limit: usize,
        \\) -> u32 {
        \\    2
        \\}
        \\fn three(
        \\    limit: usize,
        \\) -> u32 {
        \\    let guard = enter();
        \\    let a = 3;
        \\    let b = a + 1;
        \\    let c = b * 2; // edited since
        \\    c
        \\}
        \\
    });
    var buf: [std.fs.max_path_bytes]u8 = undefined;
    const dir = buf[0..try tmp.dir.realPath(testing.io, &buf)];
    const patch =
        \\--- a.rs
        \\+++ a.rs
        \\@@ -12,7 +12,8 @@ git's guess
        \\     limit: usize,
        \\ ) -> u32 {
        \\+    let guard = enter();
        \\     let a = 3;
        \\     let b = a + 1;
        \\     let c = b * 2;
        \\     c
        \\
    ;
    const result = try format(p, dir, patch);
    defer p.gpa.free(result.content);
    defer locations.freeRows(p.gpa, result.rows);
    try testing.expect(std.mem.indexOf(u8, result.content, "a.rs:12\n fn three(\na.rs:15 *\n") != null);
}