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}