Move graph algorithms on tasks into `define/Graph.scala`, and move `GraphTests.scala` into `define/` as well

4 files changed, 103 insertions, 94 deletions

diff --git a/core/src/main/scala/mill/define/Graph.scala b/core/src/main/scala/mill/define/Graph.scala
new file mode 100644
index 00000000..e7844691
--- /dev/null
+++ b/core/src/main/scala/mill/define/Graph.scala
@@ -0,0 +1,60 @@
+package mill.define
+
+import mill.eval.Tarjans
+import mill.util.{MultiBiMap, OSet}
+
+object Graph {
+  class TopoSorted private[Graph](val values: OSet[Task[_]])
+  def groupAroundImportantTargets[T](topoSortedTargets: TopoSorted)
+                                    (important: PartialFunction[Task[_], T]): MultiBiMap[T, Task[_]] = {
+
+    val output = new MultiBiMap.Mutable[T, Task[_]]()
+    for ((target, t) <- topoSortedTargets.values.flatMap(t => important.lift(t).map((t, _)))) {
+
+      val transitiveTargets = new OSet.Mutable[Task[_]]
+      def rec(t: Task[_]): Unit = {
+        if (transitiveTargets.contains(t)) () // do nothing
+        else if (important.isDefinedAt(t) && t != target) () // do nothing
+        else {
+          transitiveTargets.append(t)
+          t.inputs.foreach(rec)
+        }
+      }
+      rec(target)
+      output.addAll(t, topoSorted(transitiveTargets).values)
+    }
+    output
+  }
+
+  def transitiveTargets(sourceTargets: OSet[Task[_]]): OSet[Task[_]] = {
+    val transitiveTargets = new OSet.Mutable[Task[_]]
+    def rec(t: Task[_]): Unit = {
+      if (transitiveTargets.contains(t)) () // do nothing
+      else {
+        transitiveTargets.append(t)
+        t.inputs.foreach(rec)
+      }
+    }
+
+    sourceTargets.items.foreach(rec)
+    transitiveTargets
+  }
+  /**
+    * Takes the given targets, finds all the targets they transitively depend
+    * on, and sort them topologically. Fails if there are dependency cycles
+    */
+  def topoSorted(transitiveTargets: OSet[Task[_]]): TopoSorted = {
+
+    val indexed = transitiveTargets.indexed
+    val targetIndices = indexed.zipWithIndex.toMap
+
+    val numberedEdges =
+      for(t <- transitiveTargets.items)
+        yield t.inputs.collect(targetIndices)
+
+    val sortedClusters = Tarjans(numberedEdges)
+    val nonTrivialClusters = sortedClusters.filter(_.length > 1)
+    assert(nonTrivialClusters.isEmpty, nonTrivialClusters)
+    new TopoSorted(OSet.from(sortedClusters.flatten.map(indexed)))
+  }
+}
diff --git a/core/src/main/scala/mill/eval/Evaluator.scala b/core/src/main/scala/mill/eval/Evaluator.scala
index be0edac4..a36129a5 100644
--- a/core/src/main/scala/mill/eval/Evaluator.scala
+++ b/core/src/main/scala/mill/eval/Evaluator.scala
@@ -1,7 +1,7 @@
 package mill.eval
 
 import ammonite.ops._
-import mill.define.{Target, Task}
+import mill.define.{Graph, Target, Task}
 import mill.discover.Mirror.LabelledTarget
 import mill.util
 import mill.util.{Args, MultiBiMap, OSet}
