Lifetimes of struct fields used as KV pair

help
1

I'm learning Rust and trying to figure out how to solve this problem. I'm trying to store a struct that has some data including a key, inside of a trie container. For the sake of learning lifetimes, I'm trying to figure out how I can have the trie own the key while the struct keeps a reference to it.

It makes sense to me that the trie should own the key, since when a struct is removed, the trie will also remove the key, so the key outlives the struct. I'm just not sure how I can express this yet. I haven't really been able to find examples of doing this (potentially stupid) thing yet.

The reason why I'd like to keep a reference to the key within the struct is so its identifier can be used in the string representation. I also played around with the alternative (where trie uses reference to key), but this didn't make as much sense in terms of lifetimes to me.

The trie crate I'm stubbing is radix_trie

/*****************************************************/

// stub
struct Trie<K, V> {
    k: Option<K>, // to suppress unused type parameter
    v: Option<V>, // to suppress unused type parameter
}

// stub
#[allow(unused_variables)]
impl<K, V> Trie<K, V> {
    fn new() -> Trie<K, V> {
        Trie {
            k: None,
            v: None,
        }
    }
    
    fn get(&self, k: &K) -> Option<&V> {
        None
    }
    
    fn insert(&mut self, k: K, v: V) {
    }
}

/*****************************************************/

struct Struct<'a> {
    key: &'a String,
}

struct Manager<'a> {
    trie: Trie<String, Struct<'a>>,
}

impl<'a> Manager<'a> {
    fn new() -> Manager<'a> {
        Manager {
            trie: Trie::new(),
        }
    }

    fn get(&self, k: &str) -> Option<&Struct> {
        let k = k.to_owned(); // TODO: translate key
        self.trie.get(&k)
    }
    
    fn put(&mut self, k: &str, mut c: Struct<'a>) {
        let k = k.to_owned(); // TODO: translate key
        c.key = &k;
        self.trie.insert(k, c);
    }
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0597]: `k` does not live long enough
  --> src/lib.rs:51:17
   |
37 | impl<'a> Manager<'a> {
   |      -- lifetime `'a` defined here
...
51 |         c.key = &k;
   |         --------^^
   |         |       |
   |         |       borrowed value does not live long enough
   |         assignment requires that `k` is borrowed for `'a`
52 |         self.trie.insert(k, c);
53 |     }
   |     - `k` dropped here while still borrowed

error[E0505]: cannot move out of `k` because it is borrowed
  --> src/lib.rs:52:26
   |
37 | impl<'a> Manager<'a> {
   |      -- lifetime `'a` defined here
...
51 |         c.key = &k;
   |         ----------
   |         |       |
   |         |       borrow of `k` occurs here
   |         assignment requires that `k` is borrowed for `'a`
52 |         self.trie.insert(k, c);
   |                          ^ move out of `k` occurs here

error: aborting due to 2 previous errors

Some errors have detailed explanations: E0505, E0597.
For more information about an error, try `rustc --explain E0505`.
error: could not compile `playground`

To learn more, run the command again with --verbose.
2

You would need to store a reference to the String that is stored in the Trie, not to a local variable on the stack which is soon to vanish.

Self referential data structures are very hard to construct, and my only advise is not to do so. Or ask someone else, which is what you did...

3

So the recommendation is to copy/clone the key?

Just for the fun of it though, how would a self-referential data structure typically be done, like with a weak reference or something? I.e., it makes sense to me this should work seeing as the trie key reference only needs to live as long as the data it stores, which gets dumped when it's removed from the trie.

4

An Rc or Arc would work and no reason to make it a weak reference, unless your Trie type is broken, surely it doesn't keep the key when it deletes the value?

I'm not sure about the Trie you're working with, but normally I wouldn't expect one to keep the key at all. I thought the whole point of a Trie was to split the key up into a common prefix and unique suffix.

5

Sorry, I misspoke, yes, the trie would release the reference.

It's largely for debugging purposes so that I can access the key of the struct from within its scope, e.g., "key=value". I'm doing this for a hierarchal database (like windows registry), so the struct would wrap some value. When I've implemented something like this before in Java, the trie returns a set of values which contain the same prefix in their key, and I'd like to group the key with the data as an identifier.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.