Is there a way to make this work? Borrowing from self mutably if not already optionally borrowing from self

I'm trying to do the following but I get a borrowck error at:

            (
                SnailfishNumberComponent::Pair(left_idx),
                SnailfishNumberComponent::Literal(lit_right),
            ) if lit_right >= 10 => {
                if let Some(splittable_literal) = self.next_splittable_literal(left_idx) {
                    Some(splittable_literal)
                } else {
                    Some(&mut self.components[idx].right)
                }
            }

Here is the whole function/method:

    fn next_splittable_literal(&mut self, idx: usize) -> Option<&mut SnailfishNumberComponent> {
        #[allow(clippy::manual_map)]
        match (self.components[idx].left, self.components[idx].right) {
            (
                SnailfishNumberComponent::Literal(lit_left), //
                _,
            ) if lit_left >= 10 => Some(&mut self.components[idx].left),
            (
                SnailfishNumberComponent::Literal(_),
                SnailfishNumberComponent::Literal(lit_right),
            ) if lit_right >= 10 => Some(&mut self.components[idx].right),
            (
                SnailfishNumberComponent::Literal(_), //
                SnailfishNumberComponent::Literal(_),
            ) => None,
            (
                SnailfishNumberComponent::Literal(_), //
                SnailfishNumberComponent::Pair(right_idx),
            ) => self.next_splittable_literal(right_idx),
            (
                SnailfishNumberComponent::Pair(left_idx),
                SnailfishNumberComponent::Literal(lit_right),
            ) if lit_right >= 10 => {
                if let Some(splittable_literal) = self.next_splittable_literal(left_idx) {
                    Some(splittable_literal)
                } else {
                    Some(&mut self.components[idx].right)
                }
            }
            (SnailfishNumberComponent::Pair(left_idx), SnailfishNumberComponent::Literal(_)) => {
                if let Some(splittable_literal) = self.next_splittable_literal(left_idx) {
                    Some(splittable_literal)
                } else {
                    None
                }
            }
            (
                SnailfishNumberComponent::Pair(left_idx),
                SnailfishNumberComponent::Pair(right_idx),
            ) => todo!(),
            (SnailfishNumberComponent::Invalid, _) | (_, SnailfishNumberComponent::Invalid) => {
                unreachable!("Invalid SnailfishNumberComponents should never happen here")
            }
        }
    }

Is there a reasonable work-around to this?

I'm trying to get a mutable reference into the components member of the self structure iff a literal is found that satisfies the rule of being >= 10.

Is there another way I could approach this that the borrowck would be happy with?

Here's a playground which hopefully matches the use case, if anyone wants to play with it.

Assuming it does match the use case, this is an instance of NLL Problem Case #3 that works with Polonius.

I ended up abandoning trying to return mutable references to the components and instead re turning an index to the pair and an enum indicating whether the left or right component was the one that matched. Here is the Playground link: Rust Playground

EDIT: Here is the code for anyone interested::

use std::{error::Error, iter::Sum, ops::Add, str::FromStr};

#[cfg(test)]
mod tests;

pub fn determine_sum_of_snailfish_numbers(numbers: Vec<SnailfishNumber>) -> SnailfishNumber {
    numbers.into_iter().sum()
}

#[derive(Default)]
pub struct SnailfishNumber {
    components: Vec<SnailfishNumberPair>,
}

impl SnailfishNumber {
    fn len(&self) -> usize {
        self.components.len()
    }

    fn reduce(mut self) -> Self {
        loop {
            if self.explode() {
                continue;
            }
            if self.split() {
                continue;
            }
            break;
        }
        self
    }

    pub fn magnitude(&self) -> u64 {
        self.pair_magnitude(0)
    }

    fn pair_magnitude(&self, component_idx: usize) -> u64 {
        3 * self.component_magnitude(&self.components[component_idx].left)
            + 2 * self.component_magnitude(&self.components[component_idx].right)
    }

    fn component_magnitude(&self, component: &SnailfishNumberComponent) -> u64 {
        use SnailfishNumberComponent::*;
        match component {
            Literal(value) => *value as u64,
            Pair(idx) => self.pair_magnitude(*idx),
            Invalid => unreachable!("Invalid Pair - components are not permitted to be invalid when computing the magnitude"),
        }
    }

    fn explode(&mut self) -> bool {
        if let Some(explodable_pair_idx) = self.next_explodeable_pair(0) {
            self.explode_pair(explodable_pair_idx);
            true
        } else {
            false
        }
    }

