Building an IDE with the Scala Presentation Compiler: A Field Report

The intention of this post is to sketch the 'lay of the land' for others who, like me, want to use the presentation compiler for developing interactive Scala tools. If you want to dig deeper, I suggest the Scala internal mailing list, or taking a look at the Scala source code.


Motivation

One of the key functions of an IDE is to 'understand' the source code that the programmer writes, so that it can offer help at a semantic, rather than purely textual, level. For example, when a programmer begins to type the name of an instance method, she expects the IDE to suggest candidates methods that begin with that prefix. The IDE does the work of ensuring the candidates are all legal at this point in the program. Consider the following Scala fragment (where _ denotes the cursor):

val dog = "dog"
val og = dog.subs_

An IDE might suggest the method "substring" of the class String. This is textually correct ("subs" is a prefix of "substring") and also semantically correct, substring(a:Int,j:Int):String is a method of the String class. In order to provide this suggestion the IDE must know the type of the identifier 'dog' at this point of the program. This is not difficult to deduce in the above fragment, but as the code becomes more complex:

case class MyPair[A, B](x: A, y: B);
object Main extends Application {
 def id[T](x: T) = x
 val q = id(1)  // type: Int
 val p = new MyPair(q, "scala")
 p._
}

...it gets trickier. Scala's support for type inference and implicit resolution make the job especially hard. In some cases it's impossible to deduce the types of an expression without having a global view of the project and its dependencies. Of course the Scala compiler has just such a view, so what we'd really like to do is have the compiler tell us what it knows about the program...


The Scala Presentation Compiler

Most of the time we interact with the Scala compiler as a batch translator. We stuff a bunch of source in one end, and it spits out binaries from the other. Somewhere in between we know that the compiler is constructing ASTs, transforming them, figuring out the types of everything, etc., but this information is thrown as soon as the output is written. The presentation compiler was introduced so that external tools could get access to the compiler's internal model.

The source for the presentation compiler can be found in the Scala repository in the package scala.tools.nsc.interactive. The most important file for this discussion is Global.scala. If you open Global.scala, you'll see that it extends the standard Scala compiler, scala.tools.nsc.Global, and mixes in several helpers.

