Skip to content

symfonic.devtools.archcheck.cycles

cycles

Cycle detection over the runtime import graph (LAY-ADR SS7 rule 2).

Only module-level runtime imports create import-time cycles, so lazy (function-scoped) and if TYPE_CHECKING: imports are excluded from the graph. Detection uses an iterative Tarjan SCC to stay stack-safe on large trees.

strongly_connected_components 

strongly_connected_components(graph: Mapping[str, Iterable[str]]) -> list[list[str]]

Iterative Tarjan; returns every SCC (singletons included).

Source code in src/symfonic/devtools/archcheck/cycles.py 
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
def strongly_connected_components(graph: Mapping[str, Iterable[str]]) -> list[list[str]]:
    """Iterative Tarjan; returns every SCC (singletons included)."""
    index: dict[str, int] = {}
    lowlink: dict[str, int] = {}
    on_stack: set[str] = set()
    stack: list[str] = []
    counter = 0
    sccs: list[list[str]] = []

    for root in graph:
        if root in index:
            continue
        work: list[tuple[str, Iterator[str]]] = [(root, iter(graph.get(root, ())))]
        index[root] = lowlink[root] = counter
        counter += 1
        stack.append(root)
        on_stack.add(root)
        while work:
            node, edge_iter = work[-1]
            advanced = False
            for successor in edge_iter:
                if successor not in graph:
                    continue
                if successor not in index:
                    index[successor] = lowlink[successor] = counter
                    counter += 1
                    stack.append(successor)
                    on_stack.add(successor)
                    work.append((successor, iter(graph.get(successor, ()))))
                    advanced = True
                    break
                if successor in on_stack:
                    lowlink[node] = min(lowlink[node], index[successor])
            if advanced:
                continue
            work.pop()
            if work:
                parent = work[-1][0]
                lowlink[parent] = min(lowlink[parent], lowlink[node])
            if lowlink[node] == index[node]:
                component: list[str] = []
                while True:
                    member = stack.pop()
                    on_stack.discard(member)
                    component.append(member)
                    if member == node:
                        break
                sccs.append(component)
    return sccs