// Copyright (c) Microsoft Corporation.
// Licensed under the MIT License.

//! The Q# evaluator handles the execution of Q# programs and/or fragments.
//! It operates based on vectors of `ExecGraphNode` instances, which act as a control flow graph
//! and are generated by lowering to FIR. The evaluator will iterate through the given graph,
//! executing the instructions it encounters and updating the state it was given accordingly, and using
//! the FIR store to look up graphs for any called functions or operations. The evaluator handles tracking
//! of stack frames and push/pop of variable scopes, and uses the index into the current execution graph
//! as a kind of stack pointer, updating the index based on `Jump`, `JumpIf`, and `JumpIfNot` instructions.
//!
//! Of note, the evaluator does not own the program state, which is tracked by the passed in `Env`
//! and `Backend` instances. This allows the evaluator to be reentrant, and supports both whole-program,
//! effectively stateless execution (like running shots of a program) stateful execution scenarios
//! (like debugging or notebooks).

#[cfg(test)]
mod tests;

pub mod backend;
pub mod debug;
mod error;
pub mod intrinsic;
pub mod noise;
pub mod output;
pub mod state;
pub mod val;

use crate::val::{
    Value, index_array, make_range, slice_array, update_index_range, update_index_single,
};
use backend::Backend;
use debug::{CallStack, Frame};
pub use error::PackageSpan;
use miette::Diagnostic;
use num_bigint::BigInt;
use output::Receiver;
use qsc_data_structures::{functors::FunctorApp, index_map::IndexMap, span::Span};
use qsc_fir::fir::{
    self, BinOp, CallableImpl, ExecGraph, ExecGraphNode, Expr, ExprId, ExprKind, Field,
    FieldAssign, Global, Lit, LocalItemId, LocalVarId, PackageId, PackageStoreLookup, PatId,
    PatKind, PrimField, Res, StmtId, StoreItemId, StringComponent, UnOp,
};
use qsc_fir::ty::Ty;
use qsc_lowerer::map_fir_package_to_hir;
use rand::{SeedableRng, rngs::StdRng};
use rustc_hash::{FxHashMap, FxHashSet};
use std::ops;
use std::{
    cell::RefCell,
    fmt::{self, Display, Formatter},
    iter,
    ops::Neg,
    rc::Rc,
};
use thiserror::Error;
use val::{Qubit, update_functor_app};

