diff options
Diffstat (limited to 'src/lsp/Scip.zig')
| -rw-r--r-- | src/lsp/Scip.zig | 354 |
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 = ®ions[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)); +} |
