Skip to main content

appstruct_module_sdk/
lib.rs

1//! Stable module manifests and deterministic capability graph resolution.
2
3mod 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
80/// Resolve manifests into a stable provider-before-consumer startup order.
81///
82/// # Errors
83///
84/// Returns an error for invalid manifests, duplicate declarations or providers,
85/// missing required capabilities, and dependency cycles.
86///
87/// # Panics
88///
89/// This function does not panic for a valid manifest set. Internal lookups use
90/// assertions to defend the graph invariants established during resolution.
91pub 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}