From a514408c77c137de4a825ae243ac39ecabd9e3a3 Mon Sep 17 00:00:00 2001
From: Schuyler Eldridge
Date: Tue, 12 Feb 2019 20:56:16 -0500
Subject: Add seeded topological sort to DiGraph

This adds a method to DiGraph called "seededLinearize". This
generalizes the original topological sort ("linearize") to be
parametric in an initial set of vertices. This enables the user to
massage the DFS to produce a better topological sort if they have
information about how the DFS should proceed.

The initial set of vertices is expected to be made ordered via a
LinkedHashSet.

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>
---
 src/main/scala/firrtl/graph/DiGraph.scala | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)

(limited to 'src')

diff --git a/src/main/scala/firrtl/graph/DiGraph.scala b/src/main/scala/firrtl/graph/DiGraph.scala
index 1cac34b5..3fa0ade7 100644
--- a/src/main/scala/firrtl/graph/DiGraph.scala
+++ b/src/main/scala/firrtl/graph/DiGraph.scala
@@ -64,13 +64,14 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     */
   def findSinks: Set[T] = reverse.findSources
 
-  /** Linearizes (topologically sorts) a DAG
-    *
+  /** Linearizes (topologically sorts) a DAG using a DFS. This can be seeded with an order to use for the DFS if the user
+    * wants to tease out a special ordering of the DAG.
+    * @param seed an optional sequence of vertices to use. This will default to the vertices ordering provided by getVertices.
     * @throws CyclicException if the graph is cyclic
     * @return a Map[T,T] from each visited node to its predecessor in the
     * traversal
     */
