personal/_posts/2024-08-14-places.md

   1 ---
   2 title: "What is a place expression?"
   3 categories: programming rust
   4 reddit: /rust/comments/1esavn3/what_is_a_place_expression/
   5 ---
   6
   7 One of the more subtle aspects of the Rust language is the fact that there are actually two kinds of expressions:
   8 *value expressions* and *place expressions*.
   9 Most of the time, programmers do not have to think much about that distinction, as Rust will helpfully insert automatic conversions when one kind of expression is encountered but the other was expected.
  10 However, when it comes to unsafe code, a proper understanding of this dichotomy of expressions can be required.
  11 Consider the following [example](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=9a8802d20da16d6569510124c5827794):
  12
  13 ```rust
  14 // As a "packed" struct, this type has alignment 1.
  15 #[repr(packed)]
  16 struct MyStruct {
  17   field: i32
  18 }
  19
  20 let x = MyStruct { field: 42 };
  21 let ptr = &raw const x.field;
  22 // This line is fine.
  23 let ptr_copy = &raw const *ptr;
  24 // But this line has UB!
  25 // `ptr` is a pointer to `i32` and thus requires 4-byte alignment on
  26 // memory accesses, but `x` is just 1-aligned.
  27 let val = *ptr;
  28 ```
  29
  30 Here I am using the unstable but [soon-to-be-stabilized](https://github.com/rust-lang/rust/pull/127679) "raw borrow" operator, `&raw const`.
  31 You may know it in its stable form as a macro, `ptr::addr_of!`, but the `&` syntax makes the interplay of places and values more explicit so we will use it here.
  32
  33 The last line has Undefined Behavior (UB) because `ptr` points to a field of a packed struct, which is not sufficiently aligned.
  34 But how can it be the case that evaluating `*ptr` is UB, but evaluating `&raw const *ptr` is fine?
  35 Evaluating an expression should proceed by first evaluating the sub-expressions and then doing something with the result.
  36 However, `*ptr` is a sub-expression of `&raw const *ptr`, and we just said that `*ptr` is UB, so shouldn't `&raw const *ptr` also be UB?
  37 That is the topic of this post.
  38
  39 <!-- MORE -->
  40
  41 (You might have already encountered the distinction of place expressions and value expressions in C and C++, where they are called lvalue expressions and rvalue expressions, respectively.
  42 While the basic syntactic concept is the same as in Rust, the exact cases that are UB are different, so we will focus entirely on Rust here.)
  43
  44 ### Making the implicit explicit
  45
  46 The main reason why this dichotomy of place expressions and value expressions is so elusive is that it is entirely implicit.
  47 Therefore, to understand what actually happens in code like the above, the first step is to add some new syntax that lets us make this implicit distinction explicit in the code.
  48
  49 Normally, we may think of (a fragment of) the grammar of Rust expressions roughly as follows:
  50
  51 > _Expr_ ::= \
  52 > &nbsp;&nbsp; _Literal_ | _LocalVar_ | _Expr_ `+` _Expr_ | `&` _BorMod_ _Expr_ | `*` _Expr_ | \
  53 > &nbsp;&nbsp; _Expr_ `.` _Field_ | _Expr_ `=` _Expr_ | ... \
  54 > _BorMod_ ::= `` | `mut` | `raw` `const` | `raw` `mut` \
  55 > _Statement_ ::= \
  56 > &nbsp;&nbsp; `let` _LocalVar_ `=` _Expr_ `;` | ...
  57
  58 This directly explains why we can write expressions like `*ptr = *other_ptr + my_var`.
  59
  60 However, to understand places and values, it is instructive to consider a different grammar that explicitly has two kinds of expressions.
  61 I will first give the grammar, and then explain it with some examples:
  62
  63 > _ValueExpr_ ::= \
  64 > &nbsp;&nbsp; _Literal_ | _ValueExpr_ `+` _ValueExpr_ | `&` _BorMod_ _PlaceExpr_ | \
  65 > &nbsp;&nbsp; _PlaceExpr_ `=` _ValueExpr_ | `load` _PlaceExpr_ \
  66 > _PlaceExpr_ ::= \
  67 > &nbsp;&nbsp; _LocalVar_ | `*` _ValueExpr_ | _PlaceExpr_ `.` _Field_ \
  68 > _Statement_ ::= \
  69 > &nbsp;&nbsp; `let` _LocalVar_ `=` _ValueExpr_ `;` | ...
  70
  71 *Value expressions* are those expressions that compute a value: literals like `5`, computations like `5 + 7`,
  72 but also expressions that compute values of pointer type like `&my_var`.
  73 However, the expression `my_var` (referencing a local variable), according to this grammar, is *not* a value expression, it is a *place expression*.
  74 This is because `my_var` actually denotes a place in memory, and there's multiple things one can do with a place:
  75 one can load the contents of the place from memory (which produces a value), one can create a pointer to the place (which also produces a value, but does not access memory at all),
  76 or one can store a value into this place (which in Rust produces the `()` value, but the side-effect of changing the contents of memory is more relevant).
  77 Besides local variables, the other main example of a place expression is the result of the `*` operator, which takes a *value* (of pointer type) and turns it into a place.
  78 Furthermore, given a place of struct type, we can use a field projection to obtain a place just for that field.
  79
  80 This may sound odd, because it means that `let new_var = my_var;` is not actually a valid statement in our grammar!
  81 To accept this code, the Rust compiler will automatically convert this statement into a form that fits the grammar by adding `load` whenever needed.[^desugar]
  82 `load` takes a place and, as the name indicates, performs a load from memory to obtain the value currently stored in this place.
  83 The desugared form of the statement therefore is `let new_var = load my_var;`.
  84
  85 To consider a more complicated example, the assignment expression `*ptr = *other_ptr + my_var` mentioned above desugars to `*(load ptr) = load *(load other_ptr) + load my_var`.
  86 That's a lot of `load` expressions!
  87 It is instructive to convince yourself that every one of them is necessary to make this term fit the grammar.
  88 In particular, `*` works on a value expression (so we need `load other_ptr` to obtain the value stored in this place) and produces a place expression (so we need to `load` again to obtain a value expression that we can use with `+`).
  89 However, the left-hand side of `=` is a place expression, so we do not `load` the result of the `*` there.
  90
  91 [^desugar]: The Rust compiler does not actually explicitly do such a desugaring, but this happens implicitly as part of compiling the program into MIR form.
  92
  93 Since the `load` operator is introduced implicitly, it is sometimes referred to a "place-to-value coercion".
  94 Understanding where place-to-value coercions or `load` expressions are introduced is the key to understanding the example at the top of this blog post.
  95 So let us write the relevant part of that example again, using our more explicit grammar:
  96 ```rust
  97 let ptr = &raw const x.field;
  98 // This line is fine.
  99 let ptr_copy = &raw const *(load ptr);
 100 // But this line has UB!
 101 let val = load *(load ptr);
 102 ```
 103
 104 Suddenly, it makes perfect sense why the last line has UB but the previous one does not!
 105 The expression `&raw const *(load ptr)` merely computes the place `*(load ptr)` *without ever loading from it*, and then uses `&raw const` to turn that place into a value.
 106 This is worth repeating: the `*` operator, usually referred to as "dereferencing a pointer", *does not access memory in any way*.
 107 All it does is take a value of pointer type, and convert it into a place.
 108 This is a pure operation that can never fail.
 109 In the last line, there is an extra `load` applied to the result of the `*`, and *that* is where a memory access happens---and in this case, UB occurs since the place is not sufficiently aligned.
 110
 111 It is completely legal to evaluate a place expression that produces an unaligned place, and it is also legal to then turn that unaligned place into a raw pointer value.
 112 Generally, in terms of UB, you should think of places as being pretty much like raw pointers: there is no requirement that they point to valid values, or even to existing memory.[^field]
 113 However, it is *not* legal to load from (or store to) an unaligned place, which is why `load *(load ptr)` is UB.
 114
 115 [^field]: One subtlety, however, is that the _PlaceExpr_ `.` _Field_ expression performs *in-bounds* pointer arithmetic using the rules of the [`offset` method](https://doc.rust-lang.org/nightly/std/primitive.pointer.html#method.offset). This is the one case where a place expression does care about pointing to existing memory. This is unfortunate, but optimizations greatly benefit from this rule and since the introduction of the `offset_of!` macro, it should be extremely rare that unsafe code would want to do a field projection on a dangling pointer.
 116
 117 In other words, when `*ptr` is used as a value expression (as it is in our example), then it is *not* a sub-expression of `&raw const *ptr` because the implicit place-to-value coercion adds an extra `load` around `*ptr` that is not added in `&raw const *ptr`.
 118
 119 ### Other examples of place expression surprises
 120
 121 The other main example where place expressions can lead to surprising behavior is in combination with the `_` pattern.
 122 For instance:
 123 ```rust
 124 let ptr = std::ptr::null::<i32>();
 125 let _ = *ptr; // This is fine!
 126 let _val = *ptr; // This is UB.
 127 ```
 128
 129 Note that the grammar above cannot represent this program: in the full grammar of Rust, the `let` syntax is something like "`let` _Pattern_ `=` _PlaceExpr_ `;`",
 130 and then pattern desugaring decides what to do with that place expression.
 131 If the pattern is a binder (the common case), a `load` gets inserted to compute the initial value for the local variable that this binder refers to.
 132 However, if the pattern is `_`, then the place expression still gets evaluated---but the result of that evaluation is simply discarded.
 133 MIR uses a `PlaceMention` statement to indicate these semantics.
 134
 135 In particular, this means that the `_` pattern does *not* incur a place-to-value coercion!
 136 The desugared form of the relevant part of this code is:
 137 ```rust
 138 PlaceMention(*(load ptr)); // This is fine!
 139 let _val = load *(load ptr); // This is UB.
 140 ```
 141 As you can see, the first line does not actually load from the pointer (the only `load` is there to load the pointer itself from the local variable that stores it).
 142 No value is ever constructed when a place expression is used with the `_` pattern.
 143 In contrast, the last line actually creates a new local variable, and therefore a place-to-value coercion is inserted to compute the initial value for that variable.
 144
 145 The same also happens with `match` statements:
 146 ```rust
 147 let ptr = std::ptr::null::<i32>();
 148 match *ptr { _ => "happy" } // This is fine!
 149 match *ptr { _val => "not happy" } // This is UB.
 150 ```
 151 The scrutinee of a `match` expression is a place expression, and if the pattern is `_` then a value is never constructed.
 152 However, when an actual binder is present, this introduces a local variable and a place-to-value coercion is inserted to compute the value that will be stored in that local variable.
 153
 154 **Note on `unsafe` blocks.**
 155 Note that wrapping an expression in a block forces it to be a value expression.
 156 This means that `unsafe { *ptr }` always loads from the pointer!
 157 In other words:
 158 ```rust
 159 let ptr = std::ptr::null::<i32>();
 160 let _ = *ptr; // This is fine!
 161 let _ = unsafe { *ptr }; // This is UB.
 162 ```
 163 The fact that braces force a value expression can occasionally be useful, but the fact that `unsafe` blocks do that is definitely quite unfortunate.
 164
 165 ### Are there also value-to-place coercions?
 166
 167 So far, we have discussed what happens when a place expression is encountered in a spot where a value expression was expected.
 168 But what about the opposite case?
 169 Consider:
 170 ```rust
 171 let x = &mut 15;
 172 ```
 173 According to our grammar, `&` (in this case with the `mut` modifier) needs a place expression, but `15` is a value expression.
 174 How can the Rust compiler accept such code?
 175
 176 In this case, the desugaring involves introducing new "temporary" local variables:
 177 ```rust
 178 let mut _tmp = 15;
 179 let x = &mut _tmp;
 180 ```
 181 The exact scope in which this temporary is introduced is defined by [non-trivial rules](https://github.com/rust-lang/lang-team/blob/master/design-meeting-minutes/2023-03-15-temporary-lifetimes.md) that are outside the scope of this blog post;
 182 the key point is that this transformation again makes the program valid according to the more explicit grammar.
 183
 184 There is one exception to this rule, which is the left-hand side of an assignment operator: if you write something like `15 = 12 + 19`, the value `15` is not turned into a temporary place, and instead the program is rejected.
 185 Introducing temporaries here is very unlikely to produce a meaningful result, so there's no good reason to accept such code.
 186
 187 ### Conclusion
 188
 189 Whenever we are using a place expression where a value is expected, or a value expression where a place is expected, the Rust compiler implicitly transforms our program into a form that matches the grammar given above.
 190 If you are only writing safe code, you can almost always entirely forget about this transformation.
 191 However, if you are writing unsafe code and want to understand why some programs have UB and others do not, it can be crucial to understand what exactly happens.
 192 If you only remember one thing from this blog post, then remember that `*` dereferences a pointer but *does not load from memory*; instead, all it does is turn the pointer into a place---it is the subsequent implicit place-to-value conversion that performs the actual load.
 193 I hope that giving a name to this implicit `load` operator can help demystify the topic of places and values. :)