GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

mirrored fromhttps://github.com/microsoft/qdkAvailable

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
iadavis/qiskit2-explore

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

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