Ask a question about the responsibility of the borrower in a `zip`-like function with a callback
I am trying to implement a function that executes two iterators at the same time, calling a function for each pair. This callback can control which of the iterators is advanced at each step, returning a tuple (bool, bool)
. Since the iterators take a reference to the buffer in my use case, they cannot implement the trait Iterator
from stdlib, but instead use a function next_ref
that is identical Iterator::next
but takes an additional lifetime parameter.
// An iterator-like type, that returns references to itself
// in next_ref
struct RefIter {
value: u64
}
impl RefIter {
fn next_ref<'a>(&'a mut self) -> Option<&'a u64> {
self.value += 1;
Some(&self.value)
}
}
// Iterate over two RefIter simultaneously and call a callback
// for each pair. The callback returns a tuple of bools
// that indicate which iterators should be advanced.
fn each_zipped<F>(mut iter1: RefIter, mut iter2: RefIter, callback: F)
where F: Fn(&Option<&u64>, &Option<&u64>) -> (bool, bool)
{
let mut current1 = iter1.next_ref();
let mut current2 = iter2.next_ref();
loop {
let advance_flags = callback(¤t1, ¤t2);
match advance_flags {
(true, true) => {
current1 = iter1.next_ref();
current2 = iter2.next_ref();
},
(true, false) => {
current1 = iter1.next_ref();
},
(false, true) => {
current2 = iter1.next_ref();
},
(false, false) => {
return
}
}
}
}
fn main() {
let mut iter1 = RefIter { value: 3 };
let mut iter2 = RefIter { value: 4 };
each_zipped(iter1, iter2, |val1, val2| {
let val1 = *val1.unwrap();
let val2 = *val2.unwrap();
println!("{}, {}", val1, val2);
(val1 < 10, val2 < 10)
});
}
error[E0499]: cannot borrow `iter1` as mutable more than once at a time --> src/main.rs:28:28 | 22 | let mut current1 = iter1.next_ref(); | ----- first mutable borrow occurs here ... 28 | current1 = iter1.next_ref(); | ^^^^^ second mutable borrow occurs here ... 42 | } | - first borrow ends here error[E0499]: cannot borrow `iter2` as mutable more than once at a time --> src/main.rs:29:28 | 23 | let mut current2 = iter2.next_ref(); | ----- first mutable borrow occurs here ... 29 | current2 = iter2.next_ref(); | ^^^^^ second mutable borrow occurs here ... 42 | } | - first borrow ends here error[E0499]: cannot borrow `iter1` as mutable more than once at a time --> src/main.rs:32:28 | 22 | let mut current1 = iter1.next_ref(); | ----- first mutable borrow occurs here ... 32 | current1 = iter1.next_ref(); | ^^^^^ second mutable borrow occurs here ... 42 | } | - first borrow ends here error[E0499]: cannot borrow `iter1` as mutable more than once at a time --> src/main.rs:35:28 | 22 | let mut current1 = iter1.next_ref(); | ----- first mutable borrow occurs here ... 35 | current2 = iter1.next_ref(); | ^^^^^ second mutable borrow occurs here ... 42 | } | - first borrow ends here
I understand why he is complaining but cannot find a way around him. I would appreciate any help on this.
Link to this snippet on the playground .
source to share
Since the iterators take a reference to the buffer in my use case, they cannot implement the trait
Iterator
from stdlib, but instead use a functionnext_ref
that is identicalIterator::next
but takes an additional lifetime parameter.
You are describing a streaming iterator. There is a box for this, aptly named streaming_iterator . The documentation describes your problem (emphasis mine):
While the standard functionality of a function
Iterator
is method-basednext
, the functionality isStreamingIterator
based on a couple of methods:advance
andget
. This essentially splits the logicnext
in half (in fact, the methodStreamingIterator
next
does nothing but the calladvance
that followsget
).This is required due to the lexical treatment of rust (more in particular, no single sign-on, multiple entry exits). If it
StreamingIterator
was determined asIterator
soon as requirednext
, operations like thisfilter
cannot be defined.
The box currently has no function zip
and certainly not the option you described. However, it is quite simple to implement it:
extern crate streaming_iterator;
use streaming_iterator::StreamingIterator;
fn each_zipped<A, B, F>(mut iter1: A, mut iter2: B, callback: F)
where
A: StreamingIterator,
B: StreamingIterator,
F: for<'a> Fn(Option<&'a A::Item>, Option<&'a B::Item>) -> (bool, bool),
{
iter1.advance();
iter2.advance();
loop {
let advance_flags = callback(iter1.get(), iter2.get());
match advance_flags {
(true, true) => {
iter1.advance();
iter2.advance();
}
(true, false) => {
iter1.advance();
}
(false, true) => {
iter1.advance();
}
(false, false) => return,
}
}
}
struct RefIter {
value: u64
}
impl StreamingIterator for RefIter {
type Item = u64;
fn advance(&mut self) {
self.value += 1;
}
fn get(&self) -> Option<&Self::Item> {
Some(&self.value)
}
}
fn main() {
let iter1 = RefIter { value: 3 };
let iter2 = RefIter { value: 4 };
each_zipped(iter1, iter2, |val1, val2| {
let val1 = *val1.unwrap();
let val2 = *val2.unwrap();
println!("{}, {}", val1, val2);
(val1 < 10, val2 < 10)
});
}
source to share
The problem with this code is that it is RefIter
used in two ways, which are fundamentally at odds with each other:
- Subscribers
next_ref
receive a link to the stored value, which is tied to the lifetimeRefIter
-
RefIter
the value must be volatile so that it can be incremented on each call
This perfectly describes mutable anti-aliasing (you are trying to change the "value" while referencing it) - something that Rust is clearly intended to prevent.
To make it work each_zipped
, you need to change RefIter
to avoid giving away links to the data you want to change. I have applied one possibility below using a combination of RefCell
and Rc
:
use std::cell::RefCell;
use std::rc::Rc;
// An iterator-like type, that returns references to itself
// in next_ref
struct RefIter {
value: RefCell<Rc<u64>>
}
impl RefIter {
fn next_ref(&self) -> Option<Rc<u64>> {
let new_val = Rc::new(**self.value.borrow() + 1);
*self.value.borrow_mut() = new_val;
Some(Rc::clone(&*self.value.borrow()))
}
}
// Iterate over two RefIter simultaniously and call a callback
// for each pair. The callback returns a tuple of bools
// that indicate which iterators should be advanced.
fn each_zipped<F>(iter1: RefIter, iter2: RefIter, callback: F)
where F: Fn(&Option<Rc<u64>>, &Option<Rc<u64>>) -> (bool, bool)
{
let mut current1 = iter1.next_ref();
let mut current2 = iter2.next_ref();
loop {
let advance_flags = callback(¤t1, ¤t2);
match advance_flags {
(true, true) => {
current1 = iter1.next_ref();
current2 = iter2.next_ref();
},
(true, false) => {
current1 = iter1.next_ref();
},
(false, true) => {
current2 = iter1.next_ref();
},
(false, false) => {
return
}
}
}
}
fn main() {
let iter1 = RefIter { value: RefCell::new(Rc::new(3)) };
let iter2 = RefIter { value: RefCell::new(Rc::new(4)) };
each_zipped(iter1, iter2, |val1, val2| {
// We can't use unwrap() directly, since we're only passed a reference to an Option
let val1 = **val1.iter().next().unwrap();
let val2 = **val2.iter().next().unwrap();
println!("{}, {}", val1, val2);
(val1 < 10, val2 < 10)
});
}
This version RefIter
conveys to Rc
consumers instead of links. This avoids the problem with a mutable alias — the update value
is done by placing a new one Rc
in the external one RefCell
. A side effect of this is that consumers can keep the "old" buffer reference (via the returned one Rc
) even after it has been RefIter
promoted.
source to share