From 7452ff1caf51942ba9561acf2aa284d50435b8c3 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Mon, 3 Aug 2026 10:02:00 -0300 Subject: optimize and harness PDF sections navigation --- src/pardes.zig | 178 +++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 147 insertions(+), 31 deletions(-) (limited to 'src/pardes.zig') diff --git a/src/pardes.zig b/src/pardes.zig index 7243cf37..d490c6f3 100644 --- a/src/pardes.zig +++ b/src/pardes.zig @@ -1271,6 +1271,67 @@ test "PDF section rows preserve DFS ordinals and sanitise hierarchy" { ); try std.testing.expect(PdfSectionRows.resolve(&entries, 4) == null); try std.testing.expect(PdfSectionRows.resolve(&entries, 5) == null); + const resolved = try PdfSectionRows.resolveOrdinals(std.testing.allocator, &entries); + defer std.testing.allocator.free(resolved); + for (entries, 0..) |_, ordinal| { + const single = PdfSectionRows.resolve(&entries, ordinal); + if (resolved[ordinal] == std.math.maxInt(usize)) { + try std.testing.expect(single == null); + } else { + const bulk = PdfSectionRows.usableDestination(entries[resolved[ordinal]].destination) orelse + return error.MissingBulkPdfSectionDestination; + try std.testing.expect(single != null); + try std.testing.expect(std.meta.eql(single.?, bulk)); + } + } + + // Every allocation site in the ordinal table and output growth remains + // atomic: the testing allocator sees each induced failure cleaned up + // before the first index at which the whole render can succeed. + var rendered = false; + for (0..64) |fail_index| { + var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ + .fail_index = fail_index, + }); + const failure_gpa = failing.allocator(); + const attempt = PdfSectionRows.render(failure_gpa, "/tmp/manual.pdf", &entries) catch |err| { + try std.testing.expectEqual(error.OutOfMemory, err); + continue; + }; + failure_gpa.free(attempt); + rendered = true; + break; + } + try std.testing.expect(rendered); +} + +test "bulk PDF section resolution matches single Look policy across DFS boundaries" { + if (!pdf_enabled) return; + const E = pdf_impl.OutlineEntry; + const entries = [_]E{ + .{ .depth = 0, .title = "Resolved root", .is_open = true, .flags = 0, .color = @splat(0), .destination = .none }, + .{ .depth = 1, .title = "Unsafe branch", .is_open = true, .flags = 0, .color = @splat(0), .destination = .{ .external = "javascript:unsafe" } }, + .{ .depth = 2, .title = "Safe grandchild", .is_open = false, .flags = 0, .color = @splat(0), .destination = .{ .internal = .{ .page = 1, .x = 4, .y = 8 } } }, + .{ .depth = 1, .title = "Unresolved child", .is_open = false, .flags = 0, .color = @splat(0), .destination = .none }, + .{ .depth = 1, .title = "Sibling", .is_open = false, .flags = 0, .color = @splat(0), .destination = .{ .internal = .{ .page = 2, .x = null, .y = null } } }, + .{ .depth = 0, .title = "Unresolved root", .is_open = false, .flags = 0, .color = @splat(0), .destination = .none }, + .{ .depth = 0, .title = "Next root", .is_open = false, .flags = 0, .color = @splat(0), .destination = .{ .internal = .{ .page = 3, .x = null, .y = null } } }, + }; + const bulk = try PdfSectionRows.resolveOrdinals(std.testing.allocator, &entries); + defer std.testing.allocator.free(bulk); + const none = std.math.maxInt(usize); + try std.testing.expectEqualSlices(usize, &.{ 2, none, 2, none, 4, none, 6 }, bulk); + for (entries, 0..) |_, ordinal| { + const single = PdfSectionRows.resolve(&entries, ordinal); + if (bulk[ordinal] == none) { + try std.testing.expect(single == null); + } else { + const destination = PdfSectionRows.usableDestination(entries[bulk[ordinal]].destination) orelse + return error.MissingBoundaryPdfSectionDestination; + try std.testing.expect(single != null); + try std.testing.expect(std.meta.eql(single.?, destination)); + } + } } test "PdfSections output, Look, and n/N share exact cached outline destinations" { @@ -1330,6 +1391,19 @@ test "PdfSections output, Look, and n/N share exact cached outline destinations" try std.testing.expectEqual(output_revision, p.panes[output_id].?.file.?.revision); try std.testing.expectEqual(outline_ptr, pdf_pane.pdf.?.outline.?.entries.ptr); + // The clean remembered path is a pure re-arm: even an allocator which + // rejects its first request is never consulted, and the outline/content + // identities remain untouched. + var failing = std.testing.FailingAllocator.init(gpa, .{ .fail_index = 0 }); + const ordinary_gpa = p.gpa; + p.gpa = failing.allocator(); + p.openPdfSections(0); + p.gpa = ordinary_gpa; + try std.testing.expectEqual(@as(usize, 0), failing.alloc_index); + try std.testing.expect(!failing.has_induced_failure); + try std.testing.expectEqual(outline_ptr, pdf_pane.pdf.?.outline.?.entries.ptr); + try std.testing.expectEqual(output_revision, p.panes[output_id].?.file.?.revision); + // n and N execute the generated row through ordinary Look. The root and // child intentionally resolve to the same exact XYZ destination. p.active = 0; @@ -3116,8 +3190,8 @@ const PdfView = if (pdf_enabled) struct { /// Pure outline-to-row policy. Keeping destination resolution and title /// sanitisation together makes the ordinal written into a row exactly the /// ordinal Look later resolves; neither path invents a second flattened tree. -const PdfSectionRows = if (pdf_enabled) struct { - fn usableDestination(destination: pdf_impl.OutlineDestination) ?pdf_impl.OutlineDestination { +pub const PdfSectionRows = if (pdf_enabled) struct { + pub fn usableDestination(destination: pdf_impl.OutlineDestination) ?pdf_impl.OutlineDestination { return switch (destination) { .internal => destination, .external => |uri| if (safeHttpUri(uri)) destination else null, @@ -3144,7 +3218,7 @@ const PdfSectionRows = if (pdf_enabled) struct { /// A structural node goes to the first later DFS entry still below it /// which carries a usable destination. Nodes with their own unusable URI /// are not structural: omit them instead of silently changing their link. - fn resolve(entries: []const pdf_impl.OutlineEntry, ordinal: usize) ?pdf_impl.OutlineDestination { + pub fn resolve(entries: []const pdf_impl.OutlineEntry, ordinal: usize) ?pdf_impl.OutlineDestination { if (ordinal >= entries.len) return null; const entry = entries[ordinal]; if (entry.destination != .none) return usableDestination(entry.destination); @@ -3154,6 +3228,43 @@ const PdfSectionRows = if (pdf_enabled) struct { return null; } + /// Resolve every rendered row in one DFS pass. `resolve` above stays the + /// public single-ordinal policy used by Look; bulk materialisation avoids + /// rescanning the same descendant chain for every structural ancestor. + /// The one-usize-per-entry table is transient (32 KiB at MuPDF's 4096 + /// outline-item limit) and stores source ordinals, so URI slices continue + /// to borrow from the document-owned outline instead of being copied. + fn resolveOrdinals( + gpa: std.mem.Allocator, + entries: []const pdf_impl.OutlineEntry, + ) ![]usize { + const unresolved = std.math.maxInt(usize); + const ordinals = try gpa.alloc(usize, entries.len); + @memset(ordinals, unresolved); + + const Pending = struct { depth: u8, ordinal: usize }; + // OutlineEntry.depth is u8. A valid DFS path therefore cannot hold + // more than 256 simultaneously unresolved ancestors, independent of + // the tighter limit enforced by the MuPDF bridge. + var pending: [256]Pending = undefined; + var pending_len: usize = 0; + for (entries, 0..) |entry, ordinal| { + while (pending_len > 0 and pending[pending_len - 1].depth >= entry.depth) + pending_len -= 1; + + if (usableDestination(entry.destination) != null) { + ordinals[ordinal] = ordinal; + for (pending[0..pending_len]) |ancestor| + ordinals[ancestor.ordinal] = ordinal; + pending_len = 0; + } else if (entry.destination == .none) { + pending[pending_len] = .{ .depth = entry.depth, .ordinal = ordinal }; + pending_len += 1; + } + } + return ordinals; + } + fn appendTitle( out: *std.ArrayList(u8), gpa: std.mem.Allocator, @@ -3196,15 +3307,19 @@ const PdfSectionRows = if (pdf_enabled) struct { if (!wrote) try out.appendSlice(gpa, "[empty title]"); } - fn render( + pub fn render( gpa: std.mem.Allocator, path: []const u8, entries: []const pdf_impl.OutlineEntry, ) ![]u8 { + const ordinals = try resolveOrdinals(gpa, entries); + defer gpa.free(ordinals); var out: std.ArrayList(u8) = .empty; errdefer out.deinit(gpa); for (entries, 0..) |entry, ordinal| { - const destination = resolve(entries, ordinal) orelse continue; + const resolved = ordinals[ordinal]; + if (resolved == std.math.maxInt(usize)) continue; + const destination = usableDestination(entries[resolved].destination) orelse unreachable; switch (destination) { .internal => |internal| try out.print(gpa, "{s}:{d}:{d} ", .{ path, @@ -3214,7 +3329,7 @@ const PdfSectionRows = if (pdf_enabled) struct { .external => |uri| try out.print(gpa, "{s} ", .{uri}), .none => unreachable, } - for (0..entry.depth) |_| try out.appendSlice(gpa, " "); + try out.appendNTimes(gpa, ' ', @as(usize, entry.depth) * 2); try appendTitle(&out, gpa, entry.title); try out.append(gpa, '\n'); } @@ -9522,6 +9637,31 @@ pub const Pardes = struct { }; } + /// Re-arm a remembered, unedited +PdfSections pane without consulting + /// MuPDF or rebuilding bytes which cannot have changed while its owning + /// document remains open. Serial + generated revision are the two cache + /// guards: a closed/reused slot or user edit falls through to a fresh + /// materialisation below. + fn rearmCleanPdfSections(p: *Pardes, id: usize, pane: *Pane, pv: *PdfView) bool { + const remembered = pv.sections_output orelse return false; + if (remembered.pane >= p.panes.len) return false; + const result = p.panes[remembered.pane] orelse return false; + if (result.serial != remembered.serial or !isPdfSectionsOutput(result)) return false; + const file = &result.file.?; + if (file.revision != remembered.revision) return false; + + file.scroll = 0; + result.cur_row = 0; + result.cur_col = 0; + result.msel.active = false; + result.vsel.active = false; + result.nsel = 0; + pane.search_pane = remembered.pane; + pane.search_row = null; + p.active = id; + return true; + } + /// Lazily materialise this pane's cached MuPDF outline as a location list. /// A clean live output is refreshed in place; an edited, closed, or reused /// slot is never overwritten. Focus and n/N ownership stay on the PDF. @@ -9529,37 +9669,13 @@ pub const Pardes = struct { if (comptime pdf_enabled) { const pane = p.panes[id] orelse return; const pv = &(pane.pdf orelse return); + if (p.rearmCleanPdfSections(id, pane, pv)) return; const entries: []const pdf_impl.OutlineEntry = if (p.ensurePdfOutline(pv)) |outline| outline.entries else &.{}; const content = PdfSectionRows.render(p.gpa, pv.path, entries) catch return; - if (pv.sections_output) |remembered| { - if (remembered.pane < p.panes.len) if (p.panes[remembered.pane]) |result| { - if (result.serial == remembered.serial and isPdfSectionsOutput(result)) { - const file = &result.file.?; - if (file.revision == remembered.revision) { - if (std.mem.eql(u8, file.content, content)) - p.gpa.free(content) - else - file_pane.setContent(p, file, content); - pv.sections_output.?.revision = file.revision; - file.scroll = 0; - result.cur_row = 0; - result.cur_col = 0; - result.msel.active = false; - result.vsel.active = false; - result.nsel = 0; - pane.search_pane = remembered.pane; - pane.search_row = null; - p.active = id; - return; - } - } - }; - } - const free = p.freeSlot() orelse { p.gpa.free(content); return; -- cgit v1.3