Experiment with backtracking in the new solver

Ouverte
#15,908 1 commentaire 0 réactions 0 personnes assignées Voir sur GitHub

Personne n'a encore pris cette issue.

Évaluation

Difficulté
5/5
Temps estimé
Plus d'une semaine
Accessibilité débutants
20/100
Type d'issue
Fonctionnalité
Clarté
À clarifier
Activité
À l'abandon
Stack technique
python
Domaine
compilers, devtools

Piste de recherche

Commencez par lire l’issue #15906 et la série de suivi dans la pull request #15287 afin de comprendre les changements du solver déjà en cours. Examinez ensuite l’exemple de contrainte de variable de type présenté dans cette issue et déterminez comment cadrer une expérimentation de backtracking. La tâche serait considérée comme terminée lorsqu’un design convenu et des éléments sur les échecs d’inférence ainsi que sur le comportement dans le pire des cas seraient disponibles.

Rédigé par le modèle d'indexation à partir du texte de l'issue.

Description

feature priority-1-normal topic-type-variables

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

Langage dominant
Python
Étoiles
20.6k
Forks
3.3k
Merge moyen
1 j 18 h
PR mergées (30 j)
54

Guide de contribution

Ouvrir le guide de contribution

Par où commencer

  1. Lisez l'issue en entier, puis le guide de contribution du projet.
  2. Signalez en commentaire que vous la prenez — cela évite que deux personnes fassent le même travail.
  3. Forkez le dépôt et travaillez sur une branche.
  4. Ouvrez une pull request qui référence le numéro de l'issue.

Autres issues de python/mypy

Toutes les issues de python/mypy

Issues similaires

Plus d'issues Python

Recevez les nouvelles issues par e-mail

Un résumé court des issues GitHub adaptées aux débutants.