perf: structural shift of merge_cache on scrollback drain (replace null-on-drain)

[fredclausen]

Summary

Replace the blunt correctness fix for the scrollback-rotation merge_cache
desync (the self.merge_cache = None; added to Buffer::enforce_scrollback_limit)
with a structural fix that treats the push+drain at scrollback capacity as
the row rotation it actually is: drop the drained row's contribution from the
front of the cached merge, rebase the remaining offsets, and re-merge only the
one (or overflow) new row(s) at the bottom — preserving the incremental
fast path instead of forcing a full-window re-merge on every line feed.

This is a performance follow-up to an already-landed correctness fix.
The correctness bug is fixed and shipped; this issue is purely about buying back
the performance the blunt fix gives up. There is no user-facing correctness
bug open here — do not rush this. Getting the structural version subtly wrong
re-opens the original silent data-corruption bug (in release builds, invisibly),
so the bar for this change is extremely high.

Background: the bug that was fixed (context)

Buffer::merge_cache (introduced in #405 Part C, commit 850dd186) is an
incremental cache of the last visible-window flatten merge. It is keyed by
MergeWindowFp { visible_start, visible_end, auto_detect }, where the bounds
come from visible_window_bounds, which is a pure function of rows.len(),
height, and scroll_offset.

Once the primary-screen scrollback is at capacity, every line feed:

1. pushes one new row at the bottom (rows.len() grows by 1), then
2. enforce_scrollback_limit drains one row from the front
   (self.rows.drain(0..overflow) + self.row_cache.drain(0..overflow)),
   netting rows.len() back to its previous value.

Because rows.len() nets unchanged, visible_window_bounds returns the
same (visible_start, visible_end), so MergeWindowFp is byte-identical
to the fingerprint the cache was built against — even though every surviving
row's identity just shifted down one index. The fast path in
rows_as_tchars_and_tags_incremental then reused a stale prefix, serving a
window that was one (or overflow) rows too early at the top and dropped the
genuinely-new content below.

This is the exact same "confined in-place row rotation" bug class already
guarded at three sites in scroll.rs (scroll_slice_up, scroll_slice_down,
scroll_up), each of which sets self.merge_cache = None; at its rotation
point. enforce_scrollback_limit was the missed fourth site.

Repro precondition (confirmed): a full scrollback. E.g. cat a large file
(≥ scrollback limit lines) to fill scrollback, then run any program that
rewrites lines while emitting new ones (pre-commit run --all-files was the
1000%-reliable field repro). Below capacity, rows.len() grows each line feed
→ fingerprint changes → full re-merge → correct. At capacity → fingerprint
frozen → stale prefix.

Silent in release: the fast path is cross-checked against a full-merge
oracle via debug_verify_against_oracle, but that is #[cfg(debug_assertions)]
only. Debug/test builds panic loudly; release builds silently render stale
scrollback.

The landed fix (the thing this issue improves on)

enforce_scrollback_limit now sets self.merge_cache = None; inside its
overflow > 0 branch (not the rows.len() <= max_rows early return). Correct,
minimal, mirrors the three scroll.rs guards. Regression test:
incremental_merge_matches_oracle_after_scrollback_capacity_rotation in
freminal-buffer/src/buffer/flatten.rs.

Why the landed fix is not the end state

Nulling merge_cache on every drain means: once scrollback is at capacity
(the steady state of any long-running, high-output session — build logs,
cat, find /, streaming tools), every line feed invalidates the cache,
so the next visible_as_tchars_and_tags flatten cannot take the incremental
fast path and must run merge_row_caches_full over the entire visible window.
That is exactly the O(all visible rows) per-frame cost #405 Part C was written
to eliminate, reintroduced in the worst-case workload (large/maximized window +
heavy output).

Measured baseline

Benchmark bench_lf_flatten_at_capacity in
freminal-buffer/benches/buffer_row_bench.rs (width 200, scrollback 4000,
steady-state at capacity, one LF+flatten per timed iteration, cache warmed):

Window height	Time per (LF + flatten), post-fix (full re-merge every frame)
24 rows	~36 µs
100 rows	~66 µs

The cost scales with window height, confirming it is the full-window re-merge.
The structural fix should collapse both figures toward the incremental
fast-path cost (roughly independent of window height, proportional to the new
content only). Use these two numbers as the before/after baseline. (Note: the
benchmark uses iter_batched_ref — do not regress it to by-value
iter_batched, which bakes the ~4000-row buffer's destructor into the timed
span and makes the numbers track scrollback_limit instead of height.)

Proposed structural approach

Recognise the push+drain as a rotation identical in shape to scroll_up
("drop the top row, append one at the bottom"), and update the cached merge
in place instead of discarding it:

1. On a front-drain of overflow rows in enforce_scrollback_limit, instead
   of nulling merge_cache, shift the cached merge: drop the first
   overflow rows' contributions from chars / tags / row_offsets /
   url_tag_indices, and rebase all remaining offsets down by the dropped
   byte/char/tag counts.
2. Adjust the stored MergeWindowFp to the post-drain bounds (they are
   numerically identical at steady state, but must be correct in the general
   overflow > 1 case too).
3. Let the normal incremental path then merge the new bottom row(s) as usual
   via merge_rows_range.

The net result is amortized O(new content) per line feed, matching the intent
of the original incremental cache.

THE CORRECTNESS MINEFIELD — read before writing a single line

Getting this wrong corrupts the buffer's rendered output in ways that are
silent in release and only caught by a debug-only assertion. Treat every
one of the following as a hard requirement, each with its own dedicated test:

1. Tag boundary splitting across the dropped row. A FormatTag in the
   cached merge may start inside a dropped row and extend past it (coalesced
   across the row boundary during the original merge). When the dropped row is
   removed, that tag must be re-clamped so it starts at the new front — its
   start offset rebased, and if it began entirely within the dropped region,
   it must be dropped or truncated correctly. merge_rows_range does not
   currently handle splitting a tag across a dropped boundary; this is new
   logic. This is the single highest-risk item.

2. url_tag_indices rebasing. These are indices into tags. Dropping tags
   from the front shifts every surviving index. Any URL tag that lived wholly
   in the dropped region must be removed from the list; survivors must be
   re-indexed. An off-by-one here silently mislinks or drops hyperlinks.

3. row_offsets invariant. row_offsets[r] is the flat chars index where
   window-relative row r begins, exactly one entry per visible row. After the
   shift it must still have exactly height entries, all rebased, with
   row_offsets[0] == 0.

4. overflow > 1. A runtime scrollback_limit reduction (settings change)
   can drain more than one row in a single call. The shift must handle
   overflow rows generically, not assume 1. Test with overflow = 1, 2, and

   visible-window height (where the entire cached prefix is dropped and the
   fix must degrade to a full merge, not corrupt).

5. Interaction with auto_detect_urls. Wrapped-URL group redetection
   (refresh_row_cache_and_refine_wrapped_urls) currently relies on the
   reuse_available promise. A shifted cache must not defeat or falsely
   satisfy that promise for a wrapped-URL group straddling the old front.

6. Compaction / compression (Task 118/119). Drained rows may reference a
   compressed block (row_block_map); the existing gc_unreferenced_blocks
   runs in the same drain. Confirm the shifted cache never holds a reference
   into a reclaimed block, and that ensure_decompressed on a scrolled-back
   window is unaffected.

7. The debug oracle must stay the arbiter. Every shifted-cache return must
   continue to pass debug_verify_against_oracle (byte-for-byte against a
   from-scratch full merge). Do not weaken, gate, or special-case that
   check. If the shift is correct, the oracle passes unconditionally.

Verification bar (higher than a normal change)

• Keep incremental_merge_matches_oracle_after_scrollback_capacity_rotation
  green (it must still pass — it is the correctness floor).
• Add targeted tests for each of the 7 minefield items above, each asserting
  against independent_oracle / the full-merge oracle.
• Extend the property test incremental_merge_matches_full_merge (or add a
  sibling) to drive random writes while scrollback is at capacity, so the
  rotation path is fuzzed against the oracle across thousands of cases.
• bench_lf_flatten_at_capacity must show a real improvement over the
  ~36 µs / ~66 µs baseline above (that is the whole point); capture before/after
  per the performance-benchmarks / freminal-bench-table procedure.
• Full gate suite green: cargo test --all, cargo clippy --all-targets --all-features -- -D warnings, cargo machete, and
  cargo xtask check-windows.

Scope

• freminal-buffer/src/buffer/resize_and_alt.rs (enforce_scrollback_limit)
• freminal-buffer/src/buffer/flatten.rs (the shift logic on MergeCache,
  new tests)
• freminal-buffer/src/buffer/mod.rs (update the merge_cache field doc:
  enforce_scrollback_limit moves from "explicit null" to "shift in place")

Do NOT

• Do not start this until there is time to do it carefully. The correctness
  bug is already fixed; this is a pure optimization.
• Do not weaken or remove the debug oracle cross-check.
• Do not assume overflow == 1.
• Do not regress the benchmark harness to by-value iter_batched.

[fredclausen]

Before implementing the structural shift proposed here, a realistic benchmark (bench_lf_batch_then_flatten_at_capacity, matching real PTY-read-batched build_snapshot cadence rather than one-LF-per-flatten) showed the rotation cost amortizes to ~1.5% of the per-batch total at realistic batch sizes (K=512), with a larger, previously-unquantified ~7.2 µs/line floor in enforce_scrollback_limit's own drain machinery dominating instead. This prompted a pivot to profiling real app behavior end-to-end rather than continuing on this issue in isolation — full findings, including that benchmark's numbers, are captured in #459.

Keeping this issue open: any future work here is better framed as an architectural-risk-reduction move (stop coalescing FormatTags across row boundaries in the incremental merge cache, which would eliminate the tag-straddle-clamping correctness minefield described above entirely, since the renderer doesn't consume that cross-row property at all) rather than a CPU-savings move — see #459 for the reasoning.