cairo_lang_semantic/items/

constant.rs

use std::iter::zip;
use std::sync::Arc;

use cairo_lang_debug::DebugWithDb;
use cairo_lang_defs::db::DefsGroup;
use cairo_lang_defs::ids::{
    ConstantId, ExternFunctionId, GenericParamId, LanguageElementId, LookupItemId, ModuleItemId,
    NamedLanguageElementId, TraitConstantId, TraitId, VarId,
};
use cairo_lang_diagnostics::{
    DiagnosticAdded, DiagnosticEntry, DiagnosticNote, Diagnostics, Maybe, MaybeAsRef,
    skip_diagnostic,
};
use cairo_lang_proc_macros::{DebugWithDb, HeapSize, SemanticObject};
use cairo_lang_syntax::node::ast::ItemConstant;
use cairo_lang_syntax::node::ids::SyntaxStablePtrId;
use cairo_lang_syntax::node::{TypedStablePtr, TypedSyntaxNode};
use cairo_lang_utils::ordered_hash_map::OrderedHashMap;
use cairo_lang_utils::ordered_hash_set::OrderedHashSet;
use cairo_lang_utils::unordered_hash_map::UnorderedHashMap;
use cairo_lang_utils::unordered_hash_set::UnorderedHashSet;
use cairo_lang_utils::{Intern, define_short_id, extract_matches, require, try_extract_matches};
use itertools::Itertools;
use num_bigint::BigInt;
use num_integer::Integer;
use num_traits::{ToPrimitive, Zero};
use salsa::Database;
use starknet_types_core::felt::{CAIRO_PRIME_BIGINT, Felt as Felt252};

use super::functions::{GenericFunctionId, GenericFunctionWithBodyId};
use super::imp::{ImplId, ImplLongId};
use crate::corelib::{
    CoreInfo, CorelibSemantic, core_nonzero_ty, false_variant, true_variant,
    try_extract_bounded_int_type, try_extract_nz_wrapped_type, unit_ty, validate_literal,
};
use crate::diagnostic::{SemanticDiagnosticKind, SemanticDiagnostics, SemanticDiagnosticsBuilder};
use crate::expr::compute::{ComputationContext, ExprAndId, compute_expr_semantic};
use crate::expr::inference::conform::InferenceConform;
use crate::expr::inference::{ConstVar, InferenceId};
use crate::helper::ModuleHelper;
use crate::items::enm::SemanticEnumEx;
use crate::items::extern_function::ExternFunctionSemantic;
use crate::items::free_function::FreeFunctionSemantic;
use crate::items::function_with_body::FunctionWithBodySemantic;
use crate::items::generics::GenericParamSemantic;
use crate::items::imp::ImplSemantic;
use crate::items::structure::StructSemantic;
use crate::items::trt::TraitSemantic;
use crate::resolve::{Resolver, ResolverData};
use crate::substitution::{GenericSubstitution, SemanticRewriter, SubstitutionRewriter};
use crate::types::resolve_type;
use crate::{
    Arenas, ConcreteFunction, ConcreteTypeId, ConcreteVariant, Condition, Expr, ExprBlock,
    ExprConstant, ExprFunctionCall, ExprFunctionCallArg, ExprId, ExprMemberAccess, ExprStructCtor,
    FunctionId, GenericParam, LogicalOperator, MemberAccessKind, Pattern, PatternId,
    SemanticDiagnostic, Statement, TypeId, TypeLongId, semantic_object_for_id,
};

#[derive(Clone, Debug, PartialEq, Eq, DebugWithDb)]
#[debug_db(dyn Database)]
pub struct Constant<'db> {
    /// The actual id of the const expression value.
    pub value: ExprId,
    /// The arena of all the expressions for the const calculation.
    pub arenas: Arc<Arenas<'db>>,
}

// TODO: Review this well.
unsafe impl<'db> salsa::Update for Constant<'db> {
    unsafe fn maybe_update(old_pointer: *mut Self, new_value: Self) -> bool {
        let old_constant: &mut Constant<'db> = unsafe { &mut *old_pointer };

        if old_constant.value != new_value.value {
            *old_constant = new_value;
            return true;
        }

        false
    }
}

impl<'db> Constant<'db> {
    pub fn ty(&self) -> TypeId<'db> {
        self.arenas.exprs[self.value].ty()
    }
}

/// Information about a constant definition.
///
/// Helper struct for the data returned by [ConstantSemantic::constant_semantic_data].
#[derive(Clone, Debug, PartialEq, Eq, DebugWithDb, salsa::Update)]
#[debug_db(dyn Database)]
pub struct ConstantData<'db> {
    pub diagnostics: Diagnostics<'db, SemanticDiagnostic<'db>>,
    pub constant: Maybe<Constant<'db>>,
    pub const_value: ConstValueId<'db>,
    pub resolver_data: Arc<ResolverData<'db>>,
}

