diff options
author | Li Haoyi <haoyi.sg@gmail.com> | 2018-12-12 16:56:02 -0800 |
---|---|---|
committer | GitHub <noreply@github.com> | 2018-12-12 16:56:02 -0800 |
commit | 9ba4cb69331386dfde9bac69dc2d5b22401face3 (patch) | |
tree | 120349e8015ae5717d36bd44209cde6ff9543518 /main/core/src/define/Graph.scala | |
parent | ea7fceb6e56f53bde3517586dfc57e10a605a524 (diff) | |
download | mill-9ba4cb69331386dfde9bac69dc2d5b22401face3.tar.gz mill-9ba4cb69331386dfde9bac69dc2d5b22401face3.tar.bz2 mill-9ba4cb69331386dfde9bac69dc2d5b22401face3.zip |
collapse boilerplate folder structure within src/ folders (#505)
* collapse boilerplate folder structure within src/ folders
* .
Diffstat (limited to 'main/core/src/define/Graph.scala')
-rw-r--r-- | main/core/src/define/Graph.scala | 72 |
1 files changed, 72 insertions, 0 deletions
diff --git a/main/core/src/define/Graph.scala b/main/core/src/define/Graph.scala new file mode 100644 index 00000000..3119f2fb --- /dev/null +++ b/main/core/src/define/Graph.scala @@ -0,0 +1,72 @@ +package mill.define + +import mill.eval.Tarjans +import mill.util.MultiBiMap +import mill.util.Strict.Agg + +object Graph { + + /** + * The `values` [[Agg]] is guaranteed to be topological sorted and cycle free. + * That's why the constructor is package private. + * @see [[Graph.topoSorted]] + */ + class TopoSorted private[Graph] (val values: Agg[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 Agg.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 + } + + /** + * Collects all transitive dependencies (targets) of the given targets, + * including the given targets. + */ + def transitiveTargets(sourceTargets: Agg[Task[_]]): Agg[Task[_]] = { + val transitiveTargets = new Agg.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: Agg[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(Agg.from(sortedClusters.flatten.map(indexed))) + } +} |