//! Scrollback: the rows that left the top of the main screen, the viewport
//! that reads back into them, and the rewrap that keeps them the grid's width.

use crate::{Cell, Grid, HistoryRow};
use std::collections::VecDeque;

impl Grid {
    /// The history row backing visible row `r`, if the viewport is far enough
    /// back that `r` falls in it.
    pub(crate) fn history_row(&self, r: u16) -> Option<&HistoryRow> {
        if r >= self.view_offset {
            return None;
        }
        // The viewport's top row is `view_offset` rows above the live screen,
        // so it is that far from the end of history.
        let back = (self.view_offset - r) as usize;
        self.history
            .len()
            .checked_sub(back)
            .map(|i| &self.history[i])
    }

    /// The live logical row under visible row `r`. Only meaningful once `r` is
    /// known not to fall in history.
    pub(crate) fn live_row(&self, r: u16) -> u16 {
        r - self.view_offset
    }

    /// How far back the viewport sits, in rows. Zero is live.
    pub fn view_offset(&self) -> u16 {
        self.view_offset
    }

    /// Rows currently in scrollback.
    pub fn history_len(&self) -> usize {
        self.history.len()
    }

    /// Set how many rows of scrollback to keep, dropping the oldest if the new
    /// limit is smaller. Zero disables scrollback.
    pub fn set_history_limit(&mut self, limit: usize) {
        self.history_limit = limit;
        while self.history.len() > limit {
            self.history.pop_front();
        }
        // The viewport cannot point past what is left.
        self.set_view_offset(self.view_offset.min(self.history_len_u16()));
    }

    /// Move the viewport back into history by `n` rows, stopping at the oldest
    /// row kept. Returns whether it moved.
    pub fn scroll_view_up(&mut self, n: u16) -> bool {
        let want = self
            .view_offset
            .saturating_add(n)
            .min(self.history_len_u16());
        self.set_view_offset(want)
    }

    /// Move the viewport toward the live screen by `n` rows. Returns whether
    /// it moved.
    pub fn scroll_view_down(&mut self, n: u16) -> bool {
        let want = self.view_offset.saturating_sub(n);
        self.set_view_offset(want)
    }

    /// Snap the viewport back to the live screen. Returns whether it moved.
    ///
    /// This is what typing does: input goes to a program whose output is at the
    /// bottom, so leaving the user reading history while their keystrokes land
    /// somewhere off-screen would be a lie about where they are.
    pub fn scroll_view_to_bottom(&mut self) -> bool {
        self.set_view_offset(0)
    }

    fn set_view_offset(&mut self, want: u16) -> bool {
        // The alt screen has no history, so there is nowhere to go.
        let want = if self.on_alt { 0 } else { want };
        if want == self.view_offset {
            return false;
        }
        self.view_offset = want;
        self.view_dirty = true;
        true
    }

    pub(crate) fn history_len_u16(&self) -> u16 {
        self.history.len().min(u16::MAX as usize) as u16
    }

    /// Push the row about to be overwritten into history, and keep the viewport
    /// looking at the same content if it is back in history.
    ///
    /// Called only from the fullscreen main-screen scroll. A partial scroll
    /// region is an application drawing inside a box — the row leaving the top
    /// of that box has not left the screen — and the alt screen keeps none.
    pub(crate) fn push_history(&mut self, phys: u16) {
        if self.on_alt || self.history_limit == 0 {
            return;
        }
        let cols = self.cols as usize;
        let start = phys as usize * cols;
        let wrapped = self
            .main_wrapped
            .get(phys as usize)
            .copied()
            .unwrap_or(false);
        // Recycle the evicted row's buffer rather than freeing one and
        // allocating another. Scrolling is the throughput case the ring layout
        // exists for, and once history is full — which a long build log reaches
        // in seconds — this makes the steady state a memcpy with no allocator
        // traffic behind it.
        let mut cells = if self.history.len() == self.history_limit {
            let recycled = self.history.pop_front().map(|row| row.cells);
            // The oldest row is gone, so a viewport anchored to it has to give
            // up a row rather than silently show different text.
            self.view_offset = self.view_offset.saturating_sub(1);
            recycled.unwrap_or_default()
        } else {
            Vec::new()
        };
        cells.clear();
        cells.extend_from_slice(&self.main[start..start + cols]);
        self.history.push_back(HistoryRow { cells, wrapped });
        // Pin the view: new output below should not drag what the user is
        // reading up the screen.
        if self.view_offset > 0 {
            self.view_offset = self
                .view_offset
                .saturating_add(1)
                .min(self.history_len_u16());
            self.view_dirty = true;
        }
    }

