rustre_core/

types.rs

use crate::diagnostics::{Diagnostic, Level, Span};
use crate::engine::Engine;
use crate::eval::eval_const_node;
use crate::id::{Id, IdRef};
use crate::name_resolution::{resolve_runtime_node, NameResolveQuery, ResolvedRuntimeNode};
use crate::static_args::{NodeInstance, StaticArgs};
use crate::value::{UValue, Value};
use crate::TypedSignature;
use comemo::TrackedMut;
use rustre_parser::ast::{
    AstNode, AstToken, CallByPosExpressionNode, ExpressionNode, LeftItemNode, Root, SelectNode,
    TypeNode,
};
use std::fmt::Write;

#[derive(Clone, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub enum Type {
    /// Returned when an identifier cannot be resolved, or from an operator when it cannot resolve
    /// its type due to an operand being unknown to.
    #[default]
    Unknown,

    Boolean,
    Integer,
    Real,
    Array {
        elem: Box<Type>,
        // TODO change to platform-independent type
        size: usize,
    },

    /// Tuple value or return type of a function with multiple (or 0) values
    ///
    /// A tuple **cannot** contain only one element, but **may** be empty. More specifically, if a
    /// function returns exactly one value, it **mustn't** be typed as a `ReturnTuple` as this would
    /// prevent it from being used as an operand to pretty much all operators.
    Tuple(Vec<Type>),
}

impl Type {
    pub fn is_array(&self) -> bool {
        matches!(self, Type::Array { .. })
    }

    pub fn is_numeric(&self) -> bool {
        matches!(self, Type::Integer | Type::Real | Type::Unknown)
    }

    pub fn is_unknown(&self) -> bool {
        matches!(self, Self::Unknown)
    }

    /// Returns the first non-[`Unknown`][Self::Unknown] type between `Self` and `other`, and
    /// [`Type::Unknown`] if both are
    pub fn or(self, other: Self) -> Type {
        if !self.is_unknown() {
            self
        } else {
            other
        }
    }
    /// Returns the first non-[`Unknown`][Self::Unknown] _numeric_ type between `Self` and `other`,
    /// and [`Type::Unknown`] if both are unknown or non-numeric
    pub fn numeric_or(self, other: Self) -> Type {
        if !self.is_unknown() && self.is_numeric() {
            self
        } else if other.is_numeric() {
            other
        } else {
            Type::Unknown
        }
    }

    pub fn is_assignable_from(&self, other: &Self) -> bool {
        if self.is_unknown() || other.is_unknown() {
            true
        } else if let (
            Self::Array { elem, size },
            Self::Array {
                elem: elem_o,
                size: size_o,
            },
        ) = (self, other)
        {
            size == size_o && elem.is_assignable_from(elem_o)
        } else if let (Self::Tuple(tup), Self::Tuple(tup_o)) = (self, other) {
            std::iter::zip(tup, tup_o.iter()).all(|(s, o)| s.is_assignable_from(o))
        } else {
            self == other
        }
    }
}

// This is not great for complex types. For instance, type aliases should remain as-is instead of
// being displayed as their resolved version. We should change that later.
impl std::fmt::Display for Type {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Type::Unknown => write!(f, "{{unknown}}"),
            Type::Boolean => write!(f, "bool"),
            Type::Integer => write!(f, "int"),
            Type::Real => write!(f, "real"),
            Type::Array { elem, size } => write!(f, "{elem}^{size}"),
            Type::Tuple(types) => {
                write!(f, "(")?;
                for (idx, ty) in types.iter().enumerate() {
                    if idx == 0 {
                        write!(f, "{ty}")
                    } else {
                        write!(f, ", {ty}")
                    }?;
                }
                write!(f, ")")
            }
        }
    }
}

/// **Query**: Type-checks all equations of a given node
#[memoize]
pub fn check_node_equations(mut engine: TrackedMut<Engine>, instance: NodeInstance) {
    let Some(body_node) = instance.node.body_node() else {
        return;
    };

    for node in body_node.all_equals_equation_node() {
        if let (Some(left_node), Some(expr_node)) = (node.left_node(), node.expression_node()) {
            let lefts = left_node.all_left_item_node();
            let mut left_types = Vec::new();
            for left in lefts {
                let left_type = type_check_left(
                    TrackedMut::reborrow_mut(&mut engine),
                    Some(instance.clone()),
                    &left,
                );
                left_types.push(left_type);
            }
            let left_types = if left_types.len() == 1 {
                left_types.pop().unwrap()
            } else {
                Type::Tuple(left_types)
            };

            let right_types = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                Some(instance.clone()),
                &expr_node,
                Some(left_types.clone()),
            );

            if !left_types.is_assignable_from(&right_types) {
                Diagnostic::build(Level::Error, "incompatible types")
                    .with_attachment(
                        Span::of_node(node.left_node().unwrap().syntax()),
                        format!("the left term is of type {}", left_types),
                    )
                    .with_attachment(
                        Span::of_node(node.expression_node().unwrap().syntax()),
                        format!("while the right term is of type {}", right_types),
                    )
                    .emit(&mut engine);
            }
        }
    }

    for node in body_node.all_assert_equation_node() {
        let right_types = type_check_expression(
            TrackedMut::reborrow_mut(&mut engine),
            Some(instance.clone()),
            &node.expression_node().unwrap(),
            Some(Type::Boolean),
        );

        if right_types != Type::Boolean {
            Diagnostic::build(Level::Error, "assertions should be boolean expressions")
                .with_attachment(
                    Span::of_node(node.expression_node().unwrap().syntax()),
                    format!("this expression has type {}", right_types),
                )
                .emit(&mut engine);
        }
    }
}

