GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
v1.16.0

Branches

Tags

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

Clone

HTTPS

Download ZIP

qdk/compiler/qsc_eval/src

compiler/qsc_eval/src/lib.rs

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