1use std::collections::{BTreeMap, BTreeSet};
2use std::path::PathBuf;
3
4use callisto_format::Versioning;
5use callisto_model::{
6 BumpReason, ConfigKey, Coverage, DepEdge, DepKind, DepSpec, Diagnostic, DiagnosticCode,
7 DiagnosticSeverity, Ecosystem, GrammarMismatch, PackageId, Severity, Version,
8};
9
10use crate::config::GroupTable;
11use crate::config::{CascadeConfig, CascadeMode};
12use crate::error::GraphError;
13use crate::resolver::DependencyResolver;
14
15#[derive(Clone, Debug, PartialEq, Eq)]
16pub struct CascadeDecision {
17 pub severity: Severity,
18 pub rewrite: bool,
19 pub governed_by: Option<ConfigKey>,
20 pub escalated: bool,
21 pub unknown_coverage: bool,
22}
23
24pub fn cascade_action(
25 kind: DepKind,
26 coverage: Coverage,
27 _source: Severity,
28 cfg: &CascadeConfig,
29) -> CascadeDecision {
30 use Coverage::*;
31 use DepKind::*;
32
33 let effective = match (cfg.mode, coverage) {
34 (CascadeMode::Always, _) => DoesNotCover,
35 (CascadeMode::OutOfRange, Covers) => Covers,
36 (CascadeMode::OutOfRange, DoesNotCover) => DoesNotCover,
37 (CascadeMode::OutOfRange, Unknown) => Covers,
38 };
39
40 let rewrite = matches!(coverage, DoesNotCover);
41
42 let (severity, governed_by, escalated) = match (kind, effective) {
43 (Runtime | Optional | Build, Covers) => (Severity::None, None, false),
44 (Runtime | Optional | Build, DoesNotCover) => (
45 cfg.bump_severity.as_severity(),
46 Some(ConfigKey::CASCADE_BUMP_SEVERITY),
47 false,
48 ),
49 (Peer, Covers) => (Severity::None, None, false),
50 (Peer, DoesNotCover) if cfg.peer_escalation && matches!(coverage, DoesNotCover) => (
51 Severity::Major,
52 Some(ConfigKey::CASCADE_PEER_ESCALATION),
53 true,
54 ),
55 (Peer, DoesNotCover) => (
56 cfg.bump_severity.as_severity(),
57 Some(ConfigKey::CASCADE_BUMP_SEVERITY),
58 false,
59 ),
60 (Dev, _) => (Severity::None, None, false),
61 _ => (Severity::None, None, false),
62 };
63
64 let governed_by = match (cfg.mode, coverage, severity) {
65 (CascadeMode::Always, Covers | Unknown, s) if s != Severity::None => {
66 Some(ConfigKey::CASCADE_MODE)
67 }
68 _ => governed_by,
69 };
70
71 CascadeDecision {
72 severity,
73 rewrite,
74 governed_by,
75 escalated,
76 unknown_coverage: matches!(coverage, Unknown),
77 }
78}
79
80pub fn coverage(spec: &DepSpec, new: &Version) -> Result<Coverage, GrammarMismatch> {
81 match spec {
82 DepSpec::Exact(v) => {
83 if v == new {
84 Ok(Coverage::Covers)
85 } else {
86 Ok(Coverage::DoesNotCover)
87 }
88 }
89 DepSpec::CargoBare(v) => {
90 if caret_covers(v, new)? {
91 Ok(Coverage::Covers)
92 } else {
93 Ok(Coverage::DoesNotCover)
94 }
95 }
96 DepSpec::Range(req, _) => {
97 if req.matches(new)? {
98 Ok(Coverage::Covers)
99 } else {
100 Ok(Coverage::DoesNotCover)
101 }
102 }
103 DepSpec::Workspace(_) => Ok(Coverage::Covers),
104 DepSpec::Catalog(_) | DepSpec::Opaque(_) => Ok(Coverage::Unknown),
105 }
106}
107
108pub(crate) fn caret_covers(cur: &Version, new: &Version) -> Result<bool, GrammarMismatch> {
109 let cmp = Version::compare(new, cur)?;
110 if cmp.is_lt() {
111 return Ok(false);
112 }
113 let cur_maj = cur.major().unwrap_or(0);
114 let cur_min = cur.minor().unwrap_or(0);
115 let new_maj = new.major().unwrap_or(0);
116 let new_min = new.minor().unwrap_or(0);
117
118 if cur_maj > 0 {
119 Ok(new_maj == cur_maj)
120 } else if cur_min > 0 {
121 Ok(new_maj == 0 && new_min == cur_min)
122 } else {
123 Ok(new == cur)
124 }
125}
126
127pub struct CascadeInput<'a, D: DependencyResolver> {
128 pub graph: &'a D,
129 pub groups: &'a GroupTable,
130 pub cfg: &'a CascadeConfig,
131 pub seed: &'a BTreeMap<PackageId, Severity>,
132 pub reasons: &'a BTreeMap<PackageId, BumpReason>,
133 pub named_by: &'a BTreeMap<PackageId, crate::aggregate::NamedBy>,
134 pub base: &'a BTreeMap<PackageId, Version>,
135 pub pre: Option<&'a callisto_format::PreState>,
136}
137
138#[derive(Clone, Debug, Default)]
139pub struct CascadeOutcome {
140 pub severities: BTreeMap<PackageId, Severity>,
141 pub targets: BTreeMap<PackageId, Version>,
142 pub reasons: BTreeMap<PackageId, BumpReason>,
143 pub governed_by: BTreeMap<PackageId, ConfigKey>,
144 pub rewrites: BTreeMap<RewriteKey, SpecRewrite>,
145 pub diagnostics: Vec<Diagnostic>,
146 pub iterations: usize,
147}
148
149pub trait CascadeSolver<D: DependencyResolver> {
151 fn solve_cascade(&self, input: CascadeInput<'_, D>) -> Result<CascadeOutcome, GraphError>;
152}
153
154pub fn run_cascade<D: DependencyResolver>(
155 input: CascadeInput<'_, D>,
156) -> Result<CascadeOutcome, GraphError> {
157 solve_cascade(input)
158}
159
160pub fn solve_cascade<D: DependencyResolver>(
161 input: CascadeInput<'_, D>,
162) -> Result<CascadeOutcome, GraphError> {
163 let mut out = CascadeOutcome {
164 severities: input.seed.clone(),
165 reasons: input.reasons.clone(),
166 ..Default::default()
167 };
168
169 for (id, &sev) in input.seed {
170 let t = bump_target(id, sev, &input)?;
171 out.targets.insert(id.clone(), t);
172 }
173
174 let mut worklist: BTreeSet<PackageId> = out.targets.keys().cloned().collect();
175 let mut iterations = 0;
176 let bound = convergence_bound(input.graph.packages().count());
177
178 let mut changed = true;
179 while changed {
180 changed = false;
181
182 while let Some(pkg) = worklist.pop_first() {
183 iterations += 1;
184 if iterations > bound {
185 return Err(GraphError::CascadeNotConverged { iterations });
186 }
187
188 let new_version = out.targets[&pkg].clone();
189 let src_sev = out.severities[&pkg];
190
191 let dependents: Vec<DepEdge> = input.graph.dependents_of(&pkg).cloned().collect();
192 for edge in dependents {
193 let cov = coverage(&edge.spec, &new_version).map_err(|source| {
194 GraphError::GrammarMismatch {
195 from: edge.from.clone(),
196 to: edge.to.clone(),
197 source,
198 }
199 })?;
200
201 let d = cascade_action(edge.kind, cov, src_sev, input.cfg);
202
203 if d.unknown_coverage && !matches!(edge.spec, DepSpec::Opaque(_)) {
204 let code = match edge.spec {
205 DepSpec::Catalog(_) => DiagnosticCode::CatalogSpecNotRewritten,
206 _ => DiagnosticCode::RangeNotRoundTrippable,
207 };
208 out.diagnostics.push(Diagnostic {
209 code,
210 severity: DiagnosticSeverity::Warning,
211 message: format!(
212 "spec `{}` for `{}` could not be tested for coverage",
213 edge.spec.render(),
214 edge.to.display_name()
215 ),
216 package: Some(edge.from.clone()),
217 path: Some(edge.from_manifest.clone()),
218 governed_by: Some(ConfigKey::CASCADE_PRESERVE_NPM_RANGES),
219 escalated_by: None,
220 });
221 }
222
223 if d.rewrite {
224 let eco = edge.from.ecosystem().unwrap_or_else(|| {
225 if edge.from_manifest.to_string_lossy().ends_with("Cargo.toml") {
226 Ecosystem::Cargo
227 } else {
228 Ecosystem::Npm
229 }
230 });
231 match rewrite_spec(&edge.spec, &new_version, eco, input.cfg) {
232 RewriteOutcome::Rewritten(to_spec) => {
233 let key = RewriteKey {
234 target: if edge.inherited {
235 DepWriteTarget::CargoWorkspaceDependency {
236 root_manifest: edge.from_manifest.clone(),
237 }
238 } else {
239 DepWriteTarget::Manifest(edge.from_manifest.clone())
240 },
241 name: edge.to.name().to_string(),
242 kind: if edge.inherited {
243 None
244 } else {
245 Some(edge.kind)
246 },
247 };
248 out.rewrites.insert(
249 key.clone(),
250 SpecRewrite {
251 key,
252 dependency: edge.to.clone(),
253 from: edge.spec.clone(),
254 to: to_spec,
255 },
256 );
257 }
258 RewriteOutcome::LeftAlone(dg) => {
259 out.diagnostics.push(dg);
260 }
261 }
262 }
263
264 let cur_sev = out
265 .severities
266 .get(&edge.from)
267 .copied()
268 .unwrap_or(Severity::None);
269 if d.severity > cur_sev {
270 raise(
271 &edge.from,
272 d.severity,
273 &d,
274 &pkg,
275 &edge,
276 &new_version,
277 &mut out,
278 input.groups,
279 &mut worklist,
280 &input,
281 )?;
282 }
283 }
284 }
285
286 for g in input.groups.linked.values() {
288 let member_ids: Vec<PackageId> = g
289 .members(crate::config::GroupMemberKind::Package)
290 .filter_map(|m| match m {
291 crate::config::GroupMember::Package(ref id) => Some(id.clone()),
292 _ => None,
293 })
294 .collect();
295
296 let mut max_sev = Severity::None;
297 for id in &member_ids {
298 if let Some(&sev) = out.severities.get(id) {
299 max_sev = max_sev.max(sev);
300 }
301 }
302
303 if max_sev > Severity::None {
304 for id in member_ids {
305 let cur_sev = out.severities.get(&id).copied().unwrap_or(Severity::None);
306 if max_sev > cur_sev {
307 out.severities.insert(id.clone(), max_sev);
308 let target = bump_target(&id, max_sev, &input)?;
309 out.targets.insert(id.clone(), target);
310 out.reasons.insert(
311 id.clone(),
312 BumpReason::LinkedGroupUnion {
313 group: g.name.clone(),
314 },
315 );
316 worklist.insert(id.clone());
317 changed = true;
318 }
319 }
320 }
321 }
322 }
323
324 out.iterations = iterations;
325 Ok(out)
326}
327
328#[allow(dead_code)]
329pub(crate) fn calculate_bump_severity(from: &Version, to: &Version) -> Severity {
330 if to.major().unwrap_or(0) > from.major().unwrap_or(0) {
331 Severity::Major
332 } else if to.minor().unwrap_or(0) > from.minor().unwrap_or(0) {
333 Severity::Minor
334 } else if to.patch().unwrap_or(0) > from.patch().unwrap_or(0)
335 || to.is_prerelease()
336 || to != from
337 {
338 Severity::Patch
339 } else {
340 Severity::None
341 }
342}
343
344fn bump_target<D: DependencyResolver>(
345 id: &PackageId,
346 sev: Severity,
347 input: &CascadeInput<'_, D>,
348) -> Result<Version, GraphError> {
349 let base = input.base.get(id).cloned().ok_or_else(|| {
350 GraphError::Manifest(callisto_model::ManifestError::MissingField {
351 path: PathBuf::from(id.name()),
352 field: "version",
353 })
354 })?;
355 let versioning = callisto_format::SemVerVersioning;
356
357 if let Some(pre) = input.pre {
358 versioning
359 .bump_prerelease(&base, sev, &pre.tag, &base)
360 .map_err(GraphError::Bump)
361 } else {
362 versioning.bump(&base, sev).map_err(GraphError::Bump)
363 }
364}
365
366#[allow(clippy::too_many_arguments)]
367fn raise<D: DependencyResolver>(
368 pkg: &PackageId,
369 sev: Severity,
370 decision: &CascadeDecision,
371 via: &PackageId,
372 edge: &DepEdge,
373 dependency_to: &Version,
374 out: &mut CascadeOutcome,
375 groups: &GroupTable,
376 worklist: &mut BTreeSet<PackageId>,
377 input: &CascadeInput<'_, D>,
378) -> Result<bool, GraphError> {
379 let cur_sev = out.severities.get(pkg).copied().unwrap_or(Severity::None);
380 if sev <= cur_sev {
381 return Ok(false);
382 }
383
384 out.severities.insert(pkg.clone(), sev);
385
386 let new_reason = if decision.escalated {
387 BumpReason::PeerEscalation {
388 via: via.clone(),
389 spec: edge.spec.render(),
390 }
391 } else {
392 BumpReason::Cascade {
393 via: via.clone(),
394 dep_kind: edge.kind,
395 spec: edge.spec.render(),
396 dependency_to: dependency_to.clone(),
397 }
398 };
399 out.reasons.insert(pkg.clone(), new_reason);
400
401 if let Some(ref gov) = decision.governed_by {
402 out.governed_by.insert(pkg.clone(), gov.clone());
403 }
404
405 let new_t = bump_target(pkg, sev, input)?;
406 out.targets.insert(pkg.clone(), new_t);
407 worklist.insert(pkg.clone());
408
409 for sib in groups.fixed_siblings(pkg) {
410 let sib_sev = out.severities.get(sib).copied().unwrap_or(Severity::None);
411 if sev > sib_sev {
412 out.severities.insert(sib.clone(), sev);
413 out.reasons.insert(
414 sib.clone(),
415 BumpReason::FixedGroupUnion {
416 group: groups.fixed_group_of(pkg).unwrap().name.clone(),
417 },
418 );
419 let sib_t = bump_target(sib, sev, input)?;
420 out.targets.insert(sib.clone(), sib_t);
421 worklist.insert(sib.clone());
422 }
423 }
424
425 Ok(true)
426}
427
428pub(crate) fn convergence_bound(package_count: usize) -> usize {
429 4 * package_count + 1
430}
431
432#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
433pub enum DepWriteTarget {
434 Manifest(PathBuf),
435 CargoWorkspaceDependency { root_manifest: PathBuf },
436}
437
438#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
439pub struct RewriteKey {
440 pub target: DepWriteTarget,
441 pub name: String,
442 pub kind: Option<DepKind>,
443}
444
445#[derive(Clone, Debug, PartialEq, Eq)]
446pub struct SpecRewrite {
447 pub key: RewriteKey,
448 pub dependency: PackageId,
449 pub from: DepSpec,
450 pub to: DepSpec,
451}
452
453pub enum RewriteOutcome {
454 Rewritten(DepSpec),
455 LeftAlone(Diagnostic),
456}
457
458pub fn rewrite_spec(
459 original: &DepSpec,
460 new: &Version,
461 eco: Ecosystem,
462 cfg: &CascadeConfig,
463) -> RewriteOutcome {
464 if !cfg.preserve_npm_ranges && eco == Ecosystem::Npm {
465 return RewriteOutcome::Rewritten(DepSpec::Exact(new.clone()));
466 }
467
468 if let Some(rewritten) = callisto_manifests::round_trip(eco, original, new) {
469 RewriteOutcome::Rewritten(rewritten)
470 } else {
471 RewriteOutcome::LeftAlone(Diagnostic {
472 code: DiagnosticCode::RangeNotRoundTrippable,
473 severity: DiagnosticSeverity::Warning,
474 message: format!(
475 "spec `{}` could not be round-tripped toward version `{}`",
476 original.render(),
477 new.render()
478 ),
479 package: None,
480 path: None,
481 governed_by: Some(ConfigKey::CASCADE_PRESERVE_NPM_RANGES),
482 escalated_by: None,
483 })
484 }
485}