define_short_id!(ConstValueId, ConstValue<'db>);
semantic_object_for_id!(ConstValueId, ConstValue<'a>);
impl<'db> ConstValueId<'db> {
    /// Creates a new const value from a BigInt.
    pub fn from_int(db: &'db dyn Database, ty: TypeId<'db>, value: &BigInt) -> Self {
        let get_basic_const_value = |ty| {
            let info = db.const_calc_info();
            if ty != info.u256 {
                ConstValue::Int(value.clone(), ty).intern(db)
            } else {
                let mask128 = BigInt::from(u128::MAX);
                let low = value & mask128;
                let high = value >> 128;
                ConstValue::Struct(
                    vec![
                        (ConstValue::Int(low, info.u128).intern(db)),
                        (ConstValue::Int(high, info.u128).intern(db)),
                    ],
                    ty,
                )
                .intern(db)
            }
        };
        if let Some(inner) = try_extract_nz_wrapped_type(db, ty) {
            ConstValue::NonZero(get_basic_const_value(inner)).intern(db)
        } else {
            get_basic_const_value(ty)
        }
    }
    /// Returns a formatted string of the const value.
    pub fn format(&self, db: &dyn Database) -> String {
        format!("{:?}", self.long(db).debug(db))
    }

    /// Returns true if the const does not depend on any generics.
    pub fn is_fully_concrete(&self, db: &dyn Database) -> bool {
        self.long(db).is_fully_concrete(db)
    }

    /// Returns true if the const does not contain any inference variables.
    pub fn is_var_free(&self, db: &dyn Database) -> bool {
        self.long(db).is_var_free(db)
    }

    /// Returns the type of the const.
    pub fn ty(&self, db: &'db dyn Database) -> Maybe<TypeId<'db>> {
        self.long(db).ty(db)
    }

    /// Returns the value of an int const as a BigInt.
    pub fn to_int(&self, db: &'db dyn Database) -> Option<&'db BigInt> {
        self.long(db).to_int()
    }

    /// A utility function for extracting the generic parameters arguments from a ConstValueId.
    /// Uses memoization via `visited` to avoid re-traversing shared subtypes in DAG structures.
    pub fn extract_generic_params(
        &self,
        db: &'db dyn Database,
        generic_parameters: &mut OrderedHashSet<GenericParamId<'db>>,
        visited: &mut OrderedHashSet<TypeId<'db>>,
    ) -> Maybe<()> {
        match self.long(db) {
            ConstValue::Int(_, type_id) | ConstValue::Struct(_, type_id) => {
                type_id.extract_generic_params(db, generic_parameters, visited)?
            }
            ConstValue::Enum(_, const_value_id) => {
                const_value_id.ty(db)?.extract_generic_params(db, generic_parameters, visited)?
            }
            ConstValue::NonZero(const_value_id) => {
                const_value_id.extract_generic_params(db, generic_parameters, visited)?
            }
            ConstValue::Generic(generic_param_id) => {
                generic_parameters.insert(*generic_param_id);
            }
            ConstValue::ImplConstant(impl_constant_id) => {
                for garg in impl_constant_id.impl_id().concrete_trait(db)?.generic_args(db) {
                    garg.extract_generic_params(db, generic_parameters, visited)?;
                }
            }
            ConstValue::Var(_, type_id) => {
                type_id.extract_generic_params(db, generic_parameters, visited)?
            }
            ConstValue::Missing(diagnostic_added) => return Err(*diagnostic_added),
        }
        Ok(())
    }
}

/// Moves the value of a felt252, to the range of `[range_min, range_min + PRIME)`.
pub fn felt252_for_downcast(value: &BigInt, range_min: &BigInt) -> BigInt {
    Felt252::from(value - range_min).to_bigint() + range_min
}

/// Canonicalize the value of a felt252, to the range of `(-PRIME, PRIME)`.
pub fn canonical_felt252(value: &BigInt) -> BigInt {
    value % &*CAIRO_PRIME_BIGINT
}

/// A constant value.
#[derive(Clone, Debug, Hash, PartialEq, Eq, SemanticObject, HeapSize, salsa::Update)]
pub enum ConstValue<'db> {
    Int(#[dont_rewrite] BigInt, TypeId<'db>),
    Struct(Vec<ConstValueId<'db>>, TypeId<'db>),
    Enum(ConcreteVariant<'db>, ConstValueId<'db>),
    NonZero(ConstValueId<'db>),
    Generic(#[dont_rewrite] GenericParamId<'db>),
    ImplConstant(ImplConstantId<'db>),
    Var(ConstVar<'db>, TypeId<'db>),
    /// A missing value, used in cases where the value is not known due to diagnostics.
    Missing(#[dont_rewrite] DiagnosticAdded),
}
impl<'db> ConstValue<'db> {
    /// Returns true if the const does not depend on any generics.
    pub fn is_fully_concrete(&self, db: &dyn Database) -> bool {
        self.ty(db).unwrap().is_fully_concrete(db)
            && match self {
                ConstValue::Int(_, _) => true,
                ConstValue::Struct(members, _) => {
                    members.iter().all(|member| member.is_fully_concrete(db))
                }
                ConstValue::Enum(_, val) | ConstValue::NonZero(val) => val.is_fully_concrete(db),
                ConstValue::Generic(_)
                | ConstValue::Var(_, _)
                | ConstValue::Missing(_)
                | ConstValue::ImplConstant(_) => false,
            }
    }

    /// Returns true if the const does not contain any inference variables.
    pub fn is_var_free(&self, db: &dyn Database) -> bool {
        self.ty(db).unwrap().is_var_free(db)
            && match self {
                ConstValue::Int(_, _) | ConstValue::Generic(_) | ConstValue::Missing(_) => true,
                ConstValue::Struct(members, _) => {
                    members.iter().all(|member| member.is_var_free(db))
                }
                ConstValue::Enum(_, val) | ConstValue::NonZero(val) => val.is_var_free(db),
                ConstValue::Var(_, _) => false,
                ConstValue::ImplConstant(impl_constant) => impl_constant.impl_id().is_var_free(db),
            }
    }

    /// Returns the type of the const.
    pub fn ty(&self, db: &'db dyn Database) -> Maybe<TypeId<'db>> {
        Ok(match self {
            ConstValue::Int(_, ty) => *ty,
            ConstValue::Struct(_, ty) => *ty,
            ConstValue::Enum(variant, _) => {
                TypeLongId::Concrete(ConcreteTypeId::Enum(variant.concrete_enum_id)).intern(db)
            }
            ConstValue::NonZero(value) => core_nonzero_ty(db, value.ty(db)?),
            ConstValue::Generic(param) => {
                extract_matches!(db.generic_param_semantic(*param)?, GenericParam::Const).ty
            }
            ConstValue::Var(_, ty) => *ty,
            ConstValue::Missing(_) => TypeId::missing(db, skip_diagnostic()),
            ConstValue::ImplConstant(impl_constant_id) => {
                db.impl_constant_concrete_implized_type(*impl_constant_id)?
            }
        })
    }

    /// Returns the value of an int const as a BigInt.
    pub fn to_int(&self) -> Option<&BigInt> {
        match self {
            ConstValue::Int(value, _) => Some(value),
            _ => None,
        }
    }
}

/// An impl item of kind const.
#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, SemanticObject, HeapSize, salsa::Update)]
pub struct ImplConstantId<'db> {
    /// The impl the item const is in.
    impl_id: ImplId<'db>,
    /// The trait const this impl const "implements".
    trait_constant_id: TraitConstantId<'db>,
}

impl<'db> ImplConstantId<'db> {
    /// Creates a new impl constant id. For an impl constant of a concrete impl, asserts that the
    /// trait constant belongs to the same trait that the impl implements (panics if not).
    pub fn new(
        impl_id: ImplId<'db>,
        trait_constant_id: TraitConstantId<'db>,
        db: &dyn Database,
    ) -> Self {
        if let ImplLongId::Concrete(concrete_impl) = impl_id.long(db) {
            let impl_def_id = concrete_impl.impl_def_id(db);
            assert_eq!(Ok(trait_constant_id.trait_id(db)), db.impl_def_trait(impl_def_id));
        }

        ImplConstantId { impl_id, trait_constant_id }
    }
    pub fn impl_id(&self) -> ImplId<'db> {
        self.impl_id
    }
    pub fn trait_constant_id(&self) -> TraitConstantId<'db> {
        self.trait_constant_id
    }

    pub fn format(&self, db: &dyn Database) -> String {
        format!("{}::{}", self.impl_id.name(db), self.trait_constant_id.name(db).long(db))
    }
}
impl<'db> DebugWithDb<'db> for ImplConstantId<'db> {
    type Db = dyn Database;

    fn fmt(&self, f: &mut std::fmt::Formatter<'_>, db: &'db dyn Database) -> std::fmt::Result {
        write!(f, "{}", self.format(db))
    }
}

/// Returns the semantic data of a constant.
#[salsa::tracked(returns(ref), cycle_result=constant_semantic_data_cycle)]
fn constant_semantic_data<'db>(
    db: &'db dyn Database,
    const_id: ConstantId<'db>,
    in_cycle: bool,
) -> Maybe<ConstantData<'db>> {
    let lookup_item_id = LookupItemId::ModuleItem(ModuleItemId::Constant(const_id));
    if in_cycle {
        constant_semantic_data_cycle_helper(
            db,
            &db.module_constant_by_id(const_id)?,
            lookup_item_id,
            None,
            &const_id,
        )
    } else {
        constant_semantic_data_helper(
            db,
            &db.module_constant_by_id(const_id)?,
            lookup_item_id,
            None,
            &const_id,
        )
    }
}

/// Cycle handling for [ConstantSemantic::constant_semantic_data].
fn constant_semantic_data_cycle<'db>(
    db: &'db dyn Database,
    _id: salsa::Id,
    const_id: ConstantId<'db>,
    _in_cycle: bool,
) -> Maybe<ConstantData<'db>> {
    let lookup_item_id = LookupItemId::ModuleItem(ModuleItemId::Constant(const_id));
    constant_semantic_data_cycle_helper(
        db,
        &db.module_constant_by_id(const_id)?,
        lookup_item_id,
        None,
        &const_id,
    )
}

/// Returns constant semantic data for the given ItemConstant.
pub fn constant_semantic_data_helper<'db>(
    db: &'db dyn Database,
    constant_ast: &ItemConstant<'db>,
    lookup_item_id: LookupItemId<'db>,
    parent_resolver_data: Option<Arc<ResolverData<'db>>>,
    element_id: &impl LanguageElementId<'db>,
) -> Maybe<ConstantData<'db>> {
    let module_id = element_id.parent_module(db);
    let mut diagnostics: SemanticDiagnostics<'_> = SemanticDiagnostics::new(module_id);
    // TODO(spapini): when code changes in a file, all the AST items change (as they contain a path
    // to the green root that changes. Once ASTs are rooted on items, use a selector that picks only
    // the item instead of all the module data.

    let inference_id = InferenceId::LookupItemDeclaration(lookup_item_id);

    let mut resolver = match parent_resolver_data {
        Some(parent_resolver_data) => {
            Resolver::with_data(db, parent_resolver_data.clone_with_inference_id(db, inference_id))
        }
        None => Resolver::new(db, module_id, inference_id),
    };
    resolver.set_feature_config(element_id, constant_ast, &mut diagnostics);

    let ty_syntax = constant_ast.type_clause(db).ty(db);
    let constant_type = resolve_type(db, &mut diagnostics, &mut resolver, &ty_syntax);
    // The type of a constant must not rely on its value, to create better stability for the
    // constant signature.
    if !constant_type.is_var_free(db) {
        diagnostics.report(
            ty_syntax.stable_ptr(db).untyped(),
            SemanticDiagnosticKind::ConstTypeNotVarFree,
        );
    }

    let mut ctx = ComputationContext::new_global(db, &mut diagnostics, &mut resolver);
    let value = compute_expr_semantic(&mut ctx, &constant_ast.value(db));
    let const_value = resolve_const_expr_and_evaluate(
        db,
        &mut ctx,
        &value,
        constant_ast.stable_ptr(db).untyped(),
        constant_type,
        true,
    );
    let constant = Ok(Constant { value: value.id, arenas: Arc::new(ctx.arenas) });
    let const_value = resolver
        .inference()
        .rewrite(const_value)
        .unwrap_or_else(|_| ConstValue::Missing(skip_diagnostic()).intern(db));
    let resolver_data = Arc::new(resolver.data);
    Ok(ConstantData { diagnostics: diagnostics.build(), const_value, constant, resolver_data })
}

