path: root/src/diff.zig

//! A unified diff (`git diff`, `diff -u`), read a line at a time: which
//! file each section is about, what each line is, and where a hunk line
//! stands in the old and the new file. The syntax painter (syntax.zig
//! highlightDiff) and a look on a diff line (look.zig) both walk it.
//!
//! A hunk's extent comes from the counts in its `@@` header, as patch
//! reads it, so a removed line that itself starts `--` (`--- x`) is not
//! taken for a file header.
const std = @import("std");

pub const Kind = enum {
    /// Anything outside a file header and a hunk: a commit message,
    /// `Only in ...`, a mail's headers.
    other,
    /// `diff ...`, `index ...`, `new file mode ...`, `rename from ...`,
    /// `Binary files ... differ`: said of the section, naming no line.
    meta,
    /// `--- <old path>`
    old_path,
    /// `+++ <new path>`
    new_path,
    /// `@@ -a,b +c,d @@`
    hunk,
    context,
    added,
    removed,
    /// `\ No newline at end of file`
    no_newline,
};

/// One line, walked.
pub const Line = struct {
    kind: Kind,
    /// Where it is in the old and the new file, from 1. A hunk header has
    /// its first lines; a removed line the new line now standing where it
    /// was (the one after it); an added line the old line after it.
    old: usize = 0,
    new: usize = 0,
};

pub const Walk = struct {
    /// The section's paths, as written, borrowed from the lines walked:
    /// `a/` and `b/` kept, timestamps cut.
    old_path: []const u8 = "",
    new_path: []const u8 = "",
    /// `diff --git a/x b/y`'s b side, for a section with no `+++` yet
    /// (a mode change, a rename, a binary file).
    git_path: []const u8 = "",
    old_left: usize = 0,
    new_left: usize = 0,
    old_at: usize = 0,
    new_at: usize = 0,
    /// The hunk's header numbers, which a look past its end clamps to.
    new_start: usize = 0,
    new_count: usize = 0,
    /// Rows a terminal wrapped: inside a hunk, a row that starts with no
    /// prefix at all continues the line above instead of ending the hunk.
    continued_rows: bool = false,
    last: Kind = .other,

    pub fn inHunk(w: *const Walk) bool {
        return w.old_left > 0 or w.new_left > 0;
    }

    /// The file the section is about: the new one, else (deleted) the old
    /// one, else what its `diff --git` line names.
    pub fn path(w: *const Walk) []const u8 {
        if (w.new_path.len > 0 and !isDevNull(w.new_path)) return w.new_path;
        if (w.old_path.len > 0 and !isDevNull(w.old_path)) return w.old_path;
        return w.git_path;
    }

    /// Whether the section deletes its file (`+++ /dev/null`).
    pub fn deleted(w: *const Walk) bool {
        return isDevNull(w.new_path);
    }

    pub fn step(w: *Walk, line_raw: []const u8) Line {
        const line = std.mem.trimEnd(u8, line_raw, "\r");
        const got = w.stepInner(line);
        w.last = got.kind;
        return got;
    }

    fn stepInner(w: *Walk, line: []const u8) Line {
        if (w.inHunk()) {
            // A blank context line, its space stripped by a mailer or an
            // editor, is still context.
            const c: u8 = if (line.len == 0) ' ' else line[0];
            switch (c) {
                ' ' => if (w.old_left > 0 and w.new_left > 0) {
                    const at: Line = .{ .kind = .context, .old = w.old_at, .new = w.new_at };
                    w.old_left -= 1;
                    w.new_left -= 1;
                    w.old_at += 1;
                    w.new_at += 1;
                    return at;
                },
                '-' => if (w.old_left > 0) {
                    const at: Line = .{ .kind = .removed, .old = w.old_at, .new = w.new_at };
                    w.old_left -= 1;
                    w.old_at += 1;
                    return at;
                },
                '+' => if (w.new_left > 0) {
                    const at: Line = .{ .kind = .added, .old = w.old_at, .new = w.new_at };
                    w.new_left -= 1;
                    w.new_at += 1;
                    return at;
                },
                '\\' => return .{ .kind = .no_newline, .old = w.old_at, .new = w.new_at },
                else => if (w.continued_rows and w.last != .hunk and w.last != .other)
                    return .{ .kind = w.last, .old = w.old_at, .new = w.new_at },
            }
            // Counts run out, or a line no hunk has: the hunk was cut short.
            w.old_left = 0;
            w.new_left = 0;
        }
        if (line.len > 0 and line[0] == '\\' and w.last != .other and w.last != .meta)
            return .{ .kind = .no_newline, .old = w.old_at, .new = w.new_at };
        if (std.mem.startsWith(u8, line, "diff ")) {
            w.* = .{ .continued_rows = w.continued_rows };
            w.git_path = gitPath(line);
            return .{ .kind = .meta };
        }
        if (std.mem.startsWith(u8, line, "--- ")) {
            // A second `---` with no `+++` between starts another section
            // (plain `diff -u` output has no `diff` line of its own).
            w.* = .{ .continued_rows = w.continued_rows, .git_path = w.git_path };
            w.old_path = cutPath(line[4..]);
            return .{ .kind = .old_path };
        }
        if (std.mem.startsWith(u8, line, "+++ ")) {
            w.new_path = cutPath(line[4..]);
            return .{ .kind = .new_path };
        }
        if (parseHunk(line)) |h| {
            w.old_left = h.old_count;
            w.new_left = h.new_count;
            w.old_at = h.old_start;
            w.new_at = h.new_start;
            w.new_start = h.new_start;
            w.new_count = h.new_count;
            return .{ .kind = .hunk, .old = h.old_start, .new = h.new_start };
        }
        for (meta_words) |word| if (std.mem.startsWith(u8, line, word)) return .{ .kind = .meta };
        return .{ .kind = .other };
    }
};

