find-include-cycles.py

#!/usr/bin/env python3
""" find-include-cycles.py - Find #include cycles in js/src. """

import collections, os, re, subprocess

def tarjan(V, E):
    # https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

    vertex_index = {}
    vertex_lowlink = {}

    index = 0
    S = []

    all_components = []

    def strongconnect(v):
        nonlocal index

        # Set the depth index for v to the smallest unused index
        vertex_index[v] = index
        vertex_lowlink[v] = index
        index += 1
        S.append(v)

        # Consider successors of v
        for w in E[v]:
            if w not in vertex_index:
                # Successor w has not yet been visited; recurse on it
                strongconnect(w)
                vertex_lowlink[v] = min(vertex_lowlink[v], vertex_lowlink[w])
            elif w in S:
                # Successor w is in stack S and hence in the current SCC
                vertex_lowlink[v] = min(vertex_lowlink[v], vertex_index[w])

        # If v is a root node, pop the stack and generate an SCC
        if vertex_lowlink[v] == vertex_index[v]:
            i = S.index(v)
            scc = S[i:]
            del S[i:]
            all_components.append(scc)

    for v in V:
        if v not in vertex_index:
            strongconnect(v)
    return all_components

def main():
    root_dir = subprocess.check_output(["hg", "root"], universal_newlines=True).strip()

    # Find all vertices.
    files = subprocess.check_output(["hg", "manifest"], universal_newlines=True).split("\n")
    js_files = set(f for f in files
                   if f.startswith("js/src/")
                   and not f.startswith(("js/src/ctypes/libffi/testsuite/",
                                         "js/src/gdb",
                                         "js/src/jsapi-tests"))
                   and f.endswith((".c", ".cpp", ".h", ".msg", ".tbl")))

    # Find all edges.
    edges = {}
    for filename in js_files:
        include_requests = set()
        with open(os.path.join(root_dir, filename), encoding='utf-8') as f:
            for line in f:
                m = re.match(r'\s*#\s*include\s+"([^"]*)"\s*$', line)
                if m is not None:
                    include_requests.add(m.group(1))

        actual_includes = set()
        base, slash, local = filename.rpartition("/")
        for request in include_requests:
            if request.endswith('.h') and request.startswith(('pr', 'mozilla/', 'js/',
                                                              'unicode/', 'wtf/', 'assembler/wtf/',
                                                              'selfhosted.out.h',
                                                              'jsautooplen.h',
                                                              'js-config.h')):
                continue
            for attempt in ('js/src/' + request, base + "/" + request):
                if attempt in js_files:
                    actual_includes.add(attempt)
                    break
            else:
                if filename in ('js/src/dtoa.c', 'js/src/ctypes/libffi/src/dlmalloc.c'):
                    continue
                print("warning: could not find %r, #included from %r" % (request, filename))
        edges[filename] = actual_includes

    print()

    # Find all cycles.
    print("finding cycles...")
    components = tarjan(js_files, edges)

    # Output cycles.
    def draw_component(c):
        cset = set(c)
        drawn = set()
        def draw(v, indent):
            print('    ' * (indent - 1) + (' -> ' if indent else '') + v)
            if v in drawn:
                return
            drawn.add(v)
            for succ in edges[v]:
                if succ in cset:
                    draw(succ, indent + 1)
        draw(c[0], 0)

    for c in components:
        if len(c) != 1:
            draw_component(c)
            print()


main()