Factory method: instance does not live long enough

Question

I'm developing a word generator in Rust. The application consists of two main structs: Letter and Alphabet.

Letter consists of a single character and rules concerning its relationship with other letters.

Alphabet contains vectors for vowels and consonants as well as a hashmap with references to the letters in those vectors. This is done so that rules of a letter can be retrieved in O(1) time.

I've created a factory method to read the alphabet from a json string (code below) but I'm getting an error stating the alphabet instance does not live long enough.

src/word_generator/alphabet.rs:47:6: 47:14 error: alphabet does not live long enough src/word_generator/alphabet.rs:47 alphabet.add_letter(letter);

src/word_generator/alphabet.rs:26:40: 55:3 note: reference must be valid for the anonymous lifetime #1 defined on the block at 26:39... src/word_generator/alphabet.rs:26 pub fn from_json(json: &str)->Alphabet{

note: ...but borrowed value is only valid for the block suffix following statement 3 at 40:37 src/word_generator/alphabet.rs:40 let mut alphabet = Alphabet::new(); src/word_generator/alphabet.rs:41

I understand the error (I hope) but I don't understand why it happens. Why is the instance of Alphabet, returned by the function new(), borrowed by the variable alphabet? Isn't this a move operation?

pub struct Alphabet<'a>{
    pub vowels: Vec<Letter>,
    pub consonants: Vec<Letter>,
    letters: HashMap<char,&'a Letter>
}

impl<'a> Alphabet<'a>{

    pub fn new()->Alphabet<'a>{

        return Alphabet{
            vowels: Vec::new(),
            consonants: Vec::new(),
            letters: HashMap::new()
        }

    }

    pub fn from_json(json: &str)->Alphabet{

        let data :Json = match Json::from_str(json){
            Ok(_data)=>_data,
            Err(_err)=>panic!("Invalid JSON provided")
        };

        let letters = match data.as_array(){
            Some(_letters)=>_letters,
            None=>panic!("Expected JSON\'s root to be an array but found a different structure.")
        };

        let mut it = letters.iter();

        let mut alphabet = Alphabet::new();

        loop {
            match it.next(){
                Some(x) =>{

                    let letter : Letter= json::decode(&(x.to_string())).unwrap();
                    alphabet.add_letter(letter);

                },
                None => break,
            }
        }

        return alphabet
    }

    fn add_letter(&'a mut self,ref l: Letter){

        match l.letter_type {
            LetterType::Vowel =>{
                self.vowels.push(l.clone());
                self.letters.insert(l.value, &self.vowels.last().unwrap());
            },
            LetterType::Consonant =>{ 
                self.consonants.push(l.clone());
                self.letters.insert(l.value, &self.consonants.last().unwrap());
            }
        }

    }
}

P.S.: I'm very new to Rust so any suggestions for improvement to the code are most welcome.

Answer 1

Here's a smaller example that probably is where you started:

use std::collections::HashMap;

struct Letter;

struct Alphabet<'a>{
    vowels: Vec<Letter>,
    letters: HashMap<u8, &'a Letter>
}

impl<'a> Alphabet<'a> {
    fn add(&mut self, l: Letter) {
        self.vowels.push(l);
        self.letters.insert(42, &self.vowels.last().unwrap());
    }
}

fn main() {}

You then followed the compiler error¹:

<anon>:12:46: 12:52 error: cannot infer an appropriate lifetime for lifetime parameter 'a in function call due to conflicting requirements
<anon>:12         self.letters.insert(42, &self.vowels.last().unwrap());
                                                       ^~~~~~
<anon>:10:5: 13:6 help: consider using an explicit lifetime parameter as shown: fn add(&'a mut self, l: Letter)

And continued on, until you got something like this:

use std::collections::HashMap;

struct Letter;

struct Alphabet<'a>{
    vowels: Vec<Letter>,
    letters: HashMap<u8, &'a Letter>
}

impl<'a> Alphabet<'a> {
    fn new() -> Alphabet<'a> {
        Alphabet { vowels: Vec::new(), letters: HashMap::new() }
    }

    fn add(&'a mut self, l: Letter) {
        self.vowels.push(l);
        self.letters.insert(42, &self.vowels.last().unwrap());
    }

    fn parse() -> Alphabet<'a> {
        let mut a = Alphabet::new();
        a.add(Letter);
        a
    }
}

fn main() {}

The root problem is that you cannot have references to your own members ². In the general case, whenever you moved the structure, then the memory location of all the member variables would change, invalidating all the references. This is a bad thing, and Rust would stop you.

The error message you are getting states that there's no possible lifetime that can satisfy what you want — the reference is only valid while the struct doesn't move, but you want to return the struct from the method, moving it.

"But wait!" you say, "I have a Vec and the contents of the Vec are on the heap and won't move!". While technically true (the best kind of true), Rust doesn't track things at that fine-grained of a level.

The general solution here would be to split your structure into two parts. Parse everything from JSON into an Alphabet struct with just the Vecs. Then pass that struct (likely by reference, maybe by value) to a AlphabetSoup struct. That struct can create the HashMap all at once and provide a place to cache your values.

¹ Newer compilers actually removed this suggestion because the false-positive rate was too high and it introduced more confusion than it helped.

² You actually can have references to your own members, but you can then never move the object, which makes it impractical for most cases.