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