GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
copilot/fix-2145

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

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