4b3e773f594e8027dec661a6b9a3e907cc203e7d
[rust-101.git] / src / part16.rs
1 // Rust-101, Part 16: Unsafe Rust, Drop
2 // ====================================
3
4 use std::ptr;
5 use std::mem;
6 use std::marker::PhantomData;
7
8 //@ As we saw, the rules Rust imposes to ensure memory safety can get us pretty far. A large amount
9 //@ of programming patterns can be written within safe Rust, and, more importantly, library code
10 //@ like iterators or threads can make use of the type system to ensure some level of correctness
11 //@ beyond basic memory safety.
12 //@ 
13 //@ However, there will still be programs that one cannot write in accordance with the borrow
14 //@ checker. And there will be cases where it may be possible to satisfy the compiler, but only at
15 //@ the cost of some run-time overhead, as we saw with `RefCell` - overhead which may not be
16 //@ acceptable. In such a situation, it is possible to use *unsafe* Rust: That's a part of the
17 //@ language that is *known* to open the gate to invalid pointer access and all other sorts of
18 //@ memory safety. Of course, `unsafe` also means "Here Be Dragons": You are on your own now. <br/>
19 //@ The goal in these cases is to confine unsafety to the local module. Types like `Rc` and `Vec`
20 //@ are implemented using unsafe Rust, but *using* them as we did is (believed to be) perfectly
21 //@ safe.
22 //@ 
23 //@ ## Unsafe Code
24 //@ As an example, let us write a doubly-linked list. Clearly, such a data-structure involves
25 //@ aliasing and mutation: Every node in the list is pointed to by its left and right neighbor, but
26 //@ still we will want to modify the nodes. We could now try some clever combination of `Rc` and
27 //@ `RefCell`, but this would end up being quite annoying - and it would incur some overhead. For a
28 //@ low-level data-structure like a doubly-linked list, it makes sense to implement an efficient
29 //@ version once, that is unsafe internally, but that can be used without any risk by safe client
30 //@ code.
31 //@ As usually, we start by defining the types. Everything is parameterized by the type `T` of the
32 //@ data stored in the list.
33 // A node of the list consists of the data, and two node pointers for the predecessor and successor.
34 struct Node<T> {
35     next: NodePtr<T>,
36     prev: NodePtr<T>,
37     data: T,
38 }
39 // A node pointer is a *mutable raw pointer* to a node.
40 //@ Raw pointers (`*mut T` and `*const T`) are the Rust equivalent of pointers in C. Unlike
41 //@ references, they do not come with any guarantees: Raw pointers can be null, or they can point
42 //@ to garbage. They don't have a lifetime, either.
43 type NodePtr<T> = *mut Node<T>;
44
45 // The linked list itself stores pointers to the first and the last node. In addition, we tell Rust
46 // that this type will own data of type `T`.
47 //@ The type `PhantomData<T>` does not actually store anything in memory - it has size zero.
48 //@ However, logically, Rust will consider a `T` to be present. In this case, Rust knows that data
49 //@ of type `T` may be dropped whenever a `LinkedList<T>` is dropped. Dropping has a lot of subtle
50 //@ checks to it, making sure that things can't go wrong. For this to work, Rust needs to know
51 //@ which types could potentially be dropped. In safe Rust, this can all be inferred automatically,
52 //@ but here, we just have a `*mut Node<T>`, and we need to tell Rust that we actually own such
53 //@ data and will drop it.
54 //@ (For more of the glory details, see
55 //@ [this RFC](https://github.com/rust-lang/rfcs/blob/master/text/0769-sound-generic-drop.md).)
56 pub struct LinkedList<T> {
57     first: NodePtr<T>,
58     last:  NodePtr<T>,
59     _marker: PhantomData<T>,
60 }
61
62 //@ Before we get to the actual linked-list methods, we write two short helper functions converting
63 //@ between mutable raw pointers, and boxed data. Both employ `mem::transmute`, which can convert
64 //@ anything to anything, by just re-interpreting the bytes.
65 //@ Clearly, that's an unsafe operation and must only be used with great care - or even better, not
66 //@ at all. Seriously. If at all possible, you should never use `transmute`. <br/>
67 //@ We are making the assumption here that a `Box` and a raw pointer have the same representation
68 //@ in memory. In the future, Rust will
69 //@ [provide](https://doc.rust-lang.org/beta/alloc/boxed/struct.Box.html#method.from_raw) such
70 //@ [operations](https://doc.rust-lang.org/beta/alloc/boxed/struct.Box.html#method.into_raw) in the
71 //@ standard library, but the exact API is still being fleshed out.
72
73 //@ We declare `raw_into_box` to be an `unsafe` function, telling Rust that calling this function
74 //@ is not generally safe. This grants us the unsafe powers for the body of the function: We can
75 //@ dereference raw pointers, and - most importantly - we can call unsafe functions. (The other
76 //@ unsafe powers won't be relevant here. Go read
77 //@ [The Rustonomicon](https://doc.rust-lang.org/nightly/nomicon/) if you want to learn all about
78 //@ this, but be warned - That Way Lies Madness.) <br/>
79 //@ Here, the caller will have to ensure that `r` is a valid pointer, and that nobody else has a
80 //@ pointer to this data.
81 unsafe fn raw_into_box<T>(r: *mut T) -> Box<T> {
82     mem::transmute(r)
83 }
84 //@ The case is slightly different for `box_into_raw`: Converting a `Box` to a raw pointer is
85 //@ always safe. It just drops some information. Hence we keep the function itself safe, and use an
86 //@ *unsafe block* within the function. This is an (unchecked) promise to the Rust compiler, saying
87 //@ that a safe invocation of `box_into_raw` cannot go wrong. We also have the unsafe powers in the
88 //@ unsafe block.
89 fn box_into_raw<T>(b: Box<T>) -> *mut T {
90     unsafe { mem::transmute(b) }
91 }
92
93 impl<T> LinkedList<T> {
94     // A new linked list just contains null pointers. `PhantomData` is how we construct any
95     // `PhantomData<T>`.
96     pub fn new() -> Self {
97         LinkedList { first: ptr::null_mut(), last: ptr::null_mut(), _marker: PhantomData }
98     }
99
100     // This function adds a new node to the end of the list.
101     pub fn push_back(&mut self, t: T) {
102         // Create the new node, and make it a raw pointer.
103         //@ Calling `box_into_raw` gives up ownership of the box, which is crucial: We don't want
104         //@ the memory that it points to to be deallocated!
105         let new = Box::new( Node { data: t, next: ptr::null_mut(), prev: self.last } );
106         let new = box_into_raw(new);
107         // Update other pointers to this node.
108         if self.last.is_null() {
109             debug_assert!(self.first.is_null());
110             // The list is currently empty, so we have to update the head pointer.
111             self.first = new;                                       /*@*/
112         } else {
113             debug_assert!(!self.first.is_null());
114             // We have to update the `next` pointer of the tail node.
115             //@ Since Rust does not know that a raw pointer actually points to anything,
116             //@ dereferencing such a pointer is an unsafe operation. So this unsafe block promises
117             //@ that the pointer will actually be valid.
118             unsafe { (*self.last).next = new; }                     /*@*/
119         }
120         // Make this the last node.
121         self.last = new;
122     }
123
124     // **Exercise 16.1**: Add some more operations to `LinkedList`: `pop_back`, `push_front` and
125     // `pop_front`. Add testcases for `push_back` and all of your functions. The `pop` functions
126     // should take `&mut self` and return `Option<T>`.
127
128     // Next, we are going to provide an iterator.
129     //@ This function just creates an instance of `IterMut`, the iterator type which does the actual
130     //@ work.
131     pub fn iter_mut(&mut self) -> IterMut<T> {
132         IterMut { next: self.first, _marker: PhantomData  }
133     }
134 }
135
136 //@ What does the iterator need to store? Strictly speaking, all it needs is the pointer to the
137 //@ next node that it is going to visit. However, how do we make sure that this pointer remains
138 //@ valid? We have to get this right ourselves, as we left the safe realms of borrowing and
139 //@ ownership. Remember that the key ingredient for iterator safety was to tie the lifetime of the
140 //@ iterator to the lifetime of the reference used for `iter_mut`. We will thus give `IterMut` two
141 //@ parameters: A type parameter specifying the type of the data, and a lifetime parameter
142 //@ specifying for how long the list was borrowed to the iterator.
143
144 //@ For Rust to accept the type, we have to add two more annotations. First of all, we have to
145 //@ ensure that the data in the list lives at least as long as the iterator: If you drop the `T:
146 //@ 'a`, Rust will tell you to add it back. And secondly, Rust will complain if `'a` is not
147 //@ actually used in the struct. It doesn't know what it is supposed to do with that lifetime. So
148 //@ we use `PhantomData` again to tell it that in terms of ownership, this type actually (uniquely)
149 //@ borrows a linked list. This has no operational effect, but it means that Rust can deduce the
150 //@ intent we had when adding that seemingly useless lifetime parameter.
151 pub struct IterMut<'a, T> where T: 'a {
152     next: NodePtr<T>,
153     _marker: PhantomData<&'a mut LinkedList<T>>,
154 }
155
156 //@ When implementing `Iterator` for `IterMut`, the fact that we have the lifetime `'a` around
157 //@ immediately pays of: We would not even be able to write down the type `Item` without that
158 //@ lifetime.
159 impl<'a, T> Iterator for IterMut<'a, T> {
160     type Item = &'a mut T;
161
162     fn next(&mut self) -> Option<Self::Item> {
163         // The actual iteration is straight-forward: Once we reached a null pointer, we are done.
164         if self.next.is_null() {
165             None
166         } else {
167             // Otherwise, we can convert the next pointer to a reference, get a reference to the data
168             // and update the iterator.
169             let next = unsafe { &mut *self.next };
170             let ret = &mut next.data;
171             self.next = next.next;                                  /*@*/
172             Some(ret)                                               /*@*/
173         }
174     }
175 }
176
177 //@ In `next` above, we made crucial use of the assumption that `self.next` is either null or a
178 //@ valid pointer. This only works because if someone tries to delete elements from a list during
179 //@ iteration, we know that the borrow checker will catch them: If they call `next`, the lifetime
180 //@ `'a` we artificially added to the iterator has to still be active, which means the mutable
181 //@ reference passed to `iter_mut` is still active, which means nobody can delete anything from the
182 //@ list. In other words, we make use of the expressive type system of Rust, decorating our own
183 //@ unsafe implementation with just enough information so that Rust can check *uses* of the linked-
184 //@ list. If the type system were weaker, we could not write a linked-list like the above with a
185 //@ safe interface!
186
187 // **Exercise 16.2**: Add a method `iter` and a type `Iter` providing iteration for shared
188 // references. Add testcases for both kinds of iterators.
189
190 // ## `Drop`
191 //@ The linked list we wrote is already working quite nicely, but there is one problem: When the
192 //@ list is dropped, nobody bothers to deallocate the remaining nodes. Even worse, if `T` itself
193 //@ has a destructor that needs to clean up, it is not called for the element remaining in the
194 //@ list. We need to take care of that ourselves.
195
196 //@ In Rust, adding a destructor for a type is done by implementing the `Drop` trait. This is a
197 //@ very special trait. It can only be implemented for *nominal types*, i.e., you cannot implement
198 //@ `Drop` for `&mut T`. You also cannot restrict the type and lifetime parameters further than the
199 //@ type does - the `Drop` implementation has to apply to *all* instances of `LinkedList`.
200 impl<T> Drop for LinkedList<T> {
201     // The destructor itself is a method which takes `self` in mutably borrowed form. It cannot own
202     // `self`, because then the destructor of `self` would be called at the end of the function,
203     // resulting in endless recursion.
204     fn drop(&mut self) {
205         let mut cur_ptr = self.first;
206         while !cur_ptr.is_null() {
207             // In the destructor, we just iterate over the entire list, successively obtaining
208             // ownership (`Box`) of every node. When the box is dropped, it will call the destructor
209             // on `data` if necessary, and subsequently free the node on the heap.
210             //@ We call `drop` explicitly here just for documentation purposes.
211             let cur = unsafe { raw_into_box(cur_ptr) };
212             cur_ptr = cur.next;
213             drop(cur);
214         }
215     }
216 }
217
218 // ## The End
219
220 //@ Congratulations! You completed Rust-101. This was the last part of the course. I hope you
221 //@ enjoyed it. If you have feedback or want to contribute yourself, please head to the
222 //@ [Rust-101](https://www.ralfj.de/projects/rust-101/) website fur further information. The entire
223 //@ course is open-source (under [CC-BY-SA 4.0](https://creativecommons.org/licenses/by-sa/4.0/)).
224 //@ 
225 //@ If you want to do more, the examples you saw in this course provide lots of playground for
226 //@ coming up with your own little extensions here and there. The [index](main.html) contains some
227 //@ more links to additional resources you may find useful.
228 //@ With that, there's only one thing left to say: Happy Rust Hacking!
229
230 //@ [index](main.html) | [previous](part15.html) | [raw source](workspace/src/part16.rs) | next