/// Helper for cycle handling of constants.
pub fn constant_semantic_data_cycle_helper<'db>(
    db: &'db dyn Database,
    constant_ast: &ItemConstant<'db>,
    lookup_item_id: LookupItemId<'db>,
    parent_resolver_data: Option<Arc<ResolverData<'db>>>,
    element_id: &impl LanguageElementId<'db>,
) -> Maybe<ConstantData<'db>> {
    let module_id = element_id.parent_module(db);
    let mut diagnostics: SemanticDiagnostics<'_> = SemanticDiagnostics::new(module_id);

    let inference_id = InferenceId::LookupItemDeclaration(lookup_item_id);

    let resolver = match parent_resolver_data {
        Some(parent_resolver_data) => {
            Resolver::with_data(db, parent_resolver_data.clone_with_inference_id(db, inference_id))
        }
        None => Resolver::new(db, module_id, inference_id),
    };

    let resolver_data = Arc::new(resolver.data);

    let diagnostic_added =
        diagnostics.report(constant_ast.stable_ptr(db), SemanticDiagnosticKind::ConstCycle);
    Ok(ConstantData {
        constant: Err(diagnostic_added),
        const_value: ConstValue::Missing(diagnostic_added).intern(db),
        diagnostics: diagnostics.build(),
        resolver_data,
    })
}

/// Checks if the given expression only involved constant calculations.
pub fn validate_const_expr<'db>(ctx: &mut ComputationContext<'db, '_>, expr_id: ExprId) {
    let info = ctx.db.const_calc_info();
    let mut eval_ctx = ConstantEvaluateContext {
        db: ctx.db,
        info: info.as_ref(),
        arenas: &ctx.arenas,
        vars: Default::default(),
        generic_substitution: Default::default(),
        depth: 0,
        diagnostics: ctx.diagnostics,
    };
    eval_ctx.validate(expr_id);
}

/// Resolves the given const expression and evaluates its value.
pub fn resolve_const_expr_and_evaluate<'db, 'mt>(
    db: &'db dyn Database,
    ctx: &'mt mut ComputationContext<'db, '_>,
    value: &ExprAndId<'db>,
    const_stable_ptr: SyntaxStablePtrId<'db>,
    target_type: TypeId<'db>,
    finalize: bool,
) -> ConstValueId<'db> {
    let prev_err_count = ctx.diagnostics.error_count;
    let mut_ref = &mut ctx.resolver;
    let mut inference: crate::expr::inference::Inference<'db, '_> = mut_ref.inference();
    if let Err(err_set) = inference.conform_ty(value.ty(), target_type) {
        inference.report_on_pending_error(err_set, ctx.diagnostics, value.stable_ptr().untyped());
    }

    if finalize {
        // Check fully resolved.
        inference.finalize(ctx.diagnostics, const_stable_ptr);
    } else if let Err(err_set) = inference.solve() {
        inference.report_on_pending_error(err_set, ctx.diagnostics, const_stable_ptr);
    }
    ctx.apply_inference_rewriter();

    match &value.expr {
        Expr::Constant(ExprConstant { const_value_id, .. }) => *const_value_id,
        // Check that the expression is a valid constant.
        _ if ctx.diagnostics.error_count > prev_err_count => {
            ConstValue::Missing(skip_diagnostic()).intern(db)
        }
        _ => {
            let info = db.const_calc_info();
            let mut eval_ctx = ConstantEvaluateContext {
                db,
                info: info.as_ref(),
                arenas: &ctx.arenas,
                vars: Default::default(),
                generic_substitution: Default::default(),
                depth: 0,
                diagnostics: ctx.diagnostics,
            };
            eval_ctx.validate(value.id);
            if eval_ctx.diagnostics.error_count > prev_err_count {
                ConstValue::Missing(skip_diagnostic()).intern(db)
            } else {
                eval_ctx.evaluate(value.id)
            }
        }
    }
}

/// A context for evaluating constant expressions.
struct ConstantEvaluateContext<'a, 'r, 'mt> {
    db: &'a dyn Database,
    info: &'r ConstCalcInfo<'a>,
    arenas: &'r Arenas<'a>,
    vars: OrderedHashMap<VarId<'a>, ConstValueId<'a>>,
    generic_substitution: GenericSubstitution<'a>,
    depth: usize,
    diagnostics: &'mt mut SemanticDiagnostics<'a>,
}

/// Evaluates the `Ok` value of an expression, or returning the `Err` value from the function.
macro_rules! or_return {
    ($expr:expr) => {
        match $expr {
            Ok(value) => value,
            Err(err) => {
                return err;
            }
        }
    };
}

