Захват указателя ошибок рекурсивного перемещения дерева

Question

Чтобы узнать Rust, я реализую дерево/словарь AVL. Чтобы вставить новый элемент, я спускаюсь в дерево, пока не найду узел, в который он может быть вставлен. К сожалению, он жалуется на несколько проблем с указателями заимствований, и у меня возникают проблемы с их расшифровкой.

Я подсчитал, где и какие ошибки происходят.

enum AVLTree<T, U> { 
    Tree(T, U, Box<AVLTree<T, U>>, Box<AVLTree<T, U>>), 
    Empty, 
} 

impl<T, U> AVLTree<T, U> 
    where T: PartialOrd + PartialEq + Copy, 
      U: Copy 
{ 
    fn insert_element(&mut self, key: T, val: U) { 
     let new_node = AVLTree::Tree(key, val, Box::new(AVLTree::Empty), Box::new(AVLTree::Empty)); 

     if let AVLTree::Empty = *self { 
      *self = new_node; 
      return; 
     } 

     let mut at = self; 
     loop { 
      match at { 
       &mut AVLTree::Tree(key2, _, ref mut left, ref mut right) => { 
        //      ^~~~~~~~~~~~ 
        // error: cannot borrow `at.2` as mutable more than once at a time 
        //         ^~~~~~~~~~~~~ 
        // error: cannot borrow `at.3` as mutable more than once at a time 
        if key < key2 { 
         if let AVLTree::Empty = **left { 
          *left = Box::new(new_node); 
          break; 
         } 
         at = &mut **left; 
         // error: cannot assign to `at` because it is borrowed 
        } else { 
         if let AVLTree::Empty = **right { 
          *right = Box::new(new_node); 
          break; 
         } 
         at = &mut **right; 
         // error: cannot assign to `at` because it is borrowed 
        } 
       } 
       &mut AVLTree::Empty => unreachable!(), 
      } 
     } 
     // Do something 
    } 
} 

Почему деконструкции at заимствует его? Почему компилятор жалуется на несколько изменчивых заимствований, когда этого никогда не должно произойти? Как этот код может быть написан вместо этого, чтобы избежать таких ошибок?

Answer 1

Это, по-видимому, слабость проверки кредита, и, возможно, это ошибка. Проблема в том, что вы заимствуете at в матче, а затем изменяете его. К сожалению, компилятор не видит, что at внутри цикла и вне цикла концептуально отличаются. Мы можем сделать их явно различны, однако:

enum AVLTree { 
    Tree(Box<AVLTree>), 
    Empty, 
} 

impl AVLTree { 
    fn insert_element(&mut self) { 
     let mut at = self; 
     loop { 
      let tmp_at = at; // Main change 
      match tmp_at { 
       &mut AVLTree::Tree(ref mut left) => { 
        at = &mut **left; 
       } 
       &mut AVLTree::Empty => unreachable!() 
      } 
     } 
    } 
} 

fn main() {} 

Здесь мы переносим изменяемый позаимствовать at к tmp_at, а затем перенести его на left, а затем перенести его обратно в at.

красивее вариант может использовать новые возможности:

fn insert_element(&mut self) { 
    let mut at = self; 
    loop { 
     match {at} { // Main change 
      &mut AVLTree::Tree(ref mut left) => { 
       at = &mut **left; 
      } 
      &mut AVLTree::Empty => unreachable!(), 
     } 
    } 
}