WiringTransform Refactor (#648)

Massive refactoring to WiringTransform with the use of a new EulerTour 
class to speed things up via fast least common ancestor (LCA) queries.

Changes include (but are not limited to):

* Use lowest common ancestor when wiring
* Add EulerTour class with naive and Berkman-Vishkin RMQ
* Adds LCA method for Instance Graph
* Enables "Two Sources" using "Top" wiring test as this is now valid
* Remove TopAnnotation from WiringTransform
* Represent WiringTransform sink as `Seq[Named]`
* Remove WiringUtils.countInstances, fix imports
* Support sources under sinks in WiringTransform
* Enable internal module wiring
* Support Wiring of Aggregates
h/t @edcote
fixes #728 

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>
Reviewed-by: Jack Koenig<jack.koenig3@gmail.com>

1 files changed, 36 insertions, 0 deletions

diff --git a/src/test/scala/firrtlTests/graph/EulerTourTests.scala b/src/test/scala/firrtlTests/graph/EulerTourTests.scala
new file mode 100644
index 00000000..0b69ce61
--- /dev/null
+++ b/src/test/scala/firrtlTests/graph/EulerTourTests.scala
@@ -0,0 +1,36 @@
+package firrtlTests.graph
+
+import firrtl.graph._
+import firrtlTests._
+
+class EulerTourTests extends FirrtlFlatSpec {
+
+  val top = "top"
+  val first_layer = Set("1a", "1b", "1c")
+  val second_layer = Set("2a", "2b", "2c")
+  val third_layer = Set("3a", "3b", "3c")
+  val last_null = Set.empty[String]
+
+  val m = Map(top -> first_layer) ++ first_layer.map{
+    case x => Map(x -> second_layer) }.flatten.toMap ++ second_layer.map{
+    case x => Map(x -> third_layer) }.flatten.toMap ++ third_layer.map{
+    case x => Map(x -> last_null) }.flatten.toMap
+
+  val graph = DiGraph(m)
+  val instances = graph.pathsInDAG(top).values.flatten
+  val tour = EulerTour(graph, top)
+
+  it should "show equivalency of Berkman--Vishkin and naive RMQs" in {
+    instances.toSeq.combinations(2).toList.map { case Seq(a, b) =>
+      tour.rmqNaive(a, b) should be (tour.rmqBV(a, b))
+    }
+  }
+
+  it should "determine naive RMQs of itself correctly" in {
+    instances.toSeq.map { case a => tour.rmqNaive(a, a) should be (a) }
+  }
+
+  it should "determine Berkman--Vishkin RMQs of itself correctly" in {
+    instances.toSeq.map { case a => tour.rmqNaive(a, a) should be (a) }
+  }
+}