Merge pull request #1357 from freechipsproject/dependency-api-updates

Omnibus Dependency API Updates

9 files changed, 515 insertions, 193 deletions

diff --git a/src/main/scala/firrtl/options/DependencyManager.scala b/src/main/scala/firrtl/options/DependencyManager.scala
index 604a1b10..4880ab8f 100644
--- a/src/main/scala/firrtl/options/DependencyManager.scala
+++ b/src/main/scala/firrtl/options/DependencyManager.scala
@@ -18,19 +18,26 @@ case class DependencyManagerException(message: String, cause: Throwable = null)
   * @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] {
+  import DependencyManagerUtils.CharSet
+
+  override lazy val prerequisites = currentState
+
+  override lazy val dependents = Seq.empty
+
+  override def invalidates(a: B): Boolean = (_currentState &~ _targets)(oToD(a))
 
   /** 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[Dependency]
-  private lazy val _targets: LinkedHashSet[Dependency] = targets
-    .foldLeft(new LinkedHashSet[Dependency]()){ case (a, b) => a += b }
+  def targets: Seq[Dependency[B]]
+  private lazy val _targets: LinkedHashSet[Dependency[B]] = targets
+    .foldLeft(new LinkedHashSet[Dependency[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[Dependency]
-  private lazy val _currentState: LinkedHashSet[Dependency] = currentState
-    .foldLeft(new LinkedHashSet[Dependency]()){ case (a, b) => a += b }
+  def currentState: Seq[Dependency[B]]
+  private lazy val _currentState: LinkedHashSet[Dependency[B]] = currentState
+    .foldLeft(new LinkedHashSet[Dependency[B]]()){ case (a, b) => a += b }
 
   /** Existing transform objects that have already been constructed */
   def knownObjects: Set[B]
@@ -42,11 +49,11 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
 
   /** Store of conversions between classes and objects. Objects that do not exist in the map will be lazily constructed.
     */
-  protected lazy val classToObject: LinkedHashMap[Dependency, B] = {
-    val init = LinkedHashMap[Dependency, B](knownObjects.map(x => x.getClass -> x).toSeq: _*)
+  protected lazy val dependencyToObject: LinkedHashMap[Dependency[B], B] = {
+    val init = LinkedHashMap[Dependency[B], B](knownObjects.map(x => oToD(x) -> x).toSeq: _*)
     (_targets ++ _currentState)
       .filter(!init.contains(_))
-      .map(x => init(x) = safeConstruct(x))
+      .map(x => init(x) = x.getObject())
     init
   }
 
@@ -54,42 +61,42 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
     * requirements. This is used to solve sub-problems arising from invalidations.
     */
   protected def copy(
-    targets: Seq[Dependency],
-    currentState: Seq[Dependency],
-    knownObjects: ISet[B] = classToObject.values.toSet): B
+    targets: Seq[Dependency[B]],
+    currentState: Seq[Dependency[B]],
+    knownObjects: ISet[B] = dependencyToObject.values.toSet): B
 
-  /** Implicit conversion from Class[B] to B */
-  private implicit def cToO(c: Dependency): B = classToObject.getOrElseUpdate(c, safeConstruct(c))
+  /** Implicit conversion from Dependency to B */
+  private implicit def dToO(d: Dependency[B]): B = dependencyToObject.getOrElseUpdate(d, d.getObject())
 
-  /** Implicit conversion from B to Class[B] */
-  private implicit def oToC(b: B): Dependency = b.getClass
+  /** Implicit conversion from B to Dependency */
+  private implicit def oToD(b: B): Dependency[B] = Dependency.fromTransform(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[Dependency],
-                   blacklist: LinkedHashSet[Dependency],
-                   extractor: B => Set[Dependency] ): LinkedHashMap[B, LinkedHashSet[B]] = {
+  private def bfs( start: LinkedHashSet[Dependency[B]],
+                   blacklist: LinkedHashSet[Dependency[B]],
+                   extractor: B => Set[Dependency[B]] ): LinkedHashMap[B, LinkedHashSet[B]] = {
 
     val (queue, edges) = {
-      val a: Queue[Dependency]                    = Queue(start.toSeq:_*)
+      val a: Queue[Dependency[B]]                    = Queue(start.toSeq:_*)
       val b: LinkedHashMap[B, LinkedHashSet[B]] = LinkedHashMap[B, LinkedHashSet[B]](
-        start.map((cToO(_) -> LinkedHashSet[B]())).toSeq:_*)
+        start.map((dToO(_) -> LinkedHashSet[B]())).toSeq:_*)
       (a, b)
     }
 
     while (queue.nonEmpty) {
-      val u: Dependency = queue.dequeue
-      for (v <- extractor(classToObject(u))) {
+      val u: Dependency[B] = queue.dequeue
+      for (v <- extractor(dependencyToObject(u))) {
         if (!blacklist.contains(v) && !edges.contains(v)) {
           queue.enqueue(v)
         }
         if (!edges.contains(v)) {
-          val obj = cToO(v)
+          val obj = dToO(v)
           edges(obj) = LinkedHashSet.empty
-          classToObject += (v -> obj)
+          dependencyToObject += (v -> obj)
         }
-        edges(classToObject(u)) = edges(classToObject(u)) + classToObject(v)
+        edges(dependencyToObject(u)) = edges(dependencyToObject(u)) + dependencyToObject(v)
       }
     }
 
@@ -105,9 +112,9 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
   /** A directed graph consisting of prerequisite edges */
   private lazy val prerequisiteGraph: DiGraph[B] = {
     val edges = bfs(
-      start = _targets -- _currentState,
+      start = _targets &~ _currentState,
       blacklist = _currentState,
-      extractor = (p: B) => new LinkedHashSet[Dependency]() ++ p.prerequisites -- _currentState)
+      extractor = (p: B) => new LinkedHashSet[Dependency[B]]() ++ p.prerequisites &~ _currentState)
     DiGraph(edges)
   }
 
@@ -116,7 +123,15 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
     */
   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
+    DiGraph(new LinkedHashMap() ++ v.map(vv => vv -> (v & (vv.dependents.toSet).map(dToO)))).reverse
+  }
+
+  /** A directed graph of *optional* prerequisites. Each optional prerequisite is promoted to a full prerequisite if the
+    * optional prerequisite is already a node in the prerequisite graph.
+    */
+  private lazy val optionalPrerequisitesGraph: DiGraph[B] = {
+    val v = new LinkedHashSet() ++ prerequisiteGraph.getVertices
+    DiGraph(new LinkedHashMap() ++ v.map(vv => vv -> (v & (vv.optionalPrerequisites.toSet).map(dToO))))
   }
 
   /** A directed graph consisting of prerequisites derived from ALL targets. This is necessary for defining targets for
@@ -125,7 +140,7 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
   private lazy val otherDependents: DiGraph[B] = {
     val edges = {
       val x = new LinkedHashMap ++ _targets
-        .map(classToObject)
+        .map(dependencyToObject)
         .map{ a => a -> prerequisiteGraph.getVertices.filter(a._dependents(_)) }
       x
         .values
@@ -136,16 +151,18 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
   }
 
   /** A directed graph consisting of all prerequisites, including prerequisites derived from dependents */
-  lazy val dependencyGraph: DiGraph[B] = prerequisiteGraph + dependentsGraph
+  lazy val dependencyGraph: DiGraph[B] = prerequisiteGraph + dependentsGraph + optionalPrerequisitesGraph
 
   /** A directed graph consisting of invalidation edges */
   lazy val invalidateGraph: DiGraph[B] = {
-    val v = dependencyGraph.getVertices
+    val v = new LinkedHashSet() ++ dependencyGraph.getVertices
     DiGraph(
       bfs(
-        start = _targets -- _currentState,
+        start = v.map(oToD(_)),
         blacklist = _currentState,
-        extractor = (p: B) => v.filter(p.invalidates).map(_.getClass).toSet))
+
+        /* Explore all invalidated transforms **EXCEPT** the current transform! */
+        extractor = (p: B) => v.filter(p.invalidates).map(oToD(_)).toSet - oToD(p)))
       .reverse
   }
 
