Title: Re-think our high level logic for type inference · Issue #22063 · python/mypy · GitHub
Open Graph Title: Re-think our high level logic for type inference · Issue #22063 · python/mypy
X Title: Re-think our high level logic for type inference · Issue #22063 · python/mypy
Description: 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...
Open Graph Description: 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 ...
X Description: 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 ...
Opengraph URL: https://github.com/python/mypy/issues/22063
X: @github
Domain: github.com
{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"Re-think our high level logic for type inference","articleBody":"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:\n```python\nclass B[T]: ...\nclass C(B[int]): ...\n\ndef first[T](xs: list[T]) -> T: ...\n\nb: B[int]\ncs: list[C]\nb = first(cs) # E: some bogus stuff about list being invariant\n```\nThere 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:\n* We special-case some type contexts if a return type is a type variable or a union of type variables\n* If both type context and return type are optional we \"unwrap\" them.\n* 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.\n* We accept `return` value twice (again, in full and empty context) and see which one doesn't result in an error.\n\nThis 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:\n* This approach has its downsides, such as bad performance, and cryptic error messages.\n* It may be a too large change to do.\n\nHowever, 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:\n1. Use return/outer type context to infer some type variables, and apply them.\n2. Use this partially inferred function type to infer types of arguments (in partial/erased context).\n3. Use the types of arguments to infer the rest of type variables of the _partially inferred function_.\n4. Re-accept the arguments, now in the full type context.\n\nI 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):\n\n 3. Infer argument-side constrains, and solve them together with constrains from step 1 to infer the type variables of the _original function_.\n\nIt 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 \n\nSome non-trivial things to consider:\n* Preserving current error message logic requires falling back to outer-first inference if the two-sided fails (at given nesting level).\n* 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.\n* 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).\n* 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.\n\nFinally, this will have some performance implications. Here are two things I have to mitigate:\n* Make expression cache more robust/reliable, see e.g. https://github.com/python/mypy/pull/22059\n* (Optionally, if problems arise) limit the nesting level after which we fallback to the outer-first inference.\n\nA vague analogy would be how PEG parsers work: it is \"conceptually\" a recursive descent parser (which has exponential complexity) with extensive and robust memoization.","author":{"url":"https://github.com/ilevkivskyi","@type":"Person","name":"ilevkivskyi"},"datePublished":"2026-09-28T16:25:28Z","url":"https://github.com/python/mypy/issues/22063"}
| react-profiling | 0 |
| react-import-map | react,react-dom,react-dom/client,react-dom/profiling,react-is,react/compiler-runtime,react/jsx-dev-runtime,react/jsx-runtime,scheduler@b8488ee2c322 |
| route-pattern | /_view_fragments/issues/show/:user_id/:repository/:id/issue_layout(.:format) |
| route-controller | voltron_issues_fragments |
| route-action | issue_layout |
| fetch-nonce | v2:020ffe8c-6966-e230-4d70-1a56b36ea5c9 |
| current-catalog-service-hash | 81bb79d38c15960b92d99bca9288a9108c7a47b18f2423d0f6438c5b7bcd2114 |
| request-id | 84C6:23FDF9:2068410:2C2B296:6B00247D |
| html-safe-nonce | a292d30b50d8ce659b9ab711c2101554b005d3cb3762b484d21c5aa0be448c7b |
| visitor-payload | eyJyZWZlcnJlciI6IiIsInJlcXVlc3RfaWQiOiI4NEM2OjIzRkRGOToyMDY4NDEwOjJDMkIyOTY6NkIwMDI0N0QiLCJ2aXNpdG9yX2lkIjoiOTU5OTM2MzQ2NDgxMjM5MTY1IiwicmVnaW9uX2VkZ2UiOiJpYWQiLCJyZWdpb25fcmVuZGVyIjoiaWFkIn0= |
| visitor-hmac | 7de68b639ca99084cd34f3f2746ef7de37374287336485c2c1e4889d4886213c |
| hovercard-subject-tag | issue:5617842093 |
| github-keyboard-shortcuts | repository,issues,copilot |
| google-site-verification | Apib7-x98H0j5cPqHWwSMm6dNU4GmODRoqxLiDzdx9I |
| octolytics-url | https://collector.github.com/github/collect |
| analytics-location | / |
| fb:app_id | 1401488693436528 |
| apple-itunes-app | app-id=1477376905, app-argument=https://github.com/_view_fragments/issues/show/python/mypy/22063/issue_layout |
| twitter:image | https://opengraph.githubassets.com/afbb3d3d50138e90ffebfe73d19c744be9953a762f99820f9aa50aec02407e5d/python/mypy/issues/22063 |
| twitter:card | summary_large_image |
| og:image | https://opengraph.githubassets.com/afbb3d3d50138e90ffebfe73d19c744be9953a762f99820f9aa50aec02407e5d/python/mypy/issues/22063 |
| og:image:alt | 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 ... |
| og:image:width | 1200 |
| og:image:height | 600 |
| og:site_name | GitHub |
| og:type | object |
| og:author:username | ilevkivskyi |
| hostname | github.com |
| expected-hostname | github.com |
| None | 4eb4cba0d69f045374ac15de9666d22b0961e1d555cc3824f36b7734c00c78e0 |
| turbo-cache-control | no-preview |
| go-import | github.com/python/mypy git https://github.com/python/mypy.git |
| octolytics-dimension-user_id | 1525981 |
| octolytics-dimension-user_login | python |
| octolytics-dimension-repository_id | 7053637 |
| octolytics-dimension-repository_nwo | python/mypy |
| octolytics-dimension-repository_public | true |
| octolytics-dimension-repository_is_fork | false |
| octolytics-dimension-repository_network_root_id | 7053637 |
| octolytics-dimension-repository_network_root_nwo | python/mypy |
| turbo-body-classes | logged-out env-production page-responsive |
| disable-turbo | false |
| browser-stats-url | https://api.github.com/_private/browser/stats |
| browser-errors-url | https://api.github.com/_private/browser/errors |
| release | 44c658b24abf00491fb7ae5f56d42c9f38cbeab2 |
| ui-target | full |
| theme-color | #1e2327 |
| color-scheme | light dark |
| react-app-name | issues |
Links:
Viewport: width=device-width