Cycle detected when computing whether impls specialize one another, across crate boundaries

[patrick-gu]

I tried this code (note: the crate name is bug, and this only occurs when the files are separate):

In src/lib.rs:

pub trait Reducible {
    type Reduced;
}

pub struct Base;

pub struct Higher;

impl Reducible for Higher {
    type Reduced = Base;
}

pub trait Reduce<R> {}

impl<T> Reduce<Base> for T {}

impl<T, R> Reduce<R> for T
where
    R: Reducible,
    T: Reduce<R::Reduced>,
{
}

pub fn reduce<R>(_: R)
where
    (): Reduce<R>,
{
}

In src/main.rs:

fn main() {
    bug::reduce(bug::Higher);
}

I expected to see this happen: Code compiles successfully, as it would if everything was in main.rs.

Instead, this happened: the compiler emits an error:

error[E0391]: cycle detected when computing whether impls specialize one another
  --> C:\path\to\bug\src\lib.rs:17:1
   |
17 | / impl<T, R> Reduce<R> for T
18 | | where
19 | |     R: Reducible,
20 | |     T: Reduce<R::Reduced>,
21 | | {
22 | | }
   | |_^
   |
   = note: ...which immediately requires computing whether impls specialize one another again
note: cycle used when type-checking `main`
  --> src\main.rs:1:1
   |
