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

6 files changed, 105 insertions, 65 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
diff --git a/src/test/scala/forge/GraphTests.scala b/src/test/scala/forge/GraphTests.scala
index 86955fda..5cfea75d 100644
--- a/src/test/scala/forge/GraphTests.scala
+++ b/src/test/scala/forge/GraphTests.scala
@@ -81,16 +81,15 @@ object GraphTests extends TestSuite{
                                target: Target.Test,
                                expected: OSet[(OSet[Target.Test], Int)]) = {
 
-        val mapping: Map[Target[_], Seq[String]] = {
-          implicitly[Discovered[T]].apply(base).map(_.swap).toMap
-        }
-        val grouped = Evaluator.groupAroundNamedTargets(
-          Evaluator.topoSortedTransitiveTargets(OSet(target)),
-          mapping
-        )
-        TestUtil.checkTopological(grouped.flatMap(_.items))
+        val mapping = Discovered.mapping(base)
+        val topoSortedTransitive = Evaluator.topoSortedTransitiveTargets(OSet(target))
+
+        val grouped = Evaluator.groupAroundNamedTargets(topoSortedTransitive, mapping)
+        val flattened = OSet.from(grouped.values().flatMap(_.items))
+
+        TestUtil.checkTopological(flattened)
         for(((expectedPresent, expectedSize), i) <- expected.items.zipWithIndex){
-          val grouping = grouped.items(i)
+          val grouping = grouped.lookupKey(i)
           assert(
             grouping.size == expectedSize,
             grouping.filter(mapping.contains) == expectedPresent
diff --git a/src/test/scala/forge/Main.scala b/src/test/scala/forge/Main.scala
index e4e38b23..99237e32 100644
--- a/src/test/scala/forge/Main.scala
+++ b/src/test/scala/forge/Main.scala
@@ -4,20 +4,17 @@ import java.util.jar.JarEntry
 import collection.JavaConverters._
 import ammonite.ops._
 object Main{
+  val sourceRoot = Target.path(pwd / 'src / 'test / 'resources / 'example / 'src)
+  val resourceRoot = Target.path(pwd / 'src / 'test / 'resources / 'example / 'resources)
+  val allSources = list(sourceRoot)
+  val classFiles = compileAll(allSources)
+  val jar = jarUp(resourceRoot, classFiles)
 
   def main(args: Array[String]): Unit = {
-
-    val sourceRoot = Target.path(pwd / 'src / 'test / 'resources / 'example / 'src)
-    val resourceRoot = Target.path(pwd / 'src / 'test / 'resources / 'example / 'resources)
-    val allSources = list(sourceRoot)
-    val classFiles = compileAll(allSources)
-    val jar = jarUp(resourceRoot, classFiles)
-
-//    val evaluator = new Evaluator(
-//      Paths.get("target/workspace"),
-//      DefCtx("forge.Main ", None)
-//    )
-//    evaluator.evaluate(OSet(jar))
+    val mapping = Discovered.mapping(Main)
+    val evaluator = new Evaluator(pwd / 'target / 'workspace / 'main, mapping)
+    val res = evaluator.evaluate(OSet(jar))
+    println(res.evaluated.collect(mapping))
   }
   def compileAll(sources: Target[Seq[Path]])  = {
     new Target.Subprocess(