From 1ecb9b720840ea8e4753823fa8cddcf5d6a3a4d2 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Thu, 8 Oct 2026 12:03:46 -0300 Subject: Add a readable static Callstack pane and align tagline text --- src/lsp/lsp.zig | 10 +- src/lsp/lsp_client.zig | 263 ++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 259 insertions(+), 14 deletions(-) (limited to 'src/lsp') diff --git a/src/lsp/lsp.zig b/src/lsp/lsp.zig index 8dc4da4f..96d42bbd 100644 --- a/src/lsp/lsp.zig +++ b/src/lsp/lsp.zig @@ -16,6 +16,7 @@ pub const Kind = enum { format, select_refs, completion, + callstack, incoming_calls, outgoing_calls, supertypes, @@ -24,7 +25,14 @@ pub const Kind = enum { explain, }; +pub const callstack_match = "@callstack-match "; +pub const CallstackCorners = enum { rounded, square }; +pub const callstack_default_depth: u8 = 8; +pub const callstack_max_depth: u8 = 64; + pub const Req = struct { + callstack_depth: u8 = callstack_default_depth, + callstack_corners: CallstackCorners = .rounded, kind: Kind, path: []const u8, source: [:0]const u8, @@ -46,7 +54,7 @@ pub const Doc = struct { path: []const u8, source: [:0]const u8 }; /// file of the server's language is synced before it is asked. pub fn reachesOtherFiles(kind: Kind) bool { return switch (kind) { - .rename, .references, .implementation, .workspace_symbols, .incoming_calls, .outgoing_calls, .supertypes, .subtypes => true, + .rename, .references, .implementation, .workspace_symbols, .callstack, .incoming_calls, .outgoing_calls, .supertypes, .subtypes => true, else => false, }; } diff --git a/src/lsp/lsp_client.zig b/src/lsp/lsp_client.zig index 561195fe..54bbaa79 100644 --- a/src/lsp/lsp_client.zig +++ b/src/lsp/lsp_client.zig @@ -521,7 +521,8 @@ fn run(c: *Conn, si: usize, arena: std.mem.Allocator, req: lsp.Req, out: *std.Io }; const pos = posOf(req.source, req.offset, c.caps.enc); - var cx: Cx = .{ .arena = arena, .base = req.root, .cur_path = req.path, .cur_src = req.source, .out = out }; + var cx: Cx = .{ .arena = arena, .base = req.root, .cur_path = req.path, .cur_src = req.source, .out = out, .relative_parents = req.kind == .callstack, .callstack_corners = req.callstack_corners }; + for (req.others) |doc| try cx.files.append(arena, .{ .path = doc.path, .text = doc.source }); tr.note("server {s} (pid {d}), root {s}, {s} columns", .{ @tagName(c.state), c.pid, c.root, @tagName(c.caps.enc), }); @@ -642,6 +643,7 @@ fn run(c: *Conn, si: usize, arena: std.mem.Allocator, req: lsp.Req, out: *std.Io n += 1; } }, + .callstack => try callstack(c, si, arena, &cx, uri.items, pos, deadline, tr, req.callstack_depth), .incoming_calls => try hierarchy(c, si, arena, &cx, uri.items, pos, deadline, .incoming, tr), .outgoing_calls => try hierarchy(c, si, arena, &cx, uri.items, pos, deadline, .outgoing, tr), .supertypes => try hierarchy(c, si, arena, &cx, uri.items, pos, deadline, .supers, tr), @@ -869,6 +871,184 @@ fn sortEdits(edits: []PutEdit) void { }.lt); } +/// A bounded static hierarchy. Reuse the prepared item verbatim (including +/// server data), and retain every call-site range rather than just a declaration. +fn hierarchyResult(c: *Conn, arena: std.mem.Allocator, item: std.json.Value, method: []const u8, deadline: i64) Err!?std.json.Value { + if (jsonDepth(item, 0) > 96) return null; + var body: std.ArrayList(u8) = .empty; + try app(&body, arena, "\"item\":"); + try app(&body, arena, std.json.Stringify.valueAlloc(arena, item, .{}) catch return error.OutOfMemory); + return call(c, arena, method, body.items, deadline); +} + +const CallTree = struct { + const Site = struct { range: std.json.Value, focus: bool }; + const Node = struct { + item: std.json.Value, + ranges: std.ArrayList(Site) = .empty, + children: std.ArrayList(usize) = .empty, + cycle: bool = false, + }; + nodes: std.ArrayList(Node) = .empty, + roots: std.ArrayList(usize) = .empty, + path: [lsp.callstack_max_depth]std.json.Value = undefined, + depth_limit: usize = lsp.callstack_default_depth, + visited: usize = 0, + limited: bool = false, + siblings: [lsp.callstack_max_depth]bool = @splat(false), + rendered: usize = 0, + + /// Incoming paths arrive nearest-first. Insert them outermost-first, + /// sharing common caller prefixes and retaining all their call sites. + fn addPath(tree: *CallTree, arena: std.mem.Allocator, path: []const std.json.Value, cycle: bool) Err!void { + var parent: ?usize = null; + var at = path.len; + while (at > 0) { + at -= 1; + const entry = path[at]; + const item = get(entry, "from").?; + const children = if (parent) |id| tree.nodes.items[id].children.items else tree.roots.items; + const found = for (children) |id| { + if (sameCall(tree.nodes.items[id].item, item)) break id; + } else null; + const id = found orelse blk: { + const id = tree.nodes.items.len; + try tree.nodes.append(arena, .{ .item = item }); + if (parent) |pid| { + try tree.nodes.items[pid].children.append(arena, id); + } else try tree.roots.append(arena, id); + break :blk id; + }; + const node = &tree.nodes.items[id]; + node.cycle = node.cycle or (cycle and at == 0); + for (items(get(entry, "fromRanges"))) |range| { + const parsed = rangeOf(range) orelse continue; + for (node.ranges.items) |*other| { + if (std.meta.eql(parsed, rangeOf(other.range).?)) { + other.focus = other.focus or at == 0; + break; + } + } else try node.ranges.append(arena, .{ .range = range, .focus = at == 0 }); + } + parent = id; + } + } +}; + +fn sameCall(a: std.json.Value, b: std.json.Value) bool { + const au = str(get(a, "uri")) orelse return false; + const bu = str(get(b, "uri")) orelse return false; + const ar = rangeOf(get(a, "selectionRange") orelse get(a, "range")) orelse return false; + const br = rangeOf(get(b, "selectionRange") orelse get(b, "range")) orelse return false; + return std.mem.eql(u8, au, bu) and std.meta.eql(ar, br); +} + +fn callPrefix(out: *std.Io.Writer, tree: *const CallTree, depth: usize) Err!void { + for (tree.siblings[0..depth]) |more| try out.writeAll(if (more) "│ " else " "); +} + +fn validCaller(entry: std.json.Value) bool { + const from = get(entry, "from") orelse return false; + const uri = str(get(from, "uri")) orelse return false; + return std.mem.startsWith(u8, uri, "file:") and + rangeOf(get(from, "selectionRange") orelse get(from, "range")) != null; +} + +fn callstack(c: *Conn, si: usize, arena: std.mem.Allocator, cx: *Cx, uri: []const u8, pos: Pos, deadline: i64, tr: *Trace, max_depth: u8) Err!void { + if (!c.caps.call_hier) return lsp.none(cx.out, "{s} does not answer call hierarchy (no callHierarchyProvider)", .{specs[si].name}); + const b = try atPos(arena, uri, pos); + const prepared = (try call(c, arena, "textDocument/prepareCallHierarchy", b.items, deadline)) orelse return; + if (items(prepared).len == 0) return lsp.none(cx.out, "no function at this position", .{}); + for (items(prepared)) |item| { + var tree: CallTree = .{ .depth_limit = std.math.clamp(max_depth, 1, lsp.callstack_max_depth) }; + const incoming = try hierarchyResult(c, arena, item, "callHierarchy/incomingCalls", deadline); + const count = try collectCallers(c, arena, item, incoming, deadline, &tree, 0); + if (count == 0) try cx.out.writeAll("No callers reported\n"); + try renderCallers(cx, c.caps.enc, &tree, tree.roots.items, 0); + if (tree.limited) try cx.out.writeAll("… continue from a function above with Callstack\n"); + tr.note("callstack: {d} callers", .{tree.rendered}); + } +} + +fn collectCallers(c: *Conn, arena: std.mem.Allocator, focus: std.json.Value, incoming: ?std.json.Value, deadline: i64, tree: *CallTree, depth: usize) Err!usize { + var count: usize = 0; + for (items(incoming)) |entry| { + if (tree.visited >= 64) { + tree.limited = true; + break; + } + if (!validCaller(entry)) continue; + const from = get(entry, "from").?; + const cycle = sameCall(focus, from) or for (tree.path[0..depth]) |ancestor| { + if (sameCall(get(ancestor, "from").?, from)) break true; + } else false; + tree.path[depth] = entry; + tree.visited += 1; + count += 1; + var children: usize = 0; + if (!cycle) { + if (depth + 1 == tree.depth_limit or tree.visited >= 64) { + tree.limited = true; + } else { + const ancestors = try hierarchyResult(c, arena, from, "callHierarchy/incomingCalls", deadline); + children = try collectCallers(c, arena, focus, ancestors, deadline, tree, depth + 1); + } + } + if (children == 0) try tree.addPath(arena, tree.path[0 .. depth + 1], cycle); + } + return count; +} + +fn callerLess(tree: *const CallTree, a: usize, b: usize) bool { + const left = tree.nodes.items[a].item; + const right = tree.nodes.items[b].item; + const uri_order = std.mem.order(u8, str(get(left, "uri")).?, str(get(right, "uri")).?); + if (uri_order != .eq) return uri_order == .lt; + return callRangeLess({}, get(left, "selectionRange") orelse get(left, "range").?, get(right, "selectionRange") orelse get(right, "range").?); +} + +fn callRangeLess(_: void, a: std.json.Value, b: std.json.Value) bool { + const left = rangeOf(a).?; + const right = rangeOf(b).?; + return left.sl < right.sl or (left.sl == right.sl and left.sc < right.sc); +} + +fn renderCallers(cx: *Cx, enc: Enc, tree: *CallTree, children: []usize, depth: usize) Err!void { + std.mem.sort(usize, children, @as(*const CallTree, tree), callerLess); + for (children, 0..) |id, index| { + if (tree.rendered >= 64) { + tree.limited = true; + return; + } + const node = &tree.nodes.items[id]; + const item = node.item; + const uri = str(get(item, "uri")).?; + const more = index + 1 < children.len; + try callPrefix(cx.out, tree, depth); + const has_children = node.children.items.len > 0 or node.ranges.items.len > 0; + const rounded = cx.callstack_corners == .rounded; + try cx.out.writeAll(if (more) "├" else if (rounded) "╰" else "└"); + try cx.out.writeAll(if (has_children) "──┬ " else "─── "); + const name = flat(cx.arena, str(get(item, "name")) orelse "(unnamed)"); + const label = if (node.cycle) try std.fmt.allocPrint(cx.arena, "{s} ↻ recursion", .{name}) else name; + try emitRange(cx, enc, uri, get(item, "selectionRange") orelse get(item, "range"), label); + tree.rendered += 1; + tree.siblings[depth] = more; + std.mem.sort(CallTree.Site, node.ranges.items, {}, struct { + fn less(_: void, a: CallTree.Site, b: CallTree.Site) bool { + return callRangeLess({}, a.range, b.range); + } + }.less); + for (node.ranges.items, 0..) |site, site_index| { + if (site.focus) try cx.out.writeAll(lsp.callstack_match); + try callPrefix(cx.out, tree, depth + 1); + try cx.out.writeAll(if (node.children.items.len > 0 or site_index + 1 < node.ranges.items.len) "├─ " else if (rounded) "╰─ " else "└─ "); + try emitRange(cx, enc, uri, site.range, ""); + } + try renderCallers(cx, enc, tree, node.children.items, depth + 1); + } +} + const Hier = enum { incoming, outgoing, supers, subs }; /// The two-step hierarchy kinds: prepare at the cursor, then follow every @@ -894,17 +1074,7 @@ fn hierarchy(c: *Conn, si: usize, arena: std.mem.Allocator, cx: *Cx, uri: []cons const b = try atPos(arena, uri, pos); const prepared = (try call(c, arena, prepare, b.items, deadline)) orelse return; for (items(prepared)) |item| { - // the item goes back VERBATIM — servers hide resolution state in - // `data` and a re-serialized subset would come back unresolvable. - // But only if it can round-trip: Stringify panics past its nesting - // limit, so a server that nests a bomb in `data` gets no rows for - // that item, not a dead editor. - if (jsonDepth(item, 0) > 96) continue; - var body: std.ArrayList(u8) = .empty; - try app(&body, arena, "\"item\":"); - const item_json = std.json.Stringify.valueAlloc(arena, item, .{}) catch return error.OutOfMemory; - try app(&body, arena, item_json); - const result = (try call(c, arena, follow, body.items, deadline)) orelse return; + const result = (try hierarchyResult(c, arena, item, follow, deadline)) orelse return; for (items(result)) |entry| switch (h) { .incoming => { // one row per CALL SITE, under the caller's name — that is @@ -965,6 +1135,8 @@ const Cx = struct { cur_src: []const u8, out: *std.Io.Writer, rows: usize = 0, + relative_parents: bool = false, + callstack_corners: lsp.CallstackCorners = .rounded, files: std.ArrayList(struct { path: []const u8, text: []const u8 }) = .empty, fn text(cx: *Cx, path: []const u8) ?[]const u8 { @@ -1018,7 +1190,10 @@ fn emitRange(cx: *Cx, enc: Enc, uri: []const u8, range: ?std.json.Value, note: [ const lntext: []const u8 = if (src) |t| t[@min(bol, t.len)..@min(eol, t.len)] else ""; const col = colBytes(lntext, r.sc, enc); - const shown = lsp.rel(cx.base, path); + const shown = if (cx.relative_parents) blk: { + const relative = std.fs.path.relativePosix(cx.arena, "/", cx.base, path) catch break :blk path; + break :blk if (relative.len < path.len) relative else path; + } else lsp.rel(cx.base, path); // A same-line exclusive end byte offset is also the displayed inclusive // one-based column. Multi-line ranges display only their starting address. const end_col = if (r.el == r.sl and r.ec > r.sc) colBytes(lntext, r.ec, enc) else col; @@ -2131,6 +2306,68 @@ fn coord(v: ?std.json.Value) ?u32 { // ----------------------------------------------------------------- tests +test "caller trees reverse incoming paths and merge shared callers and sites" { + var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator); + defer arena_state.deinit(); + const arena = arena_state.allocator(); + const fixture = try std.json.parseFromSliceLeaky(std.json.Value, arena, "[{\"from\":{\"name\":\"left\",\"uri\":\"file:///test.c\",\"selectionRange\":{\"start\":{\"line\":3,\"character\":0},\"end\":{\"line\":3,\"character\":4}}},\"fromRanges\":[{\"start\":{\"line\":3,\"character\":0},\"end\":{\"line\":3,\"character\":4}}]},{\"from\":{\"name\":\"right\",\"uri\":\"file:///test.c\",\"selectionRange\":{\"start\":{\"line\":4,\"character\":0},\"end\":{\"line\":4,\"character\":4}}},\"fromRanges\":[{\"start\":{\"line\":4,\"character\":0},\"end\":{\"line\":4,\"character\":4}}]},{\"from\":{\"name\":\"page\",\"uri\":\"file:///test.c\",\"selectionRange\":{\"start\":{\"line\":1,\"character\":0},\"end\":{\"line\":1,\"character\":4}}},\"fromRanges\":[{\"start\":{\"line\":1,\"character\":0},\"end\":{\"line\":1,\"character\":4}}]},{\"from\":{\"name\":\"page\",\"uri\":\"file:///test.c\",\"selectionRange\":{\"start\":{\"line\":1,\"character\":0},\"end\":{\"line\":1,\"character\":4}}},\"fromRanges\":[{\"start\":{\"line\":2,\"character\":0},\"end\":{\"line\":2,\"character\":4}}]},{\"from\":{\"name\":\"main\",\"uri\":\"file:///test.c\",\"selectionRange\":{\"start\":{\"line\":0,\"character\":0},\"end\":{\"line\":0,\"character\":4}}},\"fromRanges\":[{\"start\":{\"line\":0,\"character\":0},\"end\":{\"line\":0,\"character\":4}}]}]", .{}); + const entries = items(fixture); + var tree: CallTree = .{}; + try tree.addPath(arena, &.{ entries[0], entries[2], entries[4] }, false); + try tree.addPath(arena, &.{ entries[1], entries[3], entries[4] }, false); + try std.testing.expectEqual(@as(usize, 1), tree.roots.items.len); + try std.testing.expectEqual(@as(usize, 4), tree.nodes.items.len); + const root = tree.nodes.items[tree.roots.items[0]]; + try std.testing.expectEqualStrings("main", str(get(root.item, "name")).?); + try std.testing.expectEqual(@as(usize, 1), root.ranges.items.len); + const page = tree.nodes.items[root.children.items[0]]; + try std.testing.expectEqual(@as(usize, 2), page.children.items.len); + try std.testing.expectEqual(@as(usize, 2), page.ranges.items.len); + try std.testing.expect(!root.ranges.items[0].focus); + for (page.ranges.items) |site| try std.testing.expect(!site.focus); + for (page.children.items) |id| try std.testing.expect(tree.nodes.items[id].ranges.items[0].focus); + var out: std.Io.Writer.Allocating = .init(arena); + var cx: Cx = .{ .arena = arena, .base = "/", .cur_path = "/test.c", .cur_src = "main_call();\npage_left();\npage_right();\nleft_call();\nright_call();\n", .out = &out.writer }; + try renderCallers(&cx, .utf8, &tree, tree.roots.items, 0); + const text = out.written(); + try std.testing.expectEqual(@as(usize, 2), std.mem.count(u8, text, lsp.callstack_match)); + const main_at = std.mem.indexOf(u8, text, " main\n").?; + const page_at = std.mem.indexOf(u8, text, " page\n").?; + const left_at = std.mem.indexOf(u8, text, " left\n").?; + const right_at = std.mem.indexOf(u8, text, " right\n").?; + try std.testing.expect(main_at < page_at and page_at < left_at and left_at < right_at); + try std.testing.expectEqual(@as(usize, 1), std.mem.count(u8, text, "main_call();")); + try std.testing.expect(std.mem.indexOf(u8, text, "page_left();").? < std.mem.indexOf(u8, text, "page_right();").?); + try std.testing.expect(std.mem.indexOf(u8, text, "├──┬ test.c:4:") != null); + try std.testing.expect(std.mem.indexOf(u8, text, "╰──┬ test.c:1:") != null); + cx.callstack_corners = .square; + tree.rendered = 0; + const square_start = out.written().len; + try renderCallers(&cx, .utf8, &tree, tree.roots.items, 0); + const square = out.written()[square_start..]; + try std.testing.expect(std.mem.indexOf(u8, square, "├──┬ test.c:4:") != null); + try std.testing.expect(std.mem.indexOf(u8, square, "└──┬ test.c:1:") != null); + try std.testing.expect(std.mem.indexOf(u8, square, "╰") == null); + try std.testing.expect(std.mem.indexOf(u8, square, "╮") == null); + var recursive: CallTree = .{}; + try recursive.addPath(arena, &.{ entries[0], entries[0] }, true); + try std.testing.expect(!recursive.nodes.items[recursive.roots.items[0]].cycle); + try std.testing.expect(recursive.nodes.items[1].cycle); +} + +test "callstack cross-crate paths remain resolvable without absolute path clutter" { + var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator); + defer arena_state.deinit(); + const arena = arena_state.allocator(); + const range = try std.json.parseFromSliceLeaky(std.json.Value, arena, + \\{"start":{"line":1,"character":3},"end":{"line":1,"character":6}} + , .{}); + var out: std.Io.Writer.Allocating = .init(arena); + var cx: Cx = .{ .arena = arena, .base = "/workspace/merkle-tree/src", .cur_path = "", .cur_src = "", .out = &out.writer, .relative_parents = true }; + try emitRange(&cx, .utf8, "file:///workspace/entry/src/entry.rs", range, "fn run()"); + try std.testing.expectEqualStrings("../../entry/src/entry.rs:2:4-6 fn run()\n", out.written()); +} + test "LSP client rename and format propagate incomplete edit encoding" { const gpa = std.testing.allocator; const uri = "file:///file.c"; -- cgit v1.3