1

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.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
Dandry
  • 495
  • 12
  • 26
  • 1
    You aren't only iterating over the structure, you are also trying to mutate it during the iteration. This is a completely different proposition. – Peter Hall Jun 08 '19 at 13:07
  • *I need to implement the A\* pathfinding algorithm* — no, you don't; just [use one that's already been written](https://docs.rs/petgraph/0.4.13/petgraph/algo/fn.astar.html). – Shepmaster Jun 08 '19 at 13:46
  • @Shepmaster People are perfectly at liberty to study and learn whatever they want. And sometimes "not invented here" is not a syndrome but a blessing. This just recently crossed my mind in the context of Julia Flux, which uses "LearningStrategies.jl" package, which is basically a glorified for loop :) – BitTickler Jun 08 '19 at 13:49
  • @BitTickler I'm responding to the **need** part of the sentence. If OP *wants* to do it, I don't care. It's just not true that they "need" to implement it. – Shepmaster Jun 08 '19 at 13:50
  • @Shepmaster unfortunately, I cannot. This implementation is part my master's thesis - the code will be used along with `wasm-bindgen` and ran in browser. – Dandry Jun 08 '19 at 13:51
  • The duplicate [applied to your question](https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=da7e6cf2ef82e1881e455d5f6c4ab4e2). TL;DR: wrap `current_cell` in curly braces to clearly transfer ownership of it before overwriting it in the loop. – Shepmaster Jun 08 '19 at 13:51
  • @Dandry you are disallowed from using existing code in your thesis? Why are you allowed to use `Vec`, `Rc` or `RefCell` then? I'd be surprised that petgraph wouldn't work in Wasm. – Shepmaster Jun 08 '19 at 13:52
  • I am implementing some algorithms (including the abovementioned A*) in JS, C/C++, C# and Rust. The goal is to compare the performance. – Dandry Jun 08 '19 at 13:54
  • 2
    @Dandry don't get me wrong but using inappropriate tools of the language may affect the performance, if the main purpose is comparing languages for the same algorithm – Ömer Erden Jun 08 '19 at 13:59
  • @Dandry May I humbly suggest you also add Haskell to your comparison? Given it is "alien" to any of the other languages, it would make an interesting topic. – BitTickler Jun 08 '19 at 14:01
  • @Ömer Erden This is indeed a very good point, coming from C# I find Rust quite difficult when it comes to managing ownership and references. I also have other algorithms which operate on matrices and their implementation in Rust was easy. I will take your point into account. – Dandry Jun 08 '19 at 14:03
  • @BitTickler I wish I had time for this. I picked Rust for it's well advertised powers to run in browser using `wasm-bindgen`. And now I struggle with handling structs ;))) – Dandry Jun 08 '19 at 14:05
  • @Dandry piling on to the "bonus suggestions" you are getting, it seems invalid to compare the performance of algorithms between languages that you aren't proficient in (unless somehow that novice nature is part of the thesis, but that seems to conflate too many topics). For example, I wouldn't use `Rc` or `RefCell` to implement this algorithm at all. If I had to implement it myself and couldn't use petgraph, I'd use an arena. – Shepmaster Jun 08 '19 at 14:10
  • You may wish to look at other resources. More open-ended questions and discussions are welcome on [the Rust subreddit](https://www.reddit.com/r/rust/), [the Rust users forum](https://users.rust-lang.org/), or [the Rust Discord server](https://www.rust-lang.org/community). You might also get useful feedback by requesting a [code review](https://codereview.meta.stackexchange.com/questions/5777/a-guide-to-code-review-for-stack-overflow-users). – Shepmaster Jun 08 '19 at 14:11
  • @Dandry I feel you. I gave rust a few spins over the past few years and each time I dropped it again, because it was too much of a diva, distracting me from what I wanted to think about. But Rust is not alone. C++ TMP can also be a distraction, so can too many tiny library dependencies in any language, over having 1 compact implementation. Again my recent flux experience. I kept muttering "nice distraction" each time I got aware of yet another library being in play. It took me 3 days to just find all the "players" lol. – BitTickler Jun 08 '19 at 14:14

0 Answers0