serde_hkx/
sort.rs

1//! Provides a method that can be used to sort bytes and XML to serialize.
2use crate::errors::ser::Error as SerError;
3use havok_serde::HavokClass;
4use indexmap::IndexMap;
5
6/// Trait that provides a method that can be used to sort bytes and XML to serialize
7pub trait HavokSort {
8    type Error;
9
10    /// Sort by dependent class from root for serialization of bytes.
11    ///
12    /// There is a rule that binary data serializes class dependency pointers in order from the root, which is `hkRootLevelContainer`.
13    /// This is because behavior is written by state transitions, which are state machines.
14    ///
15    /// # Current implementation
16    /// - If deserialize a binary with `serde-hkx` -> already sorted for bytes
17    /// - If deserialize xml of official SDK -> sort is required
18    fn sort_for_bytes(&mut self);
19
20    /// Sort by dependent class for XML serialization.
21    ///
22    /// # Return
23    /// top ptr
24    ///
25    /// # Errors
26    /// Missing top pointer.
27    fn sort_for_xml(&mut self) -> Result<usize, Self::Error>;
28}
29
30impl<V> HavokSort for IndexMap<usize, V>
31where
32    V: HavokClass,
33{
34    type Error = SerError;
35
36    fn sort_for_bytes(&mut self) {
37        fn collect_deps<V>(
38            classes: &mut IndexMap<usize, V>,
39            key: usize,
40            sorted_keys: &mut Vec<usize>,
41        ) where
42            V: HavokClass,
43        {
44            if sorted_keys.contains(&key) {
45                return;
46            }
47
48            let current_index = match classes.get_index_of(&key) {
49                Some(index) => index,
50                None => return, // Return if the key doesn't exist.
51            };
52
53            sorted_keys.push(key);
54            classes.swap_indices(sorted_keys.len().saturating_sub(1), current_index);
55
56            if let Some(class) = classes.get(&key) {
57                let deps = class.deps_indexes();
58
59                #[cfg(feature = "tracing")]
60                tracing::trace!("index = {key}, deps_indexes = {deps:?}");
61
62                for dep_key in deps {
63                    collect_deps(classes, dep_key, sorted_keys);
64                }
65            }
66        }
67
68        if self.is_empty() {
69            return;
70        }
71
72        let &root_key = match self.keys().min() {
73            Some(min) => min,
74            None => return,
75        };
76
77        let mut sorted_keys = Vec::with_capacity(self.len());
78        collect_deps(self, root_key, &mut sorted_keys);
79
80        #[cfg(feature = "tracing")]
81        tracing::trace!("sorted_keys = {:?}", sorted_keys);
82    }
83
84    fn sort_for_xml(&mut self) -> Result<usize, Self::Error> {
85        /// Create an acyclic directed graph from the order of fields in the root to the tail branch (class of dependencies).
86        fn collect_deps<V>(
87            classes: &IndexMap<usize, V>,
88            key: usize,
89            class: &V,
90            sorted: &mut Vec<usize>,
91        ) where
92            V: HavokClass,
93        {
94            if sorted.contains(&key) {
95                return;
96            }
97
98            let deps = class.deps_indexes();
99            #[cfg(feature = "tracing")]
100            tracing::trace!("index = {key}, deps_indexes = {deps:?}");
101
102            for dep_key in deps {
103                if let Some(dep_class) = classes.get(&dep_key) {
104                    collect_deps(classes, dep_key, dep_class, sorted);
105                }
106            }
107
108            sorted.push(key);
109        }
110
111        let mut sorted_keys = Vec::new();
112        let (&root_key, root_class) = self
113            .keys()
114            .min()
115            .and_then(|min| self.get_key_value(min))
116            .ok_or_else(|| SerError::Message {
117                msg: "Missing top pointer.".to_owned(),
118            })?;
119        collect_deps(self, root_key, root_class, &mut sorted_keys);
120
121        #[cfg(feature = "tracing")]
122        tracing::trace!("sorted_keys = {sorted_keys:?}");
123        let mut sorted_classes = Self::with_capacity(self.len());
124        for index in &sorted_keys {
125            if let Some(class) = self.swap_remove(index) {
126                sorted_classes.insert(*index, class);
127            }
128        }
129        *self = sorted_classes;
130        Ok(root_key)
131    }
132}
serde_hkx/sort.rs

serde_hkx/
sort.rs
