Solving function ecosystem division

[workingjubilee]

I believe the proposal in practice will only accelerate ecosystem fracturing, as people will simply not write impls for both profiles.

[ratmice]

@CAD97

and even Koka don't encode allocation as an effect.

Despite the information in the link above Koka automatic reference counting doesn't actually preclude it from encoding heap allocation as an effect. https://koka-lang.github.io/koka/doc/std_core_types.html#type_space_alloc

[y86-dev]

@the8472

I think to enforce this in a watertight way we'd need an effects system and mark functions with a no_oom_panic (or its negation?) effect. And crates/modules/impls could then blanket-apply that effect to all their functions to avoid repetitive annotations.

I feel like an effect solution is going to create too much churn. Do we have to annotate every single function with no_oom_panic? I like the general idea of effects, but the verbosity and ergonomics penalty is just too great.

@workingjubilee

I believe the proposal in practice will only accelerate ecosystem fracturing, as people will simply not write impls for both profiles.

You can still write impl<T> Vec<T>. Functions like new should belong there. And if anyone is unsure, they should add it to there. Also everyone can still call everything (ignoring the deny_profile lint) so I do not see how it accelerates divide.

[the8472]

@y86-dev

I feel like an effect solution is going to create too much churn. Do we have to annotate every single function with no_oom_panic?

Semantically each method would have to be annotated. But as I wrote it could be syntactically applied on the impl/module/crate level.

E.g.

#[effect(no_oom)]
// or #[effect(!oom)] depending on how things are propagated
impl Vec<T> {
    fn try_push (&mut self, val: T) -> Result<_> {
       // ...
    }
}

// equivalent to

impl Vec<T> {
    #[effect(no_oom)]
    fn try_push (&mut self, val: T) -> Result<_> {
       // ...
    }
}

If we wanted to combine effects with traits i.e. making it conditional on Vec<T, OOM=Fallible> that would get more complicated but probably not much more complicated than conditionally-const impls, I hope.

[y86-dev]

@the8472

Semantically each method would have to be annotated. But as I wrote it could be syntactically applied on the impl/module/crate level.

E.g.

#[effect(no_oom)]
// or #[effect(!oom)] depending on how things are propagated
impl Vec<T> {
    fn try_push (&mut self, val: T) -> Result<_> {
       // ...
    }
}

// equivalent to

impl Vec<T> {
    #[effect(no_oom)]
    fn try_push (&mut self, val: T) -> Result<_> {
       // ...
    }
}

Don't you have to mark every function that might allocate with #[effect(oom)]? If it is the default then how can we change that default for a module/crate? I still think that effects have too many loose ends...

[the8472]

Don't you have to mark every function that might allocate with #[effect(oom)]?

Const fns need their callees to be const too. So a no_oom property would have to be defined in a way that also requires that of all its callees. That way infallible doesn't need to be annotated, only code-paths that promise fallibility. All of core could be annotated that way, making things easy. Some chunks of alloc too. And then all of the kernel modules again. So they would automatically get an error when they try to call a part of alloc that is infallible.

3rd-party that only provide some limited subset of their APIs as fallible also won't have to annotate much.

In principle the compiler could help with inference, but I suspect that won't happen in practice since auto-traits have been stalled for years and we have no inference for const or pure or anything like that either.

[y86-dev]

I will definitely follow any proposals for effects with keen eyes. However, the other problem of using the same named function is not addressed by effects (and it shouldnt be). So I still think we need some profile-esque mechanism for that.

[matthieum]

I think we should consider alternative solutions that are "within reach" before wandering into brand new features.

A. Core vs std.

A first "simple" solution is to have 2 types:

• core contains a Vec<T, S: Storage> type where every method potentially requiring a memory allocation returns a Result<_, S::OomError>.
• alloc (which std inherits of) redefines a Vec<T, A: Alloc> which wraps core::Vec if S::OomError = ! and discards the Result.

It's a bit of work to replicate the API, but it could possibly be automated.

The kernel can have a lint that alloc::Vec is never imported, though in the absence of panicking allocators (with AllocErr = !) it would be able to use it anyway.

B. Trait.

Define a Vec-y trait, with a GAT type to wrap (or not) the result of methods which may require allocations.

Specialize the implementation of the trait for the case of non-faillible allocators to not wrap.

C. Vec.

Apply a GAT to Vec, deciding whether to return T or Result<T, E> based on whether Alloc::AllocErr is ! or not.

This is essentially your "context" proposal, but encoded with existing language features.

The documentation would require extensive work to remain somewhat readable, I fear.

D. Magic Result.

Make a slight change to result so that Result<T, !> does not warn if unused, as proposed by @afetisov .

It suffers from the introduction of coercions (always awkward) and the fact that existing APIs cannot easily be adjusted.

---

