//! 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; /// Agave's workspace index is 104 MiB; leave room for it and its lookup tables. /// A bigger index is refused, in words. pub const max_bytes = 512 << 20; const tables_bytes = 512 << 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.Io.Dir.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 // Keep the large bounded regions out of the executable's static address range. var regions: [kept]?[]u8 = @splat(null); var slots: [kept]Index = @splat(.{}); var clock: u64 = 0; pub const Error = error{ TooBig, Malformed, Unreadable, OutOfMemory }; /// 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.Io.Dir.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] orelse blk: { const memory = try std.heap.page_allocator.alloc(u8, max_bytes + tables_bytes); regions[pick] = memory; break :blk memory; }; 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)); }