#[memoize]
pub fn type_of_ast_type(
    mut engine: TrackedMut<Engine>,
    instance: Option<NodeInstance>,
    type_node: TypeNode,
) -> Type {
    let scalar = if type_node.bool().is_some() {
        Type::Boolean
    } else if type_node.int().is_some() {
        Type::Integer
    } else if type_node.real().is_some() {
        Type::Real
    } else if let Some(id) = type_node.id_ref_node() {
        let id_ref = IdRef::from(&id);

        if let (Some(static_args), Some(member)) = (
            &instance.as_ref().map(|i| &i.static_args),
            id_ref.as_member_implicit(),
        ) {
            if let Some(ty) = static_args.resolve_type(member) {
                return ty.clone();
            }
        }

        let decl = crate::name_resolution::resolve_type_decl(
            TrackedMut::reborrow_mut(&mut engine),
            id.clone(),
        );

        match decl {
            Some(decl) => decl
                .type_node()
                .map(|t| {
                    type_of_ast_type(TrackedMut::reborrow_mut(&mut engine), instance.clone(), t)
                })
                .unwrap_or_default(),
            None => {
                let span = Span::of_node(id.syntax());

                Diagnostic::build(Level::Error, format!("cannot resolve type {id_ref:?}"))
                    .with_attachment(span, "not found in this scope")
                    .emit(&mut engine);

                Type::Unknown
            }
        }
    } else {
        Type::Unknown
    };

    if let Some(power) = type_node.power() {
        let size_value = eval_const_node(
            TrackedMut::reborrow_mut(&mut engine),
            power.clone(),
            instance,
        );

        let size_value = size_value.as_ref().map(Value::unpack);
        let size = match size_value {
            // FIXME(diagnostics): better errors
            Some(UValue::Int(i)) => usize::try_from(i).expect("negative array size"),
            _ => {
                Diagnostic::build(Level::Error, "cannot evaluate type")
                    .with_attachment(
                        Span::of_node(power.syntax()),
                        "this expression is not constant",
                    )
                    .emit(&mut engine);
                return Type::Unknown;
            }
        };
        Type::Array {
            elem: Box::new(scalar),
            size,
        }
    } else {
        scalar
    }
}

macro_rules! some_or_unknown {
    ($option:expr) => {
        match $option {
            Some(x) => x,
            _ => return Type::Unknown,
        }
    };
}

/// Resolves the declared type of an ident using a [NameResolveQuery] from [crate::name_resolution]
#[memoize]
pub fn declared_type_of_ident(
    mut engine: TrackedMut<Engine>,
    static_args: Option<StaticArgs>,
    query: NameResolveQuery,
) -> Option<Type> {
    if let Some(static_args) = &static_args {
        if let Some(val) = static_args.resolve_const(<&Id>::from(&query.ident)) {
            // TODO this is very bad, we should use the _declared_ type instead of resolving the
            //      value. Currently we have no easy way to do that, forgive me for the following
            return Some(val.type_of().clone());
        }
    }

    let resolved_node = resolve_runtime_node(TrackedMut::reborrow_mut(&mut engine), query.clone());
    let resolved_node = resolved_node?;

    match resolved_node {
        ResolvedRuntimeNode::Const(const_decl_node) => {
            if let Some(type_node) = const_decl_node.type_node() {
                Some(type_of_ast_type(engine, query.in_node, type_node))
            } else if let Some(expression_node) = const_decl_node.expression_node() {
                let val = eval_const_node(engine, expression_node, query.in_node)?;
                Some(val.type_of().clone())
            } else {
                None
            }
        }
        ResolvedRuntimeNode::Param(var_decl_node)
        | ResolvedRuntimeNode::ReturnParam(var_decl_node)
        | ResolvedRuntimeNode::Var(var_decl_node) => Some(type_of_ast_type(
            TrackedMut::reborrow_mut(&mut engine),
            query.in_node,
            var_decl_node.type_node().unwrap(),
        )),
    }
}

