From 7c63fce3ed1474437f62a5f14cbd9fa398ec9abe Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Fri, 10 Jul 2015 17:55:43 +0200 Subject: [PATCH] finalize part 11 --- TODO.txt | 1 - src/main.rs | 1 + src/part08.rs | 10 ++-- src/part10.rs | 2 +- src/part11.rs | 117 +++++++++++++++++++++------------------- workspace/src/part08.rs | 2 +- workspace/src/part11.rs | 55 +++++++++---------- 7 files changed, 96 insertions(+), 92 deletions(-) diff --git a/TODO.txt b/TODO.txt index 1bf2f51..cc3268b 100644 --- a/TODO.txt +++ b/TODO.txt @@ -1,5 +1,4 @@ * Arrays/slices -* Trait objects * Arc, concurrency, channels: Some grep-like thing, "rgrep" * Send, Sync diff --git a/src/main.rs b/src/main.rs index 35c670f..4fe4215 100644 --- a/src/main.rs +++ b/src/main.rs @@ -78,6 +78,7 @@ // * [Part 08: Associated Types, Modules](part08.html) // * [Part 09: Iterators](part09.html) // * [Part 10: Closures](part10.html) +// * [Part 11: Trait Objects, Box, Rc, Lifetime bounds](part11.html) // * (to be continued) #![allow(dead_code, unused_imports, unused_variables, unused_mut)] mod part00; diff --git a/src/part08.rs b/src/part08.rs index d6b6782..7b471b9 100644 --- a/src/part08.rs +++ b/src/part08.rs @@ -20,19 +20,19 @@ fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) { //@ function (see [the documentation](http://doc.rust-lang.org/stable/std/primitive.u64.html#method.wrapping_add), //@ there are similar functions for other arithmetic operations). There are also similar functions //@ `checked_add` etc. to enforce the overflow check. - let sum = u64::wrapping_add(a, b); + let sum = a.wrapping_add(b); // If an overflow happened, then the sum will be smaller than *both* summands. Without an overflow, of course, it will be // at least as large as both of them. So, let's just pick one and check. if sum >= a { // The addition did not overflow.
// **Exercise 08.1**: Write the code to handle adding the carry in this case. - let sum_total = u64::wrapping_add(sum, if carry { 1 } else { 0 }); /*@@*/ - let had_overflow = sum_total < sum; /*@@*/ - (sum_total, had_overflow) /*@@*/ + let sum_total = sum.wrapping_add(if carry { 1 } else { 0 });/*@@*/ + let had_overflow = sum_total < sum; /*@@*/ + (sum_total, had_overflow) /*@@*/ } else { // Otherwise, the addition *did* overflow. It is impossible for the addition of the carry // to overflow again, as we are just adding 0 or 1. - (sum + if carry { 1 } else { 0 }, true) /*@*/ + (sum + if carry { 1 } else { 0 }, true) /*@*/ } } diff --git a/src/part10.rs b/src/part10.rs index cfa10e4..53110dc 100644 --- a/src/part10.rs +++ b/src/part10.rs @@ -141,4 +141,4 @@ fn filter_vec_by_divisor(v: &Vec, divisor: i32) -> Vec { // product of those numbers that sit at odd positions? A function that checks whether a vector contains a certain number? Whether all numbers are // smaller than some threshold? Be creative! -//@ [index](main.html) | [previous](part09.html) | [next](main.html) +//@ [index](main.html) | [previous](part09.html) | [next](part11.html) diff --git a/src/part11.rs b/src/part11.rs index 1256e19..5219d30 100644 --- a/src/part11.rs +++ b/src/part11.rs @@ -1,54 +1,53 @@ -// Rust-101, Part 11: Trait Objects, Box (WIP) -// =========================================== +// Rust-101, Part 11: Trait Objects, Box, Rc +// ========================================= -//@ Now that we know about closures, let's have some fun with them. We will try to implement some kind of generic "callback" +//@ We will play around with closures a bit more. Let us implement some kind of generic "callback" //@ mechanism, providing two functions: Registering a new callback, and calling all registered callbacks. There will be two //@ versions, so to avoid clashes of names, we put them into modules. - mod callbacks { - //@ First of all, we need to find a way to store the callbacks. Clearly, there will be a `Vec` involves, so that we can + //@ First of all, we need to find a way to store the callbacks. Clearly, there will be a `Vec` involved, so that we can //@ always grow the number of registered callbacks. A callback will be a closure, i.e., something implementing //@ `FnMut(i32)` (we want to call this multiple times, so clearly `FnOnce` would be no good). So our first attempt may be the following. - // For now, we just decide that the callbakcs have an argument of type `i32`. + // For now, we just decide that the callbacks have an argument of type `i32`. struct CallbacksV1 { callbacks: Vec, } - //@ However, this will not work. Remember how the "type" of a closure is specific to the environment of captures variables. Different closures - //@ all implementing `FnMut(i32)` may be different types. However, a `Vec` is a *uniformly typed* vector. + //@ However, this will not work. Remember how the "type" of a closure is specific to the environment of captured variables. Different closures + //@ all implementing `FnMut(i32)` may have different types. However, a `Vec` is a *uniformly typed* vector. - //@ We will this need a way to store things of *different* types in the same vector. We know all these types implement `FnMut(i32)`. For this scenario, - //@ Rust provides *trait objects*: The truth is, that `FnMut(i32)` is not just a trait. It is also a type, that can be given to anything implementing - //@ this trait. So, we may write: + //@ We will thus need a way to store things of *different* types in the same vector. We know all these types implement `FnMut(i32)`. For this scenario, + //@ Rust provides *trait objects*: The truth is, `FnMut(i32)` is not just a trait. It is also a type, that can be given to anything implementing + //@ this trait. So, we may write the following. /* struct CallbacksV2 { callbacks: Vec, } */ //@ But, Rust complains about this definition. It says something about "Sized". What's the trouble? See, for many things we want to do, it is crucial that - //@ Rust knows the precise, fixed size of the type - that is, how large will this type be when represented in memory. For example, for a `Vec`, the + //@ Rust knows the precise, fixed size of the type - that is, how large this type will be when represented in memory. For example, for a `Vec`, the //@ elements are stored one right after the other. How should that be possible, without a fixed size? The trouble is, `FnMut(i32)` could be of any size. //@ We don't know how large that "type that implemenets `FnMut(i32)`" is. Rust calls this an *unsized* type. Whenever we introduce a type variable, Rust - //@ will implicitly add a bound to that variable, demanding that it is sized. That's why we did not have to worry about this so far. - //@ You can, btw, opt-out of this implicit bound by saying `T: ?Sized`. Then `T` may or may not be sized. + //@ will implicitly add a bound to that variable, demanding that it is sized. That's why we did not have to worry about this so far.
+ //@ You can opt-out of this implicit bound by saying `T: ?Sized`. Then `T` may or may not be sized. //@ So, what can we do, if we can't store the callbacks in a vector? We can put them in a box. Semantically, `Box` is a lot like `T`: You fully own //@ the data stored there. On the machine, however, `Box` is a *pointer* to `T`. It is a lot like `std::unique_ptr` in C++. In our current example, //@ the important bit is that since it's a pointer, `T` can be unsized, but `Box` itself will always be sized. So we can put it in a `Vec`. - struct Callbacks { + pub struct Callbacks { callbacks: Vec>, } impl Callbacks { // Now we can provide some functions. The constructor should be straight-forward. - fn new() -> Self { + pub fn new() -> Self { Callbacks { callbacks: Vec::new() } /*@*/ } // Registration simply stores the callback. - fn register(&mut self, callback: Box) { + pub fn register(&mut self, callback: Box) { self.callbacks.push(callback); /*@*/ } // And here we call all the stored callbacks. - fn call(&mut self, val: i32) { + pub fn call(&mut self, val: i32) { // Since they are of type `FnMut`, we need to mutably iterate. Notice that boxes dereference implicitly. for callback in self.callbacks.iter_mut() { callback(val); /*@*/ @@ -56,68 +55,69 @@ mod callbacks { } } - // Now we are read for the demo. - pub fn demo() { - let mut c = Callbacks::new(); + // Now we are ready for the demo. + pub fn demo(c: &mut Callbacks) { c.register(Box::new(|val| println!("Callback 1: {}", val))); - c.call(0); //@ We can even register callbacks that modify their environment. Rust will again attempt to borrow `count`. However, //@ that doesn't work out this time: Since we want to put this thing in a `Box`, it could live longer than the function - //@ we are in. Then the borrow of `count` would become invalid. However, we can tell rust to `move` ownership of the - //@ variable into the closure. Its environment will then contain an `usize` rather than a `&mut uszie`, and have + //@ we are in. Then the borrow of `count` would become invalid. We have to explicitly tell Rust to `move` ownership of the + //@ variable into the closure. Its environment will then contain a `usize` rather than a `&mut uszie`, and have //@ no effect on this local variable anymore. let mut count: usize = 0; c.register(Box::new(move |val| { count = count+1; println!("Callback 2, {}. time: {}", count, val); } )); - c.call(1); - c.call(2); + c.call(1); c.call(2); } - } // Remember to edit `main.rs` to run the demo. pub fn main() { - callbacks::demo(); + let mut c = callbacks::Callbacks::new(); + callbacks::demo(&mut c); } mod callbacks_clone { //@ So, this worked great, didn't it! There's one point though that I'd like to emphasize: One cannot `clone` a closure. - //@ Hence it becomes impossibly to implement `Clone` for our `Callbacks` type. What could we do about this? + //@ Hence it becomes impossible to implement `Clone` for our `Callbacks` type. What could we do about this? - //@ You already learned about `Box` above. `Box` is historically a very special type in Rust (though it lost most of its - //@ particularities by now, and people are working on making it just a normal library type). Effectively, however, it is - //@ just an example of a *smart pointer*: It's like a pointer (i.e., a borrow), but with some additional smarts to it. For - //@ `Box`, that's the part about ownership. Once you drop the box, the content it points to will also be deleted. - //@ - //@ Another example of a smart pointer in Rust is `Rc`. This is short for *reference-counter*, so you can already guess how + //@ You already learned about `Box` above. `Box` is an example of a *smart pointer*: It's like a pointer (in the C + //@ sense), but with some additional smarts to it. For `Box`, that's the part about ownership. Once you drop the box, the + //@ content it points to will be deleted.
+ //@ Another example of a smart pointer is `Rc`. This is short for *reference-counter*, so you can already guess how //@ this pointer is smart: It has a reference count. You can `clone` an `Rc` as often as you want, that doesn't affect the - //@ data it contains at all. It only creates more references to the same data. Once all the references are gone, the data is - //@ deleted. + //@ data it contains at all. It only creates more references to the same data. Once all the references are gone, the data is deleted. //@ - //@ Wait a moment, you may here. Multiple references to the same data? That's aliasing! Indeed, we have to be careful here. - //@ Once data is stored in an `Rc`, is is read-only: By dereferencing the smart `Rc`, you can only get a shared borrow of the data. - use std::rc; + //@ Wait a moment, you may say here. Multiple references to the same data? That's aliasing! Indeed, we have to be careful. + //@ Once data is stored in an `Rc`, it is read-only: By dereferencing the smart `Rc`, you can only get a shared borrow of the data. + use std::rc::Rc; //@ Because of this read-only restriction, we cannot use `FnMut` here: We'd be unable to call the function with a mutable borrow //@ of it's environment! So we have to go with `Fn`. We wrap that in an `Rc`, and then Rust happily derives `Clone` for us. #[derive(Clone)] - struct Callbacks { - callbacks: Vec>, + pub struct Callbacks { + callbacks: Vec>, } - // The methods on these clonable callbacks are just like the ones above. impl Callbacks { - fn new() -> Self { + pub fn new() -> Self { Callbacks { callbacks: Vec::new() } /*@*/ } - fn register(&mut self, callback: rc::Rc) { - self.callbacks.push(callback); /*@*/ + // For the `register` function, we don't actually have to use trait objects in the argument. + //@ We can make this function generic, such that it will be instantiated with some concrete closure type `F` + //@ and do the creation of the `Rc` and the conversion to `Fn(i32)` itself. + + //@ For this to work, we need to demand that the type `F` does not contain any short-lived borrows. After all, we will store it + //@ in our list of callbacks indefinitely. `'static` is a lifetime, the lifetime of the entire program. We can use lifetimes + //@ as bounds on types, to demand that anything in (an element of) the type lives at least as long as this lifetime. That bound was implicit in the `Box` + //@ above, and it is the reason we could not have the borrowed `count` in the closure in `demo`. + pub fn register(&mut self, callback: F) { + self.callbacks.push(Rc::new(callback)); /*@*/ } - fn call(&mut self, val: i32) { - // We only need a shared iterator here. `Rc` also implicitly dereferences, so we can just call the callback. + pub fn call(&mut self, val: i32) { + // We only need a shared iterator here. `Rc` also implicitly dereferences, so we can simply call the callback. for callback in self.callbacks.iter() { callback(val); /*@*/ } @@ -125,12 +125,9 @@ mod callbacks_clone { } // The demo works just as above. Our counting callback doesn't work anymore though, because we are using `Fn` now. - fn demo() { - let mut c = Callbacks::new(); - c.register(rc::Rc::new(|val| println!("Callback 1: {}", val))); - - c.call(0); - c.call(1); + fn demo(c: &mut Callbacks) { + c.register(|val| println!("Callback 1: {}", val)); + c.call(0); c.call(1); } } @@ -138,4 +135,16 @@ mod callbacks_clone { // to work with an arbitrary type `T` that's passed to the callbacks. Since you need to call multiple callbacks with the // same `t: T`, you will either have to restrict `T` to `Copy` types, or pass a borrow. +//@ ## Run-time behavior +//@ When you run the program above, how does Rust know what to do with the callbacks? Since an unsized type lacks some information, +//@ a *pointer* to such a type (be it a `Box`, an `Rc` or a borrow) will need to complete this information. We say that pointers to +//@ trait objects are *fat*. They store not only the address of the object, but (in the case of trait objects) also a *vtable*: A +//@ table of function pointers, determining the code that's run when a trait method is called. There are some restrictions for traits to be usable +//@ as trait objects. This is called *object safety* and described in [the documentation](http://doc.rust-lang.org/stable/book/trait-objects.html) and [the reference](http://doc.rust-lang.org/reference.html#trait-objects). +//@ +//@ Whenever you write a generic function, you have a choice: You can make it polymorphic, like our `vec_min`. Or you +//@ can use trait objects, like the first `register` above. The latter will result in only a single compiled version (rather +//@ than one version per type it is instantiated with). This makes for smaller code, but you pay the overhead of the virtual function calls. +//@ Isn't it beautiful how traits can handle both of these cases (and much more, as we saw, like closures and operator overloading) nicely? + //@ [index](main.html) | [previous](part10.html) | [next](main.html) diff --git a/workspace/src/part08.rs b/workspace/src/part08.rs index 1fac150..0118906 100644 --- a/workspace/src/part08.rs +++ b/workspace/src/part08.rs @@ -7,7 +7,7 @@ use part05::BigInt; // 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) { - let sum = u64::wrapping_add(a, b); + let sum = a.wrapping_add(b); // If an overflow happened, then the sum will be smaller than *both* summands. Without an overflow, of course, it will be // at least as large as both of them. So, let's just pick one and check. if sum >= a { diff --git a/workspace/src/part11.rs b/workspace/src/part11.rs index f868a3c..01f170b 100644 --- a/workspace/src/part11.rs +++ b/workspace/src/part11.rs @@ -1,9 +1,8 @@ -// Rust-101, Part 11: Trait Objects, Box (WIP) -// =========================================== - +// Rust-101, Part 11: Trait Objects, Box, Rc +// ========================================= mod callbacks { - // For now, we just decide that the callbakcs have an argument of type `i32`. + // For now, we just decide that the callbacks have an argument of type `i32`. struct CallbacksV1 { callbacks: Vec, } @@ -12,23 +11,23 @@ mod callbacks { callbacks: Vec, } */ - struct Callbacks { + pub struct Callbacks { callbacks: Vec>, } impl Callbacks { // Now we can provide some functions. The constructor should be straight-forward. - fn new() -> Self { + pub fn new() -> Self { unimplemented!() } // Registration simply stores the callback. - fn register(&mut self, callback: Box) { + pub fn register(&mut self, callback: Box) { unimplemented!() } // And here we call all the stored callbacks. - fn call(&mut self, val: i32) { + pub fn call(&mut self, val: i32) { // Since they are of type `FnMut`, we need to mutably iterate. Notice that boxes dereference implicitly. for callback in self.callbacks.iter_mut() { unimplemented!() @@ -36,47 +35,45 @@ mod callbacks { } } - // Now we are read for the demo. - pub fn demo() { - let mut c = Callbacks::new(); + // Now we are ready for the demo. + pub fn demo(c: &mut Callbacks) { c.register(Box::new(|val| println!("Callback 1: {}", val))); - c.call(0); let mut count: usize = 0; c.register(Box::new(move |val| { count = count+1; println!("Callback 2, {}. time: {}", count, val); } )); - c.call(1); - c.call(2); + c.call(1); c.call(2); } - } // Remember to edit `main.rs` to run the demo. pub fn main() { - callbacks::demo(); + let mut c = callbacks::Callbacks::new(); + callbacks::demo(&mut c); } mod callbacks_clone { - use std::rc; + use std::rc::Rc; #[derive(Clone)] - struct Callbacks { - callbacks: Vec>, + pub struct Callbacks { + callbacks: Vec>, } - // The methods on these clonable callbacks are just like the ones above. impl Callbacks { - fn new() -> Self { + pub fn new() -> Self { unimplemented!() } - fn register(&mut self, callback: rc::Rc) { + // For the `register` function, we don't actually have to use trait objects in the argument. + + pub fn register(&mut self, callback: F) { unimplemented!() } - fn call(&mut self, val: i32) { - // We only need a shared iterator here. `Rc` also implicitly dereferences, so we can just call the callback. + pub fn call(&mut self, val: i32) { + // We only need a shared iterator here. `Rc` also implicitly dereferences, so we can simply call the callback. for callback in self.callbacks.iter() { unimplemented!() } @@ -84,12 +81,9 @@ mod callbacks_clone { } // The demo works just as above. Our counting callback doesn't work anymore though, because we are using `Fn` now. - fn demo() { - let mut c = Callbacks::new(); - c.register(rc::Rc::new(|val| println!("Callback 1: {}", val))); - - c.call(0); - c.call(1); + fn demo(c: &mut Callbacks) { + c.register(|val| println!("Callback 1: {}", val)); + c.call(0); c.call(1); } } @@ -97,3 +91,4 @@ mod callbacks_clone { // to work with an arbitrary type `T` that's passed to the callbacks. Since you need to call multiple callbacks with the // same `t: T`, you will either have to restrict `T` to `Copy` types, or pass a borrow. + -- 2.30.2