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:

	class TestParser extends JavaTokenParsers with CompletingParser {
	def propertyPath: Parser[Any] = "name" | ( "child"~opt("."~childProperties) ) | "chunk"
	def childProperties: Parser[Any] = "name" | "toys" | "tolerance"
	}

view raw TestParser.scala hosted with ❤ by GitHub

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:

	import util.parsing.combinator.RegexParsers
	/**
	* A trait to make parsers for string literals return a nice list of possible completions if
	* we're at the end of the input.
	*
	* @author Marcus Schulte
	*/
	trait CompletingParser extends RegexParsers {
	/**
	* A `Failure` which is curable by adding one of several possible completions.
	*
	* @param completions what would make the parser succeed if added to `in`.
	* @param next the input about to be read
	*/
	case class MissingCompletionOrFailure( val completions: List[String],
	override val msg: String,
	override val next: Input )
	extends Failure( msg, next ) {
	override def append[U](a: => ParseResult[U]) = a match {
	case MissingCompletionOrFailure( newCompletions, _, _ )
	=> val comps = completions ++ newCompletions;
	new MissingCompletionOrFailure( comps,
	if (comps.isEmpty) msg else "expected one of " + comps,
	next )
	case ns: NoSuccess => this
	case s: Success[U] => s
	}
	}
	override implicit def literal( s: String ) : Parser[String] =new Parser[String] {
	def apply(in: Input) = {
	val source = in.source
	val offset = in.offset
	val start = handleWhiteSpace(source, offset)
	var i = 0
	var j = start
	while (i < s.length && j < source.length && s.charAt(i) == source.charAt(j)) {
	i += 1
	j += 1
	}
	if (i == s.length)
	Success(source.subSequence(start, j).toString, in.drop(j - offset))
	else if (j == source.length()) {
	val missing = s.substring(i)
	MissingCompletionOrFailure( List(missing), "expected one of "+missing, in.drop(start - offset) )
	} else {
	MissingCompletionOrFailure( List(), "`"+s+"' expected but "+source.charAt(j)+" found", in.drop(start - offset))
	}
	}
	}
	}

view raw CompletingParser.scala hosted with ❤ by GitHub

Now a simple command-loop to take our work for an interactive test-drive looks like this:

	object CompletingParserTestApp extends TestParser with App {
	println( "Type something and hit enter" );
	var input = ""
	do {
	input = readLine();
	parseAll( propertyPath, input ) match {
	case s : Success[Any] => println ( "valid, parsed as "+ s.get)
	case MissingCompletionOrFailure( completions, msg, in)
	=> if ( completions.isEmpty )
	println( msg )
	else {
	println( "possible completions: ");
	for ( c <- completions ) println( input + c )
	}
	}
	}
	while ( input != "" )
	}

view raw App.scala hosted with ❤ by GitHub