summaryrefslogtreecommitdiff
path: root/src/Text.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/Text.zig')
-rw-r--r--src/Text.zig183
1 files changed, 183 insertions, 0 deletions
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);