cmake/Modules/geant4_check_module_cycles.py

0001 #!/usr/bin/env python3
0002
0003 """Check Geant4's module dependency graph for cycles
0004
0005 Geant4 organises source code into "Modules", with each Module being a
0006 directory containing headers and sources in `include/` and `src/`
0007 subdirectories respectively. One or more Modules are grouped/compiled
0008 into the actual libraries.
0009
0010 CMake will raise errors if there are circular dependencies between
0011 shared libraries (cycles are allowed between static libraries). However,
0012 CMake cannot detect cycles between Modules directly, are these are a
0013 Geant4 construct. Whilst cycles between modules that get added to the
0014 same library are technically o.k., they still indicate either:
0015
0016 - A bad design/organisation of code
0017 - A mistake in the declared dependencies for a module(s)
0018
0019 To help developers and CI pick module cycles, Geant4's CMake scripts
0020 write out the declared module dependencies in a text file as an Adjacency
0021 List graph. This comprises one line per module, with the first column
0022 being the module name, and any remaining columns being the modules the
0023 first one "depends on", i.e. uses code from.
0024
0025 This program reads that file and uses Python's graphlib module to try
0026 topologically sorting this graph. Failure to sort indicates a cycle, and
0027 this will be printed to stdout and a non-zero return code emitted on exit.
0028 """
0029
0030 import argparse
0031 import graphlib
0032 import sys
0033
0034 if __name__ == "__main__":
0035     # Parse command line to get file to load
0036     parser = argparse.ArgumentParser(
0037         description=str(__doc__), formatter_class=argparse.RawDescriptionHelpFormatter
0038     )
0039     parser.add_argument(
0040         "-f",
0041         "--file",
0042         required=True,
0043         metavar="FILE",
0044         help="file to read adjacency list from",
0045     )
0046     parser.add_argument(
0047         "-v",
0048         "--verbose",
0049         action="store_true",
0050         help="print topologically sorted list of modules",
0051     )
0052     args = parser.parse_args()
0053
0054     try:
0055         # 1. Try and construct graph from input adjancey list file
0056         adjList = {}
0057         with open(args.file) as f:
0058             for line in f:
0059                 if not line.strip().startswith("#"):
0060                     nodes = line.rstrip("\n").split(" ")
0061                     adjList[nodes[0]] = nodes[1:]
0062
0063         if not adjList:
0064             print(f"warning: graph read from '{args.file}' is empty")
0065
0066         # NB also possible with networkx, but requires pip install:
0067         # G = nx.read_adjlist(args.file, create_using=nx.DiGraph)
0068         # cycles = nx.find_cycle(G, orientation='original')
0069
0070         # Topo sort throws cycle error if one occurs during prepare
0071         ts = graphlib.TopologicalSorter(adjList)
0072         ts.prepare()
0073
0074         # Verbose print of nodes in topological order
0075         # NB: This uses the full graphlib interface in case we want to
0076         # print out nodes grouped by level in the graph.
0077         if args.verbose:
0078             while ts.is_active():
0079                 nodes = ts.get_ready()
0080                 for n in nodes:
0081                     print(n)
0082                 ts.done(*nodes)
0083
0084         print(f"pass: No cycles detected in graph defined in '{args.file}'")
0085
0086     except OSError as err:
0087         print(f"OS error: {err}")
0088         sys.exit(1)
0089     except graphlib.CycleError as err:
0090         print(
0091             f"error: cycles detected in input graph from '{args.file}':",
0092             file=sys.stderr,
0093         )
0094         cycle = " <- ".join(err.args[1])
0095         print(f"cycle: {cycle}", file=sys.stderr)
0096         sys.exit(1)