George V. Reilly

Exploring Wordle

Tue, 26 Sep 2023 07:00:00 GMT

Unless YOUVE LIVED UNDER ROCKS, you've heard of Wordle, the online word game that has become wildly popular since late 2021. You've probably seen people posting their Wordle games as grids of little green, yellow, and black (or white) emojis on social media.

Wordle 797 4/6

⬛ ⬛ ⬛ ⬛ 🟨

🟨 ⬛ 🟩 ⬛ ⬛

⬛ ⬛ 🟩 🟨 ⬛

🟩 🟩 🟩 🟩 🟩

The problem that I want to address in this post is:

Given some GUESS=SCORE pairs for Wordle and a word list, programmatically find all the words from the list that are eligible as answers.

Let's look at this four-round game for Wordle 797:

J	U	D	G	E	JUDGE=....e
C	H	E	S	T	CHEST=c.E..
W	R	E	C	K	WRECK=..Ec.
O	C	E	A	N	OCEAN=OCEAN

The letters of each guess are colored Green, Yellow, or Black (dark-gray).

A Green tile 🟩 means that the letter is correct: E is the third letter of the answer.
A Yellow tile 🟨 means that the letter is present elsewhere in the answer. There is a C in the answer; it's not in columns 1 or 4, but it is correct in column 2. Likewise, an E is present in the answer; it's not in column 5, but it's correct in column 3.
A Black tile ⬛ is absent from the answer: J, U, D, G, H, S, T, W, R, and K do not appear anywhere in OCEAN.

(This definition of “absent” turns out to be inadequate, as you will discover later.)

The GUESS=SCORE notation is intended to be clear to read and also easier to write than Greens and Yellows. For example:

GUESS=SCORE

CHEST=c.E..

the uppercase E at position 3 in the score denotes that E is in the correct position (i.e., green 🟩);
the lowercase c at position 1 in the score denotes that C is present somewhere in the answer, but it is in the wrong position (yellow 🟨);
the .s in the score at positions 2, 4, and 5 denote that the corresponding letters in the guess (H, S, and T, respectively) are absent from the answer (black ⬛).

Deducing Constraints

What can we deduce from the first three rows of guesses, JUDGE=....e CHEST=c.E.. WRECK=..Ec.?

There is a set of valid letters, C and E, that are either present (yellow 🟨) or correct (green 🟩). Both E and C start out as present, but E later finds its correct position, while C does not.

There is a set of invalid letters that are known to be absent from the answer (black ⬛): J, U, D, G, H, S, T, W, R, and K.

The remaining letters of the alphabet are currently unknown. When they are played, they will turn into valid or invalid letters. Unless we already have all five correct letters, we will draw candidate letters from the unknown pool.

Furthermore, we know something about letter positions. The correct letters are in the correct positions, while the present letters are in the wrong positions.

A candidate word must:

include all valid letters — C and E
exclude all invalid letters — JUDGHSTWRK
match all “correct” positions — 3:E
not match any “present” positions — 1:C, 4:C, or 5:E

These constraints narrow the possible choices from the word list.

The obvious way to solve this with a computer is to codify the constraints provided by previous guess–score pairs and run through the entire list of words to find eligible words. But no human solves Wordle by methodically examining thousands of words. Instead, you rack your brain for “what ends in SE and has an M?” or “I've tried A, E, and I; will O or U work?” or “What are the most likely letters left on the keyboard at the bottom?”

This article will show you how to solve Wordle programmatically. It won't help you much in playing Wordle by hand, though you may understand more about the game when you're finished reading.

Prototyping with Pipes

Let's prototype the above constraints with a series of grep's in a Unix pipeline tailored to this OCEAN example:

# JUDGE=....e CHEST=c.E.. WRECK=..Ec.

grep '^.....$' /usr/share/dict/words |  # Extract five-letter words
    tr 'a-z' 'A-Z' |                    # Translate each word to uppercase
    grep '^..E..$' |                    # Match CORRECT positions
    awk '/C/ && /E/' |                  # Match ALL of VALID set, CORRECT|PRESENT
    grep -v '[JUDGHSTWRK]' |            # Exclude INVALID set
    grep '^[^C]..[^C][^E]$'             # Exclude PRESENT positions

gives:

ICENI
ILEAC
OCEAN
OLEIC

