cl_parser/parser/
expr.rs

1use super::{PResult, PResultExt, Parse, ParseError, Parser, no_eof, pat::Prec as PPrec};
2use cl_ast::{types::Literal, *};
3use cl_token::{TKind, Token};
4
5/// Organizes the precedence hierarchy for syntactic elements
6#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
7pub enum Prec {
8    Min,
9    /// The Semicolon Operator gets its own precedence level
10    Do,
11    /// An assignment
12    Assign,
13    /// Constructor for a tuple
14    Tuple,
15    /// The body of a function, conditional, etc.
16    Body,
17    /// Constructor for a struct
18    Make,
19    /// The conditional of an `if` or `while` (which is really an `if`)
20    Logical,
21    /// The short-circuiting "boolean or" operator
22    LogOr,
23    /// The short-circuiting "boolean and" operator
24    LogAnd,
25    /// Value comparison operators
26    Compare,
27    /// Constructor for a Range
28    Range,
29    /// Binary/bitwise operators
30    Binary,
31    /// Bit-shifting operators
32    Shift,
33    /// Addition and Subtraction operators
34    Factor,
35    /// Multiplication, Division, and Remainder operators
36    Term,
37    /// Negation, Reference, Try
38    Unary,
39    /// Place-projection operators (`*x`, `x[1]`, `x.a`, `x.1`)
40    Project,
41    /// Call subscripting
42    Extend,
43    Max,
44}
45
46impl Prec {
47    pub const MIN: usize = Prec::Min.value();
48
49    pub const fn value(self) -> usize {
50        self as usize * 2
51    }
52
53    pub const fn prev(self) -> usize {
54        match self {
55            Self::Assign => self.value() + 1,
56            _ => self.value(),
57        }
58    }
59
60    pub const fn next(self) -> usize {
61        match self {
62            Self::Assign => self.value(),
63            _ => self.value() + 1,
64        }
65    }
66}
67
68/// `PseudoOperator`: fake operators used to give certain tokens special behavior.
69#[derive(Clone, Copy, Debug, PartialEq, Eq)]
70pub enum Ps {
71    Id,         // Identifier
72    Mid,        // MetaIdentifier
73    Lit,        // Literal
74    Use,        // use Use
75    Def,        // any definition (let, struct, enum, fn, ...)
76    DocInner,   // Documentation Comment `//!`
77    DocOuter,   // Documentation Comment `///`
78    For,        // for Pat in Expr Expr else Expr
79    Lambda0,    // || Expr
80    Lambda,     // | Pat,* | Expr
81    DoubleRef,  // && Expr
82    Make,       // Expr{ Expr,* }
83    Match,      // match Expr { (Pat => Expr),* }
84    ImplicitDo, // An implicit semicolon
85    Ellipsis,   // An ellipsis (...)
86    End,        // Produces an empty value.
87    Op(Op),     // A normal [ast::Op]
88}
89
90/// Tries to map the incoming [Token] to a prefix [expression operator](Op)
91/// and its [precedence level](Prec)
92fn from_prefix(token: &Token) -> PResult<(Ps, Prec)> {
93    Ok(match token.kind {
94        TKind::OutDoc => (Ps::DocOuter, Prec::Max),
95        TKind::InDoc => (Ps::DocInner, Prec::Max),
96        TKind::Do => (Ps::Op(Op::Do), Prec::Do),
97        TKind::Semi => (Ps::End, Prec::Body),
98
99        TKind::Identifier | TKind::ColonColon => (Ps::Id, Prec::Max),
100        TKind::Dollar => (Ps::Mid, Prec::Max),
101        TKind::True | TKind::False | TKind::Character | TKind::Integer | TKind::String => {
102            (Ps::Lit, Prec::Max)
103        }
104        TKind::Use => (Ps::Use, Prec::Max),
105
106        TKind::Pub => (Ps::Op(Op::Pub), Prec::Max),
107        TKind::Const => (Ps::Op(Op::Const), Prec::Max),
108        TKind::Static => (Ps::Op(Op::Static), Prec::Max),
109        TKind::For => (Ps::For, Prec::Max),
110        TKind::Match => (Ps::Match, Prec::Max),
111        TKind::Macro => (Ps::Op(Op::Macro), Prec::Assign),
112
113        TKind::Fn
114        | TKind::Mod
115        | TKind::Impl
116        | TKind::Let
117        | TKind::Type
118        | TKind::Struct
119        | TKind::Enum => (Ps::Def, Prec::Max),
120
121        TKind::Loop => (Ps::Op(Op::Loop), Prec::Body),
122        TKind::If => (Ps::Op(Op::If), Prec::Body),
123        TKind::While => (Ps::Op(Op::While), Prec::Body),
124        TKind::Break => (Ps::Op(Op::Break), Prec::Body),
125        TKind::Return => (Ps::Op(Op::Return), Prec::Body),
126        TKind::Continue => (Ps::Op(Op::Continue), Prec::Max),
127
128        TKind::LCurly => (Ps::Op(Op::Block), Prec::Min),
129        TKind::RCurly => (Ps::End, Prec::Do),
130        TKind::LBrack => (Ps::Op(Op::Array), Prec::Tuple),
131        TKind::RBrack => (Ps::End, Prec::Tuple),
132        TKind::LParen => (Ps::Op(Op::Group), Prec::Min),
133        TKind::RParen => (Ps::End, Prec::Tuple),
134        TKind::Amp => (Ps::Op(Op::Refer), Prec::Unary),
135        TKind::AmpAmp => (Ps::DoubleRef, Prec::Unary),
136        TKind::Bang => (Ps::Op(Op::Not), Prec::Unary),
137        TKind::BangBang => (Ps::Op(Op::Identity), Prec::Unary),
138        TKind::Bar => (Ps::Lambda, Prec::Body),
139        TKind::BarBar => (Ps::Lambda0, Prec::Body),
140        TKind::DotDot => (Ps::Op(Op::RangeEx), Prec::Range),
141        TKind::DotDotDot => (Ps::Ellipsis, Prec::Max),
142        TKind::DotDotEq => (Ps::Op(Op::RangeIn), Prec::Range),
143        TKind::Minus => (Ps::Op(Op::Neg), Prec::Unary),
144        TKind::Plus => (Ps::Op(Op::Identity), Prec::Unary),
145        TKind::Star => (Ps::Op(Op::Deref), Prec::Unary),
146        TKind::Hash => (Ps::Op(Op::MetaOuter), Prec::Max),
147        TKind::HashBang => (Ps::Op(Op::MetaInner), Prec::Max),
148
149        kind => Err(ParseError::NotPrefix(kind, token.span))?,
150    })
151}
152
153/// Tries to map the incoming [Token] to an infix [expression operator](Op)
154/// and its [precedence level](Prec)
155const fn from_infix(token: &Token) -> PResult<(Ps, Prec)> {
156    Ok(match token.kind {
157        TKind::Semi => (Ps::Op(Op::Do), Prec::Do), // the inspiration
158        TKind::In => (Ps::Op(Op::Do), Prec::Do),
159
160        TKind::Eq => (Ps::Op(Op::Set), Prec::Assign),
161        TKind::StarEq => (Ps::Op(Op::MulSet), Prec::Assign),
162        TKind::SlashEq => (Ps::Op(Op::DivSet), Prec::Assign),
163        TKind::RemEq => (Ps::Op(Op::RemSet), Prec::Assign),
164        TKind::PlusEq => (Ps::Op(Op::AddSet), Prec::Assign),
165        TKind::MinusEq => (Ps::Op(Op::SubSet), Prec::Assign),
166        TKind::LtLtEq => (Ps::Op(Op::ShlSet), Prec::Assign),
167        TKind::GtGtEq => (Ps::Op(Op::ShrSet), Prec::Assign),
168        TKind::AmpEq => (Ps::Op(Op::AndSet), Prec::Assign),
169        TKind::XorEq => (Ps::Op(Op::XorSet), Prec::Assign),
170        TKind::BarEq => (Ps::Op(Op::OrSet), Prec::Assign),
171        TKind::Comma => (Ps::Op(Op::Tuple), Prec::Tuple),
172        TKind::LCurly => (Ps::Make, Prec::Make),
173        TKind::XorXor => (Ps::Op(Op::LogXor), Prec::Logical),
174        TKind::BarBar => (Ps::Op(Op::LogOr), Prec::LogOr),
175        TKind::AmpAmp => (Ps::Op(Op::LogAnd), Prec::LogAnd),
176        TKind::Lt => (Ps::Op(Op::Lt), Prec::Compare),
177        TKind::LtEq => (Ps::Op(Op::Leq), Prec::Compare),
178        TKind::EqEq => (Ps::Op(Op::Eq), Prec::Compare),
179        TKind::BangEq => (Ps::Op(Op::Neq), Prec::Compare),
180        TKind::GtEq => (Ps::Op(Op::Geq), Prec::Compare),
181        TKind::Gt => (Ps::Op(Op::Gt), Prec::Compare),
182        TKind::DotDot => (Ps::Op(Op::RangeEx), Prec::Range),
183        TKind::DotDotEq => (Ps::Op(Op::RangeIn), Prec::Range),
184        TKind::Amp => (Ps::Op(Op::And), Prec::Binary),
185        TKind::Xor => (Ps::Op(Op::Xor), Prec::Binary),
186        TKind::Bar => (Ps::Op(Op::Or), Prec::Binary),
187        TKind::LtLt => (Ps::Op(Op::Shl), Prec::Shift),
188        TKind::GtGt => (Ps::Op(Op::Shr), Prec::Shift),
189        TKind::Plus => (Ps::Op(Op::Add), Prec::Factor),
190        TKind::Minus => (Ps::Op(Op::Sub), Prec::Factor),
191        TKind::Star => (Ps::Op(Op::Mul), Prec::Term),
192        TKind::Slash => (Ps::Op(Op::Div), Prec::Term),
193        TKind::Rem => (Ps::Op(Op::Rem), Prec::Term),
194
195        TKind::Question => (Ps::Op(Op::Try), Prec::Unary),
196        TKind::Dot => (Ps::Op(Op::Dot), Prec::Project),
197        TKind::LBrack => (Ps::Op(Op::Index), Prec::Project),
198        TKind::LParen => (Ps::Op(Op::Call), Prec::Extend),
199
200        TKind::RParen | TKind::RBrack | TKind::RCurly => (Ps::End, Prec::Max),
201        TKind::As => (Ps::Op(Op::As), Prec::Project),
202        _ => (Ps::ImplicitDo, Prec::Do),
203    })
204}
205
206impl<'t> Parse<'t> for Expr {
207    type Prec = usize;
208
209    /// Parses an [Expr]ession.
210    ///
211    /// The `level` parameter indicates the operator binding level of the expression.
212    fn parse(p: &mut Parser<'t>, level: usize) -> PResult<Self> {
213        const MIN: usize = Prec::MIN;
214
215        // Prefix
216        let tok @ &Token { kind, span, .. } = p.peek()?;
217        let (op, prec) = from_prefix(tok)?;
218        no_eof(move || {
219            let mut head = match op {
220                // "End" is produced when an "empty" expression is syntactically required.
221                // This happens when a semi or closing delimiter begins an expression.
222                // The token which emitted "End" cannot be consumed, as it is expected
223                // elsewhere.
224                Ps::End if (prec.value()..=prec.next()).contains(&level) => Expr::Omitted,
225                Ps::End => Err(ParseError::NotPrefix(kind, span))?,
226
227                Ps::Id => Expr::Id(p.parse(())?),
228                Ps::Mid => Expr::MetId(p.consume().next()?.lexeme.to_string().as_str().into()),
229                Ps::Lit => Expr::Lit(p.parse(())?),
230                Ps::Use => Expr::Use(p.consume().parse(())?),
231                Ps::Def => Expr::Bind(p.parse(())?),
232                Ps::For => parse_for(p, ())?,
233                Ps::Match => Expr::Match(p.parse(())?),
234                Ps::Lambda | Ps::Lambda0 => {
235                    p.consume();
236
237                    let args = if kind == TKind::Bar {
238                        p.opt(PPrec::Tuple, TKind::Bar)?
239                            .map(Pat::to_tuple)
240                            .unwrap_or(Pat::Op(PatOp::Tuple, vec![]))
241                    } else {
242                        Pat::Op(PatOp::Tuple, vec![])
243                    };
244
245                    let rety = p.opt_if(PPrec::Max, TKind::Arrow)?.unwrap_or(Pat::Ignore);
246
247                    Expr::Bind(Box::new(Bind(
248                        BindOp::Fn,
249                        vec![],
250                        Pat::Op(PatOp::Fn, vec![args, rety]),
251                        vec![p.parse(Prec::Body.next())?],
252                    )))
253                }
254                Ps::DocOuter | Ps::DocInner => {
255                    let comment = Literal::Str(p.take_lexeme()?.string().unwrap());
256                    let comment = Expr::Lit(comment).at(span);
257                    let next = p.parse(prec.next())?;
258                    Expr::Op(
259                        match op {
260                            Ps::DocOuter => Op::MetaOuter,
261                            _ => Op::MetaInner,
262                        },
263                        vec![comment, next],
264                    )
265                }
266                Ps::Ellipsis => p.consume().then(Expr::Omitted),
267                Ps::Op(op @ (Op::MetaOuter | Op::MetaInner)) => Expr::Op(
268                    op,
269                    vec![
270                        p.consume()
271                            .expect(TKind::LBrack)?
272                            .opt(MIN, TKind::RBrack)?
273                            .unwrap_or_else(|| Expr::Op(Op::Tuple, vec![]).at(span)),
274                        p.parse(prec.next())?,
275                    ],
276                ),
277                Ps::Op(Op::Block) => Expr::Op(
278                    Op::Block,
279                    p.consume().opt(MIN, kind.flip())?.into_iter().collect(),
280                ),
281                Ps::Op(Op::Array) => parse_array(p)?,
282                Ps::Op(Op::Group) => match p.consume().opt(MIN, kind.flip())? {
283                    Some(value) => Expr::Op(Op::Group, vec![value]),
284                    None => Expr::Op(Op::Tuple, vec![]),
285                },
286                Ps::Op(Op::Continue) => p.consume().then(Expr::Op(Op::Continue, vec![])),
287                Ps::Op(op @ (Op::If | Op::While)) => {
288                    p.consume();
289                    let exprs = vec![
290                        // conditional restricted to Logical operators or above
291                        p.parse(Prec::Logical.value())?,
292                        p.parse(prec.next())?,
293                        match p.peek() {
294                            Ok(Token { kind: TKind::Else, .. }) => {
295                                p.consume().parse(prec.next())?
296                            }
297                            _ => Expr::Op(Op::Tuple, vec![]).at(span.merge(p.span())),
298                        },
299                    ];
300                    Expr::Op(op, exprs)
301                }
302                Ps::DoubleRef => p.consume().parse(prec.next()).map(|At(expr, span)| {
303                    Expr::Op(
304                        Op::Refer,
305                        vec![At(Expr::Op(Op::Refer, vec![At(expr, span)]), span)],
306                    )
307                })?,
308
309                Ps::Op(op) => Expr::Op(op, vec![p.consume().parse(prec.next())?]),
310                _ => unimplemented!("prefix {op:?}"),
311            };
312
313            // Infix and Postfix
314            while let Ok(Some(tok @ &Token { kind, .. })) = p.peek().allow_eof()
315                && let Ok((op, prec)) = from_infix(tok)
316                && level <= prec.prev()
317                && op != Ps::End
318            {
319                let span = span.merge(p.span());
320
321                head = match op {
322                    // Make (structor expressions) are context-sensitive
323                    Ps::Make => match &head {
324                        Expr::Id(_) | Expr::MetId(_) => Expr::Make(Box::new(Make(
325                            head.at(span),
326                            p.consume().list(vec![], (), TKind::Comma, TKind::RCurly)?,
327                        ))),
328                        _ => break,
329                    },
330                    // As is ImplicitDo (semicolon elision)
331                    Ps::ImplicitDo if p.elide_do => head.and_do(span, p.parse(prec.next())?),
332                    Ps::ImplicitDo => break,
333                    // Allow `;` at end of file
334                    Ps::Op(Op::Do) => head.and_do(
335                        span,
336                        match p.consume().peek().allow_eof()? {
337                            Some(_) => p.parse(prec.next())?,
338                            None => At(Expr::Omitted, span),
339                        },
340                    ),
341                    Ps::Op(Op::Index) => Expr::Op(
342                        Op::Index,
343                        p.consume()
344                            .list(vec![head.at(span)], 0, TKind::Comma, TKind::RBrack)?,
345                    ),
346                    Ps::Op(Op::Call) => {
347                        let head = head.at(span);
348                        let args = match p.consume().opt::<At<Expr>>(0, TKind::RParen)? {
349                            None => Expr::Op(Op::Tuple, vec![]).at(span),
350                            Some(At(expr, span)) => expr.to_tuple(span).at(span),
351                        };
352                        Expr::Op(Op::Call, vec![head, args])
353                    }
354                    Ps::Op(op @ Op::Tuple) => Expr::Op(
355                        op,
356                        p.consume()
357                            .list_bare(vec![head.at(span)], prec.next(), kind)?,
358                    ),
359                    Ps::Op(op @ Op::Try) => {
360                        p.consume();
361                        Expr::Op(op, vec![head.at(span)])
362                    }
363                    Ps::Op(op) => {
364                        Expr::Op(op, vec![head.at(span), p.consume().parse(prec.next())?])
365                    }
366                    _ => Err(ParseError::NotInfix(kind, span))?,
367                }
368            }
369
370            Ok(head)
371        })
372    }
373}
374
375/// Parses an array with 0 or more elements, or an array-repetition
376fn parse_array(p: &mut Parser<'_>) -> PResult<Expr> {
377    if p.consume().peek()?.kind == TKind::RBrack {
378        p.consume();
379        return Ok(Expr::Op(Op::Array, vec![]));
380    }
381
382    let prec = Prec::Tuple;
383    let item = p.parse(prec.value())?;
384    let repeat = p.opt_if(prec.next(), TKind::Semi)?;
385    p.expect(TKind::RBrack)?;
386
387    Ok(match (repeat, item) {
388        (Some(repeat), item) => Expr::Op(Op::ArRep, vec![item, repeat]),
389        (None, At(Expr::Op(Op::Tuple, items), _)) => Expr::Op(Op::Array, items),
390        (None, item) => Expr::Op(Op::Array, vec![item]),
391    })
392}
393
394/// Parses a `match` expression
395///
396/// ```ignore
397/// match scrutinee {
398///     (Pat => Expr),*
399/// }
400/// ```
401impl<'t> Parse<'t> for Match {
402    type Prec = ();
403
404    fn parse(p: &mut Parser<'t>, _level: Self::Prec) -> PResult<Self>
405    where Self: Sized {
406        Ok(Self(
407            p.consume().parse(Prec::Logical.value())?,
408            p.expect(TKind::LCurly)?
409                .list(vec![], (), TKind::Comma, TKind::RCurly)?,
410        ))
411    }
412}
413
414impl<'t> Parse<'t> for MatchArm {
415    type Prec = ();
416
417    fn parse(p: &mut Parser<'t>, _level: Self::Prec) -> PResult<Self>
418    where Self: Sized {
419        // <T,*>
420        // let generics = match p.next_if(TKind::Lt)? {
421        //     Ok(_) => p.list(vec![], (), TKind::Comma, TKind::Gt)?,
422        //     Err(_) => vec![],
423        // };
424
425        // Pat
426        let pat = p.parse(PPrec::Alt)?;
427        p.expect(TKind::FatArrow)?;
428        let body = p.parse(Prec::Body.value())?;
429
430        Ok(Self(pat, body))
431    }
432}
433
434/// Parses a `for` loop expression
435fn parse_for(p: &mut Parser<'_>, _level: ()) -> PResult<Expr> {
436    // for Pat
437    let pat = p.consume().parse(PPrec::Tuple)?;
438    // in Expr
439    let iter: At<Expr> = p.expect(TKind::In)?.parse(Prec::Logical.next())?;
440    // Expr
441    let pass: At<Expr> = p.parse(Prec::Body.next())?;
442    let pspan = pass.1;
443    // else Expr?
444    let fail = match p.next_if(TKind::Else).allow_eof()? {
445        Some(Ok(_)) => p.parse(Prec::Body.next())?,
446        _ => Expr::Op(Op::Tuple, vec![]).at(pspan),
447    };
448    /*
449    TODO: desugar for into loop-match:
450    for `pat in `iter `pass else `fail
451    ==>
452    match (`iter).into_iter() {
453        #iter => loop match #iter.next() {
454            None => break `fail,
455            Some(`pat) => `pass,
456        },
457    }
458    */
459
460    Ok(Expr::Bind(Box::new(Bind(
461        BindOp::For,
462        vec![],
463        pat,
464        vec![iter, pass, fail],
465    ))))
466}
467
468/// Returns the [BindOp], [pattern precedence](PPrec), [arrow TKind](TKind), [body precedence](Prec),
469/// and [else precedence](Prec), (if applicable,) which controls the parsing of Bind expressions.
470#[rustfmt::skip]
471#[allow(clippy::type_complexity)]
472fn from_bind(p: &mut Parser<'_>) -> PResult<(BindOp, PPrec, Option<TKind>, Option<Prec>, Option<Prec>)> {
473    let bk = match p.peek()?.kind {
474        // Token            Operator        Pat prec      Body Token             Body prec            Else prec
475        TKind::Let =>    (BindOp::Let,    PPrec::Tuple, Some(TKind::Eq),       Some(Prec::Tuple),  Some(Prec::Body)),
476        TKind::Type =>   (BindOp::Type,   PPrec::Alt,   Some(TKind::Eq),       Some(Prec::Tuple),  None),
477        TKind::Struct => (BindOp::Struct, PPrec::Tuple, None,                  None,               None),
478        TKind::Enum =>   (BindOp::Enum,   PPrec::Tuple, None,                  None,               None),
479        TKind::Fn =>     (BindOp::Fn,     PPrec::Fn,    None,                  Some(Prec::Body),   None),
480        TKind::Mod =>    (BindOp::Mod,    PPrec::Max,   None,                  Some(Prec::Body),   None),
481        TKind::Impl =>   (BindOp::Impl,   PPrec::Fn,    None,                  Some(Prec::Body),   None),
482        other => return Err(ParseError::NotBind(other, p.span()))
483    };
484
485    p.consume();
486    Ok(bk)
487}
488
489impl<'t> Parse<'t> for Bind {
490    type Prec = ();
491
492    fn parse(p: &mut Parser<'t>, _level: Self::Prec) -> PResult<Self> {
493        // let
494        let (level, patp, arrow, bodyp, failp) = from_bind(p)?;
495
496        // <T,*>
497        let generics = match p.next_if(TKind::Lt)? {
498            Ok(_) => p.list(vec![], (), TKind::Comma, TKind::Gt)?,
499            Err(_) => vec![],
500        };
501
502        // Pat
503        let pat = p.parse(patp)?;
504
505        let Some(bodyp) = bodyp else {
506            return Ok(Self(level, generics, pat, vec![]));
507        };
508
509        // `=>` for match, `=` for `let`, `type`
510        if let Some(arrow) = arrow {
511            if p.next_if(arrow).allow_eof()?.is_none_or(|v| v.is_err()) {
512                return Ok(Self(level, generics, pat, vec![]));
513            }
514        } else {
515            // Allow prefix `=`? for the rest of them
516            p.next_if(TKind::Eq).allow_eof()?;
517        }
518
519        // `=` Expr
520        let body = p.parse(bodyp.value())?;
521
522        let Some(failp) = failp else {
523            return Ok(Self(level, generics, pat, vec![body]));
524        };
525
526        // `else` Expr
527        if p.next_if(TKind::Else)
528            .allow_eof()?
529            .is_none_or(|v| v.is_err())
530        {
531            return Ok(Self(level, generics, pat, vec![body]));
532        }
533
534        let fail = p.parse(failp.value())?;
535
536        Ok(Self(level, generics, pat, vec![body, fail]))
537    }
538}
539
540impl<'t> Parse<'t> for MakeArm {
541    type Prec = ();
542
543    fn parse(p: &mut Parser<'t>, _level: ()) -> PResult<Self> {
544        let name = p
545            .next_if(TKind::Identifier)?
546            .map_err(|tk| ParseError::Expected(TKind::Identifier, tk, p.span()))?;
547        Ok(MakeArm(
548            name.lexeme
549                .str()
550                .expect("Identifier should have String")
551                .into(),
552            p.opt_if(Prec::Body.value(), TKind::Colon)?,
553        ))
554    }
555}
cl_parser/parser/expr.rs

cl_parser/parser/
expr.rs
