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

servo_xpath/
eval.rs
