some iterator tuning

diff --git a/Makefile b/Makefile
index 9b2a818079f9d47d59aa34d0206e49a6f1f83886..c81bf583c634adc2bff7cacb3c2a7fe30f957d47 100644 (file)
--- 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.
        @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
 
 workspace/src/main.rs:
        # Don't touch this file

diff --git a/TODO.txt b/TODO.txt
index 39d060cbe6f27de84ed23aae8c517cf79419c638..73c82b1885fe4030843cf7de8d8dab1705ba2160 100644 (file)
--- a/TODO.txt
+++ b/TODO.txt
@@ -1,11 +1,11 @@
 * Closures: Working on iterators
 * Closures: Working on iterators

+

 * Arrays/slices
 * Trait objects
 * 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
 
 * 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 301e15a22c0c86f0edfbf875f1ce1df4fe6da1cd..9a1d22ab8a069c98a8d7d609c38cb2cb43f25973 100644 (file)
--- a/src/part04.rs
+++ b/src/part04.rs
@@ -68,7 +68,9 @@ fn vec_min(v: &Vec<i32>) -> Option<i32> {
     use std::cmp;
 
     let mut min = None;
     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,
         // 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<i32>` is the type of mutable borrows of `vec<i32>`. Because the borrow is
 
 //@ 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.
+//@ mutable, we can use a mutable iterator, providing a mutable borrow of the elements.

 fn vec_inc(v: &mut Vec<i32>) {
 fn vec_inc(v: &mut Vec<i32>) {

-    for e in v {
+    for e in v.iter_mut() {

         *e += 1;
     }
 }
         *e += 1;
     }
 }

diff --git a/src/part06.rs b/src/part06.rs
index 5b90142825798a25321352f136b1c9c913d555a7..6d50c2d0efcd21c64d501a7428d6c6b596756556 100644 (file)
--- a/src/part06.rs
+++ b/src/part06.rs
@@ -26,9 +26,9 @@ impl BigInt {
 }
 
 // Now we can write `vec_min`.
 }
 
 // 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<BigInt>) -> Option<BigInt> {
     let mut min: Option<BigInt> = None;
 fn vec_min(v: &Vec<BigInt>) -> Option<BigInt> {
     let mut min: Option<BigInt> = 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 {                                      /*@*/
     for e in v {
         let e = e.clone();                                          /*@*/
         min = Some(match min {                                      /*@*/


@@ -38,7 +38,7 @@ fn vec_min(v: &Vec<BigInt>) -> Option<BigInt> {
     }
     min
 }
     }
     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
 //@ 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 618eb22ca8924167c2299d0f494c2f59c02b3944..151a3d68ea91cac0bce206e8b979835473497e5f 100644 (file)
--- a/src/part07.rs
+++ b/src/part07.rs
@@ -35,7 +35,7 @@ pub fn vec_min<T: Minimum>(v: &Vec<T>) -> 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*
 
 // **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!()
 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 2867a588883308914a44474de0fac81ab70039bd..7a9c093d8aec4308f0c4463b5adf83e6821133c0 100644 (file)
--- 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. <br/>
         // **Exercise 08.1**: Write the code to handle adding the carry in this case.
     if sum >= a {
         // The addition did not overflow. <br/>
         // **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.
     } 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<BigInt> for BigInt {
             carry = new_carry;                                                  /*@*/
         }
         // **Exercise 08.2**: Handle the final `carry`, and return the sum.
             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 {
 //@ 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]);
     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 c6c32a47b17292e38aa8920e270b8d6aba16dc27..2a46d771fea9f34c3be9f21cce4233efeb991655 100644 (file)
--- a/src/part09.rs
+++ b/src/part09.rs
@@ -119,9 +119,9 @@ fn iter_invalidation_demo() {
 //@ which Rust successfully prevents.
 
 // ## Iterator conversion trait
 //@ 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`.
 //@ `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
 //@ 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
 //@ 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>;
 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! <br/>
     }
 }
 // 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`, 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)
 
 //@ [index](main.html) | [previous](part08.html) | [next](main.html)

diff --git a/workspace/src/part04.rs b/workspace/src/part04.rs
index c7969ac34c949ae50175f6887fb6c3802a601b8a..bde913f20cf6b7750591c0bc3849daaaa09ea250 100644 (file)
--- a/workspace/src/part04.rs
+++ b/workspace/src/part04.rs
@@ -23,7 +23,9 @@ fn vec_min(v: &Vec<i32>) -> Option<i32> {
     use std::cmp;
 
     let mut min = None;
     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,
         // 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<i32>) {
 // ## Mutable borrowing
 
 fn vec_inc(v: &mut Vec<i32>) {

-    for e in v {
+    for e in v.iter_mut() {

         *e += 1;
     }
 }
         *e += 1;
     }
 }

diff --git a/workspace/src/part06.rs b/workspace/src/part06.rs
index 72883277ab6304aa4bd7ec0ff8d38b05dac7488a..15b55d25c1af07066b59699f7b19df48bb92216d 100644 (file)
--- 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<BigInt>) -> Option<BigInt> {
     let mut min: Option<BigInt> = None;
 // Now we can write `vec_min`.
 fn vec_min(v: &Vec<BigInt>) -> Option<BigInt> {
     let mut min: Option<BigInt> = 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!()
     }
     for e in v {
         unimplemented!()
     }

diff --git a/workspace/src/part07.rs b/workspace/src/part07.rs
index 6b779ccf929b2cff2e6e9b5beb5d38c1b27434d9..e2796b409855bedd9fdaca3d8dbc27fcaefaadd0 100644 (file)
--- a/workspace/src/part07.rs
+++ b/workspace/src/part07.rs
@@ -18,7 +18,7 @@ pub fn vec_min<T: Minimum>(v: &Vec<T>) -> 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*
 
 // **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!()
 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 2d3b5d8f677a58456075d70bf3033470185ab28a..1fac1508d7326e5cbbbaadefcf74b04bd5ffe4ee 100644 (file)
--- 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. <br/>
         // **Exercise 08.1**: Write the code to handle adding the carry in this case.
     if sum >= a {
         // The addition did not overflow. <br/>
         // **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.
     } 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<BigInt> for BigInt {
             unimplemented!()
         }
         // **Exercise 08.2**: Handle the final `carry`, and return the sum.
             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 {
 // 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]);
     fn test_add() {
         let b1 = BigInt::new(1 << 32);
         let b2 = BigInt::from_vec(vec![0, 1]);