summaryrefslogtreecommitdiff
path: root/src/lsp/Scip.zig
diff options
context:
space:
mode:
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));
+}