Add regex scrollback buffer search

This adds a new regex search which allows searching the entire
scrollback and jumping between matches using the vi mode.

All visible matches should be highlighted unless their lines are
excessively long. This should help with performance since highlighting
is done during render time.

Fixes #1017.

1 files changed, 302 insertions, 48 deletions

diff --git a/alacritty/src/event.rs b/alacritty/src/event.rs
index 630e8ef0..edbc4086 100644
--- a/alacritty/src/event.rs
+++ b/alacritty/src/event.rs
@@ -1,7 +1,7 @@
 //! Process window events.
 
 use std::borrow::Cow;
-use std::cmp::max;
+use std::cmp::{max, min};
 use std::env;
 #[cfg(unix)]
 use std::fs;
@@ -12,7 +12,7 @@ use std::path::PathBuf;
 #[cfg(not(any(target_os = "macos", windows)))]
 use std::sync::atomic::Ordering;
 use std::sync::Arc;
-use std::time::Instant;
+use std::time::{Duration, Instant};
 
 use glutin::dpi::PhysicalSize;
 use glutin::event::{ElementState, Event as GlutinEvent, ModifiersState, MouseButton, WindowEvent};
@@ -27,12 +27,10 @@ use serde_json as json;
 use font::set_font_smoothing;
 use font::{self, Size};
 
-use alacritty_terminal::config::Font;
 use alacritty_terminal::config::LOG_TARGET_CONFIG;
-use alacritty_terminal::event::OnResize;
-use alacritty_terminal::event::{Event as TerminalEvent, EventListener, Notify};
-use alacritty_terminal::grid::Scroll;
-use alacritty_terminal::index::{Column, Line, Point, Side};
+use alacritty_terminal::event::{Event as TerminalEvent, EventListener, Notify, OnResize};
+use alacritty_terminal::grid::{Dimensions, Scroll};
+use alacritty_terminal::index::{Column, Direction, Line, Point, Side};
 use alacritty_terminal::message_bar::{Message, MessageBuffer};
 use alacritty_terminal::selection::{Selection, SelectionType};
 use alacritty_terminal::sync::FairMutex;
@@ -46,12 +44,18 @@ use crate::cli::Options;
 use crate::clipboard::Clipboard;
 use crate::config;
 use crate::config::Config;
-use crate::display::Display;
+use crate::display::{Display, DisplayUpdate};
 use crate::input::{self, ActionContext as _, FONT_SIZE_STEP};
-use crate::scheduler::Scheduler;
+use crate::scheduler::{Scheduler, TimerId};
 use crate::url::{Url, Urls};
 use crate::window::Window;
 
+/// Duration after the last user input until an unlimited search is performed.
+pub const TYPING_SEARCH_DELAY: Duration = Duration::from_millis(500);
+
+/// Maximum number of lines for the blocking search while still typing the search regex.
+const MAX_SEARCH_WHILE_TYPING: Option<usize> = Some(1000);
+
 /// Events dispatched through the UI event loop.
 #[derive(Debug, Clone)]
 pub enum Event {
@@ -60,6 +64,7 @@ pub enum Event {
     Scroll(Scroll),
     ConfigReload(PathBuf),
     Message(Message),
+    SearchNext,
 }
 
 impl From<Event> for GlutinEvent<'_, Event> {
@@ -74,17 +79,35 @@ impl From<TerminalEvent> for Event {
     }
 }
 
