What is the relationship between the lifetime of a borrowed reference to a vector and the borrowed pointers it contains?

Question

Editor's note: This code example is from a version of Rust prior to 1.0 and is not syntactically valid Rust 1.0 code. Updated versions of this code produce different errors, but the answers still contain valuable information.

I tried this code in Rust 0.6:

fn test<'r>(xs: &'r [&str]) -> &'r str {
    return xs[0];
}

I think this type signature means: "test takes a borrowed pointer, with lifetime 'r, to a vector of borrowed pointers to strings, and returns a borrowed pointer to a string, also with lifetime 'r. But the compiler says:

refs.rs:2:8: 2:12 error: mismatched types: expected `&'r str` but found `&str` (lifetime mismatch)
refs.rs:2       return xs[0];
                       ^~~~
refs.rs:1:39: 3:1 note: the lifetime &'r  as defined on the block at 1:39...
refs.rs:1 fn test<'r>(xs: &'r [&str]) -> &'r str {
refs.rs:2       return xs[0];
refs.rs:3 }
refs.rs:1:39: 3:1 note: ...does not necessarily outlive the anonymous lifetime #1 defined on the block at 1:39
refs.rs:1 fn test<'r>(xs: &'r [&str]) -> &'r str {
refs.rs:2       return xs[0];
refs.rs:3 }
error: aborting due to previous error

This seems to imply that the pointers within the vector may not live as long as the (read-only) vector itself. Is this possible?

Is there some additional annotation I need to make to tell the compiler this is OK?

Likewise, what about vectors of owned pointers? e.g.

fn test<'r>(xs: &'r [~str]) -> &'r str {
    return xs[0];
}

Again, I'd expect to be able to borrow a pointer to an element of the vector for at least as long as I've borrowed the whole list.

For context, my original problem was trying to extend a list of borrowed points with a list of owned pointers:

fn extend<'r>(xs: ~[&'r str], ys: &'r [~str]) -> ~[&'r str]

The plan was: create an exended list with all borrowed pointers, use it, then free the extended list, then free the original list of owned pointers, including the contained strings.

Answer 1

The second version of test, with owned/unique strings does work, just the compiler has to be assisted to convert the ~str to a &'r str:

fn test<'r>(xs: &'r [~str]) -> &'r str {
    let tmp: &'r str = xs[0];
    tmp
}

The reason this works is the xs vector owns the ~strs it contains and so the compiler knows that their lifetime is at least the lifetime of the vector (because it is also careful about mutability in the presence of borrows like this, so the string can never be removed from the vector). The only problem is convincing the compiler to coerce xs[0] to a slice, which is most easily performed by a temporary.

---

extend might look something like:

fn extend<'r>(xs: ~[&'r str], ys: &'r [~str]) -> ~[&'r str] {
    let mut xs = xs;
    for vec::each(ys) |s| {
        let tmp: &'r str = *s;
        xs.push(tmp)
    }
    xs
}

It seems that vec::each(ys) works, but ys.each doesn't, which is probably a bug (I'm investigating it now I opened #6655).

If you want to modify a vector in-place, the normal method is to pass a mutable reference to the vector, i.e.

fn extend<'r>(xs: &mut ~[&'r str], ys: &'r [~str]) {
    for vec::each(ys) |s| {
        let tmp: &'r str = *s;
        xs.push(tmp)
    }
}

which is called like extend(&mut vec, additions).

---

To illustrate:

rusti> let a = &[~"a", ~"b", ~"c"];
()
rusti> test(a)
"a"
rusti> extend(~["1", "2", "3"], a)
~["1", "2", "3", "a", "b", "c"]

Answer 2

I think that what you mean is:

fn test<'r>(xs: &[&'r str]) ->  &'r str {
        return xs[0];
}

That is, you take a borrowed array pointer containing borrowed pointers to strings with lifetime r, and returns one of these pointers, same lifetime. The lifetime of the vector itself is irrelevant.

That's the reason your second example won't work because you are returning a borrowed pointer that is not borrowed in the input of the function: the array is borrowed, its contents are not.

Answer 3

I think that this is what you mean:

fn get1<'r, T>(xs: &'r [T]) -> &'r T {
    return &xs[0];
}

fn main() {
    let a = ~[1, 2, 3];
    let b = [1, 2, 3];
    let c = @[1, 2, 3];
    let ax = get1(a);
    let bx = get1(b);
    let cx = get1(c);
    println(fmt!("%d %d %d", *ax, *bx, *cx));
}

Specifically with strings, it may not be too good (as the strings are always by-reference), but with a vector of values - it works just fine.

Answer 4

As of Rust 1.19.0 (and probably since Rust 1.0), the original code works as expected:

fn test<'r>(xs: &'r [&str]) -> &'r str {
    xs[0]
}

fn main() {}

The owned string version also works after updating the syntax:

fn test<'r>(xs: &'r [String]) -> &'r str {
    &xs[0]
}

fn main() {}

Even better, lifetime inference means that you don't need to have any explicit lifetimes on the functions (fn test(xs: &[&str]) -> &str, fn test(xs: &[String]) -> &str)

I have a feeling that this issue boils down to how to compiler calculates the (co-, contra-, in-)variance of lifetimes, or more accurately, how it didn't calculate it correctly for this case before Rust 1.0. As you correctly identified, because the slice contains the references, the references must outlive the slice. Because of this, it's safe to return the string slice with a shorter lifetime matching 'r.