Rust: Compile regression "cannot infer an appropriate lifetime for lifetime parameter"

[gz]

On linux, the following works:

git clone https://github.com/AltSysrq/proptest.git
cd proptest
rustup update nightly-2020-04-06
rustup default nightly-2020-04-06
source ~/.cargo/env
rustc --version
cargo build

(rustc version is rustc 1.44.0-nightly (b543afca9 2020-04-05))

The following does not work:

rustup update nightly
rustup default nightly
source ~/.cargo/env
rustc --version
cargo build

Build fails with:

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter `'a` due to conflicting requirements
  --> proptest/src/arbitrary/_core/iter.rs:47:23
   |
47 |         base.prop_map(Iterator::cloned).boxed()
   |                       ^^^^^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the lifetime `'a` as defined on the impl at 36:9...

(rustc version is: rustc 1.44.0-nightly (42abbd887 2020-04-07))

[Centril]

Reproducer:

fn main() {}

pub trait Strategy {
    type Value;
}

fn prop_map<O, F: Fn(S::Value) -> O, S: Strategy>(_: S, _: F) -> Map<S, F> {
    loop {}
}

fn boxed<S: 'static + Strategy>(_: S) -> *const dyn Strategy<Value = S::Value> {
    loop {}
}

pub struct Map<S, F> {
    x: std::marker::PhantomData<(S, F)>,
}

impl<S: Strategy, O, F: Fn(S::Value) -> O> Strategy for Map<S, F> {
    type Value = O;
}

fn cloned<'a, T: 'a, I: Iterator<Item = &'a T>>(x: I) -> I {
    x
}

fn lift1_with<'a, T, A, S>(base: S) -> *const dyn Strategy<Value = A>
where
    T: 'static,
    A: 'static + Iterator<Item = &'a T>,
    S: Strategy<Value = A> + 'static,
{
    boxed(prop_map(base, cloned))
}

[Centril]

