quil_rs/program/
defgate_sequence_expansion.rs

1/// This module implements the expansion of sequence gate definitions in a Quil program,
2/// as well as the associated source map that tracks how the original
3/// instructions map to the expanded instructions.
4use std::{collections::HashMap, ops::Range, vec};
5
6use indexmap::{IndexMap, IndexSet};
7
8use crate::{
9    expression::Expression,
10    instruction::{
11        DefGateSequenceExpansionError, GateDefinition, GateSignature, GateSpecification,
12        Instruction,
13    },
14    program::{InstructionIndex, SourceMap, SourceMapEntry},
15};
16
17use super::source_map::{ExpansionResult, SourceMapIndexable};
18
19/// Details about the expansion of a sequence gate definition
20#[derive(Clone, Debug, PartialEq)]
21pub struct DefGateSequenceExpansion<'a> {
22    /// The signature of the sequence gate definition that was
23    /// used to expand the instruction.
24    ///
25    /// Note, technically, the gate name itself is sufficient to identify
26    /// the sequence gate definition, since gate names are unique within
27    /// a program. Nevertheless, we include the full signature here
28    /// for later reference within error messages.
29    source_signature: crate::instruction::GateSignature<'a>,
30
31    /// The target instruction indices produced by the expansion
32    range: Range<InstructionIndex>,
33
34    /// Sequence gate definitions may refer to other sequence gate definitions
35    /// per the Quil specification. As such, we need to track how the first-level
36    /// sequence instructions map to nested sequence gate definition expansion.
37    nested_expansions: SourceMap<InstructionIndex, ExpansionResult<DefGateSequenceExpansion<'a>>>,
38}
39
40#[cfg(feature = "python")]
41impl<'a> DefGateSequenceExpansion<'a> {
42    /// Borrow the source gate signature of the sequence gate definition
43    pub(crate) fn source_signature(&self) -> &GateSignature<'a> {
44        &self.source_signature
45    }
46}
47
48impl<'a> DefGateSequenceExpansion<'a> {
49    /// Returns the range of target instruction indices produced by the expansion
50    pub fn range(&self) -> &Range<InstructionIndex> {
51        &self.range
52    }
53
54    /// Returns the nested expansions of this sequence gate definition
55    pub fn nested_expansions(
56        &self,
57    ) -> &SourceMap<InstructionIndex, ExpansionResult<DefGateSequenceExpansion<'a>>> {
58        &self.nested_expansions
59    }
60}
61
62impl SourceMapIndexable<InstructionIndex> for DefGateSequenceExpansion<'_> {
63    fn contains(&self, other: &InstructionIndex) -> bool {
64        self.range.contains(other)
65    }
66}
67
68impl<'a> SourceMapIndexable<GateSignature<'a>> for DefGateSequenceExpansion<'a> {
69    fn contains(&self, other: &GateSignature) -> bool {
70        &self.source_signature == other
71    }
72}
73
74type SequenceGateDefinitionSourceMap<'a> =
75    SourceMap<InstructionIndex, ExpansionResult<DefGateSequenceExpansion<'a>>>;
76
77/// A utility to expand sequence gate definitions in a Quil program.
78#[derive(Clone, Debug, PartialEq)]
79pub(crate) struct ProgramDefGateSequenceExpander<'a, F> {
80    gate_definitions: &'a IndexMap<String, GateDefinition>,
81    filter: F,
82}
83
84#[derive(Clone, Debug, PartialEq)]
85pub(crate) struct ExpandedInstructionsWithSourceMap<'a> {
86    pub(crate) instructions: Vec<Instruction>,
87    pub(crate) source_map: SequenceGateDefinitionSourceMap<'a>,
88}
89
90struct ExpansionStack(IndexSet<String>);
91
92impl ExpansionStack {
93    fn new() -> Self {
94        Self(IndexSet::new())
95    }
96
97    /// Check if the name is in the stack and, if so, return an error.
98    fn check(&self, name: impl AsRef<str>) -> Result<(), DefGateSequenceExpansionError> {
99        if self.0.contains(name.as_ref()) {
100            let cycle = self.0.iter().cloned().collect();
101            Err(DefGateSequenceExpansionError::CyclicSequenceGateDefinition(
102                cycle,
103            ))
104        } else {
105            Ok(())
106        }
107    }
108
109    /// Execute a closure with an gate added to the stack.
110    fn with_gate_sequence<F, R>(&mut self, name: String, f: F) -> R
111    where
112        F: FnOnce(&mut Self) -> R,
113    {
114        let must_pop = self.0.insert(name);
115        let result = f(self);
116        if must_pop {
117            self.0.pop();
118        }
119        result
120    }
121}
122
123impl<'a, F> ProgramDefGateSequenceExpander<'a, F>
124where
125    F: Fn(&str) -> bool,
126{
127    /// Creates a new `ProgramDefGateSequenceExpander`.
128    ///
129    /// # Arguments
130    ///
131    /// * `gate_definitions` - A reference to the gate definitions of the program.
132    /// * `filter` - A filter to apply to the gate definitions, allowing for selective
133    ///   expansion.
134    pub(crate) fn new(gate_definitions: &'a IndexMap<String, GateDefinition>, filter: F) -> Self {
135        Self {
136            gate_definitions,
137            filter,
138        }
139    }
140
141    /// Expands sequence gate definitions in the provided instructions.
142    pub(crate) fn expand(
143        &self,
144        source_instructions: &[Instruction],
145    ) -> Result<Vec<Instruction>, DefGateSequenceExpansionError> {
146        self.expand_without_source_map_impl(source_instructions, &mut ExpansionStack::new())
147    }
148
149    /// Expands sequence gate definitions in the provided instructions and returns a source map
150    /// detailing the expansion.
151    pub(crate) fn expand_with_source_map(
152        &self,
153        source_instructions: &'a [Instruction],
154    ) -> Result<ExpandedInstructionsWithSourceMap<'a>, DefGateSequenceExpansionError> {
155        let mut source_map = SourceMap::default();
156        self.expand_with_source_map_impl(
157            source_instructions,
158            &mut source_map,
159            &mut ExpansionStack::new(),
160        )
161        .map(|instructions| ExpandedInstructionsWithSourceMap {
162            instructions,
163            source_map,
164        })
165    }
166
167    fn expand_with_source_map_impl(
168        &self,
169        source_instructions: &[Instruction],
170        source_map: &mut SequenceGateDefinitionSourceMap<'a>,
171        stack: &mut ExpansionStack,
172    ) -> Result<Vec<Instruction>, DefGateSequenceExpansionError> {
173        let mut target_instructions = vec![];
174        for (source_instruction_index, source_instruction) in source_instructions.iter().enumerate()
175        {
176            if let Some((target_gate_instructions, gate_sequence_signature)) =
177                self.gate_sequence_from_instruction(source_instruction, stack)?
178            {
179                // If this instruction is a sequence gate definition, we need to expand it. Before
180                // doing so, we add the gate sequence signature to the `gate_expansion_stack`,
181                // so all nested expansions within this sequence have access to the stack of
182                // already expanded gate definitions.
183                let mut nested_expansions = SourceMap::default();
184                let recursive_target_gate_instructions = stack.with_gate_sequence(
185                    gate_sequence_signature.name().to_string(),
186                    |stack| {
187                        self.expand_with_source_map_impl(
188                            &target_gate_instructions,
189                            &mut nested_expansions,
190                            stack,
191                        )
192                    },
193                )?;
194
195                let target_instruction_start_index = InstructionIndex(target_instructions.len());
196                let target_instruction_end_index = InstructionIndex(
197                    target_instruction_start_index.0 + recursive_target_gate_instructions.len(),
198                );
199                source_map.entries.push(SourceMapEntry {
200                    source_location: InstructionIndex(source_instruction_index),
201                    target_location: ExpansionResult::Rewritten(DefGateSequenceExpansion {
202                        source_signature: gate_sequence_signature,
203                        range: target_instruction_start_index..target_instruction_end_index,
204                        nested_expansions,
205                    }),
206                });
207                target_instructions.extend(recursive_target_gate_instructions);
208            } else {
209                target_instructions.push(source_instruction.clone());
210                source_map.entries.push(SourceMapEntry {
211                    source_location: InstructionIndex(source_instruction_index),
212                    target_location: ExpansionResult::Unmodified(InstructionIndex(
213                        target_instructions.len() - 1,
214                    )),
215                });
216            }
217        }
218        Ok(target_instructions)
219    }
220
221    fn expand_without_source_map_impl(
222        &self,
223        source_instructions: &[Instruction],
224        stack: &mut ExpansionStack,
225    ) -> Result<Vec<Instruction>, DefGateSequenceExpansionError> {
226        let mut target_instructions = vec![];
227        for source_instruction in source_instructions {
228            if let Some((target_gate_instructions, source)) =
229                self.gate_sequence_from_instruction(source_instruction, stack)?
230            {
231                // If this instruction is a sequence gate definition, we need to expand it. Before
232                // doing so, we add the gate sequence signature to the the `gate_expansion_stack`,
233                // so all nested expansions within this sequence have access to the stack of
234                // already expanded gate definitions.
235                let recursive_target_gate_instructions = stack
236                    .with_gate_sequence(source.name().to_string(), |stack| {
237                        self.expand_without_source_map_impl(&target_gate_instructions, stack)
238                    })?;
239                target_instructions.extend(recursive_target_gate_instructions);
240            } else {
241                target_instructions.push(source_instruction.clone());
242            }
243        }
244        Ok(target_instructions)
245    }
246
247    /// Given an instruction, this function checks if it is a gate instruction that
248    /// matches a sequence gate definition. If it does and the gate name is included
249    /// by the [`ProgramDefGateSequenceExpander::filter`], it expands the gate
250    /// definition into a sequence of instructions and returns them along with the
251    /// signature of the gate definition.
252    ///
253    /// This also checks the `gate_expansion_stack` set to prevent cyclic expansions.
254    fn gate_sequence_from_instruction(
255        &self,
256        instruction: &Instruction,
257        stack: &ExpansionStack,
258    ) -> Result<Option<(Vec<Instruction>, GateSignature<'a>)>, DefGateSequenceExpansionError> {
259        if let Instruction::Gate(gate) = instruction {
260            if let Some(gate_definition) = self.gate_definitions.get(&gate.name) {
261                if let GateSpecification::Sequence(gate_sequence) = &gate_definition.specification {
262                    if (self.filter)(&gate.name) {
263                        if gate_definition.parameters.len() != gate.parameters.len() {
264                            return Err(DefGateSequenceExpansionError::ParameterCount {
265                                expected: gate_definition.parameters.len(),
266                                found: gate.parameters.len(),
267                            });
268                        }
269                        let gate_parameter_arguments = gate_definition
270                            .parameters
271                            .iter()
272                            .cloned()
273                            .zip(gate.parameters.iter().cloned())
274                            .collect::<HashMap<String, Expression>>();
275
276                        if !gate.modifiers.is_empty() {
277                            return Err(DefGateSequenceExpansionError::GateModifiersUnsupported(
278                                gate.modifiers.clone(),
279                            ));
280                        }
281                        let source = gate_definition.signature();
282                        stack.check(source.name())?;
283
284                        let target_gate_instructions = gate_sequence
285                            .expand(gate_parameter_arguments, gate.qubits.clone())?
286                            .into_iter()
287                            .map(Instruction::Gate)
288                            .collect::<Vec<_>>();
289
290                        return Ok(Some((target_gate_instructions, source)));
291                    }
292                }
293            }
294        }
295        Ok(None)
296    }
297}
298
299#[cfg(test)]
300mod tests {
301    use std::str::FromStr;
302
303    use crate::{instruction::GateSignature, Program};
304
305    use super::*;
306    use rstest::*;
307
308    /// A test case for the [`ProgramDefGateSequenceExpander`] functionality.
309    struct DefGateSequenceExpansionTestCase {
310        program: &'static str,
311        filter: Box<dyn Fn(&str) -> bool>,
312        expected: Result<&'static str, DefGateSequenceExpansionError>,
313        source_map_entry_builders:
314            Vec<SourceMapEntry<InstructionIndex, ExpansionResult<DefGateSequenceExpansionBuilder>>>,
315    }
316
317    /// Below we define a set of test cases for the `DefGateSequenceExpansion` functionality. We
318    /// cover valid and invalid expansions.
319    ///
320    /// Note, the error coverage is comprehensive with the exception of
321    /// [`DefGateSequenceExpansionError::UndefinedGateSequenceElementQubit`] and
322    /// [`DefGateSequenceExpansionError::InvalidGateSequenceElementQubit`], which
323    /// cover Quil errors that are impossible to parse or construct.
324    impl DefGateSequenceExpansionTestCase {
325        fn to_source_map(
326            &self,
327        ) -> SourceMap<InstructionIndex, ExpansionResult<DefGateSequenceExpansion<'_>>> {
328            SourceMap {
329                entries: self
330                    .source_map_entry_builders
331                    .iter()
332                    .map(|builder| SourceMapEntry {
333                        source_location: builder.source_location,
334                        target_location: match &builder.target_location {
335                            ExpansionResult::Rewritten(expansion) => expansion.build(),
336                            ExpansionResult::Unmodified(index) => {
337                                ExpansionResult::Unmodified(*index)
338                            }
339                        },
340                    })
341                    .collect(),
342            }
343        }
344
345        fn simple_1q_expansions() -> Self {
346            const QUIL: &str = r"
347DEFGATE seq2(%param1, %param2) a b AS SEQUENCE:
348    seq1(%param1) a
349    seq1(%param2) b
350
351DEFGATE seq1(%param1) a AS SEQUENCE:
352    RZ(%param1) a
353    RX(pi/2) a
354    RZ(%param1) a
355
356seq2(pi, pi/2) 0 1
357";
358            const EXPECTED_QUIL: &str = r"
359RZ(pi) 0
360RX(pi/2) 0
361RZ(pi) 0
362RZ(pi/2) 1
363RX(pi/2) 1
364RZ(pi/2) 1
365";
366            let source_map_entry_builders = vec![build_source_map_entry(
367                0,
368                DefGateSequenceExpansionBuilder::new(
369                    "seq2",
370                    &["param1", "param2"],
371                    &["a", "b"],
372                    0..6,
373                    vec![
374                        build_source_map_entry(
375                            0,
376                            DefGateSequenceExpansionBuilder::new(
377                                "seq1",
378                                &["param1"],
379                                &["a"],
380                                0..3,
381                                vec![
382                                    build_source_map_entry_copy(0, 0),
383                                    build_source_map_entry_copy(1, 1),
384                                    build_source_map_entry_copy(2, 2),
385                                ],
386                            ),
387                        ),
388                        build_source_map_entry(
389                            1,
390                            DefGateSequenceExpansionBuilder::new(
391                                "seq1",
392                                &["param1"],
393                                &["a"],
394                                3..6,
395                                vec![
396                                    build_source_map_entry_copy(0, 0),
397                                    build_source_map_entry_copy(1, 1),
398                                    build_source_map_entry_copy(2, 2),
399                                ],
400                            ),
401                        ),
402                    ],
403                ),
404            )];
405            Self {
406                program: QUIL,
407                filter: Box::new(|_| true),
408                expected: Ok(EXPECTED_QUIL),
409                source_map_entry_builders,
410            }
411        }
412
413        #[expect(clippy::too_many_lines)]
414        fn triple_recursize() -> Self {
415            const QUIL: &str = r"
416DEFGATE some_u2_cycle(%param1, %param2, %param3, %param4, %param5, %param6) a b AS SEQUENCE:
417    pmw3(%param1, %param2, %param3) a
418    pmw3(%param4, %param5, %param6) b
419
420DEFGATE pmw3(%param1, %param2, %param3) a AS SEQUENCE:
421    pmw(%param1) a
422    pmw(%param2) a
423    pmw(%param3) a
424
425DEFGATE pmw(%param1) a AS SEQUENCE:
426    RZ(%param1) a
427    RX(pi/2) a
428    RZ(-%param1) a
429
430some_u2_cycle(-pi, -pi/2, -pi/4, pi/4, pi/2, pi) 0 1
431";
432            const EXPECTED_QUIL: &str = r"
433RZ(-pi) 0
434RX(pi/2) 0
435RZ(-(-pi)) 0
436RZ(-pi/2) 0
437RX(pi/2) 0
438RZ(-(-pi/2)) 0
439RZ(-pi/4) 0
440RX(pi/2) 0
441RZ(-(-pi/4)) 0
442
443RZ(pi/4) 1
444RX(pi/2) 1
445RZ(-(pi/4)) 1
446RZ(pi/2) 1
447RX(pi/2) 1
448RZ(-(pi/2)) 1
449RZ(pi) 1
450RX(pi/2) 1
451RZ(-(pi)) 1
452";
453            let source_map_entry_builders = vec![build_source_map_entry(
454                0,
455                DefGateSequenceExpansionBuilder::new(
456                    "some_u2_cycle",
457                    &["param1", "param2", "param3", "param4", "param5", "param6"],
458                    &["a", "b"],
459                    0..18,
460                    vec![
461                        build_source_map_entry(
462                            0,
463                            DefGateSequenceExpansionBuilder::new(
464                                "pmw3",
465                                &["param1", "param2", "param3"],
466                                &["a"],
467                                0..9,
468                                vec![
469                                    build_source_map_entry(
470                                        0,
471                                        DefGateSequenceExpansionBuilder::new(
472                                            "pmw",
473                                            &["param1"],
474                                            &["a"],
475                                            0..3,
476                                            vec![
477                                                build_source_map_entry_copy(0, 0),
478                                                build_source_map_entry_copy(1, 1),
479                                                build_source_map_entry_copy(2, 2),
480                                            ],
481                                        ),
482                                    ),
483                                    build_source_map_entry(
484                                        1,
485                                        DefGateSequenceExpansionBuilder::new(
486                                            "pmw",
487                                            &["param1"],
488                                            &["a"],
489                                            3..6,
490                                            vec![
491                                                build_source_map_entry_copy(0, 0),
492                                                build_source_map_entry_copy(1, 1),
493                                                build_source_map_entry_copy(2, 2),
494                                            ],
495                                        ),
496                                    ),
497                                    build_source_map_entry(
498                                        2,
499                                        DefGateSequenceExpansionBuilder::new(
500                                            "pmw",
501                                            &["param1"],
502                                            &["a"],
503                                            6..9,
504                                            vec![
505                                                build_source_map_entry_copy(0, 0),
506                                                build_source_map_entry_copy(1, 1),
507                                                build_source_map_entry_copy(2, 2),
508                                            ],
509                                        ),
510                                    ),
511                                ],
512                            ),
513                        ),
514                        build_source_map_entry(
515                            1,
516                            DefGateSequenceExpansionBuilder::new(
517                                "pmw3",
518                                &["param1", "param2", "param3"],
519                                &["a"],
520                                9..18,
521                                vec![
522                                    build_source_map_entry(
523                                        0,
524                                        DefGateSequenceExpansionBuilder::new(
525                                            "pmw",
526                                            &["param1"],
527                                            &["a"],
528                                            0..3,
529                                            vec![
530                                                build_source_map_entry_copy(0, 0),
531                                                build_source_map_entry_copy(1, 1),
532                                                build_source_map_entry_copy(2, 2),
533                                            ],
534                                        ),
535                                    ),
536                                    build_source_map_entry(
537                                        1,
538                                        DefGateSequenceExpansionBuilder::new(
539                                            "pmw",
540                                            &["param1"],
541                                            &["a"],
542                                            3..6,
543                                            vec![
544                                                build_source_map_entry_copy(0, 0),
545                                                build_source_map_entry_copy(1, 1),
546                                                build_source_map_entry_copy(2, 2),
547                                            ],
548                                        ),
549                                    ),
550                                    build_source_map_entry(
551                                        2,
552                                        DefGateSequenceExpansionBuilder::new(
553                                            "pmw",
554                                            &["param1"],
555                                            &["a"],
556                                            6..9,
557                                            vec![
558                                                build_source_map_entry_copy(0, 0),
559                                                build_source_map_entry_copy(1, 1),
560                                                build_source_map_entry_copy(2, 2),
561                                            ],
562                                        ),
563                                    ),
564                                ],
565                            ),
566                        ),
567                    ],
568                ),
569            )];
570            Self {
571                program: QUIL,
572                filter: Box::new(|_| true),
573                expected: Ok(EXPECTED_QUIL),
574                source_map_entry_builders,
575            }
576        }
577
578        /// Test a program expansion where some instructions are not expanded
579        fn unexpanded_instructions() -> Self {
580            const QUIL: &str = r"
581DEFGATE seq2(%param1, %param2) a b AS SEQUENCE:
582    X a
583    seq1(%param2) b
584    H b
585    ISWAP a b
586
587DEFGATE seq1(%param1) a AS SEQUENCE:
588    RZ(%param1) a
589    RX(pi/2) a
590    RZ(%param1) a
591
592ISWAP 0 1
593seq2(pi, pi/2) 0 1
594MEASURE 0 ro[0]
595MEASURE 1 ro[1]
596";
597            const EXPECTED_QUIL: &str = r"
598ISWAP 0 1
599X 0
600RZ(pi/2) 1
601RX(pi/2) 1
602RZ(pi/2) 1
603H 1
604ISWAP 0 1
605MEASURE 0 ro[0]
606MEASURE 1 ro[1]
607";
608            let source_map_entry_builders = vec![
609                build_source_map_entry(0, ExpansionResult::Unmodified(InstructionIndex(0))),
610                build_source_map_entry(
611                    1,
612                    DefGateSequenceExpansionBuilder::new(
613                        "seq2",
614                        &["param1", "param2"],
615                        &["a", "b"],
616                        1..7,
617                        vec![
618                            build_source_map_entry_copy(0, 0),
619                            build_source_map_entry(
620                                1,
621                                DefGateSequenceExpansionBuilder::new(
622                                    "seq1",
623                                    &["param1"],
624                                    &["a"],
625                                    1..4,
626                                    vec![
627                                        build_source_map_entry_copy(0, 0),
628                                        build_source_map_entry_copy(1, 1),
629                                        build_source_map_entry_copy(2, 2),
630                                    ],
631                                ),
632                            ),
633                            build_source_map_entry_copy(2, 4),
634                            build_source_map_entry_copy(3, 5),
635                        ],
636                    ),
637                ),
638                build_source_map_entry_copy(2, 7),
639                build_source_map_entry_copy(3, 8),
640            ];
641            Self {
642                program: QUIL,
643                filter: Box::new(|_| true),
644                expected: Ok(EXPECTED_QUIL),
645                source_map_entry_builders,
646            }
647        }
648
649        /// Test that a sequence gate definition works even if one of the qubit parameters
650        /// is not used in the expansion.
651        ///
652        /// This is not expressly forbidden by the Quil specification, so we include
653        /// this test to document the behavior.
654        fn unused_instruction() -> Self {
655            const QUIL: &str = r"
656DEFGATE seq1(%param1) a b AS SEQUENCE:
657    RZ(%param1) a
658    RX(pi/2) a
659    RZ(%param1) a
660
661seq1(pi) 0 1
662";
663            const EXPECTED_QUIL: &str = r"
664RZ(pi) 0
665RX(pi/2) 0
666RZ(pi) 0
667";
668            let source_map_entry_builders = vec![build_source_map_entry(
669                0,
670                DefGateSequenceExpansionBuilder::new(
671                    "seq1",
672                    &["param1"],
673                    &["a", "b"],
674                    0..3,
675                    vec![
676                        build_source_map_entry_copy(0, 0),
677                        build_source_map_entry_copy(1, 1),
678                        build_source_map_entry_copy(2, 2),
679                    ],
680                ),
681            )];
682            Self {
683                program: QUIL,
684                filter: Box::new(|_| true),
685                expected: Ok(EXPECTED_QUIL),
686                source_map_entry_builders,
687            }
688        }
689
690        /// Test sequence gate definition expansion within a program, where one or more
691        /// sequence gate definitions are not included by the filter.
692        fn filtered_sequence() -> Self {
693            const QUIL: &str = r"
694DEFGATE seq1(%param1) a AS SEQUENCE:
695    RZ(%param1) a
696    RX(pi/2) a
697    RZ(%param1) a
698
699DEFGATE seq2(%param1) a AS SEQUENCE:
700    X a
701
702seq1(pi) 0
703seq2(pi/2) 0
704";
705            const EXPECTED_QUIL: &str = r"
706RZ(pi) 0
707RX(pi/2) 0
708RZ(pi) 0
709seq2(pi/2) 0
710";
711            let source_map_entry_builders = vec![
712                build_source_map_entry(
713                    0,
714                    DefGateSequenceExpansionBuilder::new(
715                        "seq1",
716                        &["param1"],
717                        &["a"],
718                        0..3,
719                        vec![
720                            build_source_map_entry_copy(0, 0),
721                            build_source_map_entry_copy(1, 1),
722                            build_source_map_entry_copy(2, 2),
723                        ],
724                    ),
725                ),
726                build_source_map_entry_copy(1, 3),
727            ];
728            Self {
729                program: QUIL,
730                filter: Box::new(|k| k == "seq1"),
731                expected: Ok(EXPECTED_QUIL),
732                source_map_entry_builders,
733            }
734        }
735
736        fn error_parameter_count() -> Self {
737            const QUIL: &str = r"
738DEFGATE seq1(%param1) a AS SEQUENCE:
739    RZ(%param1) a
740seq1() 0
741";
742            let expected = Err(DefGateSequenceExpansionError::ParameterCount {
743                expected: 1,
744                found: 0,
745            });
746            Self {
747                program: QUIL,
748                filter: Box::new(|_| true),
749                expected,
750                source_map_entry_builders: vec![],
751            }
752        }
753
754        fn error_cyclic_sequence_gate_definition() -> Self {
755            const QUIL: &str = r"
756DEFGATE seq1(%param1) a AS SEQUENCE:
757    seq2(%param1) a
758
759DEFGATE seq2(%param1) a AS SEQUENCE:
760    seq3(%param1) a
761
762DEFGATE seq3(%param1) a AS SEQUENCE:
763    seq1(%param1) a
764
765seq1(pi) 0
766";
767            let expected = Err(DefGateSequenceExpansionError::CyclicSequenceGateDefinition(
768                vec!["seq1".to_string(), "seq2".to_string(), "seq3".to_string()],
769            ));
770            Self {
771                program: QUIL,
772                filter: Box::new(|_| true),
773                expected,
774                source_map_entry_builders: vec![],
775            }
776        }
777
778        fn error_qubit_count() -> Self {
779            const QUIL: &str = r"
780DEFGATE seq1(%param1) a AS SEQUENCE:
781    RZ(%param1) a
782
783seq1(pi/2) 0 1
784";
785            let expected = Err(DefGateSequenceExpansionError::QubitCount {
786                expected: 1,
787                found: 2,
788            });
789            Self {
790                program: QUIL,
791                filter: Box::new(|_| true),
792                expected,
793                source_map_entry_builders: vec![],
794            }
795        }
796
797        fn error_gate_qubit_argument() -> Self {
798            const QUIL: &str = r"
799DEFGATE seq1(%param1) a AS SEQUENCE:
800    RZ(%param1) a
801
802seq1(pi/2) %q1
803";
804            let expected = Err(DefGateSequenceExpansionError::NonFixedQubitArgument(
805                crate::instruction::Qubit::Variable("q1".to_string()),
806            ));
807            Self {
808                program: QUIL,
809                filter: Box::new(|_| true),
810                expected,
811                source_map_entry_builders: vec![],
812            }
813        }
814
815        fn error_gate_modifiers_unsupported() -> Self {
816            const QUIL: &str = r"
817DEFGATE seq1(%param1) a AS SEQUENCE:
818    RZ(%param1) a
819
820
821DAGGER seq1(pi/2) 0
822";
823            let expected = Err(DefGateSequenceExpansionError::GateModifiersUnsupported(
824                vec![crate::instruction::GateModifier::Dagger],
825            ));
826            Self {
827                program: QUIL,
828                filter: Box::new(|_| true),
829                expected,
830                source_map_entry_builders: vec![],
831            }
832        }
833    }
834
835    #[rstest]
836    #[case::simple_1q_expansions(DefGateSequenceExpansionTestCase::simple_1q_expansions())]
837    #[case::triple_recursize(DefGateSequenceExpansionTestCase::triple_recursize())]
838    #[case::unexpanded_instructions(DefGateSequenceExpansionTestCase::unexpanded_instructions())]
839    #[case::unused_instruction(DefGateSequenceExpansionTestCase::unused_instruction())]
840    #[case::filtered_sequence(DefGateSequenceExpansionTestCase::filtered_sequence())]
841    #[case::error_qubit_count(DefGateSequenceExpansionTestCase::error_qubit_count())]
842    #[case::error_gate_qubit_argument(DefGateSequenceExpansionTestCase::error_parameter_count())]
843    #[case::error_gate_qubit_argument(DefGateSequenceExpansionTestCase::error_gate_qubit_argument())]
844    #[case::error_gate_modifiers_unsupported(
845        DefGateSequenceExpansionTestCase::error_gate_modifiers_unsupported()
846    )]
847    #[case::error_cyclic_sequence_gate_definition(
848        DefGateSequenceExpansionTestCase::error_cyclic_sequence_gate_definition()
849    )]
850    fn test_defgate_sequence_expansion(#[case] test_case: DefGateSequenceExpansionTestCase) {
851        let program =
852            crate::Program::from_str(test_case.program).expect("must be a valid Quil program");
853        let program_expansion = ProgramDefGateSequenceExpander {
854            gate_definitions: &program.gate_definitions,
855            filter: &test_case.filter,
856        };
857        let result = program_expansion.expand_with_source_map(&program.instructions);
858
859        match (&test_case.expected, result) {
860            (Ok(expected), Ok(result)) => {
861                let expected_program =
862                    Program::from_str(expected).expect("expected program must be valid Quil");
863                let mut actual_program = Program::new();
864                actual_program.add_instructions(result.instructions);
865
866                pretty_assertions::assert_eq!(expected_program, actual_program);
867                pretty_assertions::assert_eq!(test_case.to_source_map(), result.source_map);
868
869                let actual_program_without_source_map = Program::from_instructions(
870                    program_expansion
871                        .expand(&program.instructions)
872                        .expect("expansion without source map should succeed"),
873                );
874                pretty_assertions::assert_eq!(expected_program, actual_program_without_source_map);
875            }
876            (Ok(expected), Err(e)) => {
877                panic!("Expected instructions:\n\n{expected:?}\n\ngot error:\n\n{e:?}");
878            }
879            (Err(expected), Ok(result)) => {
880                panic!(
881                    "Expected error:\n\n{expected:?}\n\ngot:\n\n{:?}",
882                    result.instructions
883                );
884            }
885            (Err(expected), Err(found)) => {
886                pretty_assertions::assert_eq!(*expected, found);
887            }
888        }
889    }
890
891    struct GateSignatureBuilder {
892        gate_name: String,
893        gate_parameters: Vec<String>,
894        gate_qubits: Vec<String>,
895    }
896
897    impl GateSignatureBuilder {
898        fn new(
899            gate_name: &'static str,
900            gate_parameters: &'static [&'static str],
901            gate_qubits: &'static [&'static str],
902        ) -> Self {
903            Self {
904                gate_name: gate_name.to_string(),
905                gate_parameters: gate_parameters.iter().map(|&s| s.to_string()).collect(),
906                gate_qubits: gate_qubits.iter().map(|&s| s.to_string()).collect(),
907            }
908        }
909
910        fn build(&self) -> GateSignature<'_> {
911            GateSignature::try_new(
912                &self.gate_name,
913                &self.gate_parameters,
914                &self.gate_qubits,
915                crate::instruction::GateType::Sequence,
916            )
917            .expect("must be a valid gate signature")
918        }
919    }
920
921    struct DefGateSequenceExpansionBuilder {
922        signature: GateSignatureBuilder,
923        range: Range<usize>,
924        nested_expansions:
925            Vec<SourceMapEntry<InstructionIndex, ExpansionResult<DefGateSequenceExpansionBuilder>>>,
926    }
927
928    impl DefGateSequenceExpansionBuilder {
929        fn new(
930            gate_name: &'static str,
931            gate_parameters: &'static [&'static str],
932            gate_qubits: &'static [&'static str],
933            range: Range<usize>,
934            entries: Vec<
935                SourceMapEntry<InstructionIndex, ExpansionResult<DefGateSequenceExpansionBuilder>>,
936            >,
937        ) -> ExpansionResult<Self> {
938            ExpansionResult::Rewritten(Self {
939                signature: GateSignatureBuilder::new(gate_name, gate_parameters, gate_qubits),
940                range,
941                nested_expansions: entries,
942            })
943        }
944
945        fn build(&self) -> ExpansionResult<DefGateSequenceExpansion<'_>> {
946            let entries: Vec<_> = self
947                .nested_expansions
948                .iter()
949                .map(|entry| SourceMapEntry {
950                    source_location: entry.source_location,
951                    target_location: match entry.target_location() {
952                        ExpansionResult::Rewritten(expansion) => expansion.build(),
953                        ExpansionResult::Unmodified(index) => ExpansionResult::Unmodified(*index),
954                    },
955                })
956                .collect();
957            ExpansionResult::Rewritten(DefGateSequenceExpansion {
958                source_signature: self.signature.build(),
959                range: InstructionIndex(self.range.start)..InstructionIndex(self.range.end),
960                nested_expansions: SourceMap { entries },
961            })
962        }
963    }
964
965    fn build_source_map_entry(
966        source_location: usize,
967        target_location: ExpansionResult<DefGateSequenceExpansionBuilder>,
968    ) -> SourceMapEntry<InstructionIndex, ExpansionResult<DefGateSequenceExpansionBuilder>> {
969        SourceMapEntry {
970            source_location: InstructionIndex(source_location),
971            target_location,
972        }
973    }
974
975    fn build_source_map_entry_copy(
976        source_location: usize,
977        target_location: usize,
978    ) -> SourceMapEntry<InstructionIndex, ExpansionResult<DefGateSequenceExpansionBuilder>> {
979        build_source_map_entry(
980            source_location,
981            ExpansionResult::Unmodified(InstructionIndex(target_location)),
982        )
983    }
984}
quil_rs/program/defgate_sequence_expansion.rs

quil_rs/program/
defgate_sequence_expansion.rs
