Can only partially solve lifetime issue on code with Mutex/recursion

help
#1

Hello!

I'm working on some parallel and recursive code, but I can figure out only partially the lifetimes required.

The original code is the following:

use std::sync::{Arc, Mutex};

#[derive(Clone, Copy)]
pub struct Intersection<'a> {
    pub object: &'a dyn Shape,
}

pub trait Shape {
    fn intersections(&self) -> Vec<Intersection> {
        // [Some code removed]
        self.local_intersections()
    }

    fn local_intersections(&self) -> Vec<Intersection>;
}

pub struct Group {
    pub children: Mutex<Vec<Arc<dyn Shape>>>,
}

impl Shape for Group {
    fn local_intersections(&self) -> Vec<Intersection> {
        // Can be done via flat_map.

        let mut intersections = vec![];

        let children = &*self.children.lock().unwrap();

        for child in children {
            intersections.extend(child.intersections().iter()); // (Copy)
        }

        intersections
    }
}

(playground)

Now, I originally thought this was the mutex not allowing access to references outside of the MutexGuard scope, however, adding appropriate lifetimes solved the problem:

use std::sync::{Arc, Mutex};

#[derive(Clone, Copy)]
pub struct Intersection<'a> {
    pub object: &'a dyn Shape,
}

pub trait Shape {
    fn intersections<'a>(&self) -> Vec<Intersection<'a>> {
        // [Some code removed]
        self.local_intersections()
    }

    fn local_intersections<'a>(&self) -> Vec<Intersection<'a>>;
}

pub struct Group {
    pub children: Mutex<Vec<Arc<dyn Shape>>>,
}

impl Shape for Group {
    fn local_intersections<'a>(&self) -> Vec<Intersection<'a>> {
        // Can be done via flat_map.

        let mut intersections = vec![];

        let children = &*self.children.lock().unwrap();

        for child in children {
            intersections.extend(child.intersections().iter()); // (Copy)
        }

        intersections
    }
}

(playground)

However, if I add Shape implementors that need to return self, I can't figure out the lifetimes:

use std::sync::{Arc, Mutex};

#[derive(Clone, Copy)]
pub struct Intersection<'a> {
    pub object: &'a dyn Shape,
}

pub trait Shape {
    fn intersections<'a>(&self) -> Vec<Intersection<'a>> {
        // [Some code removed]
        self.local_intersections()
    }

    fn local_intersections<'a>(&self) -> Vec<Intersection<'a>>;
}

pub struct SomeShape {}

impl Shape for SomeShape {
    fn local_intersections<'a>(&self) -> Vec<Intersection<'a>> {
        vec![Intersection { object: self }] // PROBLEM HERE
    }
}

pub struct Group {
    pub children: Mutex<Vec<Arc<dyn Shape>>>,
}

impl Shape for Group {
    fn local_intersections<'a>(&self) -> Vec<Intersection<'a>> {
        // Can be done via flat_map.

        let mut intersections = vec![];

        let children = &*self.children.lock().unwrap();

        for child in children {
            intersections.extend(child.intersections().iter()); // (Copy)
        }

        intersections
    }
}

(playground)

I've also checked out the help for E0495, but I couldn't really connect to the overall problem.

Is there a solution to this? Or am I completely misunderstanding the problem (ie. this is expected when working with Mutex)?

#2

I have the start of a solution for you, but I get stuck before it all compiles; hopefully someone else can help with the next step. (Edit: see next post for an alternate approach)

You lifetime annotation here is incorrect. Because the 'a lifetime isn’t related to self, you can never include any references from self in the output. I’m pretty sure that this signature will prevent you from returning any non-'static reference, actually. The lifetime you actually want to use is '_, the lifetime of &self:

fn intersections(&self)->Vec<Intersection<'_>> { /* ... */ }

Updating the trait definition to this, however, causes problems with your mutex code:


   Compiling playground v0.0.1 (/playground)
error[E0515]: cannot return value referencing temporary value
  --> src/lib.rs:41:9
   |
35 |         let children = &*self.children.lock().unwrap();
   |                          ----------------------------- temporary value created here
...
41 |         intersections
   |         ^^^^^^^^^^^^^ returns a value referencing data owned by the current function

error: aborting due to previous error

(Playground)

This error occurs because local_intersections has to release the mutex before it returns, but the value you want to return holds a reference that’s protected by the mutex.

There’s probably a way to restructure your code to embed the lock guard in the return value, so that the lock remains held until the return value is dropped. Unfortunately, I don’t see how to make that happen off the top of my head.

1 Like
#3

Since you’re already using Arc<dyn Shape> for Group, an alternative is to always use Arc instead of &:


#[derive(Clone)]
pub struct Intersection {
    pub object: Arc<dyn Shape>,
}

pub trait Shape {
    fn intersections(self: Arc<Self>) -> Vec<Intersection> {
        // [Some code removed]
        self.local_intersections()
    }

    fn local_intersections(self: Arc<Self>) -> Vec<Intersection>;
}

(Playground— Contains full code)

#4

Wow, this is insane, which means... brilliant, thanks! :partying_face:

This solved the problem; I wasn't aware of this Rust feature :flushed:.

#5

I think that with the design discussed, it's ultimately possible to change the Group#children type to Vec<Arc<Mutex<dyn Shape>>>; this has, I suppose, the advantage of reducing contention on the vector.

I think it yields to an uglier, C-style, overall design (since, AFAIK, currently one can't use Arc<Mutex<Self>> as self reference), but on the other hand, it still fits cleanly: since Arc<Mutex<T> can be cloned and moved around freely, Intersection.object can be a <Arc<Mutex<T>>>, instead of a MutexGuard<'_, T> (which is a hassle, due to the lifetime).

Thanks again :slight_smile: