zerodds_types/
resolve.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2026 ZeroDDS Contributors
3//! Type-Resolution + Recursion-Guards (XTypes §7.3.4.5, §7.3.4.9).
4//!
5//! Cross-references zwischen TypeObjects passieren ueber `EquivalenceHash`-
6//! TypeIdentifier (EK_MINIMAL / EK_COMPLETE). Ein TypeRegistry-Map cached
7//! bekannte Objekte; Resolver-Funktionen folgen Alias-Ketten und
8//! erkennen Rekursion/Cycles/DoS-Versuche via Depth-Cap.
9
10use alloc::collections::{BTreeMap, BTreeSet};
11use alloc::vec::Vec;
12
13use crate::type_identifier::{EquivalenceHash, TypeIdentifier};
14use crate::type_object::minimal::MinimalTypeObject;
15use crate::type_object::{CompleteTypeObject, TypeObject};
16
17/// Maximum-Depth fuer rekursives Aufloesen von Alias-Ketten und
18/// TypeIdentifier-Referenzen. Verhindert DoS durch boese
19/// Type-Graphen mit Zyklen.
20pub const DEFAULT_MAX_RESOLVE_DEPTH: usize = 64;
21
22/// Maximum-Knotenzahl waehrend [`collect_referenced_hashes`]. Zusaetzlich
23/// zum Depth-Cap begrenzt das auch breite/fan-out-lastige Graphen
24/// (ein Struct mit 10_000 Member-Eintraegen, die alle auf Hashes
25/// verweisen).
26pub const DEFAULT_MAX_RESOLVE_NODES: usize = 4_096;
27
28/// Fehler bei Type-Resolution.
29#[derive(Debug, Clone, PartialEq, Eq)]
30#[non_exhaustive]
31pub enum ResolveError {
32    /// Maximum-Depth ueberschritten.
33    DepthExceeded {
34        /// Zulaessige Tiefe.
35        limit: usize,
36    },
37    /// Maximum-Knotenzahl ueberschritten.
38    NodeLimitExceeded {
39        /// Zulaessige Knotenzahl.
40        limit: usize,
41    },
42    /// Referenzierter Type nicht in der Registry.
43    Unknown {
44        /// Hash, der gesucht wurde.
45        hash: EquivalenceHash,
46    },
47    /// Zyklus ohne Fortschritt erkannt.
48    Cycle,
49}
50
51/// In-Memory-Registry von bekannten TypeObjects, indiziert nach
52/// `EquivalenceHash`. Wird typischerweise durch TypeLookup-Replies
53/// befuellt.
54#[derive(Debug, Clone, Default)]
55pub struct TypeRegistry {
56    minimals: BTreeMap<EquivalenceHash, MinimalTypeObject>,
57    completes: BTreeMap<EquivalenceHash, CompleteTypeObject>,
58}
59
60impl TypeRegistry {
61    /// Leere Registry.
62    #[must_use]
63    pub fn new() -> Self {
64        Self::default()
65    }
66
67    /// Fuegt ein Minimal-TypeObject ein, indiziert unter seinem Hash.
68    pub fn insert_minimal(&mut self, hash: EquivalenceHash, t: MinimalTypeObject) {
69        self.minimals.insert(hash, t);
70    }
71
72    /// Fuegt ein Complete-TypeObject ein.
73    pub fn insert_complete(&mut self, hash: EquivalenceHash, t: CompleteTypeObject) {
74        self.completes.insert(hash, t);
75    }
76
77    /// Lookup.
78    #[must_use]
79    pub fn get_minimal(&self, hash: &EquivalenceHash) -> Option<&MinimalTypeObject> {
80        self.minimals.get(hash)
81    }
82
83    /// Lookup.
84    #[must_use]
85    pub fn get_complete(&self, hash: &EquivalenceHash) -> Option<&CompleteTypeObject> {
86        self.completes.get(hash)
87    }
88
89    /// Anzahl Eintraege.
90    #[must_use]
91    pub fn len(&self) -> (usize, usize) {
92        (self.minimals.len(), self.completes.len())
93    }
94
95    /// Leer?
96    #[must_use]
97    pub fn is_empty(&self) -> bool {
98        self.minimals.is_empty() && self.completes.is_empty()
99    }
100
101    /// Iteriert alle Minimal-Eintraege.
102    pub fn iter_minimals(
103        &self,
104    ) -> alloc::collections::btree_map::Iter<'_, EquivalenceHash, MinimalTypeObject> {
105        self.minimals.iter()
106    }
107
108    /// Iteriert alle Complete-Eintraege.
109    pub fn iter_completes(
110        &self,
111    ) -> alloc::collections::btree_map::Iter<'_, EquivalenceHash, CompleteTypeObject> {
112        self.completes.iter()
113    }
114
115    /// Liefert alle direkten Dependencies eines Hashes (transitiv ueber
116    /// [`collect_referenced_hashes`]). Wenn der Type nicht in der
117    /// Registry ist, wird leer zurueckgegeben.
118    ///
119    /// Bevorzugt die Minimal-Variante, faellt zurueck auf Complete.
120    #[must_use]
121    pub fn dependencies_of(&self, hash: &EquivalenceHash) -> Vec<EquivalenceHash> {
122        let to = if let Some(m) = self.minimals.get(hash) {
123            TypeObject::Minimal(m.clone())
124        } else if let Some(c) = self.completes.get(hash) {
125            TypeObject::Complete(c.clone())
126        } else {
127            return Vec::new();
128        };
129        collect_referenced_hashes(&to, DEFAULT_MAX_RESOLVE_DEPTH).unwrap_or_default()
130    }
131
132    /// Sammelt **transitiv** alle abhaengigen Hashes — folgt jedem
133    /// gefundenen Hash rekursiv durch die Registry. Eingehender Hash
134    /// selbst ist NICHT enthalten. Begrenzt durch `max_nodes`.
135    #[must_use]
136    pub fn transitive_dependencies(
137        &self,
138        hash: &EquivalenceHash,
139        max_nodes: usize,
140    ) -> Vec<EquivalenceHash> {
141        let mut out: Vec<EquivalenceHash> = Vec::new();
142        let mut seen: BTreeSet<EquivalenceHash> = BTreeSet::new();
143        let mut queue: Vec<EquivalenceHash> = self.dependencies_of(hash);
144        while let Some(h) = queue.pop() {
145            if !seen.insert(h) {
146                continue;
147            }
148            if out.len() >= max_nodes {
149                break;
150            }
151            out.push(h);
152            for child in self.dependencies_of(&h) {
153                if !seen.contains(&child) {
154                    queue.push(child);
155                }
156            }
157        }
158        out
159    }
160}
161
162/// Folgt Alias-Ketten: wenn `ti` auf einen Alias verweist (und der
163/// Alias in der Registry bekannt ist), resolve zum related_type.
164/// Primitive / Plain / Hash-direkt werden ohne Aenderung zurueckgegeben.
165///
166/// # Errors
167/// - `DepthExceeded` bei tieferem Alias-Nesting als `max_depth`.
168/// - `Unknown` wenn ein Hash nicht in der Registry liegt.
169pub fn resolve_alias_chain(
170    start: &TypeIdentifier,
171    registry: &TypeRegistry,
172    max_depth: usize,
173) -> Result<TypeIdentifier, ResolveError> {
174    let mut current = start.clone();
175    let mut visited: BTreeSet<EquivalenceHash> = BTreeSet::new();
176    for _ in 0..max_depth {
177        let hash = match &current {
178            TypeIdentifier::EquivalenceHashMinimal(h) => *h,
179            TypeIdentifier::EquivalenceHashComplete(h) => *h,
180            _ => return Ok(current), // nicht hash-referenced — fertig
181        };
182        if !visited.insert(hash) {
183            return Err(ResolveError::Cycle);
184        }
185
186        let next_ti = if matches!(current, TypeIdentifier::EquivalenceHashMinimal(_)) {
187            match registry.get_minimal(&hash) {
188                Some(MinimalTypeObject::Alias(a)) => a.body.common.related_type.clone(),
189                Some(_) => return Ok(current), // struct/enum/... — kein Alias
190                None => return Err(ResolveError::Unknown { hash }),
191            }
192        } else {
193            match registry.get_complete(&hash) {
194                Some(CompleteTypeObject::Alias(a)) => a.body.related_type.clone(),
195                Some(_) => return Ok(current),
196                None => return Err(ResolveError::Unknown { hash }),
197            }
198        };
199        current = next_ti;
200    }
201    Err(ResolveError::DepthExceeded { limit: max_depth })
202}
203
204/// Sammelt transitiv alle `EquivalenceHash`-TypeIdentifiers, die von
205/// `root` direkt oder indirekt (durch Collections, Struct-Members,
206/// Union-Cases, Alias-Targets) referenziert werden. Nuetzlich fuer
207/// TypeLookup-Dependency-Resolution (T14).
208///
209/// Verwendet Depth-Cap gegen boese Type-Graphen.
210///
211/// # Errors
212/// `DepthExceeded` wenn der Type-Graph tiefer als `max_depth` ist.
213pub fn collect_referenced_hashes(
214    root: &TypeObject,
215    max_depth: usize,
216) -> Result<Vec<EquivalenceHash>, ResolveError> {
217    let mut out = Vec::new();
218    let mut seen = Vec::new();
219    collect_from_type_object(root, max_depth, 0, &mut out, &mut seen)?;
220    Ok(out)
221}
222
223fn collect_from_type_object(
224    to: &TypeObject,
225    max_depth: usize,
226    depth: usize,
227    out: &mut Vec<EquivalenceHash>,
228    seen: &mut Vec<EquivalenceHash>,
229) -> Result<(), ResolveError> {
230    if depth >= max_depth {
231        return Err(ResolveError::DepthExceeded { limit: max_depth });
232    }
233    match to {
234        TypeObject::Minimal(m) => collect_from_minimal(m, max_depth, depth + 1, out, seen),
235        TypeObject::Complete(c) => collect_from_complete(c, max_depth, depth + 1, out, seen),
236    }
237}
238
239fn collect_from_minimal(
240    m: &MinimalTypeObject,
241    max_depth: usize,
242    depth: usize,
243    out: &mut Vec<EquivalenceHash>,
244    seen: &mut Vec<EquivalenceHash>,
245) -> Result<(), ResolveError> {
246    match m {
247        MinimalTypeObject::Struct(s) => {
248            collect_from_ti(&s.header.base_type, max_depth, depth, out, seen)?;
249            for mem in &s.member_seq {
250                collect_from_ti(&mem.common.member_type_id, max_depth, depth, out, seen)?;
251            }
252        }
253        MinimalTypeObject::Union(u) => {
254            collect_from_ti(&u.discriminator.common.type_id, max_depth, depth, out, seen)?;
255            for mem in &u.member_seq {
256                collect_from_ti(&mem.common.type_id, max_depth, depth, out, seen)?;
257            }
258        }
259        MinimalTypeObject::Alias(a) => {
260            collect_from_ti(&a.body.common.related_type, max_depth, depth, out, seen)?;
261        }
262        MinimalTypeObject::Sequence(s) => {
263            collect_from_ti(&s.element.common.type_id, max_depth, depth, out, seen)?;
264        }
265        MinimalTypeObject::Array(a) => {
266            collect_from_ti(&a.element.common.type_id, max_depth, depth, out, seen)?;
267        }
268        MinimalTypeObject::Map(m) => {
269            collect_from_ti(&m.key.common.type_id, max_depth, depth, out, seen)?;
270            collect_from_ti(&m.element.common.type_id, max_depth, depth, out, seen)?;
271        }
272        _ => {} // Enum/Bitmask/Bitset/Annotation — keine nested TIs
273    }
274    Ok(())
275}
276
277fn collect_from_complete(
278    c: &CompleteTypeObject,
279    max_depth: usize,
280    depth: usize,
281    out: &mut Vec<EquivalenceHash>,
282    seen: &mut Vec<EquivalenceHash>,
283) -> Result<(), ResolveError> {
284    match c {
285        CompleteTypeObject::Struct(s) => {
286            collect_from_ti(&s.header.base_type, max_depth, depth, out, seen)?;
287            for mem in &s.member_seq {
288                collect_from_ti(&mem.common.member_type_id, max_depth, depth, out, seen)?;
289            }
290        }
291        CompleteTypeObject::Union(u) => {
292            collect_from_ti(&u.discriminator.common.type_id, max_depth, depth, out, seen)?;
293            for mem in &u.member_seq {
294                collect_from_ti(&mem.common.type_id, max_depth, depth, out, seen)?;
295            }
296        }
297        CompleteTypeObject::Alias(a) => {
298            collect_from_ti(&a.body.related_type, max_depth, depth, out, seen)?;
299        }
300        CompleteTypeObject::Sequence(s) => {
301            collect_from_ti(&s.element.common.type_id, max_depth, depth, out, seen)?;
302        }
303        CompleteTypeObject::Array(a) => {
304            collect_from_ti(&a.element.common.type_id, max_depth, depth, out, seen)?;
305        }
306        CompleteTypeObject::Map(m) => {
307            collect_from_ti(&m.key.common.type_id, max_depth, depth, out, seen)?;
308            collect_from_ti(&m.element.common.type_id, max_depth, depth, out, seen)?;
309        }
310        _ => {}
311    }
312    Ok(())
313}
314
315/// zerodds-lint: recursion-depth 16
316///
317/// Walked plain-Collection-Elements rekursiv (Sequence→Map→Array-nesting).
318/// Die Tiefe ist effektiv durch `TypeIdentifier::MAX_DECODE_DEPTH` (=16)
319/// begrenzt, weil der Input aus dem Wire-Decoder stammt.
320fn collect_from_ti(
321    ti: &TypeIdentifier,
322    _max_depth: usize,
323    _depth: usize,
324    out: &mut Vec<EquivalenceHash>,
325    seen: &mut Vec<EquivalenceHash>,
326) -> Result<(), ResolveError> {
327    match ti {
328        TypeIdentifier::EquivalenceHashMinimal(h) | TypeIdentifier::EquivalenceHashComplete(h) => {
329            if !seen.contains(h) {
330                if seen.len() >= DEFAULT_MAX_RESOLVE_NODES {
331                    return Err(ResolveError::NodeLimitExceeded {
332                        limit: DEFAULT_MAX_RESOLVE_NODES,
333                    });
334                }
335                seen.push(*h);
336                out.push(*h);
337            }
338        }
339        TypeIdentifier::PlainSequenceSmall { element, .. }
340        | TypeIdentifier::PlainSequenceLarge { element, .. }
341        | TypeIdentifier::PlainArraySmall { element, .. }
342        | TypeIdentifier::PlainArrayLarge { element, .. } => {
343            collect_from_ti(element, _max_depth, _depth, out, seen)?;
344        }
345        TypeIdentifier::PlainMapSmall { element, key, .. }
346        | TypeIdentifier::PlainMapLarge { element, key, .. } => {
347            collect_from_ti(element, _max_depth, _depth, out, seen)?;
348            collect_from_ti(key, _max_depth, _depth, out, seen)?;
349        }
350        _ => {}
351    }
352    Ok(())
353}
354
355// ============================================================================
356// Tests
357// ============================================================================
358
359#[cfg(test)]
360#[allow(clippy::unwrap_used, clippy::panic)]
361mod tests {
362    use super::*;
363    use crate::builder::TypeObjectBuilder;
364    use crate::hash::compute_minimal_hash;
365    use crate::type_identifier::PrimitiveKind;
366    use crate::type_object::minimal::MinimalAliasType;
367
368    fn make_alias(related: TypeIdentifier) -> MinimalAliasType {
369        use crate::type_object::flags::{AliasMemberFlag, AliasTypeFlag};
370        use crate::type_object::minimal::{CommonAliasBody, MinimalAliasBody};
371        MinimalAliasType {
372            alias_flags: AliasTypeFlag::default(),
373            body: MinimalAliasBody {
374                common: CommonAliasBody {
375                    related_flags: AliasMemberFlag::default(),
376                    related_type: related,
377                },
378            },
379        }
380    }
381
382    #[test]
383    fn resolve_returns_primitive_unchanged() {
384        let reg = TypeRegistry::new();
385        let p = TypeIdentifier::Primitive(PrimitiveKind::Int64);
386        let resolved = resolve_alias_chain(&p, &reg, 8).unwrap();
387        assert_eq!(resolved, p);
388    }
389
390    #[test]
391    fn resolve_follows_single_alias_to_target() {
392        let mut reg = TypeRegistry::new();
393        let target = TypeIdentifier::Primitive(PrimitiveKind::UInt64);
394        let alias = MinimalTypeObject::Alias(make_alias(target.clone()));
395        let alias_hash = compute_minimal_hash(&alias).unwrap();
396        reg.insert_minimal(alias_hash, alias);
397
398        let start = TypeIdentifier::EquivalenceHashMinimal(alias_hash);
399        let resolved = resolve_alias_chain(&start, &reg, 8).unwrap();
400        assert_eq!(resolved, target);
401    }
402
403    #[test]
404    fn resolve_chained_aliases_two_deep() {
405        let mut reg = TypeRegistry::new();
406        let final_target = TypeIdentifier::Primitive(PrimitiveKind::Int8);
407        let inner = MinimalTypeObject::Alias(make_alias(final_target.clone()));
408        let inner_hash = compute_minimal_hash(&inner).unwrap();
409        reg.insert_minimal(inner_hash, inner);
410
411        let outer = MinimalTypeObject::Alias(make_alias(TypeIdentifier::EquivalenceHashMinimal(
412            inner_hash,
413        )));
414        let outer_hash = compute_minimal_hash(&outer).unwrap();
415        reg.insert_minimal(outer_hash, outer);
416
417        let resolved =
418            resolve_alias_chain(&TypeIdentifier::EquivalenceHashMinimal(outer_hash), &reg, 8)
419                .unwrap();
420        assert_eq!(resolved, final_target);
421    }
422
423    #[test]
424    fn resolve_cycle_detected() {
425        let mut reg = TypeRegistry::new();
426        // Zwei Aliase, die aufeinander zeigen. Um konsistente Hashes zu
427        // bekommen muessten wir sie simultan einfuegen — wir simulieren
428        // einen Zyklus indem wir denselben Alias als related_type = sein
429        // eigener Hash eintragen.
430        let self_hash = EquivalenceHash([0x99; 14]);
431        let self_alias = MinimalTypeObject::Alias(make_alias(
432            TypeIdentifier::EquivalenceHashMinimal(self_hash),
433        ));
434        reg.insert_minimal(self_hash, self_alias);
435
436        let err = resolve_alias_chain(&TypeIdentifier::EquivalenceHashMinimal(self_hash), &reg, 8)
437            .unwrap_err();
438        assert_eq!(err, ResolveError::Cycle);
439    }
440
441    #[test]
442    fn resolve_unknown_hash_fails() {
443        let reg = TypeRegistry::new();
444        let err = resolve_alias_chain(
445            &TypeIdentifier::EquivalenceHashMinimal(EquivalenceHash([0xAA; 14])),
446            &reg,
447            8,
448        )
449        .unwrap_err();
450        assert!(matches!(err, ResolveError::Unknown { .. }));
451    }
452
453    #[test]
454    fn collect_referenced_hashes_picks_up_nested_struct_members() {
455        let inner_hash = EquivalenceHash([0x01; 14]);
456        let st = TypeObjectBuilder::struct_type("::X")
457            .member(
458                "ref_a",
459                TypeIdentifier::EquivalenceHashMinimal(inner_hash),
460                |m| m,
461            )
462            .member("p", TypeIdentifier::Primitive(PrimitiveKind::Int32), |m| m)
463            .build_minimal();
464        let to = TypeObject::Minimal(MinimalTypeObject::Struct(st));
465        let refs = collect_referenced_hashes(&to, DEFAULT_MAX_RESOLVE_DEPTH).unwrap();
466        assert_eq!(refs, alloc::vec![inner_hash]);
467    }
468
469    #[test]
470    fn collect_referenced_hashes_from_union_cases() {
471        use crate::type_object::common::CommonUnionMember;
472        use crate::type_object::flags::{UnionDiscriminatorFlag, UnionMemberFlag, UnionTypeFlag};
473        use crate::type_object::minimal::{
474            CommonDiscriminatorMember, MinimalDiscriminatorMember, MinimalUnionMember,
475            MinimalUnionType,
476        };
477        let h_disc = EquivalenceHash([0x01; 14]);
478        let h_case = EquivalenceHash([0x02; 14]);
479        let u = MinimalUnionType {
480            union_flags: UnionTypeFlag::default(),
481            discriminator: MinimalDiscriminatorMember {
482                common: CommonDiscriminatorMember {
483                    member_flags: UnionDiscriminatorFlag::default(),
484                    type_id: TypeIdentifier::EquivalenceHashMinimal(h_disc),
485                },
486            },
487            member_seq: alloc::vec![MinimalUnionMember {
488                common: CommonUnionMember {
489                    member_id: 1,
490                    member_flags: UnionMemberFlag::default(),
491                    type_id: TypeIdentifier::EquivalenceHashMinimal(h_case),
492                    label_seq: alloc::vec![1],
493                },
494                detail: crate::type_object::common::NameHash([0; 4]),
495            }],
496        };
497        let to = TypeObject::Minimal(MinimalTypeObject::Union(u));
498        let refs = collect_referenced_hashes(&to, DEFAULT_MAX_RESOLVE_DEPTH).unwrap();
499        assert!(refs.contains(&h_disc));
500        assert!(refs.contains(&h_case));
501    }
502
503    #[test]
504    fn collect_referenced_hashes_from_sequence_and_array_and_map() {
505        use crate::builder::TypeObjectBuilder;
506        let h_elem = EquivalenceHash([0x10; 14]);
507
508        let seq = TypeObjectBuilder::sequence(TypeIdentifier::EquivalenceHashMinimal(h_elem), 50)
509            .build_minimal();
510        let refs = collect_referenced_hashes(
511            &TypeObject::Minimal(MinimalTypeObject::Sequence(seq)),
512            DEFAULT_MAX_RESOLVE_DEPTH,
513        )
514        .unwrap();
515        assert_eq!(refs, alloc::vec![h_elem]);
516
517        let arr = TypeObjectBuilder::array(
518            TypeIdentifier::EquivalenceHashMinimal(h_elem),
519            alloc::vec![2, 3],
520        )
521        .build_minimal();
522        let refs = collect_referenced_hashes(
523            &TypeObject::Minimal(MinimalTypeObject::Array(arr)),
524            DEFAULT_MAX_RESOLVE_DEPTH,
525        )
526        .unwrap();
527        assert_eq!(refs, alloc::vec![h_elem]);
528
529        let h_key = EquivalenceHash([0x20; 14]);
530        let map = TypeObjectBuilder::map(
531            TypeIdentifier::EquivalenceHashMinimal(h_key),
532            TypeIdentifier::EquivalenceHashMinimal(h_elem),
533            10,
534        )
535        .build_minimal();
536        let refs = collect_referenced_hashes(
537            &TypeObject::Minimal(MinimalTypeObject::Map(map)),
538            DEFAULT_MAX_RESOLVE_DEPTH,
539        )
540        .unwrap();
541        assert!(refs.contains(&h_key));
542        assert!(refs.contains(&h_elem));
543    }
544
545    #[test]
546    fn collect_referenced_hashes_from_complete_typeobject() {
547        use crate::builder::TypeObjectBuilder;
548        let h = EquivalenceHash([0x44; 14]);
549        let st = TypeObjectBuilder::struct_type("::X")
550            .member("f", TypeIdentifier::EquivalenceHashMinimal(h), |m| m)
551            .build_complete();
552        let to = TypeObject::Complete(CompleteTypeObject::Struct(st));
553        let refs = collect_referenced_hashes(&to, DEFAULT_MAX_RESOLVE_DEPTH).unwrap();
554        assert_eq!(refs, alloc::vec![h]);
555    }
556
557    #[test]
558    fn collect_referenced_hashes_from_alias() {
559        use crate::builder::TypeObjectBuilder;
560        let h = EquivalenceHash([0x55; 14]);
561        let a = TypeObjectBuilder::alias("::A", TypeIdentifier::EquivalenceHashMinimal(h))
562            .build_minimal();
563        let to = TypeObject::Minimal(MinimalTypeObject::Alias(a));
564        let refs = collect_referenced_hashes(&to, DEFAULT_MAX_RESOLVE_DEPTH).unwrap();
565        assert_eq!(refs, alloc::vec![h]);
566    }
567
568    #[test]
569    fn collect_referenced_hashes_nested_plain_sequence_in_plain_map() {
570        // Plain TypeIdentifier im Member-Type: nested Sequence<of Map<of Hash>>
571        let h = EquivalenceHash([0x66; 14]);
572        let inner_map = TypeIdentifier::PlainMapSmall {
573            header: crate::type_identifier::PlainCollectionHeader::default(),
574            bound: 1,
575            element: alloc::boxed::Box::new(TypeIdentifier::EquivalenceHashMinimal(h)),
576            key_flags: crate::type_identifier::CollectionElementFlag(0),
577            key: alloc::boxed::Box::new(TypeIdentifier::Primitive(
578                crate::type_identifier::PrimitiveKind::Int32,
579            )),
580        };
581        let outer_seq = TypeIdentifier::PlainSequenceSmall {
582            header: crate::type_identifier::PlainCollectionHeader::default(),
583            bound: 3,
584            element: alloc::boxed::Box::new(inner_map),
585        };
586        use crate::builder::TypeObjectBuilder;
587        let st = TypeObjectBuilder::struct_type("::Nested")
588            .member("data", outer_seq, |m| m)
589            .build_minimal();
590        let to = TypeObject::Minimal(MinimalTypeObject::Struct(st));
591        let refs = collect_referenced_hashes(&to, DEFAULT_MAX_RESOLVE_DEPTH).unwrap();
592        assert_eq!(refs, alloc::vec![h]);
593    }
594
595    #[test]
596    fn resolve_depth_exceeded_with_long_alias_chain() {
597        // Build chain depth > max_depth.
598        let mut reg = TypeRegistry::new();
599        let mut last_hash = EquivalenceHash([0x00; 14]);
600        for i in 0..10u8 {
601            let target = if i == 0 {
602                TypeIdentifier::Primitive(crate::type_identifier::PrimitiveKind::Int32)
603            } else {
604                TypeIdentifier::EquivalenceHashMinimal(last_hash)
605            };
606            let alias = MinimalTypeObject::Alias(make_alias(target));
607            let h = crate::hash::compute_minimal_hash(&alias).unwrap();
608            reg.insert_minimal(h, alias);
609            last_hash = h;
610        }
611        let err = resolve_alias_chain(
612            &TypeIdentifier::EquivalenceHashMinimal(last_hash),
613            &reg,
614            3, // depth too low
615        )
616        .unwrap_err();
617        assert_eq!(err, ResolveError::DepthExceeded { limit: 3 });
618    }
619
620    #[test]
621    fn collect_referenced_hashes_skips_duplicates() {
622        let h = EquivalenceHash([0x22; 14]);
623        let st = TypeObjectBuilder::struct_type("::Y")
624            .member("a", TypeIdentifier::EquivalenceHashMinimal(h), |m| m)
625            .member("b", TypeIdentifier::EquivalenceHashMinimal(h), |m| m)
626            .build_minimal();
627        let to = TypeObject::Minimal(MinimalTypeObject::Struct(st));
628        let refs = collect_referenced_hashes(&to, DEFAULT_MAX_RESOLVE_DEPTH).unwrap();
629        assert_eq!(refs.len(), 1);
630    }
631
632    #[test]
633    fn collect_referenced_hashes_node_limit_exceeded_on_wide_struct() {
634        // Struct mit DEFAULT_MAX_RESOLVE_NODES + 1 distincten Hash-Refs
635        // triggert die NodeLimit-Bremse.
636        let mut builder = TypeObjectBuilder::struct_type("::Wide");
637        for i in 0..(DEFAULT_MAX_RESOLVE_NODES as u32 + 1) {
638            let mut h_bytes = [0u8; 14];
639            h_bytes[..4].copy_from_slice(&i.to_le_bytes());
640            let h = EquivalenceHash(h_bytes);
641            builder = builder.member(
642                alloc::format!("m_{i}").as_str(),
643                TypeIdentifier::EquivalenceHashMinimal(h),
644                |m| m,
645            );
646        }
647        let st = builder.build_minimal();
648        let to = TypeObject::Minimal(MinimalTypeObject::Struct(st));
649        let err = collect_referenced_hashes(&to, DEFAULT_MAX_RESOLVE_DEPTH).unwrap_err();
650        assert_eq!(
651            err,
652            ResolveError::NodeLimitExceeded {
653                limit: DEFAULT_MAX_RESOLVE_NODES,
654            }
655        );
656    }
657
658    // ====================================================================
659    // SCC / Mutual-Dependency (XTypes 1.3 §7.3.4.8 + §7.3.4.9)
660    // ====================================================================
661    //
662    // Wenn drei oder mehr Structs sich gegenseitig referenzieren, bilden
663    // sie eine starkconnected Komponente (SCC). Die TypeRegistry muss die
664    // Referenzen-Aufloesung trotz Cycle korrekt fuehren — der seen-Set-
665    // basierte Walker verhindert Endlosschleifen, und transitive_dependencies
666    // liefert deterministisch alle 3/4/N Knoten der SCC.
667
668    fn struct_with_member_ref(name: &str, ref_hash: EquivalenceHash) -> MinimalTypeObject {
669        MinimalTypeObject::Struct(
670            TypeObjectBuilder::struct_type(name)
671                .member(
672                    "next",
673                    TypeIdentifier::EquivalenceHashMinimal(ref_hash),
674                    |m| m,
675                )
676                .build_minimal(),
677        )
678    }
679
680    #[test]
681    fn scc_three_element_cycle_resolves_correctly() {
682        // A -> B -> C -> A
683        let h_a = EquivalenceHash([0x0A; 14]);
684        let h_b = EquivalenceHash([0x0B; 14]);
685        let h_c = EquivalenceHash([0x0C; 14]);
686        let mut reg = TypeRegistry::new();
687        reg.insert_minimal(h_a, struct_with_member_ref("A", h_b));
688        reg.insert_minimal(h_b, struct_with_member_ref("B", h_c));
689        reg.insert_minimal(h_c, struct_with_member_ref("C", h_a));
690
691        let deps = reg.transitive_dependencies(&h_a, DEFAULT_MAX_RESOLVE_NODES);
692        assert!(deps.contains(&h_a));
693        assert!(deps.contains(&h_b));
694        assert!(deps.contains(&h_c));
695        // Keine Endlosschleife: alle 3 + a-self-ref auf bekannte Hashes
696        // → exakt 3 unique Eintraege.
697        let mut sorted = deps.clone();
698        sorted.sort();
699        sorted.dedup();
700        assert_eq!(sorted.len(), 3);
701    }
702
703    #[test]
704    fn scc_four_element_cycle_resolves_correctly() {
705        // A -> B -> C -> D -> A (4-Knoten-Cycle)
706        let h_a = EquivalenceHash([0x1A; 14]);
707        let h_b = EquivalenceHash([0x1B; 14]);
708        let h_c = EquivalenceHash([0x1C; 14]);
709        let h_d = EquivalenceHash([0x1D; 14]);
710        let mut reg = TypeRegistry::new();
711        reg.insert_minimal(h_a, struct_with_member_ref("A", h_b));
712        reg.insert_minimal(h_b, struct_with_member_ref("B", h_c));
713        reg.insert_minimal(h_c, struct_with_member_ref("C", h_d));
714        reg.insert_minimal(h_d, struct_with_member_ref("D", h_a));
715
716        let deps = reg.transitive_dependencies(&h_a, DEFAULT_MAX_RESOLVE_NODES);
717        assert!(deps.contains(&h_a));
718        assert!(deps.contains(&h_b));
719        assert!(deps.contains(&h_c));
720        assert!(deps.contains(&h_d));
721        let mut sorted = deps.clone();
722        sorted.sort();
723        sorted.dedup();
724        assert_eq!(sorted.len(), 4);
725    }
726
727    #[test]
728    fn scc_diamond_with_cycle_resolves_finitely() {
729        //   A -> B -> D
730        //   |    |
731        //   v    v
732        //   C -> A   (Diamond mit Back-Edge zu A)
733        let h_a = EquivalenceHash([0x2A; 14]);
734        let h_b = EquivalenceHash([0x2B; 14]);
735        let h_c = EquivalenceHash([0x2C; 14]);
736        let h_d = EquivalenceHash([0x2D; 14]);
737        let mut reg = TypeRegistry::new();
738        // A hat zwei Member: -> B und -> C
739        let st_a = MinimalTypeObject::Struct(
740            TypeObjectBuilder::struct_type("A")
741                .member("to_b", TypeIdentifier::EquivalenceHashMinimal(h_b), |m| m)
742                .member("to_c", TypeIdentifier::EquivalenceHashMinimal(h_c), |m| m)
743                .build_minimal(),
744        );
745        reg.insert_minimal(h_a, st_a);
746        reg.insert_minimal(h_b, struct_with_member_ref("B", h_d));
747        reg.insert_minimal(h_c, struct_with_member_ref("C", h_a));
748        // D: terminal (kein Hash-Member)
749        let st_d = MinimalTypeObject::Struct(
750            TypeObjectBuilder::struct_type("D")
751                .member("x", TypeIdentifier::Primitive(PrimitiveKind::Int32), |m| m)
752                .build_minimal(),
753        );
754        reg.insert_minimal(h_d, st_d);
755
756        let deps = reg.transitive_dependencies(&h_a, DEFAULT_MAX_RESOLVE_NODES);
757        let mut sorted = deps.clone();
758        sorted.sort();
759        sorted.dedup();
760        assert!(sorted.contains(&h_a));
761        assert!(sorted.contains(&h_b));
762        assert!(sorted.contains(&h_c));
763        assert!(sorted.contains(&h_d));
764        assert_eq!(sorted.len(), 4);
765    }
766
767    // ---- §7.2.2.4.9 @external Forward-Decls + Diamond ----
768
769    #[test]
770    fn external_forward_decl_roundtrip() {
771        // Struct A hat einen `@external A* next` (Self-Forward).
772        // Wire-Encode/Decode des TypeObjects preservieren das EXTERNAL-Flag.
773        use crate::type_identifier::PrimitiveKind;
774        use crate::type_object::TypeObject;
775        use crate::type_object::flags::StructMemberFlag;
776        use crate::type_object::minimal::MinimalTypeObject;
777        let h_self = EquivalenceHash([0x4A; 14]);
778        let mut a = TypeObjectBuilder::struct_type("::A")
779            .member(
780                "next",
781                TypeIdentifier::EquivalenceHashMinimal(h_self),
782                |m| m.external().id(1),
783            )
784            .member(
785                "value",
786                TypeIdentifier::Primitive(PrimitiveKind::Int32),
787                |m| m.id(2),
788            )
789            .build_minimal();
790        // Hash an Wire-Form festschreiben (nur fuer den Test).
791        a.member_seq[0].common.member_flags = StructMemberFlag(StructMemberFlag::IS_EXTERNAL);
792
793        let mut reg = TypeRegistry::new();
794        reg.insert_minimal(h_self, MinimalTypeObject::Struct(a.clone()));
795
796        // Wire-Roundtrip via TypeObject Encode/Decode.
797        let to = TypeObject::Minimal(MinimalTypeObject::Struct(a.clone()));
798        let bytes = to.to_bytes_le().unwrap();
799        let decoded = TypeObject::from_bytes_le(&bytes).unwrap();
800        if let TypeObject::Minimal(MinimalTypeObject::Struct(b)) = decoded {
801            assert!(
802                b.member_seq[0]
803                    .common
804                    .member_flags
805                    .has(StructMemberFlag::IS_EXTERNAL)
806            );
807            assert_eq!(b.member_seq[0].common.member_id, 1);
808        } else {
809            panic!("expected MinimalStruct");
810        }
811
812        // Forward-Resolution per Registry: dependencies_of liefert h_self.
813        let deps = reg.transitive_dependencies(&h_self, DEFAULT_MAX_RESOLVE_NODES);
814        assert!(deps.contains(&h_self));
815    }
816
817    #[test]
818    fn external_diamond_resolves_through_both_paths() {
819        // Diamond:
820        //   A -> @external B -> @external D
821        //   A -> @external C -> @external D
822        //
823        // Erwartet: transitive_dependencies(A) = {B, C, D}, jeweils unique.
824        use crate::type_identifier::PrimitiveKind;
825        use crate::type_object::flags::StructMemberFlag;
826        use crate::type_object::minimal::MinimalTypeObject;
827        let h_a = EquivalenceHash([0x5A; 14]);
828        let h_b = EquivalenceHash([0x5B; 14]);
829        let h_c = EquivalenceHash([0x5C; 14]);
830        let h_d = EquivalenceHash([0x5D; 14]);
831
832        let mut a = TypeObjectBuilder::struct_type("A")
833            .member("to_b", TypeIdentifier::EquivalenceHashMinimal(h_b), |m| {
834                m.external().id(1)
835            })
836            .member("to_c", TypeIdentifier::EquivalenceHashMinimal(h_c), |m| {
837                m.external().id(2)
838            })
839            .build_minimal();
840        // Sicherstellen, dass die EXTERNAL-Flags wirklich gesetzt sind.
841        for m in &mut a.member_seq {
842            m.common.member_flags = StructMemberFlag(StructMemberFlag::IS_EXTERNAL);
843        }
844
845        let b = TypeObjectBuilder::struct_type("B")
846            .member("to_d", TypeIdentifier::EquivalenceHashMinimal(h_d), |m| {
847                m.external().id(1)
848            })
849            .build_minimal();
850        let c = TypeObjectBuilder::struct_type("C")
851            .member("to_d", TypeIdentifier::EquivalenceHashMinimal(h_d), |m| {
852                m.external().id(1)
853            })
854            .build_minimal();
855        let d = TypeObjectBuilder::struct_type("D")
856            .member("v", TypeIdentifier::Primitive(PrimitiveKind::Int32), |m| {
857                m.id(1)
858            })
859            .build_minimal();
860
861        let mut reg = TypeRegistry::new();
862        reg.insert_minimal(h_a, MinimalTypeObject::Struct(a));
863        reg.insert_minimal(h_b, MinimalTypeObject::Struct(b));
864        reg.insert_minimal(h_c, MinimalTypeObject::Struct(c));
865        reg.insert_minimal(h_d, MinimalTypeObject::Struct(d));
866
867        let deps = reg.transitive_dependencies(&h_a, DEFAULT_MAX_RESOLVE_NODES);
868        let mut sorted = deps.clone();
869        sorted.sort();
870        sorted.dedup();
871        assert!(sorted.contains(&h_b));
872        assert!(sorted.contains(&h_c));
873        assert!(sorted.contains(&h_d));
874        // 3 unique Hashes (B, C, D); A selbst ist root.
875        assert_eq!(sorted.len(), 3);
876    }
877
878    #[test]
879    fn scc_self_loop_does_not_explode_node_count() {
880        // A -> A (1-Knoten-Cycle, nur self-loop).
881        let h_a = EquivalenceHash([0x3A; 14]);
882        let mut reg = TypeRegistry::new();
883        reg.insert_minimal(h_a, struct_with_member_ref("A", h_a));
884
885        let deps = reg.transitive_dependencies(&h_a, DEFAULT_MAX_RESOLVE_NODES);
886        // dependencies_of(h_a) = [h_a], queue.pop() → seen.insert(h_a) push,
887        // dann children of h_a = [h_a] schon in seen → fertig. Genau 1 Eintrag.
888        assert_eq!(deps, alloc::vec![h_a]);
889    }
890}
zerodds_types/resolve.rs

zerodds_types/
resolve.rs
