//@ What this does is 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, a type like `SomethingOrNothing` is so
//@ useful that it is already present in the standard library: It's called an *option 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.
//@ 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.trim().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
//@ that was created before calling `vec_min` remains valid.
// ## Unique, mutable references
-
//@ There is a second way to borrow something, a second kind of reference: The *mutable reference*.
//@ This is a reference that comes with the promise that nobody else has *any kind of access* to
//@ the referee - in contrast to shared references, there is no aliasing with mutable references.
vec_inc(&mut v);
/* println!("The first element is: {}", *first); */ /* BAD! */
}
-
//@ `&mut` is the operator to create a mutable reference. We have to mark `v` as mutable in order
//@ to create such a reference: Even though we completely own `v`, Rust tries to protect us from
//@ accidentally mutating things.
//@ 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
//@ (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.
+//@ 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) | [raw source](workspace/src/part05.rs) |
//@ [next](part06.html)
//@ 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
//@ 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`.
//@ 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*. In other words, we want to return a shared reference to the minimal element.
+
//@ The function `head` demonstrates how that could work: It returns a reference to 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 obtain a reference to the first
//@ references 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 *lifetime elision*, where Rust will automatically insert lifetimes we did not specify,
-//@ following some simple, well-documented
+//@ application code. Most of the time, we don't have to explicitly add lifetimes to function
+//@ types. This is thanks to *lifetime elision*, where Rust will automatically insert lifetimes we
+//@ did not specify, following some simple, well-documented
//@ [rules](https://doc.rust- lang.org/stable/book/lifetimes.html#lifetime-elision).
//@ [index](main.html) | [previous](part05.html) | [raw source](workspace/src/part06.rs) |
//@ much safer to use.
// **Exercise 07.1**: For our `vec_min` to be usable with `BigInt`, you will have to provide an
-// **implementation of `Minimum`. You should be able to pretty much copy the code you wrote for
-// **exercise 06.1. You should *not* make any copies of `BigInt`!
+// implementation of `Minimum`. You should be able to pretty much copy the code you wrote for
+// exercise 06.1. You should *not* make any copies of `BigInt`!
impl Minimum for BigInt {
fn min<'a>(&'a self, other: &'a Self) -> &'a Self {
unimplemented!()
}
// ## Operator Overloading
-
//@ How can we know that our `min` function actually does what we want it to do? One possibility
//@ here is to do *testing*. Rust comes with nice built-in support for both unit tests and
//@ integration tests. However, before we go there, we need to have a way of checking whether the
// Now we can compare `BigInt`s. Rust treats `PartialEq` special in that it is wired to the operator
// `==`:
-
//@ That operator can now 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
// So, let us write a function to "add with carry", and give it the appropriate type. Notice Rust's
// native support for pairs.
fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) {
-
//@ Rust's stanza on integer overflows may be a bit surprising: In general, when we write `a +
//@ b`, an overflow is considered an *error*. If you compile your program in debug mode, Rust
//@ will actually check for that error and panic the program in case of overflows. For
//@ other operand. In this case, it will also be `BigInt` (and we could have left it away, since
//@ that's the default).
impl ops::Add<BigInt> for BigInt {
-
//@ Besides static functions and methods, traits can contain *associated types*: This is a type
//@ chosen by every particular implementation of the trait. The methods of the trait can then
//@ refer to that type. In the case of addition, it is used to give the type of the result.
//@ The `cfg` attribute controls whether this module is even compiled: If we added some functions
//@ that are useful for testing, Rust would not bother compiling them when you just build your
//@ program for normal use. Other than that, tests work as usually.
-
#[cfg(test)]
mod tests {
use part05::BigInt;
//@ current location. However, it cannot *own* the `BigInt`, because then the number would be gone
//@ after iteration! That'd certainly be bad. The only alternative is for the iterator to *borrow*
//@ the number, so it takes a reference.
+
//@ In writing this down, we again have to be explicit about the lifetime of the reference: We
//@ can't just have an `Iter`, we must have an `Iter<'a>` that borrows the number for lifetime
//@ `'a`. This is our first example of a data-type that's polymorphic in a lifetime, as opposed to
//@ `usize` here is the type of unsigned, pointer-sized numbers. It is typically the type of
//@ "lengths of things", in particular, it is the type of the length of a `Vec` and hence the right
//@ type to store an offset into the vector of digits.
-
pub struct Iter<'a> {
num: &'a BigInt,
idx: usize, // the index of the last number that was returned
/*b = b + BigInt::new(1);*/ /* BAD! */
}
}
-
//@ If you enable the bad line, Rust will reject the code. Why? The problem is that we are
//@ modifying the number while iterating over it. In other languages, this can have all sorts of
//@ effects from inconsistent data or throwing an exception (Java) to bad pointers being
}
}
// With this in place, you can now replace `b.iter()` in `main` by `&b`. Go ahead and try it! <br/>
-
//@ Wait, `&b`? Why that? Well, we implemented `IntoIterator` for `&BigInt`. If we are in a place
//@ where `b` is already borrowed, we can just do `for digit in b`. If however, we own `b`, we have
//@ to create a reference to it. Alternatively, we could implement `IntoIterator` for `BigInt` -
// then looks for numbers larger than some threshold, and prints them.
fn inc_print_threshold(v: &Vec<i32>, offset: i32, threshold: i32) {
//@ `map` takes a closure that is applied to every element of the iterator. `filter` removes
- //@ elements from the iterator that do not pass the test given by the closure. Since all these
- //@ closures compile down to the pattern described above, there is actually no heap allocation
- //@ going on here. This makes closures very efficient, and it makes optimization fairly
- //@ trivial: The resulting code will look like you hand-rolled the loop in C.
+ //@ elements from the iterator that do not pass the test given by the closure.
+ //@
+ //@ Since all these closures compile down to the pattern described above, there is actually no
+ //@ heap allocation going on here. This makes closures very efficient, and it makes
+ //@ optimization fairly trivial: The resulting code will look like you hand-rolled the loop in
+ //@ C.
for i in v.iter().map(|n| *n + offset).filter(|n| *n > threshold) {
println!("{}", i);
}
//@ The difference to a reference is that `Box` implies full ownership: Once you drop
//@ the box (i.e., when the entire `Callbacks` instance is dropped), the content it
//@ points to on the heap will be deleted.
-
}
}
}
//@ This restriction propagates up to `Callbacks` itself. What could we do about this?
//@ ## `Rc`
-
//@ The solution is to find some way of cloning `Callbacks` without cloning the environments. This
//@ can be achieved with `Rc<T>`, a *reference-counted* pointer. This is is another example of a
//@ smart pointer. You can `clone` an `Rc` as often as you want, that doesn't affect the data it
// `borrow_mut`.
//@ At run-time, the cell will keep track of the number of outstanding shared and
//@ mutable references, and panic if the rules are violated. <br />
-
//@ For this check to be performed, `closure` is a *guard*: Rather than a normal
//@ reference, `borrow_mut` returns a smart pointer ([`RefMut`](https://doc.rust-
//@ lang.org/stable/std/cell/struct.RefMut.html), in this case) that waits until is
// `unwrap_or_else` for this job.
//@ ## `RwLock`
-
-//@ Besides `Mutex`, there's also [`RwLock`](https://doc.rust-
-//@ lang.org/stable/std/sync/struct.RwLock.html), which provides two ways of locking: One that
-//@ grants only read-only access, to any number of concurrent readers, and another one for
-//@ exclusive write access. Notice that this is the same pattern we already saw with shared vs.
-//@ mutable references. Hence another way of explaining `RwLock` is to say that it is like
-//@ `RefCell`, but works even for concurrent access. Rather than panicking when the data is already
-//@ borrowed, `RwLock` will of course block the current thread until the lock is available.
-//@ In this view, `Mutex` is a stripped-down version of `RwLock` that does not distinguish readers
-//@ and writers.
+//@ Besides `Mutex`, there's also
+//@ [`RwLock`](https://doc.rust-lang.org/stable/std/sync/struct.RwLock.html), which provides two
+//@ ways of locking: One that grants only read-only access, to any number of concurrent readers,
+//@ and another one for exclusive write access. Notice that this is the same pattern we already
+//@ saw with shared vs. mutable references. Hence another way of explaining `RwLock` is to say that
+//@ it is like `RefCell`, but works even for concurrent access. Rather than panicking when the data
+//@ is already borrowed, `RwLock` will of course block the current thread until the lock is
+//@ available. In this view, `Mutex` is a stripped-down version of `RwLock` that does not
+//@ distinguish readers and writers.
// **Exercise 15.3**: Change the code above to use `RwLock`, such that multiple calls to `get` can
// be executed at the same time.
//@ low-level data-structure like a doubly-linked list, it makes sense to implement an efficient
//@ version once, that is unsafe internally, but that can be used without any risk by safe client
//@ code.
+
//@ As usually, we start by defining the types. Everything is parameterized by the type `T` of the
//@ data stored in the list.
// A node of the list consists of the data, and two node pointers for the predecessor and successor.
}
// ## The End
-
//@ Congratulations! You completed Rust-101. This was the last part of the course. I hope you
//@ enjoyed it. If you have feedback or want to contribute yourself, please head to the
//@ [Rust-101](https://www.ralfj.de/projects/rust-101/) website fur further information. The entire
projects / rust-101.git / commitdiff