Loop node.parent() to get list of ancestors

help
1

Background

I have a simple structure that's actually a full binary tree, but I'm using petgraph because I got stuck implementing all the traversals on a binary tree by myself (due to issues with borrow checker).

use petgraph::Graph;

pub struct Layout<'a> {
  graph: LayoutGraph<'a>,
}

pub type LayoutGraph<'a> = Graph<NodeLabel<'a>, ()>;

pub enum NodeLabel<'a> {
  Internal(SliceDirection),
  Leaf(&'a RgbImage),
}

To make working with the layout easier, I created another data structure:

pub struct LayoutNode<'a> {
  index: NodeIndex,
  layout: &'a Layout<'a>,
}

impl LayoutNode<'_> {
  pub fn node_label(&self) -> &NodeLabel { //…

  pub fn children(&self) -> Option<(LayoutNode, LayoutNode)> { //…

  pub fn parent(&self) -> Option<LayoutNode> { //…
}

LayoutNode mostly proxies those calls to Layout and Layout then operates on Graph.

Problem

Now, what I want to achieve is that given an arbitrary LayoutNode, I want to return its ancestors – essentially looping a call to .parent() until it returns None. I tried to implement an iterator, but that didn't work out because my Item would need to have a named lifetime and that isn't supported right now. A streaming iterator doesn't work for the same reason.

So then I was like, alright, let's just collect them into a VecDeque. But I just can't seem to find a way for the borrow checker to let me do that. :frowning:

let leaf_node = layout.leaf_nodes().next().unwrap();
let mut iter = leaf_node;
let mut ancestors = VecDeque::new();

while let Some(node) = iter.parent() {
  ancestors.push_front(node);
  iter = node;
}

This doesn't work because

error[E0506]: cannot assign to `iter` because it is borrowed
  --> src/main.rs:26:5
   |
24 |   while let Some(node) = iter.parent() {
   |                          ------------- borrow of `iter` occurs here
25 |     ancestors.push_front(node);
26 |     iter = node;
   |     ^^^^^^^^^^^
   |     |
   |     assignment to borrowed `iter` occurs here
   |     borrow later used here

error[E0382]: use of moved value: `node`
  --> src/main.rs:26:12
   |
24 |   while let Some(node) = iter.parent() {
   |                  ---- move occurs because `node` has type `LayoutNode<'_>`, which does not implement the `Copy` trait
25 |     ancestors.push_front(node);
   |                          ---- value moved here
26 |     iter = node;
   |            ^^^^ value used here after move

Given a Layout that exists in the same scope, I don't see a reason why I couldn't collect all those ancestry nodes into a vec.

How could I grab a parent of a node without borrowing the node itself? Or is there another way to achieve what I'm trying to do?

I feel like maybe I should use something like Rc, but thinking about ownership management still gives me a lot of trouble.

2

Well the reason you get the error is because the lifetime elision rules created the following lifetimes:

impl<'a> LayoutNode<'a> {
  pub fn node_label<'b>(&'b self) -> &'b NodeLabel<'b> { //…

  pub fn children<'b>(&'b self) -> Option<(LayoutNode<'b>, LayoutNode<'b>)> { //…

  pub fn parent<'b>(&'b self) -> Option<LayoutNode<'b>> { //…
}

So since the return values have their lifetimes tied to the self paramter, they cannot outlive the self parameter. It sounds like you probably wanted the return lifetimes to all be 'a instead.

Still, are you sure you want lifetimes here at all? When you have lifetimes like this, then it means that whatever values your references point at are:

  1. Not stored in the same struct as the reference, but in an entirely separate variable.
  2. Immutable and immovable while the structs with the references exist.

If the two above rules are violated, you get a borrow checker error. For example, if any of the layout types are used after the RgbImage they point at goes out of scope, that wont work. Similarly, the Layout object cannot be destroyed or modified while the LayoutNode exists.

2 Likes
3

Thank you, that makes a lot of sense! I'll change the lifetimes and see if I run into any problems.

On the matter of wanting lifetimes like these: I think it makes sense in my use case. I'm writing a Wasm program and those RgbImages are created in the main function of it, they're almost like the input data. I'm going to generate thousands of layouts, so I figured I don't want to copy the images for each of them – they occupy huge chunks of memory and Wasm memory is never shrunk.

I don't really understand when that would be a problem. :thinking: Is it related to what you said about variables going out of scope?

Now that's something I didn't think about. I'll definitely want to call methods on those images that mutate them. I guess in this situation RefCell might come in handy?

5

I changed the lifetimes in LayoutNode, but one error remains. :thinking:

impl<'a> LayoutNode<'a> {
  pub fn node_label(&self) -> &'a NodeLabel { //…

  pub fn children(&self) -> Option<(LayoutNode<'a>, LayoutNode<'a>)> { //…

  pub fn parent(&self) -> Option<LayoutNode<'a>> { //…

error[E0382]: use of moved value: `node`
  --> src/main.rs:26:12
   |
24 |   while let Some(node) = iter.parent() {
   |                  ---- move occurs because `node` has type `LayoutNode<'_>`, which does not implement the `Copy` trait
25 |     ancestors.push_front(node);
   |                          ---- value moved here
26 |     iter = node;
   |            ^^^^ value used here after move
6

You should probably be putting an <'a> on that NodeLabel as well.

The remaining error is unrelated to lifetimes.

It might not be a problem in your case. But many attempts at writing tree structures violate this rule by having child nodes be owned by their parents, then adding a parent reference to the child node. You have avoided that by using petgraph.

RefCell could be a solution.

7

I updated the code a bit and it works now.

  let leaf_node = layout.leaf_nodes().next().unwrap();
  let mut iter = Some(leaf_node);
  let mut ancestors = VecDeque::new();

  while let Some(node) = iter {
    let next = node.parent();
    ancestors.push_front(node);
    iter = next;
  }

I guess the problem was that while let Some(node) = iter.parent() borrowed iter for the whole while let block.

Thanks for the help, your remarks about the lifetimes will certainly help me with thinking about ownership in the future!

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.