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); }