use core::cell::Cell;
use core::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use std::sync::{Arc, OnceLock};
use std::time::Duration;
use crate::foundation::Variant;
use crate::sched::arena::join;
use crate::sched::par_iter::collect_indexed;
use crate::sched::plan::JobPlan;
#[derive(Debug, Clone)]
pub struct CancelToken {
flag: Arc<AtomicBool>,
}
impl CancelToken {
#[must_use]
pub fn new() -> Self {
Self { flag: Arc::new(AtomicBool::new(false)) }
}
#[inline]
pub fn is_canceled(&self) -> bool {
self.flag.load(Ordering::Acquire)
}
#[inline]
pub fn cancel(&self) {
self.flag.store(true, Ordering::Release);
}
}
impl Default for CancelToken {
fn default() -> Self {
Self::new()
}
}
pub fn race_variants<R, Ff, Fa, Fc>(
plan: &JobPlan,
fast: Ff,
faithful: Fa,
correct: Fc,
) -> (R, Variant)
where
R: Send + Sync + 'static,
Ff: FnOnce(&CancelToken) -> Option<R> + Send,
Fa: FnOnce(&CancelToken) -> Option<R> + Send,
Fc: FnOnce(&CancelToken) -> R + Send,
{
let cancel = Arc::new(AtomicBool::new(false));
let winner: Arc<OnceLock<(R, Variant)>> = Arc::new(OnceLock::new());
let token_f = CancelToken { flag: Arc::clone(&cancel) };
let token_a = CancelToken { flag: Arc::clone(&cancel) };
let token_c = CancelToken { flag: Arc::clone(&cancel) };
let cancel_f = Arc::clone(&cancel);
let cancel_a = Arc::clone(&cancel);
let cancel_c = Arc::clone(&cancel);
let winner_f = Arc::clone(&winner);
let winner_a = Arc::clone(&winner);
let winner_c = Arc::clone(&winner);
let arms = plan.without_worker_cap();
join(
&arms,
move || {
join(
&arms,
move || {
if let Some(r) = fast(&token_f) {
let _ = winner_f.set((r, Variant::Fast));
cancel_f.store(true, Ordering::Release);
}
},
move || {
if let Some(r) = faithful(&token_a) {
let _ = winner_a.set((r, Variant::Faithful));
cancel_a.store(true, Ordering::Release);
}
},
);
},
move || {
let r = correct(&token_c);
let _ = winner_c.set((r, Variant::Correct));
cancel_c.store(true, Ordering::Release);
},
);
drop(cancel);
Arc::try_unwrap(winner)
.ok()
.expect("winner Arc still has outstanding clones")
.into_inner()
.expect("at least Correct must have completed")
}
#[track_caller]
pub fn explore_select<R, F, B>(
plan: &JobPlan,
n: usize,
explore: F,
better: B,
) -> Option<(usize, R)>
where
R: Send,
F: Fn(usize) -> R + Sync,
B: Fn(&R, &R) -> bool,
{
if n == 0 {
return None;
}
let mut results = collect_indexed(plan, n, 1, explore);
let mut best = 0usize;
for i in 1..results.len() {
if better(&results[i], &results[best]) {
best = i;
}
}
let winner = results.swap_remove(best);
Some((best, winner))
}
#[track_caller]
pub fn race_any<P, F>(plan: &JobPlan, n: usize, attempt: F) -> Option<(usize, P)>
where
P: Send + Sync + 'static,
F: Fn(usize, &CancelToken) -> P + Sync,
{
if n == 0 {
return None;
}
let cancel = Arc::new(AtomicBool::new(false));
let winner: Arc<OnceLock<(usize, P)>> = Arc::new(OnceLock::new());
let cancel_inner = Arc::clone(&cancel);
let winner_inner = Arc::clone(&winner);
collect_indexed(plan, n, 1, move |i| {
let token = CancelToken { flag: Arc::clone(&cancel_inner) };
let r = attempt(i, &token);
if winner_inner.set((i, r)).is_ok() {
cancel_inner.store(true, Ordering::Release);
}
});
drop(cancel);
Arc::try_unwrap(winner)
.ok()
.expect("winner Arc still has outstanding clones")
.into_inner()
}
#[track_caller]
pub fn race_quorum<P, F>(plan: &JobPlan, n: usize, k: usize, attempt: F) -> Vec<(usize, P)>
where
P: Send + 'static,
F: Fn(usize, &CancelToken) -> P + Sync,
{
let k = k.min(n);
if k == 0 {
return Vec::new();
}
let cancel = Arc::new(AtomicBool::new(false));
let claimed = Arc::new(AtomicUsize::new(0));
let cancel_inner = Arc::clone(&cancel);
let claimed_inner = Arc::clone(&claimed);
let mut finished: Vec<(usize, usize, P)> = collect_indexed(plan, n, 1, move |i| {
let token = CancelToken { flag: Arc::clone(&cancel_inner) };
let r = attempt(i, &token);
let ticket = claimed_inner.fetch_add(1, Ordering::AcqRel);
if ticket + 1 == k {
cancel_inner.store(true, Ordering::Release);
}
(ticket, i, r)
});
drop(cancel);
finished.sort_by_key(|&(ticket, _, _)| ticket);
finished.truncate(k);
finished.into_iter().map(|(_, i, r)| (i, r)).collect()
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Settled<P, R> {
Proved(P),
Refuted(R),
Unsettled,
}
#[track_caller]
pub fn race_refute<P, R, FP, FR>(plan: &JobPlan, prove: FP, refute: FR) -> Settled<P, R>
where
P: Send + Sync + 'static,
R: Send + Sync + 'static,
FP: FnOnce(&CancelToken) -> Option<P> + Send,
FR: FnOnce(&CancelToken) -> Option<R> + Send,
{
let cancel = Arc::new(AtomicBool::new(false));
let verdict: Arc<OnceLock<Settled<P, R>>> = Arc::new(OnceLock::new());
let token_p = CancelToken { flag: Arc::clone(&cancel) };
let token_r = CancelToken { flag: Arc::clone(&cancel) };
let cancel_p = Arc::clone(&cancel);
let cancel_r = Arc::clone(&cancel);
let verdict_p = Arc::clone(&verdict);
let verdict_r = Arc::clone(&verdict);
join(
&plan.without_worker_cap(),
move || {
if let Some(p) = prove(&token_p)
&& verdict_p.set(Settled::Proved(p)).is_ok()
{
cancel_p.store(true, Ordering::Release);
}
},
move || {
if let Some(r) = refute(&token_r)
&& verdict_r.set(Settled::Refuted(r)).is_ok()
{
cancel_r.store(true, Ordering::Release);
}
},
);
drop(cancel);
Arc::try_unwrap(verdict)
.ok()
.expect("verdict Arc still has outstanding clones")
.into_inner()
.unwrap_or(Settled::Unsettled)
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Agreement<R> {
Consensus {
value: R,
agree: usize,
total: usize,
},
Split {
plurality: usize,
total: usize,
},
}
#[track_caller]
pub fn race_agree<R, F>(plan: &JobPlan, n: usize, threshold: usize, explore: F) -> Agreement<R>
where
R: PartialEq + Send,
F: Fn(usize) -> R + Sync,
{
if n == 0 {
return Agreement::Split { plurality: 0, total: 0 };
}
let mut results = collect_indexed(plan, n, 1, explore);
let total = results.len();
let mut best_idx = 0usize;
let mut best_count = 0usize;
for i in 0..results.len() {
let count = results.iter().filter(|r| **r == results[i]).count();
if count > best_count {
best_count = count;
best_idx = i;
}
}
if best_count >= threshold.max(1) {
let value = results.swap_remove(best_idx);
Agreement::Consensus { value, agree: best_count, total }
} else {
Agreement::Split { plurality: best_count, total }
}
}
pub struct Anytime<R> {
expired: Arc<AtomicBool>,
best: Cell<Option<(f64, R)>>,
}
impl<R> Anytime<R> {
#[inline]
pub fn is_expired(&self) -> bool {
self.expired.load(Ordering::Acquire)
}
pub fn submit(&self, score: f64, value: R) {
let kept = match self.best.take() {
Some((s, v)) if s >= score => Some((s, v)),
_ => Some((score, value)),
};
self.best.set(kept);
}
}
#[track_caller]
pub fn race_deadline<R, F>(plan: &JobPlan, budget: Duration, n: usize, explore: F) -> Option<(f64, R)>
where
R: Send,
F: Fn(usize, &Anytime<R>) + Sync + Send,
{
if n == 0 {
return None;
}
let expired = Arc::new(AtomicBool::new(false));
let timer_flag = Arc::clone(&expired);
let explorer_flag = Arc::clone(&expired);
let (_timer, published) = join(
&plan.without_worker_cap(),
move || {
std::thread::sleep(budget);
timer_flag.store(true, Ordering::Release);
},
move || {
collect_indexed(plan, n, 1, |i| {
let ctx = Anytime {
expired: Arc::clone(&explorer_flag),
best: Cell::new(None),
};
explore(i, &ctx);
ctx.best.into_inner()
})
},
);
let mut best: Option<(f64, R)> = None;
for candidate in published.into_iter().flatten() {
let improved = best.as_ref().is_none_or(|(s, _)| candidate.0 > *s);
if improved {
best = Some(candidate);
}
}
best
}
#[track_caller]
pub fn race_tournament<R, F, B>(
plan: &JobPlan,
n: usize,
eta: usize,
base_budget: u32,
run: F,
better: B,
) -> Option<(usize, R)>
where
R: Send,
F: Fn(usize, u32) -> R + Sync,
B: Fn(&R, &R) -> bool,
{
if n == 0 {
return None;
}
let eta = eta.max(2);
let mut survivors: Vec<usize> = (0..n).collect();
let mut budget = base_budget.max(1);
loop {
let ids = survivors.clone();
let mut round: Vec<(usize, R)> =
collect_indexed(plan, ids.len(), 1, |k| (ids[k], run(ids[k], budget)));
if round.len() == 1 {
return round.pop();
}
let mut order: Vec<usize> = (0..round.len()).collect();
order.sort_by(|&a, &b| {
if better(&round[a].1, &round[b].1) {
std::cmp::Ordering::Less
} else if better(&round[b].1, &round[a].1) {
std::cmp::Ordering::Greater
} else {
std::cmp::Ordering::Equal
}
});
let keep = round.len().div_ceil(eta).max(1);
survivors = order.iter().take(keep).map(|&idx| round[idx].0).collect();
budget = budget.saturating_mul(eta as u32);
}
}
#[derive(Debug, Clone, Copy)]
pub struct StatOpts {
pub value_range: f64,
pub delta: f64,
pub batch: usize,
pub max_samples: usize,
pub maximize: bool,
}
#[derive(Debug, Clone, Copy)]
pub struct StatOutcome {
pub winner: usize,
pub mean: f64,
pub samples_each: usize,
pub survivors: usize,
}
#[track_caller]
pub fn race_statistical<F>(plan: &JobPlan, n: usize, opts: StatOpts, sample: F) -> Option<StatOutcome>
where
F: Fn(usize) -> f64 + Sync,
{
if n == 0 {
return None;
}
let mut survivors: Vec<usize> = (0..n).collect();
let mut sums = vec![0.0f64; n];
let mut counts = vec![0usize; n];
let batch = opts.batch.max(1);
loop {
let ids = survivors.clone();
let partials: Vec<(usize, f64)> = collect_indexed(plan, ids.len(), 1, |k| {
let id = ids[k];
let mut s = 0.0;
for _ in 0..batch {
s += sample(id);
}
(id, s)
});
for (id, s) in partials {
sums[id] += s;
counts[id] += batch;
}
let n_each = counts[survivors[0]];
let radius = opts.value_range * ((2.0 / opts.delta).ln() / (2.0 * n_each as f64)).sqrt();
let mean = |id: usize| sums[id] / counts[id] as f64;
let leader = *survivors
.iter()
.max_by(|&&a, &&b| {
let ord = mean(a).partial_cmp(&mean(b)).unwrap_or(std::cmp::Ordering::Equal);
if opts.maximize { ord } else { ord.reverse() }
})
.expect("survivors non-empty");
let leader_bound = if opts.maximize { mean(leader) - radius } else { mean(leader) + radius };
survivors.retain(|&id| {
if id == leader {
return true;
}
let dominated = if opts.maximize {
mean(id) + radius < leader_bound
} else {
mean(id) - radius > leader_bound
};
!dominated
});
if survivors.len() == 1 || n_each >= opts.max_samples {
let winner = if survivors.len() == 1 { survivors[0] } else { leader };
return Some(StatOutcome {
winner,
mean: mean(winner),
samples_each: n_each,
survivors: survivors.len(),
});
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::sync::atomic::AtomicU32;
use std::time::Duration;
use crate::sched::plan::JobPlan;
#[test]
fn race_returns_correct_when_all_succeed() {
let plan = JobPlan::new(6, 1024);
let (r, v) = race_variants::<u32, _, _, _>(
&plan,
|_token| Some(42u32),
|_token| Some(42u32),
|_token| 42u32,
);
assert_eq!(r, 42);
assert!(matches!(v, Variant::Fast | Variant::Faithful | Variant::Correct));
}
#[test]
fn race_falls_back_to_correct_when_fast_and_faithful_return_none() {
let plan = JobPlan::new(6, 1024);
let (r, v) = race_variants::<u32, _, _, _>(
&plan,
|_token| None,
|_token| None,
|_token| 7u32,
);
assert_eq!(r, 7);
assert_eq!(v, Variant::Correct);
}
#[test]
fn race_returns_faithful_when_fast_returns_none() {
let plan = JobPlan::new(6, 1024);
let (r, _v) = race_variants::<u32, _, _, _>(
&plan,
|_token| None,
|_token| Some(11u32),
|_token| {
std::thread::sleep(Duration::from_millis(20));
99u32
},
);
assert!(r == 11 || r == 99);
}
#[test]
fn cancel_token_observed_by_losers() {
let plan = JobPlan::new(6, 1024);
let saw_cancel = Arc::new(AtomicU32::new(0));
let saw_cancel_c = Arc::clone(&saw_cancel);
let (_r, _v) = race_variants::<u32, _, _, _>(
&plan,
|_token| Some(1u32), |_token| None,
move |token| {
for _ in 0..1000 {
if token.is_canceled() {
saw_cancel_c.fetch_add(1, Ordering::Relaxed);
return 99u32;
}
std::thread::sleep(Duration::from_micros(50));
}
99u32
},
);
let _ = saw_cancel.load(Ordering::Relaxed);
}
#[test]
fn explore_select_argmin_keeps_fewest() {
let plan = JobPlan::new(6, 10);
let counts = [7u32, 3, 9, 1, 8, 4, 6, 2, 5, 10];
let (idx, best) = explore_select(
&plan,
counts.len(),
|i| counts[i],
|a, b| a < b, )
.expect("n > 0");
assert_eq!(best, 1, "min action count is 1");
assert_eq!(idx, 3, "at index 3");
}
#[test]
fn explore_select_argmax_via_comparator() {
let plan = JobPlan::new(6, 10);
let counts = [7u32, 3, 9, 1, 8, 4, 6, 2, 5, 10];
let (idx, best) =
explore_select(&plan, counts.len(), |i| counts[i], |a, b| a > b).expect("n > 0");
assert_eq!(best, 10);
assert_eq!(idx, 9);
}
#[test]
fn explore_select_runs_every_explorer_to_completion() {
let plan = JobPlan::new(6, 16);
let ran = Arc::new(AtomicU32::new(0));
let ran_c = Arc::clone(&ran);
let n = 16usize;
let (_idx, best) = explore_select(
&plan,
n,
move |i| {
ran_c.fetch_add(1, Ordering::Relaxed);
if i == 0 {
std::thread::sleep(Duration::from_millis(15));
0u32
} else {
i as u32
}
},
|a, b| a < b,
)
.expect("n > 0");
assert_eq!(ran.load(Ordering::Relaxed), n as u32, "all explorers ran");
assert_eq!(best, 0, "the slow-but-best explorer was kept");
}
#[test]
fn explore_select_empty_is_none() {
let plan = JobPlan::new(6, 0);
let out = explore_select(&plan, 0, |_i| 0u32, |a, b| a < b);
assert!(out.is_none());
}
#[test]
fn explore_select_ties_keep_earliest_index() {
let plan = JobPlan::new(6, 5);
let (idx, _best) =
explore_select(&plan, 5, |_i| 42u32, |a, b| a < b).expect("n > 0");
assert_eq!(idx, 0);
}
#[test]
fn race_any_returns_a_consistent_winner() {
let plan = JobPlan::new(6, 8);
let out = race_any(&plan, 8, |i, _t| i * 10);
let (idx, payload) = out.expect("n > 0");
assert!(idx < 8);
assert_eq!(payload, idx * 10, "payload must match the winning index");
}
#[test]
fn race_any_fast_attempt_wins_and_losers_see_cancel() {
let plan = JobPlan::new(6, 8);
let saw_cancel = Arc::new(AtomicU32::new(0));
let saw = Arc::clone(&saw_cancel);
let (idx, _p) = race_any(&plan, 8, move |i, token| {
if i == 0 {
return 0u32;
}
for _ in 0..200 {
if token.is_canceled() {
saw.fetch_add(1, Ordering::Relaxed);
break;
}
std::thread::sleep(Duration::from_millis(1));
}
i as u32
})
.expect("n > 0");
assert_eq!(idx, 0, "the instant attempt wins the hedge");
assert!(saw_cancel.load(Ordering::Relaxed) >= 1, "losers observed cancel");
}
#[test]
fn race_quorum_returns_exactly_k_distinct() {
let plan = JobPlan::new(6, 8);
let winners = race_quorum(&plan, 8, 3, |i, _t| i);
assert_eq!(winners.len(), 3, "exactly k winners");
let mut idxs: Vec<usize> = winners.iter().map(|(i, _)| *i).collect();
idxs.sort_unstable();
idxs.dedup();
assert_eq!(idxs.len(), 3, "distinct indices");
for (i, p) in winners {
assert_eq!(i, p, "payload matches index");
}
}
#[test]
fn race_quorum_k_clamped_to_n() {
let plan = JobPlan::new(6, 3);
let winners = race_quorum(&plan, 3, 99, |i, _t| i);
assert_eq!(winners.len(), 3, "k clamps to n");
}
#[test]
fn race_refute_prover_and_refuter_and_unsettled() {
let plan = JobPlan::new(6, 1);
let v = race_refute::<u32, u32, _, _>(&plan, |_t| Some(1u32), |_t| None);
assert_eq!(v, Settled::Proved(1));
let v = race_refute::<u32, u32, _, _>(&plan, |_t| None, |_t| Some(2u32));
assert_eq!(v, Settled::Refuted(2));
let v = race_refute::<u32, u32, _, _>(&plan, |_t| None, |_t| None);
assert_eq!(v, Settled::Unsettled);
}
#[test]
fn race_refute_first_to_settle_wins() {
let plan = JobPlan::new(6, 1);
let v = race_refute::<u32, u32, _, _>(
&plan,
|_t| Some(7u32),
|_t| {
std::thread::sleep(Duration::from_millis(30));
Some(9u32)
},
);
assert_eq!(v, Settled::Proved(7));
}
#[test]
fn race_agree_reaches_and_misses_consensus() {
let plan = JobPlan::new(6, 5);
let vals = [42u32, 42, 7, 42, 42];
let out = race_agree(&plan, 5, 3, |i| vals[i]);
assert_eq!(out, Agreement::Consensus { value: 42, agree: 4, total: 5 });
let out = race_agree(&plan, 5, 5, |i| vals[i]);
assert_eq!(out, Agreement::Split { plurality: 4, total: 5 });
}
#[test]
fn race_agree_flags_a_lone_divergence() {
let plan = JobPlan::new(6, 3);
let vals = [100u32, 100, 999];
let out = race_agree(&plan, 3, 3, |i| vals[i]);
assert_eq!(out, Agreement::Split { plurality: 2, total: 3 },
"unanimity required but path 2 diverged");
}
#[test]
fn race_deadline_keeps_the_best_published() {
let plan = JobPlan::new(6, 8);
let out = race_deadline(&plan, Duration::from_millis(60), 8, |i, ctx| {
ctx.submit(i as f64, i as u32);
while !ctx.is_expired() {
std::hint::spin_loop();
}
});
let (score, value) = out.expect("someone published");
assert_eq!(score, 7.0, "highest published score kept");
assert_eq!(value, 7u32);
}
#[test]
fn a_worker_cap_of_one_keeps_race_deadline_s_clock_beside_its_explorers() {
let plan = JobPlan::new(6, 8).with_workers(1);
let out = race_deadline(&plan, Duration::from_millis(60), 2, |i, ctx| {
if !ctx.is_expired() {
ctx.submit(i as f64 + 1.0, i as u32);
}
while !ctx.is_expired() {
std::hint::spin_loop();
}
});
let (score, value) = out.expect("the first explorer ran before the clock expired");
assert_eq!(
(score, value),
(1.0, 0u32),
"the explorers ran in turn, the first alone inside the budget"
);
}
#[test]
fn race_tournament_selects_the_best_candidate() {
let plan = JobPlan::new(6, 8);
let (id, score) =
race_tournament(&plan, 8, 2, 1, |id, _budget| id as u32, |a, b| a > b).expect("n > 0");
assert_eq!(id, 7);
assert_eq!(score, 7);
}
#[test]
fn race_statistical_eliminates_dominated_candidates() {
let plan = JobPlan::new(6, 5);
let opts = StatOpts {
value_range: 40.0,
delta: 0.1,
batch: 32,
max_samples: 4096,
maximize: true,
};
let out = race_statistical(&plan, 5, opts, |id| (id as f64) * 10.0).expect("n > 0");
assert_eq!(out.winner, 4, "highest mean survives");
assert_eq!(out.survivors, 1, "the others were eliminated by confidence");
assert!(out.samples_each < opts.max_samples, "stopped before the sample cap");
}
#[test]
fn cancel_token_built_by_the_caller_is_shared_by_its_clones() {
let token = CancelToken::new();
assert!(!token.is_canceled(), "fresh token is not canceled");
let peer = token.clone();
let plan = JobPlan::new(6, 2);
let saw_cancel = Arc::new(AtomicU32::new(0));
let saw = Arc::clone(&saw_cancel);
join(
&plan,
move || {
token.cancel();
token.cancel();
},
move || {
for _ in 0..2000 {
if peer.is_canceled() {
saw.fetch_add(1, Ordering::Relaxed);
return;
}
std::thread::sleep(Duration::from_micros(50));
}
},
);
assert_eq!(saw_cancel.load(Ordering::Relaxed), 1, "the peer observed the caller's cancel");
assert!(!CancelToken::default().is_canceled(), "default is a fresh token");
}
#[test]
fn cancel_token_returns_false_initially() {
let plan = JobPlan::new(6, 1024);
let observed_false = Arc::new(AtomicU32::new(0));
let observed_f = Arc::clone(&observed_false);
let (_r, _v) = race_variants::<u32, _, _, _>(
&plan,
move |token| {
if !token.is_canceled() {
observed_f.fetch_add(1, Ordering::Relaxed);
}
Some(1u32)
},
|_token| None,
|_token| {
std::thread::sleep(Duration::from_millis(50));
2u32
},
);
assert!(observed_false.load(Ordering::Relaxed) >= 1,
"Fast must observe cancel=false at entry when Correct \
takes 50ms");
}
}