From 2fb5b569d30ac09cfda7ce6450c54d0fff6f32ae Mon Sep 17 00:00:00 2001 From: Li Haoyi Date: Sun, 5 Nov 2017 06:24:14 -0800 Subject: Re-organize `forge/` folder according to ordering of build phases: target definition, target discovery, and target evaluation --- core/src/main/scala/forge/Discovered.scala | 61 ------- core/src/main/scala/forge/Evaluator.scala | 192 -------------------- core/src/main/scala/forge/JsonFormatters.scala | 47 ----- core/src/main/scala/forge/Main.scala | 4 +- core/src/main/scala/forge/Target.scala | 173 ------------------ core/src/main/scala/forge/Tarjans.scala | 50 ------ core/src/main/scala/forge/ZipTarget.scala | 40 ----- core/src/main/scala/forge/define/Target.scala | 175 +++++++++++++++++++ core/src/main/scala/forge/define/ZipTarget.scala | 40 +++++ .../src/main/scala/forge/discover/Discovered.scala | 62 +++++++ core/src/main/scala/forge/discover/Labelled.scala | 8 + core/src/main/scala/forge/eval/Evaluator.scala | 193 +++++++++++++++++++++ core/src/main/scala/forge/eval/PathRef.scala | 60 +++++++ core/src/main/scala/forge/eval/Tarjans.scala | 51 ++++++ core/src/main/scala/forge/package.scala | 8 +- .../src/main/scala/forge/util/JsonFormatters.scala | 47 +++++ core/src/main/scala/forge/util/Labelled.scala | 8 - core/src/main/scala/forge/util/PathRef.scala | 60 ------- core/src/test/examples/javac/build.sc | 7 +- core/src/test/scala/forge/CacherTests.scala | 3 + core/src/test/scala/forge/EvaluationTests.scala | 3 + core/src/test/scala/forge/GraphTests.scala | 3 + .../src/test/scala/forge/JavaCompileJarTests.scala | 5 +- core/src/test/scala/forge/TarjanTests.scala | 1 + core/src/test/scala/forge/TestGraphs.scala | 2 +- core/src/test/scala/forge/TestUtil.scala | 2 + 26 files changed, 668 insertions(+), 637 deletions(-) delete mode 100644 core/src/main/scala/forge/Discovered.scala delete mode 100644 core/src/main/scala/forge/Evaluator.scala delete mode 100644 core/src/main/scala/forge/JsonFormatters.scala delete mode 100644 core/src/main/scala/forge/Target.scala delete mode 100644 core/src/main/scala/forge/Tarjans.scala delete mode 100644 core/src/main/scala/forge/ZipTarget.scala create mode 100644 core/src/main/scala/forge/define/Target.scala create mode 100644 core/src/main/scala/forge/define/ZipTarget.scala create mode 100644 core/src/main/scala/forge/discover/Discovered.scala create mode 100644 core/src/main/scala/forge/discover/Labelled.scala create mode 100644 core/src/main/scala/forge/eval/Evaluator.scala create mode 100644 core/src/main/scala/forge/eval/PathRef.scala create mode 100644 core/src/main/scala/forge/eval/Tarjans.scala create mode 100644 core/src/main/scala/forge/util/JsonFormatters.scala delete mode 100644 core/src/main/scala/forge/util/Labelled.scala delete mode 100644 core/src/main/scala/forge/util/PathRef.scala (limited to 'core') diff --git a/core/src/main/scala/forge/Discovered.scala b/core/src/main/scala/forge/Discovered.scala deleted file mode 100644 index e3aa31f9..00000000 --- a/core/src/main/scala/forge/Discovered.scala +++ /dev/null @@ -1,61 +0,0 @@ -package forge - -import forge.util.Labelled -import play.api.libs.json.Format - -import language.experimental.macros -import reflect.macros.blackbox.Context - -class Discovered[T](val value: Seq[(Seq[String], Format[_], T => Target[_])]){ - def apply(t: T) = value.map{case (a, f, b) => (a, f, b(t)) } - -} -object Discovered { - def makeTuple[T, V](path: Seq[String], func: T => Target[V])(implicit f: Format[V]) = { - (path, f, func) - } - - - def mapping[T: Discovered](t: T): Map[Target[_], Labelled[_]] = { - implicitly[Discovered[T]].apply(t) - .map(x => x._3 -> Labelled(x._3.asInstanceOf[Target[Any]], x._2.asInstanceOf[Format[Any]], x._1)) - .toMap - } - - implicit def apply[T]: Discovered[T] = macro applyImpl[T] - - def applyImpl[T: c.WeakTypeTag](c: Context): c.Expr[Discovered[T]] = { - import c.universe._ - val tpe = c.weakTypeTag[T].tpe - def rec(segments: List[String], t: c.Type): Seq[Seq[String]] = for { - m <- t.members.toSeq - if - (m.isTerm && (m.asTerm.isGetter || m.asTerm.isLazy)) || - m.isModule || - (m.isMethod && m.typeSignature.paramLists.isEmpty && m.typeSignature.resultType <:< c.weakTypeOf[Target[_]]) - - res <- { - val extendedSegments = m.name.toString :: segments - val self = - if (m.typeSignature.resultType <:< c.weakTypeOf[Target[_]]) Seq(extendedSegments) - else Nil - val children = rec(extendedSegments, m.typeSignature) - self ++ children - } - } yield res - - val reversedPaths = rec(Nil, tpe) - - val result = for(reversedPath <- reversedPaths.toList) yield { - val base = q"${TermName(c.freshName())}" - val segments = reversedPath.reverse.toList - val ident = segments.foldLeft[Tree](base)((prefix, name) => - q"$prefix.${TermName(name)}" - ) - - q"forge.Discovered.makeTuple($segments, ($base: $tpe) => $ident)" - } - - c.Expr[Discovered[T]](q"new _root_.forge.Discovered($result)") - } -} diff --git a/core/src/main/scala/forge/Evaluator.scala b/core/src/main/scala/forge/Evaluator.scala deleted file mode 100644 index 3ef605b7..00000000 --- a/core/src/main/scala/forge/Evaluator.scala +++ /dev/null @@ -1,192 +0,0 @@ -package forge - - -import play.api.libs.json.{Format, JsValue, Json} - -import scala.collection.mutable -import ammonite.ops._ -import forge.util.{Args, Labelled, MultiBiMap, OSet} -class Evaluator(workspacePath: Path, - labeling: Map[Target[_], Labelled[_]]){ - - def evaluate(targets: OSet[Target[_]]): Evaluator.Results = { - mkdir(workspacePath) - - val sortedGroups = Evaluator.groupAroundNamedTargets( - Evaluator.topoSortedTransitiveTargets(targets), - labeling - ) - - val evaluated = new OSet.Mutable[Target[_]] - val results = mutable.LinkedHashMap.empty[Target[_], Any] - - for (groupIndex <- sortedGroups.keys()){ - val group = sortedGroups.lookupKey(groupIndex) - - val (newResults, newEvaluated) = evaluateGroupCached( - group, - results, - sortedGroups - ) - evaluated.appendAll(newEvaluated) - for((k, v) <- newResults) results.put(k, v) - - } - - Evaluator.Results(targets.items.map(results), evaluated) - } - - def evaluateGroupCached(group: OSet[Target[_]], - results: collection.Map[Target[_], Any], - sortedGroups: MultiBiMap[Int, Target[_]]): (collection.Map[Target[_], Any], Seq[Target[_]]) = { - - - val (externalInputs, terminals) = partitionGroupInputOutput(group, results) - - val inputsHash = - externalInputs.toIterator.map(results).toVector.hashCode + - group.toIterator.map(_.sideHash).toVector.hashCode() - - val primeLabel = labeling(terminals.items(0)).segments - - - val targetDestPath = workspacePath / primeLabel - val metadataPath = targetDestPath / up / (targetDestPath.last + ".forge.json") - - val cached = for{ - json <- scala.util.Try(Json.parse(read.getInputStream(metadataPath))).toOption - (cachedHash, terminalResults) <- Json.fromJson[(Int, Seq[JsValue])](json).asOpt - if cachedHash == inputsHash - } yield terminalResults - - cached match{ - case Some(terminalResults) => - val newResults = mutable.LinkedHashMap.empty[Target[_], Any] - for((terminal, res) <- terminals.items.zip(terminalResults)){ - newResults(terminal) = labeling(terminal).format.reads(res).get - } - (newResults, Nil) - - case _ => - val (newResults, newEvaluated, terminalResults) = evaluateGroup(group, results, targetDestPath) - - write.over( - metadataPath, - Json.prettyPrint( - Json.toJson(inputsHash -> terminals.toList.map(terminalResults)) - ), - ) - - (newResults, newEvaluated) - } - } - - def partitionGroupInputOutput(group: OSet[Target[_]], - results: collection.Map[Target[_], Any]) = { - val allInputs = group.items.flatMap(_.inputs) - val (internalInputs, externalInputs) = allInputs.partition(group.contains) - val internalInputSet = internalInputs.toSet - val terminals = group.filter(!internalInputSet(_)) - (OSet.from(externalInputs.distinct), terminals) - } - - def evaluateGroup(group: OSet[Target[_]], - results: collection.Map[Target[_], Any], - targetDestPath: Path) = { - - rm(targetDestPath) - val terminalResults = mutable.LinkedHashMap.empty[Target[_], JsValue] - val newEvaluated = mutable.Buffer.empty[Target[_]] - val newResults = mutable.LinkedHashMap.empty[Target[_], Any] - for (target <- group.items) { - newEvaluated.append(target) - val targetInputValues = target.inputs.toVector.map(x => - newResults.getOrElse(x, results(x)) - ) - - val args = new Args(targetInputValues, targetDestPath) - - val res = target.evaluate(args) - for(targetLabel <- labeling.get(target)){ - terminalResults(target) = targetLabel - .format - .asInstanceOf[Format[Any]] - .writes(res.asInstanceOf[Any]) - } - newResults(target) = res - } - - (newResults, newEvaluated, terminalResults) - } - -} - - -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[_], Labelled[_]]): MultiBiMap[Int, Target[_]] = { - - val grouping = new MultiBiMap.Mutable[Int, Target[_]]() - - 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 upstreamGroup == targetGroup => - val upstreamTargets = grouping.removeAll(upstreamGroup) - - grouping.addAll(targetGroup, upstreamTargets) - case _ => //donothing - } - } - } - - val targetOrdering = topoSortedTargets.values.items.zipWithIndex.toMap - val output = new MultiBiMap.Mutable[Int, Target[_]] - - // Sort groups amongst themselves, and sort the contents of each group - // before aggregating it into the final output - for(g <- grouping.values().toArray.sortBy(g => targetOrdering(g.items(0)))){ - output.addAll(output.keys.length, g.toArray.sortBy(targetOrdering)) - } - output - } - - /** - * Takes the given targets, finds all the targets they transitively depend - * on, and sort them topologically. Fails if there are dependency cycles - */ - def topoSortedTransitiveTargets(sourceTargets: OSet[Target[_]]): TopoSorted = { - val transitiveTargets = new OSet.Mutable[Target[_]] - def rec(t: Target[_]): Unit = { - if (transitiveTargets.contains(t)) () // do nothing - else { - transitiveTargets.append(t) - t.inputs.foreach(rec) - } - } - - sourceTargets.items.foreach(rec) - val targetIndices = transitiveTargets.items.zipWithIndex.toMap - - val numberedEdges = - for(t <- transitiveTargets.items) - yield t.inputs.map(targetIndices) - - val sortedClusters = Tarjans(numberedEdges) - val nonTrivialClusters = sortedClusters.filter(_.length > 1) - assert(nonTrivialClusters.isEmpty, nonTrivialClusters) - new TopoSorted(OSet.from(sortedClusters.flatten.map(transitiveTargets.items))) - } -} \ No newline at end of file diff --git a/core/src/main/scala/forge/JsonFormatters.scala b/core/src/main/scala/forge/JsonFormatters.scala deleted file mode 100644 index 4e772128..00000000 --- a/core/src/main/scala/forge/JsonFormatters.scala +++ /dev/null @@ -1,47 +0,0 @@ -package forge - -import ammonite.ops.{Bytes, Path} -import play.api.libs.json._ -object JsonFormatters extends JsonFormatters -trait JsonFormatters { - implicit object pathFormat extends Format[ammonite.ops.Path]{ - def reads(json: JsValue) = json match{ - case JsString(v) => JsSuccess(Path(v)) - case _ => JsError("Paths must be a String") - } - def writes(o: Path) = JsString(o.toString) - } - - implicit object bytesFormat extends Format[Bytes]{ - def reads(json: JsValue) = json match{ - case JsString(v) => JsSuccess( - new Bytes(javax.xml.bind.DatatypeConverter.parseBase64Binary(v)) - ) - case _ => JsError("Bytes must be a String") - } - def writes(o: Bytes) = { - JsString(javax.xml.bind.DatatypeConverter.printBase64Binary(o.array)) - } - } - - implicit def EitherFormat[T: Format, V: Format] = new Format[Either[T, V]]{ - def reads(json: JsValue) = json match{ - case JsObject(struct) => - (struct.get("type"), struct.get("value")) match{ - case (Some(JsString("Left")), Some(v)) => implicitly[Reads[T]].reads(v).map(Left(_)) - case (Some(JsString("Right")), Some(v)) => implicitly[Reads[V]].reads(v).map(Right(_)) - case _ => JsError("Either object layout is unknown") - } - case _ => JsError("Either must be an Object") - } - def writes(o: Either[T, V]) = o match{ - case Left(v) => Json.obj("type" -> "Left", "value" -> implicitly[Writes[T]].writes(v)) - case Right(v) => Json.obj("type" -> "Right", "value" -> implicitly[Writes[V]].writes(v)) - } - } - - implicit lazy val crFormat: Format[ammonite.ops.CommandResult] = Json.format - implicit lazy val modFormat: Format[coursier.Module] = Json.format - implicit lazy val depFormat: Format[coursier.Dependency]= Json.format - implicit lazy val attrFormat: Format[coursier.Attributes] = Json.format -} diff --git a/core/src/main/scala/forge/Main.scala b/core/src/main/scala/forge/Main.scala index d919d0e2..e3b89f60 100644 --- a/core/src/main/scala/forge/Main.scala +++ b/core/src/main/scala/forge/Main.scala @@ -2,6 +2,8 @@ package forge import ammonite.ops._ import ammonite.util.{Name, Res} +import forge.discover.Discovered +import forge.eval.Evaluator import forge.util.OSet @@ -12,7 +14,7 @@ object Main { case Right(interp) => val result = ammonite.main.Scripts.runScript(pwd, Path(args(0), pwd), interp, Nil) - val (obj, discovered) = result.asInstanceOf[Res.Success[(Any, forge.Discovered[Any])]].s + val (obj, discovered) = result.asInstanceOf[Res.Success[(Any, Discovered[Any])]].s val mapping = Discovered.mapping(obj)(discovered) val workspacePath = pwd / 'target / 'javac val evaluator = new Evaluator(workspacePath, mapping) diff --git a/core/src/main/scala/forge/Target.scala b/core/src/main/scala/forge/Target.scala deleted file mode 100644 index 9aa4877e..00000000 --- a/core/src/main/scala/forge/Target.scala +++ /dev/null @@ -1,173 +0,0 @@ -package forge - - -import ammonite.ops.{CommandResult, ls, mkdir} -import forge.util.{Args, PathRef} -import play.api.libs.json.{Format, JsValue, Json} - -import scala.annotation.compileTimeOnly -import language.experimental.macros -import reflect.macros.blackbox.Context -import scala.collection.mutable - -abstract class Target[T] extends Target.Ops[T]{ - /** - * What other Targets does this Target depend on? - */ - val inputs: Seq[Target[_]] - - /** - * Evaluate this target - */ - def evaluate(args: Args): T - - /** - * Even if this target's inputs did not change, does it need to re-evaluate - * anyway? - */ - def sideHash: Int = 0 - - @compileTimeOnly("Target#apply() can only be used with a T{...} block") - def apply(): T = ??? -} - -object Target{ - trait Cacher{ - private[this] val cacherLazyMap = mutable.Map.empty[sourcecode.Enclosing, Target[_]] - protected[this] def cachedTarget[T](t: => Target[T]) - (implicit c: sourcecode.Enclosing): Target[T] = synchronized{ - cacherLazyMap.getOrElseUpdate(c, t).asInstanceOf[Target[T]] - } - } - class Target0[T](t: T) extends Target[T]{ - lazy val t0 = t - val inputs = Nil - def evaluate(args: Args) = t0 - } - def apply[T](t: Target[T]): Target[T] = macro impl0[T] - def apply[T](t: T): Target[T] = macro impl[T] - def impl0[T: c.WeakTypeTag](c: Context)(t: c.Expr[Target[T]]): c.Expr[Target[T]] = { - wrapCached(c)(t.tree) - } - def impl[T: c.WeakTypeTag](c: Context)(t: c.Expr[T]): c.Expr[Target[T]] = { - import c.universe._ - def rec(t: Tree): Iterator[c.Tree] = Iterator(t) ++ t.children.flatMap(rec(_)) - val bound = collection.mutable.Buffer.empty[(c.Tree, Symbol)] - val targetApplySym = c.universe.typeOf[Target[_]].member(TermName("apply")) - // Derived from @olafurpg's - // https://gist.github.com/olafurpg/596d62f87bf3360a29488b725fbc7608 - - val (startPos, endPos) = rec(t.tree) - .map(t => (t.pos.start, t.pos.end)) - .reduce[(Int, Int)]{ case ((s1, e1), (s2, e2)) => (math.min(s1, s2), math.max(e1, e2))} - - val macroSource = t.tree.pos.source - val transformed = c.internal.typingTransform(t.tree) { - case (t @ q"$fun.apply()", api) if t.symbol == targetApplySym => - - val used = rec(t) - val banned = used.filter(x => - x.symbol.pos.source == macroSource && - x.symbol.pos.start >= startPos && - x.symbol.pos.end <= endPos - ) - if (banned.hasNext){ - val banned0 = banned.next() - c.abort( - banned0.pos, - "Target#apply() call cannot use `" + banned0.symbol + "` defined within the T{...} block" - ) - } - val tempName = c.freshName(TermName("tmp")) - val tempSym = c.internal.newTermSymbol(api.currentOwner, tempName) - c.internal.setInfo(tempSym, t.tpe) - val tempIdent = Ident(tempSym) - c.internal.setType(tempIdent, t.tpe) - bound.append((fun, tempSym)) - tempIdent - case (t, api) => api.default(t) - } - - val (exprs, symbols) = bound.unzip - - val bindings = symbols.map(c.internal.valDef(_)) - - wrapCached(c)(q"forge.zipMap(..$exprs){ (..$bindings) => $transformed }") - } - def wrapCached[T](c: Context)(t: c.Tree) = { - import c.universe._ - val owner = c.internal.enclosingOwner - val ownerIsCacherClass = owner.owner.isClass && owner.owner.asClass.baseClasses.exists(_.fullName == "forge.Target.Cacher") - - if (ownerIsCacherClass && !owner.isMethod){ - c.abort( - c.enclosingPosition, - "T{} members defined in a Cacher class/trait/object body must be defs" - ) - }else{ - val embedded = - if (!ownerIsCacherClass) t - else q"this.cachedTarget($t)" - - c.Expr[Target[T]](embedded) - } - } - - abstract class Ops[T]{ this: Target[T] => - def map[V](f: T => V) = new Target.Mapped(this, f) - - def filter(f: T => Boolean) = this - def withFilter(f: T => Boolean) = this - def zip[V](other: Target[V]) = new Target.Zipped(this, other) - - } - - def traverse[T](source: Seq[Target[T]]) = { - new Traverse[T](source) - } - class Traverse[T](val inputs: Seq[Target[T]]) extends Target[Seq[T]]{ - def evaluate(args: Args) = { - for (i <- 0 until args.length) - yield args(i).asInstanceOf[T] - } - - } - class Mapped[T, V](source: Target[T], f: T => V) extends Target[V]{ - def evaluate(args: Args) = f(args(0)) - val inputs = List(source) - } - class Zipped[T, V](source1: Target[T], - source2: Target[V]) extends Target[(T, V)]{ - def evaluate(args: Args) = (args(0), args(1)) - val inputs = List(source1, source2) - } - - def path(path: ammonite.ops.Path) = new Path(path) - class Path(path: ammonite.ops.Path) extends Target[PathRef]{ - def handle = PathRef(path) - def evaluate(args: Args) = handle - override def sideHash = handle.hashCode() - val inputs = Nil - } - - class Subprocess(val inputs: Seq[Target[_]], - command: Args => Seq[String]) extends Target[Subprocess.Result] { - - def evaluate(args: Args) = { - mkdir(args.dest) - import ammonite.ops._ - implicit val path = ammonite.ops.Path(args.dest, pwd) - val toTarget = () // Shadow the implicit conversion :/ - val output = %%(command(args)) - assert(output.exitCode == 0) - Subprocess.Result(output, PathRef(args.dest)) - } - } - object Subprocess{ - case class Result(result: ammonite.ops.CommandResult, dest: PathRef) - object Result{ - private implicit val crFormat: Format[CommandResult] = JsonFormatters.crFormat - implicit val tsFormat: Format[Target.Subprocess.Result] = Json.format - } - } -} diff --git a/core/src/main/scala/forge/Tarjans.scala b/core/src/main/scala/forge/Tarjans.scala deleted file mode 100644 index 9831fe7f..00000000 --- a/core/src/main/scala/forge/Tarjans.scala +++ /dev/null @@ -1,50 +0,0 @@ -package forge - -import collection.mutable -// Adapted from -// https://github.com/indy256/codelibrary/blob/c52247216258e84aac442a23273b7d8306ef757b/java/src/SCCTarjan.java -object Tarjans { - def apply(graph0: Seq[Seq[Int]]): Seq[Seq[Int]] = { - val graph = graph0.map(_.toArray).toArray - val n = graph.length - val visited = new Array[Boolean](n) - val stack = mutable.ArrayBuffer.empty[Integer] - var time = 0 - val lowlink = new Array[Int](n) - val components = mutable.ArrayBuffer.empty[Seq[Int]] - - - for (u <- 0 until n) { - if (!visited(u)) dfs(u) - } - - def dfs(u: Int): Unit = { - lowlink(u) = time - time += 1 - visited(u) = true - stack.append(u) - var isComponentRoot = true - for (v <- graph(u)) { - if (!visited(v)) dfs(v) - if (lowlink(u) > lowlink(v)) { - lowlink(u) = lowlink(v) - isComponentRoot = false - } - } - if (isComponentRoot) { - val component = mutable.Buffer.empty[Int] - - var done = false - while (!done) { - val x = stack.last - stack.remove(stack.length - 1) - component.append(x) - lowlink(x) = Integer.MAX_VALUE - if (x == u) done = true - } - components.append(component) - } - } - components - } -} \ No newline at end of file diff --git a/core/src/main/scala/forge/ZipTarget.scala b/core/src/main/scala/forge/ZipTarget.scala deleted file mode 100644 index e02bbc19..00000000 --- a/core/src/main/scala/forge/ZipTarget.scala +++ /dev/null @@ -1,40 +0,0 @@ -package forge - -import forge.util.Args - -object ZipTarget -trait ZipTarget { - val T = Target - type T[V] = Target[V] - def zipMap[R]()(f: () => R) = new Target.Target0(f()) - def zipMap[A, R](a: T[A])(f: A => R) = a.map(f) - def zipMap[A, B, R](a: T[A], b: T[B])(f: (A, B) => R) = zip(a, b).map(f.tupled) - def zipMap[A, B, C, R](a: T[A], b: T[B], c: T[C])(f: (A, B, C) => R) = zip(a, b, c).map(f.tupled) - def zipMap[A, B, C, D, R](a: T[A], b: T[B], c: T[C], d: T[D])(f: (A, B, C, D) => R) = zip(a, b, c, d).map(f.tupled) - def zipMap[A, B, C, D, E, R](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E])(f: (A, B, C, D, E) => R) = zip(a, b, c, d, e).map(f.tupled) - def zipMap[A, B, C, D, E, F, R](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E], f: T[F])(cb: (A, B, C, D, E, F) => R) = zip(a, b, c, d, e, f).map(cb.tupled) - def zipMap[A, B, C, D, E, F, G, R](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E], f: T[F], g: T[G])(cb: (A, B, C, D, E, F, G) => R) = zip(a, b, c, d, e, f, g).map(cb.tupled) - def zip() = new Target.Target0(()) - def zip[A](a: T[A]) = a.map(Tuple1(_)) - def zip[A, B](a: T[A], b: T[B]) = a.zip(b) - def zip[A, B, C](a: T[A], b: T[B], c: T[C]) = new T[(A, B, C)]{ - val inputs = Seq(a, b, c) - def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2)) - } - def zip[A, B, C, D](a: T[A], b: T[B], c: T[C], d: T[D]) = new T[(A, B, C, D)]{ - val inputs = Seq(a, b, c, d) - def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2), args[D](3)) - } - def zip[A, B, C, D, E](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E]) = new T[(A, B, C, D, E)]{ - val inputs = Seq(a, b, c, d, e) - def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2), args[D](3), args[E](4)) - } - def zip[A, B, C, D, E, F](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E], f: T[F]) = new T[(A, B, C, D, E, F)]{ - val inputs = Seq(a, b, c, d, e, f) - def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2), args[D](3), args[E](4), args[F](5)) - } - def zip[A, B, C, D, E, F, G](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E], f: T[F], g: T[G]) = new T[(A, B, C, D, E, F, G)]{ - val inputs = Seq(a, b, c, d, e, f, g) - def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2), args[D](3), args[E](4), args[F](5), args[G](6)) - } -} diff --git a/core/src/main/scala/forge/define/Target.scala b/core/src/main/scala/forge/define/Target.scala new file mode 100644 index 00000000..1d8ecdee --- /dev/null +++ b/core/src/main/scala/forge/define/Target.scala @@ -0,0 +1,175 @@ +package forge.define + +import ammonite.ops.{CommandResult, mkdir} +import forge.eval.PathRef +import forge.util.{Args, JsonFormatters} +import play.api.libs.json.{Format, Json} + +import scala.annotation.compileTimeOnly +import scala.collection.mutable +import scala.language.experimental.macros +import scala.reflect.macros.blackbox.Context + +abstract class Target[T] extends Target.Ops[T]{ + /** + * What other Targets does this Target depend on? + */ + val inputs: Seq[Target[_]] + + /** + * Evaluate this target + */ + def evaluate(args: Args): T + + /** + * Even if this target's inputs did not change, does it need to re-evaluate + * anyway? + */ + def sideHash: Int = 0 + + @compileTimeOnly("Target#apply() can only be used with a T{...} block") + def apply(): T = ??? +} + +object Target{ + trait Cacher{ + private[this] val cacherLazyMap = mutable.Map.empty[sourcecode.Enclosing, Target[_]] + protected[this] def cachedTarget[T](t: => Target[T]) + (implicit c: sourcecode.Enclosing): Target[T] = synchronized{ + cacherLazyMap.getOrElseUpdate(c, t).asInstanceOf[Target[T]] + } + } + class Target0[T](t: T) extends Target[T]{ + lazy val t0 = t + val inputs = Nil + def evaluate(args: Args) = t0 + } + def apply[T](t: Target[T]): Target[T] = macro impl0[T] + def apply[T](t: T): Target[T] = macro impl[T] + def impl0[T: c.WeakTypeTag](c: Context)(t: c.Expr[Target[T]]): c.Expr[Target[T]] = { + wrapCached(c)(t.tree) + } + def impl[T: c.WeakTypeTag](c: Context)(t: c.Expr[T]): c.Expr[Target[T]] = { + import c.universe._ + def rec(t: Tree): Iterator[c.Tree] = Iterator(t) ++ t.children.flatMap(rec(_)) + val bound = collection.mutable.Buffer.empty[(c.Tree, Symbol)] + val targetApplySym = c.universe.typeOf[Target[_]].member(TermName("apply")) + // Derived from @olafurpg's + // https://gist.github.com/olafurpg/596d62f87bf3360a29488b725fbc7608 + + val (startPos, endPos) = rec(t.tree) + .map(t => (t.pos.start, t.pos.end)) + .reduce[(Int, Int)]{ case ((s1, e1), (s2, e2)) => (math.min(s1, s2), math.max(e1, e2))} + + val macroSource = t.tree.pos.source + val transformed = c.internal.typingTransform(t.tree) { + case (t @ q"$fun.apply()", api) if t.symbol == targetApplySym => + + val used = rec(t) + val banned = used.filter(x => + x.symbol.pos.source == macroSource && + x.symbol.pos.start >= startPos && + x.symbol.pos.end <= endPos + ) + if (banned.hasNext){ + val banned0 = banned.next() + c.abort( + banned0.pos, + "Target#apply() call cannot use `" + banned0.symbol + "` defined within the T{...} block" + ) + } + val tempName = c.freshName(TermName("tmp")) + val tempSym = c.internal.newTermSymbol(api.currentOwner, tempName) + c.internal.setInfo(tempSym, t.tpe) + val tempIdent = Ident(tempSym) + c.internal.setType(tempIdent, t.tpe) + bound.append((fun, tempSym)) + tempIdent + case (t, api) => api.default(t) + } + + val (exprs, symbols) = bound.unzip + + val bindings = symbols.map(c.internal.valDef(_)) + + wrapCached(c)(q"forge.zipMap(..$exprs){ (..$bindings) => $transformed }") + } + def wrapCached[T](c: Context)(t: c.Tree) = { + import c.universe._ + val owner = c.internal.enclosingOwner + val ownerIsCacherClass = + owner.owner.isClass && + owner.owner.asClass.baseClasses.exists(_.fullName == "forge.define.Target.Cacher") + + if (ownerIsCacherClass && !owner.isMethod){ + c.abort( + c.enclosingPosition, + "T{} members defined in a Cacher class/trait/object body must be defs" + ) + }else{ + val embedded = + if (!ownerIsCacherClass) t + else q"this.cachedTarget($t)" + + c.Expr[Target[T]](embedded) + } + } + + abstract class Ops[T]{ this: Target[T] => + def map[V](f: T => V) = new Target.Mapped(this, f) + + def filter(f: T => Boolean) = this + def withFilter(f: T => Boolean) = this + def zip[V](other: Target[V]) = new Target.Zipped(this, other) + + } + + def traverse[T](source: Seq[Target[T]]) = { + new Traverse[T](source) + } + class Traverse[T](val inputs: Seq[Target[T]]) extends Target[Seq[T]]{ + def evaluate(args: Args) = { + for (i <- 0 until args.length) + yield args(i).asInstanceOf[T] + } + + } + class Mapped[T, V](source: Target[T], f: T => V) extends Target[V]{ + def evaluate(args: Args) = f(args(0)) + val inputs = List(source) + } + class Zipped[T, V](source1: Target[T], + source2: Target[V]) extends Target[(T, V)]{ + def evaluate(args: Args) = (args(0), args(1)) + val inputs = List(source1, source2) + } + + def path(path: ammonite.ops.Path) = new Path(path) + class Path(path: ammonite.ops.Path) extends Target[PathRef]{ + def handle = PathRef(path) + def evaluate(args: Args) = handle + override def sideHash = handle.hashCode() + val inputs = Nil + } + + class Subprocess(val inputs: Seq[Target[_]], + command: Args => Seq[String]) extends Target[Subprocess.Result] { + + def evaluate(args: Args) = { + mkdir(args.dest) + import ammonite.ops._ + implicit val path = ammonite.ops.Path(args.dest, pwd) + val toTarget = () // Shadow the implicit conversion :/ + val output = %%(command(args)) + assert(output.exitCode == 0) + Subprocess.Result(output, PathRef(args.dest)) + } + } + object Subprocess{ + case class Result(result: ammonite.ops.CommandResult, dest: PathRef) + object Result{ + private implicit val crFormat: Format[CommandResult] = JsonFormatters.crFormat + implicit val tsFormat: Format[Target.Subprocess.Result] = Json.format + } + } +} diff --git a/core/src/main/scala/forge/define/ZipTarget.scala b/core/src/main/scala/forge/define/ZipTarget.scala new file mode 100644 index 00000000..1faef07e --- /dev/null +++ b/core/src/main/scala/forge/define/ZipTarget.scala @@ -0,0 +1,40 @@ +package forge.define + +import forge.util.Args + +object ZipTarget +trait ZipTarget { + val T = Target + type T[V] = Target[V] + def zipMap[R]()(f: () => R) = new Target.Target0(f()) + def zipMap[A, R](a: T[A])(f: A => R) = a.map(f) + def zipMap[A, B, R](a: T[A], b: T[B])(f: (A, B) => R) = zip(a, b).map(f.tupled) + def zipMap[A, B, C, R](a: T[A], b: T[B], c: T[C])(f: (A, B, C) => R) = zip(a, b, c).map(f.tupled) + def zipMap[A, B, C, D, R](a: T[A], b: T[B], c: T[C], d: T[D])(f: (A, B, C, D) => R) = zip(a, b, c, d).map(f.tupled) + def zipMap[A, B, C, D, E, R](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E])(f: (A, B, C, D, E) => R) = zip(a, b, c, d, e).map(f.tupled) + def zipMap[A, B, C, D, E, F, R](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E], f: T[F])(cb: (A, B, C, D, E, F) => R) = zip(a, b, c, d, e, f).map(cb.tupled) + def zipMap[A, B, C, D, E, F, G, R](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E], f: T[F], g: T[G])(cb: (A, B, C, D, E, F, G) => R) = zip(a, b, c, d, e, f, g).map(cb.tupled) + def zip() = new Target.Target0(()) + def zip[A](a: T[A]) = a.map(Tuple1(_)) + def zip[A, B](a: T[A], b: T[B]) = a.zip(b) + def zip[A, B, C](a: T[A], b: T[B], c: T[C]) = new T[(A, B, C)]{ + val inputs = Seq(a, b, c) + def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2)) + } + def zip[A, B, C, D](a: T[A], b: T[B], c: T[C], d: T[D]) = new T[(A, B, C, D)]{ + val inputs = Seq(a, b, c, d) + def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2), args[D](3)) + } + def zip[A, B, C, D, E](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E]) = new T[(A, B, C, D, E)]{ + val inputs = Seq(a, b, c, d, e) + def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2), args[D](3), args[E](4)) + } + def zip[A, B, C, D, E, F](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E], f: T[F]) = new T[(A, B, C, D, E, F)]{ + val inputs = Seq(a, b, c, d, e, f) + def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2), args[D](3), args[E](4), args[F](5)) + } + def zip[A, B, C, D, E, F, G](a: T[A], b: T[B], c: T[C], d: T[D], e: T[E], f: T[F], g: T[G]) = new T[(A, B, C, D, E, F, G)]{ + val inputs = Seq(a, b, c, d, e, f, g) + def evaluate(args: Args) = (args[A](0), args[B](1), args[C](2), args[D](3), args[E](4), args[F](5), args[G](6)) + } +} diff --git a/core/src/main/scala/forge/discover/Discovered.scala b/core/src/main/scala/forge/discover/Discovered.scala new file mode 100644 index 00000000..964732be --- /dev/null +++ b/core/src/main/scala/forge/discover/Discovered.scala @@ -0,0 +1,62 @@ +package forge.discover + +import forge.define.Target + +import play.api.libs.json.Format + +import scala.language.experimental.macros +import scala.reflect.macros.blackbox.Context + +class Discovered[T](val value: Seq[(Seq[String], Format[_], T => Target[_])]){ + def apply(t: T) = value.map{case (a, f, b) => (a, f, b(t)) } + +} +object Discovered { + def makeTuple[T, V](path: Seq[String], func: T => Target[V])(implicit f: Format[V]) = { + (path, f, func) + } + + + def mapping[T: Discovered](t: T): Map[Target[_], Labelled[_]] = { + implicitly[Discovered[T]].apply(t) + .map(x => x._3 -> Labelled(x._3.asInstanceOf[Target[Any]], x._2.asInstanceOf[Format[Any]], x._1)) + .toMap + } + + implicit def apply[T]: Discovered[T] = macro applyImpl[T] + + def applyImpl[T: c.WeakTypeTag](c: Context): c.Expr[Discovered[T]] = { + import c.universe._ + val tpe = c.weakTypeTag[T].tpe + def rec(segments: List[String], t: c.Type): Seq[Seq[String]] = for { + m <- t.members.toSeq + if + (m.isTerm && (m.asTerm.isGetter || m.asTerm.isLazy)) || + m.isModule || + (m.isMethod && m.typeSignature.paramLists.isEmpty && m.typeSignature.resultType <:< c.weakTypeOf[Target[_]]) + + res <- { + val extendedSegments = m.name.toString :: segments + val self = + if (m.typeSignature.resultType <:< c.weakTypeOf[Target[_]]) Seq(extendedSegments) + else Nil + val children = rec(extendedSegments, m.typeSignature) + self ++ children + } + } yield res + + val reversedPaths = rec(Nil, tpe) + + val result = for(reversedPath <- reversedPaths.toList) yield { + val base = q"${TermName(c.freshName())}" + val segments = reversedPath.reverse.toList + val ident = segments.foldLeft[Tree](base)((prefix, name) => + q"$prefix.${TermName(name)}" + ) + + q"forge.discover.Discovered.makeTuple($segments, ($base: $tpe) => $ident)" + } + + c.Expr[Discovered[T]](q"new _root_.forge.discover.Discovered($result)") + } +} diff --git a/core/src/main/scala/forge/discover/Labelled.scala b/core/src/main/scala/forge/discover/Labelled.scala new file mode 100644 index 00000000..25c74e9f --- /dev/null +++ b/core/src/main/scala/forge/discover/Labelled.scala @@ -0,0 +1,8 @@ +package forge.discover + +import forge.define.Target +import play.api.libs.json.Format + +case class Labelled[T](target: Target[T], + format: Format[T], + segments: Seq[String]) diff --git a/core/src/main/scala/forge/eval/Evaluator.scala b/core/src/main/scala/forge/eval/Evaluator.scala new file mode 100644 index 00000000..19cd3236 --- /dev/null +++ b/core/src/main/scala/forge/eval/Evaluator.scala @@ -0,0 +1,193 @@ +package forge.eval + +import ammonite.ops._ +import forge.define.Target +import forge.discover.Labelled +import forge.util.{Args, MultiBiMap, OSet} +import play.api.libs.json.{Format, JsValue, Json} + +import scala.collection.mutable +class Evaluator(workspacePath: Path, + labeling: Map[Target[_], Labelled[_]]){ + + def evaluate(targets: OSet[Target[_]]): Evaluator.Results = { + mkdir(workspacePath) + + val sortedGroups = Evaluator.groupAroundNamedTargets( + Evaluator.topoSortedTransitiveTargets(targets), + labeling + ) + + val evaluated = new OSet.Mutable[Target[_]] + val results = mutable.LinkedHashMap.empty[Target[_], Any] + + for (groupIndex <- sortedGroups.keys()){ + val group = sortedGroups.lookupKey(groupIndex) + + val (newResults, newEvaluated) = evaluateGroupCached( + group, + results, + sortedGroups + ) + evaluated.appendAll(newEvaluated) + for((k, v) <- newResults) results.put(k, v) + + } + + Evaluator.Results(targets.items.map(results), evaluated) + } + + def evaluateGroupCached(group: OSet[Target[_]], + results: collection.Map[Target[_], Any], + sortedGroups: MultiBiMap[Int, Target[_]]): (collection.Map[Target[_], Any], Seq[Target[_]]) = { + + + val (externalInputs, terminals) = partitionGroupInputOutput(group, results) + + val inputsHash = + externalInputs.toIterator.map(results).toVector.hashCode + + group.toIterator.map(_.sideHash).toVector.hashCode() + + val primeLabel = labeling(terminals.items(0)).segments + + + val targetDestPath = workspacePath / primeLabel + val metadataPath = targetDestPath / up / (targetDestPath.last + ".forge.json") + + val cached = for{ + json <- scala.util.Try(Json.parse(read.getInputStream(metadataPath))).toOption + (cachedHash, terminalResults) <- Json.fromJson[(Int, Seq[JsValue])](json).asOpt + if cachedHash == inputsHash + } yield terminalResults + + cached match{ + case Some(terminalResults) => + val newResults = mutable.LinkedHashMap.empty[Target[_], Any] + for((terminal, res) <- terminals.items.zip(terminalResults)){ + newResults(terminal) = labeling(terminal).format.reads(res).get + } + (newResults, Nil) + + case _ => + val (newResults, newEvaluated, terminalResults) = evaluateGroup(group, results, targetDestPath) + + write.over( + metadataPath, + Json.prettyPrint( + Json.toJson(inputsHash -> terminals.toList.map(terminalResults)) + ), + ) + + (newResults, newEvaluated) + } + } + + def partitionGroupInputOutput(group: OSet[Target[_]], + results: collection.Map[Target[_], Any]) = { + val allInputs = group.items.flatMap(_.inputs) + val (internalInputs, externalInputs) = allInputs.partition(group.contains) + val internalInputSet = internalInputs.toSet + val terminals = group.filter(!internalInputSet(_)) + (OSet.from(externalInputs.distinct), terminals) + } + + def evaluateGroup(group: OSet[Target[_]], + results: collection.Map[Target[_], Any], + targetDestPath: Path) = { + + rm(targetDestPath) + val terminalResults = mutable.LinkedHashMap.empty[Target[_], JsValue] + val newEvaluated = mutable.Buffer.empty[Target[_]] + val newResults = mutable.LinkedHashMap.empty[Target[_], Any] + for (target <- group.items) { + newEvaluated.append(target) + val targetInputValues = target.inputs.toVector.map(x => + newResults.getOrElse(x, results(x)) + ) + + val args = new Args(targetInputValues, targetDestPath) + + val res = target.evaluate(args) + for(targetLabel <- labeling.get(target)){ + terminalResults(target) = targetLabel + .format + .asInstanceOf[Format[Any]] + .writes(res.asInstanceOf[Any]) + } + newResults(target) = res + } + + (newResults, newEvaluated, terminalResults) + } + +} + + +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[_], Labelled[_]]): MultiBiMap[Int, Target[_]] = { + + val grouping = new MultiBiMap.Mutable[Int, Target[_]]() + + 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 upstreamGroup == targetGroup => + val upstreamTargets = grouping.removeAll(upstreamGroup) + + grouping.addAll(targetGroup, upstreamTargets) + case _ => //donothing + } + } + } + + val targetOrdering = topoSortedTargets.values.items.zipWithIndex.toMap + val output = new MultiBiMap.Mutable[Int, Target[_]] + + // Sort groups amongst themselves, and sort the contents of each group + // before aggregating it into the final output + for(g <- grouping.values().toArray.sortBy(g => targetOrdering(g.items(0)))){ + output.addAll(output.keys.length, g.toArray.sortBy(targetOrdering)) + } + output + } + + /** + * Takes the given targets, finds all the targets they transitively depend + * on, and sort them topologically. Fails if there are dependency cycles + */ + def topoSortedTransitiveTargets(sourceTargets: OSet[Target[_]]): TopoSorted = { + val transitiveTargets = new OSet.Mutable[Target[_]] + def rec(t: Target[_]): Unit = { + if (transitiveTargets.contains(t)) () // do nothing + else { + transitiveTargets.append(t) + t.inputs.foreach(rec) + } + } + + sourceTargets.items.foreach(rec) + val targetIndices = transitiveTargets.items.zipWithIndex.toMap + + val numberedEdges = + for(t <- transitiveTargets.items) + yield t.inputs.map(targetIndices) + + val sortedClusters = Tarjans(numberedEdges) + val nonTrivialClusters = sortedClusters.filter(_.length > 1) + assert(nonTrivialClusters.isEmpty, nonTrivialClusters) + new TopoSorted(OSet.from(sortedClusters.flatten.map(transitiveTargets.items))) + } +} \ No newline at end of file diff --git a/core/src/main/scala/forge/eval/PathRef.scala b/core/src/main/scala/forge/eval/PathRef.scala new file mode 100644 index 00000000..1c9bc700 --- /dev/null +++ b/core/src/main/scala/forge/eval/PathRef.scala @@ -0,0 +1,60 @@ +package forge.eval + +import java.io.IOException +import java.nio.file.attribute.BasicFileAttributes +import java.nio.file.{FileVisitResult, FileVisitor} +import java.nio.{file => jnio} +import java.security.MessageDigest + +import ammonite.ops.Path +import forge.util.JsonFormatters +import play.api.libs.json.{Format, Json} + + +/** + * A wrapper around `ammonite.ops.Path` that calculates it's hashcode based + * on the contents of the filesystem underneath it. Used to ensure filesystem + * changes can bust caches which are keyed off hashcodes. + */ +case class PathRef(path: ammonite.ops.Path){ + val md5Hash = { + val digest = MessageDigest.getInstance("MD5") + + val buffer = new Array[Byte](16 * 1024) + jnio.Files.walkFileTree( + path.toNIO, + new FileVisitor[jnio.Path] { + def preVisitDirectory(dir: jnio.Path, attrs: BasicFileAttributes) = { + digest.update(dir.toAbsolutePath.toString.getBytes) + FileVisitResult.CONTINUE + } + + def visitFile(file: jnio.Path, attrs: BasicFileAttributes) = { + digest.update(file.toAbsolutePath.toString.getBytes) + val is = jnio.Files.newInputStream(file) + def rec(): Unit = { + val length = is.read(buffer) + if (length != -1){ + digest.update(buffer, 0, length) + rec() + } + } + rec() + FileVisitResult.CONTINUE + } + + def visitFileFailed(file: jnio.Path, exc: IOException) = FileVisitResult.CONTINUE + def postVisitDirectory(dir: jnio.Path, exc: IOException) = FileVisitResult.CONTINUE + } + ) + + java.util.Arrays.hashCode(digest.digest()) + + } + override def hashCode() = md5Hash +} + +object PathRef{ + private implicit val pathFormat: Format[Path] = JsonFormatters.pathFormat + implicit def jsonFormatter: Format[PathRef] = Json.format +} diff --git a/core/src/main/scala/forge/eval/Tarjans.scala b/core/src/main/scala/forge/eval/Tarjans.scala new file mode 100644 index 00000000..15d6779c --- /dev/null +++ b/core/src/main/scala/forge/eval/Tarjans.scala @@ -0,0 +1,51 @@ +package forge.eval + +import scala.collection.mutable + +// Adapted from +// https://github.com/indy256/codelibrary/blob/c52247216258e84aac442a23273b7d8306ef757b/java/src/SCCTarjan.java +object Tarjans { + def apply(graph0: Seq[Seq[Int]]): Seq[Seq[Int]] = { + val graph = graph0.map(_.toArray).toArray + val n = graph.length + val visited = new Array[Boolean](n) + val stack = mutable.ArrayBuffer.empty[Integer] + var time = 0 + val lowlink = new Array[Int](n) + val components = mutable.ArrayBuffer.empty[Seq[Int]] + + + for (u <- 0 until n) { + if (!visited(u)) dfs(u) + } + + def dfs(u: Int): Unit = { + lowlink(u) = time + time += 1 + visited(u) = true + stack.append(u) + var isComponentRoot = true + for (v <- graph(u)) { + if (!visited(v)) dfs(v) + if (lowlink(u) > lowlink(v)) { + lowlink(u) = lowlink(v) + isComponentRoot = false + } + } + if (isComponentRoot) { + val component = mutable.Buffer.empty[Int] + + var done = false + while (!done) { + val x = stack.last + stack.remove(stack.length - 1) + component.append(x) + lowlink(x) = Integer.MAX_VALUE + if (x == u) done = true + } + components.append(component) + } + } + components + } +} diff --git a/core/src/main/scala/forge/package.scala b/core/src/main/scala/forge/package.scala index 4163237e..58401c64 100644 --- a/core/src/main/scala/forge/package.scala +++ b/core/src/main/scala/forge/package.scala @@ -1 +1,7 @@ -package object forge extends ZipTarget with JsonFormatters +import forge.define.ZipTarget +import forge.util.JsonFormatters + +package object forge extends ZipTarget with JsonFormatters{ + val Target = define.Target + type Target[T] = define.Target[T] +} diff --git a/core/src/main/scala/forge/util/JsonFormatters.scala b/core/src/main/scala/forge/util/JsonFormatters.scala new file mode 100644 index 00000000..d9f07fc8 --- /dev/null +++ b/core/src/main/scala/forge/util/JsonFormatters.scala @@ -0,0 +1,47 @@ +package forge.util + +import ammonite.ops.{Bytes, Path} +import play.api.libs.json._ +object JsonFormatters extends JsonFormatters +trait JsonFormatters { + implicit object pathFormat extends Format[ammonite.ops.Path]{ + def reads(json: JsValue) = json match{ + case JsString(v) => JsSuccess(Path(v)) + case _ => JsError("Paths must be a String") + } + def writes(o: Path) = JsString(o.toString) + } + + implicit object bytesFormat extends Format[Bytes]{ + def reads(json: JsValue) = json match{ + case JsString(v) => JsSuccess( + new Bytes(javax.xml.bind.DatatypeConverter.parseBase64Binary(v)) + ) + case _ => JsError("Bytes must be a String") + } + def writes(o: Bytes) = { + JsString(javax.xml.bind.DatatypeConverter.printBase64Binary(o.array)) + } + } + + implicit def EitherFormat[T: Format, V: Format] = new Format[Either[T, V]]{ + def reads(json: JsValue) = json match{ + case JsObject(struct) => + (struct.get("type"), struct.get("value")) match{ + case (Some(JsString("Left")), Some(v)) => implicitly[Reads[T]].reads(v).map(Left(_)) + case (Some(JsString("Right")), Some(v)) => implicitly[Reads[V]].reads(v).map(Right(_)) + case _ => JsError("Either object layout is unknown") + } + case _ => JsError("Either must be an Object") + } + def writes(o: Either[T, V]) = o match{ + case Left(v) => Json.obj("type" -> "Left", "value" -> implicitly[Writes[T]].writes(v)) + case Right(v) => Json.obj("type" -> "Right", "value" -> implicitly[Writes[V]].writes(v)) + } + } + + implicit lazy val crFormat: Format[ammonite.ops.CommandResult] = Json.format + implicit lazy val modFormat: Format[coursier.Module] = Json.format + implicit lazy val depFormat: Format[coursier.Dependency]= Json.format + implicit lazy val attrFormat: Format[coursier.Attributes] = Json.format +} diff --git a/core/src/main/scala/forge/util/Labelled.scala b/core/src/main/scala/forge/util/Labelled.scala deleted file mode 100644 index a79d2d93..00000000 --- a/core/src/main/scala/forge/util/Labelled.scala +++ /dev/null @@ -1,8 +0,0 @@ -package forge.util - -import forge.Target -import play.api.libs.json.Format - -case class Labelled[T](target: Target[T], - format: Format[T], - segments: Seq[String]) diff --git a/core/src/main/scala/forge/util/PathRef.scala b/core/src/main/scala/forge/util/PathRef.scala deleted file mode 100644 index 333f225e..00000000 --- a/core/src/main/scala/forge/util/PathRef.scala +++ /dev/null @@ -1,60 +0,0 @@ -package forge -package util - -import java.io.IOException -import java.nio.file.{FileVisitResult, FileVisitor} -import java.nio.file.attribute.BasicFileAttributes -import java.security.MessageDigest -import java.nio.{file => jnio} - -import ammonite.ops.Path -import play.api.libs.json.{Format, Json} - - -/** - * A wrapper around `ammonite.ops.Path` that calculates it's hashcode based - * on the contents of the filesystem underneath it. Used to ensure filesystem - * changes can bust caches which are keyed off hashcodes. - */ -case class PathRef(path: ammonite.ops.Path){ - val md5Hash = { - val digest = MessageDigest.getInstance("MD5") - - val buffer = new Array[Byte](16 * 1024) - jnio.Files.walkFileTree( - path.toNIO, - new FileVisitor[jnio.Path] { - def preVisitDirectory(dir: jnio.Path, attrs: BasicFileAttributes) = { - digest.update(dir.toAbsolutePath.toString.getBytes) - FileVisitResult.CONTINUE - } - - def visitFile(file: jnio.Path, attrs: BasicFileAttributes) = { - digest.update(file.toAbsolutePath.toString.getBytes) - val is = jnio.Files.newInputStream(file) - def rec(): Unit = { - val length = is.read(buffer) - if (length != -1){ - digest.update(buffer, 0, length) - rec() - } - } - rec() - FileVisitResult.CONTINUE - } - - def visitFileFailed(file: jnio.Path, exc: IOException) = FileVisitResult.CONTINUE - def postVisitDirectory(dir: jnio.Path, exc: IOException) = FileVisitResult.CONTINUE - } - ) - - java.util.Arrays.hashCode(digest.digest()) - - } - override def hashCode() = md5Hash -} - -object PathRef{ - private implicit val pathFormat: Format[Path] = JsonFormatters.pathFormat - implicit def jsonFormatter: Format[PathRef] = Json.format -} diff --git a/core/src/test/examples/javac/build.sc b/core/src/test/examples/javac/build.sc index dfbe5271..d7ba5662 100644 --- a/core/src/test/examples/javac/build.sc +++ b/core/src/test/examples/javac/build.sc @@ -1,11 +1,14 @@ +import forge.define.Target +import forge.eval.PathRef + object Foo { import java.io.FileOutputStream import java.util.jar.JarEntry import ammonite.ops.{ls, pwd, read} - import forge.{Discovered, Target} - import forge.util.{Args, PathRef} + import forge.discover.Discovered + import forge.util.Args val workspacePath = pwd / 'target / 'workspace / 'javac val javacSrcPath = pwd / 'src / 'test / 'examples / 'javac diff --git a/core/src/test/scala/forge/CacherTests.scala b/core/src/test/scala/forge/CacherTests.scala index 4c346e5e..24a540ff 100644 --- a/core/src/test/scala/forge/CacherTests.scala +++ b/core/src/test/scala/forge/CacherTests.scala @@ -1,5 +1,8 @@ package forge +import forge.define.Target +import forge.discover.Discovered +import forge.eval.Evaluator import forge.util.OSet import utest._ import utest.framework.TestPath diff --git a/core/src/test/scala/forge/EvaluationTests.scala b/core/src/test/scala/forge/EvaluationTests.scala index b58d5ccc..66fe7b8d 100644 --- a/core/src/test/scala/forge/EvaluationTests.scala +++ b/core/src/test/scala/forge/EvaluationTests.scala @@ -1,6 +1,9 @@ package forge +import forge.define.Target +import forge.discover.Discovered +import forge.eval.Evaluator import forge.util.OSet import utest._ import utest.framework.TestPath diff --git a/core/src/test/scala/forge/GraphTests.scala b/core/src/test/scala/forge/GraphTests.scala index ca825683..e608c877 100644 --- a/core/src/test/scala/forge/GraphTests.scala +++ b/core/src/test/scala/forge/GraphTests.scala @@ -2,6 +2,9 @@ package forge import utest._ import TestUtil.test +import forge.define.Target +import forge.discover.Discovered +import forge.eval.Evaluator import forge.util.OSet object GraphTests extends TestSuite{ diff --git a/core/src/test/scala/forge/JavaCompileJarTests.scala b/core/src/test/scala/forge/JavaCompileJarTests.scala index 8b292a88..f4a5fc88 100644 --- a/core/src/test/scala/forge/JavaCompileJarTests.scala +++ b/core/src/test/scala/forge/JavaCompileJarTests.scala @@ -4,7 +4,10 @@ import java.io.FileOutputStream import java.util.jar.JarEntry import ammonite.ops._ -import forge.util.{Args, OSet, PathRef} +import forge.define.Target +import forge.discover.Discovered +import forge.eval.{Evaluator, PathRef} +import forge.util.{Args, OSet} import utest._ object JavaCompileJarTests extends TestSuite{ diff --git a/core/src/test/scala/forge/TarjanTests.scala b/core/src/test/scala/forge/TarjanTests.scala index 5b118368..58032b86 100644 --- a/core/src/test/scala/forge/TarjanTests.scala +++ b/core/src/test/scala/forge/TarjanTests.scala @@ -1,4 +1,5 @@ package forge +import forge.eval.Tarjans import utest._ object TarjanTests extends TestSuite{ def check(input: Seq[Seq[Int]], expected: Seq[Seq[Int]]) = { diff --git a/core/src/test/scala/forge/TestGraphs.scala b/core/src/test/scala/forge/TestGraphs.scala index 0d6040eb..5c30f948 100644 --- a/core/src/test/scala/forge/TestGraphs.scala +++ b/core/src/test/scala/forge/TestGraphs.scala @@ -1,6 +1,6 @@ package forge -import forge.Target.Cacher +import forge.define.Target.Cacher import forge.TestUtil.test class TestGraphs(){ diff --git a/core/src/test/scala/forge/TestUtil.scala b/core/src/test/scala/forge/TestUtil.scala index 9337fbe0..005bcfef 100644 --- a/core/src/test/scala/forge/TestUtil.scala +++ b/core/src/test/scala/forge/TestUtil.scala @@ -1,7 +1,9 @@ package forge +import forge.define.Target import forge.util.{Args, OSet} import utest.assert + import scala.collection.mutable object TestUtil { -- cgit v1.2.3