#28669 caused regression compiling pinyin crate on nightly

[eefriedman]

See https://tools.taskcluster.net/task-inspector/#UFk2m1UJRweSxQNABRB84w/0 ; I've confirmed the issue locally, although I haven't managed to reduce it.

For reference, the error message:

   Compiling pinyin v0.0.4 (file:///home/crate)                                                                         
src/lib.rs:157:24: 157:29 error: cannot infer an appropriate lifetime for lifetime parameter `'t` due to conflicting req
uirements [E0495]                                                                                                       
src/lib.rs:157         let cap = caps.at(0).unwrap();                                                                   
                                      ^~~~~                                                                             
src/lib.rs:157:19: 157:29 note: first, the lifetime cannot outlive the method call at 157:18...                         
src/lib.rs:157         let cap = caps.at(0).unwrap();                                                                   
                                 ^~~~~~~~~~                                                                             
src/lib.rs:157:19: 157:29 note: ...so that a type/lifetime parameter is in scope here                                   
src/lib.rs:157         let cap = caps.at(0).unwrap();                                                                   
                                 ^~~~~~~~~~                                                                             
src/lib.rs:157:19: 157:38 note: but, the lifetime must be valid for the method call at 157:18...                        
src/lib.rs:157         let cap = caps.at(0).unwrap();                                                                   
                                 ^~~~~~~~~~~~~~~~~~~                                                                    
src/lib.rs:157:19: 157:29 note: ...so that method receiver is valid for the method call                                 
src/lib.rs:157         let cap = caps.at(0).unwrap();                                                                   
                                 ^~~~~~~~~~                                                                             
error: aborting due to previous error                                                                                   
Could not compile `pinyin`.                                                                                             

To learn more, run the command again with --verbose.                                                                    
[taskcluster] Unsuccessful task run with exit code: 101 completed in 40.243 seconds                                     

CC @arielb1 .

[jonas-schievink]

Interesting, I'm wondering if I was hit by the same regression: https://travis-ci.org/jonas-schievink/lea/builds/83592818 (code in question)

(The code is horrible, so I might have been accidentally abusing a soundness bug there)

[eefriedman]

@jonas-schievink I think that's a different issue? Anyway, filed #28854 to track it.

[alexcrichton]

At least relatively minimized:

trait Borrow<T: ?Sized> {}                                       
impl<T: ?Sized> Borrow<T> for T {}                               
impl<'a, T: ?Sized> Borrow<T> for &'a T {}                       

struct Map<K: 'static>(K);                                       
static MAP: Map<&'static str> = Map("bar");                      
impl<K> Map<K> {                                                 
    fn get<T>(&self, _key: &T) -> Option<&K> where K: Borrow<T> {
        loop {}                                                  
    }                                                            
}                                                                

fn _foo<T: FnMut(&Captures)>(_: T) {}                            

struct Captures<'t>(&'t str);                                    
impl<'t> Captures<'t> {                                          
    fn at(&self) -> &'t str { loop {} }                          
}                                                                

pub fn foo() {                                                   
    _foo(|caps| {                                                
        MAP.get(&caps.at());                                     
    })                                                           
}                                                                
fn main() {}

Nominating as this code compiles on stable/beta and does not compile on nightly. Also tagging with T-compiler, but T-lang may also be appropriate.

[alexcrichton]

triage: I-nominated

[nikomatsakis]

triage: P-high

[arielb1]

this is a duplicate of #28854.

[nikomatsakis]

Closing as duplicate of #28854.

[nikomatsakis]

Actually, re-opening, as I like the fact that @alexcrichton's test case is relatively standalone.

[nikomatsakis]

Further minimized:

trait Borrow<T: ?Sized> {}
impl<T: ?Sized> Borrow<T> for T {}
impl<'a, T: ?Sized> Borrow<T> for &'a T {}

struct Map<K: 'static>(K);
impl<K> Map<K> {
    fn get<T>(&self, _key: &T) -> Option<&K> where K: Borrow<T> {
        loop {}
    }
}

struct Captures<'t>(&'t str);
impl<'t> Captures<'t> {
    fn at(&self) -> &'t str { loop {} }
}

pub fn foo(caps: &Captures,
           map: Map<&'static str>) {
    map.get(&caps.at());
}

fn main() {}

[brson]

Is this on beta/stable yet?

[arielb1]

This and #28854 are the same issue.

The extraneous address-of operation (to names[0] here, caps.at() in #28854) causes the Q type parameter of HashMap::get to be inferred to &'α str, with the argument type being &'β &'α str, and no deref-coercion taking place, and the The T: Borrow<T> impl is selected.

As one of the T-s is &'static str, this code compiling is suspect. The only reason this code compiles is because the type of transforms is a supertype of &'a HashMap<&'c str, u32> (where 'c is the lifetime of the strings in names), which matches with 'α = 'c. This is, obviously, unsound, as get is allowed to assume that 'c: 'a - I am not sure how bad this can be with HashMap::get because of parametricity, but it would certainly be a hole with specialization (though as @eefriedman observed, this specific case is in fact OK, because &'static str can implement Borrow<&'a str>).

[arielb1]

nominated for discussion on tomorrownext week's meeting.

[nikomatsakis]

OK so I dug into this in some detail. This may duplicate @arielb1's explanation, but let me write out what is happening here as I understand it. The TL;DR is that I believe this regression is legitimate.

First off, @alexcrichton's minimized example can be made somewhat more minimal. In particular, you only need this one impl:

trait Borrow<T: ?Sized> {}
impl<T: ?Sized> Borrow<T> for T {}

This is because the second impl never applies in this case. This might seem surprising, since at first glance it looks like it would:

