590763062154d9ead86e1f5afe76acba48c95fcd
[web.git] / ralf / _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 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 appearling 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
43 > *CTFE must be deterministic.*
44
45 If not, the compiler could end up thinking that two arrays have the same length, but then later compute different layouts.
46 That would be a disaster.
47 So, any kind of external input and any kind of non-determinism is a complete no-go for CTFE.
48 This does not just concern I/O, even converting a reference to a `usize` is not deterministic.
49
50 The compiler will throw a CTFE error if such an operation is ever attempted to be executed.
51 Those programs that *are* executable in const context are called *const safe*:
52
53 > *A program is const safe if it can be executed by CTFE without hitting an error (panics are allowed).*
54
55 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.
56 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.
57
58 One very interesting question now is whether some given function `foo` should be allowed to be called in const context.
59 We could just always say "yes", and rely on the fact that CTFE will throw an error when `foo` does anything fishy.
60 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.
61 In other words, making *any* function not const-safe any more would be a semver violation because it could break downstream crates.
62
63 The typical mechanism to solve that problem is to have an annotation that explicitly marks a function as "usable in const context".
64 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`.
65 The compiler can now reject calling non-`const` functions in const context, so library authors can add non-const-safe operations without breaking semver.
66
67 ## Const Type System and Const Soundness
68
69 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.
70 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.
71 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.
72 This type system does not allow calls to non-`const` functions.
73
74 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.
75 What else?
76
77 Before we go on and add random additional checks, let us step back and think about what our goals are here.
78 Typically, the purpose of a type system is to establish some sort of guarantee for a well-typed program.
79 For Rust's "main" ("run-time") type system, that guarantee is "no undefined behavior", which means no memory errors and no data races.
80 What is the guarantee for our new const type system?
81 We have already talked about it above: It's const safety!
82 This leads us to the definition of const soundness:
83
84 > *Our const type system is sound if well-typed programs are const-safe.*
85
86 Again, notice how this is very similar to the correctness statement for the run-time type system, which guarantees run-time safety.
87
88 However, we have to be a bit careful here.
89 Consider the following piece of code:
90 {% highlight rust %}
91 const fn is_eight_mod_256(x: usize) -> bool { x % 256 == 8 }
92 {% endhighlight %}
93 We will definitely want to allow this code.
94 Why should `==` or `%` not be const-safe?
95 Well, we could call our function as follows:
96 {% highlight rust %}
97 is_eight_mod_256(Box::new(0).into_raw() as usize);
98 {% endhighlight %}
99 That statement is certainly *not* const-safe as the result depends on where exactly the allocator puts our `Box`.
100 However, we want to blame the `as usize` for this issue, not the `is_eight_mod_256`.
101
102 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.
103 An integer obtained from a pointer is valid for `usize` at run-time, but it is *not* valid for `usize` in const mode!
104 After all, there are basic arithmetic operations that we expect all `usize` to support, that CTFE cannot support for pointers.
105
106 > *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).*
107
108 Under this definition, `is_eight_mod_256` is const-safe because whenever `x` is an actual integer, it will evaluate without any error.
109 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!
110 This provides a solid justification for rejecting such casts in const context.
111
112 ## CTFE correctness
113
114
115 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.
116 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.
117 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.
118
119 In fact, right now miri will reject all operations on raw pointers.
120 They all raise a CTFE error and hence must all be rejected by the const type system.
121 The plan is to change miri so that it can support more operations, but we have to be careful in doing so.
122 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:
123 CTFE, at least if it succeeds, should match run-time behavior!
124
125 > *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.*
126
127 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".
128
129 Or, do we?
130 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.
131 Maybe surprisingly, it turns out that this would not be a soundness issue!
132 All we care about for the purpose of soundness is for CTFE to be deterministic, as already discussed.
133 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.
134
135 That said, not being CTFE correct is surely very surprising and we should avoid it best we can.
136 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).
137 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.
138 I think it is possible to achieve CTFE correctness for all other operations, and I think we should strive to do so.
139
140 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.
141 That is a deliberate choice because it lets us gradually improve the operations supported by CTFE, but it is a choice that not everyone might agree with.
142
143 ## Unsafe Blocks in Const Context
144
145 Let's say we want to extend miri to support more operations on raw pointers.
146 We know we have to be careful about keeping miri deterministic, and about maintaining CTFE correctness.
147 Which operations will we be able to support?
148
149 Notice that at this point, const soundness and the related const safety are *not* a concern yet.
150 Those ideas come into play when we are changing the const type system to allow more operations.
151 CTFE determinism and correctness, however, are properties of the CTFE engine (miri) itself.
152
153 Let us look at the following example:
154 {% highlight rust %}
155 const fn make_a_bool() -> bool {
156     let x = Box::new(0);
157     let x_ptr = &*x as *const i32;
158     drop(x);
159     let y = Box::new(0);
160     let y_ptr = &*y as *const i32;
161     x_ptr == y_ptr
162 }
163 {% endhighlight %}
164 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`.
165 However, due to CTFE being deterministic, we have to pick *one* concrete answer at compile-time, and that may not be the right answer.
166 Hence we cannot allow this program to execute under CTFE if we want to maintain CTFE correctness.
167 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.
168 The only actually problematic operation here is testing two raw pointers for equality:
169 Because one of the pointers is dangling, we can not deterministically predict the result of this comparison!
170
171 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.
172
173 Now, let us go one level up and look at the const type system.
174 We have seen that comparing raw pointers can raise a CTFE error, so this is actually not a const-safe operation.
175 Similar to casting pointers to integers, we have to make the const type system reject code that compares raw pointers.
176 However, it seems like a shame to not even allow comparing two *references* for equality, after converting them to raw pointers!
177 After all, references never dangle, so this is a perfectly const-safe operation.
178
179 Lucky enough, Rust *already* has an answer to the need to side-step the type system in controlled ways: `unsafe` blocks.
180 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.
181 So, we should be able to write the following:
182 {% highlight rust %}
183 const fn ptr_eq<T>(x: &T, y: &T) -> bool {
184     unsafe { x as *const _ == y as *const _ }
185 }
186 {% endhighlight %}
187 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.
188 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.
189 For this example, the reason no CTFE error can arise is that references cannot dangle.
190 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.
191 This is, again, in perfect analogy with types like `Vec` being entirely safe to use from safe Rust even though `Vec` internally uses plenty of potentially unsafe operations.
192
193 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.
194 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.
195
196 ## Static Promotion
197
198 There is one more aspect to CTFE in Rust that I have not yet touched on: Promotion of static values.
199 This is the mechanism that makes the following code well-typed:
200 {% highlight rust %}
201 fn make_a_3() -> &'static i32 { &3 }
202 {% endhighlight %}
203 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.
204 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`.
205 This also works with e.g. `&(3+4)`.
206 Static variables, like `const`, are computed at compile time and hence CTFE comes into play.
207
208 The fundamentally new aspect to this is that *the user did not ask for the value to be promoted*.
209 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.
210 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.
211 You probably already guessed it, but what I am proposing is to use the const type system for that purpose.
212 Const soundness already says that this is a way to ensure const safety.
213
214 I propose to only ever promote values that are *safely* const-well-typed.
215 (So, we will not promote values involving const-unsafe operations even when we are in an unsafe block.)
216 When there are function calls, the function must be a safe `const fn` and all arguments, again, const-well-typed.
217 For example, `&is_eight_mod_256(13)` would be promoted but `&is_eight_mod_256(Box::new(0).into_raw() as usize)` would not.
218 As usual for type systems, this is an entirely local analysis that does not look into other functions' bodies.
219 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.
220
221 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.
222 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.
223 However, this can only break code within the same crate and can be fixed locally, so it seems like a reasonable compromise to me.
224
225 Another interesting point to consider is that we probably care much more about CTFE correctness when thinking about promotion.
226 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.
227 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.
228 (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.)
229 I am not sure which effect that should or will have for promotion.
230
231 ## Conclusion
232
233 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).
234 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).
235
236 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.
237 Let the type systems guide us :)
238
239 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.
240 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)!