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(&current1, &current2);
        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 .

+3


source to share


2 answers


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.

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-based next

, the functionality is StreamingIterator

based on a couple of methods: advance

and get

. This essentially splits the logic next

in half (in fact, the method StreamingIterator

next

does nothing but the call advance

that follows get

).

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 as Iterator

soon as required next

, operations like this filter

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)
    });
}

      

+5


source


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(&current1, &current2);
        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.

+1


source







All Articles