impl<'a, 'r, 'mt> ConstantEvaluateContext<'a, 'r, 'mt> {
    /// Validate the given expression can be used as constant.
    fn validate(&mut self, expr_id: ExprId) {
        match &self.arenas.exprs[expr_id] {
            Expr::Var(_) | Expr::Constant(_) | Expr::Missing(_) => {}
            Expr::Block(ExprBlock { statements, tail: Some(inner), .. }) => {
                for statement_id in statements {
                    match &self.arenas.statements[*statement_id] {
                        Statement::Let(statement) => {
                            self.validate(statement.expr);
                            if let Some(else_clause) = &statement.else_clause {
                                self.validate(*else_clause);
                            }
                        }
                        Statement::Expr(expr) => {
                            self.validate(expr.expr);
                        }
                        other => {
                            self.diagnostics.report(
                                other.stable_ptr(),
                                SemanticDiagnosticKind::UnsupportedConstant,
                            );
                        }
                    }
                }
                self.validate(*inner);
            }
            Expr::FunctionCall(expr) => {
                for arg in &expr.args {
                    match arg {
                        ExprFunctionCallArg::Value(arg) => self.validate(*arg),
                        ExprFunctionCallArg::Reference(var) => {
                            self.diagnostics.report(
                                var.stable_ptr(),
                                SemanticDiagnosticKind::UnsupportedConstant,
                            );
                        }
                        ExprFunctionCallArg::TempReference(expr_id) => {
                            self.diagnostics.report(
                                self.arenas.exprs[*expr_id].stable_ptr(),
                                SemanticDiagnosticKind::UnsupportedConstant,
                            );
                        }
                    }
                }
                if !self.is_function_const(expr.function) {
                    self.diagnostics.report(
                        expr.stable_ptr.untyped(),
                        SemanticDiagnosticKind::UnsupportedConstant,
                    );
                }
            }
            // Already validated by `apply_inference_rewriter`.
            Expr::Literal(_) => {}
            Expr::Tuple(expr) => {
                for item in &expr.items {
                    self.validate(*item);
                }
            }
            Expr::StructCtor(ExprStructCtor { members, base_struct, .. }) => {
                for (expr_id, _) in members {
                    self.validate(*expr_id);
                }
                if let Some(base) = base_struct {
                    self.validate(*base);
                }
            }
            Expr::EnumVariantCtor(expr) => self.validate(expr.value_expr),
            Expr::MemberAccess(expr) => self.validate(expr.expr),
            Expr::FixedSizeArray(expr) => match &expr.items {
                crate::FixedSizeArrayItems::Items(items) => {
                    for item in items {
                        self.validate(*item);
                    }
                }
                crate::FixedSizeArrayItems::ValueAndSize(value, _) => {
                    self.validate(*value);
                }
            },
            Expr::Snapshot(expr) => self.validate(expr.inner),
            Expr::Desnap(expr) => self.validate(expr.inner),
            Expr::LogicalOperator(expr) => {
                self.validate(expr.lhs);
                self.validate(expr.rhs);
            }
            Expr::Match(expr) => {
                self.validate(expr.matched_expr);
                for arm in &expr.arms {
                    self.validate(arm.expression);
                }
            }
            Expr::If(expr) => {
                for condition in &expr.conditions {
                    self.validate(match condition {
                        Condition::BoolExpr(id) | Condition::Let(id, _) => *id,
                    });
                }
                self.validate(expr.if_block);
                if let Some(else_block) = expr.else_block {
                    self.validate(else_block);
                }
            }
            other => {
                self.diagnostics.report(
                    other.stable_ptr().untyped(),
                    SemanticDiagnosticKind::UnsupportedConstant,
                );
            }
        }
    }

    /// Returns true if the given function is allowed to be called in constant context.
    fn is_function_const(&self, function_id: FunctionId<'a>) -> bool {
        if function_id == self.panic_with_felt252 {
            return true;
        }
        let db = self.db;
        let concrete_function = function_id.get_concrete(db);
        let signature = (|| match concrete_function.generic_function {
            GenericFunctionId::Free(id) => db.free_function_signature(id),
            GenericFunctionId::Extern(id) => db.extern_function_signature(id),
            GenericFunctionId::Impl(id) => {
                if let ImplLongId::Concrete(impl_id) = id.impl_id.long(db)
                    && let Ok(Some(impl_function_id)) = impl_id.get_impl_function(db, id.function)
                {
                    return self.db.impl_function_signature(impl_function_id);
                }
                self.db.trait_function_signature(id.function)
            }
        })();
        if signature.map(|s| s.is_const) == Ok(true) {
            return true;
        }
        let Ok(Some(body)) = concrete_function.body(db) else { return false };
        let GenericFunctionWithBodyId::Impl(imp) = body.generic_function(db) else {
            return false;
        };
        let impl_def = imp.concrete_impl_id.impl_def_id(db);
        if impl_def.parent_module(db).owning_crate(db) != db.core_crate() {
            return false;
        }
        let Ok(trait_id) = db.impl_def_trait(impl_def) else {
            return false;
        };
        self.const_traits.contains(&trait_id)
    }

