somni_parser/
parser.rs

1//! Grammar parser.
2//!
3//! This module parses the following grammar (minus comments, which are ignored):
4//!
5//! ```text
6//! program -> item* EOF;
7//! item -> function | global | extern_fn; // TODO types.
8//!
9//! extern_fn -> 'extern' 'fn' identifier '(' function_argument ( ',' function_argument )* ','? ')' return_decl? ;
10//! global -> 'var' identifier ':' type '=' static_initializer ';' ;
11//!
12//! static_initializer -> right_hand_expression ; // The language does not currently support function calls.
13//!
14//! function -> 'fn' identifier '(' function_argument ( ',' function_argument )* ','? ')' return_decl? body ;
15//! function_argument -> identifier ':' '&'? type ;
16//! return_decl -> '->' type ;
17//! type -> identifier ;
18//!
19//! body -> '{' statement '}' ;
20//! statement -> 'var' identifier (':' type)? '=' right_hand_expression ';' (statement)?
21//!            | 'return' right_hand_expression? ';' (statement)?
22//!            | 'break' ';' (statement)?
23//!            | 'continue' ';' (statement)?
24//!            | 'if' right_hand_expression body ( 'else' body )? (statement)?
25//!            | 'loop' body (statement)?
26//!            | 'while' right_hand_expression body (statement)?
27//!            | 'for' identifier ( ':' type )? 'in' right_hand_expression body (statement)?
28//!            | body (statement)?
29//!            | expression ';' (statement)?
30//!            | right_hand_expression // implicit return statmenet
31//!
32//! expression -> (left_hand_expression '=')? right_hand_expression ;
33//!
34//! left_hand_expression -> ( '*' )? identifier ; // Should be a valid expression, too.
35//!
36//! right_hand_expression -> binary2 ( '||' binary2 )* ;
37//! binary2 -> binary3 ( '&&' binary3 )* ;
38//! binary3 -> binary4 ( ( '<' | '<=' | '>' | '>=' | '==' | '!=' ) binary4 )* ;
39//! binary4 -> binary5 ( '|' binary5 )* ;
40//! binary5 -> binary6 ( '^' binary6 )* ;
41//! binary6 -> binary7 ( '&' binary7 )* ;
42//! binary7 -> binary8 ( ( '<<' | '>>' ) binary8 )* ;
43//! binary8 -> binary9 ( ( '+' | '-' ) binary9 )* ;
44//! binary9 -> unary ( ( '*' | '/', '%' ) unary )* ;
45//! unary -> ('!' | '-' | '&' | '*' )* primary | call ;
46//! primary -> ( literal | identifier ( '(' call_arguments ')' )? ) | '(' right_hand_expression ')' ;
47//! call_arguments -> right_hand_expression ( ',' right_hand_expression )* ','? ;
48//! literal -> NUMBER | STRING | 'true' | 'false' ;
49//! ```
50//!
51//! `NUMBER`: Non-negative integers (binary, decimal, hexadecimal) and floats.
52//! `STRING`: Double-quoted strings with escape sequences.
53
54use std::{
55    fmt::{Debug, Display},
56    num::{ParseFloatError, ParseIntError},
57    ops::ControlFlow,
58};
59
60use crate::{
61    ast::{
62        Body, Break, Continue, Else, EmptyReturn, Expression, ExternalFunction, For, Function,
63        FunctionArgument, GlobalVariable, If, Item, LeftHandExpression, Literal, LiteralValue,
64        Loop, Program, ReturnDecl, ReturnWithValue, RightHandExpression, Statement, TypeHint,
65        VariableDefinition,
66    },
67    lexer::{Token, TokenKind, Tokenizer},
68    parser::private::Sealed,
69    Error, Location,
70};
71
72mod private {
73    pub trait Sealed {}
74
75    impl Sealed for u32 {}
76    impl Sealed for u64 {}
77    impl Sealed for u128 {}
78    impl Sealed for f32 {}
79    impl Sealed for f64 {}
80}
81
82/// Parse literals into Somni integers.
83pub trait IntParser: Sized + Sealed {
84    fn parse(str: &str, radix: u32) -> Result<Self, ParseIntError>;
85}
86
87impl IntParser for u32 {
88    fn parse(str: &str, radix: u32) -> Result<Self, ParseIntError> {
89        u32::from_str_radix(str, radix)
90    }
91}
92impl IntParser for u64 {
93    fn parse(str: &str, radix: u32) -> Result<Self, ParseIntError> {
94        u64::from_str_radix(str, radix)
95    }
96}
97impl IntParser for u128 {
98    fn parse(str: &str, radix: u32) -> Result<Self, ParseIntError> {
99        u128::from_str_radix(str, radix)
100    }
101}
102
103/// Parse literals into Somni floats.
104pub trait FloatParser: Sized + Sealed {
105    fn parse(str: &str) -> Result<Self, ParseFloatError>;
106}
107
108impl FloatParser for f32 {
109    fn parse(str: &str) -> Result<Self, ParseFloatError> {
110        str.parse::<f32>()
111    }
112}
113impl FloatParser for f64 {
114    fn parse(str: &str) -> Result<Self, ParseFloatError> {
115        str.parse::<f64>()
116    }
117}
118
119/// Defines the numeric types used in the parser.
120pub trait TypeSet: Debug + Default {
121    type Integer: IntParser + Clone + Copy + PartialEq + Debug;
122    type Float: FloatParser + Clone + Copy + PartialEq + Debug;
123}
124
125/// Use 64-bit integers and 64-bit floats (default).
126#[derive(Debug, Default)]
127pub struct DefaultTypeSet;
128impl Sealed for DefaultTypeSet {}
129
130impl TypeSet for DefaultTypeSet {
131    type Integer = u64;
132    type Float = f64;
133}
134
135/// Use 32-bit integers and floats.
136#[derive(Debug, Default)]
137pub struct TypeSet32;
138impl Sealed for TypeSet32 {}
139impl TypeSet for TypeSet32 {
140    type Integer = u32;
141    type Float = f32;
142}
143
144/// Use 128-bit integers and 64-bit floats.
145#[derive(Debug, Default)]
146pub struct TypeSet128;
147impl Sealed for TypeSet128 {}
148impl TypeSet for TypeSet128 {
149    type Integer = u128;
150    type Float = f64;
151}
152
153impl<T> Program<T>
154where
155    T: TypeSet,
156{
157    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
158        let mut items = Vec::new();
159
160        while !stream.end()? {
161            items.push(Item::parse(stream)?);
162        }
163
164        Ok(Program { items })
165    }
166}
167
168impl<T> Item<T>
169where
170    T: TypeSet,
171{
172    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
173        if let Some(global_var) = GlobalVariable::try_parse(stream)? {
174            return Ok(Item::GlobalVariable(global_var));
175        }
176        if let Some(function) = ExternalFunction::try_parse(stream)? {
177            return Ok(Item::ExternFunction(function));
178        }
179        if let Some(function) = Function::try_parse(stream)? {
180            return Ok(Item::Function(function));
181        }
182
183        Err(stream.error("Expected global variable or function definition"))
184    }
185}
186
187impl<T> GlobalVariable<T>
188where
189    T: TypeSet,
190{
191    fn try_parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Option<Self>, Error> {
192        let Some(decl_token) = stream.take_match(TokenKind::Identifier, &["var"])? else {
193            return Ok(None);
194        };
195
196        let identifier = stream.expect_match(TokenKind::Identifier, &[])?;
197        let colon = stream.expect_match(TokenKind::Symbol, &[":"])?;
198        let type_token = TypeHint::parse(stream)?;
199        let equals_token = stream.expect_match(TokenKind::Symbol, &["="])?;
200        let initializer = Expression::Expression {
201            expression: RightHandExpression::parse(stream)?,
202        };
203        let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;
204
205        Ok(Some(GlobalVariable {
206            decl_token,
207            identifier,
208            colon,
209            type_token,
210            equals_token,
211            initializer,
212            semicolon,
213        }))
214    }
215}
216
217impl ExternalFunction {
218    fn try_parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Option<Self>, Error> {
219        let Some(extern_fn_token) = stream.take_match(TokenKind::Identifier, &["extern"])? else {
220            return Ok(None);
221        };
222        let Some(fn_token) = stream.take_match(TokenKind::Identifier, &["fn"])? else {
223            return Ok(None);
224        };
225
226        let name = stream.expect_match(TokenKind::Identifier, &[])?;
227        let opening_paren = stream.expect_match(TokenKind::Symbol, &["("])?;
228
229        let mut arguments = Vec::new();
230        while let Some(arg_name) = stream.take_match(TokenKind::Identifier, &[])? {
231            let colon = stream.expect_match(TokenKind::Symbol, &[":"])?;
232            let reference_token = stream.take_match(TokenKind::Symbol, &["&"])?;
233            let type_token = TypeHint::parse(stream)?;
234
235            arguments.push(FunctionArgument {
236                name: arg_name,
237                colon,
238                reference_token,
239                arg_type: type_token,
240            });
241
242            if stream.take_match(TokenKind::Symbol, &[","])?.is_none() {
243                break;
244            }
245        }
246
247        let closing_paren = stream.expect_match(TokenKind::Symbol, &[")"])?;
248
249        let return_decl =
250            if let Some(return_token) = stream.take_match(TokenKind::Symbol, &["->"])? {
251                Some(ReturnDecl {
252                    return_token,
253                    return_type: TypeHint::parse(stream)?,
254                })
255            } else {
256                None
257            };
258
259        let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;
260
261        Ok(Some(ExternalFunction {
262            extern_fn_token,
263            fn_token,
264            name,
265            opening_paren,
266            arguments,
267            closing_paren,
268            return_decl,
269            semicolon,
270        }))
271    }
272}
273
274impl<T> Function<T>
275where
276    T: TypeSet,
277{
278    fn try_parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Option<Self>, Error> {
279        let Some(fn_token) = stream.take_match(TokenKind::Identifier, &["fn"])? else {
280            return Ok(None);
281        };
282
283        let name = stream.expect_match(TokenKind::Identifier, &[])?;
284        let opening_paren = stream.expect_match(TokenKind::Symbol, &["("])?;
285
286        let mut arguments = Vec::new();
287        while let Some(arg_name) = stream.take_match(TokenKind::Identifier, &[])? {
288            let colon = stream.expect_match(TokenKind::Symbol, &[":"])?;
289            let reference_token = stream.take_match(TokenKind::Symbol, &["&"])?;
290            let type_token = TypeHint::parse(stream)?;
291
292            arguments.push(FunctionArgument {
293                name: arg_name,
294                colon,
295                reference_token,
296                arg_type: type_token,
297            });
298
299            if stream.take_match(TokenKind::Symbol, &[","])?.is_none() {
300                break;
301            }
302        }
303
304        let closing_paren = stream.expect_match(TokenKind::Symbol, &[")"])?;
305
306        let return_decl =
307            if let Some(return_token) = stream.take_match(TokenKind::Symbol, &["->"])? {
308                Some(ReturnDecl {
309                    return_token,
310                    return_type: TypeHint::parse(stream)?,
311                })
312            } else {
313                None
314            };
315
316        let body = Body::parse(stream)?;
317
318        Ok(Some(Function {
319            fn_token,
320            name,
321            opening_paren,
322            arguments,
323            closing_paren,
324            return_decl,
325            body,
326        }))
327    }
328}
329
330impl<T> Body<T>
331where
332    T: TypeSet,
333{
334    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
335        let opening_brace = stream.expect_match(TokenKind::Symbol, &["{"])?;
336
337        let mut body = Vec::new();
338        while Statement::<T>::matches(stream)? {
339            let (statement, stop) = match Statement::parse(stream)? {
340                ControlFlow::Continue(statement) => (statement, false),
341                ControlFlow::Break(statement) => (statement, true),
342            };
343            body.push(statement);
344            if stop {
345                break;
346            }
347        }
348
349        let closing_brace = stream.expect_match(TokenKind::Symbol, &["}"])?;
350
351        Ok(Body {
352            opening_brace,
353            statements: body,
354            closing_brace,
355        })
356    }
357}
358
359impl TypeHint {
360    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
361        let type_name = stream.expect_match(TokenKind::Identifier, &[])?;
362
363        Ok(TypeHint { type_name })
364    }
365}
366
367impl<T> Statement<T>
368where
369    T: TypeSet,
370{
371    fn matches(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<bool, Error> {
372        stream
373            .peek_match(TokenKind::Symbol, &["}"])
374            .map(|t| t.is_none())
375    }
376
377    fn parse(
378        stream: &mut TokenStream<'_, impl Tokenizer>,
379    ) -> Result<ControlFlow<Self, Self>, Error> {
380        if let Some(return_token) = stream.take_match(TokenKind::Identifier, &["return"])? {
381            let return_kind =
382                if let Some(semicolon) = stream.take_match(TokenKind::Symbol, &[";"])? {
383                    // Continue, parsing unreachable code is allowed
384                    Statement::EmptyReturn(EmptyReturn {
385                        return_token,
386                        semicolon,
387                    })
388                } else {
389                    let expr = RightHandExpression::parse(stream)?;
390                    let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;
391                    Statement::Return(ReturnWithValue {
392                        return_token,
393                        expression: expr,
394                        semicolon,
395                    })
396                };
397
398            // Continue, parsing unreachable code is allowed
399            return Ok(ControlFlow::Continue(return_kind));
400        }
401
402        if let Some(decl_token) = stream.take_match(TokenKind::Identifier, &["var"])? {
403            let identifier = stream.expect_match(TokenKind::Identifier, &[])?;
404
405            let type_token = if stream.take_match(TokenKind::Symbol, &[":"])?.is_some() {
406                Some(TypeHint::parse(stream)?)
407            } else {
408                None
409            };
410
411            let equals_token = stream.expect_match(TokenKind::Symbol, &["="])?;
412            let expression = RightHandExpression::parse(stream)?;
413            let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;
414
415            return Ok(ControlFlow::Continue(Statement::VariableDefinition(
416                VariableDefinition {
417                    decl_token,
418                    identifier,
419                    type_token,
420                    equals_token,
421                    initializer: expression,
422                    semicolon,
423                },
424            )));
425        }
426
427        if let Some(if_token) = stream.take_match(TokenKind::Identifier, &["if"])? {
428            let condition = RightHandExpression::parse(stream)?;
429            let body = Body::parse(stream)?;
430
431            let else_branch =
432                if let Some(else_token) = stream.take_match(TokenKind::Identifier, &["else"])? {
433                    let else_body = Body::parse(stream)?;
434
435                    Some(Else {
436                        else_token,
437                        else_body,
438                    })
439                } else {
440                    None
441                };
442
443            return Ok(ControlFlow::Continue(Statement::If(If {
444                if_token,
445                condition,
446                body,
447                else_branch,
448            })));
449        }
450
451        if let Some(loop_token) = stream.take_match(TokenKind::Identifier, &["loop"])? {
452            let body = Body::parse(stream)?;
453            return Ok(ControlFlow::Continue(Statement::Loop(Loop {
454                loop_token,
455                body,
456            })));
457        }
458
459        if let Some(while_token) = stream.take_match(TokenKind::Identifier, &["while"])? {
460            // Desugar while into loop { if condition { loop_body; } else { break; } }
461            let condition = RightHandExpression::parse(stream)?;
462            let body = Body::parse(stream)?;
463            return Ok(ControlFlow::Continue(Statement::Loop(Loop {
464                loop_token: while_token,
465                body: Body {
466                    opening_brace: body.opening_brace,
467                    closing_brace: body.closing_brace,
468                    statements: vec![Statement::If(If {
469                        if_token: while_token,
470                        condition: condition.clone(),
471                        body: body.clone(),
472                        else_branch: Some(Else {
473                            else_token: while_token,
474                            else_body: Body {
475                                opening_brace: body.opening_brace,
476                                closing_brace: body.closing_brace,
477                                statements: vec![Statement::Break(Break {
478                                    break_token: while_token,
479                                    semicolon: while_token,
480                                })],
481                            },
482                        }),
483                    })],
484                },
485            })));
486        }
487
488        if let Some(for_token) = stream.take_match(TokenKind::Identifier, &["for"])? {
489            let variable = stream.expect_match(TokenKind::Identifier, &[])?;
490            // The `: type` annotation is optional; when omitted the loop
491            // variable's type is inferred from its usage in the body.
492            let var_type = match stream.take_match(TokenKind::Symbol, &[":"])? {
493                Some(_) => Some(TypeHint::parse(stream)?),
494                None => None,
495            };
496            let in_token = stream.expect_match(TokenKind::Identifier, &["in"])?;
497            let iterable = RightHandExpression::parse(stream)?;
498            let body = Body::parse(stream)?;
499
500            return Ok(ControlFlow::Continue(Statement::For(For {
501                for_token,
502                variable,
503                var_type,
504                in_token,
505                iterable,
506                body,
507            })));
508        }
509
510        if let Some(break_token) = stream.take_match(TokenKind::Identifier, &["break"])? {
511            let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;
512            // Continue, unreachable code is allowed
513            return Ok(ControlFlow::Continue(Statement::Break(Break {
514                break_token,
515                semicolon,
516            })));
517        }
518        if let Some(continue_token) = stream.take_match(TokenKind::Identifier, &["continue"])? {
519            let semicolon = stream.expect_match(TokenKind::Symbol, &[";"])?;
520            // Continue, unreachable code is allowed
521            return Ok(ControlFlow::Continue(Statement::Continue(Continue {
522                continue_token,
523                semicolon,
524            })));
525        }
526
527        if let Ok(Some(_)) = stream.peek_match(TokenKind::Symbol, &["{"]) {
528            return Ok(ControlFlow::Continue(Statement::Scope(Body::parse(
529                stream,
530            )?)));
531        }
532
533        let save = stream.clone();
534        let expression = Expression::parse(stream)?;
535        match stream.take_match(TokenKind::Symbol, &[";"])? {
536            Some(semicolon) => Ok(ControlFlow::Continue(Statement::Expression {
537                expression,
538                semicolon,
539            })),
540            None => {
541                // No semicolon, re-parse as a right-hand expression
542                *stream = save;
543                let expression = RightHandExpression::parse(stream)?;
544
545                Ok(ControlFlow::Break(Statement::ImplicitReturn(expression)))
546            }
547        }
548    }
549}
550
551impl<T> Literal<T>
552where
553    T: TypeSet,
554{
555    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
556        let token = stream.peek_expect()?;
557
558        let token_source = stream.source(token.location);
559        let location = token.location;
560
561        let literal_value = match token.kind {
562            TokenKind::BinaryInteger => {
563                let token_source = token_source.replace("_", "");
564                Self::parse_integer_literal(&token_source[2..], 2)
565                    .map_err(|_| stream.error("Invalid binary integer literal"))?
566            }
567            TokenKind::DecimalInteger => {
568                let token_source = token_source.replace("_", "");
569                Self::parse_integer_literal(&token_source, 10)
570                    .map_err(|_| stream.error("Invalid integer literal"))?
571            }
572            TokenKind::HexInteger => {
573                let token_source = token_source.replace("_", "");
574                Self::parse_integer_literal(&token_source[2..], 16)
575                    .map_err(|_| stream.error("Invalid hexadecimal integer literal"))?
576            }
577            TokenKind::Float => {
578                let token_source = token_source.replace("_", "");
579                <T::Float as FloatParser>::parse(&token_source)
580                    .map(LiteralValue::Float)
581                    .map_err(|_| stream.error("Invalid float literal"))?
582            }
583            TokenKind::String => match unescape(&token_source[1..token_source.len() - 1]) {
584                Ok(string) => LiteralValue::String(string),
585                Err(offset) => {
586                    return Err(Error {
587                        error: String::from("Invalid escape sequence in string literal")
588                            .into_boxed_str(),
589                        location: Location {
590                            start: token.location.start + offset,
591                            end: token.location.start + offset + 1,
592                        },
593                    });
594                }
595            },
596            TokenKind::Identifier if token_source == "true" => LiteralValue::Boolean(true),
597            TokenKind::Identifier if token_source == "false" => LiteralValue::Boolean(false),
598            _ => return Err(stream.error("Expected literal (number, string, or boolean)")),
599        };
600
601        stream.expect_match(token.kind, &[])?;
602        Ok(Self {
603            value: literal_value,
604            location,
605        })
606    }
607
608    fn parse_integer_literal(
609        token_source: &str,
610        radix: u32,
611    ) -> Result<LiteralValue<T>, ParseIntError> {
612        <T::Integer as IntParser>::parse(token_source, radix).map(LiteralValue::Integer)
613    }
614}
615
616fn unescape(s: &str) -> Result<String, usize> {
617    let mut result = String::new();
618    let mut escaped = false;
619    for (i, c) in s.char_indices().peekable() {
620        if escaped {
621            match c {
622                'n' => result.push('\n'),
623                't' => result.push('\t'),
624                '\\' => result.push('\\'),
625                '"' => result.push('"'),
626                '\'' => result.push('\''),
627                _ => return Err(i), // Invalid escape sequence
628            }
629            escaped = false;
630        } else if c == '\\' {
631            escaped = true;
632        } else {
633            result.push(c);
634        }
635    }
636
637    Ok(result)
638}
639
640impl LeftHandExpression {
641    fn parse<T: TypeSet>(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
642        const UNARY_OPERATORS: &[&str] = &["*"];
643        let expr = if let Some(operator) = stream.take_match(TokenKind::Symbol, UNARY_OPERATORS)? {
644            Self::Deref {
645                operator,
646                name: Self::parse_name::<T>(stream)?,
647            }
648        } else {
649            Self::Name {
650                variable: Self::parse_name::<T>(stream)?,
651            }
652        };
653
654        Ok(expr)
655    }
656
657    fn parse_name<T: TypeSet>(
658        stream: &mut TokenStream<'_, impl Tokenizer>,
659    ) -> Result<Token, Error> {
660        let token = stream.peek_expect()?;
661        match token.kind {
662            TokenKind::Identifier => {
663                // true, false?
664                match Literal::<T>::parse(stream) {
665                    Ok(_) => Err(Error {
666                        error: "Parse error: Literals are not valid on the left-hand side"
667                            .to_string()
668                            .into_boxed_str(),
669                        location: token.location,
670                    }),
671                    _ => stream
672                        .take_match(TokenKind::Identifier, &[])
673                        .map(|v| v.unwrap()),
674                }
675            }
676            _ => Err(stream.error("Expected variable name or deref operator")),
677        }
678    }
679}
680
681impl<T> Expression<T>
682where
683    T: TypeSet,
684{
685    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
686        let save = stream.clone();
687
688        let expression = RightHandExpression::<T>::parse(stream)?;
689
690        if let Ok(Some(operator)) = stream.take_match(TokenKind::Symbol, &["="]) {
691            // Re-parse as an assignment
692            *stream = save;
693            let left_expr = LeftHandExpression::parse::<T>(stream)?;
694            stream.expect_match(TokenKind::Symbol, &["="])?;
695            let right_expr = RightHandExpression::parse(stream)?;
696
697            Ok(Self::Assignment {
698                left_expr,
699                operator,
700                right_expr,
701            })
702        } else {
703            Ok(Self::Expression { expression })
704        }
705    }
706}
707
708impl<T> RightHandExpression<T>
709where
710    T: TypeSet,
711{
712    fn parse(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
713        // We define the binary operators from the lowest precedence to the highest.
714        // Each recursive call to `parse_binary` will handle one level of precedence, and pass
715        // the rest to the inner calls of `parse_binary`.
716        let operators: &[&[&str]] = &[
717            &["||"],
718            &["&&"],
719            &["<", "<=", ">", ">=", "==", "!="],
720            &["|"],
721            &["^"],
722            &["&"],
723            &["<<", ">>"],
724            &["+", "-"],
725            &["*", "/", "%"],
726        ];
727
728        Self::parse_binary(stream, operators)
729    }
730
731    fn parse_binary(
732        stream: &mut TokenStream<'_, impl Tokenizer>,
733        binary_operators: &[&[&str]],
734    ) -> Result<Self, Error> {
735        let Some((current, higher)) = binary_operators.split_first() else {
736            unreachable!("At least one operator set is expected");
737        };
738
739        let mut expr = if higher.is_empty() {
740            Self::parse_unary(stream)?
741        } else {
742            Self::parse_binary(stream, higher)?
743        };
744
745        while let Some(operator) = stream.take_match(TokenKind::Symbol, current)? {
746            let rhs = if higher.is_empty() {
747                Self::parse_unary(stream)?
748            } else {
749                Self::parse_binary(stream, higher)?
750            };
751
752            expr = Self::BinaryOperator {
753                name: operator,
754                operands: Box::new([expr, rhs]),
755            };
756        }
757
758        Ok(expr)
759    }
760
761    fn parse_unary(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
762        const UNARY_OPERATORS: &[&str] = &["!", "-", "&", "*"];
763        if let Some(operator) = stream.take_match(TokenKind::Symbol, UNARY_OPERATORS)? {
764            let operand = Self::parse_unary(stream)?;
765            Ok(Self::UnaryOperator {
766                name: operator,
767                operand: Box::new(operand),
768            })
769        } else {
770            Self::parse_primary(stream)
771        }
772    }
773
774    fn parse_primary(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
775        let token = stream.peek_expect()?;
776
777        match token.kind {
778            TokenKind::Identifier => {
779                // true, false?
780                if let Ok(literal) = Literal::<T>::parse(stream) {
781                    return Ok(Self::Literal { value: literal });
782                }
783
784                Self::parse_call(stream)
785            }
786            TokenKind::Symbol if stream.source(token.location) == "(" => {
787                stream.take_match(token.kind, &[])?;
788                let expr = Self::parse(stream)?;
789                stream.expect_match(TokenKind::Symbol, &[")"])?;
790                Ok(expr)
791            }
792            TokenKind::HexInteger
793            | TokenKind::DecimalInteger
794            | TokenKind::BinaryInteger
795            | TokenKind::Float
796            | TokenKind::String => Literal::<T>::parse(stream).map(|value| Self::Literal { value }),
797            _ => Err(stream.error("Expected variable, literal, or '('")),
798        }
799    }
800
801    fn parse_call(stream: &mut TokenStream<'_, impl Tokenizer>) -> Result<Self, Error> {
802        let token = stream.expect_match(TokenKind::Identifier, &[])?;
803
804        if stream.take_match(TokenKind::Symbol, &["("])?.is_none() {
805            return Ok(Self::Variable { variable: token });
806        };
807
808        let mut arguments = Vec::new();
809        while stream.peek_match(TokenKind::Symbol, &[")"])?.is_none() {
810            let arg = Self::parse(stream)?;
811            arguments.push(arg);
812
813            if stream.take_match(TokenKind::Symbol, &[","])?.is_none() {
814                break;
815            }
816        }
817        stream.expect_match(TokenKind::Symbol, &[")"])?;
818
819        Ok(Self::FunctionCall {
820            name: token,
821            arguments: arguments.into_boxed_slice(),
822        })
823    }
824}
825
826#[derive(Clone)]
827struct TokenStream<'s, I>
828where
829    I: Tokenizer,
830{
831    source: &'s str,
832    tokens: I,
833}
834
835impl<'s, I> TokenStream<'s, I>
836where
837    I: Tokenizer,
838{
839    fn new(source: &'s str, tokens: I) -> Self {
840        TokenStream { source, tokens }
841    }
842
843    /// Fast-forwards the token iterator past comments.
844    fn skip_comments(&mut self) -> Result<(), Error> {
845        let mut peekable = self.tokens.clone();
846        while let Some(token) = peekable.next() {
847            if token?.kind == TokenKind::Comment {
848                self.tokens = peekable.clone();
849            } else {
850                break;
851            }
852        }
853
854        Ok(())
855    }
856
857    fn end(&mut self) -> Result<bool, Error> {
858        self.skip_comments()?;
859
860        Ok(self.tokens.clone().next().is_none())
861    }
862
863    fn peek(&mut self) -> Result<Option<Token>, Error> {
864        self.skip_comments()?;
865
866        match self.tokens.clone().next() {
867            Some(Ok(token)) => Ok(Some(token)),
868            Some(Err(error)) => Err(error),
869            None => Ok(None),
870        }
871    }
872
873    fn peek_expect(&mut self) -> Result<Token, Error> {
874        self.peek()?.ok_or_else(|| Error {
875            location: Location {
876                start: self.source.len(),
877                end: self.source.len(),
878            },
879            error: String::from("Unexpected end of input").into_boxed_str(),
880        })
881    }
882
883    fn peek_match(
884        &mut self,
885        token_kind: TokenKind,
886        source: &[&str],
887    ) -> Result<Option<Token>, Error> {
888        let Some(token) = self.peek()? else {
889            return Ok(None);
890        };
891
892        let peeked = if token.kind == token_kind
893            && (source.is_empty() || source.contains(&self.source(token.location)))
894        {
895            Some(token)
896        } else {
897            None
898        };
899
900        Ok(peeked)
901    }
902
903    fn take_match(
904        &mut self,
905        token_kind: TokenKind,
906        source: &[&str],
907    ) -> Result<Option<Token>, Error> {
908        self.peek_match(token_kind, source).map(|token| {
909            if let Some(token) = token {
910                self.tokens.next();
911                Some(token)
912            } else {
913                None
914            }
915        })
916    }
917
918    /// Takes the next token if it matches the expected kind and source.
919    /// Returns an error if the token does not match.
920    ///
921    /// If `source` is empty, it only checks the token kind.
922    /// If `source` is not empty, it checks if the token's source matches any of the provided strings.
923    fn expect_match(&mut self, token_kind: TokenKind, source: &[&str]) -> Result<Token, Error> {
924        if let Some(token) = self.take_match(token_kind, source)? {
925            Ok(token)
926        } else {
927            let token = self.peek()?;
928            let found = if let Some(token) = token {
929                if token.kind == token_kind {
930                    format!("found '{}'", self.source(token.location))
931                } else {
932                    format!("found {:?}", token.kind)
933                }
934            } else {
935                "reached end of input".to_string()
936            };
937            match source {
938                [] => Err(self.error(format_args!("Expected {token_kind:?}, {found}"))),
939                [s] => Err(self.error(format_args!("Expected '{s}', {found}"))),
940                _ => Err(self.error(format_args!("Expected one of {source:?}, {found}"))),
941            }
942        }
943    }
944
945    fn error(&self, message: impl Display) -> Error {
946        Error {
947            error: format!("Parse error: {message}").into_boxed_str(),
948            location: if let Some(Ok(token)) = self.tokens.clone().next() {
949                token.location
950            } else {
951                Location {
952                    start: self.source.len(),
953                    end: self.source.len(),
954                }
955            },
956        }
957    }
958
959    fn source(&self, location: Location) -> &'s str {
960        location.extract(self.source)
961    }
962}
963
964pub fn parse<T>(source: &str) -> Result<Program<T>, Error>
965where
966    T: TypeSet,
967{
968    let tokens = crate::lexer::tokenize(source);
969    let mut stream = TokenStream::new(source, tokens);
970
971    Program::<T>::parse(&mut stream)
972}
973
974pub fn parse_expression<T>(source: &str) -> Result<Expression<T>, Error>
975where
976    T: TypeSet,
977{
978    let tokens = crate::lexer::tokenize(source);
979    let mut stream = TokenStream::new(source, tokens);
980
981    Expression::<T>::parse(&mut stream)
982}
983
984#[cfg(test)]
985mod tests {
986    use super::*;
987
988    #[test]
989    fn test_unescape() {
990        assert_eq!(unescape(r#"Hello\nWorld\t!"#).unwrap(), "Hello\nWorld\t!");
991        assert_eq!(unescape(r#"Hello\\World"#).unwrap(), "Hello\\World");
992        assert_eq!(unescape(r#"Hello\zWorld"#), Err(6)); // Invalid escape sequence
993    }
994
995    #[test]
996    fn test_out_of_range_literal() {
997        let source = "0x100000000";
998
999        let result = parse_expression::<TypeSet32>(source).expect_err("Parsing should fail");
1000        assert_eq!(
1001            "Parse error: Invalid hexadecimal integer literal",
1002            result.error.as_ref()
1003        );
1004    }
1005
1006    #[test]
1007    fn test_grouped_numeric_literal() {
1008        let source = "1_000_000";
1009
1010        let result = parse_expression::<TypeSet32>(source).unwrap();
1011
1012        assert_eq!(source, result.location().extract(source));
1013    }
1014
1015    #[test]
1016    fn test_parse_strings() {
1017        type LitVal = LiteralValue<TypeSet32>;
1018
1019        let test_data = [
1020            (r#""hel_lo""#, Ok(LitVal::String(r#"hel_lo"#.to_string()))),
1021            ("1_000", Ok(LitVal::Integer(1000))),
1022            ("true", Ok(LitVal::Boolean(true))),
1023            ("false", Ok(LitVal::Boolean(false))),
1024            (
1025                "fal_se",
1026                Err("Parse error: Expected literal (number, string, or boolean)"),
1027            ),
1028        ];
1029
1030        for (source, expected) in test_data {
1031            let tokens = crate::lexer::tokenize(source);
1032            let mut stream = TokenStream::new(source, tokens);
1033
1034            let lit = match Literal::<TypeSet32>::parse(&mut stream) {
1035                Ok(lit) => lit,
1036                Err(err) => {
1037                    let Err(expected_err) = expected else {
1038                        panic!(
1039                            "Expected parsing to succeed, but it failed with error: {}",
1040                            err
1041                        );
1042                    };
1043                    assert_eq!(expected_err, err.to_string());
1044                    continue;
1045                }
1046            };
1047
1048            let Ok(expected) = expected else {
1049                panic!("Expected error, but `{source}` was parsed successfully");
1050            };
1051
1052            match (lit.value, expected) {
1053                (LitVal::Integer(a), LitVal::Integer(b)) => assert_eq!(a, b),
1054                (LitVal::Float(a), LitVal::Float(b)) => assert_eq!(a, b),
1055                (LitVal::String(a), LitVal::String(b)) => assert_eq!(a, b),
1056                (LitVal::Boolean(a), LitVal::Boolean(b)) => assert_eq!(a, b),
1057                _ => panic!("Unexpected literal type"),
1058            }
1059        }
1060    }
1061}
somni_parser/parser.rs

somni_parser/
parser.rs