    fn next_explodeable_pair(&self, idx: usize) -> Option<usize> {
        #[allow(clippy::manual_map)]
        if self.components[idx].level == 4 {
            Some(idx)
        } else if let Some(idx) =
            self.check_pair_component_for_explodability(&self.components[idx].left)
        {
            Some(idx)
        } else if let Some(idx) =
            self.check_pair_component_for_explodability(&self.components[idx].right)
        {
            Some(idx)
        } else {
            None
        }
    }

    fn check_pair_component_for_explodability(
        &self,
        component: &SnailfishNumberComponent,
    ) -> Option<usize> {
        if let SnailfishNumberComponent::Pair(idx) = component {
            if let Some(idx) = self.next_explodeable_pair(*idx) {
                return Some(idx);
            }
        }
        None
    }

    fn explode_pair(&mut self, current_idx: usize) {
        match (self.components[current_idx].left, self.components[current_idx].right) {
            (SnailfishNumberComponent::Literal(current_left_value), SnailfishNumberComponent::Literal(current_right_value)) => {
                if let Some(nearest_left) = find_nearest_left_literal(&mut self.components, current_idx) {
                    *nearest_left += current_left_value;
                }
                if let Some(nearest_right) = find_nearest_right_literal(&mut self.components, current_idx) {
                    *nearest_right += current_right_value;
                }
                replace_current_pair_in_parent_with_literal_zero(&mut self.components, current_idx);
            },
            _ => unreachable!("Level 4 pair with non-literal components is not permitted in a valid Snailfish Number and should never occur"),
        }
    }

    fn split(&mut self) -> bool {
        match self.next_splittable_literal(0) {
            Some((idx, left_or_right)) => {
                self.split_literal(idx, left_or_right);
                true
            }
            None => false,
        }
    }

    fn next_splittable_literal(&mut self, idx: usize) -> Option<(usize, LeftOrRight)> {
        #[allow(clippy::manual_map)]
        match (self.components[idx].left, self.components[idx].right) {
            (
                SnailfishNumberComponent::Literal(lit_left), //
                _,
            ) if lit_left >= 10 => Some((idx, LeftOrRight::Left)),
            (
                SnailfishNumberComponent::Literal(_),
                SnailfishNumberComponent::Literal(lit_right),
            ) if lit_right >= 10 => Some((idx, LeftOrRight::Right)),
            (
                SnailfishNumberComponent::Literal(_), //
                SnailfishNumberComponent::Literal(_),
            ) => None,
            (
                SnailfishNumberComponent::Literal(_), //
                SnailfishNumberComponent::Pair(right_idx),
            ) => self.next_splittable_literal(right_idx),
            (
                SnailfishNumberComponent::Pair(left_idx),
                SnailfishNumberComponent::Literal(lit_right),
            ) => {
                if let Some(found_splittable) = self.next_splittable_literal(left_idx) {
                    Some(found_splittable)
                } else if lit_right >= 10 {
                    Some((idx, LeftOrRight::Right))
                } else {
                    None
                }
            }
            (
                SnailfishNumberComponent::Pair(left_idx),
                SnailfishNumberComponent::Pair(right_idx),
            ) => {
                if let Some(found_splittable) = self.next_splittable_literal(left_idx) {
                    Some(found_splittable)
                } else {
                    self.next_splittable_literal(right_idx)
                }
            }
            (SnailfishNumberComponent::Invalid, _) | (_, SnailfishNumberComponent::Invalid) => {
                unreachable!("Invalid SnailfishNumberComponents should never happen here")
            }
        }
    }

    fn split_literal(&mut self, idx: usize, left_or_right: LeftOrRight) {
        match left_or_right {
            LeftOrRight::Left => {
                if let SnailfishNumberComponent::Literal(lit) = self.components[idx].left {
                    let parent = self.components[idx].parent;
                    let level = self.components[idx].level + 1;
                    let new_idx = self.components.len();
                    self.components[idx].left = SnailfishNumberComponent::Pair(new_idx);
                    self.components.push(SnailfishNumberPair {
                        parent,
                        idx: new_idx,
                        level,
                        left: SnailfishNumberComponent::Literal(lit / 2),
                        right: SnailfishNumberComponent::Literal(lit / 2 + lit % 2),
                    })
                } else {
                    unreachable!("the left component will always be a literal")
                }
            }
            LeftOrRight::Right => {
                if let SnailfishNumberComponent::Literal(lit) = self.components[idx].right {
                    let parent = self.components[idx].parent;
                    let level = self.components[idx].level + 1;
                    let new_idx = self.components.len();
                    self.components[idx].right = SnailfishNumberComponent::Pair(new_idx);
                    self.components.push(SnailfishNumberPair {
                        parent,
                        idx: new_idx,
                        level,
                        left: SnailfishNumberComponent::Literal(lit / 2),
                        right: SnailfishNumberComponent::Literal(lit / 2 + lit % 2),
                    })
                } else {
                    unreachable!("the right component will always be a literal")
                }
            }
        }
    }

