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