use std::collections::{BTreeMap, BTreeSet};
use critpath_core::{BuildGraph, EdgeKind, GraphBuilder, Millis, Unit, UnitId, UnitKind};
use crate::error::{ParseError, UnitDescription};
use crate::metadata::PackageIndex;
use crate::timings::{TimingReport, TimingUnit};
use crate::units::{self, MatchMethod};
use crate::verbose::{Invocation, Role, VerboseLog};
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[non_exhaustive]
pub enum Severity {
Warning,
}
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
#[non_exhaustive]
pub struct Diagnostic {
pub severity: Severity,
pub code: &'static str,
pub message: String,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum UnblockedSource {
Completion,
Metadata,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[non_exhaustive]
pub struct UnblockedPair {
pub producer: UnitId,
pub consumer: UnitId,
pub source: UnblockedSource,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub struct UnblockedCheck {
pub total: usize,
pub confirmed: usize,
pub unconfirmed: Vec<UnblockedPair>,
}
impl UnblockedCheck {
#[must_use]
pub fn is_consistent(&self) -> bool {
self.unconfirmed.is_empty()
}
}
#[derive(Clone, Debug, PartialEq, Eq, Default)]
#[non_exhaustive]
pub struct BuildMeta {
pub cargo_version: Option<String>,
pub rustc_version: Option<String>,
pub host: Option<String>,
pub target: Option<String>,
pub profile: Option<String>,
pub jobs: Option<u32>,
pub cpus: Option<u32>,
pub observed_max_concurrency: Option<u32>,
pub units_total: usize,
pub units_fresh: usize,
pub compilation_span: Millis,
pub reported_total: Option<Millis>,
pub excluded_prefix: Millis,
pub targets: Option<String>,
pub build_start: Option<String>,
}
#[derive(Clone, Debug)]
#[non_exhaustive]
pub struct BuildInput {
pub graph: BuildGraph,
pub build: BuildMeta,
pub matched_by: Vec<MatchMethod>,
pub unblocked: Vec<UnblockedPair>,
pub diagnostics: Vec<Diagnostic>,
}
impl BuildInput {
#[must_use]
pub fn check_unblocked(&self) -> UnblockedCheck {
let mut pairs = self.unblocked.clone();
pairs.sort();
let mut confirmed = 0usize;
let mut unconfirmed = Vec::new();
let mut closure_of: Option<(UnitId, BTreeSet<UnitId>)> = None;
for pair in &pairs {
let direct = self
.graph
.dependencies(pair.consumer)
.is_some_and(|deps| deps.iter().any(|d| d.unit == pair.producer));
if direct {
confirmed = confirmed.saturating_add(1);
continue;
}
let needs_closure = self
.graph
.unit(pair.consumer)
.is_some_and(|u| u.requires_full_closure);
if needs_closure {
let cached = match &closure_of {
Some((consumer, set)) if *consumer == pair.consumer => set,
_ => {
closure_of = Some((pair.consumer, self.closure(pair.consumer)));
match &closure_of {
Some((_, set)) => set,
None => continue,
}
}
};
if cached.contains(&pair.producer) {
confirmed = confirmed.saturating_add(1);
continue;
}
}
unconfirmed.push(*pair);
}
UnblockedCheck {
total: pairs.len(),
confirmed,
unconfirmed,
}
}
fn closure(&self, unit: UnitId) -> BTreeSet<UnitId> {
let mut seen = BTreeSet::new();
let mut stack: Vec<UnitId> = self
.graph
.dependencies(unit)
.unwrap_or_default()
.iter()
.map(|d| d.unit)
.collect();
while let Some(next) = stack.pop() {
if !seen.insert(next) {
continue;
}
for dep in self.graph.dependencies(next).unwrap_or_default() {
stack.push(dep.unit);
}
}
seen
}
}
struct Assembled<'a> {
invocation: &'a Invocation,
timing: &'a TimingUnit,
method: MatchMethod,
}
pub(crate) fn assemble(
log: &VerboseLog,
report: &TimingReport,
packages: Option<&PackageIndex>,
) -> Result<BuildInput, ParseError> {
if report.units.is_empty() {
return Err(ParseError::EmptyBuild);
}
let pairings = units::pair(log, report, packages)?;
let mut assembled: Vec<Assembled<'_>> = Vec::with_capacity(pairings.len());
for pairing in &pairings {
let (Some(invocation), Some(timing)) = (
log.invocations.get(pairing.invocation),
report.units.get(pairing.unit),
) else {
continue;
};
assembled.push(Assembled {
invocation,
timing,
method: pairing.method,
});
}
assembled.sort_by(|a, b| {
a.timing
.package
.cmp(&b.timing.package)
.then_with(|| a.timing.version.cmp(&b.timing.version))
.then_with(|| a.timing.target.label().cmp(b.timing.target.label()))
.then_with(|| a.invocation.kind.as_str().cmp(b.invocation.kind.as_str()))
.then_with(|| a.invocation.metadata_hash.cmp(&b.invocation.metadata_hash))
.then_with(|| a.timing.index.cmp(&b.timing.index))
});
let mut diagnostics: Vec<Diagnostic> = Vec::new();
let mut builder = GraphBuilder::with_capacity(assembled.len());
let mut matched_by = Vec::with_capacity(assembled.len());
let mut ids = Vec::with_capacity(assembled.len());
for entry in &assembled {
let metadata_at = if entry.invocation.pipelined {
entry.timing.metadata_at
} else {
None
};
let id = builder.add_unit(Unit {
package: entry.timing.package.clone(),
version: entry.timing.version.clone(),
target: entry.timing.target.label().to_owned(),
kind: entry.invocation.kind,
total: entry.timing.duration,
metadata_at,
requires_full_closure: entry.invocation.requires_full_closure,
})?;
ids.push(id);
matched_by.push(entry.method);
}
add_dependency_edges(&assembled, &ids, &mut builder, &mut diagnostics)?;
add_build_script_edges(&assembled, &ids, &mut builder, &mut diagnostics)?;
let graph = builder.build()?;
let unblocked = unblocked_pairs(&assembled, &ids);
report_inexact_matches(&matched_by, &mut diagnostics);
Ok(BuildInput {
graph,
build: meta(report),
matched_by,
unblocked,
diagnostics,
})
}
fn add_dependency_edges(
assembled: &[Assembled<'_>],
ids: &[UnitId],
builder: &mut GraphBuilder,
diagnostics: &mut Vec<Diagnostic>,
) -> Result<(), ParseError> {
let mut by_artifact: BTreeMap<&str, UnitId> = BTreeMap::new();
for (entry, id) in assembled.iter().zip(ids.iter()) {
if let Some(hash) = &entry.invocation.extra_filename {
by_artifact.insert(hash.as_str(), *id);
}
}
for (entry, consumer) in assembled.iter().zip(ids.iter()) {
for dependency in &entry.invocation.externs {
let Some(hash) = &dependency.producer else {
diagnostics.push(Diagnostic {
severity: Severity::Warning,
code: "extern-without-artifact-hash",
message: format!(
"{} names `{}` through an artifact with no compilation hash, so it is not \
one of this build's units and no edge was added for it",
label(entry),
dependency.name
),
});
continue;
};
let Some(producer) = by_artifact.get(hash.as_str()).copied() else {
return Err(ParseError::UnresolvedDependency {
consumer: Box::new(describe(entry)),
dependency: dependency.name.clone(),
producer: hash.clone(),
});
};
let kind = downgrade(
dependency.edge,
producer,
assembled,
ids,
entry,
diagnostics,
);
builder.add_edge(producer, *consumer, kind)?;
}
}
Ok(())
}
fn downgrade(
kind: EdgeKind,
producer: UnitId,
assembled: &[Assembled<'_>],
ids: &[UnitId],
consumer: &Assembled<'_>,
diagnostics: &mut Vec<Diagnostic>,
) -> EdgeKind {
if kind != EdgeKind::Metadata {
return kind;
}
let emits = ids
.iter()
.position(|id| *id == producer)
.and_then(|at| assembled.get(at))
.is_some_and(|entry| entry.invocation.pipelined && entry.timing.metadata_at.is_some());
if emits {
return EdgeKind::Metadata;
}
diagnostics.push(Diagnostic {
severity: Severity::Warning,
code: "metadata-edge-without-metadata",
message: format!(
"{} was given a dependency as metadata, but the timing report records no metadata \
moment for it, so the edge was treated as needing the whole dependency; \
the critical path this produces is an upper bound rather than an estimate",
label(consumer)
),
});
EdgeKind::Full
}
fn add_build_script_edges(
assembled: &[Assembled<'_>],
ids: &[UnitId],
builder: &mut GraphBuilder,
diagnostics: &mut Vec<Diagnostic>,
) -> Result<(), ParseError> {
let mut by_artifact: BTreeMap<&str, UnitId> = BTreeMap::new();
for (entry, id) in assembled.iter().zip(ids.iter()) {
if let Some(hash) = &entry.invocation.extra_filename {
by_artifact.insert(hash.as_str(), *id);
}
}
for (entry, run) in assembled.iter().zip(ids.iter()) {
if entry.invocation.role != Role::BuildScriptRun {
continue;
}
let Some(hash) = &entry.invocation.run_artifact else {
return Err(ParseError::UnresolvedDependency {
consumer: Box::new(describe(entry)),
dependency: "its compiled build script".to_owned(),
producer: "<no compilation hash in the execution path>".to_owned(),
});
};
let Some(compile) = by_artifact.get(hash.as_str()).copied() else {
return Err(ParseError::UnresolvedDependency {
consumer: Box::new(describe(entry)),
dependency: "its compiled build script".to_owned(),
producer: hash.clone(),
});
};
builder.add_edge(compile, *run, EdgeKind::Full)?;
let mut dependents = package_units(assembled, ids, entry, true);
if dependents.is_empty() {
dependents = package_units(assembled, ids, entry, false);
if !dependents.is_empty() {
diagnostics.push(Diagnostic {
severity: Severity::Warning,
code: "build-script-instance-ambiguous",
message: format!(
"the build script of {} shares no feature set with any of that package's \
compilations, so every one of them was made to wait for it; \
if the package is built twice with different features this is stricter \
than the real build",
label(entry)
),
});
}
}
for dependent in dependents {
builder.add_edge(*run, dependent, EdgeKind::Full)?;
}
}
Ok(())
}
fn package_units(
assembled: &[Assembled<'_>],
ids: &[UnitId],
run: &Assembled<'_>,
match_features: bool,
) -> Vec<UnitId> {
assembled
.iter()
.zip(ids.iter())
.filter(|(entry, _)| {
entry.invocation.kind != UnitKind::BuildScriptCompile
&& entry.invocation.kind != UnitKind::BuildScriptRun
&& entry.timing.package == run.timing.package
&& entry.timing.version == run.timing.version
&& (!match_features || entry.timing.features == run.timing.features)
})
.map(|(_, id)| *id)
.collect()
}
fn unblocked_pairs(assembled: &[Assembled<'_>], ids: &[UnitId]) -> Vec<UnblockedPair> {
let mut by_index: BTreeMap<usize, UnitId> = BTreeMap::new();
for (entry, id) in assembled.iter().zip(ids.iter()) {
by_index.insert(entry.timing.index, *id);
}
let mut pairs = Vec::new();
for (entry, producer) in assembled.iter().zip(ids.iter()) {
for (indices, source) in [
(&entry.timing.unblocked, UnblockedSource::Completion),
(&entry.timing.unblocked_rmeta, UnblockedSource::Metadata),
] {
for index in indices.iter() {
if let Some(consumer) = by_index.get(index).copied() {
pairs.push(UnblockedPair {
producer: *producer,
consumer,
source,
});
}
}
}
}
pairs.sort();
pairs.dedup();
pairs
}
fn report_inexact_matches(methods: &[MatchMethod], diagnostics: &mut Vec<Diagnostic>) {
let ordered = methods.iter().filter(|m| **m == MatchMethod::StartOrder);
let count = ordered.count();
if count > 0 {
diagnostics.push(Diagnostic {
severity: Severity::Warning,
code: "units-matched-by-order",
message: format!(
"{count} unit(s) could not be told apart from another unit of the same package, \
version and feature set, so each was paired with a timing entry by start order; \
they differ only in weight, and swapping two of them would move work between two \
identical compilations"
),
});
}
}
fn meta(report: &TimingReport) -> BuildMeta {
BuildMeta {
cargo_version: None,
rustc_version: report.rustc_version.clone(),
host: report.host.clone(),
target: report.target.clone(),
profile: report.profile.clone(),
jobs: report.jobs,
cpus: report.cpus,
observed_max_concurrency: report.max_concurrency,
units_total: report.total_units,
units_fresh: report.fresh_units,
compilation_span: report.compilation_span(),
reported_total: report.reported_total,
excluded_prefix: report.excluded_prefix(),
targets: report.targets.clone(),
build_start: report.build_start.clone(),
}
}
fn label(entry: &Assembled<'_>) -> String {
format!(
"{} {} ({})",
entry.timing.package,
entry.timing.version,
entry.timing.target.label()
)
}
fn describe(entry: &Assembled<'_>) -> UnitDescription {
UnitDescription {
package: entry.timing.package.clone(),
version: entry.timing.version.clone(),
target: entry.timing.target.label().to_owned(),
position: entry.timing.position.saturating_add(1),
}
}