C/C++ dependency traverser

traverse_deps.py

from __future__ import print_function

import os
import sys
import argparse
import re
from collections import defaultdict

sourceexts = ['.c', '.cpp', '.h', '.hpp', '.cc']

def compute_includes(rootdir):
    """Build an adjacency list of the include graph"""
    basepathdir = os.path.realpath(os.path.join(rootdir, '..'))
    included_by = defaultdict(list)
    pat = re.compile(r'#include [\"<](.*)[\">]')
    for root, _, files in os.walk(rootdir):
        for fname in files:
            fullname = os.path.join(root, fname).replace('\\', '/')
            if not any(fullname.endswith(ext) for ext in sourceexts):
                continue
            relname = fullname[len(basepathdir) + 1:].lower()
            content = ''
            with open(fullname, 'r') as fp:
                content = fp.read()
            lines = content.splitlines()
            for line in lines:
                match = re.search(pat, line)
                if match:
                    header = match.group(1).lower()
                    included_by[header].append(relname)
    return included_by

def trace_dependencies(dependencies, included_by):
    """Compute all graph nodes, reachable from the dependency roots"""
    queue = []
    roots = set([])
    for include in included_by:
        include = include.lower()
        for dependency in dependencies:
            if dependency.lower() not in include:
                continue
            queue.append(include)
            roots.add(include)

    visited = set([])
    qbtm = 0
    while qbtm < len(queue):
        sourcefile = queue[qbtm]
        qbtm += 1
        visited.add(sourcefile)
        for dependent in included_by[sourcefile]:
            if dependent in visited:
                continue
            queue.append(dependent)
    return sorted(list(visited - roots))

def group_by_level(files, level=2):
    """Reduce the list of files to the list of maximum level-deep directories"""
    return sorted(list(set(['/'.join(f.split('/', level)[:level]) for f in files])))

def main(codebase_root, dependencies, group_level):
    include_map = compute_includes(codebase_root)
    dependents = trace_dependencies(dependencies, include_map)
    dependents = group_by_level(dependents, level=group_level)
    print('\n'.join(dependents))

if __name__ == "__main__":
    help = """C/C++ codebase dependency traverser
    This script returns all files in a C/C++ codebase that directly or indirectly
    include one of the provided dependencies. Some assumptions:

    1) if a file contains '#include <some-string-with-SUBSTRING-and-else>', we say it depends on SUBSTRING
    2) dependencies are case-insensitive
    3) in-codebase includes have paths which start with the codebase's root dir

    """
    parser = argparse.ArgumentParser(description=help)
    parser.add_argument('--root', default='.', help='path to codebase\'s root')
    parser.add_argument('--group-level', type=int, default=1000, help='trim paths to first GROUP-LEVEL dirs')
    parser.add_argument('dependecies', nargs='+', help='dependencies to trace')
    args = parser.parse_args()
    main(os.path.realpath(args.root), args.dependecies, args.group_level)