1use std::borrow::Cow;
7use std::cell::{Cell, RefCell};
8use std::collections::{HashMap, HashSet};
9
10use parsec::{self as html, NodeId};
11
12use crate::index::{CDATA, COMMENT, ELEMENT, PI, TEXT};
13use crate::parser::{Axis, Expr, NodeTest, Op, Step};
14use crate::{Doc, Extensions, Item, Value, XML_NS, XValue};
15
16pub const WORK_LIMIT: u64 = 1 << 27;
24
25struct Context<'a, 'v> {
26 item: Item,
27 position: usize,
28 size: usize,
29 doc: Doc<'a>,
30 root: NodeId,
31 vars: &'v [(String, XValue)],
32 namespaces: &'v [(String, String)],
33 kept: &'v RefCell<Kept>,
34 ext: &'v dyn Extensions,
35 spent: &'v Cell<u64>,
37 limit: u64,
38 nested: bool,
40}
41
42type Kept = HashMap<(usize, (u32, u32)), Scalar>;
45
46#[derive(Debug, Clone, Copy)]
47enum Scalar {
48 Num(f64),
49 Bool(bool),
50}
51
52type Result<T> = std::result::Result<T, String>;
53
54fn text<'a>(s: String) -> Value<'a> {
55 Value::Str(Cow::Owned(s))
56}
57
58pub(crate) fn run<'a>(
60 expr: &Expr,
61 doc: Doc<'a>,
62 scope: NodeId,
63 vars: &[(String, XValue)],
64 namespaces: &[(String, String)],
65 ext: &dyn Extensions,
66 limit: u64,
67) -> Result<Value<'a>> {
68 let mut root = scope;
71 while let Some(up) = doc.tree.parent(root) {
72 root = up;
73 }
74 if doc.index.order(root) == u32::MAX {
75 return Err(format!(
76 "the top of node {scope}'s tree, node {root}, isn't in the index"
77 ));
78 }
79 let kept = RefCell::default();
80 let spent = Cell::new(0);
81 let ctx = Context {
82 item: Item::Node(scope),
83 position: 1,
84 size: 1,
85 doc,
86 root,
87 vars,
88 namespaces,
89 kept: &kept,
90 ext,
91 spent: &spent,
92 limit,
93 nested: false,
94 };
95 eval(expr, &ctx)
96}
97
98impl<'a> Context<'a, '_> {
99 fn spend(&self, units: usize) -> Result<()> {
101 let spent = self.spent.get().saturating_add(units as u64);
102 self.spent.set(spent);
103 if spent > self.limit {
104 return Err(format!(
105 "the query needs more than {} steps on this document, so it was stopped",
106 self.limit
107 ));
108 }
109 Ok(())
110 }
111
112 fn charge_text(&self, bytes: usize) {
114 let units = (bytes / 16) as u64;
115 self.spent.set(self.spent.get().saturating_add(units));
116 }
117
118 fn order(&self, n: NodeId) -> u32 {
119 self.doc.index.order(n)
120 }
121
122 fn key(&self, item: &Item) -> (u32, u32) {
125 match item {
126 Item::Node(n) => (self.order(*n), 0),
127 Item::Attr { owner, index, .. } => (self.order(*owner), index + 1),
128 }
129 }
130
131 fn kind(&self, n: NodeId) -> u8 {
132 self.doc.index.kind_at(self.order(n))
133 }
134
135 fn data(&self, n: NodeId) -> &'a str {
137 match self.doc.tree.kind(n) {
138 html::Kind::Text(t) | html::Kind::Cdata(t) | html::Kind::Comment(t) => t,
139 html::Kind::ProcessingInstruction { data, .. } => data,
140 _ => "",
141 }
142 }
143
144 fn string_value(&self, item: &Item) -> Cow<'a, str> {
145 let n = match item {
146 Item::Attr { owner, index, .. } => {
147 return Cow::Borrowed(self.doc.attr_at(*owner, *index).1);
148 }
149 Item::Node(n) => *n,
150 };
151 let index = self.doc.index;
152 let at = self.order(n);
153 match index.kind_at(at) {
154 TEXT | CDATA | COMMENT | PI => {
155 let data = self.data(n);
156 self.charge_text(data.len());
157 Cow::Borrowed(data)
158 }
159 _ => {
160 let end = index.end_of(at);
162 self.spent
163 .set(self.spent.get().saturating_add((end - at) as u64));
164 let mut out = Cow::Borrowed("");
166 for j in at + 1..end {
167 if matches!(index.kind_at(j), TEXT | CDATA) {
168 let piece = self.data(index.node_at(j));
169 self.charge_text(piece.len());
172 if out.is_empty() {
173 out = Cow::Borrowed(piece);
174 } else {
175 out.to_mut().push_str(piece);
176 }
177 }
178 }
179 out
180 }
181 }
182 }
183
184 fn qualified_name(&self, n: NodeId) -> &'a str {
186 self.doc.tree.lower_name(n).unwrap_or("")
187 }
188
189 fn tag(&self, n: NodeId) -> Option<&'a str> {
191 let name = self.doc.tree.lower_name(n)?;
192 if self.doc.is_xml() {
193 return Some(name.split_once(':').map_or(name, |(_, local)| local));
194 }
195 Some(name)
196 }
197
198 fn ns_id(&self, n: NodeId) -> u32 {
199 self.doc.names.map_or(0, |names| names.ns_of(n))
200 }
201
202 fn pi_target(&self, n: NodeId) -> Option<&'a str> {
203 match self.doc.tree.kind(n) {
204 html::Kind::ProcessingInstruction { target, .. } => Some(target),
205 _ => None,
206 }
207 }
208
209 fn name(&self, item: &Item) -> &'a str {
211 match item {
212 Item::Node(n) => match self.pi_target(*n) {
213 Some(target) => target,
214 None => self.qualified_name(*n),
215 },
216 Item::Attr { owner, index, .. } => self.doc.attr_at(*owner, *index).0,
217 }
218 }
219
220 fn local_name(&self, item: &Item) -> &'a str {
222 let name = self.name(item);
223 match name.split_once(':') {
225 Some((_, local)) if self.doc.is_xml() => local,
226 _ => name,
227 }
228 }
229
230 fn namespace_uri(&self, item: &Item) -> &'a str {
231 let Some(names) = self.doc.names else {
232 return "";
233 };
234 match item {
235 Item::Node(n) => names.uri(names.ns_of(*n)),
236 Item::Attr { ns, .. } => names.uri(*ns),
237 }
238 }
239
240 fn tree_range(&self) -> (u32, u32) {
243 let top = self.order(self.root);
244 (top, self.doc.index.end_of(top))
245 }
246}
247
248const RED_ZONE: usize = 64 * 1024;
252const GROW: usize = 1024 * 1024;
253
254fn eval<'a>(expr: &Expr, ctx: &Context<'a, '_>) -> Result<Value<'a>> {
255 stacker::maybe_grow(RED_ZONE, GROW, || eval_here(expr, ctx))
256}
257
258fn eval_here<'a>(expr: &Expr, ctx: &Context<'a, '_>) -> Result<Value<'a>> {
259 Ok(match expr {
260 Expr::Literal(s) => text(s.clone()),
261 Expr::Number(n) => Value::Num(*n),
262 Expr::Variable(name) => match ctx.vars.iter().find(|(k, _)| k == name) {
263 Some((_, XValue::Str(s))) => text(s.clone()),
264 Some((_, XValue::Num(n))) => Value::Num(*n),
265 Some((_, XValue::Bool(b))) => Value::Bool(*b),
266 None => return Err(format!("no value given for ${name}")),
267 },
268 Expr::Negate(e) => Value::Num(-number(eval(e, ctx)?, ctx)),
269 Expr::Binary(op, l, r) => binary(*op, l, r, ctx)?,
270 Expr::Union(l, r) => {
271 let (Value::Nodes(mut a), Value::Nodes(b)) = (eval(l, ctx)?, eval(r, ctx)?) else {
272 return Err("both sides of | must be node-sets".into());
273 };
274 a.extend(b);
275 Value::Nodes(in_document_order(a, ctx))
276 }
277 Expr::Call(name, args) => call(name, args, ctx)?,
278 Expr::Memo(e, slot) => {
279 let key = (*slot, ctx.key(&ctx.item));
280 let known = ctx.kept.borrow().get(&key).copied();
282 let scalar = match known {
283 Some(s) => s,
284 None => {
285 let s = match eval(e, ctx)? {
286 Value::Num(n) => Scalar::Num(n),
287 other => Scalar::Bool(boolean(&other)),
288 };
289 ctx.kept.borrow_mut().insert(key, s);
290 s
291 }
292 };
293 match scalar {
294 Scalar::Num(n) => Value::Num(n),
295 Scalar::Bool(b) => Value::Bool(b),
296 }
297 }
298 Expr::Path { absolute, steps } => {
299 let start = if *absolute {
300 Item::Node(ctx.root)
301 } else {
302 ctx.item
303 };
304 Value::Nodes(walk(vec![start], steps, ctx)?)
305 }
306 Expr::Filter {
307 primary,
308 predicates,
309 steps,
310 } => {
311 let Value::Nodes(mut items) = eval(primary, ctx)? else {
312 return Err("predicates and paths can only follow a node-set".into());
313 };
314 for p in predicates {
315 items = filter(items, p, ctx)?;
316 }
317 Value::Nodes(walk(items, steps, ctx)?)
318 }
319 })
320}
321
322fn in_document_order<'a>(items: Vec<Item>, ctx: &Context<'a, '_>) -> Vec<Item> {
323 if items.windows(2).all(|w| ctx.key(&w[0]) < ctx.key(&w[1])) {
325 return items;
326 }
327 let mut keyed: Vec<_> = items.into_iter().map(|i| (ctx.key(&i), i)).collect();
329 keyed.sort_unstable_by_key(|(k, _)| *k);
330 keyed.dedup_by_key(|(k, _)| *k);
331 keyed.into_iter().map(|(_, i)| i).collect()
332}
333
334fn walk<'a>(mut items: Vec<Item>, steps: &[Step], ctx: &Context<'a, '_>) -> Result<Vec<Item>> {
335 let index = ctx.doc.index;
336 let mut candidates = Vec::new();
337 let mut scanned = Vec::new();
338 let mut i = 0;
339 while i < steps.len() {
340 let step = &steps[i];
341 i += 1;
342 if let Some(next) = steps.get(i)
346 && step.axis == Axis::DescendantOrSelf
347 && step.test == NodeTest::Node
348 && step.predicates.is_empty()
349 && next.axis == Axis::Child
350 && !next.predicates.is_empty()
351 && let Some(grouped) = descendants_by_parent(&items, next, ctx)
352 {
353 items = grouped?;
354 i += 1;
355 continue;
356 }
357 let test = Test::resolve(&step.test, step.axis, ctx)?;
358 if step.predicates.is_empty()
363 && items.len() > 1
364 && let Some(found) = whole_set(&items, step.axis, &test, ctx)?
365 {
366 items = found;
367 continue;
368 }
369 let nth = match step.predicates.first() {
371 Some(Expr::Number(k)) if *k >= 1.0 && k.fract() == 0.0 && *k < usize::MAX as f64 => {
372 Some(*k as usize)
373 }
374 _ => None,
375 };
376 let mut next = Vec::new();
377 for item in &items {
378 candidates.clear();
379 let mut done = 0;
381 match (item, test.indexable()) {
382 (Item::Node(n), true)
385 if matches!(
386 step.axis,
387 Axis::Child | Axis::Descendant | Axis::DescendantOrSelf
388 ) =>
389 {
390 let at = ctx.order(*n);
391 let keep = |kind, tag| test.keeps(kind, tag);
392 scanned.clear();
393 match step.axis {
394 Axis::Child => index.children(at, keep, &mut scanned),
395 axis => {
396 ctx.spend((index.end_of(at) - at) as usize)?;
397 index.descendants(
398 at,
399 axis == Axis::DescendantOrSelf,
400 keep,
401 &mut scanned,
402 )
403 }
404 }
405 candidates.extend(
406 scanned
407 .iter()
408 .copied()
409 .map(Item::Node)
410 .filter(|i| !test.exact() || test.matches(i, ctx)),
411 );
412 }
413 _ => {
414 let looked = Cell::new(0usize);
415 let mut on_axis = axis(*item, step.axis, ctx)
416 .inspect(|_| looked.set(looked.get() + 1))
417 .filter(|c| test.matches(c, ctx));
418 if nth.is_some() {
419 done = 1;
420 }
421 match nth {
422 Some(k) => candidates.extend(on_axis.nth(k - 1)),
425 None => candidates.extend(on_axis),
426 }
427 ctx.spend(looked.get())?;
428 }
429 }
430 ctx.spend(candidates.len() + 1)?;
431 let mut kept = std::mem::take(&mut candidates);
432 for p in &step.predicates[done..] {
433 kept = filter(kept, p, ctx)?;
434 }
435 next.extend_from_slice(&kept);
436 candidates = kept;
437 }
438 items = if items.len() == 1 && !step.axis.is_reverse() {
441 next
442 } else {
443 in_document_order(next, ctx)
444 };
445 }
446 Ok(items)
447}
448
449fn whole_set<'a>(
453 items: &[Item],
454 axis: Axis,
455 test: &Test<'_>,
456 ctx: &Context<'a, '_>,
457) -> Result<Option<Vec<Item>>> {
458 let index = ctx.doc.index;
459 let (_, tree_end) = ctx.tree_range();
460 let keep = |j: u32| {
461 let item = Item::Node(index.node_at(j));
462 if test.indexable() {
463 test.keeps(index.kind_at(j), index.tag_at(j))
464 && (!test.exact() || test.matches(&item, ctx))
465 } else {
466 test.matches(&item, ctx)
467 }
468 };
469 let mut out = Vec::new();
470 match axis {
471 Axis::Descendant | Axis::DescendantOrSelf => {
472 let mut covered_to = 0;
474 for item in items {
475 match item {
476 Item::Node(n) => {
477 let at = ctx.order(*n);
478 if at < covered_to {
479 continue;
480 }
481 covered_to = index.end_of(at);
482 let from = if axis == Axis::DescendantOrSelf {
483 at
484 } else {
485 at + 1
486 };
487 ctx.spend((covered_to - from) as usize)?;
488 out.extend(
489 (from..covered_to)
490 .filter(|&j| keep(j))
491 .map(|j| Item::Node(index.node_at(j))),
492 );
493 }
494 attr if axis == Axis::DescendantOrSelf && test.matches(attr, ctx) => {
496 out.push(*attr)
497 }
498 _ => {}
499 }
500 }
501 return Ok(Some(in_document_order(out, ctx)));
502 }
503 Axis::Following => {
504 let Some(from) = items
507 .iter()
508 .map(|i| match i {
509 Item::Node(n) => index.end_of(ctx.order(*n)),
510 Item::Attr { owner, .. } => ctx.order(*owner) + 1,
511 })
512 .min()
513 else {
514 return Ok(Some(out));
515 };
516 ctx.spend(tree_end.saturating_sub(from) as usize)?;
517 out.extend(
518 (from..tree_end)
519 .filter(|&j| keep(j))
520 .map(|j| Item::Node(index.node_at(j))),
521 );
522 }
523 Axis::Preceding => {
524 let Some(last) = items.iter().map(|i| ctx.key(i).0).max() else {
526 return Ok(Some(out));
527 };
528 let (top, _) = ctx.tree_range();
529 ctx.spend(last.saturating_sub(top) as usize)?;
530 out.extend(
532 (top..last)
533 .filter(|&j| index.end_of(j) <= last && keep(j))
534 .map(|j| Item::Node(index.node_at(j))),
535 );
536 }
537 Axis::Ancestor | Axis::AncestorOrSelf => {
538 let mut seen = HashSet::new();
540 for item in items {
541 let start = match item {
542 Item::Node(n) if axis == Axis::Ancestor => index.parent_of(ctx.order(*n)),
543 Item::Node(n) => ctx.order(*n),
544 Item::Attr { owner, .. } => {
545 if axis == Axis::AncestorOrSelf && test.matches(item, ctx) {
546 out.push(*item);
547 }
548 ctx.order(*owner)
549 }
550 };
551 let mut at = start;
552 while at != u32::MAX && seen.insert(at) {
553 ctx.spend(1)?;
554 if keep(at) {
555 out.push(Item::Node(index.node_at(at)));
556 }
557 at = index.parent_of(at);
558 }
559 }
560 return Ok(Some(in_document_order(out, ctx)));
561 }
562 Axis::FollowingSibling | Axis::PrecedingSibling => {
563 let tree = ctx.doc.tree;
566 let mut from: HashMap<NodeId, NodeId> = HashMap::new();
567 for item in items {
568 if let Item::Node(n) = item
569 && let Some(p) = tree.parent(*n)
570 {
571 if axis == Axis::FollowingSibling {
572 from.entry(p).or_insert(*n);
573 } else {
574 from.insert(p, *n);
575 }
576 }
577 }
578 for &n in from.values() {
579 let step = |&s: &NodeId| match axis {
580 Axis::FollowingSibling => tree.next_sibling(s),
581 _ => tree.prev_sibling(s),
582 };
583 for s in std::iter::successors(step(&n), step) {
584 ctx.spend(1)?;
585 if keep(ctx.order(s)) {
586 out.push(Item::Node(s));
587 }
588 }
589 }
590 return Ok(Some(in_document_order(out, ctx)));
591 }
592 _ => return Ok(None),
593 }
594 Ok(Some(out))
595}
596
597fn descendants_by_parent<'a>(
601 items: &[Item],
602 step: &Step,
603 ctx: &Context<'a, '_>,
604) -> Option<Result<Vec<Item>>> {
605 let test = match Test::resolve(&step.test, step.axis, ctx) {
606 Ok(test) => test,
607 Err(e) => return Some(Err(e)),
608 };
609 if !test.indexable() {
610 return None;
611 }
612 let index = ctx.doc.index;
613 let mut found = Vec::new();
614 let mut covered_to = 0;
618 for item in items {
619 let Item::Node(n) = item else { continue };
621 let at = ctx.order(*n);
622 if at < covered_to {
623 continue;
624 }
625 covered_to = index.end_of(at);
626 if let Err(e) = ctx.spend((covered_to - at) as usize) {
627 return Some(Err(e));
628 }
629 index.descendants(at, false, |k, t| test.keeps(k, t), &mut found);
630 }
631 if test.exact() {
632 found.retain(|&n| test.matches(&Item::Node(n), ctx));
633 }
634 if !step.predicates.iter().any(Expr::positional) {
638 let mut items: Vec<Item> = found.into_iter().map(Item::Node).collect();
639 for p in &step.predicates {
640 let p = match p {
641 Expr::Memo(inner, _) if !ctx.nested => inner,
642 p => p,
643 };
644 items = match filter(items, p, ctx) {
645 Ok(items) => items,
646 Err(e) => return Some(Err(e)),
647 };
648 }
649 return Some(Ok(items));
650 }
651 let mut groups: Vec<(u32, Vec<Item>)> = Vec::new();
653 let mut slot: HashMap<u32, usize> = HashMap::new();
654 for node in found {
655 let parent = index.parent_of(ctx.order(node));
656 let at = *slot.entry(parent).or_insert_with(|| {
657 groups.push((parent, Vec::new()));
658 groups.len() - 1
659 });
660 groups[at].1.push(Item::Node(node));
661 }
662 let run = || -> Result<Vec<Item>> {
663 let mut out = Vec::new();
664 for (_, mut group) in groups {
665 for p in &step.predicates {
666 group = filter(group, p, ctx)?;
667 }
668 out.extend(group);
669 }
670 Ok(in_document_order(out, ctx))
671 };
672 Some(run())
673}
674
675fn quick_predicate(pred: &Expr, item: &Item, doc: Doc<'_>) -> Option<bool> {
679 let attr_name = |e: &Expr| match e {
680 Expr::Path {
681 absolute: false,
682 steps,
683 } => match steps.as_slice() {
684 [
685 Step {
686 axis: Axis::Attribute,
687 test: NodeTest::Name(n),
688 predicates,
689 },
690 ] if predicates.is_empty() && !n.bytes().any(|b| b.is_ascii_uppercase()) => {
694 Some(n.clone())
695 }
696 _ => None,
697 },
698 _ => None,
699 };
700 let Item::Node(node) = item else { return None };
701 match pred {
702 Expr::Binary(Op::Eq, l, r) => {
703 let (name, value) = match (attr_name(l), attr_name(r), &**l, &**r) {
704 (Some(n), None, _, Expr::Literal(v)) | (None, Some(n), Expr::Literal(v), _) => {
705 (n, v)
706 }
707 _ => return None,
708 };
709 Some(doc.attr(*node, &name) == Some(value.as_str()))
710 }
711 other => attr_name(other).map(|n| doc.attr(*node, &n).is_some()),
712 }
713}
714
715fn filter<'a>(items: Vec<Item>, pred: &Expr, ctx: &Context<'a, '_>) -> Result<Vec<Item>> {
718 let size = items.len();
719 ctx.spend(size)?;
720 let mut kept = items;
722 let mut len = 0;
723 for i in 0..size {
724 let item = kept[i];
725 if let Some(keep) = quick_predicate(pred, &item, ctx.doc) {
726 if keep {
727 kept[len] = item;
728 len += 1;
729 }
730 continue;
731 }
732 let inner = Context {
733 item,
734 position: i + 1,
735 size,
736 nested: true,
737 ..*ctx
738 };
739 let keep = match eval(pred, &inner)? {
740 Value::Num(n) => n == (i + 1) as f64,
741 other => boolean(&other),
742 };
743 if keep {
744 kept[len] = item;
745 len += 1;
746 }
747 }
748 kept.truncate(len);
749 Ok(kept)
750}
751
752fn namespace<'c>(prefix: &str, ctx: &'c Context<'_, '_>) -> Result<&'c str> {
754 if let Some((_, uri)) = ctx.namespaces.iter().rev().find(|(p, _)| p == prefix) {
755 return Ok(uri);
756 }
757 if prefix == "xml" {
758 return Ok(XML_NS);
759 }
760 Err(format!("undefined namespace prefix {prefix:?}"))
761}
762
763enum Test<'t> {
766 Node,
767 Text,
768 Comment,
769 Pi(Option<&'t str>),
771 Never,
772 AnyElement,
774 AnyAttribute,
775 ElementId(usize),
776 ElementName(&'t str),
779 AttributeName(&'t str),
780 XmlElement {
784 id: usize,
785 local: &'t str,
786 ns: u32,
787 },
788 XmlElementIn(u32),
790 XmlAttribute {
791 local: &'t str,
792 ns: u32,
793 },
794 XmlAttributeIn(u32),
795}
796
797impl<'t> Test<'t> {
798 fn resolve(test: &'t NodeTest, axis: Axis, ctx: &Context<'_, '_>) -> Result<Test<'t>> {
799 let attr = axis == Axis::Attribute;
800 let index = ctx.doc.index;
801 if let Some(names) = ctx.doc.names {
802 let ns =
805 |prefix: &str| -> Result<Option<u32>> { Ok(names.id_of(namespace(prefix, ctx)?)) };
806 return Ok(match test {
807 NodeTest::Name(local) if attr => Test::XmlAttribute { local, ns: 0 },
808 NodeTest::Prefixed(p, local) if attr => match ns(p)? {
809 Some(ns) => Test::XmlAttribute { local, ns },
810 None => Test::Never,
811 },
812 NodeTest::AnyIn(p) if attr => ns(p)?.map_or(Test::Never, Test::XmlAttributeIn),
813 NodeTest::Name(local) => match index.tag_id_named(local) {
814 Some(id) => Test::XmlElement { id, local, ns: 0 },
815 None => Test::Never,
816 },
817 NodeTest::Prefixed(p, local) => match (ns(p)?, index.tag_id_named(local)) {
818 (Some(ns), Some(id)) => Test::XmlElement { id, local, ns },
819 _ => Test::Never,
820 },
821 NodeTest::AnyIn(p) => ns(p)?.map_or(Test::Never, Test::XmlElementIn),
822 other => Test::resolve_html(other, attr, ctx),
823 });
824 }
825 if let NodeTest::Prefixed(p, _) | NodeTest::AnyIn(p) = test {
826 namespace(p, ctx)?;
829 return Ok(Test::Never);
830 }
831 Ok(Test::resolve_html(test, attr, ctx))
832 }
833
834 fn resolve_html(test: &'t NodeTest, attr: bool, ctx: &Context<'_, '_>) -> Test<'t> {
835 match test {
836 NodeTest::Node => Test::Node,
837 NodeTest::Text if attr => Test::Never,
838 NodeTest::Text => Test::Text,
839 NodeTest::Comment if attr => Test::Never,
840 NodeTest::Comment => Test::Comment,
841 NodeTest::ProcessingInstruction(_) if attr => Test::Never,
844 NodeTest::ProcessingInstruction(target) => Test::Pi(target.as_deref()),
845 NodeTest::Any if attr => Test::AnyAttribute,
846 NodeTest::Any => Test::AnyElement,
847 NodeTest::Name(name) if attr => Test::AttributeName(name),
848 NodeTest::Name(name) if name.bytes().any(|b| b.is_ascii_uppercase()) => {
849 Test::ElementName(name)
850 }
851 NodeTest::Name(name) => ctx
852 .doc
853 .index
854 .tag_id_named(name)
855 .map_or(Test::Never, Test::ElementId),
856 NodeTest::Prefixed(..) | NodeTest::AnyIn(_) => Test::Never,
857 }
858 }
859
860 fn indexable(&self) -> bool {
863 matches!(
864 self,
865 Test::Node
866 | Test::Text
867 | Test::Comment
868 | Test::Pi(None)
869 | Test::AnyElement
870 | Test::ElementId(_)
871 | Test::XmlElement { .. }
872 | Test::Never
873 )
874 }
875
876 fn exact(&self) -> bool {
878 matches!(self, Test::XmlElement { .. })
879 }
880
881 fn keeps(&self, kind: u8, tag: usize) -> bool {
883 match self {
884 Test::Node => true,
885 Test::Text => kind == TEXT || kind == CDATA,
886 Test::Comment => kind == COMMENT,
887 Test::Pi(None) => kind == PI,
888 Test::AnyElement => kind == ELEMENT,
889 Test::ElementId(id) | Test::XmlElement { id, .. } => kind == ELEMENT && tag == *id,
890 _ => false,
891 }
892 }
893
894 fn matches(&self, item: &Item, ctx: &Context<'_, '_>) -> bool {
895 let kind = |n: &NodeId| ctx.kind(*n);
896 match (self, item) {
897 (Test::Node, _) => true,
898 (Test::Never, _) => false,
899 (Test::ElementId(id), Item::Node(n)) => {
900 let at = ctx.order(*n);
901 ctx.doc.index.tag_at(at) == *id && ctx.doc.index.kind_at(at) == ELEMENT
902 }
903 (Test::ElementName(name), Item::Node(n)) => ctx.tag(*n) == Some(name),
904 (Test::AnyElement, Item::Node(n)) => kind(n) == ELEMENT,
905 (Test::Text, Item::Node(n)) => matches!(kind(n), TEXT | CDATA),
906 (Test::Comment, Item::Node(n)) => kind(n) == COMMENT,
907 (Test::Pi(target), Item::Node(n)) => {
908 kind(n) == PI && target.is_none_or(|t| ctx.pi_target(*n) == Some(t))
909 }
910 (Test::AnyAttribute, Item::Attr { .. }) => true,
911 (Test::AttributeName(name), Item::Attr { owner, index, .. }) => {
912 ctx.doc.attr_at(*owner, *index).0 == *name
913 }
914 (Test::XmlElement { local, ns, .. }, Item::Node(n)) => {
915 kind(n) == ELEMENT && ctx.tag(*n) == Some(local) && ctx.ns_id(*n) == *ns
916 }
917 (Test::XmlElementIn(ns), Item::Node(n)) => kind(n) == ELEMENT && ctx.ns_id(*n) == *ns,
918 (Test::XmlAttribute { local, ns }, i @ Item::Attr { ns: a, .. }) => {
919 a == ns && ctx.local_name(i) == *local
920 }
921 (Test::XmlAttributeIn(ns), Item::Attr { ns: a, .. }) => a == ns,
922 _ => false,
923 }
924 }
925}
926
927fn attributes<'a>(n: NodeId, doc: Doc<'a>) -> impl Iterator<Item = Item> + 'a {
928 doc.tree
929 .attrs(n)
930 .enumerate()
931 .map(move |(i, (ns, _, _))| Item::Attr {
932 owner: n,
933 index: i as u32,
934 ns: match ns {
935 html::AttrNs::Host(id) => id,
936 _ => 0,
937 },
938 })
939}
940
941fn axis<'a>(item: Item, axis: Axis, ctx: &Context<'a, '_>) -> Box<dyn Iterator<Item = Item> + 'a> {
944 let doc = ctx.doc;
945 let (tree, index) = (doc.tree, doc.index);
946 let (top, tree_end) = ctx.tree_range();
947 let node_at = move |j: u32| Item::Node(index.node_at(j));
948 let ancestors =
949 move |n: NodeId| std::iter::successors(tree.parent(n), move |&p| tree.parent(p));
950 let following = move |n: NodeId| (index.end_of(index.order(n))..tree_end).map(node_at);
952 let preceding = move |n: NodeId| {
954 let at = index.order(n);
955 (top..at)
956 .rev()
957 .filter(move |&j| index.end_of(j) <= at)
958 .map(node_at)
959 };
960 let descendants = move |n: NodeId| {
961 let at = index.order(n);
962 (at + 1..index.end_of(at)).map(node_at)
963 };
964 match item {
965 Item::Node(n) => match axis {
966 Axis::Child => Box::new(tree.children(n).map(Item::Node)),
967 Axis::Descendant => Box::new(descendants(n)),
968 Axis::DescendantOrSelf => Box::new(std::iter::once(item).chain(descendants(n))),
969 Axis::Parent => Box::new(tree.parent(n).map(Item::Node).into_iter()),
970 Axis::Ancestor => Box::new(ancestors(n).map(Item::Node)),
971 Axis::AncestorOrSelf => {
972 Box::new(std::iter::once(n).chain(ancestors(n)).map(Item::Node))
973 }
974 Axis::FollowingSibling => Box::new(
975 std::iter::successors(tree.next_sibling(n), move |&s| tree.next_sibling(s))
976 .map(Item::Node),
977 ),
978 Axis::PrecedingSibling => Box::new(
979 std::iter::successors(tree.prev_sibling(n), move |&s| tree.prev_sibling(s))
980 .map(Item::Node),
981 ),
982 Axis::Following => Box::new(following(n)),
983 Axis::Preceding => Box::new(preceding(n)),
984 Axis::Attribute if ctx.kind(n) == ELEMENT => Box::new(attributes(n, doc)),
985 Axis::Attribute | Axis::Namespace => Box::new(std::iter::empty()),
986 Axis::Itself => Box::new(std::iter::once(item)),
987 },
988 Item::Attr { owner, .. } => match axis {
989 Axis::Parent => Box::new(std::iter::once(Item::Node(owner))),
990 Axis::Ancestor => Box::new(
991 std::iter::once(owner)
992 .chain(ancestors(owner))
993 .map(Item::Node),
994 ),
995 Axis::AncestorOrSelf => Box::new(
996 std::iter::once(item).chain(
997 std::iter::once(owner)
998 .chain(ancestors(owner))
999 .map(Item::Node),
1000 ),
1001 ),
1002 Axis::Itself | Axis::DescendantOrSelf => Box::new(std::iter::once(item)),
1003 Axis::Following => Box::new(descendants(owner).chain(following(owner))),
1004 Axis::Preceding => Box::new(preceding(owner)),
1005 _ => Box::new(std::iter::empty()),
1006 },
1007 }
1008}
1009
1010fn string<'a>(v: &Value<'a>, ctx: &Context<'a, '_>) -> String {
1013 match v {
1014 Value::Str(s) => s.to_string(),
1015 Value::Num(n) => number_to_string(*n),
1016 Value::Bool(b) => b.to_string(),
1017 Value::Nodes(items) => items
1018 .first()
1019 .map(|i| ctx.string_value(i).into_owned())
1020 .unwrap_or_default(),
1021 }
1022}
1023
1024fn number_to_string(n: f64) -> String {
1025 if n.is_nan() {
1026 "NaN".into()
1027 } else if n.is_infinite() {
1028 if n > 0.0 { "Infinity" } else { "-Infinity" }.into()
1029 } else if n == 0.0 {
1030 "0".into()
1031 } else {
1032 format!("{n}")
1035 }
1036}
1037
1038fn number<'a>(v: Value<'a>, ctx: &Context<'a, '_>) -> f64 {
1039 match v {
1040 Value::Num(n) => n,
1041 Value::Bool(b) => b as u8 as f64,
1042 Value::Str(s) => parse_number(&s),
1043 nodes @ Value::Nodes(_) => parse_number(&string(&nodes, ctx)),
1044 }
1045}
1046
1047fn parse_number(s: &str) -> f64 {
1050 let t = s.trim_matches(|c| matches!(c, ' ' | '\t' | '\n' | '\r'));
1051 let digits = t.strip_prefix('-').unwrap_or(t);
1052 let valid = !digits.is_empty()
1053 && digits.chars().all(|c| c.is_ascii_digit() || c == '.')
1054 && digits.matches('.').count() <= 1
1055 && digits != ".";
1056 if valid {
1057 t.parse().unwrap_or(f64::NAN)
1058 } else {
1059 f64::NAN
1060 }
1061}
1062
1063fn boolean(v: &Value<'_>) -> bool {
1064 match v {
1065 Value::Bool(b) => *b,
1066 Value::Num(n) => *n != 0.0 && !n.is_nan(),
1067 Value::Str(s) => !s.is_empty(),
1068 Value::Nodes(items) => !items.is_empty(),
1069 }
1070}
1071
1072fn binary<'a>(op: Op, l: &Expr, r: &Expr, ctx: &Context<'a, '_>) -> Result<Value<'a>> {
1075 Ok(match op {
1076 Op::Or => Value::Bool(boolean(&eval(l, ctx)?) || boolean(&eval(r, ctx)?)),
1077 Op::And => Value::Bool(boolean(&eval(l, ctx)?) && boolean(&eval(r, ctx)?)),
1078 Op::Add | Op::Sub | Op::Mul | Op::Div | Op::Mod => {
1079 let (a, b) = (number(eval(l, ctx)?, ctx), number(eval(r, ctx)?, ctx));
1080 Value::Num(match op {
1081 Op::Add => a + b,
1082 Op::Sub => a - b,
1083 Op::Mul => a * b,
1084 Op::Div => a / b,
1085 _ => a % b,
1087 })
1088 }
1089 _ => Value::Bool(compare(op, eval(l, ctx)?, eval(r, ctx)?, ctx)),
1090 })
1091}
1092
1093fn compare_atoms<'a>(op: Op, a: &Value<'a>, b: &Value<'a>, ctx: &Context<'a, '_>) -> bool {
1094 if matches!(op, Op::Eq | Op::Neq) {
1095 let equal = if matches!(a, Value::Bool(_)) || matches!(b, Value::Bool(_)) {
1096 boolean(a) == boolean(b)
1097 } else if matches!(a, Value::Num(_)) || matches!(b, Value::Num(_)) {
1098 number(a.clone(), ctx) == number(b.clone(), ctx)
1099 } else {
1100 fn text<'v, 'a>(v: &'v Value<'a>, ctx: &Context<'a, '_>) -> Cow<'v, str> {
1103 match v {
1104 Value::Str(s) => Cow::Borrowed(s),
1105 other => Cow::Owned(string(other, ctx)),
1106 }
1107 }
1108 text(a, ctx) == text(b, ctx)
1109 };
1110 return equal == (op == Op::Eq);
1111 }
1112 let (x, y) = (number(a.clone(), ctx), number(b.clone(), ctx));
1113 match op {
1114 Op::Lt => x < y,
1115 Op::Le => x <= y,
1116 Op::Gt => x > y,
1117 _ => x >= y,
1118 }
1119}
1120
1121fn compare<'a>(op: Op, a: Value<'a>, b: Value<'a>, ctx: &Context<'a, '_>) -> bool {
1123 match (&a, &b) {
1124 (Value::Nodes(xs), Value::Nodes(ys)) => {
1125 let ys: Vec<Value<'_>> = ys.iter().map(|y| Value::Str(ctx.string_value(y))).collect();
1126 xs.iter().any(|x| {
1127 let x = Value::Str(ctx.string_value(x));
1128 ys.iter().any(|y| compare_atoms(op, &x, y, ctx))
1129 })
1130 }
1131 (Value::Nodes(_), Value::Bool(_)) | (Value::Bool(_), Value::Nodes(_)) => compare_atoms(
1132 op,
1133 &Value::Bool(boolean(&a)),
1134 &Value::Bool(boolean(&b)),
1135 ctx,
1136 ),
1137 (Value::Nodes(xs), other) => xs
1138 .iter()
1139 .any(|x| compare_atoms(op, &atom_like(x, other, ctx), other, ctx)),
1140 (other, Value::Nodes(ys)) => ys
1141 .iter()
1142 .any(|y| compare_atoms(op, other, &atom_like(y, other, ctx), ctx)),
1143 _ => compare_atoms(op, &a, &b, ctx),
1144 }
1145}
1146
1147fn atom_like<'a>(item: &Item, other: &Value<'_>, ctx: &Context<'a, '_>) -> Value<'a> {
1149 match other {
1150 Value::Num(_) => Value::Num(parse_number(&ctx.string_value(item))),
1151 _ => Value::Str(ctx.string_value(item)),
1152 }
1153}
1154
1155pub struct Args<'c, 'a> {
1160 name: &'c str,
1161 exprs: &'c [Expr],
1162 ctx: &'c Context<'a, 'c>,
1163}
1164
1165impl<'a> Args<'_, 'a> {
1166 pub fn len(&self) -> usize {
1167 self.exprs.len()
1168 }
1169
1170 pub fn is_empty(&self) -> bool {
1171 self.exprs.is_empty()
1172 }
1173
1174 pub fn arity(&self, min: usize, max: usize) -> Result<()> {
1176 arity(self.name, self.exprs.len(), min, max)
1177 }
1178
1179 pub fn value(&self, i: usize) -> Result<Value<'a>> {
1181 eval(&self.exprs[i], self.ctx)
1182 }
1183
1184 pub fn string(&self, i: usize) -> Result<String> {
1186 Ok(string(&self.value(i)?, self.ctx))
1187 }
1188
1189 pub fn context(&self) -> Item {
1191 self.ctx.item
1192 }
1193
1194 pub fn doc(&self) -> Doc<'a> {
1195 self.ctx.doc
1196 }
1197}
1198
1199fn arity(name: &str, got: usize, min: usize, max: usize) -> Result<()> {
1200 if got < min || got > max {
1201 let expected = if min == max {
1202 format!("{min}")
1203 } else if max == usize::MAX {
1204 format!("at least {min}")
1205 } else {
1206 format!("{min} to {max}")
1207 };
1208 return Err(format!("{name}() takes {expected} arguments, got {got}"));
1209 }
1210 Ok(())
1211}
1212
1213fn call<'a>(name: &str, args: &[Expr], ctx: &Context<'a, '_>) -> Result<Value<'a>> {
1214 let arity = |min: usize, max: usize| arity(name, args.len(), min, max);
1215 let arg = |i: usize| eval(&args[i], ctx);
1216 let str_arg = |i: usize| -> Result<String> { Ok(string(&eval(&args[i], ctx)?, ctx)) };
1217 let nodes_arg = |i: usize| -> Result<Vec<Item>> {
1218 match eval(&args[i], ctx)? {
1219 Value::Nodes(n) => Ok(n),
1220 _ => Err(format!("{name}() needs a node-set argument")),
1221 }
1222 };
1223 let context_or = |i: usize| -> Result<Vec<Item>> {
1226 if args.len() > i {
1227 nodes_arg(i)
1228 } else {
1229 Ok(vec![ctx.item])
1230 }
1231 };
1232 Ok(match name {
1233 "last" => {
1234 arity(0, 0)?;
1235 Value::Num(ctx.size as f64)
1236 }
1237 "position" => {
1238 arity(0, 0)?;
1239 Value::Num(ctx.position as f64)
1240 }
1241 "count" => {
1242 arity(1, 1)?;
1243 Value::Num(nodes_arg(0)?.len() as f64)
1244 }
1245 "id" => {
1246 arity(1, 1)?;
1247 let wanted: Vec<String> = match arg(0)? {
1248 Value::Nodes(items) => items
1249 .iter()
1250 .map(|i| ctx.string_value(i).into_owned())
1251 .collect(),
1252 other => vec![string(&other, ctx)],
1253 };
1254 let index = ctx.doc.index;
1255 let doc = ctx.doc;
1256 let (top, end) = ctx.tree_range();
1257 let found = wanted
1258 .iter()
1259 .flat_map(|s| s.split_whitespace())
1260 .flat_map(|id| index.with_id(id, |n| doc.attr(n, "id")))
1261 .filter(|&n| (top..end).contains(&ctx.order(n)))
1262 .map(Item::Node)
1263 .collect();
1264 Value::Nodes(in_document_order(found, ctx))
1265 }
1266 "local-name" | "name" | "namespace-uri" => {
1267 arity(0, 1)?;
1268 let first = in_document_order(context_or(0)?, ctx).into_iter().next();
1269 text(
1270 first
1271 .map(|i| match name {
1272 "name" => ctx.name(&i),
1273 "local-name" => ctx.local_name(&i),
1274 _ => ctx.namespace_uri(&i),
1275 })
1276 .unwrap_or_default()
1277 .to_string(),
1278 )
1279 }
1280 "string" => {
1281 arity(0, 1)?;
1282 text(if args.is_empty() {
1283 ctx.string_value(&ctx.item).into_owned()
1284 } else {
1285 str_arg(0)?
1286 })
1287 }
1288 "concat" => {
1289 arity(2, usize::MAX)?;
1290 let mut out = String::new();
1291 for i in 0..args.len() {
1292 out.push_str(&str_arg(i)?);
1293 }
1294 text(out)
1295 }
1296 "starts-with" => {
1297 arity(2, 2)?;
1298 Value::Bool(str_arg(0)?.starts_with(&str_arg(1)?))
1299 }
1300 "contains" => {
1301 arity(2, 2)?;
1302 Value::Bool(str_arg(0)?.contains(&str_arg(1)?))
1303 }
1304 "substring-before" => {
1305 arity(2, 2)?;
1306 let (s, t) = (str_arg(0)?, str_arg(1)?);
1307 text(s.find(&t).map(|i| s[..i].to_string()).unwrap_or_default())
1308 }
1309 "substring-after" => {
1310 arity(2, 2)?;
1311 let (s, t) = (str_arg(0)?, str_arg(1)?);
1312 text(
1313 s.find(&t)
1314 .map(|i| s[i + t.len()..].to_string())
1315 .unwrap_or_default(),
1316 )
1317 }
1318 "substring" => {
1319 arity(2, 3)?;
1320 let s = str_arg(0)?;
1321 let start = round(number(arg(1)?, ctx));
1322 let end = if args.len() == 3 {
1323 start + round(number(arg(2)?, ctx))
1324 } else {
1325 f64::INFINITY
1326 };
1327 text(
1329 s.chars()
1330 .enumerate()
1331 .filter(|(i, _)| {
1332 let p = (*i + 1) as f64;
1333 p >= start && p < end
1334 })
1335 .map(|(_, c)| c)
1336 .collect(),
1337 )
1338 }
1339 "string-length" => {
1340 arity(0, 1)?;
1341 let s = if args.is_empty() {
1342 ctx.string_value(&ctx.item).into_owned()
1343 } else {
1344 str_arg(0)?
1345 };
1346 Value::Num(s.chars().count() as f64)
1347 }
1348 "normalize-space" => {
1349 arity(0, 1)?;
1350 let s = if args.is_empty() {
1351 ctx.string_value(&ctx.item).into_owned()
1352 } else {
1353 str_arg(0)?
1354 };
1355 text(
1356 s.split([' ', '\t', '\n', '\r'])
1357 .filter(|w| !w.is_empty())
1358 .collect::<Vec<_>>()
1359 .join(" "),
1360 )
1361 }
1362 "translate" => {
1363 arity(3, 3)?;
1364 let (s, from, to) = (str_arg(0)?, str_arg(1)?, str_arg(2)?);
1365 let from: Vec<char> = from.chars().collect();
1366 let to: Vec<char> = to.chars().collect();
1367 text(
1368 s.chars()
1369 .filter_map(|c| match from.iter().position(|&f| f == c) {
1370 Some(i) => to.get(i).copied(),
1371 None => Some(c),
1372 })
1373 .collect(),
1374 )
1375 }
1376 "boolean" => {
1377 arity(1, 1)?;
1378 Value::Bool(boolean(&arg(0)?))
1379 }
1380 "not" => {
1381 arity(1, 1)?;
1382 Value::Bool(!boolean(&arg(0)?))
1383 }
1384 "true" => {
1385 arity(0, 0)?;
1386 Value::Bool(true)
1387 }
1388 "false" => {
1389 arity(0, 0)?;
1390 Value::Bool(false)
1391 }
1392 "lang" => {
1393 arity(1, 1)?;
1394 let want = str_arg(0)?.to_ascii_lowercase();
1395 let node = match ctx.item {
1396 Item::Node(n) => n,
1397 Item::Attr { owner, .. } => owner,
1398 };
1399 let tree = ctx.doc.tree;
1400 let mut declared = None;
1402 let mut at = Some(node);
1403 while let Some(n) = at {
1404 ctx.spend(1)?;
1405 declared = ctx
1406 .doc
1407 .attr(n, "xml:lang")
1408 .or_else(|| ctx.doc.attr(n, "lang"));
1409 if declared.is_some() {
1410 break;
1411 }
1412 at = tree.parent(n);
1413 }
1414 let declared = declared.map(str::to_ascii_lowercase);
1415 Value::Bool(declared.is_some_and(|l| l == want || l.starts_with(&format!("{want}-"))))
1416 }
1417 "number" => {
1418 arity(0, 1)?;
1419 Value::Num(if args.is_empty() {
1420 parse_number(&ctx.string_value(&ctx.item))
1421 } else {
1422 number(arg(0)?, ctx)
1423 })
1424 }
1425 "sum" => {
1426 arity(1, 1)?;
1427 Value::Num(
1429 nodes_arg(0)?
1430 .iter()
1431 .map(|i| parse_number(&ctx.string_value(i)))
1432 .fold(0.0, |a, b| a + b),
1433 )
1434 }
1435 "floor" => {
1436 arity(1, 1)?;
1437 Value::Num(number(arg(0)?, ctx).floor())
1438 }
1439 "ceiling" => {
1440 arity(1, 1)?;
1441 Value::Num(number(arg(0)?, ctx).ceil())
1442 }
1443 "round" => {
1444 arity(1, 1)?;
1445 Value::Num(round(number(arg(0)?, ctx)))
1446 }
1447 _ => {
1448 let args = Args {
1449 name,
1450 exprs: args,
1451 ctx,
1452 };
1453 return ctx
1454 .ext
1455 .call(name, &args)
1456 .unwrap_or_else(|| Err(format!("unknown function {name}()")));
1457 }
1458 })
1459}
1460
1461fn round(x: f64) -> f64 {
1463 if x.is_nan() || x.is_infinite() {
1464 x
1465 } else if (-0.5..0.0).contains(&x) {
1466 -0.0
1467 } else {
1468 let f = x.floor();
1471 if x - f >= 0.5 { f + 1.0 } else { f }
1472 }
1473}
1474
1475#[cfg(test)]
1476mod tests {
1477 use super::*;
1478
1479 #[test]
1480 fn xpath_number_grammar() {
1481 assert_eq!(parse_number(" 12.5\n"), 12.5);
1482 assert_eq!(parse_number("-.5"), -0.5);
1483 assert_eq!(parse_number("5."), 5.0);
1484 for bad in ["", ".", "1e3", "+1", "0x10", "1.2.3", "inf", "NaN", "- 1"] {
1485 assert!(parse_number(bad).is_nan(), "{bad:?}");
1486 }
1487 }
1488}