summaryrefslogtreecommitdiff
path: root/src/File.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-05 11:02:29 -0300
committerGabriel Schneider <[email protected]>2026-11-05 13:14:28 -0300
commit8640107e29a940d50a5eef0dc7d12689a515d856 (patch)
tree13eb927f31e34d8b50366b3cabc8491c04debdcb /src/File.zig
parent3f1533813b6692a736251e4d467a7f108229ddee (diff)
downloadpardes-8640107e29a940d50a5eef0dc7d12689a515d856.tar.gz
pardes-8640107e29a940d50a5eef0dc7d12689a515d856.zip
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 <[email protected]> Claude-Session: https://claude.ai/code/session_016Y9MNAtZenFv4weoMD3cge
Diffstat (limited to 'src/File.zig')
-rw-r--r--src/File.zig278
1 files changed, 197 insertions, 81 deletions
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]);
}
- for (starts[starts.len - moved ..]) |start| {
- out[i] = start + new.len - old.len;
+ // 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;
+ }
+ 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;