Find Import Chains That Reach a Forbidden Package

A forbidden contract is most useful when it shows the whole chain of imports from your module to the forbidden package. Then you can see which import to remove. Write that search over an import graph given as data.

This is the same depth-first search as Find One Import Cycle and List Every Import Cycle Once. This time it looks for paths that reach a forbidden module, instead of paths back to the start.

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

graph maps each module to the modules it imports directly. Take this graph, with source="app" and forbidden="db":

app.a  imports  app.b
app.b  imports  db.engine

The result is:

[("app.a", "app.b", "db.engine"), ("app.b", "db.engine")]

Each chain starts at a different source module. Adding ("app.b", "db.engine") to ignore removes both chains. Adding ("app.a", "app.b") removes only the first.

Which modules are inside a package

A module is inside a package if its name equals the package name, or starts with the package name followed by a dot. db.engine is inside db. dbx.thing is outside db, and application.x is outside app. Names are case-sensitive.

Rules

• Start a search from every key of graph that is inside source.
• A chain is a tuple of module names with at least one import in it. Each module appears at most once in a chain, though different chains can share one.
• When an import reaches a module inside forbidden, record the chain and end that branch at the forbidden module.
• A module missing from the keys of graph imports nothing. It can end a chain if it is forbidden, and the search stops there.
• Skip each (importer, imported) pair listed in ignore. Match pairs exactly, without package prefixes. A pair listed twice counts once.
• A target listed twice in one module's imports still gives each chain once.
• If source and forbidden overlap, the same rules apply. A start module on its own has no import, and a module that imports itself repeats a module, so neither gives a chain.
• Return the chains sorted with normal tuple ordering. Do not change the inputs.

Track the modules on the current path separately for each branch. One visited set for the whole search would drop valid chains that share a module. Your solution must pass mypy --strict.