Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Generic decorators don't work with generic functions #1317

Closed
alexsydell opened this issue Mar 24, 2016 · 17 comments · Fixed by #15287
Closed

Generic decorators don't work with generic functions #1317

alexsydell opened this issue Mar 24, 2016 · 17 comments · Fixed by #15287
Labels
bug mypy got something wrong topic-type-variables

Comments

@alexsydell
Copy link

alexsydell commented Mar 24, 2016

UPDATE: Although the original example is now special-cased in a plugin, the underlying problem is not solved, see #1317 (comment)

The following:

from typing import *
from contextlib import *

T = TypeVar("T")

@contextmanager
def foo(x):
  # type: (T) -> Iterator[T]
  yield x

y = 1
with foo(2) as f:
  y = f

gives this error:

error: Incompatible types in assignment (expression has type "T", variable has type "int")

It should recognize the input as an int which would lead to the output being an int as well, not a T. This is probably due to the way the contextmanager stub is defined in typeshed.

@gvanrossum
Copy link
Member

Yeah, contextmanager seems to bring out the worst in mypy, because it's a decorator and wraps a generator. :-( Note this comment in contextlib.pyi:

# TODO this doesn't capture the relationship that the returned function's args are the same as func's.
def contextmanager(func: Callable[..., Iterator[_T]]) -> Callable[..., ContextManager[_T]]: ...

Fixing that will probably require some way to describe the relationship between the args of the Callable used to describe contextmanager's 'func' argument and the args of the Callable describing its return type. (Note that the return type of the two Callables are different.)

@JukkaL
Copy link
Collaborator

JukkaL commented Apr 5, 2016

