Passing a trivial mutable reference to closure

[elefthei]

I am having trouble defining the following trait in Rust.

pub trait Traversable1<A> {
    fn fold1<Z,E,Ctx>(&self, ctx: &mut Ctx, f: &mut impl Fn(&mut Ctx, &A)->Result<Z, E>) -> Result<impl Traversable1<Z>, E>;
    fn traverse1<Z,E>(&self, f: &impl Fn(&A)->Result<Z, E>) -> Result<impl Traversable1<Z>, E> {
        let mut unit = ();
        self.fold1(&mut unit, &mut |_, a| f(a))
    }
}

Now, it is clear that traverse1 is a special case of fold1 with no mutable context, but when I try to pass a trivial mutable context let mut unit = () to it I get this error that I don't understand. I also tried setting ctx: Rc<RefCell<Ctx>> but the problem is still the lifetime of unit (same error).

 |         let mut unit = ();
   |             -------- binding `unit` declared here
13 |         self.fold1(&mut unit, &mut |_, a| f(a))
   |         -----------^^^^^^^^^-------------------
   |         |          |
   |         |          borrowed value does not live long enough
   |         argument requires that `unit` is borrowed for `'static`
14 |     }
   |     - `unit` dropped here while still borrowed

In a sense unit will never be modified, it is simply a placeholder. How can I appease the compiler? Or is it possilble to change my types so I can indeed define traverse1 in terms of fold1?

[quinedot]

I wrote a longer version, but here's the condensed version: unit and the closure you create in traverse1 are local variables, but you're trying to return &mut _ references to them (captured by the return type of fold1). You can never return references to local variables, because they dangle immediately when you return and the local variables drop.

1. Ctx placeholder: You can pull an empty &'static mut [_] "out of thin air". So allow Ctx to be ?Sized and pass in some empty &mut [()] instead of &mut ().^[1]

   //                vvvvvv
   fn fold1<Z,E,Ctx: ?Sized> ...
   
       let ctx: &mut [()] = &mut [];
       self.fold1(ctx, &mut |_, a| f(a))
   

2. The closure: Take the closures by value instead of by reference, and move the closure you take in traverse1 into the new closure. Then you'll be returning a local instead of trying to return a borrow to a local.

   //                  vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
   fn fold1<..>(.., f: impl Fn(&mut Ctx, &A)->Result<Z, E>) -> ..
   //                          vvvvvvvvvvvvvvvvvvvvvvvvv
   fn traverse1<Z,E>(&self, f: impl Fn(&A)->Result<Z, E>) -> Result<impl Traversable1<Z>, E> {
       let ctx: &mut [()] = &mut [];
       self.fold1(ctx, move |_, a| f(a))
       //              ^^^^
   

Your OP with minimal changes.

That's it for the short version; the longer version I wrote follows.

---

I'm going to suggest a bit of cleanup first.

• You can't actually prevent mutation in a generic context in Rust due to interior mutability
  • But let's ignore the motivation and soldier on
• A &mut impl Fn(..) isn't any more useful than a &impl Fn(..)
• A &impl Fn(..) also implements Fn(..)
  • So fold1 might as well take a impl Fn(..) by value
  • traverse1 as well (although it didn't have the &mut _)
• (side note) impl Trait as a function argument is basically the same as a generic parameter, so I'm going to rewrite those for readability (IMO)

This is where we get after applying those suggestions.

Still a lot of errors. I'm going to cheat a little and cherry-pick one of the suggestions I know we'll want so, I can get around to explaining something I think will be more helpful.^[2] It suggests to add move to the closure in traverse1.

pub trait Traversable1<A> {
    fn fold1<Z, E, Ctx, F>(&self, ctx: &mut Ctx, f: F) -> Result<impl Traversable1<Z>, E>
    where
        F: Fn(&mut Ctx, &A) -> Result<Z, E>
    ;
        
    fn traverse1<Z, E, F>(&self, f: F) -> Result<impl Traversable1<Z>, E>
    where
        F: Fn(&A) -> Result<Z, E>,
    {
        let mut unit = ();
        self.fold1(&mut unit, move |_, a| f(a))
        // The added `move`   ^^^^
    }
}

Okay, now we're just down to one error.

---

Next a sidebar on how to understand what impl Trait returns imply, borrow-wise.

Return position impl Trait in traits (RPITIT) captures all generic input parameters. What does that mean? It means that in the signature of fold1...

    fn fold1<Z, E, Ctx, F>(&self, ctx: &mut Ctx, f: F) 
        -> Result<impl Traversable1<Z>, E>
        //        ^^^^^^^^^^^^^^^^^^^^

...the opaque impl Traversable1<Z> type is allowed to depend on all of Z, E, Ctx, F... and also the lifetimes of the &self and &mut Ctx references. Callers have to act like they have captured all of those -- like it held on to the references you passed in.^[3]

So back in traverse1, the return from fold1 is still holding on to the borrow of unit. Then you try to return that out of traverse1, but that would be returning the borrow of a local variable -- it would immediately dangle.

That's what the error is trying to say.

(That's also what the errors that went away when we added move were about: without move, the closure you passed to fold1 borrowed the closure passed into traverse1, which was now a local due to my "by value" changes.)

Now, sometimes this is "overcapturing" where you wish the opaque return type couldn't capture that lifetime. But in this case it looks like you probably do want it to capture the &mut Ctx, correct? The return type is going to pass the captured &mut Ctx to the closure after it has been returned some time?

I'll assume so, but if I'm wrong, correct me and I'll talk a bit about how to get rid of overcapturing with some workarounds (we won't have a clean solution until the next edition, probably/hopefully).

---

So let's say we're fine with the capturing semantics here, and we've boiled the question down to this: How can you pass in a &mut ??? that you created in traverse1, but not have it get invalidated at the end of the method?

If this was &Ctx instead, you could just use some static value. You could use a static mut to a zero-sized type -- that would be harmless, but still requires unsafe to use. You could leak a zero-sized type as well.

But there's actually a family of values that are special-cased in the language in the way you need -- exclusive references (&mut) to empty slices can be generated "out of thin air" with no unsafe. This requires allowing Ctx to be unsized...

     fn fold1<Z, E, Ctx, F>(&self, ctx: &mut Ctx, f: F) -> Result<impl Traversable1<Z>, E>
     where
+        Ctx: ?Sized,
         F: Fn(&mut Ctx, &A) -> Result<Z, E>,

...after which you can generate an empty &'static mut [()] and pass that as the &mut Ctx.

        let ctx: &mut[()] = &mut [];
        self.fold1(ctx, move |_, a| f(a))

And that's enough for your OP to compile.

Rust Playground

---

1. An alternative would have been to "leak" the (), which would have effectively been the same, but I think this is cleaner. The leaky version is Box::leak(Box::new(())). Because () is zero-sized it doesn't actually allocate or leak. ↩︎

2. Also I think this only showed up due to my changes... ↩︎

3. Outside of traits, return position impl Trait captures all type parameters, but not lifetime parameters, which is a confusing difference. But in the next edition, they'll capture all lifetimes too. ↩︎

[paramagnetic]

Ouch. That's a lot of references you have there. Just do it by value, that's objectively superior:

1. it's much simpler,
2. and it's also more general (you can pass a reference where a type variable in itself is expected, but you can't pass anything by value if the signature mandates a reference). _{No wonder the equivalent in std does the same.}

pub trait Traversable1<A>: Sized {
    fn fold1<Z, E, Ctx>(
        self,
        ctx: Ctx,
        f: impl FnMut(Ctx, A) -> Result<Z, E>,
    ) -> Result<impl Traversable1<Z>, E>;
    
    fn traverse1<Z, E>(self, mut f: impl FnMut(A) -> Result<Z, E>) -> Result<impl Traversable1<Z>, E> {
        self.fold1((), move |_, a| f(a))
    }
}

Ps.: please use whitespace and Rustfmt. Your original is very heavy on the eye.

[elefthei]

Thank you for the thorough responses, the reason I am passing an impl closure by reference instead of a trait bound F: FnMut(A) -> Result<Z, E> is to get over the "Recursion limit reached while instantiating" error.

With regards to closing over mutable context and in response to

You can't actually prevent mutation in a generic context in Rust due to interior mutability.

I am rethinking this approach. If I can only use traverse1 and move all mutuable references into it, that would also work.

EDIT: It doesn't work (Rust playground). Move does not update the shared memory (the failing test). Maybe Rc<RefCell<Ctx>>?

[elefthei]

This compiles but seems unusable due to unbounded Ctx Rust Playground

[paramagnetic]

There is a lot more wrong with that code, though. For example, the Results don't match up, the RPITs aren't Debug, and the LHS of the assert_eq!() in the test is moved prematurely.

The non-Copy-ness of Ctx is a relatively minor problem: you can still make the callback take &mut Ctx and simply pass it down by value once the mutable borrow expires: Playground

pub trait Traversable1<A>: Sized {
    type Output<Z>;
    
    fn fold1<Z, E, Ctx>(
        self,
        ctx: Ctx,
        f: impl FnMut(&mut Ctx, A) -> Result<Z, E>,
    ) -> Result<Self::Output<Z>, E>
    where
        Self::Output<Z>: Traversable1<Z>;
    
    fn traverse1<Z, E>(self, mut f: impl FnMut(A) -> Result<Z, E>) -> Result<Self::Output<Z>, E>
    where
        Self::Output<Z>: Traversable1<Z>,
    {
        self.fold1((), move |_, a| f(a))
    }
}

impl<A> Traversable1<A> for List<A> {
    type Output<Z> = List<Z>;
    
    fn fold1<Z, E, Ctx>(self, mut ctx: Ctx, mut f: impl FnMut(&mut Ctx, A) -> Result<Z, E>) 
        -> Result<List<Z>, E> {
        match self {
            List::Nil => Ok(List::Nil),
            List::Cons(h, ts) => {
                let head = f(&mut ctx, h)?;
                Ok(List::Cons(head, Box::new(ts.fold1(ctx, f)?)))
            }
        }
    }
}