1use crate::diagnostic::Diagnostic;
7use crate::span::Span;
8use crate::token::{StrPart, Tok, Token, keyword};
9
10pub fn lex(src: &str, base: u32) -> (Vec<Token>, Vec<Diagnostic>) {
13 let mut lexer = Lexer {
14 src,
15 bytes: src.as_bytes(),
16 pos: 0,
17 base,
18 tokens: Vec::new(),
19 diags: Vec::new(),
20 };
21 lexer.run();
22 (filter_newlines(lexer.tokens), lexer.diags)
23}
24
25struct Lexer<'a> {
26 src: &'a str,
27 bytes: &'a [u8],
28 pos: usize,
29 base: u32,
30 tokens: Vec<Token>,
31 diags: Vec<Diagnostic>,
32}
33
34impl Lexer<'_> {
35 fn span(&self, lo: usize, hi: usize) -> Span {
36 Span::new(lo, hi).shifted(self.base)
37 }
38
39 fn push(&mut self, tok: Tok, lo: usize) {
40 let span = self.span(lo, self.pos);
41 self.tokens.push(Token { tok, span });
42 }
43
44 fn error(&mut self, lo: usize, hi: usize, message: impl Into<String>) -> &mut Diagnostic {
45 let span = self.span(lo, hi);
46 self.diags.push(Diagnostic::error(span, message));
47 self.diags.last_mut().unwrap()
48 }
49
50 fn peek(&self, ahead: usize) -> u8 {
51 self.bytes.get(self.pos + ahead).copied().unwrap_or(0)
52 }
53
54 fn run(&mut self) {
55 while self.pos < self.bytes.len() {
56 let c = self.bytes[self.pos];
57 match c {
58 b' ' | b'\t' | b'\r' => self.pos += 1,
59 b'\n' => {
60 let lo = self.pos;
61 self.pos += 1;
62 self.push(Tok::Newline, lo);
63 }
64 b'#' => {
65 while self.pos < self.bytes.len() && self.bytes[self.pos] != b'\n' {
66 self.pos += 1;
67 }
68 }
69 b'0'..=b'9' => self.number(),
70 b'"' => self.string(),
71 c if c.is_ascii_alphabetic() || c == b'_' => self.word(),
72 _ => self.punct(),
73 }
74 }
75 let end = self.bytes.len();
76 self.tokens.push(Token {
77 tok: Tok::Eof,
78 span: self.span(end, end),
79 });
80 }
81
82 fn digits(&mut self) {
83 while self.peek(0).is_ascii_digit() || (self.peek(0) == b'_' && self.peek(1).is_ascii_digit()) {
84 self.pos += 1;
85 }
86 }
87
88 fn number(&mut self) {
89 let lo = self.pos;
90 if self.peek(0) == b'0' {
91 let radix = match self.peek(1) {
92 b'b' | b'B' => Some(2),
93 b'x' | b'X' => Some(16),
94 _ => None,
95 };
96 if let Some(radix) = radix {
97 self.radix_number(radix);
98 return;
99 }
100 }
101 self.digits();
102 let mut is_float = false;
103 if self.peek(0) == b'.' && self.peek(1).is_ascii_digit() {
104 self.pos += 1;
105 self.digits();
106 is_float = true;
107 }
108 if matches!(self.peek(0), b'e' | b'E')
109 && (self.peek(1).is_ascii_digit() || (matches!(self.peek(1), b'+' | b'-') && self.peek(2).is_ascii_digit()))
110 {
111 self.pos += 2;
112 self.digits();
113 is_float = true;
114 }
115 let text: String = self.src[lo..self.pos].chars().filter(|&c| c != '_').collect();
116
117 if !is_float && self.peek(0) == b'd' && self.peek(1).is_ascii_digit() {
119 self.pos += 1;
120 let sides_lo = self.pos;
121 self.digits();
122 let sides_text: String = self.src[sides_lo..self.pos].chars().filter(|&c| c != '_').collect();
123 if self.peek(0).is_ascii_alphanumeric() || self.peek(0) == b'_' {
124 self.word_tail();
125 self.error(lo, self.pos, "invalid dice literal")
126 .help("dice are written like `2d6`: a count, `d`, and a number of sides");
127 return;
128 }
129 self.dice(lo, Some(&text), &sides_text);
130 return;
131 }
132
133 if self.peek(0) == b'%' {
135 self.pos += 1;
136 match text.parse::<f64>() {
137 Ok(v) => self.push(Tok::Percent(v / 100.0), lo),
138 Err(_) => {
139 self.error(lo, self.pos, "invalid percentage");
140 }
141 }
142 return;
143 }
144
145 if self.peek(0).is_ascii_alphabetic() || self.peek(0) == b'_' {
146 self.word_tail();
147 self.error(lo, self.pos, "invalid number")
148 .help("names can't start with a digit");
149 return;
150 }
151
152 if is_float {
153 match text.parse::<f64>() {
154 Ok(v) => self.push(Tok::Float(v), lo),
155 Err(_) => {
156 self.error(lo, self.pos, "invalid number");
157 }
158 }
159 } else {
160 match text.parse::<probl_number::Integer>() {
161 Ok(v) => self.push(Tok::Int(v), lo),
162 Err(err) => {
163 self.error(lo, self.pos, err.to_string());
164 }
165 }
166 }
167 }
168
169 fn radix_number(&mut self, radix: u32) {
170 let lo = self.pos;
171 self.pos += 2;
172 let digits_lo = self.pos;
173 self.word_tail();
176 let raw = &self.src[digits_lo..self.pos];
177 let name = if radix == 2 { "binary" } else { "hexadecimal" };
178 let valid_separators = !raw.starts_with('_') && !raw.ends_with('_') && !raw.contains("__");
179 let digits = raw.replace('_', "");
180 let parsed = if valid_separators {
181 probl_number::Integer::from_radix_digits(&digits, radix)
182 } else {
183 Err(probl_number::IntError::Invalid)
184 };
185 match parsed {
186 Ok(n) => self.push(Tok::Int(n), lo),
187 Err(probl_number::IntError::Invalid) => {
188 self.error(lo, self.pos, format!("invalid {name} integer literal")).help(if radix == 2 {
189 "write `0b` followed by binary digits (0 or 1), with optional underscores between digits"
190 } else {
191 "write `0x` followed by hexadecimal digits (0–9, a–f or A–F), with optional underscores between digits"
192 });
193 }
194 Err(err) => {
195 self.error(lo, self.pos, err.to_string());
196 }
197 }
198 }
199
200 fn dice(&mut self, lo: usize, count: Option<&str>, sides: &str) {
201 let count = match count {
202 None => Some(1),
203 Some(text) => text.parse::<u32>().ok(),
204 };
205 let sides = sides.parse::<u32>().ok();
206 match (count, sides) {
207 (Some(count), Some(sides)) if count >= 1 && sides >= 1 => {
208 self.push(Tok::Dice { count, sides }, lo);
209 }
210 (Some(0), _) => {
211 self.error(lo, self.pos, "a dice roll needs at least one die");
212 }
213 (_, Some(0)) => {
214 self.error(lo, self.pos, "a die needs at least one side");
215 }
216 _ => {
217 self.error(lo, self.pos, "dice literal too large");
218 }
219 }
220 }
221
222 fn word_tail(&mut self) {
223 while self.peek(0).is_ascii_alphanumeric() || self.peek(0) == b'_' {
224 self.pos += 1;
225 }
226 }
227
228 fn word(&mut self) {
229 let lo = self.pos;
230 self.word_tail();
231 let src = self.src;
232 let text = &src[lo..self.pos];
233 if text == "_" {
234 self.push(Tok::Underscore, lo);
235 } else if let Some(sides) = text
236 .strip_prefix('d')
237 .filter(|s| !s.is_empty() && s.bytes().all(|b| b.is_ascii_digit()))
238 {
239 self.dice(lo, None, sides);
240 } else if let Some(tok) = keyword(text) {
241 self.push(tok, lo);
242 } else {
243 self.push(Tok::Ident(text.to_string()), lo);
244 }
245 }
246
247 fn string(&mut self) {
248 let lo = self.pos;
249 self.pos += 1; let mut parts = Vec::new();
251 let mut text = String::new();
252 loop {
253 let Some(c) = self.src[self.pos..].chars().next() else {
254 self.error(lo, self.pos, "unterminated string");
255 return;
256 };
257 match c {
258 '"' => {
259 self.pos += 1;
260 break;
261 }
262 '\n' => {
263 self.error(lo, self.pos, "unterminated string")
264 .help("strings must end on the line where they start");
265 return;
266 }
267 '\\' => {
268 let esc_lo = self.pos;
269 self.pos += 1;
270 let Some(e) = self.src[self.pos..].chars().next() else {
271 self.error(lo, self.pos, "unterminated string");
272 return;
273 };
274 self.pos += e.len_utf8();
275 match e {
276 'n' => text.push('\n'),
277 't' => text.push('\t'),
278 'r' => text.push('\r'),
279 '0' => text.push('\0'),
280 '\\' | '"' | '{' | '}' => text.push(e),
281 _ => {
282 self.error(esc_lo, self.pos, format!("unknown escape `\\{e}`"))
283 .help("the escapes are \\n \\t \\r \\0 \\\\ \\\" \\{ and \\}");
284 }
285 }
286 }
287 '{' => {
288 let open = self.pos;
289 self.pos += 1;
290 let start = self.pos;
291 let Some(end) = self.interpolation_end() else {
292 self.error(open, self.pos, "unclosed `{` in string")
293 .help("write `\\{` for a literal brace");
294 return;
295 };
296 if !text.is_empty() {
297 parts.push(StrPart::Lit(std::mem::take(&mut text)));
298 }
299 let src = self.src[start..end].to_string();
300 if src.trim().is_empty() {
301 self.error(open, end + 1, "empty `{}` in string")
302 .help("put an expression inside, or write `\\{` for a literal brace");
303 }
304 parts.push(StrPart::Expr {
305 src,
306 offset: self.base + start as u32,
307 });
308 self.pos = end + 1;
309 }
310 '}' => {
311 let at = self.pos;
312 self.pos += 1;
313 self.error(at, self.pos, "unmatched `}` in string")
314 .help("write `\\}` for a literal brace");
315 }
316 c => {
317 text.push(c);
318 self.pos += c.len_utf8();
319 }
320 }
321 }
322 if !text.is_empty() || parts.is_empty() {
323 parts.push(StrPart::Lit(text));
324 }
325 self.push(Tok::Str(parts), lo);
326 }
327
328 fn interpolation_end(&self) -> Option<usize> {
330 let mut depth = 1;
331 let mut i = self.pos;
332 let mut in_string = false;
333 while i < self.bytes.len() {
334 let b = self.bytes[i];
335 if b == b'\n' {
336 return None;
337 }
338 if in_string {
339 match b {
340 b'\\' => i += 1,
341 b'"' => in_string = false,
342 _ => {}
343 }
344 } else {
345 match b {
346 b'"' => in_string = true,
347 b'{' => depth += 1,
348 b'}' => {
349 depth -= 1;
350 if depth == 0 {
351 return Some(i);
352 }
353 }
354 _ => {}
355 }
356 }
357 i += 1;
358 }
359 None
360 }
361
362 fn punct(&mut self) {
363 let lo = self.pos;
364 let (tok, len) = match (self.peek(0), self.peek(1), self.peek(2)) {
365 (b'.', b'.', b'<') => (Tok::DotDotLt, 3),
366 (b'.', b'.', _) => (Tok::DotDot, 2),
367 (b'-', b'>', _) => (Tok::Arrow, 2),
368 (b'=', b'>', _) => (Tok::FatArrow, 2),
369 (b'=', b'=', _) => (Tok::EqEq, 2),
370 (b'!', b'=', _) => (Tok::NotEq, 2),
371 (b'<', b'=', _) => (Tok::Le, 2),
372 (b'>', b'=', _) => (Tok::Ge, 2),
373 (b'+', b'=', _) => (Tok::PlusAssign, 2),
374 (b'-', b'=', _) => (Tok::MinusAssign, 2),
375 (b'*', b'=', _) => (Tok::StarAssign, 2),
376 (b'/', b'=', _) => (Tok::SlashAssign, 2),
377 (b'(', _, _) => (Tok::LParen, 1),
378 (b')', _, _) => (Tok::RParen, 1),
379 (b'[', _, _) => (Tok::LBracket, 1),
380 (b']', _, _) => (Tok::RBracket, 1),
381 (b'{', _, _) => (Tok::LBrace, 1),
382 (b'}', _, _) => (Tok::RBrace, 1),
383 (b',', _, _) => (Tok::Comma, 1),
384 (b'.', _, _) => (Tok::Dot, 1),
385 (b':', _, _) => (Tok::Colon, 1),
386 (b';', _, _) => (Tok::Semi, 1),
387 (b'@', _, _) => (Tok::At, 1),
388 (b'|', b'|', _) => return self.unexpected(2, "use `or` instead of `||`"),
389 (b'|', _, _) => (Tok::Pipe, 1),
390 (b'~', _, _) => (Tok::Tilde, 1),
391 (b'=', _, _) => (Tok::Assign, 1),
392 (b'<', _, _) => (Tok::Lt, 1),
393 (b'>', _, _) => (Tok::Gt, 1),
394 (b'+', _, _) => (Tok::Plus, 1),
395 (b'-', _, _) => (Tok::Minus, 1),
396 (b'*', _, _) => (Tok::Star, 1),
397 (b'/', _, _) => (Tok::Slash, 1),
398 (b'^', _, _) => (Tok::Caret, 1),
399 (b'&', b'&', _) => return self.unexpected(2, "use `and` instead of `&&`"),
400 (b'!', _, _) => return self.unexpected(1, "use `not` for negation"),
401 (b'%', _, _) => {
402 return self.unexpected(
403 1,
404 "`%` only marks percentages, as in `30%`; for the remainder of a division use `mod`",
405 );
406 }
407 _ => {
408 let c = self.src[self.pos..].chars().next().unwrap();
409 self.pos += c.len_utf8();
410 self.error(lo, self.pos, format!("unexpected character `{c}`"));
411 return;
412 }
413 };
414 self.pos += len;
415 self.push(tok, lo);
416 }
417
418 fn unexpected(&mut self, len: usize, help: &str) {
419 let lo = self.pos;
420 self.pos += len;
421 let text = self.src[lo..self.pos].to_string();
422 self.error(lo, self.pos, format!("unexpected `{text}`")).help(help);
423 }
424}
425
426pub fn filter_newlines(tokens: Vec<Token>) -> Vec<Token> {
435 let mut out: Vec<Token> = Vec::with_capacity(tokens.len());
436 let mut in_parens: Vec<bool> = Vec::new();
438 let mut tokens = tokens.into_iter().peekable();
439 while let Some(token) = tokens.next() {
440 match token.tok {
441 Tok::LParen | Tok::LBracket => in_parens.push(true),
442 Tok::LBrace => in_parens.push(false),
443 Tok::RParen | Tok::RBracket | Tok::RBrace => {
444 in_parens.pop();
445 }
446 Tok::Newline => {
447 while tokens.next_if(|t| t.tok == Tok::Newline).is_some() {}
450 let after_continuation = out.last().is_none_or(|prev| continues_line(&prev.tok));
451 let before_continuation = tokens.peek().is_some_and(|t| t.tok == Tok::Dot);
452 if in_parens.last() == Some(&true) || after_continuation || before_continuation {
453 continue;
454 }
455 }
456 _ => {}
457 }
458 out.push(token);
459 }
460 out
461}
462
463fn continues_line(tok: &Tok) -> bool {
465 matches!(
466 tok,
467 Tok::Semi
468 | Tok::Comma
469 | Tok::Dot
470 | Tok::Colon
471 | Tok::LParen
472 | Tok::LBracket
473 | Tok::LBrace
474 | Tok::Arrow
475 | Tok::FatArrow
476 | Tok::Tilde
477 | Tok::Assign
478 | Tok::PlusAssign
479 | Tok::MinusAssign
480 | Tok::StarAssign
481 | Tok::SlashAssign
482 | Tok::EqEq
483 | Tok::NotEq
484 | Tok::Lt
485 | Tok::Le
486 | Tok::Gt
487 | Tok::Ge
488 | Tok::Plus
489 | Tok::Minus
490 | Tok::Star
491 | Tok::Slash
492 | Tok::Caret
493 | Tok::DotDot
494 | Tok::DotDotLt
495 | Tok::And
496 | Tok::Or
497 | Tok::Not
498 | Tok::Typeof
499 | Tok::In
500 | Tok::Div
501 | Tok::Mod
502 | Tok::Pipe
503 | Tok::At
504 | Tok::With
505 )
506}
507
508#[cfg(test)]
509mod tests {
510 use super::*;
511
512 fn toks(src: &str) -> Vec<Tok> {
513 let (tokens, diags) = lex(src, 0);
514 assert!(diags.is_empty(), "unexpected diagnostics: {diags:?}");
515 tokens.into_iter().map(|t| t.tok).collect()
516 }
517
518 fn errors(src: &str) -> Vec<String> {
519 lex(src, 0).1.into_iter().map(|d| d.message).collect()
520 }
521
522 #[test]
523 fn numbers_percentages_and_dice() {
524 assert_eq!(
525 toks("42 1_000 3.5 2.5e-3 1e-12 30% 12.5% d6 2d6 10d10"),
526 vec![
527 Tok::Int(42.into()),
528 Tok::Int(1000.into()),
529 Tok::Float(3.5),
530 Tok::Float(2.5e-3),
531 Tok::Float(1e-12),
532 Tok::Percent(0.3),
533 Tok::Percent(0.125),
534 Tok::Dice { count: 1, sides: 6 },
535 Tok::Dice { count: 2, sides: 6 },
536 Tok::Dice { count: 10, sides: 10 },
537 Tok::Eof,
538 ]
539 );
540 }
541
542 #[test]
543 fn ranges_are_not_floats() {
544 assert_eq!(
545 toks("1..6 0..<n"),
546 vec![
547 Tok::Int(1.into()),
548 Tok::DotDot,
549 Tok::Int(6.into()),
550 Tok::Int(0.into()),
551 Tok::DotDotLt,
552 Tok::Ident("n".into()),
553 Tok::Eof
554 ]
555 );
556 }
557
558 #[test]
559 fn binary_and_hexadecimal_integers() {
560 assert_eq!(
561 toks("0b111 0B10_01 0xfab101 0XFA_B101 0xdead_beef 0x1e3 0xd6"),
562 vec![
563 Tok::Int(7.into()),
564 Tok::Int(9.into()),
565 Tok::Int(0xfab101.into()),
566 Tok::Int(0xfab101.into()),
567 Tok::Int(0xdead_beefu64.into()),
568 Tok::Int(0x1e3.into()),
569 Tok::Int(0xd6.into()),
570 Tok::Eof
571 ]
572 );
573 assert_eq!(
574 toks("0b1..0xF 0x0..<0B10 -0xff 0x1.bit_length()"),
575 vec![
576 Tok::Int(1.into()),
577 Tok::DotDot,
578 Tok::Int(15.into()),
579 Tok::Int(0.into()),
580 Tok::DotDotLt,
581 Tok::Int(2.into()),
582 Tok::Minus,
583 Tok::Int(255.into()),
584 Tok::Int(1.into()),
585 Tok::Dot,
586 Tok::Ident("bit_length".into()),
587 Tok::LParen,
588 Tok::RParen,
589 Tok::Eof
590 ]
591 );
592 for src in [
593 "0x", "0b", "0X_1", "0b_1", "0b2", "0b102", "0b1d6", "0xfg", "0xf_", "0b1__0", "0x1p4",
594 ] {
595 let (tokens, diags) = lex(src, 40);
596 assert_eq!(diags.len(), 1, "{src}: {diags:?}");
597 assert!(diags[0].message.contains("integer literal"), "{src}");
598 assert_eq!(diags[0].span, Span::new(0, src.len()).shifted(40));
599 assert_eq!(tokens.len(), 1, "{src}: {tokens:?}");
601 }
602 }
603
604 #[test]
605 fn names_that_look_like_dice() {
606 assert_eq!(
607 toks("d6x dx d _d6"),
608 vec![
609 Tok::Ident("d6x".into()),
610 Tok::Ident("dx".into()),
611 Tok::Ident("d".into()),
612 Tok::Ident("_d6".into()),
613 Tok::Eof
614 ]
615 );
616 }
617
618 #[test]
619 fn keywords_and_contextual_words() {
620 assert_eq!(
621 toks("let x ~ 5 to 10"),
622 vec![
623 Tok::Let,
624 Tok::Ident("x".into()),
625 Tok::Tilde,
626 Tok::Int(5.into()),
627 Tok::Ident("to".into()),
628 Tok::Int(10.into()),
629 Tok::Eof
630 ]
631 );
632 }
633
634 #[test]
635 fn strings_with_interpolation() {
636 assert_eq!(
637 toks(r#""hp: {h + 1}!" "a\{b\}" """#),
638 vec![
639 Tok::Str(vec![
640 StrPart::Lit("hp: ".into()),
641 StrPart::Expr {
642 src: "h + 1".into(),
643 offset: 6
644 },
645 StrPart::Lit("!".into()),
646 ]),
647 Tok::Str(vec![StrPart::Lit("a{b}".into())]),
648 Tok::Str(vec![StrPart::Lit(String::new())]),
649 Tok::Eof,
650 ]
651 );
652 }
653
654 #[test]
655 fn comments_are_skipped() {
656 assert_eq!(
657 toks("a # comment\nb"),
658 vec![Tok::Ident("a".into()), Tok::Newline, Tok::Ident("b".into()), Tok::Eof]
659 );
660 }
661
662 #[test]
663 fn line_breaks_inside_brackets_and_after_operators_are_dropped() {
664 assert_eq!(
665 toks("f(1,\n2)\nx = a +\n b\n\n[1\n]"),
666 vec![
667 Tok::Ident("f".into()),
668 Tok::LParen,
669 Tok::Int(1.into()),
670 Tok::Comma,
671 Tok::Int(2.into()),
672 Tok::RParen,
673 Tok::Newline,
674 Tok::Ident("x".into()),
675 Tok::Assign,
676 Tok::Ident("a".into()),
677 Tok::Plus,
678 Tok::Ident("b".into()),
679 Tok::Newline,
680 Tok::LBracket,
681 Tok::Int(1.into()),
682 Tok::RBracket,
683 Tok::Eof,
684 ]
685 );
686 }
687
688 #[test]
689 fn line_breaks_inside_blocks_nested_in_parens_are_kept() {
690 assert_eq!(
691 toks("f({\na\nb\n})"),
692 vec![
693 Tok::Ident("f".into()),
694 Tok::LParen,
695 Tok::LBrace,
696 Tok::Ident("a".into()),
697 Tok::Newline,
698 Tok::Ident("b".into()),
699 Tok::Newline,
700 Tok::RBrace,
701 Tok::RParen,
702 Tok::Eof,
703 ]
704 );
705 }
706
707 #[test]
708 fn line_breaks_before_method_chains_are_dropped() {
709 assert_eq!(
710 toks("xs\n.len()"),
711 vec![
712 Tok::Ident("xs".into()),
713 Tok::Dot,
714 Tok::Ident("len".into()),
715 Tok::LParen,
716 Tok::RParen,
717 Tok::Eof,
718 ]
719 );
720 }
721
722 #[test]
723 fn helpful_errors() {
724 assert_eq!(errors("a % b"), vec!["unexpected `%`"]);
725 assert_eq!(errors("a && b"), vec!["unexpected `&&`"]);
726 assert_eq!(errors("\"abc"), vec!["unterminated string"]);
727 assert_eq!(errors("2d6x"), vec!["invalid dice literal"]);
728 assert_eq!(errors("0d6"), vec!["a dice roll needs at least one die"]);
729 assert!(errors("9999999999999999999").is_empty());
730 assert_eq!(
731 errors(&"9".repeat(20_000)),
732 vec!["integer size exceeds the limit of 65536 bits"]
733 );
734 }
735}