@@ -14,9 +14,9 @@ class Evaluator(workspacePath: Path,
   def evaluate(goals: OSet[Task[_]]): Evaluator.Results = {
     mkdir(workspacePath)
 
-    val transitive = Evaluator.transitiveTargets(goals)
-    val topoSorted = Evaluator.topoSorted(transitive)
-    val sortedGroups = Evaluator.groupAroundImportantTargets(topoSorted){
+    val transitive = Graph.transitiveTargets(goals)
+    val topoSorted = Graph.topoSorted(transitive)
+    val sortedGroups = Graph.groupAroundImportantTargets(topoSorted){
       case t: Target[_] if labeling.contains(t) || goals.contains(t) => Right(labeling(t))
       case t if goals.contains(t) => Left(t)
     }
@@ -38,7 +38,7 @@ class Evaluator(workspacePath: Path,
     }
 
     val failing = new util.MultiBiMap.Mutable[Either[Task[_], LabelledTarget[_]], Result.Failing]
-    for((k, vs) <- sortedGroups.items){
+    for((k, vs) <- sortedGroups.items()){
       failing.addAll(k, vs.items.flatMap(results.get).collect{case f: Result.Failing => f})
     }
     Evaluator.Results(goals.indexed.map(results), evaluated, transitive, failing)
@@ -133,63 +133,11 @@ class Evaluator(workspacePath: Path,
 
 
 object Evaluator{
-  class TopoSorted private[Evaluator](val values: OSet[Task[_]])
+
   case class Results(rawValues: Seq[Result[Any]],
                      evaluated: OSet[Task[_]],
                      transitive: OSet[Task[_]],
                      failing: MultiBiMap[Either[Task[_], LabelledTarget[_]], Result.Failing]){
     def values = rawValues.collect{case Result.Success(v) => v}
   }
-  def groupAroundImportantTargets[T](topoSortedTargets: TopoSorted)
-                                    (important: PartialFunction[Task[_], T]): MultiBiMap[T, Task[_]] = {
-
-    val output = new MultiBiMap.Mutable[T, Task[_]]()
-    for ((target, t) <- topoSortedTargets.values.flatMap(t => important.lift(t).map((t, _)))) {
-
-      val transitiveTargets = new OSet.Mutable[Task[_]]
-      def rec(t: Task[_]): Unit = {
-        if (transitiveTargets.contains(t)) () // do nothing
-        else if (important.isDefinedAt(t) && t != target) () // do nothing
-        else {
-          transitiveTargets.append(t)
-          t.inputs.foreach(rec)
-        }
-      }
-      rec(target)
-      output.addAll(t, topoSorted(transitiveTargets).values)
-    }
-    output
-  }
-
-  def transitiveTargets(sourceTargets: OSet[Task[_]]): OSet[Task[_]] = {
-    val transitiveTargets = new OSet.Mutable[Task[_]]
-    def rec(t: Task[_]): Unit = {
-      if (transitiveTargets.contains(t)) () // do nothing
-      else {
-        transitiveTargets.append(t)
-        t.inputs.foreach(rec)
-      }
-    }
-
-    sourceTargets.items.foreach(rec)
-    transitiveTargets
-  }
-  /**
-    * Takes the given targets, finds all the targets they transitively depend
-    * on, and sort them topologically. Fails if there are dependency cycles
-    */
-  def topoSorted(transitiveTargets: OSet[Task[_]]): TopoSorted = {
-
-    val indexed = transitiveTargets.indexed
-    val targetIndices = indexed.zipWithIndex.toMap
-
-    val numberedEdges =
-      for(t <- transitiveTargets.items)
-      yield t.inputs.collect(targetIndices)
-
-    val sortedClusters = Tarjans(numberedEdges)
-    val nonTrivialClusters = sortedClusters.filter(_.length > 1)
-    assert(nonTrivialClusters.isEmpty, nonTrivialClusters)
-    new TopoSorted(OSet.from(sortedClusters.flatten.map(indexed)))
-  }
 }
\ No newline at end of file
diff --git a/core/src/test/scala/mill/define/GraphTests.scala b/core/src/test/scala/mill/define/GraphTests.scala
index a83f7a7b..a64c1390 100644
--- a/core/src/test/scala/mill/define/GraphTests.scala
+++ b/core/src/test/scala/mill/define/GraphTests.scala
@@ -1,6 +1,6 @@
 package mill.define
 
-import mill.discover.Discovered
+
 import mill.eval.Evaluator
 import mill.util.{OSet, TestGraphs, TestUtil}
 import utest._
@@ -15,7 +15,7 @@ object GraphTests extends TestSuite{
 
     'topoSortedTransitiveTargets - {
       def check(targets: OSet[Task[_]], expected: OSet[Task[_]]) = {
-        val result = Evaluator.topoSorted(Evaluator.transitiveTargets(targets)).values
+        val result = Graph.topoSorted(Graph.transitiveTargets(targets)).values
         TestUtil.checkTopological(result)
         assert(result == expected)
       }
@@ -59,22 +59,23 @@ object GraphTests extends TestSuite{
         )
       )
       'bigSingleTerminal - {
-        val result = Evaluator.topoSorted(Evaluator.transitiveTargets(OSet(bigSingleTerminal.j))).values
+        val result = Graph.topoSorted(Graph.transitiveTargets(OSet(bigSingleTerminal.j))).values
         TestUtil.checkTopological(result)
         assert(result.size == 28)
       }
     }
 
     'groupAroundNamedTargets - {
-      def check[T: Discovered, R <: Target[Int]](base: T,
-                                                 target: R,
-                                                 expected: OSet[(R, Int)]) = {
+      def check[T, R <: Target[Int]](base: T)
+                                    (target: T => R,
+                                     important0: OSet[T => Target[_]],
+                                     expected: OSet[(R, Int)]) = {
 
-        val mapping = Discovered.mapping(base)
-        val topoSorted = Evaluator.topoSorted(Evaluator.transitiveTargets(OSet(target)))
+        val topoSorted = Graph.topoSorted(Graph.transitiveTargets(OSet(target(base))))
 
-        val grouped = Evaluator.groupAroundImportantTargets(topoSorted) {
-          case t: Target[_] if mapping.contains(t) => t
+        val important = important0.map(_(base))
+        val grouped = Graph.groupAroundImportantTargets(topoSorted) {
+          case t: Target[_] if important.contains(t) => t
         }
         val flattened = OSet.from(grouped.values().flatMap(_.items))
 
@@ -83,28 +84,28 @@ object GraphTests extends TestSuite{
           val grouping = grouped.lookupKey(terminal)
           assert(
             grouping.size == expectedSize,
-            grouping.flatMap(_.asTarget: Option[Target[_]]).filter(mapping.contains) == OSet(terminal)
+            grouping.flatMap(_.asTarget: Option[Target[_]]).filter(important.contains) == OSet(terminal)
           )
         }
       }
-      'singleton - check(
-        singleton,
-        singleton.single,
+      'singleton - check(singleton)(
+        _.single,
+        OSet(_.single),
         OSet(singleton.single -> 1)
       )
-      'pair - check(
-        pair,
-        pair.down,
+      'pair - check(pair)(
+        _.down,
+        OSet(_.up, _.down),
         OSet(pair.up -> 1, pair.down -> 1)
       )
-      'anonTriple - check(
-        anonTriple,
-        anonTriple.down,
+      'anonTriple - check(anonTriple)(
+        _.down,
+        OSet(_.up, _.down),
         OSet(anonTriple.up -> 1, anonTriple.down -> 2)
       )
-      'diamond - check(
-        diamond,
-        diamond.down,
+      'diamond - check(diamond)(
+        _.down,
+        OSet(_.up, _.left, _.right, _.down),
         OSet(
           diamond.up -> 1,
           diamond.left -> 1,
@@ -113,9 +114,9 @@ object GraphTests extends TestSuite{
         )
       )
 
-      'defCachedDiamond - check(
-        defCachedDiamond,
-        defCachedDiamond.down,
+      'defCachedDiamond - check(defCachedDiamond)(
+        _.down,
+        OSet(_.up, _.left, _.right, _.down),
         OSet(
           defCachedDiamond.up -> 2,
           defCachedDiamond.left -> 2,
@@ -124,17 +125,17 @@ object GraphTests extends TestSuite{
         )
       )
 
-      'anonDiamond - check(
-        anonDiamond,
-        anonDiamond.down,
+      'anonDiamond - check(anonDiamond)(
+        _.down,
+        OSet(_.down, _.up),
         OSet(
           anonDiamond.up -> 1,
           anonDiamond.down -> 3
         )
       )
-      'bigSingleTerminal - check(
-        bigSingleTerminal,
-        bigSingleTerminal.j,
+      'bigSingleTerminal - check(bigSingleTerminal)(
+        _.j,
+        OSet(_.a, _.b, _.e, _.f, _.i, _.j),
         OSet(
           bigSingleTerminal.a -> 3,
           bigSingleTerminal.b -> 2,
diff --git a/core/src/test/scala/mill/eval/EvaluationTests.scala b/core/src/test/scala/mill/eval/EvaluationTests.scala
index 9a177b58..388f9f38 100644
--- a/core/src/test/scala/mill/eval/EvaluationTests.scala
+++ b/core/src/test/scala/mill/eval/EvaluationTests.scala
@@ -2,7 +2,7 @@ package mill.eval
 
 
 import mill.util.TestUtil.{Test, test}
-import mill.define.{Target, Task}
+import mill.define.{Graph, Target, Task}
 import mill.{Module, T}
 import mill.discover.Discovered
 import mill.util.{OSet, TestUtil}
@@ -49,10 +49,10 @@ object EvaluationTests extends TestSuite{
   }
   def countGroups[T: Discovered](t: T, goals: Task[_]*) = {
     val labeling = Discovered.mapping(t)
-    val topoSorted = Evaluator.topoSorted(
-      Evaluator.transitiveTargets(OSet.from(goals))
+    val topoSorted = Graph.topoSorted(
+      Graph.transitiveTargets(OSet.from(goals))
     )
-    val grouped = Evaluator.groupAroundImportantTargets(topoSorted) {
+    val grouped = Graph.groupAroundImportantTargets(topoSorted) {
       case t: Target[_] if labeling.contains(t) || goals.contains(t) => t
       case t if goals.contains(t) => t
     }