Stubborn lifetime related compile error

[spike]

This code is simplest thing that illustrates my problem. After almost 2 days I cant get the compiler to accept this, and yet the idea is quite simple;

• pass an element, containing a string slice, into a Doc constructor
• the string slice is copied into a string 'owned' by the doc and a new slice created accordingly
• add the new slice into the doc.elements vector
  ..all lifetimes are the same indicating there cannot be any dangling references

pub type Element<'a> = Option<&'a str>;
pub type Elements<'a> = Vec<Element<'a>>;
pub type ElementIndex = usize;

pub struct Doc<'a> {
    pub xml_doc: String,
    pub strings: Vec<String>,
    pub elements: Elements<'a>,
}

impl<'a> Doc<'a> {
    pub fn new_element(&mut self, mut el: Element<'a>) -> ElementIndex {
        let index: ElementIndex = self.elements.len();

        if let Some(text_val) = el {
            let text_val = String::from(text_val);
            let idx = self.strings.len();
            self.strings.push(text_val);
            el = Some(self.strings[idx].as_str());
        }
        self.elements.push(el);
        index
    }

    pub fn new_with_capacity(xml_doc: String, capacity: usize) -> Self {
        let mut doc = Doc {
            xml_doc,
            strings: Vec::new(),
            elements: Vec::with_capacity(capacity),
        };
        doc.new_element(Some("[document]"));
        doc
    }
}

pub fn main() {
    Doc::new_with_capacity(String::from("example"), 1024);
}

here is the project on rust playground or repl.it if you prefer

I'm getting this compile error;

error[E0505]: cannot move out of doc because it is borrowed
--> src/main.rs:35:9
|
11 | impl<'a> Doc<'a> {
| -- lifetime 'a defined here
...
29 | let mut doc = Doc { // possibly remove mut and line below
| ------- binding doc declared here
...
34 | doc.new_element(Some("[document]")); // possibly remove this line
| --- borrow of doc occurs here
35 | doc
| ^^^
| |
| move out of doc occurs here
| returning this value requires that doc is borrowed for 'a

Why does the borrow last beyond line 34? Note, cloning Doc is not an option.

The interesting thing is that if I remove line 34 and the 'mut' on line 29 and add in line 41 in the main function.. it compiles! But if I then try to turn main() into a Doc constructor within the Doc impl, eg;

    pub fn main() -> Self {
        let mut doc = Doc::new_with_capacity(String::from("example"), 1024);
        doc.new_element(Element::new_node("[document]", ""));
        doc
    }

the same problem comes back.

I suspect the lifetime annotations on lines 11 to 14, but after 2 days of trying I can find no combinations of anything that works. I also checked the Polonius problem cases but they don't seem to apply here. Is this an 'arena' issue?

[Schard]

You're trying to take a reference to a String owned by the struct Doc<'a>, which would require you to borrow it and thus also the struct for 'a, which would mean borrowing the struct forever.
Your problem boils down to this.

[theemathas]

You're trying to create a self-referential struct. You can kinda do this with the ouroboros crate or one of the similar crates. For more information, see Self-referential types for fun and profit | More Stina Blog!

[theemathas]

There's also an issue where, when you append to the strings vec, the vec will sometimes reallocate, moving the Strings to a new location. I think you can work around that with the elsa crate.

[spike]

Thanks for the help. I take the point about self referential structs. With respect to Vec re-sizing, isn't it a case of the Vec itself resizing but the strings themselves remaining on the same place on the heap?

[quinedot]

Dangling pointers and the compiler not distinguishing pointers to the heap and pointers to the stack is often used as a shorthand to explain why something like a self-referencial struct fails to compile. But this gives the false impression that if just that distinction existed, everything would be fine.

But in reality, if Doc<'a> becomes self-referencial, it has to be borrowed forever for deeper reasons than dangling pointers. Let's say it didn't become borrowed forever, so you could still obtain a fresh &mut doc: Doc<'a> after Doc<'a> becomes self-referencial.

Then you could simply

doc.strings  = Vec::new();

And all the references in doc.elements would dangle.

---

The real limitation is that places can not be used in an exclusive manner (moved, taking a &mut, destructed...) while they are borrowed. This is the approximation that prevents data races, dangling pointers, and so on. Thus if you borrow yourself, you can never use yourself in an exclusive manner again.

[theemathas]

Yes. But Vec's API does not make this distinction. Hence, the elsa crate.

[spike]

Yes I think I see that. I think the solution to my problem rather than use &str to reference my strings, I could use owned instances of something this like instead;

struct StrRef {
    string_id: usize,
    start: usize,
    len: usize
}

this would enable me to remove all lifetime annotations, or just go back to using 'owned' strings, which in my case means potentially thousands of string being copied.. (hence the emphasis on references)

[quinedot]

Yes, using some sort of offset / span / range / index / key / etc, is a common way to avoid self-referencial structs.