How too loop over a function that requires a mutable refrence?

Question

I am quite new to rust and I have a problem with the borrow checker.

I have a function like this:

impl<'a> DFA<'a> {
    fn solve_next(&mut self, c: Option<char>) -> Option<TokenType> {
        let node = self.state.unwrap_or_else(|| &self.start_node);
        let checks: Vec<char> = node.connections.iter().map(|x| x.1).collect();
        let mut position = None;
        if let Some(c) = c {
            position = checks.iter().position(|x| *x == c);
        }
        if let Some(i) = position {
            let node = &node.connections[i].0;
            self.state = Some(node);
            None
        } else {
            if node.is_end {
                return Some(TokenType::Keyword);
            }
            panic!("Invalid charter for current set");
        }
    }
}

This function either returns a TokenType (which is a enum) when the loop is complete or None when it is not. its is on this struct:

struct DFA<'a> {
    state: Option<&'a Node>,
    start_node: Node,
}

Node is:

struct Node {
    connections: Vec<(Node, char)>,
    is_end: bool,
    token_type: TokenType,
}

with the method

fn insert(&mut self, _match: char, end: bool) -> &mut Node {

which creates and return a new node and adds this node into its own connections.

So when I wanted to loop over the solve next function I tried:

impl<'a> Lexer<'a> {
    fn next_char(&self) -> Option<char> {
        let mut r: Option<char> = None;
        for c in &self.chars {
            match c {
                ' ' | '\n' | '\r' => {
                    continue;
                }
                _ => {
                    r = Some(c.clone());
                    break;
                }
            }
        }
        return r;
    }
    fn next_token(&'a mut self) {
        let somechar = 'c';
        let mut x = self.dfa.solve_next(self.next_char());
        while let None = x {
            x = self.dfa.solve_next(self.next_char());
        }
    }
}

which is a method of

struct Lexer<'a> {
    //the output of the lexer
    pub tokens: Vec<Token>,

    chars: Vec<char>,

    dfa: DFA<'a>,
}

the compile error's with

error[E0499]: cannot borrow `self.dfa` as mutable more than once at a time
   --> src/main.rs:177:17
    |
146 | impl<'a> Lexer<'a> {
    |      -- lifetime `'a` defined here
...
175 |         let mut x = self.dfa.solve_next(self.next_char());
    |                     -------------------------------------
    |                     |
    |                     first mutable borrow occurs here
    |                     argument requires that `self.dfa` is borrowed for `'a`
176 |         while let None = x {
177 |             x = self.dfa.solve_next(self.next_char());
    |                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ second mutable borrow occurs here

error[E0502]: cannot borrow `*self` as immutable because it is also borrowed as mutable
   --> src/main.rs:177:37
    |
146 | impl<'a> Lexer<'a> {
    |      -- lifetime `'a` defined here
...
175 |         let mut x = self.dfa.solve_next(self.next_char());
    |                     -------------------------------------
    |                     |
    |                     mutable borrow occurs here
    |                     argument requires that `self.dfa` is borrowed for `'a`
176 |         while let None = x {
177 |             x = self.dfa.solve_next(self.next_char());
    |                                     ^^^^^^^^^^^^^^^^ immutable borrow occurs here

So is their any way I can use solve_next in this loop? as I would not know how to make a function that can be used like this without having it take a mutable refrence.

Answer 1

The actual error you get with your code is the following (playground):

error: lifetime may not live long enough
  --> src/lib.rs:27:49
   |
25 | impl<'a> DFA<'a> {
   |      -- lifetime `'a` defined here
26 |     fn solve_next(&mut self, c: Option<char>) -> Option<TokenType> {
   |                   - let's call the lifetime of this reference `'1`
27 |         let node = self.state.unwrap_or_else(|| &self.start_node);
   |                                                 ^^^^^^^^^^^^^^^^ associated function was supposed to return data with lifetime `'a` but it is returning data with lifetime `'1`

This is actually complaining about the reference to self.start_node not living long enough, that is for at least 'a.

The reason for that is that your local variable node, that is of type &'x Node, being the lifetime 'x the shorter of that of self.state.unwrap() and &self.start_node. The first one is 'a and the second one is the unnamed lifetime of &self (from now on 's).

But by the rules of Rust lifetimes, 'a outlives DFA<'a> and Self outlives 's, and Self is equal to DFA<'a>, then we conclude that 'a outlives 's. So the lifetime of the local node is actually 's.

Now, the other key line is this one:

self.state = Some(node);

being self.state of type Option<&'a Node>, that requires that the lifetime of node, that is 's, outlives 'a. But that cannot be, we already determined that it is the other way around: 'a outlives 's. Thus a compiler error.

In a nutshell, you are trying to write a self-referential struct, storing in one field a reference to the other field. And that is well known to be impossible.

In the original version of your question, you tried to solve it adding an extra lifetime to the solve_next() function:

fn solve_next(&'a mut self, c: Option<char>) -> Option<TokenType>

Doing that you force the 's from my explanation above to be exactly equal to 'a, so the body of this function is actually correct. Unfortunately if you try to call it normally with:

    fn next_token(&mut self) {
        let mut x = self.dfa.solve_next(self.next_char());
    }

It fails with:

error: lifetime may not live long enough
  --> src/lib.rs:63:21
   |
46 | impl<'a> Lexer<'a> {
   |      -- lifetime `'a` defined here
...
62 |     fn next_token(&mut self) {
   |                   - let's call the lifetime of this reference `'1`
63 |         let mut x = self.dfa.solve_next(self.next_char());
   |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ argument requires that `'1` must outlive `'a`

Exactly for the same reason as above: the anonymous lifetime of self must outlive 'a but the compiler deduces it the other way around.

Naturally you can fix it the same way:

fn next_token(&'a mut self) {

And that will compile... as long as you do not try to call solve_next() twice.

I'm not sure why calling solve_next() once it compiles, but calling it twice fails with. But it does not actually matter because even if this function worked, with this extra &'a mut self you'd still have the same problem calling this function from the external code.

What about the solution? Well, I think you need to refactor the code so that you never try to add a reference start_node in the same struct.

For example, you can store the start_node outside this struct:

struct DFA<'a> {
    state: Option<&'a Node>,
    start_node: &'a Node,
}

This, and remove all the lifetime annotations from &'a self and it will just compile (playground).