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

#[cfg(test)]
mod instruction_tests;

#[cfg(test)]
mod tests;

use qsc_data_structures::attrs::Attributes;
use qsc_data_structures::target::TargetCapabilityFlags;
use qsc_rir::{
    rir::{self, ConditionCode, FcmpConditionCode},
    utils::get_all_block_successors,
};
use std::fmt::Write;

use super::name::llvm_global_name;

/// A trait for converting a type into QIR of type `T`.
/// This can be used to generate QIR strings or other representations.
pub trait ToQir<T> {
    fn to_qir(&self, program: &rir::Program) -> T;
}

impl ToQir<String> for rir::Literal {
    fn to_qir(&self, _program: &rir::Program) -> String {
        match self {
            rir::Literal::Bool(b) => format!("i1 {b}"),
            rir::Literal::Double(d) => {
                if (d.floor() - d.ceil()).abs() < f64::EPSILON {
                    // The value is a whole number, which requires at least one decimal point
                    // to differentiate it from an integer value.
                    format!("double {d:.1}")
                } else {
                    format!("double {d}")
                }
            }
            rir::Literal::Integer(i) => format!("i64 {i}"),
            rir::Literal::NullPointer => "ptr null".to_string(),
            rir::Literal::Qubit(q) => format!("ptr inttoptr (i64 {q} to ptr)"),
            rir::Literal::Result(r) => format!("ptr inttoptr (i64 {r} to ptr)"),
            rir::Literal::Tag(idx, _) => format!("ptr @{idx}"),
            rir::Literal::Array(idx) => format!("ptr @array{idx}"),
        }
    }
}

impl ToQir<String> for rir::Ty {
    fn to_qir(&self, program: &rir::Program) -> String {
        match self {
            rir::Ty::Prim(prim) => ToQir::<String>::to_qir(prim, program),
            rir::Ty::Array(size, elem_ty) => {
                format!("[{size} x {}]", ToQir::<String>::to_qir(elem_ty, program))
            }
        }
    }
}

impl ToQir<String> for rir::Prim {
    fn to_qir(&self, _program: &rir::Program) -> String {
        get_prim_ty(*self).to_owned()
    }
}

impl ToQir<String> for Option<rir::Ty> {
    fn to_qir(&self, program: &rir::Program) -> String {
        match self {
            Some(ty) => ToQir::<String>::to_qir(ty, program),
            None => "void".to_string(),
        }
    }
}

impl ToQir<String> for rir::VariableId {
    fn to_qir(&self, _program: &rir::Program) -> String {
        format!("%var_{}", self.0)
    }
}

impl ToQir<String> for rir::Variable {
    fn to_qir(&self, program: &rir::Program) -> String {
        format!(
            "{} {}",
            ToQir::<String>::to_qir(&self.ty, program),
            ToQir::<String>::to_qir(&self.variable_id, program)
        )
    }
}

impl ToQir<String> for rir::Operand {
    fn to_qir(&self, program: &rir::Program) -> String {
        match self {
            rir::Operand::Literal(lit) => ToQir::<String>::to_qir(lit, program),
            rir::Operand::Variable(var) => ToQir::<String>::to_qir(var, program),
        }
    }
}

impl ToQir<String> for rir::FcmpConditionCode {
    fn to_qir(&self, _program: &rir::Program) -> String {
        match self {
            rir::FcmpConditionCode::False => "false".to_string(),
            rir::FcmpConditionCode::OrderedAndEqual => "oeq".to_string(),
            rir::FcmpConditionCode::OrderedAndGreaterThan => "ogt".to_string(),
            rir::FcmpConditionCode::OrderedAndGreaterThanOrEqual => "oge".to_string(),
            rir::FcmpConditionCode::OrderedAndLessThan => "olt".to_string(),
            rir::FcmpConditionCode::OrderedAndLessThanOrEqual => "ole".to_string(),
            rir::FcmpConditionCode::OrderedAndNotEqual => "one".to_string(),
            rir::FcmpConditionCode::Ordered => "ord".to_string(),
            rir::FcmpConditionCode::UnorderedOrEqual => "ueq".to_string(),
            rir::FcmpConditionCode::UnorderedOrGreaterThan => "ugt".to_string(),
            rir::FcmpConditionCode::UnorderedOrGreaterThanOrEqual => "uge".to_string(),
            rir::FcmpConditionCode::UnorderedOrLessThan => "ult".to_string(),
            rir::FcmpConditionCode::UnorderedOrLessThanOrEqual => "ule".to_string(),
            rir::FcmpConditionCode::UnorderedOrNotEqual => "une".to_string(),
            rir::FcmpConditionCode::Unordered => "uno".to_string(),
            rir::FcmpConditionCode::True => "true".to_string(),
        }
    }
}

