Projectsgrep
A command-line program that prints the lines of a file, a folder tree or piped input that match a pattern, and says through its exit code whether anything matched, like the Unix grep tool. You can lean on a regular-expression library or write the matching engine yourself, and either way you learn what a pattern really is: a small language that is parsed into a structure and run as a machine over every line.
From Coding Challenges #9 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 7 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
Matching is the heart of grep on both tracks. On the hard track you build one of these machines, and on the easy track you pick a library and need to know which kind it is, because every user's pattern runs against every line of every file.
Covers: finite automata, NFA and DFA · tracking every possible state at once · backtracking and its exponential worst case · back-references, which no automaton can match · deciding yes or no versus finding where
Regular Expression Matching Can Be Simple And Fast (Russ Cox) ↗ · Details of the Cloudflare outage on July 2, 2019 (Cloudflare blog) ↗ · Regular expression Denial of Service, ReDoS (OWASP) ↗
Each step adds syntax, from the empty pattern to classes and anchors. A parsed structure lets you add each piece without rewriting the matcher, and on the easy track it's where you translate grep's dialect into your library's.
Covers: tokens and escapes · precedence of repetition, sequence and alternation · basic versus extended syntax · the empty pattern · invalid patterns
Let's Build a Regex Engine (kean.blog) ↗ · A Regular Expression Matcher (Rob Pike and Brian Kernighan, from Beautiful Code) ↗ · POSIX base definitions: Regular Expressions ↗
Steps 5 and 6 add the two shorthand classes and the two anchors. For backslash d the page, not GNU grep, is the reference, because the two disagree.
Covers: shorthand classes for digits and word characters · bracket expressions, ranges and negation · what the locale puts in a class · anchors match positions, not characters
GNU grep manual: Character Classes and Bracket Expressions ↗ · GNU grep manual: Special Backslash Expressions ↗ · Regular-Expressions.info: Start and End of String or Line Anchors ↗
The final step adds -i. The sample files are plain ASCII, but real text isn't, and a fold that only knows A to Z quietly misses É and é.
Covers: case folding versus lowercasing · simple versus full folding · language rules, such as the Turkish i · folding the parsed pattern, not its text
Unicode FAQ: Character Properties, Case Mappings and Names ↗ · UTS #18 Unicode Regular Expressions: Simple Loose Matches ↗ · Dotted and dotless I in computing (Wikipedia) ↗
Step 3 searches a folder that contains a subfolder, and every matching line has to say which file it came from.
Covers: depth-first traversal · symbolic links and cycles · unreadable files and directories · the order of entries · who expands the star
GNU grep manual: File and Directory Selection ↗ · ftw(3) and nftw, Linux manual page ↗ · symlink(7), Linux manual page ↗
Step 2 makes the exit code part of the result, and later steps add -v and files that can't be read, which change what each code means.
Covers: three answers: selected, none selected, error · what -v changes · errors on standard error · the status of a pipeline
GNU grep manual: Exit Status ↗ · POSIX grep utility (see EXIT STATUS) ↗ · Bash manual: Pipelines ↗
The first step must print every line back exactly as it was, and step 4 only works if the program reads standard input when no file is named.
Covers: the line as the unit of matching and output · files and standard input read the same way · memory bounded by the longest line · searching the buffer, not every line · output buffering in a pipeline
why GNU grep is fast (Mike Haertel) ↗ · getline(3), Linux manual page ↗ · setvbuf(3), Linux manual page ↗
What you'll build · 8 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project, save the challenge's Project Gutenberg text as the main test file, and unpack the challenge's test data next to it: a list of rock bands, a file of symbols and a subfolder with one more text file.
Works whenThe test folder holds the four files, one of them inside the subfolder, and the real grep runs on them so you can compare your results with it.
Given an empty pattern and a file, print every line of the file, because the empty pattern matches every line.
Works whenThe output is identical to the input file, so comparing the two with diff shows no difference.
Concepts: the pattern is a language · line-oriented streaming
Given a single letter, print every line that contains it anywhere. Exit with 0 when at least one line matched and with a non-zero code when none did.
Works whenSearching the band list for a capital J prints only the three bands with a J in their names, and the exit code is 0. A letter that appears nowhere prints nothing and gives a non-zero code.
Concepts: regular expressions as machines · exit codes as an interface
With -r, search every file below the named directories, and put the file's path and a colon before each matching line.
Works whenSearching the test folder recursively for Nirvana gives five lines: one from the band list and four from the file in the subfolder, each with its path in front.
Concepts: walking a directory tree · exit codes as an interface
With -v, print the lines that don't match. When no file is named, read standard input, so the program can take another program's output through a pipe.
Works whenPiping the recursive search from the last step into the program with -v and the word Madonna leaves only the line from the band list.
Concepts: line-oriented streaming · exit codes as an interface
Support backslash d, which matches any digit, and backslash w, which matches a letter, a digit or an underscore.
Works whenSearching the subfolder's file for a digit prints the five lines that contain one, and searching the symbols file for a word character prints only the two lines that hold a word. Compare with the page, not with GNU grep, which reads backslash d as a plain d.
Concepts: character classes and anchors · the pattern is a language · regular expressions as machines
Support the caret, which ties the pattern to the start of a line, and the dollar sign, which ties it to the end.
Works whenA caret followed by A lists only the bands whose names start with A, and na followed by a dollar sign matches only Nirvana.
Concepts: character classes and anchors · the pattern is a language · regular expressions as machines
With -i, match letters regardless of their case.
Works whenIn the band list, a capital A appears on 8 lines, and with -i the letter matches 58 lines.
Concepts: case-insensitive matching beyond ASCII