31. logden, alone

"Back Against the Wall."— Cage the Elephant

That is where this chapter puts you, deliberately: a specification, six checkpoints, and no walkthrough. Five projects have been read over your shoulder. This one is not.

Everything logden needs was taught. Not “mostly” and not “with a little searching” — every construct in the program below appears in a chapter you have read, and the sixth checkpoint is reachable with the contents of chapters 26 and 30 alone. That claim is the whole reason this chapter exists, and the only way to find out whether it is true is for you to write the program and for us to stay quiet.

The checkpoints are not solutions. Each one publishes an input and an expected output, and you check your work by diffing your program’s output against the transcript. What each milestone asks for is stated; how you get there is not. One hint per milestone, and no more.

31.1 The problem

logden is a query tool for a directory of log shards.

The den. Four files, s0.log through s3.log, in the directory the program runs in. Four is a number the program knows; it is not discovered at startup. These are the four this chapter’s transcripts were produced from, and you want them byte-for-byte if you intend to diff:

s0.log
06:12 wolf runs north
06:31 moon watches the ridge
07:02 wolf howls at the moon

s1.log
08:15 pack sleeps
08:52 wolf wakes alone
09:03 moonrise over the ridge
09:44 pack runs north

s2.log
10:05 ridge quiet
10:31 wolf and pack move north

s3.log
11:00 moon down
11:20 wolf alone at the ridge
11:47 pack howls north
12:02 nothing

The query. The command line is a list of terms:

$ ./logden wolf north

A line matches when it contains every term. Not any — every. With no terms on the command line the program searches for wolf.

The report. One line per shard, in shard order, naming the shard and how many of its lines matched:

s0.log 1
s1.log 0
s2.log 1
s3.log 0

Four lines, always four, in that order, whatever else happened. A shard with no matches reports zero rather than staying silent.

The exit status. Zero when anything matched, one when nothing did. This is what every grep on your machine does and it is what makes the program usable from a shell.

The shape. Each shard is indexed into its own region and frozen, and the four shards are searched concurrently — one task each, inside one scope. This is not a suggestion about how to be fast; it is part of the specification, because it is what the chapter is for.

The property. The four report lines are identical on every run of the same query against the same den. Not usually identical. Identical.

That is the whole specification. There is no more of it further down the page.

31.2 The milestone ladder

Six checkpoints. Each names what your program should print when you have reached it, so you can diff rather than wonder. Each carries one hint, and the hint is the margin note of somebody who has already made the mistake you are about to make.

Build and run the same way you have all part: wolf build logden.lu && ./logden.

M1 — ingest

Read the four shard files and report how many lines each holds.

$ wolf build logden.lu && ./logden
s0.log 3
s1.log 4
s2.log 2
s3.log 4

Hint. The counting is the half you finish first. The half that stops people is that reading a file can fail, and a function cannot use ? until its own signature admits that it can fail too. Fix main’s return type first and the rest of this milestone is four lines.

M2 — index

Give a shard a type, put each one in its own region, freeze it, and hold the four together. Print enough to prove the values survived: the shard’s position, its name, its line count, and its first line.

$ wolf build logden.lu && ./logden
0 s0.log 3 | 06:12 wolf runs north
1 s1.log 4 | 08:15 pack sleeps
2 s2.log 2 | 10:05 ridge quiet
3 s3.log 4 | 11:00 moon down

Hint. A shard is not a file. Decide what a shard is — what a query needs from it, and what it never needs again — before you decide what the region holds. The programs that get stuck here are the ones that froze a file and then wanted something else.

M3 — one query, one task

One shard, one term, one task inside one scope, and the answer arrives over a channel. Report the count for s0.log and the term wolf.

$ wolf build logden.lu && ./logden
s0.log wolf 2

Hint. A task hands nothing back except through a channel, and the receive has to happen where the value is still wanted. Put it in the wrong place relative to the scope’s closing brace and you read a number that was never sent, or wait for one that already arrived.

M4 — many tasks

Four shards, four tasks, one scope, one total. The term is still wolf.

$ wolf build logden.lu && ./logden
wolf 5

Hint. Write the four spawns out. Four is a constant in this program in every sense — a constant in the specification and a constant on the page — and a version that tries to compute it is a version that stops compiling for reasons you would rather meet later.

M5 — the query

Several terms with AND semantics, and a report that says which shard each hit came from. Terms are still in the source; the command line is M6’s. With wolf and north:

$ wolf build logden.lu && ./logden
s0.log 1
s1.log 0
s2.log 1
s3.log 0

Hint. Two things get decided here and only one of them looks hard. The one that looks like the work is AND, and it is a loop that returns early. The other is what a task’s message has to say now that there are four of them talking: a message is one word wide, so choose the word that lets the collector work out everything else.

M6 — the CLI

The command line, the exit status, and the property.

$ ./logden wolf north
s0.log 1
s1.log 0
s2.log 1
s3.log 0
$ echo $?
0
$ ./logden bear
s0.log 0
s1.log 0
s2.log 0
s3.log 0
$ echo $?
1

Hint. This one is the whole point. The other five milestones are plumbing you have laid before; this is the one where the program becomes something you would let another person run, and the part of it that matters is not the argument parsing. Run the finished program a hundred times with the same query and hash the output. If you get one hash, you designed for it in M5 without being told to. If you get two, the fix is not a lock.

That is the ladder. There are no solutions in this book for this chapter, and there is no appendix to turn to — the six hints above are the entire safety net, and they were rationed on purpose.

When it runs, and the hundred runs give one hash, you have written a concurrent tool in a language you met thirty chapters ago, and nothing in it is a trick. That was the front matter’s claim. This is where you find out.