Fix regex memory usage

This fixes an issue where regexes with a large number of possible states
would consume excessive memory, since the entire DFA was compiled ahead
of time.

To solve this, the DFA is now built at runtime using `regex-automata`'s
hybrid DFA.

There are however still some checks performed ahead of time, causing
errors with obscenely large regexes (`[0-9A-Za-z]{999999999}`), which
shouldn't cause any issues.

A regex which is large, but not large enough to fail the NFA
construction (like `[0-9A-Za-z]{999999}`) will cause a long search of
the entire grid, but will complete and show the match.

Closes #7097.

6 files changed, 24 insertions, 23 deletions

diff --git a/alacritty/src/config/ui_config.rs b/alacritty/src/config/ui_config.rs
index eb64f5b8..15423da5 100644
--- a/alacritty/src/config/ui_config.rs
+++ b/alacritty/src/config/ui_config.rs
@@ -485,7 +485,7 @@ impl LazyRegex {
     /// Execute a function with the compiled regex DFAs as parameter.
     pub fn with_compiled<T, F>(&self, f: F) -> Option<T>
     where
-        F: FnMut(&RegexSearch) -> T,
+        F: FnMut(&mut RegexSearch) -> T,
     {
         self.0.borrow_mut().compiled().map(f)
     }
@@ -514,7 +514,7 @@ impl LazyRegexVariant {
     ///
     /// If the regex is not already compiled, this will compile the DFAs and store them for future
     /// access.
-    fn compiled(&mut self) -> Option<&RegexSearch> {
+    fn compiled(&mut self) -> Option<&mut RegexSearch> {
         // Check if the regex has already been compiled.
         let regex = match self {
             Self::Compiled(regex_search) => return Some(regex_search),
@@ -578,8 +578,8 @@ mod tests {
             "ftp://ftp.example.org",
         ] {
             let term = mock_term(regular_url);
-            let regex = RegexSearch::new(URL_REGEX).unwrap();
-            let matches = visible_regex_match_iter(&term, &regex).collect::<Vec<_>>();
+            let mut regex = RegexSearch::new(URL_REGEX).unwrap();
+            let matches = visible_regex_match_iter(&term, &mut regex).collect::<Vec<_>>();
             assert_eq!(
                 matches.len(),
                 1,
@@ -599,8 +599,8 @@ mod tests {
             "mailto:",
         ] {
             let term = mock_term(url_like);
-            let regex = RegexSearch::new(URL_REGEX).unwrap();
-            let matches = visible_regex_match_iter(&term, &regex).collect::<Vec<_>>();
+            let mut regex = RegexSearch::new(URL_REGEX).unwrap();
+            let matches = visible_regex_match_iter(&term, &mut regex).collect::<Vec<_>>();
             assert!(
                 matches.is_empty(),
                 "Should not match url in string {url_like}, but instead got: {matches:?}"
diff --git a/alacritty/src/display/content.rs b/alacritty/src/display/content.rs
index 039808eb..ec0f4b6a 100644
--- a/alacritty/src/display/content.rs
+++ b/alacritty/src/display/content.rs
@@ -41,7 +41,7 @@ impl<'a> RenderableContent<'a> {
         config: &'a UiConfig,
         display: &'a mut Display,
         term: &'a Term<T>,
-        search_state: &'a SearchState,
+        search_state: &'a mut SearchState,
     ) -> Self {
         let search = search_state.dfas().map(|dfas| HintMatches::visible_regex_matches(term, dfas));
         let focused_match = search_state.focused_match();
@@ -486,7 +486,7 @@ impl<'a> HintMatches<'a> {
     }
 
     /// Create from regex matches on term visable part.
-    fn visible_regex_matches<T>(term: &Term<T>, dfas: &RegexSearch) -> Self {
+    fn visible_regex_matches<T>(term: &Term<T>, dfas: &mut RegexSearch) -> Self {
         let matches = hint::visible_regex_match_iter(term, dfas).collect::<Vec<_>>();
         Self::new(matches)
     }
diff --git a/alacritty/src/display/hint.rs b/alacritty/src/display/hint.rs
index 774b3cdb..8dffdeb5 100644
--- a/alacritty/src/display/hint.rs
+++ b/alacritty/src/display/hint.rs
@@ -90,7 +90,8 @@ impl HintState {
 
                 // Apply post-processing and search for sub-matches if necessary.
                 if hint.post_processing {
-                    self.matches.extend(matches.flat_map(|rm| {
+                    let mut matches = matches.collect::<Vec<_>>();
+                    self.matches.extend(matches.drain(..).flat_map(|rm| {
                         HintPostProcessor::new(term, regex, rm).collect::<Vec<_>>()
                     }));
                 } else {
@@ -289,7 +290,7 @@ impl HintLabels {
 /// Iterate over all visible regex matches.
 pub fn visible_regex_match_iter<'a, T>(
     term: &'a Term<T>,
-    regex: &'a RegexSearch,
+    regex: &'a mut RegexSearch,
 ) -> impl Iterator<Item = Match> + 'a {
     let viewport_start = Line(-(term.grid().display_offset() as i32));
     let viewport_end = viewport_start + term.bottommost_line();
@@ -344,7 +345,7 @@ pub fn visible_unique_hyperlinks_iter<T>(term: &Term<T>) -> impl Iterator<Item =
 fn regex_match_at<T>(
     term: &Term<T>,
     point: Point,
-    regex: &RegexSearch,
+    regex: &mut RegexSearch,
     post_processing: bool,
 ) -> Option<Match> {
     let regex_match = visible_regex_match_iter(term, regex).find(|rm| rm.contains(&point))?;
@@ -450,7 +451,7 @@ fn hyperlink_at<T>(term: &Term<T>, point: Point) -> Option<(Hyperlink, Match)> {
 /// Iterator over all post-processed matches inside an existing hint match.
 struct HintPostProcessor<'a, T> {
     /// Regex search DFAs.
-    regex: &'a RegexSearch,
+    regex: &'a mut RegexSearch,
 
     /// Terminal reference.
     term: &'a Term<T>,
@@ -467,7 +468,7 @@ struct HintPostProcessor<'a, T> {
 
 impl<'a, T> HintPostProcessor<'a, T> {
     /// Create a new iterator for an unprocessed match.
-    fn new(term: &'a Term<T>, regex: &'a RegexSearch, regex_match: Match) -> Self {
+    fn new(term: &'a Term<T>, regex: &'a mut RegexSearch, regex_match: Match) -> Self {
         let mut post_processor = Self {
             next_match: None,
             start: *regex_match.start(),
@@ -638,11 +639,11 @@ mod tests {
     fn closed_bracket_does_not_result_in_infinite_iterator() {
         let term = mock_term(" ) ");
 
-        let search = RegexSearch::new("[^/ ]").unwrap();
+        let mut search = RegexSearch::new("[^/ ]").unwrap();
 
         let count = HintPostProcessor::new(
             &term,
-            &search,
+            &mut search,
             Point::new(Line(0), Column(1))..=Point::new(Line(0), Column(1)),
         )
         .take(1)
@@ -694,9 +695,9 @@ mod tests {
         // The Term returned from this call will have a viewport starting at 0 and ending at 4096.
         // That's good enough for this test, since it only cares about visible content.
         let term = mock_term(&content);
-        let regex = RegexSearch::new("match!").unwrap();
+        let mut regex = RegexSearch::new("match!").unwrap();
 
         // The interator should match everything in the viewport.
-        assert_eq!(visible_regex_match_iter(&term, &regex).count(), 4096);
+        assert_eq!(visible_regex_match_iter(&term, &mut regex).count(), 4096);
     }
 }
diff --git a/alacritty/src/display/mod.rs b/alacritty/src/display/mod.rs
index 4037cd2e..255b587a 100644
--- a/alacritty/src/display/mod.rs
+++ b/alacritty/src/display/mod.rs
@@ -759,7 +759,7 @@ impl Display {
         scheduler: &mut Scheduler,
         message_buffer: &MessageBuffer,
         config: &UiConfig,
-        search_state: &SearchState,
+        search_state: &mut SearchState,
     ) {
         // Collect renderable content before the terminal is dropped.
         let mut content = RenderableContent::new(config, self, &terminal, search_state);
diff --git a/alacritty/src/event.rs b/alacritty/src/event.rs
index 387e768e..1b7e280c 100644
--- a/alacritty/src/event.rs
+++ b/alacritty/src/event.rs
@@ -154,8 +154,8 @@ impl SearchState {
     }
 
     /// Active search dfas.
-    pub fn dfas(&self) -> Option<&RegexSearch> {
-        self.dfas.as_ref()
+    pub fn dfas(&mut self) -> Option<&mut RegexSearch> {
+        self.dfas.as_mut()
     }
 
     /// Search regex text if a search is active.
@@ -637,7 +637,7 @@ impl<'a, N: Notify + 'a, T: EventListener> input::ActionContext<T> for ActionCon
     fn search_next(&mut self, origin: Point, direction: Direction, side: Side) -> Option<Match> {
         self.search_state
             .dfas
-            .as_ref()
+            .as_mut()
             .and_then(|dfas| self.terminal.search_next(dfas, origin, direction, side, None))
     }
 
@@ -913,7 +913,7 @@ impl<'a, N: Notify + 'a, T: EventListener> ActionContext<'a, N, T> {
 
     /// Jump to the first regex match from the search origin.
     fn goto_match(&mut self, mut limit: Option<usize>) {
-        let dfas = match &self.search_state.dfas {
+        let dfas = match &mut self.search_state.dfas {
             Some(dfas) => dfas,
             None => return,
         };
diff --git a/alacritty/src/window_context.rs b/alacritty/src/window_context.rs
index 332bdcd9..06dd68d6 100644
--- a/alacritty/src/window_context.rs
+++ b/alacritty/src/window_context.rs
@@ -398,7 +398,7 @@ impl WindowContext {
             scheduler,
             &self.message_buffer,
             &self.config,
-            &self.search_state,
+            &mut self.search_state,
         );
     }