Unsoundness in type checking of trait impls. Differences in implied lifetime bounds are not considered.

[steffahn]

Applies to current stable and nightly. See comment further down for a simplified example and one that works all the way since Rust 1.19.

type Ty = Box<&'static u8>;
trait Bad<'a> {
    fn f<'b>(x: &'static &'a Ty, y: &'b Ty) -> &'static Ty;
}

impl<'a> Bad<'a> for () {
    // NOTE that this signature does _not_ match the trait definition
    // (the first argument has different lifetimes)
    fn f<'b>(mut _x: &'static &'b Ty, y: &'b Ty) -> &'static Ty {
        let y = Box::new(y);
        let y = Box::leak(y);
        _x = y;
        foo(_x)
    }
}

fn foo<'b>(x: &'static &'b Ty) -> &'static Ty {
    x
}

fn main() {
    let v = Box::new(&42);
    let r = &v;
    let z: &_ = Box::leak(Box::new(Box::new(&0)));
    let z: &_ = Box::leak(Box::new(z));
    let r = <() as Bad<'static>>::f(z, r);
    drop(v);
    let _x = Box::new(0usize);
    println!("{}", r);
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
    Finished release [optimized] target(s) in 0.94s
     Running `target/release/playground`
timeout: the monitored command dumped core
/playground/tools/entrypoint.sh: line 11:     7 Segmentation fault      timeout --signal=KILL ${timeout} "$@"

@rustbot modify labels: T-compiler, C-bug, A-lifetimes, A-traits
@rustbot prioritize

[jyn514]

This might be a duplicate of #57893.

[steffahn]

@jyn514
Hm.. but isn’t that one about something with trait objects?

[SkiFire13]

To me this looks like a variation of #25860 , except it exploits it by implementing a trait instead of taking a function pointer.

[steffahn]

@SkiFire13 Oh, I see. It seems related. Taking some inspiration there for a simplified version:

type Ty = Box<&'static u8>;
trait Bad {
    fn f<'a>(_: &'static &'static (), y: &'a Ty) -> &'static Ty;
}

impl Bad for () {
    // NOTE that this signature does _not_ match the trait definition
    // (the first argument has different lifetimes)
    fn f<'a>(_: &'static &'a (), y: &'a Ty) -> &'static Ty {
        y
    }
}

fn main() {
    let v = Box::new(&0);
    let r = &v;
    let s = <()>::f(&&(), r);
    drop(v);
    let _x = Box::new(0usize);
    println!("{}", s);
}

And here’s a variant that compiles since rust 1.19.

static UNIT: &'static &'static () = &&();
static ZERO: &'static u8 = &0;

type Ty = Box<&'static u8>;
trait Bad {
    fn f<'a>(_: &'static &'static (), y: &'a Ty) -> &'static Ty;
}

impl Bad for () {
    // NOTE that this signature does _not_ match the trait definition
    // (the first argument has different lifetimes)
    fn f<'a>(_: &'static &'a (), y: &'a Ty) -> &'static Ty {
        y
    }
}

fn main() {
    let v = Box::new(ZERO);
    let s;
    {
        let r = &v;
        s = <()>::f(UNIT, r);
    }
    drop(v);
    let _x = Box::new(0usize);
    println!("{}", s);
}

In #25860 it sounds like one of the proposed solutions is to introduce "implicit bounds" to for<'a> fn(...) -> ... types.

Since there are no actual higher-ranked types in this example, this seems to demonstrates that there’s not only a problem around (higher ranked) function pointer types but also around the code that checks whether trait impls are conforming to the trait definition.

I’m not really into the inner workings of the type-checker/borrow-checker but (to me) it feels like there might perhaps be not-too-sophisticated ways of fixing this bug that don’t fix #25860.

[camelid]

Assigning P-critical and removing I-prioritize as discussed in the prioritization working group.

[pnkfelix]

downgrading priority to P-high (because this is an old bug, not a regression and I would not consider it a release blocker), but also nominating for discussion because I want to talk about it at a future compiler team meeting with @nikomatsakis present.

[pnkfelix]

Discussed at today's T-compiler meeting: https://zulip-archive.rust-lang.org/238009tcompilermeetings/41447weeklymeeting2021010754818.html#221955336

Downgrading to P-medium to make consistent with #25860. (We think the right path for fixing this is something that would also resolve #25860.)

Removing nomination label.

[steffahn]

@rustbot modify labels: +A-typesystem

[SkiFire13]

Coming back to this after the recent article on #25860

Since there are no actual higher-ranked types in this example, this seems to demonstrates that there’s not only a problem around (higher ranked) function pointer types but also around the code that checks whether trait impls are conforming to the trait definition.

