user/grep.c

C · 108 lines · annotated 100% · user program / library · upstream

About this file

grep pattern [file ...] prints every line of its input that matches a regular expression. grep ^xv6 README prints the lines of README that start with xv6; ls | grep sh filters the output of ls. With no file names it reads standard input, so it works as a filter in a pipeline.

The file has two independent halves:

grep() and main() (lines 8–63) deal with I/O: reading input in chunks with read, cutting it into lines, and writing matching lines to standard output. This is the interesting systems part: read returns arbitrary chunks, not lines, so the program must handle lines that straddle two reads.
match, matchhere and matchstar (lines 65–108) are a complete regular expression matcher in about 30 lines, from Kernighan and Pike. It supports c (a literal character), . (any character), * (zero or more of the previous character), ^ (start of line) and $ (end of line). There are no character classes and no escapes: there is no way to match only a literal . (it always matches any character), and * is literal only where it cannot repeat anything: at the start of the pattern or right after another c*.

The shell does not strip quotes, so write patterns without them: grep x.*v6 README, not grep 'x.*v6' README (the quotes would become part of the pattern).

Read before: user/cat.c (the read loop). Read next: user/wc.c.

Show notes inline

1// Simple grep.  Only supports ^ . * $ operators.
2
3#include "kernel/types.h"
4#include "kernel/stat.h"
5#include "kernel/fcntl.h"
6#include "user/user.h"
7
8char buf[1024];
9int match(char *, char *);
10
11void
12grep(char *pattern, int fd)
13{
14  int n, m;
15  char *p, *q;
16
17  m = 0;
18  while ((n = read(fd, buf + m, sizeof(buf) - m - 1)) > 0) {
19    m += n;
20    buf[m] = '\0';
21    p = buf;
22    while ((q = strchr(p, '\n')) != 0) {
23      *q = 0;
24      if (match(pattern, p)) {
25        *q = '\n';
26        write(1, p, q + 1 - p);
27      }
28      p = q + 1;
29    }
30    if (m > 0) {
31      m -= p - buf;
32      memmove(buf, p, m);
33    }
34  }
35}
36
37int
38main(int argc, char *argv[])
39{
40  int fd, i;
41  char *pattern;
42
43  if (argc <= 1) {
44    fprintf(2, "usage: grep pattern [file ...]\n");
45    exit(1);
46  }
47  pattern = argv[1];
48
49  if (argc <= 2) {
50    grep(pattern, 0);
51    exit(0);
52  }
53
54  for (i = 2; i < argc; i++) {
55    if ((fd = open(argv[i], O_RDONLY)) < 0) {
56      printf("grep: cannot open %s\n", argv[i]);
57      exit(1);
58    }
59    grep(pattern, fd);
60    close(fd);
61  }
62  exit(0);
63}
64
65// Regexp matcher from Kernighan & Pike,
66// The Practice of Programming, Chapter 9, or
67// https://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html
68
69int matchhere(char *, char *);
70int matchstar(int, char *, char *);
71
72int
73match(char *re, char *text)
74{
75  if (re[0] == '^')
76    return matchhere(re + 1, text);
77  do { // must look at empty string
78    if (matchhere(re, text))
79      return 1;
80  } while (*text++ != '\0');
81  return 0;
82}
83
84// matchhere: search for re at beginning of text
85int
86matchhere(char *re, char *text)
87{
88  if (re[0] == '\0')
89    return 1;
90  if (re[1] == '*')
91    return matchstar(re[0], re + 2, text);
92  if (re[0] == '$' && re[1] == '\0')
93    return *text == '\0';
94  if (*text != '\0' && (re[0] == '.' || re[0] == *text))
95    return matchhere(re + 1, text + 1);
96  return 0;
97}
98
99// matchstar: search for c*re at beginning of text
100int
101matchstar(int c, char *re, char *text)
102{
103  do { // a * matches zero or more instances
104    if (matchhere(re, text))
105      return 1;
106  } while (*text != '\0' && (*text++ == c || c == '.'));
107  return 0;
108}

