cairo_lang_semantic/expr/inference/
conform.rs

1use std::hash::Hash;
2
3use cairo_lang_defs::ids::{TraitConstantId, TraitTypeId};
4use cairo_lang_diagnostics::Maybe;
5use cairo_lang_syntax::node::ids::SyntaxStablePtrId;
6use cairo_lang_utils::ordered_hash_map::{Entry, OrderedHashMap};
7use cairo_lang_utils::{Intern, LookupIntern};
8use itertools::zip_eq;
9
10use super::canonic::{NoError, ResultNoErrEx};
11use super::{
12    ErrorSet, ImplVarId, ImplVarTraitItemMappings, Inference, InferenceError, InferenceResult,
13    InferenceVar, LocalTypeVarId, TypeVar,
14};
15use crate::corelib::never_ty;
16use crate::diagnostic::{SemanticDiagnosticKind, SemanticDiagnostics, SemanticDiagnosticsBuilder};
17use crate::items::constant::{ConstValue, ConstValueId, ImplConstantId};
18use crate::items::functions::{GenericFunctionId, ImplGenericFunctionId};
19use crate::items::imp::{ImplId, ImplImplId, ImplLongId, ImplLookupContext};
20use crate::items::trt::ConcreteTraitImplId;
21use crate::substitution::SemanticRewriter;
22use crate::types::{ClosureTypeLongId, ImplTypeId, peel_snapshots};
23use crate::{
24    ConcreteFunction, ConcreteImplLongId, ConcreteTraitId, ConcreteTraitLongId, ConcreteTypeId,
25    FunctionId, FunctionLongId, GenericArgumentId, TypeId, TypeLongId,
26};
27
28/// Functions for conforming semantic objects with each other.
29pub trait InferenceConform {
30    fn conform_ty(&mut self, ty0: TypeId, ty1: TypeId) -> InferenceResult<TypeId>;
31    fn conform_ty_ex(
32        &mut self,
33        ty0: TypeId,
34        ty1: TypeId,
35        ty0_is_self: bool,
36    ) -> InferenceResult<(TypeId, usize)>;
37    fn conform_const(
38        &mut self,
39        ty0: ConstValueId,
40        ty1: ConstValueId,
41    ) -> InferenceResult<ConstValueId>;
42    fn maybe_peel_snapshots(&mut self, ty0_is_self: bool, ty1: TypeId) -> (usize, TypeLongId);
43    fn conform_generic_args(
44        &mut self,
45        gargs0: &[GenericArgumentId],
46        gargs1: &[GenericArgumentId],
47    ) -> InferenceResult<Vec<GenericArgumentId>>;
48    fn conform_generic_arg(
49        &mut self,
50        garg0: GenericArgumentId,
51        garg1: GenericArgumentId,
52    ) -> InferenceResult<GenericArgumentId>;
53    fn conform_impl(&mut self, impl0: ImplId, impl1: ImplId) -> InferenceResult<ImplId>;
54    fn conform_traits(
55        &mut self,
56        trt0: ConcreteTraitId,
57        trt1: ConcreteTraitId,
58    ) -> InferenceResult<ConcreteTraitId>;
59    fn conform_generic_function(
60        &mut self,
61        trt0: GenericFunctionId,
62        trt1: GenericFunctionId,
63    ) -> InferenceResult<GenericFunctionId>;
64    fn ty_contains_var(&mut self, ty: TypeId, var: InferenceVar) -> bool;
65    fn generic_args_contain_var(
66        &mut self,
67        generic_args: &[GenericArgumentId],
68        var: InferenceVar,
69    ) -> bool;
70    fn impl_contains_var(&mut self, impl_id: ImplId, var: InferenceVar) -> bool;
71    fn function_contains_var(&mut self, function_id: FunctionId, var: InferenceVar) -> bool;
72}
73
74impl InferenceConform for Inference<'_> {
75    /// Conforms ty0 to ty1. Should be called when ty0 should be coerced to ty1. Not symmetric.
76    /// Returns the reduced type for ty0, or an error if the type is no coercible.
77    fn conform_ty(&mut self, ty0: TypeId, ty1: TypeId) -> InferenceResult<TypeId> {
78        Ok(self.conform_ty_ex(ty0, ty1, false)?.0)
79    }
80
81    /// Same as conform_ty but supports adding snapshots to ty0 if `ty0_is_self` is true.
82    /// Returns the reduced type for ty0 and the number of snapshots that needs to be added
83    /// for the types to conform.
84    fn conform_ty_ex(
85        &mut self,
86        ty0: TypeId,
87        ty1: TypeId,
88        ty0_is_self: bool,
89    ) -> InferenceResult<(TypeId, usize)> {
90        let ty0 = self.rewrite(ty0).no_err();
91        let ty1 = self.rewrite(ty1).no_err();
92        if ty0 == never_ty(self.db) || ty0.is_missing(self.db) {
93            return Ok((ty1, 0));
94        }
95        if ty0 == ty1 {
96            return Ok((ty0, 0));
97        }
98        let long_ty1 = ty1.lookup_intern(self.db);
99        match long_ty1 {
100            TypeLongId::Var(var) => return Ok((self.assign_ty(var, ty0)?, 0)),
101            TypeLongId::Missing(_) => return Ok((ty1, 0)),
102            TypeLongId::Snapshot(inner_ty) => {
103                if ty0_is_self {
104                    if inner_ty == ty0 {
105                        return Ok((ty1, 1));
106                    }
107                    if !matches!(ty0.lookup_intern(self.db), TypeLongId::Snapshot(_)) {
108                        if let TypeLongId::Var(var) = inner_ty.lookup_intern(self.db) {
109                            return Ok((self.assign_ty(var, ty0)?, 1));
110                        }
111                    }
112                }
113            }
114            TypeLongId::ImplType(impl_type) => {
115                if let Some(ty) = self.impl_type_bounds.get(&impl_type.into()) {
116                    return self.conform_ty_ex(ty0, *ty, ty0_is_self);
117                }
118            }
119            _ => {}
120        }
121        let long_ty0 = ty0.lookup_intern(self.db);
122
123        match long_ty0 {
124            TypeLongId::Concrete(concrete0) => {
125                let (n_snapshots, long_ty1) = self.maybe_peel_snapshots(ty0_is_self, ty1);
126                let TypeLongId::Concrete(concrete1) = long_ty1 else {
127                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
128                };
129                if concrete0.generic_type(self.db) != concrete1.generic_type(self.db) {
130                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
131                }
132                let gargs0 = concrete0.generic_args(self.db);
133                let gargs1 = concrete1.generic_args(self.db);
134                let gargs = self.conform_generic_args(&gargs0, &gargs1)?;
135                let long_ty = TypeLongId::Concrete(ConcreteTypeId::new(
136                    self.db,
137                    concrete0.generic_type(self.db),
138                    gargs,
139                ));
140                Ok((long_ty.intern(self.db), n_snapshots))
141            }
142            TypeLongId::Tuple(tys0) => {
143                let (n_snapshots, long_ty1) = self.maybe_peel_snapshots(ty0_is_self, ty1);
144                let TypeLongId::Tuple(tys1) = long_ty1 else {
145                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
146                };
147                if tys0.len() != tys1.len() {
148                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
149                }
150                let tys = zip_eq(tys0, tys1)
151                    .map(|(subty0, subty1)| self.conform_ty(subty0, subty1))
152                    .collect::<Result<Vec<_>, _>>()?;
153                Ok((TypeLongId::Tuple(tys).intern(self.db), n_snapshots))
154            }
155            TypeLongId::Closure(closure0) => {
156                let (n_snapshots, long_ty1) = self.maybe_peel_snapshots(ty0_is_self, ty1);
157                let TypeLongId::Closure(closure1) = long_ty1 else {
158                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
159                };
160                if closure0.wrapper_location != closure1.wrapper_location {
161                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
162                }
163                let param_tys = zip_eq(closure0.param_tys, closure1.param_tys)
164                    .map(|(subty0, subty1)| self.conform_ty(subty0, subty1))
165                    .collect::<Result<Vec<_>, _>>()?;
166                let captured_types = zip_eq(closure0.captured_types, closure1.captured_types)
167                    .map(|(subty0, subty1)| self.conform_ty(subty0, subty1))
168                    .collect::<Result<Vec<_>, _>>()?;
169                let ret_ty = self.conform_ty(closure0.ret_ty, closure1.ret_ty)?;
170                Ok((
171                    TypeLongId::Closure(ClosureTypeLongId {
172                        param_tys,
173                        ret_ty,
174                        captured_types,
175                        wrapper_location: closure0.wrapper_location,
176                        parent_function: closure0.parent_function,
177                    })
178                    .intern(self.db),
179                    n_snapshots,
180                ))
181            }
182            TypeLongId::FixedSizeArray { type_id, size } => {
183                let (n_snapshots, long_ty1) = self.maybe_peel_snapshots(ty0_is_self, ty1);
184                let TypeLongId::FixedSizeArray { type_id: type_id1, size: size1 } = long_ty1 else {
185                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
186                };
187                let size = self.conform_const(size, size1)?;
188                let ty = self.conform_ty(type_id, type_id1)?;
189                Ok((TypeLongId::FixedSizeArray { type_id: ty, size }.intern(self.db), n_snapshots))
190            }
191            TypeLongId::Snapshot(inner_ty0) => {
192                let TypeLongId::Snapshot(inner_ty1) = long_ty1 else {
193                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
194                };
195                let (ty, n_snapshots) = self.conform_ty_ex(inner_ty0, inner_ty1, ty0_is_self)?;
196                Ok((TypeLongId::Snapshot(ty).intern(self.db), n_snapshots))
197            }
198            TypeLongId::GenericParameter(_) => {
199                Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }))
200            }
201            TypeLongId::Var(var) => Ok((self.assign_ty(var, ty1)?, 0)),
202            TypeLongId::ImplType(impl_type) => {
203                if let Some(ty) = self.impl_type_bounds.get(&impl_type.into()) {
204                    return self.conform_ty_ex(*ty, ty1, ty0_is_self);
205                }
206                Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }))
207            }
208            TypeLongId::Missing(_) => Ok((ty0, 0)),
209            TypeLongId::Coupon(function_id0) => {
210                let TypeLongId::Coupon(function_id1) = long_ty1 else {
211                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
212                };
213
214                let func0 = function_id0.lookup_intern(self.db).function;
215                let func1 = function_id1.lookup_intern(self.db).function;
216
217                let generic_function =
218                    self.conform_generic_function(func0.generic_function, func1.generic_function)?;
219
220                if func0.generic_args.len() != func1.generic_args.len() {
221                    return Err(self.set_error(InferenceError::TypeKindMismatch { ty0, ty1 }));
222                }
223
224                let generic_args =
225                    self.conform_generic_args(&func0.generic_args, &func1.generic_args)?;
226
227                Ok((
228                    TypeLongId::Coupon(
229                        FunctionLongId {
230                            function: ConcreteFunction { generic_function, generic_args },
231                        }
232                        .intern(self.db),
233                    )
234                    .intern(self.db),
235                    0,
236                ))
237            }
238        }
239    }
240
241    /// Conforms id0 to id1. Should be called when id0 should be coerced to id1. Not symmetric.
242    /// Returns the reduced const for id0, or an error if the const is no coercible.
243    fn conform_const(
244        &mut self,
245        id0: ConstValueId,
246        id1: ConstValueId,
247    ) -> InferenceResult<ConstValueId> {
248        let id0 = self.rewrite(id0).no_err();
249        let id1 = self.rewrite(id1).no_err();
250        self.conform_ty(id0.ty(self.db).unwrap(), id1.ty(self.db).unwrap())?;
251        if id0 == id1 {
252            return Ok(id0);
253        }
254        let const_value0 = id0.lookup_intern(self.db);
255        if matches!(const_value0, ConstValue::Missing(_)) {
256            return Ok(id1);
257        }
258        match id1.lookup_intern(self.db) {
259            ConstValue::Missing(_) => return Ok(id1),
260            ConstValue::Var(var, _) => return self.assign_const(var, id0),
261            _ => {}
262        }
263        match const_value0 {
264            ConstValue::Var(var, _) => Ok(self.assign_const(var, id1)?),
265            ConstValue::ImplConstant(_) => {
266                Err(self.set_error(InferenceError::ConstKindMismatch { const0: id0, const1: id1 }))
267            }
268            _ => {
269                Err(self.set_error(InferenceError::ConstKindMismatch { const0: id0, const1: id1 }))
270            }
271        }
272    }
273
274    // Conditionally peels snapshots.
275    fn maybe_peel_snapshots(&mut self, ty0_is_self: bool, ty1: TypeId) -> (usize, TypeLongId) {
276        let (n_snapshots, long_ty1) = if ty0_is_self {
277            peel_snapshots(self.db, ty1)
278        } else {
279            (0, ty1.lookup_intern(self.db))
280        };
281        (n_snapshots, long_ty1)
282    }
283
284    /// Conforms generics args. See `conform_ty()`.
285    fn conform_generic_args(
286        &mut self,
287        gargs0: &[GenericArgumentId],
288        gargs1: &[GenericArgumentId],
289    ) -> InferenceResult<Vec<GenericArgumentId>> {
290        zip_eq(gargs0, gargs1)
291            .map(|(garg0, garg1)| self.conform_generic_arg(*garg0, *garg1))
292            .collect::<Result<Vec<_>, _>>()
293    }
294
295    /// Conforms a generics arg. See `conform_ty()`.
296    fn conform_generic_arg(
297        &mut self,
298        garg0: GenericArgumentId,
299        garg1: GenericArgumentId,
300    ) -> InferenceResult<GenericArgumentId> {
301        if garg0 == garg1 {
302            return Ok(garg0);
303        }
304        match garg0 {
305            GenericArgumentId::Type(gty0) => {
306                let GenericArgumentId::Type(gty1) = garg1 else {
307                    return Err(self.set_error(InferenceError::GenericArgMismatch { garg0, garg1 }));
308                };
309                Ok(GenericArgumentId::Type(self.conform_ty(gty0, gty1)?))
310            }
311            GenericArgumentId::Constant(gc0) => {
312                let GenericArgumentId::Constant(gc1) = garg1 else {
313                    return Err(self.set_error(InferenceError::GenericArgMismatch { garg0, garg1 }));
314                };
315
316                Ok(GenericArgumentId::Constant(self.conform_const(gc0, gc1)?))
317            }
318            GenericArgumentId::Impl(impl0) => {
319                let GenericArgumentId::Impl(impl1) = garg1 else {
320                    return Err(self.set_error(InferenceError::GenericArgMismatch { garg0, garg1 }));
321                };
322                Ok(GenericArgumentId::Impl(self.conform_impl(impl0, impl1)?))
323            }
324            GenericArgumentId::NegImpl => match garg1 {
325                GenericArgumentId::NegImpl => Ok(GenericArgumentId::NegImpl),
326                GenericArgumentId::Constant(_)
327                | GenericArgumentId::Type(_)
328                | GenericArgumentId::Impl(_) => {
329                    Err(self.set_error(InferenceError::GenericArgMismatch { garg0, garg1 }))
330                }
331            },
332        }
333    }
334
335    /// Conforms an impl. See `conform_ty()`.
336    fn conform_impl(&mut self, impl0: ImplId, impl1: ImplId) -> InferenceResult<ImplId> {
337        let impl0 = self.rewrite(impl0).no_err();
338        let impl1 = self.rewrite(impl1).no_err();
339        let long_impl1 = impl1.lookup_intern(self.db);
340        if impl0 == impl1 {
341            return Ok(impl0);
342        }
343        if let ImplLongId::ImplVar(var) = long_impl1 {
344            let impl_concrete_trait = self
345                .db
346                .impl_concrete_trait(impl0)
347                .map_err(|diag_added| self.set_error(InferenceError::Reported(diag_added)))?;
348            self.conform_traits(var.lookup_intern(self.db).concrete_trait_id, impl_concrete_trait)?;
349            let impl_id = self.rewrite(impl0).no_err();
350            return self.assign_impl(var, impl_id);
351        }
352        match impl0.lookup_intern(self.db) {
353            ImplLongId::ImplVar(var) => {
354                let impl_concrete_trait = self
355                    .db
356                    .impl_concrete_trait(impl1)
357                    .map_err(|diag_added| self.set_error(InferenceError::Reported(diag_added)))?;
358                self.conform_traits(
359                    var.lookup_intern(self.db).concrete_trait_id,
360                    impl_concrete_trait,
361                )?;
362                let impl_id = self.rewrite(impl1).no_err();
363                self.assign_impl(var, impl_id)
364            }
365            ImplLongId::Concrete(concrete0) => {
366                let ImplLongId::Concrete(concrete1) = long_impl1 else {
367                    return Err(self.set_error(InferenceError::ImplKindMismatch { impl0, impl1 }));
368                };
369                let concrete0 = concrete0.lookup_intern(self.db);
370                let concrete1 = concrete1.lookup_intern(self.db);
371                if concrete0.impl_def_id != concrete1.impl_def_id {
372                    return Err(self.set_error(InferenceError::ImplKindMismatch { impl0, impl1 }));
373                }
374                let gargs0 = concrete0.generic_args;
375                let gargs1 = concrete1.generic_args;
376                let generic_args = self.conform_generic_args(&gargs0, &gargs1)?;
377                Ok(ImplLongId::Concrete(
378                    ConcreteImplLongId { impl_def_id: concrete0.impl_def_id, generic_args }
379                        .intern(self.db),
380                )
381                .intern(self.db))
382            }
383            ImplLongId::GenericParameter(_)
384            | ImplLongId::ImplImpl(_)
385            | ImplLongId::SelfImpl(_)
386            | ImplLongId::GeneratedImpl(_) => {
387                Err(self.set_error(InferenceError::ImplKindMismatch { impl0, impl1 }))
388            }
389        }
390    }
391
392    /// Conforms generics traits. See `conform_ty()`.
393    fn conform_traits(
394        &mut self,
395        trt0: ConcreteTraitId,
396        trt1: ConcreteTraitId,
397    ) -> InferenceResult<ConcreteTraitId> {
398        let trt0 = trt0.lookup_intern(self.db);
399        let trt1 = trt1.lookup_intern(self.db);
400        if trt0.trait_id != trt1.trait_id {
401            return Err(self.set_error(InferenceError::TraitMismatch {
402                trt0: trt0.trait_id,
403                trt1: trt1.trait_id,
404            }));
405        }
406        let generic_args = self.conform_generic_args(&trt0.generic_args, &trt1.generic_args)?;
407        Ok(ConcreteTraitLongId { trait_id: trt0.trait_id, generic_args }.intern(self.db))
408    }
409
410    fn conform_generic_function(
411        &mut self,
412        func0: GenericFunctionId,
413        func1: GenericFunctionId,
414    ) -> InferenceResult<GenericFunctionId> {
415        if let (GenericFunctionId::Impl(id0), GenericFunctionId::Impl(id1)) = (func0, func1) {
416            if id0.function != id1.function {
417                return Err(
418                    self.set_error(InferenceError::GenericFunctionMismatch { func0, func1 })
419                );
420            }
421            let function = id0.function;
422            let impl_id = self.conform_impl(id0.impl_id, id1.impl_id)?;
423            return Ok(GenericFunctionId::Impl(ImplGenericFunctionId { impl_id, function }));
424        }
425
426        if func0 != func1 {
427            return Err(self.set_error(InferenceError::GenericFunctionMismatch { func0, func1 }));
428        }
429        Ok(func0)
430    }
431
432    /// Checks if a type tree contains a certain [InferenceVar] somewhere. Used to avoid inference
433    /// cycles.
434    fn ty_contains_var(&mut self, ty: TypeId, var: InferenceVar) -> bool {
435        let ty = self.rewrite(ty).no_err();
436        self.internal_ty_contains_var(ty, var)
437    }
438
439    /// Checks if a slice of generics arguments contain a certain [InferenceVar] somewhere. Used to
440    /// avoid inference cycles.
441    fn generic_args_contain_var(
442        &mut self,
443        generic_args: &[GenericArgumentId],
444        var: InferenceVar,
445    ) -> bool {
446        for garg in generic_args {
447            if match *garg {
448                GenericArgumentId::Type(ty) => self.internal_ty_contains_var(ty, var),
449                GenericArgumentId::Constant(_) => false,
450                GenericArgumentId::Impl(impl_id) => self.impl_contains_var(impl_id, var),
451                GenericArgumentId::NegImpl => false,
452            } {
453                return true;
454            }
455        }
456        false
457    }
458
459    /// Checks if an impl contains a certain [InferenceVar] somewhere. Used to avoid inference
460    /// cycles.
461    fn impl_contains_var(&mut self, impl_id: ImplId, var: InferenceVar) -> bool {
462        match impl_id.lookup_intern(self.db) {
463            ImplLongId::Concrete(concrete_impl_id) => self.generic_args_contain_var(
464                &concrete_impl_id.lookup_intern(self.db).generic_args,
465                var,
466            ),
467            ImplLongId::SelfImpl(concrete_trait_id) => {
468                self.generic_args_contain_var(&concrete_trait_id.generic_args(self.db), var)
469            }
470            ImplLongId::GenericParameter(_) => false,
471            ImplLongId::ImplVar(new_var) => {
472                let new_var_long_id = new_var.lookup_intern(self.db);
473                let new_var_local_id = new_var_long_id.id;
474                if InferenceVar::Impl(new_var_local_id) == var {
475                    return true;
476                }
477                if let Some(impl_id) = self.impl_assignment(new_var_local_id) {
478                    return self.impl_contains_var(impl_id, var);
479                }
480                self.generic_args_contain_var(
481                    &new_var_long_id.concrete_trait_id.generic_args(self.db),
482                    var,
483                )
484            }
485            ImplLongId::ImplImpl(impl_impl) => self.impl_contains_var(impl_impl.impl_id(), var),
486            ImplLongId::GeneratedImpl(generated_impl) => self.generic_args_contain_var(
487                &generated_impl.concrete_trait(self.db).generic_args(self.db),
488                var,
489            ),
490        }
491    }
492
493    /// Checks if a function contains a certain [InferenceVar] in its generic arguments or in the
494    /// generic arguments of the impl containing the function (in case the function is an impl
495    /// function).
496    ///
497    /// Used to avoid inference cycles.
498    fn function_contains_var(&mut self, function_id: FunctionId, var: InferenceVar) -> bool {
499        let function = function_id.get_concrete(self.db);
500        let generic_args = function.generic_args;
501        // Look in the generic arguments of the function and in the impl generic arguments.
502        self.generic_args_contain_var(&generic_args, var)
503            || matches!(function.generic_function,
504                GenericFunctionId::Impl(impl_generic_function_id)
505                if self.impl_contains_var(impl_generic_function_id.impl_id, var)
506            )
507    }
508}
509
510impl Inference<'_> {
511    /// Reduces an impl type to a concrete type.
512    pub fn reduce_impl_ty(&mut self, impl_type_id: ImplTypeId) -> InferenceResult<TypeId> {
513        let impl_id = impl_type_id.impl_id();
514        let trait_ty = impl_type_id.ty();
515        if let ImplLongId::ImplVar(var) = impl_id.lookup_intern(self.db) {
516            Ok(self.rewritten_impl_type(var, trait_ty))
517        } else if let Ok(ty) =
518            self.db.impl_type_concrete_implized(ImplTypeId::new(impl_id, trait_ty, self.db))
519        {
520            Ok(ty)
521        } else {
522            Err(self.set_impl_reduction_error(impl_id))
523        }
524    }
525
526    /// Reduces an impl constant to a concrete const.
527    pub fn reduce_impl_constant(
528        &mut self,
529        impl_const_id: ImplConstantId,
530    ) -> InferenceResult<ConstValueId> {
531        let impl_id = impl_const_id.impl_id();
532        let trait_constant = impl_const_id.trait_constant_id();
533        if let ImplLongId::ImplVar(var) = impl_id.lookup_intern(self.db) {
534            Ok(self.rewritten_impl_constant(var, trait_constant))
535        } else if let Ok(constant) = self.db.impl_constant_concrete_implized_value(
536            ImplConstantId::new(impl_id, trait_constant, self.db),
537        ) {
538            Ok(constant)
539        } else {
540            Err(self.set_impl_reduction_error(impl_id))
541        }
542    }
543
544    /// Reduces an impl impl to a concrete impl.
545    pub fn reduce_impl_impl(&mut self, impl_impl_id: ImplImplId) -> InferenceResult<ImplId> {
546        let impl_id = impl_impl_id.impl_id();
547        let concrete_trait_impl = impl_impl_id
548            .concrete_trait_impl_id(self.db)
549            .map_err(|diag_added| self.set_error(InferenceError::Reported(diag_added)))?;
550
551        if let ImplLongId::ImplVar(var) = impl_id.lookup_intern(self.db) {
552            Ok(self.rewritten_impl_impl(var, concrete_trait_impl))
553        } else if let Ok(imp) = self.db.impl_impl_concrete_implized(ImplImplId::new(
554            impl_id,
555            impl_impl_id.trait_impl_id(),
556            self.db,
557        )) {
558            Ok(imp)
559        } else {
560            Err(self.set_impl_reduction_error(impl_id))
561        }
562    }
563
564    /// Returns the type of an impl var's type item.
565    /// The type may be a variable itself, but it may previously exist, so may be more specific due
566    /// to rewriting.
567    pub fn rewritten_impl_type(&mut self, id: ImplVarId, trait_type_id: TraitTypeId) -> TypeId {
568        self.rewritten_impl_item(
569            id,
570            trait_type_id,
571            |m| &mut m.types,
572            |inference, stable_ptr| inference.new_type_var(stable_ptr),
573        )
574    }
575
576    /// Returns the constant value of an impl var's constant item.
577    /// The constant may be a variable itself, but it may previously exist, so may be more specific
578    /// due to rewriting.
579    pub fn rewritten_impl_constant(
580        &mut self,
581        id: ImplVarId,
582        trait_constant: TraitConstantId,
583    ) -> ConstValueId {
584        self.rewritten_impl_item(
585            id,
586            trait_constant,
587            |m| &mut m.constants,
588            |inference, stable_ptr| {
589                inference.new_const_var(
590                    stable_ptr,
591                    inference.db.trait_constant_type(trait_constant).unwrap(),
592                )
593            },
594        )
595    }
596
597    /// Returns the inner_impl value of an impl var's impl item.
598    /// The inner_impl may be a variable itself, but it may previously exist, so may be more
599    /// specific due to rewriting.
600    pub fn rewritten_impl_impl(
601        &mut self,
602        id: ImplVarId,
603        concrete_trait_impl: ConcreteTraitImplId,
604    ) -> ImplId {
605        self.rewritten_impl_item(
606            id,
607            concrete_trait_impl.trait_impl(self.db),
608            |m| &mut m.impls,
609            |inference, stable_ptr| {
610                inference.new_impl_var(
611                    inference.db.concrete_trait_impl_concrete_trait(concrete_trait_impl).unwrap(),
612                    stable_ptr,
613                    ImplLookupContext::default(),
614                )
615            },
616        )
617    }
618
619    /// Helper function for getting an impl vars item ids.
620    /// These ids are likely to be variables, but may have more specific information due to
621    /// rewriting.
622    fn rewritten_impl_item<K: Hash + PartialEq + Eq, V: Copy>(
623        &mut self,
624        id: ImplVarId,
625        key: K,
626        get_map: impl Fn(&mut ImplVarTraitItemMappings) -> &mut OrderedHashMap<K, V>,
627        new_var: impl FnOnce(&mut Self, Option<SyntaxStablePtrId>) -> V,
628    ) -> V
629    where
630        Self: SemanticRewriter<V, NoError>,
631    {
632        let var_id = id.id(self.db);
633        if let Some(value) = self
634            .data
635            .impl_vars_trait_item_mappings
636            .get_mut(&var_id)
637            .and_then(|mappings| get_map(mappings).get(&key))
638        {
639            // Copy the value to allow usage of `self`.
640            let value = *value;
641            // If the value already exists, rewrite it before returning.
642            self.rewrite(value).no_err()
643        } else {
644            let value =
645                new_var(self, self.data.stable_ptrs.get(&InferenceVar::Impl(var_id)).cloned());
646            get_map(self.data.impl_vars_trait_item_mappings.entry(var_id).or_default())
647                .insert(key, value);
648            value
649        }
650    }
651
652    /// Sets an error for an impl reduction failure.
653    fn set_impl_reduction_error(&mut self, impl_id: ImplId) -> ErrorSet {
654        self.set_error(
655            impl_id
656                .concrete_trait(self.db)
657                .map(InferenceError::NoImplsFound)
658                .unwrap_or_else(InferenceError::Reported),
659        )
660    }
661
662    /// Conforms a type to a type. Returning the reduced types on failure.
663    /// Useful for immediately reporting a diagnostic based on the compared types.
664    pub fn conform_ty_for_diag(
665        &mut self,
666        ty0: TypeId,
667        ty1: TypeId,
668        diagnostics: &mut SemanticDiagnostics,
669        diag_stable_ptr: impl FnOnce() -> SyntaxStablePtrId,
670        diag_kind: impl FnOnce(TypeId, TypeId) -> SemanticDiagnosticKind,
671    ) -> Maybe<()> {
672        match self.conform_ty(ty0, ty1) {
673            Ok(_ty) => Ok(()),
674            Err(err) => {
675                let ty0 = self.rewrite(ty0).no_err();
676                let ty1 = self.rewrite(ty1).no_err();
677                Err(if ty0 != ty1 {
678                    let diag_added = diagnostics.report(diag_stable_ptr(), diag_kind(ty0, ty1));
679                    self.consume_reported_error(err, diag_added);
680                    diag_added
681                } else {
682                    self.report_on_pending_error(err, diagnostics, diag_stable_ptr())
683                })
684            }
685        }
686    }
687
688    /// helper function for ty_contains_var
689    /// Assumes ty was already rewritten.
690    #[doc(hidden)]
691    fn internal_ty_contains_var(&mut self, ty: TypeId, var: InferenceVar) -> bool {
692        match ty.lookup_intern(self.db) {
693            TypeLongId::Concrete(concrete) => {
694                let generic_args = concrete.generic_args(self.db);
695                self.generic_args_contain_var(&generic_args, var)
696            }
697            TypeLongId::Tuple(tys) => {
698                tys.into_iter().any(|ty| self.internal_ty_contains_var(ty, var))
699            }
700            TypeLongId::Snapshot(ty) => self.internal_ty_contains_var(ty, var),
701            TypeLongId::Var(new_var) => {
702                if InferenceVar::Type(new_var.id) == var {
703                    return true;
704                }
705                if let Some(ty) = self.type_assignment.get(&new_var.id) {
706                    return self.internal_ty_contains_var(*ty, var);
707                }
708                false
709            }
710            TypeLongId::ImplType(id) => self.impl_contains_var(id.impl_id(), var),
711            TypeLongId::GenericParameter(_) | TypeLongId::Missing(_) => false,
712            TypeLongId::Coupon(function_id) => self.function_contains_var(function_id, var),
713            TypeLongId::FixedSizeArray { type_id, .. } => {
714                self.internal_ty_contains_var(type_id, var)
715            }
716            TypeLongId::Closure(closure) => {
717                closure.param_tys.into_iter().any(|ty| self.internal_ty_contains_var(ty, var))
718                    || self.internal_ty_contains_var(closure.ret_ty, var)
719            }
720        }
721    }
722
723    /// Creates a var for each constrained impl_type and conforms the types.
724    pub fn conform_generic_params_type_constraints(&mut self, constraints: &Vec<(TypeId, TypeId)>) {
725        let mut impl_type_bounds = Default::default();
726        for (ty0, ty1) in constraints {
727            let ty0 = if let TypeLongId::ImplType(impl_type) = ty0.lookup_intern(self.db) {
728                self.impl_type_assignment(impl_type, &mut impl_type_bounds)
729            } else {
730                *ty0
731            };
732            let ty1 = if let TypeLongId::ImplType(impl_type) = ty1.lookup_intern(self.db) {
733                self.impl_type_assignment(impl_type, &mut impl_type_bounds)
734            } else {
735                *ty1
736            };
737            self.conform_ty(ty0, ty1).ok();
738        }
739        self.set_impl_type_bounds(impl_type_bounds);
740    }
741
742    /// An helper function for getting for an impl type assignment.
743    /// Creates a new type var if the impl type is not yet assigned.
744    fn impl_type_assignment(
745        &mut self,
746        impl_type: ImplTypeId,
747        impl_type_bounds: &mut OrderedHashMap<ImplTypeId, TypeId>,
748    ) -> TypeId {
749        match impl_type_bounds.entry(impl_type) {
750            Entry::Occupied(entry) => *entry.get(),
751            Entry::Vacant(entry) => {
752                let inference_id = self.data.inference_id;
753                let id = LocalTypeVarId(self.data.type_vars.len());
754                let var = TypeVar { inference_id, id };
755                let ty = TypeLongId::Var(var).intern(self.db);
756                entry.insert(ty);
757                self.type_vars.push(var);
758                ty
759            }
760        }
761    }
762}
cairo_lang_semantic/expr/inference/conform.rs

cairo_lang_semantic/expr/inference/
conform.rs
