Skip to main content

max / shop

23.5 KB · 588 lines History Blame Raw
1 //! Scrollback: the rows that left the top of the main screen, the viewport
2 //! that reads back into them, and the rewrap that keeps them the grid's width.
3
4 use crate::{Cell, Grid, HistoryRow};
5 use std::collections::VecDeque;
6
7 impl Grid {
8 /// The history row backing visible row `r`, if the viewport is far enough
9 /// back that `r` falls in it.
10 pub(crate) fn history_row(&self, r: u16) -> Option<&HistoryRow> {
11 if r >= self.view_offset {
12 return None;
13 }
14 // The viewport's top row is `view_offset` rows above the live screen,
15 // so it is that far from the end of history.
16 let back = (self.view_offset - r) as usize;
17 self.history
18 .len()
19 .checked_sub(back)
20 .map(|i| &self.history[i])
21 }
22
23 /// The live logical row under visible row `r`. Only meaningful once `r` is
24 /// known not to fall in history.
25 pub(crate) fn live_row(&self, r: u16) -> u16 {
26 r - self.view_offset
27 }
28
29 /// How far back the viewport sits, in rows. Zero is live.
30 pub fn view_offset(&self) -> u16 {
31 self.view_offset
32 }
33
34 /// Rows currently in scrollback.
35 pub fn history_len(&self) -> usize {
36 self.history.len()
37 }
38
39 /// Set how many rows of scrollback to keep, dropping the oldest if the new
40 /// limit is smaller. Zero disables scrollback.
41 pub fn set_history_limit(&mut self, limit: usize) {
42 self.history_limit = limit;
43 while self.history.len() > limit {
44 self.history.pop_front();
45 }
46 // The viewport cannot point past what is left.
47 self.set_view_offset(self.view_offset.min(self.history_len_u16()));
48 }
49
50 /// Move the viewport back into history by `n` rows, stopping at the oldest
51 /// row kept. Returns whether it moved.
52 pub fn scroll_view_up(&mut self, n: u16) -> bool {
53 let want = self
54 .view_offset
55 .saturating_add(n)
56 .min(self.history_len_u16());
57 self.set_view_offset(want)
58 }
59
60 /// Move the viewport toward the live screen by `n` rows. Returns whether
61 /// it moved.
62 pub fn scroll_view_down(&mut self, n: u16) -> bool {
63 let want = self.view_offset.saturating_sub(n);
64 self.set_view_offset(want)
65 }
66
67 /// Snap the viewport back to the live screen. Returns whether it moved.
68 ///
69 /// This is what typing does: input goes to a program whose output is at the
70 /// bottom, so leaving the user reading history while their keystrokes land
71 /// somewhere off-screen would be a lie about where they are.
72 pub fn scroll_view_to_bottom(&mut self) -> bool {
73 self.set_view_offset(0)
74 }
75
76 fn set_view_offset(&mut self, want: u16) -> bool {
77 // The alt screen has no history, so there is nowhere to go.
78 let want = if self.on_alt { 0 } else { want };
79 if want == self.view_offset {
80 return false;
81 }
82 self.view_offset = want;
83 self.view_dirty = true;
84 true
85 }
86
87 pub(crate) fn history_len_u16(&self) -> u16 {
88 self.history.len().min(u16::MAX as usize) as u16
89 }
90
91 /// Push the row about to be overwritten into history, and keep the viewport
92 /// looking at the same content if it is back in history.
93 ///
94 /// Called only from the fullscreen main-screen scroll. A partial scroll
95 /// region is an application drawing inside a box — the row leaving the top
96 /// of that box has not left the screen — and the alt screen keeps none.
97 pub(crate) fn push_history(&mut self, phys: u16) {
98 if self.on_alt || self.history_limit == 0 {
99 return;
100 }
101 let cols = self.cols as usize;
102 let start = phys as usize * cols;
103 let wrapped = self
104 .main_wrapped
105 .get(phys as usize)
106 .copied()
107 .unwrap_or(false);
108 // Recycle the evicted row's buffer rather than freeing one and
109 // allocating another. Scrolling is the throughput case the ring layout
110 // exists for, and once history is full — which a long build log reaches
111 // in seconds — this makes the steady state a memcpy with no allocator
112 // traffic behind it.
113 let mut cells = if self.history.len() == self.history_limit {
114 let recycled = self.history.pop_front().map(|row| row.cells);
115 // The oldest row is gone, so a viewport anchored to it has to give
116 // up a row rather than silently show different text.
117 self.view_offset = self.view_offset.saturating_sub(1);
118 recycled.unwrap_or_default()
119 } else {
120 Vec::new()
121 };
122 cells.clear();
123 cells.extend_from_slice(&self.main[start..start + cols]);
124 self.history.push_back(HistoryRow { cells, wrapped });
125 // Pin the view: new output below should not drag what the user is
126 // reading up the screen.
127 if self.view_offset > 0 {
128 self.view_offset = self
129 .view_offset
130 .saturating_add(1)
131 .min(self.history_len_u16());
132 self.view_dirty = true;
133 }
134 }
135
136 /// Rewrap scrollback from `old_cols` to the width already stored in
137 /// `self.cols`.
138 ///
139 /// The logical lines are recoverable from the materialized rows, so this
140 /// needs no second representation: a maximal run of `wrapped` rows plus the
141 /// row that ends it is one line a program printed, and `wrapped` is correct
142 /// at the moment a row is pushed. Join those runs, re-split at the new
143 /// width, and history is still a deque of exactly-`cols` rows — `row()` and
144 /// every reader above it (selection, word boundaries, copy) is untouched.
145 ///
146 /// The alternative, storing history as logical lines and materializing rows
147 /// on read, moves the cost to every frame and puts variable-width rows in
148 /// front of every reader to buy nothing this does not.
149 ///
150 /// Costs one pass and a transient second copy of the buffer, at resize
151 /// only. That is ~24 MB at the default limit and 200 columns, held for the
152 /// length of a window drag.
153 pub(crate) fn rewrap_history(&mut self, old_cols: u16) {
154 if self.history.is_empty() || old_cols == 0 {
155 return;
156 }
157 let cols = self.cols as usize;
158 // Absolute index of the row the viewport's top sits on, if it is back
159 // in history at all. Carried through as (logical line, cells into it)
160 // so the text under the user's eye stays under it.
161 let anchor_row = self.history.len().saturating_sub(self.view_offset as usize);
162 // The newest line may run onto the live screen. Recorded before the
163 // walk, because re-splitting otherwise decides the final row's flag
164 // from the line's length and would break that join.
165 let tail_continues = self.history.back().is_some_and(|r| r.wrapped);
166
167 let mut lines: Vec<Vec<Cell>> = Vec::new();
168 let mut anchor: Option<(usize, usize)> = None;
169 // Whether the row being visited continues the line already open.
170 let mut open = false;
171 for (i, row) in self.history.iter().enumerate() {
172 if !open {
173 lines.push(Vec::new());
174 }
175 let li = lines.len() - 1;
176 let line = lines.last_mut().expect("a line is open by here");
177 if i == anchor_row {
178 anchor = Some((li, line.len()));
179 }
180 // A logical line is the CHARACTERS the program printed, so the
181 // spacers come out here and are re-derived at the new width. They
182 // are not content: which column a wide character's second half
183 // lands in is a fact about the old width, and carrying them through
184 // would wedge stale blanks into the middle of the rewrapped line.
185 // This is also what keeps a pair from being split by the re-split —
186 // there is nothing to split, only a lead to place or defer.
187 let end = if row.wrapped {
188 // An interior row ran off the right edge, so it is full of
189 // content by construction — nothing on it is padding, except a
190 // pad column a wide character could not fit into, which drops
191 // out with the rest of the spacers.
192 row.cells.len()
193 } else {
194 // The last row of a line: its tail is padding, not content.
195 // Only never-written cells count as padding. A space someone
196 // typed is a cell like any other and keeps its background.
197 row.cells
198 .iter()
199 .rposition(|c| *c != Cell::default())
200 .map_or(0, |i| i + 1)
201 };
202 line.extend(row.cells[..end].iter().filter(|c| !c.is_spacer()).copied());
203 open = row.wrapped;
204 }
205
206 let last_line = lines.len() - 1;
207 let mut out: VecDeque<HistoryRow> = VecDeque::with_capacity(self.history.len());
208 let mut new_anchor: Option<usize> = None;
209 for (li, line) in lines.into_iter().enumerate() {
210 let first = out.len();
211 // Which row of THIS line the anchored character landed on. Counted
212 // during the layout rather than divided out of an offset, because a
213 // wide character can end a row one column early.
214 let mut anchor_row_of_line: Option<usize> = None;
215 // Only the newest line can be unterminated, and only if it was
216 // running onto the live screen before the resize.
217 let unterminated = li == last_line && tail_continues;
218 if line.is_empty() {
219 // A blank line is content: someone's output had a gap in it.
220 // Never wrapped — an empty row holds nothing that could have
221 // run off the edge.
222 out.push_back(HistoryRow {
223 cells: vec![Cell::default(); cols],
224 wrapped: false,
225 });
226 } else {
227 // Lay the characters out at the new width. A row ends when the
228 // next character does not fit, which for a wide character can
229 // be one column early — the column it cannot use becomes a pad,
230 // the same as it would have on the way in.
231 let mut cells: Vec<Cell> = Vec::with_capacity(cols);
232 let mut rows_of_line = 0usize;
233 for (ci, cell) in line.iter().enumerate() {
234 let w = cell.cols() as usize;
235 if cells.len() + w > cols {
236 if cells.len() < cols {
237 cells.push(Cell::pad());
238 }
239 cells.resize(cols, Cell::default());
240 out.push_back(HistoryRow {
241 cells: std::mem::take(&mut cells),
242 wrapped: true,
243 });
244 rows_of_line += 1;
245 cells.reserve(cols);
246 }
247 if anchor == Some((li, ci)) {
248 anchor_row_of_line = Some(rows_of_line);
249 }
250 if w == 2 {
251 let (lead, spacer) = Cell::wide_pair(cell.c(), cell.fg_word, cell.bg_word);
252 cells.push(lead);
253 cells.push(spacer);
254 } else {
255 cells.push(*cell);
256 }
257 }
258 // The row the line ends on. It is wrapped only if the line ran
259 // onto the live screen and still fills the new width: the live
260 // screen is clipped rather than reflowed, so a flag on a
261 // half-full row would be the same lie about where the text
262 // leaves the edge that the live rows drop theirs for, and would
263 // emit its padding as content on a copy.
264 let full = cells.len() == cols;
265 cells.resize(cols, Cell::default());
266 out.push_back(HistoryRow {
267 cells,
268 wrapped: unterminated && full,
269 });
270 }
271 if let Some((al, _)) = anchor
272 && al == li
273 {
274 // Widening can put the anchor past the line's new end, in which
275 // case that line's last row is the closest thing to it.
276 new_anchor = Some(
277 anchor_row_of_line.map_or(out.len() - 1, |r| (first + r).min(out.len() - 1)),
278 );
279 }
280 }
281 self.history = out;
282
283 // Narrowing turns n rows into more than n, which can cross the limit.
284 // Trim after the rewrap and not before, so the trim never cuts a
285 // logical line in half and leaves its tail to be rewrapped alone.
286 let over = self.history.len().saturating_sub(self.history_limit);
287 self.history.drain(..over);
288
289 let before = self.view_offset;
290 self.view_offset = match new_anchor {
291 // The anchored row itself can fall to the trim, and then the oldest
292 // surviving row is the closest the viewport can get to it.
293 Some(a) => {
294 let a = a.saturating_sub(over);
295 (self.history.len() - a).min(u16::MAX as usize) as u16
296 }
297 None => 0,
298 };
299 if self.view_offset != before {
300 self.view_dirty = true;
301 }
302 }
303 }
304
305 #[cfg(test)]
306 mod tests {
307 use crate::testutil::{feed, history_text, row_str};
308 use crate::*;
309
310 #[test]
311 fn rows_that_scroll_off_the_top_land_in_history() {
312 let mut g = Grid::new(6, 3);
313 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
314 assert_eq!(g.history_len(), 2);
315 // Still live, so the screen reads as it did before scrollback existed.
316 assert_eq!(row_str(&g, 0), "three");
317 }
318
319 #[test]
320 fn scrolling_back_shows_the_rows_that_left() {
321 let mut g = Grid::new(6, 3);
322 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
323 assert!(g.scroll_view_up(2));
324 assert_eq!(g.view_offset(), 2);
325 assert_eq!(row_str(&g, 0), "one");
326 assert_eq!(row_str(&g, 1), "two");
327 assert_eq!(row_str(&g, 2), "three");
328 }
329
330 #[test]
331 fn the_viewport_stops_at_the_oldest_row_kept() {
332 let mut g = Grid::new(6, 3);
333 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
334 assert!(g.scroll_view_up(999));
335 assert_eq!(g.view_offset(), 2);
336 // Already at the top: no move, so nothing asks for a redraw.
337 assert!(!g.scroll_view_up(1));
338 }
339
340 #[test]
341 fn output_under_a_scrolled_back_viewport_does_not_drag_it() {
342 let mut g = Grid::new(6, 3);
343 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
344 g.scroll_view_up(2);
345 assert_eq!(row_str(&g, 0), "one");
346 feed(&mut g, b"\r\nsix\r\nseven");
347 // The reader is still looking at the same text, one row further back.
348 assert_eq!(row_str(&g, 0), "one");
349 assert_eq!(g.view_offset(), 4);
350 }
351
352 #[test]
353 fn the_oldest_row_falls_off_at_the_limit() {
354 let mut g = Grid::new(6, 3);
355 g.set_history_limit(2);
356 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive\r\nsix");
357 assert_eq!(g.history_len(), 2);
358 g.scroll_view_up(2);
359 // "one" is gone; the oldest kept row is what the top shows.
360 assert_eq!(row_str(&g, 0), "two");
361 }
362
363 #[test]
364 fn a_zero_limit_keeps_no_history() {
365 let mut g = Grid::new(6, 3);
366 g.set_history_limit(0);
367 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
368 assert_eq!(g.history_len(), 0);
369 assert!(!g.scroll_view_up(1));
370 }
371
372 #[test]
373 fn the_alt_screen_neither_feeds_history_nor_scrolls_back() {
374 let mut g = Grid::new(6, 3);
375 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
376 let before = g.history_len();
377 feed(&mut g, b"\x1b[?1049h"); // enter alt
378 feed(&mut g, b"a\r\nb\r\nc\r\nd\r\ne");
379 assert_eq!(g.history_len(), before, "alt screen wrote to history");
380 assert!(!g.scroll_view_up(1));
381 assert_eq!(g.view_offset(), 0);
382 }
383
384 #[test]
385 fn taking_the_alt_screen_puts_the_viewport_back_at_the_bottom() {
386 let mut g = Grid::new(6, 3);
387 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
388 g.scroll_view_up(2);
389 feed(&mut g, b"\x1b[?1049h");
390 assert_eq!(g.view_offset(), 0);
391 feed(&mut g, b"\x1b[?1049l"); // and back
392 assert_eq!(g.view_offset(), 0);
393 }
394
395 #[test]
396 fn a_partial_scroll_region_does_not_feed_history() {
397 let mut g = Grid::new(6, 4);
398 // DECSTBM rows 1-3: an application drawing in a box, so a row leaving
399 // the top of that box has not left the screen.
400 feed(&mut g, b"\x1b[1;3r");
401 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
402 assert_eq!(g.history_len(), 0);
403 }
404
405 #[test]
406 fn narrowing_wraps_a_long_history_row_instead_of_clipping_it() {
407 let mut g = Grid::new(8, 2);
408 feed(&mut g, b"abcdefgh\r\nsecond\r\nthird");
409 g.scroll_view_up(1);
410 assert_eq!(row_str(&g, 0), "abcdefgh");
411 g.scroll_view_down(1);
412 g.resize(4, 2);
413 // The tail moved to a continuation row rather than being destroyed.
414 assert_eq!(g.row(0).len(), 4, "history rows must be `cols` wide");
415 assert!(history_text(&g).contains("abcdefgh"));
416 }
417
418 #[test]
419 fn narrowing_then_widening_gives_the_logical_lines_back() {
420 let mut g = Grid::new(8, 2);
421 feed(&mut g, b"abcdefgh\r\nsecond\r\nthird");
422 let before = history_text(&g);
423 g.resize(4, 2);
424 g.resize(8, 2);
425 // The property the clipping code could not satisfy at any width.
426 assert_eq!(history_text(&g), before);
427 }
428
429 #[test]
430 fn a_line_exactly_cols_wide_gains_no_empty_continuation_row() {
431 let mut g = Grid::new(4, 2);
432 feed(&mut g, b"abcd\r\nxy\r\nz");
433 let rows = g.history_len();
434 g.resize(8, 2);
435 g.resize(4, 2);
436 assert_eq!(g.history_len(), rows, "a full row grew a continuation");
437 }
438
439 #[test]
440 fn widening_rejoins_what_narrowing_split() {
441 let mut g = Grid::new(4, 2);
442 // "abcdefgh" wraps into two history rows at width 4.
443 feed(&mut g, b"abcdefgh\r\nxy\r\nz");
444 assert_eq!(g.history_len(), 2);
445 g.resize(8, 2);
446 assert_eq!(g.history_len(), 1, "the two halves did not rejoin");
447 g.scroll_view_up(1);
448 assert_eq!(g.row(0).len(), 8);
449 assert_eq!(row_str(&g, 0), "abcdefgh");
450 }
451
452 #[test]
453 fn a_blank_history_line_survives_a_rewrap() {
454 let mut g = Grid::new(8, 2);
455 feed(&mut g, b"one\r\n\r\ntwo\r\nthree");
456 let before = history_text(&g);
457 g.resize(4, 2);
458 g.resize(8, 2);
459 assert_eq!(history_text(&g), before, "the gap in the output closed");
460 }
461
462 #[test]
463 fn narrowing_trims_to_the_limit_after_rewrapping_not_before() {
464 let mut g = Grid::new(8, 2);
465 g.set_history_limit(3);
466 feed(&mut g, b"abcdefgh\r\nijklmnop\r\nqrst\r\nuvwx\r\nlast");
467 g.resize(4, 2);
468 assert_eq!(g.history_len(), 3, "the limit did not hold across a rewrap");
469 // The newest rows survive and they are whole: the trim came after the
470 // rewrap, so no line was cut in half and its tail rewrapped alone.
471 assert!(
472 history_text(&g).ends_with("mnop\nqrst\n"),
473 "{:?}",
474 history_text(&g)
475 );
476 }
477
478 #[test]
479 fn the_viewport_keeps_the_row_it_was_reading_across_a_rewrap() {
480 let mut g = Grid::new(8, 2);
481 feed(&mut g, b"aaaaaaaa\r\nbbbb\r\ncccc\r\ndddd\r\nlive");
482 g.scroll_view_up(2);
483 let reading = row_str(&g, 0);
484 assert_eq!(reading, "bbbb");
485 g.resize(4, 2);
486 assert_eq!(row_str(&g, 0), reading, "narrowing moved the text");
487 g.resize(8, 2);
488 assert_eq!(row_str(&g, 0), reading, "widening moved the text");
489 }
490
491 #[test]
492 fn a_history_row_running_onto_the_live_screen_still_joins_after_a_rewrap() {
493 let mut g = Grid::new(8, 2);
494 // The oldest line runs off the edge and continues onto the live
495 // screen, so its wrap flag has to survive the rewrap.
496 feed(&mut g, b"abcdefghijklmnopqrst");
497 assert_eq!(g.history_len(), 1);
498 g.resize(4, 2);
499 let all = g.text_range(0, g.abs_rows());
500 assert!(
501 all.starts_with("abcdefghijkl"),
502 "the join to the live screen broke: {all:?}"
503 );
504 }
505
506 #[test]
507 fn a_half_full_tail_row_drops_its_wrap_flag_rather_than_emit_padding() {
508 let mut g = Grid::new(4, 2);
509 // "abcd" is a full history row continuing onto the live screen. At
510 // width 8 it no longer reaches the edge, and the live screen it ran
511 // onto is clipped rather than reflowed, so the flag would be a lie —
512 // and would emit four cells of padding as content on a copy.
513 feed(&mut g, b"abcdefghijkl");
514 g.resize(8, 2);
515 assert!(
516 !history_text(&g).starts_with("abcd "),
517 "padding emitted as content: {:?}",
518 history_text(&g)
519 );
520 }
521
522 #[test]
523 fn a_typed_space_at_the_end_of_a_line_is_content_not_padding() {
524 let mut g = Grid::new(8, 2);
525 // A trailing space inside a wrapped line is a real cell the text ran
526 // through; only never-written cells are padding.
527 feed(&mut g, b"ab cd ef gh\r\nxx\r\nyy");
528 let before = history_text(&g);
529 g.resize(4, 2);
530 g.resize(8, 2);
531 assert_eq!(history_text(&g), before);
532 }
533
534 #[test]
535 fn the_viewport_cannot_outlive_the_history_a_resize_leaves() {
536 let mut g = Grid::new(6, 3);
537 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
538 g.scroll_view_up(2);
539 g.set_history_limit(1);
540 assert_eq!(g.view_offset(), 1, "viewport pointed past the oldest row");
541 }
542
543 #[test]
544 fn the_cursor_hides_when_the_viewport_leaves_it_behind() {
545 let mut g = Grid::new(6, 3);
546 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
547 assert_eq!(g.cursor_view_row(), Some(g.cursor().row));
548 // The cursor sits on the bottom row after that output, so one row of
549 // scrollback is already enough to push it off the screen.
550 g.scroll_view_up(1);
551 assert_eq!(g.cursor_view_row(), None);
552 }
553
554 #[test]
555 fn a_viewport_move_asks_for_a_full_rebuild() {
556 let mut g = Grid::new(6, 3);
557 feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
558 let _ = g.take_damage();
559 g.scroll_view_up(1);
560 let d = g.take_damage();
561 assert!(d.view_moved);
562 assert_eq!(d.scroll, 0, "a cache rotation would be wrong here");
563 assert_eq!(d.dirty_rows.len(), 3);
564 }
565
566 #[test]
567 fn a_still_viewport_at_the_bottom_keeps_the_incremental_path() {
568 let mut g = Grid::new(6, 3);
569 feed(&mut g, b"one\r\ntwo\r\nthree");
570 let _ = g.take_damage();
571 feed(&mut g, b"\r\nfour");
572 let d = g.take_damage();
573 assert!(!d.view_moved);
574 assert_eq!(d.scroll, 1, "the O(1) scroll path must survive scrollback");
575 }
576
577 #[test]
578 fn a_wrapped_row_stays_wrapped_in_history() {
579 let mut g = Grid::new(4, 2);
580 // Eight chars over four columns: row 0 runs off the edge into row 1.
581 feed(&mut g, b"abcdefgh\r\nx\r\ny");
582 g.scroll_view_up(2);
583 assert!(g.row_wrapped(0), "the wrap point did not reach history");
584 assert_eq!(row_str(&g, 0), "abcd");
585 assert_eq!(row_str(&g, 1), "efgh");
586 }
587 }
588