macro_rules! ty_check_expr {
    (unary, $engine:expr, $instance:expr, $node:expr, $expected:expr, $accept:pat) => {{
        let operand = some_or_unknown!($node.operand());
        let type_exp = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance, &operand, Some($expected));
        match type_exp {
            $accept => type_exp,
            _ => {
                Diagnostic::build(Level::Error, "Incorrect type")
                    .with_attachment(
                        Span::of_node(operand.syntax()),
                        format!("expected {}, found {}", $expected, type_exp),
                    )
                    .emit(&mut $engine);
                Type::Unknown
            }
        }
    }};
    (binary_any, $engine:expr, $instance:expr, $node:expr, $expected:expr) => {{
        let left_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance.clone(), &some_or_unknown!($node.left()), None);
        let right_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance, &some_or_unknown!($node.right()), None);
        if left_node_type.is_assignable_from(&right_node_type) {
            left_node_type.or(right_node_type)
        } else {
            Diagnostic::build(Level::Error, "incompatible types")
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.left()).syntax()),
                    format!("this is of type {}", left_node_type),
                )
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.right()).syntax()),
                    format!("while this is of type {}", right_node_type),
                )
                .emit(&mut $engine);
            $expected.unwrap_or(Type::Unknown)
        }
    }};
    (binary, $engine:expr, $instance:expr, $node:expr, $expect:expr) => {{
        let left_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance.clone(), &some_or_unknown!($node.left()), Some($expect));
        let right_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance, &some_or_unknown!($node.right()), Some($expect));

        if !left_node_type.is_assignable_from(&$expect) {
            Diagnostic::build(Level::Error, "incorrect type")
                .with_attachment(
                    Span::of_node($node.left().unwrap().syntax()),
                    format!("expected {}, found {}", $expect, left_node_type),
                )
                .emit(&mut $engine);
        }

        if !right_node_type.is_assignable_from(&$expect) {
            Diagnostic::build(Level::Error, "incorrect type")
                .with_attachment(
                    Span::of_node($node.right().unwrap().syntax()),
                    format!("expected {}, found {}", $expect, right_node_type),
                )
                .emit(&mut $engine);
        }

        $expect
    }};
    (comparator, $engine:expr, $instance:expr, $node:expr) => {{
        let left_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance.clone(), &some_or_unknown!($node.left()), Some(Type::Integer));
        let right_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance, &some_or_unknown!($node.right()), Some(Type::Integer));

        let mut reported = false;
        if !left_node_type.is_numeric() {
            Diagnostic::build(Level::Error, "incorrect type")
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.left()).syntax()),
                    format!("expected int or real, found {}", left_node_type),
                )
                .emit(&mut $engine);
            reported = true;
        }

        if !right_node_type.is_numeric() {
            Diagnostic::build(Level::Error, "incorrect type")
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.right()).syntax()),
                    format!("expected int or real, found {}", right_node_type),
                )
                .emit(&mut $engine);
            reported = true;
        }

        if !reported && !left_node_type.is_assignable_from(&right_node_type) {
            let can_cast_right = right_node_type == Type::Real || right_node_type == Type::Integer;
            Diagnostic::build(Level::Error, "incorrect type")
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.right()).syntax()),
                    format!(
                        "expected {} (because of the left operand), found {} {}",
                        left_node_type, right_node_type,
                        if can_cast_right {
                            format!("(hint: you can use the `{}` function if you want to do a conversion)", left_node_type)
                        } else {
                            "".into()
                        }
                    ),
                )
                .emit(&mut $engine);
        }

        Type::Boolean
    }};
    (comparator_any, $engine:expr, $instance:expr, $node:expr) => {{
        let left_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance.clone(), &some_or_unknown!($node.left()), None);
        let right_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance, &some_or_unknown!($node.right()), None);
        if !left_node_type.is_assignable_from(&right_node_type) {
            Diagnostic::build(Level::Error, "incompatible types")
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.left()).syntax()),
                    format!("this is of type {}", left_node_type),
                )
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.right()).syntax()),
                    format!("while this is of type {}", right_node_type),
                )
                .emit(&mut $engine);
        }

        Type::Boolean
    }};
    (binary_number, $engine:expr, $instance:expr, $node:expr) => {{
        let left_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance.clone(), &some_or_unknown!($node.left()), Some(Type::Integer));
        let right_node_type = type_check_expression(TrackedMut::reborrow_mut(&mut $engine), $instance, &some_or_unknown!($node.right()), Some(Type::Integer));

        let mut reported = false;
        if !left_node_type.is_numeric() {
            Diagnostic::build(Level::Error, "incorrect type")
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.left()).syntax()),
                    format!("expected int or real, found {}", left_node_type),
                )
                .emit(&mut $engine);
            reported = true;
        }

        if !right_node_type.is_numeric() {
            Diagnostic::build(Level::Error, "incorrect type")
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.right()).syntax()),
                    format!("expected int or real, found {}", right_node_type),
                )
                .emit(&mut $engine);
            reported = true;
        }

        if !reported && !left_node_type.is_assignable_from(&right_node_type) {
            let can_cast_right = right_node_type == Type::Real || right_node_type == Type::Integer;
            Diagnostic::build(Level::Error, "incorrect type")
                .with_attachment(
                    Span::of_node(some_or_unknown!($node.right()).syntax()),
                    format!(
                        "expected {} (because of the left operand), found {} {}",
                        left_node_type, right_node_type,
                        if can_cast_right {
                            format!("(hint: you can use the `{}` function if you want to do a conversion)", left_node_type)
                        } else {
                            "".into()
                        }
                    ),
                )
                .emit(&mut $engine);
        }

        left_node_type.numeric_or(right_node_type)
    }}
}

