Only represent consts in types using ty::Const

[lcnr]

What is this

This is a design document for const generics. Any discussions about its content should be on zulip. The conclusions of these discussions should then be edited back into this issue. Please do not post any comments directly in this issue.

Impact

This implementation strategy relies on the following issues:

• Structural equality #29

This implementation strategy would fix the following issues:

• Self-referential where-clauses #36 Anonymous constants in binders #35 Unused generic parameters of anonymous constants #33 Leaking implementation details during unification #30 Merging impls to be exhaustive #26

This implementation strategy would help with the following issues, but will not fix them by itself:

• Constraining generic parameters #23

This implementation strategy should not negatively impact any other issue.

Design

Looking at the above topics, there are two core issues this proposal intends to fix:

• looking into anonymous constants requires us to typeck them, which means we have to wait until variance computation is finished and generally have to be careful around cycles.
• typechecking anonymous constants does a lot of implicit stuff, it can introduce auto borrows, coercions, generic parameters not mentioned explicitly and so on. This makes dealing with generic constants quite unpleasant.

The idea is that when converting a generic constant in the HIR to a ty::Const, we directly lower its body to ty::ConstKind::Expr and remove ty::ConstKind::Unevaluated. If a constant does not explicitly mention any generic parameter, we continue to not supply it any generics and are able to evaluate it eagerly before creating its ty::Const.

The new representation of ty::Const would be:

pub enum ConstKind<'tcx> {
    Param(ParamConst),
    Infer(InferConst<'tcx>),
    Bound(DebruijnIndex, BoundVar),
    Placeholder(PlaceholderConst<'tcx>),
    // Used to both represent integer values and ZST.
    // ZST are used for function types.
    //
    // Previously `Valtree::Leaf`.
    Value(ScalarInt),
    // Used for adts and stuff
    //
    // Previously `Valtree::Branch`.
    Branch(&'tcx [ty::Const<'tcx>]),
    // Used for opaque named constants.
    //
    // Previously a part of `ty::ConstKind::Unevaluated`.
    Named(DefId, SubstsRef<'tcx>),
    // Not yet evaluated expression taken from `abstract_const::Node`.
    Expr(Expr<'tcx>),
    Error(DelaySpanBugEmitted),
}

pub enum Expr<'tcx> {
    Binop(BinOp, ty::Const<'tcx>, ty::Const<'tcx>),
    UnaryOp(UnOp, ty::Const<'tcx>),
    FunctionCall(ty::Const<'tcx>, &'tcx List<ty::Const<'tcx>>),
    Cast(CastKind, ty::Const<'tcx>, Ty<'tcx>),
}

We either never typecheck generic anonymous constants by themselves, which makes #36 trivial, as they don't matter while everything happens in the same query.

Alternatively, we try to typecheck them once the parent item already finished, avoiding query cycles there. In this case we still have to deal with #36 using some other means.

Lowering from HIR to ty::Const

For the eager conversion we need to implement and maintain a new lowering from hir::Expr to ty::Const. While that one should mostly be trivial to add as long as we sufficiently restrict the allowed expressions, this does add additional complexity to the compiler which we wont really be able to remove in the future.

It is still unclear how that deals with constants in function signatures:

use std::convert::identity;
fn foo<const N: usize>() -> [u8; identity(N)] { todo!() }

The return type of foo would be lowered in a way which contains inference variables.
So we would have to lower constants and then require all inference variables to be resolved.
It is also unclear how exactly that should deal with region inference, when using something like
func(&my_value).

Evaluating ty::Const

As we have to evaluate ty::Const without them being typechecked, we can't just use the existing CTFE for this. We would therefore have to add some special evaluation code for Expr, though that could share its implementation with CTFE.

Once we interact with an opaque constant or a function, we can just use ordinary CTFE again.

Lowering concrete consts to ty::Const

This proposal would start by only lowering constants explicitly mentioning a generic
parameter to ty::Const while keeping the current setup of typechecking and evaluating them
separately for concrete constants. For consistency reasons - and for generic const expressions -
it would be nice to also lower concrete constants to ty::Const.

This would be a breaking change as currently arbitrary expressions are allowed in constants.
This is definitely something we could enable via an edition however.

Generic const expressions and bidirectional inference

With this proposal, it is possible for type inference to flow out of generic constants, allowing the following to compile.

fn generic_len<const N: usize, const ARR: [u8; N]>() {}

fn main() {
    generic_len::<_, [0; 3]>();
}

This is only possible as long as we typecheck generic constants together with their parent.
Unless we lower all constants in type to ty::Const directly this wouldn't work too well:

fn generic<T, const VALUE: T>() {}

fn main() {
    // Unless information can flow both into and out of anonymous constants
    // during typeck, this would not compile.
    generic<Vec<_>, { [0i32].into_iter().collect() }>()
}