Dandry
Dandry

Reputation: 515

Iterate over linked structs wrapped in Rc<T> and update them

I need to implement the A* pathfinding algorithm in Rust. The algorithm processes particular cells and links with one another using a parent_cell field. In the end, when the destination cell is found, the path is the way from the destination cell to the start cell. I need to capture each cell of the path in a Vec. I have created a simplified piece of code to reflect my issue:

use std::cell::RefCell;
use std::rc::Rc;

struct AstarCell {
    parent_cell: Option<Rc<RefCell<AstarCell>>>,
}

fn main() {
    let start = Rc::new(RefCell::new(AstarCell { parent_cell: None }));
    let path_cell_1 = Rc::new(RefCell::new(AstarCell {
        parent_cell: Some(Rc::clone(&start)),
    }));
    let path_cell_2 = Rc::new(RefCell::new(AstarCell {
        parent_cell: Some(Rc::clone(&path_cell_1)),
    }));
    let destination = Rc::new(RefCell::new(AstarCell {
        parent_cell: Some(Rc::clone(&path_cell_2)),
    }));

    let mut path_list: Vec<Rc<RefCell<AstarCell>>> = Vec::new();

    let mut current_cell = destination.clone();

    while let Some(parent_cell) = current_cell.borrow().parent_cell {
        path_list.push(Rc::clone(&parent_cell));
        current_cell = Rc::clone(&parent_cell);
    }
}

This does not work, as the borrow checker gets in my way:

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:24:35
   |
24 |     while let Some(parent_cell) = current_cell.borrow().parent_cell {
   |                    -----------    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |                    |              |
   |                    |              cannot move out of borrowed content
   |                    |              help: consider borrowing here: `&current_cell.borrow().parent_cell`
   |                    data moved here
   |
note: move occurs because `parent_cell` has type `std::rc::Rc<std::cell::RefCell<AstarCell>>`, which does not implement the `Copy` trait
  --> src/main.rs:24:20
   |
24 |     while let Some(parent_cell) = current_cell.borrow().parent_cell {
   |                    ^^^^^^^^^^^

error[E0506]: cannot assign to `current_cell` because it is borrowed
  --> src/main.rs:26:9
   |
24 |     while let Some(parent_cell) = current_cell.borrow().parent_cell {
   |                                   ---------------------           - ... and the borrow might be used here, when that temporary is dropped and runs the destructor for type `std::cell::Ref<'_, AstarCell>`
   |                                   |
   |                                   borrow of `current_cell` occurs here
   |                                   a temporary with access to the borrow is created here ...
25 |         path_list.push(Rc::clone(&parent_cell));
26 |         current_cell = Rc::clone(&parent_cell);
   |         ^^^^^^^^^^^^ assignment to borrowed `current_cell` occurs here
   |
   = note: The temporary is part of an expression at the end of a block. Consider adding semicolon after the expression so its temporaries are dropped sooner, before the local variables declared by the block are dropped.

I tried to play with borrowing using & as the compiler suggests but it feels like it's not the right approach.

Upvotes: 1

Views: 47

Answers (0)

Related Questions