From: Ralf Jung Date: Thu, 9 Jul 2015 13:14:20 +0000 (+0200) Subject: some iterator tuning X-Git-Url: https://git.ralfj.de/rust-101.git/commitdiff_plain/8fcdbed310c53f621fba0401399659ed1a1ec446?hp=-c some iterator tuning --- 8fcdbed310c53f621fba0401399659ed1a1ec446 diff --git a/Makefile b/Makefile index 9b2a818..c81bf58 100644 --- a/Makefile +++ b/Makefile @@ -29,7 +29,7 @@ workspace/src/%.rs: src/%.rs Makefile dup-unimpl.sed @echo "$< -> $@" @# sed-fu: remove lines starting with "//@", and replace those ending in "/*@*/" by "unimplemented!()". @# Also coalesce multiple adjacent such lines to one. - @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 diff --git a/TODO.txt b/TODO.txt index 39d060c..73c82b1 100644 --- a/TODO.txt +++ b/TODO.txt @@ -1,11 +1,11 @@ * Closures: Working on iterators + * Arrays/slices * Trait objects -* Drop -* ?unsafe? -* ?interior mutability? * Arc, concurrency, channels: Some grep-like thing, "rgrep" * Send, Sync * External dependencies: regexp crate, add to rgrep -* \ No newline at end of file + +* Shared-memoty concurrency, interior mutability: Concurrent counter +* Drop, unsafe: doubly-linked list diff --git a/src/part04.rs b/src/part04.rs index 301e15a..9a1d22a 100644 --- a/src/part04.rs +++ b/src/part04.rs @@ -68,7 +68,9 @@ fn vec_min(v: &Vec) -> Option { use std::cmp; let mut min = None; - for e in v { + // This time, we explicitly request an iterator for the vector `v`. The method `iter` borrows the vector + // it works on, and provides shared borrows of the elements. + for e in v.iter() { // In the loop, `e` now has type `&i32`, so we have to dereference it to obtain an `i32`. min = Some(match min { None => *e, @@ -102,9 +104,9 @@ fn shared_borrow_demo() { //@ As an example, consider a function which increments every element of a vector by 1. //@ The type `&mut Vec` is the type of mutable borrows of `vec`. Because the borrow is -//@ mutable, we can change `e` in the loop. +//@ mutable, we can use a mutable iterator, providing a mutable borrow of the elements. fn vec_inc(v: &mut Vec) { - for e in v { + for e in v.iter_mut() { *e += 1; } } diff --git a/src/part06.rs b/src/part06.rs index 5b90142..6d50c2d 100644 --- a/src/part06.rs +++ b/src/part06.rs @@ -26,9 +26,9 @@ impl BigInt { } // Now we can write `vec_min`. -//@ However, in order to make it type-check, we have to make a full (deep) copy of e by calling `clone`. fn vec_min(v: &Vec) -> Option { let mut min: Option = None; + // If `v` is a shared borrowed vector, then the default for iterating over it is to call `iter`, the iterator that borrows the elements. for e in v { let e = e.clone(); /*@*/ min = Some(match min { /*@*/ @@ -38,7 +38,7 @@ fn vec_min(v: &Vec) -> Option { } min } -//@ Now, what's happening here? Why do we have to clone `e`, and why did we not +//@ Now, what's happening here? Why do we have to to make a full (deep) copy of `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 diff --git a/src/part07.rs b/src/part07.rs index 618eb22..151a3d6 100644 --- a/src/part07.rs +++ b/src/part07.rs @@ -35,7 +35,7 @@ pub fn vec_min(v: &Vec) -> Option<&T> { // **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! +// make any copies of `BigInt`! impl Minimum for BigInt { fn min<'a>(&'a self, other: &'a Self) -> &'a Self { unimplemented!() diff --git a/src/part08.rs b/src/part08.rs index 2867a58..7a9c093 100644 --- a/src/part08.rs +++ b/src/part08.rs @@ -26,9 +26,7 @@ fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) { 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) /*@@*/ + unimplemented!() } 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. @@ -84,10 +82,7 @@ impl ops::Add for BigInt { carry = new_carry; /*@*/ } // **Exercise 08.2**: Handle the final `carry`, and return the sum. - if carry { /*@@*/ - result_vec.push(1); /*@@*/ - } /*@@*/ - BigInt { data: result_vec } /*@@*/ + unimplemented!() } } @@ -118,7 +113,9 @@ impl<'a, 'b> ops::Add<&'a BigInt> for &'b BigInt { //@ 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 { - #[test] + use part05::BigInt; + + /*#[test]*/ fn test_add() { let b1 = BigInt::new(1 << 32); let b2 = BigInt::from_vec(vec![0, 1]); diff --git a/src/part09.rs b/src/part09.rs index c6c32a4..2a46d77 100644 --- a/src/part09.rs +++ b/src/part09.rs @@ -119,9 +119,9 @@ fn iter_invalidation_demo() { //@ which Rust successfully prevents. // ## Iterator conversion trait -//@ If you closely compare the `for` loop in `main` above, with the one in `vec_min`, you will notice that we were able to write +//@ If you closely compare the `for` loop in `main` above, with the one in `part06::vec_min`, you will notice that we were able to write //@ `for e in v` earlier, but now we have to call `iter`. Why is that? Well, the `for` sugar is not actually tied to `Iterator`. -//@ Instead, if demands an implementation of [`IntoIterator`](http://doc.rust-lang.org/beta/std/iter/trait.IntoIterator.html). +//@ Instead, it demands an implementation of [`IntoIterator`](http://doc.rust-lang.org/beta/std/iter/trait.IntoIterator.html). //@ That's a trait of types that provide a *conversion* function into some kind of iterator. These conversion traits are a frequent //@ pattern in Rust: Rather than demanding that something is an iterator, or a string, or whatever; one demands that something //@ can be converted to an iterator/string/whatever. This provides convenience similar to overloading of functions: The function @@ -130,7 +130,7 @@ fn iter_invalidation_demo() { //@ of the right type, the conversion function will not do anything and trivially be optimized away. //@ If you have a look at the documentation of `IntoIterator`, you will notice that the function `into_iter` it provides actually -//@ consumes its argument. So, we'd like to make `Self` a borrowed type, such that the number is not lost after the iteration. +//@ consumes its argument. So we implement the trait for *borrowed* numbers, such that the number is not lost after the iteration. impl<'a> IntoIterator for &'a BigInt { type Item = u64; type IntoIter = Iter<'a>; @@ -139,10 +139,11 @@ impl<'a> IntoIterator for &'a BigInt { } } // With this in place, you can now replace `b.iter()` in `main` by `&b`. Go ahead and try it!
-//@ Wait, `&b`? Why that? Well, we implemented `IntoIterator` for `&BigInt`, so we have to borrow `b`. If we wanted to be able to write -//@ just `b`, we'd have to also implement `IntoIterator` for `BigInt` - which, as already mentioned, would mean that `b` is actually consumed -//@ by the iteration, and gone. This can easily happen, for example, with a `Vec`: Both `Vec` and `&Vec` implement `IntoIterator`, so if -//@ you do `for e in v`, and `v` has type `Vec`, then you will obtain ownership of the elements during the iteration - and destroy the vector -//@ in the process. We actually did that in `vec_min`, but we did not care. You can write `for e in &v` or `for e in v.iter()` to avoid this. +//@ 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 borrow it. Alternatively, we could implement `IntoIterator` +//@ for `BigInt` - which, as already mentioned, would mean that `b` is actually consumed by the iteration, and gone. This can easily happen, +//@ for example, with a `Vec`: Both `Vec` and `&Vec` (and `&mut Vec`) implement `IntoIterator`, so if you do `for e in v`, and `v` has type `Vec`, +//@ then you will obtain ownership of the elements during the iteration - and destroy the vector in the process. We actually did that in +//@ `part01::vec_min`, but we did not care. You can write `for e in &v` or `for e in v.iter()` to avoid this. //@ [index](main.html) | [previous](part08.html) | [next](main.html) diff --git a/workspace/src/part04.rs b/workspace/src/part04.rs index c7969ac..bde913f 100644 --- a/workspace/src/part04.rs +++ b/workspace/src/part04.rs @@ -23,7 +23,9 @@ fn vec_min(v: &Vec) -> Option { use std::cmp; let mut min = None; - for e in v { + // This time, we explicitly request an iterator for the vector `v`. The method `iter` borrows the vector + // it works on, and provides shared borrows of the elements. + for e in v.iter() { // In the loop, `e` now has type `&i32`, so we have to dereference it to obtain an `i32`. min = Some(match min { None => *e, @@ -45,7 +47,7 @@ fn shared_borrow_demo() { // ## Mutable borrowing fn vec_inc(v: &mut Vec) { - for e in v { + for e in v.iter_mut() { *e += 1; } } diff --git a/workspace/src/part06.rs b/workspace/src/part06.rs index 7288327..15b55d2 100644 --- a/workspace/src/part06.rs +++ b/workspace/src/part06.rs @@ -25,6 +25,7 @@ impl BigInt { // Now we can write `vec_min`. fn vec_min(v: &Vec) -> Option { let mut min: Option = None; + // If `v` is a shared borrowed vector, then the default for iterating over it is to call `iter`, the iterator that borrows the elements. for e in v { unimplemented!() } diff --git a/workspace/src/part07.rs b/workspace/src/part07.rs index 6b779cc..e2796b4 100644 --- a/workspace/src/part07.rs +++ b/workspace/src/part07.rs @@ -18,7 +18,7 @@ pub fn vec_min(v: &Vec) -> Option<&T> { // **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! +// make any copies of `BigInt`! impl Minimum for BigInt { fn min<'a>(&'a self, other: &'a Self) -> &'a Self { unimplemented!() diff --git a/workspace/src/part08.rs b/workspace/src/part08.rs index 2d3b5d8..1fac150 100644 --- a/workspace/src/part08.rs +++ b/workspace/src/part08.rs @@ -13,9 +13,7 @@ fn overflowing_add(a: u64, b: u64, carry: bool) -> (u64, bool) { 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) /*@@*/ + unimplemented!() } 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. @@ -54,10 +52,7 @@ impl ops::Add for BigInt { unimplemented!() } // **Exercise 08.2**: Handle the final `carry`, and return the sum. - if carry { /*@@*/ - result_vec.push(1); /*@@*/ - } /*@@*/ - BigInt { data: result_vec } /*@@*/ + unimplemented!() } } @@ -81,7 +76,9 @@ impl<'a, 'b> ops::Add<&'a BigInt> for &'b BigInt { // Rust calls a bunch of definitions that are grouped together a *module*. You can put the tests in a submodule as follows. #[cfg(test)] mod tests { - #[test] + use part05::BigInt; + + /*#[test]*/ fn test_add() { let b1 = BigInt::new(1 << 32); let b2 = BigInt::from_vec(vec![0, 1]);