impl ToQir<String> for rir::ConditionCode {
    fn to_qir(&self, _program: &rir::Program) -> String {
        match self {
            rir::ConditionCode::Eq => "eq".to_string(),
            rir::ConditionCode::Ne => "ne".to_string(),
            rir::ConditionCode::Sgt => "sgt".to_string(),
            rir::ConditionCode::Sge => "sge".to_string(),
            rir::ConditionCode::Slt => "slt".to_string(),
            rir::ConditionCode::Sle => "sle".to_string(),
        }
    }
}

impl ToQir<String> for rir::Instruction {
    #[allow(clippy::too_many_lines)]
    fn to_qir(&self, program: &rir::Program) -> String {
        match self {
            rir::Instruction::Add(lhs, rhs, variable) => {
                binop_to_qir("add", lhs, rhs, *variable, program)
            }
            rir::Instruction::Ashr(lhs, rhs, variable) => {
                binop_to_qir("ashr", lhs, rhs, *variable, program)
            }
            rir::Instruction::BitwiseAnd(lhs, rhs, variable) => {
                simple_bitwise_to_qir("and", lhs, rhs, *variable, program)
            }
            rir::Instruction::BitwiseNot(value, variable) => {
                bitwise_not_to_qir(value, *variable, program)
            }
            rir::Instruction::BitwiseOr(lhs, rhs, variable) => {
                simple_bitwise_to_qir("or", lhs, rhs, *variable, program)
            }
            rir::Instruction::BitwiseXor(lhs, rhs, variable) => {
                simple_bitwise_to_qir("xor", lhs, rhs, *variable, program)
            }
            rir::Instruction::Branch(cond, true_id, false_id, _) => {
                format!(
                    "  br {}, label %{}, label %{}",
                    ToQir::<String>::to_qir(cond, program),
                    ToQir::<String>::to_qir(true_id, program),
                    ToQir::<String>::to_qir(false_id, program)
                )
            }
            rir::Instruction::Call(call_id, args, output, _) => {
                call_to_qir(args, *call_id, *output, program)
            }
            rir::Instruction::Convert(operand, variable) => {
                convert_to_qir(operand, *variable, program)
            }
            rir::Instruction::Fadd(lhs, rhs, variable) => {
                fbinop_to_qir("fadd", lhs, rhs, *variable, program)
            }
            rir::Instruction::Fdiv(lhs, rhs, variable) => {
                fbinop_to_qir("fdiv", lhs, rhs, *variable, program)
            }
            rir::Instruction::Frem(lhs, rhs, variable) => {
                fbinop_to_qir("frem", lhs, rhs, *variable, program)
            }
            rir::Instruction::Fmul(lhs, rhs, variable) => {
                fbinop_to_qir("fmul", lhs, rhs, *variable, program)
            }
            rir::Instruction::Fsub(lhs, rhs, variable) => {
                fbinop_to_qir("fsub", lhs, rhs, *variable, program)
            }
            rir::Instruction::LogicalAnd(lhs, rhs, variable) => {
                logical_binop_to_qir("and", lhs, rhs, *variable, program)
            }
            rir::Instruction::LogicalNot(value, variable) => {
                logical_not_to_qir(value, *variable, program)
            }
            rir::Instruction::LogicalOr(lhs, rhs, variable) => {
                logical_binop_to_qir("or", lhs, rhs, *variable, program)
            }
            rir::Instruction::Mul(lhs, rhs, variable) => {
                binop_to_qir("mul", lhs, rhs, *variable, program)
            }
            rir::Instruction::Fcmp(op, lhs, rhs, variable) => {
                fcmp_to_qir(*op, lhs, rhs, *variable, program)
            }
            rir::Instruction::Icmp(op, lhs, rhs, variable) => {
                icmp_to_qir(*op, lhs, rhs, *variable, program)
            }
            rir::Instruction::Jump(block_id) => {
                format!("  br label %{}", ToQir::<String>::to_qir(block_id, program))
            }
            rir::Instruction::Phi(..) => {
                unreachable!("phi nodes should not be inserted for QIR v2 generation")
            }
            rir::Instruction::Return(operand) => match operand {
                None => "  ret void".to_string(),
                Some(operand) => format!(
                    "  ret {} {}",
                    get_value_ty(operand),
                    get_value_as_str(operand, program)
                ),
            },
            rir::Instruction::Sdiv(lhs, rhs, variable) => {
                binop_to_qir("sdiv", lhs, rhs, *variable, program)
            }
            rir::Instruction::Shl(lhs, rhs, variable) => {
                binop_to_qir("shl", lhs, rhs, *variable, program)
            }
            rir::Instruction::Srem(lhs, rhs, variable) => {
                binop_to_qir("srem", lhs, rhs, *variable, program)
            }
            rir::Instruction::Store(operand, variable) => {
                store_to_qir(*operand, *variable, program)
            }
            rir::Instruction::Sub(lhs, rhs, variable) => {
                binop_to_qir("sub", lhs, rhs, *variable, program)
            }
            rir::Instruction::Alloca(variable) => alloca_to_qir(*variable, program),
            rir::Instruction::Load(var_from, var_to) => load_to_qir(*var_from, *var_to, program),
            rir::Instruction::Index(array_op, index_op, result_var) => {
                index_to_qir(array_op, index_op, result_var, program)
            }
        }
    }
}

