1  #!/usr/bin/env python3
 2  # Copyright (c) 2018-present The Bitcoin Core developers
 3  # Distributed under the MIT software license, see the accompanying
 4  # file COPYING or http://www.opensource.org/licenses/mit-license.php.
 5  
 6  import sys
 7  import re
 8  
 9  # Directories with header-based modules, where the assumption that .cpp files
10  # define functions and variables declared in corresponding .h files is
11  # incorrect.
12  HEADER_MODULE_PATHS = [
13      'interfaces/'
14  ]
15  
16  def module_name(path):
17      if any(path.startswith(dirpath) for dirpath in HEADER_MODULE_PATHS):
18          return path
19      if path.endswith(".h"):
20          return path[:-2]
21      if path.endswith(".c"):
22          return path[:-2]
23      if path.endswith(".cpp"):
24          return path[:-4]
25      return None
26  
27  files = dict()
28  deps: dict[str, set[str]] = dict()
29  
30  RE = re.compile("^#include <(.*)>")
31  
32  # Iterate over files, and create list of modules
33  for arg in sys.argv[1:]:
34      module = module_name(arg)
35      if module is None:
36          print("Ignoring file %s (does not constitute module)\n" % arg)
37      else:
38          files[arg] = module
39          deps[module] = set()
40  
41  # Iterate again, and build list of direct dependencies for each module
42  # TODO: implement support for multiple include directories
43  for arg in sorted(files.keys()):
44      module = files[arg]
45      with open(arg, 'r') as f:
46          for line in f:
47              match = RE.match(line)
48              if match:
49                  include = match.group(1)
50                  included_module = module_name(include)
51                  if included_module is not None and included_module in deps and included_module != module:
52                      deps[module].add(included_module)
53  
54  # Loop to find the shortest (remaining) circular dependency
55  have_cycle: bool = False
56  while True:
57      shortest_cycle = None
58      for module in sorted(deps.keys()):
59          # Build the transitive closure of dependencies of module
60          closure: dict[str, list[str]] = dict()
61          for dep in deps[module]:
62              closure[dep] = []
63          while True:
64              old_size = len(closure)
65              old_closure_keys = sorted(closure.keys())
66              for src in old_closure_keys:
67                  for dep in deps[src]:
68                      if dep not in closure:
69                          closure[dep] = closure[src] + [src]
70              if len(closure) == old_size:
71                  break
72          # If module is in its own transitive closure, it's a circular dependency; check if it is the shortest
73          if module in closure and (shortest_cycle is None or len(closure[module]) + 1 < len(shortest_cycle)):
74              shortest_cycle = [module] + closure[module]
75      if shortest_cycle is None:
76          break
77      # We have the shortest circular dependency; report it
78      module = shortest_cycle[0]
79      print("Circular dependency: %s" % (" -> ".join(shortest_cycle + [module])))
80      # And then break the dependency to avoid repeating in other cycles
81      deps[shortest_cycle[-1]] = deps[shortest_cycle[-1]] - set([module])
82      have_cycle = True
83  
84  sys.exit(1 if have_cycle else 0)