summaryrefslogtreecommitdiff
path: root/src/Places.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-10-30 17:35:06 -0300
committerGabriel Schneider <[email protected]>2026-10-30 17:35:06 -0300
commit6d8da8721141284cf33bb901168b26135893eb86 (patch)
tree791d63401d4e85fbca1d597a8ce0326e70efd545 /src/Places.zig
parentefd43a3a2cf03bb741366331158b368abf9ac583 (diff)
parentbf6810a8f9d6cc82050e7d9c0cfb06358301b574 (diff)
downloadpardes-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/Places.zig')
-rw-r--r--src/Places.zig876
1 files changed, 876 insertions, 0 deletions
diff --git a/src/Places.zig b/src/Places.zig
new file mode 100644
index 00000000..cff7c22e
--- /dev/null
+++ b/src/Places.zig
@@ -0,0 +1,876 @@
+//! 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;
+ // The keystroke's share: the view; the rest a frame's slice a tick.
+ set.fill(p, pane, 0, 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: *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 start when it was
+/// remembered, else now; a place there counts (helix's `/` from the
+/// cursor).
+pub fn origin(set: *const Places, pane: *Pane) usize {
+ if (set.snap.len > 0) return @min(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 });
+}
+
+test "zz stress analysis cost" {
+ const path = "/home/goblin/00-projects/0x4200.cafe/pardes-s-converge/.scratch/stress/src/layout.zig";
+ if (std.c.getenv("PLACES_TIMES") == null) return error.SkipZigTest;
+ const io = std.testing.io;
+ const bytes = try std.Io.Dir.cwd().readFileAlloc(io, path, std.testing.allocator, .limited(4 << 20));
+ defer std.testing.allocator.free(bytes);
+ const syntax = @import("syntax.zig");
+ syntax.start(std.testing.allocator);
+ defer syntax.stop();
+ const tp = nowNs();
+ const tree = syntax.parseTree(path, bytes);
+ const tq = nowNs();
+ if (tree) |t| syntax.freeTree(t);
+ std.debug.print("parse alone {d} us\n", .{(tq - tp) / 1000});
+ const t0 = nowNs();
+ const d = try syntax.contextDeclarations(std.testing.allocator, path, bytes);
+ const t1 = nowNs();
+ std.testing.allocator.free(d);
+ const a = try syntax.analyzeSource(std.testing.allocator, path, bytes, true, true);
+ const t2 = nowNs();
+ std.testing.allocator.free(a.declarations);
+ std.testing.allocator.free(a.colors);
+ std.debug.print("decls {d} us ({d}), analysis with colours {d} us\n", .{ (t1 - t0) / 1000, d.len, (t2 - t1) / 1000 });
+}