The short version is that I view Rust types with private invariants as not having just a single invariant, but different invariants that reflect the different "modes" the type can be in.
@cramertj suggested to use "typestate" as terminology here, and I agree that this makes sense.
The short version is that I view Rust types with private invariants as not having just a single invariant, but different invariants that reflect the different "modes" the type can be in.
@cramertj suggested to use "typestate" as terminology here, and I agree that this makes sense.
You may be wondering why sharing is a separate typestate here; shouldn't that just be read-only access to a `T` that someone else owns?
However, that clearly doesn't work for `&Cell`; to explain types with interior mutability we *need* sharing as a separate state.
I explained this in more detail in the previous post, but as a quick example consider that, if you fully own a `RefCell`, the first field (storing the current count of readers/writers) has no special meaning whatsoever.
You may be wondering why sharing is a separate typestate here; shouldn't that just be read-only access to a `T` that someone else owns?
However, that clearly doesn't work for `&Cell`; to explain types with interior mutability we *need* sharing as a separate state.
I explained this in more detail in the previous post, but as a quick example consider that, if you fully own a `RefCell`, the first field (storing the current count of readers/writers) has no special meaning whatsoever.
The [corresponding RFC](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md) explains the entirey new API surface in quite some detail: [`Pin`](https://doc.rust-lang.org/nightly/std/mem/struct.Pin.html), [`PinBox`](https://doc.rust-lang.org/nightly/std/boxed/struct.PinBox.html) and the [`Unpin`](https://doc.rust-lang.org/nightly/std/marker/trait.Unpin.html) marker trait.
I will not repeat that here but only show one example of how to use `Pin` references and exploit their guarantees:
{% highlight rust %}
The [corresponding RFC](https://github.com/rust-lang/rfcs/blob/master/text/2349-pin.md) explains the entirey new API surface in quite some detail: [`Pin`](https://doc.rust-lang.org/nightly/std/mem/struct.Pin.html), [`PinBox`](https://doc.rust-lang.org/nightly/std/boxed/struct.PinBox.html) and the [`Unpin`](https://doc.rust-lang.org/nightly/std/marker/trait.Unpin.html) marker trait.
I will not repeat that here but only show one example of how to use `Pin` references and exploit their guarantees:
{% highlight rust %}
- fn init(mut self: Pin<Self>) {
- unsafe {
- let this = Pin::get_mut(&mut self);
- // Set up self_ref to point to this.data
- this.self_ref = ptr::NonNull::new(&mut this.data as *mut _);
- }
+ fn init(mut self: Pin<SelfReferential>) {
+ let this : &mut SelfReferential = unsafe { Pin::get_mut(&mut self) };
+ // Set up self_ref to point to this.data.
+ this.self_ref = &mut this.data as *const i32;
-
- fn read_ref(mut self: Pin<Self>) -> Option<i32> {
- unsafe {
- let this = Pin::get_mut(&mut self);
- // Dereference self_ref if it is set
- this.self_ref.map(|self_ref| *self_ref.as_ptr())
+
+ fn read_ref(mut self: Pin<SelfReferential>) -> Option<i32> {
+ let this : &mut SelfReferential = unsafe { Pin::get_mut(&mut self) };
+ // Dereference self_ref if it is non-NULL.
+ if this.self_ref == ptr::null() {
+ None
+ } else {
+ Some(unsafe { *this.self_ref })
-The most intersting piece of code here is `read_ref`, which dereferences a raw pointer.
-The reason this is legal is that we can rely on the entire `SelfReferential` not having been moved since `init()` was called (which is the only place that would set the pointer to `Some`).
+**Update:** Previously, the example code used `Option<ptr::NonNull<i32>>`. I think using raw pointers directly makes the code easier to follow. **/Update**
+
+The most intersting piece of code here is `read_ref`, which dereferences a raw pointer, `this.self_ref`.
+The reason this is legal is that we can rely on the entire `SelfReferential` not having been moved since `init()` was called (which is the only place that would set the pointer to something non-NULL).
In particular, if we changed the signature to `fn init(&mut self)`, we could easily cause UB by writing the following code:
{% highlight rust %}
In particular, if we changed the signature to `fn init(&mut self)`, we could easily cause UB by writing the following code:
{% highlight rust %}
`Pin` lets us give a type to `SelfReferantial` that makes it safe to use.
This is in the best tradition of Rust: We are using an expressive type system to provide safe APIs for operations that only have unsafe APIs in other languages (e.g., iterators that avoid iterator invalidation which plague even memory safe languages like Java).
In the following, I will explain how one can prove that our claim of safe encapsulation actually holds true.
`Pin` lets us give a type to `SelfReferantial` that makes it safe to use.
This is in the best tradition of Rust: We are using an expressive type system to provide safe APIs for operations that only have unsafe APIs in other languages (e.g., iterators that avoid iterator invalidation which plague even memory safe languages like Java).
In the following, I will explain how one can prove that our claim of safe encapsulation actually holds true.
However, if we go back to our notion of Rust types that I laid out at the beginning of this post, we notice that it is *impossible* to refer to the "address of `self.data`" in `T.own`!
And that's not even surprising; this just reflects the fact that in Rust, if we own a type, we can always move it to a different location---and hence the invariant must not depend on the location.
However, if we go back to our notion of Rust types that I laid out at the beginning of this post, we notice that it is *impossible* to refer to the "address of `self.data`" in `T.own`!
And that's not even surprising; this just reflects the fact that in Rust, if we own a type, we can always move it to a different location---and hence the invariant must not depend on the location.
Notice that this state talks about a *pointer* being valid, in contrast to `T.own` which talks about a *sequence of bytes*.
This gives us the expressivity we need to talk about immovable data:
Notice that this state talks about a *pointer* being valid, in contrast to `T.own` which talks about a *sequence of bytes*.
This gives us the expressivity we need to talk about immovable data:
-`SelfReferential.pin(ptr)` says that `ptr` points to some memory we own, and that memory stores some pair `(data, self_ref)`.
-(In terms of memory layout, `SelfReferential` is the same as a pair of `i32` and `Option<ptr::NonNull<i32>>`.)
-Moreover, if `self_ref` is set to `Some(data_ptr)`, then `data_ptr` is the address of the first field of the pair:
+`SelfReferential.pin(ptr)` says that `ptr` points to some memory we own, and that memory stores some pair `(data, self_ref)`, and `self_ref` is either NULL or the address of the first field, `data`, at offset `0`:
-The most important part of this is the last line, saying that if `data_ptr` is a `Some`, it actually points to the first field (at offset `0`).
-(I am of course glossing over plenty of details here, like handling of padding, but those details are not relevant right now.
+(In terms of memory layout, `SelfReferential` is the same as a pair of `i32` and `*const i32`.
+I am of course glossing over plenty of details here, but those details are not relevant right now.
Moreover, `SelfReferential` also has an owned and a shared typestate, but nothing interesting happens there.)
With this choice, it is easy to justify that `read_ref` is safe to execute: When the function begins, we can rely on `SelfReferential.pin(self)`.
Moreover, `SelfReferential` also has an owned and a shared typestate, but nothing interesting happens there.)
With this choice, it is easy to justify that `read_ref` is safe to execute: When the function begins, we can rely on `SelfReferential.pin(self)`.
-If the closure in `self_ref.map` runs, we are in the `Some` case of the `match` so the deref of the pointer obtained from `self_ref` is fine.
+If we enter the `else` branch, we know `self_ref` is not NULL, hence it must be `ptr.offset(0)`.
+As a consequence, the deref of `self_ref` is fine.
Again this is an instance of using a higher-level view of memory than a raw list of bytes.
For example, we might want to say that `ptr` points to `42` of type `i32` by saying `ptr.points_to_owned(42i32)`, without worrying about how to turn that value into a sequence of bytes.
It turns out that we can define `points_to_owned` in terms of a lower-level `points_to_owned_bytes` that operates on `List<Byte>` as follows:
Again this is an instance of using a higher-level view of memory than a raw list of bytes.
For example, we might want to say that `ptr` points to `42` of type `i32` by saying `ptr.points_to_owned(42i32)`, without worrying about how to turn that value into a sequence of bytes.
It turns out that we can define `points_to_owned` in terms of a lower-level `points_to_owned_bytes` that operates on `List<Byte>` as follows:
On the other hand, for types like `i32`, their pinned typestate invariant `i32.pin(ptr)` will only care about the memory that `ptr` points to and not about the actual value of `ptr`, so they satisfy the `Unpin` axiom.
With this definition at hand, it should be clear that if we assume `T: Unpin`, then `&'a mut T` and `Pin<'a, T>` are equivalent types, and so are `Box<T>` and `PinBox<T>`.
On the other hand, for types like `i32`, their pinned typestate invariant `i32.pin(ptr)` will only care about the memory that `ptr` points to and not about the actual value of `ptr`, so they satisfy the `Unpin` axiom.
With this definition at hand, it should be clear that if we assume `T: Unpin`, then `&'a mut T` and `Pin<'a, T>` are equivalent types, and so are `Box<T>` and `PinBox<T>`.
-We have seen how the new `Pin` type can be used to give safe APIs to types like `SelfReferential`, and how we can (semi-)formally argue for the correctness of `SelfReferential` and the methods on `Pin` and `PinBox`.
+We have seen how the new `Pin` type can be used to give safe APIs to types like `SelfReferential` (which, previously, was not possible), and how we can (semi-)formally argue for the correctness of `SelfReferential` and the methods on `Pin` and `PinBox`.
I hope I was able to shed some light both on how pinning is useful, and how we can reason about safety of a typed API in general.
Next time, we are going to look at an extension to the pinning API proposed by @cramertj which guarantees that `drop` will be called under some circumstances, and how that is useful for intrusive collections.
I hope I was able to shed some light both on how pinning is useful, and how we can reason about safety of a typed API in general.
Next time, we are going to look at an extension to the pinning API proposed by @cramertj which guarantees that `drop` will be called under some circumstances, and how that is useful for intrusive collections.
projects / web.git / blobdiff