servo_xpath/
eval.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::iter;
6
7use markup5ever::{QualName, local_name, ns};
8
9use crate::ast::{
10    Axis, BinaryOperator, Expression, FilterExpression, KindTest, Literal, LocationStepExpression,
11    NodeTest, PathExpression, PredicateListExpression,
12};
13use crate::context::PredicateCtx;
14use crate::{
15    Attribute, Dom, Element, Error, EvaluationCtx, Node, NodeSet, ProcessingInstruction, Value,
16};
17
18pub(crate) fn try_extract_nodeset<N: Node>(v: Value<N>) -> Result<NodeSet<N>, Error> {
19    match v {
20        Value::NodeSet(node_set) => Ok(node_set),
21        _ => Err(Error::NotANodeset),
22    }
23}
24
25impl Expression {
26    pub(crate) fn evaluate<D: Dom>(
27        &self,
28        cx: &mut D::Context,
29        context: &EvaluationCtx<D>,
30    ) -> Result<Value<D::Node>, Error> {
31        match self {
32            // And/Or expression are separated because they can sometimes be evaluated
33            // without evaluating both operands.
34            Expression::Binary(left, BinaryOperator::And, right) => {
35                let left_bool = left.evaluate(cx, context)?.convert_to_boolean();
36                let v = left_bool && right.evaluate(cx, context)?.convert_to_boolean();
37                Ok(Value::Boolean(v))
38            },
39            Expression::Binary(left, BinaryOperator::Or, right) => {
40                let left_bool = left.evaluate(cx, context)?.convert_to_boolean();
41                let v = left_bool || right.evaluate(cx, context)?.convert_to_boolean();
42                Ok(Value::Boolean(v))
43            },
44            Expression::Binary(left, binary_operator, right) => {
45                let left_value = left.evaluate(cx, context)?;
46                let right_value = right.evaluate(cx, context)?;
47
48                let value = match binary_operator {
49                    BinaryOperator::Equal => (left_value == right_value).into(),
50                    BinaryOperator::NotEqual => (left_value != right_value).into(),
51                    BinaryOperator::LessThan => {
52                        (left_value.convert_to_number() < right_value.convert_to_number()).into()
53                    },
54                    BinaryOperator::GreaterThan => {
55                        (left_value.convert_to_number() > right_value.convert_to_number()).into()
56                    },
57                    BinaryOperator::LessThanOrEqual => {
58                        (left_value.convert_to_number() <= right_value.convert_to_number()).into()
59                    },
60                    BinaryOperator::GreaterThanOrEqual => {
61                        (left_value.convert_to_number() >= right_value.convert_to_number()).into()
62                    },
63                    BinaryOperator::Add => {
64                        (left_value.convert_to_number() + right_value.convert_to_number()).into()
65                    },
66                    BinaryOperator::Subtract => {
67                        (left_value.convert_to_number() - right_value.convert_to_number()).into()
68                    },
69                    BinaryOperator::Multiply => {
70                        (left_value.convert_to_number() * right_value.convert_to_number()).into()
71                    },
72                    BinaryOperator::Divide => {
73                        (left_value.convert_to_number() / right_value.convert_to_number()).into()
74                    },
75                    BinaryOperator::Modulo => {
76                        (left_value.convert_to_number() % right_value.convert_to_number()).into()
77                    },
78                    BinaryOperator::Union => {
79                        let as_nodes = |cx: &mut D::Context, e: &Expression| {
80                            e.evaluate(cx, context).and_then(try_extract_nodeset)
81                        };
82                        let mut left_nodes = as_nodes(cx, left)?;
83                        let right_nodes = as_nodes(cx, right)?;
84
85                        left_nodes.extend(right_nodes);
86                        left_nodes.sort();
87                        Value::NodeSet(left_nodes)
88                    },
89                    _ => unreachable!("And/Or were handled above"),
90                };
91
92                Ok(value)
93            },
94            Expression::Negate(expr) => {
95                let value = -expr.evaluate(cx, context)?.convert_to_number();
96                Ok(value.into())
97            },
98            Expression::Path(path_expr) => path_expr.evaluate(cx, context),
99            Expression::LocationStep(location_step_expression) => {
100                location_step_expression.evaluate(cx, context)
101            },
102            Expression::Filter(filter_expression) => filter_expression.evaluate(cx, context),
103            Expression::Literal(literal) => Ok(literal.evaluate::<D>()),
104            Expression::Function(function) => function.evaluate(cx, context),
105            Expression::ContextItem => {
106                let mut result = NodeSet::default();
107                result.push(context.context_node.clone());
108                Ok(Value::NodeSet(result))
109            },
110            Expression::Variable(_) => Err(Error::CannotUseVariables),
111        }
112    }
113}
114
115impl PathExpression {
116    fn evaluate<D: Dom>(
117        &self,
118        cx: &mut D::Context,
119        context: &EvaluationCtx<D>,
120    ) -> Result<Value<D::Node>, Error> {
121        // Use root node for absolute paths, context_node otherwise
122        let starting_node = if self.is_absolute {
123            context.context_node.get_root_node()
124        } else {
125            context.context_node.clone()
126        };
127
128        // If path starts with '//', add an implicit descendant-or-self::node() step
129        let mut current_nodes = NodeSet::default();
130        if self.has_implicit_descendant_or_self_step {
131            for node in starting_node.traverse_preorder() {
132                current_nodes.push(node);
133            }
134        } else {
135            current_nodes.push(starting_node);
136        }
137        current_nodes.assume_sorted();
138
139        let have_multiple_steps = self.steps.len() > 1;
140
141        for step_expression in &self.steps {
142            let mut next_nodes = NodeSet::default();
143            for node in current_nodes {
144                let step_context = context.subcontext_for_node(node.clone());
145                let step_result = step_expression.evaluate(cx, &step_context)?;
146                match (have_multiple_steps, step_result) {
147                    (_, Value::NodeSet(nodes)) => {
148                        // as long as we evaluate to nodesets, keep going
149                        next_nodes.extend(nodes);
150                    },
151                    (false, value) => {
152                        return Ok(value);
153                    },
154                    (true, value) => {
155                        log::debug!(
156                            "Expected nodeset from step evaluation, got: {:?} node: {:?}, step: {:?}",
157                            value,
158                            node,
159                            step_expression
160                        );
161                        return Ok(value);
162                    },
163                }
164            }
165            current_nodes = next_nodes;
166        }
167
168        Ok(Value::NodeSet(current_nodes))
169    }
170}
171
172#[derive(Debug, Eq, PartialEq)]
173pub(crate) enum NameTestComparisonMode {
174    /// Namespaces must match exactly
175    XHtml,
176    /// Missing namespace information is treated as the HTML namespace
177    Html,
178}
179
180pub(crate) fn element_name_test(
181    expected_name: &QualName,
182    actual_name: QualName,
183    comparison_mode: NameTestComparisonMode,
184) -> bool {
185    if expected_name.prefix.is_none() && expected_name.local == local_name!("*") {
186        return true;
187    }
188
189    let should_compare_namespaces =
190        comparison_mode == NameTestComparisonMode::XHtml || expected_name.ns != ns!();
191    if should_compare_namespaces && expected_name.ns != actual_name.ns {
192        return false;
193    }
194
195    if expected_name.local == local_name!("*") {
196        return true;
197    }
198
199    expected_name.local == actual_name.local
200}
201
202fn apply_node_test<D: Dom>(test: &NodeTest, node: &D::Node) -> Result<bool, Error> {
203    let result = match test {
204        NodeTest::Name(expected_name) => {
205            if let Some(element) = node.as_element() {
206                let comparison_mode = if element.is_html_element_in_html_document() {
207                    NameTestComparisonMode::Html
208                } else {
209                    NameTestComparisonMode::XHtml
210                };
211                let actual_name =
212                    QualName::new(element.prefix(), element.namespace(), element.local_name());
213                element_name_test(expected_name, actual_name, comparison_mode)
214            } else if let Some(attribute) = node.as_attribute() {
215                let actual_name = QualName::new(
216                    attribute.prefix(),
217                    attribute.namespace(),
218                    attribute.local_name(),
219                );
220                // attributes are always compared with strict namespace matching
221                let comparison_mode = NameTestComparisonMode::XHtml;
222                element_name_test(expected_name, actual_name, comparison_mode)
223            } else {
224                false
225            }
226        },
227        NodeTest::Wildcard => node.as_element().is_some(),
228        NodeTest::Kind(kind) => match kind {
229            KindTest::PI(target) => {
230                if let Some(processing_instruction) = node.as_processing_instruction() {
231                    match (target, processing_instruction.target()) {
232                        (Some(target_name), node_target_name)
233                            if target_name == &node_target_name.to_string() =>
234                        {
235                            true
236                        },
237                        (Some(_), _) => false,
238                        (None, _) => true,
239                    }
240                } else {
241                    false
242                }
243            },
244            KindTest::Comment => node.is_comment(),
245            KindTest::Text => node.is_text(),
246            KindTest::Node => true,
247        },
248    };
249    Ok(result)
250}
251
252impl LocationStepExpression {
253    fn evaluate<D: Dom>(
254        &self,
255        cx: &mut D::Context,
256        context: &EvaluationCtx<D>,
257    ) -> Result<Value<D::Node>, Error> {
258        let nodes: NodeSet<D::Node> = match self.axis {
259            Axis::Child => context.context_node.children().collect(),
260            Axis::Descendant => context.context_node.traverse_preorder().skip(1).collect(),
261            Axis::Parent => vec![context.context_node.parent()]
262                .into_iter()
263                .flatten()
264                .collect(),
265            Axis::Ancestor => context.context_node.inclusive_ancestors().skip(1).collect(),
266            Axis::Following => context.context_node.following_nodes().skip(1).collect(),
267            Axis::Preceding => context.context_node.preceding_nodes().skip(1).collect(),
268            Axis::FollowingSibling => context.context_node.following_siblings().collect(),
269            Axis::PrecedingSibling => context.context_node.preceding_siblings().collect(),
270            Axis::Attribute => {
271                if let Some(element) = context.context_node.as_element() {
272                    element
273                        .attributes(cx)
274                        .map(|attribute| attribute.as_node())
275                        .collect()
276                } else {
277                    Default::default()
278                }
279            },
280            Axis::Self_ => iter::once(context.context_node.clone()).collect(),
281            Axis::DescendantOrSelf => context.context_node.traverse_preorder().collect(),
282            Axis::AncestorOrSelf => context.context_node.inclusive_ancestors().collect(),
283            Axis::Namespace => Default::default(), // Namespace axis is not commonly implemented
284        };
285
286        // Filter nodes according to the step's node_test. Will error out if any NodeTest
287        // application errors out.
288        // FIXME: Invent something like try_retain and use it here
289        let filtered_nodes: NodeSet<D::Node> = nodes
290            .into_iter()
291            .filter_map(|node| match apply_node_test::<D>(&self.node_test, &node) {
292                Ok(false) => None,
293                Ok(true) => Some(Ok(node)),
294                Err(error) => Some(Err(error)),
295            })
296            .collect::<Result<NodeSet<_>, _>>()?;
297
298        let mut filtered_nodes = if self.predicate_list.predicates.is_empty() {
299            filtered_nodes
300        } else {
301            // Apply predicates
302            self.predicate_list.apply::<D>(cx, filtered_nodes)
303        };
304
305        // Enforce tree order between nodes in the list
306        if matches!(
307            self.axis,
308            Axis::Child |
309                Axis::Descendant |
310                Axis::Parent |
311                Axis::Following |
312                Axis::FollowingSibling |
313                Axis::Attribute |
314                Axis::Self_ |
315                Axis::DescendantOrSelf
316        ) {
317            // The elements on these axis values are already in tree order
318            filtered_nodes.assume_sorted();
319        } else {
320            // The elements on these axis values are in inverse tree order
321            filtered_nodes.reverse();
322            filtered_nodes.assume_sorted();
323        };
324
325        Ok(Value::NodeSet(filtered_nodes))
326    }
327}
328
329impl PredicateListExpression {
330    fn apply<D: Dom>(
331        &self,
332        cx: &mut D::Context,
333        mut matched_nodes: NodeSet<D::Node>,
334    ) -> NodeSet<D::Node> {
335        for predicate_expr in &self.predicates {
336            let size = matched_nodes.len();
337
338            // 1-based position, per XPath spec
339            let mut position = 1;
340            matched_nodes.retain(|node| {
341                let predicate_ctx: EvaluationCtx<D> = EvaluationCtx {
342                    context_node: node.clone(),
343                    predicate_ctx: Some(PredicateCtx {
344                        index: position,
345                        size,
346                    }),
347                };
348                let eval_result = predicate_expr.evaluate(cx, &predicate_ctx);
349
350                let keep = match eval_result {
351                    Ok(Value::Number(number)) => position as f64 == number,
352                    Ok(Value::Boolean(boolean)) => boolean,
353                    Ok(value) => value.convert_to_boolean(),
354                    Err(_) => false,
355                };
356                position += 1;
357
358                keep
359            });
360        }
361
362        matched_nodes
363    }
364}
365
366impl FilterExpression {
367    fn evaluate<D: Dom>(
368        &self,
369        cx: &mut D::Context,
370        context: &EvaluationCtx<D>,
371    ) -> Result<Value<D::Node>, Error> {
372        debug_assert!(!self.predicates.predicates.is_empty());
373
374        let Value::NodeSet(node_set) = self.expression.evaluate(cx, context)? else {
375            // You can't use filtering expressions `[]` on other than node-sets
376            return Err(Error::NotANodeset);
377        };
378        Ok(Value::NodeSet(self.predicates.apply::<D>(cx, node_set)))
379    }
380}
381
382impl Literal {
383    fn evaluate<D: Dom>(&self) -> Value<D::Node> {
384        match self {
385            Literal::Integer(integer) => Value::Number(*integer as f64),
386            Literal::Decimal(decimal) => Value::Number(*decimal),
387            Literal::String(s) => Value::String(s.into()),
388        }
389    }
390}
servo_xpath/eval.rs

servo_xpath/
eval.rs
