summaryrefslogtreecommitdiff
path: root/src/Places.zig
blob: 6aab0684ff62a91a5a0eaac88d76f99eb1e80b40 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
//! 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.
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;

/// What the replay digest leaves out (src/walk.zig): the rail's ticks,
/// made again from the places when they are drawn.
pub const replica = .{ .derived = .{ "ticks", "ticks_gen", "re" } };

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.
stuck_at: ?usize = null,
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,
/// 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.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 {
    return std.sort.partitionPoint(Hit, hits, at, struct {
        fn before(byte: usize, h: Hit) bool {
            return h.start < byte;
        }
    }.before);
}

/// The line (0-based) that holds byte `at`, by a file's line index.
pub fn lineOf(index: []const usize, at: usize) usize {
    return std.sort.partitionPoint(usize, index, at, struct {
        fn before(byte: usize, start: usize) bool {
            return start <= byte;
        }
    }.before) -| 1;
}

/// 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;
    set.derive(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;
    set.derive(gpa);
    if (set.re == null) {
        // It does not compile: the characters it is.
        set.literal = true;
        set.derive(gpa);
        if (set.re == null) 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);
}

/// `re` made from the pattern: derived (Places.replica), so neither a dump
/// nor a rollback copy holds it, and a set loaded with a pattern and none
/// was a list's to `fill` (a client that joined found no places an edit
/// made, 2026-10-30). A list's places have no pattern.
fn derive(set: *Places, gpa: std.mem.Allocator) void {
    if (set.re != null or set.pattern.len == 0) return;
    var arena: std.heap.ArenaAllocator = .init(gpa);
    defer arena.deinit();
    const a = arena.allocator();
    const folded = if (set.fold) std.ascii.allocLowerString(a, set.pattern) catch return else set.pattern;
    if (!set.literal) {
        set.re = normal.SearchRegex.compile(gpa, folded) catch null;
        return;
    }
    var escaped: std.ArrayList(u8) = .empty;
    normal.appendSearchLiteral(&escaped, a, folded) catch return;
    set.re = normal.SearchRegex.compile(gpa, escaped.items) catch null;
}

/// 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;
    // What is not lowered yet is in the digest and a dump as well: zeros,
    // the same in every process, not whatever its heap held (a replica's
    // diverged). A pass over the text, as the edit that made it was.
    // ponytail: 0.4 ms for 10 MB, 10 ms for 100 MB in one frame (ReleaseFast,
    // page faults and all; lowering it is four times that, over frames). A
    // digest and a dump of the lowered pieces alone if a huge text's first
    // search ever shows.
    @memset(set.hay, 0);
    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.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 = pardes.FrameStats.nowNs();
    if (!set.started) return;
    set.derive(p.gpa);
    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(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) {
                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.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).
        // The clock's verdict is the session's (src/tape.zig): a replica
        // finds as many places a frame as this did.
        if (started_ns != 0 and bytes != std.math.maxInt(usize) and pardes.tape.over(started_ns, frame_ns)) break;
    }
    if (set.hits.items.len != found_before) {
        set.gen +%= 1;
        set.hits_gen +%= 1;
    }
    set.settleSeek(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, 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;
    } else if (set.complete()) {
        set.current = if (hits.len > 0) 0 else null;
    } 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(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;
    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;
        } else {
            const from = @min(old.anchor, old.head);
            i = firstFrom(hits, from);
            while (i > 0 and hits[i - 1].end > from) i -= 1;
            i = if (i == 0) hits.len - 1 else i - 1;
        }
        set.goTo(pane, i, add);
    }
}

/// 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 {
    const v = p.view();
    if (!set.shows(pane) and !set.started) return false;
    if (set.provenance != .search) return v.register == 0;
    const name = if (v.register != 0) v.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;
    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, pane: *Pane) void {
    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 i = std.sort.partitionPoint(Hit, hits, ls, struct {
            fn before(line_start: usize, h: Hit) bool {
                return h.end <= line_start;
            }
        }.before);
        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 line = lineOf(index, set.hits.items[i].start);
    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);
    // 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.
    try 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.?);
    set.search(p, pane, .typed, 0, "needle 3", false, 0, true);
    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..]);
    File.setContentSpan(p, f, new, null);
    set.settle(p, pane, false);
    try std.testing.expect(set.complete() and set.shows(pane));
    try std.testing.expectEqual(all, set.hits.items.len);
}

test "a lowered copy's pieces not searched yet are the same in every process: a digest and a dump take them" {
    // Two sessions searching one text, each heap handing out other bytes in
    // what is not written yet (rollback.Epoch.fill): their places agree.
    const rollback = @import("rollback.zig");
    var text: std.ArrayList(u8) = .empty;
    defer text.deinit(std.testing.allocator);
    for (0..2000) |i| try text.print(std.testing.allocator, "line {d} of a text in four pieces\n", .{i});
    var digests: [2]u64 = undefined;
    for (&digests, [_]u8{ 0x11, 0x5a }) |*d, b| {
        var e: rollback.Epoch = .{ .child = std.testing.allocator };
        defer e.deinit();
        rollback.Epoch.fill = b;
        defer rollback.Epoch.fill = null;
        const p = try Pardes.init(e.allocator(), .{ .tty_only = true, .cols = 80, .rows = 24 });
        defer p.deinit();
        const pane = try p.setTestFile(text.items);
        // The view's piece found now, the rest a frame at a time after.
        pane.places.search(p, pane, .typed, 0, "piece", false, null, false);
        try std.testing.expect(!pane.places.complete() and pane.places.fold);
        d.* = pardes.walk.digest(Places, &pane.places);
    }
    try std.testing.expectEqual(digests[0], digests[1]);
}

test "a session's places loaded from its dump find what an edit makes as the session's do" {
    // A client's core is the session's dump; `re` is derived, in no dump:
    // made again from the pattern, else the loaded set took itself for a
    // list's and found nothing an edit made (a soak's rejoin loop).
    const gpa = std.testing.allocator;
    const a = try Pardes.init(gpa, .{ .tty_only = true, .cols = 80, .rows = 24 });
    defer a.deinit();
    const pane = try a.setTestFile("alpha beta\ngamma alpha\n");
    typeKeys(a, "e*");
    try std.testing.expectEqual(@as(usize, 2), pane.places.hits.items.len);
    const bytes = try pardes.dump.dumpBytes(a);
    defer gpa.free(bytes);
    const b = try pardes.dump.load(gpa, a.opts, bytes, null);
    defer b.deinit();
    try std.testing.expectEqual(pardes.walk.digest(Pardes, a), pardes.walk.digest(Pardes, b));
    for ([_]*Pardes{ a, b }) |p| {
        const pn = p.panes[p.view().active].?;
        const new = try gpa.dupe(u8, "alpha beta\ngamma alpha alpha\n");
        File.setContentSpan(p, &pn.file.?, new, null);
        pn.places.fill(p, pn, 0, frame_steps);
        try std.testing.expectEqual(@as(usize, 3), pn.places.hits.items.len);
    }
    try std.testing.expectEqual(pardes.walk.digest(Pardes, a), pardes.walk.digest(Pardes, b));
}