GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
iadavis/pipeline-issue-debugging

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

1668lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4#[cfg(test)]
5mod tests;
6
7use crate::{
8 ComponentColumn,
9 circuit::{
10 Circuit, Ket, Measurement, Metadata, Operation, Qubit, Register, SourceLocation, Unitary,
11 operation_list_to_grid,
12 },
13 operations::QubitParam,
14};
15use qsc_data_structures::{
16 functors::FunctorApp,
17 index_map::IndexMap,
18 line_column::{Encoding, Position},
19};
20use qsc_eval::{
21 backend::Tracer,
22 debug::Frame,
23 val::{self, Value},
24};
25use qsc_fir::fir::{self, ExprId, ExprKind, PackageId, PackageLookup, StoreItemId};
26use qsc_frontend::compile::{self};
27use qsc_hir::hir;
28use qsc_lowerer::{map_fir_local_item_to_hir, map_fir_package_to_hir};
29use rustc_hash::FxHashSet;
30use std::{
31 fmt::{Debug, Display, Write},
32 hash::Hash,
33 mem::{replace, take},
34 rc::Rc,
35};
36
37/// Circuit builder that implements the `Tracer` trait to build a circuit
38/// while tracing execution.
39pub struct CircuitTracer {
40 config: TracerConfig,
41 wire_map_builder: WireMapBuilder,
42 circuit_builder: OperationListBuilder,
43 next_result_id: usize,
44 user_package_ids: Vec<PackageId>,
45 superposition_qubits: FxHashSet<QubitWire>,
46 classical_one_qubits: FxHashSet<QubitWire>,
47}
48
49impl Tracer for CircuitTracer {
50 fn qubit_allocate(&mut self, stack: &[Frame], q: usize) {
51 let declared_at = self.user_code_call_location(stack);
52 self.wire_map_builder.map_qubit(q, declared_at);
53 }
54
55 fn qubit_release(&mut self, _stack: &[Frame], q: usize) {
56 self.wire_map_builder.unmap_qubit(q);
57 }
58
59 fn qubit_swap_id(&mut self, _stack: &[Frame], q0: usize, q1: usize) {
60 self.wire_map_builder.swap(q0, q1);
61 }
62
63 fn gate(
64 &mut self,
65 stack: &[Frame],
66 name: &str,
67 is_adjoint: bool,
68 targets: &[usize],
69 controls: &[usize],
70 theta: Option<f64>,
71 ) {
72 let called_at = LogicalStack::from_evaluator_trace(stack);
73 let display_args: Vec<String> = theta.map(|p| format!("{p:.4}")).into_iter().collect();
74 let controls = if self.config.prune_classical_qubits {
75 // Any controls that are known to be classically one can be removed, so this
76 // will return the updated controls list.
77 &self.update_qubit_status(name, targets, controls)
78 } else {
79 controls
80 };
81 self.circuit_builder.gate(
82 self.wire_map_builder.current(),
83 name,
84 is_adjoint,
85 &GateInputs { targets, controls },
86 display_args,
87 called_at,
88 );
89 }
90
91 fn measure(&mut self, stack: &[Frame], name: &str, q: usize, val: &val::Result) {
92 let called_at = LogicalStack::from_evaluator_trace(stack);
93 let r = match val {
94 val::Result::Id(id) => *id,
95 val::Result::Loss | val::Result::Val(_) => {
96 let id = self.next_result_id;
97 self.next_result_id += 1;
98 id
99 }
100 };
101 self.wire_map_builder.link_result_to_qubit(q, r);
102 if name == "MResetZ" {
103 self.classical_one_qubits
104 .remove(&self.wire_map_builder.wire_map.qubit_wire(q));
105 self.circuit_builder
106 .mresetz(self.wire_map_builder.current(), q, r, called_at);
107 } else {
108 self.circuit_builder
109 .m(self.wire_map_builder.current(), q, r, called_at);
110 }
111 }
112
113 fn reset(&mut self, stack: &[Frame], q: usize) {
114 let called_at = LogicalStack::from_evaluator_trace(stack);
115 self.classical_one_qubits
116 .remove(&self.wire_map_builder.wire_map.qubit_wire(q));
117 self.circuit_builder
118 .reset(self.wire_map_builder.current(), q, called_at);
119 }
120
121 fn custom_intrinsic(&mut self, stack: &[Frame], name: &str, arg: Value) {
122 // The qubit arguments are treated as the targets for custom gates.
123 // Any remaining arguments will be kept in the display_args field
124 // to be shown as part of the gate label when the circuit is rendered.
125 let (qubit_args, classical_args) = self.split_qubit_args(arg);
126
127 if qubit_args.is_empty() {
128 // don't add a gate with no qubit targets
129 return;
130 }
131
132 self.circuit_builder.gate(
133 self.wire_map_builder.current(),
134 name,
135 false, // is_adjoint
136 &GateInputs {
137 targets: &qubit_args,
138 controls: &[],
139 },
140 if classical_args.is_empty() {
141 vec![]
142 } else {
143 vec![classical_args]
144 },
145 LogicalStack::from_evaluator_trace(stack),
146 );
147 }
148
149 fn is_stack_tracing_enabled(&self) -> bool {
150 self.config.source_locations || self.config.group_by_scope
151 }
152}
153
154impl CircuitTracer {
155 #[must_use]
156 pub fn new(config: TracerConfig, user_package_ids: &[PackageId]) -> Self {
157 CircuitTracer {
158 config,
159 wire_map_builder: WireMapBuilder::new(vec![]),
160 circuit_builder: OperationListBuilder::new(
161 config.max_operations,
162 user_package_ids.to_vec(),
163 config.group_by_scope,
164 config.source_locations,
165 ),
166 next_result_id: 0,
167 user_package_ids: user_package_ids.to_vec(),
168 superposition_qubits: FxHashSet::default(),
169 classical_one_qubits: FxHashSet::default(),
170 }
171 }
172
173 #[must_use]
174 pub fn with_qubit_input_params(
175 config: TracerConfig,
176 user_package_ids: &[PackageId],
177 operation_qubit_params: Option<(PackageId, Vec<QubitParam>)>,
178 ) -> Self {
179 // Pre-initialize the qubit declaration locations for the operation's
180 // input parameters. These will get allocated during execution, but
181 // the declaration locations inferred from the callstacks will be meaningless
182 // since those will be in the generated entry expression.
183 let params = operation_qubit_params
184 .map(|(package_id, info)| {
185 let mut decls = vec![];
186 for param in &info {
187 for _ in 0..param.num_qubits() {
188 decls.push(PackageOffset {
189 package_id,
190 offset: param.source_offset,
191 });
192 }
193 }
194 decls
195 })
196 .unwrap_or_default();
197
198 CircuitTracer {
199 config,
200 wire_map_builder: WireMapBuilder::new(params),
201 circuit_builder: OperationListBuilder::new(
202 config.max_operations,
203 user_package_ids.to_vec(),
204 config.group_by_scope,
205 config.source_locations,
206 ),
207 next_result_id: 0,
208 user_package_ids: user_package_ids.to_vec(),
209 superposition_qubits: FxHashSet::default(),
210 classical_one_qubits: FxHashSet::default(),
211 }
212 }
213
214 #[must_use]
215 pub fn snapshot(&self, source_lookup: &impl SourceLookup) -> Circuit {
216 self.finish_circuit(self.circuit_builder.operations(), source_lookup)
217 }
218
219 #[must_use]
220 pub fn finish(mut self, source_lookup: &impl SourceLookup) -> Circuit {
221 let ops = replace(
222 &mut self.circuit_builder,
223 OperationListBuilder::new(
224 self.config.max_operations,
225 self.user_package_ids.clone(),
226 self.config.group_by_scope,
227 self.config.source_locations,
228 ),
229 )
230 .into_operations();
231
232 self.finish_circuit(&ops, source_lookup)
233 }
234
235 fn finish_circuit(
236 &self,
237 operations: &[OperationOrGroup],
238 source_lookup: &impl SourceLookup,
239 ) -> Circuit {
240 let mut operations = operations.to_vec();
241 let mut qubits = self.wire_map_builder.wire_map.to_qubits(source_lookup);
242 // We need to pass the original number of qubits, before any trimming, to finish the circuit below.
243 let num_qubits = qubits.len();
244
245 if self.config.prune_classical_qubits {
246 // Remove qubits that are always classical.
247 qubits.retain(|q| self.superposition_qubits.contains(&q.id.into()));
248
249 // Remove operations that don't use any non-classical qubits.
250 operations.retain_mut(|op| self.should_keep_operation_mut(op));
251 }
252
253 if self.config.group_by_scope {
254 // Collapse unnecessary scopes
255 collapse_unnecessary_scopes(&mut operations, source_lookup);
256 }
257
258 let operations = operations
259 .into_iter()
260 .map(|o| o.into_operation(source_lookup))
261 .collect();
262
263 let component_grid = operation_list_to_grid(operations, num_qubits);
264 Circuit {
265 qubits,
266 component_grid,
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::Call(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/// Removes any scopes that are unnecessary and replaces them with their children operations.
501/// An unnecessary loop scope is one that either has a single child iteration,
502/// or has multiple iterations that each operate on distinct sets of qubits (i.e. a "vertical" loop).
503/// An unnecessary lambda scope is one where the lambda has a single child operation.
504fn collapse_unnecessary_scopes(
505 operations: &mut Vec<OperationOrGroup>,
506 source_lookup: &impl SourceLookup,
507) {
508 let mut ops = vec![];
509 for mut op in operations.drain(..) {
510 match &mut op.kind {
511 OperationOrGroupKind::Single => {}
512 OperationOrGroupKind::Group { children, .. } => {
513 collapse_unnecessary_scopes(children, source_lookup);
514 }
515 }
516
517 if let Some(children) = collapse_if_unnecessary(&mut op, source_lookup) {
518 ops.extend(children);
519 } else {
520 ops.push(op);
521 }
522 }
523 *operations = ops;
524}
525
526/// If the given operation or group is an outer scope that can be collapsed,
527/// returns its children operations or groups.
528fn collapse_if_unnecessary(
529 op: &mut OperationOrGroup,
530 source_lookup: &impl SourceLookup,
531) -> Option<Vec<OperationOrGroup>> {
532 if let OperationOrGroupKind::Group {
533 scope_stack,
534 children,
535 } = &mut op.kind
536 {
537 if let Scope::Loop(..) = scope_stack.current_lexical_scope() {
538 if children.len() == 1 {
539 // remove the loop scope
540 let mut only_child = children.remove(0);
541 let OperationOrGroupKind::Group { children, .. } = &mut only_child.kind else {
542 panic!("only child of an outer loop scope should be a group");
543 };
544 return Some(take(children));
545 }
546
547 // now, if each c applies to a distinct set of qubits, this loop is entirely vertical and can be collapsed as well
548 let mut distinct_sets_of_qubits = FxHashSet::default();
549 for child_op in children.iter() {
550 let qs = child_op.all_qubits();
551 if !distinct_sets_of_qubits.insert(qs) {
552 // There's overlap, so we won't collapse
553 return None;
554 }
555 }
556 let mut all_children = vec![];
557 for mut child_op in children.drain(..) {
558 let OperationOrGroupKind::Group { children, .. } = &mut child_op.kind else {
559 panic!("only child of an outer loop scope should be a group");
560 };
561 all_children.extend(take(children));
562 }
563 return Some(all_children);
564 } else if let Scope::Callable(..) = scope_stack.current_lexical_scope()
565 && children.len() == 1
566 && source_lookup
567 .resolve_scope(scope_stack.current_lexical_scope())
568 .name
569 .as_ref()
570 == "<lambda>"
571 {
572 // remove the lambda scope
573 return Some(take(children));
574 }
575 }
576 None
577}
578
579/// Resolves structs that use compilation-specific IDs (`PackageId`s, `ExprId`s etc.)
580/// to user legible names and source file locations.
581pub trait SourceLookup {
582 fn resolve_package_offset(&self, package_offset: &PackageOffset) -> SourceLocation;
583 fn resolve_scope(&self, scope: Scope) -> LexicalScope;
584 fn resolve_logical_stack_entry_location(
585 &self,
586 location: LogicalStackEntryLocation,
587 ) -> PackageOffset;
588}
589
590impl SourceLookup for (&compile::PackageStore, &fir::PackageStore) {
591 fn resolve_package_offset(&self, package_offset: &PackageOffset) -> SourceLocation {
592 let package = self
593 .0
594 .get(map_fir_package_to_hir(package_offset.package_id))
595 .expect("package id must exist in store");
596
597 let source = package
598 .sources
599 .find_by_offset(package_offset.offset)
600 .expect("source should exist for offset");
601
602 let pos = Position::from_utf8_byte_offset(
603 Encoding::Utf8,
604 &source.contents,
605 package_offset.offset - source.offset,
606 );
607
608 SourceLocation {
609 file: source.name.to_string(),
610 line: pos.line,
611 column: pos.column,
612 }
613 }
614
615 fn resolve_scope(&self, scope_id: Scope) -> LexicalScope {
616 match scope_id {
617 Scope::Callable(store_item_id, functor_app) => {
618 let package = self
619 .0
620 .get(map_fir_package_to_hir(store_item_id.package))
621 .expect("package id must exist in store");
622
623 let item = package
624 .package
625 .items
626 .get(map_fir_local_item_to_hir(store_item_id.item))
627 .expect("item id must exist in package");
628
629 let (scope_offset, scope_name) = match &item.kind {
630 hir::ItemKind::Callable(callable_decl) => {
631 let spec_decl = if functor_app.adjoint {
632 callable_decl.adj.as_ref().unwrap_or(&callable_decl.body)
633 } else {
634 &callable_decl.body
635 };
636
637 (spec_decl.span.lo, callable_decl.name.name.clone())
638 }
639 _ => panic!("only callables should be in the stack"),
640 };
641
642 LexicalScope {
643 location: Some(PackageOffset {
644 package_id: store_item_id.package,
645 offset: scope_offset,
646 }),
647 name: scope_name,
648 is_adjoint: functor_app.adjoint,
649 }
650 }
651 Scope::Loop(package_id, expr_id) => {
652 let package_store = self.1;
653 let package = package_store.get(package_id);
654 let loop_expr = package.get_expr(expr_id);
655 let ExprKind::While(cond_expr_id, _) = &loop_expr.kind else {
656 panic!("only while loops should be in loop containers");
657 };
658 let cond_expr = package.get_expr(*cond_expr_id);
659 let expr_contents = self
660 .0
661 .get(map_fir_package_to_hir(package_id))
662 .and_then(|p| p.sources.find_by_offset(cond_expr.span.lo))
663 .map(|s| {
664 s.contents[(cond_expr.span.lo - s.offset) as usize
665 ..(cond_expr.span.hi - s.offset) as usize]
666 .to_string()
667 });
668
669 LexicalScope {
670 name: format!("loop: {}", expr_contents.unwrap_or_default()).into(),
671 location: Some(PackageOffset {
672 package_id,
673 offset: loop_expr.span.lo,
674 }),
675 is_adjoint: false,
676 }
677 }
678 Scope::LoopIteration(package_id, expr_id, i) => {
679 let package_store = self.1;
680 let package = package_store.get(package_id);
681 let loop_expr = package.get_expr(expr_id);
682 let ExprKind::While(_cond, body) = &loop_expr.kind else {
683 panic!("only while loops should be used for loop body locations");
684 };
685 let block = package.get_block(*body);
686
687 LexicalScope {
688 name: format!("({i})").into(),
689 location: Some(PackageOffset {
690 package_id,
691 offset: block.span.lo,
692 }),
693 is_adjoint: false,
694 }
695 }
696 Scope::Top => LexicalScope {
697 name: "top".into(),
698 location: None,
699 is_adjoint: false,
700 },
701 }
702 }
703
704 fn resolve_logical_stack_entry_location(
705 &self,
706 location: LogicalStackEntryLocation,
707 ) -> PackageOffset {
708 match location {
709 LogicalStackEntryLocation::Call(package_offset) => package_offset,
710 LogicalStackEntryLocation::Loop(package_id, loop_expr_id) => {
711 let fir_package_store = self.1;
712 let package = fir_package_store.get(package_id);
713 let expr = package.get_expr(loop_expr_id);
714
715 PackageOffset {
716 package_id,
717 offset: expr.span.lo,
718 }
719 }
720 LogicalStackEntryLocation::LoopIteration(package_id, expr, _i) => {
721 let fir_package_store = self.1;
722 let package = fir_package_store.get(package_id);
723 let expr = package.get_expr(expr);
724 let ExprKind::While(_cond, body) = &expr.kind else {
725 panic!("only while loops should be used for loop body locations");
726 };
727
728 let block = package.get_block(*body);
729
730 PackageOffset {
731 package_id,
732 offset: block.span.lo,
733 }
734 }
735 }
736 }
737}
738
739#[allow(clippy::struct_excessive_bools)]
740#[derive(Clone, Debug, Copy)]
741pub struct TracerConfig {
742 /// Maximum number of operations the builder will add to the circuit
743 pub max_operations: usize,
744 /// Capture the source code locations of operations and qubit declarations
745 /// in the circuit diagram
746 pub source_locations: bool,
747 /// Group operations according to call graph in the circuit diagram
748 pub group_by_scope: bool,
749 /// Prune purely classical or unused qubits
750 pub prune_classical_qubits: bool,
751}
752
753impl TracerConfig {
754 /// Set to the current UI limit + 1 so that it still triggers
755 /// the "this circuit has too many gates" warning in the UI.
756 /// (see npm\qsharp\ux\circuit.tsx)
757 ///
758 /// A more refined way to do this might be to communicate the
759 /// "limit exceeded" state up to the UI somehow.
760 pub const DEFAULT_MAX_OPERATIONS: usize = 10001;
761}
762
763/// Maps qubit IDs to their corresponding wire IDs and tracks measurement results
764/// along with their source locations.
765#[derive(Default)]
766struct WireMap {
767 /// Maps qubit IDs to their assigned wire IDs.
768 qubits: IndexMap<usize, QubitWire>,
769 /// Maps wire IDs to their declaration locations and measurement result IDs.
770 qubit_wires: IndexMap<QubitWire, (Vec<PackageOffset>, Vec<usize>)>,
771}
772
773impl WireMap {
774 fn qubit_wire(&self, qubit_id: usize) -> QubitWire {
775 self.qubits
776 .get(qubit_id)
777 .expect("qubit should already be mapped")
778 .to_owned()
779 }
780
781 fn result_wire(&self, result_id: usize) -> ResultWire {
782 self.qubit_wires
783 .iter()
784 .find_map(|(QubitWire(qubit_wire), (_, results))| {
785 let r_idx = results.iter().position(|&r| r == result_id);
786 r_idx.map(|r_idx| ResultWire(qubit_wire, r_idx))
787 })
788 .expect("result should already be mapped")
789 }
790
791 fn to_qubits(&self, source_lookup: &impl SourceLookup) -> Vec<Qubit> {
792 let mut qubits = vec![];
793 for (QubitWire(wire_id), (declarations, results)) in self.qubit_wires.iter() {
794 qubits.push(Qubit {
795 id: wire_id,
796 num_results: results.len(),
797 declarations: declarations
798 .iter()
799 .map(|offset| source_lookup.resolve_package_offset(offset))
800 .collect(),
801 });
802 }
803
804 qubits
805 }
806}
807
808#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
809struct ResultWire(usize, usize);
810
811#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
812struct QubitWire(usize);
813
814impl From<usize> for QubitWire {
815 fn from(value: usize) -> Self {
816 QubitWire(value)
817 }
818}
819
820impl From<QubitWire> for usize {
821 fn from(value: QubitWire) -> Self {
822 value.0
823 }
824}
825
826/// Manages the mapping between qubits and wires during circuit construction.
827/// Tracks qubit allocations, measurement results, and their source locations.
828/// Also acts as a result ID allocator when the result IDs aren't passed in
829/// by the tracer.
830///
831/// This implementation is similar to the partial evaluation resource manager,
832/// which is used in RIR/QIR generation, in its Qubit ID and Result ID management.
833/// (see `source/compiler/qsc_partial_eval/src/management.rs`)
834struct WireMapBuilder {
835 next_qubit_wire_id: QubitWire,
836 wire_map: WireMap,
837}
838
839impl WireMapBuilder {
840 fn new(qubit_input_decls: Vec<PackageOffset>) -> Self {
841 let mut new = Self {
842 next_qubit_wire_id: QubitWire(0),
843 wire_map: WireMap::default(),
844 };
845
846 let mut i = new.next_qubit_wire_id;
847 for decl in qubit_input_decls {
848 new.wire_map.qubit_wires.insert(i, (vec![decl], vec![]));
849 i.0 += 1;
850 }
851
852 new
853 }
854
855 fn current(&self) -> &WireMap {
856 &self.wire_map
857 }
858
859 fn map_qubit(&mut self, qubit: usize, declared_at: Option<PackageOffset>) {
860 let mapped = self.next_qubit_wire_id;
861 self.next_qubit_wire_id.0 += 1;
862 self.wire_map.qubits.insert(qubit, mapped);
863
864 if let Some(q) = self.wire_map.qubit_wires.get_mut(mapped) {
865 if let Some(location) = declared_at {
866 q.0.push(location);
867 }
868 } else {
869 let l = declared_at.map(|l| vec![l]).unwrap_or_default();
870 self.wire_map.qubit_wires.insert(mapped, (l, vec![]));
871 }
872 }
873
874 fn unmap_qubit(&mut self, q: usize) {
875 // Simple behavior assuming qubits are always released in reverse order of allocation
876 self.next_qubit_wire_id.0 -= 1;
877 self.wire_map.qubits.remove(q);
878 }
879
880 fn link_result_to_qubit(&mut self, q: usize, r: usize) {
881 let mapped_q = self.wire_map.qubit_wire(q);
882 let Some((_, measurements)) = self.wire_map.qubit_wires.get_mut(mapped_q) else {
883 panic!("qubit should already be mapped");
884 };
885 if !measurements.contains(&r) {
886 measurements.push(r);
887 }
888 }
889
890 fn swap(&mut self, q0: usize, q1: usize) {
891 let q0_mapped = self.wire_map.qubit_wire(q0);
892 let q1_mapped = self.wire_map.qubit_wire(q1);
893 self.wire_map.qubits.insert(q0, q1_mapped);
894 self.wire_map.qubits.insert(q1, q0_mapped);
895 }
896}
897
898#[derive(Clone)]
899struct OperationOrGroup {
900 kind: OperationOrGroupKind,
901 location: Option<LogicalStackEntryLocation>,
902 op: Operation,
903}
904
905#[derive(Clone)]
906enum OperationOrGroupKind {
907 Single,
908 Group {
909 scope_stack: ScopeStack,
910 children: Vec<OperationOrGroup>,
911 },
912}
913
914impl OperationOrGroup {
915 fn new_single(op: Operation) -> Self {
916 Self {
917 kind: OperationOrGroupKind::Single,
918 op,
919 location: None,
920 }
921 }
922
923 fn new_unitary(
924 name: &str,
925 is_adjoint: bool,
926 targets: &[QubitWire],
927 controls: &[QubitWire],
928 args: Vec<String>,
929 ) -> Self {
930 Self::new_single(Operation::Unitary(Unitary {
931 gate: name.to_string(),
932 args,
933 children: vec![],
934 targets: targets
935 .iter()
936 .map(|q| Register {
937 qubit: q.0,
938 result: None,
939 })
940 .collect(),
941 controls: controls
942 .iter()
943 .map(|q| Register {
944 qubit: q.0,
945 result: None,
946 })
947 .collect(),
948 is_adjoint,
949 metadata: Some(Metadata {
950 source: None,
951 scope_location: None,
952 }),
953 }))
954 }
955
956 fn new_measurement(label: &str, qubit: QubitWire, result: ResultWire) -> Self {
957 Self::new_single(Operation::Measurement(Measurement {
958 gate: label.to_string(),
959 args: vec![],
960 children: vec![],
961 qubits: vec![Register {
962 qubit: qubit.0,
963 result: None,
964 }],
965 results: vec![Register {
966 qubit: result.0,
967 result: Some(result.1),
968 }],
969 metadata: None,
970 }))
971 }
972
973 fn new_ket(qubit: QubitWire) -> Self {
974 Self::new_single(Operation::Ket(Ket {
975 gate: "0".to_string(),
976 args: vec![],
977 children: vec![],
978 targets: vec![Register {
979 qubit: qubit.0,
980 result: None,
981 }],
982 metadata: None,
983 }))
984 }
985
986 fn all_qubits(&self) -> Vec<QubitWire> {
987 let qubits: FxHashSet<QubitWire> = match &self.op {
988 Operation::Measurement(measurement) => measurement.qubits.clone(),
989 Operation::Unitary(unitary) => unitary
990 .targets
991 .iter()
992 .chain(unitary.controls.iter())
993 .filter(|r| r.result.is_none())
994 .cloned()
995 .collect(),
996 Operation::Ket(ket) => ket.targets.clone(),
997 }
998 .into_iter()
999 .map(|r| QubitWire(r.qubit))
1000 .collect();
1001 qubits.into_iter().collect()
1002 }
1003
1004 fn all_results(&self) -> Vec<ResultWire> {
1005 let results: FxHashSet<ResultWire> = match &self.op {
1006 Operation::Measurement(measurement) => measurement
1007 .results
1008 .iter()
1009 .filter_map(|r| r.result.map(|res| ResultWire(r.qubit, res)))
1010 .collect(),
1011 Operation::Unitary(unitary) => unitary
1012 .targets
1013 .iter()
1014 .chain(unitary.controls.iter())
1015 .filter_map(|r| r.result.map(|res| ResultWire(r.qubit, res)))
1016 .collect(),
1017 Operation::Ket(_) => vec![],
1018 }
1019 .into_iter()
1020 .collect();
1021 results.into_iter().collect()
1022 }
1023
1024 fn children_mut(&mut self) -> Option<&mut Vec<Self>>
1025 where
1026 Self: std::marker::Sized,
1027 {
1028 if let OperationOrGroupKind::Group { children, .. } = &mut self.kind {
1029 Some(children)
1030 } else {
1031 None
1032 }
1033 }
1034
1035 fn new_group(scope_stack: ScopeStack, children: Vec<Self>) -> Self {
1036 let all_qubits = children
1037 .iter()
1038 .flat_map(OperationOrGroup::all_qubits)
1039 .collect::<FxHashSet<QubitWire>>()
1040 .into_iter()
1041 .collect::<Vec<QubitWire>>();
1042
1043 let all_results = children
1044 .iter()
1045 .flat_map(OperationOrGroup::all_results)
1046 .collect::<FxHashSet<ResultWire>>()
1047 .into_iter()
1048 .collect::<Vec<ResultWire>>();
1049
1050 Self {
1051 kind: OperationOrGroupKind::Group {
1052 scope_stack,
1053 children,
1054 },
1055 op: Operation::Unitary(Unitary {
1056 gate: String::new(), // to be filled in later
1057 args: vec![],
1058 children: vec![],
1059 targets: all_qubits
1060 .iter()
1061 .map(|q| Register {
1062 qubit: q.0,
1063 result: None,
1064 })
1065 .chain(all_results.iter().map(|r| Register {
1066 qubit: r.0,
1067 result: Some(r.1),
1068 }))
1069 .collect(),
1070 controls: vec![],
1071 is_adjoint: false,
1072 metadata: Some(Metadata {
1073 source: None,
1074 scope_location: None,
1075 }),
1076 }),
1077 location: None,
1078 }
1079 }
1080
1081 fn extend_target_qubits(&mut self, target_qubits: &[QubitWire]) {
1082 match &mut self.op {
1083 Operation::Measurement(_) => {}
1084 Operation::Unitary(unitary) => {
1085 unitary
1086 .targets
1087 .extend(target_qubits.iter().map(|q| Register {
1088 qubit: q.0,
1089 result: None,
1090 }));
1091 unitary
1092 .targets
1093 .sort_unstable_by_key(|r| (r.qubit, r.result));
1094 unitary.targets.dedup();
1095 }
1096 Operation::Ket(ket) => {
1097 ket.targets.extend(target_qubits.iter().map(|q| Register {
1098 qubit: q.0,
1099 result: None,
1100 }));
1101 }
1102 }
1103 }
1104
1105 fn extend_target_results(&mut self, target_results: &[ResultWire]) {
1106 match &mut self.op {
1107 Operation::Measurement(measurement) => {
1108 measurement
1109 .results
1110 .extend(target_results.iter().map(|r| Register {
1111 qubit: r.0,
1112 result: Some(r.1),
1113 }));
1114 measurement
1115 .results
1116 .sort_unstable_by_key(|reg| (reg.qubit, reg.result));
1117 measurement.results.dedup();
1118 }
1119 Operation::Unitary(unitary) => {
1120 unitary
1121 .targets
1122 .extend(target_results.iter().map(|r| Register {
1123 qubit: r.0,
1124 result: Some(r.1),
1125 }));
1126 unitary
1127 .targets
1128 .sort_unstable_by_key(|r| (r.qubit, r.result));
1129 unitary.targets.dedup();
1130 }
1131 Operation::Ket(_) => {}
1132 }
1133 }
1134
1135 fn scope_stack_if_group(&self) -> Option<&ScopeStack> {
1136 if let OperationOrGroupKind::Group { scope_stack, .. } = &self.kind {
1137 Some(scope_stack)
1138 } else {
1139 None
1140 }
1141 }
1142
1143 fn into_operation(mut self, source_lookup: &impl SourceLookup) -> Operation {
1144 if let Some(location) = self.location {
1145 let package_offset = source_lookup.resolve_logical_stack_entry_location(location);
1146 let location = source_lookup.resolve_package_offset(&package_offset);
1147
1148 self.op.source_location_mut().replace(location);
1149 }
1150
1151 match self.kind {
1152 OperationOrGroupKind::Single => self.op,
1153 OperationOrGroupKind::Group {
1154 scope_stack,
1155 children,
1156 } => {
1157 let Operation::Unitary(u) = &mut self.op else {
1158 panic!("group operation should be a unitary")
1159 };
1160 let scope = scope_stack.resolve_scope(source_lookup);
1161 u.gate = scope.name.to_string();
1162 u.is_adjoint = scope.is_adjoint;
1163 let scope_location = scope
1164 .location
1165 .map(|loc| source_lookup.resolve_package_offset(&loc));
1166 if let Some(metadata) = &mut u.metadata {
1167 metadata.scope_location = scope_location;
1168 } else {
1169 u.metadata = Some(Metadata {
1170 source: None,
1171 scope_location,
1172 });
1173 }
1174 u.children = vec![ComponentColumn {
1175 components: children
1176 .into_iter()
1177 .map(|o| o.into_operation(source_lookup))
1178 .collect(),
1179 }];
1180 self.op
1181 }
1182 }
1183 }
1184}
1185
1186/// Builds a list of circuit operations with a maximum operation limit.
1187/// Stops adding operations once the limit is exceeded.
1188///
1189/// Methods take `WireMap` as a parameter to resolve qubit and result IDs
1190/// to their corresponding wire positions in the circuit diagram.
1191struct OperationListBuilder {
1192 max_ops: usize,
1193 max_ops_exceeded: bool,
1194 operations: Vec<OperationOrGroup>,
1195 source_locations: bool,
1196 user_package_ids: Vec<PackageId>,
1197 group_by_scope: bool,
1198}
1199
1200impl OperationListBuilder {
1201 fn new(
1202 max_operations: usize,
1203 user_package_ids: Vec<PackageId>,
1204 group_by_scope: bool,
1205 source_locations: bool,
1206 ) -> Self {
1207 Self {
1208 max_ops: max_operations,
1209 max_ops_exceeded: false,
1210 operations: vec![],
1211 source_locations,
1212 user_package_ids,
1213 group_by_scope,
1214 }
1215 }
1216
1217 fn push_op(&mut self, op: OperationOrGroup, unfiltered_call_stack: LogicalStack) {
1218 if self.max_ops_exceeded || self.operations.len() >= self.max_ops {
1219 // Stop adding gates and leave the circuit as is
1220 self.max_ops_exceeded = true;
1221 return;
1222 }
1223
1224 let op_call_stack = if self.group_by_scope || self.source_locations {
1225 retain_user_frames(&self.user_package_ids, unfiltered_call_stack)
1226 } else {
1227 LogicalStack::default()
1228 };
1229
1230 add_scoped_op(
1231 &mut self.operations,
1232 &ScopeStack::top(),
1233 op,
1234 &op_call_stack,
1235 self.group_by_scope,
1236 self.source_locations,
1237 );
1238 }
1239
1240 fn operations(&self) -> &Vec<OperationOrGroup> {
1241 &self.operations
1242 }
1243
1244 fn into_operations(self) -> Vec<OperationOrGroup> {
1245 self.operations
1246 }
1247
1248 fn gate(
1249 &mut self,
1250 wire_map: &WireMap,
1251 name: &str,
1252 is_adjoint: bool,
1253 inputs: &GateInputs,
1254 args: Vec<String>,
1255 call_stack: LogicalStack,
1256 ) {
1257 let targets = inputs
1258 .targets
1259 .iter()
1260 .map(|q| wire_map.qubit_wire(*q))
1261 .collect::<Vec<_>>();
1262 let controls = inputs
1263 .controls
1264 .iter()
1265 .map(|q| wire_map.qubit_wire(*q))
1266 .collect::<Vec<_>>();
1267 self.push_op(
1268 OperationOrGroup::new_unitary(name, is_adjoint, &targets, &controls, args),
1269 call_stack,
1270 );
1271 }
1272
1273 fn m(&mut self, wire_map: &WireMap, qubit: usize, result: usize, call_stack: LogicalStack) {
1274 let qubit = wire_map.qubit_wire(qubit);
1275 let result = wire_map.result_wire(result);
1276 self.push_op(
1277 OperationOrGroup::new_measurement("M", qubit, result),
1278 call_stack,
1279 );
1280 }
1281
1282 fn mresetz(
1283 &mut self,
1284 wire_map: &WireMap,
1285 qubit: usize,
1286 result: usize,
1287 call_stack: LogicalStack,
1288 ) {
1289 let qubit = wire_map.qubit_wire(qubit);
1290 let result = wire_map.result_wire(result);
1291 self.push_op(
1292 OperationOrGroup::new_measurement("MResetZ", qubit, result),
1293 call_stack.clone(),
1294 );
1295 self.push_op(OperationOrGroup::new_ket(qubit), call_stack);
1296 }
1297
1298 fn reset(&mut self, wire_map: &WireMap, qubit: usize, call_stack: LogicalStack) {
1299 let qubit = wire_map.qubit_wire(qubit);
1300 self.push_op(OperationOrGroup::new_ket(qubit), call_stack);
1301 }
1302}
1303
1304struct GateInputs<'a> {
1305 targets: &'a [usize],
1306 controls: &'a [usize],
1307}
1308
1309pub struct LexicalScope {
1310 /// The start offset of the scope, used for navigation.
1311 location: Option<PackageOffset>,
1312 /// A display name for the scope.
1313 name: Rc<str>,
1314 /// Whether the scope represents an adjoint operation,
1315 /// used for display purposes.
1316 is_adjoint: bool,
1317}
1318
1319fn add_scoped_op(
1320 current_container: &mut Vec<OperationOrGroup>,
1321 current_scope_stack: &ScopeStack,
1322 mut op: OperationOrGroup,
1323 op_call_stack: &LogicalStack,
1324 group_by_scope: bool,
1325 set_source_location: bool,
1326) {
1327 if set_source_location && let Some(called_at) = op_call_stack.0.last() {
1328 op.location = Some(*called_at.location());
1329 }
1330
1331 let default = LogicalStack::default();
1332 let op_call_stack = if group_by_scope {
1333 op_call_stack
1334 } else {
1335 &default
1336 };
1337
1338 let relative_stack = strip_scope_stack_prefix(
1339 op_call_stack,
1340 current_scope_stack,
1341 ).expect("op_call_stack_rel should be a suffix of op_call_stack_abs after removing current_scope_stack_abs");
1342
1343 if !relative_stack.0.is_empty() {
1344 if let Some(last_op) = current_container.last_mut() {
1345 // See if we can add to the last scope inside the current container
1346 if let Some(last_scope_stack) = last_op.scope_stack_if_group()
1347 && strip_scope_stack_prefix(op_call_stack, last_scope_stack).is_some()
1348 {
1349 // The last scope matched, add to it
1350 let last_scope_stack = last_scope_stack.clone();
1351
1352 last_op.extend_target_qubits(&op.all_qubits());
1353 last_op.extend_target_results(&op.all_results());
1354 let last_op_children = last_op.children_mut().expect("operation should be a group");
1355
1356 // Recursively add to the children
1357 add_scoped_op(
1358 last_op_children,
1359 &last_scope_stack,
1360 op,
1361 op_call_stack,
1362 group_by_scope,
1363 set_source_location,
1364 );
1365
1366 return;
1367 }
1368 }
1369
1370 let op_scope_stack = scope_stack(&op_call_stack.0);
1371 if *current_scope_stack != op_scope_stack {
1372 // Need to create a new scope group
1373 let scope_group = OperationOrGroup::new_group(op_scope_stack, vec![op]);
1374
1375 let parent = LogicalStack(
1376 op_call_stack
1377 .0
1378 .split_last()
1379 .expect("should have more than one etc")
1380 .1
1381 .to_vec(),
1382 );
1383
1384 // Recursively add the new scope group to the current container
1385 add_scoped_op(
1386 current_container,
1387 current_scope_stack,
1388 scope_group,
1389 &parent,
1390 group_by_scope,
1391 set_source_location,
1392 );
1393
1394 return;
1395 }
1396 }
1397
1398 current_container.push(op);
1399}
1400
1401fn retain_user_frames(
1402 user_package_ids: &[PackageId],
1403 mut location_stack: LogicalStack,
1404) -> LogicalStack {
1405 location_stack.0.retain(|location| {
1406 let package_id = location.package_id();
1407 user_package_ids.is_empty() || user_package_ids.contains(&package_id)
1408 });
1409
1410 LogicalStack(location_stack.0)
1411}
1412
1413/// Represents a scope in the call stack, tracking the caller chain and current scope identifier.
1414#[derive(Clone, PartialEq)]
1415struct ScopeStack {
1416 caller: LogicalStack,
1417 scope: Scope,
1418}
1419
1420impl ScopeStack {
1421 fn caller(&self) -> &[LogicalStackEntry] {
1422 &self.caller.0
1423 }
1424
1425 fn current_lexical_scope(&self) -> Scope {
1426 assert!(!self.is_top(), "top scope has no lexical scope");
1427 self.scope
1428 }
1429
1430 fn is_top(&self) -> bool {
1431 self.caller.0.is_empty() && self.scope == Scope::default()
1432 }
1433
1434 fn top() -> Self {
1435 ScopeStack {
1436 caller: LogicalStack::default(),
1437 scope: Scope::default(),
1438 }
1439 }
1440
1441 fn resolve_scope(&self, source_lookup: &impl SourceLookup) -> LexicalScope {
1442 source_lookup.resolve_scope(self.scope)
1443 }
1444}
1445
1446/// Strips a scope stack prefix from a call stack.
1447///
1448/// The `full_call_stack` parameter represents a complete call stack, while
1449/// `prefix_scope_stack` represents a scope stack to match against.
1450///
1451/// If `prefix_scope_stack` is not a prefix of `full_call_stack`, this function returns `None`.
1452///
1453/// If it is a prefix, this function returns the remainder of `full_call_stack` after removing
1454/// the prefix, starting from the first location in the call stack that is in the scope of
1455/// `prefix_scope_stack.scope`.
1456fn strip_scope_stack_prefix(
1457 full_call_stack: &LogicalStack,
1458 prefix_scope_stack: &ScopeStack,
1459) -> Option<LogicalStack> {
1460 if prefix_scope_stack.is_top() {
1461 return Some(full_call_stack.clone());
1462 }
1463
1464 if full_call_stack.0.len() > prefix_scope_stack.caller().len()
1465 && let Some(rest) = full_call_stack.0.strip_prefix(prefix_scope_stack.caller())
1466 && rest[0].lexical_scope() == prefix_scope_stack.current_lexical_scope()
1467 {
1468 assert!(!rest.is_empty());
1469 return Some(LogicalStack(rest.to_vec()));
1470 }
1471 None
1472}
1473
1474fn scope_stack(instruction_stack: &[LogicalStackEntry]) -> ScopeStack {
1475 instruction_stack
1476 .split_last()
1477 .map_or(ScopeStack::top(), |(youngest, prefix)| ScopeStack {
1478 caller: LogicalStack(prefix.to_vec()),
1479 scope: youngest.lexical_scope(),
1480 })
1481}
1482
1483#[derive(Clone, Default, PartialEq)]
1484/// A "logical" stack trace. This is a processed version of a raw stack trace
1485/// captured from the evaluator.
1486/// This stack trace doesn't only contain calls to callables, but also entries into scopes
1487/// that are deemed to be interesting such as loops and lexical blocks.
1488pub struct LogicalStack(pub Vec<LogicalStackEntry>);
1489
1490impl LogicalStack {
1491 #[must_use]
1492 pub fn from_evaluator_trace(trace: &[Frame]) -> Self {
1493 let call_stack = trace
1494 .iter()
1495 .flat_map(|frame| {
1496 let mut logical_stack = vec![LogicalStackEntry::new_call_site(
1497 PackageOffset {
1498 package_id: frame.id.package,
1499 offset: frame.span.lo,
1500 },
1501 Scope::Callable(frame.id, frame.functor),
1502 )];
1503
1504 // Insert any loop frames
1505 if !frame.loop_iterations.is_empty() {
1506 for loop_scope in &frame.loop_iterations {
1507 let last = logical_stack.last_mut().expect("there should be a frame");
1508 let last_call_site = last.location;
1509 last.location =
1510 LogicalStackEntryLocation::Loop(frame.id.package, loop_scope.loop_expr);
1511 logical_stack.push(LogicalStackEntry::new(
1512 last_call_site,
1513 Scope::Loop(frame.id.package, loop_scope.loop_expr),
1514 ));
1515 let last = logical_stack.last_mut().expect("there should be a frame");
1516 let last_location = last.location;
1517 last.location = LogicalStackEntryLocation::LoopIteration(
1518 frame.id.package,
1519 loop_scope.loop_expr,
1520 loop_scope.iteration_count,
1521 );
1522 logical_stack.push(LogicalStackEntry::new(
1523 last_location,
1524 Scope::LoopIteration(
1525 frame.id.package,
1526 loop_scope.loop_expr,
1527 loop_scope.iteration_count,
1528 ),
1529 ));
1530 }
1531 }
1532
1533 logical_stack
1534 })
1535 .collect::<Vec<_>>();
1536
1537 LogicalStack(call_stack)
1538 }
1539}
1540
1541/// An entry in a logical stack trace.
1542#[derive(Clone, Debug, PartialEq)]
1543pub struct LogicalStackEntry {
1544 /// Location of the "call" into the next entry.
1545 /// The location type should correspond to the next entry's scope, e.g. a `LogicalStackEntryLocation::Call`
1546 /// would be followed by a `Scope::Callable` in the stack trace.
1547 /// Used as a discriminator when grouping. Within a scope, each distinct call/loop should have a unique location.
1548 location: LogicalStackEntryLocation,
1549 /// The lexical scope of this stack trace entry.
1550 /// Instructions that share a scope will be grouped together in the circuit diagram.
1551 scope: Scope,
1552}
1553
1554impl LogicalStackEntry {
1555 #[must_use]
1556 pub fn lexical_scope(&self) -> Scope {
1557 self.scope
1558 }
1559
1560 #[must_use]
1561 pub fn location(&self) -> &LogicalStackEntryLocation {
1562 &self.location
1563 }
1564
1565 #[must_use]
1566 pub fn package_id(&self) -> PackageId {
1567 match self.scope {
1568 Scope::Top => panic!("top scope has no package"),
1569 Scope::Callable(store_item_id, _) => store_item_id.package,
1570 Scope::LoopIteration(package_id, _, _) | Scope::Loop(package_id, _) => package_id,
1571 }
1572 }
1573
1574 fn new_call_site(package_offset: PackageOffset, scope: Scope) -> Self {
1575 Self {
1576 location: LogicalStackEntryLocation::Call(package_offset),
1577 scope,
1578 }
1579 }
1580
1581 fn new(location: LogicalStackEntryLocation, scope: Scope) -> Self {
1582 Self { location, scope }
1583 }
1584}
1585
1586#[derive(Clone, Debug, Copy, PartialEq)]
1587/// In a stack trace, represents the location of each entry.
1588pub enum LogicalStackEntryLocation {
1589 /// A call to a callable at the given package offset.
1590 Call(PackageOffset),
1591 /// An entry into a loop. The `ExprId` identifies the loop expression.
1592 Loop(PackageId, ExprId),
1593 /// An iteration of a loop. The `usize` is the iteration count
1594 /// and is used to discriminate different iterations. The `ExprId` identifies
1595 /// the loop expression.
1596 LoopIteration(PackageId, ExprId, usize),
1597}
1598
1599#[derive(Clone, Debug, PartialEq, Copy, Default)]
1600pub enum Scope {
1601 #[default]
1602 /// The top-level scope.
1603 Top,
1604 /// A callable.
1605 Callable(StoreItemId, FunctorApp),
1606 /// A loop. The `ExprId` identifies the loop expression.
1607 Loop(PackageId, ExprId),
1608 /// A loop body. The `ExprId` identifies the loop expression.
1609 /// The `usize` is the iteration count.
1610 LoopIteration(PackageId, ExprId, usize),
1611}
1612
1613impl Display for Scope {
1614 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1615 match self {
1616 Scope::Top => write!(f, "top"),
1617 Scope::Callable(i, _) => {
1618 write!(f, "callable{}-{}", i.package, i.item)
1619 }
1620 Scope::LoopIteration(_, _, i) => {
1621 write!(f, "loop-iter({i})")
1622 }
1623 Scope::Loop(..) => {
1624 write!(f, "loop-container")
1625 }
1626 }
1627 }
1628}
1629
1630#[derive(Clone, Debug, Copy, PartialEq, Eq)]
1631pub struct PackageOffset {
1632 pub package_id: PackageId,
1633 pub offset: u32,
1634}
1635
1636#[cfg(test)]
1637struct LogicalStackWithSourceLookup<'a, S> {
1638 trace: LogicalStack,
1639 source_lookup: &'a S,
1640}
1641
1642#[cfg(test)]
1643impl<S: SourceLookup> Display for LogicalStackWithSourceLookup<'_, S> {
1644 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1645 for (i, frame) in self.trace.0.iter().enumerate() {
1646 if i > 0 {
1647 write!(f, " -> ")?;
1648 }
1649
1650 let scope = self.source_lookup.resolve_scope(frame.scope);
1651 write!(
1652 f,
1653 "{}{}@",
1654 scope.name,
1655 if scope.is_adjoint { "†" } else { "" },
1656 )?;
1657 let package_offset = self
1658 .source_lookup
1659 .resolve_logical_stack_entry_location(frame.location);
1660 let l = self.source_lookup.resolve_package_offset(&package_offset);
1661 write!(f, "{}:{}:{}", l.file, l.line, l.column)?;
1662 if let LogicalStackEntryLocation::LoopIteration(_, _, iteration) = frame.location {
1663 write!(f, "[{iteration}]")?;
1664 }
1665 }
1666 Ok(())
1667 }
1668}
1669