intern predicates, introduce forall/implies

[nikomatsakis]

TL;DR

Refactor ty::Predicate to better align with how chalk handles things and to enable what we need for GATs. Highlights:

Goals:

• Introduce forall and implication predicates so we can model forall<T> { if (T: Debug) { Vec<T>: Debug } }.
• Remove the "poly" from all the other kinds of predicates (e.g., Predicate::Trait would be an ordinary TraitRef)
• Change Predicate<'tcx> to an interned reference (&'tcx PredicateKind<'tcx>) to enable recursion

Steps

• Enable recursive predicates (this work has started on a branch of mine and is basically done)
  • Rename Predicate to PredicateKind, introduce type Predicate = PredicateKind
  • Introduce interned pool for Predicate and alter type Predicate<'tcx> to &'tcx PredicateKind<'tcx>
• Introduce forall:
  • Introduce forall predicate goals and integrate into the fulfillment context
    • hmm -- this may require finishing up the universe integration work, which is semi-blocked
  • Remove the mandatory binder on trait predicates and other predicates and use forall goals instead where needed
• Introduce implication predicates, which extend the ParamEnv with new predicates

Mentors or Reviewers

nikomatsakis will mentor

[nikomatsakis]

Zulip thread

[eddyb]

@rustbot second

[nikomatsakis]

FCP closed! See #72055 for initial implementation steps.