use std::cmp::{Ordering, Reverse};
use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};
use std::fmt;
use std::time::Instant;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub(crate) struct WorkId(u64);
impl WorkId {
pub(crate) const fn new(value: u64) -> Self {
Self(value)
}
pub(crate) const fn value(self) -> u64 {
self.0
}
}
pub(crate) struct WorkItem<T> {
id: WorkId,
payload: T,
max_attempts: u32,
capacity_retries: u32,
}
impl<T> WorkItem<T> {
pub(crate) fn new(id: WorkId, payload: T, max_attempts: u32) -> Self {
Self {
id,
payload,
max_attempts,
capacity_retries: 0,
}
}
}
pub(crate) struct WorkLease<T> {
item: WorkItem<T>,
attempt: u32,
}
impl<T> WorkLease<T> {
pub(crate) fn id(&self) -> WorkId {
self.item.id
}
pub(crate) fn payload(&self) -> &T {
&self.item.payload
}
pub(crate) fn attempt(&self) -> u32 {
self.attempt
}
}
#[cfg(test)]
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum WorkState {
Pending,
Delayed,
InFlight,
Completed,
Failed,
Cancelled,
}
pub(crate) enum RetryOutcome<T> {
Scheduled,
Exhausted(T),
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum WorkScheduleError {
DuplicateId(WorkId),
InvalidLease(WorkId),
}
impl fmt::Display for WorkScheduleError {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::DuplicateId(id) => write!(formatter, "duplicate work item {}", id.value()),
Self::InvalidLease(id) => {
write!(formatter, "work item {} has no active lease", id.value())
}
}
}
}
impl std::error::Error for WorkScheduleError {}
struct ReadyWork<T> {
item: WorkItem<T>,
previous_attempts: u32,
}
struct DelayedWork<T> {
item: WorkItem<T>,
previous_attempts: u32,
ready_at: Instant,
sequence: u64,
}
impl<T> PartialEq for DelayedWork<T> {
fn eq(&self, other: &Self) -> bool {
self.ready_at == other.ready_at && self.sequence == other.sequence
}
}
impl<T> Eq for DelayedWork<T> {}
impl<T> PartialOrd for DelayedWork<T> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl<T> Ord for DelayedWork<T> {
fn cmp(&self, other: &Self) -> Ordering {
self.ready_at
.cmp(&other.ready_at)
.then_with(|| self.sequence.cmp(&other.sequence))
}
}
pub(crate) struct WorkScheduler<T> {
ready: VecDeque<ReadyWork<T>>,
delayed: BinaryHeap<Reverse<DelayedWork<T>>>,
in_flight: HashMap<WorkId, u32>,
active_ids: HashSet<WorkId>,
#[cfg(test)]
states: HashMap<WorkId, WorkState>,
#[cfg(test)]
failed_count: usize,
next_sequence: u64,
cancelled: bool,
}
impl<T> Default for WorkScheduler<T> {
fn default() -> Self {
Self {
ready: VecDeque::new(),
delayed: BinaryHeap::new(),
in_flight: HashMap::new(),
active_ids: HashSet::new(),
#[cfg(test)]
states: HashMap::new(),
#[cfg(test)]
failed_count: 0,
next_sequence: 0,
cancelled: false,
}
}
}
impl<T> WorkScheduler<T> {
pub(crate) fn new() -> Self {
Self::default()
}
pub(crate) fn enqueue(&mut self, item: WorkItem<T>) -> Result<(), WorkScheduleError> {
if self.cancelled {
return Err(WorkScheduleError::InvalidLease(item.id));
}
if !self.active_ids.insert(item.id) {
return Err(WorkScheduleError::DuplicateId(item.id));
}
#[cfg(test)]
self.states.insert(item.id, WorkState::Pending);
self.ready.push_back(ReadyWork {
item,
previous_attempts: 0,
});
Ok(())
}
#[cfg(test)]
pub(crate) fn admit(&mut self, max_in_flight: usize, now: Instant) -> Vec<WorkLease<T>> {
if self.cancelled || max_in_flight == 0 {
return Vec::new();
}
let capacity = max_in_flight.saturating_sub(self.in_flight.len());
let mut leases = Vec::with_capacity(capacity.min(self.ready.len()));
for _ in 0..capacity {
let Some(lease) = self.admit_one(max_in_flight, now) else {
break;
};
leases.push(lease);
}
leases
}
pub(crate) fn admit_one(&mut self, max_in_flight: usize, now: Instant) -> Option<WorkLease<T>> {
self.admit_one_where(max_in_flight, now, |_| true)
}
pub(crate) fn admit_one_where(
&mut self,
max_in_flight: usize,
now: Instant,
mut eligible: impl FnMut(&T) -> bool,
) -> Option<WorkLease<T>> {
if self.cancelled || self.in_flight.len() >= max_in_flight {
return None;
}
self.promote_ready(now);
let ready_index = self
.ready
.iter()
.position(|ready| eligible(&ready.item.payload))?;
let ready = self.ready.remove(ready_index)?;
let attempt = ready.previous_attempts.saturating_add(1);
let id = ready.item.id;
self.in_flight.insert(id, attempt);
#[cfg(test)]
self.states.insert(id, WorkState::InFlight);
Some(WorkLease {
item: ready.item,
attempt,
})
}
pub(crate) fn is_scheduled(&self, id: WorkId) -> bool {
self.active_ids.contains(&id)
}
pub(crate) fn complete_pending(&mut self, id: WorkId) -> bool {
if self.ready.iter().any(|ready| ready.item.id == id) {
self.ready.retain(|ready| ready.item.id != id);
} else if self
.delayed
.iter()
.any(|Reverse(delayed)| delayed.item.id == id)
{
let mut retained = BinaryHeap::new();
while let Some(Reverse(delayed)) = self.delayed.pop() {
if delayed.item.id != id {
retained.push(Reverse(delayed));
}
}
self.delayed = retained;
} else {
return false;
}
self.active_ids.remove(&id);
#[cfg(test)]
self.states.insert(id, WorkState::Completed);
true
}
pub(crate) fn discard_pending(&mut self) {
for ready in self.ready.drain(..) {
self.active_ids.remove(&ready.item.id);
#[cfg(test)]
self.states.insert(ready.item.id, WorkState::Cancelled);
}
while let Some(Reverse(delayed)) = self.delayed.pop() {
self.active_ids.remove(&delayed.item.id);
#[cfg(test)]
self.states.insert(delayed.item.id, WorkState::Cancelled);
}
}
pub(crate) fn complete(&mut self, lease: WorkLease<T>) -> Result<(), WorkScheduleError> {
self.remove_active_lease(&lease)?;
self.active_ids.remove(&lease.item.id);
#[cfg(test)]
self.states.insert(lease.item.id, WorkState::Completed);
Ok(())
}
pub(crate) fn reschedule_after_success(
&mut self,
lease: WorkLease<T>,
) -> Result<(), WorkScheduleError> {
self.remove_active_lease(&lease)?;
#[cfg(test)]
self.states.insert(lease.id(), WorkState::Pending);
self.ready.push_back(ReadyWork {
item: lease.item,
previous_attempts: lease.attempt.saturating_sub(1),
});
Ok(())
}
pub(crate) fn retry_without_consuming_attempt(
&mut self,
lease: WorkLease<T>,
) -> Result<(), WorkScheduleError> {
self.remove_active_lease(&lease)?;
#[cfg(test)]
self.states.insert(lease.id(), WorkState::Pending);
self.ready.push_back(ReadyWork {
item: lease.item,
previous_attempts: lease.attempt.saturating_sub(1),
});
Ok(())
}
pub(crate) fn retry_capacity_limited_at(
&mut self,
mut lease: WorkLease<T>,
ready_at: Instant,
max_capacity_retries: u32,
) -> Result<RetryOutcome<T>, WorkScheduleError> {
self.remove_active_lease(&lease)?;
if max_capacity_retries != 0 && lease.item.capacity_retries >= max_capacity_retries {
self.active_ids.remove(&lease.item.id);
#[cfg(test)]
{
self.states.insert(lease.item.id, WorkState::Failed);
self.failed_count += 1;
}
return Ok(RetryOutcome::Exhausted(lease.item.payload));
}
lease.item.capacity_retries = lease.item.capacity_retries.saturating_add(1);
let sequence = self.next_sequence;
self.next_sequence = self.next_sequence.wrapping_add(1);
#[cfg(test)]
self.states.insert(lease.id(), WorkState::Delayed);
self.delayed.push(Reverse(DelayedWork {
item: lease.item,
previous_attempts: lease.attempt.saturating_sub(1),
ready_at,
sequence,
}));
Ok(RetryOutcome::Scheduled)
}
pub(crate) fn retry_with_fresh_attempt_budget(
&mut self,
lease: WorkLease<T>,
) -> Result<(), WorkScheduleError> {
self.remove_active_lease(&lease)?;
#[cfg(test)]
self.states.insert(lease.id(), WorkState::Pending);
self.ready.push_back(ReadyWork {
item: lease.item,
previous_attempts: 0,
});
Ok(())
}
pub(crate) fn fail(
&mut self,
lease: WorkLease<T>,
retry_at: Option<Instant>,
) -> Result<RetryOutcome<T>, WorkScheduleError> {
self.remove_active_lease(&lease)?;
let id = lease.id();
let retry_allowed = lease.item.max_attempts == 0 || lease.attempt < lease.item.max_attempts;
if let Some(ready_at) = retry_at.filter(|_| retry_allowed && !self.cancelled) {
let sequence = self.next_sequence;
self.next_sequence = self.next_sequence.wrapping_add(1);
self.delayed.push(Reverse(DelayedWork {
item: lease.item,
previous_attempts: lease.attempt,
ready_at,
sequence,
}));
#[cfg(test)]
self.states.insert(id, WorkState::Delayed);
Ok(RetryOutcome::Scheduled)
} else {
self.active_ids.remove(&id);
#[cfg(test)]
self.states.insert(id, WorkState::Failed);
#[cfg(test)]
{
self.failed_count += 1;
}
Ok(RetryOutcome::Exhausted(lease.item.payload))
}
}
pub(crate) fn requeue_unstarted(
&mut self,
lease: WorkLease<T>,
) -> Result<(), WorkScheduleError> {
self.remove_active_lease(&lease)?;
#[cfg(test)]
self.states.insert(lease.id(), WorkState::Pending);
self.ready.push_front(ReadyWork {
item: lease.item,
previous_attempts: lease.attempt.saturating_sub(1),
});
Ok(())
}
pub(crate) fn next_retry_deadline(&self) -> Option<Instant> {
self.delayed.peek().map(|entry| entry.0.ready_at)
}
#[cfg(test)]
pub(crate) fn state(&self, id: WorkId) -> Option<WorkState> {
self.states.get(&id).copied()
}
pub(crate) fn in_flight_count(&self) -> usize {
self.in_flight.len()
}
#[cfg(test)]
pub(crate) fn failed_count(&self) -> usize {
self.failed_count
}
#[cfg(test)]
pub(crate) fn is_finished(&self) -> bool {
self.active_ids.is_empty()
}
pub(crate) fn cancel(&mut self) {
self.cancelled = true;
self.ready.clear();
self.delayed.clear();
self.in_flight.clear();
self.active_ids.clear();
#[cfg(test)]
for state in self.states.values_mut() {
if !matches!(state, WorkState::Completed | WorkState::Failed) {
*state = WorkState::Cancelled;
}
}
}
fn remove_active_lease(&mut self, lease: &WorkLease<T>) -> Result<(), WorkScheduleError> {
match self.in_flight.remove(&lease.item.id) {
Some(attempt) if attempt == lease.attempt => Ok(()),
Some(attempt) => {
self.in_flight.insert(lease.item.id, attempt);
Err(WorkScheduleError::InvalidLease(lease.item.id))
}
None => Err(WorkScheduleError::InvalidLease(lease.item.id)),
}
}
fn promote_ready(&mut self, now: Instant) {
while self
.delayed
.peek()
.is_some_and(|entry| entry.0.ready_at <= now)
{
let Reverse(delayed) = self.delayed.pop().expect("peeked delayed item");
#[cfg(test)]
self.states.insert(delayed.item.id, WorkState::Pending);
self.ready.push_back(ReadyWork {
item: delayed.item,
previous_attempts: delayed.previous_attempts,
});
}
}
}
#[cfg(test)]
mod tests;