#[derive(Clone, Debug, Diagnostic, Error)]
pub enum Error {
    #[error("array too large")]
    #[diagnostic(code("Qsc.Eval.ArrayTooLarge"))]
    ArrayTooLarge(#[label("this array has too many items")] PackageSpan),

    #[error("callable already counted")]
    #[diagnostic(help(
        "counting for a given callable must be stopped before it can be started again"
    ))]
    #[diagnostic(code("Qsc.Eval.CallableAlreadyCounted"))]
    CallableAlreadyCounted(#[label] PackageSpan),

    #[error("callable not counted")]
    #[diagnostic(help("counting for a given callable must be started before it can be stopped"))]
    #[diagnostic(code("Qsc.Eval.CallableNotCounted"))]
    CallableNotCounted(#[label] PackageSpan),

    #[error("invalid array length: {0}")]
    #[diagnostic(code("Qsc.Eval.InvalidArrayLength"))]
    InvalidArrayLength(i64, #[label("cannot be used as a length")] PackageSpan),

    #[error("division by zero")]
    #[diagnostic(code("Qsc.Eval.DivZero"))]
    DivZero(#[label("cannot divide by zero")] PackageSpan),

    #[error("empty range")]
    #[diagnostic(code("Qsc.Eval.EmptyRange"))]
    EmptyRange(#[label("the range cannot be empty")] PackageSpan),

    #[error("value cannot be used as an index: {0}")]
    #[diagnostic(code("Qsc.Eval.InvalidIndex"))]
    InvalidIndex(i64, #[label("invalid index")] PackageSpan),

    #[error("integer too large for operation")]
    #[diagnostic(code("Qsc.Eval.IntTooLarge"))]
    IntTooLarge(i64, #[label("this value is too large")] PackageSpan),

    #[error("index out of range: {0}")]
    #[diagnostic(code("Qsc.Eval.IndexOutOfRange"))]
    IndexOutOfRange(i64, #[label("out of range")] PackageSpan),

    #[error("intrinsic callable `{0}` failed: {1}")]
    #[diagnostic(code("Qsc.Eval.IntrinsicFail"))]
    IntrinsicFail(String, String, #[label] PackageSpan),

    #[error("invalid rotation angle: {0}")]
    #[diagnostic(code("Qsc.Eval.InvalidRotationAngle"))]
    InvalidRotationAngle(f64, #[label("invalid rotation angle")] PackageSpan),

    #[error("negative integers cannot be used here: {0}")]
    #[diagnostic(code("Qsc.Eval.InvalidNegativeInt"))]
    InvalidNegativeInt(i64, #[label("invalid negative integer")] PackageSpan),

    #[error("output failure")]
    #[diagnostic(code("Qsc.Eval.OutputFail"))]
    OutputFail(#[label("failed to generate output")] PackageSpan),

    #[error("qubits in invocation are not unique")]
    #[diagnostic(code("Qsc.Eval.QubitUniqueness"))]
    QubitUniqueness(#[label] PackageSpan),

    #[error("qubit used after release")]
    #[diagnostic(help(
        "qubits should not be used after being released, which typically occurs when a qubit is used after it has gone out of scope"
    ))]
    #[diagnostic(code("Qsc.Eval.QubitUsedAfterRelease"))]
    QubitUsedAfterRelease(#[label] PackageSpan),

    #[error("qubit double release")]
    #[diagnostic(code("Qsc.Eval.QubitDoubleRelease"))]
    QubitDoubleRelease(#[label("qubit has already been released")] PackageSpan),

    #[error("qubits already counted")]
    #[diagnostic(help("counting for qubits must be stopped before it can be started again"))]
    #[diagnostic(code("Qsc.Eval.QubitsAlreadyCounted"))]
    QubitsAlreadyCounted(#[label] PackageSpan),

    #[error("qubits not counted")]
    #[diagnostic(help("counting for qubits must be started before it can be stopped"))]
    #[diagnostic(code("Qsc.Eval.QubitsNotCounted"))]
    QubitsNotCounted(#[label] PackageSpan),

    #[error("qubits are not separable")]
    #[diagnostic(help(
        "subset of qubits provided as arguments must not be entangled with any qubits outside of the subset"
    ))]
    #[diagnostic(code("Qsc.Eval.QubitsNotSeparable"))]
    QubitsNotSeparable(#[label] PackageSpan),

    #[error("range with step size of zero")]
    #[diagnostic(code("Qsc.Eval.RangeStepZero"))]
    RangeStepZero(#[label("invalid range")] PackageSpan),

    #[error("qubit arrays used in relabeling must be a permutation of the same set of qubits")]
    #[diagnostic(help("ensure that each qubit is present exactly once in both arrays"))]
    #[diagnostic(code("Qsc.Eval.RelabelingMismatch"))]
    RelabelingMismatch(#[label] PackageSpan),

    #[error("Qubit{0} released while not in |0⟩ state")]
    #[diagnostic(help(
        "qubits should be returned to the |0⟩ state before being released to satisfy the assumption that allocated qubits start in the |0⟩ state"
    ))]
    #[diagnostic(code("Qsc.Eval.ReleasedQubitNotZero"))]
    ReleasedQubitNotZero(usize, #[label("Qubit{0}")] PackageSpan),

    #[error("cannot compare measurement results")]
    #[diagnostic(code("Qsc.Eval.ResultComparisonUnsupported"))]
    #[diagnostic(help(
        "comparing measurement results is not supported when performing circuit synthesis or base profile QIR generation"
    ))]
    ResultComparisonUnsupported(#[label("cannot compare to result")] PackageSpan),

    #[error("cannot compare measurement result from qubit loss")]
    #[diagnostic(code("Qsc.Eval.ResultLossComparisonUnsupported"))]
    #[diagnostic(help(
        "use of a measurement result from a qubit that was lost is not supported, use `IsLossResult` to ensure the result is valid before using it in a comparison"
    ))]
    ResultLossComparisonUnsupported(#[label("cannot compare result from qubit loss")] PackageSpan),

    #[error("name is not bound")]
    #[diagnostic(code("Qsc.Eval.UnboundName"))]
    UnboundName(#[label] PackageSpan),

    #[error("unknown intrinsic `{0}`")]
    #[diagnostic(code("Qsc.Eval.UnknownIntrinsic"))]
    UnknownIntrinsic(
        String,
        #[label("callable has no implementation")] PackageSpan,
    ),

    #[error("unsupported return type for intrinsic `{0}`")]
    #[diagnostic(help("intrinsic callable return type should be `Unit`"))]
    #[diagnostic(code("Qsc.Eval.UnsupportedIntrinsicType"))]
    UnsupportedIntrinsicType(String, #[label] PackageSpan),

    #[error("program failed: {0}")]
    #[diagnostic(code("Qsc.Eval.UserFail"))]
    UserFail(String, #[label("explicit fail")] PackageSpan),
}

impl Error {
    #[must_use]
    pub fn span(&self) -> &PackageSpan {
        match self {
            Error::ArrayTooLarge(span)
            | Error::CallableAlreadyCounted(span)
            | Error::CallableNotCounted(span)
            | Error::DivZero(span)
            | Error::EmptyRange(span)
            | Error::IndexOutOfRange(_, span)
            | Error::InvalidIndex(_, span)
            | Error::IntrinsicFail(_, _, span)
            | Error::IntTooLarge(_, span)
            | Error::InvalidRotationAngle(_, span)
            | Error::InvalidNegativeInt(_, span)
            | Error::OutputFail(span)
            | Error::QubitUniqueness(span)
            | Error::QubitUsedAfterRelease(span)
            | Error::QubitDoubleRelease(span)
            | Error::QubitsAlreadyCounted(span)
            | Error::QubitsNotCounted(span)
            | Error::QubitsNotSeparable(span)
            | Error::RangeStepZero(span)
            | Error::RelabelingMismatch(span)
            | Error::ReleasedQubitNotZero(_, span)
            | Error::ResultComparisonUnsupported(span)
            | Error::ResultLossComparisonUnsupported(span)
            | Error::UnboundName(span)
            | Error::UnknownIntrinsic(_, span)
            | Error::UnsupportedIntrinsicType(_, span)
            | Error::UserFail(_, span)
            | Error::InvalidArrayLength(_, span) => span,
        }
    }
}

/// A specialization that may be implemented for an operation.
enum Spec {
    /// The default specialization.
    Body,
    /// The adjoint specialization.
    Adj,
    /// The controlled specialization.
    Ctl,
    /// The controlled adjoint specialization.
    CtlAdj,
}

impl Display for Spec {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        match self {
            Spec::Body => f.write_str("body"),
            Spec::Adj => f.write_str("adjoint"),
            Spec::Ctl => f.write_str("controlled"),
            Spec::CtlAdj => f.write_str("controlled adjoint"),
        }
    }
}

/// Utility function to identify a subset of a control flow graph corresponding to a given
/// range.
#[must_use]
pub fn exec_graph_section(graph: &ExecGraph, range: ops::Range<usize>) -> ExecGraph {
    let start: u32 = range
        .start
        .try_into()
        .expect("exec graph ranges should fit into u32");
    graph[range]
        .iter()
        .map(|node| match node {
            ExecGraphNode::Jump(idx) => ExecGraphNode::Jump(idx - start),
            ExecGraphNode::JumpIf(idx) => ExecGraphNode::JumpIf(idx - start),
            ExecGraphNode::JumpIfNot(idx) => ExecGraphNode::JumpIfNot(idx - start),
            _ => *node,
        })
        .collect::<Vec<_>>()
        .into()
}

/// Evaluates the given code with the given context.
/// # Errors
/// Returns the first error encountered during execution.
/// # Panics
/// On internal error where no result is returned.
pub fn eval(
    package: PackageId,
    seed: Option<u64>,
    exec_graph: ExecGraph,
    globals: &impl PackageStoreLookup,
    env: &mut Env,
    sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
    receiver: &mut impl Receiver,
) -> Result<Value, (Error, Vec<Frame>)> {
    let mut state = State::new(package, exec_graph, seed);
    let res = state.eval(globals, env, sim, receiver, &[], StepAction::Continue)?;
    let StepResult::Return(value) = res else {
        panic!("eval should always return a value");
    };
    Ok(value)
}

/// Evaluates the given callable with the given context.
/// # Errors
/// Returns the first error encountered during execution.
/// # Panics
/// On internal error where no result is returned.
#[allow(clippy::too_many_arguments)]
pub fn invoke(
    package: PackageId,
    seed: Option<u64>,
    globals: &impl PackageStoreLookup,
    env: &mut Env,
    sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
    receiver: &mut impl Receiver,
    callable: Value,
    args: Value,
) -> Result<Value, (Error, Vec<Frame>)> {
    let mut state = State::new(package, Vec::new().into(), seed);
    // Push the callable value into the state stack and then the args value so they are ready for evaluation.
    state.set_val_register(callable);
    state.push_val();
    state.set_val_register(args);

    // Evaluate the call, which will pop the args and callable values from the stack and then either
    // a) prepare the call stack for the execution of the callable, or
    // b) invoke the callable directly if it is an intrinsic.
    state
        .eval_call(
            env,
            sim,
            globals,
            Span::default(),
            Span::default(),
            receiver,
        )
        .map_err(|e| (e, state.get_stack_frames()))?;

    // Trigger evaluation of the state until the end of the stack is reached and a return value is obtained, which will be the final
    // result of the invocation.
    let res = state.eval(globals, env, sim, receiver, &[], StepAction::Continue)?;
    let StepResult::Return(value) = res else {
        panic!("eval should always return a value");
    };
    Ok(value)
}

/// The type of step action to take during evaluation
#[derive(Debug, Copy, Clone, Eq, PartialEq)]
pub enum StepAction {
    Next,
    In,
    Out,
    Continue,
}

// The result of an evaluation step.
#[derive(Clone, Debug)]
pub enum StepResult {
    BreakpointHit(StmtId),
    Next,
    StepIn,
    StepOut,
    Return(Value),
    Fail,
}

trait AsIndex {
    type Output;

    fn as_index(&self, index_source: PackageSpan) -> Self::Output;
}

impl AsIndex for i64 {
    type Output = Result<usize, Error>;

    fn as_index(&self, index_source: PackageSpan) -> Self::Output {
        match (*self).try_into() {
            Ok(index) => Ok(index),
            Err(_) => Err(Error::InvalidIndex(*self, index_source)),
        }
    }
}

#[derive(Debug, Clone)]
pub struct Variable {
    pub name: Rc<str>,
    pub value: Value,
    pub span: Span,
}

#[derive(Debug, Clone)]
pub struct VariableInfo {
    pub value: Value,
    pub name: Rc<str>,
    pub type_name: String,
    pub span: Span,
}

pub struct Range {
    step: i64,
    end: i64,
    curr: i64,
}

impl Iterator for Range {
    type Item = i64;

    fn next(&mut self) -> Option<Self::Item> {
        let curr = self.curr;
        self.curr += self.step;
        if (self.step > 0 && curr <= self.end) || (self.step < 0 && curr >= self.end) {
            Some(curr)
        } else {
            None
        }
    }
}

impl Range {
    fn new(start: i64, step: i64, end: i64) -> Self {
        Range {
            step,
            end,
            curr: start,
        }
    }
}

pub struct Env {
    scopes: Vec<Scope>,
    qubits: FxHashSet<Rc<Qubit>>,
}

impl Default for Env {
    fn default() -> Self {
        // Always create a global scope for top-level statements.
        Self {
            scopes: vec![Scope::default()],
            qubits: FxHashSet::default(),
        }
    }
}

impl Env {
    #[must_use]
    pub fn get(&self, id: LocalVarId) -> Option<&Variable> {
        self.scopes
            .iter()
            .rev()
            .find_map(|scope| scope.bindings.get(id))
    }

    fn get_mut(&mut self, id: LocalVarId) -> Option<&mut Variable> {
        self.scopes
            .iter_mut()
            .rev()
            .find_map(|scope| scope.bindings.get_mut(id))
    }

    pub fn push_scope(&mut self, frame_id: usize) {
        let scope = Scope {
            frame_id,
            ..Default::default()
        };
        self.scopes.push(scope);
    }

    pub fn leave_scope(&mut self) {
        // Only pop the scope if there is more than one scope in the stack,
        // because the global/top-level scope cannot be exited.
        if self.scopes.len() > 1 {
            self.scopes
                .pop()
                .expect("scope should have more than one entry.");
        }
    }

    pub fn leave_current_frame(&mut self) {
        let current_frame_id = self
            .scopes
            .last()
            .expect("should be at least one scope")
            .frame_id;
        if current_frame_id == 0 {
            // Do not remove the global scope.
            return;
        }
        self.scopes
            .retain(|scope| scope.frame_id != current_frame_id);
    }

    pub fn bind_variable_in_top_frame(&mut self, local_var_id: LocalVarId, var: Variable) {
        let Some(scope) = self.scopes.last_mut() else {
            panic!("no frames in scope");
        };

        scope.bindings.insert(local_var_id, var);
    }

    #[must_use]
    pub fn get_variables_in_top_frame(&self) -> Vec<VariableInfo> {
        if let Some(scope) = self.scopes.last() {
            self.get_variables_in_frame(scope.frame_id)
        } else {
            vec![]
        }
    }

    #[must_use]
    pub fn get_variables_in_frame(&self, frame_id: usize) -> Vec<VariableInfo> {
        let candidate_scopes: Vec<_> = self
            .scopes
            .iter()
            .filter(|scope| scope.frame_id == frame_id)
            .map(|scope| scope.bindings.iter())
            .collect();

        let variables_by_scope: Vec<Vec<VariableInfo>> = candidate_scopes
            .into_iter()
            .map(|bindings| {
                bindings
                    .map(|(_, var)| VariableInfo {
                        name: var.name.clone(),
                        type_name: var.value.type_name().to_string(),
                        value: var.value.clone(),
                        span: var.span,
                    })
                    .collect()
            })
            .collect();
        variables_by_scope.into_iter().flatten().collect::<Vec<_>>()
    }

    #[allow(clippy::len_without_is_empty)]
    #[must_use]
    pub fn len(&self) -> usize {
        self.scopes.len()
    }

    pub fn update_variable_in_top_frame(&mut self, local_var_id: LocalVarId, value: Value) {
        let variable = self
            .get_mut(local_var_id)
            .expect("local variable is not present");
        variable.value = value;
    }

    pub fn track_qubit(&mut self, qubit: Rc<Qubit>) {
        self.qubits.insert(qubit);
    }

    pub fn release_qubit(&mut self, qubit: &Rc<Qubit>) {
        self.qubits.remove(qubit);
    }
}

#[derive(Default)]
struct Scope {
    bindings: IndexMap<LocalVarId, Variable>,
    frame_id: usize,
}

type CallableCountKey = (StoreItemId, bool, bool);

pub struct State {
    exec_graph_stack: Vec<ExecGraph>,
    idx: u32,
    idx_stack: Vec<u32>,
    val_register: Option<Value>,
    val_stack: Vec<Vec<Value>>,
    source_package: PackageId,
    package: PackageId,
    call_stack: CallStack,
    current_span: Span,
    rng: RefCell<StdRng>,
    call_counts: FxHashMap<CallableCountKey, i64>,
    qubit_counter: Option<QubitCounter>,
}

impl State {
    #[must_use]
    pub fn new(package: PackageId, exec_graph: ExecGraph, classical_seed: Option<u64>) -> Self {
        let rng = match classical_seed {
            Some(seed) => RefCell::new(StdRng::seed_from_u64(seed)),
            None => RefCell::new(StdRng::from_entropy()),
        };
        Self {
            exec_graph_stack: vec![exec_graph],
            idx: 0,
            idx_stack: Vec::new(),
            val_register: None,
            val_stack: vec![Vec::new()],
            source_package: package,
            package,
            call_stack: CallStack::default(),
            current_span: Span::default(),
            rng,
            call_counts: FxHashMap::default(),
            qubit_counter: None,
        }
    }

    fn push_frame(&mut self, exec_graph: ExecGraph, id: StoreItemId, functor: FunctorApp) {
        self.call_stack.push_frame(Frame {
            span: self.current_span,
            id,
            caller: self.package,
            functor,
        });
        self.exec_graph_stack.push(exec_graph);
        self.val_stack.push(Vec::new());
        self.idx_stack.push(self.idx);
        self.idx = 0;
        self.package = id.package;
    }

    fn leave_frame(&mut self) {
        if let Some(frame) = self.call_stack.pop_frame() {
            self.package = frame.caller;
        }
        self.val_stack.pop();
        self.idx = self.idx_stack.pop().unwrap_or_default();
        self.exec_graph_stack.pop();
    }

    fn push_scope(&mut self, env: &mut Env) {
        // `push_frame`, which increments the length of `self.call_stack` by 1,
        // is called before `self.push_scope`.
        // Since the first `frame_id` should be 0, we substract 1 here.
        env.push_scope(self.call_stack.len() - 1);
    }

    fn take_val_register(&mut self) -> Value {
        self.val_register.take().expect("value should be present")
    }

    fn set_val_register(&mut self, val: Value) {
        self.val_register = Some(val);
    }

    fn pop_val(&mut self) -> Value {
        self.val_stack
            .last_mut()
            .expect("should have at least one value frame")
            .pop()
            .expect("value should be present")
    }

    fn pop_vals(&mut self, len: usize) -> Vec<Value> {
        let last = self
            .val_stack
            .last_mut()
            .expect("should have at least one value frame");
        last.drain(last.len() - len..).collect()
    }

    fn push_val(&mut self) {
        let val = self.take_val_register();
        self.val_stack
            .last_mut()
            .expect("should have at least one value frame")
            .push(val);
    }

    #[must_use]
    pub fn get_stack_frames(&self) -> Vec<Frame> {
        let mut frames = self.call_stack.clone().into_frames();

        let mut span = self.current_span;
        for frame in frames.iter_mut().rev() {
            std::mem::swap(&mut frame.span, &mut span);
        }
        frames
    }

    /// # Errors
    /// Returns the first error encountered during execution.
    /// # Panics
    /// When returning a value in the middle of execution.
    pub fn eval(
        &mut self,
        globals: &impl PackageStoreLookup,
        env: &mut Env,
        sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
        out: &mut impl Receiver,
        breakpoints: &[StmtId],
        step: StepAction,
    ) -> Result<StepResult, (Error, Vec<Frame>)> {
        let current_frame = self.call_stack.len();
        while !self.exec_graph_stack.is_empty() {
            let exec_graph = self
                .exec_graph_stack
                .last()
                .expect("should have at least one stack frame");
            let res = match exec_graph.get(self.idx as usize) {
                Some(ExecGraphNode::Bind(pat)) => {
                    self.idx += 1;
                    self.eval_bind(env, globals, *pat);
                    continue;
                }
                Some(ExecGraphNode::Expr(expr)) => {
                    self.idx += 1;
                    self.eval_expr(env, sim, globals, out, *expr)
                        .map_err(|e| (e, self.get_stack_frames()))?;
                    continue;
                }
                Some(ExecGraphNode::Stmt(stmt)) => {
                    self.idx += 1;
                    self.current_span = globals.get_stmt((self.package, *stmt).into()).span;

                    match self.check_for_break(breakpoints, *stmt, step, current_frame) {
                        Some(value) => value,
                        None => continue,
                    }
                }
                Some(ExecGraphNode::Fail) => {
                    self.idx += 1;
                    return Ok(StepResult::Fail);
                }
                Some(ExecGraphNode::Jump(idx)) => {
                    self.idx = *idx;
                    continue;
                }
                Some(ExecGraphNode::JumpIf(idx)) => {
                    let cond = self.val_register == Some(Value::Bool(true));
                    if cond {
                        self.idx = *idx;
                    } else {
                        self.idx += 1;
                    }
                    continue;
                }
                Some(ExecGraphNode::JumpIfNot(idx)) => {
                    let cond = self.val_register == Some(Value::Bool(true));
                    if cond {
                        self.idx += 1;
                    } else {
                        self.idx = *idx;
                    }
                    continue;
                }
                Some(ExecGraphNode::Store) => {
                    self.push_val();
                    self.idx += 1;
                    continue;
                }
                Some(ExecGraphNode::Unit) => {
                    self.idx += 1;
                    self.set_val_register(Value::unit());
                    continue;
                }
                Some(ExecGraphNode::Ret) => {
                    self.leave_frame();
                    env.leave_scope();
                    continue;
                }
                Some(ExecGraphNode::RetFrame) => {
                    self.leave_frame();
                    env.leave_current_frame();
                    continue;
                }
                Some(ExecGraphNode::PushScope) => {
                    self.push_scope(env);
                    self.idx += 1;
                    continue;
                }
                Some(ExecGraphNode::PopScope) => {
                    env.leave_scope();
                    self.idx += 1;
                    continue;
                }
                None => {
                    // We have reached the end of the current graph without reaching an explicit return node,
                    // usually indicating the partial execution of a single sub-expression.
                    // This means we should pop the execution graph but not the current environment scope,
                    // so bound variables are still accessible after completion.
                    self.exec_graph_stack.pop();
                    assert!(self.exec_graph_stack.is_empty());
                    continue;
                }
            };

            if let StepResult::Return(_) = res {
                panic!("unexpected return");
            }

            return Ok(res);
        }

        Ok(StepResult::Return(self.get_result()))
    }

    fn check_for_break(
        &self,
        breakpoints: &[StmtId],
        stmt: StmtId,
        step: StepAction,
        current_frame: usize,
    ) -> Option<StepResult> {
        Some(
            if let Some(bp) = breakpoints
                .iter()
                .find(|&bp| *bp == stmt && self.package == self.source_package)
            {
                StepResult::BreakpointHit(*bp)
            } else {
                if self.current_span == Span::default() {
                    // if there is no span, we are in generated code, so we should skip
                    return None;
                }
                // no breakpoint, but we may stop here
                if step == StepAction::In {
                    StepResult::StepIn
                } else if step == StepAction::Next && current_frame >= self.call_stack.len() {
                    StepResult::Next
                } else if step == StepAction::Out && current_frame > self.call_stack.len() {
                    StepResult::StepOut
                } else {
                    return None;
                }
            },
        )
    }

    pub fn get_result(&mut self) -> Value {
        // Some executions don't have any statements to execute,
        // such as a fragment that has only item definitions.
        // In that case, the values are empty and the result is unit.
        self.val_register.take().unwrap_or_else(Value::unit)
    }

    #[allow(clippy::similar_names)]
    fn eval_expr(
        &mut self,
        env: &mut Env,
        sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
        globals: &impl PackageStoreLookup,
        out: &mut impl Receiver,
        expr: ExprId,
    ) -> Result<(), Error> {
        let expr = globals.get_expr((self.package, expr).into());
        self.current_span = expr.span;
        match &expr.kind {
            ExprKind::Array(arr) => self.eval_arr(arr.len()),
            ExprKind::ArrayLit(arr) => self.eval_arr_lit(arr, globals),
            ExprKind::ArrayRepeat(..) => self.eval_arr_repeat(expr.span)?,
            ExprKind::Assign(lhs, _) => self.eval_assign(env, globals, *lhs)?,
            ExprKind::AssignOp(op, lhs, rhs) => {
                let rhs_span = globals.get_expr((self.package, *rhs).into()).span;
                let (is_array, is_unique) =
                    is_updatable_in_place(env, globals.get_expr((self.package, *lhs).into()));
                if is_array {
                    if is_unique {
                        self.eval_array_append_in_place(env, globals, *lhs)?;
                        return Ok(());
                    }
                    let rhs_val = self.take_val_register();
                    self.eval_expr(env, sim, globals, out, *lhs)?;
                    self.push_val();
                    self.set_val_register(rhs_val);
                }
                self.eval_binop(*op, rhs_span)?;
                self.eval_assign(env, globals, *lhs)?;
            }
            ExprKind::AssignField(record, field, _) => {
                self.eval_update_field(field.clone());
                self.eval_assign(env, globals, *record)?;
            }
            ExprKind::AssignIndex(lhs, mid, _) => {
                let mid_span = globals.get_expr((self.package, *mid).into()).span;
                let (_, is_unique) =
                    is_updatable_in_place(env, globals.get_expr((self.package, *lhs).into()));
                if is_unique {
                    self.eval_update_index_in_place(env, globals, *lhs, mid_span)?;
                    return Ok(());
                }
                self.push_val();
                self.eval_expr(env, sim, globals, out, *lhs)?;
                self.eval_update_index(mid_span)?;
                self.eval_assign(env, globals, *lhs)?;
            }
            ExprKind::BinOp(op, _, rhs) => {
                let rhs_span = globals.get_expr((self.package, *rhs).into()).span;
                self.eval_binop(*op, rhs_span)?;
            }
            ExprKind::Block(..) => panic!("block expr should be handled by control flow"),
            ExprKind::Call(callee_expr, args_expr) => {
                let callable_span = globals.get_expr((self.package, *callee_expr).into()).span;
                let args_span = globals.get_expr((self.package, *args_expr).into()).span;
                self.eval_call(env, sim, globals, callable_span, args_span, out)?;
            }
            ExprKind::Closure(args, callable) => {
                let closure = resolve_closure(env, self.package, expr.span, args, *callable)?;
                self.set_val_register(closure);
            }
            ExprKind::Fail(..) => {
                return Err(Error::UserFail(
                    self.take_val_register().unwrap_string().to_string(),
                    self.to_global_span(expr.span),
                ));
            }
            ExprKind::Field(_, field) => self.eval_field(field.clone()),
            ExprKind::Hole => panic!("hole expr should be disallowed by passes"),
            ExprKind::If(..) => {
                panic!("if expr should be handled by control flow")
            }
            ExprKind::Index(_, rhs) => {
                let rhs_span = globals.get_expr((self.package, *rhs).into()).span;
                self.eval_index(rhs_span)?;
            }
            ExprKind::Lit(lit) => {
                self.set_val_register(lit_to_val(lit));
            }
            ExprKind::Range(start, step, end) => {
                self.eval_range(start.is_some(), step.is_some(), end.is_some());
            }
            ExprKind::Return(..) => panic!("return expr should be handled by control flow"),
            ExprKind::Struct(_, copy, fields) => self.eval_struct(*copy, fields),
            ExprKind::String(components) => self.collect_string(components),
            ExprKind::UpdateIndex(_, mid, _) => {
                let mid_span = globals.get_expr((self.package, *mid).into()).span;
                self.eval_update_index(mid_span)?;
            }
            ExprKind::Tuple(tup) => self.eval_tup(tup.len()),
            ExprKind::UnOp(op, _) => self.eval_unop(*op),
            ExprKind::UpdateField(_, field, _) => {
                self.eval_update_field(field.clone());
            }
            ExprKind::Var(res, _) => {
                self.set_val_register(resolve_binding(env, self.package, *res, expr.span)?);
            }
            ExprKind::While(..) => {
                panic!("while expr should be handled by control flow")
            }
        }

        Ok(())
    }

    fn collect_string(&mut self, components: &[StringComponent]) {
        if let [StringComponent::Lit(str)] = components {
            self.set_val_register(Value::String(Rc::clone(str)));
            return;
        }

        let mut string = String::new();
        for component in components.iter().rev() {
            match component {
                StringComponent::Expr(..) => {
                    let expr_str = format!("{}", self.pop_val());
                    string.insert_str(0, &expr_str);
                }
                StringComponent::Lit(lit) => {
                    string.insert_str(0, lit);
                }
            }
        }
        self.set_val_register(Value::String(Rc::from(string)));
    }

    fn eval_arr(&mut self, len: usize) {
        let arr = self.pop_vals(len);
        self.set_val_register(Value::Array(arr.into()));
    }

    fn eval_arr_lit(&mut self, arr: &Vec<ExprId>, globals: &impl PackageStoreLookup) {
        let mut new_arr: Rc<Vec<Value>> = Rc::new(Vec::with_capacity(arr.len()));
        for id in arr {
            let ExprKind::Lit(lit) = &globals.get_expr((self.package, *id).into()).kind else {
                panic!("expr kind should be lit")
            };
            Rc::get_mut(&mut new_arr)
                .expect("array should be uniquely referenced")
                .push(lit_to_val(lit));
        }
        self.set_val_register(Value::Array(new_arr));
    }

    fn eval_array_append_in_place(
        &mut self,
        env: &mut Env,
        globals: &impl PackageStoreLookup,
        lhs: ExprId,
    ) -> Result<(), Error> {
        let lhs = globals.get_expr((self.package, lhs).into());
        let rhs = self.take_val_register();
        match (&lhs.kind, rhs) {
            (&ExprKind::Var(Res::Local(id), _), rhs) => match env.get_mut(id) {
                Some(var) => {
                    var.value.append_array(rhs);
                }
                None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
            },
            _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
        }
        Ok(())
    }

    fn eval_arr_repeat(&mut self, span: Span) -> Result<(), Error> {
        let size_val = self.take_val_register().unwrap_int();
        let item_val = self.pop_val();
        let s = match size_val.try_into() {
            Ok(i) => Ok(i),
            Err(_) => Err(Error::InvalidArrayLength(
                size_val,
                self.to_global_span(span),
            )),
        }?;
        self.set_val_register(Value::Array(vec![item_val; s].into()));
        Ok(())
    }

    fn eval_assign(
        &mut self,
        env: &mut Env,
        globals: &impl PackageStoreLookup,
        lhs: ExprId,
    ) -> Result<(), Error> {
        let rhs = self.take_val_register();
        self.update_binding(env, globals, lhs, rhs)
    }

    fn eval_bind(&mut self, env: &mut Env, globals: &impl PackageStoreLookup, pat: PatId) {
        let val = self.take_val_register();
        self.bind_value(env, globals, pat, val);
    }

    fn eval_binop(&mut self, op: BinOp, span: Span) -> Result<(), Error> {
        match op {
            BinOp::Add => self.eval_binop_simple(eval_binop_add),
            BinOp::AndB => self.eval_binop_simple(eval_binop_andb),
            BinOp::Div => self.eval_binop_with_error(span, eval_binop_div)?,
            BinOp::Eq => self.eval_binop_with_error(span, eval_binop_eq)?,
            BinOp::Exp => self.eval_binop_with_error(span, eval_binop_exp)?,
            BinOp::Gt => self.eval_binop_simple(eval_binop_gt),
            BinOp::Gte => self.eval_binop_simple(eval_binop_gte),
            BinOp::Lt => self.eval_binop_simple(eval_binop_lt),
            BinOp::Lte => self.eval_binop_simple(eval_binop_lte),
            BinOp::Mod => self.eval_binop_with_error(span, eval_binop_mod)?,
            BinOp::Mul => self.eval_binop_simple(eval_binop_mul),
            BinOp::Neq => self.eval_binop_with_error(span, eval_binop_neq)?,
            BinOp::OrB => self.eval_binop_simple(eval_binop_orb),
            BinOp::Shl => self.eval_binop_with_error(span, eval_binop_shl)?,
            BinOp::Shr => self.eval_binop_with_error(span, eval_binop_shr)?,
            BinOp::Sub => self.eval_binop_simple(eval_binop_sub),
            BinOp::XorB => self.eval_binop_simple(eval_binop_xorb),

            // Logical operators should be handled by control flow
            BinOp::AndL | BinOp::OrL => {}
        }
        Ok(())
    }

    fn eval_binop_simple(&mut self, binop_func: impl FnOnce(Value, Value) -> Value) {
        let rhs_val = self.take_val_register();
        let lhs_val = self.pop_val();
        self.set_val_register(binop_func(lhs_val, rhs_val));
    }

    fn eval_binop_with_error(
        &mut self,
        span: Span,
        binop_func: impl FnOnce(Value, Value, PackageSpan) -> Result<Value, Error>,
    ) -> Result<(), Error> {
        let span = self.to_global_span(span);
        let rhs_val = self.take_val_register();
        let lhs_val = self.pop_val();
        self.set_val_register(binop_func(lhs_val, rhs_val, span)?);
        Ok(())
    }

    fn eval_call(
        &mut self,
        env: &mut Env,
        sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
        globals: &impl PackageStoreLookup,
        callable_span: Span,
        arg_span: Span,
        out: &mut impl Receiver,
    ) -> Result<(), Error> {
        let arg = self.take_val_register();
        let (callee_id, functor, fixed_args) = match self.pop_val() {
            Value::Closure(inner) => (inner.id, inner.functor, Some(inner.fixed_args)),
            Value::Global(id, functor) => (id, functor, None),
            _ => panic!("value is not callable"),
        };

        let arg_span = self.to_global_span(arg_span);

        let callee = match globals.get_global(callee_id) {
            Some(Global::Callable(callable)) => callable,
            Some(Global::Udt) => {
                self.set_val_register(arg);
                return Ok(());
            }
            None => return Err(Error::UnboundName(self.to_global_span(callable_span))),
        };

        let callee_span = self.to_global_span(callee.span);

        let spec = spec_from_functor_app(functor);
        match &callee.implementation {
            CallableImpl::Intrinsic if is_counting_call(&callee.name.name) => {
                self.push_frame(Vec::new().into(), callee_id, functor);

                let val = self.counting_call(&callee.name.name, arg, arg_span)?;

                self.set_val_register(val);
                self.leave_frame();
                Ok(())
            }
            CallableImpl::Intrinsic => self.eval_intrinsic(
                env,
                callee_id,
                functor,
                callee,
                sim,
                callee_span,
                arg,
                arg_span,
                out,
            ),
            CallableImpl::Spec(specialized_implementation) => {
                let spec_decl = match spec {
                    Spec::Body => Some(&specialized_implementation.body),
                    Spec::Adj => specialized_implementation.adj.as_ref(),
                    Spec::Ctl => specialized_implementation.ctl.as_ref(),
                    Spec::CtlAdj => specialized_implementation.ctl_adj.as_ref(),
                }
                .expect("missing specialization should be a compilation error");
                self.push_frame(spec_decl.exec_graph.clone(), callee_id, functor);
                self.push_scope(env);
                self.increment_call_count(callee_id, functor);

                self.bind_args_for_spec(
                    env,
                    globals,
                    callee.input,
                    spec_decl.input,
                    arg,
                    arg_span,
                    functor.controlled,
                    fixed_args,
                )?;
                Ok(())
            }
            CallableImpl::SimulatableIntrinsic(spec_decl) => {
                self.push_frame(spec_decl.exec_graph.clone(), callee_id, functor);
                self.push_scope(env);

                self.bind_args_for_spec(
                    env,
                    globals,
                    callee.input,
                    spec_decl.input,
                    arg,
                    arg_span,
                    functor.controlled,
                    fixed_args,
                )?;
                Ok(())
            }
        }
    }

    #[allow(clippy::too_many_arguments)]
    fn eval_intrinsic(
        &mut self,
        env: &mut Env,
        callee_id: StoreItemId,
        functor: FunctorApp,
        callee: &fir::CallableDecl,
        sim: &mut impl Backend<ResultType = impl Into<val::Result>>,
        callee_span: PackageSpan,
        arg: Value,
        arg_span: PackageSpan,
        out: &mut impl Receiver,
    ) -> Result<(), Error> {
        self.push_frame(Vec::new().into(), callee_id, functor);
        self.increment_call_count(callee_id, functor);
        let name = &callee.name.name;
        let val = match name.as_ref() {
            "__quantum__rt__qubit_allocate" => {
                let q = Rc::new(Qubit(sim.qubit_allocate()));
                env.track_qubit(Rc::clone(&q));
                if let Some(counter) = &mut self.qubit_counter {
                    counter.allocated(q.0);
                }
                Value::Qubit(q.into())
            }
            "__quantum__rt__qubit_release" => {
                let qubit = arg
                    .unwrap_qubit()
                    .try_deref()
                    .ok_or(Error::QubitDoubleRelease(arg_span))?;
                env.release_qubit(&qubit);
                if sim.qubit_release(qubit.0) {
                    Value::unit()
                } else {
                    return Err(Error::ReleasedQubitNotZero(qubit.0, arg_span));
                }
            }
            _ => {
                let val = intrinsic::call(
                    name,
                    callee_span,
                    arg,
                    arg_span,
                    sim,
                    &mut self.rng.borrow_mut(),
                    out,
                )?;
                if val == Value::unit() && callee.output != Ty::UNIT {
                    return Err(Error::UnsupportedIntrinsicType(
                        callee.name.name.to_string(),
                        callee_span,
                    ));
                }
                val
            }
        };
        self.set_val_register(val);
        self.leave_frame();
        Ok(())
    }

    fn eval_field(&mut self, field: Field) {
        let record = self.take_val_register();
        let val = match (record, field) {
            (Value::Range(inner), Field::Prim(PrimField::Start)) => Value::Int(
                inner
                    .start
                    .expect("range access should be validated by compiler"),
            ),
            (Value::Range(inner), Field::Prim(PrimField::Step)) => Value::Int(inner.step),
            (Value::Range(inner), Field::Prim(PrimField::End)) => Value::Int(
                inner
                    .end
                    .expect("range access should be validated by compiler"),
            ),
            (record, Field::Path(path)) => {
                follow_field_path(record, &path.indices).expect("field path should be valid")
            }
            (ref value, ref field) => {
                panic!("invalid field access. value: {value:?}, field: {field:?}")
            }
        };
        self.set_val_register(val);
    }

    fn eval_index(&mut self, span: Span) -> Result<(), Error> {
        let index_val = self.take_val_register();
        let arr = self.pop_val().unwrap_array();
        match &index_val {
            Value::Int(i) => {
                self.set_val_register(index_array(&arr, *i, self.to_global_span(span))?);
            }
            Value::Range(inner) => {
                self.set_val_register(slice_array(
                    &arr,
                    inner.start,
                    inner.step,
                    inner.end,
                    self.to_global_span(span),
                )?);
            }
            _ => panic!("array should only be indexed by Int or Range"),
        }
        Ok(())
    }

    fn eval_range(&mut self, has_start: bool, has_step: bool, has_end: bool) {
        let end = if has_end {
            Some(self.take_val_register().unwrap_int())
        } else {
            None
        };
        let step = if has_step {
            self.pop_val().unwrap_int()
        } else {
            val::DEFAULT_RANGE_STEP
        };
        let start = if has_start {
            Some(self.pop_val().unwrap_int())
        } else {
            None
        };
        self.set_val_register(Value::Range(val::Range { start, step, end }.into()));
    }

    fn eval_struct(&mut self, copy: Option<ExprId>, fields: &[FieldAssign]) {
        // Extract a flat list of field indexes.
        let field_indexes = fields
            .iter()
            .map(|f| match &f.field {
                Field::Path(path) => match path.indices.as_slice() {
                    &[i] => i,
                    _ => panic!("field path for struct should have a single index"),
                },
                _ => panic!("invalid field for struct"),
            })
            .collect::<Vec<_>>();

        let len = fields.len();

        let (field_vals, mut strct) = if copy.is_some() {
            // Get the field values and the copy struct value.
            let field_vals = self.pop_vals(len + 1);
            let (copy, field_vals) = field_vals.split_first().expect("copy value is expected");

            // Make a clone of the copy struct value.
            (field_vals.to_vec(), copy.clone().unwrap_tuple().to_vec())
        } else {
            // Make an empty struct of the appropriate size.
            (self.pop_vals(len), vec![Value::Int(0); len])
        };

        // Insert the field values into the new struct.
        assert!(
            field_vals.len() == field_indexes.len(),
            "number of given field values should match the number of given struct fields"
        );
        for (i, val) in field_indexes.iter().zip(field_vals.into_iter()) {
            strct[*i] = val;
        }

        self.set_val_register(Value::Tuple(strct.into()));
    }

    fn eval_update_index(&mut self, span: Span) -> Result<(), Error> {
        let values = self.take_val_register().unwrap_array();
        let update = self.pop_val();
        let index = self.pop_val();
        let span = self.to_global_span(span);
        match index {
            Value::Int(index) => self.eval_update_index_single(&values, index, update, span),
            Value::Range(inner) => self.eval_update_index_range(
                &values,
                inner.start,
                inner.step,
                inner.end,
                update,
                span,
            ),
            _ => unreachable!("array should only be indexed by Int or Range"),
        }
    }

    fn eval_update_index_single(
        &mut self,
        values: &[Value],
        index: i64,
        update: Value,
        span: PackageSpan,
    ) -> Result<(), Error> {
        let updated_array = update_index_single(values, index, update, span)?;
        self.set_val_register(updated_array);
        Ok(())
    }

    fn eval_update_index_range(
        &mut self,
        values: &[Value],
        start: Option<i64>,
        step: i64,
        end: Option<i64>,
        update: Value,
        span: PackageSpan,
    ) -> Result<(), Error> {
        let updated_array = update_index_range(values, start, step, end, update, span)?;
        self.set_val_register(updated_array);
        Ok(())
    }

    fn eval_update_index_in_place(
        &mut self,
        env: &mut Env,
        globals: &impl PackageStoreLookup,
        lhs: ExprId,
        span: Span,
    ) -> Result<(), Error> {
        let update = self.take_val_register();
        let index = self.pop_val();
        let span = self.to_global_span(span);
        match index {
            Value::Int(index) => {
                if index < 0 {
                    return Err(Error::InvalidNegativeInt(index, span));
                }
                let i = index.as_index(span)?;
                self.update_array_index_single(env, globals, lhs, span, i, update)
            }
            range @ Value::Range(..) => {
                self.update_array_index_range(env, globals, lhs, span, &range, update)
            }
            _ => unreachable!("array should only be indexed by Int or Range"),
        }
    }

    fn eval_tup(&mut self, len: usize) {
        let tup = self.pop_vals(len);
        self.set_val_register(Value::Tuple(tup.into()));
    }

    fn eval_unop(&mut self, op: UnOp) {
        let val = self.take_val_register();
        match op {
            UnOp::Functor(functor) => match val {
                Value::Closure(inner) => {
                    self.set_val_register(Value::Closure(
                        val::Closure {
                            functor: update_functor_app(functor, inner.functor),
                            ..*inner
                        }
                        .into(),
                    ));
                }
                Value::Global(id, app) => {
                    self.set_val_register(Value::Global(id, update_functor_app(functor, app)));
                }
                _ => panic!("value should be callable"),
            },
            UnOp::Neg => match val {
                Value::BigInt(v) => self.set_val_register(Value::BigInt(v.neg())),
                Value::Double(v) => self.set_val_register(Value::Double(v.neg())),
                Value::Int(v) => self.set_val_register(Value::Int(v.wrapping_neg())),
                _ => panic!("value should be number"),
            },
            UnOp::NotB => match val {
                Value::Int(v) => self.set_val_register(Value::Int(!v)),
                Value::BigInt(v) => self.set_val_register(Value::BigInt(!v)),
                _ => panic!("value should be Int or BigInt"),
            },
            UnOp::NotL => match val {
                Value::Bool(b) => self.set_val_register(Value::Bool(!b)),
                _ => panic!("value should be bool"),
            },
            UnOp::Pos => match val {
                Value::BigInt(_) | Value::Int(_) | Value::Double(_) => self.set_val_register(val),
                _ => panic!("value should be number"),
            },
            UnOp::Unwrap => self.set_val_register(val),
        }
    }

    fn eval_update_field(&mut self, field: Field) {
        let record = self.take_val_register();
        let value = self.pop_val();
        let update = match (record, field) {
            (Value::Range(mut inner), Field::Prim(PrimField::Start)) => {
                inner.start = Some(value.unwrap_int());
                Value::Range(inner)
            }
            (Value::Range(mut inner), Field::Prim(PrimField::Step)) => {
                inner.step = value.unwrap_int();
                Value::Range(inner)
            }
            (Value::Range(mut inner), Field::Prim(PrimField::End)) => {
                inner.end = Some(value.unwrap_int());
                Value::Range(inner)
            }
            (record, Field::Path(path)) => update_field_path(&record, &path.indices, &value)
                .expect("field path should be valid"),
            _ => panic!("invalid field access"),
        };
        self.set_val_register(update);
    }

    fn bind_value(&self, env: &mut Env, globals: &impl PackageStoreLookup, pat: PatId, val: Value) {
        let pat = globals.get_pat((self.package, pat).into());
        match &pat.kind {
            PatKind::Bind(variable) => {
                let scope = env.scopes.last_mut().expect("binding should have a scope");
                scope.bindings.insert(
                    variable.id,
                    Variable {
                        name: variable.name.clone(),
                        value: val,
                        span: variable.span,
                    },
                );
            }
            PatKind::Discard => {}
            PatKind::Tuple(tup) => {
                let val_tup = val.unwrap_tuple();
                for (pat, val) in tup.iter().zip(val_tup.iter()) {
                    self.bind_value(env, globals, *pat, val.clone());
                }
            }
        }
    }

    #[allow(clippy::similar_names)]
    fn update_binding(
        &self,
        env: &mut Env,
        globals: &impl PackageStoreLookup,
        lhs: ExprId,
        rhs: Value,
    ) -> Result<(), Error> {
        let lhs = globals.get_expr((self.package, lhs).into());
        match (&lhs.kind, rhs) {
            (ExprKind::Hole, _) => {}
            (&ExprKind::Var(Res::Local(id), _), rhs) => match env.get_mut(id) {
                Some(var) => {
                    var.value = rhs;
                }
                None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
            },
            (ExprKind::Tuple(var_tup), Value::Tuple(tup)) => {
                for (expr, val) in var_tup.iter().zip(tup.iter()) {
                    self.update_binding(env, globals, *expr, val.clone())?;
                }
            }
            _ => unreachable!("unassignable pattern should be disallowed by compiler"),
        }
        Ok(())
    }

    fn update_array_index_single(
        &mut self,
        env: &mut Env,
        globals: &impl PackageStoreLookup,
        lhs: ExprId,
        span: PackageSpan,
        index: usize,
        rhs: Value,
    ) -> Result<(), Error> {
        let lhs = globals.get_expr((self.package, lhs).into());
        match &lhs.kind {
            &ExprKind::Var(Res::Local(id), _) => match env.get_mut(id) {
                Some(var) => {
                    var.value.update_array(index, rhs).map_err(|idx| {
                        Error::IndexOutOfRange(idx.try_into().expect("index should be valid"), span)
                    })?;
                }
                None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
            },
            _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
        }
        Ok(())
    }

    #[allow(clippy::similar_names)] // `env` and `end` are similar but distinct
    fn update_array_index_range(
        &mut self,
        env: &mut Env,
        globals: &impl PackageStoreLookup,
        lhs: ExprId,
        range_span: PackageSpan,
        range: &Value,
        update: Value,
    ) -> Result<(), Error> {
        let lhs = globals.get_expr((self.package, lhs).into());
        match &lhs.kind {
            &ExprKind::Var(Res::Local(id), _) => match env.get_mut(id) {
                Some(var) => {
                    let rhs = update.unwrap_array();
                    let Value::Array(arr) = &mut var.value else {
                        panic!("variable should be an array");
                    };
                    let Value::Range(inner) = range else {
                        unreachable!("range should be a Value::Range");
                    };
                    let range = make_range(arr, inner.start, inner.step, inner.end, range_span)?;
                    for (idx, rhs) in range.into_iter().zip(rhs.iter()) {
                        if idx < 0 {
                            return Err(Error::InvalidNegativeInt(idx, range_span));
                        }
                        let i = idx.as_index(range_span)?;
                        var.value.update_array(i, rhs.clone()).map_err(|idx| {
                            Error::IndexOutOfRange(
                                idx.try_into().expect("index should be valid"),
                                range_span,
                            )
                        })?;
                    }
                }
                None => return Err(Error::UnboundName(self.to_global_span(lhs.span))),
            },
            _ => unreachable!("unassignable array update pattern should be disallowed by compiler"),
        }
        Ok(())
    }

    #[allow(clippy::too_many_arguments)]
    fn bind_args_for_spec(
        &self,
        env: &mut Env,
        globals: &impl PackageStoreLookup,
        decl_pat: PatId,
        spec_pat: Option<PatId>,
        args_val: Value,
        args_span: PackageSpan,
        ctl_count: u8,
        fixed_args: Option<Rc<[Value]>>,
    ) -> Result<(), Error> {
        match spec_pat {
            Some(spec_pat) => {
                assert!(
                    ctl_count > 0,
                    "spec pattern tuple used without controlled functor"
                );

                let mut tup = args_val;
                let mut ctls = vec![];
                for _ in 0..ctl_count {
                    let [c, rest] = &*tup.unwrap_tuple() else {
                        panic!("tuple should be arity 2");
                    };
                    ctls.extend_from_slice(&c.clone().unwrap_array());
                    tup = rest.clone();
                }

                if !are_ctls_unique(&ctls, &tup) {
                    return Err(Error::QubitUniqueness(args_span));
                }

                self.bind_value(env, globals, spec_pat, Value::Array(ctls.into()));
                self.bind_value(env, globals, decl_pat, merge_fixed_args(fixed_args, tup));
            }
            None => self.bind_value(
                env,
                globals,
                decl_pat,
                merge_fixed_args(fixed_args, args_val),
            ),
        }
        Ok(())
    }

    fn to_global_span(&self, span: Span) -> PackageSpan {
        PackageSpan {
            package: map_fir_package_to_hir(self.package),
            span,
        }
    }

    fn counting_call(&mut self, name: &str, arg: Value, span: PackageSpan) -> Result<Value, Error> {
        let counting_key = |arg: Value| match arg {
            Value::Closure(closure) => make_counting_key(closure.id, closure.functor),
            Value::Global(id, functor) => make_counting_key(id, functor),
            _ => panic!("value should be callable"),
        };
        match name {
            "StartCountingOperation" | "StartCountingFunction" => {
                if self.call_counts.insert(counting_key(arg), 0).is_some() {
                    Err(Error::CallableAlreadyCounted(span))
                } else {
                    Ok(Value::unit())
                }
            }
            "StopCountingOperation" | "StopCountingFunction" => {
                if let Some(count) = self.call_counts.remove(&counting_key(arg)) {
                    Ok(Value::Int(count))
                } else {
                    Err(Error::CallableNotCounted(span))
                }
            }
            "StartCountingQubits" => {
                if self
                    .qubit_counter
                    .replace(QubitCounter::default())
                    .is_some()
                {
                    Err(Error::QubitsAlreadyCounted(span))
                } else {
                    Ok(Value::unit())
                }
            }
            "StopCountingQubits" => {
                if let Some(qubit_counter) = self.qubit_counter.take() {
                    Ok(Value::Int(qubit_counter.into_count()))
                } else {
                    Err(Error::QubitsNotCounted(span))
                }
            }
            _ => panic!("unknown counting call"),
        }
    }

    fn increment_call_count(&mut self, callee_id: StoreItemId, functor: FunctorApp) {
        if let Some(count) = self
            .call_counts
            .get_mut(&make_counting_key(callee_id, functor))
        {
            *count += 1;
        }
    }
}

pub fn are_ctls_unique(ctls: &[Value], tup: &Value) -> bool {
    let mut qubits = FxHashSet::default();
    for ctl in ctls.iter().flat_map(Value::qubits) {
        if let Some(ctl) = ctl.try_deref() {
            if !qubits.insert(ctl) {
                return false;
            }
        }
    }
    for qubit in tup.qubits() {
        if let Some(qubit) = qubit.try_deref() {
            if qubits.contains(&qubit) {
                return false;
            }
        }
    }
    true
}

fn merge_fixed_args(fixed_args: Option<Rc<[Value]>>, arg: Value) -> Value {
    if let Some(fixed_args) = fixed_args {
        Value::Tuple(fixed_args.iter().cloned().chain(iter::once(arg)).collect())
    } else {
        arg
    }
}

fn resolve_binding(env: &Env, package: PackageId, res: Res, span: Span) -> Result<Value, Error> {
    Ok(match res {
        Res::Err => panic!("resolution error"),
        Res::Item(item) => Value::Global(
            StoreItemId {
                package: item.package.unwrap_or(package),
                item: item.item,
            },
            FunctorApp::default(),
        ),
        Res::Local(id) => env
            .get(id)
            .ok_or(Error::UnboundName(PackageSpan {
                package: map_fir_package_to_hir(package),
                span,
            }))?
            .value
            .clone(),
    })
}

fn spec_from_functor_app(functor: FunctorApp) -> Spec {
    match (functor.adjoint, functor.controlled) {
        (false, 0) => Spec::Body,
        (true, 0) => Spec::Adj,
        (false, _) => Spec::Ctl,
        (true, _) => Spec::CtlAdj,
    }
}

pub fn resolve_closure(
    env: &Env,
    package: PackageId,
    span: Span,
    args: &[LocalVarId],
    callable: LocalItemId,
) -> Result<Value, Error> {
    let args: Option<_> = args
        .iter()
        .map(|&arg| Some(env.get(arg)?.value.clone()))
        .collect();
    let args: Vec<_> = args.ok_or(Error::UnboundName(PackageSpan {
        package: map_fir_package_to_hir(package),
        span,
    }))?;
    let callable = StoreItemId {
        package,
        item: callable,
    };
    Ok(Value::Closure(
        val::Closure {
            fixed_args: args.into(),
            id: callable,
            functor: FunctorApp::default(),
        }
        .into(),
    ))
}

fn lit_to_val(lit: &Lit) -> Value {
    match lit {
        Lit::BigInt(v) => Value::BigInt(v.clone()),
        Lit::Bool(v) => Value::Bool(*v),
        Lit::Double(v) => Value::Double(*v),
        Lit::Int(v) => Value::Int(*v),
        Lit::Pauli(v) => Value::Pauli(*v),
        Lit::Result(fir::Result::Zero) => Value::RESULT_ZERO,
        Lit::Result(fir::Result::One) => Value::RESULT_ONE,
    }
}

fn eval_binop_eq(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
    match (lhs_val, rhs_val) {
        (Value::Result(val::Result::Id(_)), _) | (_, Value::Result(val::Result::Id(_))) => {
            // Comparison of result ids is nonsensical, so we prevent it.
            // This code path is reachable when using the circuit builder backend
            // since we don't currently do runtime capability analysis
            // to prevent executing programs that do result comparisons.
            Err(Error::ResultComparisonUnsupported(rhs_span))
        }
        (Value::Result(val::Result::Loss), _) | (_, Value::Result(val::Result::Loss)) => {
            // Loss is not comparable and should be checked ahead of time, so treat this as a runtime
            // failure.
            Err(Error::ResultLossComparisonUnsupported(rhs_span))
        }
        (lhs, rhs) => Ok(Value::Bool(lhs == rhs)),
    }
}

fn eval_binop_neq(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
    match (lhs_val, rhs_val) {
        (Value::Result(val::Result::Id(_)), _) | (_, Value::Result(val::Result::Id(_))) => {
            // Comparison of result ids is nonsensical, so we prevent it.
            // This code path is reachable when using the circuit builder backend
            // since we don't currently do runtime capability analysis
            // to prevent executing programs that do result comparisons.
            Err(Error::ResultComparisonUnsupported(rhs_span))
        }
        (Value::Result(val::Result::Loss), _) | (_, Value::Result(val::Result::Loss)) => {
            // Loss is not comparable and should be checked ahead of time, so treat this as a runtime
            // failure.
            Err(Error::ResultLossComparisonUnsupported(rhs_span))
        }
        (lhs, rhs) => Ok(Value::Bool(lhs != rhs)),
    }
}

fn eval_binop_add(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::Array(arr) => {
            let rhs_arr = rhs_val.unwrap_array();
            let items: Vec<_> = arr.iter().cloned().chain(rhs_arr.iter().cloned()).collect();
            Value::Array(items.into())
        }
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::BigInt(val + rhs)
        }
        Value::Double(val) => {
            let rhs = rhs_val.unwrap_double();
            Value::Double(val + rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Int(val.wrapping_add(rhs))
        }
        Value::String(val) => {
            let rhs = rhs_val.unwrap_string();
            Value::String((val.to_string() + &rhs).into())
        }
        _ => panic!("value is not addable: {}", lhs_val.type_name()),
    }
}

fn eval_binop_andb(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::BigInt(val & rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Int(val & rhs)
        }
        _ => panic!("value type does not support andb"),
    }
}

fn eval_binop_div(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            if rhs == BigInt::from(0) {
                Err(Error::DivZero(rhs_span))
            } else {
                Ok(Value::BigInt(val / rhs))
            }
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            if rhs == 0 {
                Err(Error::DivZero(rhs_span))
            } else {
                Ok(Value::Int(val.wrapping_div(rhs)))
            }
        }
        Value::Double(val) => {
            let rhs = rhs_val.unwrap_double();
            Ok(Value::Double(val / rhs))
        }
        _ => panic!("value should support div"),
    }
}

fn eval_binop_exp(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs_val = rhs_val.unwrap_int();
            if rhs_val < 0 {
                Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
            } else {
                let rhs_val: u32 = match rhs_val.try_into() {
                    Ok(v) => Ok(v),
                    Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
                }?;
                Ok(Value::BigInt(val.pow(rhs_val)))
            }
        }
        Value::Double(val) => Ok(Value::Double(val.powf(rhs_val.unwrap_double()))),
        Value::Int(val) => {
            let rhs_val = rhs_val.unwrap_int();
            if rhs_val < 0 {
                Err(Error::InvalidNegativeInt(rhs_val, rhs_span))
            } else {
                let result: i64 = match rhs_val.try_into() {
                    Ok(v) => val
                        .checked_pow(v)
                        .ok_or(Error::IntTooLarge(rhs_val, rhs_span)),
                    Err(_) => Err(Error::IntTooLarge(rhs_val, rhs_span)),
                }?;
                Ok(Value::Int(result))
            }
        }
        _ => panic!("value should support exp"),
    }
}

fn eval_binop_gt(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::Bool(val > rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Bool(val > rhs)
        }
        Value::Double(val) => {
            let rhs = rhs_val.unwrap_double();
            Value::Bool(val > rhs)
        }
        _ => panic!("value doesn't support binop gt"),
    }
}

fn eval_binop_gte(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::Bool(val >= rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Bool(val >= rhs)
        }
        Value::Double(val) => {
            let rhs = rhs_val.unwrap_double();
            Value::Bool(val >= rhs)
        }
        _ => panic!("value doesn't support binop gte"),
    }
}

fn eval_binop_lt(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::Bool(val < rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Bool(val < rhs)
        }
        Value::Double(val) => {
            let rhs = rhs_val.unwrap_double();
            Value::Bool(val < rhs)
        }
        _ => panic!("value doesn't support binop lt"),
    }
}

