Does a lifetime bound change the type of a reference?

I recently started learning Rust and just finished reading LifetimeKata after going through the book. I feel like I understood everything except the brainteaser from Chapter 9, which references this GitHub issue for rustc.

Essentially, the following example fails to compile despite appearing to be sound.

use std::collections::HashSet;

struct Difference<'fst, 'snd>(Vec<&'fst str>, Vec<&'snd str>);

fn diffwords<'fst, 'snd>(lhs: &'fst str, rhs: &'snd str) -> Difference<'fst, 'snd> {
    let lhs: HashSet<&str> = lhs.split(' ').collect();
    let rhs: HashSet<&str> = rhs.split(' ').collect();
    Difference(
        lhs.difference(&rhs).copied().collect(),
        rhs.difference(&lhs).copied().collect(),
    )
}

fn main() {
    let lhs = String::from("I love the surf and the sand.");

    let res = {
        let rhs = String::from("I hate the surf and the sand.");
        diffwords(&lhs, &rhs).0
    };

    assert_eq!(res, vec!["love"]);

    let res = {
        let rhs = String::from("I love the snow and the sand.");
        diffwords(&rhs, &lhs).1
    };

    assert_eq!(res, vec!["surf"]);
}

This comment appears to be in agreement with the GitHub issue's author that there is a problem in the implementation of HashSet<T, S>::difference(), but mentions that it is unlikely to be fixed in order to maintain backwards compatibility with previous Rust versions. Meanwhile, this other comment seems to be saying that the behavior is exactly as it should be as per the signature of the difference() method (copied below), where Self in this case is HashSet<T, S>.

fn difference<'a>(&'a self, other: &'a HashSet<T, S>) -> Difference<'a, T, S>

My confusion stems from this statement by the second commenter.

The API only applies to the same type T, i.e. for a referenced type, the lifetimes on both hash sets should be the same.

Am I understanding correctly that the second commenter is suggesting that two references of the same type are, in fact, different types if they have different lifetime bounds? In other words, are &'a T and &'b T two different types? And if so, why?

Solution

Your confusion might come from the fact that in a lot of cases the compiler is able to convert implicitly from &'a T to &'b T (e.g. if 'b is shorter than 'a). But they are still different types and the compiler can't always convert between them. For example:

fn uses_static (_foo: &'static i32) {}

fn calls_static<'a> (foo: &'a i32) {
    uses_static (foo);
}

The above code results in a "reference does not live long enough" error because &'a i32 is different from &'static i32. This is important because uses_static is allowed to store _foo in a global variable (because it's 'static) which would cause bugs if we tried to pass a local variable:

static GLOBAL: Mutex<&'static i32> = Mutex::new (&0);

fn uses_static (foo: &'static i32) {
    *GLOBAL.lock().unwrap() = foo;
}

fn calls_static() {
    let foo = 42;
    // `&foo` has type `&'a i32` but `uses_static` expects a `&'static i32`
    // so this is not allowed.
    uses_static (&foo);
}

fn invalid_access() {
    calls_static();
    // Invalid memory access! We're trying to read the  value of `foo`
    // but this was dropped when `calls_static` returned
    println!("{}", **GLOBAL.lock().unwrap());
}

On the other hand:

fn uses_two_refs<'b> (_x: &'b i32, _y: &'b i32) {}

fn uses_one_ref<'a> (x: &'a i32) {
    let y = 0;    // This has lifetime `'b` strictly shorter than `'a`
    uses_two_refs (x, &y);
}

In this third example, &'a i32 and &'b i32 are different types, so the call to uses_two_refs (x, &y) should fail because x and &y have different lifetimes. But in this case the compiler is able to convert x implicitly to type &'b i32 because 'b is shorter than 'a.

See also the "Subtyping and variance" chapter of the Rust reference.