Add first cut of C code coverage tool

3 files changed, 302 insertions, 0 deletions

diff --git a/tools/c_coverage/HOWTO_C_COVERAGE.txt b/tools/c_coverage/HOWTO_C_COVERAGE.txt
new file mode 100644
index 000000000..aa4737a3f
--- /dev/null
+++ b/tools/c_coverage/HOWTO_C_COVERAGE.txt
@@ -0,0 +1,118 @@
+===============
+C coverage tool
+===============
+
+This directory contains a tool to generate C code-coverage reports
+using valgrind's callgrind tool.
+
+Prerequisites
+-------------
+
+ * `Valgrind <http://www.valgrind.org/>`_ (3.5.0 tested, earlier
+   versions may work)
+
+ * `Pygments <http://www.pygments.org/>`_ (0.11 or later required)
+
+C code-coverage
+---------------
+
+Generating C code coverage reports requires two steps:
+
+ * Collecting coverage results (from valgrind)
+
+ * Generating a report from one or more sets of results
+
+For most cases, it is good enough to do::
+
+  > c_coverage_collect.sh python -c "import numpy; numpy.test()"
+  > c_coverage_report.py callgrind.out.pid
+
+which will run all of the Numpy unit tests, create a directory called
+`coverage` and place the coverage results there.
+
+In a more advanced scenario, you may wish to run individual unit tests
+(since running under valgrind slows things down) and combine multiple
+results files together in a single report.
+
+Collecting results
+``````````````````
+
+To collect coverage results, you merely run the python interpreter
+under valgrind's callgrind tool.  The `c_coverage_collect.sh` helper
+script will pass all of the required arguments to valgrind.
+
+For example, in typical usage, you may want to run all of the Numpy
+unit tests::
+
+  > c_coverage_collect.sh python -c "import numpy; numpy.test()"
+
+This will output a file ``callgrind.out.pid`` containing the results of
+the run, where ``pid`` is the process id of the run.
+
+Generating a report
+```````````````````
+
+To generate a report, you pass the ``callgrind.out.pid`` output file to
+the `c_coverage_report.py` script::
+
+  > c_coverage_report.py callgrind.out.pid
+
+To combine multiple results files together, simply list them on the
+commandline or use wildcards::
+
+  > c_coverage_report.py callgrind.out.*
+
+Options
+'''''''
+
+  * ``--directory``: Specify a different output directory
+
+  * ``--pattern``: Specify a regex pattern to match for source files.
+    The default is `numpy`, so it will only include source files whose
+    path contains the string `numpy`.  If, for instance, you wanted to
+    include all source files covered (that are available on your
+    system), pass ``--pattern=.``.
+
+  * ``--format``: Specify the output format(s) to generate.  May be
+    either ``text`` or ``html``.  If ``--format`` is not provided,
+    both formats will be output.
+
+Reading a report
+----------------
+
+The C code coverage report is a flat directory of files, containing
+text and/or html files.  The files are named based on their path in
+the original source tree with slashes converted to underscores.
+
+Text reports
+````````````
+
+The text reports add a prefix to each line of source code:
+
+ - '>' indicates the line of code was run
+
+ - '!' indicates the line of code was not run
+
+HTML reports
+````````````
+
+The HTML report highlights the code that was run in green.
+
+The HTML report has special support for the "generated" functions in
+Numpy.  Each run line of code also contains a number in square
+brackets indicating the number of different generated functions the
+line was run in.  Hovering the mouse over the line will display a list
+of the versions of the function in which the line was run.  These
+numbers can be used to see if a particular line was run in all
+versions of the function.
+
+Caveats
+-------
+
+The coverage results occasionally misses lines that clearly must have
+been run.  This usually can be traced back to the compiler optimizer
+removing lines because they are tautologically impossible or to
+combine lines together.  Compiling Numpy without optimizations helps,
+but not completely.  Even despite this flaw, this tool is still
+helpful in identifying large missed blocks or functions.
+
diff --git a/tools/c_coverage/c_coverage_collect.sh b/tools/c_coverage/c_coverage_collect.sh
new file mode 100755
index 000000000..3659d56e7
--- /dev/null
+++ b/tools/c_coverage/c_coverage_collect.sh
@@ -0,0 +1,2 @@
+#!/usr/bin/env bash
+valgrind --tool=callgrind --compress-strings=no --compress-pos=no --collect-jumps=yes "$@"
diff --git a/tools/c_coverage/c_coverage_report.py b/tools/c_coverage/c_coverage_report.py
new file mode 100755
index 000000000..0c9574511
--- /dev/null
+++ b/tools/c_coverage/c_coverage_report.py
@@ -0,0 +1,182 @@
+#!/usr/bin/env python
+"""
+A script to create C code-coverage reports based on the output of
+valgrind's callgrind tool.
+"""
+
+import optparse
+import os
+import re
+import sys
+from xml.sax.saxutils import quoteattr, escape
+
+try:
+    import pygments
+    if tuple([int(x) for x in pygments.__version__.split('.')]) < (0, 11):
+        raise ImportError()
+    from pygments import highlight
+    from pygments.lexers import CLexer
+    from pygments.formatters import HtmlFormatter
+    has_pygments = True
+except ImportError:
+    print "This script requires pygments 0.11 or greater to generate HTML"
+    has_pygments = False
+
+
+class FunctionHtmlFormatter(HtmlFormatter):
+    """Custom HTML formatter to insert extra information with the lines."""
+    def __init__(self, lines, **kwargs):
+        HtmlFormatter.__init__(self, **kwargs)
+        self.lines = lines
+
+    def wrap(self, source, outfile):
+        for i, (c, t) in enumerate(HtmlFormatter.wrap(self, source, outfile)):
+            as_functions = self.lines.get(i-1, None)
+            if as_functions is not None:
+                yield 0, ('<div title=%s style="background: #ccffcc">[%2d]' %
+                          (quoteattr('as ' + ', '.join(as_functions)),
+                           len(as_functions)))
+            else:
+                yield 0, '    '
+            yield c, t
+            if as_functions is not None:
+                yield 0, '</div>'
+
+
+class SourceFile:
+    def __init__(self, path):
+        self.path = path
+        self.lines = {}
+
+    def mark_line(self, lineno, as_func=None):
+        line = self.lines.setdefault(lineno, set())
+        if as_func is not None:
+            as_func = as_func.split("'", 1)[0]
+            line.add(as_func)
+
+    def write_text(self, fd):
+        source = open(self.path, "r")
+        for i, line in enumerate(source.readlines()):
+            if i + 1 in self.lines:
+                fd.write("> ")
+            else:
+                fd.write("! ")
+            fd.write(line)
+        source.close()
+
+    def write_html(self, fd):
+        source = open(self.path, 'r')
+        code = source.read()
+        lexer = CLexer()
+        formatter = FunctionHtmlFormatter(
+            self.lines,
+            full=True,
+            linenos='inline')
+        fd.write(highlight(code, lexer, formatter))
+        source.close()
+
+
+class SourceFiles:
+    def __init__(self):
+        self.files = {}
+        self.prefix = None
+
+    def get_file(self, path):
+        if path not in self.files:
+            self.files[path] = SourceFile(path)
+            if self.prefix is None:
+                self.prefix = path
+            else:
+                self.prefix = os.path.commonprefix([self.prefix, path])
+        return self.files[path]
+
+    def clean_path(self, path):
+        path = path[len(self.prefix):]
+        return re.sub("[^A-Za-z0-9\.]", '_', path)
+
+    def write_text(self, root):
+        for path, source in self.files.items():
+            fd = open(os.path.join(root, self.clean_path(path)), "w")
+            source.write_text(fd)
+            fd.close()
+
+    def write_html(self, root):
+        for path, source in self.files.items():
+            fd = open(os.path.join(root, self.clean_path(path) + ".html"), "w")
+            source.write_html(fd)
+            fd.close()
+
+        fd = open(os.path.join(root, 'index.html'), 'w')
+        fd.write("<html>")
+        paths = self.files.keys()
+        paths.sort()
+        for path in paths:
+            fd.write('<p><a href="%s.html">%s</a></p>' %
+                     (self.clean_path(path), escape(path[len(self.prefix):])))
+        fd.write("</html>")
+        fd.close()
+
+
+def collect_stats(files, fd, pattern):
+    # TODO: Handle compressed callgrind files
+    line_regexs = [
+        re.compile("(?P<lineno>[0-9]+)(\s[0-9]+)+"),
+        re.compile("((jump)|(jcnd))=([0-9]+)\s(?P<lineno>[0-9]+)")
+        ]
+
+    current_file = None
+    current_function = None
+    for i, line in enumerate(fd.readlines()):
+        if re.match("f[lie]=.+", line):
+            path = line.split('=', 2)[1].strip()
+            if os.path.exists(path) and re.search(pattern, path):
+                current_file = files.get_file(path)
+            else:
+                current_file = None
+        elif re.match("fn=.+", line):
+            current_function = line.split('=', 2)[1].strip()
+        elif current_file is not None:
+            for regex in line_regexs:
+                match = regex.match(line)
+                if match:
+                    lineno = int(match.group('lineno'))
+                    current_file.mark_line(lineno, current_function)
+
+
+if __name__ == '__main__':
+    parser = optparse.OptionParser(
+        usage="[options] callgrind_file(s)")
+    parser.add_option(
+        '-d', '--directory', dest='directory',
+        default='coverage',
+        help='Destination directory for output [default: coverage]')
+    parser.add_option(
+        '-p', '--pattern', dest='pattern',
+        default='numpy',
+        help='Regex pattern to match against source file paths [default: numpy]')
+    parser.add_option(
+        '-f', '--format', dest='format', default=[],
+        action='append', type='choice', choices=('text', 'html'),
+        help="Output format(s) to generate, may be 'text' or 'html' [default: both]")
+    (options, args) = parser.parse_args()
+
+    files = SourceFiles()
+    for log_file in args:
+        log_fd = open(log_file, 'r')
+        collect_stats(files, log_fd, options.pattern)
+        log_fd.close()
+
+    if not os.path.exists(options.directory):
+        os.makedirs(options.directory)
+
+    if options.format == []:
+        formats = ['text', 'html']
+    else:
+        formats = options.format
+    if 'text' in formats:
+        files.write_text(options.directory)
+    if 'html' in formats:
+        if not has_pygments:
+            print "Pygments 0.11 or later is required to generate HTML"
+            sys.exit(1)
+        files.write_html(options.directory)