summaryrefslogtreecommitdiff
path: root/src/Names.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/Names.zig')
-rw-r--r--src/Names.zig446
1 files changed, 446 insertions, 0 deletions
diff --git a/src/Names.zig b/src/Names.zig
new file mode 100644
index 00000000..48447f56
--- /dev/null
+++ b/src/Names.zig
@@ -0,0 +1,446 @@
+//! Names a query pane picks from by a fuzzy query: the files under a
+//! directory (walked a slice a frame), 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 filesystem = @import("fs.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,
+/// The files walk, while it lasts (Find in a query pane until the disk
+/// engine has it).
+walk: ?Walk = null,
+/// 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;
+/// Entries a walk reads a frame: ~1-3 ms warm.
+const walk_slice = 2000;
+const walk_max_depth = 16;
+/// A keystroke's scoring, and a frame's: what is left waits a frame.
+const score_budget_ns = 4 * std.time.ns_per_ms;
+
+const Walk = struct {
+ root: std.Io.Dir,
+ walker: std.Io.Dir.SelectiveWalker,
+ done: bool = false,
+ skipped: u32 = 0,
+
+ fn deinit(w: *Walk) void {
+ const io = std.Io.Threaded.global_single_threaded.io();
+ // The walker closes a directory only as it leaves it: the ones it
+ // is still in (all but the root, which is ours) are closed here.
+ if (w.walker.stack.items.len > 1) for (w.walker.stack.items[1..]) |*item| item.iter.reader.dir.close(io);
+ w.walker.deinit();
+ w.root.close(io);
+ }
+};
+
+pub fn deinit(n: *Names, gpa: std.mem.Allocator) void {
+ if (n.walk) |*w| w.deinit();
+ 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 {
+ if (n.walk) |*w| w.deinit();
+ n.walk = null;
+ 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));
+}
+
+/// The files under `dir`, walked from now on a slice a frame (`walkSlice`):
+/// the first slice now, so a small tree is whole before the first frame.
+pub fn startWalk(n: *Names, gpa: std.mem.Allocator, dir: []const u8) !void {
+ if (comptime !filesystem.platform_has_fs) return error.NoFilesystem;
+ const io = std.Io.Threaded.global_single_threaded.io();
+ pardes.turn.yield();
+ defer pardes.turn.back();
+ var dir_handle = try std.Io.Dir.cwd().openDir(io, dir, .{ .iterate = true });
+ errdefer dir_handle.close(io);
+ n.walk = .{ .root = dir_handle, .walker = try dir_handle.walkSelectively(gpa) };
+ n.walkSlice(gpa);
+}
+
+/// One frame's slice of a walk: up to `walk_slice` entries, files kept,
+/// what a Find skips skipped and dot-directories too.
+pub fn walkSlice(n: *Names, gpa: std.mem.Allocator) void {
+ const w = if (n.walk) |*w| w else return;
+ if (w.done) return;
+ const io = std.Io.Threaded.global_single_threaded.io();
+ pardes.turn.yield();
+ defer pardes.turn.back();
+ var steps: usize = 0;
+ walk: while (steps < walk_slice) : (steps += 1) {
+ const e = (w.walker.next(io) catch {
+ w.skipped += 1;
+ continue;
+ }) orelse {
+ w.done = true;
+ break;
+ };
+ if (e.kind != .directory) {
+ n.add(gpa, e.path, 0, e.path.len, baseOf(e.path), 0) catch {
+ w.done = true;
+ break;
+ };
+ if (n.cands.items.len >= max_cands) {
+ w.done = true;
+ break;
+ }
+ continue;
+ }
+ if (e.depth() >= walk_max_depth or e.basename[0] == '.') continue;
+ for (filesystem.find_skip) |s| if (std.mem.eql(u8, e.basename, s)) continue :walk;
+ w.walker.enter(io, e) catch {
+ w.skipped += 1;
+ };
+ }
+}
+
+pub fn walking(n: *const Names) bool {
+ return if (n.walk) |w| !w.done else false;
+}
+
+/// Still walking, or still scoring what it has: it wants the next frame.
+pub fn busy(n: *const Names) bool {
+ return n.walking() or 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 io = std.Io.Threaded.global_single_threaded.io();
+ const started = std.Io.Clock.awake.now(io);
+ 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
+ started.durationTo(std.Io.Clock.awake.now(io)).toNanoseconds() > 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"));
+}