Skip to main content

logql/
lexer.rs

1//! # LogQL Lexer
2//!
3//! Hand-rolled tokenizer for LogQL. Produces [`SpannedToken`]s with
4//! 1-based line/column positions; every error carries the position it
5//! occurred at.
6//!
7//! Notable rules:
8//!
9//! - A number immediately followed by a letter is a duration literal
10//!   (`5m`, `1h30m`, `1.5h`); an invalid unit is an error rather than
11//!   two adjacent tokens.
12//! - Double-quoted strings process escapes; backtick strings are raw
13//!   (the form used for regex patterns).
14//! - `#` starts a comment running to end of line.
15
16use crate::token::{SpannedToken, Token};
17use std::time::Duration;
18
19/// Lexing error with 1-based source position.
20///
21/// `#[non_exhaustive]` because errors gain context over time and consumers
22/// only ever read them. The AST types are deliberately left constructible —
23/// building a query by hand is a legitimate use of this crate.
24#[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
33/// Tokenize a LogQL query.
34pub fn tokenize(input: &str) -> Result<Vec<SpannedToken>, LexError> {
35    Lexer::new(input).run()
36}
37
38struct Lexer<'a> {
39    chars: std::iter::Peekable<std::str::Chars<'a>>,
40    line: u32,
41    col: u32,
42}
43
44impl<'a> Lexer<'a> {
45    fn new(input: &'a str) -> Self {
46        Self {
47            chars: input.chars().peekable(),
48            line: 1,
49            col: 1,
50        }
51    }
52
53    fn error(&self, message: impl Into<String>, line: u32, col: u32) -> LexError {
54        LexError {
55            message: message.into(),
56            line,
57            col,
58        }
59    }
60
61    fn bump(&mut self) -> Option<char> {
62        let c = self.chars.next()?;
63        if c == '\n' {
64            self.line += 1;
65            self.col = 1;
66        } else {
67            self.col += 1;
68        }
69        Some(c)
70    }
71
72    /// Consume the next char when it equals `expected`.
73    fn eat(&mut self, expected: char) -> bool {
74        if self.chars.peek() == Some(&expected) {
75            self.bump();
76            true
77        } else {
78            false
79        }
80    }
81
82    fn run(mut self) -> Result<Vec<SpannedToken>, LexError> {
83        let mut tokens = Vec::new();
84        loop {
85            // Skip whitespace and comments.
86            match self.chars.peek() {
87                Some(c) if c.is_whitespace() => {
88                    self.bump();
89                    continue;
90                }
91                Some('#') => {
92                    while let Some(&c) = self.chars.peek() {
93                        if c == '\n' {
94                            break;
95                        }
96                        self.bump();
97                    }
98                    continue;
99                }
100                None => break,
101                _ => {}
102            }
103
104            let (line, col) = (self.line, self.col);
105            let c = self.bump().expect("peeked above");
106            let token = match c {
107                '{' => Token::LBrace,
108                '}' => Token::RBrace,
109                '(' => Token::LParen,
110                ')' => Token::RParen,
111                '[' => Token::LBracket,
112                ']' => Token::RBracket,
113                ',' => Token::Comma,
114                '+' => Token::Add,
115                '-' => {
116                    // `--flag` is a parser-stage flag; a single `-` is
117                    // subtraction / unary minus.
118                    if self.eat('-') {
119                        self.lex_flag(line, col)?
120                    } else {
121                        Token::Sub
122                    }
123                }
124                '*' => Token::Mul,
125                '/' => Token::Div,
126                '%' => Token::Mod,
127                '^' => Token::Pow,
128                '|' => {
129                    if self.eat('=') {
130                        Token::PipeExact
131                    } else if self.eat('~') {
132                        Token::PipeRegex
133                    } else {
134                        Token::Pipe
135                    }
136                }
137                '=' => {
138                    if self.eat('=') {
139                        Token::CmpEq
140                    } else if self.eat('~') {
141                        Token::Re
142                    } else {
143                        Token::Eq
144                    }
145                }
146                '!' => {
147                    if self.eat('=') {
148                        Token::Neq
149                    } else if self.eat('~') {
150                        Token::Nre
151                    } else {
152                        return Err(self.error(
153                            "unexpected '!' (expected '!=' or '!~')",
154                            line,
155                            col,
156                        ));
157                    }
158                }
159                '>' => {
160                    if self.eat('=') {
161                        Token::Gte
162                    } else {
163                        Token::Gt
164                    }
165                }
166                '<' => {
167                    if self.eat('=') {
168                        Token::Lte
169                    } else {
170                        Token::Lt
171                    }
172                }
173                '"' => self.lex_string(line, col)?,
174                '`' => self.lex_raw_string(line, col)?,
175                c if c.is_ascii_digit() => self.lex_number_or_duration(c, line, col)?,
176                c if c.is_alphabetic() || c == '_' => {
177                    let mut word = String::from(c);
178                    while let Some(&next) = self.chars.peek() {
179                        if next.is_alphanumeric() || next == '_' {
180                            word.push(next);
181                            self.bump();
182                        } else {
183                            break;
184                        }
185                    }
186                    Token::keyword(&word).unwrap_or(Token::Ident(word))
187                }
188                other => {
189                    return Err(self.error(format!("unexpected character {other:?}"), line, col));
190                }
191            };
192            tokens.push(SpannedToken { token, line, col });
193        }
194        Ok(tokens)
195    }
196
197    /// Double-quoted string; the opening quote is already consumed.
198    fn lex_string(&mut self, line: u32, col: u32) -> Result<Token, LexError> {
199        let mut value = String::new();
200        loop {
201            let (c_line, c_col) = (self.line, self.col);
202            let Some(c) = self.bump() else {
203                return Err(self.error("unterminated string literal", line, col));
204            };
205            match c {
206                '"' => return Ok(Token::String(value)),
207                '\\' => {
208                    let Some(esc) = self.bump() else {
209                        return Err(self.error("unterminated string literal", line, col));
210                    };
211                    match esc {
212                        '"' => value.push('"'),
213                        '\\' => value.push('\\'),
214                        '/' => value.push('/'),
215                        'n' => value.push('\n'),
216                        't' => value.push('\t'),
217                        'r' => value.push('\r'),
218                        'u' => {
219                            let mut code = String::new();
220                            for _ in 0..4 {
221                                match self.bump() {
222                                    Some(h) if h.is_ascii_hexdigit() => code.push(h),
223                                    _ => {
224                                        return Err(self.error(
225                                            "invalid \\u escape (expected 4 hex digits)",
226                                            c_line,
227                                            c_col,
228                                        ));
229                                    }
230                                }
231                            }
232                            let cp = u32::from_str_radix(&code, 16).expect("hex digits");
233                            match char::from_u32(cp) {
234                                Some(ch) => value.push(ch),
235                                None => {
236                                    return Err(self.error(
237                                        format!("invalid unicode code point \\u{code}"),
238                                        c_line,
239                                        c_col,
240                                    ));
241                                }
242                            }
243                        }
244                        other => {
245                            return Err(self.error(
246                                format!("invalid escape sequence '\\{other}'"),
247                                c_line,
248                                c_col,
249                            ));
250                        }
251                    }
252                }
253                other => value.push(other),
254            }
255        }
256    }
257
258    /// Backtick raw string (no escape processing); the opening backtick
259    /// is already consumed.
260    fn lex_raw_string(&mut self, line: u32, col: u32) -> Result<Token, LexError> {
261        let mut value = String::new();
262        loop {
263            let Some(c) = self.bump() else {
264                return Err(self.error("unterminated raw string literal", line, col));
265            };
266            if c == '`' {
267                return Ok(Token::String(value));
268            }
269            value.push(c);
270        }
271    }
272
273    /// Read the digits (with optional fraction/exponent) of one number
274    /// starting with `first`.
275    /// Push consecutive ASCII digits from the input onto `text`. Returns
276    /// whether any digit was consumed.
277    fn read_digits(&mut self, text: &mut String) -> bool {
278        let mut any = false;
279        while let Some(&c) = self.chars.peek() {
280            if c.is_ascii_digit() {
281                text.push(c);
282                self.bump();
283                any = true;
284            } else {
285                break;
286            }
287        }
288        any
289    }
290
291    fn read_number(&mut self, first: char, line: u32, col: u32) -> Result<f64, LexError> {
292        let mut text = String::from(first);
293        self.read_digits(&mut text);
294        if self.chars.peek() == Some(&'.') {
295            text.push('.');
296            self.bump();
297            if !self.read_digits(&mut text) {
298                return Err(self.error("expected digits after decimal point", line, col));
299            }
300        }
301        // Exponent: only when followed by digits (or sign + digits), so
302        // `5e` in a duration position is not misread. Peek-ahead here is
303        // single-char, so clone the iterator to look past the 'e'.
304        if matches!(self.chars.peek(), Some('e' | 'E')) {
305            let mut lookahead = self.chars.clone();
306            lookahead.next();
307            let next = lookahead.peek().copied();
308            let is_exponent = match next {
309                Some(d) if d.is_ascii_digit() => true,
310                Some('+') | Some('-') => {
311                    lookahead.next();
312                    matches!(lookahead.peek(), Some(d) if d.is_ascii_digit())
313                }
314                _ => false,
315            };
316            if is_exponent {
317                text.push(self.bump().expect("peeked 'e'"));
318                if matches!(self.chars.peek(), Some('+') | Some('-')) {
319                    text.push(self.bump().expect("peeked sign"));
320                }
321                self.read_digits(&mut text);
322            }
323        }
324        text.parse::<f64>()
325            .map_err(|_| self.error(format!("invalid number '{text}'"), line, col))
326    }
327
328    /// A number, or a duration when a unit letter follows the number.
329    fn lex_number_or_duration(
330        &mut self,
331        first: char,
332        line: u32,
333        col: u32,
334    ) -> Result<Token, LexError> {
335        let value = self.read_number(first, line, col)?;
336
337        // 'µ' (as in µs) is alphabetic, so this also covers it.
338        if !matches!(self.chars.peek(), Some(c) if c.is_alphabetic()) {
339            return Ok(Token::Number(value));
340        }
341
342        // Read the first unit. A bytes unit (`KB`, `MiB`, ...) yields a
343        // bytes literal; otherwise fall through to duration parsing.
344        let (u_line, u_col) = (self.line, self.col);
345        let unit = self.read_unit();
346        if let Some(factor) = bytes_factor(&unit) {
347            if value < 0.0 {
348                return Err(self.error("negative bytes literal", line, col));
349            }
350            let bytes = (value * factor as f64).round() as u64;
351            return Ok(Token::Bytes(bytes));
352        }
353
354        // Duration: one or more (number, unit) pairs, e.g. `1h30m`. The
355        // first unit was already read above.
356        let mut total_secs = 0.0_f64;
357        let mut pending = value;
358        let mut unit = unit;
359        let (mut u_line, mut u_col) = (u_line, u_col);
360        loop {
361            let factor = match unit.as_str() {
362                "ns" => 1e-9,
363                "us" | "µs" => 1e-6,
364                "ms" => 1e-3,
365                "s" => 1.0,
366                "m" => 60.0,
367                "h" => 3600.0,
368                "d" => 86400.0,
369                "w" => 604800.0,
370                "y" => 31536000.0,
371                _ => {
372                    return Err(self.error(
373                        format!("invalid duration unit '{unit}'"),
374                        u_line,
375                        u_col,
376                    ));
377                }
378            };
379            total_secs += pending * factor;
380
381            // Another number directly attached continues the duration.
382            match self.chars.peek() {
383                Some(&c) if c.is_ascii_digit() => {
384                    let first = self.bump().expect("peeked digit");
385                    pending = self.read_number(first, self.line, self.col)?;
386                    (u_line, u_col) = (self.line, self.col);
387                    unit = self.read_unit();
388                }
389                _ => break,
390            }
391        }
392        if total_secs < 0.0 {
393            return Err(self.error("negative duration", line, col));
394        }
395        Ok(Token::Duration(Duration::from_secs_f64(total_secs)))
396    }
397
398    /// Read a run of unit letters (`ms`, `KiB`, `µs`, ...).
399    fn read_unit(&mut self) -> String {
400        let mut unit = String::new();
401        while let Some(&c) = self.chars.peek() {
402            if c.is_alphabetic() || c == 'µ' {
403                unit.push(c);
404                self.bump();
405            } else {
406                break;
407            }
408        }
409        unit
410    }
411
412    /// A parser-stage flag: `--<name>`. The two dashes are already
413    /// consumed.
414    fn lex_flag(&mut self, line: u32, col: u32) -> Result<Token, LexError> {
415        let mut name = String::new();
416        while let Some(&c) = self.chars.peek() {
417            if c.is_alphanumeric() || c == '-' || c == '_' {
418                name.push(c);
419                self.bump();
420            } else {
421                break;
422            }
423        }
424        if name.is_empty() {
425            return Err(self.error("expected a flag name after '--'", line, col));
426        }
427        Ok(Token::Flag(name))
428    }
429}
430
431/// Bytes-per-unit factor for a byte-size unit, or `None` if `unit` is
432/// not a bytes unit. Decimal units are powers of 1000; `*iB` units and
433/// bare `KB`/`MB`/... follow Loki's `humanize` convention of powers of
434/// 1024 for the `i` forms.
435fn bytes_factor(unit: &str) -> Option<u64> {
436    let f = match unit {
437        "B" => 1,
438        "kB" | "KB" => 1_000,
439        "MB" => 1_000_000,
440        "GB" => 1_000_000_000,
441        "TB" => 1_000_000_000_000,
442        "PB" => 1_000_000_000_000_000,
443        "KiB" => 1_024,
444        "MiB" => 1_024 * 1_024,
445        "GiB" => 1_024 * 1_024 * 1_024,
446        "TiB" => 1_024_u64.pow(4),
447        "PiB" => 1_024_u64.pow(5),
448        _ => return None,
449    };
450    Some(f)
451}
452
453#[cfg(test)]
454mod tests {
455    use super::*;
456
457    fn tokens(input: &str) -> Vec<Token> {
458        tokenize(input)
459            .expect("tokenize")
460            .into_iter()
461            .map(|t| t.token)
462            .collect()
463    }
464
465    #[test]
466    fn lexes_stream_selector() {
467        assert_eq!(
468            tokens(r#"{job="api", env!="prod", pod=~"web-.*", ns!~"kube.*"}"#),
469            vec![
470                Token::LBrace,
471                Token::Ident("job".into()),
472                Token::Eq,
473                Token::String("api".into()),
474                Token::Comma,
475                Token::Ident("env".into()),
476                Token::Neq,
477                Token::String("prod".into()),
478                Token::Comma,
479                Token::Ident("pod".into()),
480                Token::Re,
481                Token::String("web-.*".into()),
482                Token::Comma,
483                Token::Ident("ns".into()),
484                Token::Nre,
485                Token::String("kube.*".into()),
486                Token::RBrace,
487            ]
488        );
489    }
490
491    #[test]
492    fn lexes_line_filters_and_pipeline() {
493        assert_eq!(
494            tokens(
495                r#"{app="foo"} |= "error" != "timeout" |~ `exc.*` | json | line_format "{{.msg}}""#
496            ),
497            vec![
498                Token::LBrace,
499                Token::Ident("app".into()),
500                Token::Eq,
501                Token::String("foo".into()),
502                Token::RBrace,
503                Token::PipeExact,
504                Token::String("error".into()),
505                Token::Neq,
506                Token::String("timeout".into()),
507                Token::PipeRegex,
508                Token::String("exc.*".into()),
509                Token::Pipe,
510                Token::Ident("json".into()),
511                Token::Pipe,
512                Token::Ident("line_format".into()),
513                Token::String("{{.msg}}".into()),
514            ]
515        );
516    }
517
518    #[test]
519    fn lexes_metric_query() {
520        assert_eq!(
521            tokens(r#"sum by (level) (rate({app="foo"}[5m]))"#),
522            vec![
523                Token::Ident("sum".into()),
524                Token::By,
525                Token::LParen,
526                Token::Ident("level".into()),
527                Token::RParen,
528                Token::LParen,
529                Token::Ident("rate".into()),
530                Token::LParen,
531                Token::LBrace,
532                Token::Ident("app".into()),
533                Token::Eq,
534                Token::String("foo".into()),
535                Token::RBrace,
536                Token::LBracket,
537                Token::Duration(Duration::from_secs(300)),
538                Token::RBracket,
539                Token::RParen,
540                Token::RParen,
541            ]
542        );
543    }
544
545    #[test]
546    fn lexes_unwrap_and_comparison() {
547        assert_eq!(
548            tokens(
549                r#"{app="foo"} | logfmt | unwrap duration_ms | __error__ = "" and latency > 1.5"#
550            ),
551            vec![
552                Token::LBrace,
553                Token::Ident("app".into()),
554                Token::Eq,
555                Token::String("foo".into()),
556                Token::RBrace,
557                Token::Pipe,
558                Token::Ident("logfmt".into()),
559                Token::Pipe,
560                Token::Unwrap,
561                Token::Ident("duration_ms".into()),
562                Token::Pipe,
563                Token::Ident("__error__".into()),
564                Token::Eq,
565                Token::String("".into()),
566                Token::And,
567                Token::Ident("latency".into()),
568                Token::Gt,
569                Token::Number(1.5),
570            ]
571        );
572    }
573
574    #[test]
575    fn lexes_compound_and_fractional_durations() {
576        assert_eq!(
577            tokens("[1h30m]"),
578            vec![
579                Token::LBracket,
580                Token::Duration(Duration::from_secs(5400)),
581                Token::RBracket,
582            ]
583        );
584        assert_eq!(
585            tokens("[1.5h]"),
586            vec![
587                Token::LBracket,
588                Token::Duration(Duration::from_secs(5400)),
589                Token::RBracket,
590            ]
591        );
592        assert_eq!(
593            tokens("[250ms]"),
594            vec![
595                Token::LBracket,
596                Token::Duration(Duration::from_millis(250)),
597                Token::RBracket,
598            ]
599        );
600    }
601
602    #[test]
603    fn lexes_numbers_including_scientific_notation() {
604        assert_eq!(tokens("42"), vec![Token::Number(42.0)]);
605        assert_eq!(tokens("0.25"), vec![Token::Number(0.25)]);
606        assert_eq!(tokens("1e3"), vec![Token::Number(1000.0)]);
607        assert_eq!(tokens("2.5e-2"), vec![Token::Number(0.025)]);
608    }
609
610    #[test]
611    fn lexes_bytes_literals() {
612        assert_eq!(tokens("20KB"), vec![Token::Bytes(20_000)]);
613        assert_eq!(tokens("5MB"), vec![Token::Bytes(5_000_000)]);
614        assert_eq!(tokens("1GB"), vec![Token::Bytes(1_000_000_000)]);
615        assert_eq!(tokens("1KiB"), vec![Token::Bytes(1_024)]);
616        assert_eq!(tokens("2MiB"), vec![Token::Bytes(2 * 1_024 * 1_024)]);
617        assert_eq!(tokens("512B"), vec![Token::Bytes(512)]);
618        // Bytes and durations are distinguished by unit.
619        assert_eq!(
620            tokens("20ms"),
621            vec![Token::Duration(Duration::from_millis(20))]
622        );
623    }
624
625    #[test]
626    fn lexes_parser_stage_flags() {
627        assert_eq!(
628            tokens("logfmt --strict --keep-empty"),
629            vec![
630                Token::Ident("logfmt".into()),
631                Token::Flag("strict".into()),
632                Token::Flag("keep-empty".into()),
633            ]
634        );
635        // A lone '-' is still subtraction.
636        assert_eq!(
637            tokens("5 - 2"),
638            vec![Token::Number(5.0), Token::Sub, Token::Number(2.0),]
639        );
640    }
641
642    #[test]
643    fn lexes_arithmetic_and_comparison_operators() {
644        assert_eq!(
645            tokens("+ - * / % ^ == >= <= > < = != =~ !~ |= |~ |"),
646            vec![
647                Token::Add,
648                Token::Sub,
649                Token::Mul,
650                Token::Div,
651                Token::Mod,
652                Token::Pow,
653                Token::CmpEq,
654                Token::Gte,
655                Token::Lte,
656                Token::Gt,
657                Token::Lt,
658                Token::Eq,
659                Token::Neq,
660                Token::Re,
661                Token::Nre,
662                Token::PipeExact,
663                Token::PipeRegex,
664                Token::Pipe,
665            ]
666        );
667    }
668
669    #[test]
670    fn lexes_string_escapes() {
671        assert_eq!(
672            tokens(r#""a\"b\\c\n\tA""#),
673            vec![Token::String("a\"b\\c\n\tA".into())]
674        );
675    }
676
677    #[test]
678    fn raw_strings_keep_backslashes() {
679        assert_eq!(
680            tokens(r"`\d+(\.\d+)?`"),
681            vec![Token::String(r"\d+(\.\d+)?".into())]
682        );
683    }
684
685    #[test]
686    fn skips_comments_and_whitespace() {
687        assert_eq!(
688            tokens("{a=\"b\"} # trailing comment\n | json"),
689            vec![
690                Token::LBrace,
691                Token::Ident("a".into()),
692                Token::Eq,
693                Token::String("b".into()),
694                Token::RBrace,
695                Token::Pipe,
696                Token::Ident("json".into()),
697            ]
698        );
699    }
700
701    #[test]
702    fn reports_position_of_tokens_and_errors() {
703        let spanned = tokenize("{job=\"a\"}\n  |= @").unwrap_err();
704        assert_eq!(spanned.line, 2);
705        assert_eq!(spanned.col, 6);
706        assert!(spanned.to_string().contains("line 2, column 6"));
707
708        let ok = tokenize("{job=\"a\"}\n  |= \"x\"").unwrap();
709        let pipe = ok.iter().find(|t| t.token == Token::PipeExact).unwrap();
710        assert_eq!((pipe.line, pipe.col), (2, 3));
711    }
712
713    #[test]
714    fn rejects_malformed_input() {
715        assert!(tokenize(r#"{job="unterminated"#).is_err());
716        assert!(tokenize(r"`unterminated").is_err());
717        assert!(tokenize(r#""bad \q escape""#).is_err());
718        assert!(tokenize("!x").is_err());
719        assert!(tokenize("5x").is_err());
720        assert!(tokenize("1.").is_err());
721        assert!(tokenize("@").is_err());
722    }
723
724    #[test]
725    fn keywords_are_case_sensitive() {
726        assert_eq!(
727            tokens("by BY By"),
728            vec![
729                Token::By,
730                Token::Ident("BY".into()),
731                Token::Ident("By".into()),
732            ]
733        );
734    }
735}