Skip to content

Grep

Search files for lines that contain a string, with grep’s -n, -l, -i, -v and -x flags.

Adapted from Exercism’s problem specification (MIT). Listed under Strings & Text.

// FILE: grep.nomi
//# A small `grep`: searches files for lines that match a string, with the
//# canonical flags.

import
    std::fs
    std::io
end

/// The canonical flags.
pub enum Flag
    /// `-n`: put each line's number, from 1, before it.
    LineNumbers
    /// `-l`: answer the names of the files with a match, not the lines.
    FileNames
    /// `-i`: compare without regard to case.
    IgnoreCase
    /// `-v`: answer the lines that do not match.
    Invert
    /// `-x`: match only a line that is the whole pattern.
    WholeLine
end

/// The lines of `files` that contain `pattern`, in file order, as `flags`
/// say. With more than one file each line starts with its file's name.
/// A file that cannot be read is the error reading it gave.
pub fn grep(
    pattern: String,
    flags:   Set<Flag>,
    files:   List<String>,
) -> Result<List<String>, io.Error>
    named = Iter.count(files) > 1

    files
    |> Iter.map(&search(&1, pattern, flags, named))
    |> Result.collect()?
    |> Iter.flatten()
    |> Iter.to_list()
    |> Ok()
end

/// What `grep` answers for one file.
fn search(
    file:    String,
    pattern: String,
    flags:   Set<Flag>,
    named:   Bool,
) -> Result<List<String>, io.Error>
    text = fs.read_text(file)?

    found =
        String.lines(text)
        |> Iter.with_index()
        |> Iter.filter(fn (_index, line) -> matches(line, pattern, flags))
        |> Iter.to_list()

    if .FileNames in flags then
        Ok(if Iter.is_empty(found) then [] else [file])
    else
        found
        |> Iter.map(fn (index, line) ->
            file_part = if named then "${file}:" else ""

            number_part = if .LineNumbers in flags then "${index + 1}:" else ""

            file_part + number_part + line
        end)
        |> Iter.to_list()
        |> Ok()
    end
end

fn matches(line: String, pattern: String, flags: Set<Flag>) -> Bool
    (line, pattern) = if .IgnoreCase in flags then
        (String.fold_case(line), String.fold_case(pattern))
    else
        (line, pattern)
    end

    found = if .WholeLine in flags then
        line == pattern
    else
        pattern in line
    end

    found != (.Invert in flags)
end

// FILE: grep_test.nomi
import
    std::fs::testing.{self, Sandbox}
    std::io
    grep.{self, Flag}
end

once all_files = ["iliad.txt", "midsummer-night.txt", "paradise-lost.txt"]

once sandbox = Sandbox{
    files: {
        "iliad.txt" => """
            Achilles sing, O Goddess! Peleus' son;
            His wrath pernicious, who ten thousand woes
            Caused to Achaia's host, sent many a soul
            Illustrious into Ades premature,
            And Heroes gave (so stood the will of Jove)
            To dogs and to all ravening fowls a prey,
            When fierce dispute had separated once
            The noble Chief Achilles from the son
            Of Atreus, Agamemnon, King of men.
            """,
        "midsummer-night.txt" => """
            I do entreat your grace to pardon me.
            I know not by what power I am made bold,
            Nor how it may concern my modesty,
            In such a presence here to plead my thoughts;
            But I beseech your grace that I may know
            The worst that may befall me in this case,
            If I refuse to wed Demetrius.
            """,
        "paradise-lost.txt" => """
            Of Mans First Disobedience, and the Fruit
            Of that Forbidden Tree, whose mortal tast
            Brought Death into the World, and all our woe,
            With loss of Eden, till one greater Man
            Restore us, and regain the blissful Seat,
            Sing Heav'nly Muse, that on the secret top
            Of Oreb, or of Sinai, didst inspire
            That Shepherd, who first taught the chosen Seed
            """,
    },
}

/// What `grep` answers over the three canonical files, each read from an
/// in-memory file system.
fn grep_in_sandbox(
    pattern: String,
    flags:   Set<Flag>,
    files:   List<String>,
) -> Result<List<String>, io.Error>
    testing.run(sandbox, fn -> grep.grep(pattern, flags, files)).value
end