fn index_to_qir(
    array_op: &rir::Operand,
    index_op: &rir::Operand,
    result_var: &rir::Variable,
    program: &rir::Program,
) -> String {
    // Only need to emit the getelementptr instruction here, as passes are expected to insert the subsequent load instruction.
    format!(
        "  {} = getelementptr {}, ptr {}, {} {}",
        ToQir::<String>::to_qir(&result_var.variable_id, program),
        ToQir::<String>::to_qir(&result_var.ty, program),
        get_value_as_str(array_op, program),
        get_value_ty(index_op),
        get_value_as_str(index_op, program)
    )
}

fn convert_to_qir(
    operand: &rir::Operand,
    variable: rir::Variable,
    program: &rir::Program,
) -> String {
    let operand_ty = get_value_ty(operand);
    let var_ty = get_variable_ty(variable);
    assert_ne!(
        operand_ty, var_ty,
        "input/output types ({operand_ty}, {var_ty}) should not match in convert"
    );

    let convert_instr = match (operand_ty.as_str(), var_ty.as_str()) {
        ("i64", "double") => "sitofp i64",
        ("double", "i64") => "fptosi double",
        _ => panic!("unsupported conversion from {operand_ty} to {var_ty} in convert instruction"),
    };

    format!(
        "  {} = {convert_instr} {} to {var_ty}",
        ToQir::<String>::to_qir(&variable.variable_id, program),
        get_value_as_str(operand, program),
    )
}

fn store_to_qir(operand: rir::Operand, variable: rir::Variable, program: &rir::Program) -> String {
    let op_ty = get_value_ty(&operand);
    format!(
        "  store {op_ty} {}, ptr {}",
        get_value_as_str(&operand, program),
        ToQir::<String>::to_qir(&variable.variable_id, program)
    )
}

fn load_to_qir(var_from: rir::Variable, var_to: rir::Variable, program: &rir::Program) -> String {
    let var_to_ty = get_variable_ty(var_to);
    format!(
        "  {} = load {var_to_ty}, ptr {}",
        ToQir::<String>::to_qir(&var_to.variable_id, program),
        ToQir::<String>::to_qir(&var_from.variable_id, program)
    )
}

