How to output lines before and after a match while iterating over lines in a file?

Question

I am trying to replicate the -A and -B argument functionality from GNU grep in Rust. This prints out lines of text before and after a matched line read from a file or stdin. Example:

$ printf '1\n2\n3\nfoo\n4\n5\n6\n7\nfoo\n8\n9' | grep -A 1 -B 1 foo
3
foo
4
--
--
7
foo
8

My desired output would return n lines preceding and/or following a pattern match.

Using just stdin as an example, the simple case of just returning the matched line is easy to implement like this:

use std::io::{self, BufRead, BufReader, Result};
fn main() {
    for line in BufReader::new(io::stdin()).lines() {
        match line {
            Ok(l) => {
                if l.contains("foo"){
                    println!("{}", l);
                }
            }
            Err(e) => println!("error parsing line: {:?}", e),
        }
    }
}

output:

$ printf '1\n2\n3\nfoo\n4\n5\n6\n7\nfoo\n8\n9' | cargo run
foo
foo

However, returning the surrounding lines in an iterator like this does not seem possible, since the previous lines are no longer accessible upon each iteration of the loop.

I saw the Windows type, but it only works on a slice.

This sliding_windows crate appears to be the kind of functionality I want, but I cannot figure out how to get it to work with an iterator over lines from a file.

I also looked at itertools but did not see any kind of window iterator function that did this.

Before I get too deep in rolling my own form of line-buffer object in order to cache n previously seen lines (maybe some kind of ring buffer?), I was hoping that there might already be some method available in Rust that could easily accomplish this.

Answer 1

Implementing this efficiently is pretty tricky, and your instinct to use a roll buffer is pretty much on the money. This is what both GNU grep and ripgrep do. If you're willing to incur some dependencies, then you can pretty much achieve what you want by relying on some of ripgrep's internal libraries. For example, here's a program that does what you want which makes use of the grep-searcher crate:

use std::error::Error;
use std::io;

use grep_regex::RegexMatcher;
use grep_searcher::{Searcher, SearcherBuilder, Sink, SinkContext, SinkMatch};

fn main() -> Result<(), Box<dyn Error>> {
    let re = RegexMatcher::new(r"foo")?;
    let mut searcher = SearcherBuilder::new()
        .before_context(1)
        .after_context(1)
        .build();
    searcher.search_reader(
        &re,
        io::stdin().lock(),
        MySink(io::stdout().lock()),
    )?;
    Ok(())
}

struct MySink<W>(W);

impl<W: io::Write> Sink for MySink<W> {
    type Error = io::Error;

    fn matched(
        &mut self,
        _: &Searcher,
        mat: &SinkMatch,
    ) -> Result<bool, io::Error> {
        self.0.write_all(mat.bytes())?;
        Ok(true)
    }

    fn context(
        &mut self,
        _: &Searcher,
        ctx: &SinkContext,
    ) -> Result<bool, io::Error> {
        self.0.write_all(ctx.bytes())?;
        Ok(true)
    }

    fn context_break(
        &mut self,
        _: &Searcher,
    ) -> Result<bool, io::Error> {
        self.0.write_all(b"--\n")?;
        Ok(true)
    }
}

With the following dependencies:

[dependencies]
grep-regex = "0.1.5"
grep-searcher = "0.1.6"

Its output is:

$ printf '1\n2\n3\nfoo\n4\n5\n6\n7\nfoo\n8\n9' | ./target/release/grepex
3
foo
4
--
7
foo
8

The grep-regex dependency could be dropped if you don't need regexes, but it will require writing a bit more code to provide your own implementation of grep-matcher::Matcher (which is easier than it looks, if all you need is simple substring search).

If you did want to implement this yourself, then you could try reading the implementation inside grep-searcher. Effectively, it's all built on top of a roll buffer.

If performance is less of a concern, then you could do a line-by-line loop, and keep enough buffer available to store the previous N lines (where N is the size of your "before" window). When you find a match, print the previous N lines from your buffer. At the same time, start a counter at N that decreases by 1 with each successive line. While the counter is above 0, print the line, which will correspond to the "after" window. (This is not that dissimilar to what you'd do with a roll buffer.)

Answer 2

One approach is to develop a state machine that keeps a window of the last 2N+1 lines at all times. When a matching line is found, it adds a new entry to a list of to-be-printed pending matches, associated with a future line number. When that future line number is reached, the entries with that line number are printed, along with their lines of context pulled from the context window, keeping in mind that matches close to the beginnig of the input have fewer than N leading context lines. When the end of input is reached, any entries still pending are printed, keeping in mind these have fewer than N trailing context lines.

Good luck fighting Rust with all this mutation!