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