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