beck_syntax/
lexer.rs

1//! Tokens, and the layout algorithm that turns indentation into `INDENT`/`DEDENT`.
2//!
3//! [`docs/02-syntax.md`](../../../../../docs/02-syntax.md) §2.8: "`logos` for tokens; a hand-written
4//! layout algorithm producing explicit `INDENT`/`DEDENT`/`NEWLINE` tokens (Python's approach), with
5//! brackets suppressing layout so multi-line calls work."
6//!
7//! Two rules that are easy to get subtly wrong and are therefore stated here:
8//!
9//! * **Brackets suppress layout.** Inside `(`/`[`/`{` no newline is significant, so a call may span
10//!   lines without the parser ever seeing it.
11//! * **Blank and comment-only lines have no indentation.** They emit nothing at all, so a comment
12//!   at column 0 inside an indented block does not close the block.
13
14use beck_diag::{Diagnostic, Diagnostics, FileId, Span};
15use logos::Logos;
16
17#[derive(Clone, Debug, PartialEq, Logos)]
18#[logos(skip r"[ \t]+")]
19// A comment runs to the end of its line — the greedy sweep is the meaning.
20#[logos(skip(r"#[^\n]*", allow_greedy = true))]
21pub enum Raw {
22    #[regex(r"\n")]
23    Newline,
24
25    #[regex(r"[A-Za-z_][A-Za-z0-9_]*", |lex| lex.slice().to_string())]
26    Ident(String),
27
28    // `:name` — a keyword literal. Written before the `:` operator so it wins the longest match.
29    #[regex(r":[A-Za-z_][A-Za-z0-9_\-]*", |lex| lex.slice()[1..].to_string())]
30    Keyword(String),
31
32    // A digit is required on both sides of the point, and the exponent is optional. `1e6` — an
33    // exponent with no point — is a float too: a literal whose value is not representable as an
34    // `Int` must not lex as one, and the notation is how every table of physical constants is
35    // written. Longest-match puts this ahead of `Int` for `1e6`, and `1.e6` is not a float in any
36    // of the languages that have this notation, so it is not one here.
37    #[regex(r"[0-9][0-9_]*\.[0-9][0-9_]*([eE][+-]?[0-9]+)?", float)]
38    #[regex(r"[0-9][0-9_]*[eE][+-]?[0-9]+", float)]
39    Float(f64),
40
41    #[regex(r"[0-9][0-9_]*", |lex| lex.slice().replace('_', "").parse::<i64>().ok())]
42    Int(i64),
43
44    #[regex(r#""([^"\\\n]|\\.)*""#, |lex| unescape(lex.slice()))]
45    Str(String),
46
47    // `name"body"` — a typed literal (§2.5). The body is **raw**: no escape is processed and no
48    // `"` may appear, because the notation inside belongs to whatever parses the body and a
49    // regex's `\d` is not this lexer's business. Longest match puts this ahead of an `Ident`
50    // followed by a `Str`, which is a pair no Beck program has ever written adjacent.
51    #[regex(r#"[A-Za-z_][A-Za-z0-9_]*"[^"\n]*""#, sigil)]
52    Sigil(SigilText),
53
54    #[token("(")]
55    LParen,
56    #[token(")")]
57    RParen,
58    #[token("[")]
59    LBracket,
60    #[token("]")]
61    RBracket,
62    #[token("{")]
63    LBrace,
64    #[token("}")]
65    RBrace,
66
67    #[token("->")]
68    Arrow,
69    #[token("==")]
70    EqEq,
71    #[token("!=")]
72    NotEq,
73    #[token("<=")]
74    LtEq,
75    #[token(">=")]
76    GtEq,
77    // `$*` splices, `$` unquotes. Longest match puts `$*` first.
78    #[token("$*")]
79    DollarStar,
80    #[token("$")]
81    Dollar,
82    #[token("=")]
83    Eq,
84    #[token("<")]
85    Lt,
86    #[token(">")]
87    Gt,
88    #[token("+")]
89    Plus,
90    #[token("-")]
91    Minus,
92    #[token("*")]
93    Star,
94    #[token("/")]
95    Slash,
96    #[token("%")]
97    Percent,
98    #[token(".")]
99    Dot,
100    #[token(",")]
101    Comma,
102    #[token(":")]
103    Colon,
104    #[token("@")]
105    At,
106    #[token("|")]
107    Pipe,
108    #[token("?")]
109    Question,
110}
111
112/// A float literal's value, with the digit separators dropped.
113///
114/// `parse::<f64>` is the correctly-rounded reading of a decimal string, so `1.5e-3` and `0.0015`
115/// give the same `f64` — which is what lets a table of constants be transcribed in the notation it
116/// was published in rather than rewritten.
117/// A typed literal's two halves: the sigil's name, and the body exactly as written.
118///
119/// The body is not unescaped. `regex"^\d{4}$"` must reach its macro with the backslash it was
120/// written with, so the one thing this lexer does to a sigil body is find where it ends.
121#[derive(Clone, Debug, PartialEq)]
122pub struct SigilText {
123    pub name: String,
124    pub raw: String,
125}
126
127fn sigil(lex: &mut logos::Lexer<Raw>) -> SigilText {
128    let s = lex.slice();
129    // The regex guarantees both quotes, and the first one ends the name.
130    let q = s
131        .find('"')
132        .expect("a sigil's regex requires an opening quote");
133    SigilText {
134        name: s[..q].to_string(),
135        raw: s[q + 1..s.len() - 1].to_string(),
136    }
137}
138
139fn float(lex: &mut logos::Lexer<Raw>) -> Option<f64> {
140    lex.slice().replace('_', "").parse::<f64>().ok()
141}
142
143fn unescape(raw: &str) -> Option<String> {
144    let inner = &raw[1..raw.len() - 1];
145    let mut out = String::with_capacity(inner.len());
146    let mut chars = inner.chars();
147    while let Some(c) = chars.next() {
148        if c != '\\' {
149            out.push(c);
150            continue;
151        }
152        match chars.next()? {
153            'n' => out.push('\n'),
154            't' => out.push('\t'),
155            'r' => out.push('\r'),
156            '0' => out.push('\0'),
157            '\\' => out.push('\\'),
158            '"' => out.push('"'),
159            // `\u{202E}` — the escape hatch `security::scan` implies. A program may need one of
160            // the characters that file refuses as a *value*; spelling it out is what makes the
161            // difference between a value and a disguise.
162            'u' => {
163                let mut hex = String::new();
164                if chars.next()? != '{' {
165                    return None;
166                }
167                for c in chars.by_ref() {
168                    if c == '}' {
169                        break;
170                    }
171                    hex.push(c);
172                }
173                out.push(char::from_u32(u32::from_str_radix(&hex, 16).ok()?)?);
174            }
175            // Unknown escapes are kept verbatim rather than silently dropped, because `\d`
176            // inside a `regex"..."` literal is a real thing to want (§2.5).
177            other => {
178                out.push('\\');
179                out.push(other);
180            }
181        }
182    }
183    Some(out)
184}
185
186/// A token after layout: the raw tokens plus the three synthetic ones.
187#[derive(Clone, Debug, PartialEq)]
188pub enum Tok {
189    Raw(Raw),
190    Newline,
191    Indent,
192    Dedent,
193    Eof,
194}
195
196#[derive(Clone, Debug)]
197pub struct Token {
198    pub tok: Tok,
199    pub span: Span,
200}
201
202impl Token {
203    pub fn raw(&self) -> Option<&Raw> {
204        match &self.tok {
205            Tok::Raw(r) => Some(r),
206            _ => None,
207        }
208    }
209
210    pub fn is_ident(&self, name: &str) -> bool {
211        matches!(self.raw(), Some(Raw::Ident(s)) if s == name)
212    }
213
214    pub fn describe(&self) -> String {
215        match &self.tok {
216            Tok::Newline => "end of line".into(),
217            Tok::Indent => "an indented block".into(),
218            Tok::Dedent => "the end of a block".into(),
219            Tok::Eof => "end of file".into(),
220            Tok::Raw(r) => match r {
221                Raw::Ident(s) => format!("`{s}`"),
222                Raw::Keyword(s) => format!("`:{s}`"),
223                Raw::Int(n) => format!("`{n}`"),
224                Raw::Float(n) => format!("`{n}`"),
225                Raw::Str(_) => "a string".into(),
226                Raw::Sigil(t) => format!("`{}\"…\"`", t.name),
227                Raw::Newline => "end of line".into(),
228                other => format!("`{}`", punct(other)),
229            },
230        }
231    }
232}
233
234fn punct(r: &Raw) -> &'static str {
235    match r {
236        Raw::LParen => "(",
237        Raw::RParen => ")",
238        Raw::LBracket => "[",
239        Raw::RBracket => "]",
240        Raw::LBrace => "{",
241        Raw::RBrace => "}",
242        Raw::Arrow => "->",
243        Raw::EqEq => "==",
244        Raw::NotEq => "!=",
245        Raw::LtEq => "<=",
246        Raw::GtEq => ">=",
247        Raw::DollarStar => "$*",
248        Raw::Dollar => "$",
249        Raw::Eq => "=",
250        Raw::Lt => "<",
251        Raw::Gt => ">",
252        Raw::Plus => "+",
253        Raw::Minus => "-",
254        Raw::Star => "*",
255        Raw::Slash => "/",
256        Raw::Percent => "%",
257        Raw::Dot => ".",
258        Raw::Comma => ",",
259        Raw::Colon => ":",
260        Raw::At => "@",
261        Raw::Pipe => "|",
262        Raw::Question => "?",
263        _ => "?",
264    }
265}
266
267/// The words the Python surface reads as syntax rather than as names.
268///
269/// The lexer does not distinguish them — `def` is an [`Raw::Ident`] like any other, and the parser
270/// is what decides that this one starts a definition. So this is a *list*, and a list is a second
271/// place for the truth to live unless something holds it to the first: `the_keyword_table_is_the_one_the_parser_matches`
272/// reads every `at_kw("…")` and `eat_kw("…")` out of the parser's own source and asserts the two
273/// sets are equal. A keyword the parser gains and this does not is a red test rather than a word
274/// an editor quietly stops colouring.
275///
276/// It is here rather than in the parser because its consumers are editors — highlighting and
277/// completion ([`beck_core::editor`]) — and an editor should not have to depend on a parser to
278/// know which words are keywords.
279///
280/// [`beck_core::editor`]: ../../beck_core/editor/index.html
281pub const KEYWORDS: &[&str] = &[
282    "and",
283    "by",
284    "case",
285    "contains",
286    "def",
287    "elif",
288    "else",
289    "expect",
290    "flow",
291    "for",
292    "given",
293    "identity",
294    "if",
295    "impl",
296    "import",
297    "in",
298    "lambda",
299    "macro",
300    "match",
301    "matches",
302    "model",
303    "newtype",
304    "no",
305    "not",
306    "nothing",
307    "on",
308    "once",
309    "or",
310    "page",
311    "parallel",
312    "place",
313    "property",
314    "quote",
315    "raise",
316    "reaches",
317    "return",
318    "row",
319    "sends",
320    "session",
321    "snapshot",
322    "state",
323    "stub",
324    "test",
325    "times",
326    "trait",
327    "try",
328    "type",
329    "typed",
330    "union",
331    "uses",
332    "var",
333    "when",
334    "while",
335    "wire_compatible_with",
336    "with",
337];
338
339/// Lex and lay out one file.
340///
341/// Errors are reported rather than thrown: a file with an unlexable character still produces a
342/// token stream, so the parser can carry on and report more than one problem per run.
343pub fn lex(file: FileId, src: &str, diags: &mut Diagnostics) -> Vec<Token> {
344    let mut lexed: Vec<Token> = Vec::new();
345    let mut lx = Raw::lexer(src);
346    while let Some(res) = lx.next() {
347        let span = Span::new(file, lx.span());
348        match res {
349            Ok(r) => lexed.push(Token {
350                tok: Tok::Raw(r),
351                span,
352            }),
353            // A letter from another script is not a typo and not a stray byte: it is either a
354            // mistake worth naming or a confusable, and UTS #39's answer for both is the same.
355            Err(())
356                if src[span.start as usize..span.end as usize]
357                    .chars()
358                    .any(crate::security::is_non_ascii_letter) =>
359            {
360                diags.push(
361                    Diagnostic::error("B0103", "an identifier outside the ASCII profile", span)
362                        .with_primary_label("not an identifier character in Beck")
363                        .with_note(format!(
364                            "Beck's identifiers are `[A-Za-z_][A-Za-z0-9_]*` — UTS #39's \
365                             ASCII-Only restriction level, against Unicode {}. Two identifiers \
366                             that look alike cannot then be different names",
367                            crate::security::UNICODE
368                        )),
369                )
370            }
371            Err(()) => diags.push(
372                Diagnostic::error("B0100", "unrecognised character", span)
373                    .with_primary_label("not a Beck token"),
374            ),
375        }
376    }
377    layout(file, src, lexed, diags)
378}
379
380/// Python's layout algorithm: an indent stack, brackets suppressing significance.
381fn layout(file: FileId, src: &str, lexed: Vec<Token>, diags: &mut Diagnostics) -> Vec<Token> {
382    let mut out: Vec<Token> = Vec::new();
383    let mut stack: Vec<usize> = vec![0];
384    let mut depth: i32 = 0;
385    let mut at_line_start = true;
386    let mut line_has_content = false;
387
388    let mut i = 0;
389    while i < lexed.len() {
390        let t = &lexed[i];
391
392        if matches!(t.tok, Tok::Raw(Raw::Newline)) {
393            if depth == 0 && line_has_content {
394                out.push(Token {
395                    tok: Tok::Newline,
396                    span: t.span,
397                });
398                line_has_content = false;
399                at_line_start = true;
400            }
401            i += 1;
402            continue;
403        }
404
405        if at_line_start && depth == 0 {
406            let col = indent_width(src, t.span.start as usize);
407            let top = *stack.last().expect("indent stack is never empty");
408            if col > top {
409                stack.push(col);
410                out.push(Token {
411                    tok: Tok::Indent,
412                    span: t.span,
413                });
414            } else if col < top {
415                while *stack.last().expect("indent stack is never empty") > col {
416                    stack.pop();
417                    out.push(Token {
418                        tok: Tok::Dedent,
419                        span: t.span,
420                    });
421                }
422                if *stack.last().expect("indent stack is never empty") != col {
423                    diags.push(
424                        Diagnostic::error("B0101", "inconsistent indentation", t.span)
425                            .with_primary_label("this line does not match any enclosing block")
426                            .with_note("indentation is significant: spaces only, four per level"),
427                    );
428                    stack.push(col);
429                }
430            }
431            at_line_start = false;
432        }
433
434        match &t.tok {
435            Tok::Raw(Raw::LParen | Raw::LBracket | Raw::LBrace) => depth += 1,
436            Tok::Raw(Raw::RParen | Raw::RBracket | Raw::RBrace) => depth -= 1,
437            _ => {}
438        }
439        line_has_content = true;
440        out.push(t.clone());
441        i += 1;
442    }
443
444    let end = Span::new(file, src.len()..src.len());
445    if line_has_content {
446        out.push(Token {
447            tok: Tok::Newline,
448            span: end,
449        });
450    }
451    while stack.len() > 1 {
452        stack.pop();
453        out.push(Token {
454            tok: Tok::Dedent,
455            span: end,
456        });
457    }
458    out.push(Token {
459        tok: Tok::Eof,
460        span: end,
461    });
462    out
463}
464
465/// How far into the line the first token starts, counting a tab as one column.
466///
467/// §2.6 fixes indentation as "spaces only, 4"; a tab is therefore a lint, not a width question,
468/// and counting it as one keeps the layout deterministic either way.
469fn indent_width(src: &str, offset: usize) -> usize {
470    let line_start = src[..offset].rfind('\n').map(|i| i + 1).unwrap_or(0);
471    src[line_start..offset].chars().count()
472}
473
474#[cfg(test)]
475mod tests {
476    use super::*;
477
478    fn toks(src: &str) -> Vec<Tok> {
479        let mut map = beck_diag::SourceMap::new();
480        let f = map.add("t.beck", src);
481        let mut d = Diagnostics::new();
482        let out = lex(f, src, &mut d).into_iter().map(|t| t.tok).collect();
483        assert!(!d.has_errors(), "{}", d.render(&map));
484        out
485    }
486
487    /// [`KEYWORDS`] is a list, and this is what stops it being a *second* list.
488    ///
489    /// The parser asks "is the current token this word?" in exactly two places — `at_kw` and
490    /// `eat_kw` — so the words it treats as syntax are recoverable from its source, and a keyword
491    /// added there without being added here fails here rather than in an editor nobody is running.
492    #[test]
493    fn the_keyword_table_is_the_one_the_parser_matches() {
494        let parser = include_str!("parser.rs");
495        let mut matched: Vec<&str> = Vec::new();
496        for (at, _) in parser.match_indices("_kw(\"") {
497            let rest = &parser[at + "_kw(\"".len()..];
498            let Some(end) = rest.find('"') else { continue };
499            matched.push(&rest[..end]);
500        }
501        matched.sort_unstable();
502        matched.dedup();
503        assert!(
504            !matched.is_empty(),
505            "no `at_kw(\"…\")` calls found — this test has stopped reading the parser"
506        );
507        let listed: Vec<&str> = KEYWORDS.to_vec();
508        assert_eq!(
509            listed, matched,
510            "`KEYWORDS` and the words the parser matches have diverged"
511        );
512    }
513
514    #[test]
515    fn indentation_becomes_indent_and_dedent() {
516        let t = toks("def f():\n    return 1\n");
517        let shape: Vec<&str> = t
518            .iter()
519            .map(|t| match t {
520                Tok::Indent => "INDENT",
521                Tok::Dedent => "DEDENT",
522                Tok::Newline => "NL",
523                Tok::Eof => "EOF",
524                Tok::Raw(_) => "tok",
525            })
526            .collect();
527        assert_eq!(
528            shape,
529            [
530                "tok", "tok", "tok", "tok", "tok", "NL", "INDENT", "tok", "tok", "NL", "DEDENT",
531                "EOF"
532            ]
533        );
534    }
535
536    #[test]
537    fn brackets_suppress_layout_so_calls_may_span_lines() {
538        let t = toks("f(\n    1,\n    2,\n)\n");
539        assert_eq!(t.iter().filter(|t| matches!(t, Tok::Indent)).count(), 0);
540        assert_eq!(t.iter().filter(|t| matches!(t, Tok::Newline)).count(), 1);
541    }
542
543    #[test]
544    fn blank_and_comment_lines_do_not_close_a_block() {
545        let t = toks("def f():\n    a\n\n# a comment at column zero\n    b\n");
546        assert_eq!(t.iter().filter(|t| matches!(t, Tok::Dedent)).count(), 1);
547        assert_eq!(t.iter().filter(|t| matches!(t, Tok::Indent)).count(), 1);
548    }
549
550    #[test]
551    fn keywords_beat_the_colon_operator_and_dollar_star_beats_dollar() {
552        assert!(matches!(
553            &toks(":id x")[0],
554            Tok::Raw(Raw::Keyword(k)) if k == "id"
555        ));
556        assert!(matches!(&toks("$*xs")[0], Tok::Raw(Raw::DollarStar)));
557        assert!(matches!(&toks("$x")[0], Tok::Raw(Raw::Dollar)));
558    }
559
560    #[test]
561    fn strings_unescape() {
562        assert!(matches!(
563            &toks(r#""a\nb\"c""#)[0],
564            Tok::Raw(Raw::Str(s)) if s == "a\nb\"c"
565        ));
566    }
567
568    #[test]
569    fn nested_dedents_all_close_at_once() {
570        let t = toks("if a:\n    if b:\n        c\nd\n");
571        let dedents = t.iter().filter(|t| matches!(t, Tok::Dedent)).count();
572        assert_eq!(dedents, 2);
573    }
574}
beck_syntax/lexer.rs

beck_syntax/
lexer.rs
