grep: fix bugs in handling multi-line look-around

This commit hacks in a bug fix for handling look-around across multiple
lines. The main problem is that by the time the matching lines are sent
to the printer, the surrounding context---which some look-behind or
look-ahead might have matched---could have been dropped if it wasn't
part of the set of matching lines. Therefore, when the printer re-runs
the regex engine in some cases (to do replacements, color matches, etc
etc), it won't be guaranteed to see the same matches that the searcher
found.

Overall, this is a giant clusterfuck and suggests that the way I divided
the abstraction boundary between the printer and the searcher is just
wrong. It's likely that the searcher needs to handle more of the work of
matching and pass that info on to the printer. The tricky part is that
this additional work isn't always needed. Ultimately, this means a
serious re-design of the interface between searching and printing. Sigh.

The way this fix works is to smuggle the underlying buffer used by the
searcher through into the printer. Since these bugs only impact
multi-line search (otherwise, searches are only limited to matches
across a single line), and since multi-line search always requires
having the entire file contents in a single contiguous slice (memory
mapped or on the heap), it follows that the buffer we pass through when
we need it is, in fact, the entire haystack. So this commit refactors
the printer's regex searching to use that buffer instead of the intended
bundle of bytes containing just the relevant matching portions of that
same buffer.

There is one last little hiccup: PCRE2 doesn't seem to have a way to
specify an ending position for a search. So when we re-run the search to
find matches, we can't say, "but don't search past here." Since the
buffer is likely to contain the entire file, we really cannot do
anything here other than specify a fixed upper bound on the number of
bytes to search. So if look-ahead goes more than N bytes beyond the
match, this code will break by simply being unable to find the match. In
practice, this is probably pretty rare. I believe that if we did a
better fix for this bug by fixing the interfaces, then we'd probably try
to have PCRE2 find the pertinent matches up front so that it never needs
to re-discover them.

Fixes #1412

1 files changed, 179 insertions, 6 deletions