-  def linearize: Seq[T] = {
+  def seededLinearize(seed: Option[Seq[T]] = None): Seq[T] = {
     // permanently marked nodes are implicitly held in order
     val order = new mutable.ArrayBuffer[T]
     // invariant: no intersection between unmarked and tempMarked
@@ -80,7 +81,7 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     case class LinearizeFrame[T](v: T, expanded: Boolean)
     val callStack = mutable.Stack[LinearizeFrame[T]]()
 
-    unmarked ++= getVertices
+    unmarked ++= seed.getOrElse(getVertices)
     while (unmarked.nonEmpty) {
       callStack.push(LinearizeFrame(unmarked.head, false))
       while (callStack.nonEmpty) {
@@ -133,6 +134,14 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     foundPath
   }
 
+  /** Linearizes (topologically sorts) a DAG
+    *
+    * @throws CyclicException if the graph is cyclic
+    * @return a Map[T,T] from each visited node to its predecessor in the
+    * traversal
+    */
+  def linearize: Seq[T] = seededLinearize(None)
+
   /** Performs breadth-first search on the directed graph
     *
     * @param root the start node
@@ -187,7 +196,7 @@ class DiGraph[T] private[graph] (private[graph] val edges: LinkedHashMap[T, Link
     * @return a Seq[T] of nodes defining an arbitrary valid path
     */
   def path(start: T, end: T): Seq[T] = path(start, end, Set.empty[T])
-  
+
   /** Finds a path (if one exists) from one node to another, with a blacklist
     *
     * @param start the start node
-- 
cgit v1.2.3


From 2585bf986347e264f4c06c38dbcc83aaa554ec4f Mon Sep 17 00:00:00 2001
From: Schuyler Eldridge
Date: Tue, 12 Feb 2019 20:59:56 -0500
Subject: Add a DependencyAPI to firrtl.options.Phase

This adds a TransformLike mixin, DependencyAPI, that defines the basis
of the Dependency API for Stage/Phase. DependencyAPI defines three
members that define dependency relationships for some TransformLike
"Foo":

- "Prerequisites" define TransformLikes that should run before Foo
- "Dependents" define TransformLikes that should run after Foo. This
  allows Foo to inject prerequisites into some other TransformLike.
- "Invalidates" define a function that will return true if a specific
  TransformLike would be invalidated by Foo

Prerequisites and Dependents are not Sets due to lack of a fast,
immutable Set that preserves insertion order. Internally, these are
converted to a private LinkedHashSet.

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>
---
 src/main/scala/firrtl/options/Phase.scala | 88 ++++++++++++++++++++++++++-----
 1 file changed, 76 insertions(+), 12 deletions(-)

(limited to 'src')

diff --git a/src/main/scala/firrtl/options/Phase.scala b/src/main/scala/firrtl/options/Phase.scala
index 7ed964e8..e4bb6f0d 100644
--- a/src/main/scala/firrtl/options/Phase.scala
+++ b/src/main/scala/firrtl/options/Phase.scala
@@ -6,6 +6,7 @@ import firrtl.AnnotationSeq
 
 import logger.LazyLogging
 
+import scala.collection.mutable.LinkedHashSet
 
 /** A polymorphic mathematical transform
   * @tparam A the transformed type
@@ -23,15 +24,78 @@ trait TransformLike[A] extends LazyLogging {
 
 }
 
+/** Mixin that defines dependencies between [[firrtl.options.TransformLike TransformLike]]s (hereafter referred to as
+  * "transforms")
+  *
+  * This trait forms the basis of the Dependency API of the Chisel/FIRRTL Hardware Compiler Framework. Dependencies are
+  * defined in terms of prerequisistes, dependents, and invalidates. A prerequisite is a transform that must run before
+  * this transform. A dependent is a transform that must run ''after'' this transform. (This can be viewed as a means of
+  * injecting a prerequisite into some other transform.) Finally, invalidates define the set of transforms whose effects
+  * this transform undos/invalidates. (Invalidation then implies that a transform that is invalidated by this transform
+  * and needed by another transform will need to be re-run.)
+  *
+  * This Dependency API only defines dependencies. A concrete [[DependencyManager]] is expected to be used to statically
+  * resolve a linear ordering of transforms that satisfies dependency requirements.
+  * @tparam A some transform
+  * @define seqNote @note The use of a Seq here is to preserve input order. Internally, this will be converted to a private,
+  * ordered Set.
+  */
+trait DependencyAPI[A <: DependencyAPI[A]] { this: TransformLike[_] =>
+
+  /** All transform that must run before this transform
+    * $seqNote
+    */
+  def prerequisites: Seq[Class[A]] = Seq.empty
+  private[options] lazy val _prerequisites: LinkedHashSet[Class[A]] = new LinkedHashSet() ++ prerequisites.toSet
+
+  /** All transforms that must run ''after'' this transform
+    *
+    * ''This is a means of prerequisite injection into some other transform.'' Normally a transform will define its own
+    * prerequisites. Dependents exist for two main situations:
+    *
+    * First, they improve the composition of optional transforms. If some first transform is optional (e.g., an
+    * expensive validation check), you would like to be able to conditionally cause it to run. If it is listed as a
+    * prerequisite on some other, second transform then it must always run before that second transform. There's no way
+    * to turn it off. However, by listing the second transform as a dependent of the first transform, the first
+    * transform will only run (and be treated as a prerequisite of the second transform) if included in a list of target
+    * transforms that should be run.
+    *
+    * Second, an external library would like to inject some first transform before a second transform inside FIRRTL. In
+    * this situation, the second transform cannot have any knowledge of external libraries. The use of a dependent here
+    * allows for prerequisite injection into FIRRTL proper.
+    *
+    * @see [[firrtl.passes.CheckTypes]] for an example of an optional checking [[firrtl.Transform]]
+    * $seqNote
+    */
+  def dependents: Seq[Class[A]] = Seq.empty
+  private[options] lazy val _dependents: LinkedHashSet[Class[A]] = new LinkedHashSet() ++ dependents.toSet
+
+  /** A function that, given a transform will return true if this transform invalidates/undos the effects of the input
+    * transform
+    * @note Can a [[firrtl.options.Phase Phase]] ever invalidate itself?
+    */
+  def invalidates(a: A): Boolean = true
+
+  /** Helper method to return the underlying class */
+  final def asClass: Class[A] = this.getClass.asInstanceOf[Class[A]]
+
+  /** Implicit conversion that allows for terser specification of [[DependencyAPI.prerequisites prerequisites]] and
+    * [[DependencyAPI.dependents dependents]].
+    */
+  implicit def classHelper(a: Class[_ <: A]): Class[A] = a.asInstanceOf[Class[A]]
+
+}
+
 /** A mathematical transformation of an [[AnnotationSeq]].
   *
-  * A [[Phase]] forms one unit in the Chisel/FIRRTL Hardware Compiler Framework (HCF). The HCF is built from a sequence
-  * of [[Phase]]s applied to an [[AnnotationSeq]]. Note that a [[Phase]] may consist of multiple phases internally.
+  * A [[firrtl.options.Phase Phase]] forms one unit in the Chisel/FIRRTL Hardware Compiler Framework (HCF). The HCF is
+  * built from a sequence of [[firrtl.options.Phase Phase]]s applied to an [[AnnotationSeq]]. Note that a
+  * [[firrtl.options.Phase Phase]] may consist of multiple phases internally.
   */
-abstract class Phase extends TransformLike[AnnotationSeq] {
+trait Phase extends TransformLike[AnnotationSeq] with DependencyAPI[Phase] {
 
-  /** The name of this [[Phase]]. This will be used to generate debug/error messages or when deleting annotations. This
-    * will default to the `simpleName` of the class.
+  /** The name of this [[firrtl.options.Phase Phase]]. This will be used to generate debug/error messages or when deleting
+    * annotations. This will default to the `simpleName` of the class.
     * @return this phase's name
     * @note Override this with your own implementation for different naming behavior.
     */
@@ -39,15 +103,15 @@ abstract class Phase extends TransformLike[AnnotationSeq] {
 
 }
 
-/** A [[TransformLike]] that internally ''translates'' the input type to some other type, transforms the internal type,
-  * and converts back to the original type.
+/** A [[firrtl.options.TransformLike TransformLike]] that internally ''translates'' the input type to some other type,
+  * transforms the internal type, and converts back to the original type.
   *
-  * This is intended to be used to insert a [[TransformLike]] parameterized by type `B` into a sequence of
-  * [[TransformLike]]s parameterized by type `A`.
-  * @tparam A the type of the [[TransformLike]]
+  * This is intended to be used to insert a [[firrtl.options.TransformLike TransformLike]] parameterized by type `B`
+  * into a sequence of [[firrtl.options.TransformLike TransformLike]]s parameterized by type `A`.
+  * @tparam A the type of the [[firrtl.options.TransformLike TransformLike]]
   * @tparam B the internal type
   */
-trait Translator[A, B] { this: TransformLike[A] =>
+trait Translator[A, B] extends TransformLike[A] {
 
   /** A method converting type `A` into type `B`
     * @param an object of type `A`
@@ -69,6 +133,6 @@ trait Translator[A, B] { this: TransformLike[A] =>
 
   /** Convert the input object to the internal type, transform the internal type, and convert back to the original type
     */
-  final def transform(a: A): A = internalTransform(a)
+  override final def transform(a: A): A = bToA(internalTransform(aToB(a)))
 
 }
-- 
cgit v1.2.3


From c219be2375fadcdd88851842e7b9029271230398 Mon Sep 17 00:00:00 2001
From: Schuyler Eldridge
Date: Fri, 19 Apr 2019 10:42:40 -0400
Subject: Add PreservesAll stackable trait for DependencyAPI

This adds a PreservesAll that can be used to override the default
invalidation scheme (invalidated everything except yourself) such that
nothing is invalidated.

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>
---
 src/main/scala/firrtl/options/Phase.scala | 9 +++++++++
 1 file changed, 9 insertions(+)

(limited to 'src')

diff --git a/src/main/scala/firrtl/options/Phase.scala b/src/main/scala/firrtl/options/Phase.scala
index e4bb6f0d..e5aa87ec 100644
--- a/src/main/scala/firrtl/options/Phase.scala
+++ b/src/main/scala/firrtl/options/Phase.scala
@@ -86,6 +86,15 @@ trait DependencyAPI[A <: DependencyAPI[A]] { this: TransformLike[_] =>
 
 }
 
+/** A trait indicating that no invalidations occur, i.e., all previous transforms are preserved
+  * @tparam A some [[TransformLike]]
+  */
+trait PreservesAll[A <: DependencyAPI[A]] { this: DependencyAPI[A] =>
+
+  override def invalidates(a: A): Boolean = false
+
+}
+
 /** A mathematical transformation of an [[AnnotationSeq]].
   *
   * A [[firrtl.options.Phase Phase]] forms one unit in the Chisel/FIRRTL Hardware Compiler Framework (HCF). The HCF is
-- 
cgit v1.2.3


From affc0e0fa3ded5672b617a5ca722067ceac069a9 Mon Sep 17 00:00:00 2001
From: Schuyler Eldridge
Date: Tue, 12 Feb 2019 21:04:09 -0500
Subject: Add DependencyManager and PhaseManager

Adds the DependencyManager class which can be used to determine a
legal sequence of TransformLikes given their Dependency API
constraints. A DependencyManager determines an ordering that results
in some target TransformLikes being run (without invalidations) given
an initial state (some other set of TransformLikes).

Algorithmically, this works as follows:

1. A DAG of TransformLikes w/ invalidation edges is constructed (the
   "invalidate graph")

2. A DAG of TransformLikes w/ prerequisite and dependent edges is
   constructed (the "dependents graph")

3. A toplogical sort of the dependents graph, seeded with the reverse
   topological sort of the invalidate graph, gives an ordering of
   TransformLikes.

4. This ordering is examined, node by node, cleaning up any mismatches
   between TransformLikes by solving DependencyManager sub-problems.

As new graph nodes (which are classes) are found, these are lazily
constructed. Data structures are maintained that map from classes to
objects and back. All discovered classes will point to the same object.

Determinism is maintained internally using LinkedHashMap and
LinkedHashSet.

Other changes:
- Some methods that generate Graphviz for a DependencyManager are
  added.
- One concrete implementation of a DependencyManager is added for
  Phases called "PhaseManager".

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>
---
 .../scala/firrtl/options/DependencyManager.scala   | 363 +++++++++++++++++++++
 1 file changed, 363 insertions(+)
 create mode 100644 src/main/scala/firrtl/options/DependencyManager.scala

(limited to 'src')

diff --git a/src/main/scala/firrtl/options/DependencyManager.scala b/src/main/scala/firrtl/options/DependencyManager.scala
new file mode 100644
index 00000000..2afc085d
--- /dev/null
+++ b/src/main/scala/firrtl/options/DependencyManager.scala
@@ -0,0 +1,363 @@
+// See LICENSE for license details.
+
+package firrtl.options
+
+import firrtl.AnnotationSeq
+import firrtl.graph.{DiGraph, CyclicException}
+
+import scala.collection.Set
+import scala.collection.immutable.{Set => ISet}
+import scala.collection.mutable.{ArrayBuffer, HashMap, LinkedHashMap, LinkedHashSet, Queue}
+
+/** An exception arising from an in a [[DependencyManager]] */
+case class DependencyManagerException(message: String, cause: Throwable = null) extends RuntimeException(message, cause)
+
+/** A [[firrtl.options.TransformLike TransformLike]] that resolves a linear ordering of dependencies based on
+  * requirements.
+  * @tparam A the type over which this transforms
+  * @tparam B the type of the [[firrtl.options.TransformLike TransformLike]]
+  */
+trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends TransformLike[A] with DependencyAPI[B] {
+
+  /** Requested [[firrtl.options.TransformLike TransformLike]]s that should be run. Internally, this will be converted to
+    * a set based on the ordering defined here.
+    */
+  def targets: Seq[Class[B]]
+  private lazy val _targets: LinkedHashSet[Class[B]] = targets
+    .foldLeft(new LinkedHashSet[Class[B]]()){ case (a, b) => a += b }
+
+  /** A sequence of [[firrtl.Transform]]s that have been run. Internally, this will be converted to an ordered set.
+    */
+  def currentState: Seq[Class[B]]
+  private lazy val _currentState: LinkedHashSet[Class[B]] = currentState
+    .foldLeft(new LinkedHashSet[Class[B]]()){ case (a, b) => a += b }
+
+  /** Existing transform objects that have already been constructed */
+  def knownObjects: Set[B]
+
+  /** A sequence of wrappers to apply to the resulting [[firrtl.options.TransformLike TransformLike]] sequence. This can
+    * be used to, e.g., add automated pre-processing and post-processing.
+    */
+  def wrappers: Seq[(B) => B] = Seq.empty
+
+  /** Store of conversions between classes and objects. Objects that do not exist in the map will be lazily constructed.
+    */
+  protected lazy val classToObject: LinkedHashMap[Class[B], B] = {
+    val init = LinkedHashMap[Class[B], B](knownObjects.map(x => x.getClass.asInstanceOf[Class[B]] -> x).toSeq: _*)
+    (_targets ++ _currentState)
+      .filter(!init.contains(_))
+      .map(x => init(x) = safeConstruct(x))
+    init
+  }
+
+  /** A method that will create a copy of this [[firrtl.options.DependencyManager DependencyManager]], but with different
+    * requirements. This is used to solve sub-problems arising from invalidations.
+    */
+  protected def copy(
+    targets: Seq[Class[B]],
+    currentState: Seq[Class[B]],
+    knownObjects: ISet[B] = classToObject.values.toSet): B
+
+  /** Implicit conversion from Class[B] to B */
+  private implicit def cToO(c: Class[B]): B = classToObject.getOrElseUpdate(c, safeConstruct(c))
+
+  /** Implicit conversion from B to Class[B] */
+  private implicit def oToC(b: B): Class[B] = b.getClass.asInstanceOf[Class[B]]
+
+  /** Modified breadth-first search that supports multiple starting nodes and a custom extractor that can be used to
+    * generate/filter the edges to explore. Additionally, this will include edges to previously discovered nodes.
+    */
+  private def bfs( start: LinkedHashSet[Class[B]],
+                   blacklist: LinkedHashSet[Class[B]],
+                   extractor: B => Set[Class[B]] ): LinkedHashMap[B, LinkedHashSet[B]] = {
+
+    val (queue, edges) = {
+      val a: Queue[Class[B]]                    = Queue(start.toSeq:_*)
+      val b: LinkedHashMap[B, LinkedHashSet[B]] = LinkedHashMap[B, LinkedHashSet[B]](
+        start.map((cToO(_) -> LinkedHashSet[B]())).toSeq:_*)
+      (a, b)
+    }
+
+    while (queue.nonEmpty) {
+      val u: Class[B] = queue.dequeue
+      for (v: Class[B] <- extractor(classToObject(u))) {
+        if (!blacklist.contains(v) && !edges.contains(v)) {
+          queue.enqueue(v)
+        }
+        if (!edges.contains(v)) {
+          val obj = cToO(v)
+          edges(obj) = LinkedHashSet.empty
+          classToObject += (v -> obj)
+        }
+        edges(classToObject(u)) = edges(classToObject(u)) + classToObject(v)
+      }
+    }
+
+    edges
+  }
+
+  /** Pull in all registered [[firrtl.options.TransformLike TransformLike]] once [[firrtl.options.TransformLike
+    * TransformLike]] registration is integrated
+    * @todo implement this
+    */
+  private lazy val registeredTransforms: Set[B] = Set.empty
+
+  /** A directed graph consisting of prerequisite edges */
+  private lazy val prerequisiteGraph: DiGraph[B] = {
+    val edges = bfs(
+      start = _targets -- _currentState,
+      blacklist = _currentState,
+      extractor = (p: B) => new LinkedHashSet[Class[B]]() ++ p.prerequisites -- _currentState)
+    DiGraph(edges)
+  }
+
+  /** A directed graph consisting of prerequisites derived from only those transforms which are supposed to run. This
+    * pulls in dependents for transforms which are not in the target set.
+    */
+  private lazy val dependentsGraph: DiGraph[B] = {
+    val v = new LinkedHashSet() ++ prerequisiteGraph.getVertices
+    DiGraph(new LinkedHashMap() ++ v.map(vv => vv -> ((new LinkedHashSet() ++ vv.dependents).map(cToO) & v))).reverse
+  }
+
+  /** A directed graph consisting of prerequisites derived from ALL targets. This is necessary for defining targets for
+    * [[DependencyManager]] sub-problems.
+    */
+  private lazy val otherDependents: DiGraph[B] = {
+    val edges = {
+      val x = new LinkedHashMap ++ _targets
+        .map(classToObject)
+        .map{ a => a -> prerequisiteGraph.getVertices.filter(a._dependents(_)) }
+      x
+        .values
+        .reduce(_ ++ _)
+        .foldLeft(x){ case (xx, y) => if (xx.contains(y)) { xx } else { xx ++ Map(y -> Set.empty[B]) } }
+    }
+    DiGraph(edges).reverse
+  }
+
+  /** A directed graph consisting of all prerequisites, including prerequisites derived from dependents */
+  lazy val dependencyGraph: DiGraph[B] = prerequisiteGraph + dependentsGraph
+
+  /** A directed graph consisting of invalidation edges */
+  lazy val invalidateGraph: DiGraph[B] = {
+    val v = dependencyGraph.getVertices
+    DiGraph(
+      bfs(
+        start = _targets -- _currentState,
+        blacklist = _currentState,
+        extractor = (p: B) => v.filter(p.invalidates).map(_.asClass).toSet))
+      .reverse
+  }
+
+  /** Wrap a possible [[CyclicException]] thrown by a thunk in a [[DependencyManagerException]] */
+  private def cyclePossible[A](a: String, diGraph: DiGraph[_])(thunk: => A): A = try { thunk } catch {
+    case e: CyclicException =>
+      throw new DependencyManagerException(
+        s"""|No transform ordering possible due to cyclic dependency in $a with cycles:
+            |${diGraph.findSCCs.filter(_.size > 1).mkString("    - ", "\n    - ", "")}""".stripMargin, e)
+  }
+
+  /** Wrap an [[IllegalAccessException]] due to attempted object construction in a [[DependencyManagerException]] */
+  private def safeConstruct[A](a: Class[A]): A = try { a.newInstance } catch {
+    case e: IllegalAccessException => throw new DependencyManagerException(
+      s"Failed to construct '$a'! (Did you try to construct an object?)", e)
+    case e: InstantiationException => throw new DependencyManagerException(
+      s"Failed to construct '$a'! (Did you try to construct an inner class or a class with parameters?)", e)
+  }
+
+  /** An ordering of [[firrtl.options.TransformLike TransformLike]]s that causes the requested [[DependencyManager.targets
+    * targets]] to be executed starting from the [[DependencyManager.currentState currentState]]. This ordering respects
+    * prerequisites, dependents, and invalidates of all constituent [[firrtl.options.TransformLike TransformLike]]s.
+    * This uses an algorithm that attempts to reduce the number of re-lowerings due to invalidations. Re-lowerings are
+    * implemented as new [[DependencyManager]]s.
+    * @throws DependencyManagerException if a cycle exists in either the [[DependencyManager.dependencyGraph
+    * dependencyGraph]] or the [[DependencyManager.invalidateGraph invalidateGraph]].
+    */
+  lazy val transformOrder: Seq[B] = {
+
+    /* Topologically sort the dependency graph using the invalidate graph topological sort as a seed. This has the effect of
+     * reducing (perhaps minimizing?) the number of work re-lowerings.
+     */
+    val sorted = {
+      val seed = cyclePossible("invalidates", invalidateGraph){ invalidateGraph.linearize }.reverse
+
+      cyclePossible("prerequisites/dependents", dependencyGraph) {
+        dependencyGraph
+          .seededLinearize(Some(seed))
+          .reverse
+          .dropWhile(b => _currentState.contains(b))
+      }
+    }
+
+    val (state, lowerers) = {
+      /* [todo] Seq is inefficient here, but Array has ClassTag problems. Use something else? */
+      val (s, l) = sorted.foldLeft((_currentState, Seq[B]())){ case ((state, out), in) =>
+        /* The prerequisites are both prerequisites AND dependents. */
+        val prereqs = new LinkedHashSet() ++ in.prerequisites ++
+          dependencyGraph.getEdges(in).toSeq.map(oToC) ++
+          otherDependents.getEdges(in).toSeq.map(oToC)
+        val missing = (prereqs -- state)
+        val preprocessing: Option[B] = {
+          if (missing.nonEmpty) { Some(this.copy(prereqs.toSeq, state.toSeq)) }
+          else                  { None                                     }
+        }
+        ((state ++ missing + in).map(cToO).filterNot(in.invalidates).map(oToC), out ++ preprocessing :+ in)
+      }
+      val missing = (_targets -- s)
+      val postprocessing: Option[B] = {
+        if (missing.nonEmpty) { Some(this.copy(_targets.toSeq, s.toSeq)) }
+        else                  { None                        }
+      }
+
+      (s ++ missing, l ++ postprocessing)
+    }
+
+    if (!_targets.subsetOf(state)) {
+      throw new DependencyManagerException(
+        s"The final state ($state) did not include the requested targets (${targets})!")
+    }
+    lowerers
+  }
+
+  /** A version of the [[DependencyManager.transformOrder transformOrder]] that flattens the transforms of any internal
+    * [[DependencyManager]]s.
+    */
+  lazy val flattenedTransformOrder: Seq[B] = transformOrder.flatMap {
+    case p: DependencyManager[A, B] => p.flattenedTransformOrder
+    case p => Some(p)
+  }
+
+  final override def transform(annotations: A): A = {
+
+    /* A local store of each wrapper to it's underlying class. */
+    val wrapperToClass = new HashMap[B, Class[B]]
+
+    /* The determined, flat order of transforms is wrapped with surrounding transforms while populating wrapperToClass so
+     * that each wrapped transform object can be dereferenced to its underlying class. Each wrapped transform is then
+     * applied while tracking the state of the underlying A. If the state ever disagrees with a prerequisite, then this
+     * throws an exception.
+     */
+    flattenedTransformOrder
+      .map{ t =>
+        val w = wrappers.foldLeft(t){ case (tx, wrapper) => wrapper(tx) }
+        wrapperToClass += (w -> t)
+        w
+      }.foldLeft((annotations, _currentState)){ case ((a, state), t) =>
+          if (!t.prerequisites.toSet.subsetOf(state)) {
+            throw new DependencyManagerException(
+              s"""|Tried to execute '$t' for which run-time prerequisites were not satisfied:
+                  |  state: ${state.mkString("\n    -", "\n    -", "")}
+                  |  prerequisites: ${prerequisites.mkString("\n    -", "\n    -", "")}""".stripMargin)
+          }
+          (t.transform(a), ((state + wrapperToClass(t)).map(cToO).filterNot(t.invalidates).map(oToC)))
+      }._1
+  }
+
+  /** This colormap uses Colorbrewer's 4-class OrRd color scheme */
+  protected val colormap = Seq("#fef0d9", "#fdcc8a", "#fc8d59", "#d7301f")
+
+  /** Get a name of some [[firrtl.options.TransformLike TransformLike]] */
+  private def transformName(transform: B, suffix: String = ""): String = s""""${transform.name}$suffix""""
+
+  /** Convert all prerequisites, dependents, and invalidates to a Graphviz representation.
+    * @param file the name of the output file
+    */
+  def dependenciesToGraphviz: String = {
+
+    def toGraphviz(digraph: DiGraph[B], attributes: String = "", tab: String = "    "): Option[String] = {
+      val edges =
+        digraph
+          .getEdgeMap
+          .collect{ case (v, edges) if edges.nonEmpty => (v -> edges) }
+          .map{ case (v, edges) =>
+            s"""${transformName(v)} -> ${edges.map(e => transformName(e)).mkString("{ ", " ", " }")}""" }
+
+      if (edges.isEmpty) { None } else {
+        Some(
+          s"""|  { $attributes
+              |${edges.mkString(tab, "\n" + tab, "")}
+              |  }""".stripMargin
+        )
+      }
+    }
+
+    val connections =
+      Seq( (prerequisiteGraph, "edge []"),
+           (dependentsGraph,   """edge [color="#de2d26"]"""),
+           (invalidateGraph,   "edge [minlen=2,style=dashed,constraint=false]") )
+        .flatMap{ case (a, b) => toGraphviz(a, b) }
+        .mkString("\n")
+
+    val nodes =
+      (prerequisiteGraph + dependentsGraph + invalidateGraph + otherDependents)
+        .getVertices
+        .map(v => s"""${transformName(v)} [label="${v.getClass.getSimpleName}"]""")
+
+    s"""|digraph DependencyManager {
+        |  graph [rankdir=BT]
+        |  node [fillcolor="${colormap(0)}",style=filled,shape=box]
+        |${nodes.mkString("  ", "\n" + "  ", "")}
+        |$connections
+        |}
+        |""".stripMargin
+  }
+
+  def transformOrderToGraphviz(colormap: Seq[String] = colormap): String = {
+
+    def rotate[A](a: Seq[A]): Seq[A] = a match {
+      case Nil => Nil
+      case car :: cdr => cdr :+ car
+      case car => car
+    }
+
+    val sorted = ArrayBuffer.empty[String]
+
+    def rec(pm: DependencyManager[A, B], cm: Seq[String], tab: String = "", id: Int = 0): (String, Int) = {
+      var offset = id
+
+      val targets = pm._targets.toSeq.map(_.getSimpleName).mkString(", ")
+      val state = pm._currentState.toSeq.map(_.getSimpleName).mkString(", ")
+
+      val header = s"""|${tab}subgraph cluster_$id {
+                       |$tab  label="targets: $targets\\nstate: $state"
+                       |$tab  labeljust=l
+                       |$tab  node [fillcolor="${cm.head}"]""".stripMargin
+
+      val body = pm.transformOrder.map{
+        case a: DependencyManager[A, B] =>
+          val (str, d) = rec(a, rotate(cm), tab + "  ", offset + 1)
+          offset = d
+          str
+        case a =>
+          val name = s"""${transformName(a, "_" + id)}"""
+          sorted += name
+          s"""$tab  $name [label="${a.getClass.getSimpleName}"]"""
+      }.mkString("\n")
+
+      (Seq(header, body, s"$tab}").mkString("\n"), offset)
+    }
+
+    s"""|digraph DependencyManagerTransformOrder {
+        |  graph [rankdir=TB]
+        |  node [style=filled,shape=box]
+        |${rec(this, colormap, "  ")._1}
+        |  ${sorted.mkString(" -> ")}
+        |}""".stripMargin
+  }
+
+}
+
+/** A [[Phase]] that will ensure that some other [[Phase]]s and their prerequisites are executed.
+  *
+  * This tries to determine a phase ordering such that an [[AnnotationSeq]] ''output'' is produced that has had all of
+  * the requested [[Phase]] target transforms run without having them be invalidated.
+  * @param targets the [[Phase]]s you want to run
+  */
+class PhaseManager(
+  val targets: Seq[Class[Phase]],
+  val currentState: Seq[Class[Phase]] = Seq.empty,
+  val knownObjects: Set[Phase] = Set.empty) extends Phase with DependencyManager[AnnotationSeq, Phase] {
+
+  protected def copy(a: Seq[Class[Phase]], b: Seq[Class[Phase]], c: ISet[Phase]) = new PhaseManager(a, b, c)
+
+}
-- 
cgit v1.2.3


From ec3734e8d48cc429804f08e92c5ff0d2c2da3b99 Mon Sep 17 00:00:00 2001
From: Schuyler Eldridge
Date: Tue, 12 Feb 2019 21:08:49 -0500
Subject: Add PhaseManager tests

Adds tests for the PhaseManager. This includes outputs in
"test_run_dir" of Graphviz output. This will automatically generate a
PNG if "dot" is on the path. Otherwise, it will just generate the
Graphviz output. This includes tests that check for determinism.
---
 .../firrtlTests/options/PhaseManagerSpec.scala     | 556 +++++++++++++++++++++
 1 file changed, 556 insertions(+)
 create mode 100644 src/test/scala/firrtlTests/options/PhaseManagerSpec.scala

(limited to 'src')

diff --git a/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala b/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala
new file mode 100644
index 00000000..b68da0d8
--- /dev/null
+++ b/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala
@@ -0,0 +1,556 @@
+// See LICENSE for license details.
+
+package firrtlTests.options
+
+import org.scalatest.{FlatSpec, Matchers}
+
+import firrtl.AnnotationSeq
+import firrtl.options.{DependencyManagerException, Phase, PhaseManager, PreservesAll}
+
+import java.io.{File, PrintWriter}
+
+import sys.process._
+
+trait IdentityPhase extends Phase {
+  def transform(annotations: AnnotationSeq): AnnotationSeq = annotations
+}
+
+/** Default [[Phase]] that has no prerequisites and invalidates nothing */
+class A extends IdentityPhase {
+
+  override def invalidates(phase: Phase): Boolean = false
+}
+
+/** [[Phase]] that requires [[A]] and invalidates nothing */
+class B extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+  override def invalidates(phase: Phase): Boolean = false
+}
+
+/** [[Phase]] that requires [[B]] and invalidates nothing */
+class C extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+  override def invalidates(phase: Phase): Boolean = false
+}
+
+/** [[Phase]] that requires [[A]] and invalidates [[A]] */
+class D extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+  override def invalidates(phase: Phase): Boolean = phase match {
+    case _: A => true
+    case _ => false
+  }
+}
+
+/** [[Phase]] that requires [[B]] and invalidates nothing */
+class E extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B])
+  override def invalidates(phase: Phase): Boolean = false
+}
+
+/** [[Phase]] that requires [[B]] and [[C]] and invalidates [[E]] */
+class F extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B], classOf[C])
+  override def invalidates(phase: Phase): Boolean = phase match {
+    case _: E => true
+    case _ => false
+  }
+}
+
+
+/** [[Phase]] that requires [[C]] and invalidates [[F]] */
+class G extends IdentityPhase {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[C])
+  override def invalidates(phase: Phase): Boolean = phase match {
+    case _: F => true
+    case _ => false
+  }
+}
+
+class CyclicA extends IdentityPhase with PreservesAll[Phase] {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[CyclicB])
+}
+
+class CyclicB extends IdentityPhase with PreservesAll[Phase] {
+  override def prerequisites: Seq[Class[Phase]] = Seq(classOf[CyclicA])
+}
+
+class CyclicC extends IdentityPhase {
+  override def invalidates(a: Phase): Boolean = a match {
+    case _: CyclicD => true
+    case _ => false
+  }
+}
+
+class CyclicD extends IdentityPhase {
+  override def invalidates(a: Phase): Boolean = a match {
+    case _: CyclicC => true
+    case _ => false
+  }
+}
+
+object ComplicatedFixture {
+
+  class A extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class B extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class C extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: B => true
+      case _ => false
+    }
+  }
+  class D extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: C | _: E => true
+      case _ => false
+    }
+  }
+  class E extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+}
+
+object RepeatedAnalysisFixture {
+
+  trait InvalidatesAnalysis extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: Analysis => true
+      case _ => false
+    }
+  }
+
+  class Analysis extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class A extends InvalidatesAnalysis {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[Analysis])
+  }
+  class B extends InvalidatesAnalysis {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[A], classOf[Analysis])
+  }
+  class C extends InvalidatesAnalysis {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[B], classOf[Analysis])
+  }
+
+}
+
+object InvertedAnalysisFixture {
+
+  class Analysis extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class A extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[Analysis])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: Analysis => true
+      case _ => false
+    }
+  }
+  class B extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[Analysis])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: Analysis | _: A => true
+      case _ => false
+    }
+  }
+  class C extends IdentityPhase {
+    override def prerequisites: Seq[Class[Phase]] = Seq(classOf[Analysis])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: Analysis | _: B => true
+      case _ => false
+    }
+  }
+
+}
+
+object DependentsFixture {
+
+  class First extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+  class Second extends IdentityPhase {
+    override val prerequisites: Seq[Class[Phase]] = Seq(classOf[First])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+  /* This models a situation where a user has a custom Phase that they need to run before some other Phase. This is an
+   * abstract example of writing a Transform that cleans up combinational loops. This needs to run before combinational
+   * loop detection.
+   */
+  class Custom extends IdentityPhase {
+    override val prerequisites: Seq[Class[Phase]] = Seq(classOf[First])
+    override val dependents: Seq[Class[Phase]] = Seq(classOf[Second])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+}
+
+object ChainedInvalidationFixture {
+
+  class A extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: B => true
+      case _ => false
+    }
+  }
+  class B extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: C => true
+      case _ => false
+    }
+  }
+  class C extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: D => true
+      case _ => false
+    }
+  }
+  class D extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = false
+  }
+  class E extends IdentityPhase {
+    override val prerequisites: Seq[Class[Phase]] = Seq(classOf[A], classOf[B], classOf[C], classOf[D])
+    override def invalidates(phase: Phase): Boolean = false
+  }
+
+}
+
+object UnrelatedFixture {
+
+  trait InvalidatesB8Dep { this: Phase =>
+    override def invalidates(a: Phase) = a match {
+      case _: B8Dep => true
+      case _        => false
+    }
+  }
+
+  class B0 extends IdentityPhase with InvalidatesB8Dep
+  class B1 extends IdentityPhase with PreservesAll[Phase]
+  class B2 extends IdentityPhase with PreservesAll[Phase]
+  class B3 extends IdentityPhase with PreservesAll[Phase]
+  class B4 extends IdentityPhase with PreservesAll[Phase]
+  class B5 extends IdentityPhase with PreservesAll[Phase]
+  class B6 extends IdentityPhase with PreservesAll[Phase]
+  class B7 extends IdentityPhase with PreservesAll[Phase]
+
+  class B8 extends IdentityPhase with PreservesAll[Phase]
+  class B9 extends IdentityPhase with PreservesAll[Phase]
+  class B10 extends IdentityPhase with PreservesAll[Phase]
+  class B11 extends IdentityPhase with PreservesAll[Phase]
+  class B12 extends IdentityPhase with PreservesAll[Phase]
+  class B13 extends IdentityPhase with PreservesAll[Phase]
+  class B14 extends IdentityPhase with PreservesAll[Phase]
+  class B15 extends IdentityPhase with PreservesAll[Phase]
+
+  class B6Sub extends B6 {
+    override val prerequisites = Seq(classOf[B6]).asInstanceOf[Seq[Class[Phase]]]
+    override val dependents = Seq(classOf[B7]).asInstanceOf[Seq[Class[Phase]]]
+  }
+
+  class B6_0 extends B6Sub
+  class B6_1 extends B6Sub
+  class B6_2 extends B6Sub
+  class B6_3 extends B6Sub
+  class B6_4 extends B6Sub
+  class B6_5 extends B6Sub
+  class B6_6 extends B6Sub
+  class B6_7 extends B6Sub
+  class B6_8 extends B6Sub
+  class B6_9 extends B6Sub
+  class B6_10 extends B6Sub
+  class B6_11 extends B6Sub
+  class B6_12 extends B6Sub
+  class B6_13 extends B6Sub
+  class B6_14 extends B6Sub
+  class B6_15 extends B6Sub
+
+  class B8Dep extends B8 {
+    override val dependents = Seq(classOf[B8]).asInstanceOf[Seq[Class[Phase]]]
+  }
+
+  class B8_0 extends B8Dep
+  class B8_1 extends B8Dep
+  class B8_2 extends B8Dep
+  class B8_3 extends B8Dep
+  class B8_4 extends B8Dep
+  class B8_5 extends B8Dep
+  class B8_6 extends B8Dep
+  class B8_7 extends B8Dep
+  class B8_8 extends B8Dep
+  class B8_9 extends B8Dep
+  class B8_10 extends B8Dep
+  class B8_11 extends B8Dep
+  class B8_12 extends B8Dep
+  class B8_13 extends B8Dep
+  class B8_14 extends B8Dep
+  class B8_15 extends B8Dep
+
+}
+
+class PhaseManagerSpec extends FlatSpec with Matchers {
+
+  def writeGraphviz(pm: PhaseManager, dir: String): Unit = {
+
+    /** Convert a Graphviz file to PNG using */
+    def maybeToPng(f: File): Unit = try {
+      s"dot -Tpng -O ${f}" !
+    } catch {
+      case _: java.io.IOException =>
+    }
+
+    val d = new File(dir)
+    d.mkdirs()
+
+    {
+      val f = new File(d + "/dependencyGraph.dot")
+      val w = new PrintWriter(f)
+      w.write(pm.dependenciesToGraphviz)
+      w.close
+      maybeToPng(f)
+    }
+
+    {
+      val f = new File(d + "/transformOrder.dot")
+      val w = new PrintWriter(new File(d + "/transformOrder.dot"))
+      try {
+        w.write(pm.transformOrderToGraphviz())
+        w.close
+        maybeToPng(f)
+      } catch {
+        case _: DependencyManagerException =>
+      }
+    }
+
+  }
+
+  implicit def f(a: Class[_ <: Phase]): Class[Phase] = a.asInstanceOf[Class[Phase]]
+
+  behavior of this.getClass.getName
+
+  it should "do nothing if all targets are reached" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[A], classOf[B], classOf[C], classOf[D])
+    val pm = new PhaseManager(targets, targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/DoNothing")
+
+    pm.flattenedTransformOrder should be (empty)
+  }
+
+  it should "handle a simple dependency" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[B])
+    val order: Seq[Class[Phase]] = Seq(classOf[A], classOf[B])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/SimpleDependency")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  it should "handle a simple dependency with an invalidation" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[A], classOf[B], classOf[C], classOf[D])
+    val order: Seq[Class[Phase]] = Seq(classOf[A], classOf[D], classOf[A], classOf[B], classOf[C])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/OneInvalidate")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  it should "handle a dependency with two invalidates optimally" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[A], classOf[B], classOf[C], classOf[E], classOf[F], classOf[G])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/TwoInvalidates")
+
+    pm.flattenedTransformOrder.size should be (targets.size)
+  }
+
+  it should "throw an exception for cyclic prerequisites" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[CyclicA], classOf[CyclicB])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/CyclicPrerequisites")
+
+    intercept[DependencyManagerException]{ pm.flattenedTransformOrder }
+      .getMessage should startWith ("No transform ordering possible")
+  }
+
+  it should "throw an exception for cyclic invalidates" in {
+    val targets: Seq[Class[Phase]] = Seq(classOf[CyclicC], classOf[CyclicD])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/CyclicInvalidates")
+
+    intercept[DependencyManagerException]{ pm.flattenedTransformOrder }
+      .getMessage should startWith ("No transform ordering possible")
+  }
+
+  it should "handle a complicated graph" in {
+    val f = ComplicatedFixture
+    val targets: Seq[Class[Phase]] = Seq(classOf[f.A], classOf[f.B], classOf[f.C], classOf[f.D], classOf[f.E])
+      .map(_.asInstanceOf[Class[Phase]])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/Complicated")
+
+    info("only one phase was recomputed")
+    pm.flattenedTransformOrder.size should be (targets.size + 1)
+  }
+
+  it should "handle repeated recomputed analyses" in {
+    val f = RepeatedAnalysisFixture
+    val targets: Seq[Class[Phase]] = Seq(classOf[f.A], classOf[f.B], classOf[f.C])
+      .map(_.asInstanceOf[Class[Phase]])
+    val order: Seq[Class[Phase]] =
+      Seq( classOf[f.Analysis],
+           classOf[f.A],
+           classOf[f.Analysis],
+           classOf[f.B],
+           classOf[f.Analysis],
+           classOf[f.C])
+        .map(_.asInstanceOf[Class[Phase]])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/RepeatedAnalysis")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  it should "handle inverted repeated recomputed analyses" in {
+    val f = InvertedAnalysisFixture
+    val targets: Seq[Class[Phase]] = Seq(classOf[f.A], classOf[f.B], classOf[f.C])
+      .map(_.asInstanceOf[Class[Phase]])
+    val order: Seq[Class[Phase]] =
+      Seq( classOf[f.Analysis],
+           classOf[f.C],
+           classOf[f.Analysis],
+           classOf[f.B],
+           classOf[f.Analysis],
+           classOf[f.A])
+        .map(_.asInstanceOf[Class[Phase]])
+    val pm = new PhaseManager(targets)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/InvertedRepeatedAnalysis")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  /** This test shows how the dependents member can be used to run one transform before another. */
+  it should "handle a custom Phase with a dependent" in {
+    val f = DependentsFixture
+
+    info("without the custom transform it runs: First -> Second")
+    val pm = new PhaseManager(Seq(classOf[f.Second]).map(_.asInstanceOf[Class[Phase]]))
+    val orderNoCustom: Seq[Class[Phase]] = Seq(classOf[f.First], classOf[f.Second])
+      .map(_.asInstanceOf[Class[Phase]])
+    pm.flattenedTransformOrder.map(_.asClass) should be (orderNoCustom)
+
+    info("with the custom transform it runs:    First -> Custom -> Second")
+    val pmCustom = new PhaseManager(Seq(classOf[f.Custom], classOf[f.Second]).map(_.asInstanceOf[Class[Phase]]))
+    val orderCustom: Seq[Class[Phase]] = Seq(classOf[f.First], classOf[f.Custom], classOf[f.Second])
+      .map(_.asInstanceOf[Class[Phase]])
+
+    writeGraphviz(pmCustom, "test_run_dir/PhaseManagerSpec/SingleDependent")
+
+    pmCustom.flattenedTransformOrder.map(_.asClass) should be (orderCustom)
+  }
+
+  it should "handle chained invalidation" in {
+    val f = ChainedInvalidationFixture
+
+    val targets: Seq[Class[Phase]] = Seq(classOf[f.A], classOf[f.E])
+      .map(_.asInstanceOf[Class[Phase]])
+    val current: Seq[Class[Phase]] = Seq(classOf[f.B], classOf[f.C], classOf[f.D]).map(_.asInstanceOf[Class[Phase]])
+
+    val pm = new PhaseManager(targets, current)
+    val order: Seq[Class[Phase]] = Seq( classOf[f.A], classOf[f.B], classOf[f.C], classOf[f.D], classOf[f.E] )
+      .map(_.asInstanceOf[Class[Phase]])
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/ChainedInvalidate")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (order)
+  }
+
+  it should "maintain the order of input targets" in {
+    val f = UnrelatedFixture
+
+    /** A bunch of unrelated Phases. This ensures that these run in the order in which they are specified. */
+    val targets =
+      Seq( classOf[f.B0],
+           classOf[f.B1],
+           classOf[f.B2],
+           classOf[f.B3],
+           classOf[f.B4],
+           classOf[f.B5],
+           classOf[f.B6],
+           classOf[f.B7],
+           classOf[f.B8],
+           classOf[f.B9],
+           classOf[f.B10],
+           classOf[f.B11],
+           classOf[f.B12],
+           classOf[f.B13],
+           classOf[f.B14],
+           classOf[f.B15] ).asInstanceOf[Seq[Class[Phase]]]
+    /** A sequence of custom transforms that should all run after B6 and before B7. This exercises correct ordering of the
+      * prerequisiteGraph and dependentsGraph.
+      */
+    val prerequisiteTargets =
+      Seq( classOf[f.B6_0],
+           classOf[f.B6_1],
+           classOf[f.B6_2],
+           classOf[f.B6_3],
+           classOf[f.B6_4],
+           classOf[f.B6_5],
+           classOf[f.B6_6],
+           classOf[f.B6_7],
+           classOf[f.B6_8],
+           classOf[f.B6_9],
+           classOf[f.B6_10],
+           classOf[f.B6_11],
+           classOf[f.B6_12],
+           classOf[f.B6_13],
+           classOf[f.B6_14],
+           classOf[f.B6_15] ).asInstanceOf[Seq[Class[Phase]]]
+    /** A sequence of transforms that are invalidated by B0 and only define dependents on B8. This exercises the ordering
+      * defined by "otherDependents".
+      */
+    val current =
+      Seq( classOf[f.B8_0],
+           classOf[f.B8_1],
+           classOf[f.B8_2],
+           classOf[f.B8_3],
+           classOf[f.B8_4],
+           classOf[f.B8_5],
+           classOf[f.B8_6],
+           classOf[f.B8_7],
+           classOf[f.B8_8],
+           classOf[f.B8_9],
+           classOf[f.B8_10],
+           classOf[f.B8_11],
+           classOf[f.B8_12],
+           classOf[f.B8_13],
+           classOf[f.B8_14],
+           classOf[f.B8_15] ).asInstanceOf[Seq[Class[Phase]]]
+
+    /** The resulting order: B0--B6, B6_0--B6_B15, B7, B8_0--B8_15, B8--B15 */
+    val expected = targets.slice(0, 7) ++ prerequisiteTargets ++ Some(targets(7)) ++ current ++ targets.drop(8)
+
+    val pm = new PhaseManager(targets ++ prerequisiteTargets ++ current, current.reverse)
+
+    writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/DeterministicOrder")
+
+    pm.flattenedTransformOrder.map(_.asClass) should be (expected)
+  }
+
+}
-- 
cgit v1.2.3


