Add sbt incremental compilation support

To test this with sbt, see
https://github.com/lampepfl/dotty/wiki/Using-Dotty-with-sbt

The following flags are added:
 - -Yforce-sbt-phases: Run the phases used by sbt for incremental compilation
   (ExtractDependencies and ExtractAPI) even if the compiler is ran outside of
   sbt, for debugging.
 - -Ydump-sbt-inc: For every compiled foo.scala, output the API
   representation and dependencies used for sbt incremental compilation
   in foo.inc, implies -Yforce-sbt-phases.

This commit introduces two new phases which do not transform trees:
- `ExtractDependencies` which extracts the dependency information of the current
  compilation unit and sends it to sbt via callbacks
- `ExtractAPI` which creates a representation of the API of the current compilation
  unit and sends it to sbt via callbacks

Briefly, when a file changes sbt will recompile it, if its API has
changed (determined by what `ExtractAPI` sent) then sbt will determine
which reverse-dependencies (determined by what `ExtractDependencies`
sent) of the API have to be recompiled depending on what changed.
See http://www.scala-sbt.org/0.13/docs/Understanding-Recompilation.html for
more information on how sbt incremental compilation works.

This phase was originally based on
https://github.com/adriaanm/scala/tree/sbt-api-consolidate/src/compiler/scala/tools/sbt
which attempts to integrate the sbt phases into scalac (and is itself based
on https://github.com/sbt/sbt/tree/0.13/compile/interface/src/main/scala/xsbt),
but it has been heavily refactored and adapted to Dotty. The main
functional differences are:
- ExtractDependencies runs right after Frontend (so that we don't lose
  dependency informations because of the simplifications done by PostTyper),
  but ExtractAPI runs right after PostTyper (so that SuperAccessors are
  part of the API).
- `ExtractAPI` only extract types as they are defined and never "as seen
  from" some some specific prefix, see its documentation for more details.
- `ExtractDependenciesTraverser` and `ExtractUsedNames` have been fused into
  one tree traversal in `ExtractDependenciesCollector`.

TODO: Try to run these phases in parallel with the rest of the compiler
pipeline since they're independent (except for the sbt callbacks in `GenBCode`) ?

9 files changed, 986 insertions, 5 deletions

diff --git a/src/dotty/tools/backend/jvm/GenBCode.scala b/src/dotty/tools/backend/jvm/GenBCode.scala
index 8cec93977..e5b227a97 100644
--- a/src/dotty/tools/backend/jvm/GenBCode.scala
+++ b/src/dotty/tools/backend/jvm/GenBCode.scala
@@ -389,6 +389,8 @@ class GenBCodePipeline(val entryPoints: List[Symbol], val int: DottyBackendInter
             val className = jclassName.replace('/', '.')
             if (ctx.compilerCallback != null)
               ctx.compilerCallback.onClassGenerated(sourceFile, convertAbstractFile(outFile), className)
+            if (ctx.sbtCallback != null)
+              ctx.sbtCallback.generatedClass(sourceFile.jfile.orElse(null), outFile.file, className)
           }
           catch {
             case e: FileConflictException =>
diff --git a/src/dotty/tools/dotc/Compiler.scala b/src/dotty/tools/dotc/Compiler.scala
index 049906ef0..2ddd81718 100644
--- a/src/dotty/tools/dotc/Compiler.scala
+++ b/src/dotty/tools/dotc/Compiler.scala
@@ -42,7 +42,9 @@ class Compiler {
   def phases: List[List[Phase]] =
     List(
       List(new FrontEnd),           // Compiler frontend: scanner, parser, namer, typer
+      List(new sbt.ExtractDependencies), // Sends information on classes' dependencies to sbt via callbacks
       List(new PostTyper),          // Additional checks and cleanups after type checking
+      List(new sbt.ExtractAPI),     // Sends a representation of the API of classes to sbt via callbacks
       List(new Pickler),            // Generate TASTY info
       List(new FirstTransform,      // Some transformations to put trees into a canonical form
            new CheckReentrant),     // Internal use only: Check that compiled program has no data races involving global vars
diff --git a/src/dotty/tools/dotc/config/ScalaSettings.scala b/src/dotty/tools/dotc/config/ScalaSettings.scala
index f9c10442a..583778db2 100644
--- a/src/dotty/tools/dotc/config/ScalaSettings.scala
+++ b/src/dotty/tools/dotc/config/ScalaSettings.scala
@@ -160,6 +160,8 @@ class ScalaSettings extends Settings.SettingGroup {
   val YtestPickler = BooleanSetting("-Ytest-pickler", "self-test for pickling functionality; should be used with -Ystop-after:pickler")
   val YcheckReentrant = BooleanSetting("-Ycheck-reentrant", "check that compiled program does not contain vars that can be accessed from a global root.")
   val YkeepComments = BooleanSetting("-Ykeep-comments", "Keep comments when scanning source files.")
+  val YforceSbtPhases = BooleanSetting("-Yforce-sbt-phases", "Run the phases used by sbt for incremental compilation (ExtractDependencies and ExtractAPI) even if the compiler is ran outside of sbt, for debugging.")
+  val YdumpSbtInc = BooleanSetting("-Ydump-sbt-inc", "For every compiled foo.scala, output the API representation and dependencies used for sbt incremental compilation in foo.inc, implies -Yforce-sbt-phases.")
   def stop = YstopAfter
 
   /** Area-specific debug output.
diff --git a/src/dotty/tools/dotc/core/Contexts.scala b/src/dotty/tools/dotc/core/Contexts.scala
index e1aeac8c3..0c916eb4f 100644
--- a/src/dotty/tools/dotc/core/Contexts.scala
+++ b/src/dotty/tools/dotc/core/Contexts.scala
@@ -29,6 +29,7 @@ import printing._
 import config.{Settings, ScalaSettings, Platform, JavaPlatform, SJSPlatform}
 import language.implicitConversions
 import DenotTransformers.DenotTransformer
+import xsbti.AnalysisCallback
 
 object Contexts {
 
@@ -84,6 +85,12 @@ object Contexts {
       _compilerCallback = callback
     def compilerCallback: CompilerCallback = _compilerCallback
 
+    /** The sbt callback implementation if we are run from sbt, null otherwise */
+    private[this] var _sbtCallback: AnalysisCallback = _
+    protected def sbtCallback_=(callback: AnalysisCallback) =
+      _sbtCallback = callback
+    def sbtCallback: AnalysisCallback = _sbtCallback
+
     /** The current context */
     private[this] var _period: Period = _
     protected def period_=(period: Period) = {
@@ -426,6 +433,7 @@ object Contexts {
     def setPeriod(period: Period): this.type = { this.period = period; this }
     def setMode(mode: Mode): this.type = { this.mode = mode; this }
     def setCompilerCallback(callback: CompilerCallback): this.type = { this.compilerCallback = callback; this }
+    def setSbtCallback(callback: AnalysisCallback): this.type = { this.sbtCallback = callback; this }
     def setTyperState(typerState: TyperState): this.type = { this.typerState = typerState; this }
     def setReporter(reporter: Reporter): this.type = setTyperState(typerState.withReporter(reporter))
     def setNewTyperState: this.type = setTyperState(typerState.fresh(isCommittable = true))
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 09d7f0185..a318390d1 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -2484,10 +2484,14 @@ object Types {
 
   abstract class ParamType extends BoundType {
     def paramNum: Int
+    def paramName: Name
   }
 
   abstract case class MethodParam(binder: MethodType, paramNum: Int) extends ParamType with SingletonType {
     type BT = MethodType
+
+    def paramName = binder.paramNames(paramNum)
+
     override def underlying(implicit ctx: Context): Type = binder.paramTypes(paramNum)
     def copyBoundType(bt: BT) = new MethodParamImpl(bt, paramNum)
 
@@ -2500,7 +2504,7 @@ object Types {
         false
     }
 
-    override def toString = s"MethodParam(${binder.paramNames(paramNum)})"
+    override def toString = s"MethodParam($paramName)"
   }
 
   class MethodParamImpl(binder: MethodType, paramNum: Int) extends MethodParam(binder, paramNum)
@@ -2530,9 +2534,11 @@ object Types {
       case _ => false
     }
 
+    def paramName = binder.paramNames(paramNum)
+
     override def underlying(implicit ctx: Context): Type = binder.paramBounds(paramNum)
     // no customized hashCode/equals needed because cycle is broken in PolyType
-    override def toString = s"PolyParam(${binder.paramNames(paramNum)})"
+    override def toString = s"PolyParam($paramName)"
 
     override def computeHash = doHash(paramNum, binder.identityHash)
 
@@ -2784,9 +2790,9 @@ object Types {
       if ((prefix eq cls.owner.thisType) || !cls.owner.isClass || ctx.erasedTypes) tp
       else tp.substThis(cls.owner.asClass, prefix)
 
-    private var typeRefCache: Type = null
+    private var typeRefCache: TypeRef = null
 
-    def typeRef(implicit ctx: Context): Type = {
+    def typeRef(implicit ctx: Context): TypeRef = {
       def clsDenot = if (prefix eq cls.owner.thisType) cls.denot else cls.denot.copySymDenotation(info = this)
       if (typeRefCache == null)
         typeRefCache =
@@ -2795,7 +2801,7 @@ object Types {
       typeRefCache
     }
 
-    def symbolicTypeRef(implicit ctx: Context): Type = TypeRef(prefix, cls)
+    def symbolicTypeRef(implicit ctx: Context): TypeRef = TypeRef(prefix, cls)
 
     // cached because baseType needs parents
     private var parentsCache: List[TypeRef] = null
diff --git a/src/dotty/tools/dotc/sbt/ExtractAPI.scala b/src/dotty/tools/dotc/sbt/ExtractAPI.scala
new file mode 100644
index 000000000..c0a3c3dfe
--- /dev/null
+++ b/src/dotty/tools/dotc/sbt/ExtractAPI.scala
@@ -0,0 +1,479 @@
+package dotty.tools.dotc
+package sbt
+
+import ast.{Trees, tpd}
+import core._, core.Decorators._
+import Contexts._, Flags._, Phases._, Trees._, Types._, Symbols._
+import Names._, NameOps._, StdNames._
+
+import dotty.tools.io.Path
+import java.io.PrintWriter
+
+import scala.collection.mutable
+
+/** This phase sends a representation of the API of classes to sbt via callbacks.
+ *
+ *  This is used by sbt for incremental recompilation.
+ *
+ *  See the documentation of `ExtractAPICollector`, `ExtractDependencies`,
+ *  `ExtractDependenciesCollector` and
+ *  http://www.scala-sbt.org/0.13/docs/Understanding-Recompilation.html for more
+ *  information on incremental recompilation.
+ *
+ *  The following flags affect this phase:
+ *   -Yforce-sbt-phases
+ *   -Ydump-sbt-inc
+ *
+ *  @see ExtractDependencies
+ */
+class ExtractAPI extends Phase {
+  override def phaseName: String = "sbt-api"
+
+  // SuperAccessors need to be part of the API (see the scripted test
+  // `trait-super` for an example where this matters), this is only the case
+  // after `PostTyper` (unlike `ExtractDependencies`, the simplication to trees
+  // done by `PostTyper` do not affect this phase because it only cares about
+  // definitions, and `PostTyper` does not change definitions).
+  override def runsAfter = Set(classOf[transform.PostTyper])
+
+  override def run(implicit ctx: Context): Unit = {
+    val unit = ctx.compilationUnit
+    val dumpInc = ctx.settings.YdumpSbtInc.value
+    val forceRun = dumpInc || ctx.settings.YforceSbtPhases.value
+    if ((ctx.sbtCallback != null || forceRun) && !unit.isJava) {
+      val sourceFile = unit.source.file.file
+      val apiTraverser = new ExtractAPICollector
+      val source = apiTraverser.apiSource(unit.tpdTree)
+
+      if (dumpInc) {
+        // Append to existing file that should have been created by ExtractDependencies
+        val pw = new PrintWriter(Path(sourceFile).changeExtension("inc").toFile
+          .bufferedWriter(append = true), true)
+        try {
+          pw.println(DefaultShowAPI(source))
+        } finally pw.close()
+      }
+
+      if (ctx.sbtCallback != null)
+        ctx.sbtCallback.api(sourceFile, source)
+    }
+  }
+}
+
+/** Extracts full (including private members) API representation out of Symbols and Types.
+ *
+ *  The exact representation used for each type is not important: the only thing
+ *  that matters is that a binary-incompatible or source-incompatible change to
+ *  the API (for example, changing the signature of a method, or adding a parent
+ *  to a class) should result in a change to the API representation so that sbt
+ *  can recompile files that depend on this API.
+ *
+ *  Note that we only records types as they are defined and never "as seen from"
+ *  some other prefix because `Types#asSeenFrom` is a complex operation and
+ *  doing it for every inherited member would be slow, and because the number
+ *  of prefixes can be enormous in some cases:
+ *
+ *    class Outer {
+ *      type T <: S
+ *      type S
+ *      class A extends Outer { /*...*/ }
+ *      class B extends Outer { /*...*/ }
+ *      class C extends Outer { /*...*/ }
+ *      class D extends Outer { /*...*/ }
+ *      class E extends Outer { /*...*/ }
+ *    }
+ *
+ *  `S` might be refined in an arbitrary way inside `A` for example, this
+ *  affects the type of `T` as seen from `Outer#A`, so we could record that, but
+ *  the class `A` also contains itself as a member, so `Outer#A#A#A#...` is a
+ *  valid prefix for `T`. Even if we avoid loops, we still have a combinatorial
+ *  explosion of possible prefixes, like `Outer#A#B#C#D#E`.
+ *
+ *  It is much simpler to record `T` once where it is defined, but that means
+ *  that the API representation of `T` may not change even though `T` as seen
+ *  from some prefix has changed. This is why in `ExtractDependencies` we need
+ *  to traverse used types to not miss dependencies, see the documentation of
+ *  `ExtractDependencies#usedTypeTraverser`.
+ *
+ *  TODO: sbt does not store the full representation that we compute, instead it
+ *  hashes parts of it to reduce memory usage, then to see if something changed,
+ *  it compares the hashes instead of comparing the representations. We should
+ *  investigate whether we can just directly compute hashes in this phase
+ *  without going through an intermediate representation, see
+ *  http://www.scala-sbt.org/0.13/docs/Understanding-Recompilation.html#Hashing+an+API+representation
+ */
+private class ExtractAPICollector(implicit val ctx: Context) extends ThunkHolder {
+  import tpd._
+  import xsbti.api
+
+  /** This cache is necessary for correctness, see the comment about inherited
+   *  members in `apiClassStructure`
+   */
+  private[this] val classLikeCache = new mutable.HashMap[ClassSymbol, api.ClassLike]
+  /** This cache is optional, it avoids recomputing representations */
+  private[this] val typeCache = new mutable.HashMap[Type, api.Type]
+
+  private[this] object Constants {
+    val emptyStringArray = Array[String]()
+    val local            = new api.ThisQualifier
+    val public           = new api.Public
+    val privateLocal     = new api.Private(local)
+    val protectedLocal   = new api.Protected(local)
+    val unqualified      = new api.Unqualified
+    val thisPath         = new api.This
+    val emptyType        = new api.EmptyType
+    val emptyModifiers   =
+      new api.Modifiers(false, false, false, false, false,false, false, false)
+  }
+
+  /** Some Dotty types do not have a corresponding type in xsbti.api.* that
+   *  represents them. Until this is fixed we can workaround this by using
+   *  special annotations that can never appear in the source code to
+   *  represent these types.
+   *
+   *  @param tp      An approximation of the type we're trying to represent
+   *  @param marker  A special annotation to differentiate our type
+   */
+  private def withMarker(tp: api.Type, marker: api.Annotation) =
+    new api.Annotated(tp, Array(marker))
+  private def marker(name: String) =
+    new api.Annotation(new api.Constant(Constants.emptyType, name), Array())
+  val orMarker = marker("Or")
+  val byNameMarker = marker("ByName")
+
+
+  /** Extract the API representation of a source file */
+  def apiSource(tree: Tree): api.SourceAPI = {
+    val classes = new mutable.ListBuffer[api.ClassLike]
+    def apiClasses(tree: Tree): Unit = tree match {
+      case PackageDef(_, stats) =>
+        stats.foreach(apiClasses)
+      case tree: TypeDef =>
+        classes += apiClass(tree.symbol.asClass)
+      case _ =>
+    }
+
+    apiClasses(tree)
+    forceThunks()
+    new api.SourceAPI(Array(), classes.toArray)
+  }
+
+  def apiClass(sym: ClassSymbol): api.ClassLike =
+    classLikeCache.getOrElseUpdate(sym, computeClass(sym))
+
+  private def computeClass(sym: ClassSymbol): api.ClassLike = {
+    import xsbti.api.{DefinitionType => dt}
+    val defType =
+      if (sym.is(Trait)) dt.Trait
+      else if (sym.is(ModuleClass)) {
+        if (sym.is(PackageClass)) dt.PackageModule
+        else dt.Module
+      } else dt.ClassDef
+
+    val selfType = apiType(sym.classInfo.givenSelfType)
+
+    val name = if (sym.is(ModuleClass)) sym.fullName.sourceModuleName else sym.fullName
+
+    val tparams = sym.typeParams.map(tparam => apiTypeParameter(
+      tparam.name.toString, tparam.variance,
+      tparam.info.bounds.lo, tparam.info.bounds.lo))
+
+    val structure = apiClassStructure(sym)
+
+    new api.ClassLike(
+      defType, strict2lzy(selfType), strict2lzy(structure), Constants.emptyStringArray,
+      tparams.toArray, name.toString, apiAccess(sym), apiModifiers(sym),
+      apiAnnotations(sym).toArray)
+  }
+
+  private[this] val LegacyAppClass = ctx.requiredClass("dotty.runtime.LegacyApp")
+
+  def apiClassStructure(csym: ClassSymbol): api.Structure = {
+    val cinfo = csym.classInfo
+
+    val bases = linearizedAncestorTypes(cinfo)
+    val apiBases = bases.map(apiType)
+
+    // Synthetic methods that are always present do not affect the API
+    // and can therefore be ignored.
+    def alwaysPresent(s: Symbol) =
+      s.isCompanionMethod || (csym.is(ModuleClass) && s.isConstructor)
+    val decls = cinfo.decls.filterNot(alwaysPresent).toList
+    val apiDecls = apiDefinitions(decls)
+
+    val declSet = decls.toSet
+    // TODO: We shouldn't have to compute inherited members. Instead, `Structure`
+    // should have a lazy `parentStructures` field.
+    val inherited = cinfo.baseClasses
+      // We cannot filter out `LegacyApp` because it contains the main method,
+      // see the comment about main class discovery in `computeType`.
+      .filter(bc => !bc.is(Scala2x) || bc.eq(LegacyAppClass))
+      .flatMap(_.classInfo.decls.filterNot(s => s.is(Private) || declSet.contains(s)))
+    // Inherited members need to be computed lazily because a class might contain
+    // itself as an inherited member, like in `class A { class B extends A }`,
+    // this works because of `classLikeCache`
+    val apiInherited = lzy(apiDefinitions(inherited).toArray)
+
+    new api.Structure(strict2lzy(apiBases.toArray), strict2lzy(apiDecls.toArray), apiInherited)
+  }
+
+  def linearizedAncestorTypes(info: ClassInfo): List[Type] = {
+    val ref = info.fullyAppliedRef
+    // Note that the ordering of classes in `baseClasses` is important.
+    info.baseClasses.tail.map(ref.baseTypeWithArgs)
+  }
+
+  def apiDefinitions(defs: List[Symbol]): List[api.Definition] = {
+    // The hash generated by sbt for definitions is supposed to be symmetric so
+    // we shouldn't have to sort them, but it actually isn't symmetric for
+    // definitions which are classes, therefore we need to sort classes to
+    // ensure a stable hash.
+    // Modules and classes come first and are sorted by name, all other
+    // definitions come later and are not sorted.
+    object classFirstSort extends Ordering[Symbol] {
+      override def compare(a: Symbol, b: Symbol) = {
+        val aIsClass = a.isClass
+        val bIsClass = b.isClass
+        if (aIsClass == bIsClass) {
+          if (aIsClass) {
+            if (a.is(Module) == b.is(Module))
+              a.fullName.toString.compareTo(b.fullName.toString)
+            else if (a.is(Module))
+              -1
+            else
+              1
+          } else
+            0
+        } else if (aIsClass)
+          -1
+        else
+          1
+      }
+    }
+
+    defs.sorted(classFirstSort).map(apiDefinition)
+  }
+
+  def apiDefinition(sym: Symbol): api.Definition = {
+    if (sym.isClass) {
+      apiClass(sym.asClass)
+    } else if (sym.isType) {
+      apiTypeMember(sym.asType)
+    } else if (sym.is(Mutable, butNot = Accessor)) {
+      new api.Var(apiType(sym.info), sym.name.toString,
+        apiAccess(sym), apiModifiers(sym), apiAnnotations(sym).toArray)
+    } else if (sym.isStable) {
+      new api.Val(apiType(sym.info), sym.name.toString,
+        apiAccess(sym), apiModifiers(sym), apiAnnotations(sym).toArray)
+    } else {
+      apiDef(sym.asTerm)
+    }
+  }
+
+  def apiDef(sym: TermSymbol): api.Def = {
+    def paramLists(t: Type, start: Int = 0): List[api.ParameterList] = t match {
+      case mt @ MethodType(pnames, ptypes) =>
+        // TODO: We shouldn't have to work so hard to find the default parameters
+        // of a method, Dotty should expose a convenience method for that, see #1143
+        val defaults =
+          if (sym.is(DefaultParameterized)) {
+            val qual =
+              if (sym.isClassConstructor)
+                sym.owner.companionModule // default getters for class constructors are found in the companion object
+              else
+                sym.owner
+            (0 until pnames.length).map(i => qual.info.member(sym.name.defaultGetterName(start + i)).exists)
+          } else
+            (0 until pnames.length).map(Function.const(false))
+        val params = (pnames, ptypes, defaults).zipped.map((pname, ptype, isDefault) =>
+          new api.MethodParameter(pname.toString, apiType(ptype),
+            isDefault, api.ParameterModifier.Plain))
+        new api.ParameterList(params.toArray, mt.isImplicit) :: paramLists(mt.resultType, params.length)
+      case _ =>
+        Nil
+    }
+
+    val tparams = sym.info match {
+      case pt: PolyType =>
+        (pt.paramNames, pt.paramBounds).zipped.map((pname, pbounds) =>
+          apiTypeParameter(pname.toString, 0, pbounds.lo, pbounds.hi))
+      case _ =>
+        Nil
+    }
+    val vparamss = paramLists(sym.info)
+    val retTp = sym.info.finalResultType.widenExpr
+
+    new api.Def(vparamss.toArray, apiType(retTp), tparams.toArray,
+      sym.name.toString, apiAccess(sym), apiModifiers(sym), apiAnnotations(sym).toArray)
+  }
+
+  def apiTypeMember(sym: TypeSymbol): api.TypeMember = {
+    val typeParams = Array[api.TypeParameter]()
+    val name = sym.name.toString
+    val access = apiAccess(sym)
+    val modifiers = apiModifiers(sym)
+    val as = apiAnnotations(sym)
+    val tpe = sym.info
+
+    if (sym.isAliasType)
+      new api.TypeAlias(apiType(tpe.bounds.hi), typeParams, name, access, modifiers, as.toArray)
+    else {
+      assert(sym.isAbstractType)
+      new api.TypeDeclaration(apiType(tpe.bounds.lo), apiType(tpe.bounds.hi), typeParams, name, access, modifiers, as.to)
+    }
+  }
+
+  def apiType(tp: Type): api.Type = {
+    typeCache.getOrElseUpdate(tp, computeType(tp))
+  }
+
+  private def computeType(tp: Type): api.Type = {
+    // TODO: Never dealias. We currently have to dealias because
+    // sbt main class discovery relies on the signature of the main
+    // method being fully dealiased. See https://github.com/sbt/zinc/issues/102
+    val tp2 = if (!tp.isHK) tp.dealias else tp
+    tp2 match {
+      case NoPrefix | NoType =>
+        Constants.emptyType
+      case tp: NamedType =>
+        val sym = tp.symbol
+        // Normalize package prefix to avoid instability of representation
+        val prefix = if (sym.isClass && sym.owner.is(Package))
+          sym.owner.thisType
+        else
+          tp.prefix
+        new api.Projection(simpleType(prefix), sym.name.toString)
+      case TypeApplications.AppliedType(tycon, args) =>
+        def processArg(arg: Type): api.Type = arg match {
+          case arg @ TypeBounds(lo, hi) => // Handle wildcard parameters
+            if (lo.eq(defn.NothingType) && hi.eq(defn.AnyType))
+              Constants.emptyType
+            else {
+              val name = "_"
+              val ref = new api.ParameterRef(name)
+              new api.Existential(ref,
+                Array(apiTypeParameter(name, arg.variance, lo, hi)))
+            }
+          case _ =>
+            apiType(arg)
+        }
+
+        val apiTycon = simpleType(tycon)
+        val apiArgs = args.map(processArg)
+        new api.Parameterized(apiTycon, apiArgs.toArray)
+      case rt: RefinedType =>
+        val name = rt.refinedName.toString
+        val parent = apiType(rt.parent)
+
+        def typeRefinement(name: String, tp: TypeBounds): api.TypeMember = tp match {
+          case TypeAlias(alias) =>
+            new api.TypeAlias(apiType(alias),
+              Array(), name, Constants.public, Constants.emptyModifiers, Array())
+          case TypeBounds(lo, hi) =>
+            new api.TypeDeclaration(apiType(lo), apiType(hi),
+              Array(), name, Constants.public, Constants.emptyModifiers, Array())
+        }
+
+        val decl: Array[api.Definition] = rt.refinedInfo match {
+          case rinfo: TypeBounds =>
+            Array(typeRefinement(name, rinfo))
+          case _ =>
+            ctx.debuglog(i"sbt-api: skipped structural refinement in $rt")
+            Array()
+        }
+        new api.Structure(strict2lzy(Array(parent)), strict2lzy(decl), strict2lzy(Array()))
+      case tp: AndOrType =>
+        val parents = List(apiType(tp.tp1), apiType(tp.tp2))
+
+        // TODO: Add a real representation for AndOrTypes in xsbti. The order of
+        // types in an `AndOrType` does not change the API, so the API hash should
+        // be symmetric.
+        val s = new api.Structure(strict2lzy(parents.toArray), strict2lzy(Array()), strict2lzy(Array()))
+        if (tp.isAnd)
+          s
+        else
+          withMarker(s, orMarker)
+      case ExprType(resultType) =>
+        withMarker(apiType(resultType), byNameMarker)
+      case ConstantType(constant) =>
+        new api.Constant(apiType(constant.tpe), constant.stringValue)
+      case AnnotatedType(tpe, annot) =>
+        // TODO: Annotation support
+        ctx.debuglog(i"sbt-api: skipped annotation in $tp2")
+        apiType(tpe)
+      case tp: ThisType =>
+        apiThis(tp.cls)
+      case RefinedThis(binder) =>
+        apiThis(binder.typeSymbol)
+      case tp: ParamType =>
+        new api.ParameterRef(tp.paramName.toString)
+      case tp: LazyRef =>
+        apiType(tp.ref)
+      case tp: TypeVar =>
+        apiType(tp.underlying)
+      case _ => {
+        ctx.warning(i"sbt-api: Unhandled type ${tp.getClass} : $tp")
+        Constants.emptyType
+      }
+    }
+  }
+
+  // TODO: Get rid of this method. See https://github.com/sbt/zinc/issues/101
+  def simpleType(tp: Type): api.SimpleType = apiType(tp) match {
+    case tp: api.SimpleType =>
+      tp
+    case _ =>
+      ctx.debuglog("sbt-api: Not a simple type: " + tp.show)
+      Constants.emptyType
+  }
+
+  def apiThis(sym: Symbol): api.Singleton = {
+    val pathComponents = sym.ownersIterator.takeWhile(!_.isEffectiveRoot)
+      .map(s => new api.Id(s.name.toString))
+    new api.Singleton(new api.Path(pathComponents.toArray.reverse ++ Array(Constants.thisPath)))
+  }
+
+  def apiTypeParameter(name: String, variance: Int, lo: Type, hi: Type): api.TypeParameter =
+    new api.TypeParameter(name, Array(), Array(), apiVariance(variance),
+      apiType(lo), apiType(hi))
+
+  def apiVariance(v: Int): api.Variance = {
+    import api.Variance._
+    if (v < 0) Contravariant
+    else if (v > 0) Covariant
+    else Invariant
+  }
+
+  def apiAccess(sym: Symbol): api.Access = {
+    // Symbols which are private[foo] do not have the flag Private set,
+    // but their `privateWithin` exists, see `Parsers#ParserCommon#normalize`.
+    if (!sym.is(Protected | Private) && !sym.privateWithin.exists)
+      Constants.public
+    else if (sym.is(PrivateLocal))
+      Constants.privateLocal
+    else if (sym.is(ProtectedLocal))
+      Constants.protectedLocal
+    else {
+      val qualifier =
+        if (sym.privateWithin eq NoSymbol)
+          Constants.unqualified
+        else
+          new api.IdQualifier(sym.privateWithin.fullName.toString)
+      if (sym.is(Protected))
+        new api.Protected(qualifier)
+      else
+        new api.Private(qualifier)
+    }
+  }
+
+  def apiModifiers(sym: Symbol): api.Modifiers = {
+    val absOver = sym.is(AbsOverride)
+    val abs = sym.is(Abstract) || sym.is(Deferred) || absOver
+    val over = sym.is(Override) || absOver
+    new api.Modifiers(abs, over, sym.is(Final), sym.is(Sealed),
+      sym.is(Implicit), sym.is(Lazy), sym.is(Macro), sym.is(SuperAccessor))
+  }
+
+  // TODO: Annotation support
+  def apiAnnotations(s: Symbol): List[api.Annotation] = Nil
+}
diff --git a/src/dotty/tools/dotc/sbt/ExtractDependencies.scala b/src/dotty/tools/dotc/sbt/ExtractDependencies.scala
new file mode 100644
index 000000000..181d6a2d7
--- /dev/null
+++ b/src/dotty/tools/dotc/sbt/ExtractDependencies.scala
@@ -0,0 +1,265 @@
+package dotty.tools.dotc
+package sbt
+
+import ast.{Trees, tpd}
+import core._, core.Decorators._
+import Contexts._, Flags._, Phases._, Trees._, Types._, Symbols._
+import Names._, NameOps._, StdNames._
+
+import scala.collection.{Set, mutable}
+
+import dotty.tools.io.{AbstractFile, Path, PlainFile, ZipArchive}
+import java.io.File
+
+import java.util.{Arrays, Comparator}
+
+import xsbti.DependencyContext
+
+/** This phase sends information on classes' dependencies to sbt via callbacks.
+ *
+ *  This is used by sbt for incremental recompilation. Briefly, when a file
+ *  changes sbt will recompile it, if its API has changed (determined by what
+ *  `ExtractAPI` sent) then sbt will determine which reverse-dependencies
+ *  (determined by what `ExtractDependencies` sent) of the API have to be
+ *  recompiled depending on what changed.
+ *
+ *  See the documentation of `ExtractDependenciesCollector`, `ExtractAPI`,
+ *  `ExtractAPICollector` and
+ *  http://www.scala-sbt.org/0.13/docs/Understanding-Recompilation.html for more
+ *  information on how sbt incremental compilation works.
+ *
+ *  The following flags affect this phase:
+ *   -Yforce-sbt-phases
+ *   -Ydump-sbt-inc
+ *
+ *  @see ExtractAPI
+ */
+class ExtractDependencies extends Phase {
+  override def phaseName: String = "sbt-deps"
+
+  // This phase should be run directly after `Frontend`, if it is run after
+  // `PostTyper`, some dependencies will be lost because trees get simplified.
+  // See the scripted test `constants` for an example where this matters.
+  // TODO: Add a `Phase#runsBefore` method ?
+
+  override def run(implicit ctx: Context): Unit = {
+    val unit = ctx.compilationUnit
+    val dumpInc = ctx.settings.YdumpSbtInc.value
+    val forceRun = dumpInc || ctx.settings.YforceSbtPhases.value
+    if ((ctx.sbtCallback != null || forceRun) && !unit.isJava) {
+      val sourceFile = unit.source.file.file
+      val extractDeps = new ExtractDependenciesCollector
+      extractDeps.traverse(unit.tpdTree)
+
+      if (dumpInc) {
+        val names = extractDeps.usedNames.map(_.toString).toArray[Object]
+        val deps = extractDeps.topLevelDependencies.map(_.toString).toArray[Object]
+        val inhDeps = extractDeps.topLevelInheritanceDependencies.map(_.toString).toArray[Object]
+        Arrays.sort(names)
+        Arrays.sort(deps)
+        Arrays.sort(inhDeps)
+
+        val pw = Path(sourceFile).changeExtension("inc").toFile.printWriter()
+        try {
+          pw.println(s"// usedNames: ${names.mkString(",")}")
+          pw.println(s"// topLevelDependencies: ${deps.mkString(",")}")
+          pw.println(s"// topLevelInheritanceDependencies: ${inhDeps.mkString(",")}")
+        } finally pw.close()
+      }
+
+      if (ctx.sbtCallback != null) {
+        extractDeps.usedNames.foreach(name =>
+          ctx.sbtCallback.usedName(sourceFile, name.toString))
+        extractDeps.topLevelDependencies.foreach(dep =>
+          recordDependency(sourceFile, dep, DependencyContext.DependencyByMemberRef))
+        extractDeps.topLevelInheritanceDependencies.foreach(dep =>
+          recordDependency(sourceFile, dep, DependencyContext.DependencyByInheritance))
+      }
+    }
+  }
+
+  /** Record that `currentSourceFile` depends on the file where `dep` was loaded from.
+   *
+   *  @param currentSourceFile  The source file of the current unit
+   *  @param dep                The dependency
+   *  @param context            Describes how `currentSourceFile` depends on `dep`
+   */
+  def recordDependency(currentSourceFile: File, dep: Symbol, context: DependencyContext)
+      (implicit ctx: Context) = {
+    val depFile = dep.associatedFile
+    if (depFile != null) {
+      if (depFile.path.endsWith(".class")) {
+        /** Transform `List(java, lang, String.class)` into `java.lang.String` */
+        def className(classSegments: List[String]) =
+          classSegments.mkString(".").stripSuffix(".class")
+        def binaryDependency(file: File, className: String) =
+          ctx.sbtCallback.binaryDependency(file, className, currentSourceFile, context)
+
+        depFile match {
+          case ze: ZipArchive#Entry =>
+            for (zip <- ze.underlyingSource; zipFile <- Option(zip.file)) {
+              val classSegments = Path(ze.path).segments
+              binaryDependency(zipFile, className(classSegments))
+            }
+          case pf: PlainFile =>
+            val packages = dep.ownersIterator
+              .filter(x => x.is(PackageClass) && !x.isEffectiveRoot).length
+            // We can recover the fully qualified name of a classfile from
+            // its path
+            val classSegments = pf.givenPath.segments.takeRight(packages + 1)
+            binaryDependency(pf.file, className(classSegments))
+          case _ =>
+        }
+      } else if (depFile.file != currentSourceFile) {
+        ctx.sbtCallback.sourceDependency(depFile.file, currentSourceFile, context)
+      }
+    }
+  }
+}
+
+/** Extract the dependency information of a compilation unit.
+ *
+ *  To understand why we track the used names see the section "Name hashing
+ *  algorithm" in http://www.scala-sbt.org/0.13/docs/Understanding-Recompilation.html
+ *  To understand why we need to track dependencies introduced by inheritance
+ *  specially, see the subsection "Dependencies introduced by member reference and
+ *  inheritance" in the "Name hashing algorithm" section.
+ */
+private class ExtractDependenciesCollector(implicit val ctx: Context) extends tpd.TreeTraverser {
+  import tpd._
+
+  private[this] val _usedNames = new mutable.HashSet[Name]
+  private[this] val _topLevelDependencies = new mutable.HashSet[Symbol]
+  private[this] val _topLevelInheritanceDependencies = new mutable.HashSet[Symbol]
+
+  /** The names used in this class, this does not include names which are only
+   *  defined and not referenced.
+   */
+  def usedNames: Set[Name] = _usedNames
+
+  /** The set of top-level classes that the compilation unit depends on
+   *  because it refers to these classes or something defined in them.
+   *  This is always a superset of `topLevelInheritanceDependencies` by definition.
+   */
+  def topLevelDependencies: Set[Symbol] = _topLevelDependencies
+
+  /** The set of top-level classes that the compilation unit extends or that
+   *  contain a non-top-level class that the compilaion unit extends.
+   */
+  def topLevelInheritanceDependencies: Set[Symbol] = _topLevelInheritanceDependencies
+
+  private def addUsedName(name: Name) =
+    _usedNames += name
+
+  private def addDependency(sym: Symbol): Unit =
+    if (!ignoreDependency(sym)) {
+      val tlClass = sym.topLevelClass
+      if (tlClass.ne(NoSymbol)) // Some synthetic type aliases like AnyRef do not belong to any class
+        _topLevelDependencies += sym.topLevelClass
+      addUsedName(sym.name)
+    }
+
+  private def ignoreDependency(sym: Symbol) =
+    sym.eq(NoSymbol) ||
+    sym.isEffectiveRoot ||
+    sym.isAnonymousFunction ||
+    sym.isAnonymousClass ||
+    sym.isLambdaTrait
+
+  private def addInheritanceDependency(sym: Symbol): Unit =
+    _topLevelInheritanceDependencies += sym.topLevelClass
+
+  /** Traverse the tree of a source file and record the dependencies which
+   *  can be retrieved using `topLevelDependencies`, `topLevelInheritanceDependencies`,
+   *  and `usedNames`
+   */
+  override def traverse(tree: Tree)(implicit ctx: Context): Unit = {
+    tree match {
+      case Import(expr, selectors) =>
+        def lookupImported(name: Name) = expr.tpe.member(name).symbol
+        def addImported(name: Name) = {
+          // importing a name means importing both a term and a type (if they exist)
+          addDependency(lookupImported(name.toTermName))
+          addDependency(lookupImported(name.toTypeName))
+        }
+        selectors foreach {
+          case Ident(name) =>
+            addImported(name)
+           case Pair(Ident(name), Ident(rename)) =>
+            addImported(name)
+            if (rename ne nme.WILDCARD)
+              addUsedName(rename)
+          case _ =>
+        }
+      case t: TypeTree =>
+        usedTypeTraverser.traverse(t.tpe)
+      case ref: RefTree =>
+        addDependency(ref.symbol)
+        usedTypeTraverser.traverse(ref.tpe)
+      case t @ Template(_, parents, _, _) =>
+        t.parents.foreach(p => addInheritanceDependency(p.tpe.typeSymbol))
+      case _ =>
+    }
+    traverseChildren(tree)
+  }
+
+  /** Traverse a used type and record all the dependencies we need to keep track
+   *  of for incremental recompilation.
+   *
+   *  As a motivating example, given a type `T` defined as:
+   *
+   *    type T >: L <: H
+   *    type L <: A1
+   *    type H <: B1
+   *    class A1 extends A0
+   *    class B1 extends B0
+   *
+   *  We need to record a dependency on `T`, `L`, `H`, `A1`, `B1`. This is
+   *  necessary because the API representation that `ExtractAPI` produces for
+   *  `T` just refers to the strings "L" and "H", it does not contain their API
+   *  representation. Therefore, the name hash of `T` does not change if for
+   *  example the definition of `L` changes.
+   *
+   *  We do not need to keep track of superclasses like `A0` and `B0` because
+   *  the API representation of a class (and therefore its name hash) already
+   *  contains all necessary information on superclasses.
+   *
+   *  A natural question to ask is: Since traversing all referenced types to
+   *  find all these names is costly, why not change the API representation
+   *  produced by `ExtractAPI` to contain that information? This way the name
+   *  hash of `T` would change if any of the types it depends on change, and we
+   *  would only need to record a dependency on `T`. Unfortunately there is no
+   *  simple answer to the question "what does T depend on?" because it depends
+   *  on the prefix and `ExtractAPI` does not compute types as seen from every
+   *  possible prefix, the documentation of `ExtractAPI` explains why.
+   *
+   *  The tests in sbt `types-in-used-names-a`, `types-in-used-names-b`,
+   *  `as-seen-from-a` and `as-seen-from-b` rely on this.
+   */
+  private object usedTypeTraverser extends TypeTraverser {
+    val seen = new mutable.HashSet[Type]
+    def traverse(tp: Type): Unit = if (!seen.contains(tp)) {
+      seen += tp
+      tp match {
+        case tp: NamedType =>
+          val sym = tp.symbol
+          if (!sym.is(Package)) {
+            addDependency(sym)
+            if (!sym.isClass)
+              traverse(tp.info)
+            traverse(tp.prefix)
+          }
+        case tp: ThisType =>
+          traverse(tp.underlying)
+        case tp: ConstantType =>
+          traverse(tp.underlying)
+        case tp: MethodParam =>
+          traverse(tp.underlying)
+        case tp: PolyParam =>
+          traverse(tp.underlying)
+        case _ =>
+          traverseChildren(tp)
+      }
+    }
+  }
+}
diff --git a/src/dotty/tools/dotc/sbt/ShowAPI.scala b/src/dotty/tools/dotc/sbt/ShowAPI.scala
new file mode 100644
index 000000000..0e6b19867
--- /dev/null
+++ b/src/dotty/tools/dotc/sbt/ShowAPI.scala
@@ -0,0 +1,156 @@
+// This file is copied straight from
+// https://github.com/sbt/sbt/blob/0.13/compile/api/src/main/scala/xsbt/api/ShowAPI.scala
+// It is convenient to be able to pretty-print the API from Dotty itself to test
+// the sbt phase without having to run sbt.
+
+/* sbt -- Simple Build Tool
+ * Copyright 2010 Mark Harrah
+ */
+package dotty.tools.dotc
+package sbt
+
+import xsbti.api._
+
+import scala.util.Try
+
+object DefaultShowAPI {
+  private lazy val defaultNesting = Try { java.lang.Integer.parseInt(sys.props.get("sbt.inc.apidiff.depth").get) } getOrElse 2
+
+  def apply(d: Definition) = ShowAPI.showDefinition(d)(defaultNesting)
+  def apply(d: Type) = ShowAPI.showType(d)(defaultNesting)
+  def apply(a: SourceAPI) = ShowAPI.showApi(a)(defaultNesting)
+}
+
+object ShowAPI {
+  private lazy val numDecls = Try { java.lang.Integer.parseInt(sys.props.get("sbt.inc.apidiff.decls").get) } getOrElse 0
+
+  private def truncateDecls(decls: Array[Definition]): Array[Definition] = if (numDecls <= 0) decls else decls.take(numDecls)
+  private def lines(ls: Seq[String]): String = ls.mkString("\n", "\n", "\n")
+
+  def showApi(a: SourceAPI)(implicit nesting: Int) =
+    a.packages.map(pkg => "package " + pkg.name).mkString("\n") + lines(truncateDecls(a.definitions).map(showDefinition))
+
+  def showDefinition(d: Definition)(implicit nesting: Int): String = d match {
+    case v: Val              => showMonoDef(v, "val") + ": " + showType(v.tpe)
+    case v: Var              => showMonoDef(v, "var") + ": " + showType(v.tpe)
+    case d: Def              => showPolyDef(d, "def") + showValueParams(d.valueParameters) + ": " + showType(d.returnType)
+    case ta: TypeAlias       => showPolyDef(ta, "type") + " = " + showType(ta.tpe)
+    case td: TypeDeclaration => showPolyDef(td, "type") + showBounds(td.lowerBound, td.upperBound)
+    case cl: ClassLike       => showPolyDef(cl, showDefinitionType(cl.definitionType)) + " extends " + showTemplate(cl)
+  }
+
+  private def showTemplate(cl: ClassLike)(implicit nesting: Int) =
+    if (nesting <= 0) "<nesting level reached>"
+    else {
+      val showSelf = if (cl.selfType.isInstanceOf[EmptyType]) "" else " self: " + showNestedType(cl.selfType) + " =>"
+
+      cl.structure.parents.map(showNestedType).mkString("", " with ", " {") + showSelf +
+        lines(truncateDecls(cl.structure.inherited).map(d => "^inherited^ " + showNestedDefinition(d))) +
+        lines(truncateDecls(cl.structure.declared).map(showNestedDefinition)) +
+        "}"
+    }
+
+  def showType(t: Type)(implicit nesting: Int): String = t match {
+    case st: Projection   => showType(st.prefix) + "#" + st.id
+    case st: ParameterRef => "<" + st.id + ">"
+    case st: Singleton    => showPath(st.path)
+    case st: EmptyType    => "<empty>"
+    case p: Parameterized => showType(p.baseType) + p.typeArguments.map(showType).mkString("[", ", ", "]")
+    case c: Constant      => showType(c.baseType) + "(" + c.value + ")"
+    case a: Annotated     => showAnnotations(a.annotations) + " " + showType(a.baseType)
+    case s: Structure =>
+      s.parents.map(showType).mkString(" with ") + (
+        if (nesting <= 0) "{ <nesting level reached> }"
+        else truncateDecls(s.declared).map(showNestedDefinition).mkString(" {", "\n", "}"))
+    case e: Existential =>
+      showType(e.baseType) + (
+        if (nesting <= 0) " forSome { <nesting level reached> }"
+        else e.clause.map(t => "type " + showNestedTypeParameter(t)).mkString(" forSome { ", "; ", " }"))
+    case p: Polymorphic => showType(p.baseType) + (
+      if (nesting <= 0) " [ <nesting level reached> ]"
+      else showNestedTypeParameters(p.parameters))
+  }
+
+  private def showPath(p: Path): String = p.components.map(showPathComponent).mkString(".")
+  private def showPathComponent(pc: PathComponent) = pc match {
+    case s: Super => "super[" + showPath(s.qualifier) + "]"
+    case _: This  => "this"
+    case i: Id    => i.id
+  }
+
+  private def space(s: String) = if (s.isEmpty) s else s + " "
+  private def showMonoDef(d: Definition, label: String)(implicit nesting: Int): String =
+    space(showAnnotations(d.annotations)) + space(showAccess(d.access)) + space(showModifiers(d.modifiers)) + space(label) + d.name
+
+  private def showPolyDef(d: ParameterizedDefinition, label: String)(implicit nesting: Int): String =
+    showMonoDef(d, label) + showTypeParameters(d.typeParameters)
+
+  private def showTypeParameters(tps: Seq[TypeParameter])(implicit nesting: Int): String =
+    if (tps.isEmpty) ""
+    else tps.map(showTypeParameter).mkString("[", ", ", "]")
+
+  private def showTypeParameter(tp: TypeParameter)(implicit nesting: Int): String =
+    showAnnotations(tp.annotations) + " " + showVariance(tp.variance) + tp.id + showTypeParameters(tp.typeParameters) + " " + showBounds(tp.lowerBound, tp.upperBound)
+
+  private def showAnnotations(as: Seq[Annotation])(implicit nesting: Int) = as.map(showAnnotation).mkString(" ")
+  private def showAnnotation(a: Annotation)(implicit nesting: Int) =
+    "@" + showType(a.base) + (
+      if (a.arguments.isEmpty) ""
+      else a.arguments.map(a => a.name + " = " + a.value).mkString("(", ", ", ")")
+    )
+
+  private def showBounds(lower: Type, upper: Type)(implicit nesting: Int): String = ">: " + showType(lower) + " <: " + showType(upper)
+
+  private def showValueParams(ps: Seq[ParameterList])(implicit nesting: Int): String =
+    ps.map(pl =>
+      pl.parameters.map(mp =>
+        mp.name + ": " + showParameterModifier(showType(mp.tpe), mp.modifier) + (if (mp.hasDefault) "= ..." else "")
+      ).mkString(if (pl.isImplicit) "(implicit " else "(", ", ", ")")
+    ).mkString("")
+
+  private def showParameterModifier(base: String, pm: ParameterModifier): String = pm match {
+    case ParameterModifier.Plain    => base
+    case ParameterModifier.Repeated => base + "*"
+    case ParameterModifier.ByName   => "=> " + base
+  }
+
+  private def showDefinitionType(d: DefinitionType) = d match {
+    case DefinitionType.Trait         => "trait"
+    case DefinitionType.ClassDef      => "class"
+    case DefinitionType.Module        => "object"
+    case DefinitionType.PackageModule => "package object"
+  }
+
+  private def showAccess(a: Access) = a match {
+    case p: Public    => ""
+    case p: Protected => "protected" + showQualifier(p.qualifier)
+    case p: Private   => "private" + showQualifier(p.qualifier)
+  }
+
+  private def showQualifier(q: Qualifier) = q match {
+    case _: Unqualified   => ""
+    case _: ThisQualifier => "[this]"
+    case i: IdQualifier   => "[" + i.value + "]"
+  }
+
+  private def showModifiers(m: Modifiers) = List(
+    (m.isOverride, "override"),
+    (m.isFinal, "final"),
+    (m.isSealed, "sealed"),
+    (m.isImplicit, "implicit"),
+    (m.isAbstract, "abstract"),
+    (m.isLazy, "lazy")
+  ).collect { case (true, mod) => mod }.mkString(" ")
+
+  private def showVariance(v: Variance) = v match {
+    case Variance.Invariant     => ""
+    case Variance.Covariant     => "+"
+    case Variance.Contravariant => "-"
+  }
+
+  // limit nesting to prevent cycles and generally keep output from getting humongous
+  private def showNestedType(tp: Type)(implicit nesting: Int) = showType(tp)(nesting - 1)
+  private def showNestedTypeParameter(tp: TypeParameter)(implicit nesting: Int) = showTypeParameter(tp)(nesting - 1)
+  private def showNestedTypeParameters(tps: Seq[TypeParameter])(implicit nesting: Int) = showTypeParameters(tps)(nesting - 1)
+  private def showNestedDefinition(d: Definition)(implicit nesting: Int) = showDefinition(d)(nesting - 1)
+}
diff --git a/src/dotty/tools/dotc/sbt/ThunkHolder.scala b/src/dotty/tools/dotc/sbt/ThunkHolder.scala
new file mode 100644
index 000000000..e377de6da
--- /dev/null
+++ b/src/dotty/tools/dotc/sbt/ThunkHolder.scala
@@ -0,0 +1,61 @@
+package dotty.tools.dotc
+package sbt
+
+import scala.annotation.tailrec
+import scala.collection.mutable.ListBuffer
+import xsbti.api
+
+/** Create and hold thunks. A thunk is a (potentially) unevaluated value
+ *  that may be evaluated once.
+ */
+private[sbt] trait ThunkHolder {
+  private[this] val thunks = new ListBuffer[api.Lazy[_]]
+
+  /** Force all unevaluated thunks to prevent space leaks. */
+  @tailrec protected final def forceThunks(): Unit = if (!thunks.isEmpty) {
+    val toForce = thunks.toList
+    thunks.clear()
+    toForce.foreach(_.get())
+    // Forcing thunks may create new thunks
+    forceThunks()
+  }
+
+  /** Store the by-name parameter `s` in a `Lazy` container without evaluating it.
+   *  It will be forced by the next call to `forceThunks()`
+   */
+  def lzy[T <: AnyRef](t: => T): api.Lazy[T] = {
+    val l = SafeLazy(() => t)
+    thunks += l
+    l
+  }
+
+  /** Store the parameter `s` in a `Lazy` container, since `s` is not by-name, there
+   *  is nothing to force.
+   *
+   *  TODO: Get rid of this method. It is only needed because some xsbti.api classes
+   *  take lazy arguments when they could be strict, but this can be fixed in sbt,
+   *  see https://github.com/sbt/zinc/issues/114
+   */
+  def strict2lzy[T <: AnyRef](t: T): api.Lazy[T] =
+    SafeLazy.strict(t)
+}
+
+// TODO: Use xsbti.SafeLazy once https://github.com/sbt/zinc/issues/113 is fixed
+private object SafeLazy {
+  def apply[T <: AnyRef](eval: () => T): xsbti.api.Lazy[T] =
+    new Impl(eval)
+
+  def strict[T <: AnyRef](value: T): xsbti.api.Lazy[T] =
+    new Strict(value)
+
+  private[this] final class Impl[T <: AnyRef](private[this] var eval: () => T) extends xsbti.api.AbstractLazy[T] {
+    private[this] lazy val _t = {
+      val t = eval()
+      eval = null // clear the reference, ensuring the only memory we hold onto is the result
+      t
+    }
+    def get: T = _t
+  }
+
+  private[this] final class Strict[T <: AnyRef](val get: T) extends xsbti.api.Lazy[T] with java.io.Serializable
+}