Variadic type variables (python/typing#193) would be useful here, assuming that they could preserve all the details of function argument lists such as keyword argument names. They aren't in PEP 484 and mypy doesn't support them, so they won't help us right now.

Another way to go about this would be to support type checker plugins that can special case the checking of certain library functions. Mypy doesn't support them either, so the current signature is about the best we can do.

@JukkaL JukkaL added the bug mypy got something wrong label Apr 7, 2016
@gvanrossum gvanrossum added this to the 0.3.2 milestone Apr 7, 2016
@rwbarton
Copy link
Contributor

rwbarton commented Apr 8, 2016

Variadic type variables would certainly be the way to go here, but there's actually a latent mypy bug here as well, which you can expose by changing the stub type of contextlib.contextmanager to the type that should make this program type check, namely

def contextmanager(func: Callable[[_T], Iterator[_T]]) -> Callable[[_T], ContextManager[_T]]: ...

Recall that

@contextmanager
def foo(x):
  # type: (T) -> Iterator[T]
  yield x

really means something like

def foo_(x):
  # type: (T) -> Iterator[T]
  yield x
foo = contextmanager(foo_)

foo_ is a generic function with a type variable T, and in the call to the generic function contextmanager we determine that _T = T. But foo does not end up being a generic function in mypy's internal representation. It is just a function whose type involves a type variable T that is not bound anywhere. So the call foo(2) then already fails to type check, since the type of 2 is int and not T.

With the current type of contextmanager, foo gets the type Callable[..., ContextManager[T]], so foo(2) is accepted, but the result type ContextManager[T] still has a nonsensical reference to an unbound type variable.

When inferring the type of the result of a call to a generic function, we need to take care when that type still contains type variables. If the result is a callable, then we should promote it to a generic callable ("generalization"). If the result is not callable, then mypy seems to already give an error message error: Need type annotation for variable, which is sensible.

With such a change, we should almost be able to type check the original program. After all, the more specific type for contextmanager using variadic type variables should only serve to reject ill-typed programs, such as if you passed foo something other than an int.

@rwbarton
Copy link
Contributor

rwbarton commented Apr 8, 2016

("almost be able to type check" because mypy actually refuses to infer a type for f, and AFAIK you cannot specify one (aside from writing a cast on foo(2)). See #1356.)

@rwbarton
Copy link
Contributor

rwbarton commented Apr 8, 2016

Actually, type generalization as I described above is technically unsound. (TODO: Insert realistic example here.) The result of the decorator could be a closure that refers to a mutable variable of a type that depends on the type variables of the closure. What matters for soundness of generalization is whether the value is syntactically defined as a function, not whether it has a function type.

For the purposes of mypy it probably makes most sense not to worry about this point and generalize all values of function type.

@JukkaL
Copy link
Collaborator

JukkaL commented Apr 18, 2016

This may require fixing #603 first, which is not scheduled until 0.4.x. If that's the case, perhaps we should postpone this until 0.4.x?

@gvanrossum
Copy link
Member

Maybe, or we could move #603 up, or we could make both stretch goals for 0.4. It's really up to Reid.

@JukkaL
Copy link
Collaborator

JukkaL commented May 5, 2016

Moved to 0.4.x.

@JukkaL
Copy link
Collaborator

JukkaL commented May 31, 2017

This is still happening, even though mypy now special cases type inference for contextmanager. The signature of foo has a type variable, but it's not treated as a generic function (the type is def (x: T'-1) -> contextlib.GeneratorContextManager[T'-1]).

@gvanrossum
Copy link
Member

Are you saying this is a bug in the plugin for contextmanager?

@ethanhs
Copy link
Collaborator

ethanhs commented Nov 4, 2017

The provided example works on 0.540, so I am closing this.

@ethanhs ethanhs closed this as completed Nov 4, 2017
@ilevkivskyi
Copy link
Member

@ethanhs The underlying issue is still not fixed however:

def transform(f: Callable[..., T]) -> Callable[..., Iterator[T]]:
    ...

def func(x: T) -> T:
    ...

reveal_type(transform(func))  # Revealed type is 'def (*Any, **Any) -> typing.Iterator[T`-1]'

The last line shows that transform(func) is not generic and has an unbound type variable in it. The same happens if one uses transform as a decorator. I think this works for contextmanager because we have a plugin.

I therefore prefer to keep this issue open, since it has the discussion and a possible solution by Reid.

@ilevkivskyi
Copy link
Member

#1515 contains another important example of this bug in stdlib stubs.

@ilevkivskyi
Copy link
Member

#3193 shows another example in stdlib.

@ilevkivskyi
Copy link
Member

Related #1506 and #1507 (I am not sure we need to keep all three open)

@ssbarnea
Copy link
Sponsor Contributor

I think it worth keeping this open until mypy documentation will contain an example on how to use typing with a simple @contextmanager, like one that takes care of chdir maybe?

@JukkaL
Copy link
Collaborator

JukkaL commented Apr 20, 2022

Lowering priority since arguably the most common case is now supported by using ParamSpec:

from typing import Callable, TypeVar, Iterator
from typing_extensions import ParamSpec

T = TypeVar("T")
P = ParamSpec("P")

def transform(f: Callable[P, T]) -> Callable[P, Iterator[T]]:
    ...

def func(x: T) -> T:
    ...

reveal_type(transform(func))  # Revealed type is 'def [T] (x: T`-1) -> typing.Iterator[T`-1]'

ilevkivskyi added a commit that referenced this issue Jun 18, 2023
Fixes #1317
Fixes #5738
Fixes #12919 
(also fixes a `FIX` comment that is more than 10 years old according to
git blame)

Note: although this PR fixes most typical use-cases for type inference
against generic functions, it is intentionally incomplete, and it is
made in a way to limit implications to small scope.

This PR has essentially three components (better infer, better solve,
better apply - all three are needed for this MVP to work):
* A "tiny" change to `constraints.py`: if the actual function is
generic, we unify it with template before inferring constraints. This
prevents leaking generic type variables of actual in the solutions
(which makes no sense), but also introduces new kind of constraints `T
<: F[S]`, where type variables we solve for appear in target type. These
are much harder to solve, but also it is a great opportunity to play
with them to prepare for single bin inference (if we will switch to it
in some form later). Note unifying is not the best solution, but a good
first approximation (see below on what is the best solution).
* New more sophisticated constraint solver in `solve.py`. The full
algorithm is outlined in the docstring for `solve_non_linear()`. It
looks like it should be able to solve arbitrary constraints that don't
(indirectly) contain "F-bounded" things like `T <: list[T]`. Very short
the idea is to compute transitive closure, then organize constraints by
topologically sorted SCCs.
* Polymorphic type argument application in `checkexpr.py`. In cases
where solver identifies there are free variables (e.g. we have just one
constraint `S <: list[T]`, so `T` is free, and solution for `S` is
`list[T]`) it will apply the solutions while creating new generic
functions. For example, if we have a function `def [S, T] (fn:
Callable[[S], T]) -> Callable[[S], T]` applied to a function `def [U]
(x: U) -> U`, this will result in `def [T] (T) -> T` as the return.

I want to put here some thoughts on the last ingredient, since it may be
mysterious, but now it seems to me it is actually a very well defined
procedure. The key point here is thinking about generic functions as
about infinite intersections or infinite overloads. Now reducing these
infinite overloads/intersections to finite ones it is easy to understand
what is actually going on. For example, imagine we live in a world with
just two types `int` and `str`. Now we have two functions:
```python
T = TypeVar("T")
S = TypeVar("S")
U = TypeVar("U")

def dec(fn: Callable[[T], S]) -> Callable[[T], S]: ...
def id(x: U) -> U: ...
```
the first one can be seen as overload over
```
((int) -> int) -> ((int) -> int)  # 1
((int) -> str) -> ((int) -> str)  # 2
((str) -> int) -> ((str) -> int)  # 3
((str) -> str) -> ((str) -> str)  # 4
```
and second as an overload over
```
(int) -> int
(str) -> str
```
Now what happens when I apply `dec(id)`? We need to choose an overload
that matches the argument (this is what we call type inference), but
here is a trick, in this case two overloads of `dec` match the argument
type. So (and btw I think we are missing this for real overloads) we
construct a new overload that returns intersection of matching overloads
`# 1` and `# 4`. So if we generalize this intuition to the general case,
the inference is selection of an (infinite) parametrized subset among
the bigger parameterized set of intersecting types. The only question is
whether resulting infinite intersection is representable in our type
system. For example `forall T. dict[T, T]` can make sense but is not
representable, while `forall T. (T) -> T` is a well defined type. And
finally, there is a very easy way to find whether a type is
representable or not, we are already doing this during semantic
analyzis. I use the same logic (that I used to view as ad-hoc because of
lack of good syntax for callables) to bind type variables in the
inferred type.

OK, so here is the list of missing features, and some comments on them:
1. Instead of unifying the actual with template we should include
actual's variables in variable set we solve for, as explained in
#5738 (comment). Note
however, this will work only together with the next item
2. We need to (iteratively) infer secondary constraints after linear
propagation, e.g. `Sequence[T] <: S <: Sequence[U] => T <: U`
3. Support `ParamSpec` (and probably `TypeVarTuple`). Current support
for applying callables with `ParamSpec` to generics is hacky, and kind
of dead-end. Although `(Callable[P, T]) -> Callable[P, List[T]]` works
when applied to `id`, even a slight variation like `(Callable[P,
List[T]]) -> Callable[P, T]` fails. I think it needs to be re-worked in
the framework I propose (the tests I added are just to be sure I don't
break existing code)
4. Support actual types that are generic in type variables with upper
bounds or values (likely we just need to be careful when propagating
constraints and choosing free variable within an SCC).
5. Add backtracking for upper/lower bound choice. In general, in the
current "Hanoi Tower" inference scheme it is very hard to backtrack, but
in in this specific choice in the new solver, it should be totally
possible to switch from lower to upper bound on a previous step, if we
found no solution (or `<nothing>`/`object`).
6. After we polish it, we can use the new solver in more situations,
e.g. for return type context, and for unification during callable
subtyping.
7. Long term we may want to allow instances to bind type variables, at
least for things like `LRUCache[[x: T], T]`. Btw note that I apply force
expansion to type aliases and callback protocols. Since I can't
transform e.g. `A = Callable[[T], T]` into a generic callable without
getting proper type.
8. We need to figure out a solution for scenarios where non-linear
targets with free variables and constant targets mix without secondary
constraints, like `T <: List[int], T <: List[S]`.

I am planning to address at least majority of the above items, but I
think we should move slowly, since in my experience type inference is
really fragile topic with hard to predict long reaching consequences.
Please play with this PR if you want to and have time, and please
suggest tests to add.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug mypy got something wrong topic-type-variables
Projects
None yet
Development

Successfully merging a pull request may close this issue.

7 participants