I'm not convinced anymore that's the case. If you try this (wrong) code:

trait Foo {
    fn f<'a>(_: &'a ());
}

impl Foo for () {
    fn f(_: &'static ()) {}
}

You'll get this error:

error[E0308]: method not compatible with trait
 --> src/lib.rs:6:5
  |
6 |     fn f(_: &'static ()) {}
  |     ^^^^^^^^^^^^^^^^^^^^ lifetime mismatch
  |
  = note: expected fn pointer `fn(&'a ())`
             found fn pointer `fn(&'static ())`
note: the lifetime `'a` as defined here...
 --> src/lib.rs:6:5
  |
6 |     fn f(_: &'static ()) {}
  |     ^^^^^^^^^^^^^^^^^^^^
  = note: ...does not necessarily outlive the static lifetime

(Also, it's interesting the note that references a non-existing lifetime, but that's an unrelated issue)

Note the reference to function pointers. The HRTB part is missing, but I suspect this is just the way it is printed.

Edit: the code responsible for checking that methods in trait impls match the ones in the trait definition is this:

rust/compiler/rustc_typeck/src/check/compare_method.rs

Lines 32 to 74 in e069a71

	crate fn compare_impl_method<'tcx>(
	tcx: TyCtxt<'tcx>,
	impl_m: &ty::AssocItem,
	impl_m_span: Span,
	trait_m: &ty::AssocItem,
	impl_trait_ref: ty::TraitRef<'tcx>,
	trait_item_span: Option<Span>,
	) {
	debug!("compare_impl_method(impl_trait_ref={:?})", impl_trait_ref);
	let impl_m_span = tcx.sess.source_map().guess_head_span(impl_m_span);
	if let Err(ErrorReported) = compare_self_type(tcx, impl_m, impl_m_span, trait_m, impl_trait_ref)
	{
	return;
	}
	if let Err(ErrorReported) =
	compare_number_of_generics(tcx, impl_m, impl_m_span, trait_m, trait_item_span)
	{
	return;
	}
	if let Err(ErrorReported) =
	compare_number_of_method_arguments(tcx, impl_m, impl_m_span, trait_m, trait_item_span)
	{
	return;
	}
	if let Err(ErrorReported) = compare_synthetic_generics(tcx, impl_m, trait_m) {
	return;
	}
	if let Err(ErrorReported) =
	compare_predicate_entailment(tcx, impl_m, impl_m_span, trait_m, impl_trait_ref)
	{
	return;
	}
	if let Err(ErrorReported) = compare_const_param_types(tcx, impl_m, trait_m, trait_item_span) {
	return;
	}
	}

This ends up calling compare_predicate_entailment, which is defined here:

rust/compiler/rustc_typeck/src/check/compare_method.rs

Lines 76 to 406 in e069a71

	fn compare_predicate_entailment<'tcx>(
	tcx: TyCtxt<'tcx>,
	impl_m: &ty::AssocItem,
	impl_m_span: Span,
	trait_m: &ty::AssocItem,
	impl_trait_ref: ty::TraitRef<'tcx>,
	) -> Result<(), ErrorReported> {
	let trait_to_impl_substs = impl_trait_ref.substs;
	// This node-id should be used for the `body_id` field on each
	// `ObligationCause` (and the `FnCtxt`). This is what
	// `regionck_item` expects.
	let impl_m_hir_id = tcx.hir().local_def_id_to_hir_id(impl_m.def_id.expect_local());
	// We sometimes modify the span further down.
	let mut cause = ObligationCause::new(
	impl_m_span,
	impl_m_hir_id,
	ObligationCauseCode::CompareImplMethodObligation {
	impl_item_def_id: impl_m.def_id,
	trait_item_def_id: trait_m.def_id,
	},
	);
	// This code is best explained by example. Consider a trait:
	//
	// trait Trait<'t, T> {
	// fn method<'a, M>(t: &'t T, m: &'a M) -> Self;
	// }
	//
	// And an impl:
	//
	// impl<'i, 'j, U> Trait<'j, &'i U> for Foo {
	// fn method<'b, N>(t: &'j &'i U, m: &'b N) -> Foo;
	// }
	//
	// We wish to decide if those two method types are compatible.
	//
	// We start out with trait_to_impl_substs, that maps the trait
	// type parameters to impl type parameters. This is taken from the
	// impl trait reference:
	//
	// trait_to_impl_substs = {'t => 'j, T => &'i U, Self => Foo}
	//
	// We create a mapping `dummy_substs` that maps from the impl type
	// parameters to fresh types and regions. For type parameters,
	// this is the identity transform, but we could as well use any
	// placeholder types. For regions, we convert from bound to free
	// regions (Note: but only early-bound regions, i.e., those
	// declared on the impl or used in type parameter bounds).
	//
	// impl_to_placeholder_substs = {'i => 'i0, U => U0, N => N0 }
	//
	// Now we can apply placeholder_substs to the type of the impl method
	// to yield a new function type in terms of our fresh, placeholder
	// types:
	//
	// <'b> fn(t: &'i0 U0, m: &'b) -> Foo
	//
	// We now want to extract and substitute the type of the *trait*
	// method and compare it. To do so, we must create a compound
	// substitution by combining trait_to_impl_substs and
	// impl_to_placeholder_substs, and also adding a mapping for the method
	// type parameters. We extend the mapping to also include
	// the method parameters.
	//
	// trait_to_placeholder_substs = { T => &'i0 U0, Self => Foo, M => N0 }
	//
	// Applying this to the trait method type yields:
	//
	// <'a> fn(t: &'i0 U0, m: &'a) -> Foo
	//
	// This type is also the same but the name of the bound region ('a
	// vs 'b). However, the normal subtyping rules on fn types handle
	// this kind of equivalency just fine.
	//
	// We now use these substitutions to ensure that all declared bounds are
	// satisfied by the implementation's method.
	//
	// We do this by creating a parameter environment which contains a
	// substitution corresponding to impl_to_placeholder_substs. We then build
	// trait_to_placeholder_substs and use it to convert the predicates contained
	// in the trait_m.generics to the placeholder form.
	//
	// Finally we register each of these predicates as an obligation in
	// a fresh FulfillmentCtxt, and invoke select_all_or_error.
	// Create mapping from impl to placeholder.
	let impl_to_placeholder_substs = InternalSubsts::identity_for_item(tcx, impl_m.def_id);
	// Create mapping from trait to placeholder.
	let trait_to_placeholder_substs =
	impl_to_placeholder_substs.rebase_onto(tcx, impl_m.container.id(), trait_to_impl_substs);
	debug!("compare_impl_method: trait_to_placeholder_substs={:?}", trait_to_placeholder_substs);
	let impl_m_generics = tcx.generics_of(impl_m.def_id);
	let trait_m_generics = tcx.generics_of(trait_m.def_id);
	let impl_m_predicates = tcx.predicates_of(impl_m.def_id);
	let trait_m_predicates = tcx.predicates_of(trait_m.def_id);
	// Check region bounds.
	check_region_bounds_on_impl_item(
	tcx,
	impl_m_span,
	impl_m,
	trait_m,
	&trait_m_generics,
	&impl_m_generics,
	)?;
	// Create obligations for each predicate declared by the impl
	// definition in the context of the trait's parameter
	// environment. We can't just use `impl_env.caller_bounds`,
	// however, because we want to replace all late-bound regions with
	// region variables.
	let impl_predicates = tcx.predicates_of(impl_m_predicates.parent.unwrap());
	let mut hybrid_preds = impl_predicates.instantiate_identity(tcx);
	debug!("compare_impl_method: impl_bounds={:?}", hybrid_preds);
	// This is the only tricky bit of the new way we check implementation methods
	// We need to build a set of predicates where only the method-level bounds
	// are from the trait and we assume all other bounds from the implementation
	// to be previously satisfied.
	//
	// We then register the obligations from the impl_m and check to see
	// if all constraints hold.
	hybrid_preds
	.predicates
	.extend(trait_m_predicates.instantiate_own(tcx, trait_to_placeholder_substs).predicates);
	// Construct trait parameter environment and then shift it into the placeholder viewpoint.
	// The key step here is to update the caller_bounds's predicates to be
	// the new hybrid bounds we computed.
	let normalize_cause = traits::ObligationCause::misc(impl_m_span, impl_m_hir_id);
	let param_env = ty::ParamEnv::new(
	tcx.intern_predicates(&hybrid_preds.predicates),
	Reveal::UserFacing,
	hir::Constness::NotConst,
	);
	let param_env =
	traits::normalize_param_env_or_error(tcx, impl_m.def_id, param_env, normalize_cause);
	tcx.infer_ctxt().enter(|infcx| {
	let inh = Inherited::new(infcx, impl_m.def_id.expect_local());
	let infcx = &inh.infcx;
	debug!("compare_impl_method: caller_bounds={:?}", param_env.caller_bounds());
	let mut selcx = traits::SelectionContext::new(&infcx);
	let impl_m_own_bounds = impl_m_predicates.instantiate_own(tcx, impl_to_placeholder_substs);
	for (predicate, span) in iter::zip(impl_m_own_bounds.predicates, impl_m_own_bounds.spans) {
	let normalize_cause = traits::ObligationCause::misc(span, impl_m_hir_id);
	let traits::Normalized { value: predicate, obligations } =
	traits::normalize(&mut selcx, param_env, normalize_cause, predicate);
	inh.register_predicates(obligations);
	let mut cause = cause.clone();
	cause.span = span;
	inh.register_predicate(traits::Obligation::new(cause, param_env, predicate));
	}
	// We now need to check that the signature of the impl method is
	// compatible with that of the trait method. We do this by
	// checking that `impl_fty <: trait_fty`.
	//
	// FIXME. Unfortunately, this doesn't quite work right now because
	// associated type normalization is not integrated into subtype
	// checks. For the comparison to be valid, we need to
	// normalize the associated types in the impl/trait methods
	// first. However, because function types bind regions, just
	// calling `normalize_associated_types_in` would have no effect on
	// any associated types appearing in the fn arguments or return
	// type.
	// Compute placeholder form of impl and trait method tys.
	let tcx = infcx.tcx;
	let mut wf_tys = FxHashSet::default();
	let (impl_sig, _) = infcx.replace_bound_vars_with_fresh_vars(
	impl_m_span,
	infer::HigherRankedType,
	tcx.fn_sig(impl_m.def_id),
	);
	let impl_sig =
	inh.normalize_associated_types_in(impl_m_span, impl_m_hir_id, param_env, impl_sig);
	let impl_fty = tcx.mk_fn_ptr(ty::Binder::dummy(impl_sig));
	debug!("compare_impl_method: impl_fty={:?}", impl_fty);
	// First liberate late bound regions and subst placeholders
	let trait_sig = tcx.liberate_late_bound_regions(impl_m.def_id, tcx.fn_sig(trait_m.def_id));
	let trait_sig = trait_sig.subst(tcx, trait_to_placeholder_substs);
	let trait_sig =
	inh.normalize_associated_types_in(impl_m_span, impl_m_hir_id, param_env, trait_sig);
	// Add the resulting inputs and output as well-formed.
	wf_tys.extend(trait_sig.inputs_and_output.iter());
	let trait_fty = tcx.mk_fn_ptr(ty::Binder::dummy(trait_sig));
	debug!("compare_impl_method: trait_fty={:?}", trait_fty);
	let sub_result = infcx.at(&cause, param_env).sup(trait_fty, impl_fty).map(
	|InferOk { obligations, .. }| {
	// FIXME: We'd want to keep more accurate spans than "the method signature" when
	// processing the comparison between the trait and impl fn, but we sadly lose them
	// and point at the whole signature when a trait bound or specific input or output
	// type would be more appropriate. In other places we have a `Vec<Span>`
	// corresponding to their `Vec<Predicate>`, but we don't have that here.
	// Fixing this would improve the output of test `issue-83765.rs`.
	inh.register_predicates(obligations);
	},
	);
	if let Err(terr) = sub_result {
	debug!("sub_types failed: impl ty {:?}, trait ty {:?}", impl_fty, trait_fty);
	let (impl_err_span, trait_err_span) =
	extract_spans_for_error_reporting(&infcx, &terr, &cause, impl_m, trait_m);
	cause.span = impl_err_span;
	let mut diag = struct_span_err!(
	tcx.sess,
	cause.span(tcx),
	E0053,
	"method `{}` has an incompatible type for trait",
	trait_m.name
	);
	match &terr {
	TypeError::ArgumentMutability(0) | TypeError::ArgumentSorts(_, 0)
	if trait_m.fn_has_self_parameter =>
	{
	let ty = trait_sig.inputs()[0];
	let sugg = match ExplicitSelf::determine(ty, |_| ty == impl_trait_ref.self_ty())
	{
	ExplicitSelf::ByValue => "self".to_owned(),
	ExplicitSelf::ByReference(_, hir::Mutability::Not) => "&self".to_owned(),
	ExplicitSelf::ByReference(_, hir::Mutability::Mut) => {
	"&mut self".to_owned()
	}
	_ => format!("self: {}", ty),
	};
	// When the `impl` receiver is an arbitrary self type, like `self: Box<Self>`, the
	// span points only at the type `Box<Self`>, but we want to cover the whole
	// argument pattern and type.
	let span = match tcx.hir().expect_impl_item(impl_m.def_id.expect_local()).kind {
	ImplItemKind::Fn(ref sig, body) => tcx
	.hir()
	.body_param_names(body)
	.zip(sig.decl.inputs.iter())
	.map(|(param, ty)| param.span.to(ty.span))
	.next()
	.unwrap_or(impl_err_span),
	_ => bug!("{:?} is not a method", impl_m),
	};
	diag.span_suggestion(
	span,
	"change the self-receiver type to match the trait",
	sugg,
	Applicability::MachineApplicable,
	);
	}
	TypeError::ArgumentMutability(i) | TypeError::ArgumentSorts(_, i) => {
	if trait_sig.inputs().len() == *i {
	// Suggestion to change output type. We do not suggest in `async` functions
	// to avoid complex logic or incorrect output.
	match tcx.hir().expect_impl_item(impl_m.def_id.expect_local()).kind {
	ImplItemKind::Fn(ref sig, _)
	if sig.header.asyncness == hir::IsAsync::NotAsync =>
	{
	let msg = "change the output type to match the trait";
	let ap = Applicability::MachineApplicable;
	match sig.decl.output {
	hir::FnRetTy::DefaultReturn(sp) => {
	let sugg = format!("-> {} ", trait_sig.output());
	diag.span_suggestion_verbose(sp, msg, sugg, ap);
	}
	hir::FnRetTy::Return(hir_ty) => {
	let sugg = trait_sig.output().to_string();
	diag.span_suggestion(hir_ty.span, msg, sugg, ap);
	}
	};
	}
	_ => {}
	};
	} else if let Some(trait_ty) = trait_sig.inputs().get(*i) {
	diag.span_suggestion(
	impl_err_span,
	"change the parameter type to match the trait",
	trait_ty.to_string(),
	Applicability::MachineApplicable,
	);
	}
	}
	_ => {}
	}
	infcx.note_type_err(
	&mut diag,
	&cause,
	trait_err_span.map(|sp| (sp, "type in trait".to_owned())),
	Some(infer::ValuePairs::Types(ExpectedFound {
	expected: trait_fty,
	found: impl_fty,
	})),
	&terr,
	false,
	);
	diag.emit();
	return Err(ErrorReported);
	}
	// Check that all obligations are satisfied by the implementation's
	// version.
	let errors = inh.fulfillment_cx.borrow_mut().select_all_or_error(&infcx);
	if !errors.is_empty() {
	infcx.report_fulfillment_errors(&errors, None, false);
	return Err(ErrorReported);
	}
	// Finally, resolve all regions. This catches wily misuses of
	// lifetime parameters.
	let fcx = FnCtxt::new(&inh, param_env, impl_m_hir_id);
	fcx.regionck_item(impl_m_hir_id, impl_m_span, wf_tys);
	Ok(())
	})
	}

The interesting part is here though:

rust/compiler/rustc_typeck/src/check/compare_method.rs

Lines 257 to 278 in e069a71

