dmsc/core/
module_sorter.rs

1//! Copyright © 2025-2026 Wenze Wei. All Rights Reserved.
2//!
3//! This file is part of DMSC.
4//! The DMSC project belongs to the Dunimd Team.
5//!
6//! Licensed under the Apache License, Version 2.0 (the "License");
7//! You may not use this file except in compliance with the License.
8//! You may obtain a copy of the License at
9//!
10//!     http://www.apache.org/licenses/LICENSE-2.0
11//!
12//! Unless required by applicable law or agreed to in writing, software
13//! distributed under the License is distributed on an "AS IS" BASIS,
14//! WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15//! See the License for the specific language governing permissions and
16//! limitations under the License.
17
18//! # Module Sorter
19//!
20//! This module provides functionality for sorting modules based on their dependencies and priorities.
21//! It uses topological sort to handle dependencies and sorts modules by priority within the same dependency level.
22//!
23//! ## Key Components
24//!
25//! - **sort_modules**: Function that performs topological sorting of modules
26//!
27//! ## Design Principles
28//!
29//! 1. **Topological Sort**: Uses Kahn's algorithm for dependency resolution
30//! 2. **Priority-Based Ordering**: Modules with higher priority execute first
31//! 3. **Circular Dependency Detection**: Returns error if circular dependencies exist
32//! 4. **Missing Dependency Detection**: Returns error if a dependency is not found
33//!
34//! ## Usage Example
35//!
36//! ```rust
37//! use dmsc::core::module_sorter::sort_modules;
38//!
39//! let modules = vec![...]; // Module slots
40//! let sorted = sort_modules(modules)?;
41//! ```
42
43use crate::core::DMSCResult;
44use std::collections::HashMap;
45use super::module_types::ModuleSlot;
46
47/// Sort modules based on dependencies and priority
48/// Uses topological sort to handle dependencies, and sorts by priority within the same dependency level
49pub(crate) fn sort_modules(modules: Vec<ModuleSlot>) -> DMSCResult<Vec<ModuleSlot>> {
50    let mut modules = modules;
51    let mut result: Vec<ModuleSlot> = Vec::with_capacity(modules.len());
52    
53    // Loop until all modules are processed
54    while !modules.is_empty() {
55        // Create a map from module name to current index
56        let name_to_index: HashMap<&str, usize> = modules
57            .iter()
58            .enumerate()
59            .map(|(i, slot)| (slot.module.name(), i))
60            .collect();
61        
62        // Calculate in-degree for each module
63        let mut in_degree: Vec<usize> = vec![0; modules.len()];
64        
65        for (i, slot) in modules.iter().enumerate() {
66            let dependencies = slot.module.dependencies();
67            for dep_name in dependencies {
68                // Check if dependency exists in remaining modules
69                if let Some(_dep_index) = name_to_index.get(dep_name) {
70                    // Dependency exists, so this module has in-degree
71                    in_degree[i] += 1;
72                } else {
73                    // Dependency not found, check if it's already in result
74                    let dep_in_result = result.iter().any(|slot| slot.module.name() == dep_name);
75                    if !dep_in_result {
76                        return Err(crate::core::DMSCError::MissingDependency { 
77                            module_name: slot.module.name().to_string(), 
78                            dependency: dep_name.to_string() 
79                        });
80                    }
81                }
82            }
83        }
84        
85        // Collect all modules with in-degree 0
86        let mut zero_in_degree: Vec<(i32, usize)> = in_degree
87            .iter()
88            .enumerate()
89            .filter(|&(_, &degree)| degree == 0)
90            .map(|(i, _)| (modules[i].module.priority(), i))
91            .collect();
92        
93        // If no modules with in-degree 0, we have a circular dependency
94        if zero_in_degree.is_empty() {
95            return Err(crate::core::DMSCError::CircularDependency { 
96                modules: modules.iter().map(|slot| slot.module.name().to_string()).collect() 
97            });
98        }
99        
100        // Sort modules with in-degree 0 by priority (descending), then by index (ascending)
101        zero_in_degree.sort_by(|a, b| {
102            // Higher priority comes first, and if priorities are equal, lower index comes first
103            a.0.cmp(&b.0).reverse().then_with(|| a.1.cmp(&b.1))
104        });
105        
106        // Process modules with in-degree 0 in sorted order
107        // We need to collect indices in a list and process them in reverse order
108        // to avoid index shifting issues when removing elements
109        let mut indices_to_remove: Vec<usize> = zero_in_degree
110            .iter()
111            .map(|&(_, i)| i)
112            .collect();
113        
114        // Sort indices in descending order to avoid index shifting
115        indices_to_remove.sort_by(|a, b| b.cmp(a));
116        
117        // Add modules to result in the correct order
118        let mut added_modules: Vec<ModuleSlot> = Vec::with_capacity(indices_to_remove.len());
119        for &i in &indices_to_remove {
120            let module = modules.swap_remove(i);
121            added_modules.push(module);
122        }
123        
124        // Reverse the added modules to get the original sorted order
125        added_modules.reverse();
126        result.extend(added_modules);
127    }
128    
129    Ok(result)
130}
dmsc/core/module_sorter.rs

dmsc/core/
module_sorter.rs
