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