Formality model

This section defines a formal model. This is not a proposal for syntax to be added to the Rust language. It allows us to talk uniformly about what is happening. It is intended to cover a superset of functionality we might someday want.

We define an effect E as a set of runtime and associated effects <T as Trait>::Effect:

E = panic
  | loop
  | runtime
  | await
  | throw<T>
  | yield<T>
  | <P0 as Trait<P1...>>::Effect
  | union(E0, ...., En)

Rust "keywords" and funtion declarations can be translated to sets of these primitive effects:

a const fn can have the effects union(panic, loop)
a fn can have the union(panic, loop, runtime) (we also call this set of effects "default")
an async fn can have the effects union(await, default)
a gen fn, if we had that, would have the effect union(yield<T>, default)

Traits are extended with the ability to define associated effects, declared with do Effect:

#![allow(unused)]
fn main() {
trait Foo {
    do Effect;
}
}

Trait references can bound an associated effect by writing

#![allow(unused)]
fn main() {
T: Foo<Effect: E>
}

which means "the associated effect Effect is a subset of E".

Functions and methods can be declared with a set of effects, written (for now) after the do keyword:

#![allow(unused)]
fn main() {
fn foo<T: Default>()
do
    runtime,
{
    ...
}
}

The effect checker enforces:

if the function body does something that is known not to be const compatible, it must have runtime effect;
when the function calls functions etc., it must have a known superset of their effects declared.

"Marker" effects vs "codegen" effects

In the space of effects we can separate out two categories.

Marker effects do not require changes to the compiler codegen. They indicate actions that are or are not allowed. Examples include runtime, panic, and loop.
Codegen effects require changes to the compiler. An example would be await or throw<T>.

Codegen impacts

When a function is compiled that has the await or yield effects, it is compiled using the coroutine transform. The actual function call returns the coroutine.

When a function is compiled that has the throw<T> effect, it is compiled to return a Result, with the result being Ok-wrapped (we can generalize this with the Try trait if we wish).

When a function is called that has the await or yield effects and the containing function has those effects, the result is either "awaited" or "yield*"'d.

Design axioms

This document outlines the various design axioms that come into play. These are not all mutually satisfiable and not everyone will even agree they are all desirable. That's ok.

The step from a monomorphic `const fn` to one with a generic bound should be minimal

It will be common for people to write something like

#![allow(unused)]
fn main() {
const fn default_wrapper<T: Default>() -> Wrapper<T> {
    Wrapper { value: T::default() }
}
}

and then realize they need T: Default to be a const-enabled bound. We should make the step from what they have to what they need be minimal.

Adding `const` to an item should not be a breaking change

It is very common for people to start with a regular fn and then go to a const fn. It's nice that this is not a breaking change since it is hard to know what should be const up front and easy to overlook. In general, we should strive to have a rule that says: you can make something that was not const into something const and it should not be a breaking change.

`const` and `async` should "feel the same"

They are more similar than they are different -- const lets you work in const blocks, async in async blocks. Users will expect to be able to sprinkle const/async/await in roughly the right places and have things work.

`const` is `const`

When you see const fn (or any other const item), it should mean that you can use the thing in a const block. Not that you can "maybe" use the thing in a const block.

One reason to favor this axiom is if you think about having "must be const" methods in a const trait...

#![allow(unused)]
fn main() {
const trait Foo {
    const fn foo();
    fn bar();
}
}

...the fact that

We will want to have more effects than `const`

We already see the need to have (e.g.) async Fn and const Fn -- and most any trait that could be const could as well be async.

Traits in libstd that becomes a "const trait" will want to be an "async trait" too

We know we want const Default, but why not async Default? And for those where you don't want it (async Sized, for example), it doesn't have to have it be possible to write.

We might never want more complex effects than `const`

It's interesting to think about generalizations of const but it's unclear that we will ever adopt those things. When we experimented with codegen effects we encountered

We will want a "lower floor" than `const`

We already see people requesting panic freedom. It'd be cool if allocation worked in const and yet we know people want to verify allocation freedom. We should be prepared for some way to have functions that do "even less" than const.

You should be able to declare a "maybe const" function without understanding effects

Effects are kind of complex to think about. Regardless of how things work it'd be nice if you declare a "maybe const" function and think about it just in terms of const.

Most traits want to be "all or nothing" (all fns const or no fns const).

There isn't much need to have some functions that are always or never const. If you really need it, you can break up the trait into supertraits.

Twiddle const is where Rust jumps the shark

There is nothing logical about this one, but I'm sorry ~const is just not a step too far into sigil territory.

If we do a general syntax, it should cover all the "quadrants"

