use core::fmt;
use core::num::NonZeroU64;
use crate::error::GraphError;
use crate::graph::{BuildGraph, GraphBuilder, Unit, UnitId, UnitKind};
use crate::millis::Millis;
const PART_A: &str = " (part a)";
const PART_B: &str = " (part b)";
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum SplitDependents {
Optimistic,
Pessimistic,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Transform {
SplitUnit {
unit: UnitId,
numerator: u64,
denominator: NonZeroU64,
dependents: SplitDependents,
overhead: Millis,
},
RemoveEdge {
from: UnitId,
to: UnitId,
},
RemoveUnits {
units: Vec<UnitId>,
},
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Mapped {
Kept(UnitId),
Split {
first: UnitId,
second: UnitId,
},
Removed,
}
impl Mapped {
#[must_use]
pub const fn primary(self) -> Option<UnitId> {
match self {
Self::Kept(id) => Some(id),
Self::Split { first, .. } => Some(first),
_ => None,
}
}
#[must_use]
pub const fn secondary(self) -> Option<UnitId> {
match self {
Self::Split { second, .. } => Some(second),
_ => None,
}
}
#[must_use]
pub const fn is_removed(self) -> bool {
matches!(self, Self::Removed)
}
}
#[derive(Clone, Debug)]
pub struct Applied {
graph: BuildGraph,
mapping: Vec<(UnitId, Mapped)>,
}
impl Applied {
#[must_use]
pub fn graph(&self) -> &BuildGraph {
&self.graph
}
#[must_use]
pub fn into_graph(self) -> BuildGraph {
self.graph
}
#[must_use]
pub fn mapped(&self, original: UnitId) -> Option<Mapped> {
self.mapping
.get(original.index())
.map(|&(_, mapped)| mapped)
}
pub fn mapping(&self) -> impl ExactSizeIterator<Item = (UnitId, Mapped)> + '_ {
self.mapping.iter().copied()
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum TransformError {
UnknownUnit {
unit: UnitId,
units: usize,
},
UnsplittableKind {
unit: UnitId,
kind: UnitKind,
},
FractionAboveOne {
unit: UnitId,
numerator: u64,
denominator: NonZeroU64,
},
MissingEdge {
from: UnitId,
to: UnitId,
},
Rebuild {
source: GraphError,
},
}
impl From<GraphError> for TransformError {
fn from(source: GraphError) -> Self {
Self::Rebuild { source }
}
}
impl fmt::Display for TransformError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::UnknownUnit { unit, units } => write!(
f,
"unit {unit} is not part of this graph, which holds {units} units; \
identifiers are only valid for the graph that handed them out, \
so take the identifier from the graph being transformed"
),
Self::UnsplittableKind { unit, kind } => write!(
f,
"unit {unit} is a {kind} and cannot be split, \
because one run of one build script is a single indivisible step; \
split one of the library units instead, \
or shorten the build script by other means"
),
Self::FractionAboveOne {
unit,
numerator,
denominator,
} => write!(
f,
"the division fraction {numerator}/{denominator} for unit {unit} is more than the \
whole unit, which would leave the second part with negative work; \
choose a numerator no larger than the denominator"
),
Self::MissingEdge { from, to } => write!(
f,
"there is no edge from unit {from} to unit {to}, so it cannot be removed; \
list the dependencies of unit {to} and name one of those, \
remembering that an edge runs from the producer to the consumer"
),
Self::Rebuild { source } => write!(
f,
"the graph this transformation produced did not validate: {source}"
),
}
}
}
impl std::error::Error for TransformError {
fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
match self {
Self::Rebuild { source } => Some(source),
_ => None,
}
}
}
#[must_use]
pub fn roots(graph: &BuildGraph) -> Vec<UnitId> {
graph
.units()
.filter(|&(id, _)| is_root(graph, id))
.map(|(id, _)| id)
.collect()
}
pub fn apply(graph: &BuildGraph, transform: &Transform) -> Result<Applied, TransformError> {
match transform {
Transform::SplitUnit {
unit,
numerator,
denominator,
dependents,
overhead,
} => split_unit(
graph,
*unit,
*numerator,
*denominator,
*dependents,
*overhead,
),
Transform::RemoveEdge { from, to } => remove_edge(graph, *from, *to),
Transform::RemoveUnits { units } => remove_units(graph, units),
}
}
fn split_unit(
graph: &BuildGraph,
unit: UnitId,
numerator: u64,
denominator: NonZeroU64,
dependents: SplitDependents,
overhead: Millis,
) -> Result<Applied, TransformError> {
let original = graph.unit(unit).ok_or(TransformError::UnknownUnit {
unit,
units: graph.len(),
})?;
if matches!(
original.kind,
UnitKind::BuildScriptCompile | UnitKind::BuildScriptRun
) {
return Err(TransformError::UnsplittableKind {
unit,
kind: original.kind,
});
}
if numerator > denominator.get() {
return Err(TransformError::FractionAboveOne {
unit,
numerator,
denominator,
});
}
let first_work = original.total.scaled(numerator, denominator);
let second_work = original.total.saturating_sub(first_work);
let second_share = denominator.get().saturating_sub(numerator);
let part = |work: Millis, share: u64, suffix: &str| {
let total = work.saturating_add(overhead);
Unit {
package: original.package.clone(),
target: format!("{}{suffix}", original.target),
version: original.version.clone(),
kind: original.kind,
total,
metadata_at: original
.metadata_at
.map(|at| at.scaled(share, denominator).min(total)),
requires_full_closure: original.requires_full_closure,
}
};
let first_unit = part(first_work, numerator, PART_A);
let second_unit = part(second_work, second_share, PART_B);
let dependents_take_first = first_unit.total <= second_unit.total;
let mut builder = GraphBuilder::with_capacity(graph.len().saturating_add(1));
let mut mapping = Vec::with_capacity(graph.len());
let mut parts = None;
for (old, existing) in graph.units() {
if old == unit {
let first = builder.add_unit(first_unit.clone())?;
let second = builder.add_unit(second_unit.clone())?;
parts = Some((first, second));
mapping.push((old, Mapped::Split { first, second }));
} else {
let new = builder.add_unit(existing.clone())?;
mapping.push((old, Mapped::Kept(new)));
}
}
let Some((first, second)) = parts else {
return Err(TransformError::UnknownUnit {
unit,
units: graph.len(),
});
};
let units = graph.len();
for (consumer, _) in graph.units() {
for dep in graph.dependencies(consumer).unwrap_or(&[]) {
if consumer == unit {
let from = translate(&mapping, dep.unit, units)?;
builder.add_edge(from, first, dep.kind)?;
builder.add_edge(from, second, dep.kind)?;
} else if dep.unit == unit {
let to = translate(&mapping, consumer, units)?;
match dependents {
SplitDependents::Pessimistic => {
builder.add_edge(first, to, dep.kind)?;
builder.add_edge(second, to, dep.kind)?;
}
SplitDependents::Optimistic => {
let from = if dependents_take_first { first } else { second };
builder.add_edge(from, to, dep.kind)?;
}
}
} else {
let from = translate(&mapping, dep.unit, units)?;
let to = translate(&mapping, consumer, units)?;
builder.add_edge(from, to, dep.kind)?;
}
}
}
Ok(Applied {
graph: builder.build()?,
mapping,
})
}
fn remove_edge(graph: &BuildGraph, from: UnitId, to: UnitId) -> Result<Applied, TransformError> {
for id in [from, to] {
if graph.unit(id).is_none() {
return Err(TransformError::UnknownUnit {
unit: id,
units: graph.len(),
});
}
}
let present = graph
.dependencies(to)
.unwrap_or(&[])
.iter()
.any(|dep| dep.unit == from);
if !present {
return Err(TransformError::MissingEdge { from, to });
}
rebuild(graph, &vec![true; graph.len()], Some((from, to)))
}
fn remove_units(graph: &BuildGraph, targets: &[UnitId]) -> Result<Applied, TransformError> {
let mut survives = vec![true; graph.len()];
for &target in targets {
match survives.get_mut(target.index()) {
Some(slot) => *slot = false,
None => {
return Err(TransformError::UnknownUnit {
unit: target,
units: graph.len(),
})
}
}
}
let mut reaches_root = vec![false; graph.len()];
let mut pending: Vec<UnitId> = Vec::new();
for (id, _) in graph.units() {
if is_root(graph, id) && survives.get(id.index()).copied().unwrap_or(false) {
if let Some(slot) = reaches_root.get_mut(id.index()) {
*slot = true;
}
pending.push(id);
}
}
while let Some(id) = pending.pop() {
for dep in graph.dependencies(id).unwrap_or(&[]) {
if !survives.get(dep.unit.index()).copied().unwrap_or(false) {
continue;
}
if let Some(slot) = reaches_root.get_mut(dep.unit.index()) {
if !*slot {
*slot = true;
pending.push(dep.unit);
}
}
}
}
rebuild(graph, &reaches_root, None)
}
fn rebuild(
graph: &BuildGraph,
keep: &[bool],
drop_edge: Option<(UnitId, UnitId)>,
) -> Result<Applied, TransformError> {
let mut builder = GraphBuilder::with_capacity(graph.len());
let mut mapping = Vec::with_capacity(graph.len());
for (old, existing) in graph.units() {
if keep.get(old.index()).copied().unwrap_or(false) {
let new = builder.add_unit(existing.clone())?;
mapping.push((old, Mapped::Kept(new)));
} else {
mapping.push((old, Mapped::Removed));
}
}
for (consumer, _) in graph.units() {
for dep in graph.dependencies(consumer).unwrap_or(&[]) {
if drop_edge == Some((dep.unit, consumer)) {
continue;
}
let (Some(from), Some(to)) = (kept(&mapping, dep.unit), kept(&mapping, consumer))
else {
continue;
};
builder.add_edge(from, to, dep.kind)?;
}
}
Ok(Applied {
graph: builder.build()?,
mapping,
})
}
fn is_root(graph: &BuildGraph, id: UnitId) -> bool {
match graph.dependents(id) {
Some(dependents) => dependents.is_empty(),
None => false,
}
}
fn kept(mapping: &[(UnitId, Mapped)], old: UnitId) -> Option<UnitId> {
match mapping.get(old.index()) {
Some(&(_, Mapped::Kept(new))) => Some(new),
_ => None,
}
}
fn translate(
mapping: &[(UnitId, Mapped)],
old: UnitId,
units: usize,
) -> Result<UnitId, TransformError> {
kept(mapping, old).ok_or(TransformError::UnknownUnit { unit: old, units })
}