use std::collections::{HashMap, HashSet};
use std::future::Future;
use std::sync::Arc;
use tokio::sync::Semaphore;
use crate::model::{Status, Task, TaskGraph};
use crate::wave::{BlockOutcome, ConcurrencyTracker, SlotHealth, WaveConfig, on_blocked};
#[derive(Debug, Clone, serde::Serialize)]
pub struct TaskRef {
pub id: String,
pub title: String,
}
#[derive(Debug, serde::Serialize)]
pub struct Chain {
pub crate_name: Option<String>,
pub tasks: Vec<TaskRef>,
}
pub fn independent_chains(graph: &TaskGraph, max_concurrent: usize) -> Vec<Chain> {
let active: Vec<&Task> = graph
.tasks
.iter()
.filter(|t| matches!(t.status, Status::Pending | Status::Running))
.collect();
if active.is_empty() {
return vec![];
}
let active_ids: HashSet<&str> = active.iter().map(|t| t.id.as_str()).collect();
let deps_map: HashMap<&str, Vec<&str>> = active
.iter()
.map(|t| {
let deps: Vec<&str> = t
.depends_on
.iter()
.filter(|d| active_ids.contains(d.as_str()))
.map(|d| d.as_str())
.collect();
(t.id.as_str(), deps)
})
.collect();
let roots: Vec<&str> = active
.iter()
.filter(|t| deps_map[t.id.as_str()].is_empty())
.map(|t| t.id.as_str())
.collect();
let mut chains: Vec<Chain> = Vec::new();
let mut claimed: HashSet<&str> = HashSet::new();
let mut rev: HashMap<&str, Vec<&str>> = HashMap::new();
for (id, deps) in &deps_map {
for dep in deps {
rev.entry(dep).or_default().push(id);
}
}
let task_index: HashMap<&str, &Task> = graph.tasks.iter().map(|t| (t.id.as_str(), t)).collect();
for root in roots {
if claimed.contains(root) {
continue;
}
let mut chain_ids = vec![root];
claimed.insert(root);
loop {
let last = *chain_ids.last().unwrap();
let successors: Vec<&str> = rev
.get(last)
.map(|v| v.iter().copied().filter(|s| !claimed.contains(s)).collect())
.unwrap_or_default();
if successors.len() == 1 {
let next = successors[0];
chain_ids.push(next);
claimed.insert(next);
} else {
break;
}
}
let crate_name = infer_crate(&chain_ids, &task_index);
let tasks = chain_ids
.iter()
.filter_map(|id| task_index.get(id))
.map(|t| TaskRef {
id: t.id.clone(),
title: t.title.clone(),
})
.collect();
chains.push(Chain { crate_name, tasks });
if chains.len() >= max_concurrent {
break;
}
}
chains
}
pub fn critical_path(graph: &TaskGraph) -> Vec<TaskRef> {
let active: Vec<&Task> = graph
.tasks
.iter()
.filter(|t| matches!(t.status, Status::Pending | Status::Running))
.collect();
if active.is_empty() {
return vec![];
}
let active_ids: HashSet<&str> = active.iter().map(|t| t.id.as_str()).collect();
let mut in_degree: HashMap<&str, usize> = active.iter().map(|t| (t.id.as_str(), 0)).collect();
let mut rev: HashMap<&str, Vec<&str>> = HashMap::new();
for t in &active {
for dep in t
.depends_on
.iter()
.filter(|d| active_ids.contains(d.as_str()))
{
*in_degree.entry(t.id.as_str()).or_default() += 1;
rev.entry(dep.as_str()).or_default().push(t.id.as_str());
}
}
let mut depth: HashMap<&str, usize> = active.iter().map(|t| (t.id.as_str(), 1)).collect();
let mut parent: HashMap<&str, Option<&str>> =
active.iter().map(|t| (t.id.as_str(), None)).collect();
let mut queue: std::collections::VecDeque<&str> = active
.iter()
.filter(|t| in_degree[t.id.as_str()] == 0)
.map(|t| t.id.as_str())
.collect();
while let Some(id) = queue.pop_front() {
let d = depth[id];
if let Some(successors) = rev.get(id) {
for &succ in successors {
let new_d = d + 1;
if new_d > depth[succ] {
depth.insert(succ, new_d);
parent.insert(succ, Some(id));
}
let deg = in_degree.get_mut(succ).unwrap();
*deg -= 1;
if *deg == 0 {
queue.push_back(succ);
}
}
}
}
let max_depth = active.iter().map(|t| depth[t.id.as_str()]).max().unwrap();
let tail = active
.iter()
.find(|t| depth[t.id.as_str()] == max_depth)
.map(|t| t.id.as_str())
.unwrap();
let mut path_ids: Vec<&str> = Vec::new();
let mut cur = Some(tail);
while let Some(id) = cur {
path_ids.push(id);
cur = parent[id];
}
path_ids.reverse();
path_ids
.iter()
.filter_map(|id| graph.tasks.iter().find(|t| t.id == *id))
.map(|t| TaskRef {
id: t.id.clone(),
title: t.title.clone(),
})
.collect()
}
#[derive(Debug, PartialEq, Eq)]
pub enum ChainOutcome {
Completed,
Skipped,
Exhausted,
}
pub fn dispatch_with_config<F>(
chains: &[Chain],
config: &WaveConfig,
mut execute: F,
) -> Vec<ChainOutcome>
where
F: FnMut(&Chain) -> Result<(), bool>,
{
let mut tracker = ConcurrencyTracker::new(config.max_concurrency);
let mut outcomes = Vec::with_capacity(chains.len());
for chain in chains {
if !tracker.try_acquire() {
outcomes.push(ChainOutcome::Skipped);
continue;
}
let mut health = SlotHealth::default();
let mut result = execute(chain);
while let Err(true) = result {
match on_blocked(&mut health, config) {
BlockOutcome::Retry { attempt } => {
if config.retry_backoff_ms > 0 {
let delay = config.retry_backoff_ms * 2u64.pow(attempt as u32 - 1);
std::thread::sleep(std::time::Duration::from_millis(delay));
}
result = execute(chain);
}
BlockOutcome::Exhausted => {
result = Err(false);
break;
}
}
}
tracker.release();
outcomes.push(if result.is_ok() {
ChainOutcome::Completed
} else {
ChainOutcome::Exhausted
});
}
outcomes
}
pub async fn async_dispatch_with_config<F, Fut>(
chains: &[Chain],
config: &WaveConfig,
execute: F,
) -> Vec<ChainOutcome>
where
F: Fn(Vec<TaskRef>) -> Fut + Send + Sync + 'static,
Fut: Future<Output = Result<(), bool>> + Send + 'static,
{
if chains.is_empty() {
return vec![];
}
let semaphore = Arc::new(Semaphore::new(config.max_concurrency));
let max_retries = config.max_retries;
let backoff_ms = config.retry_backoff_ms;
let execute = Arc::new(execute);
let mut handles = Vec::with_capacity(chains.len());
for chain in chains {
let sem = semaphore.clone();
let tasks = chain.tasks.clone();
let exec = execute.clone();
let handle = tokio::spawn(async move {
let permit = match sem.acquire().await {
Ok(p) => p,
Err(_) => return ChainOutcome::Skipped,
};
let mut health = SlotHealth::default();
let mut result = exec(tasks.clone()).await;
let wave_cfg = WaveConfig {
max_concurrency: 0,
max_retries,
retry_backoff_ms: backoff_ms,
..Default::default()
};
while let Err(true) = result {
match on_blocked(&mut health, &wave_cfg) {
BlockOutcome::Retry { attempt } => {
if backoff_ms > 0 {
let delay = backoff_ms * 2u64.pow(attempt as u32 - 1);
tokio::time::sleep(std::time::Duration::from_millis(delay)).await;
}
result = exec(tasks.clone()).await;
}
BlockOutcome::Exhausted => {
result = Err(false);
break;
}
}
}
drop(permit);
if result.is_ok() {
ChainOutcome::Completed
} else {
ChainOutcome::Exhausted
}
});
handles.push(handle);
}
let mut outcomes = Vec::with_capacity(handles.len());
for handle in handles {
outcomes.push(handle.await.unwrap_or(ChainOutcome::Exhausted));
}
outcomes
}
pub fn file_overlap_warnings(chains: &[Chain]) -> Vec<(usize, usize, String)> {
let mut warnings = Vec::new();
for (i, a) in chains.iter().enumerate() {
for (j, b) in chains.iter().enumerate().skip(i + 1) {
if let (Some(ca), Some(cb)) = (&a.crate_name, &b.crate_name)
&& ca == cb
{
warnings.push((i, j, ca.clone()));
}
}
}
warnings
}
fn infer_crate(ids: &[&str], task_index: &HashMap<&str, &Task>) -> Option<String> {
let crates: HashSet<Option<&str>> = ids
.iter()
.filter_map(|id| task_index.get(id))
.map(|t| t.crate_name.as_deref())
.collect();
if crates.len() == 1 {
crates.into_iter().next().flatten().map(str::to_string)
} else {
None
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::model::Task;
use crate::wave::WaveConfig;
use std::sync::{Arc, Mutex};
fn make_graph(specs: &[(&str, &str, &[&str], Option<&str>)]) -> TaskGraph {
let mut g = TaskGraph::default();
for (id, title, deps, krate) in specs {
let mut t = Task::new(*id, *title);
t.depends_on = deps.iter().map(|s| s.to_string()).collect();
t.crate_name = krate.map(str::to_string);
g.tasks.push(t);
}
g
}
#[test]
fn single_chain() {
let g = make_graph(&[
("t1", "A", &[], Some("foo")),
("t2", "B", &["t1"], Some("foo")),
]);
let chains = independent_chains(&g, 5);
assert_eq!(chains.len(), 1);
let ids: Vec<&str> = chains[0].tasks.iter().map(|t| t.id.as_str()).collect();
assert_eq!(ids, vec!["t1", "t2"]);
assert_eq!(chains[0].crate_name.as_deref(), Some("foo"));
}
#[test]
fn two_independent_chains() {
let g = make_graph(&[
("a1", "A1", &[], Some("auth")),
("a2", "A2", &["a1"], Some("auth")),
("b1", "B1", &[], Some("cache")),
("b2", "B2", &["b1"], Some("cache")),
]);
let chains = independent_chains(&g, 5);
assert_eq!(chains.len(), 2);
}
#[test]
fn respects_max_concurrent() {
let g = make_graph(&[
("t1", "A", &[], None),
("t2", "B", &[], None),
("t3", "C", &[], None),
("t4", "D", &[], None),
("t5", "E", &[], None),
("t6", "F", &[], None),
]);
let chains = independent_chains(&g, 5);
assert!(chains.len() <= 5);
}
#[test]
fn empty_graph_returns_no_chains() {
let g = TaskGraph::default();
let chains = independent_chains(&g, 5);
assert!(chains.is_empty());
}
#[test]
fn critical_path_linear_chain() {
let g = make_graph(&[
("t1", "A", &[], None),
("t2", "B", &["t1"], None),
("t3", "C", &["t2"], None),
]);
let path = critical_path(&g);
let ids: Vec<&str> = path.iter().map(|t| t.id.as_str()).collect();
assert_eq!(ids, vec!["t1", "t2", "t3"]);
}
#[test]
fn critical_path_diamond_picks_longer_side() {
let g = make_graph(&[
("t1", "A", &[], None),
("t2", "B", &["t1"], None),
("t3", "C", &["t1"], None),
("t4", "D", &["t2", "t3"], None),
]);
let path = critical_path(&g);
assert_eq!(path.len(), 3);
assert_eq!(path[0].id, "t1");
assert_eq!(path.last().unwrap().id, "t4");
}
#[test]
fn critical_path_parallel_equal_length() {
let g = make_graph(&[
("a1", "A1", &[], None),
("a2", "A2", &["a1"], None),
("b1", "B1", &[], None),
("b2", "B2", &["b1"], None),
]);
let path = critical_path(&g);
assert_eq!(path.len(), 2);
assert_eq!(path[0].id, "a1");
}
#[test]
fn critical_path_empty_graph() {
let g = TaskGraph::default();
assert!(critical_path(&g).is_empty());
}
fn make_chains(n: usize) -> Vec<Chain> {
(0..n)
.map(|i| Chain {
crate_name: None,
tasks: vec![TaskRef {
id: format!("t{i}"),
title: format!("Task {i}"),
}],
})
.collect()
}
#[test]
fn dispatch_max_concurrency_2_runs_sequentially() {
let cfg = WaveConfig {
max_concurrency: 2,
max_retries: 0,
..Default::default()
};
let chains = make_chains(4);
let peak = Arc::new(Mutex::new(0usize));
let current = Arc::new(Mutex::new(0usize));
let peak_c = peak.clone();
let current_c = current.clone();
let outcomes = dispatch_with_config(&chains, &cfg, move |_chain| {
let mut c = current_c.lock().unwrap();
*c += 1;
let mut p = peak_c.lock().unwrap();
if *c > *p {
*p = *c;
}
*c -= 1;
Ok(())
});
assert_eq!(
outcomes
.iter()
.filter(|o| **o == ChainOutcome::Completed)
.count(),
4
);
assert!(*peak.lock().unwrap() <= 2);
}
#[test]
fn dispatch_transient_block_recovered_with_retry() {
let cfg = WaveConfig {
max_concurrency: 5,
max_retries: 3,
retry_backoff_ms: 0,
..Default::default()
};
let chains = make_chains(1);
let call_count = Arc::new(Mutex::new(0usize));
let call_count_c = call_count.clone();
let outcomes = dispatch_with_config(&chains, &cfg, move |_chain| {
let mut c = call_count_c.lock().unwrap();
*c += 1;
if *c == 1 {
Err(true) } else {
Ok(()) }
});
assert_eq!(outcomes[0], ChainOutcome::Completed);
assert_eq!(*call_count.lock().unwrap(), 2, "should have retried once");
}
#[test]
fn dispatch_backoff_delays_retry() {
let cfg = WaveConfig {
max_concurrency: 5,
max_retries: 1,
retry_backoff_ms: 50,
..Default::default()
};
let chains = make_chains(1);
let call_count = Arc::new(Mutex::new(0usize));
let cc = call_count.clone();
let start = std::time::Instant::now();
let outcomes = dispatch_with_config(&chains, &cfg, move |_| {
let mut c = cc.lock().unwrap();
*c += 1;
if *c == 1 { Err(true) } else { Ok(()) }
});
let elapsed = start.elapsed();
assert_eq!(outcomes[0], ChainOutcome::Completed);
assert!(
elapsed.as_millis() >= 50,
"expected backoff delay, got {elapsed:?}"
);
}
#[test]
fn dispatch_slot_unavailable_yields_skipped() {
let cfg = WaveConfig {
max_concurrency: 0,
max_retries: 0,
retry_backoff_ms: 0,
..Default::default()
};
let chains = make_chains(3);
let outcomes = dispatch_with_config(&chains, &cfg, |_| Ok(()));
assert!(outcomes.iter().all(|o| *o == ChainOutcome::Skipped));
}
#[test]
fn file_overlap_warnings_detects_shared_crate() {
let chains = vec![
Chain {
crate_name: Some("auth".into()),
tasks: vec![TaskRef {
id: "t1".into(),
title: "A".into(),
}],
},
Chain {
crate_name: Some("auth".into()),
tasks: vec![TaskRef {
id: "t2".into(),
title: "B".into(),
}],
},
Chain {
crate_name: Some("cache".into()),
tasks: vec![TaskRef {
id: "t3".into(),
title: "C".into(),
}],
},
];
let warnings = super::file_overlap_warnings(&chains);
assert_eq!(warnings.len(), 1);
assert_eq!(warnings[0], (0, 1, "auth".to_string()));
}
#[test]
fn file_overlap_warnings_none_when_distinct() {
let chains = vec![
Chain {
crate_name: Some("auth".into()),
tasks: vec![TaskRef {
id: "t1".into(),
title: "A".into(),
}],
},
Chain {
crate_name: Some("cache".into()),
tasks: vec![TaskRef {
id: "t2".into(),
title: "B".into(),
}],
},
];
assert!(super::file_overlap_warnings(&chains).is_empty());
}
#[tokio::test]
async fn async_dispatch_runs_chains_concurrently() {
let cfg = WaveConfig {
max_concurrency: 3,
max_retries: 0,
retry_backoff_ms: 0,
..Default::default()
};
let chains = make_chains(3);
let peak = Arc::new(std::sync::atomic::AtomicUsize::new(0));
let current = Arc::new(std::sync::atomic::AtomicUsize::new(0));
let peak_c = peak.clone();
let current_c = current.clone();
let outcomes = super::async_dispatch_with_config(&chains, &cfg, move |_tasks| {
let p = peak_c.clone();
let c = current_c.clone();
async move {
let prev = c.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
let _ = p.fetch_max(prev + 1, std::sync::atomic::Ordering::SeqCst);
tokio::time::sleep(std::time::Duration::from_millis(50)).await;
c.fetch_sub(1, std::sync::atomic::Ordering::SeqCst);
Ok(())
}
})
.await;
assert_eq!(outcomes.len(), 3);
assert!(outcomes.iter().all(|o| *o == ChainOutcome::Completed));
assert!(
peak.load(std::sync::atomic::Ordering::SeqCst) > 1,
"expected concurrent execution, peak was {}",
peak.load(std::sync::atomic::Ordering::SeqCst)
);
}
#[tokio::test]
async fn async_dispatch_respects_concurrency_limit() {
let cfg = WaveConfig {
max_concurrency: 1,
max_retries: 0,
retry_backoff_ms: 0,
..Default::default()
};
let chains = make_chains(3);
let peak = Arc::new(std::sync::atomic::AtomicUsize::new(0));
let current = Arc::new(std::sync::atomic::AtomicUsize::new(0));
let peak_c = peak.clone();
let current_c = current.clone();
let outcomes = super::async_dispatch_with_config(&chains, &cfg, move |_tasks| {
let p = peak_c.clone();
let c = current_c.clone();
async move {
let prev = c.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
let _ = p.fetch_max(prev + 1, std::sync::atomic::Ordering::SeqCst);
tokio::time::sleep(std::time::Duration::from_millis(10)).await;
c.fetch_sub(1, std::sync::atomic::Ordering::SeqCst);
Ok(())
}
})
.await;
assert!(outcomes.iter().all(|o| *o == ChainOutcome::Completed));
assert_eq!(
peak.load(std::sync::atomic::Ordering::SeqCst),
1,
"concurrency limit of 1 should mean peak=1"
);
}
#[tokio::test]
async fn async_dispatch_retries_transient_failure() {
let cfg = WaveConfig {
max_concurrency: 5,
max_retries: 3,
retry_backoff_ms: 0,
..Default::default()
};
let chains = make_chains(1);
let call_count = Arc::new(std::sync::atomic::AtomicUsize::new(0));
let cc = call_count.clone();
let outcomes = super::async_dispatch_with_config(&chains, &cfg, move |_tasks| {
let c = cc.clone();
async move {
let n = c.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
if n == 0 { Err(true) } else { Ok(()) }
}
})
.await;
assert_eq!(outcomes[0], ChainOutcome::Completed);
assert_eq!(call_count.load(std::sync::atomic::Ordering::SeqCst), 2);
}
#[tokio::test]
async fn async_dispatch_empty_chains() {
let cfg = WaveConfig::default();
let chains: Vec<super::Chain> = vec![];
let outcomes =
super::async_dispatch_with_config(&chains, &cfg, |_tasks| async { Ok(()) }).await;
assert!(outcomes.is_empty());
}
#[test]
fn dispatch_permanent_block_exhausted() {
let cfg = WaveConfig {
max_concurrency: 5,
max_retries: 2,
retry_backoff_ms: 0,
..Default::default()
};
let chains = make_chains(1);
let outcomes = dispatch_with_config(&chains, &cfg, |_chain| Err(true));
assert_eq!(outcomes[0], ChainOutcome::Exhausted);
}
}