const meta_words = [_][]const u8{
    "index ",            "new file mode ", "deleted file mode ", "old mode ",   "new mode ",
    "similarity index ", "rename from ",   "rename to ",         "copy from ",  "copy to ",
    "Binary files ",     "dissimilarity ",
};

fn isDevNull(path: []const u8) bool {
    return std.mem.eql(u8, path, "/dev/null");
}

/// A `---`/`+++` path with what follows it cut: `diff -u`'s tab and
/// timestamp, and git's quotes round a name it had to escape.
fn cutPath(rest: []const u8) []const u8 {
    var name = rest[0 .. std.mem.indexOfScalar(u8, rest, '\t') orelse rest.len];
    name = std.mem.trimEnd(u8, name, " \r");
    if (name.len >= 2 and name[0] == '"' and name[name.len - 1] == '"') name = name[1 .. name.len - 1];
    return name;
}

/// `diff --git a/x b/y`: the b side. A name with a space in it is split at
/// the last ` b/`, which is right unless the old name has one too.
fn gitPath(line: []const u8) []const u8 {
    if (!std.mem.startsWith(u8, line, "diff --git ")) return "";
    const rest = line["diff --git ".len..];
    const at = std.mem.lastIndexOf(u8, rest, " b/") orelse return "";
    return std.mem.trimEnd(u8, rest[at + 1 ..], " \r");
}

pub const HunkHeader = struct { old_start: usize, old_count: usize, new_start: usize, new_count: usize };

/// `@@ -a[,b] +c[,d] @@ ...`, a count left out meaning one.
pub fn parseHunk(line: []const u8) ?HunkHeader {
    if (!std.mem.startsWith(u8, line, "@@ -")) return null;
    var at: usize = "@@ -".len;
    const old = range(line, &at) orelse return null;
    if (at + 1 >= line.len or line[at] != ' ' or line[at + 1] != '+') return null;
    at += 2;
    const new = range(line, &at) orelse return null;
    if (!std.mem.startsWith(u8, line[at..], " @@")) return null;
    return .{ .old_start = old[0], .old_count = old[1], .new_start = new[0], .new_count = new[1] };
}

fn range(line: []const u8, at: *usize) ?[2]usize {
    const start = number(line, at) orelse return null;
    if (at.* < line.len and line[at.*] == ',') {
        at.* += 1;
        return .{ start, number(line, at) orelse return null };
    }
    return .{ start, 1 };
}

fn number(line: []const u8, at: *usize) ?usize {
    const from = at.*;
    var n: usize = 0;
    while (at.* < line.len and std.ascii.isDigit(line[at.*])) : (at.* += 1)
        n = std.math.add(usize, std.math.mul(usize, n, 10) catch return null, line[at.*] - '0') catch return null;
    return if (at.* > from) n else null;
}

/// Where a walk that ends up at byte `pos` of `content` may safely start:
/// the start of the nearest `diff ` line before it (no hunk line starts
/// with a `d`), else the top.
pub fn anchorBefore(content: []const u8, pos: usize) usize {
    var end = @min(pos, content.len);
    while (end > 0) {
        const nl = std.mem.lastIndexOfScalar(u8, content[0..end], '\n') orelse break;
        if (std.mem.startsWith(u8, content[nl + 1 ..], "diff ") and nl + 1 <= pos) return nl + 1;
        end = nl;
    }
    return 0;
}

