From d815a5cc854b3cd14a89f401565db212c3dc9d88 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 5 Nov 2026 11:26:35 -0300 Subject: text journal, the ring and undo over it: a file's undo is the journal of its edits (Text.Journal: entries of an offset, the bytes taken out and the count put in, grouped in steps between marks, each step with the place it began at and the place it was undone from), bounded at 256 steps or 64 MiB, the newest kept; pushUndo marks a step (none when the last changed nothing, as a snapshot equal to the text was none) and every edit goes into the last step, joined to its last entry when they touch (typing on, backspace over it, a write going on where the last ended); undo and redo turn a step's entries round, one in place, several in a copy whose gap moves from one to the next (File.Gap), one edit and one revision as the snapshot's was; the snapshots go (File.Snapshot, the undo and redo arrays and their copies of the whole text at every step); the replica's copy pins an entry's bytes (Entry.removed, a blob) as it pinned a snapshot's; tests: 'undo keeps its steps within a byte bound, the newest always' reads the journal, 'file history owns bounded snapshot storage without per-edit bookkeeping allocations' becomes 'file history keeps its last undo_max steps, and an undo or redo with no memory changes nothing', the far join's blob test makes its two blobs beside the text with a delete and a yank (its history held whole texts before), and the counts of steps read history.journal.done Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_016Y9MNAtZenFv4weoMD3cge --- src/Text.zig | 183 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 183 insertions(+) (limited to 'src/Text.zig') diff --git a/src/Text.zig b/src/Text.zig index 5e36467f..1e419732 100644 --- a/src/Text.zig +++ b/src/Text.zig @@ -694,6 +694,189 @@ pub fn clampCursor(t: *Text, text: []const u8, row0: i32) void { t.show(); } +// ---- undo: the edits a text took, as a journal ---- + +/// One edit as an undo takes it back: at `off`, the bytes `removed` were +/// taken out and `ins` bytes put in. An undo turns it round (keeping the +/// bytes it had put in, and the count of those it took out), so a redo is +/// the same move again. +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"} }; + off: usize, + removed: []u8, + ins: usize, +}; + +/// Where a text was at an undo step's edge: its cursor and selection, and +/// for a file its name's generation and whether, and as what, it was saved +/// (File.restoreName), as acme's undo puts the name back with the text. +pub const Place = struct { + cur_row: i32 = 0, + cur_col: i32 = 0, + vsel: CharSel = .{}, + gen: u32 = 0, + clean: bool = false, + saved_hash: ?u64 = null, + saved_len: ?usize = null, +}; + +/// One undo step, the entries made from one mark to the next +/// (`entries[first..][0..n]`), and the places at its edges: an undo goes +/// back to `before`, a redo to `after`, where it was undone from. +pub const Step = struct { + first: usize, + n: usize = 0, + before: Place, + after: Place = .{}, +}; + +/// A text's undo as the edits it took: `steps[0..done]` to undo, last +/// first, the rest to redo. A step is what one key did however many ranges +/// it edited, one open's writes, the writes between two `mark`s. Bounded at +/// limits.undo_max steps and limits.undo_bytes of what they hold, the +/// oldest step dropped first and the newest kept whatever its size. +pub const Journal = struct { + steps: std.ArrayList(Step) = .empty, + done: usize = 0, + entries: std.ArrayList(Entry) = .empty, + /// What the entries hold: the bytes they took out, and their own size. + bytes: usize = 0, + + pub fn deinit(j: *Journal, gpa: std.mem.Allocator) void { + for (j.entries.items) |e| memory.freeRaw(gpa, e.removed); + j.entries.deinit(gpa); + j.steps.deinit(gpa); + j.* = .{}; + } + + /// A step's edge, made before an edit: what follows is one step, which + /// an undo takes back to `place`. None when the last step changed + /// nothing, its edits undone giving `text` as it is: that step goes on, + /// its place kept, as a snapshot equal to the text was none. + pub fn mark(j: *Journal, gpa: std.mem.Allocator, text: []const u8, place: Place) void { + if (j.done > 0) { + const top = j.steps.items[j.done - 1]; + if (top.before.gen == place.gen and unchanged(gpa, j.entries.items[top.first..][0..top.n], text)) return; + } + j.dropRedo(gpa); + if (j.steps.items.len == memory.limits.undo_max) j.dropOldest(gpa); + j.steps.append(gpa, .{ .first = j.entries.items.len, .before = place }) catch return; + j.done = j.steps.items.len; + } + + /// The `len` bytes of `text` at `off` about to be replaced by `ins` + /// bytes, kept in the last step: in its last entry when they touch it + /// (typing on, deleting what was typed or what borders it, a write + /// going on where the last ended), else as an entry of its own. The + /// steps to redo go, made on the text before it; an edit with no step to + /// go in (before the first mark, or with every step undone) is kept by + /// none. On no memory the journal empties: its entries would no longer + /// be the text's. + pub fn record(j: *Journal, gpa: std.mem.Allocator, text: []const u8, off: usize, len: usize, ins: usize) void { + if (len == 0 and ins == 0) return; + j.dropRedo(gpa); + if (j.done == 0) return; + const top = &j.steps.items[j.done - 1]; + if (top.n > 0) { + 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; + if (last.ins == 0 and last.removed.len == 0) { + _ = j.entries.pop(); + top.n -= 1; + j.bytes -= @sizeOf(Entry); + } + return; + } + const before = off + len == last.off; + if (ins == 0 and (before or off == last.off + last.ins)) { + const more = memory.unfilled(gpa, last.removed.len + len) catch return j.deinit(gpa); + const taken = text[off..][0..len]; + if (before) { + @memcpy(more[0..len], taken); + @memcpy(more[len..], last.removed); + last.off = off; + } else { + @memcpy(more[0..last.removed.len], last.removed); + @memcpy(more[last.removed.len..], taken); + } + memory.freeRaw(gpa, last.removed); + last.removed = more; + j.bytes += len; + return j.bound(gpa); + } + } + const removed = memory.dupeUnfilled(gpa, text[off..][0..len]) catch return j.deinit(gpa); + j.entries.append(gpa, .{ .off = off, .removed = removed, .ins = ins }) catch { + memory.freeRaw(gpa, removed); + return j.deinit(gpa); + }; + top.n += 1; + j.bytes += len + @sizeOf(Entry); + j.bound(gpa); + } + + /// 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); + } + + fn dropRedo(j: *Journal, gpa: std.mem.Allocator) void { + 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.entries.shrinkRetainingCapacity(first); + j.steps.shrinkRetainingCapacity(j.done); + } + + 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); + } + const rest = j.entries.items.len - n; + @memmove(j.entries.items[0..rest], j.entries.items[n..]); + j.entries.shrinkRetainingCapacity(rest); + _ = j.steps.orderedRemove(0); + for (j.steps.items) |*s| s.first -= n; + j.done -= 1; + } +}; + +/// Whether undoing `entries` gives `text` back as it is. Only the stretch +/// they fell in is undone, in a copy: before their lowest offset nothing +/// changed, nor after the furthest end any reached. +fn unchanged(gpa: std.mem.Allocator, entries: []const Entry, text: []const u8) bool { + if (entries.len == 0) return true; + var grown: isize = 0; + for (entries) |e| grown += @as(isize, @intCast(e.ins)) - @as(isize, @intCast(e.removed.len)); + if (grown != 0) return false; + if (entries.len == 1) return std.mem.eql(u8, text[entries[0].off..][0..entries[0].ins], entries[0].removed); + var lo: usize = std.math.maxInt(usize); + var hi: usize = 0; + for (entries) |e| { + if (hi > e.off) hi = if (hi >= e.off + e.removed.len) hi - e.removed.len + e.ins else e.off + e.ins; + lo = @min(lo, e.off); + hi = @max(hi, e.off + e.ins); + } + var window: std.ArrayList(u8) = .empty; + defer window.deinit(gpa); + window.appendSlice(gpa, text[lo..hi]) catch return false; + var i = entries.len; + while (i > 0) { + i -= 1; + const e = entries[i]; + window.replaceRange(gpa, e.off - lo, e.ins, e.removed) catch return false; + } + return std.mem.eql(u8, window.items, text[lo..hi]); +} + fn pushHistory(gpa: std.mem.Allocator, slots: []terminal.Snapshot, len: *usize, value: terminal.Snapshot) void { if (len.* == slots.len) { if (slots[0].ovl) |overlay| gpa.free(overlay.text); -- cgit v1.3