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