Confusion on lifetime bounds on type parameters

[philomathic_life]

Below, are foo and foo2 semantically identical?

fn foo<'a, T>(_: &'a T) {
}

fn foo2<'a, T: 'a>(_: &'a T) {
}

If so, how does the compiler know about the implicit lifetime bound in foo; but it requires the explicit annotation of that lifetime bound in the implementation of std::iter::Iterator::partition_in_place:

fn partition_in_place<'a, T: 'a, P>(mut self, ref mut predicate: P) -> usize
    where
        Self: Sized + DoubleEndedIterator<Item = &'a mut T>,
        P: FnMut(&T) -> bool,
    {
      ⋮
    }

To play it safe, it is my understanding that T: 'a means that if the type T happens to have internal references, then all of those references are guaranteed to last at least as long as 'a. I don’t see how foo is correct without such a guarantee since clearly in order for the parameter _ to be valid, it must be the case that the data it refers to lasts at least as long as _ itself. This is why I’m guessing that foo and foo2 are equivalent, and that the compiler is smart enough to know this. I don’t understand why it wouldn’t be smart enough to know why Self: Sized + DoubleEndedIterator<Item = &'a mut T> requires T to have the lifetime bound T: 'a and allow one to drop the explicit annotation.

Similarly, why doesn’t the implementation of std::iter::IntoIterator for &'a std::vec::Vec<T> require T to have the lifetime bound T: 'a since it assigns the associated type Item to be &'a T? Is it because the associated type IntoIter is assigned std::slice::Iter which in turn explicitly states T: 'a allowing the compiler to infer this lifetime bound for &'a std::vec::Vec<T>?

[steffahn]