fn alloca_to_qir(variable: rir::Variable, program: &rir::Program) -> String {
    let variable_ty = get_variable_ty(variable);
    format!(
        "  {} = alloca {variable_ty}",
        ToQir::<String>::to_qir(&variable.variable_id, program)
    )
}

fn logical_not_to_qir(
    value: &rir::Operand,
    variable: rir::Variable,
    program: &rir::Program,
) -> String {
    let value_ty = get_value_ty(value);
    let var_ty = get_variable_ty(variable);
    assert_eq!(
        value_ty, var_ty,
        "mismatched input/output types ({value_ty}, {var_ty}) for not"
    );
    assert_eq!(var_ty, "i1", "unsupported type {var_ty} for not");

    format!(
        "  {} = xor i1 {}, true",
        ToQir::<String>::to_qir(&variable.variable_id, program),
        get_value_as_str(value, program)
    )
}

fn logical_binop_to_qir(
    op: &str,
    lhs: &rir::Operand,
    rhs: &rir::Operand,
    variable: rir::Variable,
    program: &rir::Program,
) -> String {
    let lhs_ty = get_value_ty(lhs);
    let rhs_ty = get_value_ty(rhs);
    let var_ty = get_variable_ty(variable);
    assert_eq!(
        lhs_ty, rhs_ty,
        "mismatched input types ({lhs_ty}, {rhs_ty}) for {op}"
    );
    assert_eq!(
        lhs_ty, var_ty,
        "mismatched input/output types ({lhs_ty}, {var_ty}) for {op}"
    );
    assert_eq!(var_ty, "i1", "unsupported type {var_ty} for {op}");

    format!(
        "  {} = {op} {var_ty} {}, {}",
        ToQir::<String>::to_qir(&variable.variable_id, program),
        get_value_as_str(lhs, program),
        get_value_as_str(rhs, program)
    )
}

fn bitwise_not_to_qir(
    value: &rir::Operand,
    variable: rir::Variable,
    program: &rir::Program,
) -> String {
    let value_ty = get_value_ty(value);
    let var_ty = get_variable_ty(variable);
    assert_eq!(
        value_ty, var_ty,
        "mismatched input/output types ({value_ty}, {var_ty}) for not"
    );
    assert_eq!(var_ty, "i64", "unsupported type {var_ty} for not");

    format!(
        "  {} = xor {var_ty} {}, -1",
        ToQir::<String>::to_qir(&variable.variable_id, program),
        get_value_as_str(value, program)
    )
}

fn call_to_qir(
    args: &[rir::Operand],
    call_id: rir::CallableId,
    output: Option<rir::Variable>,
    program: &rir::Program,
) -> String {
    let args = args
        .iter()
        .map(|arg| ToQir::<String>::to_qir(arg, program))
        .collect::<Vec<_>>()
        .join(", ");
    let callable = program.get_callable(call_id);
    let callable_name = llvm_global_name(&callable.name);
    if let Some(output) = output {
        format!(
            "  {} = call {} {}({args})",
            ToQir::<String>::to_qir(&output.variable_id, program),
            ToQir::<String>::to_qir(&callable.output_type, program),
            callable_name
        )
    } else {
        format!(
            "  call {} {}({args})",
            ToQir::<String>::to_qir(&callable.output_type, program),
            callable_name
        )
    }
}

fn fcmp_to_qir(
    op: FcmpConditionCode,
    lhs: &rir::Operand,
    rhs: &rir::Operand,
    variable: rir::Variable,
    program: &rir::Program,
) -> String {
    let lhs_ty = get_value_ty(lhs);
    let rhs_ty = get_value_ty(rhs);
    let var_ty = get_variable_ty(variable);
    assert_eq!(
        lhs_ty, rhs_ty,
        "mismatched input types ({lhs_ty}, {rhs_ty}) for fcmp {op}"
    );

    assert_eq!(var_ty, "i1", "unsupported output type {var_ty} for fcmp");
    format!(
        "  {} = fcmp {} {lhs_ty} {}, {}",
        ToQir::<String>::to_qir(&variable.variable_id, program),
        ToQir::<String>::to_qir(&op, program),
        get_value_as_str(lhs, program),
        get_value_as_str(rhs, program)
    )
}