fn eval_binop_lte(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::Bool(val <= rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Bool(val <= rhs)
        }
        Value::Double(val) => {
            let rhs = rhs_val.unwrap_double();
            Value::Bool(val <= rhs)
        }
        _ => panic!("value doesn't support binop lte"),
    }
}

fn eval_binop_mod(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            if rhs == BigInt::from(0) {
                Err(Error::DivZero(rhs_span))
            } else {
                Ok(Value::BigInt(val % rhs))
            }
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            if rhs == 0 {
                Err(Error::DivZero(rhs_span))
            } else {
                Ok(Value::Int(val.wrapping_rem(rhs)))
            }
        }
        Value::Double(val) => {
            let rhs = rhs_val.unwrap_double();
            if rhs == 0.0 {
                Err(Error::DivZero(rhs_span))
            } else {
                Ok(Value::Double(val % rhs))
            }
        }
        _ => panic!("value should support mod"),
    }
}

fn eval_binop_mul(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::BigInt(val * rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Int(val.wrapping_mul(rhs))
        }
        Value::Double(val) => {
            let rhs = rhs_val.unwrap_double();
            Value::Double(val * rhs)
        }
        _ => panic!("value should support mul"),
    }
}

fn eval_binop_orb(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::BigInt(val | rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Int(val | rhs)
        }
        _ => panic!("value type does not support orb"),
    }
}

