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

[gnprice]

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.

[JukkaL]

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

[JukkaL]

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

[gvanrossum]

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?

[JukkaL]

Sounds good to me.

[rwbarton]

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.)

[gvanrossum]

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

[rwbarton]

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.