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