ACP: Add {Box, Rc, Arc}::map and {Box, Rc, Arc}::try_map

[orlp]

Proposal

Problem statement

Suppose you a value contained in a Box, Rc, or Arc. It is quite natural to want to map this value to a different value, but still wanting the result to stay in a Box, Rc or Arc. Currently the easiest and most natural way of doing this always involves an allocation, whether this is necessary or not:

let old = Arc::new(42);
let new = Arc::new(old.unwrap_or_clone() * 2);

Motivating examples or use cases

Whenever you have both your input and output as a Box, Rc or Arc it is likely that you experience this problem. A personal example of mine was from a Domain Specific Language represented using Arcs. A simplified example is doing a recursive expression replacement of -x with 0 - x:

use std::sync::Arc;

#[derive(Clone)]
pub enum Expr {
    Add(Arc<Expr>, Arc<Expr>),
    Sub(Arc<Expr>, Arc<Expr>),
    Neg(Arc<Expr>),
    Number(i64),
}

fn repl_neg_with_sub(expr: Arc<Expr>) -> Arc<Expr> {
    use Expr::*;
    let ret = match Arc::unwrap_or_clone(expr) {
        Add(l, r) => Add(repl_neg_with_sub(l), repl_neg_with_sub(r)),
        Sub(l, r) => Sub(repl_neg_with_sub(l), repl_neg_with_sub(r)),
        Neg(x) => Sub(Arc::new(Number(0)), repl_neg_with_sub(x)),
        Number(x) => Number(x)
    };
    Arc::new(ret) // An unnecessary allocation most of the time.
}

Here we do an allocation for each node in the expression tree, when in a lot of cases the allocation could have been re-used. If I had used Boxes instead of Arcs every single allocation could have been re-used, only adding an allocation for the constant Number(0) added to the expression tree whenever Neg is substituted.

Solution sketch

I propose we add the following functions to Box, Rc and Arc:

type ChangeOutputType<T, V> = <<T as Try>::Residual as Residual<V>>::TryType;

impl<T, A> Arc<T, A>
where
    T: Clone,
    A: Allocator + Clone,
{
    fn map<U, F>(
        mut this: Self,
        f: F,
    ) -> Arc<U, A>
    where
        F: FnOnce(T) -> U,
    {
        // Inefficient example implementation showing expected behavior.
        let old = Arc::unwrap_or_clone(this);
        Arc::new(f(old))
    }

    fn try_map<F, R>(
        mut this: Self,
        f: F,
    ) -> ChangeOutputType<R, Arc<R::Output, A>>
    where
        F: FnOnce(T) -> R,
        R: Try,
        R::Residual: Residual<Arc<R::Output, A>>,
    {
        // Inefficient example implementation showing expected behavior.
        let old = Arc::unwrap_or_clone(this);
        let new = Arc::new(f(old)?);
        ChangeOutputType::<R, Arc<R::Output, A>>::from_output(new)
    }
}

The definitions for Rc are identical, the definitions for Box would also be the same except without a T: Clone bound.

While the shown example implementations work, they still would cause needless allocations. However in the standard library we can use unsafe code internally, and re-use the allocation (after {Rc, Arc}::make_mut has been called) with a transmute whenever T and U (or T and R::Output for try_map) have the same size and align.

With Arc::map the above example simplifies to:

fn repl_neg_with_sub(expr: Arc<Expr>) -> Arc<Expr> {
    use Expr::*;
    expr.map(|inner| match inner {
        Add(l, r) => Add(repl_neg_with_sub(l), repl_neg_with_sub(r)),
        Sub(l, r) => Sub(repl_neg_with_sub(l), repl_neg_with_sub(r)),
        Neg(x) => Sub(Arc::new(Number(0)), repl_neg_with_sub(x)),
        Number(x) => Number(x)
    })
}

Alternatives