    fn push_pair(&mut self, pair: SnailfishNumberPair) -> usize {
        self.components.push(pair);
        self.components.len() - 1
    }

    fn push_children_left(&mut self, components: Vec<SnailfishNumberPair>, root_idx: usize) {
        let offset = self.components.len();
        self.components.reserve(components.len());
        self.components[root_idx].left = SnailfishNumberComponent::Pair(offset);
        self.append_children(components, root_idx, offset);
    }

    fn push_children_right(&mut self, components: Vec<SnailfishNumberPair>, root_idx: usize) {
        let offset = self.components.len();
        self.components.reserve(components.len());
        self.components[root_idx].right = SnailfishNumberComponent::Pair(offset);
        self.append_children(components, root_idx, offset);
    }

    fn append_children(
        &mut self,
        components: Vec<SnailfishNumberPair>,
        root_idx: usize,
        offset: usize,
    ) {
        let mut skipped = 0;
        for mut component in components {
            if component.parent.is_none() && component.level == u8::MAX {
                skipped += 1;
                continue;
            }
            component.level += 1;
            if let Some(ref mut parent_idx) = component.parent {
                *parent_idx += offset - skipped;
            } else {
                component.parent = Some(root_idx)
            }
            component.idx += offset - skipped;
            if let SnailfishNumberComponent::Pair(ref mut idx) = component.left {
                *idx += offset - skipped;
            }
            if let SnailfishNumberComponent::Pair(ref mut idx) = component.right {
                *idx += offset - skipped;
            }
            self.components.push(component);
        }
    }
}

fn find_nearest_left_literal(
    components: &mut [SnailfishNumberPair],
    current_idx: usize,
) -> Option<&mut u8> {
    let mut current_idx = components[current_idx]
        .parent
        .expect("a parent is mandatory here");
    let mut searching_up = true;
    loop {
        match searching_up {
            true => match components[current_idx].left {
                SnailfishNumberComponent::Literal(ref mut lit) => return Some(lit),
                SnailfishNumberComponent::Pair(pair_idx) if pair_idx == current_idx => {
                    if let Some(parent_idx) = components[current_idx].parent {
                        current_idx = parent_idx;
                        continue;
                    } else {
                        return None;
                    }
                }
                SnailfishNumberComponent::Pair(pair_idx) => {
                    current_idx = pair_idx;
                    searching_up = false;
                    continue;
                }
                SnailfishNumberComponent::Invalid => {
                    unreachable!("Invalid SnailfishNumberComponent should never occur here")
                }
            },
            false => match components[current_idx].right {
                SnailfishNumberComponent::Literal(ref mut lit) => return Some(lit),
                SnailfishNumberComponent::Pair(pair_idx) => {
                    current_idx = pair_idx;
                    continue;
                }
                SnailfishNumberComponent::Invalid => {
                    unreachable!("Invalid SnailfishNumberComponent should never occur here")
                }
            },
        }
    }
}

fn find_nearest_right_literal(
    components: &mut [SnailfishNumberPair],
    current_idx: usize,
) -> Option<&mut u8> {
    let mut current_idx = components[current_idx]
        .parent
        .expect("a parent is mandatory here");
    let mut searching_up = true;
    loop {
        match searching_up {
            true => match components[current_idx].right {
                SnailfishNumberComponent::Literal(ref mut lit) => return Some(lit),
                SnailfishNumberComponent::Pair(pair_idx) if pair_idx == current_idx => {
                    if let Some(parent_idx) = components[current_idx].parent {
                        current_idx = parent_idx;
                        continue;
                    } else {
                        return None;
                    }
                }
                SnailfishNumberComponent::Pair(pair_idx) => {
                    current_idx = pair_idx;
                    searching_up = false;
                    continue;
                }
                SnailfishNumberComponent::Invalid => {
                    unreachable!("Invalid SnailfishNumberComponent should never occur here")
                }
            },
            false => match components[current_idx].left {
                SnailfishNumberComponent::Literal(ref mut lit) => return Some(lit),
                SnailfishNumberComponent::Pair(pair_idx) => {
                    current_idx = pair_idx;
                    continue;
                }
                SnailfishNumberComponent::Invalid => {
                    unreachable!("Invalid SnailfishNumberComponent should never occur here")
                }
            },
        }
    }
}

