Problems with lifetimes on recursive trait functions

Question

I am having a hard time converting my standalone merge_sort function into a trait for Vec<T>. It seems I am running into lifetime errors with the way the merge sort algorithm works.

I have tried specifying the lifetimes in the function and trait declarations but it still is giving me a similar error.

My research on lifetimes includes...

Effective Rust
The Rust book
Several YouTube videos on lifetimes
Most questions on Stack Overflow regarding lifetimes

Here is the code

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)

And the errors:

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> {
   |>     ^

@Shepmaster: The code has many issues, and this is just one of them... — Francis Gagné, Sep 17 '16 at 20:20
Answerers may also be interested in [giving OP a code review of this and other sort algorithms](http://codereview.stackexchange.com/q/141605/32521). — Shepmaster, Sep 17 '16 at 20:20
@electrometro that was directed more at me than at you ^_^. I tend to have a heavy hand with marking questions as duplicates; that was a way of telling me that such a duplicate would not serve useful. — Shepmaster, Sep 17 '16 at 20:21
@Shepmaster I am just hangry and taking everything to the extreme the first read though. ;) — Jared Mackey, Sep 17 '16 at 20:22

score 4 · Accepted Answer · edited May 23 '17 at 11:54

_merge doesn't actually need its self argument. Let's remove it:

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;
    }
}

Now we're getting a different error:

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`

And this helps us understand the first problem: when there's a self parameter and the return value is a reference, the compiler will infer that the lifetime of the returned reference is linked to self. That's not the case at all here! By removing the self parameter, the compiler is faced with two arguments that are references, and the current elision rules make it so that you must specify an explicit lifetime.

So, let's do that!

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;
    }
}

But now, we're getting more errors. Let's focus on this one:

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> {

You're trying to return a reference to a local variable. You can't do that: you must return the value itself, just like you were doing in your original function. See Return local String as a slice (&str) for more information.

Perhaps one trick you didn't know about is that you can replace the value behind a reference by assigning to its dereference (*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;
    }
}

I would also consider moving _merge out of the trait and into a free function, so that you don't have to write Self::_merge to call it.

Nice! This is full of hidden tricks I couldn't figure out after about an hour of messing with the lifetimes. So by removing self it makes it a static function, correct? — Jared Mackey, Sep 17 '16 at 20:34
Yes, removing `self` makes `_merge` a static function, but as it's in a trait, it's still polymorphic, so we need to write `Self::` or `MergeSortable::` before its name when calling it, so that the compiler knows which implementation we want to call. — Francis Gagné, Sep 17 '16 at 23:36

score 2 · Answer 2 · edited May 23 '17 at 11:54

I don't see how this worked before you converted it to a trait version. The problem is with the the signature of _merge:

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

That signature is actually a shorthand for:

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

That means, that the returned value must be a borrow from self. In your case, that's totally not true, as you either return left or right, or a totally new vector (and you can't return a reference to a local variable). The easiest way to fix it would be to return just Vec<T>. Or if you want to save a .clone() when returning left or right, you can return a Cow<[T]> (I don't think it's worth it though).

Also, I think that _merge doesn't really belong to a trait, you're not even using self there. I'd make it just a function.

It was a [free function before](http://codereview.stackexchange.com/q/141605/32521). — Shepmaster, Sep 17 '16 at 20:18

Problems with lifetimes on recursive trait functions

2 Answers2