Implement const equality and const wf

[lcnr]

Proposal

What

The goal is to implement a way to unify different ConstKind::Unevaluated
and to check that all possible instances of const expressions evaluate sucessfully.

The implementation of this PR will not be used with feature(min_const_generics) and does not block its stabilization.

It will however extend the possibilities and expressivity of const generics by a huge amount. For example the following will be possible thanks to these changes:

impl<T, const N: usize> [T; N] {
    fn split_first(self) -> (T, [T; N - 1]) {
        let rest: [T; N - 1] = todo!();
        let fst: T;
        todo!();
        (fst, rest)
    }
}

For more details on the intended design, see https://hackmd.io/OZG_XiLFRs2Xmw5s39jRzA?view.

How

Add a query running after mir_const/mir_validated which tries to build an AbstractConst in case the given DefId is a generic anonymous constant.

AbstractConsts will not support all mir expressions and are for now restricted to basic arithmetic, arbitrary function calls, and generic constants.

This restriction is probably fairly close to simply walking the MIR and erroring when encountering a terminator other than Goto, Return, Call or Assert.

The exact subset which is allowed is not yet fully clear and will be fleshed out while implementing this.

These abstract consts will then be used to check if two ConstKind::Unevaluated unify by walking them while considering their substs.

We implement const wf checks by not trying to satisfy ConstEvaluatable predicates for consts mentioned in the function signature or where clauses, but instead adding them to thecaller_bounds of the given item.

When we now have to satisfy a ConstEvaluatable predicate, we check if the given const can be unified with any of the ConstEvaluatable mentioned in the caller_bounds.

Mentors or Reviewers

@oli-obk, for changes to the type system @varkor, @eddyb or @nikomatsakis

Process

The main points of the Major Change Process is as follows:

• File an issue describing the proposal.
• A compiler team member or contributor who is knowledgeable in the area can second by writing @rustbot second.
  • Finding a "second" suffices for internal changes. If however you are proposing a new public-facing feature, such as a -C flag, then full team check-off is required.
  • Compiler team members can initiate a check-off via @rfcbot fcp merge on either the MCP or the PR.
• Once an MCP is seconded, the Final Comment Period begins. If no objections are raised after 10 days, the MCP is considered approved.

You can read more about Major Change Proposals on forge.

Comments

This issue is not meant to be used for technical discussion. There is a Zulip stream for that. Use this issue to leave procedural comments, such as volunteering to review, indicating that you second the proposal (or third, etc), or raising a concern that you would like to be addressed.

[rustbot]

This issue is not meant to be used for technical discussion. There is a Zulip stream for that. Use this issue to leave procedural comments, such as volunteering to review, indicating that you second the proposal (or third, etc), or raising a concern that you would like to be addressed.

[oli-obk]

@rustbot second