Make InstanceGraph have deterministic and use defined iteration order (#843)

1 files changed, 69 insertions, 0 deletions

diff --git a/src/test/scala/firrtlTests/analyses/InstanceGraphTests.scala b/src/test/scala/firrtlTests/analyses/InstanceGraphTests.scala
index f01de1f4..e98c1895 100644
--- a/src/test/scala/firrtlTests/analyses/InstanceGraphTests.scala
+++ b/src/test/scala/firrtlTests/analyses/InstanceGraphTests.scala
@@ -15,6 +15,8 @@ class InstanceGraphTests extends FirrtlFlatSpec {
     (graph.getVertices map {v => (v, graph.getEdges(v))}).toMap
   }
 
+  behavior of "InstanceGraph"
+
   it should "recognize a simple hierarchy" in {
     val input = """
 circuit Top :
@@ -95,4 +97,71 @@ circuit Top :
     //   (f1, Fizz) -> (f, Foo) and (f2, Fizz) -> (b, Bar)
     g2.getEdges("Fizz") shouldBe Set("Foo", "Bar")
   }
+
+  // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
+  // experience non-determinism
+  it should "preserve Module declaration order" 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 circuit = ToWorkingIR.run(parse(input))
+    val instGraph = new InstanceGraph(circuit)
+    val childMap = instGraph.getChildrenInstances
+    childMap.keys.toSeq should equal (Seq("Top", "Child1", "Child1a", "Child1b", "Child2"))
+  }
+
+  // Note that due to optimized implementations of Map1-4, at least 5 entries are needed to
+  // experience non-determinism
+  it should "preserve Instance declaration 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
+      |    inst f of Child
+      |  module Child :
+      |    skip
+      |""".stripMargin
+    val circuit = ToWorkingIR.run(parse(input))
+    val instGraph = new InstanceGraph(circuit)
+    val childMap = instGraph.getChildrenInstances
+    val insts = childMap("Top").toSeq.map(_.name)
+    insts should equal (Seq("a", "b", "c", "d", "e", "f"))
+  }
+
+  // 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 circuit = ToWorkingIR.run(parse(input))
+    val instGraph = new InstanceGraph(circuit)
+    val hier = instGraph.fullHierarchy
+    hier.keys.toSeq.map(_.name) should equal (Seq("Top", "a", "b", "c", "d", "e"))
+  }
 }