cranelift_isle/
parser.rs

1//! Parser for ISLE language.
2
3use crate::ast::*;
4use crate::error::{Error, Span};
5use crate::lexer::{Lexer, Pos, Token};
6
7type Result<T> = std::result::Result<T, Error>;
8
9/// Parse the top-level ISLE definitions and return their AST.
10pub fn parse(lexer: Lexer) -> Result<Vec<Def>> {
11    let parser = Parser::new(lexer);
12    parser.parse_defs()
13}
14
15/// The ISLE parser.
16///
17/// Takes in a lexer and creates an AST.
18#[derive(Clone, Debug)]
19struct Parser<'a> {
20    lexer: Lexer<'a>,
21}
22
23/// Used during parsing a `(rule ...)` to encapsulate some form that
24/// comes after the top-level pattern: an if-let clause, or the final
25/// top-level expr.
26enum IfLetOrExpr {
27    IfLet(IfLet),
28    Expr(Expr),
29}
30
31impl<'a> Parser<'a> {
32    /// Construct a new parser from the given lexer.
33    pub fn new(lexer: Lexer<'a>) -> Parser<'a> {
34        Parser { lexer }
35    }
36
37    fn error(&self, pos: Pos, msg: String) -> Error {
38        Error::ParseError {
39            msg,
40            span: Span::new_single(pos),
41        }
42    }
43
44    fn expect<F: Fn(&Token) -> bool>(&mut self, f: F) -> Result<Token> {
45        if let Some(&(pos, ref peek)) = self.lexer.peek() {
46            if !f(peek) {
47                return Err(self.error(pos, format!("Unexpected token {peek:?}")));
48            }
49            Ok(self.lexer.next()?.unwrap().1)
50        } else {
51            Err(self.error(self.lexer.pos(), "Unexpected EOF".to_string()))
52        }
53    }
54
55    fn eat<F: Fn(&Token) -> bool>(&mut self, f: F) -> Result<Option<Token>> {
56        if let Some(&(_pos, ref peek)) = self.lexer.peek() {
57            if !f(peek) {
58                return Ok(None);
59            }
60            Ok(Some(self.lexer.next()?.unwrap().1))
61        } else {
62            Ok(None) // EOF
63        }
64    }
65
66    fn is<F: Fn(&Token) -> bool>(&self, f: F) -> bool {
67        if let Some((_, peek)) = self.lexer.peek() {
68            f(peek)
69        } else {
70            false
71        }
72    }
73
74    fn pos(&self) -> Pos {
75        self.lexer
76            .peek()
77            .map_or_else(|| self.lexer.pos(), |(pos, _)| *pos)
78    }
79
80    fn is_lparen(&self) -> bool {
81        self.is(|tok| *tok == Token::LParen)
82    }
83    fn is_rparen(&self) -> bool {
84        self.is(|tok| *tok == Token::RParen)
85    }
86    fn is_at(&self) -> bool {
87        self.is(|tok| *tok == Token::At)
88    }
89    fn is_sym(&self) -> bool {
90        self.is(Token::is_sym)
91    }
92    fn is_int(&self) -> bool {
93        self.is(Token::is_int)
94    }
95
96    fn is_const(&self) -> bool {
97        self.is(|tok| match tok {
98            Token::Symbol(tok_s) if tok_s.starts_with('$') => true,
99            _ => false,
100        })
101    }
102
103    fn is_spec_bit_vector(&self) -> bool {
104        self.is(|tok| match tok {
105            Token::Symbol(tok_s) if tok_s.starts_with("#x") || tok_s.starts_with("#b") => true,
106            _ => false,
107        })
108    }
109
110    fn is_spec_bool(&self) -> bool {
111        self.is(|tok| match tok {
112            Token::Symbol(tok_s) if tok_s == "true" || tok_s == "false" => true,
113            _ => false,
114        })
115    }
116
117    fn expect_lparen(&mut self) -> Result<()> {
118        self.expect(|tok| *tok == Token::LParen).map(|_| ())
119    }
120    fn expect_rparen(&mut self) -> Result<()> {
121        self.expect(|tok| *tok == Token::RParen).map(|_| ())
122    }
123    fn expect_at(&mut self) -> Result<()> {
124        self.expect(|tok| *tok == Token::At).map(|_| ())
125    }
126
127    fn expect_symbol(&mut self) -> Result<String> {
128        match self.expect(Token::is_sym)? {
129            Token::Symbol(s) => Ok(s),
130            _ => unreachable!(),
131        }
132    }
133
134    fn eat_sym_str(&mut self, s: &str) -> Result<bool> {
135        self.eat(|tok| match tok {
136            Token::Symbol(tok_s) if tok_s == s => true,
137            _ => false,
138        })
139        .map(|token| token.is_some())
140    }
141
142    fn expect_int(&mut self) -> Result<i128> {
143        match self.expect(Token::is_int)? {
144            Token::Int(i) => Ok(i),
145            _ => unreachable!(),
146        }
147    }
148
149    fn parse_defs(mut self) -> Result<Vec<Def>> {
150        let mut defs = vec![];
151        while !self.lexer.eof() {
152            defs.push(self.parse_def()?);
153        }
154        Ok(defs)
155    }
156
157    fn parse_def(&mut self) -> Result<Def> {
158        self.expect_lparen()?;
159        let pos = self.pos();
160        let def = match &self.expect_symbol()?[..] {
161            "pragma" => Def::Pragma(self.parse_pragma()?),
162            "type" => Def::Type(self.parse_type()?),
163            "decl" => Def::Decl(self.parse_decl()?),
164            "spec" => Def::Spec(self.parse_spec()?),
165            "model" => Def::Model(self.parse_model()?),
166            "form" => Def::Form(self.parse_form()?),
167            "instantiate" => Def::Instantiation(self.parse_instantiation()?),
168            "rule" => Def::Rule(self.parse_rule()?),
169            "extractor" => Def::Extractor(self.parse_etor()?),
170            "extern" => Def::Extern(self.parse_extern()?),
171            "convert" => Def::Converter(self.parse_converter()?),
172            s => {
173                return Err(self.error(pos, format!("Unexpected identifier: {s}")));
174            }
175        };
176        self.expect_rparen()?;
177        Ok(def)
178    }
179
180    fn str_to_ident(&self, pos: Pos, s: &str) -> Result<Ident> {
181        let first = s
182            .chars()
183            .next()
184            .ok_or_else(|| self.error(pos, "empty symbol".into()))?;
185        if !first.is_alphabetic() && first != '_' && first != '$' {
186            return Err(self.error(
187                pos,
188                format!("Identifier '{s}' does not start with letter or _ or $"),
189            ));
190        }
191        if s.chars()
192            .skip(1)
193            .any(|c| !c.is_alphanumeric() && c != '_' && c != '.' && c != '$')
194        {
195            return Err(self.error(
196                pos,
197                format!("Identifier '{s}' contains invalid character (not a-z, A-Z, 0-9, _, ., $)"),
198            ));
199        }
200        Ok(Ident(s.to_string(), pos))
201    }
202
203    fn parse_ident(&mut self) -> Result<Ident> {
204        let pos = self.pos();
205        let s = self.expect_symbol()?;
206        self.str_to_ident(pos, &s)
207    }
208
209    fn parse_const(&mut self) -> Result<Ident> {
210        let pos = self.pos();
211        let ident = self.parse_ident()?;
212        if let Some(s) = ident.0.strip_prefix('$') {
213            Ok(Ident(s.to_string(), ident.1))
214        } else {
215            Err(self.error(
216                pos,
217                "Not a constant identifier; must start with a '$'".to_string(),
218            ))
219        }
220    }
221
222    fn parse_pragma(&mut self) -> Result<Pragma> {
223        let ident = self.parse_ident()?;
224        // currently, no pragmas are defined, but the infrastructure is useful to keep around
225        let pragma = ident.0.as_str();
226        Err(self.error(ident.1, format!("Unknown pragma '{pragma}'")))
227    }
228
229    fn parse_type(&mut self) -> Result<Type> {
230        let pos = self.pos();
231        let name = self.parse_ident()?;
232
233        let mut is_extern = false;
234        let mut is_nodebug = false;
235
236        while self.lexer.peek().map_or(false, |(_pos, tok)| tok.is_sym()) {
237            let sym = self.expect_symbol()?;
238            if sym == "extern" {
239                is_extern = true;
240            } else if sym == "nodebug" {
241                is_nodebug = true;
242            } else {
243                return Err(self.error(
244                    self.pos(),
245                    format!("unknown type declaration modifier: {sym}"),
246                ));
247            }
248        }
249
250        let ty = self.parse_typevalue()?;
251        Ok(Type {
252            name,
253            is_extern,
254            is_nodebug,
255            ty,
256            pos,
257        })
258    }
259
260    fn parse_typevalue(&mut self) -> Result<TypeValue> {
261        let pos = self.pos();
262        self.expect_lparen()?;
263        if self.eat_sym_str("primitive")? {
264            let primitive_ident = self.parse_ident()?;
265            self.expect_rparen()?;
266            Ok(TypeValue::Primitive(primitive_ident, pos))
267        } else if self.eat_sym_str("enum")? {
268            let mut variants = vec![];
269            while !self.is_rparen() {
270                let variant = self.parse_type_variant()?;
271                variants.push(variant);
272            }
273            self.expect_rparen()?;
274            Ok(TypeValue::Enum(variants, pos))
275        } else {
276            Err(self.error(pos, "Unknown type definition".to_string()))
277        }
278    }
279
280    fn parse_type_variant(&mut self) -> Result<Variant> {
281        if self.is_sym() {
282            let pos = self.pos();
283            let name = self.parse_ident()?;
284            Ok(Variant {
285                name,
286                fields: vec![],
287                pos,
288            })
289        } else {
290            let pos = self.pos();
291            self.expect_lparen()?;
292            let name = self.parse_ident()?;
293            let mut fields = vec![];
294            while !self.is_rparen() {
295                fields.push(self.parse_type_field()?);
296            }
297            self.expect_rparen()?;
298            Ok(Variant { name, fields, pos })
299        }
300    }
301
302    fn parse_type_field(&mut self) -> Result<Field> {
303        let pos = self.pos();
304        self.expect_lparen()?;
305        let name = self.parse_ident()?;
306        let ty = self.parse_ident()?;
307        self.expect_rparen()?;
308        Ok(Field { name, ty, pos })
309    }
310
311    fn parse_decl(&mut self) -> Result<Decl> {
312        let pos = self.pos();
313
314        let pure = self.eat_sym_str("pure")?;
315        let multi = self.eat_sym_str("multi")?;
316        let partial = self.eat_sym_str("partial")?;
317
318        let term = self.parse_ident()?;
319
320        self.expect_lparen()?;
321        let mut arg_tys = vec![];
322        while !self.is_rparen() {
323            arg_tys.push(self.parse_ident()?);
324        }
325        self.expect_rparen()?;
326
327        let ret_ty = self.parse_ident()?;
328
329        Ok(Decl {
330            term,
331            arg_tys,
332            ret_ty,
333            pure,
334            multi,
335            partial,
336            pos,
337        })
338    }
339
340    fn parse_spec(&mut self) -> Result<Spec> {
341        let pos = self.pos();
342        self.expect_lparen()?; // term with args: (spec (<term> <args>) (provide ...) ...)
343        let term = self.parse_ident()?;
344        let mut args = vec![];
345        while !self.is_rparen() {
346            args.push(self.parse_ident()?);
347        }
348        self.expect_rparen()?; // end term with args
349
350        self.expect_lparen()?; // provide
351        if !self.eat_sym_str("provide")? {
352            return Err(self.error(
353                pos,
354                "Invalid spec: expected (spec (<term> <args>) (provide ...) ...)".to_string(),
355            ));
356        };
357        let mut provides = vec![];
358        while !self.is_rparen() {
359            provides.push(self.parse_spec_expr()?);
360        }
361        self.expect_rparen()?; // end provide
362
363        let requires = if self.is_lparen() {
364            self.expect_lparen()?;
365            if !self.eat_sym_str("require")? {
366                return Err(self.error(
367                    pos,
368                    "Invalid spec: expected (spec (<term> <args>) (provide ...) (require ...))"
369                        .to_string(),
370                ));
371            }
372            let mut require = vec![];
373            while !self.is_rparen() {
374                require.push(self.parse_spec_expr()?);
375            }
376            self.expect_rparen()?; // end provide
377            require
378        } else {
379            vec![]
380        };
381
382        Ok(Spec {
383            term: term,
384            args,
385            provides,
386            requires,
387        })
388    }
389
390    fn parse_spec_expr(&mut self) -> Result<SpecExpr> {
391        let pos = self.pos();
392        if self.is_spec_bit_vector() {
393            let (val, width) = self.parse_spec_bit_vector()?;
394            return Ok(SpecExpr::ConstBitVec { val, width, pos });
395        } else if self.is_int() {
396            return Ok(SpecExpr::ConstInt {
397                val: self.expect_int()?,
398                pos,
399            });
400        } else if self.is_spec_bool() {
401            let val = self.parse_spec_bool()?;
402            return Ok(SpecExpr::ConstBool { val, pos });
403        } else if self.is_sym() {
404            let var = self.parse_ident()?;
405            return Ok(SpecExpr::Var { var, pos });
406        } else if self.is_lparen() {
407            self.expect_lparen()?;
408            if self.eat_sym_str("switch")? {
409                let mut args = vec![];
410                args.push(self.parse_spec_expr()?);
411                while !(self.is_rparen()) {
412                    self.expect_lparen()?;
413                    let l = Box::new(self.parse_spec_expr()?);
414                    let r = Box::new(self.parse_spec_expr()?);
415                    self.expect_rparen()?;
416                    args.push(SpecExpr::Pair { l, r });
417                }
418                self.expect_rparen()?;
419                return Ok(SpecExpr::Op {
420                    op: SpecOp::Switch,
421                    args,
422                    pos,
423                });
424            }
425            if self.is_sym() && !self.is_spec_bit_vector() {
426                let sym = self.expect_symbol()?;
427                if let Ok(op) = self.parse_spec_op(sym.as_str()) {
428                    let mut args: Vec<SpecExpr> = vec![];
429                    while !self.is_rparen() {
430                        args.push(self.parse_spec_expr()?);
431                    }
432                    self.expect_rparen()?;
433                    return Ok(SpecExpr::Op { op, args, pos });
434                };
435                let ident = self.str_to_ident(pos, &sym)?;
436                if self.is_rparen() {
437                    self.expect_rparen()?;
438                    return Ok(SpecExpr::Enum { name: ident });
439                };
440            }
441            // Unit
442            if self.is_rparen() {
443                self.expect_rparen()?;
444                return Ok(SpecExpr::ConstUnit { pos });
445            }
446        }
447        Err(self.error(pos, "Unexpected spec expression".into()))
448    }
449
450    fn parse_spec_op(&mut self, s: &str) -> Result<SpecOp> {
451        let pos = self.pos();
452        match s {
453            "=" => Ok(SpecOp::Eq),
454            "and" => Ok(SpecOp::And),
455            "not" => Ok(SpecOp::Not),
456            "=>" => Ok(SpecOp::Imp),
457            "or" => Ok(SpecOp::Or),
458            "<=" => Ok(SpecOp::Lte),
459            "<" => Ok(SpecOp::Lt),
460            ">=" => Ok(SpecOp::Gte),
461            ">" => Ok(SpecOp::Gt),
462            "bvnot" => Ok(SpecOp::BVNot),
463            "bvand" => Ok(SpecOp::BVAnd),
464            "bvor" => Ok(SpecOp::BVOr),
465            "bvxor" => Ok(SpecOp::BVXor),
466            "bvneg" => Ok(SpecOp::BVNeg),
467            "bvadd" => Ok(SpecOp::BVAdd),
468            "bvsub" => Ok(SpecOp::BVSub),
469            "bvmul" => Ok(SpecOp::BVMul),
470            "bvudiv" => Ok(SpecOp::BVUdiv),
471            "bvurem" => Ok(SpecOp::BVUrem),
472            "bvsdiv" => Ok(SpecOp::BVSdiv),
473            "bvsrem" => Ok(SpecOp::BVSrem),
474            "bvshl" => Ok(SpecOp::BVShl),
475            "bvlshr" => Ok(SpecOp::BVLshr),
476            "bvashr" => Ok(SpecOp::BVAshr),
477            "bvsaddo" => Ok(SpecOp::BVSaddo),
478            "bvule" => Ok(SpecOp::BVUle),
479            "bvult" => Ok(SpecOp::BVUlt),
480            "bvugt" => Ok(SpecOp::BVUgt),
481            "bvuge" => Ok(SpecOp::BVUge),
482            "bvslt" => Ok(SpecOp::BVSlt),
483            "bvsle" => Ok(SpecOp::BVSle),
484            "bvsgt" => Ok(SpecOp::BVSgt),
485            "bvsge" => Ok(SpecOp::BVSge),
486            "rotr" => Ok(SpecOp::Rotr),
487            "rotl" => Ok(SpecOp::Rotl),
488            "extract" => Ok(SpecOp::Extract),
489            "zero_ext" => Ok(SpecOp::ZeroExt),
490            "sign_ext" => Ok(SpecOp::SignExt),
491            "concat" => Ok(SpecOp::Concat),
492            "conv_to" => Ok(SpecOp::ConvTo),
493            "int2bv" => Ok(SpecOp::Int2BV),
494            "bv2int" => Ok(SpecOp::BV2Int),
495            "widthof" => Ok(SpecOp::WidthOf),
496            "if" => Ok(SpecOp::If),
497            "switch" => Ok(SpecOp::Switch),
498            "subs" => Ok(SpecOp::Subs),
499            "popcnt" => Ok(SpecOp::Popcnt),
500            "rev" => Ok(SpecOp::Rev),
501            "cls" => Ok(SpecOp::Cls),
502            "clz" => Ok(SpecOp::Clz),
503            "load_effect" => Ok(SpecOp::LoadEffect),
504            "store_effect" => Ok(SpecOp::StoreEffect),
505            x => Err(self.error(pos, format!("Not a valid spec operator: {x}"))),
506        }
507    }
508
509    fn parse_spec_bit_vector(&mut self) -> Result<(i128, i8)> {
510        let pos = self.pos();
511        let s = self.expect_symbol()?;
512        if let Some(s) = s.strip_prefix("#b") {
513            match i128::from_str_radix(s, 2) {
514                Ok(i) => Ok((i, s.len() as i8)),
515                Err(_) => Err(self.error(pos, "Not a constant binary bit vector".to_string())),
516            }
517        } else if let Some(s) = s.strip_prefix("#x") {
518            match i128::from_str_radix(s, 16) {
519                Ok(i) => Ok((i, (s.len() as i8) * 4)),
520                Err(_) => Err(self.error(pos, "Not a constant hex bit vector".to_string())),
521            }
522        } else {
523            Err(self.error(
524                pos,
525                "Not a constant bit vector; must start with `#x` (hex) or `#b` (binary)"
526                    .to_string(),
527            ))
528        }
529    }
530
531    fn parse_spec_bool(&mut self) -> Result<bool> {
532        let pos = self.pos();
533        let s = self.expect_symbol()?;
534        match s.as_str() {
535            "true" => Ok(true),
536            "false" => Ok(false),
537            x => Err(self.error(pos, format!("Not a valid spec boolean: {x}"))),
538        }
539    }
540
541    fn parse_model(&mut self) -> Result<Model> {
542        let pos = self.pos();
543        let name = self.parse_ident()?;
544        self.expect_lparen()?; // body
545        let val = if self.eat_sym_str("type")? {
546            let ty = self.parse_model_type();
547            ModelValue::TypeValue(ty?)
548        } else if self.eat_sym_str("enum")? {
549            let mut variants = vec![];
550            let mut has_explicit_value = false;
551            let mut implicit_idx = None;
552
553            while !self.is_rparen() {
554                self.expect_lparen()?; // enum value
555                let name = self.parse_ident()?;
556                let val = if self.is_rparen() {
557                    // has implicit enum value
558                    if has_explicit_value {
559                        return Err(self.error(
560                            pos,
561                            format!(
562                                "Spec enum has unexpected implicit value after implicit value."
563                            ),
564                        ));
565                    }
566                    implicit_idx = Some(if let Some(idx) = implicit_idx {
567                        idx + 1
568                    } else {
569                        0
570                    });
571                    SpecExpr::ConstInt {
572                        val: implicit_idx.unwrap(),
573                        pos,
574                    }
575                } else {
576                    if implicit_idx.is_some() {
577                        return Err(self.error(
578                            pos,
579                            format!(
580                                "Spec enum has unexpected explicit value after implicit value."
581                            ),
582                        ));
583                    }
584                    has_explicit_value = true;
585                    self.parse_spec_expr()?
586                };
587                self.expect_rparen()?;
588                variants.push((name, val));
589            }
590            ModelValue::EnumValues(variants)
591        } else {
592            return Err(self.error(pos, "Model must be a type or enum".to_string()));
593        };
594
595        self.expect_rparen()?; // end body
596        Ok(Model { name, val })
597    }
598
599    fn parse_model_type(&mut self) -> Result<ModelType> {
600        let pos = self.pos();
601        if self.eat_sym_str("Bool")? {
602            Ok(ModelType::Bool)
603        } else if self.eat_sym_str("Int")? {
604            Ok(ModelType::Int)
605        } else if self.eat_sym_str("Unit")? {
606            Ok(ModelType::Unit)
607        } else if self.is_lparen() {
608            self.expect_lparen()?;
609            let width = if self.eat_sym_str("bv")? {
610                if self.is_rparen() {
611                    None
612                } else if self.is_int() {
613                    Some(usize::try_from(self.expect_int()?).map_err(|err| {
614                        self.error(pos, format!("Invalid BitVector width: {err}"))
615                    })?)
616                } else {
617                    return Err(self.error(pos, "Badly formed BitVector (bv ...)".to_string()));
618                }
619            } else {
620                return Err(self.error(pos, "Badly formed BitVector (bv ...)".to_string()));
621            };
622            self.expect_rparen()?;
623            Ok(ModelType::BitVec(width))
624        } else {
625            Err(self.error(
626                pos,
627                "Model type be a Bool, Int, or BitVector (bv ...)".to_string(),
628            ))
629        }
630    }
631
632    fn parse_form(&mut self) -> Result<Form> {
633        let pos = self.pos();
634        let name = self.parse_ident()?;
635        let signatures = self.parse_signatures()?;
636        Ok(Form {
637            name,
638            signatures,
639            pos,
640        })
641    }
642
643    fn parse_signatures(&mut self) -> Result<Vec<Signature>> {
644        let mut signatures = vec![];
645        while !self.is_rparen() {
646            signatures.push(self.parse_signature()?);
647        }
648        Ok(signatures)
649    }
650
651    fn parse_signature(&mut self) -> Result<Signature> {
652        self.expect_lparen()?;
653        let pos = self.pos();
654        let args = self.parse_tagged_types("args")?;
655        let ret = self.parse_tagged_type("ret")?;
656        let canonical = self.parse_tagged_type("canon")?;
657        self.expect_rparen()?;
658        Ok(Signature {
659            args,
660            ret,
661            canonical,
662            pos,
663        })
664    }
665
666    fn parse_tagged_types(&mut self, tag: &str) -> Result<Vec<ModelType>> {
667        self.expect_lparen()?;
668        let pos = self.pos();
669        if !self.eat_sym_str(tag)? {
670            return Err(self.error(pos, format!("Invalid {tag}: expected ({tag} <arg> ...)")));
671        };
672        let mut params = vec![];
673        while !self.is_rparen() {
674            params.push(self.parse_model_type()?);
675        }
676        self.expect_rparen()?;
677        Ok(params)
678    }
679
680    fn parse_tagged_type(&mut self, tag: &str) -> Result<ModelType> {
681        self.expect_lparen()?;
682        let pos = self.pos();
683        if !self.eat_sym_str(tag)? {
684            return Err(self.error(pos, format!("Invalid {tag}: expected ({tag} <arg>)")));
685        };
686        let ty = self.parse_model_type()?;
687        self.expect_rparen()?;
688        Ok(ty)
689    }
690
691    fn parse_instantiation(&mut self) -> Result<Instantiation> {
692        let pos = self.pos();
693        let term = self.parse_ident()?;
694        // Instantiation either has an explicit signatures list, which would
695        // open with a left paren. Or it has an identifier referencing a
696        // predefined set of signatures.
697        if self.is_lparen() {
698            let signatures = self.parse_signatures()?;
699            Ok(Instantiation {
700                term,
701                form: None,
702                signatures,
703                pos,
704            })
705        } else {
706            let form = self.parse_ident()?;
707            Ok(Instantiation {
708                term,
709                form: Some(form),
710                signatures: vec![],
711                pos,
712            })
713        }
714    }
715
716    fn parse_extern(&mut self) -> Result<Extern> {
717        let pos = self.pos();
718        if self.eat_sym_str("constructor")? {
719            let term = self.parse_ident()?;
720            let func = self.parse_ident()?;
721            Ok(Extern::Constructor { term, func, pos })
722        } else if self.eat_sym_str("extractor")? {
723            let infallible = self.eat_sym_str("infallible")?;
724
725            let term = self.parse_ident()?;
726            let func = self.parse_ident()?;
727
728            Ok(Extern::Extractor {
729                term,
730                func,
731                pos,
732                infallible,
733            })
734        } else if self.eat_sym_str("const")? {
735            let pos = self.pos();
736            let name = self.parse_const()?;
737            let ty = self.parse_ident()?;
738            Ok(Extern::Const { name, ty, pos })
739        } else {
740            Err(self.error(
741                pos,
742                "Invalid extern: must be (extern constructor ...), (extern extractor ...) or (extern const ...)"
743                    .to_string(),
744            ))
745        }
746    }
747
748    fn parse_etor(&mut self) -> Result<Extractor> {
749        let pos = self.pos();
750        self.expect_lparen()?;
751        let term = self.parse_ident()?;
752        let mut args = vec![];
753        while !self.is_rparen() {
754            args.push(self.parse_ident()?);
755        }
756        self.expect_rparen()?;
757        let template = self.parse_pattern()?;
758        Ok(Extractor {
759            term,
760            args,
761            template,
762            pos,
763        })
764    }
765
766    fn parse_rule(&mut self) -> Result<Rule> {
767        let pos = self.pos();
768        let name = if self.is_sym() {
769            Some(
770                self.parse_ident()
771                    .map_err(|err| self.error(pos, format!("Invalid rule name: {err:?}")))?,
772            )
773        } else {
774            None
775        };
776        let prio = if self.is_int() {
777            Some(
778                i64::try_from(self.expect_int()?)
779                    .map_err(|err| self.error(pos, format!("Invalid rule priority: {err}")))?,
780            )
781        } else {
782            None
783        };
784        let pattern = self.parse_pattern()?;
785        let mut iflets = vec![];
786        loop {
787            match self.parse_iflet_or_expr()? {
788                IfLetOrExpr::IfLet(iflet) => {
789                    iflets.push(iflet);
790                }
791                IfLetOrExpr::Expr(expr) => {
792                    return Ok(Rule {
793                        pattern,
794                        iflets,
795                        expr,
796                        pos,
797                        prio,
798                        name,
799                    });
800                }
801            }
802        }
803    }
804
805    fn parse_pattern(&mut self) -> Result<Pattern> {
806        let pos = self.pos();
807        if self.is_int() {
808            Ok(Pattern::ConstInt {
809                val: self.expect_int()?,
810                pos,
811            })
812        } else if self.is_const() {
813            let val = self.parse_const()?;
814            Ok(Pattern::ConstPrim { val, pos })
815        } else if self.eat_sym_str("_")? {
816            Ok(Pattern::Wildcard { pos })
817        } else if self.eat_sym_str("true")? {
818            Ok(Pattern::ConstBool { val: true, pos })
819        } else if self.eat_sym_str("false")? {
820            Ok(Pattern::ConstBool { val: false, pos })
821        } else if self.is_sym() {
822            let var = self.parse_ident()?;
823            if self.is_at() {
824                self.expect_at()?;
825                let subpat = Box::new(self.parse_pattern()?);
826                Ok(Pattern::BindPattern { var, subpat, pos })
827            } else {
828                Ok(Pattern::Var { var, pos })
829            }
830        } else if self.is_lparen() {
831            self.expect_lparen()?;
832            if self.eat_sym_str("and")? {
833                let mut subpats = vec![];
834                while !self.is_rparen() {
835                    subpats.push(self.parse_pattern()?);
836                }
837                self.expect_rparen()?;
838                Ok(Pattern::And { subpats, pos })
839            } else {
840                let sym = self.parse_ident()?;
841                let mut args = vec![];
842                while !self.is_rparen() {
843                    args.push(self.parse_pattern()?);
844                }
845                self.expect_rparen()?;
846                Ok(Pattern::Term { sym, args, pos })
847            }
848        } else {
849            Err(self.error(pos, "Unexpected pattern".into()))
850        }
851    }
852
853    fn parse_iflet_or_expr(&mut self) -> Result<IfLetOrExpr> {
854        let pos = self.pos();
855        if self.is_lparen() {
856            self.expect_lparen()?;
857            let ret = if self.eat_sym_str("if-let")? {
858                IfLetOrExpr::IfLet(self.parse_iflet()?)
859            } else if self.eat_sym_str("if")? {
860                // Shorthand form: `(if (x))` desugars to `(if-let _
861                // (x))`.
862                IfLetOrExpr::IfLet(self.parse_iflet_if()?)
863            } else {
864                IfLetOrExpr::Expr(self.parse_expr_inner_parens(pos)?)
865            };
866            self.expect_rparen()?;
867            Ok(ret)
868        } else {
869            self.parse_expr().map(IfLetOrExpr::Expr)
870        }
871    }
872
873    fn parse_iflet(&mut self) -> Result<IfLet> {
874        let pos = self.pos();
875        let pattern = self.parse_pattern()?;
876        let expr = self.parse_expr()?;
877        Ok(IfLet { pattern, expr, pos })
878    }
879
880    fn parse_iflet_if(&mut self) -> Result<IfLet> {
881        let pos = self.pos();
882        let expr = self.parse_expr()?;
883        Ok(IfLet {
884            pattern: Pattern::Wildcard { pos },
885            expr,
886            pos,
887        })
888    }
889
890    fn parse_expr(&mut self) -> Result<Expr> {
891        let pos = self.pos();
892        if self.is_lparen() {
893            self.expect_lparen()?;
894            let ret = self.parse_expr_inner_parens(pos)?;
895            self.expect_rparen()?;
896            Ok(ret)
897        } else if self.is_const() {
898            let val = self.parse_const()?;
899            Ok(Expr::ConstPrim { val, pos })
900        } else if self.eat_sym_str("true")? {
901            Ok(Expr::ConstBool { val: true, pos })
902        } else if self.eat_sym_str("false")? {
903            Ok(Expr::ConstBool { val: false, pos })
904        } else if self.is_sym() {
905            let name = self.parse_ident()?;
906            Ok(Expr::Var { name, pos })
907        } else if self.is_int() {
908            let val = self.expect_int()?;
909            Ok(Expr::ConstInt { val, pos })
910        } else {
911            Err(self.error(pos, "Invalid expression".into()))
912        }
913    }
914
915    fn parse_expr_inner_parens(&mut self, pos: Pos) -> Result<Expr> {
916        if self.eat_sym_str("let")? {
917            self.expect_lparen()?;
918            let mut defs = vec![];
919            while !self.is_rparen() {
920                let def = self.parse_letdef()?;
921                defs.push(def);
922            }
923            self.expect_rparen()?;
924            let body = Box::new(self.parse_expr()?);
925            Ok(Expr::Let { defs, body, pos })
926        } else {
927            let sym = self.parse_ident()?;
928            let mut args = vec![];
929            while !self.is_rparen() {
930                args.push(self.parse_expr()?);
931            }
932            Ok(Expr::Term { sym, args, pos })
933        }
934    }
935
936    fn parse_letdef(&mut self) -> Result<LetDef> {
937        let pos = self.pos();
938        self.expect_lparen()?;
939        let var = self.parse_ident()?;
940        let ty = self.parse_ident()?;
941        let val = Box::new(self.parse_expr()?);
942        self.expect_rparen()?;
943        Ok(LetDef { var, ty, val, pos })
944    }
945
946    fn parse_converter(&mut self) -> Result<Converter> {
947        let pos = self.pos();
948        let inner_ty = self.parse_ident()?;
949        let outer_ty = self.parse_ident()?;
950        let term = self.parse_ident()?;
951        Ok(Converter {
952            term,
953            inner_ty,
954            outer_ty,
955            pos,
956        })
957    }
958}
cranelift_isle/parser.rs

cranelift_isle/
parser.rs
