path: root/vendor/libghostty-vt/src/terminal/search/viewport.zig

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,
            .active_dirty = null,
        };
    }

    pub fn deinit(self: *ViewportSearch) void {
        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 {
        self.fingerprint.clearAndRetainCapacity();
        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. 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
            return false;
        }

        // 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.
        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) {
            // 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 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.
        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 = entries[entries.len - 1].node;
            if (!end_append.last_row_wrapped) break :trailing;

            node_ = end.next;
            added = 0;
            while (node_) |node| : (node_ = node.next) {
                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
                if (!appended.last_row_wrapped) 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 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 {
            self.entries.deinit(alloc);
        }

        pub fn clearAndRetainCapacity(self: *Fingerprint) void {
            self.entries.clearRetainingCapacity();
        }

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

            self.entries.shrinkRetainingCapacity(i);
            return changed or i != old_len;
        }
    };
};

test "simple search" {
    const alloc = testing.allocator;
    const io = testing.io;
    var t: Terminal = try .init(io, 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 "fingerprint detects node generation changes" {
    const alloc = testing.allocator;
    const io = testing.io;
    var t: Terminal = try .init(io, 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;
    const io = testing.io;
    var t: Terminal = try .init(io, 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;
    const io = testing.io;
    var t: Terminal = try .init(io, 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;
    const io = testing.io;
    var t: Terminal = try .init(io, 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;
    const io = testing.io;
    var t: Terminal = try .init(io, 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.?.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);
}