/// The same for a list of lines: the nearest `diff ` line at or above `row`.
pub fn anchorRow(lines: []const []const u8, row: usize) usize {
    var r = @min(row, lines.len);
    while (r > 0) {
        r -= 1;
        if (std.mem.startsWith(u8, lines[r], "diff ")) return r;
    }
    return 0;
}

/// Whether text a command printed is a diff: a `diff --git` line, or a
/// `--- ` line with a `+++ ` line under it, in its first rows (after
/// `git show`'s commit header, say).
pub fn looksLikeDiff(lines: []const []const u8) bool {
    const n = @min(lines.len, 200);
    for (lines[0..n], 0..) |line, i| {
        if (std.mem.startsWith(u8, line, "diff --git ")) return true;
        if (std.mem.startsWith(u8, line, "--- ") and i + 1 < lines.len and std.mem.startsWith(u8, lines[i + 1], "+++ ") and
            i + 2 < lines.len and parseHunk(lines[i + 2]) != null) return true;
    }
    return false;
}

/// A look on one line of a diff: the file and line it names.
pub const Target = struct {
    /// The line's own kind.
    kind: Kind,
    /// As written in the diff, `a/`/`b/` kept.
    path: []const u8,
    /// From 1; 0 for the file alone (a `---`/`+++` line).
    line: usize,
    /// The section deletes the file, and this is its old side.
    old_side: bool = false,
};

/// What a look at `lines[row]` opens, or null for a line that is no part
/// of a file section (a commit message, `index ...`). The whole line is
/// the look's: a click on a `+++`, `---` or `@@` marker is one on its path
/// or its numbers.
///
/// `diff --git a/x b/y` opens y, and `+++ y` opens y. `--- x` opens x,
/// unless the `+++` under it names another file (a rename, a new file,
/// `diff -u old/x new/x`): then that one, the old name being the one
/// likely gone.
///
/// A removed line opens the new file at the line now standing where it
/// was: the new line after it, or the hunk's last new line when it went
/// from the end of the file. In a section that deletes its file there is
/// no new file, so a removed or context line opens the old one at its old
/// line (it is there while the diff is not applied).
pub fn targetAt(lines: []const []const u8, row: usize, continued_rows: bool) ?Target {
    if (row >= lines.len) return null;
    var w: Walk = .{ .continued_rows = continued_rows };
    var r = anchorRow(lines, row);
    var got: Line = .{ .kind = .other };
    while (r <= row) : (r += 1) got = w.step(lines[r]);
    const line = std.mem.trimEnd(u8, lines[row], "\r");
    switch (got.kind) {
        .other, .meta, .no_newline => {
            // `diff --git a/x b/y`: the file, as its `+++` would.
            if (got.kind == .meta and std.mem.startsWith(u8, line, "diff ") and w.git_path.len > 0)
                return .{ .kind = got.kind, .path = w.git_path, .line = 0 };
            return null;
        },
        .old_path, .new_path => {
            const own = cutPath(line[4..]);
            // `---` names the old file, but the new one on the `+++` under
            // it wins when they differ: a new file (`--- /dev/null`), a
            // rename, `diff -u old/x new/x`. The old name is the one
            // likely gone.
            if (got.kind == .old_path and row + 1 < lines.len and std.mem.startsWith(u8, lines[row + 1], "+++ ")) {
                const new = cutPath(std.mem.trimEnd(u8, lines[row + 1], "\r")[4..]);
                if (!isDevNull(new) and (isDevNull(own) or !std.mem.eql(u8, stripSide(new), stripSide(own))))
                    return .{ .kind = got.kind, .path = new, .line = 0 };
            }
            if (!isDevNull(own)) return .{ .kind = got.kind, .path = own, .line = 0, .old_side = got.kind == .old_path and w.deleted() };
            if (w.path().len == 0) return null;
            return .{ .kind = got.kind, .path = w.path(), .line = 0, .old_side = w.deleted() };
        },
        .hunk => {
            if (w.path().len == 0) return null;
            if (w.deleted()) return .{ .kind = got.kind, .path = w.path(), .line = @max(1, got.old), .old_side = true };
            return .{ .kind = got.kind, .path = w.path(), .line = @max(1, got.new) };
        },
        .context, .added, .removed => {
            if (w.path().len == 0) return null;
            if (w.deleted()) return .{ .kind = got.kind, .path = w.path(), .line = @max(1, got.old), .old_side = true };
            var at = got.new;
            // Gone from the end of the file: nothing stands after it.
            if (got.kind == .removed and w.new_count > 0 and at >= w.new_start + w.new_count)
                at = w.new_start + w.new_count - 1;
            return .{ .kind = got.kind, .path = w.path(), .line = @max(1, at) };
        },
    }
}