We ought to support all the "quadrants"...

methods that are always const
methods that may or may not be const, depending on impl + bounds
methods that are always "maybe const", depending on bounds

Fn items and trait items should mean same thing

If you copy and paste a fn item into a trait, it should (a) work and (b) mean the same thing. If you copy a trait item out to a top-level function, it should either (a) not compile or (b) mean the same thing.

Proposals

Here are examples written in the formality dialect. We'll reference these when discussion the options.

Default trait and impl

Here the model is having the Default trait that is usable in different contexts, e.g., const Default and async Default. There is also an impl of Wrapper<T> and then a function that calls it

#![allow(unused)]
fn main() {
trait Default {
    do DefaultEffect;

    fn default() -> Self
    do
        Self::DefaultEffect;
}

struct Wrapper<T> {
    value: T
}

impl<T> Default for Wrapper<T>
where
    T: Default,
{
    do DefaultEffect = T::DefaultEffect;

    fn default() -> Self
    do
        Self::DefaultEffect
    {
        Wrapper {
            value: T::default()
        }
    }
}

fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: Default,
do
    T::DefaultEffect,
{
    match x {
        None => <Wrapper<T>>::default(),
        Some(v) => v,
    }
}
}

All the things

This ATT trait exercises all the variations.

#![allow(unused)]
fn main() {
trait ATT {
    do Effect;

    fn always_const(&self) -> u32
    do
        const;

    fn maybe_const(&self) -> u32
    do
        (const, <Self as ATT>::Effect);

    fn maybe_maybe_const<T: ATT>(&self) -> u32
    do
        (const, <Self as ATT>::Effect, <T as ATT>::Effect);

    fn always_maybe_const<T: ATT>(&self) -> u32
    do
        (const, <T as ATT>::Effect);
}
}

ATT Impl A

ATT Impl B

rfc-proposal

This is roughly what is described in the RFC.

TL;DR

Traits can be declared as const, in which case all methods are "maybe-const" (depending on the impl)
Impl can decide whether it is implementing const Trait (const or maybe-const methods)

Design axioms

The step from a monomorphic const fn to one with a generic bound should be minimal
- In this proposal, you just add T: ~const Default, which is easy to suggest via compiler error.
Most traits want to be "all or nothing" (all fns const or no fns const).
- Therefore you write const trait Default { fn default() } with no indication on fn default.
Adding const to an item should not be a breaking change
- In this proposal we extend this rule to include changing to const trait Foo and impl const Foo.

Default trait and impl

Equivalent of default trait and impl:

