I think a counter-example will show that no such proof exists:
fn foo( a : &i32, b : &i32 ) -> ( &i32, &i32 ) {
// body hidden, because inference of lifetimes doesn't consider the body
}
So, the question is, "What lifetimes should the compiler infer?"
I was already thought about this. From the caller's view, they want to know from a signature is:
A "generic" signature will ensure the answer of question 1 requires minimal assumption, to allow the best flexibility, and answer of question 2 requires maximum guarantee, to make sure the caller don't abuse the return value incidentally.
So to infer a proper lifetime for your example, let's answer those questions.
The answer to the question 1 is obvious - two input values a and b must have different lifetime, otherwise the user will suffer from not allowed to call the function with some specific scopes.
Now to the question 2. If you have a struct with more than one lifetime in bound, the only case that would make a difference compare to having all lifetimes the same is when you want to enable partial move.
Note the inability of partial move is a guarantee, not an assumption, so we are free to reject this. This means we can use a same lifetime for both output components.
Needless to say, that the output lifetime should not outlive the input lifetimes. So lifetime bounds are necessary for both input. Again, this limits the thing a caller can do with the return value, but this is a guarantee.
So, the conclusion of the "most generic" life annotation of your example is:
fn foo<'a: 'c,'b: 'c,'c>(a: &'a i32, b: &'b i32) -> (&'c i32, &'c i32) {
...
}
of cause, if you do want to enable partial move,
fn foo<'a,'b,'c,'d>(a: &'a i32, b: &'b i32) -> (&'c i32, &'d i32)
where 'a:'c, 'b: 'c, 'a:'d,'b:'d
{
...
}
This is true, but I want to point out that you need types with invariant lifetimes to make it so. An example would be
fn foo<'a, 'b, 'c>(x: &'a mut &'b i32) -> &'c i32
where
'a: 'c,
'b: 'c
In this example you're correct that combining 'a and 'b into a single lifetime would limit the things you can pass to the function. But in all the previous examples from this thread, the single lifetime form is equivalent, because &'a i32 is (co)variant with respect to 'a.
(Aside: spoiler blurring doesn't seem to work on code font, or is it just me?)
I point this out because the following statement is only true if you assume all types are covariant:
Here's a counterexample:
fn foo<'a, 'b: 'a>(f: fn(&'a i32)) -> fn(&'b i32) {
f
}
The output lifetime may outlive the input lifetime, but this is fine. In this case, making the output lifetime larger is how you get the "maximum guarantee," as you called it.
Back to this statement:
I agree that there's always a signature that is as generic as possible, but I don't believe it is unique. Specifically, the code allowed by this signature:
fn func<'c>(a: &'c i32, b: &'c i32) -> &'c i32
is the same as that allowed by this signature (not a subset):
fn func<'a, 'b, 'c>(a: &'a i32, b: &'b i32) -> &'c i32
where
'a: 'c,
'b: 'c,
If I'm wrong, please show a counterexample (preferably some code that compiles with one but not with the other). If that's not what you meant, sorry for rambling!
I do like the puzzle, by the way. Hopefully many people will try it themselves and then read the thread to find out what the differences are.
Yes, I realized that the examples are not good and am even given up to fix it. Anyways, you can simply change the references to &mut T it will enforce invariancy, no need to use nested references.
My statement is a simplified version for newbies. Of cause I can further explain that "Input of input functions are output, input of output functions are input", but that is too much for them I think.
And I never talked about uniqueness. A much simpler example:
fn func(&i32);
definitely equivalent to
fn func<'a>(&'a i32);
and
fn func<'a,'b:'a>(&'a i32);
However,
fn func<'c>(a:&'c mut i32, b:&'c mut i32) -> &'c i32
is NOT equivalent to
fn func<'a:'c,'b:'c,'c>(a:&'a mut i32, b:&'b mut i32) -> &'c i32
You need to get more complicated than that: &'a mut T is still variant in 'a, although not in T. Your "not equivalent" signatures are, in fact, equivalent.
I took "in theory for any function signature there should exist exactly one such a form." to be a statement about uniqueness.
Oh.. I forgotten reborrowing. It is Copy that makes shared referencing variant, and it is reborrow makes mutable referencing so.
So the simplest form I could think of is (&mut T,), is it?
Ok I see. When I said that, I mean there is an algorithm in my head to calculate the ultimate form. Other forms that are equivalent to it, is then by coincident under other rules (copy or reborrow, or redundency, as in my simple examples above).
There's another variant using 'static -
fn func1<'a>( a: &'a i32, b: &'static i32 ) -> &'a i32
E: just saw that @trentj found the same
Hmm... I don't think so. Wrapping a type in a struct (or a tuple) doesn't hide its variance because the compiler peers inside the struct to determine its variance. Cell<&'a T> would work.
I'm also not convinced that the variance of &'a mut T is related to reborrowing, but I'm having a hard time coming up with a counterexample.
I agree - I don't think reborrows (or Copy for that matter) are related to variance at all. Afterall, variance is indicating whether you can substitute a Foo<'a> for Foo<'b> (where 'a: 'b), but a reborrow of a &'a mut Foo<'a> doesn't change the 'a inside Foo (that's actually why &mut T is invariant in the T portion - the T "remembers", as the nomicon describes it, which lifetime it contains inside).
Isn't all "codata is contravariant" means here that "if you return fn(&'b) that calls argument fn(&'a), 'b outliving 'a would be bad, e.g. if the argument wants 'static you don't want to pass something in and immediately free it"?