nidus_core/module/
graph.rs

1use std::collections::{BTreeMap, BTreeSet, btree_map::Entry};
2
3use crate::{Module, NidusError, Result};
4
5use super::ModuleDefinition;
6
7enum VisibleProvider<'a> {
8    Unique(&'a str),
9    Ambiguous(Vec<&'a str>),
10}
11
12enum NameLookup<'a> {
13    Empty,
14    One(&'a str),
15    Many(BTreeSet<&'a str>),
16}
17
18impl<'a> NameLookup<'a> {
19    fn new(names: &'a [String]) -> Self {
20        match names {
21            [] => Self::Empty,
22            [name] => Self::One(name),
23            names => Self::Many(names.iter().map(String::as_str).collect()),
24        }
25    }
26
27    fn contains(&self, name: &str) -> bool {
28        match self {
29            Self::Empty => false,
30            Self::One(only) => *only == name,
31            Self::Many(names) => names.contains(name),
32        }
33    }
34}
35
36/// Validated graph of module definitions.
37#[derive(Debug)]
38pub struct ModuleGraph {
39    modules: BTreeMap<String, ModuleDefinition>,
40}
41
42impl ModuleGraph {
43    /// Builds and validates a module graph by recursively following typed imports.
44    pub fn from_root<M: Module>() -> Result<Self> {
45        Self::from_root_and_modules::<M, _>([])
46    }
47
48    /// Builds and validates a module graph from a root module plus explicit definitions.
49    pub fn from_root_and_modules<M, I>(modules: I) -> Result<Self>
50    where
51        M: Module,
52        I: IntoIterator<Item = ModuleDefinition>,
53    {
54        let mut definitions = Vec::new();
55        collect_recursive(M::definition(), &mut definitions, &mut BTreeSet::new());
56        for module in modules {
57            collect_recursive(module, &mut definitions, &mut BTreeSet::new());
58        }
59        Self::from_modules(definitions)
60    }
61
62    /// Builds and validates a module graph.
63    pub fn from_modules(modules: impl IntoIterator<Item = ModuleDefinition>) -> Result<Self> {
64        let span = tracing::info_span!("module.graph.validate");
65        let _entered = span.enter();
66        let mut registered = BTreeMap::new();
67        for module in modules {
68            let name = module.name.clone();
69            match registered.entry(name) {
70                Entry::Vacant(entry) => {
71                    entry.insert(module);
72                }
73                Entry::Occupied(entry) => {
74                    return Err(NidusError::DuplicateModule {
75                        module: entry.key().clone(),
76                    });
77                }
78            }
79        }
80        let graph = Self {
81            modules: registered,
82        };
83        tracing::debug!(
84            module_count = graph.modules.len(),
85            "validating module graph"
86        );
87        for module in graph.modules.values() {
88            tracing::debug!(
89                module = %module.name,
90                imports = ?module.imports,
91                providers = ?module.providers,
92                controllers = ?module.controllers,
93                exports = ?module.exports,
94                "module graph node"
95            );
96        }
97        graph.validate_local_imports_unique()?;
98        graph.validate_imports_exist()?;
99        graph.validate_acyclic()?;
100        graph.validate_local_providers_unique()?;
101        graph.validate_local_controllers_unique()?;
102        graph.validate_providers_and_controllers_disjoint()?;
103        graph.validate_exports_unique()?;
104        graph.validate_exports_are_local()?;
105        graph.validate_local_providers_do_not_conflict_with_imports()?;
106        graph.validate_visible_providers_unambiguous()?;
107        tracing::debug!(module_count = graph.modules.len(), "module graph validated");
108        Ok(graph)
109    }
110
111    /// Returns a module definition by name.
112    pub fn get(&self, name: &str) -> Option<&ModuleDefinition> {
113        self.modules.get(name)
114    }
115
116    /// Returns validated module definitions in deterministic name order.
117    pub fn modules(&self) -> impl Iterator<Item = &ModuleDefinition> {
118        self.modules.values()
119    }
120
121    fn validate_local_imports_unique(&self) -> Result<()> {
122        for module in self.modules.values() {
123            if let Some(import) = first_duplicate(&module.imports) {
124                return Err(NidusError::DuplicateModuleImport {
125                    module: module.name.clone(),
126                    import: import.to_owned(),
127                });
128            }
129        }
130        Ok(())
131    }
132
133    fn validate_imports_exist(&self) -> Result<()> {
134        for module in self.modules.values() {
135            for import in &module.imports {
136                if !self.modules.contains_key(import) {
137                    return Err(NidusError::MissingModuleImport {
138                        module: module.name.clone(),
139                        import: import.clone(),
140                    });
141                }
142            }
143        }
144        Ok(())
145    }
146
147    fn validate_acyclic(&self) -> Result<()> {
148        let mut visiting = BTreeSet::new();
149        let mut visited = BTreeSet::new();
150        let mut stack = Vec::new();
151
152        for name in self.modules.keys() {
153            self.visit(name, &mut visiting, &mut visited, &mut stack)?;
154        }
155        Ok(())
156    }
157
158    fn validate_local_providers_unique(&self) -> Result<()> {
159        for module in self.modules.values() {
160            if let Some(provider) = first_duplicate(&module.providers) {
161                return Err(NidusError::DuplicateModuleProvider {
162                    module: module.name.clone(),
163                    provider: provider.to_owned(),
164                });
165            }
166        }
167        Ok(())
168    }
169
170    fn validate_local_controllers_unique(&self) -> Result<()> {
171        for module in self.modules.values() {
172            if let Some(controller) = first_duplicate(&module.controllers) {
173                return Err(NidusError::DuplicateModuleController {
174                    module: module.name.clone(),
175                    controller: controller.to_owned(),
176                });
177            }
178        }
179        Ok(())
180    }
181
182    fn validate_providers_and_controllers_disjoint(&self) -> Result<()> {
183        for module in self.modules.values() {
184            if module.controllers.is_empty() {
185                continue;
186            }
187            let providers = NameLookup::new(&module.providers);
188            for controller in &module.controllers {
189                if providers.contains(controller) {
190                    return Err(NidusError::ModuleProviderControllerConflict {
191                        module: module.name.clone(),
192                        type_name: controller.clone(),
193                    });
194                }
195            }
196        }
197        Ok(())
198    }
199
200    fn validate_exports_unique(&self) -> Result<()> {
201        for module in self.modules.values() {
202            if let Some(export) = first_duplicate(&module.exports) {
203                return Err(NidusError::DuplicateModuleExport {
204                    module: module.name.clone(),
205                    provider: export.to_owned(),
206                });
207            }
208        }
209        Ok(())
210    }
211
212    fn validate_exports_are_local(&self) -> Result<()> {
213        for module in self.modules.values() {
214            if module.exports.is_empty() {
215                continue;
216            }
217            let providers = NameLookup::new(&module.providers);
218            for export in &module.exports {
219                if !providers.contains(export) {
220                    return Err(NidusError::MissingProviderExport {
221                        module: module.name.clone(),
222                        provider: export.clone(),
223                    });
224                }
225            }
226        }
227        Ok(())
228    }
229
230    fn validate_local_providers_do_not_conflict_with_imports(&self) -> Result<()> {
231        for module in self.modules.values() {
232            if module.imports.is_empty() {
233                continue;
234            }
235            let local_providers = NameLookup::new(&module.providers);
236            for import in &module.imports {
237                let imported = self.modules.get(import).expect("imports were validated");
238                for export in &imported.exports {
239                    if local_providers.contains(export) {
240                        return Err(NidusError::ProviderVisibilityConflict {
241                            module: module.name.clone(),
242                            provider: export.clone(),
243                            import: import.clone(),
244                        });
245                    }
246                }
247            }
248        }
249        Ok(())
250    }
251
252    fn validate_visible_providers_unambiguous(&self) -> Result<()> {
253        for module in self.modules.values() {
254            let mut visible_exports = BTreeMap::<&str, VisibleProvider<'_>>::new();
255            for import in &module.imports {
256                let imported = self.modules.get(import).expect("imports were validated");
257                for export in &imported.exports {
258                    match visible_exports.entry(export.as_str()) {
259                        Entry::Vacant(entry) => {
260                            entry.insert(VisibleProvider::Unique(import));
261                        }
262                        Entry::Occupied(mut entry) => {
263                            let visible_provider = entry.get_mut();
264                            match visible_provider {
265                                VisibleProvider::Unique(first_import) => {
266                                    *visible_provider =
267                                        VisibleProvider::Ambiguous(vec![*first_import, import]);
268                                }
269                                VisibleProvider::Ambiguous(imports) => imports.push(import),
270                            }
271                        }
272                    }
273                }
274            }
275
276            for (provider, visibility) in visible_exports {
277                if let VisibleProvider::Ambiguous(imports) = visibility {
278                    return Err(NidusError::AmbiguousProvider {
279                        module: module.name.clone(),
280                        provider: provider.to_owned(),
281                        imports: imports.into_iter().map(str::to_owned).collect(),
282                    });
283                }
284            }
285        }
286        Ok(())
287    }
288
289    fn visit<'a>(
290        &'a self,
291        name: &'a str,
292        visiting: &mut BTreeSet<&'a str>,
293        visited: &mut BTreeSet<&'a str>,
294        stack: &mut Vec<&'a str>,
295    ) -> Result<()> {
296        if visited.contains(name) {
297            return Ok(());
298        }
299
300        if visiting.contains(name) {
301            let cycle_start = stack.iter().position(|item| *item == name).unwrap_or(0);
302            let mut cycle = stack[cycle_start..]
303                .iter()
304                .map(|name| (*name).to_owned())
305                .collect::<Vec<_>>();
306            cycle.push(name.to_owned());
307            return Err(NidusError::CircularModuleImport { cycle });
308        }
309
310        visiting.insert(name);
311        stack.push(name);
312        if let Some(module) = self.modules.get(name) {
313            for import in &module.imports {
314                self.visit(import, visiting, visited, stack)?;
315            }
316        }
317        stack.pop();
318        visiting.remove(name);
319        visited.insert(name);
320        Ok(())
321    }
322}
323
324fn first_duplicate(names: &[String]) -> Option<&str> {
325    if names.len() < 2 {
326        return None;
327    }
328
329    let mut seen = BTreeSet::new();
330    names
331        .iter()
332        .find(|name| !seen.insert(name.as_str()))
333        .map(String::as_str)
334}
335
336fn collect_recursive(
337    module: ModuleDefinition,
338    definitions: &mut Vec<ModuleDefinition>,
339    seen: &mut BTreeSet<String>,
340) {
341    if !seen.insert(module.name().to_owned()) {
342        return;
343    }
344
345    for import in module.import_factories() {
346        collect_recursive(import(), definitions, seen);
347    }
348
349    definitions.push(module);
350}
nidus_core/module/graph.rs

nidus_core/module/
graph.rs
