cairo_lang_semantic/
types.rs

1use std::fmt::Write;
2
3use cairo_lang_debug::DebugWithDb;
4use cairo_lang_defs::diagnostic_utils::StableLocation;
5use cairo_lang_defs::ids::{
6    EnumId, ExternTypeId, GenericParamId, GenericTypeId, LanguageElementId, ModuleFileId, ModuleId,
7    NamedLanguageElementId, StructId, TraitTypeId, UnstableSalsaId,
8};
9use cairo_lang_diagnostics::{DiagnosticAdded, Maybe};
10use cairo_lang_proc_macros::SemanticObject;
11use cairo_lang_syntax::attribute::consts::MUST_USE_ATTR;
12use cairo_lang_syntax::node::db::SyntaxGroup;
13use cairo_lang_syntax::node::ids::SyntaxStablePtrId;
14use cairo_lang_syntax::node::{TypedStablePtr, TypedSyntaxNode, ast};
15use cairo_lang_utils::{Intern, LookupIntern, OptionFrom, define_short_id, try_extract_matches};
16use itertools::{Itertools, chain};
17use num_bigint::BigInt;
18use num_traits::Zero;
19use sha3::{Digest, Keccak256};
20use smol_str::SmolStr;
21
22use crate::corelib::{
23    concrete_copy_trait, concrete_destruct_trait, concrete_drop_trait,
24    concrete_panic_destruct_trait, core_submodule, get_usize_ty,
25};
26use crate::db::SemanticGroup;
27use crate::diagnostic::SemanticDiagnosticKind::*;
28use crate::diagnostic::{NotFoundItemType, SemanticDiagnostics, SemanticDiagnosticsBuilder};
29use crate::expr::compute::{
30    ComputationContext, ContextFunction, Environment, compute_expr_semantic,
31};
32use crate::expr::fmt::CountingWriter;
33use crate::expr::inference::canonic::{CanonicalTrait, ResultNoErrEx};
34use crate::expr::inference::solver::{SolutionSet, enrich_lookup_context};
35use crate::expr::inference::{InferenceData, InferenceError, InferenceId, TypeVar};
36use crate::items::attribute::SemanticQueryAttrs;
37use crate::items::constant::{ConstValue, ConstValueId, resolve_const_expr_and_evaluate};
38use crate::items::enm::SemanticEnumEx;
39use crate::items::generics::fmt_generic_args;
40use crate::items::imp::{ImplId, ImplLookupContext};
41use crate::resolve::{ResolutionContext, ResolvedConcreteItem, Resolver};
42use crate::substitution::SemanticRewriter;
43use crate::{ConcreteTraitId, FunctionId, GenericArgumentId, semantic, semantic_object_for_id};
44
45#[derive(Clone, Debug, Hash, PartialEq, Eq, SemanticObject)]
46pub enum TypeLongId {
47    Concrete(ConcreteTypeId),
48    /// Some expressions might have invalid types during processing, either due to errors or
49    /// during inference.
50    Tuple(Vec<TypeId>),
51    Snapshot(TypeId),
52    GenericParameter(GenericParamId),
53    Var(TypeVar),
54    Coupon(FunctionId),
55    FixedSizeArray {
56        type_id: TypeId,
57        size: ConstValueId,
58    },
59    ImplType(ImplTypeId),
60    Closure(ClosureTypeLongId),
61    Missing(#[dont_rewrite] DiagnosticAdded),
62}
63impl OptionFrom<TypeLongId> for ConcreteTypeId {
64    fn option_from(other: TypeLongId) -> Option<Self> {
65        try_extract_matches!(other, TypeLongId::Concrete)
66    }
67}
68
69define_short_id!(TypeId, TypeLongId, SemanticGroup, lookup_intern_type, intern_type);
70semantic_object_for_id!(TypeId, lookup_intern_type, intern_type, TypeLongId);
71impl TypeId {
72    pub fn missing(db: &dyn SemanticGroup, diag_added: DiagnosticAdded) -> Self {
73        TypeLongId::Missing(diag_added).intern(db)
74    }
75
76    pub fn format(&self, db: &dyn SemanticGroup) -> String {
77        self.lookup_intern(db).format(db)
78    }
79
80    /// Returns [Maybe::Err] if the type is [TypeLongId::Missing].
81    pub fn check_not_missing(&self, db: &dyn SemanticGroup) -> Maybe<()> {
82        if let TypeLongId::Missing(diag_added) = self.lookup_intern(db) {
83            Err(diag_added)
84        } else {
85            Ok(())
86        }
87    }
88
89    /// Returns `true` if the type is [TypeLongId::Missing].
90    pub fn is_missing(&self, db: &dyn SemanticGroup) -> bool {
91        self.check_not_missing(db).is_err()
92    }
93
94    /// Returns `true` if the type is `()`.
95    pub fn is_unit(&self, db: &dyn SemanticGroup) -> bool {
96        matches!(self.lookup_intern(db), TypeLongId::Tuple(types) if types.is_empty())
97    }
98
99    /// Returns the [TypeHead] for a type if available.
100    pub fn head(&self, db: &dyn SemanticGroup) -> Option<TypeHead> {
101        self.lookup_intern(db).head(db)
102    }
103
104    /// Returns true if the type does not depend on any generics.
105    pub fn is_fully_concrete(&self, db: &dyn SemanticGroup) -> bool {
106        db.priv_type_is_fully_concrete(*self)
107    }
108
109    /// Returns true if the type does not contain any inference variables.
110    pub fn is_var_free(&self, db: &dyn SemanticGroup) -> bool {
111        db.priv_type_is_var_free(*self)
112    }
113
114    /// Returns whether the type is phantom.
115    /// Type is considered phantom if it has the `#[phantom]` attribute, or is a tuple or fixed
116    /// sized array containing it.
117    pub fn is_phantom(&self, db: &dyn SemanticGroup) -> bool {
118        self.lookup_intern(db).is_phantom(db)
119    }
120
121    /// Short name of the type argument.
122    pub fn short_name(&self, db: &dyn SemanticGroup) -> String {
123        db.priv_type_short_name(*self)
124    }
125}
126impl TypeLongId {
127    pub fn format(&self, db: &dyn SemanticGroup) -> String {
128        format!("{:?}", self.debug(db.elongate()))
129    }
130
131    /// Returns the [TypeHead] for a type if available.
132    pub fn head(&self, db: &dyn SemanticGroup) -> Option<TypeHead> {
133        Some(match self {
134            TypeLongId::Concrete(concrete) => TypeHead::Concrete(concrete.generic_type(db)),
135            TypeLongId::Tuple(_) => TypeHead::Tuple,
136            TypeLongId::Snapshot(inner) => TypeHead::Snapshot(Box::new(inner.head(db)?)),
137            TypeLongId::Coupon(_) => TypeHead::Coupon,
138            TypeLongId::FixedSizeArray { .. } => TypeHead::FixedSizeArray,
139            TypeLongId::GenericParameter(_)
140            | TypeLongId::Var(_)
141            | TypeLongId::Missing(_)
142            | TypeLongId::ImplType(_)
143            | TypeLongId::Closure(_) => {
144                return None;
145            }
146        })
147    }
148
149    /// Returns whether the type is phantom.
150    /// Type is considered phantom if it has the `#[phantom]` attribute, (or an other attribute
151    /// declared by a plugin as defining a phantom type), or is a tuple or fixed sized array
152    /// containing it.
153    pub fn is_phantom(&self, db: &dyn SemanticGroup) -> bool {
154        match self {
155            TypeLongId::Concrete(id) => match id {
156                ConcreteTypeId::Struct(id) => {
157                    let crate_id = db.lookup_intern_struct(id.struct_id(db)).0.0.owning_crate(db);
158
159                    db.declared_phantom_type_attributes(crate_id)
160                        .iter()
161                        .any(|attr| id.has_attr(db, attr).unwrap_or_default())
162                }
163                ConcreteTypeId::Enum(id) => {
164                    let crate_id = db.lookup_intern_enum(id.enum_id(db)).0.0.owning_crate(db);
165
166                    db.declared_phantom_type_attributes(crate_id)
167                        .iter()
168                        .any(|attr| id.has_attr(db, attr).unwrap_or_default())
169                }
170                ConcreteTypeId::Extern(id) => {
171                    let crate_id =
172                        db.lookup_intern_extern_type(id.extern_type_id(db)).0.0.owning_crate(db);
173
174                    db.declared_phantom_type_attributes(crate_id)
175                        .iter()
176                        .any(|attr| id.has_attr(db, attr).unwrap_or_default())
177                }
178            },
179            TypeLongId::Tuple(inner) => inner.iter().any(|ty| ty.is_phantom(db)),
180            TypeLongId::FixedSizeArray { type_id, .. } => type_id.is_phantom(db),
181            TypeLongId::Snapshot(_)
182            | TypeLongId::GenericParameter(_)
183            | TypeLongId::Var(_)
184            | TypeLongId::Coupon(_)
185            | TypeLongId::ImplType(_)
186            | TypeLongId::Missing(_)
187            | TypeLongId::Closure(_) => false,
188        }
189    }
190
191    /// Returns the module id of the given type if applicable.
192    pub fn module_id(&self, db: &dyn SemanticGroup) -> Option<ModuleId> {
193        match self {
194            TypeLongId::Concrete(concrete) => Some(concrete.generic_type(db).module_file_id(db).0),
195            TypeLongId::Snapshot(ty) => {
196                let (_n_snapshots, inner_ty) = peel_snapshots(db, *ty);
197                inner_ty.module_id(db)
198            }
199            TypeLongId::GenericParameter(_) => None,
200            TypeLongId::Var(_) => None,
201            TypeLongId::Coupon(function_id) => function_id
202                .get_concrete(db)
203                .generic_function
204                .module_file_id(db)
205                .map(|module_file_id| module_file_id.0),
206            TypeLongId::Missing(_) => None,
207            TypeLongId::Tuple(_) => Some(core_submodule(db, "tuple")),
208            TypeLongId::ImplType(_) => None,
209            TypeLongId::FixedSizeArray { .. } => Some(core_submodule(db, "fixed_size_array")),
210            TypeLongId::Closure(closure) => {
211                if let Ok(function_id) = closure.parent_function {
212                    function_id
213                        .get_concrete(db)
214                        .generic_function
215                        .module_file_id(db)
216                        .map(|module_file_id| module_file_id.0)
217                } else {
218                    None
219                }
220            }
221        }
222    }
223}
224impl DebugWithDb<dyn SemanticGroup> for TypeLongId {
225    fn fmt(
226        &self,
227        f: &mut std::fmt::Formatter<'_>,
228        db: &(dyn SemanticGroup + 'static),
229    ) -> std::fmt::Result {
230        match self {
231            TypeLongId::Concrete(concrete) => write!(f, "{}", concrete.format(db)),
232            TypeLongId::Tuple(inner_types) => {
233                if inner_types.len() == 1 {
234                    write!(f, "({},)", inner_types[0].format(db))
235                } else {
236                    write!(f, "({})", inner_types.iter().map(|ty| ty.format(db)).join(", "))
237                }
238            }
239            TypeLongId::Snapshot(ty) => write!(f, "@{}", ty.format(db)),
240            TypeLongId::GenericParameter(generic_param) => {
241                write!(f, "{}", generic_param.name(db).unwrap_or_else(|| "_".into()))
242            }
243            TypeLongId::ImplType(impl_type_id) => {
244                write!(f, "{:?}::{}", impl_type_id.impl_id.debug(db), impl_type_id.ty.name(db))
245            }
246            TypeLongId::Var(var) => write!(f, "?{}", var.id.0),
247            TypeLongId::Coupon(function_id) => write!(f, "{}::Coupon", function_id.full_path(db)),
248            TypeLongId::Missing(_) => write!(f, "<missing>"),
249            TypeLongId::FixedSizeArray { type_id, size } => {
250                write!(f, "[{}; {:?}]", type_id.format(db), size.debug(db.elongate()))
251            }
252            TypeLongId::Closure(closure) => {
253                write!(f, "{:?}", closure.debug(db.elongate()))
254            }
255        }
256    }
257}
258
259/// Head of a type.
260///
261/// A type that is not one of {generic param, type variable, impl type} has a head, which represents
262/// the kind of the root node in its type tree. This is used for caching queries for fast lookups
263/// when the type is not completely inferred yet.
264#[derive(Clone, Debug, Hash, PartialEq, Eq)]
265pub enum TypeHead {
266    Concrete(GenericTypeId),
267    Snapshot(Box<TypeHead>),
268    Tuple,
269    Coupon,
270    FixedSizeArray,
271}
272
273#[derive(Clone, Debug, Hash, PartialEq, Eq, SemanticObject)]
274pub enum ConcreteTypeId {
275    Struct(ConcreteStructId),
276    Enum(ConcreteEnumId),
277    Extern(ConcreteExternTypeId),
278}
279impl ConcreteTypeId {
280    pub fn new(
281        db: &dyn SemanticGroup,
282        generic_ty: GenericTypeId,
283        generic_args: Vec<semantic::GenericArgumentId>,
284    ) -> Self {
285        match generic_ty {
286            GenericTypeId::Struct(id) => ConcreteTypeId::Struct(
287                ConcreteStructLongId { struct_id: id, generic_args }.intern(db),
288            ),
289            GenericTypeId::Enum(id) => {
290                ConcreteTypeId::Enum(ConcreteEnumLongId { enum_id: id, generic_args }.intern(db))
291            }
292            GenericTypeId::Extern(id) => ConcreteTypeId::Extern(
293                ConcreteExternTypeLongId { extern_type_id: id, generic_args }.intern(db),
294            ),
295        }
296    }
297    pub fn generic_type(&self, db: &dyn SemanticGroup) -> GenericTypeId {
298        match self {
299            ConcreteTypeId::Struct(id) => GenericTypeId::Struct(id.lookup_intern(db).struct_id),
300            ConcreteTypeId::Enum(id) => GenericTypeId::Enum(id.lookup_intern(db).enum_id),
301            ConcreteTypeId::Extern(id) => {
302                GenericTypeId::Extern(id.lookup_intern(db).extern_type_id)
303            }
304        }
305    }
306    pub fn generic_args(&self, db: &dyn SemanticGroup) -> Vec<semantic::GenericArgumentId> {
307        match self {
308            ConcreteTypeId::Struct(id) => id.lookup_intern(db).generic_args,
309            ConcreteTypeId::Enum(id) => id.lookup_intern(db).generic_args,
310            ConcreteTypeId::Extern(id) => id.lookup_intern(db).generic_args,
311        }
312    }
313    pub fn format(&self, db: &dyn SemanticGroup) -> String {
314        format!("{:?}", self.debug(db.elongate()))
315    }
316
317    /// Returns whether the type has the `#[must_use]` attribute.
318    pub fn is_must_use(&self, db: &dyn SemanticGroup) -> Maybe<bool> {
319        match self {
320            ConcreteTypeId::Struct(id) => id.has_attr(db, MUST_USE_ATTR),
321            ConcreteTypeId::Enum(id) => id.has_attr(db, MUST_USE_ATTR),
322            ConcreteTypeId::Extern(id) => id.has_attr(db, MUST_USE_ATTR),
323        }
324    }
325    /// Returns true if the type does not depend on any generics.
326    pub fn is_fully_concrete(&self, db: &dyn SemanticGroup) -> bool {
327        self.generic_args(db)
328            .iter()
329            .all(|generic_argument_id| generic_argument_id.is_fully_concrete(db))
330    }
331    /// Returns true if the type does not contain any inference variables.
332    pub fn is_var_free(&self, db: &dyn SemanticGroup) -> bool {
333        self.generic_args(db).iter().all(|generic_argument_id| generic_argument_id.is_var_free(db))
334    }
335}
336impl DebugWithDb<dyn SemanticGroup> for ConcreteTypeId {
337    fn fmt(
338        &self,
339        f: &mut std::fmt::Formatter<'_>,
340        db: &(dyn SemanticGroup + 'static),
341    ) -> std::fmt::Result {
342        let f = &mut CountingWriter::new(f);
343        write!(f, "{}", self.generic_type(db).format(db))?;
344        fmt_generic_args(&self.generic_args(db), f, db)
345    }
346}
347
348#[derive(Clone, Debug, Hash, PartialEq, Eq, SemanticObject)]
349pub struct ConcreteStructLongId {
350    pub struct_id: StructId,
351    pub generic_args: Vec<semantic::GenericArgumentId>,
352}
353define_short_id!(
354    ConcreteStructId,
355    ConcreteStructLongId,
356    SemanticGroup,
357    lookup_intern_concrete_struct,
358    intern_concrete_struct
359);
360semantic_object_for_id!(
361    ConcreteStructId,
362    lookup_intern_concrete_struct,
363    intern_concrete_struct,
364    ConcreteStructLongId
365);
366impl ConcreteStructId {
367    pub fn struct_id(&self, db: &dyn SemanticGroup) -> StructId {
368        self.lookup_intern(db).struct_id
369    }
370}
371impl DebugWithDb<dyn SemanticGroup> for ConcreteStructLongId {
372    fn fmt(
373        &self,
374        f: &mut std::fmt::Formatter<'_>,
375        db: &(dyn SemanticGroup + 'static),
376    ) -> std::fmt::Result {
377        write!(f, "{:?}", ConcreteTypeId::Struct(self.clone().intern(db)).debug(db))
378    }
379}
380
381#[derive(Clone, Debug, Hash, PartialEq, Eq, SemanticObject)]
382pub struct ConcreteEnumLongId {
383    pub enum_id: EnumId,
384    pub generic_args: Vec<semantic::GenericArgumentId>,
385}
386impl DebugWithDb<dyn SemanticGroup> for ConcreteEnumLongId {
387    fn fmt(
388        &self,
389        f: &mut std::fmt::Formatter<'_>,
390        db: &(dyn SemanticGroup + 'static),
391    ) -> std::fmt::Result {
392        write!(f, "{:?}", ConcreteTypeId::Enum(self.clone().intern(db)).debug(db))
393    }
394}
395
396define_short_id!(
397    ConcreteEnumId,
398    ConcreteEnumLongId,
399    SemanticGroup,
400    lookup_intern_concrete_enum,
401    intern_concrete_enum
402);
403semantic_object_for_id!(
404    ConcreteEnumId,
405    lookup_intern_concrete_enum,
406    intern_concrete_enum,
407    ConcreteEnumLongId
408);
409impl ConcreteEnumId {
410    pub fn enum_id(&self, db: &dyn SemanticGroup) -> EnumId {
411        self.lookup_intern(db).enum_id
412    }
413}
414
415#[derive(Clone, Debug, Hash, PartialEq, Eq, SemanticObject)]
416pub struct ConcreteExternTypeLongId {
417    pub extern_type_id: ExternTypeId,
418    pub generic_args: Vec<semantic::GenericArgumentId>,
419}
420define_short_id!(
421    ConcreteExternTypeId,
422    ConcreteExternTypeLongId,
423    SemanticGroup,
424    lookup_intern_concrete_extern_type,
425    intern_concrete_extern_type
426);
427semantic_object_for_id!(
428    ConcreteExternTypeId,
429    lookup_intern_concrete_extern_type,
430    intern_concrete_extern_type,
431    ConcreteExternTypeLongId
432);
433impl ConcreteExternTypeId {
434    pub fn extern_type_id(&self, db: &dyn SemanticGroup) -> ExternTypeId {
435        self.lookup_intern(db).extern_type_id
436    }
437}
438
439/// A type id of a closure function.
440#[derive(Clone, Debug, Hash, PartialEq, Eq, SemanticObject)]
441pub struct ClosureTypeLongId {
442    pub param_tys: Vec<TypeId>,
443    pub ret_ty: TypeId,
444    /// The set of types captured by the closure, this field is used to determined if the
445    /// closure has Drop, Destruct or PanicDestruct.
446    /// A vector as the fields needs to be hashable.
447    pub captured_types: Vec<TypeId>,
448    /// The parent function of the closure or an error.
449    pub parent_function: Maybe<FunctionId>,
450    /// Every closure has a unique type that is based on the stable location of its wrapper.
451    #[dont_rewrite]
452    pub wrapper_location: StableLocation,
453}
454
455impl DebugWithDb<dyn SemanticGroup> for ClosureTypeLongId {
456    fn fmt(
457        &self,
458        f: &mut std::fmt::Formatter<'_>,
459        db: &(dyn SemanticGroup + 'static),
460    ) -> std::fmt::Result {
461        write!(f, "{{closure@{:?}}}", self.wrapper_location.debug(db))
462    }
463}
464
465/// An impl item of kind type.
466#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, SemanticObject)]
467pub struct ImplTypeId {
468    /// The impl the item type is in.
469    impl_id: ImplId,
470    /// The trait type this impl type "implements".
471    ty: TraitTypeId,
472}
473impl ImplTypeId {
474    /// Creates a new impl type id. For an impl type of a concrete impl, asserts that the trait
475    /// type belongs to the same trait that the impl implements (panics if not).
476    pub fn new(impl_id: ImplId, ty: TraitTypeId, db: &dyn SemanticGroup) -> Self {
477        if let crate::items::imp::ImplLongId::Concrete(concrete_impl) = impl_id.lookup_intern(db) {
478            let impl_def_id = concrete_impl.impl_def_id(db);
479            assert_eq!(Ok(ty.trait_id(db)), db.impl_def_trait(impl_def_id));
480        }
481
482        ImplTypeId { impl_id, ty }
483    }
484    pub fn impl_id(&self) -> ImplId {
485        self.impl_id
486    }
487    pub fn ty(&self) -> TraitTypeId {
488        self.ty
489    }
490    pub fn format(&self, db: &dyn SemanticGroup) -> SmolStr {
491        format!("{}::{}", self.impl_id.name(db), self.ty.name(db)).into()
492    }
493}
494impl DebugWithDb<dyn SemanticGroup> for ImplTypeId {
495    fn fmt(
496        &self,
497        f: &mut std::fmt::Formatter<'_>,
498        db: &(dyn SemanticGroup + 'static),
499    ) -> std::fmt::Result {
500        write!(f, "{}", self.format(db))
501    }
502}
503
504/// A wrapper around ImplTypeById that implements Ord for saving in an ordered collection.
505#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
506pub struct ImplTypeById(ImplTypeId);
507
508impl From<ImplTypeId> for ImplTypeById {
509    fn from(impl_type_id: ImplTypeId) -> Self {
510        Self(impl_type_id)
511    }
512}
513impl Ord for ImplTypeById {
514    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
515        self.0
516            .impl_id
517            .get_internal_id()
518            .cmp(other.0.impl_id.get_internal_id())
519            .then_with(|| self.0.ty.get_internal_id().cmp(other.0.ty.get_internal_id()))
520    }
521}
522impl PartialOrd for ImplTypeById {
523    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
524        Some(self.cmp(other))
525    }
526}
527
528// TODO(spapini): add a query wrapper.
529/// Resolves a type given a module and a path. Used for resolving from non-statement context.
530pub fn resolve_type(
531    db: &dyn SemanticGroup,
532    diagnostics: &mut SemanticDiagnostics,
533    resolver: &mut Resolver<'_>,
534    ty_syntax: &ast::Expr,
535) -> TypeId {
536    resolve_type_ex(db, diagnostics, resolver, ty_syntax, ResolutionContext::Default)
537}
538/// Resolves a type given a module and a path. Allows defining a resolution context.
539pub fn resolve_type_ex(
540    db: &dyn SemanticGroup,
541    diagnostics: &mut SemanticDiagnostics,
542    resolver: &mut Resolver<'_>,
543    ty_syntax: &ast::Expr,
544    ctx: ResolutionContext<'_>,
545) -> TypeId {
546    maybe_resolve_type(db, diagnostics, resolver, ty_syntax, ctx)
547        .unwrap_or_else(|diag_added| TypeId::missing(db, diag_added))
548}
549fn maybe_resolve_type(
550    db: &dyn SemanticGroup,
551    diagnostics: &mut SemanticDiagnostics,
552    resolver: &mut Resolver<'_>,
553    ty_syntax: &ast::Expr,
554    mut ctx: ResolutionContext<'_>,
555) -> Maybe<TypeId> {
556    Ok(match ty_syntax {
557        ast::Expr::Path(path) => {
558            match resolver.resolve_concrete_path_ex(
559                diagnostics,
560                path,
561                NotFoundItemType::Type,
562                ctx,
563            )? {
564                ResolvedConcreteItem::Type(ty) => ty,
565                _ => {
566                    return Err(diagnostics.report(path.stable_ptr(db), NotAType));
567                }
568            }
569        }
570        ast::Expr::Parenthesized(expr_syntax) => {
571            resolve_type_ex(db, diagnostics, resolver, &expr_syntax.expr(db), ctx)
572        }
573        ast::Expr::Tuple(tuple_syntax) => {
574            let sub_tys = tuple_syntax
575                .expressions(db)
576                .elements(db)
577                .map(|subexpr_syntax| {
578                    resolve_type_ex(
579                        db,
580                        diagnostics,
581                        resolver,
582                        &subexpr_syntax,
583                        match ctx {
584                            ResolutionContext::Default => ResolutionContext::Default,
585                            ResolutionContext::ModuleItem(id) => ResolutionContext::ModuleItem(id),
586                            ResolutionContext::Statement(ref mut env) => {
587                                ResolutionContext::Statement(env)
588                            }
589                        },
590                    )
591                })
592                .collect();
593            TypeLongId::Tuple(sub_tys).intern(db)
594        }
595        ast::Expr::Unary(unary_syntax)
596            if matches!(unary_syntax.op(db), ast::UnaryOperator::At(_)) =>
597        {
598            let ty = resolve_type_ex(db, diagnostics, resolver, &unary_syntax.expr(db), ctx);
599            TypeLongId::Snapshot(ty).intern(db)
600        }
601        ast::Expr::Unary(unary_syntax)
602            if matches!(unary_syntax.op(db), ast::UnaryOperator::Desnap(_)) =>
603        {
604            let ty = resolve_type_ex(db, diagnostics, resolver, &unary_syntax.expr(db), ctx);
605            if let Some(desnapped_ty) =
606                try_extract_matches!(ty.lookup_intern(db), TypeLongId::Snapshot)
607            {
608                desnapped_ty
609            } else {
610                return Err(diagnostics.report(ty_syntax.stable_ptr(db), DesnapNonSnapshot));
611            }
612        }
613        ast::Expr::FixedSizeArray(array_syntax) => {
614            let Some([ty]) = &array_syntax.exprs(db).elements(db).collect_array() else {
615                return Err(
616                    diagnostics.report(ty_syntax.stable_ptr(db), FixedSizeArrayTypeNonSingleType)
617                );
618            };
619            let ty = resolve_type_ex(db, diagnostics, resolver, ty, ctx);
620            let size =
621                match extract_fixed_size_array_size(db, diagnostics, array_syntax, resolver)? {
622                    Some(size) => size,
623                    None => {
624                        return Err(diagnostics
625                            .report(ty_syntax.stable_ptr(db), FixedSizeArrayTypeEmptySize));
626                    }
627                };
628            TypeLongId::FixedSizeArray { type_id: ty, size }.intern(db)
629        }
630        _ => {
631            return Err(diagnostics.report(ty_syntax.stable_ptr(db), UnknownType));
632        }
633    })
634}
635
636/// Extracts the size of a fixed size array, or none if the size is missing. Reports an error if the
637/// size is not a numeric literal.
638pub fn extract_fixed_size_array_size(
639    db: &dyn SemanticGroup,
640    diagnostics: &mut SemanticDiagnostics,
641    syntax: &ast::ExprFixedSizeArray,
642    resolver: &Resolver<'_>,
643) -> Maybe<Option<ConstValueId>> {
644    match syntax.size(db) {
645        ast::OptionFixedSizeArraySize::FixedSizeArraySize(size_clause) => {
646            let environment = Environment::empty();
647            let resolver = Resolver::with_data(
648                db,
649                (resolver.data).clone_with_inference_id(db, resolver.inference_data.inference_id),
650            );
651            let mut ctx = ComputationContext::new(
652                db,
653                diagnostics,
654                resolver,
655                None,
656                environment,
657                ContextFunction::Global,
658            );
659            let size_expr_syntax = size_clause.size(db);
660            let size = compute_expr_semantic(&mut ctx, &size_expr_syntax);
661            let const_value = resolve_const_expr_and_evaluate(
662                db,
663                &mut ctx,
664                &size,
665                size_expr_syntax.stable_ptr(db).untyped(),
666                get_usize_ty(db),
667                false,
668            );
669            if matches!(const_value, ConstValue::Int(_, _) | ConstValue::Generic(_)) {
670                Ok(Some(const_value.intern(db)))
671            } else {
672                Err(diagnostics.report(syntax.stable_ptr(db), FixedSizeArrayNonNumericSize))
673            }
674        }
675        ast::OptionFixedSizeArraySize::Empty(_) => Ok(None),
676    }
677}
678
679/// Verifies that a given fixed size array size is within limits, and adds a diagnostic if not.
680pub fn verify_fixed_size_array_size(
681    db: &dyn SyntaxGroup,
682    diagnostics: &mut SemanticDiagnostics,
683    size: &BigInt,
684    syntax: &ast::ExprFixedSizeArray,
685) -> Maybe<()> {
686    if size > &BigInt::from(i16::MAX) {
687        return Err(diagnostics.report(syntax.stable_ptr(db), FixedSizeArraySizeTooBig));
688    }
689    Ok(())
690}
691
692/// Query implementation of [crate::db::SemanticGroup::generic_type_generic_params].
693pub fn generic_type_generic_params(
694    db: &dyn SemanticGroup,
695    generic_type: GenericTypeId,
696) -> Maybe<Vec<semantic::GenericParam>> {
697    match generic_type {
698        GenericTypeId::Struct(id) => db.struct_generic_params(id),
699        GenericTypeId::Enum(id) => db.enum_generic_params(id),
700        GenericTypeId::Extern(id) => db.extern_type_declaration_generic_params(id),
701    }
702}
703
704#[derive(Clone, Debug, PartialEq, Eq)]
705pub struct TypeInfo {
706    pub droppable: Result<ImplId, InferenceError>,
707    pub copyable: Result<ImplId, InferenceError>,
708    pub destruct_impl: Result<ImplId, InferenceError>,
709    pub panic_destruct_impl: Result<ImplId, InferenceError>,
710}
711
712/// Checks if there is at least one impl that can be inferred for a specific concrete trait.
713pub fn get_impl_at_context(
714    db: &dyn SemanticGroup,
715    lookup_context: ImplLookupContext,
716    concrete_trait_id: ConcreteTraitId,
717    stable_ptr: Option<SyntaxStablePtrId>,
718) -> Result<ImplId, InferenceError> {
719    let constrains = db.generic_params_type_constraints(lookup_context.generic_params.clone());
720    if constrains.is_empty() && concrete_trait_id.is_var_free(db) {
721        return solve_concrete_trait_no_constraints(db, lookup_context, concrete_trait_id);
722    }
723    let mut inference_data = InferenceData::new(InferenceId::NoContext);
724    let mut inference = inference_data.inference(db);
725    inference.conform_generic_params_type_constraints(&constrains);
726    // It's ok to consume the errors without reporting as this is a helper function meant to find an
727    // impl and return it, but it's ok if the impl can't be found.
728    let impl_id = inference.new_impl_var(concrete_trait_id, stable_ptr, lookup_context);
729    if let Err((err_set, _)) = inference.finalize_without_reporting() {
730        return Err(inference
731            .consume_error_without_reporting(err_set)
732            .expect("Error couldn't be already consumed"));
733    };
734    Ok(inference.rewrite(impl_id).no_err())
735}
736
737/// Query implementation of [crate::db::SemanticGroup::single_value_type].
738pub fn single_value_type(db: &dyn SemanticGroup, ty: TypeId) -> Maybe<bool> {
739    Ok(match ty.lookup_intern(db) {
740        TypeLongId::Concrete(concrete_type_id) => match concrete_type_id {
741            ConcreteTypeId::Struct(id) => {
742                for member in db.struct_members(id.struct_id(db))?.values() {
743                    if !db.single_value_type(member.ty)? {
744                        return Ok(false);
745                    }
746                }
747                true
748            }
749            ConcreteTypeId::Enum(id) => {
750                let variants = db.enum_variants(id.enum_id(db))?;
751                if variants.len() != 1 {
752                    return Ok(false);
753                }
754
755                db.single_value_type(
756                    db.variant_semantic(id.enum_id(db), *variants.values().next().unwrap())?.ty,
757                )?
758            }
759            ConcreteTypeId::Extern(_) => false,
760        },
761        TypeLongId::Tuple(types) => {
762            for ty in &types {
763                if !db.single_value_type(*ty)? {
764                    return Ok(false);
765                }
766            }
767            true
768        }
769        TypeLongId::Snapshot(ty) => db.single_value_type(ty)?,
770        TypeLongId::GenericParameter(_)
771        | TypeLongId::Var(_)
772        | TypeLongId::Missing(_)
773        | TypeLongId::Coupon(_)
774        | TypeLongId::ImplType(_)
775        | TypeLongId::Closure(_) => false,
776        TypeLongId::FixedSizeArray { type_id, size } => {
777            db.single_value_type(type_id)?
778                || matches!(size.lookup_intern(db),
779                            ConstValue::Int(value, _) if value.is_zero())
780        }
781    })
782}
783
784/// Adds diagnostics for a type, post semantic analysis of types.
785pub fn add_type_based_diagnostics(
786    db: &dyn SemanticGroup,
787    diagnostics: &mut SemanticDiagnostics,
788    ty: TypeId,
789    stable_ptr: impl Into<SyntaxStablePtrId> + Copy,
790) {
791    if db.type_size_info(ty) == Ok(TypeSizeInformation::Infinite) {
792        diagnostics.report(stable_ptr, InfiniteSizeType(ty));
793    }
794    if let TypeLongId::Concrete(ConcreteTypeId::Extern(extrn)) = ty.lookup_intern(db) {
795        let long_id = extrn.lookup_intern(db);
796        if long_id.extern_type_id.name(db).as_str() == "Array" {
797            if let [GenericArgumentId::Type(arg_ty)] = &long_id.generic_args[..] {
798                if db.type_size_info(*arg_ty) == Ok(TypeSizeInformation::ZeroSized) {
799                    diagnostics.report(stable_ptr, ArrayOfZeroSizedElements(*arg_ty));
800                }
801            }
802        }
803    }
804}
805
806#[derive(Clone, Debug, PartialEq, Eq)]
807pub enum TypeSizeInformation {
808    /// The type has an infinite size - caused by a recursion in it.
809    /// If the type simply holds an infinite type, it would be considered `Other`, for diagnostics
810    /// reasons.
811    Infinite,
812    /// The type is zero size.
813    ZeroSized,
814    /// The typed has some none zero size.
815    Other,
816}
817
818/// Query implementation of [crate::db::SemanticGroup::type_size_info].
819pub fn type_size_info(db: &dyn SemanticGroup, ty: TypeId) -> Maybe<TypeSizeInformation> {
820    match ty.lookup_intern(db) {
821        TypeLongId::Concrete(concrete_type_id) => match concrete_type_id {
822            ConcreteTypeId::Struct(id) => {
823                if check_all_type_are_zero_sized(
824                    db,
825                    db.concrete_struct_members(id)?.iter().map(|(_, member)| &member.ty),
826                )? {
827                    return Ok(TypeSizeInformation::ZeroSized);
828                }
829            }
830            ConcreteTypeId::Enum(id) => {
831                for variant in &db.concrete_enum_variants(id)? {
832                    // Recursive calling in order to find infinite sized types.
833                    db.type_size_info(variant.ty)?;
834                }
835            }
836            ConcreteTypeId::Extern(_) => {}
837        },
838        TypeLongId::Tuple(types) => {
839            if check_all_type_are_zero_sized(db, types.iter())? {
840                return Ok(TypeSizeInformation::ZeroSized);
841            }
842        }
843        TypeLongId::Snapshot(ty) => {
844            if db.type_size_info(ty)? == TypeSizeInformation::ZeroSized {
845                return Ok(TypeSizeInformation::ZeroSized);
846            }
847        }
848        TypeLongId::Closure(closure_ty) => {
849            if check_all_type_are_zero_sized(db, closure_ty.captured_types.iter())? {
850                return Ok(TypeSizeInformation::ZeroSized);
851            }
852        }
853        TypeLongId::Coupon(_) => return Ok(TypeSizeInformation::ZeroSized),
854        TypeLongId::GenericParameter(_)
855        | TypeLongId::Var(_)
856        | TypeLongId::Missing(_)
857        | TypeLongId::ImplType(_) => {}
858        TypeLongId::FixedSizeArray { type_id, size } => {
859            if matches!(size.lookup_intern(db), ConstValue::Int(value,_) if value.is_zero())
860                || db.type_size_info(type_id)? == TypeSizeInformation::ZeroSized
861            {
862                return Ok(TypeSizeInformation::ZeroSized);
863            }
864        }
865    }
866    Ok(TypeSizeInformation::Other)
867}
868
869/// Checks if all types in the iterator are zero sized.
870fn check_all_type_are_zero_sized<'a>(
871    db: &dyn SemanticGroup,
872    types: impl Iterator<Item = &'a TypeId>,
873) -> Maybe<bool> {
874    let mut zero_sized = true;
875    for ty in types {
876        if db.type_size_info(*ty)? != TypeSizeInformation::ZeroSized {
877            zero_sized = false;
878        }
879    }
880    Ok(zero_sized)
881}
882
883/// Cycle handling of [crate::db::SemanticGroup::type_size_info].
884pub fn type_size_info_cycle(
885    _db: &dyn SemanticGroup,
886    _cycle: &salsa::Cycle,
887    _ty: &TypeId,
888) -> Maybe<TypeSizeInformation> {
889    Ok(TypeSizeInformation::Infinite)
890}
891
892// TODO(spapini): type info lookup for non generic types needs to not depend on lookup_context.
893// This is to ensure that sierra generator will see a consistent type info of types.
894/// Query implementation of [crate::db::SemanticGroup::type_info].
895pub fn type_info(
896    db: &dyn SemanticGroup,
897    lookup_context: ImplLookupContext,
898    ty: TypeId,
899) -> TypeInfo {
900    // Dummy stable pointer for type inference variables, since inference is disabled.
901    let droppable =
902        get_impl_at_context(db, lookup_context.clone(), concrete_drop_trait(db, ty), None);
903    let copyable =
904        get_impl_at_context(db, lookup_context.clone(), concrete_copy_trait(db, ty), None);
905    let destruct_impl =
906        get_impl_at_context(db, lookup_context.clone(), concrete_destruct_trait(db, ty), None);
907    let panic_destruct_impl =
908        get_impl_at_context(db, lookup_context, concrete_panic_destruct_trait(db, ty), None);
909    TypeInfo { droppable, copyable, destruct_impl, panic_destruct_impl }
910}
911
912/// Solves a concrete trait without any constraints.
913/// Only works when the given trait is var free.
914fn solve_concrete_trait_no_constraints(
915    db: &dyn SemanticGroup,
916    mut lookup_context: ImplLookupContext,
917    id: ConcreteTraitId,
918) -> Result<ImplId, InferenceError> {
919    enrich_lookup_context(db, id, &mut lookup_context);
920    match db.canonic_trait_solutions(
921        CanonicalTrait { id, mappings: Default::default() },
922        lookup_context,
923        Default::default(),
924    )? {
925        SolutionSet::None => Err(InferenceError::NoImplsFound(id)),
926        SolutionSet::Unique(solution) => Ok(solution.0),
927        SolutionSet::Ambiguous(ambiguity) => Err(InferenceError::Ambiguity(ambiguity)),
928    }
929}
930
931/// Query implementation of [crate::db::SemanticGroup::copyable].
932pub fn copyable(db: &dyn SemanticGroup, ty: TypeId) -> Result<ImplId, InferenceError> {
933    solve_concrete_trait_no_constraints(db, Default::default(), concrete_copy_trait(db, ty))
934}
935
936/// Query implementation of [crate::db::SemanticGroup::droppable].
937pub fn droppable(db: &dyn SemanticGroup, ty: TypeId) -> Result<ImplId, InferenceError> {
938    solve_concrete_trait_no_constraints(db, Default::default(), concrete_drop_trait(db, ty))
939}
940
941pub fn priv_type_is_fully_concrete(db: &dyn SemanticGroup, ty: TypeId) -> bool {
942    match ty.lookup_intern(db) {
943        TypeLongId::Concrete(concrete_type_id) => concrete_type_id.is_fully_concrete(db),
944        TypeLongId::Tuple(types) => types.iter().all(|ty| ty.is_fully_concrete(db)),
945        TypeLongId::Snapshot(ty) => ty.is_fully_concrete(db),
946        TypeLongId::GenericParameter(_)
947        | TypeLongId::Var(_)
948        | TypeLongId::Missing(_)
949        | TypeLongId::ImplType(_) => false,
950        TypeLongId::Coupon(function_id) => function_id.is_fully_concrete(db),
951        TypeLongId::FixedSizeArray { type_id, size } => {
952            type_id.is_fully_concrete(db) && size.is_fully_concrete(db)
953        }
954        TypeLongId::Closure(closure) => {
955            closure.parent_function.map(|id| id.is_fully_concrete(db)).unwrap_or(true)
956                && closure.param_tys.iter().all(|param| param.is_fully_concrete(db))
957                && closure.ret_ty.is_fully_concrete(db)
958        }
959    }
960}
961
962pub fn priv_type_is_var_free(db: &dyn SemanticGroup, ty: TypeId) -> bool {
963    match ty.lookup_intern(db) {
964        TypeLongId::Concrete(concrete_type_id) => concrete_type_id.is_var_free(db),
965        TypeLongId::Tuple(types) => types.iter().all(|ty| ty.is_var_free(db)),
966        TypeLongId::Snapshot(ty) => ty.is_var_free(db),
967        TypeLongId::Var(_) => false,
968        TypeLongId::GenericParameter(_) | TypeLongId::Missing(_) => true,
969        TypeLongId::Coupon(function_id) => function_id.is_var_free(db),
970        TypeLongId::FixedSizeArray { type_id, size } => {
971            type_id.is_var_free(db) && size.is_var_free(db)
972        }
973        // TODO(TomerStarkware): consider rename the function to `priv_type_might_need_rewrite`.
974        // a var free ImplType needs to be rewritten if has impl bounds constraints.
975        TypeLongId::ImplType(_) => false,
976        TypeLongId::Closure(closure) => {
977            chain!(&closure.captured_types, &closure.param_tys).all(|param| param.is_var_free(db))
978                && closure.ret_ty.is_var_free(db)
979        }
980    }
981}
982
983pub fn priv_type_short_name(db: &dyn SemanticGroup, ty: TypeId) -> String {
984    match ty.lookup_intern(db) {
985        TypeLongId::Concrete(concrete_type_id) => {
986            let mut result = concrete_type_id.generic_type(db).format(db);
987            let mut generic_args = concrete_type_id.generic_args(db).into_iter().peekable();
988            if generic_args.peek().is_some() {
989                result.push_str("::<h0x");
990                let mut hasher = Keccak256::new();
991                for arg in generic_args {
992                    hasher.update(arg.short_name(db).as_bytes());
993                }
994                for c in hasher.finalize() {
995                    result.push_str(&format!("{c:x}"));
996                }
997                result.push('>');
998            }
999            result
1000        }
1001        TypeLongId::Tuple(types) => {
1002            let mut result = String::from("(h0x");
1003            let mut hasher = Keccak256::new();
1004            for ty in types {
1005                hasher.update(ty.short_name(db).as_bytes());
1006            }
1007            for c in hasher.finalize() {
1008                result.push_str(&format!("{c:x}"));
1009            }
1010            result.push(')');
1011            result
1012        }
1013        TypeLongId::Snapshot(ty) => {
1014            format!("@{}", ty.short_name(db))
1015        }
1016        TypeLongId::FixedSizeArray { type_id, size } => {
1017            format!("[{}; {:?}", type_id.short_name(db), size.debug(db.elongate()))
1018        }
1019        other => other.format(db),
1020    }
1021}
1022
1023/// Peels all wrapping Snapshot (`@`) from the type.
1024/// Returns the number of peeled snapshots and the inner type.
1025pub fn peel_snapshots(db: &dyn SemanticGroup, ty: TypeId) -> (usize, TypeLongId) {
1026    peel_snapshots_ex(db, ty.lookup_intern(db))
1027}
1028
1029/// Same as `peel_snapshots`, but takes a `TypeLongId` instead of a `TypeId`.
1030pub fn peel_snapshots_ex(db: &dyn SemanticGroup, mut long_ty: TypeLongId) -> (usize, TypeLongId) {
1031    let mut n_snapshots = 0;
1032    while let TypeLongId::Snapshot(ty) = long_ty {
1033        long_ty = ty.lookup_intern(db);
1034        n_snapshots += 1;
1035    }
1036    (n_snapshots, long_ty)
1037}
1038
1039/// Wraps a type with Snapshot (`@`) `n_snapshots` times.
1040pub fn wrap_in_snapshots(db: &dyn SemanticGroup, mut ty: TypeId, n_snapshots: usize) -> TypeId {
1041    for _ in 0..n_snapshots {
1042        ty = TypeLongId::Snapshot(ty).intern(db);
1043    }
1044    ty
1045}
1046
1047/// Returns `true` if coupons are enabled in the module.
1048pub(crate) fn are_coupons_enabled(db: &dyn SemanticGroup, module_file_id: ModuleFileId) -> bool {
1049    let owning_crate = module_file_id.0.owning_crate(db);
1050    let Some(config) = db.crate_config(owning_crate) else { return false };
1051    config.settings.experimental_features.coupons
1052}
cairo_lang_semantic/types.rs

cairo_lang_semantic/
types.rs
