| 1 | //! Memoization for the per-cell tool-output shaping pipeline. |
| 2 | //! |
| 3 | //! `output_rows` (in `tui::history`) walks the raw tool output, ANSI-strips |
| 4 | //! each line, classifies path/URL-like rows, and wraps the rest to the |
| 5 | //! current viewport width. `selected_output_indices` then computes the |
| 6 | //! head/tail/importance subset that the compact "Live" view shows. Both |
| 7 | //! functions are pure functions of `(output, width)` and `(rows, |
| 8 | //! line_limit)`, but they are called on every render frame for every |
| 9 | //! visible tool cell. For a 4 KB output on a 120 FPS render loop, that |
| 10 | //! is 2–6 redundant walks per frame, per cell. |
| 11 | //! |
| 12 | //! This module adds a process-local, content-addressed cache in front of |
| 13 | //! the two pure functions. The cache is global (one per process) and |
| 14 | //! consults a small `HashMap` keyed on `(content_hash, width)` for the |
| 15 | //! rows and `(rows_hash, line_limit)` for the indices. Insertion-order |
| 16 | //! LRU eviction keeps memory bounded. |
| 17 | //! |
| 18 | //! ## When the cache is a win |
| 19 | //! |
| 20 | //! - Long tool cells that are scrolled into view repeatedly (the model |
| 21 | //! often re-asks for the same `read_file` after a partial failure). |
| 22 | //! - The whole transcript re-rendering at 120 FPS while streaming: the |
| 23 | //! finalized tool cells below the live tail are unchanged on every |
| 24 | //! frame, so their `output_rows` and `selected_output_indices` calls |
| 25 | //! are pure cache hits. |
| 26 | //! - Terminal resizes still invalidate correctly because `width` is part |
| 27 | //! of the key. |
| 28 | //! |
| 29 | //! ## When the cache misses |
| 30 | //! |
| 31 | //! - New tool output (different `content_hash`). |
| 32 | //! - First render of a cell (cache is cold). |
| 33 | //! - Terminal width changed since the last render. |
| 34 | |
| 35 | use std::cell::RefCell; |
| 36 | use std::collections::{HashMap, VecDeque}; |
| 37 | use std::sync::Arc; |
| 38 | |
| 39 | use crate::tui::history::OutputRow; |
| 40 | |
| 41 | /// Default capacity for the LRU. Sized for a worst-case \"5,000-line |
| 42 | /// transcript at 200 cells, plus a 4 KB row cache for the live tail\" — |
| 43 | /// well under a megabyte. |
| 44 | const DEFAULT_CAPACITY: usize = 256; |
| 45 | |
| 46 | /// Internal cache entry. Stores the wrapped `Vec<OutputRow>` plus the |
| 47 | /// `Vec<usize>` of selected indices so a single key lookup can satisfy |
| 48 | /// both render steps. Indices are recomputed lazily when the |
| 49 | /// `line_limit` changes; rows are shared across all line limits. |
| 50 | #[derive(Debug, Clone)] |
| 51 | struct CacheEntry { |
| 52 | /// Shared so a cache hit hands back a refcount bump. Every hit used to |
| 53 | /// deep-copy each `String` and styled span of a payload whose whole point |
| 54 | /// is that it does not change between frames (#6213 T1). |
| 55 | rows: Arc<Vec<OutputRow>>, |
| 56 | /// Map of `line_limit -> selected indices`. Bounded by the |
| 57 | /// distinct line limits passed in by the renderer (typically 1–3). |
| 58 | selected_by_limit: HashMap<usize, Vec<usize>>, |
| 59 | } |
| 60 | |
| 61 | impl CacheEntry { |
| 62 | fn new(rows: Arc<Vec<OutputRow>>) -> Self { |
| 63 | Self { |
| 64 | rows, |
| 65 | selected_by_limit: HashMap::new(), |
| 66 | } |
| 67 | } |
| 68 | } |
| 69 | |
| 70 | /// Bounded LRU cache of `(output, width) -> OutputRowsCacheEntry`. |
| 71 | /// |
| 72 | /// The eviction policy is insertion-order: when the cache reaches |
| 73 | /// `capacity`, the oldest-inserted key is dropped first. Re-inserting an |
| 74 | /// existing key (different content) keeps the original position, so |
| 75 | /// re-rendering the same cell on every frame does not churn unrelated |
| 76 | /// entries. |
| 77 | #[derive(Debug)] |
| 78 | struct OutputRowsCacheInner { |
| 79 | capacity: usize, |
| 80 | by_key: HashMap<RowsKey, CacheEntry>, |
| 81 | insertion_order: VecDeque<RowsKey>, |
| 82 | } |
| 83 | |
| 84 | #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] |
| 85 | struct RowsKey { |
| 86 | /// 64-bit content hash of the raw tool output. Two outputs with |
| 87 | /// different bytes produce different hashes; identical bytes produce |
| 88 | /// the same hash. |
| 89 | content_hash: u64, |
| 90 | /// Terminal width used for wrapping. Resize invalidates. |
| 91 | width: u16, |
| 92 | } |
| 93 | |
| 94 | impl OutputRowsCacheInner { |
| 95 | fn new() -> Self { |
| 96 | Self::with_capacity(DEFAULT_CAPACITY) |
| 97 | } |
| 98 | |
| 99 | fn with_capacity(capacity: usize) -> Self { |
| 100 | let cap = capacity.max(1); |
| 101 | Self { |
| 102 | capacity: cap, |
| 103 | by_key: HashMap::with_capacity(cap), |
| 104 | insertion_order: VecDeque::with_capacity(cap), |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | /// Get or compute the wrapped output rows for `output` at `width`. |
| 109 | /// On a hit, returns another handle on the cached rows — the caller can |
| 110 | /// iterate without holding a lock, and pays a refcount bump rather than a |
| 111 | /// deep copy. |
| 112 | fn get_or_compute_rows<F>( |
| 113 | &mut self, |
| 114 | content_hash: u64, |
| 115 | width: u16, |
| 116 | compute: F, |
| 117 | ) -> Arc<Vec<OutputRow>> |
| 118 | where |
| 119 | F: FnOnce() -> Vec<OutputRow>, |
| 120 | { |
| 121 | let key = RowsKey { |
| 122 | content_hash, |
| 123 | width, |
| 124 | }; |
| 125 | if let Some(entry) = self.by_key.get(&key) { |
| 126 | return Arc::clone(&entry.rows); |
| 127 | } |
| 128 | |
| 129 | let rows = Arc::new(compute()); |
| 130 | let entry = CacheEntry::new(Arc::clone(&rows)); |
| 131 | |
| 132 | if self.by_key.len() >= self.capacity |
| 133 | && let Some(oldest) = self.insertion_order.pop_front() |
| 134 | { |
| 135 | self.by_key.remove(&oldest); |
| 136 | } |
| 137 | self.by_key.insert(key, entry); |
| 138 | self.insertion_order.push_back(key); |
| 139 | rows |
| 140 | } |
| 141 | |
| 142 | /// Get or compute the selected indices for the cached rows at the |
| 143 | /// given `line_limit`. Looks up the row entry by `(content_hash, |
| 144 | /// width)` first (the same key used to insert the rows) and then |
| 145 | /// consults the per-line-limit map on that entry. `compute` is |
| 146 | /// invoked only on the first call for a given |
| 147 | /// `(content_hash, width, line_limit)` triple. |
| 148 | fn get_or_compute_indices<F>( |
| 149 | &mut self, |
| 150 | content_hash: u64, |
| 151 | width: u16, |
| 152 | line_limit: usize, |
| 153 | compute: F, |
| 154 | ) -> Vec<usize> |
| 155 | where |
| 156 | F: FnOnce() -> Vec<usize>, |
| 157 | { |
| 158 | let key = RowsKey { |
| 159 | content_hash, |
| 160 | width, |
| 161 | }; |
| 162 | if let Some(entry) = self.by_key.get_mut(&key) |
| 163 | && let Some(indices) = entry.selected_by_limit.get(&line_limit) |
| 164 | { |
| 165 | return indices.clone(); |
| 166 | } |
| 167 | |
| 168 | let indices = compute(); |
| 169 | if let Some(entry) = self.by_key.get_mut(&key) { |
| 170 | entry.selected_by_limit.insert(line_limit, indices.clone()); |
| 171 | } |
| 172 | indices |
| 173 | } |
| 174 | } |
| 175 | |
| 176 | thread_local! { |
| 177 | /// Thread-local cache. The TUI render loop runs on a single thread, |
| 178 | /// so a `!Sync` cache is sufficient and avoids contention with any |
| 179 | /// background workers that might call into the same module. |
| 180 | static GLOBAL_CACHE: RefCell<OutputRowsCacheInner> = |
| 181 | RefCell::new(OutputRowsCacheInner::new()); |
| 182 | } |
| 183 | |
| 184 | /// Reset the global cache. Used by tests and `/clear`. |
| 185 | #[cfg(test)] |
| 186 | pub fn reset_for_tests() { |
| 187 | GLOBAL_CACHE.with(|c| *c.borrow_mut() = OutputRowsCacheInner::new()); |
| 188 | } |
| 189 | |
| 190 | /// Look up (or compute) the wrapped output rows for `output` at `width`. |
| 191 | /// On a hit the cached rows are handed back behind a shared handle, so the |
| 192 | /// per-line ANSI strip and wrap pass are skipped without copying the rows. |
| 193 | /// String-keyed convenience over [`get_or_compute_rows_with_hash`]. Only the |
| 194 | /// tests use it now that production callers hash once and pass the hash. |
| 195 | #[cfg(test)] |
| 196 | pub fn get_or_compute_rows<F>(output: &str, width: u16, compute: F) -> Arc<Vec<OutputRow>> |
| 197 | where |
| 198 | F: FnOnce() -> Vec<OutputRow>, |
| 199 | { |
| 200 | get_or_compute_rows_with_hash(hash_str(output), width, compute) |
| 201 | } |
| 202 | |
| 203 | /// As `get_or_compute_rows` but takes a precomputed content hash, so a |
| 204 | /// caller that already hashed the output (e.g. to also key |
| 205 | /// [`get_or_compute_indices`]) does not hash it a second time (#3757 review). |
| 206 | pub fn get_or_compute_rows_with_hash<F>( |
| 207 | content_hash: u64, |
| 208 | width: u16, |
| 209 | compute: F, |
| 210 | ) -> Arc<Vec<OutputRow>> |
| 211 | where |
| 212 | F: FnOnce() -> Vec<OutputRow>, |
| 213 | { |
| 214 | GLOBAL_CACHE.with(|c| { |
| 215 | c.borrow_mut() |
| 216 | .get_or_compute_rows(content_hash, width, compute) |
| 217 | }) |
| 218 | } |
| 219 | |
| 220 | /// Look up (or compute) the selected indices for a previously-cached |
| 221 | /// rows payload at the given `line_limit`. `content_hash` is the same |
| 222 | /// 64-bit content hash that was passed to `get_or_compute_rows`. |
| 223 | pub fn get_or_compute_indices<F>( |
| 224 | content_hash: u64, |
| 225 | width: u16, |
| 226 | line_limit: usize, |
| 227 | compute: F, |
| 228 | ) -> Vec<usize> |
| 229 | where |
| 230 | F: FnOnce() -> Vec<usize>, |
| 231 | { |
| 232 | GLOBAL_CACHE.with(|c| { |
| 233 | c.borrow_mut() |
| 234 | .get_or_compute_indices(content_hash, width, line_limit, compute) |
| 235 | }) |
| 236 | } |
| 237 | |
| 238 | /// FNV-1a 64-bit content hash. Cheap, no per-process key, and ~5-10× |
| 239 | /// faster than `DefaultHasher` (SipHash) on the small-to-medium tool |
| 240 | /// output strings we see on the render hot path. The cache is a |
| 241 | /// correctness optimization, not a security boundary — a 64-bit collision |
| 242 | /// space is more than wide enough for the per-process LRU's expected |
| 243 | /// ≤ a few hundred entries, and collisions only cause a false miss, |
| 244 | /// never wrong data. |
| 245 | pub fn hash_str(s: &str) -> u64 { |
| 246 | /// FNV-1a 64-bit offset basis. |
| 247 | const FNV_OFFSET_BASIS: u64 = 0xcbf2_9ce4_8422_2325; |
| 248 | /// FNV-1a 64-bit prime. |
| 249 | const FNV_PRIME: u64 = 0x0000_0100_0000_01b3; |
| 250 | |
| 251 | let mut hash = FNV_OFFSET_BASIS; |
| 252 | for byte in s.as_bytes() { |
| 253 | hash ^= u64::from(*byte); |
| 254 | hash = hash.wrapping_mul(FNV_PRIME); |
| 255 | } |
| 256 | // Mix the length in last so two strings that share a prefix but |
| 257 | // differ in length (e.g. one has a trailing newline) still collide |
| 258 | // only on truly-identical content. |
| 259 | hash ^= s.len() as u64; |
| 260 | hash.wrapping_mul(FNV_PRIME) |
| 261 | } |
| 262 | |
| 263 | #[cfg(test)] |
| 264 | mod tests { |
| 265 | use super::*; |
| 266 | |
| 267 | fn row(text: &str) -> OutputRow { |
| 268 | OutputRow { |
| 269 | text: text.to_string(), |
| 270 | intact: false, |
| 271 | styled: None, |
| 272 | } |
| 273 | } |
| 274 | |
| 275 | #[test] |
| 276 | fn cache_hit_returns_cached_rows() { |
| 277 | reset_for_tests(); |
| 278 | |
| 279 | let calls = std::cell::Cell::new(0u32); |
| 280 | let compute = || { |
| 281 | calls.set(calls.get() + 1); |
| 282 | vec![row("hello"), row("world")] |
| 283 | }; |
| 284 | |
| 285 | let a = get_or_compute_rows("payload", 80, compute); |
| 286 | let b = get_or_compute_rows("payload", 80, || { |
| 287 | calls.set(calls.get() + 1); |
| 288 | vec![row("hello"), row("world")] |
| 289 | }); |
| 290 | assert_eq!(calls.get(), 1, "second call should hit the cache"); |
| 291 | assert_eq!(a, b); |
| 292 | } |
| 293 | |
| 294 | #[test] |
| 295 | fn different_width_invalidates_rows() { |
| 296 | reset_for_tests(); |
| 297 | |
| 298 | let calls = std::cell::Cell::new(0u32); |
| 299 | let make = || { |
| 300 | calls.set(calls.get() + 1); |
| 301 | vec![row("hello")] |
| 302 | }; |
| 303 | |
| 304 | let _ = get_or_compute_rows("payload", 80, make); |
| 305 | let _ = get_or_compute_rows("payload", 120, make); |
| 306 | assert_eq!(calls.get(), 2, "different width must miss the cache"); |
| 307 | } |
| 308 | |
| 309 | #[test] |
| 310 | fn different_output_invalidates_rows() { |
| 311 | reset_for_tests(); |
| 312 | |
| 313 | let calls = std::cell::Cell::new(0u32); |
| 314 | let make = || { |
| 315 | calls.set(calls.get() + 1); |
| 316 | vec![row("x")] |
| 317 | }; |
| 318 | |
| 319 | let _ = get_or_compute_rows("payload-a", 80, make); |
| 320 | let _ = get_or_compute_rows("payload-b", 80, make); |
| 321 | assert_eq!(calls.get(), 2); |
| 322 | } |
| 323 | |
| 324 | #[test] |
| 325 | fn indices_cached_per_line_limit() { |
| 326 | reset_for_tests(); |
| 327 | |
| 328 | let rows = get_or_compute_rows("payload", 80, || { |
| 329 | vec![row("a"), row("b"), row("c"), row("d"), row("e")] |
| 330 | }); |
| 331 | assert_eq!(rows.len(), 5); |
| 332 | |
| 333 | let content_hash = hash_str("payload"); |
| 334 | let mut calls = 0; |
| 335 | let pick_two_a = get_or_compute_indices(content_hash, 80, 2, || { |
| 336 | calls += 1; |
| 337 | vec![0usize, 4] |
| 338 | }); |
| 339 | let pick_two_b = get_or_compute_indices(content_hash, 80, 2, || { |
| 340 | calls += 1; |
| 341 | vec![0usize, 4] |
| 342 | }); |
| 343 | assert_eq!(calls, 1, "second lookup with same limit hits the cache"); |
| 344 | assert_eq!(pick_two_a, pick_two_b); |
| 345 | assert_eq!(pick_two_a, vec![0, 4]); |
| 346 | |
| 347 | // Different line_limit must miss and recompute. |
| 348 | let _ = get_or_compute_indices(content_hash, 80, 3, || { |
| 349 | calls += 1; |
| 350 | vec![0usize, 1, 4] |
| 351 | }); |
| 352 | assert_eq!(calls, 2); |
| 353 | } |
| 354 | |
| 355 | #[test] |
| 356 | fn capacity_evicts_oldest() { |
| 357 | // Build a private cache so we can size it tightly. |
| 358 | let mut cache = OutputRowsCacheInner::with_capacity(2); |
| 359 | |
| 360 | let _ = cache.get_or_compute_rows(1, 80, || vec![row("a")]); |
| 361 | let _ = cache.get_or_compute_rows(2, 80, || vec![row("b")]); |
| 362 | let _ = cache.get_or_compute_rows(3, 80, || vec![row("c")]); |
| 363 | // The first entry (hash 1) should have been evicted. |
| 364 | let mut compute_calls = 0; |
| 365 | let _ = cache.get_or_compute_rows(1, 80, || { |
| 366 | compute_calls += 1; |
| 367 | vec![row("a")] |
| 368 | }); |
| 369 | assert_eq!(compute_calls, 1, "evicted entry must miss"); |
| 370 | } |
| 371 | |
| 372 | #[test] |
| 373 | fn hash_str_stable_for_identical_input() { |
| 374 | assert_eq!(hash_str("hello"), hash_str("hello")); |
| 375 | assert_ne!(hash_str("hello"), hash_str("world")); |
| 376 | } |
| 377 | |
| 378 | #[test] |
| 379 | fn hash_str_differs_on_length_suffix() { |
| 380 | // A trailing newline is a different content; the hash must differ. |
| 381 | assert_ne!(hash_str("hello"), hash_str("hello\n")); |
| 382 | } |
| 383 | |
| 384 | #[test] |
| 385 | fn hash_str_handles_empty() { |
| 386 | // Empty string hashes to the FNV offset basis; the result just |
| 387 | // needs to be stable. |
| 388 | assert_eq!(hash_str(""), hash_str("")); |
| 389 | } |
| 390 | } |
| 391 |