Perform validation in const_eval_raw, return valtree from const_eval and decouple MIR-embedded consts from the rest

@eddyb

Right now, we have two "const_eval" queries: const_eval_raw is internal and returns a "by-reference" constant (MPlaceTy) pointing to some global allocation in tcx.alloc_map. And const_eval is the entry point supposed to be used by the rest of the compiler, and it returns a ty::Const, representing some constants of some types "by-value".

Beyond the by-ref to by-val conversion, const_eval also performs validation of the constant to make sure it matches its type. The fact that const_eval_raw does not do that is a constant source of concern for me, e.g. we have some delay_span_bug in that query that basically rely on validation happening eventually and I think some of those might actually be "exploitable" ICEs.

Furthermore, "validated or not" as a question seems separate from "by-val or by-ref". By-val representation is appropriate for many uses of const (in particular around array lengths and pattern matching), but AFAIK never makes any sense for static. We currently force statics to go through ty::Const which seems odd. In fact, in the context of rust-lang/const-eval#42 and #70889, we determined that pattern matching and const generics likely want a different, even more higher-level representation of const values than what we currently have for ty::Const.

So I propose we perform validation in const_eval_raw (whose name should be changed then... maybe const_eval_ref?). Then all these delay_span_bug issues disappear. But the query should still return an MPlaceTy. The idea is that this is the query used for static and other clients (like Miri) that can handle constants of any type and only care about their value at the byte level.

Then we can have a second query which, like current const_eval (new name maybe const_eval_val?), returns ty::Const. This would only be used for things like array lengths, pattern matching, const generics -- things which need a more "structured" view of consts than MPlaceTy provides. I think this would be a great place to put some check that "all allocations reachable from a const are read-only" (as proposed here). Also, my hypothesis is that this query should only ever be called on "structural match" types -- maybe we can assert that? Long-term, this could become the "integer tree" representation @eddyb proposed.

The main technical hurdle is that we have to avoid query cycles. That's why validation was split out into a separate pass in the first place. We can achieve that by stopping validation when we hit a GlobalAlloc::Static(DefId) allocation. I think that is reasonable -- we already stop there if the DefId is in a different crate, so we cannot rely on this for soundness anyway.

@rust-lang/wg-const-eval does this all make sense?

I think if this works it quite be a really nice cleanup, and I would finally be much less bothered by the existence of two queries and two different representations of consts. :D Some time ago I thought we could kill ty::Constand use by-ref consts for everything, and I think @oli-obk even tried that and it went nowhere. But "by-ref" just seemed like the canonical representations of consts, and we ended up with ugly hack where whether we are in a static affects how we convert MPlaceTy into ty::Const... ugh. Now I finally understand what that is the case: we have two different kinds of consumers of consts in the compiler, with different needs, and they should use different queries with different return types. Some are happy with MPlaceTy, others require a more high-level view. I feel like we finally found the right structure to represent this. :D

Here's that design worked out a bit more.

With #73513 we have a ty::consts module that could be a good place for ConstValue and anything else specific to ty::Const (possibly even that type itself, which currently lives in ty::sty).

MCP for the const representation change: rust-lang/compiler-team#323

@oli-obk

@oli-obk did we agree on names for the two different types representing consts and the corresponding queries? For the types I think we toyed with mir::Const and ty::Const, but that does not leave an obviously good name for the queries. eval_const to return mir::Const and eval_const_for_ty to return ty::Const? The latter is also heavily used for pattern matching though, right?

the latter query will be rarely invoked I think. Mostly you'll be using the eval method on ty::Const, so your suggestions are fine with me.

eval_const_to_valtree would be another option (anticipating rust-lang/compiler-team#323).

@oli-obk

My assumption with this plan was that for const items, codegen would work pretty similar to static items, as both have to work with all types (not just valtree-compatible types). But @oli-obk points out in #74949 that e.g. for consts of integer type, we want to emit LLVM integer constants.

Does this also apply to larger valtree-representable types, e.g. a big struct full of integers? We could try to get a valtree and fall back to a raw allocation when that fails. Or maybe we just want to do with this scalars, in which case we could check the layout before deciding if we want to ask for a valtree or a raw allocation.

@oli-obk

In another thread, @oli-obk wrote something that confused me a lot:

Since we still have (and maybe forever will have) ty::Const as an optimization for literals, even in mir::Const, we need to support this anyway, so I think for now we should just do this for statics where it's unambiguous.

I do not understand this statement. Are you saying mir::Const will not just be an AllocId? I think that is the wrong approach, I'd rather make the caller that has these weird special needs (i.e., codegen for consts) deal with "I want raw representation except sometimes", than making everyone deal with it.

@oli-obk, could you clarify? :)

mir::Const is a hypothetical thing that we haven't specified, and I think we both have different pictures of it and are thus talking past each other.

We don't need it at all if I'm understanding your proposal correctly, as it would just be a &'tcx Allocation (or AllocId), so we can use that directly instead of having a wrapper.

What we do need is for the mir::Body to contain both ty::Const (for const generics, unevaluated and literals) as well as &'tcx Allocation/AllocId for successfully evaluated constants. This is the main thing I was talking about, essentially the literal field of mir::Constant.

mir::Const is a hypothetical thing that we haven't specified, and I think we both have different pictures of it and are thus talking past each other.

Yeah that sounds accurate.^^

We don't need it at all if I'm understanding your proposal correctly, as it would just be a &'tcx Allocation (or AllocId), so we can use that directly instead of having a wrapper.

