Проблемы с временами жизни на функции рекурсивных признаков

Question

Мне сложно преобразовать свой автономный merge_sort функция в признаке для Vec<T>. Кажется, я сталкиваюсь с жизненными ошибками с тем, как работает алгоритм сортировки слияния.

Я попытался указать время жизни в объявлениях функций и признаков, но это все равно дает мне аналогичную ошибку.

Мои исследования по жизни включает в себя ...

• Эффективная Rust
• Книга Rust
• Несколько видео YouTube на жизни
• Большинство вопросов на переполнение стека относительно жизни

Вот код

trait MergeSortable<T> { 
    fn merge_sort(&mut self); 
    fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T>; 
} 

impl<T: Ord + Clone + PartialEq> MergeSortable<T> for Vec<T> { 
    fn merge_sort(&mut self) { 
     if self.len() <= 1 { 
      return; 
     } 
     let mid = self.len()/2; 
     let mut left = self[..mid].to_vec(); 
     left.merge_sort(); 
     let mut right = self[mid..].to_vec(); 
     right.merge_sort(); 
     self = self._merge(&mut left, &mut right); 
    } 

    fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> { 
     if left.len() == 0 { 
      return right; 
     } 
     if right.len() == 0 { 
      return left; 
     } 
     if left[0] < right[0] { 
      let mut v: Vec<T> = Vec::new(); 
      v.push(left[0].clone()); 
      v.extend_from_slice(&self._merge(&mut left[1..].to_vec().clone(), &mut right.clone())[..]); 
      return &mut v; 
     } 
     let mut v: Vec<T> = Vec::new(); 
     v.push(right[0].clone()); 
     v.extend_from_slice(&self._merge(&mut left.clone(), &mut right[1..].to_vec().clone())[..]); 
     return &mut v; 
    } 
} 

(Playground)

И ошибки:

error: lifetime of reference outlives lifetime of borrowed content... [E0312] 
    --> <anon>:27:20 
    |> 
27 |>    return left; 
    |>     ^^^^ 
note: ...the reference is valid for the anonymous lifetime #1 defined on the block at 22:75... 
    --> <anon>:22:76 
    |> 
