From 3f4f26e0e40d06427e72f72e760d01adcdc0326c Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Tue, 15 Sep 2026 18:52:46 -0300 Subject: Reuse bounded source analysis and speed up result context traversal --- src/locations.zig | 27 +++--- src/locations_cache.zig | 213 ++++++++++++++++++++++++++++++++++++++++++++++++ src/main.zig | 1 + src/pardes.zig | 2 + src/syntax.zig | 123 ++++++++++++++++++++++++---- 5 files changed, 342 insertions(+), 24 deletions(-) create mode 100644 src/locations_cache.zig (limited to 'src') diff --git a/src/locations.zig b/src/locations.zig index 97caf1d9..b34f7a6f 100644 --- a/src/locations.zig +++ b/src/locations.zig @@ -158,17 +158,19 @@ const Pending = struct { } }; -fn sourceText(p: *pardes.Pardes, arena: std.mem.Allocator, dir: []const u8, path: []const u8) ?[]const u8 { +const Source = struct { path: []const u8, bytes: []const u8 }; + +fn sourceText(p: *pardes.Pardes, arena: std.mem.Allocator, dir: []const u8, path: []const u8) ?Source { if (std.ascii.eqlIgnoreCase(std.fs.path.extension(path), ".pdf")) return null; const lexical = std.fs.path.resolvePosix(arena, &.{ dir, path }) catch return null; var pathbuf: [4096]u8 = undefined; const full = if (filesystem.resolve(p, path, dir, &pathbuf)) |resolved| resolved.path else lexical; for (p.panes) |slot| if (slot) |pane| { - if (pane.file) |file| if (file.output == null and (std.mem.eql(u8, file.path, full) or std.mem.eql(u8, file.path, lexical))) return file.content; + if (pane.file) |file| if (file.output == null and (std.mem.eql(u8, file.path, full) or std.mem.eql(u8, file.path, lexical))) return .{ .path = lexical, .bytes = file.content }; }; const bytes = filesystem.read(p, full) catch return null; defer p.gpa.free(bytes); - return arena.dupe(u8, bytes) catch null; + return .{ .path = lexical, .bytes = arena.dupe(u8, bytes) catch return null }; } /// Inputs are sorted results. Expand each source group, merge context with @@ -193,18 +195,22 @@ pub fn format(p: *pardes.Pardes, dir: []const u8, input: []const u8, anchor: ?us const group_start = pending.items.len; try pending.appendSlice(arena, matches.items[first..end]); if (expand and (p.locations_config.context > 0 or p.locations_config.tscontext)) { - if (sourceText(p, arena, dir, path)) |source| { + if (sourceText(p, arena, dir, path)) |text| { + const source = text.bytes; var source_lines: std.ArrayList([]const u8) = .empty; var source_split = std.mem.splitScalar(u8, source, '\n'); while (source_split.next()) |line| try source_lines.append(arena, line); const count = source_lines.items.len; const wanted = try arena.alloc(u8, count); @memset(wanted, 0); - const source_colors = syntax.highlightFileRange(arena, path, source, 0, source.len) catch &.{}; - const declarations = if (p.locations_config.tscontext) - syntax.contextDeclarations(arena, path, source) catch &.{} - else - &.{}; + // Muted declaration headers do not need a source-color pass. + // Exact bytes include unsaved edits and virtual/remote sources. + var cached = p.locations_cache.get(p.tree_sitter_gpa, text.path, source, p.locations_config.tscontext, p.locations_config.context > 0) catch + @import("locations_cache.zig").Result{ .analysis = syntax.analyzeSource(arena, text.path, source, p.locations_config.tscontext, p.locations_config.context > 0) catch .{} }; + defer cached.deinit(p.tree_sitter_gpa); + const analysis = cached.analysis; + const source_colors = analysis.colors; + const declarations = if (p.locations_config.tscontext) analysis.declarations else &.{}; for (pending.items[group_start..]) |*match| { const row = match.at.line -| 1; if (row >= count) continue; @@ -235,7 +241,8 @@ pub fn format(p: *pardes.Pardes, dir: []const u8, input: []const u8, anchor: ?us const declaration = kind & declaration_context != 0; const colors = if (!declaration and offset + line.len <= source_colors.len) source_colors[offset..][0..line.len] else &.{}; const hidden = !declaration or !p.locations_config.tslocations or kind & declaration_start == 0; - try appendContext(arena, &pending, path, line, row, declaration, hidden, colors); + // Later source groups may evict this analysis from the cache. + try appendContext(arena, &pending, path, line, row, declaration, hidden, try arena.dupe(u8, colors)); } } } diff --git a/src/locations_cache.zig b/src/locations_cache.zig new file mode 100644 index 00000000..a079226b --- /dev/null +++ b/src/locations_cache.zig @@ -0,0 +1,213 @@ +const std = @import("std"); +const syntax = @import("syntax.zig"); + +/// A cache hit borrows its analysis; an entry too large to retain transfers +/// ownership instead. Call deinit after consuming either result. +pub const Result = struct { + analysis: syntax.SourceAnalysis, + owned: bool = false, + + pub fn deinit(result: *Result, gpa: std.mem.Allocator) void { + if (result.owned) result.analysis.deinit(gpa); + result.* = undefined; + } +}; + +/// Owned source snapshots keep analysis valid across filesystem changes and +/// borrowed editor buffers. Entries are ordered from least to most recent. +pub const Cache = struct { + pub const max_bytes = 64 * 1024 * 1024; + pub const max_entries = 64; + + const Entry = struct { + path: []u8, + source: []u8, + analysis: syntax.SourceAnalysis, + declarations_ready: bool, + colors_ready: bool, + + fn size(entry: Entry) usize { + return entry.path.len + entry.source.len + entry.analysis.colors.len + + entry.analysis.declarations.len * @sizeOf(syntax.ContextDeclaration); + } + + fn deinit(entry: *Entry, gpa: std.mem.Allocator) void { + gpa.free(entry.path); + gpa.free(entry.source); + entry.analysis.deinit(gpa); + } + }; + + entries: [max_entries]Entry = undefined, + len: usize = 0, + bytes: usize = 0, + analyses: usize = 0, + hits: usize = 0, + + pub fn deinit(cache: *Cache, gpa: std.mem.Allocator) void { + for (cache.entries[0..cache.len]) |*entry| entry.deinit(gpa); + cache.* = .{}; + } + + /// Borrowed slices remain valid until the next get or cache deinit; an + /// owned result remains valid until Result.deinit. All calls for this + /// cache must use the same allocator. Unsupported languages + /// are cached too, including their empty analysis arrays. + pub fn get(cache: *Cache, gpa: std.mem.Allocator, path: []const u8, source: []const u8, want_declarations: bool, want_colors: bool) !Result { + return cache.getBounded(gpa, path, source, want_declarations, want_colors, max_bytes); + } + + fn getBounded(cache: *Cache, gpa: std.mem.Allocator, path: []const u8, source: []const u8, want_declarations: bool, want_colors: bool, budget: usize) !Result { + if (source.len > budget or path.len > budget - source.len) return error.SourceTooLarge; + var previous: ?usize = null; + var declarations = want_declarations; + var colors = want_colors; + for (cache.entries[0..cache.len], 0..) |entry, index| { + if (!std.mem.eql(u8, entry.path, path)) continue; + previous = index; + if (!std.mem.eql(u8, entry.source, source)) break; + if ((!want_declarations or entry.declarations_ready) and (!want_colors or entry.colors_ready)) { + // Moving the small ownership record keeps the underlying + // allocations intact and avoids timestamp/overflow state. + std.mem.copyForwards(Entry, cache.entries[index .. cache.len - 1], cache.entries[index + 1 .. cache.len]); + cache.entries[cache.len - 1] = entry; + cache.hits +|= 1; + return .{ .analysis = entry.analysis }; + } + declarations = declarations or entry.declarations_ready; + colors = colors or entry.colors_ready; + break; + } + // A supported full-source color map needs one byte per source byte. + // Reject that known minimum before parsing, so the caller's uncached + // path does not repeat an expensive analysis for oversized inputs. + const input_bytes = path.len + source.len; + if (colors and syntax.supportsPath(path) and source.len > budget - input_bytes) return error.SourceTooLarge; + var analysis = try syntax.analyzeSource(gpa, path, source, declarations, colors); + errdefer analysis.deinit(gpa); + cache.analyses +|= 1; + const analysis_bytes = analysis.colors.len + analysis.declarations.len * @sizeOf(syntax.ContextDeclaration); + if (analysis_bytes > budget - input_bytes) return .{ .analysis = analysis, .owned = true }; + const owned_path = try gpa.dupe(u8, path); + errdefer gpa.free(owned_path); + const owned_source = try gpa.dupe(u8, source); + errdefer gpa.free(owned_source); + const next: Entry = .{ + .path = owned_path, + .source = owned_source, + .analysis = analysis, + .declarations_ready = declarations, + .colors_ready = colors, + }; + // Commit only after every allocation succeeds. A failed refresh leaves + // the previous cached snapshot usable by the next request. + if (previous) |index| cache.remove(gpa, index); + while (cache.len == max_entries or cache.bytes > budget - next.size()) cache.remove(gpa, 0); + cache.entries[cache.len] = next; + cache.len += 1; + cache.bytes += next.size(); + return .{ .analysis = next.analysis }; + } + + fn remove(cache: *Cache, gpa: std.mem.Allocator, index: usize) void { + cache.bytes -= cache.entries[index].size(); + cache.entries[index].deinit(gpa); + std.mem.copyForwards(Entry, cache.entries[index .. cache.len - 1], cache.entries[index + 1 .. cache.len]); + cache.len -= 1; + } +}; + +test "locations cache validates exact source and path and upgrades analysis" { + const gpa = std.testing.allocator; + syntax.start(gpa); + defer syntax.stop(); + var cache: Cache = .{}; + defer cache.deinit(gpa); + const source = "const Thing = struct {\n value: u32,\n};\n"; + _ = try cache.get(gpa, "a.zig", source, true, false); + try std.testing.expectEqual(@as(usize, 1), cache.analyses); + _ = try cache.get(gpa, "a.zig", source, true, false); + try std.testing.expectEqual(@as(usize, 1), cache.analyses); + try std.testing.expectEqual(@as(usize, 1), cache.hits); + _ = try cache.get(gpa, "a.zig", source, false, true); + try std.testing.expectEqual(@as(usize, 2), cache.analyses); + try std.testing.expect(cache.entries[0].declarations_ready and cache.entries[0].colors_ready); + _ = try cache.get(gpa, "a.zig", source, true, true); + try std.testing.expectEqual(@as(usize, 2), cache.analyses); + _ = try cache.get(gpa, "a.zig", "const Thing = struct {\n other: u32,\n};\n", true, true); + try std.testing.expectEqual(@as(usize, 3), cache.analyses); + try std.testing.expectEqual(@as(usize, 1), cache.len); + _ = try cache.get(gpa, "a.txt", source, true, true); + try std.testing.expectEqual(@as(usize, 4), cache.analyses); + try std.testing.expectEqual(@as(usize, 2), cache.len); +} + +test "locations cache bounds memory and entries and evicts least recently used" { + const gpa = std.testing.allocator; + var cache: Cache = .{}; + defer cache.deinit(gpa); + for (0..Cache.max_entries) |index| { + var path: [32]u8 = undefined; + _ = try cache.get(gpa, try std.fmt.bufPrint(&path, "{d}.unknown", .{index}), "source", false, false); + } + _ = try cache.get(gpa, "0.unknown", "source", false, false); + _ = try cache.get(gpa, "new.unknown", "source", false, false); + try std.testing.expectEqual(Cache.max_entries, cache.len); + try std.testing.expectEqualStrings("2.unknown", cache.entries[0].path); + const count = cache.analyses; + _ = try cache.get(gpa, "0.unknown", "source", false, false); + try std.testing.expectEqual(count, cache.analyses); + cache.deinit(gpa); + _ = try cache.getBounded(gpa, "a.unknown", "source", false, false, 40); + _ = try cache.getBounded(gpa, "b.unknown", "source", false, false, 40); + _ = try cache.getBounded(gpa, "c.unknown", "source", false, false, 40); + try std.testing.expectEqual(@as(usize, 2), cache.len); + try std.testing.expect(cache.bytes <= 40); + try std.testing.expectEqualStrings("b.unknown", cache.entries[0].path); + try std.testing.expectError(error.SourceTooLarge, cache.getBounded(gpa, "large.unknown", "x" ** 41, false, false, 40)); + try std.testing.expectEqual(@as(usize, 2), cache.len); + if (syntax.supportsPath("large.zig")) { + const before = cache.analyses; + try std.testing.expectError(error.SourceTooLarge, cache.getBounded(gpa, "large.zig", "x" ** 25, true, true, 40)); + try std.testing.expectEqual(before, cache.analyses); + } + cache.deinit(gpa); + try std.testing.expectEqual(@as(usize, 0), cache.bytes); + try std.testing.expectEqual(@as(usize, 0), cache.len); +} + +test "locations cache keeps its previous snapshot after allocation failure" { + var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{}); + const gpa = failing.allocator(); + var cache: Cache = .{}; + defer cache.deinit(gpa); + _ = try cache.get(gpa, "a.unknown", "old bytes", false, false); + const retained = cache.bytes; + failing.fail_index = failing.alloc_index; + try std.testing.expectError(error.OutOfMemory, cache.get(gpa, "a.unknown", "new bytes", false, false)); + try std.testing.expectEqual(@as(usize, 1), cache.len); + try std.testing.expectEqual(retained, cache.bytes); + try std.testing.expectEqualStrings("old bytes", cache.entries[0].source); + // This succeeds with allocations still disabled because the old entry + // remains valid and the hit path moves ownership records only. + _ = try cache.get(gpa, "a.unknown", "old bytes", false, false); + try std.testing.expectEqual(@as(usize, 1), cache.hits); +} + +test "locations cache transfers oversized completed analysis without reparsing" { + if (!syntax.supportsPath("large.zig")) return error.SkipZigTest; + const gpa = std.testing.allocator; + syntax.start(gpa); + defer syntax.stop(); + var cache: Cache = .{}; + defer cache.deinit(gpa); + const source = "const Thing = struct {\n value: u32,\n};\n"; + const budget = "large.zig".len + source.len; + var result = try cache.getBounded(gpa, "large.zig", source, true, false, budget); + defer result.deinit(gpa); + try std.testing.expect(result.owned); + try std.testing.expect(result.analysis.declarations.len > 0); + try std.testing.expectEqual(@as(usize, 1), cache.analyses); + try std.testing.expectEqual(@as(usize, 0), cache.len); + try std.testing.expectEqual(@as(usize, 0), cache.bytes); +} diff --git a/src/main.zig b/src/main.zig index 2ee295e1..40ec8667 100644 --- a/src/main.zig +++ b/src/main.zig @@ -369,6 +369,7 @@ test { _ = pardes.config.User; _ = @import("crash.zig"); _ = @import("memory.zig"); + _ = @import("locations_cache.zig"); _ = @import("fs.zig"); _ = @import("detached/wire.zig"); _ = @import("detached/server.zig"); diff --git a/src/pardes.zig b/src/pardes.zig index 2729ef93..c78d4702 100644 --- a/src/pardes.zig +++ b/src/pardes.zig @@ -5969,6 +5969,7 @@ pub const Pardes = struct { next_serial: u32 = 0, settings: config.Runtime = .{ .font = .{ .tagline_percent = config.gui_tagline_font_percent } }, locations_config: locations_config.Config = .{}, + locations_cache: @import("locations_cache.zig").Cache = .{}, tty_filter_palette: panes.Terminal.FilterPalette = .{}, font_request_taken: bool = false, custom_theme: ?Theme = null, @@ -6212,6 +6213,7 @@ pub const Pardes = struct { if (p.custom_theme) |theme_value| std.zon.parse.free(gpa, theme_value); if (p.chord_arg) |a| gpa.free(a); if (p.pipe_wait) |*wait| wait.deinit(gpa); + p.locations_cache.deinit(p.tree_sitter_gpa); p.fs.deinit(gpa); p.shell_rows.reset(gpa); p.scratch.deinit(); diff --git a/src/syntax.zig b/src/syntax.zig index 9e31669f..e637bf67 100644 --- a/src/syntax.zig +++ b/src/syntax.zig @@ -376,28 +376,58 @@ pub fn supportsPath(path: []const u8) bool { return false; } -pub fn contextDeclarations(gpa: std.mem.Allocator, path: []const u8, content: []const u8) ![]ContextDeclaration { - if (!enabled or content.len == 0) return &.{}; - const selected = (try forExt(std.fs.path.extension(path))) orelse return &.{}; - const tree = selected.parser.parseString(content, null) orelse return &.{}; +/// Owned source analysis. Both slices use the allocator passed to analyzeSource. +/// The parsed tree is released before returning; callers can cache this result. +pub const SourceAnalysis = struct { + declarations: []ContextDeclaration = &.{}, + colors: []u8 = &.{}, + + pub fn deinit(self: *SourceAnalysis, gpa: std.mem.Allocator) void { + gpa.free(self.declarations); + gpa.free(self.colors); + self.* = .{}; + } +}; + +pub fn analyzeSource(gpa: std.mem.Allocator, path: []const u8, content: []const u8, want_declarations: bool, want_colors: bool) !SourceAnalysis { + if (!enabled or content.len == 0 or (!want_declarations and !want_colors)) return .{}; + const selected = (try forExt(std.fs.path.extension(path))) orelse return .{}; + const tree = selected.parser.parseString(content, null) orelse return .{}; defer tree.destroy(); + var result: SourceAnalysis = .{}; + errdefer result.deinit(gpa); + if (want_declarations) result.declarations = try declarationsFromTree(gpa, content, tree); + if (want_colors) { + result.colors = try gpa.alloc(u8, content.len); + @memset(result.colors, 0); + paintTree(result.colors, content, selected, tree); + } + return result; +} + +pub fn contextDeclarations(gpa: std.mem.Allocator, path: []const u8, content: []const u8) ![]ContextDeclaration { + const analysis = try analyzeSource(gpa, path, content, true, false); + return analysis.declarations; +} + +fn declarationsFromTree(gpa: std.mem.Allocator, content: []const u8, tree: *ts.Tree) ![]ContextDeclaration { var result: std.ArrayList(ContextDeclaration) = .empty; errdefer result.deinit(gpa); - // Iterative preorder keeps declaration order and avoids recursive traversal - // on deeply nested, partly edited source. - var node = tree.rootNode(); + // The cursor retains its ancestor stack: sibling visits do not repeatedly + // reconstruct parents in broad syntax trees. Preorder preserves source order. + var cursor = tree.rootNode().walk(); + defer cursor.destroy(); while (true) { - if (contextSpan(node, content)) |span| { + const node = cursor.node(); + if (node.isNamed()) if (contextSpan(node, content)) |span| { if (result.items.len == 0 or result.items[result.items.len - 1].start_line != span.start_line or result.items[result.items.len - 1].end_line != span.end_line) try result.append(gpa, span); + }; + if (cursor.gotoFirstChild()) continue; + while (!cursor.gotoNextSibling()) { + if (!cursor.gotoParent()) return result.toOwnedSlice(gpa); } - if (node.namedChild(0)) |child| { - node = child; - continue; - } - while (node.nextNamedSibling() == null) node = node.parent() orelse return result.toOwnedSlice(gpa); - node = node.nextNamedSibling().?; } } @@ -492,6 +522,10 @@ fn contextSpan(node: ts.Node, source: []const u8) ?ContextDeclaration { fn paint(styles: []u8, source: []const u8, selected: Selected) void { const tree = selected.parser.parseString(source, null) orelse return; defer tree.destroy(); + paintTree(styles, source, selected, tree); +} + +fn paintTree(styles: []u8, source: []const u8, selected: Selected, tree: *ts.Tree) void { runQuery(styles, selected, tree, 0); if (std.mem.eql(u8, selected.name, "markdown")) { inject(styles, source, tree.rootNode(), true); @@ -1279,3 +1313,64 @@ test "syntax stacked addresses do not split multiline source groups" { for (styles[at..][0..label.len]) |style| try std.testing.expectEqual(@intFromEnum(Syn.none), style); } } + +test "syntax source analysis preserves declarations and injected colors" { + if (!enabled) return; + const gpa = std.testing.allocator; + start(gpa); + defer stop(); + const Fixture = struct { path: []const u8, source: []const u8 }; + for ([_]Fixture{ + .{ .path = "a.zig", .source = "const Outer = struct {\n // comment\n const Inner = struct {\n pub fn run(\n x: u32,\n ) u32 { return x; }\n };\n};\n" }, + .{ .path = "a.cpp", .source = "namespace Outer {\nstruct Inner {\nint run(\n int x\n) { return x; }\n};\n}\n" }, + .{ .path = "a.rs", .source = "mod outer {\nstruct Inner {}\nimpl Inner {\nfn run(\n &self\n) {}\n}\n}\n" }, + .{ .path = "a.js", .source = "function outer() {\nclass Inner {\nrun(\n x\n) { return x; }\n}\n}\n" }, + .{ .path = "a.py", .source = "class Outer:\n class Inner:\n def run(\n self, x\n ):\n return x\n" }, + .{ .path = "a.md", .source = "# Heading\n\n```zig\npub fn run() void {}\n```\n" }, + .{ .path = "a.typst", .source = "= Heading\n\n```zig\npub fn run() void {}\n```\n" }, + }) |fixture| { + if (!supportsPath(fixture.path)) continue; + var analysis = try analyzeSource(gpa, fixture.path, fixture.source, true, true); + defer analysis.deinit(gpa); + const colors = try highlightFileRange(gpa, fixture.path, fixture.source, 0, fixture.source.len); + defer gpa.free(colors); + try std.testing.expectEqualSlices(u8, colors, analysis.colors); + + // Compare the previous named-node walk to the cursor walk, including + // source ordering, wrapper deduplication and inclusive declaration ends. + const selected = (try forExt(std.fs.path.extension(fixture.path))).?; + const tree = selected.parser.parseString(fixture.source, null).?; + defer tree.destroy(); + var reference: std.ArrayList(ContextDeclaration) = .empty; + defer reference.deinit(gpa); + var node = tree.rootNode(); + walk: while (true) { + if (contextSpan(node, fixture.source)) |span| { + if (reference.items.len == 0 or reference.items[reference.items.len - 1].start_line != span.start_line or + reference.items[reference.items.len - 1].end_line != span.end_line) + try reference.append(gpa, span); + } + if (node.namedChild(0)) |child| { + node = child; + continue; + } + while (node.nextNamedSibling() == null) node = node.parent() orelse break :walk; + node = node.nextNamedSibling().?; + } + try std.testing.expectEqual(reference.items.len, analysis.declarations.len); + for (reference.items, analysis.declarations) |old, new| try std.testing.expect(std.meta.eql(old, new)); + + var declarations_only = try analyzeSource(gpa, fixture.path, fixture.source, true, false); + defer declarations_only.deinit(gpa); + try std.testing.expectEqual(@as(usize, 0), declarations_only.colors.len); + try std.testing.expectEqual(analysis.declarations.len, declarations_only.declarations.len); + var colors_only = try analyzeSource(gpa, fixture.path, fixture.source, false, true); + defer colors_only.deinit(gpa); + try std.testing.expectEqual(@as(usize, 0), colors_only.declarations.len); + try std.testing.expectEqualSlices(u8, analysis.colors, colors_only.colors); + } + var unsupported = try analyzeSource(gpa, "a.unknown", "text", true, true); + unsupported.deinit(gpa); + try std.testing.expectEqual(@as(usize, 0), unsupported.declarations.len); + try std.testing.expectEqual(@as(usize, 0), unsupported.colors.len); +} -- cgit v1.3