scheme_edit/
lexer.rs

1use crate::cst::ListKind;
2
3#[derive(Debug, Clone, PartialEq, Eq)]
4pub enum TokenKind {
5    Open(ListKind),
6    Close(char),
7    Atom,
8    Str,
9    Prefix,
10    Ws,
11    LineComment,
12    BlockComment,
13    DatumCommentStart,
14}
15
16#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct Token {
18    pub kind: TokenKind,
19    pub text: String,
20    pub line: u32,
21    pub col: u32,
22}
23
24#[derive(Debug, Clone, PartialEq, Eq)]
25pub struct ParseError {
26    pub message: String,
27    pub line: u32,
28    pub col: u32,
29}
30
31impl std::fmt::Display for ParseError {
32    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
33        write!(f, "{}:{}: {}", self.line, self.col, self.message)
34    }
35}
36
37impl std::error::Error for ParseError {}
38
39pub struct Lexer {
40    chars: Vec<char>,
41    pos: usize,
42    line: u32,
43    col: u32,
44}
45
46/// Characters that terminate an atom (matching guile's reader).
47fn is_delimiter(c: char) -> bool {
48    c.is_whitespace() || matches!(c, '(' | ')' | '[' | ']' | '"' | ';')
49}
50
51const UNIFORM_TAGS: &[&str] = &[
52    "u8", "u16", "u32", "u64", "s8", "s16", "s32", "s64", "f32", "f64", "c32", "c64", "vu8",
53];
54
55/// A `#<tag>(` opener is a tagged vector iff the tag is a uniform/bytevector
56/// tag or starts with an ASCII digit (array rank).
57fn is_valid_vector_tag(tag: &str) -> bool {
58    !tag.is_empty()
59        && (UNIFORM_TAGS.contains(&tag) || tag.starts_with(|c: char| c.is_ascii_digit()))
60}
61
62impl Lexer {
63    pub fn new(src: &str) -> Self {
64        Lexer {
65            chars: src.chars().collect(),
66            pos: 0,
67            line: 1,
68            col: 1,
69        }
70    }
71
72    fn peek(&self, ahead: usize) -> Option<char> {
73        self.chars.get(self.pos + ahead).copied()
74    }
75
76    fn bump(&mut self) -> char {
77        let c = self.chars[self.pos];
78        self.pos += 1;
79        if c == '\n' {
80            self.line += 1;
81            self.col = 1;
82        } else {
83            self.col += 1;
84        }
85        c
86    }
87
88    fn error(&self, message: &str, line: u32, col: u32) -> ParseError {
89        ParseError {
90            message: message.to_string(),
91            line,
92            col,
93        }
94    }
95
96    pub fn next_token(&mut self) -> Result<Option<Token>, ParseError> {
97        let (line, col) = (self.line, self.col);
98        let Some(c) = self.peek(0) else {
99            return Ok(None);
100        };
101        let (kind, text) = match c {
102            _ if c.is_whitespace() => {
103                let mut text = String::new();
104                while self.peek(0).is_some_and(char::is_whitespace) {
105                    text.push(self.bump());
106                }
107                (TokenKind::Ws, text)
108            }
109            ';' => {
110                let mut text = String::new();
111                while self.peek(0).is_some_and(|c| c != '\n') {
112                    text.push(self.bump());
113                }
114                (TokenKind::LineComment, text)
115            }
116            '(' => (TokenKind::Open(ListKind::Paren), self.bump().to_string()),
117            '[' => (TokenKind::Open(ListKind::Bracket), self.bump().to_string()),
118            ')' | ']' => (TokenKind::Close(c), self.bump().to_string()),
119            '\'' | '`' => (TokenKind::Prefix, self.bump().to_string()),
120            ',' => {
121                let mut text = self.bump().to_string();
122                if self.peek(0) == Some('@') {
123                    text.push(self.bump());
124                }
125                (TokenKind::Prefix, text)
126            }
127            '"' => (TokenKind::Str, self.lex_string(line, col)?),
128            '#' => return self.lex_hash(line, col).map(Some),
129            _ => (TokenKind::Atom, self.lex_atom()),
130        };
131        Ok(Some(Token {
132            kind,
133            text,
134            line,
135            col,
136        }))
137    }
138
139    fn lex_string(&mut self, line: u32, col: u32) -> Result<String, ParseError> {
140        let mut text = self.bump().to_string();
141        loop {
142            match self.peek(0) {
143                None => return Err(self.error("unterminated string", line, col)),
144                Some('\\') => {
145                    text.push(self.bump());
146                    if self.peek(0).is_some() {
147                        text.push(self.bump());
148                    }
149                }
150                Some('"') => {
151                    text.push(self.bump());
152                    return Ok(text);
153                }
154                Some(_) => text.push(self.bump()),
155            }
156        }
157    }
158
159    fn lex_hash(&mut self, line: u32, col: u32) -> Result<Token, ParseError> {
160        let (kind, text) = match self.peek(1) {
161            Some('|') => (TokenKind::BlockComment, self.lex_block_comment(line, col)?),
162            Some(';') => {
163                let text: String = [self.bump(), self.bump()].iter().collect();
164                (TokenKind::DatumCommentStart, text)
165            }
166            Some('(') => {
167                let text: String = [self.bump(), self.bump()].iter().collect();
168                (TokenKind::Open(ListKind::Vector), text)
169            }
170            Some('\\') => {
171                let mut text: String = [self.bump(), self.bump()].iter().collect();
172                if self.peek(0).is_none() {
173                    return Err(self.error("unterminated character literal", line, col));
174                }
175                text.push(self.bump());
176                while self.peek(0).is_some_and(|c| c.is_ascii_alphanumeric()) {
177                    text.push(self.bump());
178                }
179                (TokenKind::Atom, text)
180            }
181            Some('\'') | Some('`') | Some('~') | Some('+') => {
182                let text: String = [self.bump(), self.bump()].iter().collect();
183                (TokenKind::Prefix, text)
184            }
185            Some(',') | Some('$') => {
186                let mut text: String = [self.bump(), self.bump()].iter().collect();
187                if self.peek(0) == Some('@') {
188                    text.push(self.bump());
189                }
190                (TokenKind::Prefix, text)
191            }
192            Some('{') => (TokenKind::Atom, self.lex_extended_symbol(line, col)?),
193            Some('!') => (TokenKind::BlockComment, self.lex_scsh_comment(line, col)?),
194            _ => match self.try_lex_tagged_vector() {
195                Some(opener) => (
196                    TokenKind::Open(ListKind::TaggedVector(opener.clone())),
197                    opener,
198                ),
199                None => (TokenKind::Atom, self.lex_atom()),
200            },
201        };
202        Ok(Token {
203            kind,
204            text,
205            line,
206            col,
207        })
208    }
209
210    fn lex_block_comment(&mut self, line: u32, col: u32) -> Result<String, ParseError> {
211        let mut text: String = [self.bump(), self.bump()].iter().collect();
212        let mut depth = 1usize;
213        while depth > 0 {
214            match (self.peek(0), self.peek(1)) {
215                (Some('#'), Some('|')) => {
216                    text.push(self.bump());
217                    text.push(self.bump());
218                    depth += 1;
219                }
220                (Some('|'), Some('#')) => {
221                    text.push(self.bump());
222                    text.push(self.bump());
223                    depth -= 1;
224                }
225                (Some(_), _) => text.push(self.bump()),
226                (None, _) => return Err(self.error("unterminated block comment", line, col)),
227            }
228        }
229        Ok(text)
230    }
231
232    /// `#{...}#` extended symbol; `}` terminates only when followed by `#`,
233    /// and `\` escapes the next char verbatim so `\}` does not terminate.
234    fn lex_extended_symbol(&mut self, line: u32, col: u32) -> Result<String, ParseError> {
235        let mut text: String = [self.bump(), self.bump()].iter().collect();
236        loop {
237            match self.peek(0) {
238                None => return Err(self.error("unterminated `#{...}#` symbol", line, col)),
239                Some('\\') => {
240                    text.push(self.bump());
241                    if self.peek(0).is_some() {
242                        text.push(self.bump());
243                    }
244                }
245                Some('}') if self.peek(1) == Some('#') => {
246                    text.push(self.bump());
247                    text.push(self.bump());
248                    return Ok(text);
249                }
250                Some(_) => text.push(self.bump()),
251            }
252        }
253    }
254
255    /// `#!...!#` shebang / SCSH block comment; always a comment in guile.
256    fn lex_scsh_comment(&mut self, line: u32, col: u32) -> Result<String, ParseError> {
257        let mut text: String = [self.bump(), self.bump()].iter().collect();
258        loop {
259            match self.peek(0) {
260                None => return Err(self.error("unterminated `#! ... !#` comment", line, col)),
261                Some('!') if self.peek(1) == Some('#') => {
262                    text.push(self.bump());
263                    text.push(self.bump());
264                    return Ok(text);
265                }
266                Some(_) => text.push(self.bump()),
267            }
268        }
269    }
270
271    /// If `#<tag>(` at the cursor is a tagged vector, consume it and return the
272    /// opener; otherwise consume nothing and return None.
273    fn try_lex_tagged_vector(&mut self) -> Option<String> {
274        let mut len = 0usize;
275        while len < 32 {
276            match self.peek(1 + len) {
277                Some(c) if c.is_ascii_alphanumeric() || matches!(c, '@' | ':' | '-') => len += 1,
278                _ => break,
279            }
280        }
281        let tag: String = (0..len).filter_map(|i| self.peek(1 + i)).collect();
282        if self.peek(1 + len) != Some('(') || !is_valid_vector_tag(&tag) {
283            return None;
284        }
285        let mut opener = self.bump().to_string();
286        for _ in 0..=len {
287            opener.push(self.bump());
288        }
289        Some(opener)
290    }
291
292    fn lex_atom(&mut self) -> String {
293        let mut text = String::new();
294        while self.peek(0).is_some_and(|c| !is_delimiter(c)) {
295            text.push(self.bump());
296        }
297        text
298    }
299}
300
301#[cfg(test)]
302mod tests {
303    use super::*;
304    use crate::cst::ListKind;
305
306    fn kinds(src: &str) -> Vec<(TokenKind, String)> {
307        let mut lx = Lexer::new(src);
308        let mut out = Vec::new();
309        while let Some(t) = lx.next_token().unwrap() {
310            out.push((t.kind, t.text));
311        }
312        out
313    }
314
315    #[test]
316    fn lexes_atoms_strings_ws() {
317        assert_eq!(
318            kinds("(name 'guix)"),
319            vec![
320                (TokenKind::Open(ListKind::Paren), "(".into()),
321                (TokenKind::Atom, "name".into()),
322                (TokenKind::Ws, " ".into()),
323                (TokenKind::Prefix, "'".into()),
324                (TokenKind::Atom, "guix".into()),
325                (TokenKind::Close(')'), ")".into()),
326            ]
327        );
328    }
329
330    #[test]
331    fn string_raw_with_escapes() {
332        let ks = kinds(r#""a\"b\\c""#);
333        assert_eq!(ks, vec![(TokenKind::Str, r#""a\"b\\c""#.into())]);
334    }
335
336    #[test]
337    fn line_comment_excludes_newline() {
338        let ks = kinds(";; hi\n(x)");
339        assert_eq!(ks[0], (TokenKind::LineComment, ";; hi".into()));
340        assert_eq!(ks[1], (TokenKind::Ws, "\n".into()));
341    }
342
343    #[test]
344    fn nested_block_comment() {
345        let ks = kinds("#| a #| b |# c |#x");
346        assert_eq!(ks[0], (TokenKind::BlockComment, "#| a #| b |# c |#".into()));
347        assert_eq!(ks[1], (TokenKind::Atom, "x".into()));
348    }
349
350    #[test]
351    fn hash_forms() {
352        assert_eq!(kinds("#t")[0], (TokenKind::Atom, "#t".into()));
353        assert_eq!(
354            kinds("#:use-module")[0],
355            (TokenKind::Atom, "#:use-module".into())
356        );
357        assert_eq!(kinds(r"#\(")[0], (TokenKind::Atom, r"#\(".into()));
358        assert_eq!(kinds(r"#\space")[0], (TokenKind::Atom, r"#\space".into()));
359        assert_eq!(
360            kinds("#(1)")[0],
361            (TokenKind::Open(ListKind::Vector), "#(".into())
362        );
363        assert_eq!(kinds("#;")[0], (TokenKind::DatumCommentStart, "#;".into()));
364    }
365
366    #[test]
367    fn gexp_prefixes() {
368        for p in [
369            "'", "`", ",", ",@", "#'", "#`", "#,", "#,@", "#~", "#$", "#$@", "#+",
370        ] {
371            let src = format!("{p}x");
372            let ks = kinds(&src);
373            assert_eq!(ks[0], (TokenKind::Prefix, p.to_string()), "prefix {p}");
374        }
375    }
376
377    #[test]
378    fn extended_symbol() {
379        assert_eq!(kinds("#{a b}#")[0], (TokenKind::Atom, "#{a b}#".into()));
380        assert_eq!(
381            kinds(r"#{foo\}bar}#")[0],
382            (TokenKind::Atom, r"#{foo\}bar}#".into())
383        );
384    }
385
386    #[test]
387    fn unterminated_extended_symbol_errors() {
388        let mut lx = Lexer::new("#{a b");
389        assert!(lx.next_token().is_err());
390    }
391
392    #[test]
393    fn scsh_block_comment() {
394        assert_eq!(
395            kinds("#! /bin/sh !#")[0],
396            (TokenKind::BlockComment, "#! /bin/sh !#".into())
397        );
398        let multi = "#!\nfoo bar\n!#";
399        assert_eq!(kinds(multi)[0], (TokenKind::BlockComment, multi.into()));
400    }
401
402    #[test]
403    fn unterminated_scsh_comment_errors() {
404        let mut lx = Lexer::new("#!x");
405        assert!(lx.next_token().is_err());
406    }
407
408    #[test]
409    fn tagged_vectors() {
410        assert_eq!(
411            kinds("#vu8(1 2 3)")[0],
412            (
413                TokenKind::Open(ListKind::TaggedVector("#vu8(".into())),
414                "#vu8(".into()
415            )
416        );
417        assert_eq!(
418            kinds("#u8(1 2)")[0],
419            (
420                TokenKind::Open(ListKind::TaggedVector("#u8(".into())),
421                "#u8(".into()
422            )
423        );
424        assert_eq!(
425            kinds("#f32(1.0 2.0)")[0],
426            (
427                TokenKind::Open(ListKind::TaggedVector("#f32(".into())),
428                "#f32(".into()
429            )
430        );
431        assert_eq!(
432            kinds("#2((1 2)(3 4))")[0],
433            (
434                TokenKind::Open(ListKind::TaggedVector("#2(".into())),
435                "#2(".into()
436            )
437        );
438    }
439
440    #[test]
441    fn hash_regression_guards() {
442        assert_eq!(kinds("#f")[0], (TokenKind::Atom, "#f".into()));
443        let ks = kinds("#f (x)");
444        assert_eq!(ks[0], (TokenKind::Atom, "#f".into()));
445        assert_eq!(ks[1], (TokenKind::Ws, " ".into()));
446        assert_eq!(ks[2], (TokenKind::Open(ListKind::Paren), "(".into()));
447        assert_eq!(kinds("#t")[0], (TokenKind::Atom, "#t".into()));
448        assert_eq!(kinds("#:kw")[0], (TokenKind::Atom, "#:kw".into()));
449        assert_eq!(kinds(r"#\x41")[0], (TokenKind::Atom, r"#\x41".into()));
450        assert_eq!(kinds("#*10101")[0], (TokenKind::Atom, "#*10101".into()));
451        assert_eq!(
452            kinds("#(1)")[0],
453            (TokenKind::Open(ListKind::Vector), "#(".into())
454        );
455    }
456
457    #[test]
458    fn unterminated_string_errors_with_position() {
459        let mut lx = Lexer::new("(x \"abc");
460        lx.next_token().unwrap();
461        lx.next_token().unwrap();
462        lx.next_token().unwrap();
463        let err = lx.next_token().unwrap_err();
464        assert_eq!(err.line, 1);
465    }
466}
scheme_edit/lexer.rs

scheme_edit/
lexer.rs
