Trait with HRTB blanket impl is implemented when it shouldn't be

[dtolnay]

trait Deserialize<'de> {}

trait DeserializeOwned: for<'de> Deserialize<'de> {}
impl<T> DeserializeOwned for T where T: for<'de> Deserialize<'de> {}

// Based on this impl, `&'static str` only implements Deserialize<'static>.
// It does not implement for<'de> Deserialize<'de>.
impl<'de: 'a, 'a> Deserialize<'de> for &'a str {}

fn main() {
    // Then why does it implement DeserializeOwned? This compiles.
    fn assert_deserialize_owned<T: DeserializeOwned>() {}
    assert_deserialize_owned::<&'static str>();

    // It correctly does not implement for<'de> Deserialize<'de>.
    //fn assert_hrtb<T: for<'de> Deserialize<'de>>() {}
    //assert_hrtb::<&'static str>();
}

This is a regression between rustc 1.20.0 and 1.21.0.

1.20 correctly rejects this code with the following error.

error[E0279]: the requirement `for<'de> 'de : ` is not satisfied (`expected bound lifetime parameter 'de, found concrete lifetime`)
  --> src/main.rs:13:5
   |
13 |     assert_deserialize_owned::<&'static str>();
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: required because of the requirements on the impl of `for<'de> Deserialize<'de>` for `&'static str`
   = note: required because of the requirements on the impl of `DeserializeOwned` for `&'static str`
   = note: required by `main::assert_deserialize_owned`

[dtolnay]

Tagging P-high because this very much affects Serde. @rust-lang/compiler

trait Deserialize<'de> {
    fn from_str(s: &'de str) -> Self;
}

trait DeserializeOwned: for<'de> Deserialize<'de> {}
impl<T> DeserializeOwned for T where T: for<'de> Deserialize<'de> {}

impl<'de: 'a, 'a> Deserialize<'de> for &'a str {
    fn from_str(s: &'de str) -> Self {
        s
    }
}

fn main() {
    println!("{}", use_after_free::<&'static str>());
}

fn use_after_free<T: DeserializeOwned>() -> T {
    let s = "oh my".to_owned();
    T::from_str(&s)
}

[dtolnay]

Same issue using Serde traits:

extern crate serde;
extern crate serde_json;

fn use_after_free<T: serde::de::DeserializeOwned>() -> T {
    let json = r#" "oh my" "#.to_owned();
    serde_json::from_str(&json).unwrap()
}

fn main() {
    println!("{}", use_after_free::<&'static str>());
}

(One possible) output:

¢ÚU�

[estebank]

Even better, enabling NLL causes an ICE:

error: internal compiler error: broken MIR in DefId(0/0:7 ~ playground[9687]::main[0]) (NoSolution): could not prove Binder(TraitPredicate(<&str as DeserializeOwned>))

thread 'main' panicked at 'no errors encountered even though `delay_span_bug` issued', librustc_errors/lib.rs:321:17
note: Run with `RUST_BACKTRACE=1` for a backtrace.

error: internal compiler error: unexpected panic

[nikomatsakis]

Perhaps we can bisect this regression? (e.g., with https://github.com/rust-lang-nursery/cargo-bisect-rustc)

[dtolnay]

Bisected to correct behavior in nightly-2017-07-07 -- rustc 1.20.0-nightly (696412d 2017-07-06), incorrect behavior in nightly-2017-07-08 -- rustc 1.20.0-nightly (9b85e1c 2017-07-07).

That range is 696412d...9b85e1c.

Looks like #42840.

[pnkfelix]

visited for triage. Assigning to @nikomatsakis

[nikomatsakis]

@dtolnay thanks, very helpful!

[nikomatsakis]

I think the bug is here:

rust/src/librustc/traits/fulfill.rs

Lines 296 to 304 in f7f4c50

	if data.is_global() && !data.has_late_bound_regions() {
	// no type variables present, can use evaluation for better caching.
	// FIXME: consider caching errors too.
	if self.selcx.infcx().predicate_must_hold(&obligation) {
	debug!("selecting trait `{:?}` at depth {} evaluated to holds",
	data, obligation.recursion_depth);
	return ProcessResult::Changed(vec![])
	}
	}

In particular, I think the has_late_bound_regions condition is not strong enough. predicate_must_hold doesn't consider region annotations, so we probably need to not use this logic if there are any regions.

But I'm wondering if the whole concept is flawed. I'm a bit fearful of 'static regions being introduced through associated type normalization.

[nikomatsakis]

I have a fix.

[arielb1]

Of course, any approach that relies on any lifetimes in the affected trait-ref is fatally flawed - here's an example where the trait ref is the region-free <u32 as RefFoo>.

trait Foo {
    fn foo(self) -> &'static u32;
}

impl<'a> Foo for &'a u32 where 'a: 'static {
    fn foo(self) -> &'static u32 { self }
}

trait RefFoo {
    fn ref_foo(&self) -> &'static u32;
}

impl<T> RefFoo for T where for<'a> &'a T: Foo {
    fn ref_foo(&self) -> &'static u32 {
        self.foo()
    }
}

fn coerce_lifetime(a: &u32) -> &'static u32
{
    <u32 as RefFoo>::ref_foo(a)
}

fn main() {
}

[nikomatsakis]

@arielb1 I'm not really sure what your example is meant to illustrate. That said, running that on my branch gives an error:

error[E0279]: the requirement `for<'a> 'a : 'static` is not satisfied (`expected bound lifetime parameter 'a, found concrete lifetime`)
  --> /home/nmatsakis/tmp/arielb1.rs:21:5
   |
21 |     <u32 as RefFoo>::ref_foo(a)
   |     ^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: required because of the requirements on the impl of `for<'a> Foo` for `&'a u32`
   = note: required because of the requirements on the impl of `RefFoo` for `u32`
note: required by `RefFoo::ref_foo`
  --> /home/nmatsakis/tmp/arielb1.rs:10:5
   |
10 |     fn ref_foo(&self) -> &'static u32;
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

This seems like the error I would expect, more or less. We try to use the impl to prove that for<'a> &'a T: Foo but we fail to do so (because of the side condition that it adds).

[arielb1]

BTW, the has_late_bounds_region check looks like it happened because I used is_global there, and @matthewjasper added an explicit check when he changed is_global in #48557 to note be made true by late-bound regions.

[pnkfelix]

visited for triage. bug seems to be being dealt with, assuming that PR #54401 is eventually deemed as passing muster...

[nikomatsakis]

@arielb1

BTW, the has_late_bounds_region check looks like it happened because I used is_global there, and @matthewjasper added an explicit check when he changed is_global in #48557 to note be made true by late-bound regions.

Yes, I think that the "no late-bound regions" check was basically a workaround for this same problem; I removed it in the PR since I think it has a "more correct" fix.