-#[derive(Default, Clone, Debug, PartialEq)]
-pub struct DisplayUpdate {
-    pub dimensions: Option<PhysicalSize<u32>>,
-    pub message_buffer: bool,
-    pub font: Option<Font>,
-    pub cursor: bool,
+/// Regex search state.
+pub struct SearchState {
+    /// Search string regex.
+    regex: Option<String>,
+
+    /// Search direction.
+    direction: Direction,
+
+    /// Change in display offset since the beginning of the search.
+    display_offset_delta: isize,
+
+    /// Vi cursor position before search.
+    vi_cursor_point: Point,
 }
 
-impl DisplayUpdate {
-    fn is_empty(&self) -> bool {
-        self.dimensions.is_none() && self.font.is_none() && !self.message_buffer && !self.cursor
+impl SearchState {
+    fn new() -> Self {
+        Self::default()
+    }
+}
+
+impl Default for SearchState {
+    fn default() -> Self {
+        Self {
+            direction: Direction::Right,
+            display_offset_delta: 0,
+            vi_cursor_point: Point::default(),
+            regex: None,
+        }
     }
 }
 
@@ -104,6 +127,7 @@ pub struct ActionContext<'a, N, T> {
     pub event_loop: &'a EventLoopWindowTarget<Event>,
     pub urls: &'a Urls,
     pub scheduler: &'a mut Scheduler,
+    pub search_state: &'a mut SearchState,
     font_size: &'a mut Size,
 }
 
@@ -294,19 +318,148 @@ impl<'a, N: Notify + 'a, T: EventListener> input::ActionContext<T> for ActionCon
     fn change_font_size(&mut self, delta: f32) {
         *self.font_size = max(*self.font_size + delta, Size::new(FONT_SIZE_STEP));
         let font = self.config.font.clone().with_size(*self.font_size);
-        self.display_update_pending.font = Some(font);
+        self.display_update_pending.set_font(font);
         self.terminal.dirty = true;
     }
 
     fn reset_font_size(&mut self) {
         *self.font_size = self.config.font.size;
-        self.display_update_pending.font = Some(self.config.font.clone());
+        self.display_update_pending.set_font(self.config.font.clone());
         self.terminal.dirty = true;
     }
 
+    #[inline]
     fn pop_message(&mut self) {
-        self.display_update_pending.message_buffer = true;
-        self.message_buffer.pop();
+        if !self.message_buffer.is_empty() {
+            self.display_update_pending.dirty = true;
+            self.message_buffer.pop();
+        }
+    }
+
+    #[inline]
+    fn start_search(&mut self, direction: Direction) {
+        let num_lines = self.terminal.screen_lines();
+        let num_cols = self.terminal.cols();
+
+        self.search_state.regex = Some(String::new());
+        self.search_state.direction = direction;
+
+        // Store original vi cursor position as search origin and for resetting.
+        self.search_state.vi_cursor_point = if self.terminal.mode().contains(TermMode::VI) {
+            self.terminal.vi_mode_cursor.point
+        } else {
+            match direction {
+                Direction::Right => Point::new(Line(0), Column(0)),
+                Direction::Left => Point::new(num_lines - 2, num_cols - 1),
+            }
+        };
+
+        self.display_update_pending.dirty = true;
+        self.terminal.dirty = true;
+    }
+
+    #[inline]
+    fn confirm_search(&mut self) {
+        // Enter vi mode once search is confirmed.
+        self.terminal.set_vi_mode();
+
+        // Force unlimited search if the previous one was interrupted.
+        if self.scheduler.scheduled(TimerId::DelayedSearch) {
+            self.goto_match(None);
+        }
+
+        // Move vi cursor down if resize will pull content from history.
+        if self.terminal.history_size() != 0 && self.terminal.grid().display_offset() == 0 {
+            self.terminal.vi_mode_cursor.point.line += 1;
+        }
+
+        // Clear reset state.
+        self.search_state.display_offset_delta = 0;
+
+        self.display_update_pending.dirty = true;
+        self.search_state.regex = None;
+        self.terminal.dirty = true;
+    }
+
+    #[inline]
+    fn cancel_search(&mut self) {
+        self.terminal.cancel_search();
+
+        // Recover pre-search state.
+        self.search_reset_state();
+
+        // Move vi cursor down if resize will pull from history.
+        if self.terminal.history_size() != 0 && self.terminal.grid().display_offset() == 0 {
+            self.terminal.vi_mode_cursor.point.line += 1;
+        }
+
+        self.display_update_pending.dirty = true;
+        self.search_state.regex = None;
+        self.terminal.dirty = true;
+    }
+
+    #[inline]
+    fn push_search(&mut self, c: char) {
+        let regex = match self.search_state.regex.as_mut() {
+            Some(regex) => regex,
+            None => return,
+        };
+
+        // Hide cursor while typing into the search bar.
+        if self.config.ui_config.mouse.hide_when_typing {
+            self.window.set_mouse_visible(false);
+        }
+
+        // Add new char to search string.
+        regex.push(c);
+
+        // Create terminal search from the new regex string.
+        self.terminal.start_search(&regex);
+
+        // Update search highlighting.
+        self.goto_match(MAX_SEARCH_WHILE_TYPING);
+
+        self.terminal.dirty = true;
+    }
+
+    #[inline]
+    fn pop_search(&mut self) {
+        let regex = match self.search_state.regex.as_mut() {
+            Some(regex) => regex,
+            None => return,
+        };
+
+        // Hide cursor while typing into the search bar.
+        if self.config.ui_config.mouse.hide_when_typing {
+            self.window.set_mouse_visible(false);
+        }
+
+        // Remove last char from search string.
+        regex.pop();
+
+        if regex.is_empty() {
+            // Stop search if there's nothing to search for.
+            self.search_reset_state();
+            self.terminal.cancel_search();
+        } else {
+            // Create terminal search from the new regex string.
+            self.terminal.start_search(&regex);
+
+            // Update search highlighting.
+            self.goto_match(MAX_SEARCH_WHILE_TYPING);
+        }
+
+        self.terminal.dirty = true;
+    }
+
+    #[inline]
+    fn search_direction(&self) -> Direction {
+        self.search_state.direction
+    }
+
+    #[inline]
+    fn search_active(&self) -> bool {
+        self.search_state.regex.is_some()
     }
 
     fn message(&self) -> Option<&Message> {
@@ -334,6 +487,73 @@ impl<'a, N: Notify + 'a, T: EventListener> input::ActionContext<T> for ActionCon
     }
 }
 
+impl<'a, N: Notify + 'a, T: EventListener> ActionContext<'a, N, T> {
+    /// Reset terminal to the state before search was started.
+    fn search_reset_state(&mut self) {
+        // Reset display offset.
+        self.terminal.scroll_display(Scroll::Delta(self.search_state.display_offset_delta));
+        self.search_state.display_offset_delta = 0;
+
+        // Reset vi mode cursor.
+        let mut vi_cursor_point = self.search_state.vi_cursor_point;
+        vi_cursor_point.line = min(vi_cursor_point.line, self.terminal.screen_lines() - 1);
+        vi_cursor_point.col = min(vi_cursor_point.col, self.terminal.cols() - 1);
+        self.terminal.vi_mode_cursor.point = vi_cursor_point;
+
+        // Unschedule pending timers.
+        self.scheduler.unschedule(TimerId::DelayedSearch);
+    }
+
+    /// Jump to the first regex match from the search origin.
+    fn goto_match(&mut self, mut limit: Option<usize>) {
+        let regex = match self.search_state.regex.take() {
+            Some(regex) => regex,
+            None => return,
+        };
+
+        // Limit search only when enough lines are available to run into the limit.
+        limit = limit.filter(|&limit| limit <= self.terminal.total_lines());
+
+        // Use original position as search origin.
+        let mut vi_cursor_point = self.search_state.vi_cursor_point;
+        vi_cursor_point.line = min(vi_cursor_point.line, self.terminal.screen_lines() - 1);
+        let mut origin = self.terminal.visible_to_buffer(vi_cursor_point);
+        origin.line = (origin.line as isize + self.search_state.display_offset_delta) as usize;
+
+        // Jump to the next match.
+        let direction = self.search_state.direction;
+        match self.terminal.search_next(origin, direction, Side::Left, limit) {
+            Some(regex_match) => {
+                let old_offset = self.terminal.grid().display_offset() as isize;
+
+                self.terminal.vi_goto_point(*regex_match.start());
+
+                // Store number of lines the viewport had to be moved.
+                let display_offset = self.terminal.grid().display_offset();
+                self.search_state.display_offset_delta += old_offset - display_offset as isize;
+
+                // Since we found a result, we require no delayed re-search.
+                self.scheduler.unschedule(TimerId::DelayedSearch);
+            },
+            // Reset viewport only when we know there is no match, to prevent unnecessary jumping.
+            None if limit.is_none() => self.search_reset_state(),
+            None => {
+                // Schedule delayed search if we ran into our search limit.
+                if !self.scheduler.scheduled(TimerId::DelayedSearch) {
+                    self.scheduler.schedule(
+                        Event::SearchNext.into(),
+                        TYPING_SEARCH_DELAY,
+                        false,
+                        TimerId::DelayedSearch,
+                    );
+                }
+            },
+        }
+
+        self.search_state.regex = Some(regex);
+    }
+}
+
 #[derive(Debug, Eq, PartialEq)]
 pub enum ClickState {
     None,
@@ -400,6 +620,7 @@ pub struct Processor<N> {
     display: Display,
     font_size: Size,
     event_queue: Vec<GlutinEvent<'static, Event>>,
+    search_state: SearchState,
 }
 
 impl<N: Notify + OnResize> Processor<N> {
@@ -429,6 +650,7 @@ impl<N: Notify + OnResize> Processor<N> {
             display,
             event_queue: Vec::new(),
             clipboard,
+            search_state: SearchState::new(),
         }
     }
 
@@ -513,6 +735,7 @@ impl<N: Notify + OnResize> Processor<N> {
             let mut terminal = terminal.lock();
 
             let mut display_update_pending = DisplayUpdate::default();
+            let old_is_searching = self.search_state.regex.is_some();
 
             let context = ActionContext {
                 terminal: &mut terminal,
@@ -530,6 +753,7 @@ impl<N: Notify + OnResize> Processor<N> {
                 config: &mut self.config,
                 urls: &self.display.urls,
                 scheduler: &mut scheduler,
+                search_state: &mut self.search_state,
                 event_loop,
             };
             let mut processor = input::Processor::new(context, &self.display.highlighted_url);
@@ -539,14 +763,8 @@ impl<N: Notify + OnResize> Processor<N> {
             }
 
             // Process DisplayUpdate events.
-            if !display_update_pending.is_empty() {
-                self.display.handle_update(
-                    &mut terminal,
-                    &mut self.notifier,
-                    &self.message_buffer,
-                    &self.config,
-                    display_update_pending,
-                );
+            if display_update_pending.dirty {
+                self.submit_display_update(&mut terminal, old_is_searching, display_update_pending);
             }
 
             #[cfg(not(any(target_os = "macos", windows)))]
@@ -575,12 +793,15 @@ impl<N: Notify + OnResize> Processor<N> {
                     &self.config,
                     &self.mouse,
                     self.modifiers,
+                    self.search_state.regex.as_ref(),
                 );
             }
         });
 
         // Write ref tests to disk.
-        self.write_ref_test_results(&terminal.lock());
+        if self.config.debug.ref_test {
+            self.write_ref_test_results(&terminal.lock());
+        }
     }
 
     /// Handle events from glutin.
