Unify the grid line indexing types

Previously Alacritty was using two different ways to reference lines in
the terminal. Either a `usize`, or a `Line(usize)`. These indexing
systems both served different purposes, but made it difficult to reason
about logic involving these systems because of its inconsistency.

To resolve this issue, a single new `Line(i32)` type has been
introduced.  All existing references to lines and points now rely on
this definition of a line.

The indexing starts at the top of the terminal region with the line 0,
which matches the line 1 used by escape sequences. Each line in the
history becomes increasingly negative and the bottommost line is equal
to the number of visible lines minus one.

Having a system which goes into the negatives allows following the
escape sequence's indexing system closely, while at the same time making
it trivial to implement `Ord` for points.

The Alacritty UI crate is the only place which has a different indexing
system, since rendering and input puts the zero line at the top of the
viewport, rather than the top of the terminal region.

All instances which refer to a number of lines/columns instead of just a
single Line/Column have also been changed to use a `usize` instead. This
way a Line/Column will always refer to a specific place in the grid and
no confusion is created by having a count of lines as a possible index
into the grid storage.

1 files changed, 119 insertions, 183 deletions

diff --git a/alacritty_terminal/src/grid/mod.rs b/alacritty_terminal/src/grid/mod.rs
index 7949489a..169067af 100644
--- a/alacritty_terminal/src/grid/mod.rs
+++ b/alacritty_terminal/src/grid/mod.rs
@@ -1,13 +1,13 @@
 //! A specialized 2D grid implementation optimized for use in a terminal.
 
 use std::cmp::{max, min};
-use std::iter::{Map, TakeWhile};
-use std::ops::{Bound, Deref, Index, IndexMut, Range, RangeBounds, RangeInclusive};
+use std::iter::TakeWhile;
+use std::ops::{Bound, Deref, Index, IndexMut, Range, RangeBounds};
 
 use serde::{Deserialize, Serialize};
 
 use crate::ansi::{CharsetIndex, StandardCharset};
-use crate::index::{Column, IndexRange, Line, Point};
+use crate::index::{Column, Line, Point};
 use crate::term::cell::{Flags, ResetDiscriminant};
 
 pub mod resize;
