Fix handling of type variables to prevent confusion across different functions/classes

@JukkaL

Currently type variables are identified by two namespaces "function" and "class" and a small numeric index, with the numbering starting from 1 in each new function and class. Which function or which class a given type variable refers to is implicit in where the type variable comes from in a given section of code in the type-checker. This leads to a number of bugs (TODO: link some of them here.)

@JukkaL suggests instead identifying each type variable by a fresh ID number distinct from all others, which is common practice in other type-inference engines.

Renamed Refactoring -> Fix in the title as this is will change behavior.

Should we move this to an earlier milestone? (I'll add more details soon.)

Yeah, I think this one is important and should be given priority. Maybe we should just move it into 0.3.2 and move anything that's a cleanup or refactoring out of there and into 0.3.3?

Sounds good to me.

Using distinct ids for unrelated type variables would certainly lead to less confusion (both for the human and mypy). Though there are still subtleties: if f is a generic function and I have a call like f(f(...)), I need to be able to distinguish the type variables of the outer application f from those of the inner application of f. (Imagine f has a type like (A) -> List[A].)

One thing to watch out for is nondeterminism of generated ids. Even if ids are just allocated as sequential integers, it's easy in practice for the results to be affected by minor details, such as the order of type checking modules, This might be exposed to the user in two ways:

If the ids ever appear in error messages (not sure whether they do currently), the error messages will be nondeterministic. This is mostly only a problem for the test suite and can be handled by some normalization of error messages before comparison to the expected output.
I assume the implementation of incremental type checking involves some kind of "interface files" containing type information for modules that have already been processed. If those modules contain generic functions then the interface files will have to refer to those variables, and if they do so by the allocated id then the exact contents of the interface file become nondeterministic. This might become an issue in some situations. (I haven't looked at the implementation of incremental type checking yet, so I don't know whether it makes any assumptions about determinism of type checking.)

Reid: if you get to this, great. If not, we can push it to a later milestone.

I took a stab at this but encountered a number of minor bugs that are masked by the way that mypy currently reuses type variable ids, so I'm going to move this to the next milestone. For my records, here are the issues I encountered (maybe some deserve their own issues in the tracker):

Subtype checking for generic functions with type variables with value restriction doesn't work correctly, since apply_generic_arguments won't allow a type variable with value restriction to be instantiated with itself (it's not one of the legal values!)
When checking method compatibility in various contexts (method overrides in subclasses, __add__ vs. __radd__ or __iadd__, function overloads) we sometimes check whether two (argument or result) types are the same, which for type variables means whether they have the same id. For example (from stdlib/3/builtins.pyi)
```
@overload
def reversed(object: Reversible[_T]) -> Iterator[_T]: ...
@overload
def reversed(object: Sequence[_T]) -> Iterator[_T]: ...
```
These are currently considered to be safely overlapping because they have the "same return type" Iterator[_T] where _T is the first (only) type variable of each overload. However, this logic is wrong. If the argument type of the first overload is changed to, say, Sequence[Tuple[_T, int]], then it becomes overlapping with the second with different return types, since the second can be specialized by replacing _T by Tuple[_T, int].

In these situations it generally seems to be correct to apply unify_generic_callables before comparing argument and result types, as happens already in is_callable_subtype.
In lib-python/3.2/fnmatch.py function filter, something funny happens at the line
```
  match = _compile_pattern(pat, isinstance(pat, bytes))
```
Here _compile_pattern is defined as
```
@functools.lru_cache(maxsize=250)
def _compile_pattern(pat: AnyStr,
                 is_bytes: bool = False) -> Callable[[AnyStr],
                                                     Match[AnyStr]]:
[...]
```
Because of the issue I mentioned in the comments of Generic decorators don't work with generic functions #1317, _compile_pattern ends up with a non-generic type that involves the type variable AnyStr, and therefore so does the local variable match. But filter is also a generic function with an AnyStr type variable, so (because the type variable ids are both -1) somewhere in the course of type checking filter the type variable of match gets expanded to the value of the type variable of filter, which isn't necessarily correct but unsurprisingly is in this case in practice. I expect this to be fixed by fixing Generic decorators don't work with generic functions #1317.

Allow any more general type for override of a method (#1524)

Refactoring: construct TypeVarType from TypeVarDef

Improve type checking of generic function bodies (#1580)

I partially did this in #1580: that commit generates fresh IDs for unification variables during type inference, which live in their own type variable ID "namespace". Type variables of generic classes and functions are still allocated using the same old scheme (positive for classes, negative for functions). This fixed the known issues that are a direct result of type variable ID confusion.

I still think allocating unique IDs for all type variables is probably a good idea that may be helpful for some type inference engine improvements in the future. However, there's actually a fair amount of work involved in doing this correctly and so far there hasn't been a concrete reason to do it, so I've put this off.

The major points that would need to be addressed when implementing this are:

The tests. Type variable IDs are sometimes displayed in error messages, and certainly printed by the typexport tests. If we assign a unique ID to every type variable of every function, the IDs will necessarily become sensitive to things like the exact contents of stubs, the order of type checking, etc. That means that the test output checker needs to be robust to changes in the IDs. On the other hand, the IDs also contain information to the extent of whether or not two IDs that appear in output are equal, so the test output checker should not entirely ignore IDs, but instead make sure that two IDs are equal in the actual output exactly when the corresponding IDs are equal in the expected output. (Furthermore, a large number of test cases will need to have their outputs adjusted since the old IDs were very much not unique.)
Interaction with incremental checking. Type variable IDs are written to incremental data files, for example in the types of generic functions and their arguments. The incremental data file format does not have a clear notion of scoping for these variables (for example a type variable may appear in the type of a function before it appears in list of type variables of that function). But it's reasonable to assume that the scope of the variables is the entire file.

When reading in the incremental data files, we need to make sure that type variables from different files end up with different IDs internally, even if they have the same physical ID numbers in the two files (we cannot ensure that that will not happen), while mapping a given file's IDs to new IDs consistently. This is awkward to do from the deserialize method, which has no access to any state. Instead we'd have to deserialize into a temporary "raw"/"unbound" type variable ID that gets converted to the final, fresh ID during fixup.

(Adding the Incremental label to flag this as of potential interest -- however I don't think there's an incremental action item unless we decide to proceed with the full fix here.)

Removing the Incremental label, I don't think it's relevant.

Greg's original post just says that this causes "a number of bugs", but there are no specifics and I don't recall any from the five years since this issue was last touched. Closing as obsolete.

Navigation Menu

Repository navigation

Fix handling of type variables to prevent confusion across different functions/classes #1261

10 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Fix handling of type variables to prevent confusion across different functions/classes #1261

Description

Activity

JukkaL commented on Mar 2, 2016

JukkaL commented on Mar 17, 2016

gvanrossum commented on Mar 17, 2016

JukkaL commented on Mar 17, 2016

rwbarton commented on Apr 6, 2016

gvanrossum commented on Apr 14, 2016

rwbarton commented on May 1, 2016

10 remaining items

rwbarton commented on Jul 1, 2016

gvanrossum commented on Jul 1, 2016

gvanrossum commented on Oct 17, 2016

JelleZijlstra commented on Mar 19, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions