diff options
Diffstat (limited to 'src/Text.zig')
| -rw-r--r-- | src/Text.zig | 183 |
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); |
