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 10import argparse 11import os 12import re 13import sys 14 15 16def is_config_header(h): 17 return os.path.basename(h) in ['__config', '__libcpp_version'] 18 19 20def is_experimental_header(h): 21 return ('experimental/' in h) or ('ext/' in h) 22 23 24def is_support_header(h): 25 return '__support/' in h 26 27 28class 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 36def list_all_roots_under(root): 37 result = [] 38 for root, _, files in os.walk(root): 39 for fname in files: 40 if '__support' in root: 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 49def 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 89def 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 100def transitively_includes(graph, h1, h2): 101 return (h1 != h2) and (h2 in transitive_closure_of_includes(graph, h1)) 102 103 104def 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 120def get_friendly_id(fname): 121 i = fname.index('include/') 122 assert(i >= 0) 123 result = fname[i+8:] 124 return result 125 126 127def 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 157if __name__ == '__main__': 158 parser = argparse.ArgumentParser(description='Produce a dependency graph of libc++ headers, in GraphViz dot format.') 159 parser.add_argument('--root', default=None, metavar='FILE', help='File or directory to be the root of the dependency graph') 160 parser.add_argument('-I', dest='search_dirs', default=[], action='append', metavar='DIR', help='Path(s) to search for local includes') 161 parser.add_argument('--show-transitive-edges', action='store_true', help='Show edges to headers that are transitively included anyway') 162 parser.add_argument('--show-config-headers', action='store_true', help='Show headers named __config') 163 parser.add_argument('--show-experimental-headers', action='store_true', help='Show headers in the experimental/ and ext/ directories') 164 parser.add_argument('--show-support-headers', action='store_true', help='Show headers in the __support/ directory') 165 parser.add_argument('--show-individual-line-counts', action='store_true', help='Include an individual line count in each node') 166 parser.add_argument('--show-cumulative-line-counts', action='store_true', help='Include a total line count in each node') 167 parser.add_argument('--error-on-file-not-found', action='store_true', help="Don't ignore failure to open an #included file") 168 169 options = parser.parse_args() 170 171 if options.root is None: 172 curr_dir = os.path.dirname(os.path.abspath(__file__)) 173 options.root = os.path.join(curr_dir, '../include') 174 175 if options.search_dirs == [] and os.path.isdir(options.root): 176 options.search_dirs = [options.root] 177 178 options.root = os.path.abspath(options.root) 179 options.search_dirs = [os.path.abspath(p) for p in options.search_dirs] 180 181 if os.path.isdir(options.root): 182 roots = list_all_roots_under(options.root) 183 elif os.path.isfile(options.root): 184 roots = [options.root] 185 else: 186 raise RuntimeError('--root seems to be invalid') 187 188 graph = build_graph(roots, options) 189 190 # Eliminate certain kinds of "visual noise" headers, if asked for. 191 def should_keep(fname): 192 return all([ 193 options.show_config_headers or not is_config_header(fname), 194 options.show_experimental_headers or not is_experimental_header(fname), 195 options.show_support_headers or not is_support_header(fname), 196 ]) 197 198 for fname in list(graph.keys()): 199 if should_keep(fname): 200 graph[fname].includes = [h for h in graph[fname].includes if should_keep(h)] 201 else: 202 del graph[fname] 203 204 # Look for cycles. 205 no_cycles_detected = True 206 for fname, entry in graph.items(): 207 for h in entry.includes: 208 if transitively_includes(graph, h, fname): 209 sys.stderr.write('Cycle detected between %s and %s\n' % ( 210 get_friendly_id(fname), get_friendly_id(h) 211 )) 212 no_cycles_detected = False 213 assert no_cycles_detected 214 215 print(get_graphviz(graph, options)) 216