1use crate::ast::{BinOp, Expr, Step};
8use crate::comment::CommentKind;
9use crate::lexer::Lx;
10use crate::value::Value;
11use logos::Logos;
12
13#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
15#[error("{msg} (at offset {pos})")]
16pub struct ParseError {
17 pub msg: String,
18 pub pos: usize,
19}
20
21struct Tok {
22 kind: Lx,
23 text: String,
24 start: usize,
25}
26
27pub fn parse(src: &str) -> Result<Expr, ParseError> {
29 let toks = lex(src)?;
30 let mut p = Parser { toks, pos: 0 };
31 let e = p.parse_program()?;
32 if p.pos != p.toks.len() {
33 let t = &p.toks[p.pos];
34 return Err(ParseError {
35 msg: format!("unexpected trailing token `{}`", t.text),
36 pos: t.start,
37 });
38 }
39 Ok(e)
40}
41
42fn lex(src: &str) -> Result<Vec<Tok>, ParseError> {
43 let mut lx = Lx::lexer(src);
44 let mut out = Vec::new();
45 while let Some(res) = lx.next() {
46 let span = lx.span();
47 match res {
48 Ok(kind) => out.push(Tok {
49 kind,
50 text: lx.slice().to_string(),
51 start: span.start,
52 }),
53 Err(_) => {
54 return Err(ParseError {
55 msg: format!("unexpected character `{}`", lx.slice()),
56 pos: span.start,
57 });
58 }
59 }
60 }
61 Ok(out)
62}
63
64struct Parser {
65 toks: Vec<Tok>,
66 pos: usize,
67}
68
69impl Parser {
70 fn peek(&self) -> Option<Lx> {
71 self.toks.get(self.pos).map(|t| t.kind)
72 }
73 fn text(&self) -> &str {
74 self.toks
75 .get(self.pos)
76 .map(|t| t.text.as_str())
77 .unwrap_or("")
78 }
79 fn at_end(&self) -> usize {
80 self.toks
81 .last()
82 .map(|t| t.start + t.text.len())
83 .unwrap_or(0)
84 }
85 fn err_here(&self, msg: impl Into<String>) -> ParseError {
86 let pos = self
87 .toks
88 .get(self.pos)
89 .map(|t| t.start)
90 .unwrap_or_else(|| self.at_end());
91 ParseError {
92 msg: msg.into(),
93 pos,
94 }
95 }
96 fn expect(&mut self, kind: Lx, what: &str) -> Result<(), ParseError> {
97 if self.peek() == Some(kind) {
98 self.pos += 1;
99 Ok(())
100 } else {
101 Err(self.err_here(format!("expected {what}")))
102 }
103 }
104
105 fn parse_program(&mut self) -> Result<Expr, ParseError> {
108 if self.peek() != Some(Lx::Caret) {
109 return self.parse_pipe();
110 }
111 self.pos += 1; let n = match self.peek() {
113 Some(Lx::Ident) => {
114 let digits = self.text().strip_prefix('d').ok_or_else(|| {
115 self.err_here("document selector is `^dN`, e.g. `^d0` (document 0)")
116 })?;
117 let n = digits.parse::<usize>().map_err(|_| {
118 self.err_here("`^dN` needs a document index, e.g. `^d0` (document 0)")
119 })?;
120 self.pos += 1;
121 n
122 }
123 _ => {
124 return Err(self.err_here("expected a document index after `^`, e.g. `^d0`"));
125 }
126 };
127 if self.peek() == Some(Lx::Pipe) {
130 self.pos += 1;
131 }
132 let body = if self.peek().is_none() {
133 Expr::Path(Vec::new())
134 } else {
135 self.parse_pipe()?
136 };
137 Ok(Expr::DocSelect(n, Box::new(body)))
138 }
139
140 fn parse_pipe(&mut self) -> Result<Expr, ParseError> {
141 let mut left = self.parse_comma()?;
142 while self.peek() == Some(Lx::Pipe) {
143 self.pos += 1;
144 let right = self.parse_comma()?;
145 left = Expr::Pipe(Box::new(left), Box::new(right));
146 }
147 Ok(left)
148 }
149
150 fn parse_comma(&mut self) -> Result<Expr, ParseError> {
151 let first = self.parse_assign()?;
152 if self.peek() != Some(Lx::Comma) {
153 return Ok(first);
154 }
155 let mut items = vec![first];
156 while self.peek() == Some(Lx::Comma) {
157 self.pos += 1;
158 items.push(self.parse_assign()?);
159 }
160 Ok(Expr::Comma(items))
161 }
162
163 fn parse_assign(&mut self) -> Result<Expr, ParseError> {
164 let lhs = self.parse_alt()?;
165 match self.peek() {
166 Some(Lx::Assign) => {
167 self.reject_hyphen_key_lhs(&lhs)?;
168 self.pos += 1;
169 let rhs = self.parse_assign()?; Ok(Expr::Assign(Box::new(lhs), Box::new(rhs)))
171 }
172 Some(Lx::PipeAssign) => {
173 self.reject_hyphen_key_lhs(&lhs)?;
174 self.pos += 1;
175 let rhs = self.parse_assign()?;
176 Ok(Expr::UpdateAssign(Box::new(lhs), Box::new(rhs)))
177 }
178 Some(Lx::PlusAssign) => {
179 self.reject_hyphen_key_lhs(&lhs)?;
180 self.pos += 1;
181 let rhs = self.parse_assign()?;
182 Ok(Expr::AddAssign(Box::new(lhs), Box::new(rhs)))
183 }
184 _ => Ok(lhs),
185 }
186 }
187
188 fn reject_hyphen_key_lhs(&self, lhs: &Expr) -> Result<(), ParseError> {
195 let Some((path, key)) = hyphen_key(lhs) else {
196 return Ok(());
197 };
198 Err(self.err_here(format!(
199 "key `{key}` contains `-` (parsed as subtraction); quote it: {path}"
200 )))
201 }
202
203 fn parse_alt(&mut self) -> Result<Expr, ParseError> {
206 let left = self.parse_cmp()?;
207 if self.peek() == Some(Lx::Alt) {
208 self.pos += 1;
209 let right = self.parse_alt()?;
210 return Ok(Expr::Alternative(Box::new(left), Box::new(right)));
211 }
212 Ok(left)
213 }
214
215 fn parse_cmp(&mut self) -> Result<Expr, ParseError> {
216 let left = self.parse_add()?;
217 let op = match self.peek() {
218 Some(Lx::EqEq) => BinOp::Eq,
219 Some(Lx::Ne) => BinOp::Ne,
220 Some(Lx::Lt) => BinOp::Lt,
221 Some(Lx::Gt) => BinOp::Gt,
222 Some(Lx::Le) => BinOp::Le,
223 Some(Lx::Ge) => BinOp::Ge,
224 _ => return Ok(left),
225 };
226 self.pos += 1;
227 let right = self.parse_add()?;
228 Ok(Expr::Binary(op, Box::new(left), Box::new(right)))
229 }
230
231 fn parse_add(&mut self) -> Result<Expr, ParseError> {
232 let mut left = self.parse_mul()?;
233 loop {
234 let op = match self.peek() {
235 Some(Lx::Plus) => BinOp::Add,
236 Some(Lx::Minus) => BinOp::Sub,
237 _ => break,
238 };
239 self.pos += 1;
240 let right = self.parse_mul()?;
241 left = Expr::Binary(op, Box::new(left), Box::new(right));
242 }
243 Ok(left)
244 }
245
246 fn parse_mul(&mut self) -> Result<Expr, ParseError> {
247 let mut left = self.parse_unary()?;
248 loop {
249 let op = match self.peek() {
250 Some(Lx::Star) => BinOp::Mul,
251 Some(Lx::Slash) => BinOp::Div,
252 Some(Lx::Percent) => BinOp::Mod,
253 _ => break,
254 };
255 self.pos += 1;
256 let right = self.parse_unary()?;
257 left = Expr::Binary(op, Box::new(left), Box::new(right));
258 }
259 Ok(left)
260 }
261
262 fn parse_unary(&mut self) -> Result<Expr, ParseError> {
263 if self.peek() == Some(Lx::Minus) {
264 self.pos += 1;
265 return Ok(Expr::Neg(Box::new(self.parse_unary()?)));
266 }
267 self.parse_primary()
268 }
269
270 fn parse_primary(&mut self) -> Result<Expr, ParseError> {
271 match self.peek() {
272 Some(Lx::Dot) => self.parse_path(),
273 Some(Lx::LParen) => {
274 self.pos += 1;
275 let e = self.parse_pipe()?;
276 self.expect(Lx::RParen, "`)`")?;
277 Ok(e)
278 }
279 Some(Lx::LBrack) => {
280 self.pos += 1;
281 if self.peek() == Some(Lx::RBrack) {
282 self.pos += 1;
283 return Ok(Expr::Collect(None));
284 }
285 let inner = self.parse_pipe()?;
286 self.expect(Lx::RBrack, "`]`")?;
287 Ok(Expr::Collect(Some(Box::new(inner))))
288 }
289 Some(Lx::LBrace) => self.parse_object_construct(),
290 Some(Lx::Num) => {
291 let v = number_value(self.text());
292 self.pos += 1;
293 Ok(Expr::Literal(v))
294 }
295 Some(Lx::Str) => {
296 let v = Value::Str(unescape(self.text()));
297 self.pos += 1;
298 Ok(Expr::Literal(v))
299 }
300 Some(Lx::Ident) => self.parse_ident(),
301 _ => Err(self.err_here("expected an expression")),
302 }
303 }
304
305 fn parse_object_construct(&mut self) -> Result<Expr, ParseError> {
306 self.pos += 1; let mut pairs = Vec::new();
308 if self.peek() == Some(Lx::RBrace) {
309 self.pos += 1;
310 return Ok(Expr::ObjectConstruct(pairs));
311 }
312 loop {
313 let key = match self.peek() {
314 Some(Lx::Ident) => self.text().to_string(),
315 Some(Lx::Str) => unescape(self.text()),
316 _ => return Err(self.err_here("expected an object key")),
317 };
318 self.pos += 1;
319 match self.peek() {
324 Some(Lx::Colon) | Some(Lx::Assign) => self.pos += 1,
325 _ => return Err(self.err_here("expected `:` or `=`")),
326 }
327 let value = self.parse_cmp()?;
329 pairs.push((key, value));
330 match self.peek() {
331 Some(Lx::Comma) => self.pos += 1,
332 Some(Lx::RBrace) => {
333 self.pos += 1;
334 break;
335 }
336 _ => return Err(self.err_here("expected `,` or `}`")),
337 }
338 }
339 Ok(Expr::ObjectConstruct(pairs))
340 }
341
342 fn parse_path(&mut self) -> Result<Expr, ParseError> {
343 self.pos += 1; let mut steps = Vec::new();
345 loop {
346 match self.peek() {
347 Some(Lx::Ident) => {
348 steps.push(Step::Field(self.text().to_string()));
349 self.pos += 1;
350 }
351 Some(Lx::Str) => {
352 steps.push(Step::Field(unescape(self.text())));
353 self.pos += 1;
354 }
355 Some(Lx::LBrack) => {
356 self.pos += 1;
357 if self.peek() == Some(Lx::RBrack) {
358 self.pos += 1;
359 steps.push(Step::Iterate);
360 } else if self.peek() == Some(Lx::Str) {
361 let key = unescape(self.text());
363 self.pos += 1;
364 self.expect(Lx::RBrack, "`]`")?;
365 steps.push(Step::Field(key));
366 } else {
367 let neg = self.peek() == Some(Lx::Minus);
368 if neg {
369 self.pos += 1;
370 }
371 if self.peek() != Some(Lx::Num) {
372 return Err(self.err_here("expected an array index or a string key"));
373 }
374 let n = parse_i64(self.text())
375 .map_err(|_| self.err_here("array index out of range"))?;
376 self.pos += 1;
377 self.expect(Lx::RBrack, "`]`")?;
378 steps.push(Step::Index(if neg { -n } else { n }));
379 }
380 }
381 Some(Lx::Hash) => {
382 self.pos += 1;
386 let mut kind = CommentKind::Head;
387 if self.peek() == Some(Lx::Dot)
388 && let Some(word) =
389 self.toks.get(self.pos + 1).filter(|t| t.kind == Lx::Ident)
390 && let Some(k) = comment_kind(&word.text)
391 {
392 self.pos += 2; kind = k;
394 }
395 steps.push(Step::Comment(kind));
396 break;
397 }
398 _ => break,
399 }
400 match self.peek() {
401 Some(Lx::Dot) => {
402 self.pos += 1;
403 continue;
404 }
405 Some(Lx::LBrack) => continue,
406 _ => break,
407 }
408 }
409 Ok(Expr::Path(steps))
410 }
411
412 fn parse_ident(&mut self) -> Result<Expr, ParseError> {
413 let name = self.text().to_string();
414 self.pos += 1;
415 match name.as_str() {
416 "true" => return Ok(Expr::Literal(Value::Bool(true))),
417 "false" => return Ok(Expr::Literal(Value::Bool(false))),
418 "null" => return Ok(Expr::Literal(Value::Null)),
419 _ => {}
420 }
421 if self.peek() == Some(Lx::LParen) {
422 self.pos += 1;
423 let mut args = vec![self.parse_pipe()?];
424 while self.peek() == Some(Lx::Semi) {
425 self.pos += 1;
426 args.push(self.parse_pipe()?);
427 }
428 self.expect(Lx::RParen, "`)`")?;
429 Ok(Expr::Call(name, args))
430 } else {
431 Ok(Expr::Call(name, Vec::new()))
432 }
433 }
434}
435
436fn hyphen_key(expr: &Expr) -> Option<(String, String)> {
444 let mut tail: Vec<&str> = Vec::new();
445 let mut cur = expr;
446 while let Expr::Binary(BinOp::Sub, l, r) = cur {
447 match r.as_ref() {
448 Expr::Call(name, args) if args.is_empty() => tail.push(name.as_str()),
449 _ => return None,
450 }
451 cur = l;
452 }
453 if tail.is_empty() {
454 return None;
455 }
456 let Expr::Path(steps) = cur else {
457 return None;
458 };
459 let Some((Step::Field(first), prefix)) = steps.split_last() else {
460 return None;
461 };
462 tail.push(first.as_str());
463 tail.reverse();
464 let key = tail.join("-");
465 let mut path = String::new();
466 for step in prefix {
467 match step {
468 Step::Field(f) if is_bare_key(f) => {
469 path.push('.');
470 path.push_str(f);
471 }
472 Step::Field(f) => {
473 path.push_str(&format!(".\"{f}\""));
474 }
475 Step::Index(i) => path.push_str(&format!("[{i}]")),
476 _ => return None,
477 }
478 }
479 path.push_str(&format!(".\"{key}\""));
480 Some((path, key))
481}
482
483fn is_bare_key(k: &str) -> bool {
485 let mut chars = k.chars();
486 chars
487 .next()
488 .is_some_and(|c| c.is_ascii_alphabetic() || c == '_')
489 && chars.all(|c| c.is_ascii_alphanumeric() || c == '_')
490}
491
492fn comment_kind(word: &str) -> Option<CommentKind> {
493 match word {
494 "head" => Some(CommentKind::Head),
495 "inline" => Some(CommentKind::Inline),
496 "foot" => Some(CommentKind::Foot),
497 _ => None,
498 }
499}
500
501fn number_value(t: &str) -> Value {
502 if t.contains(['.', 'e', 'E']) {
503 Value::Float(t.parse().unwrap_or(0.0))
504 } else {
505 match t.parse::<i64>() {
506 Ok(i) => Value::Int(i),
507 Err(_) => Value::Float(t.parse().unwrap_or(0.0)),
508 }
509 }
510}
511
512fn parse_i64(t: &str) -> Result<i64, std::num::ParseIntError> {
513 t.parse::<i64>()
514}
515
516fn unescape(tok: &str) -> String {
518 let inner = tok
519 .strip_prefix('"')
520 .and_then(|s| s.strip_suffix('"'))
521 .unwrap_or(tok);
522 let mut out = String::with_capacity(inner.len());
523 let mut chars = inner.chars();
524 while let Some(c) = chars.next() {
525 if c != '\\' {
526 out.push(c);
527 continue;
528 }
529 match chars.next() {
530 Some('"') => out.push('"'),
531 Some('\\') => out.push('\\'),
532 Some('/') => out.push('/'),
533 Some('n') => out.push('\n'),
534 Some('r') => out.push('\r'),
535 Some('t') => out.push('\t'),
536 Some('b') => out.push('\u{0008}'),
537 Some('f') => out.push('\u{000c}'),
538 Some('u') => {
539 let hex: String = chars.by_ref().take(4).collect();
540 if let Some(ch) = u32::from_str_radix(&hex, 16).ok().and_then(char::from_u32) {
541 out.push(ch);
542 }
543 }
544 Some(other) => {
545 out.push('\\');
546 out.push(other);
547 }
548 None => out.push('\\'),
549 }
550 }
551 out
552}
553
554#[cfg(test)]
555mod tests {
556 use super::*;
557
558 fn p(s: &str) -> Expr {
559 parse(s).unwrap_or_else(|e| panic!("parse `{s}`: {e}"))
560 }
561
562 #[test]
563 fn identity() {
564 assert_eq!(p("."), Expr::Path(vec![]));
565 }
566
567 #[test]
568 fn doc_select_parses() {
569 assert_eq!(
571 p("^d0 | .kind"),
572 Expr::DocSelect(0, Box::new(Expr::Path(vec![Step::Field("kind".into())])))
573 );
574 assert_eq!(
575 p("^d2.spec"),
576 Expr::DocSelect(2, Box::new(Expr::Path(vec![Step::Field("spec".into())])))
577 );
578 assert_eq!(p("^d1"), Expr::DocSelect(1, Box::new(Expr::Path(vec![]))));
579 assert!(p("^d0 | .replicas = 3").is_mutation());
581 }
582
583 #[test]
584 fn doc_select_bad_index_errors() {
585 assert!(parse("^dfoo | .x").is_err());
586 assert!(parse("^x").is_err());
587 assert!(parse("^ | .x").is_err());
588 }
589
590 #[test]
591 fn dotted_path() {
592 assert_eq!(
593 p(".a.b"),
594 Expr::Path(vec![Step::Field("a".into()), Step::Field("b".into())])
595 );
596 }
597
598 #[test]
599 fn index_and_iterate() {
600 assert_eq!(
601 p(".arr[0][]"),
602 Expr::Path(vec![
603 Step::Field("arr".into()),
604 Step::Index(0),
605 Step::Iterate
606 ])
607 );
608 assert_eq!(
609 p(".x[-1]"),
610 Expr::Path(vec![Step::Field("x".into()), Step::Index(-1)])
611 );
612 }
613
614 #[test]
615 fn quoted_field() {
616 assert_eq!(
617 p(r#"."weird key""#),
618 Expr::Path(vec![Step::Field("weird key".into())])
619 );
620 }
621
622 #[test]
623 fn literals() {
624 assert_eq!(p("true"), Expr::Literal(Value::Bool(true)));
625 assert_eq!(p("null"), Expr::Literal(Value::Null));
626 assert_eq!(p("42"), Expr::Literal(Value::Int(42)));
627 assert_eq!(p("1.5"), Expr::Literal(Value::Float(1.5)));
628 assert_eq!(p(r#""hi""#), Expr::Literal(Value::Str("hi".into())));
629 }
630
631 #[test]
632 fn arithmetic_precedence() {
633 assert_eq!(
635 p("1 + 2 * 3"),
636 Expr::Binary(
637 BinOp::Add,
638 Box::new(Expr::Literal(Value::Int(1))),
639 Box::new(Expr::Binary(
640 BinOp::Mul,
641 Box::new(Expr::Literal(Value::Int(2))),
642 Box::new(Expr::Literal(Value::Int(3))),
643 )),
644 )
645 );
646 }
647
648 #[test]
649 fn pipe_and_select() {
650 let e = p(r#".items[] | select(.name == "x")"#);
651 match e {
652 Expr::Pipe(l, r) => {
653 assert_eq!(
654 *l,
655 Expr::Path(vec![Step::Field("items".into()), Step::Iterate])
656 );
657 match *r {
658 Expr::Call(ref name, ref args) => {
659 assert_eq!(name, "select");
660 assert_eq!(args.len(), 1);
661 }
662 _ => panic!("expected select call"),
663 }
664 }
665 _ => panic!("expected pipe"),
666 }
667 }
668
669 #[test]
670 fn errors() {
671 assert!(parse(".a.").is_ok()); assert!(parse("(").is_err());
673 assert!(parse(".a b").is_err()); assert!(parse("@").is_err()); }
676
677 #[test]
678 fn comment_accessor() {
679 use crate::comment::CommentKind;
680 assert_eq!(
682 p(".foo.#"),
683 Expr::Path(vec![
684 Step::Field("foo".into()),
685 Step::Comment(CommentKind::Head)
686 ])
687 );
688 assert_eq!(
690 p(".foo.#.inline"),
691 Expr::Path(vec![
692 Step::Field("foo".into()),
693 Step::Comment(CommentKind::Inline)
694 ])
695 );
696 assert_eq!(
697 p(".a.#.foot"),
698 Expr::Path(vec![
699 Step::Field("a".into()),
700 Step::Comment(CommentKind::Foot)
701 ])
702 );
703 assert_eq!(p(".#"), Expr::Path(vec![Step::Comment(CommentKind::Head)]));
705 assert_eq!(
707 p(".items[].#"),
708 Expr::Path(vec![
709 Step::Field("items".into()),
710 Step::Iterate,
711 Step::Comment(CommentKind::Head)
712 ])
713 );
714 assert!(parse(".foo.#.bar").is_err());
716 }
717
718 #[test]
719 fn object_construct_accepts_toml_equals() {
720 assert_eq!(
723 p(r#"{version = "1", optional: true}"#),
724 Expr::ObjectConstruct(vec![
725 ("version".into(), Expr::Literal(Value::Str("1".into()))),
726 ("optional".into(), Expr::Literal(Value::Bool(true))),
727 ])
728 );
729 }
730
731 #[test]
732 fn object_construct_names_both_separators() {
733 let e = parse("{a 1}").unwrap_err();
734 assert!(e.to_string().contains("expected `:` or `=`"), "got: {e}");
735 }
736
737 #[test]
738 fn hyphenated_assign_lhs_hints_the_quoted_form() {
739 let e = parse(r#".package.rust-version = "1.85""#).unwrap_err();
740 assert_eq!(
741 e.to_string(),
742 "key `rust-version` contains `-` (parsed as subtraction); \
743 quote it: .package.\"rust-version\" (at offset 22)"
744 );
745 let e = parse(".lib.crate-type-x |= 1").unwrap_err();
747 assert!(e.to_string().contains("`crate-type-x`"), "got: {e}");
748 assert!(e.to_string().contains(".lib.\"crate-type-x\""), "got: {e}");
749 let e = parse(".a.b-c += 1").unwrap_err();
750 assert!(e.to_string().contains("`b-c`"), "got: {e}");
751 let e = parse(".rust-version = 1").unwrap_err();
753 assert!(e.to_string().contains(".\"rust-version\""), "got: {e}");
754 }
755
756 #[test]
757 fn hyphen_hint_leaves_real_subtraction_alone() {
758 assert_eq!(
760 p(".a-b"),
761 Expr::Binary(
762 BinOp::Sub,
763 Box::new(Expr::Path(vec![Step::Field("a".into())])),
764 Box::new(Expr::Call("b".into(), vec![]))
765 )
766 );
767 assert!(parse(".a - 1 = 2").is_ok());
771 p(".x = .a - .b");
773 }
774}