#![allow(unused)]
fn main() {
const trait Default {
    fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> const Default for Wrapper<T>
where
    T: ~const Default,
{
    fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

const fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: ~const Default,
{
    match x {
        None => <Wrapper<T>>::default(),
        Some(v) => v,
    }
}
}

Potential user confusion

If I write this...

#![allow(unused)]
fn main() {
const fn foo() {}
}

I have a function that can be used in or out of a const block. But if I put that const keyword on a generic bound...

#![allow(unused)]
fn main() {
const fn foo<T: const Default>() {

}
}

...I have a function that requires a const impl, which can be surprising (although it makes sense when you think about it, since trait bounds are declaring things that can be used by foo, not things that it does). However, it is backwards compatible to remove the const here. (It's not backwards compatible to add it.)

Generic via bounds

In the "generic via bounds" approach, you declare

direct effects on the function or item (e.g., const fn);
but you have have special bounds that potentially have other effects.

Design axioms

As in the RFC proposal, we wish to ensure

The step from a monomorphic const fn to one with a generic bound should be minimal

but we also believe

We will want to have more effects than const

However, we are not convinced that

Traits in libstd that becomes a "const trait" will want to be an "async trait" too

and therefore we prefer for people to write their trait and impl definitions purely in terms of const. If we do wind up with some more general form we can do that later.

Examples

Using the do keyword

What if...?

You believe that Traits in libstd that becomes a "const trait" will want to be an "async trait" too...?

...then this design area is unappealing. You would in that case want to have the trait declaration for Default not be const trait Default but something more like do trait Default. At that point, if you push it through, you wind up writing do (or whatever...) everywhere except on the const fn, and that is pretty clearly going to be more confusing in the end:

#![allow(unused)]
fn main() {
const trait Default {
    fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> do Default for Wrapper<T>
where
    T: do Default,
{
    do fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

const fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: do Default,
{
    match x {
        None => <Wrapper<T>>::default(), // <-- do we need something here?
        Some(v) => v,
    }
}
}

As you can see in the gvb-do example, it is kind of hard to make this coherent. You wind up with a lot of use of do except for on the fn get_me.

do bounds

TL;DR

Design axioms

Twiddle const is where Rust jumps the shark
- Therefore we use do

Default trait and impl

Equivalent of default trait and impl:

#![allow(unused)]
fn main() {
const trait Default {
    fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> const Default for Wrapper<T>
where
    T: const Default,
{
    const fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

const fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: do Default,
{
    match x {
        None => <Wrapper<T>>::default(), // <-- do we need something here?
        Some(v) => v,
    }
}
}

floor and bounds

const and const?

Summary

Declare the "floor" on the item
- const
- do -- declares default effects
For bounds, declare "maybe" bounds with a ?, e.g., const? or do?
In a trait method, declare "maybe" items with a ? to tie them to the trait mode

Design axioms

Default trait and impl

Equivalent of default trait and impl:

#![allow(unused)]
fn main() {
const trait Default {
    const? fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> const Default for Wrapper<T>
where
    T: const? Default,
{
    const? fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

const fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: const? Default,
{
    match x {
        None => <Wrapper<T>>::default(), // <-- do we need something here?
        Some(v) => v,
    }
}
}

Observations

Pretty confusing that you write const? fn in the trait definition but const fn outside of it

"Everywhere"-style proposals

Summary

Everywhere-style proposals have a keyword that represents "some set of effects". This keyword is used consistently...

on the trait, to indicate that it may contain effect-generic methods
on functions that are generic over effects
in an impl and in trait bounds, to indicate the effects of the methods defined in the trait

Question mark:

When you call a function that is effect-generic, do you need to acknowledge that?

Design axioms

"const and async should feel the same". They are more similar than they are different -- const lets you work in const blocks, async in async blocks. Users will expect to be able to sprinkle const/async/await in roughly the right places and have things work.
- Just as we support trait Foo { async fn foo() } we therefore support trait Foo { const fn foo() }.
const-is-const
- when you say that something is const it means you can use it in a const block
but we want a syntax that COULD be just about const
- just in case we never go further
you should be able to declare a maybe-const function without understanding effects
the most common pattern will be X Trait where all fns become X
every trait in libstd that becomes a "const trait" will want to be an "async trait" too
- and for the rest, it won't hurt them

~const fns, ~const methods

TL;DR

Traits can be declared as const, in which case all methods are "maybe-const" (depending on the impl)
Impl can decide whether it is implementing const Trait (const or maybe-const methods)

Design axioms

Default trait and impl

Equivalent of default trait and impl:

#![allow(unused)]
fn main() {
~const trait Default {
    ~const fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> ~const Default for Wrapper<T>
where
    T: ~const Default,
{
    fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

~const fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: ~const Default,
{
    match x {
        None => <Wrapper<T>>::default(), // <-- do we need something here?
        Some(v) => v,
    }
}
}

do bounds

This is roughly what is described in the RFC.

TL;DR

Design axioms

Default trait and impl

Equivalent of default trait and impl:

#![allow(unused)]
fn main() {
do trait Default {
    do fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> do Default for Wrapper<T>
where
    T: do Default,
{
    do fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

do fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: do Default,
{
    match x {
        None => <Wrapper<T>>::default(), // <-- do we need something here?
        Some(v) => v,
    }
}
}

do bounds

This is roughly what is described in the RFC.

TL;DR

You can think of the do keyword as saying "plus some other effects"
If you write do fn, then, it is "default + some more"
If you write const do

Design axioms

We will want a "lower floor" than const
- ...and therefore we have people write const do fn

Default trait and impl

Equivalent of default trait and impl:

#![allow(unused)]
fn main() {
const do trait Default {
    const do fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> const do Default for Wrapper<T>
where
    T: const do Default,
{
    const do fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

const do fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: const do Default,
{
    match x {
        None => <Wrapper<T>>::default(), // <-- do we need something here?
        Some(v) => v,
    }
}
}

`const+` everywhere

TL;DR

Write const to mean "can only do const things"
Write const+ to mean "can only directly do const things, but may do non-const things via trait bounds"

Design axioms

We will want a lower floor than const eventually
- What we've learned from the ?Sized experience is that it's best to have people "ask for the things they need".
You should be able to declare a maybe-const function without understanding effects.
- Therefore, we prefer a const-keyword-based syntax.

Default trait and impl

Equivalent of default trait and impl:

#![allow(unused)]
fn main() {
const+ trait Default {
    const+ fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> const+ Default for Wrapper<T>
where
    T: const+ Default,
{
    const+ fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

const+ fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: const+ Default,
{
    match x {
        None => <Wrapper<T>>::default(), // <-- do we need something here?
        Some(v) => v,
    }
}
}

`(const)` everywhere

TL;DR

Write const to mean "can only do const things"
Write (const) to mean "can only directly do const things, but may do non-const things via trait bounds"

Design axioms

We will want a lower floor than const eventually
- What we've learned from the ?Sized experience is that it's best to have people "ask for the things they need".
You should be able to declare a maybe-const function without understanding effects.
- Therefore, we prefer a const-keyword-based syntax.

Default trait and impl

Equivalent of default trait and impl:

#![allow(unused)]
fn main() {
(const) trait Default {
    (const) fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> Default for Wrapper<T>
where
    T: (const) Default,
{
    (const) fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

(const) fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: (const) Default,
{
    match x {
        None => <Wrapper<T>>::default(), // <-- do we need something here?
        Some(v) => v,
    }
}
}

Variations

I'm not persuaded by putting the (const) before the keyword trait:

#![allow(unused)]
fn main() {
(const) trait Default {
    (const) fn default() -> Self;
}
}

It seems inconsistent with how the impl works (impl (const) Default) and how bounds work ()T: const Default). I would therefore expect the following:

#![allow(unused)]
fn main() {
trait (const) Default {
    (const) fn default() -> Self;
}
}

Question though, what does it mean to write (const) anyway? It indicates the "floor" for default functions? But that is indicated on a per-function basis.

Another option is to just say that the trait is "generic over const" if it has methods that are; that has a downside in that it rules out the ability to have a trait that has "just" a (const) fn method:

#![allow(unused)]
fn main() {
trait Default {
    (const) fn foo<T: (const) Debug>() -> Self;
}
}

All of this makes me wonder if we can come up with a syntax for more explicitly "tying" things together, but I'm not sure what it would be. For example (trait) or (fn) or even const(if trait)...? Or T: (fn) Debug, which would mean "add this to the effects of the function"...?

"Quadrant"

quadrant `(const)`

TL;DR

To declare a functon with a "conditionally const" bound, you write (const) Default

#![allow(unused)]
fn main() {
const fn get<T: (const) Default> {...}
}

To declare a functon with an "always const" bound, you write const Default

#![allow(unused)]
fn main() {
const fn get<T: const Default> {
    const { T::default() }
}
}

To declare a trait with a method that is "conditionally const" depending on the impl:

#![allow(unused)]
fn main() {
trait Default {
    (const) fn default() -> Self;
}
}

To implement the trait with an impl that is always const:

#![allow(unused)]
fn main() {
impl Default for i32 {
    const fn default() -> i32 {
        0
    }
}
}

To implement the trait with an impl that is never const:

#![allow(unused)]
fn main() {
impl<T> Default for Box<T>
where
    T: Default,
{
    fn default() -> Self {
        Box::new(T::default())
    }
}
}

To implement the trait with a "conditionally const" impl:

#![allow(unused)]
fn main() {
impl<T> Default for [T; 1]
where
    T: (const) Default,
{
    (const) fn default() -> Self { // (*)
        [T::default()]
    }

    // (*) it is possible this should be `const`, we can decide,
    // I'm not sure yet which I like better.
}
}

The model also supports

"always-const" methods
"always-maybe-const" methods

see below.

Design axioms

Due to satisfying the last axiom, this design is compatible with either

We might never want more complex effects than const

Default trait and impl

Equivalent of default trait and impl:

#![allow(unused)]
fn main() {
trait Default {
    // Declare the item as conditionally const (depending on the impl):
    (const) fn default() -> Self;
}

struct Wrapper<T> {
    value: T
}

impl<T> Default for Wrapper<T>
where
    T: (const) Default,
{
    // When implementing a conditionally const method, you write `(const)`
    // to indicate that its effects may depend on the impl effect
    // (just as in the trait). The impl effect here includes the
    // `T: (const) Default` from the impl header.
    //
    // Variation: We could also have you write `const fn default() -> Self`
    // here. See discussion below.
    (const) fn default() -> Self {
        Wrapper {
            value: T::default()
        }
    }
}

const fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: (const) Default,
{
    match x {
        None => <Wrapper<T>>::default(),
        Some(v) => v,
    }
}
}

Desugaring walkthrough

#![allow(unused)]
fn main() {
trait Default {
    // Declare the item as conditionally const (depending on the impl):
    (const) fn default() -> Self;
}
}

This is desugared to

#![allow(unused)]
fn main() {
trait Default {
    do DefaultEffect; // <-- because of the `(const)`

    fn default() -> Self
    do
        <Self as Default>::DefaultEffect; // <-- because of the `(const)`
}
}

The function get_me would be desugared as:

#![allow(unused)]
fn main() {
fn get_me<T>(x: Option<Wrapper<T>>) -> Wrapper<T>
where
    T: Default,
do
    <T as Default>::Effect, // <-- because of the `T: (const) Default`
{
    match x {
        None => <Wrapper<T>>::default(),
        Some(v) => v,
    }
}
}

The impl is desugared as

#![allow(unused)]
fn main() {
impl<T> Default for Wrapper<T>
where
    T: Default,
{
    do DefaultEffect = (
        const, // <-- included because `default` was declared as `(const)`
        <T as Default>::Effect, // <-- because of `T: (const) Default` from the impl header
    );

    fn default() -> Self
    do
        <Self as Default>::DefaultEffect, // <-- because `default` was declared as `(const)`
    {
        Wrapper {
            value: T::default()
        }
    }
}
}

All the things

#![allow(unused)]
fn main() {
trait ATT {
    // const in all impls:
    const fn always_const(&self) -> u32;

    // const if declared in impl as const
    (const) fn maybe_const(&self) -> u32;

    // const if (a) declared in impl as const and (b) methods in `T: ATT` impl are const
    (const) fn maybe_maybe_const<T: (const) ATT>(&self) -> u32;

    // includes effects from `T`
    const fn always_maybe_const<T: (const) ATT>(&self) -> u32;
}
}

Preferences

Submitted notes on why people prefer various options. This table summarizes overall position. Please do not add yourself to this table without also adding a page documenting your rationale -- though you can just point to someone else's rationable if you find it persuasive.

Person	RFC	GVB `do`	EV `~const`	EV `do`	EV `const+`
nikomatsakis

Key:

-- I love this one
-- I like this one
-- I don't hate this one
-- I really don't like this one

nikomatsakis

I am pretty keen on the quadrant (const) syntax and semantics, which seems to cover all the bases. The rationale below is mostly accurate but not fully updated with latest thoughts.

outdated:

I haven't seen a proposal I truly like yet, but I do have some thoughts. The first is that I believe

const and async should "feel the same"

Today we have the ability to declare functions with given effects in traits (notably async):

#![allow(unused)]
fn main() {
trait Service {
    type Response;
    async fn request(&self) -> Self::Response;
}
}

This implies to me that we should permit const functions as well. This seems like it would clearly be useful and is analogous to supporting const items:

#![allow(unused)]
fn main() {
trait Service {
    type Response;

    /// Given the hash of the inputs, create a hash
    /// that uniquely identifies this service.
    const fn request_hash(input_hash: u64) -> u64;

    async fn request(&self) -> Self::Response;
}
}

I also believe

Traits in libstd that becomes a "const trait" will want to be an "async trait" too

I would be very interested in counter examples, but from what I can tell, a const fn is just a "very simple" function, which means that it can be used in virtually any environment. I think we have tons of combinators and methods that fit this description, as well as a number of traits, all of which seem to me like they would make sense in an async context:

#![allow(unused)]
fn main() {
trait async Default {
    async fn default() -> Self;
}

trait async Debug {
    async fn debug(
        &self, 
        fmt: &mut std::fmt::Formatter<'_>,
    ) -> Self;
}

trait async Iterator {
    type Item;

    async fn next(&mut self) -> Option<Self::Item>;
}
}

Not only does it make sense to me to have these traits be potentially async, it makes sense for them to be potentially "try" as well. (Relevant to this, I think it is a key axiom for async that you can take sync code, add "async" and "await" everywhere, and it should do the same--including dropping things at the same time, etc. This implies to me that it would be very wrong to have e.g. an async iterator that, when you execute collect, actually executed concurrently. That is a distinct trait.)

It also seems true that

In particular, I think that marker effects are going to be huge. When Esteban was exploring redpen, one thing that he found was that the vast majority of lints boiled down to "make sure that you don't call X from Y", which is basically saying "please give me effects"¹

The second most common category of lints was "make sure that you DO call X eventually", which is linear types, but never mind.

I am also very cognizant that effects, if done poorly, are going to push Rust over the edge. To that end, I believe that

You should be able to declare a "maybe const" function without understanding effects

would be a great goal, although I'm not sure I'd call it a requirement. I also think that

Twiddle const is where Rust jumps the shark

Things I do not believe or do believe but don't care

I do believe this is true:

Most traits want to be "all or nothing" (all fns const or no fns const).

but I also think that most traits that are going to be generic over effects have relatively few method. To me the consistency of actively annotating methods that diverge from "default" effects wins over the overhead of having to add annotations to a bunch of functions.

Effectively constant or constantly effective

You believe that Traits in libstd that becomes a "const trait" will want to be an "async trait" too...?