    /// Evaluate the given const expression value.
    fn evaluate<'ctx>(&'ctx mut self, expr_id: ExprId) -> ConstValueId<'a> {
        let expr = &self.arenas.exprs[expr_id];
        let db = self.db;
        let to_missing = |diag_added| ConstValue::Missing(diag_added).intern(db);
        match expr {
            Expr::Var(expr) => self.vars.get(&expr.var).copied().unwrap_or_else(|| {
                to_missing(
                    self.diagnostics
                        .report(expr.stable_ptr, SemanticDiagnosticKind::UnsupportedConstant),
                )
            }),
            Expr::Constant(expr) => {
                or_return!(self.substitute(expr.const_value_id).map_err(to_missing))
            }
            Expr::Block(ExprBlock { statements, tail: Some(inner), .. }) => {
                for statement_id in statements {
                    match &self.arenas.statements[*statement_id] {
                        Statement::Let(statement) => {
                            let value = self.evaluate(statement.expr);
                            if self.destructure_pattern(statement.pattern, value).is_none() {
                                if let Some(else_clause) = &statement.else_clause {
                                    // Only exiting the block is possible - so this is a return of a
                                    // panic.
                                    return self.evaluate(*else_clause);
                                } else {
                                    // Either the pattern is refutable and we are missing an else
                                    // clause, or the pattern is irrefutable and the pattern have
                                    // failed for some reason. Both should already cause diagstics.
                                    return to_missing(skip_diagnostic());
                                }
                            }
                        }
                        Statement::Expr(expr) => {
                            self.evaluate(expr.expr);
                        }
                        other => {
                            self.diagnostics.report(
                                other.stable_ptr(),
                                SemanticDiagnosticKind::UnsupportedConstant,
                            );
                        }
                    }
                }
                self.evaluate(*inner)
            }
            Expr::FunctionCall(expr) => self.evaluate_function_call(expr),
            Expr::Literal(expr) => ConstValueId::from_int(db, expr.ty, &expr.value),
            Expr::Tuple(expr) => ConstValue::Struct(
                expr.items.iter().map(|expr_id| self.evaluate(*expr_id)).collect(),
                or_return!(self.substitute(expr.ty).map_err(to_missing)),
            )
            .intern(db),
            Expr::StructCtor(ExprStructCtor {
                members,
                base_struct,
                ty,
                concrete_struct_id,
                ..
            }) => {
                let member_order =
                    or_return!(db.concrete_struct_members(*concrete_struct_id).map_err(to_missing));
                let ty = or_return!(self.substitute(*ty).map_err(to_missing));
                let base_members = match base_struct {
                    Some(base) => match self.evaluate(*base).long(db) {
                        ConstValue::Struct(values, base_ty) if *base_ty == ty => {
                            Some(values.as_slice())
                        }
                        _ => return to_missing(skip_diagnostic()),
                    },
                    None => None,
                };
                ConstValue::Struct(
                    member_order
                        .values()
                        .enumerate()
                        .map(|(index, m)| {
                            members
                                .iter()
                                .find(|(_, member_id)| m.id == *member_id)
                                .map(|(expr_id, _)| self.evaluate(*expr_id))
                                .or_else(|| Some(base_members?[index]))
                                // Semantic validation already reported an error, suppress cascading
                                // errors from const evaluation.
                                .unwrap_or_else(|| to_missing(skip_diagnostic()))
                        })
                        .collect(),
                    ty,
                )
                .intern(db)
            }
            Expr::EnumVariantCtor(expr) => ConstValue::Enum(
                or_return!(self.substitute(expr.variant).map_err(to_missing)),
                self.evaluate(expr.value_expr),
            )
            .intern(db),
            Expr::MemberAccess(expr) => {
                self.evaluate_member_access(expr).unwrap_or_else(to_missing)
            }
            Expr::FixedSizeArray(expr) => ConstValue::Struct(
                match &expr.items {
                    crate::FixedSizeArrayItems::Items(items) => {
                        items.iter().map(|expr_id| self.evaluate(*expr_id)).collect()
                    }
                    crate::FixedSizeArrayItems::ValueAndSize(value, count) => {
                        let value = self.evaluate(*value);
                        if let Some(count) = count.to_int(db) {
                            vec![value; count.to_usize().unwrap()]
                        } else {
                            self.diagnostics.report(
                                expr.stable_ptr.untyped(),
                                SemanticDiagnosticKind::UnsupportedConstant,
                            );
                            vec![]
                        }
                    }
                },
                or_return!(self.substitute(expr.ty).map_err(to_missing)),
            )
            .intern(db),
            Expr::Snapshot(expr) => self.evaluate(expr.inner),
            Expr::Desnap(expr) => self.evaluate(expr.inner),
            Expr::LogicalOperator(expr) => {
                let lhs = self.evaluate(expr.lhs);
                if let ConstValue::Enum(v, _) = lhs.long(db) {
                    let early_return_variant = match expr.op {
                        LogicalOperator::AndAnd => false_variant(self.db),
                        LogicalOperator::OrOr => true_variant(self.db),
                    };
                    if *v == early_return_variant { lhs } else { self.evaluate(expr.rhs) }
                } else if let ConstValue::Missing(diag_added) = lhs.long(db) {
                    to_missing(*diag_added)
                } else {
                    to_missing(self.diagnostics.report(
                        self.arenas.exprs[expr.lhs].stable_ptr(),
                        SemanticDiagnosticKind::UnsupportedConstant,
                    ))
                }
            }
            Expr::Match(expr) => {
                let value = self.evaluate(expr.matched_expr);
                for arm in &expr.arms {
                    for pattern_id in &arm.patterns {
                        if self.destructure_pattern(*pattern_id, value).is_some() {
                            return self.evaluate(arm.expression);
                        }
                    }
                }
                to_missing(
                    self.diagnostics.report(
                        expr.stable_ptr.untyped(),
                        SemanticDiagnosticKind::UnsupportedConstant,
                    ),
                )
            }
            Expr::If(expr) => {
                let mut if_condition: bool = true;
                for condition in &expr.conditions {
                    match condition {
                        crate::Condition::BoolExpr(id) => {
                            let condition = self.evaluate(*id);
                            if condition == self.true_const {
                                continue;
                            } else if condition == self.false_const {
                                if_condition = false;
                                break;
                            } else {
                                return to_missing(skip_diagnostic());
                            }
                        }
                        crate::Condition::Let(id, patterns) => {
                            let value = self.evaluate(*id);
                            let mut found_pattern = false;
                            for pattern_id in patterns {
                                if self.destructure_pattern(*pattern_id, value).is_some() {
                                    found_pattern = true;
                                    break;
                                }
                            }
                            if !found_pattern {
                                if_condition = false;
                                break;
                            }
                        }
                    }
                }

                if if_condition {
                    self.evaluate(expr.if_block)
                } else if let Some(else_block) = expr.else_block {
                    self.evaluate(else_block)
                } else {
                    self.unit_const
                }
            }
            _ => to_missing(skip_diagnostic()),
        }
    }

    /// Attempts to evaluate constants from a const function call.
    fn evaluate_function_call(&mut self, expr: &ExprFunctionCall<'a>) -> ConstValueId<'a> {
        let db = self.db;
        let to_missing = |diag_added| ConstValue::Missing(diag_added).intern(db);
        let args = expr
            .args
            .iter()
            .filter_map(|arg| try_extract_matches!(arg, ExprFunctionCallArg::Value))
            .map(|arg| {
                let value = self.evaluate(*arg);
                if value.is_fully_concrete(db) || matches!(value.long(db), ConstValue::Missing(_)) {
                    value
                } else {
                    to_missing(self.diagnostics.report(
                        self.arenas.exprs[*arg].stable_ptr(),
                        SemanticDiagnosticKind::UnsupportedConstant,
                    ))
                }
            })
            .collect_vec();
        if expr.function == self.panic_with_felt252 {
            return to_missing(self.diagnostics.report(
                expr.stable_ptr.untyped(),
                SemanticDiagnosticKind::FailedConstantCalculation,
            ));
        }
        let concrete_function =
            or_return!(self.substitute(expr.function.get_concrete(db)).map_err(to_missing));
        if let Some(calc_result) =
            self.evaluate_const_function_call(&concrete_function, &args, expr)
        {
            return calc_result;
        }

        let GenericFunctionId::Impl(imp) = concrete_function.generic_function else {
            return to_missing(skip_diagnostic());
        };
        let bool_value = |condition: bool| {
            if condition { self.true_const } else { self.false_const }
        };

        if imp.function == self.eq_fn {
            return bool_value(self.const_values_eq(args[0], args[1]));
        } else if imp.function == self.ne_fn {
            return bool_value(!self.const_values_eq(args[0], args[1]));
        } else if args.iter().all(|arg| [self.false_const, self.true_const].contains(arg)) {
            let as_bool = |v| v == self.true_const;
            if imp.function == self.not_fn {
                return bool_value(!as_bool(args[0]));
            } else if imp.function == self.bitand_fn {
                return bool_value(as_bool(args[0]) & as_bool(args[1]));
            } else if imp.function == self.bitor_fn {
                return bool_value(as_bool(args[0]) | as_bool(args[1]));
            } else if imp.function == self.bitxor_fn {
                return bool_value(as_bool(args[0]) ^ as_bool(args[1]));
            }
        }

        let args = match args
            .into_iter()
            .map(|arg| NumericArg::try_new(db, arg))
            .collect::<Option<Vec<_>>>()
        {
            Some(args) => args,
            None => return to_missing(skip_diagnostic()),
        };
        let value = match imp.function {
            id if id == self.neg_fn => -&args[0].v,
            id if id == self.add_fn => &args[0].v + &args[1].v,
            id if id == self.sub_fn => &args[0].v - &args[1].v,
            id if id == self.mul_fn => &args[0].v * &args[1].v,
            id if (id == self.div_fn || id == self.rem_fn) && args[1].v.is_zero() => {
                return to_missing(
                    self.diagnostics
                        .report(expr.stable_ptr.untyped(), SemanticDiagnosticKind::DivisionByZero),
                );
            }
            id if id == self.div_fn => &args[0].v / &args[1].v,
            id if id == self.rem_fn => &args[0].v % &args[1].v,
            id if id == self.bitand_fn => &args[0].v & &args[1].v,
            id if id == self.bitor_fn => &args[0].v | &args[1].v,
            id if id == self.bitxor_fn => &args[0].v ^ &args[1].v,
            id if id == self.lt_fn => return bool_value(args[0].v < args[1].v),
            id if id == self.le_fn => return bool_value(args[0].v <= args[1].v),
            id if id == self.gt_fn => return bool_value(args[0].v > args[1].v),
            id if id == self.ge_fn => return bool_value(args[0].v >= args[1].v),
            id if id == self.div_rem_fn => {
                // No need for non-zero check as this is type checked to begin with.
                let (q, r) = args[0].v.div_rem(&args[1].v);
                let ty = args[0].ty;
                // The quotient may overflow for signed `MIN / -1`, so it must be validated.
                if let Err(err) = validate_literal(db, ty, &q) {
                    return to_missing(self.diagnostics.report(
                        expr.stable_ptr.untyped(),
                        SemanticDiagnosticKind::LiteralError(err),
                    ));
                }
                return ConstValue::Struct(
                    vec![ConstValueId::from_int(db, ty, &q), ConstValueId::from_int(db, ty, &r)],
                    expr.ty,
                )
                .intern(db);
            }
            _ => return to_missing(skip_diagnostic()),
        };
        if expr.ty == self.felt252 {
            ConstValue::Int(canonical_felt252(&value), expr.ty).intern(db)
        } else if let Err(err) = validate_literal(db, expr.ty, &value) {
            to_missing(
                self.diagnostics
                    .report(expr.stable_ptr.untyped(), SemanticDiagnosticKind::LiteralError(err)),
            )
        } else {
            ConstValueId::from_int(db, expr.ty, &value)
        }
    }

    /// Attempts to evaluate a constant function call.
    fn evaluate_const_function_call(
        &mut self,
        concrete_function: &ConcreteFunction<'a>,
        args: &[ConstValueId<'a>],
        expr: &ExprFunctionCall<'a>,
    ) -> Option<ConstValueId<'a>> {
        let db = self.db;
        if let GenericFunctionId::Extern(extern_fn) = concrete_function.generic_function {
            let expr_ty = self.substitute(expr.ty).ok()?;
            if self.upcast_fns.contains(&extern_fn) {
                let [arg] = args else { return None };
                return Some(ConstValueId::from_int(db, expr_ty, arg.to_int(db)?));
            } else if self.unwrap_non_zero == extern_fn {
                let [arg] = args else { return None };
                return try_extract_matches!(arg.long(db), ConstValue::NonZero).copied();
            } else if self.u128s_from_felt252 == extern_fn {
                let [arg] = args else { return None };
                let TypeLongId::Concrete(ConcreteTypeId::Enum(enm)) = expr_ty.long(db) else {
                    return None;
                };
                let (narrow, wide) =
                    db.concrete_enum_variants(*enm).ok()?.into_iter().collect_tuple()?;
                let value = Felt252::from(arg.to_int(db)?).to_bigint();
                let mask128 = BigInt::from(u128::MAX);
                let low = (&value) & mask128;
                let high: BigInt = (&value) >> 128;
                return Some(if high.is_zero() {
                    ConstValue::Enum(narrow, ConstValue::Int(low, narrow.ty).intern(db)).intern(db)
                } else {
                    ConstValue::Enum(
                        wide,
                        ConstValue::Struct(
                            vec![
                                (ConstValue::Int(high, self.u128).intern(db)),
                                (ConstValue::Int(low, self.u128).intern(db)),
                            ],
                            wide.ty,
                        )
                        .intern(db),
                    )
                    .intern(db)
                });
            } else if let Some(reversed) = self.downcast_fns.get(&extern_fn) {
                let [arg] = args else { return None };
                let ConstValue::Int(value, input_ty) = arg.long(db) else { return None };
                let TypeLongId::Concrete(ConcreteTypeId::Enum(enm)) = expr_ty.long(db) else {
                    return None;
                };
                let (variant0, variant1) =
                    db.concrete_enum_variants(*enm).ok()?.into_iter().collect_tuple()?;
                let (some, none) =
                    if *reversed { (variant1, variant0) } else { (variant0, variant1) };
                let success_ty = some.ty;
                let out_range = self
                    .type_value_ranges
                    .get(&success_ty)
                    .cloned()
                    .or_else(|| {
                        let (min, max) = try_extract_bounded_int_type(db, success_ty)?;
                        Some(TypeRange::new(min.to_int(db)?.clone(), max.to_int(db)?.clone()))
                    })
                    .unwrap_or_else(|| {
                        unreachable!(
                            "`downcast` is only allowed into types that can be literals. Got `{}`.",
                            success_ty.format(db)
                        )
                    });
                let value = if *input_ty == self.felt252 {
                    felt252_for_downcast(value, &out_range.min)
                } else {
                    value.clone()
                };
                return Some(if value >= out_range.min && value <= out_range.max {
                    ConstValue::Enum(some, ConstValue::Int(value, success_ty).intern(db)).intern(db)
                } else {
                    ConstValue::Enum(none, self.unit_const).intern(db)
                });
            } else if self.nz_fns.contains(&extern_fn) {
                let [arg] = args else { return None };
                let (ty, is_zero) = match arg.long(db) {
                    ConstValue::Int(val, ty) => (ty, val.is_zero()),
                    ConstValue::Struct(members, ty) => (
                        ty,
                        // For u256 struct with (low, high), check if both are zero
                        members.iter().all(|member| match member.long(db) {
                            ConstValue::Int(val, _) => val.is_zero(),
                            _ => false,
                        }),
                    ),
                    _ => unreachable!(
                        "`is_zero` is only allowed for integers got `{}`",
                        arg.ty(db).unwrap().format(db)
                    ),
                };

                return Some(
                    if is_zero {
                        ConstValue::Enum(
                            crate::corelib::jump_nz_zero_variant(db, *ty),
                            self.unit_const,
                        )
                    } else {
                        ConstValue::Enum(
                            crate::corelib::jump_nz_nonzero_variant(db, *ty),
                            ConstValue::NonZero(*arg).intern(db),
                        )
                    }
                    .intern(db),
                );
            } else {
                return Some(
                    ConstValue::Missing(self.diagnostics.report(
                        expr.stable_ptr.untyped(),
                        SemanticDiagnosticKind::UnsupportedConstant,
                    ))
                    .intern(db),
                );
            }
        }
        let body_id = concrete_function.body(db).ok()??;
        let concrete_body_id = body_id.function_with_body_id(db);
        let signature = db.function_with_body_signature(concrete_body_id).ok()?;
        require(signature.is_const)?;
        let generic_substitution = body_id.substitution(db).ok()?;
        let body = db.function_body(concrete_body_id).ok()?;
        const MAX_CONST_EVAL_DEPTH: usize = 100;
        if self.depth > MAX_CONST_EVAL_DEPTH {
            return Some(
                ConstValue::Missing(self.diagnostics.report(
                    expr.stable_ptr,
                    SemanticDiagnosticKind::ConstantCalculationDepthExceeded,
                ))
                .intern(db),
            );
        }
        let mut diagnostics = SemanticDiagnostics::new(concrete_body_id.parent_module(db));
        let mut inner = ConstantEvaluateContext {
            db,
            info: self.info,
            arenas: &body.arenas,
            vars: signature
                .params
                .iter()
                .map(|p| VarId::Param(p.id))
                .zip(args.iter().cloned())
                .collect(),
            generic_substitution,
            depth: self.depth + 1,
            diagnostics: &mut diagnostics,
        };
        let value = inner.evaluate(body.body_expr);
        for diagnostic in diagnostics.build().get_all() {
            let location = diagnostic.location(db);
            let (inner_diag, mut notes) = match diagnostic.kind {
                SemanticDiagnosticKind::ConstantCalculationDepthExceeded => {
                    self.diagnostics.report(
                        expr.stable_ptr,
                        SemanticDiagnosticKind::ConstantCalculationDepthExceeded,
                    );
                    continue;
                }
                SemanticDiagnosticKind::InnerFailedConstantCalculation(inner_diag, notes) => {
                    (inner_diag, notes)
                }
                _ => (diagnostic.into(), vec![]),
            };
            notes.push(DiagnosticNote::with_location(
                format!("In `{}`", concrete_function.full_path(db)),
                location,
            ));
            self.diagnostics.report(
                expr.stable_ptr,
                SemanticDiagnosticKind::InnerFailedConstantCalculation(inner_diag, notes),
            );
        }
        Some(value)
    }

    /// Extract const member access from a const value.
    fn evaluate_member_access(&mut self, expr: &ExprMemberAccess<'a>) -> Maybe<ConstValueId<'a>> {
        let full_struct = self.evaluate(expr.expr);
        let ConstValue::Struct(values, _) = full_struct.long(self.db) else {
            // A semantic diagnostic should have been reported.
            return Err(skip_diagnostic());
        };
        let member_idx = match &expr.kind {
            MemberAccessKind::Struct { concrete_struct_id, member_id } => {
                let members = self.db.concrete_struct_members(*concrete_struct_id)?;
                let Some(member_idx) =
                    members.iter().position(|(_, member)| member.id == *member_id)
                else {
                    // A semantic diagnostic should have been reported.
                    return Err(skip_diagnostic());
                };
                member_idx
            }
            MemberAccessKind::Index { index, .. } => *index,
        };
        Ok(values[member_idx])
    }

    /// Destructures the pattern, binding variables to their values; returns `None` if the pattern
    /// didn't match.
    fn destructure_pattern(
        &mut self,
        pattern_id: PatternId,
        value: ConstValueId<'a>,
    ) -> Option<()> {
        let db = self.db;
        let pattern = &self.arenas.patterns[pattern_id];
        match pattern {
            Pattern::Missing(_) | Pattern::StringLiteral(_) => None,
            Pattern::Otherwise(_) => Some(()),
            Pattern::Literal(v) => {
                let arg = NumericArg::try_new(db, value)?;
                require(self.eq_in_type(&arg.v, &v.literal.value, arg.ty))
            }
            Pattern::Variable(pattern) => {
                self.vars.insert(VarId::Local(pattern.var.id), value);
                Some(())
            }
            Pattern::Struct(pattern) => {
                let ConstValue::Struct(inner_values, _) = value.long(db) else {
                    return None;
                };
                let member_order = db.concrete_struct_members(pattern.concrete_struct_id).ok()?;
                for (member, inner_value) in zip(member_order.values(), inner_values) {
                    if let Some((inner_pattern, _)) =
                        pattern.field_patterns.iter().find(|(_, field)| member.id == field.id)
                    {
                        self.destructure_pattern(*inner_pattern, *inner_value)?;
                    }
                }
                Some(())
            }
            Pattern::Tuple(pattern) => {
                let ConstValue::Struct(inner_values, _) = value.long(db) else {
                    return None;
                };
                for (inner_pattern, inner_value) in zip(&pattern.field_patterns, inner_values) {
                    self.destructure_pattern(*inner_pattern, *inner_value)?;
                }
                Some(())
            }
            Pattern::FixedSizeArray(pattern) => {
                let ConstValue::Struct(inner_values, _) = value.long(db) else {
                    return None;
                };
                for (inner_pattern, inner_value) in zip(&pattern.elements_patterns, inner_values) {
                    self.destructure_pattern(*inner_pattern, *inner_value)?;
                }
                Some(())
            }
            Pattern::EnumVariant(pattern) => {
                let ConstValue::Enum(variant, inner_value) = value.long(db) else {
                    return None;
                };
                require(pattern.variant.id == variant.id)?;
                if let Some(inner_pattern) = pattern.inner_pattern {
                    self.destructure_pattern(inner_pattern, *inner_value)
                } else {
                    Some(())
                }
            }
        }
    }

    /// Substitutes generic parameters in the given object.
    fn substitute<'w, Obj>(&'w self, obj: Obj) -> Maybe<Obj>
    where
        SubstitutionRewriter<'a, 'w>: SemanticRewriter<Obj, DiagnosticAdded>,
    {
        self.generic_substitution.substitute(self.db, obj)
    }
    /// Compares two const values for value equality, treating `felt252` as a field.
    ///
    /// Direct `felt252` literals are stored in their original signed form (`-1` vs `PRIME - 1` are
    /// distinct `ConstValueId`s). The PartialEq operator must agree with the field, not with the
    /// stored representation, so we canonicalize `felt252` ints before comparing, and recurse into
    /// the structural variants - a `felt252` may be nested inside a struct, enum or `NonZero`.
    fn const_values_eq(&self, a: ConstValueId<'a>, b: ConstValueId<'a>) -> bool {
        if a == b {
            return true;
        }
        match (a.long(self.db), b.long(self.db)) {
            (ConstValue::Int(va, ty), ConstValue::Int(vb, _)) => self.eq_in_type(va, vb, *ty),
            (ConstValue::Struct(a_members, a_ty), ConstValue::Struct(b_members, b_ty)) => {
                a_ty == b_ty
                    && a_members.len() == b_members.len()
                    && zip(a_members, b_members).all(|(a, b)| self.const_values_eq(*a, *b))
            }
            (ConstValue::Enum(a_variant, a_value), ConstValue::Enum(b_variant, b_value)) => {
                a_variant.id == b_variant.id && self.const_values_eq(*a_value, *b_value)
            }
            (ConstValue::NonZero(a_value), ConstValue::NonZero(b_value)) => {
                self.const_values_eq(*a_value, *b_value)
            }
            _ => false,
        }
    }

    /// Compares two `BigInt`s of type `ty` for value equality, treating `felt252` as a field.
    fn eq_in_type(&self, a: &BigInt, b: &BigInt, ty: TypeId<'a>) -> bool {
        a == b || (ty == self.felt252 && Felt252::from(a) == Felt252::from(b))
    }
}

