I am writing a merge function for vectors of tags with counts, but am getting borrowing errors.
fn merge(mut l1: Vec<(String, u32)>, mut l2: Vec<(String, u32)>) -> Vec<(String, u32)> {
let mut d1 = l1.drain(..);
let mut d2 = l2.drain(..);
let mut result = Vec::new();
let mut v1 = d1.next();
let mut v2 = d2.next();
loop {
match (v1, v2) {
(None, None) => return result,
(None, Some(x)) => {
result.push(x.clone());
v2 = d2.next()
}
(Some(x), None) => {
result.push(x.clone());
v1 = d1.next()
}
(Some(p1), Some(p2)) => {
let (ref s1, t1) = p1;
let (ref s2, t2) = p2;
if s1 == s2 {
result.push((s1.clone(), t1 + t2));
v1 = d1.next();
v2 = d2.next();
} else if s1 < s2 {
result.push(p1.clone());
v1 = d1.next();
} else {
result.push(p2.clone());
v2 = d2.next();
}
}
}
}
}
gives the error:
error: use of moved value: `v1` [E0382]
match (v1,v2) {
^~
help: run `rustc --explain E0382` to see a detailed explanation
note: `v1` was previously moved here because it has type `core::option::Option<(collections::string::String, u32)>`, which is non-copyable
and a similar error for v2. It usually shows the problem location and the previous move that causes the problem, but not here.
I've tried many permutations, and with the following change I've gotten it to compile, but I'm not happy about all the cloning and recreating tuples and recreating Options.
match (v1, v2) {
(None, None) => return result,
(None, Some(x)) => {
result.push(x.clone());
v1 = None;
v2 = d2.next();
}
(Some(x), None) => {
result.push(x.clone());
v1 = d1.next();
v2 = None;
}
(Some(p1), Some(p2)) => {
let (ref s1, t1) = p1;
let (ref s2, t2) = p2;
if s1 == s2 {
result.push((s1.clone(), t1 + t2));
v1 = d1.next();
v2 = d2.next();
} else if s1 < s2 {
result.push(p1.clone());
v1 = d1.next();
v2 = Some((s2.clone(), t2));
} else {
result.push(p2.clone());
v1 = Some((s1.clone(), t1));
v2 = d2.next();
}
}
}
Adding what I'd really like to write, for reference, in case someone is looking for a challenge for the borrow checker:
fn merge(mut l1: Vec<(String, u32)>, mut l2: Vec<(String, u32)>) -> Vec<(String, u32)> {
let mut d1 = l1.drain(..);
let mut d2 = l2.drain(..);
let mut result = Vec::new();
let mut v1 = d1.next();
let mut v2 = d2.next();
loop {
match (v1, v2) {
(None, None) => return result,
(None, Some(p2)) => {
result.push(p2);
v1 = None;
v2 = d2.next()
}
(Some(p1), None) => {
result.push(p1);
v1 = d1.next();
v2 = None
}
(Some(p1 @ (s1, _)), o2 @ Some((s2, _))) if s1 < s2 => {
result.push(p1);
v1 = d1.next();
v2 = o2
}
(o1 @ Some((s1, _)), Some(p2 @ (s2, _))) if s1 > s2 => {
result.push(p2);
v1 = o1;
v2 = d2.next()
}
(Some((s1, t1)), Some((_, t2))) => {
result.push((s1, t1 + t2));
v1 = d1.next();
v2 = d2.next()
}
}
}
}
Note that the match on (v1, v2) should move the values so that each path is enforced to set v1 and v2. Still not as clean as Haskell, but closer.
Variables v1 and v2 move out when creating a tuple in the match expression. You need to modify these variables inside the match, so you can`t borrow them.
With Option<T> you can use take() method:
fn merge(mut l1: Vec<(String, u32)>, mut l2: Vec<(String, u32)>) -> Vec<(String, u32)> {
let mut d1 = l1.drain(..);
let mut d2 = l2.drain(..);
let mut result = Vec::new();
let mut v1 = d1.next();
let mut v2 = d2.next();
loop {
match (v1.take(), v2.take()) {//Takes the value out of the option, leaving a None in its place.
(None, None) => return result,
(None, Some(x)) => {
result.push(x);
v2 = d2.next()
}//v1 is None
(Some(x), None) => {
result.push(x);
v1 = d1.next()
}//v2 is None
(Some(p1), Some(p2)) => {
use std::cmp::Ordering::{Equal, Less, Greater};
match p1.0.cmp(&p2.0) {
Equal => {
result.push((p1.0, p1.1 + p2.1));
v1 = d1.next();
v2 = d2.next();
}
Less => {
result.push(p1);
v1 = d1.next();
v2 = Some(p2);
}//restore v2
Greater => {
result.push(p2);
v1 = Some(p1); //restore v1
v2 = d2.next();
}
};
}
};
}
}
I have altered the code of the last branch to avoid unnecessary borrowing.
Disadvantage of this approach is that you may forget to assign a new value to a variable. I would recommend to return the values from the match expression:
fn merge(mut l1: Vec<(String, u32)>, mut l2: Vec<(String, u32)>) -> Vec<(String, u32)> {
let mut d1 = l1.drain(..);
let mut d2 = l2.drain(..);
let mut result = Vec::new();
let mut v = (d1.next(), d2.next());
loop {
v = match (v.0.take(), v.1.take()) {
(None, None) => return result,
(None, Some(x)) => {
result.push(x);
(None, d2.next())
}
(Some(x), None) => {
result.push(x);
(d1.next(), None)
}
(Some(p1), Some(p2)) => {
use std::cmp::Ordering::{Equal, Less, Greater};
match p1.0.cmp(&p2.0) {
Equal => {
result.push((p1.0, p1.1 + p2.1));
(d1.next(), d2.next())
}
Less => {
result.push(p1);
(d1.next(), Some(p2))
}
Greater => {
result.push(p2);
(Some(p1), d2.next())
}
}
}
};
}
}
Removed unnecessary clones as mentioned by @mcarton