owned this note changed 5 years ago
Published Linked with GitHub

const wf bounds implementation

This is a way to fix https://github.com/rust-lang/rust/issues/68436#issuecomment-663190861, the goal is to pretty much implement proposal 2.

One problem is dealing with desugarings. Example:

fn test<T> where [u8 {
    let mut n = 0;
    for i in 0..std::mem::size_of::<T>() {
        n += 1;
    }
    n
}], {
    let _ = [0; {
        let mut n = 0;
        let mut __iter = (0..std::mem::size_of::<T>()).into_iter();
        while let Some(i) in __iter.next() {
            n += 1;
        }
        n
    }];
}

I do not think that the const in the where clause should imply the const in function body here. Proving equality here is impossible in the general case and any non general solution puts a stability requirement on how exactly for-loops are implemented.

I therefore think we should only allow 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.

Examples of what's allowed under this proposal: 4 + N, N * 2, N.saturating_sub(1) + 10, std::mem::size_of::<T>(), T::ASSOC + 10 and foo::<T>() + bar::<T, N>() - 3.

We would forbid things like if N > 0 { 100 / N } else { 10 } and the expression used in the above example for now (and recommend wrapping them inside of a const fn instead). If expressions like this end up being fine after we implemented this, it should always be possible to allow them later.

We do not yet add a special syntax for const wf bounds for now. If required, we could use something like where (1 + N) in the future.


Implementation

We already have a PredicateKind::ConstEvaluatable for every anonymous constant during typeck at the moment. Instead of having to prove this predicate for every anon const, consts in where bounds and function signatures get added to the caller_bounds of the relevant ParamEnv instead.

If we now want to check PredicateKind::ConstEvaluatable for a const inside of the function, we first check if it depends on any generic parameter (probably using something similar to #74595). If so, we search for an equal const in the ParamEnv.

To implement this comparision we will convert MIR (mir_const or mir_validated, so optimizations don't affect this) to an abstract term tree and then relate that term tree with the term trees of all PredicateKind::ConstEvaluatable in the param_env.

The conversion from MIR to an abstract term tree would be a query akin to query anon_to_abstract(DefId) -> Option<AbstractConst>.

Select a repo