impl<'db, 'r> std::ops::Deref for ConstantEvaluateContext<'db, 'r, '_> {
    type Target = ConstCalcInfo<'db>;
    fn deref(&self) -> &Self::Target {
        self.info
    }
}

/// Helper for the arguments info.
struct NumericArg<'db> {
    /// The arg's integer value.
    v: BigInt,
    /// The arg's type, unwrapping `NonZero` types.
    ty: TypeId<'db>,
}
impl<'db> NumericArg<'db> {
    /// Extracts the numeric value and its type from `arg`, unwrapping `NonZero` values and reading
    /// a struct of 2 values as a `u256`.
    fn try_new(db: &'db dyn Database, arg: ConstValueId<'db>) -> Option<Self> {
        match arg.long(db) {
            ConstValue::Int(v, ty) => Some(Self { v: v.clone(), ty: *ty }),
            ConstValue::Struct(v, ty) if *ty == db.core_info().u256 => {
                if let [low, high] = &v[..] {
                    Some(Self { v: low.to_int(db)? + (high.to_int(db)? << 128), ty: *ty })
                } else {
                    None
                }
            }
            ConstValue::NonZero(inner) => Self::try_new(db, *inner),
            _ => None,
        }
    }
}

/// Query implementation of [ConstantSemantic::const_calc_info].
fn const_calc_info<'db>(db: &'db dyn Database) -> Arc<ConstCalcInfo<'db>> {
    Arc::new(ConstCalcInfo::new(db))
}

