GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
joaoboechat/test-get-azdo-userid

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/source/compiler/qsc_eval/src

source/compiler/qsc_eval/src/lib.rs

2616lines · modecode

RawDownload
Latest commit unavailable.
1// Copyright (c) Microsoft Corporation.
2// Licensed under the MIT License.
3
4//! The Q# evaluator handles the execution of Q# programs and/or fragments.
5//! It operates based on vectors of `ExecGraphNode` instances, which act as a control flow graph
6//! and are generated by lowering to FIR. The evaluator will iterate through the given graph,
7//! executing the instructions it encounters and updating the state it was given accordingly, and using
8//! the FIR store to look up graphs for any called functions or operations. The evaluator handles tracking
9//! of stack frames and push/pop of variable scopes, and uses the index into the current execution graph
10//! as a kind of stack pointer, updating the index based on `Jump`, `JumpIf`, and `JumpIfNot` instructions.
11//!
12//! Of note, the evaluator does not own the program state, which is tracked by the passed in `Env`
13//! and `Backend` instances. This allows the evaluator to be reentrant, and supports both whole-program,
14//! effectively stateless execution (like running shots of a program) stateful execution scenarios
15//! (like debugging or notebooks).
16
17#[cfg(test)]
18mod tests;
19
20pub mod backend;
21pub mod debug;
22mod error;
23pub mod intrinsic;
24pub mod noise;
25pub mod output;
26pub mod state;
27pub mod val;
28
29use crate::backend::{Backend, TracingBackend};
30use crate::val::{
31 Value, index_array, make_range, slice_array, update_index_range, update_index_single,
32};
33use core::panic;
34use debug::{CallStack, Frame};
35pub use error::PackageSpan;
36use miette::Diagnostic;
37use num_bigint::BigInt;
38use output::Receiver;
39use qsc_data_structures::{functors::FunctorApp, index_map::IndexMap, span::Span};
40use qsc_fir::fir::{
41 self, BinOp, BlockId, CallableImpl, ConfiguredExecGraph, ExecGraph, ExecGraphConfig,
42 ExecGraphDebugNode, ExecGraphNode, Expr, ExprId, ExprKind, Field, FieldAssign, Global, Lit,
43 LocalItemId, LocalVarId, PackageId, PackageStoreLookup, PatId, PatKind, PrimField, Res, StmtId,
44 StoreItemId, StringComponent, UnOp,
45};
46use qsc_fir::ty::Ty;
47use qsc_lowerer::map_fir_package_to_hir;
48use rand::{SeedableRng, rngs::StdRng};
49use rustc_hash::{FxHashMap, FxHashSet};
50use std::array;
51use std::{
52 cell::RefCell,
53 fmt::{self, Display, Formatter},
54 iter,
55 ops::Neg,
56 rc::Rc,
57};
58use thiserror::Error;
59use val::{Qubit, update_functor_app};
60
61#[derive(Clone, Debug, Diagnostic, Error)]
62pub enum Error {
63 #[error("array too large")]
64 #[diagnostic(code("Qsc.Eval.ArrayTooLarge"))]
65 ArrayTooLarge(#[label("this array has too many items")] PackageSpan),
66
67 #[error("callable already counted")]
68 #[diagnostic(help(
69 "counting for a given callable must be stopped before it can be started again"
70 ))]
71 #[diagnostic(code("Qsc.Eval.CallableAlreadyCounted"))]
72 CallableAlreadyCounted(#[label] PackageSpan),
73
74 #[error("callable not counted")]
75 #[diagnostic(help("counting for a given callable must be started before it can be stopped"))]
76 #[diagnostic(code("Qsc.Eval.CallableNotCounted"))]
77 CallableNotCounted(#[label] PackageSpan),
78
79 #[error("invalid array length: {0}")]
80 #[diagnostic(code("Qsc.Eval.InvalidArrayLength"))]
81 InvalidArrayLength(i64, #[label("cannot be used as a length")] PackageSpan),
82
83 #[error("division by zero")]
84 #[diagnostic(code("Qsc.Eval.DivZero"))]
85 DivZero(#[label("cannot divide by zero")] PackageSpan),
86
87 #[error("empty range")]
88 #[diagnostic(code("Qsc.Eval.EmptyRange"))]
89 EmptyRange(#[label("the range cannot be empty")] PackageSpan),
90
91 #[error("value cannot be used as an index: {0}")]
92 #[diagnostic(code("Qsc.Eval.InvalidIndex"))]
93 InvalidIndex(i64, #[label("invalid index")] PackageSpan),
94
95 #[error("integer too large for operation")]
96 #[diagnostic(code("Qsc.Eval.IntTooLarge"))]
97 IntTooLarge(i64, #[label("this value is too large")] PackageSpan),
98
99 #[error("index out of range: {0}")]
100 #[diagnostic(code("Qsc.Eval.IndexOutOfRange"))]
101 IndexOutOfRange(i64, #[label("out of range")] PackageSpan),
102
103 #[error("intrinsic callable `{0}` failed: {1}")]
104 #[diagnostic(code("Qsc.Eval.IntrinsicFail"))]
105 IntrinsicFail(String, String, #[label] PackageSpan),
106
107 #[error("invalid rotation angle: {0}")]
108 #[diagnostic(code("Qsc.Eval.InvalidRotationAngle"))]
109 InvalidRotationAngle(f64, #[label("invalid rotation angle")] PackageSpan),
110
111 #[error("negative integers cannot be used here: {0}")]
112 #[diagnostic(code("Qsc.Eval.InvalidNegativeInt"))]
113 InvalidNegativeInt(i64, #[label("invalid negative integer")] PackageSpan),
114
115 #[error("output failure")]
116 #[diagnostic(code("Qsc.Eval.OutputFail"))]
117 OutputFail(#[label("failed to generate output")] PackageSpan),
118
119 #[error("qubits in invocation are not unique")]
120 #[diagnostic(code("Qsc.Eval.QubitUniqueness"))]
121 QubitUniqueness(#[label] PackageSpan),
122
123 #[error("qubit used after release")]
124 #[diagnostic(help(
125 "qubits should not be used after being released, which typically occurs when a qubit is used after it has gone out of scope"
126 ))]
127 #[diagnostic(code("Qsc.Eval.QubitUsedAfterRelease"))]
128 QubitUsedAfterRelease(#[label] PackageSpan),
129
130 #[error("qubit double release")]
131 #[diagnostic(code("Qsc.Eval.QubitDoubleRelease"))]
132 QubitDoubleRelease(#[label("qubit has already been released")] PackageSpan),
133
134 #[error("qubits already counted")]
135 #[diagnostic(help("counting for qubits must be stopped before it can be started again"))]
136 #[diagnostic(code("Qsc.Eval.QubitsAlreadyCounted"))]
137 QubitsAlreadyCounted(#[label] PackageSpan),
138
139 #[error("qubits not counted")]
140 #[diagnostic(help("counting for qubits must be started before it can be stopped"))]
141 #[diagnostic(code("Qsc.Eval.QubitsNotCounted"))]
142 QubitsNotCounted(#[label] PackageSpan),
143
144 #[error("qubits are not separable")]
145 #[diagnostic(help(
146 "subset of qubits provided as arguments must not be entangled with any qubits outside of the subset"
147 ))]
148 #[diagnostic(code("Qsc.Eval.QubitsNotSeparable"))]
149 QubitsNotSeparable(#[label] PackageSpan),
150
151 #[error("range with step size of zero")]
152 #[diagnostic(code("Qsc.Eval.RangeStepZero"))]
153 RangeStepZero(#[label("invalid range")] PackageSpan),
154
155 #[error("qubit arrays used in relabeling must be a permutation of the same set of qubits")]
156 #[diagnostic(help("ensure that each qubit is present exactly once in both arrays"))]
157 #[diagnostic(code("Qsc.Eval.RelabelingMismatch"))]
158 RelabelingMismatch(#[label] PackageSpan),
159
160 #[error("Qubit{0} released while not in |0⟩ state")]
161 #[diagnostic(help(
162 "qubits should be returned to the |0⟩ state before being released to satisfy the assumption that allocated qubits start in the |0⟩ state"
163 ))]
164 #[diagnostic(code("Qsc.Eval.ReleasedQubitNotZero"))]
165 ReleasedQubitNotZero(usize, #[label("Qubit{0}")] PackageSpan),
166
167 #[error("cannot compare measurement results")]
168 #[diagnostic(code("Qsc.Eval.ResultComparisonUnsupported"))]
169 #[diagnostic(help(
170 "comparing measurement results is not supported when performing circuit synthesis or base profile QIR generation"
171 ))]
172 ResultComparisonUnsupported(#[label("cannot compare to result")] PackageSpan),
173
174 #[error("cannot compare measurement result from qubit loss")]
175 #[diagnostic(code("Qsc.Eval.ResultLossComparisonUnsupported"))]
176 #[diagnostic(help(
177 "use of a measurement result from a qubit that was lost is not supported, use `IsLossResult` to ensure the result is valid before using it in a comparison"
178 ))]
179 ResultLossComparisonUnsupported(#[label("cannot compare result from qubit loss")] PackageSpan),
180
181 #[error("simulation error: {0}")]
182 #[diagnostic(code("Qsc.Eval.SimulationError"))]
183 SimulationError(String, #[label("simulation error")] PackageSpan),
184
185 #[error("name is not bound")]
186 #[diagnostic(code("Qsc.Eval.UnboundName"))]
187 UnboundName(#[label] PackageSpan),
188
189 #[error("unknown intrinsic `{0}`")]
190 #[diagnostic(code("Qsc.Eval.UnknownIntrinsic"))]
191 UnknownIntrinsic(
192 String,
193 #[label("callable has no implementation")] PackageSpan,
194 ),
195
196 #[error("unsupported return type for intrinsic `{0}`")]
197 #[diagnostic(help("intrinsic callable return type should be `Unit`"))]
198 #[diagnostic(code("Qsc.Eval.UnsupportedIntrinsicType"))]
199 UnsupportedIntrinsicType(String, #[label] PackageSpan),
200
201 #[error("program failed: {0}")]
202 #[diagnostic(code("Qsc.Eval.UserFail"))]
203 UserFail(String, #[label("explicit fail")] PackageSpan),
204}
205
206impl Error {
207 #[must_use]
208 pub fn span(&self) -> &PackageSpan {
209 match self {
210 Error::ArrayTooLarge(span)
211 | Error::CallableAlreadyCounted(span)
212 | Error::CallableNotCounted(span)
213 | Error::DivZero(span)
214 | Error::EmptyRange(span)
215 | Error::IndexOutOfRange(_, span)
216 | Error::InvalidIndex(_, span)
217 | Error::IntrinsicFail(_, _, span)
218 | Error::IntTooLarge(_, span)
219 | Error::InvalidRotationAngle(_, span)
220 | Error::InvalidNegativeInt(_, span)
221 | Error::OutputFail(span)
222 | Error::QubitUniqueness(span)
223 | Error::QubitUsedAfterRelease(span)
224 | Error::QubitDoubleRelease(span)
225 | Error::QubitsAlreadyCounted(span)
226 | Error::QubitsNotCounted(span)
227 | Error::QubitsNotSeparable(span)
228 | Error::RangeStepZero(span)
229 | Error::RelabelingMismatch(span)
230 | Error::ReleasedQubitNotZero(_, span)
231 | Error::ResultComparisonUnsupported(span)
232 | Error::ResultLossComparisonUnsupported(span)
233 | Error::SimulationError(_, span)
234 | Error::UnboundName(span)
235 | Error::UnknownIntrinsic(_, span)
236 | Error::UnsupportedIntrinsicType(_, span)
237 | Error::UserFail(_, span)
238 | Error::InvalidArrayLength(_, span) => span,
239 }
240 }
241}
242
243/// A specialization that may be implemented for an operation.
244enum Spec {
245 /// The default specialization.
246 Body,
247 /// The adjoint specialization.
248 Adj,
249 /// The controlled specialization.
250 Ctl,
251 /// The controlled adjoint specialization.
252 CtlAdj,
253}
254
255impl Display for Spec {
256 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
257 match self {
258 Spec::Body => f.write_str("body"),
259 Spec::Adj => f.write_str("adjoint"),
260 Spec::Ctl => f.write_str("controlled"),
261 Spec::CtlAdj => f.write_str("controlled adjoint"),
262 }
263 }
264}
265
266/// Evaluates the given code with the given context.
267/// # Errors
268/// Returns the first error encountered during execution.
269/// # Panics
270/// On internal error where no result is returned.
271#[allow(clippy::too_many_arguments)]
272pub fn eval<B: Backend>(
273 package: PackageId,
274 seed: Option<u64>,
275 exec_graph: ExecGraph,
276 exec_graph_config: ExecGraphConfig,
277 globals: &impl PackageStoreLookup,
278 env: &mut Env,
279 sim: &mut TracingBackend<'_, B>,
280 receiver: &mut impl Receiver,
281) -> Result<Value, (Error, Vec<Frame>)> {
282 let mut state = State::new(
283 package,
284 exec_graph,
285 exec_graph_config,
286 seed,
287 ErrorBehavior::FailOnError,
288 );
289 let res = state.eval(globals, env, sim, receiver, &[], StepAction::Continue)?;
290 let StepResult::Return(value) = res else {
291 panic!("eval should always return a value");
292 };
293 Ok(value)
294}
295
296/// Evaluates the given callable with the given context.
297/// # Errors
298/// Returns the first error encountered during execution.
299/// # Panics
300/// On internal error where no result is returned.
301#[allow(clippy::too_many_arguments)]
302pub fn invoke<B: Backend>(
303 package: PackageId,
304 seed: Option<u64>,
305 globals: &impl PackageStoreLookup,
306 exec_graph_config: ExecGraphConfig,
307 env: &mut Env,
308 sim: &mut TracingBackend<'_, B>,
309 receiver: &mut impl Receiver,
310 callable: Value,
311 args: Value,
312) -> Result<Value, (Error, Vec<Frame>)> {
313 let mut state = State::new(
314 package,
315 ExecGraph::default(),
316 exec_graph_config,
317 seed,
318 ErrorBehavior::FailOnError,
319 );
320 // Push the callable value into the state stack and then the args value so they are ready for evaluation.
321 state.set_val_register(callable);
322 state.push_val();
323 state.set_val_register(args);
324
325 // Evaluate the call, which will pop the args and callable values from the stack and then either
326 // a) prepare the call stack for the execution of the callable, or
327 // b) invoke the callable directly if it is an intrinsic.
328 state
329 .eval_call(
330 env,
331 sim,
332 globals,
333 Span::default(),
334 Span::default(),
335 receiver,
336 )
337 .map_err(|e| (e, state.capture_stack()))?;
338
339 // Trigger evaluation of the state until the end of the stack is reached and a return value is obtained, which will be the final
340 // result of the invocation.
341 let res = state.eval(globals, env, sim, receiver, &[], StepAction::Continue)?;
342 let StepResult::Return(value) = res else {
343 panic!("eval should always return a value");
344 };
345 Ok(value)
346}
347
348/// The type of step action to take during evaluation
349#[derive(Debug, Copy, Clone, Eq, PartialEq)]
350pub enum StepAction {
351 Next,
352 In,
353 Out,
354 Continue,
355}
356
357// The result of an evaluation step.
358#[derive(Clone, Debug)]
359pub enum StepResult {
360 BreakpointHit(StmtId),
361 Next,
362 StepIn,
363 StepOut,
364 Return(Value),
365 Fail(String),
366}
367
368trait AsIndex {
369 type Output;
370
371 fn as_index(&self, index_source: PackageSpan) -> Self::Output;
372}
373
374impl AsIndex for i64 {
375 type Output = Result<usize, Error>;
376
377 fn as_index(&self, index_source: PackageSpan) -> Self::Output {
378 match (*self).try_into() {
379 Ok(index) => Ok(index),
380 Err(_) => Err(Error::InvalidIndex(*self, index_source)),
381 }
382 }
383}
384
385#[derive(Debug, Clone)]
386pub struct Variable {
387 pub name: Rc<str>,
388 pub value: Value,
389 pub span: Span,
390}
391
392#[derive(Debug, Clone)]
393pub struct VariableInfo {
394 pub value: Value,
395 pub name: Rc<str>,
396 pub type_name: String,
397 pub span: Span,
398}
399
400pub struct Range {
401 step: i64,
402 end: i64,
403 curr: i64,
404}
405
406impl Iterator for Range {
407 type Item = i64;
408
409 fn next(&mut self) -> Option<Self::Item> {
410 let curr = self.curr;
411 self.curr += self.step;
412 if (self.step > 0 && curr <= self.end) || (self.step < 0 && curr >= self.end) {
413 Some(curr)
414 } else {
415 None
416 }
417 }
418}
419
420impl Range {
421 fn new(start: i64, step: i64, end: i64) -> Self {
422 Range {
423 step,
424 end,
425 curr: start,
426 }
427 }
428}
429
430pub struct Env {
431 scopes: Vec<Scope>,
432 qubits: FxHashSet<Rc<Qubit>>,
433}
434
435impl Default for Env {
436 fn default() -> Self {
437 // Always create a global scope for top-level statements.
438 Self {
439 scopes: vec![Scope::default()],
440 qubits: FxHashSet::default(),
441 }
442 }
443}
444
445impl Env {
446 #[must_use]
447 pub fn get(&self, id: LocalVarId) -> Option<&Variable> {
448 self.scopes
449 .iter()
450 .rev()
451 .find_map(|scope| scope.bindings.get(id))
452 }
453
454 fn get_mut(&mut self, id: LocalVarId) -> Option<&mut Variable> {
455 self.scopes
456 .iter_mut()
457 .rev()
458 .find_map(|scope| scope.bindings.get_mut(id))
459 }
460
461 pub fn push_scope(&mut self, frame_id: usize) {
462 let scope = Scope {
463 frame_id,
464 ..Default::default()
465 };
466 self.scopes.push(scope);
467 }
468
469 pub fn push_loop_scope(&mut self, frame_id: usize) {
470 let scope = Scope {
471 frame_id,
472 is_loop: true,
473 ..Default::default()
474 };
475 self.scopes.push(scope);
476 }
477
478 #[must_use]
479 pub fn last_scope_is_loop(&self) -> bool {
480 self.scopes.last().is_some_and(|scope| scope.is_loop)
481 }
482
483 pub fn leave_scope(&mut self) {
484 // Only pop the scope if there is more than one scope in the stack,
485 // because the global/top-level scope cannot be exited.
486 if self.scopes.len() > 1 {
487 self.scopes
488 .pop()
489 .expect("scope should have more than one entry.");
490 }
491 }
492
493 pub fn leave_current_frame(&mut self) {
494 let current_frame_id = self
495 .scopes
496 .last()
497 .expect("should be at least one scope")
498 .frame_id;
499 if current_frame_id == 0 {
500 // Do not remove the global scope.
501 return;
502 }
503 self.scopes
504 .retain(|scope| scope.frame_id != current_frame_id);
505 }
506
507 pub fn bind_variable_in_top_frame(&mut self, local_var_id: LocalVarId, var: Variable) {
508 let Some(scope) = self.scopes.last_mut() else {
509 panic!("no frames in scope");
510 };
511
512 scope.bindings.insert(local_var_id, var);
513 }
514
515 #[must_use]
516 pub fn get_variables_in_top_frame(&self) -> Vec<VariableInfo> {
517 if let Some(scope) = self.scopes.last() {
518 self.get_variables_in_frame(scope.frame_id)
519 } else {
520 vec![]
521 }
522 }
523
524 #[must_use]
525 pub fn get_variables_in_frame(&self, frame_id: usize) -> Vec<VariableInfo> {
526 let candidate_scopes: Vec<_> = self
527 .scopes
528 .iter()
529 .filter(|scope| scope.frame_id == frame_id)
530 .map(|scope| scope.bindings.iter())
531 .collect();
532
533 let variables_by_scope: Vec<Vec<VariableInfo>> = candidate_scopes
534 .into_iter()
535 .map(|bindings| {
536 bindings
537 .map(|(_, var)| VariableInfo {
538 name: var.name.clone(),
539 type_name: var.value.type_name().to_string(),
540 value: var.value.clone(),
541 span: var.span,
542 })
543 .collect()
544 })
545 .collect();
546 variables_by_scope.into_iter().flatten().collect::<Vec<_>>()
547 }
548
549 #[allow(clippy::len_without_is_empty)]
550 #[must_use]
551 pub fn len(&self) -> usize {
552 self.scopes.len()
553 }
554
555 pub fn update_variable_in_top_frame(&mut self, local_var_id: LocalVarId, value: Value) {
556 let variable = self
557 .get_mut(local_var_id)
558 .expect("local variable is not present");
559 variable.value = value;
560 }
561
562 pub fn track_qubit(&mut self, qubit: Rc<Qubit>) {
563 self.qubits.insert(qubit);
564 }
565
566 pub fn release_qubit(&mut self, qubit: &Rc<Qubit>) {
567 self.qubits.remove(qubit);
568 }
569}
570
571#[derive(Default)]
572struct Scope {
573 bindings: IndexMap<LocalVarId, Variable>,
574 frame_id: usize,
575 is_loop: bool,
576}
577
578type CallableCountKey = (StoreItemId, bool, bool);
579
580#[derive(Debug, Clone, Copy, Eq, PartialEq)]
581pub enum ErrorBehavior {
582 /// Fail execution if an error is encountered.
583 FailOnError,
584 /// Stop execution on the first error encountered.
585 StopOnError,
586}
587
588pub struct State {
589 exec_graph_stack: Vec<ConfiguredExecGraph>,
590 idx: u32,
591 idx_stack: Vec<u32>,
592 val_register: Option<Value>,
593 val_stack: Vec<Vec<Value>>,
594 source_package: PackageId,
595 package: PackageId,
596 call_stack: CallStack,
597 current_span: Span,
598 rng: RefCell<StdRng>,
599 call_counts: FxHashMap<CallableCountKey, i64>,
600 qubit_counter: Option<QubitCounter>,
601 dirty_qubits: FxHashSet<usize>,
602 error_behavior: ErrorBehavior,
603 last_error: Option<(Error, Vec<Frame>)>,
604 exec_graph_config: ExecGraphConfig,
605}
606
607impl State {
608 #[must_use]
609 pub fn new(
610 package: PackageId,
611 exec_graph: ExecGraph,
612 exec_graph_config: ExecGraphConfig,
613 classical_seed: Option<u64>,
614 error_behavior: ErrorBehavior,
615 ) -> Self {
616 let rng = match classical_seed {
617 Some(seed) => RefCell::new(StdRng::seed_from_u64(seed)),
618 None => RefCell::new(StdRng::from_entropy()),
619 };
620 Self {
621 exec_graph_stack: vec![exec_graph.select(exec_graph_config)],
622 idx: 0,
623 idx_stack: Vec::new(),
624 val_register: None,
625 val_stack: vec![Vec::new()],
626 source_package: package,
627 package,
628 call_stack: CallStack::default(),
629 current_span: Span::default(),
630 rng,
631 call_counts: FxHashMap::default(),
632 qubit_counter: None,
633 dirty_qubits: FxHashSet::default(),
634 error_behavior,
635 last_error: None,
636 exec_graph_config,
637 }
638 }
639
640 fn current_frame_id(&self) -> usize {
641 self.call_stack.len()
642 }
643
644 fn push_frame(
645 &mut self,
646 exec_graph: ConfiguredExecGraph,
647 id: StoreItemId,
648 functor: FunctorApp,
649 ) {
650 self.call_stack.push_frame(Frame {
651 span: self.current_span,
652 id,
653 caller: self.package,
654 functor,
655 loop_iterations: Vec::new(),
656 });
657 self.exec_graph_stack.push(exec_graph);
658 self.val_stack.push(Vec::new());
659 self.idx_stack.push(self.idx);
660 self.idx = 0;
661 self.package = id.package;
662 }
663
664 fn leave_frame(&mut self) {
665 if let Some(frame) = self.call_stack.pop_frame() {
666 self.package = frame.caller;
667 }
668 self.val_stack.pop();
669 self.idx = self.idx_stack.pop().unwrap_or_default();
670 self.exec_graph_stack.pop();
671 }
672
673 fn push_scope(&mut self, env: &mut Env) {
674 env.push_scope(self.current_frame_id());
675 }
676
677 fn push_loop_scope(&mut self, env: &mut Env, loop_expr: ExprId) {
678 env.push_loop_scope(self.current_frame_id());
679 self.call_stack.push_loop_iteration(loop_expr);
680 }
681
682 fn take_val_register(&mut self) -> Value {
683 self.val_register.take().expect("value should be present")
684 }
685
686 fn set_val_register(&mut self, val: Value) {
687 self.val_register = Some(val);
688 }
689
690 fn pop_val(&mut self) -> Value {
691 self.val_stack
692 .last_mut()
693 .expect("should have at least one value frame")
694 .pop()
695 .expect("value should be present")
696 }
697
698 fn pop_vals(&mut self, len: usize) -> Vec<Value> {
699 let last = self
700 .val_stack
701 .last_mut()
702 .expect("should have at least one value frame");
703 last.drain(last.len() - len..).collect()
704 }
705
706 fn push_val(&mut self) {
707 let val = self.take_val_register();
708 self.val_stack
709 .last_mut()
710 .expect("should have at least one value frame")
711 .push(val);
712 }
713
714 #[must_use]
715 pub fn capture_stack(&self) -> Vec<Frame> {
716 let mut frames = self.call_stack.to_frames();
717
718 let mut span = self.current_span;
719 for frame in frames.iter_mut().rev() {
720 std::mem::swap(&mut frame.span, &mut span);
721 }
722 frames
723 }
724
725 #[must_use]
726 pub fn capture_stack_if_trace_enabled<B: Backend>(
727 &self,
728 tracing_backend: &TracingBackend<'_, B>,
729 ) -> Vec<Frame> {
730 if tracing_backend.is_stacks_enabled() {
731 self.capture_stack()
732 } else {
733 vec![]
734 }
735 }
736
737 fn set_last_error(&mut self, error: Error, frames: Vec<Frame>) {
738 assert!(
739 self.last_error.replace((error, frames)).is_none(),
740 "last error should not be set twice"
741 );
742 }
743
744 fn get_last_error(&mut self) -> Result<(), (Error, Vec<Frame>)> {
745 // Use `is_none` to check for last error, as it avoids the unconditional
746 // `mem::replace` call that `take` would perform.
747 if self.last_error.is_none() {
748 Ok(())
749 } else {
750 Err(self.last_error.take().expect("last error should be set"))
751 }
752 }
753
754 /// # Errors
755 /// Returns the first error encountered during execution.
756 /// # Panics
757 /// When returning a value in the middle of execution.
758 #[allow(clippy::too_many_lines)]
759 pub fn eval<B: Backend>(
760 &mut self,
761 globals: &impl PackageStoreLookup,
762 env: &mut Env,
763 sim: &mut TracingBackend<'_, B>,
764 out: &mut impl Receiver,
765 breakpoints: &[StmtId],
766 step: StepAction,
767 ) -> Result<StepResult, (Error, Vec<Frame>)> {
768 let current_frame = self.current_frame_id();
769 while !self.exec_graph_stack.is_empty() {
770 let exec_graph = self
771 .exec_graph_stack
772 .last()
773 .expect("should have at least one stack frame");
774 let res = match exec_graph.get(self.idx as usize) {
775 Some(ExecGraphNode::Bind(pat)) => {
776 self.idx += 1;
777 self.eval_bind(env, globals, *pat);
778 continue;
779 }
780 Some(ExecGraphNode::Expr(expr)) => {
781 self.idx += 1;
782 match self.eval_expr(env, sim, globals, out, *expr) {
783 Ok(()) => continue,
784 Err(e) => {
785 if self.error_behavior == ErrorBehavior::StopOnError {
786 let error_str = e.to_string();
787 self.set_last_error(e, self.capture_stack());
788 // Clear the execution graph stack to indicate that execution has failed.
789 // This will prevent further execution steps.
790 self.exec_graph_stack.clear();
791 return Ok(StepResult::Fail(error_str));
792 }
793 return Err((e, self.capture_stack()));
794 }
795 }
796 }
797 Some(ExecGraphNode::Jump(idx)) => {
798 self.idx = *idx;
799 continue;
800 }
801 Some(ExecGraphNode::JumpIf(idx)) => {
802 let cond = self.val_register == Some(Value::Bool(true));
803 if cond {
804 self.idx = *idx;
805 } else {
806 self.idx += 1;
807 }
808 continue;
809 }
810 Some(ExecGraphNode::JumpIfNot(idx)) => {
811 let cond = self.val_register == Some(Value::Bool(true));
812 if cond {
813 self.idx += 1;
814 } else {
815 self.idx = *idx;
816 }
817 continue;
818 }
819 Some(ExecGraphNode::Store) => {
820 self.push_val();
821 self.idx += 1;
822 continue;
823 }
824 Some(ExecGraphNode::Unit) => {
825 self.idx += 1;
826 self.set_val_register(Value::unit());
827 continue;
828 }
829 Some(ExecGraphNode::Ret) => {
830 self.leave_frame();
831 env.leave_scope();
832 continue;
833 }
834 Some(ExecGraphNode::Debug(dbg_node)) => match dbg_node {
835 ExecGraphDebugNode::PushScope => {
836 self.push_scope(env);
837 self.idx += 1;
838 continue;
839 }
840 ExecGraphDebugNode::PushLoopScope(expr) => {
841 self.push_loop_scope(env, *expr);
842 self.idx += 1;
843 continue;
844 }
845 ExecGraphDebugNode::RetFrame => {
846 self.leave_frame();
847 env.leave_current_frame();
848 continue;
849 }
850 ExecGraphDebugNode::LoopIteration => {
851 // we're in an iteration, increment counter
852 self.call_stack.increment_loop_iteration();
853 self.idx += 1;
854 continue;
855 }
856 ExecGraphDebugNode::PopScope => {
857 if env.last_scope_is_loop() {
858 self.call_stack.pop_loop_iteration();
859 }
860 env.leave_scope();
861 self.idx += 1;
862 continue;
863 }
864 ExecGraphDebugNode::BlockEnd(id) => {
865 self.idx += 1;
866 match self.check_for_block_exit_break(globals, *id, step, current_frame) {
867 Some((result, span)) => {
868 self.current_span = span;
869 return Ok(result);
870 }
871 None => continue,
872 }
873 }
874 ExecGraphDebugNode::Stmt(stmt) => {
875 self.idx += 1;
876 self.current_span = globals.get_stmt((self.package, *stmt).into()).span;
877
878 match self.check_for_break(breakpoints, *stmt, step, current_frame) {
879 Some(value) => value,
880 None => continue,
881 }
882 }
883 },
884 None => {
885 // We have reached the end of the current graph without reaching an explicit return node,
886 // usually indicating the partial execution of a single sub-expression.
887 // This means we should pop the execution graph but not the current environment scope,
888 // so bound variables are still accessible after completion.
889 self.exec_graph_stack.pop();
890 assert!(self.exec_graph_stack.is_empty());
891 continue;
892 }
893 };
894
895 if let StepResult::Return(_) = res {
896 panic!("unexpected return");
897 }
898
899 return Ok(res);
900 }
901
902 // If we made it out of the execution loop, we either reached the end of the graph,
903 // a return expression, or hit a runtime error. Check here for the error case
904 // and return it if it exists.
905 self.get_last_error()?;
906
907 Ok(StepResult::Return(self.get_result()))
908 }
909
910 fn check_for_break(
911 &self,
912 breakpoints: &[StmtId],
913 stmt: StmtId,
914 step: StepAction,
915 current_frame: usize,
916 ) -> Option<StepResult> {
917 Some(
918 if let Some(bp) = breakpoints
919 .iter()
920 .find(|&bp| *bp == stmt && self.package == self.source_package)
921 {
922 StepResult::BreakpointHit(*bp)
923 } else {
924 if self.current_span == Span::default() {
925 // if there is no span, we are in generated code, so we should skip
926 return None;
927 }
928 // no breakpoint, but we may stop here
929 if step == StepAction::In {
930 StepResult::StepIn
931 } else if step == StepAction::Next && current_frame >= self.current_frame_id() {
932 StepResult::Next
933 } else if step == StepAction::Out && current_frame > self.current_frame_id() {
934 StepResult::StepOut
935 } else {
936 return None;
937 }
938 },
939 )
940 }
941
942 fn check_for_block_exit_break(
943 &self,
944 globals: &impl PackageStoreLookup,
945 block: BlockId,
946 step: StepAction,
947 current_frame: usize,
948 ) -> Option<(StepResult, Span)> {
949 if step == StepAction::Next && current_frame >= self.current_frame_id() {
950 let block = globals.get_block((self.package, block).into());
951 let span = Span {
952 lo: block.span.hi - 1,
953 hi: block.span.hi,
954 };
955 Some((StepResult::Next, span))
956 } else {
957 None
958 }
959 }
960
961 pub fn get_result(&mut self) -> Value {
962 // Some executions don't have any statements to execute,
963 // such as a fragment that has only item definitions.
964 // In that case, the values are empty and the result is unit.
965 self.val_register.take().unwrap_or_else(Value::unit)
966 }
967
968 #[allow(clippy::similar_names)]
969 fn eval_expr<B: Backend>(
970 &mut self,
971 env: &mut Env,
972 sim: &mut TracingBackend<'_, B>,
973 globals: &impl PackageStoreLookup,
974 out: &mut impl Receiver,
975 expr: ExprId,
976 ) -> Result<(), Error> {
977 let expr = globals.get_expr((self.package, expr).into());
978 self.current_span = expr.span;
979 match &expr.kind {
980 ExprKind::Array(arr) => self.eval_arr(arr.len()),
981 ExprKind::ArrayLit(arr) => self.eval_arr_lit(arr, globals),
982 ExprKind::ArrayRepeat(..) => self.eval_arr_repeat(expr.span)?,
983 ExprKind::Assign(lhs, _) => self.eval_assign(env, globals, *lhs)?,
984 ExprKind::AssignOp(op, lhs, rhs) => {
985 let lhs_span = globals.get_expr((self.package, *lhs).into()).span;
986 let rhs_span = globals.get_expr((self.package, *rhs).into()).span;
987 let (is_array, is_unique) =
988 is_updatable_in_place(env, globals.get_expr((self.package, *lhs).into()));
989 if is_array {
990 if is_unique {
991 self.eval_array_append_in_place(env, globals, *lhs)?;
992 return Ok(());
993 }
994 let rhs_val = self.take_val_register();
995 self.eval_expr(env, sim, globals, out, *lhs)?;
996 self.push_val();
997 self.set_val_register(rhs_val);
998 }
999 self.eval_binop(*op, lhs_span, rhs_span)?;
1000 self.eval_assign(env, globals, *lhs)?;
1001 }
1002 ExprKind::AssignField(record, field, _) => {
1003 self.eval_update_field(field.clone());
1004 self.eval_assign(env, globals, *record)?;
1005 }
1006 ExprKind::AssignIndex(lhs, mid, _) => {
1007 let mid_span = globals.get_expr((self.package, *mid).into()).span;
1008 let (_, is_unique) =
1009 is_updatable_in_place(env, globals.get_expr((self.package, *lhs).into()));
1010 if is_unique {
1011 self.eval_update_index_in_place(env, globals, *lhs, mid_span)?;
1012 return Ok(());
1013 }
1014 self.push_val();
1015 self.eval_expr(env, sim, globals, out, *lhs)?;
1016 self.eval_update_index(mid_span)?;
1017 self.eval_assign(env, globals, *lhs)?;
1018 }
1019 ExprKind::BinOp(op, lhs, rhs) => {
1020 let lhs_span = globals.get_expr((self.package, *lhs).into()).span;
1021 let rhs_span = globals.get_expr((self.package, *rhs).into()).span;
1022 self.eval_binop(*op, lhs_span, rhs_span)?;
1023 }
1024 ExprKind::Block(..) => panic!("block expr should be handled by control flow"),
1025 ExprKind::Call(callee_expr, args_expr) => {
1026 let callable_span = globals.get_expr((self.package, *callee_expr).into()).span;
1027 let args_span = globals.get_expr((self.package, *args_expr).into()).span;
1028 self.eval_call(env, sim, globals, callable_span, args_span, out)?;
1029 }
1030 ExprKind::Closure(args, callable) => {
1031 let closure = resolve_closure(env, self.package, expr.span, args, *callable)?;
1032 self.set_val_register(closure);
1033 }
1034 ExprKind::Fail(..) => {
1035 return Err(Error::UserFail(
1036 self.take_val_register().unwrap_string().to_string(),
1037 self.to_global_span(expr.span),
1038 ));
1039 }
1040 ExprKind::Field(_, field) => self.eval_field(field.clone()),
1041 ExprKind::Hole => panic!("hole expr should be disallowed by passes"),
1042 ExprKind::If(..) => {
1043 panic!("if expr should be handled by control flow")
1044 }
1045 ExprKind::Index(_, rhs) => {
1046 let rhs_span = globals.get_expr((self.package, *rhs).into()).span;
1047 self.eval_index(rhs_span)?;
1048 }
1049 ExprKind::Lit(lit) => {
1050 self.set_val_register(lit_to_val(lit));
1051 }
1052 ExprKind::Range(start, step, end) => {
1053 self.eval_range(start.is_some(), step.is_some(), end.is_some());
1054 }
1055 ExprKind::Return(..) => panic!("return expr should be handled by control flow"),
1056 ExprKind::Struct(res, copy, fields) => self.eval_struct(res, *copy, fields),
1057 ExprKind::String(components) => self.collect_string(components),
1058 ExprKind::UpdateIndex(_, mid, _) => {
1059 let mid_span = globals.get_expr((self.package, *mid).into()).span;
1060 self.eval_update_index(mid_span)?;
1061 }
1062 ExprKind::Tuple(tup) => self.eval_tup(tup.len()),
1063 ExprKind::UnOp(op, _) => self.eval_unop(*op),
1064 ExprKind::UpdateField(_, field, _) => {
1065 self.eval_update_field(field.clone());
1066 }
1067 ExprKind::Var(res, _) => {
1068 self.set_val_register(resolve_binding(env, self.package, *res, expr.span)?);
1069 }
1070 ExprKind::While(..) => {
1071 panic!("while expr should be handled by control flow")
1072 }
1073 }
1074
1075 Ok(())
1076 }
1077
1078 fn collect_string(&mut self, components: &[StringComponent]) {
1079 if let [StringComponent::Lit(str)] = components {
1080 self.set_val_register(Value::String(Rc::clone(str)));
1081 return;
1082 }
1083
1084 let mut string = String::new();
1085 for component in components.iter().rev() {
1086 match component {
1087 StringComponent::Expr(..) => {
1088 let expr_str = format!("{}", self.pop_val());
1089 string.insert_str(0, &expr_str);
1090 }
1091 StringComponent::Lit(lit) => {
1092 string.insert_str(0, lit);
1093 }
1094 }
1095 }
1096 self.set_val_register(Value::String(Rc::from(string)));
1097 }
1098
1099 fn eval_arr(&mut self, len: usize) {
1100 let arr = self.pop_vals(len);
1101 self.set_val_register(Value::Array(arr.into()));
1102 }
1103
1104 fn eval_arr_lit(&mut self, arr: &Vec<ExprId>, globals: &impl PackageStoreLookup) {
1105 let mut new_arr: Rc<Vec<Value>> = Rc::new(Vec::with_capacity(arr.len()));
1106 for id in arr {
1107 let ExprKind::Lit(lit) = &globals.get_expr((self.package, *id).into()).kind else {
1108 panic!("expr kind should be lit")
1109 };
1110 Rc::get_mut(&mut new_arr)
1111 .expect("array should be uniquely referenced")
1112 .push(lit_to_val(lit));
1113 }
1114 self.set_val_register(Value::Array(new_arr));
1115 }
1116
1117 fn eval_array_append_in_place(
1118 &mut self,
1119 env: &mut Env,
1120 globals: &impl PackageStoreLookup,
1121 lhs: ExprId,
1122 ) -> Result<(), Error> {
1123 let lhs = globals.get_expr((self.package, lhs).into());
1124 let rhs = self.take_val_register();
1125 match (&lhs.kind, rhs) {
1126 (&ExprKind::Var(Res::Local(id), _), rhs) => match env.get_mut(id) {
1127 Some(var) => {
1128 var.value.append_array(rhs);
1129 }
1130 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1131 },
1132 _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
1133 }
1134 Ok(())
1135 }
1136
1137 fn eval_arr_repeat(&mut self, span: Span) -> Result<(), Error> {
1138 let size_val = self.take_val_register().unwrap_int();
1139 let item_val = self.pop_val();
1140 let s = match size_val.try_into() {
1141 Ok(i) => Ok(i),
1142 Err(_) => Err(Error::InvalidArrayLength(
1143 size_val,
1144 self.to_global_span(span),
1145 )),
1146 }?;
1147 self.set_val_register(Value::Array(vec![item_val; s].into()));
1148 Ok(())
1149 }
1150
1151 fn eval_assign(
1152 &mut self,
1153 env: &mut Env,
1154 globals: &impl PackageStoreLookup,
1155 lhs: ExprId,
1156 ) -> Result<(), Error> {
1157 let rhs = self.take_val_register();
1158 self.update_binding(env, globals, lhs, rhs)
1159 }
1160
1161 fn eval_bind(&mut self, env: &mut Env, globals: &impl PackageStoreLookup, pat: PatId) {
1162 let val = self.take_val_register();
1163 self.bind_value(env, globals, pat, val);
1164 }
1165
1166 fn eval_binop(&mut self, op: BinOp, lhs_span: Span, rhs_span: Span) -> Result<(), Error> {
1167 match op {
1168 BinOp::Add => self.eval_binop_simple(eval_binop_add),
1169 BinOp::AndB => self.eval_binop_simple(eval_binop_andb),
1170 BinOp::Div => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_div)?,
1171 BinOp::Eq => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_eq)?,
1172 BinOp::Exp => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_exp)?,
1173 BinOp::Gt => self.eval_binop_simple(eval_binop_gt),
1174 BinOp::Gte => self.eval_binop_simple(eval_binop_gte),
1175 BinOp::Lt => self.eval_binop_simple(eval_binop_lt),
1176 BinOp::Lte => self.eval_binop_simple(eval_binop_lte),
1177 BinOp::Mod => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_mod)?,
1178 BinOp::Mul => self.eval_binop_simple(eval_binop_mul),
1179 BinOp::Neq => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_neq)?,
1180 BinOp::OrB => self.eval_binop_simple(eval_binop_orb),
1181 BinOp::Shl => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_shl)?,
1182 BinOp::Shr => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_shr)?,
1183 BinOp::Sub => self.eval_binop_simple(eval_binop_sub),
1184 BinOp::XorB => self.eval_binop_simple(eval_binop_xorb),
1185
1186 // Logical operators should be handled by control flow
1187 BinOp::AndL | BinOp::OrL => {}
1188 }
1189 Ok(())
1190 }
1191
1192 fn eval_binop_simple(&mut self, binop_func: impl FnOnce(Value, Value) -> Value) {
1193 let rhs_val = self.take_val_register();
1194 let lhs_val = self.pop_val();
1195 self.set_val_register(binop_func(lhs_val, rhs_val));
1196 }
1197
1198 fn eval_binop_with_error(
1199 &mut self,
1200 lhs_span: Span,
1201 rhs_span: Span,
1202 binop_func: impl FnOnce(Value, Value, PackageSpan, PackageSpan) -> Result<Value, Error>,
1203 ) -> Result<(), Error> {
1204 let lhs_span: PackageSpan = self.to_global_span(lhs_span);
1205 let rhs_span: PackageSpan = self.to_global_span(rhs_span);
1206 let rhs_val = self.take_val_register();
1207 let lhs_val = self.pop_val();
1208 self.set_val_register(binop_func(lhs_val, rhs_val, lhs_span, rhs_span)?);
1209 Ok(())
1210 }
1211
1212 fn eval_call<B: Backend>(
1213 &mut self,
1214 env: &mut Env,
1215 sim: &mut TracingBackend<'_, B>,
1216 globals: &impl PackageStoreLookup,
1217 callable_span: Span,
1218 arg_span: Span,
1219 out: &mut impl Receiver,
1220 ) -> Result<(), Error> {
1221 let arg = self.take_val_register();
1222 let (callee_id, functor, fixed_args) = match self.pop_val() {
1223 Value::Closure(inner) => (inner.id, inner.functor, Some(inner.fixed_args)),
1224 Value::Global(id, functor) => (id, functor, None),
1225 _ => panic!("value is not callable"),
1226 };
1227
1228 let arg_span = self.to_global_span(arg_span);
1229
1230 let callee = match globals.get_global(callee_id) {
1231 Some(Global::Callable(callable)) => callable,
1232 Some(Global::Udt) => {
1233 let arg = match arg {
1234 Value::Tuple(items, _) => Value::Tuple(items, Some(callee_id.into())),
1235 _ => arg,
1236 };
1237 self.set_val_register(arg);
1238 return Ok(());
1239 }
1240 None => return Err(Error::UnboundName(self.to_global_span(callable_span))),
1241 };
1242
1243 let callee_span = self.to_global_span(callee.span);
1244
1245 let spec = spec_from_functor_app(functor);
1246 match &callee.implementation {
1247 CallableImpl::Intrinsic if is_counting_call(&callee.name.name) => {
1248 self.push_frame(Vec::new().into(), callee_id, functor);
1249
1250 let val = self.counting_call(&callee.name.name, arg, arg_span)?;
1251
1252 self.set_val_register(val);
1253 self.leave_frame();
1254 Ok(())
1255 }
1256 CallableImpl::Intrinsic => self.eval_intrinsic(
1257 env,
1258 callee_id,
1259 functor,
1260 callee,
1261 sim,
1262 callee_span,
1263 arg,
1264 arg_span,
1265 out,
1266 ),
1267 CallableImpl::Spec(specialized_implementation) => {
1268 let spec_decl = match spec {
1269 Spec::Body => Some(&specialized_implementation.body),
1270 Spec::Adj => specialized_implementation.adj.as_ref(),
1271 Spec::Ctl => specialized_implementation.ctl.as_ref(),
1272 Spec::CtlAdj => specialized_implementation.ctl_adj.as_ref(),
1273 }
1274 .expect("missing specialization should be a compilation error");
1275 self.push_frame(
1276 spec_decl.exec_graph.clone().select(self.exec_graph_config),
1277 callee_id,
1278 functor,
1279 );
1280 self.push_scope(env);
1281 self.increment_call_count(callee_id, functor);
1282
1283 self.bind_args_for_spec(
1284 env,
1285 globals,
1286 callee.input,
1287 spec_decl.input,
1288 arg,
1289 arg_span,
1290 functor.controlled,
1291 fixed_args,
1292 )?;
1293 Ok(())
1294 }
1295 CallableImpl::SimulatableIntrinsic(spec_decl) => {
1296 self.push_frame(
1297 spec_decl.exec_graph.clone().select(self.exec_graph_config),
1298 callee_id,
1299 functor,
1300 );
1301 self.push_scope(env);
1302
1303 self.bind_args_for_spec(
1304 env,
1305 globals,
1306 callee.input,
1307 spec_decl.input,
1308 arg,
1309 arg_span,
1310 functor.controlled,
1311 fixed_args,
1312 )?;
1313 Ok(())
1314 }
1315 }
1316 }
1317
1318 #[allow(clippy::too_many_arguments)]
1319 fn eval_intrinsic<B: Backend>(
1320 &mut self,
1321 env: &mut Env,
1322 callee_id: StoreItemId,
1323 functor: FunctorApp,
1324 callee: &fir::CallableDecl,
1325 sim: &mut TracingBackend<'_, B>,
1326 callee_span: PackageSpan,
1327 arg: Value,
1328 arg_span: PackageSpan,
1329 out: &mut impl Receiver,
1330 ) -> Result<(), Error> {
1331 let call_stack = self.capture_stack_if_trace_enabled(sim);
1332 self.push_frame(Vec::new().into(), callee_id, functor);
1333 self.current_span = callee_span.span;
1334 self.increment_call_count(callee_id, functor);
1335 let name = &callee.name.name;
1336 let val = match name.as_ref() {
1337 "__quantum__rt__qubit_allocate" | "__quantum__rt__qubit_borrow" => {
1338 let q = sim
1339 .qubit_allocate(&call_stack)
1340 .map_err(|e| Error::SimulationError(e, callee_span))?;
1341 let q = Rc::new(Qubit(q));
1342 env.track_qubit(Rc::clone(&q));
1343 if let Some(counter) = &mut self.qubit_counter {
1344 counter.allocated(q.0);
1345 }
1346 if name.as_ref() == "__quantum__rt__qubit_borrow" {
1347 self.dirty_qubits.insert(q.0);
1348 }
1349 Value::Qubit(q.into())
1350 }
1351 "__quantum__rt__qubit_release" => {
1352 let qubit = arg
1353 .unwrap_qubit()
1354 .try_deref()
1355 .ok_or(Error::QubitDoubleRelease(arg_span))?;
1356 env.release_qubit(&qubit);
1357 let is_zero = sim
1358 .qubit_release(qubit.0, &call_stack)
1359 .map_err(|e| Error::SimulationError(e, callee_span))?;
1360 let is_borrowed = self.dirty_qubits.remove(&qubit.0);
1361 if is_zero || is_borrowed {
1362 Value::unit()
1363 } else {
1364 return Err(Error::ReleasedQubitNotZero(qubit.0, arg_span));
1365 }
1366 }
1367 _ => {
1368 let val = intrinsic::call(
1369 name,
1370 callee_span,
1371 arg,
1372 arg_span,
1373 &call_stack,
1374 sim,
1375 &mut self.rng.borrow_mut(),
1376 out,
1377 )?;
1378 if val == Value::unit() && callee.output != Ty::UNIT {
1379 return Err(Error::UnsupportedIntrinsicType(
1380 callee.name.name.to_string(),
1381 callee_span,
1382 ));
1383 }
1384 val
1385 }
1386 };
1387 self.set_val_register(val);
1388 self.leave_frame();
1389 Ok(())
1390 }
1391
1392 fn eval_field(&mut self, field: Field) {
1393 let record = self.take_val_register();
1394 let val = match (record, field) {
1395 (Value::Range(inner), Field::Prim(PrimField::Start)) => Value::Int(
1396 inner
1397 .start
1398 .expect("range access should be validated by compiler"),
1399 ),
1400 (Value::Range(inner), Field::Prim(PrimField::Step)) => Value::Int(inner.step),
1401 (Value::Range(inner), Field::Prim(PrimField::End)) => Value::Int(
1402 inner
1403 .end
1404 .expect("range access should be validated by compiler"),
1405 ),
1406 (record, Field::Path(path)) => {
1407 follow_field_path(record, &path.indices).expect("field path should be valid")
1408 }
1409 (ref value, ref field) => {
1410 panic!("invalid field access. value: {value:?}, field: {field:?}")
1411 }
1412 };
1413 self.set_val_register(val);
1414 }
1415
1416 fn eval_index(&mut self, span: Span) -> Result<(), Error> {
1417 let index_val = self.take_val_register();
1418 let arr = self.pop_val().unwrap_array();
1419 match &index_val {
1420 Value::Int(i) => {
1421 self.set_val_register(index_array(&arr, *i, self.to_global_span(span))?);
1422 }
1423 Value::Range(inner) => {
1424 self.set_val_register(slice_array(
1425 &arr,
1426 inner.start,
1427 inner.step,
1428 inner.end,
1429 self.to_global_span(span),
1430 )?);
1431 }
1432 _ => panic!("array should only be indexed by Int or Range"),
1433 }
1434 Ok(())
1435 }
1436
1437 fn eval_range(&mut self, has_start: bool, has_step: bool, has_end: bool) {
1438 let end = if has_end {
1439 Some(self.take_val_register().unwrap_int())
1440 } else {
1441 None
1442 };
1443 let step = if has_step {
1444 self.pop_val().unwrap_int()
1445 } else {
1446 val::DEFAULT_RANGE_STEP
1447 };
1448 let start = if has_start {
1449 Some(self.pop_val().unwrap_int())
1450 } else {
1451 None
1452 };
1453 self.set_val_register(Value::Range(val::Range { start, step, end }.into()));
1454 }
1455
1456 fn eval_struct(&mut self, res: &Res, copy: Option<ExprId>, fields: &[FieldAssign]) {
1457 // Extract a flat list of field indexes.
1458 let field_indexes = fields
1459 .iter()
1460 .map(|f| match &f.field {
1461 Field::Path(path) => match path.indices.as_slice() {
1462 &[i] => i,
1463 _ => panic!("field path for struct should have a single index"),
1464 },
1465 _ => panic!("invalid field for struct"),
1466 })
1467 .collect::<Vec<_>>();
1468
1469 let len = fields.len();
1470
1471 let (field_vals, mut strct) = if copy.is_some() {
1472 // Get the field values and the copy struct value.
1473 let field_vals = self.pop_vals(len + 1);
1474 let (copy, field_vals) = field_vals.split_first().expect("copy value is expected");
1475
1476 // Make a clone of the copy struct value.
1477 (field_vals.to_vec(), copy.clone().unwrap_tuple().to_vec())
1478 } else {
1479 // Make an empty struct of the appropriate size.
1480 (self.pop_vals(len), vec![Value::Int(0); len])
1481 };
1482
1483 // Insert the field values into the new struct.
1484 assert!(
1485 field_vals.len() == field_indexes.len(),
1486 "number of given field values should match the number of given struct fields"
1487 );
1488 for (i, val) in field_indexes.iter().zip(field_vals.into_iter()) {
1489 strct[*i] = val;
1490 }
1491
1492 let store_item_id = if let Res::Item(item_id) = res {
1493 StoreItemId {
1494 package: item_id.package,
1495 item: item_id.item,
1496 }
1497 } else {
1498 panic!("UDT should be an item");
1499 };
1500
1501 self.set_val_register(Value::Tuple(strct.into(), Some(Rc::new(store_item_id))));
1502 }
1503
1504 fn eval_update_index(&mut self, span: Span) -> Result<(), Error> {
1505 let values = self.take_val_register().unwrap_array();
1506 let update = self.pop_val();
1507 let index = self.pop_val();
1508 let span = self.to_global_span(span);
1509 match index {
1510 Value::Int(index) => self.eval_update_index_single(&values, index, update, span),
1511 Value::Range(inner) => self.eval_update_index_range(
1512 &values,
1513 inner.start,
1514 inner.step,
1515 inner.end,
1516 update,
1517 span,
1518 ),
1519 _ => unreachable!("array should only be indexed by Int or Range"),
1520 }
1521 }
1522
1523 fn eval_update_index_single(
1524 &mut self,
1525 values: &[Value],
1526 index: i64,
1527 update: Value,
1528 span: PackageSpan,
1529 ) -> Result<(), Error> {
1530 let updated_array = update_index_single(values, index, update, span)?;
1531 self.set_val_register(updated_array);
1532 Ok(())
1533 }
1534
1535 fn eval_update_index_range(
1536 &mut self,
1537 values: &[Value],
1538 start: Option<i64>,
1539 step: i64,
1540 end: Option<i64>,
1541 update: Value,
1542 span: PackageSpan,
1543 ) -> Result<(), Error> {
1544 let updated_array = update_index_range(values, start, step, end, update, span)?;
1545 self.set_val_register(updated_array);
1546 Ok(())
1547 }
1548
1549 fn eval_update_index_in_place(
1550 &mut self,
1551 env: &mut Env,
1552 globals: &impl PackageStoreLookup,
1553 lhs: ExprId,
1554 span: Span,
1555 ) -> Result<(), Error> {
1556 let update = self.take_val_register();
1557 let index = self.pop_val();
1558 let span = self.to_global_span(span);
1559 match index {
1560 Value::Int(index) => {
1561 if index < 0 {
1562 return Err(Error::InvalidNegativeInt(index, span));
1563 }
1564 self.update_array_index_single(env, globals, lhs, span, index, update)
1565 }
1566 range @ Value::Range(..) => {
1567 self.update_array_index_range(env, globals, lhs, span, &range, update)
1568 }
1569 _ => unreachable!("array should only be indexed by Int or Range"),
1570 }
1571 }
1572
1573 fn eval_tup(&mut self, len: usize) {
1574 let tup = self.pop_vals(len);
1575 self.set_val_register(Value::Tuple(tup.into(), None));
1576 }
1577
1578 fn eval_unop(&mut self, op: UnOp) {
1579 let val = self.take_val_register();
1580 match op {
1581 UnOp::Functor(functor) => match val {
1582 Value::Closure(inner) => {
1583 self.set_val_register(Value::Closure(
1584 val::Closure {
1585 functor: update_functor_app(functor, inner.functor),
1586 ..*inner
1587 }
1588 .into(),
1589 ));
1590 }
1591 Value::Global(id, app) => {
1592 self.set_val_register(Value::Global(id, update_functor_app(functor, app)));
1593 }
1594 _ => panic!("value should be callable"),
1595 },
1596 UnOp::Neg => match val {
1597 Value::BigInt(v) => self.set_val_register(Value::BigInt(v.neg())),
1598 Value::Double(v) => self.set_val_register(Value::Double(v.neg())),
1599 Value::Int(v) => self.set_val_register(Value::Int(v.wrapping_neg())),
1600 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
1601 let [real, imag] = array::from_fn(|i| v[i].clone());
1602 let real = real.unwrap_double();
1603 let imag = imag.unwrap_double();
1604 self.set_val_register(Value::Tuple(
1605 vec![Value::Double(-real), Value::Double(-imag)].into(),
1606 Some(Rc::new(StoreItemId::complex())),
1607 ));
1608 }
1609 _ => panic!("value should be number"),
1610 },
1611 UnOp::NotB => match val {
1612 Value::Int(v) => self.set_val_register(Value::Int(!v)),
1613 Value::BigInt(v) => self.set_val_register(Value::BigInt(!v)),
1614 _ => panic!("value should be Int or BigInt"),
1615 },
1616 UnOp::NotL => match val {
1617 Value::Bool(b) => self.set_val_register(Value::Bool(!b)),
1618 _ => panic!("value should be bool"),
1619 },
1620 UnOp::Pos => match val {
1621 Value::BigInt(_) | Value::Int(_) | Value::Double(_) => self.set_val_register(val),
1622 Value::Tuple(_, Some(ref id)) if *id.as_ref() == StoreItemId::complex() => {
1623 self.set_val_register(val);
1624 }
1625 _ => panic!("value should be number"),
1626 },
1627 UnOp::Unwrap => self.set_val_register(val),
1628 }
1629 }
1630
1631 fn eval_update_field(&mut self, field: Field) {
1632 let record = self.take_val_register();
1633 let value = self.pop_val();
1634 let update = match (record, field) {
1635 (Value::Range(mut inner), Field::Prim(PrimField::Start)) => {
1636 inner.start = Some(value.unwrap_int());
1637 Value::Range(inner)
1638 }
1639 (Value::Range(mut inner), Field::Prim(PrimField::Step)) => {
1640 inner.step = value.unwrap_int();
1641 Value::Range(inner)
1642 }
1643 (Value::Range(mut inner), Field::Prim(PrimField::End)) => {
1644 inner.end = Some(value.unwrap_int());
1645 Value::Range(inner)
1646 }
1647 (record, Field::Path(path)) => update_field_path(&record, &path.indices, &value)
1648 .expect("field path should be valid"),
1649 _ => panic!("invalid field access"),
1650 };
1651 self.set_val_register(update);
1652 }
1653
1654 fn bind_value(&self, env: &mut Env, globals: &impl PackageStoreLookup, pat: PatId, val: Value) {
1655 let pat = globals.get_pat((self.package, pat).into());
1656 match &pat.kind {
1657 PatKind::Bind(variable) => {
1658 let scope = env.scopes.last_mut().expect("binding should have a scope");
1659 scope.bindings.insert(
1660 variable.id,
1661 Variable {
1662 name: variable.name.clone(),
1663 value: val,
1664 span: variable.span,
1665 },
1666 );
1667 }
1668 PatKind::Discard => {}
1669 PatKind::Tuple(tup) => {
1670 let val_tup = val.unwrap_tuple();
1671 for (pat, val) in tup.iter().zip(val_tup.iter()) {
1672 self.bind_value(env, globals, *pat, val.clone());
1673 }
1674 }
1675 }
1676 }
1677
1678 #[allow(clippy::similar_names)]
1679 fn update_binding(
1680 &self,
1681 env: &mut Env,
1682 globals: &impl PackageStoreLookup,
1683 lhs: ExprId,
1684 rhs: Value,
1685 ) -> Result<(), Error> {
1686 let lhs = globals.get_expr((self.package, lhs).into());
1687 match (&lhs.kind, rhs) {
1688 (ExprKind::Hole, _) => {}
1689 (&ExprKind::Var(Res::Local(id), _), rhs) => match env.get_mut(id) {
1690 Some(var) => {
1691 var.value = rhs;
1692 }
1693 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1694 },
1695 (ExprKind::Tuple(var_tup), Value::Tuple(tup, _)) => {
1696 for (expr, val) in var_tup.iter().zip(tup.iter()) {
1697 self.update_binding(env, globals, *expr, val.clone())?;
1698 }
1699 }
1700 _ => unreachable!("unassignable pattern should be disallowed by compiler"),
1701 }
1702 Ok(())
1703 }
1704
1705 fn update_array_index_single(
1706 &mut self,
1707 env: &mut Env,
1708 globals: &impl PackageStoreLookup,
1709 lhs: ExprId,
1710 span: PackageSpan,
1711 index: i64,
1712 rhs: Value,
1713 ) -> Result<(), Error> {
1714 let lhs = globals.get_expr((self.package, lhs).into());
1715 match &lhs.kind {
1716 &ExprKind::Var(Res::Local(id), _) => match env.get_mut(id) {
1717 Some(var) => {
1718 var.value.update_array(index, rhs, span)?;
1719 }
1720 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1721 },
1722 _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
1723 }
1724 Ok(())
1725 }
1726
1727 #[allow(clippy::similar_names)] // `env` and `end` are similar but distinct
1728 fn update_array_index_range(
1729 &mut self,
1730 env: &mut Env,
1731 globals: &impl PackageStoreLookup,
1732 lhs: ExprId,
1733 range_span: PackageSpan,
1734 range: &Value,
1735 update: Value,
1736 ) -> Result<(), Error> {
1737 let lhs = globals.get_expr((self.package, lhs).into());
1738 match &lhs.kind {
1739 &ExprKind::Var(Res::Local(id), _) => match env.get_mut(id) {
1740 Some(var) => {
1741 let rhs = update.unwrap_array();
1742 let Value::Array(arr) = &mut var.value else {
1743 panic!("variable should be an array");
1744 };
1745 let Value::Range(inner) = range else {
1746 unreachable!("range should be a Value::Range");
1747 };
1748 let range = make_range(arr, inner.start, inner.step, inner.end, range_span)?;
1749 for (idx, rhs) in range.into_iter().zip(rhs.iter()) {
1750 if idx < 0 {
1751 return Err(Error::InvalidNegativeInt(idx, range_span));
1752 }
1753 var.value.update_array(idx, rhs.clone(), range_span)?;
1754 }
1755 }
1756 None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
1757 },
1758 _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
1759 }
1760 Ok(())
1761 }
1762
1763 #[allow(clippy::too_many_arguments)]
1764 fn bind_args_for_spec(
1765 &self,
1766 env: &mut Env,
1767 globals: &impl PackageStoreLookup,
1768 decl_pat: PatId,
1769 spec_pat: Option<PatId>,
1770 args_val: Value,
1771 args_span: PackageSpan,
1772 ctl_count: u8,
1773 fixed_args: Option<Rc<[Value]>>,
1774 ) -> Result<(), Error> {
1775 match spec_pat {
1776 Some(spec_pat) => {
1777 assert!(
1778 ctl_count > 0,
1779 "spec pattern tuple used without controlled functor"
1780 );
1781
1782 let mut tup = args_val;
1783 let mut ctls = vec![];
1784 for _ in 0..ctl_count {
1785 let [c, rest] = &*tup.unwrap_tuple() else {
1786 panic!("tuple should be arity 2");
1787 };
1788 ctls.extend_from_slice(&c.clone().unwrap_array());
1789 tup = rest.clone();
1790 }
1791
1792 if !are_ctls_unique(&ctls, &tup) {
1793 return Err(Error::QubitUniqueness(args_span));
1794 }
1795
1796 self.bind_value(env, globals, spec_pat, Value::Array(ctls.into()));
1797 self.bind_value(env, globals, decl_pat, merge_fixed_args(fixed_args, tup));
1798 }
1799 None => self.bind_value(
1800 env,
1801 globals,
1802 decl_pat,
1803 merge_fixed_args(fixed_args, args_val),
1804 ),
1805 }
1806 Ok(())
1807 }
1808
1809 fn to_global_span(&self, span: Span) -> PackageSpan {
1810 PackageSpan {
1811 package: map_fir_package_to_hir(self.package),
1812 span,
1813 }
1814 }
1815
1816 fn counting_call(&mut self, name: &str, arg: Value, span: PackageSpan) -> Result<Value, Error> {
1817 let counting_key = |arg: Value| match arg {
1818 Value::Closure(closure) => make_counting_key(closure.id, closure.functor),
1819 Value::Global(id, functor) => make_counting_key(id, functor),
1820 _ => panic!("value should be callable"),
1821 };
1822 match name {
1823 "StartCountingOperation" | "StartCountingFunction" => {
1824 if self.call_counts.insert(counting_key(arg), 0).is_some() {
1825 Err(Error::CallableAlreadyCounted(span))
1826 } else {
1827 Ok(Value::unit())
1828 }
1829 }
1830 "StopCountingOperation" | "StopCountingFunction" => {
1831 if let Some(count) = self.call_counts.remove(&counting_key(arg)) {
1832 Ok(Value::Int(count))
1833 } else {
1834 Err(Error::CallableNotCounted(span))
1835 }
1836 }
1837 "StartCountingQubits" => {
1838 if self
1839 .qubit_counter
1840 .replace(QubitCounter::default())
1841 .is_some()
1842 {
1843 Err(Error::QubitsAlreadyCounted(span))
1844 } else {
1845 Ok(Value::unit())
1846 }
1847 }
1848 "StopCountingQubits" => {
1849 if let Some(qubit_counter) = self.qubit_counter.take() {
1850 Ok(Value::Int(qubit_counter.into_count()))
1851 } else {
1852 Err(Error::QubitsNotCounted(span))
1853 }
1854 }
1855 _ => panic!("unknown counting call"),
1856 }
1857 }
1858
1859 fn increment_call_count(&mut self, callee_id: StoreItemId, functor: FunctorApp) {
1860 if let Some(count) = self
1861 .call_counts
1862 .get_mut(&make_counting_key(callee_id, functor))
1863 {
1864 *count += 1;
1865 }
1866 }
1867}
1868
1869pub fn are_ctls_unique(ctls: &[Value], tup: &Value) -> bool {
1870 let mut qubits = FxHashSet::default();
1871 for ctl in ctls.iter().flat_map(Value::qubits) {
1872 if let Some(ctl) = ctl.try_deref()
1873 && !qubits.insert(ctl)
1874 {
1875 return false;
1876 }
1877 }
1878 for qubit in tup.qubits() {
1879 if let Some(qubit) = qubit.try_deref()
1880 && qubits.contains(&qubit)
1881 {
1882 return false;
1883 }
1884 }
1885 true
1886}
1887
1888fn merge_fixed_args(fixed_args: Option<Rc<[Value]>>, arg: Value) -> Value {
1889 if let Some(fixed_args) = fixed_args {
1890 Value::Tuple(
1891 fixed_args.iter().cloned().chain(iter::once(arg)).collect(),
1892 None,
1893 )
1894 } else {
1895 arg
1896 }
1897}
1898
1899fn resolve_binding(env: &Env, package: PackageId, res: Res, span: Span) -> Result<Value, Error> {
1900 Ok(match res {
1901 Res::Err => panic!("resolution error"),
1902 Res::Item(item) => Value::Global(
1903 StoreItemId {
1904 package: item.package,
1905 item: item.item,
1906 },
1907 FunctorApp::default(),
1908 ),
1909 Res::Local(id) => env
1910 .get(id)
1911 .ok_or(Error::UnboundName(PackageSpan {
1912 package: map_fir_package_to_hir(package),
1913 span,
1914 }))?
1915 .value
1916 .clone(),
1917 })
1918}
1919
1920fn spec_from_functor_app(functor: FunctorApp) -> Spec {
1921 match (functor.adjoint, functor.controlled) {
1922 (false, 0) => Spec::Body,
1923 (true, 0) => Spec::Adj,
1924 (false, _) => Spec::Ctl,
1925 (true, _) => Spec::CtlAdj,
1926 }
1927}
1928
1929pub fn resolve_closure(
1930 env: &Env,
1931 package: PackageId,
1932 span: Span,
1933 args: &[LocalVarId],
1934 callable: LocalItemId,
1935) -> Result<Value, Error> {
1936 let args: Option<_> = args
1937 .iter()
1938 .map(|&arg| Some(env.get(arg)?.value.clone()))
1939 .collect();
1940 let args: Vec<_> = args.ok_or(Error::UnboundName(PackageSpan {
1941 package: map_fir_package_to_hir(package),
1942 span,
1943 }))?;
1944 let callable = StoreItemId {
1945 package,
1946 item: callable,
1947 };
1948 Ok(Value::Closure(
1949 val::Closure {
1950 fixed_args: args.into(),
1951 id: callable,
1952 functor: FunctorApp::default(),
1953 }
1954 .into(),
1955 ))
1956}
1957
1958fn lit_to_val(lit: &Lit) -> Value {
1959 match lit {
1960 Lit::BigInt(v) => Value::BigInt(v.clone()),
1961 Lit::Bool(v) => Value::Bool(*v),
1962 Lit::Double(v) => Value::Double(*v),
1963 Lit::Int(v) => Value::Int(*v),
1964 Lit::Pauli(v) => Value::Pauli(*v),
1965 Lit::Result(fir::Result::Zero) => Value::RESULT_ZERO,
1966 Lit::Result(fir::Result::One) => Value::RESULT_ONE,
1967 }
1968}
1969
1970fn eval_binop_eq(
1971 lhs_val: Value,
1972 rhs_val: Value,
1973 lhs_span: PackageSpan,
1974 rhs_span: PackageSpan,
1975) -> Result<Value, Error> {
1976 match (lhs_val, rhs_val) {
1977 (Value::Result(val::Result::Id(_)), _) => {
1978 // Comparison of result ids is nonsensical, so we prevent it.
1979 // This code path is reachable when using the circuit builder backend
1980 // since we don't currently do runtime capability analysis
1981 // to prevent executing programs that do result comparisons.
1982 Err(Error::ResultComparisonUnsupported(lhs_span))
1983 }
1984 (Value::Result(val::Result::Loss), _) => {
1985 // Loss is not comparable and should be checked ahead of time, so treat this as a runtime
1986 // failure.
1987 Err(Error::ResultLossComparisonUnsupported(lhs_span))
1988 }
1989 (_, Value::Result(val::Result::Id(_))) => {
1990 // Comparison of result ids is nonsensical, so we prevent it.
1991 // This code path is reachable when using the circuit builder backend
1992 // since we don't currently do runtime capability analysis
1993 // to prevent executing programs that do result comparisons.
1994 Err(Error::ResultComparisonUnsupported(rhs_span))
1995 }
1996 (_, Value::Result(val::Result::Loss)) => {
1997 // Loss is not comparable and should be checked ahead of time, so treat this as a runtime
1998 // failure.
1999 Err(Error::ResultLossComparisonUnsupported(rhs_span))
2000 }
2001 (lhs, rhs) => Ok(Value::Bool(lhs == rhs)),
2002 }
2003}
2004
2005fn eval_binop_neq(
2006 lhs_val: Value,
2007 rhs_val: Value,
2008 lhs_span: PackageSpan,
2009 rhs_span: PackageSpan,
2010) -> Result<Value, Error> {
2011 match (lhs_val, rhs_val) {
2012 (Value::Result(val::Result::Id(_)), _) => {
2013 // Comparison of result ids is nonsensical, so we prevent it.
2014 // This code path is reachable when using the circuit builder backend
2015 // since we don't currently do runtime capability analysis
2016 // to prevent executing programs that do result comparisons.
2017 Err(Error::ResultComparisonUnsupported(lhs_span))
2018 }
2019 (Value::Result(val::Result::Loss), _) => {
2020 // Loss is not comparable and should be checked ahead of time, so treat this as a runtime
2021 // failure.
2022 Err(Error::ResultLossComparisonUnsupported(lhs_span))
2023 }
2024 (_, Value::Result(val::Result::Id(_))) => {
2025 // Comparison of result ids is nonsensical, so we prevent it.
2026 // This code path is reachable when using the circuit builder backend
2027 // since we don't currently do runtime capability analysis
2028 // to prevent executing programs that do result comparisons.
2029 Err(Error::ResultComparisonUnsupported(rhs_span))
2030 }
2031 (_, Value::Result(val::Result::Loss)) => {
2032 // Loss is not comparable and should be checked ahead of time, so treat this as a runtime
2033 // failure.
2034 Err(Error::ResultLossComparisonUnsupported(rhs_span))
2035 }
2036
2037 (lhs, rhs) => Ok(Value::Bool(lhs != rhs)),
2038 }
2039}
2040
2041fn eval_binop_add(lhs_val: Value, rhs_val: Value) -> Value {
2042 match lhs_val {
2043 Value::Array(arr) => {
2044 let rhs_arr = rhs_val.unwrap_array();
2045 let items: Vec<_> = arr.iter().cloned().chain(rhs_arr.iter().cloned()).collect();
2046 Value::Array(items.into())
2047 }
2048 Value::BigInt(val) => {
2049 let rhs = rhs_val.unwrap_big_int();
2050 Value::BigInt(val + rhs)
2051 }
2052 Value::Double(val) => {
2053 match &rhs_val {
2054 Value::Double(v) => Value::Double(val + v),
2055 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2056 // Special case for adding a double and a complex literal.
2057 let [real, imag] = array::from_fn(|i| v[i].clone());
2058 let real = real.unwrap_double();
2059 let imag = imag.unwrap_double();
2060 Value::Tuple(
2061 vec![Value::Double(val + real), Value::Double(imag)].into(),
2062 Some(Rc::clone(id)),
2063 )
2064 }
2065 _ => panic!("value is not addable: {}", rhs_val.type_name()),
2066 }
2067 }
2068 Value::Int(val) => {
2069 let rhs = rhs_val.unwrap_int();
2070 Value::Int(val.wrapping_add(rhs))
2071 }
2072 Value::String(val) => {
2073 let rhs = rhs_val.unwrap_string();
2074 Value::String((val.to_string() + &rhs).into())
2075 }
2076 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2077 let [real, imag] = array::from_fn(|i| v[i].clone());
2078 let real = real.unwrap_double();
2079 let imag = imag.unwrap_double();
2080 match &rhs_val {
2081 // Special case for adding a complex literal and a double.
2082 Value::Double(v) => Value::Tuple(
2083 vec![Value::Double(real + v), Value::Double(imag)].into(),
2084 Some(Rc::clone(&id)),
2085 ),
2086 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2087 let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone());
2088 let rhs_real = rhs_real.unwrap_double();
2089 let rhs_imag = rhs_imag.unwrap_double();
2090 Value::Tuple(
2091 vec![
2092 Value::Double(real + rhs_real),
2093 Value::Double(imag + rhs_imag),
2094 ]
2095 .into(),
2096 Some(Rc::clone(id)),
2097 )
2098 }
2099 _ => panic!("value is not addable: {}", rhs_val.type_name()),
2100 }
2101 }
2102 _ => panic!("value is not addable: {}", lhs_val.type_name()),
2103 }
2104}
2105
2106fn eval_binop_andb(lhs_val: Value, rhs_val: Value) -> Value {
2107 match lhs_val {
2108 Value::BigInt(val) => {
2109 let rhs = rhs_val.unwrap_big_int();
2110 Value::BigInt(val & rhs)
2111 }
2112 Value::Int(val) => {
2113 let rhs = rhs_val.unwrap_int();
2114 Value::Int(val & rhs)
2115 }
2116 _ => panic!("value type does not support andb"),
2117 }
2118}
2119
2120fn eval_binop_div(
2121 lhs_val: Value,
2122 rhs_val: Value,
2123 _: PackageSpan,
2124 rhs_span: PackageSpan,
2125) -> Result<Value, Error> {
2126 match lhs_val {
2127 Value::BigInt(val) => {
2128 let rhs = rhs_val.unwrap_big_int();
2129 if rhs == BigInt::from(0) {
2130 Err(Error::DivZero(rhs_span))
2131 } else {
2132 Ok(Value::BigInt(val / rhs))
2133 }
2134 }
2135 Value::Int(val) => {
2136 let rhs = rhs_val.unwrap_int();
2137 if rhs == 0 {
2138 Err(Error::DivZero(rhs_span))
2139 } else {
2140 Ok(Value::Int(val.wrapping_div(rhs)))
2141 }
2142 }
2143 Value::Double(val) => {
2144 let rhs = rhs_val.unwrap_double();
2145 Ok(Value::Double(val / rhs))
2146 }
2147 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2148 let [real, imag] = array::from_fn(|i| v[i].clone());
2149 let real = real.unwrap_double();
2150 let imag = imag.unwrap_double();
2151 match rhs_val {
2152 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2153 let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone());
2154 let rhs_real = rhs_real.unwrap_double();
2155 let rhs_imag = rhs_imag.unwrap_double();
2156 let denom = rhs_real * rhs_real + rhs_imag * rhs_imag;
2157 if denom == 0.0 {
2158 Err(Error::DivZero(rhs_span))
2159 } else {
2160 Ok(Value::Tuple(
2161 vec![
2162 Value::Double((real * rhs_real + imag * rhs_imag) / denom),
2163 Value::Double((imag * rhs_real - real * rhs_imag) / denom),
2164 ]
2165 .into(),
2166 Some(Rc::clone(&id)),
2167 ))
2168 }
2169 }
2170 _ => panic!("value should support div"),
2171 }
2172 }
2173 _ => panic!("value should support div"),
2174 }
2175}
2176
2177fn eval_binop_exp(
2178 lhs_val: Value,
2179 rhs_val: Value,
2180 _: PackageSpan,
2181 rhs_span: PackageSpan,
2182) -> Result<Value, Error> {
2183 match lhs_val {
2184 Value::BigInt(val) => {
2185 let rhs_val = rhs_val.unwrap_int();
2186 if rhs_val < 0 {
2187 Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
2188 } else {
2189 let rhs_val: u32 = match rhs_val.try_into() {
2190 Ok(v) => Ok(v),
2191 Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
2192 }?;
2193 Ok(Value::BigInt(val.pow(rhs_val)))
2194 }
2195 }
2196 Value::Double(val) => Ok(Value::Double(val.powf(rhs_val.unwrap_double()))),
2197 Value::Int(val) => {
2198 let rhs_val = rhs_val.unwrap_int();
2199 if rhs_val < 0 {
2200 Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
2201 } else {
2202 let result: i64 = match rhs_val.try_into() {
2203 Ok(v) => val
2204 .checked_pow(v)
2205 .ok_or(Error::IntTooLarge(rhs_val, rhs_span)),
2206 Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
2207 }?;
2208 Ok(Value::Int(result))
2209 }
2210 }
2211 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2212 let [real, imag] = array::from_fn(|i| v[i].clone());
2213 let real = real.unwrap_double();
2214 let imag = imag.unwrap_double();
2215 match rhs_val {
2216 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2217 let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone());
2218 let rhs_real = rhs_real.unwrap_double();
2219 let rhs_imag = rhs_imag.unwrap_double();
2220 // (a + bi)^(c + di) = exp((c + di) * log(a + bi))
2221 let log_re = 0.5 * (real * real + imag * imag).ln();
2222 let log_im = imag.atan2(real);
2223 let exp_re = (rhs_real * log_re - rhs_imag * log_im).exp();
2224 let exp_im = rhs_real * log_im + rhs_imag * log_re;
2225 Ok(Value::Tuple(
2226 vec![
2227 Value::Double(exp_re * exp_im.cos()),
2228 Value::Double(exp_re * exp_im.sin()),
2229 ]
2230 .into(),
2231 Some(Rc::clone(&id)),
2232 ))
2233 }
2234 _ => panic!("value should support exp"),
2235 }
2236 }
2237 _ => panic!("value should support exp"),
2238 }
2239}
2240
2241fn eval_binop_gt(lhs_val: Value, rhs_val: Value) -> Value {
2242 match lhs_val {
2243 Value::BigInt(val) => {
2244 let rhs = rhs_val.unwrap_big_int();
2245 Value::Bool(val > rhs)
2246 }
2247 Value::Int(val) => {
2248 let rhs = rhs_val.unwrap_int();
2249 Value::Bool(val > rhs)
2250 }
2251 Value::Double(val) => {
2252 let rhs = rhs_val.unwrap_double();
2253 Value::Bool(val > rhs)
2254 }
2255 _ => panic!("value doesn't support binop gt"),
2256 }
2257}
2258
2259fn eval_binop_gte(lhs_val: Value, rhs_val: Value) -> Value {
2260 match lhs_val {
2261 Value::BigInt(val) => {
2262 let rhs = rhs_val.unwrap_big_int();
2263 Value::Bool(val >= rhs)
2264 }
2265 Value::Int(val) => {
2266 let rhs = rhs_val.unwrap_int();
2267 Value::Bool(val >= rhs)
2268 }
2269 Value::Double(val) => {
2270 let rhs = rhs_val.unwrap_double();
2271 Value::Bool(val >= rhs)
2272 }
2273 _ => panic!("value doesn't support binop gte"),
2274 }
2275}
2276
2277fn eval_binop_lt(lhs_val: Value, rhs_val: Value) -> Value {
2278 match lhs_val {
2279 Value::BigInt(val) => {
2280 let rhs = rhs_val.unwrap_big_int();
2281 Value::Bool(val < rhs)
2282 }
2283 Value::Int(val) => {
2284 let rhs = rhs_val.unwrap_int();
2285 Value::Bool(val < rhs)
2286 }
2287 Value::Double(val) => {
2288 let rhs = rhs_val.unwrap_double();
2289 Value::Bool(val < rhs)
2290 }
2291 _ => panic!("value doesn't support binop lt"),
2292 }
2293}
2294
2295fn eval_binop_lte(lhs_val: Value, rhs_val: Value) -> Value {
2296 match lhs_val {
2297 Value::BigInt(val) => {
2298 let rhs = rhs_val.unwrap_big_int();
2299 Value::Bool(val <= rhs)
2300 }
2301 Value::Int(val) => {
2302 let rhs = rhs_val.unwrap_int();
2303 Value::Bool(val <= rhs)
2304 }
2305 Value::Double(val) => {
2306 let rhs = rhs_val.unwrap_double();
2307 Value::Bool(val <= rhs)
2308 }
2309 _ => panic!("value doesn't support binop lte"),
2310 }
2311}
2312
2313fn eval_binop_mod(
2314 lhs_val: Value,
2315 rhs_val: Value,
2316 _: PackageSpan,
2317 rhs_span: PackageSpan,
2318) -> Result<Value, Error> {
2319 match lhs_val {
2320 Value::BigInt(val) => {
2321 let rhs = rhs_val.unwrap_big_int();
2322 if rhs == BigInt::from(0) {
2323 Err(Error::DivZero(rhs_span))
2324 } else {
2325 Ok(Value::BigInt(val % rhs))
2326 }
2327 }
2328 Value::Int(val) => {
2329 let rhs = rhs_val.unwrap_int();
2330 if rhs == 0 {
2331 Err(Error::DivZero(rhs_span))
2332 } else {
2333 Ok(Value::Int(val.wrapping_rem(rhs)))
2334 }
2335 }
2336 Value::Double(val) => {
2337 let rhs = rhs_val.unwrap_double();
2338 if rhs == 0.0 {
2339 Err(Error::DivZero(rhs_span))
2340 } else {
2341 Ok(Value::Double(val % rhs))
2342 }
2343 }
2344 _ => panic!("value should support mod"),
2345 }
2346}
2347
2348fn eval_binop_mul(lhs_val: Value, rhs_val: Value) -> Value {
2349 match lhs_val {
2350 Value::BigInt(val) => {
2351 let rhs = rhs_val.unwrap_big_int();
2352 Value::BigInt(val * rhs)
2353 }
2354 Value::Int(val) => {
2355 let rhs = rhs_val.unwrap_int();
2356 Value::Int(val.wrapping_mul(rhs))
2357 }
2358 Value::Double(val) => {
2359 let rhs = rhs_val.unwrap_double();
2360 Value::Double(val * rhs)
2361 }
2362 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2363 // Special case for multiplying complex literals.
2364 let [real, imag] = array::from_fn(|i| v[i].clone());
2365 let real = real.unwrap_double();
2366 let imag = imag.unwrap_double();
2367 match &rhs_val {
2368 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2369 let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone());
2370 let rhs_real = rhs_real.unwrap_double();
2371 let rhs_imag = rhs_imag.unwrap_double();
2372 Value::Tuple(
2373 vec![
2374 Value::Double(real * rhs_real - imag * rhs_imag),
2375 Value::Double(real * rhs_imag + imag * rhs_real),
2376 ]
2377 .into(),
2378 Some(Rc::clone(id)),
2379 )
2380 }
2381 _ => panic!("value is not multipliable: {}", rhs_val.type_name()),
2382 }
2383 }
2384 _ => panic!("value should support mul"),
2385 }
2386}
2387
2388fn eval_binop_orb(lhs_val: Value, rhs_val: Value) -> Value {
2389 match lhs_val {
2390 Value::BigInt(val) => {
2391 let rhs = rhs_val.unwrap_big_int();
2392 Value::BigInt(val | rhs)
2393 }
2394 Value::Int(val) => {
2395 let rhs = rhs_val.unwrap_int();
2396 Value::Int(val | rhs)
2397 }
2398 _ => panic!("value type does not support orb"),
2399 }
2400}
2401
2402fn eval_binop_shl(
2403 lhs_val: Value,
2404 rhs_val: Value,
2405 _: PackageSpan,
2406 rhs_span: PackageSpan,
2407) -> Result<Value, Error> {
2408 Ok(match lhs_val {
2409 Value::BigInt(val) => {
2410 let rhs = rhs_val.unwrap_int();
2411 if rhs > 0 {
2412 Value::BigInt(val << rhs)
2413 } else {
2414 Value::BigInt(val >> rhs.abs())
2415 }
2416 }
2417 Value::Int(val) => {
2418 let rhs = rhs_val.unwrap_int();
2419 Value::Int(if rhs > 0 {
2420 let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
2421 val.checked_shl(shift)
2422 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
2423 } else {
2424 let shift: u32 = rhs
2425 .checked_neg()
2426 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
2427 .try_into()
2428 .or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
2429 val.checked_shr(shift)
2430 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
2431 })
2432 }
2433 _ => panic!("value should support shl"),
2434 })
2435}
2436
2437fn eval_binop_shr(
2438 lhs_val: Value,
2439 rhs_val: Value,
2440 _: PackageSpan,
2441 rhs_span: PackageSpan,
2442) -> Result<Value, Error> {
2443 Ok(match lhs_val {
2444 Value::BigInt(val) => {
2445 let rhs = rhs_val.unwrap_int();
2446 if rhs > 0 {
2447 Value::BigInt(val >> rhs)
2448 } else {
2449 Value::BigInt(val << rhs.abs())
2450 }
2451 }
2452 Value::Int(val) => {
2453 let rhs = rhs_val.unwrap_int();
2454 Value::Int(if rhs > 0 {
2455 let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
2456 val.checked_shr(shift)
2457 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
2458 } else {
2459 let shift: u32 = rhs
2460 .checked_neg()
2461 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
2462 .try_into()
2463 .or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
2464 val.checked_shl(shift)
2465 .ok_or(Error::IntTooLarge(rhs, rhs_span))?
2466 })
2467 }
2468 _ => panic!("value should support shr"),
2469 })
2470}
2471
2472fn eval_binop_sub(lhs_val: Value, rhs_val: Value) -> Value {
2473 match lhs_val {
2474 Value::BigInt(val) => {
2475 let rhs = rhs_val.unwrap_big_int();
2476 Value::BigInt(val - rhs)
2477 }
2478 Value::Double(val) => {
2479 match &rhs_val {
2480 Value::Double(v) => Value::Double(val - v),
2481 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2482 // Special case for subtracting a complex literal from a double.
2483 let [real, imag] = array::from_fn(|i| v[i].clone());
2484 let real = real.unwrap_double();
2485 let imag = imag.unwrap_double();
2486 Value::Tuple(
2487 vec![Value::Double(val - real), Value::Double(-imag)].into(),
2488 Some(Rc::clone(id)),
2489 )
2490 }
2491 _ => panic!("value is not subtractable: {}", rhs_val.type_name()),
2492 }
2493 }
2494 Value::Int(val) => {
2495 let rhs = rhs_val.unwrap_int();
2496 Value::Int(val.wrapping_sub(rhs))
2497 }
2498 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2499 let [real, imag] = array::from_fn(|i| v[i].clone());
2500 let real = real.unwrap_double();
2501 let imag = imag.unwrap_double();
2502 match &rhs_val {
2503 // Special case for subtracting a double from a complex literal.
2504 Value::Double(v) => Value::Tuple(
2505 vec![Value::Double(real - v), Value::Double(imag)].into(),
2506 Some(Rc::clone(&id)),
2507 ),
2508 Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => {
2509 let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone());
2510 let rhs_real = rhs_real.unwrap_double();
2511 let rhs_imag = rhs_imag.unwrap_double();
2512 Value::Tuple(
2513 vec![
2514 Value::Double(real - rhs_real),
2515 Value::Double(imag - rhs_imag),
2516 ]
2517 .into(),
2518 Some(Rc::clone(id)),
2519 )
2520 }
2521 _ => panic!("value is not subtractable: {}", rhs_val.type_name()),
2522 }
2523 }
2524 _ => panic!("value is not subtractable"),
2525 }
2526}
2527
2528fn eval_binop_xorb(lhs_val: Value, rhs_val: Value) -> Value {
2529 match lhs_val {
2530 Value::BigInt(val) => {
2531 let rhs = rhs_val.unwrap_big_int();
2532 Value::BigInt(val ^ rhs)
2533 }
2534 Value::Int(val) => {
2535 let rhs = rhs_val.unwrap_int();
2536 Value::Int(val ^ rhs)
2537 }
2538 _ => panic!("value type does not support xorb"),
2539 }
2540}
2541
2542fn follow_field_path(mut value: Value, path: &[usize]) -> Option<Value> {
2543 for &index in path {
2544 let Value::Tuple(items, _) = value else {
2545 return None;
2546 };
2547 value = items[index].clone();
2548 }
2549 Some(value)
2550}
2551
2552fn update_field_path(record: &Value, path: &[usize], replace: &Value) -> Option<Value> {
2553 match (record, path) {
2554 (_, []) => Some(replace.clone()),
2555 (Value::Tuple(items, store_item_id), &[next_index, ..]) if next_index < items.len() => {
2556 let update = |(index, item)| {
2557 if index == next_index {
2558 update_field_path(item, &path[1..], replace)
2559 } else {
2560 Some(item.clone())
2561 }
2562 };
2563
2564 let items: Option<_> = items.iter().enumerate().map(update).collect();
2565 Some(Value::Tuple(items?, store_item_id.clone()))
2566 }
2567 _ => None,
2568 }
2569}
2570
2571fn is_updatable_in_place(env: &Env, expr: &Expr) -> (bool, bool) {
2572 match &expr.kind {
2573 ExprKind::Var(Res::Local(id), _) => match env.get(*id) {
2574 Some(var) => match &var.value {
2575 Value::Array(var) => (true, Rc::weak_count(var) + Rc::strong_count(var) == 1),
2576 _ => (false, false),
2577 },
2578 _ => (false, false),
2579 },
2580 _ => (false, false),
2581 }
2582}
2583
2584fn is_counting_call(name: &str) -> bool {
2585 matches!(
2586 name,
2587 "StartCountingOperation"
2588 | "StopCountingOperation"
2589 | "StartCountingFunction"
2590 | "StopCountingFunction"
2591 | "StartCountingQubits"
2592 | "StopCountingQubits"
2593 )
2594}
2595
2596fn make_counting_key(id: StoreItemId, functor: FunctorApp) -> CallableCountKey {
2597 (id, functor.adjoint, functor.controlled > 0)
2598}
2599
2600#[derive(Default)]
2601struct QubitCounter {
2602 seen: FxHashSet<usize>,
2603 count: i64,
2604}
2605
2606impl QubitCounter {
2607 fn allocated(&mut self, qubit: usize) {
2608 if self.seen.insert(qubit) {
2609 self.count += 1;
2610 }
2611 }
2612
2613 fn into_count(self) -> i64 {
2614 self.count
2615 }
2616}
2617