xsd_schema/xpath/
tree_comparer.rs

1//! XPath tree comparison helpers.
2//!
3//! Port of `xpath2/XPath20Api/XPath20Api/TreeComparer.cs`.
4//! Aligns with `DOM_NAVIGATOR_DESIGN.md` and `XML_NODE_ITERATOR_DESIGN.md`.
5
6use crate::types::XmlTypeCode;
7use crate::types::{normalize_whitespace, WhitespaceMode, XmlAtomicValue, XmlValue, XmlValueKind};
8
9use super::ast::BinaryOpKind;
10use super::error::XPathError;
11use super::iterator::{XmlItemRef, XmlNodeIterator};
12use super::operators::eval_binary;
13use super::string_ops::is_xml_whitespace;
14use super::{DomNavigator, DomNodeType};
15
16/// Compares XPath nodes and sequences for deep equality.
17#[derive(Debug, Clone, Default)]
18pub struct TreeComparer {
19    pub ignore_whitespace: bool,
20}
21
22impl TreeComparer {
23    pub fn new() -> Self {
24        Self::default()
25    }
26
27    pub fn with_ignore_whitespace(ignore_whitespace: bool) -> Self {
28        Self { ignore_whitespace }
29    }
30
31    fn text_equal(&self, left: &str, right: &str) -> bool {
32        if self.ignore_whitespace {
33            normalize_whitespace(left, WhitespaceMode::Collapse)
34                == normalize_whitespace(right, WhitespaceMode::Collapse)
35        } else {
36            left == right
37        }
38    }
39
40    fn normalized_item_value(&self, value: &XmlValue) -> XmlValue {
41        match value.type_code {
42            XmlTypeCode::UntypedAtomic | XmlTypeCode::AnyUri => {
43                XmlValue::string(value.to_string_value())
44            }
45            _ => value.clone(),
46        }
47    }
48
49    fn is_nan_value(&self, value: &XmlValue) -> bool {
50        match &value.value {
51            XmlValueKind::Atomic(XmlAtomicValue::Float(f)) => f.is_nan(),
52            XmlValueKind::Atomic(XmlAtomicValue::Double(d)) => d.is_nan(),
53            _ => false,
54        }
55    }
56
57    fn values_equal_or_nan(&self, left: &XmlValue, right: &XmlValue) -> bool {
58        if self.is_nan_value(left) && self.is_nan_value(right) {
59            return true;
60        }
61        left == right
62    }
63
64    fn item_equal(&self, left: &XmlValue, right: &XmlValue) -> bool {
65        let left = self.normalized_item_value(left);
66        let right = self.normalized_item_value(right);
67
68        if self.values_equal_or_nan(&left, &right) {
69            return true;
70        }
71
72        if let Ok(result) = eval_binary(BinaryOpKind::ValueEq, &left, &right) {
73            return result.as_boolean().unwrap_or(false);
74        }
75
76        false
77    }
78
79    fn is_whitespace_node<N: DomNavigator>(&self, nav: &N) -> bool {
80        if !self.ignore_whitespace || !nav.node_type().is_text_like() {
81            return false;
82        }
83        nav.value().chars().all(is_xml_whitespace)
84    }
85
86    fn node_equal<N: DomNavigator>(&self, left: &N, right: &N) -> bool {
87        if left.node_type() != right.node_type() {
88            return false;
89        }
90
91        match left.node_type() {
92            DomNodeType::Element => self.element_equal(left, right),
93            DomNodeType::Attribute => self.attribute_equal(left, right),
94            DomNodeType::Text
95            | DomNodeType::Whitespace
96            | DomNodeType::SignificantWhitespace
97            | DomNodeType::Comment => self.text_equal(&left.value(), &right.value()),
98            DomNodeType::ProcessingInstruction => self.processing_instruction_equal(left, right),
99            _ => self.deep_equal(left, right),
100        }
101    }
102
103    fn element_equal<N: DomNavigator>(&self, left: &N, right: &N) -> bool {
104        if left.local_name() != right.local_name() || left.namespace_uri() != right.namespace_uri()
105        {
106            return false;
107        }
108
109        let mut left_nav = left.clone();
110        let mut right_nav = right.clone();
111
112        self.element_attributes_equal(&mut left_nav, &mut right_nav) && self.deep_equal(left, right)
113    }
114
115    fn element_attributes_equal<N: DomNavigator>(&self, left: &mut N, right: &mut N) -> bool {
116        if left.has_attributes() != right.has_attributes() {
117            return false;
118        }
119
120        if !left.has_attributes() {
121            return true;
122        }
123
124        let left_count = count_attributes(left);
125        let right_count = count_attributes(right);
126        if left_count != right_count {
127            return false;
128        }
129
130        if left.move_to_first_attribute() {
131            loop {
132                let mut found = false;
133                if right.move_to_first_attribute() {
134                    loop {
135                        if self.attribute_equal(left, right) {
136                            found = true;
137                            break;
138                        }
139                        if !right.move_to_next_attribute() {
140                            break;
141                        }
142                    }
143                    right.move_to_parent();
144                }
145
146                if !found {
147                    left.move_to_parent();
148                    return false;
149                }
150
151                if !left.move_to_next_attribute() {
152                    break;
153                }
154            }
155            left.move_to_parent();
156        }
157
158        true
159    }
160
161    fn processing_instruction_equal<N: DomNavigator>(&self, left: &N, right: &N) -> bool {
162        left.local_name() == right.local_name() && left.value() == right.value()
163    }
164
165    fn attribute_equal<N: DomNavigator>(&self, left: &N, right: &N) -> bool {
166        if left.local_name() != right.local_name() || left.namespace_uri() != right.namespace_uri()
167        {
168            return false;
169        }
170
171        // Attributes cannot be Nilled/Absent; fall back to untyped on error.
172        let left_value = crate::xpath::atomize::atomize_node(left)
173            .ok()
174            .flatten()
175            .unwrap_or_else(|| XmlValue::untyped(left.value()));
176        let right_value = crate::xpath::atomize::atomize_node(right)
177            .ok()
178            .flatten()
179            .unwrap_or_else(|| XmlValue::untyped(right.value()));
180        self.values_equal_or_nan(&left_value, &right_value)
181    }
182
183    /// Deep equality for two navigator positions (node comparison).
184    pub fn deep_equal<N: DomNavigator>(&self, left: &N, right: &N) -> bool {
185        let mut left_iter = ChildIter::new(left.clone());
186        let mut right_iter = ChildIter::new(right.clone());
187
188        loop {
189            let left_child = self.next_significant_child(&mut left_iter);
190            let right_child = self.next_significant_child(&mut right_iter);
191
192            match (left_child, right_child) {
193                (None, None) => return true,
194                (Some(_), None) | (None, Some(_)) => return false,
195                (Some(left_node), Some(right_node)) => {
196                    if !self.node_equal(&left_node, &right_node) {
197                        return false;
198                    }
199                }
200            }
201        }
202    }
203
204    /// Deep equality for two XPath item iterators.
205    pub fn deep_equal_iter<I>(&self, left: &I, right: &I) -> Result<bool, XPathError>
206    where
207        I: XmlNodeIterator,
208    {
209        let mut left_iter = left.clone();
210        let mut right_iter = right.clone();
211
212        loop {
213            let left_has = left_iter.move_next()?;
214            let right_has = right_iter.move_next()?;
215            if left_has != right_has {
216                return Ok(false);
217            }
218            if !left_has {
219                return Ok(true);
220            }
221
222            let left_item = left_iter.current();
223            let right_item = right_iter.current();
224
225            match (left_item, right_item) {
226                (Some(XmlItemRef::Node(left_node)), Some(XmlItemRef::Node(right_node))) => {
227                    if !self.node_equal(left_node, right_node) {
228                        return Ok(false);
229                    }
230                }
231                (Some(XmlItemRef::Atomic(left_value)), Some(XmlItemRef::Atomic(right_value))) => {
232                    if !self.item_equal(left_value, right_value) {
233                        return Ok(false);
234                    }
235                }
236                _ => return Ok(false),
237            }
238        }
239    }
240
241    fn next_significant_child<N: DomNavigator>(&self, iter: &mut ChildIter<N>) -> Option<N> {
242        let mut current = iter.next();
243        while let Some(ref nav) = current {
244            if !self.is_whitespace_node(nav) {
245                return current;
246            }
247            current = iter.next();
248        }
249        None
250    }
251}
252
253fn count_attributes<N: DomNavigator>(nav: &mut N) -> usize {
254    let mut count = 0;
255    if nav.move_to_first_attribute() {
256        loop {
257            count += 1;
258            if !nav.move_to_next_attribute() {
259                break;
260            }
261        }
262        nav.move_to_parent();
263    }
264    count
265}
266
267#[derive(Clone)]
268struct ChildIter<N: DomNavigator> {
269    nav: N,
270    started: bool,
271    done: bool,
272}
273
274impl<N: DomNavigator> ChildIter<N> {
275    fn new(nav: N) -> Self {
276        Self {
277            nav,
278            started: false,
279            done: false,
280        }
281    }
282
283    fn next(&mut self) -> Option<N> {
284        if self.done {
285            return None;
286        }
287
288        if !self.started {
289            self.started = true;
290            if !self.nav.move_to_first_child() {
291                self.done = true;
292                return None;
293            }
294            return Some(self.nav.clone());
295        }
296
297        if self.nav.move_to_next_sibling() {
298            Some(self.nav.clone())
299        } else {
300            self.done = true;
301            None
302        }
303    }
304}
305
306#[cfg(test)]
307mod tests {
308    use super::*;
309
310    use num_bigint::BigInt;
311    use rust_decimal::Decimal;
312
313    use crate::navigator::RoXmlNavigator;
314    use crate::xpath::iterator::{VecNodeIterator, XmlItem};
315
316    #[test]
317    fn test_deep_equal_ignores_whitespace_nodes() {
318        let comparer = TreeComparer::with_ignore_whitespace(true);
319        let doc1 = roxmltree::Document::parse("<root>\n  <a>1</a>\n  <b>2</b>\n</root>")
320            .expect("parse xml");
321        let doc2 = roxmltree::Document::parse("<root><a>1</a><b>2</b></root>").expect("parse xml");
322        let nav1 = RoXmlNavigator::new(&doc1);
323        let nav2 = RoXmlNavigator::new(&doc2);
324
325        assert!(comparer.deep_equal(&nav1, &nav2));
326    }
327
328    #[test]
329    fn test_deep_equal_detects_whitespace_when_enabled() {
330        let comparer = TreeComparer::new();
331        let doc1 = roxmltree::Document::parse("<root>\n  <a>1</a>\n</root>").expect("parse xml");
332        let doc2 = roxmltree::Document::parse("<root><a>1</a></root>").expect("parse xml");
333        let nav1 = RoXmlNavigator::new(&doc1);
334        let nav2 = RoXmlNavigator::new(&doc2);
335
336        assert!(!comparer.deep_equal(&nav1, &nav2));
337    }
338
339    #[test]
340    fn test_deep_equal_attributes_order_insensitive() {
341        let comparer = TreeComparer::new();
342        let doc1 = roxmltree::Document::parse("<root b=\"2\" a=\"1\"/>").expect("parse xml");
343        let doc2 = roxmltree::Document::parse("<root a=\"1\" b=\"2\"/>").expect("parse xml");
344        let nav1 = RoXmlNavigator::new(&doc1);
345        let nav2 = RoXmlNavigator::new(&doc2);
346
347        assert!(comparer.deep_equal(&nav1, &nav2));
348    }
349
350    #[test]
351    fn test_deep_equal_iter_uses_value_eq() {
352        let comparer = TreeComparer::new();
353        let left: VecNodeIterator<RoXmlNavigator<'static>> =
354            VecNodeIterator::new(vec![XmlItem::Atomic(XmlValue::integer(BigInt::from(1)))]);
355        let right: VecNodeIterator<RoXmlNavigator<'static>> =
356            VecNodeIterator::new(vec![XmlItem::Atomic(XmlValue::decimal(Decimal::new(1, 0)))]);
357
358        assert!(comparer.deep_equal_iter(&left, &right).unwrap());
359    }
360
361    #[test]
362    fn test_deep_equal_iter_nan() {
363        let comparer = TreeComparer::new();
364        let left: VecNodeIterator<RoXmlNavigator<'static>> =
365            VecNodeIterator::new(vec![XmlItem::Atomic(XmlValue::double(f64::NAN))]);
366        let right: VecNodeIterator<RoXmlNavigator<'static>> =
367            VecNodeIterator::new(vec![XmlItem::Atomic(XmlValue::float(f32::NAN))]);
368
369        assert!(comparer.deep_equal_iter(&left, &right).unwrap());
370    }
371}
xsd_schema/xpath/tree_comparer.rs

xsd_schema/xpath/
tree_comparer.rs
