summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-05 11:26:35 -0300
committerGabriel Schneider <[email protected]>2026-11-05 13:14:28 -0300
commitd815a5cc854b3cd14a89f401565db212c3dc9d88 (patch)
tree1335995520095445488d26dc030dd777db010fd9
parent8640107e29a940d50a5eef0dc7d12689a515d856 (diff)
downloadpardes-d815a5cc854b3cd14a89f401565db212c3dc9d88.tar.gz
pardes-d815a5cc854b3cd14a89f401565db212c3dc9d88.zip
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 <[email protected]> Claude-Session: https://claude.ai/code/session_016Y9MNAtZenFv4weoMD3cge
-rw-r--r--src/File.zig262
-rw-r--r--src/Pipe.zig14
-rw-r--r--src/Text.zig183
-rw-r--r--src/builtins.zig4
-rw-r--r--src/edit_cmd.zig4
-rw-r--r--src/fs.zig2
-rw-r--r--src/host_io.zig6
-rw-r--r--src/ninep/ctl.zig15
-rw-r--r--src/replica.zig3
-rw-r--r--test/panes.zig43
10 files changed, 389 insertions, 147 deletions
diff --git a/src/File.zig b/src/File.zig
index 7aac4cb9..92e5b210 100644
--- a/src/File.zig
+++ b/src/File.zig
@@ -27,33 +27,10 @@ const Text = panes.Text;
const SYNTAX_CONTEXT_AFTER_ROWS: usize = 2;
const long_paint: usize = 16 << 10;
-/// Content and primary selection at one file edit boundary. Keeping only the
-/// primary avoids putting Text.max_selections ranges in every history entry.
-pub const Snapshot = struct {
- pub const replica = .{ .blob = .{"content"} };
- content: []u8,
- cur_row: i32,
- cur_col: i32,
- vsel: Text.CharSel,
- /// The pane's name then, as History.gen counts its renames, and whether
- /// and as what the text was saved under it: an undo across a load into
- /// the pane under another name (Get file, Edit's e) puts the name back
- /// with the text, and the dirty state that went with them, as acme's
- /// undo does. No allocation a step: a name is kept once, at its rename.
- gen: u32 = 0,
- clean: bool = false,
- saved_hash: ?u64 = null,
- saved_len: ?usize = null,
-
- fn deinit(s: Snapshot, gpa: std.mem.Allocator) void {
- pardes.memory.freeRaw(gpa, s.content);
- }
-};
-
-/// The pane's text, place and name now, for an undo or redo step.
-fn snapshotOf(gpa: std.mem.Allocator, pane: *const Pane, f: *const State) ?Snapshot {
+/// Where the pane is in its text and what the text is saved as now: an
+/// undo step's edge (Text.Place), kept once, never a copy of the text.
+fn placeOf(pane: *const Pane, f: *const State) Text.Place {
return .{
- .content = pardes.memory.dupeUnfilled(gpa, f.content) catch return null,
.cur_row = pane.body.cur_row,
.cur_col = pane.body.cur_col,
.vsel = pane.body.vsel,
@@ -73,8 +50,9 @@ pub fn noteRenamed(gpa: std.mem.Allocator, history: *History, old: []u8) void {
}
/// After a step's text went in: if it was under another name, that name
-/// back, and the step's saved state with it (Get file, Edit's e).
-fn restoreName(p: *Pardes, pane: *Pane, f: *State, snap: Snapshot) void {
+/// back, and the step's saved state with it (Get file, Edit's e), as acme's
+/// undo puts them back with the text.
+fn restoreName(p: *Pardes, pane: *Pane, f: *State, snap: Text.Place) void {
const history = f.history;
if (snap.gen == history.gen) return;
// The latest name kept for that generation.
@@ -103,33 +81,24 @@ fn restoreName(p: *Pardes, pane: *Pane, f: *State, snap: Snapshot) void {
if (filesystem.localPath(path) != null) p.emit(.{ .watch = .{ .pane = @intCast(id), .on = true } });
}
+/// A file's undo, which its twins (Zerox) share: its edits as a journal
+/// (Text.Journal), and the names it had.
pub const History = struct {
- pub const replica = .{ .len = .{ .{ "undo", "undo_len" }, .{ "redo", "redo_len" } } };
- undo: [limits.undo_max]Snapshot = undefined,
- undo_len: usize = 0,
- redo: [limits.undo_max]Snapshot = undefined,
- redo_len: usize = 0,
- /// The text `undo` and `redo` hold, kept near limits.undo_bytes.
- bytes: usize = 0,
-
+ journal: Text.Journal = .{},
/// The names the file had, each with the rename generation it ended
- /// (Snapshot.gen), and the generation now.
+ /// (Text.Place.gen), and the generation now: no allocation a step, a
+ /// name is kept once, at its rename.
names: std.ArrayList(struct { gen: u32, path: []u8 }) = .empty,
gen: u32 = 0,
pub fn create(gpa: std.mem.Allocator) !*History {
const history = try gpa.create(History);
- history.undo_len = 0;
- history.redo_len = 0;
- history.bytes = 0;
- history.names = .empty;
- history.gen = 0;
+ history.* = .{};
return history;
}
pub fn destroy(history: *History, gpa: std.mem.Allocator) void {
- for (history.undo[0..history.undo_len]) |snap| snap.deinit(gpa);
- for (history.redo[0..history.redo_len]) |snap| snap.deinit(gpa);
+ history.journal.deinit(gpa);
for (history.names.items) |name| gpa.free(name.path);
history.names.deinit(gpa);
gpa.destroy(history);
@@ -870,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);
+ _ = edit(p, f, span.head, f.content.len - span.head - span.tail, new[span.head .. new.len - span.tail], new, true);
}
/// The one change a text takes: the `len` bytes at `off` replaced by
@@ -878,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);
+ return edit(p, f, off, len, bytes, null, true);
}
/// Whether `f`'s bytes must stay as they are, an edit putting a new buffer
@@ -891,9 +860,10 @@ fn keepsBytes(p: *const Pardes, f: *const State) bool {
/// `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
-/// 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) bool {
+/// 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 {
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 };
@@ -945,6 +915,7 @@ 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);
// 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) {
@@ -1328,7 +1299,7 @@ test "a pager's text is a diff when it holds a diff header or a unified hunk" {
try std.testing.expect(!looksLikeDiff("commit abc\nAuthor: x\n\n plain log\n"));
}
-pub fn restoreSnap(pane: *Pane, f: *State, snap: Snapshot) void {
+pub fn restoreSnap(pane: *Pane, f: *State, snap: Text.Place) void {
const n = nlines(pane.gpa, f);
const row: usize = @min(@as(usize, @intCast(@max(0, snap.cur_row))), n - 1);
const llen = modal.lineSlice(f.content, row).len;
@@ -1340,56 +1311,140 @@ pub fn restoreSnap(pane: *Pane, f: *State, snap: Snapshot) void {
pane.ensureCursorVisible();
}
-/// Bounded in steps and in bytes: the oldest go first, though the one
-/// pushed always stays.
-fn pushHistory(gpa: std.mem.Allocator, history: *History, slots: []Snapshot, len: *usize, snap: Snapshot) void {
- while (len.* > 0 and (len.* == slots.len or history.bytes + snap.content.len > limits.undo_bytes)) {
- history.bytes -= slots[0].content.len;
- slots[0].deinit(gpa);
- std.mem.copyForwards(Snapshot, slots[0 .. len.* - 1], slots[1..len.*]);
- len.* -= 1;
- }
- slots[len.*] = snap;
- len.* += 1;
- history.bytes += snap.content.len;
-}
-
+/// An undo step's edge, made before an edit (Text.Journal.mark): the edits
+/// after it are one step back to the pane's place now.
pub fn pushUndo(p: *Pardes, pane: *Pane) void {
const f = if (pane.file) |*file| file else return;
- const history = f.history;
- if (history.undo_len > 0) {
- const last = history.undo[history.undo_len - 1];
- if (std.mem.eql(u8, last.content, f.content) and last.gen == history.gen) return;
- }
- const snap = snapshotOf(p.gpa, pane, f) orelse return;
- for (history.redo[0..history.redo_len]) |item| {
- history.bytes -= item.content.len;
- item.deinit(p.gpa);
- }
- history.redo_len = 0;
- pushHistory(p.gpa, history, &history.undo, &history.undo_len, snap);
+ f.history.journal.mark(p.gpa, f.content, placeOf(pane, f));
}
-/// Undo (back) or redo one step: the text, its place and its name go back
-/// to the step's, and the text as it is goes on the other history.
+/// Undo (back) or redo one step: its edits turned round in the text, and the
+/// place and name it began at (or, redone, was undone from) back.
pub fn undoStep(p: *Pardes, pane: *Pane, back: bool) void {
const f = if (pane.file) |*file| file else return;
- const history = f.history;
- const from, const from_len, const to, const to_len = if (back)
- .{ &history.undo, &history.undo_len, &history.redo, &history.redo_len }
- else
- .{ &history.redo, &history.redo_len, &history.undo, &history.undo_len };
- if (from_len.* == 0) return;
- const current = snapshotOf(p.gpa, pane, f) orelse return;
- pushHistory(p.gpa, history, to, to_len, current);
- from_len.* -= 1;
- const snap = from[from_len.*];
- history.bytes -= snap.content.len; // the file's text now
- setContent(p, f, snap.content);
- restoreName(p, pane, f, snap);
- restoreSnap(pane, f, snap);
+ const j = &f.history.journal;
+ 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;
+ const s = &j.steps.items[at];
+ if (back) {
+ s.after = now;
+ j.done -= 1;
+ } else {
+ s.before = now;
+ j.done += 1;
+ }
+ const to = if (back) s.before else s.after;
+ restoreName(p, pane, f, to);
+ 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
+/// 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 {
+ const j = &f.history.journal;
+ if (entries.len == 0) return edit(p, f, f.content.len, 0, "", null, false);
+ 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)) {
+ pardes.memory.freeRaw(p.gpa, put);
+ return false;
+ }
+ j.bytes = j.bytes - e.removed.len + put.len;
+ e.ins = e.removed.len;
+ pardes.memory.freeRaw(p.gpa, e.removed);
+ e.removed = put;
+ return true;
+ }
+ // The gap's room: what the entries put back past what they take out.
+ var room: usize = 0;
+ for (entries) |e| room += e.removed.len -| e.ins;
+ var gap = Gap.init(p.gpa, f.content, room) catch return false;
+ const puts = p.scratch.allocator().alloc([]u8, entries.len) catch {
+ pardes.memory.freeRaw(p.gpa, gap.buf);
+ return false;
+ };
+ @memset(puts, &.{});
+ for (0..entries.len) |k| {
+ const i = if (back) entries.len - 1 - k else k;
+ const e = entries[i];
+ puts[i] = gap.replace(p.gpa, e.off, e.ins, e.removed) catch {
+ for (puts) |put| pardes.memory.freeRaw(p.gpa, put);
+ pardes.memory.freeRaw(p.gpa, gap.buf);
+ return false;
+ };
+ }
+ 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)) {
+ 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;
+ }
+ return true;
+}
+
+/// A copy of a text with a gap where it was last written (`turn`): moving
+/// the gap costs the bytes between two places, never the text, so a step of
+/// many entries (a key typed at many ranges) is turned in one pass.
+const Gap = struct {
+ /// The text is `buf[0..lo]` then `buf[hi..]`.
+ buf: []u8,
+ lo: usize,
+ hi: usize,
+
+ fn init(gpa: std.mem.Allocator, bytes: []const u8, room: usize) !Gap {
+ const buf = try pardes.memory.unfilled(gpa, bytes.len + room);
+ @memcpy(buf[0..bytes.len], bytes);
+ return .{ .buf = buf, .lo = bytes.len, .hi = buf.len };
+ }
+
+ fn move(g: *Gap, at: usize) void {
+ if (at < g.lo) {
+ const n = g.lo - at;
+ @memmove(g.buf[g.hi - n .. g.hi], g.buf[at..g.lo]);
+ g.lo = at;
+ g.hi -= n;
+ } else if (at > g.lo) {
+ const n = at - g.lo;
+ @memmove(g.buf[g.lo..][0..n], g.buf[g.hi..][0..n]);
+ g.lo += n;
+ g.hi += n;
+ }
+ }
+
+ /// The `len` bytes at `at` replaced by `bytes` (in the room `init` was
+ /// given); what they were, copied out.
+ fn replace(g: *Gap, gpa: std.mem.Allocator, at: usize, len: usize, bytes: []const u8) ![]u8 {
+ g.move(at);
+ const out = try pardes.memory.dupeUnfilled(gpa, g.buf[g.hi..][0..len]);
+ g.hi += len;
+ @memcpy(g.buf[g.lo..][0..bytes.len], bytes);
+ g.lo += bytes.len;
+ return out;
+ }
+
+ /// The text whole, at the buffer's start.
+ fn whole(g: *Gap) []u8 {
+ g.move(g.lo + (g.buf.len - g.hi));
+ return g.buf[0..g.lo];
+ }
+};
+
/// A pane's file deleted on disk: the text stays, and it says so once,
/// `<file> deleted on disk (Save writes it again)`, logged `changed
/// <serial> deleted`.
@@ -1441,13 +1496,7 @@ pub fn changed(p: *Pardes, id: u8, bytes: []const u8) void {
pushUndo(p, pane);
setContent(p, f, new);
f.saved_revision = f.revision;
- // restoreSnap only consumes cursor/selection from this synthetic snapshot.
- restoreSnap(pane, f, .{
- .content = undefined,
- .cur_row = pane.body.cur_row,
- .cur_col = pane.body.cur_col,
- .vsel = pane.body.vsel,
- });
+ restoreSnap(pane, f, .{ .cur_row = pane.body.cur_row, .cur_col = pane.body.cur_col, .vsel = pane.body.vsel });
}
/// re-highlight the visible window of any file whose syntax went stale
@@ -2294,12 +2343,17 @@ test "undo keeps its steps within a byte bound, the newest always" {
setContent(p, f, try gpa.dupe(u8, text));
}
pushUndo(p, pane);
- const history = f.history;
- try std.testing.expect(history.undo_len > 0 and history.undo_len < 8);
- try std.testing.expect(history.bytes <= limits.undo_bytes + step);
+ 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 (history.undo[0..history.undo_len]) |snap| sum += snap.content.len;
- try std.testing.expectEqual(sum, history.bytes);
+ for (j.entries.items) |e| sum += e.removed.len + @sizeOf(Text.Entry);
+ 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.
+ while (j.done > 0) {
+ undoStep(p, pane, true);
+ try std.testing.expect(std.mem.allEqual(u8, f.content, f.content[0]));
+ }
}
diff --git a/src/Pipe.zig b/src/Pipe.zig
index 1f0ee5fc..3045d738 100644
--- a/src/Pipe.zig
+++ b/src/Pipe.zig
@@ -446,7 +446,7 @@ test "selection pipe replaces all ranges atomically and undo restores them" {
const outputs: []const []const u8 = &.{ "AA\n", "" };
p.update(.{ .pipe_resp = .{ .id = id, .success = true, .outputs = outputs } });
try std.testing.expectEqualSlices(u8, "AA bb \n", pane.file.?.content);
- try std.testing.expectEqual(@as(usize, 1), pane.file.?.history.undo_len);
+ try std.testing.expectEqual(@as(usize, 1), pane.file.?.history.journal.done);
try std.testing.expectEqual(@as(u16, 1), pane.body.nsel);
try std.testing.expectEqual(@as(i32, 1), pane.body.cur_col);
try std.testing.expectEqual(@as(i32, 6), pane.body.sels[0].col);
@@ -514,7 +514,7 @@ test "a command with no stdin runs once and every cursor gets that one answer" {
p.update(.{ .pipe_resp = .{ .id = id, .success = true, .outputs = &.{"T"} } });
try std.testing.expectEqualSlices(u8, "Taa bb Tcc\n", pane.file.?.content);
- try std.testing.expectEqual(@as(usize, 1), pane.file.?.history.undo_len);
+ try std.testing.expectEqual(@as(usize, 1), pane.file.?.history.journal.done);
}
test "selection pipe failure and stale completion never mutate the file" {
@@ -532,7 +532,7 @@ test "selection pipe failure and stale completion never mutate the file" {
const failed_id = nextPipeEffect(p) orelse return error.MissingPipeEffect;
p.update(.{ .pipe_resp = .{ .id = failed_id, .success = false, .outputs = &.{} } });
try std.testing.expectEqualSlices(u8, "abc\n", pane.file.?.content);
- try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.undo_len);
+ try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.journal.done);
p.update(.{ .key = .{ .cp = '|' } });
p.update(.{ .key = .{ .cp = 'c', .text = "cat" } });
@@ -541,7 +541,7 @@ test "selection pipe failure and stale completion never mutate the file" {
panes.File.setContent(p, &pane.file.?, try gpa.dupe(u8, "changed\n"));
p.update(.{ .pipe_resp = .{ .id = stale_id, .success = true, .outputs = &.{"ABC"} } });
try std.testing.expectEqualSlices(u8, "changed\n", pane.file.?.content);
- try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.undo_len);
+ try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.journal.done);
}
test "a failed filter opens an errors buffer carrying the command's own words" {
@@ -570,7 +570,7 @@ test "a failed filter opens an errors buffer carrying the command's own words" {
// The text is untouched — a failed filter is not an edit...
try std.testing.expectEqualSlices(u8, "abc\n", pane.file.?.content);
- try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.undo_len);
+ try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.journal.done);
// ...and the cursor did not go anywhere, so `|` again edits the same file.
try std.testing.expectEqual(@as(usize, 0), p.active);
@@ -603,7 +603,7 @@ test "selection pipe rejects a reused pane slot and a superseded request" {
pane = try p.setTestFile("new\n"); // same slot, different serial
p.update(.{ .pipe_resp = .{ .id = replaced_id, .success = true, .outputs = &.{"OLD"} } });
try std.testing.expectEqualSlices(u8, "new\n", pane.file.?.content);
- try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.undo_len);
+ try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.journal.done);
pane.body.cur_col = 2;
pane.body.vsel = .{ .active = true, .row = 0, .col = 0, .explicit = true };
@@ -621,7 +621,7 @@ test "selection pipe rejects a reused pane slot and a superseded request" {
try std.testing.expectEqualSlices(u8, "new\n", pane.file.?.content);
p.update(.{ .pipe_resp = .{ .id = latest_id, .success = true, .outputs = &.{"NEW"} } });
try std.testing.expectEqualSlices(u8, "NEW\n", pane.file.?.content);
- try std.testing.expectEqual(@as(usize, 1), pane.file.?.history.undo_len);
+ try std.testing.expectEqual(@as(usize, 1), pane.file.?.history.journal.done);
}
test "selection pipe binding is file-normal-only" {
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);
diff --git a/src/builtins.zig b/src/builtins.zig
index 2f51d81b..0295130d 100644
--- a/src/builtins.zig
+++ b/src/builtins.zig
@@ -1358,7 +1358,7 @@ pub const Edit = struct {
pub const Undo = struct {
pub fn run(c: Ctx) void {
if (@import("edit_cmd.zig").busyOn(c.p, c.id)) return c.p.reportFailure(c.id, "Undo: " ++ @import("edit_cmd.zig").e_busy);
- if (c.pane.file) |f| if (f.history.undo_len == 0) return c.p.setMessage(c.id, "Undo: nothing to undo");
+ if (c.pane.file) |f| if (f.history.journal.done == 0) return c.p.setMessage(c.id, "Undo: nothing to undo");
edit.undoStep(c.p, &c.pane.body, true);
}
};
@@ -1367,7 +1367,7 @@ pub const Undo = struct {
pub const Redo = struct {
pub fn run(c: Ctx) void {
if (@import("edit_cmd.zig").busyOn(c.p, c.id)) return c.p.reportFailure(c.id, "Redo: " ++ @import("edit_cmd.zig").e_busy);
- if (c.pane.file) |f| if (f.history.redo_len == 0) return c.p.setMessage(c.id, "Redo: nothing to redo");
+ if (c.pane.file) |f| if (f.history.journal.done == f.history.journal.steps.items.len) return c.p.setMessage(c.id, "Redo: nothing to redo");
edit.undoStep(c.p, &c.pane.body, false);
}
};
diff --git a/src/edit_cmd.zig b/src/edit_cmd.zig
index 517f2e8d..99cac6ce 100644
--- a/src/edit_cmd.zig
+++ b/src/edit_cmd.zig
@@ -565,7 +565,7 @@ test "Edit's < | and > with a real shell: a command per address, > printed to +E
try testing.expectEqual(@as(usize, 3), p.pipe.edit_run.?.request.inputs.len);
try runReal(p);
try testing.expectEqualStrings("ONE TWO\nTHREE\n", p.panes[0].?.file.?.content);
- try testing.expectEqual(@as(usize, 1), p.panes[0].?.file.?.history.undo_len);
+ try testing.expectEqual(@as(usize, 1), p.panes[0].?.file.?.history.journal.done);
try testing.expectEqual(tree.Status.ok, th.wr(p, ctl, "Edit 2 < printf new\n").reply.status);
try runReal(p);
try testing.expectEqualStrings("ONE TWO\nnew", p.panes[0].?.file.?.content);
@@ -585,7 +585,7 @@ test "a failing command changes nothing and says why, its stderr in +Errors" {
p.fs.edit_hold = .{ .asker = @ptrCast(p), .slot = 0, .seq = 1, .tag = 2, .node = ctl, .handle = 0, .written = 1 };
try runReal(p);
try testing.expectEqualStrings("keep\n", p.panes[0].?.file.?.content);
- try testing.expectEqual(@as(usize, 0), p.panes[0].?.file.?.history.undo_len);
+ try testing.expectEqual(@as(usize, 0), p.panes[0].?.file.?.history.journal.done);
// The held write's answer is the failure, in its words.
try testing.expectEqualStrings("Edit: | echo boom >&2; exit 3: exit status 3", filesystem.EditHold.answer(&p.fs).ename);
const report = errorsText(p).?;
diff --git a/src/fs.zig b/src/fs.zig
index f32c6ea7..ae614cd7 100644
--- a/src/fs.zig
+++ b/src/fs.zig
@@ -665,7 +665,7 @@ test "virtual body writes can read their input from the same pane" {
try write(p, path, pane.file.?.content);
try std.testing.expectEqualStrings("same pane contents\n", pane.file.?.content);
// The truncation and the write are one undo step.
- try std.testing.expectEqual(@as(usize, 1), pane.file.?.history.undo_len);
+ try std.testing.expectEqual(@as(usize, 1), pane.file.?.history.journal.done);
const events = &p.panes[p.active].?.fs.events;
try std.testing.expect(std.mem.startsWith(u8, events.peek().?, "ED"));
events.pop();
diff --git a/src/host_io.zig b/src/host_io.zig
index 6b27141e..86e97876 100644
--- a/src/host_io.zig
+++ b/src/host_io.zig
@@ -908,7 +908,7 @@ pub const Lsp = struct {
pane.file.?.path = path;
pane.body.cur_col = 6;
const revision = pane.file.?.revision;
- const undo_len = pane.file.?.history.undo_len;
+ const undo_len = pane.file.?.history.journal.done;
var failing = std.testing.FailingAllocator.init(gpa, .{});
var sink: Sink = .{ .core = core, .gpa = failing.allocator() };
for ([_]bool{ true, false }) |fail| {
@@ -928,10 +928,10 @@ pub const Lsp = struct {
if (fail) {
try std.testing.expectEqualStrings("const value=1;\n", pane.file.?.content);
try std.testing.expectEqual(revision, pane.file.?.revision);
- try std.testing.expectEqual(undo_len, pane.file.?.history.undo_len);
+ try std.testing.expectEqual(undo_len, pane.file.?.history.journal.done);
} else {
try std.testing.expectEqualStrings(if (kind == .format) "const value = 1;\n" else "const renamed=1;\n", pane.file.?.content);
- try std.testing.expectEqual(undo_len + 1, pane.file.?.history.undo_len);
+ try std.testing.expectEqual(undo_len + 1, pane.file.?.history.journal.done);
}
}
try std.testing.expectEqual(@as(usize, 2), sink.calls);
diff --git a/src/ninep/ctl.zig b/src/ninep/ctl.zig
index 96c44d14..8a84e37f 100644
--- a/src/ninep/ctl.zig
+++ b/src/ninep/ctl.zig
@@ -431,8 +431,8 @@ pub fn paneText(p: *Pardes, pane: *Pane, buf: []u8) []const u8 {
// While a column's or the workspace's tag has the keyboard, no pane does.
const current = p.panes[p.active] == pane and !p.header_focus;
const f = pane_files.fileOf(pane);
- const undo = if (f) |file| file.history.undo_len > 0 else false;
- const redo = if (f) |file| file.history.redo_len > 0 else false;
+ const undo = if (f) |file| file.history.journal.done > 0 else false;
+ const redo = if (f) |file| file.history.journal.done < file.history.journal.steps.items.len else false;
w.print(" {d:>11} {d:>11} {d:>11} {s} ", .{ config.tab_now, @intFromBool(undo), @intFromBool(redo), if (current) "current" else "notcurrent" }) catch {};
// A terminal bound as a REPL ends with its id, `python-a`.
var idbuf: [48]u8 = undefined;
@@ -2695,8 +2695,15 @@ test "what a /pager open writes after its directory is the text: plain in the bo
try testing.expectEqual(pardes.Color{ .index = 1 }, f.pager_spans[0].style.fg);
try testing.expect(f.pager_spans[1].style.bold);
// One undo step back to the empty pane.
- try testing.expect(f.history.undo_len > 0);
- try testing.expectEqualStrings("", f.history.undo[f.history.undo_len - 1].content);
+ const j = &f.history.journal;
+ try testing.expect(j.done > 0);
+ const top = j.steps.items[j.done - 1];
+ try testing.expectEqual(@as(usize, 1), top.n);
+ // Its one entry took out the nothing the pane held and put the page in.
+ const e = j.entries.items[top.first];
+ try testing.expectEqual(@as(usize, 0), e.off);
+ try testing.expectEqual(@as(usize, 0), e.removed.len);
+ try testing.expectEqual(f.content.len, e.ins);
// An edit drops the colours (pager.zig's ponytail).
try testing.expectEqual(Status.ok, call(p, .{ .tag = 6, .op = .write, .node = Node.of(pn.serial, .body), .data = "more\n" }).reply.status);
try testing.expectEqual(@as(usize, 0), f.pager_spans.len);
diff --git a/src/replica.zig b/src/replica.zig
index 858c8e01..82cd83f9 100644
--- a/src/replica.zig
+++ b/src/replica.zig
@@ -3757,6 +3757,9 @@ test "a far join is sent each blob once: joined again with them on disk or in th
_ = try a.local(.{ .key = .{ .cp = 'o', .text = "o" } });
_ = try a.local(.{ .paste = text[0..9000] });
_ = try a.local(.{ .key = .{ .cp = pardes.Key.escape, .text = "" } });
+ // Two blobs more than the text: 70 lines deleted (the undo's), the 80
+ // after them yanked (the register's).
+ for ("gg70xd80xy") |c| _ = try a.local(.{ .key = .{ .cp = c, .text = &.{c} } });
const was = Stepping.begin(&a.t, null);
defer was.end();
const whole = try pardes.dump.dumpBytes(a.core);
diff --git a/test/panes.zig b/test/panes.zig
index aa54d483..958c35a2 100644
--- a/test/panes.zig
+++ b/test/panes.zig
@@ -1376,8 +1376,7 @@ test "file history construction failures preserve existing panes" {
if (result) |pane| {
if (case == .output) incoming = null;
try std.testing.expect(pane.file.?.history != old_history);
- try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.undo_len);
- try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.redo_len);
+ try std.testing.expectEqual(@as(usize, 0), pane.file.?.history.journal.steps.items.len);
succeeded = true;
break;
} else |err| {
@@ -1394,7 +1393,7 @@ test "file history construction failures preserve existing panes" {
}
}
-test "file history owns bounded snapshot storage without per-edit bookkeeping allocations" {
+test "file history keeps its last undo_max steps, and an undo or redo with no memory changes nothing" {
var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{});
const p = try Pardes.init(failing.allocator(), .{ .tty_only = true, .cols = 40, .rows = 12 });
defer p.deinit();
@@ -1403,39 +1402,35 @@ test "file history owns bounded snapshot storage without per-edit bookkeeping al
const history = file.history;
for (0..pardes.memory.limits.undo_max + 2) |index| {
const next = try std.fmt.allocPrint(p.gpa, "{d}", .{index});
- const before = failing.alloc_index;
panes.File.pushUndo(p, pane);
- try std.testing.expectEqual(before + 1, failing.alloc_index);
panes.File.setContent(p, file, next);
try std.testing.expectEqual(history, file.history);
}
- try std.testing.expectEqual(pardes.memory.limits.undo_max, history.undo_len);
- try std.testing.expectEqualStrings("1", history.undo[0].content);
- const current = file.content;
+ const j = &history.journal;
+ try std.testing.expectEqual(pardes.memory.limits.undo_max, j.done);
+ // The two oldest steps went: the oldest kept took "1" out for "2".
+ try std.testing.expectEqualStrings("1", j.entries.items[j.steps.items[0].first].removed);
+ // No memory for the bytes an undo keeps: nothing changes.
failing.fail_index = failing.alloc_index;
- panes.File.pushUndo(p, pane);
panes.File.undoStep(p, pane, true);
- try std.testing.expectEqual(current.ptr, file.content.ptr);
- try std.testing.expectEqual(pardes.memory.limits.undo_max, history.undo_len);
- try std.testing.expectEqual(@as(usize, 0), history.redo_len);
+ try std.testing.expectEqualStrings("257", file.content);
+ try std.testing.expectEqual(pardes.memory.limits.undo_max, j.done);
failing.fail_index = std.math.maxInt(usize);
- const before = failing.alloc_index;
panes.File.undoStep(p, pane, true);
- try std.testing.expectEqual(before + 2, failing.alloc_index);
- try std.testing.expectEqual(@as(usize, 1), file.line_starts.len);
- try std.testing.expectEqual(@as(usize, 1), history.redo_len);
- const undone = file.content;
+ try std.testing.expectEqualStrings("256", file.content);
+ try std.testing.expectEqual(@as(usize, 1), j.steps.items.len - j.done);
failing.fail_index = failing.alloc_index;
panes.File.undoStep(p, pane, false);
- try std.testing.expectEqual(undone.ptr, file.content.ptr);
- try std.testing.expectEqual(@as(usize, 1), history.redo_len);
+ try std.testing.expectEqualStrings("256", file.content);
+ try std.testing.expectEqual(@as(usize, 1), j.steps.items.len - j.done);
failing.fail_index = std.math.maxInt(usize);
- const before_redo = failing.alloc_index;
panes.File.undoStep(p, pane, false);
- // The snapshot's copy alone: the line index moves in place.
- try std.testing.expectEqual(before_redo + 1, failing.alloc_index);
- try std.testing.expectEqual(pardes.memory.limits.undo_max, history.undo_len);
- try std.testing.expectEqual(@as(usize, 0), history.redo_len);
+ try std.testing.expectEqualStrings("257", file.content);
+ try std.testing.expectEqual(pardes.memory.limits.undo_max, j.done);
+ // Back through every step kept, and no further.
+ for (0..pardes.memory.limits.undo_max + 1) |_| panes.File.undoStep(p, pane, true);
+ try std.testing.expectEqualStrings("1", file.content);
+ try std.testing.expectEqual(@as(usize, 0), j.done);
}
test "file history allocation precedes reading the served tree" {