infinite recursion with TAIT and `replace_opaque_types_with_inference_vars` in project

[lcnr]

#![feature(type_alias_impl_trait)]

type Foo<'a> = impl Fn() -> Foo<'a>;

fn crash<'a>(_: &'a (), x: Foo<'a>) -> Foo<'a> {
    x
}

fn main() {}

this causes rustc to freeze. This is similar to

rust/tests/ui/type-alias-impl-trait/issue-53398-cyclic-types.rs

Lines 1 to 10 in c50c62d

	#![feature(type_alias_impl_trait)]
	type Foo = impl Fn() -> Foo;
	fn foo() -> Foo {
	//~^ ERROR: overflow evaluating the requirement
	foo
	}
	fn main() {}

The only reason that this test does not hang is the following hack in fulfillment

rust/compiler/rustc_trait_selection/src/traits/fulfill.rs

Lines 711 to 733 in c50c62d

	if obligation.predicate.is_global() {
	// no type variables present, can use evaluation for better caching.
	// FIXME: consider caching errors too.
	if self.selcx.infcx.predicate_must_hold_considering_regions(obligation) {
	if let Some(key) = ProjectionCacheKey::from_poly_projection_predicate(
	&mut self.selcx,
	project_obligation.predicate,
	) {
	// If `predicate_must_hold_considering_regions` succeeds, then we've
	// evaluated all sub-obligations. We can therefore mark the 'root'
	// obligation as complete, and skip evaluating sub-obligations.
	self.selcx
	.infcx
	.inner
	.borrow_mut()
	.projection_cache()
	.complete(key, EvaluationResult::EvaluatedToOk);
	}
	return ProcessResult::Changed(vec![]);
	} else {
	debug!("Does NOT hold: {:?}", obligation);
	}
	}

because of this hack we only try to prove <Foo as FnOnce<()>>::Output == Foo using evaluate_obligation which uses DefiningAnchor::Bubble instead of the DefiningAnchor::Bind used by typeck and fulfill directly.

The reason this breaks when using DefiningAnchor::Bind is the following:

we call project_and_unify_type for <Foo as FnOnce<()>>::Output == Foo which normalizes <Foo as FnOnce<()>>::Output to Foo.

The issue is that we then replace Foo with a new inference variable (if we use DefiningAnchor::Bind) ?n and add the item bounds of Foo as obligations on that new inference variable:

rust/compiler/rustc_trait_selection/src/traits/project.rs

Lines 280 to 286 in c50c62d

	let InferOk { value: actual, obligations: new } =
	selcx.infcx.replace_opaque_types_with_inference_vars(
	actual,
	obligation.cause.body_id,
	obligation.cause.span,
	obligation.param_env,
	);

This adds a new obligation <?n as FnOnce<()>>::Output == Foo to the fulfillment context, even though ?n was already constrained to Foo again. The easiest fix is to resolve inference variables in obligations before adding them to the fulfillment context.

[compiler-errors]

The easiest fix is to resolve inference variables in obligations before adding them to the fulfillment context.

We already do this though, unless you meant something different--

rust/compiler/rustc_trait_selection/src/traits/fulfill.rs

Lines 118 to 128 in c50c62d

	impl<'tcx> TraitEngine<'tcx> for FulfillmentContext<'tcx> {
	fn register_predicate_obligation(
	&mut self,
	infcx: &InferCtxt<'tcx>,
	obligation: PredicateObligation<'tcx>,
	) {
	// this helps to reduce duplicate errors, as well as making
	// debug output much nicer to read and so on.
	let obligation = infcx.resolve_vars_if_possible(obligation);
	debug!(?obligation, "register_predicate_obligation");

[compiler-errors]

Ah, but ObligationForest::register_obligation_at skips over that code, oof

[oli-obk]

This now reports an overflow instead of freezing rustc or otherwise crashing. It's still wrong, but easier to debug

[matthiaskrgr]

seems this does not hang anymore
rustc 1.84.0-nightly (59cec72a5 2024-11-08)