1  | fn main() {
   | ^^^^^^^^^

For more information about this error, try `rustc --explain E0391`.
error: could not compile `bug` due to previous error

Meta

rustc --version --verbose:

rustc 1.56.0 (09c42c458 2021-10-18)
binary: rustc
commit-hash: 09c42c45858d5f3aedfa670698275303a3d19afa
commit-date: 2021-10-18
host: x86_64-pc-windows-msvc
release: 1.56.0
LLVM version: 13.0.0

This also appears to be present on 1.58.0-nightly 2021-11-10, commit hash 82af160.

[patrick-gu]

This check seems to allow the code to compile when the impls are in the same crate:

rust/compiler/rustc_trait_selection/src/traits/specialize/mod.rs

Lines 123 to 129 in 6bda5b3

	// The feature gate should prevent introducing new specializations, but not
	// taking advantage of upstream ones.
	let features = tcx.features();
	let specialization_enabled = features.specialization || features.min_specialization;
	if !specialization_enabled && (impl1_def_id.is_local() || impl2_def_id.is_local()) {
	return false;
	}

[patrick-gu]

It seems that the cause of the issue is that, when trying to fulfil the bound (): Reduce<Higher>, it is checked whether the first impl specializes the second impl:

rust/compiler/rustc_trait_selection/src/traits/select/mod.rs

Lines 1693 to 1706 in 6bda5b3

	(&ImplCandidate(other_def), &ImplCandidate(victim_def)) => {
	// See if we can toss out `victim` based on specialization.
	// This requires us to know *for sure* that the `other` impl applies
	// i.e., `EvaluatedToOk`.
	//
	// FIXME(@lcnr): Using `modulo_regions` here seems kind of scary
	// to me but is required for `std` to compile, so I didn't change it
	// for now.
	let tcx = self.tcx();
	if other.evaluation.must_apply_modulo_regions() {
	if tcx.specializes((other_def, victim_def)) {
	return true;
	}
	}

Since specialization could be enabled, the compiler tries to determine if it is present:

rust/compiler/rustc_trait_selection/src/traits/specialize/mod.rs

Lines 131 to 171 in 6bda5b3

	// We determine whether there's a subset relationship by:
	//
	// - replacing bound vars with placeholders in impl1,
	// - assuming the where clauses for impl1,
	// - instantiating impl2 with fresh inference variables,
	// - unifying,
	// - attempting to prove the where clauses for impl2
	//
	// The last three steps are encapsulated in `fulfill_implication`.
	//
	// See RFC 1210 for more details and justification.
	// Currently we do not allow e.g., a negative impl to specialize a positive one
	if tcx.impl_polarity(impl1_def_id) != tcx.impl_polarity(impl2_def_id) {
	return false;
	}
	// create a parameter environment corresponding to a (placeholder) instantiation of impl1
	let penv = tcx.param_env(impl1_def_id);
	let impl1_trait_ref = tcx.impl_trait_ref(impl1_def_id).unwrap();
	// Create an infcx, taking the predicates of impl1 as assumptions:
	tcx.infer_ctxt().enter(|infcx| {
	// Normalize the trait reference. The WF rules ought to ensure
	// that this always succeeds.
	let impl1_trait_ref = match traits::fully_normalize(
	&infcx,
	FulfillmentContext::new(),
	ObligationCause::dummy(),
	penv,
	impl1_trait_ref,
	) {
	Ok(impl1_trait_ref) => impl1_trait_ref,
	Err(err) => {
	bug!("failed to fully normalize {:?}: {:?}", impl1_trait_ref, err);
	}
	};
	// Attempt to prove that impl2 applies, given all of the above.
	fulfill_implication(&infcx, penv, impl1_trait_ref, impl2_def_id).is_ok()
	})

In trying to fulfill the trait obligations, the bounds on the second candidate are evaluated again:

rust/compiler/rustc_trait_selection/src/traits/select/mod.rs

Lines 961 to 973 in 6bda5b3

	/// Further evaluates `candidate` to decide whether all type parameters match and whether nested
	/// obligations are met. Returns whether `candidate` remains viable after this further
	/// scrutiny.
	#[instrument(
	level = "debug",
	skip(self, stack),
	fields(depth = stack.obligation.recursion_depth)
	)]
	fn evaluate_candidate<'o>(
	&mut self,
	stack: &TraitObligationStack<'o, 'tcx>,
	candidate: &SelectionCandidate<'tcx>,
	) -> Result<EvaluationResult, OverflowError> {

Which requires deciding between the two impls:

rust/compiler/rustc_trait_selection/src/traits/select/mod.rs

Lines 1525 to 1543 in 6bda5b3

	///////////////////////////////////////////////////////////////////////////
	// WINNOW
	//
	// Winnowing is the process of attempting to resolve ambiguity by
	// probing further. During the winnowing process, we unify all
	// type variables and then we also attempt to evaluate recursive
	// bounds to see if they are satisfied.
	/// Returns `true` if `victim` should be dropped in favor of
	/// `other`. Generally speaking we will drop duplicate
	/// candidates and prefer where-clause candidates.
	///
	/// See the comment for "SelectionCandidate" for more details.
	fn candidate_should_be_dropped_in_favor_of(
	&mut self,
	victim: &EvaluatedCandidate<'tcx>,
	other: &EvaluatedCandidate<'tcx>,
	needs_infer: bool,
	) -> bool {

Creating a loop.

[patrick-gu]

A similar problem is present in 1.57.0, but not in 1.56.0.

src/lib.rs:

pub trait Change<T> {
    type Changed;
}

impl<T> Change<T> for () {
    type Changed = T;
}

pub trait Split {
    type First;
    type Rest;
}

pub trait Combine<T> {}

impl<U> Combine<()> for U {}

impl<T, U> Combine<U> for T
where
    U: Split,
    Self: Change<U::First>,
    <Self as Change<U::First>>::Changed: Combine<U::Rest>,
{
}

pub fn combine<T>(_: T)
where
    (): Combine<T>,
{
}

src/main.rs:

fn main() {
    bug::combine(());
}

Error message:

error[E0391]: cycle detected when computing whether impls specialize one another
  --> C:\path\to\bug\src\lib.rs:18:1
   |
18 | / impl<T, U> Combine<U> for T
19 | | where
20 | |     U: Split,
21 | |     Self: Change<U::First>,
22 | |     <Self as Change<U::First>>::Changed: Combine<U::Rest>,
23 | | {
24 | | }
   | |_^
   |
   = note: ...which requires evaluating trait selection obligation `(): bug::Combine<^1_0>`...
   = note: ...which again requires computing whether impls specialize one another, completing the cycle
note: cycle used when type-checking `main`
  --> src\main.rs:1:1
   |
1  | fn main() {
   | ^^^^^^^^^

For more information about this error, try `rustc --explain E0391`.

[patrick-gu]

@rustbot label: +A-specialization +A-traits +regression-from-stable-to-stable

[apiraino]

@patrick-gu for the code in the first comment can you identify a previous version of Rust that does not reproduce the issue? I've tried backtracking to really old nightlies and I could not find a version that does not reproduce.

I confirm that the snippet in this comment reproduce the error in 1.57 and not 1.56.1

[patrick-gu]

@apiraino The code in the first comment compiles on 1.8.0 but not on 1.9.0. The error message for 1.9.0 is:

error: Could not compile `bug`.

Caused by:
  Process didn't exit successfully: `rustc src/main.rs --crate-name bug --crate-type bin -g --out-dir /path/to/bug/target/debug --emit=dep-info,link -L dependency=/path/to/bug/target/debug -L dependency=/path/to/bug/target/debug/deps --extern bug=/path/to/bug/target/debug/libbug.rlib` (signal: 11, SIGSEGV: invalid memory reference)

with no mention of a cycle.

In 1.22.0 and after, the error message mentions a cycle:

error[E0391]: unsupported cyclic reference between types/traits detected
  --> /path/to/bug/src/lib.rs:17:1
   |
17 | / impl<T, R> Reduce<R> for T
18 | | where
19 | |     R: Reducible,
20 | |     T: Reduce<R::Reduced>,
21 | | {
22 | | }
   | |_^ cyclic reference
   |
note: the cycle begins when computing whether impls specialize one another...
  --> /path/to/bug/src/lib.rs:17:1
   |
17 | / impl<T, R> Reduce<R> for T
18 | | where
19 | |     R: Reducible,
20 | |     T: Reduce<R::Reduced>,
21 | | {
22 | | }
   | |_^
   = note: ...which then again requires computing whether impls specialize one another, completing the cycle.

[apiraino]

WG-prioritization assigning priority (Zulip discussion) to this old issue. Can only reproduce the miscompile on the stable rustc channel and not on beta or nightly channel (weird).

@rustbot label -I-prioritize +P-low