Feature: Recursive Types

[nathanielsimard]

Why

It is impossible right now to have an array of cmma matrix fragments, which is necessary to implement some optimizations. It's also quite constraining in general.

How

We should create the concept of CubeTypeId and add them to the CubeContext. Right now Item is mostly used as type id, but this is wrong. In the context, we should have a map of CubeTypeId => CubeTypeKind, where CubeTypeKind is a new enum listing all possible types:

pub enum CubeTypeKind {
   Line {
      kind: CubeTypeId,
      size: u32,
   },
   Array {
       kind: CubeTypeId,
       size: u32,
   }
   Elem(ElemKind)
}

The goal is the this will be easy to build up during expansion. But we would also need a recursive enum type for each compiler, so that it's easy to format.

pub enum CppCubeTypeKind {
   Line {
      kind: Box<CppCubeTypeKind>,
      size: u32,
   },
   Array {
       kind: Box<CppCubeTypeKind>,
       size: u32,
   }
   Elem(CppElemKind)
}

With that, it would be easy to implement Array<Matrix<C, 16, 16, 16, Accumulator>>>, which is necessary for double buffering.

Why a Type ID, vs directly in the Variable ?

Currently Variable implements Clone & Copy which makes it easier to work with. But it also means that we can't extend the enum to become resursive, since Box doesn't implement Copy. Also Variable could probably be simplified in that case only having an id and a type id.

[maxtremblay]

The length of an array is not part of the type (we have Array<T> instead of Array<T, const N: u32>). Thus, we need a way to query during comptime the information required to allocate a child type of an array. That is, given Array<Array<T>>, it is not clear that all child arrays should have the same size from the type signature, but it is a requirement to allocate memory properly.

One solution is to add the length of the array to the type: Array<T> ->Array<T, const N: u32>. However, this remove some comptime functionalities such as

// This is currently possible in a kernel
let array = Array::<T>::new(COMPTIME_VALUE);

// This is impossible as COMPTIME_VALUE is, in fact, a runtime value for rust.
let array = Array::<T, COMPTIME_VALUE)::new();

Also, it is unclear to me what are the implication in function signatures of

#[cube]
fn do_something<T, const N: u32>(data: Array<T, N>) { }

[maxtremblay]

Also, what about

Array<(Line<S>, Line<T>)>

For example, in ArgMax I could want to use

type Accumulator = Array<(Line<Float>, Line<u32>)>;

Is it something we should support?