Compleat is an easy, declarative way to add smart tab-completion for
any command-line program. For a quick description, see the
README. For
more explanation and a brief tutorial, keep reading...
Background
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 for supported programs like ssh and git. (If you are
not familiar it, you
really should install and enable bash-completion, or
the equivalent package for your chosen shell.) You can also add your own
completions for programs that aren't supported but in my experience,
most users never bother.
When I worked at Amazon, everyone used Zsh (which has a very powerful but
especially baroque completion system) and shared the completion scripts they
wrote for our myriad internal tools. Now that I'm in a startup with few other
command line die-hards, I'm on my own when it comes to extending my shell.
So I read the fine manual and started writing my own completions. Over on
GitHub you can see the
script I made for three commands from the Google
Android SDK. It's 200 lines of shell code, 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
GNU AutoOpt. Here's one 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
<opts>. I can define that parameter using the same usage syntax.
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, like this:
avd = ! android list avd grep 'Name:' cut -f2 -d: ;
target = ! android list target grep '^id:' cut -f2 -d' ' ;
And any parameter without a definition will just use the shell's built-in
completion rules, which suggest matching filenames by default.
The
README file has more details of 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 would also make it easy for usage files to include logic written in the
target language.
Final Thoughts
Recently I realized that parts of my work are so specialized that my parents
and non-programmer friends will probably never really 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
only 160 lines of Haskell, excluding comments and imports. Every module was
completely rewritten at least once as I tried and 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 CS 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.
This afternoon Andre released
telepathy-qt4 0.2.0,
the first version that builds a shared library, and I've uploaded it to Debian
(it'll get into unstable as soon as it clears the NEW queue).
This is a major milestone for telepathy-qt4: over the course of 16 months'
development it's gone from a collection of auto-generated constants (Olli
Salli's initial commit, back in July 2008) to a shared library with a frozen
API and ABI. We encourage Qt/KDE application developers to treat telepathy-qt4
as the preferred Qt 4 binding for Telepathy.
Andre and the rest of
the Telepathy project will continue
to add high-level bindings for more Telepathy features over the course of the
0.3.x series; we plan to keep the API and ABI backwards-compatible until
shortly before the next milestone, 0.4.0, at which point we'll consider
breaking ABI to drop deprecated functionality.
A lot of people seem to think that open source is a magic solution to
project management and that open source projects will automatically
attract a large and healthy community of contributors and users who will
improve the software. This, of course, is not the case. In fact,
creating a successful open source project is a really major and
difficult effort. You have to deliver an initial promise that people
find interesting, attract other people, then facilitate and lead the
community, etc. You just have to look at all the failed projects on
SourceForge that never delivered any code to see that "open source" is
not a guarantee for success.
Even though project management is a key element of every open source
project, there are only few resources about this topic. That's why I
always enjoy reading about the experience from open source project
leaders. Jim Hall, the founder of the FreeDOS project, recently posted
a series of four articles which I find particularly interesting.
Here are links to the articles along with a quick summary:
ACPI is a confusing place. It's often thought of as a suspend/resume
thing, though if you're unlucky you've learned that it's also involved
in boot-time configuration because it's screwed up your interrupts
again. But ACPI's also heavily involved in the runtime management of
the system, and it's necessary for there to be a mechanism for the
hardware to alert the OS of events.
ACPI handles this case by providing a set of general purpose events
(GPEs). The implementation of these is fairly straightforward - an
ACPI table points at a defined system resource (typically an area of
system io space, though in principle it could be something like mmio
instead), and when the hardware fires an ACPI interrupt the kernel
looks at this region to see which GPEs are flagged. Then things get
more interesting.
The majority of GPEs are implemented in the ACPI tables via methods
with names like _Lxx or _Exx. The xx is the number of the GPE in hex,
while the leading _L or _E indicates whether the GPE is level- or
edge-triggered. If an ACPI interrupt is fired and GPE 0x1D is flagged
as being the source of the interrupt, the ACPI interpreter will then
look for an _L1D or _E1D method. Upon finding one, it'll execute
it. What this method does is entirely up to the firmware - on most HP
laptops, GPE 0x1D is hooked up to the lid switch[1] and so executing
it will send a notification to the OS that the lid switch has changed
state. The OS will then evaluate the state of the lid switch
(generally by making another ACPI query) and send the event up to
userspace.
How does the lid end up triggering GPE 0x1D? Things get pretty
hardware specific at this point. Intel motherboard chipsets have a set
of general purpose io (GPIO) lines that can, for the most part[2], be
used by the system vendor for anything they want. For a lid switch,
one of these lines is hooked to the switch and the BIOS configures the
GPIO as an input. Pressing the switch will cause the GPIO line to
become active. The GPIO lines are mapped to GPEs in a 1:1 manner,
though with an offset of 16 - ie, GPIO 0xd will map to GPE 0x1d. If
GPIO 0xd becomes active, GPE 0x1d will be flagged and an ACPI
interrupt sent. The ACPI code will then do something to quash the
interrupts, such as inverting the polarity of the GPIO[3], as well as
send the notification to the OS.
Why are the GPIOs offset by 16 relative to the GPEs? The lower 16 GPEs
(again, talking about Intel hardware) have pre-defined
purposes[4]. These range from things like "Critically low battery" to
"PCIe hotplug event" down to "This device triggered a wakeup". And the
latter is what I'm most interested in here.
Various pieces of modern hardware can be placed into power saving
states when not in use. The problem with this is that the user
experience of having to turn on hardware before you can use it is not
a good one, so in order to make this the default behaviour we need the
hardware to tell us that something happened that requires us to wake
the hardware up.
There's something of a chicken and egg problem here, but thankfully
most of the relevant modern hardware has out of band mechanisms to
tell us about things going on. The PCI spec defines something called
Power Management Events (PME), which are driven by an additional
current that's supplied to the hardware even when it's otherwise
turned off. On plug-in PCI Express cards, firing a PME generates an
interrupt on the root bridge and a native driver can interpret that,
but for legacy PCI devices and integrated chipset devices the
notification has to come via ACPI.
The example I've been working on is USB. It's a good choice for
various reasons - firstly, there's already support for detecting when
the USB controller is idle. Secondly, modern USB host controllers have
support for generating PMEs on device insertion, removal or (and this
is important) remote wakeup. In other words, as long as the USB bus is
idle we can power down the entire USB controller. If the OS tries to
access a USB device, we'll power it back up. If the user unplugs or
plugs a device, we'll power it back up. If a previously idle device
suddenly responds to some external input, we'll power it back up. And
it's all nicely invisible to the user.
How does this work? The controller retains a small amount of power
even when nominally pwoered down. This is used to keep the detection
circuitry alive. When it receives a wakeup event, it asserts the PME
line. The chipset detects this and fires a GPE. The OS runs this GPE
and receives a device notification on the ACPI representation of the
USB controller, telling us to power it back up. We do so and process
whatever woke us - if the bus then goes idle again, we can power down
once more.
The astonishing thing is that this all works. The only problem we have
is that it relies on the machine vendor to have provided the ACPI
methods that are associated with the GPEs. If they haven't, we can't
enable this functionality - even though the hardware is capable of
generating the GPEs, we have no method to execute to let us know which
device has to be woken up. The GPE is never answered, we never
acknowledge the PME and the hardware keeps on screaming for attention
without getting any. And, more to the point, it never gets powered up
and your mouse doesn't work.
There's a pretty gross hack to deal with this. In general, we know
what the GPE to device mappings are - they're pretty static across
Intel chipsets, and while AMD ones can be programmed differently by
the BIOS we can read that information back and set up a mapping
ourselves. This trick also comes in handy when some vendors (like,
say, Dell) manage to implement one of the GPE events
wrongly. Everything looks like it should work, but the method never
sends a notification because it's buggy. In that case we can
unregister the existing method and implement our own instead.
This code isn't upstream yet, but patches have been posted to the
linux-acpi mailing list and with luck it'll be there in the 2.6.33
timeframe. My tests suggest about 0.2W saving per machine, which isn't
going to save all that many polar bears but seems worth it anyway.
[1] _L1D = lid. Sigh.
[2] There's a few that are reserved for specific purposes
[3] So where before it had to be high to be active, it now has to be
low to be active - this means that it'll now trigger on the switch
being opened rather than closed, so you'll get another event when you
open the lid again.
[4] You can find a list in the documentation for the appropriate ICH
chip - the relevant section is "GPE0_STS" under the LPC interface
chapter.
I was referred to 
I have been reading a great many posts about Android lately, some consisting of criticism, some of praise and some simply addressing issues in the Android community . Let s have a look at those.
Matt Porter s Android Mythbusters presentation and Harald Welte s reaction
Sarah's Mum is flying her back for the scattering of her grandmother's ashes,
and I figured that as this will be her third trip back this year, and she's
seen my family more than I have in the last 12 months, I should come as well.
So I'm getting my first opportunity to sample 
Earlier this year, 
The ftpmasters merged my dak branch last week during their meeting and have enabled the support of new source formats 3.0 (quilt) and 3.0 (native) in testing, unstable and testing-proposed-updates. I have uploaded 3 packages using the new formats already: logidee-tools using 3.0 (native) , quilt and ftplib using 3.0 (quilt) . The latter is arch any and has been 
As a concluding remark, 
This month hasn't seen many big changes happen in FusionForge.
Notable improvements include an initial search engine for Word files,
fixes to the automated builds and tests, and lots of bugfixes.
The biggest news is probably the start of the