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    #[token("(")]
48    LParen,
49    #[token(")")]
50    RParen,
51    #[token("[")]
52    LBracket,
53    #[token("]")]
54    RBracket,
55    #[token("{")]
56    LBrace,
57    #[token("}")]
58    RBrace,
59
60    #[token("->")]
61    Arrow,
62    #[token("==")]
63    EqEq,
64    #[token("!=")]
65    NotEq,
66    #[token("<=")]
67    LtEq,
68    #[token(">=")]
69    GtEq,
70    // `$*` splices, `$` unquotes. Longest match puts `$*` first.
71    #[token("$*")]
72    DollarStar,
73    #[token("$")]
74    Dollar,
75    #[token("=")]
76    Eq,
77    #[token("<")]
78    Lt,
79    #[token(">")]
80    Gt,
81    #[token("+")]
82    Plus,
83    #[token("-")]
84    Minus,
85    #[token("*")]
86    Star,
87    #[token("/")]
88    Slash,
89    #[token("%")]
90    Percent,
91    #[token(".")]
92    Dot,
93    #[token(",")]
94    Comma,
95    #[token(":")]
96    Colon,
97    #[token("@")]
98    At,
99    #[token("|")]
100    Pipe,
101    #[token("?")]
102    Question,
103}
104
105/// A float literal's value, with the digit separators dropped.
106///
107/// `parse::<f64>` is the correctly-rounded reading of a decimal string, so `1.5e-3` and `0.0015`
108/// give the same `f64` — which is what lets a table of constants be transcribed in the notation it
109/// was published in rather than rewritten.
110fn float(lex: &mut logos::Lexer<Raw>) -> Option<f64> {
111    lex.slice().replace('_', "").parse::<f64>().ok()
112}
113
114fn unescape(raw: &str) -> Option<String> {
115    let inner = &raw[1..raw.len() - 1];
116    let mut out = String::with_capacity(inner.len());
117    let mut chars = inner.chars();
118    while let Some(c) = chars.next() {
119        if c != '\\' {
120            out.push(c);
121            continue;
122        }
123        match chars.next()? {
124            'n' => out.push('\n'),
125            't' => out.push('\t'),
126            'r' => out.push('\r'),
127            '0' => out.push('\0'),
128            '\\' => out.push('\\'),
129            '"' => out.push('"'),
130            // `\u{202E}` — the escape hatch `security::scan` implies. A program may need one of
131            // the characters that file refuses as a *value*; spelling it out is what makes the
132            // difference between a value and a disguise.
133            'u' => {
134                let mut hex = String::new();
135                if chars.next()? != '{' {
136                    return None;
137                }
138                for c in chars.by_ref() {
139                    if c == '}' {
140                        break;
141                    }
142                    hex.push(c);
143                }
144                out.push(char::from_u32(u32::from_str_radix(&hex, 16).ok()?)?);
145            }
146            // Unknown escapes are kept verbatim rather than silently dropped, because `\d`
147            // inside a `regex"..."` literal is a real thing to want (§2.5).
148            other => {
149                out.push('\\');
150                out.push(other);
151            }
152        }
153    }
154    Some(out)
155}
156
157/// A token after layout: the raw tokens plus the three synthetic ones.
158#[derive(Clone, Debug, PartialEq)]
159pub enum Tok {
160    Raw(Raw),
161    Newline,
162    Indent,
163    Dedent,
164    Eof,
165}
166
167#[derive(Clone, Debug)]
168pub struct Token {
169    pub tok: Tok,
170    pub span: Span,
171}
172
173impl Token {
174    pub fn raw(&self) -> Option<&Raw> {
175        match &self.tok {
176            Tok::Raw(r) => Some(r),
177            _ => None,
178        }
179    }
180
181    pub fn is_ident(&self, name: &str) -> bool {
182        matches!(self.raw(), Some(Raw::Ident(s)) if s == name)
183    }
184
185    pub fn describe(&self) -> String {
186        match &self.tok {
187            Tok::Newline => "end of line".into(),
188            Tok::Indent => "an indented block".into(),
189            Tok::Dedent => "the end of a block".into(),
190            Tok::Eof => "end of file".into(),
191            Tok::Raw(r) => match r {
192                Raw::Ident(s) => format!("`{s}`"),
193                Raw::Keyword(s) => format!("`:{s}`"),
194                Raw::Int(n) => format!("`{n}`"),
195                Raw::Float(n) => format!("`{n}`"),
196                Raw::Str(_) => "a string".into(),
197                Raw::Newline => "end of line".into(),
198                other => format!("`{}`", punct(other)),
199            },
200        }
201    }
202}
203
204fn punct(r: &Raw) -> &'static str {
205    match r {
206        Raw::LParen => "(",
207        Raw::RParen => ")",
208        Raw::LBracket => "[",
209        Raw::RBracket => "]",
210        Raw::LBrace => "{",
211        Raw::RBrace => "}",
212        Raw::Arrow => "->",
213        Raw::EqEq => "==",
214        Raw::NotEq => "!=",
215        Raw::LtEq => "<=",
216        Raw::GtEq => ">=",
217        Raw::DollarStar => "$*",
218        Raw::Dollar => "$",
219        Raw::Eq => "=",
220        Raw::Lt => "<",
221        Raw::Gt => ">",
222        Raw::Plus => "+",
223        Raw::Minus => "-",
224        Raw::Star => "*",
225        Raw::Slash => "/",
226        Raw::Percent => "%",
227        Raw::Dot => ".",
228        Raw::Comma => ",",
229        Raw::Colon => ":",
230        Raw::At => "@",
231        Raw::Pipe => "|",
232        Raw::Question => "?",
233        _ => "?",
234    }
235}
236
237/// Lex and lay out one file.
238///
239/// Errors are reported rather than thrown: a file with an unlexable character still produces a
240/// token stream, so the parser can carry on and report more than one problem per run.
241pub fn lex(file: FileId, src: &str, diags: &mut Diagnostics) -> Vec<Token> {
242    let mut lexed: Vec<Token> = Vec::new();
243    let mut lx = Raw::lexer(src);
244    while let Some(res) = lx.next() {
245        let span = Span::new(file, lx.span());
246        match res {
247            Ok(r) => lexed.push(Token {
248                tok: Tok::Raw(r),
249                span,
250            }),
251            // A letter from another script is not a typo and not a stray byte: it is either a
252            // mistake worth naming or a confusable, and UTS #39's answer for both is the same.
253            Err(())
254                if src[span.start as usize..span.end as usize]
255                    .chars()
256                    .any(crate::security::is_non_ascii_letter) =>
257            {
258                diags.push(
259                    Diagnostic::error("B0103", "an identifier outside the ASCII profile", span)
260                        .with_primary_label("not an identifier character in Beck")
261                        .with_note(format!(
262                            "Beck's identifiers are `[A-Za-z_][A-Za-z0-9_]*` — UTS #39's \
263                             ASCII-Only restriction level, against Unicode {}. Two identifiers \
264                             that look alike cannot then be different names",
265                            crate::security::UNICODE
266                        )),
267                )
268            }
269            Err(()) => diags.push(
270                Diagnostic::error("B0100", "unrecognised character", span)
271                    .with_primary_label("not a Beck token"),
272            ),
273        }
274    }
275    layout(file, src, lexed, diags)
276}
277
278/// Python's layout algorithm: an indent stack, brackets suppressing significance.
279fn layout(file: FileId, src: &str, lexed: Vec<Token>, diags: &mut Diagnostics) -> Vec<Token> {
280    let mut out: Vec<Token> = Vec::new();
281    let mut stack: Vec<usize> = vec![0];
282    let mut depth: i32 = 0;
283    let mut at_line_start = true;
284    let mut line_has_content = false;
285
286    let mut i = 0;
287    while i < lexed.len() {
288        let t = &lexed[i];
289
290        if matches!(t.tok, Tok::Raw(Raw::Newline)) {
291            if depth == 0 && line_has_content {
292                out.push(Token {
293                    tok: Tok::Newline,
294                    span: t.span,
295                });
296                line_has_content = false;
297                at_line_start = true;
298            }
299            i += 1;
300            continue;
301        }
302
303        if at_line_start && depth == 0 {
304            let col = indent_width(src, t.span.start as usize);
305            let top = *stack.last().expect("indent stack is never empty");
306            if col > top {
307                stack.push(col);
308                out.push(Token {
309                    tok: Tok::Indent,
310                    span: t.span,
311                });
312            } else if col < top {
313                while *stack.last().expect("indent stack is never empty") > col {
314                    stack.pop();
315                    out.push(Token {
316                        tok: Tok::Dedent,
317                        span: t.span,
318                    });
319                }
320                if *stack.last().expect("indent stack is never empty") != col {
321                    diags.push(
322                        Diagnostic::error("B0101", "inconsistent indentation", t.span)
323                            .with_primary_label("this line does not match any enclosing block")
324                            .with_note("indentation is significant: spaces only, four per level"),
325                    );
326                    stack.push(col);
327                }
328            }
329            at_line_start = false;
330        }
331
332        match &t.tok {
333            Tok::Raw(Raw::LParen | Raw::LBracket | Raw::LBrace) => depth += 1,
334            Tok::Raw(Raw::RParen | Raw::RBracket | Raw::RBrace) => depth -= 1,
335            _ => {}
336        }
337        line_has_content = true;
338        out.push(t.clone());
339        i += 1;
340    }
341
342    let end = Span::new(file, src.len()..src.len());
343    if line_has_content {
344        out.push(Token {
345            tok: Tok::Newline,
346            span: end,
347        });
348    }
349    while stack.len() > 1 {
350        stack.pop();
351        out.push(Token {
352            tok: Tok::Dedent,
353            span: end,
354        });
355    }
356    out.push(Token {
357        tok: Tok::Eof,
358        span: end,
359    });
360    out
361}
362
363/// How far into the line the first token starts, counting a tab as one column.
364///
365/// §2.6 fixes indentation as "spaces only, 4"; a tab is therefore a lint, not a width question,
366/// and counting it as one keeps the layout deterministic either way.
367fn indent_width(src: &str, offset: usize) -> usize {
368    let line_start = src[..offset].rfind('\n').map(|i| i + 1).unwrap_or(0);
369    src[line_start..offset].chars().count()
370}
371
372#[cfg(test)]
373mod tests {
374    use super::*;
375
376    fn toks(src: &str) -> Vec<Tok> {
377        let mut map = beck_diag::SourceMap::new();
378        let f = map.add("t.beck", src);
379        let mut d = Diagnostics::new();
380        let out = lex(f, src, &mut d).into_iter().map(|t| t.tok).collect();
381        assert!(!d.has_errors(), "{}", d.render(&map));
382        out
383    }
384
385    #[test]
386    fn indentation_becomes_indent_and_dedent() {
387        let t = toks("def f():\n    return 1\n");
388        let shape: Vec<&str> = t
389            .iter()
390            .map(|t| match t {
391                Tok::Indent => "INDENT",
392                Tok::Dedent => "DEDENT",
393                Tok::Newline => "NL",
394                Tok::Eof => "EOF",
395                Tok::Raw(_) => "tok",
396            })
397            .collect();
398        assert_eq!(
399            shape,
400            [
401                "tok", "tok", "tok", "tok", "tok", "NL", "INDENT", "tok", "tok", "NL", "DEDENT",
402                "EOF"
403            ]
404        );
405    }
406
407    #[test]
408    fn brackets_suppress_layout_so_calls_may_span_lines() {
409        let t = toks("f(\n    1,\n    2,\n)\n");
410        assert_eq!(t.iter().filter(|t| matches!(t, Tok::Indent)).count(), 0);
411        assert_eq!(t.iter().filter(|t| matches!(t, Tok::Newline)).count(), 1);
412    }
413
414    #[test]
415    fn blank_and_comment_lines_do_not_close_a_block() {
416        let t = toks("def f():\n    a\n\n# a comment at column zero\n    b\n");
417        assert_eq!(t.iter().filter(|t| matches!(t, Tok::Dedent)).count(), 1);
418        assert_eq!(t.iter().filter(|t| matches!(t, Tok::Indent)).count(), 1);
419    }
420
421    #[test]
422    fn keywords_beat_the_colon_operator_and_dollar_star_beats_dollar() {
423        assert!(matches!(
424            &toks(":id x")[0],
425            Tok::Raw(Raw::Keyword(k)) if k == "id"
426        ));
427        assert!(matches!(&toks("$*xs")[0], Tok::Raw(Raw::DollarStar)));
428        assert!(matches!(&toks("$x")[0], Tok::Raw(Raw::Dollar)));
429    }
430
431    #[test]
432    fn strings_unescape() {
433        assert!(matches!(
434            &toks(r#""a\nb\"c""#)[0],
435            Tok::Raw(Raw::Str(s)) if s == "a\nb\"c"
436        ));
437    }
438
439    #[test]
440    fn nested_dedents_all_close_at_once() {
441        let t = toks("if a:\n    if b:\n        c\nd\n");
442        let dedents = t.iter().filter(|t| matches!(t, Tok::Dedent)).count();
443        assert_eq!(dedents, 2);
444    }
445}
beck_syntax/lexer.rs

beck_syntax/
lexer.rs
