Weird higher-ranked outlives bounds - are they possible?

Disclaimer: I have already found a satisfactory solution to my original problem that triggered this question. Now I am asking just out of curiosity and to extend my Rust knowledge.

Hi,

is it possible to express the following bounds?

  1. T does not borrow more than U, i.e. something like:
    T: for<'a where U: 'a> 'a
    // or
    trait SomeTrait {
        type Assoc<X>: for<'a where Self: 'a> 'a
    }
    
  2. outlives bound for all instances of generic (associated) type:
    // given
    trait SomeTrait {
        type Assoc<X>;
    }
    
    // I would like
    fn do_something<'a, T: SomeTrait>(/* ... */) where for<X> T::Assoc<X>: 'a { /* ... */ }
    

I would guess they are not possible now. (But am I right?) Are there any plans about them or something similar?

  1. No. Lifetime annotations only relate to their specific reference and other lifetime annotations through the 'a: 'b syntax. There is no way to constrain a loan's duration based on some other loan's duration, and I don't even know what it would mean to express such a thing.

  2. I'm also not sure what you are trying to express with the GAT. If X is another case of "this other type unrelated to 'a, then I still need a better picture of what this is attempting to accomplish.

It may also be helpful to know what solution you landed on, so that we may better recognize the actual requirement you originally had. Sorry I'm not of more help, here. This line of reasoning does not evenly map to my understanding of lifetime annotations.

1 Like

If I understand correctly, for the first example you want something like "wherever U is valid, T is also valid." T: 'supremum(U) or the like. I don't know a way to express that. I'm also unaware of any plans about it. I have ran into places where it would be useful.

For the second example, there is gradual movement towards some sort of higher-ranked bounds over types. I have no idea as to any expected timeline. The feature is called "non-lifetime binders".

2 Likes

Well, focused on the bounds themselves, I probably simplified too much. Now that you asked, let me elaborate a bit:

I have something like this:

trait Consumer<X> { /* object safe, details omitted */ }

trait Eater {
    type Consumer<X>: Consumer<X>;
}

trait Wrapper<E: Eater, F: Eater> {
    fn wrap_consumer<X>(from: E::Consumer<X>) -> F::Consumer<X>;
}

Now, I would like to do type erasure on Eaters and their associated Consumers:

struct EaterBox<'a>(&'a());  // details omitted, something like Box<dyn HelperTrait + 'a>

impl<'a> Eater for EaterBox<'a> {
    type Consumer<X> = Box<dyn Consumer<X> + 'a>;
}

impl<'a, X> Consumer<X> for Box<dyn Consumer<X> + 'a> { }

struct Boxer<'a>(&'a());

impl<'a, E: Eater + 'a> Wrapper<E, EaterBox<'a>> for Boxer<'a> {
    fn wrap_consumer<X>(from: E::Consumer<X>) -> Box<dyn Consumer<X> + 'a> {
        Box::new(from)
    }
}

this fails to compile with

the associated type `<E as Eater>::Consumer<X>` may not live long enough

... obviously, I am putting them into a Box<dyn ... + 'a>. If I add the compiler suggested bound:

fn wrap_consumer<X>(from: E::Consumer<X>) -> Box<dyn Consumer<X> + 'a> where <E as Eater>::Consumer<X>: 'a

... it fails with

impl has stricter requirements than trait

again, obviously, the associated fn was declared to work for all X.

So I would like to do something like (case #2):

impl<'a, E: Eater + 'a> Wrapper<E, EaterBox<'a>> for Boxer<'a>
    where for<X> E::Consumer<X>: 'a { /* items as before */ }
    // we wrap only eaters which can guarantee their consumers live long enough

or (case #1)

trait Eater {
    type Consumer<X>: Consumer<X> + for<'a where Self: 'a> 'a;  // or 'supremum(Self)
    // Every consumer must outlive its "parent" eater
}

The solution I landed on is to add a lifetime parameter on the Wrapper trait:

trait Wrapper2<'a, E: Eater, F: Eater> {
    fn wrap_consumer<X>(from: E::Consumer<X>) -> F::Consumer<X> where E: 'a, F: 'a, E::Consumer<X>: 'a, F::Consumer<X>: 'a;
}

impl<'a, E: Eater + 'a> Wrapper2<'a, E, EaterBox<'a>> for Boxer<'a> {
    fn wrap_consumer<X>(from: E::Consumer<X>) -> Box<dyn Consumer<X> + 'a> where E::Consumer<X>: 'a {
        Box::new(from)
    }
}

So far, it works for me.

(everything is on the Rust Playground)

Yes, seems you understand me correctly, thanks for the reference.

T: 'supremum(U) or the like.

.. which brings me to completely unrelated question: Is there an "established" direction of lifetime comparison/ordering?

If you interpret lifetimes as "a timespan or part of code or something like that" then 'static would the largest and the above would indeed be a supremum.

If on the other hand you interpret them as "set of allowed reference/borrow targets" (as I have read somewhere) then 'static would be the smallest and the above would be an infimum.

If you want lifetime ordering be "somehow compatible" with subtyping relation, so that references can be thought as covariant in their lifetime parameters, the above would again be an infimum. Although lifetimes are not types, so there is really no sense in having them "ordered in the same direction as types", but it might be helpful for some intuitions.