test "Test grepping a single file"
    [
        (
            "One file, one match, no flags",
            "Agamemnon",
            Set[],
            "iliad.txt",
            ["Of Atreus, Agamemnon, King of men."],
        ),
        (
            "One file, one match, print line numbers flag",
            "Forbidden",
            Set[Flag.LineNumbers],
            "paradise-lost.txt",
            ["2:Of that Forbidden Tree, whose mortal tast"],
        ),
        (
            "One file, one match, case-insensitive flag",
            "FORBIDDEN",
            [.IgnoreCase],
            "paradise-lost.txt",
            ["Of that Forbidden Tree, whose mortal tast"],
        ),
        (
            "One file, one match, print file names flag",
            "Forbidden",
            [.FileNames],
            "paradise-lost.txt",
            ["paradise-lost.txt"],
        ),
        (
            "One file, one match, match entire lines flag",
            "With loss of Eden, till one greater Man",
            [.WholeLine],
            "paradise-lost.txt",
            ["With loss of Eden, till one greater Man"],
        ),
        (
            "One file, one match, multiple flags",
            "OF ATREUS, Agamemnon, KIng of MEN.",
            [.LineNumbers, .IgnoreCase, .WholeLine],
            "iliad.txt",
            ["9:Of Atreus, Agamemnon, King of men."],
        ),
        (
            "One file, several matches, no flags",
            "may",
            [],
            "midsummer-night.txt",
            [
                "Nor how it may concern my modesty,",
                "But I beseech your grace that I may know",
                "The worst that may befall me in this case,",
            ],
        ),
        (
            "One file, several matches, print line numbers flag",
            "may",
            [.LineNumbers],
            "midsummer-night.txt",
            [
                "3:Nor how it may concern my modesty,",
                "5:But I beseech your grace that I may know",
                "6:The worst that may befall me in this case,",
            ],
        ),
        (
            "One file, several matches, match entire lines flag",
            "may",
            [.WholeLine],
            "midsummer-night.txt",
            [],
        ),
        (
            "One file, several matches, case-insensitive flag",
            "ACHILLES",
            [.IgnoreCase],
            "iliad.txt",
            ["Achilles sing, O Goddess! Peleus' son;", "The noble Chief Achilles from the son"],
        ),
        (
            "One file, several matches, inverted flag",
            "Of",
            [.Invert],
            "paradise-lost.txt",
            [
                "Brought Death into the World, and all our woe,",
                "With loss of Eden, till one greater Man",
                "Restore us, and regain the blissful Seat,",
                "Sing Heav'nly Muse, that on the secret top",
                "That Shepherd, who first taught the chosen Seed",
            ],
        ),
        (
            "One file, no matches, various flags",
            "Gandalf",
            [.LineNumbers, .FileNames, .WholeLine, .IgnoreCase],
            "iliad.txt",
            [],
        ),
        (
            "One file, one match, file flag takes precedence over line flag",
            "ten",
            [.LineNumbers, .FileNames],
            "iliad.txt",
            ["iliad.txt"],
        ),
        (
            "One file, several matches, inverted and match entire lines flags",
            "Illustrious into Ades premature,",
            [.WholeLine, .Invert],
            "iliad.txt",
            [
                "Achilles sing, O Goddess! Peleus' son;",
                "His wrath pernicious, who ten thousand woes",
                "Caused to Achaia's host, sent many a soul",
                "And Heroes gave (so stood the will of Jove)",
                "To dogs and to all ravening fowls a prey,",
                "When fierce dispute had separated once",
                "The noble Chief Achilles from the son",
                "Of Atreus, Agamemnon, King of men.",
            ],
        ),
    ]
    |> subtests (description, pattern, flags, file, expected), description
        assert grep_in_sandbox(pattern, flags, [file]) == Ok(expected)
    end
end

