You can use chapters 10.3 and 19.2 as a reference for these exercices.

As a motivating example for this section, let us consider the idea of a task scheduler. The user can write tasks (units of computation) which should be run, and each task can schedule additional tasks to run after it has completed.

You will have to write a parallel runtime for such a scheduler in the project -- but for now, let us consider a simpler, sequential implementation to illustrate some lifetime issues. Below is a simple implementation using a queue of tasks backed by a vector of references. The code is correct, but there are some lifetime issues which Rust is complaining about. Explain why, and make the code compile using only lifetime annotations.

/// A task represents an unit of computation.
trait TaskMut: 'static {
    /// Execute the task.  The task can use the scheduler to mark additional tasks as needing to be
    /// run.
    fn execute_mut(&mut self, scheduler: &mut dyn Scheduler);
}

/// A scheduler object allowing to register tasks to be executed asynchronously.
trait Scheduler {
    /// Schedule a new task to be executed.  The `Scheduler` should not execute the task
    /// immediately; rather, the task should be stored in an auxiliary data structure and executed
    /// at a later time.  The caller should ensure that any prerequisites for the task's execution
    /// are met.
    fn schedule_mut(&mut self, task: &mut dyn TaskMut);
}

/// A basic runtime.  It maintains ready vector of tasks to schedule, and executes them
/// sequentially.  When executing, tasks can schedule additional tasks to run later.
///
/// The intended use case is that tasks should be pre-allocated before being
/// passed to the `Runtime`, which doesn't care about memory management at all.
/// Hence, the `Runtime` type takes a lifetime `'r` as argument, which is a
/// lower bound on the lifetime of the tasks.
struct Runtime<'r> {
    /// Ready vector of tasks to execute.
    ready: Vec<&'r mut dyn TaskMut>,
}

impl<'r> Runtime<'r> {
    /// Create a new Runtime from a vector of tasks references.
    fn new(ready: Vec<&'r mut dyn TaskMut>) -> Self {
        Runtime { ready }
    }

    /// Execute tasks until none are left.
    fn execute(&mut self) {
        while let Some(task) = self.ready.pop() {
            task.execute_mut(self)
        }
    }
}


// Implement the Scheduler trait for the Runtime.  We want tasks to be able to register additional
// tasks when being run.
impl<'r> Scheduler for Runtime<'r> {
    /// Schedule a task by registering it into the runtime's `ready` queue.
    fn schedule_mut(&mut self, task: &mut dyn TaskMut) {
        self.ready.push(task)
    }
}

fn main() {}

Hint: we should only be able to schedule tasks which outlive the scheduler -- otherwise we could end up with dangling pointers when we get to executing them. The following code must be prevented somehow:

struct NoOp;

impl TaskMut for NoOp {
    fn execute_mut(&mut self, _: &mut dyn Scheduler) {
        // This is called "NoOp". What did you expect?
    }
}

fn main() {
    let mut runtime = Runtime::new(Vec::new());

    {
        let mut stack_task = NoOp;
        runtime.schedule(&mut stack_task);
    }

    // The runtime cannot still have a reference to `stack_print` here!
    runtime.execute()
}

We are using references in the runtime because we want to be able to run our graph of tasks multiple times, possibly in different runtimes (for instance, the tasks could implement one step of a physical simulation - or video game loop). Hence the following code, which takes a vector of owned tasks and runs them using a local scheduler, should be allowed:

# #![allow(unused_variables)]
#fn main() {
fn execute(tasks: &mut Vec<Box<dyn TaskMut>>) {
    let mut runtime = Runtime::new(tasks.iter_mut().map(Box::as_mut).collect());
    runtime.execute();
}
#}

Does your solution to question 1 allow this use case? If not, propose another solution which does not prevent re-executing the tasks with a different scheduler.

Hint: tasks should not be tied to a particular scheduler lifetime. They need to be usable with any lifetime, as long as we have a sufficiently long-lived reference.

We added a constraint that the TaskMut trait must have a 'static lifetime, i.e. should not contain any reference. Alter the lifetime annotations to allow tasks to contain references.

Hint: tasks should still not be tied to a particular lifetime. Remove the 'static bound and let the compiler guide you.

We want tasks to be able to schedule other tasks, which is currently not possible, as evidenced by the following Loop task which doesn't typecheck:

# #![allow(unused_variables)]
#fn main() {
struct Loop;

impl TaskMut for Loop {
    fn execute_mut<'r>(&mut self, scheduler: &mut dyn Scheduler<'r>) {
        scheduler.schedule_mut(self)
    }
}
#}

Can you find a way to make it work with only lifetime annotations? Is it possible to add an inner task to the Loop as a body (so that the definition becomes struct Loop<T> { body: T }), calling execute_mut on the body each time the Loop is scheduled (in addition re-scheduling the Loop)?

Let's try to find a formulation where we can write a loop. Remove the extra lifetime from the TaskMut trait so that the signature of execute_mut is fn execute_mut<'r>(&mut self, scheduler: &mut dyn Scheduler<'r> again.

We now define the following extra traits:

# #![allow(unused_variables)]
#fn main() {
trait Task {
    fn execute<'r>(&self, scheduler: &mut dyn Scheduler<'r>);
}

trait TaskBox {
    fn execute_box<'r>(self: Box<Self>, scheduler: &mut dyn Scheduler<'r>);
}
#}

and add the corresponding schedule(&mut self, node: &'r dyn Task) and schedule_box(&mut self, node: Box<dyn TaskBox + 'r>) methods on the Scheduler trait. Which of the following impls can you write?

• impl<T: Task> Task for Loop<T>
• impl<T: Task> TaskMut for Loop<T>
• impl<T: TaskMut> TaskMut for Loop<T>
• impl<T: Task> TaskBox for Loop<T>
• impl<T: TaskMut> TaskBox for Loop<T>
• impl<T: TaskBox> TaskBox for Loop<T>

What is the difference between the TaskBox trait and the TaskMut with a &'r mut self parameter from the previous question?

Let us add an explicit runtime reference to the Task trait:

# #![allow(unused_variables)]
#fn main() {
trait Task {
    fn execute<'r>(&'r self, scheduler: &mut dyn Scheduler<'r>);
}
#}

Can you now write an impl<T: Task> Task for Loop<T>? Can you explain why it works for Task but not TaskMut?

Hint: for implementing a loop, we need two things: tasks which are able to re-schedule themselves, and tasks which are able to schedule repeatedly inner tasks. Is it possible to encode those two capabilities in the same trait taking mutable references? What about immutable references?