1use crate::token::{SpannedToken, Token};
22use std::time::Duration;
23
24#[derive(Debug, Clone, PartialEq, thiserror::Error)]
30#[error("{message} at line {line}, column {col}")]
31#[non_exhaustive]
32pub struct LexError {
33 pub message: String,
34 pub line: u32,
35 pub col: u32,
36}
37
38pub fn tokenize(input: &str) -> Result<Vec<SpannedToken>, LexError> {
64 Lexer::new(input).run()
65}
66
67struct Lexer<'a> {
68 chars: std::iter::Peekable<std::str::Chars<'a>>,
69 line: u32,
70 col: u32,
71}
72
73impl<'a> Lexer<'a> {
74 fn new(input: &'a str) -> Self {
75 Self {
76 chars: input.chars().peekable(),
77 line: 1,
78 col: 1,
79 }
80 }
81
82 fn error(&self, message: impl Into<String>, line: u32, col: u32) -> LexError {
83 LexError {
84 message: message.into(),
85 line,
86 col,
87 }
88 }
89
90 fn bump(&mut self) -> Option<char> {
91 let c = self.chars.next()?;
92 if c == '\n' {
93 self.line += 1;
94 self.col = 1;
95 } else {
96 self.col += 1;
97 }
98 Some(c)
99 }
100
101 fn peek2(&self) -> Option<char> {
105 let mut lookahead = self.chars.clone();
106 lookahead.next();
107 lookahead.peek().copied()
108 }
109
110 fn eat(&mut self, expected: char) -> bool {
112 if self.chars.peek() == Some(&expected) {
113 self.bump();
114 true
115 } else {
116 false
117 }
118 }
119
120 fn run(mut self) -> Result<Vec<SpannedToken>, LexError> {
121 let mut tokens = Vec::new();
122 loop {
123 match self.chars.peek() {
125 Some(c) if c.is_whitespace() => {
126 self.bump();
127 continue;
128 }
129 Some('#') => {
130 while let Some(&c) = self.chars.peek() {
131 if c == '\n' {
132 break;
133 }
134 self.bump();
135 }
136 continue;
137 }
138 None => break,
139 _ => {}
140 }
141
142 let (line, col) = (self.line, self.col);
143 let c = self.bump().expect("peeked above");
144 let token = match c {
145 '{' => Token::LBrace,
146 '}' => Token::RBrace,
147 '(' => Token::LParen,
148 ')' => Token::RParen,
149 '[' => Token::LBracket,
150 ']' => Token::RBracket,
151 ',' => Token::Comma,
152 '+' => Token::Add,
153 '-' => {
154 if self.eat('-') {
157 self.lex_flag(line, col)?
158 } else {
159 Token::Sub
160 }
161 }
162 '*' => Token::Mul,
163 '/' => Token::Div,
164 '%' => Token::Mod,
165 '^' => Token::Pow,
166 '|' => {
167 if self.eat('=') {
168 Token::PipeExact
169 } else if self.eat('~') {
170 Token::PipeRegex
171 } else {
172 Token::Pipe
173 }
174 }
175 '=' => {
176 if self.eat('=') {
177 Token::CmpEq
178 } else if self.eat('~') {
179 Token::Re
180 } else {
181 Token::Eq
182 }
183 }
184 '!' => {
185 if self.eat('=') {
186 Token::Neq
187 } else if self.eat('~') {
188 Token::Nre
189 } else {
190 return Err(self.error(
191 "unexpected '!' (expected '!=' or '!~')",
192 line,
193 col,
194 ));
195 }
196 }
197 '>' => {
198 if self.eat('=') {
199 Token::Gte
200 } else {
201 Token::Gt
202 }
203 }
204 '<' => {
205 if self.eat('=') {
206 Token::Lte
207 } else {
208 Token::Lt
209 }
210 }
211 '"' => self.lex_string(line, col)?,
212 '`' => self.lex_raw_string(line, col)?,
213 c if c.is_ascii_digit() => self.lex_number_or_duration(c, line, col)?,
214 c if c.is_alphabetic() || c == '_' => {
215 let mut word = String::from(c);
216 loop {
217 match self.chars.peek() {
218 Some(&next) if next.is_alphanumeric() || next == '_' => {
219 word.push(next);
220 self.bump();
221 }
222 Some(&'.') => match self.peek2() {
228 Some(after) if after.is_alphanumeric() || after == '_' => {
229 word.push('.');
230 self.bump();
231 }
232 _ => break,
233 },
234 _ => break,
235 }
236 }
237 Token::keyword(&word).unwrap_or(Token::Ident(word))
238 }
239 other => {
240 return Err(self.error(format!("unexpected character {other:?}"), line, col));
241 }
242 };
243 tokens.push(SpannedToken { token, line, col });
244 }
245 Ok(tokens)
246 }
247
248 fn lex_string(&mut self, line: u32, col: u32) -> Result<Token, LexError> {
250 let mut value = String::new();
251 loop {
252 let (c_line, c_col) = (self.line, self.col);
253 let Some(c) = self.bump() else {
254 return Err(self.error("unterminated string literal", line, col));
255 };
256 match c {
257 '"' => return Ok(Token::String(value)),
258 '\\' => {
259 let Some(esc) = self.bump() else {
260 return Err(self.error("unterminated string literal", line, col));
261 };
262 match esc {
263 '"' => value.push('"'),
264 '\\' => value.push('\\'),
265 '/' => value.push('/'),
266 'n' => value.push('\n'),
267 't' => value.push('\t'),
268 'r' => value.push('\r'),
269 'u' => {
270 let mut code = String::new();
271 for _ in 0..4 {
272 match self.bump() {
273 Some(h) if h.is_ascii_hexdigit() => code.push(h),
274 _ => {
275 return Err(self.error(
276 "invalid \\u escape (expected 4 hex digits)",
277 c_line,
278 c_col,
279 ));
280 }
281 }
282 }
283 let cp = u32::from_str_radix(&code, 16).expect("hex digits");
284 match char::from_u32(cp) {
285 Some(ch) => value.push(ch),
286 None => {
287 return Err(self.error(
288 format!("invalid unicode code point \\u{code}"),
289 c_line,
290 c_col,
291 ));
292 }
293 }
294 }
295 other => {
296 return Err(self.error(
297 format!("invalid escape sequence '\\{other}'"),
298 c_line,
299 c_col,
300 ));
301 }
302 }
303 }
304 other => value.push(other),
305 }
306 }
307 }
308
309 fn lex_raw_string(&mut self, line: u32, col: u32) -> Result<Token, LexError> {
312 let mut value = String::new();
313 loop {
314 let Some(c) = self.bump() else {
315 return Err(self.error("unterminated raw string literal", line, col));
316 };
317 if c == '`' {
318 return Ok(Token::String(value));
319 }
320 value.push(c);
321 }
322 }
323
324 fn read_digits(&mut self, text: &mut String) -> bool {
329 let mut any = false;
330 while let Some(&c) = self.chars.peek() {
331 if c.is_ascii_digit() {
332 text.push(c);
333 self.bump();
334 any = true;
335 } else {
336 break;
337 }
338 }
339 any
340 }
341
342 fn read_number(&mut self, first: char, line: u32, col: u32) -> Result<f64, LexError> {
343 let mut text = String::from(first);
344 self.read_digits(&mut text);
345 if self.chars.peek() == Some(&'.') {
346 text.push('.');
347 self.bump();
348 if !self.read_digits(&mut text) {
349 return Err(self.error("expected digits after decimal point", line, col));
350 }
351 }
352 if matches!(self.chars.peek(), Some('e' | 'E')) {
356 let is_exponent = match self.peek2() {
357 Some(d) if d.is_ascii_digit() => true,
358 Some('+') | Some('-') => {
359 let mut lookahead = self.chars.clone();
362 lookahead.next();
363 lookahead.next();
364 matches!(lookahead.peek(), Some(d) if d.is_ascii_digit())
365 }
366 _ => false,
367 };
368 if is_exponent {
369 text.push(self.bump().expect("peeked 'e'"));
370 if matches!(self.chars.peek(), Some('+') | Some('-')) {
371 text.push(self.bump().expect("peeked sign"));
372 }
373 self.read_digits(&mut text);
374 }
375 }
376 text.parse::<f64>()
377 .map_err(|_| self.error(format!("invalid number '{text}'"), line, col))
378 }
379
380 fn lex_number_or_duration(
382 &mut self,
383 first: char,
384 line: u32,
385 col: u32,
386 ) -> Result<Token, LexError> {
387 let value = self.read_number(first, line, col)?;
388
389 if !matches!(self.chars.peek(), Some(c) if c.is_alphabetic()) {
391 return Ok(Token::Number(value));
392 }
393
394 let (u_line, u_col) = (self.line, self.col);
397 let unit = self.read_unit();
398 if let Some(factor) = bytes_factor(&unit) {
399 if value < 0.0 {
400 return Err(self.error("negative bytes literal", line, col));
401 }
402 let bytes = (value * factor as f64).round() as u64;
403 return Ok(Token::Bytes(bytes));
404 }
405
406 let mut total_secs = 0.0_f64;
409 let mut pending = value;
410 let mut unit = unit;
411 let (mut u_line, mut u_col) = (u_line, u_col);
412 loop {
413 let factor = match unit.as_str() {
414 "ns" => 1e-9,
415 "us" | "µs" => 1e-6,
416 "ms" => 1e-3,
417 "s" => 1.0,
418 "m" => 60.0,
419 "h" => 3600.0,
420 "d" => 86400.0,
421 "w" => 604800.0,
422 "y" => 31536000.0,
423 _ => {
424 return Err(self.error(
425 format!("invalid duration unit '{unit}'"),
426 u_line,
427 u_col,
428 ));
429 }
430 };
431 total_secs += pending * factor;
432
433 match self.chars.peek() {
435 Some(&c) if c.is_ascii_digit() => {
436 let first = self.bump().expect("peeked digit");
437 pending = self.read_number(first, self.line, self.col)?;
438 (u_line, u_col) = (self.line, self.col);
439 unit = self.read_unit();
440 }
441 _ => break,
442 }
443 }
444 if total_secs < 0.0 {
445 return Err(self.error("negative duration", line, col));
446 }
447 Ok(Token::Duration(Duration::from_secs_f64(total_secs)))
448 }
449
450 fn read_unit(&mut self) -> String {
452 let mut unit = String::new();
453 while let Some(&c) = self.chars.peek() {
454 if c.is_alphabetic() || c == 'µ' {
455 unit.push(c);
456 self.bump();
457 } else {
458 break;
459 }
460 }
461 unit
462 }
463
464 fn lex_flag(&mut self, line: u32, col: u32) -> Result<Token, LexError> {
467 let mut name = String::new();
468 while let Some(&c) = self.chars.peek() {
469 if c.is_alphanumeric() || c == '-' || c == '_' {
470 name.push(c);
471 self.bump();
472 } else {
473 break;
474 }
475 }
476 if name.is_empty() {
477 return Err(self.error("expected a flag name after '--'", line, col));
478 }
479 Ok(Token::Flag(name))
480 }
481}
482
483fn bytes_factor(unit: &str) -> Option<u64> {
488 let f = match unit {
489 "B" => 1,
490 "kB" | "KB" => 1_000,
491 "MB" => 1_000_000,
492 "GB" => 1_000_000_000,
493 "TB" => 1_000_000_000_000,
494 "PB" => 1_000_000_000_000_000,
495 "KiB" => 1_024,
496 "MiB" => 1_024 * 1_024,
497 "GiB" => 1_024 * 1_024 * 1_024,
498 "TiB" => 1_024_u64.pow(4),
499 "PiB" => 1_024_u64.pow(5),
500 _ => return None,
501 };
502 Some(f)
503}
504
505#[cfg(test)]
506mod tests {
507 use super::*;
508
509 fn tokens(input: &str) -> Vec<Token> {
510 tokenize(input)
511 .expect("tokenize")
512 .into_iter()
513 .map(|t| t.token)
514 .collect()
515 }
516
517 #[test]
518 fn lexes_stream_selector() {
519 assert_eq!(
520 tokens(r#"{job="api", env!="prod", pod=~"web-.*", ns!~"kube.*"}"#),
521 vec![
522 Token::LBrace,
523 Token::Ident("job".into()),
524 Token::Eq,
525 Token::String("api".into()),
526 Token::Comma,
527 Token::Ident("env".into()),
528 Token::Neq,
529 Token::String("prod".into()),
530 Token::Comma,
531 Token::Ident("pod".into()),
532 Token::Re,
533 Token::String("web-.*".into()),
534 Token::Comma,
535 Token::Ident("ns".into()),
536 Token::Nre,
537 Token::String("kube.*".into()),
538 Token::RBrace,
539 ]
540 );
541 }
542
543 #[test]
544 fn lexes_line_filters_and_pipeline() {
545 assert_eq!(
546 tokens(
547 r#"{app="foo"} |= "error" != "timeout" |~ `exc.*` | json | line_format "{{.msg}}""#
548 ),
549 vec![
550 Token::LBrace,
551 Token::Ident("app".into()),
552 Token::Eq,
553 Token::String("foo".into()),
554 Token::RBrace,
555 Token::PipeExact,
556 Token::String("error".into()),
557 Token::Neq,
558 Token::String("timeout".into()),
559 Token::PipeRegex,
560 Token::String("exc.*".into()),
561 Token::Pipe,
562 Token::Ident("json".into()),
563 Token::Pipe,
564 Token::Ident("line_format".into()),
565 Token::String("{{.msg}}".into()),
566 ]
567 );
568 }
569
570 #[test]
571 fn lexes_metric_query() {
572 assert_eq!(
573 tokens(r#"sum by (level) (rate({app="foo"}[5m]))"#),
574 vec![
575 Token::Ident("sum".into()),
576 Token::By,
577 Token::LParen,
578 Token::Ident("level".into()),
579 Token::RParen,
580 Token::LParen,
581 Token::Ident("rate".into()),
582 Token::LParen,
583 Token::LBrace,
584 Token::Ident("app".into()),
585 Token::Eq,
586 Token::String("foo".into()),
587 Token::RBrace,
588 Token::LBracket,
589 Token::Duration(Duration::from_secs(300)),
590 Token::RBracket,
591 Token::RParen,
592 Token::RParen,
593 ]
594 );
595 }
596
597 #[test]
598 fn lexes_unwrap_and_comparison() {
599 assert_eq!(
600 tokens(
601 r#"{app="foo"} | logfmt | unwrap duration_ms | __error__ = "" and latency > 1.5"#
602 ),
603 vec![
604 Token::LBrace,
605 Token::Ident("app".into()),
606 Token::Eq,
607 Token::String("foo".into()),
608 Token::RBrace,
609 Token::Pipe,
610 Token::Ident("logfmt".into()),
611 Token::Pipe,
612 Token::Unwrap,
613 Token::Ident("duration_ms".into()),
614 Token::Pipe,
615 Token::Ident("__error__".into()),
616 Token::Eq,
617 Token::String("".into()),
618 Token::And,
619 Token::Ident("latency".into()),
620 Token::Gt,
621 Token::Number(1.5),
622 ]
623 );
624 }
625
626 #[test]
627 fn lexes_compound_and_fractional_durations() {
628 assert_eq!(
629 tokens("[1h30m]"),
630 vec![
631 Token::LBracket,
632 Token::Duration(Duration::from_secs(5400)),
633 Token::RBracket,
634 ]
635 );
636 assert_eq!(
637 tokens("[1.5h]"),
638 vec![
639 Token::LBracket,
640 Token::Duration(Duration::from_secs(5400)),
641 Token::RBracket,
642 ]
643 );
644 assert_eq!(
645 tokens("[250ms]"),
646 vec![
647 Token::LBracket,
648 Token::Duration(Duration::from_millis(250)),
649 Token::RBracket,
650 ]
651 );
652 }
653
654 #[test]
655 fn lexes_numbers_including_scientific_notation() {
656 assert_eq!(tokens("42"), vec![Token::Number(42.0)]);
657 assert_eq!(tokens("0.25"), vec![Token::Number(0.25)]);
658 assert_eq!(tokens("1e3"), vec![Token::Number(1000.0)]);
659 assert_eq!(tokens("2.5e-2"), vec![Token::Number(0.025)]);
660 }
661
662 #[test]
663 fn lexes_bytes_literals() {
664 assert_eq!(tokens("20KB"), vec![Token::Bytes(20_000)]);
665 assert_eq!(tokens("5MB"), vec![Token::Bytes(5_000_000)]);
666 assert_eq!(tokens("1GB"), vec![Token::Bytes(1_000_000_000)]);
667 assert_eq!(tokens("1KiB"), vec![Token::Bytes(1_024)]);
668 assert_eq!(tokens("2MiB"), vec![Token::Bytes(2 * 1_024 * 1_024)]);
669 assert_eq!(tokens("512B"), vec![Token::Bytes(512)]);
670 assert_eq!(
672 tokens("20ms"),
673 vec![Token::Duration(Duration::from_millis(20))]
674 );
675 }
676
677 #[test]
678 fn lexes_parser_stage_flags() {
679 assert_eq!(
680 tokens("logfmt --strict --keep-empty"),
681 vec![
682 Token::Ident("logfmt".into()),
683 Token::Flag("strict".into()),
684 Token::Flag("keep-empty".into()),
685 ]
686 );
687 assert_eq!(
689 tokens("5 - 2"),
690 vec![Token::Number(5.0), Token::Sub, Token::Number(2.0),]
691 );
692 }
693
694 #[test]
695 fn lexes_arithmetic_and_comparison_operators() {
696 assert_eq!(
697 tokens("+ - * / % ^ == >= <= > < = != =~ !~ |= |~ |"),
698 vec![
699 Token::Add,
700 Token::Sub,
701 Token::Mul,
702 Token::Div,
703 Token::Mod,
704 Token::Pow,
705 Token::CmpEq,
706 Token::Gte,
707 Token::Lte,
708 Token::Gt,
709 Token::Lt,
710 Token::Eq,
711 Token::Neq,
712 Token::Re,
713 Token::Nre,
714 Token::PipeExact,
715 Token::PipeRegex,
716 Token::Pipe,
717 ]
718 );
719 }
720
721 #[test]
722 fn lexes_string_escapes() {
723 assert_eq!(
724 tokens(r#""a\"b\\c\n\tA""#),
725 vec![Token::String("a\"b\\c\n\tA".into())]
726 );
727 }
728
729 #[test]
730 fn raw_strings_keep_backslashes() {
731 assert_eq!(
732 tokens(r"`\d+(\.\d+)?`"),
733 vec![Token::String(r"\d+(\.\d+)?".into())]
734 );
735 }
736
737 #[test]
738 fn skips_comments_and_whitespace() {
739 assert_eq!(
740 tokens("{a=\"b\"} # trailing comment\n | json"),
741 vec![
742 Token::LBrace,
743 Token::Ident("a".into()),
744 Token::Eq,
745 Token::String("b".into()),
746 Token::RBrace,
747 Token::Pipe,
748 Token::Ident("json".into()),
749 ]
750 );
751 }
752
753 #[test]
754 fn reports_position_of_tokens_and_errors() {
755 let spanned = tokenize("{job=\"a\"}\n |= @").unwrap_err();
756 assert_eq!(spanned.line, 2);
757 assert_eq!(spanned.col, 6);
758 assert!(spanned.to_string().contains("line 2, column 6"));
759
760 let ok = tokenize("{job=\"a\"}\n |= \"x\"").unwrap();
761 let pipe = ok.iter().find(|t| t.token == Token::PipeExact).unwrap();
762 assert_eq!((pipe.line, pipe.col), (2, 3));
763 }
764
765 #[test]
766 fn rejects_malformed_input() {
767 assert!(tokenize(r#"{job="unterminated"#).is_err());
768 assert!(tokenize(r"`unterminated").is_err());
769 assert!(tokenize(r#""bad \q escape""#).is_err());
770 assert!(tokenize("!x").is_err());
771 assert!(tokenize("5x").is_err());
772 assert!(tokenize("1.").is_err());
773 assert!(tokenize("@").is_err());
774 }
775
776 #[test]
777 fn keywords_are_case_sensitive() {
778 assert_eq!(
779 tokens("by BY By"),
780 vec![
781 Token::By,
782 Token::Ident("BY".into()),
783 Token::Ident("By".into()),
784 ]
785 );
786 }
787
788 #[test]
791 fn lexes_dotted_identifier() {
792 assert_eq!(
793 tokens("k8s.pod.name"),
794 vec![Token::Ident("k8s.pod.name".into())]
795 );
796 assert_eq!(
797 tokens("http.response.status_code"),
798 vec![Token::Ident("http.response.status_code".into())]
799 );
800 }
801
802 #[test]
803 fn lexes_dotted_identifier_followed_by_eq() {
804 assert_eq!(
805 tokens(r#"{k8s.pod.name="checkout-7c9f"}"#),
806 vec![
807 Token::LBrace,
808 Token::Ident("k8s.pod.name".into()),
809 Token::Eq,
810 Token::String("checkout-7c9f".into()),
811 Token::RBrace,
812 ]
813 );
814 }
815
816 #[test]
821 fn dotted_identifier_does_not_consume_trailing_dot() {
822 let err = tokenize("foo.").expect_err("a bare trailing '.' is not a token");
823 assert_eq!(err.col, 4, "the dot, not 'foo', should be blamed");
824
825 let err = tokenize("foo..bar").expect_err("'..' is not a token");
826 assert_eq!(err.col, 4);
827 }
828}