use crate::graph::{BuildGraph, EdgeKind, UnitId};
use crate::millis::Millis;
#[derive(Clone, Debug)]
pub struct Analysis {
earliest_start: Vec<Millis>,
earliest_finish: Vec<Millis>,
latest_finish: Vec<Millis>,
contribution: Vec<Option<Millis>>,
path: Vec<UnitId>,
critical_path_len: Millis,
total_work: Millis,
}
#[derive(Clone, Copy)]
struct Reason {
producer: UnitId,
kind: EdgeKind,
}
impl Analysis {
#[must_use]
pub fn critical_path_len(&self) -> Millis {
self.critical_path_len
}
#[must_use]
pub fn critical_path(&self) -> &[UnitId] {
&self.path
}
#[must_use]
pub fn total_work(&self) -> Millis {
self.total_work
}
#[must_use]
pub fn earliest_start(&self, id: UnitId) -> Option<Millis> {
self.earliest_start.get(id.index()).copied()
}
#[must_use]
pub fn earliest_finish(&self, id: UnitId) -> Option<Millis> {
self.earliest_finish.get(id.index()).copied()
}
#[must_use]
pub fn latest_finish(&self, id: UnitId) -> Option<Millis> {
self.latest_finish.get(id.index()).copied()
}
#[must_use]
pub fn slack(&self, id: UnitId) -> Option<Millis> {
let latest = self.latest_finish(id)?;
let earliest = self.earliest_finish(id)?;
Some(latest.saturating_sub(earliest))
}
#[must_use]
pub fn is_critical(&self, id: UnitId) -> bool {
self.slack(id) == Some(Millis::ZERO)
}
#[must_use]
pub fn critical_contribution(&self, id: UnitId) -> Option<Millis> {
self.contribution.get(id.index()).copied().flatten()
}
}
#[must_use]
pub fn analyze(graph: &BuildGraph) -> Analysis {
let count = graph.len();
let (earliest_start, earliest_finish, reason) = forward_pass(graph, count);
let (critical_path_len, attaining) = latest_finisher(graph, &earliest_finish);
let latest_finish = backward_pass(graph, count, critical_path_len, &earliest_finish);
let (path, contribution) = recover_path(graph, count, attaining, &reason);
Analysis {
earliest_start,
earliest_finish,
latest_finish,
contribution,
path,
critical_path_len,
total_work: graph.total_work(),
}
}
fn forward_pass(
graph: &BuildGraph,
count: usize,
) -> (Vec<Millis>, Vec<Millis>, Vec<Option<Reason>>) {
let mut earliest_start = vec![Millis::ZERO; count];
let mut earliest_finish = vec![Millis::ZERO; count];
let mut reason: Vec<Option<Reason>> = vec![None; count];
let mut closure_finish: Vec<Option<Candidate>> = vec![None; count];
for &id in graph.topological_order() {
let Some(unit) = graph.unit(id) else {
continue;
};
let deps = graph.dependencies(id).unwrap_or(&[]);
let mut closure: Option<Candidate> = None;
for dep in deps {
let index = dep.unit.index();
let dep_finish = earliest_finish.get(index).copied().unwrap_or(Millis::ZERO);
take_later(&mut closure, dep_finish, dep.unit);
if let Some(inherited) = closure_finish.get(index).copied().flatten() {
take_later(&mut closure, inherited.time, inherited.unit);
}
}
if let Some(slot) = closure_finish.get_mut(id.index()) {
*slot = closure;
}
let start = if unit.requires_full_closure {
closure.map(|c| {
(
c.time,
Reason {
producer: c.unit,
kind: EdgeKind::Full,
},
)
})
} else {
let mut best: Option<(Millis, Reason)> = None;
for dep in deps {
let Some(producer) = graph.unit(dep.unit) else {
continue;
};
let offset = release_offset(producer.total, producer.metadata_at, dep.kind);
let dep_start = earliest_start
.get(dep.unit.index())
.copied()
.unwrap_or(Millis::ZERO);
let release = dep_start.saturating_add(offset);
let better = match best {
None => true,
Some((time, current)) => {
release > time || (release == time && dep.unit < current.producer)
}
};
if better {
best = Some((
release,
Reason {
producer: dep.unit,
kind: dep.kind,
},
));
}
}
best
};
let (start, why) = match start {
Some((start, why)) => (start, Some(why)),
None => (Millis::ZERO, None),
};
if let Some(slot) = earliest_start.get_mut(id.index()) {
*slot = start;
}
if let Some(slot) = earliest_finish.get_mut(id.index()) {
*slot = start.saturating_add(unit.total);
}
if let Some(slot) = reason.get_mut(id.index()) {
*slot = why;
}
}
(earliest_start, earliest_finish, reason)
}
fn backward_pass(
graph: &BuildGraph,
count: usize,
critical_path_len: Millis,
earliest_finish: &[Millis],
) -> Vec<Millis> {
let mut latest_finish = vec![critical_path_len; count];
let mut closure_cap: Vec<Option<Millis>> = vec![None; count];
for &id in graph.topological_order().iter().rev() {
let Some(unit) = graph.unit(id) else {
continue;
};
let mut cap: Option<Millis> = None;
let mut bound = critical_path_len;
for dep in graph.dependents(id).unwrap_or(&[]) {
let Some(consumer) = graph.unit(dep.unit) else {
continue;
};
let consumer_latest_finish = latest_finish
.get(dep.unit.index())
.copied()
.unwrap_or(critical_path_len);
let consumer_latest_start = consumer_latest_finish.saturating_sub(consumer.total);
if consumer.requires_full_closure {
take_earlier(&mut cap, consumer_latest_start);
} else {
if let Some(inherited) = closure_cap.get(dep.unit.index()).copied().flatten() {
take_earlier(&mut cap, inherited);
}
let offset = release_offset(unit.total, unit.metadata_at, dep.kind);
let slack_past_release = unit.total.saturating_sub(offset);
bound = bound.min(consumer_latest_start.saturating_add(slack_past_release));
}
}
if let Some(cap) = cap {
bound = bound.min(cap);
}
if let Some(slot) = closure_cap.get_mut(id.index()) {
*slot = cap;
}
let floor = earliest_finish
.get(id.index())
.copied()
.unwrap_or(Millis::ZERO);
if let Some(slot) = latest_finish.get_mut(id.index()) {
*slot = bound.max(floor);
}
}
latest_finish
}
fn recover_path(
graph: &BuildGraph,
count: usize,
attaining: Option<UnitId>,
reason: &[Option<Reason>],
) -> (Vec<UnitId>, Vec<Option<Millis>>) {
let mut contribution: Vec<Option<Millis>> = vec![None; count];
let mut path = Vec::new();
let Some(attaining) = attaining else {
return (path, contribution);
};
if let Some(unit) = graph.unit(attaining) {
if let Some(slot) = contribution.get_mut(attaining.index()) {
*slot = Some(unit.total);
}
}
let mut current = attaining;
for _ in 0..count {
path.push(current);
let Some(why) = reason.get(current.index()).copied().flatten() else {
break;
};
if let Some(producer) = graph.unit(why.producer) {
if let Some(slot) = contribution.get_mut(why.producer.index()) {
*slot = Some(release_offset(
producer.total,
producer.metadata_at,
why.kind,
));
}
}
current = why.producer;
}
path.reverse();
(path, contribution)
}
fn release_offset(total: Millis, metadata_at: Option<Millis>, kind: EdgeKind) -> Millis {
match kind {
EdgeKind::Metadata => metadata_at.unwrap_or(total),
EdgeKind::Full => total,
}
}
#[derive(Clone, Copy)]
struct Candidate {
time: Millis,
unit: UnitId,
}
fn take_later(best: &mut Option<Candidate>, time: Millis, unit: UnitId) {
let better = match best {
None => true,
Some(current) => time > current.time || (time == current.time && unit < current.unit),
};
if better {
*best = Some(Candidate { time, unit });
}
}
fn take_earlier(best: &mut Option<Millis>, time: Millis) {
*best = Some(match *best {
None => time,
Some(current) => current.min(time),
});
}
fn latest_finisher(graph: &BuildGraph, earliest_finish: &[Millis]) -> (Millis, Option<UnitId>) {
let mut best: Option<Candidate> = None;
for (id, _) in graph.units() {
let finish = earliest_finish
.get(id.index())
.copied()
.unwrap_or(Millis::ZERO);
take_later(&mut best, finish, id);
}
match best {
Some(best) => (best.time, Some(best.unit)),
None => (Millis::ZERO, None),
}
}