Lines 1–6
What this grep supports, and headersThe comment is accurate: the four operators ^ . * $ plus ordinary characters are
the whole language. kernel/fcntl.h is needed for O_RDONLY; kernel/stat.h is
not used.

Lines 8–9
Line buffer and a forward declarationbuf holds input that has been read but not yet split into lines: at most 1023 bytes
plus a terminating NUL. It is global, so it is in .bss section rather than on the
stack.
match is defined at the bottom of the file but called by grep above it, so it
must be declared first; C requires a declaration before a call.

Line 8
Unexamined input: up to 1023 bytes plus a NUL.

Line 9
Declare match before its first use on line 24.

Lines 11–35
grep(): split the input into lines and test each onem counts the bytes in buf that are waiting to be examined. Each read appends new
data after them (buf + m), asking for at most the room left minus one byte for a
terminating NUL. Then the inner loop finds each complete line with strchr,
temporarily replaces its newline with a NUL so that match sees a C string ending
at the end of the line, and writes the line (newline restored) to descriptor 1 if it
matches. Finally, lines 30–33 slide the incomplete last line, if any, to the start of
buf so the next read can complete it.
Three limits follow from this design:
A line longer than 1022 characters stops grep. When buf holds 1023 bytes and
no newline, line 18 asks read for 0 bytes; read returns 0, which looks like end
of file, and the rest of that file (or of standard input) is silently ignored. (On a
pipe, the 0-byte read first waits until more data arrives or the writer closes,
then returns 0.)
A last line with no newline is never tested. When read returns 0, the loop
ends and whatever is left in buf is dropped.
Read errors are not reported. read returning -1 also ends the loop quietly.
The if (m > 0) test on line 30 is always true here, since the loop body runs only
after a read that returned at least one byte.

Line 17
The buffer starts empty.

Line 18
Append up to sizeof(buf) - m - 1 new bytes after the m already waiting
(sys_read). The - 1 keeps room for the NUL written on line 20. The loop
runs while read returns data; 0 (end of input) or -1 (error) ends it.

Line 19
Count the new bytes.

Line 20
Terminate the data with a NUL so that strchr on line 22 stops at the end of
what was read instead of running into stale bytes from an earlier read.

Line 21
p marks the start of the next line to examine.

Line 22
Find the next newline. If there is none, the rest of buf is an incomplete line and
the loop stops.

Line 23
Cut the line off at its newline so match sees exactly this line as a string.

Line 24
Test the line against the pattern.

Line 25
Put the newline back, so it is printed with the line.

Line 26
Write the line, newline included: q + 1 - p bytes starting at p, to descriptor 1.

Line 28
Move past the newline to the start of the next line.

Line 30
Always true here (see the block note), so the test is harmless but redundant.

Line 31
p - buf bytes were consumed as complete lines; what remains is the start of an
incomplete line.

Line 32
Slide that partial line to the front of buf. memmove is used rather than
memcpy because source and destination may overlap.

Lines 37–63
main(): a pattern, then standard input or filesargv[1] is the pattern; any further arguments are files. With no pattern
the usage message goes to descriptor 2 and grep exits with status 1
(exit status). With a pattern but no files it reads descriptor 0,
standard input.
Files are handled as in user/cat.c: open read-only, process, close, so the same
descriptor number is reused for each file. Unlike cat, the “cannot open” message on
line 56 uses printf, so it goes to standard output, not standard error: with
grep x a nofile > out the message ends up inside out. That is a small bug; the
usage message on line 44 does it right. As in cat, a missing file stops the whole
run. Unlike Unix grep, the exit status does not say whether any line matched: it is
0 whenever all files could be opened.

Line 43
No pattern given.

Line 44
Usage message on standard error.

Line 47
The first argument is the pattern.

Line 49
A pattern but no files.

Line 50
Filter standard input.

Line 55
Open each file read-only (sys_open).

Line 56
This error goes to standard output, not standard error (see the block note).

Line 59
Print the matching lines of this file.

Line 60
Free the descriptor for the next file (sys_close).

