welly_parser/
ast.rs

1use std::{fmt};
2
3use super::{bracket, expr, stmt, Tree, Location, Loc, Token, Invalid, AST};
4use bracket::{Round, Brace};
5use expr::{Op};
6use stmt::{AssignOp, Verb};
7
8/// Reports an error if `tree` is `None`.
9fn compulsory<T>(
10    tree: &Option<T>,
11    missing: impl FnOnce(),
12) -> Result<&T, Invalid> {
13    Ok(tree.as_ref().ok_or_else(missing)?)
14}
15
16/// Returns the sole element of `array`, if its length is `1`.
17fn only<T>(array: Box<[T]>) -> Result<T, Box<[T]>> {
18    let array: Box<[T; 1]> = array.try_into()?;
19    let [element] = *array;
20    Ok(element)
21}
22
23// ----------------------------------------------------------------------------
24
25/// Represents a comma-separated tuple of `A`s in round brackets.
26///
27/// The `bool` indicates if there is a trailing comma.
28#[derive(Debug, Clone)]
29pub struct Tuple<A>(pub Box<[A]>, pub bool);
30
31impl<A> Tuple<A> {
32    /// If there's no trailing comma and exactly one element, return it.
33    /// Otherwise apply `tuple`.
34    fn bracket_or_tuple(self, tuple: impl FnOnce(Box<[A]>) -> A) -> A {
35        let Tuple(asts, trailing_comma) = self;
36        let asts = if !trailing_comma { only(asts) } else { Err(asts) };
37        asts.unwrap_or_else(|asts| tuple(asts))
38    }
39}
40
41impl<A: AST> AST for Tuple<A> where
42    <A as AST>::Generous: Tree,
43{
44    type Generous = Round;
45
46    fn validate(report: &mut impl FnMut(Location, &str), round: &Self::Generous)
47    -> Result<Self, Invalid> {
48        struct State<'s, R, A> {
49            asts: Vec<A>,
50            report: &'s mut R,
51            is_valid: bool,
52            trailing_comma: bool,
53        }
54        
55        impl<R: FnMut(Location, &str), A> State<'_, R, A> {
56            /// Report an error.
57            fn report(&mut self, loc: Location, msg: &str) {
58                if self.is_valid { (self.report)(loc, msg); }
59                self.is_valid = false;
60            }
61
62            /// Record an `A`.
63            fn push(&mut self, loc: Location, ast: A) {
64                if !self.trailing_comma { self.report(loc, "Missing comma"); }
65                self.asts.push(ast);
66                self.trailing_comma = false;
67            }
68
69            /// Record a comma.
70            fn comma(&mut self, loc: Location) {
71                if self.trailing_comma { self.report(loc, "Missing expression"); }
72                self.trailing_comma = true;
73            }
74        }
75        
76        let mut state = State {asts: Vec::new(), report, is_valid: true, trailing_comma: true};
77        let mut contents = round.0.iter();
78        while let Some(&Token(Loc(ref result, loc))) = contents.next() {
79            match result {
80                Ok(tree) => {
81                    if let Some(tree) = tree.downcast_ref::<A::Generous>() {
82                        if let Ok(ast) = A::validate(state.report, tree) {
83                            state.push(loc, ast);
84                        } else {
85                            state.is_valid = false;
86                        }
87                    } else if **tree == ',' {
88                        state.comma(loc);
89                    } else if state.trailing_comma {
90                        state.report(loc, "Expected an expression");
91                    } else if state.is_valid {
92                        state.report(loc, "Expected a comma");
93                    }
94                },
95                Err(msg) => {
96                    state.report(loc, msg);
97                },
98            }
99        }
100        if state.is_valid {
101            Ok(Self(state.asts.into(), state.trailing_comma))
102        } else { Err(Invalid) }
103    }
104}
105
106// ----------------------------------------------------------------------------
107
108/// A Literal expression, representing a constant value.
109#[derive(Clone)]
110pub enum Literal {
111    Int(Loc<u64>),
112    Char(Loc<char>),
113    Str(Loc<String>),
114}
115
116impl fmt::Debug for Literal {
117    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
118        match self {
119            Self::Int(i) => i.fmt(f),
120            Self::Char(c) => c.fmt(f),
121            Self::Str(s) => s.fmt(f),
122        }
123    }
124}
125
126impl AST for Loc<u64> {
127    type Generous = Loc<String>;
128
129    fn validate(report: &mut impl FnMut(Location, &str), value: &Self::Generous)
130    -> Result<Self, Invalid> {
131        if let Ok(i) = value.0.parse::<u64>() { return Ok(Loc(i, value.1)); }
132        if let Ok(i) = value.0.parse::<i64>() { return Ok(Loc(i as u64, value.1)); }
133        Err(report(value.1, "Invalid integer literal"))?
134    }
135}
136
137// ----------------------------------------------------------------------------
138
139/// An valid identifier.
140///
141/// Identifiers are written with capital and lower-case letters, digits and
142/// underscores, and do not start with a digit.
143#[derive(Clone)]
144pub struct Name(Loc<String>);
145
146impl std::borrow::Borrow<str> for Name {
147    fn borrow(&self) -> &str { self.0.0.borrow() }
148}
149
150impl Name {
151    /// Returns `value` as `Self` if possible.
152    fn maybe_validate(value: &Loc<String>) -> Option<Self> {
153        let mut cs = value.0.chars();
154        if let Some(c) = cs.next() {
155            if !matches!(c, '_' | 'A'..='Z' | 'a'..='z') { return None; }
156            while let Some(c) = cs.next() {
157                if !matches!(c, '_' | '0'..='9' | 'A'..='Z' | 'a'..='z') { return None; }
158            }
159            Some(Self(value.clone()))
160        } else { None }
161    }
162}
163
164impl fmt::Debug for Name {
165    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.0.fmt(f) }
166}
167
168impl AST for Name {
169    type Generous = Loc<String>;
170
171    fn validate(report: &mut impl FnMut(Location, &str), value: &Self::Generous)
172    -> Result<Self, Invalid> {
173        Ok(Name::maybe_validate(value).ok_or_else(|| report(value.1, "Invalid identifier"))?)
174    }
175}
176
177// ----------------------------------------------------------------------------
178
179/// An valid tag.
180///
181/// Tags are written with capital letters, digits and underscores, and do not
182/// start with a digit.
183#[derive(Clone)]
184pub struct Tag(Loc<String>);
185
186impl fmt::Debug for Tag {
187    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.0.fmt(f) }
188}
189
190impl std::borrow::Borrow<str> for Tag {
191    fn borrow(&self) -> &str { self.0.0.borrow() }
192}
193
194impl Tag {
195    /// Returns `value` as `Self` if possible.
196    fn maybe_validate(value: &Loc<String>) -> Option<Self> {
197        let mut cs = value.0.chars();
198        if let Some(c) = cs.next() {
199            if !matches!(c, '_' | 'A'..='Z') { return None; }
200            while let Some(c) = cs.next() {
201                if !matches!(c, '_' | '0'..='9' | 'A'..='Z') { return None; }
202            }
203            Some(Self(value.clone()))
204        } else { None }
205    }
206
207    /// Returns `value` as `Self` if possible.
208    fn maybe_validate_expr(tree: &expr::Expr) -> Option<Self> {
209        if let expr::Expr::Name(s) = tree { Self::maybe_validate(s) } else { None }
210    }
211}
212
213// ----------------------------------------------------------------------------
214
215/// An expression that can appear on the left-hand side of an assignment.
216#[derive(Debug, Clone)]
217pub enum LExpr {
218    Name(Name),
219    Literal(Literal),
220    Tuple(Loc<Box<[LExpr]>>),
221    Field(Box<LExpr>, Name),
222    Tag(Tag, Loc<Box<[LExpr]>>),
223    Cast(Location, Box<LExpr>, Box<Type>),
224}
225
226impl AST for LExpr {
227    type Generous = expr::Expr;
228
229    fn validate(report: &mut impl FnMut(Location, &str), tree: &Self::Generous)
230    -> Result<Self, Invalid> {
231        Ok(match tree {
232            expr::Expr::Char(c) => Self::Literal(Literal::Char(*c)),
233            expr::Expr::String(s) => Self::Literal(Literal::Str(s.clone())),
234            expr::Expr::Name(s) => {
235                let c = s.0.chars().next().expect("Should be non-empty");
236                if matches!(c, '0'..='9') {
237                    Self::Literal(Literal::Int(Loc::<u64>::validate(report, s)?))
238                } else {
239                    Self::Name(Name::validate(report, s)?)
240                }
241            },
242            expr::Expr::Round(round) => {
243                let loc = Location::EVERYWHERE; // TODO.
244                Tuple::validate(report, round)?.bracket_or_tuple(
245                    |asts| Self::Tuple(Loc(asts, loc))
246                )
247            },
248            expr::Expr::Function(_name, params, _return_type, _body) => {
249                Err(report(params.1, "Expression is not assignable"))?
250            },
251            expr::Expr::Op(left, op, right) => {
252                match op.0 {
253                    Op::Cast => {
254                        let left = compulsory(left, || report(op.1, "Missing left operand"))?;
255                        let right = compulsory(right, || report(op.1, "Missing right operand"))?;
256                        let left = Box::<Self>::validate(report, &*left);
257                        let right = Box::<Type>::validate(report, &*right);
258                        Self::Cast(op.1, left?, right?)
259                    },
260                    Op::Missing => Err(report(op.1, "Missing operator"))?,
261                    _ => Err(report(op.1, "This operator does not make an assignable expression"))?,
262                }
263            },
264            expr::Expr::Field(object, field) => {
265                let object = compulsory(object, || report(field.1, "Missing expression before `.field`"))?;
266                let object = Box::<Self>::validate(report, &*object);
267                let field = Name::validate(report, field);
268                Self::Field(object?, field?)
269            },
270            expr::Expr::Call(tag, Loc(args, loc)) => {
271                let tag = tag.as_ref().expect("Should have parsed as a tuple");
272                let args = Tuple::validate(report, args);
273                if let Some(tag) = Tag::maybe_validate_expr(tag) {
274                    Self::Tag(tag, Loc(args?.0, *loc))
275                } else { Err(report(*loc, "Expression is not assignable"))? }
276            },
277        })
278    }
279}
280
281// ----------------------------------------------------------------------------
282
283/// An expression.
284#[derive(Debug, Clone)]
285pub enum Expr {
286    Name(Name),
287    Literal(Literal),
288    Tuple(Loc<Box<[Expr]>>),
289    Unary(Loc<Op>, Box<Expr>),
290    Binary(Loc<Op>, Box<Expr>, Box<Expr>),
291    Function(Option<Name>, Loc<Box<[LExpr]>>, Option<Box<Type>>, Block),
292    FunctionType(Option<Name>, Loc<Box<[LExpr]>>, Option<Box<Type>>),
293    Field(Box<Expr>, Name),
294    Tag(Tag, Loc<Box<[Expr]>>),
295    Call(Box<Expr>, Loc<Box<[Expr]>>),
296    Cast(Location, Box<Expr>, Box<Expr>),
297}
298
299impl AST for Expr {
300    type Generous = expr::Expr;
301
302    fn validate(report: &mut impl FnMut(Location, &str), tree: &Self::Generous)
303    -> Result<Self, Invalid> {
304        Ok(match tree {
305            expr::Expr::Char(c) => Self::Literal(Literal::Char(*c)),
306            expr::Expr::String(s) => Self::Literal(Literal::Str(s.clone())),
307            expr::Expr::Name(s) => {
308                let c = s.0.chars().next().expect("Should be non-empty");
309                if matches!(c, '0'..='9') {
310                    Self::Literal(Literal::Int(Loc::<u64>::validate(report, s)?))
311                } else {
312                    Self::Name(Name::validate(report, s)?)
313                }
314            },
315            expr::Expr::Round(round) => {
316                let loc = Location::EVERYWHERE; // TODO.
317                Tuple::validate(report, round)?.bracket_or_tuple(
318                    |asts| Self::Tuple(Loc(asts, loc))
319                )
320            },
321            expr::Expr::Function(name, Loc(params, loc), return_type, body) => {
322                let name = Option::<Name>::validate(report, name);
323                let params = Tuple::validate(report, params);
324                let return_type = Option::<Box<Type>>::validate(report, return_type);
325                if let Some(body) = body {
326                    let body = Block::validate(report, body);
327                    Self::Function(name?, Loc(params?.0, *loc), return_type?, body?)
328                } else {
329                    Self::FunctionType(name?, Loc(params?.0, *loc), return_type?)
330                }
331            },
332            expr::Expr::Op(left, op, right) => {
333                match op.0.precedence() {
334                    (None, None) => panic!("Nonfix operator"),
335                    (Some(_), None) => {
336                        let left = compulsory(left, || report(op.1, "Missing left operand"))?;
337                        let left = Box::<Self>::validate(report, left);
338                        if !right.is_none() { Err(report(op.1, "Unexpected right operand"))? }
339                        Self::Unary(*op, left?)
340                    },
341                    (None, Some(_)) => {
342                        let right = compulsory(right, || report(op.1, "Missing right operand"))?;
343                        let right = Box::<Self>::validate(report, right);
344                        if !left.is_none() { Err(report(op.1, "Unexpected right operand"))? }
345                        Self::Unary(*op, right?)
346                    },
347                    (Some(_), Some(_)) => {
348                        let left = compulsory(left, || report(op.1, "Missing left operand"))?;
349                        let left = Box::<Self>::validate(report, left);
350                        let right = compulsory(right, || report(op.1, "Missing right operand"))?;
351                        let right = Box::<Self>::validate(report, right);
352                        match op.0 {
353                            Op::Cast => Self::Cast(op.1, left?, right?),
354                            Op::Missing => Err(report(op.1, "Missing operator"))?,
355                            _ => Self::Binary(*op, left?, right?),
356                        }
357                    },
358                }
359            },
360            expr::Expr::Field(object, field) => {
361                let object = compulsory(object, || report(field.1, "Missing expression before `.field`"))?;
362                let object = Box::<Self>::validate(report, object);
363                let field = Name::validate(report, field);
364                Self::Field(object?, field?)
365            },
366            expr::Expr::Call(fn_, Loc(args, loc)) => {
367                let fn_ = fn_.as_ref().expect("Should have parsed as a tuple");
368                let args = Tuple::validate(report, args);
369                if let Some(tag) = Tag::maybe_validate_expr(fn_) {
370                    Self::Tag(tag, Loc(args?.0, *loc))
371                } else {
372                    let fn_ = Box::<Expr>::validate(report, fn_);
373                    Self::Call(fn_?, Loc(args?.0, *loc))
374                }
375            },
376        })
377    }
378}
379
380/// An [`Expr`] used as a type.
381type Type = Expr;
382
383// ----------------------------------------------------------------------------
384
385/// A `case` clause.
386#[derive(Debug, Clone)]
387pub struct Case(Location, Box<LExpr>, Block);
388
389impl AST for Case {
390    type Generous = stmt::Case;
391
392    fn validate(report: &mut impl FnMut(Location, &str), case: &Self::Generous)
393    -> Result<Self, Invalid> {
394        let stmt::Case(loc, pattern, body) = case;
395        let pattern = compulsory(pattern, || report(*loc, "Missing pattern after `case`"))?;
396        let pattern = Box::<LExpr>::validate(report, pattern);
397        let body = Block::validate(report, body);
398        Ok(Case(*loc, pattern?, body?))
399    }
400}
401
402// ----------------------------------------------------------------------------
403
404/// An `else` clause.
405#[derive(Debug, Clone)]
406pub struct Else(Location, Block);
407
408impl AST for Else {
409    type Generous = stmt::Else;
410
411    fn validate(report: &mut impl FnMut(Location, &str), else_: &Self::Generous)
412    -> Result<Self, Invalid> {
413        let stmt::Else(loc, body) = else_;
414        Ok(Else(*loc, Block::validate(report, body)?))
415    }
416}
417
418// ----------------------------------------------------------------------------
419
420/// A statement.
421#[derive(Debug, Clone)]
422pub enum Stmt {
423    Empty,
424    Expr(Box<Expr>),
425    Let(Box<LExpr>, Location, Box<Expr>),
426    Set(Box<LExpr>, Location, Box<Expr>),
427    Mut(Box<LExpr>, Loc<Op>, Box<Expr>),
428    If(Location, Box<Expr>, Block, Option<Else>),
429    While(Location, Box<Expr>, Block, Option<Else>),
430    For(Location, Box<LExpr>, Box<Expr>, Block, Option<Else>),
431    Switch(Location, Box<Expr>, Box<[Case]>, Option<Else>),
432    Break(Location),
433    Continue(Location),
434    Return(Location, Option<Box<Expr>>),
435    Throw(Location, Box<Expr>),
436    Assert(Location, Box<Expr>),
437    Assume(Location, Box<Expr>),
438}
439
440impl AST for Stmt {
441    type Generous = stmt::Stmt;
442
443    fn validate(report: &mut impl FnMut(Location, &str), tree: &Self::Generous)
444    -> Result<Self, Invalid> {
445        Ok(match tree {
446            stmt::Stmt::Expr(expr) => {
447                if let Some(expr) = expr.as_ref() {
448                    Self::Expr(Box::<Expr>::validate(report, expr)?)
449                } else {
450                    Self::Empty
451                }
452            },
453            stmt::Stmt::Assign(lhs, Loc(op, loc), rhs) => {
454                let lhs = compulsory(lhs,
455                    || report(*loc, "Missing pattern on left-hand side of assignment")
456                )?;
457                let rhs = compulsory(rhs,
458                    || report(*loc, "Missing expression on right-hand side of assignment")
459                )?;
460                let lhs = Box::<LExpr>::validate(report, lhs);
461                let rhs = Box::<Expr>::validate(report, rhs);
462                match op {
463                    AssignOp::Let => Self::Let(lhs?, *loc, rhs?),
464                    AssignOp::Set => Self::Set(lhs?, *loc, rhs?),
465                    AssignOp::Op(op) => Self::Mut(lhs?, Loc(*op, *loc), rhs?),
466                }
467            },
468            stmt::Stmt::If(loc, condition, body, else_) => {
469                let condition = compulsory(condition, || report(*loc, "Missing condition"))?;
470                let condition = Box::<Expr>::validate(report, condition);
471                let body = Block::validate(report, body);
472                let else_ = Option::<Else>::validate(report, else_);
473                Self::If(*loc, condition?, body?, else_?)
474            },
475            stmt::Stmt::While(loc, condition, body, else_) => {
476                let condition = compulsory(condition, || report(*loc, "Missing condition"))?;
477                let condition = Box::<Expr>::validate(report, condition);
478                let body = Block::validate(report, body);
479                let else_ = Option::<Else>::validate(report, else_);
480                Self::While(*loc, condition?, body?, else_?)
481            },
482            stmt::Stmt::For(loc, item_in_sequence, body, else_) => {
483                let item_in_sequence = compulsory(item_in_sequence,
484                    || report(*loc, "Missing `in` after `for`")
485                )?;
486                if let expr::Expr::Op(item, Loc(Op::In, in_loc), sequence) = &**item_in_sequence {
487                    let item = compulsory(item,
488                        || report(*loc, "Missing item pattern after `for`")
489                    )?;
490                    let sequence = compulsory(sequence,
491                        || report(*in_loc, "Missing sequence expression after `for ... in`")
492                    )?;
493                    let item = Box::<LExpr>::validate(report, item);
494                    let sequence = Box::<Expr>::validate(report, sequence);
495                    let body = Block::validate(report, body);
496                    let else_ = Option::<Else>::validate(report, else_);
497                    Self::For(*loc, item?, sequence?, body?, else_?)
498                } else { Err(report(*loc, "Missing `in` after for"))? }
499            },
500            stmt::Stmt::Switch(loc, discriminant, cases, else_) => {
501                let discriminant = compulsory(discriminant, || report(*loc, "Missing condition"))?;
502                let discriminant = Box::<Expr>::validate(report, discriminant);
503                let cases: Vec<Result<Case, Invalid>> = cases.iter().map(
504                    |case| Case::validate(report, case)
505                ).collect();
506                let cases: Result<Box<[Case]>, Invalid> = cases.into_iter().collect();
507                let else_ = Option::<Else>::validate(report, else_);
508                Self::Switch(*loc, discriminant?, cases?, else_?)
509            },
510            stmt::Stmt::Verb(Loc(verb, loc), expr) => match verb {
511                Verb::Break => {
512                    if let Some(_) = expr { Err(report(*loc, "Unexpected expression after `break`"))? }
513                    Self::Break(*loc)
514                },
515                Verb::Continue => {
516                    if let Some(_) = expr { Err(report(*loc, "Unexpected expression after `continue`"))? }
517                    Self::Continue(*loc)
518                },
519                Verb::Return => {
520                    Self::Return(*loc, Option::<Box<Expr>>::validate(report, expr)?)
521                },
522                Verb::Throw => {
523                    let expr = compulsory(expr, || report(*loc, "Missing expression after `throw`"))?;
524                    Self::Throw(*loc, Box::<Expr>::validate(report, expr)?)
525                },
526                Verb::Assert => {
527                    let expr = compulsory(expr, || report(*loc, "Missing expression after `assert`"))?;
528                    Self::Assert(*loc, Box::<Expr>::validate(report, expr)?)
529                },
530                Verb::Assume => {
531                    let expr = compulsory(expr, || report(*loc, "Missing expression after `assume`"))?;
532                    Self::Assume(*loc, Box::<Expr>::validate(report, expr)?)
533                },
534            },
535        })
536    }
537}
538
539// ----------------------------------------------------------------------------
540
541/// A block of [`Stmt`]s.
542#[derive(Debug, Clone)]
543pub struct Block(Box<[Stmt]>);
544
545impl AST for Block {
546    type Generous = Brace;
547
548    fn validate(report: &mut impl FnMut(Location, &str), tree: &Brace)
549    -> Result<Self, Invalid> {
550        let mut ret = Vec::new();
551        let mut is_valid = true;
552        for Token(Loc(result, loc)) in &tree.0 {
553            match result {
554                Ok(tree) => {
555                    if let Some(tree) = tree.downcast_ref::<stmt::Stmt>() {
556                        ret.push(Stmt::validate(report, tree)?);
557                    } else {
558                        report(*loc, "Expected a statement");
559                        is_valid = false;
560                    }
561                },
562                Err(msg) => { report(*loc, msg); is_valid = false; }
563            }
564        }
565        if is_valid { Ok(Block(ret.into())) } else { Err(Invalid) }
566    }
567}
welly_parser/ast.rs

welly_parser/
ast.rs
