Generic, What is the relationship between T and [T]

1

Hierarchy of generics in RUST

Generics in RUST form a hierarchy from general to specific, similar to the base class and subclass relationship in object-oriented programming:

Base level: T: ?Sized The constraint ?Sized indicates all types.

First-level sub-level: Default memory fixed type T; raw pointer type *const T / *mut T; slice type [T]; array type [T; N]; reference type &T / &mut T; trait constraint type T: trait; generic tuple (T, U...); generic composite type struct<T>; enum<T>; union<T> and specific types u8/u16/i8/bool/f32/&str/String...

Second-level sub-level: Assign a specific type to T in the first-level sub-level, such as *const u8; [i32], or specialize T in the first-level sub-level again, such as *const [T]; [*const T]; &(*const T); *const T where T: trait; struct<T: trait>

This hierarchy can be recursively applied. Clearly, methods and traits implemented for base types can be applied to higher-level generic types. For example:

impl<T> Option<T> {...}
impl<T, U> Option<(T, U)> {...}
impl<T: Copy> Option<&T> {...}
impl<T: Default> Option<T> {...}

The above examples are different implementations of methods for different generics of Option in the standard library. They follow the rule from general to specific.

Similar implementations can be demonstrated with the following examples:

impl<T: ?Sized> *const T {...}
impl<T: ?Sized> *const [T] {...}
impl<T: ?Sized> *mut T {...}
impl<T: ?Sized> *mut [T] {...}
impl<T> [T] {...}
impl<T, const N: usize> [T; N] {...}
impl AsRef<[u8]> for str {...}
impl AsRef<str> for str {...}

Regarding the generic type T mentioned above, I have a question. If the first T represents all types, does this include [T]? In other words, is the type [i32] considered part of T or [T], or both?

2

It's both.

  • If T is i32, then [T] is [i32].

  • If T is [i32], then T is (obviously) [i32], and [T] is [[i32]].

3

Rust doesn’t automatically flatten types, so generic arguments substitute almost like copy’n’paste of the type names. Types like &&Option<Option<Option< &&&&u32>>> are possible.

One quirk is that some types are unsized, and their size information is stored in their pointer, not the type’s value, and that affects nesting of types a little. For example [T] is unsized, so it needs a fat pointer, and Box<[T]> will be a fat pointer because it holds [T] without indirection, so the length won’t be stored in the box.

5 Likes
4

It's quite common a source of confusion (or perhaps a learning opportunity) especially to people new to Rust that a with a generic <T> parameter, the type T does not need to be an “owned type”, but can actually also be something of the form &mut U, or &U.

The same applies to [U], too, in princple, but not quite as generally. The reason is the Sized-ness of types.

If your question is comparing T and [T] for the same set of types T, then there’s no overlap: The type [T] requires that T: Sized, however [T] is not a Sized type. However if you compare T in a <T: ?Sized> context with T in a <T> (i.e. implicitly <T: Sized>) context, then there is overlap.

Note that the name “T” isn’t special. It’s a common name for type parameters, but it’s the fact that it’s a type parameter introduced by some <T> syntax[1] that really gives it meaning, together with the accompanying trait bounds, if any. The meaning would be the same if you used X introduced by <X> syntax, or FooBar introduced by <FooBar> syntax.

So let me try to give a concrete answer

The answer is: those impl blocks with just T will not include types like T == [i32], but those with T: ?Sized do.

So:

impl<T: ?Sized> *const T {...}

this includes *const [i32]

impl<T: ?Sized> *const [T] {...}

this impl is illegal because [T] requires T: Sized. But without the : ?Sized, then T == [i32] is not included but T == i32 gives rise to an impl on *const [i32], so there you have a “[i32]”.

Similarly

impl<T: ?Sized> *mut T {...}

includes *mut [i32] and

impl<T: ?Sized> *mut [T] {...}

is illegal because [T] requires T: Sized. But without the : ?Sized, then T == [i32] is not included but T == i32 gives rise to an impl on *mut [i32].

impl<T> [T] {...}

includes the case [i32] via T == i32

impl<T, const N: usize> [T; N] {...}

doesn't include anything with [i32] because [T; N] requires T: Sized. But it does include [i32; N] via T == i32, which is a type related to [i32] via unsizing coercion

  1. in places such as impl<…here> or trait Name<…here>/struct Name<…here>/enun Name<…here> or in fn name<…here…> in declarations ↩︎

5 Likes
5

One minor addition to make: [[i32]] is in fact a "real" type, despite being ill-formed and an error to use. You can without an error mention the type in a type alias (e.g. type Illegal = [[i32]];), and you can even mention it as the base of a type projection (e.g. <[[i32]] as Trait>::AssociatedType), although the latter is probably a bug.

3 Likes
6

IMO it’s best to think of the compiler accepting type Illegal = [[i32]]; as a delayed type error[1], and the compiler accepting <[[i32]] as Trait>::AssociatedType as a bug.

So @Rgoogle: For all practical purposes, especially from a language learner’s perspective, it should be very clear that “[[i32]]” is not a real type, and doesn’t have any real meaning beyond being “something that will produce a compilation error”.

I generally do like the “well, technically…” remarks myself, but in this topic, it would probably only cause confusion to discuss the meaning of “[[i32]]” any further than “doesn’t exist”/“compilation error”.

  1. not entirely unlike macro_rules! illegal { () => { [[i32]] } } which works, too, of course, until you really use illegal!() as a type somewhere ↩︎

1 Like
7

One fun and practical way to demonstrate this, by the way, is with Rust’s own overlap detection for trait implementations.[1]

No overlap with just <T>

trait MyTrait {}

impl<T> MyTrait for T {}
impl<T> MyTrait for [T] {}

Rust Playground

Overlap, and thus compilation error, with <T: ?Sized> instead:

trait MyTrait {}

impl<T: ?Sized> MyTrait for T {}
impl<T> MyTrait for [T] {}

Rust Playground

error[E0119]: conflicting implementations of trait `MyTrait` for type `[_]`
 --> src/lib.rs:4:1
  |
3 | impl<T: ?Sized> MyTrait for T {}
  | ----------------------------- first implementation here
4 | impl<T> MyTrait for [T] {}
  | ^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `[_]`

For more information about this error, try `rustc --explain E0119`.

  1. Note that the overlap detection is not perfect, and additionally also very conservative around semver concerns of the “upstream crates might add such-and-such impl in the future” kind, so this approach doesn’t work in general to figure out if there’s actually, relistically ever overlap, in cases where overlap is detected. ↩︎

2 Likes
8

4 posts were split to a new topic: Does a type like [[i32]] need to be forbidden?

9

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.