GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/bounds

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

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