diff options
| author | Gabriel Schneider <[email protected]> | 2026-10-30 17:35:06 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-10-30 17:35:06 -0300 |
| commit | 6d8da8721141284cf33bb901168b26135893eb86 (patch) | |
| tree | 791d63401d4e85fbca1d597a8ce0326e70efd545 /src/Names.zig | |
| parent | efd43a3a2cf03bb741366331158b368abf9ac583 (diff) | |
| parent | bf6810a8f9d6cc82050e7d9c0cfb06358301b574 (diff) | |
| download | pardes-6d8da8721141284cf33bb901168b26135893eb86.tar.gz pardes-6d8da8721141284cf33bb901168b26135893eb86.zip | |
Merge latest upstream into the macOS branch for Zig 0.17
Retain the macOS branch history and local Acme selection color while adopting upstream's current core and platform changes. Pin Zig and ZLS to 0.17.0, and fetch the existing zstbi compatibility commit through upstream after its original fork was removed.
Diffstat (limited to 'src/Names.zig')
| -rw-r--r-- | src/Names.zig | 367 |
1 files changed, 367 insertions, 0 deletions
diff --git a/src/Names.zig b/src/Names.zig new file mode 100644 index 00000000..0c8ba075 --- /dev/null +++ b/src/Names.zig @@ -0,0 +1,367 @@ +//! 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 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")); +} |
