Trait objects force higher-ranked trait bounds, which break nested closures

[kurtschelfthout]

Reposting from SO: rust - Trait objects force higher-ranked trait bounds, which break nested closures - Stack Overflow hope that's ok. (Didn't get a lot of views there, so maybe more lucky here?) Happy to sync both threads back and forth.

I am in a situation where Rust makes me add a HRTB for a generic type that is used as argument in a trait object. But this HRTB makes nested closures not work.

Here's the trait I'm going to use to make a trait object Box<dyn OpTrait>:

trait OpTrait {}

struct Op<T>(T);

impl<T> OpTrait for Op<T> {}

Here's the struct with the trait objects:

#[derive(Clone)]
struct Succ<'a, T>(T, &'a RefCell<Option<Box<dyn OpTrait>>>);

impl<'a, T: Clone> Succ<'a, T>
where
    for<'c> T: 'c, 
{
    fn trace(&self) -> Self {
        let b = Box::new(Op(self.0.clone()));
        self.1.borrow_mut().insert(b);
        Succ(self.0.clone(), self.1)
    }
}

#[derive(Debug, Clone)]
struct Zero;

And here's the function to put it all together:

fn nest<T: Clone, F>(f: F, t: &T) -> T
where
    for<'a> F: Fn(&Succ<'a, T>) -> Succ<'a, T>,
{
    let trace = RefCell::new(None);
    let nested = Succ(t.clone(), &trace);
    let result = f(&nested);
    result.0
}

I can use this like:

let input = Zero;
let result0 = nest(|n| n.trace(), &input);

which works.

But actually nesting the nest call stops working:

let result = nest(|n| nest(|nn| nn.trace(), n), &input);

  --> src/main.rs:46:37
   |
46 |     let result = nest(|n| nest(|nn| nn.trace(), n), &input);
   |                        -            ^^^^^^^^^^
   |                        |            |
   |                        |            `n` escapes the closure body here
   |                        |            argument requires that `'1` must outlive `'static`
   |                        `n` is a reference that is only valid in the closure body
   |                        has type `&Succ<'1, Zero>`

Note:

Rust makes me add for<'c> T: 'c in the impl for Succ - something to do with the trait object, I'm not exactly sure. This HRTB causes the problem with nested closures - without it in play, nested closures work fine:

// ok
let result2 = nest(|n| nest(|nn| nn.clone(), n), &input);

Playground: Rust Playground

EDIT: There's something with the 'a lifetime of the reference in Succ.

When I update that struct to remove the reference (and use Rc to support Clone):

#[derive(Clone)]
struct Succ<T>(T, Rc<dyn OpTrait>);

That works fine with the nesting, despite needing one more HRTB for T on nest.

[2e71828]

Box<dyn OpTrait> has a hidden lifetime parameter that defaults to 'static, so you can only convert Box<T> to Box<dyn OpTrait> if T:'static. I'm having a little bit of trouble following your code, but I suspect that one of your closures is collecting a lifetime from one of the Succ<'a,T> local variables.

[SkiFire13]

I already answered on stackoverflow, but to not leave this post without answer here, I'll copy-paste it:

Consider the following line:

let result1 = nest(|n| nest(|nn| nn.trace(), n), &input);

n has type &Succ<'_, Zero> due to nest's definition, and for the same reason nn has type &Succ<'_, &Succ<'_, Zero>> (all the hidden lifetimes are different because you didn't specify lifetimes with the same parameter in the arguments of the Fn bound. This is not important though).

You're then trying to call .trace() on nn, which requires the bound for<'c> T: 'c. This bound is essentially the same as T: 'static, to see this you can just take 'c = 'static, which must be valid because your bound is required for every possible lifetime 'c. In this call the T from the definition of trace is actually &Succ<'_, Zero>, which however contains unknown lifetimes and thus is not 'static and the bound for<'c> T: 'c is not satisfied.

The reason result0 works is because you have a &Succ<'_, Zero>, where the T in .trace() is Zero, which is 'static, so everything is fine.

Meanwhile in result2 you're not calling .trace() which is the reason the 'static bound was needed before, and thus that also works.

The fundamental problem in your code is that Box<dyn OpTrait> is implicitly a Box<dyn OpTrait + 'static>, while you actually want a Box<dyn OpTrait + 'lifetime_of_t>. It is natural then to introduce a lifetime 't to use in the Box and to bound T by. That is, changing Succ's definition to:

#[derive(Clone)]
struct Succ<'a, 't, T: 't>(T, &'a RefCell<Option<Box<dyn OpTrait + 't>>>);

and then updating the other methods to add 't lifetimes and T: 't bounds whenever needed.

Here's the complete fixed code: Rust Playground

[kurtschelfthout]

Beautiful, thank you both very much for the quick and clear responses! I'm also happy to report adding the lifetime parameter works in my original, uncut problem.