diff options
| author | Ogulcan Celik <ogulcancelik@gmail.com> | 2026-07-16 23:28:05 +0300 |
|---|---|---|
| committer | Ogulcan Celik <ogulcancelik@gmail.com> | 2026-07-16 23:29:28 +0300 |
| commit | 4a3302d19a2baa3a33e910e0088c24e780905b90 (patch) | |
| tree | dcaf76fae1c82102d933c9225b17ca7ac5d3a847 /vendor/libghostty-vt/src/terminal/search | |
| parent | 550e9f8cc085f428429f5cf2da0bb2dba897e8b8 (diff) | |
chore: update vendored libghostty-vt
refs #276
Diffstat (limited to 'vendor/libghostty-vt/src/terminal/search')
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/Thread.zig | 100 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/active.zig | 16 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/pagelist.zig | 129 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/screen.zig | 482 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/sliding_window.zig | 143 | ||||
| -rw-r--r-- | vendor/libghostty-vt/src/terminal/search/viewport.zig | 229 |
6 files changed, 921 insertions, 178 deletions
diff --git a/vendor/libghostty-vt/src/terminal/search/Thread.zig b/vendor/libghostty-vt/src/terminal/search/Thread.zig index fa09af5f..d7f0d562 100644 --- a/vendor/libghostty-vt/src/terminal/search/Thread.zig +++ b/vendor/libghostty-vt/src/terminal/search/Thread.zig @@ -121,7 +121,11 @@ pub fn deinit(self: *Thread) void { // Nothing can possibly access the mailbox anymore, destroy it. self.mailbox.destroy(self.alloc); - if (self.search) |*s| s.deinit(); + if (self.search) |*s| { + self.opts.mutex.lock(); + defer self.opts.mutex.unlock(); + s.deinit(self.opts.terminal); + } } /// The main entrypoint for the thread. @@ -252,11 +256,15 @@ fn drainMailbox(self: *Thread) !void { 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(); + // A screen can be removed or replaced between refresh ticks. Reconcile + // while holding the terminal lock before touching any ScreenSearch pins. + s.feed(self.alloc, self.opts.terminal); + const screen_search = s.screens.getPtr(s.last_screen.key) orelse return; + // Make the selection. Ignore the result because we don't // care if the selection didn't change. _ = try screen_search.select(sel); @@ -308,7 +316,11 @@ fn changeNeedle(self: *Thread, needle: []const u8) !void { // If our search is unchanged, do nothing. if (std.ascii.eqlIgnoreCase(s.viewport.needle(), needle)) return; - s.deinit(); + { + self.opts.mutex.lock(); + defer self.opts.mutex.unlock(); + s.deinit(self.opts.terminal); + } self.search = null; // When the search changes then we need to emit that it stopped. @@ -497,6 +509,11 @@ const Search = struct { /// The searchers for all the screens. screens: std.EnumMap(ScreenSet.Key, ScreenSearch), + /// ScreenSet generations captured when each searcher was initialized. + /// Allocators may reuse a destroyed Screen address, so pointer equality + /// alone cannot distinguish replacement screens from stale handles. + screen_generations: std.EnumMap(ScreenSet.Key, usize), + /// All state related to screen switches, collected so that when /// we switch screens it makes everything related stale, too. last_screen: ScreenState, @@ -537,16 +554,35 @@ const Search = struct { return .{ .viewport = vp, .screens = .init(.{}), + .screen_generations = .init(.{}), .last_screen = .{ .key = .primary }, .last_complete = false, .stale_viewport_matches = true, }; } - pub fn deinit(self: *Search) void { + pub fn deinit(self: *Search, t: *Terminal) void { self.viewport.deinit(); var it = self.screens.iterator(); - while (it.next()) |entry| entry.value.deinit(); + while (it.next()) |entry| { + if (self.screenIsValid(&t.screens, entry.key, entry.value)) { + entry.value.deinit(); + } else { + entry.value.deinitScreenInvalid(); + } + } + } + + fn screenIsValid( + self: *const Search, + screens: *const ScreenSet, + key: ScreenSet.Key, + search: *const ScreenSearch, + ) bool { + const generation = self.screen_generations.get(key) orelse return false; + if (generation != screens.generation(key)) return false; + const actual = screens.get(key) orelse return false; + return actual == search.screen; } /// Returns true if all searches on all screens are complete. @@ -629,18 +665,16 @@ const Search = struct { // 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; - }; + const remove = !self.screenIsValid( + &t.screens, + entry.key, + entry.value, + ); if (remove) { - entry.value.deinit(); + entry.value.deinitScreenInvalid(); _ = self.screens.remove(entry.key); + _ = self.screen_generations.remove(entry.key); } } } @@ -649,7 +683,7 @@ const Search = struct { var it = t.screens.all.iterator(); while (it.next()) |entry| { if (self.screens.contains(entry.key)) continue; - self.screens.put(entry.key, ScreenSearch.init( + const screen_search = ScreenSearch.init( alloc, entry.value.*, self.viewport.needle(), @@ -664,7 +698,12 @@ const Search = struct { ); continue; }, - }); + }; + self.screens.put(entry.key, screen_search); + self.screen_generations.put( + entry.key, + t.screens.generation(entry.key), + ); } } @@ -903,3 +942,32 @@ test { } }, t.screens.active.pages.pointFromPin(.screen, sel.end).?); } } + +test "select after active screen removal" { + const alloc = testing.allocator; + var mutex: std.Thread.Mutex = .{}; + var t: Terminal = try .init(alloc, .{ .cols = 20, .rows = 2 }); + defer t.deinit(alloc); + + _ = try t.switchScreen(.alternate); + + var search: Search = try .init(alloc, "needle"); + search.feed(alloc, &t); + try testing.expectEqual(ScreenSet.Key.alternate, search.last_screen.key); + try testing.expect(search.screens.contains(.alternate)); + + var thread: Thread = undefined; + thread.search = search; + thread.opts = .{ + .mutex = &mutex, + .terminal = &t, + }; + defer if (thread.search) |*active| active.deinit(&t); + + _ = try t.switchScreen(.primary); + t.screens.remove(alloc, .alternate); + + try thread.select(.next); + try testing.expectEqual(ScreenSet.Key.primary, thread.search.?.last_screen.key); + try testing.expect(!thread.search.?.screens.contains(.alternate)); +} diff --git a/vendor/libghostty-vt/src/terminal/search/active.zig b/vendor/libghostty-vt/src/terminal/search/active.zig index 692a10e1..b99b2357 100644 --- a/vendor/libghostty-vt/src/terminal/search/active.zig +++ b/vendor/libghostty-vt/src/terminal/search/active.zig @@ -56,6 +56,10 @@ pub const ActiveSearch = struct { // Clear our previous sliding window self.window.clearAndRetainCapacity(); + // An empty needle represents an inactive search and has no overlap + // or history to load. + if (self.window.needle.len == 0) return null; + // First up, add enough pages to cover the active area. var rem: usize = list.rows; var node_ = list.pages.last; @@ -68,26 +72,22 @@ pub const ActiveSearch = struct { // 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) { + if (rem <= node.rows()) { node_ = node.prev; break; } - rem -= node.data.size.rows; + rem -= node.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; + const appended = try self.window.appendIfWrapped(node) orelse break; + if (appended.content_len >= self.window.needle.len - 1) break; } // Return the last node we added to our window. diff --git a/vendor/libghostty-vt/src/terminal/search/pagelist.zig b/vendor/libghostty-vt/src/terminal/search/pagelist.zig index f76ad4e4..98a24c18 100644 --- a/vendor/libghostty-vt/src/terminal/search/pagelist.zig +++ b/vendor/libghostty-vt/src/terminal/search/pagelist.zig @@ -3,6 +3,7 @@ const Allocator = std.mem.Allocator; const testing = std.testing; const terminal = @import("../main.zig"); const point = terminal.point; +const size = terminal.size; const FlattenedHighlight = @import("../highlight.zig").Flattened; const Page = terminal.Page; const PageList = terminal.PageList; @@ -56,8 +57,8 @@ pub const PageListSearch = struct { // be moved somewhere safe. const pin = try list.trackPin(.{ .node = start, - .y = start.data.size.rows - 1, - .x = start.data.size.cols - 1, + .y = start.rows() - 1, + .x = start.cols() - 1, }); errdefer list.untrackPin(pin); @@ -84,6 +85,13 @@ pub const PageListSearch = struct { self.list.untrackPin(self.pin); } + /// Release owned search buffers after the PageList itself has already + /// been destroyed. Its pin belonged to the PageList pool and was freed + /// with that list, so it must not be untracked here. + pub fn deinitListInvalid(self: *PageListSearch) void { + self.window.deinit(); + } + /// 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. @@ -121,10 +129,13 @@ pub const PageListSearch = struct { // 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); + rem -|= (try self.window.append(node)).content_len; // Move our tracked pin to the new node. self.pin.node = node; + self.pin.y = node.rows() - 1; + self.pin.x = node.cols() - 1; + self.pin.garbage = false; if (rem == 0) break; } @@ -190,7 +201,7 @@ test "feed multiple pages with matches" { defer s.deinit(); // Fill up first page - const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows; + const first_page_rows = t.screens.active.pages.pages.first.?.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); @@ -234,7 +245,7 @@ test "feed multiple pages no matches" { defer s.deinit(); // Fill up first page - const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows; + const first_page_rows = t.screens.active.pages.pages.first.?.capacity().rows; for (0..first_page_rows - 1) |_| s.nextSlice("\r\n"); s.nextSlice("Hello"); @@ -272,7 +283,7 @@ test "feed iteratively through multiple matches" { var s = t.vtStream(); defer s.deinit(); - const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows; + const first_page_rows = t.screens.active.pages.pages.first.?.capacity().rows; // Fill first page with a match at the end for (0..first_page_rows - 1) |_| s.nextSlice("\r\n"); @@ -313,7 +324,7 @@ test "feed with match spanning page boundary" { var s = t.vtStream(); defer s.deinit(); - const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows; + const first_page_rows = t.screens.active.pages.pages.first.?.capacity().rows; // Fill first page ending with "Te" for (0..first_page_rows - 1) |_| s.nextSlice("\r\n"); @@ -359,6 +370,76 @@ test "feed with match spanning page boundary" { try testing.expect(!try search.feed()); } +test "compressed history match spanning page boundary remains compressed" { + const alloc = testing.allocator; + var t: Terminal = try .init(alloc, .{ + .cols = 80, + .rows = 24, + .max_scrollback = 10 * 1024 * 1024, + }); + defer t.deinit(alloc); + + var stream = t.vtStream(); + defer stream.deinit(); + + const pages = &t.screens.active.pages; + const first = pages.pages.first.?; + const first_page_rows = first.capacity().rows; + + // Put half the needle on either side of a soft-wrapped page boundary. + for (0..first_page_rows - 1) |_| stream.nextSlice("\r\n"); + for (0..pages.cols - 2) |_| stream.nextSlice("x"); + stream.nextSlice("Test"); + const second = first.next.?; + try testing.expectEqual(second, pages.pages.last.?); + + // Move both matching pages completely into history. The third page holds + // the active area, making the first two eligible for compression. + while (pages.pages.last.? == second) stream.nextSlice("\r\n"); + for (0..pages.rows) |_| stream.nextSlice("\r\n"); + try testing.expect(pages.getTopLeft(.active).node != second); + + _ = pages.compress(.full); + try testing.expectEqual(PageList.List.Node.Storage.compressed, first.storage()); + try testing.expectEqual(PageList.List.Node.Storage.compressed, second.storage()); + const compressed = pages.memoryStats(); + try testing.expect(compressed.compressed_pages >= 2); + + var search: PageListSearch = try .init( + alloc, + "Test", + pages, + pages.pages.last.?, + ); + defer search.deinit(); + + // Drain and feed incrementally until the boundary match is available. The + // exact number of feeds depends on how much blank-page text the formatter + // trims, so bound progress by the number of pages rather than encoding + // that implementation detail in the test. + var found: ?FlattenedHighlight = null; + for (0..pages.totalPages() + 1) |_| { + if (search.next()) |match| { + found = match; + break; + } + if (!try search.feed()) break; + } + try testing.expect(found != null); + + const match = found.?.untracked(); + try testing.expectEqual(first, match.start.node); + try testing.expectEqual(second, match.end.node); + try testing.expectEqual(@as(size.CellCountInt, pages.cols - 2), match.start.x); + try testing.expectEqual(@as(size.CellCountInt, 1), match.end.x); + + // Search owns formatted text and coordinate maps, not page snapshots. The + // original raw mappings therefore remain discarded after matching. + try testing.expectEqual(compressed, pages.memoryStats()); + try testing.expectEqual(PageList.List.Node.Storage.compressed, first.storage()); + try testing.expectEqual(PageList.List.Node.Storage.compressed, second.storage()); +} + test "feed with match spanning page boundary with newline" { const alloc = testing.allocator; var t: Terminal = try .init(alloc, .{ .cols = 80, .rows = 24 }); @@ -367,7 +448,7 @@ test "feed with match spanning page boundary with newline" { var s = t.vtStream(); defer s.deinit(); - const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows; + const first_page_rows = t.screens.active.pages.pages.first.?.capacity().rows; // Fill first page ending with "Te" for (0..first_page_rows - 1) |_| s.nextSlice("\r\n"); @@ -404,14 +485,14 @@ test "feed with pruned page" { // Grow to capacity const page1_node = p.pages.last.?; - const page1 = page1_node.data; + const page1 = page1_node.page(); 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; + const page2 = page2_node.page(); for (0..page2.capacity.rows - page2.size.rows) |_| { try testing.expect(try p.grow() == null); } @@ -439,3 +520,31 @@ test "feed with pruned page" { // Feed should still do nothing try testing.expect(!try search.feed()); } + +test "feed keeps its tracked pin within a shorter page" { + const alloc = testing.allocator; + var pages: PageList = try .init(alloc, 10, 2, null); + defer pages.deinit(); + + const first = pages.pages.first.?; + while (first.rows() < first.capacity().rows) _ = try pages.grow(); + + const second = (try pages.grow()).?; + while (second.rows() < second.capacity().rows) _ = try pages.grow(); + + try pages.split(.{ .node = first, .y = 1, .x = 0 }); + const shorter = first.next.?; + try testing.expect(shorter.rows() < second.rows()); + + var search: PageListSearch = try .init( + alloc, + "x", + &pages, + second, + ); + defer search.deinit(); + + try testing.expect(try search.feed()); + try testing.expectEqual(shorter, search.pin.node); + try testing.expect(pages.pinIsValid(search.pin.*)); +} diff --git a/vendor/libghostty-vt/src/terminal/search/screen.zig b/vendor/libghostty-vt/src/terminal/search/screen.zig index 3e7e316f..e0cd9911 100644 --- a/vendor/libghostty-vt/src/terminal/search/screen.zig +++ b/vendor/libghostty-vt/src/terminal/search/screen.zig @@ -157,10 +157,29 @@ pub const ScreenSearch = struct { } pub fn deinit(self: *ScreenSearch) void { + self.deinitInternal(true); + } + + /// Release owned search state after the underlying Screen has already + /// been destroyed. Tracked pins belonged to that Screen's PageList pool + /// and were freed with it, so only independently owned memory is freed. + pub fn deinitScreenInvalid(self: *ScreenSearch) void { + self.deinitInternal(false); + } + + fn deinitInternal(self: *ScreenSearch, screen_valid: bool) void { const alloc = self.allocator(); self.active.deinit(); - if (self.history) |*h| h.deinit(self.screen); - if (self.selected) |*m| m.deinit(self.screen); + if (self.history) |*h| { + if (screen_valid) { + h.deinit(self.screen); + } else { + h.searcher.deinitListInvalid(); + } + } + if (screen_valid) { + 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); @@ -182,6 +201,33 @@ pub const ScreenSearch = struct { return self.active_results.items.len + self.history_results.items.len; } + /// Reinitialize cached search state after a screen resize. Reflow can + /// replace every PageList node, so even flattened highlights that weren't + /// selected contain invalid node pointers once either dimension changes. + /// + /// Returns true when the reset occurred. The replacement search has + /// already loaded its active area through `init` in that case. + fn resetIfDimensionsChanged(self: *ScreenSearch) Allocator.Error!bool { + if (self.screen.pages.rows == self.rows and + self.screen.pages.cols == self.cols) + { + return false; + } + + const new: ScreenSearch = try .init( + self.allocator(), + self.screen, + self.needle(), + ); + + self.deinit(); + self.* = new; + + assert(self.screen.pages.rows == self.rows); + assert(self.screen.pages.cols == self.cols); + return true; + } + /// 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). @@ -260,28 +306,9 @@ pub const ScreenSearch = struct { /// 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); - } + // Resize/reflow invalidates every flattened result, not just search + // state that needs another history feed. + _ = try self.resetIfDimensionsChanged(); const history: *PageListSearch = if (self.history) |*h| &h.searcher else { // No history to feed, search is complete. @@ -317,22 +344,88 @@ pub const ScreenSearch = struct { } } + fn historyResultIsValid( + self: *const ScreenSearch, + hl: *const FlattenedHighlight, + ) bool { + const chunks = hl.chunks.slice(); + const nodes = chunks.items(.node); + const serials = chunks.items(.serial); + for (nodes, serials) |node, serial| { + if (!self.screen.pages.nodeIsValid(node, serial)) return false; + } + + return true; + } + + /// Clear a selected history match if its flattened page coordinates are + /// stale. reloadActive only inspects the selected history result, so this + /// avoids validating every cached result on each active-area refresh. + fn validateSelectedHistory(self: *ScreenSearch) void { + const m = if (self.selected) |*m| m else return; + const active_len = self.active_results.items.len; + if (m.idx < active_len) return; + + const history_idx = m.idx - active_len; + if (history_idx < self.history_results.items.len and + self.historyResultIsValid(&self.history_results.items[history_idx])) + { + return; + } + + m.deinit(self.screen); + self.selected = null; + } + 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| { + // any result that contains an invalid serial. + var i: usize = 0; + while (i < self.history_results.items.len) { 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 chunks = hl.chunks.slice(); + const serials = chunks.items(.serial); + const first_serial = serials[0]; + if (first_serial < self.screen.pages.page_serial_epoch) { + // Only a whole-list reset advances the epoch. Results are + // newest to oldest, so this result and the entire remaining + // suffix predate that reset. Drop them without scanning the + // live page list for every captured chunk. const alloc = self.allocator(); + if (self.selected) |*m| { + const first_pruned = self.active_results.items.len + i; + if (m.idx >= first_pruned) { + m.deinit(self.screen); + self.selected = null; + } + } for (self.history_results.items[i..]) |*prune_hl| prune_hl.deinit(alloc); self.history_results.shrinkAndFree(alloc, i); return; } + + // Ordinary pruning, layout changes, and replacements do not + // advance the epoch. Validate their pointer-plus-generation pairs + // against the live list. + if (self.historyResultIsValid(hl)) { + i += 1; + continue; + } + + // Only this result is known to be invalid. Older results may live + // on unrelated pages and remain usable, so remove it individually. + const result_idx = self.active_results.items.len + i; + if (self.selected) |*m| { + if (m.idx == result_idx) { + m.deinit(self.screen); + self.selected = null; + } else if (m.idx > result_idx) { + m.idx -= 1; + } + } + + var removed = self.history_results.orderedRemove(i); + removed.deinit(self.allocator()); } } @@ -392,6 +485,14 @@ pub const ScreenSearch = struct { /// /// The caller must hold the necessary locks to access the screen state. pub fn reloadActive(self: *ScreenSearch) Allocator.Error!void { + // This check must precede all inspection of cached highlights and + // searchers: column reflow may have freed every node they reference. + if (try self.resetIfDimensionsChanged()) return; + + // reloadActive only inspects the selected history result, so validate + // that result without scanning every cached match on this hot path. + self.validateSelectedHistory(); + const tw = reloadActive_tw; // If our selection pin became garbage it means we scrolled off @@ -696,9 +797,14 @@ pub const ScreenSearch = struct { /// 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. + // A resize can replace any page node, including nodes retained by + // flattened history results. Reset before reloadActive or tracking a + // selected result so no pre-resize pointer is ever dereferenced. + _ = try self.resetIfDimensionsChanged(); + + // Reload validates the selected history result before inspecting its + // cached coordinates. Prune the remaining results afterward so every + // candidate is valid before selection tracks it. try self.reloadActive(); self.pruneHistory(); @@ -798,7 +904,7 @@ pub const ScreenSearch = struct { 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 next_idx = if (prev.idx != 0) prev.idx - 1 else active_len + history_len - 1; const hl: FlattenedHighlight = if (next_idx < active_len) self.active_results.items[active_len - 1 - next_idx] @@ -1090,6 +1196,40 @@ test "select next" { } } +test "select after resize resets stale flattened results" { + const alloc = testing.allocator; + var t: Terminal = try .init(alloc, .{ + .cols = 10, + .rows = 3, + .max_scrollback = std.math.maxInt(usize), + }); + defer t.deinit(alloc); + + var stream = t.vtStream(); + defer stream.deinit(); + stream.nextSlice("Fizz\r\nBuzz"); + + var search: ScreenSearch = try .init(alloc, t.screens.active, "Fizz"); + defer search.deinit(); + try search.searchAll(); + try testing.expect(try search.select(.next)); + try testing.expect(search.selectedMatch() != null); + try testing.expectEqual(@as(size.CellCountInt, 10), search.cols); + + // Column reflow replaces the nodes referenced by the cached flattened + // active result. select() calls reloadActive(), so dimension invalidation + // must run before either path dereferences those old nodes. + try t.screens.active.pages.resize(.{ .cols = 5 }); + try testing.expectEqual(@as(size.CellCountInt, 10), search.cols); + + try testing.expect(try search.select(.next)); + try testing.expectEqual(@as(size.CellCountInt, 5), search.cols); + + const selected = search.selectedMatch().?.untracked(); + try testing.expectEqual(@as(size.CellCountInt, 5), selected.start.node.cols()); + try testing.expectEqual(@as(size.CellCountInt, 5), selected.end.node.cols()); +} + test "select in active changes contents completely" { const alloc = testing.allocator; var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 5 }); @@ -1380,6 +1520,276 @@ test "select prev with history" { } } +test "select prev wraps when all matches are in history" { + // Regression test: when every match is in scrollback (the active area + // has none, so active_len == 0), selecting prev from index 0 must wrap + // to the last result without underflowing `active_len - 1`. + 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(); + + // Put the only match in scrollback, then scroll the active area to all + // blank lines so it contains no match (active_len == 0, history_len == 1). + s.nextSlice("Fizz\r\n"); + while (list.totalPages() < 3) s.nextSlice("\r\n"); + for (0..list.rows) |_| s.nextSlice("\r\n"); + + 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); + + // Select the first match (idx 0), then wrap backwards. This must not + // panic and must keep a valid selection. + _ = try search.select(.next); + _ = try search.select(.prev); + try testing.expect(search.selectedMatch() != null); +} + +test "select after all matches disappear drops the selection" { + // The wrap arithmetic in selectPrev (active_len + history_len - 1) would + // underflow if a selection were ever live while both result lists are + // empty. This guards the invariant that makes that unreachable: when a + // reload/prune empties the results, the selection is dropped, so the next + // select() hits the "no matches" guard instead of the wrap arithmetic. + 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"); + + 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); + + // Take a selection, then overwrite the only match so a reload finds none + // (active and history both empty). + _ = try search.select(.next); + try testing.expect(search.selectedMatch() != null); + s.nextSlice("\x1b[1;1H "); + + // Must not underflow; the selection is dropped and nothing is selected. + _ = try search.select(.prev); + try testing.expect(search.selectedMatch() == null); + try testing.expectEqual(0, search.active_results.items.len); + try testing.expectEqual(0, search.history_results.items.len); +} + +test "select after partial history erase drops a pruned selection" { + 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 stream = t.vtStream(); + defer stream.deinit(); + + stream.nextSlice("error\r\n"); + const first = list.pages.first.?; + while (list.totalPages() < 3) stream.nextSlice("\r\n"); + const first_rows = first.rows(); + + var search: ScreenSearch = try .init(alloc, t.screens.active, "error"); + defer search.deinit(); + try search.searchAll(); + try testing.expectEqual(0, search.active_results.items.len); + try testing.expectEqual(1, search.history_results.items.len); + try testing.expect(try search.select(.next)); + + list.eraseHistory(.{ .history = .{ .y = first_rows - 1 } }); + try testing.expect(!search.selected.?.highlight.start.garbage); + + try testing.expect(!try search.select(.next)); + try testing.expect(search.selected == null); +} + +test "select after history compaction ignores replaced results" { + 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 stream = t.vtStream(); + defer stream.deinit(); + + stream.nextSlice("error\r\n"); + const first = list.pages.first.?; + while (list.totalPages() < 3) stream.nextSlice("\r\n"); + try list.split(.{ + .node = first, + .y = first.rows() / 2, + .x = 0, + }); + + var search: ScreenSearch = try .init(alloc, t.screens.active, "error"); + defer search.deinit(); + try search.searchAll(); + try testing.expectEqual(1, search.history_results.items.len); + + const replacement = (try list.compact(first)).?; + try testing.expect(replacement != first); + + try testing.expect(!try search.select(.next)); + try testing.expect(search.selected == null); +} + +test "select after partial history page erase ignores shifted results" { + 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 stream = t.vtStream(); + defer stream.deinit(); + + const first = list.pages.first.?; + while (first.rows() < first.capacity().rows) stream.nextSlice("\r\n"); + stream.nextSlice("error"); + for (0..list.rows + 1) |_| stream.nextSlice("\r\n"); + try testing.expect(first != list.pages.last.?); + + var search: ScreenSearch = try .init(alloc, t.screens.active, "error"); + defer search.deinit(); + try search.searchAll(); + try testing.expectEqual(0, search.active_results.items.len); + try testing.expectEqual(1, search.history_results.items.len); + + const old_rows = first.rows(); + list.eraseHistory(.{ .history = .{ .y = 0 } }); + try testing.expectEqual(old_rows - 1, first.rows()); + + try testing.expect(!try search.select(.next)); + try testing.expect(search.selected == null); +} + +test "reload defers pruning unselected history results" { + 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 stream = t.vtStream(); + defer stream.deinit(); + + const first = list.pages.first.?; + while (first.rows() < first.capacity().rows) stream.nextSlice("\r\n"); + stream.nextSlice("error"); + for (0..list.rows + 1) |_| stream.nextSlice("\r\n"); + + var search: ScreenSearch = try .init(alloc, t.screens.active, "error"); + defer search.deinit(); + try search.searchAll(); + try testing.expectEqual(1, search.history_results.items.len); + + list.eraseHistory(.{ .history = .{ .y = 0 } }); + + // Routine active refreshes don't inspect unselected history results. + try search.reloadActive(); + try testing.expectEqual(1, search.history_results.items.len); + + // Selection prunes every candidate before attempting to track it. + try testing.expect(!try search.select(.next)); + try testing.expectEqual(0, search.history_results.items.len); +} + +test "reload after partial history page erase drops shifted selection first" { + 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 stream = t.vtStream(); + defer stream.deinit(); + + const first = list.pages.first.?; + while (first.rows() < first.capacity().rows) stream.nextSlice("\r\n"); + stream.nextSlice("error"); + for (0..list.rows + 1) |_| stream.nextSlice("\r\n"); + + var search: ScreenSearch = try .init(alloc, t.screens.active, "error"); + defer search.deinit(); + try search.searchAll(); + try testing.expect(try search.select(.next)); + try testing.expect(search.selected != null); + + list.eraseHistory(.{ .history = .{ .y = 0 } }); + + // Advance the active boundary into another node and add matches so + // reloadActive updates the history result offsets. It must discard the + // stale selected result before comparing any of its captured coordinates. + const active_node = list.getTopLeft(.active).node; + while (list.getTopLeft(.active).node == active_node) { + stream.nextSlice("error\r\n"); + } + + try search.reloadActive(); + try testing.expect(search.selected == null); +} + +test "select after history page split ignores moved results" { + 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 stream = t.vtStream(); + defer stream.deinit(); + + const first = list.pages.first.?; + while (first.rows() < first.capacity().rows) stream.nextSlice("\r\n"); + stream.nextSlice("error"); + for (0..list.rows + 1) |_| stream.nextSlice("\r\n"); + + var search: ScreenSearch = try .init(alloc, t.screens.active, "error"); + defer search.deinit(); + try search.searchAll(); + try testing.expectEqual(1, search.history_results.items.len); + + try list.split(.{ + .node = first, + .y = first.rows() / 2, + .x = 0, + }); + + try testing.expect(!try search.select(.next)); + try testing.expect(search.selected == null); +} + test "screen search no scrollback has no history" { const alloc = testing.allocator; var t: Terminal = try .init(alloc, .{ diff --git a/vendor/libghostty-vt/src/terminal/search/sliding_window.zig b/vendor/libghostty-vt/src/terminal/search/sliding_window.zig index 93a606fd..2f858ec8 100644 --- a/vendor/libghostty-vt/src/terminal/search/sliding_window.zig +++ b/vendor/libghostty-vt/src/terminal/search/sliding_window.zig @@ -89,6 +89,7 @@ pub const SlidingWindow = struct { const Meta = struct { node: *PageList.List.Node, serial: u64, + rows: size.CellCountInt, cell_map: std.ArrayList(point.Coordinate), pub fn deinit(self: *Meta, alloc: Allocator) void { @@ -96,6 +97,17 @@ pub const SlidingWindow = struct { } }; + /// Information copied from a page while appending it to the window. + /// + /// Both values remain safe after the node's preserved page is released. + /// In particular, callers use `last_row_wrapped` to decide whether an + /// adjacent page can contribute to a cross-page match without reading the + /// node again. + pub const AppendResult = struct { + content_len: usize, + last_row_wrapped: bool, + }; + pub fn init( alloc: Allocator, direction: Direction, @@ -164,6 +176,11 @@ pub const SlidingWindow = struct { /// or `append()`. If the caller wants to retain the flattened highlight /// then they should clone it. pub fn next(self: *SlidingWindow) ?FlattenedHighlight { + // An empty needle represents an inactive search. Searching for it + // would otherwise produce a zero-length match, which highlight() + // cannot represent because its end offset is inclusive. + if (self.needle.len == 0) return null; + const slices = slices: { // If we have less data then the needle then we can't possibly match const data_len = self.data.len(); @@ -309,6 +326,12 @@ pub const SlidingWindow = struct { self.chunk_buf.clearRetainingCapacity(); var result: terminal.highlight.Flattened = .empty; + // A reverse cross-page match needs the row count of the last meta in + // search order after the chunks themselves are reversed. Snapshot it + // while traversing Meta rather than dereferencing a PageList node after + // the terminal lock has been released. + var cross_page_end_rows: ?size.CellCountInt = null; + // Go through the meta nodes to find our start. const tl: struct { /// If non-null, we need to continue searching for the bottom-right. @@ -375,7 +398,7 @@ pub const SlidingWindow = struct { .node = meta.node, .serial = meta.serial, .start = @intCast(map.y), - .end = meta.node.data.size.rows, + .end = meta.rows, }); break :tl .{ @@ -410,7 +433,7 @@ pub const SlidingWindow = struct { .node = meta.node, .serial = meta.serial, .start = 0, - .end = meta.node.data.size.rows, + .end = meta.rows, }); meta_consumed += meta.cell_map.items.len; @@ -420,6 +443,7 @@ pub const SlidingWindow = struct { // We found it const map = meta.cell_map.items[meta_i]; result.bot_x = map.x; + cross_page_end_rows = meta.rows; self.chunk_buf.appendAssumeCapacity(.{ .node = meta.node, .serial = meta.serial, @@ -465,12 +489,14 @@ pub const SlidingWindow = struct { .reverse => { const slice = self.chunk_buf.slice(); const nodes = slice.items(.node); + const serials = slice.items(.serial); 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(u64, serials); std.mem.reverse(size.CellCountInt, starts); std.mem.reverse(size.CellCountInt, ends); @@ -491,7 +517,7 @@ pub const SlidingWindow = struct { // order. assert(nodes.len >= 2); starts[0] = ends[0] - 1; - ends[0] = nodes[0].data.size.rows; + ends[0] = cross_page_end_rows.?; ends[nodes.len - 1] = starts[nodes.len - 1] + 1; starts[nodes.len - 1] = 0; } else { @@ -526,11 +552,49 @@ pub const SlidingWindow = struct { pub fn append( self: *SlidingWindow, node: *PageList.List.Node, - ) Allocator.Error!usize { + ) Allocator.Error!AppendResult { + var preserved = try node.pagePreservingState(self.alloc); + defer preserved.deinit(); + + const page = preserved.page(); + const last_row_wrapped = page.getRow(page.size.rows - 1).wrap; + return self.appendPage(node, page, last_row_wrapped); + } + + /// Append a node only when its last row is soft wrapped. + /// + /// This acquires one preserved page for both the wrap check and formatting + /// so a compressed node is decoded at most once. It is used when loading + /// the overlap around an otherwise complete search region. + pub fn appendIfWrapped( + self: *SlidingWindow, + node: *PageList.List.Node, + ) Allocator.Error!?AppendResult { + var preserved = try node.pagePreservingState(self.alloc); + defer preserved.deinit(); + + const page = preserved.page(); + const last_row_wrapped = page.getRow(page.size.rows - 1).wrap; + if (!last_row_wrapped) return null; + return try self.appendPage(node, page, last_row_wrapped); + } + + /// Copy one preserved page into the window's owned search buffers. + /// + /// No pointer into `page` may escape this function: compressed preserved + /// pages own temporary decode storage, while resident values borrow node + /// memory. + fn appendPage( + self: *SlidingWindow, + node: *PageList.List.Node, + page: *const terminal.Page, + last_row_wrapped: bool, + ) Allocator.Error!AppendResult { // Initialize our metadata for the node. var meta: Meta = .{ .node = node, .serial = node.serial, + .rows = page.size.rows, .cell_map = .empty, }; errdefer meta.deinit(self.alloc); @@ -544,7 +608,7 @@ pub const SlidingWindow = struct { // Encode the page into the buffer. const formatter: PageFormatter = formatter: { - var formatter: PageFormatter = .init(&meta.node.data, .{ + var formatter: PageFormatter = .init(page, .{ .emit = .plain, .unwrap = true, }); @@ -563,8 +627,7 @@ pub const SlidingWindow = struct { // 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) { + if (!last_row_wrapped) { encoded.writer.writeByte('\n') catch return error.OutOfMemory; try meta.cell_map.append( self.alloc, @@ -580,7 +643,10 @@ pub const SlidingWindow = struct { const written = encoded.written(); if (written.len == 0) { self.assertIntegrity(); - return 0; + return .{ + .content_len = 0, + .last_row_wrapped = last_row_wrapped, + }; } // Get our written data. If we're doing a reverse search then we @@ -603,7 +669,10 @@ pub const SlidingWindow = struct { self.meta.appendAssumeCapacity(meta); self.assertIntegrity(); - return written.len; + return .{ + .content_len = written.len, + .last_row_wrapped = last_row_wrapped, + }; } /// Only for tests! @@ -642,6 +711,25 @@ test "SlidingWindow empty on init" { try testing.expectEqual(0, w.meta.len()); } +test "SlidingWindow empty needle has no matches" { + const testing = std.testing; + const alloc = testing.allocator; + + var w: SlidingWindow = try .init(alloc, .forward, ""); + defer w.deinit(); + + var s = try Screen.init(alloc, .{ + .cols = 80, + .rows = 24, + .max_scrollback = 0, + }); + defer s.deinit(); + try s.testWriteString("hello"); + + _ = try w.append(s.pages.pages.first.?); + try testing.expectEqual(null, w.next()); +} + test "SlidingWindow single append" { const testing = std.testing; const alloc = testing.allocator; @@ -813,7 +901,7 @@ test "SlidingWindow two pages" { // 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; + const first_page_rows = s.pages.pages.first.?.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!"); @@ -868,7 +956,7 @@ test "SlidingWindow two pages single char" { // 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; + const first_page_rows = s.pages.pages.first.?.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!"); @@ -923,7 +1011,7 @@ test "SlidingWindow two pages match across boundary" { // 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; + const first_page_rows = s.pages.pages.first.?.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"); @@ -968,7 +1056,7 @@ test "SlidingWindow two pages no match across boundary with newline" { // 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; + const first_page_rows = s.pages.pages.first.?.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"); @@ -1001,7 +1089,7 @@ test "SlidingWindow two pages no match across boundary with newline reverse" { // 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; + const first_page_rows = s.pages.pages.first.?.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"); @@ -1031,7 +1119,7 @@ test "SlidingWindow two pages no match prunes first page" { // 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; + const first_page_rows = s.pages.pages.first.?.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!"); @@ -1063,7 +1151,7 @@ test "SlidingWindow two pages no match keeps both pages" { // 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; + const first_page_rows = s.pages.pages.first.?.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!"); @@ -1164,7 +1252,7 @@ test "SlidingWindow single append match on boundary" { // 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; + node.page().getRow(node.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 @@ -1290,7 +1378,7 @@ test "SlidingWindow two pages reversed" { // 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; + const first_page_rows = s.pages.pages.first.?.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!"); @@ -1345,7 +1433,7 @@ test "SlidingWindow two pages match across boundary reversed" { // 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; + const first_page_rows = s.pages.pages.first.?.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"); @@ -1361,6 +1449,15 @@ test "SlidingWindow two pages match across boundary reversed" { // Search should find a match { const h = w.next().?; + const chunks = h.chunks.slice(); + const nodes = chunks.items(.node); + const serials = chunks.items(.serial); + try testing.expectEqual(2, chunks.len); + try testing.expectEqual(node, nodes[0]); + try testing.expectEqual(node.serial, serials[0]); + try testing.expectEqual(node.next.?, nodes[1]); + try testing.expectEqual(node.next.?.serial, serials[1]); + const sel = h.untracked(); try testing.expectEqual(point.Point{ .active = .{ .x = 76, @@ -1391,7 +1488,7 @@ test "SlidingWindow two pages no match prunes first page reversed" { // 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; + const first_page_rows = s.pages.pages.first.?.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!"); @@ -1423,7 +1520,7 @@ test "SlidingWindow two pages no match keeps both pages reversed" { // 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; + const first_page_rows = s.pages.pages.first.?.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!"); @@ -1525,7 +1622,7 @@ test "SlidingWindow single append match on boundary reversed" { // 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; + node.page().getRow(node.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 @@ -1665,7 +1762,7 @@ test "SlidingWindow append whitespace only node" { // 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); + const last_row = node.page().getRow(node.rows() - 1); last_row.wrap = true; try testing.expect(s.pages.pages.first == s.pages.pages.last); diff --git a/vendor/libghostty-vt/src/terminal/search/viewport.zig b/vendor/libghostty-vt/src/terminal/search/viewport.zig index 35dd9331..09d202be 100644 --- a/vendor/libghostty-vt/src/terminal/search/viewport.zig +++ b/vendor/libghostty-vt/src/terminal/search/viewport.zig @@ -24,7 +24,7 @@ const Terminal = @import("../Terminal.zig"); /// lives in the same page. pub const ViewportSearch = struct { window: SlidingWindow, - fingerprint: ?Fingerprint, + 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 @@ -43,21 +43,19 @@ pub const ViewportSearch = struct { 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.fingerprint.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.fingerprint.clearAndRetainCapacity(); self.window.clearAndRetainCapacity(); } @@ -80,48 +78,37 @@ pub const ViewportSearch = struct { 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; - } + // See if our viewport changed. We retain the fingerprint buffer so + // unchanged viewports don't allocate and changed viewports usually + // reuse the previous capacity. + const fingerprint = &self.fingerprint; + if (!try fingerprint.update(self.window.alloc, list)) 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 (fingerprint.entries.items) |entry| { + if (entry.node == active_tl.node) break :match; + if (entry.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; + // No change + return false; } // If our active area was set as dirty, we always unset it here @@ -134,40 +121,40 @@ pub const ViewportSearch = struct { // 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; + const overlap_len = self.window.needle.len -| 1; + const entries = fingerprint.entries.items; + var node_ = entries[0].node.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; + const appended = try self.window.appendIfWrapped(node) orelse break; + added += appended.content_len; + if (added >= overlap_len) 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); + var end_append: SlidingWindow.AppendResult = undefined; + for (entries) |entry| { + end_append = try self.window.append(entry.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; + const end: *PageList.List.Node = entries[entries.len - 1].node; + if (!end_append.last_row_wrapped) 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; + const appended = try self.window.append(node); + added += appended.content_len; + if (added >= overlap_len) 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; + if (!appended.last_row_wrapped) break; } } @@ -182,36 +169,59 @@ pub const ViewportSearch = struct { /// 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) }; - } + /// The node addresses and generations that make up the viewport. We + /// can't safely dereference cached node pointers because the nodes may + /// be invalid, so equality only compares these captured values. + entries: std.ArrayListUnmanaged(Entry) = .empty, + + const Entry = struct { + node: *PageList.List.Node, + serial: u64, + }; pub fn deinit(self: *Fingerprint, alloc: Allocator) void { - alloc.free(self.nodes); + self.entries.deinit(alloc); + } + + pub fn clearAndRetainCapacity(self: *Fingerprint) void { + self.entries.clearRetainingCapacity(); } - 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; + /// Update this fingerprint to match the current viewport. + /// + /// Returns true if the viewport changed. The viewport can have at + /// most one entry per visible row, so we reserve that upper bound + /// before mutating the retained buffer. This lets us rebuild in one + /// pass while still preserving the old fingerprint if allocation + /// fails. + pub fn update(self: *Fingerprint, alloc: Allocator, pages: *PageList) Allocator.Error!bool { + try self.entries.ensureTotalCapacity(alloc, pages.rows); + + const old_len = self.entries.items.len; + var changed = false; + + var i: usize = 0; + var it = pages.pageIterator(.right_down, .{ .viewport = .{} }, null); + while (it.next()) |chunk| : (i += 1) { + const entry: Entry = .{ + .node = chunk.node, + .serial = chunk.node.serial, + }; + if (!changed) { + changed = i >= old_len or + self.entries.items[i].node != entry.node or + self.entries.items[i].serial != entry.serial; + } + + if (i < self.entries.items.len) { + self.entries.items[i] = entry; + } else { + self.entries.appendAssumeCapacity(entry); + } } - return true; + + self.entries.shrinkRetainingCapacity(i); + return changed or i != old_len; } }; }; @@ -259,6 +269,55 @@ test "simple search" { try testing.expect(search.next() == null); } +test "fingerprint detects node generation changes" { + const alloc = testing.allocator; + var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 }); + defer t.deinit(alloc); + + var search: ViewportSearch = try .init(alloc, "needle"); + defer search.deinit(); + search.active_dirty = false; + + try testing.expect(try search.update(&t.screens.active.pages)); + try testing.expect(!try search.update(&t.screens.active.pages)); + + const old_entry = search.fingerprint.entries.items[0]; + const node = t.screens.active.pages.pages.first.?; + try testing.expectEqual(node, old_entry.node); + const original_serial = node.serial; + defer node.serial = original_serial; + node.serial += 1; + + // The viewport still contains the same pointer, but its generation has + // changed, so the cached window must be rebuilt. + try testing.expect(try search.update(&t.screens.active.pages)); + const new_entry = search.fingerprint.entries.items[0]; + try testing.expectEqual(old_entry.node, new_entry.node); + try testing.expect(old_entry.serial != new_entry.serial); +} + +test "fingerprint only allocates on changes" { + const alloc = testing.allocator; + var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 }); + defer t.deinit(alloc); + + var failing = testing.FailingAllocator.init(alloc, .{}); + const failing_alloc = failing.allocator(); + + var search: ViewportSearch = try .init(failing_alloc, "needle"); + defer search.deinit(); + search.active_dirty = false; + + try testing.expect(try search.update(&t.screens.active.pages)); + + // Fail the next allocation. An unchanged viewport with active dirty + // tracking disabled should reuse the existing fingerprint and return + // unchanged before rebuilding the search window, so this update should + // succeed without reporting a viewport change. + failing.fail_index = failing.alloc_index; + try testing.expect(!try search.update(&t.screens.active.pages)); +} + test "clear screen and search" { const alloc = testing.allocator; var t: Terminal = try .init(alloc, .{ .cols = 10, .rows = 10 }); @@ -348,7 +407,7 @@ test "history search, no active area" { defer s.deinit(); // Fill up first page - const first_page_rows = t.screens.active.pages.pages.first.?.data.capacity.rows; + const first_page_rows = t.screens.active.pages.pages.first.?.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); |
