Merge pull request #2 from wheals/master

[rust-101.git] / src / part16.rs

diff --git a/src/part16.rs b/src/part16.rs
index 5ae6a4824971b430984305301cd9c6732a03daee..90b687bb7438c668c9a11cc2d0de98bdc3f8173d 100644 (file)
--- a/src/part16.rs
+++ b/src/part16.rs
@@ -5,7 +5,7 @@ use std::ptr;
 use std::mem;
 use std::marker::PhantomData;
 
 use std::mem;
 use std::marker::PhantomData;
 

-//@ As we saw, the rules Rust imposes to ensure memory safety can get us pretty far. A surprising amount of programming patterns
+//@ As we saw, the rules Rust imposes to ensure memory safety can get us pretty far. A large amount of programming patterns

 //@ can be written within safe Rust, and, more importantly, library code like iterators or threads can make
 //@ use of the type system to ensure some level of correctness beyond basic memory safety.
 //@ 
 //@ can be written within safe Rust, and, more importantly, library code like iterators or threads can make
 //@ use of the type system to ensure some level of correctness beyond basic memory safety.
 //@ 


@@ -13,19 +13,16 @@ use std::marker::PhantomData;
 //@ will be cases where it may be possible to satisfy the compiler, but only at the cost of some run-time overhead,
 //@ as we saw with `RefCell` - overhead which may not be acceptable. In such a situation, it is possible to
 //@ use *unsafe* Rust: That's a part of the language that is *known* to open the gate to invalid pointer access
 //@ will be cases where it may be possible to satisfy the compiler, but only at the cost of some run-time overhead,
 //@ as we saw with `RefCell` - overhead which may not be acceptable. In such a situation, it is possible to
 //@ use *unsafe* Rust: That's a part of the language that is *known* to open the gate to invalid pointer access

-//@ and all other sorts of memory safety. It is typically disabled, guarded by the keyword `unsafe`. Of course,
-//@ `unsafe` also means "Here Be Dragons": You are on your own now.
-//@ 
+//@ and all other sorts of memory safety. Of course, `unsafe` also means "Here Be Dragons": You are on your own now. <br/>

 //@ The goal in these cases is to confine unsafety to the local module. Types like `Rc` and `Vec` are implemented
 //@ using unsafe Rust, but *using* them as we did is (believed to be) perfectly safe.
 //@ 
 //@ ## Unsafe Code
 //@ As an example, let us write a doubly-linked list. Clearly, such a data-structure involves aliasing and mutation:
 //@ The goal in these cases is to confine unsafety to the local module. Types like `Rc` and `Vec` are implemented
 //@ using unsafe Rust, but *using* them as we did is (believed to be) perfectly safe.
 //@ 
 //@ ## Unsafe Code
 //@ As an example, let us write a doubly-linked list. Clearly, such a data-structure involves aliasing and mutation:

-//@ Every node in the list is pointed to by its left and right neighbor, but still we will want to modify the nodes
-//@ (either to change the value at that place, or to insert/delete nodes). We could now try some clever combination of
-//@ `Rc` and `RefCell`, but this would end up being quite annoying - and it would incur some over-head. For a low-level
-//@ data-structure like a doubly-linked list, it makes sense to implement an efficient version *once*, that is unsafe
-//@ internally, but that can be used without any risk by safe client code.
+//@ Every node in the list is pointed to by its left and right neighbor, but still we will want to modify the nodes. We
+//@ could now try some clever combination of `Rc` and `RefCell`, but this would end up being quite annoying - and it would
+//@ incur some overhead. For a low-level data-structure like a doubly-linked list, it makes sense to implement an efficient
+//@ version once, that is unsafe internally, but that can be used without any risk by safe client code.

 
 //@ As usually, we start by defining the types. Everything is parameterized by the type `T` of the data stored in the list.
 // A node of the list consists of the data, and two node pointers for the predecessor and successor.
 
 //@ As usually, we start by defining the types. Everything is parameterized by the type `T` of the data stored in the list.
 // A node of the list consists of the data, and two node pointers for the predecessor and successor.


