Skip to content
CryoCryo home
LanguageAbstraction

11Generics

Generics let you write code once and have the compiler specialise it for each concrete type used. The model is monomorphisation: at compile time, every distinct instantiation produces a dedicated copy of the code. There is no boxing, no vtable, and no runtime type information.

11.1 Type Parameters

Type parameters are declared in angle brackets after the name. By convention they use single uppercase letters: T for a general type, E for an error type, K and V for key / value, A for an allocator.

11.2 Generic Structs

import std::core::ptr;
import std::core::intrinsics::{ malloc, free };

type struct Box<T> {
    ptr: T*;

    static new(value: T) -> Box<T> {
        const p: T* = malloc(sizeof(T)) as T*;
        *p = value;
        return Box { ptr: p };
    }

    get(&this) -> &T {
        return &*this.ptr;
    }
}

// The destructor. Only an `implement trait Drop` defines one; a method that is
// merely named `drop` in the struct body would be an ordinary method.
implement<T> trait Drop for Box<T> {
    drop(mut &this) -> void {
        ptr::drop_in_place::<T>(this.ptr);   // release the boxed value
        free(this.ptr as void*);             // then its storage
    }
}

A struct can have multiple type parameters, and a parameter can have a default. The standard library uses defaults extensively to make the common case ergonomic:

type struct Array<T, A = GlobalAlloc> { /* ... */ }
type struct HashMap<K, V, A = GlobalAlloc> { /* ... */ }

Calling Array::<int>::new() uses GlobalAlloc; calling Array::<int, Arena>::new_in(my_arena) parameterises the container over a custom allocator.

A written type takes at most as many type arguments as its declaration has parameters, and at least as many as it has parameters without a default: with type struct Box<T>, Box<i32, i64> is refused where it is written (E0307, "Box has 1 type parameter, and 2 type arguments are written"), and so is Pair<i32> for type struct Pair<A, B>. An enum and a generic alias are counted the same way. A call writing more type arguments on a method than the method has type parameters of its own is refused the same way, s.pick::<i32, u8>(4) for pick<T>.

A default resolves in the module where the type is declared, not at the use site: writing Array<int> fills in GlobalAlloc as collections::array's own scope sees it, so the user never imports GlobalAlloc to use the default. A user who writes Array<int, GlobalAlloc> names GlobalAlloc themselves and needs it in scope, because they wrote it. This is the general rule - a name resolves in the scope where it is written - and it is also why a function body, a type alias's right-hand side and an implement body resolve where they are written. A name that exists nowhere is an error in every position, expression and type-argument positions included: sizeof(Nope), 1 as Nope and Array<Nope> are refused, not silently accepted.

A default fills a parameter that a use leaves out. An implement head is not a use: it names every parameter of the template it is written for, either as parameters of its own or as a concrete instantiation, and a head that leaves one out is an error (E0302), whether every parameter has a default or only the trailing ones do. implement trait Display for String would read as an impl for every String<A> while binding only String<GlobalAlloc>, so the writer says which is meant:

implement<A> trait Display for String<A> { /* ... */ }        // every String<A>
implement trait Display for String<GlobalAlloc> { /* ... */ }  // this instantiation
implement<T, A> trait Clone for Array<T, A> { /* ... */ }      // not `Array<T>`

An inherent block declares its parameters in the same list that names them, so implement enum Option<T> { /* ... */ } is the one spelling for Option<T>.

A trait head declares its parameters in the leading list. A name in the trailing list that is declared nowhere is the same error (E0302), with the head spelled as it must be written: implement trait Atomic<T> for Cell<T> with no T declared is refused, and implement<T> trait Atomic<T> for Cell<T> is the head it meant.

11.3 Generic Enums

type enum Result<T, E> {
    Ok(T);
    Err(E);
}

Each Result<T, E> instantiation is a distinct compile-time type.

11.4 Generic Functions

function identity<T>(x: T) -> T {
    return x;
}

const n: int = identity::<int>(42);

11.5 Generic Implement Blocks

When you add methods to a generic type via implement, the block itself is generic. Methods may introduce additional type parameters:

implement enum Result<T, E> {
    is_ok(&this) -> boolean {
        match (this) {
            Result::Ok(_)  => { return true;  }
            Result::Err(_) => { return false; }
        }
    }

    map<U>(&this, op: (T) -> U) -> Result<U, E> {
        match (this) {
            Result::Ok(value) => { return Result::Ok(op(value)); }
            Result::Err(err)  => { return Result::Err(err);      }
        }
    }
}

Result's parameters <T, E> are fixed by the type; map introduces an additional <U>.

