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
358
359
360
361
362
363
364
365
|
//! Names a query pane picks from by a fuzzy query: the files under a
//! directory (listed by the disk engine, Stream.zig), the recent files, the open panes,
//! a file's declarations. Each keystroke scores them again with a small
//! fzf-style scorer (subsequence, Smith-Waterman with affine gaps, bonuses
//! at the starts of words and path segments), a frame's budget at a time,
//! the best kept first. Lifted from the pick prototype (Pick.zig), whose
//! scorer took ~1 ms for 20k paths in a release build. Embedded in a
//! Query; the rows it shows are the Query's to make.
const Names = @This();
const std = @import("std");
const pardes = @import("pardes.zig");
const panes = @import("panes.zig");
const config = @import("config.zig");
const Pardes = pardes.Pardes;
/// The candidates' rows, back to back, no newlines.
bytes: std.ArrayList(u8) = .empty,
/// `bytes` in lowercase, for a lowercase query to match without folding.
lower: std.ArrayList(u8) = .empty,
cands: std.ArrayList(Cand) = .empty,
/// The candidates `query` matches, best first.
hits: std.ArrayList(Hit) = .empty,
/// `cands[0..scored]` were scored against `query` (in `hits` or not): the
/// ones a walk adds past it are scored as they come.
scored: u32 = 0,
/// Candidates to score before `cands[scored..]`: what the last query
/// matched, when this one only grew from it.
pending: std.ArrayList(u32) = .empty,
pending_at: usize = 0,
query_buf: [max_query]u8 = undefined,
query_len: u8 = 0,
/// Bumped whenever `hits` change: the rows are made again only then.
gen: u32 = 0,
pub const Cand = struct {
/// The row: `bytes[start..][0..len]`.
start: u32,
len: u16,
/// What is scored: the row's `[key..][0..key_len]` (a path, a
/// declaration's text, a name), its basename from `base` within it.
key: u16,
key_len: u16,
base: u16,
/// What the row is of: a line of the owner (Symbols, 1-based), a
/// pane's serial (Panes); 0 for a path.
ref: u32 = 0,
};
pub const Hit = struct { cand: u32, score: i32 };
/// The most rows shown: the rest are counted.
pub const max_rows = 200;
pub const max_query = 64;
/// A candidate is scored over its first this many bytes.
const max_text = 512;
const max_cands = 200_000;
/// A keystroke's scoring, and a frame's: what is left waits a frame.
const score_budget_ns = 4 * std.time.ns_per_ms;
pub fn deinit(n: *Names, gpa: std.mem.Allocator) void {
n.bytes.deinit(gpa);
n.lower.deinit(gpa);
n.cands.deinit(gpa);
n.hits.deinit(gpa);
n.pending.deinit(gpa);
n.* = .{};
}
/// No candidates, no walk: for a source filled again.
pub fn reset(n: *Names) void {
n.bytes.clearRetainingCapacity();
n.lower.clearRetainingCapacity();
n.cands.clearRetainingCapacity();
n.hits.clearRetainingCapacity();
n.pending.clearRetainingCapacity();
n.pending_at = 0;
n.scored = 0;
n.gen +%= 1;
}
pub fn queryText(n: *const Names) []const u8 {
return n.query_buf[0..n.query_len];
}
pub fn add(n: *Names, gpa: std.mem.Allocator, row_in: []const u8, key: usize, key_len: usize, base: u16, ref: u32) !void {
if (n.cands.items.len >= max_cands) return;
const text = row_in[0..@min(row_in.len, std.math.maxInt(u16))];
try n.cands.append(gpa, .{
.start = @intCast(n.bytes.items.len),
.len = @intCast(text.len),
.key = @intCast(@min(key, text.len)),
.key_len = @intCast(@min(key_len, text.len - @min(key, text.len))),
.base = base,
.ref = ref,
});
try n.bytes.appendSlice(gpa, text);
try n.lower.ensureUnusedCapacity(gpa, text.len);
for (text) |c| n.lower.appendAssumeCapacity(std.ascii.toLower(c));
}
pub fn relative(path: []const u8, dir: []const u8) []const u8 {
const d = std.mem.trimEnd(u8, dir, "/");
if (d.len > 0 and path.len > d.len + 1 and std.mem.startsWith(u8, path, d) and path[d.len] == '/') return path[d.len + 1 ..];
return path;
}
pub fn baseOf(path: []const u8) u16 {
const slash = std.mem.lastIndexOfScalar(u8, std.mem.trimEnd(u8, path, "/"), '/') orelse return 0;
return @intCast(@min(slash + 1, max_text));
}
/// Still scoring what it has: it wants the next frame.
pub fn busy(n: *const Names) bool {
return n.scored < n.cands.items.len or n.pending_at < n.pending.items.len;
}
/// A new query: scored again, from what the last one matched when it only
/// grew from it.
pub fn typed(n: *Names, gpa: std.mem.Allocator, text: []const u8) void {
const q = text[0..@min(text.len, max_query)];
if (std.mem.eql(u8, q, n.queryText()) and n.scored > 0) return;
// A query that only grew matches a subset of what the last one did:
// only those are scored again (and then the ones not yet scored).
const grew = n.query_len > 0 and std.mem.startsWith(u8, q, n.queryText()) and std.mem.indexOfScalar(u8, q[n.query_len..], ' ') == null;
n.query_len = @intCast(q.len);
@memcpy(n.query_buf[0..q.len], q);
if (grew) {
const pending = n.pending.items[n.pending_at..];
std.mem.copyForwards(u32, n.pending.items[0..pending.len], pending);
n.pending.items.len = pending.len;
n.pending.ensureUnusedCapacity(gpa, n.hits.items.len) catch return;
for (n.hits.items) |h| n.pending.appendAssumeCapacity(h.cand);
} else {
n.scored = 0;
n.pending.clearRetainingCapacity();
}
n.pending_at = 0;
n.hits.clearRetainingCapacity();
n.rescore(gpa);
}
/// Scores the pending candidates, then `cands[scored..]`, into `hits`, and
/// sorts them: at most `score_budget_ns` of it a call, the rest on the
/// next frames while the best so far is shown.
pub fn rescore(n: *Names, gpa: std.mem.Allocator) void {
const q = n.queryText();
const empty = std.mem.trim(u8, q, " ").len == 0;
const started = pardes.FrameStats.nowNs();
const had = n.hits.items.len;
const was_scored = n.scored;
var count: usize = 0;
while (true) : (count += 1) {
const i: u32 = if (n.pending_at < n.pending.items.len) blk: {
n.pending_at += 1;
break :blk n.pending.items[n.pending_at - 1];
} else if (n.scored < n.cands.items.len) blk: {
n.scored += 1;
break :blk n.scored - 1;
} else break;
const c = n.cands.items[i];
const key = n.bytes.items[c.start + c.key ..][0..c.key_len];
const s = if (empty) 0 else match(q, key, n.lower.items[c.start + c.key ..][0..c.key_len], c.base, null, null, null);
if (s) |score| n.hits.append(gpa, .{ .cand = i, .score = score }) catch break;
// The clock every 256 candidates: reading it is not free either.
if (!empty and count % 256 == 255 and pardes.tape.over(started, score_budget_ns)) break;
}
// An empty query keeps the source's order (the walk's, recency): no
// row moves as the walk goes on, it only grows at the foot.
if (!empty) std.sort.pdq(Hit, n.hits.items, n.cands.items, struct {
fn lt(cands: []const Cand, a: Hit, b: Hit) bool {
if (a.score != b.score) return a.score > b.score;
const la = cands[a.cand].key_len;
const lb = cands[b.cand].key_len;
if (la != lb) return la < lb;
return a.cand < b.cand;
}
}.lt);
if (n.hits.items.len != had or n.scored != was_scored or count > 0) n.gen +%= 1;
}
/// The row of hit `i` and, in `marks`, the bytes of it the query matched.
pub fn row(n: *const Names, i: usize, marks: []u16, nmarks: *usize) []const u8 {
const c = n.cands.items[n.hits.items[i].cand];
nmarks.* = 0;
const q = n.queryText();
if (std.mem.trim(u8, q, " ").len > 0) {
const key = n.bytes.items[c.start + c.key ..][0..c.key_len];
_ = match(q, key, n.lower.items[c.start + c.key ..][0..c.key_len], c.base, marks, nmarks, &dp_trace);
for (marks[0..nmarks.*]) |*m| m.* += c.key;
}
return n.bytes.items[c.start..][0..c.len];
}
// ---- the scorer (pick's) ----
const neg: i32 = -(1 << 24);
const score_match = 16;
const gap_start = 3;
const gap_ext = 1;
const bonus_consecutive = 7;
/// At the start of the text or of a path segment.
const bonus_start = 12;
/// After `_ - . : space`.
const bonus_delim = 9;
/// A camelCase hump, or a word after other punctuation.
const bonus_camel = 8;
/// Each matched character in the basename.
const bonus_base = 2;
/// The scorer's two rows, and the whole table the marks are backtracked
/// through: the main loop's, one score at a time. Not locals: a safe build
/// fills an undefined local, 4 KB a candidate, which was most of a
/// keystroke's time.
var dp_rows: [2][max_text]i32 = undefined;
var dp_trace: [max_query * max_text]i32 = undefined;
fn bonusAt(text: []const u8, j: usize) i32 {
if (j == 0) return bonus_start;
const prev = text[j - 1];
const c = text[j];
if (prev == '/') return bonus_start;
switch (prev) {
'_', '-', '.', ':', ' ', '\t' => return bonus_delim,
else => {},
}
if (std.ascii.isLower(prev) and std.ascii.isUpper(c)) return bonus_camel;
if (!std.ascii.isAlphanumeric(prev) and std.ascii.isAlphanumeric(c)) return bonus_camel;
return 0;
}
/// `query`'s score against `text` (`lower` its lowercase copy, its
/// basename from `base`), null if some term of it is not a subsequence of
/// `text`. Terms split on spaces are ANDed; smart case per term. With
/// `marks`, the bytes matched are written there, ascending.
pub fn match(query: []const u8, text_in: []const u8, lower_in: []const u8, base: usize, marks: ?[]u16, marks_len: ?*usize, trace: ?[]i32) ?i32 {
const text = text_in[0..@min(text_in.len, max_text)];
const lower = lower_in[0..text.len];
var total: i32 = 0;
var nmarks: usize = 0;
var terms = std.mem.tokenizeScalar(u8, query, ' ');
while (terms.next()) |term_in| {
const term = term_in[0..@min(term_in.len, max_query)];
const m = term.len;
const sensitive = for (term) |c| {
if (std.ascii.isUpper(c)) break true;
} else false;
// A lowercase term is matched against the lowercase copy.
var low_buf: [max_query]u8 = undefined;
const want = if (sensitive) term else std.ascii.lowerString(&low_buf, term);
const hay = if (sensitive) text else lower;
// The window a match can be in: from the first character's first
// place to the last one's last place, else no match at all.
const lo = std.mem.indexOfScalar(u8, hay, want[0]) orelse return null;
var pos = lo + 1;
for (want[1..]) |c| pos = (std.mem.indexOfScalarPos(u8, hay, pos, c) orelse return null) + 1;
const end = std.mem.lastIndexOfScalar(u8, hay, want[m - 1]).? + 1;
// D[i][j]: the best score with term[i] matched at text[j].
var prev = &dp_rows[0];
var cur = &dp_rows[1];
const width = text.len;
const keep = if (trace) |t| t.len >= m * width else false;
for (0..m) |i| {
var gapped: i32 = neg; // max over k <= j-2 of D[i-1][k], less the gap to j
for (lo..end) |col| {
var best: i32 = neg;
if (i > 0 and col >= lo + 2) gapped = @max(gapped - gap_ext, prev[col - 2] - gap_start);
if (hay[col] == want[i]) {
const own: i32 = score_match + bonusAt(text, col) + @as(i32, if (col >= base) bonus_base else 0);
if (i == 0) {
best = own;
} else if (col > lo) {
const from = @max(if (prev[col - 1] > neg) prev[col - 1] + bonus_consecutive else neg, gapped);
if (from > neg) best = from + own;
}
}
cur[col] = best;
if (keep) trace.?[i * width + col] = best;
}
const t = prev;
prev = cur;
cur = t;
}
var best: i32 = neg;
var at: usize = lo;
for (lo..end) |col| if (prev[col] > best) {
best = prev[col];
at = col;
};
if (best <= neg) return null;
total += best;
// Back from the best end, the place each character was matched at.
if (keep and marks != null) {
const out = marks.?;
const t = trace.?;
var i = m;
var col = at;
while (i > 0) {
i -= 1;
if (nmarks < out.len) {
out[nmarks] = @intCast(col);
nmarks += 1;
}
if (i == 0) break;
const here = t[i * width + col];
const own: i32 = score_match + bonusAt(text, col) + @as(i32, if (col >= base) bonus_base else 0);
if (col > lo and t[(i - 1) * width + col - 1] > neg and t[(i - 1) * width + col - 1] + bonus_consecutive + own == here) {
col -= 1;
continue;
}
var found = col - 1;
if (col >= lo + 2) {
var k = col - 2;
while (true) {
const d = t[(i - 1) * width + k];
if (d > neg and d - gap_start - @as(i32, @intCast(col - 2 - k)) * gap_ext + own == here) {
found = k;
break;
}
if (k == lo) break;
k -= 1;
}
}
col = found;
}
}
}
if (marks_len) |count| {
if (marks) |out| std.mem.sort(u16, out[0..nmarks], {}, std.sort.asc(u16));
count.* = nmarks;
}
return total;
}
const test_paths = [_][]const u8{
"src/layout.zig", "src/locations.zig", "src/Output.zig", "src/hunks.zig",
"src/pardes.zig", "src/pdf.zig", "src/look.zig", "src/syntax.zig",
"src/body_layer.zig", "build.zig", "src/ninep/ctl.zig", "docs/helix-keys.md",
"notes/helix-keys.md", "src/gui/Post.zig", "cmd/tool/ui_review.py",
};
fn topFor(q: []const u8) []const u8 {
var best: ?[]const u8 = null;
var best_score: i32 = std.math.minInt(i32);
for (test_paths) |path| {
var low: [256]u8 = undefined;
const s = match(q, path, std.ascii.lowerString(&low, path), baseOf(path), null, null, null) orelse continue;
if (s > best_score or (s == best_score and path.len < best.?.len)) {
best = path;
best_score = s;
}
}
return best orelse "";
}
test "Names ranks real paths as the pick prototype did" {
try std.testing.expectEqualStrings("src/layout.zig", topFor("layout"));
try std.testing.expectEqualStrings("src/Output.zig", topFor("out"));
try std.testing.expectEqualStrings("src/pardes.zig", topFor("prz"));
try std.testing.expectEqualStrings("src/body_layer.zig", topFor("bl"));
try std.testing.expectEqualStrings("src/ninep/ctl.zig", topFor("ctl ninep"));
try std.testing.expectEqualStrings("docs/helix-keys.md", topFor("helkey"));
try std.testing.expectEqualStrings("src/gui/Post.zig", topFor("gui/po"));
try std.testing.expectEqualStrings("src/Output.zig", topFor("Out"));
}
|