```
cargo-bisect-rustc \
--test-dir=proptest-regression \
--end=42abbd8878d3b67238f3611b0587c704ba94f39c \
--start=f6fe99c798cb65280a9a56f442b371adcb7b8aa2
````
reports that the regression happened in https://github.com/rust-lang/rust/commit/209b2be09fcaff937480d1fbbe8b31646e361c7a, i.e. https://github.com/rust-lang/rust/pull/70164. cc @eddyb

[eddyb]

Reduced (playground/stable -> playground/nightly):

fn assert_static<T: 'static>(_: T) {}

fn capture_type<T>() {}
fn capture_lifetime<'a: 'a>() {}

// Errors on stable & nightly.
fn test_type<'a>() {
    assert_static(capture_type::<&'a ()>);
}

// Errors *only* on nightly.
fn test_lifetime<'a>() {
    assert_static(capture_lifetime::<'a>);
}

@nikomatsakis Are we supposed to ignore only lifetime parameters in ty::FnDefs? If the reasoning is that the only thing you can do with a ty::FnDef is call it, why aren't all generics ignored?

cc @rust-lang/lang @matthewjasper

[eddyb]

I should say, I didn't expect to fix a lifetime vs type inconsistency, the goal was to fix type vs const inconsistencies. Somehow we have a behavior with no tests, I'm not sure how intentional it was.

[Centril]

(I'm perfectly happy to issue a point release, 0.9.6, to proptest btw if we decide the new compiler behavior is correct and proptest is in the wrong.)

[spastorino]

Assigning P-high and leaving nomination for T-lang. This was discussed as part of pre-triage meeting in Zulip.

[nikomatsakis]

Let me leave a brief comment explaining what is going on, because it took me a bit to figure out what @eddyb was talking about.

The type in question is one of the "anonymous types" that we construct for functions. You can think of these types as being roughly F<...>, where F is the name of the function and ... are the generic types from the function definition. In this case, the type would be something like capture_lifetime<'a>.

We are processing a constraint like capture_lifetime<'a>: 'static. The ordinary "outlives" rules for such types require that each component be 'static, so in this case it would require that 'a: 'static, which is not known to be true. These rules were defined in RFC 1214.

I'm not sure why the old code seemingly ignored this requirement. It seems like a bug to me though, a kind of artifact of the structure of the code that @eddyb fixed "in passing" by making the code operate more uniformly.

[Centril]

Notes from the language team meeting yesterday:

• We believe @eddyb's changes to be a fix, and not a bug.
• We try to assess the impact using crater (not sure how you do that -- @Mark-Simulacrum maybe you can help?)
• It seems to have broken proptest (I mistakenly suggested it broke structopt; it has not), but I am the maintainer of that crate so I am happy to publish a point release (I'll try to do so today).
• We could add a special case to have a warning period or accept this indefinitely (Speaking personally, I would prefer the former.)
• Niko does not believe the previous behavior is unsound, but interactions with typeof(...) could perhaps change that.

[Mark-Simulacrum]

@craterbot run start=master#bf1f2eedda4fa02b7c9347dd849ed73ddd43dedc end=master#209b2be09fcaff937480d1fbbe8b31646e361c7a mode=check-only

[craterbot]

:ok_hand: Experiment pr-70917 created and queued.
:mag: You can check out the queue and this experiment's details.

:information_source: Crater is a tool to run experiments across parts of the Rust ecosystem. Learn more

[pnkfelix]

Touched on briefly at the ad hoc triage meeting today. But since we are awaiting crater results, there is nothing for us to discuss at the moment.

Leaving nominated for discussion at next week's triage meeting (or hopefully sooner, async), since by then the crater results should be available.

[craterbot]

:construction: Experiment pr-70917 is now running

:information_source: Crater is a tool to run experiments across parts of the Rust ecosystem. Learn more

[Centril]

I've gone ahead and released proptest 0.9.6 which has a fix for the problem here.

[craterbot]

:tada: Experiment pr-70917 is completed!
:bar_chart: 194 regressed and 1 fixed (98337 total)
:newspaper: Open the full report.

:warning: If you notice any spurious failure please add them to the blacklist!
:information_source: Crater is a tool to run experiments across parts of the Rust ecosystem. Learn more

[lqd]

All these depend on proptest, except:

• zenroom_minimal-0.1.0
• luster
• clint
• (xtp is marked as a regressions but looks like a spurious issue maybe in crater)

[nikomatsakis]

But oof, that's a lot of regressions. Looking at zenroom_minimal and luster, both issues seem to be related to lua. Not sure about clint.

[eddyb]

We should probably allow this, since it's sound (AFAIK). If nothing else, we should be more intentional about a breaking change.

[nikomatsakis]

I'm thinking similarly. To recap what I said in the meeting, we could allow this -- it might even be something we want to consider generalizing to other types. It would I think be sound but would require caution if/when we introduce typeof, I think. In particular something like

impl<'a> Iterator for typeof(foo::<'a>) {
   type Item = &'a u32
}

would be bad, because we would think that typeof(foo::<'a>): 'static, but &'a u32: 'static doesn't hold (see RFC 1214 for more details).

However, I would like to modify RFC 1214 anyway so that we have it so that lifetime variables which appear in some positions of types are considered "unconstrained" and then cannot appear in associated types. I particularly wanted to do this for things like fn(&'a u32) (though it'd be a breaking change), and this same technique could apply to lifetimes/types that appear in FnDef types).

[spastorino]

Removed nomination as per pre-triage discussions. This was already discussed on last compiler meeting and we'll probably again tomorrow because it's an unassigned regression.

[eddyb]

Found where I introduced the breaking change: these were using push_regions:

• https://github.com/rust-lang/rust/blob/0d4705b0097a132cbb721095997d91090e8cdb21/src/librustc_middle/ty/outlives.rs#L175-L177
• https://github.com/rust-lang/rust/blob/0d4705b0097a132cbb721095997d91090e8cdb21/src/librustc_infer/infer/outlives/verify.rs#L155-L157

And push_regions was ignoring ty::FnDef's substs: https://github.com/rust-lang/rust/commit/26199f0cbc947a09d21044aacaa1ae12af465e65#diff-4cbc928241996c3226a17d1a924c6ebaL2174.

Doesn't even look like the behavior was intentional, but at least now I know where to restore it (however it is annoying that this code is duplicated...).

EDIT: opened #71218 with the fix.

[nikomatsakis]

@eddyb yeah, I expected to see some code like that -- I agree the behavior was not intentional.