@@ -598,20 +819,21 @@ impl<N: Notify + OnResize> Processor<N> {
                     let display_update_pending = &mut processor.ctx.display_update_pending;
 
                     // Push current font to update its DPR.
-                    display_update_pending.font =
-                        Some(processor.ctx.config.font.clone().with_size(*processor.ctx.font_size));
+                    let font = processor.ctx.config.font.clone();
+                    display_update_pending.set_font(font.with_size(*processor.ctx.font_size));
 
                     // Resize to event's dimensions, since no resize event is emitted on Wayland.
-                    display_update_pending.dimensions = Some(PhysicalSize::new(width, height));
+                    display_update_pending.set_dimensions(PhysicalSize::new(width, height));
 
                     processor.ctx.size_info.dpr = scale_factor;
                     processor.ctx.terminal.dirty = true;
                 },
                 Event::Message(message) => {
                     processor.ctx.message_buffer.push(message);
-                    processor.ctx.display_update_pending.message_buffer = true;
+                    processor.ctx.display_update_pending.dirty = true;
                     processor.ctx.terminal.dirty = true;
                 },
+                Event::SearchNext => processor.ctx.goto_match(None),
                 Event::ConfigReload(path) => Self::reload_config(&path, processor),
                 Event::Scroll(scroll) => processor.ctx.scroll(scroll),
                 Event::TerminalEvent(event) => match event {
@@ -647,7 +869,7 @@ impl<N: Notify + OnResize> Processor<N> {
                             }
                         }
 
