GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
b1b391e95f06be200f32aaae59680ecb856cfcba

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

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