From c9b9dad8469f5d654c31d688d7e2d93da8325f39 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 5 Nov 2026 12:14:09 -0300 Subject: text journal, a text replaced whole is swapped, not copied (the architect's 15.3): an edit that takes out most of a text and at least 64 KiB of it (Get, Edit's e, a Restore, a 9P > body write, a delete of everything) gives the old buffer to the journal by pointer (Text.Journal.swap, an Entry with swap set and its buffer's room, a derived field) where it copied what it took out, and puts the rest in a new buffer; its undo swaps the buffers back, a step that began with a swap (a > and the writes after it) folding into one swap the other way (Journal.fold), so neither the edit, its undo nor its redo copies the old text; the 64 MiB bound counts copied bytes only, and a text keeps two swaps: a third drops the steps before the older, said in the pane's message row ('undo keeps the last two texts replaced whole: the steps before them are gone'); tests: 'a text replaced whole keeps its old buffer for its undo, swapped back and forth, two at most' is new, and 'undo keeps its steps within a byte bound, the newest always' takes out middles under half the text, so what it bounds are copies Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_016Y9MNAtZenFv4weoMD3cge --- src/File.zig | 156 +++++++++++++++++++++++++++++++++++++++++++++++------------ src/Text.zig | 76 ++++++++++++++++++++++++++--- 2 files changed, 195 insertions(+), 37 deletions(-) (limited to 'src') diff --git a/src/File.zig b/src/File.zig index 4b73b311..89acd4d8 100644 --- a/src/File.zig +++ b/src/File.zig @@ -839,7 +839,7 @@ pub fn setContent(p: *Pardes, f: *State, new: []u8) void { /// caller made anyway, as the text's buffer. pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { const span = span_in orelse spanOf(f.content, new); - _ = edit(p, f, span.head, f.content.len - span.head - span.tail, new[span.head .. new.len - span.tail], new, true); + _ = edit(p, f, span.head, f.content.len - span.head - span.tail, new[span.head .. new.len - span.tail], new, true, null); } /// The one change a text takes: the `len` bytes at `off` replaced by @@ -847,7 +847,7 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { /// them, never a copy of the text. False with no memory for it, and /// nothing changed. pub fn replace(p: *Pardes, f: *State, off: usize, len: usize, bytes: []const u8) bool { - return edit(p, f, off, len, bytes, null, true); + return edit(p, f, off, len, bytes, null, true, null); } /// Whether `f`'s bytes must stay as they are, an edit putting a new buffer @@ -857,13 +857,20 @@ fn keepsBytes(p: *const Pardes, f: *const State) bool { return pardes.rollback.isEpoch(p.gpa) or pardes.memory.isPinned(f.content); } +/// A replacement that takes out at least this much, and most of the text, +/// keeps the old buffer for its undo (Text.Journal.swap) instead of copying +/// what it takes out. +const swap_min = 64 << 10; + /// `replace`, or with `whole` that text's new buffer, `bytes` its middle, /// taken as it is. Its room comes first, so an edit with no memory for it /// changes nothing; then what holds a place in the text moves through the /// edit (twins, other views, readers of its events, its line index, the /// journal when `journaled`: an undo's own edits are not), the bytes go in -/// and it is a new revision. -fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, whole: ?[]u8, journaled: bool) bool { +/// and it is a new revision. An edit that takes out most of the text puts +/// a new buffer in and gives the old to the journal whole (a swap); an +/// undo's swap back hands the buffer it replaces to `kept`. +fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, whole: ?[]u8, journaled: bool, kept: ?*[]u8) bool { const old_len = f.content.len; const new_len = old_len - len + bytes_in.len; const span: Span = .{ .head = off, .tail = old_len - off - len }; @@ -874,7 +881,8 @@ fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, who // text moves under them. const own = whole == null and @intFromPtr(bytes_in.ptr) < @intFromPtr(room.ptr) + room.len and @intFromPtr(bytes_in.ptr) + bytes_in.len > @intFromPtr(room.ptr); const bytes = if (own) p.scratch.allocator().dupe(u8, bytes_in) catch return false else bytes_in; - const keep = whole == null and keepsBytes(p, f); + const swapping = journaled and len >= swap_min and len * 2 >= old_len; + const keep = whole == null and (swapping or keepsBytes(p, f)); const fresh: ?[]u8 = whole orelse if (keep) copySpliced(p.gpa, f.content, off, len, bytes) catch return false else null; if (fresh == null) { grow(p.gpa, f, new_len) catch return false; @@ -915,19 +923,27 @@ fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, who if (f.mini) |*mini| mini.deinit(p.gpa); f.mini = null; if (f.line_starts.len > 0) shiftIndex(p.gpa, f, off, len, bytes, pardes.rollback.isEpoch(p.gpa)); - if (journaled) f.history.journal.record(p.gpa, f.content, off, len, bytes.len); + if (journaled and !swapping) f.history.journal.record(p.gpa, f.content, off, len, bytes.len); // ponytail: a whole-text hash per edit that keeps the saved length; a // rolling hash when that too matters. if (f.revision == f.saved_revision or f.saved_hash == null) { f.saved_hash = std.hash.Wyhash.hash(0, f.content); f.saved_len = f.content.len; } + var undo_gone = false; if (fresh) |new| { - // Raw: `free` overwrites a safe build's freed memory, a whole - // file's worth; and its digest word goes (src/walk.zig). - pardes.memory.freeRaw(p.gpa, textRoom(f)); + const old = textRoom(f); f.content = new[0..new_len]; f.cap = new.len; + if (kept) |k| { + k.* = old; + } else if (swapping) { + undo_gone = f.history.journal.swap(p.gpa, old, old_len, new_len); + } else { + // Raw: `free` overwrites a safe build's freed memory, a whole + // file's worth; and its digest word goes (src/walk.zig). + pardes.memory.freeRaw(p.gpa, old); + } } else { const buffer = textRoom(f); const tail = old_len - off - len; @@ -950,6 +966,9 @@ fn edit(p: *Pardes, f: *State, off: usize, len: usize, bytes_in: []const u8, who f.highlight_start = 0; f.syntax_dirty = true; if (f.pager) f.pager_diff = looksLikeDiff(f.content[0..@min(new_len, 64 * 1024)]); + if (undo_gone) for (p.panes, 0..) |slot, id| { + if (slot) |pane| if (pane.file) |*state| if (state == f) p.setMessage(id, "undo keeps the last two texts replaced whole: the steps before them are gone"); + }; for (twins[0..ntwins], 0..) |id, i| { const t = p.panes[id].?; const tf = &t.file.?; @@ -1330,8 +1349,7 @@ pub fn undoStep(p: *Pardes, pane: *Pane, back: bool) void { if (if (back) j.done == 0 else j.done == j.steps.items.len) return; const at = if (back) j.done - 1 else j.done; const now = placeOf(pane, f); - const step = j.steps.items[at]; - if (!turn(p, f, j.entries.items[step.first..][0..step.n], back)) return; + if (!turn(p, f, at, back)) return; const s = &j.steps.items[at]; if (back) { s.after = now; @@ -1345,20 +1363,36 @@ pub fn undoStep(p: *Pardes, pane: *Pane, back: bool) void { restoreSnap(pane, f, to); } -/// A step's entries turned round in `f`'s text: each one's bytes put back -/// and the bytes it had put in kept in its place, an undo's last first and -/// a redo's first first. One entry is turned in place, its bytes alone +/// Step `at`'s entries turned round in `f`'s text: each one's bytes put +/// back and the bytes it had put in kept in its place, an undo's last first +/// and a redo's first first. One entry is turned in place, its bytes alone /// moved; several in a copy of the text whose gap goes from one to the next /// (`Gap`), put in as one edit; none is an edit that changes nothing, as -/// the snapshot equal to the text was put in once. False with no memory, -/// nothing changed. -fn turn(p: *Pardes, f: *State, entries: []Text.Entry, back: bool) bool { +/// the snapshot equal to the text was put in once. A step that began by +/// replacing the text whole has kept its old buffer: that buffer goes back +/// in and the step becomes one swap the other way, holding the text it +/// ended on for its redo, and no byte moves. False with no memory, nothing +/// changed. +fn turn(p: *Pardes, f: *State, at: usize, back: bool) bool { const j = &f.history.journal; - if (entries.len == 0) return edit(p, f, f.content.len, 0, "", null, false); + const step = j.steps.items[at]; + const entries = j.entries.items[step.first..][0..step.n]; + if (entries.len == 0) return edit(p, f, f.content.len, 0, "", null, false, null); + if (entries[0].swap and (back or entries.len == 1)) { + const e = &entries[0]; + const now_len = f.content.len; + const back_len = e.removed.len; + const span = spanOf(f.content, e.removed); + var out: []u8 = undefined; + if (!edit(p, f, span.head, now_len - span.head - span.tail, e.removed[span.head .. back_len - span.tail], e.removed.ptr[0..@max(e.room, back_len)], false, &out)) return false; + j.fold(p.gpa, at); + e.* = .{ .off = 0, .removed = out[0..now_len], .ins = back_len, .swap = true, .room = out.len }; + return true; + } if (entries.len == 1) { const e = &entries[0]; const put = pardes.memory.dupeUnfilled(p.gpa, f.content[e.off..][0..e.ins]) catch return false; - if (!edit(p, f, e.off, e.ins, e.removed, null, false)) { + if (!edit(p, f, e.off, e.ins, e.removed, null, false, null)) { pardes.memory.freeRaw(p.gpa, put); return false; } @@ -1388,16 +1422,16 @@ fn turn(p: *Pardes, f: *State, entries: []Text.Entry, back: bool) bool { } const new = gap.whole(); const span = spanOf(f.content, new); - if (!edit(p, f, span.head, f.content.len - span.head - span.tail, new[span.head .. new.len - span.tail], gap.buf, false)) { + if (!edit(p, f, span.head, f.content.len - span.head - span.tail, new[span.head .. new.len - span.tail], gap.buf, false, null)) { for (puts) |put| pardes.memory.freeRaw(p.gpa, put); pardes.memory.freeRaw(p.gpa, gap.buf); return false; } for (entries, puts) |*e, put| { - j.bytes = j.bytes - e.removed.len + put.len; - e.ins = e.removed.len; - pardes.memory.freeRaw(p.gpa, e.removed); - e.removed = put; + const was = e.*; + e.* = .{ .off = was.off, .removed = put, .ins = was.removed.len }; + j.bytes = j.bytes - Text.Journal.held(was) + Text.Journal.held(e.*); + Text.Journal.free(p.gpa, was); } return true; } @@ -2380,32 +2414,94 @@ test "undo and redo walk back and forth through every step of random edits, join } } -test "undo keeps its steps within a byte bound, the newest always" { +test "a text replaced whole keeps its old buffer for its undo, swapped back and forth, two at most" { const gpa = std.testing.allocator; const p = try Pardes.init(gpa, .{ .tty_only = true, .cols = 80, .rows = 24 }); defer p.deinit(); const pane = try p.setTestFile(""); const f = &pane.file.?; + const j = &f.history.journal; + var texts: [5][]u8 = undefined; + for (&texts, 0..) |*t, i| { + t.* = try gpa.alloc(u8, swap_min + 1000 * i); + @memset(t.*, 'a' + @as(u8, @intCast(i))); + } + defer for (texts) |t| gpa.free(t); + setContent(p, f, try gpa.dupe(u8, texts[0])); + const first = f.content.ptr; + pushUndo(p, pane); + setContent(p, f, try gpa.dupe(u8, texts[1])); + // The old buffer itself, kept: no byte of it copied, none counted. + const e = j.entries.items[j.entries.items.len - 1]; + try std.testing.expect(e.swap and e.removed.ptr == first); + try std.testing.expectEqual(@as(usize, @sizeOf(Text.Entry)), j.bytes); + const second = f.content.ptr; + undoStep(p, pane, true); + try std.testing.expect(f.content.ptr == first); + try std.testing.expectEqualStrings(texts[0], f.content); + undoStep(p, pane, false); + try std.testing.expect(f.content.ptr == second); + try std.testing.expectEqualStrings(texts[1], f.content); + // A third and a fourth: two swaps kept, the steps before them gone, said. + for (texts[2..4]) |t| { + pushUndo(p, pane); + setContent(p, f, try gpa.dupe(u8, t)); + } + try std.testing.expectEqual(@as(usize, 2), j.done); + try std.testing.expect(std.mem.indexOf(u8, pane.msg[0..pane.msg_len], "undo keeps the last two texts replaced whole") != null); + undoStep(p, pane, true); + undoStep(p, pane, true); + try std.testing.expectEqualStrings(texts[1], f.content); + undoStep(p, pane, true); + try std.testing.expectEqualStrings(texts[1], f.content); + // A body emptied and written again on one open (a shell's >): its undo + // swaps the old text back and folds the step into one swap the other way. + pushUndo(p, pane); + try std.testing.expect(replace(p, f, 0, f.content.len, "")); + try std.testing.expect(replace(p, f, 0, 0, "fresh\n")); + undoStep(p, pane, true); + try std.testing.expectEqualStrings(texts[1], f.content); + try std.testing.expectEqual(@as(usize, 1), j.steps.items[j.done].n); + undoStep(p, pane, false); + try std.testing.expectEqualStrings("fresh\n", f.content); + undoStep(p, pane, true); + try std.testing.expectEqualStrings(texts[1], f.content); +} + +test "undo keeps its steps within a byte bound, the newest always" { + const gpa = std.testing.allocator; + const p = try Pardes.init(gpa, .{ .tty_only = true, .cols = 80, .rows = 24 }); + defer p.deinit(); const step = limits.undo_bytes / 4 + 1; + // Each edit takes out the middle, under half the text: a copy each, not + // a swap of the whole. + const base = try gpa.alloc(u8, 2 * step + 1); + defer gpa.free(base); + @memset(base, 'z'); + const pane = try p.setTestFile(base); + const f = &pane.file.?; const text = try gpa.alloc(u8, step); defer gpa.free(text); for (0..8) |i| { @memset(text, 'a' + @as(u8, @intCast(i))); pushUndo(p, pane); - setContent(p, f, try gpa.dupe(u8, text)); + try std.testing.expect(replace(p, f, step / 2, step, text)); } pushUndo(p, pane); const j = &f.history.journal; try std.testing.expect(j.done > 0 and j.done < 8); try std.testing.expect(j.bytes <= limits.undo_bytes + step + @sizeOf(Text.Entry)); var sum: usize = 0; - for (j.entries.items) |e| sum += e.removed.len + @sizeOf(Text.Entry); + for (j.entries.items) |e| { + try std.testing.expect(!e.swap); + sum += Text.Journal.held(e); + } try std.testing.expectEqual(sum, j.bytes); undoStep(p, pane, true); - try std.testing.expectEqualStrings(text[0..1], f.content[0..1]); - // Back as far as the bound kept: each step's text whole again. + try std.testing.expectEqual(text[0], f.content[step / 2]); + // Back as far as the bound kept: each step's middle whole again. while (j.done > 0) { undoStep(p, pane, true); - try std.testing.expect(std.mem.allEqual(u8, f.content, f.content[0])); + try std.testing.expect(std.mem.allEqual(u8, f.content[step / 2 ..][0..step], f.content[step / 2])); } } diff --git a/src/Text.zig b/src/Text.zig index 1e419732..6d0e28c9 100644 --- a/src/Text.zig +++ b/src/Text.zig @@ -703,10 +703,16 @@ pub fn clampCursor(t: *Text, text: []const u8, row0: i32) void { pub const Entry = struct { /// Never written once made: a new one takes its place and the old is /// freed raw (a replica's rollback copy pins it, a digest hashes it once). - pub const replica = .{ .blob = .{"removed"} }; + pub const replica = .{ .blob = .{"removed"}, .derived = .{"room"} }; off: usize, removed: []u8, ins: usize, + /// A text replaced whole (Get, Edit's e, a Restore, a 9P > body write): + /// `removed` is the text as it was, its own buffer kept by pointer, not + /// a copy (`Journal.swap`), and an undo swaps the buffers back. + swap: bool = false, + /// The bytes `removed`'s buffer has room for (0: as many as it holds). + room: usize = 0, }; /// Where a text was at an undo step's edge: its cursor and selection, and @@ -745,7 +751,7 @@ pub const Journal = struct { bytes: usize = 0, pub fn deinit(j: *Journal, gpa: std.mem.Allocator) void { - for (j.entries.items) |e| memory.freeRaw(gpa, e.removed); + for (j.entries.items) |e| free(gpa, e); j.entries.deinit(gpa); j.steps.deinit(gpa); j.* = .{}; @@ -779,7 +785,7 @@ pub const Journal = struct { j.dropRedo(gpa); if (j.done == 0) return; const top = &j.steps.items[j.done - 1]; - if (top.n > 0) { + if (top.n > 0 and !j.entries.items[j.entries.items.len - 1].swap) { const last = &j.entries.items[j.entries.items.len - 1]; if (off >= last.off and off + len <= last.off + last.ins) { last.ins = last.ins - len + ins; @@ -818,6 +824,37 @@ pub const Journal = struct { j.bound(gpa); } + /// A text replaced whole, its old buffer `room` (holding `len` bytes) + /// kept in the last step by pointer where `record` would copy it, so + /// neither the edit nor its undo moves a byte; counted in the bound in + /// bytes by its entry alone. Two are kept a text: a third drops the + /// oldest steps until two are left, and answers true, that the undo + /// before them is gone. With no step to go in it is freed. + pub fn swap(j: *Journal, gpa: std.mem.Allocator, room: []u8, len: usize, ins: usize) bool { + j.dropRedo(gpa); + const kept: Entry = .{ .off = 0, .removed = room[0..len], .ins = ins, .swap = true, .room = room.len }; + if (j.done == 0) { + free(gpa, kept); + return false; + } + j.entries.append(gpa, kept) catch { + free(gpa, kept); + j.deinit(gpa); + return false; + }; + j.steps.items[j.done - 1].n += 1; + j.bytes += @sizeOf(Entry); + var dropped = false; + while (j.done > 1) { + var swaps: usize = 0; + for (j.entries.items) |e| swaps += @intFromBool(e.swap); + if (swaps <= 2) break; + j.dropOldest(gpa); + dropped = true; + } + return dropped; + } + /// The oldest steps dropped while over the bound in bytes, the last kept. fn bound(j: *Journal, gpa: std.mem.Allocator) void { while (j.bytes > memory.limits.undo_bytes and j.done > 1) j.dropOldest(gpa); @@ -827,8 +864,8 @@ pub const Journal = struct { if (j.done == j.steps.items.len) return; const first = j.steps.items[j.done].first; for (j.entries.items[first..]) |e| { - j.bytes -= e.removed.len + @sizeOf(Entry); - memory.freeRaw(gpa, e.removed); + j.bytes -= held(e); + free(gpa, e); } j.entries.shrinkRetainingCapacity(first); j.steps.shrinkRetainingCapacity(j.done); @@ -837,8 +874,8 @@ pub const Journal = struct { fn dropOldest(j: *Journal, gpa: std.mem.Allocator) void { const n = j.steps.items[0].n; for (j.entries.items[0..n]) |e| { - j.bytes -= e.removed.len + @sizeOf(Entry); - memory.freeRaw(gpa, e.removed); + j.bytes -= held(e); + free(gpa, e); } const rest = j.entries.items.len - n; @memmove(j.entries.items[0..rest], j.entries.items[n..]); @@ -847,6 +884,31 @@ pub const Journal = struct { for (j.steps.items) |*s| s.first -= n; j.done -= 1; } + + /// Step `at` made one entry, its first: the rest freed and gone (`turn` + /// swapped the whole text back, and its first holds what they made). + pub fn fold(j: *Journal, gpa: std.mem.Allocator, at: usize) void { + const folded = &j.steps.items[at]; + if (folded.n < 2) return; + const rest = j.entries.items[folded.first + 1 ..][0 .. folded.n - 1]; + for (rest) |e| { + j.bytes -= held(e); + free(gpa, e); + } + j.entries.replaceRangeAssumeCapacity(folded.first + 1, rest.len, &.{}); + for (j.steps.items[at + 1 ..]) |*s| s.first -= rest.len; + folded.n = 1; + } + + /// What an entry counts in the bound: its copied bytes and its own size. + pub fn held(e: Entry) usize { + return @sizeOf(Entry) + if (e.swap) 0 else e.removed.len; + } + + /// An entry's bytes freed, a swap's whole buffer. + pub fn free(gpa: std.mem.Allocator, e: Entry) void { + memory.freeRaw(gpa, e.removed.ptr[0..@max(e.room, e.removed.len)]); + } }; /// Whether undoing `entries` gives `text` back as it is. Only the stretch -- cgit v1.3