luaur_analysis/methods/
unifier_2_unify_unifier_2_alt_q.rs

1//! Source: `Analysis/src/Unifier2.cpp:669-807` — `Unifier2::unify_(TypePackId, TypePackId)`,
2//! the type-pack core of new-solver unification.
3
4use crate::enums::occurs_check_result::OccursCheckResult;
5use crate::enums::unify_result::UnifyResult;
6use crate::functions::as_mutable_type_pack::as_mutable_type_pack_id;
7use crate::functions::emplace_type_pack::emplace_type_pack;
8use crate::functions::extend_type_pack::extend_type_pack;
9use crate::functions::flatten_type_pack::flatten_type_pack_id;
10use crate::functions::follow_type_pack::follow_type_pack_id;
11use crate::functions::get_type_pack::get_type_pack_id;
12use crate::functions::is_irresolvable_unifier_2_alt_b::is_irresolvable;
13use crate::functions::occurs_check_type_utils_alt_b::occurs_check_type_pack_id_type_pack_id;
14use crate::records::free_type_pack::FreeTypePack;
15use crate::records::non_exceptional_recursion_limiter::NonExceptionalRecursionLimiter;
16use crate::records::pack_subtype_constraint::PackSubtypeConstraint;
17use crate::records::replacer::Replacer;
18use crate::records::type_pack::TypePack;
19use crate::records::unifier_2::Unifier2;
20use crate::type_aliases::constraint_v::ConstraintV;
21use crate::type_aliases::type_id::TypeId;
22use crate::type_aliases::type_pack_id::TypePackId;
23use crate::type_aliases::type_pack_variant::TypePackVariant;
24use core::ptr::NonNull;
25use luaur_common::macros::luau_assert::LUAU_ASSERT;
26use luaur_common::records::dense_hash_set::DenseHashSet;
27use luaur_common::{FFlag, FInt};
28
29impl Unifier2 {
30    pub fn unify_type_pack_id_type_pack_id(
31        &mut self,
32        mut sub_tp: TypePackId,
33        mut super_tp: TypePackId,
34    ) -> UnifyResult {
35        if FInt::LuauTypeInferIterationLimit.get() > 0
36            && self.iteration_count >= FInt::LuauTypeInferIterationLimit.get() as i32
37        {
38            return UnifyResult::TooComplex;
39        }
40
41        self.iteration_count += 1;
42
43        if FFlag::LuauLimitUnificationRecursion.get() {
44            // ++(*count) — mirror the C++ NonExceptionalRecursionLimiter (RecursionCounter ctor).
45            self.recursion_count += 1;
46            let mut nerl = NonExceptionalRecursionLimiter {
47                base: unsafe { core::mem::zeroed() },
48                native_stack_guard: unsafe { core::mem::zeroed() },
49            };
50            nerl.non_exceptional_recursion_limiter_non_exceptional_recursion_limiter(
51                &mut self.recursion_count as *mut i32 as *mut core::ffi::c_int,
52            );
53            if !nerl.is_ok(self.recursion_limit as core::ffi::c_int) {
54                return UnifyResult::TooComplex;
55            }
56        }
57
58        sub_tp = unsafe { follow_type_pack_id(sub_tp) };
59        super_tp = unsafe { follow_type_pack_id(super_tp) };
60
61        if self.seen_type_pack_pairings.contains(&(sub_tp, super_tp)) {
62            return UnifyResult::Ok;
63        }
64        self.seen_type_pack_pairings.insert((sub_tp, super_tp));
65
66        if sub_tp == super_tp {
67            return UnifyResult::Ok;
68        }
69
70        // FIXME: CLI-188000: If we are _directly_ given a free type, we must
71        // eagerly emplace it. Otherwise, later, we may generalize the underlying
72        // free types incorrectly.
73        if !unsafe { get_type_pack_id::<FreeTypePack>(sub_tp) }.is_null() {
74            return self.emplace_free_type_pack(sub_tp, super_tp);
75        }
76
77        if !unsafe { get_type_pack_id::<FreeTypePack>(super_tp) }.is_null() {
78            return self.emplace_free_type_pack(super_tp, sub_tp);
79        }
80
81        let sub_len = flatten_type_pack_id(sub_tp).0.len();
82        let super_len = flatten_type_pack_id(super_tp).0.len();
83        let max_length = core::cmp::max(sub_len, super_len);
84
85        let arena = self.arena.as_ptr();
86        let builtin_types_ptr = self.builtin_types.as_ptr();
87
88        let sub_extended = extend_type_pack(
89            unsafe { &mut *arena },
90            builtin_types_ptr,
91            sub_tp,
92            max_length,
93            alloc::vec::Vec::new(),
94        );
95        let super_extended = extend_type_pack(
96            unsafe { &mut *arena },
97            builtin_types_ptr,
98            super_tp,
99            max_length,
100            alloc::vec::Vec::new(),
101        );
102
103        let sub_types = sub_extended.head;
104        let sub_tail = sub_extended.tail;
105        let super_types = super_extended.head;
106        let super_tail = super_extended.tail;
107
108        let limit = core::cmp::min(sub_types.len(), super_types.len());
109        for i in 0..limit {
110            self.unify_type_id_type_id(sub_types[i], super_types[i]);
111        }
112
113        // At this point it should be the case that either:
114        // - `subTypes` now has all of its types unified, and we are down to its tail
115        // - `superTypes` now has all of its types unified, and we are down to its tail
116
117        if sub_tail.is_none() && super_tail.is_none() {
118            // If both types are missing a tail, we've done all we can.
119            return UnifyResult::Ok;
120        }
121
122        // It should be the case that exclusively one of these packs can be reduced
123        // to their tail for the rest of the function.
124        if limit < sub_types.len() {
125            LUAU_ASSERT!(limit == super_types.len());
126            // If we have extra subtypes left over, construct a new type pack
127            let new_sub_head: alloc::vec::Vec<TypeId> = sub_types[super_types.len()..].to_vec();
128            sub_tp = unsafe { &mut *arena }.add_type_pack_t(TypePack {
129                head: new_sub_head,
130                tail: sub_tail,
131            });
132            super_tp = self.maybe_replace_tail(super_tail);
133        } else if limit < super_types.len() {
134            LUAU_ASSERT!(limit == sub_types.len() && limit < super_types.len());
135            // If we have extra subtypes left over, construct a new type pack
136            let new_super_head: alloc::vec::Vec<TypeId> = super_types[sub_types.len()..].to_vec();
137            super_tp = unsafe { &mut *arena }.add_type_pack_t(TypePack {
138                head: new_super_head,
139                tail: super_tail,
140            });
141            sub_tp = self.maybe_replace_tail(sub_tail);
142        } else {
143            sub_tp = self.maybe_replace_tail(sub_tail);
144            super_tp = self.maybe_replace_tail(super_tail);
145        }
146
147        if is_irresolvable(sub_tp) || is_irresolvable(super_tp) {
148            if !self.uninhabited_type_functions.is_null()
149                && unsafe {
150                    (*self.uninhabited_type_functions)
151                        .contains(&(sub_tp as *const core::ffi::c_void))
152                        || (*self.uninhabited_type_functions)
153                            .contains(&(super_tp as *const core::ffi::c_void))
154                }
155            {
156                return UnifyResult::Ok;
157            }
158
159            self.incomplete_subtypes
160                .push(ConstraintV::PackSubtype(PackSubtypeConstraint {
161                    sub_pack: sub_tp,
162                    super_pack: super_tp,
163                    returns: false,
164                }));
165            return UnifyResult::Ok;
166        }
167
168        // ... after doing all of our replacements, we may also need to check for
169        // free types again.
170
171        if !unsafe { get_type_pack_id::<FreeTypePack>(sub_tp) }.is_null() {
172            return self.emplace_free_type_pack(sub_tp, super_tp);
173        }
174
175        if !unsafe { get_type_pack_id::<FreeTypePack>(super_tp) }.is_null() {
176            return self.emplace_free_type_pack(super_tp, sub_tp);
177        }
178
179        UnifyResult::Ok
180    }
181
182    /// C++ `emplaceFreeTypePack` lambda from `unify_(TypePackId, TypePackId)`.
183    fn emplace_free_type_pack(&mut self, target: TypePackId, bound_to: TypePackId) -> UnifyResult {
184        LUAU_ASSERT!(!unsafe { get_type_pack_id::<FreeTypePack>(target) }.is_null());
185
186        let bound_to = self.instantiate_with_bound_types_pack(bound_to);
187
188        let error_pack = unsafe { (*self.builtin_types.as_ptr()).errorTypePack };
189
190        if FFlag::LuauOccursCheckForAllBindings.get() {
191            if occurs_check_type_pack_id_type_pack_id(target, bound_to) == OccursCheckResult::Fail {
192                emplace_type_pack(
193                    unsafe { as_mutable_type_pack_id(target) },
194                    TypePackVariant::Bound(error_pack),
195                );
196                return UnifyResult::OccursCheckFailed;
197            }
198        } else {
199            let mut seen: DenseHashSet<TypePackId> = DenseHashSet::new(core::ptr::null());
200            if OccursCheckResult::Fail == self.occurs_check_deprecated(&mut seen, target, bound_to)
201            {
202                emplace_type_pack(
203                    unsafe { as_mutable_type_pack_id(target) },
204                    TypePackVariant::Bound(error_pack),
205                );
206                return UnifyResult::OccursCheckFailed;
207            }
208        }
209
210        emplace_type_pack(
211            unsafe { as_mutable_type_pack_id(target) },
212            TypePackVariant::Bound(bound_to),
213        );
214        UnifyResult::Ok
215    }
216
217    /// C++ `maybeReplaceTail` lambda from `unify_(TypePackId, TypePackId)`.
218    fn maybe_replace_tail(&self, maybe_tp: Option<TypePackId>) -> TypePackId {
219        let maybe_tp = match maybe_tp {
220            None => return unsafe { (*self.builtin_types.as_ptr()).emptyTypePack },
221            Some(tp) => tp,
222        };
223
224        let tp = unsafe { follow_type_pack_id(maybe_tp) };
225        if let Some(replacement) = self.generic_pack_substitutions.find(&tp) {
226            return unsafe { follow_type_pack_id(*replacement) };
227        }
228        tp
229    }
230
231    /// `instantiateWithBoundTypes` for type packs (`Unifier2.cpp:307-314`, TypePackId
232    /// instantiation of the `template<typename TID>` overload).
233    fn instantiate_with_bound_types_pack(&mut self, tp: TypePackId) -> TypePackId {
234        let mut r = Replacer::replacer(
235            self.arena.as_ptr(),
236            NonNull::from(&mut self.generic_substitutions).as_ptr(),
237            NonNull::from(&mut self.generic_pack_substitutions).as_ptr(),
238        );
239        if let Some(new_tp) = r.substitute_type_pack_id(tp) {
240            return new_tp;
241        }
242        tp
243    }
244}
luaur_analysis/methods/unifier_2_unify_unifier_2_alt_q.rs

luaur_analysis/methods/
unifier_2_unify_unifier_2_alt_q.rs
