Move compiler and compiler tests to compiler dir

4 files changed, 1003 insertions, 0 deletions

diff --git a/compiler/src/dotty/tools/dotc/sbt/ExtractAPI.scala b/compiler/src/dotty/tools/dotc/sbt/ExtractAPI.scala
new file mode 100644
index 000000000..bc8528c05
--- /dev/null
+++ b/compiler/src/dotty/tools/dotc/sbt/ExtractAPI.scala
@@ -0,0 +1,518 @@
+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 typer.Inliner
+
+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(apiTypeParameter)
+
+    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 pt: PolyType =>
+        assert(start == 0)
+        paramLists(pt.resultType)
+      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 PolyType(tparams, res) =>
+        val apiTparams = tparams.map(apiTypeParameter)
+        val apiRes = apiType(res)
+        new api.Polymorphic(apiRes, apiTparams.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: RecType =>
+        apiType(tp.parent)
+      case RecThis(recType) =>
+        // `tp` must be present inside `recType`, so calling `apiType` on
+        // `recType` would lead to an infinite recursion, we avoid this by
+        //  computing the representation of `recType` lazily.
+        apiLazy(recType)
+      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 tp: ParamType =>
+        // TODO: Distinguishing parameters based on their names alone is not enough,
+        // the binder is also needed (at least for type lambdas).
+        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 apiLazy(tp: => Type): api.Type = {
+    // TODO: The sbt api needs a convenient way to make a lazy type.
+    // For now, we repurpose Structure for this.
+    val apiTp = lzy(Array(apiType(tp)))
+    new api.Structure(apiTp, strict2lzy(Array()), strict2lzy(Array()))
+  }
+
+  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(tparam: TypeParamInfo): api.TypeParameter =
+    apiTypeParameter(tparam.paramName.toString, tparam.paramVariance,
+      tparam.paramBounds.lo, tparam.paramBounds.hi)
+
+  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: Support other annotations
+  def apiAnnotations(s: Symbol): List[api.Annotation] = {
+    val annots = new mutable.ListBuffer[api.Annotation]
+
+    if (Inliner.hasBodyToInline(s)) {
+      // FIXME: If the body of an inline method changes, all the reverse
+      // dependencies of this method need to be recompiled. sbt has no way
+      // of tracking method bodies, so as a hack we include the pretty-printed
+      // typed tree of the method as part of the signature we send to sbt.
+      // To do this properly we would need a way to hash trees and types in
+      // dotty itself.
+      val printTypesCtx = ctx.fresh.setSetting(ctx.settings.printtypes, true)
+      annots += marker(Inliner.bodyToInline(s).show(printTypesCtx).toString)
+    }
+
+    annots.toList
+  }
+}
diff --git a/compiler/src/dotty/tools/dotc/sbt/ExtractDependencies.scala b/compiler/src/dotty/tools/dotc/sbt/ExtractDependencies.scala
new file mode 100644
index 000000000..229e35360
--- /dev/null
+++ b/compiler/src/dotty/tools/dotc/sbt/ExtractDependencies.scala
@@ -0,0 +1,268 @@
+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
+
+  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 Thicket(Ident(name) :: Ident(rename) :: Nil) =>
+            addImported(name)
+            if (rename ne nme.WILDCARD)
+              addUsedName(rename)
+          case _ =>
+        }
+      case Inlined(call, _, _) =>
+        // The inlined call is normally ignored by TreeTraverser but we need to
+        // record it as a dependency
+        traverse(call)
+      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/compiler/src/dotty/tools/dotc/sbt/ShowAPI.scala b/compiler/src/dotty/tools/dotc/sbt/ShowAPI.scala
new file mode 100644
index 000000000..0e6b19867
--- /dev/null
+++ b/compiler/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/compiler/src/dotty/tools/dotc/sbt/ThunkHolder.scala b/compiler/src/dotty/tools/dotc/sbt/ThunkHolder.scala
new file mode 100644
index 000000000..e377de6da
--- /dev/null
+++ b/compiler/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
+}