How Ghostty Implements Terminal Search Using a Sliding-Window Algorithm

Ghostty implements terminal search using a sliding-window algorithm that incrementally streams terminal page data into a circular buffer, searches for matches while handling page boundary overlaps, and prunes old data to maintain constant memory usage regardless of scrollback size.

Ghostty is a modern terminal emulator written in Zig that must efficiently search massive scrollback buffers without loading all history into memory. Rather than buffering the entire terminal history, Ghostty implements terminal search using a sliding-window algorithm in src/terminal/search/sliding_window.zig that processes text incrementally while preserving the ability to find matches that span page boundaries.

Core Architecture of the Sliding-Window Search

The sliding-window search centers on the SlidingWindow struct, which manages a circular data buffer (DataBuf) and associated metadata (Meta) that maps character offsets back to screen coordinates. This architecture allows Ghostty to search multi-page terminal content as a continuous stream while maintaining precise location tracking for match highlighting.

Initialization and Direction Handling

The algorithm initializes via pub fn init (lines 99–140 in sliding_window.zig), which accepts an allocator, a search direction (forward or reverse), and the search string (needle). When the direction is reverse, Ghostty reverses the needle string immediately to simplify downstream matching logic. The initialization allocates the circular buffer and prepares the metadata structures required to translate text offsets back to terminal coordinates.

The Circular Buffer and Metadata

Each terminal page (PageList.List.Node) is encoded into plain text and appended to DataBuf, while Meta stores a map from text offsets to screen coordinates. This separation allows the search algorithm to operate on raw bytes for speed, while the metadata enables precise translation of match positions back to terminal locations for rendering highlights.

The Search Algorithm Step-by-Step

The core search logic resides in pub fn next (lines 151–189), which implements a three-phase scanning strategy to locate matches without missing content that spans page boundaries.

Appending Terminal Pages

When new pages enter the search window via pub fn append (lines 191–237), the method encodes the page content into UTF-8 text and writes it into the circular buffer. For reverse searches, Ghostty reverses both the data and coordinate maps during append (lines 886–894) so that the same forward-search logic can operate bidirectionally.

Handling Page Boundary Overlaps

To detect matches that span two adjacent pages, next() implements an overlap strategy:

1. Primary scan: Checks the main data slice for exact matches.
2. Overlap buffer: If the needle could span two pages, fills a dedicated overlap buffer of size needle.len * 2 with the tail of the first slice and head of the second slice, then searches this contiguous region.
3. Secondary scan: If still unmatched, scans the remaining second slice.

When a match is found, highlight() (lines 663–705) constructs a FlattenedHighlight containing exact screen coordinates. For reverse searches, this method reorders chunks and swaps X coordinates (lines 663–705) to restore top-to-bottom ordering before returning results.

Pruning for Memory Efficiency

After unsuccessful searches, the algorithm prunes pages that cannot contain future matches (lines 336–374). The window discards old data but retains needle.len - 1 bytes from the oldest page to ensure future overlap checks can still detect matches crossing the new boundary. This pruning applies simultaneously to both the data buffer and metadata buffer, ensuring memory usage remains proportional to the needle length rather than the scrollback size.

Integration with the Viewport

The higher-level ViewportSearch struct in src/terminal/search/viewport.zig drives the sliding window for active screen areas. It calls SlidingWindow.update() whenever viewport content changes, ensuring that only the visible portion is re-searched. This integration minimizes CPU usage by avoiding unnecessary re-scans of off-screen content.

Practical Implementation Example

The following Zig code demonstrates how to instantiate and use the sliding-window search, adapted from Ghostty's unit tests:

const std = @import("std");

// Create a sliding window searching forward for "boo!"
var win = try SlidingWindow.init(allocator, .forward, "boo!");
defer win.deinit();

// Build a screen and write test text
var screen = try Screen.init(allocator, .{ .cols = 80, .rows = 24, .max_scrollback = 0 });
defer screen.deinit();
try screen.testWriteString("hello. boo! hello. boo!");

// Append the page containing the text
const node = screen.pages.pages.first.?;
_ = try win.append(node);

// Iterate through matches
while (win.next()) |highlight| {
    const sel = highlight.untracked(); // Returns Selection with start/end points
    
    // Convert to screen coordinates
    const startPt = screen.pages.pointFromPin(.active, sel.start);
    const endPt = screen.pages.pointFromPin(.active, sel.end);
    
    // Use coordinates for rendering or logging...
    std.log.info("Match at ({d}, {d})", .{ startPt.x, startPt.y });
}

For reverse searches, instantiate with .reverse and append pages in reverse chronological order:

var revWin = try SlidingWindow.init(allocator, .reverse, "boo!");
// Append pages from newest to oldest...

Why Ghostty Uses a Sliding Window

Memory efficiency: The circular buffer retains only pages that could still contain the needle, with aggressive pruning that keeps memory usage constant even with millions of lines of scrollback.

Incremental streaming: As users scroll or new output arrives, the window grows by appending new pages without re-scanning data already confirmed to contain no matches.

Overlap handling: The dedicated overlap buffer eliminates the need to allocate and copy concatenated page data, allowing matches that cross page boundaries to be detected with minimal overhead.

Bidirectional support: The same data structure serves both forward and reverse searches through simple string reversal and coordinate transformation, avoiding code duplication.

Summary

• Core implementation: src/terminal/search/sliding_window.zig contains the SlidingWindow struct with init, append, next, and highlight methods.
• Memory management: The algorithm uses a circular DataBuf and prunes old pages while retaining needle.len - 1 bytes for boundary overlap checking.
• Boundary handling: An overlap buffer of size needle.len * 2 ensures matches spanning page boundaries are never missed.
• Direction support: Reverse searches reverse the needle and data on append, with coordinate fixup in highlight() (lines 663–705).
• Viewport integration: ViewportSearch in src/terminal/search/viewport.zig drives the window to search only visible content.
• Result type: Matches return FlattenedHighlight structures that convert to Selection objects for renderer consumption without locking terminal state.

Frequently Asked Questions

What is the overlap buffer in Ghostty's terminal search?

The overlap buffer is a temporary allocation of size needle.len * 2 used when checking for matches that might span two adjacent terminal pages. According to the source code in sliding_window.zig, when the primary data slice doesn't contain a match, the algorithm copies the tail of the first page and the head of the second page into this contiguous buffer and searches it as a single unit, ensuring no boundary-crossing matches are missed.

How does Ghostty handle reverse terminal search?

Ghostty handles reverse searches by reversing the needle string during initialization and reversing page data when appending to the buffer (lines 886–894 in sliding_window.zig). After finding a match, the highlight() method (lines 663–705) reorders the coordinate chunks and swaps X coordinates to restore proper top-to-bottom ordering before returning the result to the caller.

Which source files contain the sliding-window search implementation?

The primary implementation lives in src/terminal/search/sliding_window.zig, containing the core algorithm, circular buffer management, and overlap handling. The viewport integration is located in src/terminal/search/viewport.zig, while src/terminal/search/screen.zig provides full-screen search caching and abstractions used in testing.

How does the sliding window algorithm minimize memory usage?

The algorithm minimizes memory through aggressive pruning that occurs after each unsuccessful search. Ghostty discards old pages that cannot contain future matches, keeping only needle.len - 1 bytes from the oldest retained page to handle boundary overlaps. This ensures that memory consumption remains proportional to the search string length rather than the total scrollback size, allowing efficient searches even with massive terminal histories.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}