Check TLDR at the bottom if you are not interested in me rambling about stuff I don't understand :).

I am trying to implement A-star pathfinding alg in Rust. Just a basic version. I don't want to use Rc and my nodes store *const (raw pointer) to previous Node (prev: const* Node) so that I can retrieve the shortest path (solution).

struct Node {
    position: Position,
    // NonNull also works I guess
    previous: Option<*const Node>
}

Also I am using PriorityQueue (crate link) where I store my nodes. My knowledge is very limited regarding memory management and low-level stuff.

Okay now I will first talk a bit what happens inside my program to better clarify what I am asking.

To my understanding, my nodes get stored/moved into PriorityQueue that is actually a HashMap.

PriorityQueue -> ... -> Vec<Bucket<K, V>> -> Bucket { hash: HashValue, key: K, value: V }

So they get stored on the heap, but the thing is that my nodes first get created on stack (I never heap allocate them using Box, or their lifetime is just bound to the stack I guess?).

Then their previous field gets assigned a raw pointer to the previous node *const Node and then they get moved/pushed in the vector that is returned from the function (now they are on the heap).

Nodes: stack -> Vec

Code of function that returns that Vec:

fn neighbours(&self, maze: &Maze) -> Vec<Node> {
    let offset_x: [isize; 8] = [-1, -1, 0, 1, 1, 1, 0, -1];
    let offset_y: [isize; 8] = [0, -1, -1, -1, 0, 1, 1, 1];

    let mut neighbours = Vec::new();

    for i in 0..8 {
        let nx = self.position.x()   offset_x[i];
        let ny = self.position.y()   offset_y[i];

        if Node::is_valid((nx, ny), maze) {
            let (nx, ny) = (nx as usize, ny as usize);

            let mut node = Node::new(Position((nx, ny)), self, maze.end().unwrap());

            node.previous = Some(self as *const _);
            neighbours.push(node);
        } else {
            continue;
        }
    }
    neighbours
}

Keep in mind that previous node is on stack when we assign raw pointer to it (*const Node) to our newly created nodes. (Also sidenote, the Previous node was originally popped from PriorityQueue and moved into a variable on a stack)

Previous: stack

After that, (nodes) from that vector they get moved into PriorityQueue we will call this queue open (or just get dropped but that is not important).

Nodes: Vec -> open: PriorityQueue

So far so good because Previous node is not yet moved and the raw pointer should still point to it.

But after those nodes get into PriorityQueue the Previous node gets moved also into the other PriorityQueue lets call that queue closed.

Previous: stack -> closed: PriorityQueue

Now my question finally is, what happens to the raw pointer that pointed to the previous nodes, is this undefined behaviour, meaning that now pointer is no longer pointing to that allocation?

TLDR:

How memory works when non Copy value gets moved (is it still on the same memory address)? Does only the ownership of the value changes and the value stays on the same memory address, or it changes memory address, gets new memory allocation and just gets copied there? If this might be a bit too general, what happens to my Node struct then when it gets moved, will those pointers that point to previous Node that got moved be invalid?

CodePudding user response：

When a node is moved, it as actually stored somewhere else, thus its address is not the same (in general, even if some optimisations could prevent that, but nothing is guaranteed).

The minimal example below shows this; the initial nodes are created on the stack, then we move them into the heap-allocated storage of a vector. Displaying the address of all these nodes shows that these addresses are not the same indeed.

The previous member of n1, initialised with the address of n0 when it was on the stack, becomes a dangling pointer as soon as n0 is moved to the vector. The location of n0 could have been reused for some other variables, and what happens when accessing this memory location through the pointer is actually undefined.

That's why dereferencing a raw pointer is an unsafe operation in Rust (and that's also probably why Rust exists).

Independently of the Copy trait, the difference between copying a value and moving a value is subtle. In this case, Node is only made of basic types (an integer and a raw pointer, eventually null if None) and does not perform memory management with this pointer (as Vec does with the pointer it contains). Thus, moving a Node happens to be physically the same thing as copying it: more or less a bitwise copy of the members of the struct as if Node was Copy.

When it comes to a Vec that we would like to move for example, the move operation would have been much more interesting. The new location of the Vec (where it is moved-to) keeps the pointer (bitwise copy) to the heap-allocated storage as known in the initial location (where it is moved-from). Then, this moved-from location is not considered anymore to be the owner of this heap-allocated storage: we have transferred ownership of the heap-allocated storage between the moved-from and moved-to locations, but we did not have to duplicate this heap-allocated storage. This is the main interest of the move operation over the copy/clone (saving the duplication of heap-allocated storage by simply transferring ownership). This situation is visible in the example below, when nodes is moved to nodes_again: the Vec itself is moved, but the Nodes it contains are not. This section of « The Rust Programming Language » explains very well this situation, using a String instead of a Vec.

#[derive(Debug)]
struct Node {
    value: i32,
    previous: Option<*const Node>,
}

fn main() {
    let n0 = Node {
        value: 0,
        previous: None,
    };
    let n1 = Node {
        value: 1,
        previous: Some(&n0 as *const _),
    };
    println!("n0 at {:?}: {:?}", &n0 as *const _, n0);
    println!("n1 at {:?}: {:?}", &n1 as *const _, n1);
    println!("~~~~~~~~");
    let nodes = vec![n0, n1];
    println!("nodes at {:?}", &nodes as *const _);
    for (i, n) in nodes.iter().enumerate() {
        println!("nodes[{}] at {:?}: {:?}", i, n as *const _, n);
    }
    println!("~~~~~~~~");
    let nodes_again = nodes;
    println!("nodes_again at {:?}", &nodes_again as *const _);
    for (i, n) in nodes_again.iter().enumerate() {
        println!("nodes_again[{}] at {:?}: {:?}", i, n as *const _, n);
    }
}
/*
n0 at 0x7ffd2dd14520: Node { value: 0, previous: None }
n1 at 0x7ffd2dd14500: Node { value: 1, previous: Some(0x7ffd2dd14520) }
~~~~~~~~
nodes at 0x7ffd2dd144e8
nodes[0] at 0x558bad50fba0: Node { value: 0, previous: None }
nodes[1] at 0x558bad50fbb8: Node { value: 1, previous: Some(0x7ffd2dd14520) }
~~~~~~~~
nodes_again at 0x7ffd2dd14490
nodes_again[0] at 0x558bad50fba0: Node { value: 0, previous: None }
nodes_again[1] at 0x558bad50fbb8: Node { value: 1, previous: Some(0x7ffd2dd14520) }
*/