fn replace_current_pair_in_parent_with_literal_zero(
    // parent: &mut SnailfishNumberPair,
    // current: &mut SnailfishNumberPair,
    components: &mut [SnailfishNumberPair],
    current_idx: usize,
) {
    use SnailfishNumberComponent::*;
    let (_before_parent, parent, _after_parent, current, _rest) =
        split_components_into_before_parent_parent_after_parent_current_and_rest(
            components,
            current_idx,
        );
    loop {
        if let Pair(parent_left_idx) = parent.left {
            if parent_left_idx == current_idx {
                parent.left = Literal(0);
                // mark current as "dead"
                current.parent = None;
                current.level = u8::MAX;
            }
            break;
        }
        if let Pair(parent_right_idx) = parent.right {
            if parent_right_idx == current_idx {
                parent.right = Literal(0);
                // mark current as "dead"
                current.parent = None;
                current.level = u8::MAX;
            }
            break;
        }
        unreachable!(
            "Either left or right of parent must point to child which claims it as its parent"
        )
    }
}

fn split_components_into_before_parent_parent_after_parent_current_and_rest(
    components: &mut [SnailfishNumberPair],
    current_idx: usize,
) -> (
    &mut [SnailfishNumberPair],
    &mut SnailfishNumberPair,
    &mut [SnailfishNumberPair],
    &mut SnailfishNumberPair,
    &mut [SnailfishNumberPair],
) {
    let (parents, rest) = components.split_at_mut(current_idx);
    let (current, rest) = rest.split_at_mut(1);
    let current = &mut current[0];
    let (before_parent, parents) = parents.split_at_mut(current.parent.expect(
        "explodeable pair without parent encountered which is forbidden - should never happen",
    ));
    let (parent, after_parent) = parents.split_at_mut(1);
    let parent = &mut parent[0];
    (before_parent, parent, after_parent, current, rest)
}

impl Add<SnailfishNumber> for SnailfishNumber {
    type Output = SnailfishNumber;

    fn add(self, rhs: SnailfishNumber) -> Self::Output {
        let mut sum = Self::default();
        let root_idx = sum.push_pair(sum.len().into());
        sum.push_children_left(self.components, root_idx);
        sum.push_children_right(rhs.components, root_idx);
        sum.reduce()
    }
}

impl Sum for SnailfishNumber {
    fn sum<I: Iterator<Item = Self>>(mut iter: I) -> Self {
        let mut sum = iter.next().unwrap_or_default();
        for num in iter {
            sum = sum + num;
        }
        sum
    }
}

impl FromStr for SnailfishNumber {
    type Err = Box<dyn Error>;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        todo!()
    }
}

pub struct SnailfishNumberPair {
    parent: Option<usize>,
    idx: usize,
    level: u8,
    left: SnailfishNumberComponent,
    right: SnailfishNumberComponent,
}

impl From<usize> for SnailfishNumberPair {
    fn from(idx: usize) -> Self {
        Self {
            parent: None,
            idx,
            level: 0,
            left: Default::default(),
            right: Default::default(),
        }
    }
}

#[derive(Copy, Clone)]
pub enum SnailfishNumberComponent {
    Invalid,
    Literal(u8),
    Pair(usize),
}

impl Default for SnailfishNumberComponent {
    fn default() -> Self {
        SnailfishNumberComponent::Invalid
    }
}

impl SnailfishNumberComponent {
    fn is_literal(&self) -> bool {
        match self {
            SnailfishNumberComponent::Invalid => false,
            SnailfishNumberComponent::Literal(_) => true,
            SnailfishNumberComponent::Pair(_) => false,
        }
    }

    fn is_pair(&self) -> bool {
        match self {
            SnailfishNumberComponent::Invalid => false,
            SnailfishNumberComponent::Literal(_) => false,
            SnailfishNumberComponent::Pair(_) => true,
        }
    }
}

enum LeftOrRight {
    Left,
    Right,
}

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.