class Global(settings: Settings, reporter: Reporter)
     extends scala.tools.nsc.Global(settings, reporter)
        with CompilerControl
        with RangePositions
        with ContextTrees
        with RichCompilationUnits {

The first thing Global does is fire up its main runner thread. This thread is the brains of the presentation compiler. Its job is two-fold: to manage a set of CompilationUnits, trying to make them as up-to-date as possible, and to service client requests. The main logic for the runner is copied below:

       ....
       while (true) {
         scheduler.waitForMoreWork()
         pollForWork()
         while (outOfDate) {
           try {
             backgroundCompile()
             outOfDate = false
           } catch {
             case FreshRunReq =>
           }
         }
       }
   ....

As you can see, the presentation compiler does two things in its main loop: it services work requests from the client, and it compiles all known units until outOfDate = false. The inner loop is necessary because the backgroundCompile method may be interrupted by a user request.

It's important to remember this picture of the compiler's behavior, as it will determine how clients must interact with the compiler. All work must be done within a scheduled work unit or we risk corruption due to race conditions.

Let's look a bit closer at the compilation behavior. beckgroundCompile assembles a list of units to recompile, and then calls recompile.

  def recompile(units: List[RichCompilationUnit]) {
    for (unit <- units) {
      reset(unit)
      if (debugIDE) inform("parsing: "+unit)
      parse(unit)
    }
    for (unit <- units) {
      if (debugIDE) inform("type checking: "+unit)
      activeLocks = 0
      currentTyperRun.typeCheck(unit)
      unit.status = currentRunId
    }
  }

Each unit is reset to a pristine state, re-parsed, and then type-checked against the current Run instance. In the standard Scala compiler, a Run will consist of many phases, all the way up to byte-code generation. In the presentation compiler, we only apply the typerPhase phase. This specialized Run is defined in Global.scala:

 class TyperRun extends Run {
   // units is always empty

   /** canRedefine is used to detect double declarations in multiple  source files.
    *  Since the IDE rechecks units several times in the same run,  these tests
    *  are disabled by always returning true here.
    */
   override def canRedefine(sym: Symbol) = true

   def typeCheck(unit: CompilationUnit): Unit = {
     applyPhase(typerPhase, unit)
   }
   ...

The Run instance maintains the global map of definitions, so that cross-unit dependencies can be checked. Note that canRedefine is overridden so that a single unit may be type-checked against this Run many times without generating redefinition errors.



Client Interface

The client interface to the presentation compiler is defined in CompilerControl. CompilerControl is a convenience interface that does the work of adding jobs to the main runner thread. It usually returns a sync var in case the client wants to block on the request. There are roughly three categories of requests you can make through CompilerControl:

• Requesting for sources to be reloaded from disk, and for the corresponding units to be recompiled.

• Requesting Context or Tree objects for a specific source position.

• Requesting completion results for members of a Type, or symbols in a Context.

This interface provides most of the functionality you'd need for an IDE. Let's break down some common use-cases.


Displaying Error and Warning Messages

Remember from before that the compiler was parametrized with a Reporter instance. Whenever an error or warning is generated by the compiler, the reporter is notified. In the standard compiler, the reporter's behavior is to write these messages to the console. In an interactive IDE, we would rather aggregate these messages and transform them to our own data-structures. For example, in ENSIME, I use the following (inspired by code in the Eclipse Scala Plugin):

class PresentationReporter extends Reporter {

 private val notes = new HashMap[SourceFile, HashSet[Note]] with  SynchronizedMap[SourceFile, HashSet[Note]] {
   override def default(k: SourceFile) = { val v = new HashSet[Note];  put(k, v); v }
 }

 def allNotes: Iterable[Note] = {
   notes.flatMap { e => e._2 }.toList
 }

 .....

 override def info0(pos: Position, msg: String, severity: Severity,  force: Boolean): Unit = {
   severity.count += 1
   try {
     if (pos.isDefined) {
       val source = pos.source
       val note = new Note(
         source.file.absolute.path,
         formatMessage(msg),
         severity.id,
         pos.startOrPoint,
         pos.endOrPoint,
         pos.line,
         pos.column
         )
       notes(source) += note
     }
   } catch {
     case ex: UnsupportedOperationException =>
   }
 }
 .....

Whenever the compiler reports an error or warning, I transform it to my own Note data-structure and then add it to a collection. When the compile is done, I use these notes to display errors and warnings to the user.

If, for example, you wanted to check a file for errors after a user saves, you can trigger a recompile with the askReloadSources method of CompilerControl. The reporter first receives any parsing errors generated when the source is reloaded - this is done in the job that the runner thread pulls from the queue. Later, asynchronously with respect to client code, the runner thread will do a background compile and the reporter will receive the full type-checking results.




Accessing Symbol or Type Information for a Specific Position

There are many situations in which an IDE will want semantic information for a specific source position. For example, jumping to the definition of a symbol, or providing on-demand type information when the user clicks on or hovers over a symbol. To satisfy these requests we can use the askTypeAt method of CompilerControl, which, despite it's name, actually returns a Tree instance that's been annotated with types.

Trees are great. Once you have a typed tree corresponding to the requested source position, you have access to all the symbol and type information that your heart may desire. Check out scala.tools.nsc.symtab.Symbols$Symbol and scala.tools.nsc.symtab.Types$Type for details on what's available.

Since requesting trees is very common, the presentation compiler provides special support for quickly retrieving them. askTypeAt in CompilerControl boils down to a call to typeTreeAt in TyperRun:

def typedTreeAt(pos: Position): Tree = {
     val tree = locateTree(pos)
     if (stabilizedType(tree) ne null) {
       tree
     } else {
       val unit = unitOf(pos)
       assert(unit.status >= JustParsed)
       unit.targetPos = pos
       try {
         typeCheck(unit)
         throw new FatalError("tree not found")
       } catch {
         case ex: TyperResult =>
           ex.tree
       } finally {
         unit.targetPos = NoPosition
       }
     }
   }

First there are some checks to see if an annotated tree is already available for the position. Then, if the tree is not available, the unit is type-checked, and then it seems a FatalError is immediately thrown... What's going on here? Well, in order to return to the client as quickly as possible the compiler only wants to type-check far enough to get the tree for our position. Any further work is wasted. Notice the surrounding try,catch handler that matches TyperResults. Elsewhere, the presentation compiler overrides signalDone, which is invoked whenever a node finishes type-checking:

 override def signalDone(context: Context, old: Tree, result: Tree) {

     .....

     if (context.unit != null &&
         result.pos.isOpaqueRange &&
         (result.pos includes context.unit.targetPos)) {
     ....
       throw new TyperResult(located)
     }

     .....

As soon as the requested position is 'done', a TyperResult is thrown that will short-circuit the rest of the type-check. Control hops over that 'throw FatalError' and immediately returns a piping hot tree to the waiting user. Pretty neat!



Symbol Completion & Type Member Completion

CompilerControl has two methods for requesting completion results. askTypeCompletion(pos:Position, result:Response[List[Member]]) returns the visible members of the tree at pos. askScopeCompletion(pos:Position, result:Response[List[Member]]) returns the visible members of the scope that encloses pos.

The tricky thing about completion is that the results need to be based on the very latest source. If I quickly type dog.ba_, I expect the completion engine will give me legitimate Dog members. This means that before we can ask for completions, we have to reload the source and refresh the trees. And since the source at this point is by definition _incomplete_, the compiler may have trouble deducing types.

The technique I use in ENSIME is to make a background copy of the source buffer, clean it up so it's easier to parse, and then use that buffer as the basis for completion. For example, if my source read:

def hello(){
 val dog = "dog"
 dog.sub_
}

...and the user pressed TAB, a copy of the buffer would be created that reads:

def hello(){
 val dog = "dog"
 dog.()
}

First off, notice that the method prefix is gone. The prefix will be used later to filter the results, but all we're really interested in now is getting the members of dog.

The '()' is an expression that I find helps to prevent compiler confusion when there are trailing commas in the source. Remember, the askTypeCompletions call expects to be given the position of the _target_ of the member access, so it's critical that the compiler be able to find the type of 'dog'. Once the request gets to the ENSIME server, the modified source is reloaded using reloadSources and then we grab a tree using typedTreeAt (the short-circuiting tree getter).

A similar technique is used for scope completion. We start with:

def hello(){
 hell_
}

...and massage to:

def hello(){
  ()
}

The position we pass to askScopeCompletion is the space immediately preceding '()'. In this case the '()' is a workaround for a compiler bug (fixed in trunk) that causes the context to be measured incorrectly if you're completing a symbol at the end of a block.

There's a bit more work that needs to be done to collect the results and transform them to something presentable, but I'll leave that as an exercise for the reader (or you can just look inside ENSIME).


Another Warning on Races

It's important to use the work scheduling API to interact with the compiler. Bad things might happen otherwise. Here's what Martin Odersky had to say on the subject:

 
  .......
  The issue is that _any_ operation on a symbol, type or tree returned
  by the presentation compiler is a potential race condition. Even a
  simple member lookup or subtype check can internally change compiler
  state, and if that happens concurrently with a presentation compiler
  background compile, bad things will happen.
  ......

  What to do? Any operation on a tree, type or symbol that was returned
  by the presentation compiler, and that is more than a simple  attribute
  value get should be run on the presentation compiler thread.
  Previously, there was no easy and fast way to do this, but now there
  is: I added an `ask` operation to
  scala.tools.nsc.interactive.CompilerControl which will execute the
  passed operation as a high priarity "interrupt" on the presentation
  compiler thread. You should never have to wait more than a couple of
  milliseconds on operations dispatched to `ask`. Here's the signature
  of this method:

   def ask[A](op: () => A): A


  So where previously you might have written T <:< U, say, you should
  now transform this to
  
   cc.ask(T <:< U)
  
  where `cc` is your instance of the presentation compiler
  CompilerControl.

  

Unfortunately, this 'ask' method is not available in 2.8.0, but it's not hard to hack together a similar solution for defining custom jobs.


Onward

I hope you found this post useful! The presentation compiler is a great tool. For a language like Scala, where re-implementing the type-checking behavior would be highly non-trivial, it's an enabling tool. Many thanks to the Scala core team for providing this window onto the compiler's innards.

[ By the way, if you found this post because you're interested in adding Scala support to your favorite editor, I suggest you consider re-using the ENSIME server. It wraps all the compiler goodness and exposes it via an editor-agnostic socket protocol. ]


Aemon