Тип параметра `T` может не сохраняться достаточно долго при записи двоичного дерева поиска

Question

Я пытаюсь написать двоичное дерево поиска в Rust, но я не понимаю, что происходит:

enum BST<'a, T: Ord> {
    Leaf,
    BinTree { value: T, left: &'a mut BST<'a, T>, right: &'a mut BST<'a, T> }
}

impl<'a, T: Ord> BST<'a, T> {
    fn new() -> BST<'a, T> {
        BST::Leaf
    }

    fn add(self, val: T) {
        match self {
            BST::Leaf => self = BST::BinTree {
                value: val,
                left: &mut BST::<'a, T>::new(),
                right: &mut BST::<'a, T>::new()
            },
            BST::BinTree{value: v, left: l, right: r} => if val < v {
                l.add(val);
            } else {
                r.add(val);
            }
        }
    }
}

fn main() {
}

Когда я пытаюсь скомпилировать это, я получаю следующие ошибки:

error[E0309]: the parameter type `T` may not live long enough
 --> heap.rs:3:25
  |
3 |     BinTree { value: T, left: &'a mut BST<'a, T>, right: &'a mut BST<'a, T> }
  |                         ^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = help: consider adding an explicit lifetime bound `T: 'a`...
note: ...so that the reference type `&'a mut BST<'a, T>` does not outlive the data it points at
 --> heap.rs:3:25
  |
3 |     BinTree { value: T, left: &'a mut BST<'a, T>, right: &'a mut BST<'a, T> }
  |                         ^^^^^^^^^^^^^^^^^^^^^^^^

Что ж, после долгих исследований и того, что предлагает компилятор, я придумал следующий код:

enum BST<'a, T: Ord + 'a> {
    Leaf,
    BinTree { 
        value: T,
        left: &'a mut BST<'a, T>,
        right: &'a mut BST<'a, T>
    }
}

impl<'a, T: Ord + 'a > BST<'a, T> {
    fn new() -> BST<'a, T> {
        BST::Leaf
    }

    fn add(&mut self, val: T) {
        match *self {
            BST::Leaf => *self = BST::BinTree {
                value: val,
                left: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>,
                right: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>
            },
            BST::BinTree{value: ref v, left: ref mut l, right: ref mut r} => if val < *v {
                l.add(val);
            } else {
                r.add(val);
            }
        }
    }
}

fn main() {
}

Но я все еще получаю ошибки:

error: borrowed value does not live long enough
  --> heap.rs:19:16
   |
19 |                left: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>,
   |                           ^^^^^^^^^^^^^^^^^^^ does not live long enough
20 |                right: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>
21 |            },
   |            - temporary value only lives until here
   |
note: borrowed value must be valid for the lifetime 'a as defined on the body at 15:27...
  --> heap.rs:15:28
   |
15 |    fn add(&mut self, val: T) {
   |  ____________________________^
16 | |      match *self {
17 | |          BST::Leaf => *self = BST::BinTree {
18 | |              value: val,
...  |
27 | |      }
28 | |  }
   | |__^

error: borrowed value does not live long enough
  --> heap.rs:20:17
   |
20 |                right: &mut BST::<'a, T>::new() as &'a mut BST<'a, T>
   |                            ^^^^^^^^^^^^^^^^^^^ does not live long enough
21 |            },
   |            - temporary value only lives until here
   |
note: borrowed value must be valid for the lifetime 'a as defined on the body at 15:27...
  --> heap.rs:15:28
   |
15 |    fn add(&mut self, val: T) {
   |  ____________________________^
16 | |      match *self {
17 | |          BST::Leaf => *self = BST::BinTree {
18 | |              value: val,
...  |
27 | |      }
28 | |  }
   | |__^

error: aborting due to 2 previous errors

Я знаю, что это можно исправить с помощью Boxes вместо ссылок, но я хочу сделать это для упражнений.

Answer 1

Как говорится в сообщении об ошибке, эту конкретную ошибку можно исправить, добавив предел жизни T: 'a, Но тогда вы получите много других ошибок, потому что то, что вы пытаетесь сделать, не обосновано: вы пытаетесь хранить ссылки на объекты, у которых нет владельца в другом месте.

Когда вы делаете что-то вроде хранения &mut BST::<'a, T>::new() в вашем узле, BST::<'a, T>::new() возвращает временное значение, которое вскоре будет уничтожено, поэтому вы не можете сохранить ссылку на него и ожидать, что оно будет жить.

Вместо ссылок вам нужен ваш узел, чтобы владеть его дочерними элементами. Вы можете сделать это, изменив дочерний тип на left: Box<BST<T>> и используя Box::new когда вы создаете новый дочерний узел. Как только вы это сделаете, вы можете избавиться от всех 'a везде и не получит ошибок, связанных с жизнью.

Другая проблема заключается в том, что ваш add потребляет self параметр, так что он не сможет больше использоваться вызывающей стороной. Вы должны сделать это взять &mut self вместо этого, чтобы он мог изменить дерево, принадлежащее вызывающей стороне.