libcxx/utils/graph_header_deps.py

   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
  10 import argparse
  11 import os
  12 import re
  13 import sys
  14
  15
  16 def is_config_header(h):
  17     return os.path.basename(h) in ['__config', '__undef_macros', 'version']
  18
  19
  20 def is_experimental_header(h):
  21     return ('experimental/' in h) or ('ext/' in h)
  22
  23
  24 def is_support_header(h):
  25     return '__support/' in h
  26
  27
  28 class FileEntry:
  29     def __init__(self, includes, individual_linecount):
  30         self.includes = includes
  31         self.individual_linecount = individual_linecount
  32         self.cumulative_linecount = None  # documentation: this gets filled in later
  33         self.is_graph_root = None  # documentation: this gets filled in later
  34
  35
  36 def list_all_roots_under(root):
  37     result = []
  38     for root, _, files in os.walk(root):
  39         for fname in files:
  40             if os.path.basename(root).startswith('__') or fname.startswith('__'):
  41                 pass
  42             elif ('.' in fname and not fname.endswith('.h')):
  43                 pass
  44             else:
  45                 result.append(root + '/' + fname)
  46     return result
  47
  48
  49 def build_file_entry(fname, options):
  50     assert os.path.exists(fname)
  51
  52     def locate_header_file(h, paths):
  53         for p in paths:
  54             fullname = p + '/' + h
  55             if os.path.exists(fullname):
  56                 return fullname
  57         if options.error_on_file_not_found:
  58             raise RuntimeError('Header not found: %s, included by %s' % (h, fname))
  59         return None
  60
  61     local_includes = []
  62     system_includes = []
  63     linecount = 0
  64     with open(fname, 'r', encoding='utf-8') as f:
  65         for line in f.readlines():
  66             linecount += 1
  67             m = re.match(r'\s*#\s*include\s+"([^"]*)"', line)
  68             if m is not None:
  69                 local_includes.append(m.group(1))
  70             m = re.match(r'\s*#\s*include\s+<([^>]*)>', line)
  71             if m is not None:
  72                 system_includes.append(m.group(1))
  73
  74     fully_qualified_includes = [
  75         locate_header_file(h, options.search_dirs)
  76         for h in system_includes
  77     ] + [
  78         locate_header_file(h, os.path.dirname(fname))
  79         for h in local_includes
  80     ]
  81
  82     return FileEntry(
  83         # If file-not-found wasn't an error, then skip non-found files
  84         includes = [h for h in fully_qualified_includes if h is not None],
  85         individual_linecount = linecount,
  86     )
  87
  88
  89 def transitive_closure_of_includes(graph, h1):
  90     visited = set()
  91     def explore(graph, h1):
  92         if h1 not in visited:
  93             visited.add(h1)
  94             for h2 in graph[h1].includes:
  95                 explore(graph, h2)
  96     explore(graph, h1)
  97     return visited
  98
  99
 100 def transitively_includes(graph, h1, h2):
 101     return (h1 != h2) and (h2 in transitive_closure_of_includes(graph, h1))
 102
 103
 104 def build_graph(roots, options):
 105     original_roots = list(roots)
 106     graph = {}
 107     while roots:
 108         frontier = roots
 109         roots = []
 110         for fname in frontier:
 111             if fname not in graph:
 112                 graph[fname] = build_file_entry(fname, options)
 113                 graph[fname].is_graph_root = (fname in original_roots)
 114                 roots += graph[fname].includes
 115     for fname, entry in graph.items():
 116         entry.cumulative_linecount = sum(graph[h].individual_linecount for h in transitive_closure_of_includes(graph, fname))
 117     return graph
 118
 119
 120 def get_friendly_id(fname):
 121     i = fname.index('include/')
 122     assert(i >= 0)
 123     result = fname[i+8:]
 124     return result
 125
 126
 127 def get_graphviz(graph, options):
 128
 129     def get_decorators(fname, entry):
 130         result = ''
 131         if entry.is_graph_root:
 132             result += ' [style=bold]'
 133         if options.show_individual_line_counts and options.show_cumulative_line_counts:
 134             result += ' [label="%s\\n%d indiv, %d cumul"]' % (
 135                 get_friendly_id(fname), entry.individual_linecount, entry.cumulative_linecount
 136             )
 137         elif options.show_individual_line_counts:
 138             result += ' [label="%s\\n%d indiv"]' % (get_friendly_id(fname), entry.individual_linecount)
 139         elif options.show_cumulative_line_counts:
 140             result += ' [label="%s\\n%d cumul"]' % (get_friendly_id(fname), entry.cumulative_linecount)
 141         return result
 142
 143     result = ''
 144     result += 'strict digraph {\n'
 145     result += '    rankdir=LR;\n'
 146     result += '    layout=dot;\n\n'
 147     for fname, entry in graph.items():
 148         result += '    "%s"%s;\n' % (get_friendly_id(fname), get_decorators(fname, entry))
 149         for h in entry.includes:
 150             if any(transitively_includes(graph, i, h) for i in entry.includes) and not options.show_transitive_edges:
 151                 continue
 152             result += '        "%s" -> "%s";\n' % (get_friendly_id(fname), get_friendly_id(h))
 153     result += '}\n'
 154     return result
 155
 156
 157 if __name__ == '__main__':
 158     parser = argparse.ArgumentParser(
 159         description='Produce a dependency graph of libc++ headers, in GraphViz dot format.\n' +
 160                     'For example, ./graph_header_deps.py | dot -Tpng > graph.png',
 161         formatter_class=argparse.RawDescriptionHelpFormatter,
 162     )
 163     parser.add_argument('--root', default=None, metavar='FILE', help='File or directory to be the root of the dependency graph')
 164     parser.add_argument('-I', dest='search_dirs', default=[], action='append', metavar='DIR', help='Path(s) to search for local includes')
 165     parser.add_argument('--show-transitive-edges', action='store_true', help='Show edges to headers that are transitively included anyway')
 166     parser.add_argument('--show-config-headers', action='store_true', help='Show universally included headers, such as __config')
 167     parser.add_argument('--show-experimental-headers', action='store_true', help='Show headers in the experimental/ and ext/ directories')
 168     parser.add_argument('--show-support-headers', action='store_true', help='Show headers in the __support/ directory')
 169     parser.add_argument('--show-individual-line-counts', action='store_true', help='Include an individual line count in each node')
 170     parser.add_argument('--show-cumulative-line-counts', action='store_true', help='Include a total line count in each node')
 171     parser.add_argument('--error-on-file-not-found', action='store_true', help="Don't ignore failure to open an #included file")
 172
 173     options = parser.parse_args()
 174
 175     if options.root is None:
 176         curr_dir = os.path.dirname(os.path.abspath(__file__))
 177         options.root = os.path.join(curr_dir, '../include')
 178
 179     if options.search_dirs == [] and os.path.isdir(options.root):
 180         options.search_dirs = [options.root]
 181
 182     options.root = os.path.abspath(options.root)
 183     options.search_dirs = [os.path.abspath(p) for p in options.search_dirs]
 184
 185     if os.path.isdir(options.root):
 186         roots = list_all_roots_under(options.root)
 187     elif os.path.isfile(options.root):
 188         roots = [options.root]
 189     else:
 190         raise RuntimeError('--root seems to be invalid')
 191
 192     graph = build_graph(roots, options)
 193
 194     # Eliminate certain kinds of "visual noise" headers, if asked for.
 195     def should_keep(fname):
 196         return all([
 197             options.show_config_headers or not is_config_header(fname),
 198             options.show_experimental_headers or not is_experimental_header(fname),
 199             options.show_support_headers or not is_support_header(fname),
 200         ])
 201
 202     for fname in list(graph.keys()):
 203         if should_keep(fname):
 204             graph[fname].includes = [h for h in graph[fname].includes if should_keep(h)]
 205         else:
 206             del graph[fname]
 207
 208     # Look for cycles.
 209     no_cycles_detected = True
 210     for fname, entry in graph.items():
 211         for h in entry.includes:
 212             if h == fname:
 213                 sys.stderr.write('Cycle detected: %s includes itself\n' % (
 214                     get_friendly_id(fname)
 215                 ))
 216                 no_cycles_detected = False
 217             elif transitively_includes(graph, h, fname):
 218                 sys.stderr.write('Cycle detected between %s and %s\n' % (
 219                     get_friendly_id(fname), get_friendly_id(h)
 220                 ))
 221                 no_cycles_detected = False
 222     assert no_cycles_detected
 223
 224     print(get_graphviz(graph, options))