If `Foo<'a,'b>` requires 'a <= 'b, need to infer (or provide easy way to express) constraint

[pnkfelix]

Forked off from #10396 comment

Consider this code:

pub struct Foo<'a, 'b> { foo: &'a &'b int }

#[cfg(works)]
pub fn foo<'a, 'b>(x: Foo<'a, 'b>, _o: Option<&'a &'b ()>) { let _y = x.foo; }
#[cfg(not(works))]
pub fn foo<'a, 'b>(x: Foo<'a, 'b>, _o: Option<&   &   ()>) { let _y = x.foo; }

fn main() {}

I spoke with @eddyb and pointed him at regions-variance-covariant-use-contravariant.rs to illustrate that we do infer 'a <= 'b from the existence of &'a &'b T.

The fact that the code above does not compile as-is is interesting. I cannot tell if that is actually related to #10396 or not. (That's why I am filing this separate ticket.)

In particular, the constraints are generated by immediate occurrences of &'a &'b T, but not by occurrences of Foo<'a,'b> (despite Foo having a field of type &'a &'b T within it).

There are a couple different approaches to resolving this. The one with least user impact is probably to make occurrences of Foo<'a,'b> (when defined as above) also generate the constraint 'a <= 'b.

---

For completeness (and to save others the trouble of running rustc themselves on the above test case) here is the compile failure you get today if you attempt to compile the code above without --cfg works:

/tmp/lifetime.rs:6:66: 6:68 error: in type `&'a &'b int`, pointer has a longer lifetime than the data it references
/tmp/lifetime.rs:6 pub fn foo<'a, 'b>(x: Foo<'a, 'b>, _o: Option<&   &   ()>) { let _y = x.foo; }
                                                                                    ^~
/tmp/lifetime.rs:6:60: 6:79 note: the pointer is valid for the lifetime &'a  as defined on the block at 6:59
/tmp/lifetime.rs:6 pub fn foo<'a, 'b>(x: Foo<'a, 'b>, _o: Option<&   &   ()>) { let _y = x.foo; }
                                                                              ^~~~~~~~~~~~~~~~~~~
/tmp/lifetime.rs:6:60: 6:79 note: but the referenced data is only valid for the lifetime &'b  as defined on the block at 6:59
/tmp/lifetime.rs:6 pub fn foo<'a, 'b>(x: Foo<'a, 'b>, _o: Option<&   &   ()>) { let _y = x.foo; }
                                                                              ^~~~~~~~~~~~~~~~~~~
error: aborting due to previous error

[pnkfelix]

cc @nikomatsakis

[Valloric]

I think this issue (as pointed out by @eddyb in IRC) is currently preventing me from implementing iterators for a trait. Here's my testcase (I've reduced it quite a bit from the original code):

use std::iter::Iterator;

pub struct PreOrderNodes<'a, 'b> {
  queue: Vec<&'a Node<'b>>
}

impl<'a, 'b> Iterator<&'a Node<'b>> for PreOrderNodes<'a, 'b> {
  fn next( &mut self ) -> Option<&'a Node<'b>> {
    match self.queue.pop() {
      ex @ Some( node ) => {
        match node.contents {
          Children( ref x ) => {
            for child in x.as_slice().iter().rev() {
              self.queue.push( child )
            }
          }
          _ => ()
        };
        ex
      }
      _ => None
    }
  }
}

pub enum NodeContents<'a> {
  Data( &'a [u8] ),
  Children( Vec<Node<'a>> )
}


pub struct Node<'a> {
  pub name: &'static str,
  pub contents: NodeContents<'a>
}

impl<'a> Node<'a> {
  pub fn preOrder<'b>( &'b self ) -> PreOrderNodes<'b, 'a> {
    PreOrderNodes { queue: vec!( self ) }
  }
}

#[cfg(test)]
mod tests {
  use super::{Node, Data};

  #[test]
  fn preOrder() {
    static data: &'static [u8] = &[];
    let root = Node { name: "a", contents: Data( data ) };
    let mut names : Vec<char> = vec!();
    root.preOrder().map( |x| {
      names.push( x.name.char_at( 0 ) )
    });

    assert_eq!( names, vec!( 'a' ) )
  }
}

That with rustc --test testcase.rs (with rustc compiled from commit 9f484e6) gives me the following:

testcase.rs:14:15: 14:25 error: in type `&mut std::vec::Vec<&'a Node<'b>>`, pointer has a longer lifetime than the data it references
testcase.rs:14               self.queue.push( child )
                             ^~~~~~~~~~
testcase.rs:8:48: 23:4 note: the pointer is valid for the lifetime &'a  as defined on the block at 8:47
testcase.rs:8   fn next( &mut self ) -> Option<&'a Node<'b>> {
testcase.rs:9     match self.queue.pop() {
testcase.rs:10       ex @ Some( node ) => {
testcase.rs:11         match node.contents {
testcase.rs:12           Children( ref x ) => {
testcase.rs:13             for child in x.as_slice().rev_iter() {
               ...
testcase.rs:8:48: 23:4 note: but the referenced data is only valid for the lifetime &'b  as defined on the block at 8:47
testcase.rs:8   fn next( &mut self ) -> Option<&'a Node<'b>> {
testcase.rs:9     match self.queue.pop() {
testcase.rs:10       ex @ Some( node ) => {
testcase.rs:11         match node.contents {
testcase.rs:12           Children( ref x ) => {
testcase.rs:13             for child in x.as_slice().rev_iter() {
               ...
testcase.rs:8:3: 23:4 note: consider using an explicit lifetime parameter as shown: fn next(&mut self) -> Option<&'a Node<'a>>
testcase.rs:8   fn next( &mut self ) -> Option<&'a Node<'b>> {
testcase.rs:9     match self.queue.pop() {
testcase.rs:10       ex @ Some( node ) => {
testcase.rs:11         match node.contents {
testcase.rs:12           Children( ref x ) => {
testcase.rs:13             for child in x.as_slice().rev_iter() {
               ...
testcase.rs:12:21: 12:26 error: cannot infer an appropriate lifetime for pattern due to conflicting requirements
testcase.rs:12           Children( ref x ) => {
                                   ^~~~~
error: aborting due to 2 previous errors

[huonw]

This was fixed by #16453. Both versions of foo now compile by changing the Foo definition to

pub struct Foo<'a, 'b: 'a> { foo: &'a &'b int }