How importlens works

1. Import resolution

Every .py file under SRC becomes a module. pkg/__init__.py is pkg, pkg/a.py is pkg.a. Directories without __init__.py are namespace packages: they have no node of their own but their children resolve normally. Names are relative to the directory above the outermost enclosing package, so passing src/pkg/sub still yields pkg.sub.x and absolute imports of pkg.sub.x resolve.

For each import statement:

  1. import a.b.c targets the deepest existing prefix (a.b.c, else a.b, else a). A missing leaf is usually an attribute.
  2. from X import n first turns X into an absolute name. For a relative import in module m with level L, start from m's package (m itself for an __init__), drop L-1 components, and append the module part. Going past the top is dropped.
  3. For every name n: if X.n is a module file, the edge goes to X.n; otherwise n is an attribute and the edge goes to X. * goes to X.
  4. If nothing internal matches and the top-level name is not one of the scanned top-level packages, it is recorded as an external (third-party or stdlib) for the allowlist rule.

Worked example, in pkg/sub/c.py:

from .. import a        # base pkg; pkg.a is a module -> edge c -> pkg.a
from ..b import thing   # base pkg.b; pkg.b.thing is not a module -> edge c -> pkg.b
import pkg.sub.c.x      # pkg.sub.c.x missing -> edge to pkg.sub.c itself, dropped as a self-edge

Each edge keeps every import site (file, line, type_checking, lazy). An edge is "TYPE_CHECKING" or "lazy" only if all its sites are, so one eager import makes it a real runtime dependency.

2. Tarjan SCC (iterative)

Recursive Tarjan overflows Python's recursion limit on long chains (the tests use a 20 000 node ring). The implementation keeps an explicit work stack of (node, successor-iterator) pairs and updates the parent's lowlink when a frame is popped. Components of size > 1 are cycle groups; self-imports are not edges.

3. Representative cycles and the cheapest edge

Inside one SCC, for each node v run one BFS from v restricted to the SCC. For every in-edge (u, v), the BFS path v -> ... -> u plus the edge is the shortest cycle through (u, v). Cycles are rotated to start at their smallest module and deduplicated.

To show a minimal set rather than hundreds of near-duplicates, cycles are sorted by length and kept greedily only if they cover an edge not yet covered. Every cyclic edge ends up in at least one shown cycle.

The suggested edge to break is chosen from the deduplicated shortest-cycle family: most cycles containing it, ties broken by fewest import sites (cheapest to edit), then by name.

Example: a -> b, b -> c, b -> a, c -> a. Shortest cycles: (a b) through a->b and b->a, (a b c) through b->c and c->a. a -> b is in both, so it is the suggestion.

4. Contracts

All pairwise rules reduce to a predicate bad(src, dst) -> message | None:

Direct violations test every graph edge and report the first import site. With --transitive, a BFS from each module finds every reachable dst at distance >= 2 where bad holds; the BFS shortest path is the reported chain (infra.mailer -> services.notifications -> domain.user). Pairs already reported directly are not repeated. External allowlists check each module's recorded third-party packages directly.

5. Metrics

For a module: Ca = distinct internal modules importing it, Ce = distinct internal modules it imports, I = Ce / (Ca + Ce) (0 if both are 0), A = abstract classes / classes where a class is abstract if a base or the metaclass is ABC, ABCMeta or Protocol, and D = |A + I - 1|.

For a package, members are all modules below it. Ca counts distinct modules outside the package that import any member, Ce distinct outside modules imported by members. Internal edges do not count, which is what makes package instability meaningful. A and LOC are summed over members. LOC counts non-blank, non-comment lines.

6. Dead modules

Reachability is a DFS from the entries over all edges (typing and lazy imports count as uses). Two implicit rules: importing a module executes its parent packages' __init__, so parents of a reachable module are reachable; and a reachable package whose __all__ names a submodule re-exports it, so that submodule is reachable (without adding an edge, which would fake cycles).

7. Diff

git archive <ref> -- <path> is extracted to a temp directory and analysed like any tree, giving identical module names. New edges are head - base. A new cycle is a cycle through at least one new edge: for each new edge inside a cyclic component of the head graph, the shortest cycle through it is reported. A new violation is one whose (rule, src, dst) key is absent from the base violations, so pre-existing debt does not fail the build.

8. HTML layout

assets/layout.js is a small force simulation: spring forces per edge (strength divided by the smaller endpoint degree so hubs are not torn apart), repulsion computed only between nodes in neighbouring cells of a spatial grid (so cost is roughly linear), weak gravity, velocity clamp, and a cooling alpha. Layout runs 3 ticks per animation frame until it settles; dragging a node pins it and reheats the simulation. Django (884 nodes) settles in about 250 ticks.