Re-think our high level logic for type inference

@JukkaL

There is a fundamental problem with how type inference for generic functions works in mypy. To illustrate, this simple basic example still fails as of now:

class B[T]: ...
class C(B[int]): ...

def first[T](xs: list[T]) -> T: ...

b: B[int]
cs: list[C]
b = first(cs)  # E: some bogus stuff about list being invariant

There are many similar examples where type inference fails. This problem is sometimes referred to as "overusing the outer context". As of now we have at least four weird ad-hoc workarounds in the code to compensate for this problem:

We special-case some type contexts if a return type is a type variable or a union of type variables
If both type context and return type are optional we "unwrap" them.
If type of a variable is a union, we accept r.h.s. in assignment to it twice, with full and empty context, and check which one gives a more narrow type.
We accept return value twice (again, in full and empty context) and see which one doesn't result in an error.

This all happens because mypy doesn't do a "full expression" inference (i.e. solving all type variables in an expression at the same time). I considered doing this a while ago, but:

This approach has its downsides, such as bad performance, and cryptic error messages.
It may be a too large change to do.

However, few days ago I realized that our current algorithm (Hanoi towers inference, as I call it) may actually be implemented not as intended. At very high level this is how it roughly works currently:

Use return/outer type context to infer some type variables, and apply them.
Use this partially inferred function type to infer types of arguments (in partial/erased context).
Use the types of arguments to infer the rest of type variables of the partially inferred function.
Re-accept the arguments, now in the full type context.

I think the emphasized part of step 3 is problematic. IMO it should work like this (and maybe it was actually intended to work like this):

Infer argument-side constrains, and solve them together with constrains from step 1 to infer the type variables of the original function.

It seems to me this (relatively modest, but still quite fundamental) change may solve many/most existing problems with overusing outer type context. We may not need the full expression type inference, it seems like simply solving return- and argument-side constraints together at each nesting level may be sufficient. Currently type context propagates one way: from outside in, with this change the inner type context will have a chance to "fight back". I played with this on the weekend, and first results look promising. But before fully committing to this, I wanted to see if there are any thoughts/objections or cases to consider. cc @JukkaL @hauntsaninja

Some non-trivial things to consider:

Preserving current error message logic requires falling back to outer-first inference if the two-sided fails (at given nesting level).
I am not sure yet what to do with two-pass argument inference (for lambdas). We may potentially integrate it fully in the new logic, but this will make overall logic too complex/hard to grasp.
Polymorphic inference may need some care. Right now it is still used as a fallback. Potentially we may keep it this way, since in most cases where it is useful, the outer context is empty (e.g. for decorators or functional programming).
We need to re-inspect (and potentially unify) what is considered a valid solution for a type variable, right now the logic is slightly different between various steps.

Finally, this will have some performance implications. Here are two things I have to mitigate:

Make expression cache more robust/reliable, see e.g. Make expression cache robust for nested generic calls #22059
(Optionally, if problems arise) limit the nesting level after which we fallback to the outer-first inference.

A vague analogy would be how PEG parsers work: it is "conceptually" a recursive descent parser (which has exponential complexity) with extensive and robust memoization.

@ilevkivskyi

Hi @ilevkivskyi, I’d like to investigate this and see whether I can contribute an implementation.

My initial plan would be to start by reproducing the examples from the issue and identifying the current constraint-solving path, then add focused regression tests around the outer-context/argument-context interaction before changing the inference logic.

The proposed approach of solving the return-side and argument-side constraints together seems particularly interesting. I’d like to first understand where the current “partially inferred function type → argument inference → solve remaining variables” flow is implemented, and whether the two-sided solving can be introduced at a single nesting level without changing unrelated inference behavior.

Would you be open to a contributor exploring an initial implementation/PR for this approach? I’d also be interested in any pointers to the relevant inference code or existing tests you’d recommend starting from.

Btw, I just noticed there was an earlier attempt to fix this issue #21803. It however uses a different (and IMO less principled) approach. That PR however shows the importance of this problem: it closes two dozen open issues.

@ilevkivskyi

Thanks @ilevkivskyi for pointing me to #21803. I’ll use it as a baseline to understand the existing approach and compare it with the two-sided constraint-solving direction proposed here.

I’ll first trace the current inference flow, reproduce the relevant cases from #21803, and identify where constraints are currently solved against the partially inferred function rather than the original function.

Then I’ll investigate whether the proposed change can be implemented as a focused modification while preserving the existing outer-first fallback and error-reporting behavior. I’ll share my findings before attempting an implementation.

@vinitsonawane45

@vinitsonawane45 Please don't (assuming you are a real person).

Btw, I just noticed there was an earlier attempt to fix this issue #21803. It however uses a different (and IMO less principled) approach. That PR however shows the importance of this problem: it closes two dozen open issues.

I just got bored one day and was trying to fix a reported issue without causing too many deeper changes, then it spiraled into dozens of issues and this whole big thing... It can definitely be closed once a better solution is prepared. The regression tests might be worth carrying over though.

Since you asked for cases to consider: I tried a rough sketch of the two-sided solve on the issue snippets #21803 affects. It fixes nearly all of them, including #20648, which #21803 only partly fixes because it can't use the arguments and the context at the same time. A couple things tripped it up:

Upper bounds from both sides. In ".".join(min(x, key=len)) with x: list[tuple[str, ...]], the context gives T <: Iterable[str] and len gives T <: Sized. The meet of those is Never, so solving fails even though tuple[str, ...] satisfies both. Checking the lower bound against each upper bound separately fixed the min/max(..., key=len) cases in Assigning to intermediate variable changes type checking results #19304 and error: "key" to "max" has incompatible type #21104.
Generic callable arguments that normally go through the second pass, e.g. s - reduce(frozenset.union, nests, empty) from functools.reduce over sets becomes unacceptable when used in a larger expression #17694. My sketch didn't handle this, so it's probably the two-pass question you already mentioned.

@rheard

@rheard Thanks for investigating this! I will not close #21803 just yet. I want to play with it before making any commitments (since this kind of change will affect a lot of people).

@ilevkivskyi

@ilevkivskyi I just ran into an issue with mypyc, mypyc/mypyc#1231, and found the same bug exists for mypy. I've gone ahead and created an issue for this, #22138.

I've prepared a fix for this but it changes the same code you're working on changing for this issue. I can create a PR but thought I'd just let you know so you can add it to your tests.

@rheard

@rheard Don't worry about possible merge conflicts. That said, that issue may be quite non-trivial to fix (for a quite niche edge case). At least I don't know what is the proper way to do it.

@ilevkivskyi

@ilevkivskyi Okay, I spoke up saying I had a fix prepared, when really I think it was my earlier draft of the two-sided solve I was thinking of. I've done a lot of mypy work in the last week and wires are getting crossed....

I've gone ahead and done that though I will say I'm not super confident about the PR, #22142, and you will likely want to close it. I basically did what you did in #20622, a binder frame whose changes get thrown away.

Again this is very likely to clash with what you're doing here though so I just wanted to bring it up.

Navigation Menu

Repository navigation

Re-think our high level logic for type inference #22063

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Re-think our high level logic for type inference #22063

Description

Activity

vinitsonawane45 commented on Sep 30, 2026

ilevkivskyi commented on Oct 4, 2026

vinitsonawane45 commented on Oct 4, 2026

ilevkivskyi commented on Oct 4, 2026

rheard commented on Oct 4, 2026

ilevkivskyi commented on Oct 4, 2026

rheard commented on Oct 7, 2026

ilevkivskyi commented on Oct 7, 2026

rheard commented on Oct 8, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions