# const traits model

## NB: syntax in this document

This document defines a large amount of new syntax. This is for the sake of fully defining the underlying model. Only a small portion of the syntax should be stabilized in the near future.

## const vs runtime bounds

### Introduction

Every function item in Rust has two sets of trait bounds: set $R$ determines the requirements for calling the function in a runtime context, and set $C$ for calling it in a const context. Wherever $C$ is satisfied, so is $R$; henceforth we will denote this $C ≥ R$.

In today’s Rust, one of the following is always true: either $C = R$ (`const fn`s), or $C$ is impossible to satisfy (non-`const` `fn`s). Our aim is to change that: to introduce functions where $C > R$, but $C$ is still possible to satisfy.

### Syntax

To indicate this, we attach `where` clauses to the `const` keyword specifically:

(const where T: Bar) fn do_thing<T: Foo>() {}

The function above can be called with any `T: Foo` in a runtime context, but requires `T: Foo + Bar` in a const context.

// The following are effectively equivalent
(const where String: Copy) fn nonconst() {}
fn nonconst() {}

## `const fn` in traits

A trait definition can contain both `const` and non-`const` `fn` items; the `const` keyword on the `const fn`s may or may not carry extra bounds.

trait Trait {
    fn nonconst();
    const fn fullyconst();
    (const where T: Foo) fn sometimesconst<T>();
}

The bounds on the functions in the `impl` cannot be more restrictive than those in the trait definition:

impl Trait for () {
    fn nonconst() {}
    fn fullyconst() {} // Error
    (const where T: Foo + Bar) fn sometimesconst<T>() {} // Error
}

However, they can be *less* restrictive:

impl Trait for () {
    const fn nonconst() {} // OK
    const fn fullyconst() {}
    const fn sometimesconst<T>() {} // OK
}

## `: const` bounds

Consider the (simplifed) `Add` trait:

pub trait Add {
    fn add(self, rhs: Self) -> Self;
}

Some types can implement this with a `const fn`:

impl Add for i32 {
    const fn add(self, rhs: Self) -> Self {
        // compiler intrinsic
    }
}

But others cannot:

impl Add for BigInt {
    fn add(self, rhs: Self) -> Self {
        // Implementation omitted
    }
}

Consider the following function that uses `Add`:

fn add_twice<T: Add>(a: T, b: T, c: T) -> T {
    a + b + c
}

Let’s say we want to make this function usable in const contexts. To do this, we need some way to write a bound asserting that the `fn add` in `T`’s `add` impl is `const`. We write this `T::add: const`:

(const where T::add: const) fn add_twice<T: Add>(a: T, b: T, c: T) -> T {
    a + b + c
}

The function above requires `T: Add` in order to be called in a runtime context, and additionally needs the `Add` impl to have `const fn add()` in order to be called in a const context.

### What if the function has early-bound generic parameters?

Consider the following trait:

trait Trait {
    fn foo<T>();
}

The following is not legal:

(const where T::foo: const) fn foo<T: Trait, U>() {
             // ^^^ERROR: Missing generics
    T::foo::<U>();
}

This reflects the fact that constness is a boolean property of fully-instantiated functions, but is not boolean with respect to generic `fn` items.

Instead, you should write:

(const where T::foo<U>: const) fn foo<T: Trait, U>() { // OK
    T::foo::<U>();
}

This also works:

(const where for<U> T::foo<U>: const) fn foo<T: Trait>() { // OK
    T::foo::<u32>();
    T::foo::<String>();
}

You can even do this:

(const where for<U: Copy> T::foo<U>: const) fn foo<T: Trait>() { // OK
    T::foo::<u32>();
    T::foo::<char>();
    //T::foo::<String>(); // this call would not be legal
}

## Basic `const Trait`

Returning to our `add` example, `T::add: const` is a little verbose. And if the trait had several methods we wanted to mention, it would get even worse. To alleviate this, we can define a trait alias:

pub trait ConstAdd = Add
where
    Self::add: const;

(const where T: ConstAdd) fn add_twice<T: Add>(a: T, b: T, c: T) -> T {
    a + b + c
}

For convenience, we introduce built-in syntax sugar for this pattern: `const trait`.

pub const trait Add {
    ~const fn add(self, rhs: Self) -> Self;
}

This desugars to an `Add` trait with the same semantics as our original trait, plus a `const Add` alias with the same semantics as `ConstAdd`. The `~const` in `~const fn add` indicates that the `add` function is required to be `const` for the `const Add` alias to be satisfied, but base `Add` does not require it.

(You can think of the `~` in `~const` as being a “string” that “ties” the constness of the function to that of the outer trait.)

Now, we can rewrite our `add_twice` like so:

(const where T: const Add) fn add_twice<T: Add>(a: T, b: T, c: T) -> T {
    a + b + c
}

This is still more verbose than we’d like; we will address that in the next section.

### More complicated `const trait` example

This:

const trait Trait {
    fn nonconst(); // Neither `Trait` nor `const Trait` require this to be `const`
    ~const fn maybeconst(); // Only `const Trait` requires this to be `const`
    const fn alwaysconst(); // `Trait` and `const Trait` require this to be `const`
}

Desugars to approximately this:

trait Trait {
    fn nonconst();
    fn maybeconst();
    const fn alwaysconst();
}

// Actually called `const Trait`
trait ConstTrait = Trait
where
    Self::maybeconst: const;

## `~const` bounds on `fn`s

We want to make this less verbose:

(const where T: const Add) fn add_twice<T: Add>(a: T, b: T, c: T) -> T {
    a + b + c
}

To do so, we rewrite it as:

const fn add_twice<T: ~const Add>(a: T, b: T, c: T) -> T {
    a + b + c
}

`~const` inside an `fn`’s bounds means “the non-`const` form of the bound is required to call the function at runtime, but the `const` form is required at compile-time”.

Again, the `~` serves to “tie” the two `const` keywords together. Just as the constness of a `const Trait` is dependent on the constness of its `~const fn`s,
the constness of a `const fn` is dependent on its `~const` bounds.

`~const` also works with method `const` bounds:

// These two `fn`s are exactly equivalent

const fn add_twice<T: Add>(a: T, b: T, c: T) -> T
where 
    T::add: ~const,
{
    a + b + c
}

(const where T::add: const) fn add_twice<T: Add>(a: T, b: T, c: T) -> T {
    a + b + c
}

## Advanced `const Trait`

### `~const` method defaults

Consider the (simplified) `PartialEq` trait:

pub trait PartialEq {
    fn eq(&self, other: &Self) -> bool;

    fn ne(&self, other: &Self) -> bool {
        !(self.eq(other))
    }
}

We can `const`ify it like so:

pub const trait PartialEq {
    ~const fn eq(&self, other: &Self) -> bool;

    ~const fn ne(&self, other: &Self) -> bool {
        !(self.eq(other))
    }
}

According to the rules we have established so far, this would desugar to approximately:

pub trait PartialEq {
    fn eq(&self, other: &Self) -> bool;

    fn ne(&self, other: &Self) -> bool {
        !(self.eq(other))
    }
}

// Actually called `const PartialEq`
pub trait ConstPartialEq = PartialEq
where
    Self::eq: const,
    Self::ne: const;

But there’s an issue. Let’s try implementing it:

struct Foo(u32);

impl PartialEq for Foo {
    const fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }
}

With the default `ne` impl, this desugars to:

struct Foo(u32);

impl PartialEq for Foo {
    const fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }

    fn ne(&self, other: &Self) -> bool {
        !(self.eq(other))
    }
}

`ne` is not `const fn`, so this `PartialEq` impl is not `const`.

To fix this problem, we make a small change to the rules. We say that, when a `~const fn` inside a trait has a default body, that default is implicitly `const fn` `where Self: ~const Trait` (where `Trait` is the trait containing the `fn` item). So our new `impl` desugaring would be:

struct Foo(u32);

impl PartialEq for Foo {
    const fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }

    const fn ne(&self, other: &Self) -> bool
    where
        Self: ~const PartialEq,
    {
        !(self.eq(other))
    }
}

Which in turn desugars to:

struct Foo(u32);

impl PartialEq for Foo {
    const fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
    }

    (const where Self: const PartialEq) fn ne(&self, other: &Self) -> bool {
        !(self.eq(other))
    }
}

Thanks to coinduction, the `Self: const PartialEq` bound is satisfied, so `ne` is `const fn` and the impl is `const PartialEq`. However, if we were to remove the `const` from `const fn eq()` in the impl, then `Self: const PartialEq` would become unsatisfiable, so `Foo::ne()` would effectively become fully non-`const`.

### `~const` supertraits

Now let’s consider the `Eq` trait. It has no methods:

trait Eq: PartialEq {}

Also consider this `Eq`-using function:

fn is_equal<T: Eq>(a: T, b: T) -> bool {
    a == b
}

To make this function work in `const`, we would write:

const fn is_equal<T: Eq + ~const PartialEq>(a: T, b: T) -> bool {
    a == b
}

This is verbose. We can shorten it by making `Eq` into a `const trait`:

const trait Eq: ~const PartialEq {}

This desugars to approximately:

pub trait Eq: PartialEq {}

// Actually called `const Eq`
pub trait ConstEq = Eq
where
    Self: const PartialEq;

Now, we can write:

const fn is_equal<T: ~const Eq>(a: T, b: T) -> bool {
    a == b
}

### `~const` bounds on `~const fn`s

`~const fn`s can have `~const` bounds.

const trait Trait {
    ~const fn foo<T: ~const Debug>();
}

This desugars to approximately:

trait Trait {
    fn foo<T: Debug>();
}

// Actually called `const Trait`
trait ConstTrait = Trait
where
    for<T: const Debug> Self::foo<T>: const;

### Fully custom `const` bounds

Just like `const fn`s, `const` traits can specify fully custom `where` clauses for their `const`ness.

(const where Self: Foo) trait Bar {
    // ...
}

This desugars to approximately:

trait Bar {
    // ...
}

// Actually called `const Bar`
trait ConstBar = Bar
where
    Self: Foo;

## Asserting `const`ness of an `impl`

To assert that a trait `impl` is `const`, one can write `impl const Trait` instead of `impl Trait`. This asserts that `const Trait` is implemented whenever the `const` versions of all `~const` bounds on the `impl` block are satisfied. Such `impl` blocks can also contain `~const fn`s; functions denoted in this way inherit the `~const` bounds of the impl block.

For example:

struct Wrapper<T>(T);

const trait Trait {
    ~const fn foo(self) -> Self;
}

impl<T: ~const Trait> const Trait for Wrapper<T> {
    ~const fn foo(self) -> Self {
        Self(self.0.foo())
    }
}