1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
#!/usr/bin/env python
#===----------------------------------------------------------------------===##
#
# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
# See https://llvm.org/LICENSE.txt for license information.
# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#
#===----------------------------------------------------------------------===##
from argparse import ArgumentParser
import os
import shutil
import sys
import shlex
import json
import re
import libcxx.graph as dot
import libcxx.util
def print_and_exit(msg):
sys.stderr.write(msg + '\n')
sys.exit(1)
def libcxx_include_path():
curr_dir = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
include_dir = os.path.join(curr_dir, 'include')
return include_dir
def get_libcxx_headers():
headers = []
include_dir = libcxx_include_path()
for fname in os.listdir(include_dir):
f = os.path.join(include_dir, fname)
if not os.path.isfile(f):
continue
base, ext = os.path.splitext(fname)
if (ext == '' or ext == '.h') and (not fname.startswith('__') or fname == '__config'):
headers += [f]
return headers
def rename_headers_and_remove_test_root(graph):
inc_root = libcxx_include_path()
to_remove = set()
for n in graph.nodes:
assert 'label' in n.attributes
l = n.attributes['label']
if not l.startswith('/') and os.path.exists(os.path.join('/', l)):
l = '/' + l
if l.endswith('.tmp.cpp'):
to_remove.add(n)
if l.startswith(inc_root):
l = l[len(inc_root):]
if l.startswith('/'):
l = l[1:]
n.attributes['label'] = l
for n in to_remove:
graph.removeNode(n)
def remove_non_std_headers(graph):
inc_root = libcxx_include_path()
to_remove = set()
for n in graph.nodes:
test_file = os.path.join(inc_root, n.attributes['label'])
if not test_file.startswith(inc_root):
to_remove.add(n)
for xn in to_remove:
graph.removeNode(xn)
class DependencyCommand(object):
def __init__(self, compile_commands, output_dir, new_std=None):
output_dir = os.path.abspath(output_dir)
if not os.path.isdir(output_dir):
print_and_exit('"%s" must point to a directory' % output_dir)
self.output_dir = output_dir
self.new_std = new_std
cwd,bcmd = self._get_base_command(compile_commands)
self.cwd = cwd
self.base_cmd = bcmd
def run_for_headers(self, header_list):
outputs = []
for header in header_list:
header_name = os.path.basename(header)
out = os.path.join(self.output_dir, ('%s.dot' % header_name))
outputs += [out]
cmd = self.base_cmd + ["-fsyntax-only", "-Xclang", "-dependency-dot", "-Xclang", "%s" % out, '-xc++', '-']
libcxx.util.executeCommandOrDie(cmd, cwd=self.cwd, input='#include <%s>\n\n' % header_name)
return outputs
def _get_base_command(self, command_file):
commands = None
with open(command_file, 'r') as f:
commands = json.load(f)
for compile_cmd in commands:
file = compile_cmd['file']
if not file.endswith('src/algorithm.cpp'):
continue
wd = compile_cmd['directory']
cmd_str = compile_cmd['command']
cmd = shlex.split(cmd_str)
out_arg = cmd.index('-o')
del cmd[out_arg]
del cmd[out_arg]
in_arg = cmd.index('-c')
del cmd[in_arg]
del cmd[in_arg]
if self.new_std is not None:
for f in cmd:
if f.startswith('-std='):
del cmd[cmd.index(f)]
cmd += [self.new_std]
break
return wd, cmd
print_and_exit("failed to find command to build algorithm.cpp")
def post_process_outputs(outputs, libcxx_only):
graphs = []
for dot_file in outputs:
g = dot.DirectedGraph.fromDotFile(dot_file)
rename_headers_and_remove_test_root(g)
if libcxx_only:
remove_non_std_headers(g)
graphs += [g]
g.toDotFile(dot_file)
return graphs
def build_canonical_names(graphs):
canonical_names = {}
next_idx = 0
for g in graphs:
for n in g.nodes:
if n.attributes['label'] not in canonical_names:
name = 'header_%d' % next_idx
next_idx += 1
canonical_names[n.attributes['label']] = name
return canonical_names
class CanonicalGraphBuilder(object):
def __init__(self, graphs):
self.graphs = list(graphs)
self.canonical_names = build_canonical_names(graphs)
def build(self):
self.canonical = dot.DirectedGraph('all_headers')
for k,v in self.canonical_names.iteritems():
n = dot.Node(v, edges=[], attributes={'shape': 'box', 'label': k})
self.canonical.addNode(n)
for g in self.graphs:
self._merge_graph(g)
return self.canonical
def _merge_graph(self, g):
for n in g.nodes:
new_name = self.canonical.getNodeByLabel(n.attributes['label']).id
for e in n.edges:
to_node = self.canonical.getNodeByLabel(e.attributes['label']).id
self.canonical.addEdge(new_name, to_node)
def main():
parser = ArgumentParser(
description="Generate a graph of libc++ header dependencies")
parser.add_argument(
'-v', '--verbose', dest='verbose', action='store_true', default=False)
parser.add_argument(
'-o', '--output', dest='output', required=True,
help='The output file. stdout is used if not given',
type=str, action='store')
parser.add_argument(
'--no-compile', dest='no_compile', action='store_true', default=False)
parser.add_argument(
'--libcxx-only', dest='libcxx_only', action='store_true', default=False)
parser.add_argument(
'compile_commands', metavar='compile-commands-file',
help='the compile commands database')
args = parser.parse_args()
builder = DependencyCommand(args.compile_commands, args.output, new_std='-std=c++2a')
if not args.no_compile:
outputs = builder.run_for_headers(get_libcxx_headers())
graphs = post_process_outputs(outputs, args.libcxx_only)
else:
outputs = [os.path.join(args.output, l) for l in os.listdir(args.output) if not l.endswith('all_headers.dot')]
graphs = [dot.DirectedGraph.fromDotFile(o) for o in outputs]
canon = CanonicalGraphBuilder(graphs).build()
canon.toDotFile(os.path.join(args.output, 'all_headers.dot'))
all_graphs = graphs + [canon]
found_cycles = False
for g in all_graphs:
cycle_finder = dot.CycleFinder(g)
all_cycles = cycle_finder.findCyclesInGraph()
if len(all_cycles):
found_cycles = True
print("cycle in graph %s" % g.name)
for start, path in all_cycles:
print("Cycle for %s = %s" % (start, path))
if not found_cycles:
print("No cycles found")
if __name__ == '__main__':
main()
|
