Conflicting lifetime requirements

[phoracek]

Hello folks,

I can imagine this one pops up quite often, but I just can't wrap my head around this for several weeks now. I want to know whether what I'm trying to do is doable at all.

I am trying to implement an on-stack linked list. I use my library to allocate values. Values are stored on the stack, represented by the type Rack64<T>. References to these values are represented as the type Unit<'a, T>. The rest is vanilla Rust.

This is the code:

extern crate heapnotize;

use heapnotize::*;

pub struct List<'a> {
    head: Link<'a>,
    rack: Rack64<Node<'a>>,
}

type Link<'a> = Option<Unit<'a, Node<'a>>>;

struct Node<'a> {
    elem: i32,
    next: Link<'a>,
}

impl<'a> List<'a> {
    pub fn new() -> Self {
        List {
            head: None,
            rack: Rack64::new(),
        }
    }

    pub fn push(&mut self, elem: i32) {
        let new_node = self.rack.must_add(Node {
            elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn push_to_list() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);
    }
}

And this is the failure:

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/list.rs:28:34
   |
28 |         let new_node = self.rack.must_add(Node {
   |                                  ^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 27:5...
  --> src/list.rs:27:5
   |
27 | /     pub fn push(&mut self, elem: i32) {
28 | |         let new_node = self.rack.must_add(Node {
29 | |             elem,
30 | |             next: self.head.take(),
...  |
33 | |         self.head = Some(new_node);
34 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/list.rs:28:24
   |
28 |         let new_node = self.rack.must_add(Node {
   |                        ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime `'a` as defined on the impl at 19:6...
  --> src/list.rs:19:6
   |
19 | impl<'a> List<'a> {
   |      ^^
note: ...so that the expression is assignable
  --> src/list.rs:33:21
   |
33 |         self.head = Some(new_node);
   |                     ^^^^^^^^^^^^^^
   = note: expected `core::option::Option<list::heapnotize::Unit<'a, _>>`
              found `core::option::Option<list::heapnotize::Unit<'_, _>>`

I would be thankful for any hints. Thanks in advance.

[alice]

When you put a lifetime on a field in a struct, that is saying "this lifetime annotates a borrow of a thing stored outside of this struct". However in your case the thing is actually stored inside the struct in rack, not outside of it. Hence the compiler error.

It is not possible to create a self-referential struct (i.e. a struct with references into itself). Consider reading Learn Rust With Entirely Too Many Linked Lists.

[phoracek]

Oh I see! Thanks a lot Alice. Will go through Too Many Linked Lists for sure.

/me moving the rack out and closing this thread.