Better documentation for how to create an Executor

[Pauan]

When creating a new Executor from scratch, there's a lot of subtle behavior which currently isn't documented.

This can create edge cases where one Executor behaves differently from another Executor, and Futures might start to rely upon the behavior of a particular Executor.

I believe these behaviors should be documented:

• If a Future calls task.notify() multiple times within a certain time frame, it's allowed for the Executor to only call poll once (rather than once per task.notify())

  Of course an Executor must call poll after task.notify(), but it is allowed to combine multiple calls to task.notify() together. As an example:

  let task = futures::task::current();
  
  task.notify();
  task.notify();

  With the above code, the Executor is allowed to call poll only once, even though task.notify() was called twice.

• Under certain pathological situations, it is allowed for the Executor to deadlock.

  For example, a Future that calls task.notify() inside of poll can sometimes trigger an infinite loop:

  struct MyFuture;
  
  impl Future for MyFuture {
      type Item = ();
      type Error = ();
  
      fn poll(&mut self) -> futures::Poll<Self::Item, Self::Error> {
          let task = futures::task::current();
  
          task.notify();
  
          Ok(futures::Async::NotReady)
      }
  }

  In the above example, it is allowed for the Executor to deadlock, go into a 100% CPU infinite loop, etc.

  In non-pathological situations, it is allowed for a Future to call task.notify() inside of poll, and in that situation the Executor must not deadlock.

• Futures aren't supposed to call task.notify() if they cannot make any progress.

  This is related to the above point. If a Future calls task.notify() when nothing will change, then there is the possibility of a deadlock, so they shouldn't do that.

  This isn't a contract for Executors, it's a contract for Futures, but it affects the way that Executors are allowed to be implemented.

  In particular, if a Future calls task.notify() without making any progress, then the behavior of the Executor is undefined and it can do anything it wants, including deadlock.

• Executors are allowed to synchronously call the poll method immediately when task.notify() is called. In other words, it isn't guaranteed that task.notify() is always asynchronous.

  This affects any situation where a Future calls task.notify() and then proceeds to do something afterwards. The Future has to deal with the possibility that when it calls task.notify() it might immediately have consequences.

  A contrived example is sharing a RefCell between two Futures. If Future A mutably borrows the RefCell, and then it calls task.notify() which triggers Future B, and the poll implementation of Future B also mutably borrows the RefCell, then it might trigger a panic.

  This behavior is allowed because the Executor is allowed to call the poll method immediately when task.notify() is called, so Futures need to plan for that.

• When calling task.notify(), it must not call poll immediately. In other words, task.notify() must always be delayed, it yields to the event loop.

[alexcrichton]

cc @aturon, perhaps excellent fodder for the book you're writing?

[Pauan]

In particular, if a Future calls task.notify() without making any progress, then the behavior of the Executor is undefined and it can do anything it wants, including deadlock.

For Futures that don't make progress, deadlocks (and probably panics) should be allowed, but I'm not sure if it should actually be undefined behavior. But I'm not an expert on Futures, so that's for you guys to decide.

[carllerche]

IMO:

Executors are allowed to synchronously call the poll method immediately when task.notify() is called. In other words, it isn't guaranteed that task.notify() is always asynchronous.

should not be true as this could wreak havoc on things like Tokio, timers, etc...

[Pauan]

@carllerche But it's already true: there are various Executors which behavior that way, e.g. .wait()

Everything I described is behaviors that Executors already have, I am not suggesting new behaviors.

Whether the behaviors should be changed is a different issue, this issue is just about documenting the current behaviors (obviously if the behavior is changed then the docs should be changed to match).

[carllerche]

@Pauan Perhaps I misunderstood what you meant, my interpretation of the original statement is not how wait is implemented.

Notify is a trait. no implementation of Notify::notify should call poll on a future.

[ipetkov]

@Pauan

Futures aren't supposed to call task.notify() if they have not made any progress.

I'd like to make a subtle distinction here: Futures aren't supposed to call task.notify() if they cannot yet make any progress. A notify() denotes the potential of making progress, but it's not proof that progress was made.

This is related to the above point. If a Future calls task.notify() when nothing has changed, then there is the possibility of a deadlock, so they shouldn't do that.

If a Future calls task.notify() but can't make any progress, it would just burn CPU as it keeps spinning, but shouldn't deadlock, as long as the executor implements a form of fairness by giving other futures a chance to run if they have called task.notify()

[Pauan]

@carllerche You're right, I just tested .wait() and it seems that task.notify() is indeed delayed.

Requiring task.notify() to always yield complicates certain single-threaded environments (such as JavaScript), but I suppose it does make logical sense to require it to be delayed.

Notify is a trait. no implementation of Notify::notify should call poll on a future.

That sounds very odd to me: the whole purpose of task.notify() is to cause the Executor to (eventually) call poll on the Future. Could you explain more what you mean?

---

@ipetkov A notify() denotes the potential of making progress, but it's not proof that progress was made.

That's a good point, I'll change it.

If a Future calls task.notify() but can't make any progress, it would just burn CPU as it keeps spinning, but shouldn't deadlock

But it will cause a deadlock on some single-threaded implementations of Executor (such as .wait()). I'm not saying that it should deadlock, I'm just saying that it's acceptable for the Executor to deadlock.

---

I have edited the original post to incorporate the changes.

[carllerche]

@Pauan

That sounds very odd to me: the whole purpose of task.notify() is to cause the Executor to (eventually) call poll on the Future. Could you explain more what you mean?

Running in a javascript VM would be a very different case due to fundamental limitations. However, in Rust, libs are being designed assuming that task.notify() is very cheap. For example, the Tokio runtime assumes that no user code will ever get run on the epoll loop (by default).

If an executor implements notify() to immediately call poll, this would break the assumption.

[Pauan]

@carllerche I see, you just meant that task.notify() shouldn't directly and immediately call poll

[aturon]

I'm going to go ahead and close this out in light of the re-written docs for 0.2, as well as the (eventual) book, which will talk about this in depth.