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