test "Test grepping multiples files at once"
    [
        (
            "Multiple files, one match, no flags",
            "Agamemnon",
            Set[],
            ["iliad.txt:Of Atreus, Agamemnon, King of men."],
        ),
        (
            "Multiple files, several matches, no flags",
            "may",
            Set[],
            [
                "midsummer-night.txt:Nor how it may concern my modesty,",
                "midsummer-night.txt:But I beseech your grace that I may know",
                "midsummer-night.txt:The worst that may befall me in this case,",
            ],
        ),
        (
            "Multiple files, several matches, print line numbers flag",
            "that",
            Set[Flag.LineNumbers],
            [
                "midsummer-night.txt:5:But I beseech your grace that I may know",
                "midsummer-night.txt:6:The worst that may befall me in this case,",
                "paradise-lost.txt:2:Of that Forbidden Tree, whose mortal tast",
                "paradise-lost.txt:6:Sing Heav'nly Muse, that on the secret top",
            ],
        ),
        (
            "Multiple files, one match, print file names flag",
            "who",
            [.FileNames],
            ["iliad.txt", "paradise-lost.txt"],
        ),
        (
            "Multiple files, several matches, case-insensitive flag",
            "TO",
            [.IgnoreCase],
            [
                "iliad.txt:Caused to Achaia's host, sent many a soul",
                "iliad.txt:Illustrious into Ades premature,",
                "iliad.txt:And Heroes gave (so stood the will of Jove)",
                "iliad.txt:To dogs and to all ravening fowls a prey,",
                "midsummer-night.txt:I do entreat your grace to pardon me.",
                "midsummer-night.txt:In such a presence here to plead my thoughts;",
                "midsummer-night.txt:If I refuse to wed Demetrius.",
                "paradise-lost.txt:Brought Death into the World, and all our woe,",
                "paradise-lost.txt:Restore us, and regain the blissful Seat,",
                "paradise-lost.txt:Sing Heav'nly Muse, that on the secret top",
            ],
        ),
        (
            "Multiple files, several matches, inverted flag",
            "a",
            [.Invert],
            [
                "iliad.txt:Achilles sing, O Goddess! Peleus' son;",
                "iliad.txt:The noble Chief Achilles from the son",
                "midsummer-night.txt:If I refuse to wed Demetrius.",
            ],
        ),
        (
            "Multiple files, one match, match entire lines flag",
            "But I beseech your grace that I may know",
            [.WholeLine],
            ["midsummer-night.txt:But I beseech your grace that I may know"],
        ),
        (
            "Multiple files, one match, multiple flags",
            "WITH LOSS OF EDEN, TILL ONE GREATER MAN",
            [.LineNumbers, .IgnoreCase, .WholeLine],
            ["paradise-lost.txt:4:With loss of Eden, till one greater Man"],
        ),
        (
            "Multiple files, no matches, various flags",
            "Frodo",
            [.LineNumbers, .FileNames, .WholeLine, .IgnoreCase],
            [],
        ),
        (
            "Multiple files, several matches, file flag takes precedence over line number flag",
            "who",
            [.LineNumbers, .FileNames],
            ["iliad.txt", "paradise-lost.txt"],
        ),
        (
            "Multiple files, several matches, inverted and match entire lines flags",
            "Illustrious into Ades premature,",
            [.WholeLine, .Invert],
            [
                "iliad.txt:Achilles sing, O Goddess! Peleus' son;",
                "iliad.txt:His wrath pernicious, who ten thousand woes",
                "iliad.txt:Caused to Achaia's host, sent many a soul",
                "iliad.txt:And Heroes gave (so stood the will of Jove)",
                "iliad.txt:To dogs and to all ravening fowls a prey,",
                "iliad.txt:When fierce dispute had separated once",
                "iliad.txt:The noble Chief Achilles from the son",
                "iliad.txt:Of Atreus, Agamemnon, King of men.",
                "midsummer-night.txt:I do entreat your grace to pardon me.",
                "midsummer-night.txt:I know not by what power I am made bold,",
                "midsummer-night.txt:Nor how it may concern my modesty,",
                "midsummer-night.txt:In such a presence here to plead my thoughts;",
                "midsummer-night.txt:But I beseech your grace that I may know",
                "midsummer-night.txt:The worst that may befall me in this case,",
                "midsummer-night.txt:If I refuse to wed Demetrius.",
                "paradise-lost.txt:Of Mans First Disobedience, and the Fruit",
                "paradise-lost.txt:Of that Forbidden Tree, whose mortal tast",
                "paradise-lost.txt:Brought Death into the World, and all our woe,",
                "paradise-lost.txt:With loss of Eden, till one greater Man",
                "paradise-lost.txt:Restore us, and regain the blissful Seat,",
                "paradise-lost.txt:Sing Heav'nly Muse, that on the secret top",
                "paradise-lost.txt:Of Oreb, or of Sinai, didst inspire",
                "paradise-lost.txt:That Shepherd, who first taught the chosen Seed",
            ],
        ),
    ]
    |> subtests (description, pattern, flags, expected), description
        assert grep_in_sandbox(pattern, flags, all_files) == Ok(expected)
    end
end

// Not a canonical case: the exercise reads only files that exist.
test "a missing file is the error reading it"
    assert grep_in_sandbox("Of", [], ["odyssey.txt"]) == Err(io.Error.NotFound{path: "odyssey.txt"})
end
  • The files are read with std/fs’s fs.read_text and split with String.lines. The tests never touch the disk: grep_in_sandbox runs each search inside std::fs::testing.run over a Sandbox holding the three canonical files, so std/fs reads them from an in-memory file system rooted at /work, and a relative name such as iliad.txt resolves there.
  • The flags are a Set<Flag> of a Flag enum, so a case writes the flags it sets, as grep’s command line does: Set[.LineNumbers, .IgnoreCase]. The order the canonical data lists flags in never matters, which a set says and a list of flag strings would not. An Options struct of five Bool fields defaulting to False was the other form; the set is shorter in the tables, and the first row that names a flag writes Flag.LineNumbers, so neither table needs a type annotation. The solution asks .IgnoreCase in flags where the struct read options.ignore_case.
  • grep answers Result<List<String>, io.Error>. A file that cannot be read is the error fs.read_text gave, passed up with ?; one file’s error stops the search, through Result.collect()?. The canonical data has no such case; the test file adds one, marked not canonical, for a missing file.
  • matches folds the case of both sides with String.fold_case for -i, compares the whole line or looks for the pattern in it for -x, and turns the answer over for -v with found != (.Invert in flags).
  • -l answers the file’s name once if any line matched and takes precedence over -n, as two canonical cases ask. With more than one file each line starts with its file’s name.
  • Each canonical group is a test with one subtests table named by the description column.