cairo_lang_semantic/expr/inference/
conform.rs

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

cairo_lang_semantic/expr/inference/
conform.rs