@@ -43,30 +40,34 @@ type NodePtr<T> = *mut Node<T>;
 // will own data of type `T`.
 //@ The type `PhantomData<T>` does not actually store anything in memory - it has size zero. However, logically,
 //@ Rust will consider a `T` to be present. In this case, Rust knows that data of type `T` may be dropped
 // will own data of type `T`.
 //@ The type `PhantomData<T>` does not actually store anything in memory - it has size zero. However, logically,
 //@ Rust will consider a `T` to be present. In this case, Rust knows that data of type `T` may be dropped

-//@ whenever a `LinkedList<T>` is dropped. The checks involving destructors are pretty subtle, so it's always
-//@ a good idea to provide such extra information. In safe Rust, this can all be done automatically, but here,
-//@ we just have a `*mut Node<T>`, which Rust does not consider as actually owning the data it points to.
+//@ whenever a `LinkedList<T>` is dropped. Dropping has a lot of subtle checks to it, making sure that things can't go
+//@ wrong. For this to work, Rust needs to know which types could potentially be dropped. In safe Rust, this can all be inferred
+//@ automatically, but here, we just have a `*mut Node<T>`, and we need to tell Rust that we actually own such data and will drop it.
+//@ (For more of the glory details, see [this RFC](https://github.com/rust-lang/rfcs/blob/master/text/0769-sound-generic-drop.md).)

 pub struct LinkedList<T> {
     first: NodePtr<T>,
     last:  NodePtr<T>,
     _marker: PhantomData<T>,
 }
 
 pub struct LinkedList<T> {
     first: NodePtr<T>,
     last:  NodePtr<T>,
     _marker: PhantomData<T>,
 }
 

-//@ Before we get to the actual linked-list methods, we write two short helper functions converting between
-//@ mutable raw pointers, and owned pointers (aka `Box`). Both employ `mem::transmute`, which is Rust's
-//@ `reinterpret_cast`: It can convert anything to anything, by just re-interpreting the bytes. Clearly,
-//@ that's an unsafe operation and must only be used with great care. If at all possible, its use should be avoided. <br/>
+//@ Before we get to the actual linked-list methods, we write two short helper functions converting between mutable raw pointers,
+//@ and boxed data. Both employ `mem::transmute`, which can convert anything to anything, by just re-interpreting the bytes.
+//@ Clearly, that's an unsafe operation and must only be used with great care - or even better, not at all. Seriously.
+//@ If at all possible, you should never use `transmute`. <br/>

 //@ We are making the assumption here that a `Box` and a raw pointer have the same representation in memory. In the future,
 //@ We are making the assumption here that a `Box` and a raw pointer have the same representation in memory. In the future,

-//@ Rust will [provide](http://doc.rust-lang.org/beta/alloc/boxed/struct.Box.html#method.from_raw) such [operations](http://doc.rust-lang.org/beta/alloc/boxed/struct.Box.html#method.into_raw) in the standard library, but the exact API is still being fleshed out.
+//@ Rust will [provide](https://doc.rust-lang.org/beta/alloc/boxed/struct.Box.html#method.from_raw) such [operations](https://doc.rust-lang.org/beta/alloc/boxed/struct.Box.html#method.into_raw) in the standard library, but the exact API is still being fleshed out.

 
 //@ We declare `raw_into_box` to be an `unsafe` function, telling Rust that calling this function is not generally safe.
 
 //@ We declare `raw_into_box` to be an `unsafe` function, telling Rust that calling this function is not generally safe.

-//@ The caller will have to ensure that `r` is a valid pointer, and that nobody else has a pointer to this data.
+//@ This grants us the unsafe powers for the body of the function: We can dereference raw pointers, and - most importantly - we
+//@ can call unsafe functions. (The other unsafe powers won't be relevant here. Go read [The Rustonomicon](https://doc.rust-lang.org/nightly/nomicon/)
+//@ if you want to learn all about this, but be warned - That Way Lies Madness.) <br/>
+//@ Here, the caller will have to ensure that `r` is a valid pointer, and that nobody else has a pointer to this data.

 unsafe fn raw_into_box<T>(r: *mut T) -> Box<T> {
     mem::transmute(r)
 }
 unsafe fn raw_into_box<T>(r: *mut T) -> Box<T> {
     mem::transmute(r)
 }

