servo_xpath/
value.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5use std::borrow::ToOwned;
6use std::collections::HashSet;
7use std::mem;
8
9use crate::Node;
10
11/// The primary types of values that an XPath expression returns as a result.
12#[derive(Debug)]
13pub enum Value<N: Node> {
14    Boolean(bool),
15    /// A IEEE-754 double-precision floating point number.
16    Number(f64),
17    String(String),
18    NodeSet(NodeSet<N>),
19}
20
21#[derive(Debug)]
22pub struct NodeSet<N: Node> {
23    nodes: Vec<N>,
24    is_sorted: bool,
25}
26
27impl<N: Node> Default for NodeSet<N> {
28    fn default() -> Self {
29        Self {
30            nodes: Default::default(),
31            is_sorted: false,
32        }
33    }
34}
35
36impl<N: Node> NodeSet<N> {
37    pub(crate) fn len(&self) -> usize {
38        self.nodes.len()
39    }
40
41    fn is_empty(&self) -> bool {
42        self.nodes.is_empty()
43    }
44
45    pub(crate) fn push(&mut self, node: N) {
46        self.is_sorted = false;
47        self.nodes.push(node);
48    }
49
50    pub(crate) fn extend<I>(&mut self, iter: I)
51    where
52        I: IntoIterator<Item = N>,
53    {
54        self.nodes.extend(iter);
55    }
56
57    /// Whether this set is known to be sorted in tree order.
58    ///
59    /// This method is pessimistic and will never look at the elements in the set.
60    /// As such, it *may* return `false` even if the set happens to be sorted.
61    pub(crate) fn is_sorted(&self) -> bool {
62        self.is_sorted || self.nodes.len() < 2
63    }
64
65    /// Assume that this set is sorted, without actually sorting it.
66    pub(crate) fn assume_sorted(&mut self, cx: &mut N::Context) {
67        debug_assert!(
68            self.nodes
69                .is_sorted_by(|a, b| a.compare_tree_order(cx, b).is_le())
70        );
71        self.is_sorted = true;
72    }
73
74    pub(crate) fn sort(&mut self, cx: &mut N::Context) {
75        if self.is_sorted() {
76            return;
77        }
78
79        // Using sort_unstable_by here is fine because duplicates won't appear in the final
80        // result anyways.
81        self.nodes
82            .sort_unstable_by(|a, b| a.compare_tree_order(cx, b));
83    }
84
85    pub(crate) fn iter(&self) -> impl Iterator<Item = &N> {
86        self.nodes.iter()
87    }
88
89    /// Return the first node in tree order that appears within this set.
90    ///
91    /// This method will not sort the set itself.
92    pub(crate) fn first(&self, cx: &mut N::Context) -> Option<N> {
93        if self.is_sorted() {
94            return self.nodes.first().cloned();
95        }
96
97        self.iter()
98            .min_by(|a, b| a.compare_tree_order(cx, b))
99            .cloned()
100    }
101
102    pub(crate) fn deduplicate(&mut self) {
103        let mut seen = HashSet::new();
104        self.nodes = mem::take(&mut self.nodes)
105            .into_iter()
106            .filter_map(|node| {
107                let opaque = node.to_opaque();
108                seen.insert(opaque).then_some(node)
109            })
110            .collect();
111    }
112
113    /// Retains only the elements specified by the predicate.
114    ///
115    /// In other words, remove all elements `e` for which `f(&e)` returns `false`.
116    /// This method operates in place, visiting each element exactly once in the
117    /// original order, and preserves the order of the retained elements.
118    pub(crate) fn retain<F>(&mut self, f: F)
119    where
120        F: FnMut(&N) -> bool,
121    {
122        self.nodes.retain(f)
123    }
124
125    pub(crate) fn reverse(&mut self) {
126        self.nodes = mem::take(&mut self.nodes).into_iter().rev().collect();
127    }
128}
129
130impl<N: Node> IntoIterator for NodeSet<N> {
131    type IntoIter = <Vec<N> as IntoIterator>::IntoIter;
132    type Item = <Vec<N> as IntoIterator>::Item;
133
134    fn into_iter(self) -> Self::IntoIter {
135        self.nodes.into_iter()
136    }
137}
138
139impl<N: Node> FromIterator<N> for NodeSet<N> {
140    fn from_iter<T: IntoIterator<Item = N>>(iter: T) -> Self {
141        Self {
142            nodes: iter.into_iter().collect(),
143            is_sorted: false,
144        }
145    }
146}
147
148pub(crate) fn parse_number_from_string(string: &str) -> f64 {
149    // https://www.w3.org/TR/1999/REC-xpath-19991116/#function-number:
150    // > a string that consists of optional whitespace followed by an optional minus sign followed
151    // > by a Number followed by whitespace is converted to the IEEE 754 number that is nearest
152    // > (according to the IEEE 754 round-to-nearest rule) to the mathematical value represented
153    // > by the string; any other string is converted to NaN
154
155    // The specification does not define what "whitespace" means exactly, we choose to trim only ascii whitespace,
156    // as that seems to be what other browsers do.
157    string.trim_ascii().parse().unwrap_or(f64::NAN)
158}
159
160/// Helper for `PartialEq<Value>` implementations
161fn num_vals<N: Node>(nodes: &NodeSet<N>) -> Vec<f64> {
162    nodes
163        .iter()
164        .map(|node| parse_number_from_string(&node.text_content()))
165        .collect()
166}
167
168impl<N: Node> Value<N> {
169    pub(crate) fn partial_eq(&self, cx: &mut N::Context, other: &Self) -> bool {
170        match (self, other) {
171            (Value::NodeSet(left_nodes), Value::NodeSet(right_nodes)) => {
172                let left_strings: HashSet<String> =
173                    left_nodes.iter().map(|node| node.text_content()).collect();
174                let right_strings: HashSet<String> =
175                    right_nodes.iter().map(|node| node.text_content()).collect();
176                !left_strings.is_disjoint(&right_strings)
177            },
178            (&Value::NodeSet(ref nodes), &Value::Number(val)) |
179            (&Value::Number(val), &Value::NodeSet(ref nodes)) => {
180                let numbers = num_vals(nodes);
181                numbers.contains(&val)
182            },
183            (&Value::NodeSet(ref nodes), &Value::String(ref string)) |
184            (&Value::String(ref string), &Value::NodeSet(ref nodes)) => nodes
185                .iter()
186                .map(|node| node.text_content())
187                .any(|text_content| &text_content == string),
188            (&Value::Boolean(_), _) | (_, &Value::Boolean(_)) => {
189                self.convert_to_boolean() == other.convert_to_boolean()
190            },
191            (&Value::Number(_), _) | (_, &Value::Number(_)) => {
192                self.convert_to_number(cx) == other.convert_to_number(cx)
193            },
194            _ => self.convert_to_string(cx) == other.convert_to_string(cx),
195        }
196    }
197
198    /// <https://www.w3.org/TR/1999/REC-xpath-19991116/#function-boolean>
199    pub fn convert_to_boolean(&self) -> bool {
200        match self {
201            Value::Boolean(boolean) => *boolean,
202            Value::Number(number) => *number != 0.0 && !number.is_nan(),
203            Value::String(string) => !string.is_empty(),
204            Value::NodeSet(nodeset) => !nodeset.is_empty(),
205        }
206    }
207
208    /// <https://www.w3.org/TR/1999/REC-xpath-19991116/#function-number>
209    pub fn convert_to_number(&self, cx: &mut N::Context) -> f64 {
210        match self {
211            Value::Boolean(boolean) => {
212                if *boolean {
213                    1.0
214                } else {
215                    0.0
216                }
217            },
218            Value::Number(number) => *number,
219            Value::String(string) => parse_number_from_string(string),
220            Value::NodeSet(_) => parse_number_from_string(&self.convert_to_string(cx)),
221        }
222    }
223
224    /// <https://www.w3.org/TR/1999/REC-xpath-19991116/#function-string>
225    pub fn convert_to_string(&self, cx: &mut N::Context) -> String {
226        match self {
227            Value::Boolean(value) => value.to_string(),
228            Value::Number(number) => {
229                if number.is_infinite() {
230                    if number.is_sign_negative() {
231                        "-Infinity".to_owned()
232                    } else {
233                        "Infinity".to_owned()
234                    }
235                } else if *number == 0.0 {
236                    // catches -0.0 also
237                    "0".into()
238                } else {
239                    number.to_string()
240                }
241            },
242            Value::String(string) => string.to_owned(),
243            Value::NodeSet(nodes) => nodes
244                .first(cx)
245                .as_ref()
246                .map(Node::text_content)
247                .unwrap_or_default(),
248        }
249    }
250}
251
252macro_rules! from_impl {
253    ($raw:ty, $variant:expr) => {
254        impl<N: Node> From<$raw> for Value<N> {
255            fn from(other: $raw) -> Self {
256                $variant(other)
257            }
258        }
259    };
260}
261
262from_impl!(bool, Value::Boolean);
263from_impl!(f64, Value::Number);
264from_impl!(String, Value::String);
265impl<'a, N: Node> From<&'a str> for Value<N> {
266    fn from(other: &'a str) -> Self {
267        Value::String(other.into())
268    }
269}
270
271macro_rules! partial_eq_impl {
272    ($raw:ty, $variant:pat => $b:expr) => {
273        impl<N: Node> PartialEq<$raw> for Value<N> {
274            fn eq(&self, other: &$raw) -> bool {
275                match *self {
276                    $variant => $b == other,
277                    _ => false,
278                }
279            }
280        }
281
282        impl<N: Node> PartialEq<Value<N>> for $raw {
283            fn eq(&self, other: &Value<N>) -> bool {
284                match *other {
285                    $variant => $b == self,
286                    _ => false,
287                }
288            }
289        }
290    };
291}
292
293partial_eq_impl!(bool, Value::Boolean(ref v) => v);
294partial_eq_impl!(f64, Value::Number(ref v) => v);
295partial_eq_impl!(String, Value::String(ref v) => v);
296partial_eq_impl!(&str, Value::String(ref v) => v);
297
298#[cfg(test)]
299mod tests {
300    use std::f64;
301
302    use crate::dummy_implementation;
303
304    type Value = super::Value<dummy_implementation::DummyNode>;
305
306    #[test]
307    fn string_value_to_number() {
308        let cx = &mut ();
309        assert_eq!(Value::String("42.123".into()).convert_to_number(cx), 42.123);
310        assert_eq!(Value::String(" 42\n".into()).convert_to_number(cx), 42.);
311        assert!(
312            Value::String("totally-invalid".into())
313                .convert_to_number(cx)
314                .is_nan()
315        );
316
317        // U+2004 is non-ascii whitespace, which should be rejected
318        assert!(
319            Value::String("\u{2004}42".into())
320                .convert_to_number(cx)
321                .is_nan()
322        );
323    }
324
325    #[test]
326    fn number_value_to_string() {
327        let cx = &mut ();
328        assert_eq!(Value::Number(f64::NAN).convert_to_string(cx), "NaN");
329        assert_eq!(Value::Number(0.).convert_to_string(cx), "0");
330        assert_eq!(Value::Number(-0.).convert_to_string(cx), "0");
331        assert_eq!(
332            Value::Number(f64::INFINITY).convert_to_string(cx),
333            "Infinity"
334        );
335        assert_eq!(
336            Value::Number(f64::NEG_INFINITY).convert_to_string(cx),
337            "-Infinity"
338        );
339        assert_eq!(Value::Number(42.0).convert_to_string(cx), "42");
340        assert_eq!(Value::Number(-42.0).convert_to_string(cx), "-42");
341        assert_eq!(Value::Number(0.75).convert_to_string(cx), "0.75");
342        assert_eq!(Value::Number(-0.75).convert_to_string(cx), "-0.75");
343    }
344
345    #[test]
346    fn boolean_value_to_string() {
347        let cx = &mut ();
348        assert_eq!(Value::Boolean(false).convert_to_string(cx), "false");
349        assert_eq!(Value::Boolean(true).convert_to_string(cx), "true");
350    }
351}
servo_xpath/value.rs

servo_xpath/
value.rs
