Tracking Issue for const_heap

[oli-obk]

This is a tracking issue for rust-lang/const-eval#20
The feature gate for the issue is #![feature(const_heap)].
The general design can be found here

About tracking issues

Tracking issues are used to record the overall progress of implementation.
They are also used as hubs connecting to other relevant issues, e.g., bugs or open design questions.
A tracking issue is however not meant for large scale discussion, questions, or bug reports about a feature.
Instead, open a dedicated issue for the specific matter and add the relevant feature gate label.

Steps

• Implement Heap allocations in constants const-eval#20 experimentally
• Adjust documentation (see instructions on rustc-dev-guide)
• Stabilization PR (see instructions on rustc-dev-guide)

Unresolved Questions

• Do we want to allow the regular Global allocator? This would give us post-monomorpization errors. More details can be found in https://hackmd.io/h2O2vkj3RimrBTfm9hvZWA#Transient-heap-allocations-via-Global
• If we stabilize this, we fundamentally change the nature of const fn: before this change, a const fn() -> T would inevitably have to always return the same value; after this change, that is no longer the case. With ptr_guaranteed_eq, this can even to some extend be observed during CTFE. So in that sense, this feature is much bigger than anything we ever stabilized for CTFE.
• We can already emulate all this via build.rs scripts or proc macros that generate the appropriate constants/statics and references them. Const heap will "just" make generating static/const allocations more convenient.
• Once we permit references to things that (can) contain interior mutability, it would be possible for users to write a const fn foo() -> &'static Cell<i32>, which could then be used to initialize a const FOO: &'static Cell<i32> which is unsound (and only caught by dynamic checks). The tracking issue for interior mutability behind references is Tracking Issue for const_refs_to_cell #80384

Implementation history

• add const_allocate intrinsic #79594 adds the base intrinsic for telling the miri-engine to create a virtual heap allocation
• move interpret::MemoryKind::Heap to const eval #79664 makes sure that code outside of the const evaluator has no knowledge about heap allocations

[RalfJung]

As discussed here, this feature makes const fn observably impure: let x = f(); (x, x) is no longer always equivalent to (f(), f()). We are at a crossroads for the language here: if we want to support heap allocations in const fn, we have to either introduce some kind of effect system or say goodbye to the idea that const fn denotes a form of purity that would be useful to unsafe code.

[RalfJung]

Btw, given how far-reaching the consequences of this feature are, I wonder if doing this without an RFC is really appropriate. But it could make sense to experiment some more with what can be done for transient vs. non-transient allocations, and how Global comes in, so that we have a better idea of the design space.

@oli-obk something is wrong with "implementation history", it links to the same PR twice.

[oli-obk]

The experimentation that @vn-ki has been doing has exposed various problems that aren't even related to heap stuff itself, but are prerequisites. I believe we should keep on doing this experimentation, just to find out what all the problems are and how a possible implementation could look. Doing this in the abstract has not allowed us to realize what the dependency graph actually is and I will be updating the skill tree to reflect that as we gain more information. Some examples off the top of my head:

• generic types are considered having interior mutability within constants and thus forbid short lived immutable references to them
• trait bounds on methods only work if the bounds are on the method and not if they are on the containing impl block
• the existing alloc code needs support for closures or at least impl const Fn for const fn()
• just needs an impl: use fallible allocations for Allocation to make sure that we report an error instead of crashing rustc with OOM (this can be done on stable via the use of large arrays)

[RalfJung]

The first three points don't seem really related to heap allocations though?

[oli-obk]

They are not, they are prerequisites for Box::new_in and whatever things are called by that.

[RalfJung]

generic types are considered having interior mutability within constants and thus forbid short lived immutable references to them

Is there a separate issue for this? I think this is closely related to some of the other issues that came up over the last year -- where we have a restriction that applies to the final value of all consts, but be unnecessarily apply it even during the course of the computation -- since we have no good way to otherwise ensure that the final value is okay. &mut references have basically the same problem.

[oli-obk]

There is not. I have a local branch that generalizes to all such checks, so we'll be able to just check them on the final value

[RalfJung]

For associated consts, I assume that's a post-monomorphization error then?

(I know this is off-topic here, that's why I asked if there is a better place.^^)

[oli-obk]

No... this is a static check that is overzealous in the presence of generics and such.

[RalfJung]

Okay, looking forward to it. :) Doing a write-up first before finishing the implementation could also help (but we can also do that later if you prefer... I just think we should do it before landing; "writeup later" hasn't worked out well for us in the past^^).

[arnabanimesh]

I personally think that heap allocation at compile time should be done independently. It is a bad idea to include it in const fn. const fn should not have heap allocations since it increases the code analysis complexity considerably.

I would suggest independently create const using heap allocation before starting compilations. Using a separate file known as consts.rs in the root would be one way of doing it and instantiating the same using Cargo.toml (as in case of build.rs). However, unlike build.rs, it should be able to accept multiple files as it will help in organizing constants for multiple binaries as multiple files. It can have all the rust language features but it should have compiler checks that ensure that at the end only const variables can be created and each of them has to be assigned to at least one binary with the same name. Generally, it is main, but sometimes multiple bins with their own names are also possible.

It can be done similarly using build.rs itself but additional language structs need to be implemented and I don't find it appealing.

It is just like running configure before make. It should be doable.

[oli-obk]

What you describe (and as you noted), can already be done via build.rs. This issue is specifically tracking heap at compile-time, we are very far from stabilization, and I'll add your concerns to the main post. Please be aware that this is a frequently asked for feature, so there is different desires for language design that need to be balanced against each other.

That said, at the current design phase, you can statically know wheter a const fn does heap allocations internally, because it must have a A: AllocRef generic parameter. If it does not have this, it can only use the ConstHeap heap allocator, which at present cannot be used at runtime at all (there is no runtime implementation for the relevant intrinsic, so you'd get a (right now very bad) compile-time error).

[petrochenkov]

How far is the implementation state from being able to construct a FxHashMap at compile time?

It would be pretty useful for string interner in the compiler itself given that available static alternatives like phf appear to be slower in this case (#80420 (comment)).

[oli-obk]

Very far. This requires not just const heap, but also all kinds of trait methods to be const, which has its own blockers (I should really update the const skill tree with all the new information I have now. I guess since we are on nightly we can go quite crazy with feature gates, but we'd first have to implement appropriate const stability attributes for trait impls so we can make trait impls in libcore/libstd const