impl<'a, T: ?Sized> Borrow<T> for &'a T {}

However, in this instance, the type K is &'static str, and we are passing an argument of type &&str, hence T is &str. So this works out to the get() method having a where clause like &'x str: Borrow<&'y str>, where 'x and 'y are inference variables. Because this only matches the impl impl<T> Borrow<T> for T, 'x and 'y are effectively unified.

So the question then is why this 'x gets inferred to 'static. At first you might think "well, of course it does" because here the map has type Map<&'static str>, and the obligation is K: Borrow<T>, and so you would think that K=&'static str. But this is not necessarily true. In fact, the K being used for this particular method in a covariant position. In other words, we replace K with a variable $K and then the method expects &Map<$K> and is provided with &Map<&'static str>. So that only requires that &'static str <: &'x str, and hence that 'static: 'x (which is true for any 'x). So in fact the reason that 'x is being inferred to 'static is not because it's a Map<&'static str>.

The reason is because the definition of Map places a 'static bound on K: Map<K:'static>. Thus, for this method call to be well-formed, &'x str: 'static must hold, which implies that 'x = 'static. This makes sense becuase #28669 was precisely concerned with adding those sorts of bounds. (And, indeed, if we remove the 'static bound from Map, the code builds again.)

So, in summary, I think this code should not have compiled in the first place. Now, all of this is At least, this is true of @alexcrichton's example. I guess we have to double check about the original from which it was derived.

[nikomatsakis]

So, looking at the example from #28854:

use std::collections::HashMap;
pub fn named_lints<'a>(names: &[&str],
                       transforms: &'a HashMap<&'static str, u32>)
                       -> Option<&'a u32> {
    transforms.get(&names[0])
}
fn main(){}

My explanation doesn't quite fit here, because it is using the standard HashMap, which has no 'static bound on its key type.

[nikomatsakis]

This variation seems to produce the error from #28854:

trait Borrow<T: ?Sized> {}
impl<T: ?Sized> Borrow<T> for T {}

struct Map<K>(K);
impl<K> Map<K> {
    fn get<T>(&self, _key: &T) -> Option<&u32> where K: Borrow<T> {
        loop {}
    }
}

struct Captures<'t>(&'t str);
impl<'t> Captures<'t> {
    fn at(&self) -> &'t str { loop {} }
}

fn foo<'a>(names: &[&str],
           map: &'a Map<&'static str>)
           -> Option<&'a u32> {
    map.get(&names[0])
}

fn main() {}

Error:

/home/nmatsakis/tmp/issue-28853.rs:20:9: 20:23 error: cannot infer an appropriate lifetime due to conflicting requirements [E0495]
/home/nmatsakis/tmp/issue-28853.rs:20     map.get(&names[0])
                                              ^~~~~~~~~~~~~~
/home/nmatsakis/tmp/issue-28853.rs:16:1: 21:2 help: consider using an explicit lifetime parameter as shown: fn foo<'a, 'b>(names: &[&'a str], map: &'a Map<&'static str>)
 -> Option<&'a u32>
/home/nmatsakis/tmp/issue-28853.rs:16 fn foo<'a,'b>(names: &[&str],
/home/nmatsakis/tmp/issue-28853.rs:17               map: &'a Map<&'static str>)
/home/nmatsakis/tmp/issue-28853.rs:18               -> Option<&'a u32>
/home/nmatsakis/tmp/issue-28853.rs:19 {
/home/nmatsakis/tmp/issue-28853.rs:20     map.get(&names[0])
/home/nmatsakis/tmp/issue-28853.rs:21 }
error: aborting due to previous error

[nikomatsakis]

I think the reason this error is reported is similar. In this case, the problem is that the self type must be &'a Map<K> which, to be well-formed, requires that K: 'a. Here, K is &'x str, where 'x is the lifetime of the input string. We do not know that 'x: 'a, so we get unhappy. To fix, you must extend lifetime of names, either by declaring its type to be &[&'a str] (as suggested by the error) or a change like this:

fn foo<'a,'b>(names: &[&'b str],
              map: &'a Map<&'static str>)
              -> Option<&'a u32>
    where 'b: 'a
{
    map.get(&names[0])
}

This is somewhat unfortunate. The Borrow trait impl here is really just being kind of overly strict.

[nikomatsakis]

Note that modifying the example to remove the return type will also make things compile: http://is.gd/6LqdTK. This is because the self parameter type can then be some small region confined to the body of the fn.

[nikomatsakis]

This feels like a libs issue, and probably one we can't really fix. Some more discussion here: https://botbot.me/mozilla/rust-internals/2015-11-25/?msg=54910979&page=8

[arielb1]

@nikomatsakis

Your explanation is right. However, in this case the correct fix is to remove the & and let the second impl take effect. As I discussed with @aturon back then (https://botbot.me/mozilla/rust-libs/2015-10-05/?msg=51175014&page=1), having Borrow's self-type be covariant would fix this issue.

[alexcrichton]

Recategorizing as T-libs instead of T-compiler due to @nikomatsakis's analysis to come up during triage.

[nikomatsakis]

@arielb1

having Borrow's self-type be covariant would fix this issue.

Of course, we no longer support variance in trait matching, and I don't really have much desire to do so (it opens a big can of worms). I do agree it would address this issue though.

[alexcrichton]

The libs team discussed this during triage yesterday and the conclusion was that this is an acceptable regression as it was a bugfix in the language. The library side of things may be able to accomodate this in the future but it doesn't seem necessary at this time.

@bluss also mentioned that he's updated the crate in question, so that should be taken care of.

[bluss]

The PR to fix pinyin is linked to this issue, so I didn't think that was a surprise that it was fixed.