`impl_trait_in_bindings` and pick-constraint region bounds

[nikomatsakis]

I'm working on #56238. In the process, I'm extending how impl Trait lifetime inference works -- in particular in scenarios involving multiple, unrelated lifetimes, such as impl Trait<'a, 'b>. The challenge here is that each region 'h in the hidden type must be equal to 'a or 'b, but we can't readily express that relationship in terms of our usual "outlives relationships". The solver is thus extended with a "pick constraint", written pick 'h from ['a, 'b], which expresses that 'h must be equal to 'a or 'b. The current integration into the solver, however, requires that the regions involved are lifetime parameters. This is always true for impl Trait used at function boundaries, but it is not true for let bindings.

The challenge is that if you have a program like:

#![feature(impl_trait_in_bindings)]

trait Foo<'a> { }
impl Foo<'_> for &u32 { }

fn main() {
  let _: impl Foo<'_> = &44; // let's call the region variable for `'_` `'1`
}

then we would wind up with pick '0 from ['1, 'static], where '0 is the region variable in the hidden type (&'0 u32) and '1 is the region variable in the bounds Foo<'1>. This is tricky because both '0 and '1 are being inferred -- so making them equal may have other repercussions.

For the time being, I've chosen to include some assertions that this scenario never comes up. I'm tagging a FIXME in the code with this issue number. I was going to create some tests, but owing to the ICE #60473 (not unrelated to this issue, actually), that proved difficult, so I'll just post comments in here instead.

[nikomatsakis]

Example test. An easy case is when they use named regions from in scope:

trait Foo<'_> { }
impl Foo<'_> for &u32 { }

fn bar<'a>(data: &'a u32) {
  let x: impl Foo<'a> = data;
}

[nikomatsakis]

Example test. A harder case is when we have inferred lifetime variables.

trait Trait<'a, 'b> { }
impl<T> Trait<'_, '_> for T { }


fn bar<'a>(data0: &'a u32, data1: &'b u32) {
  let x: impl Trait<'_, '_> = (data0, data1);
  force_equal(x);
}

fn force_equal<'a>(t: impl Trait<'a, 'a>) { }

I expect this to compile because:

• the force_equal method forces the two '_ to be equal, so we effectively have impl Trait<'x, 'x>
• the hidden type is a tuple (&'0 u32, &'1 u32) where 'a: '0 and 'b: '1
• thus '0 and '1 must either equal 'x or 'static
• but 'x can be some portion of the fn body -- basically the scope of x

[vandenheuvel]

For the time being, I've chosen to include some assertions that this scenario never comes up.

@nikomatsakis I triggered this FIXME using the type_alias_impl_trait feature (and others). Is that expected?

Basically, the situation is as follows:

// All three can be disabled, ICE still triggers
// #![feature(type_alias_impl_trait)]  // Can be enabled or not, ICE will trigger
// #![feature(impl_trait_existential_types)]  // Can be enabled or not, ICE will trigger
// #![feature(trait_alias)]  // Can be enabled or not, ICE will trigger

struct S<T, I>(T, I);
trait UsedAlias<'a, T> = Iterator<Item = &'a UsedTypeAlias<T>>;
type UsedTypeAlias<T> = (usize, T); 
trait OtherTraitAlias<T> = where for<'r> &'r Self: IntoIterator<Item = UsedTypeAlias<T>>;
trait Trait<T> {
    type Associated: OtherTraitAlias<T>;
    fn into(self) -> Self::Associated;
}

// local definition, not used. Uncommenting this line will make compilation proceed to the next error.
// type Unused<T> = impl UsedAlias<T>;
impl<'a, T, I> Trait<T> for S<T, I> where T: Default, I: UsedAlias<T> {
    type Associated = S<T, impl UsedAlias<'a, T>>; // Line also necessary for the ICE
    fn into(self) -> Self::Associated { S(T::default(), vec![(0_usize, T::default())].iter()) }
}

fn other() {
    let _: i32 = 0_f64;
}

Playground.

[vandenheuvel]

Actually, this seems to be a regression from 1.45.0-beta.3 (2020-06-27 8196407f01018b442e80) to 1.46.0-nightly (2020-07-02 3503f565e1fb72969837), I'll see where else I can mention this.

[nikomatsakis]

@vandenheuvel hmm, that is somewhat unexpected, thanks for the example