luaur_analysis/methods/
unifier_reflexive_equal.rs

1//! Reflexive structural-equality fast-path for the unifier.
2//!
3//! C++ Luau keeps the `if (superTy == subTy) return;` pointer fast-path in
4//! `tryUnify_` cheap because type-alias unions (and the function/pack types
5//! built over them) share a single TypeId across every use, so the pointer
6//! check fires pervasively. Our port does NOT pointer-share alias-derived
7//! composite types, so structurally-identical `Color`/function/pack values sit
8//! at distinct pointers and the pointer check misses — forcing the full
9//! element-by-element walk on every curried use and blowing the iteration
10//! limit on pathological inputs (`luau_subtyping_is_np_hard`).
11//!
12//! Unifying a type/pack with a structurally-identical type/pack always succeeds
13//! by reflexivity, regardless of variance, so short-circuiting here is sound.
14//! The walk is log-aware (uses `self.log.follow*`) and depth-bounded; on hitting
15//! the bound it conservatively returns `false` and the normal unifier runs.
16use crate::records::function_type::FunctionType;
17use crate::records::intersection_type::IntersectionType;
18use crate::records::type_pack::TypePack;
19use crate::records::unifier::Unifier;
20use crate::records::union_type::UnionType;
21use crate::type_aliases::type_id::TypeId;
22use crate::type_aliases::type_pack_id::TypePackId;
23
24impl Unifier {
25    pub(crate) fn reflexive_equal_type_id(&self, a: TypeId, b: TypeId, depth: u32) -> bool {
26        if depth == 0 {
27            return false;
28        }
29        let a = self.log.follow_type_id(a);
30        let b = self.log.follow_type_id(b);
31        if a == b {
32            return true;
33        }
34        unsafe {
35            let au = self.log.txn_log_get::<UnionType, TypeId>(a);
36            let bu = self.log.txn_log_get::<UnionType, TypeId>(b);
37            if !au.is_null() && !bu.is_null() {
38                let ao = &(*au).options;
39                let bo = &(*bu).options;
40                return ao.len() == bo.len()
41                    && ao
42                        .iter()
43                        .zip(bo.iter())
44                        .all(|(x, y)| self.reflexive_equal_type_id(*x, *y, depth - 1));
45            }
46
47            let ai = self.log.txn_log_get::<IntersectionType, TypeId>(a);
48            let bi = self.log.txn_log_get::<IntersectionType, TypeId>(b);
49            if !ai.is_null() && !bi.is_null() {
50                let ap = &(*ai).parts;
51                let bp = &(*bi).parts;
52                return ap.len() == bp.len()
53                    && ap
54                        .iter()
55                        .zip(bp.iter())
56                        .all(|(x, y)| self.reflexive_equal_type_id(*x, *y, depth - 1));
57            }
58
59            let af = self.log.txn_log_get::<FunctionType, TypeId>(a);
60            let bf = self.log.txn_log_get::<FunctionType, TypeId>(b);
61            if !af.is_null() && !bf.is_null() {
62                return self.reflexive_equal_type_pack_id(
63                    (*af).arg_types,
64                    (*bf).arg_types,
65                    depth - 1,
66                ) && self.reflexive_equal_type_pack_id(
67                    (*af).ret_types,
68                    (*bf).ret_types,
69                    depth - 1,
70                );
71            }
72        }
73        false
74    }
75
76    pub(crate) fn reflexive_equal_type_pack_id(
77        &self,
78        a: TypePackId,
79        b: TypePackId,
80        depth: u32,
81    ) -> bool {
82        if depth == 0 {
83            return false;
84        }
85        let a = self.log.follow_type_pack_id(a);
86        let b = self.log.follow_type_pack_id(b);
87        if a == b {
88            return true;
89        }
90        unsafe {
91            let ap = self.log.txn_log_get::<TypePack, TypePackId>(a);
92            let bp = self.log.txn_log_get::<TypePack, TypePackId>(b);
93            if !ap.is_null() && !bp.is_null() {
94                let ah = &(*ap).head;
95                let bh = &(*bp).head;
96                if ah.len() != bh.len() {
97                    return false;
98                }
99                if !ah
100                    .iter()
101                    .zip(bh.iter())
102                    .all(|(x, y)| self.reflexive_equal_type_id(*x, *y, depth - 1))
103                {
104                    return false;
105                }
106                return match (&(*ap).tail, &(*bp).tail) {
107                    (None, None) => true,
108                    (Some(ta), Some(tb)) => self.reflexive_equal_type_pack_id(*ta, *tb, depth - 1),
109                    _ => false,
110                };
111            }
112        }
113        false
114    }
115}
luaur_analysis/methods/unifier_reflexive_equal.rs

luaur_analysis/methods/
unifier_reflexive_equal.rs