(This was in Bash, on macOS 13.6. Zsh doesn't like the comments in the middle of the multi-line pipeline, so you may have to omit them. Other operating systems will have different versions of /usr/share/dict/words that may not have all of these obscure words.)

We can accomplish this with only the simplest features of regular expressions: the dot metacharacter (.), character classes ([JUD...]) and negated character classes ([^E]), and the ^ and $ anchors. Awk gives us regex conjunctions, allowing us to match all of the chars.

The above regular expressions are a simple mechanical transformation of the guess–score pairs. They could be simplified. For example, after grep '^..E..$', the E in awk '/C/ && /E/' is redundant. We're not going to optimize the regexes, however.

Three of the four answers—ICENI, ILEAC, and OLEIC—are far too obscure to be Wordle answers. Actual Wordle answers also exclude simple plurals (YARDS) and simple past tense (LIKED), but allow more complex plurals (BOXES) and irregular past tense (DWELT, BROKE). We make no attempt to judge if an eligible word is likely as a Wordle answer; merely that it fits.

Let's make a pipeline for Wordle 787 (INDEX):

# VOUCH=..... GRIPE=..i.e DENIM=deni. WIDEN=.iDEn

grep '^.....$' /usr/share/dict/words |
    tr 'a-z' 'A-Z' |
    grep '^..DE.$' |                    # CORRECT pos
    awk '/D/ && /E/ && /I/ && /N/' |    # VALID set
    grep -v '[VOUCHGRPMW]' |            # INVALID set
    grep '^[^D][^EI][^IN][^I][^EN]$'    # PRESENT pos

yields:

INDEX

This approach is promising, but constructing those regexes by hand is not maintainable.

Word Lists

There are several sources of five-letter words.

Filtering /usr/share/dict/words or similar lists.
wordle.txt: The nearly 15,000 words that Wordle accepts as entries. Many of these words are obscure.
answers.txt: The 2,309 words that Wordle uses as answers. These words are fairly recognizable. They are a subset of the other list.

The latter two lists were extracted from the source code of the game. In the various examples below, I use the larger 15,000-word list.

Initial Python Solution

Let's attempt to solve this in Python. The first piece is to parse a list of GUESS=SCORE pairs.

def parse_guesses(guess_scores):
    invalid = set()                         # Black/Absent
    valid = set()                           # Green/Correct or Yellow/Present
    mask = [None] * 5                       # Exact match for pos (Green/Correct)
    wrong_spot = [set() for _ in range(5)]  # Wrong spot (Yellow/Present)
    for gs in guess_scores:
        guess, score = gs.split("=")
        for i, (g, s) in enumerate(zip(guess, score)):
            assert "A" <= g <= "Z", "GUESS should be uppercase"
            if "A" <= s <= "Z":
                assert g == s
                valid.add(g)
                mask[i] = g
            elif "a" <= s <= "z":
                assert g == s.upper()
                valid.add(g)
                wrong_spot[i].add(g)
            elif s == ".":
                invalid.add(g)
            else:
                raise ValueError(f"Unexpected {s} for {g}")
    return (invalid, valid, mask, wrong_spot)

Let's try it for the OCEAN guesses:

>>> invalid, valid, mask, wrong_spot = parse_guesses(
...     ["JUDGE=....e", "CHEST=c.E..", "WRECK=..Ec."])

>>> print(f"{invalid=}\n{valid=}\n{mask=}\n{wrong_spot=}")
invalid={'H', 'K', 'D', 'G', 'T', 'R', 'U', 'W', 'J', 'S'}
valid={'E', 'C'}
mask=[None, None, 'E', None, None]
wrong_spot=[{'C'}, set(), set(), {'C'}, {'E'}]

>>> for w in vocab:
...     if is_eligible(w, invalid, valid, mask, wrong_spot):
...         print(w)
...
ICENI
ILEAC
OCEAN
OLEIC

Here's the is_eligible function. We short-circuit the evaluation and return as soon as any condition is False.

def is_eligible(word, invalid, valid, mask, wrong_spot):
    letters = {c for c in word}
    if letters & valid != valid:
        # Missing some 'valid' letters from the word;
        # all Green/Correct and Yellow/Present letters are required
        logging.debug("!Valid: %s", word)
        return False
    elif any(m is not None and c != m for c, m in zip(word, mask)):
        # Some of the Green/Correct letters are not at their positions
        logging.debug("!Mask: %s", word)
        return False
    elif letters & invalid:
        # Some invalid (Black/Absent) letters are in the word
        logging.debug("Invalid: %s", word)
        return False
    elif any(c in ws for c, ws in zip(word, wrong_spot)):
        # We have valid letters in the wrong position (Yellow/Present)
        logging.debug("WrongSpot: %s", word)
        return False
    else:
        logging.debug("Got: %s", word)
        return True

Converting to Classes

Returning four parallel collections from a function is a code smell. Let's refactor these functions into a WordleGuesses class.

First, we'll need some helper classes:

WordleError: an exception class;
TileState: a multi-attribute enumeration;
GuessScore: a dataclass that manages a guess–score pair and the associated TileStates.
We'll also use type annotations because it's 2023.

WORDLE_LEN = 5

class WordleError(Exception):
   """Base exception class"""

class TileState(namedtuple("TileState", "value emoji color css_color"), Enum):
    CORRECT = 1, "\U0001F7E9", "Green",  "#6aaa64"
    PRESENT = 2, "\U0001F7E8", "Yellow", "#c9b458"
    ABSENT  = 3, "\U00002B1B", "Black",  "#838184"

@dataclass
class GuessScore:
    guess: str
    score: str
    tiles: list[TileState]

    @classmethod
    def make(cls, guess_score: str) -> "GuessScore":
        guess, score = guess_score.split("=")
        tiles = [cls.tile_state(s) for s in score]
        return cls(guess, score, tiles)

    @classmethod
    def tile_state(cls, score_tile: str) -> TileState:
        if "A" <= score_tile <= "Z":
            return TileState.CORRECT
        elif "a" <= score_tile <= "z":
            return TileState.PRESENT
        elif score_tile == ".":
            return TileState.ABSENT
        else:
            raise WordleError(f"Invalid score: {score_tile}")

    def __repr__(self):
        return f"{self.guess}={self.score}"

    def emojis(self, separator=""):
        return separator.join(t.emoji for t in self.tiles)

For brevity, I presented a minimal version of GuessScore.make above. The version in my Wordle repository has robust validation.

Let's add the main class, WordleGuesses:

@dataclass
class WordleGuesses:
    mask: list[str | None]      # Exact match for position (Green/Correct)
    valid: set[str]             # Green/Correct or Yellow/Present
    invalid: set[str]           # Black/Absent
    wrong_spot: list[set[str]]  # Wrong spot (Yellow/Present)
    guess_scores: list[GuessScore]

    @classmethod
    def parse(cls, guess_scores: list[GuessScore]) -> "WordleGuesses":
        mask: list[str | None] = [None] * WORDLE_LEN
        valid: set[str] = set()
        invalid: set[str] = set()
        wrong_spot: list[set[str]] = [set() for _ in range(WORDLE_LEN)]

        for gs in guess_scores:
            for i, (t, g) in enumerate(zip(gs.tiles, gs.guess)):
                if t is TileState.CORRECT:
                    mask[i] = g
                    valid.add(g)
                elif t is TileState.PRESENT:
                    wrong_spot[i].add(g)
                    valid.add(g)
                elif t is TileState.ABSENT:
                    invalid.add(g)

        return cls(mask, valid, invalid, wrong_spot, guess_scores)

WordleGuesses.parse is a bit shorter and clearer than parse_guesses. It uses TileState at each position to classify the current tile and accumulate state in the four member collections. Since GuessScore.make has validated the input, parse doesn't need to do any further validation.

The is_eligible method is essentially the same as its predecessor:

class WordleGuesses:
    def is_eligible(self, word: str) -> bool:
        letters = {c for c in word}
        if letters & self.valid != self.valid:
            # Did not have the full set of green+yellow letters known to be valid
            logging.debug("!Valid: %s", word)
            return False
        elif any(m is not None and c != m for c, m in zip(word, self.mask)):
            # Couldn't find all the green/correct letters
            logging.debug("!Mask: %s", word)
            return False
        elif letters & self.invalid:
            # Invalid (black) letters are in the word
            logging.debug("Invalid: %s", word)
            return False
        elif any(c in ws for c, ws in zip(word, self.wrong_spot)):
            # Found some yellow letters: valid letters in wrong position
            logging.debug("WrongSpot: %s", word)
            return False
        else:
            # Potentially valid
            logging.info("Got: %s", word)
            return True

    def find_eligible(self, vocabulary: list[str]) -> list[str]:
        return [w for w in vocabulary if self.is_eligible(w)]

There's a famous story where Donald Knuth was asked by Jon Bentley to demonstrate literate programming by finding the K most common words from a text file. Knuth turned in an eight-page gem of WEB, which was reviewed by Doug McIlroy, who demonstrated that the task could also be accomplished in a six-line pipeline.

Wordle can also be solved with a six-line pipeline, but the regexes are quite difficult to type correctly and they have to be carefully hand tailored for each set of guess–score pairs. There is no one general six-line pipeline.

I know that I'd much rather work with these Python classes. As we'll see below, they are a solid foundation that can be built upon in many ways.

Does it Work?

Let's try it!:

# answer: ARBOR
$ ./wordle.py HARES=.ar.. GUILT=..... CROAK=.Roa. BRAVO=bRa.o
ARBOR

# answer: CACHE
$ ./wordle.py CHAIR=Cha.. CLASH=C.a.h CATCH=CA.ch
CACHE
CAHOW

# answer: TOXIC
$ ./wordle.py LEAKS=..... MIGHT=.i..t BLITZ=..it. OPTIC=o.tIC TONIC=TO.IC
TORIC
TOXIC

This looks right but there are some subtle bugs in the code.

Fifty is the new Witty

Here we expect to find FIFTY, but no words match:

# answer: FIFTY
$ ./wordle.py HARES=..... BUILT=..i.t TIMID=tI... PINTO=.I.T. WITTY=.I.TY
--None--

Let's take a look at the state of the WordleGuesses instance:

>>> guess_scores = [GuessScore.make(gs) for gs in
        "HARES=..... BUILT=..i.t TIMID=tI... PINTO=.I.T. WITTY=.I.TY".split()]

>>> wg = WordleGuesses.parse(guess_scores)
>>> wg
WordleGuesses(mask=[None, 'I', None, 'T', 'Y'], valid={'T', 'I', 'Y'}, invalid={
'A', 'E', 'D', 'M', 'U', 'H', 'I', 'B', 'L', 'T', 'P', 'O', 'R', 'W', 'N', 'S'},
wrong_spot=[{'T'}, set(), {'I'}, set(), {'T'}], guess_scores=[GuessScore(guess='HARES',
score='.....', tiles=[<TileState.ABSENT: TileState(value=3, emoji='⬛', color='Black',
css_color='#838184')>, <TileState.ABSENT: TileState(value=3, emoji='⬛', color='Black',
css_color='#838184')>,
    ... much snipped ...

That's ugly.

Better String Representation

Let's write a few helper functions to improve the __repr__:

def letter_set(s: set[str]) -> str:
    return "".join(sorted(s))

def letter_sets(ls: list[set[str]]) -> str:
    return "[" + ",".join(letter_set(e) or "-" for e in ls) + "]"

def dash_mask(mask: list[str | None]):
    return "".join(m or "-" for m in mask)

class WordleGuesses:
    def __repr__(self) -> str:
        mask = dash_mask(self.mask)
        valid = letter_set(self.valid)
        invalid = letter_set(self.invalid)
        wrong_spot = letter_sets(self.wrong_spot)
        unused = letter_set(
            set(string.ascii_uppercase) - self.valid - self.invalid)
        _guess_scores = [", ".join(f"{gs}|{gs.emojis()}"
            for gs in self.guess_scores)]
        return (
            f"WordleGuesses({mask=}, {valid=}, {invalid=},\n"
            f"    {wrong_spot=}, {unused=})"
        )

Let's run it again, printing out the instance:

# answer: FIFTY
$ ./wordle.py -v HARES=..... BUILT=..i.t TIMID=tI... PINTO=.I.T. WITTY=.I.TY
WordleGuesses(mask='-I-TY', valid='ITY', invalid='ABDEHILMNOPRSTUW',
    wrong_spot='[T,-,I,-,T]', unused='CFGJKQVXZ')
    guess_scores= ['HARES=.....|⬛⬛⬛⬛⬛, BUILT=..i.t|⬛⬛🟨⬛🟨,
        TIMID=tI...|🟨🟩⬛⬛⬛, PINTO=.I.T.|⬛🟩⬛🟩⬛, WITTY=.I.TY|⬛🟩⬛🟩🟩']
--None--

That's a huge improvement in legibility over the default string representation!

There's a T in both valid and invalid—two sets that should be mutually exclusive. The first “absent” T at position 3 in WITTY has poisoned the second T at position 4, which is “correct”. The T at position 1 in TIMID and the T at position 5 in BUILT are “present” because they are the only T in those guesses.

When there are two Ts in a guess, but only one T in the answer, one of the Ts will either be “correct” or “present”. The second, superfluous T will be “absent”.

First Attempt at Fixing the Bug

Let's modify WordleGuesses.parse slightly to address that. When we get an ABSENT tile, we should add that letter to invalid only if it's not already in valid.

class WordleGuesses:
    @classmethod
    def parse(cls, guess_scores: list[GuessScore]) -> "WordleGuesses":
        mask: list[str | None] = [None] * WORDLE_LEN
        valid: set[str] = set()
        invalid: set[str] = set()
        wrong_spot: list[set[str]] = [set() for _ in range(WORDLE_LEN)]

        for gs in guess_scores:
            for i, (t, g) in enumerate(zip(gs.tiles, gs.guess)):
                if t is TileState.CORRECT:
                    mask[i] = g
                    valid.add(g)
                elif t is TileState.PRESENT:
                    wrong_spot[i].add(g)
                    valid.add(g)
                elif t is TileState.ABSENT:
                    if g not in valid:  # <<< new
                        invalid.add(g)

        return cls(mask, valid, invalid, wrong_spot, guess_scores)

Does it work? Yes! Now we have FIFTY.

# answer: FIFTY
$ ./wordle.py -v HARES=..... BUILT=..i.t TIMID=tI... PINTO=.I.T. WITTY=.I.TY
WordleGuesses(mask='-I-TY', valid='ITY', invalid='ABDEHLMNOPRSUW',
    wrong_spot='[T,-,I,-,T]', unused='CFGJKQVXZ')
FIFTY
JITTY
KITTY
ZITTY

But we also have JITTY, KITTY, and ZITTY, which should not been considered eligible since WITTY was eliminated for the T at position 3. We'll come back to this soon.

The Problem of Repeated Letters

There's a problem that we haven't grappled with properly yet: repeated letters in a guess or in an answer. We've made an implicit assumption that there are five distinct letters in each guess and in the answer.

Here's an example that fails with the original parse:

# answer: EMPTY
$ ./wordle.py -v LODGE=....e WIPER=..Pe. TEPEE=teP.. EXPAT=E.P.t
WordleGuesses(mask='E-P--', valid='EPT', invalid='ADEGILORWX',
    wrong_spot='[T,E,-,E,ET]', unused='BCFHJKMNQSUVYZ')
--None--

but works with the current parse:

# answer: EMPTY
$ ./wordle.py -v LODGE=....e WIPER=..Pe. TEPEE=teP.. EXPAT=E.P.t
WordleGuesses(mask='E-P--', valid='EPT', invalid='ADGILORWX',
    wrong_spot='[T,E,-,E,ET]', unused='BCFHJKMNQSUVYZ')
EMPTS
EMPTY

Note that there is no longer an E in invalid. In TEPEE=teP.., the E in position 2 is considered “present”, while the two Es in positions 4 and 5 are marked “absent”. This tells us that there is only one E in the answer. Since P is correct in position 3 of TEPEE, the E must be in position 1. This is confirmed by the subsequent EXPAT=E.P.t, where the initial E is marked “correct”.

Our previous understanding of “absent” was too simple. An “absent” tile can mean one of two things:

This letter is not in the answer at all—the usual case.
If another copy of this letter is “correct” or “present” elsewhere in the same guess (i.e., valid), the letter is superfluous at this position. The guess has more instances of this letter than the answer does.

Consider the results here:

# answer: STYLE
$ ./wordle.py -v GROAN=..... WHILE=...LE BELLE=...LE TUPLE=t..LE STELE=ST.LE
WordleGuesses(mask='ST-LE', valid='ELST', invalid='ABGHINOPRUW',
    wrong_spot='[T,-,-,-,-]', unused='CDFJKMQVXYZ')
STELE
STYLE

STELE was an incorrect guess, so it should not have been offered as an eligible word. E is valid in position 5, but wrong in position 3.

Another example:

# answer: WRITE
$ ./wordle.py -v SABER=...er REFIT=re.it TRITE=.RITE
WordleGuesses(mask='-RITE', valid='EIRT', invalid='ABFS',
    wrong_spot='[R,E,-,EI,RT]', unused='CDGHJKLMNOPQUVWXYZ')
TRITE
URITE
WRITE

TRITE was an incorrect guess, so it should not have been offered. 4:T is valid, 1:T is wrong.

Fixing Repeated Absent Letters

We can fix this by making two passes through the tiles for each guess–score pair.

Handle “correct” and “present” tiles as before.
Add “absent” tiles to either invalid or wrong_spot.

We need the second pass to handle a case like WITTY=.I.TY, where the “absent” 3:T precedes the “correct” 4:T: the valid set must be fully updated before we process “absent” tiles.

class WordleGuesses:
    @classmethod
    def parse(cls, guess_scores: list[GuessScore]) -> "WordleGuesses":
        mask: list[str | None] = [None for _ in range(WORDLE_LEN)]
        valid: set[str] = set()
        invalid: set[str] = set()
        wrong_spot: list[set[str]] = [set() for _ in range(WORDLE_LEN)]

        for gs in guess_scores:
            # First pass for correct and present
            for i, (t, g) in enumerate(zip(gs.tiles, gs.guess)):
                if t is TileState.CORRECT:
                    mask[i] = g
                    valid.add(g)
                elif t is TileState.PRESENT:
                    wrong_spot[i].add(g)
                    valid.add(g)

            # Second pass for absent letters
            for i, (t, g) in enumerate(zip(gs.tiles, gs.guess)):
                if t is TileState.ABSENT:
                    if g in valid:
                        # There are more instances of `g` in `gs.guess`
                        # than in the answer
                        wrong_spot[i].add(g)
                    else:
                        invalid.add(g)

        return cls(mask, valid, invalid, wrong_spot, guess_scores)

We can see that valid and invalid are disjoint. The is_eligible method needs no changes.

Let's try the WRITE example again:

# answer: WRITE
$ ./wordle.py -v SABER=...er REFIT=re.it TRITE=.RITE
WordleGuesses(mask='-RITE', valid='EIRT', invalid='ABFS',
    wrong_spot='[RT,E,-,EI,RT]', unused='CDGHJKLMNOPQUVWXYZ')
URITE
WRITE

There is now a T in the first wrong_spot entry.

And STYLE?

# answer: STYLE
$ ./wordle.py -v GROAN=..... WHILE=...LE BELLE=...LE TUPLE=t..LE STELE=ST.LE
WordleGuesses(mask='ST-LE', valid='ELST', invalid='ABGHINOPRUW',
    wrong_spot='[T,E,EL,-,-]', unused='CDFJKMQVXYZ')
STYLE

Both the second and third wrong_spots now have an E. The “absent” 3:L from BELLE is also in the third wrong_spot.

What about some other examples?

In our previous attempt at fixing the bug, neither QUICK nor SPICK were found because the first C in CHICK was “absent” and thus marked invalid. Now, the valid and invalid sets are disjoint, there's a C in the first element of wrong_spot, and both words are found:

# answer: QUICK
$ ./wordle.py -v MORAL=..... TWINE=..I.. CHICK=..ICK
WordleGuesses(mask='--ICK', valid='CIK', invalid='AEHLMNORTW',
    wrong_spot='[C,-,-,-,-]', unused='BDFGJPQSUVXYZ')
QUICK
SPICK

As expected, we find only one answer for FIFTY now:

# answer: FIFTY
$ ./wordle.py -v HARES=..... BUILT=..i.t TIMID=tI... PINTO=.I.T. WITTY=.I.TY
WordleGuesses(mask='-I-TY', valid='ITY', invalid='ABDEHLMNOPRSUW',
    wrong_spot='[T,-,IT,I,T]', unused='CFGJKQVXZ')
FIFTY

The new T in the third element of wrong_spot blocks the rhymes for WITTY.

Further Optimization of the Mask

There's still room for improvement. If you guess ANGLE=ANGle, it's immediately obvious (to a human player) that you should swap the L and E to guess ANGEL on your next turn. Or swap the P and T in SPRAT=SpRAt to guess STRAP.

Similarly, TENET=TEN.t tells you that the fourth letter of the answer must be T, while CHORE=C.OrE must have 2:R.

A more complex example:

# answer: BURLY
$ ./wordle.py -v LOWER=l...r FRAIL=.r..l BLURT=Blur.
WordleGuesses(mask='B----', valid='BLRU', invalid='AEFIOTW',
    wrong_spot='[L,LR,U,R,LR]', unused='CDGHJKMNPQSVXYZ')

The R is in the wrong spot in positions 5 (l...r), 2 (.r..l), and 4 (Blur.). The B is correct in position 1, so R must be in position 3.

The L is in the wrong spot in positions 1, 5, and 2. B is in position 1, R is now in 3, so that leaves only position 4 for L.

There remain two possibilities for U—positions 2 and 5; the information contained in mask and wrong_spot is not enough to determine where U should go.

The original mask, B----, was due to having only one “correct” letter. Using the cumulative information in the guesses and scores, we can infer a mask of B-RL-.

In all of these cases, we can find exactly one remaining position where a “present” letter can be placed. In the BURLY example, it takes two passes: we couldn't uniquely determine a place for L until we had already placed R.

Up to now, we've been treating each tile in almost complete isolation. Let's optimize the mask programmatically.

To account for repeated letters, such as the two Ts in TENET=TEN.t, we use Python's collections.Counter as a multiset. Counter's union operation, |=, computes the maximum of corresponding counts.

First, we loop through all the guess–score pairs, building a valid multiset of the “correct” and “present” letters. Then we subtract a multiset of the “correct” letters, yielding a multiset of the “present” letters.

Second, we loop over present, trying for each letter to find a single empty position where it can be placed in the mask. If there is such a position, we update mask2, remove the letter from present, and break out of the inner loop. If there isn't (as in the two possibilities for U in BURLY), then we use the little-known break-else construct to exit from the outer loop.

Finally, we merge mask2 into self.mask. This optimize method is called from the end of WordleGuesses.parse.

class WordleGuesses:
    def optimize(self) -> list[str | None]:
        """Use PRESENT tiles to improve `mask`."""
        mask1: list[str | None] = self.mask
        mask2: list[str | None] = [None] * WORDLE_LEN
        # Compute `valid`, a multiset of the correct and present letters in all guesses
        valid: Counter[str] = Counter()
        for gs in self.guess_scores:
            valid |= Counter(
                g for g, t in zip(gs.guess, gs.tiles) if t is not TileState.ABSENT
            )
        correct = Counter(c for c in mask1 if c is not None)
        # Compute `present`, a multiset of the valid letters
        # whose correct position is not yet known; i.e., PRESENT in any row.
        present = valid - correct
        logging.debug(f"{valid=} {correct=} {present=}")

        def available(c, i):
            "Can `c` be placed in slot `i` of `mask2`?"
            return mask1[i] is None and mask2[i] is None and c not in self.wrong_spot[i]

        while present:
            for c in present:
                positions = [i for i in range(WORDLE_LEN) if available(c, i)]
                # Is there only one position where `c` can be placed?
                if len(positions) == 1:
                    i = positions[0]
                    mask2[i] = c
                    present -= Counter(c)
                    logging.debug(f"{i+1} -> {c}")
                    break
            else:
                # We reach this for-else only if there was no `break` in the for-loop;
                # i.e., no one-element `positions` was found in `present`.
                # We must abandon the outer loop, even though `present` is not empty.
                break

        logging.debug(f"{present=} {mask2=}")

        self.mask = [m1 or m2 for m1, m2 in zip(mask1, mask2)]
        logging.info(
            f"\toptimize: {dash_mask(mask1)} | {dash_mask(mask2)}"
            f" => {dash_mask(self.mask)}"
        )
        return mask2

Here are some examples of it in action. Going from ---ET to -ESET:

# answer: BESET
$ ./wordle.py -vv CIVET=...ET EGRET=e..ET SLEET=s.eET
WordleGuesses(mask=---ET, valid=EST, invalid=CGILRV,
    wrong_spot=[ES,-,E,-,-], unused=ABDFHJKMNOPQUWXYZ)
valid=Counter({'E': 2, 'T': 1, 'S': 1}) correct=Counter({'E': 1, 'T': 1})
    present=Counter({'E': 1, 'S': 1})
2 -> E
3 -> S
present=Counter() mask2=[None, 'E', 'S', None, None]
    optimize: ---ET | -ES-- => -ESET

And from C---- to CLER-:

# answer: CLERK
$ ./wordle.py -vv SINCE=...ce CEDAR=Ce..r CRUEL=Cr.el
WordleGuesses(mask=C----, valid=CELR, invalid=ADINSU,
    wrong_spot=[-,ER,-,CE,ELR], unused=BFGHJKMOPQTVWXYZ)
valid=Counter({'C': 1, 'E': 1, 'R': 1, 'L': 1}) correct=Counter({'C': 1})
    present=Counter({'E': 1, 'R': 1, 'L': 1})
3 -> E
4 -> R
2 -> L
present=Counter() mask2=[None, 'L', 'E', 'R', None]
    optimize: C---- | -LER- => CLER-

Demanding an Explanation

Would you like to know why a guess is ineligible? We can do that too.

# answer: ROUSE
$ ./wordle.py THIEF=...e. BLADE=....E GROVE=.ro.E \
    --words ROMEO PROSE STORE MURAL ROUSE --explain

WordleGuesses(mask=----E, valid=EOR, invalid=ABDFGHILTV,
    wrong_spot=[-,R,O,E,-], unused=CJKMNPQSUWXYZ)
    guess_scores: ['THIEF=...e.|⬛⬛⬛🟨⬛, BLADE=....E|⬛⬛⬛⬛🟩,
                    GROVE=.ro.E|⬛🟨🟨⬛🟩']
ROMEO   Mask: needs ----E; WrongSpot: has ---E-
PROSE   WrongSpot: has -RO--
STORE   Invalid: has -T---; WrongSpot: has --O--
MURAL   Valid: missing EO; Mask: needs ----E; Invalid: has ---AL
ROUSE   Eligible

# answer: BIRCH
$ ./wordle.py CLAIM=c..i. TRICE=.riC. \
    --words INCUR TAXIS PRICY ERICA BIRCH --explain

WordleGuesses(mask=---C-, valid=CIR, invalid=AELMT,
    wrong_spot=[C,R,I,I,-], unused=BDFGHJKNOPQSUVWXYZ)
    guess_scores: ['CLAIM=c..i.|🟨⬛⬛🟨⬛, TRICE=.riC.|⬛🟨🟨🟩⬛']
INCUR   Mask: needs ---C-
TAXIS   Valid: missing CR; Mask: needs ---C-; Invalid: has TA---; WrongSpot: has ---I-
PRICY   WrongSpot: has -RI--
ERICA   Invalid: has E---A; WrongSpot: has -RI--
BIRCH   Eligible

Here's how those explanations were computed, using a variation on is_eligible:

class WordleGuesses:
    def is_ineligible(self, word: str) -> dict[str, str]:
        reasons = {}
        letters = {c for c in word}
        if missing := self.valid - (letters & self.valid):
            # Did not have the full set of green+yellow letters known to be valid
            reasons["Valid"] = f"missing {letter_set(missing)}"

        mask = [(m if c != m else None) for c, m in zip(word, self.mask)]
        if any(mask):
            # Couldn't find all the green/correct letters
            reasons["Mask"] = f"needs {dash_mask(mask)}"

        invalid = [(c if c in self.invalid else None) for c in word]
        if any(invalid):
            # Invalid (black) letters present at specific positions
            reasons["Invalid"] = f"has {dash_mask(invalid)}"

        wrong = [(c if c in ws else None) for c, ws in zip(word, self.wrong_spot)]
        if any(wrong):
            # Found some yellow letters: valid letters in wrong position
            reasons["WrongSpot"] = f"has {dash_mask(wrong)}"

        return reasons

    def find_explanations_(
        self, vocabulary: list[str]
    ) -> list[tuple[str, str | None]]:
        explanations = []
        for word in vocabulary:
            reasons = self.is_ineligible(word)
            why = None
            if reasons:
                why = "; ".join(
                    f"{k}: {v}" for k, v in self.is_ineligible(word).items())
            explanations.append((word, why))
        return explanations

This approach is slower than is_eligible, though it's not noticeable when running wordle.py for one set of guess–scores. I have a test tool (score.py) that runs through the 200+ games that I've recorded. Using find_explanations, it took about 10 seconds to run. Switching to find_eligible, it dropped to 2 seconds (5x improvement). By prefiltering the word list with a regex made from the mask, the time drops to half a second (further 4x improvement).

pattern = re.compile("".join(m or "." for m in parsed_guesses.mask))
word_list = [w for w in vocabulary if pattern.fullmatch(w)]
eligible = parsed_guesses.find_eligible(word_list)

Finally

I thought I knew a lot about solving Wordle programmatically when I started this long post a month ago. As I wrote this, I realized that I could use a few ugly greps to accomplish the same thing as my Python code; wrote a tool to render games as HTML and emojis; spun off a couple of blog posts on multi-attribute enumeration and regex conjunctions; found and fixed several bugs with repeated letters, greatly refining my understanding of the nuances; rewrote the sections on repeated letters repeatedly; added a means to explain ineligibility; and had a minor epiphany about optimizing the mask programmatically.

The full code can be found in my Wordle repository.

Other Work

I found these articles after I completed the final draft of this post.

Bertsimas and Paskov used Exact Dynamic Programming to find An Exact and Interpretable Solution to Wordle.
Yann Landry's Solver is a little JavaScript and HTML tool that tries to pick the best next word using a scoring system.
Solving with Basic Python makes suggestions for each round based on word commonality.
Some Tips and Tricks for playing the game.

Regex Conjunctions

Tue, 05 Sep 2023 07:00:00 GMT

Most regular expression engines make it easy to match alternations (or disjunctions) with the | operator: to match either foo or bar, use foo|bar.

Few regex engines have any provisions for conjunctions, and the syntax is often horrible. Awk makes it easy to match /pat1/ && /pat2/ && /pat3/.

$ cat <<EOF | awk '/bar/ && /foo/'
> foo bar
> bar
> barfy food
> barfly
> EOF
foo bar
barfy food

In the case of a Unix pipeline, the conjunction could also be expressed as a series of pipes: ... | grep pat1 | grep pat2 | grep pat3 | ....

The longest regex that I ever encountered was an enormous alternation—a true horror that shouldn't have been a regex at all.

Python Enums with Attributes

Sat, 02 Sep 2023 07:00:00 GMT

Python enumerations are useful for grouping related constants in a namespace. You can add additional behaviors to an enum class, but there isn't an easy and obvious way to add attributes to enum members.

class TileState(Enum):
    CORRECT = 1
    PRESENT = 2
    ABSENT  = 3

    def color(self):
        if self is self.CORRECT:
            return "Green"
        elif self is self.PRESENT:
            return "Yellow"
        elif self is self.ABSENT:
            return "Black"

    def emoji(self):
        return {
            self.CORRECT: "\U0001F7E9",
            self.PRESENT: "\U0001F7E8",
            self.ABSENT:  "\U00002B1B",
        }[self]

Accessing the members and the methods:

>>> for ts in TileState:
...     print(f"{ts.name:<7}: {ts.value} {ts.color():<6} {ts.emoji()}")
...
CORRECT: 1 Green  🟩
PRESENT: 2 Yellow 🟨
ABSENT : 3 Black  ⬛

You can add methods like color() and emoji() above—you can even decorate them with @property so that you don't need parentheses—but you have to remember to update every method when you add or remove members from the enumeration.

Namedtuples to the rescue

It turns out that you can build a mixin enumeration from namedtuple and Enum that gives terse construction syntax:

class TileState(namedtuple("TileState", "value emoji color css_color"), Enum):
    CORRECT = 1, "\U0001F7E9", "Green",  "#6aaa64"
    PRESENT = 2, "\U0001F7E8", "Yellow", "#c9b458"
    ABSENT  = 3, "\U00002B1B", "Black",  "#838184"

Each member now has multiple read-only attributes, like emoji and css_color:

>>> for ts in TileState:
...     print(f"{ts.name:<7}: {ts.value} {ts.emoji} U+{ord(ts.emoji):05x} "
...           f"{ts.color:<6} {ts.css_color}")
...
CORRECT: 1 🟩 U+1f7e9 Green  #6aaa64
PRESENT: 2 🟨 U+1f7e8 Yellow #c9b458
ABSENT : 3 ⬛ U+02b1b Black  #838184

Patching a Python Wheel

Thu, 10 Aug 2023 07:00:00 GMT

Recently, I had to create a new Python wheel for PyTorch. There is a cyclic dependency between PyTorch 2.0.1 and Triton 2.0.0: Torch depends upon Triton, but Triton also depends on Torch. Pip is okay with installing packages where there's a cyclic dependency. Bazel, however, does not handle cyclic dependencies between packages. We use Bazel extensively at Stripe and this cyclic dependency prevented us from using the latest version of Torch.

I spent a few days trying to build the PyTorch wheel from source. It was a nightmare! I ran out of disk space on the root partition on my EC2 devbox trying to install system packages, so I had to bring up a custom instance. Then I ran out of space on the main partition, trying to compile, so I had to bring up another custom instance. Then I realized I had installed CUDA 12.1 and couldn't install CUDA 11.8 over it, so yet another instance. Then a long list of other problems. I was eventually able to get python setup.py develop to execute, but it took three hours! And I had little confidence that I was building the same thing that was in the official wheels.

Then I had a brainwave: what if I patch the official Torch wheel and simply remove the requirement on Triton? All the officially built code would remain untouched. That worked!

This post is adapted from my writeup on the issue.

What is a Wheel?

A Python wheel is a ready-to-install Python package that requires no compilation at installation time. Unlike older formats such as source distributions or eggs, setup.py is not run during installation from a wheel. The older formats conflated build and install and required arbitrary code to run.

A wheel is a Zip archive with a specially formatted filename and a .whl extension. The wheel contains a dist-info metadata directory and the installable payload. A wheel is either pure Python, which can install on any platform, or a platform (binary) wheel, which usually contains compiled Python extension code.

Java JARs, Android APKs, Mozilla XPIs, and many other file types are also structured Zip archives.

Manual Patching

The wheel file's contents include the {distribution}-{version}.dist-info/ directory, which contains metadata about the wheel.

In the case of PyTorch 2.0.1, I had torch-2.0.1-cp38-cp38-manylinux1_x86_64.whl, a Linux x86_64 wheel for Python 3.8.

I used unzip to extract the wheel's contents into a directory, torch201.2. (The .2 denoted my second attempt.) In the torch201.2 directory was the entire content of the wheel, including the torch-2.0.1.dist-info/ subdirectory.

unzip -d torch201.2 torch-2.0.1-cp38-cp38-manylinux1_x86_64.whl
cd torch201.2

# Rename the `dist-info` directory to include '+stripe.2' as a suffix for `2.0.1`
mv torch-2.0.1{,+stripe.2}.dist-info/
cd torch-2.0.1+stripe.2.dist-info/

Normally, when we build wheels for forked version of Python packages at Stripe, we append +stripe.{major}.{commits}.{revision} to the version number. Both commits and revision come from the output of git describe --tags HEAD, which looks like {tag}-{commits}-g{revision}; major is currently hardcoded to 1. This suffix helps distinguish a forked wheel's version from the upstream version number.

Since I wasn't forking, I used a simplified scheme, +stripe.{attempt}.

Then I updated some fields in torch-2.0.1+stripe.2.dist-info/METADATA:

Updated Version to include +stripe.2
Removed the Requires-Dist line for triton. This is the crucial step to fix the cyclic dependency problem.

Now I had to update torch-2.0.1+stripe.2.dist-info/RECORD, which contains signatures for all the files in the wheel, in the form {filename},sha256={safe_hash},{filesize}. Of course, RECORD does not have an entry for itself.

The paths to all the dist-info files needed to be updated in RECORD to include the +stripe.2 suffix.

In Vim terms:

:%s/^\(torch-2.0.1\)\(\.dist-info\)/\1+stripe.2\2/

You can use this record_hash.py script to compute the entry for a file:

#!/usr/bin/env python3

import base64
import hashlib
import os
import sys

filename = sys.argv[1]

with open(filename, "rb") as f:
    digest = hashlib.sha256(f.read())
    safe_hash = base64.urlsafe_b64encode(digest.digest()).decode("us-ascii").rstrip("=")
print(f"{filename},sha256={safe_hash},{os.path.getsize(filename)}")

The output will look like this:

$ ../record_hash.py torch-2.0.1+stripe.2.dist-info/METADATA
torch-2.0.1+stripe.2.dist-info/METADATA,sha256=StmZkVzCWlHIxaIGVJocXv7JsDnlrSaNXwtuIlE_PKc,24703

Replace the METADATA entry in RECORD with the output from record_hash.py.

Finally, you can zip up everything into a new wheel. Note the +stripe.2 in the new wheel's filename:

zip ../torch-2.0.1+stripe.2-cp38-cp38-manylinux1_x86_64.whl -r .

At this point, you can upload the wheel to a private repository.

To install the wheel:

pip install torch==2.0.1+stripe.2

You will not see triton being installed, unlike before. However, if you do install triton, it will be satisfied by this patched version of torch.

Summary

If you have to manually patch a Python wheel:

Decide upon a suffix, such as +stripe.2.
Unzip the wheel.
Rename the dist-info directory to include the suffix.
Update Version in METADATA to include the suffix.
Make other modifications.
Append the suffix to the dist-info entries in RECORD.
Use record_hash.py to compute new entries for all modified files. Update RECORD accordingly.
Zip up the new wheel. Include the suffix in the filename.
pip install the new wheel.

Bram Moolenaar RIP

Mon, 07 Aug 2023 07:00:00 GMT

I woke up on Saturday to read on Bram Moolenaar's Facebook page an announcement of his death. I knew Bram online for nearly 30 years and I was one of his relatively small number of Facebook friends, but we never met in real life. I knew that he had retired from Google Zurich to Tenerife, but I hadn't been aware that he had been ill.

Bram was known to the world for his signature creation, the Vim text editor, used by millions of developers on Linux, macOS, and Windows. Vim stands for Vi IMproved, but it outgrew the original vi long ago.

I was an active contributor to Vim in the 1990s: I wrote a lot of the Win32 console mode code as well as the alpha version of Windows gVim; my name is at the top of the page if you do :help win32. In the 00s, I ported Vim to Win64. I drifted away from active participation more than a decade ago, but I still lurk on the vim_dev mailing list.

Vim has been the thoroughly dominant flavor of vi for a number of years, but that wasn’t the case in the 90s. There were Elvis, vile, xvi, and other things I no longer recall. Bram built a better vi and he built a solid community of developers and users. I never saw the toxic behavior that’s prevalent in some tech communities. Bram was always a patient and reasonable leader. He poured countless hours into making Vim an ever better editor and he answered so many questions on the various mailing lists. Vim would not have succeeded half so well without the community that he built. I didn’t always agree with Bram's technical decisions (and neither did the NeoVim people), but I have enormous respect for what he accomplished, technically and socially.

The other remarkable thing about Vim is that it’s charityware. Vim users were strongly encouraged to donate to ICCF Holland, which supports children in Kibaale, Uganda. Bram was the treasurer of ICCF and was involved with the work for many years. When I was at Microsoft, I got a bunch of Vim-loving engineers to donate; Microsoft matched our donations. I made another donation to ICCF today in his memory.

It’s clear that work on Vim will continue. Although Bram was the benevolent dictator for life of Vim, a handful of others have commit rights and are planning future of the Vim project. They have big shoes to fill. I don’t know enough about ICCF to say how severely this will affect them.

ETA: The upcoming Vim 9.1 release will be dedicated to Bram, just as the 9.0 release was dedicated to Sven Guckes, who died last year. Sven was one of Vim's greatest ambassadors, endlessly helpful to users in the newsgroups. We stayed for a week with Sven in August 2014 in his Berlin apartment, and he was the most wonderful host, spending many hours showing us around his beloved city.

The best articles that I’ve seen about Bram so far:

The Reg's obituary
The Legacy of Bram Moolenaar, Jan van den Berg
Vim Boss, Justin M. Keyes

:wq!

Cold Brew Coffee Recipe

Mon, 24 Jul 2023 07:00:00 GMT

I often enjoy cold brew coffee in summer. I bought an Oxo Cold Brew Coffee Maker one winter when it was on sale at Bed, Bath & Beyond. Before that, I used a nut milk bag in a jar. I like the Oxo and it gets high marks in many reviews, such as HomeGrounds or Wirecutter. It's easy to use, easy to clean, and makes a good brew.

The only downside to making your own cold brew coffee is that you must plan ahead. You can make hot coffee in a few minutes, but cold brew takes hours.

I have used this recipe for a number of years. It makes a smooth, less acidic coffee.

Ingredients

24 fl oz water
6 oz fresh coarsely ground coffee. Store-bought pre-ground coffee is too fine.

This will half-fill the Oxo jar. It yields about 16 fl oz (1 pt) of cold brew coffee. You can double the quantities in the Oxo, if you like.

Instructions

Grind the coffee beans coarsely.
Place the ground coffee in the Oxo jar.
Pour water through the rain sprinkler top.
Swirl gently to ensure that all coffee grounds are wet. (I once followed a recipe that called for vigorous stirring. Never again! The grounds absorbed so much more water that I only got half the yield.)
Some people put the jar in the fridge at this point. I don't bother.
Wait for the coffee to brew! Some instructions say 12 to 24 hours. I usually wait 6–8 hours.
Put the jar on the stand. First, make sure that the switch is closed.
Place the flask under the stand. Push the switch down to release the brew.
Let the cold brew coffee drain. This will take 10–15 minutes.
Refrigerate the cold brew.
Use the coffee grounds to turn hydrangeas blue or exfoliate your skin.

Adjustments

You can vary the ratio of coffee to water and how long you steep the mixture.

Drinks

2 fl oz of cold brew
6 fl oz milk

Fork in the Kitchen has some suggestions if you don't have a coffee grinder or an Oxo maker.

Compressing Tar Files in Parallel

Tue, 21 Feb 2023 07:00:00 GMT

TL;DR: use tar -I pigz or tar -I lbzip2 to compress large tar files much more quickly.

I investigated various ways of compressing a 7GiB tar file.

The built-in --gzip and --bzip2 compression methods in GNU tar are single-threaded. If you invoke an external compressor with --use-compress-program, you can get some huge reductions in compression time, with slightly worse compression ratios.

You can use pigz as a parallel replacement for gzip and lbzip2 as a parallel version of bzip2. Both of them will make heavy use of all the cores in your system, greatly reducing the real time relative to the user time.

Single-threaded compression timing: gzip is a lot faster than bzip2:

$ time tar --bzip2 -cf huge-bzip2.tar.bz2 hugedir

real    13m15.352s
user    12m53.972s
sys     0m16.029s

$ time tar --gzip -cf huge-gzip.tar.gz hugedir

real    5m56.489s
user    5m30.271s
sys     0m14.633s

fast parallel compression timing: pigz is the clear winner:

$ time tar --use-compress-program='lbzip2 --fast' \
    -cf huge-lbzip2-fast.tar.bz2 hugedir

real    2m35.967s
user    11m38.865s
sys     0m26.981s

$ time tar --use-compress-program='pigz --fast' \
    -cf huge-pigz-fast.tar.gz hugedir

real    0m58.222s
user    3m22.134s
sys     0m17.357s

best parallel compression timing: lbzip2 is much quicker than pigz:

$ time tar --use-compress-program='lbzip2 --best' \
    -cf huge-lbzip2-best.tar.bz2 hugedir

real    1m44.365s
user    11m38.277s
sys     0m13.551s

$ time tar --use-compress-program='pigz --best' \
    -cf huge-pigz-best.tar.gz hugedir

real    2m27.694s
user    16m20.441s
sys     0m16.092s

Compressed file sizes: bzip2 family compresses better than gzip family; best is smaller than default compression level which is smaller than fast:

$ ls -lSr
-rw-r--r-- 1 user group 2460438578 Feb 22 03:03 huge-lbzip2-best.tar.bz2
-rw-r--r-- 1 user group 2461172874 Feb 22 03:19 huge-bzip2.tar.bz2
-rw-r--r-- 1 user group 2689784220 Feb 22 03:00 huge-lbzip2-fast.tar.bz2
-rw-r--r-- 1 user group 2691286852 Feb 22 03:06 huge-pigz-best.tar.gz
-rw-r--r-- 1 user group 2704591997 Feb 22 03:25 huge-gzip.tar.gz
-rw-r--r-- 1 user group 2950547862 Feb 22 03:01 huge-pigz-fast.tar.gz
-rw-r--r-- 1 user group 7365222400 Feb 22 03:00 huge.tar

Implementing the Tree command in Rust, part 2: Printing Trees

Tue, 24 Jan 2023 07:00:00 GMT

In Part 1, we saw how to walk directory trees, recursively using fs::read_dir to construct an in-memory tree of FileNodes. In Part 2, we'll implement the rest of the core of the tree command: printing the directory tree with Box Drawing characters.

Let's take a look at some output from tree:

.
├── alloc.rs
├── ascii.rs
├── os
│   ├── wasi
│   │   ├── ffi.rs
│   │   ├── mod.rs          ➊
│   │   └── net             ➋
│   │       └── mod.rs
│   └── windows
│       ├── ffi.rs          ➌
│       ├── fs.rs
│       ├── io
│       │   └── tests.rs
│       ├── mod.rs
│       └── thread.rs
├── personality
│   ├── dwarf
│   │   ├── eh.rs
│   │   ├── mod.rs
│   │   └── tests.rs
│   ├── emcc.rs
│   └── gcc.rs
└── personality.rs

The first thing that we notice is that most entries at any level, such as ➊, are preceded by ├──, while the last entry, ➋, is preceded by └──. This article about building a directory tree generator in Python calls them the tee and elbow connectors, and I'm going to use that terminology.

The second thing we notice is that there are multiple prefixes before the connectors, either │ (pipe) or (space), one prefix for each level. The rule is that children of a last entry, such as os/windows ➌, get the space prefix, while children of other entries, such as os/wasi or personality, get the pipe prefix.

For both connectors and prefixes, the last entry at a particular level gets special treatment.

The `print_tree` function

A classic technique with recursion is to create a pair of functions: an outer public function that calls a private helper function with the initial set of parameters to visit recursively.

Our print_tree function uses an inner visit function to recursively do almost all of the work.

pub fn print_tree(root: &str, dir: &Directory) {
    const OTHER_CHILD: &str = "│   ";   // prefix: pipe
    const OTHER_ENTRY: &str = "├── ";   // connector: tee
    const FINAL_CHILD: &str = "    ";   // prefix: no more siblings
    const FINAL_ENTRY: &str = "└── ";   // connector: elbow

    println!("{}", root);                                           ➊
    let (d, f) = visit(dir, "");
    println!("\n{} directories, {} files", d, f);

    fn visit(node: &Directory, prefix: &str) -> (usize, usize) {    ➋
        let mut dirs: usize = 1; // counting this directory         ➌
        let mut files: usize = 0;
        let mut count = node.entries.len();                         ➍
        for entry in &node.entries {
            count -= 1;
            let connector =
                if count == 0 { FINAL_ENTRY } else { OTHER_ENTRY }; ➎
            match entry {
                FileTree::DirNode(sub_dir) => {                     ➏
                    println!("{}{}{}", prefix, connector, sub_dir.name);
                    let new_prefix = format!(                       ➐
                        "{}{}",
                        prefix,
                        if count == 0 { FINAL_CHILD } else { OTHER_CHILD }
                    );
                    let (d, f) = visit(&sub_dir, &new_prefix);      ➑
                    dirs += d;
                    files += f;
                }
                FileTree::LinkNode(symlink) => {
                    println!(
                        "{}{}{} -> {}", prefix, connector,
                        symlink.name, symlink.target);
                    files += 1;
                }
                FileTree::FileNode(file) => {
                    println!("{}{}{}", prefix, connector, file.name);
                    files += 1;
                }
            }
        }
        (dirs, files)                                               ➒
    }
}

The outer function, print_tree, simply prints the name of the root node on a line by itself; calls the inner visit function with the dir node and an empty prefix; and finally prints the number of directories and files visited. This is for compatibility with the output of tree.
The inner visit function takes two parameters: node, a Directory, and prefix, a string which is initially empty.
Keep track of the number of dirs and files seen at this level and in sub-directories.
We count downwards from the number of entries in this directory to zero. When count is zero, we are on the last entry, which gets special treatment.
Compute the connector, └── (elbow) for the last entry; ├── (tee) otherwise.
Match the FileTree::DirNode variant and destructure the value into sub_dir, a &Directory.
Before recursively visiting a sub-directory, we compute a new prefix, by appending the appropriate sub-prefix to the current prefix. If there are further entries (count > 0), the sub-prefix for the current level is │ (pipe); otherwise, it's (spaces).
Call visit recursively, then add to the running totals of dirs and files.
visit returns a tuple of the counts of directories and files that were recursively visited.

One subtlety that is not obvious from the above is that OTHER_CHILD actually contains two non-breaking spaces:

const OTHER_CHILD: &str = "│\u{00A0}\u{00A0} "; // prefix: pipe

This is for compatibility with the output of tree:

$ diff <(cargo run -q -- ./tests) <(tree ./tests) && echo "no difference"
no difference

Using process substitution to generate two different inputs for diff.

The `main` function

Let's tie it all together.

fn main() -> io::Result<()> {
    let root = env::args().nth(1).unwrap_or(".".to_string());   ➊
    let dir: Directory = dir_walk(                              ➋
        &PathBuf::from(root.clone()),                           ➌
        is_not_hidden,
        sort_by_name)?;                                         ➍
    print_tree(&root, &dir);                                    ➎
    Ok(())                                                      ➏
}

The simplest possible way to get a single, optional command-line argument. If omitted, we default to ., the current directory. For more sophisticated argument parsing, we could use Clap.
Use dir_walk from Part 1 to recursively build a directory of FileTree nodes.
Create a PathBuf from root, a string; clone is needed because PathBuf::from takes ownership of the string buffer. Use the is_not_hidden filter and the sort_by_name comparator from Part 1.
The postfix question mark operator, ?, is used to propagate errors.
Let print_tree draw the diagram.
Return the Ok unit result to indicate success.

Baum

You can find the Baum source code on GitHub.

In Part 3, we'll discuss testing.

Resources

Official tree source: The actual source for tree, written in old-school C.
Draw a Tree Structure With Only CSS: Use CSS to draw links in nested, unordered lists.
Build a Python Directory Tree Generator for the Command Line.
Kevin Newton has implemented Tree in Multiple Languages.
Tre is a modern alternative to tree in Rust.

Implementing the Tree command in Rust, part 1: Walking Directories

Mon, 23 Jan 2023 07:00:00 GMT

I've been learning Rust lately. I started by reading several books, including Rust in Action, Code Like a Pro in Rust, and most of Programming Rust. Now, I'm starting to actually write code.

I read the Command-Line Rust book last month, which challenged readers to write our own implementations of the tree command.

I decided to accept the challenge.

At its simplest, tree simply prints a directory tree, using some of the Unicode Box Drawing characters to show the hierarchical relationship, as in the image at right.

I've split the code into two phases, which will be covered in two blog posts.

Walking the directory tree on disk to build an in-memory tree.
Pretty-printing the in-memory tree.

While it's certainly possible to print a subtree as it's being read, separating the two phases yields code that is cleaner, simpler, and more testable.

In future, I will insert a third phase, processing, between the reading and writing phases, by a weak analogy with Extract-Transform-Load (ETL).

Walking the Directory Tree

There are three kinds of file tree node that I care about: File, Directory, and Symlink. These are the variants exposed by Rust's FileType.

File has a name and file system metadata;
Symlink has a name, a target, and metadata;
Directory has a name and a list of child file tree nodes.

Here, name refers to the last component of a path; e.g., the gamma in alpha/beta/gamma. The file system metadata is not currently used, but will be in future.

#[derive(Debug)]
pub struct File {
    pub name: String,
    pub metadata: fs::Metadata,
}

#[derive(Debug)]
pub struct Symlink {
    pub name: String,
    pub target: String,
    pub metadata: fs::Metadata,
}

#[derive(Debug)]
pub struct Directory {
    pub name: String,
    pub entries: Vec<FileTree>,
}

File and directory paths are not guaranteed to be UTF-8. Indeed, Unix file paths are an arbitrary sequence of bytes, while Windows file paths are an opaque sequence of 16-bit integers. You might think that I should be using OsString here, since it holds a platform-native string. String has to be valid UTF-8; OsString doesn't. Unfortunately, it's not easy to look at the actual data in an OsString, unless you convert it (possibly lossily) to a String. See File paths and OS strings for more.

The obvious way to represent a file tree node in Rust is as an enum with three tuple-like variants.

#[derive(Debug)]
pub enum FileTree {
    DirNode(Directory),
    FileNode(File),
    LinkNode(Symlink),
}

Here, each variant in the enum holds a struct of similar name. We will be able to take advantage of Rust's pattern matching to handle each variant.

We'll use fs::read_dir to read each directory in the hierarchy. The read_dir function returns an iterator that yields instances of io::Result<DirEntry>. If a DirEntry is a directory, we can recursively invoke our dir_walk function to read the child directory and add its contents to our in-memory tree.

The walkdir crate also walks through a directory tree, but it hides the recursion from you. It's an excellent choice otherwise.

Skipping and Sorting

In each directory that we read, we need to consider two factors.

Which entries to skip, such as hidden files.
How to sort the entries.

We almost always want to skip hidden files and directories—on Unix, those entries whose names start with the . character. Every directory includes entries for . (itself) and .. (parent directory), and may include other hidden files or directories, such as .vimrc or .git.

On Windows, hidden files are controlled by an attribute, not by their name.

For more complicated usage, we might want to skip ignored files, as specified in .gitignore.

The simplest useful filter for entry names is one that rejects hidden files and directories.

pub fn is_not_hidden(name: &str) -> bool {
    return !name.starts_with('.');
}

Disk I/O is costly and slow, compared to memory access. It's far more efficient to not read a directory at all than it is to eliminate a subtree at a later stage. Even if the OS has cached the relevant directory contents, there's still a cost to the syscall to retrieve that data from the kernel.

There is no specific order to entries in a directory or to the results returned by low-level APIs like fs::read_dir. By default, ls sorts entries alphabetically, but it can also sort by creation time, modification time, or size, in ascending or descending order.

Unix filesystems are case-sensitive, but Mac filesystems (APFS and HFS+) are case-insensitive by default, although they preserve the case of the original filename. Windows' filesystems (NTFS, exFAT, and FAT32) are likewise case-preserving and case-insensitive.

Here is a case-sensitive comparator for use with sort_by:

pub fn sort_by_name(a: &fs::DirEntry, b: &fs::DirEntry) -> Ordering {
    let a_name: String =
        a.path().file_name().unwrap().to_str().unwrap().into();     ➊
    let b_name: String =
        b.path().file_name().unwrap().to_str().unwrap().into();
    a_name.cmp(&b_name)                                             ➋
}

This messy expression is necessary to get the name as a String.
cmp returns Less, Equal, or Greater from the Ordering enum.

The `dir_walk` function

Finally, the recursive dir_walk function that creates the tree of FileTree nodes.

pub fn dir_walk(
    root: &PathBuf,
    filter: fn(name: &str) -> bool,                 ➊
    compare: fn(a: &fs::DirEntry, b: &fs::DirEntry) -> Ordering,
) -> io::Result<Directory> {
    let mut entries: Vec<fs::DirEntry> = fs::read_dir(root)?
        .filter_map(|result| result.ok())
        .collect();                                 ➋
    entries.sort_by(compare);
    let mut directory: Vec<FileTree> =
        Vec::with_capacity(entries.len());          ➌
    for e in entries {
        let path = e.path();
        let name: String = path.file_name().unwrap().to_str().unwrap().into();
        if !filter(&name) {                         ➍
            continue;
        };
        let metadata = fs::metadata(&path).unwrap();
        let node = match path {                     ➎
            path if path.is_dir() => {
                FileTree::DirNode(                  ➏
                    dir_walk(&root.join(name), filter, compare)?)
            }
            path if path.is_symlink() => FileTree::LinkNode(Symlink {
                name: name.into(),
                target: fs::read_link(path).unwrap().to_string_lossy().to_string(),
                metadata: metadata,
            }),
            path if path.is_file() => FileTree::FileNode(File {
                name: name.into(),
                metadata: metadata,
            }),
            _ => unreachable!(),
        };
        directory.push(node);
    }
    let name = root
        .file_name()
        .unwrap_or(OsStr::new("."))                 ➐
        .to_str()
        .unwrap()
        .into();
    Ok(Directory {                                  ➑
        name: name,
        entries: directory,
    })
}

Currently, the filter and compare parameters are fns. They could probably be FnMut traits.
Read directory. Discard any Error results. Collect into a Vec.
We'll need at most this many entries.
Use filter to discard names that won't be visited.
Match the path as a DirNode, LinkNode, or FileNode, by using match guards.
Visit the subdirectory recursively.
If root was ".", the file_name() will be None.
Return a Directory for this directory, wrapped in an io::Result.

In Part 2, we'll print the directory tree.

fsymbols for Unicode weirdness

Sun, 01 Jan 2023 03:35:00 GMT

My display name on Twitter currently looks like @ɢᴇᴏʀɢᴇᴠʀᴇɪʟʟʏ@ᴛᴇᴄʜ.ʟɢʙᴛ, an attempt to route around Twitter's apparent censorship of Mastodon information.

I used the FSymbols Generators to produce several variants.

@𝕘𝕖𝕠𝕣𝕘𝕖𝕧𝕣𝕖𝕚𝕝𝕝𝕪@𝕥𝕖𝕔𝕙.𝕝𝕘𝕓𝕥
ʇqƃʅ.ɥɔǝʇ@ʎʅʅᴉǝɹʌǝƃɹoǝƃ@
@𝗀𝖾𝗈𝗋𝗀𝖾𝗏𝗋𝖾𝗂𝗅𝗅𝗒@𝗍𝖾𝖼𝗁.𝗅𝗀𝖻𝗍
@𝘨𝘦𝘰𝘳𝘨𝘦𝘷𝘳𝘦𝘪𝘭𝘭𝘺@𝘵𝘦𝘤𝘩.𝘭𝘨𝘣𝘵
@𝑔𝑒𝑜𝑟𝑔𝑒𝑣𝑟𝑒𝑖𝑙𝑙𝑦@𝑡𝑒𝑐ℎ.𝑙𝑔𝑏𝑡
@𝙜𝙚𝙤𝙧𝙜𝙚𝙫𝙧𝙚𝙞𝙡𝙡𝙮@𝙩𝙚𝙘𝙝.𝙡𝙜𝙗𝙩
@𝚐𝚎𝚘𝚛𝚐𝚎𝚟𝚛𝚎𝚒𝚕𝚕𝚢@𝚝𝚎𝚌𝚑.𝚕𝚐𝚋𝚝
@𝔤𝔢𝔬𝔯𝔤𝔢𝔳𝔯𝔢𝔦𝔩𝔩𝔶@𝔱𝔢𝔠𝔥.𝔩𝔤𝔟𝔱

Many of these variants come from Unicode Block "Mathematical Alphanumeric Symbols".

There are a lot more things you can do with Unicode than just upside-down text.

Backwards Ranges in Python

Mon, 19 Dec 2022 22:20:00 GMT

In Python, if you want to specify a sequence of numbers from a up to (but excluding) b, you can write range(a, b). This generates the sequence a, a+1, a+2, ..., b-1. You start at a and keep going until the next number would be b.

In Python 3, range is lazy and the values in the sequence do not materialize until you consume the range.

>>> range(3,12)
range(3, 12)
>>> list(range(3,12))
[3, 4, 5, 6, 7, 8, 9, 10, 11]

Trey Hunner makes the point that range is a lazy iterable rather than an iterator.

You can also step by an increment other than one: range(a, b, s). This generates a, a+s, a+2*s, ..., b-s (assuming that (b - a) % s == 0; i.e., a and b are separated by an exact multiple of s.)

>>> list(range(3, 12, 3))
[3, 6, 9]

What if you want to count down? range(b, a, -s) won't do what you want.

>>> list(range(12,3, -3))
[12, 9, 6]

Why? Because you're starting at b, a value that doesn't appear in the forward range, and you're ending before you reach a, a value that is certainly in the forward range. You have to subtract s from both b and a:

When you use range(b-s, a-s, -s), you get b-s, b-2*s, ..., a+s, a.

>>> list(range(12-3,3-3, -3))
[9, 6, 3]
>>> list(range(12-3,3-3, -3)), list(reversed(range(3, 12, 3)))
([9, 6, 3], [9, 6, 3])

Ulysses at 100

Wed, 02 Feb 2022 07:00:00 GMT

On 2nd February 1882, in the Dublin suburb of Rathgar, a son was given unto John and May Joyce. James Joyce celebrated his 40th birthday in Paris on 2nd February 1922 by receiving the first printed copy of his novel Ulysses. Parts of it had already been published in literary magazines and the book was eagerly received by the cognoscenti. It took more than a decade for Ulysses to be published in Britain and the United States. Censors had considered the book obscene, but the courts established that it had legitimate literary merit.

For decades, Ulysses was poorly received in Ireland. The book was considered blasphemous and obscene by many. Worse, Joyce had freely borrowed from life, populating the pages of Ulysses with people he had known in Dublin.

By the time of the centenary of Joyce's birth in 1982, attitudes had changed in Ireland. Ulysses was now celebrated, if not widely read. RTÉ Radio broadcast a 25-hour reading of the entire book.

I was a schoolboy of almost seventeen in Dublin in February 1982. I did not, alas, listen to the RTÉ recording at the time, but at some point that year, I started reading Ulysses for myself. And like so many would-be readers before and since, I hit Episode 3, "Proteus", which opens with "Ineluctable modality of the visible" and promptly dives into Stephen Dedalus's impenetrable thoughts. If I could give some advice to myself 40 years ago, it would be to "skip over the hard bits". I'm in good company on that recommendation. Daniel Mulhall, Ireland's Ambassador to the US and author of the recent Ulysses: A Reader's Odyssey, gives the same advice. Episode 4, "Calypso", introduces us to Leopold Bloom and is far more enjoyable.

Unfortunately, I did not have the benefit of that advice then, and I had little to do with Ulysses for the next two decades. In 2003, I took part in the Wild Geese Players of Seattle's staged reading of Episodes 8 and 9, "Lestrygonians" and "Scylla and Charybdis". In 2004, I helped adapt the next episode, "Wandering Rocks", for that year's staged reading. When Kieran O'Malley, the group's original founder, moved back to Ireland in 2005 or 2006, I took over as dramaturg. I've led the Geese for many years now, and I've adapted scripts for the entire book.

Why? The connection with Dublin that I share with Joyce is certainly part of it. I've come to love the book. (Most of it; there are certainly parts that I find tedious.) It's a book in which very little happens, and yet it encompasses everything. We get an extremely rounded picture of Bloom and his inner life. It's funny and sad and erudite and annoying and wise. Joyce has distilled the human condition into one summer's day in Dublin.

And now it is the centenary of the publication of Ulysses. I posted some centenary material at the Wild Geese website.

Ulysses has become an ineluctable part of my life.

Diffing a fragment of a file

Mon, 31 Jan 2022 07:00:00 GMT

A while back, I had extracted some code out of a large file into a separate file and made some modifications. I wanted to check that the differences were minimal. Let's say that the extracted code had been between lines 123 and 456 of large_old_file.

diff -u <(sed -n '123,456p;457q' large_old_file) new_file

What's happening here?

sed -n '123,456p' is printing lines 123–456 of large_old_file.
The 457q tells sed to abandon the file at line 457. Otherwise, it will keep reading all the way to the end.
The <(sed ...) is an example of process substitution. The output of the sed invocation becomes the first input of the diff command.

A similar example: Diff a Transformed File.

BTW, these days, I usually use delta for diffing at the command line, especially with Git.

40 Years of Programming

Mon, 31 Jan 2022 07:00:00 GMT

40 years ago this month, I sat down at a computer and wrote a program. (Or "programme", as I spelled it then.) It was the first time I had ever used a computer. Very few people had used computers in 1982, in Ireland or elsewhere.

What was the program? No idea. Just a few lines of AppleSoft Basic. But it was enough to get me hooked and change my life.

I still get a hit when a little bit of code unlocks in my brain. It's quite addictive. There's always more to learn and to see.

I wrote more about this in 2012: 30 Years of Programming.

On Circumnavigating the Aubreyiad Again

Thu, 30 Dec 2021 07:00:00 GMT

At the beginning of 2021, prompted by Russell Crowe's defense of Master and Commander, I began yet another re-read of the twenty Aubrey-Maturin novels. Or, as the fandom would have it, another circumnavigation. It's probably my fifth or sixth circumnavigation, since I bought the complete boxed set as a Christmas present to myself in the early aughts.

I completed the twentieth book, Blue at the Mizzen, yesterday, and also the few pages of the final, unfinished novel, 21. (I also read about 120 other books in 2021, down from a stupendous 200 books in 2020, but that's neither here nor there.)

I think I'm due for another re-read of Patrick O'Brian's Aubrey/Maturin novels (all 6,500 pages) and a rewatch of Master and Commander. pic.twitter.com/gVf9IBan7e
— George V. Reilly (@georgevreilly) January 17, 2021

Why did I put myself through re-reading 6,500 pages of a dense roman-fleuve yet again? For the sheer pleasure of joining up once more with my old friends, Captain Jack Aubrey and Dr Stephen Maturin, in their 15-year fight against Napoleon.

They are an unlikely pair of friends. Jack Aubrey, a big, hearty English naval officer, is utterly competent in his domain, magnificent at sea but naïve and easily duped on land. Stephen Maturin, the illegitimate son of an Irish officer and a Catalan lady, is a renowned physician and naturalist, a former United Irishman turned British intelligence agent, a Catholic in a Protestant service, and a perpetual landlubber and sloven. They have little in common, save a shared love of music and of natural philosophy. Both are Fellows of the Royal Society—Jack, to many's surprise, is a mathematician and astronomer.

And yet, they are fast friends and Stephen follows Jack from ship to ship. A captain must hold himself aloof from his crew and his officers. He is the sole authority, often months of sailing away from his superiors. He dines alone, save when invited to the officers' wardroom or when he invites them to join him. Stephen, as Jack's particular friend, is exempt from the normal strictures, allowing Jack to retain his humanity on the long voyages.

It is the friendship and the two main characters that hold me, along with the adventure and the travel. O'Brian immersed himself in the eighteenth and early nineteenth centuries, and his encyclopaedic knowledge helped him bring the era to life with incredible verisimilitude. O'Brian was an accomplished storyteller and often very funny.

The characters sound and act like people of the time, not like transplanted twentieth century Americans. Jack, Stephen, and the other characters would be at home in the pages of Jane Austen (sister to two Royal Navy officers).

Jo Walton's re-read will give you a taste of the books.

Review: Crafting Interpreters

Tue, 28 Dec 2021 07:00:00 GMT

Title: Crafting Interpreters

Author: Robert Nystrom

Rating: ★ ★ ★ ★ ★

Publisher: Genever Benning

ISBN: 978-0990582939

Pages: 640

Keywords: programming, interpreters

Reading period: 10–28 December, 2021

I've read hundreds of technical books over the last 40 years. Crafting Interpreters is an instant classic, and far more readable and fun than many of the classics.

Nystrom covers a lot of ground in this book, building two very different interpreters for Lox, a small dynamic language of his own design. He takes us through every line of jlox, a Java-based tree-walk interpreter, and of clox, a bytecode virtual machine written in C.

For the first implementation, jlox, he covers such topics as scanning, parsing expressions with recursive descent, evaluating expressions, control flow, functions and closures, classes, and inheritance.

Starting with an empty slate, Nystrom adds just enough code to implement the topic of each chapter, having a working albeit incomplete implementation of the interpreter by the end of the chapter. He adds new code as he goes, inserting an extra case into a switch here or writing a new function there, or replacing a few lines of an earlier implementation with something that's just been explained. Knuth's Literate Programming explains a finished implementation, broken into separate pieces for exposition. Nystrom's continual, ever-evolving exposition is slower to get to the point, but it's excellent pedagogy. I would be remiss if I didn't mention the hundreds of hand-drawn illustrations, which add a quirky flavor to the tone of the book. He has a blog post on how he pulled this organization off and another on how he created a physical book from the text.

clox is a very different second implementation of a Lox interpreter. Instead of a slow interpreter walking an abstract syntax tree, he develops a stack-based virtual machine, compiles Lox into bytecode, and interprets the bytecode. He covers theory and practical considerations for creating a bytecode virtual machine, makes use of Pratt’s “top-down operator precedence parsing”, and implements closures and classes in C. In jlox, he used Java's HashMap to manage identifiers and relied on Java's garbage collection for memory management. For clox, he implements a hash table and a mark-and-sweep garbage collector. Although he has to cover similar topics (parsing, local variables, closures) each time, he finds a fresh perspective for the second implementation.

I read the entire book for free at https://craftinginterpreters.com/, but I liked it so much that I've ordered a physical copy. In fact, I actually read much of the book on the website in 2020, but life intervened and I didn't finish it, so this month, I read it again from the start.

This book is not a textbook and you don't get an exhaustive introduction to building interpreters, much less compilers. In the final year of my Computer Science degree at Trinity College Dublin in 1986–87, I studied the Dragon Book when the first edition was brand new. Crafting Interpreters is a lot more fun than the Dragon Book.

Highly recommended!

Path Traversal Attacks

Tue, 05 Oct 2021 07:00:00 GMT

I was surprised to read this evening that the Apache Web Server just fixed an actively exploited path traversal flaw.

🚨 Apache has disclosed an *actively exploited* Path traversal flaw in the #opensource "httpd" server. Over 112,000 exposed Apache servers run version 2.4.49, and should be upgraded now!
New fix checks for encoded path traversal characters e.g. /../.%2E/https://t.co/1tLNc3LAul pic.twitter.com/mDHLEU3k9N
— Ax Sharma (@Ax_Sharma) October 5, 2021

Apparently, it was introduced over a year ago.

I'm gobsmacked that Apache didn't have a robust suite of tests for this.

Directory Traversal attacks have been a problem for web servers since the beginning. OWASP, PortSwigger, and Spanning all have explanations that you can read. The essence is that you make a request to a URL that looks like http://example.com/cgi-bin/../../../../etc/passwd and, voilà, you get access to something that you shouldn't. Each of the .. path segments climbs up a level of the file system. Even the simplest web server knows better than to blindly allow a sequence of .. path segments, so you have to be a little clever about how you express them.

IIS Unicode Exploit

I remember when I worked on the IIS development team at Microsoft in 1997–2004, we got hit by CVE-2000-0884 in 2000, which made use of an overlong UTF-8 encoding.

URLs allow percent encoding for characters that can't be sent literally. For example, %3D encodes an = as the two-digit hexadecimal value of =’s ASCII code. UTF-8 characters beyond U+007F require two or more bytes of storage, each of which can be percent encoded; e.g., U+00C1 (Á) is encoded as the C3 81 byte pair in UTF-8, and as %C3%81 in percent encoding.

The slash character, / or U+002F, can be percent encoded as %2F. IIS 4 and 5 were smart enough to treat %2F as a slash and to defend against sequences like ..%2F..%2F. However, the attackers encoded a slash as %C0%AF—a sequence that is burned into my brain. This two-byte UTF-8 sequence can be decoded as U+002F, though it should not be treated as valid as it is overlong: the five payload bits in the leading byte are all zero.

The GIAC paper explains in some detail how this could be exploited.

Windows Security Push

Windows XP went on sale in late 2001, touted as the most secure version of Windows ever. (It was, at that time.)

Right around Christmas 2001, the UPnP vulnerabilty was disclosed. Brian Valentine, the Senior VP who ran Windows, threw a shitfit. It was announced that all of Windows would spend the month of February 2002 undergoing security training, so that we could threat model and review our code.

For IIS 6, which would be released in Windows Server 2003, we had fundamentally rearchitected it with a new worker process model (inspired by Apache's) and we had rewritten much of it. There was a new kernel mode driver, http.sys, that terminated all requests and routed them to the appropriate handler in kernel or user mode. I was part of the http.sys dev team at that point.

IIS had already gotten serious about security by then. We had to, after Code Red, Nimda, the Unicode exploit, and others. Mike Howard had been the IIS Security Program Manager before he went on to bigger responsiblities. A lot of the first edition of his Writing Secure Code book was based on his experience with securing IIS, and a lot of the second edition benefited from the Security Push experience.

Since http.sys was new and an obvious target, our team actually spent two months carefully reviewing everything. It turned out that we had done a good job over the previous couple of years and we didn't find much to worry about.

We did identify that the URL canonicalization in http.sys was overly complicated. I rewrote that component and I created a ton of unit tests for it. Developers writing unit tests was not common at Microsoft back in 2002: we had a separate caste of testers to write tests.

I've been out of the loop since I left IIS in 2004, but to my knowledge, there were no further vulnerabilities in URL handling.

I'm surprised and disappointed that Apache would mess up path traversal in the 2020s.

Accidentally Quadratic: Python List Membership

Mon, 04 Oct 2021 07:00:00 GMT

We had a performance regression in a test suite recently when the median test time jumped by two minutes.

We tracked it down to this (simplified) code fragment:

task_inclusions = [ some_collection_of_tasks() ]
invalid_tasks = [t.task_id() for t in airflow_tasks
                 if t.task_id() not in task_inclusions]

This looks fairly innocuous—and it was—until the size of the result returned from some_collection_of_tasks() jumped from a few hundred to a few thousand.

The in comparison operator conveniently works with all of Python's standard sequences and collections, but its efficiency varies. For a list and other sequences, in must search linearly through all the elements until it finds a matching element or the list is exhausted. In other words, x in some_list takes O(n) time. For a set or a dict, however, x in container takes, on average, only O(1) time. See Time Complexity for more.

The invalid_tasks list comprehension was explicitly looping through one list, airflow_tasks, and implicitly doing a linear search through task_inclusions for each value of t. The nested loop was hidden and its effect only became apparent when task_inclusions grew large.

The list comprehension was actually taking O(n²) time. When n was comparatively small (a few hundred), this wasn't a problem. When n grew to several thousand, it became a big problem.

This is a classic example of an accidentally quadratic algorithm. Indeed, Nelson describes a very similar problem with Mercurial changegroups.

This performance regression was compounded because this fragment of code was being called thousands of times—I believe once for each task— making the overall cost cubic, O(n³).

The fix here is similar: Use a set instead of a list and get O(1) membership testing. The invalid_tasks list comprehension now takes the expected O(n) time.

task_inclusions = set( some_collection_of_tasks() )
invalid_tasks = [t.task_id() for t in airflow_tasks
                 if t.task_id() not in task_inclusions]

More at Understanding Big-O Notation and the Big-O Cheat Sheet.

Passphrase Generators

Mon, 10 May 2021 07:00:00 GMT

I've been using password managers for at least 15 years to keep track of all my passwords. I have separate, distinct, strong passwords for hundreds of sites, and I've only memorized the handful that I need to actually type regularly.

I started out with the KeePass desktop app originally, but I switched to the online LastPass app about a decade ago. At work, we use 1Password.

When I register for a site, LastPass generates a random password for me, such as:

tV%5joS$U6^uY5xU
T2oEUY!g70Iv1b&I
8kNHg9*A5GMR9%8D

LastPass securely syncs my passwords between machines and devices. Its browser integration and its Android and iPhone apps mean that I rarely ever have to actually type any of those ugly messes in.

But when I do have to type in such a password, it's unpleasant in a browser. It doesn't help that LastPass in some cases displays passwords in a sans-serif font that makes it easy to misrecognize letters such as Il, 0O, 5S, or 8B. It's far more painful in an Android app, where you have to switch the keyboard in and out of symbol mode. It's usually even worse in iPhone apps, which rarely offer you an option to see your password in the clear as you're laboriously typing it, so it's easy to make a mistake. When I tried to use a remote control to enter my Netflix and Amazon Prime passwords into a new set-top box, I got so annoyed that I brought down a real keyboard and plugged it into the USB port.

Passphrases have nice properties compared to random passwords: they're human readable, they're much easier—if longer—to type, and you can actually remember them if you have to. A passphrase of at least five words (chosen by a secure random generator) is computationally infeasible to crack.

The ur-example of random passphrase generators is Diceware from 1995. There are various problems with the Diceware wordlist, which are rectified by more modern lists, such as the EFF Wordlists.

Which would you rather type? The line noise above or one of these passphrases?:

confident starfish aftermost elsewhere jasmine
shun baggage chaps reward cuddle
avenue rut pardon skating earlobe
latter blissful snippet jolt corroding
upstage-divinely-ninth-unfilled-skeleton
SkimmingMachinistBlessHesitancyKissableRink

When I want to generate a random passphrase, I tend to use either the Python diceware command-line tool or Glenn Rempe's JavaScript-based Diceware website. Both use cryptographic random number generators to generate excellent passphrases.

The 1Password Online Generator (in Memorable Password mode) also generates passphrases, as do the desktop and browser versions of 1Password.

My master password for LastPass is a passphrase, as is my laptop password. I'm also using Authy for 2FA, but that's a post for another time.

Tip

If you have to supply answers for one of those misbegotten security questions, such as your favorite movie or your first car, do not answer truthfully. Truthful answers increase your risk of identity theft. The answers are often guessable, can frequently be learned easily about you, and may be obtained through a password breach on another site.

Instead, generate a passphrase as the "answer" and store it and the question in the Notes field of your password manager. If you have to supply the answer to a security question over the phone to a customer service rep, you'll be thankful that you chose something that you can clearly say aloud.

Also Facebook quizzes and memes like "Your porn name is your middle name and the first car you had" are trying to obtain your answers to common security questions. Don't answer them.

Punctuating James Joyce

Sat, 08 May 2021 07:00:00 GMT

In The Punctuation Marks Loved (and Hated) by Famous Writers, Emily Temple relays a range of opinions from writers such as Tom Wolfe, Elmore Leonard, and Ursula K. Le Guin on periods, semicolons, hyphens and more.

On commas:

Listens to the sound of the sentence, and is always right, Bob: Toni Morrison

[On her editor, Bob Gottlieb, who famously “was always inserting commas into Morrison’s sentences and she was always taking them out”] We read the same way. We think the same way. He is overwhelmingly aggressive about commas and all sorts of things. He does not understand that commas are for pauses and breath. He thinks commas are for grammatical things. We have come to an understanding, but it is still a fight.

On periods:

Tolerates it, if he must: Cormac McCarthy

I believe in periods, in capitals, in the occasional comma, and that’s it.

James Joyce is a good model for punctuation. He keeps it to an absolute minimum. There’s no reason to blot the page up with weird little marks. I mean, if you write properly you shouldn’t have to punctuate.

My own prose tends towards longer sentences, often sprinkled with dashes, parentheses, and semicolons.

Since 2004, I've adapted all of James Joyce's Ulysses for staged readings by the Wild Geese Players of Seattle, and I'm in the Morrison camp, not the McCarthy–Joyce one.

Paragraphs like these work on the printed page. (More or less.)

The tear is bloody near your eye. Talking through his bloody hat. Fitter for him go home to the little sleepwalking bitch he married, Mooney, the bumbailiff's daughter, mother kept a kip in Hardwicke street, that used to be stravaging about the landings Bantam Lyons told me that was stopping there at two in the morning without a stitch on her, exposing her person, open to all comers, fair field and no favour.

—Anonymous narrator, Episode 12, “Cyclops”, L400

Martin Cunningham forgot to give us his spellingbee conundrum this morning. It is amusing to view the unpar one ar alleled embarra two ars is it? double ess ment of a harassed pedlar while gauging au the symmetry with a y of a peeled pear under a cemetery wall. Silly, isn't it? Cemetery put in of course on account of the symmetry.

—Mr Bloom, Episode 7, “Aeolus”, L170

But imagine trying to read those sentences aloud during a performance and bring the sense of the text to the audience.

As an aide to my performers, I've introduced “cadence bars” (denoted by ‘≀’) to the scripts to augment Joyce's sparse punctuation and to bring out the individual fragments.

The tear is bloody near your eye. Talking through his bloody hat. Fitter for him go home ≀ to the little sleepwalking bitch he married, Mooney, the bum·bailiff's daughter, mother kept a kip in Hardwicke street, that used to be stravaging about the landings ≀ Bantam Lyons told me ≀ that was stopping there at two in the morning ≀ without a stitch on her, exposing her person, open to all comers, fair field and no favour.

Martin Cunningham forgot to give us his spelling·bee conundrum this morning. It is amusing to view the ≀ unpar ≀ one ar ≀ alleled ≀ embarra ≀ two ars is it? ≀ double ess ≀ ment ≀ of a harassed pedlar ≀ while gauging ≀ au ≀ the symmetry ≀ with a y ≀ of a peeled pear ≀ under a cemetery wall. Silly, isn't it? Cemetery put in of course ≀ on account of the symmetry.

I've also added some pseudo-hyphens (bum·bailiff, spelling·bee, what·do·you·call·him) to counteract Joyce's Germanic habit of stringing several words into one.

This seems to help, though some of our readers have to fight a tendency to pause too much when they encounter a ‘≀’ symbol.

Now You Have 32 Problems

Thu, 23 Apr 2020 07:00:00 GMT

Some people, when confronted with a problem, think “I know, I'll use regular expressions.” Now they have two problems.

— Jaime Zawinksi

A Twitter thread about very long regexes reminded me of the longest regex that I ever ran afoul of, a particularly horrible multilevel mess that had worked acceptably on the 32-bit .NET CLR, but brought the 64-bit CLR to its knees.

Whenever I ran our ASP.NET web application [on Win64], it would go berserk, eat up all 4GB of my physical RAM, push the working set of IIS's w3wp.exe to 12GB, and max out one of my 4 cores! The only way to maintain any sanity was to run iisreset every 20 minutes to gently kill the process.

WinDbg and Process Explorer showed that the rogue thread was stuck in a loop in mscorjit!LifetimesListInteriorBlocksHelperIterative<GCInfoLiveRecordManipulator>. I passed a minidump on to my former colleagues in IIS, who sent it to the CLR team. They said:

The only thing I can tell is that it is Regex, and some regex expression compiled down to a method with 456KB of IL. That is huge, and yes 12GB of RAM consumed for something like that is expected.

With that clue, I was able to track down the problem, a particularly foul regex, built from a 10KB string, with 32 alternating expressions, each of which contains dozens of alternated subexpressions. The string is built from many smaller strings, so it's not obvious in the source just how ugly it is.

I never wrote a followup post explaining how I dealt with this beast.

The regex was used on the Cozi calendar to parse appointments in everyday language, such as “Ann/John Dinner out Friday at 8pm” or “John's birthday every Dec. 7”. These would get translated into (possibly recurring) iCalendar appointments.

Some of the subexpressions mentioned above looked like:

ordinals = "1st|2nd|...|31st"
short_days = "Sun|Mon|...|Sat"
full_days = "Sunday|Monday|...|Saturday"
short_months = "Jan|Feb|...|Dec"
full_months = "January|February|...|December"
recurrence = "((every|each)? (first|second|third|fourth|fifth|last)? " + "(" + short_days + "|" + full_days + ")" + ...

I've elided the intermediate values but they were spelled out in the original. Some of the simpler subexpressions were repeated several times, nested inside others.

This all screamed that a grammar and a real parser were needed, but the test suite also screamed here be dragons!

I resisted the temptation to rewrite the appointment parser from scratch with a proper grammar, or to experiment with a real natural language parser, though it remained on my personal todo list for the rest of my time at Cozi. We were migrating from C# to Python at that point, and the legacy appointment parser was one of the few remaining pieces that prevented us from shutting down the .NET servers.

Instead, I changed the appointment parser code so that it didn't attempt to match the entire 10KB monster in one go. I looped through each of the 32 top-level disjunctions, manually performing the alternation. If any one of those matched, then I had what I needed. Reducing the regexes to a few hundred characters each tamed the combinatorial explosion of backtracking state.

Regexes definitely have a place, but do not try to implement a full grammar as a single regular expression.

Weirdest Birthday Ever

Sun, 15 Mar 2020 07:00:00 GMT

When I said that Emma and I would be spending 2020 in Dublin, I could not possibly have anticipated what would be happening in Seattle while we were gone.

Today is my 55th birthday and it's the weirdest birthday ever, in what must be the weirdest week that most of us have lived through. (So far.)

COVID-19 is all that anyone can talk about: where it's spreading, how it's being handled, what comes next.

I started working from home on Tuesday, March 10th. Emma's general health and immune system are not good. My parents, who live nearby, are now both 80 years old and neither is in great health. It seemed prudent to minimize my risk of passing something on to any of them. Since then, Stripe has closed most offices, as have many other companies.

Ireland has closed schools, banned large gatherings, and is generally trying not to become like Italy. St Patrick's Day parades are cancelled. Most pubs have not yet closed and I wish they would, since they are now a public health risk.

If Ireland institutes a full lockdown, we'll move in with my parents for the duration—assuming that none of us are showing signs of COVID-19.

Seattle has been ground zero for coronavirus in the US. All of the initial deaths were there. Some hospitals are already overwhelmed, and I'm sure others will be as the number of cases rises exponentially. Governor Inslee and other state and city leaders have been doing a good job of managing the crisis.

I wish I could say the same about the United States as a whole. It was always obvious that Trump was wholly unfit to be president, but it's never been more clear over the past month. I fear for my adopted country.

Anyway, we're heading off to my parents soon, for a subdued birthday celebration.

Dublin for 2020

Fri, 22 Nov 2019 07:00:00 GMT

I left in the Eighties; I'm going back in the Twenties.

I am transferring to a Dublin-based team at Stripe for a one-year rotation. Emma and I will be moving to Dublin just before Christmas. Emma has never lived in Ireland and I haven't lived there since January 1989. After 30 years in the US, I'm about to spend a year in my hometown.

I grew up in Dublin, earned a Bachelor's degree in Computer Science at Trinity College Dublin in 1987, and moved to the US in 1989 to get a Master's degree in Comp Sci at Brown University in Providence, RI. Microsoft moved me to Seattle, WA in 1992, where I've lived ever since. Between 1992 and 2005, I worked at Microsoft three times for a total of ten years. I joined Stripe in Seattle in mid-2018, after eleven years at two startups, Cozi and Cookbrite/MetaBrite.

Emma and I met in 1997, and married and bought a house in 2000. We are now frantically trying to get that house into shape to rent out during our year's absence. We've been working all-out for several weeks and now there's only four weeks to go. She carried the burden by herself last week, as I spent the week in Dublin, meeting my new team. I had done so much painting of interior rooms before I went to Dublin two weeks ago, that the fingerprint readers on my laptop and phones were rejecting my fingerprint. My fingerprint works again, but there's still a little painting to be done.

We're excited and nervous. It's not easy to pick up and move after spending decades in one city. We have plenty of storage in our Seattle house and had little impetus—until now—to shed stuff. And there's lots and lots of stuff. Thousands upon thousands of books, the impedimenta of various hobbies, and twenty years of odds and ends. We've purged a lot but the end is not yet in sight. I'll be spending the second week of December in the San Jose and San Francisco, so I'll need to spend Thanksgiving working on the house.

Stripe has been great in providing relocation assistance to us, providing services in both Seattle and Dublin. I lined up an apartment in Dublin the day before I returned. We'll be living at the top of a Georgian house on Adelaide Road. It's not too small, but it'll feel cramped compared to our Seattle house.

A few weeks ago, I moved from an infrastructure team in the Stripe Seattle office to a new security team (Anti-Abuse) in the Stripe Dublin office. Not only is the team new, all of the team members are new to Stripe: most joined in August and the longest-tenured joined in March. They've already accomplished quite a bit, but they've left a few things for me to do.

My family are excited too. I have two siblings living in Ireland, but they're both over two hours' drive from my parents' home in Dublin. My sister's in rural Cork and one of my brothers is in rural Mayo. We're all going down to Cork for a few days at Christmas.

Ireland, here we come!

A Use for Octal: Calculating Modulo 36 from Modulo 9

Sun, 15 Sep 2019 07:00:00 GMT

(I posted an earlier version of this in December 2004 on my old technical blog. A discussion at work last week about 36-bit computers at the Living Computers Museum prompted me to write an updated post with improved explanations and much better typography.)

I've been programming in C since 1985 and C++ since 1991, but I've never found a use for octal representation until [2004], aside from the permissions argument for chmod. Octal has always seemed as vestigial as a human appendix, a leftover from the early days of computers, when word sizes were often a multiple of three: 6-, 12-, 24-, or 36-bits wide. All modern computers use word sizes that are powers of two—16-, 32-, or 64-bits wide—with 8-bit bytes, so octal is less useful than hex, which evenly subdivides bytes and words. I've done a lot of bit twiddling and hexadecimal has always been indispensable, while octal has remained a curiosity.

The other day [in 2004], a mathematician friend described to me a problem that he had solved at a previous company. They were designing hardware that emulated some old 36-bit computers. For backward compatibility, the various shift instructions had to accept an arbitrarily large shift count, k, and shift left or right by (k mod 36). Now, divisions are not cheap to implement in hardware, so they needed to come up with an alternate approach to calculate the modulus.

My friend tried to do something with the factors of 36: 4×9. Four and nine are relatively prime: they have no common factors other than one. By the Chinese Remainder Theorem therefore, the combination of k mod 4 and k mod 9 is enough to uniquely determine k mod 36. By inspection, this is true for the following table of “residues”. All the integers in the range [0, 36) appear exactly once.

4 \ 9	0	1	2	3	4	5	6	7	8
0	0	28	20	12	4	32	24	16	8
1	9	1	29	21	13	5	33	25	17
2	18	10	2	30	22	14	6	34	26
3	27	19	11	3	31	23	15	7	35

Calculating k mod 4 is easy in hardware: it's the two least-significant bits.

How to calculate k mod 9 in hardware is not so obvious.

Shifting and Masking

Several programming languages now provide a 0b prefix for binary literals to go along with the 0x prefix for hex literals and the 0o prefix for octal literals. (Older languages, such as C, use a 0 prefix for octal and have no 0b prefix.) See the discussion in Go number literals for more detail on 0b, including a list of languages that now support this notation.

2ⁿ, written in binary, looks like 1 followed by n 0s. For example, 2³ = 1000₂. In C-like languages, 2ⁿ can be written as 1 << n.

Similarly, 2ⁿ − 1, (1 << n) - 1, written in binary, looks like n 1s. For example, 2⁵ − 1 = 31₁₀ = 11111₂.

We can multiply an unsigned integer, u, by 2ⁿ by shifting u left by n bits, u << n, introducing n zeroes as the low-order bits. For example, using 8-bit numbers without loss of generality, written as modern Go/Rust number literals:

0b_0001_0101 << 3 == 0b_1010_1000

Similarly, we can divide u by 2ⁿ by shifting u right by n bits, u >>> n, which drops the n low-order bits and introduces n zeroes as the high-order bits.

0b_0101_0110 >>> 3 == 0b_0000_1010

A sign-extending or arithmetic right shift introduces n copies of the sign bit as the high-order bits. In some languages, such as Java and JavaScript, >> means an arithmetic right shift and >>> means a zero-extending right shift. In other languages, including C, C++, and Go, there is only a >> operator and sign-extension generally depends upon the type of the left operand, signed or unsigned. However, sign extension is not guaranteed in C/C++.

0b_0101_0110 >> 2 == 0b_0001_0101
0b_1001_0110 >> 2 == 0b_1110_0101

Finally, we can find the remainder of dividing u by 2ⁿ by masking u with 2ⁿ − 1, that is, bitwise-and with (1 << n) - 1, to extract the n low-order bits:

0b_0101_0110 & 0b_0000_0111 = 0b_0000_0110

In other words, u % 8 == u & 7 and u / 8 == u >> 3.

Read bitwise operations for more background.

Casting Out Nines

There's an old trick for checking the results of arithmetic operations, known as casting out nines or dropping nines.

Add up the decimal digits of each number. Apply the arithmetic operation to these digit sums. They should be congruent, modulo 9.

For example, 12, 345×8, 765 = 108, 203, 925.

To check the multiplication, compute the digit sum of each number, by adding up each decimal digit:

1 + 2 + 3 + 4 + 5 = 15 ≡ 6 ( mod 9)

Note: 12, 345 mod 9 = 6

and

8 + 7 + 6 + 5 = 26 ≡ 8 ( mod 9)

Note: 8, 765 mod 9 = 8

Take the first two digit sums, modulo 9, and multiply them:

6×8 = 48 ≡ 3 ( mod 9)

Note: 15×26 = 390 ≡ 3 ( mod 9)

Check against the sum of the digits of the product:

1 + 0 + 8 + 2 + 0 + 3 + 9 + 2 + 5 = 30 ≡ 3 ( mod 9)

Note: 108, 203, 925 mod 9 = 3

This works because 10ⁿ ≡ 1 ( mod 9).

Consider 758:

758 = 7×100 + 5×10 + 8

758 = 7×(9 + 1)×(9 + 1) + 5×(9 + 1) + 8

758 = 7×(9² + 2×9 + 1) + 5×(9 + 1) + 8

Dropping the nines from each term leaves the digit sum, which is congruent to the original number modulo nine:

7×1 + 5×1 + 8 = 7 + 5 + 8 = 20 ≡ 2 ( mod 9)

Checking: 758 mod 9 = 2.

Congruences have a number of useful properties.

Casting Out Elevens

Let's use 11, instead of 9. Since 10 = 11 − 1, then 10ⁿ ≡ − 1ⁿ (mod 11).

Consider 5234:

5234 = 5×10³ + 2×10² + 3×10¹ + 4×10⁰

5234 = 5×(11 − 1)×(11 − 1)×(11 − 1) + 2×(11 − 1)×(11 − 1) + 3×(11 − 1) + 4

5234 = 5×(11³ − 3×11²×1 + 3×11×1² − 1³) + 2×(11² − 2×11×1 + 1²) + 3×(11 − 1) + 4

Dropping the elevens from each term leaves the alternating digit sum:

5× − 1 + 2×1 + 3× − 1 + 4 = − 5 + 2 − 3 + 4 = − 2 ≡ 9 ( mod 11)

It's more convenient to proceed rightwards from the least significant digit, 4 − 3 + 2 − 5.

Checking: 5234 mod 11 = 9.

To cast out elevens, we calculate the alternating sum from right to left.

Casting out elevens catches some transposition errors, unlike casting out nines. For more, see divisibility rule for 11 and proof for alternating sum.

Modulo 9

At last, we turn to base 8, octal. Nine bears the same relationship to eight in octal, as eleven does to ten in decimal: 9₁₀ = 11₈, base plus one, and 8ⁿ ≡ − 1ⁿ (mod 9).

We can calculate k mod 9 in base 8 by alternately adding and subtracting the octal digits, from right to left. For example, 1234₈ mod 9 = 4 − 3 + 2 − 1 = 2. This gives the right answer.

Here's a simple, albeit incomplete, algorithm in Go. We're masking and shifting three bits at a time, which is tantamount to working with the octal representation of k.

func Mod9(k uint) uint {
    var m int = 0
    sign := +1

    for t := k; 0 != t; t >>= 3 {
        r := int(t & 7)
        m += sign * r
        sign = -sign
    }

    return uint(m)
}

What about 617₈?

7 − 1 + 6 = 12 ≡ 3 ( mod 9)

617₈ mod 9 = 3

And 6172₈?

2 − 7 + 1 − 6 = − 10 ≡ 8 ( mod 9)

6172₈ mod 9 = 8

Almost there!

Casting out “octal-elevens” (11₈ = 9₁₀) in octal, by an alternating sum of the base-eight digits, computes a small number congruent to the original number number modulo nine.

The algorithm above is calculating numbers that are congruent to the correct answer modulo nine, but which may be outside the desired range. If the intermediate sum dips below zero or rises above eight, we have to add nine or subtract nine respectively to keep the running total in the range [0, 9).

Here's a complete algorithm for Modulo 9 in Go, computing the alternating sum of the octal digits:

func Mod9(k uint) uint {
    var m int = 0
    var negative bool = false

    for t := k; 0 != t; t >>= 3 {
        r := int(t & 7)
        if negative {
            m -= r
            if m < 0 {
                m += 9
            }
        } else {
            m += r
            if m >= 9 {
                m -= 9
            }
        }
        // assert(0 <= m && m < 9)
        negative = !negative
    }

    return uint(m)
}

Clearly, this algorithm can be implemented in much simpler circuitry than that required to compute a remainder through full-blown division.

Modulo 36

We now have enough to calculate k mod 36 from Mod9 and the Chinese Remainder Theorem:

func Mod36(k uint) uint {
    Residues := [4][9]uint{
        { 0, 28, 20, 12,  4, 32, 24, 16,  8},
        { 9,  1, 29, 21, 13,  5, 33, 25, 17},
        {18, 10,  2, 30, 22, 14,  6, 34, 26},
        {27, 19, 11,  3, 31, 23, 15,  7, 35},
    }
    return Residues[k & 3][Mod9(k)]
}

My friend says that he later learned that similar tricks were used in classic 36-bit hardware.

I looked everywhere I could think of to see if I could find this algorithm to calculate modulo 9 described. I found something that hinted at it in Knuth's Seminumerical Algorithms, §4.4.C, discussing converting octal integers to decimal by hand, where he mentions using casting out nines in octal and in decimal to check the result. There was no mention of it in Warren's marvelous Hacker's Delight or in HAKMEM.

I tried to come up with an analytic way to calculate the elements of the 9x4 table. The best that I found is (72 − 8×(k mod 9) + 9×(k mod 4)) mod 36! The inner expression yields a number in the range [0, 99], which can be reduced to [0, 36) by subtracting 36 at most twice. From Concrete Mathematics, mod 36 can be derived from mod 4 and mod 9 by looking at the [0][1] and [1][0] elements of the table: (9×(k mod 4) + 28×(k mod 9)) mod 36. It works, but it's even worse. A table lookup is clearly more efficient.

Most, if not all, of the computer architectures designed in the last forty years use a word size that is a power of two. Useful relationships like shifting and masking are one big reason why non-power-of-two word sizes have gone out of fashion.

Another big reason is the success of C and Unix, which have a bias towards 8-bit bytes. C doesn't require 8-bit bytes, but there's a lot of software which tacitly assumes that char has exactly 8 bits.

On systems with 9-bit bytes, like the 36-bit computers, octal is useful, since a 9-bit byte can hold all values up to 777₈ and the word size is a multiple of three.

And there you have it: an unexpected use for octal notation. It's not exactly an important use, but then 36-bit computers aren't exactly important any more either.

Decrypting Blackbox secrets at build time with Paperkey

Mon, 02 Sep 2019 07:00:00 GMT

“Security is 1% technology plus 99% following the procedures correctly” — Tom Limoncelli

Having dealt with GPG last week at work, I remembered that I had intended to write a blog post about how we used GPG, Blackbox, and Paperkey to store secrets in Git at my previous job.

We used Blackbox to manage secrets that were needed during development, build, deployment, and runtime. These secrets included AWS credentials, Docker registry credentials, our private PyPI credentials, database credentials, and certificates. We wanted these secrets to be under version control, but also to be secure.

For example, we had a credentials.sh that exported environment variables, which was managed by Blackbox:

# Save current value of xtrace option from $-; disable echoing of executed commands
{ if echo $- | grep -q "x"; then XT="-x"; else XT="+x"; fi; set +x; } 2>/dev/null

# export environment variables, many containing secrets
export AWS_ACCESS_KEY_ID='...'
export AWS_SECRET_ACCESS_KEY='...'

export PYPI_USER='build'
export PYPI_PASSWD='...'
export PIP_INDEX_URL="https://$PYPI_USER:$PYPI_PASSWD@pypi.example.com/pypi/"

# Restore previous value of xtrace option
set $XT

The XT prologue ensures that even if this script is source’d with set -x (debug tracing) enabled, that executing this script will not leak secrets into build logs. The epilogue turns the xtrace option back on again if it was on at the start.

We used LastPass to manage personal credentials that were needed in a browser, but it wasn't suitable for automated use in CI.

How Blackbox Works

Blackbox builds on top of GNU Privacy Guard (aka GnuPG aka GPG) to automate the secure management of a set of files containing secrets that are “encrypted at rest” and stored in a Version Control System (VCS), such as Git. These registered files are owned collectively by a set of administrators, each of whom has their own separate keypair (a public key and a private key) stored in their own keyrings. The administrators' public keys are also present in Blackbox's keyring, which is stored in the VCS. Using Blackbox's commands, any administrator can decrypt a file containing secrets, update the secrets in the file, encrypt the updated secrets file, and commit that encrypted file into the VCS. Administrators can be removed from a Blackbox installation, after which they will not be able to decrypt the updated secrets files[1].

How does Blackbox encrypt a file so that any administrator can decrypt it? It uses GPG to encrypt the file for multiple recipients, say, Alice, Bob, and Carol.

When GPG encrypts a file, it:

creates a random session key for symmetric encryption
writes a header for each recipient, containing:
- the ID of the recipient's public key
- the result of asymmetrically encrypting the session key with the recipient's public key
possibly signs the data
compresses the (signed) data
symmetrically encrypts the compressed data with the session key
writes the encrypted, compressed data

Only the recipients have the private keys (in theory, at least). Therefore, only a recipient can decrypt the encrypted file.

To decrypt the file for a recipient, GPG:

finds the encrypted session key packet whose keyID matches the recipient's public key
decrypts the session key using the recipient's private key
decrypts the encrypted, compressed data using the session key
decompresses the decrypted data
verifies the signature, if present
writes the cleartext

This is a hybrid scheme. Symmetric encryption is a lot faster and more compact than public key/private key asymmetric encryption, so it's used to encrypt the actual data. Furthermore, if the data were entirely encrypted with a recipient's public key, then encrypting for N recipients would mean that the size of the result would be proportional to the (number of recipients) × (the length of the original data). With the hybrid scheme, the header grows a few hundred bytes for each recipient but the data is encrypted only once, with faster encryption.

Blackbox encrypts a registered file with all of the administrators as the recipients, so any administrator can decrypt the file.

Typical PGP Message

(Figure from Network Security: Email Security, PKI, Tuomas Aura)

You can use gpg --list-packets to dump the contents of any GPG message. An Advanced Intro to GnuPG dives into the message format in more detail.

Going back to my original example, credentials.sh is a file registered in blackbox-files.txt. This file should never be committed to the VCS—add it to gitignore to prevent accidentally committing it. Instead, credentials.sh.gpg is committed. Since the latter is a binary file, comparing two versions in cleartext is tricky.

[1]	If they have a snapshot of the VCS before their access was revoked, they will still be able to decrypt the secrets as they were then. In principle, you should be changing passwords and certificates every time someone's access is revoked.

Private Keys and Paperkey

Administrators can encrypt and decrypt Blackbox'd files because they have their private key on a local keyring.

Getting a private key onto other hosts can be tricky. We developed this technique when we were using Atlassian's hosted Bamboo CI service. We later used it with hosted Jenkins at Cloudbees. Because we were using a hosted Continuous Integration (CI) service, we had limited control over what we could install. If I remember correctly, Bamboo had support for secret environment variables, but did not provide a way to store a keyring file. There was also a limit on the length of the environment variables, I believe.

We were able to get past this by using Paperkey to (de)serialize the secret key. Paperkey can extract just the secret part of a secret key: ‘Due to metadata and redundancy, OpenPGP secret keys are significantly larger than just the "secret bits". In fact, the secret key contains a complete copy of the public key.’

We created a keypair for the CI on a secure host, serialized the secret with Paperkey, and pasted the secret into the CI's UI to become an environment variable. At build time, we used Paperkey on the CI box to deserialize the secret key from the environment variable, before decrypting the secrets needed with Blackbox.

To create the CI keypair, follow the portion of the Blackbox "role accounts" instructions that create a sub-key with no password for ci@example.com.

Then, serialize the public key and the secret with Paperkey:

cd /tmp/NEWMASTER
gpg --homedir . --export ci@example.com \
    | base64 > public_key.txt
gpg --homedir . --export-secret-keys ci@example.com \
    | paperkey --output-type=raw \
    | base64 > secret.txt

Copy and paste the contents of public_key.txt to the GPG_PUBLIC_KEY environment variable in the CI. Similarly, copy secret.txt to GPG_SECRET.

Securely delete everything in /tmp/NEWMASTER.

We used a script like this on the CI to reconstitute the keypair and to decrypt the other secrets from Blackbox:

#!/usr/bin/env bash

# Run during a CI build to decrypt all Blackbox-encrypted files in this repo.
# Can also be used interactively.

set -ex

# Root of Git working tree
SERVICES_DIR="$(cd "$(dirname "$0")/.."; pwd)"

if [ "$CI_BUILD" = "true" ]; then
    GPG_HOMEDIR="$(mktemp -d -t gnupg.XXX)"
    SECRET_KEY_FILE="$GPG_HOMEDIR/secret.key"
    PUBLIC_KEY_FILE="$GPG_HOMEDIR/public_key.gpg"

    # this variable is how you can customize how GPG is used in Blackbox
    GPG="gpg --homedir=$GPG_HOMEDIR"

    # Remove secrets from filesystem on exit.
    function clean_up {
        # TODO: use shred, if available
        rm -rf "$GPG_HOMEDIR"
    }
    trap clean_up EXIT;

    echo "Unpacking keys; exiting debug mode to redact..."
    set +x

    if [ -z "$GPG_PUBLIC_KEY" -o -z "$GPG_SECRET" ]; then
        echo "Missing CI credential env vars for GPG key and secret"
        exit 1
    fi

    # unpack public key
    echo "$GPG_PUBLIC_KEY" | base64 --decode > "$PUBLIC_KEY_FILE"

    # unpack secret key
    echo "$GPG_SECRET" | base64 --decode > "$SECRET_KEY_FILE"

    echo "Secrets unpacked..."
    set -x

    # reconstitute and import full key into $GPG_HOMEDIR
    paperkey --pubring "$PUBLIC_KEY_FILE" --secrets "$SECRET_KEY_FILE" \
        | $GPG --import

    # TODO: vendor Blackbox
    BLACKBOX_DIR="$(mktemp -d -t blackbox.XXX)"
    BLACKBOX_BIN=$BLACKBOX_DIR/bin

    # Shallow clone of Blackbox with most-recent commit only
    git clone --depth 1 https://github.com/StackExchange/blackbox.git $BLACKBOX_DIR
else
    # So that you only have to enter your password once when running interactively
    eval "$(gpg-agent --daemon)"

    # No custom GPG_HOMEDIR needed
    GPG="gpg"

    BLACKBOX_POSTDEPLOY="$(command -v blackbox_postdeploy)" || ret=$?
    if [ -n "$BLACKBOX_POSTDEPLOY" ]; then
        # Use the Blackbox that's on the path
        BLACKBOX_BIN="$(dirname $BLACKBOX_POSTDEPLOY)"
    else
        # Assume Blackbox is checked out in a sibling dir to $SERVICES_DIR
        BLACKBOX_BIN="$(cd "$SERVICES_DIR/.."; pwd)"/blackbox/bin
        if [ ! -f "$BLACKBOX_BIN/blackbox_postdeploy" ]; then
            echo "Can't find Blackbox binaries"
            exit 1
        fi
    fi
fi

# decrypt secrets in $SERVICES_DIR using custom GPG_HOMEDIR
GPG="$GPG" $BLACKBOX_BIN/blackbox_postdeploy

# test that decryption worked
grep 'congrats!' test_secret.txt

At the end of the build, run blackbox_shred_all_files to destroy any decrypted files.

4 \ 9	0	1	2	3	4	5	6	7	8
0	0	28	20	12	4	32	24	16	8
1	9	1	29	21	13	5	33	25	17
2	18	10	2	30	22	14	6	34	26
3	27	19	11	3	31	23	15	7	35

4 \ 9	0	1	2	3	4	5	6	7	8
0	0	28	20	12	4	32	24	16	8
1	9	1	29	21	13	5	33	25	17
2	18	10	2	30	22	14	6	34	26
3	27	19	11	3	31	23	15	7	35