From 01fb87e1f8b1f9408827655e944036a9bcf76fd9 Mon Sep 17 00:00:00 2001
From: Schuyler Eldridge
Date: Thu, 18 Apr 2019 23:52:13 -0400
Subject: Make Transform extend TransformLike

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>
---
 src/main/scala/firrtl/Compiler.scala | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

(limited to 'src')

diff --git a/src/main/scala/firrtl/Compiler.scala b/src/main/scala/firrtl/Compiler.scala
index c01564d2..b72fd4ce 100644
--- a/src/main/scala/firrtl/Compiler.scala
+++ b/src/main/scala/firrtl/Compiler.scala
@@ -11,7 +11,7 @@ import firrtl.annotations._
 import firrtl.ir.Circuit
 import firrtl.Utils.throwInternalError
 import firrtl.annotations.transforms.{EliminateTargetPaths, ResolvePaths}
-import firrtl.options.StageUtils
+import firrtl.options.{StageUtils, TransformLike}
 
 /** Container of all annotations for a Firrtl compiler */
 class AnnotationSeq private (private[firrtl] val underlying: List[Annotation]) {
@@ -169,7 +169,7 @@ final case object UnknownForm extends CircuitForm(-1) {
 // scalastyle:on magic.number
 
 /** The basic unit of operating on a Firrtl AST */
-abstract class Transform extends LazyLogging {
+abstract class Transform extends TransformLike[CircuitState] {
   /** A convenience function useful for debugging and error messages */
   def name: String = this.getClass.getSimpleName
   /** The [[firrtl.CircuitForm]] that this transform requires to operate on */
@@ -185,6 +185,8 @@ abstract class Transform extends LazyLogging {
     */
   protected def execute(state: CircuitState): CircuitState
 
+  def transform(state: CircuitState): CircuitState = execute(state)
+
   /** Convenience method to get annotations relevant to this Transform
     *
     * @param state The [[CircuitState]] form which to extract annotations
-- 
cgit v1.2.3