fn eval_binop_shl(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
    Ok(match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_int();
            if rhs > 0 {
                Value::BigInt(val << rhs)
            } else {
                Value::BigInt(val >> rhs.abs())
            }
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Int(if rhs > 0 {
                let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
                val.checked_shl(shift)
                    .ok_or(Error::IntTooLarge(rhs, rhs_span))?
            } else {
                let shift: u32 = rhs
                    .checked_neg()
                    .ok_or(Error::IntTooLarge(rhs, rhs_span))?
                    .try_into()
                    .or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
                val.checked_shr(shift)
                    .ok_or(Error::IntTooLarge(rhs, rhs_span))?
            })
        }
        _ => panic!("value should support shl"),
    })
}

fn eval_binop_shr(lhs_val: Value, rhs_val: Value, rhs_span: PackageSpan) -> Result<Value, Error> {
    Ok(match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_int();
            if rhs > 0 {
                Value::BigInt(val >> rhs)
            } else {
                Value::BigInt(val << rhs.abs())
            }
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Int(if rhs > 0 {
                let shift: u32 = rhs.try_into().or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
                val.checked_shr(shift)
                    .ok_or(Error::IntTooLarge(rhs, rhs_span))?
            } else {
                let shift: u32 = rhs
                    .checked_neg()
                    .ok_or(Error::IntTooLarge(rhs, rhs_span))?
                    .try_into()
                    .or(Err(Error::IntTooLarge(rhs, rhs_span)))?;
                val.checked_shl(shift)
                    .ok_or(Error::IntTooLarge(rhs, rhs_span))?
            })
        }
        _ => panic!("value should support shr"),
    })
}

