implement `is_coinductive` chalk callback

[nikomatsakis]

The chalk integrate includes a is_coinductive callback that indicates whether a particular goal is co-inductive:

rust/src/librustc_traits/chalk_context.rs

Lines 132 to 135 in e1643a8

	/// True if this is a coinductive goal -- e.g., proving an auto trait.
	fn is_coinductive(&self, _goal: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>) -> bool {
	unimplemented!()
	}

A co-inductive goal is one of the following (see the corresponding chalk code for a kind of reference):

• proving whether an auto-trait is implemented
• "trait" well-formedness goals (not the type variant)

The existing trait solver doesn't have this notion of "well-formed trait goals" -- but it does have code related to testing about auto-traits that gives a few clues as to how to do the first step.

[nikomatsakis]

Mentoring instructions

Looking at the chalk implementation, we want this function to match on goals that are:

• domain goals of "auto traits" (test with trait_is_auto)
• domain goals for "trait well-formedness conditions" (this variant)
• quantified goals that meet the coinductive criteria -- in chalk, we only match forall goals, but actually I imagine the same is true for exist goals (though rust never really uses those...)

This function is given a "canonical goal", so the first step is that we want to just look at the canonical value (e.g., goal.value). It's fine to just skip past the canonical binders here because the stuff we care about (e.g., the trait name) is not something you can quantify over (i.e., you can't write forall<trait T> { Implemented(u32: T) }). So just match on goal.value and look for the various cases enumerated above, something like:

fn is_coinductive(&self, goal: &Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>) -> bool {
  let mut goal = &goal.value;
  loop {
    match goal {
      GoalKind::DomainGoal(DomainGoal::WellFormed(WellFormed::Trait(..))) => return true,
      GoalKind::DomainGoal(DomainGoal::Implemented(trait_predicate) => {
          return self.tcx.trait_is_auto(trait_predicate.def_id),
      }
      GoalKind::Quantified(_, bound_goal) => goal = bound_goal.skip_binder(),
      _ => return false,
    }
  }
}

[sunjay]

Hello I'd like to work on this!

[sunjay]

I see that @scalexm is working on this right now. Sorry I haven't been around. I'll let them finish it since they have already started. My apologies again and thanks for picking up my slack! :)