    /// Rewrap scrollback from `old_cols` to the width already stored in
    /// `self.cols`.
    ///
    /// The logical lines are recoverable from the materialized rows, so this
    /// needs no second representation: a maximal run of `wrapped` rows plus the
    /// row that ends it is one line a program printed, and `wrapped` is correct
    /// at the moment a row is pushed. Join those runs, re-split at the new
    /// width, and history is still a deque of exactly-`cols` rows — `row()` and
    /// every reader above it (selection, word boundaries, copy) is untouched.
    ///
    /// The alternative, storing history as logical lines and materializing rows
    /// on read, moves the cost to every frame and puts variable-width rows in
    /// front of every reader to buy nothing this does not.
    ///
    /// Costs one pass and a transient second copy of the buffer, at resize
    /// only. That is ~24 MB at the default limit and 200 columns, held for the
    /// length of a window drag.
    pub(crate) fn rewrap_history(&mut self, old_cols: u16) {
        if self.history.is_empty() || old_cols == 0 {
            return;
        }
        let cols = self.cols as usize;
        // Absolute index of the row the viewport's top sits on, if it is back
        // in history at all. Carried through as (logical line, cells into it)
        // so the text under the user's eye stays under it.
        let anchor_row = self.history.len().saturating_sub(self.view_offset as usize);
        // The newest line may run onto the live screen. Recorded before the
        // walk, because re-splitting otherwise decides the final row's flag
        // from the line's length and would break that join.
        let tail_continues = self.history.back().is_some_and(|r| r.wrapped);

        let mut lines: Vec<Vec<Cell>> = Vec::new();
        let mut anchor: Option<(usize, usize)> = None;
        // Whether the row being visited continues the line already open.
        let mut open = false;
        for (i, row) in self.history.iter().enumerate() {
            if !open {
                lines.push(Vec::new());
            }
            let li = lines.len() - 1;
            let line = lines.last_mut().expect("a line is open by here");
            if i == anchor_row {
                anchor = Some((li, line.len()));
            }
            // A logical line is the CHARACTERS the program printed, so the
            // spacers come out here and are re-derived at the new width. They
            // are not content: which column a wide character's second half
            // lands in is a fact about the old width, and carrying them through
            // would wedge stale blanks into the middle of the rewrapped line.
            // This is also what keeps a pair from being split by the re-split —
            // there is nothing to split, only a lead to place or defer.
            let end = if row.wrapped {
                // An interior row ran off the right edge, so it is full of
                // content by construction — nothing on it is padding, except a
                // pad column a wide character could not fit into, which drops
                // out with the rest of the spacers.
                row.cells.len()
            } else {
                // The last row of a line: its tail is padding, not content.
                // Only never-written cells count as padding. A space someone
                // typed is a cell like any other and keeps its background.
                row.cells
                    .iter()
                    .rposition(|c| *c != Cell::default())
                    .map_or(0, |i| i + 1)
            };
            line.extend(row.cells[..end].iter().filter(|c| !c.is_spacer()).copied());
            open = row.wrapped;
        }

        let last_line = lines.len() - 1;
        let mut out: VecDeque<HistoryRow> = VecDeque::with_capacity(self.history.len());
        let mut new_anchor: Option<usize> = None;
        for (li, line) in lines.into_iter().enumerate() {
            let first = out.len();
            // Which row of THIS line the anchored character landed on. Counted
            // during the layout rather than divided out of an offset, because a
            // wide character can end a row one column early.
            let mut anchor_row_of_line: Option<usize> = None;
            // Only the newest line can be unterminated, and only if it was
            // running onto the live screen before the resize.
            let unterminated = li == last_line && tail_continues;
            if line.is_empty() {
                // A blank line is content: someone's output had a gap in it.
                // Never wrapped — an empty row holds nothing that could have
                // run off the edge.
                out.push_back(HistoryRow {
                    cells: vec![Cell::default(); cols],
                    wrapped: false,
                });
            } else {
                // Lay the characters out at the new width. A row ends when the
                // next character does not fit, which for a wide character can
                // be one column early — the column it cannot use becomes a pad,
                // the same as it would have on the way in.
                let mut cells: Vec<Cell> = Vec::with_capacity(cols);
                let mut rows_of_line = 0usize;
                for (ci, cell) in line.iter().enumerate() {
                    let w = cell.cols() as usize;
                    if cells.len() + w > cols {
                        if cells.len() < cols {
                            cells.push(Cell::pad());
                        }
                        cells.resize(cols, Cell::default());
                        out.push_back(HistoryRow {
                            cells: std::mem::take(&mut cells),
                            wrapped: true,
                        });
                        rows_of_line += 1;
                        cells.reserve(cols);
                    }
                    if anchor == Some((li, ci)) {
                        anchor_row_of_line = Some(rows_of_line);
                    }
                    if w == 2 {
                        let (lead, spacer) = Cell::wide_pair(cell.c(), cell.fg_word, cell.bg_word);
                        cells.push(lead);
                        cells.push(spacer);
                    } else {
                        cells.push(*cell);
                    }
                }
                // The row the line ends on. It is wrapped only if the line ran
                // onto the live screen and still fills the new width: the live
                // screen is clipped rather than reflowed, so a flag on a
                // half-full row would be the same lie about where the text
                // leaves the edge that the live rows drop theirs for, and would
                // emit its padding as content on a copy.
                let full = cells.len() == cols;
                cells.resize(cols, Cell::default());
                out.push_back(HistoryRow {
                    cells,
                    wrapped: unterminated && full,
                });
            }
            if let Some((al, _)) = anchor
                && al == li
            {
                // Widening can put the anchor past the line's new end, in which
                // case that line's last row is the closest thing to it.
                new_anchor = Some(
                    anchor_row_of_line.map_or(out.len() - 1, |r| (first + r).min(out.len() - 1)),
                );
            }
        }
        self.history = out;

        // Narrowing turns n rows into more than n, which can cross the limit.
        // Trim after the rewrap and not before, so the trim never cuts a
        // logical line in half and leaves its tail to be rewrapped alone.
        let over = self.history.len().saturating_sub(self.history_limit);
        self.history.drain(..over);

        let before = self.view_offset;
        self.view_offset = match new_anchor {
            // The anchored row itself can fall to the trim, and then the oldest
            // surviving row is the closest the viewport can get to it.
            Some(a) => {
                let a = a.saturating_sub(over);
                (self.history.len() - a).min(u16::MAX as usize) as u16
            }
            None => 0,
        };
        if self.view_offset != before {
            self.view_dirty = true;
        }
    }
}

