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`) ?

1 files changed, 265 insertions, 0 deletions

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)
+      }
+    }
+  }
+}