use core::cmp::Reverse;
use core::num::{NonZeroU32, NonZeroU64};
use std::collections::BinaryHeap;
use crate::analysis::{analyze, Analysis};
use crate::graph::{BuildGraph, EdgeKind, UnitId};
use crate::millis::Millis;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Policy {
CargoLike,
LongestPath,
}
impl Default for Policy {
fn default() -> Self {
Self::CargoLike
}
}
#[derive(Clone, Debug)]
pub struct Schedule {
start: Vec<Millis>,
finish: Vec<Millis>,
makespan: Millis,
policy: Policy,
executors: NonZeroU32,
}
impl Schedule {
#[must_use]
pub fn makespan(&self) -> Millis {
self.makespan
}
#[must_use]
pub fn start(&self, id: UnitId) -> Option<Millis> {
self.start.get(id.index()).copied()
}
#[must_use]
pub fn finish(&self, id: UnitId) -> Option<Millis> {
self.finish.get(id.index()).copied()
}
#[must_use]
pub fn policy(&self) -> Policy {
self.policy
}
#[must_use]
pub fn executors(&self) -> NonZeroU32 {
self.executors
}
}
#[must_use]
pub fn simulate(graph: &BuildGraph, executors: NonZeroU32, policy: Policy) -> Schedule {
let count = graph.len();
let priority = priorities(graph, policy);
let mut state = Readiness::new(graph, count);
let mut start = vec![Millis::ZERO; count];
let mut finish = vec![Millis::ZERO; count];
let mut waiting: Waiting = BinaryHeap::new();
let mut ready: BinaryHeap<(u64, Reverse<UnitId>)> = BinaryHeap::new();
let mut running: BinaryHeap<Reverse<(Millis, UnitId)>> = BinaryHeap::new();
for (id, _) in graph.units() {
if graph.dependencies(id).unwrap_or(&[]).is_empty() {
waiting.push(Reverse((Millis::ZERO, id)));
}
}
let mut now = Millis::ZERO;
let mut free = u64::from(executors.get());
let mut makespan = Millis::ZERO;
loop {
let mut progress = false;
while let Some(&Reverse((at, id))) = running.peek() {
if at > now {
break;
}
running.pop();
free = free.saturating_add(1);
progress = true;
state.on_finish(graph, id, at, &finish, &mut waiting);
}
while let Some(&Reverse((at, id))) = waiting.peek() {
if at > now {
break;
}
waiting.pop();
let priority = priority.get(id.index()).copied().unwrap_or(0);
ready.push((priority, Reverse(id)));
progress = true;
}
while free > 0 {
let Some((_, Reverse(id))) = ready.pop() else {
break;
};
let Some(unit) = graph.unit(id) else {
continue;
};
let ends = now.saturating_add(unit.total);
if let Some(slot) = start.get_mut(id.index()) {
*slot = now;
}
if let Some(slot) = finish.get_mut(id.index()) {
*slot = ends;
}
running.push(Reverse((ends, id)));
free = free.saturating_sub(1);
makespan = makespan.max(ends);
progress = true;
state.on_start(graph, id, now, &mut waiting);
}
if progress {
continue;
}
let next_finish = running.peek().map(|&Reverse((at, _))| at);
let next_release = waiting.peek().map(|&Reverse((at, _))| at);
let next = match (next_finish, next_release) {
(Some(a), Some(b)) => Some(a.min(b)),
(Some(a), None) | (None, Some(a)) => Some(a),
(None, None) => None,
};
match next {
Some(at) if at > now => now = at,
_ => break,
}
}
Schedule {
start,
finish,
makespan,
policy,
executors,
}
}
#[must_use]
pub fn area_bound(graph: &BuildGraph, executors: NonZeroU32) -> Millis {
graph.total_work().div_ceil_by(NonZeroU64::from(executors))
}
#[must_use]
pub fn lower_bound(analysis: &Analysis, executors: NonZeroU32) -> Millis {
let area = analysis
.total_work()
.div_ceil_by(NonZeroU64::from(executors));
analysis.critical_path_len().max(area)
}
type Waiting = BinaryHeap<Reverse<(Millis, UnitId)>>;
struct Readiness {
unmet_edges: Vec<u32>,
released_at: Vec<Millis>,
unsettled_deps: Vec<u32>,
closure_finish: Vec<Millis>,
finished: Vec<bool>,
}
impl Readiness {
fn new(graph: &BuildGraph, count: usize) -> Self {
let degrees: Vec<u32> = graph
.units()
.map(|(id, _)| {
let deps = graph.dependencies(id).unwrap_or(&[]).len();
u32::try_from(deps).unwrap_or(u32::MAX)
})
.collect();
Self {
unmet_edges: degrees.clone(),
released_at: vec![Millis::ZERO; count],
unsettled_deps: degrees,
closure_finish: vec![Millis::ZERO; count],
finished: vec![false; count],
}
}
fn on_start(&mut self, graph: &BuildGraph, id: UnitId, at: Millis, waiting: &mut Waiting) {
let Some(unit) = graph.unit(id) else {
return;
};
for dep in graph.dependents(id).unwrap_or(&[]) {
if dep.kind != EdgeKind::Metadata || requires_closure(graph, dep.unit) {
continue;
}
let offset = unit.metadata_at.unwrap_or(unit.total);
self.satisfy_edge(dep.unit, at.saturating_add(offset), waiting);
}
}
fn on_finish(
&mut self,
graph: &BuildGraph,
id: UnitId,
at: Millis,
finish: &[Millis],
waiting: &mut Waiting,
) {
if let Some(slot) = self.finished.get_mut(id.index()) {
*slot = true;
}
for dep in graph.dependents(id).unwrap_or(&[]) {
if dep.kind != EdgeKind::Full || requires_closure(graph, dep.unit) {
continue;
}
self.satisfy_edge(dep.unit, at, waiting);
}
self.settle(graph, id, finish, waiting);
}
fn satisfy_edge(&mut self, consumer: UnitId, release: Millis, waiting: &mut Waiting) {
if let Some(slot) = self.released_at.get_mut(consumer.index()) {
*slot = (*slot).max(release);
}
let Some(remaining) = self.unmet_edges.get_mut(consumer.index()) else {
return;
};
*remaining = remaining.saturating_sub(1);
if *remaining == 0 {
let at = self
.released_at
.get(consumer.index())
.copied()
.unwrap_or(Millis::ZERO);
waiting.push(Reverse((at, consumer)));
}
}
fn settle(&mut self, graph: &BuildGraph, id: UnitId, finish: &[Millis], waiting: &mut Waiting) {
let mut worklist = Vec::new();
if self.is_settled(id) {
worklist.push(id);
}
while let Some(settled) = worklist.pop() {
let behind = finish
.get(settled.index())
.copied()
.unwrap_or(Millis::ZERO)
.max(
self.closure_finish
.get(settled.index())
.copied()
.unwrap_or(Millis::ZERO),
);
for dep in graph.dependents(settled).unwrap_or(&[]) {
if let Some(slot) = self.closure_finish.get_mut(dep.unit.index()) {
*slot = (*slot).max(behind);
}
let Some(remaining) = self.unsettled_deps.get_mut(dep.unit.index()) else {
continue;
};
*remaining = remaining.saturating_sub(1);
if *remaining > 0 {
continue;
}
if requires_closure(graph, dep.unit) {
let at = self
.closure_finish
.get(dep.unit.index())
.copied()
.unwrap_or(Millis::ZERO);
waiting.push(Reverse((at, dep.unit)));
}
if self.is_settled(dep.unit) {
worklist.push(dep.unit);
}
}
}
}
fn is_settled(&self, id: UnitId) -> bool {
self.finished.get(id.index()).copied().unwrap_or(false)
&& self.unsettled_deps.get(id.index()).copied().unwrap_or(0) == 0
}
}
fn requires_closure(graph: &BuildGraph, id: UnitId) -> bool {
graph
.unit(id)
.is_some_and(|unit| unit.requires_full_closure)
}
fn priorities(graph: &BuildGraph, policy: Policy) -> Vec<u64> {
match policy {
Policy::CargoLike => transitive_dependents(graph)
.into_iter()
.map(|count| count.saturating_add(1))
.collect(),
Policy::LongestPath => {
let analysis = analyze(graph);
let critical_path = analysis.critical_path_len();
graph
.units()
.map(|(id, unit)| {
let latest_start = analysis
.latest_finish(id)
.unwrap_or(critical_path)
.saturating_sub(unit.total);
critical_path.saturating_sub(latest_start).get()
})
.collect()
}
}
}
fn transitive_dependents(graph: &BuildGraph) -> Vec<u64> {
let count = graph.len();
let mut totals = vec![0u64; count];
let mut reachable = vec![0u64; count];
let order = graph.topological_order();
let mut block = 0usize;
while block < count {
let end = block.saturating_add(64).min(count);
reachable.fill(0);
for &id in order.iter().rev() {
let mut mask = 0u64;
for dep in graph.dependents(id).unwrap_or(&[]) {
let index = dep.unit.index();
if index >= block && index < end {
mask |= 1u64 << (index - block);
}
mask |= reachable.get(index).copied().unwrap_or(0);
}
if let Some(slot) = reachable.get_mut(id.index()) {
*slot = mask;
}
}
for (index, mask) in reachable.iter().enumerate() {
if let Some(total) = totals.get_mut(index) {
*total = total.saturating_add(u64::from(mask.count_ones()));
}
}
block = block.saturating_add(64);
}
totals
}