/// `a/x` and `b/x` as git writes them: the name in the repository.
pub fn stripSide(path: []const u8) []const u8 {
    if (path.len > 2 and (path[0] == 'a' or path[0] == 'b') and path[1] == '/') return path[2..];
    return path;
}

// ---- tests ----

const testing = std.testing;

fn splitLines(comptime text: []const u8) [std.mem.count(u8, text, "\n")][]const u8 {
    @setEvalBranchQuota(100_000);
    var out: [std.mem.count(u8, text, "\n")][]const u8 = undefined;
    var it = std.mem.splitScalar(u8, text, '\n');
    for (&out) |*line| line.* = it.next().?;
    return out;
}

const git_diff =
    \\diff --git a/src/a.zig b/src/a.zig
    \\index 1111111..2222222 100644
    \\--- a/src/a.zig
    \\+++ b/src/a.zig
    \\@@ -10,4 +10,4 @@ pub fn main() void {
    \\ const a = 1;
    \\-const b = 2;
    \\+const b = 3;
    \\+const c = 4;
    \\ const d = 5;
    \\--- x
    \\@@ -40,2 +41,2 @@
    \\ keep();
    \\-gone();
    \\+added();
    \\diff --git a/old.py b/old.py
    \\deleted file mode 100644
    \\--- a/old.py
    \\+++ /dev/null
    \\@@ -1,2 +0,0 @@
    \\-def f():
    \\-    return 1
    \\
;

test "diff a walk follows the hunk counts, so a removed `--` line is no header" {
    const lines = splitLines(git_diff);
    var w: Walk = .{};
    var kinds: [lines.len]Kind = undefined;
    for (lines, 0..) |line, i| kinds[i] = w.step(line).kind;
    try testing.expectEqualSlices(Kind, &.{
        .meta,    .meta,    .old_path, .new_path, .hunk,
        .context, .removed, .added,    .added,    .context,
        .removed, .hunk,    .context,  .removed,  .added,
        .meta,    .meta,    .old_path, .new_path, .hunk,
        .removed, .removed,
    }, &kinds);
}

test "diff a look on each kind of line names the new file and its line" {
    const lines = splitLines(git_diff);
    const expect = struct {
        fn at(ls: []const []const u8, row: usize, path: []const u8, line: usize) !void {
            const t = targetAt(ls, row, false) orelse return error.NoTarget;
            try testing.expectEqualStrings(path, t.path);
            try testing.expectEqual(line, t.line);
        }
    };
    try expect.at(&lines, 0, "b/src/a.zig", 0); // diff --git
    try testing.expect(targetAt(&lines, 1, false) == null); // index
    try expect.at(&lines, 2, "a/src/a.zig", 0); // ---
    try expect.at(&lines, 3, "b/src/a.zig", 0); // +++
    try expect.at(&lines, 4, "b/src/a.zig", 10); // @@
    try expect.at(&lines, 5, "b/src/a.zig", 10); // context
    try expect.at(&lines, 6, "b/src/a.zig", 11); // removed: the line now there
    try expect.at(&lines, 7, "b/src/a.zig", 11); // added
    try expect.at(&lines, 8, "b/src/a.zig", 12);
    try expect.at(&lines, 9, "b/src/a.zig", 13);
    // `--- x` is a removed line, gone from past the hunk's new lines.
    try expect.at(&lines, 10, "b/src/a.zig", 13);
    try expect.at(&lines, 11, "b/src/a.zig", 41);
    try expect.at(&lines, 12, "b/src/a.zig", 41);
    try expect.at(&lines, 13, "b/src/a.zig", 42);
    try expect.at(&lines, 14, "b/src/a.zig", 42);
    // A removed line of a deleted file: its old line in the old file.
    const gone = targetAt(&lines, 21, false).?;
    try testing.expectEqualStrings("a/old.py", gone.path);
    try testing.expectEqual(@as(usize, 2), gone.line);
    try testing.expect(gone.old_side);
    try testing.expect(targetAt(&lines, 1, false) == null);
}

test "diff a removed line at the end of a file opens the hunk's last new line" {
    const lines = splitLines(
        \\--- a/f.c
        \\+++ b/f.c
        \\@@ -1,3 +1,2 @@
        \\ one
        \\ two
        \\-three
        \\
    );
    try testing.expectEqual(@as(usize, 2), targetAt(&lines, 5, false).?.line);
}

test "diff plain diff -u output: no a/ b/, timestamps after the names" {
    const lines = splitLines("--- old/x.zig\t2026-09-30 10:00:00.000000000 +0000\n" ++
        "+++ new/x.zig\t2026-09-30 11:00:00.000000000 +0000\n" ++
        "@@ -3 +3,2 @@\n" ++
        "-const a = 1;\n" ++
        "+const a = 2;\n" ++
        "+const b = 3;\n");
    try testing.expect(looksLikeDiff(&lines));
    const t = targetAt(&lines, 5, false).?;
    try testing.expectEqualStrings("new/x.zig", t.path);
    try testing.expectEqual(@as(usize, 4), t.line);
    // `--- old/x.zig` with `+++ new/x.zig` under it: the new file.
    try testing.expectEqualStrings("new/x.zig", targetAt(&lines, 0, false).?.path);
    try testing.expectEqualStrings("new/x.zig", stripSide("new/x.zig"));
    try testing.expectEqualStrings("x.zig", stripSide("b/x.zig"));
}

test "diff a --- line opens the new name when the +++ under it names another" {
    const lines = splitLines(
        \\diff --git a/old name.zig b/new name.zig
        \\similarity index 90%
        \\rename from old name.zig
        \\rename to new name.zig
        \\--- a/old name.zig
        \\+++ b/new name.zig
        \\@@ -1 +1 @@
        \\-a
        \\+b
        \\
    );
    try testing.expectEqualStrings("b/new name.zig", targetAt(&lines, 0, false).?.path);
    try testing.expectEqualStrings("b/new name.zig", targetAt(&lines, 4, false).?.path);
    try testing.expectEqualStrings("b/new name.zig", targetAt(&lines, 5, false).?.path);
    try testing.expect(targetAt(&lines, 2, false) == null);
}

test "diff a new file's --- /dev/null opens the file it makes" {
    const lines = splitLines(
        \\--- /dev/null
        \\+++ b/made.zig
        \\@@ -0,0 +1 @@
        \\+const x = 1;
        \\
    );
    try testing.expectEqualStrings("b/made.zig", targetAt(&lines, 0, false).?.path);
    try testing.expectEqual(@as(usize, 1), targetAt(&lines, 2, false).?.line);
    try testing.expectEqual(@as(usize, 1), targetAt(&lines, 3, false).?.line);
}

test "diff output is told from other text by its first rows" {
    const git = [_][]const u8{ "$ git diff", "diff --git a/x b/x", "index 1..2" };
    try testing.expect(looksLikeDiff(&git));
    const show = [_][]const u8{ "commit abc", "Author: a", "", "    msg", "", "diff --git a/x b/x" };
    try testing.expect(looksLikeDiff(&show));
    const prose = [_][]const u8{ "--- a heading", "+++ not a path", "text" };
    try testing.expect(!looksLikeDiff(&prose));
    const nothing = [_][]const u8{ "ls", "a.zig b.zig" };
    try testing.expect(!looksLikeDiff(&nothing));
}

test "diff hunk headers: counts left out are one, a broken one is none" {
    try testing.expectEqual(HunkHeader{ .old_start = 3, .old_count = 1, .new_start = 4, .new_count = 1 }, parseHunk("@@ -3 +4 @@").?);
    try testing.expectEqual(HunkHeader{ .old_start = 1, .old_count = 0, .new_start = 0, .new_count = 0 }, parseHunk("@@ -1,0 +0,0 @@ fn x").?);
    try testing.expect(parseHunk("@@ -a +1 @@") == null);
    try testing.expect(parseHunk("@@ -1 +1") == null);
    try testing.expect(parseHunk("@@@ -1 -1 +1 @@@") == null);
}

test "diff a terminal's wrapped row stays in its line" {
    const lines = [_][]const u8{ "--- a/x.c", "+++ b/x.c", "@@ -1,2 +1,2 @@", "+int a = 1; /* a long", "comment */", " int b;", "-int c;" };
    try testing.expectEqual(@as(usize, 2), targetAt(&lines, 5, true).?.line);
    var w: Walk = .{ .continued_rows = true };
    var last: Kind = .other;
    for (lines[0..5]) |line| last = w.step(line).kind;
    try testing.expectEqual(Kind.added, last);
}