Rust: guidance on recursive function mutating vectors

user_2375119 0
Viewed 170

I need some guidance how to approach a recursive function that needs to mutate the vectors that are provided to it from previous recursion level.

fn solve (graph: &CompleteGraph) -> Path {
    let mut path = Path { cities: Vec::<usize>::new() };
    let mut visited = Visited { cities: vec!(false; graph.numcities) };
    let since = Instant::now();

    let bestpath = Path { cities: trivialpath(&graph) };
    let besttotal = pathtotal(&bestpath.cities, &graph);

    let (path, visited, bestpath, besttotal) = solverec(path, 0.0, visited, since, bestpath, besttotal);

    return bestpath;
}

fn solverec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, besttotal: f64) -> (Path, Visited, Path, f64) {
    
    if since.elapsed() > Duration::from_secs(5) {
        return (path, visited, bestpath, besttotal);
    }
    if pathtotal > besttotal {
        return (path, visited, bestpath, besttotal);
    }

    for nextcity in 0..visited.cities.len() {
        if visited.cities[nextcity] == false {
            path.cities.push(nextcity);
            visited.cities[nextcity] = true;
            let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, bestpath, besttotal);
            visited.cities[nextcity] = false;
            path.cities.pop();
        }
    }

    unimplemented!();
}

Compiler complains a lot:

error[E0382]: borrow of moved value: `visited`
   --> tsp-arekbulski-05-brute.rs:123:6
    |
113 | ...verec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, best...
    |                                       ------- move occurs because `visited` has type `Visited`, which does not implement the `Copy` trait
...
123 | ...isited.cities[nextcity] == false {
    |         ^^^^^^^^^^^^^^ value borrowed here after move
...
126 | ... (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, bestpat...
    |                                                                               ------- value moved here, in previous iteration of loop

error[E0596]: cannot borrow `path.cities` as mutable, as `path` is not declared as mutable
   --> tsp-arekbulski-05-brute.rs:124:4
    |
113 | fn solverec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, b...
    |              ---- help: consider changing this to be mutable: `mut path`
...
124 |             path.cities.push(nextcity);
    |             ^^^^^^^^^^^ cannot borrow as mutable

error[E0382]: borrow of moved value: `path`
   --> tsp-arekbulski-05-brute.rs:124:4
    |
113 | fn solverec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, b...
    |              ---- move occurs because `path` has type `Path`, which does not implement the `Copy` trait
...
124 |             path.cities.push(nextcity);
    |             ^^^^^^^^^^^ value borrowed here after move
125 |             visited.cities[nextcity] = true;
126 |             let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, best...
    |                                                                 ---- value moved here, in previous iteration of loop

error[E0596]: cannot borrow `visited.cities` as mutable, as `visited` is not declared as mutable
   --> tsp-arekbulski-05-brute.rs:125:4
    |
113 | fn solverec (path: Path, pathtotal: f64, visited: Visited, since: Instant, bestpath: Path, b...
    |                                          ------- help: consider changing this to be mutable: `mut visited`
...
125 |             visited.cities[nextcity] = true;
    |             ^^^^^^^^^^^^^^ cannot borrow as mutable

error[E0382]: use of moved value: `bestpath`
   --> tsp-arekbulski-05-brute.rs:126:89
    |
113 | ...sited, since: Instant, bestpath: Path, besttotal: f64) -> (Path, Visited, Path, f64) {
    |                           -------- move occurs because `bestpath` has type `Path`, which does not implement the `Copy` trait
...
126 | ...ec(path, pathtotal, visited, since, bestpath, besttotal);
    |                                                 ^^^^^^^^ value moved here, in previous iteration of loop

error[E0596]: cannot borrow `visited.cities` as mutable, as `visited` is not declared as mutable
   --> tsp-arekbulski-05-brute.rs:127:4
    |
126 |             let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, best...
    |                        ------- help: consider changing this to be mutable: `mut visited`
127 |             visited.cities[nextcity] = false;
    |             ^^^^^^^^^^^^^^ cannot borrow as mutable

error[E0596]: cannot borrow `path.cities` as mutable, as `path` is not declared as mutable
   --> tsp-arekbulski-05-brute.rs:128:4
    |
126 |             let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, best...
    |                  ---- help: consider changing this to be mutable: `mut path`
127 |             visited.cities[nextcity] = false;
128 |             path.cities.pop();
    |             ^^^^^^^^^^^ cannot borrow as mutable

error: aborting due to 7 previous errors; 7 warnings emitted
borrow-checker rust recursion arrays
1 Answers
        let (path, visited, bestpath, besttotal) = solverec(path, pathtotal, visited, since, bestpath, besttotal);

This consumes the 4 function-local variables, and shadows them with 4 loop-local variables.

So the loop can only execute once, afterwards there's nothing to use: loop-local variables are dropped at the end of the loop.

You may have tried to use this because a mass-reassignment

(path, visited, bestpath, besttotal) = ...

did not work.

And sadly, no it does not, reassignments are not patterns so you can't use destructuring reassignments, and no a re-declaration does not fix it. You have to make the function-local bindings mut, then reassign explicitly from the loop-local results you got from solverec e.g.

fn solverec (mut path: Path, mut pathtotal: f64, mut visited: Visited, mut since: Instant, mut bestpath: Path, mut besttotal: f64) -> (Path, Visited, Path, f64) {
    // ...
        let r = solverec(path, pathtotal, visited, since, bestpath, besttotal);
        path = r.0;
        visited = r.1;
        bestpath = r.2;
        besttotal = r.3;

I would recommend either extracting these to a single structure (possibly just a typedef e.g. type Solution = (Path, Visited, Path, f64)) so they can be manipulated or reassigned as a unit rather than piecemeal, or restructuring the entire thing somehow.

user_81821180
Related