diff options
| -rw-r--r-- | core/src/main/scala/mill/eval/Evaluator.scala | 127 | ||||
| -rw-r--r-- | core/src/main/scala/mill/util/MultiBiMap.scala | 2 | ||||
| -rw-r--r-- | core/src/test/scala/mill/CacherTests.scala | 1 | ||||
| -rw-r--r-- | core/src/test/scala/mill/EvaluationTests.scala | 85 | ||||
| -rw-r--r-- | core/src/test/scala/mill/GraphTests.scala | 48 |
5 files changed, 132 insertions, 131 deletions
diff --git a/core/src/main/scala/mill/eval/Evaluator.scala b/core/src/main/scala/mill/eval/Evaluator.scala index da6e2656..8163a304 100644 --- a/core/src/main/scala/mill/eval/Evaluator.scala +++ b/core/src/main/scala/mill/eval/Evaluator.scala @@ -10,44 +10,43 @@ import scala.collection.mutable class Evaluator(workspacePath: Path, labeling: Map[Task[_], Labelled[_]]){ - def evaluate(targets: OSet[Task[_]]): Evaluator.Results = { + def evaluate(goals: OSet[Task[_]]): Evaluator.Results = { mkdir(workspacePath) - val transitive = Evaluator.transitiveTargets(targets) + val transitive = Evaluator.transitiveTargets(goals) val topoSorted = Evaluator.topoSorted(transitive) - val sortedGroups = Evaluator.groupAroundNamedTargets(topoSorted, labeling) + val sortedGroups = Evaluator.groupAroundImportantTargets( + topoSorted, + t => labeling.contains(t) || goals.contains(t) + ) val evaluated = new OSet.Mutable[Task[_]] val results = mutable.LinkedHashMap.empty[Task[_], Any] - for (groupIndex <- sortedGroups.keys()){ - val group = sortedGroups.lookupKey(groupIndex) - - val (newResults, newEvaluated) = evaluateGroupCached( - group, - results, - sortedGroups - ) - evaluated.appendAll(newEvaluated) + for ((terminal, group)<- sortedGroups.items()){ + val (newResults, newEvaluated) = evaluateGroupCached(terminal, group, results) + for(ev <- newEvaluated){ + evaluated.append(ev) + } for((k, v) <- newResults) results.put(k, v) } - Evaluator.Results(targets.items.map(results), evaluated, transitive) + Evaluator.Results(goals.items.map(results), evaluated, transitive) } - def evaluateGroupCached(group: OSet[Task[_]], - results: collection.Map[Task[_], Any], - sortedGroups: MultiBiMap[Int, Task[_]]): (collection.Map[Task[_], Any], Seq[Task[_]]) = { + def evaluateGroupCached(terminal: Task[_], + group: OSet[Task[_]], + results: collection.Map[Task[_], Any]): (collection.Map[Task[_], Any], Seq[Task[_]]) = { - val (externalInputs, terminals) = partitionGroupInputOutput(group, results) + val externalInputs = group.items.flatMap(_.inputs).filter(!group.contains(_)) val inputsHash = externalInputs.toIterator.map(results).toVector.hashCode + group.toIterator.map(_.sideHash).toVector.hashCode() - val (targetDestPath, metadataPath) = labeling.get(terminals.items(0)) match{ + val (targetDestPath, metadataPath) = labeling.get(terminal) match{ case Some(labeling) => val targetDestPath = workspacePath / labeling.segments val metadataPath = targetDestPath / up / (targetDestPath.last + ".mill.json") @@ -58,16 +57,14 @@ class Evaluator(workspacePath: Path, val cached = for{ metadataPath <- metadataPath json <- scala.util.Try(Json.parse(read.getInputStream(metadataPath))).toOption - (cachedHash, terminalResults) <- Json.fromJson[(Int, Seq[JsValue])](json).asOpt + (cachedHash, terminalResult) <- Json.fromJson[(Int, JsValue)](json).asOpt if cachedHash == inputsHash - } yield terminalResults + } yield terminalResult cached match{ - case Some(terminalResults) => + case Some(terminalResult) => val newResults = mutable.LinkedHashMap.empty[Task[_], Any] - for((terminal, res) <- terminals.items.zip(terminalResults)){ - newResults(terminal) = labeling(terminal).format.reads(res).get - } + newResults(terminal) = labeling(terminal).format.reads(terminalResult).get (newResults, Nil) case _ => @@ -76,13 +73,13 @@ class Evaluator(workspacePath: Path, if (labeled.nonEmpty){ println(fansi.Color.Blue("Running " + labeled.map(_.segments.mkString(".")).mkString(", "))) } - val (newResults, newEvaluated, terminalResults) = evaluateGroup(group, results, targetDestPath) + val (newResults, newEvaluated, terminalResult) = evaluateGroup(group, results, targetDestPath) metadataPath.foreach( write.over( _, Json.prettyPrint( - Json.toJson(inputsHash -> terminals.toList.map(terminalResults)) + Json.toJson(inputsHash -> terminalResult) ), ) ) @@ -91,24 +88,17 @@ class Evaluator(workspacePath: Path, } } - def partitionGroupInputOutput(group: OSet[Task[_]], - results: collection.Map[Task[_], Any]) = { - val allInputs = group.items.flatMap(_.inputs) - val (internalInputs, externalInputs) = allInputs.partition(group.contains) - val internalInputSet = internalInputs.toSet - val terminals = group.filter(x => !internalInputSet(x) || labeling.contains(x)) - (OSet.from(externalInputs.distinct), terminals) - } def evaluateGroup(group: OSet[Task[_]], results: collection.Map[Task[_], Any], targetDestPath: Option[Path]) = { targetDestPath.foreach(rm) - val terminalResults = mutable.LinkedHashMap.empty[Task[_], JsValue] + var terminalResult: JsValue = null val newEvaluated = mutable.Buffer.empty[Task[_]] val newResults = mutable.LinkedHashMap.empty[Task[_], Any] - for (target <- group.items) { + for (target <- group.items if !results.contains(target)) { + newEvaluated.append(target) val targetInputValues = target.inputs.toVector.map(x => newResults.getOrElse(x, results(x)) @@ -117,7 +107,7 @@ class Evaluator(workspacePath: Path, val args = new Args(targetInputValues, targetDestPath.orNull) val res = target.evaluate(args) for(targetLabel <- labeling.get(target)){ - terminalResults(target) = targetLabel + terminalResult = targetLabel .format .asInstanceOf[Format[Any]] .writes(res.asInstanceOf[Any]) @@ -125,7 +115,7 @@ class Evaluator(workspacePath: Path, newResults(target) = res } - (newResults, newEvaluated, terminalResults) + (newResults, newEvaluated, terminalResult) } } @@ -134,52 +124,23 @@ class Evaluator(workspacePath: Path, object Evaluator{ class TopoSorted private[Evaluator](val values: OSet[Task[_]]) case class Results(values: Seq[Any], evaluated: OSet[Task[_]], transitive: OSet[Task[_]]) - def groupAroundNamedTargets(topoSortedTargets: TopoSorted, - labeling: Map[Task[_], Labelled[_]]): MultiBiMap[Int, Task[_]] = { - - val grouping = new MultiBiMap.Mutable[Int, Task[_]]() - - var groupCount = 0 - - for(target <- topoSortedTargets.values.items.reverseIterator){ - if (!grouping.containsValue(target)){ - grouping.add(groupCount, target) - groupCount += 1 - } - - val targetGroup = grouping.lookupValue(target) - for(upstream <- target.inputs){ - grouping.lookupValueOpt(upstream) match{ - case None if !labeling.contains(upstream) => - grouping.add(targetGroup, upstream) - case Some(upstreamGroup) - if !labeling.contains(upstream) && upstreamGroup != targetGroup => - val upstreamTargets = grouping.removeAll(upstreamGroup) - grouping.addAll(targetGroup, upstreamTargets) - case _ => //donothing + def groupAroundImportantTargets(topoSortedTargets: TopoSorted, + important: Task[_] => Boolean): MultiBiMap[Task[_], Task[_]] = { + + val output = new MultiBiMap.Mutable[Task[_], Task[_]]() + for (target <- topoSortedTargets.values if important(target)) { + + val transitiveTargets = new OSet.Mutable[Task[_]] + def rec(t: Task[_]): Unit = { + if (transitiveTargets.contains(t)) () // do nothing + else if (important(t) && t != target) () // do nothing + else { + transitiveTargets.append(t) + t.inputs.foreach(rec) } } - } - - - // Sort groups amongst themselves, and sort the contents of each group - // before aggregating it into the final output - 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.lookupKeyOpt).flatten.sortBy(targetOrdering) - ) - output.addAll(i, sortedGroup) + rec(target) + output.addAll(target, topoSorted(transitiveTargets).values) } output } @@ -207,7 +168,7 @@ object Evaluator{ val numberedEdges = for(t <- transitiveTargets.items) - yield t.inputs.map(targetIndices) + yield t.inputs.collect(targetIndices) val sortedClusters = Tarjans(numberedEdges) val nonTrivialClusters = sortedClusters.filter(_.length > 1) diff --git a/core/src/main/scala/mill/util/MultiBiMap.scala b/core/src/main/scala/mill/util/MultiBiMap.scala index 2052ef90..ef5359bc 100644 --- a/core/src/main/scala/mill/util/MultiBiMap.scala +++ b/core/src/main/scala/mill/util/MultiBiMap.scala @@ -16,9 +16,11 @@ trait MultiBiMap[K, V]{ def removeAll(k: K): OSet[V] def addAll(k: K, vs: TraversableOnce[V]): Unit def keys(): Iterator[K] + def items(): Iterator[(K, OSet[V])] def values(): Iterator[OSet[V]] def keyCount: Int } + object MultiBiMap{ class Mutable[K, V]() extends MultiBiMap[K, V]{ private[this] val valueToKey = mutable.LinkedHashMap.empty[V, K] diff --git a/core/src/test/scala/mill/CacherTests.scala b/core/src/test/scala/mill/CacherTests.scala index 1a510e4c..5931691d 100644 --- a/core/src/test/scala/mill/CacherTests.scala +++ b/core/src/test/scala/mill/CacherTests.scala @@ -51,3 +51,4 @@ object CacherTests extends TestSuite{ ) } } + diff --git a/core/src/test/scala/mill/EvaluationTests.scala b/core/src/test/scala/mill/EvaluationTests.scala index 09dd6731..32d2b847 100644 --- a/core/src/test/scala/mill/EvaluationTests.scala +++ b/core/src/test/scala/mill/EvaluationTests.scala @@ -48,12 +48,15 @@ object EvaluationTests extends TestSuite{ } } } - def countGroups[T: Discovered](t: T, terminals: Task[_]*) = { + def countGroups[T: Discovered](t: T, goals: Task[_]*) = { val labeling = Discovered.mapping(t) val topoSorted = Evaluator.topoSorted( - Evaluator.transitiveTargets(OSet.from(terminals)) + Evaluator.transitiveTargets(OSet.from(goals)) + ) + val grouped = Evaluator.groupAroundImportantTargets( + topoSorted, + t => labeling.contains(t) || goals.contains(t) ) - val grouped = Evaluator.groupAroundNamedTargets(topoSorted, labeling) grouped.keyCount } @@ -158,6 +161,40 @@ object EvaluationTests extends TestSuite{ } 'evaluateMixed - { + 'separateGroups - { + // Make sure that `left` and `right` are able to recompute separately, + // even though one depends on the other + // + // _ left _ + // / \ + // task1 -------- right + // _/ + // change - task2 + object build extends Cacher{ + val task1 = T.task{ 1 } + def left = T{ task1() } + val change = test() + val task2 = T.task{ change() } + def right = T{ task1() + task2() + left() + 1 } + + } + import build._ + val groupCount = countGroups(build, right, left) + assert(groupCount == 3) + val checker = new Checker(build) + val evaled1 = checker.evaluator.evaluate(OSet(right, left)) + val filtered1 = evaled1.evaluated.filter(_.isInstanceOf[Target[_]]) + assert(filtered1 == OSet(change, left, right)) + val evaled2 = checker.evaluator.evaluate(OSet(right, left)) + val filtered2 = evaled2.evaluated.filter(_.isInstanceOf[Target[_]]) + assert(filtered2 == OSet()) + change.counter += 1 + val evaled3 = checker.evaluator.evaluate(OSet(right, left)) + val filtered3 = evaled3.evaluated.filter(_.isInstanceOf[Target[_]]) + assert(filtered3 == OSet(change, right)) + + + } '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` @@ -166,17 +203,17 @@ object EvaluationTests extends TestSuite{ // _ left _ // / \ // task -------- right - object taskTriangle extends Cacher{ + object build extends Cacher{ val task = T.task{ 1 } def left = T{ task() } def right = T{ task() + left() + 1 } } - - val groupCount = countGroups(taskTriangle, taskTriangle.right, taskTriangle.left) - assert(groupCount == 1) - val checker = new Checker(taskTriangle) - checker(taskTriangle.right, 3, OSet(taskTriangle.right), extraEvaled = -1) - checker(taskTriangle.left, 1, OSet(taskTriangle.left), extraEvaled = -1) + import build._ + val groupCount = countGroups(build, right, left) + assert(groupCount == 2) + val checker = new Checker(build) + checker(right, 3, OSet(left, right), extraEvaled = -1) + checker(left, 1, OSet(), extraEvaled = -1) } 'multiTerminalGroup - { @@ -185,17 +222,17 @@ object EvaluationTests extends TestSuite{ // _ left // / // task -------- right - object taskTriangle extends Cacher{ + object build extends Cacher{ val task = T.task{ 1 } def left = T{ task() } def right = T{ task() } } - val groupCount = countGroups(taskTriangle, taskTriangle.right, taskTriangle.left) - assert(groupCount == 1) + val groupCount = countGroups(build, build.right, build.left) + assert(groupCount == 2) - val checker = new Checker(taskTriangle) - checker(taskTriangle.right, 1, OSet(taskTriangle.right), extraEvaled = -1) - checker(taskTriangle.left, 1, OSet(taskTriangle.left), extraEvaled = -1) + val checker = new Checker(build) + checker(build.right, 1, OSet(build.right), extraEvaled = -1) + checker(build.left, 1, OSet(build.left), extraEvaled = -1) } 'multiTerminalBoundary - { @@ -204,18 +241,18 @@ object EvaluationTests extends TestSuite{ // _ left _____________ // / \ \ // task1 -------- right ----- task2 - object multiTerminalBoundary extends Cacher{ + object build extends Cacher{ val task1 = T.task{ 1 } def left = T{ task1() } def right = T{ task1() + left() + 1 } val task2 = T.task{ left() + right() } } - import multiTerminalBoundary._ - val groupCount = countGroups(multiTerminalBoundary, task2) - assert(groupCount == 2) + import build._ + val groupCount = countGroups(build, task2) + assert(groupCount == 3) - val checker = new Checker(multiTerminalBoundary) + val checker = new Checker(build) checker(task2, 4, OSet(right, left), extraEvaled = -1, secondRunNoOp = false) checker(task2, 4, OSet(), extraEvaled = -1, secondRunNoOp = false) } @@ -229,7 +266,7 @@ object EvaluationTests extends TestSuite{ // up middle -- down // / // right - object taskDiamond extends Cacher{ + object build extends Cacher{ var leftCount = 0 var rightCount = 0 var middleCount = 0 @@ -240,7 +277,7 @@ object EvaluationTests extends TestSuite{ def down = T{ left() + middle() + right() } } - import taskDiamond._ + import build._ // Ensure task objects themselves are not cached, and recomputed each time assert( @@ -253,7 +290,7 @@ object EvaluationTests extends TestSuite{ // During the first evaluation, they get computed normally like any // cached target - val check = new Checker(taskDiamond) + val check = new Checker(build) assert(leftCount == 0, rightCount == 0) check(down, expValue = 10101, expEvaled = OSet(up, right, down), extraEvaled = 8) assert(leftCount == 1, middleCount == 1, rightCount == 1) diff --git a/core/src/test/scala/mill/GraphTests.scala b/core/src/test/scala/mill/GraphTests.scala index 60895c71..fe21a6de 100644 --- a/core/src/test/scala/mill/GraphTests.scala +++ b/core/src/test/scala/mill/GraphTests.scala @@ -137,46 +137,46 @@ object GraphTests extends TestSuite{ 'groupAroundNamedTargets - { def check[T: Discovered, R <: Task[Int]](base: T, target: R, - expected: OSet[(OSet[R], Int)]) = { + expected: OSet[(R, Int)]) = { val mapping = Discovered.mapping(base) val topoSortedTransitive = Evaluator.topoSorted(Evaluator.transitiveTargets(OSet(target))) - val grouped = Evaluator.groupAroundNamedTargets(topoSortedTransitive, mapping) + val grouped = Evaluator.groupAroundImportantTargets(topoSortedTransitive, mapping.contains) val flattened = OSet.from(grouped.values().flatMap(_.items)) TestUtil.checkTopological(flattened) - for(((expectedPresent, expectedSize), i) <- expected.items.zipWithIndex){ - val grouping = grouped.lookupKey(i) + for((terminal, expectedSize) <- expected){ + val grouping = grouped.lookupKey(terminal) assert( grouping.size == expectedSize, - grouping.filter(mapping.contains) == expectedPresent + grouping.filter(mapping.contains) == OSet(terminal) ) } } 'singleton - check( singleton, singleton.single, - OSet(OSet(singleton.single) -> 1) + OSet(singleton.single -> 1) ) 'pair - check( pair, pair.down, - OSet(OSet(pair.up) -> 1, OSet(pair.down) -> 1) + OSet(pair.up -> 1, pair.down -> 1) ) 'anonTriple - check( anonTriple, anonTriple.down, - OSet(OSet(anonTriple.up) -> 1, OSet(anonTriple.down) -> 2) + OSet(anonTriple.up -> 1, anonTriple.down -> 2) ) 'diamond - check( diamond, diamond.down, OSet( - OSet(diamond.up) -> 1, - OSet(diamond.left) -> 1, - OSet(diamond.right) -> 1, - OSet(diamond.down) -> 1 + diamond.up -> 1, + diamond.left -> 1, + diamond.right -> 1, + diamond.down -> 1 ) ) @@ -184,10 +184,10 @@ object GraphTests extends TestSuite{ defCachedDiamond, defCachedDiamond.down, OSet( - OSet(defCachedDiamond.up) -> 2, - OSet(defCachedDiamond.left) -> 2, - OSet(defCachedDiamond.right) -> 2, - OSet(defCachedDiamond.down) -> 2 + defCachedDiamond.up -> 2, + defCachedDiamond.left -> 2, + defCachedDiamond.right -> 2, + defCachedDiamond.down -> 2 ) ) @@ -195,20 +195,20 @@ object GraphTests extends TestSuite{ anonDiamond, anonDiamond.down, OSet( - OSet(anonDiamond.up) -> 1, - OSet(anonDiamond.down) -> 3 + anonDiamond.up -> 1, + anonDiamond.down -> 3 ) ) 'bigSingleTerminal - check( bigSingleTerminal, bigSingleTerminal.j, OSet( - OSet(bigSingleTerminal.a) -> 3, - OSet(bigSingleTerminal.b) -> 2, - OSet(bigSingleTerminal.e) -> 9, - OSet(bigSingleTerminal.i) -> 6, - OSet(bigSingleTerminal.f) -> 4, - OSet(bigSingleTerminal.j) -> 4 + bigSingleTerminal.a -> 3, + bigSingleTerminal.b -> 2, + bigSingleTerminal.e -> 9, + bigSingleTerminal.i -> 6, + bigSingleTerminal.f -> 4, + bigSingleTerminal.j -> 4 ) ) } |