serenade_kernel/
registry.rs

1//! Ordered collection of bundles with dependency sorting.
2
3use std::cmp::Reverse;
4use std::collections::{BinaryHeap, HashMap};
5
6use crate::{BundleInterface, KernelError};
7
8/// Holds bundles until the kernel compiles them.
9///
10/// Registration order is preserved when there are no dependencies; otherwise
11/// [`Self::sorted`] returns a topologically sorted list (dependencies first).
12#[derive(Default)]
13pub struct BundleRegistry {
14    bundles: Vec<Box<dyn BundleInterface>>,
15}
16
17impl BundleRegistry {
18    /// Empty registry.
19    #[must_use]
20    pub fn new() -> Self {
21        Self::default()
22    }
23
24    /// Registers a bundle. Names must be unique.
25    ///
26    /// # Errors
27    ///
28    /// Returns [`KernelError::DuplicateBundle`] when `bundle.name()` is already present.
29    pub fn register(&mut self, bundle: impl BundleInterface + 'static) -> Result<(), KernelError> {
30        let name = bundle.name();
31        if self.bundles.iter().any(|existing| existing.name() == name) {
32            return Err(KernelError::DuplicateBundle(name));
33        }
34        self.bundles.push(Box::new(bundle));
35        Ok(())
36    }
37
38    /// Registered names in registration order (before sorting).
39    #[must_use]
40    pub fn names(&self) -> Vec<&'static str> {
41        self.bundles.iter().map(|bundle| bundle.name()).collect()
42    }
43
44    /// Number of registered bundles.
45    #[must_use]
46    pub fn len(&self) -> usize {
47        self.bundles.len()
48    }
49
50    /// Whether no bundles are registered.
51    #[must_use]
52    pub fn is_empty(&self) -> bool {
53        self.bundles.is_empty()
54    }
55
56    /// Returns bundles in dependency order (dependencies before dependents).
57    ///
58    /// Among ready nodes, lower registration index wins (stable).
59    ///
60    /// # Errors
61    ///
62    /// - [`KernelError::UnknownBundleDependency`] when a dependency was never registered.
63    /// - [`KernelError::CyclicBundleDependency`] when the graph has a cycle.
64    ///
65    /// # Panics
66    ///
67    /// Panics if a sorted index does not map to a registered bundle (internal invariant).
68    pub fn sorted(self) -> Result<Vec<Box<dyn BundleInterface>>, KernelError> {
69        let order = topological_order(&self.bundles)?;
70        let mut slots: Vec<Option<Box<dyn BundleInterface>>> =
71            self.bundles.into_iter().map(Some).collect();
72        let mut sorted = Vec::with_capacity(order.len());
73        for index in order {
74            // `topological_order` returns each index exactly once when it succeeds.
75            let bundle = slots[index]
76                .take()
77                .expect("sorted indexes each registered bundle once");
78            sorted.push(bundle);
79        }
80        Ok(sorted)
81    }
82}
83
84fn topological_order(bundles: &[Box<dyn BundleInterface>]) -> Result<Vec<usize>, KernelError> {
85    let n = bundles.len();
86    let mut index_by_name = HashMap::with_capacity(n);
87    for (index, bundle) in bundles.iter().enumerate() {
88        index_by_name.insert(bundle.name(), index);
89    }
90
91    let mut indegree = vec![0_usize; n];
92    let mut adjacency: Vec<Vec<usize>> = vec![Vec::new(); n];
93
94    for (index, bundle) in bundles.iter().enumerate() {
95        for dependency in bundle.dependencies() {
96            let Some(&dep_index) = index_by_name.get(dependency) else {
97                return Err(KernelError::UnknownBundleDependency {
98                    bundle: bundle.name(),
99                    dependency,
100                });
101            };
102            adjacency[dep_index].push(index);
103            indegree[index] += 1;
104        }
105    }
106
107    let mut ready: BinaryHeap<Reverse<usize>> = indegree
108        .iter()
109        .enumerate()
110        .filter_map(|(index, degree)| (*degree == 0).then_some(Reverse(index)))
111        .collect();
112
113    let mut order = Vec::with_capacity(n);
114    while let Some(Reverse(index)) = ready.pop() {
115        order.push(index);
116        for &dependent in &adjacency[index] {
117            indegree[dependent] -= 1;
118            if indegree[dependent] == 0 {
119                ready.push(Reverse(dependent));
120            }
121        }
122    }
123
124    if order.len() != n {
125        let cycle_member = bundles
126            .iter()
127            .enumerate()
128            .find_map(|(index, bundle)| (indegree[index] > 0).then_some(bundle.name()))
129            .unwrap_or("unknown");
130        return Err(KernelError::CyclicBundleDependency(cycle_member));
131    }
132    Ok(order)
133}
serenade_kernel/registry.rs

serenade_kernel/
registry.rs