I am asking because at first glance I was not sure if by 'supremum you mean something like "covering timespan" or something like "common supertype" which are quite opposite things.

It is most common today to pretend 'static is the bottom "type" so that references are covariant, but it used to be the other way around.

So yeah, one could go either way with the terminology.

2 Likes

Yeah, and as a matter of fact, I'm personally an advocate of comparing lifetimes as the regions they represent ("set ordering"), rather than as "subtypes", especially given that since there are no "var"/instances of the "lifetime type" (i.e., since a lifetime is a not a type), talking of subtyping for lifetimes makes no sense. It is a kind with arbitrary polarity based on which the variance of types such as 'x -> &'x [mut] T is defined.

In order to avoid ambiguity, though, I usually go for the βŠ‡ symbol:

  • it goes in the same order as Rust's :.
  • it does convey the notion of β‰₯, but with emphasis on set semantics.

(I also prefer writing down T : 'r as T : UsableFor<'r>, and 'static as 'forever.)

Finally, once we consider set semantics, we can talk of 'intersections and 'unions.

  • Better than 'max or 'min since those suggest there being a total order between lifetimes/regions, which is not true: there exist uncomparable lifetimes, such as those of the respective borrows of a and b in:

    let [a, b] = ::core::array::from_fn(|_| String::from("…"));
    let it = Demo { at_a: &a, at_b: &b };
    if ::rand::random() {
        let Demo { at_b, .. } = it;
        drop(a);
        dbg!(at_b);
        drop(b);
    } else {
        let Demo { at_a, .. } = it;
        drop(b);
        dbg!(at_a);
        drop(a);
    }
    
    • In fact, this is a good example to show why sometimes distinct lifetime params are necessary even for structs dealing with all covariant lifetime params:

With this, "the maximal region of usability" of a type T = …<'a, 'b, …, 'x> is indeed the 'intersection<'a, 'b, …, 'x>.

//! Given some `'r`, and `T = …<'a, 'b, …, 'x>`

T : UsableFor<'r>,
⇔
…<'a, 'b, …, 'x> : UsableFor<'r>,
⇔ // WF rule.
{ 'a βŠ‡ 'r, 'b βŠ‡ 'r, …, 'x βŠ‡ 'r }
⇔
('a ∩ 'b ∩ … ∩ 'x) βŠ‡ 'r
⇔
'intersection<'a, 'b, …, 'x> βŠ‡ 'r
⇔
'intersection<T> βŠ‡ 'r
// let's write it down as `'T`:
'T βŠ‡ 'r

Back to the OP

So, back to your question, you want to express, for two types T, and U, the following equivalent properties:

for<'r where T : 'r>
    U : UsableFor<'r>
,
U : UsableFor<'T>,
'U βŠ‡ 'T,
'inter<'u1, 'u2, …> βŠ‡ 'inter<'t1, 't2, …>,

Since Rust does most definitely not have notation for the 'inter<…> operation, or the 'T "extraction", we have to rule out the last three.

So you are right that a HRTB/for<> quantification is necessary to express this property.

Now, the final struggle is that we don't (yet) have where-in-for<> either, "to keep Rust simple" (it just means that whenever these properties are needed, some more obscure hoops and convolutions are needed, making the whole thing significantly less clear than if we did have where-in-for<>).

  • (Rust is a language which is self-conscious/has a complex about, heh, complexity, and thus its designers have been going down a path of simplicity-through-obscurity and "white lies"[1] which, in turn, is more detrimental to the actual accessibility of the language than if it did acknowledged, recognized, and embraced, the actual theoretical patterns on which Rust hinges, and just made even more effort in teaching and documenting about them.)

So the way to hack our way around where-in-for<> is through implicit bounds: types such as &'r X, by the act of merely naming them, introduce an implicit where X : UsableFor<'r> i.e., where 'X βŠ‡ 'r bound β€”a well-formedness (WF) boundβ€”, in order for the containing predicate to ever make sense.

macro_rules! ImplicitBound {(
    where $T:ty : $region:lifetime $(,)?
) => (
    &$region $T
)}
  • e.g., ImplicitBound! { where T : 'r } becomes &'r T.

Knowing that, we could define:

trait UsableFor<'region, _UnusedWFBounds = ()> : 'region {}

impl<'r, T : 'r, _UnusedWFBounds>
    UsableFor<'r, _UnusedWFBounds>
for
    T
{}

that way we could express:

for<'r /* where 'T : 'r */>
//        ^
//        |
//        +-<-----------<------------<-+
//                                     |
    U : UsableFor<'r, ImplicitBound! { where T : 'r }>
,

Does it work?

No. :pensive: . Rust gets confused about this for now, and still treats it as for<'r> U : UsableFor<'r>, i.e., 'U βŠ‡ 'union<for<'r> 'r> i.e. 'U βŠ‡ 'forever.

But maybe one day it will? :pray:


  1. e.g., calling &mut mutable references, and worse, & references, immutable, rejecting the existence and need for &own references (instead trying to favor the way more limited and magical unsized_{rvalues,fn_params}), not allowing where-in-for<>, not allowing manual variance adjustments, delegating to more convoluted and limited PhantomData patterns, … β†©οΈŽ

2 Likes

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.