fn icmp_to_qir(
    op: ConditionCode,
    lhs: &rir::Operand,
    rhs: &rir::Operand,
    variable: rir::Variable,
    program: &rir::Program,
) -> String {
    let lhs_ty = get_value_ty(lhs);
    let rhs_ty = get_value_ty(rhs);
    let var_ty = get_variable_ty(variable);
    assert_eq!(
        lhs_ty, rhs_ty,
        "mismatched input types ({lhs_ty}, {rhs_ty}) for icmp {op}"
    );

    assert_eq!(var_ty, "i1", "unsupported output type {var_ty} for icmp");
    format!(
        "  {} = icmp {} {lhs_ty} {}, {}",
        ToQir::<String>::to_qir(&variable.variable_id, program),
        ToQir::<String>::to_qir(&op, program),
        get_value_as_str(lhs, program),
        get_value_as_str(rhs, program)
    )
}

fn binop_to_qir(
    op: &str,
    lhs: &rir::Operand,
    rhs: &rir::Operand,
    variable: rir::Variable,
    program: &rir::Program,
) -> String {
    let lhs_ty = get_value_ty(lhs);
    let rhs_ty = get_value_ty(rhs);
    let var_ty = get_variable_ty(variable);
    assert_eq!(
        lhs_ty, rhs_ty,
        "mismatched input types ({lhs_ty}, {rhs_ty}) for {op}"
    );
    assert_eq!(
        lhs_ty, var_ty,
        "mismatched input/output types ({lhs_ty}, {var_ty}) for {op}"
    );
    assert_eq!(var_ty, "i64", "unsupported type {var_ty} for {op}");

    format!(
        "  {} = {op} {var_ty} {}, {}",
        ToQir::<String>::to_qir(&variable.variable_id, program),
        get_value_as_str(lhs, program),
        get_value_as_str(rhs, program)
    )
}

fn fbinop_to_qir(
    op: &str,
    lhs: &rir::Operand,
    rhs: &rir::Operand,
    variable: rir::Variable,
    program: &rir::Program,
) -> String {
    let lhs_ty = get_value_ty(lhs);
    let rhs_ty = get_value_ty(rhs);
    let var_ty = get_variable_ty(variable);
    assert_eq!(
        lhs_ty, rhs_ty,
        "mismatched input types ({lhs_ty}, {rhs_ty}) for {op}"
    );
    assert_eq!(
        lhs_ty, var_ty,
        "mismatched input/output types ({lhs_ty}, {var_ty}) for {op}"
    );
    assert_eq!(var_ty, "double", "unsupported type {var_ty} for {op}");

    format!(
        "  {} = {op} {var_ty} {}, {}",
        ToQir::<String>::to_qir(&variable.variable_id, program),
        get_value_as_str(lhs, program),
        get_value_as_str(rhs, program)
    )
}

fn simple_bitwise_to_qir(
    op: &str,
    lhs: &rir::Operand,
    rhs: &rir::Operand,
    variable: rir::Variable,
    program: &rir::Program,
) -> String {
    let lhs_ty = get_value_ty(lhs);
    let rhs_ty = get_value_ty(rhs);
    let var_ty = get_variable_ty(variable);
    assert_eq!(
        lhs_ty, rhs_ty,
        "mismatched input types ({lhs_ty}, {rhs_ty}) for {op}"
    );
    assert_eq!(
        lhs_ty, var_ty,
        "mismatched input/output types ({lhs_ty}, {var_ty}) for {op}"
    );
    assert_eq!(var_ty, "i64", "unsupported type {var_ty} for {op}");

    format!(
        "  {} = {op} {var_ty} {}, {}",
        ToQir::<String>::to_qir(&variable.variable_id, program),
        get_value_as_str(lhs, program),
        get_value_as_str(rhs, program)
    )
}

