Forbidden import chains, with the route

Implement import-linter‘s forbidden contract — the one that finds the violations a grep cannot see, because they are three modules away.

def forbidden_chains(
    graph: Mapping[str, Sequence[str]],
    source: str,
    forbidden: str,
    ignore: Sequence[tuple[str, str]],
) -> list[tuple[str, ...]]:

• graph maps a module to the modules it imports.
• source and forbidden are package names. A module is inside a package when it equals it or starts with it followed by a dot. db.engine is inside db; dbx.thing is not, and neither is application.x inside app.
• ignore is import-linter’s ignore_imports: (importer, imported) edges to delete from the graph before checking. That is how a team records a known, deliberate exception without switching the whole contract off.

Return every simple import chain that starts at a module inside source and ends at a module inside forbidden:

• A chain is a tuple of module names, first element inside source, last element inside forbidden, no module repeated.
• The walk stops on reaching the forbidden package — the forbidden module is always the last element.
• A module that appears as an import target but is not a key of graph is a leaf: you cannot walk through it. Third-party and stdlib modules behave this way in every real graph.
• The result is sorted, and stable regardless of dict ordering.

Note that chains starting from different source modules are separate findings. If app.a → app.b → db.engine, you report both ("app.a", "app.b", "db.engine") and ("app.b", "db.engine") — one for each source module that can reach the forbidden package.

Why the chain, and not just a boolean. “Your domain layer depends on sqlite3” is not actionable. ("pricing.domain.order", "pricing.domain.util", "sqlite3") names the edge to cut. A structural check that reports a violation without a route gets triaged into the backlog and stays there; one that hands over the exact path gets fixed that afternoon.

Why transitivity is the point. A direct-edge check — the kind you can write with a grep — passes cleanly on domain → helpers → sqlite3, because no line in domain mentions sqlite3. That is precisely the violation you needed to find, and it is why this contract is a graph search rather than a name match.

A caution about the tooling this models. Static import-graph tools read the AST. Some count a function-local import sqlite3 and some do not, so a contract can be green on a real violation. Break yours on purpose once to find out which kind you have.

Your submission must pass mypy --strict. ignore arrives as a sequence of 2-tuples, and graph.get(node, ()) needs a default compatible with Sequence[str].