Vec<MyTrait> without N heap allocations?

Question

I'm trying to port some C++ code to Rust. It composes a virtual (.mp4) file from a few kinds of slices (string reference, lazy-evaluated string reference, part of a physical file) and serves HTTP requests based on the result. (If you're curious, see Mp4File which takes advantage of the FileSlice interface and its concrete implementations in http.h.)

Here's the problem: I want require as few heap allocations as possible. Let's say I have a few implementations of resource::Slice that I can hopefully figure out on my own. Then I want to make the one that composes them all:

pub trait Slice : Send + Sync {
    /// Returns the length of the slice in bytes.
    fn len(&self) -> u64;

    /// Writes bytes indicated by `range` to `out.`
    fn write_to(&self, range: &ByteRange,
                out: &mut io::Write) -> io::Result<()>;
}

// (used below)
struct SliceInfo<'a> {
    range: ByteRange,
    slice: &'a Slice,
}

/// A `Slice` composed of other `Slice`s.    
pub struct Slices<'a> {
    len: u64,
    slices: Vec<SliceInfo<'a>>,
}

impl<'a> Slices<'a> {
    pub fn new() -> Slices<'a> { ... }
    pub fn append(&mut self, slice: &'a resource::Slice) { ... }
}

impl<'a> Slice for Slices<'a> { ... }

and use them to append lots and lots of slices with as few heap allocations as possible. Simplified, something like this:

struct ThingUsedWithinMp4Resource {
    slice_a: resource::LazySlice,
    slice_b: resource::LazySlice,
    slice_c: resource::LazySlice,
    slice_d: resource::FileSlice,
}

struct Mp4Resource {
    slice_a: resource::StringSlice,
    slice_b: resource::LazySlice,
    slice_c: resource::StringSlice,
    slice_d: resource::LazySlice,
    things: Vec<ThingUsedWithinMp4Resource>,
    slices: resource::Slices
}

impl Mp4Resource {
    fn new() {
        let mut f = Mp4Resource{slice_a: ...,
                                slice_b: ...,
                                slice_c: ...,
                                slices: resource::Slices::new()};
        // ...fill `things` with hundreds of things...
        slices.append(&f.slice_a);
        for thing in f.things { slices.append(&thing.slice_a); }
        slices.append(&f.slice_b);
        for thing in f.things { slices.append(&thing.slice_b); }
        slices.append(&f.slice_c);
        for thing in f.things { slices.append(&thing.slice_c); }
        slices.append(&f.slice_d);
        for thing in f.things { slices.append(&thing.slice_d); }
        f;
    }
}

but this isn't working. The append lines cause errors "f.slice_* does not live long enough", "reference must be valid for the lifetime 'a as defined on the block at ...", "...but borrowed value is only valid for the block suffix following statement". I think this is similar to this question about the self-referencing struct. That's basically what this is, with more indirection. And apparently it's impossible.

So what can I do instead?

I think I'd be happy to give ownership to the resource::Slices in append, but I can't put a resource::Slice in the SliceInfo used in Vec<SliceInfo> because resource::Slice is a trait, and traits are unsized. I could do a Box<resource::Slice> instead but that means a separate heap allocation for each slice. I'd like to avoid that. (There can be thousands of slices per Mp4Resource.)

I'm thinking of doing an enum, something like:

enum BasicSlice {
    String(StringSlice),
    Lazy(LazySlice),
    File(FileSlice)
};

and using that in the SliceInfo. I think I can make this work. But it definitely limits the utility of my resource::Slices class. I want to allow it to be used easily in situations I didn't anticipate, preferably without having to define a new enum each time.

Any other options?

Answer 1

You can add a User variant to your BasicSlice enum, which takes a Box<SliceInfo>. This way only the specialized case of users will take the extra allocation, while the normal path is optimized.