diff options
| author | Gabriel Schneider <[email protected]> | 2026-10-24 14:31:04 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-10-24 15:56:58 -0300 |
| commit | 349bc6fa736edcebd789c5a39885d08f251713a1 (patch) | |
| tree | e6855670062ecd46d31085d442ea71ca701eb09a | |
| parent | 8f5871340b87a0d5399967ccc7eac0d12dc10821 (diff) | |
| download | pardes-349bc6fa736edcebd789c5a39885d08f251713a1.tar.gz pardes-349bc6fa736edcebd789c5a39885d08f251713a1.zip | |
Tables 3/3: what a table costs, an edit's tables shifted by its splice and only its block read again (a fence line in it reads all), a big text read from the top 4 ms a frame (nextWake while busy); Tables.zig's tests registered; an empty delimiter cell's alignment
| -rw-r--r-- | src/Tables.zig | 419 | ||||
| -rw-r--r-- | src/pardes.zig | 3 |
2 files changed, 406 insertions, 16 deletions
diff --git a/src/Tables.zig b/src/Tables.zig index 8038dd65..1dd296f7 100644 --- a/src/Tables.zig +++ b/src/Tables.zig @@ -67,18 +67,42 @@ pub const max_cols = 64; /// A centred column pads both sides of a cell, and a leading `|` its indent. pub const max_pads = 2 * max_cols + 1; -/// The text these tables are of: its revision, where it is and how long. +/// The text these tables are of: its revision, where it is, how long, and +/// how many lines. revision: ?u32 = null, content: usize = 0, len: usize = 0, +lines: usize = 0, list: std.ArrayList(Table) = .empty, widths: std.ArrayList(u16) = .empty, aligns: std.ArrayList(Align) = .empty, +/// The fenced code blocks, opener and closer lines (an unclosed one closes +/// past the end): no table is in one, and an edit to one of these lines +/// changes what every line after it is, so it finds them all again. +fences: std.ArrayList([2]u32) = .empty, +/// Columns in `widths` that no table points at any more (an edit's tables +/// are added at the end); past a bound, everything is found again. +garbage: usize = 0, +/// How many times the whole text was read (for the numbers and the tests). +scans: u32 = 0, +/// Where a reading of the whole text goes on from, until it reaches the +/// end: it is read a frame's budget at a time from the top (`frame_ns`), as +/// Places finds, so opening a big file never holds a frame; rows past it +/// are shown as their source until it gets there. +pending: ?Resume = null, + +/// A scan's place: the next line's byte and number, the fence it is in, +/// and whether the line before ended a block. +const Resume = struct { at: usize, n: u32, fence: ?Fence, prev_blank: bool }; + +/// What one frame spends reading a big text from the top. +pub const frame_ns: u64 = 4 * std.time.ns_per_ms; pub fn deinit(t: *Tables, gpa: std.mem.Allocator) void { t.list.deinit(gpa); t.widths.deinit(gpa); t.aligns.deinit(gpa); + t.fences.deinit(gpa); t.* = .{}; } @@ -102,19 +126,182 @@ pub fn find(t: *const Tables, line: usize) ?*const Table { /// Find the tables of `f`'s text again unless they are of it already. Only /// a markdown file has any; on no memory there are none (the text is shown -/// as it is). -pub fn ensure(t: *Tables, gpa: std.mem.Allocator, f: *const File.State) void { - if (t.current(f)) return; - t.revision = f.revision; - t.content = @intFromPtr(f.content.ptr); - t.len = f.content.len; +/// as it is). After one edit (File.State.splice) the tables it did not +/// touch shift and only the block around it is read again (`reflow`): a +/// keystroke costs its table, not the file. +pub fn ensure(t: *Tables, gpa: std.mem.Allocator, f: *File.State) void { + if (t.current(f)) { + if (t.pending != null) t.go(gpa, f.content, frame_ns); + return; + } + defer { + t.revision = f.revision; + t.content = @intFromPtr(f.content.ptr); + t.len = f.content.len; + } + if (f.output != null or f.mini != null or !isMarkdown(f.path)) { + t.list.clearRetainingCapacity(); + t.pending = null; + return; + } + const starts = File.lineIndex(gpa, f) catch { + t.list.clearRetainingCapacity(); + t.pending = null; + return; + }; + const one_edit = t.revision != null and t.revision.? +% 1 == f.revision and + f.splice.revision == f.revision and f.splice.old_len == t.len; + if (one_edit and t.garbage <= 4 * t.widths.items.len + 1024) { + if (t.pending) |r| { + // An edit past where the reading has got to changes nothing it + // read: it goes on. + if (lineHolding(starts, f.splice.head) >= r.n) { + t.lines = starts.len; + t.go(gpa, f.content, frame_ns); + return; + } + } else if (t.reflow(gpa, f)) |_| return else |_| {} + } + t.begin(starts.len); + t.go(gpa, f.content, frame_ns); +} + +/// Whether a reading of the text is still under way (Pardes.nextWake). +pub fn busy(t: *const Tables) bool { + return t.pending != null; +} + +/// Start reading the whole text again, from the top. +fn begin(t: *Tables, lines: usize) void { t.list.clearRetainingCapacity(); - if (f.output != null or f.mini != null or !isMarkdown(f.path)) return; - scan(t, gpa, f.content) catch { + t.widths.clearRetainingCapacity(); + t.aligns.clearRetainingCapacity(); + t.fences.clearRetainingCapacity(); + t.garbage = 0; + t.scans +%= 1; + t.lines = lines; + t.pending = .{ .at = 0, .n = 0, .fence = null, .prev_blank = true }; +} + +/// Read on for about `budget_ns` (0: to the end). On no memory there are +/// no tables (the text is shown as it is). +fn go(t: *Tables, gpa: std.mem.Allocator, content: []const u8, budget_ns: u64) void { + var at = t.pending orelse return; + const done = t.scanFrom(gpa, content, &at, std.math.maxInt(u32), true, budget_ns) catch { t.list.clearRetainingCapacity(); - t.widths.clearRetainingCapacity(); - t.aligns.clearRetainingCapacity(); + t.pending = null; + return; }; + t.pending = if (done) null else at; +} + +/// Line `n` of a text whose line index is `starts`. +fn lineOf(content: []const u8, starts: []const usize, n: usize) Line { + const start = starts[n]; + const end = if (n + 1 < starts.len) starts[n + 1] - 1 else content.len; + const text = content[start..end]; + return .{ .text = if (text.len > 0 and text[text.len - 1] == '\r') text[0 .. text.len - 1] else text, .start = start, .n = @intCast(n) }; +} + +/// The line byte `at` is on. +fn lineHolding(starts: []const usize, at: usize) usize { + var lo: usize = 0; + var hi: usize = starts.len; + while (lo < hi) { + const mid = (lo + hi) / 2; + if (starts[mid] <= at) lo = mid + 1 else hi = mid; + } + return lo -| 1; +} + +/// The tables after one edit: those it did not touch kept (shifted by the +/// lines it added), the block around it read again. error.Whole when the +/// edit could change what a line far from it is (a fence line in it), or +/// the block is unbounded. +fn reflow(t: *Tables, gpa: std.mem.Allocator, f: *File.State) !void { + const content = f.content; + const starts = try File.lineIndex(gpa, f); + const sp = f.splice; + const delta: i64 = @as(i64, @intCast(starts.len)) - @as(i64, @intCast(t.lines)); + // The edited lines: [a, b] now, [a, b_old] before it. + const a = lineHolding(starts, sp.head); + const b = lineHolding(starts, content.len - sp.tail); + const b_old_i = @as(i64, @intCast(b)) - delta; + if (b_old_i < @as(i64, @intCast(a))) return error.Whole; + const b_old: usize = @intCast(b_old_i); + for (a..b + 1) |n| if (fenceOf(lineOf(content, starts, n).text) != null) return error.Whole; + var inside = false; + for (t.fences.items) |fence| { + if ((fence[0] >= a and fence[0] <= b_old) or (fence[1] >= a and fence[1] <= b_old)) return error.Whole; + if (fence[0] < a and fence[1] > b_old) inside = true; + } + const shift = struct { + fn by(n: u32, d: i64) u32 { + return @intCast(@as(i64, n) + d); + } + }.by; + for (t.fences.items) |*fence| { + if (fence[0] > b_old) fence[0] = shift(fence[0], delta); + if (fence[1] > b_old and fence[1] != std.math.maxInt(u32)) fence[1] = shift(fence[1], delta); + } + // The old tables the edit touched or is next to: [lo_i, hi_i). + const items = t.list.items; + var lo_i: usize = 0; + while (lo_i < items.len and items[lo_i].end < a) lo_i += 1; + var hi_i = lo_i; + while (hi_i < items.len and items[hi_i].first <= b_old + 1) hi_i += 1; + for (items[hi_i..]) |*table| { + table.first = shift(table.first, delta); + table.end = shift(table.end, delta); + } + // Inside fenced code, no table changes. + if (inside) { + t.lines = starts.len; + return; + } + // The block: from the blank line before it to the one after, the old + // tables it touched taken in, never into a neighbouring table. + var r0 = a; + var r1 = b; + if (lo_i < hi_i) { + // Old lines: those past the edit moved by what it added. + const head: usize = items[lo_i].first; + const last: usize = items[hi_i - 1].end - 1; + r0 = @min(r0, if (head > b_old) @as(usize, shift(@intCast(head), delta)) else head); + r1 = @max(r1, if (last > b_old) @as(usize, shift(@intCast(last), delta)) else last); + } + const floor: usize = if (lo_i > 0) items[lo_i - 1].end else 0; + const ceiling: usize = if (hi_i < items.len) items[hi_i].first else starts.len; + var steps: usize = 0; + while (r0 > floor and !blank(lineOf(content, starts, r0 - 1).text)) : (steps += 1) { + if (steps > 512 or fenceOf(lineOf(content, starts, r0 - 1).text) != null) break; + r0 -= 1; + } + steps = 0; + while (r1 + 1 < ceiling and !blank(lineOf(content, starts, r1 + 1).text)) : (steps += 1) { + if (steps > 512) return error.Whole; + if (fenceOf(lineOf(content, starts, r1 + 1).text) != null) break; + r1 += 1; + } + for (items[lo_i..hi_i]) |table| t.garbage += table.cols; + // Its tables, found as the whole text's are, then put in the old ones' place. + const before = t.list.items.len; + const prev = if (r0 == 0) "" else lineOf(content, starts, r0 - 1).text; + const prev_blank = r0 == 0 or blank(prev) or closesAny(prev) or std.mem.startsWith(u8, prev[@min(indentOf(prev), prev.len)..], "#"); + const head = lineOf(content, starts, r0); + var at: Resume = .{ .at = head.start, .n = head.n, .fence = null, .prev_blank = prev_blank }; + _ = try t.scanFrom(gpa, content, &at, @intCast(r1), false, 0); + const fresh = try gpa.dupe(Table, t.list.items[before..]); + defer gpa.free(fresh); + t.list.shrinkRetainingCapacity(before); + try t.list.replaceRange(gpa, lo_i, hi_i - lo_i, fresh); + t.lines = starts.len; +} + +/// Whether a line closes some fence (any fence line does, to the block +/// after it: a header may follow it). +fn closesAny(text: []const u8) bool { + return fenceOf(text) != null; } pub fn isMarkdown(path: []const u8) bool { @@ -267,6 +454,8 @@ fn delimiterCells(text: []const u8, out: *[max_cols]Align) ?usize { while (i < text.len and (text[i] == ' ' or text[i] == '\t')) i += 1; if (i >= text.len) break; if (text[i] == '|') { + // An empty cell (`||`): the scanner counts it, aligned as none. + if (cells < max_cols) out[cells] = .left; cells += 1; pipes += 1; i += 1; @@ -309,19 +498,41 @@ pub fn scan(t: *Tables, gpa: std.mem.Allocator, content: []const u8) !void { t.list.clearRetainingCapacity(); t.widths.clearRetainingCapacity(); t.aligns.clearRetainingCapacity(); - var fence: ?Fence = null; - var prev_blank = true; - var line = lineAt(content, 0, 0); - while (line) |l| { + t.begin(std.mem.count(u8, content, "\n") + 1); + var at = t.pending.?; + _ = try t.scanFrom(gpa, content, &at, std.math.maxInt(u32), true, 0); + t.pending = null; +} + +/// Find the tables whose header is on a line from `at` to `stop`, +/// appending them; with `fences`, keep the fences. With a budget, stop +/// when it is spent, `at` where to go on from. Whether it reached the end +/// (or `stop`). +fn scanFrom(t: *Tables, gpa: std.mem.Allocator, content: []const u8, at: *Resume, stop: u32, fences: bool, budget_ns: u64) !bool { + var fence = at.fence; + var prev_blank = at.prev_blank; + var line = lineAt(content, at.at, at.n); + const t0 = if (budget_ns > 0) panes.Places.nowNs() else 0; + var lines: usize = 0; + while (line) |l| : (lines += 1) { + if (l.n > stop) break; + if (budget_ns > 0 and lines % 256 == 255 and panes.Places.nowNs() -| t0 > budget_ns) { + at.* = .{ .at = l.start, .n = l.n, .fence = fence, .prev_blank = prev_blank }; + return false; + } const following = nextLine(content, l); if (fence) |open| { - if (closes(l.text, open)) fence = null; + if (closes(l.text, open)) { + fence = null; + if (fences) t.fences.items[t.fences.items.len - 1][1] = l.n; + } prev_blank = fence == null; line = following; continue; } if (fenceOf(l.text)) |open| { fence = open; + if (fences) try t.fences.append(gpa, .{ l.n, std.math.maxInt(u32) }); prev_blank = false; line = following; continue; @@ -348,6 +559,7 @@ pub fn scan(t: *Tables, gpa: std.mem.Allocator, content: []const u8) !void { prev_blank = is_blank or std.mem.startsWith(u8, l.text[@min(indentOf(l.text), l.text.len)..], "#"); line = following; } + return true; } /// Take the table whose header is `header`: its rows, its columns' widths @@ -753,3 +965,178 @@ test "tables: typing in a cell re-aligns the table live, and j/k keep the column try testing.expectEqual(@as(i32, 4), pane.body.cur_row); try testing.expectEqual(shown, File.displayOffset(pane, 4, 0, pane.body.cur_col)); } + +test "tables: an edit's tables, shifted and found again around it, are the whole text's" { + const p = try Pardes.init(testing.allocator, .{ .tty_only = true, .cols = 80, .rows = 24 }); + defer p.deinit(); + var frame = std.heap.ArenaAllocator.init(testing.allocator); + defer frame.deinit(); + const pane = try testPane(p, sample ++ "\n```\n| a | b |\n|---|---|\n```\n\n" ++ sample ++ "para\n| x | y |\n|---|--|\n| 1 | 2 |\n", frame.allocator()); + const f = &pane.file.?; + var whole: Tables = .{}; + defer whole.deinit(testing.allocator); + var prng: std.Random.DefaultPrng = .init(11); + const random = prng.random(); + const alphabet = "|||--: \n\nab`"; + var reflowed: usize = 0; + for (0..1500) |round| { + const old = f.content; + const at = random.uintAtMost(usize, old.len); + const cut = if (random.boolean()) @min(old.len - at, random.uintAtMost(usize, 3)) else 0; + const grow = random.uintAtMost(usize, 2); + const new = try p.gpa.alloc(u8, old.len - cut + grow); + @memcpy(new[0..at], old[0..at]); + for (new[at..][0..grow]) |*c| c.* = alphabet[random.uintLessThan(usize, alphabet.len)]; + @memcpy(new[at + grow ..], old[at + cut ..]); + const scans = f.tables.scans; + File.setContent(p, f, new); + f.tables.ensure(p.gpa, f); + if (f.tables.scans == scans) reflowed += 1; + try whole.scan(testing.allocator, f.content); + testing.expectEqual(whole.list.items.len, f.tables.list.items.len) catch |e| { + std.debug.print("round {d}\n{s}\n", .{ round, f.content }); + return e; + }; + for (whole.list.items, f.tables.list.items) |w, mine| { + try testing.expectEqual(w.first, mine.first); + try testing.expectEqual(w.end, mine.end); + try testing.expectEqual(w.cols, mine.cols); + try testing.expectEqual(w.lead, mine.lead); + try testing.expectEqual(w.width, mine.width); + try testing.expectEqualSlices(u16, whole.widths.items[w.col0..][0..w.cols], f.tables.widths.items[mine.col0..][0..mine.cols]); + try testing.expectEqualSlices(Align, whole.aligns.items[w.col0..][0..w.cols], f.tables.aligns.items[mine.col0..][0..mine.cols]); + } + try testing.expectEqual(whole.lines, f.tables.lines); + } + // Most edits took the short way. + try testing.expect(reflowed > 1000); +} + +test "tables: a big text's tables are read a frame's budget at a time from the top, edits on the way kept" { + var big: std.ArrayList(u8) = .empty; + defer big.deinit(testing.allocator); + for (0..1500) |i| try big.print(testing.allocator, "## {d}\n\n| a | b {d} |\n|---|--:|\n| one | two |\n| three | {d} |\n\n", .{ i, i, i * 7 }); + const p = try Pardes.init(testing.allocator, .{ .tty_only = true, .cols = 80, .rows = 24 }); + defer p.deinit(); + var frame = std.heap.ArenaAllocator.init(testing.allocator); + defer frame.deinit(); + const pane = try testPane(p, big.items, frame.allocator()); + const f = &pane.file.?; + // One frame did not read it all, and asks for the next. + try testing.expect(f.tables.busy()); + try testing.expect(p.nextWake() != null); + // The top's tables are found already: the view is right at once. + try testing.expect(File.rowTable(pane, 2) != null); + const reached = f.tables.pending.?.n; + // An edit past where it got to: it goes on; one before it: from the top. + var edits: usize = 0; + var frames: usize = 0; + while (f.tables.busy()) : (frames += 1) { + if (edits < 2) { + const at = if (edits == 0) f.content.len - 3 else 10; + const new = try std.mem.concat(p.gpa, u8, &.{ f.content[0..at], "x", f.content[at..] }); + File.setContent(p, f, new); + edits += 1; + } + _ = frame.reset(.retain_capacity); + _ = try p.render(frame.allocator()); + try testing.expect(frames < 10_000); + } + try testing.expect(reached < File.nlines(p.gpa, f)); + var whole: Tables = .{}; + defer whole.deinit(testing.allocator); + try whole.scan(testing.allocator, f.content); + try testing.expectEqual(whole.list.items.len, f.tables.list.items.len); + for (whole.list.items, f.tables.list.items) |w, mine| { + try testing.expectEqual(w.first, mine.first); + try testing.expectEqual(w.end, mine.end); + try testing.expectEqual(w.width, mine.width); + } +} + +test "zz tables timings on a big markdown file (TABLES_TIMES=<path>)" { + const path_z = std.c.getenv("TABLES_TIMES") orelse return error.SkipZigTest; + const path = std.mem.span(path_z); + const io = testing.io; + const bytes = try std.Io.Dir.cwd().readFileAlloc(io, path, testing.allocator, .limited(16 << 20)); + defer testing.allocator.free(bytes); + const now = panes.Places.nowNs; + var report: std.ArrayList(u8) = .empty; + defer report.deinit(testing.allocator); + { + var t: Tables = .{}; + defer t.deinit(testing.allocator); + var worst: u64 = 0; + var sum: u64 = 0; + for (0..5) |_| { + const t0 = now(); + try t.scan(testing.allocator, bytes); + const d = now() - t0; + sum += d; + worst = @max(worst, d); + } + try report.print(testing.allocator, "scan of {d} bytes: {d} tables, mean {d} us, worst {d} us\n", .{ bytes.len, t.list.items.len, sum / 5 / 1000, worst / 1000 }); + } + // The same text as markdown and as plain text: what the tables cost a + // frame and an edit. + for ([_][]const u8{ "/stress.md", "/stress.txt" }) |name| { + const p = try Pardes.init(testing.allocator, .{ .tty_only = true, .cols = 160, .rows = 50 }); + defer p.deinit(); + var frame = std.heap.ArenaAllocator.init(testing.allocator); + defer frame.deinit(); + const pane = try p.setTestFile(bytes); + p.gpa.free(pane.file.?.path); + pane.file.?.path = try p.gpa.dupe(u8, name); + { + var t0 = now(); + _ = try p.render(frame.allocator()); + const first = now() - t0; + var frames: usize = 1; + var worst: u64 = first; + t0 = now(); + while (pane.file.?.tables.busy()) : (frames += 1) { + const t1 = now(); + _ = frame.reset(.retain_capacity); + _ = try p.render(frame.allocator()); + worst = @max(worst, now() - t1); + } + try report.print(testing.allocator, "{s}: the first frame {d} us; the tables read in {d} frames, the worst {d} us\n", .{ name, first / 1000, frames, worst / 1000 }); + } + // Into the middle of a table half way down. + var line: usize = File.nlines(p.gpa, &pane.file.?) / 2; + while (!std.mem.startsWith(u8, File.sourceLine(pane, @intCast(line)), "| ") or + std.mem.indexOf(u8, File.sourceLine(pane, @intCast(line)), "col") != null) line += 1; + pane.body.cur_row = @intCast(line + 2); + pane.body.cur_col = 2; + pane.ensureCursorVisible(); + _ = frame.reset(.retain_capacity); + _ = try p.render(frame.allocator()); + const Clock = struct { + fn step(pp: *Pardes, fr: *std.heap.ArenaAllocator, ev: pardes.Event) !u64 { + const t0 = panes.Places.nowNs(); + pp.update(ev); + _ = fr.reset(.retain_capacity); + _ = try pp.render(fr.allocator()); + return panes.Places.nowNs() - t0; + } + }; + var sum: u64 = 0; + var worst: u64 = 0; + for (0..10) |_| { + const d = try Clock.step(p, &frame, .{ .key = .{ .cp = 'j', .text = "j" } }); + sum += d; + worst = @max(worst, d); + } + try report.print(testing.allocator, "{s}: j and its frame: mean {d} us, worst {d} us\n", .{ name, sum / 10 / 1000, worst / 1000 }); + _ = try Clock.step(p, &frame, .{ .key = .{ .cp = 'i', .text = "i" } }); + sum = 0; + worst = 0; + for (0..10) |_| { + const d = try Clock.step(p, &frame, .{ .key = .{ .cp = 'x', .text = "x" } }); + sum += d; + worst = @max(worst, d); + } + try report.print(testing.allocator, "{s}: a letter typed in a cell and its frame: mean {d} us, worst {d} us\n", .{ name, sum / 10 / 1000, worst / 1000 }); + } + std.debug.print("\n{s}", .{report.items}); +} diff --git a/src/pardes.zig b/src/pardes.zig index 7f79f094..79a2e5a5 100644 --- a/src/pardes.zig +++ b/src/pardes.zig @@ -494,6 +494,7 @@ test { _ = @import("Names.zig"); _ = @import("Stream.zig"); _ = @import("Finder.zig"); + _ = @import("Tables.zig"); } pub const Builtin = builtins.registry.Builtin(); @@ -7655,6 +7656,8 @@ pub const Pardes = struct { if (p.chrome_animation.isActive() or p.presentation.animating()) return next; // Places still to find resume on the next frame. for (p.panes) |slot| if (slot) |pane| if (pane.places.busy(pane)) return next; + // A markdown text's tables still being read from the top (Tables.zig). + for (p.panes) |slot| if (slot) |pane| if (pane.file) |f| if (f.tables.busy()) return next; if (panes.Query.busy(p)) return next; // A typed Grep waiting out its pause. const streaming = p.stream.wake(next); |
