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

cranelift_isle/
parser.rs
