Inside Bitcoin

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
6import sys
7import 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.
12HEADER_MODULE_PATHS = [
13    'interfaces/'
14]
15
16def 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
27files = dict()
28deps: dict[str, set[str]] = dict()
29
30RE = re.compile("^#include <(.*)>")
31
32# Iterate over files, and create list of modules
33for 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
43for 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
55have_cycle: bool = False
56while 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
84sys.exit(1 if have_cycle else 0)
85