1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
|
//! 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));
}
|