cqlib_core/compile/knowledge/rule_dsl/
parser.rs

1// This code is part of Cqlib.
2//
3// (C) Copyright China Telecom Quantum Group 2025-2026
4//
5// This code is licensed under the Apache License, Version 2.0. You may
6// obtain a copy of this license in the LICENSE.txt file in the root directory
7// of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
8//
9// Any modifications or derivative works of this code must retain this
10// copyright notice, and modified files need to carry a notice indicating
11// that they have been altered from the originals.
12
13//! Recursive-descent parser for the rule DSL.
14//!
15//! Expression parsing is delegated to [`Parameter::try_from`] by extracting
16//! the raw text span from the input string. This avoids building a custom
17//! expression AST and reuses the full symbolic math support in
18//! [`Parameter`].
19
20use crate::circuit::Parameter;
21use crate::compile::knowledge::rule::Condition;
22use crate::compile::knowledge::rule_dsl::ast::{GatePattern, GateSpec, RuleDef};
23use crate::compile::knowledge::rule_dsl::lexer::{Lexer, Token, TokenKind};
24
25/// Errors that can occur while parsing a rule DSL source.
26#[derive(Debug, Clone, PartialEq, thiserror::Error)]
27pub enum ParseError {
28    /// An error originating from the lexer.
29    #[error("lexer error at byte {pos}: {msg}")]
30    Lexer {
31        /// Error message from the lexer.
32        msg: String,
33        /// Byte offset where the error occurred.
34        pos: usize,
35    },
36    /// The parser encountered a token other than the one it expected.
37    #[error("unexpected token at byte {pos}: expected {expected}, found {found}")]
38    UnexpectedToken {
39        /// Human-readable description of the expected token kind.
40        expected: String,
41        /// Description of the token that was actually found.
42        found: String,
43        /// Byte offset of the unexpected token.
44        pos: usize,
45    },
46    /// An expression span was empty (e.g. two commas with nothing between them).
47    #[error("empty expression at byte {pos}")]
48    EmptyExpr {
49        /// Byte offset where the empty expression started.
50        pos: usize,
51    },
52    /// A captured expression string could not be parsed by `Parameter::try_from`.
53    #[error("invalid expression {expr:?}: {reason}")]
54    InvalidExpr {
55        /// The raw expression text that failed to parse.
56        expr: String,
57        /// Underlying error message.
58        reason: String,
59    },
60    /// A bracketed multi-control gate name did not use the `MC<Gate>[n]` form.
61    #[error("invalid multi-controlled gate name at byte {pos}: {gate_name:?}")]
62    InvalidMultiControlledGateName {
63        /// Gate name that appeared before `[n]`.
64        gate_name: String,
65        /// Byte offset where the gate name began.
66        pos: usize,
67    },
68}
69
70/// Recursive-descent parser for the rule DSL.
71pub struct Parser<'a> {
72    /// The full input string; used to extract raw expression spans.
73    input: &'a str,
74    /// The underlying lexer.
75    lexer: Lexer<'a>,
76    /// The current lookahead token.
77    current: Token<'a>,
78}
79
80impl<'a> Parser<'a> {
81    /// Creates a new parser for the given input.
82    ///
83    /// Returns an error if the lexer fails on the very first token.
84    pub fn new(input: &'a str) -> Result<Self, ParseError> {
85        let mut lexer = Lexer::new(input);
86        let current = lexer.next_token().map_err(|e| ParseError::Lexer {
87            msg: e.msg,
88            pos: e.pos,
89        })?;
90        Ok(Self {
91            input,
92            lexer,
93            current,
94        })
95    }
96
97    /// Advances the lexer and stores the next token in `self.current`.
98    fn advance(&mut self) -> Result<(), ParseError> {
99        self.current = self.lexer.next_token().map_err(|e| ParseError::Lexer {
100            msg: e.msg,
101            pos: e.pos,
102        })?;
103        Ok(())
104    }
105
106    /// Consumes the current token if it matches `kind`, otherwise returns an
107    /// [`ParseError::UnexpectedToken`].
108    fn expect(&mut self, kind: TokenKind) -> Result<Token<'a>, ParseError> {
109        if self.current.kind == kind {
110            let token = Token {
111                kind: self.current.kind.clone(),
112                text: self.current.text,
113                pos: self.current.pos,
114            };
115            self.advance()?;
116            Ok(token)
117        } else {
118            Err(ParseError::UnexpectedToken {
119                expected: format!("{:?}", kind),
120                found: format!("{:?}({})", self.current.kind, self.current.text),
121                pos: self.current.pos,
122            })
123        }
124    }
125
126    /// Skips line breaks where the grammar permits layout whitespace.
127    fn skip_newlines(&mut self) -> Result<(), ParseError> {
128        while self.current.kind == TokenKind::Newline {
129            self.advance()?;
130        }
131        Ok(())
132    }
133
134    /// Parses an entire rule file (zero or more rules).
135    pub fn parse_rule_file(&mut self) -> Result<Vec<RuleDef>, ParseError> {
136        let mut rules = Vec::new();
137        self.skip_newlines()?;
138        while self.current.kind != TokenKind::Eof {
139            rules.push(self.parse_rule()?);
140            self.skip_newlines()?;
141        }
142        Ok(rules)
143    }
144
145    /// Parses a single `rule ident { ... }` definition.
146    fn parse_rule(&mut self) -> Result<RuleDef, ParseError> {
147        self.expect(TokenKind::Rule)?;
148        let name = self.expect(TokenKind::Ident)?.text.to_string();
149        self.expect(TokenKind::LBrace)?;
150        self.skip_newlines()?;
151
152        self.expect(TokenKind::Match)?;
153        self.expect(TokenKind::LBrace)?;
154        let match_ops = self.parse_gate_patterns()?;
155        self.expect(TokenKind::RBrace)?;
156        self.skip_newlines()?;
157
158        let mut conditions = Vec::new();
159        if self.current.kind == TokenKind::Require {
160            self.advance()?;
161            self.expect(TokenKind::LBrace)?;
162            conditions = self.parse_conditions()?;
163            self.expect(TokenKind::RBrace)?;
164            self.skip_newlines()?;
165        }
166
167        self.expect(TokenKind::Rewrite)?;
168        self.expect(TokenKind::LBrace)?;
169        let rewrite_ops = self.parse_gate_patterns()?;
170        self.expect(TokenKind::RBrace)?;
171        self.skip_newlines()?;
172
173        self.expect(TokenKind::RBrace)?;
174
175        Ok(RuleDef {
176            name,
177            match_ops,
178            conditions,
179            rewrite_ops,
180        })
181    }
182
183    /// Parses a list of gate patterns separated by optional commas.
184    ///
185    /// Returns an empty vector if the list is immediately closed by `}`.
186    /// Commas are required only when multiple patterns appear on the same line;
187    /// they may be omitted between line breaks.
188    fn parse_gate_patterns(&mut self) -> Result<Vec<GatePattern>, ParseError> {
189        let mut patterns = Vec::new();
190        self.skip_newlines()?;
191        while self.current.kind != TokenKind::RBrace && self.current.kind != TokenKind::Eof {
192            patterns.push(self.parse_gate_pattern()?);
193            match self.current.kind {
194                TokenKind::Comma => {
195                    self.advance()?;
196                    self.skip_newlines()?;
197                }
198                TokenKind::Newline => {
199                    self.skip_newlines()?;
200                }
201                TokenKind::RBrace | TokenKind::Eof => {}
202                _ => {
203                    return Err(ParseError::UnexpectedToken {
204                        expected: "Comma, Newline, or RBrace".to_string(),
205                        found: format!("{:?}({})", self.current.kind, self.current.text),
206                        pos: self.current.pos,
207                    });
208                }
209            }
210        }
211        Ok(patterns)
212    }
213
214    /// Parses a single gate pattern: `gate_spec [ "(" params ")" ] qubits`.
215    fn parse_gate_pattern(&mut self) -> Result<GatePattern, ParseError> {
216        let gate_token = self.expect(TokenKind::Ident)?;
217        let gate_name = gate_token.text.to_string();
218        let gate = if self.current.kind == TokenKind::LBracket {
219            self.advance()?;
220            let control_token = self.expect(TokenKind::Number)?;
221            let added_controls =
222                control_token
223                    .text
224                    .parse::<u8>()
225                    .map_err(|_| ParseError::UnexpectedToken {
226                        expected: "u8 multi-control count".to_string(),
227                        found: control_token.text.to_string(),
228                        pos: control_token.pos,
229                    })?;
230            self.expect(TokenKind::RBracket)?;
231            let base_gate_name = gate_name.strip_prefix("MC").ok_or_else(|| {
232                ParseError::InvalidMultiControlledGateName {
233                    gate_name: gate_name.clone(),
234                    pos: gate_token.pos,
235                }
236            })?;
237            if base_gate_name.is_empty() {
238                return Err(ParseError::InvalidMultiControlledGateName {
239                    gate_name,
240                    pos: gate_token.pos,
241                });
242            }
243            GateSpec::MultiControlled {
244                base_gate_name: base_gate_name.to_string(),
245                added_controls,
246            }
247        } else {
248            GateSpec::Standard { gate_name }
249        };
250
251        let mut params = Vec::new();
252        if self.current.kind == TokenKind::LParen {
253            self.advance()?;
254            if self.current.kind != TokenKind::RParen {
255                params.push(self.parse_param()?);
256                while self.current.kind == TokenKind::Comma {
257                    self.advance()?;
258                    params.push(self.parse_param()?);
259                }
260            }
261            self.expect(TokenKind::RParen)?;
262        }
263
264        let mut qubits = Vec::new();
265        while self.current.kind == TokenKind::Number {
266            let text = self.current.text;
267            let q = text
268                .parse::<u32>()
269                .map_err(|_| ParseError::UnexpectedToken {
270                    expected: "qubit index".to_string(),
271                    found: text.to_string(),
272                    pos: self.current.pos,
273                })?;
274            qubits.push(q);
275            self.advance()?;
276        }
277
278        Ok(GatePattern {
279            gate,
280            params,
281            qubits,
282        })
283    }
284
285    /// Parses a single parameter expression up to `,` or `)`.
286    fn parse_param(&mut self) -> Result<Parameter, ParseError> {
287        self.parse_expr(|kind| *kind == TokenKind::Comma || *kind == TokenKind::RParen)
288    }
289
290    /// Parses a list of conditions separated by optional commas.
291    ///
292    /// Returns an empty vector if the list is immediately closed by `}`.
293    /// Commas are required only when multiple conditions appear on the same line;
294    /// they may be omitted between line breaks.
295    fn parse_conditions(&mut self) -> Result<Vec<Condition>, ParseError> {
296        let mut conditions = Vec::new();
297        self.skip_newlines()?;
298        while self.current.kind != TokenKind::RBrace && self.current.kind != TokenKind::Eof {
299            conditions.push(self.parse_condition()?);
300            match self.current.kind {
301                TokenKind::Comma => {
302                    self.advance()?;
303                    self.skip_newlines()?;
304                }
305                TokenKind::Newline => {
306                    self.skip_newlines()?;
307                }
308                TokenKind::RBrace | TokenKind::Eof => {}
309                _ => {
310                    return Err(ParseError::UnexpectedToken {
311                        expected: "Comma, Newline, or RBrace".to_string(),
312                        found: format!("{:?}({})", self.current.kind, self.current.text),
313                        pos: self.current.pos,
314                    });
315                }
316            }
317        }
318        Ok(conditions)
319    }
320
321    /// Parses a single condition: `expr == expr [mod expr]`.
322    fn parse_condition(&mut self) -> Result<Condition, ParseError> {
323        let lhs = self.parse_expr(|kind| *kind == TokenKind::EqEq)?;
324        self.expect(TokenKind::EqEq)?;
325        let rhs = self.parse_expr(|kind| {
326            *kind == TokenKind::Mod
327                || *kind == TokenKind::Comma
328                || *kind == TokenKind::Newline
329                || *kind == TokenKind::RBrace
330        })?;
331
332        if self.current.kind == TokenKind::Mod {
333            self.advance()?;
334            let modulus = self.parse_expr(|kind| {
335                *kind == TokenKind::Comma
336                    || *kind == TokenKind::Newline
337                    || *kind == TokenKind::RBrace
338            })?;
339            Ok(Condition::EqMod(lhs, rhs, modulus))
340        } else {
341            Ok(Condition::Eq(lhs, rhs))
342        }
343    }
344
345    /// Parses an expression by consuming tokens until `stop` returns true.
346    ///
347    /// The raw text spanning from the first token to the boundary token is
348    /// trimmed and passed to [`Parameter::try_from`]. This avoids building a
349    /// custom expression AST and reuses the existing symbolic math parser.
350    fn parse_expr(&mut self, stop: impl Fn(&TokenKind) -> bool) -> Result<Parameter, ParseError> {
351        let start = self.current.pos;
352        let mut paren_depth = 0usize;
353        while self.current.kind != TokenKind::Eof {
354            if paren_depth == 0 && stop(&self.current.kind) {
355                break;
356            }
357            match self.current.kind {
358                TokenKind::LParen => paren_depth += 1,
359                TokenKind::RParen if paren_depth > 0 => paren_depth -= 1,
360                _ => {}
361            }
362            self.advance()?;
363        }
364        let end = self.current.pos;
365        let expr_str = self.input[start..end].trim();
366        if expr_str.is_empty() {
367            return Err(ParseError::EmptyExpr { pos: start });
368        }
369        Parameter::try_from(expr_str).map_err(|e| ParseError::InvalidExpr {
370            expr: expr_str.to_string(),
371            reason: format!("{}", e),
372        })
373    }
374}
375
376#[cfg(test)]
377mod tests {
378    use super::*;
379    use crate::circuit::ParameterValue;
380
381    #[test]
382    fn parse_cancel_rule() {
383        let input = r#"
384            rule cancel_rx_inverse {
385                match {
386                    RX(a) 0
387                    RX(b) 0
388                }
389                require {
390                    a + b == 0 mod 2*π
391                }
392                rewrite {
393                }
394            }
395
396            rule cancel_h {
397                match {
398                    H 0
399                    H 0
400                }
401                rewrite {
402                }
403            }
404        "#;
405        let mut parser = Parser::new(input).unwrap();
406        let rules = parser.parse_rule_file().unwrap();
407        assert_eq!(rules.len(), 2);
408
409        // cancel_rx_inverse
410        let r0 = rules[0].clone().into_rule().unwrap();
411        assert_eq!(r0.name, "cancel_rx_inverse");
412        assert_eq!(r0.operations.len(), 2);
413        assert_eq!(r0.conditions.as_ref().unwrap().len(), 1);
414        assert!(r0.target.is_empty());
415
416        // cancel_h
417        let r1 = rules[1].clone().into_rule().unwrap();
418        assert_eq!(r1.name, "cancel_h");
419        assert_eq!(r1.operations.len(), 2);
420        assert!(r1.conditions.is_none());
421        assert!(r1.target.is_empty());
422    }
423
424    #[test]
425    fn parse_merge_rule() {
426        let input = r#"
427            rule merge_rz {
428                match {
429                    RZ(a) 0
430                    RZ(b) 0
431                }
432                rewrite {
433                    RZ(a + b) 0
434                }
435            }
436        "#;
437        let mut parser = Parser::new(input).unwrap();
438        let rules = parser.parse_rule_file().unwrap();
439        assert_eq!(rules.len(), 1);
440
441        let r = rules[0].clone().into_rule().unwrap();
442        assert_eq!(r.name, "merge_rz");
443        assert_eq!(r.operations.len(), 2);
444        assert_eq!(r.target.len(), 1);
445
446        let target = &r.target[0];
447        assert_eq!(target.qubits.as_slice(), &[0]);
448        let params = target.params.as_ref().unwrap();
449        assert_eq!(params.len(), 1);
450        match &params[0] {
451            ParameterValue::Param(p) => {
452                assert_eq!(p.to_string(), "a + b");
453            }
454            _ => panic!("expected Expr pattern"),
455        }
456    }
457
458    #[test]
459    fn parse_newline_separated_patterns() {
460        let input = r#"rule test {
461            match { H 0
462            H 0
463            H 0 }
464            rewrite {}
465        }"#;
466        let mut parser = Parser::new(input).unwrap();
467        let rules = parser.parse_rule_file().unwrap();
468        let r = rules[0].clone().into_rule().unwrap();
469        assert_eq!(r.operations.len(), 3);
470    }
471
472    #[test]
473    fn parse_comma_separated_patterns() {
474        let input = r#"rule test {
475            match { H 0, H 0, H 0 }
476            rewrite {}
477        }"#;
478        let mut parser = Parser::new(input).unwrap();
479        let rules = parser.parse_rule_file().unwrap();
480        let r = rules[0].clone().into_rule().unwrap();
481        assert_eq!(r.operations.len(), 3);
482    }
483
484    #[test]
485    fn reject_same_line_patterns_without_comma() {
486        let input = r#"rule test {
487            match { H 0 H 0 }
488            rewrite {}
489        }"#;
490        let mut parser = Parser::new(input).unwrap();
491        assert!(parser.parse_rule_file().is_err());
492    }
493
494    #[test]
495    fn parse_nested_parenthesized_param_expr() {
496        let input = r#"rule test {
497            match { RZ(a) 0 }
498            rewrite { RZ((a + 1)) 0 }
499        }"#;
500        let mut parser = Parser::new(input).unwrap();
501        let rules = parser.parse_rule_file().unwrap();
502        let r = rules[0].clone().into_rule().unwrap();
503        assert_eq!(r.target.len(), 1);
504    }
505
506    #[test]
507    fn parse_gphase_rule() {
508        let input = r#"
509            rule merge_gphase {
510                match { GPhase(a), GPhase(b) }
511                rewrite { GPhase(a + b) }
512            }
513            rule cancel_gphase_inverse {
514                match { GPhase(a), GPhase(b) }
515                require { a + b == 0 mod 2*π }
516                rewrite {}
517            }
518        "#;
519        let mut parser = Parser::new(input).unwrap();
520        let rules = parser.parse_rule_file().unwrap();
521        assert_eq!(rules.len(), 2);
522
523        let r0 = rules[0].clone().into_rule().unwrap();
524        assert_eq!(r0.name, "merge_gphase");
525        assert_eq!(r0.operations.len(), 2);
526        assert!(r0.operations[0].qubits.is_empty());
527        assert_eq!(r0.target.len(), 1);
528        assert!(r0.target[0].qubits.is_empty());
529
530        let r1 = rules[1].clone().into_rule().unwrap();
531        assert_eq!(r1.name, "cancel_gphase_inverse");
532        assert_eq!(r1.operations.len(), 2);
533        assert!(r1.operations[0].qubits.is_empty());
534        assert_eq!(r1.conditions.as_ref().unwrap().len(), 1);
535        assert!(r1.target.is_empty());
536    }
537
538    #[test]
539    fn parse_multi_controlled_gate_pattern() {
540        let input = r#"rule decompose_m3cx {
541            match { MCX[3] 0 1 2 3 }
542            rewrite { CCX 0 1 2 }
543        }"#;
544        let mut parser = Parser::new(input).unwrap();
545        let rules = parser.parse_rule_file().unwrap();
546        assert_eq!(rules.len(), 1);
547        let pattern = &rules[0].match_ops[0];
548        assert_eq!(
549            pattern.gate,
550            GateSpec::MultiControlled {
551                base_gate_name: "X".to_string(),
552                added_controls: 3
553            }
554        );
555        assert_eq!(pattern.qubits, vec![0, 1, 2, 3]);
556    }
557
558    #[test]
559    fn parse_parameterized_multi_controlled_gate_pattern() {
560        let input = r#"rule decompose_m2rz {
561            match { MCRZ[2](theta) 0 1 2 }
562            rewrite { CRZ(theta) 1 2 }
563        }"#;
564        let mut parser = Parser::new(input).unwrap();
565        let rules = parser.parse_rule_file().unwrap();
566        assert_eq!(rules[0].match_ops[0].params.len(), 1);
567        assert_eq!(
568            rules[0].match_ops[0].gate,
569            GateSpec::MultiControlled {
570                base_gate_name: "RZ".to_string(),
571                added_controls: 2
572            }
573        );
574    }
575
576    #[test]
577    fn reject_bracketed_non_multi_controlled_gate_name() {
578        let input = r#"rule bad {
579            match { X[3] 0 1 2 3 }
580            rewrite {}
581        }"#;
582        let mut parser = Parser::new(input).unwrap();
583        assert!(matches!(
584            parser.parse_rule_file(),
585            Err(ParseError::InvalidMultiControlledGateName { .. })
586        ));
587    }
588
589    #[test]
590    fn reject_fractional_multi_control_count() {
591        let input = r#"rule bad {
592            match { MCX[1.5] 0 1 }
593            rewrite {}
594        }"#;
595        let mut parser = Parser::new(input).unwrap();
596        assert!(matches!(
597            parser.parse_rule_file(),
598            Err(ParseError::UnexpectedToken { .. })
599        ));
600    }
601}
cqlib_core/compile/knowledge/rule_dsl/parser.rs

cqlib_core/compile/knowledge/rule_dsl/
parser.rs
