ripbi_core/m/
lexer.rs

1//! M tokenizer, following the lexical grammar of the official Power Query
2//! specification (<https://learn.microsoft.com/en-us/powerquery-m/m-spec-lexical-structure>)
3//! with microsoft/powerquery-parser (MIT) as the battle-tested reference for the
4//! fiddly corners. Reduced to what reference extraction needs — no line-mode
5//! bookkeeping, no error positions, no formatter.
6//!
7//! Like the DAX tokenizer, the scanner is tolerance-first: unterminated strings,
8//! quoted identifiers, and comments never fail — they simply run to the end of
9//! the input. Lexing is a total function; there is nothing to report as an error.
10//!
11//! Two spec details shape the token set:
12//!
13//! - `#"…"` is **only** a quoted identifier. M has no interpolated strings;
14//!   the `#"name"` form follows exactly the same character rules as a text
15//!   literal (doubled-quote escapes, `#(lf)`-style escapes stay inside the
16//!   token), and `#!"…"` is the verbatim literal.
17//! - Regular identifiers absorb internal dots lexically — `Table.SelectRows`
18//!   is one token, and so is a dotted parameter use such as `Server.Name`.
19
20/// What a [`Token`] is.
21#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
22pub enum TokenKind {
23    /// End of input. Always the last token; `text` is empty.
24    Eof,
25    /// `Source`, `let`, `Table.SelectRows`, `#table`, `Server.Name` — keywords,
26    /// dotted names, and the `#`-prefixed keyword family are all identifiers
27    /// here; whether a word means a keyword or a name is resolution's business,
28    /// not the lexer's.
29    Identifier,
30    /// `#"1998 Sales"` — a quoted identifier, `""` as the escape.
31    QuotedIdentifier,
32    /// `#!"not parsed"` — a verbatim literal (evaluates to an error value).
33    Verbatim,
34    /// `"text"` — a text literal, `""` as the escape.
35    String,
36    /// `1`, `1.5`, `1.5E-10`, `0xff`.
37    Number,
38    /// `// …` or `/* … */` — never produces a reference.
39    Comment,
40    /// `= < > <= >= <> + - * / & @ ! ? ?? => .. ...`
41    Operator,
42    /// `.` on its own — a dot that did not absorb into an identifier.
43    Dot,
44    /// `(`
45    OpenParen,
46    /// `)`
47    CloseParen,
48    /// `[` — opens a field access (`[Name]`) or a record literal (`[K = V]`);
49    /// the extractor tells the two apart.
50    OpenBracket,
51    /// `]`
52    CloseBracket,
53    /// `{`
54    OpenBrace,
55    /// `}`
56    CloseBrace,
57    /// `,`
58    Comma,
59    /// `;`
60    Semicolon,
61    /// Any other character. Never fails the scan.
62    Unknown,
63}
64
65/// One lexical token: [`kind`](Token::kind), the source [`slice`](Token::text)
66/// it covers, and the byte offset it starts at.
67///
68/// The text is borrowed from the expression — lexing allocates nothing but the
69/// returned `Vec`.
70#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
71pub struct Token<'a> {
72    /// What the token is.
73    pub kind: TokenKind,
74    /// The exact source text, delimiters and escapes included.
75    pub text: &'a str,
76    /// Byte offset of the token in the expression.
77    pub start: usize,
78}
79
80impl Token<'_> {
81    /// The byte offset one past the token's last byte.
82    #[must_use]
83    pub fn end(&self) -> usize {
84        self.start + self.text.len()
85    }
86}
87
88/// Multi-character operators, longest first.
89const MULTI_CHAR_OPERATORS: [&str; 7] = ["...", "..", "??", "<>", "<=", ">=", "=>"];
90
91/// Converts M source into tokens, ending with one [`TokenKind::Eof`].
92///
93/// Whitespace produces no tokens, so the token after any given token is exactly
94/// its next significant neighbour — the property the reference extractor's
95/// adjacency rules rely on.
96///
97/// ```
98/// use ripbi_core::m::{TokenKind, tokenize};
99///
100/// let tokens = tokenize("Table.SelectRows(Source, each [Amount] > 0)");
101/// let kinds: Vec<TokenKind> = tokens.iter().map(|t| t.kind).collect();
102/// assert_eq!(
103///     kinds,
104///     [
105///         TokenKind::Identifier,
106///         TokenKind::OpenParen,
107///         TokenKind::Identifier,
108///         TokenKind::Comma,
109///         TokenKind::Identifier,
110///         TokenKind::OpenBracket,
111///         TokenKind::Identifier,
112///         TokenKind::CloseBracket,
113///         TokenKind::Operator,
114///         TokenKind::Number,
115///         TokenKind::CloseParen,
116///         TokenKind::Eof,
117///     ]
118/// );
119/// ```
120#[must_use]
121pub fn tokenize(source: &str) -> Vec<Token<'_>> {
122    let bytes = source.as_bytes();
123    let mut tokens = Vec::new();
124    let mut index = 0usize;
125
126    while index < source.len() {
127        let start = index;
128        // `index` is always on a char boundary: every advance below moves past a
129        // whole character (or an ASCII-only run).
130        let ch = source[index..].chars().next().expect("index < len");
131        let ch_len = ch.len_utf8();
132
133        if ch.is_whitespace() {
134            index += ch_len;
135            continue;
136        }
137
138        let rest = &source[index..];
139
140        // Line and block comments. Unterminated block comments run to the end.
141        if rest.starts_with("//") {
142            let end = rest.find(['\r', '\n']).map_or(source.len(), |i| index + i);
143            tokens.push(Token {
144                kind: TokenKind::Comment,
145                text: &source[start..end],
146                start,
147            });
148            index = end;
149            continue;
150        }
151        if let Some(after_open) = rest.strip_prefix("/*") {
152            let end = after_open
153                .find("*/")
154                .map_or(source.len(), |i| index + 2 + i + 2);
155            tokens.push(Token {
156                kind: TokenKind::Comment,
157                text: &source[start..end],
158                start,
159            });
160            index = end;
161            continue;
162        }
163
164        let kind;
165
166        if ch == '"' {
167            index = scan_delimited(source, index);
168            kind = TokenKind::String;
169        } else if rest.starts_with("#!\"") {
170            index = scan_delimited(source, index + 2);
171            kind = TokenKind::Verbatim;
172        } else if rest.starts_with("#\"") {
173            index = scan_delimited(source, index + 1);
174            kind = TokenKind::QuotedIdentifier;
175        } else if ch == '#'
176            && source[index + 1..]
177                .chars()
178                .next()
179                .is_some_and(is_identifier_start)
180        {
181            // The `#`-prefixed keyword family: #table, #date, #shared, …
182            index = scan_identifier(source, index + 1);
183            kind = TokenKind::Identifier;
184        } else if ch.is_ascii_digit()
185            || (ch == '.' && bytes.get(index + 1).is_some_and(|b| b.is_ascii_digit()))
186        {
187            index = scan_number(source, index);
188            kind = TokenKind::Number;
189        } else if is_identifier_start(ch) {
190            index = scan_identifier(source, index);
191            kind = TokenKind::Identifier;
192        } else if let Some(op) = MULTI_CHAR_OPERATORS
193            .iter()
194            .find(|op| rest.starts_with(**op))
195        {
196            index += op.len();
197            kind = TokenKind::Operator;
198        } else {
199            index += ch_len;
200            kind = match ch {
201                '(' => TokenKind::OpenParen,
202                ')' => TokenKind::CloseParen,
203                '[' => TokenKind::OpenBracket,
204                ']' => TokenKind::CloseBracket,
205                '{' => TokenKind::OpenBrace,
206                '}' => TokenKind::CloseBrace,
207                ',' => TokenKind::Comma,
208                ';' => TokenKind::Semicolon,
209                '.' => TokenKind::Dot,
210                '=' | '<' | '>' | '+' | '-' | '*' | '/' | '&' | '@' | '!' | '?' => {
211                    TokenKind::Operator
212                }
213                _ => TokenKind::Unknown,
214            };
215        }
216
217        tokens.push(Token {
218            kind,
219            text: &source[start..index],
220            start,
221        });
222    }
223
224    tokens.push(Token {
225        kind: TokenKind::Eof,
226        text: "",
227        start: source.len(),
228    });
229    tokens
230}
231
232/// Scans a quoted run (`"…"`, `#"…"`, `#!"…` up to its closing quote), treating
233/// a doubled quote as an escaped quote. Unterminated input consumes the rest of
234/// the source. `index` points at the opening quote.
235fn scan_delimited(source: &str, index: usize) -> usize {
236    let bytes = source.as_bytes();
237    let mut index = index + 1; // opening delimiter
238    while index < bytes.len() {
239        if bytes[index] != b'"' {
240            index += 1;
241            continue;
242        }
243        if bytes.get(index + 1) == Some(&b'"') {
244            index += 2;
245            continue;
246        }
247        return index + 1;
248    }
249    index
250}
251
252fn scan_number(source: &str, mut index: usize) -> usize {
253    let bytes = source.as_bytes();
254
255    // Hexadecimal: 0xff / 0XFF. A `0x` without hex digits after it falls back
256    // to the decimal path below and lexes as `0`.
257    if bytes[index] == b'0'
258        && bytes
259            .get(index + 1)
260            .is_some_and(|b| b.eq_ignore_ascii_case(&b'x'))
261        && bytes.get(index + 2).is_some_and(|b| b.is_ascii_hexdigit())
262    {
263        index += 2;
264        while index < bytes.len() && bytes[index].is_ascii_hexdigit() {
265            index += 1;
266        }
267        return index;
268    }
269
270    while index < bytes.len() && (bytes[index].is_ascii_digit() || bytes[index] == b'.') {
271        index += 1;
272    }
273
274    // Exponent: 1.5E+10, 2e-3. Only consume it when digits actually follow, so
275    // that a field access such as `1[E]` cannot be mistaken for an exponent.
276    if bytes
277        .get(index)
278        .is_some_and(|b| b.eq_ignore_ascii_case(&b'e'))
279    {
280        let mut lookahead = index + 1;
281        if matches!(bytes.get(lookahead), Some(&b'+') | Some(&b'-')) {
282            lookahead += 1;
283        }
284        if bytes.get(lookahead).is_some_and(|b| b.is_ascii_digit()) {
285            index = lookahead;
286            while index < bytes.len() && bytes[index].is_ascii_digit() {
287                index += 1;
288            }
289        }
290    }
291    index
292}
293
294/// Scans an identifier, absorbing the internal dots of names such as
295/// `Table.SelectRows` or `Server.Name`, per the spec's
296/// `available-identifier dot-character regular-identifier` production. A dot
297/// that is not followed by an identifier character is left as its own token.
298fn scan_identifier(source: &str, mut index: usize) -> usize {
299    index = advance_while(source, index, is_identifier_part);
300    while bytes_at(source, index) == Some(b'.')
301        && source[index + 1..]
302            .chars()
303            .next()
304            .is_some_and(is_identifier_part)
305    {
306        index = advance_while(source, index + 1, is_identifier_part);
307    }
308    index
309}
310
311/// The byte at `index`, when it is inside the source. Multi-byte characters are
312/// never equal to an ASCII byte, so this is safe to branch on.
313fn bytes_at(source: &str, index: usize) -> Option<u8> {
314    source.as_bytes().get(index).copied()
315}
316
317/// Advances `index` past every character satisfying `predicate`.
318fn advance_while(source: &str, mut index: usize, predicate: impl Fn(char) -> bool) -> usize {
319    while let Some(ch) = source[index..].chars().next() {
320        if !predicate(ch) {
321            break;
322        }
323        index += ch.len_utf8();
324    }
325    index
326}
327
328fn is_identifier_start(ch: char) -> bool {
329    ch.is_alphabetic() || ch == '_'
330}
331
332fn is_identifier_part(ch: char) -> bool {
333    ch.is_alphanumeric() || ch == '_'
334}
335
336#[cfg(test)]
337mod tests {
338    use super::*;
339    use rstest::rstest;
340
341    /// The kinds of every token, including the trailing `Eof` — the shape-level
342    /// assertions below all compare against this compact form.
343    fn kinds(source: &str) -> Vec<TokenKind> {
344        tokenize(source).into_iter().map(|t| t.kind).collect()
345    }
346
347    /// The text of every token except the trailing `Eof`.
348    fn texts(source: &str) -> Vec<&str> {
349        let all = tokenize(source);
350        let end = all.len() - 1; // drop Eof, whose text is empty
351        all[..end].iter().map(|t| t.text).collect()
352    }
353
354    #[test]
355    fn tokenizes_a_typical_partition_step() {
356        assert_eq!(
357            texts(
358                r#"#"Changed Type" = Table.TransformColumnTypes(Source, {{"Amount", type text}})"#
359            ),
360            [
361                "#\"Changed Type\"",
362                "=",
363                "Table.TransformColumnTypes",
364                "(",
365                "Source",
366                ",",
367                "{",
368                "{",
369                "\"Amount\"",
370                ",",
371                "type",
372                "text",
373                "}",
374                "}",
375                ")",
376            ]
377        );
378    }
379
380    #[test]
381    fn empty_input_produces_only_eof() {
382        assert_eq!(kinds(""), [TokenKind::Eof]);
383        assert_eq!(kinds("   \r\n\t"), [TokenKind::Eof]);
384    }
385
386    #[test]
387    fn eof_marks_the_end_of_input() {
388        let tokens = tokenize("[X]");
389        let eof = tokens.last().expect("eof token");
390        assert_eq!(eof.kind, TokenKind::Eof);
391        assert_eq!(eof.start, 3);
392        assert_eq!(eof.text, "");
393    }
394
395    #[test]
396    fn tokens_carry_their_exact_source_slices_and_offsets() {
397        let source = "Table.Column(#\"My Table\", \"Col\")";
398        let tokens = tokenize(source);
399        for token in &tokens {
400            assert_eq!(&source[token.start..token.end()], token.text);
401        }
402        assert_eq!(
403            texts(source),
404            ["Table.Column", "(", "#\"My Table\"", ",", "\"Col\"", ")"]
405        );
406    }
407
408    #[test]
409    fn quoted_identifiers_keep_doubled_quotes_verbatim() {
410        // The lexer preserves escapes; logical unescaping happens at bind time.
411        assert_eq!(texts("#\"It\"\"s\""), ["#\"It\"\"s\""]);
412        assert_eq!(
413            texts("#\"Change \"\"Type\"\"\""),
414            ["#\"Change \"\"Type\"\"\""]
415        );
416    }
417
418    #[test]
419    fn strings_keep_doubled_quotes_verbatim() {
420        assert_eq!(texts(r#""say ""hi"" ok""#), [r#""say ""hi"" ok""#]);
421    }
422
423    #[test]
424    fn escape_sequences_stay_inside_the_string() {
425        // #(cr,lf) contains no quote, so it is just string content.
426        assert_eq!(texts("\"a#(cr,lf)b\""), ["\"a#(cr,lf)b\""]);
427        // #(#)( escapes the escape start itself — still string content.
428        assert_eq!(texts("\"#(#)(\""), ["\"#(#)(\""]);
429    }
430
431    #[test]
432    fn the_verbatim_literal_is_its_own_kind() {
433        assert_eq!(
434            kinds("#!\"let x = 1\""),
435            [TokenKind::Verbatim, TokenKind::Eof]
436        );
437        assert_eq!(texts("#!\"let x = 1\""), ["#!\"let x = 1\""]);
438    }
439
440    #[test]
441    fn the_hash_quote_pair_is_never_an_interpolated_string() {
442        // M has no interpolated strings: #"…" is always a quoted identifier,
443        // braces and all — matching the spec and powerquery-parser.
444        assert_eq!(
445            texts("#\"Amount {x}\""),
446            ["#\"Amount {x}\""],
447            "the brace stays inside the quoted identifier"
448        );
449    }
450
451    #[test]
452    fn identifiers_absorb_internal_dots() {
453        assert_eq!(texts("Table.SelectRows"), ["Table.SelectRows"]);
454        assert_eq!(texts("a.b.c(x)"), ["a.b.c", "(", "x", ")"]);
455        // A dotted parameter use is one identifier, just like a built-in.
456        assert_eq!(
457            texts("Sql.Database(Server.Name)"),
458            ["Sql.Database", "(", "Server.Name", ")"]
459        );
460    }
461
462    #[test]
463    fn a_trailing_dot_stays_its_own_token() {
464        assert_eq!(
465            kinds("A.B."),
466            [TokenKind::Identifier, TokenKind::Dot, TokenKind::Eof]
467        );
468        assert_eq!(
469            kinds("A . B"),
470            [
471                TokenKind::Identifier,
472                TokenKind::Dot,
473                TokenKind::Identifier,
474                TokenKind::Eof,
475            ]
476        );
477    }
478
479    #[test]
480    fn hash_prefixed_keywords_lex_as_identifiers() {
481        assert_eq!(
482            texts("#table({\"A\"}, {{}})"),
483            [
484                "#table", "(", "{", "\"A\"", "}", ",", "{", "{", "}", "}", ")"
485            ]
486        );
487        assert_eq!(
488            texts("#date(2024, 1, 1)"),
489            ["#date", "(", "2024", ",", "1", ",", "1", ")"]
490        );
491        // #shared[Query] is how M reaches every query in the section.
492        assert_eq!(
493            kinds("#shared[#\"My Query\"]"),
494            [
495                TokenKind::Identifier,
496                TokenKind::OpenBracket,
497                TokenKind::QuotedIdentifier,
498                TokenKind::CloseBracket,
499                TokenKind::Eof,
500            ]
501        );
502    }
503
504    #[test]
505    fn a_bare_hash_is_unknown() {
506        assert_eq!(
507            kinds("# 1"),
508            [TokenKind::Unknown, TokenKind::Number, TokenKind::Eof]
509        );
510    }
511
512    #[rstest]
513    #[case("0xff", &["0xff"])]
514    #[case("0X1F", &["0X1F"])]
515    #[case("1.5", &["1.5"])]
516    #[case("1.5E+10", &["1.5E+10"])]
517    #[case("2e-3", &["2e-3"])]
518    #[case("1.5E", &["1.5", "E"])]
519    #[case(".5", &[".5"])]
520    #[case("0x", &["0", "x"])]
521    fn numbers_follow_the_spec_shapes(#[case] source: &str, #[case] expected: &[&str]) {
522        assert_eq!(texts(source), expected);
523    }
524
525    #[test]
526    fn a_list_range_lexes_without_confusing_numbers_and_dots() {
527        // The dot-absorbing number scan reads `1..5` as one number token.
528        // Numbers never yield references, so the tolerance is harmless.
529        assert_eq!(texts("{1..5}"), ["{", "1..5", "}"]);
530    }
531
532    #[rstest]
533    #[case("// line comment")]
534    #[case("/* block comment */")]
535    fn comments_become_single_comment_tokens(#[case] source: &str) {
536        assert_eq!(kinds(source), [TokenKind::Comment, TokenKind::Eof]);
537    }
538
539    #[test]
540    fn line_comments_end_at_the_line_break() {
541        let source = "[A] // [B] not a ref\n[C]";
542        let tokens = tokenize(source);
543        assert_eq!(
544            texts(source),
545            ["[", "A", "]", "// [B] not a ref", "[", "C", "]"]
546        );
547        let comment = &tokens[3];
548        assert_eq!(comment.kind, TokenKind::Comment);
549        assert!(!comment.text.contains('\n'));
550    }
551
552    #[test]
553    fn unterminated_block_comment_runs_to_the_end() {
554        assert_eq!(kinds("/* [hidden"), [TokenKind::Comment, TokenKind::Eof]);
555    }
556
557    #[test]
558    fn comment_markers_inside_a_string_are_not_a_comment() {
559        assert_eq!(texts("\"// not a comment\""), ["\"// not a comment\""],);
560    }
561
562    #[test]
563    fn brackets_are_punctuator_tokens() {
564        // Field access and record literals both use plain brackets; the
565        // extractor tells the two apart by their contents.
566        assert_eq!(
567            kinds("[Amount] = [K = 1]"),
568            [
569                TokenKind::OpenBracket,
570                TokenKind::Identifier,
571                TokenKind::CloseBracket,
572                TokenKind::Operator,
573                TokenKind::OpenBracket,
574                TokenKind::Identifier,
575                TokenKind::Operator,
576                TokenKind::Number,
577                TokenKind::CloseBracket,
578                TokenKind::Eof,
579            ]
580        );
581    }
582
583    #[rstest]
584    #[case("??")]
585    #[case("<>")]
586    #[case(">=")]
587    #[case("<=")]
588    #[case("=>")]
589    #[case("..")]
590    #[case("...")]
591    fn multi_character_operators_lex_as_one_token(#[case] source: &str) {
592        assert_eq!(kinds(source), [TokenKind::Operator, TokenKind::Eof]);
593        assert_eq!(tokenize(source).first().expect("op").text, source);
594    }
595
596    #[test]
597    fn operators_prefer_the_longest_form() {
598        assert_eq!(texts("a<=b"), ["a", "<=", "b"]);
599        assert_eq!(texts("a?b"), ["a", "?", "b"]);
600        assert_eq!(texts("a ?? b"), ["a", "??", "b"]);
601    }
602
603    #[test]
604    fn unknown_characters_never_fail_the_scan() {
605        assert_eq!(
606            kinds("[A] ~ [B]"),
607            [
608                TokenKind::OpenBracket,
609                TokenKind::Identifier,
610                TokenKind::CloseBracket,
611                TokenKind::Unknown,
612                TokenKind::OpenBracket,
613                TokenKind::Identifier,
614                TokenKind::CloseBracket,
615                TokenKind::Eof,
616            ]
617        );
618    }
619
620    #[rstest]
621    #[case("\"string")]
622    #[case("#\"identifier")]
623    #[case("#!\"verbatim")]
624    fn unterminated_delimiters_run_to_the_end_without_panicking(#[case] source: &str) {
625        let tokens = tokenize(source);
626        assert_eq!(tokens.len(), 2); // one token + Eof
627        assert_eq!(&source[tokens[0].start..tokens[0].end()], source);
628    }
629
630    #[test]
631    fn unicode_names_lex_as_single_identifiers() {
632        assert_eq!(texts("Måned"), ["Måned"]);
633        assert_eq!(texts("#\"Salg ~ Beløb\""), ["#\"Salg ~ Beløb\""]);
634    }
635
636    #[test]
637    fn multibyte_characters_do_not_distort_offsets() {
638        let source = "#\"Ærø\"[Ø]";
639        let tokens = tokenize(source);
640        for token in &tokens {
641            assert_eq!(&source[token.start..token.end()], token.text);
642        }
643        assert_eq!(tokens.last().expect("eof").start, source.len());
644    }
645}
ripbi_core/m/lexer.rs

ripbi_core/m/
lexer.rs
