Lifetime parameters on self + impl Traits requires unexpected workaround

[snoyberg]

This may simply be that I'm misunderstanding something. But I was surprised by the workaround necessary to make the following code work. When working on the Xorcism exercise in Exercism, I needed to return an impl Iterator<Item=u8>. This was complicated by the presence of two different lifetime parameters (the 'a parameter from the trait for the key field, which is a &'a [u8], and the 'b parameter for the &'b mut self). With the following initial code:

use std::borrow::Borrow;

#[derive(Clone)]
pub struct Xorcism<'a> {
    key: &'a [u8],
    index: usize,
}

pub trait MungeOutput: Iterator<Item = u8> + ExactSizeIterator {}
impl<'a, T> MungeOutput for T where T: Iterator<Item = u8> + ExactSizeIterator {}

fn next_key(key: &[u8], index: &mut usize) -> u8 {
    let b = key[*index];
    *index += 1;
    if *index >= key.len() {
        *index = 0;
    }
    b
}

impl<'a> Xorcism<'a> {
    pub fn new<Key: AsRef<[u8]> + ?Sized>(key: &'a Key) -> Xorcism<'a> {
        Xorcism {
            key: key.as_ref(),
            index: 0,
        }
    }

    pub fn munge_in_place(&mut self, data: &mut [u8]) {
        for b in data {
            *b ^= next_key(self.key, &mut self.index);
        }
    }

    pub fn munge<'b, Data>(&'b mut self, data: Data) -> impl Iterator<Item=u8> + 'b
    where
        Data: IntoIterator,
        Data::Item: Borrow<u8>,
        Data::IntoIter: 'b,
    {
        data.into_iter().map(move |b| *b.borrow() ^ next_key(&self.key, &mut self.index))
    }
}

I got the error message:

error[E0700]: hidden type for `impl Trait` captures lifetime that does not appear in bounds
  --> src\lib.rs:35:57
   |
35 |     pub fn munge<'b, Data>(&'b mut self, data: Data) -> impl Iterator<Item=u8> + 'b
   |                                                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: hidden type `Map<<Data as IntoIterator>::IntoIter, [closure@src\lib.rs:41:30: 41:89]>` captures the lifetime `'a` as defined on the impl at 21:6
  --> src\lib.rs:21:6
   |
21 | impl<'a> Xorcism<'a> {
   |      ^^

However, if I replaced the line:

data.into_iter().map(move |b| *b.borrow() ^ next_key(&self.key, &mut self.index))

With the non-obvious and less intuitive:

let key = &self.key;
let index = &mut self.index;
data.into_iter().map(move |b| *b.borrow() ^ next_key(key, index))

The code compiled and ran as expected. I may be missing something, but I can't see a reason why borrowing the fields from the structure would be safe, but borrowing the structure itself would be dangerous.

Note that the original goal was to make next_key a method of the Xorcism struct, so that the best version of the code would read:

data.into_iter().map(move |b| *b.borrow() ^ self.next_key())

Meta

rustc --version --verbose:

> rustc --version --verbose
rustc 1.48.0 (7eac88abb 2020-11-16)
binary: rustc
commit-hash: 7eac88abb2e57e752f3302f02be5f3ce3d7adfb4
commit-date: 2020-11-16
host: x86_64-pc-windows-msvc
release: 1.48.0
LLVM version: 11.0

Also occurs on nightly:

> rustc +nightly --version --verbose
rustc 1.51.0-nightly (158f8d034 2020-12-29)
binary: rustc
commit-hash: 158f8d034b15e65ba8dc0d066358dd0632bfcd6e
commit-date: 2020-12-29
host: x86_64-pc-windows-msvc
release: 1.51.0-nightly

[nagisa]

To answer your question:

The reason you are seeing this issue is coming up because the closure is capturing a &'b mut Xorcism<'a> – note the both lifetimes present here. However, the code does not specify the relationship between the lifetimes 'b and 'a aywhere, so they are considered unrelated. So while the return type was specified to contain references living for at least 'b, it also needs to be at least 'a as well due to 'a in Xorcism<'a>. If you specify some relationship between the two lifetimes, then things should build with the original code as well.

That's also effectively what the note attached to the diagnostic is saying.

As for why the modified code worked – references of references imply an implicit "outlives" relationship that follows from some rules of the construct. In this instance the more-inner lifetimes gets equated to the outermost lifetime, so &'b &'a T becomes &'b &'b T. That erases the 'a lifetime from the captures, and makes things work out. (Pedantically speaking the explanation might not be quite right, but I hope it gets the point across)

For future reference there are a couple user support avenues that are more appropriate for asking questions: users.rlo, stackoverflow, reddit, or one of the chat platforms: discord or zulip.

I'm going to close this out as not-a-bug, but if you think there's something that can be improved here complain and I'll reopen.

[nagisa]

Actually, I'm going to reopen this, as I myself felt somewhat unsure about the details in the answer above as I thought about it a little bit more.

[snoyberg]

Thank you for the thorough answer here, I appreciate it. And apologies if I shouldn't have opened the issue in the first place. It's true that I wasn't sure if this was a bug or expected behavior, but I believe more clarity in the error message would still be helpful.

As to your comments about relationship of the lifetimes: I didn't want to overload the initial issue with all the variations I've tried, but I see now that I should have provided more context. Firstly: if I add a bound of 'b: 'a, then the code provided compiles, but the calling code is now an error. A simple function such as:

fn foo() {
    let mut xorcism = Xorcism::new("hello".as_bytes());
    xorcism.munge(&[1, 2, 3]);
    xorcism.munge(&[1, 2, 3]);
}

results in:

error[E0499]: cannot borrow `xorcism` as mutable more than once at a time
  --> src\lib.rs:46:5
   |
45 |     xorcism.munge(&[1, 2, 3]);
   |     ------- first mutable borrow occurs here
46 |     xorcism.munge(&[1, 2, 3]);
   |     ^^^^^^^
   |     |
   |     second mutable borrow occurs here
   |     first borrow later used here

Adding 'a: 'b results in:

error[E0700]: hidden type for `impl Trait` captures lifetime that does not appear in bounds
  --> src\lib.rs:32:57
   |
32 |     pub fn munge<'b, Data>(&'b mut self, data: Data) -> impl Iterator<Item=u8> + 'b
   |                                                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: hidden type `Map<<Data as IntoIterator>::IntoIter, [closure@src\lib.rs:39:30: 39:88]>` captures the lifetime `'a` as defined on the impl at 18:6
  --> src\lib.rs:18:6
   |
