docs/doxygen/graphbuilder.py

   1 #!/usr/bin/python
   2 #
   3 # This file is part of the GROMACS molecular simulation package.
   4 #
   5 # Copyright (c) 2012,2013,2014, 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
  62 from gmxtree import DocType
  63
  64 class EdgeType(object):
  65
  66     """Enumeration type for edge types in include dependency graphs."""
  67
  68     # Mapping to string representation for the internal integer values
  69     _names = ['test', 'pubimpl', 'libimpl', 'library', 'public',
  70             'intramodule', 'legacy', 'undocumented']
  71
  72     def __init__(self, value):
  73         """Initialize a EdgeType instance.
  74
  75         EdgeType.{test,pubimpl,...,undocumented} should be used outside the
  76         class instead of calling the constructor.
  77         """
  78         self._value = value
  79
  80     def __str__(self):
  81         """Return string representation for the edge type (for debugging)."""
  82         return self._names[self._value]
  83
  84     def __cmp__(self, other):
  85         """Order edge types in the order of increasing coupling."""
  86         return cmp(self._value, other._value)
  87
  88 # Tests depend on test
  89 EdgeType.test = EdgeType(0)
  90 # Implementation depends on public/library headers
  91 EdgeType.pubimpl = EdgeType(1)
  92 EdgeType.libimpl = EdgeType(2)
  93 # Library header depends on other module
  94 EdgeType.library = EdgeType(3)
  95 # Public header depends on other module
  96 EdgeType.public = EdgeType(4)
  97 # Intramodule dependency
  98 EdgeType.intramodule = EdgeType(5)
  99 EdgeType.legacy = EdgeType(6)
 100 EdgeType.cyclic = EdgeType(7)
 101 # Invalid dependency
 102 EdgeType.undocumented = EdgeType(8)
 103
 104 class Edge(object):
 105
 106     """Graph edge between two Node objects in 'dot' graph.
 107
 108     Signifies an include dependency between the two nodes, and manages types
 109     associated with the dependencies.
 110     """
 111
 112     def __init__(self, fromnode, tonode, edgetype):
 113         """Create edge between given Nodes with given type."""
 114         self._fromnode = fromnode
 115         self._tonode = tonode
 116         self._edgetype = edgetype
 117
 118     def merge_edge(self, other):
 119         """Merge another edge into this one and choose an appropriate type.
 120
 121         Updates the type of this edge based on the types of the merged edges.
 122         """
 123         self._edgetype = max(self._edgetype, other._edgetype)
 124
 125     def format(self):
 126         """Format this edge for 'dot'."""
 127         # If you change these styles, update also the legend in modulegraph.md
 128         if self._fromnode.is_file_node() and self._tonode.is_file_node():
 129             properties = ''
 130         elif self._edgetype == EdgeType.intramodule:
 131             properties = ''
 132         elif self._edgetype == EdgeType.test:
 133             properties = 'color=".33 .8 .8", style=dashed'
 134         elif self._edgetype == EdgeType.libimpl:
 135             properties = 'color=".66 .8 .8", style=dashed'
 136         elif self._edgetype == EdgeType.pubimpl:
 137             properties = 'color=black, style=dashed'
 138         elif self._edgetype == EdgeType.library:
 139             properties = 'color=".66 .8 .8"'
 140         elif self._edgetype == EdgeType.public:
 141             properties = 'color=black'
 142         elif self._edgetype == EdgeType.legacy:
 143             properties = 'color=grey75'
 144         elif self._edgetype == EdgeType.cyclic:
 145             properties = 'color=red, constraint=no'
 146         else: # undocumented
 147             properties = 'color=red'
 148         return '{0} -> {1} [{2}]'.format(self._fromnode.get_nodename(),
 149                                          self._tonode.get_nodename(),
 150                                          properties)
 151
 152 class Node(object):
 153
 154     """Node in 'dot' graph."""
 155
 156     def __init__(self, nodename, label, style=None, properties=None, is_file=False):
 157         """Create node with given attributes.
 158
 159         is_file does not affect the appearance of the node, but is used for
 160         formatting edges between two files differently from other edges.
 161         style and properties should be iterables with graphviz attributes for
 162         the node.
 163
 164         Node can have child nodes.  Such nodes are rendered as cluster
 165         subgraphs for 'dot'.
 166         """
 167         self._nodename = nodename
 168         self._label = label
 169         if style:
 170             self._style = ','.join(style)
 171         else:
 172             self._style = None
 173         if properties:
 174             self._properties = ', '.join(properties)
 175         else:
 176             self._properties = None
 177         self._is_file = is_file
 178         self._children = []
 179
 180     def add_child(self, child):
 181         """Add a child node."""
 182         self._children.append(child)
 183
 184     def clear_children(self):
 185         """Remove all children from the node."""
 186         self._children = []
 187
 188     def is_file_node(self):
 189         """Return True if the node was created with is_file=True."""
 190         return self._is_file
 191
 192     def get_nodename(self):
 193         """Get internal name of the node in 'dot'."""
 194         return self._nodename
 195
 196     def get_children(self, recursive=False):
 197         """Get list of child nodes."""
 198         if recursive:
 199             result = list(self._children)
 200             for child in self._children:
 201                 result.extend(child.get_children(recursive=True))
 202             return result
 203         else:
 204             return self._children
 205
 206     def format(self):
 207         """Format this node for 'dot'."""
 208         # TODO: Take indent as a parameter to make output marginally nicer.
 209         result = ''
 210         if self._children:
 211             result += '    subgraph cluster_{0} {{\n' \
 212                           .format(self._nodename)
 213             result += '        label = "{0}"\n'.format(self._label)
 214             for child in self._children:
 215                 result += child.format()
 216             result += '    }\n'
 217         else:
 218             properties = 'label="{0}"'.format(self._label)
 219             if self._properties:
 220                 properties += ', ' + self._properties
 221             if self._style:
 222                 properties += ', style="{0}"'.format(self._style)
 223             result += '    {0} [{1}]\n'.format(self._nodename, properties)
 224         return result
 225
 226
 227 class Graph(object):
 228
 229     """Graph for 'dot'."""
 230
 231     def __init__(self, nodes, edges):
 232         """Create graph with given nodes and edges."""
 233         self._nodes = set(nodes)
 234         self._edges = edges
 235         self._left_to_right = False
 236         self._concentrate = True
 237
 238     def set_options(self, left_to_right=None, concentrate=None):
 239         """Set output options for the graph."""
 240         if left_to_right != None:
 241             self._left_to_right = left_to_right
 242         if concentrate != None:
 243             self._concentrate = concentrate
 244
 245     def merge_nodes(self, nodes, target):
 246         """Merge a set of nodes into a single node.
 247
 248         All nodes from the list nodes are merged into the target node.
 249         All edges to or from the merged nodes are rerouted to/from target
 250         instead.  Duplicate edges are not created.  Instead, if an edge already
 251         exists, the edge types are merged.  All nodes from the list nodes are
 252         removed from the graph after the merge is done.
 253         """
 254         nodes = set(nodes)
 255         nodes.add(target)
 256         newedges = []
 257         edgesto = dict()
 258         edgesfrom = dict()
 259         for edge in self._edges:
 260             isfrom = (edge._fromnode in nodes)
 261             isto = (edge._tonode in nodes)
 262             if isfrom and isto:
 263                 pass
 264             elif isfrom:
 265                 if not edge._tonode in edgesfrom:
 266                     edgesfrom[edge._tonode] = \
 267                             Edge(target, edge._tonode, edge._edgetype)
 268                 else:
 269                     edgesfrom[edge._tonode].merge_edge(edge)
 270             elif isto:
 271                 if not edge._fromnode in edgesto:
 272                     edgesto[edge._fromnode] = \
 273                             Edge(edge._fromnode, target, edge._edgetype)
 274                 else:
 275                     edgesto[edge._fromnode].merge_edge(edge)
 276             else:
 277                 newedges.append(edge)
 278         newedges.extend(edgesfrom.values())
 279         newedges.extend(edgesto.values())
 280         self._edges = newedges
 281
 282     def collapse_node(self, node):
 283         """Merge all children of a node into the node.
 284
 285         All child nodes are removed after the merge is done.
 286         """
 287         nodes = node.get_children(recursive=True)
 288         self.merge_nodes(nodes, node)
 289         node.clear_children()
 290
 291     def write(self, outfile):
 292         """Write the graph in 'dot' format."""
 293         outfile.write('digraph includedeps {\n')
 294         if self._left_to_right:
 295             outfile.write('    rankdir = LR\n')
 296         if self._concentrate:
 297             outfile.write('    concentrate = true\n')
 298         outfile.write('    node [fontname="FreeSans",fontsize=10,height=.2,'
 299                                  'shape=box]\n')
 300         for node in self._nodes:
 301             outfile.write(node.format())
 302         for edge in self._edges:
 303             outfile.write('    ' + edge.format() + '\n')
 304         outfile.write('}\n')
 305
 306 class GraphBuilder(object):
 307
 308     """Builder for Graph objects from gmxtree.GromacsTree representation."""
 309
 310     def __init__(self, tree):
 311         """Initialize builder for a given tree representation."""
 312         self._tree = tree
 313
 314     def _create_file_node(self, fileobj, filenodes):
 315         """Create graph node for a file object.
 316
 317         filenodes is a dict() that maps file objects to their nodes, and is
 318         updated by this call.
 319         """
 320         nodename = re.subn(r'[-./]', '_', fileobj.get_relpath())[0]
 321         style = []
 322         properties = []
 323         properties.append('URL="\\ref {0}"'.format(fileobj.get_name()))
 324         if not fileobj.get_module():
 325             style.append('bold')
 326             properties.append('color=red')
 327         if fileobj.is_test_file():
 328             style.append('filled')
 329             properties.append('fillcolor=".33 .2 1"')
 330         elif fileobj.is_source_file():
 331             style.append('filled')
 332             properties.append('fillcolor=grey75')
 333         elif fileobj.get_api_type() == DocType.public:
 334             style.append('filled')
 335             properties.append('fillcolor=".66 .2 1"')
 336         elif fileobj.get_api_type() == DocType.library:
 337             style.append('filled')
 338             properties.append('fillcolor=".66 .5 1"')
 339         node = Node(nodename, fileobj.get_name(), style, properties, is_file=True)
 340         filenodes[fileobj] = node
 341         return node
 342
 343     def _get_file_edge_type(self, fromfile, tofile):
 344         """Get EdgeType for an edge between two file objects.
 345
 346         Determines the type for the edge from the information provided by
 347         gmxtree.
 348         """
 349         intramodule = (fromfile.get_module() == tofile.get_module())
 350         is_legacy = not tofile.api_type_is_reliable()
 351         if fromfile.get_module() == tofile.get_module():
 352             return EdgeType.intramodule
 353         elif tofile.get_api_type() == DocType.internal and not tofile.is_public():
 354             if is_legacy:
 355                 return EdgeType.legacy
 356             else:
 357                 return EdgeType.undocumented
 358         elif fromfile.is_test_file():
 359             return EdgeType.test
 360         elif tofile.is_test_file():
 361             return EdgeType.undocumented
 362         elif fromfile.is_module_internal():
 363             if tofile.is_public():
 364                 return EdgeType.pubimpl
 365             elif tofile.get_api_type() == DocType.library:
 366                 return EdgeType.libimpl
 367             elif is_legacy:
 368                 return EdgeType.legacy
 369             elif not tofile.is_documented():
 370                 return EdgeType.undocumented
 371             else:
 372                 raise ValueError('Unknown edge type between {0} and {1}'
 373                         .format(fromfile.get_relpath(), tofile.get_relpath()))
 374         elif fromfile.get_api_type() == DocType.library:
 375             return EdgeType.library
 376         elif fromfile.is_public() or fromfile.is_installed():
 377             if tofile.is_public() or tofile.is_installed():
 378                 return EdgeType.public
 379             else:
 380                 return EdgeType.undocumented
 381         elif is_legacy:
 382             return EdgeType.legacy
 383         else:
 384             raise ValueError('Unknown edge type between {0} and {1}'
 385                     .format(fromfile.get_relpath(), tofile.get_relpath()))
 386
 387     def _create_file_edge(self, fromfile, tofile, filenodes):
 388         """Create edge between two file objects.
 389
 390         Determines the type for the edge from the information provided by
 391         gmxtree.
 392         """
 393         edgetype = self._get_file_edge_type(fromfile, tofile)
 394         return Edge(filenodes[fromfile], filenodes[tofile], edgetype)
 395
 396     def _create_file_edges(self, filenodes):
 397         """Create edges between all file nodes.
 398
 399         Create edges between file nodes specified in filenodes from all include
 400         dependencies.  An edge is created only if both ends of the dependency
 401         are in the list of nodes.
 402         """
 403         edges = []
 404         for fileobj in filenodes.iterkeys():
 405             for includedfile in fileobj.get_includes():
 406                 otherfile = includedfile.get_file()
 407                 if otherfile and otherfile in filenodes:
 408                     edge = self._create_file_edge(fileobj, otherfile, filenodes)
 409                     edges.append(edge)
 410         return edges
 411
 412     def _get_module_color(self, modulegroup):
 413         # If you change these styles, update also the legend in modulegraph.md
 414         if modulegroup == 'legacy':
 415             return 'fillcolor=grey75'
 416         elif modulegroup == 'analysismodules':
 417             return 'fillcolor="0 .2 1"'
 418         elif modulegroup == 'utilitymodules':
 419             return 'fillcolor=".08 .2 1"'
 420         elif modulegroup == 'mdrun':
 421             return 'fillcolor=".75 .2 1"'
 422         return None
 423
 424     def _create_module_node(self, module):
 425         """Create node for a module."""
 426         style = []
 427         properties = []
 428         properties.append('shape=ellipse')
 429         if module.is_documented():
 430             properties.append('URL="\\ref {0}"'.format(module.get_name()))
 431         if not module.is_documented():
 432             fillcolor = self._get_module_color('legacy')
 433         else:
 434             fillcolor = self._get_module_color(module.get_group())
 435         if fillcolor:
 436             style.append('filled')
 437             properties.append(fillcolor)
 438         rootdir = module.get_root_dir()
 439         if rootdir.has_installed_files():
 440             properties.append('color=".66 .5 1"')
 441             properties.append('penwidth=3')
 442         nodename = 'module_' + re.subn(r'[-./]', '_', rootdir.get_relpath())[0]
 443         label = module.get_name()[7:]
 444         node = Node(nodename, label, style, properties)
 445         return node
 446
 447     def _create_module_edges(self, modulenodes):
 448         """Create edges between all module nodes.
 449
 450         Create edges between module nodes specified in modulenodes from all
 451         include dependencies.  An edge is created only if both ends of the
 452         dependency are in the list of nodes.
 453         """
 454         edges = []
 455         for moduleobj in modulenodes.iterkeys():
 456             for dep in moduleobj.get_dependencies():
 457                 othermodule = dep.get_other_module()
 458                 if othermodule and othermodule in modulenodes:
 459                     if dep.is_cycle_suppressed():
 460                         edgetype = EdgeType.cyclic
 461                     else:
 462                         edgetype = max([
 463                             self._get_file_edge_type(x.get_including_file(), x.get_file())
 464                             for x in dep.get_included_files()])
 465                     edge = Edge(modulenodes[moduleobj], modulenodes[othermodule], edgetype)
 466                     edges.append(edge)
 467         return edges
 468
 469     def create_modules_graph(self):
 470         """Create module dependency graph."""
 471         nodes = []
 472         modulenodes = dict()
 473         libgromacsnode = Node('libgromacs', 'libgromacs')
 474         nodes.append(libgromacsnode)
 475         for moduleobj in self._tree.get_modules():
 476             node = self._create_module_node(moduleobj)
 477             if moduleobj.get_root_dir().get_relpath().startswith('src/gromacs'):
 478                 libgromacsnode.add_child(node)
 479             else:
 480                 nodes.append(node)
 481             modulenodes[moduleobj] = node
 482         edges = self._create_module_edges(modulenodes)
 483         graph = Graph(nodes, edges)
 484         graph.set_options(concentrate=False)
 485         return graph
 486
 487     def create_module_file_graph(self, module):
 488         """Create file dependency graph for files within a module."""
 489         filenodes = dict()
 490         nodes = []
 491         for fileobj in module.get_files():
 492             nodes.append(self._create_file_node(fileobj, filenodes))
 493         edges = self._create_file_edges(filenodes)
 494         graph = Graph(nodes, edges)
 495         graph.set_options(left_to_right=True)
 496         return graph
 497
 498 def main():
 499     """Run the graph generation script."""
 500     import os
 501     import sys
 502
 503     from optparse import OptionParser
 504
 505     from gmxtree import GromacsTree
 506     from reporter import Reporter
 507
 508     parser = OptionParser()
 509     parser.add_option('-S', '--source-root',
 510                       help='Source tree root directory')
 511     parser.add_option('-B', '--build-root',
 512                       help='Build tree root directory')
 513     parser.add_option('--ignore-cycles',
 514                       help='Set file with module dependencies to ignore in cycles')
 515     parser.add_option('-o', '--outdir', default='.',
 516                       help='Specify output directory for graphs')
 517     parser.add_option('-q', '--quiet', action='store_true',
 518                       help='Do not write status messages')
 519     options, args = parser.parse_args()
 520
 521     reporter = Reporter(quiet=True)
 522
 523     if not options.quiet:
 524         sys.stderr.write('Scanning source tree...\n')
 525     tree = GromacsTree(options.source_root, options.build_root, reporter)
 526     tree.load_installed_file_list()
 527     if not options.quiet:
 528         sys.stderr.write('Reading source files...\n')
 529     tree.scan_files()
 530     if options.ignore_cycles:
 531         tree.load_cycle_suppression_list(options.ignore_cycles)
 532     if not options.quiet:
 533         sys.stderr.write('Reading Doxygen XML files...\n')
 534     tree.load_xml(only_files=True)
 535
 536     if not options.quiet:
 537         sys.stderr.write('Writing graphs...\n')
 538     graphbuilder = GraphBuilder(tree)
 539     if not os.path.exists(options.outdir):
 540         os.mkdir(options.outdir)
 541
 542     filename = os.path.join(options.outdir, 'module-deps.dot')
 543     graph = graphbuilder.create_modules_graph()
 544     with open(filename, 'w') as outfile:
 545         graph.write(outfile)
 546
 547     # Skip some modules that are too big to make any sense
 548     skippedmodules = ('legacyheaders', 'gmxlib', 'mdlib', 'gmxana', 'gmxpreprocess')
 549     for module in tree.get_modules():
 550         if not module.get_name()[7:] in skippedmodules:
 551             filename = '{0}-deps.dot'.format(module.get_name())
 552             filename = os.path.join(options.outdir, filename)
 553             graph = graphbuilder.create_module_file_graph(module)
 554             with open(filename, 'w') as outfile:
 555                 graph.write(outfile)
 556
 557 if __name__ == '__main__':
 558     main()