Add regex terminal hints

This adds support for hints, which allow opening parts of the visual
buffer with external programs if they match a certain regex.

This is done using a visual overlay triggered on a specified key
binding, which then instructs the user which keys they need to press to
pass the text to the application.

In the future it should be possible to supply some built-in actions for
Copy/Pasting the action and using this to launch text when clicking on
it with the mouse. But the current implementation should already be
useful as-is.

Fixes #2792.
Fixes #2536.

3 files changed, 410 insertions, 39 deletions

diff --git a/alacritty/src/display/content.rs b/alacritty/src/display/content.rs
index 9f035a1c..6532f236 100644
--- a/alacritty/src/display/content.rs
+++ b/alacritty/src/display/content.rs
@@ -1,6 +1,7 @@
+use std::borrow::Cow;
 use std::cmp::max;
 use std::mem;
-use std::ops::RangeInclusive;
+use std::ops::{Deref, DerefMut, RangeInclusive};
 
 use alacritty_terminal::ansi::{Color, CursorShape, NamedColor};
 use alacritty_terminal::config::Config;
@@ -16,6 +17,8 @@ use alacritty_terminal::term::{
 
 use crate::config::ui_config::UiConfig;
 use crate::display::color::{List, DIM_FACTOR};
+use crate::display::hint::HintState;
+use crate::display::Display;
 
 /// Minimum contrast between a fixed cursor color and the cell's background.
 pub const MIN_CURSOR_CONTRAST: f64 = 1.5;
@@ -30,31 +33,38 @@ pub struct RenderableContent<'a> {
     terminal_content: TerminalContent<'a>,
     terminal_cursor: TerminalCursor,
     cursor: Option<RenderableCursor>,
-    search: RenderableSearch,
+    search: Regex<'a>,
+    hint: Hint<'a>,
     config: &'a Config<UiConfig>,
     colors: &'a List,
 }
 
 impl<'a> RenderableContent<'a> {
     pub fn new<T: EventListener>(
-        term: &'a Term<T>,
-        dfas: Option<&RegexSearch>,
         config: &'a Config<UiConfig>,
-        colors: &'a List,
-        show_cursor: bool,
+        display: &'a mut Display,
+        term: &'a Term<T>,
+        search_dfas: Option<&RegexSearch>,
     ) -> Self {
-        let search = dfas.map(|dfas| RenderableSearch::new(&term, dfas)).unwrap_or_default();
+        let search = search_dfas.map(|dfas| Regex::new(&term, dfas)).unwrap_or_default();
         let terminal_content = term.renderable_content();
 
         // Copy the cursor and override its shape if necessary.
         let mut terminal_cursor = terminal_content.cursor;
-        if !show_cursor || terminal_cursor.shape == CursorShape::Hidden {
+        if terminal_cursor.shape == CursorShape::Hidden
+            || display.cursor_hidden
+            || search_dfas.is_some()
+        {
             terminal_cursor.shape = CursorShape::Hidden;
         } else if !term.is_focused && config.cursor.unfocused_hollow {
             terminal_cursor.shape = CursorShape::HollowBlock;
         }
 
-        Self { cursor: None, terminal_content, terminal_cursor, search, config, colors }
+        display.hint_state.update_matches(term);
+        let hint = Hint::from(&display.hint_state);
+
+        let colors = &display.colors;
+        Self { cursor: None, terminal_content, terminal_cursor, search, config, colors, hint }
     }
 
     /// Viewport offset.
@@ -193,37 +203,40 @@ impl RenderableCell {
             .map_or(false, |selection| selection.contains_cell(&cell, content.terminal_cursor));
         let mut is_match = false;
 
+        let mut character = cell.c;
+
         let colors = &content.config.ui_config.colors;
-        if is_selected {
+        if let Some((c, is_first)) = content.hint.advance(cell.point) {
+            let (config_fg, config_bg) = if is_first {
+                (colors.hints.start.foreground, colors.hints.start.background)
+            } else {
+                (colors.hints.end.foreground, colors.hints.end.background)
+            };
+            Self::compute_cell_rgb(&mut fg_rgb, &mut bg_rgb, &mut bg_alpha, config_fg, config_bg);
+
+            character = c;
+        } else if is_selected {
+            let config_fg = colors.selection.foreground;
             let config_bg = colors.selection.background;
-            let selected_fg = colors.selection.foreground.color(fg_rgb, bg_rgb);
-            bg_rgb = config_bg.color(fg_rgb, bg_rgb);
-            fg_rgb = selected_fg;
+            Self::compute_cell_rgb(&mut fg_rgb, &mut bg_rgb, &mut bg_alpha, config_fg, config_bg);
 
             if fg_rgb == bg_rgb && !cell.flags.contains(Flags::HIDDEN) {
                 // Reveal inversed text when fg/bg is the same.
                 fg_rgb = content.color(NamedColor::Background as usize);
                 bg_rgb = content.color(NamedColor::Foreground as usize);
                 bg_alpha = 1.0;
-            } else if config_bg != CellRgb::CellBackground {
-                bg_alpha = 1.0;
             }
         } else if content.search.advance(cell.point) {
             // Highlight the cell if it is part of a search match.
+            let config_fg = colors.search.matches.foreground;
             let config_bg = colors.search.matches.background;
-            let matched_fg = colors.search.matches.foreground.color(fg_rgb, bg_rgb);
-            bg_rgb = config_bg.color(fg_rgb, bg_rgb);
-            fg_rgb = matched_fg;
-
-            if config_bg != CellRgb::CellBackground {
-                bg_alpha = 1.0;
-            }
+            Self::compute_cell_rgb(&mut fg_rgb, &mut bg_rgb, &mut bg_alpha, config_fg, config_bg);
 
             is_match = true;
         }
 
         RenderableCell {
-            character: cell.c,
+            character,
             zerowidth: cell.zerowidth().map(|zerowidth| zerowidth.to_vec()),
             point: cell.point,
             fg: fg_rgb,
@@ -242,6 +255,22 @@ impl RenderableCell {
             && self.zerowidth.is_none()
     }
 
+    /// Apply [`CellRgb`] colors to the cell's colors.
+    fn compute_cell_rgb(
+        cell_fg: &mut Rgb,
+        cell_bg: &mut Rgb,
+        bg_alpha: &mut f32,
+        fg: CellRgb,
+        bg: CellRgb,
+    ) {
+        let old_fg = mem::replace(cell_fg, fg.color(*cell_fg, *cell_bg));
+        *cell_bg = bg.color(old_fg, *cell_bg);
+
+        if bg != CellRgb::CellBackground {
+            *bg_alpha = 1.0;
+        }
+    }
+
     /// Get the RGB color from a cell's foreground color.
     fn compute_fg_rgb(content: &mut RenderableContent<'_>, fg: Color, flags: Flags) -> Rgb {
         let ui_config = &content.config.ui_config;
@@ -339,18 +368,58 @@ impl RenderableCursor {
     }
 }
 
-/// Regex search highlight tracking.
-#[derive(Default)]
-pub struct RenderableSearch {
-    /// All visible search matches.
-    matches: Vec<RangeInclusive<Point>>,
+/// Regex hints for keyboard shortcuts.
+struct Hint<'a> {
+    /// Hint matches and position.
+    regex: Regex<'a>,
 
-    /// Index of the last match checked.
-    index: usize,
+    /// Last match checked against current cell position.
+    labels: &'a Vec<Vec<char>>,
+}
+
+impl<'a> Hint<'a> {
+    /// Advance the hint iterator.
+    ///
+    /// If the point is within a hint, the keyboard shortcut character that should be displayed at
+    /// this position will be returned.
+    ///
+    /// The tuple's [`bool`] will be `true` when the character is the first for this hint.
+    fn advance(&mut self, point: Point) -> Option<(char, bool)> {
+        // Check if we're within a match at all.
+        if !self.regex.advance(point) {
+            return None;
+        }
+
+        // Match starting position on this line; linebreaks interrupt the hint labels.
+        let start = self
+            .regex
+            .matches
+            .get(self.regex.index)
+            .map(|regex_match| regex_match.start())
+            .filter(|start| start.line == point.line)?;
+
+        // Position within the hint label.
+        let label_position = point.column.0 - start.column.0;
+        let is_first = label_position == 0;
+
+        // Hint label character.
+        self.labels[self.regex.index].get(label_position).copied().map(|c| (c, is_first))
+    }
+}
+
+impl<'a> From<&'a HintState> for Hint<'a> {
+    fn from(hint_state: &'a HintState) -> Self {
+        let regex = Regex { matches: Cow::Borrowed(hint_state.matches()), index: 0 };
+        Self { labels: hint_state.labels(), regex }
+    }
 }
 
-impl RenderableSearch {
-    /// Create a new renderable search iterator.
+/// Wrapper for finding visible regex matches.
+#[derive(Default, Clone)]
+pub struct RegexMatches(Vec<RangeInclusive<Point>>);
+
+impl RegexMatches {
+    /// Find all visible matches.
     pub fn new<T>(term: &Term<T>, dfas: &RegexSearch) -> Self {
         let viewport_end = term.grid().display_offset();
         let viewport_start = viewport_end + term.screen_lines().0 - 1;
@@ -383,12 +452,44 @@ impl RenderableSearch {
                 viewport_start..=viewport_end
             });
 
-        Self { matches: iter.collect(), index: 0 }
+        Self(iter.collect())
+    }
+}
+
+impl Deref for RegexMatches {
+    type Target = Vec<RangeInclusive<Point>>;
+
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl DerefMut for RegexMatches {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.0
+    }
+}
+
+/// Visible regex match tracking.
+#[derive(Default)]
+struct Regex<'a> {
+    /// All visible matches.
+    matches: Cow<'a, RegexMatches>,
+
+    /// Index of the last match checked.
+    index: usize,
+}
+
+impl<'a> Regex<'a> {
+    /// Create a new renderable regex iterator.
+    fn new<T>(term: &Term<T>, dfas: &RegexSearch) -> Self {
+        let matches = Cow::Owned(RegexMatches::new(term, dfas));
+        Self { index: 0, matches }
     }
 
-    /// Advance the search tracker to the next point.
+    /// Advance the regex tracker to the next point.
     ///
-    /// This will return `true` if the point passed is part of a search match.
+    /// This will return `true` if the point passed is part of a regex match.
     fn advance(&mut self, point: Point) -> bool {
         while let Some(regex_match) = self.matches.get(self.index) {
             if regex_match.start() > &point {
diff --git a/alacritty/src/display/hint.rs b/alacritty/src/display/hint.rs
new file mode 100644
index 00000000..6499a959
--- /dev/null
+++ b/alacritty/src/display/hint.rs
@@ -0,0 +1,264 @@
+use alacritty_terminal::term::Term;
+
+use crate::config::ui_config::Hint;
+use crate::daemon::start_daemon;
+use crate::display::content::RegexMatches;
+
+/// Percentage of characters in the hints alphabet used for the last character.
+const HINT_SPLIT_PERCENTAGE: f32 = 0.5;
+
+/// Keyboard regex hint state.
+pub struct HintState {
+    /// Hint currently in use.
+    hint: Option<Hint>,
+
+    /// Alphabet for hint labels.
+    alphabet: String,
+
+    /// Visible matches.
+    matches: RegexMatches,
+
+    /// Key label for each visible match.
+    labels: Vec<Vec<char>>,
+
+    /// Keys pressed for hint selection.
+    keys: Vec<char>,
+}
+
+impl HintState {
+    /// Initialize an inactive hint state.
+    pub fn new<S: Into<String>>(alphabet: S) -> Self {
+        Self {
+            alphabet: alphabet.into(),
+            hint: Default::default(),
+            matches: Default::default(),
+            labels: Default::default(),
+            keys: Default::default(),
+        }
+    }
+
+    /// Check if a hint selection is in progress.
+    pub fn active(&self) -> bool {
+        self.hint.is_some()
+    }
+
+    /// Start the hint selection process.
+    pub fn start(&mut self, hint: Hint) {
+        self.hint = Some(hint);
+    }
+
+    /// Cancel the hint highlighting process.
+    fn stop(&mut self) {
+        self.matches.clear();
+        self.labels.clear();
+        self.keys.clear();
+        self.hint = None;
+    }
+
+    /// Update the visible hint matches and key labels.
+    pub fn update_matches<T>(&mut self, term: &Term<T>) {
+        let hint = match self.hint.as_mut() {
+            Some(hint) => hint,
+            None => return,
+        };
+
+        // Find visible matches.
+        self.matches = hint.regex.with_compiled(|regex| RegexMatches::new(term, regex));
+
+        // Cancel highlight with no visible matches.
+        if self.matches.is_empty() {
+            self.stop();
+            return;
+        }
+
+        let mut generator = HintLabels::new(&self.alphabet, HINT_SPLIT_PERCENTAGE);
+        let match_count = self.matches.len();
+        let keys_len = self.keys.len();
+
+        // Get the label for each match.
+        self.labels.resize(match_count, Vec::new());
+        for i in (0..match_count).rev() {
+            let mut label = generator.next();
+            if label.len() >= keys_len && label[..keys_len] == self.keys[..] {
+                self.labels[i] = label.split_off(keys_len);
+            } else {
+                self.labels[i] = Vec::new();
+            }
+        }
+    }
+
+    /// Handle keyboard input during hint selection.
+    pub fn keyboard_input<T>(&mut self, term: &Term<T>, c: char) {
+        match c {
+            // Use backspace to remove the last character pressed.
+            '\x08' | '\x1f' => {
+                self.keys.pop();
+            },
+            // Cancel hint highlighting on ESC.
+            '\x1b' => self.stop(),
+            _ => (),
+        }
+
+        // Update the visible matches.
+        self.update_matches(term);
+
+        let hint = match self.hint.as_ref() {
+            Some(hint) => hint,
+            None => return,
+        };
+
+        // Find the last label starting with the input character.
+        let mut labels = self.labels.iter().enumerate().rev();
+        let (index, label) = match labels.find(|(_, label)| !label.is_empty() && label[0] == c) {
+            Some(last) => last,
+            None => return,
+        };
+
+        // Check if the selected label is fully matched.
+        if label.len() == 1 {
+            // Get text for the hint's regex match.
+            let hint_match = &self.matches[index];
+            let start = term.visible_to_buffer(*hint_match.start());
+            let end = term.visible_to_buffer(*hint_match.end());
+            let text = term.bounds_to_string(start, end);
+
+            // Append text as last argument and launch command.
+            let program = hint.command.program();
+            let mut args = hint.command.args().to_vec();
+            args.push(text);
+            start_daemon(program, &args);
+
+            self.stop();
+        } else {
+            // Store character to preserve the selection.
+            self.keys.push(c);
+        }
+    }
+
+    /// Hint key labels.
+    pub fn labels(&self) -> &Vec<Vec<char>> {
+        &self.labels
+    }
+
+    /// Visible hint regex matches.
+    pub fn matches(&self) -> &RegexMatches {
+        &self.matches
+    }
+
+    /// Update the alphabet used for hint labels.
+    pub fn update_alphabet(&mut self, alphabet: &str) {
+        if self.alphabet != alphabet {
+            self.alphabet = alphabet.to_owned();
+            self.keys.clear();
+        }
+    }
+}
+
+/// Generator for creating new hint labels.
+struct HintLabels {
+    /// Full character set available.
+    alphabet: Vec<char>,
+
+    /// Alphabet indices for the next label.
+    indices: Vec<usize>,
+
+    /// Point separating the alphabet's head and tail characters.
+    ///
+    /// To make identification of the tail character easy, part of the alphabet cannot be used for
+    /// any other position.
+    ///
+    /// All characters in the alphabet before this index will be used for the last character, while
+    /// the rest will be used for everything else.
+    split_point: usize,
+}
+
+impl HintLabels {
+    /// Create a new label generator.
+    ///
+    /// The `split_ratio` should be a number between 0.0 and 1.0 representing the percentage of
+    /// elements in the alphabet which are reserved for the tail of the hint label.
+    fn new(alphabet: impl Into<String>, split_ratio: f32) -> Self {
+        let alphabet: Vec<char> = alphabet.into().chars().collect();
+        let split_point = ((alphabet.len() - 1) as f32 * split_ratio.min(1.)) as usize;
+
+        Self { indices: vec![0], split_point, alphabet }
+    }
+
+    /// Get the characters for the next label.
+    fn next(&mut self) -> Vec<char> {
+        let characters = self.indices.iter().rev().map(|index| self.alphabet[*index]).collect();
+        self.increment();
+        characters
+    }
+
+    /// Increment the character sequence.
+    fn increment(&mut self) {
+        // Increment the last character; if it's not at the split point we're done.
+        let tail = &mut self.indices[0];
+        if *tail < self.split_point {
+            *tail += 1;
+            return;
+        }
+        *tail = 0;
+
+        // Increment all other characters in reverse order.
+        let alphabet_len = self.alphabet.len();
+        for index in self.indices.iter_mut().skip(1) {
+            if *index + 1 == alphabet_len {
+                // Reset character and move to the next if it's already at the limit.
+                *index = self.split_point + 1;
+            } else {
+                // If the character can be incremented, we're done.
+                *index += 1;
+                return;
+            }
+        }
+
+        // Extend the sequence with another character when nothing could be incremented.
+        self.indices.push(self.split_point + 1);
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn hint_label_generation() {
+        let mut generator = HintLabels::new("0123", 0.5);
+
+        assert_eq!(generator.next(), vec!['0']);
+        assert_eq!(generator.next(), vec!['1']);
+
+        assert_eq!(generator.next(), vec!['2', '0']);
+        assert_eq!(generator.next(), vec!['2', '1']);
+        assert_eq!(generator.next(), vec!['3', '0']);
+        assert_eq!(generator.next(), vec!['3', '1']);
+
+        assert_eq!(generator.next(), vec!['2', '2', '0']);
+        assert_eq!(generator.next(), vec!['2', '2', '1']);
+        assert_eq!(generator.next(), vec!['2', '3', '0']);
+        assert_eq!(generator.next(), vec!['2', '3', '1']);
+        assert_eq!(generator.next(), vec!['3', '2', '0']);
+        assert_eq!(generator.next(), vec!['3', '2', '1']);
+        assert_eq!(generator.next(), vec!['3', '3', '0']);
+        assert_eq!(generator.next(), vec!['3', '3', '1']);
+
+        assert_eq!(generator.next(), vec!['2', '2', '2', '0']);
+        assert_eq!(generator.next(), vec!['2', '2', '2', '1']);
+        assert_eq!(generator.next(), vec!['2', '2', '3', '0']);
+        assert_eq!(generator.next(), vec!['2', '2', '3', '1']);
+        assert_eq!(generator.next(), vec!['2', '3', '2', '0']);
+        assert_eq!(generator.next(), vec!['2', '3', '2', '1']);
+        assert_eq!(generator.next(), vec!['2', '3', '3', '0']);
+        assert_eq!(generator.next(), vec!['2', '3', '3', '1']);
+        assert_eq!(generator.next(), vec!['3', '2', '2', '0']);
+        assert_eq!(generator.next(), vec!['3', '2', '2', '1']);
+        assert_eq!(generator.next(), vec!['3', '2', '3', '0']);
+        assert_eq!(generator.next(), vec!['3', '2', '3', '1']);
+        assert_eq!(generator.next(), vec!['3', '3', '2', '0']);
+        assert_eq!(generator.next(), vec!['3', '3', '2', '1']);
+        assert_eq!(generator.next(), vec!['3', '3', '3', '0']);
+        assert_eq!(generator.next(), vec!['3', '3', '3', '1']);
+    }
+}
diff --git a/alacritty/src/display/mod.rs b/alacritty/src/display/mod.rs
index 9c37bd0e..d44013c4 100644
--- a/alacritty/src/display/mod.rs
+++ b/alacritty/src/display/mod.rs
@@ -38,6 +38,7 @@ use crate::display::bell::VisualBell;
 use crate::display::color::List;
 use crate::display::content::RenderableContent;
 use crate::display::cursor::IntoRects;
+use crate::display::hint::HintState;
 use crate::display::meter::Meter;
 use crate::display::window::Window;
 use crate::event::{Mouse, SearchState};
@@ -48,6 +49,7 @@ use crate::url::{Url, Urls};
 
 pub mod content;
 pub mod cursor;
+pub mod hint;
 pub mod window;
 
 mod bell;
@@ -181,6 +183,9 @@ pub struct Display {
     /// Mapped RGB values for each terminal color.
     pub colors: List,
 
+    /// State of the keyboard hints.
+    pub hint_state: HintState,
+
     renderer: QuadRenderer,
     glyph_cache: GlyphCache,
     meter: Meter,
@@ -317,10 +322,13 @@ impl Display {
             _ => (),
         }
 
+        let hint_state = HintState::new(config.ui_config.hints.alphabet());
+
         Ok(Self {
             window,
             renderer,
             glyph_cache,
+            hint_state,
             meter: Meter::new(),
             size_info,
             urls: Urls::new(),
@@ -474,12 +482,10 @@ impl Display {
         let viewport_match = search_state
             .focused_match()
             .and_then(|focused_match| terminal.grid().clamp_buffer_range_to_visible(focused_match));
-        let cursor_hidden = self.cursor_hidden || search_state.regex().is_some();
 
         // Collect renderable content before the terminal is dropped.
-        let dfas = search_state.dfas();
-        let colors = &self.colors;
-        let mut content = RenderableContent::new(&terminal, dfas, config, colors, !cursor_hidden);
+        let search_dfas = search_state.dfas();
+        let mut content = RenderableContent::new(config, self, &terminal, search_dfas);
         let mut grid_cells = Vec::new();
         while let Some(cell) = content.next() {
             grid_cells.push(cell);