Indeed, I think that's what I had in mind.

What we do need is for the mir::Body to contain both ty::Const (for const generics, unevaluated and literals) as well as &'tcx Allocation/AllocId for successfully evaluated constants. This is the main thing I was talking about, essentially the literal field of mir::Constant.

Okay, so we actually have two places where we do not want to use ty::Const (valtree) or &'tcx Allocation: in mir::Operand, because when constructing we often have a known scalar (or ScalarPair?) value that we want to embed directly without having to create an allocation; and in codegen, because LLVM likewise has a more efficient way to put scalar (ScalarPair?) literals into the code (rather than always using a raw allocation).

I would treat those separately. In particular, codegen is just one of several consumers of the final value of a const, and different backends could have different things that they can more efficiently represent in the target IR. So the LLVM-specific knowledge of what should become an IR literal vs a raw allocation should be handled in codegen.

For mir::Operand::Constant, indeed maybe that's the thing that we should call mir::Const. It would basically be either a valtree or an &Allocation, right? Hm, or it is unevaluated or a paremeter... so a lot like the current ty::ConstValue. So maybe we should have ty::ConstValtree, and then ty::Const is the thing that is "unevaluated or a parameter or an error or a valtree"? And mir::Const would be ty::Const or &Allocation?

But there's still a problem with that... I'd think a ty::Const is something that is evaluable to a valtree, so we shouldn't use it for all general mir::Const that are not evaluated yet. OTOH it might be too confusing to also have an "unevaluated" variant in mir::Const itself. Not sure what is best here. Maybe we need a type like

enum NotSureWhatToCallThis<T> {
  Unevaluated(...),
  Param(...),
  Error(...),
  Evaluated(T)
}

mod ty { type Const = NotSureWhatToCallThis<Valtree>; }
mod mir { type Const = NotSureWhatToCallThis<&'tcx Allocation>; }

Then use ty::Const in types and mir::Const in mir::Operand.

. I'd think a ty::Const is something that is evaluable to a valtree

I think we're in agreement here, but I think this wording is more precise: It's something that should be evaluable to a valtree and will error if trying to do so fails.

OTOH it might be too confusing to also have an "unevaluated" variant in mir::Const itself. Not sure what is best here. Maybe we need a type like

This is similar to my first attempt, but it failed badly because getting there is very hard with the way ty::Const is hardwired into things like https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/mir/visit/trait.MutVisitor.html#method.visit_const and https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/fold/trait.TypeVisitor.html#method.visit_const

I'm not sure we can just use NotSureWhatToCallThis<&'tcx Allocation> for mir::Const, as we also have to allow for literals that came from the AST to be in an "optimized" representation. It may be ok to allocate a &'tcx Allocation for every single one of them, but when we tried to do that for ty::Const the regressions were very bad (though that may just be because they are used in the type system). So we can try again, but we should likely make that a step that's completely independent of any other changes.

I'm wondering whether we should also have LitBytes ([u8; N]) and LitSlice (&[u8] or &str) variants on ValTree, as I'm considering it very likely that we'll want to use strings in const generics. While we could encode them as aggregates, that would be very inefficient (storage wise), and probably annoying to handle. That said, we can start out with encoding them as aggregates and seeing how it goes. If anyone starts putting huge strings in their types, we may just give up (or set a configurable limit like with the recursion depth checks).

I think having LitByteSlice at least makes sense... that could cover both arrays and slices (both byte and string slices) I think.

We then need to be careful to never use the normal aggregate representation for these types, as that would break equality checking.

Ugh yea, I forgot about the equality part. I guess let's go with full expansion at first and then check whether doing an optimization like that actually has any benefits

I would be very surprised if this was not necessary to avoid some enormous regressions, but let's see.

Since this will only be used for constants in the type system, I don't see what this could regress. We don't have any constants but usize in the type system right now (modulo const generics), and const generics other than usize aren't stable or perf tested.

Auto merge of rust-lang#77227 - oli-obk:const_val_🌳_prelude, r=RalfJung

Auto merge of rust-lang#79135 - lcnr:the-paleogenesis-of-generic-germ…

I think this is resolved? The main const-eval query is eval_to_allocation_raw, it returns an AllocId and it performs validation. We have "type" constants whose normal form is a valtree and "MIR" constants whose normal form is a ConstValue. ConstValue is not just an AllocId so that it can efficiently hold a Scalar (used a lot everywhere) or a (byte) str literal (used for MIR building for said literals).

There is more cleanup that I can imagine, but it should probably be in a new issue.

Navigation Menu

Repository navigation

Perform validation in const_eval_raw, return valtree from const_eval and decouple MIR-embedded consts from the rest #72396

16 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Perform validation in const_eval_raw, return valtree from const_eval and decouple MIR-embedded consts from the rest #72396

Description

Activity

RalfJung commented on Jun 20, 2020

oli-obk commented on Jul 6, 2020

RalfJung commented on Jul 27, 2020

oli-obk commented on Jul 27, 2020

RalfJung commented on Jul 27, 2020

RalfJung commented on Aug 10, 2020

RalfJung commented on Aug 10, 2020

oli-obk commented on Aug 10, 2020

RalfJung commented on Aug 10, 2020

oli-obk commented on Aug 10, 2020

16 remaining items

oli-obk commented on Sep 26, 2020

RalfJung commented on Sep 27, 2020

oli-obk commented on Sep 28, 2020

RalfJung commented on Sep 28, 2020

oli-obk commented on Sep 28, 2020

RalfJung commented on Sep 15, 2023

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions