Add a `visualize` command to render portions of the build graph as SVG (#349)

* Transitive reduction of visualized graph via jgrapht now works

```
out/dev/launcher/dest/run -i visualize __.compile _
out/dev/launcher/dest/run -i visualize core.__
```

* Move test running logic from scalaworker into scalalib

This is to try and reduce the size of the classpath we are passing to the test runner subprocess, in an attempt to fix the command-line-too-long errors we're getting in Appveyor. Now the test runner subprocess should no longer need Zinc or all of it's transitive dependencies

* - Break out `GraphvizTools` into a separate Mill module, to avoid bloating the main jar and try to shorten the `MILL_SCALA_WORKER` classpath being sent to scalajslib.test (which is blowing up on windows as the CLI command is too long)

- Move the meat of `resolveDependencies` from `scalalib` to `main`, to support resolving mill modules

- DRY up resolution of mill modules in `Util.millProjectModule`

* fix mill module resolution

* Tweaks to try and make zinc work again...

* Tweak `Module#reflect` to try and make it happy with `visualize` module...

* fix integration test classpath

* move visualization into it's own module

7 files changed, 271 insertions, 35 deletions

diff --git a/main/graphviz/src/mill/main/graphviz/GraphvizTools.scala b/main/graphviz/src/mill/main/graphviz/GraphvizTools.scala
new file mode 100644
index 00000000..300bd98a
--- /dev/null
+++ b/main/graphviz/src/mill/main/graphviz/GraphvizTools.scala
@@ -0,0 +1,66 @@
+package mill.main.graphviz
+import ammonite.ops.Path
+import mill.define.{Graph, NamedTask}
+import org.jgrapht.graph.{DefaultEdge, SimpleDirectedGraph}
+object GraphvizTools{
+  def apply(rs: Seq[NamedTask[Any]], dest: Path) = {
+    val transitive = Graph.transitiveTargets(rs.distinct)
+    val topoSorted = Graph.topoSorted(transitive)
+    val goalSet = rs.toSet
+    val sortedGroups = Graph.groupAroundImportantTargets(topoSorted){
+      case x: NamedTask[Any] if goalSet.contains(x) => x
+    }
+    import guru.nidi.graphviz.model.Factory._
+    import guru.nidi.graphviz.engine.{Format, Graphviz}
+
+    val edgesIterator =
+      for((k, vs) <- sortedGroups.items())
+        yield (
+          k,
+          for {
+            v <- vs.items
+            dest <- v.inputs.collect { case v: NamedTask[Any] => v }
+            if goalSet.contains(dest)
+          } yield dest
+        )
+
+    val edges = edgesIterator.map{case (k, v) => (k, v.toArray.distinct)}.toArray
+
+    val indexToTask = edges.flatMap{case (k, vs) => Iterator(k) ++ vs}.distinct
+    val taskToIndex = indexToTask.zipWithIndex.toMap
+
+    val jgraph = new SimpleDirectedGraph[Int, DefaultEdge](classOf[DefaultEdge])
+
+    for(i <- indexToTask.indices) jgraph.addVertex(i)
+    for((src, dests) <- edges; dest <- dests) {
+      jgraph.addEdge(taskToIndex(src), taskToIndex(dest))
+    }
+
+
+    org.jgrapht.alg.TransitiveReduction.INSTANCE.reduce(jgraph)
+    val nodes = indexToTask.map(t => node(t.ctx.segments.render))
+
+    var g = graph("example1").directed
+    for(i <- indexToTask.indices){
+      val outgoing = for{
+        e <- edges(i)._2
+        j = taskToIndex(e)
+        if jgraph.containsEdge(i, j)
+      } yield nodes(j)
+      g = g.`with`(nodes(i).link(outgoing:_*))
+    }
+
+    val gv = Graphviz.fromGraph(g).totalMemory(100 * 1000 * 1000)
+    val outputs = Seq(
+      Format.PLAIN -> "out.txt",
+      Format.XDOT -> "out.dot",
+      Format.JSON -> "out.json",
+      Format.PNG -> "out.png",
+      Format.SVG -> "out.svg"
+    )
+    for((fmt, name) <- outputs) {
+      gv.render(fmt).toFile((dest / name).toIO)
+    }
+    outputs.map(x => mill.PathRef(dest / x._2))
+  }
+}
\ No newline at end of file
diff --git a/main/src/mill/main/MainModule.scala b/main/src/mill/main/MainModule.scala
index 4fed5ec5..c7efbd21 100644
--- a/main/src/mill/main/MainModule.scala
+++ b/main/src/mill/main/MainModule.scala
@@ -1,12 +1,15 @@
 package mill.main
 
 import ammonite.ops.Path
-import mill.define.{NamedTask, Task}
-import mill.eval.{Evaluator, Result}
-import mill.util.{PrintLogger, Watched}
+import coursier.Cache
+import coursier.maven.MavenRepository
+import mill.T
+import mill.define.{Graph, NamedTask, Task}
+import mill.eval.{Evaluator, PathRef, Result}
+import mill.util.{Loose, PrintLogger, Watched}
 import pprint.{Renderer, Truncated}
 import upickle.Js
-
+import mill.util.JsonFormatters._
 object MainModule{
   def resolveTasks[T](evaluator: Evaluator[Any], targets: Seq[String], multiSelect: Boolean)
                      (f: List[NamedTask[Any]] => T) = {
@@ -217,4 +220,12 @@ trait MainModule extends mill.Module{
     }
   }
 
+  val visualize: VisualizeModule = new VisualizeModule {
+    def repositories = Seq(
+      Cache.ivy2Local,
+      MavenRepository("https://repo1.maven.org/maven2"),
+      MavenRepository("https://oss.sonatype.org/content/repositories/releases")
+    )
+  }
+
 }
diff --git a/main/src/mill/main/Resolve.scala b/main/src/mill/main/Resolve.scala
index 4b0ae27f..4baac312 100644
--- a/main/src/mill/main/Resolve.scala
+++ b/main/src/mill/main/Resolve.scala
@@ -188,28 +188,37 @@ object ResolveTasks extends Resolve[NamedTask[Any]]{
                       revSelectorsSoFar: List[Segment],
                       last: String,
                       discover: Discover[_],
-                      rest: Seq[String]) = {
-    val target =
-      obj
-        .millInternal
-        .reflect[Target[_]]
-        .find(_.label == last)
-        .map(Right(_))
-
-    val command = Resolve.invokeCommand(obj, last, discover, rest).headOption
-
-    command orElse target orElse Resolve.runDefault(obj, Segment.Label(last), discover, rest).flatten.headOption match {
-      case None =>
-        Resolve.errorMsgLabel(
-          singleModuleMeta(obj, discover, revSelectorsSoFar.isEmpty),
-          last,
-          revSelectorsSoFar
-        )
-
-      // Contents of `either` *must* be a `Task`, because we only select
-      // methods returning `Task` in the discovery process
-      case Some(either) => either.right.map(Seq(_))
-    }
+                      rest: Seq[String]) = last match{
+    case "__" =>
+      Right(
+        obj.millInternal.modules
+          .filter(_ != obj)
+          .flatMap(m => m.millInternal.reflect[Target[_]])
+      )
+    case "_" => Right(obj.millInternal.reflect[Target[_]])
+
+    case _ =>
+      val target =
+        obj
+          .millInternal
+          .reflect[Target[_]]
+          .find(_.label == last)
+          .map(Right(_))
+
+      val command = Resolve.invokeCommand(obj, last, discover, rest).headOption
+
+      command orElse target orElse Resolve.runDefault(obj, Segment.Label(last), discover, rest).flatten.headOption match {
+        case None =>
+          Resolve.errorMsgLabel(
+            singleModuleMeta(obj, discover, revSelectorsSoFar.isEmpty),
+            last,
+            revSelectorsSoFar
+          )
+
+        // Contents of `either` *must* be a `Task`, because we only select
+        // methods returning `Task` in the discovery process
+        case Some(either) => either.right.map(Seq(_))
+      }
   }
 }
 object Resolve{
diff --git a/main/src/mill/main/VisualizeModule.scala b/main/src/mill/main/VisualizeModule.scala
new file mode 100644
index 00000000..00651a8e
--- /dev/null
+++ b/main/src/mill/main/VisualizeModule.scala
@@ -0,0 +1,37 @@
+package mill.main
+
+import ammonite.ops.Path
+import coursier.core.Repository
+import mill.T
+import mill.eval.{Evaluator, PathRef, Result}
+
+trait VisualizeModule extends mill.define.TaskModule{
+  def repositories: Seq[Repository]
+  def defaultCommandName() = "run"
+  def classpath = T{
+    mill.modules.Util.millProjectModule("MILL_GRAPHVIZ", "mill-main-graphviz", repositories)
+  }
+  /**
+    * Given a set of tasks, prints out the execution plan of what tasks will be
+    * executed in what order, without actually executing them.
+    */
+  def run(evaluator: Evaluator[Any], targets: String*) = mill.T.command{
+    val resolved = RunScript.resolveTasks(
+      mill.main.ResolveTasks, evaluator, targets, multiSelect = true
+    )
+    resolved match{
+      case Left(err) => Result.Failure(err)
+      case Right(rs) =>
+        Result.Success(
+          mill.modules.Jvm.inprocess(classpath().map(_.path), false, isolated = false, cl => {
+            cl.loadClass("mill.main.graphviz.GraphvizTools")
+              .getMethod("apply", classOf[Seq[_]], classOf[Path])
+              .invoke(null, rs, T.ctx().dest)
+              .asInstanceOf[Seq[PathRef]]
+          })
+        )
+
+    }
+  }
+
+}
diff --git a/main/src/mill/modules/Jvm.scala b/main/src/mill/modules/Jvm.scala
index d32d3612..1a28189f 100644
--- a/main/src/mill/modules/Jvm.scala
+++ b/main/src/mill/modules/Jvm.scala
@@ -8,9 +8,11 @@ import java.nio.file.attribute.PosixFilePermission
 import java.util.jar.{JarEntry, JarFile, JarOutputStream}
 
 import ammonite.ops._
+import ammonite.util.Util
+import coursier.{Cache, Dependency, Fetch, Repository, Resolution}
 import geny.Generator
 import mill.main.client.InputPumper
-import mill.eval.PathRef
+import mill.eval.{PathRef, Result}
 import mill.util.{Ctx, IO}
 import mill.util.Loose.Agg
 
@@ -78,7 +80,7 @@ object Jvm {
                classPath: Agg[Path],
                mainArgs: Seq[String] = Seq.empty)
               (implicit ctx: Ctx): Unit = {
-    inprocess(classPath, classLoaderOverrideSbtTesting = false, cl => {
+    inprocess(classPath, classLoaderOverrideSbtTesting = false, isolated = true, cl => {
       getMainMethod(mainClass, cl).invoke(null, mainArgs.toArray)
     })
   }
@@ -101,6 +103,7 @@ object Jvm {
 
   def inprocess[T](classPath: Agg[Path],
                    classLoaderOverrideSbtTesting: Boolean,
+                   isolated: Boolean,
                    body: ClassLoader => T)
                   (implicit ctx: Ctx.Home): T = {
     val urls = classPath.map(_.toIO.toURI.toURL)
@@ -111,8 +114,11 @@ object Jvm {
           Some(outerClassLoader.loadClass(name))
         else None
       })
-    } else {
+    } else if (isolated){
+
       mill.util.ClassLoader.create(urls.toVector, null)
+    }else{
+      mill.util.ClassLoader.create(urls.toVector, getClass.getClassLoader)
     }
     val oldCl = Thread.currentThread().getContextClassLoader
     Thread.currentThread().setContextClassLoader(cl)
@@ -376,4 +382,87 @@ object Jvm {
     PathRef(outputPath)
   }
 
+  /**
+    * Resolve dependencies using Coursier.
+    *
+    * We do not bother breaking this out into the separate ScalaWorker classpath,
+    * because Coursier is already bundled with mill/Ammonite to support the
+    * `import $ivy` syntax.
+    */
+  def resolveDependencies(repositories: Seq[Repository],
+                          deps: TraversableOnce[coursier.Dependency],
+                          force: TraversableOnce[coursier.Dependency],
+                          sources: Boolean = false,
+                          mapDependencies: Option[Dependency => Dependency] = None): Result[Agg[PathRef]] = {
+
+    val (_, resolution) = resolveDependenciesMetadata(
+      repositories, deps, force, mapDependencies
+    )
+    val errs = resolution.metadataErrors
+    if(errs.nonEmpty) {
+      val header =
+        s"""|
+            |Resolution failed for ${errs.length} modules:
+            |--------------------------------------------
+            |""".stripMargin
+
+      val errLines = errs.map {
+        case ((module, vsn), errMsgs) => s"  ${module.trim}:$vsn \n\t" + errMsgs.mkString("\n\t")
+      }.mkString("\n")
+      val msg = header + errLines + "\n"
+      Result.Failure(msg)
+    } else {
+
+      def load(artifacts: Seq[coursier.Artifact]) = {
+        val logger = None
+        val loadedArtifacts = scalaz.concurrent.Task.gatherUnordered(
+          for (a <- artifacts)
+            yield coursier.Cache.file(a, logger = logger).run
+              .map(a.isOptional -> _)
+        ).unsafePerformSync
+
+        val errors = loadedArtifacts.collect {
+          case (false, scalaz.-\/(x)) => x
+          case (true, scalaz.-\/(x)) if !x.notFound => x
+        }
+        val successes = loadedArtifacts.collect { case (_, scalaz.\/-(x)) => x }
+        (errors, successes)
+      }
+
+      val sourceOrJar =
+        if (sources) resolution.classifiersArtifacts(Seq("sources"))
+        else resolution.artifacts(true)
+      val (errors, successes) = load(sourceOrJar)
+      if(errors.isEmpty){
+        mill.Agg.from(
+          successes.map(p => PathRef(Path(p), quick = true)).filter(_.path.ext == "jar")
+        )
+      }else{
+        val errorDetails = errors.map(e => s"${ammonite.util.Util.newLine}  ${e.describe}").mkString
+        Result.Failure("Failed to load source dependencies" + errorDetails)
+      }
+    }
+  }
+
+
+  def resolveDependenciesMetadata(repositories: Seq[Repository],
+                                  deps: TraversableOnce[coursier.Dependency],
+                                  force: TraversableOnce[coursier.Dependency],
+                                  mapDependencies: Option[Dependency => Dependency] = None) = {
+
+    val forceVersions = force
+      .map(mapDependencies.getOrElse(identity[Dependency](_)))
+      .map{d => d.module -> d.version}
+      .toMap
+
+    val start = Resolution(
+      deps.map(mapDependencies.getOrElse(identity[Dependency](_))).toSet,
+      forceVersions = forceVersions,
+      mapDependencies = mapDependencies
+    )
+
+    val fetch = Fetch.from(repositories, Cache.fetch())
+    val resolution = start.process.run(fetch).unsafePerformSync
+    (deps.toSeq, resolution)
+  }
 }
diff --git a/main/src/mill/modules/Util.scala b/main/src/mill/modules/Util.scala
index 3029411c..da7407d0 100644
--- a/main/src/mill/modules/Util.scala
+++ b/main/src/mill/modules/Util.scala
@@ -2,8 +2,9 @@ package mill.modules
 
 
 import ammonite.ops.{Path, RelPath, empty, mkdir, read}
+import coursier.Repository
 import mill.eval.PathRef
-import mill.util.{Ctx, IO}
+import mill.util.{Ctx, IO, Loose}
 
 object Util {
   def download(url: String, dest: RelPath = "download")(implicit ctx: Ctx.Dest) = {
@@ -54,4 +55,27 @@ object Util {
     })()
     PathRef(ctx.dest / dest)
   }
+
+  def millProjectModule(key: String,
+                        artifact: String,
+                        repositories: Seq[Repository],
+                        resolveFilter: Path => Boolean = _ => true) = {
+    val localPath = sys.props(key)
+    if (localPath != null) {
+      mill.eval.Result.Success(
+        Loose.Agg.from(localPath.split(',').map(p => PathRef(Path(p), quick = true)))
+      )
+    } else {
+      mill.modules.Jvm.resolveDependencies(
+        repositories,
+        Seq(
+          coursier.Dependency(
+            coursier.Module("com.lihaoyi", artifact + "_2.12"),
+            sys.props("MILL_VERSION")
+          )
+        ),
+        Nil
+      ).map(_.filter(x => resolveFilter(x.path)))
+    }
+  }
 }
diff --git a/main/test/src/mill/util/TestEvaluator.scala b/main/test/src/mill/util/TestEvaluator.scala
index 26e4b4b5..bcfcc9bf 100644
--- a/main/test/src/mill/util/TestEvaluator.scala
+++ b/main/test/src/mill/util/TestEvaluator.scala
@@ -24,11 +24,11 @@ class TestEvaluator[T <: TestUtil.BaseModule](module: T)
                                              tp: TestPath){
   val outPath =  TestUtil.getOutPath()
 
-  val logger = DummyLogger
-//  val logger = new PrintLogger(
-//    true,
-//    ammonite.util.Colors.Default, System.out, System.out, System.err, System.in
-// )
+//  val logger = DummyLogger
+  val logger = new PrintLogger(
+    true,
+    ammonite.util.Colors.Default, System.out, System.out, System.err, System.in
+ )
   val evaluator = new Evaluator(Ctx.defaultHome, outPath, TestEvaluator.externalOutPath, module, logger)
 
   def apply[T](t: Task[T]): Either[Result.Failing[T], (T, Int)] = {