5

I'm making a Combinatory Optimization project to learn Rust and I've got a problem I cannot resolve myself...

I've got 2 functions :

pub fn get_pareto_front_offline<'a>(scheduling_jobs: &'a Vec<Vec<u32>>, costs_vector: &'a Vec<(u32, u32)>) -> Vec<(&'a Vec<u32>, &'a (u32, u32))> {
    // ...
}

and

pub fn pareto_approach_offline<'a>(list_of_jobs: &'a mut Vec<Vec<u32>>, neighborhood: &'a mut Vec<Vec<u32>>, costs: &'a Vec<(u32, u32)>) -> Vec<(&'a Vec<u32>, &'a (u32, u32))> {
    let pareto_front = get_pareto_front_offline(neighborhood, costs);

    loop {
        if pareto_front == vec![] {
            break;
        }

        neighborhood.clear();

        for front in pareto_front.iter() {
            neighborhood.push((front.0).clone());
        }
    }

    pareto_front
}

I've got a problem because the compiler tells me:

cannot borrow '*neighborhood' as mutable because it is also borrowed as immutableat line 15 col 9
cannot borrow '*neighborhood' as mutable because it is also borrowed as immutableat line 19 col 13
Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
WebTogz
  • 59
  • 1
  • 3

2 Answers2

6

You're trying to do something fundamentally impossible.

When you call get_pareto_front_offline, you pass a re-borrowing of neighborhood into that function. This re-borrow must be maintained in order for pareto_front to remain valid. In other words, as long as pareto_front exists, the compiler will not allow you to access neighborhood in any fashion whatsoever.

This is a good thing, because you then proceed to try and clear our neighborhood, which would almost certainly invalidate pareto_front, likely leading to use-after-free and corrupting your program's state.

It's not clear what it is you're attempting to do; but you cannot do it this way.

As an aside, even if it compiled, that loop would probably never finish running: your termination condition (pareto_front == vec![]) will never be satisfied because you never modify pareto_front; it'll either stop immediately, or run forever.

The simplest way to get out from under borrowing problems is to make copies of things, so that you don't need a long-lived borrow; if get_pareto_front_offline returned a Vec<(Vec<u32>, (u32, u32))> instead, you wouldn't have this issue. That, or modify to code to not touch neighborhood once you call get_pareto_front_offline.

DK.
  • 55,277
  • 5
  • 189
  • 162
  • Thank you! Your solution is exactly what I'm thinking... I'm trying to make an optimized solution to this problem, but with my "level" in Rust, it's really hard :-/ – WebTogz Nov 29 '15 at 17:49
  • In situations like this you often need a specialized collection. I believe that `VecDeque` can solve the problem, (but I may be wrong) https://doc.rust-lang.org/std/collections/struct.VecDeque.html Alternatively you can use channels https://doc.rust-lang.org/std/sync/mpsc/ – nielsle Nov 30 '15 at 18:08
6

In this case the compiler helped you avoid a use-after-free error by not accepting the code. The problem can be reduced to this piece of code:

fn main() {
    let mut v = vec![0,1,2,3];
    let r = &v[2];
    v.push(5);
    println!("{}", *r); // oops
}

A Vec has a length and a capacity. If length equals capacity it means that there is no space left in the buffer for a new element. In such a case push involves moving all the elements to a new buffer that is big enough to store new data. But this action would invalidate the reference r because r still stores the old and now invalid address of the 3rd vector element. This is exactly the kind of error Rust is trying to prevent with the borrowing rules and the borrow checker.

But if you just add new stuff to the vector, it won't change the order of the elements that were already in there. Maybe you could just replace some references to Vec elements with indices which stay the same regardless of where the Vec elements are stored.

Some aside suggestions: Prefer &[T] over &Vec<T> for function arguments. It's more flexible. Also, pareto_front == vec![] can be replaced with pareto_front.is_empty().

sellibitze
  • 27,611
  • 3
  • 75
  • 95