-//@ The case is slightly different for `box_into_raw`: Converting a `Box` to a raw pointer is always safe. I just drops some
-//@ information. Hence we keep the function itself safe, and use an *unsafe block* within the function. This is an (unchecked)
-//@ promise to the Rust compiler, saying that a safe invocation of `box_into_raw` cannot go wrong.
+//@ The case is slightly different for `box_into_raw`: Converting a `Box` to a raw pointer is always safe. It just drops some information.
+//@ Hence we keep the function itself safe, and use an *unsafe block* within the function. This is an (unchecked) promise to the Rust
+//@ compiler, saying that a safe invocation of `box_into_raw` cannot go wrong. We also have the unsafe powers in the unsafe block.

 fn box_into_raw<T>(b: Box<T>) -> *mut T {
     unsafe { mem::transmute(b) }
 }
 fn box_into_raw<T>(b: Box<T>) -> *mut T {
     unsafe { mem::transmute(b) }
 }


@@ -80,11 +81,10 @@ impl<T> LinkedList<T> {
     // This function adds a new node to the end of the list.
     pub fn push_back(&mut self, t: T) {
         // Create the new node, and make it a raw pointer.
     // This function adds a new node to the end of the list.
     pub fn push_back(&mut self, t: T) {
         // Create the new node, and make it a raw pointer.

-        //@ Calling `box_into_raw` gives up ownership of the box, which is crucial: We don't want the
-        //@ memory that it points to to be deallocated!
+        //@ Calling `box_into_raw` gives up ownership of the box, which is crucial: We don't want the memory that it points to to be deallocated!

         let new = Box::new( Node { data: t, next: ptr::null_mut(), prev: self.last } );
         let new = box_into_raw(new);
         let new = Box::new( Node { data: t, next: ptr::null_mut(), prev: self.last } );
         let new = box_into_raw(new);

-        // Update other points to this node.
+        // Update other pointers to this node.

         if self.last.is_null() {
             debug_assert!(self.first.is_null());
             // The list is currently empty, so we have to update the head pointer.
         if self.last.is_null() {
             debug_assert!(self.first.is_null());
             // The list is currently empty, so we have to update the head pointer.


@@ -106,7 +106,7 @@ impl<T> LinkedList<T> {
 
     // Next, we are going to provide an iterator.
     //@ This function just creates an instance of `IterMut`, the iterator type which does the actual work.
 
     // Next, we are going to provide an iterator.
     //@ This function just creates an instance of `IterMut`, the iterator type which does the actual work.

-    pub fn iter_mut(&self) -> IterMut<T> {
+    pub fn iter_mut(&mut self) -> IterMut<T> {

         IterMut { next: self.first, _marker: PhantomData  }
     }
 }
         IterMut { next: self.first, _marker: PhantomData  }
     }
 }


@@ -173,7 +173,7 @@ impl<'a, T> Iterator for IterMut<'a, T> {
 //@ of `LinkedList`.
 impl<T> Drop for LinkedList<T> {
     // The destructor itself is a method which takes `self` in mutably borrowed form. It cannot own `self`, because then
 //@ of `LinkedList`.
 impl<T> Drop for LinkedList<T> {
     // The destructor itself is a method which takes `self` in mutably borrowed form. It cannot own `self`, because then

-    // the destructor of `self` would be called at the end pf the function, resulting in endless recursion...
+    // the destructor of `self` would be called at the end of the function, resulting in endless recursion...

     fn drop(&mut self) {
         let mut cur_ptr = self.first;
         while !cur_ptr.is_null() {
     fn drop(&mut self) {
         let mut cur_ptr = self.first;
         while !cur_ptr.is_null() {


@@ -197,4 +197,4 @@ impl<T> Drop for LinkedList<T> {
 //@ extensions here and there. The [index](main.html) contains some more links to additional resources you may find useful. 
 //@ With that, there's only one thing left to say: Happy Rust Hacking!
 
 //@ extensions here and there. The [index](main.html) contains some more links to additional resources you may find useful. 
 //@ With that, there's only one thing left to say: Happy Rust Hacking!
 

-//@ [index](main.html) | [previous](part15.html) | next
+//@ [index](main.html) | [previous](part15.html) | [raw source](https://www.ralfj.de/git/rust-101.git/blob_plain/HEAD:/workspace/src/part16.rs) | next