@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
// 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
// **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)
// 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<T> {
Something(T),
Nothing,
}
// Instead of writing out all the variants, we can also just import them all at once.
pub use self::SomethingOrNothing::*;
-// What this does is to define an entire family of types: We can now write
-// `SomethingOrNothing<i32>` to get back our `NumberOrNothing`.
+//@ What this does is to define an entire family of types: We can now write
+//@ `SomethingOrNothing<i32>` to get back our `NumberOrNothing`.
type NumberOrNothing = SomethingOrNothing<i32>;
-// However, we can also write `SomethingOrNothing<bool>` or even `SomethingOrNothing<SomethingOrNothing<i32>>`.
-// In fact, such a type is so useful that it is already present in the standard library: It's called an
-// *option type*, written `Option<T>`. Go check out its [documentation](http://doc.rust-lang.org/stable/std/option/index.html)!
-// (And don't worry, there's indeed lots of material mentioned there that we did not cover yet.)
+//@ However, we can also write `SomethingOrNothing<bool>` or even `SomethingOrNothing<SomethingOrNothing<i32>>`.
+//@ In fact, such a type is so useful that it is already present in the standard library: It's called an
+//@ *option type*, written `Option<T>`. Go check out its [documentation](http://doc.rust-lang.org/stable/std/option/index.html)!
+//@ (And don't worry, there's indeed lots of material mentioned there that we did not cover yet.)
// ## Generic `impl`, Static functions
-// The types are so similar, that we can provide a generic function to construct a `SomethingOrNothing<T>`
-// from an `Option<T>`, and vice versa.
-// **Exercise 02.1**: Implement such functions! I provided a skeleton of the solution. Here,
-// `unimplemented!` is another macro. This one terminates execution saying that something has not yet
-// been implemented.
-//
-// Notice the syntax for giving generic implementations to generic types: Think of the first `<T>`
-// as *declaring* a type variable ("I am doing something for all types `T`"), and the second `<T>` as
-// *using* that variable ("The thing I do, is implement `SomethingOrNothing<T>`").
-//
+//@ The types are so similar, that we can provide a generic function to construct a `SomethingOrNothing<T>`
+//@ from an `Option<T>`, and vice versa.
+//@
+//@ Notice the syntax for giving generic implementations to generic types: Think of the first `<T>`
+//@ as *declaring* a type variable ("I am doing something for all types `T`"), and the second `<T>` as
+//@ *using* that variable ("The thing I do, is implement `SomethingOrNothing<T>`").
+//@
// Inside an `impl`, `Self` refers to the type we are implementing things for. Here, it is
// an alias for `SomethingOrNothing<T>`.
-// Remember that `self` is the `this` of Rust, and implicitly has type `Self`.
+//@ Remember that `self` is the `this` of Rust, and implicitly has type `Self`.
impl<T> SomethingOrNothing<T> {
fn new(o: Option<T>) -> Self {
- unimplemented!()
+ match o { None => Nothing, Some(t) => Something(t) } /*@*/
}
fn to_option(self) -> Option<T> {
- 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<i32> {
SomethingOrNothing::new(Some(x))
}
// ## Traits
-// Now that we have a generic `SomethingOrNothing`, wouldn't it be nice to also gave a generic
-// `vec_min`? Of course, we can't take the minimum of a vector of *any* type. It has to be a type
-// supporting a `min` operation. Rust calls such properties that we may demand of types *traits*.
+//@ Now that we have a generic `SomethingOrNothing`, wouldn't it be nice to also gave a generic
+//@ `vec_min`? Of course, we can't take the minimum of a vector of *any* type. It has to be a type
+//@ supporting a `min` operation. Rust calls such properties that we may demand of types *traits*.
-// So, as a first step towards a generic `vec_min`, we define a `Minimum` trait.
-// For now, just ignore the `Copy`, we will come back to this point later.
-// A `trait` is a lot like interfaces in Java: You define a bunch of functions
-// you want to have implemented, and their argument and return types.<br/>
-// The function `min` takes to arguments of the same type, but I made the
-// first argument the special `self` argument. I could, alternatively, have
-// made `min` a static function as follows: `fn min(a: Self, b: Self) -> Self`.
-// However, in Rust one typically prefers methods over static function wherever possible.
+//@ So, as a first step towards a generic `vec_min`, we define a `Minimum` trait.
+//@ For now, just ignore the `Copy`, we will come back to this point later.
+//@ A `trait` is a lot like interfaces in Java: You define a bunch of functions
+//@ you want to have implemented, and their argument and return types.<br/>
+//@ The function `min` takes to arguments of the same type, but I made the
+//@ first argument the special `self` argument. I could, alternatively, have
+//@ made `min` a static function as follows: `fn min(a: Self, b: Self) -> Self`.
+//@ However, in Rust one typically prefers methods over static function wherever possible.
pub trait Minimum : Copy {
fn min(self, b: Self) -> Self;
}
-// Next, we write `vec_min` as a generic function over a type `T` that we demand to satisfy the `Minimum` trait.
-// This requirement is called a *trait bound*.
-// The only difference to the version from the previous part is that we call `e.min(n)` instead
-// of `std::cmp::min(n, e)`. Rust automatically figures out that `n` is of type `T`, which implements
-// the `Minimum` trait, and hence we can call that function.
-//
-// There is a crucial difference to templates in C++: We actually have to declare which traits
-// we want the type to satisfy. If we left away the `Minimum`, Rust would have complained that
-// we cannot call `min`. Just try it!<br/>
-// This is in strong contrast to C++, where the compiler only checks such details when the
-// function is actually used.
+//@ Next, we write `vec_min` as a generic function over a type `T` that we demand to satisfy the `Minimum` trait.
+//@ This requirement is called a *trait bound*.
+//@ The only difference to the version from the previous part is that we call `e.min(n)` instead
+//@ of `std::cmp::min(n, e)`. Rust automatically figures out that `n` is of type `T`, which implements
+//@ the `Minimum` trait, and hence we can call that function.
+//@
+//@ There is a crucial difference to templates in C++: We actually have to declare which traits
+//@ we want the type to satisfy. If we left away the `Minimum`, Rust would have complained that
+//@ we cannot call `min`. Just try it!<br/>
+//@ This is in strong contrast to C++, where the compiler only checks such details when the
+//@ function is actually used.
pub fn vec_min<T: Minimum>(v: Vec<T>) -> SomethingOrNothing<T> {
let mut min = Nothing;
for e in v {
min = Something(match min {
Nothing => e,
- Something(n) => e.min(n)
+ // 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<i32>`, we implement the `Minimum` trait for `i32`.
+// To make `vec_min` usable with a `Vec<i32>`, we implement the `Minimum` trait for `i32`.
impl Minimum for i32 {
fn min(self, b: Self) -> Self {
- if self < b { self } else { b }
+ if self < b { self } else { b } /*@*/
}
}
-// We again provide a `print` function. This also shows that we can have multiple `impl` blocks
-// for the same type (remember that `NumberOrNothing` is just a type alias for `SomethingOrNothing<i32>`),
-// and we can provide some methods only for certain instances of a generic type.
+// We again provide a `print` function.
+//@ This also shows that we can have multiple `impl` blocks
+//@ for the same type (remember that `NumberOrNothing` is just a type alias for `SomethingOrNothing<i32>`),
+//@ and we can provide some methods only for certain instances of a generic type.
impl NumberOrNothing {
pub fn print(self) {
match self {
}
}
-// 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<i32> {
vec![18,5,7,3,9,27]
}
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<f32>` (where `f32` is the type
+// **Exercise 02.1**: Change your program such that it computes the minimum of a `Vec<f32>` (where `f32` is the type
// of 32-bit floating-point numbers). You should not change `vec_min` in any way, obviously!
-// [index](main.html) | [previous](part01.html) | [next](part03.html)
+//@ [index](main.html) | [previous](part01.html) | [next](part03.html)
// 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::<i32>::new()`), the common way to make sure we
-// get the right type is to annotate a type at the *variable*. It is this variable
-// that we interact with for the rest of the function, so having its type available
-// (and visible!) is much more useful. Without knowing the return type of `Vec::new`,
-// specifying its type parameter doesn't tell us all that much.
+//@ Let's now go over this function line-by-line. First, we call the constructor of `Vec`
+//@ to create an empty vector. As mentioned in the previous part, `new` here is just
+//@ a static function with no special treatment. While it is possible to call `new`
+//@ for a particular type (`Vec::<i32>::new()`), the common way to make sure we
+//@ get the right type is to annotate a type at the *variable*. It is this variable
+//@ that we interact with for the rest of the function, so having its type available
+//@ (and visible!) is much more useful. Without knowing the return type of `Vec::new`,
+//@ specifying its type parameter doesn't tell us all that much.
fn read_vec() -> Vec<i32> {
let mut vec: Vec<i32> = Vec::<i32>::new();
// The central handle to the standard input is made available by `io::stdin()`.
let stdin = io::stdin();
println!("Enter a list of numbers, one per line. End with Ctrl-D.");
- // We would now like to iterate over standard input line-by-line. We can use a `for` loop
- // for that, but there is a catch: What happens if there is some other piece of code running
- // concurrently, that also reads from standard input? The result would be a mess. Hence
- // Rust requires us to `lock()` standard input if we want to perform large operations on
- // it. (See [the documentation](http://doc.rust-lang.org/stable/std/io/struct.Stdin.html) for more
- // details.)
+ //@ We would now like to iterate over standard input line-by-line. We can use a `for` loop
+ //@ for that, but there is a catch: What happens if there is some other piece of code running
+ //@ concurrently, that also reads from standard input? The result would be a mess. Hence
+ //@ Rust requires us to `lock()` standard input if we want to perform large operations on
+ //@ it. (See [the documentation](http://doc.rust-lang.org/stable/std/io/struct.Stdin.html) for more
+ //@ details.)
for line in stdin.lock().lines() {
// Rust's type for (dynamic, growable) strings is `String`. However, our variable `line`
- // here is not yet of that type. The problem with I/O is that it can always go wrong, so
- // `line` has type `io::Result<String>`. This is a lot like `Option<String>` ("a `String` or
- // nothing"), but in the case of "nothing", there is additional information about the error.
- // Again, I recommend to check [the documentation](http://doc.rust-lang.org/stable/std/io/type.Result.html).
- // You will see that `io::Result` is actually just an alias for `Result`, so click on that to obtain
- // the list of all constructors and methods of the type.
+ // here is not yet of that type: It rather has type `io::Result<String>`.
+ //@ The problem with I/O is that it can always go wrong. The type of `line`is a lot like `Option<String>` ("a `String` or
+ //@ nothing"), but in the case of "nothing", there is additional information about the error.
+ //@ Again, I recommend to check [the documentation](http://doc.rust-lang.org/stable/std/io/type.Result.html).
+ //@ You will see that `io::Result` is actually just an alias for `Result`, so click on that to obtain
+ //@ the list of all constructors and methods of the type.
- // We will be lazy here and just assume that nothing goes wrong: `unwrap()` returns the `String` if there is one,
- // and panics the program otherwise. Since a `Result` carries some details about the error that occurred,
- // there will be a somewhat reasonable error message. Still, you would not want a user to see such
- // an error, so in a "real" program, we would have to do proper error handling.
- // Can you find the documentation of `Result::unwrap()`?
- //
+ //@ 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::<i32>` 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::<i32>` is `parse` with its generic type set to `i32`.
match line.parse::<i32>() {
- // `parse` returns again a `Result`, and this time we use a `match` to handle errors (like, the user entering
- // something that is not a number).
- // This is a common pattern in Rust: Operations that could go wrong will return `Option` or `Result`.
- // The only way to get to the value we are interested in is through pattern matching (and through helper functions
- // like `unwrap()`). If we call a function that returns a `Result`, and throw the return value away,
- // the compiler will emit a warning. It is hence impossible for us to *forget* handling an error,
- // or to accidentally use a value that doesn't make any sense because there was an error producing it.
- Ok(num) => vec.push(num),
+ //@ `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`.
// **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)
// 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<int> v) {
int *first = &v[0];
*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<i32>) { /* do something */ }
fn ownership_demo() {
let v = vec![1,2,3,4];
work_on_vector(v);
/* println!("The first element is: {}", v[0]); */
}
-// Rust attaches additional meaning to the argument of `work_on_vector`: The function can assume
-// that it entirely *owns* `v`, and hence can do anything with it. When `work_on_vector` ends,
-// nobody needs `v` anymore, so it will be deleted (including its buffer on the heap).
-// Passing a `Vec<i32>` to `work_on_vector` is considered *transfer of ownership*: Someone used
-// to own that vector, but now he gave it on to `take` and has no business with it anymore.
-//
-// If you give a book to your friend, you cannot just come to his place next day and get the book!
-// It's no longer yours. Rust makes sure you don't break this rule. Try enabling the commented
-// line in `ownership_demo`. Rust will tell you that `v` has been *moved*, which is to say that ownership
-// has been transferred somewhere else. In this particular case, the buffer storing the data
-// does not even exist anymore, so we are lucky that Rust caught this problem!
-// Essentially, ownership rules out aliasing, hence making the kind of problem discussed above
-// impossible.
+//@ Rust attaches additional meaning to the argument of `work_on_vector`: The function can assume
+//@ that it entirely *owns* `v`, and hence can do anything with it. When `work_on_vector` ends,
+//@ nobody needs `v` anymore, so it will be deleted (including its buffer on the heap).
+//@ Passing a `Vec<i32>` to `work_on_vector` is considered *transfer of ownership*: Someone used
+//@ to own that vector, but now he gave it on to `take` and has no business with it anymore.
+//@
+//@ If you give a book to your friend, you cannot just come to his place next day and get the book!
+//@ It's no longer yours. Rust makes sure you don't break this rule. Try enabling the commented
+//@ line in `ownership_demo`. Rust will tell you that `v` has been *moved*, which is to say that ownership
+//@ has been transferred somewhere else. In this particular case, the buffer storing the data
+//@ does not even exist anymore, so we are lucky that Rust caught this problem!
+//@ Essentially, ownership rules out aliasing, hence making the kind of problem discussed above
+//@ impossible.
// ## Shared borrowing
-// If you go back to our example with `vec_min`, and try to call that function twice, you will
-// get the same error. That's because `vec_min` demands that the caller transfers ownership of the
-// vector. Hence, when `vec_min` finishes, the entire vector is deleted. That's of course not what
-// we wanted! Can't we somehow give `vec_min` access to the vector, while retaining ownership of it?
-//
-// Rust calls this *borrowing* the vector, and it works a bit like borrowing does in the real world:
-// If you borrow a book to your friend, your friend can have it and work on it (and you can't!)
-// as long as the book is still borrowed. Your friend could even borrow the book to someone else.
-// Eventually however, your friend has to give the book back to you, at which point you again
-// have full control.
-//
-// Rust distinguishes between two kinds of borrows. First of all, there's the *shared* borrow.
-// This is where the book metaphor kind of breaks down... you can give a shared borrow of
-// *the same data* to lots of different people, who can all access the data. This of course
-// introduces aliasing, so in order to live up to its promise of safety, Rust does not allow
-// mutation through a shared borrow.
+//@ If you go back to our example with `vec_min`, and try to call that function twice, you will
+//@ get the same error. That's because `vec_min` demands that the caller transfers ownership of the
+//@ vector. Hence, when `vec_min` finishes, the entire vector is deleted. That's of course not what
+//@ we wanted! Can't we somehow give `vec_min` access to the vector, while retaining ownership of it?
+//@
+//@ Rust calls this *borrowing* the vector, and it works a bit like borrowing does in the real world:
+//@ If you borrow a book to your friend, your friend can have it and work on it (and you can't!)
+//@ as long as the book is still borrowed. Your friend could even borrow the book to someone else.
+//@ Eventually however, your friend has to give the book back to you, at which point you again
+//@ have full control.
+//@
+//@ Rust distinguishes between two kinds of borrows. First of all, there's the *shared* borrow.
+//@ This is where the book metaphor kind of breaks down... you can give a shared borrow of
+//@ *the same data* to lots of different people, who can all access the data. This of course
+//@ introduces aliasing, so in order to live up to its promise of safety, Rust does not allow
+//@ mutation through a shared borrow.
-// So, let's re-write `vec_min` to work on a shared borrow of a vector, written `&Vec<i32>`.
-// I also took the liberty to convert the function from `SomethingOrNothing` to the standard
-// library type `Option`.
+//@ So, let's re-write `vec_min` to work on a shared borrow of a vector, written `&Vec<i32>`.
+//@ I also took the liberty to convert the function from `SomethingOrNothing` to the standard
+//@ library type `Option`.
fn vec_min(v: &Vec<i32>) -> Option<i32> {
use std::cmp;
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<i32>` is the type of mutable borrows of `vec<i32>`. 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<i32>` is the type of mutable borrows of `vec<i32>`. Because the borrow is
+//@ mutable, we can change `e` in the loop.
fn vec_inc(v: &mut Vec<i32>) {
for e in v {
*e += 1;
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:
// 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)
// ========================
// ## Big Numbers
-// In the course of the next few parts, we are going to build a data-structure for computations with
-// *big* numbers. We would like to not have an upper bound to how large these numbers can get, with
-// the memory of the machine being the only limit.
-//
-// We start by deciding how to represent such big numbers. One possibility here is
-// to use a vector "digits" of the number. This is like "1337" being a vector of four digits (1, 3, 3, 7),
-// except that we will use `u64` as type of our digits, meaning we have 2^64 individual digits. Now we just
-// have to decide the order in which we store numbers. I decided that we will store the least significant
-// digit first. This means that "1337" would actually become (7, 3, 3, 1).<br/>
-// Finally, we declare that there must not be any trailing zeros (corresponding to
-// useless leading zeros in our usual way of writing numbers). This is to ensure that
-// the same number can only be stored in one way.
+//@ In the course of the next few parts, we are going to build a data-structure for computations with
+//@ *big* numbers. We would like to not have an upper bound to how large these numbers can get, with
+//@ the memory of the machine being the only limit.
+//@
+//@ We start by deciding how to represent such big numbers. One possibility here is
+//@ to use a vector "digits" of the number. This is like "1337" being a vector of four digits (1, 3, 3, 7),
+//@ except that we will use `u64` as type of our digits, meaning we have 2^64 individual digits. Now we just
+//@ have to decide the order in which we store numbers. I decided that we will store the least significant
+//@ digit first. This means that "1337" would actually become (7, 3, 3, 1).<br/>
+//@ Finally, we declare that there must not be any trailing zeros (corresponding to
+//@ useless leading zeros in our usual way of writing numbers). This is to ensure that
+//@ the same number can only be stored in one way.
-// To write this down in Rust, we use a `struct`, which is a lot like structs in C:
-// Just a bunch of named fields. Every field can be private to the current module (which is the default),
-// or public (which is indicated by a `pub` in front of the name). For the sake of the tutorial, we make
-// `data` public - otherwise, the next parts of this course could not work on `BigInt`s. Of course, in a
-// real program, one would make the field private to ensure that the invariant (no trailing zeros) is maintained.
+//@ To write this down in Rust, we use a `struct`, which is a lot like structs in C:
+//@ Just a bunch of named fields. Every field can be private to the current module (which is the default),
+//@ or public (which is indicated by a `pub` in front of the name). For the sake of the tutorial, we make
+//@ `data` public - otherwise, the next parts of this course could not work on `BigInt`s. Of course, in a
+//@ real program, one would make the field private to ensure that the invariant (no trailing zeros) is maintained.
pub struct BigInt {
pub data: Vec<u64>,
}
// Now that we fixed the data representation, we can start implementing methods on it.
impl BigInt {
- // Let's start with a constructor, creating a `BigInt` from an ordinary integer.
- // To create an instance of a struct, we write its name followed by a list of
- // fields and initial values assigned to them.
+ //@ 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 /*@*/
}
}
}
// ## 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<T>` implement `Clone`. However, that
-// can only work if `T` is `Clone`! So we have to add this bound to `T` when we introduce
-// the type variable.
+// We can also make the type `SomethingOrNothing<T>` implement `Clone`.
+//@ However, that can only work if `T` is `Clone`! So we have to add this bound to `T` when we introduce
+//@ the type variable.
use part02::{SomethingOrNothing,Something,Nothing};
impl<T: Clone> Clone for SomethingOrNothing<T> {
fn clone(&self) -> Self {
- match *self {
- Nothing => Nothing,
- // In the second arm of the match, we need to talk about the value `v`
- // that's stored in `self`. However, if we would write the pattern as
- // `Something(v)`, that would indicate that we *own* `v` in the code
- // after the arrow. That can't work though, we have to leave `v` owned by
- // whoever called us - after all, we don't even own `self`, we just borrowed it.
- // By writing `Something(ref v)`, we borrow `v` for the duration of the match
- // arm. That's good enough for cloning it.
- Something(ref v) => Something(v.clone()),
- }
+ 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 {
/* 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)
// 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.
fn vec_min(v: &Vec<BigInt>) -> Option<BigInt> {
let mut min: Option<BigInt> = None;
for e in v {
- let e = e.clone();
- min = Some(match min {
- None => e,
- Some(n) => e.min_try1(n)
- });
+ let e = e.clone(); /*@*/
+ min = Some(match min { /*@*/
+ None => e, /*@*/
+ Some(n) => e.min_try1(n) /*@*/
+ }); /*@*/
}
min
}
-// Now, what's happening here? Why do we have to clone `e`, and why did we not
-// have to do that in our previous version?
-//
-// The answer is already hidden in the type of `vec_min`: `v` is just borrowed, but
-// the Option<BigInt> that it returns is *owned*. We can't just return one of the elements of `v`,
-// as that would mean that it is no longer in the vector! In our code, this comes up when we update
-// the intermediate variable `min`, which also has type `Option<BigInt>`. If you replace get rid of the
-// `e.clone()`, Rust will complain "Cannot move out of borrowed content". That's because
-// `e` is a `&BigInt`. Assigning `min = Some(*e)` works just like a function call: Ownership of the
-// underlying data is transferred from where `e` borrows from to `min`. But that's not allowed, since
-// we just borrowed `e`, so we cannot empty it! We can, however, call `clone()` on it. Then we own
-// the copy that was created, and hence we can store it in `min`.<br/>
-// Of course, making such a full copy is expensive, so we'd like to avoid it. We'll some to that in the next part.
+//@ Now, what's happening here? Why do we have to clone `e`, and why did we not
+//@ have to do that in our previous version?
+//@
+//@ The answer is already hidden in the type of `vec_min`: `v` is just borrowed, but
+//@ the Option<BigInt> that it returns is *owned*. We can't just return one of the elements of `v`,
+//@ as that would mean that it is no longer in the vector! In our code, this comes up when we update
+//@ the intermediate variable `min`, which also has type `Option<BigInt>`. If you replace get rid of the
+//@ `e.clone()`, Rust will complain "Cannot move out of borrowed content". That's because
+//@ `e` is a `&BigInt`. Assigning `min = Some(*e)` works just like a function call: Ownership of the
+//@ underlying data is transferred from where `e` borrows from to `min`. But that's not allowed, since
+//@ we just borrowed `e`, so we cannot empty it! We can, however, call `clone()` on it. Then we own
+//@ the copy that was created, and hence we can store it in `min`.<br/>
+//@ Of course, making such a full copy is expensive, so we'd like to avoid it. We'll some to that in the next part.
// ## `Copy` types
-// But before we go there, I should answer the second question I brought up above: Why did our old `vec_min` work?
-// We stored the minimal `i32` locally without cloning, and Rust did not complain. That's because there isn't
-// really much of an "ownership" when it comes to types like `i32` or `bool`: If you move the value from one
-// place to another, then both instances are "complete". We also say the value has been *duplicated*. This is in
-// stark contrast to types like `Vec<i32>`, where moving the value results in both the old and the new vector to
-// point to the same underlying buffer. We don't have two vectors, there's no proper duplication.
-//
-// Rust calls types that can be easily duplicated `Copy` types. `Copy` is another trait, and it is implemented for
-// types like `i32` and `bool`. Remember how we defined the trait `Minimum` by writing `trait Minimum : Copy { ...`?
-// This tells Rust that every type that implements `Minimum` must also implement `Copy`, and that's why the compiler
-// accepted our generic `vec_min` in part 02. `Copy` is the first *marker trait* that we encounter: It does not provide
-// any methods, but makes a promise about the behavior of the type - in this case, being duplicable.
+//@ But before we go there, I should answer the second question I brought up above: Why did our old `vec_min` work?
+//@ We stored the minimal `i32` locally without cloning, and Rust did not complain. That's because there isn't
+//@ really much of an "ownership" when it comes to types like `i32` or `bool`: If you move the value from one
+//@ place to another, then both instances are "complete". We also say the value has been *duplicated*. This is in
+//@ stark contrast to types like `Vec<i32>`, where moving the value results in both the old and the new vector to
+//@ point to the same underlying buffer. We don't have two vectors, there's no proper duplication.
+//@
+//@ Rust calls types that can be easily duplicated `Copy` types. `Copy` is another trait, and it is implemented for
+//@ types like `i32` and `bool`. Remember how we defined the trait `Minimum` by writing `trait Minimum : Copy { ...`?
+//@ This tells Rust that every type that implements `Minimum` must also implement `Copy`, and that's why the compiler
+//@ accepted our generic `vec_min` in part 02. `Copy` is the first *marker trait* that we encounter: It does not provide
+//@ any methods, but makes a promise about the behavior of the type - in this case, being duplicable.
-// If you try to implement `Copy` for `BigInt`, you will notice that Rust
-// does not let you do that. A type can only be `Copy` if all its elements
-// are `Copy`, and that's not the case for `BigInt`. However, we can make
-// `SomethingOrNothing<T>` copy if `T` is `Copy`.
+//@ If you try to implement `Copy` for `BigInt`, you will notice that Rust
+//@ does not let you do that. A type can only be `Copy` if all its elements
+//@ are `Copy`, and that's not the case for `BigInt`. However, we can make
+//@ `SomethingOrNothing<T>` copy if `T` is `Copy`.
use part02::{SomethingOrNothing,Something,Nothing};
impl<T: Copy> Copy for SomethingOrNothing<T> {}
-// Again, Rust can generate implementations of `Copy` automatically. If
-// you add `#[derive(Copy,Clone)]` right before the definition of `SomethingOrNothing`,
-// both `Copy` and `Clone` will automatically be implemented.
+//@ Again, Rust can generate implementations of `Copy` automatically. If
+//@ you add `#[derive(Copy,Clone)]` right before the definition of `SomethingOrNothing`,
+//@ both `Copy` and `Clone` will automatically be implemented.
-// ## An operational perspective
-// Instead of looking at what happens "at the surface" (i.e., visible in Rust), one can also explain
-// ownership passing and how `Copy` and `Clone` fit in by looking at what happens on the machine.<br/>
-// When Rust code is executed, passing a value (like `i32` or `Vec<i32>`) to a function will always
-// result in a shallow copy being performed: Rust just copies the bytes representing that value, and
-// considers itself done. That's just like the default copy constructor in C++. Rust, however, will
-// consider this a destructive operation: After copying the bytes elsewhere, the original value must
-// no longer be used. After all, the two could now share a pointer! If, however, you mark a type `Copy`,
-// then Rust will *not* consider a move destructive, and just like in C++, the old and new value
-// can happily coexist. Now, Rust does not allow you to overload the copy constructor. This means that
-// passing a value around will always be a fast operation, no allocation or any other kind of heap access
-// will happen. In the situations where you would write a copy constructor in C++ (and hence
-// incur a hidden cost on every copy of this type), you'd have the type *not* implement `Copy`, but only
-// `Clone`. This makes the cost explicit.
+//@ ## An operational perspective
+//@ Instead of looking at what happens "at the surface" (i.e., visible in Rust), one can also explain
+//@ ownership passing and how `Copy` and `Clone` fit in by looking at what happens on the machine.<br/>
+//@ When Rust code is executed, passing a value (like `i32` or `Vec<i32>`) to a function will always
+//@ result in a shallow copy being performed: Rust just copies the bytes representing that value, and
+//@ considers itself done. That's just like the default copy constructor in C++. Rust, however, will
+//@ consider this a destructive operation: After copying the bytes elsewhere, the original value must
+//@ no longer be used. After all, the two could now share a pointer! If, however, you mark a type `Copy`,
+//@ then Rust will *not* consider a move destructive, and just like in C++, the old and new value
+//@ can happily coexist. Now, Rust does not allow you to overload the copy constructor. This means that
+//@ passing a value around will always be a fast operation, no allocation or any other kind of heap access
+//@ will happen. In the situations where you would write a copy constructor in C++ (and hence
+//@ incur a hidden cost on every copy of this type), you'd have the type *not* implement `Copy`, but only
+//@ `Clone`. This makes the cost explicit.
// ## Lifetimes
-// To fix the performance problems of `vec_min`, we need to avoid using `clone()`. We'd like
-// the return value to not be owned (remember that this was the source of our need for cloning), but *borrowed*.
+//@ 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<T>(v: &Vec<T>) -> Option<&T> {
if v.len() > 0 {
- Some(&v[0])
+ Some(&v[0]) /*@*/
} else {
None
}
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>) -> i32 {
let first: Option<&i32> = head(&v);
/* v.push(42); */
*first.unwrap()
}
-// To give the answer to this question, we have to talk about the *lifetime* of a borrow. The point is, saying that
-// you borrowed your friend a `Vec<i32>`, or a book, is not good enough, unless you also agree on *how long*
-// your friend can borrow it. After all, you need to know when you can rely on owning your data (or book) again.
-//
-// Every borrow in Rust has an associated lifetime, written `&'a T` for a borrow of type `T` with lifetime `'a`. The full
-// type of `head` reads as follows: `fn<'a, T>(&'a Vec<T>) -> Option<&'a T>`. Here, `'a` is a *lifetime variable*, which
-// represents how long the vector has been borrowed. The function type expresses that argument and return value have *the same lifetime*.
-//
-// When analyzing the code of `rust_foo`, Rust has to assign a lifetime to `first`. It will choose the scope
-// where `first` is valid, which is the entire rest of the function. Because `head` ties the lifetime of its
-// argument and return value together, this means that `&v` also has to borrow `v` for the entire duration of
-// the function. So when we try to borrow `v` mutable for `push`, Rust complains that the two borrows (the one
-// for `head`, and the one for `push`) overlap. Lucky us! Rust caught our mistake and made sure we don't crash the program.
-//
-// So, to sum this up: Lifetimes enable Rust to reason about *how long* a pointer has been borrowed. We can thus
-// safely write functions like `head`, that return pointers into data they got as argument, and make sure they
-// are used correctly, *while looking only at the function type*. At no point in our analysis of `rust_foo` did
-// we have to look *into* `head`. That's, of course, crucial if we want to separate library code from application code.
-// Most of the time, we don't have to explicitly add lifetimes to function types. This is thanks to *lifetimes elision*,
-// where Rust will automatically insert lifetimes we did not specify, following some [simple, well-documented rules](http://doc.rust-lang.org/stable/book/lifetimes.html#lifetime-elision).
+//@ To give the answer to this question, we have to talk about the *lifetime* of a borrow. The point is, saying that
+//@ you borrowed your friend a `Vec<i32>`, or a book, is not good enough, unless you also agree on *how long*
+//@ your friend can borrow it. After all, you need to know when you can rely on owning your data (or book) again.
+//@
+//@ Every borrow in Rust has an associated lifetime, written `&'a T` for a borrow of type `T` with lifetime `'a`. The full
+//@ type of `head` reads as follows: `fn<'a, T>(&'a Vec<T>) -> Option<&'a T>`. Here, `'a` is a *lifetime variable*, which
+//@ represents how long the vector has been borrowed. The function type expresses that argument and return value have *the same lifetime*.
+//@
+//@ When analyzing the code of `rust_foo`, Rust has to assign a lifetime to `first`. It will choose the scope
+//@ where `first` is valid, which is the entire rest of the function. Because `head` ties the lifetime of its
+//@ argument and return value together, this means that `&v` also has to borrow `v` for the entire duration of
+//@ the function. So when we try to borrow `v` mutable for `push`, Rust complains that the two borrows (the one
+//@ for `head`, and the one for `push`) overlap. Lucky us! Rust caught our mistake and made sure we don't crash the program.
+//@
+//@ So, to sum this up: Lifetimes enable Rust to reason about *how long* a pointer has been borrowed. We can thus
+//@ safely write functions like `head`, that return pointers into data they got as argument, and make sure they
+//@ are used correctly, *while looking only at the function type*. At no point in our analysis of `rust_foo` did
+//@ we have to look *into* `head`. That's, of course, crucial if we want to separate library code from application code.
+//@ Most of the time, we don't have to explicitly add lifetimes to function types. This is thanks to *lifetimes elision*,
+//@ where Rust will automatically insert lifetimes we did not specify, following some [simple, well-documented rules](http://doc.rust-lang.org/stable/book/lifetimes.html#lifetime-elision).
-// [index](main.html) | [previous](part05.html) | [next](part07.html)
+//@ [index](main.html) | [previous](part05.html) | [next](part07.html)
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<T: Minimum>(v: &Vec<T>) -> Option<&T> {
let mut min: Option<&T> = None;
for e in v {
- min = Some(match min {
- None => e,
- Some(n) => n.min(e)
- });
+ min = Some(match min { /*@*/
+ None => e, /*@*/
+ Some(n) => n.min(e) /*@*/
+ }); /*@*/
}
min
}
-// Notice that the return type `Option<&T>` is technically (leaving the borrowing story aside) a
-// pointer to a `T`, that could optionally be invalid. In other words, it's just like a pointer in
-// C(++) or Java that can be `NULL`! However, thanks to `Option` being an `enum`, we cannot forget
-// to check the pointer for validity, avoiding the safety issues of C(++).<br/>
-// Also, if you are worried about wasting space, notice that Rust knows that `&T` can never be
-// `NULL`, and hence optimizes `Option<&T>` to be no larger than `&T`. The `None` case is represented
-// as `NULL`. This is another great example of a zero-cost abstraction: `Option<&T>` is exactly like
-// a pointer in C(++), if you look at what happens during execution - but it's much safer to use.
+//@ Notice that the return type `Option<&T>` is technically (leaving the borrowing story aside) a
+//@ pointer to a `T`, that could optionally be invalid. In other words, it's just like a pointer in
+//@ C(++) or Java that can be `NULL`! However, thanks to `Option` being an `enum`, we cannot forget
+//@ to check the pointer for validity, avoiding the safety issues of C(++).<br/>
+//@ Also, if you are worried about wasting space, notice that Rust knows that `&T` can never be
+//@ `NULL`, and hence optimizes `Option<&T>` to be no larger than `&T`. The `None` case is represented
+//@ as `NULL`. This is another great example of a zero-cost abstraction: `Option<&T>` is exactly like
+//@ a pointer in C(++), if you look at what happens during execution - but it's much safer to use.
// **Exercise 07.1**: For our `vec_min` to be usable with `BigInt`, you will have to provide an implementation of
// `Minimum`. You should be able to pretty much copy the code you wrote for exercise 06.1. You should *not*
}
// ## 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);
}
// ## 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<u64>`.
+//@ In the case of `BigInt`, we'd like to just output our internal `data` array, so we
+//@ simply call the formating function of `Vec<u64>`.
impl fmt::Debug for BigInt {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.data.fmt(f)
}
}
-// `Debug` implementations can be automatically generated using the `derive(Debug)` attribute.
+//@ `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);
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
// of course, need a `Display` bound on `T`.) Then you should be able to use them with `println!` just like you do
// with numbers, and get rid of the inherent functions to print `SomethingOrNothing<i32>` and `SomethingOrNothing<f32>`.
-// [index](main.html) | [previous](part06.html) | [next](main.html)
+//@ [index](main.html) | [previous](part06.html) | [next](main.html)
-// Rust-101, Part 08: Associated Types, Modules
-// ============================================
+// Rust-101, Part 08: Associated Types, Modules (WIP)
+// ==================================================
use std::cmp;
use std::ops;
-// Rust-101, Part 09: Iterators
-// ============================
+// Rust-101, Part 09: Iterators (WIP)
+// =================================
// [index](main.html) | [previous](part08.html) | [next](main.html)
// 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!()
// **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)
// Rust-101, Part 02: Generic types, Traits
// ========================================
-// Let us for a moment reconsider the type `NumberOrNothing`. Isn't it a bit annoying that we
-// had to hard-code the type `i32` in there? What if tomorrow, we want a `CharOrNothing`, and
-// later a `FloatOrNothing`? Certainly we don't want to re-write the type and all its inherent methods.
// ## Generic datatypes
-// The solution to this is called *generics* or *polymorphism* (the latter is Greek,
-// meaning "many shapes"). You may know something similar from C++ (where it's called
-// *templates*) or Java, or one of the many functional languages. So here, we define
-// a generic type `SomethingOrNothing`.
pub enum SomethingOrNothing<T> {
Something(T),
Nothing,
}
// Instead of writing out all the variants, we can also just import them all at once.
pub use self::SomethingOrNothing::*;
-// What this does is to define an entire family of types: We can now write
-// `SomethingOrNothing<i32>` to get back our `NumberOrNothing`.
type NumberOrNothing = SomethingOrNothing<i32>;
-// However, we can also write `SomethingOrNothing<bool>` or even `SomethingOrNothing<SomethingOrNothing<i32>>`.
-// In fact, such a type is so useful that it is already present in the standard library: It's called an
-// *option type*, written `Option<T>`. Go check out its [documentation](http://doc.rust-lang.org/stable/std/option/index.html)!
-// (And don't worry, there's indeed lots of material mentioned there that we did not cover yet.)
// ## Generic `impl`, Static functions
-// The types are so similar, that we can provide a generic function to construct a `SomethingOrNothing<T>`
-// from an `Option<T>`, and vice versa.
-// **Exercise 02.1**: Implement such functions! I provided a skeleton of the solution. Here,
-// `unimplemented!` is another macro. This one terminates execution saying that something has not yet
-// been implemented.
-//
-// Notice the syntax for giving generic implementations to generic types: Think of the first `<T>`
-// as *declaring* a type variable ("I am doing something for all types `T`"), and the second `<T>` as
-// *using* that variable ("The thing I do, is implement `SomethingOrNothing<T>`").
-//
// Inside an `impl`, `Self` refers to the type we are implementing things for. Here, it is
// an alias for `SomethingOrNothing<T>`.
-// Remember that `self` is the `this` of Rust, and implicitly has type `Self`.
impl<T> SomethingOrNothing<T> {
fn new(o: Option<T>) -> Self {
unimplemented!()
unimplemented!()
}
}
-// Observe how `new` does *not* have a `self` parameter. This corresponds to a `static` method
-// in Java or C++. In fact, `new` is the Rust convention for defining constructors: They are
-// nothing special, just static functions returning `Self`.
-//
// You can call static functions, and in particular constructors, as demonstrated in `call_constructor`.
fn call_constructor(x: i32) -> SomethingOrNothing<i32> {
SomethingOrNothing::new(Some(x))
}
// ## Traits
-// Now that we have a generic `SomethingOrNothing`, wouldn't it be nice to also gave a generic
-// `vec_min`? Of course, we can't take the minimum of a vector of *any* type. It has to be a type
-// supporting a `min` operation. Rust calls such properties that we may demand of types *traits*.
-// So, as a first step towards a generic `vec_min`, we define a `Minimum` trait.
-// For now, just ignore the `Copy`, we will come back to this point later.
-// A `trait` is a lot like interfaces in Java: You define a bunch of functions
-// you want to have implemented, and their argument and return types.<br/>
-// The function `min` takes to arguments of the same type, but I made the
-// first argument the special `self` argument. I could, alternatively, have
-// made `min` a static function as follows: `fn min(a: Self, b: Self) -> Self`.
-// However, in Rust one typically prefers methods over static function wherever possible.
pub trait Minimum : Copy {
fn min(self, b: Self) -> Self;
}
-// Next, we write `vec_min` as a generic function over a type `T` that we demand to satisfy the `Minimum` trait.
-// This requirement is called a *trait bound*.
-// The only difference to the version from the previous part is that we call `e.min(n)` instead
-// of `std::cmp::min(n, e)`. Rust automatically figures out that `n` is of type `T`, which implements
-// the `Minimum` trait, and hence we can call that function.
-//
-// There is a crucial difference to templates in C++: We actually have to declare which traits
-// we want the type to satisfy. If we left away the `Minimum`, Rust would have complained that
-// we cannot call `min`. Just try it!<br/>
-// This is in strong contrast to C++, where the compiler only checks such details when the
-// function is actually used.
pub fn vec_min<T: Minimum>(v: Vec<T>) -> SomethingOrNothing<T> {
let mut min = Nothing;
for e in v {
min = Something(match min {
Nothing => e,
- Something(n) => e.min(n)
+ // 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<i32>`, we implement the `Minimum` trait for `i32`.
+// To make `vec_min` usable with a `Vec<i32>`, we implement the `Minimum` trait for `i32`.
impl Minimum for i32 {
fn min(self, b: Self) -> Self {
- if self < b { self } else { b }
+ 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<i32>`),
-// 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 {
}
}
-// 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<i32> {
vec![18,5,7,3,9,27]
}
min.print();
}
-// If this printed `3`, then you generic `vec_min` is working! So get ready for the next part.
-// **Exercise 02.2**: Change your program such that it computes the minimum of a `Vec<f32>` (where `f32` is the type
+// **Exercise 02.1**: Change your program such that it computes the minimum of a `Vec<f32>` (where `f32` is the type
// of 32-bit floating-point numbers). You should not change `vec_min` in any way, obviously!
-// [index](main.html) | [previous](part01.html) | [next](part03.html)
// 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::<i32>::new()`), the common way to make sure we
-// get the right type is to annotate a type at the *variable*. It is this variable
-// that we interact with for the rest of the function, so having its type available
-// (and visible!) is much more useful. Without knowing the return type of `Vec::new`,
-// specifying its type parameter doesn't tell us all that much.
fn read_vec() -> Vec<i32> {
let mut vec: Vec<i32> = Vec::<i32>::new();
// The central handle to the standard input is made available by `io::stdin()`.
let stdin = io::stdin();
println!("Enter a list of numbers, one per line. End with Ctrl-D.");
- // We would now like to iterate over standard input line-by-line. We can use a `for` loop
- // for that, but there is a catch: What happens if there is some other piece of code running
- // concurrently, that also reads from standard input? The result would be a mess. Hence
- // Rust requires us to `lock()` standard input if we want to perform large operations on
- // it. (See [the documentation](http://doc.rust-lang.org/stable/std/io/struct.Stdin.html) for more
- // details.)
for line in stdin.lock().lines() {
// Rust's type for (dynamic, growable) strings is `String`. However, our variable `line`
- // here is not yet of that type. The problem with I/O is that it can always go wrong, so
- // `line` has type `io::Result<String>`. This is a lot like `Option<String>` ("a `String` or
- // nothing"), but in the case of "nothing", there is additional information about the error.
- // Again, I recommend to check [the documentation](http://doc.rust-lang.org/stable/std/io/type.Result.html).
- // You will see that `io::Result` is actually just an alias for `Result`, so click on that to obtain
- // the list of all constructors and methods of the type.
+ // here is not yet of that type: It rather has type `io::Result<String>`.
- // 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::<i32>` is `parse` with its generic type set to `i32`.
match line.parse::<i32>() {
- // `parse` returns again a `Result`, and this time we use a `match` to handle errors (like, the user entering
- // something that is not a number).
- // This is a common pattern in Rust: Operations that could go wrong will return `Option` or `Result`.
- // The only way to get to the value we are interested in is through pattern matching (and through helper functions
- // like `unwrap()`). If we call a function that returns a `Result`, and throw the return value away,
- // the compiler will emit a warning. It is hence impossible for us to *forget* handling an error,
- // or to accidentally use a value that doesn't make any sense because there was an error producing it.
- Ok(num) => vec.push(num),
+ 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`.
// **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)
// Rust-101, Part 04: Ownership, Borrowing
// =======================================
-// Rust aims to be a "safe systems language". As a systems language, of course it
-// provides *references* (or *pointers*). But as a safe language, it has to
-// prevent bugs like this C++ snippet.
/*
void foo(std::vector<int> v) {
int *first = &v[0];
*first = 1337; // This is bad!
}
*/
-// What's going wrong here? `first` is a pointer into the vector `v`. The operation `push_back`
-// may re-allocate the storage for the vector, in case the old buffer was full. If that happens,
-// `first` is now a dangling pointer, and accessing it can crash the program (or worse).
-//
-// It turns out that only the combination of two circumstances can lead to such a bug:
-// *aliasing* and *mutation*. In the code above, we have `first` and the buffer of `v`
-// being aliases, and when `push_back` is called, the latter is used to perform a mutation.
-// Therefore, the central principle of the Rust typesystem is to *rule out mutation in the presence
-// of aliasing*. The core tool to achieve that is the notion of *ownership*.
// ## Ownership
-// What does that mean in practice? Consider the following example.
fn work_on_vector(v: Vec<i32>) { /* do something */ }
fn ownership_demo() {
let v = vec![1,2,3,4];
work_on_vector(v);
/* println!("The first element is: {}", v[0]); */
}
-// Rust attaches additional meaning to the argument of `work_on_vector`: The function can assume
-// that it entirely *owns* `v`, and hence can do anything with it. When `work_on_vector` ends,
-// nobody needs `v` anymore, so it will be deleted (including its buffer on the heap).
-// Passing a `Vec<i32>` to `work_on_vector` is considered *transfer of ownership*: Someone used
-// to own that vector, but now he gave it on to `take` and has no business with it anymore.
-//
-// If you give a book to your friend, you cannot just come to his place next day and get the book!
-// It's no longer yours. Rust makes sure you don't break this rule. Try enabling the commented
-// line in `ownership_demo`. Rust will tell you that `v` has been *moved*, which is to say that ownership
-// has been transferred somewhere else. In this particular case, the buffer storing the data
-// does not even exist anymore, so we are lucky that Rust caught this problem!
-// Essentially, ownership rules out aliasing, hence making the kind of problem discussed above
-// impossible.
// ## Shared borrowing
-// If you go back to our example with `vec_min`, and try to call that function twice, you will
-// get the same error. That's because `vec_min` demands that the caller transfers ownership of the
-// vector. Hence, when `vec_min` finishes, the entire vector is deleted. That's of course not what
-// we wanted! Can't we somehow give `vec_min` access to the vector, while retaining ownership of it?
-//
-// Rust calls this *borrowing* the vector, and it works a bit like borrowing does in the real world:
-// If you borrow a book to your friend, your friend can have it and work on it (and you can't!)
-// as long as the book is still borrowed. Your friend could even borrow the book to someone else.
-// Eventually however, your friend has to give the book back to you, at which point you again
-// have full control.
-//
-// Rust distinguishes between two kinds of borrows. First of all, there's the *shared* borrow.
-// This is where the book metaphor kind of breaks down... you can give a shared borrow of
-// *the same data* to lots of different people, who can all access the data. This of course
-// introduces aliasing, so in order to live up to its promise of safety, Rust does not allow
-// mutation through a shared borrow.
-// So, let's re-write `vec_min` to work on a shared borrow of a vector, written `&Vec<i32>`.
-// I also took the liberty to convert the function from `SomethingOrNothing` to the standard
-// library type `Option`.
fn vec_min(v: &Vec<i32>) -> Option<i32> {
use std::cmp;
vec_min(&v);
println!("The first element is: {}", *first);
}
-// What's going on here? First, `&` is how you create a shared borrow to something. All borrows are created like
-// this - there is no way to have something like a NULL pointer. This code creates three shared borrows to `v`:
-// The borrow for `first` begins in the 2nd line of the function and lasts all the way to the end. The other two
-// borrows, created for calling `vec_min`, only last for the duration of that respective call.
-//
-// Technically, of course, borrows are pointers. Notice that since `vec_min` only gets a shared
-// borrow, Rust knows that it cannot mutate `v` in any way. Hence the pointer into the buffer of `v`
-// that was created before calling `vec_min` remains valid.
// ## Mutable borrowing
-// There is a second kind of borrow, a *mutable borrow*. As the name suggests, such a borrow permits
-// mutation, and hence has to prevent aliasing. There can only ever be one mutable borrow to a
-// particular piece of data.
-// As an example, consider a function which increments every element of a vector by 1.
-// The type `&mut Vec<i32>` is the type of mutable borrows of `vec<i32>`. Because the borrow is
-// mutable, we can change `e` in the loop.
fn vec_inc(v: &mut Vec<i32>) {
for e in v {
*e += 1;
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:
// 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)
// ========================
// ## Big Numbers
-// In the course of the next few parts, we are going to build a data-structure for computations with
-// *big* numbers. We would like to not have an upper bound to how large these numbers can get, with
-// the memory of the machine being the only limit.
-//
-// We start by deciding how to represent such big numbers. One possibility here is
-// to use a vector "digits" of the number. This is like "1337" being a vector of four digits (1, 3, 3, 7),
-// except that we will use `u64` as type of our digits, meaning we have 2^64 individual digits. Now we just
-// have to decide the order in which we store numbers. I decided that we will store the least significant
-// digit first. This means that "1337" would actually become (7, 3, 3, 1).<br/>
-// Finally, we declare that there must not be any trailing zeros (corresponding to
-// useless leading zeros in our usual way of writing numbers). This is to ensure that
-// the same number can only be stored in one way.
-// To write this down in Rust, we use a `struct`, which is a lot like structs in C:
-// Just a bunch of named fields. Every field can be private to the current module (which is the default),
-// or public (which is indicated by a `pub` in front of the name). For the sake of the tutorial, we make
-// `data` public - otherwise, the next parts of this course could not work on `BigInt`s. Of course, in a
-// real program, one would make the field private to ensure that the invariant (no trailing zeros) is maintained.
pub struct BigInt {
pub data: Vec<u64>,
}
// Now that we fixed the data representation, we can start implementing methods on it.
impl BigInt {
- // Let's start with a constructor, creating a `BigInt` from an ordinary integer.
- // To create an instance of a struct, we write its name followed by a list of
- // fields and initial values assigned to them.
pub fn new(x: u64) -> Self {
if x == 0 {
BigInt { data: vec![] }
} else {
- BigInt { data: vec![x] }
+ 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!()
}
}
}
// ## 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<T>` implement `Clone`. However, that
-// can only work if `T` is `Clone`! So we have to add this bound to `T` when we introduce
-// the type variable.
+// We can also make the type `SomethingOrNothing<T>` implement `Clone`.
use part02::{SomethingOrNothing,Something,Nothing};
impl<T: Clone> Clone for SomethingOrNothing<T> {
fn clone(&self) -> Self {
- match *self {
- Nothing => Nothing,
- // In the second arm of the match, we need to talk about the value `v`
- // that's stored in `self`. However, if we would write the pattern as
- // `Something(v)`, that would indicate that we *own* `v` in the code
- // after the arrow. That can't work though, we have to leave `v` owned by
- // whoever called us - after all, we don't even own `self`, we just borrowed it.
- // By writing `Something(ref v)`, we borrow `v` for the duration of the match
- // arm. That's good enough for cloning it.
- Something(ref v) => Something(v.clone()),
- }
+ 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 {
/* 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)
// 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.
fn vec_min(v: &Vec<BigInt>) -> Option<BigInt> {
let mut min: Option<BigInt> = None;
for e in v {
- let e = e.clone();
- min = Some(match min {
- None => e,
- Some(n) => e.min_try1(n)
- });
+ 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<BigInt> that it returns is *owned*. We can't just return one of the elements of `v`,
-// as that would mean that it is no longer in the vector! In our code, this comes up when we update
-// the intermediate variable `min`, which also has type `Option<BigInt>`. If you replace get rid of the
-// `e.clone()`, Rust will complain "Cannot move out of borrowed content". That's because
-// `e` is a `&BigInt`. Assigning `min = Some(*e)` works just like a function call: Ownership of the
-// underlying data is transferred from where `e` borrows from to `min`. But that's not allowed, since
-// we just borrowed `e`, so we cannot empty it! We can, however, call `clone()` on it. Then we own
-// the copy that was created, and hence we can store it in `min`.<br/>
-// Of course, making such a full copy is expensive, so we'd like to avoid it. We'll some to that in the next part.
// ## `Copy` types
-// But before we go there, I should answer the second question I brought up above: Why did our old `vec_min` work?
-// We stored the minimal `i32` locally without cloning, and Rust did not complain. That's because there isn't
-// really much of an "ownership" when it comes to types like `i32` or `bool`: If you move the value from one
-// place to another, then both instances are "complete". We also say the value has been *duplicated*. This is in
-// stark contrast to types like `Vec<i32>`, where moving the value results in both the old and the new vector to
-// point to the same underlying buffer. We don't have two vectors, there's no proper duplication.
-//
-// Rust calls types that can be easily duplicated `Copy` types. `Copy` is another trait, and it is implemented for
-// types like `i32` and `bool`. Remember how we defined the trait `Minimum` by writing `trait Minimum : Copy { ...`?
-// This tells Rust that every type that implements `Minimum` must also implement `Copy`, and that's why the compiler
-// accepted our generic `vec_min` in part 02. `Copy` is the first *marker trait* that we encounter: It does not provide
-// any methods, but makes a promise about the behavior of the type - in this case, being duplicable.
-// If you try to implement `Copy` for `BigInt`, you will notice that Rust
-// does not let you do that. A type can only be `Copy` if all its elements
-// are `Copy`, and that's not the case for `BigInt`. However, we can make
-// `SomethingOrNothing<T>` copy if `T` is `Copy`.
use part02::{SomethingOrNothing,Something,Nothing};
impl<T: Copy> Copy for SomethingOrNothing<T> {}
-// Again, Rust can generate implementations of `Copy` automatically. If
-// you add `#[derive(Copy,Clone)]` right before the definition of `SomethingOrNothing`,
-// both `Copy` and `Clone` will automatically be implemented.
-// ## An operational perspective
-// Instead of looking at what happens "at the surface" (i.e., visible in Rust), one can also explain
-// ownership passing and how `Copy` and `Clone` fit in by looking at what happens on the machine.<br/>
-// When Rust code is executed, passing a value (like `i32` or `Vec<i32>`) to a function will always
-// result in a shallow copy being performed: Rust just copies the bytes representing that value, and
-// considers itself done. That's just like the default copy constructor in C++. Rust, however, will
-// consider this a destructive operation: After copying the bytes elsewhere, the original value must
-// no longer be used. After all, the two could now share a pointer! If, however, you mark a type `Copy`,
-// then Rust will *not* consider a move destructive, and just like in C++, the old and new value
-// can happily coexist. Now, Rust does not allow you to overload the copy constructor. This means that
-// passing a value around will always be a fast operation, no allocation or any other kind of heap access
-// will happen. In the situations where you would write a copy constructor in C++ (and hence
-// incur a hidden cost on every copy of this type), you'd have the type *not* implement `Copy`, but only
-// `Clone`. This makes the cost explicit.
// ## Lifetimes
-// To fix the performance problems of `vec_min`, we need to avoid using `clone()`. We'd like
-// the return value to not be owned (remember that this was the source of our need for cloning), but *borrowed*.
-// The function `head` demonstrates how that could work: It borrows the first element of a vector if it is non-empty.
-// The type of the function says that it will either return nothing, or it will return a borrowed `T`.
-// We can then borrow the first element of `v` and use it to construct the return value.
fn head<T>(v: &Vec<T>) -> Option<&T> {
if v.len() > 0 {
- Some(&v[0])
+ unimplemented!()
} else {
None
}
return *first;
}
*/
-// This is very much like our very first motivating example for ownership, at the beginning of part 04:
-// `push_back` could reallocate the buffer, making `first` an invalid pointer. Again, we have aliasing (of `first`
-// and `v`) and mutation. But this time, the bug is hidden behind the call to `head`. How does Rust solve this? If we translate
-// the code above to Rust, it doesn't compile, so clearly we are good - but how and why?
-// (Notice that have to explicitly assert using `unwrap` that `first` is not `None`, whereas the C++ code
-// above would silently dereference a `NULL`-pointer. But that's another point.)
fn rust_foo(mut v: Vec<i32>) -> i32 {
let first: Option<&i32> = head(&v);
/* v.push(42); */
*first.unwrap()
}
-// To give the answer to this question, we have to talk about the *lifetime* of a borrow. The point is, saying that
-// you borrowed your friend a `Vec<i32>`, or a book, is not good enough, unless you also agree on *how long*
-// your friend can borrow it. After all, you need to know when you can rely on owning your data (or book) again.
-//
-// Every borrow in Rust has an associated lifetime, written `&'a T` for a borrow of type `T` with lifetime `'a`. The full
-// type of `head` reads as follows: `fn<'a, T>(&'a Vec<T>) -> Option<&'a T>`. Here, `'a` is a *lifetime variable*, which
-// represents how long the vector has been borrowed. The function type expresses that argument and return value have *the same lifetime*.
-//
-// When analyzing the code of `rust_foo`, Rust has to assign a lifetime to `first`. It will choose the scope
-// where `first` is valid, which is the entire rest of the function. Because `head` ties the lifetime of its
-// argument and return value together, this means that `&v` also has to borrow `v` for the entire duration of
-// the function. So when we try to borrow `v` mutable for `push`, Rust complains that the two borrows (the one
-// for `head`, and the one for `push`) overlap. Lucky us! Rust caught our mistake and made sure we don't crash the program.
-//
-// So, to sum this up: Lifetimes enable Rust to reason about *how long* a pointer has been borrowed. We can thus
-// safely write functions like `head`, that return pointers into data they got as argument, and make sure they
-// are used correctly, *while looking only at the function type*. At no point in our analysis of `rust_foo` did
-// we have to look *into* `head`. That's, of course, crucial if we want to separate library code from application code.
-// Most of the time, we don't have to explicitly add lifetimes to function types. This is thanks to *lifetimes elision*,
-// where Rust will automatically insert lifetimes we did not specify, following some [simple, well-documented rules](http://doc.rust-lang.org/stable/book/lifetimes.html#lifetime-elision).
-// [index](main.html) | [previous](part05.html) | [next](part07.html)
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<T: Minimum>(v: &Vec<T>) -> Option<&T> {
let mut min: Option<&T> = None;
for e in v {
- min = Some(match min {
- None => e,
- Some(n) => n.min(e)
- });
+ 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(++).<br/>
-// Also, if you are worried about wasting space, notice that Rust knows that `&T` can never be
-// `NULL`, and hence optimizes `Option<&T>` to be no larger than `&T`. The `None` case is represented
-// as `NULL`. This is another great example of a zero-cost abstraction: `Option<&T>` is exactly like
-// a pointer in C(++), if you look at what happens during execution - but it's much safer to use.
// **Exercise 07.1**: For our `vec_min` to be usable with `BigInt`, you will have to provide an implementation of
// `Minimum`. You should be able to pretty much copy the code you wrote for exercise 06.1. You should *not*
}
// ## 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);
}
// ## 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<u64>`.
impl fmt::Debug for BigInt {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.data.fmt(f)
}
}
-// `Debug` implementations can be automatically generated using the `derive(Debug)` attribute.
// Now we are ready to use `assert_eq!` to test `vec_min`.
-#[test]
+/*#[test]*/
fn test_vec_min() {
let b1 = BigInt::new(1);
let b2 = BigInt::new(42);
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
// of course, need a `Display` bound on `T`.) Then you should be able to use them with `println!` just like you do
// with numbers, and get rid of the inherent functions to print `SomethingOrNothing<i32>` and `SomethingOrNothing<f32>`.
-// [index](main.html) | [previous](part06.html) | [next](main.html)
// ***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;
// ***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)
projects / rust-101.git / commitdiff