ship generated workspace files for the benefit of non-Linux users
authorRalf Jung <post@ralfj.de>
Fri, 26 Jun 2015 17:55:59 +0000 (19:55 +0200)
committerRalf Jung <post@ralfj.de>
Fri, 26 Jun 2015 17:55:59 +0000 (19:55 +0200)
.gitignore
workspace/src/part00.rs [new file with mode: 0644]
workspace/src/part01.rs [new file with mode: 0644]
workspace/src/part02.rs [new file with mode: 0644]
workspace/src/part03.rs [new file with mode: 0644]
workspace/src/part04.rs [new file with mode: 0644]
workspace/src/part05.rs [new file with mode: 0644]
workspace/src/part06.rs [new file with mode: 0644]
workspace/src/part07.rs [new file with mode: 0644]
workspace/src/part08.rs [new file with mode: 0644]
workspace/src/part09.rs [new file with mode: 0644]

index aded1db4b281497738183d2af3878f69c21e8c44..ff9a79d976ca54490f3e34936826bf0521830098 100644 (file)
@@ -1,4 +1,3 @@
 target/
 sync-docs
 .tmp/
 target/
 sync-docs
 .tmp/
-workspace/src/part*.rs
diff --git a/workspace/src/part00.rs b/workspace/src/part00.rs
new file mode 100644 (file)
index 0000000..4f7b403
--- /dev/null
@@ -0,0 +1,89 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 00: Algebraic datatypes
+// ======================================
+
+// As our first piece of Rust code, we want to write a function that computes the
+// minimum of a list.
+
+
+// An `enum` for "a number or nothing" could look as follows:
+enum NumberOrNothing {
+    Number(i32),
+    Nothing
+}
+
+// Observe how in Rust, the return type comes *after* the arguments.
+fn vec_min(vec: Vec<i32>) -> NumberOrNothing {
+    let mut min = NumberOrNothing::Nothing;
+
+    // Now we want to *iterate* over the list. Rust has some nice syntax for
+    // iterators:
+    for el in vec {
+        // So `el` is al element of the list. We need to update `min` accordingly, but how do we get the current
+        // number in there? This is what pattern matching can do:
+        match min {
+            // In this case (*arm*) of the `match`, `min` is currently nothing, so let's just make it the number `el`.
+            NumberOrNothing::Nothing => {
+                unimplemented!()
+            },
+            // In this arm, `min` is currently the number `n`, so let's compute the new minimum and store it. We will write
+            // the function `min_i32` just after we completed this one.
+            NumberOrNothing::Number(n) => {
+                unimplemented!()
+            }
+        }
+    }
+    // Finally, we return the result of the computation.
+    return min;
+}
+
+// Now that we reduced the problem to computing the minimum of two integers, let's do that.
+fn min_i32(a: i32, b: i32) -> i32 {
+    if a < b {
+        unimplemented!()
+    } else {
+        unimplemented!()
+    }
+}
+
+// Phew. We wrote our first Rust function! But all this `NumberOrNothing::` is getting kind of
+// ugly. Can't we do that nicer?
+
+// Indeed, we can: The following line tells Rust to take
+// the constructors of `NumberOrNothing` into the local namespace.
+// Try moving that above the function, and removing all the occurrences `NumberOrNothing::`.
+use self::NumberOrNothing::{Number,Nothing};
+
+// To call this function, we now just need a list. Of course, ultimately we want to ask the user for
+// a list of numbers, but for now, let's just hard-code something.
+
+// `vec!` is a *macro* (as you can tell from the `!`) that constructs a constant `Vec<_>` with the given
+// elements.
+fn read_vec() -> Vec<i32> {
+    vec![18,5,7,1,9,27]
+}
+
+// Finally, let's call our functions and run the code!
+// But, wait, we would like to actually see something, so we need to print the result.
+// Of course Rust can print numbers, but after calling `vec_min`, we have a `NumberOrNothing`.
+// So let's write a small helper function that prints such values.
+
+fn print_number_or_nothing(n: NumberOrNothing) {
+    match n {
+        Nothing => println!("The number is: <nothing>"),
+        Number(n) => println!("The number is: {}", n),
+    };
+}
+
+// Putting it all together:
+pub fn main() {
+    let vec = read_vec();
+    let min = vec_min(vec);
+    print_number_or_nothing(min);
+}
+
+// Now try `cargo run` on the console to run above code.
+
+
+// [index](main.html) | previous | [next](part01.html)
diff --git a/workspace/src/part01.rs b/workspace/src/part01.rs
new file mode 100644 (file)
index 0000000..da94915
--- /dev/null
@@ -0,0 +1,103 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 01: Expressions, Inherent methods
+// ================================================
+
+// Even though our code from the first part works, we can still learn a
+// lot by making it prettier. To understand how, it is important to
+// understand that Rust is an "expression-based" language. This means that most of the
+// terms you write down are not just *statements* (executing code), but *expressions*
+// (returning a value). This applies even to the body of entire functions!
+
+// ## Expression-based programming
+// For example, consider `sqr`:
+fn sqr(i: i32) -> i32 { i * i }
+// Between the curly braces, we are giving the *expression* that computes the return value.
+// So we can just write `i * i`, the expression that returns the square if `i`!
+// This is very close to how mathematicians write down functions (but with more types).
+
+// Conditionals are also just expressions. You can compare this to the ternary `? :` operator
+// from languages like C.
+fn abs(i: i32) -> i32 { if i >= 0 { i } else { -i } }
+
+// And the same applies to case distinction with `match`: Every `arm` of the match
+// gives the expression that is returned in the respective case.
+// (We repeat the definition from the previous part here.)
+enum NumberOrNothing {
+    Number(i32),
+    Nothing
+}
+use self::NumberOrNothing::{Number,Nothing};
+fn number_or_default(n: NumberOrNothing, default: i32) -> i32 {
+    match n {
+        Nothing => default,
+        Number(n) => n,
+    }
+}
+
+// Let us now refactor `vec_min`.
+fn vec_min(v: Vec<i32>) -> NumberOrNothing {
+    // Remember that helper function `min_i32`? Rust allows us to define such helper functions *inside* other
+    // functions. This is just a matter of namespacing, the inner function has no access to the data of the outer
+    // one. Still, being able to nicely group functions can be very useful.
+    fn min_i32(a: i32, b: i32) -> i32 {
+        if a < b { a } else { b }
+    }
+
+    let mut min = Nothing;
+    for e in v {
+        // Notice that all we do here is compute a new value for `min`, and that it will always end
+        // up being a `Number` rather than `Nothing`. In Rust, the structure of the code
+        // can express this uniformity.
+        min = Number(match min {
+            Nothing => e,
+            Number(n) => min_i32(n, e)
+        });
+    }
+    // The `return` keyword exists in Rust, but it is rarely used. Instead, we typically
+    // make use of the fact that the entire function body is an expression, so we can just
+    // write down the desired return value.
+    min
+}
+
+// Now that's already much shorter! Make sure you can go over the code above and actually understand
+// every step of what's going on.
+
+// ## Inherent implementations
+// So much for `vec_min`. Let us now reconsider `print_number_or_nothing`. That function
+// really belongs pretty close to the type `NumberOrNothing`. In C++ or Java, you would
+// probably make it a method of the type. In Rust, we can achieve something very similar
+// by providing an *inherent implementation*.
+impl NumberOrNothing {
+    fn print(self) {
+        match self {
+            Nothing => println!("The number is: <nothing>"),
+            Number(n) => println!("The number is: {}", n),
+        };
+    }
+}
+// So, what just happened? Rust separates code from data, so the definition of the
+// methods on an `enum` (and also on `struct`, which we will learn about later)
+// is independent of the definition of the type. `self` is like `this` in other
+// languages, and its type is always implicit. So `print` is now a method that
+// takes as first argument a `NumberOrNothing`, just like `print_number_or_nothing`.
+// 
+// Try making `number_or_default` from above an inherent method as well!
+
+// With our refactored functions and methods, `main` now looks as follows:
+fn read_vec() -> Vec<i32> {
+    vec![18,5,7,2,9,27]
+}
+pub fn main() {
+    let vec = read_vec();
+    let min = vec_min(vec);
+    min.print();
+}
+// You will have to replace `part00` by `part01` in the `main` function in
+// `main.rs` to run this code.
+
+// **Exercise 01.1**: Write a funtion `vec_sum` that computes the sum of all values of a `Vec<i32>`.
+
+// **Exercise 01.2**: Write a function `vec_print` that takes a vector and prints all its elements.
+
+// [index](main.html) | [previous](part00.html) | [next](part02.html)
diff --git a/workspace/src/part02.rs b/workspace/src/part02.rs
new file mode 100644 (file)
index 0000000..908bb2a
--- /dev/null
@@ -0,0 +1,150 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 02: Generic types, Traits
+// ========================================
+
+// Let us for a moment reconsider the type `NumberOrNothing`. Isn't it a bit annoying that we
+// had to hard-code the type `i32` in there? What if tomorrow, we want a `CharOrNothing`, and
+// later a `FloatOrNothing`? Certainly we don't want to re-write the type and all its inherent methods.
+
+// ## Generic datatypes
+
+// The solution to this is called *generics* or *polymorphism* (the latter is Greek,
+// meaning "many shapes"). You may know something similar from C++ (where it's called
+// *templates*) or Java, or one of the many functional languages. So here, we define
+// a generic type `SomethingOrNothing`.
+pub enum SomethingOrNothing<T>  {
+    Something(T),
+    Nothing,
+}
+// Instead of writing out all the variants, we can also just import them all at once.
+pub use self::SomethingOrNothing::*;
+// What this does is to define an entire family of types: We can now write
+// `SomethingOrNothing<i32>` to get back our `NumberOrNothing`.
+type NumberOrNothing = SomethingOrNothing<i32>;
+// However, we can also write `SomethingOrNothing<bool>` or even `SomethingOrNothing<SomethingOrNothing<i32>>`.
+// In fact, such a type is so useful that it is already present in the standard library: It's called an
+// *option type*, written `Option<T>`. Go check out its [documentation](http://doc.rust-lang.org/stable/std/option/index.html)!
+// (And don't worry, there's indeed lots of material mentioned there that we did not cover yet.)
+
+// ## Generic `impl`, Static functions
+// The types are so similar, that we can provide a generic function to construct a `SomethingOrNothing<T>`
+// from an `Option<T>`, and vice versa.
+// **Exercise 02.1**: Implement such functions! I provided a skeleton of the solution. Here,
+// `unimplemented!` is another macro. This one terminates execution saying that something has not yet
+// been implemented.
+// 
+// Notice the syntax for giving generic implementations to generic types: Think of the first `<T>` 
+// as *declaring* a type variable ("I am doing something for all types `T`"), and the second `<T>` as
+// *using* that variable ("The thing I do, is implement `SomethingOrNothing<T>`").
+//
+// Inside an `impl`, `Self` refers to the type we are implementing things for. Here, it is
+// an alias for `SomethingOrNothing<T>`.
+// Remember that `self` is the `this` of Rust, and implicitly has type `Self`.
+impl<T> SomethingOrNothing<T> {
+    fn new(o: Option<T>) -> Self {
+        unimplemented!()
+    }
+
+    fn to_option(self) -> Option<T> {
+        unimplemented!()
+    }
+}
+// Observe how `new` does *not* have a `self` parameter. This corresponds to a `static` method
+// in Java or C++. In fact, `new` is the Rust convention for defining constructors: They are
+// nothing special, just static functions returning `Self`.
+// 
+// You can call static functions, and in particular constructors, as demonstrated in `call_constructor`.
+fn call_constructor(x: i32) -> SomethingOrNothing<i32> {
+    SomethingOrNothing::new(Some(x))
+}
+
+// ## Traits
+// Now that we have a generic `SomethingOrNothing`, wouldn't it be nice to also gave a generic
+// `vec_min`? Of course, we can't take the minimum of a vector of *any* type. It has to be a type
+// supporting a `min` operation. Rust calls such properties that we may demand of types *traits*.
+
+// So, as a first step towards a generic `vec_min`, we define a `Minimum` trait.
+// For now, just ignore the `Copy`, we will come back to this point later.
+// A `trait` is a lot like interfaces in Java: You define a bunch of functions
+// you want to have implemented, and their argument and return types.<br/>
+// The function `min` takes to arguments of the same type, but I made the
+// first argument the special `self` argument. I could, alternatively, have
+// made `min` a static function as follows: `fn min(a: Self, b: Self) -> Self`.
+// However, in Rust one typically prefers methods over static function wherever possible.
+pub trait Minimum : Copy {
+    fn min(self, b: Self) -> Self;
+}
+
+// Next, we write `vec_min` as a generic function over a type `T` that we demand to satisfy the `Minimum` trait.
+// This requirement is called a *trait bound*.
+// The only difference to the version from the previous part is that we call `e.min(n)` instead
+// of `std::cmp::min(n, e)`. Rust automatically figures out that `n` is of type `T`, which implements
+// the `Minimum` trait, and hence we can call that function.
+// 
+// There is a crucial difference to templates in C++: We actually have to declare which traits
+// we want the type to satisfy. If we left away the `Minimum`, Rust would have complained that
+// we cannot call `min`. Just try it!<br/>
+// This is in strong contrast to C++, where the compiler only checks such details when the
+// function is actually used.
+pub fn vec_min<T: Minimum>(v: Vec<T>) -> SomethingOrNothing<T> {
+    let mut min = Nothing;
+    for e in v {
+        min = Something(match min {
+            Nothing => e,
+            Something(n) => e.min(n)
+        });
+    }
+    min
+}
+// Before going on, take a moment to ponder the flexibility of Rust's take on abstraction:
+// We just defined our own, custom trait (interface), and then implemented that trait
+// *for an existing type*. With the hierarchical approach of, e.g., C++ or Java,
+// that's not possible: We cannot make an existing type suddenly also inherit from our abstract base class.
+// 
+// In case you are worried about performance, note that Rust performs *monomorphisation*
+// of generic functions: When you call `vec_min` with `T` being `i32`, Rust essentially goes
+// ahead and creates a copy of the function for this particular type, filling in all the blanks.
+// In this case, the call to `T::min` will become a call to our implementation *statically*. There is
+// no dynamic dispatch, like there would be for Java interface methods or C++ `virtual` methods.
+// This behavior is similar to C++ templates. The optimizer (Rust is using LLVM) then has all the
+// information it could want to, e.g., inline function calls.
+
+// ## Trait implementations
+// To make the function usable with a `Vec<i32>`, we implement the `Minimum` trait for `i32`.
+impl Minimum for i32 {
+    fn min(self, b: Self) -> Self {
+        if self < b { self } else { b }
+    }
+}
+
+// We again provide a `print` function. This also shows that we can have multiple `impl` blocks
+// for the same type (remember that `NumberOrNothing` is just a type alias for `SomethingOrNothing<i32>`),
+// and we can provide some methods only for certain instances of a generic type.
+impl NumberOrNothing {
+    pub fn print(self) {
+        match self {
+            Nothing => println!("The number is: <nothing>"),
+            Something(n) => println!("The number is: {}", n),
+        };
+    }
+}
+
+// Now we are again ready to run our code. Remember to change `main.rs` appropriately.
+// Rust figures out automatically that we want the `T` of `vec_min` to be `i32`, and
+// that `i32` implements `Minimum` and hence all is good.
+fn read_vec() -> Vec<i32> {
+    vec![18,5,7,3,9,27]
+}
+pub fn main() {
+    let vec = read_vec();
+    let min = vec_min(vec);
+    min.print();
+}
+
+// If this printed `3`, then you generic `vec_min` is working! So get ready for the next part.
+
+// **Exercise 02.2**: Change your program such that it computes the minimum of a `Vec<f32>` (where `f32` is the type
+// of 32-bit floating-point numbers). You should not change `vec_min` in any way, obviously!
+
+// [index](main.html) | [previous](part01.html) | [next](part03.html)
diff --git a/workspace/src/part03.rs b/workspace/src/part03.rs
new file mode 100644 (file)
index 0000000..7d022e8
--- /dev/null
@@ -0,0 +1,116 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 03: Input
+// ========================
+
+// In part 00, I promised that we would eventually replace `read_vec` by a function
+// that actually asks the user to enter a bunch of numbers. Unfortunately,
+// I/O is a complicated topic, so the code to do that is not exactly pretty - but well,
+// let's get that behind us.
+
+// I/O is provided by the module `std::io`, so we first have import that with `use`.
+// We also import the I/O *prelude*, which brings a bunch of commonly used I/O stuff
+// directly available.
+use std::io::prelude::*;
+use std::io;
+
+// Let's now go over this function line-by-line. First, we call the constructor of `Vec`
+// to create an empty vector. As mentioned in the previous part, `new` here is just
+// a static function with no special treatment. While it is possible to call `new`
+// for a particular type (`Vec::<i32>::new()`), the common way to make sure we
+// get the right type is to annotate a type at the *variable*. It is this variable
+// that we interact with for the rest of the function, so having its type available
+// (and visible!) is much more useful. Without knowing the return type of `Vec::new`,
+// specifying its type parameter doesn't tell us all that much.
+fn read_vec() -> Vec<i32> {
+    let mut vec: Vec<i32> = Vec::<i32>::new();
+    // The central handle to the standard input is made available by `io::stdin()`.
+    let stdin = io::stdin();
+    println!("Enter a list of numbers, one per line. End with Ctrl-D.");
+    // We would now like to iterate over standard input line-by-line. We can use a `for` loop
+    // for that, but there is a catch: What happens if there is some other piece of code running
+    // concurrently, that also reads from standard input? The result would be a mess. Hence
+    // Rust requires us to `lock()` standard input if we want to perform large operations on
+    // it. (See [the documentation](http://doc.rust-lang.org/stable/std/io/struct.Stdin.html) for more
+    // details.) 
+    for line in stdin.lock().lines() {
+        // Rust's type for (dynamic, growable) strings is `String`. However, our variable `line`
+        // here is not yet of that type. The problem with I/O is that it can always go wrong, so
+        // `line` has type `io::Result<String>`. This is a lot like `Option<String>` ("a `String` or
+        // nothing"), but in the case of "nothing", there is additional information about the error.
+        // Again, I recommend to check [the documentation](http://doc.rust-lang.org/stable/std/io/type.Result.html).
+        // You will see that `io::Result` is actually just an alias for `Result`, so click on that to obtain
+        // the list of all constructors and methods of the type.
+
+        // We will be lazy here and just assume that nothing goes wrong: `unwrap()` returns the `String` if there is one,
+        // and panics the program otherwise. Since a `Result` carries some details about the error that occurred,
+        // there will be a somewhat reasonable error message. Still, you would not want a user to see such
+        // an error, so in a "real" program, we would have to do proper error handling.
+        // Can you find the documentation of `Result::unwrap()`?
+        // 
+        // I chose the same name (`line`) for the new variable to ensure that I will never, accidentally,
+        // access the "old" `line` again.
+        let line = line.unwrap();
+        // Now that we have our `String`, we want to make it an `i32`. `parse` is a method on `String` that
+        // can convert a string to anything. Try finding it's documentation!
+
+        // In this case, Rust *could* figure out automatically that we need an `i32` (because of the return type
+        // of the function), but that's a bit too much magic for my taste. We are being more explicit here:
+        // `parse::<i32>` is `parse` with its generic type set to `i32`.
+        match line.parse::<i32>() {
+            // `parse` returns again a `Result`, and this time we use a `match` to handle errors (like, the user entering
+            // something that is not a number).
+            // This is a common pattern in Rust: Operations that could go wrong will return `Option` or `Result`.
+            // The only way to get to the value we are interested in is through pattern matching (and through helper functions
+            // like `unwrap()`). If we call a function that returns a `Result`, and throw the return value away,
+            // the compiler will emit a warning. It is hence impossible for us to *forget* handling an error,
+            // or to accidentally use a value that doesn't make any sense because there was an error producing it.
+            Ok(num) => vec.push(num),
+            // We don't care about the particular error, so we ignore it with a `_`.
+            Err(_) => println!("What did I say about numbers?"),
+        }
+    }
+
+    vec
+}
+
+// So much for `read_vec`. If there are any questions left, the documentation of the respective function
+// should be very helpful. Try finding the one for `Vec::push`. I will not always provide the links,
+// as the documentation is quite easy to navigate and you should get used to that.
+
+// For the rest of the code, we just re-use part 02 by importing it with `use`.
+// I already sneaked a bunch of `pub` in part 02 to make this possible: Only
+// items declared public can be imported elsewhere.
+use part02::{SomethingOrNothing,Something,Nothing,vec_min};
+
+// If you update your `main.rs` to use part 03, `cargo run` should now ask you for some numbers,
+// and tell you the minimum. Neat, isn't it?
+pub fn main() {
+    let vec = read_vec();
+    let min = vec_min(vec);
+    min.print();
+}
+
+// **Exercise 03.1**: Define a trait `Print` to write a generic version of `SomethingOrNothing::print`.
+// Implement that trait for `i32`, and change the code above to use it.
+// I will again provide a skeleton for this solution. It also shows how to attach bounds to generic
+// implementations (just compare it to the `impl` block from the previous exercise).
+// You can read this as "For all types `T` satisfying the `Print` trait, I provide an implementation
+// for `SomethingOrNothing<T>`".
+// 
+// Notice that I called the function on `SomethingOrNothing` `print2` to disambiguate from the `print` defined previously.
+// 
+// *Hint*: There is a macro `print!` for printing without appending a newline.
+trait Print {
+    /* Add things here */
+}
+impl<T: Print> SomethingOrNothing<T> {
+    fn print2(self) {
+        unimplemented!()
+    }
+}
+
+// **Exercise 03.2**: Building on exercise 02.2, implement all the things you need on `f32` to make your
+// program work with floating-point numbers.
+
+// [index](main.html) | [previous](part02.html) | [next](part04.html)
diff --git a/workspace/src/part04.rs b/workspace/src/part04.rs
new file mode 100644 (file)
index 0000000..894ce24
--- /dev/null
@@ -0,0 +1,144 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 04: Ownership, Borrowing
+// =======================================
+
+// Rust aims to be a "safe systems language". As a systems language, of course it
+// provides *references* (or *pointers*). But as a safe language, it has to
+// prevent bugs like this C++ snippet.
+/*
+  void foo(std::vector<int> v) {
+      int *first = &v[0];
+      v.push_back(42);
+      *first = 1337; // This is bad!
+  }
+*/
+// What's going wrong here? `first` is a pointer into the vector `v`. The operation `push_back`
+// may re-allocate the storage for the vector, in case the old buffer was full. If that happens,
+// `first` is now a dangling pointer, and accessing it can crash the program (or worse).
+// 
+// It turns out that only the combination of two circumstances can lead to such a bug:
+// *aliasing* and *mutation*. In the code above, we have `first` and the buffer of `v`
+// being aliases, and when `push_back` is called, the latter is used to perform a mutation.
+// Therefore, the central principle of the Rust typesystem is to *rule out mutation in the presence
+// of aliasing*. The core tool to achieve that is the notion of *ownership*.
+
+// ## Ownership
+// What does that mean in practice? Consider the following example.
+fn work_on_vector(v: Vec<i32>) { /* do something */ }
+fn ownership_demo() {
+    let v = vec![1,2,3,4];
+    work_on_vector(v);
+    /* println!("The first element is: {}", v[0]); */
+}
+// Rust attaches additional meaning to the argument of `work_on_vector`: The function can assume
+// that it entirely *owns* `v`, and hence can do anything with it. When `work_on_vector` ends,
+// nobody needs `v` anymore, so it will be deleted (including its buffer on the heap).
+// Passing a `Vec<i32>` to `work_on_vector` is considered *transfer of ownership*: Someone used
+// to own that vector, but now he gave it on to `take` and has no business with it anymore.
+// 
+// If you give a book to your friend, you cannot just come to his place next day and get the book!
+// It's no longer yours. Rust makes sure you don't break this rule. Try enabling the commented
+// line in `ownership_demo`. Rust will tell you that `v` has been *moved*, which is to say that ownership
+// has been transferred somewhere else. In this particular case, the buffer storing the data
+// does not even exist anymore, so we are lucky that Rust caught this problem!
+// Essentially, ownership rules out aliasing, hence making the kind of problem discussed above
+// impossible.
+
+// ## Shared borrowing
+// If you go back to our example with `vec_min`, and try to call that function twice, you will
+// get the same error. That's because `vec_min` demands that the caller transfers ownership of the
+// vector. Hence, when `vec_min` finishes, the entire vector is deleted. That's of course not what
+// we wanted! Can't we somehow give `vec_min` access to the vector, while retaining ownership of it?
+// 
+// Rust calls this *borrowing* the vector, and it works a bit like borrowing does in the real world:
+// If you borrow a book to your friend, your friend can have it and work on it (and you can't!)
+// as long as the book is still borrowed. Your friend could even borrow the book to someone else.
+// Eventually however, your friend has to give the book back to you, at which point you again
+// have full control.
+// 
+// Rust distinguishes between two kinds of borrows. First of all, there's the *shared* borrow.
+// This is where the book metaphor kind of breaks down... you can give a shared borrow of
+// *the same data* to lots of different people, who can all access the data. This of course
+// introduces aliasing, so in order to live up to its promise of safety, Rust does not allow
+// mutation through a shared borrow.
+
+// So, let's re-write `vec_min` to work on a shared borrow of a vector, written `&Vec<i32>`.
+// I also took the liberty to convert the function from `SomethingOrNothing` to the standard
+// library type `Option`.
+fn vec_min(v: &Vec<i32>) -> Option<i32> {
+    use std::cmp;
+
+    let mut min = None;
+    for e in v {
+        // In the loop, `e` now has type `&i32`, so we have to dereference it to obtain an `i32`.
+        min = Some(match min {
+            None => *e,
+            Some(n) => cmp::min(n, *e)
+        });
+    }
+    min
+}
+
+// Now that `vec_min` does not acquire ownership of the vector anymore, we can call it multiple times on the same vector and also do things like
+fn shared_borrow_demo() {
+    let v = vec![5,4,3,2,1];
+    let first = &v[0];
+    vec_min(&v);
+    vec_min(&v);
+    println!("The first element is: {}", *first);
+}
+// What's going on here? First, `&` is how you create a shared borrow to something. All borrows are created like
+// this - there is no way to have something like a  NULL pointer. This code creates three shared borrows to `v`:
+// The borrow for `first` begins in the 2nd line of the function and lasts all the way to the end. The other two
+// borrows, created for calling `vec_min`, only last for the duration of that respective call.
+// 
+// Technically, of course, borrows are pointers. Notice that since `vec_min` only gets a shared
+// borrow, Rust knows that it cannot mutate `v` in any way. Hence the pointer into the buffer of `v`
+// that was created before calling `vec_min` remains valid.
+
+// ## Mutable borrowing
+// There is a second kind of borrow, a *mutable borrow*. As the name suggests, such a borrow permits
+// mutation, and hence has to prevent aliasing. There can only ever be one mutable borrow to a
+// particular piece of data.
+
+// As an example, consider a function which increments every element of a vector by 1.
+// The type `&mut Vec<i32>` is the type of mutable borrows of `vec<i32>`. Because the borrow is
+// mutable, we can change `e` in the loop.
+fn vec_inc(v: &mut Vec<i32>) {
+    for e in v {
+        *e += 1;
+    }
+}
+// Here's an example of calling `vec_inc`.
+fn mutable_borrow_demo() {
+    let mut v = vec![5,4,3,2,1];
+    /* let first = &v[0]; */
+    vec_inc(&mut v);
+    vec_inc(&mut v);
+    /* println!("The first element is: {}", *first); */
+}
+// `&mut` is the operator to create a mutable borrow. We have to mark `v` as mutable in order to create such a
+// borrow. Because the borrow passed to `vec_inc` only lasts as long as the function call, we can still call
+// `vec_inc` on the same vector twice: The durations of the two borrows do not overlap, so we never have more
+// than one mutable borrow. However, we can *not* create a shared borrow that spans a call to `vec_inc`. Just try
+// enabling the commented-out lines, and watch Rust complain. This is because `vec_inc` could mutate
+// the vector structurally (i.e., it could add or remove elements), and hence the pointer `first`
+// could become invalid. In other words, Rust keeps us safe from bugs like the one in the C++ snipped above.
+// 
+// Above, I said that having a mutable borrow excludes aliasing. But if you look at the code above carefully,
+// you may say: "Wait! Don't the `v` in `mutable_borrow_demo` and the `v` in `vec_inc` alias?" And you are right,
+// they do. However, the `v` in `mutable_borrow_demo` is not actually usable, it is not *active*: As long as there is an
+// outstanding borrow, Rust will not allow you to do anything with `v`.
+
+// ## Summary
+// The ownership and borrowing system of Rust enforces the following three rules:
+// 
+// * There is always exactly one owner of a piece of data
+// * If there is an active mutable borrow, then nobody else can have active access to the data
+// * If there is an active shared borrow, then every other active access to the data is also a shared borrow
+// 
+// As it turns out, combined with the abstraction facilities of Rust, this is a very powerful mechanism
+// to tackle many problems beyond basic memory safety. You will see some examples for this soon.
+
+// [index](main.html) | [previous](part03.html) | [next](part05.html)
diff --git a/workspace/src/part05.rs b/workspace/src/part05.rs
new file mode 100644 (file)
index 0000000..538bf5f
--- /dev/null
@@ -0,0 +1,150 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 05: Clone
+// ========================
+
+// ## Big Numbers
+// In the course of the next few parts, we are going to build a data-structure for computations with
+// *big* numbers. We would like to not have an upper bound to how large these numbers can get, with
+// the memory of the machine being the only limit.
+// 
+// We start by deciding how to represent such big numbers. One possibility here is
+// to use a vector "digits" of the number. This is like "1337" being a vector of four digits (1, 3, 3, 7),
+// except that we will use `u64` as type of our digits, meaning we have 2^64 individual digits. Now we just
+// have to decide the order in which we store numbers. I decided that we will store the least significant
+// digit first. This means that "1337" would actually become (7, 3, 3, 1).<br/>
+// Finally, we declare that there must not be any trailing zeros (corresponding to
+// useless leading zeros in our usual way of writing numbers). This is to ensure that
+// the same number can only be stored in one way.
+
+// To write this down in Rust, we use a `struct`, which is a lot like structs in C:
+// Just a bunch of named fields. Every field can be private to the current module (which is the default),
+// or public (which is indicated by a `pub` in front of the name). For the sake of the tutorial, we make
+// `data` public - otherwise, the next parts of this course could not work on `BigInt`s. Of course, in a
+// real program, one would make the field private to ensure that the invariant (no trailing zeros) is maintained.
+pub struct BigInt {
+    pub data: Vec<u64>,
+}
+
+// Now that we fixed the data representation, we can start implementing methods on it.
+impl BigInt {
+    // Let's start with a constructor, creating a `BigInt` from an ordinary integer.
+    // To create an instance of a struct, we write its name followed by a list of
+    // fields and initial values assigned to them.
+    pub fn new(x: u64) -> Self {
+        if x == 0 {
+            BigInt { data: vec![] }
+        } else {
+            BigInt { data: vec![x] }
+        }
+    }
+
+    // It can often be useful to encode the invariant of a data-structure in code, so here
+    // is a check that detects useless trailing zeros.
+    pub fn test_invariant(&self) -> bool {
+        if self.data.len() == 0 {
+            true
+        } else {
+            self.data[self.data.len() - 1] != 0
+        }
+    }
+
+    // We can convert any vector of digits into a number, by removing trailing zeros. The `mut`
+    // declaration for `v` here is just like the one in `let mut ...`, it says that we will locally
+    // change the vector `v`.
+    // 
+    // **Exercise 05.1**: Implement this function.
+    // 
+    // *Hint*: You can use `pop()` to remove the last element of a vector.
+    pub fn from_vec(mut v: Vec<u64>) -> Self {
+        unimplemented!()
+    }
+}
+
+// ## Cloning
+// If you have a close look at the type of `BigInt::from_vec`, you will notice that it
+// consumes the vector `v`. The caller hence loses access to its vector. There is however something
+// we can do if we don't want that to happen: We can explicitly `clone` the vector,
+// which means that a full (or *deep*) copy will be performed. Technically,
+// `clone` takes a borrowed vector, and returns a fully owned one.
+fn clone_demo() {
+    let v = vec![0,1 << 16];
+    let b1 = BigInt::from_vec((&v).clone());
+    let b2 = BigInt::from_vec(v);
+}
+// Rust has special treatment for methods that borrow its `self` argument (like `clone`, or
+// like `test_invariant` above): It is not necessary to explicitly borrow the receiver of the
+// method. Hence you could replace `(&v).clone()` by `v.clone()` above. Just try it!
+
+// To be clonable is a property of a type, and as such, naturally expressed with a trait.
+// In fact, Rust already comes with a trait `Clone` for exactly this purpose. We can hence
+// make our `BigInt` clonable as well.
+impl Clone for BigInt {
+    fn clone(&self) -> Self {
+        BigInt { data: self.data.clone() }
+    }
+}
+// Making a type clonable is such a common exercise that Rust can even help you doing it:
+// If you add `#[derive(Clone)]` right in front of the definition of `BigInt`, Rust will
+// generate an implementation of `Clone` that simply clones all the fields. Try it!
+// These `#[...]` annotations at types (and functions, modules, crates) are called *attributes*.
+// We will see some more examples of attributes later.
+
+// We can also make the type `SomethingOrNothing<T>` implement `Clone`. However, that
+// can only work if `T` is `Clone`! So we have to add this bound to `T` when we introduce
+// the type variable.
+use part02::{SomethingOrNothing,Something,Nothing};
+impl<T: Clone> Clone for SomethingOrNothing<T> {
+    fn clone(&self) -> Self {
+        match *self {
+            Nothing => Nothing,
+            // In the second arm of the match, we need to talk about the value `v`
+            // that's stored in `self`. However, if we would write the pattern as
+            // `Something(v)`, that would indicate that we *own* `v` in the code
+            // after the arrow. That can't work though, we have to leave `v` owned by
+            // whoever called us - after all, we don't even own `self`, we just borrowed it.
+            // By writing `Something(ref v)`, we borrow `v` for the duration of the match
+            // arm. That's good enough for cloning it.
+            Something(ref v) => Something(v.clone()),
+        }
+    }
+}
+// Again, Rust will generate this implementation automatically if you add
+// `#[derive(Clone)]` right before the definition of `SomethingOrNothing`.
+
+// **Exercise 05.2**: Write some more functions on `BigInt`. What about a function that returns the number of
+// digits? The number of non-zero digits? The smallest/largest digit?
+
+// ## Mutation + aliasing considered harmful (part 2)
+// Now that we know how to borrow a part of an `enum` (like `v` above), there's another example for why we
+// have to rule out mutation in the presence of aliasing. First, we define an `enum` that can hold either
+// a number, or a string.
+enum Variant {
+    Number(i32),
+    Text(String),
+}
+// Now consider the following piece of code. Like above, `n` will be a borrow of a part of `var`,
+// and since we wrote `ref mut`, the borrow will be mutable. In other words, right after the match, `ptr`
+// points to the number that's stored in `var`, where `var` is a `Number`. Remember that `_` means
+// "we don't care".
+fn work_on_variant(mut var: Variant, text: String) {
+    let mut ptr: &mut i32;
+    match var {
+        Variant::Number(ref mut n) => ptr = n,
+        Variant::Text(_) => return,
+    }
+    /* var = Variant::Text(text); */
+    *ptr = 1337;
+}
+// Now, imagine what would happen if we were permitted to also mutate `var`. We could, for example,
+// make it a `Text`. However, `ptr` still points to the old location! Hence `ptr` now points somewhere
+// into the representation of a `String`. By changing `ptr`, we manipulate the string in completely
+// unpredictable ways, and anything could happen if we were to use it again! (Technically, the first field
+// of a `String` is a pointer to its character data, so by overwriting that pointer with an integer,
+// we make it a completely invalid address. When the destructor of `var` runs, it would try to deallocate
+// that address, and Rust would eat your laundry - or whatever.)
+// 
+// I hope this example clarifies why Rust has to rule out mutation in the presence of aliasing *in general*,
+// not just for the specific case of a buffer being reallocated, and old pointers becoming hence invalid.
+
+// [index](main.html) | [previous](part04.html) | [next](part06.html)
diff --git a/workspace/src/part06.rs b/workspace/src/part06.rs
new file mode 100644 (file)
index 0000000..dea1d1d
--- /dev/null
@@ -0,0 +1,152 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 06: Copy, Lifetimes
+// ==================================
+
+// We continue to work on our `BigInt`, so we start by importing what we already established.
+use part05::BigInt;
+
+// With `BigInt` being about numbers, we should be able to write a version of `vec_min`
+// that computes the minimum of a list of `BigInt`. First, we have to write `min` for `BigInt`.
+impl BigInt {
+    fn min_try1(self, other: Self) -> Self {
+        // Just to be sure, we first check that both operands actually satisfy our invariant. `debug_assert!` is a
+        // macro that checks that its argument (must be of type `bool`) is `true`, and panics otherwise. It gets
+        // removed in release builds, which you do with `cargo build --release`.
+        debug_assert!(self.test_invariant() && other.test_invariant());
+        // Now our assumption of having no trailing zeros comes in handy:
+        // If the lengths of the two numbers differ, we already know which is larger.
+        if self.data.len() < other.data.len() {
+            self
+        } else if self.data.len() > other.data.len() {
+            other
+        } else {
+            // **Exercise 06.1**: Fill in this code.
+            unimplemented!()
+        }
+    }
+}
+
+// Now we can write `vec_min`. However, in order to make it type-check, we have to make a full (deep) copy of e
+// by calling `clone()`.
+fn vec_min(v: &Vec<BigInt>) -> Option<BigInt> {
+    let mut min: Option<BigInt> = None;
+    for e in v {
+        let e = e.clone();
+        min = Some(match min {
+            None => e,
+            Some(n) => e.min_try1(n)
+        });
+    }
+    min
+}
+// Now, what's happening here? Why do we have to clone `e`, and why did we not
+// have to do that in our previous version?
+// 
+// The answer is already hidden in the type of `vec_min`: `v` is just borrowed, but
+// the Option<BigInt> that it returns is *owned*. We can't just return one of the elements of `v`,
+// as that would mean that it is no longer in the vector! In our code, this comes up when we update
+// the intermediate variable `min`, which also has type `Option<BigInt>`. If you replace get rid of the
+// `e.clone()`, Rust will complain "Cannot move out of borrowed content". That's because
+// `e` is a `&BigInt`. Assigning `min = Some(*e)` works just like a function call: Ownership of the
+// underlying data is transferred from where `e` borrows from to `min`. But that's not allowed, since
+// we just borrowed `e`, so we cannot empty it! We can, however, call `clone()` on it. Then we own
+// the copy that was created, and hence we can store it in `min`.<br/>
+// Of course, making such a full copy is expensive, so we'd like to avoid it. We'll some to that in the next part.
+
+// ## `Copy` types
+// But before we go there, I should answer the second question I brought up above: Why did our old `vec_min` work?
+// We stored the minimal `i32` locally without cloning, and Rust did not complain. That's because there isn't
+// really much of an "ownership" when it comes to types like `i32` or `bool`: If you move the value from one
+// place to another, then both instances are "complete". We also say the value has been *duplicated*. This is in
+// stark contrast to types like `Vec<i32>`, where moving the value results in both the old and the new vector to
+// point to the same underlying buffer. We don't have two vectors, there's no proper duplication.
+//
+// Rust calls types that can be easily duplicated `Copy` types. `Copy` is another trait, and it is implemented for
+// types like `i32` and `bool`. Remember how we defined the trait `Minimum` by writing `trait Minimum : Copy { ...`?
+// This tells Rust that every type that implements `Minimum` must also implement `Copy`, and that's why the compiler
+// accepted our generic `vec_min` in part 02. `Copy` is the first *marker trait* that we encounter: It does not provide
+// any methods, but makes a promise about the behavior of the type - in this case, being duplicable.
+
+// If you try to implement `Copy` for `BigInt`, you will notice that Rust
+// does not let you do that. A type can only be `Copy` if all its elements
+// are `Copy`, and that's not the case for `BigInt`. However, we can make
+// `SomethingOrNothing<T>` copy if `T` is `Copy`.
+use part02::{SomethingOrNothing,Something,Nothing};
+impl<T: Copy> Copy for SomethingOrNothing<T> {}
+// Again, Rust can generate implementations of `Copy` automatically. If
+// you add `#[derive(Copy,Clone)]` right before the definition of `SomethingOrNothing`,
+// both `Copy` and `Clone` will automatically be implemented.
+
+// ## An operational perspective
+// Instead of looking at what happens "at the surface" (i.e., visible in Rust), one can also explain
+// ownership passing and how `Copy` and `Clone` fit in by looking at what happens on the machine.<br/>
+// When Rust code is executed, passing a value (like `i32` or `Vec<i32>`) to a function will always
+// result in a shallow copy being performed: Rust just copies the bytes representing that value, and
+// considers itself done. That's just like the default copy constructor in C++. Rust, however, will
+// consider this a destructive operation: After copying the bytes elsewhere, the original value must
+// no longer be used. After all, the two could now share a pointer! If, however, you mark a type `Copy`,
+// then Rust will *not* consider a move destructive, and just like in C++, the old and new value
+// can happily coexist. Now, Rust does not allow you to overload the copy constructor. This means that
+// passing a value around will always be a fast operation, no allocation or any other kind of heap access
+// will happen. In the situations where you would write a copy constructor in C++ (and hence
+// incur a hidden cost on every copy of this type), you'd have the type *not* implement `Copy`, but only
+// `Clone`. This makes the cost explicit.
+
+// ## Lifetimes
+// To fix the performance problems of `vec_min`, we need to avoid using `clone()`. We'd like
+// the return value to not be owned (remember that this was the source of our need for cloning), but *borrowed*.
+
+// The function `head` demonstrates how that could work: It borrows the first element of a vector if it is non-empty.
+// The type of the function says that it will either return nothing, or it will return a borrowed `T`.
+// We can then borrow the first element of `v` and use it to construct the return value.
+fn head<T>(v: &Vec<T>) -> Option<&T> {
+    if v.len() > 0 {
+        Some(&v[0])
+    } else {
+        None
+    }
+}
+// Technically, we are returning a pointer to the first element. But doesn't that mean that callers have to be
+// careful? Imagine `head` would be a C++ function, and we would write the following code.
+/*
+  int foo(std::vector<int> v) {
+    int *first = head(v);
+    v.push_back(42);
+    return *first;
+  }
+*/
+// This is very much like our very first motivating example for ownership, at the beginning of part 04:
+// `push_back` could reallocate the buffer, making `first` an invalid pointer. Again, we have aliasing (of `first`
+// and `v`) and mutation. But this time, the bug is hidden behind the call to `head`. How does Rust solve this? If we translate
+// the code above to Rust, it doesn't compile, so clearly we are good - but how and why?
+// (Notice that have to explicitly assert using `unwrap` that `first` is not `None`, whereas the C++ code
+// above would silently dereference a `NULL`-pointer. But that's another point.)
+fn rust_foo(mut v: Vec<i32>) -> i32 {
+    let first: Option<&i32> = head(&v);
+    /* v.push(42); */
+    *first.unwrap()
+}
+
+// To give the answer to this question, we have to talk about the *lifetime* of a borrow. The point is, saying that
+// you borrowed your friend a `Vec<i32>`, or a book, is not good enough, unless you also agree on *how long*
+// your friend can borrow it. After all, you need to know when you can rely on owning your data (or book) again.
+// 
+// Every borrow in Rust has an associated lifetime, written `&'a T` for a borrow of type `T` with lifetime `'a`. The full
+// type of `head` reads as follows: `fn<'a, T>(&'a Vec<T>) -> Option<&'a T>`. Here, `'a` is a *lifetime variable*, which
+// represents how long the vector has been borrowed. The function type expresses that argument and return value have *the same lifetime*.
+// 
+// When analyzing the code of `rust_foo`, Rust has to assign a lifetime to `first`. It will choose the scope
+// where `first` is valid, which is the entire rest of the function. Because `head` ties the lifetime of its
+// argument and return value together, this means that `&v` also has to borrow `v` for the entire duration of
+// the function. So when we try to borrow `v` mutable for `push`, Rust complains that the two borrows (the one
+// for `head`, and the one for `push`) overlap. Lucky us! Rust caught our mistake and made sure we don't crash the program.
+// 
+// So, to sum this up: Lifetimes enable Rust to reason about *how long* a pointer has been borrowed. We can thus
+// safely write functions like `head`, that return pointers into data they got as argument, and make sure they
+// are used correctly, *while looking only at the function type*. At no point in our analysis of `rust_foo` did
+// we have to look *into* `head`. That's, of course, crucial if we want to separate library code from application code.
+// Most of the time, we don't have to explicitly add lifetimes to function types. This is thanks to *lifetimes elision*,
+// where Rust will automatically insert lifetimes we did not specify, following some [simple, well-documented rules](http://doc.rust-lang.org/stable/book/lifetimes.html#lifetime-elision).
+
+// [index](main.html) | [previous](part05.html) | [next](part07.html)
diff --git a/workspace/src/part07.rs b/workspace/src/part07.rs
new file mode 100644 (file)
index 0000000..002fcdc
--- /dev/null
@@ -0,0 +1,151 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 07: Operator Overloading, Tests, Formatting
+// ==========================================================
+
+pub use part05::BigInt;
+
+// With our new knowledge of lifetimes, we are now able to write down the desired type
+// of `min`: We want the function to take two borrows *of the same lifetime*, and then
+// return a borrow of that lifetime. If the two input lifetimes would be different, we
+// would not know which lifetime to use for the result.
+pub trait Minimum {
+    fn min<'a>(&'a self, other: &'a Self) -> &'a Self;
+}
+
+// Now we can implement a generic function `vec_min` that works on above trait.
+// The code is pretty much straight-forward, and Rust checks that all the
+// lifetimes actually work out. Observe that we don't have to make any copies!
+pub fn vec_min<T: Minimum>(v: &Vec<T>) -> Option<&T> {
+    let mut min: Option<&T> = None;
+    for e in v {
+        min = Some(match min {
+            None => e,
+            Some(n) => n.min(e)
+        });
+    }
+    min
+}
+// Notice that the return type `Option<&T>` is technically (leaving the borrowing story aside) a
+// pointer to a `T`, that could optionally be invalid. In other words, it's just like a pointer in
+// C(++) or Java that can be `NULL`! However, thanks to `Option` being an `enum`, we cannot forget
+// to check the pointer for validity, avoiding the safety issues of C(++).<br/>
+// Also, if you are worried about wasting space, notice that Rust knows that `&T` can never be
+// `NULL`, and hence optimizes `Option<&T>` to be no larger than `&T`. The `None` case is represented
+// as `NULL`. This is another great example of a zero-cost abstraction: `Option<&T>` is exactly like
+// a pointer in C(++), if you look at what happens during execution - but it's much safer to use.
+
+// **Exercise 07.1**: For our `vec_min` to be usable with `BigInt`, you will have to provide an implementation of
+// `Minimum`. You should be able to pretty much copy the code you wrote for exercise 06.1. You should *not*
+// make any copies!
+impl Minimum for BigInt {
+    fn min<'a>(&'a self, other: &'a Self) -> &'a Self {
+        unimplemented!()
+    }
+}
+
+// ## Operator Overloading
+// How can we know that our `min` function actually does what we want it to do? One possibility
+// here is to do *testing*. Rust comes with nice built-in support for both unit tests and integration
+// tests. However, before we go there, we need to have a way of checking whether the results of function calls are
+// correct. In other words, we need to define how to test equality of `BigInt`. Being able to
+// test equality is a property of a type, that - you guessed it - Rust expresses as a trait: `PartialEq`.
+
+// Doing this for `BigInt` is fairly easy, thanks to our requirement that there be no trailing zeros. We simply
+// re-use the equality test on vectors, which compares all the elements individually.
+// The `inline` attribute tells Rust that we will typically want this function to be inlined.
+impl PartialEq for BigInt {
+    #[inline]
+    fn eq(&self, other: &BigInt) -> bool {
+        debug_assert!(self.test_invariant() && other.test_invariant());
+        self.data == other.data
+    }
+}
+// Since implementing `PartialEq` is a fairly mechanical business, you can let Rust automate this
+// by adding the attribute `derive(PartialEq)` to the type definition. In case you wonder about
+// the "partial", I suggest you check out the documentation of [`PartialEq`](http://doc.rust-lang.org/std/cmp/trait.PartialEq.html)
+// and [`Eq`](http://doc.rust-lang.org/std/cmp/trait.Eq.html). `Eq` can be automatically derived as well.
+
+// Now we can compare `BigInt`s. Rust treats `PratialEq` special in that it is wired to the operator `==`:
+//  That operator can not be used on our numbers! Speaking in C++ terms, we just overloaded the `==` operator
+// for `BigInt`. Rust does not have function overloading (i.e., it will not dispatch to different
+// functions depending on the type of the argument). Instead, one typically finds (or defines) a
+// trait that catches the core characteristic common to all the overloads, and writes a single
+// function that's generic in the trait. For example, instead of overloading a function for all
+// the ways a string can be represented, one writes a generic functions over [ToString](http://doc.rust-lang.org/std/string/trait.ToString.html).
+// Usually, there is a trait like this that fits the purpose - and if there is, this has the great
+// advantage that any type *you* write, that can convert to a string, just has to implement
+// that trait to be immediately usable with all the functions out there that generalize over `ToString`.
+// Compare that to C++ or Java, where the only chance to add a new overloading variant is to
+// edit the class of the receiver.
+// 
+// Why can we also use `!=`, even though we just overloaded `==`? The answer lies in what's called a *default implementation*.
+// If you check out the documentation of `PartialEq` I linked above, you will see that the trait actually provides
+// two methods: `eq` to test equality, and `ne` to test inequality. As you may have guessed, `!=` is wired to `ne`.
+// The trait *definition* also provides a default implementation of `ne` to be the negation of `eq`. Hence you can just
+// provide `eq`, and `!=` will work fine. Or, if you have a more efficient way of deciding inequality, you can provide
+// `ne` for your type yourself.
+fn compare_big_ints() {
+    let b1 = BigInt::new(13);
+    let b2 = BigInt::new(37);
+    println!("b1 == b1: {} ; b1 == b2: {}; b1 != b2: {}", b1 == b1, b1 == b2, b1 != b2);
+}
+
+// ## Testing
+// With our equality test written, we are now ready to write our first testcase. It doesn't get much
+// simpler: You just write a function (with no arguments or return value), and give it the `test` attribute.
+// `assert!` is like `debug_assert!`, but does not get compiled away in a release build.
+#[test]
+fn test_min() {
+    let b1 = BigInt::new(1);
+    let b2 = BigInt::new(42);
+    let b3 = BigInt::from_vec(vec![0, 1]);
+
+    assert!(*b1.min(&b2) == b1);
+    assert!(*b3.min(&b2) == b2);
+}
+// Now run `cargo test` to execute the test. If you implemented `min` correctly, it should all work!
+
+// ## Formatting
+// There is also a macro `assert_eq!` that's specialized to test for equality, and that prints the two
+// values (left and right) if they differ. To be able to do that, the macro needs to know how to format
+// the value for printing. This means that we - guess what? - have to implement an appropriate trait.
+// Rust knows about two ways of formatting a value: `Display` is for pretty-printing something in a way
+// that users can understand, while `Debug` is meant to show the internal state of data and targeted at
+// the programmer. The latter is what we want for `assert_eq!`, so let's get started.
+
+// All formating is handled by [`std::fmt`](http://doc.rust-lang.org/std/fmt/index.html). I won't explain
+// all the details, and refer you to the documentation instead.
+use std::fmt;
+
+// In the case of `BigInt`, we'd like to just output our internal `data` array, so we
+// simply call the formating function of `Vec<u64>`.
+impl fmt::Debug for BigInt {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.data.fmt(f)
+    }
+}
+// `Debug` implementations can be automatically generated using the `derive(Debug)` attribute.
+
+// Now we are ready to use `assert_eq!` to test `vec_min`.
+#[test]
+fn test_vec_min() {
+    let b1 = BigInt::new(1);
+    let b2 = BigInt::new(42);
+    let b3 = BigInt::from_vec(vec![0, 1]);
+
+    let v1 = vec![b2.clone(), b1.clone(), b3.clone()];
+    let v2 = vec![b2.clone(), b3.clone()];
+    assert_eq!(vec_min(&v1), Some(&b1));
+    assert_eq!(vec_min(&v2), Some(&b2));
+}
+
+// **Exercise 07.1**: Add some more testcases. In particular, make sure you test the behavior of
+// `vec_min` on an empty vector. Also add tests for `BigInt::from_vec` (in particular, removing
+// trailing zeros). Finally, break one of your functions in a subtle way and watch the test fail.
+// 
+// **Exercise 07.2**: Go back to your good ol' `SomethingOrNothing`, and implement `Display` for it. (This will,
+// of course, need a `Display` bound on `T`.) Then you should be able to use them with `println!` just like you do
+// with numbers, and get rid of the inherent functions to print `SomethingOrNothing<i32>` and `SomethingOrNothing<f32>`.
+
+// [index](main.html) | [previous](part06.html) | [next](main.html)
diff --git a/workspace/src/part08.rs b/workspace/src/part08.rs
new file mode 100644 (file)
index 0000000..269f134
--- /dev/null
@@ -0,0 +1,38 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 08: Associated Types, Modules
+// ============================================
+
+use std::cmp;
+use std::ops;
+use std::fmt;
+use part05::BigInt;
+
+// Add with carry, returning the sum and the carry
+fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
+    let sum = u64::wrapping_add(a, b);
+    if sum >= a { // first addition did not overflow
+        unimplemented!()
+    } else { // first addition *did* overflow
+        unimplemented!()
+    }
+}
+
+/*#[test]*/
+fn test_overflowing_add() {
+    assert_eq!(overflowing_add(10, 100, false), (110, false));
+    assert_eq!(overflowing_add(10, 100, true), (111, false));
+    assert_eq!(overflowing_add(1 << 63, 1 << 63, false), (0, true));
+    assert_eq!(overflowing_add(1 << 63, 1 << 63, true), (1, true));
+    assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true));
+}
+
+impl ops::Add for BigInt {
+    type Output = BigInt;
+    fn add(self, rhs: BigInt) -> Self::Output {
+        let mut result_vec:Vec<u64> = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len()));
+        unimplemented!()
+    }
+}
+
+// [index](main.html) | [previous](part07.html) | [next](main.html)
diff --git a/workspace/src/part09.rs b/workspace/src/part09.rs
new file mode 100644 (file)
index 0000000..e153f6d
--- /dev/null
@@ -0,0 +1,6 @@
+// ***Remember to enable/add this part in `main.rs`!***
+
+// Rust-101, Part 09: Iterators
+// ============================
+
+// [index](main.html) | [previous](part08.html) | [next](main.html)