diff options
author | Li Haoyi <haoyi.sg@gmail.com> | 2017-11-18 16:02:56 -0800 |
---|---|---|
committer | Li Haoyi <haoyi.sg@gmail.com> | 2017-11-18 16:02:56 -0800 |
commit | a56cc38ff068fa2efd5df066dd3a8143f7f76fea (patch) | |
tree | c78c17c1cdbae18eb56cdac6152a786b52d1a62b /core | |
parent | fba1439021e9ad009157cc56dccc93b2e90b2c71 (diff) | |
download | mill-a56cc38ff068fa2efd5df066dd3a8143f7f76fea.tar.gz mill-a56cc38ff068fa2efd5df066dd3a8143f7f76fea.tar.bz2 mill-a56cc38ff068fa2efd5df066dd3a8143f7f76fea.zip |
Move graph algorithms on tasks into `define/Graph.scala`, and move `GraphTests.scala` into `define/` as well
Diffstat (limited to 'core')
-rw-r--r-- | core/src/main/scala/mill/define/Graph.scala | 60 | ||||
-rw-r--r-- | core/src/main/scala/mill/eval/Evaluator.scala | 64 | ||||
-rw-r--r-- | core/src/test/scala/mill/define/GraphTests.scala | 65 | ||||
-rw-r--r-- | core/src/test/scala/mill/eval/EvaluationTests.scala | 8 |
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 } |