xonecas.io
79113
Ma

mini-coding-agent / files

mini-coding-agent / src / diff.zig

6.0 KB
1const std = @import("std");
2
3const context = 3;
4const max_trace_bytes = 64 << 20;
5
6const Line = struct {
7    p: []const u8,
8    nl: bool,
9};
10
11const OpKind = enum { eq, del, ins };
12const Op = struct { kind: OpKind, line: Line };
13
14fn splitLines(a: std.mem.Allocator, text: []const u8) ![]Line {
15    var out: std.ArrayList(Line) = .empty;
16    var i: usize = 0;
17    while (i < text.len) {
18        const start = i;
19        while (i < text.len and text[i] != '\n') i += 1;
20        try out.append(a, .{ .p = text[start..i], .nl = i < text.len });
21        if (i < text.len) i += 1;
22    }
23    return out.toOwnedSlice(a);
24}
25
26fn lineEq(x: Line, y: Line) bool {
27    return x.nl == y.nl and x.p.len == y.p.len and std.mem.eql(u8, x.p, y.p);
28}
29
30fn myers(a: std.mem.Allocator, la: []const Line, lb: []const Line) ![]Op {
31    const n = la.len;
32    const m = lb.len;
33    var ops: std.ArrayList(Op) = .empty;
34    try ops.ensureTotalCapacity(a, n + m);
35
36    if (n == 0) {
37        for (lb) |l| ops.appendAssumeCapacity(.{ .kind = .ins, .line = l });
38        return ops.toOwnedSlice(a);
39    }
40    if (m == 0) {
41        for (la) |l| ops.appendAssumeCapacity(.{ .kind = .del, .line = l });
42        return ops.toOwnedSlice(a);
43    }
44
45    const max: usize = n + m;
46    const vsize = 2 * max + 3;
47    const offset: i64 = @intCast(max + 1);
48    const v = try a.alloc(i64, vsize);
49    @memset(v, 0);
50    v[@intCast(offset + 1)] = 0;
51
52    var trace: std.ArrayList([]i64) = .empty;
53    var trace_bytes: usize = 0;
54    var found_d: ?usize = null;
55
56    var d: usize = 0;
57    while (d <= max) : (d += 1) {
58        if (trace_bytes + vsize * @sizeOf(i64) > max_trace_bytes) break;
59        try trace.append(a, try a.dupe(i64, v));
60        trace_bytes += vsize * @sizeOf(i64);
61
62        const di: i64 = @intCast(d);
63        var k: i64 = -di;
64        while (k <= di) : (k += 2) {
65            const im: usize = @intCast(offset + k - 1);
66            const ip: usize = @intCast(offset + k + 1);
67            var x: i64 = if (k == -di or (k != di and v[im] < v[ip]))
68                v[ip]
69            else
70                v[im] + 1;
71            var y: i64 = x - k;
72            while (x < @as(i64, @intCast(n)) and y < @as(i64, @intCast(m)) and
73                lineEq(la[@intCast(x)], lb[@intCast(y)]))
74            {
75                x += 1;
76                y += 1;
77            }
78            v[@intCast(offset + k)] = x;
79            if (x >= @as(i64, @intCast(n)) and y >= @as(i64, @intCast(m))) {
80                found_d = d;
81                break;
82            }
83        }
84        if (found_d != null) break;
85    }
86
87    if (found_d == null) {
88        for (la) |l| try ops.append(a, .{ .kind = .del, .line = l });
89        for (lb) |l| try ops.append(a, .{ .kind = .ins, .line = l });
90        return ops.toOwnedSlice(a);
91    }
92
93    var x: i64 = @intCast(n);
94    var y: i64 = @intCast(m);
95    var dd: i64 = @intCast(found_d.?);
96    while (dd >= 0) : (dd -= 1) {
97        const vt = trace.items[@intCast(dd)];
98        const k = x - y;
99        const im: usize = @intCast(offset + k - 1);
100        const ip: usize = @intCast(offset + k + 1);
101        const prev_k: i64 = if (k == -dd or (k != dd and vt[im] < vt[ip])) k + 1 else k - 1;
102        const prev_x = vt[@intCast(offset + prev_k)];
103        const prev_y = prev_x - prev_k;
104        while (x > prev_x and y > prev_y) {
105            try ops.append(a, .{ .kind = .eq, .line = la[@intCast(x - 1)] });
106            x -= 1;
107            y -= 1;
108        }
109        if (dd > 0) {
110            if (x == prev_x) {
111                try ops.append(a, .{ .kind = .ins, .line = lb[@intCast(y - 1)] });
112                y -= 1;
113            } else {
114                try ops.append(a, .{ .kind = .del, .line = la[@intCast(x - 1)] });
115                x -= 1;
116            }
117        }
118    }
119
120    std.mem.reverse(Op, ops.items);
121    return ops.toOwnedSlice(a);
122}
123
124fn addRange(w: *std.Io.Writer, start: usize, count: usize) !void {
125    switch (count) {
126        0 => try w.print("{d},0", .{start - 1}),
127        1 => try w.print("{d}", .{start}),
128        else => try w.print("{d},{d}", .{ start, count }),
129    }
130}
131
132pub fn unified(a: std.mem.Allocator, before: []const u8, after: []const u8) ![]u8 {
133    var arena = std.heap.ArenaAllocator.init(a);
134    defer arena.deinit();
135    const tmp = arena.allocator();
136
137    const la = try splitLines(tmp, before);
138    const lb = try splitLines(tmp, after);
139    const ops = try myers(tmp, la, lb);
140
141    const opref = try tmp.alloc(usize, ops.len + 1);
142    const npref = try tmp.alloc(usize, ops.len + 1);
143    opref[0] = 0;
144    npref[0] = 0;
145    for (ops, 0..) |op, i| {
146        opref[i + 1] = opref[i] + @intFromBool(op.kind != .ins);
147        npref[i + 1] = npref[i] + @intFromBool(op.kind != .del);
148    }
149
150    var out: std.Io.Writer.Allocating = .init(a);
151    const w = &out.writer;
152
153    var i: usize = 0;
154    while (i < ops.len) {
155        while (i < ops.len and ops[i].kind == .eq) i += 1;
156        if (i >= ops.len) break;
157        const block_start = i;
158        var last = i;
159        while (last < ops.len and ops[last].kind != .eq) last += 1;
160        while (true) {
161            var g = last;
162            while (g < ops.len and ops[g].kind == .eq) g += 1;
163            if (g >= ops.len) break;
164            if (g - last > 2 * context) break;
165            var b2 = g;
166            while (b2 < ops.len and ops[b2].kind != .eq) b2 += 1;
167            last = b2;
168        }
169        const hs = if (block_start >= context) block_start - context else 0;
170        const he = if (last + context <= ops.len) last + context else ops.len;
171
172        try w.writeAll("@@ -");
173        try addRange(w, opref[hs] + 1, opref[he] - opref[hs]);
174        try w.writeAll(" +");
175        try addRange(w, npref[hs] + 1, npref[he] - npref[hs]);
176        try w.writeAll(" @@\n");
177
178        for (ops[hs..he]) |op| {
179            const prefix: u8 = switch (op.kind) {
180                .del => '-',
181                .ins => '+',
182                .eq => ' ',
183            };
184            try w.writeByte(prefix);
185            try w.writeAll(op.line.p);
186            try w.writeByte('\n');
187            if (!op.line.nl) try w.writeAll("\\ No newline at end of file\n");
188        }
189        i = he;
190    }
191    return out.written();
192}