1use std::fmt;
14
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
19pub enum Axis {
20 Ancestor,
21 AncestorOrSelf,
22 Attribute,
23 Child,
24 Descendant,
25 DescendantOrSelf,
26 Following,
27 FollowingSibling,
28 Namespace,
29 Parent,
30 Preceding,
31 PrecedingSibling,
32 SelfAxis,
33}
34
35impl Axis {
36 fn from_name(s: &str) -> Option<Axis> {
37 Some(match s {
38 "ancestor" => Axis::Ancestor,
39 "ancestor-or-self" => Axis::AncestorOrSelf,
40 "attribute" => Axis::Attribute,
41 "child" => Axis::Child,
42 "descendant" => Axis::Descendant,
43 "descendant-or-self" => Axis::DescendantOrSelf,
44 "following" => Axis::Following,
45 "following-sibling" => Axis::FollowingSibling,
46 "namespace" => Axis::Namespace,
47 "parent" => Axis::Parent,
48 "preceding" => Axis::Preceding,
49 "preceding-sibling" => Axis::PrecedingSibling,
50 "self" => Axis::SelfAxis,
51 _ => return None,
52 })
53 }
54
55 pub fn is_reverse(self) -> bool {
63 matches!(
64 self,
65 Axis::Ancestor | Axis::AncestorOrSelf | Axis::Preceding | Axis::PrecedingSibling
66 )
67 }
68
69 pub fn principal(self) -> Principal {
74 match self {
75 Axis::Attribute => Principal::Attribute,
76 Axis::Namespace => Principal::Namespace,
77 _ => Principal::Element,
78 }
79 }
80}
81
82#[derive(Debug, Clone, Copy, PartialEq, Eq)]
83pub enum Principal {
84 Element,
85 Attribute,
86 Namespace,
87}
88
89#[derive(Debug, Clone, PartialEq, Eq)]
91pub enum NodeTest {
92 Any,
94 AnyInPrefix(String),
96 Name(String),
100 Node,
102 Text,
104 Comment,
106 Pi(Option<String>),
108}
109
110#[derive(Debug, Clone, PartialEq)]
111pub struct Step {
112 pub axis: Axis,
113 pub test: NodeTest,
114 pub preds: Vec<Expr>,
115}
116
117#[derive(Debug, Clone, PartialEq)]
119pub enum PathStart {
120 Root,
122 Relative,
124 Filter(Box<Expr>, Vec<Expr>),
126}
127
128#[derive(Debug, Clone, Copy, PartialEq, Eq)]
129pub enum RelOp {
130 Lt,
131 Gt,
132 Le,
133 Ge,
134}
135
136#[derive(Debug, Clone, PartialEq)]
137pub enum Expr {
138 Or(Box<Expr>, Box<Expr>),
139 And(Box<Expr>, Box<Expr>),
140 Eq(Box<Expr>, Box<Expr>),
141 Ne(Box<Expr>, Box<Expr>),
142 Rel(RelOp, Box<Expr>, Box<Expr>),
143 Add(Box<Expr>, Box<Expr>),
144 Sub(Box<Expr>, Box<Expr>),
145 Mul(Box<Expr>, Box<Expr>),
146 Div(Box<Expr>, Box<Expr>),
147 Mod(Box<Expr>, Box<Expr>),
148 Neg(Box<Expr>),
149 Union(Box<Expr>, Box<Expr>),
150 Path(PathStart, Vec<Step>),
151 Number(f64),
152 Literal(String),
153 Call(String, Vec<Expr>),
154}
155
156#[derive(Debug, Clone, PartialEq)]
159pub enum Tok {
160 Slash,
161 DblSlash,
162 LParen,
163 RParen,
164 LBracket,
165 RBracket,
166 Dot,
167 DblDot,
168 At,
169 Comma,
170 DblColon,
171 Star,
172 Pipe,
173 Plus,
174 Minus,
175 Eq,
176 Ne,
177 Lt,
178 Gt,
179 Le,
180 Ge,
181 Op(&'static str),
183 Num(f64),
184 Str(String),
185 Name {
188 text: String,
189 is_fn: bool,
190 is_axis: bool,
191 },
192}
193
194impl fmt::Display for Tok {
195 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
196 match self {
197 Tok::Slash => f.write_str("/"),
198 Tok::DblSlash => f.write_str("//"),
199 Tok::LParen => f.write_str("("),
200 Tok::RParen => f.write_str(")"),
201 Tok::LBracket => f.write_str("["),
202 Tok::RBracket => f.write_str("]"),
203 Tok::Dot => f.write_str("."),
204 Tok::DblDot => f.write_str(".."),
205 Tok::At => f.write_str("@"),
206 Tok::Comma => f.write_str(","),
207 Tok::DblColon => f.write_str("::"),
208 Tok::Star => f.write_str("*"),
209 Tok::Pipe => f.write_str("|"),
210 Tok::Plus => f.write_str("+"),
211 Tok::Minus => f.write_str("-"),
212 Tok::Eq => f.write_str("="),
213 Tok::Ne => f.write_str("!="),
214 Tok::Lt => f.write_str("<"),
215 Tok::Gt => f.write_str(">"),
216 Tok::Le => f.write_str("<="),
217 Tok::Ge => f.write_str(">="),
218 Tok::Op(s) => f.write_str(s),
219 Tok::Num(n) => write!(f, "{n}"),
220 Tok::Str(s) => write!(f, "'{s}'"),
221 Tok::Name { text, .. } => f.write_str(text),
222 }
223 }
224}
225
226fn is_name_start(c: char) -> bool {
232 c.is_alphabetic() || c == '_' || !c.is_ascii()
233}
234
235fn is_name_char(c: char) -> bool {
236 is_name_start(c) || c.is_ascii_digit() || c == '-' || c == '.'
237}
238
239pub fn lex(src: &str) -> Result<Vec<Tok>, String> {
253 let cs: Vec<char> = src.chars().collect();
254 let mut i = 0;
255 let mut out: Vec<Tok> = Vec::new();
256 while i < cs.len() {
257 let c = cs[i];
258 if c.is_whitespace() {
259 i += 1;
260 continue;
261 }
262 let after_operand = matches!(
264 out.last(),
265 Some(
266 Tok::RParen
267 | Tok::RBracket
268 | Tok::Num(_)
269 | Tok::Str(_)
270 | Tok::Star
271 | Tok::Dot
272 | Tok::DblDot
273 | Tok::Name { .. }
274 )
275 );
276 match c {
277 '(' => {
278 out.push(Tok::LParen);
279 i += 1;
280 }
281 ')' => {
282 out.push(Tok::RParen);
283 i += 1;
284 }
285 '[' => {
286 out.push(Tok::LBracket);
287 i += 1;
288 }
289 ']' => {
290 out.push(Tok::RBracket);
291 i += 1;
292 }
293 '@' => {
294 out.push(Tok::At);
295 i += 1;
296 }
297 ',' => {
298 out.push(Tok::Comma);
299 i += 1;
300 }
301 '|' => {
302 out.push(Tok::Pipe);
303 i += 1;
304 }
305 '+' => {
306 out.push(Tok::Plus);
307 i += 1;
308 }
309 '-' => {
310 out.push(Tok::Minus);
311 i += 1;
312 }
313 '*' => {
314 out.push(Tok::Star);
318 i += 1;
319 }
320 '=' => {
321 out.push(Tok::Eq);
322 i += 1;
323 }
324 '!' if cs.get(i + 1) == Some(&'=') => {
325 out.push(Tok::Ne);
326 i += 2;
327 }
328 '!' => return Err("`!` must be part of `!=`".into()),
329 '<' if cs.get(i + 1) == Some(&'=') => {
330 out.push(Tok::Le);
331 i += 2;
332 }
333 '<' => {
334 out.push(Tok::Lt);
335 i += 1;
336 }
337 '>' if cs.get(i + 1) == Some(&'=') => {
338 out.push(Tok::Ge);
339 i += 2;
340 }
341 '>' => {
342 out.push(Tok::Gt);
343 i += 1;
344 }
345 '/' if cs.get(i + 1) == Some(&'/') => {
346 out.push(Tok::DblSlash);
347 i += 2;
348 }
349 '/' => {
350 out.push(Tok::Slash);
351 i += 1;
352 }
353 ':' if cs.get(i + 1) == Some(&':') => {
354 out.push(Tok::DblColon);
355 i += 2;
356 }
357 '\'' | '"' => {
358 let quote = c;
363 i += 1;
364 let start = i;
365 while i < cs.len() && cs[i] != quote {
366 i += 1;
367 }
368 if i >= cs.len() {
369 return Err(format!("unterminated string literal ({quote}…)"));
370 }
371 out.push(Tok::Str(cs[start..i].iter().collect()));
372 i += 1;
373 }
374 '.' if cs.get(i + 1) == Some(&'.') => {
375 out.push(Tok::DblDot);
376 i += 2;
377 }
378 '.' if cs.get(i + 1).is_some_and(char::is_ascii_digit) => {
381 let start = i;
382 i += 1;
383 while i < cs.len() && cs[i].is_ascii_digit() {
384 i += 1;
385 }
386 out.push(Tok::Num(num(&cs[start..i])?));
387 }
388 '.' => {
389 out.push(Tok::Dot);
390 i += 1;
391 }
392 c if c.is_ascii_digit() => {
393 let start = i;
394 while i < cs.len() && cs[i].is_ascii_digit() {
395 i += 1;
396 }
397 if cs.get(i) == Some(&'.') {
398 i += 1;
399 while i < cs.len() && cs[i].is_ascii_digit() {
400 i += 1;
401 }
402 }
403 out.push(Tok::Num(num(&cs[start..i])?));
404 }
405 c if is_name_start(c) => {
406 let start = i;
407 while i < cs.len() && is_name_char(cs[i]) {
408 i += 1;
409 }
410 if cs.get(i) == Some(&':') && cs.get(i + 1).is_some_and(|c| is_name_start(*c)) {
413 i += 1;
414 while i < cs.len() && is_name_char(cs[i]) {
415 i += 1;
416 }
417 } else if cs.get(i) == Some(&':') && cs.get(i + 1) == Some(&'*') {
418 i += 2;
419 }
420 let text: String = cs[start..i].iter().collect();
421 let mut j = i;
423 while j < cs.len() && cs[j].is_whitespace() {
424 j += 1;
425 }
426 let is_fn = cs.get(j) == Some(&'(');
427 let is_axis = cs.get(j) == Some(&':') && cs.get(j + 1) == Some(&':');
428 if after_operand && !is_fn && !is_axis {
431 match text.as_str() {
432 "and" | "or" | "mod" | "div" => {
433 out.push(Tok::Op(match text.as_str() {
434 "and" => "and",
435 "or" => "or",
436 "mod" => "mod",
437 _ => "div",
438 }));
439 continue;
440 }
441 _ => {}
442 }
443 }
444 out.push(Tok::Name {
445 text,
446 is_fn,
447 is_axis,
448 });
449 }
450 other => return Err(format!("unexpected character `{other}`")),
451 }
452 }
453 Ok(out)
454}
455
456fn num(cs: &[char]) -> Result<f64, String> {
457 let s: String = cs.iter().collect();
458 s.parse::<f64>().map_err(|_| format!("bad number `{s}`"))
459}
460
461struct P {
464 toks: Vec<Tok>,
465 i: usize,
466}
467
468pub fn parse(src: &str) -> Result<Expr, String> {
475 let toks = lex(src)?;
476 if toks.is_empty() {
477 return Err("empty expression".into());
478 }
479 let mut p = P { toks, i: 0 };
480 let e = p.expr()?;
481 if p.i != p.toks.len() {
482 return Err(format!(
483 "unexpected `{}` after a complete expression",
484 p.toks[p.i]
485 ));
486 }
487 Ok(e)
488}
489
490impl P {
491 fn peek(&self) -> Option<&Tok> {
492 self.toks.get(self.i)
493 }
494
495 fn eat(&mut self, t: &Tok) -> bool {
496 if self.peek() == Some(t) {
497 self.i += 1;
498 true
499 } else {
500 false
501 }
502 }
503
504 fn expect(&mut self, t: &Tok) -> Result<(), String> {
505 if self.eat(t) {
506 Ok(())
507 } else {
508 Err(match self.peek() {
509 Some(g) => format!("expected `{t}`, found `{g}`"),
510 None => format!("expected `{t}`, found end of expression"),
511 })
512 }
513 }
514
515 fn expr(&mut self) -> Result<Expr, String> {
517 let mut l = self.and_expr()?;
518 while self.eat(&Tok::Op("or")) {
519 l = Expr::Or(Box::new(l), Box::new(self.and_expr()?));
520 }
521 Ok(l)
522 }
523
524 fn and_expr(&mut self) -> Result<Expr, String> {
525 let mut l = self.eq_expr()?;
526 while self.eat(&Tok::Op("and")) {
527 l = Expr::And(Box::new(l), Box::new(self.eq_expr()?));
528 }
529 Ok(l)
530 }
531
532 fn eq_expr(&mut self) -> Result<Expr, String> {
533 let mut l = self.rel_expr()?;
534 loop {
535 if self.eat(&Tok::Eq) {
536 l = Expr::Eq(Box::new(l), Box::new(self.rel_expr()?));
537 } else if self.eat(&Tok::Ne) {
538 l = Expr::Ne(Box::new(l), Box::new(self.rel_expr()?));
539 } else {
540 return Ok(l);
541 }
542 }
543 }
544
545 fn rel_expr(&mut self) -> Result<Expr, String> {
546 let mut l = self.add_expr()?;
547 loop {
548 let op = match self.peek() {
549 Some(Tok::Lt) => RelOp::Lt,
550 Some(Tok::Gt) => RelOp::Gt,
551 Some(Tok::Le) => RelOp::Le,
552 Some(Tok::Ge) => RelOp::Ge,
553 _ => return Ok(l),
554 };
555 self.i += 1;
556 l = Expr::Rel(op, Box::new(l), Box::new(self.add_expr()?));
557 }
558 }
559
560 fn add_expr(&mut self) -> Result<Expr, String> {
561 let mut l = self.mul_expr()?;
562 loop {
563 if self.eat(&Tok::Plus) {
564 l = Expr::Add(Box::new(l), Box::new(self.mul_expr()?));
565 } else if self.eat(&Tok::Minus) {
566 l = Expr::Sub(Box::new(l), Box::new(self.mul_expr()?));
567 } else {
568 return Ok(l);
569 }
570 }
571 }
572
573 fn mul_expr(&mut self) -> Result<Expr, String> {
574 let mut l = self.unary_expr()?;
575 loop {
576 if self.eat(&Tok::Star) {
579 l = Expr::Mul(Box::new(l), Box::new(self.unary_expr()?));
580 } else if self.eat(&Tok::Op("div")) {
581 l = Expr::Div(Box::new(l), Box::new(self.unary_expr()?));
582 } else if self.eat(&Tok::Op("mod")) {
583 l = Expr::Mod(Box::new(l), Box::new(self.unary_expr()?));
584 } else {
585 return Ok(l);
586 }
587 }
588 }
589
590 fn unary_expr(&mut self) -> Result<Expr, String> {
592 if self.eat(&Tok::Minus) {
593 return Ok(Expr::Neg(Box::new(self.unary_expr()?)));
594 }
595 self.union_expr()
596 }
597
598 fn union_expr(&mut self) -> Result<Expr, String> {
599 let mut l = self.path_expr()?;
600 while self.eat(&Tok::Pipe) {
601 l = Expr::Union(Box::new(l), Box::new(self.path_expr()?));
602 }
603 Ok(l)
604 }
605
606 fn path_expr(&mut self) -> Result<Expr, String> {
611 let node_type_ahead = matches!(
618 self.peek(),
619 Some(Tok::Name { text, is_fn: true, .. })
620 if matches!(text.as_str(), "node" | "text" | "comment" | "processing-instruction")
621 );
622 let is_filter = !node_type_ahead
623 && (matches!(
624 self.peek(),
625 Some(Tok::Num(_)) | Some(Tok::Str(_)) | Some(Tok::LParen)
626 ) || matches!(self.peek(), Some(Tok::Name { is_fn: true, .. })));
627 if is_filter {
628 let base = self.primary_expr()?;
629 let mut preds = Vec::new();
630 while self.eat(&Tok::LBracket) {
631 preds.push(self.expr()?);
632 self.expect(&Tok::RBracket)?;
633 }
634 let mut steps = Vec::new();
635 if self.eat(&Tok::DblSlash) {
636 steps.push(descendant_or_self());
637 steps.extend(self.relative_path()?);
638 } else if self.eat(&Tok::Slash) {
639 steps.extend(self.relative_path()?);
640 }
641 if preds.is_empty() && steps.is_empty() {
647 return Ok(base);
648 }
649 return Ok(Expr::Path(PathStart::Filter(Box::new(base), preds), steps));
650 }
651 self.location_path()
652 }
653
654 fn location_path(&mut self) -> Result<Expr, String> {
656 if self.eat(&Tok::DblSlash) {
657 let mut steps = vec![descendant_or_self()];
659 steps.extend(self.relative_path()?);
660 return Ok(Expr::Path(PathStart::Root, steps));
661 }
662 if self.eat(&Tok::Slash) {
663 if self.starts_step() {
668 let steps = self.relative_path()?;
669 return Ok(Expr::Path(PathStart::Root, steps));
670 }
671 return Ok(Expr::Path(PathStart::Root, Vec::new()));
672 }
673 let steps = self.relative_path()?;
674 Ok(Expr::Path(PathStart::Relative, steps))
675 }
676
677 fn starts_step(&self) -> bool {
679 matches!(
680 self.peek(),
681 Some(Tok::At | Tok::Dot | Tok::DblDot | Tok::Star | Tok::Name { .. })
682 )
683 }
684
685 fn relative_path(&mut self) -> Result<Vec<Step>, String> {
686 let mut steps = vec![self.step()?];
687 loop {
688 if self.eat(&Tok::DblSlash) {
689 steps.push(descendant_or_self());
690 steps.push(self.step()?);
691 } else if self.eat(&Tok::Slash) {
692 steps.push(self.step()?);
693 } else {
694 return Ok(steps);
695 }
696 }
697 }
698
699 fn step(&mut self) -> Result<Step, String> {
701 if self.eat(&Tok::Dot) {
703 return Ok(Step {
704 axis: Axis::SelfAxis,
705 test: NodeTest::Node,
706 preds: Vec::new(),
707 });
708 }
709 if self.eat(&Tok::DblDot) {
710 return Ok(Step {
711 axis: Axis::Parent,
712 test: NodeTest::Node,
713 preds: Vec::new(),
714 });
715 }
716 let axis = if self.eat(&Tok::At) {
718 Axis::Attribute
719 } else if let Some(Tok::Name {
720 text,
721 is_axis: true,
722 ..
723 }) = self.peek()
724 {
725 let name = text.clone();
726 let a =
727 Axis::from_name(&name).ok_or_else(|| format!("`{name}` is not an XPath axis"))?;
728 self.i += 1;
729 self.expect(&Tok::DblColon)?;
730 a
731 } else {
732 Axis::Child
733 };
734 let test = self.node_test()?;
735 let mut preds = Vec::new();
736 while self.eat(&Tok::LBracket) {
737 preds.push(self.expr()?);
738 self.expect(&Tok::RBracket)?;
739 }
740 Ok(Step { axis, test, preds })
741 }
742
743 fn node_test(&mut self) -> Result<NodeTest, String> {
745 if self.eat(&Tok::Star) {
746 return Ok(NodeTest::Any);
747 }
748 let (text, is_fn) = match self.peek() {
749 Some(Tok::Name { text, is_fn, .. }) => (text.clone(), *is_fn),
750 Some(t) => return Err(format!("expected a node test, found `{t}`")),
751 None => return Err("expected a node test, found end of expression".into()),
752 };
753 self.i += 1;
754 if is_fn {
755 self.expect(&Tok::LParen)?;
756 let t = match text.as_str() {
757 "node" => NodeTest::Node,
758 "text" => NodeTest::Text,
759 "comment" => NodeTest::Comment,
760 "processing-instruction" => {
761 if let Some(Tok::Str(s)) = self.peek() {
762 let s = s.clone();
763 self.i += 1;
764 NodeTest::Pi(Some(s))
765 } else {
766 NodeTest::Pi(None)
767 }
768 }
769 other => {
770 return Err(format!(
771 "`{other}()` is not a node type (expected node, text, comment or \
772 processing-instruction)"
773 ))
774 }
775 };
776 self.expect(&Tok::RParen)?;
777 return Ok(t);
778 }
779 if let Some(prefix) = text.strip_suffix(":*") {
780 return Ok(NodeTest::AnyInPrefix(prefix.to_string()));
781 }
782 Ok(NodeTest::Name(text))
783 }
784
785 fn primary_expr(&mut self) -> Result<Expr, String> {
787 match self.peek().cloned() {
788 Some(Tok::Num(n)) => {
789 self.i += 1;
790 Ok(Expr::Number(n))
791 }
792 Some(Tok::Str(s)) => {
793 self.i += 1;
794 Ok(Expr::Literal(s))
795 }
796 Some(Tok::LParen) => {
797 self.i += 1;
798 let e = self.expr()?;
799 self.expect(&Tok::RParen)?;
800 Ok(e)
801 }
802 Some(Tok::Name {
803 text, is_fn: true, ..
804 }) => {
805 self.i += 1;
806 self.expect(&Tok::LParen)?;
807 let mut args = Vec::new();
808 if !self.eat(&Tok::RParen) {
809 loop {
810 args.push(self.expr()?);
811 if self.eat(&Tok::Comma) {
812 continue;
813 }
814 self.expect(&Tok::RParen)?;
815 break;
816 }
817 }
818 Ok(Expr::Call(text, args))
819 }
820 Some(t) => Err(format!("expected an expression, found `{t}`")),
821 None => Err("expected an expression, found end of expression".into()),
822 }
823 }
824}
825
826fn descendant_or_self() -> Step {
828 Step {
829 axis: Axis::DescendantOrSelf,
830 test: NodeTest::Node,
831 preds: Vec::new(),
832 }
833}