1. You can simply keep using extra allocations through Arc::new and such.
2. You can write the unsafe code yourself (don't mess up the case when f panics!).
3. You can use the replace_with crate, if your T has Default and don't mind a tiny bit of overhead from Default being temporarily placed inside the container.
4. You can use the replace_with crate, if you don't mind an otherwise recoverable panic be turned into an abort.
5. You can use the map_box crate if you only care about Box and don't need the Try version.

While the latter case (map_box) could be extended to cover the other cases, I feel such a basic and core functionality should be in the standard library instead of a third-party crate.

Links and related work

https://docs.rs/replace_with/latest/replace_with
https://docs.rs/map_box/
https://rust-lang.zulipchat.com/#narrow/stream/219381-t-libs/topic/.7BBox.2C.20Rc.2C.20Arc.7D.3A.3Amap.20and.20.7BBox.2C.20Rc.2C.20Arc.7D.3A.3Atry_map

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

[kennytm]

I think Box::map is good but I'm not sure about Arc::map which requires a Clone bound of the inner type.

An alternative is making Arc::map take a FnOnce(&T) -> U rather than FnOnce(T) -> U.

• by ref — will not unnecessarily clone the T when the Arc's strong ref count >= 2 provided f doesn't need to own the inner value
• by value — when we are the unique owner of the Arc we can read the inner value without cloning

[Amanieu]

We discussed this in the @rust-lang/libs-api meeting and are happy to accept this!

Specifically, we would like to have the following methods:

// Taking T by value
impl Box<T> {
    fn map<U>(this: Self, f: impl FnOnce(T) -> U) -> Box<U>;
    fn try_map<R>(this: Self, f: impl FnOnce(T) -> R) -> ChangeOutputType<R, Box<R::Output>>
    where
        R: Try,
        R::Residual: Residual<Box<R::Output, A>>;
}
impl UniqueRc<T> {
    fn map<U>(this: Self, f: impl FnOnce(T) -> U) -> UniqueRc<U>;
    fn try_map<R>(this: Self, f: impl FnOnce(T) -> R) -> ChangeOutputType<R, UniqueRc<R::Output>>
    where
        R: Try,
        R::Residual: Residual<UniqueRc<R::Output, A>>;
}
impl UniqueArc<T> {
    fn map<U>(this: Self, f: impl FnOnce(T) -> U) -> UniqueArc<U>;
    fn try_map<R>(this: Self, f: impl FnOnce(T) -> R) -> ChangeOutputType<R, UniqueArc<R::Output>>
    where
        R: Try,
        R::Residual: Residual<UniqueArc<R::Output, A>>;
}

// Taking T by reference
impl Rc<T> {
    fn map<U>(this: Self, f: impl FnOnce(&T) -> U) -> Rc<U>;
    fn try_map<R>(this: Self, f: impl FnOnce(&T) -> R) -> ChangeOutputType<R, Rc<R::Output>>
    where
        R: Try,
        R::Residual: Residual<Rc<R::Output, A>>;
}
impl Arc<T> {
    fn map<U>(this: Self, f: impl FnOnce(&T) -> U) -> Arc<<U>;
    fn try_map<R>(this: Self, f: impl FnOnce(&T) -> R) -> ChangeOutputType<R, Arc<<R::Output>>
    where
        R: Try,
        R::Residual: Residual<Arc<R::Output, A>>;
}

The methods taking T by reference will try to re-use the allocation only if there are no other references. For cases where mapping by value is desired, you should first convert an Arc to a UniqueArc (cloning the inner value if needed) before mapping that.

Please open a tracking issue and open a PR to rust-lang/rust to add it as an unstable feature. You can close this ACP once the tracking issue has been created.

[RustyYato]

Could Arc/Rc::map/try_map use Cow<'_, T> instead of &T? This way, if the reference count happens to be 1 the user can get an owned value.

[Amanieu]

The only problem with Cow is that it requires T: Clone. This might be an acceptable compromise though. It should be noted as a concern to be resolved in the tracking issue.