personal/_posts/2018-07-19-const.md

   1 ---
   2 title: "Thoughts on Compile-Time Function Evaluation and Type Systems"
   3 categories: internship rust
   4 forum: https://internals.rust-lang.org/t/thoughts-on-compile-time-function-evaluation-and-type-systems/8004
   5 ---
   6
   7 For some time now (since the 1.26 release, to be precise), Rust has a [very powerful machinery for CTFE](https://github.com/rust-lang/rust/pull/46882), or compile-time function evaluation.
   8 Since then, there have been various discussions about which operations should be allowed during CTFE, which checks the compiler should do, how this all relates to promotion and which kinds of guarantees we should be able to expect around CTFE.
   9 This post is my take on those topics, and it should not be surprising that I am going to take a very type-system centric view.
  10 Expect something like a structured brain dump, so there are some unanswered questions towards the end as well.
  11
  12 <!-- MORE -->
  13
  14 ## Some Background
  15
  16 CTFE is the mechanism used by the compiler, primarily, to evaluate items like `const x: T = ...;`.
  17 The `...` here is going to be Rust code that must be "run" at compile-time, because it can be used as a constant in the code -- for example, it can be used for array lengths.
  18
  19 Notice that CTFE is *not* the same as constant propagation: Constant propagation is an optimization pass done by compilers like LLVM that will opportunistically change code like `3 + 4` into `7` to avoid run-time work.
  20 Being an optimization, constant propagation must, by definition, not change program behavior and will not be observable at all (other than performance).
  21 CTFE, on the other hand, is about code that *must* be executed at compile-time because the compiler needs to know its result to proceed -- for example, it needs to know the size of an array to compute how to lay out data in memory.
  22 You can statically see, just from the syntax of the code, whether CTFE applies to some piece of code or not:
  23 CTFE is only used in places like the value of a `const` or the length of an array.
  24 {% highlight rust %}
  25 fn demo() {
  26   const X: u32 = 3 + 4; // CTFE
  27   let x: u32 = 4 + 3; // no CTFE (but maybe constant propagation)
  28 }
  29 {% endhighlight %}
  30 We say that the `3 + 4` above is in *const context* and hence subject to CTFE, but the `4 + 3` is not.
  31
  32 ## Const Safety
  33
  34 Not all operations can be used in const context.
  35 For example, it makes no sense to compute your array length as "please go read that file from disk and compute something" -- we can't know what will be on the disk when the program actually runs.
  36 We could use the disk of the machine compiling the program, but that does not sound very appealing either.
  37 Things get even worse when you consider letting the program send information to the network.
  38 Clearly, we don't want CTFE to have actually observable side-effects outside of compilation.
  39
  40 In fact, just naively letting programs read files would also be grossly unsafe:
  41 When computing the length of an array twice, it is important that we obtain the same result.
  42 **Update:** As @eddyb points out, things get even worse once you consider const generics, traits, and coherence: At that point, you have to [rely on evaluating the same expression in different crates to produce the same result](https://internals.rust-lang.org/t/mir-constant-evaluation/3143/47). **/Update**
  43
  44 > *CTFE must be deterministic.*
  45
  46 If not, the compiler could end up thinking that two arrays have the same length, but then later compute different layouts.
  47 That would be a disaster.
  48 So, any kind of external input and any kind of non-determinism is a complete no-go for CTFE.
  49 This does not just concern I/O, even converting a reference to a `usize` is not deterministic.
  50
  51 The compiler will throw a CTFE error if such an operation is ever attempted to be executed.
  52 Those programs that *are* executable in const context are called *const safe*:
  53
  54 > *A program is const safe if it can be executed by CTFE without hitting an error (panics are allowed).*
  55
  56 This is very much in analogy with the idea that a *safe* (or *run-time safe*, to distinguish it from const safe) program is a program that does not cause any memory errors or data races.
  57 In fact, we will see that this analogy between "programs that are well-behaved under CTFE" (const safety) and "programs that do not cause UB" (run-time safety) can carry us very far.
  58
  59 One very interesting question now is whether some given function `foo` should be allowed to be called in const context.
  60 We could just always say "yes", and rely on the fact that CTFE will throw an error when `foo` does anything fishy.
  61 The problem with this approach is that, if `foo` is in a library, updating the library might change `foo` in a way that makes it no longer const-safe.
  62 In other words, making *any* function not const-safe any more would be a semver violation because it could break downstream crates.
  63
  64 The typical mechanism to solve that problem is to have an annotation that explicitly marks a function as "usable in const context".
  65 In Rust, the proposed mechanism for this purpose is [`const fn`](https://github.com/rust-lang/rust/issues/24111); in C++ it is called `constexpr`.
  66 The compiler can now reject calling non-`const` functions in const context, so library authors can add non-const-safe operations without breaking semver.
  67
  68 ## Const Type System and Const Soundness
  69
  70 This leads us to the interesting situation that the compiler will reject code in const context that it would accept just fine outside of const context.
  71 In particular, the body of a `const fn` is *also* considered to be in const context -- otherwise, if we allowed calling arbitrary functions, we would have the same problem again.
  72 One useful way to think about this is that we have a second type system, a "const type system", that is used to type-check code in const context.
  73 This type system does not allow calls to non-`const` functions.
  74
  75 It should probably also not allow casting a reference to an integer, because (as discussed above) that is a non-deterministic operation which cannot be performed during CTFE.
  76 What else?
  77
  78 Before we go on and add random additional checks, let us step back and think about what our goals are here.
  79 Typically, the purpose of a type system is to establish some sort of guarantee for a well-typed program.
  80 For Rust's "main" ("run-time") type system, that guarantee is "no undefined behavior", which means no memory errors and no data races.
  81 What is the guarantee for our new const type system?
  82 We have already talked about it above: It's const safety!
  83 This leads us to the definition of const soundness:
  84
  85 > *Our const type system is sound if well-typed programs are const-safe.*
  86
  87 Again, notice how this is very similar to the correctness statement for the run-time type system, which guarantees run-time safety.
  88
  89 However, we have to be a bit careful here.
  90 Consider the following piece of code:
  91 {% highlight rust %}
  92 const fn is_eight_mod_256(x: usize) -> bool { x % 256 == 8 }
  93 {% endhighlight %}
  94 We will definitely want to allow this code.
  95 Why should `==` or `%` not be const-safe?
  96 Well, we could call our function as follows:
  97 {% highlight rust %}
  98 is_eight_mod_256(Box::into_raw(Box::new(0)) as usize);
  99 {% endhighlight %}
 100 That statement is certainly *not* const-safe as the result depends on where exactly the allocator puts our [`Box`](https://doc.rust-lang.org/stable/std/boxed/struct.Box.html).
 101 However, we want to blame the `as usize` for this issue, not the `is_eight_mod_256`.
 102
 103 The solution is for the const type system to not just have separate rules about which operations are allowed, we also must change our notion of which values are "valid" for a given type.
 104 An integer obtained from a pointer is valid for `usize` at run-time, but it is *not* valid for `usize` in const mode!
 105 After all, there are basic arithmetic operations that we expect all `usize` to support, that CTFE cannot support for pointers.
 106
 107 > *A function is const-safe if, when executed with const-valid arguments, it does not trigger a CTFE error and returns a const-valid result (if it returns at all).*
 108
 109 Under this definition, `is_eight_mod_256` is const-safe because whenever `x` is an actual integer, it will evaluate without any error.
 110 At the same time, this shows that converting a reference into `usize` is *not* const-safe, because the input of this operation is const-valid, but the output is not!
 111 This provides a solid justification for rejecting such casts in const context.
 112
 113 ## CTFE correctness
 114
 115
 116 In Rust, CTFE is performed by miri, a MIR interpreter that used to be a [separate project](https://github.com/solson/miri/) but whose core engine has been integrated into rustc.
 117 miri will execute the code in const context step-by-step and just complain and fail with an error when an operation cannot be performed.
 118 This does not just concern non-determinism; miri does not support everything it could support because @oli-obk is [super careful](https://github.com/rust-lang/rust/blob/5ba21844f6c85a0cd55c8ea0250d5cd758134f84/src/librustc_mir/interpret/const_eval.rs#L199) about not accidentally stabilizing behavior that should undergo an RFC.
 119
 120 In fact, right now miri will reject all operations on raw pointers.
 121 They all raise a CTFE error and hence must all be rejected by the const type system.
 122 The plan is to change miri so that it can support more operations, but we have to be careful in doing so.
 123 I have already mentioned that miri must be deterministic, but there is another point to consider that you might have expected to play a much more prominent role:
 124 CTFE, at least if it succeeds, should match run-time behavior!
 125
 126 > *CTFE is correct if, when it loops forever, completes with a result, or panics, that behavior matches the run-time behavior of the same code.*
 127
 128 We clearly do not want code to behave differently when it lives in const context and is run by CTFE, and when it is compiled to machine-code and executed "for real".
 129
 130 Or, do we?
 131 Don't get me wrong, I am not advocating for deliberately breaking that property, but it sure is worth considering what would go wrong if miri was *not* CTFE-correct.
 132 Maybe surprisingly, it turns out that this would not be a soundness issue!
 133 All we care about for the purpose of soundness is for CTFE to be deterministic, as already discussed.
 134 We don't re-run the same code at run-time and rely on it still doing the same, so nothing actually breaks if CTFE behavior diverges from run-time behavior.
 135
 136 That said, not being CTFE correct is surely very surprising and we should avoid it best we can.
 137 However, I am told that actually predicting the result of floating-point operations deterministically [is extremely hard](https://gafferongames.com/post/floating_point_determinism/) and [LLVM isn't exactly helping](https://github.com/rust-lang/rust/issues/24111#issuecomment-386765720).
 138 So, we will likely have to live with either considering floating point operations to be const-unsafe (raising a CTFE error), or not having CTFE correctness when floating point operations are involved.
 139 I think it is possible to achieve CTFE correctness for all other operations, and I think we should strive to do so.
 140
 141 Before we go on, notice that CTFE correctness as defined above does not say anything about the case where CTFE fails with an error, e.g. because of an unsupported operation.
 142 CTFE would be trivially correct (in the above sense) if it just always immediately returned an error.
 143 However, since const-safe programs cannot error during CTFE, we know from CTFE correctness that *those* programs *do* in fact behave exactly the same at compile-time and at run-time.
 144
 145 ## Unsafe Blocks in Const Context
 146
 147 Let's say we want to extend miri to support more operations on raw pointers.
 148 We know we have to be careful about keeping miri deterministic, and about maintaining CTFE correctness.
 149 Which operations will we be able to support?
 150
 151 Notice that at this point, const soundness and the related const safety are *not* a concern yet.
 152 Those ideas come into play when we are changing the const type system to allow more operations.
 153 CTFE determinism and correctness, however, are properties of the CTFE engine (miri) itself.
 154
 155 Let us look at the following example:
 156 {% highlight rust %}
 157 const fn make_a_bool() -> bool {
 158     let x = Box::new(0);
 159     let x_ptr = &*x as *const i32;
 160     drop(x);
 161     let y = Box::new(0);
 162     let y_ptr = &*y as *const i32;
 163     x_ptr == y_ptr
 164 }
 165 {% endhighlight %}
 166 At run-time, whether this function returns `true` or `false` depends on whether or not the allocator re-used the space for `x` when allocating `y`.
 167 However, due to CTFE being deterministic, we have to pick *one* concrete answer at compile-time, and that may not be the right answer.
 168 Hence we cannot allow this program to execute under CTFE if we want to maintain CTFE correctness.
 169 Supporting memory allocation in a deterministic way is perfectly feasible (in fact, miri already has that implemented), and casting a reference to a raw pointer changes nothing but the type.
 170 The only actually problematic operation here is testing two raw pointers for equality:
 171 Because one of the pointers is dangling, we can not deterministically predict the result of this comparison!
 172
 173 In other words, if/when miri learns how to compare pointers, we must make it raise a CTFE error if one of the pointers is dangling (points to unallocated memory), or else we would violate CTFE correctness.
 174
 175 Now, let us go one level up and look at the const type system.
 176 We have seen that comparing raw pointers can raise a CTFE error, so this is actually not a const-safe operation.
 177 Similar to casting pointers to integers, we have to make the const type system reject code that compares raw pointers.
 178 However, it seems like a shame to not even allow comparing two *references* for equality, after converting them to raw pointers!
 179 After all, references never dangle, so this is a perfectly const-safe operation.
 180
 181 Lucky enough, Rust *already* has an answer to the need to side-step the type system in controlled ways: `unsafe` blocks.
 182 Comparing raw pointers is not allowed by the const type system because it is not const-safe, but just like we allow run-time-unsafe operations to be performed in unsafe blocks, we can allow const-unsafe operations as well.
 183 So, we should be able to write the following:
 184 {% highlight rust %}
 185 const fn ptr_eq<T>(x: &T, y: &T) -> bool {
 186     unsafe { x as *const _ == y as *const _ }
 187 }
 188 {% endhighlight %}
 189 As usual when writing `unsafe` code, we have to be careful not to violate the safety guarantees that are usually upheld by the type system.
 190 We have to manually ensure that, *if* our inputs are const-valid, then we will not trigger a CTFE error and return a const-valid result.
 191 For this example, the reason no CTFE error can arise is that references cannot dangle.
 192 We can thus provide `ptr_eq` as an abstraction that is entirely safe to use in const context, even though it contains a potentially const-unsafe operation.
 193 This is, again, in perfect analogy with types like [`Vec`](https://doc.rust-lang.org/stable/std/vec/struct.Vec.html) being entirely safe to use from safe Rust even though `Vec` internally uses plenty of potentially unsafe operations.
 194
 195 Whenever I said above that some operation must be rejected by the const type system, what that really means is that the operation should be unsafe in const context.
 196 Even pointer-to-integer casts can be used internally in const-safe code, for example to pack additional bits into the aligned part of a pointer in a perfectly deterministic way.
 197
 198 ## Static Promotion
 199
 200 There is one more aspect to CTFE in Rust that I have not yet touched on: Promotion of static values.
 201 This is the mechanism that makes the following code well-typed:
 202 {% highlight rust %}
 203 fn make_a_3() -> &'static i32 { &3 }
 204 {% endhighlight %}
 205 This may look like it should be rejected because we are returning a reference to a locally created value with lifetime `'static`, but instead, Magic (TM) is happening.
 206 The compiler determines that `3` is a static value that can be computed at compile-time and put into static memory (like a `static` variable), and hence `&3` can have lifetime `'static`.
 207 This also works with e.g. `&(3+4)`.
 208 Static variables, like `const`, are computed at compile time and hence CTFE comes into play.
 209
 210 The fundamentally new aspect to this is that *the user did not ask for the value to be promoted*.
 211 That means we have to be really careful when deciding which values to promote: If we promote something that miri cannot evaluate, there will be a CTFE error and we have just broken compilation for no good reason.
 212 We better make sure that we only promote values that we can expect miri to actually be able to compute -- i.e., we should only promote the results of const-safe code.
 213 You probably already guessed it, but what I am proposing is to use the const type system for that purpose.
 214 Const soundness already says that this is a way to ensure const safety.
 215
 216 I propose to only ever promote values that are *safely* const-well-typed.
 217 (So, we will not promote values involving const-unsafe operations even when we are in an unsafe block.)
 218 When there are function calls, the function must be a safe `const fn` and all arguments, again, const-well-typed.
 219 For example, `&is_eight_mod_256(13)` would be promoted but `&is_eight_mod_256(Box::into_raw(Box::new(0)) as usize)` would not.
 220 As usual for type systems, this is an entirely local analysis that does not look into other functions' bodies.
 221 Assuming our const type system is sound, the only way we could possibly have a CTFE error from promotion is when there is a safe `const fn` with an unsound `unsafe` block.
 222
 223 Notably, we are relying on library authors properly writing `unsafe const fn` even for private functions whenever there is a chance that this function might cause a CTFE error for const-valid inputs.
 224 If there is a `const fn` that is actually unsafe, arguing "but it is private and hence that's fine" will not help because the compiler might decide to promote the result of that function.
 225 However, this can only break code within the same crate and can be fixed locally, so it seems like a reasonable compromise to me.
 226
 227 Another interesting point to consider is that we probably care much more about CTFE correctness when thinking about promotion.
 228 After all, the user asked for the run-time behavior; if they are getting a completely different behavior from CTFE, that would lead to problems.
 229 If miri is CTFE-correct except for obscure floating point issues, that means "only" people relying on specific behavior of floating point operations could be affected, and likely LLVM will already violate whatever assumptions those people are making.
 230 (miri's floating point implementation is perfectly sane and should be standards compliant, LLVM and the particularities of x87 rounding are the sources of uncertainty here.)
 231 I am not sure which effect that should or will have for promotion.
 232
 233 ## Conclusion
 234
 235 I have discussed the notions of CTFE determinism and CTFE correctness (which are properties of a CTFE engine like miri), as well as const safety (property of a piece of code) and const soundness (property of a type system).
 236 In particular, I propose that *when type-checking safe code in const context, we guarantee that this code is const-safe*, i.e., that it will not hit a CTFE error (though panics are allowed, just like they are in "run-time" Rust code).
 237
 238 There are still plenty of open questions, in particular around the interaction of [`const fn` and traits](https://github.com/rust-lang/rust/issues/24111#issuecomment-311029471), but I hope this terminology is useful when having those discussions.
 239 Let the type systems guide us :)
 240
 241 Thanks to @oli-obk for feedback on a draft of this post, and to @centril for interesting discussion in #rust-lang that triggered me into developing these ideas and terminology.
 242 If you have feedback or questions, [let's discuss in the internals forum](https://internals.rust-lang.org/t/thoughts-on-compile-time-function-evaluation-and-type-systems/8004)!