diff options
Diffstat (limited to 'scripts/analyze-project-deps.py')
| -rw-r--r-- | scripts/analyze-project-deps.py | 208 |
1 files changed, 0 insertions, 208 deletions
diff --git a/scripts/analyze-project-deps.py b/scripts/analyze-project-deps.py deleted file mode 100644 index b7f6e6803d02..000000000000 --- a/scripts/analyze-project-deps.py +++ /dev/null @@ -1,208 +0,0 @@ -#! /usr/bin/env python - -import argparse -import itertools -import os -import re -import sys -from collections import defaultdict - -from use_lldb_suite import lldb_root - -parser = argparse.ArgumentParser( - description='Analyze LLDB project #include dependencies.') -parser.add_argument('--show-counts', default=False, action='store_true', - help='When true, show the number of dependencies from each subproject') -parser.add_argument('--discover-cycles', default=False, action='store_true', - help='When true, find and display all project dependency cycles. Note,' - 'this option is very slow') - -args = parser.parse_args() - -src_dir = os.path.join(lldb_root, "source") -inc_dir = os.path.join(lldb_root, "include") - -src_map = {} - -include_regex = re.compile('#include \"((lldb|Plugins|clang)(.*/)+).*\"') - -def is_sublist(small, big): - it = iter(big) - return all(c in it for c in small) - -def normalize_host(str): - if str.startswith("lldb/Host"): - return "lldb/Host" - if str.startswith("Plugins"): - return "lldb/" + str - if str.startswith("lldb/../../source"): - return str.replace("lldb/../../source", "lldb") - return str - -def scan_deps(this_dir, file): - global src_map - deps = {} - this_dir = normalize_host(this_dir) - if this_dir in src_map: - deps = src_map[this_dir] - - with open(file) as f: - for line in list(f): - m = include_regex.match(line) - if m is None: - continue - relative = m.groups()[0].rstrip("/") - if relative == this_dir: - continue - relative = normalize_host(relative) - if relative in deps: - deps[relative] += 1 - elif relative != this_dir: - deps[relative] = 1 - if this_dir not in src_map and len(deps) > 0: - src_map[this_dir] = deps - -for (base, dirs, files) in os.walk(inc_dir): - dir = os.path.basename(base) - relative = os.path.relpath(base, inc_dir) - inc_files = filter(lambda x : os.path.splitext(x)[1] in [".h"], files) - relative = relative.replace("\\", "/") - for inc in inc_files: - inc_path = os.path.join(base, inc) - scan_deps(relative, inc_path) - -for (base, dirs, files) in os.walk(src_dir): - dir = os.path.basename(base) - relative = os.path.relpath(base, src_dir) - src_files = filter(lambda x : os.path.splitext(x)[1] in [".cpp", ".h", ".mm"], files) - norm_base_path = os.path.normpath(os.path.join("lldb", relative)) - norm_base_path = norm_base_path.replace("\\", "/") - for src in src_files: - src_path = os.path.join(base, src) - scan_deps(norm_base_path, src_path) - pass - -def is_existing_cycle(path, cycles): - # If we have a cycle like # A -> B -> C (with an implicit -> A at the end) - # then we don't just want to check for an occurrence of A -> B -> C in the - # list of known cycles, but every possible rotation of A -> B -> C. For - # example, if we previously encountered B -> C -> A (with an implicit -> B - # at the end), then A -> B -> C is also a cycle. This is an important - # optimization which reduces the search space by multiple orders of - # magnitude. - for i in range(0,len(path)): - if any(is_sublist(x, path) for x in cycles): - return True - path = [path[-1]] + path[0:-1] - return False - -def expand(path_queue, path_lengths, cycles, src_map): - # We do a breadth first search, to make sure we visit all paths in order - # of ascending length. This is an important optimization to make sure that - # short cycles are discovered first, which will allow us to discard longer - # cycles which grow the search space exponentially the longer they get. - while len(path_queue) > 0: - cur_path = path_queue.pop(0) - if is_existing_cycle(cur_path, cycles): - continue - - next_len = path_lengths.pop(0) + 1 - last_component = cur_path[-1] - - for item in src_map[last_component]: - if item.startswith("clang"): - continue - - if item in cur_path: - # This is a cycle. Minimize it and then check if the result is - # already in the list of cycles. Insert it (or not) and then - # exit. - new_index = cur_path.index(item) - cycle = cur_path[new_index:] - if not is_existing_cycle(cycle, cycles): - cycles.append(cycle) - continue - - path_lengths.append(next_len) - path_queue.append(cur_path + [item]) - pass - -cycles = [] - -path_queue = [[x] for x in iter(src_map)] -path_lens = [1] * len(path_queue) - -items = list(src_map.items()) -items.sort(key = lambda A : A[0]) - -for (path, deps) in items: - print(path + ":") - sorted_deps = list(deps.items()) - if args.show_counts: - sorted_deps.sort(key = lambda A: (A[1], A[0])) - for dep in sorted_deps: - print("\t{} [{}]".format(dep[0], dep[1])) - else: - sorted_deps.sort(key = lambda A: A[0]) - for dep in sorted_deps: - print("\t{}".format(dep[0])) - -def iter_cycles(cycles): - global src_map - for cycle in cycles: - cycle.append(cycle[0]) - zipper = list(zip(cycle[0:-1], cycle[1:])) - result = [(x, src_map[x][y], y) for (x,y) in zipper] - total = 0 - smallest = result[0][1] - for (first, value, last) in result: - total += value - smallest = min(smallest, value) - yield (total, smallest, result) - -if args.discover_cycles: - print("Analyzing cycles...") - - expand(path_queue, path_lens, cycles, src_map) - - average = sum([len(x)+1 for x in cycles]) / len(cycles) - - print("Found {} cycles. Average cycle length = {}.".format(len(cycles), average)) - counted = list(iter_cycles(cycles)) - if args.show_counts: - counted.sort(key = lambda A: A[0]) - for (total, smallest, cycle) in counted: - sys.stdout.write("{} deps to break: ".format(total)) - sys.stdout.write(cycle[0][0]) - for (first, count, last) in cycle: - sys.stdout.write(" [{}->] {}".format(count, last)) - sys.stdout.write("\n") - else: - for cycle in cycles: - cycle.append(cycle[0]) - print(" -> ".join(cycle)) - - print("Analyzing islands...") - islands = [] - outgoing_counts = defaultdict(int) - incoming_counts = defaultdict(int) - for (total, smallest, cycle) in counted: - for (first, count, last) in cycle: - outgoing_counts[first] += count - incoming_counts[last] += count - for cycle in cycles: - this_cycle = set(cycle) - disjoints = [x for x in islands if this_cycle.isdisjoint(x)] - overlaps = [x for x in islands if not this_cycle.isdisjoint(x)] - islands = disjoints + [set.union(this_cycle, *overlaps)] - print("Found {} disjoint cycle islands...".format(len(islands))) - for island in islands: - print("Island ({} elements)".format(len(island))) - sorted = [] - for node in island: - sorted.append((node, incoming_counts[node], outgoing_counts[node])) - sorted.sort(key = lambda x: x[1]+x[2]) - for (node, inc, outg) in sorted: - print(" {} [{} in, {} out]".format(node, inc, outg)) - sys.stdout.flush() -pass |