#[memoize]
pub fn type_check_expression(
    mut engine: TrackedMut<Engine>,
    instance: Option<NodeInstance>,
    expr: &ExpressionNode,
    expected_type: Option<Type>,
) -> Type {
    match expr {
        ExpressionNode::ConstantNode(constant) => {
            if constant.is_true() || constant.is_false() {
                Type::Boolean
            } else if constant.i_const().is_some() {
                Type::Integer
            } else if constant.r_const().is_some() {
                Type::Real
            } else {
                Type::Unknown
            }
        }
        ExpressionNode::NotExpressionNode(node) => {
            ty_check_expr!(unary, engine, instance, node, Type::Boolean, Type::Boolean)
        }
        ExpressionNode::NegExpressionNode(node) => ty_check_expr!(
            unary,
            engine,
            instance,
            node,
            Type::Integer,
            Type::Integer | Type::Real
        ),
        ExpressionNode::PreExpressionNode(node) => {
            type_check_expression(engine, instance, &node.operand().unwrap(), expected_type)
        }
        ExpressionNode::CurrentExpressionNode(node) => {
            type_check_expression(engine, instance, &node.operand().unwrap(), expected_type)
        }
        ExpressionNode::IntExpressionNode(node) => {
            // TODO: what types can be converted to int?
            let type_exp = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance,
                &node.operand().unwrap(),
                None,
            );

            match type_exp {
                Type::Real | Type::Unknown => Type::Integer,
                Type::Integer => {
                    Diagnostic::build(Level::Warning, "useless type conversion")
                        .with_attachment(
                            Span::of_node(node.operand().unwrap().syntax()),
                            "this expression is already an int",
                        )
                        .emit(&mut engine);
                    Type::Integer
                }
                _ => {
                    Diagnostic::build(Level::Error, "invalid type conversion")
                        .with_attachment(
                            Span::of_node(node.operand().unwrap().syntax()),
                            format!(
                                "this expression has type {}, which cannot be converted to int.",
                                type_exp
                            ),
                        )
                        .emit(&mut engine);
                    Type::Unknown
                }
            }
        }
        ExpressionNode::RealExpressionNode(node) => {
            let type_exp = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance,
                &node.operand().unwrap(),
                None,
            );

            match type_exp {
                Type::Integer | Type::Unknown => Type::Real,
                Type::Real => {
                    Diagnostic::build(Level::Warning, "useless type conversion")
                        .with_attachment(
                            Span::of_node(node.operand().unwrap().syntax()),
                            "this expression is already a real",
                        )
                        .emit(&mut engine);
                    Type::Real
                }
                _ => {
                    Diagnostic::build(Level::Error, "invalid type conversion")
                        .with_attachment(
                            Span::of_node(node.operand().unwrap().syntax()),
                            format!(
                                "this expression has type {}, which cannot be converted to real.",
                                type_exp
                            ),
                        )
                        .emit(&mut engine);
                    Type::Unknown
                }
            }
        }
        ExpressionNode::WhenExpressionNode(_) => todo!(),
        ExpressionNode::FbyExpressionNode(node) => {
            ty_check_expr!(binary_any, engine, instance, node, expected_type)
        }
        ExpressionNode::ArrowExpressionNode(node) => {
            ty_check_expr!(binary_any, engine, instance, node, expected_type)
        }
        ExpressionNode::AndExpressionNode(node) => {
            ty_check_expr!(binary, engine, instance, node, Type::Boolean)
        }
        ExpressionNode::OrExpressionNode(node) => {
            ty_check_expr!(binary, engine, instance, node, Type::Boolean)
        }
        ExpressionNode::XorExpressionNode(node) => {
            ty_check_expr!(binary, engine, instance, node, Type::Boolean)
        }
        ExpressionNode::ImplExpressionNode(node) => {
            ty_check_expr!(binary, engine, instance, node, Type::Boolean)
        } // TODO, is that true?
        ExpressionNode::EqExpressionNode(node) => {
            ty_check_expr!(comparator_any, engine, instance, node)
        }
        ExpressionNode::NeqExpressionNode(node) => {
            ty_check_expr!(comparator_any, engine, instance, node)
        }
        ExpressionNode::LtExpressionNode(node) => {
            ty_check_expr!(comparator, engine, instance, node)
        }
        ExpressionNode::LteExpressionNode(node) => {
            ty_check_expr!(comparator, engine, instance, node)
        }
        ExpressionNode::GtExpressionNode(node) => {
            ty_check_expr!(comparator, engine, instance, node)
        }
        ExpressionNode::GteExpressionNode(node) => {
            ty_check_expr!(comparator, engine, instance, node)
        }
        ExpressionNode::DivExpressionNode(node) => {
            ty_check_expr!(binary_number, engine, instance, node)
        }
        ExpressionNode::ModExpressionNode(node) => {
            ty_check_expr!(binary_number, engine, instance, node)
        }
        ExpressionNode::SubExpressionNode(node) => {
            ty_check_expr!(binary_number, engine, instance, node)
        }
        ExpressionNode::AddExpressionNode(node) => {
            ty_check_expr!(binary_number, engine, instance, node)
        }
        ExpressionNode::MulExpressionNode(node) => {
            ty_check_expr!(binary_number, engine, instance, node)
        }
        ExpressionNode::PowerExpressionNode(node) => {
            ty_check_expr!(binary_number, engine, instance, node)
        }
        ExpressionNode::HatExpressionNode(node) => {
            let left_expectation = match expected_type.clone() {
                Some(Type::Array { elem, .. }) => Some(*elem),
                _ => None,
            };
            let left_node_type = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                &some_or_unknown!(node.left()),
                left_expectation,
            );
            let right_node_type = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                &some_or_unknown!(node.right()),
                Some(Type::Integer),
            );

            let size_value = eval_const_node(
                TrackedMut::reborrow_mut(&mut engine),
                some_or_unknown!(node.right()),
                instance,
            );

            let size_value = size_value.as_ref().map(Value::unpack);
            let size = match size_value {
                // FIXME(diagnostics): better errors
                Some(UValue::Int(i)) => Some(usize::try_from(i).expect("negative array size")),
                _ => None,
            };

            if right_node_type != Type::Integer {
                Diagnostic::build(Level::Error, "incorrect type")
                    .with_attachment(
                        Span::of_node(some_or_unknown!(node.right()).syntax()),
                        format!("expected int, found {}", right_node_type),
                    )
                    .emit(&mut engine);
            }

            if expected_type == Some(Type::Integer) || expected_type == Some(Type::Real) {
                Diagnostic::build(Level::Warning, "possible confusion")
                    .with_attachment(Span::of_node(node.syntax()), "the `^` operator creates an array by repeting an element a given number of times, it is not a power operator (hint: use ** instead)")
                    .emit(&mut engine);
            }

            Type::Array {
                elem: Box::new(left_node_type),
                size: some_or_unknown!(size),
            }
        }
        ExpressionNode::IfExpressionNode(node) => {
            let if_body_type = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                &some_or_unknown!(node.if_body()),
                Some(Type::Boolean),
            );
            let else_body_type = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                &some_or_unknown!(node.else_body()),
                None,
            );
            let cond_type = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance,
                &some_or_unknown!(node.cond()),
                Some(Type::Boolean),
            );

            if !if_body_type.is_assignable_from(&else_body_type) {
                Diagnostic::build(Level::Error, "incompatible types")
                    .with_attachment(
                        Span::of_node(some_or_unknown!(node.else_body()).syntax()),
                        format!(
                            "expected {} (because of if body), found {}",
                            if_body_type, else_body_type
                        ),
                    )
                    .emit(&mut engine);
            }

            if !Type::Boolean.is_assignable_from(&cond_type) {
                Diagnostic::build(Level::Error, "Incorrect type")
                    .with_attachment(
                        Span::of_node(some_or_unknown!(node.cond()).syntax()),
                        format!("expected a boolean condition, found {}", cond_type),
                    )
                    .emit(&mut engine);
            }

            if_body_type.or(else_body_type)
        }
        ExpressionNode::WithExpressionNode(node) => {
            let cond_expr = some_or_unknown!(node.cond());
            let cond_type = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                &cond_expr,
                Some(Type::Boolean),
            );

            if !Type::Boolean.is_assignable_from(&cond_type) {
                Diagnostic::build(Level::Error, "Incorrect type")
                    .with_attachment(
                        Span::of_node(some_or_unknown!(node.cond()).syntax()),
                        format!("expected a boolean condition, found {}", cond_type),
                    )
                    .emit(&mut engine);

                return Type::Unknown;
            }

            let cond = eval_const_node(
                TrackedMut::reborrow_mut(&mut engine),
                cond_expr,
                instance.clone(),
            );

            let Some(cond) = cond else {
                return Type::Unknown;
            };

            let body = match cond.unpack() {
                UValue::Bool(true) => node.with_body(),
                UValue::Bool(false) => node.else_body(),
                _ => unreachable!(),
            };

            type_check_expression(engine, instance, &some_or_unknown!(body), None)
        }
        ExpressionNode::DieseExpressionNode(node) => {
            let node_list = node.list().unwrap().all_expression_node();
            for element in node_list {
                let el_type = type_check_expression(
                    TrackedMut::reborrow_mut(&mut engine),
                    instance.clone(),
                    &element,
                    Some(Type::Boolean),
                );
                if el_type != Type::Boolean || el_type != Type::Unknown {
                    Diagnostic::build(Level::Error, "Incorrect type")
                        .with_attachment(
                            Span::of_node(element.syntax()),
                            format!("expected boolean, found {}", el_type),
                        )
                        .emit(&mut engine);
                }
            }

            Type::Boolean
        }
        ExpressionNode::NorExpressionNode(node) => {
            let node_list = node.list().unwrap().all_expression_node();
            for element in node_list {
                let el_type = type_check_expression(
                    TrackedMut::reborrow_mut(&mut engine),
                    instance.clone(),
                    &element,
                    Some(Type::Boolean),
                );
                if el_type != Type::Boolean || el_type != Type::Unknown {
                    Diagnostic::build(Level::Error, "Incorrect type")
                        .with_attachment(
                            Span::of_node(element.syntax()),
                            format!("expected boolean, found {}", el_type),
                        )
                        .emit(&mut engine);
                }
            }

            Type::Boolean
        }
        ExpressionNode::IdentExpressionNode(node) => {
            let ident = some_or_unknown!(node.id_ref_node()).member();
            let query = NameResolveQuery {
                ident: ident.clone(),
                in_node: instance.clone(),
            };

            let resolved = declared_type_of_ident(
                TrackedMut::reborrow_mut(&mut engine),
                instance.map(|i| i.static_args),
                query,
            );

            match resolved {
                Some(ty) => ty,
                None => {
                    let name = ident.text();
                    let span = Span::of_token(ident.syntax());

                    Diagnostic::build(Level::Error, format!("cannot find value {name:?}"))
                        .with_attachment(span, "not found in this scope")
                        .emit(&mut engine);

                    Type::Unknown
                }
            }
        }
        ExpressionNode::ParExpressionNode(node) => type_check_expression(
            engine,
            instance,
            &some_or_unknown!(node.expression_node()),
            expected_type,
        ),
        ExpressionNode::CallByPosExpressionNode(expr) => {
            let callee = crate::static_args::instance_of_call_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                expr.clone(),
            );

            if let Some(callee) = callee {
                let all_sig = crate::all_typed_signatures(TrackedMut::reborrow_mut(&mut engine));

                let sig = all_sig
                    .get(&callee)
                    .expect("not computed yet (reentrancy issue?)");

                check_call_expression(engine, instance, expr, sig)
            } else {
                Type::Unknown
            }
        }
        ExpressionNode::ArrayAccessExpressionNode(expr) => {
            let hopefully_array = type_check_expression(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                &expr.left().unwrap(),
                None,
            );

            let index = match (expr.scalar_index(), expr.select_index()) {
                (None, None) => ArrayIndex::None,
                (_, Some(select)) => ArrayIndex::Select(select),
                (Some(scalar), None) => ArrayIndex::Scalar(scalar),
            };

            let array_span = Span::of_node(expr.left().unwrap().syntax());
            type_check_array(engine, instance, array_span, hopefully_array, index)
        }
    }
}

