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

   1 ---
   2 title: "What is a place expression?"
   3 categories: programming rust
   4 ---
   5
   6 One of the more subtle aspects of the Rust language is the fact that there are actually two kinds of expressions:
   7 *value expressions* and *place expressions*.
   8 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.
   9 However, when it comes to unsafe code, a proper understanding of this dichotomy of expressions can be required.
  10 Consider the following [example](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=9a8802d20da16d6569510124c5827794):
  11
  12 ```rust
  13 #[repr(packed)]
  14 struct MyStruct {
  15   field: i32
  16 }
  17
  18 let x = MyStruct { field: 42 };
  19 let ptr = &raw const x.field;
  20 // This line is fine.
  21 let ptr_copy = &raw const *ptr;
  22 // But this line has UB!
  23 let val = *ptr;
  24 ```
  25
  26 Here I am using the unstable but soon-to-be-stabilized "raw borrow" operator, `&raw const`.
  27 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.
  28
  29 The last line has Undefined Behavior (UB) because `ptr` points to a field of a packed struct, which is not sufficiently aligned.
  30 But how can it be the case that evaluating `*ptr` is UB, but evaluating `&raw const *ptr` is fine?
  31 Evaluating an expression should proceed by first evaluating the sub-expressions and then doing something with the result.
  32 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?
  33 That is the topic of this post.
  34
  35 <!-- MORE -->
  36
  37 ### Making the implicit explicit
  38
  39 The main reason why this dichotomy of place expressions and value expressions is so elusive is that it is entirely implicit.
  40 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.
  41
  42 Normally, we may think of (a fragment of) the grammar of Rust expressions roughly as follows:
  43
  44 > _Expr_ ::= \
  45 > &nbsp;&nbsp; _Literal_ | _LocalVar_ | _Expr_ `+` _Expr_ | `&` _BorMod_ _Expr_ | `*` _Expr_ | \
  46 > &nbsp;&nbsp; _Expr_ `.` _Field_ | _Expr_ `=` _Expr_ | ... \
  47 > _BorMod_ ::= `` | `mut` | `raw` `const` | `raw` `mut` \
  48 > _Statement_ ::= \
  49 > &nbsp;&nbsp; `let` _LocalVar_ `=` _Expr_ `;` | ...
  50
  51 This directly explains why we can write expressions like `*ptr = *other_ptr + my_var`.
  52
  53 However, to understand places and values, it is instructive to consider a different grammar that explicitly has two kinds of expressions.
  54 I will first give the grammar, and then explain it with some examples:
  55
  56 > _ValueExpr_ ::= \
  57 > &nbsp;&nbsp; _Literal_ | _ValueExpr_ `+` _ValueExpr_ | `&` _BorMod_ _PlaceExpr_ | \
  58 > &nbsp;&nbsp; _PlaceExpr_ `=` _ValueExpr_ | `load` _PlaceExpr_ \
  59 > _PlaceExpr_ ::= \
  60 > &nbsp;&nbsp; _LocalVar_ | `*` _ValueExpr_ | _PlaceExpr_ `.` _Field_ \
  61 > _Statement_ ::= \
  62 > &nbsp;&nbsp; `let` _LocalVar_ `=` _ValueExpr_ `;` | ...
  63
  64 *Value expressions* are those expressions that compute a value: literals like `5`, computations like `5 + 7`,
  65 but also expressions that compute values of pointer type like `&my_var`.
  66 However, the expression `my_var` (referencing a local variable), according to this grammar, is *not* a value expression, it is a *place expression*.
  67 This is because `my_var` actually denotes a place in memory, and there's multiple things one can do with a place:
  68 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),
  69 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).
  70 Besides local variable, 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.
  71 Furthermore, given a place of struct type, we can use a field projection to obtain a place just for that field.
  72
  73 This may sound odd, because it means that `let new_var = my_var;` is not actually a valid statement in our grammar!
  74 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]
  75 `load` takes a place and, as the name indicates, performs a load from memory to obtain the value currently stored in this place.
  76 The desugared form of the statement therefore is `let new_var = load my_var;`.
  77
  78 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`.
  79 That's a lot of `load` expressions!
  80 It is instructive to convince yourself that every one of them is necessary to make this term fit the grammar.
  81 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 `+`).
  82 However, the left-hand side of `=` is a place expression, so we do not `load` the result of the `*` there.
  83
  84 [^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.
  85
  86 Since the `load` operator is introduced implicitly, it is sometimes referred to a "place-to-value coercion".
  87 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.
  88 So let us write the relevant part of that example again, using our more explicit grammar:
  89 ```rust
  90 let ptr = &raw const x.field;
  91 // This line is fine.
  92 let ptr_copy = &raw const *(load ptr);
  93 // But this line has UB!
  94 let val = load *(load ptr);
  95 ```
  96
  97 Suddenly, it makes perfect sense why the last line has UB but the previous one does not!
  98 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.
  99 This is worth repeating: the `*` operator, usually referred to as "dereferencing a pointer", *does not access memory in any way*.
 100 All it does is take a value of pointer type, and convert it into a place.
 101 This is a pure operation that can never fail.
 102 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.
 103
 104 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.
 105 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]
 106 However, it is *not* legal to load from (or store to) an unaligned place, which is why `load *(load ptr)` is UB.
 107
 108 [^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.
 109
 110 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`.
 111
 112 ### Other examples of place expression surprises
 113
 114 The other main example where place expressions can lead to surprising behavior is in combination with the `_` pattern.
 115 For instance:
 116 ```rust
 117 let ptr = std::ptr::null::<i32>();
 118 let _ = *ptr; // This is fine!
 119 let _val = *ptr; // This is UB.
 120 ```
 121
 122 The reason for this is that the `_` pattern does *not* incur a place-to-value coercion.
 123 The desugared form of the relevant part of this code is:
 124 ```rust
 125 let _ = *(load ptr); // This is fine!
 126 let _val = load *(load ptr); // This is UB.
 127 ```
 128 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).
 129 No value is ever constructed when a place expression is used with the `_` pattern.
 130 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.
 131
 132 The same also happens with `match` statements:
 133 ```rust
 134 let ptr = std::ptr::null::<i32>();
 135 match *ptr { _ => "happy" } // This is fine!
 136 match *ptr { _val => "not happy" } // This is UB.
 137 ```
 138 The scrutinee of a `match` expression is a place expression, and if the pattern is `_` then a value is never constructed.
 139 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.
 140
 141 ### Are there also value-to-place coercions?
 142
 143 So far, we have discussed what happens when a place expression is encountered in a spot where a value expression was expected.
 144 But what about the opposite case?
 145 Consider:
 146 ```rust
 147 let x = &mut 15;
 148 ```
 149 According to our grammar, `&` (in this case with the `mut` modifier) needs a place expression, but `15` is a value expression.
 150 How can the Rust compiler accept such code?
 151
 152 In this case, the desugaring involves introducing new "temporary" local variables:
 153 ```rust
 154 let mut _tmp = 15;
 155 let x = &mut _tmp;
 156 ```
 157 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;
 158 the key point is that this transformation again makes the program valid according to the more explicit grammar.
 159
 160 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.
 161 Introducing temporaries here is very unlikely to produce a meaningful result, so there's no good reason to accept such code.
 162
 163 ### Conclusion
 164
 165 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.
 166 If you are only writing safe code, you can almost always entirely forget about this transformation.
 167 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.
 168 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.
 169 I hope that giving a name to this implicit `load` operator can help demystify the topic of places and values. :)