1

I am trying to write a trie structure, which takes in a stream of characters and adds them onto the trie if it doesn't exist yet. When it adds a character, it returns to the top to start again.

#[derive(Debug)]
pub struct Trie {
    char: u8,
    children: [Option<Box<Self>>; 2],
}

impl Trie {
    pub fn new(char: u8) -> Trie {
        return Trie {
            char,
            children: [None, None],
        };
    }

    pub fn push(&mut self, lz_pair: Trie) {
        let idx = lz_pair.char as usize;
        self.children[idx] = Some(Box::new(lz_pair));
    }

    pub fn get_child(&mut self, char: u8) -> Option<&mut Trie> {
        let child = self.children[char as usize].as_mut();
        if let Some(c) = child {
            Some(c.as_mut())
        } else {
            None
        }
    }
}

fn main() {
    let data = b"abbabababbbbbabaaaabababaa";

    let mut root = Trie::new(0);
    let mut cur = &mut root;

    for c in data {
        cur = match cur.get_child(*c) {
            Some(child) => child,
            None => {
                cur.push(Trie::new(*c - 97));
                &mut root
            }
        };
    }
}

Playground

The actual code is a bit more complicated, but I distilled it down to just show this error.

The borrow checker complains:

error[E0499]: cannot borrow `*cur` as mutable more than once at a time
  --> src/main.rs:40:17
   |
37 |         cur = match cur.get_child(*c) {
   |                     --- first mutable borrow occurs here
...
40 |                 cur.push(Trie::new(*c - 97));
   |                 ^^^
   |                 |
   |                 second mutable borrow occurs here
   |                 first borrow used here, in later iteration of loop

I have read through all the questions here on the borrow checker errors when unwrapping Options (i.e. This question and all the duplicates), so I sort of understand why it happens, however I don't know how I can restructure this code to solve this particular case.

Non-lexical lifetimes don't seem to solve this problem as I am compiling using the 2018 version of Rust.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
8176135
  • 3,755
  • 3
  • 19
  • 42
  • Instead of borrowing you can use `Rc` to have multiple owners. And if you really need mutability you can use `RefCell` and the internal mutability pattern. – Svetlin Zarev Apr 01 '19 at 11:40
  • This actually *will* be fixed by NLL, just not the NLL that's available in the current version of Rust. In the meantime, you will want to workaround this with some inefficiency by returning a boolean instead of an (optional) reference. – Shepmaster Apr 01 '19 at 13:08

0 Answers0