zerodds_xml/
inheritance.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 ZeroDDS Contributors
3//! `base_name`-Resolver mit Cycle-Detection.
4//!
5//! DDS-XML 1.0 erlaubt mehreren Building-Blocks (QoS-Profile §7.3.2.4.2,
6//! Domain §7.3.4.4.2, DomainParticipant §7.3.5.4.3) eine `base_name`-Attribut-
7//! basierte Vererbung. Die Spec verlangt, dass die Basis-Definition vor der
8//! erbenden Definition steht — naive Implementierungen koennen ueber
9//! Bibliotheks-Grenzen hinweg dennoch Zyklen erzeugen.
10//!
11//! Dieses Modul implementiert eine generische Inheritance-Aufloesung mit
12//! DAG-Pruefung. Die Aufloesungs-Routine ist parametrisiert ueber den
13//! Item-Typ (z.B. QoS-Profile, Domain, Participant) und die `base_name`-
14//! Lookup-Funktion.
15
16use crate::errors::XmlError;
17use alloc::collections::BTreeSet;
18use alloc::format;
19use alloc::string::{String, ToString};
20use alloc::vec::Vec;
21
22/// Maximale Inheritance-Tiefe (DoS-Cap).
23pub const MAX_INHERITANCE_DEPTH: usize = 32;
24
25/// Resolves a `base_name`-chain starting at `name` and returns the
26/// chain in **base-first** order, i.e. `[grandparent, parent, name]`.
27///
28/// Die Reihenfolge ermoeglicht es Aufrufern, Felder schrittweise zu
29/// "merge"en (Base-Defaults zuerst, dann ueberschreiben).
30///
31/// # Parameter
32/// * `name` — Startpunkt der Aufloesung.
33/// * `lookup` — Closure, die fuer einen `name` den `base_name` (oder
34///   `None`, wenn keine Basis vorhanden) zurueckgibt. Wenn der `name`
35///   selbst nicht existiert, soll [`XmlError::MissingRequiredElement`]
36///   zurueckgegeben werden.
37///
38/// # Errors
39/// * [`XmlError::CircularInheritance`] — wenn ein Zyklus erkannt wird.
40/// * [`XmlError::LimitExceeded`] — wenn [`MAX_INHERITANCE_DEPTH`]
41///   ueberschritten wird.
42/// * Fehler aus der `lookup`-Closure werden durchgereicht.
43///
44/// zerodds-lint: recursion-depth = no recursion (iterative loop with
45/// MAX_INHERITANCE_DEPTH bound).
46pub fn resolve_chain<F>(name: &str, mut lookup: F) -> Result<Vec<String>, XmlError>
47where
48    F: FnMut(&str) -> Result<Option<String>, XmlError>,
49{
50    let mut visited: BTreeSet<String> = BTreeSet::new();
51    let mut chain: Vec<String> = Vec::new();
52    let mut current = name.to_string();
53
54    for _ in 0..MAX_INHERITANCE_DEPTH {
55        if !visited.insert(current.clone()) {
56            // Zyklus: `current` wurde bereits besucht.
57            chain.push(current.clone());
58            let pretty = chain.join(" -> ");
59            return Err(XmlError::CircularInheritance(pretty));
60        }
61        chain.push(current.clone());
62
63        match lookup(&current)? {
64            None => {
65                // Kein Basis-Eintrag: Aufloesung beendet.
66                chain.reverse();
67                return Ok(chain);
68            }
69            Some(base) => {
70                current = base;
71            }
72        }
73    }
74
75    Err(XmlError::LimitExceeded(format!(
76        "base_name chain depth > {MAX_INHERITANCE_DEPTH}"
77    )))
78}
79
80#[cfg(test)]
81#[allow(clippy::expect_used, clippy::unwrap_used, clippy::panic)]
82mod tests {
83    use super::*;
84    use alloc::collections::BTreeMap;
85    use alloc::vec;
86
87    fn make_lookup(
88        items: BTreeMap<&'static str, Option<&'static str>>,
89    ) -> impl FnMut(&str) -> Result<Option<String>, XmlError> {
90        move |name: &str| {
91            items
92                .get(name)
93                .copied()
94                .ok_or_else(|| XmlError::MissingRequiredElement(name.to_string()))
95                .map(|opt| opt.map(|s| s.to_string()))
96        }
97    }
98
99    #[test]
100    fn no_inheritance() {
101        let mut items: BTreeMap<&str, Option<&str>> = BTreeMap::new();
102        items.insert("A", None);
103        let chain = resolve_chain("A", make_lookup(items)).expect("ok");
104        assert_eq!(chain, vec!["A".to_string()]);
105    }
106
107    #[test]
108    fn three_level_chain() {
109        // C is base of B, B is base of A.
110        let mut items: BTreeMap<&str, Option<&str>> = BTreeMap::new();
111        items.insert("A", Some("B"));
112        items.insert("B", Some("C"));
113        items.insert("C", None);
114        let chain = resolve_chain("A", make_lookup(items)).expect("ok");
115        // base-first order
116        assert_eq!(
117            chain,
118            vec!["C".to_string(), "B".to_string(), "A".to_string()]
119        );
120    }
121
122    #[test]
123    fn two_node_cycle() {
124        // A -> B -> A
125        let mut items: BTreeMap<&str, Option<&str>> = BTreeMap::new();
126        items.insert("A", Some("B"));
127        items.insert("B", Some("A"));
128        let err = resolve_chain("A", make_lookup(items)).expect_err("cycle");
129        match err {
130            XmlError::CircularInheritance(msg) => {
131                assert!(msg.contains("A -> B -> A") || msg.contains("A"));
132            }
133            other => panic!("unexpected error: {other:?}"),
134        }
135    }
136
137    #[test]
138    fn self_cycle() {
139        let mut items: BTreeMap<&str, Option<&str>> = BTreeMap::new();
140        items.insert("A", Some("A"));
141        let err = resolve_chain("A", make_lookup(items)).expect_err("self-cycle");
142        assert!(matches!(err, XmlError::CircularInheritance(_)));
143    }
144
145    #[test]
146    fn missing_base_propagates() {
147        let mut items: BTreeMap<&str, Option<&str>> = BTreeMap::new();
148        items.insert("A", Some("DOES_NOT_EXIST"));
149        let err = resolve_chain("A", make_lookup(items)).expect_err("missing");
150        assert!(matches!(err, XmlError::MissingRequiredElement(_)));
151    }
152
153    #[test]
154    fn depth_cap_enforced() {
155        // Build a chain of MAX_INHERITANCE_DEPTH+1 levels.
156        // We can't easily do that with &'static strings, so we use
157        // a closure that fabricates names on the fly.
158        let lookup = |name: &str| -> Result<Option<String>, XmlError> {
159            // Always return `name + "x"` -> infinite chain.
160            Ok(Some(format!("{name}x")))
161        };
162        let err = resolve_chain("A", lookup).expect_err("depth");
163        assert!(matches!(err, XmlError::LimitExceeded(_)));
164    }
165}
zerodds_xml/inheritance.rs

zerodds_xml/
inheritance.rs
