diff options
| author | Can Celik <ogulcancelik@gmail.com> | 2026-04-04 19:22:04 +0300 |
|---|---|---|
| committer | Can Celik <ogulcancelik@gmail.com> | 2026-04-05 01:23:06 +0300 |
| commit | 41dd733ca7123c9ac4bfc6c781697a660e95b052 (patch) | |
| tree | 3fc91815ca139ef2e0b281bba0abda4ef15175f4 /vendor/libghostty-vt/src/terminal/search | |
| parent | 55c138263e190a1e79d4b997bfb9397306c0ec1f (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.zig | 905 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/active.zig | 175 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/pagelist.zig | 441 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/screen.zig | 1552 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/sliding_window.zig | 1676 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/viewport.zig | 384 |
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); +} |
