use core::fmt;
use std::collections::{BTreeMap, VecDeque};
use crate::error::GraphError;
use crate::millis::Millis;
pub const MAX_UNITS: usize = u32::MAX as usize - 1;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct UnitId(u32);
impl UnitId {
#[must_use]
pub const fn index(self) -> usize {
self.0 as usize
}
}
impl fmt::Display for UnitId {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.0)
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[non_exhaustive]
pub enum UnitKind {
Lib,
ProcMacro,
Bin,
Test,
BuildScriptCompile,
BuildScriptRun,
Other,
}
impl UnitKind {
#[must_use]
pub const fn as_str(self) -> &'static str {
match self {
Self::Lib => "lib",
Self::ProcMacro => "proc-macro",
Self::Bin => "bin",
Self::Test => "test",
Self::BuildScriptCompile => "build-script-compile",
Self::BuildScriptRun => "build-script-run",
Self::Other => "other",
}
}
}
impl fmt::Display for UnitKind {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(self.as_str())
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Unit {
pub package: String,
pub version: String,
pub target: String,
pub kind: UnitKind,
pub total: Millis,
pub metadata_at: Option<Millis>,
pub requires_full_closure: bool,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum EdgeKind {
Metadata,
Full,
}
impl EdgeKind {
#[must_use]
pub const fn as_str(self) -> &'static str {
match self {
Self::Metadata => "metadata",
Self::Full => "full",
}
}
#[must_use]
const fn is_at_least_as_strong_as(self, other: Self) -> bool {
matches!(self, Self::Full) || matches!(other, Self::Metadata)
}
}
impl fmt::Display for EdgeKind {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(self.as_str())
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Dep {
pub unit: UnitId,
pub kind: EdgeKind,
}
#[derive(Clone, Debug)]
pub struct BuildGraph {
units: Vec<Unit>,
dep_start: Vec<u32>,
deps: Vec<Dep>,
rdep_start: Vec<u32>,
rdeps: Vec<Dep>,
topo: Vec<UnitId>,
total_work: Millis,
}
impl BuildGraph {
#[must_use]
pub fn len(&self) -> usize {
self.units.len()
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.units.is_empty()
}
#[must_use]
pub fn edge_count(&self) -> usize {
self.deps.len()
}
#[must_use]
pub fn total_work(&self) -> Millis {
self.total_work
}
#[must_use]
pub fn unit(&self, id: UnitId) -> Option<&Unit> {
self.units.get(id.index())
}
pub fn units(&self) -> impl ExactSizeIterator<Item = (UnitId, &Unit)> + '_ {
self.units
.iter()
.enumerate()
.map(|(i, u)| (UnitId(i as u32), u))
}
#[must_use]
pub fn dependencies(&self, id: UnitId) -> Option<&[Dep]> {
Self::slice(&self.deps, &self.dep_start, id)
}
#[must_use]
pub fn dependents(&self, id: UnitId) -> Option<&[Dep]> {
Self::slice(&self.rdeps, &self.rdep_start, id)
}
#[must_use]
pub fn topological_order(&self) -> &[UnitId] {
&self.topo
}
fn slice<'a>(edges: &'a [Dep], starts: &[u32], id: UnitId) -> Option<&'a [Dep]> {
let from = *starts.get(id.index())? as usize;
let to = *starts.get(id.index().checked_add(1)?)? as usize;
edges.get(from..to)
}
}
#[derive(Clone, Debug, Default)]
pub struct GraphBuilder {
units: Vec<Unit>,
edges: BTreeMap<(u32, u32), EdgeKind>,
}
impl GraphBuilder {
#[must_use]
pub fn new() -> Self {
Self::default()
}
#[must_use]
pub fn with_capacity(units: usize) -> Self {
Self {
units: Vec::with_capacity(units),
edges: BTreeMap::new(),
}
}
pub fn add_unit(&mut self, unit: Unit) -> Result<UnitId, GraphError> {
if self.units.len() >= MAX_UNITS {
return Err(GraphError::UnitLimitExceeded { limit: MAX_UNITS });
}
let id = UnitId(self.units.len() as u32);
self.units.push(unit);
Ok(id)
}
pub fn add_edge(&mut self, from: UnitId, to: UnitId, kind: EdgeKind) -> Result<(), GraphError> {
for id in [from, to] {
if id.index() >= self.units.len() {
return Err(GraphError::UnknownUnit {
id,
units: self.units.len(),
});
}
}
if from == to {
return Err(GraphError::SelfDependency { unit: from });
}
self.edges
.entry((to.0, from.0))
.and_modify(|existing| {
if kind.is_at_least_as_strong_as(*existing) {
*existing = kind;
}
})
.or_insert(kind);
Ok(())
}
pub fn build(self) -> Result<BuildGraph, GraphError> {
let count = self.units.len();
for (i, unit) in self.units.iter().enumerate() {
if let Some(metadata_at) = unit.metadata_at {
if metadata_at > unit.total {
return Err(GraphError::MetadataAfterCompletion {
unit: UnitId(i as u32),
metadata_at,
total: unit.total,
});
}
}
}
for (&(consumer, producer), &kind) in &self.edges {
if kind == EdgeKind::Metadata {
let emits = self
.units
.get(producer as usize)
.is_some_and(|u| u.metadata_at.is_some());
if !emits {
return Err(GraphError::MetadataEdgeFromOpaqueUnit {
producer: UnitId(producer),
consumer: UnitId(consumer),
});
}
}
}
let mut in_degree = vec![0u32; count];
let mut out_degree = vec![0u32; count];
for &(consumer, producer) in self.edges.keys() {
if let Some(d) = in_degree.get_mut(consumer as usize) {
*d = d.saturating_add(1);
}
if let Some(d) = out_degree.get_mut(producer as usize) {
*d = d.saturating_add(1);
}
}
let dep_start = prefix_sums(&in_degree);
let deps: Vec<Dep> = self
.edges
.iter()
.map(|(&(_, producer), &kind)| Dep {
unit: UnitId(producer),
kind,
})
.collect();
let rdep_start = prefix_sums(&out_degree);
let mut cursor = rdep_start.clone();
let mut rdeps = vec![
Dep {
unit: UnitId(0),
kind: EdgeKind::Full,
};
self.edges.len()
];
for (&(consumer, producer), &kind) in &self.edges {
let Some(slot) = cursor.get_mut(producer as usize) else {
continue;
};
let at = *slot as usize;
*slot = slot.saturating_add(1);
if let Some(cell) = rdeps.get_mut(at) {
*cell = Dep {
unit: UnitId(consumer),
kind,
};
}
}
let topo = topological_order(count, &in_degree, &rdep_start, &rdeps);
if topo.len() < count {
return Err(GraphError::Cycle {
units: find_cycle(count, &topo, &dep_start, &deps),
});
}
let total_work = self.units.iter().map(|u| u.total).sum();
Ok(BuildGraph {
units: self.units,
dep_start,
deps,
rdep_start,
rdeps,
topo,
total_work,
})
}
}
fn prefix_sums(degrees: &[u32]) -> Vec<u32> {
let mut starts = Vec::with_capacity(degrees.len().saturating_add(1));
let mut running = 0u32;
for degree in degrees {
starts.push(running);
running = running.saturating_add(*degree);
}
starts.push(running);
starts
}
fn topological_order(
count: usize,
in_degree: &[u32],
rdep_start: &[u32],
rdeps: &[Dep],
) -> Vec<UnitId> {
let mut remaining = in_degree.to_vec();
let mut order = Vec::with_capacity(count);
let mut queue: VecDeque<u32> = (0..count)
.filter(|&i| remaining.get(i).copied() == Some(0))
.map(|i| i as u32)
.collect();
while let Some(node) = queue.pop_front() {
order.push(UnitId(node));
let from = *rdep_start.get(node as usize).unwrap_or(&0) as usize;
let to = rdep_start
.get((node as usize).saturating_add(1))
.copied()
.unwrap_or(0) as usize;
for dep in rdeps.get(from..to).unwrap_or(&[]) {
if let Some(d) = remaining.get_mut(dep.unit.index()) {
*d = d.saturating_sub(1);
if *d == 0 {
queue.push_back(dep.unit.0);
}
}
}
}
order
}
fn find_cycle(count: usize, placed: &[UnitId], dep_start: &[u32], deps: &[Dep]) -> Vec<UnitId> {
let mut stuck = vec![true; count];
for id in placed {
if let Some(slot) = stuck.get_mut(id.index()) {
*slot = false;
}
}
let Some(start) = (0..count).find(|&i| stuck.get(i).copied() == Some(true)) else {
return Vec::new();
};
let mut on_path = vec![usize::MAX; count];
let mut path: Vec<u32> = Vec::new();
let mut current = start as u32;
loop {
if let Some(&position) = on_path.get(current as usize) {
if position != usize::MAX {
let mut cycle: Vec<UnitId> = path
.get(position..)
.unwrap_or(&[])
.iter()
.map(|&n| UnitId(n))
.collect();
cycle.reverse();
return cycle;
}
}
if let Some(slot) = on_path.get_mut(current as usize) {
*slot = path.len();
}
path.push(current);
let from = *dep_start.get(current as usize).unwrap_or(&0) as usize;
let to = dep_start
.get((current as usize).saturating_add(1))
.copied()
.unwrap_or(0) as usize;
let next = deps
.get(from..to)
.unwrap_or(&[])
.iter()
.filter(|d| stuck.get(d.unit.index()).copied() == Some(true))
.map(|d| d.unit.0)
.min();
match next {
Some(n) => current = n,
None => return path.iter().map(|&n| UnitId(n)).collect(),
}
}
}