diff --git a/crates/matcher/src/lib.rs b/crates/matcher/src/lib.rs
index 2bcd0c12..4859de39 100644
--- a/crates/matcher/src/lib.rs
+++ b/crates/matcher/src/lib.rs
@@ -618,12 +618,31 @@ pub trait Matcher {
     fn find_iter<F>(
         &self,
         haystack: &[u8],
+        matched: F,
+    ) -> Result<(), Self::Error>
+    where
+        F: FnMut(Match) -> bool,
+    {
+        self.find_iter_at(haystack, 0, matched)
+    }
+
+    /// Executes the given function over successive non-overlapping matches
+    /// in `haystack`. If no match exists, then the given function is never
+    /// called. If the function returns `false`, then iteration stops.
+    ///
+    /// The significance of the starting point is that it takes the surrounding
+    /// context into consideration. For example, the `\A` anchor can only
+    /// match when `at == 0`.
+    fn find_iter_at<F>(
+        &self,
+        haystack: &[u8],
+        at: usize,
         mut matched: F,
     ) -> Result<(), Self::Error>
     where
         F: FnMut(Match) -> bool,
     {
-        self.try_find_iter(haystack, |m| Ok(matched(m)))
+        self.try_find_iter_at(haystack, at, |m| Ok(matched(m)))
             .map(|r: Result<(), ()>| r.unwrap())
     }
 
@@ -637,12 +656,35 @@ pub trait Matcher {
     fn try_find_iter<F, E>(
         &self,
         haystack: &[u8],
+        matched: F,
+    ) -> Result<Result<(), E>, Self::Error>
+    where
+        F: FnMut(Match) -> Result<bool, E>,
+    {
+        self.try_find_iter_at(haystack, 0, matched)
+    }
+
+    /// Executes the given function over successive non-overlapping matches
+    /// in `haystack`. If no match exists, then the given function is never
+    /// called. If the function returns `false`, then iteration stops.
+    /// Similarly, if the function returns an error then iteration stops and
+    /// the error is yielded. If an error occurs while executing the search,
+    /// then it is converted to
+    /// `E`.
+    ///
+    /// The significance of the starting point is that it takes the surrounding
+    /// context into consideration. For example, the `\A` anchor can only
+    /// match when `at == 0`.
+    fn try_find_iter_at<F, E>(
+        &self,
+        haystack: &[u8],
+        at: usize,
         mut matched: F,
     ) -> Result<Result<(), E>, Self::Error>
     where
         F: FnMut(Match) -> Result<bool, E>,
     {
-        let mut last_end = 0;
+        let mut last_end = at;
         let mut last_match = None;
 
         loop {
@@ -696,12 +738,33 @@ pub trait Matcher {
         &self,
         haystack: &[u8],
         caps: &mut Self::Captures,
+        matched: F,
+    ) -> Result<(), Self::Error>
+    where
+        F: FnMut(&Self::Captures) -> bool,
+    {
+        self.captures_iter_at(haystack, 0, caps, matched)
+    }
+
+    /// Executes the given function over successive non-overlapping matches
+    /// in `haystack` with capture groups extracted from each match. If no
+    /// match exists, then the given function is never called. If the function
+    /// returns `false`, then iteration stops.
+    ///
+    /// The significance of the starting point is that it takes the surrounding
+    /// context into consideration. For example, the `\A` anchor can only
+    /// match when `at == 0`.
+    fn captures_iter_at<F>(
+        &self,
+        haystack: &[u8],
+        at: usize,
+        caps: &mut Self::Captures,
         mut matched: F,
     ) -> Result<(), Self::Error>
     where
         F: FnMut(&Self::Captures) -> bool,
     {
-        self.try_captures_iter(haystack, caps, |caps| Ok(matched(caps)))
+        self.try_captures_iter_at(haystack, at, caps, |caps| Ok(matched(caps)))
             .map(|r: Result<(), ()>| r.unwrap())
     }
 
@@ -716,12 +779,36 @@ pub trait Matcher {
         &self,
         haystack: &[u8],
         caps: &mut Self::Captures,
+        matched: F,
+    ) -> Result<Result<(), E>, Self::Error>
+    where
+        F: FnMut(&Self::Captures) -> Result<bool, E>,
+    {
+        self.try_captures_iter_at(haystack, 0, caps, matched)
+    }
+
+    /// Executes the given function over successive non-overlapping matches
+    /// in `haystack` with capture groups extracted from each match. If no
+    /// match exists, then the given function is never called. If the function
+    /// returns `false`, then iteration stops. Similarly, if the function
+    /// returns an error then iteration stops and the error is yielded. If
+    /// an error occurs while executing the search, then it is converted to
+    /// `E`.
+    ///
+    /// The significance of the starting point is that it takes the surrounding
+    /// context into consideration. For example, the `\A` anchor can only
+    /// match when `at == 0`.
+    fn try_captures_iter_at<F, E>(
+        &self,
+        haystack: &[u8],
+        at: usize,
+        caps: &mut Self::Captures,
         mut matched: F,
     ) -> Result<Result<(), E>, Self::Error>
     where
         F: FnMut(&Self::Captures) -> Result<bool, E>,
     {
-        let mut last_end = 0;
+        let mut last_end = at;
         let mut last_match = None;
 
         loop {
@@ -819,13 +906,35 @@ pub trait Matcher {
         haystack: &[u8],
         caps: &mut Self::Captures,
         dst: &mut Vec<u8>,
+        append: F,
+    ) -> Result<(), Self::Error>
+    where
+        F: FnMut(&Self::Captures, &mut Vec<u8>) -> bool,
+    {
+        self.replace_with_captures_at(haystack, 0, caps, dst, append)
+    }
+
+    /// Replaces every match in the given haystack with the result of calling
+    /// `append` with the matching capture groups.
+    ///
+    /// If the given `append` function returns `false`, then replacement stops.
+    ///
+    /// The significance of the starting point is that it takes the surrounding
+    /// context into consideration. For example, the `\A` anchor can only
+    /// match when `at == 0`.
+    fn replace_with_captures_at<F>(
+        &self,
+        haystack: &[u8],
+        at: usize,
+        caps: &mut Self::Captures,
+        dst: &mut Vec<u8>,
         mut append: F,
     ) -> Result<(), Self::Error>
     where
         F: FnMut(&Self::Captures, &mut Vec<u8>) -> bool,
     {
-        let mut last_match = 0;
-        self.captures_iter(haystack, caps, |caps| {
+        let mut last_match = at;
+        self.captures_iter_at(haystack, at, caps, |caps| {
             let m = caps.get(0).unwrap();
             dst.extend(&haystack[last_match..m.start]);
             last_match = m.end;
@@ -1039,6 +1148,18 @@ impl<'a, M: Matcher> Matcher for &'a M {
         (*self).find_iter(haystack, matched)
     }
 
+    fn find_iter_at<F>(
+        &self,
+        haystack: &[u8],
+        at: usize,
+        matched: F,
+    ) -> Result<(), Self::Error>
+    where
+        F: FnMut(Match) -> bool,
+    {
+        (*self).find_iter_at(haystack, at, matched)
+    }
+
     fn try_find_iter<F, E>(
         &self,
         haystack: &[u8],
@@ -1050,6 +1171,18 @@ impl<'a, M: Matcher> Matcher for &'a M {
         (*self).try_find_iter(haystack, matched)
     }
 
+    fn try_find_iter_at<F, E>(
+        &self,
+        haystack: &[u8],
+        at: usize,
+        matched: F,
+    ) -> Result<Result<(), E>, Self::Error>
+    where
+        F: FnMut(Match) -> Result<bool, E>,
+    {
+        (*self).try_find_iter_at(haystack, at, matched)
+    }
+
     fn captures(
         &self,
         haystack: &[u8],
@@ -1070,6 +1203,19 @@ impl<'a, M: Matcher> Matcher for &'a M {
         (*self).captures_iter(haystack, caps, matched)
     }
 
+    fn captures_iter_at<F>(
+        &self,
+        haystack: &[u8],
+        at: usize,
+        caps: &mut Self::Captures,
+        matched: F,
+    ) -> Result<(), Self::Error>
+    where
+        F: FnMut(&Self::Captures) -> bool,
+    {
+        (*self).captures_iter_at(haystack, at, caps, matched)
+    }
+
     fn try_captures_iter<F, E>(
         &self,
         haystack: &[u8],
@@ -1082,6 +1228,19 @@ impl<'a, M: Matcher> Matcher for &'a M {
         (*self).try_captures_iter(haystack, caps, matched)
     }
 
+    fn try_captures_iter_at<F, E>(
+        &self,
+        haystack: &[u8],
+        at: usize,
+        caps: &mut Self::Captures,
+        matched: F,
+    ) -> Result<Result<(), E>, Self::Error>
+    where
+        F: FnMut(&Self::Captures) -> Result<bool, E>,
+    {
+        (*self).try_captures_iter_at(haystack, at, caps, matched)
+    }
+
     fn replace<F>(
         &self,
         haystack: &[u8],
@@ -1107,6 +1266,20 @@ impl<'a, M: Matcher> Matcher for &'a M {
         (*self).replace_with_captures(haystack, caps, dst, append)
     }
 
+    fn replace_with_captures_at<F>(
+        &self,
+        haystack: &[u8],
+        at: usize,
+        caps: &mut Self::Captures,
+        dst: &mut Vec<u8>,
+        append: F,
+    ) -> Result<(), Self::Error>
+    where
+        F: FnMut(&Self::Captures, &mut Vec<u8>) -> bool,
+    {
+        (*self).replace_with_captures_at(haystack, at, caps, dst, append)
+    }
+
     fn is_match(&self, haystack: &[u8]) -> Result<bool, Self::Error> {
         (*self).is_match(haystack)
     }