fn check_call_expression(
    mut engine: TrackedMut<Engine>,
    caller: Option<NodeInstance>,
    expr: &CallByPosExpressionNode,
    sig: &TypedSignature,
) -> Type {
    // Check input parameters
    let expected = sig.params.iter().map(Some).chain(std::iter::repeat(None));
    let found = expr.args().skip(1).map(Some).chain(std::iter::repeat(None));
    for (expected, found) in expected.zip(found) {
        match (expected, found) {
            (None, None) => break,
            (Some((_, expected_ty)), Some(found)) => {
                if !expected_ty.is_unknown() {
                    let found_ty = type_check_expression(
                        TrackedMut::reborrow_mut(&mut engine),
                        caller.clone(),
                        &found,
                        Some(expected_ty.clone()),
                    );
                    if !expected_ty.is_assignable_from(&found_ty) {
                        let span = Span::of_node(found.syntax());
                        Diagnostic::build(Level::Error, "invalid type for argument")
                            .with_attachment(
                                span,
                                format!("expected {expected_ty}, found {found_ty}"),
                            )
                            .emit(&mut engine);
                    }
                }
            }
            (Some((expected_ident, _expected_type)), None) => {
                let error_span = expr
                    .args()
                    .last()
                    .map(|s| Span::of_node(s.syntax()))
                    .or_else(|| expr.open_par().map(|p| Span::of_token(p.syntax())))
                    .or_else(|| expr.node_ref().map(|i| Span::of_node(i.syntax())))
                    .unwrap_or_else(|| Span::of_node(expr.syntax()))
                    .after();

                let name_span = Span::of_node(expr.node_ref().unwrap().syntax());
                let found_count = expr.args().skip(1).count();
                let expected_count = sig.params.len();
                let expected_ident = expected_ident.text();

                Diagnostic::build(Level::Error, format!("missing argument {expected_ident:?}"))
                    .with_attachment(name_span, format!("this function expects {expected_count} arguments but {found_count} were supplied"))
                    .with_attachment(error_span, "hint: add the missing arguments(s)")
                    .emit(&mut engine);
            }
            (None, Some(found)) => {
                let arg_span = Span::of_node(found.syntax());
                let name_span = Span::of_node(expr.node_ref().unwrap().syntax());
                let found_count = expr.args().skip(1).count();
                let expected_count = sig.params.len();

                Diagnostic::build(Level::Error, "unexpected argument")
                    .with_attachment(arg_span, "hint: remove this argument")
                    .with_attachment(name_span, format!("this function expects {expected_count} arguments but {found_count} were supplied"))
                    .emit(&mut engine);
            }
        }
    }

    // Find out returned value(s)
    if sig.return_params.len() == 1 {
        sig.return_params[0].1.clone()
    } else {
        let cloned = sig.return_params.iter().map(|(_, t)| t).cloned().collect();
        Type::Tuple(cloned)
    }
}