18 | impl<'a> Xorcism<'a> {
   |      ^^

error: aborting due to previous error

And changing the return type to:

impl Iterator<Item=u8> + 'a + 'b

results in:

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
  --> src\lib.rs:38:30
   |
38 |         data.into_iter().map(move |b| *b.borrow() ^ next_key(self.key, &mut self.index))
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime `'b` as defined on the method body at 32:18...
  --> src\lib.rs:32:18
   |
32 |     pub fn munge<'b, Data>(&'b mut self, data: Data) -> impl Iterator<Item=u8> + 'a + 'b
   |                  ^^
note: ...so that the types are compatible
  --> src\lib.rs:38:30
   |
38 |         data.into_iter().map(move |b| *b.borrow() ^ next_key(self.key, &mut self.index))
   |                              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   = note: expected `&mut Xorcism<'a>`
              found `&'b mut Xorcism<'a>`
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 18:6...
  --> src\lib.rs:18:6
   |
18 | impl<'a> Xorcism<'a> {
   |      ^^
note: ...so that return value is valid for the call
  --> src\lib.rs:32:57
   |
32 |     pub fn munge<'b, Data>(&'b mut self, data: Data) -> impl Iterator<Item=u8> + 'a + 'b
   |                                                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

Again, thank you for the thorough and quick response, and apologies for lack of clarity in the initial report.

[steffahn]

I don’t know the reasoning behind the compiler error when using impl Iterator<Item=u8> + 'a + 'b (in particular I don’t quite know what exactly this return type even means). The other cases behave as intended IMO.

In particular,

impl<'a> Xorcism<'a> {
    pub fn munge<'b, Data>(&'b mut self, data: Data) -> impl Iterator<Item=u8> + 'b;
}

or equivalently (in terms of type-checking) as a freestanding function

pub fn munge<'a, 'b, Data>(self: &'b Xorcism<'a>, data: Data) -> impl Iterator<Item=u8> + 'b;

comes with an implicit 'a: 'b constraint anyways (due to the type &'b Xorcism<'a> being used in the signature). Hence, adding 'a: 'b explicitly doesn’t change a thing, and adding 'b: 'a is equivalent to narrowing it down to 'a == 'b, in other words requiring self: &'a Xorcism<'a> which is a huge anti-pattern and leads to errors such as cannot borrow `xorcism` as mutable more than once at a time at use-sites, as expected.

The basics of impl Trait and lifetimes are specified in the corresponding RFC. The return type of munge<'a, 'b, Data> is something like a type-synonym but with some abstraction/opaqueness in form of additional restrictions that code using the synonym cannot rely on too much details about what the actual definition is. The details of this opaqueness are still a bit messy and currently unsound when combined with HRTBs, but that isn’t relevant here. This type synonym has certain parameters, and as per that RFC, it uses all type parameters of the function, but only those lifetime parameters that are (syntactically) appearing in the impl … return type.

