From 229b86d07e94cd3ec175051a44b3f3cb45b40b65 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Fri, 26 Jun 2015 19:55:59 +0200 Subject: [PATCH] ship generated workspace files for the benefit of non-Linux users --- .gitignore | 1 - workspace/src/part00.rs | 89 +++++++++++++++++++++++ workspace/src/part01.rs | 103 +++++++++++++++++++++++++++ workspace/src/part02.rs | 150 +++++++++++++++++++++++++++++++++++++++ workspace/src/part03.rs | 116 ++++++++++++++++++++++++++++++ workspace/src/part04.rs | 144 +++++++++++++++++++++++++++++++++++++ workspace/src/part05.rs | 150 +++++++++++++++++++++++++++++++++++++++ workspace/src/part06.rs | 152 ++++++++++++++++++++++++++++++++++++++++ workspace/src/part07.rs | 151 +++++++++++++++++++++++++++++++++++++++ workspace/src/part08.rs | 38 ++++++++++ workspace/src/part09.rs | 6 ++ 11 files changed, 1099 insertions(+), 1 deletion(-) create mode 100644 workspace/src/part00.rs create mode 100644 workspace/src/part01.rs create mode 100644 workspace/src/part02.rs create mode 100644 workspace/src/part03.rs create mode 100644 workspace/src/part04.rs create mode 100644 workspace/src/part05.rs create mode 100644 workspace/src/part06.rs create mode 100644 workspace/src/part07.rs create mode 100644 workspace/src/part08.rs create mode 100644 workspace/src/part09.rs diff --git a/.gitignore b/.gitignore index aded1db..ff9a79d 100644 --- a/.gitignore +++ b/.gitignore @@ -1,4 +1,3 @@ target/ sync-docs .tmp/ -workspace/src/part*.rs diff --git a/workspace/src/part00.rs b/workspace/src/part00.rs new file mode 100644 index 0000000..4f7b403 --- /dev/null +++ b/workspace/src/part00.rs @@ -0,0 +1,89 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 00: Algebraic datatypes +// ====================================== + +// As our first piece of Rust code, we want to write a function that computes the +// minimum of a list. + + +// An `enum` for "a number or nothing" could look as follows: +enum NumberOrNothing { + Number(i32), + Nothing +} + +// Observe how in Rust, the return type comes *after* the arguments. +fn vec_min(vec: Vec) -> NumberOrNothing { + let mut min = NumberOrNothing::Nothing; + + // Now we want to *iterate* over the list. Rust has some nice syntax for + // iterators: + for el in vec { + // So `el` is al element of the list. We need to update `min` accordingly, but how do we get the current + // number in there? This is what pattern matching can do: + match min { + // In this case (*arm*) of the `match`, `min` is currently nothing, so let's just make it the number `el`. + NumberOrNothing::Nothing => { + unimplemented!() + }, + // In this arm, `min` is currently the number `n`, so let's compute the new minimum and store it. We will write + // the function `min_i32` just after we completed this one. + NumberOrNothing::Number(n) => { + unimplemented!() + } + } + } + // Finally, we return the result of the computation. + return min; +} + +// Now that we reduced the problem to computing the minimum of two integers, let's do that. +fn min_i32(a: i32, b: i32) -> i32 { + if a < b { + unimplemented!() + } else { + unimplemented!() + } +} + +// Phew. We wrote our first Rust function! But all this `NumberOrNothing::` is getting kind of +// ugly. Can't we do that nicer? + +// Indeed, we can: The following line tells Rust to take +// the constructors of `NumberOrNothing` into the local namespace. +// Try moving that above the function, and removing all the occurrences `NumberOrNothing::`. +use self::NumberOrNothing::{Number,Nothing}; + +// To call this function, we now just need a list. Of course, ultimately we want to ask the user for +// a list of numbers, but for now, let's just hard-code something. + +// `vec!` is a *macro* (as you can tell from the `!`) that constructs a constant `Vec<_>` with the given +// elements. +fn read_vec() -> Vec { + vec![18,5,7,1,9,27] +} + +// Finally, let's call our functions and run the code! +// But, wait, we would like to actually see something, so we need to print the result. +// Of course Rust can print numbers, but after calling `vec_min`, we have a `NumberOrNothing`. +// So let's write a small helper function that prints such values. + +fn print_number_or_nothing(n: NumberOrNothing) { + match n { + Nothing => println!("The number is: "), + Number(n) => println!("The number is: {}", n), + }; +} + +// Putting it all together: +pub fn main() { + let vec = read_vec(); + let min = vec_min(vec); + print_number_or_nothing(min); +} + +// Now try `cargo run` on the console to run above code. + + +// [index](main.html) | previous | [next](part01.html) diff --git a/workspace/src/part01.rs b/workspace/src/part01.rs new file mode 100644 index 0000000..da94915 --- /dev/null +++ b/workspace/src/part01.rs @@ -0,0 +1,103 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 01: Expressions, Inherent methods +// ================================================ + +// Even though our code from the first part works, we can still learn a +// lot by making it prettier. To understand how, it is important to +// understand that Rust is an "expression-based" language. This means that most of the +// terms you write down are not just *statements* (executing code), but *expressions* +// (returning a value). This applies even to the body of entire functions! + +// ## Expression-based programming +// For example, consider `sqr`: +fn sqr(i: i32) -> i32 { i * i } +// Between the curly braces, we are giving the *expression* that computes the return value. +// So we can just write `i * i`, the expression that returns the square if `i`! +// This is very close to how mathematicians write down functions (but with more types). + +// Conditionals are also just expressions. You can compare this to the ternary `? :` operator +// from languages like C. +fn abs(i: i32) -> i32 { if i >= 0 { i } else { -i } } + +// And the same applies to case distinction with `match`: Every `arm` of the match +// gives the expression that is returned in the respective case. +// (We repeat the definition from the previous part here.) +enum NumberOrNothing { + Number(i32), + Nothing +} +use self::NumberOrNothing::{Number,Nothing}; +fn number_or_default(n: NumberOrNothing, default: i32) -> i32 { + match n { + Nothing => default, + Number(n) => n, + } +} + +// Let us now refactor `vec_min`. +fn vec_min(v: Vec) -> NumberOrNothing { + // Remember that helper function `min_i32`? Rust allows us to define such helper functions *inside* other + // functions. This is just a matter of namespacing, the inner function has no access to the data of the outer + // one. Still, being able to nicely group functions can be very useful. + fn min_i32(a: i32, b: i32) -> i32 { + if a < b { a } else { b } + } + + let mut min = Nothing; + for e in v { + // Notice that all we do here is compute a new value for `min`, and that it will always end + // up being a `Number` rather than `Nothing`. In Rust, the structure of the code + // can express this uniformity. + min = Number(match min { + Nothing => e, + Number(n) => min_i32(n, e) + }); + } + // The `return` keyword exists in Rust, but it is rarely used. Instead, we typically + // make use of the fact that the entire function body is an expression, so we can just + // write down the desired return value. + min +} + +// Now that's already much shorter! Make sure you can go over the code above and actually understand +// every step of what's going on. + +// ## Inherent implementations +// So much for `vec_min`. Let us now reconsider `print_number_or_nothing`. That function +// really belongs pretty close to the type `NumberOrNothing`. In C++ or Java, you would +// probably make it a method of the type. In Rust, we can achieve something very similar +// by providing an *inherent implementation*. +impl NumberOrNothing { + fn print(self) { + match self { + Nothing => println!("The number is: "), + Number(n) => println!("The number is: {}", n), + }; + } +} +// So, what just happened? Rust separates code from data, so the definition of the +// methods on an `enum` (and also on `struct`, which we will learn about later) +// is independent of the definition of the type. `self` is like `this` in other +// languages, and its type is always implicit. So `print` is now a method that +// takes as first argument a `NumberOrNothing`, just like `print_number_or_nothing`. +// +// Try making `number_or_default` from above an inherent method as well! + +// With our refactored functions and methods, `main` now looks as follows: +fn read_vec() -> Vec { + vec![18,5,7,2,9,27] +} +pub fn main() { + let vec = read_vec(); + let min = vec_min(vec); + min.print(); +} +// You will have to replace `part00` by `part01` in the `main` function in +// `main.rs` to run this code. + +// **Exercise 01.1**: Write a funtion `vec_sum` that computes the sum of all values of a `Vec`. + +// **Exercise 01.2**: Write a function `vec_print` that takes a vector and prints all its elements. + +// [index](main.html) | [previous](part00.html) | [next](part02.html) diff --git a/workspace/src/part02.rs b/workspace/src/part02.rs new file mode 100644 index 0000000..908bb2a --- /dev/null +++ b/workspace/src/part02.rs @@ -0,0 +1,150 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 02: Generic types, Traits +// ======================================== + +// Let us for a moment reconsider the type `NumberOrNothing`. Isn't it a bit annoying that we +// had to hard-code the type `i32` in there? What if tomorrow, we want a `CharOrNothing`, and +// later a `FloatOrNothing`? Certainly we don't want to re-write the type and all its inherent methods. + +// ## Generic datatypes + +// The solution to this is called *generics* or *polymorphism* (the latter is Greek, +// meaning "many shapes"). You may know something similar from C++ (where it's called +// *templates*) or Java, or one of the many functional languages. So here, we define +// a generic type `SomethingOrNothing`. +pub enum SomethingOrNothing { + 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!() + } + + fn to_option(self) -> Option { + 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) + }); + } + 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`. +impl Minimum for i32 { + fn min(self, b: Self) -> Self { + if self < b { self } else { b } + } +} + +// We again provide a `print` function. This also shows that we can have multiple `impl` blocks +// for the same type (remember that `NumberOrNothing` is just a type alias for `SomethingOrNothing`), +// and we can provide some methods only for certain instances of a generic type. +impl NumberOrNothing { + pub fn print(self) { + match self { + Nothing => println!("The number is: "), + Something(n) => println!("The number is: {}", n), + }; + } +} + +// Now we are again ready to run our code. Remember to change `main.rs` appropriately. +// Rust figures out automatically that we want the `T` of `vec_min` to be `i32`, and +// that `i32` implements `Minimum` and hence all is good. +fn read_vec() -> Vec { + vec![18,5,7,3,9,27] +} +pub fn main() { + let vec = read_vec(); + let min = vec_min(vec); + min.print(); +} + +// If this printed `3`, then you generic `vec_min` is working! So get ready for the next part. + +// **Exercise 02.2**: Change your program such that it computes the minimum of a `Vec` (where `f32` is the type +// of 32-bit floating-point numbers). You should not change `vec_min` in any way, obviously! + +// [index](main.html) | [previous](part01.html) | [next](part03.html) diff --git a/workspace/src/part03.rs b/workspace/src/part03.rs new file mode 100644 index 0000000..7d022e8 --- /dev/null +++ b/workspace/src/part03.rs @@ -0,0 +1,116 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 03: Input +// ======================== + +// In part 00, I promised that we would eventually replace `read_vec` by a function +// that actually asks the user to enter a bunch of numbers. Unfortunately, +// I/O is a complicated topic, so the code to do that is not exactly pretty - but well, +// let's get that behind us. + +// I/O is provided by the module `std::io`, so we first have import that with `use`. +// We also import the I/O *prelude*, which brings a bunch of commonly used I/O stuff +// directly available. +use std::io::prelude::*; +use std::io; + +// Let's now go over this function line-by-line. First, we call the constructor of `Vec` +// to create an empty vector. As mentioned in the previous part, `new` here is just +// a static function with no special treatment. While it is possible to call `new` +// for a particular type (`Vec::::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. + + // We will be lazy here and just assume that nothing goes wrong: `unwrap()` returns the `String` if there is one, + // and panics the program otherwise. Since a `Result` carries some details about the error that occurred, + // there will be a somewhat reasonable error message. Still, you would not want a user to see such + // an error, so in a "real" program, we would have to do proper error handling. + // Can you find the documentation of `Result::unwrap()`? + // + // I chose the same name (`line`) for the new variable to ensure that I will never, accidentally, + // access the "old" `line` again. + let line = line.unwrap(); + // Now that we have our `String`, we want to make it an `i32`. `parse` is a method on `String` that + // can convert a string to anything. Try finding it's documentation! + + // In this case, Rust *could* figure out automatically that we need an `i32` (because of the return type + // of the function), but that's a bit too much magic for my taste. We are being more explicit here: + // `parse::` 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), + // We don't care about the particular error, so we ignore it with a `_`. + Err(_) => println!("What did I say about numbers?"), + } + } + + vec +} + +// So much for `read_vec`. If there are any questions left, the documentation of the respective function +// should be very helpful. Try finding the one for `Vec::push`. I will not always provide the links, +// as the documentation is quite easy to navigate and you should get used to that. + +// For the rest of the code, we just re-use part 02 by importing it with `use`. +// I already sneaked a bunch of `pub` in part 02 to make this possible: Only +// items declared public can be imported elsewhere. +use part02::{SomethingOrNothing,Something,Nothing,vec_min}; + +// If you update your `main.rs` to use part 03, `cargo run` should now ask you for some numbers, +// and tell you the minimum. Neat, isn't it? +pub fn main() { + let vec = read_vec(); + let min = vec_min(vec); + min.print(); +} + +// **Exercise 03.1**: Define a trait `Print` to write a generic version of `SomethingOrNothing::print`. +// Implement that trait for `i32`, and change the code above to use it. +// I will again provide a skeleton for this solution. It also shows how to attach bounds to generic +// implementations (just compare it to the `impl` block from the previous exercise). +// You can read this as "For all types `T` satisfying the `Print` trait, I provide an implementation +// for `SomethingOrNothing`". +// +// Notice that I called the function on `SomethingOrNothing` `print2` to disambiguate from the `print` defined previously. +// +// *Hint*: There is a macro `print!` for printing without appending a newline. +trait Print { + /* Add things here */ +} +impl SomethingOrNothing { + fn print2(self) { + unimplemented!() + } +} + +// **Exercise 03.2**: Building on exercise 02.2, implement all the things you need on `f32` to make your +// program work with floating-point numbers. + +// [index](main.html) | [previous](part02.html) | [next](part04.html) diff --git a/workspace/src/part04.rs b/workspace/src/part04.rs new file mode 100644 index 0000000..894ce24 --- /dev/null +++ b/workspace/src/part04.rs @@ -0,0 +1,144 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 04: Ownership, Borrowing +// ======================================= + +// Rust aims to be a "safe systems language". As a systems language, of course it +// provides *references* (or *pointers*). But as a safe language, it has to +// prevent bugs like this C++ snippet. +/* + void foo(std::vector v) { + int *first = &v[0]; + v.push_back(42); + *first = 1337; // This is bad! + } +*/ +// What's going wrong here? `first` is a pointer into the vector `v`. The operation `push_back` +// may re-allocate the storage for the vector, in case the old buffer was full. If that happens, +// `first` is now a dangling pointer, and accessing it can crash the program (or worse). +// +// It turns out that only the combination of two circumstances can lead to such a bug: +// *aliasing* and *mutation*. In the code above, we have `first` and the buffer of `v` +// being aliases, and when `push_back` is called, the latter is used to perform a mutation. +// Therefore, the central principle of the Rust typesystem is to *rule out mutation in the presence +// of aliasing*. The core tool to achieve that is the notion of *ownership*. + +// ## Ownership +// What does that mean in practice? Consider the following example. +fn work_on_vector(v: Vec) { /* 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; + + let mut min = None; + for e in v { + // In the loop, `e` now has type `&i32`, so we have to dereference it to obtain an `i32`. + min = Some(match min { + None => *e, + Some(n) => cmp::min(n, *e) + }); + } + min +} + +// Now that `vec_min` does not acquire ownership of the vector anymore, we can call it multiple times on the same vector and also do things like +fn shared_borrow_demo() { + let v = vec![5,4,3,2,1]; + let first = &v[0]; + vec_min(&v); + vec_min(&v); + println!("The first element is: {}", *first); +} +// What's going on here? First, `&` is how you create a shared borrow to something. All borrows are created like +// this - there is no way to have something like a NULL pointer. This code creates three shared borrows to `v`: +// The borrow for `first` begins in the 2nd line of the function and lasts all the way to the end. The other two +// borrows, created for calling `vec_min`, only last for the duration of that respective call. +// +// Technically, of course, borrows are pointers. Notice that since `vec_min` only gets a shared +// borrow, Rust knows that it cannot mutate `v` in any way. Hence the pointer into the buffer of `v` +// that was created before calling `vec_min` remains valid. + +// ## Mutable borrowing +// There is a second kind of borrow, a *mutable borrow*. As the name suggests, such a borrow permits +// mutation, and hence has to prevent aliasing. There can only ever be one mutable borrow to a +// particular piece of data. + +// As an example, consider a function which increments every element of a vector by 1. +// The type `&mut Vec` 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; + } +} +// Here's an example of calling `vec_inc`. +fn mutable_borrow_demo() { + let mut v = vec![5,4,3,2,1]; + /* let first = &v[0]; */ + vec_inc(&mut v); + vec_inc(&mut v); + /* println!("The first element is: {}", *first); */ +} +// `&mut` is the operator to create a mutable borrow. We have to mark `v` as mutable in order to create such a +// borrow. Because the borrow passed to `vec_inc` only lasts as long as the function call, we can still call +// `vec_inc` on the same vector twice: The durations of the two borrows do not overlap, so we never have more +// than one mutable borrow. However, we can *not* create a shared borrow that spans a call to `vec_inc`. Just try +// enabling the commented-out lines, and watch Rust complain. This is because `vec_inc` could mutate +// the vector structurally (i.e., it could add or remove elements), and hence the pointer `first` +// could become invalid. In other words, Rust keeps us safe from bugs like the one in the C++ snipped above. +// +// Above, I said that having a mutable borrow excludes aliasing. But if you look at the code above carefully, +// you may say: "Wait! Don't the `v` in `mutable_borrow_demo` and the `v` in `vec_inc` alias?" And you are right, +// they do. However, the `v` in `mutable_borrow_demo` is not actually usable, it is not *active*: As long as there is an +// outstanding borrow, Rust will not allow you to do anything with `v`. + +// ## Summary +// The ownership and borrowing system of Rust enforces the following three rules: +// +// * There is always exactly one owner of a piece of data +// * If there is an active mutable borrow, then nobody else can have active access to the data +// * If there is an active shared borrow, then every other active access to the data is also a shared borrow +// +// As it turns out, combined with the abstraction facilities of Rust, this is a very powerful mechanism +// to tackle many problems beyond basic memory safety. You will see some examples for this soon. + +// [index](main.html) | [previous](part03.html) | [next](part05.html) diff --git a/workspace/src/part05.rs b/workspace/src/part05.rs new file mode 100644 index 0000000..538bf5f --- /dev/null +++ b/workspace/src/part05.rs @@ -0,0 +1,150 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 05: Clone +// ======================== + +// ## Big Numbers +// In the course of the next few parts, we are going to build a data-structure for computations with +// *big* numbers. We would like to not have an upper bound to how large these numbers can get, with +// the memory of the machine being the only limit. +// +// We start by deciding how to represent such big numbers. One possibility here is +// to use a vector "digits" of the number. This is like "1337" being a vector of four digits (1, 3, 3, 7), +// except that we will use `u64` as type of our digits, meaning we have 2^64 individual digits. Now we just +// have to decide the order in which we store numbers. I decided that we will store the least significant +// digit first. This means that "1337" would actually become (7, 3, 3, 1).
+// 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] } + } + } + + // It can often be useful to encode the invariant of a data-structure in code, so here + // is a check that detects useless trailing zeros. + pub fn test_invariant(&self) -> bool { + if self.data.len() == 0 { + true + } else { + self.data[self.data.len() - 1] != 0 + } + } + + // We can convert any vector of digits into a number, by removing trailing zeros. The `mut` + // declaration for `v` here is just like the one in `let mut ...`, it says that we will locally + // change the vector `v`. + // + // **Exercise 05.1**: Implement this function. + // + // *Hint*: You can use `pop()` to remove the last element of a vector. + pub fn from_vec(mut v: Vec) -> Self { + unimplemented!() + } +} + +// ## Cloning +// If you have a close look at the type of `BigInt::from_vec`, you will notice that it +// consumes the vector `v`. The caller hence loses access to its vector. There is however something +// we can do if we don't want that to happen: We can explicitly `clone` the vector, +// which means that a full (or *deep*) copy will be performed. Technically, +// `clone` takes a borrowed vector, and returns a fully owned one. +fn clone_demo() { + let v = vec![0,1 << 16]; + let b1 = BigInt::from_vec((&v).clone()); + let b2 = BigInt::from_vec(v); +} +// Rust has special treatment for methods that borrow its `self` argument (like `clone`, or +// like `test_invariant` above): It is not necessary to explicitly borrow the receiver of the +// method. Hence you could replace `(&v).clone()` by `v.clone()` above. Just try it! + +// To be clonable is a property of a type, and as such, naturally expressed with a trait. +// In fact, Rust already comes with a trait `Clone` for exactly this purpose. We can hence +// make our `BigInt` clonable as well. +impl Clone for BigInt { + fn clone(&self) -> Self { + BigInt { data: self.data.clone() } + } +} +// Making a type clonable is such a common exercise that Rust can even help you doing it: +// If you add `#[derive(Clone)]` right in front of the definition of `BigInt`, Rust will +// generate an implementation of `Clone` that simply clones all the fields. Try it! +// These `#[...]` annotations at types (and functions, modules, crates) are called *attributes*. +// We will see some more examples of attributes later. + +// We can also make the type `SomethingOrNothing` 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()), + } + } +} +// Again, Rust will generate this implementation automatically if you add +// `#[derive(Clone)]` right before the definition of `SomethingOrNothing`. + +// **Exercise 05.2**: Write some more functions on `BigInt`. What about a function that returns the number of +// digits? The number of non-zero digits? The smallest/largest digit? + +// ## Mutation + aliasing considered harmful (part 2) +// Now that we know how to borrow a part of an `enum` (like `v` above), there's another example for why we +// have to rule out mutation in the presence of aliasing. First, we define an `enum` that can hold either +// a number, or a string. +enum Variant { + Number(i32), + Text(String), +} +// Now consider the following piece of code. Like above, `n` will be a borrow of a part of `var`, +// and since we wrote `ref mut`, the borrow will be mutable. In other words, right after the match, `ptr` +// points to the number that's stored in `var`, where `var` is a `Number`. Remember that `_` means +// "we don't care". +fn work_on_variant(mut var: Variant, text: String) { + let mut ptr: &mut i32; + match var { + Variant::Number(ref mut n) => ptr = n, + Variant::Text(_) => return, + } + /* var = Variant::Text(text); */ + *ptr = 1337; +} +// Now, imagine what would happen if we were permitted to also mutate `var`. We could, for example, +// make it a `Text`. However, `ptr` still points to the old location! Hence `ptr` now points somewhere +// into the representation of a `String`. By changing `ptr`, we manipulate the string in completely +// unpredictable ways, and anything could happen if we were to use it again! (Technically, the first field +// of a `String` is a pointer to its character data, so by overwriting that pointer with an integer, +// we make it a completely invalid address. When the destructor of `var` runs, it would try to deallocate +// that address, and Rust would eat your laundry - or whatever.) +// +// I hope this example clarifies why Rust has to rule out mutation in the presence of aliasing *in general*, +// not just for the specific case of a buffer being reallocated, and old pointers becoming hence invalid. + +// [index](main.html) | [previous](part04.html) | [next](part06.html) diff --git a/workspace/src/part06.rs b/workspace/src/part06.rs new file mode 100644 index 0000000..dea1d1d --- /dev/null +++ b/workspace/src/part06.rs @@ -0,0 +1,152 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 06: Copy, Lifetimes +// ================================== + +// We continue to work on our `BigInt`, so we start by importing what we already established. +use part05::BigInt; + +// With `BigInt` being about numbers, we should be able to write a version of `vec_min` +// that computes the minimum of a list of `BigInt`. First, we have to write `min` for `BigInt`. +impl BigInt { + fn min_try1(self, other: Self) -> Self { + // Just to be sure, we first check that both operands actually satisfy our invariant. `debug_assert!` is a + // macro that checks that its argument (must be of type `bool`) is `true`, and panics otherwise. It gets + // removed in release builds, which you do with `cargo build --release`. + debug_assert!(self.test_invariant() && other.test_invariant()); + // Now our assumption of having no trailing zeros comes in handy: + // If the lengths of the two numbers differ, we already know which is larger. + if self.data.len() < other.data.len() { + self + } else if self.data.len() > other.data.len() { + other + } else { + // **Exercise 06.1**: Fill in this code. + unimplemented!() + } + } +} + +// Now we can write `vec_min`. However, in order to make it type-check, we have to make a full (deep) copy of e +// by calling `clone()`. +fn vec_min(v: &Vec) -> 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) + }); + } + 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]) + } else { + None + } +} +// Technically, we are returning a pointer to the first element. But doesn't that mean that callers have to be +// careful? Imagine `head` would be a C++ function, and we would write the following code. +/* + int foo(std::vector v) { + int *first = head(v); + v.push_back(42); + return *first; + } +*/ +// This is very much like our very first motivating example for ownership, at the beginning of part 04: +// `push_back` could reallocate the buffer, making `first` an invalid pointer. Again, we have aliasing (of `first` +// and `v`) and mutation. But this time, the bug is hidden behind the call to `head`. How does Rust solve this? If we translate +// the code above to Rust, it doesn't compile, so clearly we are good - but how and why? +// (Notice that have to explicitly assert using `unwrap` that `first` is not `None`, whereas the C++ code +// above would silently dereference a `NULL`-pointer. But that's another point.) +fn rust_foo(mut v: Vec) -> i32 { + 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 new file mode 100644 index 0000000..002fcdc --- /dev/null +++ b/workspace/src/part07.rs @@ -0,0 +1,151 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 07: Operator Overloading, Tests, Formatting +// ========================================================== + +pub use part05::BigInt; + +// With our new knowledge of lifetimes, we are now able to write down the desired type +// of `min`: We want the function to take two borrows *of the same lifetime*, and then +// return a borrow of that lifetime. If the two input lifetimes would be different, we +// would not know which lifetime to use for the result. +pub trait Minimum { + fn min<'a>(&'a self, other: &'a Self) -> &'a Self; +} + +// Now we can implement a generic function `vec_min` that works on above trait. +// The code is pretty much straight-forward, and Rust checks that all the +// lifetimes actually work out. Observe that we don't have to make any copies! +pub fn vec_min(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 +} +// 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* +// make any copies! +impl Minimum for BigInt { + fn min<'a>(&'a self, other: &'a Self) -> &'a Self { + unimplemented!() + } +} + +// ## Operator Overloading +// How can we know that our `min` function actually does what we want it to do? One possibility +// here is to do *testing*. Rust comes with nice built-in support for both unit tests and integration +// tests. However, before we go there, we need to have a way of checking whether the results of function calls are +// correct. In other words, we need to define how to test equality of `BigInt`. Being able to +// test equality is a property of a type, that - you guessed it - Rust expresses as a trait: `PartialEq`. + +// Doing this for `BigInt` is fairly easy, thanks to our requirement that there be no trailing zeros. We simply +// re-use the equality test on vectors, which compares all the elements individually. +// The `inline` attribute tells Rust that we will typically want this function to be inlined. +impl PartialEq for BigInt { + #[inline] + fn eq(&self, other: &BigInt) -> bool { + debug_assert!(self.test_invariant() && other.test_invariant()); + self.data == other.data + } +} +// Since implementing `PartialEq` is a fairly mechanical business, you can let Rust automate this +// by adding the attribute `derive(PartialEq)` to the type definition. In case you wonder about +// the "partial", I suggest you check out the documentation of [`PartialEq`](http://doc.rust-lang.org/std/cmp/trait.PartialEq.html) +// and [`Eq`](http://doc.rust-lang.org/std/cmp/trait.Eq.html). `Eq` can be automatically derived as well. + +// Now we can compare `BigInt`s. Rust treats `PratialEq` special in that it is wired to the operator `==`: +// That operator can not be used on our numbers! Speaking in C++ terms, we just overloaded the `==` operator +// for `BigInt`. Rust does not have function overloading (i.e., it will not dispatch to different +// functions depending on the type of the argument). Instead, one typically finds (or defines) a +// trait that catches the core characteristic common to all the overloads, and writes a single +// function that's generic in the trait. For example, instead of overloading a function for all +// the ways a string can be represented, one writes a generic functions over [ToString](http://doc.rust-lang.org/std/string/trait.ToString.html). +// Usually, there is a trait like this that fits the purpose - and if there is, this has the great +// advantage that any type *you* write, that can convert to a string, just has to implement +// that trait to be immediately usable with all the functions out there that generalize over `ToString`. +// Compare that to C++ or Java, where the only chance to add a new overloading variant is to +// edit the class of the receiver. +// +// Why can we also use `!=`, even though we just overloaded `==`? The answer lies in what's called a *default implementation*. +// If you check out the documentation of `PartialEq` I linked above, you will see that the trait actually provides +// two methods: `eq` to test equality, and `ne` to test inequality. As you may have guessed, `!=` is wired to `ne`. +// The trait *definition* also provides a default implementation of `ne` to be the negation of `eq`. Hence you can just +// provide `eq`, and `!=` will work fine. Or, if you have a more efficient way of deciding inequality, you can provide +// `ne` for your type yourself. +fn compare_big_ints() { + let b1 = BigInt::new(13); + let b2 = BigInt::new(37); + println!("b1 == b1: {} ; b1 == b2: {}; b1 != b2: {}", b1 == b1, b1 == b2, b1 != b2); +} + +// ## Testing +// With our equality test written, we are now ready to write our first testcase. It doesn't get much +// simpler: You just write a function (with no arguments or return value), and give it the `test` attribute. +// `assert!` is like `debug_assert!`, but does not get compiled away in a release build. +#[test] +fn test_min() { + let b1 = BigInt::new(1); + let b2 = BigInt::new(42); + let b3 = BigInt::from_vec(vec![0, 1]); + + assert!(*b1.min(&b2) == b1); + assert!(*b3.min(&b2) == b2); +} +// Now run `cargo test` to execute the test. If you implemented `min` correctly, it should all work! + +// ## Formatting +// There is also a macro `assert_eq!` that's specialized to test for equality, and that prints the two +// values (left and right) if they differ. To be able to do that, the macro needs to know how to format +// the value for printing. This means that we - guess what? - have to implement an appropriate trait. +// Rust knows about two ways of formatting a value: `Display` is for pretty-printing something in a way +// that users can understand, while `Debug` is meant to show the internal state of data and targeted at +// the programmer. The latter is what we want for `assert_eq!`, so let's get started. + +// All formating is handled by [`std::fmt`](http://doc.rust-lang.org/std/fmt/index.html). I won't explain +// all the details, and refer you to the documentation instead. +use std::fmt; + +// In the case of `BigInt`, we'd like to just output our internal `data` array, so we +// simply call the formating function of `Vec`. +impl fmt::Debug for BigInt { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.data.fmt(f) + } +} +// `Debug` implementations can be automatically generated using the `derive(Debug)` attribute. + +// Now we are ready to use `assert_eq!` to test `vec_min`. +#[test] +fn test_vec_min() { + let b1 = BigInt::new(1); + let b2 = BigInt::new(42); + let b3 = BigInt::from_vec(vec![0, 1]); + + let v1 = vec![b2.clone(), b1.clone(), b3.clone()]; + let v2 = vec![b2.clone(), b3.clone()]; + assert_eq!(vec_min(&v1), Some(&b1)); + assert_eq!(vec_min(&v2), Some(&b2)); +} + +// **Exercise 07.1**: Add some more testcases. In particular, make sure you test the behavior of +// `vec_min` on an empty vector. Also add tests for `BigInt::from_vec` (in particular, removing +// trailing zeros). Finally, break one of your functions in a subtle way and watch the test fail. +// +// **Exercise 07.2**: Go back to your good ol' `SomethingOrNothing`, and implement `Display` for it. (This will, +// of course, need a `Display` bound on `T`.) Then you should be able to use them with `println!` just like you do +// with numbers, and get rid of the inherent functions to print `SomethingOrNothing` and `SomethingOrNothing`. + +// [index](main.html) | [previous](part06.html) | [next](main.html) diff --git a/workspace/src/part08.rs b/workspace/src/part08.rs new file mode 100644 index 0000000..269f134 --- /dev/null +++ b/workspace/src/part08.rs @@ -0,0 +1,38 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 08: Associated Types, Modules +// ============================================ + +use std::cmp; +use std::ops; +use std::fmt; +use part05::BigInt; + +// Add with carry, returning the sum and the carry +fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) { + let sum = u64::wrapping_add(a, b); + if sum >= a { // first addition did not overflow + unimplemented!() + } else { // first addition *did* overflow + unimplemented!() + } +} + +/*#[test]*/ +fn test_overflowing_add() { + assert_eq!(overflowing_add(10, 100, false), (110, false)); + assert_eq!(overflowing_add(10, 100, true), (111, false)); + assert_eq!(overflowing_add(1 << 63, 1 << 63, false), (0, true)); + assert_eq!(overflowing_add(1 << 63, 1 << 63, true), (1, true)); + assert_eq!(overflowing_add(1 << 63, (1 << 63) -1 , true), (0, true)); +} + +impl ops::Add for BigInt { + type Output = BigInt; + fn add(self, rhs: BigInt) -> Self::Output { + let mut result_vec:Vec = Vec::with_capacity(cmp::max(self.data.len(), rhs.data.len())); + unimplemented!() + } +} + +// [index](main.html) | [previous](part07.html) | [next](main.html) diff --git a/workspace/src/part09.rs b/workspace/src/part09.rs new file mode 100644 index 0000000..e153f6d --- /dev/null +++ b/workspace/src/part09.rs @@ -0,0 +1,6 @@ +// ***Remember to enable/add this part in `main.rs`!*** + +// Rust-101, Part 09: Iterators +// ============================ + +// [index](main.html) | [previous](part08.html) | [next](main.html) -- 2.30.2