Managing multiple slices of the same section of memory

Question

I've been banging my head against the wall trying to figure out how to manage multiple slices of the same larger slice. My primary motivation for doing this is I have some large slice that I start with, and gradually work with smaller and smaller subslices until the subslice contains only one element.

From a high level perspective, it isn't obvious to me why this can't be done, as I don't need to move or mutate the original slice. I only need multiple views of the slice with the same lifetime as the original slice.

To illustrate, refer to this diagram:

The original slice is in green, and each layer down represents slices of smaller and smaller size until only one element is in the slice. What I want is to ensure that the lifetime of the elements of each slice to "reach through" to the original slice, and not depend on the lifetime of the slice above it. I am using these slices inside of a while loop, and storing each of the slices in a queue that lasts for the duration of the loop.

The problem I'm running into is that the slices don't "live long enough", though I don't quite understand why that's the case.

Since each of the slices only reference the original slice, would it be possible to store these slices as "owned slices" in the queue rather than new vectors? Is there even a difference in performance? Would it be better to just store the indexes of the slice bounds in a queue for later? Any and all help is appreciated, thank you.

Here is some code that precisely demonstrates the issue:

pub struct Split<'a> {
    pub first_half: &'a [&'a [u8]],
    pub second_half: &'a [&'a [u8]],
}

impl<'a> Split<'a> {
    pub fn new(first_half: &'a [&'a [u8]], second_half: &'a [&'a [u8]]) -> Split<'a> {
        Self {
            first_half,
            second_half,
        }
    }
}

fn make_smaller_slice<'a>(slice: &'a [&'a [u8]]) -> Vec<&'a [u8]> {
    let mut smaller_slice = Vec::with_capacity(slice.len());
    for elem in slice {
        if true {
            smaller_slice.push(*elem)
        }
    }

    smaller_slice
}

fn main() {
    let mut original_data = Vec::with_capacity(100);
    for i in 0..100 {
        original_data.push(vec![i]);
    }
    let original_slice = original_data
        .iter()
        .map(|x| x.as_slice())
        .collect::<Vec<_>>();
    let mut split_queue = vec![];
    split_queue.push(Split::new(&original_slice[0..50], &original_slice[50..100]));
    loop {
        let split = split_queue.remove(0);
        let first_half = split.first_half.split_at(split.first_half.len() / 2);

        let processed_first_half_0 = make_smaller_slice(&first_half.0);
        let processed_first_half_1 = make_smaller_slice(&first_half.1);

        let first_split = Split::new(&processed_first_half_0, &processed_first_half_1);
        split_queue.insert(0, first_split);
    }
}

And the resulting errors:

error[E0597]: `processed_first_half_0` does not live long enough
  --> src/main.rs:44:38
   |
38 |         let split = split_queue.remove(0);
   |                     ----------- borrow used here, in later iteration of loop
...
44 |         let first_split = Split::new(&processed_first_half_0, &processed_first_half_1);
   |                                      ^^^^^^^^^^^^^^^^^^^^^^^ borrowed value does not live long enough
45 |         split_queue.insert(0, first_split);
46 |     }
   |     - `processed_first_half_0` dropped here while still borrowed

error[E0597]: `processed_first_half_1` does not live long enough
  --> src/main.rs:44:63
   |
38 |         let split = split_queue.remove(0);
   |                     ----------- borrow used here, in later iteration of loop
...
44 |         let first_split = Split::new(&processed_first_half_0, &processed_first_half_1);
   |                                                               ^^^^^^^^^^^^^^^^^^^^^^^ borrowed value does not live long enough
45 |         split_queue.insert(0, first_split);
46 |     }
   |     - `processed_first_half_1` dropped here while still borrowed

ChosunOne ChosunOne · Accepted Answer · 2019-03-03T11:55:52

Modifying make_smaller_slice to return a reference to a slice instead of a vector resolves the issue.

pub struct Split<'a> {
    pub first_half: &'a [&'a [u8]],
    pub second_half: &'a [&'a [u8]]
}

impl<'a> Split<'a> {
    pub fn new(first_half: &'a [&'a [u8]], second_half: &'a [&'a [u8]]) -> Split<'a> {
        Self {
            first_half,
            second_half
        }
    }
}

fn make_smaller_slice<'a>(slice: &'a [&'a [u8]]) -> &'a[&'a [u8]] {
    let mut start_bound = 0;
    for i in 0..slice.len() {
        if true {
            start_bound = i;
        } 
    }

    &slice[start_bound..]
}

fn main() {
    let mut original_data = Vec::with_capacity(100);
    for i in 0..100 {
        original_data.push(vec![i]);
    }
    let original_slice = original_data.iter().map(|x| x.as_slice()).collect::<Vec<_>>();
    let mut split_queue = vec![];
    split_queue.push(Split::new(&original_slice[0..50], &original_slice[50..100]));
    loop {
        let split = split_queue.remove(0);
        let first_half = split.first_half.split_at(split.first_half.len() / 2);

        let processed_first_half_0 = make_smaller_slice(&first_half.0);
        let processed_first_half_1 = make_smaller_slice(&first_half.1);

        let first_split = Split::new(&processed_first_half_0, &processed_first_half_1);
        split_queue.insert(0, first_split);
    }
}

Credit to _TheDust_ from Reddit for this.

Managing multiple slices of the same section of memory

2 Answers