aboutsummaryrefslogtreecommitdiff
path: root/src/grid/storage.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/grid/storage.rs')
-rw-r--r--src/grid/storage.rs651
1 files changed, 651 insertions, 0 deletions
diff --git a/src/grid/storage.rs b/src/grid/storage.rs
new file mode 100644
index 00000000..ad94cf2b
--- /dev/null
+++ b/src/grid/storage.rs
@@ -0,0 +1,651 @@
+/// Wrapper around Vec which supports fast indexing and rotation
+///
+/// The rotation implemented by grid::Storage is a simple integer addition.
+/// Compare with standard library rotation which requires rearranging items in
+/// memory.
+///
+/// As a consequence, the indexing operators need to be reimplemented for this
+/// type to account for the 0th element not always being at the start of the
+/// allocation.
+///
+/// Because certain Vec operations are no longer valid on this type, no Deref
+/// implementation is provided. Anything from Vec that should be exposed must be
+/// done so manually.
+use std::ops::{Index, IndexMut};
+use std::slice;
+
+use index::Line;
+use super::Row;
+
+/// Maximum number of invisible lines before buffer is resized
+const TRUNCATE_STEP: usize = 100;
+
+#[derive(Clone, Debug, Deserialize, Serialize)]
+pub struct Storage<T> {
+ inner: Vec<Row<T>>,
+ zero: usize,
+ visible_lines: Line,
+
+ /// Total number of lines currently active in the terminal (scrollback + visible)
+ ///
+ /// Shrinking this length allows reducing the number of lines in the scrollback buffer without
+ /// having to truncate the raw `inner` buffer.
+ /// As long as `len` is bigger than `inner`, it is also possible to grow the scrollback buffer
+ /// without any additional insertions.
+ #[serde(skip)]
+ len: usize,
+}
+
+impl<T: PartialEq> ::std::cmp::PartialEq for Storage<T> {
+ fn eq(&self, other: &Self) -> bool {
+ // Make sure length is equal
+ if self.inner.len() != other.inner.len() {
+ return false;
+ }
+
+ // Check which vec has the bigger zero
+ let (ref bigger, ref smaller) = if self.zero >= other.zero {
+ (self, other)
+ } else {
+ (other, self)
+ };
+
+ // Calculate the actual zero offset
+ let len = self.inner.len();
+ let bigger_zero = bigger.zero % len;
+ let smaller_zero = smaller.zero % len;
+
+ // Compare the slices in chunks
+ // Chunks:
+ // - Bigger zero to the end
+ // - Remaining lines in smaller zero vec
+ // - Beginning of smaller zero vec
+ //
+ // Example:
+ // Bigger Zero (6):
+ // 4 5 6 | 7 8 9 | 0 1 2 3
+ // C2 C2 C2 | C3 C3 C3 | C1 C1 C1 C1
+ // Smaller Zero (3):
+ // 7 8 9 | 0 1 2 3 | 4 5 6
+ // C3 C3 C3 | C1 C1 C1 C1 | C2 C2 C2
+ bigger.inner[bigger_zero..]
+ == smaller.inner[smaller_zero..smaller_zero + (len - bigger_zero)]
+ && bigger.inner[..bigger_zero - smaller_zero]
+ == smaller.inner[smaller_zero + (len - bigger_zero)..]
+ && bigger.inner[bigger_zero - smaller_zero..bigger_zero]
+ == smaller.inner[..smaller_zero]
+ }
+}
+
+impl<T> Storage<T> {
+ #[inline]
+ pub fn with_capacity(cap: usize, lines: Line, template: Row<T>) -> Storage<T>
+ where
+ T: Clone,
+ {
+ // Allocate all lines in the buffer, including scrollback history
+ let inner = vec![template; cap];
+
+ Storage {
+ inner,
+ zero: 0,
+ visible_lines: lines - 1,
+ len: cap,
+ }
+ }
+
+ /// Update the size of the scrollback history
+ pub fn update_history(&mut self, history_size: usize, template_row: Row<T>)
+ where
+ T: Clone,
+ {
+ let current_history = self.len - (self.visible_lines.0 + 1);
+ if history_size > current_history {
+ self.grow_lines(history_size - current_history, template_row);
+ } else if history_size < current_history {
+ self.shrink_lines(current_history - history_size);
+ }
+ }
+
+ /// Increase the number of lines in the buffer
+ pub fn grow_visible_lines(&mut self, next: Line, template_row: Row<T>)
+ where
+ T: Clone,
+ {
+ // Number of lines the buffer needs to grow
+ let growage = (next - (self.visible_lines + 1)).0;
+ self.grow_lines(growage, template_row);
+
+ // Update visible lines
+ self.visible_lines = next - 1;
+ }
+
+ /// Grow the number of lines in the buffer, filling new lines with the template
+ fn grow_lines(&mut self, growage: usize, template_row: Row<T>)
+ where
+ T: Clone,
+ {
+ // Only grow if there are not enough lines still hidden
+ let mut new_growage = 0;
+ if growage > (self.inner.len() - self.len) {
+ // Lines to grow additionally to invisible lines
+ new_growage = growage - (self.inner.len() - self.len);
+
+ // Split off the beginning of the raw inner buffer
+ let mut start_buffer = self.inner.split_off(self.zero);
+
+ // Insert new template rows at the end of the raw inner buffer
+ let mut new_lines = vec![template_row; new_growage];
+ self.inner.append(&mut new_lines);
+
+ // Add the start to the raw inner buffer again
+ self.inner.append(&mut start_buffer);
+ }
+
+ // Update raw buffer length and zero offset
+ self.zero = (self.zero + new_growage) % self.inner.len();
+ self.len += growage;
+ }
+
+ /// Decrease the number of lines in the buffer
+ pub fn shrink_visible_lines(&mut self, next: Line) {
+ // Shrink the size without removing any lines
+ let shrinkage = (self.visible_lines - (next - 1)).0;
+ self.shrink_lines(shrinkage);
+
+ // Update visible lines
+ self.visible_lines = next - 1;
+ }
+
+ // Shrink the number of lines in the buffer
+ fn shrink_lines(&mut self, shrinkage: usize) {
+ self.len -= shrinkage;
+
+ // Free memory
+ if self.inner.len() > self.len() + TRUNCATE_STEP {
+ self.truncate();
+ }
+ }
+
+ /// Truncate the invisible elements from the raw buffer
+ pub fn truncate(&mut self) {
+ // Calculate shrinkage/offset for indexing
+ let shrinkage = self.inner.len() - self.len;
+ let shrinkage_start = ::std::cmp::min(self.zero, shrinkage);
+
+ // Create two vectors with correct ordering
+ let mut split = self.inner.split_off(self.zero);
+
+ // Truncate the buffers
+ let len = self.inner.len();
+ let split_len = split.len();
+ self.inner.truncate(len - shrinkage_start);
+ split.truncate(split_len - (shrinkage - shrinkage_start));
+
+ // Merge buffers again and reset zero
+ split.append(&mut self.inner);
+ self.inner = split;
+ self.zero = 0;
+ }
+
+ #[inline]
+ pub fn len(&self) -> usize {
+ self.len
+ }
+
+ /// Compute actual index in underlying storage given the requested index.
+ fn compute_index(&self, requested: usize) -> usize {
+ debug_assert!(requested < self.len);
+ let zeroed = requested + self.zero;
+
+ // This part is critical for performance,
+ // so an if/else is used here instead of a moludo operation
+ if zeroed >= self.inner.len() {
+ zeroed - self.inner.len()
+ } else {
+ zeroed
+ }
+ }
+
+ pub fn swap_lines(&mut self, a: Line, b: Line) {
+ let offset = self.inner.len() + self.zero + *self.visible_lines;
+ let a = (offset - *a) % self.inner.len();
+ let b = (offset - *b) % self.inner.len();
+ self.inner.swap(a, b);
+ }
+
+ /// Swap implementation for Row<T>.
+ ///
+ /// Exploits the known size of Row<T> to produce a slightly more efficient
+ /// swap than going through slice::swap.
+ ///
+ /// The default implementation from swap generates 8 movups and 4 movaps
+ /// instructions. This implementation achieves the swap in only 8 movups
+ /// instructions.
+ pub fn swap(&mut self, a: usize, b: usize) {
+ assert_eq_size!(Row<T>, [u32; 8]);
+
+ let a = self.compute_index(a);
+ let b = self.compute_index(b);
+
+ unsafe {
+ // Cast to a qword array to opt out of copy restrictions and avoid
+ // drop hazards. Byte array is no good here since for whatever
+ // reason LLVM won't optimized it.
+ let a_ptr = self.inner.as_mut_ptr().offset(a as isize) as *mut u64;
+ let b_ptr = self.inner.as_mut_ptr().offset(b as isize) as *mut u64;
+
+ // Copy 1 qword at a time
+ //
+ // The optimizer unrolls this loop and vectorizes it.
+ let mut tmp: u64;
+ for i in 0..4 {
+ tmp = *a_ptr.offset(i);
+ *a_ptr.offset(i) = *b_ptr.offset(i);
+ *b_ptr.offset(i) = tmp;
+ }
+ }
+ }
+
+ /// Iterate over *all* entries in the underlying buffer
+ ///
+ /// This includes hidden entries.
+ ///
+ /// XXX This suggests that Storage is a leaky abstraction. Ultimately, this
+ /// is needed because of the grow lines functionality implemented on
+ /// this type, and maybe that's where the leak is necessitating this
+ /// accessor.
+ pub fn iter_mut_raw<'a>(&'a mut self) -> slice::IterMut<'a, Row<T>> {
+ self.inner.iter_mut()
+ }
+
+ pub fn rotate(&mut self, count: isize) {
+ debug_assert!(count.abs() as usize <= self.inner.len());
+
+ let len = self.inner.len();
+ self.zero = (self.zero as isize + count + len as isize) as usize % len;
+ }
+
+ // Fast path
+ pub fn rotate_up(&mut self, count: usize) {
+ self.zero = (self.zero + count) % self.inner.len();
+ }
+}
+
+impl<T> Index<usize> for Storage<T> {
+ type Output = Row<T>;
+ #[inline]
+ fn index(&self, index: usize) -> &Self::Output {
+ let index = self.compute_index(index); // borrowck
+ &self.inner[index]
+ }
+}
+
+impl<T> IndexMut<usize> for Storage<T> {
+ #[inline]
+ fn index_mut(&mut self, index: usize) -> &mut Self::Output {
+ let index = self.compute_index(index); // borrowck
+ &mut self.inner[index]
+ }
+}
+
+impl<T> Index<Line> for Storage<T> {
+ type Output = Row<T>;
+ #[inline]
+ fn index(&self, index: Line) -> &Self::Output {
+ let index = self.visible_lines - index;
+ &self[*index]
+ }
+}
+
+impl<T> IndexMut<Line> for Storage<T> {
+ #[inline]
+ fn index_mut(&mut self, index: Line) -> &mut Self::Output {
+ let index = self.visible_lines - index;
+ &mut self[*index]
+ }
+}
+
+#[cfg(test)]
+use index::Column;
+
+/// Grow the buffer one line at the end of the buffer
+///
+/// Before:
+/// 0: 0 <- Zero
+/// 1: 1
+/// 2: -
+/// After:
+/// 0: -
+/// 1: 0 <- Zero
+/// 2: 1
+/// 3: -
+#[test]
+fn grow_after_zero() {
+ // Setup storage area
+ let mut storage = Storage {
+ inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'-')],
+ zero: 0,
+ visible_lines: Line(2),
+ len: 3,
+ };
+
+ // Grow buffer
+ storage.grow_visible_lines(Line(4), Row::new(Column(1), &'-'));
+
+ // Make sure the result is correct
+ let expected = Storage {
+ inner: vec![Row::new(Column(1), &'-'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'-')],
+ zero: 1,
+ visible_lines: Line(0),
+ len: 4,
+ };
+ assert_eq!(storage.inner, expected.inner);
+ assert_eq!(storage.zero, expected.zero);
+ assert_eq!(storage.len, expected.len);
+}
+
+/// Grow the buffer one line at the start of the buffer
+///
+/// Before:
+/// 0: -
+/// 1: 0 <- Zero
+/// 2: 1
+/// After:
+/// 0: -
+/// 1: -
+/// 2: 0 <- Zero
+/// 3: 1
+#[test]
+fn grow_before_zero() {
+ // Setup storage area
+ let mut storage = Storage {
+ inner: vec![Row::new(Column(1), &'-'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1')],
+ zero: 1,
+ visible_lines: Line(2),
+ len: 3,
+ };
+
+ // Grow buffer
+ storage.grow_visible_lines(Line(4), Row::new(Column(1), &'-'));
+
+ // Make sure the result is correct
+ let expected = Storage {
+ inner: vec![Row::new(Column(1), &'-'), Row::new(Column(1), &'-'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1')],
+ zero: 2,
+ visible_lines: Line(0),
+ len: 4,
+ };
+ assert_eq!(storage.inner, expected.inner);
+ assert_eq!(storage.zero, expected.zero);
+ assert_eq!(storage.len, expected.len);
+}
+
+/// Shrink the buffer one line at the start of the buffer
+///
+/// Before:
+/// 0: 2
+/// 1: 0 <- Zero
+/// 2: 1
+/// After:
+/// 0: 2 <- Hidden
+/// 0: 0 <- Zero
+/// 1: 1
+#[test]
+fn shrink_before_zero() {
+ // Setup storage area
+ let mut storage = Storage {
+ inner: vec![Row::new(Column(1), &'2'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1')],
+ zero: 1,
+ visible_lines: Line(2),
+ len: 3,
+ };
+
+ // Shrink buffer
+ storage.shrink_visible_lines(Line(2));
+
+ // Make sure the result is correct
+ let expected = Storage {
+ inner: vec![Row::new(Column(1), &'2'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1')],
+ zero: 1,
+ visible_lines: Line(0),
+ len: 2,
+ };
+ assert_eq!(storage.inner, expected.inner);
+ assert_eq!(storage.zero, expected.zero);
+ assert_eq!(storage.len, expected.len);
+}
+
+/// Shrink the buffer one line at the end of the buffer
+///
+/// Before:
+/// 0: 0 <- Zero
+/// 1: 1
+/// 2: 2
+/// After:
+/// 0: 0 <- Zero
+/// 1: 1
+/// 2: 2 <- Hidden
+#[test]
+fn shrink_after_zero() {
+ // Setup storage area
+ let mut storage = Storage {
+ inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'2')],
+ zero: 0,
+ visible_lines: Line(2),
+ len: 3,
+ };
+
+ // Shrink buffer
+ storage.shrink_visible_lines(Line(2));
+
+ // Make sure the result is correct
+ let expected = Storage {
+ inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'2')],
+ zero: 0,
+ visible_lines: Line(0),
+ len: 2,
+ };
+ assert_eq!(storage.inner, expected.inner);
+ assert_eq!(storage.zero, expected.zero);
+ assert_eq!(storage.len, expected.len);
+}
+
+/// Shrink the buffer at the start and end of the buffer
+///
+/// Before:
+/// 0: 4
+/// 1: 5
+/// 2: 0 <- Zero
+/// 3: 1
+/// 4: 2
+/// 5: 3
+/// After:
+/// 0: 4 <- Hidden
+/// 1: 5 <- Hidden
+/// 2: 0 <- Zero
+/// 3: 1
+/// 4: 2 <- Hidden
+/// 5: 3 <- Hidden
+#[test]
+fn shrink_before_and_after_zero() {
+ // Setup storage area
+ let mut storage = Storage {
+ inner: vec![Row::new(Column(1), &'4'), Row::new(Column(1), &'5'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'2'), Row::new(Column(1), &'3')],
+ zero: 2,
+ visible_lines: Line(5),
+ len: 6,
+ };
+
+ // Shrink buffer
+ storage.shrink_visible_lines(Line(2));
+
+ // Make sure the result is correct
+ let expected = Storage {
+ inner: vec![Row::new(Column(1), &'4'), Row::new(Column(1), &'5'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'2'), Row::new(Column(1), &'3')],
+ zero: 2,
+ visible_lines: Line(0),
+ len: 2,
+ };
+ assert_eq!(storage.inner, expected.inner);
+ assert_eq!(storage.zero, expected.zero);
+ assert_eq!(storage.len, expected.len);
+}
+
+/// Check that when truncating all hidden lines are removed from the raw buffer
+///
+/// Before:
+/// 0: 4 <- Hidden
+/// 1: 5 <- Hidden
+/// 2: 0 <- Zero
+/// 3: 1
+/// 4: 2 <- Hidden
+/// 5: 3 <- Hidden
+/// After:
+/// 0: 0 <- Zero
+/// 1: 1
+#[test]
+fn truncate_invisible_lines() {
+ // Setup storage area
+ let mut storage = Storage {
+ inner: vec![Row::new(Column(1), &'4'), Row::new(Column(1), &'5'), Row::new(Column(1), &'0'), Row::new(Column(1), &'1'), Row::new(Column(1), &'2'), Row::new(Column(1), &'3')],
+ zero: 2,
+ visible_lines: Line(1),
+ len: 2,
+ };
+
+ // Truncate buffer
+ storage.truncate();
+
+ // Make sure the result is correct
+ let expected = Storage {
+ inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1')],
+ zero: 0,
+ visible_lines: Line(1),
+ len: 2,
+ };
+ assert_eq!(storage.visible_lines, expected.visible_lines);
+ assert_eq!(storage.inner, expected.inner);
+ assert_eq!(storage.zero, expected.zero);
+ assert_eq!(storage.len, expected.len);
+}
+
+/// Truncate buffer only at the beginning
+///
+/// Before:
+/// 0: 1
+/// 1: 2 <- Hidden
+/// 2: 0 <- Zero
+/// After:
+/// 0: 1
+/// 0: 0 <- Zero
+#[test]
+fn truncate_invisible_lines_beginning() {
+ // Setup storage area
+ let mut storage = Storage {
+ inner: vec![Row::new(Column(1), &'1'), Row::new(Column(1), &'2'), Row::new(Column(1), &'0')],
+ zero: 2,
+ visible_lines: Line(1),
+ len: 2,
+ };
+
+ // Truncate buffer
+ storage.truncate();
+
+ // Make sure the result is correct
+ let expected = Storage {
+ inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1')],
+ zero: 0,
+ visible_lines: Line(1),
+ len: 2,
+ };
+ assert_eq!(storage.visible_lines, expected.visible_lines);
+ assert_eq!(storage.inner, expected.inner);
+ assert_eq!(storage.zero, expected.zero);
+ assert_eq!(storage.len, expected.len);
+}
+
+/// First shrink the buffer and then grow it again
+///
+/// Before:
+/// 0: 4
+/// 1: 5
+/// 2: 0 <- Zero
+/// 3: 1
+/// 4: 2
+/// 5: 3
+/// After Shrinking:
+/// 0: 4 <- Hidden
+/// 1: 5 <- Hidden
+/// 2: 0 <- Zero
+/// 3: 1
+/// 4: 2
+/// 5: 3 <- Hidden
+/// After Growing:
+/// 0: 4
+/// 1: 5
+/// 2: -
+/// 3: 0 <- Zero
+/// 4: 1
+/// 5: 2
+/// 6: 3
+#[test]
+fn shrink_then_grow() {
+ // Setup storage area
+ let mut storage = Storage {
+ inner: vec![
+ Row::new(Column(1), &'4'),
+ Row::new(Column(1), &'5'),
+ Row::new(Column(1), &'0'),
+ Row::new(Column(1), &'1'),
+ Row::new(Column(1), &'2'),
+ Row::new(Column(1), &'3'),
+ ],
+ zero: 2,
+ visible_lines: Line(0),
+ len: 6,
+ };
+
+ // Shrink buffer
+ storage.shrink_lines(3);
+
+ // Make sure the result after shrinking is correct
+ let shrinking_expected = Storage {
+ inner: vec![
+ Row::new(Column(1), &'4'),
+ Row::new(Column(1), &'5'),
+ Row::new(Column(1), &'0'),
+ Row::new(Column(1), &'1'),
+ Row::new(Column(1), &'2'),
+ Row::new(Column(1), &'3'),
+ ],
+ zero: 2,
+ visible_lines: Line(0),
+ len: 3,
+ };
+ assert_eq!(storage.inner, shrinking_expected.inner);
+ assert_eq!(storage.zero, shrinking_expected.zero);
+ assert_eq!(storage.len, shrinking_expected.len);
+
+ // Grow buffer
+ storage.grow_lines(4, Row::new(Column(1), &'-'));
+
+ // Make sure the result after shrinking is correct
+ let growing_expected = Storage {
+ inner: vec![
+ Row::new(Column(1), &'4'),
+ Row::new(Column(1), &'5'),
+ Row::new(Column(1), &'-'),
+ Row::new(Column(1), &'0'),
+ Row::new(Column(1), &'1'),
+ Row::new(Column(1), &'2'),
+ Row::new(Column(1), &'3'),
+ ],
+ zero: 3,
+ visible_lines: Line(0),
+ len: 7,
+ };
+ assert_eq!(storage.inner, growing_expected.inner);
+ assert_eq!(storage.zero, growing_expected.zero);
+ assert_eq!(storage.len, growing_expected.len);
+}
7apu2bq3rhoylwmucxizk54afw5jyda7pho4j5zdcqpwkufke7zdzwad.onion