fn eval_binop_sub(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::BigInt(val - rhs)
        }
        Value::Double(val) => {
            let rhs = rhs_val.unwrap_double();
            Value::Double(val - rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Int(val.wrapping_sub(rhs))
        }
        _ => panic!("value is not subtractable"),
    }
}

fn eval_binop_xorb(lhs_val: Value, rhs_val: Value) -> Value {
    match lhs_val {
        Value::BigInt(val) => {
            let rhs = rhs_val.unwrap_big_int();
            Value::BigInt(val ^ rhs)
        }
        Value::Int(val) => {
            let rhs = rhs_val.unwrap_int();
            Value::Int(val ^ rhs)
        }
        _ => panic!("value type does not support xorb"),
    }
}

fn follow_field_path(mut value: Value, path: &[usize]) -> Option<Value> {
    for &index in path {
        let Value::Tuple(items) = value else {
            return None;
        };
        value = items[index].clone();
    }
    Some(value)
}

fn update_field_path(record: &Value, path: &[usize], replace: &Value) -> Option<Value> {
    match (record, path) {
        (_, []) => Some(replace.clone()),
        (Value::Tuple(items), &[next_index, ..]) if next_index < items.len() => {
            let update = |(index, item)| {
                if index == next_index {
                    update_field_path(item, &path[1..], replace)
                } else {
                    Some(item.clone())
                }
            };

            let items: Option<_> = items.iter().enumerate().map(update).collect();
            Some(Value::Tuple(items?))
        }
        _ => None,
    }
}

fn is_updatable_in_place(env: &Env, expr: &Expr) -> (bool, bool) {
    match &expr.kind {
        ExprKind::Var(Res::Local(id), _) => match env.get(*id) {
            Some(var) => match &var.value {
                Value::Array(var) => (true, Rc::weak_count(var) + Rc::strong_count(var) == 1),
                _ => (false, false),
            },
            _ => (false, false),
        },
        _ => (false, false),
    }
}

fn is_counting_call(name: &str) -> bool {
    matches!(
        name,
        "StartCountingOperation"
            | "StopCountingOperation"
            | "StartCountingFunction"
            | "StopCountingFunction"
            | "StartCountingQubits"
            | "StopCountingQubits"
    )
}

fn make_counting_key(id: StoreItemId, functor: FunctorApp) -> CallableCountKey {
    (id, functor.adjoint, functor.controlled > 0)
}

#[derive(Default)]
struct QubitCounter {
    seen: FxHashSet<usize>,
    count: i64,
}

impl QubitCounter {
    fn allocated(&mut self, qubit: usize) {
        if self.seen.insert(qubit) {
            self.count += 1;
        }
    }

    fn into_count(self) -> i64 {
        self.count
    }
}