	let (impl_sig, _) = infcx.replace_bound_vars_with_fresh_vars(
	impl_m_span,
	infer::HigherRankedType,
	tcx.fn_sig(impl_m.def_id),
	);
	let impl_sig =
	inh.normalize_associated_types_in(impl_m_span, impl_m_hir_id, param_env, impl_sig);
	let impl_fty = tcx.mk_fn_ptr(ty::Binder::dummy(impl_sig));
	debug!("compare_impl_method: impl_fty={:?}", impl_fty);
	// First liberate late bound regions and subst placeholders
	let trait_sig = tcx.liberate_late_bound_regions(impl_m.def_id, tcx.fn_sig(trait_m.def_id));
	let trait_sig = trait_sig.subst(tcx, trait_to_placeholder_substs);
	let trait_sig =
	inh.normalize_associated_types_in(impl_m_span, impl_m_hir_id, param_env, trait_sig);
	// Add the resulting inputs and output as well-formed.
	wf_tys.extend(trait_sig.inputs_and_output.iter());
	let trait_fty = tcx.mk_fn_ptr(ty::Binder::dummy(trait_sig));
	debug!("compare_impl_method: trait_fty={:?}", trait_fty);
	let sub_result = infcx.at(&cause, param_env).sup(trait_fty, impl_fty).map(

This converts the methods defined in the trait implementation and the definition to higher order function pointers, and then checks that the one from the implementation is a subtype of the one from the definition, which brings us back to #25860

[thomcc]

Is this fixed by implied_bounds_entailment? All the reproducers here seem to be, and my (admittedly rudimentary) understanding is that it would be expected to be?

[lcnr]

yes, it should be, cc #105572

[lcnr]

this has been fixed in #117984, marking as E-needs-test. It can then be closed

[lcnr]

already have tests added, cc #117984