1import argparse
2import itertools
3import os
4import re
5import sys
6from collections import defaultdict
7
8from use_lldb_suite import lldb_root
9
10parser = argparse.ArgumentParser(
11    description='Analyze LLDB project #include dependencies.')
12parser.add_argument('--show-counts', default=False, action='store_true',
13    help='When true, show the number of dependencies from each subproject')
14parser.add_argument('--discover-cycles', default=False, action='store_true',
15    help='When true, find and display all project dependency cycles.  Note,'
16         'this option is very slow')
17
18args = parser.parse_args()
19
20src_dir = os.path.join(lldb_root, "source")
21inc_dir = os.path.join(lldb_root, "include")
22
23src_map = {}
24
25include_regex = re.compile('#include \"((lldb|Plugins|clang)(.*/)+).*\"')
26
27def is_sublist(small, big):
28    it = iter(big)
29    return all(c in it for c in small)
30
31def normalize_host(str):
32    if str.startswith("lldb/Host"):
33        return "lldb/Host"
34    if str.startswith("Plugins"):
35        return "lldb/" + str
36    if str.startswith("lldb/../../source"):
37        return str.replace("lldb/../../source", "lldb")
38    return str
39
40def scan_deps(this_dir, file):
41    global src_map
42    deps = {}
43    this_dir = normalize_host(this_dir)
44    if this_dir in src_map:
45        deps = src_map[this_dir]
46
47    with open(file) as f:
48        for line in list(f):
49            m = include_regex.match(line)
50            if m is None:
51                continue
52            relative = m.groups()[0].rstrip("/")
53            if relative == this_dir:
54                continue
55            relative = normalize_host(relative)
56            if relative in deps:
57                deps[relative] += 1
58            elif relative != this_dir:
59                deps[relative] = 1
60    if this_dir not in src_map and len(deps) > 0:
61        src_map[this_dir] = deps
62
63for (base, dirs, files) in os.walk(inc_dir):
64    dir = os.path.basename(base)
65    relative = os.path.relpath(base, inc_dir)
66    inc_files = filter(lambda x : os.path.splitext(x)[1] in [".h"], files)
67    relative = relative.replace("\\", "/")
68    for inc in inc_files:
69        inc_path = os.path.join(base, inc)
70        scan_deps(relative, inc_path)
71
72for (base, dirs, files) in os.walk(src_dir):
73    dir = os.path.basename(base)
74    relative = os.path.relpath(base, src_dir)
75    src_files = filter(lambda x : os.path.splitext(x)[1] in [".cpp", ".h", ".mm"], files)
76    norm_base_path = os.path.normpath(os.path.join("lldb", relative))
77    norm_base_path = norm_base_path.replace("\\", "/")
78    for src in src_files:
79        src_path = os.path.join(base, src)
80        scan_deps(norm_base_path, src_path)
81    pass
82
83def is_existing_cycle(path, cycles):
84    # If we have a cycle like # A -> B -> C (with an implicit -> A at the end)
85    # then we don't just want to check for an occurrence of A -> B -> C in the
86    # list of known cycles, but every possible rotation of A -> B -> C.  For
87    # example, if we previously encountered B -> C -> A (with an implicit -> B
88    # at the end), then A -> B -> C is also a cycle.  This is an important
89    # optimization which reduces the search space by multiple orders of
90    # magnitude.
91    for i in xrange(0,len(path)):
92        if any(is_sublist(x, path) for x in cycles):
93            return True
94        path = [path[-1]] + path[0:-1]
95    return False
96
97def expand(path_queue, path_lengths, cycles, src_map):
98    # We do a breadth first search, to make sure we visit all paths in order
99    # of ascending length.  This is an important optimization to make sure that
100    # short cycles are discovered first, which will allow us to discard longer
101    # cycles which grow the search space exponentially the longer they get.
102    while len(path_queue) > 0:
103        cur_path = path_queue.pop(0)
104        if is_existing_cycle(cur_path, cycles):
105            continue
106
107        next_len = path_lengths.pop(0) + 1
108        last_component = cur_path[-1]
109
110        for item in src_map[last_component]:
111            if item.startswith("clang"):
112                continue
113
114            if item in cur_path:
115                # This is a cycle.  Minimize it and then check if the result is
116                # already in the list of cycles.  Insert it (or not) and then
117                # exit.
118                new_index = cur_path.index(item)
119                cycle = cur_path[new_index:]
120                if not is_existing_cycle(cycle, cycles):
121                    cycles.append(cycle)
122                continue
123
124            path_lengths.append(next_len)
125            path_queue.append(cur_path + [item])
126    pass
127
128cycles = []
129
130path_queue = [[x] for x in src_map.iterkeys()]
131path_lens = [1] * len(path_queue)
132
133items = list(src_map.iteritems())
134items.sort(lambda A, B : cmp(A[0], B[0]))
135
136for (path, deps) in items:
137    print path + ":"
138    sorted_deps = list(deps.iteritems())
139    if args.show_counts:
140        sorted_deps.sort(lambda A, B: cmp(A[1], B[1]))
141        for dep in sorted_deps:
142            print "\t{} [{}]".format(dep[0], dep[1])
143    else:
144        sorted_deps.sort(lambda A, B: cmp(A[0], B[0]))
145        for dep in sorted_deps:
146            print "\t{}".format(dep[0])
147
148def iter_cycles(cycles):
149    global src_map
150    for cycle in cycles:
151        cycle.append(cycle[0])
152        zipper = list(zip(cycle[0:-1], cycle[1:]))
153        result = [(x, src_map[x][y], y) for (x,y) in zipper]
154        total = 0
155        smallest = result[0][1]
156        for (first, value, last) in result:
157            total += value
158            smallest = min(smallest, value)
159        yield (total, smallest, result)
160
161if args.discover_cycles:
162    print "Analyzing cycles..."
163
164    expand(path_queue, path_lens, cycles, src_map)
165
166    average = sum([len(x)+1 for x in cycles]) / len(cycles)
167
168    print "Found {} cycles.  Average cycle length = {}.".format(len(cycles), average)
169    counted = list(iter_cycles(cycles))
170    if args.show_counts:
171        counted.sort(lambda A, B: cmp(A[0], B[0]))
172        for (total, smallest, cycle) in counted:
173            sys.stdout.write("{} deps to break: ".format(total))
174            sys.stdout.write(cycle[0][0])
175            for (first, count, last) in cycle:
176                sys.stdout.write(" [{}->] {}".format(count, last))
177            sys.stdout.write("\n")
178    else:
179        for cycle in cycles:
180            cycle.append(cycle[0])
181            print " -> ".join(cycle)
182
183    print "Analyzing islands..."
184    islands = []
185    outgoing_counts = defaultdict(int)
186    incoming_counts = defaultdict(int)
187    for (total, smallest, cycle) in counted:
188        for (first, count, last) in cycle:
189            outgoing_counts[first] += count
190            incoming_counts[last] += count
191    for cycle in cycles:
192        this_cycle = set(cycle)
193        disjoints = [x for x in islands if this_cycle.isdisjoint(x)]
194        overlaps = [x for x in islands if not this_cycle.isdisjoint(x)]
195        islands = disjoints + [set.union(this_cycle, *overlaps)]
196    print "Found {} disjoint cycle islands...".format(len(islands))
197    for island in islands:
198        print "Island ({} elements)".format(len(island))
199        sorted = []
200        for node in island:
201            sorted.append((node, incoming_counts[node], outgoing_counts[node]))
202        sorted.sort(lambda x, y: cmp(x[1]+x[2], y[1]+y[2]))
203        for (node, inc, outg) in sorted:
204            print "  {} [{} in, {} out]".format(node, inc, outg)
205    sys.stdout.flush()
206pass