Naming the enclosing type. Inside an implement block (a trait's included) or a type body, generic or not, This is the enclosing type with its own parameters as arguments, so This::of(..) in implement struct Pair<T> means Pair<T>::of(..), and a parameter typed &This there is &Pair<T>: on a Pair<i32> it takes a &Pair<i32>. A generic type's bare name written there without arguments, Pair::of(..), infers its arguments from the call:

type struct Pair<T> { a: T; b: T; }

implement struct Pair<T> {
    static of(a: T, b: T) -> Pair<T> { return Pair { a: a, b: b }; }

    swapped(&this) -> Pair<T> where T: Copy { return This::of(this.b, this.a); }   // the enclosing Pair<T>
    copy(&this)    -> Pair<T> where T: Copy { return Pair::of(this.a, this.b); }   // arguments inferred from the call
}

In a trait's own declaration This is whichever type implements the trait. This::member in a default body names the trait's member, typed by the trait's declaration of it, and each implementation's copy of the default calls that implementation's member, its own or the trait's default:

type trait Seven {
    static base() -> i64;
    static build_default() -> i64 { return This::base() + 1; }   // the implementor's base()
}

A parameter a method introduces must not spell one its owner already declares: map<T> inside Result<T, E> is refused at the method's T (E0311), as is a second T in one list, a trait method's <T> inside trait Conv<T>, and an impl method's <T> inside implement<T>. An enclosing generic parameter is in scope for every declaration nested in its owner, so an inner one of the same name could only be that parameter again - there is nothing for the inner declaration to mean. A method's parameter that shadows a type of the same spelling, or a value parameter spelled like a generic one, is ordinary shadowing and is allowed.

11.6 Monomorphisation

When the compiler sees:

const a: Pair<int>    = Pair::<int>::new(1, 2);
const b: Pair<string> = Pair::<string>::new("x", "y");

it generates two independent types and two specialised function bodies, one for each instantiation. There is no shared dispatch; every call is a direct call to a fully-typed function. The trade-off is binary size: each instantiation produces its own code.

Generic bodies are type-checked once, as templates, before monomorphisation: a body is checked against its parameters' bounds, never against the types it is later instantiated with, so an error in a generic body is reported whether or not anything instantiates it. One exception: a path through a type parameter naming a member none of its bounds declares (T::m(), T::m, (Tr for T)::m) is found by that check and reported only once the body is instantiated (section on calls through a bound). Monomorphisation then copies each instantiated body with its type arguments substituted and binds every call in the copy to its concrete callee; the copies are not type-checked again, so a call the template check accepts must be one every copy can bind. A method call on the body's own instantiation of a generic type (xs.get(i) with xs: &Array<T>) is therefore refused where it is written when its arguments bind to no method of the name, by the rule a call's arguments bind by - an i64 passed for get's u64 index is refused (E0214), as is an overload set none of whose members takes the arguments. The driver lives in compiler/src/compiler/mono/ (monomorphizer.cryo), run from instance.cryo after the function-body type check.

11.7 static match — Compile-Time Type Dispatch

static match selects a body by inspecting a type parameter at compile time. It is the mechanism that lets one generic function accept several unrelated types without a trait bound and without runtime dispatch.

static match (T) {
    u8      => { this.write_u8(value); }
    i8      => { this.write_u8(value as u8); }
    boolean => { this.write_u8(if (value) { 1 as u8 } else { 0 as u8 }); }
}

The subject is a type, not a value, and each arm is a type rather than a pattern. During monomorphisation the compiler knows what T is, keeps the one matching arm, and discards the rest — so there is no branch and no runtime cost in the emitted code. Every arm is still type-checked first, on the generic body (see below).

Arms may group types with |, and _ is the wildcard:

static match (T) {
    u8 | u16 | u32 | u64 => { this.push_display(item) }
    string               => { this.push_view_bytes(Str::from(item)) }
    _                    => { core::unreachable(); }
}

Omitting _ makes the arm list the accepted-type list. A T that matches no arm is a compile error. This is deliberate and is how the standard library expresses "this generic accepts exactly these types" without inventing a trait:

// `String::try_push` accepts strings, integers, floats and boolean.
// Any other T is rejected at compile time - there is no `_` arm.
try_push<T>(mut &this, item: T) -> Result<(), AllocError> {
    return static match (T) {
        String  => { this.push_view_bytes(item.as_str()) }
        Str     => { this.push_view_bytes(item) }
        string  => { this.push_view_bytes(Str::from(item)) }
        u8 | u16 | u32 | u64 |
        i8 | i16 | i32 | i64 |
        f32 | f64 |
        boolean => { this.push_display(item) }
    };
}

Statement and expression position both work. As an expression, every arm's body yields the value of its final expression, and all arms must agree on a type — as in the try_push example above, where each arm yields Result<(), AllocError>.

Every arm is checked, each against its own type. The arms are type-checked on the generic body, before monomorphisation, so a broken arm is an error even if no instantiation selects it:

  • A single-type arm narrows T to that type inside the arm: in String => { ... }, item is a String, so item.as_str() is fine.
  • A multi-type arm (u8 | u16 | u32 | u64 => ...) is checked once for each listed type, and must be valid for all of them.
  • The wildcard arm _ knows only T's declared bounds, like ordinary generic code: a method, operator or field its bounds do not give is refused (E0358, E0229, E0204).
function show<T>(x: T) -> i32 {
    return static match (T) {
        string    => { x.length() as i32 }   // `x: string` here
        i32 | i64 => { x as i32 }            // checked as i32, then as i64
        _         => { 0 }                   // only `T`'s bounds; `x.length()` here would be E0358
    };
}

This is what makes the construct useful: an arm may use operations valid only for its own type, without every arm having to compile for every T.

The subject may be any type parameter in scope — the enclosing type's parameter, or one introduced by the method itself:

type struct Atomic<T> {
    // `T` here comes from the type.
    load(&this) -> T { return static match (T) { /* ... */ }; }
}

implement struct String<A> {
    // `T` here is introduced by the method.
    push<T>(mut &this, item: T) -> void { /* static match (T) ... */ }
}

static match is also permitted in a trait's default method body, which is what lets io::Write::write<T> dispatch on the payload type without each implementor restating the arms.

When to reach for it. Prefer a trait bound when the operation is genuinely the same across types and the set is open. Reach for static match when the set of accepted types is closed and each one needs different code — width-specific integer handling, or a conversion whose implementation differs per source type. The standard library uses it for Hash::fold, String::push/try_push, Str::from, Atomic<T>, and io::Write::write.