python / python/mypy

Experiment with backtracking in the new solver

Open
#15,908 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

feature priority-1-normal topic-type-variables
Dominant language
Python
Stars
20.6k
Forks
3.3k
PR merge metrics
PR metrics pending

Description

Depend on https://github.com/python/mypy/issues/15906. This is a follow-up for series started by https://github.com/python/mypy/pull/15287

Currently when getting both upper and lower bounds for a type variable we randomly choose the lower one. This is not always the best choice and can lead to inference failures. A possible example is:

def dec(fn: Callable[[S, S, int], float]) -> Callable[[S], float]: ... 
def f(x: List[float], y: List[T], z: T) -> T: ...
dec(f)

this will infer constraints like

S <: List[float], S <: List[T], T <: float, T :> int

They split into two SCCs each containing one variable {T} and {S}, and the second depends on first one. So we would first solve T = int and then we will get updated constraints for S: S <: List[float], S <: List[int], with the only solution S = <nothing>. At the same time T = float, S = List[float] is a totally valid solution. We could get it by backtracking when we get <nothing> and trying different bound(s) in the previous SCC.

One possible problem I see is that this backtracking is exponential in worst case of inference failure (e.g. due to actual user error). Another problem is that backtracking can make implementation much less readable.

cc @JukkaL

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reading issue #15906 and the follow-up series in pull request #15287 to understand the solver changes already under way. Then examine the type-variable constraint example in this issue and determine how a backtracking experiment would be scoped. Done would require an agreed design and evidence about inference failures and worst-case behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
compilers, devtools
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.