-                        processor.ctx.display_update_pending.dimensions = Some(size);
+                        processor.ctx.display_update_pending.set_dimensions(size);
                         processor.ctx.terminal.dirty = true;
                     },
                     WindowEvent::KeyboardInput { input, is_synthetic: false, .. } => {
@@ -741,14 +963,14 @@ impl<N: Notify + OnResize> Processor<N> {
         }
     }
 
-    pub fn reload_config<T>(
-        path: &PathBuf,
-        processor: &mut input::Processor<T, ActionContext<N, T>>,
-    ) where
+    fn reload_config<T>(path: &PathBuf, processor: &mut input::Processor<T, ActionContext<N, T>>)
+    where
         T: EventListener,
     {
-        processor.ctx.message_buffer.remove_target(LOG_TARGET_CONFIG);
-        processor.ctx.display_update_pending.message_buffer = true;
+        if !processor.ctx.message_buffer.is_empty() {
+            processor.ctx.message_buffer.remove_target(LOG_TARGET_CONFIG);
+            processor.ctx.display_update_pending.dirty = true;
+        }
 
         let config = match config::reload_from(&path) {
             Ok(config) => config,
@@ -764,7 +986,7 @@ impl<N: Notify + OnResize> Processor<N> {
         if (processor.ctx.config.cursor.thickness() - config.cursor.thickness()).abs()
             > std::f64::EPSILON
         {
-            processor.ctx.display_update_pending.cursor = true;
+            processor.ctx.display_update_pending.set_cursor_dirty();
         }
 
         if processor.ctx.config.font != config.font {
@@ -774,7 +996,7 @@ impl<N: Notify + OnResize> Processor<N> {
             }
 
             let font = config.font.clone().with_size(*processor.ctx.font_size);
-            processor.ctx.display_update_pending.font = Some(font);
+            processor.ctx.display_update_pending.set_font(font);
         }
 
         #[cfg(not(any(target_os = "macos", windows)))]
@@ -793,12 +1015,44 @@ impl<N: Notify + OnResize> Processor<N> {
         processor.ctx.terminal.dirty = true;
     }
 
-    // Write the ref test results to the disk.
-    pub fn write_ref_test_results<T>(&self, terminal: &Term<T>) {
-        if !self.config.debug.ref_test {
-            return;
+    /// Submit the pending changes to the `Display`.
+    fn submit_display_update<T>(
+        &mut self,
+        terminal: &mut Term<T>,
+        old_is_searching: bool,
+        display_update_pending: DisplayUpdate,
+    ) where
+        T: EventListener,
+    {
+        // Compute cursor positions before resize.
+        let num_lines = terminal.screen_lines();
+        let cursor_at_bottom = terminal.grid().cursor.point.line + 1 == num_lines;
+        let origin_at_bottom = (!terminal.mode().contains(TermMode::VI)
+            && self.search_state.direction == Direction::Left)
+            || terminal.vi_mode_cursor.point.line == num_lines - 1;
+
+        self.display.handle_update(
+            terminal,
+            &mut self.notifier,
+            &self.message_buffer,
+            self.search_state.regex.is_some(),
+            &self.config,
+            display_update_pending,
+        );
+
+        // Scroll to make sure search origin is visible and content moves as little as possible.
+        if !old_is_searching && self.search_state.regex.is_some() {
+            let display_offset = terminal.grid().display_offset();
+            if display_offset == 0 && cursor_at_bottom && !origin_at_bottom {
+                terminal.scroll_display(Scroll::Delta(1));
+            } else if display_offset != 0 && origin_at_bottom {
+                terminal.scroll_display(Scroll::Delta(-1));
+            }
         }
+    }
 
+    /// Write the ref test results to the disk.
+    fn write_ref_test_results<T>(&self, terminal: &Term<T>) {
         // Dump grid state.
         let mut grid = terminal.grid().clone();
         grid.initialize_all(Cell::default());