Lines 65–70
The matcher, from The Practice of ProgrammingThis matcher was written by Rob Pike and published by Brian Kernighan and Pike in
The Practice of Programming (1999), and later discussed by Kernighan in the essay at
the URL above. It is a classic example of how much a few lines of recursion can do.
The two prototypes are needed because match, matchhere and matchstar call
each other. All three work on C strings: re is the rest of the pattern still to be
matched, text the rest of the line.

Lines 72–82
match(): try every starting positionA pattern without ^ may match anywhere in the line, so match tries
matchhere at each position in turn: at text, then text + 1, and so on. The
first success means the line matches. With ^, only the first position is tried, and
the ^ itself is skipped.
The do ... while with the post-increment tries one more position than there are
characters: the empty string at the very end of the line. That is what the comment
“must look at empty string” means. It matters for patterns that can match zero
characters: $ must match at the end of every line, and x* must match even an
empty line.
The search stops at the first match; grep only needs to know whether the line
matches, not where.

Line 75
A leading ^ anchors the pattern to the start of the line.

Line 76
Match the rest of the pattern at position 0 only.

Line 77
Unanchored: try each starting position, including the empty string at the end.

Line 78
Does the pattern match starting here?

Line 80
Advance to the next position. The test uses the character before the increment, so
the last iteration runs with text pointing at the terminating NUL.

Line 81
No starting position worked.

Lines 84–97
matchhere(): does re match a prefix of text?matchhere answers “does the pattern re match at the very start of text?” (the
comment’s “at beginning of text”). It looks at the first element of the pattern and
handles one of five cases, in this order:
The pattern is empty: everything has been matched. Success, no matter what text
remains.
The second pattern character is *: hand the starred character and the rest of
the pattern to matchstar. This must be checked before case 4, so that a*
is not treated as a literal a.
The pattern is exactly $: match only if the text has ended. A $ anywhere else
in the pattern is an ordinary character.
The text is not empty and the first pattern character is . or equals the first
text character: both advance by one and the rest is matched recursively.
Anything else: failure.
Each recursive call removes at least one character from the pattern, so the
recursion depth is at most the pattern’s length. A ^ that is not the first pattern
character reaches case 4 and is compared literally.

Line 88
Case 1: pattern used up, success.

Line 90
Case 2: the next pattern element is x*.

Line 91
Pass the starred character, the pattern after the *, and the text.

Line 92
Case 3: $ as the last pattern character.

Line 93
Matches only at the end of the text.

Line 94
Case 4: one character matches: . matches anything, otherwise the characters must be
equal. The *text != '\0' check stops . from matching the end of the string.

Line 95
Advance both and match the rest.

Line 96
Case 5: no match here.

Lines 99–108
matchstar(): c* followed by the rest of the patternmatchstar tries to match the rest of the pattern after skipping zero copies of
c, then one, then two, and so on, for as long as the next text character is c (or
any character, if c is .). It is shortest-first: it succeeds with the fewest
repetitions that let the rest match. For a yes/no answer that is as good as
longest-first.
Worked example: pattern a.*c against the line xabc.
match tries position 0, xabc: matchhere("a.*c", "xabc"). a is not x,
case 5, fail.
match tries position 1, abc: matchhere("a.*c", "abc"). a equals a, so
case 4 recurses with matchhere(".*c", "bc").
Now re[1] is *, so case 2 calls matchstar('.', "c", "bc").
Zero copies: matchhere("c", "bc"), c is not b, fail. The loop condition
consumes b (any character matches .), and text becomes "c".
One copy: matchhere("c", "c") matches c and recurses to
matchhere("", ""): the pattern is empty, success.
The 1 returns all the way up and grep prints the line. If no number of repetitions
works, the loop stops at the end of the text or at the first character that is not
c, and the result is 0.
Because matchstar may try every repetition count and each of those may call
matchstar again, a pattern with many stars can take a long time on a long line;
this backtracking is the price of the matcher’s simplicity.

Line 103
Try the rest of the pattern after the current number of cs (zero on the first
iteration).

Line 104
The rest matched: the whole c*re matched.

Line 106
If the text is not over and its next character is c (or c is .), consume it and
try again with one more repetition. *text++ is evaluated before the ||, so the
character is consumed in both cases.

Line 107
No number of repetitions let the rest match.