fn type_check_left(
    mut engine: TrackedMut<Engine>,
    instance: Option<NodeInstance>,
    expr: &LeftItemNode,
) -> Type {
    match expr {
        LeftItemNode::IdNode(ident) => {
            let query = NameResolveQuery {
                ident: ident.ident().unwrap(),
                in_node: instance.clone(),
            };
            let resolved_node = resolve_runtime_node(TrackedMut::reborrow_mut(&mut engine), query);
            match resolved_node {
                Some(ResolvedRuntimeNode::Const(ref const_decl_node)) => type_of_ast_type(
                    engine,
                    instance,
                    some_or_unknown!(const_decl_node.type_node()),
                ),
                Some(ResolvedRuntimeNode::Param(ref var_decl_node))
                | Some(ResolvedRuntimeNode::ReturnParam(ref var_decl_node))
                | Some(ResolvedRuntimeNode::Var(ref var_decl_node)) => type_of_ast_type(
                    engine,
                    instance,
                    some_or_unknown!(var_decl_node.type_node()),
                ),
                None => Type::Unknown,
            }
        }
        LeftItemNode::LeftTableAccessNode(table_item) => {
            let hopefully_array = type_check_left(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                &table_item.left_item_node().unwrap(),
            );

            let index = match (table_item.scalar_index(), table_item.select_index()) {
                (None, None) => ArrayIndex::None,
                (_, Some(select)) => ArrayIndex::Select(select),
                (Some(scalar), None) => ArrayIndex::Scalar(scalar),
            };

            let array_span = Span::of_node(table_item.left_item_node().unwrap().syntax());
            type_check_array(engine, instance, array_span, hopefully_array, index)
        }
        LeftItemNode::LeftFieldAccessNode(_) => {
            todo!("Structures are not supported yet.")
        }
    }
}

