docs/doxygen/graphbuilder.py

   1 #!/usr/bin/env python3
   2 #
   3 # This file is part of the GROMACS molecular simulation package.
   4 #
   5 # Copyright (c) 2012,2013,2014,2015,2018,2019, by the GROMACS development team, led by
   6 # Mark Abraham, David van der Spoel, Berk Hess, and Erik Lindahl,
   7 # and including many others, as listed in the AUTHORS file in the
   8 # top-level source directory and at http://www.gromacs.org.
   9 #
  10 # GROMACS is free software; you can redistribute it and/or
  11 # modify it under the terms of the GNU Lesser General Public License
  12 # as published by the Free Software Foundation; either version 2.1
  13 # of the License, or (at your option) any later version.
  14 #
  15 # GROMACS is distributed in the hope that it will be useful,
  16 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  17 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18 # Lesser General Public License for more details.
  19 #
  20 # You should have received a copy of the GNU Lesser General Public
  21 # License along with GROMACS; if not, see
  22 # http://www.gnu.org/licenses, or write to the Free Software Foundation,
  23 # Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA.
  24 #
  25 # If you want to redistribute modifications to GROMACS, please
  26 # consider that scientific software is very special. Version
  27 # control is crucial - bugs must be traceable. We will be happy to
  28 # consider code for inclusion in the official distribution, but
  29 # derived work must not be called official GROMACS. Details are found
  30 # in the README & COPYING files - if they are missing, get the
  31 # official version at http://www.gromacs.org.
  32 #
  33 # To help us fund GROMACS development, we humbly ask that you cite
  34 # the research papers on the package. Check out http://www.gromacs.org.
  35
  36 """Generate include dependency graphs.
  37
  38 This script generates include dependency graphs from the GROMACS source tree.
  39 One graph is generated to show inter-module dependencies, and separate graphs
  40 for each module to show file-level dependencies within the module.
  41
  42 Output format for the graphs is suitable for processing with 'dot' in graphviz.
  43
  44 The graphs are built from the source tree representation constructed in
  45 gmxtree.py.
  46
  47 Classes Graph, Node, Edge, and EdgeType provide a relatively general
  48 implementation for constructing 'dot' graphs.  GraphBuilder is used to
  49 create Graph instances from a gmxtree.GromacsTree object; the actual graph
  50 objects will not contain any references to the gmxtree objects.
  51
  52 When run in script mode, the GromacsTree object is first constructed, and then
  53 GraphBuilder is used to construct the necessary graphs, which are then written
  54 out.
  55
  56 The produced graphs are documented in doxygen.md.
  57 """
  58
  59 import os.path
  60 import re
  61 import functools
  62
  63 from gmxtree import DocType
  64
  65 @functools.total_ordering
  66 class EdgeType(object):
  67
  68     """Enumeration type for edge types in include dependency graphs."""
  69
  70     # Mapping to string representation for the internal integer values
  71     _names = ['test', 'pubimpl', 'libimpl', 'library', 'public',
  72             'intramodule', 'legacy', 'undocumented']
  73
  74     def __init__(self, value):
  75         """Initialize a EdgeType instance.
  76
  77         EdgeType.{test,pubimpl,...,undocumented} should be used outside the
  78         class instead of calling the constructor.
  79         """
  80         self._value = value
  81
  82     def __str__(self):
  83         """Return string representation for the edge type (for debugging)."""
  84         return self._names[self._value]
  85
  86     def __eq__(self, other):
  87         """Order edge types in the order of increasing coupling."""
  88         return self._value == other._value
  89
  90     def __lt__(self, other):
  91         """Order edge types in the order of increasing coupling."""
  92         return self._value < other._value
  93
  94 # Tests depend on test
  95 EdgeType.test = EdgeType(0)
  96 # Implementation depends on public/library headers
  97 EdgeType.pubimpl = EdgeType(1)
  98 EdgeType.libimpl = EdgeType(2)
  99 # Library header depends on other module
 100 EdgeType.library = EdgeType(3)
 101 # Public header depends on other module
 102 EdgeType.public = EdgeType(4)
 103 # Intramodule dependency
 104 EdgeType.intramodule = EdgeType(5)
 105 EdgeType.legacy = EdgeType(6)
 106 EdgeType.cyclic = EdgeType(7)
 107 # Invalid dependency
 108 EdgeType.undocumented = EdgeType(8)
 109
 110 class Edge(object):
 111
 112     """Graph edge between two Node objects in 'dot' graph.
 113
 114     Signifies an include dependency between the two nodes, and manages types
 115     associated with the dependencies.
 116     """
 117
 118     def __init__(self, fromnode, tonode, edgetype):
 119         """Create edge between given Nodes with given type."""
 120         self._fromnode = fromnode
 121         self._tonode = tonode
 122         self._edgetype = edgetype
 123
 124     def merge_edge(self, other):
 125         """Merge another edge into this one and choose an appropriate type.
 126
 127         Updates the type of this edge based on the types of the merged edges.
 128         """
 129         self._edgetype = max(self._edgetype, other._edgetype)
 130
 131     def format(self):
 132         """Format this edge for 'dot'."""
 133         # If you change these styles, update also the legend in modulegraph.md
 134         if self._fromnode.is_file_node() and self._tonode.is_file_node():
 135             properties = ''
 136         elif self._edgetype == EdgeType.intramodule:
 137             properties = ''
 138         elif self._edgetype == EdgeType.test:
 139             # TODO: Consider if only some test edges should be made non-constraints
 140             properties = 'color=".33 .8 .8", style=dashed, constraint=no'
 141         elif self._edgetype == EdgeType.libimpl:
 142             properties = 'color=".66 .8 .8", style=dashed'
 143         elif self._edgetype == EdgeType.pubimpl:
 144             properties = 'color=black, style=dashed'
 145         elif self._edgetype == EdgeType.library:
 146             properties = 'color=".66 .8 .8"'
 147         elif self._edgetype == EdgeType.public:
 148             properties = 'color=black'
 149         elif self._edgetype == EdgeType.legacy:
 150             properties = 'color=grey75'
 151         elif self._edgetype == EdgeType.cyclic:
 152             properties = 'color=red, constraint=no'
 153         else: # undocumented
 154             properties = 'color=red'
 155         return '{0} -> {1} [{2}]'.format(self._fromnode.get_nodename(),
 156                                          self._tonode.get_nodename(),
 157                                          properties)
 158
 159 class Node(object):
 160
 161     """Node in 'dot' graph."""
 162
 163     def __init__(self, nodename, label, style=None, properties=None, is_file=False):
 164         """Create node with given attributes.
 165
 166         is_file does not affect the appearance of the node, but is used for
 167         formatting edges between two files differently from other edges.
 168         style and properties should be iterables with graphviz attributes for
 169         the node.
 170
 171         Node can have child nodes.  Such nodes are rendered as cluster
 172         subgraphs for 'dot'.
 173         """
 174         self._nodename = nodename
 175         self._label = label
 176         if style:
 177             self._style = ','.join(style)
 178         else:
 179             self._style = None
 180         if properties:
 181             self._properties = ', '.join(properties)
 182         else:
 183             self._properties = None
 184         self._is_file = is_file
 185         self._children = []
 186
 187     def add_child(self, child):
 188         """Add a child node."""
 189         self._children.append(child)
 190
 191     def clear_children(self):
 192         """Remove all children from the node."""
 193         self._children = []
 194
 195     def is_file_node(self):
 196         """Return True if the node was created with is_file=True."""
 197         return self._is_file
 198
 199     def get_nodename(self):
 200         """Get internal name of the node in 'dot'."""
 201         return self._nodename
 202
 203     def get_children(self, recursive=False):
 204         """Get list of child nodes."""
 205         if recursive:
 206             result = list(self._children)
 207             for child in self._children:
 208                 result.extend(child.get_children(recursive=True))
 209             return result
 210         else:
 211             return self._children
 212
 213     def format(self):
 214         """Format this node for 'dot'."""
 215         # TODO: Take indent as a parameter to make output marginally nicer.
 216         result = ''
 217         if self._children:
 218             result += '    subgraph cluster_{0} {{\n' \
 219                           .format(self._nodename)
 220             result += '        label = "{0}"\n'.format(self._label)
 221             for child in self._children:
 222                 result += child.format()
 223             result += '    }\n'
 224         else:
 225             properties = 'label="{0}"'.format(self._label)
 226             if self._properties:
 227                 properties += ', ' + self._properties
 228             if self._style:
 229                 properties += ', style="{0}"'.format(self._style)
 230             result += '    {0} [{1}]\n'.format(self._nodename, properties)
 231         return result
 232
 233
 234 class Graph(object):
 235
 236     """Graph for 'dot'."""
 237
 238     def __init__(self, nodes, edges):
 239         """Create graph with given nodes and edges."""
 240         self._nodes = set(nodes)
 241         self._edges = edges
 242         self._left_to_right = False
 243         self._concentrate = True
 244
 245     def set_options(self, left_to_right=None, concentrate=None):
 246         """Set output options for the graph."""
 247         if left_to_right != None:
 248             self._left_to_right = left_to_right
 249         if concentrate != None:
 250             self._concentrate = concentrate
 251
 252     def merge_nodes(self, nodes, target):
 253         """Merge a set of nodes into a single node.
 254
 255         All nodes from the list nodes are merged into the target node.
 256         All edges to or from the merged nodes are rerouted to/from target
 257         instead.  Duplicate edges are not created.  Instead, if an edge already
 258         exists, the edge types are merged.  All nodes from the list nodes are
 259         removed from the graph after the merge is done.
 260         """
 261         nodes = set(nodes)
 262         nodes.add(target)
 263         newedges = []
 264         edgesto = dict()
 265         edgesfrom = dict()
 266         for edge in self._edges:
 267             isfrom = (edge._fromnode in nodes)
 268             isto = (edge._tonode in nodes)
 269             if isfrom and isto:
 270                 pass
 271             elif isfrom:
 272                 if not edge._tonode in edgesfrom:
 273                     edgesfrom[edge._tonode] = \
 274                             Edge(target, edge._tonode, edge._edgetype)
 275                 else:
 276                     edgesfrom[edge._tonode].merge_edge(edge)
 277             elif isto:
 278                 if not edge._fromnode in edgesto:
 279                     edgesto[edge._fromnode] = \
 280                             Edge(edge._fromnode, target, edge._edgetype)
 281                 else:
 282                     edgesto[edge._fromnode].merge_edge(edge)
 283             else:
 284                 newedges.append(edge)
 285         newedges.extend(edgesfrom.values())
 286         newedges.extend(edgesto.values())
 287         self._edges = newedges
 288
 289     def collapse_node(self, node):
 290         """Merge all children of a node into the node.
 291
 292         All child nodes are removed after the merge is done.
 293         """
 294         nodes = node.get_children(recursive=True)
 295         self.merge_nodes(nodes, node)
 296         node.clear_children()
 297
 298     def write(self, outfile):
 299         """Write the graph in 'dot' format."""
 300         outfile.write('digraph includedeps {\n')
 301         if self._left_to_right:
 302             outfile.write('    rankdir = LR\n')
 303         if self._concentrate:
 304             outfile.write('    concentrate = true\n')
 305         outfile.write('    node [fontname="FreeSans",fontsize=10,height=.2,'
 306                                  'shape=box]\n')
 307         for node in self._nodes:
 308             outfile.write(node.format())
 309         for edge in self._edges:
 310             outfile.write('    ' + edge.format() + '\n')
 311         outfile.write('}\n')
 312
 313 class GraphBuilder(object):
 314
 315     """Builder for Graph objects from gmxtree.GromacsTree representation."""
 316
 317     def __init__(self, tree):
 318         """Initialize builder for a given tree representation."""
 319         self._tree = tree
 320
 321     def _create_file_node(self, fileobj, filenodes):
 322         """Create graph node for a file object.
 323
 324         filenodes is a dict() that maps file objects to their nodes, and is
 325         updated by this call.
 326         """
 327         nodename = re.subn(r'[-./]', '_', fileobj.get_relpath())[0]
 328         style = []
 329         properties = []
 330         properties.append('URL="\\ref {0}"'.format(fileobj.get_name()))
 331         if not fileobj.get_module():
 332             style.append('bold')
 333             properties.append('color=red')
 334         if fileobj.is_test_file():
 335             style.append('filled')
 336             properties.append('fillcolor=".33 .2 1"')
 337         elif fileobj.is_source_file():
 338             style.append('filled')
 339             properties.append('fillcolor=grey75')
 340         elif fileobj.get_api_type() == DocType.public:
 341             style.append('filled')
 342             properties.append('fillcolor=".66 .2 1"')
 343         elif fileobj.get_api_type() == DocType.library:
 344             style.append('filled')
 345             properties.append('fillcolor=".66 .5 1"')
 346         node = Node(nodename, fileobj.get_name(), style, properties, is_file=True)
 347         filenodes[fileobj] = node
 348         return node
 349
 350     def _get_file_edge_type(self, fromfile, tofile):
 351         """Get EdgeType for an edge between two file objects.
 352
 353         Determines the type for the edge from the information provided by
 354         gmxtree.
 355         """
 356         intramodule = (fromfile.get_module() == tofile.get_module())
 357         is_legacy = not tofile.api_type_is_reliable()
 358         if fromfile.get_module() == tofile.get_module():
 359             return EdgeType.intramodule
 360         elif tofile.get_api_type() == DocType.internal and not tofile.is_public():
 361             if is_legacy:
 362                 return EdgeType.legacy
 363             else:
 364                 return EdgeType.undocumented
 365         elif fromfile.is_test_file():
 366             return EdgeType.test
 367         elif tofile.is_test_file():
 368             return EdgeType.undocumented
 369         elif fromfile.is_module_internal():
 370             if tofile.is_public():
 371                 return EdgeType.pubimpl
 372             elif tofile.get_api_type() == DocType.library:
 373                 return EdgeType.libimpl
 374             elif is_legacy:
 375                 return EdgeType.legacy
 376             elif not tofile.is_documented():
 377                 return EdgeType.undocumented
 378             else:
 379                 raise ValueError('Unknown edge type between {0} and {1}'
 380                         .format(fromfile.get_relpath(), tofile.get_relpath()))
 381         elif fromfile.get_api_type() == DocType.library:
 382             return EdgeType.library
 383         elif fromfile.is_public():
 384             if tofile.is_public():
 385                 return EdgeType.public
 386             else:
 387                 return EdgeType.undocumented
 388         elif is_legacy:
 389             return EdgeType.legacy
 390         else:
 391             raise ValueError('Unknown edge type between {0} and {1}'
 392                     .format(fromfile.get_relpath(), tofile.get_relpath()))
 393
 394     def _create_file_edge(self, fromfile, tofile, filenodes):
 395         """Create edge between two file objects.
 396
 397         Determines the type for the edge from the information provided by
 398         gmxtree.
 399         """
 400         edgetype = self._get_file_edge_type(fromfile, tofile)
 401         return Edge(filenodes[fromfile], filenodes[tofile], edgetype)
 402
 403     def _create_file_edges(self, filenodes):
 404         """Create edges between all file nodes.
 405
 406         Create edges between file nodes specified in filenodes from all include
 407         dependencies.  An edge is created only if both ends of the dependency
 408         are in the list of nodes.
 409         """
 410         edges = []
 411         for fileobj in filenodes.keys():
 412             for includedfile in fileobj.get_includes():
 413                 otherfile = includedfile.get_file()
 414                 if otherfile and otherfile in filenodes:
 415                     edge = self._create_file_edge(fileobj, otherfile, filenodes)
 416                     edges.append(edge)
 417         return edges
 418
 419     def _get_module_color(self, modulegroup):
 420         # If you change these styles, update also the legend in modulegraph.md
 421         if modulegroup == 'legacy':
 422             return 'fillcolor=grey75'
 423         elif modulegroup == 'analysismodules':
 424             return 'fillcolor="0 .2 1"'
 425         elif modulegroup == 'utilitymodules':
 426             return 'fillcolor=".08 .2 1"'
 427         elif modulegroup == 'mdrun':
 428             return 'fillcolor=".75 .2 1"'
 429         return None
 430
 431     def _create_module_node(self, module):
 432         """Create node for a module."""
 433         style = []
 434         properties = []
 435         properties.append('shape=ellipse')
 436         if module.is_documented():
 437             properties.append('URL="\\ref {0}"'.format(module.get_name()))
 438         if not module.is_documented():
 439             fillcolor = self._get_module_color('legacy')
 440         else:
 441             fillcolor = self._get_module_color(module.get_group())
 442         if fillcolor:
 443             style.append('filled')
 444             properties.append(fillcolor)
 445         rootdir = module.get_root_dir()
 446         nodename = 'module_' + re.subn(r'[-./]', '_', rootdir.get_relpath())[0]
 447         label = module.get_name()[7:]
 448         node = Node(nodename, label, style, properties)
 449         return node
 450
 451     def _create_module_edges(self, modulenodes):
 452         """Create edges between all module nodes.
 453
 454         Create edges between module nodes specified in modulenodes from all
 455         include dependencies.  An edge is created only if both ends of the
 456         dependency are in the list of nodes.
 457         """
 458         edges = []
 459         for moduleobj in modulenodes.keys():
 460             for dep in moduleobj.get_dependencies():
 461                 othermodule = dep.get_other_module()
 462                 if othermodule and othermodule in modulenodes:
 463                     if dep.is_cycle_suppressed():
 464                         edgetype = EdgeType.cyclic
 465                     else:
 466                         edgetype = max([
 467                             self._get_file_edge_type(x.get_including_file(), x.get_file())
 468                             for x in dep.get_included_files()])
 469                     edge = Edge(modulenodes[moduleobj], modulenodes[othermodule], edgetype)
 470                     edges.append(edge)
 471         return edges
 472
 473     def create_modules_graph(self):
 474         """Create module dependency graph."""
 475         nodes = []
 476         modulenodes = dict()
 477         libgromacsnode = Node('libgromacs', 'libgromacs')
 478         nodes.append(libgromacsnode)
 479         for moduleobj in self._tree.get_modules():
 480             node = self._create_module_node(moduleobj)
 481             if moduleobj.get_root_dir().get_relpath().startswith('src/gromacs'):
 482                 libgromacsnode.add_child(node)
 483             else:
 484                 nodes.append(node)
 485             modulenodes[moduleobj] = node
 486         edges = self._create_module_edges(modulenodes)
 487         graph = Graph(nodes, edges)
 488         graph.set_options(concentrate=False)
 489         return graph
 490
 491     def create_module_file_graph(self, module):
 492         """Create file dependency graph for files within a module."""
 493         filenodes = dict()
 494         nodes = []
 495         for fileobj in module.get_files():
 496             nodes.append(self._create_file_node(fileobj, filenodes))
 497         edges = self._create_file_edges(filenodes)
 498         graph = Graph(nodes, edges)
 499         graph.set_options(left_to_right=True)
 500         return graph
 501
 502 def main():
 503     """Run the graph generation script."""
 504     import os
 505     import sys
 506
 507     from optparse import OptionParser
 508
 509     from gmxtree import GromacsTree
 510     from reporter import Reporter
 511
 512     parser = OptionParser()
 513     parser.add_option('-S', '--source-root',
 514                       help='Source tree root directory')
 515     parser.add_option('-B', '--build-root',
 516                       help='Build tree root directory')
 517     parser.add_option('--ignore-cycles',
 518                       help='Set file with module dependencies to ignore in cycles')
 519     parser.add_option('-o', '--outdir', default='.',
 520                       help='Specify output directory for graphs')
 521     parser.add_option('-q', '--quiet', action='store_true',
 522                       help='Do not write status messages')
 523     options, args = parser.parse_args()
 524
 525     reporter = Reporter(quiet=True)
 526
 527     if not options.quiet:
 528         sys.stderr.write('Scanning source tree...\n')
 529     tree = GromacsTree(options.source_root, options.build_root, reporter)
 530     if not options.quiet:
 531         sys.stderr.write('Reading source files...\n')
 532     tree.scan_files()
 533     if options.ignore_cycles:
 534         tree.load_cycle_suppression_list(options.ignore_cycles)
 535     if not options.quiet:
 536         sys.stderr.write('Reading Doxygen XML files...\n')
 537     tree.load_xml(only_files=True)
 538
 539     if not options.quiet:
 540         sys.stderr.write('Writing graphs...\n')
 541     graphbuilder = GraphBuilder(tree)
 542     if not os.path.exists(options.outdir):
 543         os.mkdir(options.outdir)
 544
 545     filename = os.path.join(options.outdir, 'module-deps.dot')
 546     graph = graphbuilder.create_modules_graph()
 547     with open(filename, 'w') as outfile:
 548         graph.write(outfile)
 549
 550     # Skip some modules that are too big to make any sense
 551     skippedmodules = ('gmxlib', 'mdlib', 'gmxana', 'gmxpreprocess')
 552     for module in tree.get_modules():
 553         if not module.get_name()[7:] in skippedmodules:
 554             filename = '{0}-deps.dot'.format(module.get_name())
 555             filename = os.path.join(options.outdir, filename)
 556             graph = graphbuilder.create_module_file_graph(module)
 557             with open(filename, 'w') as outfile:
 558                 graph.write(outfile)
 559
 560 if __name__ == '__main__':
 561     main()