Page MenuHomeFreeBSD
Files F167512379

D6616.id17021.diff
No OneTemporary
Actions

D6616.id17021.diff
View Options

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] <filename> [<filename> ...]
+ graph-makeincludes -h | --help
+ graph-makeincludes --version
+
+Options:
+ -h --help Show this screen.
+ --version Show version.
+ --metadata=<metadata> Metadata to search for [default: CC, LOCALBASE]
+ -o <file>, --output=<file> 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['<filename>']
+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')

File Metadata

Mime Type
text/plain
Expires
Sun, Aug 23, 9:44 AM (1 h, 42 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
37130911
Default Alt Text
D6616.id17021.diff (8 KB)

Event Timeline