Matt Brubeck

30 Oct 2009

Compleat: Bash completion for human beings

Compleat is an easy, declarative way to add smart tab completion for any shell command. It's written in Haskell but requires no programming knowledge. See the GitHub repository for a quick description, or read on for a complete explanation.


I'm one of those programmers who loves to carefully tailor my development environment. I do nearly all of my work at the shell or in a text editor, and I've spent a dozen years learning and customizing them to work more quickly and easily.

Most experienced shell users know about programmable completion, which provides smart tab-completion for supported programs like ssh and git. You can also add your own completions for programs that aren't supported. So I read the fine manual and started writing completions. You can see the script I made for three commands from the Google Android SDK. It's 200 lines of Bash code, and fairly straightforward if you happen to be familiar with the Bash completion API. But as I cranked out more and more case statements, I felt there must be a better way...

The Idea

It's not hard to describe the usage of a typical command-line program. There's even a semi-standard format for it, used in man pages and generated by libraries like AutoOpt. For example, here's the usage for android, one of the SDK commands supported by my script:

 android [--silent | --verbose]
   ( list [avd|target]
   | create avd ( --target <target> | --name <name> | --skin <name>
                | --path <file> | --sdcard <file> | --force ) ...
   | move avd (--name <avd> | --rename <new> | --path <file>) ...
   | (delete|update) avd --name <avd>
   | create project ( (--package|--name|--activity|--path) <val>
                    | --target <target> ) ...
   | update project ((--name|--path) <val> | --target <target>) ...
   | update adb )

My idea: What if you could teach the shell to complete a program's arguments just by writing a usage description like this one?

The Solution

With Compleat, you can add completion for any command just by writing a usage description and saving it in a configuration folder. The ten-line description of the android command above generates the same results as my 76-line bash function, and it's so much easier to write and understand!

The syntax should be familiar to long-time Unix users. Optional arguments are enclosed in square brackets; alternate choices are separated by vertical pipes. An ellipsis following an item means it may be repeated, and parentheses group several items into one. Words in angle brackets are parameters for the user to fill in.

Let's look at some more features of the usage format. For programs with complicated arguments, it can be useful to break them down further. You can place alternate usages on their own lines separated by semicolons, like this:

android <opts> list [avd|target];
android <opts> move avd (--name <avd>|--rename <new>|--path <file>)...;
android <opts> (delete|update) avd --name <avd>;

...and so on. Rather than repeat the common options on every line, I used a parameter named "opts". I can define that parameter to be a sub-pattern, which will be used wherever <opts> appears:

opts = [ --silent | --verbose ];

For parameters whose values are not fixed but can be computed by another program, we use a ! symbol followed by a shell command to generate completions. For example, we can run shell commands to suggest names of Android Virtual Devices or target types whenever <avd> or <target> appears in a pattern:

avd = ! android list avd | grep 'Name:' | cut -f2 -d: ;
target = ! android list target | grep '^id:'| cut -f2 -d' ' ;

Any parameter without a definition will use the shell's built-in completion rules, which suggest matching filenames by default.

The source code is on GitHub. I've been using it for just a week and I'm now writing new usage files for myself almost every day. The README file has more details about the usage syntax, and instructions for installing the software. Give it a try, and please send in any usage files that you want to share! (Questions, bug reports, or patches are also welcome.)

Future Work

For the next release of Compleat, I would like to make installation easier by providing better packaging and pre-compiled binaries; support zsh and other non-bash shells; and write better documentation.

In the long term, I'm thinking about replacing the usage file interpreter with a compiler. The compiler would translate the usage file into shell code, or perhaps another language like C or Haskell. This would potentially improve performance (although speed isn't an issue right now on my development box), and make it easy for usage files to include logic written in the target language. Another idea for the future: What if option-parsing libraries like AutoOpt or the Ruby/Perl/Python equivalents generated completion scripts for every program you wrote?

Final Thoughts

I realized recently that some things I do are so specialized that my parents and non-programmer friends will probably never get them. For example, Compleat is a program to generate programs to help you… run programs? Sigh. Well, maybe someone out there will appreciate it.

Compleat was my weekends/evenings/bus-rides project for the last few weeks (as you can see in the GitHub punch card), and my most fun side project in quite a while. It's the first "real" program I've written in Haskell, though I've been experimenting with the language for a while. Now that I'm comfortable with it, I find that Haskell's particular combination of features works just right to enable quick exploratory programming, while giving a high level of confidence in the behavior of the resulting program. Compleat 1.0 is just 160 lines of Haskell, excluding comments and imports. Every module was completely rewritten at least once as I compared different approaches. (This is much less daunting when the code in question is only a couple dozen lines.) I don't think this particular program would have been quite as easy to write—at least for me—in any of the other platforms I know (including Ruby, Python, Scheme, and C).

I had the idea for Compleat more than a year ago, but at the time I did not know how to implement it easily. I quickly realized that what I wanted to write was a specialized parser generator, and a domain-specific language to go with it. Unfortunately I never took a compiler-design class in school, and had forgotten most of what I learned in my programming languages course. So I began studying parsing algorithms and language implementation, with Compleat as my ultimate goal.

My good friend Josh and his Gazelle parser generator helped inspire me and point me toward other existing work. Compleat actually contains three parsers. The usage file parser and the input line tokenizer are built on the excellent Parsec library. The usage file is then translated into a parser that's built with my own simple set of parser combinators, which were inspired both by Parsec and by the original Monadic Parser Combinators paper by Graham Hutton and Erik Meijer. The simple evaluator for the usage DSL applies what I learned from Jonathan Tang's Write Yourself a Scheme in 48 Hours. And of course Real World Haskell was an essential resource for both the nuts and bolts and the design philosophy of Haskell.

So besides producing a tool that will be useful to me and hopefully others, I also filled in a gap in my education, learned some great new languages and tools, and kindled an interest in several new (to me) research areas. It has also renewed my belief in the importance of "academic" knowledge to real engineering problems. I've already come across at least one problem in my day job that I was able to solve faster by implementing a simple parser than I would have a year ago by fumbling with regexes. And I'll be even happier if this inspires some friends or strangers to take a closer look at Haskell, Parsec, or any problem they've thought about and didn't know enough to solve. Yet.