Deprecate InstanceGraph (#1800)

* InstanceKeyGraph: add staticInstanceCount, getGraph and getChildrenInstanceMap

* InstanceKeyGraph: reachableModules, unreachableModules, lowestCommonAncestor and fullHierarchy

* Replace usage of InstanceGraph with InstanceKeyGraph

Also deprecates all unused methods.

* WiringUtils: make new version of sinksToSources package private

This will make our live easier next time we need to change it.

* CircuitGraph: use InstanceKeyGraph

* InstanceKeyGraphSpec: respect maximum line width

* InstanceKeyGraph: make constructor private

* InstanceKeyGraph: move lowestCommonAncestor function to Wiring

* WiringUtils: update deprecation message

1 files changed, 233 insertions, 6 deletions

diff --git a/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala b/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala
index 8d073ecb..ec403259 100644
--- a/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala
+++ b/src/test/scala/firrtlTests/analyses/InstanceKeyGraphSpec.scala
@@ -4,10 +4,105 @@ package firrtlTests.analyses
 
 import firrtl.analyses.InstanceKeyGraph
 import firrtl.analyses.InstanceKeyGraph.InstanceKey
+import firrtl.annotations.TargetToken.OfModule
+import firrtl.graph.DiGraph
 import firrtl.testutils.FirrtlFlatSpec
 
 class InstanceKeyGraphSpec extends FirrtlFlatSpec {
-  behavior of "InstanceKeyGraph"
+  behavior of "InstanceKeyGraph.graph"
+
+  private def getEdgeSet(graph: DiGraph[String]): collection.Map[String, collection.Set[String]] = {
+    (graph.getVertices map {v => (v, graph.getEdges(v))}).toMap
+  }
+
+  it should "recognize a simple hierarchy" in {
+    val input =
+      """circuit Top :
+        |  module Top :
+        |    inst c1 of Child1
+        |    inst c2 of Child2
+        |  module Child1 :
+        |    inst a of Child1a
+        |    inst b of Child1b
+        |    skip
+        |  module Child1a :
+        |    skip
+        |  module Child1b :
+        |    skip
+        |  module Child2 :
+        |    skip
+        |""".stripMargin
+
+    val graph = InstanceKeyGraph(parse(input)).graph.transformNodes(_.module)
+    getEdgeSet(graph) shouldBe Map(
+      "Top" -> Set("Child1", "Child2"),
+      "Child1" -> Set("Child1a", "Child1b"),
+      "Child2" -> Set(), "Child1a" -> Set(), "Child1b" -> Set())
+  }
+
+  it should "recognize disconnected hierarchies" in {
+    val input =
+      """circuit Top :
+        |  module Top :
+        |    inst c of Child1
+        |  module Child1 :
+        |    skip
+        |
+        |  module Top2 :
+        |    inst a of Child2
+        |    inst b of Child3
+        |    skip
+        |  module Child2 :
+        |    inst a of Child2a
+        |    inst b of Child2b
+        |    skip
+        |  module Child2a :
+        |    skip
+        |  module Child2b :
+        |    skip
+        |  module Child3 :
+        |    skip
+        |""".stripMargin
+
+    val graph = InstanceKeyGraph(parse(input)).graph.transformNodes(_.module)
+    getEdgeSet(graph) shouldBe Map(
+      "Top" -> Set("Child1"),
+      "Top2" -> Set("Child2", "Child3"),
+      "Child2" -> Set("Child2a", "Child2b"),
+      "Child1" -> Set(), "Child2a" -> Set(), "Child2b" -> Set(), "Child3" -> Set())
+  }
+
+  it should "not drop duplicate nodes when they collide as a result of transformNodes" in {
+    val input =
+      """circuit Top :
+        |  module Buzz :
+        |    skip
+        |  module Fizz :
+        |    inst b of Buzz
+        |  module Foo :
+        |    inst f1 of Fizz
+        |  module Bar :
+        |    inst f2 of Fizz
+        |  module Top :
+        |    inst f of Foo
+        |    inst b of Bar
+        |""".stripMargin
+    val graph = InstanceKeyGraph(parse(input)).graph
+
+    // Create graphs with edges from child to parent module
+    // g1 has collisions on parents to children, ie. it combines:
+    //   (f1, Fizz) -> (b, Buzz) and (f2, Fizz) -> (b, Buzz)
+    val g1 = graph.transformNodes(_.module).reverse
+    g1.getEdges("Fizz") shouldBe Set("Foo", "Bar")
+
+    val g2 = graph.reverse.transformNodes(_.module)
+    // g2 combines
+    //   (f1, Fizz) -> (f, Foo) and (f2, Fizz) -> (b, Bar)
+    g2.getEdges("Fizz") shouldBe Set("Foo", "Bar")
+  }
+
+
+  behavior of "InstanceKeyGraph.getChildInstances"
 
   // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
   // experience non-determinism
@@ -29,7 +124,7 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
                   |    skip
                   |""".stripMargin
     val circuit = parse(input)
-    val instGraph = new InstanceKeyGraph(circuit)
+    val instGraph = InstanceKeyGraph(circuit)
     val childMap = instGraph.getChildInstances
     childMap.map(_._1) should equal (Seq("Top", "Child1", "Child1a", "Child1b", "Child2"))
   }
@@ -50,12 +145,14 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
                   |    skip
                   |""".stripMargin
     val circuit = parse(input)
-    val instGraph = new InstanceKeyGraph(circuit)
+    val instGraph = InstanceKeyGraph(circuit)
     val childMap = instGraph.getChildInstances.toMap
     val insts = childMap("Top").map(_.name)
     insts should equal (Seq("a", "b", "c", "d", "e", "f"))
   }
 
+  behavior of "InstanceKeyGraph.moduleOrder"
+
   it should "compute a correct and deterministic module order" in {
     val input = """
                   |circuit Top :
@@ -80,12 +177,14 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
                   |    skip
                   |""".stripMargin
     val circuit = parse(input)
-    val instGraph = new InstanceKeyGraph(circuit)
+    val instGraph = InstanceKeyGraph(circuit)
     val order = instGraph.moduleOrder.map(_.name)
     // Where it has freedom, the instance declaration order will be reversed.
     order should equal (Seq("Top", "Child3", "Child4", "Child2", "Child1", "Child1b", "Child1a"))
   }
 
+  behavior of "InstanceKeyGraph.findInstancesInHierarchy"
+
   it should "find hierarchical instances correctly in disconnected hierarchies" in {
     val input =
       """circuit Top :
@@ -111,9 +210,10 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
         |""".stripMargin
 
     val circuit = parse(input)
-    val iGraph = new InstanceKeyGraph(circuit)
+    val iGraph = InstanceKeyGraph(circuit)
     iGraph.findInstancesInHierarchy("Top") shouldBe Seq(Seq(InstanceKey("Top", "Top")))
-    iGraph.findInstancesInHierarchy("Child1") shouldBe Seq(Seq(InstanceKey("Top", "Top"), InstanceKey("c", "Child1")))
+    iGraph.findInstancesInHierarchy("Child1") shouldBe
+      Seq(Seq(InstanceKey("Top", "Top"), InstanceKey("c", "Child1")))
     iGraph.findInstancesInHierarchy("Top2") shouldBe Nil
     iGraph.findInstancesInHierarchy("Child2") shouldBe Nil
     iGraph.findInstancesInHierarchy("Child2a") shouldBe Nil
@@ -121,4 +221,131 @@ class InstanceKeyGraphSpec extends FirrtlFlatSpec {
     iGraph.findInstancesInHierarchy("Child3") shouldBe Nil
   }
 
+  behavior of "InstanceKeyGraph.staticInstanceCount"
+
+  it should "report that there is one instance of the top module" in {
+    val input =
+      """|circuit Foo:
+         |  module Foo:
+         |    skip
+         |""".stripMargin
+    val iGraph = InstanceKeyGraph(parse(input))
+    val expectedCounts = Map(OfModule("Foo") -> 1)
+    iGraph.staticInstanceCount should be (expectedCounts)
+  }
+
+  it should "report correct number of instances for a sample circuit" in {
+    val input =
+      """|circuit Foo:
+         |  module Baz:
+         |    skip
+         |  module Bar:
+         |    inst baz1 of Baz
+         |    inst baz2 of Baz
+         |    inst baz3 of Baz
+         |    skip
+         |  module Foo:
+         |    inst bar1 of Bar
+         |    inst bar2 of Bar
+         |""".stripMargin
+    val iGraph = InstanceKeyGraph(parse(input))
+    val expectedCounts = Map(OfModule("Foo") -> 1,
+      OfModule("Bar") -> 2,
+      OfModule("Baz") -> 3)
+    iGraph.staticInstanceCount should be (expectedCounts)
+  }
+
+  it should "report zero instances for dead modules" in {
+    val input =
+      """|circuit Foo:
+         |  module Bar:
+         |    skip
+         |  module Foo:
+         |    skip
+         |""".stripMargin
+    val iGraph = InstanceKeyGraph(parse(input))
+    val expectedCounts = Map(OfModule("Foo") -> 1,
+      OfModule("Bar") -> 0)
+    iGraph.staticInstanceCount should be (expectedCounts)
+  }
+
+  behavior of "InstanceKeyGraph.getChildInstanceMap"
+
+  it should "preserve Module declaration order" in {
+    val input = """
+                  |circuit Top :
+                  |  module Top :
+                  |    inst c1 of Child1
+                  |    inst c2 of Child2
+                  |    inst c3 of Child1
+                  |    inst c4 of Child1
+                  |    inst c5 of Child1
+                  |  module Child1 :
+                  |    inst a of Child1a
+                  |    inst b of Child1b
+                  |    skip
+                  |  module Child1a :
+                  |    skip
+                  |  module Child1b :
+                  |    skip
+                  |  module Child2 :
+                  |    skip
+                  |""".stripMargin
+    val circuit = parse(input)
+    val instGraph = InstanceKeyGraph(circuit)
+    val childMap = instGraph.getChildInstanceMap
+
+    val modules = childMap.keys.toSeq.map(_.value)
+    assert(modules == Seq("Top", "Child1", "Child1a", "Child1b", "Child2"))
+
+    assert(childMap(OfModule("Child1a")).isEmpty)
+    assert(childMap(OfModule("Child1b")).isEmpty)
+    assert(childMap(OfModule("Child2")).isEmpty)
+
+    val topInstances = childMap(OfModule("Top")).map { case (k,v) => k.value -> v.value}.toSeq
+    assert(topInstances ==
+      Seq("c1" -> "Child1", "c2" -> "Child2", "c3" -> "Child1", "c4" -> "Child1", "c5" -> "Child1"))
+
+    val child1Instance = childMap(OfModule("Child1")).map { case (k,v) => k.value -> v.value}.toSeq
+    assert(child1Instance == Seq("a" -> "Child1a", "b" -> "Child1b"))
+  }
+
+  behavior of "InstanceKeyGraph.fullHierarchy"
+
+  // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
+  // experience non-determinism
+  it should "have defined fullHierarchy order" in {
+    val input =
+      """circuit Top :
+        |  module Top :
+        |    inst a of Child
+        |    inst b of Child
+        |    inst c of Child
+        |    inst d of Child
+        |    inst e of Child
+        |  module Child :
+        |    skip
+        |""".stripMargin
+
+    val instGraph = InstanceKeyGraph(parse(input))
+    val hier = instGraph.fullHierarchy
+    hier.keys.toSeq.map(_.name) should equal (Seq("Top", "a", "b", "c", "d", "e"))
+  }
+
+  behavior of "Reachable/Unreachable helper methods"
+
+  they should "report correct reachable/unreachable counts" in {
+    val input =
+      """|circuit Top:
+         |  module Unreachable:
+         |    skip
+         |  module Reachable:
+         |    skip
+         |  module Top:
+         |    inst reachable of Reachable
+         |""".stripMargin
+    val iGraph = InstanceKeyGraph(parse(input))
+    iGraph.reachableModules should contain theSameElementsAs Seq(OfModule("Top"), OfModule("Reachable"))
+    iGraph.unreachableModules should contain theSameElementsAs Seq(OfModule("Unreachable"))
+  }
 }