/// Implementation of [ConstantSemantic::const_calc_info].
#[salsa::tracked]
fn const_calc_info_tracked<'db>(db: &'db dyn Database) -> Arc<ConstCalcInfo<'db>> {
    const_calc_info(db)
}

/// Holds static information about extern functions required for const calculations.
#[derive(Debug, PartialEq, Eq, salsa::Update)]
pub struct ConstCalcInfo<'db> {
    /// Traits that are allowed for consts if their impls is in the corelib.
    const_traits: UnorderedHashSet<TraitId<'db>>,
    /// The const value for the unit type `()`.
    unit_const: ConstValueId<'db>,
    /// The const value for `true`.
    true_const: ConstValueId<'db>,
    /// The const value for `false`.
    false_const: ConstValueId<'db>,
    /// The function for panicking with a felt252.
    panic_with_felt252: FunctionId<'db>,
    /// The integer `upcast` style functions.
    pub upcast_fns: UnorderedHashSet<ExternFunctionId<'db>>,
    /// The integer `downcast` style functions, mapping to whether it returns a reversed Option
    /// enum.
    pub downcast_fns: UnorderedHashMap<ExternFunctionId<'db>, bool>,
    /// The `felt252` into `u128` words libfunc.
    pub u128s_from_felt252: ExternFunctionId<'db>,
    /// The `unwrap_non_zero` function.
    unwrap_non_zero: ExternFunctionId<'db>,
    /// The `is_zero` style functions.
    pub nz_fns: UnorderedHashSet<ExternFunctionId<'db>>,
    /// The range of values of a numeric type.
    pub type_value_ranges: UnorderedHashMap<TypeId<'db>, TypeRange>,

    core_info: Arc<CoreInfo<'db>>,
}

impl<'db> std::ops::Deref for ConstCalcInfo<'db> {
    type Target = CoreInfo<'db>;
    fn deref(&self) -> &CoreInfo<'db> {
        &self.core_info
    }
}

impl<'db> ConstCalcInfo<'db> {
    /// Creates a new ConstCalcInfo.
    fn new(db: &'db dyn Database) -> Self {
        let core_info = db.core_info();
        let unit_const = ConstValue::Struct(vec![], unit_ty(db)).intern(db);
        let core = ModuleHelper::core(db);
        let bounded_int = core.submodule("internal").submodule("bounded_int");
        let integer = core.submodule("integer");
        let zeroable = core.submodule("zeroable");
        let starknet = core.submodule("starknet");
        let class_hash_module = starknet.submodule("class_hash");
        let class_hash_ty = class_hash_module.ty("ClassHash", vec![]);
        let contract_address_module = starknet.submodule("contract_address");
        let contract_address_ty = contract_address_module.ty("ContractAddress", vec![]);
        Self {
            const_traits: FromIterator::from_iter([
                core_info.neg_trt,
                core_info.add_trt,
                core_info.sub_trt,
                core_info.mul_trt,
                core_info.div_trt,
                core_info.rem_trt,
                core_info.div_rem_trt,
                core_info.bitand_trt,
                core_info.bitor_trt,
                core_info.bitxor_trt,
                core_info.partialeq_trt,
                core_info.partialord_trt,
                core_info.not_trt,
            ]),
            true_const: ConstValue::Enum(true_variant(db), unit_const).intern(db),
            false_const: ConstValue::Enum(false_variant(db), unit_const).intern(db),
            unit_const,
            panic_with_felt252: core.function_id("panic_with_felt252", vec![]),
            upcast_fns: FromIterator::from_iter([
                bounded_int.extern_function_id("upcast"),
                integer.extern_function_id("u8_to_felt252"),
                integer.extern_function_id("u16_to_felt252"),
                integer.extern_function_id("u32_to_felt252"),
                integer.extern_function_id("u64_to_felt252"),
                integer.extern_function_id("u128_to_felt252"),
                integer.extern_function_id("i8_to_felt252"),
                integer.extern_function_id("i16_to_felt252"),
                integer.extern_function_id("i32_to_felt252"),
                integer.extern_function_id("i64_to_felt252"),
                integer.extern_function_id("i128_to_felt252"),
                class_hash_module.extern_function_id("class_hash_to_felt252"),
                contract_address_module.extern_function_id("contract_address_to_felt252"),
            ]),
            downcast_fns: FromIterator::from_iter([
                (bounded_int.extern_function_id("downcast"), false),
                (bounded_int.extern_function_id("bounded_int_trim_min"), true),
                (bounded_int.extern_function_id("bounded_int_trim_max"), true),
                (integer.extern_function_id("u8_try_from_felt252"), false),
                (integer.extern_function_id("u16_try_from_felt252"), false),
                (integer.extern_function_id("u32_try_from_felt252"), false),
                (integer.extern_function_id("u64_try_from_felt252"), false),
                (integer.extern_function_id("i8_try_from_felt252"), false),
                (integer.extern_function_id("i16_try_from_felt252"), false),
                (integer.extern_function_id("i32_try_from_felt252"), false),
                (integer.extern_function_id("i64_try_from_felt252"), false),
                (integer.extern_function_id("i128_try_from_felt252"), false),
                (class_hash_module.extern_function_id("class_hash_try_from_felt252"), false),
                (
                    contract_address_module.extern_function_id("contract_address_try_from_felt252"),
                    false,
                ),
            ]),
            u128s_from_felt252: integer.extern_function_id("u128s_from_felt252"),
            unwrap_non_zero: zeroable.extern_function_id("unwrap_non_zero"),
            nz_fns: FromIterator::from_iter([
                core.extern_function_id("felt252_is_zero"),
                bounded_int.extern_function_id("bounded_int_is_zero"),
                integer.extern_function_id("u8_is_zero"),
                integer.extern_function_id("u16_is_zero"),
                integer.extern_function_id("u32_is_zero"),
                integer.extern_function_id("u64_is_zero"),
                integer.extern_function_id("u128_is_zero"),
                integer.extern_function_id("u256_is_zero"),
            ]),
            type_value_ranges: FromIterator::from_iter([
                (core_info.u8, TypeRange::new(u8::MIN, u8::MAX)),
                (core_info.u16, TypeRange::new(u16::MIN, u16::MAX)),
                (core_info.u32, TypeRange::new(u32::MIN, u32::MAX)),
                (core_info.u64, TypeRange::new(u64::MIN, u64::MAX)),
                (core_info.u128, TypeRange::new(u128::MIN, u128::MAX)),
                (core_info.u256, TypeRange::new(BigInt::ZERO, (BigInt::from(1) << 256) - 1)),
                (core_info.i8, TypeRange::new(i8::MIN, i8::MAX)),
                (core_info.i16, TypeRange::new(i16::MIN, i16::MAX)),
                (core_info.i32, TypeRange::new(i32::MIN, i32::MAX)),
                (core_info.i64, TypeRange::new(i64::MIN, i64::MAX)),
                (core_info.i128, TypeRange::new(i128::MIN, i128::MAX)),
                // `ClassHash` and `ContractAddress` accept values in `[0, 2^251 - 1]`.
                (class_hash_ty, TypeRange::new(BigInt::ZERO, (BigInt::from(1) << 251) - 1)),
                (contract_address_ty, TypeRange::new(BigInt::ZERO, (BigInt::from(1) << 251) - 1)),
            ]),
            core_info,
        }
    }
}

/// Trait for constant-related semantic queries.
pub trait ConstantSemantic<'db>: Database {
    /// Returns the semantic diagnostics of a constant definition.
    fn constant_semantic_diagnostics(
        &'db self,
        const_id: ConstantId<'db>,
    ) -> Diagnostics<'db, SemanticDiagnostic<'db>> {
        let db = self.as_dyn_database();
        constant_semantic_data(db, const_id, false)
            .as_ref()
            .map(|data| data.diagnostics.clone())
            .unwrap_or_default()
    }
    /// Returns the semantic data of a constant definition.
    fn constant_semantic_data(&'db self, use_id: ConstantId<'db>) -> Maybe<Constant<'db>> {
        let db = self.as_dyn_database();
        constant_semantic_data(db, use_id, false).maybe_as_ref()?.constant.clone()
    }
    /// Returns the resolver data of a constant definition.
    fn constant_resolver_data(&'db self, use_id: ConstantId<'db>) -> Maybe<Arc<ResolverData<'db>>> {
        let db = self.as_dyn_database();
        Ok(constant_semantic_data(db, use_id, false).maybe_as_ref()?.resolver_data.clone())
    }
    /// Returns the const value of a constant definition.
    fn constant_const_value(&'db self, const_id: ConstantId<'db>) -> Maybe<ConstValueId<'db>> {
        let db = self.as_dyn_database();
        Ok(constant_semantic_data(db, const_id, false).maybe_as_ref()?.const_value)
    }
    /// Returns information required for const calculations.
    fn const_calc_info(&'db self) -> Arc<ConstCalcInfo<'db>> {
        const_calc_info_tracked(self.as_dyn_database())
    }
}
impl<'db, T: Database + ?Sized> ConstantSemantic<'db> for T {}

/// A range of values of a numeric type.
#[derive(Clone, Debug, PartialEq, Eq, salsa::Update)]
pub struct TypeRange {
    /// The minimum value of the range.
    pub min: BigInt,
    /// The maximum value of the range.
    pub max: BigInt,
}
impl TypeRange {
    pub fn new(min: impl Into<BigInt>, max: impl Into<BigInt>) -> Self {
        Self { min: min.into(), max: max.into() }
    }
}