diff options
author | Li Haoyi <haoyi.sg@gmail.com> | 2017-10-29 10:58:57 -0700 |
---|---|---|
committer | Li Haoyi <haoyi.sg@gmail.com> | 2017-10-29 10:58:57 -0700 |
commit | d3ac2ca2c3a581152323d315d3765a18c2fb02c0 (patch) | |
tree | a84748888f6fa501f962f88b0000672742cbe17f /src/main/scala | |
parent | 1b940e9c1341f6f8e42293661b6dcdbffecbe66e (diff) | |
download | mill-d3ac2ca2c3a581152323d315d3765a18c2fb02c0.tar.gz mill-d3ac2ca2c3a581152323d315d3765a18c2fb02c0.tar.bz2 mill-d3ac2ca2c3a581152323d315d3765a18c2fb02c0.zip |
WIP
- Making `groupAroundNamedTargets` return a `MutableBiMap`
- Make `evaluateGroupCached` also take note of the `sideHash`es of upstream targets, to handle cases like `Path`s where the path you're returning doesn't change but we still want to invalidate it anyway
Diffstat (limited to 'src/main/scala')
-rw-r--r-- | src/main/scala/forge/Discovered.scala | 9 | ||||
-rw-r--r-- | src/main/scala/forge/Evaluator.scala | 67 | ||||
-rw-r--r-- | src/main/scala/forge/Target.scala | 6 | ||||
-rw-r--r-- | src/main/scala/forge/Util.scala | 50 |
4 files changed, 88 insertions, 44 deletions
diff --git a/src/main/scala/forge/Discovered.scala b/src/main/scala/forge/Discovered.scala index 2475dc18..6003f3b8 100644 --- a/src/main/scala/forge/Discovered.scala +++ b/src/main/scala/forge/Discovered.scala @@ -4,11 +4,14 @@ import scala.language.experimental.macros import scala.reflect.macros.blackbox.Context class Discovered[T](val value: Seq[(Seq[String], T => Target[_])]){ - def apply(t: T) = { - value.map{case (a, b) => (a, b(t)) } - } + def apply(t: T) = value.map{case (a, b) => (a, b(t)) } + } object Discovered { + def mapping[T: Discovered](t: T): Map[Target[_], Seq[String]] = { + implicitly[Discovered[T]].apply(t).map(_.swap).toMap + } + implicit def apply[T]: Discovered[T] = macro applyImpl[T] def applyImpl[T: c.WeakTypeTag](c: Context): c.Expr[Discovered[T]] = { diff --git a/src/main/scala/forge/Evaluator.scala b/src/main/scala/forge/Evaluator.scala index fae4447b..d19b8aa3 100644 --- a/src/main/scala/forge/Evaluator.scala +++ b/src/main/scala/forge/Evaluator.scala @@ -4,7 +4,6 @@ package forge import play.api.libs.json.{JsValue, Json} import scala.collection.mutable -import scala.io.Codec import ammonite.ops._ class Evaluator(workspacePath: Path, labeling: Map[Target[_], Seq[String]]){ @@ -19,38 +18,58 @@ class Evaluator(workspacePath: Path, val evaluated = new MutableOSet[Target[_]] val results = mutable.Map.empty[Target[_], Any] - for (group <- sortedGroups){ - val (newResults, newEvaluated) = evaluateGroupCached(group, results) + val groupHashes = mutable.Map.empty[Int, Int] + for (groupIndex <- sortedGroups.keys()){ + val group = sortedGroups.lookupKey(groupIndex) + val (inputsHash, newResults, newEvaluated) = evaluateGroupCached( + group, + results, + groupHashes, + sortedGroups + ) evaluated.appendAll(newEvaluated) for((k, v) <- newResults) results.put(k, v) + groupHashes(groupIndex) = inputsHash } + Evaluator.Results(targets.items.map(results), evaluated) } def evaluateGroupCached(group: OSet[Target[_]], - results: collection.Map[Target[_], Any]) = { + results: collection.Map[Target[_], Any], + groupHashes: collection.Map[Int, Int], + sortedGroups: MultiBiMap[Int, Target[_]]) = { + + pprint.log(group) + val (externalInputs, terminals) = partitionGroupInputOutput(group, results) + val upstreamGroupIds = OSet.from(externalInputs.map(sortedGroups.lookupValue), dedup = true) + + val inputsHash = + externalInputs.toIterator.map(results).hashCode + + group.toIterator.map(_.sideHash).hashCode + + upstreamGroupIds.toIterator.map(groupHashes).hashCode - val (inputsHash0, terminals) = partitionGroupInputOutput(group, results) - val inputsHash = inputsHash0 + group.toIterator.map(_.externalHash).sum val primeLabel = labeling(terminals.items(0)) + val targetDestPath = workspacePath / primeLabel val metadataPath = targetDestPath / up / (targetDestPath.last + ".forge.json") val cached = for{ json <- util.Try(Json.parse(read.getInputStream(metadataPath))).toOption (hash, terminalResults) <- Json.fromJson[(Int, Seq[JsValue])](json).asOpt + _ = println("cached hash " + hash) if hash == inputsHash - } yield (hash, terminalResults) + } yield terminalResults cached match{ - case Some((hash, terminalResults)) => + case Some(terminalResults) => val newResults = mutable.Map.empty[Target[_], Any] for((terminal, res) <- terminals.items.zip(terminalResults)){ newResults(terminal) = terminal.formatter.reads(res).get } - (newResults, Nil) + (inputsHash, newResults, Nil) case _ => val (newResults, newEvaluated, terminalResults) = { @@ -60,10 +79,12 @@ class Evaluator(workspacePath: Path, write.over( metadataPath, - Json.prettyPrint(Json.toJson((inputsHash , terminalResults))).getBytes(Codec.UTF8.charSet), + Json.prettyPrint( + Json.toJson((inputsHash , terminalResults)) + ), ) - (newResults, newEvaluated) + (inputsHash, newResults, newEvaluated) } } @@ -72,10 +93,8 @@ class Evaluator(workspacePath: Path, val allInputs = group.items.flatMap(_.inputs) val (internalInputs, externalInputs) = allInputs.partition(group.contains) val internalInputSet = internalInputs.toSet - val inputResults = externalInputs.distinct.map(results).toIndexedSeq - val inputsHash = inputResults.hashCode val terminals = group.filter(!internalInputSet(_)) - (inputsHash, terminals) + (OSet.from(externalInputs, dedup=true), terminals) } def evaluateGroup(group: OSet[Target[_]], @@ -115,13 +134,13 @@ object Evaluator{ class TopoSorted private[Evaluator] (val values: OSet[Target[_]]) case class Results(values: Seq[Any], evaluated: OSet[Target[_]]) def groupAroundNamedTargets(topoSortedTargets: TopoSorted, - labeling: Map[Target[_], Seq[String]]): OSet[OSet[Target[_]]] = { - val grouping = new MultiBiMap[Int, Target[_]]() + labeling: Map[Target[_], Seq[String]]): MultiBiMap[Int, Target[_]] = { + + val grouping = new MutableMultiBiMap[Int, Target[_]]() var groupCount = 0 for(target <- topoSortedTargets.values.items.reverseIterator){ - if (!grouping.containsValue(target)){ grouping.add(groupCount, target) groupCount += 1 @@ -140,18 +159,14 @@ object Evaluator{ } } } - val output = mutable.Buffer.empty[OSet[Target[_]]] - for(target <- topoSortedTargets.values.items.reverseIterator){ + val output = new MutableMultiBiMap[Int, Target[_]] + for(target <- topoSortedTargets.values.items){ for(targetGroup <- grouping.lookupValueOpt(target)){ - output.append( - OSet.from( - grouping.removeAll(targetGroup) - .sortBy(topoSortedTargets.values.items.indexOf) - ) - ) + val shifted = grouping.removeAll(targetGroup) + output.addAll(output.keys().length, shifted.reverse) } } - OSet.from(output.reverse) + output } /** diff --git a/src/main/scala/forge/Target.scala b/src/main/scala/forge/Target.scala index 81bc5b69..f6339e55 100644 --- a/src/main/scala/forge/Target.scala +++ b/src/main/scala/forge/Target.scala @@ -18,7 +18,7 @@ abstract class Target[T](implicit formatter: Format[T]) extends Target.Ops[T]{ * Even if this target's inputs did not change, does it need to re-evaluate * anyway? */ - def externalHash: Int = 0 + def sideHash: Int = 0 } @@ -55,7 +55,7 @@ object Target{ def evaluate(args: Args) = { counter + args.args.map(_.asInstanceOf[Int]).sum } - override def externalHash = counter + override def sideHash = counter } def traverse[T: Format](source: Seq[Target[T]]) = { new Traverse[T](source) @@ -81,7 +81,7 @@ object Target{ class Path(path: ammonite.ops.Path) extends Target[ammonite.ops.Path]{ def evaluate(args: Args) = path val inputs = Nil - override def externalHash = ls.rec(path).map(x => (x.toString, x.mtime)).hashCode() + override def sideHash = ls.rec(path).map(x => (x.toString, x.mtime)).hashCode() } class Subprocess(val inputs: Seq[Target[_]], command: Args => Seq[String]) extends Target[Subprocess.Result] { diff --git a/src/main/scala/forge/Util.scala b/src/main/scala/forge/Util.scala index 362d66aa..3877015a 100644 --- a/src/main/scala/forge/Util.scala +++ b/src/main/scala/forge/Util.scala @@ -2,29 +2,41 @@ package forge import scala.collection.mutable - -class MultiBiMap[K, V](){ - private[this] val valueToKey = mutable.Map.empty[V, K] - private[this] val keyToValues = mutable.Map.empty[K, List[V]] +trait MultiBiMap[K, V]{ + def containsValue(v: V): Boolean + def lookupKey(k: K): OSet[V] + def lookupValue(v: V): K + def lookupValueOpt(v: V): Option[K] + def add(k: K, v: V): Unit + def removeAll(k: K): OSet[V] + def addAll(k: K, vs: TraversableOnce[V]): Unit + def keys(): Iterator[K] + def values(): Iterator[OSet[V]] +} +class MutableMultiBiMap[K, V]() extends MultiBiMap[K, V]{ + private[this] val valueToKey = mutable.LinkedHashMap.empty[V, K] + private[this] val keyToValues = mutable.LinkedHashMap.empty[K, MutableOSet[V]] def containsValue(v: V) = valueToKey.contains(v) + def lookupKey(k: K) = keyToValues(k) def lookupValue(v: V) = valueToKey(v) def lookupValueOpt(v: V) = valueToKey.get(v) def add(k: K, v: V): Unit = { valueToKey(v) = k - keyToValues(k) = v :: keyToValues.getOrElse(k, Nil) + keyToValues.getOrElseUpdate(k, new MutableOSet[V]()).append(v) } - def removeAll(k: K): Seq[V] = keyToValues.get(k) match { - case None => Nil + def removeAll(k: K): OSet[V] = keyToValues.get(k) match { + case None => OSet() case Some(vs) => vs.foreach(valueToKey.remove) keyToValues.remove(k) vs } - def addAll(k: K, vs: Seq[V]): Unit = { - vs.foreach(valueToKey.update(_, k)) - keyToValues(k) = vs ++: keyToValues.getOrElse(k, Nil) - } + def addAll(k: K, vs: TraversableOnce[V]): Unit = vs.foreach(this.add(k, _)) + + def keys() = keyToValues.keysIterator + + def values() = keyToValues.valuesIterator } /** @@ -38,7 +50,9 @@ trait OSet[V] extends TraversableOnce[V]{ def flatMap[T](f: V => TraversableOnce[T]): OSet[T] def map[T](f: V => T): OSet[T] def filter(f: V => Boolean): OSet[V] - + def collect[T](f: PartialFunction[V, T]): OSet[T] + def zipWithIndex: OSet[(V, Int)] + def reverse: OSet[V] } object OSet{ @@ -81,6 +95,18 @@ class MutableOSet[V](dedup: Boolean = false) extends OSet[V]{ output } + def collect[T](f: PartialFunction[V, T]) = this.filter(f.isDefinedAt).map(x => f(x)) + + def zipWithIndex = { + var i = 0 + this.map{ x => + i += 1 + (x, i-1) + } + } + + def reverse = OSet.from(items.reverseIterator) + // Members declared in scala.collection.GenTraversableOnce def isTraversableAgain: Boolean = items.isTraversableAgain def toIterator: Iterator[V] = items.toIterator |