How to bind multiple fields of a boxed struct without getting "use moved value" error?

Question

I'm trying to code a generic recursive data structure. As it turns out, I can't as I'm hitting a wall when I want to access more than one field of an owned struct value.

I define a struct that will hold a list:

struct ListNode<T> {
    val: T,
    tail: List<T>
}

struct List<T>(Option<Box<ListNode<T>>>);

The empty list is represented by List(None).

I want to be able to append to a list:

impl<T> List<T> {
    fn append(self, val: T) -> List<T> {
        match self {
            List(None) => List(Some(Box::new(ListNode {
                val: val,
                tail: List(None),
            }))),
            List(Some(node)) => List(Some(Box::new(ListNode {
                val: node.val,
                tail: node.tail.append(val),
            }))),
        }
    }
}

This fails with an understandable error:

error[E0382]: use of moved value: `node`
  --> src/main.rs:17:23
   |
16 |                 val: node.val,
   |                      -------- value moved here
17 |                 tail: node.tail.append(val),
   |                       ^^^^^^^^^ value used here after move
   |
   = note: move occurs because `node.val` has type `T`, which does not implement the `Copy` trait

I looked for ways to use more than one field of a struct and I found Avoiding partially moved values error when consuming a struct with multiple fields, so I'll do that:

List(Some(node)) => {
    let ListNode {
        val: nval,
        tail: ntail,
    } = *node;
    List(Some(Box::new(ListNode {
        val: nval,
        tail: ntail.append(val),
    })))
}

Well, nope, still the same error. Apparently this doesn't work like in the link anymore.

I've also tried using refs:

List(Some(node)) => {
    let ListNode {
        val: ref nval,
        tail: ref ntail,
    } = *node;
    List(Some(Box::new(ListNode {
        val: *nval,
        tail: (*ntail).append(val),
    })))
}

This time the deconstruction passes, but the creation of the new node fails with:

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:21:26
   |
21 |                     val: *nval,
   |                          ^^^^^ cannot move out of borrowed content

error[E0507]: cannot move out of borrowed content
  --> src/main.rs:22:27
   |
22 |                     tail: (*ntail).append(val),
   |                           ^^^^^^^^ cannot move out of borrowed content

Am I missing something obvious here? If not, what is the proper way to access multiple fields of a struct that is not passed by reference? I'm using Rust 1.1.

Answer 1

There's some weird interaction with Box going on. You need to add an intermediate let statement that unwraps the box.

List(Some(node)) => {
    let node = *node; // this moves the value from the heap to the stack
    let ListNode { val, tail } = node; // now this works as it should
    List(Some(Box::new(ListNode { val: val, tail: tail.append(value) })))
}

Note that I renamed your function argument to value, so I could write the destructuring in the short form without renaming.

Try it out in the playground.

Answer 2

Non-lexical lifetimes, availing starting in Rust 2018, allows your original code to compile as-is:

struct ListNode<T> {
    val: T,
    tail: List<T>
}

struct List<T>(Option<Box<ListNode<T>>>);

impl<T> List<T> {
    fn append(self, val: T) -> List<T> {
        match self {
            List(None) => List(Some(Box::new(ListNode {
                val: val,
                tail: List(None),
            }))),
            List(Some(node)) => List(Some(Box::new(ListNode {
                val: node.val,
                tail: node.tail.append(val),
            }))),
        }
    }
}

fn main() {}