Experiment with backtracking in the new solver

Aberta
#15,908 1 comentário 0 reações 0 responsáveis Ver no GitHub

Ninguém assumiu esta issue ainda.

Avaliação

Dificuldade
5/5
Tempo estimado
Mais de uma semana
Facilidade para iniciantes
20/100
Tipo de issue
Funcionalidade
Clareza
Precisa de esclarecimento
Status de atividade
Estagnada
Stack de tecnologia
python
Domínio
compilers, devtools

Direção de pesquisa

Comece lendo a issue #15906 e a série de acompanhamento na pull request #15287 para entender as alterações no solver que já estão em andamento. Em seguida, examine o exemplo de restrição de variável de tipo nesta issue e determine como delimitar um experimento de backtracking. Para considerar o trabalho concluído, seria necessário ter um design acordado e evidências sobre falhas de inferência e o comportamento no pior caso.

Escrita pelo modelo de indexação a partir do texto da issue.

Descrição

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

Linguagem predominante
Python
Estrelas
20.6k
Forks
3.3k
Merge médio
1d 18h
PRs com merge (30d)
54

Guia de contribuição

Abrir o guia de contribuição

Primeiros passos

  1. Leia a issue inteira e depois o guia de contribuição do projeto.
  2. Comente na issue dizendo que vai assumir — evita que duas pessoas façam o mesmo trabalho.
  3. Faça um fork do repositório e trabalhe em uma branch.
  4. Abra um pull request que referencie o número da issue.

Mais de python/mypy

Todas as issues de python/mypy

Issues semelhantes

Mais issues de Python

Receba novas issues na sua caixa de entrada

Um resumo curto de issues do GitHub para quem está começando.