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