- Give `Target`s nicer `toString`s using `sourcecode.Enclosing`. Still not as good as the `Labeling` they get during evaluation, but better than nothing

- Split out `TargetImpl` from `Target`, so we can make our dummy `TestUtils.Test` class implement `Target`s for discoverability etc.

- Make `Discovered` only discover `Target`s, not `Task`s

- Make `groupAroundNamedTargets` properly sort the groups topologically, and by flexible enough to combine groups which have cycles between them.

8 files changed, 57 insertions, 18 deletions

diff --git a/core/src/main/scala/mill/define/Cacher.scala b/core/src/main/scala/mill/define/Cacher.scala
index 192f9a3e..224704ce 100644
--- a/core/src/main/scala/mill/define/Cacher.scala
+++ b/core/src/main/scala/mill/define/Cacher.scala
@@ -6,10 +6,10 @@ import scala.reflect.macros.blackbox.Context
 
 trait Cacher[C[_], V[_]]{
   private[this] val cacherLazyMap = mutable.Map.empty[sourcecode.Enclosing, V[_]]
-  def wrapCached[T](in: C[T]): V[T]
+  def wrapCached[T](in: C[T], enclosing: String): V[T]
   protected[this] def cachedTarget[T](t: => C[T])
                                      (implicit c: sourcecode.Enclosing): V[T] = synchronized{
-    cacherLazyMap.getOrElseUpdate(c, wrapCached(t)).asInstanceOf[V[T]]
+    cacherLazyMap.getOrElseUpdate(c, wrapCached(t, c.value)).asInstanceOf[V[T]]
   }
 }
 object Cacher{
diff --git a/core/src/main/scala/mill/define/Task.scala b/core/src/main/scala/mill/define/Task.scala
index 31ac7f4b..9d0972eb 100644
--- a/core/src/main/scala/mill/define/Task.scala
+++ b/core/src/main/scala/mill/define/Task.scala
@@ -24,9 +24,11 @@ abstract class Task[+T] extends Task.Ops[T] with Applyable[T]{
   def sideHash: Int = 0
 }
 
-class Target[+T](t: Task[T]) extends Task[T] {
+trait Target[+T] extends Task[T]
+class TargetImpl[+T](t: Task[T], enclosing: String) extends Target[T] {
   val inputs = Seq(t)
   def evaluate(args: Args) = args[T](0)
+  override def toString = enclosing + "@" + Integer.toHexString(System.identityHashCode(this))
 }
 class Command[+T](t: Task[T]) extends Task[T] {
   val inputs = Seq(t)
@@ -37,7 +39,7 @@ object Task extends Applicative.Applyer[Task, Task, Args]{
   def underlying[A](v: Task[A]) = v
 
   trait Cacher extends mill.define.Cacher[Task, Target]{
-    def wrapCached[T](t: Task[T]): Target[T] = new Target(t)
+    def wrapCached[T](t: Task[T], enclosing: String): Target[T] = new TargetImpl(t, enclosing)
   }
   class Target0[T](t: T) extends Task[T]{
     lazy val t0 = t
@@ -83,7 +85,8 @@ object Task extends Applicative.Applyer[Task, Task, Args]{
   def traverse[T](source: Seq[Task[T]]) = {
     new Traverse[T](source)
   }
-  class Traverse[+T](val inputs: Seq[Task[T]]) extends Task[Seq[T]]{
+  class Traverse[+T](inputs0: Seq[Task[T]]) extends Task[Seq[T]]{
+    val inputs = inputs0
     def evaluate(args: Args) = {
       for (i <- 0 until args.length)
       yield args(i).asInstanceOf[T]
diff --git a/core/src/main/scala/mill/discover/Discovered.scala b/core/src/main/scala/mill/discover/Discovered.scala
index 3fca9a9f..0a17dcba 100644
--- a/core/src/main/scala/mill/discover/Discovered.scala
+++ b/core/src/main/scala/mill/discover/Discovered.scala
@@ -62,12 +62,12 @@ object Discovered {
         if
           (m.isTerm && (m.asTerm.isGetter || m.asTerm.isLazy)) ||
           m.isModule ||
-          (m.isMethod && m.typeSignature.paramLists.isEmpty && m.typeSignature.resultType <:< c.weakTypeOf[Task[_]])
+          (m.isMethod && m.typeSignature.paramLists.isEmpty && m.typeSignature.resultType <:< c.weakTypeOf[Target[_]])
         if !m.name.toString.contains('$')
       } yield {
         val extendedSegments = m.name.toString :: segments
         val self =
-          if (m.typeSignature.resultType <:< c.weakTypeOf[Task[_]]) Seq(extendedSegments)
+          if (m.typeSignature.resultType <:< c.weakTypeOf[Target[_]]) Seq(extendedSegments)
           else Nil
 
         val (mains, children) = rec(extendedSegments, m.typeSignature)
diff --git a/core/src/main/scala/mill/eval/Evaluator.scala b/core/src/main/scala/mill/eval/Evaluator.scala
index de6d81cd..947a2bca 100644
--- a/core/src/main/scala/mill/eval/Evaluator.scala
+++ b/core/src/main/scala/mill/eval/Evaluator.scala
@@ -13,10 +13,8 @@ class Evaluator(workspacePath: Path,
   def evaluate(targets: OSet[Task[_]]): Evaluator.Results = {
     mkdir(workspacePath)
 
-    val sortedGroups = Evaluator.groupAroundNamedTargets(
-      Evaluator.topoSortedTransitiveTargets(targets),
-      labeling
-    )
+    val topoSorted = Evaluator.topoSortedTransitiveTargets(targets)
+    val sortedGroups = Evaluator.groupAroundNamedTargets(topoSorted, labeling)
 
     val evaluated = new OSet.Mutable[Task[_]]
     val results = mutable.LinkedHashMap.empty[Task[_], Any]
@@ -158,13 +156,23 @@ object Evaluator{
       }
     }
 
-    val targetOrdering = topoSortedTargets.values.items.zipWithIndex.toMap
-    val output = new MultiBiMap.Mutable[Int, Task[_]]
 
     // Sort groups amongst themselves, and sort the contents of each group
     // before aggregating it into the final output
-    for(g <- grouping.values().toArray.sortBy(g => targetOrdering(g.items(0)))){
-      output.addAll(output.keys.length, g.toArray.sortBy(targetOrdering))
+    val groupGraph = mutable.Buffer.fill[Seq[Int]](groupCount)(Nil)
+    for((groupId, groupTasks) <- grouping.items()){
+      groupGraph(groupId) =
+        groupTasks.toIterator.flatMap(_.inputs).map(grouping.lookupValue).toArray.distinct.toSeq
+    }
+    // Given input topoSortedTargets has no cycles, group graph should not have cycles
+    val groupOrdering = Tarjans.apply(groupGraph)
+
+
+    val targetOrdering = topoSortedTargets.values.items.zipWithIndex.toMap
+    val output = new MultiBiMap.Mutable[Int, Task[_]]
+    for((groupIndices, i) <- groupOrdering.zipWithIndex){
+      val sortedGroup = OSet.from(groupIndices.flatMap(grouping.lookupKey).sortBy(targetOrdering))
+      output.addAll(i, sortedGroup)
     }
     output
   }
diff --git a/core/src/main/scala/mill/util/MultiBiMap.scala b/core/src/main/scala/mill/util/MultiBiMap.scala
index 752d2b9d..88bb172c 100644
--- a/core/src/main/scala/mill/util/MultiBiMap.scala
+++ b/core/src/main/scala/mill/util/MultiBiMap.scala
@@ -17,6 +17,7 @@ trait MultiBiMap[K, V]{
   def addAll(k: K, vs: TraversableOnce[V]): Unit
   def keys(): Iterator[K]
   def values(): Iterator[OSet[V]]
+  def keyCount: Int
 }
 object MultiBiMap{
   class Mutable[K, V]() extends MultiBiMap[K, V]{
@@ -43,5 +44,9 @@ object MultiBiMap{
     def keys() = keyToValues.keysIterator
 
     def values() = keyToValues.valuesIterator
+
+    def items() = keyToValues.iterator
+
+    def keyCount = keyToValues.size
   }
 }
diff --git a/core/src/test/scala/mill/CacherTests.scala b/core/src/test/scala/mill/CacherTests.scala
index b6aebb0c..1a510e4c 100644
--- a/core/src/test/scala/mill/CacherTests.scala
+++ b/core/src/test/scala/mill/CacherTests.scala
@@ -33,7 +33,7 @@ object CacherTests extends TestSuite{
 
     'simpleDefIsCached - assert(
       Base.value eq Base.value,
-      eval(Base, Base.value) == 11
+      eval(Base, Base.value) == 1
     )
 
     'overridingDefIsAlsoCached - assert(
diff --git a/core/src/test/scala/mill/EvaluationTests.scala b/core/src/test/scala/mill/EvaluationTests.scala
index 48b42539..ee7b081e 100644
--- a/core/src/test/scala/mill/EvaluationTests.scala
+++ b/core/src/test/scala/mill/EvaluationTests.scala
@@ -147,7 +147,30 @@ object EvaluationTests extends TestSuite{
     }
 
     'evaluateMixed - {
+      'triangleTask - {
+        // Make sure the following graph ends up as a single group, since although
+        // `right` depends on `left`, both of them depend on the un-cached `task`
+        // which would force them both to re-compute every time `task` changes
+        //
+        //      _ left _
+        //     /        \
+        // task -------- right
+        object taskTriangle extends Cacher{
+          val task = T.task{ 1 }
+          def left = T{ task() }
+          def right = T{ task() + left() }
+        }
+        val labeling = Discovered.mapping(taskTriangle)
+        val topoSorted = Evaluator.topoSortedTransitiveTargets(OSet(taskTriangle.right, taskTriangle.left))
+        val grouped = Evaluator.groupAroundNamedTargets(topoSorted, labeling)
+        val groupCount = grouped.keyCount
+        assert(groupCount == 1)
+
+      }
       'tasksAreUncached - {
+        // Make sure the tasks `left` and `middle` re-compute every time, while
+        // the target `right` does not
+        //
         //    ___ left ___
         //   /            \
         // up    middle -- down
diff --git a/core/src/test/scala/mill/TestUtil.scala b/core/src/test/scala/mill/TestUtil.scala
index f2c4ad3a..59cda559 100644
--- a/core/src/test/scala/mill/TestUtil.scala
+++ b/core/src/test/scala/mill/TestUtil.scala
@@ -1,6 +1,6 @@
 package mill
 
-import mill.define.Task
+import mill.define.{Target, Task}
 import mill.util.{Args, OSet}
 import utest.assert
 
@@ -17,7 +17,7 @@ object TestUtil {
     * test how changes propagate.
     */
   class Test(override val inputs: Seq[Task[Int]],
-             val pure: Boolean) extends Task[Int]{
+             val pure: Boolean) extends Target[Int]{
     var counter = 0
     override def evaluate(args: Args) = {
       counter + args.args.map(_.asInstanceOf[Int]).sum