Changeset View
Changeset View
Standalone View
Standalone View
contrib/devtools/circular-dependencies.py
| #!/usr/bin/env python3 | #!/usr/bin/env python3 | ||||
| # Copyright (c) 2018-2020 The Bitcoin developers | # Copyright (c) 2018-2020 The Bitcoin developers | ||||
| # Distributed under the MIT software license, see the accompanying | # Distributed under the MIT software license, see the accompanying | ||||
| # file COPYING or http://www.opensource.org/licenses/mit-license.php. | # file COPYING or http://www.opensource.org/licenses/mit-license.php. | ||||
| import re | import re | ||||
| import sys | import sys | ||||
| from typing import Dict, List, Set | from typing import Dict, List, Set | ||||
| MAPPING = { | MAPPING = { | ||||
| 'core_read.cpp': 'core_io.cpp', | "core_read.cpp": "core_io.cpp", | ||||
| 'core_write.cpp': 'core_io.cpp', | "core_write.cpp": "core_io.cpp", | ||||
| } | } | ||||
| # Directories with header-based modules, where the assumption that .cpp files | # Directories with header-based modules, where the assumption that .cpp files | ||||
| # define functions and variables declared in corresponding .h files is | # define functions and variables declared in corresponding .h files is | ||||
| # incorrect. | # incorrect. | ||||
| HEADER_MODULE_PATHS = [ | HEADER_MODULE_PATHS = ["interfaces/"] | ||||
| 'interfaces/' | |||||
| ] | |||||
| def module_name(path): | def module_name(path): | ||||
| if path in MAPPING: | if path in MAPPING: | ||||
| path = MAPPING[path] | path = MAPPING[path] | ||||
| if any(path.startswith(dirpath) for dirpath in HEADER_MODULE_PATHS): | if any(path.startswith(dirpath) for dirpath in HEADER_MODULE_PATHS): | ||||
| return path | return path | ||||
| if path.endswith(".h"): | if path.endswith(".h"): | ||||
| Show All 18 Lines | for arg in sys.argv[1:]: | ||||
| else: | else: | ||||
| files[arg] = module | files[arg] = module | ||||
| deps[module] = set() | deps[module] = set() | ||||
| # Iterate again, and build list of direct dependencies for each module | # Iterate again, and build list of direct dependencies for each module | ||||
| # TODO: implement support for multiple include directories | # TODO: implement support for multiple include directories | ||||
| for arg in sorted(files.keys()): | for arg in sorted(files.keys()): | ||||
| module = files[arg] | module = files[arg] | ||||
| with open(arg, 'r', encoding="utf8") as f: | with open(arg, "r", encoding="utf8") as f: | ||||
| for line in f: | for line in f: | ||||
| match = RE.match(line) | match = RE.match(line) | ||||
| if match: | if match: | ||||
| include = match.group(1) | include = match.group(1) | ||||
| included_module = module_name(include) | included_module = module_name(include) | ||||
| if included_module is not None and included_module in deps and included_module != module: | if ( | ||||
| included_module is not None | |||||
| and included_module in deps | |||||
| and included_module != module | |||||
| ): | |||||
| deps[module].add(included_module) | deps[module].add(included_module) | ||||
| # Loop to find the shortest (remaining) circular dependency | # Loop to find the shortest (remaining) circular dependency | ||||
| have_cycle = False | have_cycle = False | ||||
| while True: | while True: | ||||
| shortest_cycle = None | shortest_cycle = None | ||||
| for module in sorted(deps.keys()): | for module in sorted(deps.keys()): | ||||
| # Build the transitive closure of dependencies of module | # Build the transitive closure of dependencies of module | ||||
| closure: Dict[str, List[str]] = {dep: [] for dep in deps[module]} | closure: Dict[str, List[str]] = {dep: [] for dep in deps[module]} | ||||
| while True: | while True: | ||||
| old_size = len(closure) | old_size = len(closure) | ||||
| old_closure_keys = sorted(closure.keys()) | old_closure_keys = sorted(closure.keys()) | ||||
| for src in old_closure_keys: | for src in old_closure_keys: | ||||
| for dep in deps[src]: | for dep in deps[src]: | ||||
| if dep not in closure: | if dep not in closure: | ||||
| closure[dep] = closure[src] + [src] | closure[dep] = closure[src] + [src] | ||||
| if len(closure) == old_size: | if len(closure) == old_size: | ||||
| break | break | ||||
| # If module is in its own transitive closure, it's a circular | # If module is in its own transitive closure, it's a circular | ||||
| # dependency; check if it is the shortest | # dependency; check if it is the shortest | ||||
| if module in closure and (shortest_cycle is None or len( | if module in closure and ( | ||||
| closure[module]) + 1 < len(shortest_cycle)): | shortest_cycle is None or len(closure[module]) + 1 < len(shortest_cycle) | ||||
| ): | |||||
| shortest_cycle = [module] + closure[module] | shortest_cycle = [module] + closure[module] | ||||
| if shortest_cycle is None: | if shortest_cycle is None: | ||||
| break | break | ||||
| # We have the shortest circular dependency; report it | # We have the shortest circular dependency; report it | ||||
| module = shortest_cycle[0] | module = shortest_cycle[0] | ||||
| print(f"Circular dependency: {' -> '.join(shortest_cycle + [module])}") | print(f"Circular dependency: {' -> '.join(shortest_cycle + [module])}") | ||||
| # And then break the dependency to avoid repeating in other cycles | # And then break the dependency to avoid repeating in other cycles | ||||
| deps[shortest_cycle[-1]] = deps[shortest_cycle[-1]] - {module} | deps[shortest_cycle[-1]] = deps[shortest_cycle[-1]] - {module} | ||||
| have_cycle = True | have_cycle = True | ||||
| sys.exit(1 if have_cycle else 0) | sys.exit(1 if have_cycle else 0) | ||||