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