Skip to content
Tutorials Center
My learning

Topics

Lesson 118 of 132 ยท Projects

Project: A grep Clone

Build a grep clone in Rust: a search function with lifetimes, case-insensitive matching, argument parsing, a tiny wildcard matcher, error types, exit codes and tests.

grep finds the lines of a file that contain some text. It is one of the most useful tools ever written, and a small version of it is one of the best Rust practice projects: it forces you to deal with borrowed strings and lifetimes, iterators, errors from the outside world (missing files, bad flags), exit codes and testable design, all in a program you can finish in an afternoon.

We will build minigrep in four stages. First the search function on its own, then the command-line options, then a tiny pattern matcher that understands ., *, ^ and $, and finally the complete program that reads real files. As in the to-do project, the logic is kept in plain functions, so every part can be checked without a terminal.

A real minigrep reads std::env::args(). Our editor starts programs without arguments, so the examples feed a list of arguments to the same code a real main would use. The last section shows the three-line main for your own machine, where you would run cargo run -- -n duck poem.txt.

Stage 1: the search function

The core question is: given a query and some text, which lines match? The answer should be the lines themselves, not copies of them. The text already exists in memory, so the result can borrow slices of it. That is where the lifetime comes in: the returned lines live as long as the text, not as long as the query.

First, see what happens if you do not say that. This is the most common stumbling block in the project:

