GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored from https://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
v1.29.0

Branches

Tags

  • No tags available.
0Branches0Tags
Go to file
Add file
Code

Clone

HTTPS

Download ZIP

qdk/source/compiler/qsc_circuit/src

source/compiler/qsc_circuit/src/builder.rs

2007lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#[cfg(test)]
5pub(crate) mod tests;
6
7use crate::{
8 circuit::{
9 Circuit, ComponentColumn, Ket, Measurement, Metadata, Operation, Qubit, Register,
10 SourceLocation, Unitary, operation_list_to_grid,
11 },
12 operations::QubitParam,
13};
14use qsc_data_structures::{
15 functors::FunctorApp,
16 index_map::IndexMap,
17 line_column::{Encoding, Position},
18};
19use qsc_eval::{
20 backend::Tracer,
21 debug::Frame,
22 val::{self, Value},
23};
24use qsc_fir::fir::{
25 self, ExprId, ExprKind, PackageId, PackageLookup, PackageStoreLookup, StoreItemId,
26};
27use qsc_frontend::compile::{self};
28use qsc_lowerer::map_fir_package_to_hir;
29use rustc_hash::{FxHashMap, FxHashSet};
30#[cfg(test)]
31use std::fmt::Display;
32use std::{
33 fmt::{Debug, Write},
34 hash::Hash,
35 mem::{replace, take},
36 rc::Rc,
37};
38
39/// Circuit builder that implements the `Tracer` trait to build a circuit
40/// while tracing execution.
41pub struct CircuitTracer {
42 config: TracerConfig,
43 wire_map_builder: WireMapBuilder,
44 circuit_builder: OperationListBuilder,
45 next_result_id: usize,
46 user_package_ids: Vec<PackageId>,
47 superposition_qubits: FxHashSet<QubitWire>,
48 classical_one_qubits: FxHashSet<QubitWire>,
49}
50
51impl Tracer for CircuitTracer {
52 fn qubit_allocate(&mut self, stack: &[Frame], q: usize) {
53 let declared_at = self.user_code_call_location(stack);
54 self.wire_map_builder.map_qubit(q, declared_at);
55 }
56
57 fn qubit_release(&mut self, _stack: &[Frame], q: usize) {
58 self.wire_map_builder.unmap_qubit(q);
59 }
60
61 fn qubit_swap_id(&mut self, _stack: &[Frame], q0: usize, q1: usize) {
62 self.wire_map_builder.swap(q0, q1);
63 }
64
65 fn gate(
66 &mut self,
67 stack: &[Frame],
68 name: &str,
69 is_adjoint: bool,
70 targets: &[usize],
71 controls: &[usize],
72 theta: Option<f64>,
73 ) {
74 let called_at = LogicalStack::from_evaluator_trace(stack);
75 let display_args: Vec<String> = theta.map(|p| format!("{p:.4}")).into_iter().collect();
76 let controls = if self.config.prune_classical_qubits {
77 // Any controls that are known to be classically one can be removed, so this
78 // will return the updated controls list.
79 &self.update_qubit_status(name, targets, controls)
80 } else {
81 controls
82 };
83 self.circuit_builder.gate(
84 self.wire_map_builder.current(),
85 name,
86 is_adjoint,
87 &GateInputs { targets, controls },
88 display_args,
89 called_at,
90 );
91 }
92
93 fn measure(&mut self, stack: &[Frame], name: &str, q: usize, val: &val::Result) {
94 let called_at = LogicalStack::from_evaluator_trace(stack);
95 let r = match val {
96 val::Result::Id(id) => *id,
97 val::Result::Loss | val::Result::Val(_) => {
98 let id = self.next_result_id;
99 self.next_result_id += 1;
100 id
101 }
102 };
103 self.wire_map_builder.link_result_to_qubit(q, r);
104 if name == "MResetZ" {
105 self.classical_one_qubits
106 .remove(&self.wire_map_builder.wire_map.qubit_wire(q));
107 self.circuit_builder.measurement(
108 self.wire_map_builder.current(),
109 "MResetZ",
110 q,
111 r,
112 called_at,
113 );
114 } else {
115 self.circuit_builder
116 .measurement(self.wire_map_builder.current(), "M", q, r, called_at);
117 }
118 }
119
120 fn reset(&mut self, stack: &[Frame], q: usize) {
121 let called_at = LogicalStack::from_evaluator_trace(stack);
122 self.classical_one_qubits
123 .remove(&self.wire_map_builder.wire_map.qubit_wire(q));
124 self.circuit_builder
125 .reset(self.wire_map_builder.current(), q, called_at);
126 }
127
128 fn custom_intrinsic(&mut self, stack: &[Frame], name: &str, arg: Value) {
129 // The qubit arguments are treated as the targets for custom gates.
130 // Any remaining arguments will be kept in the display_args field
131 // to be shown as part of the gate label when the circuit is rendered.
132 let (qubit_args, classical_args) = self.split_qubit_args(arg);
133
134 if qubit_args.is_empty() {
135 // don't add a gate with no qubit targets
136 return;
137 }
138
139 self.circuit_builder.gate(
140 self.wire_map_builder.current(),
141 name,
142 false, // is_adjoint
143 &GateInputs {
144 targets: &qubit_args,
145 controls: &[],
146 },
147 if classical_args.is_empty() {
148 vec![]
149 } else {
150 vec![classical_args]
151 },
152 LogicalStack::from_evaluator_trace(stack),
153 );
154 }
155
156 fn is_stack_tracing_enabled(&self) -> bool {
157 self.config.source_locations || self.config.group_by_scope
158 }
159}
160
161impl CircuitTracer {
162 #[must_use]
163 pub fn new(config: TracerConfig, user_package_ids: &[PackageId]) -> Self {
164 CircuitTracer {
165 config,
166 wire_map_builder: WireMapBuilder::new(vec![]),
167 circuit_builder: OperationListBuilder::new(
168 config.max_operations,
169 user_package_ids.to_vec(),
170 config.group_by_scope,
171 config.source_locations,
172 ),
173 next_result_id: 0,
174 user_package_ids: user_package_ids.to_vec(),
175 superposition_qubits: FxHashSet::default(),
176 classical_one_qubits: FxHashSet::default(),
177 }
178 }
179
180 #[must_use]
181 pub fn with_qubit_input_params(
182 config: TracerConfig,
183 user_package_ids: &[PackageId],
184 operation_qubit_params: Option<(PackageId, Vec<QubitParam>)>,
185 ) -> Self {
186 // Pre-initialize the qubit declaration locations for the operation's
187 // input parameters. These will get allocated during execution, but
188 // the declaration locations inferred from the callstacks will be meaningless
189 // since those will be in the generated entry expression.
190 let params = if config.source_locations {
191 operation_qubit_params
192 .map(|(package_id, info)| {
193 let mut decls = vec![];
194 for param in &info {
195 for _ in 0..param.num_qubits() {
196 decls.push(PackageOffset {
197 package_id,
198 offset: param.source_offset,
199 });
200 }
201 }
202 decls
203 })
204 .unwrap_or_default()
205 } else {
206 vec![]
207 };
208
209 CircuitTracer {
210 config,
211 wire_map_builder: WireMapBuilder::new(params),
212 circuit_builder: OperationListBuilder::new(
213 config.max_operations,
214 user_package_ids.to_vec(),
215 config.group_by_scope,
216 config.source_locations,
217 ),
218 next_result_id: 0,
219 user_package_ids: user_package_ids.to_vec(),
220 superposition_qubits: FxHashSet::default(),
221 classical_one_qubits: FxHashSet::default(),
222 }
223 }
224
225 #[must_use]
226 pub fn snapshot(&self, source_lookup: &impl SourceLookup) -> Circuit {
227 self.finish_circuit(self.circuit_builder.operations(), source_lookup)
228 }
229
230 #[must_use]
231 pub fn finish(mut self, source_lookup: &impl SourceLookup) -> Circuit {
232 let ops = replace(
233 &mut self.circuit_builder,
234 OperationListBuilder::new(
235 self.config.max_operations,
236 self.user_package_ids.clone(),
237 self.config.group_by_scope,
238 self.config.source_locations,
239 ),
240 )
241 .into_operations();
242
243 self.finish_circuit(&ops, source_lookup)
244 }
245
246 fn finish_circuit(
247 &self,
248 operations: &[OperationOrGroup],
249 source_lookup: &impl SourceLookup,
250 ) -> Circuit {
251 let mut operations = operations.to_vec();
252 let mut qubits = self.wire_map_builder.wire_map.to_qubits(source_lookup);
253
254 if self.config.prune_classical_qubits {
255 // Remove qubits that are always classical.
256 qubits.retain(|q| self.superposition_qubits.contains(&q.id.into()));
257
258 // Remove operations that don't use any non-classical qubits.
259 operations.retain_mut(|op| self.should_keep_operation_mut(op));
260 }
261
262 finish_circuit(
263 source_lookup,
264 operations,
265 qubits,
266 self.config.group_by_scope,
267 )
268 }
269
270 fn should_keep_operation_mut(&self, op: &mut OperationOrGroup) -> bool {
271 if matches!(op.kind, OperationOrGroupKind::Single) {
272 // This is a normal gate operation, so only keep it if all the qubits are non-classical.
273 op.all_qubits()
274 .iter()
275 .all(|q| self.superposition_qubits.contains(q))
276 } else {
277 // This is a grouped operation, so process the children recursively.
278 let mut used_qubits = FxHashSet::default();
279 op.children_mut()
280 .expect("operation should be a group with children")
281 .retain_mut(|child_op| {
282 // Prune out child ops that don't use any non-classical qubits.
283 // This has the side effect of updating each child op's target qubits.
284 if self.should_keep_operation_mut(child_op) {
285 for q in child_op.all_qubits() {
286 used_qubits.insert(q);
287 }
288 true
289 } else {
290 false
291 }
292 });
293 // Update the targets of this grouped operation to only include qubits actually used by child operations.
294 op.op
295 .targets_mut()
296 .retain(|q| used_qubits.contains(&q.qubit.into()));
297 // Only keep this grouped operation if any of its targets were kept.
298 !op.op.targets_mut().is_empty()
299 }
300 }
301
302 /// Splits the qubit arguments from classical arguments so that the qubits
303 /// can be treated as the targets for custom gates.
304 /// The classical arguments get formatted into a comma-separated list.
305 fn split_qubit_args(&mut self, arg: Value) -> (Vec<usize>, String) {
306 let arg = if let Value::Tuple(vals, _) = arg {
307 vals
308 } else {
309 // Single arguments are not passed as tuples, wrap in an array
310 Rc::new([arg])
311 };
312 let mut qubits = vec![];
313 let mut classical_args = String::new();
314 self.push_vals(&arg, &mut qubits, &mut classical_args);
315 (qubits, classical_args)
316 }
317
318 /// Pushes all qubit values into `qubits`, and formats all classical values into `classical_args`.
319 fn push_val(&self, arg: &Value, qubits: &mut Vec<usize>, classical_args: &mut String) {
320 match arg {
321 Value::Array(vals) => {
322 self.push_list::<'[', ']'>(vals, qubits, classical_args);
323 }
324 Value::Tuple(vals, _) => {
325 self.push_list::<'(', ')'>(vals, qubits, classical_args);
326 }
327 Value::Qubit(q) => {
328 qubits.push(q.deref().0);
329 }
330 v => {
331 let _ = write!(classical_args, "{v}");
332 }
333 }
334 qubits.sort_unstable();
335 qubits.dedup();
336 }
337
338 /// Pushes all qubit values into `qubits`, and formats all
339 /// classical values into `classical_args` as a list.
340 fn push_list<const OPEN: char, const CLOSE: char>(
341 &self,
342 vals: &[Value],
343 qubits: &mut Vec<usize>,
344 classical_args: &mut String,
345 ) {
346 classical_args.push(OPEN);
347 let start = classical_args.len();
348 self.push_vals(vals, qubits, classical_args);
349 if classical_args.len() > start {
350 classical_args.push(CLOSE);
351 } else {
352 classical_args.pop();
353 }
354 }
355
356 /// Pushes all qubit values into `qubits`, and formats all
357 /// classical values into `classical_args` as comma-separated values.
358 fn push_vals(&self, vals: &[Value], qubits: &mut Vec<usize>, classical_args: &mut String) {
359 let mut any = false;
360 for v in vals {
361 let start = classical_args.len();
362 self.push_val(v, qubits, classical_args);
363 if classical_args.len() > start {
364 any = true;
365 classical_args.push_str(", ");
366 }
367 }
368 if any {
369 // remove trailing comma
370 classical_args.pop();
371 classical_args.pop();
372 }
373 }
374
375 fn user_code_call_location(&self, stack: &[Frame]) -> Option<PackageOffset> {
376 if self.config.source_locations {
377 let logical_stack = LogicalStack::from_evaluator_trace(stack);
378 retain_user_frames(&self.user_package_ids, logical_stack)
379 .0
380 .last()
381 .map(|l| {
382 let LogicalStackEntryLocation::Source(location) = *l.location() else {
383 panic!("last frame in stack trace should be a call to an intrinsic")
384 };
385 location
386 })
387 } else {
388 None
389 }
390 }
391
392 fn mark_qubit_in_superposition(&mut self, wire: QubitWire) {
393 assert!(
394 self.config.prune_classical_qubits,
395 "should only be called when pruning is enabled"
396 );
397 self.superposition_qubits.insert(wire);
398 self.classical_one_qubits.remove(&wire);
399 }
400
401 fn flip_classical_qubit(&mut self, wire: QubitWire) {
402 assert!(
403 self.config.prune_classical_qubits,
404 "should only be called when pruning is enabled"
405 );
406 if self.classical_one_qubits.contains(&wire) {
407 self.classical_one_qubits.remove(&wire);
408 } else {
409 self.classical_one_qubits.insert(wire);
410 }
411 }
412
413 fn update_qubit_status(
414 &mut self,
415 name: &str,
416 targets: &[usize],
417 controls: &[usize],
418 ) -> Vec<usize> {
419 match name {
420 "H" | "Rx" | "Ry" | "SX" | "Rxx" | "Ryy" => {
421 // These gates create superpositions, so mark the qubits as non-trimmable
422 for &q in targets {
423 let mapped_q = self.wire_map_builder.wire_map.qubit_wire(q);
424 self.mark_qubit_in_superposition(mapped_q);
425 }
426 }
427 "X" | "Y" => {
428 let mapped_target = self.wire_map_builder.wire_map.qubit_wire(targets[0]);
429 let controls: Vec<usize> = controls
430 .iter()
431 .filter(|c| !self.classical_one_qubits.contains(&(**c).into()))
432 .copied()
433 .collect();
434 if !self.superposition_qubits.contains(&mapped_target) {
435 // The target is not yet marked as non-trimmable, so check the controls.
436 let superposition_controls_count = controls
437 .iter()
438 .filter(|c| self.superposition_qubits.contains(&(**c).into()))
439 .count();
440
441 if controls.is_empty() {
442 // If all controls are classical 1 or there are no controls, the target is flipped
443 self.flip_classical_qubit(mapped_target);
444 } else if superposition_controls_count == controls.len() {
445 // If all controls are in superposition, the target is also in superposition
446 self.mark_qubit_in_superposition(mapped_target);
447 }
448 }
449 return controls;
450 }
451 "Z" => {
452 // Only clean up the classical 1 qubits from the controls list. No need to update the target,
453 // since Z does not introduce superpositions.
454 return controls
455 .iter()
456 .filter(|c| !self.classical_one_qubits.contains(&(**c).into()))
457 .copied()
458 .collect();
459 }
460 "SWAP" => {
461 // If either qubit is non-trimmable, both become non-trimmable
462 let q0_mapped = self.wire_map_builder.wire_map.qubit_wire(targets[0]);
463 let q1_mapped = self.wire_map_builder.wire_map.qubit_wire(targets[1]);
464 if self.superposition_qubits.contains(&q0_mapped)
465 || self.superposition_qubits.contains(&q1_mapped)
466 {
467 self.mark_qubit_in_superposition(q0_mapped);
468 self.mark_qubit_in_superposition(q1_mapped);
469 } else {
470 match (
471 self.classical_one_qubits.contains(&q0_mapped),
472 self.classical_one_qubits.contains(&q1_mapped),
473 ) {
474 (true, false) | (false, true) => {
475 self.flip_classical_qubit(q0_mapped);
476 self.flip_classical_qubit(q1_mapped);
477 }
478 _ => {
479 // Nothing to do if both are classical 0 or both are in superposition
480 }
481 }
482 }
483 }
484 "S" | "T" | "Rz" | "Rzz" => {
485 // These gates don't create superpositions on their own, so do nothing
486 }
487 _ => {
488 // For any other gate, conservatively mark all target qubits as non-trimmable
489 for &q in targets.iter().chain(controls.iter()) {
490 let mapped_q = self.wire_map_builder.wire_map.qubit_wire(q);
491 self.mark_qubit_in_superposition(mapped_q);
492 }
493 }
494 }
495 // Return the normal controls list if no changes were made.
496 controls.to_vec()
497 }
498}
499
500/// Take a sequence of operations and build the final `Circuit`.
501/// Operations are laid out into columns. Unnecessary groups are removed.
502/// Source location metadata is resolved into displayable file/line/column information.
503pub(crate) fn finish_circuit(
504 source_lookup: &impl SourceLookup,
505 mut operations: Vec<OperationOrGroup>,
506 qubits: Vec<Qubit>,
507 collapse_trivial_groups: bool,
508) -> Circuit {
509 if collapse_trivial_groups {
510 collapse_unnecessary_scopes(&mut operations, source_lookup);
511 }
512 let mut loop_id_cache = Default::default();
513 let operations = operations
514 .into_iter()
515 .map(|o| o.into_operation(source_lookup, &mut loop_id_cache))
516 .collect();
517
518 let component_grid = operation_list_to_grid(operations, &qubits);
519 Circuit {
520 qubits,
521 component_grid,
522 }
523}
524
525/// Removes any scopes that are unnecessary and replaces them with their children operations.
526/// An unnecessary loop scope is one that either has a single child iteration,
527/// or has multiple iterations that each operate on distinct sets of qubits (i.e. a "vertical" loop).
528/// An unnecessary lambda scope is one where the lambda has a single child operation.
529fn collapse_unnecessary_scopes(
530 operations: &mut Vec<OperationOrGroup>,
531 source_lookup: &impl SourceLookup,
532) {
533 let mut ops = vec![];
534 for mut op in operations.drain(..) {
535 match &mut op.kind {
536 OperationOrGroupKind::Single => {}
537 OperationOrGroupKind::Group { children, .. } => {
538 collapse_unnecessary_scopes(children, source_lookup);
539 }
540 }
541
542 if let Some(children) = collapse_if_unnecessary(&mut op, source_lookup) {
543 ops.extend(children);
544 } else {
545 ops.push(op);
546 }
547 }
548 *operations = ops;
549}
550
551/// If the given operation or group is an outer scope that can be collapsed,
552/// returns its children operations or groups.
553fn collapse_if_unnecessary(
554 op: &mut OperationOrGroup,
555 source_lookup: &impl SourceLookup,
556) -> Option<Vec<OperationOrGroup>> {
557 if let OperationOrGroupKind::Group {
558 scope_stack,
559 children,
560 } = &mut op.kind
561 {
562 if let Scope::Loop(..) = scope_stack.current_lexical_scope() {
563 if children.len() == 1 {
564 // remove the loop scope
565 let mut only_child = children.remove(0);
566 let OperationOrGroupKind::Group { children, .. } = &mut only_child.kind else {
567 panic!("only child of an outer loop scope should be a group");
568 };
569 return Some(take(children));
570 }
571
572 // now, if each c applies to a distinct set of qubits, this loop is entirely vertical and can be collapsed as well
573 let mut distinct_sets_of_qubits = FxHashSet::default();
574 for child_op in children.iter() {
575 let qs = child_op.all_qubits();
576 if !distinct_sets_of_qubits.insert(qs) {
577 // There's overlap, so we won't collapse
578 return None;
579 }
580 }
581 let mut all_children = vec![];
582 for mut child_op in children.drain(..) {
583 let OperationOrGroupKind::Group { children, .. } = &mut child_op.kind else {
584 panic!("only child of an outer loop scope should be a group");
585 };
586 all_children.extend(take(children));
587 }
588 return Some(all_children);
589 } else if let Scope::Callable(..) = scope_stack.current_lexical_scope()
590 && children.len() == 1
591 && source_lookup
592 .resolve_scope(scope_stack.current_lexical_scope(), &mut Default::default())
593 .name
594 .as_ref()
595 == "<lambda>"
596 {
597 // remove the lambda scope
598 return Some(take(children));
599 }
600 }
601 None
602}
603
604/// Cache for mapping loop source locations to their corresponding package and expression IDs.
605/// This information is repeatedly looked up when resolving loop scopes from RIR debug metadata,
606/// so caching it avoids expensive lookups in the FIR package store.
607pub(crate) type LoopIdCache = FxHashMap<PackageOffset, (PackageId, ExprId)>;
608
609/// Resolves structs that use compilation-specific IDs (`PackageId`s, `ExprId`s etc.)
610/// to user legible names and source file locations.
611pub trait SourceLookup {
612 fn resolve_package_offset(&self, package_offset: &PackageOffset) -> SourceLocation;
613 fn resolve_scope(&self, scope: &Scope, loop_id_cache: &mut LoopIdCache) -> LexicalScope;
614 fn resolve_logical_stack_entry_location(
615 &self,
616 location: LogicalStackEntryLocation,
617 loop_id_cache: &mut LoopIdCache,
618 ) -> Option<PackageOffset>;
619}
620
621impl SourceLookup for (&compile::PackageStore, &fir::PackageStore) {
622 fn resolve_package_offset(&self, package_offset: &PackageOffset) -> SourceLocation {
623 let package = self
624 .0
625 .get(map_fir_package_to_hir(package_offset.package_id))
626 .expect("package id must exist in store");
627
628 let source = package
629 .sources
630 .find_by_offset(package_offset.offset)
631 .expect("source should exist for offset");
632
633 let pos = Position::from_utf8_byte_offset(
634 Encoding::Utf8,
635 &source.contents,
636 package_offset.offset - source.offset,
637 );
638
639 SourceLocation {
640 file: source.name.to_string(),
641 line: pos.line,
642 column: pos.column,
643 }
644 }
645
646 fn resolve_scope(&self, scope_id: &Scope, loop_id_cache: &mut LoopIdCache) -> LexicalScope {
647 match scope_id {
648 Scope::Callable(CallableId::Id(store_item_id, functor_app)) => {
649 let item = self.1.get_item(*store_item_id);
650
651 let fir::ItemKind::Callable(callable_decl) = &item.kind else {
652 panic!("only callables should be in the stack")
653 };
654
655 let scope_offset = callable_scope_offset(callable_decl, *functor_app);
656
657 LexicalScope {
658 location: Some(PackageOffset {
659 package_id: store_item_id.package,
660 offset: scope_offset,
661 }),
662 name: callable_decl.name.name.clone(),
663 is_adjoint: functor_app.adjoint,
664 is_classically_controlled: false,
665 }
666 }
667 Scope::Callable(CallableId::Source(package_offset, name)) => {
668 // trim the trailing dagger symbol and set `is_adjoint` accordingly
669 let (name, is_adjoint) = if let Some(pos) = name.rfind('\'') {
670 if pos == name.len() - 1 {
671 (name[..pos].to_string().into(), true)
672 } else {
673 (name.clone(), false)
674 }
675 } else {
676 (name.clone(), false)
677 };
678 LexicalScope {
679 location: Some(*package_offset),
680 name,
681 is_adjoint,
682 is_classically_controlled: false,
683 }
684 }
685 Scope::Loop(loop_id) => {
686 let found_loop_expr = find_loop(self.1, loop_id_cache, loop_id);
687 if let (Some((package_id, expr_id)), package_offset) = found_loop_expr {
688 let (package, cond_expr_id, _) =
689 get_loop_by_expr_id(self.1, package_id, expr_id);
690 let cond_expr = package.get_expr(cond_expr_id);
691 let expr_contents = self
692 .0
693 .get(map_fir_package_to_hir(package_id))
694 .and_then(|p| p.sources.find_by_offset(cond_expr.span.lo))
695 .map(|s| {
696 s.contents[(cond_expr.span.lo - s.offset) as usize
697 ..(cond_expr.span.hi - s.offset) as usize]
698 .to_string()
699 });
700
701 LexicalScope {
702 name: format!("loop: {}", expr_contents.unwrap_or_default()).into(),
703 location: Some(package_offset),
704 is_adjoint: false,
705 is_classically_controlled: false,
706 }
707 } else {
708 LexicalScope {
709 name: "loop".into(),
710 location: Some(found_loop_expr.1),
711 is_adjoint: false,
712 is_classically_controlled: false,
713 }
714 }
715 }
716 Scope::LoopIteration(loop_id, i) => {
717 let package_offset = match loop_id {
718 LoopId::Id(package_id, expr_id) => {
719 let (package, _, body_block_id) =
720 get_loop_by_expr_id(self.1, *package_id, *expr_id);
721 let block = package.get_block(body_block_id);
722 PackageOffset {
723 package_id: *package_id,
724 offset: block.span.lo,
725 }
726 }
727 LoopId::Source(package_offset) => *package_offset,
728 };
729 LexicalScope {
730 name: format!("({i})").into(),
731 location: Some(package_offset),
732 is_adjoint: false,
733 is_classically_controlled: false,
734 }
735 }
736 Scope::Top => LexicalScope {
737 name: "top".into(),
738 location: None,
739 is_adjoint: false,
740 is_classically_controlled: false,
741 },
742 Scope::ClassicallyControlled {
743 label,
744 control_result_ids: _,
745 } => LexicalScope {
746 location: None,
747 name: label.clone().into(),
748 is_adjoint: false,
749 is_classically_controlled: true,
750 },
751 }
752 }
753
754 fn resolve_logical_stack_entry_location(
755 &self,
756 location: LogicalStackEntryLocation,
757 loop_id_cache: &mut LoopIdCache,
758 ) -> Option<PackageOffset> {
759 match location {
760 LogicalStackEntryLocation::Unknown => None,
761 LogicalStackEntryLocation::Branch(package_offset, _) => package_offset,
762 LogicalStackEntryLocation::Source(package_offset)
763 | LogicalStackEntryLocation::Loop(LoopId::Source(package_offset)) => {
764 Some(package_offset)
765 }
766 LogicalStackEntryLocation::Loop(LoopId::Id(package_id, loop_expr_id)) => {
767 let fir_package_store = self.1;
768 let package = fir_package_store.get(package_id);
769 let expr = package.get_expr(loop_expr_id);
770
771 Some(PackageOffset {
772 package_id,
773 offset: expr.span.lo,
774 })
775 }
776 LogicalStackEntryLocation::LoopIteration(LoopId::Id(package_id, expr_id), _) => {
777 let (package, _, body_block_id) = get_loop_by_expr_id(self.1, package_id, expr_id);
778 let block = package.get_block(body_block_id);
779
780 Some(PackageOffset {
781 package_id,
782 offset: block.span.lo,
783 })
784 }
785 LogicalStackEntryLocation::LoopIteration(LoopId::Source(package_offset), _) => {
786 let found_loop_expr = if let Some(cached) = loop_id_cache.get(&package_offset) {
787 Some(*cached)
788 } else {
789 let val = find_loop_by_source_offset(self.1, &package_offset);
790 if let Some(val) = val {
791 // cache the result
792 loop_id_cache.insert(package_offset, val);
793 }
794 val
795 };
796
797 if let Some((package_id, expr_id)) = found_loop_expr {
798 let (package, _, body_block_id) =
799 get_loop_by_expr_id(self.1, package_id, expr_id);
800 let block = package.get_block(body_block_id);
801
802 Some(PackageOffset {
803 package_id,
804 offset: block.span.lo,
805 })
806 } else {
807 // Fall back to loop expr location
808 Some(package_offset)
809 }
810 }
811 }
812 }
813}
814
815fn callable_scope_offset(callable_decl: &fir::CallableDecl, functor_app: FunctorApp) -> u32 {
816 match &callable_decl.implementation {
817 fir::CallableImpl::Intrinsic => callable_decl.span.lo,
818 fir::CallableImpl::Spec(spec_impl) => {
819 if functor_app.adjoint && functor_app.controlled > 0 {
820 spec_impl.ctl_adj.as_ref().unwrap_or(&spec_impl.body)
821 } else if functor_app.adjoint {
822 spec_impl.adj.as_ref().unwrap_or(&spec_impl.body)
823 } else if functor_app.controlled > 0 {
824 spec_impl.ctl.as_ref().unwrap_or(&spec_impl.body)
825 } else {
826 &spec_impl.body
827 }
828 .span
829 .lo
830 }
831 fir::CallableImpl::SimulatableIntrinsic(spec_decl) => spec_decl.span.lo,
832 }
833}
834
835fn find_loop(
836 fir_store: &fir::PackageStore,
837 loop_id_cache: &mut LoopIdCache,
838 loop_id: &LoopId,
839) -> (Option<(PackageId, ExprId)>, PackageOffset) {
840 match loop_id {
841 LoopId::Id(package_id, expr_id) => {
842 let package_offset = PackageOffset {
843 package_id: *package_id,
844 offset: fir_store.get(*package_id).get_expr(*expr_id).span.lo,
845 };
846 (Some((*package_id, *expr_id)), package_offset)
847 }
848 LoopId::Source(package_offset) => {
849 if let Some(cached) = loop_id_cache.get(package_offset) {
850 (Some(*cached), *package_offset)
851 } else {
852 let val = find_loop_by_source_offset(fir_store, package_offset);
853 if let Some(val) = val {
854 // cache the result
855 loop_id_cache.insert(*package_offset, val);
856 }
857 (val, *package_offset)
858 }
859 }
860 }
861}
862
863fn find_loop_by_source_offset(
864 fir_store: &fir::PackageStore,
865 package_offset: &PackageOffset,
866) -> Option<(PackageId, ExprId)> {
867 fir_store
868 .get(package_offset.package_id)
869 .exprs
870 .iter()
871 .find_map(|(expr_id, expr)| {
872 if expr.span.lo == package_offset.offset && matches!(expr.kind, ExprKind::While(_, _)) {
873 Some((package_offset.package_id, expr_id))
874 } else {
875 None
876 }
877 })
878}
879
880fn get_loop_by_expr_id(
881 fir_store: &fir::PackageStore,
882 package_id: PackageId,
883 expr_id: ExprId,
884) -> (&fir::Package, fir::ExprId, fir::BlockId) {
885 let package = fir_store.get(package_id);
886 let loop_expr = package.get_expr(expr_id);
887 let ExprKind::While(cond_expr_id, body_block_id) = &loop_expr.kind else {
888 panic!("only while loops are expected in FIR");
889 };
890 (package, *cond_expr_id, *body_block_id)
891}
892
893#[allow(clippy::struct_excessive_bools)]
894#[derive(Clone, Debug, Copy)]
895pub struct TracerConfig {
896 /// Maximum number of operations the builder will add to the circuit
897 pub max_operations: usize,
898 /// Capture the source code locations of operations and qubit declarations
899 /// in the circuit diagram
900 pub source_locations: bool,
901 /// Group operations according to call graph in the circuit diagram
902 pub group_by_scope: bool,
903 /// Prune purely classical or unused qubits
904 pub prune_classical_qubits: bool,
905}
906
907impl TracerConfig {
908 /// Set to the current UI limit + 1 so that it still triggers
909 /// the "this circuit has too many gates" warning in the UI.
910 /// (see npm\qsharp\ux\circuit.tsx)
911 ///
912 /// A more refined way to do this might be to communicate the
913 /// "limit exceeded" state up to the UI somehow.
914 pub const DEFAULT_MAX_OPERATIONS: usize = 10001;
915}
916
917/// Maps qubit IDs to their corresponding wire IDs and tracks measurement results
918/// along with their source locations.
919#[derive(Default)]
920pub(crate) struct WireMap {
921 /// Maps qubit IDs to their assigned wire IDs.
922 qubits: IndexMap<usize, QubitWire>,
923 /// Maps wire IDs to their declaration locations and measurement result IDs.
924 qubit_wires: IndexMap<QubitWire, (Vec<PackageOffset>, Vec<usize>)>,
925}
926
927impl WireMap {
928 pub(crate) fn qubit_wire(&self, qubit_id: usize) -> QubitWire {
929 self.qubits
930 .get(qubit_id)
931 .unwrap_or_else(|| panic!("qubit {qubit_id} should already be mapped"))
932 .to_owned()
933 }
934
935 pub(crate) fn result_wire(&self, result_id: usize) -> ResultWire {
936 self.qubit_wires
937 .iter()
938 .find_map(|(QubitWire(qubit_wire), (_, results))| {
939 let r_idx = results.iter().position(|&r| r == result_id);
940 r_idx.map(|r_idx| ResultWire(qubit_wire, r_idx))
941 })
942 .expect("result should already be mapped")
943 }
944
945 pub(crate) fn to_qubits(&self, source_lookup: &impl SourceLookup) -> Vec<Qubit> {
946 let mut qubits = vec![];
947 for (QubitWire(wire_id), (declarations, results)) in self.qubit_wires.iter() {
948 qubits.push(Qubit {
949 id: wire_id,
950 num_results: results.len(),
951 declarations: declarations
952 .iter()
953 .map(|offset| source_lookup.resolve_package_offset(offset))
954 .collect(),
955 });
956 }
957
958 qubits
959 }
960}
961
962#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
963pub(crate) struct ResultWire(pub(crate) usize, pub(crate) usize);
964
965#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
966pub(crate) struct QubitWire(pub(crate) usize);
967
968impl From<usize> for QubitWire {
969 fn from(value: usize) -> Self {
970 QubitWire(value)
971 }
972}
973
974impl From<QubitWire> for usize {
975 fn from(value: QubitWire) -> Self {
976 value.0
977 }
978}
979
980/// Manages the mapping between qubits and wires during circuit construction.
981/// Tracks qubit allocations, measurement results, and their source locations.
982/// Also acts as a result ID allocator when the result IDs aren't passed in
983/// by the tracer.
984///
985/// This implementation is similar to the partial evaluation resource manager,
986/// which is used in RIR/QIR generation, in its Qubit ID and Result ID management.
987/// (see `source/compiler/qsc_partial_eval/src/management.rs`)
988pub(crate) struct WireMapBuilder {
989 next_qubit_wire_id: QubitWire,
990 wire_map: WireMap,
991}
992
993impl Default for WireMapBuilder {
994 fn default() -> Self {
995 Self {
996 next_qubit_wire_id: QubitWire(0),
997 wire_map: WireMap::default(),
998 }
999 }
1000}
1001
1002impl WireMapBuilder {
1003 fn new(qubit_input_decls: Vec<PackageOffset>) -> Self {
1004 let mut new = Self {
1005 next_qubit_wire_id: QubitWire(0),
1006 wire_map: WireMap::default(),
1007 };
1008
1009 let mut i = new.next_qubit_wire_id;
1010 for decl in qubit_input_decls {
1011 new.wire_map.qubit_wires.insert(i, (vec![decl], vec![]));
1012 i.0 += 1;
1013 }
1014
1015 new
1016 }
1017
1018 pub fn current(&self) -> &WireMap {
1019 &self.wire_map
1020 }
1021
1022 pub fn map_qubit(&mut self, qubit: usize, declared_at: Option<PackageOffset>) {
1023 let mapped = self.next_qubit_wire_id;
1024 self.next_qubit_wire_id.0 += 1;
1025 self.wire_map.qubits.insert(qubit, mapped);
1026
1027 if let Some(q) = self.wire_map.qubit_wires.get_mut(mapped) {
1028 if let Some(location) = declared_at {
1029 q.0.push(location);
1030 }
1031 } else {
1032 let l = declared_at.map(|l| vec![l]).unwrap_or_default();
1033 self.wire_map.qubit_wires.insert(mapped, (l, vec![]));
1034 }
1035 }
1036
1037 pub(crate) fn into_wire_map(self) -> WireMap {
1038 self.wire_map
1039 }
1040
1041 fn unmap_qubit(&mut self, q: usize) {
1042 // Simple behavior assuming qubits are always released in reverse order of allocation
1043 self.next_qubit_wire_id.0 -= 1;
1044 self.wire_map.qubits.remove(q);
1045 }
1046
1047 pub fn link_result_to_qubit(&mut self, q: usize, r: usize) {
1048 let mapped_q = self.wire_map.qubit_wire(q);
1049 let Some((_, measurements)) = self.wire_map.qubit_wires.get_mut(mapped_q) else {
1050 panic!("qubit should already be mapped");
1051 };
1052 if !measurements.contains(&r) {
1053 measurements.push(r);
1054 }
1055 }
1056
1057 fn swap(&mut self, q0: usize, q1: usize) {
1058 let q0_mapped = self.wire_map.qubit_wire(q0);
1059 let q1_mapped = self.wire_map.qubit_wire(q1);
1060 self.wire_map.qubits.insert(q0, q1_mapped);
1061 self.wire_map.qubits.insert(q1, q0_mapped);
1062 }
1063}
1064
1065#[derive(Clone)]
1066pub(crate) struct OperationOrGroup {
1067 kind: OperationOrGroupKind,
1068 location: Option<LogicalStackEntryLocation>,
1069 op: Operation,
1070}
1071
1072#[derive(Clone)]
1073enum OperationOrGroupKind {
1074 Single,
1075 Group {
1076 scope_stack: ScopeStack,
1077 children: Vec<OperationOrGroup>,
1078 },
1079}
1080
1081impl OperationOrGroup {
1082 fn new_single(op: Operation) -> Self {
1083 Self {
1084 kind: OperationOrGroupKind::Single,
1085 op,
1086 location: None,
1087 }
1088 }
1089
1090 fn new_unitary(
1091 name: &str,
1092 is_adjoint: bool,
1093 targets: &[QubitWire],
1094 controls: &[QubitWire],
1095 args: Vec<String>,
1096 ) -> Self {
1097 Self::new_single(Operation::Unitary(Unitary {
1098 gate: name.to_string(),
1099 args,
1100 children: vec![],
1101 targets: targets
1102 .iter()
1103 .map(|q| Register {
1104 qubit: q.0,
1105 result: None,
1106 })
1107 .collect(),
1108 controls: controls
1109 .iter()
1110 .map(|q| Register {
1111 qubit: q.0,
1112 result: None,
1113 })
1114 .collect(),
1115 is_adjoint,
1116 is_conditional: false,
1117 metadata: None,
1118 }))
1119 }
1120
1121 fn new_measurement(label: &str, qubit: QubitWire, result: ResultWire) -> Self {
1122 Self::new_single(Operation::Measurement(Measurement {
1123 gate: label.to_string(),
1124 args: vec![],
1125 children: vec![],
1126 qubits: vec![Register {
1127 qubit: qubit.0,
1128 result: None,
1129 }],
1130 results: vec![Register {
1131 qubit: result.0,
1132 result: Some(result.1),
1133 }],
1134 metadata: None,
1135 }))
1136 }
1137
1138 fn new_reset(qubit: QubitWire) -> Self {
1139 Self::new_single(Operation::Ket(Ket {
1140 gate: "0".to_string(),
1141 args: vec![],
1142 children: vec![],
1143 targets: vec![Register {
1144 qubit: qubit.0,
1145 result: None,
1146 }],
1147 metadata: None,
1148 }))
1149 }
1150
1151 fn all_qubits(&self) -> Vec<QubitWire> {
1152 let qubits: FxHashSet<QubitWire> = match &self.op {
1153 Operation::Measurement(measurement) => measurement.qubits.clone(),
1154 Operation::Unitary(unitary) => unitary
1155 .targets
1156 .iter()
1157 .chain(unitary.controls.iter())
1158 .filter(|r| r.result.is_none())
1159 .cloned()
1160 .collect(),
1161 Operation::Ket(ket) => ket.targets.clone(),
1162 }
1163 .into_iter()
1164 .map(|r| QubitWire(r.qubit))
1165 .collect();
1166 qubits.into_iter().collect()
1167 }
1168
1169 fn target_results(&self) -> Vec<ResultWire> {
1170 let results: FxHashSet<ResultWire> = match &self.op {
1171 Operation::Measurement(measurement) => measurement
1172 .results
1173 .iter()
1174 .filter_map(|r| r.result.map(|res| ResultWire(r.qubit, res)))
1175 .collect(),
1176 Operation::Unitary(unitary) => unitary
1177 .targets
1178 .iter()
1179 .filter_map(|r| r.result.map(|res| ResultWire(r.qubit, res)))
1180 .collect(),
1181 Operation::Ket(_) => vec![],
1182 }
1183 .into_iter()
1184 .collect();
1185 results.into_iter().collect()
1186 }
1187
1188 fn control_results(&self) -> Vec<ResultWire> {
1189 let results: FxHashSet<ResultWire> = match &self.op {
1190 Operation::Unitary(unitary) => unitary
1191 .controls
1192 .iter()
1193 .filter_map(|r| r.result.map(|res| ResultWire(r.qubit, res)))
1194 .collect(),
1195 Operation::Measurement(_) | Operation::Ket(_) => vec![],
1196 }
1197 .into_iter()
1198 .collect();
1199 results.into_iter().collect()
1200 }
1201
1202 fn children(&self) -> Option<&Vec<Self>>
1203 where
1204 Self: std::marker::Sized,
1205 {
1206 if let OperationOrGroupKind::Group { children, .. } = &self.kind {
1207 Some(children)
1208 } else {
1209 None
1210 }
1211 }
1212
1213 fn children_mut(&mut self) -> Option<&mut Vec<Self>>
1214 where
1215 Self: std::marker::Sized,
1216 {
1217 if let OperationOrGroupKind::Group { children, .. } = &mut self.kind {
1218 Some(children)
1219 } else {
1220 None
1221 }
1222 }
1223
1224 fn new_group(scope_stack: ScopeStack, wire_map: &WireMap) -> Self {
1225 let mut control_result_ids_map = vec![];
1226 let mut control_result_registers = vec![];
1227 let mut metadata = None;
1228
1229 if let Scope::ClassicallyControlled {
1230 control_result_ids, ..
1231 } = scope_stack.current_lexical_scope()
1232 {
1233 for result_id in control_result_ids {
1234 let result_wire = wire_map.result_wire(*result_id);
1235 let register = Register {
1236 qubit: result_wire.0,
1237 result: Some(result_wire.1),
1238 };
1239 control_result_ids_map.push((register.clone(), *result_id));
1240 control_result_registers.push(register);
1241 }
1242
1243 metadata = Some(Metadata {
1244 control_result_ids: control_result_ids_map,
1245 ..Default::default()
1246 });
1247 }
1248
1249 Self {
1250 kind: OperationOrGroupKind::Group {
1251 scope_stack,
1252 children: vec![],
1253 },
1254 op: Operation::Unitary(Unitary {
1255 // Most fields here are to be filled in later, in `into_operation`.
1256 gate: String::new(),
1257 args: vec![],
1258 children: vec![],
1259 targets: control_result_registers.clone(),
1260 controls: control_result_registers,
1261 is_adjoint: false,
1262 metadata,
1263 is_conditional: false,
1264 }),
1265 location: None,
1266 }
1267 }
1268
1269 fn extend_target_qubits(&mut self, target_qubits: &[QubitWire]) {
1270 match &mut self.op {
1271 Operation::Measurement(_) => {}
1272 Operation::Unitary(unitary) => {
1273 unitary
1274 .targets
1275 .extend(target_qubits.iter().map(|q| Register {
1276 qubit: q.0,
1277 result: None,
1278 }));
1279 unitary
1280 .targets
1281 .sort_unstable_by_key(|r| (r.qubit, r.result));
1282 unitary.targets.dedup();
1283 }
1284 Operation::Ket(ket) => {
1285 ket.targets.extend(target_qubits.iter().map(|q| Register {
1286 qubit: q.0,
1287 result: None,
1288 }));
1289 }
1290 }
1291 }
1292
1293 fn extend_target_results(&mut self, target_results: &[ResultWire]) {
1294 match &mut self.op {
1295 Operation::Measurement(measurement) => {
1296 measurement
1297 .results
1298 .extend(target_results.iter().map(|r| Register {
1299 qubit: r.0,
1300 result: Some(r.1),
1301 }));
1302 measurement
1303 .results
1304 .sort_unstable_by_key(|reg| (reg.qubit, reg.result));
1305 measurement.results.dedup();
1306 }
1307 Operation::Unitary(unitary) => {
1308 unitary
1309 .targets
1310 .extend(target_results.iter().map(|r| Register {
1311 qubit: r.0,
1312 result: Some(r.1),
1313 }));
1314 unitary
1315 .targets
1316 .sort_unstable_by_key(|r| (r.qubit, r.result));
1317 unitary.targets.dedup();
1318 }
1319 Operation::Ket(_) => {}
1320 }
1321 }
1322
1323 fn scope_stack_if_group(&self) -> Option<&ScopeStack> {
1324 if let OperationOrGroupKind::Group { scope_stack, .. } = &self.kind {
1325 Some(scope_stack)
1326 } else {
1327 None
1328 }
1329 }
1330
1331 fn into_operation(
1332 mut self,
1333 source_lookup: &impl SourceLookup,
1334 loop_id_cache: &mut LoopIdCache,
1335 ) -> Operation {
1336 if let Some(location) = self.location {
1337 let package_offset =
1338 source_lookup.resolve_logical_stack_entry_location(location, loop_id_cache);
1339
1340 if let Some(package_offset) = package_offset {
1341 let location = source_lookup.resolve_package_offset(&package_offset);
1342 self.op.source_location_mut().replace(location);
1343 }
1344 }
1345
1346 match self.kind {
1347 OperationOrGroupKind::Single => self.op,
1348 OperationOrGroupKind::Group {
1349 scope_stack,
1350 children,
1351 } => {
1352 let Operation::Unitary(u) = &mut self.op else {
1353 panic!("group operation should be a unitary")
1354 };
1355
1356 let scope = source_lookup.resolve_scope(&scope_stack.scope, loop_id_cache);
1357 u.gate = scope.name.to_string();
1358 u.is_adjoint = scope.is_adjoint;
1359 let scope_location = scope
1360 .location
1361 .map(|loc| source_lookup.resolve_package_offset(&loc));
1362
1363 u.is_conditional = scope.is_classically_controlled;
1364
1365 if u.metadata.is_none() {
1366 u.metadata = Some(Metadata::default());
1367 }
1368
1369 if let Some(md) = &mut u.metadata {
1370 md.scope_location = scope_location;
1371 } else {
1372 unreachable!("metadata should have been set");
1373 }
1374
1375 u.children = vec![ComponentColumn {
1376 components: children
1377 .into_iter()
1378 .map(|o| o.into_operation(source_lookup, loop_id_cache))
1379 .collect(),
1380 }];
1381 self.op
1382 }
1383 }
1384 }
1385
1386 fn merge_inputs(&mut self, op: &OperationOrGroup) {
1387 self.extend_target_qubits(&op.all_qubits());
1388 self.extend_target_results(&op.target_results());
1389 self.extend_target_results(&op.control_results());
1390 }
1391}
1392
1393/// Builds a list of circuit operations with a maximum operation limit.
1394/// Stops adding operations once the limit is exceeded.
1395///
1396/// Methods take `WireMap` as a parameter to resolve qubit and result IDs
1397/// to their corresponding wire positions in the circuit diagram.
1398pub(crate) struct OperationListBuilder {
1399 max_ops: usize,
1400 max_ops_exceeded: bool,
1401 top: OperationOrGroup,
1402 user_package_ids: Vec<PackageId>,
1403 grouping_config: GroupingConfig,
1404}
1405
1406#[derive(Clone, Copy)]
1407struct GroupingConfig {
1408 source_locations: bool,
1409 group_by_scope: bool,
1410}
1411
1412impl OperationListBuilder {
1413 pub fn new(
1414 max_operations: usize,
1415 user_package_ids: Vec<PackageId>,
1416 group_by_scope: bool,
1417 source_locations: bool,
1418 ) -> Self {
1419 Self {
1420 max_ops: max_operations,
1421 max_ops_exceeded: false,
1422 top: OperationOrGroup::new_group(ScopeStack::top(), &WireMap::default()),
1423 grouping_config: GroupingConfig {
1424 source_locations,
1425 group_by_scope,
1426 },
1427 user_package_ids,
1428 }
1429 }
1430
1431 fn push_op(
1432 &mut self,
1433 op: OperationOrGroup,
1434 unfiltered_call_stack: LogicalStack,
1435 wire_map: &WireMap,
1436 ) {
1437 if self.max_ops_exceeded
1438 || self
1439 .top
1440 .children()
1441 .expect("container should be a group")
1442 .len()
1443 >= self.max_ops
1444 {
1445 // Stop adding gates and leave the circuit as is
1446 self.max_ops_exceeded = true;
1447 return;
1448 }
1449
1450 let op_call_stack =
1451 if self.grouping_config.group_by_scope || self.grouping_config.source_locations {
1452 retain_user_frames(&self.user_package_ids, unfiltered_call_stack)
1453 } else {
1454 LogicalStack::default()
1455 };
1456
1457 add_scoped_op(
1458 &mut self.top,
1459 &ScopeStack::top(),
1460 op,
1461 &op_call_stack,
1462 self.grouping_config.group_by_scope,
1463 self.grouping_config.source_locations,
1464 wire_map,
1465 );
1466 }
1467
1468 fn operations(&self) -> &Vec<OperationOrGroup> {
1469 self.top.children().expect("container should be a group")
1470 }
1471
1472 pub(crate) fn into_operations(self) -> Vec<OperationOrGroup> {
1473 let OperationOrGroupKind::Group { children, .. } = self.top.kind else {
1474 panic!("container should be a group");
1475 };
1476 children
1477 }
1478}
1479
1480pub(crate) struct GateInputs<'a> {
1481 pub(crate) targets: &'a [usize],
1482 pub(crate) controls: &'a [usize],
1483}
1484
1485/// Trait representing a receiver of circuit operations that can accept
1486/// gates, measurements, and resets into an internal operation list.
1487pub(crate) trait OperationReceiver {
1488 fn gate(
1489 &mut self,
1490 wire_map: &WireMap,
1491 name: &str,
1492 is_adjoint: bool,
1493 inputs: &GateInputs,
1494 args: Vec<String>,
1495 call_stack: LogicalStack,
1496 );
1497
1498 fn measurement(
1499 &mut self,
1500 wire_map: &WireMap,
1501 name: &str,
1502 qubit: usize,
1503 result: usize,
1504 call_stack: LogicalStack,
1505 );
1506
1507 fn reset(&mut self, wire_map: &WireMap, qubit: usize, call_stack: LogicalStack);
1508}
1509
1510impl OperationReceiver for OperationListBuilder {
1511 fn gate(
1512 &mut self,
1513 wire_map: &WireMap,
1514 name: &str,
1515 is_adjoint: bool,
1516 inputs: &GateInputs,
1517 args: Vec<String>,
1518 call_stack: LogicalStack,
1519 ) {
1520 let targets = inputs
1521 .targets
1522 .iter()
1523 .map(|q| wire_map.qubit_wire(*q))
1524 .collect::<Vec<_>>();
1525 let controls = inputs
1526 .controls
1527 .iter()
1528 .map(|q| wire_map.qubit_wire(*q))
1529 .collect::<Vec<_>>();
1530 self.push_op(
1531 OperationOrGroup::new_unitary(name, is_adjoint, &targets, &controls, args),
1532 call_stack,
1533 wire_map,
1534 );
1535 }
1536
1537 fn measurement(
1538 &mut self,
1539 wire_map: &WireMap,
1540 name: &str,
1541 qubit: usize,
1542 result: usize,
1543 call_stack: LogicalStack,
1544 ) {
1545 let qubit = wire_map.qubit_wire(qubit);
1546 let result = wire_map.result_wire(result);
1547 if name == "MResetZ" {
1548 self.push_op(
1549 OperationOrGroup::new_measurement("M", qubit, result),
1550 call_stack.clone(),
1551 wire_map,
1552 );
1553 self.push_op(OperationOrGroup::new_reset(qubit), call_stack, wire_map);
1554 } else {
1555 self.push_op(
1556 OperationOrGroup::new_measurement(name, qubit, result),
1557 call_stack.clone(),
1558 wire_map,
1559 );
1560 }
1561 }
1562
1563 fn reset(&mut self, wire_map: &WireMap, qubit: usize, call_stack: LogicalStack) {
1564 let qubit = wire_map.qubit_wire(qubit);
1565 self.push_op(OperationOrGroup::new_reset(qubit), call_stack, wire_map);
1566 }
1567}
1568
1569/// Represents a scope with name and location information all resolved.
1570/// Ultimately corresponds to a group in the circuit diagram.
1571pub struct LexicalScope {
1572 /// The start offset of the scope, used for navigation.
1573 pub(crate) location: Option<PackageOffset>,
1574 /// A display name for the scope.
1575 pub(crate) name: Rc<str>,
1576 /// Whether the scope represents an adjoint operation,
1577 /// used for display purposes.
1578 pub(crate) is_adjoint: bool,
1579 /// Whether the scope is classically controlled, or contains any operations or parameters
1580 /// that are classically controlled.
1581 pub(crate) is_classically_controlled: bool,
1582}
1583
1584pub(crate) fn add_scoped_op(
1585 current_container: &mut OperationOrGroup,
1586 current_scope_stack: &ScopeStack,
1587 mut op: OperationOrGroup,
1588 op_call_stack: &LogicalStack,
1589 group_by_scope: bool,
1590 set_source_location: bool,
1591 wire_map: &WireMap,
1592) {
1593 if set_source_location && let Some(called_at) = op_call_stack.0.last() {
1594 op.location = Some(*called_at.location());
1595 }
1596
1597 let default = LogicalStack::default();
1598 let op_call_stack = if group_by_scope {
1599 op_call_stack
1600 } else {
1601 &default
1602 };
1603
1604 let Some(relative_stack) = strip_scope_stack_prefix(op_call_stack, current_scope_stack) else {
1605 panic!("op_call_stack should be a child of current_scope_stack",);
1606 };
1607
1608 if !relative_stack.0.is_empty() {
1609 if let Some(last_op) = current_container
1610 .children_mut()
1611 .expect("currentcontainer should be a group")
1612 .last_mut()
1613 {
1614 // See if we can add to the last scope inside the current container
1615 if let Some(last_scope_stack) = last_op.scope_stack_if_group()
1616 && strip_scope_stack_prefix(op_call_stack, last_scope_stack).is_some()
1617 {
1618 // The last scope matched, add to it
1619 let last_scope_stack = last_scope_stack.clone();
1620
1621 // Recursively add to the children
1622 add_scoped_op(
1623 last_op,
1624 &last_scope_stack,
1625 op.clone(),
1626 op_call_stack,
1627 group_by_scope,
1628 set_source_location,
1629 wire_map,
1630 );
1631 current_container.merge_inputs(&op);
1632
1633 return;
1634 }
1635 }
1636
1637 let op_scope_stack = scope_stack(op_call_stack);
1638 if *current_scope_stack != op_scope_stack {
1639 // Need to create a new scope group
1640 let mut scope_group = OperationOrGroup::new_group(op_scope_stack, wire_map);
1641 scope_group.merge_inputs(&op);
1642 *scope_group
1643 .children_mut()
1644 .expect("operation should be a group") = vec![op];
1645
1646 let parent = LogicalStack(
1647 op_call_stack
1648 .0
1649 .split_last()
1650 .expect("should have more than one frame")
1651 .1
1652 .to_vec(),
1653 );
1654
1655 // Recursively add the new scope group to the current container
1656 add_scoped_op(
1657 current_container,
1658 current_scope_stack,
1659 scope_group.clone(),
1660 &parent,
1661 group_by_scope,
1662 set_source_location,
1663 wire_map,
1664 );
1665 current_container.merge_inputs(&scope_group);
1666
1667 return;
1668 }
1669 }
1670
1671 current_container.merge_inputs(&op);
1672 current_container
1673 .children_mut()
1674 .expect("current_container should be a group")
1675 .push(op);
1676}
1677
1678pub(crate) fn retain_user_frames(
1679 user_package_ids: &[PackageId],
1680 mut location_stack: LogicalStack,
1681) -> LogicalStack {
1682 location_stack.0.retain(|location| {
1683 let package_id = location.package_id();
1684 // If no package ID, always include
1685 package_id.is_none_or(|package_id| {
1686 user_package_ids.is_empty() || user_package_ids.contains(&package_id)
1687 })
1688 });
1689 LogicalStack(location_stack.0)
1690}
1691
1692/// Represents a scope in the call stack, tracking the caller chain and current scope identifier.
1693#[derive(Clone, PartialEq)]
1694pub(crate) struct ScopeStack {
1695 caller: LogicalStack,
1696 scope: Scope,
1697}
1698
1699impl ScopeStack {
1700 pub(crate) fn new(caller: LogicalStack, scope: Scope) -> Self {
1701 Self { caller, scope }
1702 }
1703 pub(crate) fn caller(&self) -> &LogicalStack {
1704 &self.caller
1705 }
1706
1707 pub(crate) fn current_lexical_scope(&self) -> &Scope {
1708 &self.scope
1709 }
1710
1711 pub(crate) fn is_top(&self) -> bool {
1712 self.caller.0.is_empty() && self.scope == Scope::default()
1713 }
1714
1715 pub(crate) fn top() -> Self {
1716 ScopeStack {
1717 caller: LogicalStack::default(),
1718 scope: Scope::default(),
1719 }
1720 }
1721
1722 pub(crate) fn extend(&self, location: LogicalStackEntryLocation) -> LogicalStack {
1723 let mut new_stack = self.caller.0.clone();
1724 new_stack.push(LogicalStackEntry {
1725 location,
1726 scope: self.scope.clone(),
1727 });
1728 LogicalStack(new_stack)
1729 }
1730}
1731
1732/// Strips a scope stack prefix from a call stack.
1733///
1734/// The `full_call_stack` parameter represents a complete call stack, while
1735/// `prefix_scope_stack` represents a scope stack to match against.
1736///
1737/// If `prefix_scope_stack` is not a prefix of `full_call_stack`, this function returns `None`.
1738///
1739/// If it is a prefix, this function returns the remainder of `full_call_stack` after removing
1740/// the prefix, starting from the first location in the call stack that is in the scope of
1741/// `prefix_scope_stack.scope`.
1742fn strip_scope_stack_prefix(
1743 full_call_stack: &LogicalStack,
1744 prefix_scope_stack: &ScopeStack,
1745) -> Option<LogicalStack> {
1746 if prefix_scope_stack.is_top() {
1747 return Some(full_call_stack.clone());
1748 }
1749
1750 if full_call_stack.0.len() > prefix_scope_stack.caller().0.len()
1751 && let Some(rest) = full_call_stack
1752 .0
1753 .strip_prefix(prefix_scope_stack.caller().0.as_slice())
1754 && rest[0].lexical_scope() == prefix_scope_stack.current_lexical_scope()
1755 {
1756 assert!(!rest.is_empty());
1757 return Some(LogicalStack(rest.to_vec()));
1758 }
1759 None
1760}
1761
1762fn scope_stack(instruction_stack: &LogicalStack) -> ScopeStack {
1763 instruction_stack
1764 .0
1765 .split_last()
1766 .map_or(ScopeStack::top(), |(last, prefix)| ScopeStack {
1767 caller: LogicalStack(prefix.to_vec()),
1768 scope: last.lexical_scope().clone(),
1769 })
1770}
1771
1772#[derive(Clone, Default, PartialEq)]
1773/// A "logical" stack trace. This is a processed version of a raw stack trace
1774/// captured from the evaluator.
1775/// This stack trace doesn't only contain calls to callables, but also entries into scopes
1776/// that are deemed to be interesting such as loops and lexical blocks.
1777pub struct LogicalStack(pub Vec<LogicalStackEntry>);
1778
1779impl LogicalStack {
1780 #[must_use]
1781 pub fn from_evaluator_trace(trace: &[Frame]) -> Self {
1782 let call_stack = trace
1783 .iter()
1784 .flat_map(|frame| {
1785 let mut logical_stack = vec![LogicalStackEntry::new_call_site(
1786 PackageOffset {
1787 package_id: frame.id.package,
1788 offset: frame.span.lo,
1789 },
1790 Scope::Callable(CallableId::Id(frame.id, frame.functor)),
1791 )];
1792
1793 // Insert any loop frames
1794 if !frame.loop_iterations.is_empty() {
1795 for loop_scope in &frame.loop_iterations {
1796 let last = logical_stack.last_mut().expect("there should be a frame");
1797 let last_call_site = last.location;
1798 last.location = LogicalStackEntryLocation::Loop(LoopId::Id(
1799 frame.id.package,
1800 loop_scope.loop_expr,
1801 ));
1802 logical_stack.push(LogicalStackEntry::new(
1803 last_call_site,
1804 Scope::Loop(LoopId::Id(frame.id.package, loop_scope.loop_expr)),
1805 ));
1806 let last = logical_stack.last_mut().expect("there should be a frame");
1807 let last_location = last.location;
1808 last.location = LogicalStackEntryLocation::LoopIteration(
1809 LoopId::Id(frame.id.package, loop_scope.loop_expr),
1810 loop_scope.iteration_count,
1811 );
1812 logical_stack.push(LogicalStackEntry::new(
1813 last_location,
1814 Scope::LoopIteration(
1815 LoopId::Id(frame.id.package, loop_scope.loop_expr),
1816 loop_scope.iteration_count,
1817 ),
1818 ));
1819 }
1820 }
1821
1822 logical_stack
1823 })
1824 .collect::<Vec<_>>();
1825
1826 LogicalStack(call_stack)
1827 }
1828}
1829
1830/// An entry in a logical stack trace.
1831#[derive(Clone, PartialEq)]
1832pub struct LogicalStackEntry {
1833 /// Location of the "call" into the next entry.
1834 /// The location type should correspond to the next entry's scope, e.g. a `LogicalStackEntryLocation::Call`
1835 /// would be followed by a `Scope::Callable` in the stack trace.
1836 /// Used as a discriminator when grouping. Within a scope, each distinct call/loop should have a unique location.
1837 pub(crate) location: LogicalStackEntryLocation,
1838 /// The lexical scope of this stack trace entry.
1839 /// Instructions that share a scope will be grouped together in the circuit diagram.
1840 pub(crate) scope: Scope,
1841}
1842
1843impl LogicalStackEntry {
1844 #[must_use]
1845 pub fn lexical_scope(&self) -> &Scope {
1846 &self.scope
1847 }
1848
1849 #[must_use]
1850 pub fn location(&self) -> &LogicalStackEntryLocation {
1851 &self.location
1852 }
1853
1854 #[must_use]
1855 pub fn package_id(&self) -> Option<PackageId> {
1856 match self.scope {
1857 Scope::Callable(
1858 CallableId::Source(PackageOffset { package_id, .. }, _)
1859 | CallableId::Id(
1860 StoreItemId {
1861 package: package_id,
1862 ..
1863 },
1864 _,
1865 ),
1866 )
1867 | Scope::LoopIteration(
1868 LoopId::Id(package_id, _) | LoopId::Source(PackageOffset { package_id, .. }),
1869 _,
1870 )
1871 | Scope::Loop(
1872 LoopId::Id(package_id, _) | LoopId::Source(PackageOffset { package_id, .. }),
1873 ) => Some(package_id),
1874 Scope::Top | Scope::ClassicallyControlled { .. } => None,
1875 }
1876 }
1877
1878 pub(crate) fn new_call_site(package_offset: PackageOffset, scope: Scope) -> Self {
1879 Self {
1880 location: LogicalStackEntryLocation::Source(package_offset),
1881 scope,
1882 }
1883 }
1884
1885 pub(crate) fn new(location: LogicalStackEntryLocation, scope: Scope) -> Self {
1886 Self { location, scope }
1887 }
1888}
1889
1890#[derive(Clone, Debug, Copy)]
1891/// In a stack trace, represents the location of each entry.
1892pub enum LogicalStackEntryLocation {
1893 /// A branch. The `Option<PackageOffset>` is the location of the branch instruction, if known.
1894 /// The `bool` indicates which branch (true or false).
1895 Branch(Option<PackageOffset>, bool),
1896 /// Source code location at the given package offset.
1897 Source(PackageOffset),
1898 /// A loop. The `ExprId` identifies the loop expression.
1899 Loop(LoopId),
1900 /// An iteration of a loop. The `usize` is the iteration count
1901 /// and is used to discriminate different iterations. The `ExprId` identifies
1902 /// the loop expression.
1903 LoopIteration(LoopId, usize),
1904 /// Location is unknown. Always unique.
1905 Unknown,
1906}
1907
1908impl PartialEq for LogicalStackEntryLocation {
1909 fn eq(&self, other: &Self) -> bool {
1910 match (self, other) {
1911 (Self::Branch(loc1, val1), Self::Branch(loc2, val2)) => loc1 == loc2 && val1 == val2,
1912 (Self::Source(loc1), Self::Source(loc2)) => loc1 == loc2,
1913 (Self::Loop(loop_id1), Self::Loop(loop_id2)) => loop_id1 == loop_id2,
1914 (Self::LoopIteration(loop_id1, iter1), Self::LoopIteration(loop_id2, iter2)) => {
1915 loop_id1 == loop_id2 && iter1 == iter2
1916 }
1917 // Unknowns are always unique
1918 _ => false,
1919 }
1920 }
1921}
1922
1923#[derive(Clone, Debug, PartialEq, Default)]
1924pub enum Scope {
1925 #[default]
1926 /// The top-level scope.
1927 Top,
1928 /// A callable.
1929 Callable(CallableId),
1930 /// A loop. The `ExprId` identifies the loop expression.
1931 Loop(LoopId),
1932 /// A loop body. The `ExprId` identifies the loop expression.
1933 /// The `usize` is the iteration count.
1934 LoopIteration(LoopId, usize),
1935 /// A conditional branch. The `String` is a label for the condition expression.
1936 ClassicallyControlled {
1937 label: String,
1938 control_result_ids: Vec<usize>,
1939 },
1940}
1941
1942#[derive(Clone, Debug, PartialEq)]
1943pub enum CallableId {
1944 Id(StoreItemId, FunctorApp),
1945 Source(PackageOffset, Rc<str>),
1946}
1947
1948#[derive(Clone, Copy, Debug, PartialEq)]
1949pub enum LoopId {
1950 Id(PackageId, ExprId),
1951 Source(PackageOffset),
1952}
1953
1954#[derive(Clone, Debug, Copy, PartialEq, Eq, Hash)]
1955pub struct PackageOffset {
1956 pub package_id: PackageId,
1957 pub offset: u32,
1958}
1959
1960#[cfg(test)]
1961pub(crate) struct LogicalStackWithSourceLookup<'a, S> {
1962 pub(crate) trace: LogicalStack,
1963 pub(crate) source_lookup: &'a S,
1964}
1965
1966#[cfg(test)]
1967impl<S: SourceLookup> Display for LogicalStackWithSourceLookup<'_, S> {
1968 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1969 if self.trace.0.is_empty() {
1970 write!(f, "[no stack]")?;
1971 return Ok(());
1972 }
1973 let mut loop_id_cache = Default::default();
1974 for (i, frame) in self.trace.0.iter().enumerate() {
1975 if i > 0 {
1976 write!(f, " -> ")?;
1977 }
1978
1979 let scope = self
1980 .source_lookup
1981 .resolve_scope(&frame.scope, &mut loop_id_cache);
1982 write!(
1983 f,
1984 "{}{}",
1985 scope.name,
1986 if scope.is_adjoint { "†" } else { "" },
1987 )?;
1988 let package_offset = self
1989 .source_lookup
1990 .resolve_logical_stack_entry_location(frame.location, &mut loop_id_cache);
1991 if let Some(package_offset) = package_offset {
1992 let l = self.source_lookup.resolve_package_offset(&package_offset);
1993 write!(f, "@{}:{}:{}", l.file, l.line, l.column)?;
1994 }
1995 if let LogicalStackEntryLocation::LoopIteration(_, iteration) = frame.location {
1996 write!(f, "[{iteration}]")?;
1997 }
1998 if let LogicalStackEntryLocation::Branch(_, val) = frame.location {
1999 write!(f, "[{val}]")?;
2000 }
2001 if let LogicalStackEntryLocation::Unknown = frame.location {
2002 write!(f, "[unknown]")?;
2003 }
2004 }
2005 Ok(())
2006 }
2007}
2008