#[derive(Clone, Debug, Eq, Hash, PartialEq)]
enum ArrayIndex {
    None,
    Scalar(ExpressionNode),
    Select(SelectNode),
}

#[memoize]
fn type_check_array(
    mut engine: TrackedMut<Engine>,
    instance: Option<NodeInstance>,
    array_span: Span<Root>,
    hopefully_array: Type,
    right: ArrayIndex,
) -> Type {
    let Type::Array { elem, size } = hopefully_array else {
        Diagnostic::build(Level::Error, "cannot index into a non-array type")
            .with_attachment(
                array_span,
                format!("non-array type `{hopefully_array}` cannot be indexed"),
            )
            .with_help("to use indexing, the left side of the expression must be an array")
            .emit(&mut engine);

        return Type::Unknown;
    };

    match right {
        ArrayIndex::Scalar(index_expression) => {
            let _ =
                array_resolve_index(engine, instance, array_span, size, index_expression, false);

            *elem
        }
        ArrayIndex::Select(select_expression) => {
            let start = select_expression.left().unwrap();
            let end = select_expression.right().unwrap();
            let step = select_expression
                .step_node()
                .and_then(|step| step.expression_node());

            let start_value = array_resolve_index(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                array_span.clone(),
                size,
                start,
                false,
            );

            let end_value = array_resolve_index(
                TrackedMut::reborrow_mut(&mut engine),
                instance.clone(),
                array_span.clone(),
                size,
                end,
                false,
            );

            let (Some(start_value), Some(end_value)) = (start_value, end_value) else {
                return Type::Unknown;
            };

            let range_diff = end_value - start_value;
            let range_size = range_diff.abs() + 1;

            let step_value = step
                .clone()
                .and_then(|step| {
                    array_resolve_index(
                        TrackedMut::reborrow_mut(&mut engine),
                        instance.clone(),
                        array_span,
                        size,
                        step,
                        true,
                    )
                })
                .unwrap_or(range_size.signum());

            if step_value == 0 {
                let step_span = Span::of_node(step.unwrap().syntax());

                Diagnostic::build(Level::Error, "invalid select expression with step of zero")
                    .with_attachment(step_span, "step cannot be zero")
                    .with_help("the step value determines the stride for the slice operation")
                    .with_help("a zero step would result in an infinite selection")
                    .emit(&mut engine);

                // TODO(examples): suggest writing `1` IF the step is a constant literal zero

                // With a better type-checker, we could fix the array element type and let the
                // step be unknown.
                return Type::Unknown;
            } else if range_diff != 0 && range_diff.signum() != step_value.signum() {
                let mut range_span = Span::of_token(select_expression.c_dots().unwrap().syntax());

                range_span.extend(
                    [select_expression.left(), select_expression.right()]
                        .into_iter()
                        .flatten()
                        .map(|e| Span::of_node(e.syntax())),
                );

                let step_span = Span::of_node(step.unwrap().syntax());

                let (range_order, range_sign, step_sign) = if range_diff > 0 {
                    ("increasing", "up to", "negative")
                } else {
                    ("decreasing", "down to", "positive")
                };

                let example_indices = {
                    let mut builder = String::from("the selected indices would be the following: ");

                    let mut pos = start_value;
                    write!(builder, "{pos}").unwrap();
                    for _ in 0..4 {
                        pos += step_value;
                        write!(builder, ", {pos}").unwrap();
                    }

                    write!(builder, "… which never converge to {end_value}").unwrap();
                    builder
                };

                Diagnostic::build(
                    Level::Error,
                    "invalid select expression with diverging step",
                )
                .with_attachment(
                    range_span,
                    format!("this range is {range_order} ({start_value} {range_sign} {end_value})"),
                )
                .with_attachment(
                    step_span,
                    format!("this step is {step_sign} ({step_value})"),
                )
                .with_help(example_indices)
                .with_help(format!("try to use a step of {} instead", -step_value))
                .emit(&mut engine);

                // TODO(examples): suggest adding/removing a minus sign
            }

            // Guaranteed positive
            let size = usize::try_from(range_size / step_value.abs()).unwrap();

            Type::Array { elem, size }
        }
        ArrayIndex::None => {
            // No expression between brackets. The parser will have signaled an error.
            // We assume a by-index array access. With a more advanced type-checker, we could
            // consider an array element AND an equivalent array of different size both
            // assignable.
            *elem
        }
    }
}

