use core::{
cmp::Ordering,
fmt,
hash::{Hash, Hasher},
marker::PhantomData,
num::NonZeroU64,
};
use crate::{StateMachine, StepInputOf};
#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct PositiveDuration(NonZeroU64);
impl PositiveDuration {
pub const fn from_nanoseconds(nanoseconds: NonZeroU64) -> Self {
Self(nanoseconds)
}
pub const fn nanoseconds(self) -> NonZeroU64 {
self.0
}
}
pub struct ContinuationId<Machine> {
value: NonZeroU64,
machine: PhantomData<fn() -> Machine>,
}
impl<Machine> ContinuationId<Machine> {
pub const fn from_nonzero(value: NonZeroU64) -> Self {
Self {
value,
machine: PhantomData,
}
}
pub const fn value(self) -> NonZeroU64 {
self.value
}
}
impl<Machine> Clone for ContinuationId<Machine> {
fn clone(&self) -> Self {
*self
}
}
impl<Machine> Copy for ContinuationId<Machine> {}
impl<Machine> fmt::Debug for ContinuationId<Machine> {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
self.value.fmt(formatter)
}
}
impl<Machine> PartialEq for ContinuationId<Machine> {
fn eq(&self, other: &Self) -> bool {
self.value == other.value
}
}
impl<Machine> Eq for ContinuationId<Machine> {}
impl<Machine> PartialOrd for ContinuationId<Machine> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl<Machine> Ord for ContinuationId<Machine> {
fn cmp(&self, other: &Self) -> Ordering {
self.value.cmp(&other.value)
}
}
impl<Machine> Hash for ContinuationId<Machine> {
fn hash<H: Hasher>(&self, state: &mut H) {
self.value.hash(state);
}
}
enum NextContinuationId {
Available(NonZeroU64),
Exhausted,
}
pub struct ContinuationIds<Machine> {
next: NextContinuationId,
machine: PhantomData<fn() -> Machine>,
}
impl<Machine> ContinuationIds<Machine> {
pub const fn new() -> Self {
Self {
next: NextContinuationId::Available(NonZeroU64::MIN),
machine: PhantomData,
}
}
pub fn try_issue(
&mut self,
) -> Result<ContinuationId<Machine>, ContinuationIdentifiersExhausted> {
let NextContinuationId::Available(current) = self.next else {
return Err(ContinuationIdentifiersExhausted);
};
self.next = match current.get().checked_add(1).and_then(NonZeroU64::new) {
Some(next) => NextContinuationId::Available(next),
None => NextContinuationId::Exhausted,
};
Ok(ContinuationId::from_nonzero(current))
}
}
impl<Machine> Default for ContinuationIds<Machine> {
fn default() -> Self {
Self::new()
}
}
pub struct ContinuationCoordinator<Machine> {
ids: ContinuationIds<Machine>,
}
impl<Machine> ContinuationCoordinator<Machine> {
pub const fn new() -> Self {
Self {
ids: ContinuationIds::new(),
}
}
}
impl<Machine> Default for ContinuationCoordinator<Machine> {
fn default() -> Self {
Self::new()
}
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct ContinuationIdentifiersExhausted;
#[must_use = "continuation settlements must be stepped back into their owning machine"]
pub enum ContinuationSettlement<Completion, Expiry> {
Completed(Completion),
Expired(Expiry),
}
#[must_use = "continuation inputs must be stepped back into their owning machine"]
pub struct ContinuationInput<Machine, Completion, Expiry> {
id: ContinuationId<Machine>,
settlement: ContinuationSettlement<Completion, Expiry>,
}
impl<Machine, Completion, Expiry> ContinuationInput<Machine, Completion, Expiry> {
pub const fn id(&self) -> ContinuationId<Machine> {
self.id
}
pub const fn settlement(&self) -> &ContinuationSettlement<Completion, Expiry> {
&self.settlement
}
pub fn into_parts(
self,
) -> (
ContinuationId<Machine>,
ContinuationSettlement<Completion, Expiry>,
) {
(self.id, self.settlement)
}
}
#[must_use = "dropping a continuation abandons owed work without settling its machine"]
pub struct Continuation<Machine, Completion, Expiry> {
id: ContinuationId<Machine>,
expiry: Expiry,
completion: PhantomData<fn(Completion)>,
}
impl<Machine, Completion, Expiry> Continuation<Machine, Completion, Expiry> {
pub const fn id(&self) -> ContinuationId<Machine> {
self.id
}
pub fn complete(
self,
completion: Completion,
) -> CompletedContinuation<Machine, Completion, Expiry> {
CompletedContinuation {
input: ContinuationInput {
id: self.id,
settlement: ContinuationSettlement::Completed(completion),
},
cancel_deadline: CancelContinuationDeadline { id: self.id },
}
}
pub fn expire(self) -> ContinuationInput<Machine, Completion, Expiry> {
ContinuationInput {
id: self.id,
settlement: ContinuationSettlement::Expired(self.expiry),
}
}
}
#[must_use = "completion must route both the machine input and deadline cancellation"]
pub struct CompletedContinuation<Machine, Completion, Expiry> {
input: ContinuationInput<Machine, Completion, Expiry>,
cancel_deadline: CancelContinuationDeadline<Machine>,
}
impl<Machine, Completion, Expiry> CompletedContinuation<Machine, Completion, Expiry> {
pub fn into_parts(
self,
) -> (
ContinuationInput<Machine, Completion, Expiry>,
CancelContinuationDeadline<Machine>,
) {
(self.input, self.cancel_deadline)
}
}
#[must_use = "continuation deadlines must be routed before their work is released"]
pub struct ContinuationDeadline<Machine> {
id: ContinuationId<Machine>,
after: PositiveDuration,
}
impl<Machine> ContinuationDeadline<Machine> {
pub const fn id(&self) -> ContinuationId<Machine> {
self.id
}
pub const fn after(&self) -> PositiveDuration {
self.after
}
pub fn into_parts(self) -> (ContinuationId<Machine>, PositiveDuration) {
(self.id, self.after)
}
}
#[must_use = "completed continuation deadlines must be cancelled or explicitly discarded"]
pub struct CancelContinuationDeadline<Machine> {
id: ContinuationId<Machine>,
}
impl<Machine> CancelContinuationDeadline<Machine> {
pub const fn id(&self) -> ContinuationId<Machine> {
self.id
}
pub fn into_id(self) -> ContinuationId<Machine> {
self.id
}
}
#[must_use = "owed work must be delivered or returned to its owner"]
pub struct ContinuationWork<Machine, Work> {
id: ContinuationId<Machine>,
work: Work,
}
impl<Machine, Work> ContinuationWork<Machine, Work> {
pub const fn new(id: ContinuationId<Machine>, work: Work) -> Self {
Self { id, work }
}
pub const fn id(&self) -> ContinuationId<Machine> {
self.id
}
pub const fn work(&self) -> &Work {
&self.work
}
pub fn into_parts(self) -> (ContinuationId<Machine>, Work) {
(self.id, self.work)
}
pub fn map<Mapped>(
self,
map: impl FnOnce(Work) -> Mapped,
) -> ContinuationWork<Machine, Mapped> {
ContinuationWork {
id: self.id,
work: map(self.work),
}
}
}
impl<Requester, Target, Work> StepInputOf<Target> for ContinuationWork<Requester, Work>
where
Target: StateMachine,
Work: StepInputOf<Target>,
{
type Outcome = ContinuationCompletion<Requester, Work::Outcome>;
#[inline]
fn step(self, target: &mut Target) -> Self::Outcome {
let (id, work) = self.into_parts();
ContinuationCompletion::new(id, target.step(work))
}
}
#[must_use = "continuation completions must settle or be classified as stale"]
pub struct ContinuationCompletion<Machine, Completion> {
id: ContinuationId<Machine>,
completion: Completion,
}
impl<Machine, Completion> ContinuationCompletion<Machine, Completion> {
pub const fn new(id: ContinuationId<Machine>, completion: Completion) -> Self {
Self { id, completion }
}
pub const fn id(&self) -> ContinuationId<Machine> {
self.id
}
pub const fn completion(&self) -> &Completion {
&self.completion
}
pub fn into_parts(self) -> (ContinuationId<Machine>, Completion) {
(self.id, self.completion)
}
pub fn map<Mapped>(
self,
map: impl FnOnce(Completion) -> Mapped,
) -> ContinuationCompletion<Machine, Mapped> {
ContinuationCompletion {
id: self.id,
completion: map(self.completion),
}
}
}
#[must_use = "owed work must be parked, scheduled, and delivered"]
pub struct Owed<Machine, Completion, Expiry, Work = ()> {
work: Work,
expiry: Expiry,
timeout_after: PositiveDuration,
machine: PhantomData<fn() -> Machine>,
completion: PhantomData<fn(Completion)>,
}
impl<Machine, Completion, Expiry, Work> Owed<Machine, Completion, Expiry, Work>
where
Machine: StateMachine,
ContinuationInput<Machine, Completion, Expiry>: StepInputOf<Machine>,
{
pub const fn new(work: Work, expiry: Expiry, timeout_after: PositiveDuration) -> Self {
Self {
work,
expiry,
timeout_after,
machine: PhantomData,
completion: PhantomData,
}
}
}
impl<Machine, Completion, Expiry, Work> Owed<Machine, Completion, Expiry, Work> {
pub const fn work(&self) -> &Work {
&self.work
}
pub const fn timeout_after(&self) -> PositiveDuration {
self.timeout_after
}
pub fn into_parts(self) -> (Work, Expiry, PositiveDuration) {
(self.work, self.expiry, self.timeout_after)
}
}
impl<Machine, Completion, Expiry> Owed<Machine, Completion, Expiry>
where
Machine: StateMachine,
ContinuationInput<Machine, Completion, Expiry>: StepInputOf<Machine>,
{
pub const fn wait(expiry: Expiry, timeout_after: PositiveDuration) -> Self {
Self::new((), expiry, timeout_after)
}
}
pub type OwedAdmissionOutcome<Machine, Completion, Expiry, Work> =
Result<ParkedOwed<Machine, Work>, OwedAdmissionFailure<Machine, Completion, Expiry, Work>>;
pub type OwedIssueOutcome<Machine, Completion, Expiry, Work> = Result<
UnparkedOwedParts<Machine, Completion, Expiry, Work>,
OwedIssueFailure<Machine, Completion, Expiry, Work>,
>;
impl<Machine> ContinuationCoordinator<Machine> {
pub fn try_admit<Completion, Expiry, Work>(
&mut self,
owed: Owed<Machine, Completion, Expiry, Work>,
slot: &mut ContinuationSlot<Machine, Completion, Expiry>,
) -> OwedAdmissionOutcome<Machine, Completion, Expiry, Work> {
if let Some(pending_id) = slot.pending_id() {
return Err(OwedAdmissionFailure::Pending { pending_id, owed });
}
let id = match self.ids.try_issue() {
Ok(id) => id,
Err(ContinuationIdentifiersExhausted) => {
return Err(OwedAdmissionFailure::IdentifiersExhausted(owed));
}
};
let (work, expiry, timeout_after) = owed.into_parts();
slot.state = ContinuationSlotState::Pending(Continuation {
id,
expiry,
completion: PhantomData,
});
Ok(ParkedOwed {
deadline: ContinuationDeadline {
id,
after: timeout_after,
},
work: ContinuationWork { id, work },
})
}
pub fn try_issue<Completion, Expiry, Work>(
&mut self,
owed: Owed<Machine, Completion, Expiry, Work>,
) -> OwedIssueOutcome<Machine, Completion, Expiry, Work> {
let id = match self.ids.try_issue() {
Ok(id) => id,
Err(ContinuationIdentifiersExhausted) => return Err(OwedIssueFailure { owed }),
};
let (work, expiry, timeout_after) = owed.into_parts();
Ok(UnparkedOwedParts {
work: ContinuationWork { id, work },
deadline: ContinuationDeadline {
id,
after: timeout_after,
},
continuation: Continuation {
id,
expiry,
completion: PhantomData,
},
})
}
pub fn try_complete<Completion, Expiry>(
&self,
slot: &mut ContinuationSlot<Machine, Completion, Expiry>,
completion: ContinuationCompletion<Machine, Completion>,
) -> Result<
CompletedContinuation<Machine, Completion, Expiry>,
CompleteContinuationFailure<Machine, Completion>,
> {
slot.try_complete(completion)
}
pub fn try_expire<Completion, Expiry>(
&self,
slot: &mut ContinuationSlot<Machine, Completion, Expiry>,
id: ContinuationId<Machine>,
) -> Result<ContinuationInput<Machine, Completion, Expiry>, ContinuationNotPending<Machine>>
{
slot.try_expire(id)
}
}
#[must_use = "the continuation must be parked before its deadline or work is routed"]
pub struct UnparkedOwedParts<Machine, Completion, Expiry, Work> {
work: ContinuationWork<Machine, Work>,
deadline: ContinuationDeadline<Machine>,
continuation: Continuation<Machine, Completion, Expiry>,
}
impl<Machine, Completion, Expiry, Work> UnparkedOwedParts<Machine, Completion, Expiry, Work> {
pub fn into_parts(
self,
) -> (
ContinuationWork<Machine, Work>,
ContinuationDeadline<Machine>,
Continuation<Machine, Completion, Expiry>,
) {
(self.work, self.deadline, self.continuation)
}
}
#[must_use = "the deadline must be routed before the associated work is released"]
pub struct ParkedOwed<Machine, Work> {
deadline: ContinuationDeadline<Machine>,
work: ContinuationWork<Machine, Work>,
}
impl<Machine, Work> ParkedOwed<Machine, Work> {
pub fn into_parts(
self,
) -> (
ContinuationDeadline<Machine>,
ContinuationWork<Machine, Work>,
) {
(self.deadline, self.work)
}
}
#[must_use = "failed admission still owns the rejected owed operation"]
pub enum OwedAdmissionFailure<Machine, Completion, Expiry, Work> {
Pending {
pending_id: ContinuationId<Machine>,
owed: Owed<Machine, Completion, Expiry, Work>,
},
IdentifiersExhausted(Owed<Machine, Completion, Expiry, Work>),
}
impl<Machine, Completion, Expiry, Work> OwedAdmissionFailure<Machine, Completion, Expiry, Work> {
pub const fn pending_id(&self) -> Option<ContinuationId<Machine>> {
match self {
Self::Pending { pending_id, .. } => Some(*pending_id),
Self::IdentifiersExhausted(_) => None,
}
}
pub fn into_owed(self) -> Owed<Machine, Completion, Expiry, Work> {
match self {
Self::Pending { owed, .. } | Self::IdentifiersExhausted(owed) => owed,
}
}
}
#[must_use = "failed issuance still owns the rejected owed operation"]
pub struct OwedIssueFailure<Machine, Completion, Expiry, Work> {
owed: Owed<Machine, Completion, Expiry, Work>,
}
impl<Machine, Completion, Expiry, Work> OwedIssueFailure<Machine, Completion, Expiry, Work> {
pub fn into_owed(self) -> Owed<Machine, Completion, Expiry, Work> {
self.owed
}
}
enum ContinuationSlotState<Machine, Completion, Expiry> {
Vacant,
Pending(Continuation<Machine, Completion, Expiry>),
}
pub struct ContinuationSlot<Machine, Completion, Expiry> {
state: ContinuationSlotState<Machine, Completion, Expiry>,
}
impl<Machine, Completion, Expiry> ContinuationSlot<Machine, Completion, Expiry> {
pub const fn new() -> Self {
Self {
state: ContinuationSlotState::Vacant,
}
}
pub const fn pending_id(&self) -> Option<ContinuationId<Machine>> {
match &self.state {
ContinuationSlotState::Vacant => None,
ContinuationSlotState::Pending(continuation) => Some(continuation.id()),
}
}
pub fn try_park(
&mut self,
continuation: Continuation<Machine, Completion, Expiry>,
) -> Result<(), ContinuationSlotOccupied<Machine, Completion, Expiry>> {
match &self.state {
ContinuationSlotState::Vacant => {
self.state = ContinuationSlotState::Pending(continuation);
Ok(())
}
ContinuationSlotState::Pending(pending) => Err(ContinuationSlotOccupied {
pending_id: pending.id(),
rejected: continuation,
}),
}
}
pub fn try_take(
&mut self,
id: ContinuationId<Machine>,
) -> Result<Continuation<Machine, Completion, Expiry>, ContinuationNotPending<Machine>> {
let state = core::mem::replace(&mut self.state, ContinuationSlotState::Vacant);
match state {
ContinuationSlotState::Vacant => Err(ContinuationNotPending::Vacant { requested: id }),
ContinuationSlotState::Pending(pending) if pending.id() != id => {
let pending_id = pending.id();
self.state = ContinuationSlotState::Pending(pending);
Err(ContinuationNotPending::Different {
requested: id,
pending: pending_id,
})
}
ContinuationSlotState::Pending(pending) => Ok(pending),
}
}
pub fn try_complete(
&mut self,
completion: ContinuationCompletion<Machine, Completion>,
) -> Result<
CompletedContinuation<Machine, Completion, Expiry>,
CompleteContinuationFailure<Machine, Completion>,
> {
let id = completion.id();
let continuation = match self.try_take(id) {
Ok(continuation) => continuation,
Err(cause) => return Err(CompleteContinuationFailure { completion, cause }),
};
let (_, completion) = completion.into_parts();
Ok(continuation.complete(completion))
}
pub fn try_expire(
&mut self,
id: ContinuationId<Machine>,
) -> Result<ContinuationInput<Machine, Completion, Expiry>, ContinuationNotPending<Machine>>
{
self.try_take(id).map(Continuation::expire)
}
}
impl<Machine, Completion, Expiry> Default for ContinuationSlot<Machine, Completion, Expiry> {
fn default() -> Self {
Self::new()
}
}
#[must_use = "a rejected continuation still owns its resumption authority"]
pub struct ContinuationSlotOccupied<Machine, Completion, Expiry> {
pending_id: ContinuationId<Machine>,
rejected: Continuation<Machine, Completion, Expiry>,
}
impl<Machine, Completion, Expiry> ContinuationSlotOccupied<Machine, Completion, Expiry> {
pub const fn pending_id(&self) -> ContinuationId<Machine> {
self.pending_id
}
pub fn into_rejected(self) -> Continuation<Machine, Completion, Expiry> {
self.rejected
}
}
#[must_use = "unknown continuation IDs must be classified as stale or invalid"]
pub enum ContinuationNotPending<Machine> {
Vacant {
requested: ContinuationId<Machine>,
},
Different {
requested: ContinuationId<Machine>,
pending: ContinuationId<Machine>,
},
}
impl<Machine> Clone for ContinuationNotPending<Machine> {
fn clone(&self) -> Self {
*self
}
}
impl<Machine> Copy for ContinuationNotPending<Machine> {}
impl<Machine> fmt::Debug for ContinuationNotPending<Machine> {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::Vacant { requested } => formatter
.debug_struct("Vacant")
.field("requested", requested)
.finish(),
Self::Different { requested, pending } => formatter
.debug_struct("Different")
.field("requested", requested)
.field("pending", pending)
.finish(),
}
}
}
impl<Machine> PartialEq for ContinuationNotPending<Machine> {
fn eq(&self, other: &Self) -> bool {
match (self, other) {
(
Self::Vacant {
requested: left_requested,
},
Self::Vacant {
requested: right_requested,
},
) => left_requested == right_requested,
(
Self::Different {
requested: left_requested,
pending: left_pending,
},
Self::Different {
requested: right_requested,
pending: right_pending,
},
) => left_requested == right_requested && left_pending == right_pending,
(Self::Vacant { .. }, Self::Different { .. })
| (Self::Different { .. }, Self::Vacant { .. }) => false,
}
}
}
impl<Machine> Eq for ContinuationNotPending<Machine> {}
#[must_use = "failed completion retains the outside-world result"]
pub struct CompleteContinuationFailure<Machine, Completion> {
completion: ContinuationCompletion<Machine, Completion>,
cause: ContinuationNotPending<Machine>,
}
impl<Machine, Completion> CompleteContinuationFailure<Machine, Completion> {
pub const fn cause(&self) -> &ContinuationNotPending<Machine> {
&self.cause
}
pub fn into_completion(self) -> ContinuationCompletion<Machine, Completion> {
self.completion
}
pub fn into_parts(
self,
) -> (
ContinuationCompletion<Machine, Completion>,
ContinuationNotPending<Machine>,
) {
(self.completion, self.cause)
}
}
#[cfg(kani)]
mod proofs;
#[cfg(test)]
mod tests;