fn get_value_as_str(value: &rir::Operand, program: &rir::Program) -> String {
    match value {
        rir::Operand::Literal(lit) => match lit {
            rir::Literal::Bool(b) => format!("{b}"),
            rir::Literal::Double(d) => {
                if (d.floor() - d.ceil()).abs() < f64::EPSILON {
                    // The value is a whole number, which requires at least one decimal point
                    // to differentiate it from an integer value.
                    format!("{d:.1}")
                } else {
                    format!("{d}")
                }
            }
            rir::Literal::Integer(i) => format!("{i}"),
            rir::Literal::NullPointer => "null".to_string(),
            rir::Literal::Qubit(q) => format!("{q}"),
            rir::Literal::Result(r) => format!("{r}"),
            rir::Literal::Array(idx) => {
                format!("@array{idx}")
            }
            rir::Literal::Tag(..) => panic!(
                "tag literals should not be used as string values outside of output recording"
            ),
        },
        rir::Operand::Variable(var) => ToQir::<String>::to_qir(&var.variable_id, program),
    }
}

fn get_value_ty(lhs: &rir::Operand) -> String {
    match lhs {
        rir::Operand::Literal(lit) => match lit {
            rir::Literal::Integer(_) => "i64",
            rir::Literal::Bool(_) => "i1",
            rir::Literal::Double(_) => get_f64_ty(),
            rir::Literal::Qubit(_)
            | rir::Literal::Result(_)
            | rir::Literal::NullPointer
            | rir::Literal::Tag(..)
            | rir::Literal::Array(_) => "ptr",
        }
        .to_owned(),
        rir::Operand::Variable(var) => get_variable_ty(*var),
    }
}

fn get_variable_ty(variable: rir::Variable) -> String {
    match variable.ty {
        rir::Ty::Prim(prim) => get_prim_ty(prim).to_owned(),
        rir::Ty::Array(size, elem_ty) => format!("[{size} x {}]", get_prim_ty(elem_ty)),
    }
}

fn get_prim_ty(prim: rir::Prim) -> &'static str {
    match prim {
        rir::Prim::Integer => "i64",
        rir::Prim::Boolean => "i1",
        rir::Prim::Double => get_f64_ty(),
        rir::Prim::Qubit | rir::Prim::Result | rir::Prim::Pointer => "ptr",
    }
}

/// phi only supports "Floating-Point Types" which are defined as:
/// - `half` (`f16`)
/// - `bfloat`
/// - `float` (`f32`)
/// - `double` (`f64`)
/// - `fp128`
///
/// We only support `f64`, so we break the pattern used for integers
/// and have to use `double` here.
///
/// This conflicts with the QIR spec which says f64. Need to follow up on this.
fn get_f64_ty() -> &'static str {
    "double"
}

impl ToQir<String> for rir::BlockId {
    fn to_qir(&self, _program: &rir::Program) -> String {
        format!("block_{}", self.0)
    }
}

impl ToQir<String> for rir::Block {
    fn to_qir(&self, program: &rir::Program) -> String {
        self.0
            .iter()
            .map(|instr| ToQir::<String>::to_qir(instr, program))
            .collect::<Vec<_>>()
            .join("\n")
    }
}

impl ToQir<String> for rir::Callable {
    fn to_qir(&self, program: &rir::Program) -> String {
        // The trait entry point preserves the historical behavior of treating a bodied callable
        // as the program entry point. Non-entry IR functions are emitted via `callable_to_qir`
        // from `Program::to_qir`, where the callable's id is known.
        callable_to_qir(self, true, program)
    }
}

