diff options
| -rw-r--r-- | src/File.zig | 262 | ||||
| -rw-r--r-- | src/Pipe.zig | 14 | ||||
| -rw-r--r-- | src/Text.zig | 183 | ||||
| -rw-r--r-- | src/builtins.zig | 4 | ||||
| -rw-r--r-- | src/edit_cmd.zig | 4 | ||||
| -rw-r--r-- | src/fs.zig | 2 | ||||
| -rw-r--r-- | src/host_io.zig | 6 | ||||
| -rw-r--r-- | src/ninep/ctl.zig | 15 | ||||
| -rw-r--r-- | src/replica.zig | 3 | ||||
| -rw-r--r-- | test/panes.zig | 43 |
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).?; @@ -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" { |