#[cfg(test)]
mod tests {
    use crate::testutil::{feed, history_text, row_str};
    use crate::*;

    #[test]
    fn rows_that_scroll_off_the_top_land_in_history() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        assert_eq!(g.history_len(), 2);
        // Still live, so the screen reads as it did before scrollback existed.
        assert_eq!(row_str(&g, 0), "three");
    }

    #[test]
    fn scrolling_back_shows_the_rows_that_left() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        assert!(g.scroll_view_up(2));
        assert_eq!(g.view_offset(), 2);
        assert_eq!(row_str(&g, 0), "one");
        assert_eq!(row_str(&g, 1), "two");
        assert_eq!(row_str(&g, 2), "three");
    }

    #[test]
    fn the_viewport_stops_at_the_oldest_row_kept() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        assert!(g.scroll_view_up(999));
        assert_eq!(g.view_offset(), 2);
        // Already at the top: no move, so nothing asks for a redraw.
        assert!(!g.scroll_view_up(1));
    }

    #[test]
    fn output_under_a_scrolled_back_viewport_does_not_drag_it() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        g.scroll_view_up(2);
        assert_eq!(row_str(&g, 0), "one");
        feed(&mut g, b"\r\nsix\r\nseven");
        // The reader is still looking at the same text, one row further back.
        assert_eq!(row_str(&g, 0), "one");
        assert_eq!(g.view_offset(), 4);
    }

    #[test]
    fn the_oldest_row_falls_off_at_the_limit() {
        let mut g = Grid::new(6, 3);
        g.set_history_limit(2);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive\r\nsix");
        assert_eq!(g.history_len(), 2);
        g.scroll_view_up(2);
        // "one" is gone; the oldest kept row is what the top shows.
        assert_eq!(row_str(&g, 0), "two");
    }

    #[test]
    fn a_zero_limit_keeps_no_history() {
        let mut g = Grid::new(6, 3);
        g.set_history_limit(0);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        assert_eq!(g.history_len(), 0);
        assert!(!g.scroll_view_up(1));
    }

    #[test]
    fn the_alt_screen_neither_feeds_history_nor_scrolls_back() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        let before = g.history_len();
        feed(&mut g, b"\x1b[?1049h"); // enter alt
        feed(&mut g, b"a\r\nb\r\nc\r\nd\r\ne");
        assert_eq!(g.history_len(), before, "alt screen wrote to history");
        assert!(!g.scroll_view_up(1));
        assert_eq!(g.view_offset(), 0);
    }

    #[test]
    fn taking_the_alt_screen_puts_the_viewport_back_at_the_bottom() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        g.scroll_view_up(2);
        feed(&mut g, b"\x1b[?1049h");
        assert_eq!(g.view_offset(), 0);
        feed(&mut g, b"\x1b[?1049l"); // and back
        assert_eq!(g.view_offset(), 0);
    }

    #[test]
    fn a_partial_scroll_region_does_not_feed_history() {
        let mut g = Grid::new(6, 4);
        // DECSTBM rows 1-3: an application drawing in a box, so a row leaving
        // the top of that box has not left the screen.
        feed(&mut g, b"\x1b[1;3r");
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        assert_eq!(g.history_len(), 0);
    }

    #[test]
    fn narrowing_wraps_a_long_history_row_instead_of_clipping_it() {
        let mut g = Grid::new(8, 2);
        feed(&mut g, b"abcdefgh\r\nsecond\r\nthird");
        g.scroll_view_up(1);
        assert_eq!(row_str(&g, 0), "abcdefgh");
        g.scroll_view_down(1);
        g.resize(4, 2);
        // The tail moved to a continuation row rather than being destroyed.
        assert_eq!(g.row(0).len(), 4, "history rows must be `cols` wide");
        assert!(history_text(&g).contains("abcdefgh"));
    }

    #[test]
    fn narrowing_then_widening_gives_the_logical_lines_back() {
        let mut g = Grid::new(8, 2);
        feed(&mut g, b"abcdefgh\r\nsecond\r\nthird");
        let before = history_text(&g);
        g.resize(4, 2);
        g.resize(8, 2);
        // The property the clipping code could not satisfy at any width.
        assert_eq!(history_text(&g), before);
    }

    #[test]
    fn a_line_exactly_cols_wide_gains_no_empty_continuation_row() {
        let mut g = Grid::new(4, 2);
        feed(&mut g, b"abcd\r\nxy\r\nz");
        let rows = g.history_len();
        g.resize(8, 2);
        g.resize(4, 2);
        assert_eq!(g.history_len(), rows, "a full row grew a continuation");
    }

    #[test]
    fn widening_rejoins_what_narrowing_split() {
        let mut g = Grid::new(4, 2);
        // "abcdefgh" wraps into two history rows at width 4.
        feed(&mut g, b"abcdefgh\r\nxy\r\nz");
        assert_eq!(g.history_len(), 2);
        g.resize(8, 2);
        assert_eq!(g.history_len(), 1, "the two halves did not rejoin");
        g.scroll_view_up(1);
        assert_eq!(g.row(0).len(), 8);
        assert_eq!(row_str(&g, 0), "abcdefgh");
    }

    #[test]
    fn a_blank_history_line_survives_a_rewrap() {
        let mut g = Grid::new(8, 2);
        feed(&mut g, b"one\r\n\r\ntwo\r\nthree");
        let before = history_text(&g);
        g.resize(4, 2);
        g.resize(8, 2);
        assert_eq!(history_text(&g), before, "the gap in the output closed");
    }

    #[test]
    fn narrowing_trims_to_the_limit_after_rewrapping_not_before() {
        let mut g = Grid::new(8, 2);
        g.set_history_limit(3);
        feed(&mut g, b"abcdefgh\r\nijklmnop\r\nqrst\r\nuvwx\r\nlast");
        g.resize(4, 2);
        assert_eq!(g.history_len(), 3, "the limit did not hold across a rewrap");
        // The newest rows survive and they are whole: the trim came after the
        // rewrap, so no line was cut in half and its tail rewrapped alone.
        assert!(
            history_text(&g).ends_with("mnop\nqrst\n"),
            "{:?}",
            history_text(&g)
        );
    }

    #[test]
    fn the_viewport_keeps_the_row_it_was_reading_across_a_rewrap() {
        let mut g = Grid::new(8, 2);
        feed(&mut g, b"aaaaaaaa\r\nbbbb\r\ncccc\r\ndddd\r\nlive");
        g.scroll_view_up(2);
        let reading = row_str(&g, 0);
        assert_eq!(reading, "bbbb");
        g.resize(4, 2);
        assert_eq!(row_str(&g, 0), reading, "narrowing moved the text");
        g.resize(8, 2);
        assert_eq!(row_str(&g, 0), reading, "widening moved the text");
    }

    #[test]
    fn a_history_row_running_onto_the_live_screen_still_joins_after_a_rewrap() {
        let mut g = Grid::new(8, 2);
        // The oldest line runs off the edge and continues onto the live
        // screen, so its wrap flag has to survive the rewrap.
        feed(&mut g, b"abcdefghijklmnopqrst");
        assert_eq!(g.history_len(), 1);
        g.resize(4, 2);
        let all = g.text_range(0, g.abs_rows());
        assert!(
            all.starts_with("abcdefghijkl"),
            "the join to the live screen broke: {all:?}"
        );
    }

    #[test]
    fn a_half_full_tail_row_drops_its_wrap_flag_rather_than_emit_padding() {
        let mut g = Grid::new(4, 2);
        // "abcd" is a full history row continuing onto the live screen. At
        // width 8 it no longer reaches the edge, and the live screen it ran
        // onto is clipped rather than reflowed, so the flag would be a lie —
        // and would emit four cells of padding as content on a copy.
        feed(&mut g, b"abcdefghijkl");
        g.resize(8, 2);
        assert!(
            !history_text(&g).starts_with("abcd    "),
            "padding emitted as content: {:?}",
            history_text(&g)
        );
    }

    #[test]
    fn a_typed_space_at_the_end_of_a_line_is_content_not_padding() {
        let mut g = Grid::new(8, 2);
        // A trailing space inside a wrapped line is a real cell the text ran
        // through; only never-written cells are padding.
        feed(&mut g, b"ab cd ef gh\r\nxx\r\nyy");
        let before = history_text(&g);
        g.resize(4, 2);
        g.resize(8, 2);
        assert_eq!(history_text(&g), before);
    }

    #[test]
    fn the_viewport_cannot_outlive_the_history_a_resize_leaves() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        g.scroll_view_up(2);
        g.set_history_limit(1);
        assert_eq!(g.view_offset(), 1, "viewport pointed past the oldest row");
    }

    #[test]
    fn the_cursor_hides_when_the_viewport_leaves_it_behind() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        assert_eq!(g.cursor_view_row(), Some(g.cursor().row));
        // The cursor sits on the bottom row after that output, so one row of
        // scrollback is already enough to push it off the screen.
        g.scroll_view_up(1);
        assert_eq!(g.cursor_view_row(), None);
    }

    #[test]
    fn a_viewport_move_asks_for_a_full_rebuild() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree\r\nfour\r\nfive");
        let _ = g.take_damage();
        g.scroll_view_up(1);
        let d = g.take_damage();
        assert!(d.view_moved);
        assert_eq!(d.scroll, 0, "a cache rotation would be wrong here");
        assert_eq!(d.dirty_rows.len(), 3);
    }

    #[test]
    fn a_still_viewport_at_the_bottom_keeps_the_incremental_path() {
        let mut g = Grid::new(6, 3);
        feed(&mut g, b"one\r\ntwo\r\nthree");
        let _ = g.take_damage();
        feed(&mut g, b"\r\nfour");
        let d = g.take_damage();
        assert!(!d.view_moved);
        assert_eq!(d.scroll, 1, "the O(1) scroll path must survive scrollback");
    }

    #[test]
    fn a_wrapped_row_stays_wrapped_in_history() {
        let mut g = Grid::new(4, 2);
        // Eight chars over four columns: row 0 runs off the edge into row 1.
        feed(&mut g, b"abcdefgh\r\nx\r\ny");
        g.scroll_view_up(2);
        assert!(g.row_wrapped(0), "the wrap point did not reach history");
        assert_eq!(row_str(&g, 0), "abcd");
        assert_eq!(row_str(&g, 1), "efgh");
    }
}