Using a Scoped Allocator in Generic Code

Hi, I’m trying to create som kind of stack allocator so I can preallocate memory for vector computations. However I get stuck when I try to turn my current results into a trait.

My current allocator looks as follows:

pub struct Alloc<'a,T> where T: 'a {
    buffer: &'a mut [T],
}

impl<'a,T> Alloc<'a,T> {

    pub fn alloc(&mut self, count: usize) -> &'a mut [T] {
        let mut buffer = &mut [][..]; // dummy value
        std::mem::swap(&mut self.buffer, &mut buffer);
        let (a, rest) = buffer.split_at_mut(count);
        self.buffer = rest;
        a
    }

    pub fn scope<'b>(&'b mut self) -> Alloc<'b,T> where 'a:'b {
        Alloc {
            buffer: self.buffer
        }
    }

    pub fn scoped<'b, F, U>(&'b mut self, f: F) -> U where F: Fn(Alloc<'b,T>) -> U, 'a:'b {
        f(self.scope())
    }
}

This can now be used to preallocate memory which is then used in computations:

fn main() {
    let mut buffer = [1,2,3,4,5,6,7];
    let mut a = Alloc{buffer: &mut buffer};
    
    {
        let mut a = a.scope();
        let mut v = a.alloc(2);
        v[0] *= 10;
        v[1] *= 10;
    }
        {
        let mut a = a.scope();
        let mut v = a.alloc(2);
        v[0] *= 10;
        v[1] *= 10;
    }
    println!("Memory got reused: 1*10*10 = {:?}", a.buffer[0]); // prints 100
}

(https://play.rust-lang.org/?gist=0ad60f8ce3fad00beafae3e721e3551b&version=stable&mode=debug&edition=2015)

Now, I want to turn the scope function into a trait. However, I can’t figure out how to define the trait.
I tried

pub trait Scope<'c> {
    type Scope;
    fn sscope(&'c mut self) -> Self::Scope ;
}

impl<'a,'b,T> Scope<'b> for Alloc<'a,T> where 'a:'b {
    type Scope = Alloc<'b,T>;
    fn sscope(&'b mut self) -> Alloc<'b,T>   {
        Alloc {
            buffer: self.buffer
        }
    }
}

which compiles fine, however I can’t figure out how to use it in a generic function and get an error[E0597]: s does not live long enough

fn compliles(mut s: Alloc<'_,u32>) {
    {
        let _s1 = s.sscope();
    } {
        let _s2 = s.sscope();
    }
}

fn error<'b,S:Scope<'b> + 'b>(mut s: S) {
    {
        let s1 = s.sscope();
    } {
        let s2 = s.sscope();
    }
}

(https://play.rust-lang.org/?gist=ff1cdaa66fc12293896fe649edaad8a6&version=stable&mode=debug&edition=2015)

Does anybody have an idea how to define the trait, such that the generic version works too? I want to be able to create scopes such that I can reuse the allocated memory inside them.

Thank you for your help!

Not sure you can improve upon the likely undesirable;

pub trait Scope<'a, T> {
    fn sscope<'b>(&'b mut self) -> Box<dyn Scope<'b, T> + 'b> where 'a:'b;
}

These scenarios really need the GAT feature. This is a good blog post investigating alternatives. There’s really no great solution, however - certainly nothing that approaches the natural path that GATs provide.

Your immediate compilation problem can be fixed with:

fn error<S: for<'b> Scope<'b>>(mut s: S)

But I think you’ll find this method not really callable with the type you want to use.

Perhaps instead of trying to return a scope, expose a method somewhat similar to scoped(); it would take a closure and an allocation request, and provide the allocated slice to the closure.

Also, is there a reason for the Scope associated type? Instead of that, could all Scope impls return some concrete type from sscope that always borrows from self? I guess it’s unclear on what types of impls you’re trying to abstract over. Perhaps the abstraction is unnecessary.

Thank you both for help! :slight_smile:

Based on your suggestions I came up with the following which seems to work quite well and should be good enough for now:

pub trait Scope<'a> {
    fn scope<'b>(&'b mut self) -> Box<Scope<'b> + 'b>;
    fn alloc(&mut self, count: usize) -> &'a mut [u8];
    fn scoped<'b, F, U>(&'b mut self, f: F) -> U where F: Fn(&mut dyn Scope<'b>) -> U, Self: Sized {
        // unpack the box
        f(&mut *self.scope3())
    }
}

example: Rust Playground

Even though I still have to think a bit more about all the lifetimes.

I think I need it such that I can allocate multiple times from a scope.