serde_hkx/
tree.rs

1/// Trait to create a state transition tree
2use crate::HavokSort as _;
3use havok_serde::HavokClass;
4use havok_types::Pointer;
5use indexmap::IndexMap;
6use std::collections::HashMap;
7
8/// Trait to create ptr dependencies tree
9pub trait HavokTree {
10    /// Tree of the order in which to serialize as binary data.
11    fn tree_for_bytes(&mut self) -> String;
12    /// Tree of the order in which to serialize as XML.
13    fn tree_for_xml(&mut self) -> String;
14}
15
16#[derive(Debug)]
17struct Node {
18    name: String,
19    deps: Vec<usize>,
20}
21
22impl Node {
23    #[inline]
24    const fn new(name: String, deps: Vec<usize>) -> Self {
25        Self { name, deps }
26    }
27}
28
29#[allow(clippy::too_many_arguments)]
30fn print_node(
31    nodes: &IndexMap<usize, Node>,
32    idx: usize,
33    depth: usize,
34    visited: &mut HashMap<usize, usize>,
35    last_children: &mut Vec<bool>,
36    result: &mut String,
37    path: &mut Vec<usize>,
38    already_visited: &mut HashMap<usize, bool>,
39) {
40    if path.contains(&idx) {
41        // Cycle detected
42        let cycle_start = path.iter().position(|&x| x == idx).unwrap_or_default();
43        let cycle_path: Vec<String> = path[cycle_start..]
44            .iter()
45            .map(|&i| nodes[&i].name.clone())
46            .collect();
47
48        result.push_str(&format!(
49            "{}\\_Cycle Start(Invalid state transition): {}\n",
50            "| ".repeat(depth + 2),
51            nodes[&idx].name,
52        ));
53
54        for node_name in cycle_path.iter().skip(1) {
55            result.push_str(&format!("{}|-- {}\n", "| ".repeat(depth + 2), node_name));
56        }
57
58        result.push_str(&format!(
59            "{}    \\_Cycle End: {}\n",
60            "| ".repeat(depth + 2),
61            nodes[&idx].name,
62        ));
63        return;
64    }
65
66    let visit_count = visited.entry(idx).or_insert(0);
67    *visit_count += 1;
68
69    let is_already_visited = already_visited.entry(idx).or_insert(false);
70
71    if !*is_already_visited {
72        *is_already_visited = true;
73
74        for level in 0..depth {
75            if level == depth - 1 {
76                if *last_children.last().unwrap_or(&false) {
77                    result.push_str("`-- ");
78                } else {
79                    result.push_str("|-- ");
80                }
81            } else if *last_children.get(level).unwrap_or(&false) {
82                result.push_str("    ");
83            } else {
84                result.push_str("|   ");
85            }
86        }
87
88        if let Some(node) = nodes.get(&idx) {
89            result.push_str(&node.name);
90            result.push('\n');
91        } else {
92            #[cfg(feature = "tracing")]
93            tracing::error!("Not found key: {idx}");
94            return;
95        }
96    } else if *visit_count > 1 {
97        for level in 0..depth {
98            if level == depth - 1 {
99                if *last_children.last().unwrap_or(&false) {
100                    result.push_str("`-- ");
101                } else {
102                    result.push_str("|-- ");
103                }
104            } else if *last_children.get(level).unwrap_or(&false) {
105                result.push_str("    ");
106            } else {
107                result.push_str("|   ");
108            }
109        }
110        result.push_str(&format!(
111            "{} (visited {visit_count} times)\n",
112            nodes[&idx].name,
113        ));
114    }
115
116    // Add the current node to the path
117    path.push(idx);
118
119    // Print visited tree dependencies
120    if let Some(node) = nodes.get(&idx) {
121        for (i, &dep) in node.deps.iter().enumerate() {
122            last_children.push(i == node.deps.len() - 1);
123            print_node(
124                nodes,
125                dep,
126                depth + 1,
127                visited,
128                last_children,
129                result,
130                path,
131                already_visited,
132            );
133            last_children.pop();
134        }
135    }
136
137    // Remove the current node from the path after processing
138    path.pop();
139}
140
141impl<V> HavokTree for IndexMap<usize, V>
142where
143    V: HavokClass,
144{
145    fn tree_for_bytes(&mut self) -> String {
146        self.sort_for_bytes();
147
148        let mut nodes: IndexMap<usize, Node> = IndexMap::new();
149        for (&index, class) in self.iter() {
150            let non_null_deps = class
151                .deps_indexes()
152                .into_iter()
153                .filter(|&index| index != 0)
154                .collect();
155
156            nodes.insert(
157                index,
158                Node::new(
159                    format!("{}({})", class.name(), Pointer::new(index)),
160                    non_null_deps,
161                ),
162            );
163        }
164
165        let mut visited = HashMap::new();
166        let mut result = String::new();
167        let mut already_visited = HashMap::new();
168        let mut path = Vec::new();
169        for &key in nodes.keys() {
170            if !already_visited.contains_key(&key) {
171                print_node(
172                    &nodes,
173                    key,
174                    0,
175                    &mut visited,
176                    &mut vec![],
177                    &mut result,
178                    &mut path,
179                    &mut already_visited,
180                );
181            }
182        }
183
184        result
185    }
186
187    // FIXME: This is not possible unless sort can be reproduced.
188    fn tree_for_xml(&mut self) -> String {
189        String::new()
190    }
191}
192
193#[cfg_attr(miri, ignore)] // Unexplained hang
194#[test]
195#[cfg_attr(
196    feature = "tracing",
197    quick_tracing::init(test = "generate_tree_from_xml", stdio = false)
198)]
199fn should_create_tree() {
200    use crate::tests::ClassMap;
201
202    let s = include_str!("../../docs/handson_hex_dump/wisp_skeleton/skeleton.xml");
203    let mut classes: ClassMap = crate::from_str(s).unwrap();
204    let tree = classes.tree_for_bytes();
205    tracing::debug!("tree =\n{tree}");
206}
serde_hkx/tree.rs

serde_hkx/
tree.rs
