#!/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()