From: Ralf Jung Date: Tue, 16 Jun 2015 16:22:07 +0000 (+0200) Subject: work on parts 6-8 X-Git-Url: https://git.ralfj.de/rust-101.git/commitdiff_plain/09a36e34a7b4f163c25fb971771bc4c7edd63e2b?ds=sidebyside work on parts 6-8 --- diff --git a/docs/pycco_custom.css b/docs/pycco_custom.css index bee0e24..4fe2638 100644 --- a/docs/pycco_custom.css +++ b/docs/pycco_custom.css @@ -16,7 +16,7 @@ body { } h1, h2, h3, h4, h5, h6 { - line-height: 1em; + line-height: 1.1em; } /*---------------------- Syntax Highlighting -----------------------------*/ diff --git a/src/part06.rs b/src/part06.rs index 26fa124..abe4c63 100644 --- a/src/part06.rs +++ b/src/part06.rs @@ -1,17 +1,17 @@ -// Rust-101, Part 06: Copy -// ======================= +// Rust-101, Part 06: Copy, Lifetimes +// ================================== +// We continue to work on our `BigInt`, so we start by importing what we already established. use part05::BigInt; // With `BigInt` being about numbers, we should be able to write a version of `vec_min` // that computes the minimum of a list of `BigInt`. We start by writing `min` for // `BigInt`. Now our assumption of having no trailing zeros comes in handy! impl BigInt { - fn min(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`. + 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()); // If the lengths of the two numbers differ, we already know which is larger. if self.data.len() < other.data.len() { @@ -19,8 +19,8 @@ impl BigInt { } else if self.data.len() > other.data.len() { other } else { - // **Exercise 05.1**: Fill in this code. - panic!("Not yet implemented."); + // **Exercise 06.1**: Fill in this code. + unimplemented!() } } } @@ -31,7 +31,7 @@ fn vec_min(v: &Vec) -> Option { for e in v { min = Some(match min { None => e.clone(), - Some(n) => e.clone().min(n) + Some(n) => e.clone().min_try1(n) }); } min @@ -48,7 +48,7 @@ fn vec_min(v: &Vec) -> Option { // 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 soon. +// 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? @@ -58,12 +58,11 @@ fn vec_min(v: &Vec) -> Option { // 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 duplication. // -// Rust calls types that can be freely 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. +// Rust calls types that can be freely 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 @@ -91,7 +90,7 @@ impl Copy for SomethingOrNothing{} // `Clone`. This makes the cost explicit. // ## Lifetimes -// To fix the performance problems of `vec_min`, we need ti avoid using `clone()`. We'd like +// 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*. // This is demonstrated by the function `head` that borrows the first element of a vector if it is non-empty. @@ -147,4 +146,4 @@ fn rust_foo(mut v: Vec) -> i32 { // 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](main.html) +// [index](main.html) | [previous](part05.html) | [next](part07.html) diff --git a/src/part07.rs b/src/part07.rs index 92da555..c12081e 100644 --- a/src/part07.rs +++ b/src/part07.rs @@ -1,54 +1,149 @@ -use part05::BigInt; +// Rust-101, Part 07: Operator Overloading, Tests, Output +// ====================================================== +pub use part05::BigInt; + +// With our new knowledge on 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 { - /// Return the smaller of the two fn min<'a>(&'a self, other: &'a Self) -> &'a Self; } -/// Return a pointer to the minimal value of `v`. +// 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. pub fn vec_min(v: &Vec) -> Option<&T> { - let mut min = None; + let mut min: Option<&T> = None; for e in v { min = Some(match min { None => e, - Some(n) => e.min(n) + Some(n) => n.min(e) }); } min } -// Notice that `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(++). At the same time, when we +// 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(++). At the same time, when we // have a borrow like `v` above that's not an `Option`, we *know* that is has to be a valid -// pointer, so we don't even need to do a `NULL`-check.
+// pointer, so we don't even need to do the `NULL`-check that Java does all the time.
// 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. +// For our `vec_min` to be usable with `BigInt`, we need to provide an implementation of +// `minimum`. You should be able to pretty much copy the code you wrote for exercise 06.1. impl Minimum for BigInt { fn min<'a>(&'a self, other: &'a Self) -> &'a Self { + unimplemented!() + } +} + +// ## Operator Overloading +// How can we know that our `min` function actually does what we want it to do? One possibility +// here is to do *testing*. Rust comes with nice build-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 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`. Once a type implements that trait, one can use the `==` operator on it. + +// Doing this for `BigInt` is fairly easy, thanks to our requirement that there be no trailing zeros. +// 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()); - if self.data.len() < other.data.len() { - self - } else if self.data.len() > other.data.len() { - other - } else { - // compare back-to-front, i.e., most significant digit first - let mut idx = self.data.len()-1; - while idx > 0 { - if self.data[idx] < other.data[idx] { - return self; - } else if self.data[idx] > other.data[idx] { - return other; - } - else { - idx = idx-1; - } - } - // the two are equal - return self; - } + 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). Again, `Eq` can be automatically derived. + +// Now we can compare `BigInt`s! 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 write 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. +fn compare_big_ints() { + let b1 = BigInt::new(13); + let b2 = BigInt::new(37); + println!("b1 == b1: {} ; b1 == b2: {}; b1 != b2: {}", b1 == b1, b1 == b2, b1 != b2); +} + +// ## Testing +// With our equality test written, we are now ready to write out first testcase. It doesn't get much +// simpler: You just write a function (with no arguments or return value), and give it the `test` attribute. +// `assert!` is like `debug_assert!`, but does not get compiled away in a release build. +#[test] +fn test_min() { + let b1 = BigInt::new(1); + let b2 = BigInt::new(42); + let b3 = BigInt::from_vec(vec![0, 1]); + + assert!(*b1.min(&b2) == b1); + assert!(*b3.min(&b2) == b2); +} +// Now run `cargo test` to execute the test. If you implemented `min` correctly, it should all work! + +// ## Formatting +// There is also a macro `assert_eq!` that's specialized to test for equality, and that prints the two +// values (left and right) if they differ. To be able to do that, the macro needs to know how to format +// the value for printing. This means that we - guess what? - have to implement an appropriate trait. +// Rust knows about two ways of formatting a value: `Display` is for pretty-printing something in a way +// that users can understand, while `Debug` is meant to show the internal state of data and targeted at +// the programmer. The latter is what we want for `assert_eq!`, so let's get started. + +// Al 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`. While we are at it, let's also follow the usual +// Rust style of putting tests into a *submodule*, to avoid polluting the namespace. The attribute `cfg(test)` +// at the submodule means that it will only be compiled when building the tests. +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn test_vec_min() { + let b1 = BigInt::new(1); + let b2 = BigInt::new(42); + let b3 = BigInt::from_vec(vec![0, 1]); + + let v1 = vec![b2.clone(), b1.clone(), b3.clone()]; + let v2 = vec![b2.clone(), b3.clone()]; + assert_eq!(vec_min(&v1), Some(&b1)); + assert_eq!(vec_min(&v2), Some(&b2)); + } +} + +// **Exercise 07.1**: Add some more testcases. In particular, make sure you test the behavior of +// `vec_min` on an empty vector. Also add tests for `BigInt::from_vec` (in particular, removing +// trailing zeros) and the functions you wrote for exercise 05.1. Finally, break one of your +// functions in a subtle way and watch the test fail. +// +// **Exercise 07.2**: Go back to your good ol' `SomethingOrNothing`, and implement `Display` for it. (This will, +// of course, need a `Display` bound on `T`.) Then you should be able to use them with `println!` just like you do with numbers. + +// [index](main.html) | [previous](part06.html) | [next](main.html) diff --git a/src/part08.rs b/src/part08.rs index 558bd62..db8e56c 100644 --- a/src/part08.rs +++ b/src/part08.rs @@ -1,63 +1,18 @@ +// Rust-101, Part 08: Associated Types, Modules +// ============================================ + use std::cmp; use std::ops; use std::fmt; use part05::BigInt; -impl PartialEq for BigInt { - fn eq(&self, other: &BigInt) -> bool { - debug_assert!(self.test_invariant() && other.test_invariant()); - self.data == other.data - } -} - -fn call_eq() { - let b1 = BigInt::new(13); - let b2 = BigInt::new(37); - println!("b1 == b1: {} ; b1 == b2: {}; b1 != b2: {}", b1 == b1, b1 == b2, b1 != b2); -} - - -impl fmt::Debug for BigInt { - fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { - self.data.fmt(f) - } -} - - - -impl BigInt { - pub fn inc(&mut self, mut by: u64) { - panic!("Not yet implemented."); - } -} - - -#[test] -fn test_inc() { - let mut b = BigInt::new(1337); - b.inc(1337); - assert!(b == BigInt::new(1337 + 1337)); - - b = BigInt::new(0); - assert_eq!(b, BigInt::from_vec(vec![0])); - b.inc(1 << 63); - assert_eq!(b, BigInt::from_vec(vec![1 << 63])); - b.inc(1 << 63); - assert_eq!(b, BigInt::from_vec(vec![0, 1])); - b.inc(1 << 63); - assert_eq!(b, BigInt::from_vec(vec![1 << 63, 1])); - b.inc(1 << 63); - assert_eq!(b, BigInt::from_vec(vec![0, 2])); -} - - // Add with carry, returning the sum and the carry fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) { let sum = u64::wrapping_add(a, b); - if sum >= a { - panic!("First addition did not overflow. Not implemented."); - } else { - panic!("First addition *did* overflow. Not implemented."); + if sum >= a { // first addition did not overflow + unimplemented!() + } else { // first addition *did* overflow + unimplemented!() } } @@ -74,6 +29,8 @@ impl ops::Add for BigInt { type Output = BigInt; fn add(self, rhs: BigInt) -> Self::Output { let mut result_vec:Vec = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len())); - panic!("Not yet implemented."); + unimplemented!() } } + +// [index](main.html) | [previous](part07.html) | [next](main.html)