Building my own shell in Python — day 3

Today was tab completion. Type a few letters, hit Tab, the shell fills in the rest. It's the feature you use more than any other and think about less than any other.

I had the intuition immediately — given what's been typed so far, find the commands that start with it and offer them. What I didn't have was any idea how to actually wire that into a terminal. Three separate things had to be true before a single Tab press would do anything, and I got all three wrong before I got them right.

The bug wasn't in the completion code

I wrote a completer. I registered it. I pressed Tab. Nothing happened — not a wrong suggestion, not an error, just nothing at all.

The problem was somewhere I hadn't thought to look: how I was reading input. I'd been using sys.stdin.readline(), which does exactly what it says — reads a line from standard input. Nothing more.

But readline, the library that provides completion, doesn't intercept your terminal globally. It hooks into Python's built-in input() specifically. Read your line any other way and you've quietly opted out of the whole thing — completion, history, arrow-key editing, all of it. My completer was correct. It was simply never being called.

Switching to input() fixed it, and it's the portable choice anyway: readline isn't part of the standard library on Windows, and input() keeps working there regardless — just without the extras.

Knowing the directories isn't knowing the files

My first real attempt at gathering candidates is still sitting in my source as a commented-out line, because it's too good a mistake to delete:

[e for e in path_dirs if e.startswith(text)]

I was searching the directory names in PATH, not the programs inside them. Which produces exactly nothing useful, and taught me something I hadn't noticed on day 1.

Back then, running an external command meant a probe: I had a name — ls — and I walked the PATH directories asking one yes/no question, does this-directory/ls exist and can I execute it. Precise, cheap, and it only works because you already know what you're looking for.

Completion has no name. It has a prefix. And you cannot probe for something you can't name — there's no file to check the existence of. You have to go the other direction entirely: open every directory on PATH, list everything inside it, keep whatever is actually an executable file, and only then filter by what's been typed.

Listing a directory's contents and checking whether one specific path exists are different operations. Day 1 solved finding the directories. Day 3 turned out to need the files.

Doing that on every keystroke is a bad idea

The first working version scanned all of PATH every single time Tab was pressed. It worked, and it was obviously wrong the moment I thought about it. PATH can hold a dozen directories with hundreds of executables each, and Tab is the most-pressed key in a shell. That's a pile of filesystem work for something that has to feel instantaneous.

So I cache it. The scan runs once, stores the result, and every call after that returns the stored list immediately. Concretely: the first Tab press pays the full cost, and every Tab press after it is free. The completer stops touching the disk and just filters a list already in memory. Names are collected into a set along the way, so a program that appears in two different PATH directories is only offered once.

Which introduces the obvious problem with any cache: it's a snapshot. Install a new program while the shell is running and completion won't know it exists, because the list it's filtering was built before that program did.

So I added a rehash builtin that clears the cache. The next Tab press finds it empty, rebuilds it from scratch, and picks up everything new. I later found out this isn't a workaround I invented — zsh has a rehash command that does the same job for the same reason. Running into a problem and independently landing on the solution real shells use is a good feeling.

The completer protocol is not what you'd guess

This is the part where knowing the intuition genuinely didn't help.

If you designed this yourself, you'd write a function that takes a prefix and returns a list of matches. One call, one list, done. That is not what readline wants.

readline wants a function it can call over and over, handing it the same text each time along with a counter that increases on every call. You return the first match when the counter is 0, the second when it's 1, and so on — and None once you've run out, which is how it knows to stop asking.

completer("ec", 0)  ->  "echo"
completer("ec", 1)  ->  "echoes"
completer("ec", 2)  ->  None      # that's all of them

It's a strange shape until you accept it, and then it's fine. Compute the matches, hand them back one at a time, index by the counter.

Two details worth getting right inside it. Builtins and executables are gathered separately and then merged with duplicates removed — necessary because a name like echo exists both as a builtin and as a real file on disk, and offering it twice looks broken. And each completed command comes back with a trailing space, so the cursor is ready for the next word — a small thing that makes it feel like a real shell instead of an imitation of one.

Binding Tab, and one last trap

Registering a completer isn't enough on its own. Tab has to be explicitly bound to the completion action, or the key stays as dumb as it ever was.

And a subtler one I hit while cleaning up: the prompt has to be handed to input(), not printed beforehand. Writing $ to the screen yourself and then calling input() looks identical — until you start editing or completing, and the line redraws in the wrong place. readline needs to know what the prompt is to work out where your text actually begins. Print it separately and you've hidden that from it.

Where I am now

Completion works across builtins and every executable on PATH, it's fast after the first press, and rehash keeps it honest when the system changes underneath it.

Three days in, and every single feature has followed the same shape: the idea is obvious, and all the actual work is in the layer underneath the idea.