First attempt at a ChoiceStream implementation

[sstangl]

This is a WIP patch for attempting to get some Superposition tests running for Maxwell. For context, Maxwell is implemented in terms of async Streams, which are effectively async Iterators.

The usage of a stream is via, e.g., stream.next().await. Internally, this adds a Task for the stream to the executor. Every time that task is scheduled, it calls a synchronous poll_next() function that returns either Pending or Ready(Some(Item)).

This patch was an experiment to see if I can get away with not open-coding the Superposition epsilon choice logic in Maxwell's Batcher: instead, since it's already idiomatic for one Stream to defer to another, I thought I'd see if it would work to wrap the choice logic into a ChoiceStream, so the Batcher can call choice_stream.poll_next(), and only maintain a small explicit state machine inside itself for continuation.

Since the poll_next() function is synchronous, this code can't use the same yield_now() trick that hilberts_epsilon() uses. Instead, I tried to queue a bunch of tasks where their relative scheduler ordering determines the choice. The first attempt didn't go so hot, but I have some ideas for improving it. At the moment, it reaches many duplicate states because it tries all combinations of sub-tasks, even though the majority of their ordering is unrelated to the ultimate choice.

There's an additional problem with this setup though: if the Batcher stream defers to the ChoiceStream for polling, then that means there are two tasks that poll. So for example, if the batcher wants to choose from 3 possible choices, it will create the following task queue (in the current setup)

1. Batcher
2. ChoiceStream
3. Set Choice to 1
4. Set Choice to 2

All orderings where Batcher < ChoiceStream are useless, because the Batcher will just return Poll::Pending. And indeed there are an infinite number of such orderings, since on each Pending return, the Batcher task is re-queued!

Really the way I would want to implement this is to remove the Batcher task from the task queue entirely, and then teach the ChoiceStream to re-enqueue it after the choice has been made. As far as I can tell the interface doesn't exist for that, but maybe I can manually reach into the Executor?

[sstangl]

Oh, of course, ignore that last part about the Batcher/ChoiceStream interaction: it's just one task, the Batcher, which calls choice_stream.poll_next(), which never returns Pending.

[rw]

Interesting stuff!