22 |>  fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> { 
    |>                   ^
note: ...but the borrowed content is only valid for the anonymous lifetime #2 defined on the block at 22:75 
    --> <anon>:22:76 
    |> 
22 |>  fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> { 
    |>                   ^

error: lifetime of reference outlives lifetime of borrowed content... [E0312] 
    --> <anon>:24:20 
    |> 
24 |>    return right; 
    |>     ^^^^^ 
note: ...the reference is valid for the anonymous lifetime #1 defined on the block at 22:75... 
    --> <anon>:22:76 
    |> 
22 |>  fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> { 
    |>                   ^
note: ...but the borrowed content is only valid for the anonymous lifetime #3 defined on the block at 22:75 
    --> <anon>:22:76 
    |> 
22 |>  fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> { 
    |>                   ^
help: consider using an explicit lifetime parameter as shown: fn _merge<'a, 'b>(&'a self, left: &'a mut Vec<T>, right: &'b mut Vec<T>) 
-> &mut Vec<T> 
    --> <anon>:22:5 
    |> 
22 |>  fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> { 
    |> ^

Answer 1

_merge не нуждается в его аргументе self. Давайте удалим его:

use std::cmp::Ord; 
use std::clone::Clone; 

trait MergeSortable<T> { 
    fn merge_sort(&mut self); 
    fn _merge(left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T>; 
} 

impl<T: Ord + Clone + PartialEq> MergeSortable<T> for Vec<T> { 
    fn merge_sort(&mut self) { 
     if self.len() <= 1 { 
      return; 
     } 
     let mid = self.len()/2; 
     let mut left = self[..mid].to_vec(); 
     left.merge_sort(); 
     let mut right = self[mid..].to_vec(); 
     right.merge_sort(); 
     self = Self::_merge(&mut left, &mut right); 
    } 

    fn _merge(left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> { 
     if left.len() == 0 { 
      return {right}; 
     } 
     if right.len() == 0 { 
      return {left}; 
     } 
     if left[0] < right[0] { 
      let mut v: Vec<T> = Vec::new(); 
      v.push(left[0].clone()); 
      v.extend_from_slice(&Self::_merge(&mut left[1..].to_vec().clone(), &mut right.clone())[..]); 
      return &mut v; 
     } 
     let mut v: Vec<T> = Vec::new(); 
     v.push(right[0].clone()); 
     v.extend_from_slice(&Self::_merge(&mut left.clone(), &mut right[1..].to_vec().clone())[..]); 
     return &mut v; 
    } 
} 

Теперь мы получаем другую ошибку:

error: missing lifetime specifier [--explain E0106] 
--> <anon>:6:57 
    |> 
6 |>  fn _merge(left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T>; 
    |>               ^^^^^^^^^^^ 
help: this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from `left` or `right` 

error: missing lifetime specifier [--explain E0106] 
    --> <anon>:22:57 
    |> 
22 |>  fn _merge(left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T> { 
    |>               ^^^^^^^^^^^ 
help: this function's return type contains a borrowed value, but the signature does not say whether it is borrowed from `left` or `right` 

И это помогает нам понять, первая проблема: когда есть параметр self и возвращаемое значение является ссылкой, то компилятор будет считать, что время жизни возвращаемой ссылки связано с self. Это совсем не так! Удалив параметр self, компилятор сталкивается с двумя аргументами, которые являются ссылками, а текущие правила элиции делают так, чтобы вы должны указать явное время жизни.

Итак, давайте сделаем это!

use std::cmp::Ord; 
use std::clone::Clone; 

trait MergeSortable<T> { 
    fn merge_sort(&mut self); 
    fn _merge<'a>(left: &'a mut Vec<T>, right: &'a mut Vec<T>) -> &'a mut Vec<T>; 
} 

impl<T: Ord + Clone + PartialEq> MergeSortable<T> for Vec<T> { 
    fn merge_sort(&mut self) { 
     if self.len() <= 1 { 
      return; 
     } 
     let mid = self.len()/2; 
     let mut left = self[..mid].to_vec(); 
     left.merge_sort(); 
     let mut right = self[mid..].to_vec(); 
     right.merge_sort(); 
     self = Self::_merge(&mut left, &mut right); 
    } 

    fn _merge<'a>(left: &'a mut Vec<T>, right: &'a mut Vec<T>) -> &'a mut Vec<T> { 
     if left.len() == 0 { 
      return right; 
     } 
     if right.len() == 0 { 
      return left; 
     } 
     if left[0] < right[0] { 
      let mut v: Vec<T> = Vec::new(); 
      v.push(left[0].clone()); 
      v.extend_from_slice(&Self::_merge(&mut left[1..].to_vec().clone(), &mut right.clone())[..]); 
      return &mut v; 
     } 
     let mut v: Vec<T> = Vec::new(); 
     v.push(right[0].clone()); 
     v.extend_from_slice(&Self::_merge(&mut left.clone(), &mut right[1..].to_vec().clone())[..]); 
     return &mut v; 
    } 
} 

Но теперь мы получаем больше ошибок. Давайте сосредоточимся на этом:

error: `v` does not live long enough 
    --> <anon>:33:25 
    |> 
33 |>    return &mut v; 
    |>      ^
note: reference must be valid for the lifetime 'a as defined on the block at 22:81... 
    --> <anon>:22:82 
    |> 
22 |>  fn _merge<'a>(left: &'a mut Vec<T>, right: &'a mut Vec<T>) -> &'a mut Vec<T> { 

Вы пытаетесь вернуть ссылку на локальную переменную. Вы не можете этого сделать: вы должны вернуть само значение, как и в своей первоначальной функции. См. Return local String as a slice (&str) для получения дополнительной информации.

Возможно, один трюк, о котором вы не знали, заключается в том, что вы можете заменить значение за ссылкой, назначив его разыменование (*self = new_value).

use std::cmp::Ord; 
use std::clone::Clone; 

trait MergeSortable<T> { 
    fn merge_sort(&mut self); 
    fn _merge(left: Vec<T>, right: Vec<T>) -> Vec<T>; 
} 

impl<T: Ord + Clone + PartialEq> MergeSortable<T> for Vec<T> { 
    fn merge_sort(&mut self) { 
     if self.len() <= 1 { 
      return; 
     } 
     let mid = self.len()/2; 
     let mut left = self[..mid].to_vec(); 
     left.merge_sort(); 
     let mut right = self[mid..].to_vec(); 
     right.merge_sort(); 
     *self = Self::_merge(left, right); 
    } 

    fn _merge(left: Vec<T>, right: Vec<T>) -> Vec<T> { 
     if left.len() == 0 { 
      return right; 
     } 
     if right.len() == 0 { 
      return left; 
     } 
     if left[0] < right[0] { 
      let mut v: Vec<T> = Vec::new(); 
      v.push(left[0].clone()); 
      v.extend_from_slice(&Self::_merge(left[1..].to_vec(), right)[..]); 
      return v; 
     } 
     let mut v: Vec<T> = Vec::new(); 
     v.push(right[0].clone()); 
     v.extend_from_slice(&Self::_merge(left, right[1..].to_vec())[..]); 
     return v; 
    } 
} 

Я хотел бы также рассмотреть вопрос о переносе _merge из признака и в свободную функцию, так что вам не придется писать Self::_merge назвать.

Answer 2

Я не понимаю, как это работает, прежде чем вы превратили его в версии признака. Проблема с подписью _merge:

fn _merge(&self, left: &mut Vec<T>, right: &mut Vec<T>) -> &mut Vec<T>; 

Это подпись на самом деле является сокращением для:

fn _merge<'a>(&'a self, left: &mut Vec<T>, right: &mut Vec<T>) -> &'a mut Vec<T>; 

Это означает, что возвращаемое значение должно быть заимствуют от self. В вашем случае это абсолютно не так, поскольку вы либо возвращаете left, либо right, или совершенно новый вектор (и вы can't return a reference to a local variable). Самый простой способ исправить это - это вернуть только Vec<T>. Или если вы хотите сохранить .clone() при возврате left или right, вы можете вернуть Cow<[T]> (я не думаю, что это того стоит).

Кроме того, я думаю, что _merge действительно не относится к признаку, вы даже не используете self. Я бы сделал это просто функцией.