From 18d89dcedaed1f8437799621675e88ca47d7cdc1 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Sat, 24 Oct 2026 10:29:10 -0300 Subject: 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 --- src/Places.zig | 849 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 849 insertions(+) create mode 100644 src/Places.zig (limited to 'src/Places.zig') 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 }); +} -- cgit v1.3