/// Converts a callable to its QIR string representation.
///
/// `is_entry` selects how a bodied callable is rendered: the entry point is emitted as
/// `@ENTRYPOINT__main()` returning `i64 0`, while a non-entry `Regular` callable is emitted as a
/// real LLVM `define void @<name>(<params>)` IR function with typed parameters named after the
/// callable's `input_vars`. Bodyless callables (intrinsics) always render as `declare`.
fn callable_to_qir(callable: &rir::Callable, is_entry: bool, program: &rir::Program) -> String {
    let output_type = ToQir::<String>::to_qir(&callable.output_type, program);
    let Some(entry_id) = callable.body else {
        let input_type = callable
            .input_type
            .iter()
            .map(|t| ToQir::<String>::to_qir(t, program))
            .collect::<Vec<_>>()
            .join(", ");
        let callable_name = llvm_global_name(&callable.name);
        return format!(
            "declare {output_type} {callable_name}({input_type}){}",
            match callable.call_type {
                rir::CallableType::Measurement | rir::CallableType::Reset => {
                    // These callables are a special case that need the irreversible attribute.
                    " #1"
                }
                rir::CallableType::NoiseIntrinsic => " #2",
                _ => "",
            }
        );
    };
    let mut body = String::new();
    let mut all_blocks = vec![entry_id];
    all_blocks.extend(get_all_block_successors(entry_id, program));
    for block_id in all_blocks {
        let block = program.get_block(block_id);
        write!(
            body,
            "{}:\n{}\n",
            ToQir::<String>::to_qir(&block_id, program),
            ToQir::<String>::to_qir(block, program)
        )
        .expect("writing to string should succeed");
    }
    if is_entry {
        assert!(
            callable.input_type.is_empty(),
            "entry point should not have an input"
        );
        format!("define {output_type} @ENTRYPOINT__main() #0 {{\n{body}}}")
    } else {
        let callable_name = llvm_global_name(&callable.name);
        let params = callable
            .input_type
            .iter()
            .zip(callable.input_vars.iter())
            .map(|(ty, var_id)| {
                format!(
                    "{} {}",
                    ToQir::<String>::to_qir(ty, program),
                    ToQir::<String>::to_qir(var_id, program)
                )
            })
            .collect::<Vec<_>>()
            .join(", ");
        format!("define {output_type} {callable_name}({params}) {{\n{body}}}")
    }
}

impl ToQir<String> for rir::ArrayLiteral {
    fn to_qir(&self, program: &rir::Program) -> String {
        let elem_ty = get_prim_ty(self.ty);
        let elems = self
            .contents
            .iter()
            .map(|elem| ToQir::<String>::to_qir(elem, program))
            .collect::<Vec<_>>()
            .join(", ");
        format!("[{} x {}] [{}]", self.contents.len(), elem_ty, elems)
    }
}

impl ToQir<String> for rir::Program {
    fn to_qir(&self, _program: &rir::Program) -> String {
        let callables = self
            .callables
            .iter()
            .map(|(id, callable)| callable_to_qir(callable, id == self.entry, self))
            .collect::<Vec<_>>()
            .join("\n\n");
        let mut constants = String::default();
        for (idx, tag) in self.tags.iter().enumerate() {
            // We need to add the tag as a global constant.
            writeln!(
                constants,
                "@{idx} = internal constant [{} x i8] c\"{tag}\\00\"",
                tag.len() + 1
            )
            .expect("writing to string should succeed");
        }
        for (idx, array) in self.array_literals.iter().enumerate() {
            // We need to add the array as a global constant.
            writeln!(
                constants,
                "@array{idx} = internal constant {}",
                ToQir::<String>::to_qir(array, self)
            )
            .expect("writing to string should succeed");
        }
        // When dynamic qubit allocation is enabled, qubits are allocated via the
        // runtime API rather than declared up front. The spec states that the
        // `required_num_qubits` entry-point attribute is not required in that case,
        // and the `dynamic_qubit_management` module flag must be set to true.
        let dynamic_qubit_management = self
            .config
            .capabilities
            .contains(TargetCapabilityFlags::DynamicQubitAllocation);
        let required_num_qubits = if dynamic_qubit_management {
            String::new()
        } else {
            format!("\"required_num_qubits\"=\"{}\" ", self.num_qubits)
        };
        let body = format!(
            include_str!("./v2/template.ll"),
            constants,
            callables,
            required_num_qubits,
            self.num_results,
            get_additional_module_attributes(self),
            dynamic_qubit_management,
        );
        body
    }
}

fn get_additional_module_attributes(program: &rir::Program) -> String {
    let mut attrs = String::new();
    if program.attrs.contains(Attributes::QdkNoise) {
        attrs.push_str("\nattributes #2 = { \"qdk_noise\" }");
    }

    attrs
}