Regression: Not well-formed HRTB doesn't compile

[mashedcode]

The code below doesn't compile anymore since nightly-2018-10-05:

use std::marker::PhantomData;

pub trait FooTypeHack: for<'a, 'b> FooType<'a, 'b> {}
impl<T: for<'a, 'b> FooType<'a, 'b>> FooTypeHack for T {}

pub trait FooType<'a, 'b: 'a> {
    type Foo: Foo<'a, 'b>;
}

pub trait Foo<'a, 'b: 'a> {}

pub struct FooStruct<T>
where
    T: FooTypeHack,
{
    _t: PhantomData<T>,
}

impl<T> FooStruct<T>
where
    T: FooTypeHack,
{
    fn new() -> Self {
        Self { _t: PhantomData }
    }
}

pub struct FooTypeImpl {}
impl<'a, 'b: 'a> FooType<'a, 'b> for FooTypeImpl {
    type Foo = FooImpl<'a, 'b>;
}

pub struct FooImpl<'a, 'b: 'a> {
    _a: &'a PhantomData<&'b String>,
}

impl<'a, 'b> Foo<'a, 'b> for FooImpl<'a, 'b> {}

fn main() {
    FooStruct::<FooTypeImpl>::new();
}

(Playground)

One would expect this to compile since it compiles on stable. Instead it throws:

error[E0279]: the requirement `for<'b, 'a> 'b : 'a` is not satisfied (`expected bound lifetime parameter 'a, found concrete lifetime`)
  --> src/main.rs:40:5

AFAIK for<'b, 'a> 'b: 'a can currently not be satisfied in rust therefore this should compile.

[jonas-schievink]

Fixed playground link.

Compiles fine on 1.30.0, fails on 1.31.0.

This might be expected fallout from a soundness fix, but I'll mark this as a regression anyways (looks like this completely fell through the cracks).

[spastorino]

@rustbot ping cleanup

To find where this "broke"

[rustbot]

Hey Cleanup Crew ICE-breakers! This bug has been identified as a good
"Cleanup ICE-breaking candidate". In case it's useful, here are some
instructions for tackling these sorts of bugs. Maybe take a look?
Thanks! <3

cc @AminArria @camelid @chrissimpkins @contrun @DutchGhost @elshize @ethanboxx @h-michael @HallerPatrick @hdhoang @hellow554 @imtsuki @kanru @KarlK90 @LeSeulArtichaut @MAdrianMattocks @matheus-consoli @mental32 @nmccarty @Noah-Kennedy @pard68 @PeytonT @pierreN @Redblueflame @RobbieClarken @RobertoSnap @robjtede @SarthakSingh31 @senden9 @shekohex @sinato @spastorino @turboladen @woshilapin @yerke

[spastorino]

---

Regression in nightly-2018-10-05

---

fetching https://static.rust-lang.org/dist/2018-10-04/channel-rust-nightly-git-commit-hash.txt
nightly manifest 2018-10-04: 40 B / 40 B [=============================================================================================================================================================================] 100.00 % 311.23 KB/s converted 2018-10-04 to 5597ee8
fetching https://static.rust-lang.org/dist/2018-10-05/channel-rust-nightly-git-commit-hash.txt
nightly manifest 2018-10-05: 40 B / 40 B [=============================================================================================================================================================================] 100.00 % 293.24 KB/s converted 2018-10-05 to 8c4ad4e
looking for regression commit between 2018-10-04 and 2018-10-05
cloning rust repository
fetching (via local git) commits from 5597ee8 to 8c4ad4e
opening existing repository at "rust.git"
refreshing repository
looking up first commit
looking up second commit
checking that commits are by bors and thus have ci artifacts...
finding bors merge commits
found 10 bors merge commits in the specified range
commit[0] 2018-10-03UTC: Auto merge of #54605 - petrochenkov:mambig, r=alexcrichton
commit[1] 2018-10-03UTC: Auto merge of #54391 - davidtwco:issue-54230, r=petrochenkov
commit[2] 2018-10-04UTC: Auto merge of #54447 - KiChjang:issue-54331, r=nikomatsakis
commit[3] 2018-10-04UTC: Auto merge of #54624 - arielb1:evaluate-outlives, r=nikomatsakis
commit[4] 2018-10-04UTC: Auto merge of #53851 - oli-obk:local_promotion, r=eddyb
commit[5] 2018-10-04UTC: Auto merge of #54638 - christianpoveda:master, r=kennytm
commit[6] 2018-10-04UTC: Auto merge of #54809 - pietroalbini:rollup, r=pietroalbini
commit[7] 2018-10-04UTC: Auto merge of #54784 - Manishearth:clippyup, r=oli-obk
commit[8] 2018-10-04UTC: Auto merge of #54666 - matthewjasper:mir-function-spans, r=pnkfelix
commit[9] 2018-10-04UTC: Auto merge of #54649 - nikomatsakis:universes-refactor-1, r=scalexm
ERROR: no commits between 5597ee8 and 8c4ad4e within last 167 days

[spastorino]

Related to #54624 I guess

[nikomatsakis]

OK, I suspect I know what caused this. Ah, yes, so I see that @spastorino posted the list -- it's pretty clearl #54649. I believe that the error is correct, at least given the current capabilities of the compiler, if unfortunate. This issue is also a sort of duplicate with some other issues I may try to find later. =)

In short, the error is occurring because we cannot prove for<'a, 'b> FooType: FooTypeImpl<'a, 'b> because of the where-clauses on that impl, which require that 'b: 'a.

I'm actually not 100% sure why this used to work, but it is likely because we somehow inferred some region to 'empty. That PR effectively made it so that we can no longer prove exists<'a> { forall<'b> { 'b: 'a } }, which used to be provable with the older universe code. The leak-check kind of kept that from being observed by most code, but I guess this case "snuck through" somehow.

In short, it's a regression, yes, but I think a justified one, though I do hope we'll accept this code (or code much like it) at some point -- I guess I'd like to talk to @mashedcode about how we can help you to adjust your code, that is perhaps the most likely solution.

(Though it might be worth me digging in to see why it was accepted before, as I don't quite get it.)