Rust Missing lifetime specifier (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The compiler refuses with error[E0106]: missing lifetime specifier. It sees two input references and one output reference and cannot guess which input the output borrows from. The help note says so in plain words. You fix it by naming a lifetime and tying the result to contents only:

Rust Stage 1: search with a lifetime

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

What is going on:

  • lines() yields &str slices pointing into contents. enumerate() pairs them with a position, and filter and map build the result lazily until collect().
  • Hit<'a> stores a &'a str, so it needs the same lifetime parameter as the function. The result cannot outlive poem, which the compiler checks.
  • The last block proves the point of 'a: query is gone, but hits is still fine. If the signature had tied the result to query, that block would not compile.
  • to_lowercase() allocates a new string for every line. That is simple and correct enough for a first version. It is also not perfect for every language (some letters change length when lowercased, and some comparisons need full Unicode case folding). For ASCII-only input, eq_ignore_ascii_case on windows of bytes avoids the allocation; for serious work you would use a regex crate.

Use String::from in a nested block like the one above whenever you want to test whether a lifetime really is what you think it is. If shrinking the scope of a variable breaks the build, the result was tied to that variable.

Stage 2: configuration and options

Now the command line. We want this:

TEXT
minigrep [-i] [-n] [-c] [-v] [-e] <pattern> <file>...
  • -i ignore case, -n show line numbers, -c print only the number of matching lines, -v invert (print lines that do not match), -e treat the pattern as a mini pattern (stage 3).
  • The environment variable IGNORE_CASE also switches case-insensitive search on, the way the classic Rust book exercise does.

The arguments become a Config through Config::build, which returns a Result. The function takes any iterator of strings, so tests and main pass different things. It does not read the environment itself: the caller passes in whether IGNORE_CASE is set. Reading the environment inside deep code makes it hard to test, because tests share one process environment.

Rust Stage 2: parsing arguments into a Config

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Things to notice:

  • ..Config::default() is struct update syntax: set the fields you care about, take the rest from the default value. The derived Default gives empty strings and false everywhere.
  • args: impl IntoIterator<Item = String> accepts a Vec<String>, an array, or std::env::args().skip(1). The first thing a real main would do is Config::build(std::env::args().skip(1), std::env::var_os("IGNORE_CASE").is_some()).
  • Flags are only recognised before the pattern. After the first non-flag argument, flags_done becomes true, so a file called -v can still be searched. The special argument -- ends the flags explicitly, which is a convention you know from many tools. The last attempt, ["--", "-v", "poem.txt"], therefore searches for the pattern -v in poem.txt.
  • UnknownFlag(arg) moves the String into the error. No clone is needed because we return immediately.

Stage 3: a tiny pattern matcher

Plain contains is not what makes grep powerful; patterns are. A full regular-expression engine is a big project (the standard library has none, and real programs use the regex crate). A tiny subset is a classic exercise and fits on one screen:

Pattern Meaning
c the literal character c
. any single character
c* zero or more of the character before the star
^ at the start of the pattern: the match must begin at the start of the line
$ at the end of the pattern: the match must end at the end of the line

The algorithm is a short recursion, usually credited to Brian Kernighan and Rob Pike. It works on slices of characters, and Rust's slice patterns make it read almost like a specification:

Rust Stage 3: a matcher for . * ^ $

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Walk through match_here the way the computer does:

  1. An empty pattern matches everything that is left. This is the success case of the recursion.
  2. [c, '*', rest @ ..] is checked before the plain character rule, because x* must be treated as a unit. match_star tries to match the rest of the pattern after zero copies of c; if that fails, it consumes one more matching character and tries again.
  3. ['$'] succeeds only if no text is left.
  4. Otherwise the first pattern character must equal (or be . for) the first text character, and we continue with both tails.

is_match slides the starting position along the line unless the pattern starts with ^. The range 0..=line.len() includes the empty position at the end, so an empty-ish pattern such as x* still matches an empty line.

This matcher is a teaching tool. It can take exponential time on nasty patterns such as a*a*a*a*a*b against a long string of as, it has no character classes, no +, ?, groups or escapes, and a literal * or $ cannot be searched for. If you need real patterns in a program, use the regex crate (regex = "1" in Cargo.toml), whose engine runs in linear time. See regular expressions and parsing.

Stage 4: the complete program

Now put it together: a Matcher that hides the choice between plain text and the mini pattern, a run function that reads each file and writes the results, and an error type that remembers which file failed. Output goes to a writer, not straight to the terminal, and the exit status follows the convention of the real grep: 0 when something matched, 1 when nothing matched, 2 on errors.

The program first creates two small files in the current directory (they exist only while this run lasts), then runs minigrep several times on them.

Rust Stage 4: the complete minigrep

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Read the output against the flags. A few points explain the design:

  • Case handling. With -i, the pattern is lowercased once in Matcher::new and each line is lowercased before matching. That is why the doc comment on Matcher::is_match says the line must already be lowercased: the invariant is documented where it matters.
  • hit == config.invert is the whole implementation of -v. A line is skipped when "matched" equals "inverted": without -v, skip non-matching lines; with -v, skip matching ones.
  • Several files. With more than one path, each output line gets the file name as a prefix. label_files.then_some(path.as_str()) turns a bool into an Option<&str> in one expression.
  • A missing file does not stop the search. The error goes to err, the loop continues, and the final status is 2. That matches how grep behaves, and it is why run uses a local failed flag instead of ? for read errors. Only a failure to write output aborts.
  • AppError::Io keeps the path and the source error. Display shows both, and source() lets error-reporting code walk the chain. The text after the file name (No such file or directory (os error 2)) comes from the operating system.
  • The closure (|| -> Result<u8, AppError> { ... })() is a small trick to use ? inside a function that returns a plain u8. In your own code you would usually make run return Result<u8, AppError> and convert it in main.

On your machine, main becomes tiny:

Rust
// Read-only: a real main for a Cargo project (needs real command-line arguments).
use std::process::ExitCode;

fn main() -> ExitCode {
    let args: Vec<String> = std::env::args().skip(1).collect();
    let ignore_case = std::env::var_os("IGNORE_CASE").is_some();
    let (mut out, mut err) = (std::io::stdout().lock(), std::io::stderr().lock());
    // ... build the Config, call search_text for each file, as in `run` above ...
    ExitCode::from(status)
}

The two shortcuts we took to fit one file are worth fixing in a real project: run buffers everything in a Vec<u8> (a real tool writes straight to stdout().lock() wrapped in a BufWriter), and read_to_string loads the whole file into memory (a real tool reads line by line with BufReader, so it can search files bigger than RAM, and stops cleanly when the other end of a pipe closes).

Testing

The pure functions are easy to test, and the stage 4 design makes whole runs testable too. Put this at the bottom of the file and run cargo test on your own machine. It is read-only here because the editor runs programs, not test harnesses.

Rust
#[cfg(test)]
mod tests {
    use super::*;

    const TEXT: &str = "Rust is fast.\nTrust me.\nrust never sleeps.";

    #[test]
    fn case_sensitive_finds_two_lines() {
        let config = Config { pattern: "rust".into(), ..Config::default() };
        let mut out = Vec::new();
        let count = search_text(&config, &Matcher::new(&config), None, TEXT, &mut out).unwrap();
        assert_eq!(count, 2); // "Trust me." and "rust never sleeps."
    }

    #[test]
    fn invert_flips_the_selection() {
        let config = Config { pattern: "rust".into(), invert: true, ..Config::default() };
        let mut out = Vec::new();
        search_text(&config, &Matcher::new(&config), None, TEXT, &mut out).unwrap();
        assert_eq!(String::from_utf8(out).unwrap(), "Rust is fast.\n");
    }

    #[test]
    fn mini_pattern_anchors() {
        assert!(is_match("^Rust", "Rust is fast."));
        assert!(!is_match("^rust", "Trust me."));
        assert!(is_match("s*$", "sleeps"));
    }

    #[test]
    fn unknown_flag_is_an_error() {
        let args = ["-q".to_string(), "x".to_string(), "f".to_string()];
        assert_eq!(Config::build(args, false), Err(ConfigError::UnknownFlag("-q".into())));
    }
}

Test the edges, not just the happy path: an empty file, a file whose last line has no newline, a pattern longer than the line, a pattern with * at the start, and non-ASCII text. A line-based tool should also decide what to do with invalid UTF-8. read_to_string returns an error for it, while real grep treats the data as bytes; the standard library function String::from_utf8_lossy is the cheap way to be forgiving.

Ideas to extend it

  1. Add -w to match whole words only. What counts as a word boundary: any non-alphanumeric character, or only spaces?
  2. Add -A <n> context lines after each match. This needs the matcher to look back and ahead; an iterator of (index, line) and a small counter is enough.
  3. Search directories recursively with std::fs::read_dir, skipping files that are not text.
  4. Use threads to search many files in parallel and then print the results in file order. See parallel patterns.
  5. Replace the mini matcher with a regex-based one when you move to Cargo.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In fn search<'a>(query: &str, contents: &'a str) -> Vec<Hit<'a>>, what does the lifetime 'a promise?

    Only contents carries 'a, so the returned hits are tied to it. query has its own anonymous lifetime and may be dropped earlier.
  2. 2. Why does Config::build take ignore_case_from_env: bool instead of reading the environment itself?

    Passing the value in lets tests choose it per call. Reading global state inside would make tests depend on and disturb each other.
  3. 3. What does the compiler error E0106: missing lifetime specifier tell you about fn search(query: &str, contents: &str) -> Vec<&str>?

    Lifetime elision only works with one input reference (or &self). With two, you must name the lifetime that the output is tied to.
  4. 4. How does the stage 4 code implement the -v (invert) option?

    Without -v (invert == false) non-matching lines are skipped; with -v (invert == true) matching lines are skipped. One comparison covers both.
  5. 5. What does an exit status of 1 mean for the real grep and for our clone?

    0 means something was selected, 1 means nothing was selected, and 2 means an error occurred, so scripts can tell 'no match' from 'failure'.

Summary

  • A search function that returns slices of its input needs a named lifetime tied to that input; otherwise rustc reports E0106.
  • lines().enumerate().filter(...).map(...).collect() is the idiomatic shape of a line search.
  • Build configuration with a function that takes impl IntoIterator<Item = String> and returns Result<Config, ConfigError>; pass environment values in as parameters.
  • Slice patterns ([c, '*', rest @ ..]) make small recursive matchers short and readable, but a hand-written matcher is a teaching tool; use the regex crate for real work.
  • Write output through impl Write and keep exit codes meaningful (0 match, 1 none, 2 error).
  • Error types that remember the path and the source error make failures understandable.

Next: Project: Bank Account System