I tried to implement Callable[[int, int], str] as ((int, int), str). However, it breaks much of typing's tests and requires recursion to account for the nested tuples, in both typing, and in the C implementation of GenericAlias.

I'd like to humbly propose a less breaking solution: express __args__ of Callable[[int, int], str] as (Tuple[int, int], str). Almost all the current code in the typing library already supports this. As for collections.abc.Callable, its __args__ simply needs to be expressed as (tuple[int, int], str). This is also an easy fix.

Semantically, this makes sense to me too. Both of the above changes will also still allow caching since Tuple[x] is hashable. This will allow us to fix this issue without depending on issue42102, or at least it can be a stop gap measure. If issue42102 has a resolution, the C implementation can just replace the Python one directly.