GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
v1.28.0

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

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