| /// 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 grid::Row; |
| |
| /// Maximum number of invisible lines before buffer is resized |
| const TRUNCATE_STEP: usize = 100; |
| |
| pub trait Swap { |
| fn swap(&mut self, _: usize, _: usize); |
| } |
| |
| impl<T> Swap for Storage<T> { |
| /// Swap two lines in raw buffer |
| /// |
| /// # Panics |
| /// |
| /// `swap` will panic if either `a` or `b` are out-of-bounds of the |
| /// underlying storage. |
| default fn swap(&mut self, a: usize, b: usize) { |
| let a = self.compute_index(a); |
| let b = self.compute_index(b); |
| |
| self.inner.swap(a, b); |
| } |
| } |
| |
| impl<T> Swap for Storage<Row<T>> { |
| /// Custom 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. |
| fn swap(&mut self, a: usize, b: usize) { |
| debug_assert!(::std::mem::size_of::<Row<T>>() == 32); |
| |
| 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; |
| } |
| } |
| } |
| } |
| |
| #[derive(Clone, Debug, Deserialize, Serialize)] |
| pub struct Storage<T> { |
| inner: Vec<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: T) -> Storage<T> |
| where |
| T: Clone, |
| { |
| // Allocate all lines in the buffer, including scrollback history |
| // |
| // TODO (jwilm) Allocating each line at this point is expensive and |
| // delays startup. A nice solution might be having `Row` delay |
| // allocation until it's actually used. |
| let inner = vec![template; cap]; |
| Storage { |
| inner, |
| zero: 0, |
| visible_lines: lines - 1, |
| len: cap, |
| } |
| } |
| |
| /// Increase the number of lines in the buffer |
| pub fn grow_visible_lines(&mut self, next: Line, template_row: T) |
| where |
| T: Clone, |
| { |
| // Number of lines the buffer needs to grow |
| let lines_to_grow = (next - (self.visible_lines + 1)).0; |
| |
| // Only grow if there are not enough lines still hidden |
| if lines_to_grow > (self.inner.len() - self.len) { |
| // Lines to grow additionally to invisible lines |
| let new_lines_to_grow = lines_to_grow - (self.inner.len() - self.len); |
| |
| // Get the position of the start of the buffer |
| let offset = self.zero % self.inner.len(); |
| |
| // Split off the beginning of the raw inner buffer |
| let mut start_buffer = self.inner.split_off(offset); |
| |
| // Insert new template rows at the end of the raw inner buffer |
| let mut new_lines = vec![template_row; new_lines_to_grow]; |
| self.inner.append(&mut new_lines); |
| |
| // Add the start to the raw inner buffer again |
| self.inner.append(&mut start_buffer); |
| |
| // Update the zero to after the lines we just inserted |
| self.zero = offset + lines_to_grow; |
| } |
| |
| // Update visible lines and raw buffer length |
| self.len += lines_to_grow; |
| self.visible_lines = next - 1; |
| } |
| |
| /// Decrease the number of lines in the buffer |
| pub fn shrink_visible_lines(&mut self, next: Line) { |
| // Shrink the size without removing any lines |
| self.len -= (self.visible_lines - (next - 1)).0; |
| |
| // Update visible lines |
| self.visible_lines = next - 1; |
| |
| // 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 offset = self.zero % self.inner.len(); |
| let shrinkage = self.inner.len() - self.len; |
| let shrinkage_start = ::std::cmp::min(offset, shrinkage); |
| |
| // Create two vectors with correct ordering |
| let mut split = self.inner.split_off(offset); |
| |
| // 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 |
| self.zero = self.inner.len(); |
| self.inner.append(&mut split); |
| } |
| |
| #[inline] |
| pub fn len(&self) -> usize { |
| self.len |
| } |
| |
| #[inline] |
| pub fn raw_len(&self) -> usize { |
| self.inner.len() |
| } |
| |
| /// Compute actual index in underlying storage given the requested index. |
| fn compute_index(&self, requested: usize) -> usize { |
| use ::std::hint::unreachable_unchecked; |
| |
| // This prevents an extra branch being inserted which checks for the |
| // divisor to be zero thus making a % b generate equivalent code as in C |
| if self.inner.len() == 0 { |
| unsafe { unreachable_unchecked(); } |
| } |
| |
| (requested + self.zero) % self.inner.len() |
| } |
| |
| #[inline] |
| pub fn line_offset(&self) -> usize { |
| self.inner.len() + self.zero + *self.visible_lines |
| } |
| |
| pub fn compute_line_index(&self, a: Line) -> usize { |
| (self.line_offset() - *a) % self.inner.len() |
| } |
| |
| 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); |
| } |
| |
| /// Iterator over *logical* entries in the storage |
| /// |
| /// This *does not* iterate over hidden entries. |
| pub fn iter_mut(&mut self) -> IterMut<T> { |
| IterMut { storage: self, index: 0 } |
| } |
| |
| /// 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, 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 = T; |
| #[inline] |
| fn index(&self, index: usize) -> &T { |
| 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 T { |
| let index = self.compute_index(index); // borrowck |
| &mut self.inner[index] |
| } |
| } |
| |
| impl<T> Index<Line> for Storage<T> { |
| type Output = T; |
| #[inline] |
| fn index(&self, index: Line) -> &T { |
| let index = self.visible_lines - index; |
| &self[*index] |
| } |
| } |
| |
| impl<T> IndexMut<Line> for Storage<T> { |
| #[inline] |
| fn index_mut(&mut self, index: Line) -> &mut T { |
| let index = self.visible_lines - index; |
| &mut self[*index] |
| } |
| } |
| |
| pub struct IterMut<'a, T: 'a> { |
| storage: &'a mut Storage<T>, |
| index: usize, |
| } |
| |
| impl<'a, T: 'a> Iterator for IterMut<'a, T> { |
| type Item = &'a mut T; |
| |
| fn next(&mut self) -> Option<Self::Item> { |
| if self.index == self.storage.len() { |
| None |
| } else { |
| let index = self.index; |
| self.index += 1; |
| |
| unsafe { |
| Some(&mut *(&mut self.storage[index] as *mut _)) |
| } |
| } |
| } |
| } |
| |
| /// 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!["0", "1", "-"], |
| zero: 0, |
| visible_lines: Line(2), |
| len: 3, |
| }; |
| |
| // Grow buffer |
| storage.grow_visible_lines(Line(4), "-"); |
| |
| // Make sure the result is correct |
| let expected = Storage { |
| inner: vec!["-", "0", "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!["-", "0", "1"], |
| zero: 1, |
| visible_lines: Line(2), |
| len: 3, |
| }; |
| |
| // Grow buffer |
| storage.grow_visible_lines(Line(4), "-"); |
| |
| // Make sure the result is correct |
| let expected = Storage { |
| inner: vec!["-", "-", "0", "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!["2", "0", "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!["2", "0", "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!["0", "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!["0", "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!["4", "5", "0", "1", "2", "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!["4", "5", "0", "1", "2", "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!["4", "5", "0", "1", "2", "3"], |
| zero: 2, |
| visible_lines: Line(1), |
| len: 2, |
| }; |
| |
| // Truncate buffer |
| storage.truncate(); |
| |
| // Make sure the result is correct |
| let expected = Storage { |
| inner: vec!["0", "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!["1", "2", "0"], |
| zero: 2, |
| visible_lines: Line(1), |
| len: 2, |
| }; |
| |
| // Truncate buffer |
| storage.truncate(); |
| |
| // Make sure the result is correct |
| let expected = Storage { |
| inner: vec!["1", "0"], |
| zero: 1, |
| 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); |
| } |