summaryrefslogtreecommitdiff
path: root/src/lsp/Scip.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-05 11:24:31 -0300
committerGabriel Schneider <[email protected]>2026-11-05 12:02:59 -0300
commit60a891ce8127c87b55aed1ff71e435cb7fbd28fc (patch)
treea69bdf00d8d5630e40c1f74b14d97d3b59f6d784 /src/lsp/Scip.zig
parent2143d01eeeadd33c49ceaf22721729a5d03b2810 (diff)
downloadpardes-60a891ce8127c87b55aed1ff71e435cb7fbd28fc.tar.gz
pardes-60a891ce8127c87b55aed1ff71e435cb7fbd28fc.zip
lsp: SCIP first, the server second: the language words ask the nearest index.scip above the file (src/lsp/Scip.zig: a protobuf reader of the fields the words read, each document's occurrences with their ranges, roles and enclosing nodes, the symbols interned, a document's locals its own, with their occurrences listed by symbol, each symbol's information read again when a word wants it; loaded on the first question on the query's worker and again once the file changes, into a fixed region of two indexes, 32 MiB of index and 32 MiB of tables each, eight times rust-analyzer's index of clap_builder 4.6.7, 3.9 MB with 3.1 MB of tables); Def, type definition, Refs, SelectRefs, gi and Subtypes, Supertypes, Symbols, WsSymbols, Hover, Callers, Callees and Callstack answer from it in the server's rows (the Callstack walk takes its hops from the index or the server, each caller the function whose definition holds the call), and the server answers what it lacks (no index, a file, place or symbol it does not hold, a pane's unsaved changes) and Diagnostics, Rename, CodeAction, format, completion and declaration; an index older than its file answers and says so once; Lspinfo starts with the index (path, size, documents, symbols, when, files newer) and its log names scip; Lspwhy narrates the branch taken; the Index word runs the file's indexer (rust-analyzer scip . and the like, PARDES_SCIP_* naming another) at the project's root in a command pane; T1 cases over a hand-made index and rust-analyzer's own (test/scipfixture); the reference, setup, guide, lsp-evaluation.md, the changelog and both builtins lists say so
Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_016Y9MNAtZenFv4weoMD3cge
Diffstat (limited to 'src/lsp/Scip.zig')
-rw-r--r--src/lsp/Scip.zig354
1 files changed, 354 insertions, 0 deletions
diff --git a/src/lsp/Scip.zig b/src/lsp/Scip.zig
new file mode 100644
index 00000000..8deffe26
--- /dev/null
+++ b/src/lsp/Scip.zig
@@ -0,0 +1,354 @@
+//! A repository's code intelligence, read from its `index.scip` (SCIP,
+//! scip-code.org; the schema is scip.proto in sourcegraph/scip): the
+//! language words ask it first and the language server when it has
+//! nothing to say (lsp_client.zig). An indexer writes it at the project's
+//! root (the Index word runs one); the nearest above a file's directory
+//! answers for the file. It is read on the first question that wants it,
+//! on the query's worker, off the typing path, and again once it changes.
+//!
+//! Kept: each document's path, position encoding and occurrences (range,
+//! symbol, roles, the enclosing node's range), the symbols interned with
+//! their occurrences listed by symbol, and the bytes of each symbol's
+//! information, read again when a word wants its documentation, signature,
+//! kind or relationships. Skipped: the metadata (paths resolve against
+//! the index's own directory), external symbols, syntax kinds, an
+//! occurrence's diagnostics and a document's text.
+const std = @import("std");
+const statPath = @import("../fs.zig").statPath;
+
+/// One loaded index's caps, measured on a real one: rust-analyzer 1.97's
+/// index of clap_builder 4.6.7 (29 kloc) is 3.9 MB, with 55 documents,
+/// 32,795 occurrences and 6,661 symbols, and its tables take 3.1 MB; these
+/// hold eight times that. A bigger index is refused, in words.
+pub const max_bytes = 32 << 20;
+const tables_bytes = 32 << 20;
+/// Indexes kept loaded at once, the one asked least recently replaced.
+const kept = 2;
+
+pub const Range = struct { sl: u32 = 0, sc: u32 = 0, el: u32 = 0, ec: u32 = 0 };
+/// What a document's characters count (its `position_encoding`).
+pub const Enc = enum { utf8, utf16, utf32 };
+/// An occurrence's role bit (scip.proto SymbolRole) for a definition.
+pub const role_definition = 1;
+
+pub const Occurrence = struct {
+ range: Range,
+ /// The node a definition names, a function's signature and body, when
+ /// the indexer gave it; empty otherwise.
+ enclosing: Range,
+ symbol: u32,
+ doc: u32,
+ roles: u32,
+};
+
+pub const Document = struct { path: []const u8, enc: Enc, first: u32, len: u32 };
+
+pub const Index = struct {
+ path_buf: [4096]u8 = undefined,
+ path_len: usize = 0,
+ mtime: i96 = 0,
+ size: u64 = 0,
+ used: u64 = 0,
+ /// A document newer than the index has been said once.
+ stale_said: bool = false,
+ documents: []Document = &.{},
+ occurrences: []Occurrence = &.{},
+ /// By symbol id: its string, its information's bytes (empty for one
+ /// defined in no document here), and its occurrences,
+ /// `order[starts[id]..starts[id + 1]]`.
+ symbols: std.ArrayList([]const u8) = .empty,
+ infos: std.ArrayList([]const u8) = .empty,
+ starts: []u32 = &.{},
+ order: []u32 = &.{},
+ ids: std.StringHashMapUnmanaged(u32) = .empty,
+
+ pub fn path(ix: *const Index) []const u8 {
+ return ix.path_buf[0..ix.path_len];
+ }
+
+ pub fn root(ix: *const Index) []const u8 {
+ return std.fs.path.dirname(ix.path()) orelse "/";
+ }
+
+ /// The document of the file at `abs`, or null.
+ pub fn document(ix: *const Index, abs: []const u8) ?u32 {
+ const r = ix.root();
+ if (abs.len <= r.len + 1 or !std.mem.startsWith(u8, abs, r) or abs[r.len] != '/') return null;
+ for (ix.documents, 0..) |d, i| if (std.mem.eql(u8, d.path, abs[r.len + 1 ..])) return @intCast(i);
+ return null;
+ }
+
+ /// The innermost occurrence of `doc` at (line, ch), counted in the
+ /// document's units; one ending at the cursor counts.
+ pub fn at(ix: *const Index, doc: u32, line: u32, ch: u32) ?u32 {
+ const d = ix.documents[doc];
+ var best: ?u32 = null;
+ for (d.first..d.first + d.len) |i| {
+ const r = ix.occurrences[i].range;
+ if (!holds(r, .{ .sl = line, .sc = ch, .el = line, .ec = ch })) continue;
+ if (best == null or holds(ix.occurrences[best.?].range, r)) best = @intCast(i);
+ }
+ return best;
+ }
+
+ /// Whether the file at `abs` changed after the index was written.
+ pub fn stale(ix: *const Index, io: std.Io, abs: []const u8) bool {
+ const st = statPath(io, abs, .{}) catch return false;
+ return st.mtime.nanoseconds > ix.mtime;
+ }
+
+ pub fn of(ix: *const Index, symbol: u32) []const u32 {
+ return ix.order[ix.starts[symbol]..ix.starts[symbol + 1]];
+ }
+
+ /// The definition whose node holds occurrence `o`, the innermost, of a
+ /// function-like symbol: where the call `o` is made from.
+ pub fn enclosingDefinition(ix: *const Index, o: u32) ?u32 {
+ const d = ix.documents[ix.occurrences[o].doc];
+ var best: ?u32 = null;
+ for (d.first..d.first + d.len) |i| {
+ const def = ix.occurrences[i];
+ if (i == o or def.roles & role_definition == 0 or !holds(def.enclosing, ix.occurrences[o].range)) continue;
+ if (!callable(ix.infos.items[def.symbol])) continue;
+ if (best == null or holds(ix.occurrences[best.?].enclosing, def.enclosing)) best = @intCast(i);
+ }
+ return best;
+ }
+};
+
+/// Whether `outer` holds `inner`, its ends included.
+pub fn holds(outer: Range, inner: Range) bool {
+ const starts_before = outer.sl < inner.sl or (outer.sl == inner.sl and outer.sc <= inner.sc);
+ const ends_after = outer.el > inner.el or (outer.el == inner.el and outer.ec >= inner.ec);
+ return starts_before and ends_after and (outer.sl != outer.el or outer.sc != outer.ec);
+}
+
+/// A symbol information's kind (5) is a function's or a method's.
+pub fn callable(info: []const u8) bool {
+ const kind = (field(info, 5) orelse return false).int;
+ return switch (kind) {
+ 9, 17, 18, 25, 26, 45, 47, 66...72, 74, 76, 80 => true,
+ else => false,
+ };
+}
+
+// ------------------------------------------------------------------ the wire
+
+/// One field of a Protobuf message: its number, and its varint or its
+/// length-delimited bytes (fixed 32- and 64-bit ones are skipped whole).
+pub const Field = struct { num: u64, int: u64 = 0, bytes: []const u8 = "" };
+
+pub const Reader = struct {
+ bytes: []const u8,
+ at: usize = 0,
+
+ pub fn varint(r: *Reader) error{Malformed}!u64 {
+ var n: u64 = 0;
+ var shift: u7 = 0;
+ while (r.at < r.bytes.len and shift < 64) : (shift += 7) {
+ const b = r.bytes[r.at];
+ r.at += 1;
+ n |= @as(u64, b & 0x7f) << @intCast(shift);
+ if (b < 0x80) return n;
+ }
+ return error.Malformed;
+ }
+
+ pub fn next(r: *Reader) error{Malformed}!?Field {
+ if (r.at == r.bytes.len) return null;
+ const key = try r.varint();
+ var f: Field = .{ .num = key >> 3 };
+ switch (key & 7) {
+ 0 => f.int = try r.varint(),
+ 1 => r.at += 8,
+ 5 => r.at += 4,
+ 2 => {
+ const len = try r.varint();
+ if (len > r.bytes.len - r.at) return error.Malformed;
+ f.bytes = r.bytes[r.at..][0..@intCast(len)];
+ r.at += @intCast(len);
+ },
+ else => return error.Malformed,
+ }
+ if (r.at > r.bytes.len) return error.Malformed;
+ return f;
+ }
+};
+
+/// The first field `num` of a message.
+pub fn field(msg: []const u8, num: u64) ?Field {
+ var r: Reader = .{ .bytes = msg };
+ while (r.next() catch return null) |f| if (f.num == num) return f;
+ return null;
+}
+
+/// A range written as packed varints, `[line, start, end]` or `[line,
+/// start, end line, end]`, or as a SingleLineRange or MultiLineRange
+/// message (`typed`), its zeros left out.
+fn rangeOf(bytes: []const u8, typed: enum { packed_ints, single, multi }) error{Malformed}!Range {
+ var v: [4]u32 = @splat(0);
+ var n: usize = 0;
+ var r: Reader = .{ .bytes = bytes };
+ if (typed == .packed_ints) {
+ while (r.at < bytes.len and n < 4) : (n += 1) v[n] = @truncate(try r.varint());
+ if (n == 3) return .{ .sl = v[0], .sc = v[1], .el = v[0], .ec = v[2] };
+ if (n != 4) return error.Malformed;
+ } else while (try r.next()) |f| if (f.num >= 1 and f.num <= 4) {
+ v[f.num - 1] = @truncate(f.int);
+ };
+ if (typed == .single) return .{ .sl = v[0], .sc = v[1], .el = v[0], .ec = v[2] };
+ return .{ .sl = v[0], .sc = v[1], .el = v[2], .ec = v[3] };
+}
+
+// ------------------------------------------------------------------ loading
+
+var regions: [kept][max_bytes + tables_bytes]u8 align(std.heap.page_size_max) = @splat(@splat(0));
+var slots: [kept]Index = @splat(.{});
+var clock: u64 = 0;
+
+pub const Error = error{ TooBig, Malformed, Unreadable };
+
+/// The index for a file in `dir`: the nearest `index.scip` there or up to
+/// seven directories above, read again when it changed since; null with
+/// none.
+pub fn find(io: std.Io, dir: []const u8) Error!?*Index {
+ var buf: [4096]u8 = undefined;
+ var d = dir;
+ for (0..8) |_| {
+ const p = std.fmt.bufPrint(&buf, "{s}/index.scip", .{if (std.mem.eql(u8, d, "/")) "" else d}) catch return null;
+ if (statPath(io, p, .{})) |st| return try use(io, p, st) else |_| {}
+ d = std.fs.path.dirname(d) orelse return null;
+ }
+ return null;
+}
+
+fn use(io: std.Io, p: []const u8, st: std.Io.File.Stat) Error!*Index {
+ clock += 1;
+ var pick: usize = 0;
+ for (&slots, 0..) |*ix, i| {
+ if (std.mem.eql(u8, ix.path(), p) and ix.mtime == st.mtime.nanoseconds and ix.size == st.size) {
+ ix.used = clock;
+ return ix;
+ }
+ if (ix.used < slots[pick].used) pick = i;
+ }
+ if (st.size > max_bytes) return error.TooBig;
+ const ix = &slots[pick];
+ ix.* = .{ .mtime = st.mtime.nanoseconds, .size = st.size, .used = clock, .path_len = p.len };
+ @memcpy(ix.path_buf[0..p.len], p);
+ errdefer ix.* = .{};
+ const region = &regions[pick];
+ const file = std.Io.Dir.cwd().openFile(io, p, .{}) catch return error.Unreadable;
+ defer file.close(io);
+ const got = file.readPositionalAll(io, region[0..@intCast(st.size)], 0) catch return error.Unreadable;
+ var fba: std.heap.FixedBufferAllocator = .init(region[max_bytes..]);
+ parse(ix, region[0..got], fba.allocator()) catch |e| return if (e == error.OutOfMemory) error.TooBig else error.Malformed;
+ return ix;
+}
+
+/// Two walks over the documents: one counts them and their occurrences,
+/// the other fills the tables sized from the counts.
+fn parse(ix: *Index, bytes: []const u8, a: std.mem.Allocator) !void {
+ var docs: usize = 0;
+ var occs: usize = 0;
+ var r: Reader = .{ .bytes = bytes };
+ while (try r.next()) |f| if (f.num == 2) {
+ docs += 1;
+ var d: Reader = .{ .bytes = f.bytes };
+ while (try d.next()) |g| occs += @intFromBool(g.num == 2);
+ };
+ ix.documents = try a.alloc(Document, docs);
+ ix.occurrences = try a.alloc(Occurrence, occs);
+ occs = 0;
+ docs = 0;
+ r = .{ .bytes = bytes };
+ while (try r.next()) |f| if (f.num == 2) {
+ const doc = &ix.documents[docs];
+ doc.* = .{ .path = "", .enc = .utf8, .first = @intCast(occs), .len = 0 };
+ var d: Reader = .{ .bytes = f.bytes };
+ while (try d.next()) |g| switch (g.num) {
+ 1 => doc.path = g.bytes,
+ 2 => {
+ const o = &ix.occurrences[occs];
+ o.* = .{ .range = .{}, .enclosing = .{}, .symbol = 0, .doc = @intCast(docs), .roles = 0 };
+ var name: []const u8 = "";
+ var e: Reader = .{ .bytes = g.bytes };
+ while (try e.next()) |h| switch (h.num) {
+ 1 => o.range = try rangeOf(h.bytes, .packed_ints),
+ 2 => name = h.bytes,
+ 3 => o.roles = @truncate(h.int),
+ 7 => o.enclosing = try rangeOf(h.bytes, .packed_ints),
+ 8, 10 => (if (h.num == 8) &o.range else &o.enclosing).* = try rangeOf(h.bytes, .single),
+ 9, 11 => (if (h.num == 9) &o.range else &o.enclosing).* = try rangeOf(h.bytes, .multi),
+ else => {},
+ };
+ o.symbol = try intern(ix, a, name, docs);
+ occs += 1;
+ },
+ 3 => if (field(g.bytes, 1)) |s| {
+ const id = try intern(ix, a, s.bytes, docs);
+ ix.infos.items[id] = g.bytes;
+ },
+ 6 => doc.enc = switch (g.int) {
+ 2 => .utf16,
+ 3 => .utf32,
+ else => .utf8,
+ },
+ else => {},
+ };
+ doc.len = @intCast(occs - doc.first);
+ docs += 1;
+ };
+ // The occurrences listed by symbol: counted, the counts summed, filled.
+ ix.starts = try a.alloc(u32, ix.symbols.items.len + 1);
+ @memset(ix.starts, 0);
+ for (ix.occurrences) |o| ix.starts[o.symbol + 1] += 1;
+ for (1..ix.starts.len) |i| ix.starts[i] += ix.starts[i - 1];
+ ix.order = try a.alloc(u32, ix.occurrences.len);
+ const filled = try a.alloc(u32, ix.symbols.items.len);
+ @memset(filled, 0);
+ for (ix.occurrences, 0..) |o, i| {
+ ix.order[ix.starts[o.symbol] + filled[o.symbol]] = @intCast(i);
+ filled[o.symbol] += 1;
+ }
+}
+
+/// A symbol's id, a `local N` one's in its document alone (its key is the
+/// document's number and the name), the first time it is met a new one.
+fn intern(ix: *Index, a: std.mem.Allocator, name: []const u8, doc: usize) !u32 {
+ var buf: [64]u8 = undefined;
+ const local = std.mem.startsWith(u8, name, "local ");
+ const key = if (local) std.fmt.bufPrint(&buf, "{d} {s}", .{ doc, name }) catch return error.Malformed else name;
+ const got = try ix.ids.getOrPut(a, key);
+ if (!got.found_existing) {
+ if (local) got.key_ptr.* = try a.dupe(u8, key);
+ got.value_ptr.* = @intCast(ix.symbols.items.len);
+ try ix.symbols.append(a, name);
+ try ix.infos.append(a, "");
+ }
+ return got.value_ptr.*;
+}
+
+test "a varint and every wire type a reader skips" {
+ var r: Reader = .{ .bytes = &.{ 0xac, 0x02 } };
+ try std.testing.expectEqual(@as(u64, 300), try r.varint());
+ // field 1 varint 7, field 2 fixed64, field 3 bytes "hi", field 4 fixed32, field 5 varint 1
+ const msg = [_]u8{ 0x08, 0x07, 0x11 } ++ @as([8]u8, @splat(9)) ++ [_]u8{ 0x1a, 0x02, 'h', 'i', 0x25 } ++ @as([4]u8, @splat(9)) ++ [_]u8{ 0x28, 0x01 };
+ try std.testing.expectEqual(@as(u64, 7), field(&msg, 1).?.int);
+ try std.testing.expectEqualStrings("hi", field(&msg, 3).?.bytes);
+ try std.testing.expectEqual(@as(u64, 1), field(&msg, 5).?.int);
+ try std.testing.expect(field(&msg, 6) == null);
+ // cut short, an unknown wire type, a length past the end
+ for ([_][]const u8{ &.{0x80}, &.{ 0x0b, 0x00 }, &.{ 0x1a, 0x05, 'h' } }) |bad| {
+ var b: Reader = .{ .bytes = bad };
+ try std.testing.expectError(error.Malformed, b.next());
+ }
+}
+
+test "ranges in the packed form and the typed ones, zeros left out" {
+ try std.testing.expectEqual(Range{ .sl = 3, .sc = 4, .el = 3, .ec = 7 }, try rangeOf(&.{ 3, 4, 7 }, .packed_ints));
+ try std.testing.expectEqual(Range{ .sl = 1, .sc = 0, .el = 2, .ec = 5 }, try rangeOf(&.{ 1, 0, 2, 5 }, .packed_ints));
+ try std.testing.expectEqual(Range{ .sl = 0, .sc = 0, .el = 0, .ec = 3 }, try rangeOf(&.{ 0x18, 3 }, .single));
+ try std.testing.expectEqual(Range{ .sl = 2, .sc = 0, .el = 4, .ec = 1 }, try rangeOf(&.{ 0x08, 2, 0x18, 4, 0x20, 1 }, .multi));
+ try std.testing.expectError(error.Malformed, rangeOf(&.{ 1, 2 }, .packed_ints));
+}