How to return the current node in a recursive iteration, if there is a condition?

So, first, a clarification: this question is in essence very similar to Append an element to a recursive list iteratively and Convert tail-recursive form to iterative form?, however, there is a crucial difference, and it's the one that causes the problem - the conditional return of the current node.

This is a relatively barebones version of a list iterator:

struct Node {
    node_data: Option<Box<Node>>,
}

impl Node {
    fn find_iterative(&mut self) -> &mut Node {
        let mut current = self;

        loop {
            match current.node_data {
                Some(ref mut child) => {
                    if Self::some_condition() {
                        return current;
                    } else {
                        current = child;
                    }
                }
                _ => {
                    panic!("");
                }
            }
        }
    }

    fn some_condition() -> bool {
        true
    }
}

(playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=37ed9921a51a6ed508ed058eff312d07)

Now, I get an error on the return current;. I've tried the conventional workarounds:

  • using a temporary value for current;
  • wrapping current in curly braces (in the match expression).

none of those worked. The culprit is the conditional block (intended as a whole, not just the if expression), which I can't remove, because it's crucial.

The only two ways of making it work are:

  • converting the logic to recursive;
  • using the polonius Rust flag.

Is there some workaround/solution I can use, instead of the two above?

The problem is that current.node_data is holding exclusive access to current for the entire match body. If you refactor that to hold a boolean test result instead of a mutable reference, it’ll fix the problem:

            if current.node_data.is_some() {
                if Self::some_condition() {
                    return current;
                } else {
                    current = current.node_data.as_mut().unwrap();
                }
            } else {
                panic!("");
            }

(Playground)

Transforming the if into a match guard also seems to make the borrow checker happy:

            match current.node_data {
                Some(_) if Self::some_condition() => {
                    return current;
                }
                Some(ref mut child) => {
                    current = child;
                }
                None => {
                    panic!("");
                }
            }

This only works if Self::some_condition() is not an expression that uses child mutably -- you can, perhaps surprisingly, bind child in the pattern by shared reference.

3 Likes

@trentj's observation is actually correct - my example was oversimplified.

The suggested strategy is still a clean, working, solution; this is the working, complete, version of the logic:

struct Node<T: PartialOrd + Copy> {
    node_data: Option<(T, Box<Node<T>>)>,
}

impl<T: PartialOrd + Copy> Node<T> {
    fn iterative_ordered_push(&mut self, value: T) {
        let mut current = self;

        loop {
            match current.node_data {
                Some((ref current_value, _)) if *current_value > value => {
                    break;
                }
                Some((_, ref mut child)) => {
                    current = child;
                }
                _ => {
                    break;
                }
            }
        }

        current.push_front(value);
    }

    fn push_front(&mut self, _value: T) {
        // Push to front of the self node
    }
}

Thanks!

1 Like