## File: README.md

# Constant Evaluation

Constant evaluation is the process of running Rust code at compile-time
in order to use the result e.g. to set the discriminant of enum variants
or as an array length.

Examples:

```rust
enum Foo {
    A = 5,
    B = 7 - 3,
}
type NineStrings = [&str, 3 * 3];
```

The Rust compiler runs the [MIR](https://rustc-dev-guide.rust-lang.org/mir/index.html)
in the [`MIR` interpreter (miri)](https://rustc-dev-guide.rust-lang.org/const-eval),
which sort of is a virtual machine using `MIR` as "bytecode".

## Table of Contents

* [Unstable Feature Skill Tree](https://rust-lang.github.io/const-eval/)
* [Const Safety](const_safety.md)
* [Static and dynamic checks](const_checks.md)
* The three "kinds" of compile-time evaluated data:
  * [Statics](static.md) (`static`, `static mut`)
  * [Constants](const.md) (`const`, array sizes, non-`Copy` array initializers)
  * [Promoteds](promotion.md) (rvalue promotion)

## Related RFCs

### Const Promotion

[RFC 1414](https://github.com/rust-lang/rfcs/pull/1414) injects a hidden static for any
`&foo` expression as long as `foo` follows a certain set of rules.
These rules are discussed [here](promotion.md)

### Drop types in constants/statics

[RFC 1440](https://github.com/rust-lang/rfcs/pull/1440) allows using types that implement
`Drop` (or have fields that do so) inside constants and statics. It is guaranteed that the
`Drop::drop` method will never be called on the static/const object.

### Constants in Repeat expressions

[RFC 2203](https://github.com/rust-lang/rfcs/pull/2203) allows the use `!Copy` types for the
initializer of repeat expressions, as long as that value is constant.

This permits e.g. `[Vec::new(); 42]`.

### Statically known bugs and panics in runtime code are warnings

[RFC 1229](https://github.com/rust-lang/rfcs/pull/1229) formalized the concept that

```rust
let x: usize = 1 - 2;
```

is allowed to produce a `lint` but not an `error`. This allows us to make these analyses
more powerful without suddenly breaking compilation. The corresponding lint is the `const_err`
lint, which is `deny` by default and will thus break compilation of the crate currently being built,
even if it does not break the compilation of the current crate's dependencies.

### Various new const-eval features

* [`loop`](https://github.com/rust-lang/rfcs/pull/2344)
* [`if` and `match`](https://github.com/rust-lang/rfcs/pull/2342)
* [`panic!`](https://github.com/rust-lang/rfcs/pull/2345)
* [`locals and destructuring`](https://github.com/rust-lang/rfcs/pull/2341)

Some of these features interact. E.g.

* `match` + `loop` yields `while`
* `panic!` + `if` + `locals` yields `assert!`

---

## File: CODE_OF_CONDUCT.md

# The Rust Code of Conduct

A version of this document [can be found online](https://www.rust-lang.org/conduct.html).

## Conduct

**Contact**: [rust-mods@rust-lang.org](mailto:rust-mods@rust-lang.org)

* We are committed to providing a friendly, safe and welcoming environment for all, regardless of level of experience, gender identity and expression, sexual orientation, disability, personal appearance, body size, race, ethnicity, age, religion, nationality, or other similar characteristic.
* On IRC, please avoid using overtly sexual nicknames or other nicknames that might detract from a friendly, safe and welcoming environment for all.
* Please be kind and courteous. There's no need to be mean or rude.
* Respect that people have differences of opinion and that every design or implementation choice carries a trade-off and numerous costs. There is seldom a right answer.
* Please keep unstructured critique to a minimum. If you have solid ideas you want to experiment with, make a fork and see how it works.
* We will exclude you from interaction if you insult, demean or harass anyone. That is not welcome behavior. We interpret the term "harassment" as including the definition in the [Citizen Code of Conduct](http://citizencodeofconduct.org/); if you have any lack of clarity about what might be included in that concept, please read their definition. In particular, we don't tolerate behavior that excludes people in socially marginalized groups.
* Private harassment is also unacceptable. No matter who you are, if you feel you have been or are being harassed or made uncomfortable by a community member, please contact one of the channel ops or any of the [Rust moderation team][mod_team] immediately. Whether you're a regular contributor or a newcomer, we care about making this community a safe place for you and we've got your back.
* Likewise any spamming, trolling, flaming, baiting or other attention-stealing behavior is not welcome.

## Moderation


These are the policies for upholding our community's standards of conduct. If you feel that a thread needs moderation, please contact the [Rust moderation team][mod_team].

1. Remarks that violate the Rust standards of conduct, including hateful, hurtful, oppressive, or exclusionary remarks, are not allowed. (Cursing is allowed, but never targeting another user, and never in a hateful manner.)
2. Remarks that moderators find inappropriate, whether listed in the code of conduct or not, are also not allowed.
3. Moderators will first respond to such remarks with a warning.
4. If the warning is unheeded, the user will be "kicked," i.e., kicked out of the communication channel to cool off.
5. If the user comes back and continues to make trouble, they will be banned, i.e., indefinitely excluded.
6. Moderators may choose at their discretion to un-ban the user if it was a first offense and they offer the offended party a genuine apology.
7. If a moderator bans someone and you think it was unjustified, please take it up with that moderator, or with a different moderator, **in private**. Complaints about bans in-channel are not allowed.
8. Moderators are held to a higher standard than other community members. If a moderator creates an inappropriate situation, they should expect less leeway than others.

In the Rust community we strive to go the extra step to look out for each other. Don't just aim to be technically unimpeachable, try to be your best self. In particular, avoid flirting with offensive or sensitive issues, particularly if they're off-topic; this all too often leads to unnecessary fights, hurt feelings, and damaged trust; worse, it can drive people away from the community entirely.

And if someone takes issue with something you said or did, resist the urge to be defensive. Just stop doing what it was they complained about and apologize. Even if you feel you were misinterpreted or unfairly accused, chances are good there was something you could've communicated better — remember that it's your responsibility to make your fellow Rustaceans comfortable. Everyone wants to get along and we are all here first and foremost because we want to talk about cool technology. You will find that people will be eager to assume good intent and forgive as long as you earn their trust.

The enforcement policies listed above apply to all official Rust venues; including official IRC channels (#rust, #rust-internals, #rust-tools, #rust-libs, #rustc, #rust-beginners, #rust-docs, #rust-community, #rust-lang, and #cargo); GitHub repositories under rust-lang, rust-lang-nursery, and rust-lang-deprecated; and all forums under rust-lang.org (users.rust-lang.org, internals.rust-lang.org). For other projects adopting the Rust Code of Conduct, please contact the maintainers of those projects for enforcement. If you wish to use this code of conduct for your own project, consider explicitly mentioning your moderation policy or making a copy with your own moderation policy so as to avoid confusion.

*Adapted from the [Node.js Policy on Trolling](http://blog.izs.me/post/30036893703/policy-on-trolling) as well as the [Contributor Covenant v1.3.0](https://www.contributor-covenant.org/version/1/3/0/).*

[mod_team]: https://www.rust-lang.org/team.html#Moderation-team

---

## File: const.md

# Constants

"Constants" in this document refers to `const` bodies, array sizes, and non-`Copy` array initializers.
On top of what applies to [statics](static.md), they are subject to an additional constraint: In code like
```rust
const CONST: T = EXPR;
```
is supposed to behave as-if `EXPR` was written at every use site of `CONST`.
However, in current versions of rustc, `EXPR` is just computed once and the result is bit-wise copied each time `CONST` is used.
To make this work, we need to ensure [const safety](const_safety.md).

Based on this requirement, we allow other constants and [promoteds](promotion.md) to read from constants.
This is why the value of a `const` is subject to validity checks.

Constants can also be [used in patterns](patterns.md), which brings its own soundness concerns.

## References

One issue is constants of reference type:
```rust
const REF: &u32 = &EXPR;
```
Instead of creating a new allocation for storing the result of `EXPR` on every
use site, we just have a single global "static" allocation and every use of
`REF` uses its address.  It's as if we had written:
```rust
const REF: &u32 = { const _VAL = EXPR; static _STATIC = EXPR; &_STATIC };
```
(`EXPR` is assigned to a `const` first to make it subject to the restrictions
discussed in this document.)

There are various reasons why this could be an issue.

### 1. Pointer equality

We effectively "deduplicate" all the allocations that would otherwise locally be
created at each use site of `REF`.  This is observable when the program compares
these pointers for equality.  We consider this okay, i.e., programs may not rely
on such constants all getting distinct addresses.  They may not rely on them all
getting the same address either.

### 2. Interior mutability

If the reference has type `&Cell` it is quite clear that the program can
easily observe whether two references point to the same memory even without
comparing their address: Changes through one reference will affect reads through
the other.  So, we cannot allow constant references to types that have interior
mutability (types that are not `Freeze`):

```rust
const BAD: &Cell<i32> = &Cell::new(42);
// Inlining `BAD` everywhere clearly is not the same as them all pointing to the same thing.
```

However, we can do better than that: Even if a *type* is not `Freeze`, it can
have *values* that do not exhibit any interior mutability.  For example, `&None`
at type `&Option<Cell>` would be rejected by the naive analysis above, but
is actually accepted by the compiler because we know that there is no
`UnsafeCell` here that would permit interior mutability.

*Dynamic check.* The Miri engine enforces this dynamically by ensuring that the
new data that is interned for a constant is all marked as immutable.
(Except for
[data inside promoteds](https://github.com/rust-lang/rust/blob/d538b80ad77949e46989cd355cdec193b574f052/src/librustc_mir/interpret/intern.rs#L363-L367)
which cannot easily be checked, and is thus just *marked* as immutable because
it descends from a shared reference subject to the strict syntactic checks of
lifetime extension.)

Note that a constant *referring to* some already existing mutable memory is
fine: inlining that reference everywhere has the same behavior as computing a
new reference each time.  In both cases, there exists exactly one instance of
the mutable memory that everything references.

### 3. `Send`

Finally, the same constant value is actually shared across threads.  This is
very similar to sending the same value across threads, so it seems like we
should reject non-`Send` types.  For shared references, this means the pointee
type ought to be `Sync`.  That is already required for `static` items, so this
is consistent with the desugaring described above.

However, this does not currently happen, and there are several crates across the
ecosystem that would break if we just started enforcing this now. See
[this issue](https://github.com/rust-lang/rust/issues/49206) and the
[PR attempting to fix this](https://github.com/rust-lang/rust/pull/54424/).

One could make the argument that the value does not have to be `Send` because it
is not actually sent to other threads; instead, conceptually, each thread
re-does the same computation.  But we know they will all come to the same
result.  This works, except when we consider address identity: with references
in the `const`, all threads will get the same address, unlike in case of a
per-thread recomputation which would lead to different addresses. As a
consequence, non-`Send` `const` without references are fine, but once references
and thus address identity comes into play, we have a problem.

*Dynamic check.* It is unclear how the Miri engine could dynamically check this.

### 4. Drop

`Drop` is actually not an issue, at least not more so than for statics:

```rust
struct Foo;

impl Drop for Foo {
    fn drop(&mut self) {
        println!("foo dropped");
    }
}

const FOO: Foo = Foo; // Ok, drop is run at each use site in runtime code

// Not ok, cannot run `Foo::drop` because it's not a const fn
const BAR: i32 = (Foo, 42).1;
```

## Reading statics

Beyond values of reference type, we have to be careful that *computing* a
`const` cannot read from a static that could get mutated (because it is `static
mut`, or because it has interior mutability).  That would lead to the constant
expression (being computed at compile-time) not having the same value any more
when evaluated at run-time.

This is distinct to the concern about interior mutability above: That concern
was about first computing a `&Cell` and then using it at run-time (and
observing the fact that it has been "deduplicated"), this here is about using
such a value at compile-time even though it might be changed at run-time.

*Dynamic check.* The Miri engine checks this dynamically by refusing to access
global mutable memory, and refusing to dereference any pointer to a static, when
computing a const.

---

## File: const_checks.md

# Static and dynamic checks

This repository describes a set of rules that various forms of compile-time evaluated code needs to satisfy.
The compiler contains two kinds of checks that guard against violations of these rules: static checks and dynamic checks.

## Dynamic checks

Dynamic checks are conceptually very simple: when evaluating the compile-time code, we look at what it does, and if what it does violates the rules, we halt evaluation.
Thus, a dynamic check generally makes it very clear what is being protected against.

The main disadvantage of dynamic checks is that they can only run when the compile-time code is being evaluated, which is after monomorphization.
We generally try to avoid post-monomorphization errors as they inherently make for a bad user experience.
While there are technical aspects that could be improved here, the main problem is that the site where the error is reported is disconnected from the site where the root cause is.
Such problems can be observed when creating an associated constant that uses associated constants from generic parameters.
These generic parameters are unknown, so the usage of these associated constants may cause errors depending on the *value* of the generic parameter's associated constants.

[Promotion analysis](promotion.md) also makes little sense dynamically as it is about code transformation.
All we can do is check after the transformation if the generated code makes sense.

## Static checks

Static checks work by "looking" at the code.
(This is "static" as in [static analysis](https://en.wikipedia.org/wiki/Static_analysis), not to be confused with Rust's `static` keyword.)
The idea is to predict what the code will do without actually executing it.
That means we can even analyze code that we cannot run pre-monomorphization.
However, static checks are necessarily less precise than dynamic checks (this is the famous halting problem), which means they will reject code that the dynamic checks would accept.

The key property is that the static check is *sound*, which means that everything accepted by the static checks will also be accepted by the dynamic checks.
It might seem like this makes the dynamic checks unnecessary, but they are still tremendously useful.
On the one hand, the dynamic checks serve as a safety net for when we have bugs in the static checks (dynamic checks are much easier to get right, typically).
On the other hand, having the dynamic checks forces us through the helpful exercise of figuring out what the dynamic property we are enforcing actually *is*, which is crucial when we want to adjust the static check to be more precise.
The dynamic check serves as the "ground truth" that the static check approximates, and we can improve that approximation over time.

---

## File: const_safety.md

# Const safety

The miri engine, which is used to execute code at compile time, can fail in
four possible ways:

* The program performs an unsupported operation (e.g., calling an unimplemented
  intrinsics, or doing an operation that would observe the integer address of a
  pointer).
* The program causes undefined behavior (e.g., dereferencing an out-of-bounds
  pointer).
* The program panics (e.g., a failed bounds check).
* The program exhausts its resources: It might overflow the stack, allocate
  too much memory or loop forever.  Note that detecting these conditions
  happens on a best-effort basis only.

Just like panics and non-termination are acceptable in safe run-time Rust code,
we also consider these acceptable in safe compile-time Rust code.  However, we
would like to rule out the first two kinds of failures in safe code.  Following
the terminology in [this blog post], we call a program that does not fail in the
first two ways *const safe*.

[this blog post]: https://www.ralfj.de/blog/2018/07/19/const.html

The goal of the const safety check, then, is to ensure that a program is const
safe.  What makes this tricky is that there are some operations that are safe as
far as run-time Rust is concerned, but unsupported in the miri engine and hence
not const safe (they fall in the first category of failures above).  We call these operations *unconst*.  The purpose
of the following section is to explain this in more detail, before proceeding
with the main definitions.

## Miri background

A very simple example of an unconst operation is
```rust
static S:i32 = 0;
const BAD:bool = (&S as *const i32 as usize) % 16 == 0;
```
The modulo operation here is not supported by the miri engine because evaluating
it requires knowing the actual integer address of `S`.

The way miri handles this is by treating pointer and integer values separately.
The most primitive kind of value in miri is a `Scalar`, and a scalar is *either*
a pointer (`Scalar::Ptr`) or a bunch of bits representing an integer
(`Scalar::Bits`).  Every value of a variable of primitive type is stored as a
`Scalar`.  In the code above, casting the pointer `&S` to `*const i32` and then
to `usize` does not actually change the value -- we end up with a local variable
of type `usize` whose value is a `Scalar::Ptr`.  This is not a problem in
itself, but then executing `%` on this *pointer value* is unsupported.

However, it does not seem appropriate to blame the `%` operation above for this
failure. `%` on "normal" `usize` values (`Scalar::Bits`) is perfectly fine, just using it on
values computed from pointers is an issue.  Essentially, `&i32 as *const i32 as
usize` is a "safe" `usize` at run-time (meaning that applying safe operations to
this `usize` cannot lead to misbehavior, following terminology [suggested here])
-- but the same value is *not* "safe" at compile-time, because we can cause a
const safety violation by applying a safe operation (namely, `%`).

[suggested here]: https://www.ralfj.de/blog/2018/08/22/two-kinds-of-invariants.html

## Const safety check on values

The result of any const computation (`const`, `static`, promoteds) is subject to
a "sanity check" which enforces const safety.  (A sanity check is already
happening, but it is not exactly checking const safety currently.)  Const safety
is defined as follows:

* Integer and floating point types are const-safe if they are a `Scalar::Bits`.
  This makes sure that we can run `%` and other operations without violating
  const safety.  In particular, the value must *not* be uninitialized.
* References are const-safe if they are `Scalar::Ptr` into allocated memory, and
  the data stored there is const-safe.  (Technically, we would also like to
  require `&mut` to be unique and `&` to not be mutable unless there is an
  `UnsafeCell`, but it seems infeasible to check that.)  For fat pointers, the
  length of a slice must be a valid `usize` and the vtable of a `dyn Trait` must
  be a valid vtable.
* `bool` is const-safe if it is `Scalar::Bits` with a value of `0` or `1`.
* `char` is const-safe if it is a valid unicode codepoint.
* `()` is always const-safe.
* `!` is never const-safe.
* Tuples, structs, arrays and slices are const-safe if all their fields are
  const-safe.
* Enums are const-safe if they have a valid discriminant and the fields of the
  active variant are const-safe.
* Unions are always const-safe; the data does not matter.
* `dyn Trait` is const-safe if the value is const-safe at the type indicated by
  the vtable.
* Function pointers are const-safe if they point to an actual function.  A
  `const fn` pointer (when/if we have those) must point to a `const fn`.

For example:
```rust
static S: i32 = 0;
const BAD: usize = &S as *const i32 as usize;
```
Here, `S` is const-safe because `0` is a `Scalar::Bits`.  However, `BAD` is *not* const-safe because it is a `Scalar::Ptr`.

## Const safety check on code

The purpose of the const safety check on code is to prohibit construction of
non-const-safe values in safe code.  We can allow *almost* all safe operations,
except for unconst operations -- which are all related to raw pointers:
Comparing raw pointers for (in)equality, converting them to integers, hashing
them (including hashing references) and so on must be prohibited.  Basically, we
should not permit any raw pointer operations to begin with, and carefully
evaluate any that we permit to make sure they are fully supported by miri and do
not permit constructing non-const-safe values.

There should also be a mechanism akin to `unsafe` blocks to opt-in to using
unconst operations.  At this point, it becomes the responsibility of the
programmer to preserve const safety.  In particular, a *safe* `const fn` must
always execute const-safely when called with const-safe arguments, and produce a
const-safe result.  For example, the following function is const-safe (after
some extensions of the miri engine that are already implemented in miri) even
though it uses raw pointer operations:
```rust
const fn slice_eq(x: &[u32], y: &[u32]) -> bool {
    if x.len() != y.len() {
        return false;
    }
    // equal length and address -> memory must be equal, too
    if unconst { x as *const [u32] as *const u32 == y as *const [u32] as *const u32 } {
        return true;
    }
    // assume the following is legal const code for the purpose of this function
    x.iter().eq(y.iter())
}
```
On the other hand, the following function is *not* const-safe and hence it is considered a bug to mark it as such:
```
const fn ptr_eq<T>(x: &T, y: &T) -> bool {
    unconst { x as *const T == y as *const T }
}
```

If the function were invoked as `ptr_eq(&42, &42)` the result depends on the potential
deduplication of the memory of the `42`s.

## Open questions

* Do we allow unconst operations in `unsafe` blocks, or do we have some other
  mechanism for opting in to them (like `unconst` blocks)?

* How do we communicate that the rules for safe `const fn` using unsafe code are
  different than the ones for "runtime" functions?  The good news here is that
  violating the rules, at worst, leads to a compile-time error in a dependency.
  No UB can arise.  However, thanks to [promotion](promotion.md), compile-time
  errors can arise even if no `const` or `static` is involved.

---

## File: patterns.md

# Constants in patterns

Constants that pass the [structural equality check][struct-eq] can be used in patterns:
```rust
const FOO: i32 = 13;

fn is_foo(x: i32) -> bool {
  match x {
    FOO => true,
    _ => false,
  }
}
```
However, that check has some loopholes, so e.g. `&T` can be used in a pattern no matter the `T`.

The way this works is that the constant is converted to a [THIR pattern](https://doc.rust-lang.org/nightly/nightly-rustc/rustc_mir_build/thir/pattern/enum.PatKind.html).
This proceeds recursively through fields of the constant until we hit a reference.
Then, `&[u8]` and `&str` are treated specially, while everything else becomes just a `PatKind::Constant`.

For further compilation, `Constant` are translated to [`PartialEq::eq`][compile-partial-eq], whereas everything else is translated as if the constant was inlined as a pattern.
[RFC 1445](https://github.com/rust-lang/rfcs/blob/master/text/1445-restrict-constants-in-patterns.md) lays the groundwork for changing this in the future to always using `PartialEq::eq`, but no decision either way has been made yet.

[struct-eq]: https://github.com/rust-lang/rust/blob/2c28244cf0fc9868f55070e55b8f332d196eaf3f/src/librustc_mir_build/hair/pattern/const_to_pat.rs#L121
[compile-partial-eq]: https://github.com/rust-lang/rust/blob/2c28244cf0fc9868f55070e55b8f332d196eaf3f/src/librustc_mir_build/build/matches/test.rs#L355

## Soundness concerns

Most of the time there are no extra soundness concerns due to const-patterns; except for surprising behavior nothing can go wrong when the structural equality check gives a wrong answer.
However, there is one exception: some constants participate in exhaustiveness checking.
If a pattern is incorrectly considered exhaustive, that leads to a critical soundness bug.

Exhaustiveness checking is done based on the THIR pattern tree, with `PatKind::Constant` being ignored.
This means we can write:
```rust
#![feature(exclusive_range_pattern)]
#![feature(half_open_range_patterns)]
const PAT: &[u8] = &[0];

pub fn test(x: &[u8]) -> bool {
    match x {
        PAT => true,
        &[] => false,
        &[1..] => false,
        &[_, _, ..] => false
    }
}
```

To ensure soundness of exhaustiveness checking, it is crucial that all data considered this check is fully immutable.
In particular, for constants of reference type, it is important that they only point to immutable data.
For this reason, the static const checks reject references to `static` items.
This is a new soundness concern that otherwise does not come up during CTFE.
Note that this is orthogonal to the concern of [*reading from* a mutable `static`](const.md#reading-statics) during const initialization, which is a problem for all `const` (even when they are not used in patterns) because it breaks the "inlining" property.
A more precise check could be possible, but is non-trivial: even an immutable `static` could point to a mutable `static`; that would have to be excluded.
(We could, in principle, also rely on it being UB to have a shared reference to mutable memory, but for now we prefer not to rely on the aliasing model like that---aliasing of global pointers is a tricky subject.)

*Dynamic check.*
To dynamically ensure constants only point to read-only data, we maintain a global invariant:
pointers to a `static` (including memory that was created as part of interning a `static`) may never "leak" to a non-`static`.
All memory outside of `static`s is marked as immutable.
As a consequence, non-`static`s recursively only point to immutable memory.

This check is uncomfortably close to the static checks, and fragile due to its reliance on a global invariant.
Longer-term, it would be better to move to a more local check, by making validation check if consts are recursively read-only.
This check (unlike our current validation) would have to descend through pointers to `static`.

An alternative could be to wait for the [value tree proposal](https://github.com/rust-lang/compiler-team/issues/323) to be implemented.
Then we could check during value tree construction that all memory is read-only (if we use the CTFE machine in `const`-mode, that will happen implicitly), and thus we know for sure we can rely on the value tree to be sound to use for exhaustiveness checking.
How exactly this looks like depends on how we resolve [pattern matching allowing many things that do not fit a value tree](https://github.com/rust-lang/rust/issues/74446#issuecomment-663439899).
However, if only the well-behaved part of the value tree is used for exhaustiveness checking, handling these extra patterns should not interact closely with the soundness concerns discussed here.

---

## File: promotion.md

# Const promotion

"Promotion" is the act of splicing a part of a MIR computation out into a
separate self-contained MIR body which is evaluated at compile-time like a
constant. This mechanism has been introduced by [RFC 1414][promotion-rfc] with
the goal of equipping some references-to-temporaries with a `'static` lifetime,
which is sometimes called "lifetime extension".

[promotion-rfc]: https://github.com/rust-lang/rfcs/blob/master/text/1414-rvalue_static_promotion.md

Promotion / lifetime extension affects code like `&3`: Instead of putting it on
the stack, the `3` is allocated in global static memory and a reference with
lifetime `'static` is provided.  This is essentially an automatic transformation
turning `&EXPR` into `{ const _PROMOTED = &EXPR; _PROMOTED }`, but only if
`EXPR` qualifies. Topmost projections are not promoted, so `&EXPR.proj1.proj2`
turns into `{ const _PROMOTED = &EXPR; &(*_PROMOTED).proj1.proj2 }`.

Note that promotion happens on the MIR, not on surface-level syntax.  This is
relevant when discussing e.g. handling of panics caused by overflowing
arithmetic.

## Promotion and fallability of const-evaluation

On top of what applies to [consts](const.md), promoteds suffer from the
additional issue that *the user did not ask for them to be evaluated at
compile-time*.  Thus, if CTFE fails but the code would have worked fine at
run-time, we broke the user's code for no good reason.  Even if we are sure we
found an error in the user's code, we are only allowed to
[emit a warning, not a hard error][warn-rfc].

For example:
```rust
fn foo() {
    if false {
        let x = &(1/0);
    }
}
```
If we performed promotion here, this would turn into
```rust
fn foo() {
    if false {
        const _PROMOTED = &(1/0);
        let x = _PROMOTED;
    }
}
```
When compiling this function, we have to evaluate all constants that occur
inside the function body, even if they might only be used in dead code. This
means we have to evaluate `_PROMOTED`, which will error -- and now what, should
we halt compilation? That would be wrong since there is no problem with this
code, the "bad" division never actually happens as it occurs in dead code.
(Note that the considerations would be the same even if `foo` were a `const
fn`.)

As a consequence, we only promote code that can never fail to evaluate (see
[RFC 3027]). This ensures that even if promotion happens inside dead code, this
will not turn a "runtime error in dead code" (which is not an error at all) into
a compile-time error. In particular, we cannot promote calls to arbitrary `const
fn`, as discussed in detail in
[rust-lang/const-eval#19](https://github.com/rust-lang/const-eval/issues/19).
Thus, only functions marked `#[rustc_promotable]` are promotable.

[RFC 3027]: https://rust-lang.github.io/rfcs/3027-infallible-promotion.html

There is one exception to this rule: the bodies of `const`/`static`
initializers. This code is never compiled, so we do not actually have to
evaluate constants that occur in dead code. If we are careful enough during
compilation, we can ensure that only constants whose value is *actually needed*
are evaluated. We thus can be more relaxed about promotion; in practice, what
this means is that we will promote calls to arbitrary `const fn`, not just those
marked `#[rustc_promotable]`.

[See below][access-static] for another special case in promotion analysis:
accesses and references to statics are only promoted inside other statics.

[warn-rfc]: https://github.com/rust-lang/rfcs/blob/master/text/1229-compile-time-asserts.md

## "enclosing scope" rule

Notice that some code involving `&` *looks* like it relies on promotion /
lifetime extension but actually does not:

```rust
const EMPTY_BYTES: &Vec<u8> = &Vec::new(); // Ok without lifetime extension
```

`Vec::new()` cannot get promoted because it needs dropping. And yet this
compiles. Why that? The reason is that the reference obtains the lifetime of
the "enclosing scope", similar to how `let x = &mut x;` creates a reference
whose lifetime lasts for the enclosing scope. This is decided during MIR
building already, and does not involve lifetime extension.

In contrast, this does not compile:

```rust
const OPT_EMPTY_BYTES: Option<&Vec<u8>> = Some(&Vec::new());
```

The "enclosing scope" rule only fires for outermost `&`, just like in `fn` bodies.

## Promotability

We have described the circumstances where promotion is desirable, but what
expressions are actually eligible for promotion? We refer to eligible
expressions as "promotable" and describe the restrictions on such expressions
below.

First of all, expressions have to be [allowed in constants](const.md). The
restrictions described there are needed because we want `const` to behave the
same as copying the `const` initializer everywhere the constant is used; we need
the same property when promoting expressions. But we need more.

Note that there is no point in doing additional dynamic checks to ensure that we
do get these restrictions right. The entire point of the promotion restrictions
is to avoid failing compilation for code that would have been fine without
promotion. The best a dynamic check could do is tell us after the fact that we
should not have promoted something, but then it is already too late -- and the
dynamic checks for that are exactly the ones we are already doing for constants
and statics.

### Panics, overflow and bounds checks

Let us look at what happens when we promote `&(0_usize - 1)` in a debug build.
This code is promoted even though we cannot promote code that could fail, and
this code will fail with an overflow error! What is happening?  We have to look
at the underlying MIR representation of this code to explain what happens:

```
_tmp1 = CheckedSub (const 0usize) (const 1usize)
assert(!_tmp1.1) -> [success: bb2; unwind: ..]

bb2:
_tmp2 = tmp1.0
_res = &_tmp2
```

Both `_tmp1` and `_tmp2` are promoted.  `_tmp1` evaluates to `(~0, true)`, so
the assertion will always fail at run-time. Computing `_tmp2` evaluates to `~0`.

In other words, the actually failing check is not promoted, only the computation
that serves as input to the check is promoted.

An earlier version of Miri used to error on arithmetic overflow even in release
mode. This breaks promotion, because now promoting code like `_tmp1` would
introduce promotes that fail to evaluate, which is not acceptable as explained
above!

Something similar but more subtle happens when promoting array accesses: the
bounds check is not promoted, but the array access is. However, before accepting
a temporary for promotion, we ensure that array accesses are definitely
in-bounds. This leads to MIR without bounds checks, but we know the array access
will always succeed.

### Const safety

We have explained how we ensure that evaluating a promoted does not panic, but
what about other kinds of failure -- what about hitting an unsupported operation
or undefined behavior? To make sure this does not happen, only const safe code
gets promoted. The exact details for `const safety` are discussed in
[here](const_safety.md).

An example of this would be `&(&1 as *const i32 as usize % 16 == 0)`. The actual
location is not known at compile-time, so we cannot promote this.  Generally, we
can guarantee const-safety by not promoting when an unsafe or unconst operation
is performed -- if our const safety checker is correct, that has to cover
everything, so the only possible remaining failure are panics.

However, things get more tricky when `const` and `const fn` are involved.

For `const`, based on the const safety check described [here](const_safety.md#const-safety-check-on-values),
we can rely on there not being const-unsafe values in the `const`, so we should
be able to promote freely.  For example:

```rust
union Foo { x: &'static i32, y: usize }
const A: usize = unsafe { Foo { x: &1 }.y };
const B: usize = unsafe { Foo { x: &2 }.y };
let x: &bool = &(A < B);
```

Promoting `x` would lead to a compile failure because we cannot compare pointer
addresses.  However, we do not even get there -- computing `A` or `B` fails with
a const safety check error because these are values of type `usize` that contain
a `Scalar::Ptr`.

For `const fn`, however, there is no way to check anything in advance.  We can
either just not promote, or we can move responsibility to the `const fn` and
promote *if* all function arguments pass the const safety check.  So,
`foo(42usize)` would get promoted, but `foo(&1 as *const i32 as usize)` would
not.  When this call panics, compilation proceeds and we just hard-code a panic
to happen as well at run-time.  However, when const evaluation fails with
another error (unsupported operation or undefined behavior), we have no choice
but to abort compilation of a program that would have compiled fine if we would
not have decided to promote.  It is the responsibility of `foo` to not fail this
way when working with const-safe arguments.

For this reason, only `const fn` that were explicitly marked with the
`#[rustc_promotable]` attribute are subject to promotion. Those functions must
be manually reviewed to never raise CTFE errors.

### Drop

Expressions returning "needs drop" types can never be promoted. If such an
expression were promoted, the `Drop` impl would never get called on the value,
even though the user did not explicitly request such behavior by using an
explicit `const` or `static` item.

As expression promotion is essentially the silent insertion of a `static` item, and
`static` items never have their `Drop` impl called, the `Drop` impl of the promoted
value would never get called.

While it is sound to `std::mem::forget` any value and thus not call its `Drop` impl,
it is unlikely to be the desired behavior in most cases and very likey to be confusing
to the user. If such behavior is desired, the user can still use an explicit `static`
or `const` item and refer to that.

*Dynamic check.* The Miri engine could dynamically check this by ensuring that
the result of computing a promoted is a value that does not need dropping.

### Access to a `const` or `static`
[access-static]: #access-to-a-const-or-static

When accessing a `const` in a promotable context, its value gets computed
at compile-time anyway, so we do not have to check the initializer.  However, the
restrictions described above still apply for the *result* of the promoted
computation: in particular, it must be a valid `const` (i.e., it cannot
introduce interior mutability) and it must not require dropping.

For instance the following would be legal even though calls to `do_it` are not
eligible for implicit promotion:

```rust
const fn do_it(x: i32) -> i32 { 2*x }
const ANSWER: i32 = {
  let ret = do_it(21);
  ret
};

let x: &'static i32 = &ANSWER;
```

An access to a `static`, including just taking references to a `static`, is only
promotable within the initializer of another `static`. This is for the same
reason that `const` initializers
[cannot access statics](const.md#reading-statics).

Crucially, however, the following is *not* legal:

```rust
const X: Cell<i32> = Cell::new(5); // ok
const XREF: &Cell<i32> = &X; // not ok
fn main() {
    let x: &'static _ = &X; // not ok
}
```

Just like allowing `XREF` would be a problem because, by the inlining semantics,
every user of `XREF` should get their own `Cell`; it would also be a problem to
promote here because if that code gets executed multiple times (e.g. inside a
loop), it should get a new `Cell` each time.

### Named locals

Promotable expressions cannot refer to named locals. This is not a technical
limitation with the CTFE engine. While writing `let x = {expr}` outside of a
const context, the user likely expects that `x` will live on the stack and be
initialized at run-time.  Although this is not (to my knowledge) guaranteed by
the language, we do not wish to violate the user's expectations here.

Note that constant-folding still applies: the optimizer may compute `x` at
compile-time and even inline it everywhere if it can show that this does not
observably alter program behavior.  Promotion is very different from
constant-folding as promotion can introduce observable differences in behavior
(if const-evaluation fails) and as it is *guaranteed* to happen in some cases
(and thus exploited by the borrow checker).  This is reflected in the fact that
promotion affects lifetimes, but constant folding does not.

### Single assignment

We only promote temporaries that are assigned to exactly once. For example, the
lifetime of the temporary whose reference is assigned to `x` below will not be
extended.

```rust
let x: &'static i32 = &if cfg!(windows) { 0 } else { 1 };
```

Once again, this is not a fundamental limitation in the CTFE engine; we are
perfectly capable of evaluating such expressions at compile time. However,
determining the promotability of complex expressions would require more
resources for little benefit.

## Open questions

* There is a fourth kind of CTFE failure -- resource exhaustion.  What do we do
  when that happens while evaluating a promoted?

---

## File: static.md

# Statics

Statics (`static`, `static mut`) are the simplest kind of compile-time evaluated data:
* The user explicitly requested them to be evaluated at compile-time,
  so evaluation errors from computing the initial value of a static are no concern
  (in other words, [const safety](const_safety.md) is mostly not an issue).
* They observably get evaluated *once*, with the result being put at some address known at run-time,
  so there are no fundamental restrictions on what statics can do.
* The compiler checks that statics are `Sync`, justifying sharing their address across threads.
* [Constants](const.md) and [promoteds](promotion.md) are not allowed to read from statics,
  so their final value does not have have to be [const-valid](const_safety.md#const-safety-check-on-values) in any meaningful way.
  As of 2019-08, we do check them for validity anyway, to be conservative; and indeed constants could be allowed to read from frozen statics.

## `Drop`

The compiler rejects intermediate values (created and discarded during the computation of a static initializer) that implement `Drop`.
The reason for this is simply that the `Drop` implementation might be non-`const fn`
(so really, this is just a special case of static initializers not being able to call non-`const` functions).
This restriction can be lifted once `const impl Drop for Type` (or something similar) is supported.

```rust
struct Foo;

impl Drop for Foo {
    fn drop(&mut self) {
        println!("foo dropped");
    }
}

static FOOO: Foo = Foo; // Ok, drop is never run

// Not ok, cannot run `Foo::drop` because it's not a const fn
static BAR: i32 = (Foo, 42).1;
```

*Dynamic check.* The Miri engine dynamically checks that this is done correctly
by not permitting calls of non-`const` functions.

---

## File: src/skill_tree.md

# Skill tree for const eval features

```skill-tree
[[group]]
name = "cell_ref"
label = "references to interior mutability\nfeature:const_cell_refs"
href = "https://github.com/rust-lang/rust/issues/79703"
items = []

[[group]]
name = "mut_ref"
label = "mutable references in\nconst fn\nfeature:const_mut_refs"
href = "https://github.com/rust-lang/rust/issues/57349"
items = []

[[group]]
name = "const_mut_ref"
label = "mutable references in\ninitializers of const items"
href = "https://github.com/rust-lang/rust/issues/71212"
requires = ["mut_ref"]
items = []

[[group]]
name = "file_output"
label = "write to files\nfrom constants"
href = "https://github.com/rust-lang/const-eval/issues/25"
items = []

[[group]]
name = "final_heap"
label = "heap allocations\nin the final value of constants"
requires = ["heap"]
href = "https://github.com/rust-lang/const-eval/issues/20"
items = []

[[group]]
name = "heap"
label = "heap allocations"
requires = ["mut_ref", "cell_ref", "trait_impl"]
items = []
href = "https://github.com/rust-lang/const-eval/issues/20"

[[group]]
name = "iterators"
label = "iterators"
requires = ["mut_ref", "trait_impl"]
items = []

[[group]]
name = "for"
label = "for loops"
requires = ["trait_impl", "mut_ref"]
items = []

[[group]]
name = "slice_eq"
label = "[T]::eq"
requires = ["for", "fuzzy-ptr-comparisons", "trait_impl"]
items = []

[[group]]
name = "box_new"
label = "Box::new"
requires = ["heap", "trait_bound_opt_out", "drop"]
items = []

[[group]]
name = "ptr-is-null"
label = "<*T>::is_null\nfeature:const_ptr_is_null"
requires = ["fuzzy-ptr-comparisons"]
href = "https://github.com/rust-lang/rust/issues/74939"
items = []

[[group]]
name = "fuzzy-ptr-comparisons"
label = "guaranteed_eq and\nguaranteed_ne\nfeature:const_compare_raw_pointers"
href = "https://github.com/rust-lang/rust/issues/53020"
requires = []
items = []

[[group]]
name = "unconst_rules"
label = "unconst operations"
href = "https://github.com/rust-lang/const-eval/issues/14"
items = []

[[group]]
name = "raw_ptr_deref"
label = "feature:const_raw_ptr_deref"
items = []
href = "https://github.com/rust-lang/rust/issues/51911"

[[group]]
name = "offset_of"
label = "offset_of"
items = []
requires = [
  "raw_ptr_deref",
  "raw_ref_macros",
  "maybe_uninit_as_ptr",
  "offset_from",
]

[[group]]
name = "offset"
label = "offset\nfeature:const_ptr_offset"
href = "https://github.com/rust-lang/rust/issues/71499"
items = []

[[group]]
name = "offset_from"
label = "offset_from\nfeature:ptr_offset_from"
href = "https://github.com/rust-lang/rust/issues/41079"
items = []

[[group]]
name = "raw_ref_macros"
label = "raw_ref maros\nfeature:raw_ref_macros"
href = "https://github.com/rust-lang/rust/issues/73394"
items = []

[[group]]
name = "maybe_uninit_as_ptr"
label = "MaybeUninit::as_ptr\nfeature:const_maybe_uninit_as_ptr"
href = "https://github.com/rust-lang/rust/issues/75251"
items = []

[[group]]
name = "question_mark"
label = "using ? in const"
href = "https://github.com/rust-lang/rust/issues/74935"
requires = ["trait_impl"]
items = []

[[group]]
name = "mutex_new"
label = "Mutex::new"
href = "https://github.com/rust-lang/rust/issues/66806"
items = []
requires = ["parking_lot"]

[[group]]
name = "parking_lot"
label = "`parking_lot` in `std`"
href = "https://github.com/rust-lang/rust/issues/73714"
items = []

[[group]]
name = "const_fn_in_patterns"
label = "const fn callable in patterns"
href = "https://github.com/rust-lang/rust/issues/57240"
requires = ["const-blocks"]
items = []

[[group]]
name = "from_str"
label = "FromStr"
href = "https://github.com/rust-lang/rust/issues/59133"
requires = ["trait_impl"]
items = []

[[group]]
name = "float"
label = "floats in const fn"
href = "https://github.com/rust-lang/rust/issues/57241"
items = [
    { label = "from_bits" },
    { label = "to_bits" },
    { label = "float math, arguments and return types" },
]

[[group]]
name = "float_classify"
label = "feature:const_float_classify"
href = "https://github.com/rust-lang/rust/issues/72505"
items = []
requires = ["float_bits_conv"]

[[group]]
name = "float_bits_conv"
label = "feature:const_float_bits_conv"
href = "https://github.com/rust-lang/rust/issues/72447"
items = []
requires = ["float"]

[[group]]
name = "const-assert-eq"
label = "assert_eq!"
requires = ["trait_impl", "panic_fmt"]
href = "https://github.com/rust-lang/rust/issues/74925"
items = []

[[group]]
name = "const-blocks"
label = "inline const"
href = "https://github.com/rust-lang/rust/issues/76001"
items = []

[[group]]
label = "panic! with formatting"
name = "panic_fmt"
requires = ["format_args"]
href = "https://github.com/rust-lang/rust/issues/51999"
items = []

[[group]]
label = "feature:const_discriminant"
name = "discriminant"
href = "https://github.com/rust-lang/rust/pull/69825"
items = []

[[group]]
label = "feature:const_trait_bound_opt_out"
name = "trait_bound_opt_out"
href = "https://github.com/rust-lang/rust/issues/67794"
items = []

[[group]]
label = "feature:const_trait_impl"
name = "trait_impl"
href="https://github.com/rust-lang/rust/issues/67792"
items = []
requires = ["trait_bound_opt_out"]

[[group]]
label = "feature:const_raw_ptr_to_usize_cast"
name = "raw_ptr_to_usize_cast"
href="https://github.com/rust-lang/rust/issues/51910"
items = []
requires = ["unconst_rules"]

[[group]]
label = "feature:const_extern_fn"
name = "extern_const_fn"
href = "https://github.com/rust-lang/rust/issues/64926"
items = []

[[group]]
label = "const function pointers"
name = "const_fn_ptr"
href = "https://github.com/rust-lang/rust/issues/63997"
items = []
requires = ["trait_impl", "trait_bound_opt_out"]

[[group]]
label = "format!"
name = "format"
items = []
requires = ["string", "format_args"]

[[group]]
label = "format_args!"
name = "format_args"
items = []
requires = ["trait_impl", "fuzzy-ptr-comparisons"]

[[group]]
label = "String operations"
name = "string"
items = []
requires = ["vec"]

[[group]]
label = "Vec operations"
name = "vec"
items = []
requires = ["mut_ref", "heap", "trait_impl", "drop", "raw_ptr_deref"]

[[group]]
label = "Drop"
name = "drop"
items = []
requires = ["mut_ref", "trait_impl"]

[[group]]
label = "ptr::copy_nonoverlapping\nfeature:const_intrinsic_copy"
name = "copy_nonoverlapping"
items = []
href = "https://github.com/rust-lang/rust/issues/80697"
requires = ["raw_ptr_deref", "mut_ref"]

[[group]]
label = "async functions\nand blocks"
name = "async"
items = []
href = "https://github.com/rust-lang/rust/issues/69431"
requires = ["trait_impl"]
```

---

## File: src/SUMMARY.md

# Summary

- [Feature Skill Tree](./skill_tree.md)

---

## File: .github/workflows/deploy_skill_tree.yml

name: github pages

on:
  push:
    branches:
      - master

jobs:
  deploy:
    runs-on: ubuntu-18.04
    steps:
      - uses: actions/checkout@v2

      - name: Setup mdBook
        uses: peaceiris/actions-mdbook@v1
        with:
          mdbook-version: '0.4.5'
          # mdbook-version: 'latest'

      - name: Cache multiple paths
        uses: actions/cache@v2
        with:
          path: |
            ~/.cargo/bin
          key: ${{ runner.os }}

      - name: Install mdbook-skill-tree
        run: cargo install --git https://github.com/nikomatsakis/skill-tree.git mdbook-skill-tree
        continue-on-error: true # we don't care if this is already cached

      - name: Install skill tree files
        run: mdbook-skill-tree install

      - run: mdbook build

      - name: Deploy
        uses: peaceiris/actions-gh-pages@v3
        with:
          github_token: ${{ secrets.GITHUB_TOKEN }}
          publish_dir: ./book