/// Resolves the integer value of an array index expression, and emits related diagnostics
#[memoize]
fn array_resolve_index(
    mut engine: TrackedMut<Engine>,
    instance: Option<NodeInstance>,
    array_span: Span<Root>,
    size: usize,
    int_expression: ExpressionNode,
    is_step: bool,
) -> Option<i32> {
    let span = Span::of_node(int_expression.syntax());

    let index_type = type_check_expression(
        TrackedMut::reborrow_mut(&mut engine),
        instance.clone(),
        &int_expression,
        Some(Type::Integer),
    );

    match index_type {
        Type::Unknown => None,
        Type::Tuple(..) => unreachable!(),
        Type::Boolean | Type::Real | Type::Array { .. } => {
            let mut diag = Diagnostic::build(Level::Error, "cannot index with non-integer type")
                .with_attachment(span, format!("this is a {index_type}"))
                .with_note("arrays can only be indexed using constant `int` values");

            if matches!(index_type, Type::Boolean) {
                diag = diag.with_help(
                    "help: you can convert a boolean to an int using `if <bool> then 1 else 0`",
                );
            } else if matches!(index_type, Type::Real) {
                diag = diag.with_help("help: you can convert a real to an int using `int <real>`");
            }

            diag.emit(&mut engine);

            None
        }
        Type::Integer => {
            let index_value = eval_const_node(
                TrackedMut::reborrow_mut(&mut engine),
                int_expression,
                instance,
            );

            let index_value = index_value.as_ref().map(Value::unpack);
            if let Some(UValue::Int(index_value)) = index_value {
                let too_small = index_value < 0;
                let too_big = index_value >= size as i32;
                let zero_sized = size == 0;

                if !is_step && (too_small || too_big) {
                    let mut diag = Diagnostic::build(Level::Error, "out of bounds")
                        .with_attachment(
                            span,
                            format!("this expression evaluates to {index_value}"),
                        );

                    diag = if too_big {
                        diag.with_attachment(
                            array_span,
                            format!("but this array is {size} items long"),
                        )
                    } else {
                        diag.with_help("array indices start at 0 and must be positive")
                    };

                    if index_value == size as i32 && !zero_sized {
                        let last_index = index_value - 1;
                        diag = diag.with_help(format!(
                            "arrays are zero-indexed, the last element has index {last_index}"
                        ));
                    }

                    diag.emit(&mut engine);
                }

                Some(index_value)
            } else if index_value.is_some() {
                unreachable!();
            } else {
                None
            }
        }
    }
}