Replaces #13292
This optimizes page-local hyperlink and grapheme maps under full
occupancy, repeated clear and redraw, and managed-cell movement.
Hyperlink maps previously allowed 100% occupancy and retained tombstones
after removals. This PR bounds probe lengths with a reserved load factor
and removes tombstones from the design entirely: removal now restores
the table to the exact state it would be in had the key never been
inserted, so fragmentation cannot accumulate by construction.
Clear and redraw improves by 2.4x, hyperlinked cell movement by 10.4x, a
scrolling OSC 8 stream by 1.7x, and normal ASCII/unicode output does not
regress.
## The changes
1. **Reserve probe headroom in hyperlink cell maps.** Hash maps now
support a maximum load config and hyperlink maps set it to 80%.
**Result: known-absent cell movement improves from 1.550 s to 149 ms.**
2. **Replace tombstone removal with backward-shift deletion.** Removing
an entry now closes the hole by shifting later entries backward. This
keeps probe chains short without tombstones, headroom bookkeeping, or
periodic rehashing. Removal may move other entries, but no caller
retains pointers across removals. **Result: clear and redraw improves
from 672 ms to 512 ms over the tombstone revision, 2.4x over baseline,
and the map shrinks by ~140 lines, improving maintenance.**
3. **Avoid duplicate probes when moving managed cell data.** Hyperlink
and grapheme movement already guarantees that the destination is absent,
so these paths use no-clobber insertion and skip duplicate detection.
With backward-shift deletion this fast path is safe at every load state
without special cases, because removing the source genuinely frees a
slot before the destination is inserted. **Result: movement stays at
parity with the tombstone revision (149 ms vs 148 ms) while its
rehash-retry guard is deleted.**
Note a trade-off: the map-churn microbenchmark at maximum load is ~16%
slower, because removal pays a cluster scan up front instead of
deferring cost to later probes and periodic rebuilds. But its a
synthetic case that isn't grounded in reality. Instead, the realistic
counterpart (clear and redraw at high occupancy through the full VT
stream) is 31% faster, and lookups are neutral.
## Benchmarks
| workload | baseline | tombstones | this PR |
|---|---:|---:|---:|
| clear and redraw, 3,000 frames | 1.243 s | 671.9 ms | 511.6 ms |
| scrolling OSC 8 stream, 39 MiB | 5.375 s | 3.484 s | 3.214 s |
| known-absent cell movement | 1.550 s | 148.2 ms | 149.2 ms |
| map churn, 50% load | n/a | 566.8 ms | 464.6 ms |
| map churn, max load | n/a | 1.088 s | 1.259 s |
| map lookup | n/a | 636.2 ms | 643.0 ms |
## LLM Notes
Assisted by GPT 5.6 and Fable. Hand-reviewed, transition to backshift
was my nudge, benchmark numbers are from an LLM benchmark run using
committed benchmarks.
Page maps handled removal with tombstones, which a fixed-capacity map
can never outgrow. Keeping probe lengths bounded required an insertion
headroom counter, an allocation-free rehash, and five separate recovery
paths with subtle invariants: removal created a tombstone without
restoring headroom, so the counter could reach zero while the map was
half empty and every insertion path had to be prepared to rebuild.
Replace tombstones with backward-shift deletion (Knuth vol. 3, 6.4
algorithm R). Removal restores the table to the state it would be in
had the key never been inserted, so probe chains stay canonical at all
times and fragmentation cannot accumulate by construction. This deletes
the headroom counter, the in-place rehash, and every recovery path.
Insertion no longer invalidates pointers; removal may now move other
entries instead, and no caller holds entry pointers across removals.
Removal costs a cluster scan instead of a byte write, paying
incrementally what tombstones deferred to later probes and periodic
rebuilds. Free slots remain all-zero bytes so probe loops keep fusing
the state and fingerprint checks into single-byte compares. A
randomized oracle test against the stdlib map and a canonical-placement
invariant check cover the new removal path, including full tables where
no free slot terminates the shift.
ReleaseFast benchmarks against the prior map commits:
| workload | delta |
|---|---:|
| map churn, 50% load | 1.23x faster |
| map churn, 75% load | 1.15x faster |
| map churn, max load | 1.07x slower |
| map lookup | neutral |
| clear and redraw stream | 1.32x faster |
| full OSC 8 stream | 1.06x faster |
| linked-line movement | neutral |
Hyperlink and grapheme maps are keyed by cell offset. Moving their
data removes the source entry and reinserts it at a destination known
to be absent. Generic clobbering insertion still searches the probe
sequence to rule out a duplicate.
Use no-clobber insertion for these moves so the first available
tombstone can be reused. If a destination reaches a free slot after
tombstones exhaust insertion headroom, rebuild the map in place and
retry before decrementing the budget. This keeps the known-absent fast
path safe at every load state.
The ReleaseFast movement benchmark improves from 133.7 ms to 126.4 ms,
a 5.5% reduction. The linked-line control remains neutral at 395.4 ms
before and 395.7 ms after.
#13292
Page maps previously allowed a 100% load factor. Once live entries
and tombstones filled every slot, a missing-key lookup or insertion
could scan the entire map.
Reserve 20% of each offset hash map as insertion headroom and track
that budget separately from the live count. Port the allocation-free
in-place rehash from Zig HashMapUnmanaged so canonical insertion can
rebuild fragmented probes and restore tombstone-exhausted headroom
without growing the page. Assumed-capacity insertion now applies the
same guard, preventing the headroom counter from wrapping.
Pass the exact requested hyperlink count into map layout before
load-factor scaling, avoiding a redundant power-of-two rounding step.
Screen-level recovery now grows only when live hyperlinks actually fill
usable capacity.
ReleaseFast terminal benchmarks compare main with the combined map
changes:
| workload | before | after | speedup |
|---|---:|---:|---:|
| map churn | 1.253 s | 12.5 ms | 100x |
| full OSC 8 stream | 3.576 s | 75.6 ms | 47x |
| clear and redraw | 299.1 ms | 118.3 ms | 2.5x |
Co-authored-by: Tim Culverhouse <tim@timculverhouse.com>
This changes our `page_serial` semantics from monotonic min to a
generation marker (any change means you should reload). This fixes a
number of real bugs that search had.
In reality, this invariant was already broken and not true. So this PR
comes to reality with that and fixes all our usage. The most visible
failures were panics when selecting cached search results after
partially erasing a history page or splitting a page, but the same bug
class affected viewport search fingerprints and asynchronous render
highlights.
It was mostly search, for now, but this type of fix is important for
some upcoming work I'm playing around with regarding deferred reflow and
disk offload.
## Page Serial Semantics
`Node.serial` is now explicitly a page generation. It changes whenever a
node is allocated or reused, and whenever an in-place mutation changes
the meaning or valid range of its row coordinates.
`page_serial_min` is renamed to `page_serial_epoch` to reflect its
remaining purpose. Only a whole-list reset advances the epoch. A serial
below the epoch is definitely stale and can be rejected in O(1); a
serial at or above it is only potentially valid and is checked against
the live list using its captured pointer and generation.
## Performance
The generation bump is constant work per node whose layout is already
being changed. There is no additional page-list scan on normal row
append or scrollback pruning.
I did add a new field to the render state, so I ran render state
benchmarks we already have that shows a very slight slowdown but this is
acceptable especially given recent speedups outweigh this significantly:
| render measurement | before | after | change |
|--------------------|--------|-------|--------|
| full rebuild | 2.915 us/update | 2.926 us/update | +0.27% |
| lock-held rebuild | 2.472 us/update | 2.489 us/update | +0.53% (within
noise) |
| clean update | 19.03 ns/update | 19.30 ns/update | +1.43% (+0.27 ns) |
| one dirty row | 52.97 ns/update | 53.40 ns/update | +0.96% (within
noise) |
| flattened highlight miss | 86.77 ns/update | 86.87 ns/update | +0.19%
(within noise) |
| flattened highlight match | 88.38 ns/update | 90.26 ns/update | +2.00%
(+1.88 ns) |
## LLM Notes
This work was done in concert with Codex. I reviewed and reshaped the
serial model, implementation, tests, documentation, and performance
analysis throughout. This PR message is hand-written.
reloadActive previously pruned every cached history result whenever the
active area changed. Search reconciliation runs under the terminal lock,
so this scaled with both result and page counts on a frame-paced path.
Validate only the selected history result during reload. Keep full
pruning before selection navigation so stale candidates are removed
before their coordinates are tracked.
Screen scroll fast paths and Terminal line insertion/deletion move Row
values directly instead of using PageList erasure helpers. Their node
generations therefore stayed valid after cached row coordinates changed.
Expose the PageList layout invalidator to sibling terminal modules and
renew each affected existing page once before full-row rotations or
swaps. Keep partial-width cell moves on the content-only path and cover
same-page, cross-page, and fresh-tail behavior.
libghostty-vt was already parsing OSC 52 into the clipboard_contents
action but the stream handler dropped, so there was no way to observe
clipboard writes (in this case, a program using go-libghostty). This
adds a clipboard_set effect following the existing bell/title_changed
pattern and expose it through the C API as
`GHOSTTY_TERMINAL_OPT_CLIPBOARD_SET`.
The callback receives the OSC 52 kind byte and the base64 payload
exactly as received; decoding and kind interpretation are left to the
embedder, matching how decoding is typically deferred.
Note this intentionally does not deal with clipboard read requests given
the security implications.
AI disclosure: Fable (via Claude Code) did the majority of the work
here, I validated it on the client side and fully understand the pattern
we're fitting into.
#13182
Replace the OSC 52-specific kind and encoded payload callback with an
atomic clipboard write containing a normalized destination and decoded
MIME representations. This keeps protocol details out of embedders and
lets iTerm2 Copy use the same semantic path.
Represent clears with an empty content list, preserve binary payloads,
and return a generic result for protocols that acknowledge writes. Add
the C ABI descriptors, layout metadata, and effects example so future
multipart protocols can reuse the callback without another API break.
page_serial_min no longer represented the minimum live page serial.
Its name still suggested an ordering relationship and obscured the
remaining reset-only invalidation behavior.
Rename the field to page_serial_epoch and document its O(1) rejection
and ScreenSearch bulk-pruning utility. Explicitly verify that ordinary
bounded pruning does not begin a new whole-list epoch.
Kitty graphics payloads are dispatched in bulk, but finding each slice
boundary still examines every byte with a scalar loop. This leaves large
direct base64 image transmissions parser-bound.
Scan ordinary APC bytes using the vector width recommended for the
compile target. Keep the scalar scan both as the tail and as the full
fallback when the target has no recommended vector width. Test
state-machine boundaries against byte-at-a-time parsing.
A ReleaseFast APC parser benchmark over the same 64 MiB Kitty graphics
corpus, with 10 warmups and 30 measured runs, produced:
```
mean median
scalar 37.6 ms 32.6 ms
vectorized 22.3 ms 19.0 ms
```
Hyperfine reports the vectorized version as **1.69 times faster
overall**, with the median runtime improving by approximately 42
percent.
AI Disclosure: This patch was created with the assistance of GPT-5.6
Single-row erasure and trailing blank-row trimming can remap or remove
stored row coordinates while retaining the same node. External pointer-
plus-generation references could therefore survive these less common
PageList mutation paths.
Renew each affected node inside the traversal that already changes it,
and signal compression activity only when row erasure begins in
history. This adds constant work per touched page without another list
scan or normal append cost.
Compaction and capacity growth publish fresh page generations, so an
active incremental traversal can detect them. They did not update the
separate activity token, however, and a completed compressor could
remain idle after either operation restored or replaced a cold page.
Mark successful replacements as compression activity without resetting
the exact continuation marker. The next scheduled step can retain valid
progress or restart through the existing generation checks.
ScreenSearch reloaded active state before pruning stale flattened
history. Reload could compare a shifted tracked selection against
cached page coordinates and panic before the later validation step ran.
Prune history immediately after dimension reconciliation in
reloadActive, before any cached coordinate is inspected or converted to
a pin. Selection now relies on that ordering and avoids a redundant
second prune.
RenderState applied flattened highlights after releasing the terminal
lock and matched them to copied rows by node address alone. A recycled
address could therefore make a stale asynchronous highlight decorate
unrelated content.
Capture the live node generation with each render row and require both
the pointer and copied generation to match. Validation remains lock-
free and never dereferences a potentially stale node.
ViewportSearch compared only cached node addresses when deciding
whether to reuse its owned search window. An in-place layout change or
pool address reuse could therefore make stale text and coordinates
appear current.
Snapshot each node generation with its pointer and compare only those
captured values. This detects a renewed generation at the same address
without ever dereferencing cached node pointers.
Reverse multi-page highlight construction reordered node and row-
bound columns but left captured page generations in their original
order. Every cross-page result therefore paired each node with another
page generation and could be rejected as stale despite remaining live.
Reverse the serial column with the other flattened chunk metadata and
cover the node-plus-generation pairing in the existing boundary match
test.
PageList.split moved the source suffix into a fresh target but left
the shortened source on its old generation. Cached matches in that
suffix could therefore pass validation against the live source pointer
and reach pin tracking with invalid coordinates.
Renew the source generation only after target cloning succeeds, and
mark compression activity so restored history is reconsidered. The
conservative floor keeps bounded pruning safe even when the renewed
source and fresh target precede older successors.
Partial history erasure shifted retained rows while preserving the
node generation. Cached flattened matches then passed pointer-plus-
generation validation and could be tracked with coordinates beyond the
shortened page.
Renew the generation before reinitializing or shifting a page layout,
and mark compression activity so an incremental pass restarts and
revisits a restored cold page. The conservative serial floor permits
the fresh generation to remain before older live successors without
rejecting them.
Page generations are not ordered with the page list because splits
and in-place replacements insert fresh generations before older live
pages. Advancing page_serial_min while pruning could therefore reject
live successors and fail PageList integrity checks.
Keep the floor as a whole-list invalidation epoch and use the existing
pointer-plus-generation membership check for ordinary removals. Add
bounded pruning coverage for split and replacement ordering, and verify
reset still rejects a stale generation when its node address is reused.
Kitty graphics payloads are dispatched in bulk, but finding each slice
boundary still examines every byte with a scalar loop. This leaves large
direct base64 image transmissions parser-bound.
Scan ordinary APC bytes using the vector width recommended for the compile
target. Keep the scalar scan both as the tail and as the full fallback when
the target has no recommended vector width. Test state-machine boundaries
against byte-at-a-time parsing.
A ReleaseFast APC parser benchmark over the same 64 MiB Kitty graphics
corpus, with 10 warmups and 30 measured runs, produced:
mean median
scalar 37.6 ms 32.6 ms
vectorized 22.3 ms 19.0 ms
Hyperfine reports the vectorized version as 1.69 times faster overall, with
the median runtime improving by approximately 42 percent.
All found by GPT 5.6. I'm still going through manual review of each one
now and will remove or rewrite the ones that are pointless or
unreachable (if any, I prompted it to ignore those too).
Count-limited PageIterator traversal took the minimum of the page and requested lengths, then tested whether that minimum exceeded the request. The condition was impossible, so iteration never crossed a page. Reverse traversal also excluded the current row and subtracted one from row zero, causing a runtime safety panic.
Count the current row in both directions, consume the returned length, and move to an adjacent page only when the request has rows remaining. Returned chunks now preserve their half-open bounds at row zero and across page boundaries.
Search selection could run after the terminal removed a screen but before the next refresh reconciled the cached searchers. Reloading that stale ScreenSearch dereferenced freed PageList nodes, while normal cleanup also tried to untrack pins from the destroyed list.
Reconcile under the terminal lock before selecting, track ScreenSet generations so allocator address reuse cannot hide replacements, and release stale search buffers without touching pins already freed with the screen. Cleanup now takes the same lock when live pins must be untracked.
History pruning only compared cached serials with page_serial_min. Replacing a historical node through compaction left its old serial above that cutoff, so selecting the cached match attempted to track a destroyed node and hit the PageList validity assertion.
Validate every flattened chunk by finding the live node and matching its serial without dereferencing stale pointers. Remove only the invalid result and adjust any later selection index so unrelated older results remain available.
PageListSearch.feed changed only the node of its tracked progress pin. If the preceding history page had fewer rows or columns after a split, the retained bottom-right coordinates fell outside that page and the next PageList integrity check panicked.
Reset both coordinates to the new node's actual bottom-right cell whenever feed advances. The progress pin now remains valid across heterogeneous page sizes.
Partial history erasure can remove a page without marking tracked pins as garbage because they move coherently to the next page. ScreenSearch therefore retained a selection whose cached history result was subsequently removed by pruneHistory. Selecting again indexed an empty history result list and panicked.
Clear the tracked selection when its combined result index falls within the history suffix being pruned. Retained active and newer history selections keep their existing indices.
startHyperlink accepts borrowed URI and ID slices. When those slices came from the current cursor hyperlink, startHyperlinkOnce ended and freed that hyperlink before duplicating the replacement, then dereferenced the released URI and segfaulted.
Duplicate the new hyperlink before ending the prior one. Aliased inputs remain valid through the copy, and allocation failure leaves the existing cursor hyperlink intact.
setTitle can receive the slice returned by getTitle. Clearing the list retained its allocation, so appending that same slice used memcpy with aliased source and destination ranges and panicked in runtime-safe builds.
Resize the list within its reserved capacity and copy the value forward before writing the sentinel. This supports the complete current value and its subslices without weakening allocation-failure atomicity.
setPwd can receive the slice returned by getPwd. Clearing the list retained its allocation, so appending that same slice used memcpy with aliased source and destination ranges and panicked in runtime-safe builds.
Resize the list within its reserved capacity and copy the value forward before writing the sentinel. This supports the complete current value and its subslices without weakening allocation-failure atomicity.
Screen.select accepted an already tracked selection by value. Passing the screen's current selection back into the setter caused the old selection cleanup to free the same pin pair that the replacement retained, so the next selection operation dereferenced stale pool entries and panicked.
When replacing tracked state, release only old pins that are not also owned by the replacement. Exact and partial aliases now retain their shared pins while ordinary replacements still reclaim both old entries.
Terminal.resize deinitialized the current tab stops before allocating their replacement. If a resize beyond the inline tab-stop capacity ran out of memory, the terminal retained an undefined tab-stop value and normal deinitialization dereferenced a poisoned pointer.
Allocate and initialize the replacement first, then release the old tab stops only after allocation succeeds. A failed resize now retains the original tab stops and remains safe to destroy.
setTitle appended the title bytes and terminating NUL with separate fallible operations. If only the terminator allocation failed, it returned OutOfMemory but left a nonempty unterminated buffer that made getTitle panic on its sentinel check.
Reserve checked capacity before clearing the existing title, then append both the title and terminator without further allocation. Allocation failure now leaves the prior valid title intact.
setPwd appended the path bytes and terminating NUL with separate fallible operations. If only the terminator allocation failed, the function returned OutOfMemory but left a nonempty unterminated buffer that made getPwd panic on its sentinel check.
Reserve checked capacity for the complete sentinel-terminated value before clearing the old state, then use infallible appends. Allocation failure now leaves a valid prior value instead of exposing partial data.
Implicit OSC 8 hyperlinks incremented a u32 identifier with checked arithmetic even though the cursor contract allows the sequence to wrap. Reaching the maximum identifier therefore caused a runtime safety panic before the link could be installed.
Use wrapping arithmetic for both the successful increment and the error rollback. The identifier now returns to zero at the boundary, while failed allocation attempts still restore the original value.
With mode 2027 disabled, the printer attaches zero-width codepoints without applying Unicode grapheme boundaries. Enabling the mode later and printing another non-ASCII codepoint asserted that every stored pair was part of one grapheme and panicked when it was not.
Feed all stored codepoints through the grapheme state machine and let it reset at existing boundaries before testing the new codepoint. The deterministic print comparison can now exercise live mode changes without clearing the screen first.
Screen.clearRows sliced backing cells using the desired PageList width.
During incomplete reflow, clearing a narrower stored page extended the
slice past its row and tripped clearCells runtime validation before any
cells were cleared.
Obtain cells from the owning page and use its stored width for whole-row
managed-memory bookkeeping. Mixed-width history rows now clear safely.
Rectangle orientation swaps endpoint columns when a selection is mirrored.
During incomplete reflow, copying a column from a wider page onto the
narrower corner page created an invalid pin that panicked when resolved.
Clamp every swapped column to the page that owns the oriented corner.
Top-left and bottom-right calculations now always return valid pins.
Screen.clone clipped selections with the desired screen width or copied
rectangle columns unchanged. PageList.clone preserves stored page widths,
so a clipped boundary on a narrower page produced an invalid tracked pin
and panicked during runtime validation.
Build fallback pins from the first or last cloned node and clamp rectangle
columns to that node. Clipped selections now remain valid during reflow.
Selection drags converted caller-provided floating-point positions directly
to u32 and multiplied geometry dimensions without checking their range.
Non-finite positions, oversized values, overflowing dimensions, or empty
core geometry could therefore panic in runtime safety builds.
Clamp pixel positions to the representable u32 range, reject empty
geometry, and saturate the pixel span when dimensions overflow. Valid
drags keep their existing threshold behavior.
cursorCellEndOfPrev moved its pin to the previous row but then set the
column from the desired screen width. If incomplete reflow left that
previous page narrower, resolving the cell used an out-of-bounds column
and panicked in runtime safety builds.
Set the column from the page reached by the cursor pin so the returned
cell is always the actual final cell of that row.
containedRowCached built full-row and rectangular selections using
the desired screen width. During incomplete reflow, an intermediate
narrower page received endpoints beyond its cell range, and consumers
could panic when resolving the returned pins.
Use the owning page width for full rows and clamp rectangular bounds to
that width. Every contained-row selection now returns resolvable pins.
Semantic line selection moved to the previous row when the next row
started with different content, then assigned the previous pin an x
coordinate from the next page. During incomplete reflow, a wider next
page produced an out-of-bounds pin and a runtime safety panic.
Set the end column from the page that owns the destination pin. Line
selection now remains valid while crossing mixed-width page boundaries.
Tabstops.reset subtracted one from the column count before iterating
default stops. Although init and resize accept zero columns, resetting
that state with a nonzero interval underflowed and panicked.
Return after clearing when the grid has fewer than two columns. Empty
and single-column tabstop sets now preserve the normal no-stop result.
SelectionGesture passed caller-supplied repeat timestamps directly to
Instant.since. A C API client or non-monotonic timer could provide an
earlier timestamp after a later one, causing a runtime safety panic
while converting negative elapsed seconds to u64.
Compare instants before calculating elapsed time and treat backwards
timestamps as failed repeats. The next press becomes a new single-click
anchor, matching other invalid repeat inputs.
Screen.clearCells accepted a slice but its runtime safety validation
indexed the first and last elements unconditionally. Passing an empty
range therefore panicked before the otherwise valid no-op clear.
Return immediately for an empty slice so validation and managed-memory
bookkeeping only run when there are cells to clear.
Pin movement assumed every page had the same column count. During an
incomplete reflow, crossing into a narrower page could produce an
out-of-bounds x coordinate, while wrapped movement could land on the
wrong row or stop early.
Use destination page widths while moving vertically or wrapping, and
reject points that exceed the resolved page. Add synthetic mixed-width
coverage for movement, wrapping, overflow, and point conversion.
