From 51903dd947f90381d1a908c488a019289a1c8413 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Sat, 24 Oct 2026 11:57:26 -0300 Subject: Search converge 3/6: the query pane, line 1 the query and its first word the source, rows made live like Callstack's, the owner's places showing the set, a +Preview promoted in place, Enter freezes, Esc restores --- src/Names.zig | 446 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 446 insertions(+) create mode 100644 src/Names.zig (limited to 'src/Names.zig') 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")); +} -- cgit v1.3