Index: share/mk/graph-mkincludes =================================================================== --- /dev/null +++ share/mk/graph-mkincludes @@ -0,0 +1,288 @@ +#!/usr/bin/env python + +# Copyright (c) 2016 Jonathan Anderson. All rights reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in the +# documentation and/or other materials provided with the distribution. +# +# THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND +# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +# ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE +# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +# OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +# OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +# SUCH DAMAGE. + +""" +Parser for the include graph of BSD makefiles. + +Reads BSD makefiles and constructs a graph of file inclusions. This graph +incorporates knowledge of the order in which these files are included and +can show how metadata such as variables propagate through the graph. + +Usage: + graph-makeincludes [options] [ ...] + graph-makeincludes -h | --help + graph-makeincludes --version + +Options: + -h --help Show this screen. + --version Show version. + --metadata= Metadata to search for [default: CC, LOCALBASE] + -o , --output= Output file, or '-' for stdout [default: -]. + filename Input file(s), in BSD make form +""" + +import collections +import docopt +import itertools +import re +import sys + + +class File(object): + """ + A file in the Makefile graph contains zero or more `.include` lines + and also keeps track of where it is `.include`d. + """ + def __init__(self): + self.lines = collections.defaultdict(Line) + self.edges_out = set() + +class Line(object): + """ + A `.include` line includes a source makefile into the current file. + """ + def __init__(self): + self.edges_in = set() + self.metadata = collections.defaultdict(bool) + + +# Metadata that can be present at a particular line of a makefile +# (e.g., an important variable or a suffix rule). We can select which metadata +# we care about through the command-line argument --metadata. +all_metadata = { + 'CC': re.compile('^CC\t*\??='), + 'CFLAGS': re.compile('^CFLAGS\t*\??='), + 'CTFCONVERT_CMD': re.compile('CTFCONVERT_CMD.*='), + 'LOCALBASE': re.compile('^LOCALBASE\??='), + 'Suffix rules': re.compile('^\.c\.o:$'), +} + + +def parse(filenames, metadata): + """ + Look through a set of Makefiles to find "interesting" lines + (e.g., those that include other Makefiles or define key variables). + """ + + parse.include = re.compile('^\.[a-z]?include [<"](.*)[>"]') + files = collections.defaultdict(File) + + for filename in filenames: + line_number = 0 + + for line in open(filename): + line_number += 1 + + # This lambda ensures we retrieve the file/line only as + # needed, avoiding spurious object / node creation. + get_node = lambda: files[filename].lines[line_number] + + match = parse.include.match(line) + if match: + node = get_node() + + (included,) = match.groups() + node.edges_in.add(included) + files[included].edges_out.add(node) + + for (name, pattern) in metadata.items(): + if pattern.match(line): + get_node().metadata[name] = True + + return files + + +def propagate_metadata(files, metadata): + """ + Propagate all metadata through the graph, repeating until we can + walk though the entire graph without doing any propagation. + """ + + def propagate(source, dest): + """ + Propagate the presence of metadata from one node to another. + """ + for name in metadata: + if source.metadata[name] and not dest.metadata[name]: + dest.metadata[name] = True + propagate.new_taint = True + + propagate.new_taint = True + + while propagate.new_taint: + propagate.new_taint = False + + for (filename,f) in files.items(): + previous = None + + # Propagate from line to line within the file: + for line_number in sorted(f.lines.keys()): + node = f.lines[line_number] + if previous: propagate(previous, node) + previous = node + + # Propagate from the last line to its include sites: + if previous: + last = previous + for recipient in f.edges_out: + propagate(last, recipient) + + +def attribute_list(attrs): + """ + Convert a Python dictionary to a GraphViz dot attribute list. + """ + return '[ %s ]' % ', '.join([ '%s="%s"' % (a,attrs[a]) for a in attrs]) + + +# Parse arguments. +args = docopt.docopt(__doc__) + +filenames = args[''] +outname = args['--output'] +outfile = open(outname, 'w') if outname != '-' else sys.stdout + +# Filter out the metadata we aren't interested in. +metadata = {k:v for k,v in all_metadata.iteritems() if k in args['--metadata']} +pastels = [ '/pastel28/%d' % x for x in range(1,9) ] +colours = dict(zip(metadata.keys(), itertools.cycle(pastels))) + + +# +# Parse the makefiles and propagate any metadata that we care about. +# +files = parse(filenames, metadata) +propagate_metadata(files, metadata) + + +# +# Write the actual graph, starting with a legend: +# +outfile.write(''' +digraph { + rankdir = TB; + + subgraph cluster_legend { + label = "Legend"; + rankdir = TB; + edge [ style = invis; ]; +''') + +prev = None + +for name in sorted(metadata): + outfile.write(' "%s" %s;\n' % (name, attribute_list({ + 'style': 'filled', + 'fillcolor': colours[name], + }))) + + if prev: outfile.write(' "%s" -> "%s";\n' % (prev, name)) + prev = name + +outfile.write('\n }\n') + +# +# First, define each file as a cluster of lines (or just a box): +# +for (filename,f) in files.items(): + safe_name = filename.replace('.', '_').replace( + '-', '_').replace('$','_').replace('/', '_') + + lines = sorted(f.lines.items(), key = lambda (l,_): l) + + # + # If a file has no .include lines, it is only a source of include + # material rather than a recipient of it. Represent such files + # just a box. + # + if len(lines) == 0: + attrs = attribute_list({ + 'label': filename, + 'shape': 'rectangle', + }) + + outfile.write(' "%s" %s;\n' % (filename, attrs)) + continue + + + # + # If the file does contain .include lines, show these lines as + # nodes within a boxed cluster. + # + outfile.write(' subgraph cluster_%s {\n' % safe_name) + outfile.write(' rankdir = TB;\n') + outfile.write(' label = "%s";\n' % filename) + + previous = None + + for (line_number, node) in lines: + name = '%s:%d' % (filename, line_number) + fills = [] + for metaname in node.metadata.keys(): + if node.metadata[metaname]: + fills.append(colours[metaname]) + + if len(fills) == 0: + fills = [ 'white' ] + + attrs = { + 'label': line_number, + 'style': 'filled', + 'fillcolor': ':'.join(fills), + } + + outfile.write(' "%s" %s;\n' % (name, attribute_list(attrs))) + + if previous: + attrs = { 'style': 'dotted' } + outfile.write(' "%s" -> "%s" %s;\n' % ( + previous, name, attribute_list(attrs))) + + previous = name + + outfile.write(' }\n') + +# +# Now iterate through all nodes again to join the clusters up. +# We have to do things this way so that we don't end up defining nodes +# inside the wrong clusters. +# +for (filename,f) in files.items(): + for (line_number, node) in f.lines.items(): + name = '%s:%d' % (filename, line_number) + + for source_filename in node.edges_in: + source_file = files[source_filename] + source_lines = sorted(source_file.lines.keys()) + + if len(source_lines) == 0: + source = source_filename + else: + final_line = source_lines[-1] + source = '%s:%d' % (source_filename, final_line) + + outfile.write(' "%s" -> "%s";\n' % (source, name)) + +outfile.write('}\n')