aboutsummaryrefslogtreecommitdiff
path: root/vendor/libghostty-vt/src/terminal/search
diff options
context:
space:
mode:
authorCan Celik <ogulcancelik@gmail.com>2026-04-04 19:22:04 +0300
committerCan Celik <ogulcancelik@gmail.com>2026-04-05 01:23:06 +0300
commit41dd733ca7123c9ac4bfc6c781697a660e95b052 (patch)
tree3fc91815ca139ef2e0b281bba0abda4ef15175f4 /vendor/libghostty-vt/src/terminal/search
parent55c138263e190a1e79d4b997bfb9397306c0ec1f (diff)
feat: finish ghostty pane backend integration
Diffstat (limited to 'vendor/libghostty-vt/src/terminal/search')
-rw-r--r--vendor/libghostty-vt/src/terminal/search/Thread.zig905
-rw-r--r--vendor/libghostty-vt/src/terminal/search/active.zig175
-rw-r--r--vendor/libghostty-vt/src/terminal/search/pagelist.zig441
-rw-r--r--vendor/libghostty-vt/src/terminal/search/screen.zig1552
-rw-r--r--vendor/libghostty-vt/src/terminal/search/sliding_window.zig1676
-rw-r--r--vendor/libghostty-vt/src/terminal/search/viewport.zig384
6 files changed, 5133 insertions, 0 deletions
diff --git a/vendor/libghostty-vt/src/terminal/search/Thread.zig b/vendor/libghostty-vt/src/terminal/search/Thread.zig
new file mode 100644
index 00000000..fa09af5f
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/search/Thread.zig
@@ -0,0 +1,905 @@
+//! Search thread that handles searching a terminal for a string match.
+//! This is expected to run on a dedicated thread to try to prevent too much
+//! overhead to other terminal read/write operations.
+//!
+//! The current architecture of search does acquire global locks for accessing
+//! terminal data, so there's still added contention, but we do our best to
+//! minimize this by trading off memory usage (copying data to minimize lock
+//! time).
+pub const Thread = @This();
+
+const std = @import("std");
+const builtin = @import("builtin");
+const testing = std.testing;
+const Allocator = std.mem.Allocator;
+const ArenaAllocator = std.heap.ArenaAllocator;
+const Mutex = std.Thread.Mutex;
+const xev = @import("../../global.zig").xev;
+const internal_os = @import("../../os/main.zig");
+const BlockingQueue = @import("../../datastruct/main.zig").BlockingQueue;
+const MessageData = @import("../../datastruct/main.zig").MessageData;
+const point = @import("../point.zig");
+const FlattenedHighlight = @import("../highlight.zig").Flattened;
+const UntrackedHighlight = @import("../highlight.zig").Untracked;
+const ScreenSet = @import("../ScreenSet.zig");
+const Selection = @import("../Selection.zig");
+const Terminal = @import("../Terminal.zig");
+
+const ScreenSearch = @import("screen.zig").ScreenSearch;
+const ViewportSearch = @import("viewport.zig").ViewportSearch;
+
+const log = std.log.scoped(.search_thread);
+
+// TODO: Some stuff that could be improved:
+// - pause the refresh timer when the terminal isn't focused
+// - we probably want to know our progress through the search
+// for viewport matches so we can show n/total UI.
+// - notifications should be coalesced to avoid spamming a massive
+// amount of events if the terminal is changing rapidly.
+
+/// The interval at which we refresh the terminal state to check if
+/// there are any changes that require us to re-search. This should be
+/// balanced to be fast enough to be responsive but not so fast that
+/// we hold the terminal lock too often.
+const REFRESH_INTERVAL = 24; // 40 FPS
+
+/// Allocator used for some state
+alloc: std.mem.Allocator,
+
+/// The mailbox that can be used to send this thread messages. Note
+/// this is a blocking queue so if it is full you will get errors (or block).
+mailbox: *Mailbox,
+
+/// The event loop for the search thread.
+loop: xev.Loop,
+
+/// This can be used to wake up the renderer and force a render safely from
+/// any thread.
+wakeup: xev.Async,
+wakeup_c: xev.Completion = .{},
+
+/// This can be used to stop the thread on the next loop iteration.
+stop: xev.Async,
+stop_c: xev.Completion = .{},
+
+/// The timer used for refreshing the terminal state to determine if
+/// we have a stale active area, viewport, screen change, etc. This is
+/// CPU intensive so we stop doing this under certain conditions.
+refresh: xev.Timer,
+refresh_c: xev.Completion = .{},
+refresh_active: bool = false,
+
+/// Search state. Starts as null and is populated when a search is
+/// started (a needle is given).
+search: ?Search = null,
+
+/// The options used to initialize this thread.
+opts: Options,
+
+/// Initialize the thread. This does not START the thread. This only sets
+/// up all the internal state necessary prior to starting the thread. It
+/// is up to the caller to start the thread with the threadMain entrypoint.
+pub fn init(alloc: Allocator, opts: Options) !Thread {
+ // The mailbox for messaging this thread
+ var mailbox = try Mailbox.create(alloc);
+ errdefer mailbox.destroy(alloc);
+
+ // Create our event loop.
+ var loop = try xev.Loop.init(.{});
+ errdefer loop.deinit();
+
+ // This async handle is used to "wake up" the renderer and force a render.
+ var wakeup_h = try xev.Async.init();
+ errdefer wakeup_h.deinit();
+
+ // This async handle is used to stop the loop and force the thread to end.
+ var stop_h = try xev.Async.init();
+ errdefer stop_h.deinit();
+
+ // Refresh timer, see comments.
+ var refresh_h = try xev.Timer.init();
+ errdefer refresh_h.deinit();
+
+ return .{
+ .alloc = alloc,
+ .mailbox = mailbox,
+ .loop = loop,
+ .wakeup = wakeup_h,
+ .stop = stop_h,
+ .refresh = refresh_h,
+ .opts = opts,
+ };
+}
+
+/// Clean up the thread. This is only safe to call once the thread
+/// completes executing; the caller must join prior to this.
+pub fn deinit(self: *Thread) void {
+ self.refresh.deinit();
+ self.wakeup.deinit();
+ self.stop.deinit();
+ self.loop.deinit();
+ // Nothing can possibly access the mailbox anymore, destroy it.
+ self.mailbox.destroy(self.alloc);
+
+ if (self.search) |*s| s.deinit();
+}
+
+/// The main entrypoint for the thread.
+pub fn threadMain(self: *Thread) void {
+ // Call child function so we can use errors...
+ self.threadMain_() catch |err| {
+ // In the future, we should expose this on the thread struct.
+ log.warn("search thread err={}", .{err});
+ };
+}
+
+fn threadMain_(self: *Thread) !void {
+ defer log.debug("search thread exited", .{});
+
+ // Right now, on Darwin, `std.Thread.setName` can only name the current
+ // thread, and we have no way to get the current thread from within it,
+ // so instead we use this code to name the thread instead.
+ if (comptime builtin.os.tag.isDarwin()) {
+ internal_os.macos.pthread_setname_np(&"search".*);
+
+ // We can run with lower priority than other threads.
+ const class: internal_os.macos.QosClass = .utility;
+ if (internal_os.macos.setQosClass(class)) {
+ log.debug("thread QoS class set class={}", .{class});
+ } else |err| {
+ log.warn("error setting QoS class err={}", .{err});
+ }
+ }
+
+ // Start the async handlers
+ self.wakeup.wait(&self.loop, &self.wakeup_c, Thread, self, wakeupCallback);
+ self.stop.wait(&self.loop, &self.stop_c, Thread, self, stopCallback);
+
+ // Send an initial wakeup so we drain our mailbox immediately.
+ try self.wakeup.notify();
+
+ // Start the refresh timer
+ self.startRefreshTimer();
+
+ // Run
+ log.debug("starting search thread", .{});
+ defer {
+ log.debug("starting search thread shutdown", .{});
+
+ // Send the quit message
+ if (self.opts.event_cb) |cb| {
+ cb(.quit, self.opts.event_userdata);
+ }
+ }
+
+ // Unlike some of our other threads, we interleave search work
+ // with our xev loop so that we can try to make forward search progress
+ // while also listening for messages.
+ while (true) {
+ // If our loop is canceled then we drain our messages and quit.
+ if (self.loop.stopped()) {
+ while (self.mailbox.pop()) |message| {
+ log.debug("mailbox message ignored during shutdown={}", .{message});
+ }
+
+ return;
+ }
+
+ const s: *Search = if (self.search) |*s| s else {
+ // If we're not actively searching, we can block the loop
+ // until it does some work.
+ try self.loop.run(.once);
+ continue;
+ };
+
+ // If we have an active search, we always send any pending
+ // notifications. Even if the search is complete, there may be
+ // notifications to send.
+ if (self.opts.event_cb) |cb| {
+ s.notify(
+ self.alloc,
+ cb,
+ self.opts.event_userdata,
+ );
+ }
+
+ if (s.isComplete()) {
+ // If our search is complete, there's no more work to do, we
+ // can block until we have an xev action.
+ try self.loop.run(.once);
+ continue;
+ }
+
+ // Tick the search. This will trigger any event callbacks, lock
+ // for data loading, etc.
+ switch (s.tick()) {
+ // We're complete now when we were not before. Notify!
+ .complete => {},
+
+ // Forward progress was made.
+ .progress => {},
+
+ // All searches are blocked. Let's grab the lock and feed data.
+ .blocked => {
+ self.opts.mutex.lock();
+ defer self.opts.mutex.unlock();
+ s.feed(self.alloc, self.opts.terminal);
+ },
+ }
+
+ // We have an active search, so we only want to process messages
+ // we have but otherwise return immediately so we can continue the
+ // search. If the above completed the search, we still want to
+ // go around the loop as quickly as possible to send notifications,
+ // and then we'll block on the loop next time.
+ try self.loop.run(.no_wait);
+ }
+}
+
+/// Drain the mailbox.
+fn drainMailbox(self: *Thread) !void {
+ while (self.mailbox.pop()) |message| {
+ log.debug("mailbox message={}", .{message});
+ switch (message) {
+ .change_needle => |v| {
+ defer v.deinit();
+ try self.changeNeedle(v.slice());
+ },
+ .select => |v| try self.select(v),
+ }
+ }
+}
+
+fn select(self: *Thread, sel: ScreenSearch.Select) !void {
+ const s = if (self.search) |*s| s else return;
+ const screen_search = s.screens.getPtr(s.last_screen.key) orelse return;
+
+ self.opts.mutex.lock();
+ defer self.opts.mutex.unlock();
+
+ // Make the selection. Ignore the result because we don't
+ // care if the selection didn't change.
+ _ = try screen_search.select(sel);
+
+ // Grab our match if we have one. If we don't have a selection
+ // then we do nothing.
+ const flattened = screen_search.selectedMatch() orelse return;
+
+ // No matter what we reset our selected match cache. This will
+ // trigger a callback which will trigger the renderer to wake up
+ // so it can be notified the screen scrolled.
+ s.last_screen.selected = null;
+
+ // Grab the current screen and see if this match is visible within
+ // the viewport already. If it is, we do nothing.
+ const screen = self.opts.terminal.screens.get(
+ s.last_screen.key,
+ ) orelse return;
+
+ // Grab the viewport. Viewports and selections are usually small
+ // so this check isn't very expensive, despite appearing O(N^2),
+ // both Ns are usually equal to 1.
+ var it = screen.pages.pageIterator(
+ .right_down,
+ .{ .viewport = .{} },
+ null,
+ );
+ const hl_chunks = flattened.chunks.slice();
+ while (it.next()) |chunk| {
+ for (0..hl_chunks.len) |i| {
+ const hl_chunk = hl_chunks.get(i);
+ if (chunk.overlaps(.{
+ .node = hl_chunk.node,
+ .start = hl_chunk.start,
+ .end = hl_chunk.end,
+ })) return;
+ }
+ }
+
+ screen.scroll(.{ .pin = flattened.startPin() });
+}
+
+/// Change the search term to the given value.
+fn changeNeedle(self: *Thread, needle: []const u8) !void {
+ log.debug("changing search needle to '{s}'", .{needle});
+
+ // Stop the previous search
+ if (self.search) |*s| {
+ // If our search is unchanged, do nothing.
+ if (std.ascii.eqlIgnoreCase(s.viewport.needle(), needle)) return;
+
+ s.deinit();
+ self.search = null;
+
+ // When the search changes then we need to emit that it stopped.
+ if (self.opts.event_cb) |cb| {
+ cb(
+ .{ .total_matches = 0 },
+ self.opts.event_userdata,
+ );
+ cb(
+ .{ .selected_match = null },
+ self.opts.event_userdata,
+ );
+ cb(
+ .{ .viewport_matches = &.{} },
+ self.opts.event_userdata,
+ );
+ }
+ }
+
+ // No needle means stop the search.
+ if (needle.len == 0) return;
+
+ // Setup our search state.
+ self.search = try .init(self.alloc, needle);
+
+ // We need to grab the terminal lock and do an initial feed.
+ self.opts.mutex.lock();
+ defer self.opts.mutex.unlock();
+ self.search.?.feed(self.alloc, self.opts.terminal);
+}
+
+fn startRefreshTimer(self: *Thread) void {
+ // Set our active state so it knows we're running. We set this before
+ // even checking the active state in case we have a pending shutdown.
+ self.refresh_active = true;
+
+ // If our timer is already active, then we don't have to do anything.
+ if (self.refresh_c.state() == .active) return;
+
+ // Start the timer which loops
+ self.refresh.run(
+ &self.loop,
+ &self.refresh_c,
+ REFRESH_INTERVAL,
+ Thread,
+ self,
+ refreshCallback,
+ );
+}
+
+fn stopRefreshTimer(self: *Thread) void {
+ // This will stop the refresh on the next iteration.
+ self.refresh_active = false;
+}
+
+fn wakeupCallback(
+ self_: ?*Thread,
+ _: *xev.Loop,
+ _: *xev.Completion,
+ r: xev.Async.WaitError!void,
+) xev.CallbackAction {
+ _ = r catch |err| {
+ log.warn("error in wakeup err={}", .{err});
+ return .rearm;
+ };
+
+ const self = self_.?;
+
+ // When we wake up, we drain the mailbox. Mailbox producers should
+ // wake up our thread after publishing.
+ self.drainMailbox() catch |err|
+ log.warn("error draining mailbox err={}", .{err});
+
+ return .rearm;
+}
+
+fn stopCallback(
+ self_: ?*Thread,
+ _: *xev.Loop,
+ _: *xev.Completion,
+ r: xev.Async.WaitError!void,
+) xev.CallbackAction {
+ _ = r catch unreachable;
+ self_.?.loop.stop();
+ return .disarm;
+}
+
+fn refreshCallback(
+ self_: ?*Thread,
+ _: *xev.Loop,
+ _: *xev.Completion,
+ r: xev.Timer.RunError!void,
+) xev.CallbackAction {
+ _ = r catch unreachable;
+ const self: *Thread = self_ orelse {
+ // This shouldn't happen so we log it.
+ log.warn("refresh callback fired without data set", .{});
+ return .disarm;
+ };
+
+ // Run our feed if we have a search active.
+ if (self.search) |*s| {
+ self.opts.mutex.lock();
+ defer self.opts.mutex.unlock();
+ s.feed(self.alloc, self.opts.terminal);
+ }
+
+ // Only continue if we're still active
+ if (self.refresh_active) self.refresh.run(
+ &self.loop,
+ &self.refresh_c,
+ REFRESH_INTERVAL,
+ Thread,
+ self,
+ refreshCallback,
+ );
+
+ return .disarm;
+}
+
+pub const Options = struct {
+ /// Mutex that must be held while reading/writing the terminal.
+ mutex: *Mutex,
+
+ /// The terminal data to search.
+ terminal: *Terminal,
+
+ /// The callback for events from the search thread along with optional
+ /// userdata. This can be null if you don't want to receive events,
+ /// which could be useful for a one-time search (although, odd, you
+ /// should use our search structures directly then).
+ event_cb: ?EventCallback = null,
+ event_userdata: ?*anyopaque = null,
+};
+
+pub const EventCallback = *const fn (event: Event, userdata: ?*anyopaque) void;
+
+/// The type used for sending messages to the thread.
+pub const Mailbox = BlockingQueue(Message, 64);
+
+/// The messages that can be sent to the thread.
+pub const Message = union(enum) {
+ /// Represents a write request. Magic number comes from the max size
+ /// we want this union to be.
+ pub const WriteReq = MessageData(u8, 255);
+
+ /// Change the search term. If no prior search term is given this
+ /// will start a search. If an existing search term is given this will
+ /// stop the prior search and start a new one.
+ change_needle: WriteReq,
+
+ /// Select a search result.
+ select: ScreenSearch.Select,
+};
+
+/// Events that can be emitted from the search thread. The caller
+/// chooses to handle these as they see fit.
+pub const Event = union(enum) {
+ /// Search is quitting. The search thread is exiting.
+ quit,
+
+ /// Search is complete for the given needle on all screens.
+ complete,
+
+ /// Total matches on the current active screen have changed.
+ total_matches: usize,
+
+ /// Selected match changed.
+ selected_match: ?SelectedMatch,
+
+ /// Matches in the viewport have changed. The memory is owned by the
+ /// search thread and is only valid during the callback.
+ viewport_matches: []const FlattenedHighlight,
+
+ pub const SelectedMatch = struct {
+ idx: usize,
+ highlight: FlattenedHighlight,
+ };
+};
+
+/// Search state.
+const Search = struct {
+ /// Active viewport search for the active screen.
+ viewport: ViewportSearch,
+
+ /// The searchers for all the screens.
+ screens: std.EnumMap(ScreenSet.Key, ScreenSearch),
+
+ /// All state related to screen switches, collected so that when
+ /// we switch screens it makes everything related stale, too.
+ last_screen: ScreenState,
+
+ /// True if we sent the complete notification yet.
+ last_complete: bool,
+
+ /// The last viewport matches we found.
+ stale_viewport_matches: bool,
+
+ const ScreenState = struct {
+ /// Last active screen key
+ key: ScreenSet.Key,
+
+ /// Last notified total matches count
+ total: ?usize = null,
+
+ /// Last notified selected match index
+ selected: ?SelectedMatch = null,
+
+ const SelectedMatch = struct {
+ idx: usize,
+ highlight: UntrackedHighlight,
+ };
+ };
+
+ pub fn init(
+ alloc: Allocator,
+ needle: []const u8,
+ ) Allocator.Error!Search {
+ var vp: ViewportSearch = try .init(alloc, needle);
+ errdefer vp.deinit();
+
+ // We use dirty tracking for active area changes. Start with it
+ // dirty so the first change is re-searched.
+ vp.active_dirty = true;
+
+ return .{
+ .viewport = vp,
+ .screens = .init(.{}),
+ .last_screen = .{ .key = .primary },
+ .last_complete = false,
+ .stale_viewport_matches = true,
+ };
+ }
+
+ pub fn deinit(self: *Search) void {
+ self.viewport.deinit();
+ var it = self.screens.iterator();
+ while (it.next()) |entry| entry.value.deinit();
+ }
+
+ /// Returns true if all searches on all screens are complete.
+ pub fn isComplete(self: *Search) bool {
+ var it = self.screens.iterator();
+ while (it.next()) |entry| {
+ if (!entry.value.state.isComplete()) return false;
+ }
+
+ return true;
+ }
+
+ pub const Tick = enum {
+ /// All searches are complete.
+ complete,
+
+ /// Progress was made on at least one screen.
+ progress,
+
+ /// All incomplete searches are blocked on feed.
+ blocked,
+ };
+
+ /// Tick the search forward as much as possible without acquiring
+ /// the big lock. Returns the overall tick progress.
+ pub fn tick(self: *Search) Tick {
+ var result: Tick = .complete;
+ var it = self.screens.iterator();
+ while (it.next()) |entry| {
+ if (entry.value.tick()) {
+ result = .progress;
+ } else |err| switch (err) {
+ // Ignore... nothing we can do.
+ error.OutOfMemory => log.warn(
+ "error ticking screen search key={} err={}",
+ .{ entry.key, err },
+ ),
+
+ // Ignore, good for us. State remains whatever it is.
+ error.SearchComplete => {},
+
+ // Ignore, too, progressed
+ error.FeedRequired => switch (result) {
+ // If we think we're complete, we're not because we're
+ // blocked now (nothing made progress).
+ .complete => result = .blocked,
+
+ // If we made some progress, we remain in progress
+ // since blocked means no progress at all.
+ .progress => {},
+
+ // If we're blocked already then we remain blocked.
+ .blocked => {},
+ },
+ }
+ }
+
+ // log.debug("tick result={}", .{result});
+ return result;
+ }
+
+ /// Grab the mutex and update any state that requires it, such as
+ /// feeding additional data to the searches or updating the active screen.
+ pub fn feed(
+ self: *Search,
+ alloc: Allocator,
+ t: *Terminal,
+ ) void {
+ // Update our active screen
+ if (t.screens.active_key != self.last_screen.key) {
+ // The default values will force resets of a bunch of other
+ // state too to force recalculations and notifications.
+ self.last_screen = .{ .key = t.screens.active_key };
+ }
+
+ // Reconcile our screens with the terminal screens. Remove
+ // searchers for screens that no longer exist and add searchers
+ // for screens that do exist but we don't have yet.
+ {
+ // Remove screens we have that no longer exist or changed.
+ var it = self.screens.iterator();
+ while (it.next()) |entry| {
+ const remove: bool = remove: {
+ // If the screen doesn't exist at all, remove it.
+ const actual = t.screens.all.get(entry.key) orelse break :remove true;
+
+ // If the screen pointer changed, remove it, the screen
+ // was totally reinitialized.
+ break :remove actual != entry.value.screen;
+ };
+
+ if (remove) {
+ entry.value.deinit();
+ _ = self.screens.remove(entry.key);
+ }
+ }
+ }
+ {
+ // Add screens that exist but we don't have yet.
+ var it = t.screens.all.iterator();
+ while (it.next()) |entry| {
+ if (self.screens.contains(entry.key)) continue;
+ self.screens.put(entry.key, ScreenSearch.init(
+ alloc,
+ entry.value.*,
+ self.viewport.needle(),
+ ) catch |err| switch (err) {
+ error.OutOfMemory => {
+ // OOM is probably going to sink the entire ship but
+ // we can just ignore it and wait on the next
+ // reconciliation to try again.
+ log.warn(
+ "error initializing screen search for key={} err={}",
+ .{ entry.key, err },
+ );
+ continue;
+ },
+ });
+ }
+ }
+
+ // See the `search_viewport_dirty` flag on the terminal to know
+ // what exactly this is for. But, if this is set, we know the renderer
+ // found the viewport/active area dirty, so we should mark it as
+ // dirty in our viewport searcher so it forces a re-search.
+ if (t.flags.search_viewport_dirty) {
+ t.flags.search_viewport_dirty = false;
+
+ // Mark our viewport dirty so it researches the active
+ self.viewport.active_dirty = true;
+
+ // Reload our active area for our active screen
+ if (self.screens.getPtr(t.screens.active_key)) |screen_search| {
+ screen_search.reloadActive() catch |err| switch (err) {
+ error.OutOfMemory => log.warn(
+ "error reloading active area for screen key={} err={}",
+ .{ t.screens.active_key, err },
+ ),
+ };
+ }
+ }
+
+ // Check our viewport for changes.
+ if (self.viewport.update(&t.screens.active.pages)) |updated| {
+ if (updated) self.stale_viewport_matches = true;
+ } else |err| switch (err) {
+ error.OutOfMemory => log.warn(
+ "error updating viewport search err={}",
+ .{err},
+ ),
+ }
+
+ // Feed data
+ var it = self.screens.iterator();
+ while (it.next()) |entry| {
+ if (entry.value.state.needsFeed()) {
+ entry.value.feed() catch |err| switch (err) {
+ error.OutOfMemory => log.warn(
+ "error feeding screen search key={} err={}",
+ .{ entry.key, err },
+ ),
+ };
+ }
+ }
+ }
+
+ /// Notify about any changes to the search state.
+ ///
+ /// This doesn't require any locking as it only reads internal state.
+ pub fn notify(
+ self: *Search,
+ alloc: Allocator,
+ cb: EventCallback,
+ ud: ?*anyopaque,
+ ) void {
+ const screen_search = self.screens.get(self.last_screen.key) orelse return;
+
+ // Check our total match data
+ const total = screen_search.matchesLen();
+ if (total != self.last_screen.total) {
+ log.debug("notifying total matches={}", .{total});
+ self.last_screen.total = total;
+ cb(.{ .total_matches = total }, ud);
+ }
+
+ // Check our viewport matches. If they're stale, we do the
+ // viewport search now. We do this as part of notify and not
+ // tick because the viewport search is very fast and doesn't
+ // require ticked progress or feeds.
+ if (self.stale_viewport_matches) viewport: {
+ // We always make stale as false. Even if we fail below
+ // we require a re-feed to re-search the viewport. The feed
+ // process will make it stale again.
+ self.stale_viewport_matches = false;
+
+ var arena: ArenaAllocator = .init(alloc);
+ defer arena.deinit();
+ const arena_alloc = arena.allocator();
+ var results: std.ArrayList(FlattenedHighlight) = .empty;
+ while (self.viewport.next()) |hl| {
+ const hl_cloned = hl.clone(arena_alloc) catch continue;
+ results.append(arena_alloc, hl_cloned) catch |err| switch (err) {
+ error.OutOfMemory => {
+ log.warn(
+ "error collecting viewport matches err={}",
+ .{err},
+ );
+
+ // Reset the viewport so we force an update on the
+ // next feed.
+ self.viewport.reset();
+ break :viewport;
+ },
+ };
+ }
+
+ log.debug("notifying viewport matches len={}", .{results.items.len});
+ cb(.{ .viewport_matches = results.items }, ud);
+ }
+
+ // Check our last selected match data.
+ if (screen_search.selected) |m| match: {
+ const flattened = screen_search.selectedMatch() orelse break :match;
+ const untracked = flattened.untracked();
+ if (self.last_screen.selected) |prev| {
+ if (prev.idx == m.idx and prev.highlight.eql(untracked)) {
+ // Same selection, don't update it.
+ break :match;
+ }
+ }
+
+ // New selection, notify!
+ self.last_screen.selected = .{
+ .idx = m.idx,
+ .highlight = untracked,
+ };
+
+ log.debug("notifying selection updated idx={}", .{m.idx});
+ cb(
+ .{ .selected_match = .{
+ .idx = m.idx,
+ .highlight = flattened,
+ } },
+ ud,
+ );
+ } else if (self.last_screen.selected != null) {
+ log.debug("notifying selection cleared", .{});
+ self.last_screen.selected = null;
+ cb(
+ .{ .selected_match = null },
+ ud,
+ );
+ }
+
+ // Send our complete notification if we just completed.
+ if (!self.last_complete and self.isComplete()) {
+ log.debug("notifying search complete", .{});
+ self.last_complete = true;
+ cb(.complete, ud);
+ }
+ }
+};
+
+const TestUserData = struct {
+ const Self = @This();
+ reset: std.Thread.ResetEvent = .{},
+ total: usize = 0,
+ selected: ?Event.SelectedMatch = null,
+ viewport: []FlattenedHighlight = &.{},
+
+ fn deinit(self: *Self) void {
+ for (self.viewport) |*hl| hl.deinit(testing.allocator);
+ testing.allocator.free(self.viewport);
+ }
+
+ fn callback(event: Event, userdata: ?*anyopaque) void {
+ const ud: *Self = @ptrCast(@alignCast(userdata.?));
+ switch (event) {
+ .quit => {},
+ .complete => ud.reset.set(),
+ .total_matches => |v| ud.total = v,
+ .selected_match => |v| ud.selected = v,
+ .viewport_matches => |v| {
+ for (ud.viewport) |*hl| hl.deinit(testing.allocator);
+ testing.allocator.free(ud.viewport);
+
+ ud.viewport = testing.allocator.alloc(
+ FlattenedHighlight,
+ v.len,
+ ) catch unreachable;
+ for (ud.viewport, v) |*dst, src| {
+ dst.* = src.clone(testing.allocator) catch unreachable;
+ }
+ },
+ }
+ }
+};
+
+test {
+ const alloc = testing.allocator;
+ var mutex: std.Thread.Mutex = .{};
+ var t: Terminal = try .init(alloc, .{ .cols = 20, .rows = 2 });
+ defer t.deinit(alloc);
+
+ var stream = t.vtStream();
+ defer stream.deinit();
+ stream.nextSlice("Hello, world");
+
+ var ud: TestUserData = .{};
+ defer ud.deinit();
+ var thread: Thread = try .init(alloc, .{
+ .mutex = &mutex,
+ .terminal = &t,
+ .event_cb = &TestUserData.callback,
+ .event_userdata = &ud,
+ });
+ defer thread.deinit();
+
+ var os_thread = try std.Thread.spawn(
+ .{},
+ threadMain,
+ .{&thread},
+ );
+
+ // Start our search
+ _ = thread.mailbox.push(
+ .{ .change_needle = try .init(
+ alloc,
+ @as([]const u8, "world"),
+ ) },
+ .forever,
+ );
+ try thread.wakeup.notify();
+
+ // Wait for completion
+ try ud.reset.timedWait(100 * std.time.ns_per_ms);
+
+ // Stop the thread
+ try thread.stop.notify();
+ os_thread.join();
+
+ // 1 total matches
+ try testing.expectEqual(1, ud.total);
+ try testing.expectEqual(1, ud.viewport.len);
+ {
+ const sel = ud.viewport[0].untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 7,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 11,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+}
diff --git a/vendor/libghostty-vt/src/terminal/search/active.zig b/vendor/libghostty-vt/src/terminal/search/active.zig
new file mode 100644
index 00000000..692a10e1
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/search/active.zig
@@ -0,0 +1,175 @@
+const std = @import("std");
+const testing = std.testing;
+const Allocator = std.mem.Allocator;
+const point = @import("../point.zig");
+const size = @import("../size.zig");
+const FlattenedHighlight = @import("../highlight.zig").Flattened;
+const PageList = @import("../PageList.zig");
+const SlidingWindow = @import("sliding_window.zig").SlidingWindow;
+const Terminal = @import("../Terminal.zig");
+
+/// Searches for a substring within the active area of a PageList.
+///
+/// The distinction for "active area" is important because it is the
+/// only part of a PageList that is mutable. Therefore, its the only part
+/// of the terminal that needs to be repeatedly searched as the contents
+/// change.
+///
+/// This struct specializes in searching only within that active area,
+/// and handling the active area moving as new lines are added to the bottom.
+pub const ActiveSearch = struct {
+ window: SlidingWindow,
+
+ pub fn init(
+ alloc: Allocator,
+ needle: []const u8,
+ ) Allocator.Error!ActiveSearch {
+ // We just do a forward search since the active area is usually
+ // pretty small so search results are instant anyways. This avoids
+ // a small amount of work to reverse things.
+ var window: SlidingWindow = try .init(alloc, .forward, needle);
+ errdefer window.deinit();
+ return .{ .window = window };
+ }
+
+ pub fn deinit(self: *ActiveSearch) void {
+ self.window.deinit();
+ }
+
+ /// Update the active area to reflect the current state of the PageList.
+ ///
+ /// This doesn't do the search, it only copies the necessary data
+ /// to perform the search later. This lets the caller hold the lock
+ /// on the PageList for a minimal amount of time.
+ ///
+ /// This returns the first page (in reverse order) covered by this
+ /// search. This allows the history search to overlap and search history.
+ /// There CAN BE duplicates, and this page CAN BE mutable, so the history
+ /// search results should prune anything that's in the active area.
+ ///
+ /// If the return value is null it means the active area covers the entire
+ /// PageList, currently.
+ pub fn update(
+ self: *ActiveSearch,
+ list: *const PageList,
+ ) Allocator.Error!?*PageList.List.Node {
+ // Clear our previous sliding window
+ self.window.clearAndRetainCapacity();
+
+ // First up, add enough pages to cover the active area.
+ var rem: usize = list.rows;
+ var node_ = list.pages.last;
+ var last_node: ?*PageList.List.Node = null;
+ while (node_) |node| : (node_ = node.prev) {
+ _ = try self.window.append(node);
+ last_node = node;
+
+ // If we reached our target amount, then this is the last
+ // page that contains the active area. We go to the previous
+ // page once more since its the first page of our required
+ // overlap.
+ if (rem <= node.data.size.rows) {
+ node_ = node.prev;
+ break;
+ }
+
+ rem -= node.data.size.rows;
+ }
+
+ // Next, add enough overlap to cover needle.len - 1 bytes (if it
+ // exists) so we can cover the overlap.
+ while (node_) |node| : (node_ = node.prev) {
+ // If the last row of this node isn't wrapped we can't overlap.
+ const row = node.data.getRow(node.data.size.rows - 1);
+ if (!row.wrap) break;
+
+ // We could be more accurate here and count bytes since the
+ // last wrap but its complicated and unlikely multiple pages
+ // wrap so this should be fine.
+ const added = try self.window.append(node);
+ if (added >= self.window.needle.len - 1) break;
+ }
+
+ // Return the last node we added to our window.
+ return last_node;
+ }
+
+ /// Find the next match for the needle in the active area. This returns
+ /// null when there are no more matches.
+ pub fn next(self: *ActiveSearch) ?FlattenedHighlight {
+ return self.window.next();
+ }
+};
+
+test "simple search" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ActiveSearch = try .init(alloc, "Fizz");
+ defer search.deinit();
+ _ = try search.update(&t.screens.active.pages);
+
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(search.next() == null);
+}
+
+test "clear screen and search" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ActiveSearch = try .init(alloc, "Fizz");
+ defer search.deinit();
+ _ = try search.update(&t.screens.active.pages);
+
+ s.nextSlice("\x1b[2J"); // Clear screen
+ s.nextSlice("\x1b[H"); // Move cursor home
+ s.nextSlice("Buzz\r\nFizz\r\nBuzz");
+ _ = try search.update(&t.screens.active.pages);
+
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(search.next() == null);
+}
diff --git a/vendor/libghostty-vt/src/terminal/search/pagelist.zig b/vendor/libghostty-vt/src/terminal/search/pagelist.zig
new file mode 100644
index 00000000..f76ad4e4
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/search/pagelist.zig
@@ -0,0 +1,441 @@
+const std = @import("std");
+const Allocator = std.mem.Allocator;
+const testing = std.testing;
+const terminal = @import("../main.zig");
+const point = terminal.point;
+const FlattenedHighlight = @import("../highlight.zig").Flattened;
+const Page = terminal.Page;
+const PageList = terminal.PageList;
+const Pin = PageList.Pin;
+const Selection = terminal.Selection;
+const Screen = terminal.Screen;
+const Terminal = @import("../Terminal.zig");
+const SlidingWindow = @import("sliding_window.zig").SlidingWindow;
+
+/// Searches for a term in a PageList structure.
+///
+/// This searches in reverse order starting from the given node.
+///
+/// This assumes that nodes do not change contents. For nodes that change
+/// contents, look at ActiveSearch, which is designed to re-search the active
+/// area since it assumed to change. When integrating ActiveSearch with
+/// PageListSearch, the caller should start the PageListSearch from the
+/// returned node from ActiveSearch.update().
+///
+/// Concurrent access to a PageList or nodes in a PageList are not allowed,
+/// so the caller should ensure that necessary locks are held. Each function
+/// documents whether it accesses the PageList or not. For example, you can
+/// safely call `next()` without holding a lock, but you must hold a lock
+/// while calling `feed()`.
+pub const PageListSearch = struct {
+ /// The list we're searching.
+ list: *PageList,
+
+ /// The sliding window of page contents and nodes to search.
+ window: SlidingWindow,
+
+ /// The tracked pin for our current position in the pagelist. This
+ /// will always point to the CURRENT node we're searching from so that
+ /// we can track if we move.
+ pin: *Pin,
+
+ /// Initialize the page list search. The needle is copied so it can
+ /// be freed immediately.
+ ///
+ /// Accesses the PageList/Node so the caller must ensure it is safe
+ /// to do so if there is any concurrent access.
+ pub fn init(
+ alloc: Allocator,
+ needle: []const u8,
+ list: *PageList,
+ start: *PageList.List.Node,
+ ) Allocator.Error!PageListSearch {
+ // We put a tracked pin into the node that we're starting from.
+ // By using a tracked pin, we can keep our pagelist references safe
+ // because if the pagelist prunes pages, the tracked pin will
+ // be moved somewhere safe.
+ const pin = try list.trackPin(.{
+ .node = start,
+ .y = start.data.size.rows - 1,
+ .x = start.data.size.cols - 1,
+ });
+ errdefer list.untrackPin(pin);
+
+ // Create our sliding window we'll use for searching.
+ var window: SlidingWindow = try .init(alloc, .reverse, needle);
+ errdefer window.deinit();
+
+ // We always feed our initial page data into the window, because
+ // we have the lock anyways and this lets our `pin` point to our
+ // current node and feed to work properly.
+ _ = try window.append(start);
+
+ return .{
+ .list = list,
+ .window = window,
+ .pin = pin,
+ };
+ }
+
+ /// Modifies the PageList (to untrack a pin) so the caller must ensure
+ /// that it is safe to do so.
+ pub fn deinit(self: *PageListSearch) void {
+ self.window.deinit();
+ self.list.untrackPin(self.pin);
+ }
+
+ /// Return the next match in the loaded page nodes. If this returns
+ /// null then the PageList search needs to be fed the next node(s).
+ /// Call, `feed` to do this.
+ ///
+ /// Beware that the selection returned may point to a node that
+ /// is freed if the caller does not hold necessary locks on the
+ /// PageList while searching. The pins should be validated prior to
+ /// final use.
+ ///
+ /// This does NOT access the PageList, so it can be called without
+ /// a lock held.
+ pub fn next(self: *PageListSearch) ?FlattenedHighlight {
+ return self.window.next();
+ }
+
+ /// Feed more data to the sliding window from the pagelist. This will
+ /// feed enough data to cover at least one match (needle length) if it
+ /// exists; this doesn't perform the search, it only feeds data.
+ ///
+ /// This accesses nodes in the PageList, so the caller must ensure
+ /// it is safe to do so (i.e. hold necessary locks).
+ ///
+ /// This returns false if there is no more data to feed. This essentially
+ /// means we've searched the entire pagelist.
+ pub fn feed(self: *PageListSearch) Allocator.Error!bool {
+ // If our pin becomes garbage it means wherever we were next
+ // was reused and we can't make sense of our progress anymore.
+ // It is effectively equivalent to reaching the end of the PageList.
+ if (self.pin.garbage) return false;
+
+ // Add at least enough data to find a single match.
+ var rem = self.window.needle.len;
+
+ // Start at our previous node and then continue adding until we
+ // get our desired amount of data.
+ var node_: ?*PageList.List.Node = self.pin.node.prev;
+ while (node_) |node| : (node_ = node.prev) {
+ rem -|= try self.window.append(node);
+
+ // Move our tracked pin to the new node.
+ self.pin.node = node;
+
+ if (rem == 0) break;
+ }
+
+ // True if we fed any data.
+ return rem < self.window.needle.len;
+ }
+};
+
+test "simple search" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: PageListSearch = try .init(
+ alloc,
+ "Fizz",
+ &t.screens.active.pages,
+ t.screens.active.pages.pages.last.?,
+ );
+ defer search.deinit();
+
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(search.next() == null);
+
+ // We should not be able to feed since we have one page
+ try testing.expect(!try search.feed());
+}
+
+test "feed multiple pages with matches" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ // Fill up first page
+ const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| s.nextSlice("\r\n");
+ s.nextSlice("Fizz");
+ try testing.expect(t.screens.active.pages.pages.first == t.screens.active.pages.pages.last);
+
+ // Create second page
+ s.nextSlice("\r\n");
+ try testing.expect(t.screens.active.pages.pages.first != t.screens.active.pages.pages.last);
+ s.nextSlice("Buzz\r\nFizz");
+
+ var search: PageListSearch = try .init(
+ alloc,
+ "Fizz",
+ &t.screens.active.pages,
+ t.screens.active.pages.pages.last.?,
+ );
+ defer search.deinit();
+
+ // First match on the last page
+ const sel1 = search.next();
+ try testing.expect(sel1 != null);
+ try testing.expect(search.next() == null);
+
+ // Feed should succeed and load the first page
+ try testing.expect(try search.feed());
+
+ // Now we should find the match on the first page
+ const sel2 = search.next();
+ try testing.expect(sel2 != null);
+ try testing.expect(search.next() == null);
+
+ // No more pages to feed
+ try testing.expect(!try search.feed());
+}
+
+test "feed multiple pages no matches" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ // Fill up first page
+ const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| s.nextSlice("\r\n");
+ s.nextSlice("Hello");
+
+ // Create second page
+ s.nextSlice("\r\n");
+ try testing.expect(t.screens.active.pages.pages.first != t.screens.active.pages.pages.last);
+ s.nextSlice("World");
+
+ var search: PageListSearch = try .init(
+ alloc,
+ "Nope",
+ &t.screens.active.pages,
+ t.screens.active.pages.pages.last.?,
+ );
+ defer search.deinit();
+
+ // No matches on last page
+ try testing.expect(search.next() == null);
+
+ // Feed first page
+ try testing.expect(try search.feed());
+
+ // Still no matches
+ try testing.expect(search.next() == null);
+
+ // No more pages
+ try testing.expect(!try search.feed());
+}
+
+test "feed iteratively through multiple matches" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 80, .rows = 24 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows;
+
+ // Fill first page with a match at the end
+ for (0..first_page_rows - 1) |_| s.nextSlice("\r\n");
+ s.nextSlice("Page1Test");
+ try testing.expect(t.screens.active.pages.pages.first == t.screens.active.pages.pages.last);
+
+ // Create second page with a match
+ s.nextSlice("\r\n");
+ try testing.expect(t.screens.active.pages.pages.first != t.screens.active.pages.pages.last);
+ s.nextSlice("Page2Test");
+
+ var search: PageListSearch = try .init(
+ alloc,
+ "Test",
+ &t.screens.active.pages,
+ t.screens.active.pages.pages.last.?,
+ );
+ defer search.deinit();
+
+ // Match on page 2
+ try testing.expect(search.next() != null);
+ try testing.expect(search.next() == null);
+
+ // Feed page 1
+ try testing.expect(try search.feed());
+ try testing.expect(search.next() != null);
+ try testing.expect(search.next() == null);
+
+ // No more pages
+ try testing.expect(!try search.feed());
+}
+
+test "feed with match spanning page boundary" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 80, .rows = 24 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows;
+
+ // Fill first page ending with "Te"
+ for (0..first_page_rows - 1) |_| s.nextSlice("\r\n");
+ for (0..t.screens.active.pages.cols - 2) |_| s.nextSlice("x");
+ s.nextSlice("Te");
+ try testing.expect(t.screens.active.pages.pages.first == t.screens.active.pages.pages.last);
+
+ // Second page starts with "st"
+ s.nextSlice("st");
+ try testing.expect(t.screens.active.pages.pages.first != t.screens.active.pages.pages.last);
+
+ var search: PageListSearch = try .init(
+ alloc,
+ "Test",
+ &t.screens.active.pages,
+ t.screens.active.pages.pages.last.?,
+ );
+ defer search.deinit();
+
+ // No complete match on last page alone (only has "st")
+ try testing.expect(search.next() == null);
+
+ // Feed first page - this should give us enough data to find "Test"
+ try testing.expect(try search.feed());
+
+ // Should find the spanning match
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expect(sel.start.node != sel.end.node);
+ {
+ const str = try t.screens.active.selectionString(
+ alloc,
+ .{ .sel = .init(sel.start, sel.end, false) },
+ );
+ defer alloc.free(str);
+ try testing.expectEqualStrings(str, "Test");
+ }
+
+ // No more matches
+ try testing.expect(search.next() == null);
+
+ // No more pages
+ try testing.expect(!try search.feed());
+}
+
+test "feed with match spanning page boundary with newline" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 80, .rows = 24 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows;
+
+ // Fill first page ending with "Te"
+ for (0..first_page_rows - 1) |_| s.nextSlice("\r\n");
+ for (0..t.screens.active.pages.cols - 2) |_| s.nextSlice("x");
+ s.nextSlice("Te");
+ try testing.expect(t.screens.active.pages.pages.first == t.screens.active.pages.pages.last);
+
+ // Second page starts with "st"
+ s.nextSlice("\r\n");
+ try testing.expect(t.screens.active.pages.pages.first != t.screens.active.pages.pages.last);
+ s.nextSlice("st");
+
+ var search: PageListSearch = try .init(
+ alloc,
+ "Test",
+ &t.screens.active.pages,
+ t.screens.active.pages.pages.last.?,
+ );
+ defer search.deinit();
+
+ // Should not find any matches since we broke with an explicit newline.
+ try testing.expect(search.next() == null);
+ try testing.expect(try search.feed());
+ try testing.expect(search.next() == null);
+ try testing.expect(!try search.feed());
+}
+
+test "feed with pruned page" {
+ const alloc = testing.allocator;
+
+ // Zero here forces minimum max size to effectively two pages.
+ var p: PageList = try .init(alloc, 80, 24, 0);
+ defer p.deinit();
+
+ // Grow to capacity
+ const page1_node = p.pages.last.?;
+ const page1 = page1_node.data;
+ for (0..page1.capacity.rows - page1.size.rows) |_| {
+ try testing.expect(try p.grow() == null);
+ }
+
+ // Grow and allocate one more page. Then fill that page up.
+ const page2_node = (try p.grow()).?;
+ const page2 = page2_node.data;
+ for (0..page2.capacity.rows - page2.size.rows) |_| {
+ try testing.expect(try p.grow() == null);
+ }
+
+ // Setup search and feed until we can't
+ var search: PageListSearch = try .init(
+ alloc,
+ "Test",
+ &p,
+ p.pages.last.?,
+ );
+ defer search.deinit();
+ try testing.expect(try search.feed());
+ try testing.expect(!try search.feed());
+
+ // Next should create a new page, but it should reuse our first
+ // page since we're at max size.
+ const new = (try p.grow()).?;
+ try testing.expect(p.pages.last.? == new);
+
+ // Our first should now be page2 and our last should be page1
+ try testing.expectEqual(page2_node, p.pages.first.?);
+ try testing.expectEqual(page1_node, p.pages.last.?);
+
+ // Feed should still do nothing
+ try testing.expect(!try search.feed());
+}
diff --git a/vendor/libghostty-vt/src/terminal/search/screen.zig b/vendor/libghostty-vt/src/terminal/search/screen.zig
new file mode 100644
index 00000000..3e7e316f
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/search/screen.zig
@@ -0,0 +1,1552 @@
+const std = @import("std");
+const assert = @import("../../quirks.zig").inlineAssert;
+const testing = std.testing;
+const tripwire = @import("../../tripwire.zig");
+const Allocator = std.mem.Allocator;
+const point = @import("../point.zig");
+const highlight = @import("../highlight.zig");
+const size = @import("../size.zig");
+const FlattenedHighlight = highlight.Flattened;
+const TrackedHighlight = highlight.Tracked;
+const PageList = @import("../PageList.zig");
+const Pin = PageList.Pin;
+const Screen = @import("../Screen.zig");
+const Terminal = @import("../Terminal.zig");
+const ActiveSearch = @import("active.zig").ActiveSearch;
+const PageListSearch = @import("pagelist.zig").PageListSearch;
+const SlidingWindow = @import("sliding_window.zig").SlidingWindow;
+
+const log = std.log.scoped(.search_screen);
+
+const reloadActive_tw = tripwire.module(enum {
+ history_append_new,
+ history_append_existing,
+}, ScreenSearch.reloadActive);
+
+/// Searches for a needle within a Screen, handling active area updates,
+/// pages being pruned from the screen (e.g. scrollback limits), and more.
+///
+/// Unlike our lower-level searchers (like ActiveSearch and PageListSearch),
+/// this will cache and store all search results so the caller can re-access
+/// them as needed. This structure does this because it is intended to help
+/// the caller handle the case where the Screen is changing while the user
+/// is searching.
+///
+/// An inactive screen can continue to be searched in the background, and when
+/// screen state changes, the renderer/caller can access the existing search
+/// results without needing to re-search everything. This prevents a particularly
+/// nasty UX where going to alt screen (e.g. neovim) and then back would
+/// restart the full scrollback search.
+pub const ScreenSearch = struct {
+ /// The screen being searched.
+ screen: *Screen,
+
+ /// The active area search state
+ active: ActiveSearch,
+
+ /// The history (scrollback) search state. May be null if there is
+ /// no history yet.
+ history: ?HistorySearch,
+
+ /// Current state of the search, a state machine.
+ state: State,
+
+ /// The currently selected match, if any. As the screen contents
+ /// change or get pruned, the screen search will do its best to keep
+ /// this accurate.
+ selected: ?SelectedMatch = null,
+
+ /// The results found so far. These are stored separately because history
+ /// is mostly immutable once found, while active area results may
+ /// change. This lets us easily reset the active area results for a
+ /// re-search scenario.
+ history_results: std.ArrayList(FlattenedHighlight),
+ active_results: std.ArrayList(FlattenedHighlight),
+
+ /// The dimensions of the screen. When this changes we need to
+ /// restart the whole search, currently.
+ rows: size.CellCountInt,
+ cols: size.CellCountInt,
+
+ pub const SelectedMatch = struct {
+ /// Index from the end of the match list (0 = most recent match)
+ idx: usize,
+
+ /// Tracked highlight so we can detect movement.
+ highlight: TrackedHighlight,
+
+ pub fn deinit(self: *SelectedMatch, screen: *Screen) void {
+ self.highlight.deinit(screen);
+ }
+ };
+
+ /// History search state.
+ const HistorySearch = struct {
+ /// The actual searcher state.
+ searcher: PageListSearch,
+
+ /// The pin for the first node that this searcher is searching from.
+ /// We use this when the active area changes to find the diff between
+ /// the top of the new active area and the previous start point
+ /// to determine if we need to search more history.
+ start_pin: *Pin,
+
+ pub fn deinit(self: *HistorySearch, screen: *Screen) void {
+ self.searcher.deinit();
+ screen.pages.untrackPin(self.start_pin);
+ }
+ };
+
+ /// Search state machine
+ const State = enum {
+ /// Currently searching the active area
+ active,
+
+ /// Currently searching the history area
+ history,
+
+ /// History search is waiting for more data to be fed before
+ /// it can progress.
+ history_feed,
+
+ /// Search is complete given the current terminal state.
+ complete,
+
+ pub fn isComplete(self: State) bool {
+ return switch (self) {
+ .complete => true,
+ else => false,
+ };
+ }
+
+ pub fn needsFeed(self: State) bool {
+ return switch (self) {
+ .history_feed => true,
+
+ // Not obvious but complete search states will prune
+ // stale history results on feed.
+ .complete => true,
+
+ else => false,
+ };
+ }
+ };
+
+ // Initialize a screen search for the given screen and needle.
+ pub fn init(
+ alloc: Allocator,
+ screen: *Screen,
+ needle_unowned: []const u8,
+ ) Allocator.Error!ScreenSearch {
+ var result: ScreenSearch = .{
+ .screen = screen,
+ .rows = screen.pages.rows,
+ .cols = screen.pages.cols,
+ .active = try .init(alloc, needle_unowned),
+ .history = null,
+ .state = .active,
+ .active_results = .empty,
+ .history_results = .empty,
+ };
+ errdefer result.deinit();
+
+ // Update our initial active area state
+ try result.reloadActive();
+
+ return result;
+ }
+
+ pub fn deinit(self: *ScreenSearch) void {
+ const alloc = self.allocator();
+ self.active.deinit();
+ if (self.history) |*h| h.deinit(self.screen);
+ if (self.selected) |*m| m.deinit(self.screen);
+ for (self.active_results.items) |*hl| hl.deinit(alloc);
+ self.active_results.deinit(alloc);
+ for (self.history_results.items) |*hl| hl.deinit(alloc);
+ self.history_results.deinit(alloc);
+ }
+
+ fn allocator(self: *ScreenSearch) Allocator {
+ return self.active.window.alloc;
+ }
+
+ /// The needle that this search is using.
+ pub fn needle(self: *const ScreenSearch) []const u8 {
+ assert(self.active.window.direction == .forward);
+ return self.active.window.needle;
+ }
+
+ /// Returns the total number of matches found so far.
+ pub fn matchesLen(self: *const ScreenSearch) usize {
+ return self.active_results.items.len + self.history_results.items.len;
+ }
+
+ /// Returns all matches as an owned slice (caller must free).
+ /// The matches are ordered from most recent to oldest (e.g. bottom
+ /// of the screen to top of the screen).
+ pub fn matches(
+ self: *ScreenSearch,
+ alloc: Allocator,
+ ) Allocator.Error![]FlattenedHighlight {
+ const active_results = self.active_results.items;
+ const history_results = self.history_results.items;
+ const results = try alloc.alloc(
+ FlattenedHighlight,
+ active_results.len + history_results.len,
+ );
+ errdefer alloc.free(results);
+
+ // Active does a forward search, so we add the active results then
+ // reverse them. There are usually not many active results so this
+ // is fast enough compared to adding them in reverse order.
+ assert(self.active.window.direction == .forward);
+ @memcpy(
+ results[0..active_results.len],
+ active_results,
+ );
+ std.mem.reverse(FlattenedHighlight, results[0..active_results.len]);
+
+ // History does a backward search, so we can just append them
+ // after.
+ @memcpy(
+ results[active_results.len..],
+ history_results,
+ );
+
+ return results;
+ }
+
+ /// Search the full screen state. This will block until the search
+ /// is complete. For performance, it is recommended to use `tick` and
+ /// `feed` to incrementally make progress on the search instead.
+ pub fn searchAll(self: *ScreenSearch) Allocator.Error!void {
+ while (true) {
+ self.tick() catch |err| switch (err) {
+ error.OutOfMemory => return error.OutOfMemory,
+ error.FeedRequired => try self.feed(),
+ error.SearchComplete => return,
+ };
+ }
+ }
+
+ pub const TickError = Allocator.Error || error{
+ FeedRequired,
+ SearchComplete,
+ };
+
+ /// Make incremental progress on the search without accessing any
+ /// screen state (so no lock is required).
+ ///
+ /// This will return error.FeedRequired if the search cannot make progress
+ /// without being fed more data. In this case, the caller should call
+ /// the `feed` function to provide more data to the searcher.
+ ///
+ /// This will return error.SearchComplete if the search is fully complete.
+ /// This is to signal to the caller that it can move to a more efficient
+ /// sleep/wait state until there is more work to do (e.g. new data to feed).
+ pub fn tick(self: *ScreenSearch) TickError!void {
+ switch (self.state) {
+ .active => try self.tickActive(),
+ .history => try self.tickHistory(),
+ .history_feed => return error.FeedRequired,
+ .complete => return error.SearchComplete,
+ }
+ }
+
+ /// Feed more data to the searcher so it can continue searching. This
+ /// accesses the screen state, so the caller must hold the necessary locks.
+ ///
+ /// Feed on a complete screen search will perform some cleanup of
+ /// potentially stale history results (pruned) and reclaim some memory.
+ pub fn feed(self: *ScreenSearch) Allocator.Error!void {
+ // If the screen resizes, we have to reset our entire search. That
+ // isn't ideal but we don't have a better way right now to handle
+ // reflowing the search results beyond putting a tracked pin for
+ // every single result.
+ if (self.screen.pages.rows != self.rows or
+ self.screen.pages.cols != self.cols)
+ {
+ // Reinit
+ const new: ScreenSearch = try .init(
+ self.allocator(),
+ self.screen,
+ self.needle(),
+ );
+
+ // Deinit/reinit
+ self.deinit();
+ self.* = new;
+
+ // New result should have matching dimensions
+ assert(self.screen.pages.rows == self.rows);
+ assert(self.screen.pages.cols == self.cols);
+ }
+
+ const history: *PageListSearch = if (self.history) |*h| &h.searcher else {
+ // No history to feed, search is complete.
+ self.state = .complete;
+ return;
+ };
+
+ // Future: we may want to feed multiple pages at once here to
+ // lower the frequency of lock acquisitions.
+ if (!try history.feed()) {
+ // No more data to feed, search is complete.
+ self.state = .complete;
+
+ // We use this opportunity to also clean up older history
+ // results that may be gone due to scrollback pruning, though.
+ self.pruneHistory();
+
+ return;
+ }
+
+ // Depending on our state handle where feed goes
+ switch (self.state) {
+ // If we're searching active or history, then feeding doesn't
+ // change the state.
+ .active, .history => {},
+
+ // Feed goes back to searching history.
+ .history_feed => self.state = .history,
+
+ // If we're complete then the feed call above should always
+ // return false and we can't reach this.
+ .complete => unreachable,
+ }
+ }
+
+ fn pruneHistory(self: *ScreenSearch) void {
+ // Go through our history results in order (newest to oldest) to find
+ // any result that contains an invalid serial. Prune up to that
+ // point.
+ for (0..self.history_results.items.len) |i| {
+ const hl = &self.history_results.items[i];
+ const serials = hl.chunks.items(.serial);
+ const lowest = serials[0];
+ if (lowest < self.screen.pages.page_serial_min) {
+ // Everything from here forward we assume is invalid because
+ // our history results only get older.
+ const alloc = self.allocator();
+ for (self.history_results.items[i..]) |*prune_hl| prune_hl.deinit(alloc);
+ self.history_results.shrinkAndFree(alloc, i);
+ return;
+ }
+ }
+ }
+
+ fn tickActive(self: *ScreenSearch) Allocator.Error!void {
+ // For the active area, we consume the entire search in one go
+ // because the active area is generally small.
+ const alloc = self.allocator();
+ while (self.active.next()) |hl| {
+ // If this fails, then we miss a result since `active.next()`
+ // moves forward and prunes data. In the future, we may want
+ // to have some more robust error handling but the only
+ // scenario this would fail is OOM and we're probably in
+ // deeper trouble at that point anyways.
+ var hl_cloned = try hl.clone(alloc);
+ errdefer hl_cloned.deinit(alloc);
+ try self.active_results.append(alloc, hl_cloned);
+ }
+
+ // We've consumed the entire active area, move to history.
+ self.state = .history;
+ }
+
+ fn tickHistory(self: *ScreenSearch) Allocator.Error!void {
+ const history: *HistorySearch = if (self.history) |*h| h else {
+ // No history to search, we're done.
+ self.state = .complete;
+ return;
+ };
+
+ // Try to consume all the loaded matches in one go, because
+ // the search is generally fast for loaded data.
+ const alloc = self.allocator();
+ while (history.searcher.next()) |hl| {
+ // Ignore selections that are found within the starting
+ // node since those are covered by the active area search.
+ if (hl.chunks.items(.node)[0] == history.start_pin.node) continue;
+
+ // Same note as tickActive for error handling.
+ var hl_cloned = try hl.clone(alloc);
+ errdefer hl_cloned.deinit(alloc);
+ try self.history_results.append(alloc, hl_cloned);
+
+ // Since history only appends to our results in reverse order,
+ // we don't need to update any selected match state. The index
+ // and prior results are unaffected.
+ }
+
+ // We need to be fed more data.
+ self.state = .history_feed;
+ }
+
+ /// Reload the active area because it has changed.
+ ///
+ /// Since it is very fast, this will also do the full active area
+ /// search again, too. This avoids any complexity around the search
+ /// state machine.
+ ///
+ /// The caller must hold the necessary locks to access the screen state.
+ pub fn reloadActive(self: *ScreenSearch) Allocator.Error!void {
+ const tw = reloadActive_tw;
+
+ // If our selection pin became garbage it means we scrolled off
+ // the end. Clear our selection and on exit of this function,
+ // try to select the last match.
+ const select_prev: bool = select_prev: {
+ const m = if (self.selected) |*m| m else break :select_prev false;
+ if (!m.highlight.start.garbage and
+ !m.highlight.end.garbage) break :select_prev false;
+
+ m.deinit(self.screen);
+ self.selected = null;
+ break :select_prev true;
+ };
+ defer if (select_prev) {
+ _ = self.select(.prev) catch |err| {
+ log.info("reload failed to reset search selection err={}", .{err});
+ };
+ };
+
+ const alloc = self.allocator();
+ const list: *PageList = &self.screen.pages;
+ if (try self.active.update(list)) |history_node| history: {
+ // We need to account for any active area growth that would
+ // cause new pages to move into our history. If there are new
+ // pages then we need to re-search the pages and add it to
+ // our history results.
+
+ // If our screen has no scrollback then we have no history.
+ if (self.screen.no_scrollback) {
+ assert(self.history == null);
+ break :history;
+ }
+
+ const history_: ?*HistorySearch = if (self.history) |*h| state: {
+ // If our start pin became garbage, it means we pruned all
+ // the way up through it, so we have no history anymore.
+ // Reset our history state.
+ if (h.start_pin.garbage) {
+ h.deinit(self.screen);
+ self.history = null;
+ for (self.history_results.items) |*hl| hl.deinit(alloc);
+ self.history_results.clearRetainingCapacity();
+ break :state null;
+ }
+
+ break :state h;
+ } else null;
+
+ const history = history_ orelse {
+ // No history search yet, but we now have history. So let's
+ // initialize.
+
+ var search: PageListSearch = try .init(
+ alloc,
+ self.needle(),
+ list,
+ history_node,
+ );
+ errdefer search.deinit();
+
+ const pin = try list.trackPin(.{ .node = history_node });
+ errdefer list.untrackPin(pin);
+
+ self.history = .{
+ .searcher = search,
+ .start_pin = pin,
+ };
+
+ // We don't need to update any history since we had no history
+ // before, so we can break out of the whole conditional.
+ break :history;
+ };
+
+ if (history.start_pin.node == history_node) {
+ // No change in the starting node, we're done.
+ break :history;
+ }
+
+ // Do a forward search from our prior node to this one. We
+ // collect all the results into a new list. We ASSUME that
+ // reloadActive is being called frequently enough that there isn't
+ // a massive amount of history to search here.
+ var window: SlidingWindow = try .init(
+ alloc,
+ .forward,
+ self.needle(),
+ );
+ defer window.deinit();
+ while (true) {
+ _ = try window.append(history.start_pin.node);
+ if (history.start_pin.node == history_node) break;
+ const next = history.start_pin.node.next orelse break;
+ history.start_pin.node = next;
+ }
+ assert(history.start_pin.node == history_node);
+
+ var results: std.ArrayList(FlattenedHighlight) = try .initCapacity(
+ alloc,
+ self.history_results.items.len,
+ );
+ errdefer {
+ for (results.items) |*hl| hl.deinit(alloc);
+ results.deinit(alloc);
+ }
+ while (window.next()) |hl| {
+ if (hl.chunks.items(.node)[0] == history_node) continue;
+
+ var hl_cloned = try hl.clone(alloc);
+ errdefer hl_cloned.deinit(alloc);
+ try tw.check(.history_append_new);
+ try results.append(alloc, hl_cloned);
+ }
+
+ // If we have no matches then there is nothing to change
+ // in our history (fast path)
+ if (results.items.len == 0) break :history;
+
+ // The number added to our history. Needed for updating
+ // our selection if we have one.
+ const added_len = results.items.len;
+
+ // Matches! Reverse our list then append all the remaining
+ // history items that didn't start on our original node.
+ std.mem.reverse(FlattenedHighlight, results.items);
+ try tw.check(.history_append_existing);
+ try results.appendSlice(alloc, self.history_results.items);
+ self.history_results.deinit(alloc);
+ self.history_results = results;
+
+ // If our prior selection was in the history area, update
+ // the offset.
+ if (self.selected) |*m| selected: {
+ const active_len = self.active_results.items.len;
+ if (m.idx < active_len) break :selected;
+ m.idx += added_len;
+
+ // Moving the idx should not change our targeted result
+ // since the history is immutable.
+ if (comptime std.debug.runtime_safety) {
+ const hl = self.history_results.items[m.idx - active_len];
+ assert(m.highlight.start.eql(hl.startPin()));
+ }
+ }
+ } else {
+ // No history node means we have no history
+ if (self.history) |*h| {
+ h.deinit(self.screen);
+ self.history = null;
+ for (self.history_results.items) |*hl| hl.deinit(alloc);
+ self.history_results.clearRetainingCapacity();
+ }
+
+ // If we have a selection in the history area, we need to
+ // move it to the end of the active area.
+ if (self.selected) |*m| selected: {
+ const active_len = self.active_results.items.len;
+ if (m.idx < active_len) break :selected;
+ m.deinit(self.screen);
+ self.selected = null;
+ _ = self.select(.prev) catch |err| {
+ log.info("reload failed to reset search selection err={}", .{err});
+ };
+ }
+ }
+
+ // Figure out if we need to fixup our selection later because
+ // it was in the active area.
+ const old_active_len = self.active_results.items.len;
+ const old_selection_idx: ?usize = if (self.selected) |m| m.idx else null;
+ errdefer if (old_selection_idx != null and
+ old_selection_idx.? < old_active_len)
+ {
+ // This is the error scenario. If something fails below,
+ // our active area is probably gone, so we just go back
+ // to the first result because our selection can't be trusted.
+ if (self.selected) |*m| {
+ m.deinit(self.screen);
+ self.selected = null;
+ _ = self.select(.next) catch |err| {
+ log.info("reload failed to reset search selection err={}", .{err});
+ };
+ }
+ };
+
+ // Reset our active search results and search again.
+ for (self.active_results.items) |*hl| hl.deinit(alloc);
+ self.active_results.clearRetainingCapacity();
+ switch (self.state) {
+ // If we're in the active state we run a normal tick so
+ // we can move into a better state.
+ .active => try self.tickActive(),
+
+ // Otherwise, just tick it and move back to whatever state
+ // we were in.
+ else => {
+ const old_state = self.state;
+ defer self.state = old_state;
+ try self.tickActive();
+ },
+ }
+
+ // If we have no scrollback, we need to prune any active results
+ // that aren't in the actual active area. We only do this for the
+ // no scrollback scenario because with scrollback we actually
+ // rely on our active search searching by page to find history
+ // items as well. This is all related to the fact that PageList
+ // scrollback limits are discrete by page size except we special
+ // case zero.
+ if (self.screen.no_scrollback and
+ self.active_results.items.len > 0)
+ active_prune: {
+ const items = self.active_results.items;
+ const tl = self.screen.pages.getTopLeft(.active);
+ for (0.., items) |i, *hl| {
+ if (!tl.before(hl.endPin())) {
+ // Deinit because its going to be pruned no matter
+ // what at some point for not being in the active area.
+ hl.deinit(alloc);
+ continue;
+ }
+
+ // In the active area! Since our results are sorted
+ // that means everything after this is also in the active
+ // area, so we prune up to this i.
+ if (i > 0) self.active_results.replaceRangeAssumeCapacity(
+ 0,
+ i,
+ &.{},
+ );
+
+ break :active_prune;
+ }
+
+ // None are in the active area...
+ self.active_results.clearRetainingCapacity();
+ }
+
+ // Now we have to fixup our selection if we had one.
+ fixup: {
+ const old_idx = old_selection_idx orelse break :fixup;
+ const m = if (self.selected) |*m| m else break :fixup;
+
+ // If our old selection wasn't in the active area, then we
+ // need to fix up our offsets.
+ if (old_idx >= old_active_len) {
+ m.idx -= old_active_len;
+ m.idx += self.active_results.items.len;
+ break :fixup;
+ }
+
+ // We search for the matching highlight in the new active results.
+ for (0.., self.active_results.items) |i, hl| {
+ const untracked = hl.untracked();
+ if (m.highlight.start.eql(untracked.start) and
+ m.highlight.end.eql(untracked.end))
+ {
+ // Found it! Update our index.
+ m.idx = self.active_results.items.len - 1 - i;
+ break :fixup;
+ }
+ }
+
+ // No match, just go back to the first match.
+ m.deinit(self.screen);
+ self.selected = null;
+ _ = self.select(.next) catch |err| {
+ log.info("reload failed to reset search selection err={}", .{err});
+ };
+ }
+ }
+
+ /// Return the selected match.
+ ///
+ /// This does not require read/write access to the underlying screen.
+ pub fn selectedMatch(self: *const ScreenSearch) ?FlattenedHighlight {
+ const sel = self.selected orelse return null;
+ const active_len = self.active_results.items.len;
+ if (sel.idx < active_len) {
+ return self.active_results.items[active_len - 1 - sel.idx];
+ }
+
+ const history_len = self.history_results.items.len;
+ if (sel.idx < active_len + history_len) {
+ return self.history_results.items[sel.idx - active_len];
+ }
+
+ return null;
+ }
+
+ pub const Select = enum {
+ /// Next selection, in reverse order (newest to oldest),
+ /// non-wrapping.
+ next,
+
+ /// Prev selection, in forward order (oldest to newest),
+ /// non-wrapping.
+ prev,
+ };
+
+ /// Select the next or previous search result. This requires read/write
+ /// access to the underlying screen, since we utilize tracked pins to
+ /// ensure our selection sticks with contents changing.
+ pub fn select(self: *ScreenSearch, to: Select) Allocator.Error!bool {
+ // All selection requires valid pins so we prune history and
+ // reload our active area immediately. This ensures all search
+ // results point to valid nodes.
+ try self.reloadActive();
+ self.pruneHistory();
+
+ return switch (to) {
+ .next => try self.selectNext(),
+ .prev => try self.selectPrev(),
+ };
+ }
+
+ fn selectNext(self: *ScreenSearch) Allocator.Error!bool {
+ // Get our previous match so we can change it. If we have no
+ // prior match, we have the easy task of getting the first.
+ var prev = if (self.selected) |*m| m else {
+ // Get our highlight
+ const hl: FlattenedHighlight = hl: {
+ if (self.active_results.items.len > 0) {
+ // Active is in forward order
+ const len = self.active_results.items.len;
+ break :hl self.active_results.items[len - 1];
+ } else if (self.history_results.items.len > 0) {
+ // History is in reverse order
+ break :hl self.history_results.items[0];
+ } else {
+ // No matches at all. Can't select anything.
+ return false;
+ }
+ };
+
+ // Pin it so we can track any movement
+ const tracked = try hl.untracked().track(self.screen);
+ errdefer tracked.deinit(self.screen);
+
+ // Our selection is index zero since we just started and
+ // we store our selection.
+ self.selected = .{
+ .idx = 0,
+ .highlight = tracked,
+ };
+ return true;
+ };
+
+ const active_len = self.active_results.items.len;
+ const history_len = self.history_results.items.len;
+ const next_idx = if (prev.idx + 1 >= active_len + history_len) 0 else prev.idx + 1;
+ const hl: FlattenedHighlight = if (next_idx < active_len)
+ self.active_results.items[active_len - 1 - next_idx]
+ else
+ self.history_results.items[next_idx - active_len];
+
+ // Pin it so we can track any movement
+ const tracked = try hl.untracked().track(self.screen);
+ errdefer tracked.deinit(self.screen);
+
+ // Free our previous match and setup our new selection
+ prev.deinit(self.screen);
+ self.selected = .{
+ .idx = next_idx,
+ .highlight = tracked,
+ };
+
+ return true;
+ }
+
+ fn selectPrev(self: *ScreenSearch) Allocator.Error!bool {
+ // Get our previous match so we can change it. If we have no
+ // prior match, we have the easy task of getting the last.
+ var prev = if (self.selected) |*m| m else {
+ // Get our highlight (oldest match)
+ const hl: FlattenedHighlight = hl: {
+ if (self.history_results.items.len > 0) {
+ // History is in reverse order, so last item is oldest
+ const len = self.history_results.items.len;
+ break :hl self.history_results.items[len - 1];
+ } else if (self.active_results.items.len > 0) {
+ // Active is in forward order, so first item is oldest
+ break :hl self.active_results.items[0];
+ } else {
+ // No matches at all. Can't select anything.
+ return false;
+ }
+ };
+
+ // Pin it so we can track any movement
+ const tracked = try hl.untracked().track(self.screen);
+ errdefer tracked.deinit(self.screen);
+
+ // Our selection is the last index since we just started
+ // and we store our selection.
+ const active_len = self.active_results.items.len;
+ const history_len = self.history_results.items.len;
+ self.selected = .{
+ .idx = active_len + history_len - 1,
+ .highlight = tracked,
+ };
+ return true;
+ };
+
+ const active_len = self.active_results.items.len;
+ const history_len = self.history_results.items.len;
+ const next_idx = if (prev.idx != 0) prev.idx - 1 else active_len - 1 + history_len;
+
+ const hl: FlattenedHighlight = if (next_idx < active_len)
+ self.active_results.items[active_len - 1 - next_idx]
+ else
+ self.history_results.items[next_idx - active_len];
+
+ // Pin it so we can track any movement
+ const tracked = try hl.untracked().track(self.screen);
+ errdefer tracked.deinit(self.screen);
+
+ // Free our previous match and setup our new selection
+ prev.deinit(self.screen);
+ self.selected = .{
+ .idx = next_idx,
+ .highlight = tracked,
+ };
+
+ return true;
+ }
+};
+
+test "simple search" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 2 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+ try testing.expectEqual(2, search.active_results.items.len);
+ // We don't test history results since there is overlap
+
+ // Get all matches
+ const matches = try search.matches(alloc);
+ defer alloc.free(matches);
+ try testing.expectEqual(2, matches.len);
+
+ {
+ const sel = matches[0].untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+ {
+ const sel = matches[1].untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+}
+
+test "simple search with history" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{
+ .cols = 10,
+ .rows = 2,
+ .max_scrollback = std.math.maxInt(usize),
+ });
+ defer t.deinit(alloc);
+ const list: *PageList = &t.screens.active.pages;
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ s.nextSlice("Fizz\r\n");
+ while (list.totalPages() < 3) s.nextSlice("\r\n");
+ for (0..list.rows) |_| s.nextSlice("\r\n");
+ s.nextSlice("hello.");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+ try testing.expectEqual(0, search.active_results.items.len);
+
+ // Get all matches
+ const matches = try search.matches(alloc);
+ defer alloc.free(matches);
+ try testing.expectEqual(1, matches.len);
+
+ {
+ const sel = matches[0].untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+}
+
+test "reload active with history change" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{
+ .cols = 10,
+ .rows = 2,
+ .max_scrollback = std.math.maxInt(usize),
+ });
+ defer t.deinit(alloc);
+ const list: *PageList = &t.screens.active.pages;
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\n");
+
+ // Start up our search which will populate our initial active area.
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+ {
+ const matches = try search.matches(alloc);
+ defer alloc.free(matches);
+ try testing.expectEqual(1, matches.len);
+ }
+
+ // Grow into two pages so our history pin will move.
+ while (list.totalPages() < 2) s.nextSlice("\r\n");
+ for (0..list.rows) |_| s.nextSlice("\r\n");
+ s.nextSlice("2Fizz");
+
+ // Active area changed so reload
+ try search.reloadActive();
+ try search.searchAll();
+
+ // Get all matches
+ {
+ const matches = try search.matches(alloc);
+ defer alloc.free(matches);
+ try testing.expectEqual(2, matches.len);
+ {
+ const sel = matches[1].untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+ {
+ const sel = matches[0].untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 1,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 4,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ }
+
+ // Reset the screen which will make our pin garbage.
+ t.fullReset();
+ s.nextSlice("WeFizzing");
+ try search.reloadActive();
+ try search.searchAll();
+
+ {
+ const matches = try search.matches(alloc);
+ defer alloc.free(matches);
+ try testing.expectEqual(1, matches.len);
+ {
+ const sel = matches[0].untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 2,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 5,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ }
+}
+
+test "active change contents" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 5 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fuzz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+ try testing.expectEqual(1, search.active_results.items.len);
+
+ // Erase the screen, move our cursor to the top, and change contents.
+ s.nextSlice("\x1b[2J\x1b[H"); // Clear screen and move home
+ s.nextSlice("Bang\r\nFizz\r\nHello!");
+
+ try search.reloadActive();
+ try search.searchAll();
+ try testing.expectEqual(1, search.active_results.items.len);
+
+ // Get all matches
+ const matches = try search.matches(alloc);
+ defer alloc.free(matches);
+ try testing.expectEqual(1, matches.len);
+
+ {
+ const sel = matches[0].untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+}
+
+test "select next" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 2 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+
+ // Initially no selection
+ try testing.expect(search.selectedMatch() == null);
+
+ // Select our next match (first)
+ try search.searchAll();
+ _ = try search.select(.next);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+
+ // Next match
+ _ = try search.select(.next);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+
+ // Next match (wrap)
+ _ = try search.select(.next);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+}
+
+test "select in active changes contents completely" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 5 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+ _ = try search.select(.next);
+ _ = try search.select(.next);
+ {
+ // Initial selection is the first fizz
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+
+ // Erase the screen, move our cursor to the top, and change contents.
+ s.nextSlice("\x1b[2J\x1b[H"); // Clear screen and move home
+ s.nextSlice("Fuzz\r\nFizz\r\nHello!");
+
+ try search.reloadActive();
+ {
+ // Our selection should move to the first
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+
+ // Erase the screen, redraw with same contents.
+ s.nextSlice("\x1b[2J\x1b[H"); // Clear screen and move home
+ s.nextSlice("Fuzz\r\nFizz\r\nFizz");
+
+ try search.reloadActive();
+ {
+ // Our selection should not move to the first
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+}
+
+test "select into history" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{
+ .cols = 10,
+ .rows = 2,
+ .max_scrollback = std.math.maxInt(usize),
+ });
+ defer t.deinit(alloc);
+ const list: *PageList = &t.screens.active.pages;
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ s.nextSlice("Fizz\r\n");
+ while (list.totalPages() < 3) s.nextSlice("\r\n");
+ for (0..list.rows) |_| s.nextSlice("\r\n");
+ s.nextSlice("hello.");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+
+ // Get all matches
+ _ = try search.select(.next);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+
+ // Erase the screen, redraw with same contents.
+ s.nextSlice("\x1b[2J\x1b[H"); // Clear screen and move home
+ s.nextSlice("yo yo");
+
+ try search.reloadActive();
+ {
+ // Our selection should not move since the history is still active.
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+
+ // Create some new history by adding more lines.
+ s.nextSlice("\r\nfizz\r\nfizz\r\nfizz"); // Clear screen and move home
+ try search.reloadActive();
+ {
+ // Our selection should not move since the history is still not
+ // pruned.
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+}
+
+test "select prev" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 2 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+
+ // Initially no selection
+ try testing.expect(search.selectedMatch() == null);
+
+ // Select prev (oldest first)
+ try search.searchAll();
+ _ = try search.select(.prev);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+
+ // Prev match (towards newest)
+ _ = try search.select(.prev);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+
+ // Prev match (wrap)
+ _ = try search.select(.prev);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+}
+
+test "select prev then next" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 2 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+
+ // Select next (newest first)
+ _ = try search.select(.next);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ }
+
+ // Select next (older)
+ _ = try search.select(.next);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ }
+
+ // Select prev (back to newer)
+ _ = try search.select(.prev);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ }
+}
+
+test "select prev with history" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{
+ .cols = 10,
+ .rows = 2,
+ .max_scrollback = std.math.maxInt(usize),
+ });
+ defer t.deinit(alloc);
+ const list: *PageList = &t.screens.active.pages;
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ s.nextSlice("Fizz\r\n");
+ while (list.totalPages() < 3) s.nextSlice("\r\n");
+ for (0..list.rows) |_| s.nextSlice("\r\n");
+ s.nextSlice("Fizz.");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+
+ // Select prev (oldest first, should be in history)
+ _ = try search.select(.prev);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+
+ // Select prev (towards newer, should move to active area)
+ _ = try search.select(.prev);
+ {
+ const sel = search.selectedMatch().?.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+}
+
+test "screen search no scrollback has no history" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{
+ .cols = 10,
+ .rows = 2,
+ .max_scrollback = 0,
+ });
+ defer t.deinit(alloc);
+
+ // Alt screen has no scrollback
+ _ = try t.switchScreen(.alternate);
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ // This will probably stop working at some point and we'll have
+ // no way to test it using public APIs, but at the time of writing
+ // this test, CSI 22 J (scroll complete) pushes into scrollback
+ // with alt screen.
+ s.nextSlice("Fizz\r\n");
+ s.nextSlice("\x1b[22J");
+ s.nextSlice("hello.");
+
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+ try testing.expectEqual(0, search.active_results.items.len);
+
+ // Get all matches
+ const matches = try search.matches(alloc);
+ defer alloc.free(matches);
+ try testing.expectEqual(0, matches.len);
+}
+
+test "reloadActive partial history cleanup on appendSlice error" {
+ // This test verifies that when reloadActive fails at appendSlice (after
+ // the loop), all FlattenedHighlight items are properly cleaned up.
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{
+ .cols = 10,
+ .rows = 2,
+ .max_scrollback = std.math.maxInt(usize),
+ });
+ defer t.deinit(alloc);
+ const list: *PageList = &t.screens.active.pages;
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ // Write multiple "Fizz" matches that will end up in history.
+ // We need enough content to push "Fizz" entries into scrollback.
+ s.nextSlice("Fizz\r\nFizz\r\n");
+ while (list.totalPages() < 3) s.nextSlice("\r\n");
+ for (0..list.rows) |_| s.nextSlice("\r\n");
+ s.nextSlice("Fizz.");
+
+ // Complete initial search
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+
+ // Now trigger reloadActive by adding more content that changes the
+ // active/history boundary. First add more "Fizz" entries to history.
+ s.nextSlice("\r\nFizz\r\nFizz\r\n");
+ while (list.totalPages() < 4) s.nextSlice("\r\n");
+ for (0..list.rows) |_| s.nextSlice("\r\n");
+
+ // Arm the tripwire to fail at appendSlice (after the loop completes).
+ // At this point, there are FlattenedHighlight items in the results list
+ // that need cleanup.
+ const tw = reloadActive_tw;
+ defer tw.end(.reset) catch unreachable;
+ tw.errorAlways(.history_append_existing, error.OutOfMemory);
+
+ // reloadActive is called by select(), which should trigger the error path.
+ // If the bug exists, testing.allocator will report a memory leak
+ // because FlattenedHighlight items weren't cleaned up.
+ try testing.expectError(error.OutOfMemory, search.select(.next));
+}
+
+test "reloadActive partial history cleanup on loop append error" {
+ // This test verifies that when reloadActive fails inside the loop
+ // (after some items have been appended), all FlattenedHighlight items
+ // are properly cleaned up.
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{
+ .cols = 10,
+ .rows = 2,
+ .max_scrollback = std.math.maxInt(usize),
+ });
+ defer t.deinit(alloc);
+ const list: *PageList = &t.screens.active.pages;
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ // Write multiple "Fizz" matches that will end up in history.
+ // We need enough content to push "Fizz" entries into scrollback.
+ s.nextSlice("Fizz\r\nFizz\r\n");
+ while (list.totalPages() < 3) s.nextSlice("\r\n");
+ for (0..list.rows) |_| s.nextSlice("\r\n");
+ s.nextSlice("Fizz.");
+
+ // Complete initial search
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz");
+ defer search.deinit();
+ try search.searchAll();
+
+ // Now trigger reloadActive by adding more content that changes the
+ // active/history boundary. First add more "Fizz" entries to history.
+ s.nextSlice("\r\nFizz\r\nFizz\r\n");
+ while (list.totalPages() < 4) s.nextSlice("\r\n");
+ for (0..list.rows) |_| s.nextSlice("\r\n");
+
+ // Arm the tripwire to fail after the first loop append succeeds.
+ // This leaves at least one FlattenedHighlight in the results list
+ // that needs cleanup.
+ const tw = reloadActive_tw;
+ defer tw.end(.reset) catch unreachable;
+ tw.errorAfter(.history_append_new, error.OutOfMemory, 1);
+
+ // reloadActive is called by select(), which should trigger the error path.
+ // If the bug exists, testing.allocator will report a memory leak
+ // because FlattenedHighlight items weren't cleaned up.
+ try testing.expectError(error.OutOfMemory, search.select(.next));
+}
+
+test "select after clearing scrollback" {
+ // Regression test for: https://github.com/ghostty-org/ghostty/issues/11957
+ // After clearing scrollback (CSI 3J), selecting next/prev should not crash.
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{
+ .cols = 10,
+ .rows = 2,
+ .max_scrollback = std.math.maxInt(usize),
+ });
+ defer t.deinit(alloc);
+ const list: *PageList = &t.screens.active.pages;
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ // Write enough content to push matches into scrollback history.
+ s.nextSlice("error\r\n");
+ while (list.totalPages() < 3) s.nextSlice("error\r\n");
+ for (0..list.rows) |_| s.nextSlice("\r\n");
+ s.nextSlice("error.");
+
+ // Start search and find all matches.
+ var search: ScreenSearch = try .init(alloc, t.screens.active, "error");
+ defer search.deinit();
+ try search.searchAll();
+
+ // Should have matches in both history and active areas.
+ try testing.expect(search.history_results.items.len > 0);
+ try testing.expect(search.active_results.items.len > 0);
+
+ // Select a match first (so we have a selection).
+ _ = try search.select(.next);
+ try testing.expect(search.selected != null);
+
+ // Clear scrollback (equivalent to CSI 3J / Cmd+K erasing scrollback).
+ t.eraseDisplay(.scrollback, false);
+
+ // Selecting next/prev after clearing scrollback should not crash.
+ // Before the fix, this would hit an assertion in trackPin because
+ // the FlattenedHighlight contained dangling node pointers.
+ _ = try search.select(.next);
+ _ = try search.select(.prev);
+}
diff --git a/vendor/libghostty-vt/src/terminal/search/sliding_window.zig b/vendor/libghostty-vt/src/terminal/search/sliding_window.zig
new file mode 100644
index 00000000..93a606fd
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/search/sliding_window.zig
@@ -0,0 +1,1676 @@
+const std = @import("std");
+const assert = @import("../../quirks.zig").inlineAssert;
+const Allocator = std.mem.Allocator;
+const CircBuf = @import("../../datastruct/main.zig").CircBuf;
+const terminal = @import("../main.zig");
+const point = terminal.point;
+const size = terminal.size;
+const PageList = terminal.PageList;
+const Pin = PageList.Pin;
+const Selection = terminal.Selection;
+const Screen = terminal.Screen;
+const Terminal = terminal.Terminal;
+const PageFormatter = @import("../formatter.zig").PageFormatter;
+const FlattenedHighlight = terminal.highlight.Flattened;
+
+/// Searches page nodes via a sliding window. The sliding window maintains
+/// the invariant that data isn't pruned until (1) we've searched it and
+/// (2) we've accounted for overlaps across pages to fit the needle.
+///
+/// The sliding window is first initialized empty. Pages are then appended
+/// in the order to search them. The sliding window supports both a forward
+/// and reverse order specified via `init`. The pages should be appended
+/// in the correct order matching the search direction.
+///
+/// All appends grow the window. The window is only pruned when a search
+/// is done (positive or negative match) via `next()`.
+///
+/// To avoid unnecessary memory growth, the recommended usage is to
+/// call `next()` until it returns null and then `append` the next page
+/// and repeat the process. This will always maintain the minimum
+/// required memory to search for the needle.
+///
+/// The caller is responsible for providing the pages and ensuring they're
+/// in the proper order. The SlidingWindow itself doesn't own the pages, but
+/// it will contain pointers to them in order to return selections. If any
+/// pages become invalid, the caller should clear the sliding window and
+/// start over.
+pub const SlidingWindow = struct {
+ /// The allocator to use for all the data within this window. We
+ /// store this rather than passing it around because its already
+ /// part of multiple elements (eg. Meta's CellMap) and we want to
+ /// ensure we always use a consistent allocator. Additionally, only
+ /// a small amount of sliding windows are expected to be in use
+ /// at any one time so the memory overhead isn't that large.
+ alloc: Allocator,
+
+ /// The data buffer is a circular buffer of u8 that contains the
+ /// encoded page text that we can use to search for the needle.
+ data: DataBuf,
+
+ /// The meta buffer is a circular buffer that contains the metadata
+ /// about the pages we're searching. This usually isn't that large
+ /// so callers must iterate through it to find the offset to map
+ /// data to meta.
+ meta: MetaBuf,
+
+ /// Buffer that can fit any amount of chunks necessary for next
+ /// to never fail allocation.
+ chunk_buf: std.MultiArrayList(FlattenedHighlight.Chunk),
+
+ /// Offset into data for our current state. This handles the
+ /// situation where our search moved through meta[0] but didn't
+ /// do enough to prune it.
+ data_offset: usize = 0,
+
+ /// The needle we're searching for. Does own the memory.
+ needle: []const u8,
+
+ /// The search direction. If the direction is forward then pages should
+ /// be appended in forward linked list order from the PageList. If the
+ /// direction is reverse then pages should be appended in reverse order.
+ ///
+ /// This is important because in most cases, a reverse search is going
+ /// to be more desirable to search from the end of the active area
+ /// backwards so more recent data is found first. Supporting both is
+ /// trivial though and will let us do more complex optimizations in the
+ /// future (e.g. starting from the viewport and doing a forward/reverse
+ /// concurrently from that point).
+ direction: Direction,
+
+ /// A buffer to store the overlap search data. This is used to search
+ /// overlaps between pages where the match starts on one page and
+ /// ends on another. The length is always `needle.len * 2`.
+ overlap_buf: []u8,
+
+ const Direction = enum { forward, reverse };
+ const DataBuf = CircBuf(u8, 0);
+ const MetaBuf = CircBuf(Meta, undefined);
+ const Meta = struct {
+ node: *PageList.List.Node,
+ serial: u64,
+ cell_map: std.ArrayList(point.Coordinate),
+
+ pub fn deinit(self: *Meta, alloc: Allocator) void {
+ self.cell_map.deinit(alloc);
+ }
+ };
+
+ pub fn init(
+ alloc: Allocator,
+ direction: Direction,
+ needle_unowned: []const u8,
+ ) Allocator.Error!SlidingWindow {
+ var data = try DataBuf.init(alloc, 0);
+ errdefer data.deinit(alloc);
+
+ var meta = try MetaBuf.init(alloc, 0);
+ errdefer meta.deinit(alloc);
+
+ const needle = try alloc.dupe(u8, needle_unowned);
+ errdefer alloc.free(needle);
+ switch (direction) {
+ .forward => {},
+ .reverse => std.mem.reverse(u8, needle),
+ }
+
+ const overlap_buf = try alloc.alloc(u8, needle.len * 2);
+ errdefer alloc.free(overlap_buf);
+
+ return .{
+ .alloc = alloc,
+ .data = data,
+ .meta = meta,
+ .chunk_buf = .empty,
+ .needle = needle,
+ .direction = direction,
+ .overlap_buf = overlap_buf,
+ };
+ }
+
+ pub fn deinit(self: *SlidingWindow) void {
+ self.alloc.free(self.overlap_buf);
+ self.alloc.free(self.needle);
+ self.chunk_buf.deinit(self.alloc);
+ self.data.deinit(self.alloc);
+
+ var meta_it = self.meta.iterator(.forward);
+ while (meta_it.next()) |meta| meta.deinit(self.alloc);
+ self.meta.deinit(self.alloc);
+ }
+
+ /// Clear all data but retain allocated capacity.
+ pub fn clearAndRetainCapacity(self: *SlidingWindow) void {
+ var meta_it = self.meta.iterator(.forward);
+ while (meta_it.next()) |meta| meta.deinit(self.alloc);
+ self.meta.clear();
+ self.data.clear();
+ self.data_offset = 0;
+ }
+
+ /// Search the window for the next occurrence of the needle. As
+ /// the window moves, the window will prune itself while maintaining
+ /// the invariant that the window is always big enough to contain
+ /// the needle.
+ ///
+ /// This returns a flattened highlight on a match. The
+ /// flattened highlight requires allocation and is therefore more expensive
+ /// than a normal selection, but it is more efficient to render since it
+ /// has all the information without having to dereference pointers into
+ /// the terminal state.
+ ///
+ /// The flattened highlight chunks reference internal memory for this
+ /// sliding window and are only valid until the next call to `next()`
+ /// or `append()`. If the caller wants to retain the flattened highlight
+ /// then they should clone it.
+ pub fn next(self: *SlidingWindow) ?FlattenedHighlight {
+ const slices = slices: {
+ // If we have less data then the needle then we can't possibly match
+ const data_len = self.data.len();
+ if (data_len < self.needle.len) return null;
+
+ break :slices self.data.getPtrSlice(
+ self.data_offset,
+ data_len - self.data_offset,
+ );
+ };
+
+ // Search the first slice for the needle.
+ if (std.ascii.indexOfIgnoreCase(slices[0], self.needle)) |idx| {
+ return self.highlight(
+ idx,
+ self.needle.len,
+ );
+ }
+
+ // Search the overlap buffer for the needle.
+ if (slices[0].len > 0 and slices[1].len > 0) overlap: {
+ // Get up to needle.len - 1 bytes from each side (as much as
+ // we can) and store it in the overlap buffer.
+ const prefix: []const u8 = prefix: {
+ const len = @min(slices[0].len, self.needle.len - 1);
+ const idx = slices[0].len - len;
+ break :prefix slices[0][idx..];
+ };
+ const suffix: []const u8 = suffix: {
+ const len = @min(slices[1].len, self.needle.len - 1);
+ break :suffix slices[1][0..len];
+ };
+ const overlap_len = prefix.len + suffix.len;
+ assert(overlap_len <= self.overlap_buf.len);
+ @memcpy(self.overlap_buf[0..prefix.len], prefix);
+ @memcpy(self.overlap_buf[prefix.len..overlap_len], suffix);
+
+ // Search the overlap
+ const idx = std.ascii.indexOfIgnoreCase(
+ self.overlap_buf[0..overlap_len],
+ self.needle,
+ ) orelse break :overlap;
+
+ // We found a match in the overlap buffer. We need to map the
+ // index back to the data buffer in order to get our selection.
+ return self.highlight(
+ slices[0].len - prefix.len + idx,
+ self.needle.len,
+ );
+ }
+
+ // Search the last slice for the needle.
+ if (std.ascii.indexOfIgnoreCase(slices[1], self.needle)) |idx| {
+ return self.highlight(
+ slices[0].len + idx,
+ self.needle.len,
+ );
+ }
+
+ // Special case 1-lengthed needles to delete the entire buffer.
+ if (self.needle.len == 1) {
+ self.clearAndRetainCapacity();
+ self.assertIntegrity();
+ return null;
+ }
+
+ // No match. We keep `needle.len - 1` bytes available to
+ // handle the future overlap case.
+ prune: {
+ var meta_it = self.meta.iterator(.reverse);
+ var saved: usize = 0;
+ while (meta_it.next()) |meta| {
+ const needed = self.needle.len - 1 - saved;
+ if (meta.cell_map.items.len >= needed) {
+ // We save up to this meta. We set our data offset
+ // to exactly where it needs to be to continue
+ // searching.
+ self.data_offset = meta.cell_map.items.len - needed;
+ break;
+ }
+
+ saved += meta.cell_map.items.len;
+ } else {
+ // If we exited the while loop naturally then we
+ // never got the amount we needed and so there is
+ // nothing to prune.
+ assert(saved < self.needle.len - 1);
+ break :prune;
+ }
+
+ const prune_count = self.meta.len() - meta_it.idx;
+ if (prune_count == 0) {
+ // This can happen if we need to save up to the first
+ // meta value to retain our window.
+ break :prune;
+ }
+
+ // We can now delete all the metas up to but NOT including
+ // the meta we found through meta_it.
+ meta_it = self.meta.iterator(.forward);
+ var prune_data_len: usize = 0;
+ for (0..prune_count) |_| {
+ const meta = meta_it.next().?;
+ prune_data_len += meta.cell_map.items.len;
+ meta.deinit(self.alloc);
+ }
+ self.meta.deleteOldest(prune_count);
+ self.data.deleteOldest(prune_data_len);
+ }
+
+ // Our data offset now moves to needle.len - 1 from the end so
+ // that we can handle the overlap case.
+ self.data_offset = self.data.len() - self.needle.len + 1;
+
+ self.assertIntegrity();
+ return null;
+ }
+
+ /// Return a flattened highlight for the given start and length.
+ ///
+ /// The flattened highlight can be used to render the highlight
+ /// in the most efficient way because it doesn't require a terminal
+ /// lock to access terminal data to compare whether some viewport
+ /// matches the highlight (because it doesn't need to traverse
+ /// the page nodes).
+ ///
+ /// The start index is assumed to be relative to the offset. i.e.
+ /// index zero is actually at `self.data[self.data_offset]`. The
+ /// selection will account for the offset.
+ fn highlight(
+ self: *SlidingWindow,
+ start_offset: usize,
+ len: usize,
+ ) terminal.highlight.Flattened {
+ const start = start_offset + self.data_offset;
+ const end = start + len - 1;
+ if (comptime std.debug.runtime_safety) {
+ assert(start < self.data.len());
+ assert(start + len <= self.data.len());
+ }
+
+ // Clear our previous chunk buffer to store this result
+ self.chunk_buf.clearRetainingCapacity();
+ var result: terminal.highlight.Flattened = .empty;
+
+ // Go through the meta nodes to find our start.
+ const tl: struct {
+ /// If non-null, we need to continue searching for the bottom-right.
+ br: ?struct {
+ it: MetaBuf.Iterator,
+ consumed: usize,
+ },
+
+ /// Data to prune, both are lengths.
+ prune: struct {
+ meta: usize,
+ data: usize,
+ },
+ } = tl: {
+ var meta_it = self.meta.iterator(.forward);
+ var meta_consumed: usize = 0;
+ while (meta_it.next()) |meta| {
+ // Always increment our consumed count so that our index
+ // is right for the end search if we do it.
+ const prior_meta_consumed = meta_consumed;
+ meta_consumed += meta.cell_map.items.len;
+
+ // meta_i is the index we expect to find the match in the
+ // cell map within this meta if it contains it.
+ const meta_i = start - prior_meta_consumed;
+
+ // This meta doesn't contain the match. This means we
+ // can also prune this set of data because we only look
+ // forward.
+ if (meta_i >= meta.cell_map.items.len) continue;
+
+ // Now we look for the end. In MOST cases it is the same as
+ // our starting chunk because highlights are usually small and
+ // not on a boundary, so let's optimize for that.
+ const end_i = end - prior_meta_consumed;
+ if (end_i < meta.cell_map.items.len) {
+ @branchHint(.likely);
+
+ // The entire highlight is within this meta.
+ const start_map = meta.cell_map.items[meta_i];
+ const end_map = meta.cell_map.items[end_i];
+ result.top_x = start_map.x;
+ result.bot_x = end_map.x;
+ self.chunk_buf.appendAssumeCapacity(.{
+ .node = meta.node,
+ .serial = meta.serial,
+ .start = @intCast(start_map.y),
+ .end = @intCast(end_map.y + 1),
+ });
+
+ break :tl .{
+ .br = null,
+ .prune = .{
+ .meta = meta_it.idx - 1,
+ .data = prior_meta_consumed,
+ },
+ };
+ } else {
+ // We found the meta that contains the start of the match
+ // only. Consume this entire node from our start offset.
+ const map = meta.cell_map.items[meta_i];
+ result.top_x = map.x;
+ self.chunk_buf.appendAssumeCapacity(.{
+ .node = meta.node,
+ .serial = meta.serial,
+ .start = @intCast(map.y),
+ .end = meta.node.data.size.rows,
+ });
+
+ break :tl .{
+ .br = .{
+ .it = meta_it,
+ .consumed = meta_consumed,
+ },
+ .prune = .{
+ .meta = meta_it.idx - 1,
+ .data = prior_meta_consumed,
+ },
+ };
+ }
+ } else {
+ // Precondition that the start index is within the data buffer.
+ unreachable;
+ }
+ };
+
+ // Search for our end.
+ if (tl.br) |br| {
+ var meta_it = br.it;
+ var meta_consumed: usize = br.consumed;
+ while (meta_it.next()) |meta| {
+ // meta_i is the index we expect to find the match in the
+ // cell map within this meta if it contains it.
+ const meta_i = end - meta_consumed;
+ if (meta_i >= meta.cell_map.items.len) {
+ // This meta doesn't contain the match. We still add it
+ // to our results because we want the full flattened list.
+ self.chunk_buf.appendAssumeCapacity(.{
+ .node = meta.node,
+ .serial = meta.serial,
+ .start = 0,
+ .end = meta.node.data.size.rows,
+ });
+
+ meta_consumed += meta.cell_map.items.len;
+ continue;
+ }
+
+ // We found it
+ const map = meta.cell_map.items[meta_i];
+ result.bot_x = map.x;
+ self.chunk_buf.appendAssumeCapacity(.{
+ .node = meta.node,
+ .serial = meta.serial,
+ .start = 0,
+ .end = @intCast(map.y + 1),
+ });
+ break;
+ } else {
+ // Precondition that the end index is within the data buffer.
+ unreachable;
+ }
+ }
+
+ // Our offset into the current meta block is the start index
+ // minus the amount of data fully consumed. We then add one
+ // to move one past the match so we don't repeat it.
+ self.data_offset = start - tl.prune.data + 1;
+
+ // If we went beyond our initial meta node we can prune.
+ if (tl.prune.meta > 0) {
+ // Deinit all our memory in the meta blocks prior to our
+ // match.
+ var meta_it = self.meta.iterator(.forward);
+ var meta_consumed: usize = 0;
+ for (0..tl.prune.meta) |_| {
+ const meta: *Meta = meta_it.next().?;
+ meta_consumed += meta.cell_map.items.len;
+ meta.deinit(self.alloc);
+ }
+ if (comptime std.debug.runtime_safety) {
+ assert(meta_it.idx == tl.prune.meta);
+ assert(meta_it.next().?.node == self.chunk_buf.items(.node)[0]);
+ }
+ self.meta.deleteOldest(tl.prune.meta);
+
+ // Delete all the data up to our current index.
+ assert(tl.prune.data > 0);
+ self.data.deleteOldest(tl.prune.data);
+ }
+
+ switch (self.direction) {
+ .forward => {},
+ .reverse => {
+ const slice = self.chunk_buf.slice();
+ const nodes = slice.items(.node);
+ const starts = slice.items(.start);
+ const ends = slice.items(.end);
+
+ if (self.chunk_buf.len > 1) {
+ // Reverse all our chunks. This should be pretty obvious why.
+ std.mem.reverse(*PageList.List.Node, nodes);
+ std.mem.reverse(size.CellCountInt, starts);
+ std.mem.reverse(size.CellCountInt, ends);
+
+ // Now normally with forward traversal with multiple pages,
+ // the suffix of the first page and the prefix of the last
+ // page are used.
+ //
+ // For a reverse traversal, this is inverted (since the
+ // pages are in reverse order we get the suffix of the last
+ // page and the prefix of the first page). So we need to
+ // invert this.
+ //
+ // We DON'T need to do this for any middle pages because
+ // they always use the full page.
+ //
+ // This is a fixup that makes our start/end match the
+ // same logic as the loops above if they were in forward
+ // order.
+ assert(nodes.len >= 2);
+ starts[0] = ends[0] - 1;
+ ends[0] = nodes[0].data.size.rows;
+ ends[nodes.len - 1] = starts[nodes.len - 1] + 1;
+ starts[nodes.len - 1] = 0;
+ } else {
+ // For a single chunk, the y values are in reverse order
+ // (start is the screen-end, end is the screen-start).
+ // Swap them to get proper top-to-bottom order.
+ const start_y = starts[0];
+ starts[0] = ends[0] - 1;
+ ends[0] = start_y + 1;
+ }
+
+ // X values also need to be reversed since the top/bottom
+ // are swapped for the nodes.
+ const top_x = result.top_x;
+ result.top_x = result.bot_x;
+ result.bot_x = top_x;
+ },
+ }
+
+ // Copy over our MultiArrayList so it points to the proper memory.
+ result.chunks = self.chunk_buf;
+ return result;
+ }
+
+ /// Add a new node to the sliding window. This will always grow
+ /// the sliding window; data isn't pruned until it is consumed
+ /// via a search (via next()).
+ ///
+ /// Returns the number of bytes of content added to the sliding window.
+ /// The total bytes will be larger since this omits metadata, but it is
+ /// an accurate measure of the text content size added.
+ pub fn append(
+ self: *SlidingWindow,
+ node: *PageList.List.Node,
+ ) Allocator.Error!usize {
+ // Initialize our metadata for the node.
+ var meta: Meta = .{
+ .node = node,
+ .serial = node.serial,
+ .cell_map = .empty,
+ };
+ errdefer meta.deinit(self.alloc);
+
+ // This is suboptimal but we need to encode the page once to
+ // temporary memory, and then copy it into our circular buffer.
+ // In the future, we should benchmark and see if we can encode
+ // directly into the circular buffer.
+ var encoded: std.Io.Writer.Allocating = .init(self.alloc);
+ defer encoded.deinit();
+
+ // Encode the page into the buffer.
+ const formatter: PageFormatter = formatter: {
+ var formatter: PageFormatter = .init(&meta.node.data, .{
+ .emit = .plain,
+ .unwrap = true,
+ });
+ formatter.point_map = .{
+ .alloc = self.alloc,
+ .map = &meta.cell_map,
+ };
+ break :formatter formatter;
+ };
+ formatter.format(&encoded.writer) catch {
+ // writer uses anyerror but the only realistic error on
+ // an ArrayList is out of memory.
+ return error.OutOfMemory;
+ };
+ assert(meta.cell_map.items.len == encoded.written().len);
+
+ // If the node we're adding isn't soft-wrapped, we add the
+ // trailing newline.
+ const row = node.data.getRow(node.data.size.rows - 1);
+ if (!row.wrap) {
+ encoded.writer.writeByte('\n') catch return error.OutOfMemory;
+ try meta.cell_map.append(
+ self.alloc,
+ meta.cell_map.getLastOrNull() orelse .{
+ .x = 0,
+ .y = 0,
+ },
+ );
+ }
+
+ // If our written data is empty, then there is nothing to
+ // add to our data set.
+ const written = encoded.written();
+ if (written.len == 0) {
+ self.assertIntegrity();
+ return 0;
+ }
+
+ // Get our written data. If we're doing a reverse search then we
+ // need to reverse all our encodings.
+ switch (self.direction) {
+ .forward => {},
+ .reverse => {
+ std.mem.reverse(u8, written);
+ std.mem.reverse(point.Coordinate, meta.cell_map.items);
+ },
+ }
+
+ // Ensure our buffers are big enough to store what we need.
+ try self.data.ensureUnusedCapacity(self.alloc, written.len);
+ try self.meta.ensureUnusedCapacity(self.alloc, 1);
+ try self.chunk_buf.ensureTotalCapacity(self.alloc, self.meta.capacity());
+
+ // Append our new node to the circular buffer.
+ self.data.appendSliceAssumeCapacity(written);
+ self.meta.appendAssumeCapacity(meta);
+
+ self.assertIntegrity();
+ return written.len;
+ }
+
+ /// Only for tests!
+ fn testChangeNeedle(self: *SlidingWindow, new: []const u8) void {
+ assert(new.len == self.needle.len);
+ self.alloc.free(self.needle);
+ self.needle = self.alloc.dupe(u8, new) catch unreachable;
+ }
+
+ fn assertIntegrity(self: *const SlidingWindow) void {
+ if (comptime !std.debug.runtime_safety) return;
+
+ // We don't run integrity checks on Valgrind because its soooooo slow,
+ // Valgrind is our integrity checker, and we run these during unit
+ // tests (non-Valgrind) anyways so we're verifying anyways.
+ if (std.valgrind.runningOnValgrind() > 0) return;
+
+ // Integrity check: verify our data matches our metadata exactly.
+ var meta_it = self.meta.iterator(.forward);
+ var data_len: usize = 0;
+ while (meta_it.next()) |m| data_len += m.cell_map.items.len;
+ assert(data_len == self.data.len());
+
+ // Integrity check: verify our data offset is within bounds.
+ assert(self.data.len() == 0 or self.data_offset < self.data.len());
+ }
+};
+
+test "SlidingWindow empty on init" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "boo!");
+ defer w.deinit();
+ try testing.expectEqual(0, w.data.len());
+ try testing.expectEqual(0, w.meta.len());
+}
+
+test "SlidingWindow single append" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "boo!");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("hello. boo! hello. boo!");
+
+ // We want to test single-page cases.
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+
+ // We should be able to find two matches.
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start));
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 10,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end));
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 19,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start));
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 22,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end));
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow single append case insensitive ASCII" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "Boo!");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("hello. boo! hello. boo!");
+
+ // We want to test single-page cases.
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+
+ // We should be able to find two matches.
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start));
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 10,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end));
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 19,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start));
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 22,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end));
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow single append single char" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "b");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("hello. boo! hello. boo!");
+
+ // We want to test single-page cases.
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+
+ // We should be able to find two matches.
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start));
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end));
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 19,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start));
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 19,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end));
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow single append no match" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "nope!");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("hello. boo! hello. boo!");
+
+ // We want to test single-page cases.
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+
+ // No matches
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+
+ // Should still keep the page
+ try testing.expectEqual(1, w.meta.len());
+}
+
+test "SlidingWindow two pages" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "boo!");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("boo!");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("\n");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+ try s.testWriteString("hello. boo!");
+
+ // Add both pages
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+ _ = try w.append(node.next.?);
+
+ // Search should find two matches
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 76,
+ .y = 22,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 79,
+ .y = 22,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 23,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 10,
+ .y = 23,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow two pages single char" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "b");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("boo!");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("\n");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+ try s.testWriteString("hello. boo!");
+
+ // Add both pages
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+ _ = try w.append(node.next.?);
+
+ // Search should find two matches
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 76,
+ .y = 22,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 76,
+ .y = 22,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 23,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 23,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow two pages match across boundary" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "hello, world");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("hell");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("o, world!");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+
+ // Add both pages
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+ _ = try w.append(node.next.?);
+
+ // Search should find a match
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 76,
+ .y = 22,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 23,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+
+ // We shouldn't prune because we don't have enough space
+ try testing.expectEqual(2, w.meta.len());
+}
+
+test "SlidingWindow two pages no match across boundary with newline" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "hello, world");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("hell");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("\no, world!");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+
+ // Add both pages
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+ _ = try w.append(node.next.?);
+
+ // Search should NOT find a match
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+
+ // We shouldn't prune because we don't have enough space
+ try testing.expectEqual(2, w.meta.len());
+}
+
+test "SlidingWindow two pages no match across boundary with newline reverse" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, "hello, world");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("hell");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("\no, world!");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+
+ // Add both pages in reverse order
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node.next.?);
+ _ = try w.append(node);
+
+ // Search should NOT find a match
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow two pages no match prunes first page" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "nope!");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("boo!");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("\n");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+ try s.testWriteString("hello. boo!");
+
+ // Add both pages
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+ _ = try w.append(node.next.?);
+
+ // Search should find nothing
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+
+ // We should've pruned our page because the second page
+ // has enough text to contain our needle.
+ try testing.expectEqual(1, w.meta.len());
+}
+
+test "SlidingWindow two pages no match keeps both pages" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("boo!");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("\n");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+ try s.testWriteString("hello. boo!");
+
+ // Imaginary needle for search. Doesn't match!
+ var needle_list: std.ArrayList(u8) = .empty;
+ defer needle_list.deinit(alloc);
+ try needle_list.appendNTimes(alloc, 'x', first_page_rows * s.pages.cols);
+ const needle: []const u8 = needle_list.items;
+
+ var w: SlidingWindow = try .init(alloc, .forward, needle);
+ defer w.deinit();
+
+ // Add both pages
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+ _ = try w.append(node.next.?);
+
+ // Search should find nothing
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+
+ // No pruning because both pages are needed to fit needle.
+ try testing.expectEqual(2, w.meta.len());
+}
+
+test "SlidingWindow single append across circular buffer boundary" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "abc");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("XXXXXXXXXXXXXXXXXXXboo!XXXXX");
+
+ // We are trying to break a circular buffer boundary so the way we
+ // do this is to duplicate the data then do a failing search. This
+ // will cause the first page to be pruned. The next time we append we'll
+ // put it in the middle of the circ buffer. We assert this so that if
+ // our implementation changes our test will fail.
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+ _ = try w.append(node);
+ {
+ // No wrap around yet
+ const slices = w.data.getPtrSlice(0, w.data.len());
+ try testing.expect(slices[0].len > 0);
+ try testing.expect(slices[1].len == 0);
+ }
+
+ // Search non-match, prunes page
+ try testing.expect(w.next() == null);
+ try testing.expectEqual(1, w.meta.len());
+
+ // Change the needle, just needs to be the same length (not a real API)
+ w.testChangeNeedle("boo");
+
+ // Add new page, now wraps
+ _ = try w.append(node);
+ {
+ const slices = w.data.getPtrSlice(0, w.data.len());
+ try testing.expect(slices[0].len > 0);
+ try testing.expect(slices[1].len > 0);
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 19,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 21,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow single append match on boundary" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "abcd");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("o!XXXXXXXXXXXXXXXXXXXbo");
+
+ // We need to surgically modify the last row to be soft-wrapped
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ node.data.getRow(node.data.size.rows - 1).wrap = true;
+
+ // We are trying to break a circular buffer boundary so the way we
+ // do this is to duplicate the data then do a failing search. This
+ // will cause the first page to be pruned. The next time we append we'll
+ // put it in the middle of the circ buffer. We assert this so that if
+ // our implementation changes our test will fail.
+ _ = try w.append(node);
+ _ = try w.append(node);
+ {
+ // No wrap around yet
+ const slices = w.data.getPtrSlice(0, w.data.len());
+ try testing.expect(slices[0].len > 0);
+ try testing.expect(slices[1].len == 0);
+ }
+
+ // Search non-match, prunes page
+ try testing.expect(w.next() == null);
+ try testing.expectEqual(1, w.meta.len());
+
+ // Change the needle, just needs to be the same length (not a real API)
+ w.testChangeNeedle("boo!");
+
+ // Add new page, now wraps
+ _ = try w.append(node);
+ {
+ const slices = w.data.getPtrSlice(0, w.data.len());
+ try testing.expect(slices[0].len > 0);
+ try testing.expect(slices[1].len > 0);
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 21,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 1,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow single append reversed" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, "boo!");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("hello. boo! hello. boo!");
+
+ // We want to test single-page cases.
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+
+ // We should be able to find two matches.
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 19,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 22,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 10,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow single append no match reversed" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, "nope!");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("hello. boo! hello. boo!");
+
+ // We want to test single-page cases.
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+
+ // No matches
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+
+ // Should still keep the page
+ try testing.expectEqual(1, w.meta.len());
+}
+
+test "SlidingWindow two pages reversed" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, "boo!");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("boo!");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("\n");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+ try s.testWriteString("hello. boo!");
+
+ // Add both pages in reverse order
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node.next.?);
+ _ = try w.append(node);
+
+ // Search should find two matches (in reverse order)
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 23,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 10,
+ .y = 23,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 76,
+ .y = 22,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 79,
+ .y = 22,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow two pages match across boundary reversed" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, "hello, world");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "hell"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("hell");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("o, world!");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+
+ // Add both pages in reverse order
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node.next.?);
+ _ = try w.append(node);
+
+ // Search should find a match
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 76,
+ .y = 22,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 7,
+ .y = 23,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+
+ // In reverse mode, the last appended meta (first original page) is large
+ // enough to contain needle.len - 1 bytes, so pruning occurs
+ try testing.expectEqual(1, w.meta.len());
+}
+
+test "SlidingWindow two pages no match prunes first page reversed" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, "nope!");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("boo!");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("\n");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+ try s.testWriteString("hello. boo!");
+
+ // Add both pages in reverse order
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node.next.?);
+ _ = try w.append(node);
+
+ // Search should find nothing
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+
+ // We should've pruned our page because the second page
+ // has enough text to contain our needle.
+ try testing.expectEqual(1, w.meta.len());
+}
+
+test "SlidingWindow two pages no match keeps both pages reversed" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 1000 });
+ defer s.deinit();
+
+ // Fill up the first page. The final bytes in the first page
+ // are "boo!"
+ const first_page_rows = s.pages.pages.first.?.data.capacity.rows;
+ for (0..first_page_rows - 1) |_| try s.testWriteString("\n");
+ for (0..s.pages.cols - 4) |_| try s.testWriteString("x");
+ try s.testWriteString("boo!");
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ try s.testWriteString("\n");
+ try testing.expect(s.pages.pages.first != s.pages.pages.last);
+ try s.testWriteString("hello. boo!");
+
+ // Imaginary needle for search. Doesn't match!
+ var needle_list: std.ArrayList(u8) = .empty;
+ defer needle_list.deinit(alloc);
+ try needle_list.appendNTimes(alloc, 'x', first_page_rows * s.pages.cols);
+ const needle: []const u8 = needle_list.items;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, needle);
+ defer w.deinit();
+
+ // Add both pages in reverse order
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node.next.?);
+ _ = try w.append(node);
+
+ // Search should find nothing
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+
+ // No pruning because both pages are needed to fit needle.
+ try testing.expectEqual(2, w.meta.len());
+}
+
+test "SlidingWindow single append across circular buffer boundary reversed" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, "abc");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("XXXXXXXXXXXXXXXXXXXboo!XXXXX");
+
+ // We are trying to break a circular buffer boundary so the way we
+ // do this is to duplicate the data then do a failing search. This
+ // will cause the first page to be pruned. The next time we append we'll
+ // put it in the middle of the circ buffer. We assert this so that if
+ // our implementation changes our test will fail.
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ _ = try w.append(node);
+ _ = try w.append(node);
+ {
+ // No wrap around yet
+ const slices = w.data.getPtrSlice(0, w.data.len());
+ try testing.expect(slices[0].len > 0);
+ try testing.expect(slices[1].len == 0);
+ }
+
+ // Search non-match, prunes page
+ try testing.expect(w.next() == null);
+ try testing.expectEqual(1, w.meta.len());
+
+ // Change the needle, just needs to be the same length (not a real API)
+ // testChangeNeedle doesn't reverse, so pass reversed needle for reverse mode
+ w.testChangeNeedle("oob");
+
+ // Add new page, now wraps
+ _ = try w.append(node);
+ {
+ const slices = w.data.getPtrSlice(0, w.data.len());
+ try testing.expect(slices[0].len > 0);
+ try testing.expect(slices[1].len > 0);
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 19,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 21,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow single append match on boundary reversed" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, "abcd");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
+ defer s.deinit();
+ try s.testWriteString("o!XXXXXXXXXXXXXXXXXXXbo");
+
+ // We need to surgically modify the last row to be soft-wrapped
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ node.data.getRow(node.data.size.rows - 1).wrap = true;
+
+ // We are trying to break a circular buffer boundary so the way we
+ // do this is to duplicate the data then do a failing search. This
+ // will cause the first page to be pruned. The next time we append we'll
+ // put it in the middle of the circ buffer. We assert this so that if
+ // our implementation changes our test will fail.
+ _ = try w.append(node);
+ _ = try w.append(node);
+ {
+ // No wrap around yet
+ const slices = w.data.getPtrSlice(0, w.data.len());
+ try testing.expect(slices[0].len > 0);
+ try testing.expect(slices[1].len == 0);
+ }
+
+ // Search non-match, prunes page
+ try testing.expect(w.next() == null);
+ try testing.expectEqual(1, w.meta.len());
+
+ // Change the needle, just needs to be the same length (not a real API)
+ // testChangeNeedle doesn't reverse, so pass reversed needle for reverse mode
+ w.testChangeNeedle("!oob");
+
+ // Add new page, now wraps
+ _ = try w.append(node);
+ {
+ const slices = w.data.getPtrSlice(0, w.data.len());
+ try testing.expect(slices[0].len > 0);
+ try testing.expect(slices[1].len > 0);
+ }
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 21,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 1,
+ .y = 0,
+ } }, s.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow single append soft wrapped" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "boo!");
+ defer w.deinit();
+
+ var t: Terminal = try .init(alloc, .{ .cols = 4, .rows = 5 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("A\r\nxxboo!\r\nC");
+
+ // We want to test single-page cases.
+ const screen = t.screens.active;
+ try testing.expect(screen.pages.pages.first == screen.pages.pages.last);
+ const node: *PageList.List.Node = screen.pages.pages.first.?;
+ _ = try w.append(node);
+
+ // We should be able to find two matches.
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 2,
+ .y = 1,
+ } }, screen.pages.pointFromPin(.active, sel.start));
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 1,
+ .y = 2,
+ } }, screen.pages.pointFromPin(.active, sel.end));
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+test "SlidingWindow single append reversed soft wrapped" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .reverse, "boo!");
+ defer w.deinit();
+
+ var t: Terminal = try .init(alloc, .{ .cols = 4, .rows = 5 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("A\r\nxxboo!\r\nC");
+
+ // We want to test single-page cases.
+ const screen = t.screens.active;
+ try testing.expect(screen.pages.pages.first == screen.pages.pages.last);
+ const node: *PageList.List.Node = screen.pages.pages.first.?;
+ _ = try w.append(node);
+
+ // We should be able to find two matches.
+ {
+ const h = w.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 2,
+ .y = 1,
+ } }, screen.pages.pointFromPin(.active, sel.start));
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 1,
+ .y = 2,
+ } }, screen.pages.pointFromPin(.active, sel.end));
+ }
+ try testing.expect(w.next() == null);
+ try testing.expect(w.next() == null);
+}
+
+// This tests a real bug that occurred where a whitespace-only page
+// that encodes to zero bytes would crash.
+test "SlidingWindow append whitespace only node" {
+ const testing = std.testing;
+ const alloc = testing.allocator;
+
+ var w: SlidingWindow = try .init(alloc, .forward, "x");
+ defer w.deinit();
+
+ var s = try Screen.init(alloc, .{
+ .cols = 80,
+ .rows = 24,
+ .max_scrollback = 0,
+ });
+ defer s.deinit();
+
+ // By setting the empty page to wrap we get a zero-byte page.
+ // This is invasive but its otherwise hard to reproduce naturally
+ // without creating a slow test.
+ const node: *PageList.List.Node = s.pages.pages.first.?;
+ const last_row = node.data.getRow(node.data.size.rows - 1);
+ last_row.wrap = true;
+
+ try testing.expect(s.pages.pages.first == s.pages.pages.last);
+ _ = try w.append(node);
+
+ // No matches expected
+ try testing.expect(w.next() == null);
+}
diff --git a/vendor/libghostty-vt/src/terminal/search/viewport.zig b/vendor/libghostty-vt/src/terminal/search/viewport.zig
new file mode 100644
index 00000000..35dd9331
--- /dev/null
+++ b/vendor/libghostty-vt/src/terminal/search/viewport.zig
@@ -0,0 +1,384 @@
+const std = @import("std");
+const assert = @import("../../quirks.zig").inlineAssert;
+const testing = std.testing;
+const Allocator = std.mem.Allocator;
+const point = @import("../point.zig");
+const size = @import("../size.zig");
+const FlattenedHighlight = @import("../highlight.zig").Flattened;
+const PageList = @import("../PageList.zig");
+const SlidingWindow = @import("sliding_window.zig").SlidingWindow;
+const Terminal = @import("../Terminal.zig");
+
+/// Searches for a substring within the viewport of a PageList.
+///
+/// This contains logic to efficiently detect when the viewport changes
+/// and only re-search when necessary.
+///
+/// The specialization for "viewport" is because the viewport is the
+/// only part of the search where the user can actively see the results,
+/// usually. In that case, it is more efficient to re-search only the
+/// viewport rather than store all the results for the entire screen.
+///
+/// Note that this searches all the pages that viewport covers, so
+/// this can include extra matches outside the viewport if the data
+/// lives in the same page.
+pub const ViewportSearch = struct {
+ window: SlidingWindow,
+ fingerprint: ?Fingerprint,
+
+ /// If this is null, then active dirty tracking is disabled and if the
+ /// viewport overlaps the active area we always re-search. If this is
+ /// non-null, then we only re-search if the active area is dirty. Dirty
+ /// marking is up to the caller.
+ active_dirty: ?bool,
+
+ pub fn init(
+ alloc: Allocator,
+ needle_unowned: []const u8,
+ ) Allocator.Error!ViewportSearch {
+ // We just do a forward search since the viewport is usually
+ // pretty small so search results are instant anyways. This avoids
+ // a small amount of work to reverse things.
+ var window: SlidingWindow = try .init(alloc, .forward, needle_unowned);
+ errdefer window.deinit();
+ return .{
+ .window = window,
+ .fingerprint = null,
+ .active_dirty = null,
+ };
+ }
+
+ pub fn deinit(self: *ViewportSearch) void {
+ if (self.fingerprint) |*fp| fp.deinit(self.window.alloc);
+ self.window.deinit();
+ }
+
+ /// Reset our fingerprint and results so that the next update will
+ /// always re-search.
+ pub fn reset(self: *ViewportSearch) void {
+ if (self.fingerprint) |*fp| fp.deinit(self.window.alloc);
+ self.fingerprint = null;
+ self.window.clearAndRetainCapacity();
+ }
+
+ /// The needle that this search is using.
+ pub fn needle(self: *const ViewportSearch) []const u8 {
+ assert(self.window.direction == .forward);
+ return self.window.needle;
+ }
+
+ /// Update the sliding window to reflect the current viewport. This
+ /// will do nothing if the viewport hasn't changed since the last
+ /// search.
+ ///
+ /// The PageList must be safe to read throughout the lifetime of this
+ /// function.
+ ///
+ /// Returns true if the viewport changed and a re-search is needed.
+ /// Returns false if the viewport is unchanged.
+ pub fn update(
+ self: *ViewportSearch,
+ list: *PageList,
+ ) Allocator.Error!bool {
+ // See if our viewport changed
+ var fingerprint: Fingerprint = try .init(self.window.alloc, list);
+ if (self.fingerprint) |*old| {
+ if (old.eql(fingerprint)) match: {
+ // Determine if we need to check if we overlap the active
+ // area. If we have dirty tracking on we also set it to
+ // false here.
+ const check_active: bool = active: {
+ const dirty = self.active_dirty orelse break :active true;
+ if (!dirty) break :active false;
+ self.active_dirty = false;
+ break :active true;
+ };
+
+ if (check_active) {
+ // If our fingerprint contains the active area, then we always
+ // re-search since the active area is mutable.
+ const active_tl = list.getTopLeft(.active);
+ const active_br = list.getBottomRight(.active).?;
+
+ // If our viewport contains the start or end of the active area,
+ // we are in the active area. We purposely do this first
+ // because our viewport is always larger than the active area.
+ for (old.nodes) |node| {
+ if (node == active_tl.node) break :match;
+ if (node == active_br.node) break :match;
+ }
+ }
+
+ // No change
+ fingerprint.deinit(self.window.alloc);
+ return false;
+ }
+
+ old.deinit(self.window.alloc);
+ self.fingerprint = null;
+ }
+ assert(self.fingerprint == null);
+ self.fingerprint = fingerprint;
+ errdefer {
+ fingerprint.deinit(self.window.alloc);
+ self.fingerprint = null;
+ }
+
+ // If our active area was set as dirty, we always unset it here
+ // because we're re-searching now.
+ if (self.active_dirty) |*v| v.* = false;
+
+ // Clear our previous sliding window
+ self.window.clearAndRetainCapacity();
+
+ // Add enough overlap to cover needle.len - 1 bytes (if it
+ // exists) so we can cover the overlap. We only do this for the
+ // soft-wrapped prior pages.
+ var node_ = fingerprint.nodes[0].prev;
+ var added: usize = 0;
+ while (node_) |node| : (node_ = node.prev) {
+ // If the last row of this node isn't wrapped we can't overlap.
+ const row = node.data.getRow(node.data.size.rows - 1);
+ if (!row.wrap) break;
+
+ // We could be more accurate here and count bytes since the
+ // last wrap but its complicated and unlikely multiple pages
+ // wrap so this should be fine.
+ added += try self.window.append(node);
+ if (added >= self.window.needle.len - 1) break;
+ }
+
+ // We can use our fingerprint nodes to initialize our sliding
+ // window, since we already traversed the viewport once.
+ for (fingerprint.nodes) |node| {
+ _ = try self.window.append(node);
+ }
+
+ // Add any trailing overlap as well.
+ trailing: {
+ const end: *PageList.List.Node = fingerprint.nodes[fingerprint.nodes.len - 1];
+ if (!end.data.getRow(end.data.size.rows - 1).wrap) break :trailing;
+
+ node_ = end.next;
+ added = 0;
+ while (node_) |node| : (node_ = node.next) {
+ added += try self.window.append(node);
+ if (added >= self.window.needle.len - 1) break;
+
+ // If this row doesn't wrap, then we can quit
+ const row = node.data.getRow(node.data.size.rows - 1);
+ if (!row.wrap) break;
+ }
+ }
+
+ return true;
+ }
+
+ /// Find the next match for the needle in the active area. This returns
+ /// null when there are no more matches.
+ pub fn next(self: *ViewportSearch) ?FlattenedHighlight {
+ return self.window.next();
+ }
+
+ /// Viewport fingerprint so we can detect when the viewport moves.
+ const Fingerprint = struct {
+ /// The nodes that make up the viewport. We need to flatten this
+ /// to a single list because we can't safely traverse the cached values
+ /// because the page nodes may be invalid. All that is safe is comparing
+ /// the actual pointer values.
+ nodes: []const *PageList.List.Node,
+
+ pub fn init(alloc: Allocator, pages: *PageList) Allocator.Error!Fingerprint {
+ var list: std.ArrayList(*PageList.List.Node) = .empty;
+ defer list.deinit(alloc);
+
+ // Get our viewport area. Bottom right of a viewport can never
+ // fail.
+ const tl = pages.getTopLeft(.viewport);
+ const br = pages.getBottomRight(.viewport).?;
+
+ var it = tl.pageIterator(.right_down, br);
+ while (it.next()) |chunk| try list.append(alloc, chunk.node);
+ return .{ .nodes = try list.toOwnedSlice(alloc) };
+ }
+
+ pub fn deinit(self: *Fingerprint, alloc: Allocator) void {
+ alloc.free(self.nodes);
+ }
+
+ pub fn eql(self: Fingerprint, other: Fingerprint) bool {
+ if (self.nodes.len != other.nodes.len) return false;
+ for (self.nodes, other.nodes) |a, b| {
+ if (a != b) return false;
+ }
+ return true;
+ }
+ };
+};
+
+test "simple search" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ViewportSearch = try .init(alloc, "Fizz");
+ defer search.deinit();
+ try testing.expect(try search.update(&t.screens.active.pages));
+
+ // Viewport contains active so update should always re-search.
+ try testing.expect(try search.update(&t.screens.active.pages));
+
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 2,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(search.next() == null);
+}
+
+test "clear screen and search" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ViewportSearch = try .init(alloc, "Fizz");
+ defer search.deinit();
+ try testing.expect(try search.update(&t.screens.active.pages));
+
+ s.nextSlice("\x1b[2J"); // Clear screen
+ s.nextSlice("\x1b[H"); // Move cursor home
+ s.nextSlice("Buzz\r\nFizz\r\nBuzz");
+ try testing.expect(try search.update(&t.screens.active.pages));
+
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(search.next() == null);
+}
+
+test "clear screen and search dirty tracking" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+ s.nextSlice("Fizz\r\nBuzz\r\nFizz\r\nBang");
+
+ var search: ViewportSearch = try .init(alloc, "Fizz");
+ defer search.deinit();
+
+ // Turn on dirty tracking
+ search.active_dirty = false;
+
+ // Should update since we've never searched before
+ try testing.expect(try search.update(&t.screens.active.pages));
+
+ // Should not update since nothing changed
+ try testing.expect(!try search.update(&t.screens.active.pages));
+
+ s.nextSlice("\x1b[2J"); // Clear screen
+ s.nextSlice("\x1b[H"); // Move cursor home
+ s.nextSlice("Buzz\r\nFizz\r\nBuzz");
+
+ // Should still not update since active area isn't dirty
+ try testing.expect(!try search.update(&t.screens.active.pages));
+
+ // Mark
+ search.active_dirty = true;
+ try testing.expect(try search.update(&t.screens.active.pages));
+
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 0,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.start).?);
+ try testing.expectEqual(point.Point{ .active = .{
+ .x = 3,
+ .y = 1,
+ } }, t.screens.active.pages.pointFromPin(.active, sel.end).?);
+ }
+ try testing.expect(search.next() == null);
+}
+
+test "history search, no active area" {
+ const alloc = testing.allocator;
+ var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 2 });
+ defer t.deinit(alloc);
+
+ var s = t.vtStream();
+ defer s.deinit();
+
+ // Fill up first page
+ const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows;
+ s.nextSlice("Fizz\r\n");
+ for (1..first_page_rows - 1) |_| s.nextSlice("\r\n");
+ try testing.expect(t.screens.active.pages.pages.first == t.screens.active.pages.pages.last);
+
+ // Create second page
+ s.nextSlice("\r\n");
+ try testing.expect(t.screens.active.pages.pages.first != t.screens.active.pages.pages.last);
+ s.nextSlice("Buzz\r\nFizz");
+
+ t.scrollViewport(.top);
+
+ var search: ViewportSearch = try .init(alloc, "Fizz");
+ defer search.deinit();
+ try testing.expect(try search.update(&t.screens.active.pages));
+
+ {
+ const h = search.next().?;
+ const sel = h.untracked();
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 0,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.start).?);
+ try testing.expectEqual(point.Point{ .screen = .{
+ .x = 3,
+ .y = 0,
+ } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?);
+ }
+ try testing.expect(search.next() == null);
+
+ // Viewport doesn't contain active
+ try testing.expect(!try search.update(&t.screens.active.pages));
+ try testing.expect(search.next() == null);
+}