rusty_stack/core/
plan.rs

1//! Plan types and topological sorting.
2//!
3//! This module implements:
4//! - [`PlanItem`] — a component update plan item with risk tier, dependencies, etc.
5//! - [`topological_sort`] — sorts components by dependency order
6//! - [`Plan`] — a full update plan with items and summary
7
8use crate::core::types::{RiskTier, ValidationTier};
9use serde::{Deserialize, Serialize};
10use std::collections::{HashMap, HashSet};
11
12// ---------------------------------------------------------------------------
13// Plan Item
14// ---------------------------------------------------------------------------
15
16/// Input bundle for [`PlanItem::new`].
17///
18/// Groups the eight construction fields so the constructor stays well under
19/// clippy's `too_many_arguments` threshold.
20#[derive(Debug, Clone)]
21pub struct PlanItemInput {
22    /// Component ID.
23    pub component_id: String,
24    /// Currently installed version (empty if not installed).
25    pub current_version: String,
26    /// Proposed version to install.
27    pub proposed_version: String,
28    /// Validation tier of this component.
29    pub validation_tier: ValidationTier,
30    /// Whether this item is selected for apply.
31    pub selected: bool,
32    /// Human-readable rationale for this update.
33    pub rationale: String,
34    /// Component IDs this item depends on.
35    pub dependencies: Vec<String>,
36    /// Whether this component can be installed in isolation.
37    pub isolation_safe: bool,
38}
39
40/// A single item in an update plan.
41#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
42pub struct PlanItem {
43    /// Component ID.
44    pub component_id: String,
45    /// Currently installed version (empty if not installed).
46    pub current_version: String,
47    /// Proposed version to install.
48    pub proposed_version: String,
49    /// Validation tier of this component.
50    pub validation_tier: ValidationTier,
51    /// Whether this item is selected for apply.
52    pub selected: bool,
53    /// Human-readable rationale for this update.
54    pub rationale: String,
55    /// Component IDs this item depends on.
56    #[serde(default)]
57    pub dependencies: Vec<String>,
58    /// Whether this component can be installed in isolation.
59    pub isolation_safe: bool,
60    /// Risk tier (low/medium/high).
61    pub risk_tier: RiskTier,
62}
63
64impl PlanItem {
65    /// Create a new plan item.
66    pub fn new(input: PlanItemInput) -> Self {
67        Self {
68            component_id: input.component_id,
69            current_version: input.current_version,
70            proposed_version: input.proposed_version,
71            validation_tier: input.validation_tier,
72            selected: input.selected,
73            rationale: input.rationale,
74            dependencies: input.dependencies,
75            isolation_safe: input.isolation_safe,
76            risk_tier: RiskTier::Medium, // default
77        }
78    }
79}
80
81// ---------------------------------------------------------------------------
82// Topological Sort
83// ---------------------------------------------------------------------------
84
85/// Sort components topologically by their dependencies.
86///
87/// Returns a new vector with components ordered such that all dependencies
88/// of a component appear before the component itself.
89///
90/// # Arguments
91/// * `items` - Vector of plan items
92///
93/// # Returns
94/// A new vector with items in topological order.
95///
96/// # Panics
97/// Panics if a dependency cycle is detected.
98pub fn topological_sort(items: Vec<PlanItem>) -> Vec<PlanItem> {
99    // Track remaining dependencies for each node
100    let mut remaining_deps: HashMap<String, Vec<String>> = HashMap::new();
101    // Track which nodes depend on each node (for cleanup)
102    let mut dependents: HashMap<String, Vec<String>> = HashMap::new();
103    let mut all_nodes: HashSet<String> = HashSet::new();
104
105    // Initialize tracking structures
106    for item in &items {
107        all_nodes.insert(item.component_id.clone());
108        // Each node starts with all its declared dependencies
109        remaining_deps.insert(item.component_id.clone(), item.dependencies.clone());
110        // Track dependents for cleanup
111        for dep in &item.dependencies {
112            dependents
113                .entry(dep.clone())
114                .or_default()
115                .push(item.component_id.clone());
116        }
117    }
118
119    // Kahn's algorithm
120    let mut sorted_nodes = Vec::new();
121
122    // Start with nodes that have no dependencies
123    let mut queue: Vec<String> = all_nodes
124        .iter()
125        .filter(|id| remaining_deps.get(*id).is_none_or(|d| d.is_empty()))
126        .cloned()
127        .collect();
128
129    while let Some(node) = queue.pop() {
130        sorted_nodes.push(node.clone());
131
132        // Find all nodes that depend on this node
133        if let Some(dep_on_node) = dependents.get(&node) {
134            for dependent in dep_on_node.clone() {
135                // Remove this node from dependent's remaining dependencies
136                if let Some(deps) = remaining_deps.get_mut(&dependent) {
137                    deps.retain(|d| d != &node);
138                    // If all dependencies are now satisfied, add to queue
139                    if deps.is_empty() {
140                        queue.push(dependent);
141                    }
142                }
143            }
144        }
145    }
146
147    if sorted_nodes.len() != all_nodes.len() {
148        panic!("Dependency cycle detected in plan items");
149    }
150
151    // Reconstruct plan items in topological order
152    let mut item_map: HashMap<String, PlanItem> = items
153        .into_iter()
154        .map(|item| (item.component_id.clone(), item))
155        .collect();
156
157    sorted_nodes
158        .into_iter()
159        .filter_map(|id| item_map.remove(&id))
160        .collect()
161}
162
163// ---------------------------------------------------------------------------
164// Plan
165// ---------------------------------------------------------------------------
166
167/// A full update plan with items and summary.
168#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
169pub struct Plan {
170    /// Plan items in execution order.
171    pub items: Vec<PlanItem>,
172    /// Summary statistics.
173    pub summary: PlanSummary,
174}
175
176/// Summary statistics for a plan.
177#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
178pub struct PlanSummary {
179    pub total: usize,
180    pub selected: usize,
181    pub safe: usize,
182    pub guarded: usize,
183    pub candidate: usize,
184    pub experimental: usize,
185    pub blocked: usize,
186}
187
188impl Plan {
189    /// Create a new plan from items.
190    pub fn new(items: Vec<PlanItem>) -> Self {
191        let items = topological_sort(items);
192        let summary = PlanSummary::from_items(&items);
193        Self { items, summary }
194    }
195}
196
197impl PlanSummary {
198    /// Compute summary from a list of plan items.
199    pub fn from_items(items: &[PlanItem]) -> Self {
200        Self {
201            total: items.len(),
202            selected: items.iter().filter(|i| i.selected).count(),
203            safe: items
204                .iter()
205                .filter(|i| i.risk_tier == RiskTier::Low)
206                .count(),
207            guarded: items
208                .iter()
209                .filter(|i| i.risk_tier == RiskTier::Medium)
210                .count(),
211            candidate: items
212                .iter()
213                .filter(|i| i.risk_tier == RiskTier::High)
214                .count(),
215            experimental: items
216                .iter()
217                .filter(|i| i.validation_tier == ValidationTier::Experimental)
218                .count(),
219            blocked: 0, // blocked items are filtered out
220        }
221    }
222}
223
224// ===========================================================================
225// Tests
226// ===========================================================================
227
228#[cfg(test)]
229mod tests {
230    use super::*;
231    use crate::core::types::{RiskTier, ValidationTier};
232
233    // -----------------------------------------------------------------------
234    // VAL-PLAN-001: Topological sort orders dependencies before dependents
235    // -----------------------------------------------------------------------
236
237    #[test]
238    fn test_topological_sort_simple_dependency() {
239        let items = vec![
240            PlanItem::new(PlanItemInput {
241                component_id: "pytorch".into(),
242                current_version: "2.4.0".into(),
243                proposed_version: "2.5.0".into(),
244                validation_tier: ValidationTier::Validated,
245                selected: true,
246                rationale: "update pytorch".into(),
247                dependencies: vec!["rocm".to_string()],
248                isolation_safe: true,
249            }),
250            PlanItem::new(PlanItemInput {
251                component_id: "rocm".into(),
252                current_version: "7.2.0".into(),
253                proposed_version: "7.3.0".into(),
254                validation_tier: ValidationTier::Validated,
255                selected: true,
256                rationale: "update rocm".into(),
257                dependencies: vec![],
258                isolation_safe: true,
259            }),
260        ];
261
262        let sorted = topological_sort(items);
263        assert_eq!(sorted[0].component_id, "rocm");
264        assert_eq!(sorted[1].component_id, "pytorch");
265    }
266
267    #[test]
268    fn test_topological_sort_complex_dependency_chain() {
269        let items = vec![
270            PlanItem::new(PlanItemInput {
271                component_id: "pytorch".into(),
272                current_version: "2.4.0".into(),
273                proposed_version: "2.5.0".into(),
274                validation_tier: ValidationTier::Validated,
275                selected: true,
276                rationale: "update pytorch".into(),
277                dependencies: vec!["rocm".to_string()],
278                isolation_safe: true,
279            }),
280            PlanItem::new(PlanItemInput {
281                component_id: "triton".into(),
282                current_version: "3.0.0".into(),
283                proposed_version: "3.1.0".into(),
284                validation_tier: ValidationTier::Validated,
285                selected: true,
286                rationale: "update triton".into(),
287                dependencies: vec!["pytorch".to_string()],
288                isolation_safe: true,
289            }),
290            PlanItem::new(PlanItemInput {
291                component_id: "rocm".into(),
292                current_version: "7.2.0".into(),
293                proposed_version: "7.3.0".into(),
294                validation_tier: ValidationTier::Validated,
295                selected: true,
296                rationale: "update rocm".into(),
297                dependencies: vec![],
298                isolation_safe: true,
299            }),
300        ];
301
302        let sorted = topological_sort(items);
303        assert_eq!(sorted[0].component_id, "rocm");
304        assert_eq!(sorted[1].component_id, "pytorch");
305        assert_eq!(sorted[2].component_id, "triton");
306    }
307
308    #[test]
309    fn test_topological_sort_empty_dependencies() {
310        let items = vec![
311            PlanItem::new(PlanItemInput {
312                component_id: "pytorch".into(),
313                current_version: "2.4.0".into(),
314                proposed_version: "2.5.0".into(),
315                validation_tier: ValidationTier::Validated,
316                selected: true,
317                rationale: "update pytorch".into(),
318                dependencies: vec![],
319                isolation_safe: true,
320            }),
321            PlanItem::new(PlanItemInput {
322                component_id: "rocm".into(),
323                current_version: "7.2.0".into(),
324                proposed_version: "7.3.0".into(),
325                validation_tier: ValidationTier::Validated,
326                selected: true,
327                rationale: "update rocm".into(),
328                dependencies: vec![],
329                isolation_safe: true,
330            }),
331        ];
332
333        let sorted = topological_sort(items);
334        // Order of independent items is not guaranteed, but all should be present
335        let ids: HashSet<_> = sorted.iter().map(|i| i.component_id.clone()).collect();
336        assert!(ids.contains("pytorch"));
337        assert!(ids.contains("rocm"));
338    }
339
340    // -----------------------------------------------------------------------
341    // VAL-PLAN-002: Topological sort detects dependency cycles
342    // -----------------------------------------------------------------------
343
344    #[test]
345    #[should_panic(expected = "Dependency cycle detected")]
346    fn test_topological_sort_detects_cycle() {
347        let items = vec![
348            PlanItem::new(PlanItemInput {
349                component_id: "pytorch".into(),
350                current_version: "2.4.0".into(),
351                proposed_version: "2.5.0".into(),
352                validation_tier: ValidationTier::Validated,
353                selected: true,
354                rationale: "update pytorch".into(),
355                dependencies: vec!["triton".to_string()],
356                isolation_safe: true,
357            }),
358            PlanItem::new(PlanItemInput {
359                component_id: "triton".into(),
360                current_version: "3.0.0".into(),
361                proposed_version: "3.1.0".into(),
362                validation_tier: ValidationTier::Validated,
363                selected: true,
364                rationale: "update triton".into(),
365                dependencies: vec!["pytorch".to_string()],
366                isolation_safe: true,
367            }),
368        ];
369
370        topological_sort(items);
371    }
372
373    // -----------------------------------------------------------------------
374    // VAL-PLAN-003: Plan creation applies topological sort
375    // -----------------------------------------------------------------------
376
377    #[test]
378    fn test_plan_creation_applies_topological_sort() {
379        let items = vec![
380            PlanItem::new(PlanItemInput {
381                component_id: "pytorch".into(),
382                current_version: "2.4.0".into(),
383                proposed_version: "2.5.0".into(),
384                validation_tier: ValidationTier::Validated,
385                selected: true,
386                rationale: "update pytorch".into(),
387                dependencies: vec!["rocm".to_string()],
388                isolation_safe: true,
389            }),
390            PlanItem::new(PlanItemInput {
391                component_id: "rocm".into(),
392                current_version: "7.2.0".into(),
393                proposed_version: "7.3.0".into(),
394                validation_tier: ValidationTier::Validated,
395                selected: true,
396                rationale: "update rocm".into(),
397                dependencies: vec![],
398                isolation_safe: true,
399            }),
400        ];
401
402        let plan = Plan::new(items);
403        assert_eq!(plan.items[0].component_id, "rocm");
404        assert_eq!(plan.items[1].component_id, "pytorch");
405    }
406
407    // -----------------------------------------------------------------------
408    // VAL-PLAN-004: Plan summary counts are accurate
409    // -----------------------------------------------------------------------
410
411    #[test]
412    fn test_plan_summary_counts() {
413        let items = vec![
414            PlanItem {
415                component_id: "rocm".to_string(),
416                current_version: "7.2.0".to_string(),
417                proposed_version: "7.3.0".to_string(),
418                validation_tier: ValidationTier::Validated,
419                selected: true,
420                rationale: "update rocm".to_string(),
421                dependencies: vec![],
422                isolation_safe: true,
423                risk_tier: RiskTier::Low,
424            },
425            PlanItem {
426                component_id: "pytorch".to_string(),
427                current_version: "2.4.0".to_string(),
428                proposed_version: "2.5.0".to_string(),
429                validation_tier: ValidationTier::Validated,
430                selected: true,
431                rationale: "update pytorch".to_string(),
432                dependencies: vec!["rocm".to_string()],
433                isolation_safe: true,
434                risk_tier: RiskTier::Medium,
435            },
436            PlanItem {
437                component_id: "deepspeed".to_string(),
438                current_version: "".to_string(),
439                proposed_version: "0.15.0".to_string(),
440                validation_tier: ValidationTier::Experimental,
441                selected: false,
442                rationale: "new experimental".to_string(),
443                dependencies: vec!["pytorch".to_string()],
444                isolation_safe: true,
445                risk_tier: RiskTier::High,
446            },
447        ];
448
449        let plan = Plan::new(items);
450        assert_eq!(plan.summary.total, 3);
451        assert_eq!(plan.summary.selected, 2);
452        assert_eq!(plan.summary.safe, 1);
453        assert_eq!(plan.summary.guarded, 1);
454        assert_eq!(plan.summary.candidate, 1);
455        assert_eq!(plan.summary.experimental, 1);
456        assert_eq!(plan.summary.blocked, 0);
457    }
458
459    // -----------------------------------------------------------------------
460    // VAL-PLAN-005: PlanItem serde roundtrip
461    // -----------------------------------------------------------------------
462
463    #[test]
464    fn test_plan_item_serde_roundtrip() {
465        let item = PlanItem {
466            component_id: "pytorch".to_string(),
467            current_version: "2.4.0".to_string(),
468            proposed_version: "2.5.0".to_string(),
469            validation_tier: ValidationTier::Validated,
470            selected: true,
471            rationale: "update pytorch".to_string(),
472            dependencies: vec!["rocm".to_string()],
473            isolation_safe: true,
474            risk_tier: RiskTier::Medium,
475        };
476
477        let json = serde_json::to_string(&item).unwrap();
478        let back: PlanItem = serde_json::from_str(&json).unwrap();
479        assert_eq!(item, back);
480    }
481
482    // -----------------------------------------------------------------------
483    // VAL-PLAN-006: Plan serde roundtrip
484    // -----------------------------------------------------------------------
485
486    #[test]
487    fn test_plan_serde_roundtrip() {
488        let items = vec![
489            PlanItem::new(PlanItemInput {
490                component_id: "rocm".into(),
491                current_version: "7.2.0".into(),
492                proposed_version: "7.3.0".into(),
493                validation_tier: ValidationTier::Validated,
494                selected: true,
495                rationale: "update rocm".into(),
496                dependencies: vec![],
497                isolation_safe: true,
498            }),
499            PlanItem::new(PlanItemInput {
500                component_id: "pytorch".into(),
501                current_version: "2.4.0".into(),
502                proposed_version: "2.5.0".into(),
503                validation_tier: ValidationTier::Validated,
504                selected: true,
505                rationale: "update pytorch".into(),
506                dependencies: vec!["rocm".to_string()],
507                isolation_safe: true,
508            }),
509        ];
510
511        let plan = Plan::new(items);
512        let json = serde_json::to_string(&plan).unwrap();
513        let back: Plan = serde_json::from_str(&json).unwrap();
514        assert_eq!(plan.items, back.items);
515        assert_eq!(plan.summary, back.summary);
516    }
517
518    // -----------------------------------------------------------------------
519    // VAL-PLAN-007: Topological sort with dependencies from baseline manifest
520    // -----------------------------------------------------------------------
521
522    #[test]
523    fn test_topological_sort_with_llama_cpp_dependencies() {
524        let items = vec![
525            PlanItem::new(PlanItemInput {
526                component_id: "llama-cpp".into(),
527                current_version: "".into(),
528                proposed_version: "latest".into(),
529                validation_tier: ValidationTier::Experimental,
530                selected: true,
531                rationale: "install llama-cpp".into(),
532                dependencies: vec!["rocm".to_string()],
533                isolation_safe: true,
534            }),
535            PlanItem::new(PlanItemInput {
536                component_id: "rocm".into(),
537                current_version: "7.2.0".into(),
538                proposed_version: "7.3.0".into(),
539                validation_tier: ValidationTier::Validated,
540                selected: true,
541                rationale: "update rocm".into(),
542                dependencies: vec![],
543                isolation_safe: true,
544            }),
545        ];
546
547        let sorted = topological_sort(items);
548        assert_eq!(sorted[0].component_id, "rocm");
549        assert_eq!(sorted[1].component_id, "llama-cpp");
550    }
551}
rusty_stack/core/plan.rs

rusty_stack/core/
plan.rs
