From 8640107e29a940d50a5eef0dc7d12689a515d856 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 5 Nov 2026 11:02:29 -0300 Subject: text journal, the primitive: File.replace(off, len, bytes) puts an edit in the text's own buffer (its tail moved with @memmove), the buffer grown by an eighth when it must be (State.cap), and moves its line index in place from the edit on (shiftIndex, State.line_cap), so a key, a backspace and a 9P write cost their bytes and what follows them, never a copy of the text (on the 50k-line file, Debug, medians against the base run beside it: edit-char 1105 -> 420 us, edit-twin 930 -> 433, body-2m 8.6 -> 4.7 ms, body-appends 173 -> 79 ms); setContent is the same edit with the caller's whole new text taken as the buffer; a replica's core (its allocator an epoch's, rollback.isEpoch) and a text a join still sends (memory.isPinned) keep their bytes, the edit putting a new buffer in their place as every edit did, so the rollback copy, its pins and the join's blobs work as they were; a pane's event readers hear an edit's span found from the edit (events.editSpan), the one diffSpan found from two texts; tests: 'edited line index equals a rebuilt one' becomes 'a line index shifted in place equals a rebuilt one' (editedLineStarts goes), 'an edit's span is where the texts before and after it differ' is new, and the panes test of history storage counts one allocation less for a redo (the index moves in place) Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_016Y9MNAtZenFv4weoMD3cge --- src/File.zig | 278 ++++++++++++++++++++++++++++++++++++--------------- src/edit.zig | 38 +++++-- src/memory.zig | 9 ++ src/ninep/events.zig | 109 ++++++++++++-------- src/ninep/pane.zig | 6 +- src/rollback.zig | 11 +- 6 files changed, 315 insertions(+), 136 deletions(-) (limited to 'src') diff --git a/src/File.zig b/src/File.zig index 94e211a1..7aac4cb9 100644 --- a/src/File.zig +++ b/src/File.zig @@ -141,13 +141,19 @@ pub const State = struct { /// What the replay digest leaves out (src/walk.zig): what is made again /// from the text whenever it is wanted. pub const replica = .{ - .derived = .{ "line_starts", "highlights", "highlight_start", "syntax_dirty", "node_tree", "node_tree_revision", "node_history", "tables" }, - // Replaced whole at every edit (setContentSpan), never written. + .derived = .{ "cap", "line_starts", "line_cap", "highlights", "highlight_start", "syntax_dirty", "node_tree", "node_tree_revision", "node_history", "tables" }, + // Written in place by `replace`, but never in a replica's core or + // while a join sends them (`keepsBytes`): there an edit puts a new + // buffer in their place. .blob = .{ "content", "line_starts", "location_rows" }, }; path: []u8, content: []u8, + /// The bytes `content`'s buffer has room for (0: as many as it holds): + /// an edit that must grow it grows it by an eighth more, so the keys + /// after it move no text but what follows them (`replace`). + cap: usize = 0, revision: u32 = 0, /// Revision last known to match disk, after Save or an external reload. /// Equal means the screen matches disk. @@ -190,6 +196,8 @@ pub const State = struct { scroll: usize = 0, /// `line_starts[i]` is line i's byte offset. Empty means not built yet. line_starts: []usize = &.{}, + /// The room `line_starts` has, as `cap` is `content`'s. + line_cap: usize = 0, /// One tree_sitter_gpa-owned syntax.Syn byte per highlighted source byte. highlights: []u8 = &.{}, location_rows: []locations.Row = &.{}, @@ -348,7 +356,8 @@ test "indexed source rows match uncached scans across content changes" { // An edit carries a built index forward; it must equal a fresh one. if (file.line_starts.len > 0) { const carried = file.line_starts; - defer p.gpa.free(carried); + const room = indexRoom(file); + defer p.gpa.free(room); file.line_starts = &.{}; try std.testing.expectEqualSlices(usize, try lineIndex(p.gpa, file), carried); p.gpa.free(file.line_starts); @@ -603,81 +612,100 @@ pub fn lineIndex(gpa: std.mem.Allocator, f: *State) ![]const usize { i += 1; } f.line_starts = starts; + f.line_cap = 0; return starts; } +/// The whole buffer of a text's bytes, its room past them included. +fn textRoom(f: *const State) []u8 { + return f.content.ptr[0..@max(f.cap, f.content.len)]; +} + +/// The whole buffer of a text's line index, as `textRoom` is its text's. +fn indexRoom(f: *const State) []usize { + return f.line_starts.ptr[0..@max(f.line_cap, f.line_starts.len)]; +} + /// `std.sort`'s order for offsets: a key against an item. fn ascending(key: usize, item: usize) std.math.Order { return std.math.order(key, item); } -/// The line index of `new` from `old`'s: an edit replaces one span, so -/// line starts before it stand, starts after it shift, and only the span -/// is scanned. Rebuilding scanned the whole file on every keystroke. /// The bytes a splice left alone at either end, when its caller knows them. pub const Span = struct { head: usize, tail: usize }; -fn editedLineStarts(gpa: std.mem.Allocator, starts: []const usize, old: []const u8, new: []const u8, known: ?Span) ![]usize { - const span = known orelse spanOf(old, new); - const head = span.head; - const tail = span.tail; - // A start s follows the newline at s-1: kept while that newline is in - // the common head, shifted while it is in the common tail. - const kept = std.sort.upperBound(usize, starts, head, ascending); - const old_tail_at = old.len - tail; - const moved = starts.len - std.sort.upperBound(usize, starts, old_tail_at, ascending); - const middle = new[head .. new.len - tail]; - const out = try gpa.alloc(usize, kept + std.mem.count(u8, middle, "\n") + moved); - @memcpy(out[0..kept], starts[0..kept]); - var i = kept; - var off: usize = 0; - while (std.mem.indexOfScalarPos(u8, middle, off, '\n')) |nl| { - off = nl + 1; - out[i] = head + off; - i += 1; +/// `f`'s line index through the edit that puts `bytes` over the `len` bytes +/// at `off`, in its own buffer: the starts before the edit stand, those it +/// took out go, its newlines' come in, and those after it move by what it +/// added; only the moving is a pass over the index, and only from the edit +/// on. `keep` (a replica's core, whose rollback copy holds the old index) +/// makes a new one instead, as every edit did once. On no memory the index +/// goes, to be made again when it is asked for. +fn shiftIndex(gpa: std.mem.Allocator, f: *State, off: usize, len: usize, bytes: []const u8, keep: bool) void { + const starts = f.line_starts; + const room = indexRoom(f); + const kept = std.sort.upperBound(usize, starts, off, ascending); + const moved = starts.len - std.sort.upperBound(usize, starts, off + len, ascending); + const n = kept + std.mem.count(u8, bytes, "\n") + moved; + const from = starts.len - moved; + const to = n - moved; + var out = room; + if (keep or n > room.len) { + const want = if (keep) n else n + @max(n / 8, 512); + out = gpa.alloc(usize, want) catch { + pardes.memory.freeRaw(gpa, room); + f.line_starts = &.{}; + f.line_cap = 0; + return; + }; + @memcpy(out[0..kept], starts[0..kept]); + } + // In place, the starts that move go back to front when the edit grew + // the index, front to back when it shrank it. + if (to > from and out.ptr == room.ptr) { + var k = moved; + while (k > 0) { + k -= 1; + out[to + k] = room[from + k] - len + bytes.len; + } + } else for (0..moved) |k| { + out[to + k] = room[from + k] - len + bytes.len; } - for (starts[starts.len - moved ..]) |start| { - out[i] = start + new.len - old.len; + var i = kept; + var at: usize = 0; + while (std.mem.indexOfScalarPos(u8, bytes, at, '\n')) |nl| { + at = nl + 1; + out[i] = off + at; i += 1; } - return out; + if (out.ptr != room.ptr) pardes.memory.freeRaw(gpa, room); + f.line_starts = out[0..n]; + f.line_cap = out.len; } -test "edited line index equals a rebuilt one" { +test "a line index shifted in place equals a rebuilt one" { const gpa = std.testing.allocator; - var prng = std.Random.DefaultPrng.init(7); + var prng = std.Random.DefaultPrng.init(11); const r = prng.random(); var text: std.ArrayList(u8) = .empty; defer text.deinit(gpa); for (0..300) |_| try text.append(gpa, "ab\n"[r.uintLessThan(usize, 3)]); - for (0..2000) |_| { - var old_state: State = undefined; - old_state.content = text.items; - old_state.line_starts = &.{}; - const starts = try lineIndex(gpa, &old_state); - defer gpa.free(starts); - // one random replace, like any edit through setContent + var f: State = .{ .path = &.{}, .content = text.items, .history = undefined }; + _ = try lineIndex(gpa, &f); + defer gpa.free(indexRoom(&f)); + for (0..2000) |round| { const at = r.uintAtMost(usize, text.items.len); - const del = r.uintAtMost(usize, @min(8, text.items.len - at)); - var ins: [8]u8 = undefined; - const ins_len = r.uintAtMost(usize, 8); + const del = r.uintAtMost(usize, @min(12, text.items.len - at)); + var ins: [12]u8 = undefined; + const ins_len = r.uintAtMost(usize, 12); for (ins[0..ins_len]) |*c| c.* = "ab\n"[r.uintLessThan(usize, 3)]; - const old = try gpa.dupe(u8, text.items); - defer gpa.free(old); + // In place, and every tenth as a replica's core makes it, anew. + shiftIndex(gpa, &f, at, del, ins[0..ins_len], round % 10 == 0); try text.replaceRange(gpa, at, del, ins[0..ins_len]); - // As a splice that says what it kept, and as one that does not. - const known: Span = .{ .head = at, .tail = old.len - at - del }; - const told = try editedLineStarts(gpa, starts, old, text.items, known); - defer gpa.free(told); - const edited = try editedLineStarts(gpa, starts, old, text.items, null); - try std.testing.expectEqualSlices(usize, edited, told); - defer gpa.free(edited); - var fresh_state: State = undefined; - fresh_state.content = text.items; - fresh_state.line_starts = &.{}; - const fresh = try lineIndex(gpa, &fresh_state); - defer gpa.free(fresh); - try std.testing.expectEqualSlices(usize, fresh, edited); + var fresh: State = .{ .path = &.{}, .content = text.items, .history = undefined }; + const want = try lineIndex(gpa, &fresh); + defer gpa.free(want); + try std.testing.expectEqualSlices(usize, want, f.line_starts); } } @@ -806,10 +834,10 @@ pub fn deinit(p: *Pardes, pane: *Pane, file: *State) void { p.gpa.free(file.path); // Raw, as every text is freed (a replica's rollback copy pins them, // src/rollback.zig, and a safe build's free writes over what it frees). - if (ntwins == 0) pardes.memory.freeRaw(p.gpa, file.content); + if (ntwins == 0) pardes.memory.freeRaw(p.gpa, textRoom(file)); if (file.listing) |listing| p.gpa.free(listing.names); if (file.mini) |*mini| mini.deinit(p.gpa); - if (file.line_starts.len > 0 and !index_shared) pardes.memory.freeRaw(p.gpa, file.line_starts); + if (file.line_starts.len > 0 and !index_shared) pardes.memory.freeRaw(p.gpa, indexRoom(file)); if (file.highlights.len > 0) p.tree_sitter_gpa.free(file.highlights); p.gpa.free(file.pager_spans); locations.freeRows(p.gpa, file.location_rows); @@ -822,13 +850,14 @@ pub fn deinit(p: *Pardes, pane: *Pane, file: *State) void { file.history.destroy(p.gpa); } -fn reportEdit(p: *Pardes, f: *State, new: []const u8) void { +/// The edit `replace` makes told to the event readers, before it is made. +fn reportEdit(p: *Pardes, f: *State, off: usize, len: usize, bytes: []const u8) void { if (p.fs.listeners == 0) return; const id = for (p.panes, 0..) |slot, i| { const pane = slot orelse continue; if (pane.file) |*state| if (state == f) break i; } else return; - pardes.ctlfs.events.noteReplace(p, id, false, f.content, new); + pardes.ctlfs.events.noteEdit(p, id, false, f.content, off, len, bytes); } pub fn setContent(p: *Pardes, f: *State, new: []u8) void { @@ -836,24 +865,67 @@ pub fn setContent(p: *Pardes, f: *State, new: []u8) void { } /// `setContent` for a splice that knows what it left alone at either end, -/// so the line index is not found again by comparing the whole text. +/// so it is not found again by comparing the whole text. The edit is what +/// lies between them, made by `edit`, which takes `new`, a whole text its +/// caller made anyway, as the text's buffer. pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { - // Twins (Zerox) take the same splice: where it is, found once here when - // the caller did not say, is what the line index wants anyway. + 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); +} + +/// The one change a text takes: the `len` bytes at `off` replaced by +/// `bytes`, in its own buffer, so an edit costs its bytes and what follows +/// 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); +} + +/// Whether `f`'s bytes must stay as they are, an edit putting a new buffer +/// in their place: a replica's core, whose rollback copy holds them +/// (src/rollback.zig), or a text a join is still sending (memory.zig `pin`). +fn keepsBytes(p: *const Pardes, f: *const State) bool { + return pardes.rollback.isEpoch(p.gpa) or pardes.memory.isPinned(f.content); +} + +/// `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 { + 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 }; var twins: [pardes.MAX_PANES]usize = undefined; const ntwins = twinsOf(p, f, &twins); + const room = textRoom(f); + // Bytes of the text's own (a move within it) are copied out first: the + // text moves under them. + const own = whole == null and @intFromPtr(bytes_in.ptr) < @intFromPtr(room.ptr) + room.len and @intFromPtr(bytes_in.ptr) + bytes_in.len > @intFromPtr(room.ptr); + const bytes = if (own) p.scratch.allocator().dupe(u8, bytes_in) catch return false else bytes_in; + const keep = whole == null and keepsBytes(p, f); + const fresh: ?[]u8 = whole orelse if (keep) copySpliced(p.gpa, f.content, off, len, bytes) catch return false else null; + if (fresh == null) { + grow(p.gpa, f, new_len) catch return false; + // The twins' buffer is this one, which may have moved. + for (twins[0..ntwins]) |id| { + const tf = &p.panes[id].?.file.?; + tf.content = f.content; + tf.cap = f.cap; + } + } // The views not live keep their place in it as twins do (views.zig). const viewed = pardes.views.several(p); - const span: ?Span = span_in orelse if (ntwins > 0 or viewed) spanOf(f.content, new) else null; var parked: ParkedPlaces = .{}; - if (viewed) parked.before(p, f, span.?, new.len); + if (viewed) parked.before(p, f, span, new_len); defer if (viewed) parked.after(p); var moved: [pardes.MAX_PANES]struct { cursor: usize, scroll: usize } = undefined; for (twins[0..ntwins], 0..) |id, i| { const t = p.panes[id].?; const tf = &t.file.?; const at = lineStart(p.gpa, tf, @intCast(@max(0, t.body.cur_row))) + @as(usize, @intCast(@max(0, t.body.cur_col))); - moved[i] = .{ .cursor = spliced(@min(at, f.content.len), f.content.len, new.len, span.?), .scroll = spliced(lineStart(p.gpa, tf, tf.scroll), f.content.len, new.len, span.?) }; + moved[i] = .{ .cursor = spliced(@min(at, old_len), old_len, new_len, span), .scroll = spliced(lineStart(p.gpa, tf, tf.scroll), old_len, new_len, span) }; } const old_starts = f.line_starts.ptr; // An edit drops the rows and the colours, made for the text it changes. @@ -869,45 +941,54 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { } }; }; - reportEdit(p, f, new); + reportEdit(p, f, off, len, bytes); if (f.mini) |*mini| mini.deinit(p.gpa); f.mini = null; - // Found once for the line index and the places both (32 bytes a step). - const known = span orelse spanOf(f.content, new); - const starts: []usize = if (f.line_starts.len > 0) editedLineStarts(p.gpa, f.line_starts, f.content, new, known) catch &.{} else &.{}; - const old_len = f.content.len; + if (f.line_starts.len > 0) shiftIndex(p.gpa, f, off, len, bytes, pardes.rollback.isEpoch(p.gpa)); // 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) { f.saved_hash = std.hash.Wyhash.hash(0, f.content); f.saved_len = f.content.len; } - // Raw: `free` overwrites a safe build's freed memory, a whole file's - // worth per keystroke; and its digest word goes (src/walk.zig). - pardes.memory.freeRaw(p.gpa, f.content); - f.content = new; + if (fresh) |new| { + // Raw: `free` overwrites a safe build's freed memory, a whole + // file's worth; and its digest word goes (src/walk.zig). + pardes.memory.freeRaw(p.gpa, textRoom(f)); + f.content = new[0..new_len]; + f.cap = new.len; + } else { + const buffer = textRoom(f); + const tail = old_len - off - len; + if (bytes.len != len) @memmove(buffer[off + bytes.len ..][0..tail], buffer[off + len ..][0..tail]); + @memcpy(buffer[off..][0..bytes.len], bytes); + f.content = buffer[0..new_len]; + f.cap = buffer.len; + // Written in place: a word a digest kept for it is no longer its. + pardes.walk.forget(@intFromPtr(buffer.ptr)); + } f.revision +%= 1; - f.splice = .{ .revision = f.revision, .head = known.head, .tail = known.tail, .old_len = old_len }; - if (f.saved_hash) |h| if ((f.saved_len orelse new.len) == new.len and std.hash.Wyhash.hash(0, new) == h) { + f.splice = .{ .revision = f.revision, .head = span.head, .tail = span.tail, .old_len = old_len }; + if (f.saved_hash) |h| if ((f.saved_len orelse new_len) == new_len and std.hash.Wyhash.hash(0, f.content) == h) { f.saved_revision = f.revision; }; // The clock the session that recorded read (src/tape.zig). f.mtime = pardes.tape.value(.mtime, pardes.ctlfs.events.now, .{}); - if (f.line_starts.len > 0) pardes.memory.freeRaw(p.gpa, f.line_starts); - f.line_starts = starts; if (f.highlights.len > 0) p.tree_sitter_gpa.free(f.highlights); f.highlights = &.{}; f.highlight_start = 0; f.syntax_dirty = true; - if (f.pager) f.pager_diff = looksLikeDiff(new[0..@min(new.len, 64 * 1024)]); + if (f.pager) f.pager_diff = looksLikeDiff(f.content[0..@min(new_len, 64 * 1024)]); for (twins[0..ntwins], 0..) |id, i| { const t = p.panes[id].?; const tf = &t.file.?; // Its own index, built while the shared one was empty, goes; the - // shared one, freed above, is replaced. - if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) pardes.memory.freeRaw(p.gpa, tf.line_starts); + // shared one is this one's, moved through the edit. + if (tf.line_starts.len > 0 and tf.line_starts.ptr != old_starts) pardes.memory.freeRaw(p.gpa, indexRoom(tf)); tf.content = f.content; + tf.cap = f.cap; tf.line_starts = f.line_starts; + tf.line_cap = f.line_cap; tf.revision = f.revision; tf.saved_revision = f.saved_revision; tf.saved_hash = f.saved_hash; @@ -932,6 +1013,35 @@ pub fn setContentSpan(p: *Pardes, f: *State, new: []u8, span_in: ?Span) void { t.body.cur_col = @intCast(cursor.col); tf.scroll = positionIn(p.gpa, tf, moved[i].scroll).row; } + return true; +} + +/// Room in `f`'s buffer for `n` bytes, grown by an eighth more when it must +/// be: in place where its allocator can, else into a new buffer. +fn grow(gpa: std.mem.Allocator, f: *State, n: usize) !void { + const room = textRoom(f); + if (n <= room.len) return; + const want = n + @max(n / 8, 4096); + if (room.len > 0) if (gpa.remap(room, want)) |grown| { + pardes.walk.forget(@intFromPtr(room.ptr)); + f.content = grown[0..f.content.len]; + f.cap = grown.len; + return; + }; + const fresh = try pardes.memory.unfilled(gpa, want); + @memcpy(fresh[0..f.content.len], f.content); + pardes.memory.freeRaw(gpa, room); + f.content = fresh[0..f.content.len]; + f.cap = fresh.len; +} + +/// `text` with the `len` bytes at `off` replaced by `bytes`, in a new buffer. +fn copySpliced(gpa: std.mem.Allocator, text: []const u8, off: usize, len: usize, bytes: []const u8) ![]u8 { + const out = try pardes.memory.unfilled(gpa, text.len - len + bytes.len); + @memcpy(out[0..off], text[0..off]); + @memcpy(out[off..][0..bytes.len], bytes); + @memcpy(out[off + bytes.len ..], text[off + len ..]); + return out; } /// Each other view's cursor and scroll on a text being changed, as offsets @@ -1068,7 +1178,9 @@ pub fn zerox(p: *Pardes, from: usize, to: usize) !*Pane { pane.file = .{ .path = path, .content = f.content, + .cap = f.cap, .line_starts = f.line_starts, + .line_cap = f.line_cap, .history = f.history, .revision = f.revision, .saved_revision = f.saved_revision, @@ -1099,8 +1211,12 @@ pub fn leaveTwins(p: *Pardes, f: *State) void { const shared_index = for (twins[0..n]) |id| { if (p.panes[id].?.file.?.line_starts.ptr == f.line_starts.ptr) break true; } else false; - if (shared_index) f.line_starts = &.{}; + if (shared_index) { + f.line_starts = &.{}; + f.line_cap = 0; + } f.content = p.gpa.dupe(u8, f.content) catch p.gpa.alloc(u8, 0) catch &.{}; + f.cap = 0; f.history = History.create(p.gpa) catch f.history; // The one left is no twin now (syncTwins drops the group). if (n == 1) p.panes[twins[0]].?.file.?.twin = 0; diff --git a/src/edit.zig b/src/edit.zig index 84db62c0..ec37d0e3 100644 --- a/src/edit.zig +++ b/src/edit.zig @@ -545,6 +545,17 @@ fn setEditTextSpan(p: *Pardes, t: *Text, new: []u8, known_end: ?modal.Cursor, sp panes.terminal.setEditText(p, pane, new); } +/// The file whose text `t` edits in place (File.replace), the bytes it puts +/// in and no copy of the text: a file's body, not a live query's (whose +/// edits `setEditTextSpan` cuts to its line 1). +fn bodyFile(t: *Text) ?*panes.File.State { + if (t.what != .body) return null; + const pane = t.pane() orelse return null; + const f = if (pane.file) |*file| file else return null; + if (pane.query) |q| if (!q.frozen) return null; + return f; +} + /// Take a text an edit made that nothing keeps, holding it until the next /// one: the edit's caller still reads it to place the cursor. pub fn retireEditText(p: *Pardes, new: []u8) void { @@ -841,9 +852,14 @@ fn insertEdit(p: *Pardes, t: *Text, key: Key) void { panes.File.textLineStart(t, text, c.row) + @min(c.col, panes.File.textLine(t, text, c.row).len) else modal.insertOffset(text, c); - const new = modal.spliceAlloc(p.gpa, text, at, at, key.text) catch return; const end = modal.advanceBy(c, key.text); - setEditTextSpan(p, t, new, end, .{ .head = at, .tail = text.len - at }); + if (bodyFile(t)) |f| { + if (!panes.File.replace(p, f, at, 0, key.text)) return; + t.last_edit = .{ .row = @intCast(end.row), .col = @intCast(end.col) }; + } else { + const new = modal.spliceAlloc(p.gpa, text, at, at, key.text) catch return; + setEditTextSpan(p, t, new, end, .{ .head = at, .tail = text.len - at }); + } t.cur_row = @as(i32, @intCast(end.row)) + eb.row0; t.cur_col = @intCast(end.col); t.cur_pinned = true; @@ -958,9 +974,16 @@ fn insertEdit(p: *Pardes, t: *Text, key: Key) void { // deleteSpan's splice, the line found once. const s = start + @min(prev, line.len); const e = start + @min(c.col, line.len); - const new = if (e > s) modal.spliceAlloc(p.gpa, text, s, e, "") catch return else p.gpa.dupe(u8, text) catch return; - const span: panes.File.Span = if (e > s) .{ .head = s, .tail = text.len - e } else .{ .head = text.len, .tail = 0 }; - setEditTextSpan(p, t, new, .{ .row = c.row, .col = prev }, span); + if (bodyFile(t)) |f| { + // As the whole text put back would be: a no-op edit + // when there is nothing before the cursor to take. + if (!(if (e > s) panes.File.replace(p, f, s, e - s, "") else panes.File.replace(p, f, text.len, 0, ""))) return; + t.last_edit = .{ .row = @intCast(c.row), .col = @intCast(prev) }; + } else { + const new = if (e > s) modal.spliceAlloc(p.gpa, text, s, e, "") catch return else p.gpa.dupe(u8, text) catch return; + const span: panes.File.Span = if (e > s) .{ .head = s, .tail = text.len - e } else .{ .head = text.len, .tail = 0 }; + setEditTextSpan(p, t, new, .{ .row = c.row, .col = prev }, span); + } t.cur_col = @intCast(prev); t.cur_pinned = true; t.show(); @@ -2272,8 +2295,9 @@ test "typing and backspace through the line index keep the text and the index as // the index the edits kept, against one built from the text const kept = try gpa.dupe(usize, try panes.File.lineIndex(gpa, &pane.file.?)); defer gpa.free(kept); - gpa.free(pane.file.?.line_starts); - pane.file.?.line_starts = &.{}; + gpa.free(f.line_starts.ptr[0..@max(f.line_cap, f.line_starts.len)]); + f.line_starts = &.{}; + f.line_cap = 0; try std.testing.expectEqualSlices(usize, try panes.File.lineIndex(gpa, &pane.file.?), kept); } } diff --git a/src/memory.zig b/src/memory.zig index 6f6c6191..7021a1bb 100644 --- a/src/memory.zig +++ b/src/memory.zig @@ -409,6 +409,15 @@ pub fn unpin(bytes: []const u8) void { } } +/// Whether the blob at `bytes.ptr` is pinned: a join's writer is still to +/// send it, so it is not written in place (File.replace). +pub fn isPinned(bytes: []const u8) bool { + if (pin_count.load(.acquire) == 0) return false; + lockPins(); + defer pins_lock.store(false, .release); + return pins.contains(@intFromPtr(bytes.ptr)); +} + /// Whether the free of `bytes` is put off (it is pinned). fn pinned(allocator: Allocator, bytes: []const u8, alignment: std.mem.Alignment) bool { if (pin_count.load(.acquire) == 0) return false; diff --git a/src/ninep/events.zig b/src/ninep/events.zig index d77cc65a..e0a67ad4 100644 --- a/src/ninep/events.zig +++ b/src/ninep/events.zig @@ -550,51 +550,76 @@ pub const flag_chorded: u32 = 8; pub const Span = struct { at: u32, removed: u32, inserted: u32 }; -pub fn diffSpan(old: []const u8, new: []const u8) Span { - const both = @min(old.len, new.len); - const stride = 64; - var head: usize = 0; - while (head + stride <= both and - std.mem.eql(u8, old[head..][0..stride], new[head..][0..stride])) head += stride; - while (head < both and old[head] == new[head]) head += 1; - var tail: usize = 0; - const rest = both - head; - while (tail + stride <= rest and std.mem.eql( - u8, - old[old.len - tail - stride ..][0..stride], - new[new.len - tail - stride ..][0..stride], - )) tail += stride; - while (tail < rest and old[old.len - 1 - tail] == new[new.len - 1 - tail]) tail += 1; - return .{ - .at = @intCast(head), - .removed = @intCast(old.len - tail - head), - .inserted = @intCast(new.len - tail - head), - }; -} - -pub fn noteReplace(p: *Pardes, id: usize, on_tag: bool, old: []const u8, new: []const u8) void { +/// What an edit about to be made changes, told to the pane's event +/// readers: the `len` bytes of `old` at `off` replaced by `bytes`, as the +/// span the texts before and after it differ in (its ends grown past the +/// edit's as far as they agree), found from the edit, never the new text. +pub fn noteEdit(p: *Pardes, id: usize, on_tag: bool, old: []const u8, off: usize, len: usize, bytes: []const u8) void { const pane = p.panes[id] orelse return; if (pane.fs.readers == 0) return; - const span = diffSpan(old, new); + const span = editSpan(old, off, len, bytes); if (span.removed == 0 and span.inserted == 0) return; - if (span.removed > 0) noteAction( - p, - id, - if (on_tag) .tag_delete else .body_delete, - span.at, - span.at + span.removed, - 0, - "", - ); - if (span.inserted > 0) noteAction( - p, - id, - if (on_tag) .tag_insert else .body_insert, - span.at, - span.at + span.inserted, - 0, - new[span.at..][0..span.inserted], - ); + if (span.removed > 0) noteAction(p, id, if (on_tag) .tag_delete else .body_delete, span.at, span.at + span.removed, 0, ""); + if (span.inserted > 0) noteAction(p, id, if (on_tag) .tag_insert else .body_insert, span.at, span.at + span.inserted, 0, bytes[span.at - off ..][0..span.inserted]); +} + +/// `noteEdit` for a text replaced whole by `new`. +pub fn noteReplace(p: *Pardes, id: usize, on_tag: bool, old: []const u8, new: []const u8) void { + noteEdit(p, id, on_tag, old, 0, old.len, new); +} + +fn editSpan(old: []const u8, off: usize, len: usize, bytes: []const u8) Span { + const n = old.len - len + bytes.len; + const New = struct { + old: []const u8, + off: usize, + len: usize, + bytes: []const u8, + fn at(t: @This(), i: usize) u8 { + if (i < t.off) return t.old[i]; + if (i < t.off + t.bytes.len) return t.bytes[i - t.off]; + return t.old[i - t.bytes.len + t.len]; + } + }; + const new: New = .{ .old = old, .off = off, .len = len, .bytes = bytes }; + const both = @min(old.len, n); + var head = off; + while (head < both and old[head] == new.at(head)) head += 1; + const rest = both - head; + var tail = @min(old.len - off - len, rest); + while (tail < rest and old[old.len - 1 - tail] == new.at(n - 1 - tail)) tail += 1; + return .{ .at = @intCast(head), .removed = @intCast(old.len - tail - head), .inserted = @intCast(n - tail - head) }; +} + +test "an edit's span is where the texts before and after it differ" { + const reference = struct { + fn span(old: []const u8, new: []const u8) Span { + const both = @min(old.len, new.len); + var head: usize = 0; + while (head < both and old[head] == new[head]) head += 1; + var tail: usize = 0; + while (tail < both - head and old[old.len - 1 - tail] == new[new.len - 1 - tail]) tail += 1; + return .{ .at = @intCast(head), .removed = @intCast(old.len - tail - head), .inserted = @intCast(new.len - tail - head) }; + } + }.span; + var prng = std.Random.DefaultPrng.init(3); + const r = prng.random(); + var old: [24]u8 = undefined; + var new: [48]u8 = undefined; + var bytes: [24]u8 = undefined; + for (0..20000) |_| { + const old_len = r.uintAtMost(usize, old.len); + for (old[0..old_len]) |*c| c.* = "ab"[r.uintLessThan(usize, 2)]; + const off = r.uintAtMost(usize, old_len); + const len = r.uintAtMost(usize, old_len - off); + const n = r.uintAtMost(usize, bytes.len); + for (bytes[0..n]) |*c| c.* = "ab"[r.uintLessThan(usize, 2)]; + @memcpy(new[0..off], old[0..off]); + @memcpy(new[off..][0..n], bytes[0..n]); + @memcpy(new[off + n ..][0 .. old_len - off - len], old[off + len .. old_len]); + const new_len = old_len - len + n; + try std.testing.expectEqual(reference(old[0..old_len], new[0..new_len]), editSpan(old[0..old_len], off, len, bytes[0..n])); + } } /// Records ` ` for a pane a diff --git a/src/ninep/pane.zig b/src/ninep/pane.zig index 289639e9..ab4b2d7d 100644 --- a/src/ninep/pane.zig +++ b/src/ninep/pane.zig @@ -300,14 +300,10 @@ pub fn spliceBody(p: *Pardes, pane: *Pane, q0: usize, q1: usize, bytes: []const // An empty range deleted, or a range replaced by what it holds: no // edit, so no undo step and no new revision. if (std.mem.eql(u8, f.content[lo..hi], bytes[0..take])) return take; - const new = p.gpa.alloc(u8, f.content.len - (hi - lo) + take) catch return null; - @memcpy(new[0..lo], f.content[0..lo]); - @memcpy(new[lo..][0..take], bytes[0..take]); - @memcpy(new[lo + take ..], f.content[hi..]); const join = pane.fs.joined == f.revision; pane.fs.joined = null; if (!pane.fs.nomark and !join) panes.File.pushUndo(p, pane); - panes.File.setContentSpan(p, f, new, .{ .head = lo, .tail = f.content.len - hi }); + if (!panes.File.replace(p, f, lo, hi - lo, bytes[0..take])) return null; return take; } diff --git a/src/rollback.zig b/src/rollback.zig index aebca40d..320e7949 100644 --- a/src/rollback.zig +++ b/src/rollback.zig @@ -64,8 +64,10 @@ pub const Epoch = struct { const Entry = struct { len: usize, alignment: Alignment, epoch: u32, freed: bool = false }; + const vtable: Allocator.VTable = .{ .alloc = alloc, .resize = resize, .remap = remap, .free = free }; + pub fn allocator(e: *Epoch) Allocator { - return .{ .ptr = e, .vtable = &.{ .alloc = alloc, .resize = resize, .remap = remap, .free = free } }; + return .{ .ptr = e, .vtable = &vtable }; } pub fn deinit(e: *Epoch) void { @@ -197,6 +199,13 @@ pub const Epoch = struct { } }; +/// Whether `a` is an epoch's: a replica's core, whose texts a copy holds, +/// so an edit puts a new buffer in place of one and never writes it +/// (File.replace). +pub fn isEpoch(a: Allocator) bool { + return a.vtable == &Epoch.vtable; +} + pub const Copy = struct { meta: Allocator = std.heap.c_allocator, regions: std.ArrayListUnmanaged(Region) = .empty, -- cgit v1.3