grep

grep prints the lines that contain a pattern. Two things in it are worth building by hand: the search itself, and the exit code, which is the part people forget is a feature.

Substring search, done the obvious way, is two nested loops. Try the first position: do the bytes match, one by one, until the pattern runs out? If the pattern ran out, that is a match. If a byte disagreed, give up and try the next starting position. That is O(n×m) in the worst case, and the worst case needs input like aaaaaaaaab searched for aaab, which does not happen to a line of text. There are cleverer algorithms, Boyer-Moore and friends, and they exist because the naive one is genuinely good enough almost always.

The program

const std = @import("std");

/// The naive search, written out rather than called, because it is the thing
/// worth seeing once: try every start position, compare forward, give up on
/// the first mismatch. O(n*m) in the worst case and fine for a line of text.
fn find(haystack: []const u8, needle: []const u8) ?usize {
    if (needle.len == 0) return 0;
    if (needle.len > haystack.len) return null;

    var start: usize = 0;
    while (start + needle.len <= haystack.len) : (start += 1) {
        var i: usize = 0;
        while (i < needle.len and haystack[start + i] == needle[i]) : (i += 1) {}
        if (i == needle.len) return start;
    }
    return null;
}

/// Returns whether anything matched, which is what the exit code reports.
/// grep's contract is that "found nothing" is not an error, and a shell
/// pipeline depends on being able to tell those two apart.
fn grep(text: []const u8, pattern: []const u8, out: *std.Io.Writer) !bool {
    var lines: std.Io.Reader = .fixed(text);
    var matched = false;
    var number: usize = 0;

    while (try lines.takeDelimiter('\n')) |line| {
        number += 1;
        if (find(line, pattern) != null) {
            matched = true;
            try out.print("{d}:{s}\n", .{ number, line });
        }
    }
    return matched;
}

pub fn main(init: std.process.Init) !void {
    var buf: [1024]u8 = undefined;
    var stdout_writer = std.Io.File.stdout().writerStreaming(init.io, &buf);
    const out = &stdout_writer.interface;

    const text =
        \\the quick brown fox
        \\jumps over the lazy dog
        \\the end
        \\
    ;

    for ([_][]const u8{ "the", "fox", "cat" }) |pattern| {
        try out.print("--- grep \"{s}\"\n", .{pattern});
        const matched = try grep(text, pattern, out);
        // 0 when something matched, 1 when nothing did. Not an error either way.
        try out.print("exit {d}\n\n", .{@intFromBool(!matched)});
    }

    try out.flush();
}

What just happened

Three searches, and the third found nothing. Look at what it printed: exit 1. Not an error, not a message on stderr, just a different status.

This is the part that makes grep composable, and it is a design decision you would not arrive at by thinking about searching. A shell needs to ask “does this file mention the pattern” without caring about the output, and it does that with if grep -q pattern file; then. For that to work, “found nothing” has to be a reportable outcome rather than a failure. grep uses 0 for found, 1 for not found, and 2 for an actual error like a missing file. Three outcomes, one small integer, which is exactly the point made in Talking to the Operating System.

The line number came from counting, not from the search. Nothing in the input marks where line 2 starts. The loop over takeDelimiter('\n') counts as it goes, which is the same streaming shape as the last two chapters.

Matching is on bytes, and that is a real limitation. Searching for é works, because its two bytes are compared like any others. Searching case-insensitively does not, because upper-casing a byte is only meaningful in ASCII. Real grep with -i on UTF-8 has to know about Unicode case folding, which is a much larger problem than the search.

Check yourself

The search returns ?usize, the position of a match, rather than bool. It only ever gets compared against null here. Why not return bool?

Because the position is the thing a caller usually needs next, and it costs nothing to return. grep -o prints just the matched part; grep --color highlights it; a replace tool needs to know where to splice. Returning bool throws away information the loop already had. This is a small instance of a useful habit: return what you found, not merely that you found it.

If you have written C

The search is the same, and C’s standard library will do it for you:

char *hit = strstr(line, pattern);   /* NULL when absent */

Two differences matter. strstr needs both strings null-terminated, so it cannot search a slice of a larger buffer without you cutting it first, which usually means copying. Zig’s version takes lengths, so searching part of a buffer is free.

And strstr returns a pointer into the haystack, which is a position and an alias at the same time. Getting the index means hit - line, pointer arithmetic that is only valid because both point into the same array. Returning ?usize says the same thing without the aliasing.

The standard library has this as std.mem.find, covered in String Recipes. The version here is written out because the loop is worth seeing once.

Next: sort, the first tool that cannot stream.