Pro tip: If you wrap your code in ```s, you get syntax highlighting.

E.g.

```
fn main() {
    println!("Hello, World!");
}
```

becomes

fn main() {
    println!("Hello, World!");
}

[philomathic_life]

Thank you. I manually added 4 spaces to each line.

[steffahn]

I know. That way, you’ll still get monospace font and a box etc. but no colorful Rust syntax highlighting.

Edit: Ah, there we go ^^

[steffahn]

@philomathic_life

This is why I’m guessing that foo and foo2 are equivalent, and that the compiler is smart enough to know this.

They are definitely equivalent. I don’t fully grasp the rules around when you need to specify those bounds myself either. One thing that is true is that reference types like &'a T or &'a mut T do require T: 'a. This the same as a struct like

struct Struct<'a, T: 'a>(...);

requiring T: 'a. You can define a function like foo for such a struct as well

struct Struct<'a, T: 'a>(&'a (), T);

fn foo<'a, T>(_: Struct<'a, T>) {}

where the T: 'a can be left out, but it’ſ logically the same as if it was still there.

Experimenting a bit, it seems like leaving the T: 'a out is disallowed if the type &'a T is only mentioned in where bounds and doesn’t appear in any argument types or return value types.

[cuviper]

There's a good discussion of this in the background of RFC 2093.

[philomathic_life]

That’s an incredible link. Thank you so much. I often find that Rust’s “intelligence” is too amazing for a pathetic newb like myself since I constantly doubt my comprehension of something—my pure math background has “ruined” me like that. Of course if I ever make it to the third level of Rust comprehension, I will be eternally grateful for the increased ergonomics.

[philomathic_life]

Sorry for asking another question after accepting your answer, but I find it weird that if I explicitly state incorrect lifetime bounds that the compiler will “magically” fix it based on RFC 2093. For example, the following compiles:

struct Foo<'a, 'b: 'a, T: 'a> {
    x: &'b &'a T,
}
struct Foo2<'a, 'b: 'a, T: 'b> {
    x: &'b &'a T,
}

Clearly, the bounds must be 'a: 'b, T: 'a though. Because of this inability to break the compiler, I am having trouble testing my comprehension; so I was wondering if you can tell me which of the below structs are properly defined:

struct Foo<'a, 'b: 'a, T> {
    x: &'a &'b String,
    y: T,
}
struct Foo2<'a, 'b: 'a, T: 'a> {
    x: &'a &'b String,
    y: T,
}
struct Foo3<'a, 'b: 'a, T: 'b> {
    x: &'a &'b String,
    y: T,
}

The following are my justifications for each:

1. Foo is correct since there are no references to T at all; thus it doesn’t require any lifetime bound.
2. Foo2 is correct since all internal fields of an instance of Foo2 must last at least as long as the instance itself. This forces all fields to last as long as each other which in this case is 'a.
3. Foo3 is correct for the same reason as above, but that actually requires T to last at least as long as 'b.

I am most confident in my second line of reasoning followed by my first and finally my third.

Edit
https://rust.godbolt.org/ compiles Foo using rustc 1.0.0, so all three are “correct”; however it is unnecessary for T to have any lifetime bounds. I find it bizarre that the following compiles under rustc 1.0.0 though

fn bar<'b, 'a: 'b, 'c: 'b>(x: &'c Foo<'a, 'b, String>) -> usize {
    x.x.len()
}

Seems weird that I can reverse the lifetime bounds of 'a and 'b as well as not having to add a lifetime bound of 'c to them.

[quinedot]

@philomathic_life

Clearly, the bounds must be 'a: 'b, T: 'a though.

Although the bound is usually read as "outlives", it more accurately means "is longer or equal to". If 'a == 'b, for example, both 'a: 'b and 'b: 'a are true and safely constructable.

(And beyond all that, I'm not sure there's any restriction on declaring an un-safely-constructable bound, anyway.)

A better reply would include discussion on your examples, but I haven't the time right now; apologies. I'll check back later in case no one else replies, but still felt this was worth pointing out.

[philomathic_life]

Yeah, I know it's technically a non-strict inequality; and I believe I have been carefully wording things as "live at least as long as …" (emphasis added). You can see that rustc 1.0.0. doesn't compile either of the structs I first mentioned though, specifically

struct Foo<'a, 'b: 'a, T: 'a> {
    x: &'b &'a T,
}
struct Foo2<'a, 'b: 'a, T: 'b> {
    x: &'b &'a T,
}

Furthermore just because it is possible that 'a == 'b doesn't mean that must be true which is the whole point of a compiler: to guarantee that something will uphold.

fn foo<T>(x: T) -> u32 {
    10u32 + x
}

Obviously the above will not compile because the compiler cannot guarantee that T implements core::ops::Add<u32>; however by the same argument you made above, because it is possible that T implements that trait, the compiler should allow it.

[steffahn]

@philomathic_life

struct Foo<'a, 'b: 'a, T> {
    x: &'a &'b String,
    y: T,
}
struct Foo2<'a, 'b: 'a, T: 'a> {
    x: &'a &'b String,
    y: T,
}
struct Foo3<'a, 'b: 'a, T: 'b> {
    x: &'a &'b String,
    y: T,
}

As far as I understand, they are all correct (in the sense that they should compile, and no implicit extra bounds are added), and the first one has the minimal possible constraints, in the sense that it should be equivalent to not specifying any explicit bounds in current Rust. The other two add some redundant constraints. (Redundant in the sense that the struct does not inherently need them, but when you define it with those extra, stricter bounds, then they will be enforced on the users of Foo2 and Foo3).

[quinedot]

OK, let's look at your examples. Disclaimer up front: I'm only going to be using the playground version of Rust; in particular I'm not going to be using Rust 1.0.0.

Playground versions of the examples.

For your first example, these compile:

    let foo1a = Foo { x: &&0 };  // Foo<'static, 'static, i32>
    let foo2a = Foo2 { x: &&0 }; // Foo<'static, 'static, i32>

The constraints in both cases are met (because all lifetimes are the same, 'static).

@philomathic_life

Clearly, the bounds must be 'a: 'b, T: 'a though.

That would be more permissive and almost surely what was intended, but as shown above, the bounds as given are realizable. If the compiler denied the declaration, it would be preventing something that can be safely constructed.

And you found for yourself that your last three examples also compile, for similar reasons, so I guess I won't inline them here.

@philomathic_life

Furthermore just because it is possible that 'a == 'b doesn't mean that must be true which is the whole point of a compiler: to guarantee that something will uphold.

The point is that 'a == 'b allows the bounds to be met. The compiler is still guaranteeing that the bounds are met. I don't understand how you are reasoning; you clearly see a contradiction here, but I'm not sure where.

If the compiler could guarantee the bounds couldn't be met, it might give an error. I'm not sure if it does or not though, hence my parenthetical statement. If it does, I would bet it doesn't catch all cases^*. This isn't a violation of guarantee though, it would just mean that you could declare something that could never be (safely) constructed -- any attempt would violate some bound.

*: (I haven't played around with it, but I have heard Rust's type system is Turing complete. There's a good chance, then, that it literally impossible to always error when you declare a structure with unsatisfiable bounds, ala the halting problem.)

@philomathic_life

however by the same argument you made above, because it is possible that T implements that trait, the compiler should allow it.

I didn't make an argument, I pointed out a fact (a == b satisfies both a >= b and b >= a). Some may make the argument you stated -- it would be a call for trait bounds to be implied by the function body -- but I wouldn't support it.

[philomathic_life]

Do you find it bizarre or even unfortunate that one can't override the lifetime inference in current Rust? Specifically, that the below is allowed to compile despite being incorrect (which is why rustc 1.0.0. disallows it):

struct Foo<'a, 'b: 'a, T: 'a> {
    x: &'b &'a T,
}

If one does define Foo without a lifetime bound on T like the first definition in the three you quoted, then is it correct to say that one is guaranteed that instances of Foo can last no longer than the shortest lifetime among 'a and all lifetimes of the internal references of T (if they exist)? On the other hand, Foo2 instances are guaranteed to last no longer than 'a which means it is possible that they can lost longer than Foo instances (in particular when T has an internal reference whose lifetime is shorter than 'a)?

Also, why is it that rustc 1.0.0. doesn't require the below function to have an explicit lifetime bound on T or 'b even though the struct below it does?

// Will compile.
fn foo<'a, 'b, T>(_: &'a &'b T) {
}
// Won't compile.
struct Foo<'a, 'b, T> {
    x: &'a &'b T,
}

[philomathic_life]

If you use godbolt, you can control which version of the compiler to use. As @cuviper stated in their answer, current Rust infers the lifetime bounds now; but that wasn't the case before. Furthermore, it (correctly) infers 'b: 'a and T: 'b. If you use current Rust, this is hidden from you and will be difficult to see "what is really going on".

This is why the below struct will not compile using rustc 1.0.0 (thus avoiding the inference of lifetime bounds):

struct Foo<'a, 'b, T> {
    x: &'a &'b T,
}

Clearly the compiler cannot guarantee that any internal reference of T will last at least as long as 'b and that 'b will last at least as long as 'a. The compiler only knows that 'a and 'b are some lifetimes. Sure there are certain values for 'a and 'b that will work (i.e., whenever 'b ≥ 'a and the internal lifetimes of T are ≥ 'b, but it cannot guarantee that since it's also possible that 'a is greater than 'b. For that reason, it will not compile. That's why I gave the analogous example of adding an unknown type T to a u32. The code won't compile for the same reason.

[steffahn]

@philomathic_life

If one does define Foo without a lifetime bound on T like the first definition in the three you quoted, then is it correct to say that one is guaranteed that instances of Foo can last no longer than the shortest lifetime among 'a and all lifetimes of the internal references of T (if they exist)?

Yes.

A more formalistic way to put this is:

Foo<'a, 'b, T>: 'c if and only if 'a: 'c && T: 'c

(in particular, using the term “shorter than”: Foo<'a, 'b, T> can live for 'c only if 'c is shorter that 'a and ' is shorter than all internal references of T)

@philomathic_life

On the other hand, Foo2 instances are guaranteed to last no longer than 'a

Yes, so: Foo2<'a, 'b, T>: 'c iff 'a: 'c

@philomathic_life

which means it is possible that they can lost longer than Foo instances (in particular when T has an internal reference whose lifetime is shorter than a )?

well, when T has an internal references whose lifetime is shorter than a then T: 'a is FALSE, hence the type Foo2<'a, 'b, T> doesn’t even exist, since it’s T: 'a constraint is broken. So in this case you cannot compare Foo<'a, 'b, T> and Foo2<'a, 'b, T>. So I would disagree with the conclusion here.

@philomathic_life

Also, why is it that rustc 1.0.0. doesn't require the below function to have an explicit lifetime bound on T or 'b even though the struct below it does?

I have no idea about how rust 1.0 works, sorry.

---

To extend the formalistic view: We have for all versions of Foo:

Foo<'a, 'b, T>: 'c if and only if 'a: 'c && 'b: 'c && T: 'c

Foo2<'a, 'b, T>: 'c if and only if 'a: 'c && 'b: 'c && T: 'c

Foo3<'a, 'b, T>: 'c if and only if 'a: 'c && 'b: 'c && T: 'c

But they come with different bounds, which are precondition in order to even be allowed to write Foo<'a, 'b, T>. Perhaps similarly to how you must ensure x≠0 in order do be allowed to write 1/x in maths.

So under the preconditions of Foo, i.e. 'b: 'a, the equivalence
Foo<'a, 'b, T>: 'c if and only if 'a: 'c && 'b: 'c && T: 'c

is the same as

Foo<'a, 'b, T>: 'c if and only if 'a: 'c && T: 'c

in the sense that you can prove

'b: 'a => [
       ( Foo<'a, 'b, T>: 'c <=> 'a: 'c && 'b: 'c && T: 'c )
         <=> ( Foo<'a, 'b, T>: 'c <=> 'a: 'c && T: 'c )
]
(interpret the : as ≥ for better intuition, the important point for proving this is that 'b: 'a and 'a: 'c implies 'b: 'c)

similarly, under 'b: 'a && T: 'a

Foo2<'a, 'b, T>: 'c if and only if 'a: 'c && 'b: 'c && T: 'c
becomes
Foo2<'a, 'b, T>: 'c if and only if 'a: 'c
(analogous to above, and since T: 'a and 'a: 'c implies T: 'c)

[philomathic_life]

which means it is possible that they can lost longer than Foo instances (in particular when T has an internal reference whose lifetime is shorter than a )

I should have been clearer. I was referring to Foo there (i.e., T has lifetimes shorter than 'a which is allowed since there were no bounds defined on T in Foo). I was then assuming that the T you pass to Foo2 was a different T (since it would have to be as you pointed out) which is extremely confusing, so I apologize. The rest of your response is enough for me to answer that question.

Just to further clarify what I meant there: if the lifetime variables are the same for both Foo and Foo2, it is possible to pass a type T with at least one internal reference shorter than 'a while at the same time pass in another type T2 in Foo2 that (per the bounds) is guaranteed to not have references shorter than 'a. This in turn would mean that such a Foo2 instance could last longer than the corresponding Foo instance.

[steffahn]

@philomathic_life

I should have been clearer. I was referring to Foo there (i.e., T has lifetimes shorter than a which is allowed since there were no bounds defined). As the beginning of your response shows, this is correct.

Well, if you fix 'a, 'b, and T in a way that both Foo<'a, 'b, T> and Foo2<'a, 'b, T> are valid, i.e. in a way such that 'b: 'a and T: 'a, then Foo and Foo2 behave the same in that Foo<'a, 'b, T>: 'c iff Foo2<'a, 'b, T>: 'c. The only difference is that Foo can be used in settings (as parameterized by 'a, 'b, T) in which Foo2 can’t be used. The additional T: 'a restriction could be useful when you want to avoid introducing breaking changes when T: 'a is implicitly added in a later version, or if Foo2 contains some kind of unsafe raw-pointers stuff that doesn’t implicitly generate a T: 'a constraint, but your API becomes unsound if you don’t add this kind of constraint. Also if Foo2 has a destructor [i.e. Drop implementation] that needs T: 'a for its implementation, then you’d need to add the additional constraint on the type. Otherwise I would probably not add unnecessary constraints like that.

[philomathic_life]

Yeah, I was embarrassingly imprecise by talking about the the same exact lifetimes for Foo and Foo2; but at the same time, used T to represent two different different types. Again, I'm sorry for that.

[steffahn]

@philomathic_life

the below is allowed to compile despite being incorrect (which is why rustc 1.0.0. disallows it):

struct Foo<'a, 'b: 'a, T: 'a> {
    x: &'b &'a T,
}

just to avoid confusion: The current rust does compile this to something that is equivalent to

struct Foo<'a: 'b, 'b: 'a, T: 'a>
{
    x: &'b &'a T,
}

which effectively constrains 'a and 'b to be the same lifetime; so you could’ve used

struct Foo<'a, T: 'a>
{
    x: &'a &'a T,
}

and (syntactically) saved a parameter.

I find it unfortunate that it is currently hard to find out about the implicit bounds in Rust. In particular I would at least wish for rustdoc to figure out and show all the implicit bounds of a struct, in particular when the fields are private.

[philomathic_life]

It does?!? Good to know. So it basically combines the inference algorithm with what was explicitly stated which is only possible iff 'a= 'b. I thought it simply ignored my lifetime bounds completely and compiled that to the same thing as

struct Foo<'a, 'b, T> {
    x: &'b &'a T,
}

which in turn is equivalent to (correct?)

struct Foo<'b, 'a: 'b, T: 'a> {
    x: &'b &'a T,
}

I think that that is what @quinedot may have been trying to tell me.