GitVita
New repositoryImport repositoryNew issue
Your repositories Your dashboard Sign in

microsoft/qdk

Public

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

Watch0Fork0Star0
CodeCommitsIssuesPull requestsActionsInsightsSecurity
alex/pythontelem

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

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