@@ -157,14 +174,6 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
             |${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.
@@ -175,48 +184,45 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
     */
   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.
+    /* Topologically sort the dependency graph to determine a "good" initial ordering.
      */
     val sorted = {
-      val seed = cyclePossible("invalidates", invalidateGraph){ invalidateGraph.linearize }.reverse
+      val edges = {
+        val v = cyclePossible("invalidates", invalidateGraph){ invalidateGraph.linearize }.reverse
+        /* A comparison function that will sort vertices based on the topological sort of the invalidation graph */
+        val cmp =
+          (l: B, r: B) => v.foldLeft((Map.empty[B, Dependency[B] => Boolean], Set.empty[Dependency[B]])){
+            case ((m, s), r) => (m + (r -> ((a: Dependency[B]) => !s(a))), s + r) }._1(l)(r)
+        new LinkedHashMap() ++
+          v.map(vv => vv -> (new LinkedHashSet() ++ (dependencyGraph.getEdges(vv).toSeq.sortWith(cmp))))
+      }
 
       cyclePossible("prerequisites/dependents", dependencyGraph) {
-        dependencyGraph
-          .seededLinearize(Some(seed))
+        DiGraph(edges)
+          .linearize
           .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                        }
+    /* [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(oToD) ++
+        otherDependents.getEdges(in).toSeq.map(oToD)
+      val preprocessing: Option[B] = {
+        if ((prereqs -- state).nonEmpty) { Some(this.copy(prereqs.toSeq, state.toSeq)) }
+        else                             { None                                        }
       }
-
-      (s ++ missing, l ++ postprocessing)
+      /* "in" is added *after* invalidation because a transform my not invalidate itself! */
+      ((state ++ prereqs).map(dToO).filterNot(in.invalidates).map(oToD) + in, out ++ preprocessing :+ in)
     }
-
-    if (!_targets.subsetOf(state)) {
-      throw new DependencyManagerException(
-        s"The final state ($state) did not include the requested targets (${targets})!")
+    val postprocessing: Option[B] = {
+      if ((_targets -- s).nonEmpty) { Some(this.copy(_targets.toSeq, s.toSeq)) }
+      else                          { None                                     }
     }
-    lowerers
+    l ++ postprocessing
   }
 
   /** A version of the [[DependencyManager.transformOrder transformOrder]] that flattens the transforms of any internal
@@ -230,7 +236,7 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
   final override def transform(annotations: A): A = {
 
     /* A local store of each wrapper to it's underlying class. */
-    val wrapperToClass = new HashMap[B, Dependency]
+    val wrapperToClass = new HashMap[B, Dependency[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
@@ -249,7 +255,7 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
                   |  state: ${state.mkString("\n    -", "\n    -", "")}
                   |  prerequisites: ${prerequisites.mkString("\n    -", "\n    -", "")}""".stripMargin)
           }
-          (t.transform(a), ((state + wrapperToClass(t)).map(cToO).filterNot(t.invalidates).map(oToC)))
+          (t.transform(a), ((state + wrapperToClass(t)).map(dToO).filterNot(t.invalidates).map(oToD)))
       }._1
   }
 
@@ -283,15 +289,16 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
 
     val connections =
       Seq( (prerequisiteGraph, "edge []"),
-           (dependentsGraph,   """edge [color="#de2d26"]"""),
-           (invalidateGraph,   "edge [minlen=2,style=dashed,constraint=false]") )
+           (dependentsGraph,   """edge [style=bold color="#4292c6"]"""),
+           (invalidateGraph,   """edge [minlen=2 style=dashed constraint=false color="#fb6a4a"]"""),
+           (optionalPrerequisitesGraph, """edge [style=dotted color="#a1d99b"]""") )
         .flatMap{ case (a, b) => toGraphviz(a, b) }
         .mkString("\n")
 
     val nodes =
       (prerequisiteGraph + dependentsGraph + invalidateGraph + otherDependents)
         .getVertices
-        .map(v => s"""${transformName(v)} [label="${v.getClass.getName}"]""")
+        .map(v => s"""${transformName(v)} [label="${v.name}"]""")
 
     s"""|digraph DependencyManager {
         |  graph [rankdir=BT]
@@ -315,8 +322,8 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
     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(_.getName).mkString(", ")
-      val state = pm._currentState.toSeq.map(_.getName).mkString(", ")
+      val targets = pm._targets.toSeq.map(_.name).mkString(", ")
+      val state = pm._currentState.toSeq.map(_.name).mkString(", ")
 
       val header = s"""|${tab}subgraph cluster_$id {
                        |$tab  label="targets: $targets\\nstate: $state"
@@ -331,7 +338,7 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
         case a =>
           val name = s"""${transformName(a, "_" + id)}"""
           sorted += name
-          s"""$tab  $name [label="${a.getClass.getName}"]"""
+          s"""$tab  $name [label="${a.name}"]"""
       }.mkString("\n")
 
       (Seq(header, body, s"$tab}").mkString("\n"), offset)
@@ -345,6 +352,57 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
         |}""".stripMargin
   }
 
+  /** A method that can be overridden to define custom print handling. This is useful if you would like to make some
+    * transform print additional information.
+    * @param tab the current tab setting
+    * @param charSet the character set in use
+    * @param size the number of nodes at the current level of the tree
+    */
+  def customPrintHandling(
+    tab: String,
+    charSet: CharSet,
+    size: Int): Option[PartialFunction[(B, Int), Seq[String]]] = None
+
+  /** Helper utility when recursing during pretty printing
+    * @param tab an indentation string to use for every line of output
+    * @param charSet a collection of characters to use when printing
+    * @param preprocess a partial function that will be used before any other printing logic
+    */
+  def prettyPrintRec(tab: String, charSet: CharSet): Seq[String] = {
+
+    val (l, n, c) = (charSet.lastNode, charSet.notLastNode, charSet.continuation)
+    val last = transformOrder.size - 1
+
+    val defaultHandling: PartialFunction[(B, Int), Seq[String]] = {
+      case (a: DependencyManager[_, _], `last`) =>
+        Seq(s"$tab$l ${a.name}") ++ a.prettyPrintRec(s"""$tab${" " * c.size} """, charSet)
+      case (a: DependencyManager[_, _], _)      => Seq(s"$tab$n ${a.name}") ++ a.prettyPrintRec(s"$tab$c ", charSet)
+      case (a, `last`)                          => Seq(s"$tab$l ${a.name}")
+      case (a, _)                               => Seq(s"$tab$n ${a.name}")
+    }
+
+    val handling = customPrintHandling(tab, charSet, transformOrder.size) match {
+      case Some(a) => a.orElse(defaultHandling)
+      case None    => defaultHandling
+    }
+
+    transformOrder
+      .zipWithIndex
+      .flatMap(handling)
+  }
+
+  /** Textually show the determined transform order
+    * @param tab an indentation string to use for every line of output
+    * @param charSet a collection of characters to use when printing
+    */
+  def prettyPrint(
+    tab: String = "",
+    charSet: DependencyManagerUtils.CharSet = DependencyManagerUtils.PrettyCharSet): String = {
+
+    (Seq(s"$tab$name") ++ prettyPrintRec(tab, charSet)).mkString("\n")
+
+  }
+
 }
 
 /** A [[Phase]] that will ensure that some other [[Phase]]s and their prerequisites are executed.
@@ -356,15 +414,48 @@ trait DependencyManager[A, B <: TransformLike[A] with DependencyAPI[B]] extends
 class PhaseManager(
   val targets: Seq[PhaseManager.PhaseDependency],
   val currentState: Seq[PhaseManager.PhaseDependency] = Seq.empty,
-  val knownObjects: Set[Phase] = Set.empty) extends Phase with DependencyManager[AnnotationSeq, Phase] {
-
-  protected def copy(a: Seq[Dependency], b: Seq[Dependency], c: ISet[Phase]) = new PhaseManager(a, b, c)
+  val knownObjects: Set[Phase] = Set.empty) extends DependencyManager[AnnotationSeq, Phase] with Phase {
 
+  import PhaseManager.PhaseDependency
+  protected def copy(a: Seq[PhaseDependency], b: Seq[PhaseDependency], c: ISet[Phase]) = new PhaseManager(a, b, c)
 }
 
 object PhaseManager {
 
   /** The type used to represent dependencies between [[Phase]]s */
-  type PhaseDependency = Class[_ <: Phase]
+  type PhaseDependency = Dependency[Phase]
+
+}
+
+object DependencyManagerUtils {
+
+  /** A character set used for pretty printing
+    * @see [[PrettyCharSet]]
+    * @see [[ASCIICharSet]]
+    */
+  trait CharSet {
+    /** Used when printing the last node */
+    val lastNode: String
+
+    /** Used when printing a node that is NOT the last */
+    val notLastNode: String
+
+    /** Used while recursing into a node that is NOT the last */
+    val continuation: String
+  }
+
+  /** Uses prettier characters, but possibly not supported by all fonts */
+  object PrettyCharSet extends CharSet {
+    val lastNode     = "└──"
+    val notLastNode  = "├──"
+    val continuation = "│  "
+  }
+
+  /** Basic ASCII output */
+  object ASCIICharSet extends CharSet {
+    val lastNode     = "\\--"
+    val notLastNode  = "|--"
+    val continuation = "|  "
+  }
 
 }
diff --git a/src/main/scala/firrtl/options/Phase.scala b/src/main/scala/firrtl/options/Phase.scala
index e328282f..0e534ec8 100644
--- a/src/main/scala/firrtl/options/Phase.scala
+++ b/src/main/scala/firrtl/options/Phase.scala
@@ -8,6 +8,61 @@ import logger.LazyLogging
 
 import scala.collection.mutable.LinkedHashSet
 
+import scala.reflect
+import scala.reflect.ClassTag
+
+object Dependency {
+  def apply[A <: DependencyAPI[_] : ClassTag]: Dependency[A] = {
+    val clazz = reflect.classTag[A].runtimeClass
+    Dependency(Left(clazz.asInstanceOf[Class[A]]))
+  }
+
+  def apply[A <: DependencyAPI[_]](c: Class[_ <: A]): Dependency[A] = {
+    // It's forbidden to wrap the class of a singleton as a Dependency
+    require(c.getName.last != '$')
+    Dependency(Left(c))
+  }
+
+  def apply[A <: DependencyAPI[_]](o: A with Singleton): Dependency[A] = Dependency(Right(o))
+
+  def fromTransform[A <: DependencyAPI[_]](t: A): Dependency[A] = {
+    if (isSingleton(t)) {
+      Dependency[A](Right(t.asInstanceOf[A with Singleton]))
+    } else {
+      Dependency[A](Left(t.getClass))
+    }
+  }
+
+  private def isSingleton(obj: AnyRef): Boolean = {
+    reflect.runtime.currentMirror.reflect(obj).symbol.isModuleClass
+  }
+}
+
+case class Dependency[+A <: DependencyAPI[_]](id: Either[Class[_ <: A], A with Singleton]) {
+  def getObject(): A = id match {
+    case Left(c) => safeConstruct(c)
+    case Right(o) => o
+  }
+
+  def getSimpleName: String = id match {
+    case Left(c) => c.getSimpleName
+    case Right(o) => o.getClass.getSimpleName
+  }
+
+  def getName: String = id match {
+    case Left(c) => c.getName
+    case Right(o) => o.getClass.getName
+  }
+
+  /** 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)
+  }
+}
+
 /** A polymorphic mathematical transform
   * @tparam A the transformed type
   */
@@ -42,14 +97,18 @@ trait TransformLike[A] extends LazyLogging {
   */
 trait DependencyAPI[A <: DependencyAPI[A]] { this: TransformLike[_] =>
 
-  /** The type used to express dependencies: a class which itself has dependencies. */
-  type Dependency = Class[_ <: A]
-
   /** All transform that must run before this transform
     * $seqNote
     */
-  def prerequisites: Seq[Dependency] = Seq.empty
-  private[options] lazy val _prerequisites: LinkedHashSet[Dependency] = new LinkedHashSet() ++ prerequisites.toSet
+  def prerequisites: Seq[Dependency[A]] = Seq.empty
+  private[options] lazy val _prerequisites: LinkedHashSet[Dependency[A]] = new LinkedHashSet() ++ prerequisites.toSet
+
+  /** All transforms that, if a prerequisite of *another* transform, will run before this transform.
+    * $seqNote
+    */
+  def optionalPrerequisites: Seq[Dependency[A]] = Seq.empty
+  private[options] lazy val _optionalPrerquisites: LinkedHashSet[Dependency[A]] =
+    new LinkedHashSet() ++ optionalPrerequisites.toSet
 
   /** All transforms that must run ''after'' this transform
     *
@@ -70,8 +129,8 @@ trait DependencyAPI[A <: DependencyAPI[A]] { this: TransformLike[_] =>
     * @see [[firrtl.passes.CheckTypes]] for an example of an optional checking [[firrtl.Transform]]
     * $seqNote
     */
-  def dependents: Seq[Dependency] = Seq.empty
-  private[options] lazy val _dependents: LinkedHashSet[Dependency] = new LinkedHashSet() ++ dependents.toSet
+  def dependents: Seq[Dependency[A]] = Seq.empty
+  private[options] lazy val _dependents: LinkedHashSet[Dependency[A]] = new LinkedHashSet() ++ dependents.toSet
 
   /** A function that, given *another* transform (parameter `a`) will return true if this transform invalidates/undos the
     * effects of the *other* transform (parameter `a`).
@@ -86,7 +145,7 @@ trait DependencyAPI[A <: DependencyAPI[A]] { this: TransformLike[_] =>
   */
 trait PreservesAll[A <: DependencyAPI[A]] { this: DependencyAPI[A] =>
 
-  override def invalidates(a: A): Boolean = false
+  override final def invalidates(a: A): Boolean = false
 
 }
 
diff --git a/src/main/scala/firrtl/options/phases/AddDefaults.scala b/src/main/scala/firrtl/options/phases/AddDefaults.scala
index 8f7fe401..a327d930 100644
--- a/src/main/scala/firrtl/options/phases/AddDefaults.scala
+++ b/src/main/scala/firrtl/options/phases/AddDefaults.scala
@@ -3,14 +3,18 @@
 package firrtl.options.phases
 
 import firrtl.AnnotationSeq
-import firrtl.options.{Phase, TargetDirAnnotation}
+import firrtl.options.{Dependency, Phase, PreservesAll, TargetDirAnnotation}
 
 /** Add default annotations for a [[Stage]]
   *
   * This currently only adds a [[TargetDirAnnotation]]. This isn't necessary for a [[StageOptionsView]], but downstream
   * tools may expect a [[TargetDirAnnotation]] to exist.
   */
-class AddDefaults extends Phase {
+class AddDefaults extends Phase with PreservesAll[Phase] {
+
+  override val prerequisites = Seq(Dependency[GetIncludes], Dependency[ConvertLegacyAnnotations])
+
+  override val dependents = Seq.empty
 
   def transform(annotations: AnnotationSeq): AnnotationSeq = {
     val td = annotations.collectFirst{ case a: TargetDirAnnotation => a}.isEmpty
diff --git a/src/main/scala/firrtl/options/phases/Checks.scala b/src/main/scala/firrtl/options/phases/Checks.scala
index 0691e9b0..659247c9 100644
--- a/src/main/scala/firrtl/options/phases/Checks.scala
+++ b/src/main/scala/firrtl/options/phases/Checks.scala
@@ -4,12 +4,17 @@ package firrtl.options.phases
 
 import firrtl.AnnotationSeq
 import firrtl.annotations.Annotation
-import firrtl.options.{OptionsException, OutputAnnotationFileAnnotation, Phase, TargetDirAnnotation}
+import firrtl.options.{OptionsException, OutputAnnotationFileAnnotation, Phase, PreservesAll, TargetDirAnnotation}
+import firrtl.options.Dependency
 
 /** [[firrtl.options.Phase Phase]] that validates an [[AnnotationSeq]]. If successful, views of this [[AnnotationSeq]]
   * as [[StageOptions]] are guaranteed to succeed.
   */
-class Checks extends Phase {
+class Checks extends Phase with PreservesAll[Phase] {
+
+  override val prerequisites = Seq(Dependency[GetIncludes], Dependency[ConvertLegacyAnnotations], Dependency[AddDefaults])
+
+  override val dependents = Seq.empty
 
   /** Validate an [[AnnotationSeq]] for [[StageOptions]]
     * @throws OptionsException if annotations are invalid
diff --git a/src/main/scala/firrtl/options/phases/ConvertLegacyAnnotations.scala b/src/main/scala/firrtl/options/phases/ConvertLegacyAnnotations.scala
index 39f59572..a8e86a77 100644
--- a/src/main/scala/firrtl/options/phases/ConvertLegacyAnnotations.scala
+++ b/src/main/scala/firrtl/options/phases/ConvertLegacyAnnotations.scala
@@ -4,10 +4,14 @@ package firrtl.options.phases
 
 import firrtl.AnnotationSeq
 import firrtl.annotations.LegacyAnnotation
-import firrtl.options.Phase
+import firrtl.options.{Dependency, Phase, PreservesAll}
 
 /** Convert any [[firrtl.annotations.LegacyAnnotation LegacyAnnotation]]s to non-legacy variants */
-class ConvertLegacyAnnotations extends Phase {
+class ConvertLegacyAnnotations extends Phase with PreservesAll[Phase] {
+
+  override val prerequisites = Seq(Dependency[GetIncludes])
+
+  override val dependents = Seq.empty
 
   def transform(annotations: AnnotationSeq): AnnotationSeq = LegacyAnnotation.convertLegacyAnnos(annotations)
 
diff --git a/src/main/scala/firrtl/options/phases/DeletedWrapper.scala b/src/main/scala/firrtl/options/phases/DeletedWrapper.scala
index 0a959f32..5374aa66 100644
--- a/src/main/scala/firrtl/options/phases/DeletedWrapper.scala
+++ b/src/main/scala/firrtl/options/phases/DeletedWrapper.scala
@@ -4,7 +4,7 @@ package firrtl.options.phases
 
 import firrtl.AnnotationSeq
 import firrtl.annotations.DeletedAnnotation
-import firrtl.options.{Phase, Translator}
+import firrtl.options.{Phase, PreservesAll, Translator}
 
 import scala.collection.mutable
 
@@ -12,7 +12,12 @@ import scala.collection.mutable
   * wrapped [[firrtl.options.Phase Phase]] will be added as [[firrtl.annotations.DeletedAnnotation DeletedAnnotation]]s.
   * @param p a [[firrtl.options.Phase Phase]] to wrap
   */
-class DeletedWrapper(p: Phase) extends Phase with Translator[AnnotationSeq, (AnnotationSeq, AnnotationSeq)] {
+class DeletedWrapper(p: Phase) extends Phase with Translator[AnnotationSeq, (AnnotationSeq, AnnotationSeq)]
+    with PreservesAll[Phase] {
+
+  override val prerequisites = Seq.empty
+
+  override val dependents = Seq.empty
 
   override lazy val name: String = p.name
 
diff --git a/src/main/scala/firrtl/options/phases/GetIncludes.scala b/src/main/scala/firrtl/options/phases/GetIncludes.scala
index cb9bb840..f6c02543 100644
--- a/src/main/scala/firrtl/options/phases/GetIncludes.scala
+++ b/src/main/scala/firrtl/options/phases/GetIncludes.scala
@@ -7,7 +7,7 @@ import net.jcazevedo.moultingyaml._
 import firrtl.AnnotationSeq
 import firrtl.annotations.{AnnotationFileNotFoundException, JsonProtocol, LegacyAnnotation}
 import firrtl.annotations.AnnotationYamlProtocol._
-import firrtl.options.{InputAnnotationFileAnnotation, Phase, StageUtils}
+import firrtl.options.{InputAnnotationFileAnnotation, Phase, PreservesAll, StageUtils}
 import firrtl.FileUtils
 
 import java.io.File
@@ -16,7 +16,11 @@ import scala.collection.mutable
 import scala.util.{Try, Failure}
 
 /** Recursively expand all [[InputAnnotationFileAnnotation]]s in an [[AnnotationSeq]] */
-class GetIncludes extends Phase {
+class GetIncludes extends Phase with PreservesAll[Phase] {
+
+  override val prerequisites = Seq.empty
+
+  override val dependents = Seq.empty
 
   /** Read all [[annotations.Annotation]] from a file in JSON or YAML format
     * @param filename a JSON or YAML file of [[annotations.Annotation]]
diff --git a/src/main/scala/firrtl/options/phases/WriteOutputAnnotations.scala b/src/main/scala/firrtl/options/phases/WriteOutputAnnotations.scala
index bb2a8cd6..4a638393 100644
--- a/src/main/scala/firrtl/options/phases/WriteOutputAnnotations.scala
+++ b/src/main/scala/firrtl/options/phases/WriteOutputAnnotations.scala
@@ -4,14 +4,23 @@ package firrtl.options.phases
 
 import firrtl.AnnotationSeq
 import firrtl.annotations.{DeletedAnnotation, JsonProtocol}
-import firrtl.options.{Phase, StageOptions, Unserializable, Viewer}
+import firrtl.options.{Phase, PreservesAll, StageOptions, Unserializable, Viewer}
+import firrtl.options.Dependency
 
 import java.io.PrintWriter
 
 /** [[firrtl.options.Phase Phase]] that writes an [[AnnotationSeq]] to a file. A file is written if and only if a
   * [[StageOptions]] view has a non-empty [[StageOptions.annotationFileOut annotationFileOut]].
   */
-class WriteOutputAnnotations extends Phase {
+class WriteOutputAnnotations extends Phase with PreservesAll[Phase] {
+
+  override val prerequisites =
+    Seq( Dependency[GetIncludes],
+         Dependency[ConvertLegacyAnnotations],
+         Dependency[AddDefaults],
+         Dependency[Checks] )
+
+  override val dependents = Seq.empty
 
   /** Write the input [[AnnotationSeq]] to a fie. */
   def transform(annotations: AnnotationSeq): AnnotationSeq = {
diff --git a/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala b/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala
index 518728d2..744d621e 100644
--- a/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala
+++ b/src/test/scala/firrtlTests/options/PhaseManagerSpec.scala
@@ -5,7 +5,7 @@ package firrtlTests.options
 import org.scalatest.{FlatSpec, Matchers}
 
 import firrtl.AnnotationSeq
-import firrtl.options.{DependencyManagerException, Phase, PhaseManager, PreservesAll}
+import firrtl.options.{DependencyManagerException, Phase, PhaseManager, PreservesAll, Dependency}
 
 import java.io.{File, PrintWriter}
 
@@ -23,19 +23,19 @@ class A extends IdentityPhase {
 
 /** [[Phase]] that requires [[A]] and invalidates nothing */
 class B extends IdentityPhase {
-  override def prerequisites: Seq[Dependency] = Seq(classOf[A])
+  override def prerequisites = Seq(Dependency[A])
   override def invalidates(phase: Phase): Boolean = false
 }
 
 /** [[Phase]] that requires [[B]] and invalidates nothing */
 class C extends IdentityPhase {
-  override def prerequisites = Seq(classOf[A])
+  override def prerequisites = Seq(Dependency[A])
   override def invalidates(phase: Phase): Boolean = false
 }
 
 /** [[Phase]] that requires [[A]] and invalidates [[A]] */
 class D extends IdentityPhase {
-  override def prerequisites = Seq(classOf[A])
+  override def prerequisites = Seq(Dependency[A])
   override def invalidates(phase: Phase): Boolean = phase match {
     case _: A => true
     case _ => false
@@ -44,13 +44,13 @@ class D extends IdentityPhase {
 
 /** [[Phase]] that requires [[B]] and invalidates nothing */
 class E extends IdentityPhase {
-  override def prerequisites = Seq(classOf[B])
+  override def prerequisites = Seq(Dependency[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(classOf[B], classOf[C])
+  override def prerequisites = Seq(Dependency[B], Dependency[C])
   override def invalidates(phase: Phase): Boolean = phase match {
     case _: E => true
     case _ => false
@@ -60,7 +60,7 @@ class F extends IdentityPhase {
 
 /** [[Phase]] that requires [[C]] and invalidates [[F]] */
 class G extends IdentityPhase {
-  override def prerequisites = Seq(classOf[C])
+  override def prerequisites = Seq(Dependency[C])
   override def invalidates(phase: Phase): Boolean = phase match {
     case _: F => true
     case _ => false
@@ -68,11 +68,11 @@ class G extends IdentityPhase {
 }
 
 class CyclicA extends IdentityPhase with PreservesAll[Phase] {
-  override def prerequisites = Seq(classOf[CyclicB])
+  override def prerequisites = Seq(Dependency[CyclicB])
 }
 
 class CyclicB extends IdentityPhase with PreservesAll[Phase] {
-  override def prerequisites = Seq(classOf[CyclicA])
+  override def prerequisites = Seq(Dependency[CyclicA])
 }
 
 class CyclicC extends IdentityPhase {
@@ -95,25 +95,25 @@ object ComplicatedFixture {
     override def invalidates(phase: Phase): Boolean = false
   }
   class B extends IdentityPhase {
-    override def prerequisites = Seq(classOf[A])
+    override def prerequisites = Seq(Dependency[A])
     override def invalidates(phase: Phase): Boolean = false
   }
   class C extends IdentityPhase {
-    override def prerequisites = Seq(classOf[A])
+    override def prerequisites = Seq(Dependency[A])
     override def invalidates(phase: Phase): Boolean = phase match {
       case _: B => true
       case _ => false
     }
   }
   class D extends IdentityPhase {
-    override def prerequisites = Seq(classOf[B])
+    override def prerequisites = Seq(Dependency[B])
     override def invalidates(phase: Phase): Boolean = phase match {
       case _: C | _: E => true
       case _ => false
     }
   }
   class E extends IdentityPhase {
-    override def prerequisites = Seq(classOf[B])
+    override def prerequisites = Seq(Dependency[B])
     override def invalidates(phase: Phase): Boolean = false
   }
 
@@ -132,13 +132,13 @@ object RepeatedAnalysisFixture {
     override def invalidates(phase: Phase): Boolean = false
   }
   class A extends InvalidatesAnalysis {
-    override def prerequisites = Seq(classOf[Analysis])
+    override def prerequisites = Seq(Dependency[Analysis])
   }
   class B extends InvalidatesAnalysis {
-    override def prerequisites = Seq(classOf[A], classOf[Analysis])
+    override def prerequisites = Seq(Dependency[A], Dependency[Analysis])
   }
   class C extends InvalidatesAnalysis {
-    override def prerequisites = Seq(classOf[B], classOf[Analysis])
+    override def prerequisites = Seq(Dependency[B], Dependency[Analysis])
   }
 
 }
@@ -149,21 +149,21 @@ object InvertedAnalysisFixture {
     override def invalidates(phase: Phase): Boolean = false
   }
   class A extends IdentityPhase {
-    override def prerequisites = Seq(classOf[Analysis])
+    override def prerequisites = Seq(Dependency[Analysis])
     override def invalidates(phase: Phase): Boolean = phase match {
       case _: Analysis => true
       case _ => false
     }
   }
   class B extends IdentityPhase {
-    override def prerequisites = Seq(classOf[Analysis])
+    override def prerequisites = Seq(Dependency[Analysis])
     override def invalidates(phase: Phase): Boolean = phase match {
       case _: Analysis | _: A => true
       case _ => false
     }
   }
   class C extends IdentityPhase {
-    override def prerequisites = Seq(classOf[Analysis])
+    override def prerequisites = Seq(Dependency[Analysis])
     override def invalidates(phase: Phase): Boolean = phase match {
       case _: Analysis | _: B => true
       case _ => false
@@ -179,7 +179,7 @@ object DependentsFixture {
   }
 
   class Second extends IdentityPhase {
-    override val prerequisites = Seq(classOf[First])
+    override val prerequisites = Seq(Dependency[First])
     override def invalidates(phase: Phase): Boolean = false
   }
 
@@ -188,8 +188,8 @@ object DependentsFixture {
    * loop detection.
    */
   class Custom extends IdentityPhase {
-    override val prerequisites = Seq(classOf[First])
-    override val dependents = Seq(classOf[Second])
+    override val prerequisites = Seq(Dependency[First])
+    override val dependents = Seq(Dependency[Second])
     override def invalidates(phase: Phase): Boolean = false
   }
 
@@ -219,7 +219,7 @@ object ChainedInvalidationFixture {
     override def invalidates(phase: Phase): Boolean = false
   }
   class E extends IdentityPhase {
-    override val prerequisites = Seq(classOf[A], classOf[B], classOf[C], classOf[D])
+    override val prerequisites = Seq(Dependency[A], Dependency[B], Dependency[C], Dependency[D])
     override def invalidates(phase: Phase): Boolean = false
   }
 
@@ -253,8 +253,8 @@ object UnrelatedFixture {
   class B15 extends IdentityPhase with PreservesAll[Phase]
 
   class B6Sub extends B6 {
-    override val prerequisites = Seq(classOf[B6])
-    override val dependents = Seq(classOf[B7])
+    override val prerequisites = Seq(Dependency[B6])
+    override val dependents = Seq(Dependency[B7])
   }
 
   class B6_0 extends B6Sub
@@ -275,7 +275,7 @@ object UnrelatedFixture {
   class B6_15 extends B6Sub
 
   class B8Dep extends B8 {
-    override val dependents = Seq(classOf[B8])
+    override val dependents = Seq(Dependency[B8])
   }
 
   class B8_0 extends B8Dep
@@ -297,6 +297,90 @@ object UnrelatedFixture {
 
 }
 
+object CustomAfterOptimizationFixture {
+
+  class Root extends IdentityPhase with PreservesAll[Phase]
+
+  class OptMinimum extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[Root])
+    override val dependents = Seq(Dependency[AfterOpt])
+  }
+
+  class OptFull extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[Root], Dependency[OptMinimum])
+    override val dependents = Seq(Dependency[AfterOpt])
+  }
+
+  class AfterOpt extends IdentityPhase with PreservesAll[Phase]
+
+  class DoneMinimum extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[OptMinimum])
+  }
+
+  class DoneFull extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[OptFull])
+  }
+
+  class Custom extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[Root], Dependency[AfterOpt])
+    override val dependents = Seq(Dependency[DoneMinimum], Dependency[DoneFull])
+  }
+
+}
+
+object OptionalPrerequisitesFixture {
+
+  class Root extends IdentityPhase
+
+  class OptMinimum extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[Root])
+  }
+
+  class OptFull extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[Root], Dependency[OptMinimum])
+  }
+
+  class DoneMinimum extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[OptMinimum])
+  }
+
+  class DoneFull extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[OptFull])
+  }
+
+  class Custom extends IdentityPhase with PreservesAll[Phase] {
+    override val prerequisites = Seq(Dependency[Root])
+    override val optionalPrerequisites = Seq(Dependency[OptMinimum], Dependency[OptFull])
+    override val dependents = Seq(Dependency[DoneMinimum], Dependency[DoneFull])
+  }
+
+}
+
+object OrderingFixture {
+
+  class A extends IdentityPhase with PreservesAll[Phase]
+
+  class B extends IdentityPhase {
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: A => true
+      case _    => false
+    }
+  }
+
+  class C extends IdentityPhase {
+    override val prerequisites = Seq(Dependency[A], Dependency[B])
+    override def invalidates(phase: Phase): Boolean = phase match {
+      case _: B => true
+      case _    => false
+    }
+  }
+
+  class Cx extends C {
+    override val prerequisites = Seq(Dependency[B], Dependency[A])
+  }
+
+}
+
 class PhaseManagerSpec extends FlatSpec with Matchers {
 
   def writeGraphviz(pm: PhaseManager, dir: String): Unit = {
@@ -323,6 +407,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
       val f = new File(d + "/transformOrder.dot")
       val w = new PrintWriter(new File(d + "/transformOrder.dot"))
       try {
+        info("transform order:\n" + pm.prettyPrint("    "))
         w.write(pm.transformOrderToGraphviz())
         w.close
         maybeToPng(f)
@@ -336,7 +421,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
   behavior of this.getClass.getName
 
   it should "do nothing if all targets are reached" in {
-    val targets = Seq(classOf[A], classOf[B], classOf[C], classOf[D])
+    val targets = Seq(Dependency[A], Dependency[B], Dependency[C], Dependency[D])
     val pm = new PhaseManager(targets, targets)
 
     writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/DoNothing")
@@ -345,7 +430,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
   }
 
   it should "handle a simple dependency" in {
-    val targets = Seq(classOf[B])
+    val targets = Seq(Dependency[B])
     val order = Seq(classOf[A], classOf[B])
     val pm = new PhaseManager(targets)
 
@@ -355,7 +440,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
   }
 
   it should "handle a simple dependency with an invalidation" in {
-    val targets = Seq(classOf[A], classOf[B], classOf[C], classOf[D])
+    val targets = Seq(Dependency[A], Dependency[B], Dependency[C], Dependency[D])
     val order = Seq(classOf[A], classOf[D], classOf[A], classOf[B], classOf[C])
     val pm = new PhaseManager(targets)
 
@@ -365,7 +450,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
   }
 
   it should "handle a dependency with two invalidates optimally" in {
-    val targets = Seq(classOf[A], classOf[B], classOf[C], classOf[E], classOf[F], classOf[G])
+    val targets = Seq(Dependency[A], Dependency[B], Dependency[C], Dependency[E], Dependency[F], Dependency[G])
     val pm = new PhaseManager(targets)
 
     writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/TwoInvalidates")
@@ -374,7 +459,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
   }
 
   it should "throw an exception for cyclic prerequisites" in {
-    val targets = Seq(classOf[CyclicA], classOf[CyclicB])
+    val targets = Seq(Dependency[CyclicA], Dependency[CyclicB])
     val pm = new PhaseManager(targets)
 
     writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/CyclicPrerequisites")
@@ -384,7 +469,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
   }
 
   it should "throw an exception for cyclic invalidates" in {
-    val targets = Seq(classOf[CyclicC], classOf[CyclicD])
+    val targets = Seq(Dependency[CyclicC], Dependency[CyclicD])
     val pm = new PhaseManager(targets)
 
     writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/CyclicInvalidates")
@@ -395,7 +480,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
 
   it should "handle a complicated graph" in {
     val f = ComplicatedFixture
-    val targets = Seq(classOf[f.A], classOf[f.B], classOf[f.C], classOf[f.D], classOf[f.E])
+    val targets = Seq(Dependency[f.A], Dependency[f.B], Dependency[f.C], Dependency[f.D], Dependency[f.E])
     val pm = new PhaseManager(targets)
 
     writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/Complicated")
@@ -406,7 +491,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
 
   it should "handle repeated recomputed analyses" in {
     val f = RepeatedAnalysisFixture
-    val targets = Seq(classOf[f.A], classOf[f.B], classOf[f.C])
+    val targets = Seq(Dependency[f.A], Dependency[f.B], Dependency[f.C])
     val order =
       Seq( classOf[f.Analysis],
            classOf[f.A],
@@ -423,7 +508,7 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
 
   it should "handle inverted repeated recomputed analyses" in {
     val f = InvertedAnalysisFixture
-    val targets = Seq(classOf[f.A], classOf[f.B], classOf[f.C])
+    val targets = Seq(Dependency[f.A], Dependency[f.B], Dependency[f.C])
     val order =
       Seq( classOf[f.Analysis],
            classOf[f.C],
@@ -443,12 +528,12 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
     val f = DependentsFixture
 
     info("without the custom transform it runs: First -> Second")
-    val pm = new PhaseManager(Seq(classOf[f.Second]))
+    val pm = new PhaseManager(Seq(Dependency[f.Second]))
     val orderNoCustom = Seq(classOf[f.First], classOf[f.Second])
     pm.flattenedTransformOrder.map(_.getClass) should be (orderNoCustom)
 
     info("with the custom transform it runs:    First -> Custom -> Second")
-    val pmCustom = new PhaseManager(Seq(classOf[f.Custom], classOf[f.Second]))
+    val pmCustom = new PhaseManager(Seq(Dependency[f.Custom], Dependency[f.Second]))
     val orderCustom = Seq(classOf[f.First], classOf[f.Custom], classOf[f.Second])
 
     writeGraphviz(pmCustom, "test_run_dir/PhaseManagerSpec/SingleDependent")
@@ -459,8 +544,8 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
   it should "handle chained invalidation" in {
     val f = ChainedInvalidationFixture
 
-    val targets = Seq(classOf[f.A], classOf[f.E])
-    val current = Seq(classOf[f.B], classOf[f.C], classOf[f.D])
+    val targets = Seq(Dependency[f.A], Dependency[f.E])
+    val current = Seq(Dependency[f.B], Dependency[f.C], Dependency[f.D])
 
     val pm = new PhaseManager(targets, current)
     val order = Seq( classOf[f.A], classOf[f.B], classOf[f.C], classOf[f.D], classOf[f.E] )
@@ -475,71 +560,127 @@ class PhaseManagerSpec extends FlatSpec with Matchers {
 
     /** 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] )
+      Seq( Dependency[f.B0],
+           Dependency[f.B1],
+           Dependency[f.B2],
+           Dependency[f.B3],
+           Dependency[f.B4],
+           Dependency[f.B5],
+           Dependency[f.B6],
+           Dependency[f.B7],
+           Dependency[f.B8],
+           Dependency[f.B9],
+           Dependency[f.B10],
+           Dependency[f.B11],
+           Dependency[f.B12],
+           Dependency[f.B13],
+           Dependency[f.B14],
+           Dependency[f.B15] )
     /** 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] )
+      Seq( Dependency[f.B6_0],
+           Dependency[f.B6_1],
+           Dependency[f.B6_2],
+           Dependency[f.B6_3],
+           Dependency[f.B6_4],
+           Dependency[f.B6_5],
+           Dependency[f.B6_6],
+           Dependency[f.B6_7],
+           Dependency[f.B6_8],
+           Dependency[f.B6_9],
+           Dependency[f.B6_10],
+           Dependency[f.B6_11],
+           Dependency[f.B6_12],
+           Dependency[f.B6_13],
+           Dependency[f.B6_14],
+           Dependency[f.B6_15] )
     /** 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] )
+      Seq( Dependency[f.B8_0],
+           Dependency[f.B8_1],
+           Dependency[f.B8_2],
+           Dependency[f.B8_3],
+           Dependency[f.B8_4],
+           Dependency[f.B8_5],
+           Dependency[f.B8_6],
+           Dependency[f.B8_7],
+           Dependency[f.B8_8],
+           Dependency[f.B8_9],
+           Dependency[f.B8_10],
+           Dependency[f.B8_11],
+           Dependency[f.B8_12],
+           Dependency[f.B8_13],
+           Dependency[f.B8_14],
+           Dependency[f.B8_15] )
 
     /** 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 expectedDeps = targets.slice(0, 7) ++ prerequisiteTargets ++ Some(targets(7)) ++ current ++ targets.drop(8)
+    val expectedClasses = expectedDeps.map { case Dependency(Left(c)) => c }
 
     val pm = new PhaseManager(targets ++ prerequisiteTargets ++ current, current.reverse)
 
     writeGraphviz(pm, "test_run_dir/PhaseManagerSpec/DeterministicOrder")
 
-    pm.flattenedTransformOrder.map(_.getClass) should be (expected)
+    pm.flattenedTransformOrder.map(_.getClass) should be (expectedClasses)
+  }
+
+  it should "allow conditional placement of custom transforms" in {
+    val f = CustomAfterOptimizationFixture
+
+    val targetsMinimum = Seq(Dependency[f.Custom], Dependency[f.DoneMinimum])
+    val pmMinimum = new PhaseManager(targetsMinimum)
+
+    val targetsFull = Seq(Dependency[f.Custom], Dependency[f.DoneFull])
+    val pmFull = new PhaseManager(targetsFull)
+
+    val expectedMinimum = Seq(classOf[f.Root], classOf[f.OptMinimum], classOf[f.AfterOpt], classOf[f.Custom], classOf[f.DoneMinimum])
+    writeGraphviz(pmMinimum, "test_run_dir/PhaseManagerSpec/CustomAfterOptimization/minimum")
+    pmMinimum.flattenedTransformOrder.map(_.getClass) should be (expectedMinimum)
+
+    val expectedFull = Seq(classOf[f.Root], classOf[f.OptMinimum], classOf[f.OptFull], classOf[f.AfterOpt], classOf[f.Custom], classOf[f.DoneFull])
+    writeGraphviz(pmFull, "test_run_dir/PhaseManagerSpec/CustomAfterOptimization/full")
+    pmFull.flattenedTransformOrder.map(_.getClass) should be (expectedFull)
+  }
+
+  it should "support optional prerequisites" in {
+    val f = OptionalPrerequisitesFixture
+
+    val targetsMinimum = Seq(Dependency[f.Custom], Dependency[f.DoneMinimum])
+    val pmMinimum = new PhaseManager(targetsMinimum)
+
+    val targetsFull = Seq(Dependency[f.Custom], Dependency[f.DoneFull])
+    val pmFull = new PhaseManager(targetsFull)
+
+    val expectedMinimum = Seq(classOf[f.Root], classOf[f.OptMinimum], classOf[f.Custom], classOf[f.DoneMinimum])
+    writeGraphviz(pmMinimum, "test_run_dir/PhaseManagerSpec/CustomAfterOptimization/minimum")
+    pmMinimum.flattenedTransformOrder.map(_.getClass) should be (expectedMinimum)
+
+    val expectedFull = Seq(classOf[f.Root], classOf[f.OptMinimum], classOf[f.OptFull], classOf[f.Custom], classOf[f.DoneFull])
+    writeGraphviz(pmFull, "test_run_dir/PhaseManagerSpec/CustomAfterOptimization/full")
+    pmFull.flattenedTransformOrder.map(_.getClass) should be (expectedFull)
+  }
+
+  /** This tests a situation the ordering of edges matters. Namely, this test is dependent on the ordering in which
+    * DiGraph.linearize walks the edges of each node.
+    */
+  it should "choose the optimal solution irregardless of prerequisite ordering" in {
+    val f = OrderingFixture
+
+    {
+      val targets = Seq(Dependency[f.A], Dependency[f.B], Dependency[f.C])
+      val order = Seq(classOf[f.B], classOf[f.A], classOf[f.C], classOf[f.B], classOf[f.A])
+      (new PhaseManager(targets)).flattenedTransformOrder.map(_.getClass) should be (order)
+    }
+
+    {
+      val targets = Seq(Dependency[f.A], Dependency[f.B], Dependency[f.Cx])
+      val order = Seq(classOf[f.B], classOf[f.A], classOf[f.Cx], classOf[f.B], classOf[f.A])
+      (new PhaseManager(targets)).flattenedTransformOrder.map(_.getClass) should be (order)
+    }
   }
 
 }