1use std::collections::{BTreeMap, BTreeSet};
5
6use critpath_core::{BuildGraph, EdgeKind, GraphBuilder, Millis, Unit, UnitId, UnitKind};
7
8use crate::error::{ParseError, UnitDescription};
9use crate::metadata::PackageIndex;
10use crate::timings::{TimingReport, TimingUnit};
11use crate::units::{self, MatchMethod};
12use crate::verbose::{Invocation, Role, VerboseLog};
13
14#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
20#[non_exhaustive]
21pub enum Severity {
22 Warning,
24}
25
26#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
28#[non_exhaustive]
29pub struct Diagnostic {
30 pub severity: Severity,
32 pub code: &'static str,
34 pub message: String,
36}
37
38#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
40pub enum UnblockedSource {
41 Completion,
43 Metadata,
45}
46
47#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
49#[non_exhaustive]
50pub struct UnblockedPair {
51 pub producer: UnitId,
53 pub consumer: UnitId,
55 pub source: UnblockedSource,
57}
58
59#[derive(Clone, Debug, PartialEq, Eq)]
61#[non_exhaustive]
62pub struct UnblockedCheck {
63 pub total: usize,
65 pub confirmed: usize,
67 pub unconfirmed: Vec<UnblockedPair>,
69}
70
71impl UnblockedCheck {
72 #[must_use]
74 pub fn is_consistent(&self) -> bool {
75 self.unconfirmed.is_empty()
76 }
77}
78
79#[derive(Clone, Debug, PartialEq, Eq, Default)]
85#[non_exhaustive]
86pub struct BuildMeta {
87 pub cargo_version: Option<String>,
89 pub rustc_version: Option<String>,
91 pub host: Option<String>,
93 pub target: Option<String>,
95 pub profile: Option<String>,
97 pub jobs: Option<u32>,
99 pub cpus: Option<u32>,
101 pub observed_max_concurrency: Option<u32>,
104 pub units_total: usize,
106 pub units_fresh: usize,
109 pub compilation_span: Millis,
111 pub reported_total: Option<Millis>,
113 pub excluded_prefix: Millis,
116 pub targets: Option<String>,
118 pub build_start: Option<String>,
120}
121
122#[derive(Clone, Debug)]
124#[non_exhaustive]
125pub struct BuildInput {
126 pub graph: BuildGraph,
128 pub build: BuildMeta,
130 pub matched_by: Vec<MatchMethod>,
133 pub unblocked: Vec<UnblockedPair>,
137 pub diagnostics: Vec<Diagnostic>,
139}
140
141impl BuildInput {
142 #[must_use]
154 pub fn check_unblocked(&self) -> UnblockedCheck {
155 let mut pairs = self.unblocked.clone();
156 pairs.sort();
158
159 let mut confirmed = 0usize;
160 let mut unconfirmed = Vec::new();
161 let mut closure_of: Option<(UnitId, BTreeSet<UnitId>)> = None;
162
163 for pair in &pairs {
164 let direct = self
165 .graph
166 .dependencies(pair.consumer)
167 .is_some_and(|deps| deps.iter().any(|d| d.unit == pair.producer));
168 if direct {
169 confirmed = confirmed.saturating_add(1);
170 continue;
171 }
172 let needs_closure = self
173 .graph
174 .unit(pair.consumer)
175 .is_some_and(|u| u.requires_full_closure);
176 if needs_closure {
177 let cached = match &closure_of {
178 Some((consumer, set)) if *consumer == pair.consumer => set,
179 _ => {
180 closure_of = Some((pair.consumer, self.closure(pair.consumer)));
181 match &closure_of {
182 Some((_, set)) => set,
183 None => continue,
184 }
185 }
186 };
187 if cached.contains(&pair.producer) {
188 confirmed = confirmed.saturating_add(1);
189 continue;
190 }
191 }
192 unconfirmed.push(*pair);
193 }
194
195 UnblockedCheck {
196 total: pairs.len(),
197 confirmed,
198 unconfirmed,
199 }
200 }
201
202 fn closure(&self, unit: UnitId) -> BTreeSet<UnitId> {
204 let mut seen = BTreeSet::new();
205 let mut stack: Vec<UnitId> = self
206 .graph
207 .dependencies(unit)
208 .unwrap_or_default()
209 .iter()
210 .map(|d| d.unit)
211 .collect();
212 while let Some(next) = stack.pop() {
213 if !seen.insert(next) {
214 continue;
215 }
216 for dep in self.graph.dependencies(next).unwrap_or_default() {
217 stack.push(dep.unit);
218 }
219 }
220 seen
221 }
222}
223
224struct Assembled<'a> {
226 invocation: &'a Invocation,
227 timing: &'a TimingUnit,
228 method: MatchMethod,
229}
230
231pub(crate) fn assemble(
233 log: &VerboseLog,
234 report: &TimingReport,
235 packages: Option<&PackageIndex>,
236) -> Result<BuildInput, ParseError> {
237 if report.units.is_empty() {
238 return Err(ParseError::EmptyBuild);
239 }
240 let pairings = units::pair(log, report, packages)?;
241
242 let mut assembled: Vec<Assembled<'_>> = Vec::with_capacity(pairings.len());
243 for pairing in &pairings {
244 let (Some(invocation), Some(timing)) = (
245 log.invocations.get(pairing.invocation),
246 report.units.get(pairing.unit),
247 ) else {
248 continue;
249 };
250 assembled.push(Assembled {
251 invocation,
252 timing,
253 method: pairing.method,
254 });
255 }
256
257 assembled.sort_by(|a, b| {
262 a.timing
263 .package
264 .cmp(&b.timing.package)
265 .then_with(|| a.timing.version.cmp(&b.timing.version))
266 .then_with(|| a.timing.target.label().cmp(b.timing.target.label()))
267 .then_with(|| a.invocation.kind.as_str().cmp(b.invocation.kind.as_str()))
268 .then_with(|| a.invocation.metadata_hash.cmp(&b.invocation.metadata_hash))
269 .then_with(|| a.timing.index.cmp(&b.timing.index))
270 });
271
272 let mut diagnostics: Vec<Diagnostic> = Vec::new();
273 let mut builder = GraphBuilder::with_capacity(assembled.len());
274 let mut matched_by = Vec::with_capacity(assembled.len());
275 let mut ids = Vec::with_capacity(assembled.len());
276
277 for entry in &assembled {
278 let metadata_at = if entry.invocation.pipelined {
281 entry.timing.metadata_at
282 } else {
283 None
284 };
285 let id = builder.add_unit(Unit {
286 package: entry.timing.package.clone(),
287 version: entry.timing.version.clone(),
288 target: entry.timing.target.label().to_owned(),
289 kind: entry.invocation.kind,
290 total: entry.timing.duration,
291 metadata_at,
292 requires_full_closure: entry.invocation.requires_full_closure,
293 })?;
294 ids.push(id);
295 matched_by.push(entry.method);
296 }
297
298 add_dependency_edges(&assembled, &ids, &mut builder, &mut diagnostics)?;
299 add_build_script_edges(&assembled, &ids, &mut builder, &mut diagnostics)?;
300
301 let graph = builder.build()?;
302 let unblocked = unblocked_pairs(&assembled, &ids);
303 report_inexact_matches(&matched_by, &mut diagnostics);
304
305 Ok(BuildInput {
306 graph,
307 build: meta(report),
308 matched_by,
309 unblocked,
310 diagnostics,
311 })
312}
313
314fn add_dependency_edges(
316 assembled: &[Assembled<'_>],
317 ids: &[UnitId],
318 builder: &mut GraphBuilder,
319 diagnostics: &mut Vec<Diagnostic>,
320) -> Result<(), ParseError> {
321 let mut by_artifact: BTreeMap<&str, UnitId> = BTreeMap::new();
322 for (entry, id) in assembled.iter().zip(ids.iter()) {
323 if let Some(hash) = &entry.invocation.extra_filename {
324 by_artifact.insert(hash.as_str(), *id);
325 }
326 }
327
328 for (entry, consumer) in assembled.iter().zip(ids.iter()) {
329 for dependency in &entry.invocation.externs {
330 let Some(hash) = &dependency.producer else {
331 diagnostics.push(Diagnostic {
332 severity: Severity::Warning,
333 code: "extern-without-artifact-hash",
334 message: format!(
335 "{} names `{}` through an artifact with no compilation hash, so it is not \
336 one of this build's units and no edge was added for it",
337 label(entry),
338 dependency.name
339 ),
340 });
341 continue;
342 };
343 let Some(producer) = by_artifact.get(hash.as_str()).copied() else {
344 return Err(ParseError::UnresolvedDependency {
345 consumer: Box::new(describe(entry)),
346 dependency: dependency.name.clone(),
347 producer: hash.clone(),
348 });
349 };
350 let kind = downgrade(
351 dependency.edge,
352 producer,
353 assembled,
354 ids,
355 entry,
356 diagnostics,
357 );
358 builder.add_edge(producer, *consumer, kind)?;
359 }
360 }
361 Ok(())
362}
363
364fn downgrade(
368 kind: EdgeKind,
369 producer: UnitId,
370 assembled: &[Assembled<'_>],
371 ids: &[UnitId],
372 consumer: &Assembled<'_>,
373 diagnostics: &mut Vec<Diagnostic>,
374) -> EdgeKind {
375 if kind != EdgeKind::Metadata {
376 return kind;
377 }
378 let emits = ids
379 .iter()
380 .position(|id| *id == producer)
381 .and_then(|at| assembled.get(at))
382 .is_some_and(|entry| entry.invocation.pipelined && entry.timing.metadata_at.is_some());
383 if emits {
384 return EdgeKind::Metadata;
385 }
386 diagnostics.push(Diagnostic {
387 severity: Severity::Warning,
388 code: "metadata-edge-without-metadata",
389 message: format!(
390 "{} was given a dependency as metadata, but the timing report records no metadata \
391 moment for it, so the edge was treated as needing the whole dependency; \
392 the critical path this produces is an upper bound rather than an estimate",
393 label(consumer)
394 ),
395 });
396 EdgeKind::Full
397}
398
399fn add_build_script_edges(
402 assembled: &[Assembled<'_>],
403 ids: &[UnitId],
404 builder: &mut GraphBuilder,
405 diagnostics: &mut Vec<Diagnostic>,
406) -> Result<(), ParseError> {
407 let mut by_artifact: BTreeMap<&str, UnitId> = BTreeMap::new();
408 for (entry, id) in assembled.iter().zip(ids.iter()) {
409 if let Some(hash) = &entry.invocation.extra_filename {
410 by_artifact.insert(hash.as_str(), *id);
411 }
412 }
413
414 for (entry, run) in assembled.iter().zip(ids.iter()) {
415 if entry.invocation.role != Role::BuildScriptRun {
416 continue;
417 }
418 let Some(hash) = &entry.invocation.run_artifact else {
422 return Err(ParseError::UnresolvedDependency {
423 consumer: Box::new(describe(entry)),
424 dependency: "its compiled build script".to_owned(),
425 producer: "<no compilation hash in the execution path>".to_owned(),
426 });
427 };
428 let Some(compile) = by_artifact.get(hash.as_str()).copied() else {
429 return Err(ParseError::UnresolvedDependency {
430 consumer: Box::new(describe(entry)),
431 dependency: "its compiled build script".to_owned(),
432 producer: hash.clone(),
433 });
434 };
435 builder.add_edge(compile, *run, EdgeKind::Full)?;
436
437 let mut dependents = package_units(assembled, ids, entry, true);
442 if dependents.is_empty() {
443 dependents = package_units(assembled, ids, entry, false);
444 if !dependents.is_empty() {
445 diagnostics.push(Diagnostic {
446 severity: Severity::Warning,
447 code: "build-script-instance-ambiguous",
448 message: format!(
449 "the build script of {} shares no feature set with any of that package's \
450 compilations, so every one of them was made to wait for it; \
451 if the package is built twice with different features this is stricter \
452 than the real build",
453 label(entry)
454 ),
455 });
456 }
457 }
458 for dependent in dependents {
459 builder.add_edge(*run, dependent, EdgeKind::Full)?;
460 }
461 }
462 Ok(())
463}
464
465fn package_units(
467 assembled: &[Assembled<'_>],
468 ids: &[UnitId],
469 run: &Assembled<'_>,
470 match_features: bool,
471) -> Vec<UnitId> {
472 assembled
473 .iter()
474 .zip(ids.iter())
475 .filter(|(entry, _)| {
476 entry.invocation.kind != UnitKind::BuildScriptCompile
477 && entry.invocation.kind != UnitKind::BuildScriptRun
478 && entry.timing.package == run.timing.package
479 && entry.timing.version == run.timing.version
480 && (!match_features || entry.timing.features == run.timing.features)
481 })
482 .map(|(_, id)| *id)
483 .collect()
484}
485
486fn unblocked_pairs(assembled: &[Assembled<'_>], ids: &[UnitId]) -> Vec<UnblockedPair> {
488 let mut by_index: BTreeMap<usize, UnitId> = BTreeMap::new();
489 for (entry, id) in assembled.iter().zip(ids.iter()) {
490 by_index.insert(entry.timing.index, *id);
491 }
492
493 let mut pairs = Vec::new();
494 for (entry, producer) in assembled.iter().zip(ids.iter()) {
495 for (indices, source) in [
496 (&entry.timing.unblocked, UnblockedSource::Completion),
497 (&entry.timing.unblocked_rmeta, UnblockedSource::Metadata),
498 ] {
499 for index in indices.iter() {
500 if let Some(consumer) = by_index.get(index).copied() {
501 pairs.push(UnblockedPair {
502 producer: *producer,
503 consumer,
504 source,
505 });
506 }
507 }
508 }
509 }
510 pairs.sort();
511 pairs.dedup();
512 pairs
513}
514
515fn report_inexact_matches(methods: &[MatchMethod], diagnostics: &mut Vec<Diagnostic>) {
516 let ordered = methods.iter().filter(|m| **m == MatchMethod::StartOrder);
517 let count = ordered.count();
518 if count > 0 {
519 diagnostics.push(Diagnostic {
520 severity: Severity::Warning,
521 code: "units-matched-by-order",
522 message: format!(
523 "{count} unit(s) could not be told apart from another unit of the same package, \
524 version and feature set, so each was paired with a timing entry by start order; \
525 they differ only in weight, and swapping two of them would move work between two \
526 identical compilations"
527 ),
528 });
529 }
530}
531
532fn meta(report: &TimingReport) -> BuildMeta {
533 BuildMeta {
534 cargo_version: None,
535 rustc_version: report.rustc_version.clone(),
536 host: report.host.clone(),
537 target: report.target.clone(),
538 profile: report.profile.clone(),
539 jobs: report.jobs,
540 cpus: report.cpus,
541 observed_max_concurrency: report.max_concurrency,
542 units_total: report.total_units,
543 units_fresh: report.fresh_units,
544 compilation_span: report.compilation_span(),
545 reported_total: report.reported_total,
546 excluded_prefix: report.excluded_prefix(),
547 targets: report.targets.clone(),
548 build_start: report.build_start.clone(),
549 }
550}
551
552fn label(entry: &Assembled<'_>) -> String {
553 format!(
554 "{} {} ({})",
555 entry.timing.package,
556 entry.timing.version,
557 entry.timing.target.label()
558 )
559}
560
561fn describe(entry: &Assembled<'_>) -> UnitDescription {
562 UnitDescription {
563 package: entry.timing.package.clone(),
564 version: entry.timing.version.clone(),
565 target: entry.timing.target.label().to_owned(),
566 position: entry.timing.position.saturating_add(1),
567 }
568}