//! 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"); /// 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, /// The query is `query_buf[0..query_len]`: what lies past it is undefined /// (0xAA in Debug, not in a release build), so no digest reads it. pub const replica = .{ .len = .{.{ "query_buf", "query_len" }} }; 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) error{OutOfMemory}!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 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); 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); 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 (the table they /// are backtracked through is `dp_trace`). fn match(query: []const u8, text_in: []const u8, lower_in: []const u8, base: usize, marks: ?[]u16, marks_len: ?*usize) ?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 = marks != null; 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) dp_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) { const out = marks.?; const t = &dp_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) 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")); }