How do I tell the compiler a lifetime is long enough?


#1

I am trying to implement a very simple symbol table, that holds symbol name bytes in a single Vec<u8> and handles out opaque Copy-able “symbols” to be used in the rest of the program. I suppose that the problem is that the compiler doesn’t know that the bytes in the Vec<u8> (that is part of the struct SymbolTable) will live at least as the struct itself and I don’t know how to tell it.

Code here: https://is.gd/lG3AlE

(Or the error is a completely different one and I don’t grok lifetimes at all… g)


#2

Mm. I now understand that the compiler is saving my day. The vector data can move and change address so what I was trying to do (keep the &str alive) is wrong. The new question is “what’s the right way to do what I wanted to do?”


#3

It depends on what your constraints are. You could simply store the strings twice like the lalrpop-intern crate does. More complicated solutions could use a typed arena.


#4

I’d like to store the strings only once. The idea is to have opaque, copy-able handles to be used in other data structures, like graphs, but still have access to the string once the result are computed and need to be printed out. The data sets are in the order of GB and one can have several hundred MB of labels so duplicating them isn’t a good idea.


#5

Here’s an implementation, that uses an arena. Depending on your needs you can put a &String or &str in the Symbol. The interesting bits:

pub struct Symbol<'a>(&'a String);

pub struct SymbolTable<'a> {
    arena: &'a Arena<String>,
    set: RefCell<HashSet<Symbol<'a>>>,
}

impl<'a> SymbolTable<'a> {
    fn add(&self, name: &str) -> Symbol {
        let mut set = self.set.borrow_mut();
        if let Some(&sym) = set.get(name) {
            return sym;
        }
        let sym = Symbol(self.arena.alloc(name.to_string()));
        set.insert(sym);
        sym
    }
}

#6

Thank you very much for the example. I’ll look into creating a custom area for the symbol table.


#7

BTW String here can be changed to Box<str> to save more space (making it arena.alloc(name.to_string().into_boxed_str())).