[red-knot] Implement Homogeneous Tuple Type

[cake-monotone]

As Type::Tuple is becoming more actively used in implementations, I think we should implement Homogeneous Tuples before the refactoring cost becomes too high.

I’m considering an implementation like the following using an enum:

#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
pub enum TupleType<'db> {
    Heterogeneous(HeterogeneousTupleType<'db>),
    Homogeneous(HomogeneousTupleType<'db>),
}

#[salsa::interned]
pub struct HeterogeneousTupleType<'db> {
    elements: Box<[Type<'db>]>,
}

#[salsa::interned]
pub struct HomogeneousTupleType<'db> {
    element: Type<'db>,
}

Expected Issues

Currently, it seems that there is no way to assign a homogeneous tuple type in the tests.

Do you have any suggestions for a proper way to handle this? Or should we wait for another feature to be merged first?

[AlexWaygood]

Thanks for opening this issue!

I think homogenous tuples will require much less special-casing from us than heterogenous tuples (thankfully!). Whereas heterogenous tuples need to be extensively special-cased in red-knot, homogenous tuples are pretty similar to most other generic sequence types -- I think we should simply be able to fallback to typeshed's annotations for tuple for most simple operations.

We don't yet have any representation of generic types in red-knot at all, however. This is a large outstanding task, and something that I know @carljm plans to work on soon. I think we should probably hold off on implementing anything to do with homogenous tuples until we have an initial implementation of generic types.

We will of course have to have some special handling of homogenous tuples in due course:

• We need to understand where heterogenous tuples are and aren't subtypes of homogenous tuples
• We'll need to understand somewhat terrifying types such as tuple[int, *tuple[str, ...], bytes] which combine heterogenous and homogenous tuples.

But I still expect it to be much more limited than the special casing we've already implemented for heterogenous tuples. And it will possibly be implemented in a completely different way.

[cake-monotone]

Thank you for the detailed answer! I’m leaving a few special cases I had in mind for future consideration:

• tuple[*tuple[str, ...], ...] is invalid.
• tuple[*tuple[int, ...]] should be inferred as tuple[int, ...].

[AlexWaygood]

We'll also need to make sure we understand that tuple[str, *tuple[int, ...]] and tuple[str, typing.Unpack[tuple[int, ...]]] are the same type.

[MichaReiser]

Nit:

 #[salsa::interned]
 pub struct HomogeneousTupleType<'db> {
-     element: Box<Type<'db>>,
+     element: Type<'db>,
 }

[carljm]

It may be that the existing Type::Tuple should be renamed to make it more clear that it represents only heterogeneous tuple types, but I'm hesitant to spend too much time on renamings until we see the full shape of our tuple support.