1mod manifest;
4
5pub use manifest::{
6 MODULE_API_VERSION, ModuleArtifact, ModuleManifest, module_namespace, validate_manifest,
7 validate_relative_path,
8};
9
10use std::collections::{BTreeMap, BTreeSet};
11use std::error::Error;
12use std::fmt;
13
14#[derive(Clone, Debug, PartialEq, Eq)]
15pub struct ResolvedModule {
16 pub manifest: ModuleManifest,
17 pub startup_order: u32,
18}
19
20#[derive(Clone, Debug, PartialEq, Eq)]
21pub enum ModuleGraphError {
22 InvalidManifest {
23 module: String,
24 message: String,
25 },
26 DuplicateModule {
27 module: String,
28 },
29 DuplicateProvider {
30 capability: String,
31 first: String,
32 second: String,
33 },
34 MissingCapability {
35 module: String,
36 capability: String,
37 },
38 DependencyCycle {
39 modules: Vec<String>,
40 },
41}
42
43impl fmt::Display for ModuleGraphError {
44 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
45 match self {
46 Self::InvalidManifest { module, message } => {
47 write!(
48 formatter,
49 "module `{module}` has an invalid manifest: {message}"
50 )
51 }
52 Self::DuplicateModule { module } => {
53 write!(formatter, "module `{module}` is declared more than once")
54 }
55 Self::DuplicateProvider {
56 capability,
57 first,
58 second,
59 } => write!(
60 formatter,
61 "capability `{capability}` has multiple providers: `{first}` and `{second}`"
62 ),
63 Self::MissingCapability { module, capability } => write!(
64 formatter,
65 "module `{module}` requires missing capability `{capability}`"
66 ),
67 Self::DependencyCycle { modules } => {
68 write!(
69 formatter,
70 "module dependency cycle includes {}",
71 modules.join(", ")
72 )
73 }
74 }
75 }
76}
77
78impl Error for ModuleGraphError {}
79
80pub fn resolve_modules(
92 manifests: impl IntoIterator<Item = ModuleManifest>,
93) -> Result<Vec<ResolvedModule>, ModuleGraphError> {
94 let mut modules = BTreeMap::new();
95 for mut manifest in manifests {
96 validate_manifest(&mut manifest)?;
97 let name = manifest.name.clone();
98 if modules.insert(name.clone(), manifest).is_some() {
99 return Err(ModuleGraphError::DuplicateModule { module: name });
100 }
101 }
102
103 let providers = capability_providers(&modules)?;
104 let mut dependencies = BTreeMap::<String, BTreeSet<String>>::new();
105 let mut consumers = BTreeMap::<String, BTreeSet<String>>::new();
106 for (name, manifest) in &modules {
107 let required = manifest
108 .requires
109 .iter()
110 .map(|capability| {
111 providers.get(capability).cloned().ok_or_else(|| {
112 ModuleGraphError::MissingCapability {
113 module: name.clone(),
114 capability: capability.clone(),
115 }
116 })
117 })
118 .collect::<Result<BTreeSet<_>, _>>()?;
119 for provider in required.iter().filter(|provider| *provider != name) {
120 consumers
121 .entry(provider.clone())
122 .or_default()
123 .insert(name.clone());
124 }
125 dependencies.insert(
126 name.clone(),
127 required
128 .into_iter()
129 .filter(|provider| provider != name)
130 .collect(),
131 );
132 }
133
134 let mut ready = dependencies
135 .iter()
136 .filter_map(|(name, required)| required.is_empty().then_some(name.clone()))
137 .collect::<BTreeSet<_>>();
138 let mut ordered = Vec::with_capacity(modules.len());
139 while let Some(name) = ready.pop_first() {
140 let manifest = modules.get(&name).expect("ready module exists").clone();
141 let startup_order =
142 u32::try_from(ordered.len()).map_err(|_| ModuleGraphError::InvalidManifest {
143 module: name.clone(),
144 message: "too many modules to represent startup order".to_owned(),
145 })?;
146 ordered.push(ResolvedModule {
147 manifest,
148 startup_order,
149 });
150 for consumer in consumers.get(&name).into_iter().flatten() {
151 let required = dependencies
152 .get_mut(consumer)
153 .expect("consumer dependency set exists");
154 required.remove(&name);
155 if required.is_empty() {
156 ready.insert(consumer.clone());
157 }
158 }
159 }
160
161 if ordered.len() != modules.len() {
162 let resolved = ordered
163 .iter()
164 .map(|module| module.manifest.name.as_str())
165 .collect::<BTreeSet<_>>();
166 let cycle = modules
167 .keys()
168 .filter(|name| !resolved.contains(name.as_str()))
169 .cloned()
170 .collect();
171 return Err(ModuleGraphError::DependencyCycle { modules: cycle });
172 }
173 Ok(ordered)
174}
175
176fn capability_providers(
177 modules: &BTreeMap<String, ModuleManifest>,
178) -> Result<BTreeMap<String, String>, ModuleGraphError> {
179 let mut providers = BTreeMap::new();
180 for (name, manifest) in modules {
181 for capability in &manifest.provides {
182 if let Some(first) = providers.insert(capability.clone(), name.clone()) {
183 return Err(ModuleGraphError::DuplicateProvider {
184 capability: capability.clone(),
185 first,
186 second: name.clone(),
187 });
188 }
189 }
190 }
191 Ok(providers)
192}
193
194#[cfg(test)]
195mod tests {
196 use super::{ModuleGraphError, ModuleManifest, resolve_modules};
197
198 fn manifest(name: &str, provides: &[&str], requires: &[&str]) -> ModuleManifest {
199 ModuleManifest::new(
200 name,
201 "1",
202 provides.iter().copied(),
203 requires.iter().copied(),
204 )
205 }
206
207 #[test]
208 fn resolves_provider_before_consumer_deterministically() {
209 let resolved = resolve_modules([
210 manifest("audit", &["audit.events"], &["auth.identity"]),
211 manifest("mail", &["mail.delivery"], &[]),
212 manifest("auth", &["auth.identity"], &[]),
213 ])
214 .unwrap();
215 let names = resolved
216 .iter()
217 .map(|module| module.manifest.name.as_str())
218 .collect::<Vec<_>>();
219 assert_eq!(names, ["auth", "audit", "mail"]);
220 assert_eq!(resolved[1].startup_order, 1);
221 }
222
223 #[test]
224 fn rejects_missing_capabilities() {
225 let error = resolve_modules([manifest("tenant", &["tenant.context"], &["auth.identity"])])
226 .unwrap_err();
227 assert!(matches!(
228 error,
229 ModuleGraphError::MissingCapability { capability, .. }
230 if capability == "auth.identity"
231 ));
232 }
233
234 #[test]
235 fn rejects_invalid_and_duplicate_manifests() {
236 let invalid = resolve_modules([manifest("", &["identity"], &[])]).unwrap_err();
237 assert!(matches!(invalid, ModuleGraphError::InvalidManifest { .. }));
238
239 let duplicate = resolve_modules([
240 manifest("auth", &["identity"], &[]),
241 manifest("auth", &["roles"], &[]),
242 ])
243 .unwrap_err();
244 assert_eq!(
245 duplicate,
246 ModuleGraphError::DuplicateModule {
247 module: "auth".to_owned()
248 }
249 );
250 }
251
252 #[test]
253 fn rejects_duplicate_providers() {
254 let error = resolve_modules([
255 manifest("first", &["storage"], &[]),
256 manifest("second", &["storage"], &[]),
257 ])
258 .unwrap_err();
259 assert!(matches!(error, ModuleGraphError::DuplicateProvider { .. }));
260 }
261
262 #[test]
263 fn rejects_dependency_cycles() {
264 let error = resolve_modules([
265 manifest("first", &["first"], &["second"]),
266 manifest("second", &["second"], &["first"]),
267 ])
268 .unwrap_err();
269 assert_eq!(
270 error,
271 ModuleGraphError::DependencyCycle {
272 modules: vec!["first".to_owned(), "second".to_owned()]
273 }
274 );
275 }
276}