Tuesday, April 10, 2012

Autocompletion support for Scala's combinator parsers

Recently, I came to revisit Scala a bit more in depth -- compared to the odd script or hack I did before. Now, things at work change a bit: some green-field stuff to be done, even calling for some kind of DSL -- ok, maybe not really calling, really loudly but close enough to warrant spending some quality playing-time with my favorite "next great programming language".
So I threw together some combinator parsers which was some fun in itself and most of it felt very good. Except there was no autocompletion. The envisioned DSL should, among other things, navigate a mildly complex domain model. But, in contrast to a generic expression language, typos in property-names should be caught at the syntax level, and possible completions should be displayed when the user types the start of a property (or a dot). What I wanted to do was something like the made-up example below:
Of course, in the real DSL, the properties would not be hardcoded but reflectively collected from the model. The missing key-feature here is the CompletingParser mix-in: It doesn't come with the standard Scala library and I didn't easily find a nice solution readymade. So, that looked like a good opportunity to take Scala's extensibility for a test-drive that's both, interesting and easily within a Scala-beginner's reach
The basic ideas are
  • override the Parser class' alternative combinator "|" to make it collect possible completions in the ParseResult instead of just returning a Failure
  • override the implicit factory method for string literals to produce an alternative literal parser which differentiates between an unexpected and a missing character
As it turns out, in the standard implementation, the | combinator just delegates to ParseResult's append method which normally discards all results but the successful one, or, failing that, returns the failure which consumed most of the input stream. So we just need to replace the Failure parse result with a version that's able to keep track of possible completions, rather smellily named MissingCompletionOrFailure. This plan led me to the following little trait:
Now a simple command-loop to take our work for an interactive test-drive looks like this: