Two traits with single HRTB

Hi!

If I have two traits trait Upcast<'a> and trait Downcast<'a> is it possible to define a function's argument of impl FnOnce with an argument of Downcast and result of Upcast such that the trait bounds will match in general.

In pseudo-code something like this:

fn foo(f: impl for<'a> FnOnce(Downcast<'a>) -> Upcast<'a>)

I cannot uplift 'a to foo, because I want 'a to be general(high-ranked).

It might help move the discussion along if some example code is provided (ideally a playground link, so we can play with it and see any error messages). For all I know, given the information in the OP, this is what you want (obviously I am missing something):

fn foo<F>(f: F) where F: for<'a> FnOnce(&dyn Downcast<'a>) -> Box<dyn Upcast<'a>>

edit: But I think this is probably the same as uplifting the lifetime into foo because it's already named out of necessity:

fn foo<'a>(f: impl FnOnce(&dyn Downcast<'a>) -> Box<dyn Upcast<'a>>)

Thank you for your reply.

This is a minimal (non-)working example of what I'm trying to achieve:

Here the Cell::upcast function is where I have difficulties to express:

 fn upcast(
    mut self,
    // TODO this is what needs to be expressed.
    map: for<'a, D: Downcast<'a>, U: Upcast<'a>> FnOnce(D) -> U,
) -> Self

The map function should be static. Dynamic-dispatch solutions are unfortunately don't work for me.

In the playground I listed a few use cases of desirable function applications.

No, they're different. You could pass the latter a impl FnOnce(&dyn Downcast<'static> -> Box<dyn Upcast<'static>), but can only pass the former one that can handle any lifetime in the trait parameter.

(I'll look at the playground now.)

1 Like

:eyes:

This is kind of surprising. I can't tell if you inadvertently swapped "latter" and "former", or if I just really don't understand the nuance of HRTBs (very likely, I'll admit). I could see that for<'a> must accept 'static (the former case), for instance. But also, both seem to accept the static lifetime in this example. Maybe it is a bad example.

Expanding further, the HRTB page in the nomicon seems to imply that the higher ranked lifetime is only useful for "late binding" scenarios, as in the example it provides, where you don't want to bind the lifetime at constructor-time. This is obviously at the edge of my understanding, so I could even be using incorrect terminology!

Heads up: I renamed your Cell to WhatHaveYou because Cell is a special thing in Rust.


First, a problem. If I rewrite your bounds closer to how I might think of them, I get

    fn upcast<'a, D, U, F>(mut self, map: F) -> Self
    where
        D: for<'any> Downcast<'any>,
        U: for<'any> Upcast<'any>,
        // for <'any> <U as Upcast<'any>>::Output: SomeBound???,
        F: FnOnce(D) -> U,
    {
        let from: D = <D as Downcast<'_>>::Downcast::downcast(&mut self);
        let mapped: U = map(from);
        let to: <U as Upcast<'_>>::Output = <U as Upcast<'_>>::upcast(mapped);

It's still not clear how you can get from the generic U::Output to Self, but let's ignore that for now.

The problem is that type parameters like D can only represent a single type, but given your trait signatures, the type of D is probably supposed to vary per input lifetime of Downcast::downcast. That would be a type constructor, not a single type.

Upcast is probably in a similar boat.

Rust doesn't support generic type constructor parameters, but you can sometimes use GATs to work around this (GATs were originally called ACTs -- associated type constructors).

(...goes back to playground...)


I GATified the traits and gave this a shot...

trait Downcast {
    type Realized<'a>: Sized;
    fn downcast(cell: &mut WhatHaveYou) -> Self::Realized<'_>;
}

trait Upcast {
    type Output<'a>: Sized;
    type Realized<'a>: Sized;
    fn upcast(this: Self::Realized<'_>) -> Self::Output<'_>;
}

impl WhatHaveYou {
    fn upcast<D, U, F>(mut self, map: F) -> Self
    where
        D: Downcast,
        U: Upcast,
        F: for<'any> FnOnce(D::Realized<'any>) -> U::Realized<'any>,
        // for<'any> <U as Upcast>::Output<'any>: SomeBound ???,

But because the lifetime is in a GAT, it's unconstrained.

Ugh, that means we probably have to go through the dance of uplifting a FnOnce from single lifetime to any lifetime...

trait MapOne<'a, D: Downcast, U: Upcast>: Sized {
    fn map_one(self, _: <D as Downcast>::Realized<'a>) -> <U as Upcast>::Realized<'a>;
}

trait Map<D: Downcast, U: Upcast>: for<'any> MapOne<'any, D, U> {
    fn map(self, d: <D as Downcast>::Realized<'_>) -> <U as Upcast>::Realized<'_> {
        self.map_one(d)
    }
}

impl<F, D, U> Map<D, U> for F
where
    F: for<'any> MapOne<'any, D, U>,
    D: Downcast,
    U: Upcast,
{}

impl<'a, F, D, U> MapOne<'a, D, U> for F
where
    F: FnOnce(<D as Downcast>::Realized<'a>) -> <U as Upcast>::Realized<'a>,
    D: Downcast,
    U: Upcast,
{
    fn map_one(self, d: <D as Downcast>::Realized<'a>) -> <U as Upcast>::Realized<'a> {
        self(d)
    }
}
    fn upcast<D, U, F>(mut self, map: F) -> Self
    where
        D: Downcast,
        U: Upcast,
        F: Map<D, U>,

And this works... but all the indirection kills type inference. I had to add some annotations to upcast and if you uncomment the rest of use_cases, you'll get a bunch of inference errors.

You can still use it, with painful ergonomics. Or mostly, I stopped spending time on the owned -> borrowed case.


More generally, this is what abstracting over owned and borrowed tends to look like. You might be able to ease some of the ergonomics as per that other post (but I'm out of time for this now).

1 Like

Maybe I got the ordering wrong, so here's a concrete example that demonstrates they are different.

I interpreted them as needing foo not bar. But writing that up, it occurs to me they might be able to get away with

fn upcast<'a, D, U, F>(&'a mut self, map: F) -> Self where ...

And then use the 'a lifetime instead of all the higher-ranked stuff, which may make things simpler, maybe get rid of the GATs, help inference, who knows.

But... maybe they had a reason for taking self and needing the HRTB.

1 Like

Playground. If it's feasible, it is indeed much much simpler.

@quinedot Thank you very much for the detailed analysis!

I was trying to introduce GATs too, but I failed in expressing FnOnce through the helper traits, and I was thinking I went in wrong direction in general. However, I surprised it's still possible at some extent.

With such type inference flaws perhaps it would be better just to propose to the user to implement custom helper traits without GATs to mimic anonymous functions manually:

trait Map<'a> {
    type Downcast: Downcast<'a>;
    type Upcast: Upcast<'a>;
    fn map(from: Self::Downcast) -> Self::Upcast;
}

struct M;
impl<'a> Map<'a> for M {
    type Downcast = &'a usize;
    type Upcast = usize;

    fn map(from: Self::Downcast) -> Self::Upcast { *from }
}

why.upcast(M);

Or to provide more verbose "WhatHaveYou" functions like "upcast_ref_to_own" etc, or using some other explicitness that the user will have to uphold.

Honestly speaking, I'm a bit confused that what I wanted in the beginning cannot be expressed clearly in Rust's type system. But at least now I have more clear understanding of limitations.

If it's feasible, it is indeed much much simpler.

Well, the main reason I can't do it like this in my current design(which I maybe will rethink) is that after feeding &mut self to the Downcast::downcast function I no longer able to use self. Because, well, &mut self is not Copy. And I need this &mut self reference to properly construct new instance of Self from what I later receive from Upcast::upcast.

Behind the scene, I'm actually just trying to encapsulate hugely unsafe(but carefully checked for soundness) code from the end user.

Ah, so, even with the &mut self you'd need the reborrow to be some arbitrarily short lifetime that the caller can't name, and then you're right back in HRTB territory.

Actually, it cannot work in the general case due to borrowing. If you have a &mut Cell -> BorrowedDowncast -> BorrowedUpcastOutput situation, you can't use your Cell and the output at the same time as the exclusive borrow of Cell must still be active while BorrowedUpcastOutput exists.

(Which is also why these don't work.)

If that could help, I don't really need "active" thing to what I have received from Upcast interface.

Sorry that I didn't disclose the full picture, I just wanted my original question to be more framed.

The Upcast interface in fact has more explicit restrictions that look like this:

trait Upcast<'a>: Sized {
    type Output: 'static;
    fn upcast(this: Self) -> Projection<'a, Self::Output>
}

enum Projection<'a, T> {
    Own(Box<T>),
    Ref(&'a T),
    Mut(&'a mut T)
}

So, the "upcasting" process has some by-design restrictions uplifted to Runtime. In particular, in the end of Cell::cell body we know the type of the borrow.

This borrow 'a lifetime is still bound to the Cell's Self (mut self or &mut Self) lifetime, but we don't need this borrow to be active in order to construct new Self instance. I can "deactivate" the Projection instance just instantly turning borrowed variants to Raw Pointers, and effectively releasing the Self borrow.

Under the hood in the Cell object I just store raw pointers, and the original Cell instance from which this raw pointer was originated with Downcast. So, with owned value of self my original goal could be achieved like this:

struct Cell(Option<CellInner>);

impl Cell {
    fn upcast(
        mut self,
        // Let's assume we somehow expressed this:
        f: impl for<'a, D: Downcast<'a>, U: Upcast<'a>> FnOnce(D) -> U
    ) {
        let to: *const dyn Any = {
            let downcasted = Downcast::downcast(&mut self);
            let mapped = f(downcasted);
            let upcasted = Upcast::upcast(mapped);
            upcasted.into_raw_pointer()
        };

        // From now on self is no longer borrowed.
        // And the `to` pointer is also valid as long as we don't change
        // CellInner, because Downcast could only receive it's borrow from CellInner
        // under the hood.
        // e.g. I can take CellInner from Cell, and the `to` Pointer still be valid.
        // That's what I actually do here.
    }
}

The same thing could be expressed with &mut self if I had a "copy" of the mutable reference.

In fact maybe I could do the copy by my own risk. It looks sound at a very first glance, but I truly very-very unsure about soundness.

impl Cell {
    fn upcast<'a, D: Downcast<'a>, U: Upcast<'a>>(
        &'a mut self,
        f: impl FnOnce(D) -> U
    ) {
        let to: *const dyn Any = {
            // Maybe this is safe as we don't "activate" &mut self in the outer block.
            let this = unsafe { transmute::<&mut Self, &mut Self>(self); }

            let downcasted = Downcast::downcast(this);
            let mapped = f(downcasted);
            let upcasted = Upcast::upcast(mapped);
            upcasted.into_raw_pointer()
        };

        // And here I'm going to keep using original &'a mut Self.
        // In particular the first thing I will do here is taking CellInner from Cell.
        let cell_inner = take(&mut self.0);
        //...
    }
}

So, if "copying" of the mutable reference like this would be sound, maybe my design could be simplified avoiding HRTBs. But I truly unsure. Because of this I was thinking to use HRTBs.

Well, moving something then reading the memory is definitely UB. But maybe I'm missing details about CellInner or something. If you settle on unsafe, run it against Miri at a minimum.

1 Like

About this part I'm quite confident of safety. At least I'm quite confident that the "mut Self" version above would be sound. Of course I checked these constructions with Miri, I actually even checked the "&mut self" version with Miri, and didn't detect any issues.

But I'm unsure about the &mut self version anyway, because the Self is owned by an external context, and I'm not sure how Rust would interpret the fact that we have two copies of mutable borrow in edge cases. e.g. maybe during inline it could somehow reorder the copied part.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.