From f13685918ff42c3a919f8a84fea64a144979d13a Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Sun, 14 Jan 2018 21:51:56 -0800 Subject: WIP optimize scroll in region This intends to optimize the case where the top of the scrolling region is the top of the screen. In theory, scrolling in this case can be optimized to shifting the start/end of the visible region, and then rearranging any lines that were not supposed to be scrolled (at the bottom of the region). However, this didn't produce quite the speedup I expected. --- src/grid/storage.rs | 129 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 129 insertions(+) create mode 100644 src/grid/storage.rs (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs new file mode 100644 index 00000000..f5c2d87e --- /dev/null +++ b/src/grid/storage.rs @@ -0,0 +1,129 @@ +/// 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}; + +#[derive(Clone, Debug, Deserialize, Serialize, Eq, PartialEq)] +pub struct Storage { + inner: Vec, + zero: usize, +} + +impl Storage { + #[inline] + pub fn with_capacity(cap: usize) -> Storage { + Storage { + inner: Vec::with_capacity(cap), + zero: 0 + } + } + + #[inline] + pub fn push(&mut self, item: T) { + self.inner.push(item) + } + + #[inline] + pub fn pop(&mut self) -> Option { + self.inner.pop() + } + + #[inline] + pub fn len(&self) -> usize { + self.inner.len() + } + + /// Compute actual index in underlying storage given the requested index. + #[inline] + fn compute_index(&self, requested: usize) -> usize { + (requested + self.zero) % self.len() + } + + pub 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); + } + + pub fn iter(&self) -> Iter { + Iter { storage: self, index: 0 } + } + + pub fn iter_mut(&mut self) -> IterMut { + IterMut { storage: self, index: 0 } + } + + pub fn rotate(&mut self, count: isize) { + let len = self.len(); + assert!(count.abs() as usize <= len); + self.zero += (count + len as isize) as usize % len; + } +} + +impl Index for Storage { + type Output = T; + #[inline] + fn index(&self, index: usize) -> &T { + let index = self.compute_index(index); // borrowck + &self.inner[index] + } +} + +impl IndexMut for Storage { + #[inline] + fn index_mut(&mut self, index: usize) -> &mut T { + let index = self.compute_index(index); // borrowck + &mut self.inner[index] + } +} + +pub struct Iter<'a, T: 'a> { + storage: &'a Storage, + index: usize, +} + +pub struct IterMut<'a, T: 'a> { + storage: &'a mut Storage, + index: usize, +} + +impl<'a, T: 'a> Iterator for Iter<'a, T> { + type Item = &'a T; + + fn next(&mut self) -> Option { + if self.index == self.storage.len() { + None + } else { + let res = Some(&self.storage[self.index]); + self.index += 1; + res + } + } +} + +impl<'a, T: 'a> Iterator for IterMut<'a, T> { + type Item = &'a mut T; + + fn next(&mut self) -> Option { + if self.index == self.storage.len() { + None + } else { + let index = self.index; + self.index += 1; + + unsafe { + Some(&mut *(&mut self.storage[index] as *mut _)) + } + } + } +} -- cgit From 92b11cfa43c3a5d32b461e43975146b27eb71ccd Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Sun, 11 Feb 2018 10:07:33 -0800 Subject: Minor improvements --- src/grid/storage.rs | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index f5c2d87e..49f3d26c 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -68,6 +68,11 @@ impl Storage { assert!(count.abs() as usize <= len); self.zero += (count + len as isize) as usize % len; } + + // Fast path + pub fn rotate_up(&mut self, count: usize) { + self.zero = (self.zero + count) % self.len(); + } } impl Index for Storage { -- cgit From 84769ce170bd529989698bbbb4ee902e72569cbe Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Sun, 11 Feb 2018 12:27:23 -0800 Subject: Remove some unused impls --- src/grid/storage.rs | 23 ----------------------- 1 file changed, 23 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 49f3d26c..3c64f700 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -55,10 +55,6 @@ impl Storage { self.inner.swap(a, b); } - pub fn iter(&self) -> Iter { - Iter { storage: self, index: 0 } - } - pub fn iter_mut(&mut self) -> IterMut { IterMut { storage: self, index: 0 } } @@ -92,30 +88,11 @@ impl IndexMut for Storage { } } -pub struct Iter<'a, T: 'a> { - storage: &'a Storage, - index: usize, -} - pub struct IterMut<'a, T: 'a> { storage: &'a mut Storage, index: usize, } -impl<'a, T: 'a> Iterator for Iter<'a, T> { - type Item = &'a T; - - fn next(&mut self) -> Option { - if self.index == self.storage.len() { - None - } else { - let res = Some(&self.storage[self.index]); - self.index += 1; - res - } - } -} - impl<'a, T: 'a> Iterator for IterMut<'a, T> { type Item = &'a mut T; -- cgit From 45c2b3fbf72fa6dfd36bee590e64314c6da7c6c2 Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Thu, 15 Feb 2018 18:35:49 -0800 Subject: checkpoint: very basic scrolling works Things that do not work - Limiting how far back in the buffer it's possible to scroll - Selections (need to transform to buffer offsets) --- src/grid/storage.rs | 40 ++++++++++++++++++++++++++++++++++++++-- 1 file changed, 38 insertions(+), 2 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 3c64f700..b4228687 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -13,21 +13,34 @@ /// done so manually. use std::ops::{Index, IndexMut}; +use index::Line; + #[derive(Clone, Debug, Deserialize, Serialize, Eq, PartialEq)] pub struct Storage { inner: Vec, zero: usize, + visible_lines: Line, } impl Storage { #[inline] - pub fn with_capacity(cap: usize) -> Storage { + pub fn with_capacity(cap: usize, lines: Line) -> Storage { Storage { inner: Vec::with_capacity(cap), - zero: 0 + zero: 0, + visible_lines: lines - 1, } } + #[inline] + pub fn capacity(&self) -> usize { + self.inner.capacity() + } + + pub fn set_visible_lines(&mut self, next: Line) { + self.visible_lines = next - 1; + } + #[inline] pub fn push(&mut self, item: T) { self.inner.push(item) @@ -55,6 +68,12 @@ impl Storage { self.inner.swap(a, b); } + pub fn swap_lines(&mut self, a: Line, b: Line) { + let a = self.visible_lines - a; + let b = self.visible_lines - b; + self.swap(*a, *b); + } + pub fn iter_mut(&mut self) -> IterMut { IterMut { storage: self, index: 0 } } @@ -88,6 +107,23 @@ impl IndexMut for Storage { } } +impl Index for Storage { + type Output = T; + #[inline] + fn index(&self, index: Line) -> &T { + let index = self.visible_lines - index; + &self[*index] + } +} + +impl IndexMut for Storage { + #[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, index: usize, -- cgit From f67b17ca7b2e0e47ad5eee24d8b86800c61139b4 Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Thu, 15 Feb 2018 19:34:23 -0800 Subject: wip fix scroll_down --- src/grid/storage.rs | 1 + 1 file changed, 1 insertion(+) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index b4228687..0ca2f525 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -69,6 +69,7 @@ impl Storage { } pub fn swap_lines(&mut self, a: Line, b: Line) { + println!("visible: {}, a: {}, b: {}", self.visible_lines, a, b); let a = self.visible_lines - a; let b = self.visible_lines - b; self.swap(*a, *b); -- cgit From 54d50ed3be810861d3c2fa500c3fcc8e802198d9 Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Fri, 16 Feb 2018 18:35:54 -0800 Subject: Fix scrolling backwards in tmux --- src/grid/storage.rs | 11 +++++++---- 1 file changed, 7 insertions(+), 4 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 0ca2f525..1588b006 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -62,6 +62,10 @@ impl Storage { (requested + self.zero) % self.len() } + fn compute_line_index(&self, requested: Line) -> usize { + ((self.len() + self.zero + *self.visible_lines) - *requested) % self.len() + } + pub fn swap(&mut self, a: usize, b: usize) { let a = self.compute_index(a); let b = self.compute_index(b); @@ -69,10 +73,9 @@ impl Storage { } pub fn swap_lines(&mut self, a: Line, b: Line) { - println!("visible: {}, a: {}, b: {}", self.visible_lines, a, b); - let a = self.visible_lines - a; - let b = self.visible_lines - b; - self.swap(*a, *b); + let a = self.compute_line_index(a); + let b = self.compute_line_index(b); + self.inner.swap(a, b); } pub fn iter_mut(&mut self) -> IterMut { -- cgit From b0f655ac85ab6d86e9e482cbb9035200c6f08d40 Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Fri, 9 Mar 2018 13:49:47 -0800 Subject: Make tests compile again Some tests are still not passing, though. A migration script was added to migrate serialized grids from pre-scrollback to the current format. The script is included with this commit for completeness, posterity, and as an example to be used in the future. A few tests in grid/tests.rs were removed due to becoming irrelevant. --- src/grid/storage.rs | 14 ++++++++++++-- 1 file changed, 12 insertions(+), 2 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 1588b006..0f1ba9c5 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -13,15 +13,25 @@ /// done so manually. use std::ops::{Index, IndexMut}; -use index::Line; +use index::{IndexRange, Line}; -#[derive(Clone, Debug, Deserialize, Serialize, Eq, PartialEq)] +#[derive(Clone, Debug, Deserialize, Serialize)] pub struct Storage { inner: Vec, zero: usize, visible_lines: Line, } +impl ::std::cmp::PartialEq for Storage { + fn eq(&self, other: &Self) -> bool { + let mut equal = true; + for i in IndexRange(Line(0) .. self.visible_lines) { + equal = equal && (self[i] == other[i]) + } + equal + } +} + impl Storage { #[inline] pub fn with_capacity(cap: usize, lines: Line) -> Storage { -- cgit From b19045da66899999856c6b2cc6707b60c607660a Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Mon, 2 Apr 2018 08:44:54 -0700 Subject: Fix BCE ref tests BCE was broken in attempt to optimize row clearing. The fix is to revert to passing in the current cursor state when clearing. --- src/grid/storage.rs | 11 ----------- 1 file changed, 11 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 0f1ba9c5..b620b9c0 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -56,11 +56,6 @@ impl Storage { self.inner.push(item) } - #[inline] - pub fn pop(&mut self) -> Option { - self.inner.pop() - } - #[inline] pub fn len(&self) -> usize { self.inner.len() @@ -76,12 +71,6 @@ impl Storage { ((self.len() + self.zero + *self.visible_lines) - *requested) % self.len() } - pub 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); - } - pub fn swap_lines(&mut self, a: Line, b: Line) { let a = self.compute_line_index(a); let b = self.compute_line_index(b); -- cgit From e615d112fb9fffe46121bd9068498b07c4733fa8 Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Sat, 7 Apr 2018 01:50:14 +0200 Subject: Fix scrollback history size 0 bug There was an issue where alacritty would panic whenever the scrollback history size is set to 0, this fixes that issue. The panic was caused by a substraction with unsigned integers which was underflowing, this has been fixed to use `saturating_sub`. After that was fixed there was still a bug where scrollback would not behave correctly because the number of lines in the grid was decided at startup. This has been adapted so whenever the size of the terminal changes, the scrollback history and grid adapts to make sure the number of lines in the terminal is always the number of visible lines plus the amount of scrollback lines configured in the config file. This fixes #1150. --- src/grid/storage.rs | 11 +++++++++++ 1 file changed, 11 insertions(+) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index b620b9c0..cc32d6d1 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -48,6 +48,17 @@ impl Storage { } pub fn set_visible_lines(&mut self, next: Line) { + // Change capacity to fit scrollback + screen size + if next > self.visible_lines + 1 { + self.inner.reserve_exact((next - (self.visible_lines + 1)).0); + } else if next < self.visible_lines + 1 { + let shrinkage = (self.visible_lines + 1 - next).0; + let new_size = self.inner.capacity() - shrinkage; + self.inner.truncate(new_size); + self.inner.shrink_to_fit(); + } + + // Update visible lines self.visible_lines = next - 1; } -- cgit From fe749cf0adee1be93fd3473f6d3533fbe892e3dc Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Sun, 22 Apr 2018 14:39:55 +0200 Subject: Fix order of lines after resize There was an issue where the lines would be messed up when the terminal was resized, this was because lines were just added/removed at the end of the buffer instead of the actual end of the terminal (since the end of the terminal might be in the middle of the buffer). This has been fixed by relying on `self.zero` to determine the position of the start of the terminal and then calculating where lines have to be inserted/removed. Some tests have also been added with documentation that should make it a little easier to understand how the process works and how the raw buffer is layed out. This should all work no matter how big the scrollback history and even when the currenty viewport is not at the bottom of the terminal output. --- src/grid/storage.rs | 214 +++++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 205 insertions(+), 9 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index cc32d6d1..f6fcc8f3 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -47,15 +47,49 @@ impl Storage { self.inner.capacity() } - pub fn set_visible_lines(&mut self, next: Line) { - // Change capacity to fit scrollback + screen size - if next > self.visible_lines + 1 { - self.inner.reserve_exact((next - (self.visible_lines + 1)).0); - } else if next < self.visible_lines + 1 { - let shrinkage = (self.visible_lines + 1 - next).0; - let new_size = self.inner.capacity() - shrinkage; - self.inner.truncate(new_size); - self.inner.shrink_to_fit(); + /// Increase the number of lines in the buffer + pub fn grow_visible_lines(&mut self, next: Line, template_row: T) + where + T: Clone, + { + // Calculate insert position (before the first line) + let offset = self.zero % self.inner.len(); + + // Insert new template row for every line grown + let lines_to_grow = (next - (self.visible_lines + 1)).0; + for _ in 0..lines_to_grow { + self.inner.insert(offset, template_row.clone()); + } + + // Set zero to old zero + lines grown + self.zero = offset + lines_to_grow; + + // Update visible lines + self.visible_lines = next - 1; + } + + /// Decrease the number of lines in the buffer + pub fn shrink_visible_lines(&mut self, next: Line) { + // Calculate shrinkage and last line of buffer + let shrinkage = (self.visible_lines + 1 - next).0; + let offset = (self.zero + self.inner.len() - 1) % self.inner.len(); + + // Generate range of lines that have to be deleted before the zero line + let start = offset.saturating_sub(shrinkage - 1); + let shrink_before = start..=offset; + + // Generate range of lines that have to be deleted after the zero line + let shrink_after = (self.inner.len() + offset + 1 - shrinkage)..self.inner.len(); + + // Delete all lines in reverse order + for i in shrink_before.chain(shrink_after).rev() { + self.inner.remove(i); + } + + // Check if zero has moved (not the first line in the buffer) + if self.zero % (self.inner.len() + shrinkage) != 0 { + // Set zero to the first deleted line in the buffer + self.zero = start; } // Update visible lines @@ -159,3 +193,165 @@ impl<'a, T: 'a> Iterator for IterMut<'a, T> { } } } + +/// 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), + }; + + // 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), + }; + assert_eq!(storage.inner, expected.inner); + assert_eq!(storage.zero, expected.zero); +} + +/// 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), + }; + + // 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), + }; + assert_eq!(storage.inner, expected.inner); + assert_eq!(storage.zero, expected.zero); +} + +/// Shrink the buffer one line at the start of the buffer +/// +/// Before: +/// 0: 2 +/// 1: 0 <- Zero +/// 2: 1 +/// After: +/// 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), + }; + + // Shrink buffer + storage.shrink_visible_lines(Line(2)); + + // Make sure the result is correct + let expected = Storage { + inner: vec!["0", "1"], + zero: 0, + visible_lines: Line(0), + }; + assert_eq!(storage.inner, expected.inner); + assert_eq!(storage.zero, expected.zero); +} + +/// 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 +#[test] +fn shrink_after_zero() { + // Setup storage area + let mut storage = Storage { + inner: vec!["0", "1", "2"], + zero: 0, + visible_lines: Line(2), + }; + + // Shrink buffer + storage.shrink_visible_lines(Line(2)); + + // Make sure the result is correct + let expected = Storage { + inner: vec!["0", "1"], + zero: 0, + visible_lines: Line(0), + }; + assert_eq!(storage.inner, expected.inner); + assert_eq!(storage.zero, expected.zero); +} + +/// 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: 0 <- Zero +/// 1: 1 +#[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), + }; + + // Shrink buffer + storage.shrink_visible_lines(Line(2)); + + // Make sure the result is correct + let expected = Storage { + inner: vec!["0", "1"], + zero: 0, + visible_lines: Line(0), + }; + assert_eq!(storage.inner, expected.inner); + assert_eq!(storage.zero, expected.zero); +} -- cgit From 0d900cdf69d0d53b52c44b302907380ad4d3735d Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Tue, 24 Apr 2018 09:39:46 -0700 Subject: Compile on stable --- src/grid/storage.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index f6fcc8f3..fb66b0c3 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -76,7 +76,7 @@ impl Storage { // Generate range of lines that have to be deleted before the zero line let start = offset.saturating_sub(shrinkage - 1); - let shrink_before = start..=offset; + let shrink_before = start..(offset + 1); // Generate range of lines that have to be deleted after the zero line let shrink_after = (self.inner.len() + offset + 1 - shrinkage)..self.inner.len(); -- cgit From 2234234ca9a2ab0d7eccd46893cbe6799b051aba Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Sat, 14 Apr 2018 17:21:48 +0200 Subject: Enable history comparison in ref-tests Previously ref-tests just ignored the scrollback history to keep the old tests working, this would lead to new tests which rely on scrollback history to succeeed even though they should not. This has been fixed and it is now possible to create ref-tests with and without scrollback history. When available the scrollback history is compared, but the old tests still work without having to adjust them. This fixes #1244. --- src/grid/storage.rs | 10 ---------- 1 file changed, 10 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index fb66b0c3..50ce6aa5 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -22,16 +22,6 @@ pub struct Storage { visible_lines: Line, } -impl ::std::cmp::PartialEq for Storage { - fn eq(&self, other: &Self) -> bool { - let mut equal = true; - for i in IndexRange(Line(0) .. self.visible_lines) { - equal = equal && (self[i] == other[i]) - } - equal - } -} - impl Storage { #[inline] pub fn with_capacity(cap: usize, lines: Line) -> Storage { -- cgit From d39370514a127faa05832701bb4a56fc6811de9d Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Sat, 14 Apr 2018 17:37:57 +0200 Subject: Reset grid content when running `reset` In the current scrollback PR the `reset` command does not affect the scrollback history. To make sure the terminal is properly reset, it should clear the scrollback history. This commit fixes this by creating a new and empty grid whenever `reset` is executed. It takes the current dimensions and history size from the old grid. Right now there's an empty ref-test called `grid_reset` without any content, this should be implemented once #1244 is resolved. This fixes #1242. --- src/grid/storage.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 50ce6aa5..66e0ccc8 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -13,7 +13,7 @@ /// done so manually. use std::ops::{Index, IndexMut}; -use index::{IndexRange, Line}; +use index::Line; #[derive(Clone, Debug, Deserialize, Serialize)] pub struct Storage { -- cgit From 8168d85a21b1a67b9cf25808c4e3e01f7437b50d Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Sat, 28 Apr 2018 16:15:21 +0200 Subject: Improve storage comparison algorithm Instead of iterating over the raw storage vector because the offsets don't allow direct comparison, the comparison is now done in chunks. Based on benchmarking this is a lot more efficient than using split_off + append or iterating over the elements of the buffer. The `history_size` field has also been removed from the storage structure because it can be easily calculated by substracting the number of visible lines from the length of the raw storage vector. --- src/grid/storage.rs | 41 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 41 insertions(+) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 66e0ccc8..323d8ec4 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -22,6 +22,47 @@ pub struct Storage { visible_lines: Line, } +impl ::std::cmp::PartialEq for Storage { + 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 Storage { #[inline] pub fn with_capacity(cap: usize, lines: Line) -> Storage { -- cgit From a3c6c1db63af8dea62146739dc183c05b26b56d6 Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Mon, 30 Apr 2018 00:22:15 +0200 Subject: Improve the resizing implementation Until now the resizing implementation with scrollback has been really inefficient because it made use of APIs like `Vec::insert`. This has been rewored with this commit. A `len` property has been added to the `Storage` struct which keeps track of the actual length of the raw buffer. This has changed both shrinking and growing implementations. With shrinking, no more lines are removed, only the `len` property is updated to set all lines shrunk to an "invisible" state which cannot be accessed from the outside, this effectively changes it to a O(1) operation. The only issue with this would be memory consumption, but since the maximum shrinkage is the number of lines on one screen, it should be a rather small impacte (probabl <100 lines usually). If desired it would be possible to change this to shrink the raw inner buffer whenever there are more than X lines hidden. Growing now works in a similar way to shrinking, if the "invisible" lines are enough, no new lines are inserted but rather the invisible buffer is made visible again. Otherwise the amount of lines that still needs to be inserted is added to the raw buffer, but instead of the inefficient `Vec::insert`, the `Vec::push` API is used now. This fixes #1271. --- src/grid/storage.rs | 108 +++++++++++++++++++++++++++++----------------------- 1 file changed, 61 insertions(+), 47 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 323d8ec4..a50e8076 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -20,6 +20,8 @@ pub struct Storage { inner: Vec, zero: usize, visible_lines: Line, + #[serde(skip)] + len: usize, } impl ::std::cmp::PartialEq for Storage { @@ -70,58 +72,49 @@ impl Storage { inner: Vec::with_capacity(cap), zero: 0, visible_lines: lines - 1, + len: cap, } } - #[inline] - pub fn capacity(&self) -> usize { - self.inner.capacity() - } - /// Increase the number of lines in the buffer pub fn grow_visible_lines(&mut self, next: Line, template_row: T) where T: Clone, { - // Calculate insert position (before the first line) - let offset = self.zero % self.inner.len(); - - // Insert new template row for every line grown + // Number of lines the buffer needs to grow let lines_to_grow = (next - (self.visible_lines + 1)).0; - for _ in 0..lines_to_grow { - self.inner.insert(offset, template_row.clone()); - } - // Set zero to old zero + lines grown - self.zero = offset + lines_to_grow; + // 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); - // Update visible lines - self.visible_lines = next - 1; - } + // Get the position of the start of the buffer + let offset = self.zero % self.inner.len(); - /// Decrease the number of lines in the buffer - pub fn shrink_visible_lines(&mut self, next: Line) { - // Calculate shrinkage and last line of buffer - let shrinkage = (self.visible_lines + 1 - next).0; - let offset = (self.zero + self.inner.len() - 1) % self.inner.len(); + // Split off the beginning of the raw inner buffer + let mut start_buffer = self.inner.split_off(offset); - // Generate range of lines that have to be deleted before the zero line - let start = offset.saturating_sub(shrinkage - 1); - let shrink_before = start..(offset + 1); + // 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); - // Generate range of lines that have to be deleted after the zero line - let shrink_after = (self.inner.len() + offset + 1 - shrinkage)..self.inner.len(); + // Add the start to the raw inner buffer again + self.inner.append(&mut start_buffer); - // Delete all lines in reverse order - for i in shrink_before.chain(shrink_after).rev() { - self.inner.remove(i); + // Update the zero to after the lines we just inserted + self.zero = offset + lines_to_grow; } - // Check if zero has moved (not the first line in the buffer) - if self.zero % (self.inner.len() + shrinkage) != 0 { - // Set zero to the first deleted line in the buffer - self.zero = start; - } + // 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; @@ -134,17 +127,17 @@ impl Storage { #[inline] pub fn len(&self) -> usize { - self.inner.len() + self.len } /// Compute actual index in underlying storage given the requested index. #[inline] fn compute_index(&self, requested: usize) -> usize { - (requested + self.zero) % self.len() + (requested + self.zero) % self.inner.len() } fn compute_line_index(&self, requested: Line) -> usize { - ((self.len() + self.zero + *self.visible_lines) - *requested) % self.len() + ((self.inner.len() + self.zero + *self.visible_lines) - *requested) % self.inner.len() } pub fn swap_lines(&mut self, a: Line, b: Line) { @@ -158,14 +151,14 @@ impl Storage { } pub fn rotate(&mut self, count: isize) { - let len = self.len(); + let len = self.inner.len(); assert!(count.abs() as usize <= len); self.zero += (count + len as isize) as usize % len; } // Fast path pub fn rotate_up(&mut self, count: usize) { - self.zero = (self.zero + count) % self.len(); + self.zero = (self.zero + count) % self.inner.len(); } } @@ -243,6 +236,7 @@ fn grow_after_zero() { inner: vec!["0", "1", "-"], zero: 0, visible_lines: Line(2), + len: 3, }; // Grow buffer @@ -253,9 +247,11 @@ fn grow_after_zero() { 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 @@ -276,6 +272,7 @@ fn grow_before_zero() { inner: vec!["-", "0", "1"], zero: 1, visible_lines: Line(2), + len: 3, }; // Grow buffer @@ -286,9 +283,11 @@ fn grow_before_zero() { 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 @@ -298,6 +297,7 @@ fn grow_before_zero() { /// 1: 0 <- Zero /// 2: 1 /// After: +/// 0: 2 <- Hidden /// 0: 0 <- Zero /// 1: 1 #[test] @@ -307,6 +307,7 @@ fn shrink_before_zero() { inner: vec!["2", "0", "1"], zero: 1, visible_lines: Line(2), + len: 3, }; // Shrink buffer @@ -314,12 +315,14 @@ fn shrink_before_zero() { // Make sure the result is correct let expected = Storage { - inner: vec!["0", "1"], - zero: 0, + 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 @@ -331,6 +334,7 @@ fn shrink_before_zero() { /// After: /// 0: 0 <- Zero /// 1: 1 +/// 2: 2 <- Hidden #[test] fn shrink_after_zero() { // Setup storage area @@ -338,6 +342,7 @@ fn shrink_after_zero() { inner: vec!["0", "1", "2"], zero: 0, visible_lines: Line(2), + len: 3, }; // Shrink buffer @@ -345,12 +350,14 @@ fn shrink_after_zero() { // Make sure the result is correct let expected = Storage { - inner: vec!["0", "1"], + 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 @@ -363,8 +370,12 @@ fn shrink_after_zero() { /// 4: 2 /// 5: 3 /// After: -/// 0: 0 <- Zero -/// 1: 1 +/// 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 @@ -372,6 +383,7 @@ fn shrink_before_and_after_zero() { inner: vec!["4", "5", "0", "1", "2", "3"], zero: 2, visible_lines: Line(5), + len: 6, }; // Shrink buffer @@ -379,10 +391,12 @@ fn shrink_before_and_after_zero() { // Make sure the result is correct let expected = Storage { - inner: vec!["0", "1"], - zero: 0, + 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); } -- cgit From eabd6bb95b1ab883bdec16f8c307432c1e7c73d5 Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Tue, 1 May 2018 20:07:59 +0200 Subject: Remove `push` from `Storage` Since every line is allocated at startup anyways, the `push` method on `Storage` has been removed and instead of pushing to the vector the initialization has been moved to the `with_capacity` method. This has the advantage that we don't need to keep track of the `len` in push (like adding one), but we just need to worry about growing/shrinking the visible area. --- src/grid/storage.rs | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index a50e8076..1f71b5b5 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -67,9 +67,18 @@ impl ::std::cmp::PartialEq for Storage { impl Storage { #[inline] - pub fn with_capacity(cap: usize, lines: Line) -> Storage { + pub fn with_capacity(cap: usize, lines: Line, template: T) -> Storage + 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: Vec::with_capacity(cap), + inner, zero: 0, visible_lines: lines - 1, len: cap, @@ -120,11 +129,6 @@ impl Storage { self.visible_lines = next - 1; } - #[inline] - pub fn push(&mut self, item: T) { - self.inner.push(item) - } - #[inline] pub fn len(&self) -> usize { self.len -- cgit From 6cddceb6cde032a79253f0596850c3e3c1c66db7 Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Wed, 2 May 2018 20:49:32 +0200 Subject: Add documentation for `len` field on `Storage` Because the purpose of the `len` field wasn't obvious and collided with other uses (like Vec::len()), some additional documentation has added to make things a little easier to understand. --- src/grid/storage.rs | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 1f71b5b5..f59b01b7 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -20,6 +20,13 @@ pub struct Storage { inner: Vec, 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, } -- cgit From ac93f6d03198c1826dbed60fa8283aeb8d1a577d Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Tue, 15 May 2018 22:36:14 +0200 Subject: Truncate invisible lines before storing ref-tests Because there is no good way to store invisible lines in a backwards- and forwards-compatible way, they buffer now gets truncated before dumping the state of a grid when creating a ref-test. This involved a few workaround of which a few required adding additional methods which are only used in ref-tests, these should be minimal though. Since this required the creation of a truncation method anyways, some logic has been added which automatically truncates the invisible buffer when there are more than X (set to 100) invisible lines. This should not impact performance because it rarely occurs, but it could save a bit of memory when the history size is shrunk during runtime (see #1293). This also adds an optional `config.json` file to the ref-test output where it is possible to manually specify variables which should override config defaults, this has been used only for history_size so far. Creating a new ref-test does also still work, so there was no regression here, if history size is altered, the config.json just has to be created manually with the content `{"history_size":HIST_SIZE}`, where `HIST_SIZE` is the desired history size. --- src/grid/storage.rs | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 102 insertions(+) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index f59b01b7..885cb94c 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -15,6 +15,9 @@ use std::ops::{Index, IndexMut}; use index::Line; +/// Maximum number of invisible lines before buffer is resized +const TRUNCATE_STEP: usize = 100; + #[derive(Clone, Debug, Deserialize, Serialize)] pub struct Storage { inner: Vec, @@ -134,6 +137,32 @@ impl Storage { // 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] @@ -411,3 +440,76 @@ fn shrink_before_and_after_zero() { 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); +} -- cgit From 4b1a3b1e929bbf580de7106a688043bb44523a7f Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Fri, 18 May 2018 20:44:54 -0700 Subject: Optimize Storage::swap_lines Saves a few cycles in a *very* hot function. --- src/grid/storage.rs | 14 ++++++-------- 1 file changed, 6 insertions(+), 8 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 885cb94c..cadd4e29 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -176,13 +176,10 @@ impl Storage { (requested + self.zero) % self.inner.len() } - fn compute_line_index(&self, requested: Line) -> usize { - ((self.inner.len() + self.zero + *self.visible_lines) - *requested) % self.inner.len() - } - pub fn swap_lines(&mut self, a: Line, b: Line) { - let a = self.compute_line_index(a); - let b = self.compute_line_index(b); + 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); } @@ -191,9 +188,10 @@ impl Storage { } pub fn rotate(&mut self, count: isize) { + debug_assert!(count.abs() as usize <= self.inner.len()); + let len = self.inner.len(); - assert!(count.abs() as usize <= len); - self.zero += (count + len as isize) as usize % len; + self.zero = (self.zero as isize + count + len as isize) as usize % len; } // Fast path -- cgit From 5a11f8584317b6a949a1ff3a5b3a446766db0665 Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Sat, 19 May 2018 12:06:21 -0700 Subject: Fix OOB index in grid::DisplayIter When resizing prior to this patch, hidden rows in Storage were not having columns added along with everything else. This feels like a bit of tech debt, but the patch is simple enough that it won't be much extra to back out later when the underlying cause is addressed (see comments in code). --- src/grid/storage.rs | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index cadd4e29..e7c1a307 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -12,6 +12,7 @@ /// 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; @@ -183,10 +184,25 @@ impl Storage { 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 { 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()); -- cgit From 169b87e4ce19f4fd22e5d06ff27f9d3d0ee19b44 Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Sat, 19 May 2018 14:47:16 -0700 Subject: Shave a few cycles off Grid::scroll_up This implementation avoids a few extra transformations by operating in buffer-space. However, there is still a transformation from the logical buffer-space to the underlying vector. --- src/grid/storage.rs | 28 +++++++++++++++++++++++++++- 1 file changed, 27 insertions(+), 1 deletion(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index e7c1a307..eb87c622 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -171,12 +171,25 @@ impl Storage { self.len } - /// Compute actual index in underlying storage given the requested index. #[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 { (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(); @@ -184,6 +197,19 @@ impl Storage { self.inner.swap(a, b); } + /// Swap two lines in raw buffer + /// + /// # Panics + /// + /// `swap` will panic if either `a` or `b` are out-of-bounds of the + /// underlying storage. + pub 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); + } + /// Iterator over *logical* entries in the storage /// /// This *does not* iterate over hidden entries. -- cgit From 9a98d5e0ee9139d5a2988d125352c5d70a39ad20 Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Tue, 29 May 2018 21:33:13 -0700 Subject: Refactor Storage to be a Vec> internally This will allow certain optimizations around swap which are currently only possible in a generalized way with specialization. --- src/grid/storage.rs | 57 +++++++++++++++++++++++++++-------------------------- 1 file changed, 29 insertions(+), 28 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index eb87c622..57afde82 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -14,14 +14,15 @@ use std::ops::{Index, IndexMut}; use std::slice; -use index::Line; +use index::{Column, 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 { - inner: Vec, + inner: Vec>, zero: usize, visible_lines: Line, @@ -78,7 +79,7 @@ impl ::std::cmp::PartialEq for Storage { impl Storage { #[inline] - pub fn with_capacity(cap: usize, lines: Line, template: T) -> Storage + pub fn with_capacity(cap: usize, lines: Line, template: Row) -> Storage where T: Clone, { @@ -97,7 +98,7 @@ impl Storage { } /// Increase the number of lines in the buffer - pub fn grow_visible_lines(&mut self, next: Line, template_row: T) + pub fn grow_visible_lines(&mut self, next: Line, template_row: Row) where T: Clone, { @@ -225,7 +226,7 @@ impl Storage { /// 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> { + pub fn iter_mut_raw<'a>(&'a mut self) -> slice::IterMut<'a, Row> { self.inner.iter_mut() } @@ -243,9 +244,9 @@ impl Storage { } impl Index for Storage { - type Output = T; + type Output = Row; #[inline] - fn index(&self, index: usize) -> &T { + fn index(&self, index: usize) -> &Self::Output { let index = self.compute_index(index); // borrowck &self.inner[index] } @@ -253,16 +254,16 @@ impl Index for Storage { impl IndexMut for Storage { #[inline] - fn index_mut(&mut self, index: usize) -> &mut T { + fn index_mut(&mut self, index: usize) -> &mut Self::Output { let index = self.compute_index(index); // borrowck &mut self.inner[index] } } impl Index for Storage { - type Output = T; + type Output = Row; #[inline] - fn index(&self, index: Line) -> &T { + fn index(&self, index: Line) -> &Self::Output { let index = self.visible_lines - index; &self[*index] } @@ -270,7 +271,7 @@ impl Index for Storage { impl IndexMut for Storage { #[inline] - fn index_mut(&mut self, index: Line) -> &mut T { + fn index_mut(&mut self, index: Line) -> &mut Self::Output { let index = self.visible_lines - index; &mut self[*index] } @@ -282,7 +283,7 @@ pub struct IterMut<'a, T: 'a> { } impl<'a, T: 'a> Iterator for IterMut<'a, T> { - type Item = &'a mut T; + type Item = &'a mut Row; fn next(&mut self) -> Option { if self.index == self.storage.len() { @@ -313,18 +314,18 @@ impl<'a, T: 'a> Iterator for IterMut<'a, T> { fn grow_after_zero() { // Setup storage area let mut storage = Storage { - inner: vec!["0", "1", "-"], + 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), "-"); + storage.grow_visible_lines(Line(4), Row::new(Column(1), &'-')); // Make sure the result is correct let expected = Storage { - inner: vec!["-", "0", "1", "-"], + 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, @@ -349,18 +350,18 @@ fn grow_after_zero() { fn grow_before_zero() { // Setup storage area let mut storage = Storage { - inner: vec!["-", "0", "1"], + 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), "-"); + storage.grow_visible_lines(Line(4), Row::new(Column(1), &'-')); // Make sure the result is correct let expected = Storage { - inner: vec!["-", "-", "0", "1"], + 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, @@ -384,7 +385,7 @@ fn grow_before_zero() { fn shrink_before_zero() { // Setup storage area let mut storage = Storage { - inner: vec!["2", "0", "1"], + 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, @@ -395,7 +396,7 @@ fn shrink_before_zero() { // Make sure the result is correct let expected = Storage { - inner: vec!["2", "0", "1"], + 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, @@ -419,7 +420,7 @@ fn shrink_before_zero() { fn shrink_after_zero() { // Setup storage area let mut storage = Storage { - inner: vec!["0", "1", "2"], + 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, @@ -430,7 +431,7 @@ fn shrink_after_zero() { // Make sure the result is correct let expected = Storage { - inner: vec!["0", "1", "2"], + 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, @@ -460,7 +461,7 @@ fn shrink_after_zero() { fn shrink_before_and_after_zero() { // Setup storage area let mut storage = Storage { - inner: vec!["4", "5", "0", "1", "2", "3"], + 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, @@ -471,7 +472,7 @@ fn shrink_before_and_after_zero() { // Make sure the result is correct let expected = Storage { - inner: vec!["4", "5", "0", "1", "2", "3"], + 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, @@ -497,7 +498,7 @@ fn shrink_before_and_after_zero() { fn truncate_invisible_lines() { // Setup storage area let mut storage = Storage { - inner: vec!["4", "5", "0", "1", "2", "3"], + 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, @@ -508,7 +509,7 @@ fn truncate_invisible_lines() { // Make sure the result is correct let expected = Storage { - inner: vec!["0", "1"], + inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1')], zero: 0, visible_lines: Line(1), len: 2, @@ -532,7 +533,7 @@ fn truncate_invisible_lines() { fn truncate_invisible_lines_beginning() { // Setup storage area let mut storage = Storage { - inner: vec!["1", "2", "0"], + 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, @@ -543,7 +544,7 @@ fn truncate_invisible_lines_beginning() { // Make sure the result is correct let expected = Storage { - inner: vec!["1", "0"], + inner: vec![Row::new(Column(1), &'1'), Row::new(Column(1), &'0')], zero: 1, visible_lines: Line(1), len: 2, -- cgit From a2f99883773676a9dcc537afff4bce54e04e412b Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Tue, 29 May 2018 21:37:56 -0700 Subject: Optimize Storage::swap Removes 4 movaps instructions from generated assembly. --- src/grid/storage.rs | 38 ++++++++++++++++++++++++++++++++------ 1 file changed, 32 insertions(+), 6 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 57afde82..0f0f611b 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -14,7 +14,7 @@ use std::ops::{Index, IndexMut}; use std::slice; -use index::{Column, Line}; +use index::Line; use super::Row; /// Maximum number of invisible lines before buffer is resized @@ -198,17 +198,40 @@ impl Storage { self.inner.swap(a, b); } - /// Swap two lines in raw buffer + /// Swap implementation for Row. /// - /// # Panics + /// Exploits the known size of Row to produce a slightly more efficient + /// swap than going through slice::swap. /// - /// `swap` will panic if either `a` or `b` are out-of-bounds of the - /// underlying storage. + /// The default implementation from swap generates 8 movups and 4 movaps + /// instructions. This implementation achieves the swap in only 8 movups + /// instructions. + /// + // TODO Once specialization is available, Storage can be fully generic + // again instead of enforcing inner: Vec>. pub fn swap(&mut self, a: usize, b: usize) { + debug_assert!(::std::mem::size_of::>() == 32); + let a = self.compute_index(a); let b = self.compute_index(b); - self.inner.swap(a, 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; + } + } } /// Iterator over *logical* entries in the storage @@ -299,6 +322,9 @@ impl<'a, T: 'a> Iterator for IterMut<'a, T> { } } +#[cfg(test)] +use index::Column; + /// Grow the buffer one line at the end of the buffer /// /// Before: -- cgit From 24c50fa0a793cd8c6127b5cf8ba3ea59f47cc1ca Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Tue, 29 May 2018 21:45:28 -0700 Subject: Remove dead code --- src/grid/storage.rs | 43 ------------------------------------------- 1 file changed, 43 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 0f0f611b..d517fa01 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -172,25 +172,11 @@ impl Storage { 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 { (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(); @@ -234,13 +220,6 @@ impl Storage { } } - /// Iterator over *logical* entries in the storage - /// - /// This *does not* iterate over hidden entries. - pub fn iter_mut(&mut self) -> IterMut { - IterMut { storage: self, index: 0 } - } - /// Iterate over *all* entries in the underlying buffer /// /// This includes hidden entries. @@ -300,28 +279,6 @@ impl IndexMut for Storage { } } -pub struct IterMut<'a, T: 'a> { - storage: &'a mut Storage, - index: usize, -} - -impl<'a, T: 'a> Iterator for IterMut<'a, T> { - type Item = &'a mut Row; - - fn next(&mut self) -> Option { - if self.index == self.storage.len() { - None - } else { - let index = self.index; - self.index += 1; - - unsafe { - Some(&mut *(&mut self.storage[index] as *mut _)) - } - } - } -} - #[cfg(test)] use index::Column; -- cgit From 4631ca4db5faf10eb0276e3968814a68c86c81ee Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Wed, 30 May 2018 10:20:47 +0200 Subject: Allow changing scrollback history size at runtime Making use of the changes that have been introduced in #1234 and #1284, this allows changing the size of the scrollback buffer at runtime. This simply changes the size of the raw inner buffer making use of the optimized mutation algorithms introduced in #1284. As a result, shrinking the scrollback history size at runtime should be basically free and growing will only introduce a performance cost when there are no more buffered lines. However, as a result there will not be any memory freed when shrinking the scrollback history size at runtime. As discussed in #1234 a potential solution for this could be to truncate the raw buffer whenever more than X lines are deleted, however this issue should not be very significant PR and if a solution is desired a separate issue/PR should be opened. This fixes #1235. --- src/grid/storage.rs | 140 ++++++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 126 insertions(+), 14 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index d517fa01..6ed4a06a 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -97,48 +97,75 @@ impl Storage { } } + /// Update the size of the scrollback history + pub fn update_history(&mut self, history_size: usize, template_row: Row) + 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) where T: Clone, { // Number of lines the buffer needs to grow - let lines_to_grow = (next - (self.visible_lines + 1)).0; + 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 + pub fn grow_lines(&mut self, growage: usize, template_row: Row) + where + T: Clone, + { + // Get the position of the start of the buffer + let offset = self.zero % self.inner.len(); // Only grow if there are not enough lines still hidden - if lines_to_grow > (self.inner.len() - self.len) { + let mut new_growage = 0; + if growage > (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(); + 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(offset); // Insert new template rows at the end of the raw inner buffer - let mut new_lines = vec![template_row; new_lines_to_grow]; + 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 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; + // Update raw buffer length and zero offset + self.zero = offset + new_growage; + 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 - self.len -= (self.visible_lines - (next - 1)).0; + 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 { @@ -537,3 +564,88 @@ fn truncate_invisible_lines_beginning() { 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); +} -- cgit From bfd62ef45bedf02a4f61c08bba134a2eb06c0b47 Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Sat, 16 Jun 2018 17:50:44 +0000 Subject: Optimize indexing of the grid's raw buffer The `compute_index` method in the `Storage` struct used to normalize indices was responsible for a significant amount of the CPU time spent while running the `alt-screen-random-write` benchmark (~50%). The issue with this relatively simple method was that due to how often the method is executed, the modulo operation was too expensive. Instead of the modulo, a more conservative branch has been put in place which has a very efficient best-case (which is hit most of the time). Until now the methods for growing/shrinking the storage buffer and compute_index have been written with the assumption that `self.zero` might be bigger than `self.inner.len()`. However there is no reason why `self.zero` wouldn't be constrained to always be within the size of the raw buffer, so this has been changed to make things a little simpler and more explicit. Instead of clamping the selection to be within the buffer inside the storage, this is now checked in the selection logic to remove all selection-specific logic from `storage.rs`. --- src/grid/storage.rs | 32 +++++++++++++++++++------------- 1 file changed, 19 insertions(+), 13 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 6ed4a06a..2f34b3f0 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -128,9 +128,6 @@ impl Storage { where T: Clone, { - // Get the position of the start of the buffer - let offset = self.zero % self.inner.len(); - // Only grow if there are not enough lines still hidden let mut new_growage = 0; if growage > (self.inner.len() - self.len) { @@ -138,7 +135,7 @@ impl Storage { 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(offset); + 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]; @@ -149,7 +146,7 @@ impl Storage { } // Update raw buffer length and zero offset - self.zero = offset + new_growage; + self.zero = (self.zero + new_growage) % self.inner.len(); self.len += growage; } @@ -176,12 +173,11 @@ impl Storage { /// 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); + let shrinkage_start = ::std::cmp::min(self.zero, shrinkage); // Create two vectors with correct ordering - let mut split = self.inner.split_off(offset); + let mut split = self.inner.split_off(self.zero); // Truncate the buffers let len = self.inner.len(); @@ -190,8 +186,9 @@ impl Storage { split.truncate(split_len - (shrinkage - shrinkage_start)); // Merge buffers again and reset zero - self.zero = self.inner.len(); - self.inner.append(&mut split); + split.append(&mut self.inner); + self.inner = split; + self.zero = 0; } #[inline] @@ -201,7 +198,16 @@ impl Storage { /// Compute actual index in underlying storage given the requested index. fn compute_index(&self, requested: usize) -> usize { - (requested + self.zero) % self.inner.len() + debug_assert!(requested < self.inner.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) { @@ -554,8 +560,8 @@ fn truncate_invisible_lines_beginning() { // Make sure the result is correct let expected = Storage { - inner: vec![Row::new(Column(1), &'1'), Row::new(Column(1), &'0')], - zero: 1, + inner: vec![Row::new(Column(1), &'0'), Row::new(Column(1), &'1')], + zero: 0, visible_lines: Line(1), len: 2, }; -- cgit From 07aaf05f7463a971e56de87e3b6b24e4153e5a98 Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Mon, 2 Jul 2018 22:03:04 +0000 Subject: Fix scrollback accessing indices out of bounds There have been two instances of the scrollback trying to access indices which were moved out of bounds due to new lines (`yes` command). These have both been fixed. The first instance was during semantic selection, since the logic of limiting the selection start point was moved outside of `compute_index`, it was necessary to add this to semantic selection too. Now semantic selection, line selection and normal selection should all work without crashing when new lines are shoving the selection out of bounds. The other error was with the viewport being outside of the scrollback history. Since the default is to keep the scrollback buffer at its current position when new lines are added, it is possible that the position the scrollback buffer is at is suddenly shoved out of the visible area. To fix this the `display_offset` is now limited to always be an allowed value. If a single line of the viewport is moved out of the history now, the viewport should move down a single line now, so only valid content is displayed, with multiple lines this process is repeated. This fixes #1400. There was another error where the iterator would attempt to iterate before the first line in the history buffer, this was because the bounds of the `prev` iterator weren't setup correctly. The iterator should now properly iterate from the first cell in the terminal until the last one. This also fixes #1406, since these semantic selection errors were partiall related to indexing. --- src/grid/storage.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 2f34b3f0..5d6cb936 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -198,7 +198,7 @@ impl Storage { /// Compute actual index in underlying storage given the requested index. fn compute_index(&self, requested: usize) -> usize { - debug_assert!(requested < self.inner.len()); + debug_assert!(requested < self.len); let zeroed = requested + self.zero; // This part is critical for performance, -- cgit From f50ca1a54c94fe324d22d985c1acae1ff7c16a80 Mon Sep 17 00:00:00 2001 From: Christian Duerr Date: Sat, 21 Jul 2018 17:17:41 +0000 Subject: Scrollback cleanup There were some unneeded codeblocks and TODO/XXX comments in the code that have been removed. All issues marked with TODO/XXX have either been already resolved or tracking issues exist. --- src/grid/storage.rs | 22 ++++++++-------------- 1 file changed, 8 insertions(+), 14 deletions(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 5d6cb936..6a453da6 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -68,12 +68,12 @@ impl ::std::cmp::PartialEq for Storage { // 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] + 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] } } @@ -84,11 +84,8 @@ impl Storage { 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, @@ -124,7 +121,7 @@ impl Storage { } /// Grow the number of lines in the buffer, filling new lines with the template - pub fn grow_lines(&mut self, growage: usize, template_row: Row) + fn grow_lines(&mut self, growage: usize, template_row: Row) where T: Clone, { @@ -225,9 +222,6 @@ impl Storage { /// The default implementation from swap generates 8 movups and 4 movaps /// instructions. This implementation achieves the swap in only 8 movups /// instructions. - /// - // TODO Once specialization is available, Storage can be fully generic - // again instead of enforcing inner: Vec>. pub fn swap(&mut self, a: usize, b: usize) { debug_assert!(::std::mem::size_of::>() == 32); -- cgit From b59fd21cac5f84c02e2df161bad708e440834320 Mon Sep 17 00:00:00 2001 From: Th3Fanbus Date: Thu, 26 Jul 2018 17:47:14 +0200 Subject: Replace runtime debug assertions with static asserts on scrollback --- src/grid/storage.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/grid/storage.rs') diff --git a/src/grid/storage.rs b/src/grid/storage.rs index 6a453da6..ad94cf2b 100644 --- a/src/grid/storage.rs +++ b/src/grid/storage.rs @@ -223,7 +223,7 @@ impl Storage { /// instructions. This implementation achieves the swap in only 8 movups /// instructions. pub fn swap(&mut self, a: usize, b: usize) { - debug_assert!(::std::mem::size_of::>() == 32); + assert_eq_size!(Row, [u32; 8]); let a = self.compute_index(a); let b = self.compute_index(b); -- cgit