arithmetic_parser/parser/
expr.rs

1//! `Expr`-related parsing functions.
2
3use core::mem;
4
5use nom::{
6    branch::alt,
7    bytes::complete::{tag, take_while1},
8    character::complete::{char as tag_char, one_of},
9    combinator::{cut, map, map_res, opt},
10    error::context,
11    multi::{many0, separated_list0},
12    sequence::{delimited, preceded, terminated},
13    Err as NomErr, Input, Parser,
14};
15
16use super::{
17    block, fn_def,
18    helpers::{comma_sep, is_valid_variable_name, mandatory_ws, var_name, ws, GrammarType},
19};
20use crate::{
21    alloc::{vec, Box, Vec},
22    grammars::{Features, Grammar, Parse, ParseLiteral},
23    spans::{unite_spans, with_span},
24    BinaryOp, Context, Error, ErrorKind, Expr, InputSpan, NomResult, ObjectExpr, Spanned,
25    SpannedExpr, UnaryOp,
26};
27
28/// Function arguments in the call position; e.g., `(a, B + 1)`.
29///
30/// # Return value
31///
32/// The second component of the returned tuple is set to `true` if the list is `,`-terminated.
33fn fn_args<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, (Vec<SpannedExpr<'_, T::Base>>, bool)>
34where
35    T: Parse,
36    Ty: GrammarType,
37{
38    let maybe_comma = map(opt(preceded(ws::<Ty>, tag_char(','))), |c| c.is_some());
39
40    preceded(
41        terminated(tag_char('('), ws::<Ty>),
42        // Once we've encountered the opening `(`, the input *must* correspond to the parser.
43        cut((
44            separated_list0(delimited(ws::<Ty>, tag_char(','), ws::<Ty>), expr::<T, Ty>),
45            terminated(maybe_comma, (ws::<Ty>, tag_char(')'))),
46        )),
47    )
48    .parse(input)
49}
50
51/// Expression enclosed in parentheses. This may be a simple value (e.g., `(1 + 2)`)
52/// or a tuple (e.g., `(x, y)`), depending on the number of comma-separated terms.
53pub(super) fn paren_expr<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
54where
55    T: Parse,
56    Ty: GrammarType,
57{
58    with_span(fn_args::<T, Ty>)
59        .parse(input)
60        .and_then(|(rest, parsed)| {
61            let comma_terminated = parsed.extra.1;
62            let terms = parsed.map_extra(|terms| terms.0);
63
64            match (terms.extra.len(), comma_terminated) {
65                (1, false) => Ok((
66                    rest,
67                    terms.map_extra(|mut terms| terms.pop().unwrap().extra),
68                )),
69                _ => {
70                    if T::FEATURES.contains(Features::TUPLES) {
71                        Ok((rest, terms.map_extra(Expr::Tuple)))
72                    } else {
73                        Err(NomErr::Failure(
74                            ErrorKind::UnexpectedTerm { context: None }.with_span(&terms),
75                        ))
76                    }
77                }
78            }
79        })
80}
81
82/// Parses a block and wraps it into an `Expr`.
83fn block_expr<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
84where
85    T: Parse,
86    Ty: GrammarType,
87{
88    map(with_span(block::<T, Ty>), |spanned| {
89        spanned.map_extra(Expr::Block)
90    })
91    .parse(input)
92}
93
94fn object_expr_field<T, Ty>(
95    input: InputSpan<'_>,
96) -> NomResult<'_, (Spanned<'_>, Option<SpannedExpr<'_, T::Base>>)>
97where
98    T: Parse,
99    Ty: GrammarType,
100{
101    let colon_sep = delimited(ws::<Ty>, tag_char(':'), ws::<Ty>);
102    (
103        map(var_name, Spanned::from),
104        opt(preceded(colon_sep, expr::<T, Ty>)),
105    )
106        .parse(input)
107}
108
109pub(super) fn object_expr<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
110where
111    T: Parse,
112    Ty: GrammarType,
113{
114    let object = preceded(
115        terminated(tag("#{"), ws::<Ty>),
116        cut(terminated(
117            terminated(
118                separated_list0(comma_sep::<Ty>, object_expr_field::<T, Ty>),
119                opt(comma_sep::<Ty>),
120            ),
121            preceded(ws::<Ty>, tag_char('}')),
122        )),
123    );
124
125    map(with_span(object), |spanned| {
126        spanned.map_extra(|fields| Expr::Object(ObjectExpr { fields }))
127    })
128    .parse(input)
129}
130
131/// Parses a function definition and wraps it into an `Expr`.
132fn fn_def_expr<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
133where
134    T: Parse,
135    Ty: GrammarType,
136{
137    map(with_span(fn_def::<T, Ty>), |spanned| {
138        spanned.map_extra(Expr::FnDefinition)
139    })
140    .parse(input)
141}
142
143/// Parses a simple expression, i.e., one not containing binary operations or function calls.
144///
145/// From the construction, the evaluation priorities within such an expression are always higher
146/// than for possible binary ops surrounding it.
147fn simplest_expr<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
148where
149    T: Parse,
150    Ty: GrammarType,
151{
152    fn error<T>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
153    where
154        T: Parse,
155    {
156        let e = ErrorKind::Leftovers.with_span(&input.into());
157        Err(NomErr::Error(e))
158    }
159
160    let block_parser = if T::FEATURES.contains(Features::BLOCKS) {
161        block_expr::<T, Ty>
162    } else {
163        error::<T>
164    };
165    let object_parser = if T::FEATURES.contains(Features::OBJECTS) {
166        object_expr::<T, Ty>
167    } else {
168        error::<T>
169    };
170    let fn_def_parser = if T::FEATURES.contains(Features::FN_DEFINITIONS) {
171        fn_def_expr::<T, Ty>
172    } else {
173        error::<T>
174    };
175
176    alt((
177        map(with_span(<T::Base>::parse_literal), |span| {
178            span.map_extra(Expr::Literal)
179        }),
180        map(with_span(var_name), |span| {
181            span.copy_with_extra(Expr::Variable)
182        }),
183        fn_def_parser,
184        map(
185            with_span((
186                terminated(with_span(one_of("-!")), ws::<Ty>),
187                expr_with_calls::<T, Ty>,
188            )),
189            |spanned| {
190                spanned.map_extra(|(op, inner)| Expr::Unary {
191                    op: UnaryOp::from_span(op),
192                    inner: Box::new(inner),
193                })
194            },
195        ),
196        block_parser,
197        object_parser,
198        paren_expr::<T, Ty>,
199    ))
200    .parse(input)
201}
202
203#[derive(Debug)]
204struct MethodOrFnCall<'a, T: Grammar> {
205    separator: Option<Spanned<'a>>,
206    fn_name: Option<SpannedExpr<'a, T>>,
207    args: Option<Vec<SpannedExpr<'a, T>>>,
208}
209
210impl<T: Grammar> MethodOrFnCall<'_, T> {
211    fn is_method(&self) -> bool {
212        self.fn_name.is_some() && self.args.is_some()
213    }
214}
215
216type MethodParseResult<'a, T> = NomResult<'a, MethodOrFnCall<'a, <T as Parse>::Base>>;
217
218fn fn_call<T, Ty>(input: InputSpan<'_>) -> MethodParseResult<'_, T>
219where
220    T: Parse,
221    Ty: GrammarType,
222{
223    map(fn_args::<T, Ty>, |(args, _)| MethodOrFnCall {
224        separator: None,
225        fn_name: None,
226        args: Some(args),
227    })
228    .parse(input)
229}
230
231fn method_or_fn_call<T, Ty>(input: InputSpan<'_>) -> MethodParseResult<'_, T>
232where
233    T: Parse,
234    Ty: GrammarType,
235{
236    let var_name_or_digits = alt((var_name, take_while1(|c: char| c.is_ascii_digit())));
237    let method_or_field_expr = alt((
238        map(with_span(var_name_or_digits), |span| {
239            span.copy_with_extra(Expr::Variable)
240        }),
241        block_expr::<T, Ty>,
242    ));
243    let method_or_field_access_parser = map_res(
244        (
245            method_or_field_expr,
246            opt(preceded(ws::<Ty>, fn_args::<T, Ty>)),
247        ),
248        |(fn_name, maybe_args)| {
249            if maybe_args.is_some() {
250                let is_bogus_name = matches!(fn_name.extra, Expr::Variable)
251                    && !is_valid_variable_name(fn_name.fragment());
252                if is_bogus_name {
253                    return Err(ErrorKind::LiteralName);
254                }
255            }
256            Ok(MethodOrFnCall {
257                separator: None,
258                fn_name: Some(fn_name),
259                args: maybe_args.map(|(args, _)| args),
260            })
261        },
262    );
263    let method_or_field_access_parser = map(
264        (
265            terminated(with_span(tag_char('.')), ws::<Ty>),
266            cut(method_or_field_access_parser),
267        ),
268        |(separator, mut call)| {
269            call.separator = Some(separator.with_no_extra());
270            call
271        },
272    );
273
274    alt((method_or_field_access_parser, fn_call::<T, Ty>)).parse(input)
275}
276
277/// Expression, which includes, besides `simplest_expr`s, function calls.
278fn expr_with_calls<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
279where
280    T: Parse,
281    Ty: GrammarType,
282{
283    let method_or_fn_call = if T::FEATURES.contains(Features::METHODS) {
284        method_or_fn_call::<T, Ty>
285    } else {
286        fn_call::<T, Ty>
287    };
288
289    let mut parser = (
290        simplest_expr::<T, Ty>,
291        many0(with_span(preceded(ws::<Ty>, method_or_fn_call))),
292    );
293    parser.parse(input).and_then(|(rest, (base, calls))| {
294        fold_args(input, base, calls).map(|folded| (rest, folded))
295    })
296}
297
298/// Simple expression, which includes `expr_with_calls` and type casts.
299pub(super) fn simple_expr<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
300where
301    T: Parse,
302    Ty: GrammarType,
303{
304    let as_keyword = delimited(ws::<Ty>, tag("as"), mandatory_ws::<Ty>);
305    let parser = (
306        expr_with_calls::<T, Ty>,
307        many0(preceded(as_keyword, cut(with_span(<T::Base>::parse_type)))),
308    );
309
310    map(parser, |(base, casts)| {
311        casts.into_iter().fold(base, |value, ty| {
312            let united_span = unite_spans(input, &value, &ty);
313            united_span.copy_with_extra(Expr::TypeCast {
314                value: Box::new(value),
315                ty,
316            })
317        })
318    })
319    .parse(input)
320}
321
322#[allow(clippy::option_if_let_else, clippy::range_plus_one)]
323// ^-- See explanations in the function code.
324fn fold_args<'a, T: Grammar>(
325    input: InputSpan<'a>,
326    mut base: SpannedExpr<'a, T>,
327    calls: Vec<Spanned<'a, MethodOrFnCall<'a, T>>>,
328) -> Result<SpannedExpr<'a, T>, NomErr<Error>> {
329    // Do we need to reorder unary op application and method calls? This is only applicable if:
330    //
331    // - `base` is a literal (as a corollary, `-` / `!` may be a start of a literal)
332    // - The next call is a method
333    // - A literal is parsed without the unary op.
334    //
335    // If all these conditions hold, we reorder the unary op to execute *after* all calls.
336    // This is necessary to correctly parse `-1.abs()` as `-(1.abs())`, not as `(-1).abs()`.
337    let mut maybe_reordered_op = None;
338
339    if matches!(base.extra, Expr::Literal(_)) {
340        match calls.first() {
341            Some(call) if !call.extra.is_method() => {
342                // Bogus function call, such as `1(2, 3)` or `1.x`.
343                let e = ErrorKind::LiteralName.with_span(&base);
344                return Err(NomErr::Failure(e));
345            }
346            // Indexing should be safe: literals must have non-empty span.
347            Some(_) => maybe_reordered_op = UnaryOp::try_from_byte(base.fragment().as_bytes()[0]),
348            None => { /* Special processing is not required. */ }
349        }
350    }
351
352    let reordered_op = if let Some(reordered_op) = maybe_reordered_op {
353        let lit_start = base.location_offset() - input.location_offset();
354        let unsigned_lit_input = input.take_from(lit_start + 1).take(base.fragment().len());
355
356        if let Ok((_, unsigned_lit)) = T::parse_literal(unsigned_lit_input) {
357            base = SpannedExpr::new(unsigned_lit_input, Expr::Literal(unsigned_lit));
358
359            // `nom::Slice` is not implemented for inclusive range types, so the Clippy warning
360            // cannot be fixed.
361            let op_span = input.take_from(lit_start).take(1);
362            Some(Spanned::new(op_span, reordered_op))
363        } else {
364            None
365        }
366    } else {
367        None
368    };
369
370    let folded = calls.into_iter().fold(base, |name, call| {
371        let united_span = unite_spans(input, &name, &call);
372
373        // Clippy lint is triggered here. `name` cannot be moved into both branches,
374        // so it's a false positive.
375        let expr = if let Some(fn_name) = call.extra.fn_name {
376            if let Some(args) = call.extra.args {
377                Expr::Method {
378                    name: fn_name.into(),
379                    receiver: Box::new(name),
380                    separator: call.extra.separator.unwrap(), // safe by construction
381                    args,
382                }
383            } else {
384                Expr::FieldAccess {
385                    name: fn_name.into(),
386                    receiver: Box::new(name),
387                }
388            }
389        } else {
390            Expr::Function {
391                name: Box::new(name),
392                args: call.extra.args.expect("Args must be present for functions"),
393            }
394        };
395        united_span.copy_with_extra(expr)
396    });
397
398    Ok(if let Some(unary_op) = reordered_op {
399        unite_spans(input, &unary_op, &folded).copy_with_extra(Expr::Unary {
400            op: unary_op,
401            inner: Box::new(folded),
402        })
403    } else {
404        folded
405    })
406}
407
408/// Parses an expression with binary operations into a tree with the hierarchy reflecting
409/// the evaluation order of the operations.
410pub(super) fn binary_expr<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
411where
412    T: Parse,
413    Ty: GrammarType,
414{
415    // First, we parse the expression into a list with simple expressions interspersed
416    // with binary operations. For example, `1 + 2 * foo(x, y)` is parsed into
417    //
418    //     [ 1, +, 2, *, foo(x, y) ]
419    #[rustfmt::skip]
420        let binary_ops = alt((
421        tag("+"), tag("-"), tag("*"), tag("/"), tag("^"), // simple ops
422        tag("=="), tag("!="), // equality comparisons
423        tag("&&"), tag("||"), // logical ops
424        tag(">="), tag("<="), tag(">"), tag("<"), // order comparisons
425    ));
426    let mut binary_ops = map(binary_ops, BinaryOp::from_span);
427
428    let full_binary_ops = move |input| {
429        let (rest, spanned_op) = binary_ops.parse(input)?;
430        if spanned_op.extra.is_supported(T::FEATURES) {
431            Ok((rest, spanned_op))
432        } else {
433            // Immediately drop parsing on an unsupported op, since there are no alternatives.
434            let err = ErrorKind::UnsupportedOp(spanned_op.extra.into());
435            let spanned_err = err.with_span(&spanned_op);
436            Err(NomErr::Failure(spanned_err))
437        }
438    };
439
440    let mut binary_parser = (
441        simple_expr::<T, Ty>,
442        many0((
443            delimited(ws::<Ty>, full_binary_ops, ws::<Ty>),
444            cut(simple_expr::<T, Ty>),
445        )),
446    );
447
448    let (remaining_input, (first, rest)) = binary_parser.parse(input)?;
449    let folded = fold_binary_expr(input, first, rest).map_err(NomErr::Failure)?;
450    Ok((remaining_input, folded))
451}
452
453// After obtaining the list, we fold it paying attention to the operation priorities.
454// We track the `right_contour` of the parsed tree and insert a new operation so that
455// operations in the contour with lower priority remain in place.
456//
457// As an example, consider expression `1 + 2 * foo(x, y) - 7` split into list
458// `[ 1, +, 2, *, foo(x, y), -, 7 ]`. First, we form a tree
459//
460//   +
461//  / \
462// 1   2
463//
464// Then, we find the place to insert the `*` op and `foo(x, y)` operand. Since `*` has
465// a higher priority than `+`, we insert it *below* the `+` op:
466//
467//   +
468//  / \
469// 1   *
470//    / \
471//   2  foo(x, y)
472//
473// The next op `-` has the same priority as the first op in the right contour (`+`), so
474// we insert it *above* it:
475//
476//    -
477//   / \
478//   +  7
479//  / \
480// 1   *
481//    / \
482//   2  foo(x, y)
483fn fold_binary_expr<'a, T: Grammar>(
484    input: InputSpan<'a>,
485    first: SpannedExpr<'a, T>,
486    rest: Vec<(Spanned<'a, BinaryOp>, SpannedExpr<'a, T>)>,
487) -> Result<SpannedExpr<'a, T>, Error> {
488    let mut right_contour: Vec<BinaryOp> = vec![];
489
490    rest.into_iter().try_fold(first, |mut acc, (new_op, expr)| {
491        let united_span = unite_spans(input, &acc, &expr);
492
493        let insert_pos = right_contour
494            .iter()
495            .position(|past_op| past_op.priority() >= new_op.extra.priority())
496            .unwrap_or(right_contour.len());
497
498        // We determine the error span later.
499        let chained_comparison = right_contour
500            .get(insert_pos)
501            .is_some_and(|past_op| past_op.is_comparison() && new_op.extra.is_comparison());
502
503        right_contour.truncate(insert_pos);
504        right_contour.push(new_op.extra);
505
506        if insert_pos == 0 {
507            if chained_comparison {
508                return Err(ErrorKind::ChainedComparison.with_span(&united_span));
509            }
510
511            Ok(united_span.copy_with_extra(Expr::Binary {
512                lhs: Box::new(acc),
513                op: new_op,
514                rhs: Box::new(expr),
515            }))
516        } else {
517            let mut parent = &mut acc;
518            for _ in 1..insert_pos {
519                parent = match &mut parent.extra {
520                    Expr::Binary { rhs, .. } => rhs,
521                    _ => unreachable!(),
522                };
523            }
524
525            *parent = unite_spans(input, parent, &expr).copy_with_extra(parent.extra.clone());
526            if let Expr::Binary { rhs, .. } = &mut parent.extra {
527                let rhs_span = unite_spans(input, rhs, &expr);
528                if chained_comparison {
529                    return Err(ErrorKind::ChainedComparison.with_span(&rhs_span));
530                }
531
532                let dummy = Box::new(rhs.copy_with_extra(Expr::Variable));
533                let old_rhs = mem::replace(rhs, dummy);
534                let new_expr = Expr::Binary {
535                    lhs: old_rhs,
536                    op: new_op,
537                    rhs: Box::new(expr),
538                };
539                *rhs = Box::new(rhs_span.copy_with_extra(new_expr));
540            }
541            acc = united_span.copy_with_extra(acc.extra);
542            Ok(acc)
543        }
544    })
545}
546
547pub(super) fn expr<T, Ty>(input: InputSpan<'_>) -> NomResult<'_, SpannedExpr<'_, T::Base>>
548where
549    T: Parse,
550    Ty: GrammarType,
551{
552    context(Context::Expr.to_str(), binary_expr::<T, Ty>).parse(input)
553}
arithmetic_parser/parser/expr.rs

arithmetic_parser/parser/
expr.rs
