Dependency Graphs (#2308)

* Further fixes to the example code.

* Bumped dependencies.

* Fixed Debouncer example code.

* Some more cleanup.

* Black's opinion.

* Run with pyVHDLModel dev-branch.

* Fixed imports for Name.

* Fixed test case.

* Added a formatter to write dependency graphs and hierarchy as graphml.

* Improved GraphML formatting.

* Write compile order graph.

* Computing compile order.

* Bumped dependencies.

* Black's opinion.

* Fixed incorrect dependency.

2 files changed, 350 insertions, 18 deletions

diff --git a/pyGHDL/dom/formatting/GraphML.py b/pyGHDL/dom/formatting/GraphML.py
new file mode 100644
index 000000000..7f72d54b5
--- /dev/null
+++ b/pyGHDL/dom/formatting/GraphML.py
@@ -0,0 +1,340 @@
+from pathlib import Path
+from textwrap import dedent
+from typing import Dict, List
+
+from pyTooling.Graph import Graph, Vertex
+
+from pyVHDLModel import (
+    DependencyGraphVertexKind,
+    DependencyGraphEdgeKind,
+    Library as VHDLModel_Library,
+    Document as VHDLModel_Document,
+)
+
+
+class DependencyGraphFormatter:
+    _graph: Graph
+
+    NODE_COLORS = {
+        DependencyGraphVertexKind.Document: "#999999",
+        DependencyGraphVertexKind.Library: "#99ccff",
+        DependencyGraphVertexKind.Package: "#ff9900",
+        DependencyGraphVertexKind.PackageBody: "#ff9900",
+        DependencyGraphVertexKind.Context: "#cc99ff",
+        DependencyGraphVertexKind.Entity: "#ffff99",
+        DependencyGraphVertexKind.Architecture: "#ff99cc",
+        DependencyGraphVertexKind.Configuration: "#ff9900",
+    }
+    EDGE_COLORS = {
+        DependencyGraphEdgeKind.SourceFile: "#000000",
+        DependencyGraphEdgeKind.CompileOrder: "#ff0000",
+        DependencyGraphEdgeKind.LibraryClause: "#000000",
+        DependencyGraphEdgeKind.UseClause: "#000000",
+        DependencyGraphEdgeKind.ContextReference: "#000000",
+        DependencyGraphEdgeKind.EntityImplementation: "#99ccff",
+        DependencyGraphEdgeKind.PackageImplementation: "#99ccff",
+        DependencyGraphEdgeKind.EntityInstantiation: "#000000",
+        DependencyGraphEdgeKind.ComponentInstantiation: "#000000",
+        DependencyGraphEdgeKind.ConfigurationInstantiation: "#000000",
+    }
+
+    def __init__(self, graph: Graph):
+        self._graph = graph
+
+    def WriteGraphML(self, path: Path):
+        with path.open("w") as file:
+            file.write(
+                dedent(
+                    f"""\
+            <graphml xmlns="http://graphml.graphdrawing.org/xmlns"
+                     xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+                     xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
+              <key id="nd1" for="node" attr.name="id" attr.type="string"/>
+              <key id="nd2" for="node" attr.name="value" attr.type="string"/>
+              <key id="nd3" for="node" attr.name="kind" attr.type="string"/>
+              <key id="nd4" for="node" attr.name="color" attr.type="string"/>
+
+              <key id="ed3" for="edge" attr.name="kind" attr.type="string"/>
+              <key id="ed4" for="edge" attr.name="color" attr.type="string"/>
+              <graph id="DependencyGraph"
+                     edgedefault="directed"
+                     parse.nodes="{len(self._graph._verticesWithID)}"
+                     parse.edges="{len(self._graph._edgesWithoutID)}"
+                     parse.order="nodesfirst">
+            """
+                )
+            )
+            groups: Dict[str, List[Vertex]] = {}
+            for vertex in self._graph._verticesWithID.values():
+                if isinstance(vertex.Value, VHDLModel_Library):
+                    identifier = vertex.Value.NormalizedIdentifier
+                elif isinstance(vertex.Value, VHDLModel_Document):
+                    identifier = vertex.Value.DesignUnits[0].Library.NormalizedIdentifier
+                else:
+                    identifier = vertex.Value.Library.NormalizedIdentifier
+
+                if identifier in groups:
+                    groups[identifier].append(vertex)
+                else:
+                    groups[identifier] = [vertex]
+
+            for group, vertices in groups.items():
+                file.write(
+                    dedent(
+                        """\
+                    {prefix}<node id="grp_{id}">
+                    {prefix}  <data key="nd2">{value}</data>
+                    {prefix}  <graph id="{id}" edgedefault="directed">
+                """
+                    ).format(prefix="    ", id=group, value=group)
+                )
+
+                for vertex in vertices:
+                    if vertex["kind"] is DependencyGraphVertexKind.Architecture:
+                        value = f"{vertex.Value.Entity.Identifier}({vertex.Value.Identifier})"
+                    elif vertex["kind"] is DependencyGraphVertexKind.Document:
+                        value = f"{vertex.ID}"
+                    else:
+                        value = f"{vertex.Value.Identifier}"
+                    file.write(
+                        dedent(
+                            """\
+                        {prefix}<node id="{vertex.ID}">
+                        {prefix}  <data key="nd1">{vertex.ID}</data>
+                        {prefix}  <data key="nd2">{value}</data>
+                        {prefix}  <data key="nd3">{vertex[kind].name}</data>
+                        {prefix}  <data key="nd4">{color}</data>
+                        {prefix}</node>
+                    """
+                        ).format(prefix="        ", vertex=vertex, value=value, color=self.NODE_COLORS[vertex["kind"]])
+                    )
+
+                file.write(
+                    dedent(
+                        """\
+                    {prefix}  </graph>
+                    {prefix}</node>
+                """
+                    ).format(prefix="    ")
+                )
+
+            edgeCount = 1
+            for edge in self._graph._edgesWithoutID:
+                file.write(
+                    dedent(
+                        """\
+                    {prefix}<edge id="e{edgeCount}" source="{edge.Source.ID}" target="{edge.Destination.ID}">
+                    {prefix}  <data key="ed3">{edge[kind].name}</data>
+                    {prefix}  <data key="ed4">{color}</data>
+                    {prefix}</edge>
+                """
+                    ).format(prefix="    ", edgeCount=edgeCount, edge=edge, color=self.EDGE_COLORS[edge["kind"]])
+                )
+                edgeCount += 1
+
+            file.write(
+                dedent(
+                    """\
+              </graph>
+            </graphml>
+            """
+                )
+            )
+
+
+class HierarchyGraphFormatter:
+    _graph: Graph
+
+    NODE_COLORS = {
+        DependencyGraphVertexKind.Document: "#999999",
+        DependencyGraphVertexKind.Library: "#99ccff",
+        DependencyGraphVertexKind.Package: "#ff9900",
+        DependencyGraphVertexKind.PackageBody: "#ff9900",
+        DependencyGraphVertexKind.Context: "#cc99ff",
+        DependencyGraphVertexKind.Entity: "#ffff99",
+        DependencyGraphVertexKind.Architecture: "#ff99cc",
+        DependencyGraphVertexKind.Configuration: "#ff9900",
+    }
+    EDGE_COLORS = {
+        DependencyGraphEdgeKind.SourceFile: "#000000",
+        DependencyGraphEdgeKind.CompileOrder: "#ff0000",
+        DependencyGraphEdgeKind.LibraryClause: "#000000",
+        DependencyGraphEdgeKind.UseClause: "#000000",
+        DependencyGraphEdgeKind.ContextReference: "#000000",
+        DependencyGraphEdgeKind.EntityImplementation: "#99ccff",
+        DependencyGraphEdgeKind.PackageImplementation: "#99ccff",
+        DependencyGraphEdgeKind.EntityInstantiation: "#000000",
+        DependencyGraphEdgeKind.ComponentInstantiation: "#000000",
+        DependencyGraphEdgeKind.ConfigurationInstantiation: "#000000",
+    }
+
+    def __init__(self, graph: Graph):
+        self._graph = graph
+
+    def WriteGraphML(self, path: Path):
+        with path.open("w") as file:
+            file.write(
+                dedent(
+                    f"""\
+            <graphml xmlns="http://graphml.graphdrawing.org/xmlns"
+                     xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+                     xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
+              <key id="nd1" for="node" attr.name="id" attr.type="string"/>
+              <key id="nd2" for="node" attr.name="value" attr.type="string"/>
+              <key id="nd3" for="node" attr.name="kind" attr.type="string"/>
+              <key id="nd4" for="node" attr.name="color" attr.type="string"/>
+
+              <key id="ed3" for="edge" attr.name="kind" attr.type="string"/>
+              <key id="ed4" for="edge" attr.name="color" attr.type="string"/>
+              <graph id="HierarchyGraph"
+                     edgedefault="directed"
+                     parse.nodes="{len(self._graph._verticesWithID)}"
+                     parse.edges="{len(self._graph._edgesWithoutID)}"
+                     parse.order="nodesfirst">
+            """
+                )
+            )
+
+            for vertex in self._graph._verticesWithID.values():
+                if vertex["kind"] is DependencyGraphVertexKind.Entity:
+                    file.write(
+                        dedent(
+                            """\
+                        {prefix}<node id="{vertex.ID}">
+                        {prefix}  <data key="nd1">{vertex.ID}</data>
+                        {prefix}  <data key="nd2">{vertex.Value.Identifier}</data>
+                        {prefix}  <data key="nd3">{vertex[kind].name}</data>
+                        {prefix}  <data key="nd4">{color}</data>
+                        {prefix}</node>
+                    """
+                        ).format(prefix="    ", vertex=vertex, color=self.NODE_COLORS[vertex["kind"]])
+                    )
+                elif vertex["kind"] is DependencyGraphVertexKind.Architecture:
+                    file.write(
+                        dedent(
+                            """\
+                        {prefix}<node id="{vertex.ID}">
+                        {prefix}  <data key="nd1">{vertex.ID}</data>
+                        {prefix}  <data key="nd2">{vertex.Value.Identifier}</data>
+                        {prefix}  <data key="nd3">{vertex[kind].name}</data>
+                        {prefix}  <data key="nd4">{color}</data>
+                        {prefix}</node>
+                    """
+                        ).format(prefix="    ", vertex=vertex, color=self.NODE_COLORS[vertex["kind"]])
+                    )
+
+            edgeCount = 1
+            for edge in self._graph._edgesWithoutID:
+                file.write(
+                    dedent(
+                        """\
+                    {prefix}<edge id="e{edgeCount}" source="{edge.Source.ID}" target="{edge.Destination.ID}">
+                    {prefix}  <data key="ed3">{edge[kind].name}</data>
+                    {prefix}  <data key="ed4">{color}</data>
+                    {prefix}</edge>
+                """
+                    ).format(prefix="    ", edgeCount=edgeCount, edge=edge, color=self.EDGE_COLORS[edge["kind"]])
+                )
+                edgeCount += 1
+
+            file.write(
+                dedent(
+                    """\
+              </graph>
+            </graphml>
+            """
+                )
+            )
+
+
+class CompileOrderGraphFormatter:
+    _graph: Graph
+
+    NODE_COLORS = {
+        DependencyGraphVertexKind.Document: "#999999",
+        DependencyGraphVertexKind.Library: "#99ccff",
+        DependencyGraphVertexKind.Package: "#ff9900",
+        DependencyGraphVertexKind.PackageBody: "#ff9900",
+        DependencyGraphVertexKind.Context: "#cc99ff",
+        DependencyGraphVertexKind.Entity: "#ffff99",
+        DependencyGraphVertexKind.Architecture: "#ff99cc",
+        DependencyGraphVertexKind.Configuration: "#ff9900",
+    }
+    EDGE_COLORS = {
+        DependencyGraphEdgeKind.SourceFile: "#000000",
+        DependencyGraphEdgeKind.CompileOrder: "#ff0000",
+        DependencyGraphEdgeKind.LibraryClause: "#000000",
+        DependencyGraphEdgeKind.UseClause: "#000000",
+        DependencyGraphEdgeKind.ContextReference: "#000000",
+        DependencyGraphEdgeKind.EntityImplementation: "#99ccff",
+        DependencyGraphEdgeKind.PackageImplementation: "#99ccff",
+        DependencyGraphEdgeKind.EntityInstantiation: "#000000",
+        DependencyGraphEdgeKind.ComponentInstantiation: "#000000",
+        DependencyGraphEdgeKind.ConfigurationInstantiation: "#000000",
+    }
+
+    def __init__(self, graph: Graph):
+        self._graph = graph
+
+    def WriteGraphML(self, path: Path):
+        print(path.absolute())
+        with path.open("w") as file:
+            file.write(
+                dedent(
+                    f"""\
+            <graphml xmlns="http://graphml.graphdrawing.org/xmlns"
+                     xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+                     xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
+              <key id="nd1" for="node" attr.name="id" attr.type="string"/>
+              <key id="nd2" for="node" attr.name="value" attr.type="string"/>
+              <key id="nd3" for="node" attr.name="kind" attr.type="string"/>
+              <key id="nd4" for="node" attr.name="color" attr.type="string"/>
+
+              <key id="ed3" for="edge" attr.name="kind" attr.type="string"/>
+              <key id="ed4" for="edge" attr.name="color" attr.type="string"/>
+              <graph id="CompileOrderGraph"
+                     edgedefault="directed"
+                     parse.nodes="{len(self._graph._verticesWithID)}"
+                     parse.edges="{len(self._graph._edgesWithoutID)}"
+                     parse.order="nodesfirst">
+            """
+                )
+            )
+
+            for vertex in self._graph._verticesWithID.values():
+                if vertex["kind"] is DependencyGraphVertexKind.Document:
+                    file.write(
+                        dedent(
+                            """\
+                        {prefix}<node id="{vertex.ID}">
+                        {prefix}  <data key="nd1">{vertex.ID}</data>
+                        {prefix}  <data key="nd2">{vertex.Value.Path.name}</data>
+                        {prefix}  <data key="nd3">{vertex[kind].name}</data>
+                        {prefix}  <data key="nd4">{color}</data>
+                        {prefix}</node>
+                    """
+                        ).format(prefix="    ", vertex=vertex, color=self.NODE_COLORS[vertex["kind"]])
+                    )
+
+            edgeCount = 1
+            for edge in self._graph._edgesWithoutID:
+                file.write(
+                    dedent(
+                        """\
+                    {prefix}<edge id="e{edgeCount}" source="{edge.Source.ID}" target="{edge.Destination.ID}">
+                    {prefix}  <data key="ed3">{edge[kind].name}</data>
+                    {prefix}  <data key="ed4">{color}</data>
+                    {prefix}</edge>
+                """
+                    ).format(prefix="    ", edgeCount=edgeCount, edge=edge, color=self.EDGE_COLORS[edge["kind"]])
+                )
+                edgeCount += 1
+
+            file.write(
+                dedent(
+                    """\
+              </graph>
+            </graphml>
+            """
+                )
+            )
diff --git a/pyGHDL/dom/formatting/prettyprint.py b/pyGHDL/dom/formatting/prettyprint.py
index da26372c4..5be27492d 100644
--- a/pyGHDL/dom/formatting/prettyprint.py
+++ b/pyGHDL/dom/formatting/prettyprint.py
@@ -34,6 +34,15 @@ from typing import List, Union
 
 from pyTooling.Decorators import export
 
+from pyVHDLModel.Base import NamedEntityMixin
+from pyVHDLModel.Interface import GenericInterfaceItem, PortInterfaceItem
+from pyVHDLModel.Subprogram import Function
+from pyVHDLModel.Object import BaseConstant, WithDefaultExpressionMixin
+from pyVHDLModel.Type import BaseType, FullType
+from pyVHDLModel.Concurrent import ConcurrentStatement
+
+from pyGHDL import GHDLBaseException
+from pyGHDL.dom.NonStandard import Document, Design, Library
 from pyGHDL.dom.Concurrent import (
     ConcurrentBlockStatement,
     ProcessStatement,
@@ -45,20 +54,6 @@ from pyGHDL.dom.Concurrent import (
     EntityInstantiation,
     ConcurrentProcedureCall,
 )
-from pyVHDLModel.SyntaxModel import (
-    GenericInterfaceItem,
-    NamedEntityMixin,
-    PortInterfaceItem,
-    WithDefaultExpressionMixin,
-    Function,
-    BaseType,
-    FullType,
-    BaseConstant,
-    ConcurrentStatement,
-)
-
-from pyGHDL import GHDLBaseException
-from pyGHDL.dom.NonStandard import Document, Design, Library
 from pyGHDL.dom.DesignUnit import (
     Entity,
     Architecture,
@@ -70,10 +65,7 @@ from pyGHDL.dom.DesignUnit import (
     UseClause,
     PackageInstantiation,
 )
-from pyGHDL.dom.Symbol import (
-    SimpleSubtypeSymbol,
-    ConstrainedCompositeSubtypeSymbol,
-)
+from pyGHDL.dom.Symbol import SimpleSubtypeSymbol, ConstrainedCompositeSubtypeSymbol
 from pyGHDL.dom.Type import (
     IntegerType,
     Subtype,