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)
85