boxworks/lang/
lexer.rs

1//! Lexer and tokens for Box language.
2
3use super::Error;
4use super::Str;
5use std::{borrow::Cow, rc::Rc};
6
7/// Box language lexer.
8pub struct Lexer<'a> {
9    /// The full source file being lexed.
10    s: &'a str,
11    /// Inclusive lower bound on the part of the file being lexed by this lexer.
12    l: usize,
13    /// Exclusive upper bound on the part of the file being lexed by this lexer.
14    u: usize,
15    /// Opening parens.
16    op: Rc<[Option<ClosingParen>]>,
17    /// Index of the next opening paren that is expected.
18    op_i: usize,
19    /// Error accumulator.
20    errs: super::ErrorAccumulator<'a>,
21}
22
23/// Opaque marker of a closing parenthesis.
24#[derive(Clone, Copy, Debug, PartialEq)]
25pub struct ClosingParen {
26    /// Index of the closing parenthesis in the source.
27    /// Because this closing paren matches an opening paren,
28    /// it cannot come at the start of the file and thus the index
29    /// is strictly bigger than 0.
30    source_idx: std::num::NonZeroUsize,
31    /// Starting index of parens after this closing paren in the parens array.
32    op_i: usize,
33}
34
35impl ClosingParen {
36    fn str<'a>(&self, source: &'a str) -> Str<'a> {
37        Str {
38            value: source,
39            start: self.source_idx.get(),
40            end: self.source_idx.get() + 1,
41        }
42    }
43}
44
45impl<'a> Lexer<'a> {
46    /// Create a new Box language lexer.
47    pub fn new(source: &'a str, errs: super::ErrorAccumulator<'a>) -> Self {
48        Self {
49            s: source,
50            l: 0,
51            u: source.len(),
52            op: Self::build(source),
53            op_i: 0,
54            errs,
55        }
56    }
57
58    /// Splits off a nested lexer.
59    pub fn split_nested(&mut self, closing_paren: Option<ClosingParen>) -> Self {
60        let inner = Self {
61            s: self.s,
62            l: self.l,
63            u: match closing_paren {
64                Some(c) => c.source_idx.get(),
65                None => self.u,
66            },
67            op: self.op.clone(),
68            op_i: self.op_i,
69            errs: self.errs.clone(),
70        };
71        (self.l, self.op_i) = match closing_paren {
72            Some(c) => (c.source_idx.get() + 1, c.op_i),
73            None => (self.u, self.op.len()),
74        };
75        inner
76    }
77
78    pub fn remaining_source(&self) -> Str<'a> {
79        Str {
80            value: self.s,
81            start: self.l,
82            end: self.u,
83        }
84    }
85    fn build(source: &'a str) -> Rc<[Option<ClosingParen>]> {
86        #[derive(Clone, Copy)]
87        enum State {
88            Regular,
89            Comment,
90            /// In a string.
91            String,
92            /// In a string after the escape character \
93            StringEscaped,
94        }
95        struct Stack {
96            i: usize,
97        }
98        let mut v: Vec<Option<ClosingParen>> = vec![];
99        let mut stack = vec![];
100        let mut state = State::Regular;
101        let mut i = 0;
102        for c in source.chars() {
103            match (c, state) {
104                ('(' | '[', State::Regular) => {
105                    stack.push(Stack { i: v.len() });
106                    v.push(None);
107                }
108                (')' | ']', State::Regular) => {
109                    if let Some(s) = stack.pop() {
110                        v[s.i] = Some(ClosingParen {
111                            source_idx: i.try_into().expect("i>0 because this character is preceded by a [ or ( that pushed to the stack"),
112                            op_i: v.len(),
113                        });
114                    }
115                }
116                ('\n', State::Comment) => {
117                    state = State::Regular;
118                }
119                ('#', State::Regular) => {
120                    state = State::Comment;
121                }
122                ('"', State::Regular) => {
123                    state = State::String;
124                }
125                ('"', State::String) => {
126                    state = State::Regular;
127                }
128                ('\\', State::String) => {
129                    state = State::StringEscaped;
130                }
131                (_, State::StringEscaped) => {
132                    state = State::String;
133                }
134                (_, State::Regular | State::Comment | State::String) => {}
135            }
136            i += c.len_utf8();
137        }
138        v.into()
139    }
140}
141
142/// A token in the Box language.
143#[derive(Clone, Debug)]
144pub struct Token<'a> {
145    pub value: TokenValue<'a>,
146    pub source: Str<'a>,
147}
148
149/// Value of a token in the Box language.
150#[derive(Clone, Debug, PartialEq)]
151pub enum TokenValue<'a> {
152    SquareOpen {
153        /// The closing bracket that matches this opening bracket.
154        ///
155        /// If `None`, this opening bracket is not matched.
156        /// If provided, the closing bracket may be either `)` or `]`.
157        closing: Option<ClosingParen>,
158    },
159    SquareClose,
160    /// Opening round bracket `(`.
161    RoundOpen {
162        /// The closing bracket that matches this opening bracket.
163        ///
164        /// If `None`, this opening bracket is not matched.
165        /// If provided, the closing bracket may be either `)` or `]`.
166        closing: Option<ClosingParen>,
167    },
168    RoundClose,
169    Comma,
170    Equal,
171    Keyword,
172    String(Cow<'a, str>),
173    Integer(i32),
174    Scaled(common::Scaled),
175    InfiniteGlue(common::Scaled, common::GlueOrder),
176    Comment,
177}
178
179impl<'a> Iterator for Lexer<'a> {
180    type Item = Token<'a>;
181
182    fn next(&mut self) -> Option<Token<'a>> {
183        // Consume whitespace and comments
184        let mut comment_start: Option<usize> = None;
185        while let Some(c) = self.s[self.l..self.u].chars().next() {
186            let should_skip = match c {
187                '\n' => {
188                    if let Some(comment_start) = comment_start.take() {
189                        return Some(Token {
190                            value: TokenValue::Comment,
191                            source: Str {
192                                value: self.s,
193                                start: comment_start,
194                                end: self.l,
195                            },
196                        });
197                    }
198                    true
199                }
200                '#' => {
201                    if comment_start.is_none() {
202                        comment_start = Some(self.l + 1);
203                    }
204                    true
205                }
206                c => comment_start.is_some() || c.is_whitespace(),
207            };
208            if !should_skip {
209                break;
210            }
211            self.l += c.len_utf8();
212        }
213        // Now look at the token
214        let mut iter = self.s[self.l..self.u].chars();
215        let c = iter.next()?;
216        let start = self.l;
217        self.l += c.len_utf8();
218        use TokenValue::*;
219        let value = match c {
220            '[' | '(' => {
221                let closing = self.op.get(self.op_i).cloned().flatten();
222                let open = Str {
223                    value: self.s,
224                    start,
225                    end: start + 1,
226                };
227                match &closing {
228                    Some(closing) => {
229                        let close = closing.str(self.s);
230                        let want = if c == '[' { "]" } else { ")" };
231                        if close.str() != want {
232                            self.errs.add(Error::MismatchedBraces { open, close });
233                        }
234                    }
235                    None => {
236                        self.errs.add(Error::UnmatchedOpeningBracket { open });
237                    }
238                };
239                self.op_i += 1;
240                if c == '[' {
241                    SquareOpen { closing }
242                } else {
243                    RoundOpen { closing }
244                }
245            }
246            ']' => SquareClose,
247            ')' => RoundClose,
248            '=' => Equal,
249            ',' => Comma,
250            'a'..='z' | 'A'..='Z' => {
251                while let Some(n @ 'a'..='z' | n @ 'A'..='Z' | n @ '_') = iter.next() {
252                    self.l += n.len_utf8();
253                }
254                Keyword
255            }
256            '"' => {
257                // TODO: only allocate a buffer if we're going to use it
258                let mut buf: std::string::String = Default::default();
259                loop {
260                    let Some(n) = iter.next() else {
261                        // TODO: error in this case?
262                        return None;
263                    };
264                    self.l += n.len_utf8();
265                    let c: char = match n {
266                        '"' => {
267                            break;
268                        }
269                        // Escape character
270                        //
271                        // We support a subset of Rust escape characters, which are documented
272                        // here: https://doc.rust-lang.org/reference/expressions/literal-expr.html.
273                        '\\' => {
274                            let Some(n) = iter.next() else {
275                                // TODO: error in this case?
276                                return None;
277                            };
278                            self.l += n.len_utf8();
279                            match n {
280                                '\"' | '\'' | '\\' => n,
281                                'n' => '\n',
282                                't' => '\t',
283                                '0' => '\0',
284                                'r' => '\r',
285                                'u' => {
286                                    if iter.next() != Some('{') {
287                                        // TODO error
288                                        continue;
289                                    }
290                                    self.l += '{'.len_utf8();
291                                    let mut i = 0;
292                                    let mut valid = true;
293                                    loop {
294                                        let Some(n) = iter.next() else {
295                                            // TODO: error in this case?
296                                            return None;
297                                        };
298                                        self.l += n.len_utf8();
299                                        if n == '}' {
300                                            // TODO: error if no number was provided.
301                                            break;
302                                        }
303                                        match n.to_digit(16) {
304                                            None => {
305                                                valid = false;
306                                            }
307                                            Some(d) => {
308                                                i = i * 16 + d;
309                                            }
310                                        }
311                                    }
312                                    if !valid {
313                                        // TODO: error
314                                        continue;
315                                    }
316                                    let Some(c) = char::from_u32(i) else {
317                                        // TODO: error
318                                        continue;
319                                    };
320                                    c
321                                }
322                                _ => {
323                                    self.errs.add(Error::UnknownEscapeSequence {
324                                        sequence: Str {
325                                            value: self.s,
326                                            start: self.l - n.len_utf8() - 1,
327                                            end: self.l,
328                                        },
329                                    });
330                                    continue;
331                                }
332                            }
333                        }
334                        _ => n,
335                    };
336                    buf.push(c);
337                }
338                // If the string is exactly in this source (e.g. no special control sequences)
339                // then we can avoid an allocation.
340                let source = &self.s[start + 1..self.l - 1];
341                String(if buf.len() == source.len() {
342                    Cow::Borrowed(source)
343                } else {
344                    Cow::Owned(buf)
345                })
346            }
347            '0'..='9' => {
348                let initial_value = (c as i32) - ('0' as i32);
349                self.parse_number(false, initial_value, start)
350            }
351            '-' => self.parse_number(true, 0, start),
352            _ => {
353                self.errs.add(Error::InvalidCharacter {
354                    char: Str {
355                        value: self.s,
356                        start,
357                        end: self.l,
358                    },
359                });
360                return self.next();
361            }
362        };
363        Some(Token {
364            value,
365            source: Str {
366                value: self.s,
367                start,
368                end: self.l,
369            },
370        })
371    }
372}
373
374impl<'a> Lexer<'a> {
375    fn parse_number(
376        &mut self,
377        negative: bool,
378        initial_value: i32,
379        start_idx: usize,
380    ) -> TokenValue<'a> {
381        let mut iter = self.s[self.l..self.u].chars();
382        let mut n = initial_value;
383        let mut parsing_n = true;
384        let mut d = [0_u8; 17];
385        let mut next_d = 0_usize;
386        loop {
387            match iter.next() {
388                Some(c @ '0'..='9') => {
389                    let i = (c as i32) - ('0' as i32);
390                    if parsing_n {
391                        n = n.checked_mul(10).unwrap();
392                        n = n.checked_add(i).unwrap();
393                    } else {
394                        if let Some(d) = d.get_mut(next_d) {
395                            *d = i.try_into().expect("i in [0,9]")
396                        }
397                        next_d += 1;
398                    }
399                    self.l += c.len_utf8();
400                }
401                Some(d @ '.') => {
402                    if !parsing_n {
403                        self.errs.add(Error::MultipleDecimalPoints {
404                            point: Str {
405                                value: self.s,
406                                start: self.l,
407                                end: self.l + d.len_utf8(),
408                            },
409                        });
410                    }
411                    parsing_n = false;
412                    self.l += d.len_utf8();
413                }
414                Some(c @ 'a'..='z' | c @ 'A'..='Z') => {
415                    let u = self.l;
416                    self.l += c.len_utf8();
417                    while let Some(n @ 'a'..='z' | n @ 'A'..='Z' | n @ '_') = iter.next() {
418                        self.l += n.len_utf8();
419                    }
420
421                    let mut s = common::Scaled::from_decimal_digits(&d) + common::Scaled::ONE * n;
422                    if negative {
423                        s.0 *= -1;
424                    }
425                    let raw_unit = &self.s[u..self.l];
426                    if let Some(unit) = common::ScaledUnit::parse(raw_unit) {
427                        let mut s =
428                            common::Scaled::new(n, common::Scaled::from_decimal_digits(&d), unit)
429                                .unwrap();
430                        if negative {
431                            s = -s;
432                        }
433                        return TokenValue::Scaled(s);
434                    }
435                    if let Some(glue_order) = common::GlueOrder::parse(raw_unit) {
436                        return TokenValue::InfiniteGlue(s, glue_order);
437                    }
438                    self.errs.add(Error::InvalidDimensionUnit {
439                        dimension: Str {
440                            value: self.s,
441                            start: start_idx,
442                            end: self.l,
443                        },
444                        unit: Str {
445                            value: self.s,
446                            start: u,
447                            end: self.l,
448                        },
449                    });
450                    return TokenValue::Scaled(common::Scaled::ZERO);
451                }
452                d => {
453                    if !parsing_n {
454                        self.errs.add(Error::NumberWithoutUnits {
455                            number: Str {
456                                value: self.s,
457                                start: self.l,
458                                end: self.l + d.map(|c| c.len_utf8()).unwrap_or(0),
459                            },
460                        });
461                        return TokenValue::Scaled(common::Scaled::ZERO);
462                    }
463                    if negative {
464                        n *= -1;
465                    }
466                    return TokenValue::Integer(n);
467                }
468            }
469        }
470    }
471}
472
473#[cfg(test)]
474mod tests {
475    use super::super::ErrorAccumulator;
476
477    use super::*;
478    fn run_lexer_test(input: &str, want: Vec<TokenValue>) {
479        let errs: ErrorAccumulator = Default::default();
480        let lexer = Lexer::new(&input, errs);
481
482        let got: Vec<TokenValue> = lexer.into_iter().map(|t| t.value).collect();
483
484        assert_eq!(got, want);
485    }
486
487    macro_rules! lexer_tests {
488        ( $( ($name: ident, $input: expr, $want: expr, ), )+ ) => {
489            $(
490                #[test]
491                fn $name() {
492                    let input = $input;
493                    let want = $want;
494                    run_lexer_test(input, want);
495                }
496            )+
497        };
498    }
499
500    lexer_tests!(
501        (
502            string_simple,
503            r#" "string" "#,
504            vec![TokenValue::String("string".into())],
505        ),
506        (
507            string_with_special_char_1,
508            r#" "\"" "#,
509            vec![TokenValue::String("\"".into())],
510        ),
511        (
512            string_with_special_char_2,
513            r#" "\\" "#,
514            vec![TokenValue::String("\\".into())],
515        ),
516        (
517            string_with_invalid_special_char,
518            r#" "\a" "#,
519            vec![TokenValue::String("".into())],
520        ),
521        (
522            string_with_unicode,
523            r#" "\u{100}", "second" "#,
524            vec![
525                TokenValue::String("\u{100}".into()),
526                TokenValue::Comma,
527                TokenValue::String("second".into()),
528            ],
529        ),
530    );
531}
boxworks/lang/lexer.rs

boxworks/lang/
lexer.rs
