Monday, August 30, 2010

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

Tuesday, August 17, 2010

Pencils down

Phew! GSOC 2010 is over. I've had a lot of fun working on ENSIME this summer, and I'm really excited about some of the new features. Here's a quick overview of what's been added:

Project configuration:
  • ENSIME can now find dependencies declared via sbt, Maven or Ivy.
  • The M-x ensime-config-gen automates the creation of a .ensime configuration for your project.

Type/Package Inspector:
  • The inspector now alerts you when an interface is provided via implicit resolution.
  • There's now a toggle link to switch between a type and its companion object.
  • Type arguments are linked separately.
  • Nested types are listed for each interface.

Completion:
  • Symbol and member completion much more reliable.
  • Completion candidates are prettier.
  • Method parameter help is displayed in the minibuffer when completing a call.

Incremental Builder:
  • Added a stand-alone, incremental builder based on scala.tools.nsc.interactive.BuildManager
  • Errors and warnings are displayed in a hyperlinked read-out after each build/rebuild.

Refactoring support:
  • Mirko Stocker's stand-alone refactoring library has been integrated.
  • Rename, Organize Imports, Extract Method, Inline Local are all just an Emacs command away.

SBT integration:
  • Ray Racine's inferior sbt mode for Emacs has been integrated.
  • There's an elisp-hacker-friendly interface for sending commands to sbt.

Debugger integration:
  • JDB can now be controlled using graphical breakpoints and run/step/next shortcuts.
  • class->source and source->class mapping are handled intelligently, so setting breakpoints in anonymous functions works as it should.

REPL integration:
  • Scala REPL can be launched with your project's classes loaded.

If you want more information on any of these topics, please check the ENSIME manual.

And, of course, the work is far from done. There are still plenty of rough edges, and if you run into one, please open an issue at github. Or even better, fork the repo and send a patch! The meat of ENSIME is its Scala-based server component, so you don't even need to look at E-Lisp in order to contribute ;)

This summer was a great experience for me. I want to thank my GSOC mentor Hubert Plociniczak for his patient support, the organizers at Google for creating this program, and all the brilliant folks at EPFL for making Scala such a wonderful language to work with.

-Aemon

Friday, July 9, 2010

Debugger Sneak Peak

I've started working on debug support for ENSIME. The plan is launch JDB as an inferior process, send commands via stdin and then parse what comes out of stdout. Things are moving along pretty well - here's a little screencast I just made to demo the progress:

http://www.youtube.com/watch?v=v7-G6vD42z8

Emacs users will probabably be aware that Emacs already includes a general framework for managing commandline gdb-esque debuggers, called gud-mode. In fact, gud-mode already includes support for controlling an inferior jdb. It's very basic (barely functional), though, and not extensible in the ways that I required (no way to redefine the methods for mapping class->source or source ->class). Thus I decided to whip up an improved jdb-specific debugging mode in ensime-debug.el. This new mode uses the ENSIME server to accurately map source locations to classes (for setting breakpoints) and to map class names to source files (for moving the debugger mark).

Wednesday, June 30, 2010

New, new .ensime format

In my previous post I proposed a new ENSIME configuration format, to support the inclusion of Maven, Ivy, and sbt dependencies. Since then I've noticed that external build specifications are also useful for launching the REPL and the debugger. Specifically, one needs to know the runtime dependencies of the project, which are often different from the compilation dependencies (usually a super-set of). I've modified the .ensime file format so that Maven,Ivy and Sbt users are better able to utilize their existing build configurations in ENSIME.

Here's an example .ensime, for an sbt project:

(

:server-root "/home/aemon/src/misc/ensime/dist"
:server-cmd "bin/server.sh"

:use-sbt t
:sbt-compile-conf "compile"
:sbt-runtime-conf "runtime"

:project-package "com.ensime"
:debug-class "com.ensime.server.Server"
:debug-args ("/tmp/ensime_port.tmp")

)

This configuration will cause ENSIME to use the "compile" dependencies for building and the "runtime" dependencies when launching the REPL or debugger. The :use-sbt directive also sets default values for the :sources and :target directives (which can be overridden if needed).

A similiar maven configuration would look like this:
:use-maven t
:maven-compile-scopes "compile"
:maven-runtime-scopes "runtime"

And for Ivy:
:use-ivy t
:ivy-compile-conf "compile"
:ivy-runtime-conf "runtime"

The options available are fully explained in the .ensime.example file in the root of the distribution.

Thursday, June 10, 2010

Maven and Ivy and sbt, oh my

One of the goals of ENSIME is to provide support for common build systems, so that you don't have to repeat yourself (too much) when describing your project. At the same time, we want to stay decoupled from any particular build system.

I've been sketching out some changes to the .ensime config format:

(
:server-root
"/home/aemon/src/misc/ensime/dist"

:server-cmd "bin/server.sh"
:server-host "localhost"

:project-package "com.ensime"

:source (
:include ([files or dirs(recursive)])
:exclude ([file or dirs(recursive)])
)

:classpath (
:ivy [ t | nil ]
:mvn [ t | nil ]
:sbt [ t | nil ]
:jars ([files or dirs(recursive)])
:dirs ([dirs])
)

)

The :ivy and :mvn options would cause ENSIME to search for "ivy.xml" or "pom.xml", and analyze these files for dependencies. The locations of these dependencies in the local ivy or maven cache would then be added to the classpath.

The :sbt option would cause the jars in the 'lib' and 'lib_managed' directories to be added to the classpath.

The :jars and :dirs option would act as a fallback when the above options are not sufficient.

I think it's important that ENSIME _not_ try to do the work of a build management system; that problem is already well solved. Hence, there are no plans to try to resolve and download dependencies.

Saturday, May 29, 2010

SBT and ENSIME

I imported Ray Racine's sbt.el into the ENSIME project today. What this means is that sbt users can now type C-c C-a to launch (or switch to an existing) sbt interactive shell.

Warnings and errors are automatically highlighted in the shell, and file references are hyperlinked (just like in an Emacs compilation-mode buffer).

Users can customize ensime-sbt-compile-on-save to enable automatic recompilation every time a scala/java buffer is saved. This option is disabled by default, as it eats a lot of CPU, and I don't feel it adds a whole lot over the existing ENSIME syntax/type checking. It may be useful, though, if you're working on a project that you need to run frequently.

If you'd like to bind short-cut keys to sbt actions, you can use the function: ensime-sbt-action which issues an action, provided as a string argument, to the sbt shell.

Thanks to Ray for a nice piece of code. I use sbt for ENSIME development, so this is a welcome addition : )

Thursday, May 27, 2010

The State of Completion

ENSIME uses two completion facilities provided by the Scala presentation compiler, askScopeCompletion and askTypeCompletion. The first lists the symbols that are accessible in the current scope. The second lists the symbols that are accessible as members of the Type of the Symbol at the given Position.

The decision of whether to complete a symbol or a member is made in Emacs, based on the current syntactic context. If the user hits TAB when typing a symbol that follows what looks like an expression, separated by a dot or space, we try to complete as a type member. Otherwise, we assume it's just a floating symbol.

ENSIME augments the completion information with information about the Type and 'callability' of each symbol. This way, we can fill in parenthesis and parameter information when the user selects a callable symbol.

Today I added a third context for completion of a symbol following 'new'. In this situation ENSIME will only return completion candidates that are known to be class constructors. As with methods, we provide param help in the mini-buffer after a completion is chosen.