By that logic, the return type of munge is like a synonym type MungeReturnType<'b, Data> = …: since 'a doesn’t appear anywhere in the impl …, it isn’t a parameter of the type synonym. OTOH, the type of the actual iterator contains a closure capturing an &'b mut Xorcism<'a>, so it depends on 'a in the sense that different 'a’s lead to different iterator types. You can’t have the same synonym MungeReturnType<'b, Data> refer to different types depending on the choice of 'a, hence the compiler error. And introducing additional lifetime parameters based on the implementation of munge would open the door to some new ways of unintentionally introducing breaking changes to your library when that implementation changes.

One way to mention the lifetime is in a trait bound: you could introduce a trait

pub trait CaptureLifetime<'a> {}
impl<T: ?Sized> CaptureLifetime<'_> for T {}

and then write

impl<'a> Xorcism<'a> {
    pub fn munge<'b, Data>(&'b mut self, data: Data) -> impl Iterator<Item=u8> + 'b + CaptureLifetime<'a>;
}

Now, the lifetime 'a does appear in the impl … and the compiler is happy.

Regarding the approach/workaround that you described: Instead of capturing a &'b mut Xorcism<'a>, you are capturing &self.key which is allowed to be any type &'c &'a [u8] with 'b: 'c and &mut self.index which is some type &'d mut usize with 'b: 'd. I don’t know the details but from what I can tell, the type checker appears to be trying to narrow these lifetimes down such that they don’t contain any lifetimes besides 'b so that the return type doesn’t capture any lifetimes anymore that it isn’t allowed to capture. In particular, choosing 'c == 'd == 'b gives &'b &'a [u8] and &'b mut usize. Getting rid of the 'a is now possible by coercing &'b &'a [u8] into &'b &'b [u8] (note coercion that this relies on the implicit 'a: 'b). As I said, I don’t know the details of how exactly the type-checker knows to insert this kind of coercion, but this should be the explanation why borrowing the fields works.

The difference that the fields introduce is that &'b &'a [u8] can be coerced into &'b &'b [u8] due to &T being covariant in its type parameter T, wherease &'b mut Xorcism<'a> cannot be coerced into &'b mut Xorcism<'b> due to &mut T being invariant in its type parameter T. The more important change wasn’t that you’re borrowing the fields individually instead of the whole struct. After all, if you write

pub fn munge<'b, Data>(&'b mut self, data: Data) -> impl Iterator<Item=u8> + 'b
where
    Data: IntoIterator,
    Data::Item: Borrow<u8>,
    Data::IntoIter: 'b,
{
    let key = &mut self.key;
    let index = &mut self.index;
    data.into_iter().map(move |b| *b.borrow() ^ next_key(&*key, index))
}

this doesn’t compile. The important step/change that made the compiler happy was in borrowing the field whose type contains the lifetime 'a only immutably so that the lifetime 'a can disappear due to variance.

[danielhenrymantilla]

… impl Iterator<Item=u8> + 'a + 'b (in particular I don’t quite know what exactly this return type even means)

the return type needs to be owned-usable within both the 'a and 'b regions, i.e., within their union. When the lifetimes are comparable, this means it needs to be usable within the bigger / maximum lifetime (also, given the current hacky implementation of impl Trait unsugaring, it also infects the existential with genericity over both lifetime params). But this is often wrong, since if the real returned type is infected with those two lifetime parameters, then it is bounded by both, i.e., its region of owned-usability is contained within the intersection / minimum of those two lifetimes (that's why your suggested + Capture<'lifetime> workaround is the way to palliate for the hacky impl Trait unsugaring).

• Regarding why I call that unsugaring hacky, I have yet to see an instance where an "overly" generic impl Trait existential would be problematic; I think that if those impl Trait existentials were made generic over all the generic parameters in scope, then the Captures<'lifetime> hack would not be needed, and the programs would still be well behaved (modulo the current bugs out there). It would lead to impl … and dyn … behaving the same (modulo Sized), which I'd qualify as being what the programmers expect.

[snoyberg]

Thank you all for the responses here!

The important step/change that made the compiler happy was in borrowing the field whose type contains the lifetime 'a only immutably so that the lifetime 'a can disappear due to variance.

I completely missed this the first time around. Thank you so much for pointing this out.

This type synonym has certain parameters, and as per that RFC, it uses all type parameters of the function, but only those lifetime parameters that are (syntactically) appearing in the impl … return type.

This, and the comments about covariance/invariance, are intriguing, and I'll need to spend a lot more time reading through the RFC carefully to understand the details. There are clearly details of impl Trait that I still don't fully grasp, I appreciate you pointing to the relevant portion of the RFC.

---

I don't have any specific requests for changes to the compiler, and my questions have been answered (thank you!), so I'll close this issue now. I appreciate everyone's help.