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.
34///
35/// # Examples
36///
37/// ```
38/// use logql::Token;
39///
40/// let tokens = logql::tokenize(r#"{service_name="api"}"#)?;
41/// assert_eq!(tokens[0].token, Token::LBrace);
42/// assert_eq!(tokens[1].token, Token::Ident("service_name".into()));
43/// # Ok::<(), logql::LexError>(())
44/// ```
45///
46/// Durations are single tokens, not a number beside an identifier — which is
47/// why an invalid unit is an error here rather than two valid tokens:
48///
49/// ```
50/// use logql::Token;
51/// use std::time::Duration;
52///
53/// let tokens = logql::tokenize("5m")?;
54/// assert_eq!(tokens[0].token, Token::Duration(Duration::from_secs(300)));
55/// assert!(logql::tokenize("5z").is_err());
56/// # Ok::<(), logql::LexError>(())
57/// ```
58pub 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    /// Consume the next char when it equals `expected`.
97    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            // Skip whitespace and comments.
110            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                    // `--flag` is a parser-stage flag; a single `-` is
141                    // subtraction / unary minus.
142                    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    /// Double-quoted string; the opening quote is already consumed.
222    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    /// Backtick raw string (no escape processing); the opening backtick
283    /// is already consumed.
284    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    /// Read the digits (with optional fraction/exponent) of one number
298    /// starting with `first`.
299    /// Push consecutive ASCII digits from the input onto `text`. Returns
300    /// whether any digit was consumed.
301    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        // Exponent: only when followed by digits (or sign + digits), so
326        // `5e` in a duration position is not misread. Peek-ahead here is
327        // single-char, so clone the iterator to look past the 'e'.
328        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    /// A number, or a duration when a unit letter follows the number.
353    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        // 'µ' (as in µs) is alphabetic, so this also covers it.
362        if !matches!(self.chars.peek(), Some(c) if c.is_alphabetic()) {
363            return Ok(Token::Number(value));
364        }
365
366        // Read the first unit. A bytes unit (`KB`, `MiB`, ...) yields a
367        // bytes literal; otherwise fall through to duration parsing.
368        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        // Duration: one or more (number, unit) pairs, e.g. `1h30m`. The
379        // first unit was already read above.
380        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            // Another number directly attached continues the duration.
406            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    /// Read a run of unit letters (`ms`, `KiB`, `µs`, ...).
423    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    /// A parser-stage flag: `--<name>`. The two dashes are already
437    /// consumed.
438    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
455/// Bytes-per-unit factor for a byte-size unit, or `None` if `unit` is
456/// not a bytes unit. Decimal units are powers of 1000; `*iB` units and
457/// bare `KB`/`MB`/... follow Loki's `humanize` convention of powers of
458/// 1024 for the `i` forms.
459fn 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        // Bytes and durations are distinguished by unit.
643        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        // A lone '-' is still subtraction.
660        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}