blob: 996a160039cb82c11baca0ebb9a991381dd8399f [file]
/-
Copyright (c) 2025 Lean FRO, LLC. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Henrik Böving
-/
module
prelude
public import Init.Data.Random
public import Std.Internal.Async.Basic
import Init.Data.ByteArray.Extra
import Init.Data.Array.Lemmas
import Init.Omega
public section
/-!
This module contains the implementation of a fair and data-loss free IO multiplexing primitive.
The main entrypoint for users is `Selectable.one` and the various functions to produce
`Selector`s from other modules.
-/
namespace Std
namespace Internal
namespace IO
namespace Async
/--
The core data structure for racing on winning a `Selectable.one` if multiple event sources are ready
at the same time. A `Task` can try to finish the waiter by calling `Waiter.race`.
-/
structure Waiter (α : Type) where
private mk ::
private finished : IO.Ref Bool
promise : IO.Promise (Except IO.Error α)
/--
Swap out the `IO.Promise` within the `Waiter`. Note that the part which determines whether the
`Waiter` is finished is not swapped out.
-/
@[inline]
def Waiter.withPromise (w : Waiter α) (p : IO.Promise (Except IO.Error β)) : Waiter β :=
Waiter.mk w.finished p
/--
Try to atomically finish the `Waiter`. If the race for finishing it is won, `win` is executed
with the internal `IO.Promise` of the `Waiter`. This promise must under all circumstances be
resolved by `win`. If the race is lost some cleanup work can be done in `lose`.
-/
@[specialize]
def Waiter.race [Monad m] [MonadLiftT (ST IO.RealWorld) m] (w : Waiter α)
(lose : m β) (win : IO.Promise (Except IO.Error α) → m β) : m β := do
let first ← w.finished.modifyGet fun s => (s == false, true)
if first then
win w.promise
else
lose
/--
Atomically checks whether the `Waiter` has already finished. Note that right after this function
call ends this might have already changed.
-/
@[inline]
def Waiter.checkFinished [Monad m] [MonadLiftT (ST IO.RealWorld) m] (w : Waiter α) : m Bool := do
w.finished.get
/--
An event source that can be multiplexed using `Selectable.one`, see the documentation of
`Selectable.one` for how the protocol of communicating with a `Selector` works.
-/
structure Selector (α : Type) where
/--
Attempts to retrieve a piece of data from the event source in a non-blocking fashion, returning
`some` if data is available and `none` otherwise.
-/
tryFn : Async (Option α)
/--
Registers a `Waiter` with the event source. Once data is available, the event source should
attempt to call `Waiter.race` and resolve the `Waiter`'s promise if it wins. It is crucial that
data is never actually consumed from the event source unless `Waiter.race` wins in order to
prevent data loss.
-/
registerFn : Waiter α → Async Unit
/--
A cleanup function that is called once any `Selector` has won the `Selectable.one` race.
-/
unregisterFn : Async Unit
/--
An event source together with a continuation to call on data obtained from that event source,
usually used together in conjunction with `Selectable.one`.
-/
structure Selectable (α : Type) where
case ::
{β : Type}
/--
The event source.
-/
selector : Selector β
/--
The continuation that is called on results from the event source.
-/
cont : β → Async α
private def shuffleIt {α : Type u} (xs : Array α) (gen : StdGen) : Array α :=
go xs gen 0
where
go (xs : Array α) (gen : StdGen) (i : Nat) : Array α :=
if _ : i < xs.size - 1 then
let (j, gen) := randNat gen i (xs.size - 1)
let xs := xs.swapIfInBounds i j
go xs gen (i + 1)
else
xs
/--
Performs fair and data-loss free multiplexing on the `Selectable`s in `selectables`.
The protocol for this is as follows:
1. The `selectables` are shuffled randomly.
2. Run `Selector.tryFn` for each element in `selectables`. If any succeed, the corresponding
`Selectable.cont` is executed and its result is returned immediately.
3. If none succeed, a `Waiter` is registered with each `Selector` using `Selector.registerFn`.
Once one of them resolves the `Waiter`, all `Selector.unregisterFn` functions are called, and
the `Selectable.cont` of the winning `Selector` is executed and returned.
-/
partial def Selectable.one (selectables : Array (Selectable α)) : Async α := do
if selectables.isEmpty then
throw <| .userError "Selectable.one requires at least one Selectable"
let seed := UInt64.toNat (ByteArray.toUInt64LE! (← IO.getRandomBytes 8))
let gen := mkStdGen seed
let selectables := shuffleIt selectables gen
for selectable in selectables do
if let some val ← selectable.selector.tryFn then
let result ← selectable.cont val
return result
let finished ← IO.mkRef false
let promise ← IO.Promise.new
for selectable in selectables do
let waiterPromise ← IO.Promise.new
let waiter := Waiter.mk finished waiterPromise
selectable.selector.registerFn waiter
discard <| IO.bindTask (t := waiterPromise.result?) fun res? => do
match res? with
| none =>
/-
If we get `none` that means the waiterPromise was dropped, usually due to cancellation. In
this situation just do nothing.
-/
return (Task.pure (.ok ()))
| some res =>
let async : Async _ :=
try
let res ← IO.ofExcept res
for selectable in selectables do
selectable.selector.unregisterFn
let contRes ← selectable.cont res
promise.resolve (.ok contRes)
catch e =>
promise.resolve (.error e)
async.toBaseIO
Async.ofPromise (pure promise)
/--
Performs fair and data-loss free non-blocking multiplexing on the `Selectable`s in `selectables`.
This function only tries the non-blocking `tryFn` for each `Selectable` without registering
waiters or blocking. It returns `some result` if any `Selectable` is immediately available,
or `none` if all would block.
The protocol for this is as follows:
1. The `selectables` are shuffled randomly for fairness.
2. Run `Selector.tryFn` for each element in `selectables`. If any succeed, the corresponding
`Selectable.cont` is executed and its result is returned as `some result`.
3. If none succeed, `none` is returned immediately without blocking.
-/
def Selectable.tryOne (selectables : Array (Selectable α)) : Async (Option α) := do
if selectables.isEmpty then
return none
let seed := UInt64.toNat (ByteArray.toUInt64LE! (← IO.getRandomBytes 8))
let gen := mkStdGen seed
let selectables := shuffleIt selectables gen
for selectable in selectables do
if let some val ← selectable.selector.tryFn then
let result ← selectable.cont val
return some result
return none
/--
Creates a `Selector` that performs fair and data-loss free multiplexing on multiple `Selectable`s.
This allows the multiplexing operation to be composed with other selectors.
-/
def Selectable.combine (selectables : Array (Selectable α)) : IO (Selector α) := do
if selectables.isEmpty then
throw <| .userError "Selectable.one requires at least one Selectable"
let seed := UInt64.toNat (ByteArray.toUInt64LE! (← IO.getRandomBytes 8))
let gen := mkStdGen seed
let selectables := shuffleIt selectables gen
return {
tryFn := do
for selectable in selectables do
if let some val ← selectable.selector.tryFn then
let result ← selectable.cont val
return some result
return none
registerFn := fun waiter => do
for selectable in selectables do
let waiterPromise ← IO.Promise.new
let derivedWaiter := Waiter.mk waiter.finished waiterPromise
selectable.selector.registerFn derivedWaiter
discard <| IO.bindTask (t := waiterPromise.result?) fun res? => do
match res? with
| none => return (Task.pure (.ok ()))
| some res =>
let async : Async _ := do
let mainPromise := waiter.promise
for selectable in selectables do
selectable.selector.unregisterFn
try
let val ← IO.ofExcept res
let result ← selectable.cont val
mainPromise.resolve (.ok result)
catch e =>
mainPromise.resolve (.error e)
async.toBaseIO
unregisterFn := do
for selectable in selectables do
selectable.selector.unregisterFn
}
end Async
end IO
end Internal
end Std