Argument escapes function body

help
1

Functions median_idx, partition_idx, and partition_slice are unchanged in the correct and the incorrect code.

// *******************************************************************
fn median_idx(v: &[i32]) -> usize {
    let l = v.len() - 1;
    let m = v.len() / 2;
    if v[0] < v[m] {
        if v[m] < v[l] {
            m
        } else if v[0] < v[l] {
            l
        } else {
            0
        }
    } else {
        if v[m] > v[l] {
            m
        } else if v[0] > v[l] {
            l
        } else {
            0
        }
    }
}

// *******************************************************************
fn partition_idx(v: &mut [i32], px: usize) -> (usize, usize) {
    let e = v.len();
    let pivot = v[px];
    let (mut l, mut m, mut r): (usize, usize, usize) = (0, 0, e);

    while m < r {
        if v[m] < pivot {
            if l < m {
                v.swap(l, m);
            }
            l += 1;
            m += 1;
        } else if pivot < v[m] {
            if m + 1 < r {
                v.swap(m, r - 1);
            }
            r -= 1;
        } else {
            // pivot == v[m]
            m += 1;
        }
    }

    assert!(l < m);
    (l, m)
}

// *******************************************************************
pub fn partition_slice(v: &mut [i32], px: usize) -> (&mut [i32], &mut [i32]) {
    let (l, m) = partition_idx(v, px);
    let (left, mid_right) = v.split_at_mut(l);
    let (_, right) = mid_right.split_at_mut(m - l);
    (left, right)
}

When doing sequential recursion, code compiles correctly:

// *******************************************************************
pub fn qsort(vv: &mut [i32]) {
    let mut v = vv;

    while v.len() > 2 {
        let px = median_idx(v);
        let (left, right) = partition_slice(v, px);
        let (smaller, larger) = if left.len() < right.len() {
            (left, right)
        } else {
            (right, left)
        };
        if smaller.len() > 1 {
            qsort(smaller);
        }
        v = larger;
    }
    if v.len() == 2 {
        // 2 elements exactly
        if v[0] > v[1] {
            v.swap(0, 1);
        }
    }
}

However, when the recursive call is executed in a separate thread, the compiler errors:

// *******************************************************************
pub fn qsort(vv: &mut [i32]) {
    let mut v = vv;
    let handles = Vector::new();

    while v.len() > 2 {
        let px = median_idx(v);
        let (left, right) = partition_slice(v, px);
        let (smaller, larger) = if left.len() < right.len() {
            (left, right)
        } else {
            (right, left)
        };
        if smaller.len() > 1 {
            let handle = thread::spawn(|| {  // recursive call in thread => error
                qsort(smaller);
            });
            handles.push(handle);
        }
        v = larger;
    }
    if v.len() == 2 {
        // 2 elements exactly
        if v[0] > v[1] {
            v.swap(0, 1);
        }
    }
    for handle in handles {
        handle.join();
    }
}

The error message is shown below. The unexpected is that the error message does not refer to the recursive call wrapped in thread(), but to an unchanged called to partition_slice().

cargo build --release
   Compiling escape v0.1.0 (src/escape)
error[E0521]: borrowed data escapes outside of function
  --> src/lib.rs:69:29
   |
64 | pub fn qsort(vv: &mut [i32]) {
   |              --  - let's call the lifetime of this reference `'1`
   |              |
   |              `vv` is a reference that is only valid in the function body
...
69 |         let (left, right) = partition_slice(v, px);
   |                             ^^^^^^^^^^^^^^^^^^^^^^
   |                             |
   |                             `vv` escapes the function body here
   |                             argument requires that `'1` must outlive `'static`

For more information about this error, try `rustc --explain E0521`.
error: could not compile `escape` (lib) due to 1 previous error
2

std::thread::spawn() creates threads that are allowed to outlive the function call, and even the thread, that spawned them. This is true regardless of whether you join() them, because

  • there is no way for a function call like join() to tell the compiler “this causes that other borrowed data to stop being borrowed”, and
  • even if there was, your program would be incorrect in the case where any code between spawn() and join() panics, causing the function to unwind and the vv borrow to be released (and its referent possibly deallocated) while the spawned thread still runs.

The way std::thread::spawn() enforces this rule is that it requires the function passed to it to meet a 'static lifetime bound, which means that every borrow it takes must be 'static, which leads to the error you received. The borrow of smaller, which is derived from vv, escapes in the very direct sense that it now lives on an independent thread.

The solution to this problem is to use std::thread::scope() instead, which does enforce that the spawned threads terminate before the caller does, and therefore allows them to borrow data from the caller.

6 Likes
3

I believe this is caused by type inference:

  1. The closure passed to thread::spawn must be 'static because of the generic bounds on thread::spawn.
  2. Therefore, smaller must have type &'static mut [i32] because it is captured by the closure.
  3. Therefore, left and right must have type &'static mut [i32] because they are assigned to smaller.
  4. Therefore, partition_slice must be called with an &'static mut [i32], which causes the error message about mismatched lifetimes.
1 Like
4

Thank you for the explanation! Your second point about panic completely escaped me.

The location of the complaint confused me. Why isn't the compiler complaining about the escape at the thread invocation qsort() rather than at a sequential call partition_slice()?

5

See my comment above for an attempt to explain this. I believe the error points to the partition_slice call because it is the earliest point in the function where the compiler infers an unsatisfiable 'static borrow.

6

More generally, in any situation involving type inference or lifetime inference, you may receive errors that are not positioned “where the mistake is”, but “where the conflict was first noticed”. The compiler doesn't know which you meant — doesn't know whether '1 should be used more places or 'static should be used more places — so it’s not necessarily going to report the one that makes more sense to you.

However, in this case, it’s particularly unfortunate that the error message doesn't mention the original source of the 'static bound at all. It seems that the compiler is not good at reporting this case, in general:

Here's a reduced example of the same failure:

pub fn thread_recursive<'a>(v: &'a mut [i32]) {
    if v.len() == 0 {
        return;
    }
    let (left, right): (&'a mut [i32], &'a mut [i32]) =
        v.split_at_mut(v.len() / 2);
    std::thread::spawn(|| thread_recursive(left));
    std::thread::spawn(|| thread_recursive(right));
}

rror: lifetime may not live long enough
 --> src/lib.rs:5:24
  |
1 | pub fn thread_recursive<'a>(v: &'a mut [i32]) {
  |                         -- lifetime `'a` defined here
...
5 |     let (left, right): (&'a mut [i32], &'a mut [i32]) =
  |                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ type annotation requires that `'a` must outlive `'static`

Even with the type annotation narrowing down which lifetimes go where, the compiler doesn't point to the right place. I've posted this example to #112519.

3 Likes
7

Thanks. thread::scope worked!

8

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.