From 4f61be32dd480f23a7fef05ee66c42ae27c980c6 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Fri, 26 Jun 2015 20:56:02 +0200 Subject: [PATCH] @-ify all the things --- Makefile | 2 +- src/part00.rs | 4 +- src/part01.rs | 2 +- src/part02.rs | 153 +++++++++++++++++------------------ src/part03.rs | 110 +++++++++++++------------ src/part04.rs | 144 ++++++++++++++++----------------- src/part05.rs | 150 +++++++++++++++++----------------- src/part06.rs | 174 ++++++++++++++++++++-------------------- src/part07.rs | 139 ++++++++++++++++---------------- src/part08.rs | 4 +- src/part09.rs | 4 +- workspace/src/part00.rs | 2 - workspace/src/part01.rs | 1 - workspace/src/part02.rs | 83 +++---------------- workspace/src/part03.rs | 63 +++------------ workspace/src/part04.rs | 72 ----------------- workspace/src/part05.rs | 80 ++---------------- workspace/src/part06.rs | 89 +------------------- workspace/src/part07.rs | 79 +++--------------- workspace/src/part08.rs | 4 +- workspace/src/part09.rs | 4 +- 21 files changed, 486 insertions(+), 877 deletions(-) diff --git a/Makefile b/Makefile index 25a2fe0..40a2a79 100644 --- a/Makefile +++ b/Makefile @@ -24,7 +24,7 @@ workspace/src/%.rs: src/%.rs Makefile dup-unimpl.sed @echo "$< -> $@" @echo "// ***Remember to enable/add this part in \`main.rs\`!***" > $@ @echo >> $@ - @sed '/^\s*\/\/@/d;s|\(\s*\)[^\s].*/\*@\*/|\1unimplemented!()|' $< | sed -f dup-unimpl.sed >> $@ + @sed '/^\s*\/\/@/d;s|\(\s*\)\S.*/\*@\*/|\1unimplemented!()|' $< | sed -f dup-unimpl.sed >> $@ workspace/src/main.rs: # Don't touch this file diff --git a/src/part00.rs b/src/part00.rs index ed76e81..06bb205 100644 --- a/src/part00.rs +++ b/src/part00.rs @@ -85,8 +85,8 @@ fn read_vec() -> Vec { // 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. +//@ 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. //@ `println!` is again a macro, where the first argument is a *format string*. For //@ now, you just need to know that `{}` is the placeholder for a value, and that Rust diff --git a/src/part01.rs b/src/part01.rs index 11e9077..ed4f73f 100644 --- a/src/part01.rs +++ b/src/part01.rs @@ -100,4 +100,4 @@ pub fn main() { // **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) +//@ [index](main.html) | [previous](part00.html) | [next](part02.html) diff --git a/src/part02.rs b/src/part02.rs index e4f50be..41bb3bc 100644 --- a/src/part02.rs +++ b/src/part02.rs @@ -1,124 +1,125 @@ // 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. +//@ 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`. +//@ 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 { 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` to get back our `NumberOrNothing`. +//@ What this does is to define an entire family of types: We can now write +//@ `SomethingOrNothing` to get back our `NumberOrNothing`. type NumberOrNothing = SomethingOrNothing; -// However, we can also write `SomethingOrNothing` or even `SomethingOrNothing>`. -// 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`. 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.) +//@ However, we can also write `SomethingOrNothing` or even `SomethingOrNothing>`. +//@ 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`. 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` -// from an `Option`, 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 `` -// as *declaring* a type variable ("I am doing something for all types `T`"), and the second `` as -// *using* that variable ("The thing I do, is implement `SomethingOrNothing`"). -// +//@ The types are so similar, that we can provide a generic function to construct a `SomethingOrNothing` +//@ from an `Option`, and vice versa. +//@ +//@ Notice the syntax for giving generic implementations to generic types: Think of the first `` +//@ as *declaring* a type variable ("I am doing something for all types `T`"), and the second `` as +//@ *using* that variable ("The thing I do, is implement `SomethingOrNothing`"). +//@ // Inside an `impl`, `Self` refers to the type we are implementing things for. Here, it is // an alias for `SomethingOrNothing`. -// Remember that `self` is the `this` of Rust, and implicitly has type `Self`. +//@ Remember that `self` is the `this` of Rust, and implicitly has type `Self`. impl SomethingOrNothing { fn new(o: Option) -> Self { - unimplemented!() + match o { None => Nothing, Some(t) => Something(t) } /*@*/ } fn to_option(self) -> Option { - unimplemented!() + match self { Nothing => None, Something(t) => Some(t) } /*@*/ } } -// 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`. -// +//@ 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 { 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*. +//@ 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.
-// 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. +//@ 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.
+//@ 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!
-// This is in strong contrast to C++, where the compiler only checks such details when the -// function is actually used. +//@ 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!
+//@ This is in strong contrast to C++, where the compiler only checks such details when the +//@ function is actually used. pub fn vec_min(v: Vec) -> SomethingOrNothing { let mut min = Nothing; for e in v { min = Something(match min { Nothing => e, - Something(n) => e.min(n) + // Here, we can now call the `min` function of the trait. + 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. +//@ 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`, we implement the `Minimum` trait for `i32`. +// To make `vec_min` usable with a `Vec`, we implement the `Minimum` trait for `i32`. impl Minimum for i32 { fn min(self, b: Self) -> Self { - if self < b { self } else { b } + 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`), -// and we can provide some methods only for certain instances of a generic type. +// 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`), +//@ and we can provide some methods only for certain instances of a generic type. impl NumberOrNothing { pub fn print(self) { match self { @@ -128,9 +129,9 @@ impl NumberOrNothing { } } -// 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. +// Now we are ready to run our new 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 { vec![18,5,7,3,9,27] } @@ -140,9 +141,9 @@ pub fn main() { min.print(); } -// If this printed `3`, then you generic `vec_min` is working! So get ready for the next part. +//@ 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` (where `f32` is the type +// **Exercise 02.1**: Change your program such that it computes the minimum of a `Vec` (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) +//@ [index](main.html) | [previous](part01.html) | [next](part03.html) diff --git a/src/part03.rs b/src/part03.rs index 9ab153d..4a69aab 100644 --- a/src/part03.rs +++ b/src/part03.rs @@ -1,92 +1,96 @@ // 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. +//@ 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 +// We also import the I/O *prelude*, which makes 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::::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. +//@ 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::::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 { let mut vec: Vec = Vec::::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.) + //@ 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`. This is a lot like `Option` ("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. + // here is not yet of that type: It rather has type `io::Result`. + //@ The problem with I/O is that it can always go wrong. The type of `line`is a lot like `Option` ("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()`? - // + //@ 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! + // 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::` is `parse` with its generic type set to `i32`. + //@ 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::` is `parse` with its generic type set to `i32`. match line.parse::() { - // `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), + //@ `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?"), + 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. +//@ 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. +//@ 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(); + let min = vec_min(vec); /*@*/ + min.print(); /*@*/ } // **Exercise 03.1**: Define a trait `Print` to write a generic version of `SomethingOrNothing::print`. @@ -111,4 +115,4 @@ impl SomethingOrNothing { // **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) +//@ [index](main.html) | [previous](part02.html) | [next](part04.html) diff --git a/src/part04.rs b/src/part04.rs index 663e01e..f39df37 100644 --- a/src/part04.rs +++ b/src/part04.rs @@ -1,9 +1,9 @@ // 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. +//@ 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 v) { int *first = &v[0]; @@ -11,59 +11,59 @@ *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*. +//@ 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. +//@ What does that mean in practice? Consider the following example. fn work_on_vector(v: Vec) { /* 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` 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. +//@ 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` 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. +//@ 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`. -// I also took the liberty to convert the function from `SomethingOrNothing` to the standard -// library type `Option`. +//@ So, let's re-write `vec_min` to work on a shared borrow of a vector, written `&Vec`. +//@ I also took the liberty to convert the function from `SomethingOrNothing` to the standard +//@ library type `Option`. fn vec_min(v: &Vec) -> Option { use std::cmp; @@ -86,23 +86,23 @@ fn shared_borrow_demo() { 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. +//@ 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. +//@ 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` is the type of mutable borrows of `vec`. Because the borrow is -// mutable, we can change `e` in the loop. +//@ As an example, consider a function which increments every element of a vector by 1. +//@ The type `&mut Vec` is the type of mutable borrows of `vec`. Because the borrow is +//@ mutable, we can change `e` in the loop. fn vec_inc(v: &mut Vec) { for e in v { *e += 1; @@ -116,18 +116,18 @@ fn mutable_borrow_demo() { 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`. +//@ `&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: @@ -139,4 +139,4 @@ fn mutable_borrow_demo() { // 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) +//@ [index](main.html) | [previous](part03.html) | [next](part05.html) diff --git a/src/part05.rs b/src/part05.rs index 84f14ff..72c787d 100644 --- a/src/part05.rs +++ b/src/part05.rs @@ -2,48 +2,48 @@ // ======================== // ## 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).
-// 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. +//@ 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).
+//@ 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. +//@ 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, } // 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. + //@ 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] } + 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. + //@ 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 + self.data[self.data.len() - 1] != 0 /*@*/ } } @@ -60,71 +60,71 @@ impl BigInt { } // ## 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. +//@ 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! +//@ 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. +//@ 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() } + 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. +//@ 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` 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. +// We can also make the type `SomethingOrNothing` 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 Clone for SomethingOrNothing { 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()), - } + 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`. +//@ 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. +//@ 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". +//@ 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 { @@ -134,15 +134,15 @@ fn work_on_variant(mut var: Variant, text: String) { /* 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. +//@ 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) +//@ [index](main.html) | [previous](part04.html) | [next](part06.html) diff --git a/src/part06.rs b/src/part06.rs index e357d0e..00a2bde 100644 --- a/src/part06.rs +++ b/src/part06.rs @@ -8,9 +8,9 @@ use part05::BigInt; // 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`. + //@ 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. @@ -30,77 +30,77 @@ impl BigInt { fn vec_min(v: &Vec) -> Option { let mut min: Option = None; for e in v { - let e = e.clone(); - min = Some(match min { - None => e, - Some(n) => e.min_try1(n) - }); + 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 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`. 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`.
-// 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. +//@ 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 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`. 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`.
+//@ 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`, 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. +//@ 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`, 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` copy if `T` is `Copy`. +//@ 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` copy if `T` is `Copy`. use part02::{SomethingOrNothing,Something,Nothing}; impl Copy for SomethingOrNothing {} -// 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. +//@ 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.
-// When Rust code is executed, passing a value (like `i32` or `Vec`) 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. +//@ ## 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.
+//@ When Rust code is executed, passing a value (like `i32` or `Vec`) 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*. +//@ 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. +//@ 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(v: &Vec) -> Option<&T> { if v.len() > 0 { - Some(&v[0]) + Some(&v[0]) /*@*/ } else { None } @@ -114,37 +114,37 @@ fn head(v: &Vec) -> Option<&T> { 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.) +//@ 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 { 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`, 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) -> 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). +//@ 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`, 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) -> 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) +//@ [index](main.html) | [previous](part05.html) | [next](part07.html) diff --git a/src/part07.rs b/src/part07.rs index 85fe071..6544995 100644 --- a/src/part07.rs +++ b/src/part07.rs @@ -3,35 +3,35 @@ 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. +// 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! +//@ 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(v: &Vec) -> Option<&T> { let mut min: Option<&T> = None; for e in v { - min = Some(match min { - None => e, - Some(n) => n.min(e) - }); + 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(++).
-// 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. +//@ 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(++).
+//@ 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* @@ -43,46 +43,47 @@ impl Minimum for BigInt { } // ## 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. +//@ 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 + 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. + +//@ 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. +//@ 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); @@ -90,43 +91,43 @@ fn compare_big_ints() { } // ## 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. +// 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); + 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. +//@ 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`. +//@ In the case of `BigInt`, we'd like to just output our internal `data` array, so we +//@ simply call the formating function of `Vec`. 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. +//@ `Debug` implementations can be automatically generated using the `derive(Debug)` attribute. // Now we are ready to use `assert_eq!` to test `vec_min`. -#[test] +/*#[test]*/ fn test_vec_min() { let b1 = BigInt::new(1); let b2 = BigInt::new(42); @@ -134,8 +135,8 @@ fn test_vec_min() { 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)); + 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 @@ -146,4 +147,4 @@ fn test_vec_min() { // 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` and `SomethingOrNothing`. -// [index](main.html) | [previous](part06.html) | [next](main.html) +//@ [index](main.html) | [previous](part06.html) | [next](main.html) diff --git a/src/part08.rs b/src/part08.rs index db8e56c..90c35f6 100644 --- a/src/part08.rs +++ b/src/part08.rs @@ -1,5 +1,5 @@ -// Rust-101, Part 08: Associated Types, Modules -// ============================================ +// Rust-101, Part 08: Associated Types, Modules (WIP) +// ================================================== use std::cmp; use std::ops; diff --git a/src/part09.rs b/src/part09.rs index 023a48f..dc329bc 100644 --- a/src/part09.rs +++ b/src/part09.rs @@ -1,4 +1,4 @@ -// Rust-101, Part 09: Iterators -// ============================ +// Rust-101, Part 09: Iterators (WIP) +// ================================= // [index](main.html) | [previous](part08.html) | [next](main.html) diff --git a/workspace/src/part00.rs b/workspace/src/part00.rs index 2998b20..bf6a9fd 100644 --- a/workspace/src/part00.rs +++ b/workspace/src/part00.rs @@ -63,8 +63,6 @@ fn read_vec() -> Vec { // 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) { unimplemented!() diff --git a/workspace/src/part01.rs b/workspace/src/part01.rs index bcc1b03..0578c43 100644 --- a/workspace/src/part01.rs +++ b/workspace/src/part01.rs @@ -68,4 +68,3 @@ pub fn main() { // **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 index 908bb2a..ece854a 100644 --- a/workspace/src/part02.rs +++ b/workspace/src/part02.rs @@ -3,44 +3,20 @@ // 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 { 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` to get back our `NumberOrNothing`. type NumberOrNothing = SomethingOrNothing; -// However, we can also write `SomethingOrNothing` or even `SomethingOrNothing>`. -// 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`. 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` -// from an `Option`, 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 `` -// as *declaring* a type variable ("I am doing something for all types `T`"), and the second `` as -// *using* that variable ("The thing I do, is implement `SomethingOrNothing`"). -// // Inside an `impl`, `Self` refers to the type we are implementing things for. Here, it is // an alias for `SomethingOrNothing`. -// Remember that `self` is the `this` of Rust, and implicitly has type `Self`. impl SomethingOrNothing { fn new(o: Option) -> Self { unimplemented!() @@ -50,77 +26,40 @@ impl SomethingOrNothing { 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 { 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.
-// 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!
-// This is in strong contrast to C++, where the compiler only checks such details when the -// function is actually used. pub fn vec_min(v: Vec) -> SomethingOrNothing { let mut min = Nothing; for e in v { min = Something(match min { Nothing => e, - Something(n) => e.min(n) + // Here, we can now call the `min` function of the trait. + Something(n) => { + unimplemented!() + } }); } 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`, we implement the `Minimum` trait for `i32`. +// To make `vec_min` usable with a `Vec`, we implement the `Minimum` trait for `i32`. impl Minimum for i32 { fn min(self, b: Self) -> Self { - if self < b { self } else { b } + unimplemented!() } } -// 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`), -// and we can provide some methods only for certain instances of a generic type. +// We again provide a `print` function. impl NumberOrNothing { pub fn print(self) { match self { @@ -130,9 +69,7 @@ impl NumberOrNothing { } } -// 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. +// Now we are ready to run our new code. Remember to change `main.rs` appropriately. fn read_vec() -> Vec { vec![18,5,7,3,9,27] } @@ -142,9 +79,7 @@ pub fn main() { 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` (where `f32` is the type +// **Exercise 02.1**: Change your program such that it computes the minimum of a `Vec` (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 index 7d022e8..08cca72 100644 --- a/workspace/src/part03.rs +++ b/workspace/src/part03.rs @@ -3,92 +3,50 @@ // 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 +// We also import the I/O *prelude*, which makes 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::::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 { let mut vec: Vec = Vec::::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`. This is a lot like `Option` ("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. + // here is not yet of that type: It rather has type `io::Result`. - // 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! + // Now that we have our `String`, we want to make it an `i32`. - // 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::` is `parse` with its generic type set to `i32`. match line.parse::() { - // `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), + Ok(num) => { + unimplemented!() + }, // We don't care about the particular error, so we ignore it with a `_`. - Err(_) => println!("What did I say about numbers?"), + Err(_) => { + unimplemented!() + }, } } 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(); + unimplemented!() } // **Exercise 03.1**: Define a trait `Print` to write a generic version of `SomethingOrNothing::print`. @@ -113,4 +71,3 @@ impl SomethingOrNothing { // **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 index 894ce24..fb23f29 100644 --- a/workspace/src/part04.rs +++ b/workspace/src/part04.rs @@ -3,9 +3,6 @@ // 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 v) { int *first = &v[0]; @@ -13,59 +10,17 @@ *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) { /* 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` 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`. -// I also took the liberty to convert the function from `SomethingOrNothing` to the standard -// library type `Option`. fn vec_min(v: &Vec) -> Option { use std::cmp; @@ -88,23 +43,9 @@ fn shared_borrow_demo() { 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` is the type of mutable borrows of `vec`. Because the borrow is -// mutable, we can change `e` in the loop. fn vec_inc(v: &mut Vec) { for e in v { *e += 1; @@ -118,18 +59,6 @@ fn mutable_borrow_demo() { 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: @@ -141,4 +70,3 @@ fn mutable_borrow_demo() { // 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 index 538bf5f..1eb02d8 100644 --- a/workspace/src/part05.rs +++ b/workspace/src/part05.rs @@ -4,48 +4,26 @@ // ======================== // ## 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).
-// 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, } // 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] } + unimplemented!() } } - // 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 + unimplemented!() } } @@ -62,71 +40,34 @@ impl BigInt { } // ## 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() } + unimplemented!() } } -// 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` 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. +// We can also make the type `SomethingOrNothing` implement `Clone`. use part02::{SomethingOrNothing,Something,Nothing}; impl Clone for SomethingOrNothing { 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()), - } + unimplemented!() } } -// 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 { @@ -136,15 +77,4 @@ fn work_on_variant(mut var: Variant, text: String) { /* 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 index dea1d1d..8b69022 100644 --- a/workspace/src/part06.rs +++ b/workspace/src/part06.rs @@ -10,9 +10,6 @@ use part05::BigInt; // 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. @@ -32,77 +29,22 @@ impl BigInt { fn vec_min(v: &Vec) -> Option { let mut min: Option = None; for e in v { - let e = e.clone(); - min = Some(match min { - None => e, - Some(n) => e.min_try1(n) - }); + unimplemented!() } 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 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`. 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`.
-// 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`, 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` copy if `T` is `Copy`. use part02::{SomethingOrNothing,Something,Nothing}; impl Copy for SomethingOrNothing {} -// 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.
-// When Rust code is executed, passing a value (like `i32` or `Vec`) 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(v: &Vec) -> Option<&T> { if v.len() > 0 { - Some(&v[0]) + unimplemented!() } else { None } @@ -116,37 +58,10 @@ fn head(v: &Vec) -> Option<&T> { 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 { 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`, 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) -> 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 index 002fcdc..0130637 100644 --- a/workspace/src/part07.rs +++ b/workspace/src/part07.rs @@ -5,35 +5,18 @@ 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. +// With our new knowledge of lifetimes, we are now able to write down the desired type of `min`: 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(v: &Vec) -> Option<&T> { let mut min: Option<&T> = None; for e in v { - min = Some(match min { - None => e, - Some(n) => n.min(e) - }); + unimplemented!() } 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(++).
-// 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* @@ -45,46 +28,17 @@ impl Minimum for BigInt { } // ## 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 + unimplemented!() } } -// 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); @@ -92,43 +46,32 @@ fn compare_big_ints() { } // ## 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. +// With our equality test written, we are now ready to write our first testcase. +// 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); + unimplemented!() } // 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`. 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] +/*#[test]*/ fn test_vec_min() { let b1 = BigInt::new(1); let b2 = BigInt::new(42); @@ -136,8 +79,7 @@ fn test_vec_min() { 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)); + unimplemented!() } // **Exercise 07.1**: Add some more testcases. In particular, make sure you test the behavior of @@ -148,4 +90,3 @@ fn test_vec_min() { // 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` and `SomethingOrNothing`. -// [index](main.html) | [previous](part06.html) | [next](main.html) diff --git a/workspace/src/part08.rs b/workspace/src/part08.rs index 269f134..d02cad5 100644 --- a/workspace/src/part08.rs +++ b/workspace/src/part08.rs @@ -1,7 +1,7 @@ // ***Remember to enable/add this part in `main.rs`!*** -// Rust-101, Part 08: Associated Types, Modules -// ============================================ +// Rust-101, Part 08: Associated Types, Modules (WIP) +// ================================================== use std::cmp; use std::ops; diff --git a/workspace/src/part09.rs b/workspace/src/part09.rs index e153f6d..23fd31e 100644 --- a/workspace/src/part09.rs +++ b/workspace/src/part09.rs @@ -1,6 +1,6 @@ // ***Remember to enable/add this part in `main.rs`!*** -// Rust-101, Part 09: Iterators -// ============================ +// Rust-101, Part 09: Iterators (WIP) +// ================================= // [index](main.html) | [previous](part08.html) | [next](main.html) -- 2.30.2