Alexis Beingessner
Carleton University + Mozilla Research
rendered: http://cglab.ca/~abeinges/talks/iter/
raw: http://cglab.ca/~abeinges/talks/iter/index.md
pub trait Iterator { // I can yield things type Item; // Things I yield // How I yield them fn next(&mut self) -> Option<Self::Item>; }
mut because we want to progressOption coalesces has_next and get_next
for i in 0..10 { println!("{}", i); }
i: name for item in Some(item)0..10: the thing to iterate (0 to 10, 10 excluded)(these are structs)
Ownership!
fn process(data: Vec<String>) { for string in data.into_iter() { // I got all the data, it's mine! println!("{}", string); } // Oh no! Iterating consumed it :( println!("{}", data.len()); //~ERROR }
Trash Language; Quit Forever
fn print(data: &Vec<String>) for string in data.iter() { // All I can do is read :/ println!("{}", string); } // Yay it lives! println!("{}", data.len()); }
fn print_combos(data: &Vec<String>) { let len = data.len(); for string in data.iter() { // Iterate and query at the same time! println!("{} {}", string, &data[random_idx(len)]); } }
fn make_better(data: &mut Vec<String>) { for string in data.iter_mut() { // Ooh I can mutate you! string.push_str("!!!!!"); // But I can't share :( } }
let mut data = vec![0, 1, 2, 3, 4, 5]; for x in data.drain(2..4) { // got exclusive access so we can "drain" // the values out but leave the vec alive consume(x); } // data lives on! We can reuse the allocation! // Bulk `remove`! // Dat Perf. ;_; assert_eq!(&*data, &[0, 1, 4, 5]);
Iterators naturally fall out of ownership:
T&T&mut T🍼TRust doesn't understand when indexing is disjoint:
let mut data = vec![1, 2, 3, 4]; let ptr1 = &mut data[0]; let ptr2 = &mut data[1]; //~ ERROR *ptr1 += 5; *ptr2 *= 3;
(I would argue this is a good thing)
But it's ok with IterMut?! Ownership busted?!
let mut data = vec![1, 2, 3, 4]; let mut iter = data.iter_mut(); let ptr1 = iter.next().unwrap(); let ptr2 = iter.next().unwrap(); *ptr1 += 5; *ptr2 *= 3;
(not true for indexing in general)
impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next<'b>(&'b mut self) -> Option<&'a mut T> { ... } }
'a is not associated with 'b, so next doesn't care if you still have a 'a
Shh... It's okay borrow checker, only dreams now
How can Rust let you implement this?!?
You can statically prove to the compiler that this works.
pub struct IterMut<'a, T: 'a> { data: &'a mut[T] }; impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { let d = replace(&mut self.data, &mut []); if d.is_empty() { return None; } let (l, r) = d.split_at_mut(1); self.data = r; l.get_mut(0) } }
Same basic idea works on singly-linked lists and trees -- anything with clear ownership that you can get subviews into.
Totally valid use-cases:
None of these are sound because Iterator says "you can always call next again".
// Vec of enemies with health. // When they reach 0 we "die!" and drop them. // Concurrent modification and iteration! for i in (0..enemies.len()).rev() { enemies[i] -= 1; if enemies[i] == 0 { println!("die!"); enemies.swap_remove(i); } }
You only wanted to work with arrays, right?
pub trait StreamingIterator { type Item; fn next<'a>(&'a mut self) -> Option<&'a mut Self::Item>; }
Now the lifetimes are attached!
Statically prevented from calling next twice.
Actual mutual exclusion!
let ptr1 = iter.next().unwrap(); let ptr2 = iter.next().unwrap(); //~ERROR
&mut Item is hardcoded.
&Item?Item<'a>?(╯°□°)╯︵ ┻━┻
(need higher-kinded-whatzits)
pub trait Seeker { fn next(&mut self) -> Option<&mut Self::Item>; fn prev(&mut self) -> Option<&mut Self::Item>; }
pub trait Cursor { fn next(&mut self) -> Option<&mut Self::Item>; fn prev(&mut self) -> Option<&mut Self::Item>; fn insert(&mut self, Self::Item); fn remove(&mut self) -> Option<Self::Item>; }
http://contain-rs.github.io/linked-list/linked_list/struct.Cursor.html
next againnextprev, insert, remove