// Copyright (c) Microsoft Corporation. // Licensed under the MIT License. //! The Q# evaluator handles the execution of Q# programs and/or fragments. //! It operates based on vectors of `ExecGraphNode` instances, which act as a control flow graph //! and are generated by lowering to FIR. The evaluator will iterate through the given graph, //! executing the instructions it encounters and updating the state it was given accordingly, and using //! the FIR store to look up graphs for any called functions or operations. The evaluator handles tracking //! of stack frames and push/pop of variable scopes, and uses the index into the current execution graph //! as a kind of stack pointer, updating the index based on `Jump`, `JumpIf`, and `JumpIfNot` instructions. //! //! Of note, the evaluator does not own the program state, which is tracked by the passed in `Env` //! and `Backend` instances. This allows the evaluator to be reentrant, and supports both whole-program, //! effectively stateless execution (like running shots of a program) stateful execution scenarios //! (like debugging or notebooks). #[cfg(test)] mod tests; pub mod backend; pub mod debug; mod error; pub mod intrinsic; pub mod noise; pub mod output; pub mod state; pub mod val; use crate::backend::{Backend, TracingBackend}; use crate::val::{ Value, index_array, make_range, slice_array, update_index_range, update_index_single, }; use core::panic; use debug::{CallStack, Frame}; pub use error::PackageSpan; use miette::Diagnostic; use num_bigint::BigInt; use output::Receiver; use qsc_data_structures::{functors::FunctorApp, index_map::IndexMap, span::Span}; use qsc_fir::fir::{ self, BinOp, BlockId, CallableImpl, ConfiguredExecGraph, ExecGraph, ExecGraphConfig, ExecGraphDebugNode, ExecGraphNode, Expr, ExprId, ExprKind, Field, FieldAssign, Global, Lit, LocalItemId, LocalVarId, PackageId, PackageStoreLookup, PatId, PatKind, PrimField, Res, StmtId, StoreItemId, StringComponent, UnOp, }; use qsc_fir::ty::Ty; use qsc_lowerer::map_fir_package_to_hir; use rand::{SeedableRng, rngs::StdRng}; use rustc_hash::{FxHashMap, FxHashSet}; use std::array; use std::{ cell::RefCell, fmt::{self, Display, Formatter}, iter, ops::Neg, rc::Rc, }; use thiserror::Error; use val::{Qubit, update_functor_app}; #[derive(Clone, Debug, Diagnostic, Error)] pub enum Error { #[error("array too large")] #[diagnostic(code("Qsc.Eval.ArrayTooLarge"))] ArrayTooLarge(#[label("this array has too many items")] PackageSpan), #[error("callable already counted")] #[diagnostic(help( "counting for a given callable must be stopped before it can be started again" ))] #[diagnostic(code("Qsc.Eval.CallableAlreadyCounted"))] CallableAlreadyCounted(#[label] PackageSpan), #[error("callable not counted")] #[diagnostic(help("counting for a given callable must be started before it can be stopped"))] #[diagnostic(code("Qsc.Eval.CallableNotCounted"))] CallableNotCounted(#[label] PackageSpan), #[error("invalid array length: {0}")] #[diagnostic(code("Qsc.Eval.InvalidArrayLength"))] InvalidArrayLength(i64, #[label("cannot be used as a length")] PackageSpan), #[error("division by zero")] #[diagnostic(code("Qsc.Eval.DivZero"))] DivZero(#[label("cannot divide by zero")] PackageSpan), #[error("empty range")] #[diagnostic(code("Qsc.Eval.EmptyRange"))] EmptyRange(#[label("the range cannot be empty")] PackageSpan), #[error("value cannot be used as an index: {0}")] #[diagnostic(code("Qsc.Eval.InvalidIndex"))] InvalidIndex(i64, #[label("invalid index")] PackageSpan), #[error("integer too large for operation")] #[diagnostic(code("Qsc.Eval.IntTooLarge"))] IntTooLarge(i64, #[label("this value is too large")] PackageSpan), #[error("index out of range: {0}")] #[diagnostic(code("Qsc.Eval.IndexOutOfRange"))] IndexOutOfRange(i64, #[label("out of range")] PackageSpan), #[error("intrinsic callable `{0}` failed: {1}")] #[diagnostic(code("Qsc.Eval.IntrinsicFail"))] IntrinsicFail(String, String, #[label] PackageSpan), #[error("invalid rotation angle: {0}")] #[diagnostic(code("Qsc.Eval.InvalidRotationAngle"))] InvalidRotationAngle(f64, #[label("invalid rotation angle")] PackageSpan), #[error("negative integers cannot be used here: {0}")] #[diagnostic(code("Qsc.Eval.InvalidNegativeInt"))] InvalidNegativeInt(i64, #[label("invalid negative integer")] PackageSpan), #[error("output failure")] #[diagnostic(code("Qsc.Eval.OutputFail"))] OutputFail(#[label("failed to generate output")] PackageSpan), #[error("qubits in invocation are not unique")] #[diagnostic(code("Qsc.Eval.QubitUniqueness"))] QubitUniqueness(#[label] PackageSpan), #[error("qubit used after release")] #[diagnostic(help( "qubits should not be used after being released, which typically occurs when a qubit is used after it has gone out of scope" ))] #[diagnostic(code("Qsc.Eval.QubitUsedAfterRelease"))] QubitUsedAfterRelease(#[label] PackageSpan), #[error("qubit double release")] #[diagnostic(code("Qsc.Eval.QubitDoubleRelease"))] QubitDoubleRelease(#[label("qubit has already been released")] PackageSpan), #[error("qubits already counted")] #[diagnostic(help("counting for qubits must be stopped before it can be started again"))] #[diagnostic(code("Qsc.Eval.QubitsAlreadyCounted"))] QubitsAlreadyCounted(#[label] PackageSpan), #[error("qubits not counted")] #[diagnostic(help("counting for qubits must be started before it can be stopped"))] #[diagnostic(code("Qsc.Eval.QubitsNotCounted"))] QubitsNotCounted(#[label] PackageSpan), #[error("qubits are not separable")] #[diagnostic(help( "subset of qubits provided as arguments must not be entangled with any qubits outside of the subset" ))] #[diagnostic(code("Qsc.Eval.QubitsNotSeparable"))] QubitsNotSeparable(#[label] PackageSpan), #[error("range with step size of zero")] #[diagnostic(code("Qsc.Eval.RangeStepZero"))] RangeStepZero(#[label("invalid range")] PackageSpan), #[error("qubit arrays used in relabeling must be a permutation of the same set of qubits")] #[diagnostic(help("ensure that each qubit is present exactly once in both arrays"))] #[diagnostic(code("Qsc.Eval.RelabelingMismatch"))] RelabelingMismatch(#[label] PackageSpan), #[error("Qubit{0} released while not in |0⟩ state")] #[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" ))] #[diagnostic(code("Qsc.Eval.ReleasedQubitNotZero"))] ReleasedQubitNotZero(usize, #[label("Qubit{0}")] PackageSpan), #[error("cannot compare measurement results")] #[diagnostic(code("Qsc.Eval.ResultComparisonUnsupported"))] #[diagnostic(help( "comparing measurement results is not supported when performing circuit synthesis or base profile QIR generation" ))] ResultComparisonUnsupported(#[label("cannot compare to result")] PackageSpan), #[error("cannot compare measurement result from qubit loss")] #[diagnostic(code("Qsc.Eval.ResultLossComparisonUnsupported"))] #[diagnostic(help( "use of a measurement result from a qubit that was lost is not supported, use `IsLossResult` to ensure the result is valid before using it in a comparison" ))] ResultLossComparisonUnsupported(#[label("cannot compare result from qubit loss")] PackageSpan), #[error("simulation error: {0}")] #[diagnostic(code("Qsc.Eval.SimulationError"))] SimulationError(String, #[label("simulation error")] PackageSpan), #[error("name is not bound")] #[diagnostic(code("Qsc.Eval.UnboundName"))] UnboundName(#[label] PackageSpan), #[error("unknown intrinsic `{0}`")] #[diagnostic(code("Qsc.Eval.UnknownIntrinsic"))] UnknownIntrinsic( String, #[label("callable has no implementation")] PackageSpan, ), #[error("unsupported return type for intrinsic `{0}`")] #[diagnostic(help("intrinsic callable return type should be `Unit`"))] #[diagnostic(code("Qsc.Eval.UnsupportedIntrinsicType"))] UnsupportedIntrinsicType(String, #[label] PackageSpan), #[error("program failed: {0}")] #[diagnostic(code("Qsc.Eval.UserFail"))] UserFail(String, #[label("explicit fail")] PackageSpan), } impl Error { #[must_use] pub fn span(&self) -> &PackageSpan { match self { Error::ArrayTooLarge(span) | Error::CallableAlreadyCounted(span) | Error::CallableNotCounted(span) | Error::DivZero(span) | Error::EmptyRange(span) | Error::IndexOutOfRange(_, span) | Error::InvalidIndex(_, span) | Error::IntrinsicFail(_, _, span) | Error::IntTooLarge(_, span) | Error::InvalidRotationAngle(_, span) | Error::InvalidNegativeInt(_, span) | Error::OutputFail(span) | Error::QubitUniqueness(span) | Error::QubitUsedAfterRelease(span) | Error::QubitDoubleRelease(span) | Error::QubitsAlreadyCounted(span) | Error::QubitsNotCounted(span) | Error::QubitsNotSeparable(span) | Error::RangeStepZero(span) | Error::RelabelingMismatch(span) | Error::ReleasedQubitNotZero(_, span) | Error::ResultComparisonUnsupported(span) | Error::ResultLossComparisonUnsupported(span) | Error::SimulationError(_, span) | Error::UnboundName(span) | Error::UnknownIntrinsic(_, span) | Error::UnsupportedIntrinsicType(_, span) | Error::UserFail(_, span) | Error::InvalidArrayLength(_, span) => span, } } } /// A specialization that may be implemented for an operation. enum Spec { /// The default specialization. Body, /// The adjoint specialization. Adj, /// The controlled specialization. Ctl, /// The controlled adjoint specialization. CtlAdj, } impl Display for Spec { fn fmt(&self, f: &mut Formatter) -> fmt::Result { match self { Spec::Body => f.write_str("body"), Spec::Adj => f.write_str("adjoint"), Spec::Ctl => f.write_str("controlled"), Spec::CtlAdj => f.write_str("controlled adjoint"), } } } /// Evaluates the given code with the given context. /// # Errors /// Returns the first error encountered during execution. /// # Panics /// On internal error where no result is returned. #[allow(clippy::too_many_arguments)] pub fn eval( package: PackageId, seed: Option, exec_graph: ExecGraph, exec_graph_config: ExecGraphConfig, globals: &impl PackageStoreLookup, env: &mut Env, sim: &mut TracingBackend<'_, B>, receiver: &mut impl Receiver, ) -> Result)> { let mut state = State::new( package, exec_graph, exec_graph_config, seed, ErrorBehavior::FailOnError, ); let res = state.eval(globals, env, sim, receiver, &[], StepAction::Continue)?; let StepResult::Return(value) = res else { panic!("eval should always return a value"); }; Ok(value) } /// Evaluates the given callable with the given context. /// # Errors /// Returns the first error encountered during execution. /// # Panics /// On internal error where no result is returned. #[allow(clippy::too_many_arguments)] pub fn invoke( package: PackageId, seed: Option, globals: &impl PackageStoreLookup, exec_graph_config: ExecGraphConfig, env: &mut Env, sim: &mut TracingBackend<'_, B>, receiver: &mut impl Receiver, callable: Value, args: Value, ) -> Result)> { let mut state = State::new( package, ExecGraph::default(), exec_graph_config, seed, ErrorBehavior::FailOnError, ); // Push the callable value into the state stack and then the args value so they are ready for evaluation. state.set_val_register(callable); state.push_val(); state.set_val_register(args); // Evaluate the call, which will pop the args and callable values from the stack and then either // a) prepare the call stack for the execution of the callable, or // b) invoke the callable directly if it is an intrinsic. state .eval_call( env, sim, globals, Span::default(), Span::default(), receiver, ) .map_err(|e| (e, state.capture_stack()))?; // Trigger evaluation of the state until the end of the stack is reached and a return value is obtained, which will be the final // result of the invocation. let res = state.eval(globals, env, sim, receiver, &[], StepAction::Continue)?; let StepResult::Return(value) = res else { panic!("eval should always return a value"); }; Ok(value) } /// The type of step action to take during evaluation #[derive(Debug, Copy, Clone, Eq, PartialEq)] pub enum StepAction { Next, In, Out, Continue, } // The result of an evaluation step. #[derive(Clone, Debug)] pub enum StepResult { BreakpointHit(StmtId), Next, StepIn, StepOut, Return(Value), Fail(String), } trait AsIndex { type Output; fn as_index(&self, index_source: PackageSpan) -> Self::Output; } impl AsIndex for i64 { type Output = Result; fn as_index(&self, index_source: PackageSpan) -> Self::Output { match (*self).try_into() { Ok(index) => Ok(index), Err(_) => Err(Error::InvalidIndex(*self, index_source)), } } } #[derive(Debug, Clone)] pub struct Variable { pub name: Rc, pub value: Value, pub span: Span, } #[derive(Debug, Clone)] pub struct VariableInfo { pub value: Value, pub name: Rc, pub type_name: String, pub span: Span, } pub struct Range { step: i64, end: i64, curr: i64, } impl Iterator for Range { type Item = i64; fn next(&mut self) -> Option { let curr = self.curr; self.curr += self.step; if (self.step > 0 && curr <= self.end) || (self.step < 0 && curr >= self.end) { Some(curr) } else { None } } } impl Range { fn new(start: i64, step: i64, end: i64) -> Self { Range { step, end, curr: start, } } } pub struct Env { scopes: Vec, qubits: FxHashSet>, } impl Default for Env { fn default() -> Self { // Always create a global scope for top-level statements. Self { scopes: vec![Scope::default()], qubits: FxHashSet::default(), } } } impl Env { #[must_use] pub fn get(&self, id: LocalVarId) -> Option<&Variable> { self.scopes .iter() .rev() .find_map(|scope| scope.bindings.get(id)) } fn get_mut(&mut self, id: LocalVarId) -> Option<&mut Variable> { self.scopes .iter_mut() .rev() .find_map(|scope| scope.bindings.get_mut(id)) } pub fn push_scope(&mut self, frame_id: usize) { let scope = Scope { frame_id, ..Default::default() }; self.scopes.push(scope); } pub fn push_loop_scope(&mut self, frame_id: usize) { let scope = Scope { frame_id, is_loop: true, ..Default::default() }; self.scopes.push(scope); } #[must_use] pub fn last_scope_is_loop(&self) -> bool { self.scopes.last().is_some_and(|scope| scope.is_loop) } pub fn leave_scope(&mut self) { // Only pop the scope if there is more than one scope in the stack, // because the global/top-level scope cannot be exited. if self.scopes.len() > 1 { self.scopes .pop() .expect("scope should have more than one entry."); } } pub fn leave_current_frame(&mut self) { let current_frame_id = self .scopes .last() .expect("should be at least one scope") .frame_id; if current_frame_id == 0 { // Do not remove the global scope. return; } self.scopes .retain(|scope| scope.frame_id != current_frame_id); } pub fn bind_variable_in_top_frame(&mut self, local_var_id: LocalVarId, var: Variable) { let Some(scope) = self.scopes.last_mut() else { panic!("no frames in scope"); }; scope.bindings.insert(local_var_id, var); } #[must_use] pub fn get_variables_in_top_frame(&self) -> Vec { if let Some(scope) = self.scopes.last() { self.get_variables_in_frame(scope.frame_id) } else { vec![] } } #[must_use] pub fn get_variables_in_frame(&self, frame_id: usize) -> Vec { let candidate_scopes: Vec<_> = self .scopes .iter() .filter(|scope| scope.frame_id == frame_id) .map(|scope| scope.bindings.iter()) .collect(); let variables_by_scope: Vec> = candidate_scopes .into_iter() .map(|bindings| { bindings .map(|(_, var)| VariableInfo { name: var.name.clone(), type_name: var.value.type_name().to_string(), value: var.value.clone(), span: var.span, }) .collect() }) .collect(); variables_by_scope.into_iter().flatten().collect::>() } #[allow(clippy::len_without_is_empty)] #[must_use] pub fn len(&self) -> usize { self.scopes.len() } pub fn update_variable_in_top_frame(&mut self, local_var_id: LocalVarId, value: Value) { let variable = self .get_mut(local_var_id) .expect("local variable is not present"); variable.value = value; } pub fn track_qubit(&mut self, qubit: Rc) { self.qubits.insert(qubit); } pub fn release_qubit(&mut self, qubit: &Rc) { self.qubits.remove(qubit); } } #[derive(Clone, Default)] struct Scope { bindings: IndexMap, frame_id: usize, is_loop: bool, } type CallableCountKey = (StoreItemId, bool, bool); #[derive(Debug, Clone, Copy, Eq, PartialEq)] pub enum ErrorBehavior { /// Fail execution if an error is encountered. FailOnError, /// Stop execution on the first error encountered. StopOnError, } pub struct State { exec_graph_stack: Vec, idx: u32, idx_stack: Vec, val_register: Option, val_stack: Vec>, source_package: PackageId, package: PackageId, call_stack: CallStack, current_span: Span, rng: RefCell, call_counts: FxHashMap, qubit_counter: Option, dirty_qubits: FxHashSet, error_behavior: ErrorBehavior, last_error: Option<(Error, Vec)>, exec_graph_config: ExecGraphConfig, } impl State { #[must_use] pub fn new( package: PackageId, exec_graph: ExecGraph, exec_graph_config: ExecGraphConfig, classical_seed: Option, error_behavior: ErrorBehavior, ) -> Self { let rng = match classical_seed { Some(seed) => RefCell::new(StdRng::seed_from_u64(seed)), None => RefCell::new(StdRng::from_rng(&mut rand::rng())), }; Self { exec_graph_stack: vec![exec_graph.select(exec_graph_config)], idx: 0, idx_stack: Vec::new(), val_register: None, val_stack: vec![Vec::new()], source_package: package, package, call_stack: CallStack::default(), current_span: Span::default(), rng, call_counts: FxHashMap::default(), qubit_counter: None, dirty_qubits: FxHashSet::default(), error_behavior, last_error: None, exec_graph_config, } } fn current_frame_id(&self) -> usize { self.call_stack.len() } fn push_frame( &mut self, exec_graph: ConfiguredExecGraph, id: StoreItemId, functor: FunctorApp, ) { self.call_stack.push_frame(Frame { span: self.current_span, id, caller: self.package, functor, loop_iterations: Vec::new(), }); self.exec_graph_stack.push(exec_graph); self.val_stack.push(Vec::new()); self.idx_stack.push(self.idx); self.idx = 0; self.package = id.package; } fn leave_frame(&mut self) { if let Some(frame) = self.call_stack.pop_frame() { self.package = frame.caller; } self.val_stack.pop(); self.idx = self.idx_stack.pop().unwrap_or_default(); self.exec_graph_stack.pop(); } fn push_scope(&mut self, env: &mut Env) { env.push_scope(self.current_frame_id()); } fn push_loop_scope(&mut self, env: &mut Env, loop_expr: ExprId) { env.push_loop_scope(self.current_frame_id()); self.call_stack.push_loop_iteration(loop_expr); } fn take_val_register(&mut self) -> Value { self.val_register.take().expect("value should be present") } fn set_val_register(&mut self, val: Value) { self.val_register = Some(val); } fn pop_val(&mut self) -> Value { self.val_stack .last_mut() .expect("should have at least one value frame") .pop() .expect("value should be present") } fn pop_vals(&mut self, len: usize) -> Vec { let last = self .val_stack .last_mut() .expect("should have at least one value frame"); last.drain(last.len() - len..).collect() } fn push_val(&mut self) { let val = self.take_val_register(); self.val_stack .last_mut() .expect("should have at least one value frame") .push(val); } #[must_use] pub fn capture_stack(&self) -> Vec { let mut frames = self.call_stack.to_frames(); let mut span = self.current_span; for frame in frames.iter_mut().rev() { std::mem::swap(&mut frame.span, &mut span); } frames } #[must_use] pub fn capture_stack_if_trace_enabled( &self, tracing_backend: &TracingBackend<'_, B>, ) -> Vec { if tracing_backend.is_stacks_enabled() { self.capture_stack() } else { vec![] } } fn set_last_error(&mut self, error: Error, frames: Vec) { assert!( self.last_error.replace((error, frames)).is_none(), "last error should not be set twice" ); } fn get_last_error(&mut self) -> Result<(), (Error, Vec)> { // Use `is_none` to check for last error, as it avoids the unconditional // `mem::replace` call that `take` would perform. if self.last_error.is_none() { Ok(()) } else { Err(self.last_error.take().expect("last error should be set")) } } /// # Errors /// Returns the first error encountered during execution. /// # Panics /// When returning a value in the middle of execution. #[allow(clippy::too_many_lines)] pub fn eval( &mut self, globals: &impl PackageStoreLookup, env: &mut Env, sim: &mut TracingBackend<'_, B>, out: &mut impl Receiver, breakpoints: &[StmtId], step: StepAction, ) -> Result)> { let current_frame = self.current_frame_id(); while !self.exec_graph_stack.is_empty() { let exec_graph = self .exec_graph_stack .last() .expect("should have at least one stack frame"); let res = match exec_graph.get(self.idx as usize) { Some(ExecGraphNode::Bind(pat)) => { self.idx += 1; self.eval_bind(env, globals, *pat); continue; } Some(ExecGraphNode::Expr(expr)) => { self.idx += 1; match self.eval_expr(env, sim, globals, out, *expr) { Ok(()) => continue, Err(e) => { if self.error_behavior == ErrorBehavior::StopOnError { let error_str = e.to_string(); self.set_last_error(e, self.capture_stack()); // Clear the execution graph stack to indicate that execution has failed. // This will prevent further execution steps. self.exec_graph_stack.clear(); return Ok(StepResult::Fail(error_str)); } return Err((e, self.capture_stack())); } } } Some(ExecGraphNode::Jump(idx)) => { self.idx = *idx; continue; } Some(ExecGraphNode::JumpIf(idx)) => { let cond = self.val_register == Some(Value::Bool(true)); if cond { self.idx = *idx; } else { self.idx += 1; } continue; } Some(ExecGraphNode::JumpIfNot(idx)) => { let cond = self.val_register == Some(Value::Bool(true)); if cond { self.idx += 1; } else { self.idx = *idx; } continue; } Some(ExecGraphNode::Store) => { self.push_val(); self.idx += 1; continue; } Some(ExecGraphNode::Unit) => { self.idx += 1; self.set_val_register(Value::unit()); continue; } Some(ExecGraphNode::Ret) => { self.leave_frame(); env.leave_scope(); continue; } Some(ExecGraphNode::Debug(dbg_node)) => match dbg_node { ExecGraphDebugNode::PushScope => { self.push_scope(env); self.idx += 1; continue; } ExecGraphDebugNode::PushLoopScope(expr) => { self.push_loop_scope(env, *expr); self.idx += 1; continue; } ExecGraphDebugNode::RetFrame => { self.leave_frame(); env.leave_current_frame(); continue; } ExecGraphDebugNode::LoopIteration => { // we're in an iteration, increment counter self.call_stack.increment_loop_iteration(); self.idx += 1; continue; } ExecGraphDebugNode::PopScope => { if env.last_scope_is_loop() { self.call_stack.pop_loop_iteration(); } env.leave_scope(); self.idx += 1; continue; } ExecGraphDebugNode::BlockEnd(id) => { self.idx += 1; match self.check_for_block_exit_break(globals, *id, step, current_frame) { Some((result, span)) => { self.current_span = span; return Ok(result); } None => continue, } } ExecGraphDebugNode::Stmt(stmt) => { self.idx += 1; self.current_span = globals.get_stmt((self.package, *stmt).into()).span; match self.check_for_break(breakpoints, *stmt, step, current_frame) { Some(value) => value, None => continue, } } }, None => { // We have reached the end of the current graph without reaching an explicit return node, // usually indicating the partial execution of a single sub-expression. // This means we should pop the execution graph but not the current environment scope, // so bound variables are still accessible after completion. self.exec_graph_stack.pop(); assert!(self.exec_graph_stack.is_empty()); continue; } }; if let StepResult::Return(_) = res { panic!("unexpected return"); } return Ok(res); } // If we made it out of the execution loop, we either reached the end of the graph, // a return expression, or hit a runtime error. Check here for the error case // and return it if it exists. self.get_last_error()?; Ok(StepResult::Return(self.get_result())) } fn check_for_break( &self, breakpoints: &[StmtId], stmt: StmtId, step: StepAction, current_frame: usize, ) -> Option { Some( if let Some(bp) = breakpoints .iter() .find(|&bp| *bp == stmt && self.package == self.source_package) { StepResult::BreakpointHit(*bp) } else { if self.current_span == Span::default() { // if there is no span, we are in generated code, so we should skip return None; } // no breakpoint, but we may stop here if step == StepAction::In { StepResult::StepIn } else if step == StepAction::Next && current_frame >= self.current_frame_id() { StepResult::Next } else if step == StepAction::Out && current_frame > self.current_frame_id() { StepResult::StepOut } else { return None; } }, ) } fn check_for_block_exit_break( &self, globals: &impl PackageStoreLookup, block: BlockId, step: StepAction, current_frame: usize, ) -> Option<(StepResult, Span)> { if step == StepAction::Next && current_frame >= self.current_frame_id() { let block = globals.get_block((self.package, block).into()); let span = Span { lo: block.span.hi - 1, hi: block.span.hi, }; Some((StepResult::Next, span)) } else { None } } pub fn get_result(&mut self) -> Value { // Some executions don't have any statements to execute, // such as a fragment that has only item definitions. // In that case, the values are empty and the result is unit. self.val_register.take().unwrap_or_else(Value::unit) } #[allow(clippy::similar_names)] fn eval_expr( &mut self, env: &mut Env, sim: &mut TracingBackend<'_, B>, globals: &impl PackageStoreLookup, out: &mut impl Receiver, expr: ExprId, ) -> Result<(), Error> { let expr = globals.get_expr((self.package, expr).into()); self.current_span = expr.span; match &expr.kind { ExprKind::Array(arr) => self.eval_arr(arr.len()), ExprKind::ArrayLit(arr) => self.eval_arr_lit(arr, globals), ExprKind::ArrayRepeat(..) => self.eval_arr_repeat(expr.span)?, ExprKind::Assign(lhs, _) => self.eval_assign(env, globals, *lhs)?, ExprKind::AssignOp(op, lhs, rhs) => { let lhs_span = globals.get_expr((self.package, *lhs).into()).span; let rhs_span = globals.get_expr((self.package, *rhs).into()).span; let (is_array, is_unique) = is_updatable_in_place(env, globals.get_expr((self.package, *lhs).into())); if is_array { if is_unique { self.eval_array_append_in_place(env, globals, *lhs)?; return Ok(()); } let rhs_val = self.take_val_register(); self.eval_expr(env, sim, globals, out, *lhs)?; self.push_val(); self.set_val_register(rhs_val); } self.eval_binop(*op, lhs_span, rhs_span)?; self.eval_assign(env, globals, *lhs)?; } ExprKind::AssignField(record, field, _) => { self.eval_update_field(field.clone()); self.eval_assign(env, globals, *record)?; } ExprKind::AssignIndex(lhs, mid, _) => { let mid_span = globals.get_expr((self.package, *mid).into()).span; let (_, is_unique) = is_updatable_in_place(env, globals.get_expr((self.package, *lhs).into())); if is_unique { self.eval_update_index_in_place(env, globals, *lhs, mid_span)?; return Ok(()); } self.push_val(); self.eval_expr(env, sim, globals, out, *lhs)?; self.eval_update_index(mid_span)?; self.eval_assign(env, globals, *lhs)?; } ExprKind::BinOp(op, lhs, rhs) => { let lhs_span = globals.get_expr((self.package, *lhs).into()).span; let rhs_span = globals.get_expr((self.package, *rhs).into()).span; self.eval_binop(*op, lhs_span, rhs_span)?; } ExprKind::Block(..) => panic!("block expr should be handled by control flow"), ExprKind::Call(callee_expr, args_expr) => { let callable_span = globals.get_expr((self.package, *callee_expr).into()).span; let args_span = globals.get_expr((self.package, *args_expr).into()).span; self.eval_call(env, sim, globals, callable_span, args_span, out)?; } ExprKind::Closure(args, callable) => { let closure = resolve_closure(env, self.package, expr.span, args, *callable)?; self.set_val_register(closure); } ExprKind::Fail(..) => { return Err(Error::UserFail( self.take_val_register().unwrap_string().to_string(), self.to_global_span(expr.span), )); } ExprKind::Field(_, field) => self.eval_field(field.clone()), ExprKind::Hole => panic!("hole expr should be disallowed by passes"), ExprKind::If(..) => { panic!("if expr should be handled by control flow") } ExprKind::Index(_, rhs) => { let rhs_span = globals.get_expr((self.package, *rhs).into()).span; self.eval_index(rhs_span)?; } ExprKind::Lit(lit) => { self.set_val_register(lit_to_val(lit)); } ExprKind::Range(start, step, end) => { self.eval_range(start.is_some(), step.is_some(), end.is_some()); } ExprKind::Return(..) => panic!("return expr should be handled by control flow"), ExprKind::Struct(res, copy, fields) => self.eval_struct(res, *copy, fields), ExprKind::String(components) => self.collect_string(components), ExprKind::UpdateIndex(_, mid, _) => { let mid_span = globals.get_expr((self.package, *mid).into()).span; self.eval_update_index(mid_span)?; } ExprKind::Tuple(tup) => self.eval_tup(tup.len()), ExprKind::UnOp(op, _) => self.eval_unop(*op), ExprKind::UpdateField(_, field, _) => { self.eval_update_field(field.clone()); } ExprKind::Var(res, _) => { self.set_val_register(resolve_binding(env, self.package, *res, expr.span)?); } ExprKind::While(..) => { panic!("while expr should be handled by control flow") } } Ok(()) } fn collect_string(&mut self, components: &[StringComponent]) { if let [StringComponent::Lit(str)] = components { self.set_val_register(Value::String(Rc::clone(str))); return; } let mut string = String::new(); for component in components.iter().rev() { match component { StringComponent::Expr(..) => { let expr_str = format!("{}", self.pop_val()); string.insert_str(0, &expr_str); } StringComponent::Lit(lit) => { string.insert_str(0, lit); } } } self.set_val_register(Value::String(Rc::from(string))); } fn eval_arr(&mut self, len: usize) { let arr = self.pop_vals(len); self.set_val_register(Value::Array(arr.into())); } fn eval_arr_lit(&mut self, arr: &Vec, globals: &impl PackageStoreLookup) { let mut new_arr: Rc> = Rc::new(Vec::with_capacity(arr.len())); for id in arr { let ExprKind::Lit(lit) = &globals.get_expr((self.package, *id).into()).kind else { panic!("expr kind should be lit") }; Rc::get_mut(&mut new_arr) .expect("array should be uniquely referenced") .push(lit_to_val(lit)); } self.set_val_register(Value::Array(new_arr)); } fn eval_array_append_in_place( &mut self, env: &mut Env, globals: &impl PackageStoreLookup, lhs: ExprId, ) -> Result<(), Error> { let lhs = globals.get_expr((self.package, lhs).into()); let rhs = self.take_val_register(); match (&lhs.kind, rhs) { (&ExprKind::Var(Res::Local(id), _), rhs) => match env.get_mut(id) { Some(var) => { var.value.append_array(rhs); } None => { return Err(Error::UnboundName(self.to_global_span(lhs.span))); } }, _ => unreachable!("unassignable array update pattern should be disallowed by compiler"), } Ok(()) } fn eval_arr_repeat(&mut self, span: Span) -> Result<(), Error> { let size_val = self.take_val_register().unwrap_int(); let item_val = self.pop_val(); let s = match size_val.try_into() { Ok(i) => Ok(i), Err(_) => Err(Error::InvalidArrayLength( size_val, self.to_global_span(span), )), }?; self.set_val_register(Value::Array(vec![item_val; s].into())); Ok(()) } fn eval_assign( &mut self, env: &mut Env, globals: &impl PackageStoreLookup, lhs: ExprId, ) -> Result<(), Error> { let rhs = self.take_val_register(); self.update_binding(env, globals, lhs, rhs) } fn eval_bind(&mut self, env: &mut Env, globals: &impl PackageStoreLookup, pat: PatId) { let val = self.take_val_register(); self.bind_value(env, globals, pat, val); } fn eval_binop(&mut self, op: BinOp, lhs_span: Span, rhs_span: Span) -> Result<(), Error> { match op { BinOp::Add => self.eval_binop_simple(eval_binop_add), BinOp::AndB => self.eval_binop_simple(eval_binop_andb), BinOp::Div => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_div)?, BinOp::Eq => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_eq)?, BinOp::Exp => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_exp)?, BinOp::Gt => self.eval_binop_simple(eval_binop_gt), BinOp::Gte => self.eval_binop_simple(eval_binop_gte), BinOp::Lt => self.eval_binop_simple(eval_binop_lt), BinOp::Lte => self.eval_binop_simple(eval_binop_lte), BinOp::Mod => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_mod)?, BinOp::Mul => self.eval_binop_simple(eval_binop_mul), BinOp::Neq => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_neq)?, BinOp::OrB => self.eval_binop_simple(eval_binop_orb), BinOp::Shl => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_shl)?, BinOp::Shr => self.eval_binop_with_error(lhs_span, rhs_span, eval_binop_shr)?, BinOp::Sub => self.eval_binop_simple(eval_binop_sub), BinOp::XorB => self.eval_binop_simple(eval_binop_xorb), // Logical operators should be handled by control flow BinOp::AndL | BinOp::OrL => {} } Ok(()) } fn eval_binop_simple(&mut self, binop_func: impl FnOnce(Value, Value) -> Value) { let rhs_val = self.take_val_register(); let lhs_val = self.pop_val(); self.set_val_register(binop_func(lhs_val, rhs_val)); } fn eval_binop_with_error( &mut self, lhs_span: Span, rhs_span: Span, binop_func: impl FnOnce(Value, Value, PackageSpan, PackageSpan) -> Result, ) -> Result<(), Error> { let lhs_span: PackageSpan = self.to_global_span(lhs_span); let rhs_span: PackageSpan = self.to_global_span(rhs_span); let rhs_val = self.take_val_register(); let lhs_val = self.pop_val(); self.set_val_register(binop_func(lhs_val, rhs_val, lhs_span, rhs_span)?); Ok(()) } #[allow(clippy::too_many_lines)] fn eval_call( &mut self, env: &mut Env, sim: &mut TracingBackend<'_, B>, globals: &impl PackageStoreLookup, callable_span: Span, arg_span: Span, out: &mut impl Receiver, ) -> Result<(), Error> { let arg = self.take_val_register(); let (callee_id, functor, fixed_args) = match self.pop_val() { Value::Closure(inner) => (inner.id, inner.functor, Some(inner.fixed_args)), Value::Global(id, functor) => (id, functor, None), _ => panic!("value is not callable"), }; let arg_span = self.to_global_span(arg_span); let callee = match globals.get_global(callee_id) { Some(Global::Callable(callable)) => callable, Some(Global::Udt) => { let arg = match arg { Value::Tuple(items, _) => Value::Tuple(items, Some(callee_id.into())), _ => arg, }; self.set_val_register(arg); return Ok(()); } None => { return Err(Error::UnboundName(self.to_global_span(callable_span))); } }; let callee_span = self.to_global_span(callee.span); let spec = spec_from_functor_app(functor); match &callee.implementation { CallableImpl::Intrinsic if is_counting_call(&callee.name.name) => { self.push_frame(Vec::new().into(), callee_id, functor); let val = self.counting_call(&callee.name.name, arg, arg_span)?; self.set_val_register(val); self.leave_frame(); Ok(()) } CallableImpl::Intrinsic => self.eval_intrinsic( env, callee_id, functor, callee, sim, callee_span, arg, arg_span, out, ), CallableImpl::Spec(specialized_implementation) => { let spec_decl = match spec { Spec::Body => Some(&specialized_implementation.body), Spec::Adj => specialized_implementation.adj.as_ref(), Spec::Ctl => specialized_implementation.ctl.as_ref(), Spec::CtlAdj => specialized_implementation.ctl_adj.as_ref(), } .expect("missing specialization should be a compilation error"); self.push_frame( spec_decl.exec_graph.clone().select(self.exec_graph_config), callee_id, functor, ); self.push_scope(env); self.increment_call_count(callee_id, functor); self.bind_args_for_spec( env, globals, callee.input, spec_decl.input, arg, arg_span, functor.controlled, fixed_args, )?; Ok(()) } CallableImpl::SimulatableIntrinsic(spec_decl) => { self.push_frame( spec_decl.exec_graph.clone().select(self.exec_graph_config), callee_id, functor, ); self.push_scope(env); self.bind_args_for_spec( env, globals, callee.input, spec_decl.input, arg, arg_span, functor.controlled, fixed_args, )?; Ok(()) } } } #[allow(clippy::too_many_arguments)] fn eval_intrinsic( &mut self, env: &mut Env, callee_id: StoreItemId, functor: FunctorApp, callee: &fir::CallableDecl, sim: &mut TracingBackend<'_, B>, callee_span: PackageSpan, arg: Value, arg_span: PackageSpan, out: &mut impl Receiver, ) -> Result<(), Error> { let call_stack = self.capture_stack_if_trace_enabled(sim); self.push_frame(Vec::new().into(), callee_id, functor); self.current_span = callee_span.span; self.increment_call_count(callee_id, functor); let name = &callee.name.name; let val = match name.as_ref() { "__quantum__rt__qubit_allocate" | "__quantum__rt__qubit_borrow" => { let q = sim .qubit_allocate(&call_stack) .map_err(|e| Error::SimulationError(e, callee_span))?; let q = Rc::new(Qubit(q)); env.track_qubit(Rc::clone(&q)); if let Some(counter) = &mut self.qubit_counter { counter.allocated(q.0); } if name.as_ref() == "__quantum__rt__qubit_borrow" { self.dirty_qubits.insert(q.0); } Value::Qubit(q.into()) } "__quantum__rt__qubit_release" => { let qubit = arg .unwrap_qubit() .try_deref() .ok_or(Error::QubitDoubleRelease(arg_span))?; env.release_qubit(&qubit); let is_zero = sim .qubit_release(qubit.0, &call_stack) .map_err(|e| Error::SimulationError(e, callee_span))?; let is_borrowed = self.dirty_qubits.remove(&qubit.0); if is_zero || is_borrowed { Value::unit() } else { return Err(Error::ReleasedQubitNotZero(qubit.0, arg_span)); } } _ => { let val = intrinsic::call( name, callee_span, arg, arg_span, &call_stack, sim, &mut self.rng.borrow_mut(), out, )?; if val == Value::unit() && callee.output != Ty::UNIT { return Err(Error::UnsupportedIntrinsicType( callee.name.name.to_string(), callee_span, )); } val } }; self.set_val_register(val); self.leave_frame(); Ok(()) } fn eval_field(&mut self, field: Field) { let record = self.take_val_register(); let val = match (record, field) { (Value::Range(inner), Field::Prim(PrimField::Start)) => Value::Int( inner .start .expect("range access should be validated by compiler"), ), (Value::Range(inner), Field::Prim(PrimField::Step)) => Value::Int(inner.step), (Value::Range(inner), Field::Prim(PrimField::End)) => Value::Int( inner .end .expect("range access should be validated by compiler"), ), (record, Field::Path(path)) => { follow_field_path(record, &path.indices).expect("field path should be valid") } (ref value, ref field) => { panic!("invalid field access. value: {value:?}, field: {field:?}") } }; self.set_val_register(val); } fn eval_index(&mut self, span: Span) -> Result<(), Error> { let index_val = self.take_val_register(); let arr = self.pop_val().unwrap_array(); match &index_val { Value::Int(i) => { self.set_val_register(index_array(&arr, *i, self.to_global_span(span))?); } Value::Range(inner) => { self.set_val_register(slice_array( &arr, inner.start, inner.step, inner.end, self.to_global_span(span), )?); } _ => panic!("array should only be indexed by Int or Range"), } Ok(()) } fn eval_range(&mut self, has_start: bool, has_step: bool, has_end: bool) { let end = if has_end { Some(self.take_val_register().unwrap_int()) } else { None }; let step = if has_step { self.pop_val().unwrap_int() } else { val::DEFAULT_RANGE_STEP }; let start = if has_start { Some(self.pop_val().unwrap_int()) } else { None }; self.set_val_register(Value::Range(val::Range { start, step, end }.into())); } fn eval_struct(&mut self, res: &Res, copy: Option, fields: &[FieldAssign]) { // Extract a flat list of field indexes. let field_indexes = fields .iter() .map(|f| match &f.field { Field::Path(path) => match path.indices.as_slice() { &[i] => i, _ => panic!("field path for struct should have a single index"), }, _ => panic!("invalid field for struct"), }) .collect::>(); let len = fields.len(); let (field_vals, mut strct) = if copy.is_some() { // Get the field values and the copy struct value. let field_vals = self.pop_vals(len + 1); let (copy, field_vals) = field_vals.split_first().expect("copy value is expected"); // Make a clone of the copy struct value. (field_vals.to_vec(), copy.clone().unwrap_tuple().to_vec()) } else { // Make an empty struct of the appropriate size. (self.pop_vals(len), vec![Value::Int(0); len]) }; // Insert the field values into the new struct. assert!( field_vals.len() == field_indexes.len(), "number of given field values should match the number of given struct fields" ); for (i, val) in field_indexes.iter().zip(field_vals) { strct[*i] = val; } let store_item_id = if let Res::Item(item_id) = res { StoreItemId { package: item_id.package, item: item_id.item, } } else { panic!("UDT should be an item"); }; self.set_val_register(Value::Tuple(strct.into(), Some(Rc::new(store_item_id)))); } fn eval_update_index(&mut self, span: Span) -> Result<(), Error> { let values = self.take_val_register().unwrap_array(); let update = self.pop_val(); let index = self.pop_val(); let span = self.to_global_span(span); match index { Value::Int(index) => self.eval_update_index_single(&values, index, update, span), Value::Range(inner) => self.eval_update_index_range( &values, inner.start, inner.step, inner.end, update, span, ), _ => unreachable!("array should only be indexed by Int or Range"), } } fn eval_update_index_single( &mut self, values: &[Value], index: i64, update: Value, span: PackageSpan, ) -> Result<(), Error> { let updated_array = update_index_single(values, index, update, span)?; self.set_val_register(updated_array); Ok(()) } fn eval_update_index_range( &mut self, values: &[Value], start: Option, step: i64, end: Option, update: Value, span: PackageSpan, ) -> Result<(), Error> { let updated_array = update_index_range(values, start, step, end, update, span)?; self.set_val_register(updated_array); Ok(()) } fn eval_update_index_in_place( &mut self, env: &mut Env, globals: &impl PackageStoreLookup, lhs: ExprId, span: Span, ) -> Result<(), Error> { let update = self.take_val_register(); let index = self.pop_val(); let span = self.to_global_span(span); match index { Value::Int(index) => { if index < 0 { return Err(Error::InvalidNegativeInt(index, span)); } self.update_array_index_single(env, globals, lhs, span, index, update) } range @ Value::Range(..) => { self.update_array_index_range(env, globals, lhs, span, &range, update) } _ => unreachable!("array should only be indexed by Int or Range"), } } fn eval_tup(&mut self, len: usize) { let tup = self.pop_vals(len); self.set_val_register(Value::Tuple(tup.into(), None)); } fn eval_unop(&mut self, op: UnOp) { let val = self.take_val_register(); match op { UnOp::Functor(functor) => match val { Value::Closure(inner) => { self.set_val_register(Value::Closure( val::Closure { functor: update_functor_app(functor, inner.functor), ..*inner } .into(), )); } Value::Global(id, app) => { self.set_val_register(Value::Global(id, update_functor_app(functor, app))); } _ => panic!("value should be callable"), }, UnOp::Neg => match val { Value::BigInt(v) => self.set_val_register(Value::BigInt(v.neg())), Value::Double(v) => self.set_val_register(Value::Double(v.neg())), Value::Int(v) => self.set_val_register(Value::Int(v.wrapping_neg())), Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [real, imag] = array::from_fn(|i| v[i].clone()); let real = real.unwrap_double(); let imag = imag.unwrap_double(); self.set_val_register(Value::Tuple( vec![Value::Double(-real), Value::Double(-imag)].into(), Some(Rc::new(StoreItemId::complex())), )); } _ => panic!("value should be number"), }, UnOp::NotB => match val { Value::Int(v) => self.set_val_register(Value::Int(!v)), Value::BigInt(v) => self.set_val_register(Value::BigInt(!v)), _ => panic!("value should be Int or BigInt"), }, UnOp::NotL => match val { Value::Bool(b) => self.set_val_register(Value::Bool(!b)), _ => panic!("value should be bool"), }, UnOp::Pos => match val { Value::BigInt(_) | Value::Int(_) | Value::Double(_) => self.set_val_register(val), Value::Tuple(_, Some(ref id)) if *id.as_ref() == StoreItemId::complex() => { self.set_val_register(val); } _ => panic!("value should be number"), }, UnOp::Unwrap => self.set_val_register(val), } } fn eval_update_field(&mut self, field: Field) { let record = self.take_val_register(); let value = self.pop_val(); let update = match (record, field) { (Value::Range(mut inner), Field::Prim(PrimField::Start)) => { inner.start = Some(value.unwrap_int()); Value::Range(inner) } (Value::Range(mut inner), Field::Prim(PrimField::Step)) => { inner.step = value.unwrap_int(); Value::Range(inner) } (Value::Range(mut inner), Field::Prim(PrimField::End)) => { inner.end = Some(value.unwrap_int()); Value::Range(inner) } (record, Field::Path(path)) => update_field_path(&record, &path.indices, &value) .expect("field path should be valid"), _ => panic!("invalid field access"), }; self.set_val_register(update); } fn bind_value(&self, env: &mut Env, globals: &impl PackageStoreLookup, pat: PatId, val: Value) { let pat = globals.get_pat((self.package, pat).into()); match &pat.kind { PatKind::Bind(variable) => { let scope = env.scopes.last_mut().expect("binding should have a scope"); scope.bindings.insert( variable.id, Variable { name: variable.name.clone(), value: val, span: variable.span, }, ); } PatKind::Discard => {} PatKind::Tuple(tup) => { let val_tup = val.unwrap_tuple(); for (pat, val) in tup.iter().zip(val_tup.iter()) { self.bind_value(env, globals, *pat, val.clone()); } } } } #[allow(clippy::similar_names)] fn update_binding( &self, env: &mut Env, globals: &impl PackageStoreLookup, lhs: ExprId, rhs: Value, ) -> Result<(), Error> { let lhs = globals.get_expr((self.package, lhs).into()); match (&lhs.kind, rhs) { (ExprKind::Hole, _) => {} (&ExprKind::Var(Res::Local(id), _), rhs) => match env.get_mut(id) { Some(var) => { var.value = rhs; } None => { return Err(Error::UnboundName(self.to_global_span(lhs.span))); } }, (ExprKind::Tuple(var_tup), Value::Tuple(tup, _)) => { for (expr, val) in var_tup.iter().zip(tup.iter()) { self.update_binding(env, globals, *expr, val.clone())?; } } _ => unreachable!("unassignable pattern should be disallowed by compiler"), } Ok(()) } fn update_array_index_single( &mut self, env: &mut Env, globals: &impl PackageStoreLookup, lhs: ExprId, span: PackageSpan, index: i64, rhs: Value, ) -> Result<(), Error> { let lhs = globals.get_expr((self.package, lhs).into()); match &lhs.kind { &ExprKind::Var(Res::Local(id), _) => match env.get_mut(id) { Some(var) => { var.value.update_array(index, rhs, span)?; } None => return Err(Error::UnboundName(self.to_global_span(lhs.span))), }, _ => unreachable!("unassignable array update pattern should be disallowed by compiler"), } Ok(()) } #[allow(clippy::similar_names)] // `env` and `end` are similar but distinct fn update_array_index_range( &mut self, env: &mut Env, globals: &impl PackageStoreLookup, lhs: ExprId, range_span: PackageSpan, range: &Value, update: Value, ) -> Result<(), Error> { let lhs = globals.get_expr((self.package, lhs).into()); match &lhs.kind { &ExprKind::Var(Res::Local(id), _) => match env.get_mut(id) { Some(var) => { let rhs = update.unwrap_array(); let Value::Array(arr) = &mut var.value else { panic!("variable should be an array"); }; let Value::Range(inner) = range else { unreachable!("range should be a Value::Range"); }; let range = make_range(arr, inner.start, inner.step, inner.end, range_span)?; for (idx, rhs) in range.into_iter().zip(rhs.iter()) { if idx < 0 { return Err(Error::InvalidNegativeInt(idx, range_span)); } var.value.update_array(idx, rhs.clone(), range_span)?; } } None => return Err(Error::UnboundName(self.to_global_span(lhs.span))), }, _ => unreachable!("unassignable array update pattern should be disallowed by compiler"), } Ok(()) } #[allow(clippy::too_many_arguments)] fn bind_args_for_spec( &self, env: &mut Env, globals: &impl PackageStoreLookup, decl_pat: PatId, spec_pat: Option, args_val: Value, args_span: PackageSpan, ctl_count: u8, fixed_args: Option>, ) -> Result<(), Error> { match spec_pat { Some(spec_pat) => { assert!( ctl_count > 0, "spec pattern tuple used without controlled functor" ); let mut tup = args_val; let mut ctls = vec![]; for _ in 0..ctl_count { let [c, rest] = &*tup.unwrap_tuple() else { panic!("tuple should be arity 2"); }; ctls.extend_from_slice(&c.clone().unwrap_array()); tup = rest.clone(); } if !are_ctls_unique(&ctls, &tup) { return Err(Error::QubitUniqueness(args_span)); } self.bind_value(env, globals, spec_pat, Value::Array(ctls.into())); self.bind_value(env, globals, decl_pat, merge_fixed_args(fixed_args, tup)); } None => self.bind_value( env, globals, decl_pat, merge_fixed_args(fixed_args, args_val), ), } Ok(()) } fn to_global_span(&self, span: Span) -> PackageSpan { PackageSpan { package: map_fir_package_to_hir(self.package), span, } } fn counting_call(&mut self, name: &str, arg: Value, span: PackageSpan) -> Result { let counting_key = |arg: Value| match arg { Value::Closure(closure) => make_counting_key(closure.id, closure.functor), Value::Global(id, functor) => make_counting_key(id, functor), _ => panic!("value should be callable"), }; match name { "StartCountingOperation" | "StartCountingFunction" => { if self.call_counts.insert(counting_key(arg), 0).is_some() { Err(Error::CallableAlreadyCounted(span)) } else { Ok(Value::unit()) } } "StopCountingOperation" | "StopCountingFunction" => { if let Some(count) = self.call_counts.remove(&counting_key(arg)) { Ok(Value::Int(count)) } else { Err(Error::CallableNotCounted(span)) } } "StartCountingQubits" => { if self .qubit_counter .replace(QubitCounter::default()) .is_some() { Err(Error::QubitsAlreadyCounted(span)) } else { Ok(Value::unit()) } } "StopCountingQubits" => { if let Some(qubit_counter) = self.qubit_counter.take() { Ok(Value::Int(qubit_counter.into_count())) } else { Err(Error::QubitsNotCounted(span)) } } _ => panic!("unknown counting call"), } } fn increment_call_count(&mut self, callee_id: StoreItemId, functor: FunctorApp) { if let Some(count) = self .call_counts .get_mut(&make_counting_key(callee_id, functor)) { *count += 1; } } } pub fn are_ctls_unique(ctls: &[Value], tup: &Value) -> bool { let mut qubits = FxHashSet::default(); for ctl in ctls.iter().flat_map(Value::qubits) { if let Some(ctl) = ctl.try_deref() && !qubits.insert(ctl) { return false; } } for qubit in tup.qubits() { if let Some(qubit) = qubit.try_deref() && qubits.contains(&qubit) { return false; } } true } fn merge_fixed_args(fixed_args: Option>, arg: Value) -> Value { if let Some(fixed_args) = fixed_args { Value::Tuple( fixed_args.iter().cloned().chain(iter::once(arg)).collect(), None, ) } else { arg } } fn resolve_binding(env: &Env, package: PackageId, res: Res, span: Span) -> Result { Ok(match res { Res::Err => panic!("resolution error"), Res::Item(item) => Value::Global( StoreItemId { package: item.package, item: item.item, }, FunctorApp::default(), ), Res::Local(id) => env .get(id) .ok_or(Error::UnboundName(PackageSpan { package: map_fir_package_to_hir(package), span, }))? .value .clone(), }) } fn spec_from_functor_app(functor: FunctorApp) -> Spec { match (functor.adjoint, functor.controlled) { (false, 0) => Spec::Body, (true, 0) => Spec::Adj, (false, _) => Spec::Ctl, (true, _) => Spec::CtlAdj, } } pub fn resolve_closure( env: &Env, package: PackageId, span: Span, args: &[LocalVarId], callable: LocalItemId, ) -> Result { let args: Option<_> = args .iter() .map(|&arg| Some(env.get(arg)?.value.clone())) .collect(); let args: Vec<_> = args.ok_or(Error::UnboundName(PackageSpan { package: map_fir_package_to_hir(package), span, }))?; let callable = StoreItemId { package, item: callable, }; Ok(Value::Closure( val::Closure { fixed_args: args.into(), id: callable, functor: FunctorApp::default(), } .into(), )) } fn lit_to_val(lit: &Lit) -> Value { match lit { Lit::BigInt(v) => Value::BigInt(v.clone()), Lit::Bool(v) => Value::Bool(*v), Lit::Double(v) => Value::Double(*v), Lit::Int(v) => Value::Int(*v), Lit::Pauli(v) => Value::Pauli(*v), Lit::Result(fir::Result::Zero) => Value::RESULT_ZERO, Lit::Result(fir::Result::One) => Value::RESULT_ONE, } } fn eval_binop_eq( lhs_val: Value, rhs_val: Value, lhs_span: PackageSpan, rhs_span: PackageSpan, ) -> Result { match (lhs_val, rhs_val) { (Value::Result(val::Result::Id(_)), _) => { // Comparison of result ids is nonsensical, so we prevent it. // This code path is reachable when using the circuit builder backend // since we don't currently do runtime capability analysis // to prevent executing programs that do result comparisons. Err(Error::ResultComparisonUnsupported(lhs_span)) } (Value::Result(val::Result::Loss), _) => { // Loss is not comparable and should be checked ahead of time, so treat this as a runtime // failure. Err(Error::ResultLossComparisonUnsupported(lhs_span)) } (_, Value::Result(val::Result::Id(_))) => { // Comparison of result ids is nonsensical, so we prevent it. // This code path is reachable when using the circuit builder backend // since we don't currently do runtime capability analysis // to prevent executing programs that do result comparisons. Err(Error::ResultComparisonUnsupported(rhs_span)) } (_, Value::Result(val::Result::Loss)) => { // Loss is not comparable and should be checked ahead of time, so treat this as a runtime // failure. Err(Error::ResultLossComparisonUnsupported(rhs_span)) } (lhs, rhs) => Ok(Value::Bool(lhs == rhs)), } } fn eval_binop_neq( lhs_val: Value, rhs_val: Value, lhs_span: PackageSpan, rhs_span: PackageSpan, ) -> Result { match (lhs_val, rhs_val) { (Value::Result(val::Result::Id(_)), _) => { // Comparison of result ids is nonsensical, so we prevent it. // This code path is reachable when using the circuit builder backend // since we don't currently do runtime capability analysis // to prevent executing programs that do result comparisons. Err(Error::ResultComparisonUnsupported(lhs_span)) } (Value::Result(val::Result::Loss), _) => { // Loss is not comparable and should be checked ahead of time, so treat this as a runtime // failure. Err(Error::ResultLossComparisonUnsupported(lhs_span)) } (_, Value::Result(val::Result::Id(_))) => { // Comparison of result ids is nonsensical, so we prevent it. // This code path is reachable when using the circuit builder backend // since we don't currently do runtime capability analysis // to prevent executing programs that do result comparisons. Err(Error::ResultComparisonUnsupported(rhs_span)) } (_, Value::Result(val::Result::Loss)) => { // Loss is not comparable and should be checked ahead of time, so treat this as a runtime // failure. Err(Error::ResultLossComparisonUnsupported(rhs_span)) } (lhs, rhs) => Ok(Value::Bool(lhs != rhs)), } } fn eval_binop_add(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::Array(arr) => { let rhs_arr = rhs_val.unwrap_array(); let items: Vec<_> = arr.iter().cloned().chain(rhs_arr.iter().cloned()).collect(); Value::Array(items.into()) } Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::BigInt(val + rhs) } Value::Double(val) => { match &rhs_val { Value::Double(v) => Value::Double(val + v), Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { // Special case for adding a double and a complex literal. let [real, imag] = array::from_fn(|i| v[i].clone()); let real = real.unwrap_double(); let imag = imag.unwrap_double(); Value::Tuple( vec![Value::Double(val + real), Value::Double(imag)].into(), Some(Rc::clone(id)), ) } _ => panic!("value is not addable: {}", rhs_val.type_name()), } } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Int(val.wrapping_add(rhs)) } Value::String(val) => { let rhs = rhs_val.unwrap_string(); Value::String((val.to_string() + &rhs).into()) } Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [real, imag] = array::from_fn(|i| v[i].clone()); let real = real.unwrap_double(); let imag = imag.unwrap_double(); match &rhs_val { // Special case for adding a complex literal and a double. Value::Double(v) => Value::Tuple( vec![Value::Double(real + v), Value::Double(imag)].into(), Some(Rc::clone(&id)), ), Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone()); let rhs_real = rhs_real.unwrap_double(); let rhs_imag = rhs_imag.unwrap_double(); Value::Tuple( vec![ Value::Double(real + rhs_real), Value::Double(imag + rhs_imag), ] .into(), Some(Rc::clone(id)), ) } _ => panic!("value is not addable: {}", rhs_val.type_name()), } } _ => panic!("value is not addable: {}", lhs_val.type_name()), } } fn eval_binop_andb(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::BigInt(val & rhs) } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Int(val & rhs) } _ => panic!("value type does not support andb"), } } fn eval_binop_div( lhs_val: Value, rhs_val: Value, _: PackageSpan, rhs_span: PackageSpan, ) -> Result { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); if rhs == BigInt::from(0) { Err(Error::DivZero(rhs_span)) } else { Ok(Value::BigInt(val / rhs)) } } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); if rhs == 0 { Err(Error::DivZero(rhs_span)) } else { Ok(Value::Int(val.wrapping_div(rhs))) } } Value::Double(val) => { let rhs = rhs_val.unwrap_double(); Ok(Value::Double(val / rhs)) } Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [real, imag] = array::from_fn(|i| v[i].clone()); let real = real.unwrap_double(); let imag = imag.unwrap_double(); match rhs_val { Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone()); let rhs_real = rhs_real.unwrap_double(); let rhs_imag = rhs_imag.unwrap_double(); let denom = rhs_real * rhs_real + rhs_imag * rhs_imag; if denom == 0.0 { Err(Error::DivZero(rhs_span)) } else { Ok(Value::Tuple( vec![ Value::Double((real * rhs_real + imag * rhs_imag) / denom), Value::Double((imag * rhs_real - real * rhs_imag) / denom), ] .into(), Some(Rc::clone(&id)), )) } } _ => panic!("value should support div"), } } _ => panic!("value should support div"), } } fn eval_binop_exp( lhs_val: Value, rhs_val: Value, _: PackageSpan, rhs_span: PackageSpan, ) -> Result { match lhs_val { Value::BigInt(val) => { let rhs_val = rhs_val.unwrap_int(); if rhs_val < 0 { Err(Error::InvalidNegativeInt(rhs_val, rhs_span)) } else { let rhs_val: u32 = match rhs_val.try_into() { Ok(v) => Ok(v), Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)), }?; Ok(Value::BigInt(val.pow(rhs_val))) } } Value::Double(val) => Ok(Value::Double(val.powf(rhs_val.unwrap_double()))), Value::Int(val) => { let rhs_val = rhs_val.unwrap_int(); if rhs_val < 0 { Err(Error::InvalidNegativeInt(rhs_val, rhs_span)) } else { let result: i64 = match rhs_val.try_into() { Ok(v) => val .checked_pow(v) .ok_or(Error::IntTooLarge(rhs_val, rhs_span)), Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)), }?; Ok(Value::Int(result)) } } Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [real, imag] = array::from_fn(|i| v[i].clone()); let real = real.unwrap_double(); let imag = imag.unwrap_double(); match rhs_val { Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone()); let rhs_real = rhs_real.unwrap_double(); let rhs_imag = rhs_imag.unwrap_double(); // (a + bi)^(c + di) = exp((c + di) * log(a + bi)) let log_re = 0.5 * (real * real + imag * imag).ln(); let log_im = imag.atan2(real); let exp_re = (rhs_real * log_re - rhs_imag * log_im).exp(); let exp_im = rhs_real * log_im + rhs_imag * log_re; Ok(Value::Tuple( vec![ Value::Double(exp_re * exp_im.cos()), Value::Double(exp_re * exp_im.sin()), ] .into(), Some(Rc::clone(&id)), )) } _ => panic!("value should support exp"), } } _ => panic!("value should support exp"), } } fn eval_binop_gt(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::Bool(val > rhs) } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Bool(val > rhs) } Value::Double(val) => { let rhs = rhs_val.unwrap_double(); Value::Bool(val > rhs) } _ => panic!("value doesn't support binop gt"), } } fn eval_binop_gte(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::Bool(val >= rhs) } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Bool(val >= rhs) } Value::Double(val) => { let rhs = rhs_val.unwrap_double(); Value::Bool(val >= rhs) } _ => panic!("value doesn't support binop gte"), } } fn eval_binop_lt(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::Bool(val < rhs) } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Bool(val < rhs) } Value::Double(val) => { let rhs = rhs_val.unwrap_double(); Value::Bool(val < rhs) } _ => panic!("value doesn't support binop lt"), } } fn eval_binop_lte(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::Bool(val <= rhs) } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Bool(val <= rhs) } Value::Double(val) => { let rhs = rhs_val.unwrap_double(); Value::Bool(val <= rhs) } _ => panic!("value doesn't support binop lte"), } } fn eval_binop_mod( lhs_val: Value, rhs_val: Value, _: PackageSpan, rhs_span: PackageSpan, ) -> Result { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); if rhs == BigInt::from(0) { Err(Error::DivZero(rhs_span)) } else { Ok(Value::BigInt(val % rhs)) } } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); if rhs == 0 { Err(Error::DivZero(rhs_span)) } else { Ok(Value::Int(val.wrapping_rem(rhs))) } } Value::Double(val) => { let rhs = rhs_val.unwrap_double(); if rhs == 0.0 { Err(Error::DivZero(rhs_span)) } else { Ok(Value::Double(val % rhs)) } } _ => panic!("value should support mod"), } } fn eval_binop_mul(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::BigInt(val * rhs) } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Int(val.wrapping_mul(rhs)) } Value::Double(val) => { let rhs = rhs_val.unwrap_double(); Value::Double(val * rhs) } Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { // Special case for multiplying complex literals. let [real, imag] = array::from_fn(|i| v[i].clone()); let real = real.unwrap_double(); let imag = imag.unwrap_double(); match &rhs_val { Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone()); let rhs_real = rhs_real.unwrap_double(); let rhs_imag = rhs_imag.unwrap_double(); Value::Tuple( vec![ Value::Double(real * rhs_real - imag * rhs_imag), Value::Double(real * rhs_imag + imag * rhs_real), ] .into(), Some(Rc::clone(id)), ) } _ => panic!("value is not multipliable: {}", rhs_val.type_name()), } } _ => panic!("value should support mul"), } } fn eval_binop_orb(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::BigInt(val | rhs) } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Int(val | rhs) } _ => panic!("value type does not support orb"), } } fn eval_binop_shl( lhs_val: Value, rhs_val: Value, _: PackageSpan, rhs_span: PackageSpan, ) -> Result { Ok(match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_int(); if rhs > 0 { Value::BigInt(val << rhs) } else { Value::BigInt(val >> rhs.abs()) } } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Int(if rhs > 0 { let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?; val.checked_shl(shift) .ok_or(Error::IntTooLarge(rhs, rhs_span))? } else { let shift: u32 = rhs .checked_neg() .ok_or(Error::IntTooLarge(rhs, rhs_span))? .try_into() .or(Err(Error::IntTooLarge(rhs, rhs_span)))?; val.checked_shr(shift) .ok_or(Error::IntTooLarge(rhs, rhs_span))? }) } _ => panic!("value should support shl"), }) } fn eval_binop_shr( lhs_val: Value, rhs_val: Value, _: PackageSpan, rhs_span: PackageSpan, ) -> Result { Ok(match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_int(); if rhs > 0 { Value::BigInt(val >> rhs) } else { Value::BigInt(val << rhs.abs()) } } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Int(if rhs > 0 { let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?; val.checked_shr(shift) .ok_or(Error::IntTooLarge(rhs, rhs_span))? } else { let shift: u32 = rhs .checked_neg() .ok_or(Error::IntTooLarge(rhs, rhs_span))? .try_into() .or(Err(Error::IntTooLarge(rhs, rhs_span)))?; val.checked_shl(shift) .ok_or(Error::IntTooLarge(rhs, rhs_span))? }) } _ => panic!("value should support shr"), }) } fn eval_binop_sub(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::BigInt(val - rhs) } Value::Double(val) => { match &rhs_val { Value::Double(v) => Value::Double(val - v), Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { // Special case for subtracting a complex literal from a double. let [real, imag] = array::from_fn(|i| v[i].clone()); let real = real.unwrap_double(); let imag = imag.unwrap_double(); Value::Tuple( vec![Value::Double(val - real), Value::Double(-imag)].into(), Some(Rc::clone(id)), ) } _ => panic!("value is not subtractable: {}", rhs_val.type_name()), } } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Int(val.wrapping_sub(rhs)) } Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [real, imag] = array::from_fn(|i| v[i].clone()); let real = real.unwrap_double(); let imag = imag.unwrap_double(); match &rhs_val { // Special case for subtracting a double from a complex literal. Value::Double(v) => Value::Tuple( vec![Value::Double(real - v), Value::Double(imag)].into(), Some(Rc::clone(&id)), ), Value::Tuple(v, Some(id)) if *id.as_ref() == StoreItemId::complex() => { let [rhs_real, rhs_imag] = array::from_fn(|i| v[i].clone()); let rhs_real = rhs_real.unwrap_double(); let rhs_imag = rhs_imag.unwrap_double(); Value::Tuple( vec![ Value::Double(real - rhs_real), Value::Double(imag - rhs_imag), ] .into(), Some(Rc::clone(id)), ) } _ => panic!("value is not subtractable: {}", rhs_val.type_name()), } } _ => panic!("value is not subtractable"), } } fn eval_binop_xorb(lhs_val: Value, rhs_val: Value) -> Value { match lhs_val { Value::BigInt(val) => { let rhs = rhs_val.unwrap_big_int(); Value::BigInt(val ^ rhs) } Value::Int(val) => { let rhs = rhs_val.unwrap_int(); Value::Int(val ^ rhs) } _ => panic!("value type does not support xorb"), } } fn follow_field_path(mut value: Value, path: &[usize]) -> Option { for &index in path { let Value::Tuple(items, _) = value else { return None; }; value = items[index].clone(); } Some(value) } fn update_field_path(record: &Value, path: &[usize], replace: &Value) -> Option { match (record, path) { (_, []) => Some(replace.clone()), (Value::Tuple(items, store_item_id), &[next_index, ..]) if next_index < items.len() => { let update = |(index, item)| { if index == next_index { update_field_path(item, &path[1..], replace) } else { Some(item.clone()) } }; let items: Option<_> = items.iter().enumerate().map(update).collect(); Some(Value::Tuple(items?, store_item_id.clone())) } _ => None, } } fn is_updatable_in_place(env: &Env, expr: &Expr) -> (bool, bool) { match &expr.kind { ExprKind::Var(Res::Local(id), _) => match env.get(*id) { Some(var) => match &var.value { Value::Array(var) => (true, Rc::weak_count(var) + Rc::strong_count(var) == 1), _ => (false, false), }, _ => (false, false), }, _ => (false, false), } } fn is_counting_call(name: &str) -> bool { matches!( name, "StartCountingOperation" | "StopCountingOperation" | "StartCountingFunction" | "StopCountingFunction" | "StartCountingQubits" | "StopCountingQubits" ) } fn make_counting_key(id: StoreItemId, functor: FunctorApp) -> CallableCountKey { (id, functor.adjoint, functor.controlled > 0) } #[derive(Default)] struct QubitCounter { seen: FxHashSet, count: i64, } impl QubitCounter { fn allocated(&mut self, qubit: usize) { if self.seen.insert(qubit) { self.count += 1; } } fn into_count(self) -> i64 { self.count } }