@@ -71,7 +71,7 @@ impl IndexMut<CharsetIndex> for Charsets {
 
 #[derive(Debug, Copy, Clone)]
 pub enum Scroll {
-    Delta(isize),
+    Delta(i32),
     PageUp,
     PageDown,
     Top,
@@ -103,7 +103,7 @@ pub enum Scroll {
 /// │                         │
 /// └─────────────────────────┘  <-- zero
 ///                           ^
-///                          cols
+///                        columns
 /// ```
 #[derive(Serialize, Deserialize, Clone, Debug)]
 pub struct Grid<T> {
@@ -120,10 +120,10 @@ pub struct Grid<T> {
     raw: Storage<T>,
 
     /// Number of columns.
-    cols: Column,
+    columns: usize,
 
     /// Number of visible lines.
-    lines: Line,
+    lines: usize,
 
     /// Offset of displayed area.
     ///
@@ -137,15 +137,15 @@ pub struct Grid<T> {
 }
 
 impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
-    pub fn new(lines: Line, cols: Column, max_scroll_limit: usize) -> Grid<T> {
+    pub fn new(lines: usize, columns: usize, max_scroll_limit: usize) -> Grid<T> {
         Grid {
-            raw: Storage::with_capacity(lines, cols),
+            raw: Storage::with_capacity(lines, columns),
             max_scroll_limit,
             display_offset: 0,
             saved_cursor: Cursor::default(),
             cursor: Cursor::default(),
             lines,
-            cols,
+            columns,
         }
     }
 
@@ -161,12 +161,11 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
 
     pub fn scroll_display(&mut self, scroll: Scroll) {
         self.display_offset = match scroll {
-            Scroll::Delta(count) => min(
-                max((self.display_offset as isize) + count, 0isize) as usize,
-                self.history_size(),
-            ),
-            Scroll::PageUp => min(self.display_offset + self.lines.0, self.history_size()),
-            Scroll::PageDown => self.display_offset.saturating_sub(self.lines.0),
+            Scroll::Delta(count) => {
+                min(max((self.display_offset as i32) + count, 0) as usize, self.history_size())
+            },
+            Scroll::PageUp => min(self.display_offset + self.lines, self.history_size()),
+            Scroll::PageDown => self.display_offset.saturating_sub(self.lines),
             Scroll::Top => self.history_size(),
             Scroll::Bottom => 0,
         };
@@ -175,7 +174,7 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
     fn increase_scroll_limit(&mut self, count: usize) {
         let count = min(count, self.max_scroll_limit - self.history_size());
         if count != 0 {
-            self.raw.initialize(count, self.cols);
+            self.raw.initialize(count, self.columns);
         }
     }
 
@@ -188,18 +187,15 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
     }
 
     #[inline]
-    pub fn scroll_down<D>(&mut self, region: &Range<Line>, positions: Line)
+    pub fn scroll_down<D>(&mut self, region: &Range<Line>, positions: usize)
     where
         T: ResetDiscriminant<D>,
         D: PartialEq,
     {
-        let screen_lines = self.screen_lines().0;
-
         // When rotating the entire region, just reset everything.
-        if positions >= region.end - region.start {
-            for i in region.start.0..region.end.0 {
-                let index = screen_lines - i - 1;
-                self.raw[index].reset(&self.cursor.template);
+        if region.end - region.start <= positions {
+            for i in (region.start.0..region.end.0).map(Line::from) {
+                self.raw[i].reset(&self.cursor.template);
             }
 
             return;
@@ -218,32 +214,32 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
             //
             // We need to start from the top, to make sure the fixed lines aren't swapped with each
             // other.
-            let fixed_lines = screen_lines - region.end.0;
-            for i in (0..fixed_lines).rev() {
-                self.raw.swap(i, i + positions.0);
+            let screen_lines = self.screen_lines() as i32;
+            for i in (region.end.0..screen_lines).map(Line::from) {
+                self.raw.swap(i, i - positions as i32);
             }
 
             // Rotate the entire line buffer downward.
-            self.raw.rotate_down(*positions);
+            self.raw.rotate_down(positions);
 
             // Ensure all new lines are fully cleared.
-            for i in 0..positions.0 {
-                let index = screen_lines - i - 1;
-                self.raw[index].reset(&self.cursor.template);
+            for i in (0..positions).map(Line::from) {
+                self.raw[i].reset(&self.cursor.template);
             }
 
             // Swap the fixed lines at the top back into position.
-            for i in 0..region.start.0 {
-                let index = screen_lines - i - 1;
-                self.raw.swap(index, index - positions.0);
+            for i in (0..region.start.0).map(Line::from) {
+                self.raw.swap(i, i + positions);
             }
         } else {
             // Subregion rotation.
-            for line in IndexRange((region.start + positions)..region.end).rev() {
-                self.raw.swap_lines(line, line - positions);
+            let range = (region.start + positions).0..region.end.0;
+            for line in range.rev().map(Line::from) {
+                self.raw.swap(line, line - positions);
             }
 
-            for line in IndexRange(region.start..(region.start + positions)) {
+            let range = region.start.0..(region.start + positions).0;
+            for line in range.rev().map(Line::from) {
                 self.raw[line].reset(&self.cursor.template);
             }
         }
@@ -252,18 +248,15 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
     /// Move lines at the bottom toward the top.
     ///
     /// This is the performance-sensitive part of scrolling.
-    pub fn scroll_up<D>(&mut self, region: &Range<Line>, positions: Line)
+    pub fn scroll_up<D>(&mut self, region: &Range<Line>, positions: usize)
     where
         T: ResetDiscriminant<D>,
         D: PartialEq,
     {
-        let screen_lines = self.screen_lines().0;
-
         // When rotating the entire region with fixed lines at the top, just reset everything.
-        if positions >= region.end - region.start && region.start != Line(0) {
-            for i in region.start.0..region.end.0 {
-                let index = screen_lines - i - 1;
-                self.raw[index].reset(&self.cursor.template);
+        if region.end - region.start <= positions && region.start != 0 {
+            for i in (region.start.0..region.end.0).map(Line::from) {
+                self.raw[i].reset(&self.cursor.template);
             }
 
             return;
@@ -271,11 +264,11 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
 
         // Update display offset when not pinned to active area.
         if self.display_offset != 0 {
-            self.display_offset = min(self.display_offset + *positions, self.max_scroll_limit);
+            self.display_offset = min(self.display_offset + positions, self.max_scroll_limit);
         }
 
         // Create scrollback for the new lines.
-        self.increase_scroll_limit(*positions);
+        self.increase_scroll_limit(positions);
 
         // Swap the lines fixed at the top to their target positions after rotation.
         //
@@ -285,23 +278,22 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
         //
         // We need to start from the bottom, to make sure the fixed lines aren't swapped with each
         // other.
-        for i in (0..region.start.0).rev() {
-            let index = screen_lines - i - 1;
-            self.raw.swap(index, index - positions.0);
+        for i in (0..region.start.0).rev().map(Line::from) {
+            self.raw.swap(i, i + positions);
         }
 
         // Rotate the entire line buffer upward.
-        self.raw.rotate(-(positions.0 as isize));
+        self.raw.rotate(-(positions as isize));
 
         // Ensure all new lines are fully cleared.
-        for i in 0..positions.0 {
+        let screen_lines = self.screen_lines();
+        for i in ((screen_lines - positions)..screen_lines).map(Line::from) {
             self.raw[i].reset(&self.cursor.template);
         }
 
         // Swap the fixed lines at the bottom back into position.
-        let fixed_lines = screen_lines - region.end.0;
-        for i in 0..fixed_lines {
-            self.raw.swap(i, i + positions.0);
+        for i in (region.end.0..(screen_lines as i32)).rev().map(Line::from) {
+            self.raw.swap(i, i - positions);
         }
     }
 
@@ -311,16 +303,16 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
         D: PartialEq,
     {
         // Determine how many lines to scroll up by.
-        let end = Point { line: 0, column: self.cols() };
+        let end = Point::new(Line(self.lines as i32 - 1), Column(self.columns()));
         let mut iter = self.iter_from(end);
         while let Some(cell) = iter.prev() {
-            if !cell.is_empty() || cell.point.line >= *self.lines {
+            if !cell.is_empty() || cell.point.line < 0 {
                 break;
             }
         }
-        debug_assert!(iter.point.line <= *self.lines);
-        let positions = self.lines - iter.point.line;
-        let region = Line(0)..self.screen_lines();
+        debug_assert!(iter.point.line >= -1);
+        let positions = (iter.point.line.0 + 1) as usize;
+        let region = Line(0)..Line(self.lines as i32);
 
         // Reset display offset.
         self.display_offset = 0;
@@ -329,8 +321,8 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
         self.scroll_up(&region, positions);
 
         // Reset rotated lines.
-        for i in positions.0..self.lines.0 {
-            self.raw[i].reset(&self.cursor.template);
+        for line in (0..(self.lines - positions)).map(Line::from) {
+            self.raw[line].reset(&self.cursor.template);
         }
     }
 
@@ -347,8 +339,9 @@ impl<T: GridCell + Default + PartialEq + Clone> Grid<T> {
         self.display_offset = 0;
 
         // Reset all visible lines.
-        for row in 0..self.raw.len() {
-            self.raw[row].reset(&self.cursor.template);
+        let range = self.topmost_line().0..(self.screen_lines() as i32);
+        for line in range.map(Line::from) {
+            self.raw[line].reset(&self.cursor.template);
         }
     }
 }
@@ -369,59 +362,17 @@ impl<T> Grid<T> {
         let end = match bounds.end_bound() {
             Bound::Included(line) => *line + 1,
             Bound::Excluded(line) => *line,
-            Bound::Unbounded => self.screen_lines(),
+            Bound::Unbounded => Line(self.screen_lines() as i32),
         };
 
-        debug_assert!(start < self.screen_lines());
-        debug_assert!(end <= self.screen_lines());
+        debug_assert!(start < self.screen_lines() as i32);
+        debug_assert!(end <= self.screen_lines() as i32);
 
-        for row in start.0..end.0 {
-            self.raw[Line(row)].reset(&self.cursor.template);
+        for line in (start.0..end.0).map(Line::from) {
+            self.raw[line].reset(&self.cursor.template);
         }
     }
 
-    /// Clamp a buffer point to the visible region.
-    pub fn clamp_buffer_to_visible(&self, point: Point<usize>) -> Point {
-        if point.line < self.display_offset {
-            Point::new(self.lines - 1, self.cols - 1)
-        } else if point.line >= self.display_offset + self.lines.0 {
-            Point::new(Line(0), Column(0))
-        } else {
-            // Since edgecases are handled, conversion is identical as visible to buffer.
-            self.visible_to_buffer(point.into()).into()
-        }
-    }
-
-    // Clamp a buffer point based range to the viewport.
-    //
-    // This will make sure the content within the range is visible and return `None` whenever the
-    // entire range is outside the visible region.
-    pub fn clamp_buffer_range_to_visible(
-        &self,
-        range: &RangeInclusive<Point<usize>>,
-    ) -> Option<RangeInclusive<Point>> {
-        let start = range.start();
-        let end = range.end();
-
-        // Check if the range is completely offscreen
-        let viewport_end = self.display_offset;
-        let viewport_start = viewport_end + self.lines.0 - 1;
-        if end.line > viewport_start || start.line < viewport_end {
-            return None;
-        }
-
-        let start = self.clamp_buffer_to_visible(*start);
-        let end = self.clamp_buffer_to_visible(*end);
-
-        Some(start..=end)
-    }
-
-    /// Convert viewport relative point to global buffer indexing.
-    #[inline]
-    pub fn visible_to_buffer(&self, point: Point) -> Point<usize> {
-        Point { line: self.lines.0 + self.display_offset - point.line.0 - 1, column: point.column }
-    }
-
     #[inline]
     pub fn clear_history(&mut self) {
         // Explicitly purge all lines from history.
@@ -438,7 +389,7 @@ impl<T> Grid<T> {
         self.truncate();
 
         // Initialize everything with empty new lines.
-        self.raw.initialize(self.max_scroll_limit - self.history_size(), self.cols);
+        self.raw.initialize(self.max_scroll_limit - self.history_size(), self.columns);
     }
 
     /// This is used only for truncating before saving ref-tests.
@@ -448,28 +399,21 @@ impl<T> Grid<T> {
     }
 
     #[inline]
-    pub fn iter_from(&self, point: Point<usize>) -> GridIterator<'_, T> {
+    pub fn iter_from(&self, point: Point) -> GridIterator<'_, T> {
         GridIterator { grid: self, point }
     }
 
     /// Iterator over all visible cells.
     #[inline]
     pub fn display_iter(&self) -> DisplayIter<'_, T> {
-        let start = Point::new(self.display_offset + self.lines.0, self.cols() - 1);
-        let end = Point::new(self.display_offset, self.cols());
+        let start = Point::new(Line(-(self.display_offset as i32) - 1), self.last_column());
+        let end = Point::new(start.line + self.lines, Column(self.columns));
 
         let iter = GridIterator { grid: self, point: start };
 
-        let display_offset = self.display_offset;
-        let lines = self.lines.0;
-
         let take_while: DisplayIterTakeFun<'_, T> =
             Box::new(move |indexed: &Indexed<&T>| indexed.point <= end);
-        let map: DisplayIterMapFun<'_, T> = Box::new(move |indexed: Indexed<&T>| {
-            let line = Line(lines + display_offset - indexed.point.line - 1);
-            Indexed { point: Point::new(line, indexed.point.column), cell: indexed.cell }
-        });
-        iter.take_while(take_while).map(map)
+        iter.take_while(take_while)
     }
 
     #[inline]
@@ -488,7 +432,7 @@ impl<T: PartialEq> PartialEq for Grid<T> {
     fn eq(&self, other: &Self) -> bool {
         // Compare struct fields and check result of grid comparison.
         self.raw.eq(&other.raw)
-            && self.cols.eq(&other.cols)
+            && self.columns.eq(&other.columns)
             && self.lines.eq(&other.lines)
             && self.display_offset.eq(&other.display_offset)
     }
@@ -510,38 +454,6 @@ impl<T> IndexMut<Line> for Grid<T> {
     }
 }
 
-impl<T> Index<usize> for Grid<T> {
-    type Output = Row<T>;
-
-    #[inline]
-    fn index(&self, index: usize) -> &Row<T> {
-        &self.raw[index]
-    }
-}
-
-impl<T> IndexMut<usize> for Grid<T> {
-    #[inline]
-    fn index_mut(&mut self, index: usize) -> &mut Row<T> {
-        &mut self.raw[index]
-    }
-}
-
-impl<T> Index<Point<usize>> for Grid<T> {
-    type Output = T;
-
-    #[inline]
-    fn index(&self, point: Point<usize>) -> &T {
-        &self[point.line][point.column]
-    }
-}
-
-impl<T> IndexMut<Point<usize>> for Grid<T> {
-    #[inline]
-    fn index_mut(&mut self, point: Point<usize>) -> &mut T {
-        &mut self[point.line][point.column]
-    }
-}
-
 impl<T> Index<Point> for Grid<T> {
     type Output = T;
 
@@ -564,15 +476,33 @@ pub trait Dimensions {
     fn total_lines(&self) -> usize;
 
     /// Height of the viewport in lines.
-    fn screen_lines(&self) -> Line;
+    fn screen_lines(&self) -> usize;
 
     /// Width of the terminal in columns.
-    fn cols(&self) -> Column;
+    fn columns(&self) -> usize;
+
+    /// Index for the last column.
+    #[inline]
+    fn last_column(&self) -> Column {
+        Column(self.columns() - 1)
+    }
+
+    /// Line farthest up in the grid history.
+    #[inline]
+    fn topmost_line(&self) -> Line {
+        Line(-(self.history_size() as i32))
+    }
+
+    /// Line farthest down in the grid history.
+    #[inline]
+    fn bottommost_line(&self) -> Line {
+        Line(self.screen_lines() as i32 - 1)
+    }
 
     /// Number of invisible lines part of the scrollback history.
     #[inline]
     fn history_size(&self) -> usize {
-        self.total_lines() - self.screen_lines().0
+        self.total_lines() - self.screen_lines()
     }
 }
 
@@ -583,38 +513,38 @@ impl<G> Dimensions for Grid<G> {
     }
 
     #[inline]
-    fn screen_lines(&self) -> Line {
+    fn screen_lines(&self) -> usize {
         self.lines
     }
 
     #[inline]
-    fn cols(&self) -> Column {
-        self.cols
+    fn columns(&self) -> usize {
+        self.columns
     }
 }
 
 #[cfg(test)]
-impl Dimensions for (Line, Column) {
+impl Dimensions for (usize, usize) {
     fn total_lines(&self) -> usize {
-        *self.0
+        self.0
     }
 
-    fn screen_lines(&self) -> Line {
+    fn screen_lines(&self) -> usize {
         self.0
     }
 
-    fn cols(&self) -> Column {
+    fn columns(&self) -> usize {
         self.1
     }
 }
 
 #[derive(Debug, PartialEq)]
-pub struct Indexed<T, L = usize> {
-    pub point: Point<L>,
+pub struct Indexed<T> {
+    pub point: Point,
     pub cell: T,
 }
 
-impl<T, L> Deref for Indexed<T, L> {
+impl<T> Deref for Indexed<T> {
     type Target = T;
 
     #[inline]
@@ -629,12 +559,12 @@ pub struct GridIterator<'a, T> {
     grid: &'a Grid<T>,
 
     /// Current position of the iterator within the grid.
-    point: Point<usize>,
+    point: Point,
 }
 
 impl<'a, T> GridIterator<'a, T> {
     /// Current iteratior position.
-    pub fn point(&self) -> Point<usize> {
+    pub fn point(&self) -> Point {
         self.point
     }
 
@@ -648,12 +578,17 @@ impl<'a, T> Iterator for GridIterator<'a, T> {
     type Item = Indexed<&'a T>;
 
     fn next(&mut self) -> Option<Self::Item> {
-        let last_col = self.grid.cols() - 1;
+        let last_column = self.grid.last_column();
+
+        // Stop once we've reached the end of the grid.
+        if self.point == Point::new(self.grid.bottommost_line(), last_column) {
+            return None;
+        }
+
         match self.point {
-            Point { line, column: col } if line == 0 && col == last_col => return None,
-            Point { column: col, .. } if (col == last_col) => {
-                self.point.line -= 1;
+            Point { column, .. } if column == last_column => {
                 self.point.column = Column(0);
+                self.point.line += 1;
             },
             _ => self.point.column += Column(1),
         }
@@ -669,15 +604,18 @@ pub trait BidirectionalIterator: Iterator {
 
 impl<'a, T> BidirectionalIterator for GridIterator<'a, T> {
     fn prev(&mut self) -> Option<Self::Item> {
-        let last_col = self.grid.cols() - 1;
+        let topmost_line = self.grid.topmost_line();
+        let last_column = self.grid.last_column();
+
+        // Stop once we've reached the end of the grid.
+        if self.point == Point::new(topmost_line, Column(0)) {
+            return None;
+        }
 
         match self.point {
-            Point { line, column: Column(0) } if line == self.grid.total_lines() - 1 => {
-                return None
-            },
             Point { column: Column(0), .. } => {
-                self.point.line += 1;
-                self.point.column = last_col;
+                self.point.column = last_column;
+                self.point.line -= 1;
             },
             _ => self.point.column -= Column(1),
         }
@@ -686,7 +624,5 @@ impl<'a, T> BidirectionalIterator for GridIterator<'a, T> {
     }
 }
 
-pub type DisplayIter<'a, T> =
-    Map<TakeWhile<GridIterator<'a, T>, DisplayIterTakeFun<'a, T>>, DisplayIterMapFun<'a, T>>;
+pub type DisplayIter<'a, T> = TakeWhile<GridIterator<'a, T>, DisplayIterTakeFun<'a, T>>;
 type DisplayIterTakeFun<'a, T> = Box<dyn Fn(&Indexed<&'a T>) -> bool>;
-type DisplayIterMapFun<'a, T> = Box<dyn FnMut(Indexed<&'a T>) -> Indexed<&'a T, Line>>;