Out of all of these, and your existing proposal, I feel that A requires the least amount of magic, and may anyway be desirable for the Storage proposal.

Given how Rust wishes to be both a low-level and a high-level language, it makes sense to me that it would simply support 2 sets of APIs for collections:

• The low-level set of APIs would be allocation conscious.
• The high-level set of APIs would be built on top of its low-level counterpart, forwarding calls and yeeting on allocation failures.

[kornel]

I think it's fine to require libraries to always use fallible Vec methods. The split could be avoided by having a lint that bans aborting Vec methods, and expect libraries to be written in that mode.

I'm working on projects that need to watch out for OOM and fallible_collections is okay. It helps to have methods like try_extend_from_slice. It would be nice to also have try_collect or perhaps FromIterator impl of Result<Vec<_>, OOM> that uses fallible allocation. With enough helper methods this can be ergonomic enough to be a standard practice.

Std is also getting push_within_capacity, although I think it'd be better to have another wrapper type like FixedCapacityVec<'_> that can be borrowed from any Vec with all of the Vec's methods, but in fallible style, and without reallocation support.

[afetisov]

The more I think about it, the more it feels like we are really missing some powerful feature here. As I said above, even Clone should be changed in the presence of fallible allocations. The dominant reason to use Clone instead of Copy is because your structure contains, or may contain in the future some collection, and thus cloning involves multiple allocations. Should we add a fallible Clone::try_clone method? But it can't be implemented via Clone::clone, and it can't be added in a backwards-compatible way otherwise. Should we add a separate TryClone trait? But in the context where fallible allocations matter you would want to avoid the panicking methods entirely. Leaving them in stdlib is a footgun. Maybe we should make Clone return a higher-kinded type, like in your C. option? we don't have a way to introduce higher-kindedness backwards-compatibly at the moment, and I'm afraid it will break type inference.

[y86-dev]

I do not like sticking generics onto every trait to make them fallible. We could make use of profiles there as well:

pub trait Clone: Sized in @default {
    fn clone(&self) -> Self;
}

pub trait Clone: Sized in @no_std {
    type Error;

    fn clone(&self) -> Result<Self, Self::Error>;
}

impl Clone in @default for Foo {...}

But this touches on a lot of other areas, for example derive macros, so not so sure if this leads anywhere.

[CAD97]

This is a place that keyword generics is a potential help. If try can be a keyword generic, anyway.

[afetisov]

I'm not familiar with the developments in that area, but how would that work? I can imagine how that would allow you to write a polymorphic signature, but how would you write an implementation? A fallible function would have to use ? operators in code (or even do explicit matches on Result), while an infallible one would contain neither of those. How can you abstract over that?

[GKFX]

If use for this is limited to wanting versions of Vec and other container types having allocation fallibility by default, then it would seem sufficient to have an alloc::fallible module containing types like

struct Vec(pub alloc::alloc::Vec);
impl<T> Vec<T> {
    pub fn reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
        self.0.try_reserve(additional)
    }
}

In other words thin wrappers that remain perfectly compatible (as you can extract the underlying alloc::alloc::Vec) but only expose the fallible API and without the try_ prefix.

You could then make the prelude configurable to give you the fallible wrappers instead of the normal types, which effectively results in the "profiles" feature working as requested.

[matthieum]

The problem is that profiles, like any other effect systems, introduce a whole other meta-programming dimension.

TL;DR: Why is exception specific seen as "bad" in C++ or Java, and Result seen as good in Rust? Because Result is just a type.

Longer version

Profiles, effect systems, etc... are handy in simple situations; the problem comes when generic programming/meta-programming rears its head.

Let's take your profiles:

pub trait Clone: Sized in @default {
    fn clone(&self) -> Self;
}

pub trait Clone: Sized in @no_std {
    type Error;

    fn clone(&self) -> Result<Self, Self::Error>;
}

And write a method such as dup:

fn dup<T: Clone>(t: T) -> (T, T) { (t.clone(), t) }

How do I make it generic over profiles?

I mean, I expect in the @no_std profile we'd want to be:

fn dup<T: Clone>(t: T) -> (T, Result<T, T::Error>) {
    let other = t.clone();
    (t, other)
}

But I can't be talking about <T as Clone>::Error in @default profile, so how do I do that?

(Duplicating the method implementation for every profile is NOT a solution)

By comparison, TryClone is a doozy:

pub trait TryClone: Sized {
    type Error;

    fn try_clone(&self) -> Result<Self, Self::Error>;
}

impl<T: Clone> TryClone for T {
    type Error = !;

    fn try_clone(&self) -> Result<Self, Self::Error> { Ok(self.clone()) }
}

Which lets me:

fn dup<T: TryClone>(t: T) -> (T, Result<T, T::Error>) {
    let other = t.try_clone();
    (t, other)
}