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