summaryrefslogtreecommitdiff
path: root/src/Places.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-10-24 10:29:10 -0300
committerGabriel Schneider <[email protected]>2026-10-24 10:29:10 -0300
commit18d89dcedaed1f8437799621675e88ca47d7cdc1 (patch)
tree2cf2e2ae46de1308e5b90aca33413282cdd73e8b /src/Places.zig
parent873f81ccb1449119846de8d4e6e0e8899236100a (diff)
downloadpardes-18d89dcedaed1f8437799621675e88ca47d7cdc1.tar.gz
pardes-18d89dcedaed1f8437799621675e88ca47d7cdc1.zip
Search converge 2/6: a pane's places, every match or listed place tinted and ticked on the rail, n/N stepping them silently, shifted by an edit rather than searched again
Diffstat (limited to 'src/Places.zig')
-rw-r--r--src/Places.zig849
1 files changed, 849 insertions, 0 deletions
diff --git a/src/Places.zig b/src/Places.zig
new file mode 100644
index 00000000..435a138a
--- /dev/null
+++ b/src/Places.zig
@@ -0,0 +1,849 @@
+//! A pane's places: where in its text the current search, or the current
+//! list, says to look, and which of them is current. A query pane typed
+//! into under this pane feeds them (`/pat` as it is typed, a Grep's hits
+//! in this file, a language server's references), so do `*` and the `/`
+//! register; whichever fed them last is their provenance. They are shown
+//! three ways that read these fields and nothing else, so they cannot
+//! disagree: every place tinted in the body (the current one stronger), a
+//! tick on the scroll rail at each one's place in the file (B1 on a tick
+//! goes there), and the current one selected and in view. n and N step
+//! them, round the end without a word (the count in the query pane's tag
+//! says where you are).
+//!
+//! A pattern's places are found where the text is shown first, then on to
+//! the end, then from the top up to where it started, a frame's budget at
+//! a time (`fill`, run after every step and on every tick until done), so
+//! a keystroke in a big file costs what its view costs. They are for one
+//! revision of the text: an edit shifts the ones it did not touch and
+//! finds again only on the lines it touched (File.State.splice), so typing
+//! in a pane whose places are shown costs a line, not the file.
+const std = @import("std");
+const pardes = @import("pardes.zig");
+const panes = @import("panes.zig");
+const modal = @import("modal.zig");
+const colors = @import("colors.zig");
+const regexp = @import("regexp.zig");
+const normal = @import("normal.zig");
+const memory = @import("memory.zig");
+const Surface = @import("surface.zig").Surface;
+const Pardes = pardes.Pardes;
+const Pane = panes.Pane;
+const Text = panes.Text;
+const File = panes.File;
+
+const Places = @This();
+
+/// One place: byte offsets into the file's text, `end` past its last byte.
+pub const Hit = struct { start: usize, end: usize };
+
+/// What fed them. `typed`: a query pane's `/pat` while it is typed, not
+/// in the `/` register yet. `search`: the `/` register's pattern (a query
+/// answered with Enter, `*`). `list`: a list's places in this text (a
+/// Grep's hits in an open file, every pane's for All, a language server's
+/// references or diagnostics), matched as given.
+pub const Provenance = enum { typed, search, list };
+
+/// Places past this many are not kept. ponytail: 16 bytes a place, 16 MB
+/// at the cap; a sparse count past it if a million is ever too few.
+pub const max_hits = 1 << 20;
+/// What one frame spends finding places: about 4 ms on the clock, checked
+/// between pieces of the text; mvzr's steps (Regex.budget is about 300 ms
+/// of them, so this is about 5 ms), which bound one slow piece; and bytes
+/// read, the bound where there is no clock (the board, the web).
+pub const frame_ns: u64 = 4 * std.time.ns_per_ms;
+pub const frame_steps: u64 = regexp.Regex.budget / 64;
+pub const frame_bytes: usize = 8 << 20;
+/// The text is searched in pieces of about this much, each ending at a
+/// line's end, so that a budget runs out between pieces, not inside one.
+/// A folding set lowers its copy of the text a piece at a time too.
+const chunk_bytes = 16 << 10;
+/// A rail's ticks are placed to 1/`tick_scale` of the file.
+pub const tick_scale = @import("surface.zig").rail_tick_scale;
+
+pub fn nowNs() u64 {
+ if (comptime !pardes.hosted) return 0;
+ var ts: std.c.timespec = undefined;
+ if (std.c.clock_gettime(.MONOTONIC, &ts) != 0) return 0;
+ return @as(u64, @intCast(ts.sec)) *| std.time.ns_per_s +| @as(u64, @intCast(ts.nsec));
+}
+
+started: bool = false,
+provenance: Provenance = .search,
+/// The query pane that fed them, by serial; 0 for `*` and the register.
+from: u32 = 0,
+/// The pattern as it was typed (gpa); empty for a list's places.
+pattern: []u8 = &.{},
+/// It did not compile as a regex (`foo(` while typing `foo(x)`), or it is
+/// a Grep's: matched as the characters it is.
+literal: bool = false,
+/// No capital in it: matched without regard to case, on a lowered copy.
+fold: bool = false,
+re: ?normal.SearchRegex = null,
+/// The lowered copy of the text a folding set searches (gpa), of the text
+/// at `hay_revision`, lowered a piece at a time as it is searched (`low`,
+/// one bit a `chunk_bytes`): kept across patterns, spliced by an edit.
+hay: []u8 = &.{},
+hay_revision: u32 = 0,
+low: std.DynamicBitSetUnmanaged = .{},
+/// Sorted, apart from one another.
+hits: std.ArrayList(Hit) = .empty,
+/// The text the places are of: its revision and length.
+revision: u32 = 0,
+len: usize = 0,
+/// What has been searched: [lo, hi) from the view on, then [0, head_to).
+/// `nhead` of the hits are from the second, all before `lo`.
+lo: usize = 0,
+hi: usize = 0,
+head_to: usize = 0,
+nhead: usize = 0,
+/// Where the last budget ran out: a line too slow for a whole frame's
+/// budget, run out at twice, is passed over and counted.
+stuck_at: ?usize = null,
+skipped: u32 = 0,
+capped: bool = false,
+current: ?usize = null,
+/// The first place at or after this offset becomes current once the
+/// search has got there; with `seek_moves` it takes the selection and view.
+seek: ?usize = null,
+seek_moves: bool = false,
+/// The last step went round the end of the text (or its start). Said by
+/// nothing but the count wrapping in the query pane's tag.
+wrapped: bool = false,
+/// Moves with every change to the places or the current one (the ticks'
+/// cue and the query pane's); `hits_gen` only with the places.
+gen: u32 = 0,
+hits_gen: u32 = 0,
+ticks: std.ArrayList(u16) = .empty,
+ticks_gen: u32 = std.math.maxInt(u32),
+/// The body as it was when a query began, for Esc to put back exactly
+/// (gpa; empty: nothing remembered).
+snap: []modal.Selection = &.{},
+snap_pri: usize = 0,
+snap_expl: bool = false,
+snap_scroll: usize = 0,
+snap_hscroll: i32 = 0,
+
+pub fn deinit(set: *Places, gpa: std.mem.Allocator) void {
+ set.clear(gpa);
+ if (set.hay.len > 0) gpa.rawFree(set.hay, .of(u8), @returnAddress());
+ set.low.deinit(gpa);
+ set.hits.deinit(gpa);
+ set.ticks.deinit(gpa);
+ gpa.free(set.snap);
+ set.* = .{};
+}
+
+/// No places here any more: no tint, no ticks.
+pub fn clear(set: *Places, gpa: std.mem.Allocator) void {
+ if (set.re) |re| gpa.free(re.branches);
+ set.re = null;
+ gpa.free(set.pattern);
+ set.pattern = &.{};
+ set.hits.clearRetainingCapacity();
+ set.started = false;
+ set.from = 0;
+ set.current = null;
+ set.seek = null;
+ set.wrapped = false;
+ set.gen +%= 1;
+ set.hits_gen +%= 1;
+}
+
+/// Whether the body and the rail show these places now: never a stale set.
+pub fn shows(set: *const Places, pane: *const Pane) bool {
+ const f = pane.file orelse return false;
+ return set.started and set.revision == f.revision and set.len == f.content.len;
+}
+
+pub fn complete(set: *const Places) bool {
+ return set.hi >= set.len and set.head_to >= set.lo;
+}
+
+/// The first hit starting at or after `at`.
+pub fn firstFrom(hits: []const Hit, at: usize) usize {
+ var lo: usize = 0;
+ var hi = hits.len;
+ while (lo < hi) {
+ const mid = lo + (hi - lo) / 2;
+ if (hits[mid].start < at) lo = mid + 1 else hi = mid;
+ }
+ return lo;
+}
+
+/// Search `pane`'s text for `pattern` from now on, in place of whatever
+/// fed the places before. A regex unless `literal`, smart case (no capital:
+/// any case); one that does not compile is matched literally, so a pattern
+/// half typed still finds what it says. `seek`: the place at or after it
+/// becomes current, and with `moves` the selection and view go to it.
+pub fn search(set: *Places, p: *Pardes, pane: *Pane, provenance: Provenance, from: u32, pattern: []const u8, literal: bool, seek: ?usize, moves: bool) void {
+ const f = if (pane.file) |*file| file else return;
+ const gpa = p.gpa;
+ // The same question again (a key that left the pattern as it was):
+ // the places stand, the current one too.
+ if (set.started and set.re != null and set.literal == literal and std.mem.eql(u8, set.pattern, pattern)) {
+ set.provenance = provenance;
+ set.from = from;
+ return;
+ }
+ set.clear(gpa);
+ if (pattern.len == 0) return;
+ set.pattern = gpa.dupe(u8, pattern) catch return;
+ set.provenance = provenance;
+ set.from = from;
+ set.fold = for (pattern) |c| {
+ if (std.ascii.isUpper(c)) break false;
+ } else true;
+ set.literal = literal;
+ const arena = p.scratch.allocator();
+ const folded = if (set.fold) std.ascii.allocLowerString(arena, pattern) catch return else pattern;
+ set.re = if (literal) null else normal.SearchRegex.compile(gpa, folded) catch null;
+ if (set.re == null) {
+ set.literal = true;
+ var escaped: std.ArrayList(u8) = .empty;
+ normal.appendSearchLiteral(&escaped, arena, folded) catch return;
+ set.re = normal.SearchRegex.compile(gpa, escaped.items) catch return;
+ }
+ set.started = true;
+ set.revision = f.revision +% 1; // `fill` starts it over for the text as it is
+ set.seek = seek;
+ set.seek_moves = moves;
+ set.fill(p, pane, frame_bytes, frame_steps);
+}
+
+/// A list's places in this text, as it gives them (sorted here), in place
+/// of whatever fed them before: a language server's references, say.
+/// `current`: the one at or after this offset is current.
+pub fn feed(set: *Places, p: *Pardes, pane: *Pane, from: u32, hits: []const Hit, current: ?usize) void {
+ const f = if (pane.file) |*file| file else return;
+ set.clear(p.gpa);
+ set.hits.ensureTotalCapacity(p.gpa, hits.len) catch return;
+ for (hits) |h| if (h.end > h.start and h.end <= f.content.len) set.hits.appendAssumeCapacity(h);
+ std.mem.sort(Hit, set.hits.items, {}, struct {
+ fn lt(_: void, a: Hit, b: Hit) bool {
+ return a.start < b.start;
+ }
+ }.lt);
+ set.started = true;
+ set.provenance = .list;
+ set.from = from;
+ set.revision = f.revision;
+ set.len = f.content.len;
+ set.lo = 0;
+ set.hi = f.content.len;
+ set.head_to = 0;
+ set.nhead = 0;
+ if (current) |at| {
+ const i = firstFrom(set.hits.items, at);
+ set.current = if (i < set.hits.items.len) i else if (set.hits.items.len > 0) 0 else null;
+ }
+ set.hits_gen +%= 1;
+}
+
+/// The lowered copy's pieces holding [from, to) lowered, as they are
+/// first searched.
+fn lower(set: *Places, content: []const u8, from: usize, to: usize) void {
+ if (to <= from) return;
+ var b = from / chunk_bytes;
+ const last = (to - 1) / chunk_bytes;
+ while (b <= last and b < set.low.bit_length) : (b += 1) {
+ if (set.low.isSet(b)) continue;
+ const lo = b * chunk_bytes;
+ const hi = @min(content.len, lo + chunk_bytes);
+ _ = std.ascii.lowerString(set.hay[lo..hi], content[lo..hi]);
+ set.low.set(b);
+ }
+}
+
+/// A fresh lowered copy for the text as it is now, nothing of it lowered.
+fn freshHay(set: *Places, gpa: std.mem.Allocator, f: *File.State) bool {
+ if (set.hay.len > 0) gpa.rawFree(set.hay, .of(u8), @returnAddress());
+ set.hay = &.{};
+ set.hay = memory.unfilled(gpa, f.content.len) catch return false;
+ set.low.resize(gpa, (f.content.len + chunk_bytes - 1) / chunk_bytes, false) catch return false;
+ set.low.unsetAll();
+ set.hay_revision = f.revision;
+ return true;
+}
+
+/// The text changed by one splice since the places were found (`fill`
+/// checks): the ones before the lines it touched kept, the ones after
+/// moved by what it added or took, those lines searched again. A list's
+/// places on them are dropped (nothing says where they went). Costs the
+/// places and the lines, never the whole text.
+fn shift(set: *Places, p: *Pardes, f: *File.State) void {
+ const gpa = p.gpa;
+ const new = f.content;
+ const sp = f.splice;
+ const old_len = sp.old_len;
+ const head = @min(sp.head, new.len);
+ const tail_new = new.len - @min(sp.tail, new.len - head);
+ // The lines it touched, in the new text and in the old.
+ const ds = if (std.mem.lastIndexOfScalar(u8, new[0..head], '\n')) |nl| nl + 1 else 0;
+ const de = if (std.mem.indexOfScalarPos(u8, new, tail_new, '\n')) |nl| nl + 1 else new.len;
+ const ode = de + old_len - new.len;
+ var kept: usize = 0;
+ var after: usize = set.hits.items.len;
+ for (set.hits.items, 0..) |h, i| {
+ if (h.end <= ds) kept = i + 1;
+ if (h.start >= ode) {
+ after = i;
+ break;
+ }
+ }
+ const old_current = set.current;
+ // The lowered copy takes the same splice.
+ if (set.fold) {
+ const hay = memory.unfilled(gpa, new.len) catch return set.restart(p, f);
+ @memcpy(hay[0..head], set.hay[0..head]);
+ const tail_len = new.len - tail_new;
+ @memcpy(hay[tail_new..], set.hay[old_len - tail_len ..]);
+ _ = std.ascii.lowerString(hay[head..tail_new], new[head..tail_new]);
+ if (set.hay.len > 0) gpa.rawFree(set.hay, .of(u8), @returnAddress());
+ set.hay = hay;
+ set.low.resize(gpa, (new.len + chunk_bytes - 1) / chunk_bytes, true) catch return set.restart(p, f);
+ set.low.setAll();
+ set.hay_revision = f.revision;
+ }
+ // The lines it touched, searched again: what lies between.
+ var middle: std.ArrayList(Hit) = .empty;
+ defer middle.deinit(gpa);
+ if (set.re) |*re| {
+ const hay: []const u8 = if (set.fold) set.hay else new;
+ for (re.branches) |*b| b.re.steps = regexp.Regex.budget;
+ var at = ds;
+ while (at < de) {
+ const m = re.find(hay, at, de) orelse break;
+ if (m.start >= de) break;
+ if (m.end > m.start) middle.append(gpa, .{ .start = m.start, .end = m.end }) catch break;
+ at = if (m.end > m.start) m.end else m.end + 1;
+ }
+ }
+ const delta_add = new.len >= old_len;
+ for (set.hits.items[after..]) |*h| {
+ if (delta_add) {
+ h.start += new.len - old_len;
+ h.end += new.len - old_len;
+ } else {
+ h.start -= old_len - new.len;
+ h.end -= old_len - new.len;
+ }
+ }
+ set.hits.replaceRange(gpa, kept, after - kept, middle.items) catch return set.restart(p, f);
+ set.current = null;
+ if (old_current) |c| {
+ if (c < kept) set.current = c else if (c >= after) set.current = c - after + kept + middle.items.len else {
+ // It was on the lines touched: the first there now, or after.
+ set.seek = ds;
+ set.seek_moves = false;
+ }
+ }
+ set.revision = f.revision;
+ set.len = new.len;
+ set.lo = 0;
+ set.hi = new.len;
+ set.head_to = 0;
+ set.nhead = 0;
+ set.gen +%= 1;
+ set.hits_gen +%= 1;
+}
+
+/// The places found again from nothing for the text as it is, the view
+/// first; the current one looked for where it was.
+fn restart(set: *Places, p: *Pardes, f: *File.State) void {
+ const gpa = p.gpa;
+ if (set.current) |c| if (set.seek == null and c < set.hits.items.len) {
+ set.seek = @min(set.hits.items[c].start, f.content.len);
+ set.seek_moves = false;
+ };
+ set.current = null;
+ set.hits.clearRetainingCapacity();
+ set.revision = f.revision;
+ set.len = f.content.len;
+ set.lo = File.lineStart(gpa, f, f.scroll);
+ set.hi = set.lo;
+ set.head_to = 0;
+ set.nhead = 0;
+ set.stuck_at = null;
+ set.skipped = 0;
+ set.capped = false;
+ set.gen +%= 1;
+ set.hits_gen +%= 1;
+ if (set.re == null) {
+ // A list's places have no pattern to be found again by: kept where
+ // the text still has room for them. ponytail: they go stale by what
+ // was added above them, until the list is asked again.
+ set.lo = 0;
+ set.hi = f.content.len;
+ }
+}
+
+/// Find more of the places, `bytes` of text and `steps` of mvzr's at most,
+/// the rows the pane shows always; and once the current place's offset has
+/// been searched, make it current. Run after every step (with no budget:
+/// the view only) and every tick (a frame's).
+pub fn fill(set: *Places, p: *Pardes, pane: *Pane, bytes: usize, steps: u64) void {
+ const started_ns = nowNs();
+ if (!set.started) return;
+ const f = if (pane.file) |*file| file else return set.clear(p.gpa);
+ const gpa = p.gpa;
+ if (f.revision != set.revision or f.content.len != set.len) {
+ const spans = if (set.re) |re| for (re.branches) |b| {
+ if (b.re.spans) break true;
+ } else false else false;
+ const one_splice = f.splice.revision == f.revision and set.revision +% 1 == f.revision and
+ f.splice.old_len == set.len and set.complete() and !spans and
+ (!set.fold or set.hay_revision == set.revision);
+ if (one_splice) set.shift(p, f) else set.restart(p, f);
+ if (set.re == null) {
+ // a list's: clamp what the text has no room for any more
+ var n: usize = 0;
+ for (set.hits.items) |h| if (h.end <= f.content.len) {
+ set.hits.items[n] = h;
+ n += 1;
+ };
+ set.hits.shrinkRetainingCapacity(n);
+ if (set.current) |c| if (c >= n) {
+ set.current = null;
+ };
+ }
+ }
+ if (set.fold and (set.hay_revision != f.revision or set.hay.len != f.content.len))
+ if (!set.freshHay(gpa, f)) return set.clear(gpa);
+ if (set.re == null) return set.settleSeek(p, pane);
+ const re = &set.re.?;
+ const hay: []const u8 = if (set.fold) set.hay else f.content;
+ for (re.branches) |*b| b.re.steps = @max(1, steps / re.branches.len);
+ // A pattern naming a newline matches across lines: searched in one piece.
+ const spans = for (re.branches) |b| {
+ if (b.re.spans) break true;
+ } else false;
+ const view_end = File.lineStart(gpa, f, f.scroll + pane.rows + 1);
+ var left = bytes;
+ var head: std.ArrayList(Hit) = .empty;
+ defer head.deinit(gpa);
+ const found_before = set.hits.items.len;
+ while (left > 0 or (set.hi < view_end and set.hi >= set.lo)) {
+ const forward = set.hi < set.len;
+ if (!forward and set.head_to >= set.lo) break;
+ const from = if (forward) set.hi else set.head_to;
+ const limit = if (forward) set.len else set.lo;
+ var to = if (spans) limit else @min(limit, from + chunk_bytes);
+ if (to < limit) to = if (std.mem.indexOfScalarPos(u8, f.content, to, '\n')) |nl| @min(limit, nl + 1) else limit;
+ if (set.fold) set.lower(f.content, from -| 1, @min(f.content.len, to + 1));
+ // Each piece is searched as sam searches a range (normal.zig
+ // applySelRegex): the text around it still says where lines begin.
+ var at = from;
+ var short = false;
+ const out = if (forward) &set.hits else &head;
+ head.clearRetainingCapacity();
+ while (at < to) {
+ if (set.hits.items.len + head.items.len >= max_hits) {
+ set.capped = true;
+ at = to;
+ break;
+ }
+ const m = re.find(hay, at, to) orelse {
+ for (re.branches) |b| if (b.re.steps == 0) {
+ short = true;
+ };
+ if (!short) at = to;
+ break;
+ };
+ if (m.start >= to) {
+ at = to;
+ break;
+ }
+ if (m.end > m.start) out.append(gpa, .{ .start = m.start, .end = m.end }) catch return;
+ at = if (m.end > m.start) m.end else m.end + 1;
+ }
+ at = @min(at, to);
+ if (short) {
+ // Spent: the rest next frame, from here. Spent here twice, the
+ // line is past searching and is passed over.
+ if (set.stuck_at == at) {
+ at = if (std.mem.indexOfScalarPos(u8, hay, at, '\n')) |nl| @min(to, nl + 1) else to;
+ set.skipped += 1;
+ set.stuck_at = null;
+ } else set.stuck_at = at;
+ }
+ if (forward) set.hi = at else {
+ set.hits.insertSlice(gpa, set.nhead, head.items) catch return;
+ if (set.current) |*c| c.* += head.items.len;
+ set.nhead += head.items.len;
+ set.head_to = at;
+ }
+ left -|= at - from;
+ if (short) break;
+ // A frame's time spent (a whole search's for n and N, whose steps
+ // are mvzr's whole budget).
+ if (started_ns != 0 and bytes != std.math.maxInt(usize) and nowNs() - started_ns > frame_ns) break;
+ }
+ if (set.hits.items.len != found_before) {
+ set.gen +%= 1;
+ set.hits_gen +%= 1;
+ }
+ set.settleSeek(p, pane);
+}
+
+/// The place at or after `seek` becomes current, once all the text
+/// between them has been searched (never a false "next" across a gap).
+fn settleSeek(set: *Places, p: *Pardes, pane: *Pane) void {
+ const seek = set.seek orelse return;
+ const hits = set.hits.items;
+ const i = firstFrom(hits, seek);
+ const between_to = if (i < hits.len) hits[i].start + 1 else set.len;
+ const searched = if (set.head_to >= set.lo) between_to <= set.hi else between_to <= set.head_to or (seek >= set.lo and between_to <= set.hi);
+ if (i < hits.len and searched) {
+ set.current = i;
+ set.wrapped = false;
+ } else if (set.complete()) {
+ set.current = if (hits.len > 0) 0 else null;
+ set.wrapped = hits.len > 0 and seek > 0;
+ } else return;
+ set.seek = null;
+ set.gen +%= 1;
+ if (!set.seek_moves) return;
+ if (set.current) |c| return set.goTo(pane, c, false);
+ // Nothing matches: the body as it was before the query, as helix
+ // leaves it.
+ set.restore(p, pane);
+}
+
+/// The places have more to do on a frame of their own: places still to
+/// find, or a text changed under them.
+pub fn busy(set: *const Places, pane: *const Pane) bool {
+ if (!set.started) return false;
+ const f = pane.file orelse return false;
+ return !set.complete() or set.revision != f.revision or set.len != f.content.len;
+}
+
+/// Make place `i` current: the primary selection on it (a new one beside
+/// the others in select mode, `add`), the view on it, centred when it was
+/// off it.
+pub fn goTo(set: *Places, pane: *Pane, i: usize, add: bool) void {
+ const f = if (pane.file) |*file| file else return;
+ if (i >= set.hits.items.len) return;
+ const t = &pane.body;
+ const text = f.content;
+ const h = set.hits.items[i];
+ var ranges: [Text.max_selections]modal.Selection = undefined;
+ const got = t.ranges(text, 0, &ranges);
+ const old = ranges[got.pri];
+ const next: modal.Selection = if (old.anchor > old.head)
+ .{ .anchor = h.end, .head = h.start }
+ else
+ .{ .anchor = h.start, .head = h.end };
+ if (add and got.n < ranges.len) {
+ ranges[got.n] = next;
+ t.setRanges(text, ranges[0 .. got.n + 1], &.{}, got.n, true);
+ } else {
+ ranges[got.pri] = next;
+ t.setRanges(text, ranges[0..got.n], &.{}, got.pri, true);
+ }
+ set.current = i;
+ set.gen +%= 1;
+ const off = pane.scroll();
+ if (t.cur_row < off or t.cur_row >= off + @as(i32, pane.rows))
+ pane.scrollBy(t.cur_row - off - @divTrunc(@as(i32, pane.rows), 2));
+ t.show();
+}
+
+/// n and N (and Ctrl-n, Ctrl-p on a query's line): the next place after
+/// the primary selection, or the last before it, `count` times, round the
+/// end of the text when there is none, silently. It needs them all, so it
+/// finishes the search first. ponytail: within mvzr's whole budget (300
+/// ms), which a file of millions of lines can outrun; past it a step sees
+/// what was found.
+pub fn step(set: *Places, p: *Pardes, pane: *Pane, forward: bool, count: u32, add: bool) void {
+ const f = if (pane.file) |*file| file else return;
+ set.fill(p, pane, std.math.maxInt(usize), regexp.Regex.budget);
+ const hits = set.hits.items;
+ if (hits.len == 0) return;
+ const t = &pane.body;
+ var wrapped = false;
+ for (0..count) |_| {
+ var ranges: [Text.max_selections]modal.Selection = undefined;
+ const got = t.ranges(f.content, 0, &ranges);
+ const old = ranges[got.pri];
+ var i: usize = 0;
+ if (forward) {
+ i = firstFrom(hits, @max(old.anchor, old.head));
+ if (i == hits.len) {
+ i = 0;
+ wrapped = true;
+ }
+ } else {
+ const from = @min(old.anchor, old.head);
+ i = firstFrom(hits, from);
+ while (i > 0 and hits[i - 1].end > from) i -= 1;
+ if (i == 0) {
+ i = hits.len - 1;
+ wrapped = true;
+ } else i -= 1;
+ }
+ set.goTo(pane, i, add);
+ }
+ set.wrapped = wrapped;
+}
+
+/// Whether n and N in this pane are these places' to step: a list's or a
+/// query's always; a search's while it is what the register says (an `s`,
+/// a `/` elsewhere or `"a` since makes them helix's register search again).
+pub fn answersN(set: *const Places, p: *Pardes, pane: *const Pane) bool {
+ if (!set.shows(pane) and !set.started) return false;
+ if (set.provenance != .search) return p.register == 0;
+ const name = if (p.register != 0) p.register else p.registers.last_search;
+ const pat = p.registers.value(name, 0) orelse return false;
+ if (!set.literal) return std.mem.eql(u8, pat, set.pattern);
+ var spelled: std.ArrayList(u8) = .empty;
+ normal.appendSearchLiteral(&spelled, p.scratch.allocator(), set.pattern) catch return false;
+ return std.mem.eql(u8, pat, spelled.items) or std.mem.eql(u8, pat, set.pattern);
+}
+
+/// The body as it is now, for `restore` to put back: when a query begins.
+pub fn remember(set: *Places, p: *Pardes, pane: *Pane) void {
+ const f = if (pane.file) |*file| file else return;
+ var ranges: [Text.max_selections]modal.Selection = undefined;
+ const got = pane.body.ranges(f.content, 0, &ranges);
+ p.gpa.free(set.snap);
+ set.snap = p.gpa.dupe(modal.Selection, ranges[0..got.n]) catch &.{};
+ set.snap_pri = got.pri;
+ set.snap_expl = (pane.body.vsel.active and pane.body.vsel.explicit) or pane.body.msel.active;
+ set.snap_scroll = f.scroll;
+ set.snap_hscroll = pane.hscroll;
+}
+
+/// The body as `remember` kept it: its selections and its view.
+pub fn restore(set: *Places, p: *Pardes, pane: *Pane) void {
+ _ = p;
+ const f = if (pane.file) |*file| file else return;
+ if (set.snap.len == 0) return;
+ for (set.snap) |*r| {
+ r.anchor = @min(r.anchor, f.content.len);
+ r.head = @min(r.head, f.content.len);
+ }
+ pane.body.setRanges(f.content, set.snap, &.{}, set.snap_pri, set.snap_expl);
+ f.scroll = set.snap_scroll;
+ f.syntax_dirty = true;
+ pane.hscroll = set.snap_hscroll;
+}
+
+/// What `remember` kept, let go: the query was answered.
+pub fn forget(set: *Places, gpa: std.mem.Allocator) void {
+ gpa.free(set.snap);
+ set.snap = &.{};
+}
+
+/// Where the query began: the primary selection's end when it was
+/// remembered, else now.
+pub fn origin(set: *const Places, pane: *const Pane) usize {
+ if (set.snap.len > 0) return @max(set.snap[set.snap_pri].anchor, set.snap[set.snap_pri].head);
+ const f = pane.file orelse return 0;
+ const r = pane.body.primaryRange(f.content, 0);
+ return @min(r.anchor, r.head);
+}
+
+/// Every place on the rows shown, tinted over the text; the current one in
+/// the search colour itself, the rest halfway to the page.
+pub fn paint(set: *Places, p: *Pardes, s: *Surface, pane: *Pane, r: pardes.Rect, body_h: u16) void {
+ if (!set.shows(pane)) return;
+ const f = &pane.file.?;
+ const th = p.theme();
+ const strong = p.chromeTheme().search_bg;
+ const quiet = colors.mix(th.bg orelse th.tag_bg, strong);
+ const hits = set.hits.items;
+ if (hits.len == 0) return;
+ const nlines = File.nlines(p.gpa, f);
+ var last_line: i32 = -1;
+ var vr: i32 = 0;
+ while (vr < body_h) : (vr += 1) {
+ const line = pane.wrapAt(vr).line;
+ if (line == last_line or line < 0) continue;
+ if (line >= nlines) break;
+ last_line = line;
+ const ls = File.lineStart(p.gpa, f, @intCast(line));
+ const next = File.lineStart(p.gpa, f, @intCast(line + 1));
+ const le = if (next > ls and next <= f.content.len and f.content[next - 1] == '\n') next - 1 else next;
+ // the first hit ending past the line's start
+ var lo: usize = 0;
+ var hi = hits.len;
+ while (lo < hi) {
+ const mid = lo + (hi - lo) / 2;
+ if (hits[mid].end <= ls) lo = mid + 1 else hi = mid;
+ }
+ var i = lo;
+ while (i < hits.len and hits[i].start <= le) : (i += 1) {
+ const a = @max(hits[i].start, ls) - ls;
+ const b = @min(hits[i].end, le) - ls;
+ if (b <= a) continue;
+ const current = set.current != null and set.current.? == i;
+ File.paintWordSelection(p, s, pane, r, line, @intCast(a), @intCast(b), if (current) strong else quiet);
+ }
+ }
+}
+
+/// The rail's ticks, in 1/`tick_scale`s of the file: one per such step
+/// that holds a place, made again only when the places or the current one
+/// move.
+fn buildTicks(set: *Places, p: *Pardes, f: *File.State) void {
+ if (set.ticks_gen == set.gen) return;
+ set.ticks_gen = set.gen;
+ set.ticks.clearRetainingCapacity();
+ const index = File.lineIndex(p.gpa, f) catch return;
+ const total = @max(1, index.len);
+ var line: usize = 0;
+ for (set.hits.items) |h| {
+ while (line + 1 < index.len and index[line + 1] <= h.start) line += 1;
+ const b: u16 = @intCast(@min(tick_scale - 1, line * tick_scale / total));
+ if (set.ticks.items.len == 0 or set.ticks.items[set.ticks.items.len - 1] != b)
+ set.ticks.append(p.gpa, b) catch return;
+ }
+}
+
+/// The step of the rail holding place `i`.
+fn tickOf(set: *Places, p: *Pardes, f: *File.State, i: usize) ?u16 {
+ const index = File.lineIndex(p.gpa, f) catch return null;
+ const at = set.hits.items[i].start;
+ var lo: usize = 0;
+ var hi = index.len;
+ while (lo < hi) {
+ const mid = lo + (hi - lo) / 2;
+ if (index[mid] <= at) lo = mid + 1 else hi = mid;
+ }
+ const line = lo -| 1;
+ return @intCast(@min(tick_scale - 1, line * tick_scale / @max(1, index.len)));
+}
+
+/// These places' ticks onto the frame's, for rail `owner` (draw.place):
+/// the cell shells paint them on the rail's track, the pixel ones at their
+/// place along it.
+pub fn addTicks(set: *Places, p: *Pardes, pane: *Pane, s: *Surface, owner: u8) void {
+ if (!set.shows(pane)) return;
+ const f = &pane.file.?;
+ set.buildTicks(p, f);
+ const cur = if (set.current) |c| set.tickOf(p, f, c) else null;
+ for (set.ticks.items) |b| {
+ if (s.nrail_ticks == s.rail_ticks.len) return;
+ s.rail_ticks[s.nrail_ticks] = .{ .owner = owner, .at = b, .current = cur != null and cur.? == b };
+ s.nrail_ticks += 1;
+ }
+}
+
+/// The place a click on row `row` of a rail `rows` tall goes to: the first
+/// of the tick drawn in that cell, as a cell shell draws it; null where
+/// there is none, and the click scrolls as on any rail.
+pub fn tickHit(set: *Places, p: *Pardes, pane: *Pane, row: u16, rows: u16) ?usize {
+ if (!set.shows(pane) or rows == 0) return null;
+ const f = &pane.file.?;
+ set.buildTicks(p, f);
+ const total = File.nlines(p.gpa, f);
+ for (set.ticks.items) |b| {
+ if (@as(usize, b) * rows / tick_scale != row) continue;
+ const first_line = (@as(usize, b) * total + tick_scale - 1) / tick_scale;
+ const i = firstFrom(set.hits.items, File.lineStart(p.gpa, f, first_line));
+ if (i < set.hits.items.len) return i;
+ }
+ return null;
+}
+
+/// At the end of every step: more of the places found (a frame's worth on
+/// a tick, the view's on anything else), and the current one taken from
+/// the selection when something else put it on one (a Look, a click).
+pub fn settle(set: *Places, p: *Pardes, pane: *Pane, tick: bool) void {
+ if (!set.started) return;
+ set.fill(p, pane, if (tick) frame_bytes else 0, frame_steps);
+ if (!set.shows(pane)) return;
+ const f = &pane.file.?;
+ const r = pane.body.primaryRange(f.content, 0);
+ const i = firstFrom(set.hits.items, @min(r.anchor, r.head));
+ if (i < set.hits.items.len and set.hits.items[i].start == @min(r.anchor, r.head) and
+ set.hits.items[i].end == @max(r.anchor, r.head) and (set.current == null or set.current.? != i))
+ {
+ set.current = i;
+ set.gen +%= 1;
+ }
+}
+
+fn typeKeys(p: *Pardes, keys: []const u8) void {
+ for (keys) |c| p.update(.{ .key = .{ .cp = c, .text = &[_]u8{c} } });
+}
+
+test "places: * finds them all, n and N step them round the end silently, an edit shifts them" {
+ const p = try Pardes.init(std.testing.allocator, .{ .tty_only = true, .cols = 80, .rows = 24 });
+ defer p.deinit();
+ const pane = try p.setTestFile("alpha beta\ngamma alpha\nALPHA delta\nalphabet\n");
+ // `e` selects `alpha`; `*` makes the places from it.
+ typeKeys(p, "e*");
+ const set = &pane.places;
+ try std.testing.expect(set.started and set.shows(pane));
+ try std.testing.expectEqual(Provenance.search, set.provenance);
+ // smart case: `alpha` has no capital, so ALPHA counts; `*` keeps to
+ // whole words, so `alphabet` does not
+ try std.testing.expectEqual(@as(usize, 3), set.hits.items.len);
+ try std.testing.expectEqual(@as(?usize, 0), set.current);
+ typeKeys(p, "n");
+ try std.testing.expectEqual(@as(?usize, 1), set.current);
+ typeKeys(p, "n");
+ try std.testing.expectEqual(@as(?usize, 2), set.current);
+ const logged = p.messages.len;
+ typeKeys(p, "n");
+ try std.testing.expectEqual(@as(?usize, 0), set.current);
+ try std.testing.expect(set.wrapped);
+ // round the end without a word anywhere
+ try std.testing.expectEqual(logged, p.messages.len);
+ typeKeys(p, "N");
+ try std.testing.expectEqual(@as(?usize, 2), set.current);
+
+ // An edit on one line: the others shifted, that line found again.
+ const f = &pane.file.?;
+ const before = set.hits.items[2];
+ const new = try std.testing.allocator.dupe(u8, "alpha beta\ngamma alpha alpha\nALPHA delta\nalphabet\n");
+ File.setContentSpan(p, f, new, null);
+ set.fill(p, pane, 0, frame_steps);
+ try std.testing.expect(set.shows(pane));
+ try std.testing.expectEqual(@as(usize, 4), set.hits.items.len);
+ try std.testing.expectEqual(before.start + 6, set.hits.items[3].start);
+ try std.testing.expectEqual(@as(?usize, 3), set.current);
+ // Another `/` register (an `s`, a search elsewhere): n is helix's again.
+ p.registers.put(p.gpa, '/', "gamma", 0, 1, true);
+ try std.testing.expect(!set.answersN(p, pane));
+}
+
+test "places: a big file costs a keystroke its view, the ticks find the rest, an edit costs a line" {
+ const p = try Pardes.init(std.testing.allocator, .{ .tty_only = true, .cols = 120, .rows = 40 });
+ defer p.deinit();
+ var text: std.ArrayList(u8) = .empty;
+ defer text.deinit(std.testing.allocator);
+ for (0..40_000) |i| try text.print(std.testing.allocator, "line {d}: some words and a needle {d} here\n", .{ i, i % 7 });
+ const pane = try p.setTestFile(text.items);
+ const set = &pane.places;
+ // The line index is the file's, made once whatever asks for it first.
+ _ = try File.lineIndex(p.gpa, &pane.file.?);
+ const t0 = nowNs();
+ set.search(p, pane, .typed, 0, "needle 3", false, 0, true);
+ const first_ns = nowNs() - t0;
+ try std.testing.expect(set.hits.items.len > 0);
+ var ticks: usize = 0;
+ while (set.busy(pane) and ticks < 10_000) : (ticks += 1) set.settle(p, pane, true);
+ try std.testing.expect(set.complete());
+ const all = set.hits.items.len;
+ try std.testing.expect(all > 5000);
+ // An edit: one splice, shifted, no rescan of the file.
+ const f = &pane.file.?;
+ const at = 10;
+ const new = try std.testing.allocator.alloc(u8, f.content.len + 1);
+ @memcpy(new[0..at], f.content[0..at]);
+ new[at] = 'x';
+ @memcpy(new[at + 1 ..], f.content[at..]);
+ const t1 = nowNs();
+ File.setContentSpan(p, f, new, null);
+ const t2 = nowNs();
+ set.settle(p, pane, false);
+ const edit_ns = nowNs() - t2;
+ const text_ns = t2 - t1;
+ try std.testing.expect(set.complete() and set.shows(pane));
+ try std.testing.expectEqual(all, set.hits.items.len);
+ // PLACES_TIMES=1 says the numbers (on stderr, which fails the run).
+ if (std.c.getenv("PLACES_TIMES") != null)
+ std.debug.print("places: first key {d} us, {d} ticks, an edit {d} us (the text's own splice {d} us)\n", .{ first_ns / 1000, ticks, edit_ns / 1000, text_ns / 1000 });
+}