Skip to content

Sort modules in dependency cycles based on dependencies #1530

@JukkaL

Description

@JukkaL

Topo sort modules within dependency cycles to get a more consistent build ordering and fewer bogus errors due to ordering issues. Specifically, each import would have a priority (high/low).
Topo sort modules in a cycle by considering high-priority dependencies first. We can use low-priority dependencies as secondary sort criteria.

We'd assign a high priority in these cases:

  • from m import ... at module top level (not within a function) so that one of the imported names is not a module
  • Imported module referenced at module top level outside import statements (independent of the kind of import)

Exceptions:

  • Anything within if False: is ignored and can't affect ordering.
  • References to a module within type annotations are ignored. (Optimally, we'd only ignore string-literal-quoted references and comment annotations, but we don't have that information yet.)

Intuitively, we want to make build ordering approximate the order in which modules are initialized at runtime.

Example:

from util import helper_func   # high, at top level
import model  # high, used at top level (as base class)
import logger  # low, use only within function

class Person(model.Model):
    def check(self) -> None:
        from validators import validate    # low, within function

def log(s: str) -> None:
    logger.log(s)

Expected benefits:

  1. A base class will usually be type checked before a derived class (if defined in different modules), so attributes and decorated methods in the base class would have inferred types when type checking the derived class.

  2. Less likely to access an imported type alias that hasn't been processed yet, but only if type alias is imported using from m import ....

  3. Order of checking modules within a cycle would be more predictable. This is useful, as ordering changes may result in "Cannot determine type" errors that seem to come out of nowhere.

  4. Cycles caused by mypy-only imports within if False: blocks won't affect the ordering of a build.

This would partially solve #481. The rules above still don't cover all interesting problems but they should give a clear improvement for a lot of code.

This could perhaps be implemented as a new pass in process_stale_scc, where we'd sort the strongly connected component before the main semantic analysis pass.

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions