Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : /*
4 : : subtyping predicate
5 : :
6 : : Uses the algorithm described in section 4.2.2 of https://github.com/JeffBezanson/phdthesis/
7 : : This code adds the following features to the core algorithm:
8 : :
9 : : - Type variables can be restricted to range over only concrete types.
10 : : This is done by returning false if such a variable's lower bound is not concrete.
11 : : - Diagonal rule: a type variable is concrete if it occurs more than once in
12 : : covariant position, and never in invariant position. This sounds like a syntactic
13 : : property, but actually isn't since it depends on which occurrences of a type
14 : : variable the algorithm actually uses.
15 : : - Unconstrained type vars (Bottom<:T<:Any) can match non-type values.
16 : : - Vararg types have an int-valued length parameter N (in `Vararg{T,N}`).
17 : : - Type{T}<:S if isa(T,S). Existing code assumes this, but it's not strictly
18 : : correct since a type can equal `T` without having the same representation.
19 : : - Free type variables are tolerated. This can hopefully be removed after a
20 : : deprecation period.
21 : : */
22 : : #include <stdlib.h>
23 : : #include <string.h>
24 : : #ifdef _OS_WINDOWS_
25 : : #include <malloc.h>
26 : : #endif
27 : : #include "julia.h"
28 : : #include "julia_internal.h"
29 : : #include "julia_assert.h"
30 : :
31 : : #ifdef __cplusplus
32 : : extern "C" {
33 : : #endif
34 : :
35 : : // stack of bits to keep track of which combination of Union components we are
36 : : // looking at (0 for Union.a, 1 for Union.b). forall_exists_subtype and
37 : : // exists_subtype loop over all combinations by updating a binary count in
38 : : // this structure.
39 : : // Union type decision points are discovered while the algorithm works.
40 : : // If a new Union decision is encountered, the `more` flag is set to tell
41 : : // the forall/exists loop to grow the stack.
42 : : // TODO: the stack probably needs to be artificially large because of some
43 : : // deeper problem (see #21191) and could be shrunk once that is fixed
44 : : typedef struct {
45 : : int16_t depth;
46 : : int16_t more;
47 : : int16_t used;
48 : : uint32_t stack[100]; // stack of bits represented as a bit vector
49 : : } jl_unionstate_t;
50 : :
51 : : typedef struct {
52 : : int16_t depth;
53 : : int16_t more;
54 : : int16_t used;
55 : : void *stack;
56 : : } jl_saved_unionstate_t;
57 : :
58 : : // Linked list storing the type variable environment. A new jl_varbinding_t
59 : : // is pushed for each UnionAll type we encounter. `lb` and `ub` are updated
60 : : // during the computation.
61 : : // Most of the complexity is due to the "diagonal rule", requiring us to
62 : : // identify which type vars range over only concrete types.
63 : : typedef struct jl_varbinding_t {
64 : : jl_tvar_t *var;
65 : : jl_value_t *lb;
66 : : jl_value_t *ub;
67 : : int8_t right; // whether this variable came from the right side of `A <: B`
68 : : int8_t occurs_inv; // occurs in invariant position
69 : : int8_t occurs_cov; // # of occurrences in covariant position
70 : : int8_t concrete; // 1 if another variable has a constraint forcing this one to be concrete
71 : : // constraintkind: in covariant position, we try three different ways to compute var ∩ type:
72 : : // let ub = var.ub ∩ type
73 : : // 0 - var.ub <: type ? var : ub
74 : : // 1 - var.ub = ub; return var
75 : : // 2 - either (var.ub = ub; return var), or return ub
76 : : int8_t constraintkind;
77 : : int8_t intvalued; // must be integer-valued; i.e. occurs as N in Vararg{_,N}
78 : : int8_t limited;
79 : : int16_t depth0; // # of invariant constructors nested around the UnionAll type for this var
80 : : // when this variable's integer value is compared to that of another,
81 : : // it equals `other + offset`. used by vararg length parameters.
82 : : int16_t offset;
83 : : // array of typevars that our bounds depend on, whose UnionAlls need to be
84 : : // moved outside ours.
85 : : jl_array_t *innervars;
86 : : struct jl_varbinding_t *prev;
87 : : } jl_varbinding_t;
88 : :
89 : : // subtype algorithm state
90 : : typedef struct jl_stenv_t {
91 : : // N.B.: varbindings are created on the stack and rooted there
92 : : jl_varbinding_t *vars; // type variable environment
93 : : jl_unionstate_t Lunions; // union state for unions on the left of A <: B
94 : : jl_unionstate_t Runions; // union state for unions on the right
95 : : // N.B.: envout is gc-rooted
96 : : jl_value_t **envout; // for passing caller the computed bounds of right-side variables
97 : : int envsz; // length of envout
98 : : int envidx; // current index in envout
99 : : int invdepth; // # of invariant constructors we're nested in on the left
100 : : int Rinvdepth; // # of invariant constructors we're nested in on the right
101 : : int ignore_free; // treat free vars as black boxes; used during intersection
102 : : int intersection; // true iff subtype is being called from intersection
103 : : int emptiness_only; // true iff intersection only needs to test for emptiness
104 : : int triangular; // when intersecting Ref{X} with Ref{<:Y}
105 : : } jl_stenv_t;
106 : :
107 : : // state manipulation utilities
108 : :
109 : : // look up a type variable in an environment
110 : : #ifdef __clang_gcanalyzer__
111 : : static jl_varbinding_t *lookup(jl_stenv_t *e, jl_tvar_t *v) JL_GLOBALLY_ROOTED JL_NOTSAFEPOINT;
112 : : #else
113 : 1505350000 : static jl_varbinding_t *lookup(jl_stenv_t *e, jl_tvar_t *v) JL_GLOBALLY_ROOTED JL_NOTSAFEPOINT
114 : : {
115 : 1505350000 : jl_varbinding_t *b = e->vars;
116 [ + + ]: 3631800000 : while (b != NULL) {
117 [ + + ]: 3604750000 : if (b->var == v) return b;
118 : 2126450000 : b = b->prev;
119 : : }
120 : 27052200 : return b;
121 : : }
122 : : #endif
123 : :
124 : 3220990000 : static int statestack_get(jl_unionstate_t *st, int i) JL_NOTSAFEPOINT
125 : : {
126 [ + - + - ]: 3220990000 : assert(i >= 0 && i < sizeof(st->stack) * 8);
127 : : // get the `i`th bit in an array of 32-bit words
128 : 3220990000 : return (st->stack[i>>5] & (1u<<(i&31))) != 0;
129 : : }
130 : :
131 : 1273830000 : static void statestack_set(jl_unionstate_t *st, int i, int val) JL_NOTSAFEPOINT
132 : : {
133 [ + - + - ]: 1273830000 : assert(i >= 0 && i < sizeof(st->stack) * 8);
134 [ + + ]: 1273830000 : if (val)
135 : 545021000 : st->stack[i>>5] |= (1u<<(i&31));
136 : : else
137 : 728810000 : st->stack[i>>5] &= ~(1u<<(i&31));
138 : 1273830000 : }
139 : :
140 : : #define push_unionstate(saved, src) \
141 : : do { \
142 : : (saved)->depth = (src)->depth; \
143 : : (saved)->more = (src)->more; \
144 : : (saved)->used = (src)->used; \
145 : : (saved)->stack = alloca(((src)->used+7)/8); \
146 : : memcpy((saved)->stack, &(src)->stack, ((src)->used+7)/8); \
147 : : } while (0);
148 : :
149 : : #define pop_unionstate(dst, saved) \
150 : : do { \
151 : : (dst)->depth = (saved)->depth; \
152 : : (dst)->more = (saved)->more; \
153 : : (dst)->used = (saved)->used; \
154 : : memcpy(&(dst)->stack, (saved)->stack, ((saved)->used+7)/8); \
155 : : } while (0);
156 : :
157 : : typedef struct {
158 : : int8_t *buf;
159 : : int rdepth;
160 : : int8_t _space[16];
161 : : } jl_savedenv_t;
162 : :
163 : 2935780000 : static void save_env(jl_stenv_t *e, jl_value_t **root, jl_savedenv_t *se)
164 : : {
165 : 2935780000 : jl_varbinding_t *v = e->vars;
166 : 2935780000 : int len=0;
167 [ + + ]: 4967030000 : while (v != NULL) {
168 : 2031250000 : len++;
169 : 2031250000 : v = v->prev;
170 : : }
171 [ + + ]: 2935780000 : if (root)
172 : 2901530000 : *root = (jl_value_t*)jl_alloc_svec(len * 3);
173 [ + + ]: 2935780000 : se->buf = (int8_t*)(len > 8 ? malloc_s(len * 2) : &se->_space);
174 : : #ifdef __clang_gcanalyzer__
175 : : memset(se->buf, 0, len * 2);
176 : : #endif
177 : 2935780000 : int i=0, j=0; v = e->vars;
178 [ + + ]: 4967030000 : while (v != NULL) {
179 [ + + ]: 2031250000 : if (root) {
180 : 1976010000 : jl_svecset(*root, i++, v->lb);
181 : 1976010000 : jl_svecset(*root, i++, v->ub);
182 : 1976010000 : jl_svecset(*root, i++, (jl_value_t*)v->innervars);
183 : : }
184 : 2031250000 : se->buf[j++] = v->occurs_inv;
185 : 2031250000 : se->buf[j++] = v->occurs_cov;
186 : 2031250000 : v = v->prev;
187 : : }
188 : 2935780000 : se->rdepth = e->Runions.depth;
189 : 2935780000 : }
190 : :
191 : 2935780000 : static void free_env(jl_savedenv_t *se) JL_NOTSAFEPOINT
192 : : {
193 [ + + ]: 2935780000 : if (se->buf != se->_space)
194 : 17213300 : free(se->buf);
195 : 2935780000 : se->buf = NULL;
196 : 2935780000 : }
197 : :
198 : 2533950000 : static void restore_env(jl_stenv_t *e, jl_value_t *root, jl_savedenv_t *se) JL_NOTSAFEPOINT
199 : : {
200 : 2533950000 : jl_varbinding_t *v = e->vars;
201 : 2533950000 : int i = 0, j = 0;
202 [ + + ]: 3362990000 : while (v != NULL) {
203 [ + + ]: 829043000 : if (root) v->lb = jl_svecref(root, i);
204 : 829043000 : i++;
205 [ + + ]: 829043000 : if (root) v->ub = jl_svecref(root, i);
206 : 829043000 : i++;
207 [ + + ]: 829043000 : if (root) v->innervars = (jl_array_t*)jl_svecref(root, i);
208 : 829043000 : i++;
209 : 829043000 : v->occurs_inv = se->buf[j++];
210 : 829043000 : v->occurs_cov = se->buf[j++];
211 : 829043000 : v = v->prev;
212 : : }
213 : 2533950000 : e->Runions.depth = se->rdepth;
214 [ + + + + ]: 2533950000 : if (e->envout && e->envidx < e->envsz)
215 : 16910700 : memset(&e->envout[e->envidx], 0, (e->envsz - e->envidx)*sizeof(void*));
216 : 2533950000 : }
217 : :
218 : : // type utilities
219 : :
220 : : // quickly test that two types are identical
221 : 1165580000 : static int obviously_egal(jl_value_t *a, jl_value_t *b)
222 : : {
223 [ + + ]: 1165580000 : if (a == (jl_value_t*)jl_typeofbottom_type->super)
224 : 186 : a = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
225 [ + + ]: 1165580000 : if (b == (jl_value_t*)jl_typeofbottom_type->super)
226 : 3622 : b = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
227 [ + + ]: 1165580000 : if (a == b) return 1;
228 [ + + ]: 1045330000 : if (jl_typeof(a) != jl_typeof(b)) return 0;
229 [ + + ]: 439368000 : if (jl_is_datatype(a)) {
230 : 168640000 : jl_datatype_t *ad = (jl_datatype_t*)a;
231 : 168640000 : jl_datatype_t *bd = (jl_datatype_t*)b;
232 [ + + ]: 168640000 : if (ad->name != bd->name) return 0;
233 [ + + + + ]: 32309000 : if (ad->isconcretetype || bd->isconcretetype) return 0;
234 : 21483600 : size_t i, np = jl_nparams(ad);
235 [ + + ]: 21483600 : if (np != jl_nparams(bd)) return 0;
236 [ + + ]: 20653500 : for (i = 0; i < np; i++) {
237 [ + + ]: 20522200 : if (!obviously_egal(jl_tparam(ad,i), jl_tparam(bd,i)))
238 : 20234200 : return 0;
239 : : }
240 : 131310 : return 1;
241 : : }
242 [ + + ]: 270728000 : if (jl_is_uniontype(a)) {
243 [ + + + + ]: 14028100 : return obviously_egal(((jl_uniontype_t*)a)->a, ((jl_uniontype_t*)b)->a) &&
244 : 4191500 : obviously_egal(((jl_uniontype_t*)a)->b, ((jl_uniontype_t*)b)->b);
245 : : }
246 [ + + ]: 260891000 : if (jl_is_unionall(a)) {
247 [ + + + + ]: 29449600 : return ((jl_unionall_t*)a)->var == ((jl_unionall_t*)b)->var &&
248 : 10713200 : obviously_egal(((jl_unionall_t*)a)->body, ((jl_unionall_t*)b)->body);
249 : : }
250 [ + + ]: 242155000 : if (jl_is_vararg(a)) {
251 : 407668 : jl_vararg_t *vma = (jl_vararg_t *)a;
252 : 407668 : jl_vararg_t *vmb = (jl_vararg_t *)b;
253 [ + + ]: 563601 : return obviously_egal(jl_unwrap_vararg(vma), jl_unwrap_vararg(vmb)) &&
254 [ + + + + : 155933 : ((!vma->N && !vmb->N) || (vma->N && vmb->N && obviously_egal(vma->N, vmb->N)));
+ + + + +
+ ]
255 : : }
256 [ + + ]: 241747000 : if (jl_is_typevar(a)) return 0;
257 [ + - + + ]: 101430000 : return !jl_is_type(a) && jl_egal(a,b);
258 : : }
259 : :
260 : 9307380000 : static int obviously_unequal(jl_value_t *a, jl_value_t *b)
261 : : {
262 [ + + ]: 9307380000 : if (a == (jl_value_t*)jl_typeofbottom_type->super)
263 : 259346 : a = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
264 [ + + ]: 9307380000 : if (b == (jl_value_t*)jl_typeofbottom_type->super)
265 : 368029 : b = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
266 [ + + ]: 9307380000 : if (a == b)
267 : 2176890000 : return 0;
268 [ + + ]: 7130500000 : if (jl_is_unionall(a))
269 : 819013000 : a = jl_unwrap_unionall(a);
270 [ + + ]: 7130500000 : if (jl_is_unionall(b))
271 : 858915000 : b = jl_unwrap_unionall(b);
272 [ + + ]: 7130500000 : if (jl_is_datatype(a)) {
273 [ + + ]: 6917510000 : if (b == jl_bottom_type)
274 : 413706 : return 1;
275 [ + + ]: 6917090000 : if (jl_is_datatype(b)) {
276 : 6861330000 : jl_datatype_t *ad = (jl_datatype_t*)a;
277 : 6861330000 : jl_datatype_t *bd = (jl_datatype_t*)b;
278 [ + + + + ]: 6861330000 : if (a == (jl_value_t*)jl_typeofbottom_type && bd->name == jl_type_typename)
279 : 276080 : return obviously_unequal(jl_bottom_type, jl_tparam(bd, 0));
280 [ + + + + ]: 6861050000 : if (ad->name == jl_type_typename && b == (jl_value_t*)jl_typeofbottom_type)
281 : 346374 : return obviously_unequal(jl_tparam(ad, 0), jl_bottom_type);
282 [ + + ]: 6860710000 : if (ad->name != bd->name)
283 : 1642880000 : return 1;
284 : 5217820000 : int istuple = (ad->name == jl_tuple_typename);
285 [ + + + + : 7359110000 : if ((jl_is_concrete_type(a) || jl_is_concrete_type(b)) &&
+ + ]
286 : 2141290000 : jl_type_equality_is_identity(a, b)) {
287 [ + + + - ]: 2105580000 : if (!istuple && ad->name != jl_type_typename) // HACK: can't properly normalize Tuple{Float64} == Tuple{<:Float64} like types or Type{T} types
288 : 838977000 : return 1;
289 : : }
290 : : size_t i, np;
291 [ + + ]: 4378850000 : if (istuple) {
292 : 2884440000 : size_t na = jl_nparams(ad), nb = jl_nparams(bd);
293 [ + + ]: 2884440000 : if (jl_is_va_tuple(ad)) {
294 : 75725600 : na -= 1;
295 [ + + ]: 75725600 : if (jl_is_va_tuple(bd))
296 : 55759000 : nb -= 1;
297 : : }
298 [ + + ]: 2808720000 : else if (jl_is_va_tuple(bd)) {
299 : 27852100 : nb -= 1;
300 : : }
301 [ + + ]: 2780870000 : else if (na != nb) {
302 : 236041000 : return 1;
303 : : }
304 : 2648400000 : np = na < nb ? na : nb;
305 : : }
306 : : else {
307 : 1494400000 : np = jl_nparams(ad);
308 [ - + ]: 1494400000 : if (np != jl_nparams(bd))
309 : 0 : return 1;
310 : : }
311 [ + + ]: 6768780000 : for (i = 0; i < np; i++) {
312 [ + + ]: 6450180000 : if (obviously_unequal(jl_tparam(ad, i), jl_tparam(bd, i)))
313 : 3824200000 : return 1;
314 : : }
315 : : }
316 : : }
317 [ + + + + ]: 212990000 : else if (a == jl_bottom_type && jl_is_datatype(b)) {
318 : 119161 : return 1;
319 : : }
320 [ + + + + : 587236000 : if (jl_is_typevar(a) && jl_is_typevar(b) && obviously_unequal(((jl_tvar_t*)a)->ub, ((jl_tvar_t*)b)->ub))
+ + ]
321 : 7620100 : return 1;
322 [ + + ]: 579616000 : if (jl_is_long(a)) {
323 [ + + + - ]: 3373330 : if (jl_is_long(b) && jl_unbox_long(a) != jl_unbox_long(b))
324 : 2373490 : return 1;
325 : : }
326 [ + + ]: 576243000 : else if (jl_is_long(b)) {
327 : 834587 : return 1;
328 : : }
329 [ + + + + : 576408000 : if ((jl_is_symbol(a) || jl_is_symbol(b)) && a != b)
+ - ]
330 : 4897 : return 1;
331 : 576403000 : return 0;
332 : : }
333 : :
334 : 829283 : int jl_obviously_unequal(jl_value_t *a, jl_value_t *b)
335 : : {
336 : 829283 : return obviously_unequal(a, b);
337 : : }
338 : :
339 : 410811000 : static int in_union(jl_value_t *u, jl_value_t *x) JL_NOTSAFEPOINT
340 : : {
341 [ + + ]: 410811000 : if (u == x) return 1;
342 [ + + ]: 311590000 : if (!jl_is_uniontype(u)) return 0;
343 [ + + + + ]: 102823000 : return in_union(((jl_uniontype_t*)u)->a, x) || in_union(((jl_uniontype_t*)u)->b, x);
344 : : }
345 : :
346 : 918688000 : static int obviously_disjoint(jl_value_t *a, jl_value_t *b, int specificity)
347 : : {
348 [ + + + + : 918688000 : if (a == b || a == (jl_value_t*)jl_any_type || b == (jl_value_t*)jl_any_type)
+ + ]
349 : 329497000 : return 0;
350 [ + + + + ]: 589191000 : if (specificity && a == (jl_value_t*)jl_typeofbottom_type)
351 : 6604 : return 0;
352 [ + + + + : 654654000 : if (jl_is_concrete_type(a) && jl_is_concrete_type(b) &&
+ + ]
353 : 65469900 : jl_type_equality_is_identity(a, b) &&
354 [ + + ]: 65402600 : (((jl_datatype_t*)a)->name != jl_tuple_typename ||
355 [ + + ]: 12183900 : ((jl_datatype_t*)b)->name != jl_tuple_typename))
356 : 54072400 : return 1;
357 [ + + ]: 535112000 : if (jl_is_unionall(a)) a = jl_unwrap_unionall(a);
358 [ + + ]: 535112000 : if (jl_is_unionall(b)) b = jl_unwrap_unionall(b);
359 [ + + + + ]: 642204000 : if (jl_is_datatype(a) && jl_is_datatype(b)) {
360 : 494930000 : jl_datatype_t *ad = (jl_datatype_t*)a, *bd = (jl_datatype_t*)b;
361 [ + + ]: 494930000 : if (ad->name != bd->name) {
362 : 155477000 : jl_datatype_t *temp = ad;
363 [ + + + + ]: 479489000 : while (temp != jl_any_type && temp->name != bd->name)
364 : 324012000 : temp = temp->super;
365 [ + + ]: 155477000 : if (temp == jl_any_type) {
366 : 145787000 : temp = bd;
367 [ + + + + ]: 427551000 : while (temp != jl_any_type && temp->name != ad->name)
368 : 281764000 : temp = temp->super;
369 [ + + ]: 145787000 : if (temp == jl_any_type)
370 : 136891000 : return 1;
371 : 8895620 : bd = temp;
372 : : }
373 : : else {
374 : 9690100 : ad = temp;
375 : : }
376 [ + + ]: 18585700 : if (specificity) {
377 : : // account for declared subtypes taking priority (issue #21710)
378 : 5182330 : return 0;
379 : : }
380 : : }
381 : 352857000 : int istuple = (ad->name == jl_tuple_typename);
382 : : size_t np;
383 [ + + ]: 352857000 : if (istuple) {
384 : 263730000 : size_t na = jl_nparams(ad), nb = jl_nparams(bd);
385 [ + + ]: 263730000 : if (jl_is_va_tuple(ad)) {
386 : 16325200 : na -= 1;
387 [ + + ]: 16325200 : if (jl_is_va_tuple(bd))
388 : 4151900 : nb -= 1;
389 : : }
390 [ + + ]: 247404000 : else if (jl_is_va_tuple(bd)) {
391 : 12137700 : nb -= 1;
392 : : }
393 [ + + + + ]: 235267000 : else if (!specificity && na != nb) {
394 : : // note: some disjoint types (e.g. tuples of different lengths) can be more specific
395 : 19198700 : return 1;
396 : : }
397 : 244531000 : np = na < nb ? na : nb;
398 : : }
399 : : else {
400 : 89127300 : np = jl_nparams(ad);
401 : : }
402 : : size_t i;
403 [ + + ]: 772315000 : for (i = 0; i < np; i++) {
404 : 665223000 : jl_value_t *ai = jl_tparam(ad, i);
405 : 665223000 : jl_value_t *bi = jl_tparam(bd, i);
406 [ + + + + ]: 665223000 : if (jl_is_typevar(ai) || jl_is_typevar(bi))
407 : 59605200 : continue; // it's possible that Union{} is in this intersection
408 [ + + ]: 605618000 : if (jl_is_type(ai)) {
409 [ + + ]: 602216000 : if (jl_is_type(bi)) {
410 [ + + + + : 602216000 : if (istuple && (ai == jl_bottom_type || bi == jl_bottom_type))
+ + ]
411 : : ; // TODO: this can return 1 if and when Tuple{Union{}} === Union{}
412 [ + + ]: 602214000 : else if (obviously_disjoint(ai, bi, specificity))
413 : 225634000 : return 1;
414 : : }
415 [ - + ]: 131 : else if (ai != (jl_value_t*)jl_any_type) {
416 : 0 : return 1;
417 : : }
418 : : }
419 [ + + ]: 3402060 : else if (jl_is_type(bi)) {
420 [ - + ]: 1237 : if (bi != (jl_value_t*)jl_any_type)
421 : 0 : return 1;
422 : : }
423 [ + + ]: 3400820 : else if (!jl_egal(ai, bi)) {
424 : 932031 : return 1;
425 : : }
426 : : }
427 : : }
428 [ + + + + ]: 40181300 : else if (a == jl_bottom_type || b == jl_bottom_type) {
429 : 532404 : return 1;
430 : : }
431 : 146741000 : return 0;
432 : : }
433 : :
434 : : // compute a least upper bound of `a` and `b`
435 : 259772000 : static jl_value_t *simple_join(jl_value_t *a, jl_value_t *b)
436 : : {
437 [ + + + + : 259772000 : if (a == jl_bottom_type || b == (jl_value_t*)jl_any_type || obviously_egal(a,b))
+ + ]
438 : 236415000 : return b;
439 [ + + + + ]: 23357300 : if (b == jl_bottom_type || a == (jl_value_t*)jl_any_type)
440 : 8207030 : return a;
441 [ + + + + : 15150200 : if (!(jl_is_type(a) || jl_is_typevar(a)) || !(jl_is_type(b) || jl_is_typevar(b)))
+ + + + ]
442 : 7 : return (jl_value_t*)jl_any_type;
443 [ + + + + ]: 15150200 : if (jl_is_uniontype(a) && in_union(a, b))
444 : 5113370 : return a;
445 [ + + + + ]: 10036900 : if (jl_is_uniontype(b) && in_union(b, a))
446 : 81076 : return b;
447 [ + + + + : 9955780 : if (jl_is_kind(a) && jl_is_type_type(b) && jl_typeof(jl_tparam0(b)) == a)
+ - ]
448 : 1235 : return a;
449 [ + + + + : 9954550 : if (jl_is_kind(b) && jl_is_type_type(a) && jl_typeof(jl_tparam0(a)) == b)
+ - ]
450 : 130 : return b;
451 [ + + + + ]: 9954420 : if (jl_is_typevar(a) && obviously_egal(b, ((jl_tvar_t*)a)->lb))
452 : 553 : return a;
453 [ + + + + ]: 9953870 : if (jl_is_typevar(b) && obviously_egal(a, ((jl_tvar_t*)b)->lb))
454 : 484202 : return b;
455 [ + + + + : 12817000 : if (!jl_has_free_typevars(a) && !jl_has_free_typevars(b) &&
+ + ]
456 : : // issue #24521: don't merge Type{T} where typeof(T) varies
457 [ + + + + ]: 3347540 : !(jl_is_type_type(a) && jl_is_type_type(b) && jl_typeof(jl_tparam0(a)) != jl_typeof(jl_tparam0(b)))) {
458 [ + + ]: 3347340 : if (jl_subtype(a, b)) return b;
459 [ + + ]: 3196330 : if (jl_subtype(b, a)) return a;
460 : : }
461 : 9198850 : return jl_new_struct(jl_uniontype_type, a, b);
462 : : }
463 : :
464 : : // compute a greatest lower bound of `a` and `b`
465 : : // in many cases, we need to over-estimate this by returning `b`.
466 : 167669000 : static jl_value_t *simple_meet(jl_value_t *a, jl_value_t *b)
467 : : {
468 [ + + + + : 167669000 : if (a == (jl_value_t*)jl_any_type || b == jl_bottom_type || obviously_egal(a,b))
+ + ]
469 : 125761000 : return b;
470 [ + + + + ]: 41908000 : if (b == (jl_value_t*)jl_any_type || a == jl_bottom_type)
471 : 371 : return a;
472 [ + + + - : 41907600 : if (!(jl_is_type(a) || jl_is_typevar(a)) || !(jl_is_type(b) || jl_is_typevar(b)))
+ + + + ]
473 : 5540 : return jl_bottom_type;
474 [ + + + + ]: 41902100 : if (jl_is_uniontype(a) && in_union(a, b))
475 : 3373700 : return b;
476 [ + + - + ]: 38528400 : if (jl_is_uniontype(b) && in_union(b, a))
477 : 0 : return a;
478 [ + + - + : 38528400 : if (jl_is_kind(a) && jl_is_type_type(b) && jl_typeof(jl_tparam0(b)) == a)
- - ]
479 : 0 : return b;
480 [ + + - + : 38528400 : if (jl_is_kind(b) && jl_is_type_type(a) && jl_typeof(jl_tparam0(a)) == b)
- - ]
481 : 0 : return a;
482 [ + + + + ]: 38528400 : if (jl_is_typevar(a) && obviously_egal(b, ((jl_tvar_t*)a)->ub))
483 : 6 : return a;
484 [ + + + + ]: 38528400 : if (jl_is_typevar(b) && obviously_egal(a, ((jl_tvar_t*)b)->ub))
485 : 14415400 : return b;
486 [ - + ]: 24113000 : if (obviously_disjoint(a, b, 0))
487 : 0 : return jl_bottom_type;
488 [ + + + + ]: 24113000 : if (!jl_has_free_typevars(a) && !jl_has_free_typevars(b)) {
489 [ + + ]: 9021610 : if (jl_subtype(a, b)) return a;
490 [ + - ]: 9014540 : if (jl_subtype(b, a)) return b;
491 : : }
492 : 15091400 : return b;
493 : : }
494 : :
495 : 104961000 : static jl_unionall_t *rename_unionall(jl_unionall_t *u)
496 : : {
497 : 104961000 : jl_tvar_t *v = jl_new_typevar(u->var->name, u->var->lb, u->var->ub);
498 : 104961000 : jl_value_t *t = NULL;
499 : 104961000 : JL_GC_PUSH2(&v, &t);
500 : 104961000 : t = jl_instantiate_unionall(u, (jl_value_t*)v);
501 : 104961000 : t = jl_new_struct(jl_unionall_type, v, t);
502 : 104961000 : JL_GC_POP();
503 : 104961000 : return (jl_unionall_t*)t;
504 : : }
505 : :
506 : : // main subtyping algorithm
507 : :
508 : : static int subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param);
509 : :
510 : 1138440000 : static jl_value_t *pick_union_element(jl_value_t *u JL_PROPAGATES_ROOT, jl_stenv_t *e, int8_t R) JL_NOTSAFEPOINT
511 : : {
512 [ + + ]: 1138440000 : jl_unionstate_t *state = R ? &e->Runions : &e->Lunions;
513 : : do {
514 [ + + ]: 3174940000 : if (state->depth >= state->used) {
515 : 669163000 : statestack_set(state, state->used, 0);
516 : 669163000 : state->used++;
517 : : }
518 : 3174940000 : int ui = statestack_get(state, state->depth);
519 : 3174940000 : state->depth++;
520 [ + + ]: 3174940000 : if (ui == 0) {
521 : 916834000 : state->more = state->depth; // memorize that this was the deepest available choice
522 : 916834000 : u = ((jl_uniontype_t*)u)->a;
523 : : }
524 : : else {
525 : 2258110000 : u = ((jl_uniontype_t*)u)->b;
526 : : }
527 [ + + ]: 3174940000 : } while (jl_is_uniontype(u));
528 : 1138440000 : return u;
529 : : }
530 : :
531 : : static int forall_exists_subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param);
532 : :
533 : : // subtype for variable bounds consistency check. needs its own forall/exists environment.
534 : 414763000 : static int subtype_ccheck(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
535 : : {
536 [ + + ]: 414763000 : if (x == y)
537 : 199735000 : return 1;
538 [ + + + + ]: 215028000 : if (x == jl_bottom_type && jl_is_type(y))
539 : 3648060 : return 1;
540 [ + + + + ]: 211380000 : if (y == (jl_value_t*)jl_any_type && jl_is_type(x))
541 : 44345400 : return 1;
542 [ + + + + ]: 167035000 : if (jl_is_uniontype(x) && jl_egal(x, y))
543 : 317858 : return 1;
544 [ + + + + ]: 166717000 : if (x == (jl_value_t*)jl_any_type && jl_is_datatype(y))
545 : 734924 : return 0;
546 : 165982000 : jl_saved_unionstate_t oldLunions; push_unionstate(&oldLunions, &e->Lunions);
547 : 165982000 : jl_saved_unionstate_t oldRunions; push_unionstate(&oldRunions, &e->Runions);
548 : : int sub;
549 : 165982000 : e->Lunions.used = e->Runions.used = 0;
550 : 165982000 : e->Runions.depth = 0;
551 : 165982000 : e->Runions.more = 0;
552 : 165982000 : e->Lunions.depth = 0;
553 : 165982000 : e->Lunions.more = 0;
554 : :
555 : 165982000 : sub = forall_exists_subtype(x, y, e, 0);
556 : :
557 : 165982000 : pop_unionstate(&e->Runions, &oldRunions);
558 : 165982000 : pop_unionstate(&e->Lunions, &oldLunions);
559 : 165982000 : return sub;
560 : : }
561 : :
562 : 238926000 : static int subtype_left_var(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param)
563 : : {
564 [ + + ]: 238926000 : if (x == y)
565 : 68197300 : return 1;
566 [ + + + + ]: 170729000 : if (x == jl_bottom_type && jl_is_type(y))
567 : 1427 : return 1;
568 [ + + + + ]: 170727000 : if (y == (jl_value_t*)jl_any_type && jl_is_type(x))
569 : 18580900 : return 1;
570 [ + + + + ]: 152146000 : if (jl_is_uniontype(x) && jl_egal(x, y))
571 : 152045 : return 1;
572 [ + + + + ]: 151994000 : if (x == (jl_value_t*)jl_any_type && jl_is_datatype(y))
573 : 21824000 : return 0;
574 : 130170000 : return subtype(x, y, e, param);
575 : : }
576 : :
577 : : // use the current context to record where a variable occurred, for the purpose
578 : : // of determining whether the variable is concrete.
579 : 981843000 : static void record_var_occurrence(jl_varbinding_t *vb, jl_stenv_t *e, int param) JL_NOTSAFEPOINT
580 : : {
581 [ + + + + ]: 981843000 : if (vb != NULL && param) {
582 : : // saturate counters at 2; we don't need values bigger than that
583 [ + + + + : 503453000 : if (param == 2 && (vb->right ? e->Rinvdepth : e->invdepth) > vb->depth0) {
+ + ]
584 [ + + ]: 454615000 : if (vb->occurs_inv < 2)
585 : 435259000 : vb->occurs_inv++;
586 : : }
587 [ + + ]: 48837100 : else if (vb->occurs_cov < 2) {
588 : 47538600 : vb->occurs_cov++;
589 : : }
590 : : }
591 : 981843000 : }
592 : :
593 : : // is var x's quantifier outside y's in nesting order
594 : 26198800 : static int var_outside(jl_stenv_t *e, jl_tvar_t *x, jl_tvar_t *y)
595 : : {
596 : 26198800 : jl_varbinding_t *btemp = e->vars;
597 [ + - ]: 46753800 : while (btemp != NULL) {
598 [ + + ]: 46753800 : if (btemp->var == x) return 0;
599 [ + + ]: 34738400 : if (btemp->var == y) return 1;
600 : 20555000 : btemp = btemp->prev;
601 : : }
602 : 0 : return 0;
603 : : }
604 : :
605 : : static jl_value_t *intersect_aside(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int R, int d);
606 : :
607 : : // check that type var `b` is <: `a`, and update b's upper bound.
608 : 435730000 : static int var_lt(jl_tvar_t *b, jl_value_t *a, jl_stenv_t *e, int param)
609 : : {
610 : 435730000 : jl_varbinding_t *bb = lookup(e, b);
611 [ + + ]: 435730000 : if (bb == NULL)
612 [ + + + + ]: 4362730 : return e->ignore_free || subtype_left_var(b->ub, a, e, param);
613 : 431367000 : record_var_occurrence(bb, e, param);
614 [ + + ]: 431367000 : if (!bb->right) // check ∀b . b<:a
615 : 225636000 : return subtype_left_var(bb->ub, a, e, param);
616 [ + + ]: 205731000 : if (bb->ub == a)
617 : 28982100 : return 1;
618 [ + + - + : 176749000 : if (!((bb->lb == jl_bottom_type && !jl_is_type(a) && !jl_is_typevar(a)) || subtype_ccheck(bb->lb, a, e)))
- - + + ]
619 : 7043960 : return 0;
620 : : // for this to work we need to compute issub(left,right) before issub(right,left),
621 : : // since otherwise the issub(a, bb.ub) check in var_gt becomes vacuous.
622 [ + + ]: 169705000 : if (e->intersection) {
623 : 2035480 : jl_value_t *ub = intersect_aside(bb->ub, a, e, 0, bb->depth0);
624 [ + - ]: 2035480 : if (ub != (jl_value_t*)b)
625 : 2035480 : bb->ub = ub;
626 : : }
627 : : else {
628 : 167669000 : bb->ub = simple_meet(bb->ub, a);
629 : : }
630 [ - + ]: 169705000 : assert(bb->ub != (jl_value_t*)b);
631 [ + + ]: 169705000 : if (jl_is_typevar(a)) {
632 : 94681200 : jl_varbinding_t *aa = lookup(e, (jl_tvar_t*)a);
633 [ + + + - : 94681200 : if (aa && !aa->right && in_union(bb->lb, a) && bb->depth0 != aa->depth0 && var_outside(e, b, (jl_tvar_t*)a)) {
+ - + + +
+ ]
634 : : // an "exists" var cannot equal a "forall" var inside it unless the forall
635 : : // var has equal bounds.
636 : 12 : return subtype_left_var(aa->ub, aa->lb, e, param);
637 : : }
638 : : }
639 : 169705000 : return 1;
640 : : }
641 : :
642 : : static int subtype_by_bounds(jl_value_t *x, jl_value_t *y, jl_stenv_t *e) JL_NOTSAFEPOINT;
643 : :
644 : : // check that type var `b` is >: `a`, and update b's lower bound.
645 : 269632000 : static int var_gt(jl_tvar_t *b, jl_value_t *a, jl_stenv_t *e, int param)
646 : : {
647 : 269632000 : jl_varbinding_t *bb = lookup(e, b);
648 [ + + ]: 269632000 : if (bb == NULL)
649 [ + + + + ]: 2953910 : return e->ignore_free || subtype_left_var(a, b->lb, e, param);
650 : 266678000 : record_var_occurrence(bb, e, param);
651 [ + + ]: 266678000 : if (!bb->right) // check ∀b . b>:a
652 : 8161240 : return subtype_left_var(a, bb->lb, e, param);
653 [ + + ]: 258517000 : if (bb->lb == bb->ub) {
654 [ + + + + : 33923200 : if (jl_is_typevar(bb->lb) && !jl_is_type(a) && !jl_is_typevar(a))
+ + ]
655 : 200675 : return var_gt((jl_tvar_t*)bb->lb, a, e, param);
656 [ + + + + : 33722500 : if (jl_is_typevar(a) && !jl_is_type(bb->lb) && !jl_is_typevar(bb->lb))
+ + ]
657 : 7650 : return var_lt((jl_tvar_t*)a, bb->lb, e, param);
658 : : }
659 [ + + + + : 258308000 : if (!((bb->ub == (jl_value_t*)jl_any_type && !jl_is_type(a) && !jl_is_typevar(a)) || subtype_ccheck(a, bb->ub, e)))
+ + + + ]
660 : 38237900 : return 0;
661 : 220070000 : jl_value_t *lb = simple_join(bb->lb, a);
662 [ + + + + ]: 220070000 : if (!e->intersection || !subtype_by_bounds(lb, (jl_value_t*)b, e))
663 : 220063000 : bb->lb = lb;
664 : : // this bound should not be directly circular
665 [ - + ]: 220070000 : assert(bb->lb != (jl_value_t*)b);
666 [ + + ]: 220070000 : if (jl_is_typevar(a)) {
667 : 113083000 : jl_varbinding_t *aa = lookup(e, (jl_tvar_t*)a);
668 [ + + + - : 113083000 : if (aa && !aa->right && bb->depth0 != aa->depth0 && param == 2 && var_outside(e, b, (jl_tvar_t*)a))
+ + + + +
+ ]
669 : 800694 : return subtype_left_var(aa->ub, aa->lb, e, param);
670 : : }
671 : 219270000 : return 1;
672 : : }
673 : :
674 : : // check that a type is concrete or quasi-concrete (Type{T}).
675 : : // this is used to check concrete typevars:
676 : : // issubtype is false if the lower bound of a concrete type var is not concrete.
677 : 39153300 : static int is_leaf_bound(jl_value_t *v) JL_NOTSAFEPOINT
678 : : {
679 [ + + ]: 39153300 : if (v == jl_bottom_type)
680 : 19446500 : return 1;
681 [ + + ]: 19706800 : if (jl_is_datatype(v)) {
682 [ + + ]: 12214300 : if (((jl_datatype_t*)v)->name->abstract) {
683 [ + + ]: 8057400 : if (jl_is_type_type(v))
684 : 1863 : return 1;//!jl_has_free_typevars(jl_tparam0(v));
685 : 8055540 : return 0;
686 : : }
687 : 4156880 : return ((jl_datatype_t*)v)->isconcretetype;
688 : : }
689 [ + + + + ]: 7492470 : return !jl_is_type(v) && !jl_is_typevar(v);
690 : : }
691 : :
692 : 10668100 : static int is_leaf_typevar(jl_tvar_t *v) JL_NOTSAFEPOINT
693 : : {
694 : 10668100 : return is_leaf_bound(v->lb);
695 : : }
696 : :
697 : 397864000 : static jl_value_t *widen_Type(jl_value_t *t JL_PROPAGATES_ROOT) JL_NOTSAFEPOINT
698 : : {
699 [ + + + + ]: 397864000 : if (jl_is_type_type(t) && !jl_is_typevar(jl_tparam0(t)))
700 : 22741 : return jl_typeof(jl_tparam0(t));
701 [ + + ]: 397841000 : if (jl_is_uniontype(t)) {
702 : 587811 : jl_value_t *a = widen_Type(((jl_uniontype_t*)t)->a);
703 : 587811 : jl_value_t *b = widen_Type(((jl_uniontype_t*)t)->b);
704 [ + + ]: 587811 : if (a == b)
705 : 453 : return a;
706 : : }
707 : 397841000 : return t;
708 : : }
709 : :
710 : : // convert a type with free variables to a typevar bounded by a UnionAll-wrapped
711 : : // version of that type.
712 : : // TODO: This loses some inference precision. For example in a case where a
713 : : // variable bound is `Vector{_}`, we could potentially infer `Type{Vector{_}} where _`,
714 : : // but this causes us to infer the larger `Type{T} where T<:Vector` instead.
715 : : // However this is needed because many contexts check `isa(sp, TypeVar)` to determine
716 : : // when a static parameter value is not known exactly.
717 : 29039900 : static jl_value_t *fix_inferred_var_bound(jl_tvar_t *var, jl_value_t *ty JL_MAYBE_UNROOTED)
718 : : {
719 [ + + + + ]: 29039900 : if (!jl_is_typevar(ty) && jl_has_free_typevars(ty)) {
720 : 1762590 : jl_value_t *ans = ty;
721 : 1762590 : jl_array_t *vs = NULL;
722 : 1762590 : JL_GC_PUSH2(&ans, &vs);
723 : 1762590 : vs = jl_find_free_typevars(ty);
724 : : int i;
725 [ + + ]: 3698640 : for (i = 0; i < jl_array_len(vs); i++) {
726 : 1936040 : ans = jl_type_unionall((jl_tvar_t*)jl_array_ptr_ref(vs, i), ans);
727 : : }
728 : 1762590 : ans = (jl_value_t*)jl_new_typevar(var->name, jl_bottom_type, ans);
729 : 1762590 : JL_GC_POP();
730 : 1762590 : return ans;
731 : : }
732 : 27277300 : return ty;
733 : : }
734 : :
735 : : static int var_occurs_inside(jl_value_t *v, jl_tvar_t *var, int inside, int want_inv) JL_NOTSAFEPOINT;
736 : :
737 : : typedef int (*tvar_callback)(void*, int8_t, jl_stenv_t *, int);
738 : :
739 : 13094300 : static int var_occurs_invariant(jl_value_t *v, jl_tvar_t *var, int inv) JL_NOTSAFEPOINT
740 : : {
741 : 13094300 : return var_occurs_inside(v, var, 0, 1);
742 : : }
743 : :
744 : 1299150000 : static jl_unionall_t *unalias_unionall(jl_unionall_t *u, jl_stenv_t *e)
745 : : {
746 : 1299150000 : jl_varbinding_t *btemp = e->vars;
747 : : // if the var for this unionall (based on identity) already appears somewhere
748 : : // in the environment, rename to get a fresh var.
749 : 1299150000 : JL_GC_PUSH1(&u);
750 [ + + ]: 2577840000 : while (btemp != NULL) {
751 [ + + ]: 1377610000 : if (btemp->var == u->var ||
752 : : // outer var can only refer to inner var if bounds changed
753 [ + + + + ]: 1278730000 : (btemp->lb != btemp->var->lb && jl_has_typevar(btemp->lb, u->var)) ||
754 [ + + - + ]: 1278690000 : (btemp->ub != btemp->var->ub && jl_has_typevar(btemp->ub, u->var))) {
755 : 98923700 : u = rename_unionall(u);
756 : 98923700 : break;
757 : : }
758 : 1278690000 : btemp = btemp->prev;
759 : : }
760 : 1299150000 : JL_GC_POP();
761 : 1299150000 : return u;
762 : : }
763 : :
764 : 1299150000 : static int subtype_unionall(jl_value_t *t, jl_unionall_t *u, jl_stenv_t *e, int8_t R, int param)
765 : : {
766 : 1299150000 : u = unalias_unionall(u, e);
767 [ + + ]: 1299150000 : jl_varbinding_t vb = { u->var, u->var->lb, u->var->ub, R, 0, 0, 0, 0, 0, 0,
768 : 1299150000 : R ? e->Rinvdepth : e->invdepth, 0, NULL, e->vars };
769 : 1299150000 : JL_GC_PUSH4(&u, &vb.lb, &vb.ub, &vb.innervars);
770 : 1299150000 : e->vars = &vb;
771 : : int ans;
772 [ + + ]: 1299150000 : if (R) {
773 : 594258000 : e->envidx++;
774 : 594258000 : ans = subtype(t, u->body, e, param);
775 : 594258000 : e->envidx--;
776 : : // widen Type{x} to typeof(x) in argument position
777 [ + + ]: 594258000 : if (!vb.occurs_inv)
778 : 396689000 : vb.lb = widen_Type(vb.lb);
779 : : // fill variable values into `envout` up to `envsz`
780 [ + + ]: 594258000 : if (e->envidx < e->envsz) {
781 : : jl_value_t *val;
782 [ + + + - ]: 27755100 : if (vb.intvalued && vb.lb == (jl_value_t*)jl_any_type)
783 : 8631 : val = (jl_value_t*)jl_wrap_vararg(NULL, NULL);
784 [ + + + + ]: 27746500 : else if (!vb.occurs_inv && vb.lb != jl_bottom_type)
785 [ + + ]: 931127 : val = is_leaf_bound(vb.lb) ? vb.lb : (jl_value_t*)jl_new_typevar(u->var->name, jl_bottom_type, vb.lb);
786 [ + + ]: 26815400 : else if (vb.lb == vb.ub)
787 : 12438300 : val = vb.lb;
788 [ + + ]: 14377000 : else if (vb.lb != jl_bottom_type)
789 : : // TODO: for now return the least solution, which is what
790 : : // method parameters expect.
791 : 1053470 : val = vb.lb;
792 [ + - + + ]: 13323600 : else if (vb.lb == u->var->lb && vb.ub == u->var->ub)
793 : 13323600 : val = (jl_value_t*)u->var;
794 : : else
795 : 15 : val = (jl_value_t*)jl_new_typevar(u->var->name, vb.lb, vb.ub);
796 : 27755100 : jl_value_t *oldval = e->envout[e->envidx];
797 : : // if we try to assign different variable values (due to checking
798 : : // multiple union members), consider the value unknown.
799 [ + + + + ]: 27755100 : if (oldval && !jl_egal(oldval, val))
800 : 27537 : e->envout[e->envidx] = (jl_value_t*)u->var;
801 : : else
802 : 27727600 : e->envout[e->envidx] = fix_inferred_var_bound(u->var, val);
803 : : // TODO: substitute the value (if any) of this variable into previous envout entries
804 : : }
805 : : }
806 : : else {
807 [ - + ]: 1409790000 : ans = R ? subtype(t, u->body, e, param) :
808 : 704894000 : subtype(u->body, t, e, param);
809 : : }
810 : :
811 : : // handle the "diagonal dispatch" rule, which says that a type var occurring more
812 : : // than once, and only in covariant position, is constrained to concrete types. E.g.
813 : : // ( Tuple{Int, Int} <: Tuple{T, T} where T) but
814 : : // !( Tuple{Int, String} <: Tuple{T, T} where T)
815 : : // Then check concreteness by checking that the lower bound is not an abstract type.
816 [ + + + + ]: 1299150000 : int diagonal = vb.occurs_cov > 1 && !var_occurs_invariant(u->body, u->var, 0);
817 [ + + + + : 1299150000 : if (ans && (vb.concrete || (diagonal && is_leaf_typevar(u->var)))) {
+ + + + ]
818 [ + + + + : 10043100 : if (vb.concrete && !diagonal && !is_leaf_bound(vb.ub)) {
+ + ]
819 : : // a non-diagonal var can only be a subtype of a diagonal var if its
820 : : // upper bound is concrete.
821 : 9 : ans = 0;
822 : : }
823 [ + + ]: 10043100 : else if (jl_is_typevar(vb.lb)) {
824 : 151544 : jl_tvar_t *v = (jl_tvar_t*)vb.lb;
825 : 151544 : jl_varbinding_t *vlb = lookup(e, v);
826 [ + + ]: 151544 : if (vlb)
827 : 151542 : vlb->concrete = 1;
828 : : }
829 [ + + ]: 9891580 : else if (!is_leaf_bound(vb.lb)) {
830 : 1223090 : ans = 0;
831 : : }
832 : : }
833 : :
834 : 1299150000 : e->vars = vb.prev;
835 : :
836 [ + + ]: 1299150000 : if (!ans) {
837 : 1057030000 : JL_GC_POP();
838 : 1057030000 : return 0;
839 : : }
840 : :
841 : 242126000 : jl_varbinding_t *btemp = e->vars;
842 [ + + ]: 242126000 : if (vb.lb != vb.ub) {
843 [ + + ]: 280633000 : while (btemp != NULL) {
844 : 174418000 : jl_value_t *vu = btemp->ub;
845 : 174418000 : jl_value_t *vl = btemp->lb;
846 : : // TODO: this takes a significant amount of time
847 [ + + ]: 174418000 : if (btemp->depth0 != vb.depth0 &&
848 [ + - + + : 87172300 : ((vu != (jl_value_t*)vb.var && btemp->var->ub != vu && var_occurs_inside(vu, vb.var, 0, 1)) ||
+ + ]
849 [ + + + + : 87170300 : (vl != (jl_value_t*)vb.var && btemp->var->lb != vl && var_occurs_inside(vl, vb.var, 0, 1)))) {
+ + ]
850 : 2080 : ans = 0; break;
851 : : }
852 : 174416000 : btemp = btemp->prev;
853 : : }
854 : : }
855 : :
856 : 242126000 : JL_GC_POP();
857 : 242126000 : return ans;
858 : : }
859 : :
860 : : // check n <: (length of vararg type v)
861 : 38084200 : static int check_vararg_length(jl_value_t *v, ssize_t n, jl_stenv_t *e)
862 : : {
863 : 38084200 : jl_value_t *N = jl_unwrap_vararg_num(v);
864 : : // only do the check if N is free in the tuple type's last parameter
865 [ + + ]: 38084200 : if (N) {
866 : 5995080 : jl_value_t *nn = jl_box_long(n);
867 : 5995080 : JL_GC_PUSH1(&nn);
868 : 5995080 : e->invdepth++;
869 : 5995080 : e->Rinvdepth++;
870 [ + + + + ]: 5995080 : int ans = subtype(nn, N, e, 2) && subtype(N, nn, e, 0);
871 : 5995080 : e->invdepth--;
872 : 5995080 : e->Rinvdepth--;
873 : 5995080 : JL_GC_POP();
874 [ + + ]: 5995080 : if (!ans)
875 : 201690 : return 0;
876 : : }
877 : 37882500 : return 1;
878 : : }
879 : :
880 : : static int forall_exists_equal(jl_value_t *x, jl_value_t *y, jl_stenv_t *e);
881 : :
882 : : struct subtype_tuple_env {
883 : : jl_datatype_t *xd, *yd;
884 : : jl_value_t *lastx, *lasty;
885 : : size_t lx, ly;
886 : : size_t i, j;
887 : : int vx, vy;
888 : : jl_value_t *vtx;
889 : : jl_value_t *vty;
890 : : jl_vararg_kind_t vvx, vvy;
891 : : } JL_ROOTED_VALUE_COLLECTION;
892 : :
893 : 37049700 : static int subtype_tuple_varargs(
894 : : jl_vararg_t *vtx, jl_vararg_t *vty,
895 : : size_t vx, size_t vy,
896 : : jl_stenv_t *e, int param)
897 : : {
898 : 37049700 : jl_value_t *xp0 = jl_unwrap_vararg(vtx); jl_value_t *xp1 = jl_unwrap_vararg_num(vtx);
899 : 37049700 : jl_value_t *yp0 = jl_unwrap_vararg(vty); jl_value_t *yp1 = jl_unwrap_vararg_num(vty);
900 : :
901 [ + + ]: 37049700 : if (!xp1) {
902 : 34808200 : jl_value_t *yl = yp1;
903 [ + + ]: 34808200 : if (yl) {
904 : : // Unconstrained on the left, constrained on the right
905 [ + - ]: 2297370 : if (jl_is_typevar(yl)) {
906 : 2297370 : jl_varbinding_t *ylv = lookup(e, (jl_tvar_t*)yl);
907 [ + + ]: 2297370 : if (ylv)
908 : 2297340 : yl = ylv->lb;
909 : : }
910 [ + + ]: 2297370 : if (jl_is_long(yl)) {
911 : 10198 : return 0;
912 : : }
913 : : }
914 : : }
915 : : else {
916 : 2241530 : jl_value_t *xl = jl_unwrap_vararg_num(vtx);
917 [ + + ]: 2241530 : if (jl_is_typevar(xl)) {
918 : 2241520 : jl_varbinding_t *xlv = lookup(e, (jl_tvar_t*)xl);
919 [ + + ]: 2241520 : if (xlv)
920 : 2235640 : xl = xlv->lb;
921 : : }
922 [ + + ]: 2241530 : if (jl_is_long(xl)) {
923 [ + + ]: 4281 : if (jl_unbox_long(xl) + 1 == vx) {
924 : : // LHS is exhausted. We're a subtype if the RHS is either
925 : : // exhausted as well or unbounded (in which case we need to
926 : : // set it to 0).
927 : 4271 : jl_value_t *yl = jl_unwrap_vararg_num(vty);
928 [ + + ]: 4271 : if (yl) {
929 [ + - ]: 2361 : if (jl_is_typevar(yl)) {
930 : 2361 : jl_varbinding_t *ylv = lookup(e, (jl_tvar_t*)yl);
931 [ + - ]: 2361 : if (ylv)
932 : 2361 : yl = ylv->lb;
933 : : }
934 [ + + ]: 2361 : if (jl_is_long(yl)) {
935 : 2360 : return jl_unbox_long(yl) + 1 == vy;
936 : : }
937 : : } else {
938 : : // We can skip the subtype check, but we still
939 : : // need to make sure to constrain the length of y
940 : : // to 0.
941 : 1910 : goto constrain_length;
942 : : }
943 : : }
944 : : }
945 : : }
946 : :
947 : : // in Vararg{T1} <: Vararg{T2}, need to check subtype twice to
948 : : // simulate the possibility of multiple arguments, which is needed
949 : : // to implement the diagonal rule correctly.
950 [ + + ]: 37035200 : if (!subtype(xp0, yp0, e, param)) return 0;
951 [ + + ]: 26034700 : if (!subtype(xp0, yp0, e, 1)) return 0;
952 : :
953 : 17714200 : constrain_length:
954 [ + + ]: 17716100 : if (!yp1) {
955 : 15936100 : return 1;
956 : : }
957 [ + + ]: 1779990 : if (!xp1) {
958 : 1584790 : jl_value_t *yl = yp1;
959 : 1584790 : jl_varbinding_t *ylv = NULL;
960 [ + - ]: 1584790 : if (jl_is_typevar(yl)) {
961 : 1584790 : ylv = lookup(e, (jl_tvar_t*)yl);
962 [ + + ]: 1584790 : if (ylv)
963 : 1584780 : yl = ylv->lb;
964 : : }
965 [ - + ]: 1584790 : if (jl_is_long(yl)) {
966 : : // The length of the x tuple is unconstrained, but the
967 : : // length of the y tuple is now fixed (this could have happened
968 : : // as a result of the subtype call above).
969 : 0 : return 0;
970 : : }
971 : :
972 [ + + ]: 1584790 : if (ylv) {
973 [ + + + + ]: 1584780 : if (ylv->depth0 != e->invdepth || ylv->occurs_inv)
974 : 155514 : return 0;
975 : 1429260 : ylv->intvalued = 1;
976 : : }
977 : : // set lb to Any. Since `intvalued` is set, we'll interpret that
978 : : // appropriately.
979 : 1429280 : e->invdepth++;
980 : 1429280 : e->Rinvdepth++;
981 : 1429280 : int ans = subtype((jl_value_t*)jl_any_type, yp1, e, 2);
982 : 1429280 : e->invdepth--;
983 : 1429280 : e->Rinvdepth--;
984 : 1429280 : return ans;
985 : : }
986 : :
987 : : // Vararg{T,N} <: Vararg{T2,N2}; equate N and N2
988 : 195198 : e->invdepth++;
989 : 195198 : e->Rinvdepth++;
990 : 195198 : JL_GC_PUSH2(&xp1, &yp1);
991 [ + - + + : 195198 : if (xp1 && jl_is_long(xp1) && vx != 1)
+ + ]
992 : 1 : xp1 = jl_box_long(jl_unbox_long(xp1) - vx + 1);
993 [ + + + + ]: 195198 : if (jl_is_long(yp1) && vy != 1)
994 : 1 : yp1 = jl_box_long(jl_unbox_long(yp1) - vy + 1);
995 : 195198 : int ans = forall_exists_equal(xp1, yp1, e);
996 : 195198 : JL_GC_POP();
997 : 195198 : e->invdepth--;
998 : 195198 : e->Rinvdepth--;
999 : 195198 : return ans;
1000 : : }
1001 : :
1002 : 483787000 : static int subtype_tuple_tail(jl_datatype_t *xd, jl_datatype_t *yd, int8_t R, jl_stenv_t *e, int param)
1003 : : {
1004 : 483787000 : size_t lx = jl_nparams(xd);
1005 : 483787000 : size_t ly = jl_nparams(yd);
1006 : 483787000 : size_t i = 0, j = 0, vx = 0, vy = 0, x_reps = 1;
1007 : 483787000 : jl_value_t *lastx = NULL, *lasty = NULL;
1008 : 483787000 : jl_value_t *xi = NULL, *yi = NULL;
1009 : :
1010 : 663798000 : for (;;) {
1011 [ + + ]: 1147580000 : if (i < lx) {
1012 : 1097660000 : xi = jl_tparam(xd, i);
1013 [ + + + + : 1097660000 : if (i == lx-1 && (vx || jl_is_vararg(xi))) {
+ + ]
1014 : 33113500 : vx += 1;
1015 : : }
1016 : : }
1017 : :
1018 [ + + ]: 1147580000 : if (j < ly) {
1019 : 1112030000 : yi = jl_tparam(yd, j);
1020 [ + + + + : 1112030000 : if (j == ly-1 && (vy || jl_is_vararg(yi))) {
+ + ]
1021 : 159734000 : vy += 1;
1022 : : }
1023 : : }
1024 : :
1025 [ + + ]: 1147580000 : if (i >= lx)
1026 : 49928300 : break;
1027 : :
1028 [ + + + + ]: 1097660000 : int all_varargs = vx && vy;
1029 [ + + + + ]: 1097660000 : if (!all_varargs && vy == 1) {
1030 [ + + ]: 46098600 : if (jl_unwrap_vararg(yi) == (jl_value_t*)jl_any_type) {
1031 : : // Tuple{...} <: Tuple{..., Vararg{Any, _}}
1032 : : // fast path all the type checks away
1033 : 27835100 : xi = jl_tparam(xd, lx-1);
1034 [ + + ]: 27835100 : if (jl_is_vararg(xi)) {
1035 : 4210940 : all_varargs = 1;
1036 : 4210940 : vy += lx - i;
1037 : 4210940 : vx = 1;
1038 : : } else {
1039 : 23624200 : break;
1040 : : }
1041 : : }
1042 : : }
1043 : :
1044 [ + + ]: 1074030000 : if (all_varargs) {
1045 : : // Tuple{..., Vararg{xi, _}} <: Tuple{..., Vararg{yi, _}}
1046 : 37049700 : return subtype_tuple_varargs(
1047 : : (jl_vararg_t*)xi,
1048 : : (jl_vararg_t*)yi,
1049 : : vx, vy, e, param);
1050 : : }
1051 : :
1052 [ + + ]: 1036980000 : if (j >= ly)
1053 : 90563 : return !!vx;
1054 : :
1055 [ + + ]: 1036890000 : xi = vx ? jl_unwrap_vararg(xi) : xi;
1056 [ + + + + ]: 1036890000 : int x_same = lastx && jl_egal(xi, lastx);
1057 [ + + ]: 1036890000 : if (vy) {
1058 : 84600500 : yi = jl_unwrap_vararg(yi);
1059 : : // keep track of number of consecutive identical types compared to Vararg
1060 [ + + ]: 84600500 : if (x_same)
1061 : 65667300 : x_reps++;
1062 : : else
1063 : 18933300 : x_reps = 1;
1064 : : }
1065 [ + + ]: 1036890000 : if (x_reps > 2) {
1066 : : // an identical type on the left doesn't need to be compared to a Vararg
1067 : : // element type on the right more than twice.
1068 : : }
1069 [ + + + + : 976543000 : else if (x_same && e->Runions.depth == 0 &&
+ + ]
1070 [ + + + + : 20144200 : ((yi == lasty && !jl_has_free_typevars(xi) && !jl_has_free_typevars(yi)) ||
+ + ]
1071 [ + + + + : 277325 : (yi == lastx && !vx && vy && jl_is_concrete_type(xi)))) {
+ + ]
1072 : : // fast path for repeated elements
1073 : : }
1074 [ + + + + : 968308000 : else if (e->Runions.depth == 0 && e->Lunions.depth == 0 && !jl_has_free_typevars(xi) && !jl_has_free_typevars(yi)) {
+ + + + ]
1075 : : // fast path for separable sub-formulas
1076 [ + + ]: 731152000 : if (!jl_subtype(xi, yi))
1077 : 203312000 : return 0;
1078 : : }
1079 [ + + ]: 237157000 : else if (!subtype(xi, yi, e, param)) {
1080 : 169782000 : return 0;
1081 : : }
1082 : 663798000 : lastx = xi; lasty = yi;
1083 [ + + + + ]: 663798000 : if (i < lx-1 || !vx)
1084 : 663614000 : i++;
1085 [ + + + + ]: 663798000 : if (j < ly-1 || !vy)
1086 : 589241000 : j++;
1087 : : }
1088 : :
1089 [ + + + - : 73552500 : if (vy && !vx && lx+1 >= ly) {
+ - ]
1090 : : // in Tuple{...,tn} <: Tuple{...,Vararg{T,N}}, check (lx+1-ly) <: N
1091 [ + + ]: 38083900 : if (!check_vararg_length(yi, lx+1-ly, e))
1092 : 201351 : return 0;
1093 : : }
1094 [ + + + - : 73351100 : assert((lx + vx == ly + vy) || (vy && (lx >= (vx ? ly : (ly-1)))));
+ - + - ]
1095 : 73351100 : return 1;
1096 : : }
1097 : :
1098 : 519108000 : static int subtype_tuple(jl_datatype_t *xd, jl_datatype_t *yd, jl_stenv_t *e, int param)
1099 : : {
1100 : : // Check tuple compatibility based on tuple length only (fastpath)
1101 : 519108000 : size_t lx = jl_nparams(xd);
1102 : 519108000 : size_t ly = jl_nparams(yd);
1103 : :
1104 [ + + - + ]: 519108000 : if (lx == 0 && ly == 0)
1105 : 0 : return 1;
1106 : :
1107 : 519108000 : jl_vararg_kind_t vvx = JL_VARARG_NONE;
1108 : 519108000 : jl_vararg_kind_t vvy = JL_VARARG_NONE;
1109 : 519108000 : jl_varbinding_t *xbb = NULL;
1110 : 519108000 : jl_value_t *xva = NULL, *yva = NULL;
1111 [ + + ]: 519108000 : if (lx > 0) {
1112 : 511951000 : xva = jl_tparam(xd, lx-1);
1113 : 511951000 : vvx = jl_vararg_kind(xva);
1114 [ + + ]: 511951000 : if (vvx == JL_VARARG_BOUND)
1115 : 8015410 : xbb = lookup(e, (jl_tvar_t *)jl_unwrap_vararg_num(xva));
1116 : : }
1117 [ + + ]: 519108000 : if (ly > 0) {
1118 : 515772000 : yva = jl_tparam(yd, ly-1);
1119 : 515772000 : vvy = jl_vararg_kind(yva);
1120 : : }
1121 [ + + + + : 519108000 : if (vvx != JL_VARARG_NONE && vvx != JL_VARARG_INT &&
+ + ]
1122 [ + + ]: 8009180 : (!xbb || !jl_is_long(xbb->lb))) {
1123 [ + + + + : 70934900 : if (vvx == JL_VARARG_UNBOUND || (xbb && !xbb->right)) {
+ + ]
1124 : : // Unbounded on the LHS, bounded on the RHS
1125 [ + + + + ]: 70923100 : if (vvy == JL_VARARG_NONE || vvy == JL_VARARG_INT)
1126 : 23948500 : return 0;
1127 [ + + ]: 46974600 : else if (lx < ly) // Unbounded includes N == 0
1128 : 5382430 : return 0;
1129 : : }
1130 [ + + + + ]: 11822 : else if (vvy == JL_VARARG_NONE && !check_vararg_length(xva, ly+1-lx, e)) {
1131 : 339 : return 0;
1132 : : }
1133 : : }
1134 : : else {
1135 : 448173000 : size_t nx = lx;
1136 [ + + ]: 448173000 : if (vvx == JL_VARARG_INT)
1137 : 13 : nx += jl_vararg_length(xva) - 1;
1138 [ + + + - ]: 448173000 : else if (xbb && jl_is_long(xbb->lb))
1139 : 95762 : nx += jl_unbox_long(xbb->lb) - 1;
1140 : : else
1141 [ - + ]: 448077000 : assert(vvx == JL_VARARG_NONE);
1142 : 448173000 : size_t ny = ly;
1143 [ + + ]: 448173000 : if (vvy == JL_VARARG_INT)
1144 : 9 : ny += jl_vararg_length(yva) - 1;
1145 [ + + ]: 448173000 : else if (vvy != JL_VARARG_NONE)
1146 : 61296800 : ny -= 1;
1147 [ + + + + ]: 448173000 : if (vvy == JL_VARARG_NONE || vvy == JL_VARARG_INT) {
1148 [ + + ]: 386876000 : if (nx != ny)
1149 : 4108820 : return 0;
1150 : : }
1151 : : else {
1152 [ + + ]: 61296800 : if (ny > nx)
1153 : 1881200 : return 0;
1154 : : }
1155 : : }
1156 : :
1157 [ + + ]: 483787000 : param = (param == 0 ? 1 : param);
1158 : 483787000 : int ans = subtype_tuple_tail(xd, yd, 0, e, param);
1159 : 483787000 : return ans;
1160 : : }
1161 : :
1162 : : // `param` means we are currently looking at a parameter of a type constructor
1163 : : // (as opposed to being outside any type constructor, or comparing variable bounds).
1164 : : // this is used to record the positions where type variables occur for the
1165 : : // diagonal rule (record_var_occurrence).
1166 : 5224850000 : static int subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param)
1167 : : {
1168 [ + + ]: 5224850000 : if (jl_is_uniontype(x)) {
1169 [ + + ]: 416502000 : if (x == y) return 1;
1170 : 416396000 : x = pick_union_element(x, e, 0);
1171 : : }
1172 [ + + ]: 5224740000 : if (jl_is_uniontype(y)) {
1173 [ + + + + ]: 1024770000 : if (x == ((jl_uniontype_t*)y)->a || x == ((jl_uniontype_t*)y)->b)
1174 : 37818900 : return 1;
1175 [ + + ]: 986954000 : if (jl_is_unionall(x))
1176 : 264861000 : return subtype_unionall(y, (jl_unionall_t*)x, e, 0, param);
1177 : 722093000 : int ui = 1;
1178 [ + + ]: 722093000 : if (jl_is_typevar(x)) {
1179 : : // The `convert(Type{T},T)` pattern, where T is a Union, required changing priority
1180 : : // of unions and vars: if matching `typevar <: union`, first try to match the whole
1181 : : // union against the variable before trying to take it apart to see if there are any
1182 : : // variables lurking inside.
1183 : 46045500 : jl_unionstate_t *state = &e->Runions;
1184 [ + + ]: 46045500 : if (state->depth >= state->used) {
1185 : 19568600 : statestack_set(state, state->used, 0);
1186 : 19568600 : state->used++;
1187 : : }
1188 : 46045500 : ui = statestack_get(state, state->depth);
1189 : 46045500 : state->depth++;
1190 [ + + ]: 46045500 : if (ui == 0)
1191 : 36911700 : state->more = state->depth; // memorize that this was the deepest available choice
1192 : : }
1193 [ + + ]: 722093000 : if (ui == 1)
1194 : 685181000 : y = pick_union_element(y, e, 1);
1195 : : }
1196 [ + + ]: 4922060000 : if (jl_is_typevar(x)) {
1197 [ + + ]: 569875000 : if (jl_is_typevar(y)) {
1198 [ + + ]: 245597000 : if (x == y) return 1;
1199 : 244236000 : jl_varbinding_t *xx = lookup(e, (jl_tvar_t*)x);
1200 : 244236000 : jl_varbinding_t *yy = lookup(e, (jl_tvar_t*)y);
1201 [ + + ]: 244236000 : jl_value_t *xub = xx ? xx->ub : ((jl_tvar_t*)x)->ub;
1202 [ + + ]: 244236000 : jl_value_t *ylb = yy ? yy->lb : ((jl_tvar_t*)y)->lb;
1203 [ + + ]: 244236000 : if (e->intersection) {
1204 [ + + ]: 903855 : jl_value_t *xlb = xx ? xx->lb : ((jl_tvar_t*)x)->lb;
1205 [ + + ]: 903855 : jl_value_t *yub = yy ? yy->ub : ((jl_tvar_t*)y)->ub;
1206 : : // find equivalence class for typevars during intersection
1207 [ + + + + ]: 903855 : if (xub == xlb && jl_is_typevar(xub))
1208 : 374462 : return subtype(xub, y, e, param);
1209 [ + + + + ]: 529393 : if (yub == ylb && jl_is_typevar(yub))
1210 : 374521 : return subtype(x, yub, e, param);
1211 : : }
1212 [ + + + + ]: 243487000 : int xr = xx && xx->right; // treat free variables as "forall" (left)
1213 [ + + + + ]: 243487000 : int yr = yy && yy->right;
1214 [ + + ]: 243487000 : if (xr) {
1215 [ + + ]: 111447000 : if (yy) record_var_occurrence(yy, e, param);
1216 [ + + ]: 111447000 : if (yr) {
1217 : 3736 : record_var_occurrence(xx, e, param);
1218 : 3736 : return subtype(xx->lb, yy->ub, e, 0);
1219 : : }
1220 : 111443000 : return var_lt((jl_tvar_t*)x, y, e, param);
1221 : : }
1222 [ + + ]: 132040000 : else if (yr) {
1223 [ + + ]: 128925000 : if (xx) record_var_occurrence(xx, e, param);
1224 : 128925000 : return var_gt((jl_tvar_t*)y, x, e, param);
1225 : : }
1226 : : // check ∀x,y . x<:y
1227 : : // the bounds of left-side variables never change, and can only lead
1228 : : // to other left-side variables, so using || here is safe.
1229 [ + + + + ]: 3115390 : return subtype(xub, y, e, param) || subtype(x, ylb, e, param);
1230 : : }
1231 : 324279000 : return var_lt((jl_tvar_t*)x, y, e, param);
1232 : : }
1233 [ + + ]: 4352180000 : if (jl_is_typevar(y))
1234 : 140506000 : return var_gt((jl_tvar_t*)y, x, e, param);
1235 [ + + + + ]: 4211680000 : if (y == (jl_value_t*)jl_any_type && !jl_has_free_typevars(x))
1236 : 26430200 : return 1;
1237 [ + + + + ]: 4185250000 : if (x == jl_bottom_type && !jl_has_free_typevars(y))
1238 : 7030020 : return 1;
1239 : 4178220000 : jl_value_t *ux = jl_unwrap_unionall(x);
1240 : 4178220000 : jl_value_t *uy = jl_unwrap_unionall(y);
1241 [ + + + + : 5492590000 : if ((x != ux || y != uy) && y != (jl_value_t*)jl_any_type && jl_is_datatype(ux) && jl_is_datatype(uy) &&
+ + + + +
+ + + ]
1242 : 1314370000 : !jl_is_type_type(ux)) {
1243 [ - + ]: 1193470000 : assert(ux);
1244 [ + + ]: 1193470000 : if (uy == (jl_value_t*)jl_any_type)
1245 : 13 : return 1;
1246 : 1193470000 : jl_datatype_t *xd = (jl_datatype_t*)ux, *yd = (jl_datatype_t*)uy;
1247 [ + - + + : 2407350000 : while (xd != NULL && xd != jl_any_type && xd->name != yd->name) {
+ + ]
1248 : 1213890000 : xd = xd->super;
1249 : : }
1250 [ + + ]: 1193470000 : if (xd == jl_any_type)
1251 : 509071000 : return 0;
1252 : : }
1253 : : // handle forall ("left") vars first
1254 [ + + ]: 3669150000 : if (jl_is_unionall(x)) {
1255 [ + + + + ]: 440093000 : if (x == y && !(e->envidx < e->envsz))
1256 : 60458 : return 1;
1257 : 440033000 : return subtype_unionall(y, (jl_unionall_t*)x, e, 0, param);
1258 : : }
1259 [ + + ]: 3229050000 : if (jl_is_unionall(y))
1260 : 594258000 : return subtype_unionall(x, (jl_unionall_t*)y, e, 1, param);
1261 [ + + + + ]: 2634790000 : if (jl_is_datatype(x) && jl_is_datatype(y)) {
1262 [ + + ]: 2512270000 : if (x == y) return 1;
1263 [ + + ]: 2475190000 : if (y == (jl_value_t*)jl_any_type) return 1;
1264 : 2472690000 : jl_datatype_t *xd = (jl_datatype_t*)x, *yd = (jl_datatype_t*)y;
1265 [ + + + + ]: 2472690000 : if (jl_is_type_type(x) && !jl_is_type_type(y)) {
1266 : 10696200 : jl_value_t *tp0 = jl_tparam0(xd);
1267 [ + + ]: 10696200 : if (!jl_is_typevar(tp0)) {
1268 : : // TODO this is not strictly correct, but we don't yet have any other way for
1269 : : // e.g. the argument `Int` to match a `::DataType` slot. Most correct would be:
1270 : : // Int isa DataType, Int isa Type{Int}, Type{Int} more specific than DataType,
1271 : : // !(Type{Int} <: DataType), !isleaftype(Type{Int}), because non-DataTypes can
1272 : : // be type-equal to `Int`.
1273 : 6111440 : return jl_typeof(tp0) == (jl_value_t*)yd;
1274 : : }
1275 : 4584800 : return 0;
1276 : : }
1277 [ + + + + : 2462000000 : if (jl_is_type_type(y) && !jl_is_type_type(x) && x != (jl_value_t*)jl_typeofbottom_type) {
+ + ]
1278 : 34051900 : jl_value_t *tp0 = jl_tparam0(yd);
1279 [ + + + + ]: 34051900 : if (!jl_is_typevar(tp0) || !jl_is_kind(x))
1280 : 31533800 : return 0;
1281 : : // DataType.super is special, so `DataType <: Type{T}` (T free) needs special handling.
1282 : : // The answer is true iff `T` has full bounds (as in `Type`), but this needs to
1283 : : // be checked at the same depth where `Type{T}` occurs --- the depth of the LHS
1284 : : // doesn't matter because it (e.g. `DataType`) doesn't actually contain the variable.
1285 : 2518060 : int saved = e->invdepth;
1286 : 2518060 : e->invdepth = e->Rinvdepth;
1287 : 2518060 : int issub = subtype((jl_value_t*)jl_type_type, y, e, param);
1288 : 2518060 : e->invdepth = saved;
1289 : 2518060 : return issub;
1290 : : }
1291 [ + + + + ]: 5447240000 : while (xd != jl_any_type && xd->name != yd->name) {
1292 [ + + ]: 3019290000 : if (xd->super == NULL)
1293 : 1 : jl_errorf("circular type parameter constraint in definition of %s", jl_symbol_name(xd->name->name));
1294 : 3019290000 : xd = xd->super;
1295 : : }
1296 [ + + ]: 2427940000 : if (xd == jl_any_type) return 0;
1297 [ + + ]: 1173990000 : if (xd->name == jl_tuple_typename)
1298 : 519108000 : return subtype_tuple(xd, yd, e, param);
1299 : 654878000 : size_t i, np = jl_nparams(xd);
1300 : 654878000 : int ans = 1;
1301 : 654878000 : e->invdepth++;
1302 : 654878000 : e->Rinvdepth++;
1303 [ + + ]: 899993000 : for (i=0; i < np; i++) {
1304 : 500774000 : jl_value_t *xi = jl_tparam(xd, i), *yi = jl_tparam(yd, i);
1305 [ + + + + ]: 500774000 : if (!(xi == yi || forall_exists_equal(xi, yi, e))) {
1306 : 255659000 : ans = 0; break;
1307 : : }
1308 : : }
1309 : 654878000 : e->invdepth--;
1310 : 654878000 : e->Rinvdepth--;
1311 : 654878000 : return ans;
1312 : : }
1313 [ + + ]: 122528000 : if (jl_is_type(y))
1314 : 25442300 : return x == jl_bottom_type;
1315 : 97086100 : return jl_egal(x, y);
1316 : : }
1317 : :
1318 : 457019000 : static int is_indefinite_length_tuple_type(jl_value_t *x)
1319 : : {
1320 : 457019000 : x = jl_unwrap_unionall(x);
1321 [ + + ]: 457019000 : if (!jl_is_tuple_type(x))
1322 : 444597000 : return 0;
1323 : 12421900 : size_t n = jl_nparams(x);
1324 [ + + + + ]: 12421900 : return n > 0 && jl_vararg_kind(jl_tparam(x, n-1)) == JL_VARARG_UNBOUND;
1325 : : }
1326 : :
1327 : 446432000 : static int is_definite_length_tuple_type(jl_value_t *x)
1328 : : {
1329 [ + + ]: 446432000 : if (jl_is_typevar(x))
1330 : 180722000 : x = ((jl_tvar_t*)x)->ub;
1331 : 446432000 : x = jl_unwrap_unionall(x);
1332 [ + + ]: 446432000 : if (!jl_is_tuple_type(x))
1333 : 421382000 : return 0;
1334 : 25049300 : size_t n = jl_nparams(x);
1335 [ + + ]: 25049300 : if (n == 0)
1336 : 2621470 : return 1;
1337 : 22427800 : jl_vararg_kind_t k = jl_vararg_kind(jl_tparam(x, n-1));
1338 [ + + + + ]: 22427800 : return k == JL_VARARG_NONE || k == JL_VARARG_INT;
1339 : : }
1340 : :
1341 : 445603000 : static int forall_exists_equal(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
1342 : : {
1343 [ + + ]: 445603000 : if (obviously_egal(x, y)) return 1;
1344 : :
1345 [ + + + + : 890355000 : if ((is_indefinite_length_tuple_type(x) && is_definite_length_tuple_type(y)) ||
+ + ]
1346 [ + + ]: 456183000 : (is_definite_length_tuple_type(x) && is_indefinite_length_tuple_type(y)))
1347 : 1673100 : return 0;
1348 : :
1349 : 443922000 : jl_saved_unionstate_t oldLunions; push_unionstate(&oldLunions, &e->Lunions);
1350 : 443922000 : e->Lunions.used = 0;
1351 : : int sub;
1352 : :
1353 [ + + + + ]: 443922000 : if (!jl_has_free_typevars(x) || !jl_has_free_typevars(y)) {
1354 : 284421000 : jl_saved_unionstate_t oldRunions; push_unionstate(&oldRunions, &e->Runions);
1355 : 284421000 : e->Runions.used = 0;
1356 : 284421000 : e->Runions.depth = 0;
1357 : 284421000 : e->Runions.more = 0;
1358 : 284421000 : e->Lunions.depth = 0;
1359 : 284421000 : e->Lunions.more = 0;
1360 : :
1361 : 284421000 : sub = forall_exists_subtype(x, y, e, 2);
1362 : :
1363 : 284421000 : pop_unionstate(&e->Runions, &oldRunions);
1364 : : }
1365 : : else {
1366 : 159501000 : int lastset = 0;
1367 : 1048960 : while (1) {
1368 : 160550000 : e->Lunions.more = 0;
1369 : 160550000 : e->Lunions.depth = 0;
1370 : 160550000 : sub = subtype(x, y, e, 2);
1371 : 160550000 : int set = e->Lunions.more;
1372 [ + + + + ]: 160550000 : if (!sub || !set)
1373 : : break;
1374 [ - + ]: 1048960 : for (int i = set; i <= lastset; i++)
1375 : 0 : statestack_set(&e->Lunions, i, 0);
1376 : 1048960 : lastset = set - 1;
1377 : 1048960 : statestack_set(&e->Lunions, lastset, 1);
1378 : : }
1379 : : }
1380 : :
1381 : 443922000 : pop_unionstate(&e->Lunions, &oldLunions);
1382 [ + + + + ]: 443922000 : return sub && subtype(y, x, e, 0);
1383 : : }
1384 : :
1385 : 2640570000 : static int exists_subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, jl_value_t *saved, jl_savedenv_t *se, int param)
1386 : : {
1387 : 2640570000 : e->Runions.used = 0;
1388 : 2640570000 : int lastset = 0;
1389 : 467348000 : while (1) {
1390 : 3107920000 : e->Runions.depth = 0;
1391 : 3107920000 : e->Runions.more = 0;
1392 : 3107920000 : e->Lunions.depth = 0;
1393 : 3107920000 : e->Lunions.more = 0;
1394 [ + + ]: 3107920000 : if (subtype(x, y, e, param))
1395 : 673357000 : return 1;
1396 : 2434560000 : restore_env(e, saved, se);
1397 : 2434560000 : int set = e->Runions.more;
1398 [ + + ]: 2434560000 : if (!set)
1399 : 1967210000 : return 0;
1400 [ + + ]: 487553000 : for (int i = set; i <= lastset; i++)
1401 : 20204800 : statestack_set(&e->Runions, i, 0);
1402 : 467348000 : lastset = set - 1;
1403 : 467348000 : statestack_set(&e->Runions, lastset, 1);
1404 : : }
1405 : : }
1406 : :
1407 : 2579600000 : static int forall_exists_subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param)
1408 : : {
1409 : : // The depth recursion has the following shape, after simplification:
1410 : : // ∀₁
1411 : : // ∃₁
1412 [ - + ]: 2579600000 : assert(e->Runions.depth == 0);
1413 [ - + ]: 2579600000 : assert(e->Lunions.depth == 0);
1414 : 2579600000 : jl_value_t *saved=NULL; jl_savedenv_t se;
1415 : 2579600000 : JL_GC_PUSH1(&saved);
1416 : 2579600000 : save_env(e, &saved, &se);
1417 : :
1418 : 2579600000 : e->Lunions.used = 0;
1419 : 2579600000 : int lastset = 0;
1420 : : int sub;
1421 : 60974700 : while (1) {
1422 : 2640570000 : sub = exists_subtype(x, y, e, saved, &se, param);
1423 : 2640570000 : int set = e->Lunions.more;
1424 [ + + + + ]: 2640570000 : if (!sub || !set)
1425 : : break;
1426 : 60974700 : free_env(&se);
1427 : 60974700 : save_env(e, &saved, &se);
1428 [ + + ]: 74608100 : for (int i = set; i <= lastset; i++)
1429 : 13633400 : statestack_set(&e->Lunions, i, 0);
1430 : 60974700 : lastset = set - 1;
1431 : 60974700 : statestack_set(&e->Lunions, lastset, 1);
1432 : : }
1433 : :
1434 : 2579600000 : free_env(&se);
1435 : 2579600000 : JL_GC_POP();
1436 : 2579600000 : return sub;
1437 : : }
1438 : :
1439 : 2155900000 : static void init_stenv(jl_stenv_t *e, jl_value_t **env, int envsz)
1440 : : {
1441 : 2155900000 : e->vars = NULL;
1442 [ + + - + ]: 2155900000 : assert(env != NULL || envsz == 0);
1443 : 2155900000 : e->envsz = envsz;
1444 : 2155900000 : e->envout = env;
1445 [ + + ]: 2155900000 : if (envsz)
1446 : 14565000 : memset(env, 0, envsz*sizeof(void*));
1447 : 2155900000 : e->envidx = 0;
1448 : 2155900000 : e->invdepth = e->Rinvdepth = 0;
1449 : 2155900000 : e->ignore_free = 0;
1450 : 2155900000 : e->intersection = 0;
1451 : 2155900000 : e->emptiness_only = 0;
1452 : 2155900000 : e->triangular = 0;
1453 : 2155900000 : e->Lunions.depth = 0; e->Runions.depth = 0;
1454 : 2155900000 : e->Lunions.more = 0; e->Runions.more = 0;
1455 : 2155900000 : e->Lunions.used = 0; e->Runions.used = 0;
1456 : 2155900000 : }
1457 : :
1458 : : // subtyping entry points
1459 : :
1460 : 56133200 : JL_DLLEXPORT int jl_subtype_env_size(jl_value_t *t)
1461 : : {
1462 : 56133200 : int sz = 0;
1463 [ + + ]: 84248100 : while (jl_is_unionall(t)) {
1464 : 28114900 : sz++;
1465 : 28114900 : t = ((jl_unionall_t*)t)->body;
1466 : : }
1467 : 56133200 : return sz;
1468 : : }
1469 : :
1470 : : // compute the minimum bound on the number of concrete types that are subtypes of `t`
1471 : : // returns 0, 1, or many (2+)
1472 : 404174 : static int concrete_min(jl_value_t *t)
1473 : : {
1474 [ + + ]: 404174 : if (jl_is_unionall(t))
1475 : 8806 : t = jl_unwrap_unionall(t);
1476 [ - + ]: 404174 : if (t == (jl_value_t*)jl_bottom_type)
1477 : 0 : return 1;
1478 [ + + ]: 404174 : if (jl_is_datatype(t)) {
1479 [ + + ]: 367596 : if (jl_is_type_type(t))
1480 : 4411 : return 0; // Type{T} may have the concrete supertype `typeof(T)`, so don't try to handle them here
1481 [ + + ]: 363185 : return jl_is_concrete_type(t) ? 1 : 2;
1482 : : }
1483 [ - + ]: 36578 : if (jl_is_vararg(t))
1484 : 0 : return 0;
1485 [ + + ]: 36578 : if (jl_is_typevar(t))
1486 : 2395 : return 0; // could be 0 or more, since we didn't track if it was unbound
1487 [ + + ]: 34183 : if (jl_is_uniontype(t)) {
1488 : 34174 : int count = concrete_min(((jl_uniontype_t*)t)->a);
1489 [ + + ]: 34174 : if (count > 1)
1490 : 3808 : return count;
1491 : 30366 : return count + concrete_min(((jl_uniontype_t*)t)->b);
1492 : : }
1493 [ - + ]: 9 : assert(!jl_is_kind(t));
1494 : 9 : return 1; // a non-Type is also considered concrete
1495 : : }
1496 : :
1497 : 2813250 : static jl_value_t *find_var_body(jl_value_t *t, jl_tvar_t *v)
1498 : : {
1499 [ + + ]: 2813250 : if (jl_is_unionall(t)) {
1500 [ + + ]: 1128310 : if (((jl_unionall_t*)t)->var == v)
1501 : 572945 : return ((jl_unionall_t*)t)->body;
1502 : 555365 : jl_value_t *b = find_var_body(((jl_unionall_t*)t)->var->lb, v);
1503 [ - + ]: 555365 : if (b) return b;
1504 : 555365 : b = find_var_body(((jl_unionall_t*)t)->var->ub, v);
1505 [ + + ]: 555365 : if (b) return b;
1506 : 551638 : return find_var_body(((jl_unionall_t*)t)->body, v);
1507 : : }
1508 [ + + ]: 1684940 : else if (jl_is_uniontype(t)) {
1509 : 4872 : jl_value_t *b = find_var_body(((jl_uniontype_t*)t)->a, v);
1510 [ - + ]: 4872 : if (b) return b;
1511 : 4872 : return find_var_body(((jl_uniontype_t*)t)->b, v);
1512 : : }
1513 [ + + ]: 1680070 : else if (jl_is_vararg(t)) {
1514 : 155 : jl_vararg_t *vm = (jl_vararg_t *)t;
1515 [ + - ]: 155 : if (vm->T) {
1516 : 155 : jl_value_t *b = find_var_body(vm->T, v);
1517 [ - + ]: 155 : if (b) return b;
1518 [ + + ]: 155 : if (vm->N) {
1519 : 6 : return find_var_body(vm->N, v);
1520 : : }
1521 : : }
1522 : : }
1523 [ + + ]: 1679920 : else if (jl_is_datatype(t)) {
1524 : : size_t i;
1525 [ + + ]: 1430230 : for (i=0; i < jl_nparams(t); i++) {
1526 : 562947 : jl_value_t *b = find_var_body(jl_tparam(t, i), v);
1527 [ + + ]: 562947 : if (b)
1528 : 240956 : return b;
1529 : : }
1530 : : }
1531 : 1439110 : return NULL;
1532 : : }
1533 : :
1534 : : // quickly compute if x seems like a possible subtype of y
1535 : : // especially optimized for x isa concrete type
1536 : : // returns true if it could be easily determined, with the result in subtype
1537 : : // the approximation widens typevar bounds under the assumption they are bound
1538 : : // in the immediate caller--the caller must be conservative in handling the result
1539 : 7653810000 : static int obvious_subtype(jl_value_t *x, jl_value_t *y, jl_value_t *y0, int *subtype)
1540 : : {
1541 [ + + + + ]: 7653810000 : if (x == y || y == (jl_value_t*)jl_any_type) {
1542 : 1472250000 : *subtype = 1;
1543 : 1472250000 : return 1;
1544 : : }
1545 [ + + ]: 6469980000 : while (jl_is_unionall(x)) {
1546 [ + + ]: 739509000 : if (!jl_is_unionall(y)) {
1547 [ + + + + ]: 451094000 : if (obvious_subtype(jl_unwrap_unionall(x), y, y0, subtype) && !*subtype)
1548 : 149305000 : return 1;
1549 : 301789000 : return 0;
1550 : : }
1551 : 288415000 : x = ((jl_unionall_t*)x)->body;
1552 : 288415000 : y = ((jl_unionall_t*)y)->body;
1553 : : }
1554 [ + + ]: 5730470000 : if (jl_is_unionall(y))
1555 : 845065000 : y = jl_unwrap_unionall(y);
1556 [ + + ]: 5730470000 : if (x == (jl_value_t*)jl_typeofbottom_type->super)
1557 : 5940090 : x = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
1558 [ + + ]: 5730470000 : if (y == (jl_value_t*)jl_typeofbottom_type->super)
1559 : 2599930 : y = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
1560 [ + + + + ]: 5730470000 : if (x == y || y == (jl_value_t*)jl_any_type) {
1561 : 1251510 : *subtype = 1;
1562 : 1251510 : return 1;
1563 : : }
1564 [ + + ]: 5729220000 : if (jl_is_typevar(x)) {
1565 [ + + ]: 397184000 : if (((jl_tvar_t*)x)->lb != (jl_value_t*)jl_bottom_type)
1566 : 7947650 : return 0;
1567 [ + + + + ]: 389236000 : if (obvious_subtype(((jl_tvar_t*)x)->ub, y, y0, subtype) && *subtype)
1568 : 1590360 : return 1;
1569 : 387646000 : return 0;
1570 : : }
1571 [ + + ]: 5332030000 : if (jl_is_typevar(y)) {
1572 [ + + ]: 492463000 : if (((jl_tvar_t*)y)->lb != (jl_value_t*)jl_bottom_type)
1573 : 13744500 : return 0;
1574 [ + + + + ]: 478719000 : if (obvious_subtype(x, ((jl_tvar_t*)y)->ub, y0, subtype) && !*subtype)
1575 : 71128600 : return 1;
1576 : 407590000 : return 0;
1577 : : }
1578 [ + + ]: 4839570000 : if (x == (jl_value_t*)jl_bottom_type) {
1579 : 146529 : *subtype = 1;
1580 : 146529 : return 1;
1581 : : }
1582 [ + + ]: 4839420000 : if (y == (jl_value_t*)jl_bottom_type) {
1583 : 1904140 : *subtype = 0;
1584 : 1904140 : return 1;
1585 : : }
1586 [ - + ]: 4837520000 : if (jl_is_vararg(x)) {
1587 [ # # ]: 0 : if (!jl_is_vararg(y)) {
1588 : 0 : *subtype = 0;
1589 : 0 : return 1;
1590 : : }
1591 : 0 : return 0;
1592 : : }
1593 [ + + + + ]: 4837520000 : if (!jl_is_type(x) || !jl_is_type(y)) {
1594 : 186153000 : *subtype = jl_egal(x, y);
1595 : 186153000 : return 1;
1596 : : }
1597 [ + + ]: 4651360000 : if (jl_is_uniontype(x)) {
1598 : : // TODO: consider handling more LHS unions, being wary of covariance
1599 [ + + + + ]: 209841000 : if (obvious_subtype(((jl_uniontype_t*)x)->a, y, y0, subtype) && *subtype) {
1600 [ + + + + ]: 33080400 : if (obvious_subtype(((jl_uniontype_t*)x)->b, y, y0, subtype) && *subtype)
1601 : 12851100 : return 1;
1602 : : }
1603 : : //if (obvious_subtype(((jl_uniontype_t*)x)->a, y, y0, subtype)) {
1604 : : // if (!*subtype)
1605 : : // return 1;
1606 : : // if (obvious_subtype(((jl_uniontype_t*)x)->b, y, y0, subtype))
1607 : : // return 1;
1608 : : //}
1609 : : //else if (obvious_subtype(((jl_uniontype_t*)x)->b, y, y0, subtype)) {
1610 : : // if (!*subtype)
1611 : : // return 1;
1612 : : //}
1613 : 196990000 : return 0;
1614 : : }
1615 [ + + ]: 4441520000 : if (jl_is_uniontype(y)) {
1616 [ + + ]: 664021000 : if (obvious_subtype(x, ((jl_uniontype_t*)y)->a, y0, subtype)) {
1617 [ + + ]: 630096000 : if (*subtype)
1618 : 44319100 : return 1;
1619 [ + + ]: 585777000 : if (obvious_subtype(x, ((jl_uniontype_t*)y)->b, y0, subtype))
1620 : 562338000 : return 1;
1621 : : }
1622 [ + + ]: 33924800 : else if (obvious_subtype(x, ((jl_uniontype_t*)y)->b, y0, subtype)) {
1623 [ + + ]: 19440900 : if (*subtype)
1624 : 47400 : return 1;
1625 : : }
1626 : 57316400 : return 0;
1627 : : }
1628 [ + + ]: 3777500000 : if (x == (jl_value_t*)jl_any_type) {
1629 : 212093000 : *subtype = 0;
1630 : 212093000 : return 1;
1631 : : }
1632 [ + - ]: 3565410000 : if (jl_is_datatype(y)) {
1633 : 3565410000 : int istuple = (((jl_datatype_t*)y)->name == jl_tuple_typename);
1634 : 3565410000 : int iscov = istuple;
1635 : : // TODO: this would be a nice fast-path to have, unfortuanately,
1636 : : // datatype allocation fails to correctly hash-cons them
1637 : : // and the subtyping tests include tests for this case
1638 : : //if (!iscov && ((jl_datatype_t*)y)->isconcretetype && !jl_is_type_type(x)) {
1639 : : // *subtype = 0;
1640 : : // return 1;
1641 : : //}
1642 [ + - ]: 3565410000 : if (jl_is_datatype(x)) {
1643 : : // Weaker version of above, but runs into the same problem
1644 : : //if (((jl_datatype_t*)x)->isconcretetype && ((jl_datatype_t*)y)->isconcretetype && (!istuple || !istuple_x)) {
1645 : : // *subtype = 0;
1646 : : // return 1;
1647 : : //}
1648 : 3565410000 : int uncertain = 0;
1649 [ + + ]: 3565410000 : if (((jl_datatype_t*)x)->name != ((jl_datatype_t*)y)->name) {
1650 [ + + + + ]: 2480240000 : if (jl_is_type_type(x) && jl_is_kind(y)) {
1651 : 4244420 : jl_value_t *t0 = jl_tparam0(x);
1652 [ + + ]: 4244420 : if (jl_is_typevar(t0))
1653 : 2280990 : return 0;
1654 : 1963430 : *subtype = jl_typeof(t0) == y;
1655 : 1963430 : return 1;
1656 : : }
1657 [ + + ]: 2476000000 : if (jl_is_type_type(y)) {
1658 : 225504000 : jl_value_t *t0 = jl_tparam0(y);
1659 [ - + ]: 225504000 : assert(!jl_is_type_type(x));
1660 [ + + + + ]: 225504000 : if (jl_is_kind(x) && jl_is_typevar(t0))
1661 : 6524540 : return 0;
1662 : 218979000 : *subtype = 0;
1663 : 218979000 : return 1;
1664 : : }
1665 : 2250490000 : jl_datatype_t *temp = (jl_datatype_t*)x;
1666 [ + + ]: 5121180000 : while (temp->name != ((jl_datatype_t*)y)->name) {
1667 : 4447350000 : temp = temp->super;
1668 [ + + ]: 4447350000 : if (temp == NULL) // invalid state during type declaration
1669 : 1 : return 0;
1670 [ + + ]: 4447350000 : if (temp == jl_any_type) {
1671 : 1576660000 : *subtype = 0;
1672 : 1576660000 : return 1;
1673 : : }
1674 : : }
1675 [ + + + + ]: 673830000 : if (obvious_subtype((jl_value_t*)temp, y, y0, subtype) && *subtype)
1676 : 327060000 : return 1;
1677 : 50540300 : return 0;
1678 : : }
1679 [ + + + + ]: 1085170000 : if (!iscov && !((jl_datatype_t*)x)->hasfreetypevars) {
1680 : : // by transitivity, if `wrapper <: y`, then `x <: y` if x is a leaf type of its name
1681 [ - + - - ]: 198584000 : if (obvious_subtype(((jl_datatype_t*)x)->name->wrapper, y, y0, subtype) && *subtype)
1682 : 0 : return 1;
1683 : : }
1684 : 1085170000 : int i, npx = jl_nparams(x), npy = jl_nparams(y);
1685 : 1085170000 : jl_vararg_kind_t vx = JL_VARARG_NONE;
1686 : 1085170000 : jl_vararg_kind_t vy = JL_VARARG_NONE;
1687 : 1085170000 : jl_value_t *vxt = NULL;
1688 : 1085170000 : int nparams_expanded_x = npx;
1689 : 1085170000 : int nparams_expanded_y = npy;
1690 [ + + ]: 1085170000 : if (istuple) {
1691 [ + + ]: 478083000 : if (npx > 0) {
1692 : 470227000 : jl_value_t *xva = jl_tparam(x, npx - 1);
1693 : 470227000 : vx = jl_vararg_kind(xva);
1694 [ + + ]: 470227000 : if (vx != JL_VARARG_NONE) {
1695 : 77719200 : vxt = jl_unwrap_vararg(xva);
1696 : 77719200 : nparams_expanded_x -= 1;
1697 [ + + ]: 77719200 : if (vx == JL_VARARG_INT)
1698 : 13 : nparams_expanded_x += jl_vararg_length(xva);
1699 : : }
1700 : : }
1701 [ + + ]: 478083000 : if (npy > 0) {
1702 : 474217000 : jl_value_t *yva = jl_tparam(y, npy - 1);
1703 : 474217000 : vy = jl_vararg_kind(yva);
1704 [ + + ]: 474217000 : if (vy != JL_VARARG_NONE) {
1705 : 111295000 : nparams_expanded_y -= 1;
1706 [ + + ]: 111295000 : if (vy == JL_VARARG_INT)
1707 : 8 : nparams_expanded_y += jl_vararg_length(yva);
1708 : : }
1709 : : }
1710 : : // if the nparams aren't equal, or at least one of them is a typevar (uncertain), they may be obviously disjoint
1711 [ + + + + : 478083000 : if (nparams_expanded_x != nparams_expanded_y || (vx != JL_VARARG_NONE && vx != JL_VARARG_INT) || (vy != JL_VARARG_NONE && vy != JL_VARARG_INT)) {
+ + + + +
+ ]
1712 : : // we have a stronger bound on x if:
1713 [ + + + + ]: 159475000 : if (vy == JL_VARARG_NONE || vy == JL_VARARG_INT) { // the bound on y is certain
1714 [ + + + - : 48180600 : if (vx == JL_VARARG_NONE || vx == JL_VARARG_INT || vx == JL_VARARG_UNBOUND || // and the bound on x is also certain
+ + + + ]
1715 [ + + ]: 5894110 : nparams_expanded_x > nparams_expanded_y || npx > nparams_expanded_y) { // or x is unknown, but definitely longer than y
1716 : 44604200 : *subtype = 0;
1717 : 44604200 : return 1; // number of fixed parameters in x are more than declared in y
1718 : : }
1719 : : }
1720 [ + + ]: 114871000 : if (nparams_expanded_x < nparams_expanded_y) {
1721 : 16868300 : *subtype = 0;
1722 : 16868300 : return 1; // number of fixed parameters in x could be fewer than in y
1723 : : }
1724 : 98002700 : uncertain = 1;
1725 : : }
1726 : : }
1727 [ - + ]: 607085000 : else if (npx != npy) {
1728 : 0 : *subtype = 0;
1729 : 0 : return 1;
1730 : : }
1731 : :
1732 : : // inspect the fixed parameters in y against x
1733 [ + + ]: 2235150000 : for (i = 0; i < npy - (vy == JL_VARARG_NONE ? 0 : 1); i++) {
1734 [ + + ]: 1675760000 : jl_value_t *a = i >= (npx - (vx == JL_VARARG_NONE ? 0 : 1)) ? vxt : jl_tparam(x, i);
1735 : 1675760000 : jl_value_t *b = jl_tparam(y, i);
1736 [ + + + + ]: 1675760000 : if (iscov || jl_is_typevar(b)) {
1737 [ + + ]: 1163510000 : if (obvious_subtype(a, b, y0, subtype)) {
1738 [ + + ]: 707720000 : if (!*subtype)
1739 : 239312000 : return 1;
1740 [ + + ]: 468408000 : if (jl_has_free_typevars(b)) // b is actually more constrained that this
1741 : 17988200 : uncertain = 1;
1742 : : }
1743 : : else {
1744 : 455786000 : uncertain = 1;
1745 : : }
1746 : : }
1747 : : else {
1748 [ + + ]: 512251000 : if (!obviously_egal(a, b)) {
1749 [ + + ]: 459602000 : if (obvious_subtype(a, b, y0, subtype)) {
1750 [ + + ]: 213368000 : if (!*subtype)
1751 : 207254000 : return 1;
1752 [ + + ]: 6114010 : if (jl_has_free_typevars(b)) // b is actually more constrained that this
1753 : 3538 : uncertain = 1;
1754 : : }
1755 : : else {
1756 : 246234000 : uncertain = 1;
1757 : : }
1758 [ + + + + ]: 252348000 : if (!jl_has_free_typevars(b) && obvious_subtype(b, a, y0, subtype)) {
1759 [ + + ]: 18073700 : if (!*subtype)
1760 : 17737500 : return 1;
1761 [ + + ]: 336236 : if (jl_has_free_typevars(a)) // a is actually more constrained that this
1762 : 4502 : uncertain = 1;
1763 : : }
1764 : : else {
1765 : 234274000 : uncertain = 1;
1766 : : }
1767 : : }
1768 : : }
1769 : : }
1770 [ + + ]: 559392000 : if (i < nparams_expanded_x) {
1771 : : // there are elements left in x (possibly just a Vararg), check them against the Vararg tail of y too
1772 [ + - + - : 61198000 : assert(vy != JL_VARARG_NONE && istuple && iscov);
+ - ]
1773 [ + + + + ]: 61198000 : jl_value_t *a1 = (vx != JL_VARARG_NONE && i >= npx - 1) ? vxt : jl_tparam(x, i);
1774 : 61198000 : jl_value_t *b = jl_unwrap_vararg(jl_tparam(y, i));
1775 [ + + ]: 61198000 : if (jl_is_typevar(b)) {
1776 : 578033 : jl_value_t *body = find_var_body(y0, (jl_tvar_t*)b);
1777 [ + + ]: 578033 : if (body == NULL)
1778 : 5088 : body = y0;
1779 [ + + ]: 578033 : if (var_occurs_invariant(body, (jl_tvar_t*)b, 0))
1780 : 1112 : return 0;
1781 : : }
1782 [ + + + + : 61196900 : if (nparams_expanded_x > npy && jl_is_typevar(b) && concrete_min(a1) > 1) {
+ + ]
1783 : : // diagonal rule for 2 or more elements: they must all be concrete on the LHS
1784 : 54642 : *subtype = 0;
1785 : 54642 : return 1;
1786 : : }
1787 : 61142300 : jl_value_t *a1u = jl_unwrap_unionall(a1);
1788 [ + + + + ]: 61142300 : if (jl_is_type_type(a1u) && jl_is_type(jl_tparam0(a1u))) {
1789 : 292253 : a1 = jl_typeof(jl_tparam0(a1u));
1790 : : }
1791 [ + + ]: 387107000 : for (; i < nparams_expanded_x; i++) {
1792 [ + + + + ]: 339399000 : jl_value_t *a = (vx != JL_VARARG_NONE && i >= npx - 1) ? vxt : jl_tparam(x, i);
1793 [ + + + + ]: 339399000 : if (i > npy && jl_is_typevar(b)) { // i == npy implies a == a1
1794 : : // diagonal rule: all the later parameters are also constrained to be type-equal to the first
1795 : 2175910 : jl_value_t *a2 = a;
1796 : 2175910 : jl_value_t *au = jl_unwrap_unionall(a);
1797 [ + + + + ]: 2175910 : if (jl_is_type_type(au) && jl_is_type(jl_tparam0(au))) {
1798 : : // if a is exactly Type{T}, then use the concrete typeof(T) instead here
1799 : 2665 : a2 = jl_typeof(jl_tparam0(au));
1800 : : }
1801 [ + + ]: 2175910 : if (!obviously_egal(a1, a2)) {
1802 [ + + ]: 63045 : if (obvious_subtype(a2, a1, y0, subtype)) {
1803 [ + + ]: 36038 : if (!*subtype)
1804 : 36034 : return 1;
1805 [ - + ]: 4 : if (jl_has_free_typevars(a1)) // a1 is actually more constrained that this
1806 : 0 : uncertain = 1;
1807 : : }
1808 : : else {
1809 : 27007 : uncertain = 1;
1810 : : }
1811 [ + + ]: 27011 : if (obvious_subtype(a1, a2, y0, subtype)) {
1812 [ + + ]: 20067 : if (!*subtype)
1813 : 8119 : return 1;
1814 [ - + ]: 11948 : if (jl_has_free_typevars(a2)) // a2 is actually more constrained that this
1815 : 0 : uncertain = 1;
1816 : : }
1817 : : else {
1818 : 6944 : uncertain = 1;
1819 : : }
1820 : : }
1821 : : }
1822 [ + + ]: 339354000 : if (obvious_subtype(a, b, y0, subtype)) {
1823 [ + + ]: 308979000 : if (!*subtype)
1824 : 13389400 : return 1;
1825 [ + + ]: 295590000 : if (jl_has_free_typevars(b)) // b is actually more constrained that this
1826 : 3801 : uncertain = 1;
1827 : : }
1828 : : else {
1829 : 30375000 : uncertain = 1;
1830 : : }
1831 : : }
1832 : : }
1833 [ + + ]: 545903000 : if (uncertain)
1834 : 534986000 : return 0;
1835 : 10916600 : *subtype = 1;
1836 : 10916600 : return 1;
1837 : : }
1838 : : }
1839 : 0 : return 0;
1840 : : }
1841 : :
1842 : 2076350000 : JL_DLLEXPORT int jl_obvious_subtype(jl_value_t *x, jl_value_t *y, int *subtype)
1843 : : {
1844 : 2076350000 : return obvious_subtype(x, y, y, subtype);
1845 : : }
1846 : :
1847 : : // `env` is NULL if no typevar information is requested, or otherwise
1848 : : // points to a rooted array of length `jl_subtype_env_size(y)`.
1849 : : // This will be populated with the values of variables from unionall
1850 : : // types at the outer level of `y`.
1851 : 2584290000 : JL_DLLEXPORT int jl_subtype_env(jl_value_t *x, jl_value_t *y, jl_value_t **env, int envsz)
1852 : : {
1853 : : jl_stenv_t e;
1854 [ + + + + ]: 2584290000 : if (y == (jl_value_t*)jl_any_type || x == jl_bottom_type)
1855 : 136789000 : return 1;
1856 [ + + ]: 2447500000 : if (x == y ||
1857 [ + + ]: 1892310000 : (jl_typeof(x) == jl_typeof(y) &&
1858 [ + + + + : 1414200000 : (jl_is_unionall(y) || jl_is_uniontype(y)) &&
+ + ]
1859 : 95183600 : jl_types_egal(x, y))) {
1860 [ + + ]: 559045000 : if (envsz != 0) { // quickly copy env from x
1861 : 915994 : jl_unionall_t *ua = (jl_unionall_t*)x;
1862 : : int i;
1863 [ + + ]: 2055980 : for (i = 0; i < envsz; i++) {
1864 [ - + ]: 1139980 : assert(jl_is_unionall(ua));
1865 : 1139980 : env[i] = (jl_value_t*)ua->var;
1866 : 1139980 : ua = (jl_unionall_t*)ua->body;
1867 : : }
1868 : : }
1869 : 559045000 : return 1;
1870 : : }
1871 : 1888460000 : int obvious_subtype = 2;
1872 [ + + ]: 1888460000 : if (jl_obvious_subtype(x, y, &obvious_subtype)) {
1873 : : #ifdef NDEBUG
1874 : : if (obvious_subtype == 0)
1875 : : return obvious_subtype;
1876 : : else if (envsz == 0)
1877 : : return obvious_subtype;
1878 : : #endif
1879 : : }
1880 : : else {
1881 : 227122000 : obvious_subtype = 3;
1882 : : }
1883 : 1888460000 : init_stenv(&e, env, envsz);
1884 : 1888460000 : int subtype = forall_exists_subtype(x, y, &e, 0);
1885 [ + + + + : 1888460000 : assert(obvious_subtype == 3 || obvious_subtype == subtype || jl_has_free_typevars(x) || jl_has_free_typevars(y));
- + - - ]
1886 : : #ifndef NDEBUG
1887 [ + + + + : 1888460000 : if (obvious_subtype == 0 || (obvious_subtype == 1 && envsz == 0))
+ + ]
1888 : 1661290000 : subtype = obvious_subtype; // this ensures that running in a debugger doesn't change the result
1889 : : #endif
1890 : 1888460000 : return subtype;
1891 : : }
1892 : :
1893 : 52823600 : static int subtype_in_env_(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int invdepth, int Rinvdepth)
1894 : : {
1895 : : jl_stenv_t e2;
1896 : 52823600 : init_stenv(&e2, NULL, 0);
1897 : 52823600 : e2.vars = e->vars;
1898 : 52823600 : e2.intersection = e->intersection;
1899 : 52823600 : e2.ignore_free = e->ignore_free;
1900 : 52823600 : e2.invdepth = invdepth;
1901 : 52823600 : e2.Rinvdepth = Rinvdepth;
1902 : 52823600 : e2.envsz = e->envsz;
1903 : 52823600 : e2.envout = e->envout;
1904 : 52823600 : e2.envidx = e->envidx;
1905 : 52823600 : return forall_exists_subtype(x, y, &e2, 0);
1906 : : }
1907 : :
1908 : 23702200 : static int subtype_in_env(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
1909 : : {
1910 : 23702200 : return subtype_in_env_(x, y, e, e->invdepth, e->Rinvdepth);
1911 : : }
1912 : :
1913 : 29121400 : static int subtype_bounds_in_env(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int R, int d)
1914 : : {
1915 [ + + + + ]: 29121400 : return subtype_in_env_(x, y, e, R ? e->invdepth : d, R ? d : e->Rinvdepth);
1916 : : }
1917 : :
1918 : 2535070000 : JL_DLLEXPORT int jl_subtype(jl_value_t *x, jl_value_t *y)
1919 : : {
1920 : 2535070000 : return jl_subtype_env(x, y, NULL, 0);
1921 : : }
1922 : :
1923 : 2856850000 : JL_DLLEXPORT int jl_types_equal(jl_value_t *a, jl_value_t *b)
1924 : : {
1925 [ + + ]: 2856850000 : if (a == b)
1926 : 32553300 : return 1;
1927 [ + + + + ]: 2824300000 : if (jl_typeof(a) == jl_typeof(b) && jl_types_egal(a, b))
1928 : 9033020 : return 1;
1929 [ + + ]: 2815270000 : if (obviously_unequal(a, b))
1930 : 2721310000 : return 0;
1931 : : // the following is an interleaved version of:
1932 : : // return jl_subtype(a, b) && jl_subtype(b, a)
1933 : : // where we try to do the fast checks before the expensive ones
1934 [ + + + + ]: 93954800 : if (jl_is_datatype(a) && !jl_is_concrete_type(b)) {
1935 : : // if one type looks simpler, check it on the right
1936 : : // first in order to reject more quickly.
1937 : 35432200 : jl_value_t *temp = a;
1938 : 35432200 : a = b;
1939 : 35432200 : b = temp;
1940 : : }
1941 : : // first check if a <: b has an obvious answer
1942 : 93954800 : int subtype_ab = 2;
1943 [ + + - + ]: 93954800 : if (b == (jl_value_t*)jl_any_type || a == jl_bottom_type) {
1944 : 15265 : subtype_ab = 1;
1945 : : }
1946 [ + + ]: 93939500 : else if (jl_obvious_subtype(a, b, &subtype_ab)) {
1947 : : #ifdef NDEBUG
1948 : : if (subtype_ab == 0)
1949 : : return 0;
1950 : : #endif
1951 : : }
1952 : : else {
1953 : 34949000 : subtype_ab = 3;
1954 : : }
1955 : : // next check if b <: a has an obvious answer
1956 : 93954800 : int subtype_ba = 2;
1957 [ + - + + ]: 93954800 : if (a == (jl_value_t*)jl_any_type || b == jl_bottom_type) {
1958 : 168 : subtype_ba = 1;
1959 : : }
1960 [ + + ]: 93954600 : else if (jl_obvious_subtype(b, a, &subtype_ba)) {
1961 : : #ifdef NDEBUG
1962 : : if (subtype_ba == 0)
1963 : : return 0;
1964 : : #endif
1965 : : }
1966 : : else {
1967 : 34701400 : subtype_ba = 3;
1968 : : }
1969 : : // finally, do full subtyping for any inconclusive test
1970 : : jl_stenv_t e;
1971 : : #ifdef NDEBUG
1972 : : if (subtype_ab != 1)
1973 : : #endif
1974 : : {
1975 : 93954800 : init_stenv(&e, NULL, 0);
1976 : 93954800 : int subtype = forall_exists_subtype(a, b, &e, 0);
1977 [ + + - + : 93954800 : assert(subtype_ab == 3 || subtype_ab == subtype || jl_has_free_typevars(a) || jl_has_free_typevars(b));
- - - - ]
1978 : : #ifndef NDEBUG
1979 [ + + + + ]: 93954800 : if (subtype_ab != 0 && subtype_ab != 1) // ensures that running in a debugger doesn't change the result
1980 : : #endif
1981 : 34949000 : subtype_ab = subtype;
1982 : : #ifdef NDEBUG
1983 : : if (subtype_ab == 0)
1984 : : return 0;
1985 : : #endif
1986 : : }
1987 : : #ifdef NDEBUG
1988 : : if (subtype_ba != 1)
1989 : : #endif
1990 : : {
1991 : 93954800 : init_stenv(&e, NULL, 0);
1992 : 93954800 : int subtype = forall_exists_subtype(b, a, &e, 0);
1993 [ + + - + : 93954800 : assert(subtype_ba == 3 || subtype_ba == subtype || jl_has_free_typevars(a) || jl_has_free_typevars(b));
- - - - ]
1994 : : #ifndef NDEBUG
1995 [ + + + + ]: 93954800 : if (subtype_ba != 0 && subtype_ba != 1) // ensures that running in a debugger doesn't change the result
1996 : : #endif
1997 : 34701400 : subtype_ba = subtype;
1998 : : }
1999 : : // all tests successful
2000 [ + + + + ]: 93954800 : return subtype_ab && subtype_ba;
2001 : : }
2002 : :
2003 : 5882170 : JL_DLLEXPORT int jl_is_not_broken_subtype(jl_value_t *a, jl_value_t *b)
2004 : : {
2005 : : // TODO: the final commented out check here isn't correct; it should be closer to the
2006 : : // `issingletype` check used by `isnotbrokensubtype` in `base/compiler/typeutils.jl`
2007 [ + + + + ]: 5882170 : return !jl_is_kind(b) || !jl_is_type_type(a); // || jl_is_datatype_singleton((jl_datatype_t*)jl_tparam0(a));
2008 : : }
2009 : :
2010 : 313097000 : int jl_tuple1_isa(jl_value_t *child1, jl_value_t **child, size_t cl, jl_datatype_t *pdt)
2011 : : {
2012 [ + + + + ]: 313097000 : if (jl_is_tuple_type(pdt) && !jl_is_va_tuple(pdt)) {
2013 [ + + ]: 311909000 : if (cl != jl_nparams(pdt))
2014 : 6716 : return 0;
2015 : : size_t i;
2016 [ + + ]: 311902000 : if (!jl_isa(child1, jl_tparam(pdt, 0)))
2017 : 188 : return 0;
2018 [ + + ]: 600697000 : for (i = 1; i < cl; i++) {
2019 [ + + ]: 327569000 : if (!jl_isa(child[i - 1], jl_tparam(pdt, i)))
2020 : 38774300 : return 0;
2021 : : }
2022 : 273128000 : return 1;
2023 : : }
2024 : 1187940 : jl_value_t *tu = (jl_value_t*)arg_type_tuple(child1, child, cl);
2025 : : int ans;
2026 : 1187940 : JL_GC_PUSH1(&tu);
2027 : 1187940 : ans = jl_subtype(tu, (jl_value_t*)pdt);
2028 : 1187940 : JL_GC_POP();
2029 : 1187940 : return ans;
2030 : : }
2031 : :
2032 : 2931 : int jl_tuple_isa(jl_value_t **child, size_t cl, jl_datatype_t *pdt)
2033 : : {
2034 [ + + ]: 2931 : if (cl == 0) {
2035 [ + - ]: 1 : if (pdt == jl_emptytuple_type)
2036 : 1 : return 1;
2037 [ # # # # : 0 : if (jl_is_tuple_type(pdt) && (jl_nparams(pdt) != 1 || !jl_is_va_tuple(pdt)))
# # ]
2038 : 0 : return 0;
2039 : 0 : return jl_isa(jl_emptytuple, (jl_value_t*)pdt);
2040 : : }
2041 : 2930 : return jl_tuple1_isa(child[0], &child[1], cl, pdt);
2042 : : }
2043 : :
2044 : : // returns true if the intersection of `t` and `Type` is non-empty and not a kind
2045 : : // this is sufficient to determine if `isa(x, T)` can instead simply check for `typeof(x) <: T`
2046 : 26751800 : int jl_has_intersect_type_not_kind(jl_value_t *t)
2047 : : {
2048 : 26751800 : t = jl_unwrap_unionall(t);
2049 [ - + ]: 26751800 : if (t == (jl_value_t*)jl_any_type)
2050 : 0 : return 1;
2051 [ + + ]: 26751800 : if (jl_is_uniontype(t)) {
2052 [ + + + + ]: 727166 : return jl_has_intersect_type_not_kind(((jl_uniontype_t*)t)->a) ||
2053 : 317230 : jl_has_intersect_type_not_kind(((jl_uniontype_t*)t)->b);
2054 : : }
2055 [ - + ]: 26341900 : if (jl_is_typevar(t)) {
2056 : 0 : return jl_has_intersect_type_not_kind(((jl_tvar_t*)t)->ub);
2057 : : }
2058 [ + - ]: 26341900 : if (jl_is_datatype(t)) {
2059 [ + + ]: 26341900 : if (((jl_datatype_t*)t)->name == jl_type_typename)
2060 : 25302200 : return 1;
2061 : : }
2062 : 1039700 : return 0;
2063 : : }
2064 : :
2065 : 3707640000 : JL_DLLEXPORT int jl_isa(jl_value_t *x, jl_value_t *t)
2066 : : {
2067 [ + + + + ]: 3707640000 : if (jl_typeis(x,t) || t == (jl_value_t*)jl_any_type)
2068 : 2840830000 : return 1;
2069 [ + + ]: 866803000 : if (jl_is_type(x)) {
2070 [ + + ]: 613587000 : if (t == (jl_value_t*)jl_type_type)
2071 : 574383000 : return 1;
2072 [ + + ]: 39204200 : if (!jl_has_free_typevars(x)) {
2073 [ + + ]: 39093400 : if (jl_is_concrete_type(t))
2074 : 2419350 : return 0;
2075 [ + + ]: 36674000 : if (jl_is_type_type(t))
2076 : 2210200 : return jl_types_equal(x, jl_tparam0(t));
2077 : 34463800 : jl_value_t *t2 = jl_unwrap_unionall(t);
2078 [ + + ]: 34463800 : if (jl_is_datatype(t2)) {
2079 [ + + ]: 30496200 : if (((jl_datatype_t*)t2)->name == jl_type_typename) {
2080 : 28213900 : jl_value_t *tp = jl_tparam0(t2);
2081 [ + + ]: 28213900 : if (jl_is_typevar(tp)) {
2082 [ + + ]: 3013910 : if (((jl_tvar_t*)tp)->lb == jl_bottom_type) {
2083 [ + + ]: 6027420 : while (jl_is_typevar(tp))
2084 : 3013710 : tp = ((jl_tvar_t*)tp)->ub;
2085 [ + + ]: 3013710 : if (!jl_has_free_typevars(tp))
2086 : 3011970 : return jl_subtype(x, tp);
2087 : : }
2088 [ + - ]: 202 : else if (((jl_tvar_t*)tp)->ub == (jl_value_t*)jl_any_type) {
2089 [ + + ]: 404 : while (jl_is_typevar(tp))
2090 : 202 : tp = ((jl_tvar_t*)tp)->lb;
2091 [ + - ]: 202 : if (!jl_has_free_typevars(tp))
2092 : 202 : return jl_subtype(tp, x);
2093 : : }
2094 : : }
2095 : : }
2096 : : else {
2097 : 2282290 : return 0;
2098 : : }
2099 : : }
2100 [ + + ]: 29169400 : if (jl_subtype(jl_typeof(x), t))
2101 : 3675210 : return 1;
2102 [ + + ]: 25494100 : if (jl_has_intersect_type_not_kind(t2)) {
2103 : 25297500 : JL_GC_PUSH1(&x);
2104 : 25297500 : x = (jl_value_t*)jl_wrap_Type(x); // TODO jb/subtype avoid jl_wrap_Type
2105 : 25297500 : int ans = jl_subtype(x, t);
2106 : 25297500 : JL_GC_POP();
2107 : 25297500 : return ans;
2108 : : }
2109 : 196601 : return 0;
2110 : : }
2111 : : }
2112 [ + + + + ]: 253326000 : if (jl_is_concrete_type(t) && jl_type_equality_is_identity(jl_typeof(x), t))
2113 : 26396200 : return 0;
2114 : 226930000 : return jl_subtype(jl_typeof(x), t);
2115 : : }
2116 : :
2117 : : // type intersection
2118 : :
2119 : : static jl_value_t *intersect(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param);
2120 : :
2121 : : static jl_value_t *intersect_all(jl_value_t *x, jl_value_t *y, jl_stenv_t *e);
2122 : :
2123 : : // intersect in nested union environment, similar to subtype_ccheck
2124 : 25323300 : static jl_value_t *intersect_aside(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int R, int d)
2125 : : {
2126 : : // band-aid for #30335
2127 [ + + + + ]: 25323300 : if (x == (jl_value_t*)jl_any_type && !jl_is_typevar(y))
2128 : 9093520 : return y;
2129 [ + + + + ]: 16229800 : if (y == (jl_value_t*)jl_any_type && !jl_is_typevar(x))
2130 : 1870570 : return x;
2131 : :
2132 : 14359200 : jl_saved_unionstate_t oldRunions; push_unionstate(&oldRunions, &e->Runions);
2133 : 14359200 : int savedepth = e->invdepth, Rsavedepth = e->Rinvdepth;
2134 : : // TODO: this doesn't quite make sense
2135 : 14359200 : e->invdepth = e->Rinvdepth = d;
2136 : :
2137 : 14359200 : jl_value_t *res = intersect_all(x, y, e);
2138 : :
2139 : 14359200 : pop_unionstate(&e->Runions, &oldRunions);
2140 : 14359200 : e->invdepth = savedepth;
2141 : 14359200 : e->Rinvdepth = Rsavedepth;
2142 : 14359200 : return res;
2143 : : }
2144 : :
2145 : 55594100 : static jl_value_t *intersect_union(jl_value_t *x, jl_uniontype_t *u, jl_stenv_t *e, int8_t R, int param)
2146 : : {
2147 [ + + + + : 55594100 : if (param == 2 || (!jl_has_free_typevars(x) && !jl_has_free_typevars((jl_value_t*)u))) {
+ + ]
2148 : 18726700 : jl_value_t *a=NULL, *b=NULL;
2149 : 18726700 : JL_GC_PUSH2(&a, &b);
2150 : 18726700 : jl_saved_unionstate_t oldRunions; push_unionstate(&oldRunions, &e->Runions);
2151 [ + + ]: 18726700 : a = R ? intersect_all(x, u->a, e) : intersect_all(u->a, x, e);
2152 [ + + ]: 18726700 : b = R ? intersect_all(x, u->b, e) : intersect_all(u->b, x, e);
2153 : 18726700 : pop_unionstate(&e->Runions, &oldRunions);
2154 : 18726700 : jl_value_t *i = simple_join(a,b);
2155 : 18726700 : JL_GC_POP();
2156 : 18726700 : return i;
2157 : : }
2158 : 36867400 : jl_value_t *choice = pick_union_element((jl_value_t*)u, e, 1);
2159 : : // try all possible choices in covariant position; union them all together at the top level
2160 [ + + ]: 36867400 : return R ? intersect(x, choice, e, param) : intersect(choice, x, e, param);
2161 : : }
2162 : :
2163 : : // set a variable to a non-type constant
2164 : 1489360 : static jl_value_t *set_var_to_const(jl_varbinding_t *bb, jl_value_t *v JL_MAYBE_UNROOTED, jl_varbinding_t *othervar)
2165 : : {
2166 : 1489360 : int offset = bb->offset;
2167 [ + + + - ]: 1489360 : if (othervar && offset == 0)
2168 : 123291 : offset = -othervar->offset;
2169 [ + + - + ]: 1489360 : assert(!othervar || othervar->offset == -offset);
2170 [ + + + + ]: 1489360 : if (bb->lb == jl_bottom_type && bb->ub == (jl_value_t*)jl_any_type) {
2171 [ + + ]: 1215360 : if (jl_is_long(v))
2172 : 960019 : v = jl_box_long(jl_unbox_long(v) + offset);
2173 : 1215360 : bb->lb = bb->ub = v;
2174 : : }
2175 [ + + + + ]: 274009 : else if (jl_is_long(v) && jl_is_long(bb->lb)) {
2176 [ + + ]: 266649 : if (jl_unbox_long(v) != jl_unbox_long(bb->lb))
2177 : 6626 : return jl_bottom_type;
2178 : : }
2179 [ + + ]: 7360 : else if (!jl_egal(v, bb->lb)) {
2180 : 5639 : return jl_bottom_type;
2181 : : }
2182 : 1477100 : return v;
2183 : : }
2184 : :
2185 : 27579 : static jl_value_t *bound_var_below(jl_tvar_t *tv, jl_varbinding_t *bb, jl_stenv_t *e) {
2186 [ + + ]: 27579 : if (!bb)
2187 : 4 : return (jl_value_t*)tv;
2188 [ + + ]: 27575 : if (bb->depth0 != e->invdepth)
2189 : 4948 : return jl_bottom_type;
2190 : 22627 : record_var_occurrence(bb, e, 2);
2191 [ + + ]: 22627 : if (jl_is_long(bb->lb)) {
2192 [ + + ]: 2488 : if (bb->offset == 0)
2193 : 1326 : return bb->lb;
2194 [ + + ]: 1162 : if (jl_unbox_long(bb->lb) < bb->offset)
2195 : 25 : return jl_bottom_type;
2196 : 1137 : return jl_box_long(jl_unbox_long(bb->lb) - bb->offset);
2197 : : }
2198 : 20139 : return (jl_value_t*)tv;
2199 : : }
2200 : :
2201 : 1533280 : static int try_subtype_in_env(jl_value_t *a, jl_value_t *b, jl_stenv_t *e, int R, int d)
2202 : : {
2203 : 1533280 : jl_value_t *root=NULL; jl_savedenv_t se;
2204 : 1533280 : JL_GC_PUSH1(&root);
2205 : 1533280 : save_env(e, &root, &se);
2206 : 1533280 : int ret = subtype_bounds_in_env(a, b, e, R, d);
2207 : 1533280 : restore_env(e, root, &se);
2208 : 1533280 : free_env(&se);
2209 : 1533280 : JL_GC_POP();
2210 : 1533280 : return ret;
2211 : : }
2212 : :
2213 : 595666 : static void set_bound(jl_value_t **bound, jl_value_t *val, jl_tvar_t *v, jl_stenv_t *e) JL_NOTSAFEPOINT
2214 : : {
2215 [ + + ]: 595666 : if (in_union(val, (jl_value_t*)v))
2216 : 9 : return;
2217 : 595657 : jl_varbinding_t *btemp = e->vars;
2218 [ + + ]: 1769100 : while (btemp != NULL) {
2219 [ + + + + : 1229220 : if ((btemp->lb == (jl_value_t*)v || btemp->ub == (jl_value_t*)v) &&
+ + ]
2220 : 55770 : in_union(val, (jl_value_t*)btemp->var))
2221 : 10 : return;
2222 : 1173440 : btemp = btemp->prev;
2223 : : }
2224 : 595647 : *bound = val;
2225 : : }
2226 : :
2227 : : // subtype, treating all vars as existential
2228 : 36787600 : static int subtype_in_env_existential(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int R, int d)
2229 : : {
2230 : 36787600 : jl_varbinding_t *v = e->vars;
2231 : 36787600 : int len = 0;
2232 [ + + + + ]: 36787600 : if (x == jl_bottom_type || y == (jl_value_t*)jl_any_type)
2233 : 9199500 : return 1;
2234 [ + + ]: 155543000 : while (v != NULL) {
2235 : 127954000 : len++;
2236 : 127954000 : v = v->prev;
2237 : : }
2238 : 27588100 : int8_t *rs = (int8_t*)malloc_s(len);
2239 : 27588100 : int n = 0;
2240 : 27588100 : v = e->vars;
2241 [ + + ]: 155543000 : while (n < len) {
2242 [ - + ]: 127954000 : assert(v != NULL);
2243 : 127954000 : rs[n++] = v->right;
2244 : 127954000 : v->right = 1;
2245 : 127954000 : v = v->prev;
2246 : : }
2247 : 27588100 : int issub = subtype_bounds_in_env(x, y, e, R, d);
2248 : 27588100 : n = 0; v = e->vars;
2249 [ + + ]: 155543000 : while (n < len) {
2250 [ - + ]: 127954000 : assert(v != NULL);
2251 : 127954000 : v->right = rs[n++];
2252 : 127954000 : v = v->prev;
2253 : : }
2254 : 27588100 : free(rs);
2255 : 27588100 : return issub;
2256 : : }
2257 : :
2258 : : // See if var y is reachable from x via bounds; used to avoid cycles.
2259 : 108956000 : static int reachable_var(jl_value_t *x, jl_tvar_t *y, jl_stenv_t *e)
2260 : : {
2261 [ + + ]: 108956000 : if (in_union(x, (jl_value_t*)y))
2262 : 8249 : return 1;
2263 [ + + ]: 108948000 : if (!jl_is_typevar(x))
2264 : 94336000 : return 0;
2265 : 14611800 : jl_varbinding_t *xv = lookup(e, (jl_tvar_t*)x);
2266 [ + + ]: 14611800 : if (xv == NULL)
2267 : 1539 : return 0;
2268 [ + + - + ]: 14610200 : return reachable_var(xv->ub, y, e) || reachable_var(xv->lb, y, e);
2269 : : }
2270 : :
2271 : : // check whether setting v == t implies v == SomeType{v}, which is unsatisfiable.
2272 : 1330370 : static int check_unsat_bound(jl_value_t *t, jl_tvar_t *v, jl_stenv_t *e) JL_NOTSAFEPOINT
2273 : : {
2274 [ + + ]: 1330370 : if (var_occurs_inside(t, v, 0, 0))
2275 : 1235 : return 1;
2276 : 1329130 : jl_varbinding_t *btemp = e->vars;
2277 [ + + ]: 7062930 : while (btemp != NULL) {
2278 [ + + + - : 5736030 : if (btemp->lb == (jl_value_t*)v && btemp->ub == (jl_value_t*)v &&
+ + ]
2279 : 1173 : var_occurs_inside(t, btemp->var, 0, 0))
2280 : 1059 : return 1;
2281 : 5733800 : btemp = btemp->prev;
2282 : : }
2283 : 1328070 : return 0;
2284 : : }
2285 : :
2286 : 19223000 : static jl_value_t *intersect_var(jl_tvar_t *b, jl_value_t *a, jl_stenv_t *e, int8_t R, int param)
2287 : : {
2288 : 19223000 : jl_varbinding_t *bb = lookup(e, b);
2289 [ + + ]: 19223000 : if (bb == NULL)
2290 [ + + ]: 3996 : return R ? intersect_aside(a, b->ub, e, 1, 0) : intersect_aside(b->ub, a, e, 0, 0);
2291 [ + + - + ]: 19219000 : if (reachable_var(bb->lb, b, e) || reachable_var(bb->ub, b, e))
2292 : 1 : return a;
2293 [ + + + + ]: 19219000 : if (bb->lb == bb->ub && jl_is_typevar(bb->lb)) {
2294 : 187291 : return intersect(a, bb->lb, e, param);
2295 : : }
2296 [ + + + + ]: 19031700 : if (!jl_is_type(a) && !jl_is_typevar(a))
2297 : 1359320 : return set_var_to_const(bb, a, NULL);
2298 : 17672400 : int d = bb->depth0;
2299 : 17672400 : jl_value_t *root=NULL; jl_savedenv_t se;
2300 [ + + ]: 17672400 : if (param == 2) {
2301 : 12499200 : jl_value_t *ub = NULL;
2302 : 12499200 : JL_GC_PUSH2(&ub, &root);
2303 [ + + ]: 12499200 : if (!jl_has_free_typevars(a)) {
2304 : 8155090 : save_env(e, &root, &se);
2305 [ + + + + ]: 8155090 : int issub = subtype_in_env_existential(bb->lb, a, e, 0, d) && subtype_in_env_existential(a, bb->ub, e, 1, d);
2306 : 8155090 : restore_env(e, root, &se);
2307 : 8155090 : free_env(&se);
2308 [ + + ]: 8155090 : if (!issub) {
2309 : 3289980 : JL_GC_POP();
2310 : 3289980 : return jl_bottom_type;
2311 : : }
2312 : 4865100 : ub = a;
2313 : : }
2314 : : else {
2315 : 4344160 : e->triangular++;
2316 [ + + ]: 4344160 : ub = R ? intersect_aside(a, bb->ub, e, 1, d) : intersect_aside(bb->ub, a, e, 0, d);
2317 : 4344160 : e->triangular--;
2318 : 4344160 : save_env(e, &root, &se);
2319 : 4344160 : int issub = subtype_in_env_existential(bb->lb, ub, e, 0, d);
2320 : 4344160 : restore_env(e, root, &se);
2321 : 4344160 : free_env(&se);
2322 [ + + ]: 4344160 : if (!issub) {
2323 : 305678 : JL_GC_POP();
2324 : 305678 : return jl_bottom_type;
2325 : : }
2326 : : }
2327 [ + - ]: 8903590 : if (ub != (jl_value_t*)b) {
2328 [ + + ]: 8903590 : if (jl_has_free_typevars(ub)) {
2329 [ + + ]: 1300260 : if (check_unsat_bound(ub, b, e)) {
2330 : 2293 : JL_GC_POP();
2331 : 2293 : return jl_bottom_type;
2332 : : }
2333 : : }
2334 : 8901290 : bb->ub = ub;
2335 : 8901290 : bb->lb = ub;
2336 : : }
2337 : 8901290 : JL_GC_POP();
2338 : 8901290 : return ub;
2339 : : }
2340 [ + + ]: 5173130 : jl_value_t *ub = R ? intersect_aside(a, bb->ub, e, 1, d) : intersect_aside(bb->ub, a, e, 0, d);
2341 [ + + ]: 5173130 : if (ub == jl_bottom_type)
2342 : 2702980 : return jl_bottom_type;
2343 [ + + + + ]: 2470150 : if (bb->constraintkind == 1 || e->triangular) {
2344 [ + + + + ]: 485716 : if (e->triangular && check_unsat_bound(ub, b, e))
2345 : 1 : return jl_bottom_type;
2346 : 485715 : set_bound(&bb->ub, ub, b, e);
2347 : 485715 : return (jl_value_t*)b;
2348 : : }
2349 [ + + ]: 1984440 : else if (bb->constraintkind == 0) {
2350 : 1563110 : JL_GC_PUSH1(&ub);
2351 [ + + + + ]: 1563110 : if (!jl_is_typevar(a) && try_subtype_in_env(bb->ub, a, e, 0, d)) {
2352 : 871291 : JL_GC_POP();
2353 : 871291 : return (jl_value_t*)b;
2354 : : }
2355 : 691822 : JL_GC_POP();
2356 : 691822 : return ub;
2357 : : }
2358 [ - + ]: 421322 : assert(bb->constraintkind == 2);
2359 [ + + ]: 421322 : if (!jl_is_typevar(a)) {
2360 [ + + + + ]: 418995 : if (ub == a && bb->lb != jl_bottom_type)
2361 : 191288 : return ub;
2362 [ + + ]: 227707 : else if (jl_egal(bb->ub, bb->lb))
2363 : 117756 : return ub;
2364 : 109951 : set_bound(&bb->ub, ub, b, e);
2365 : : }
2366 : 112278 : return (jl_value_t*)b;
2367 : : }
2368 : :
2369 : : // test whether `var` occurs inside constructors. `want_inv` tests only inside
2370 : : // invariant constructors. `inside` means we are currently inside a constructor of the
2371 : : // requested kind.
2372 : 1077490000 : static int var_occurs_inside(jl_value_t *v, jl_tvar_t *var, int inside, int want_inv) JL_NOTSAFEPOINT
2373 : : {
2374 [ + + ]: 1077490000 : if (v == (jl_value_t*)var) {
2375 : 24979300 : return inside;
2376 : : }
2377 [ + + ]: 1052510000 : else if (jl_is_uniontype(v)) {
2378 [ + + + + ]: 125136000 : return var_occurs_inside(((jl_uniontype_t*)v)->a, var, inside, want_inv) ||
2379 : 62566800 : var_occurs_inside(((jl_uniontype_t*)v)->b, var, inside, want_inv);
2380 : : }
2381 [ + + ]: 989938000 : else if (jl_is_unionall(v)) {
2382 : 189090000 : jl_unionall_t *ua = (jl_unionall_t*)v;
2383 [ + + ]: 189090000 : if (ua->var == var)
2384 : 3122740 : return 0;
2385 [ + - + + ]: 185967000 : if (var_occurs_inside(ua->var->lb, var, inside, want_inv) || var_occurs_inside(ua->var->ub, var, inside, want_inv))
2386 : 3683 : return 1;
2387 : 185963000 : return var_occurs_inside(ua->body, var, inside, want_inv);
2388 : : }
2389 [ + + ]: 800848000 : else if (jl_is_vararg(v)) {
2390 : 17767800 : jl_vararg_t *vm = (jl_vararg_t*)v;
2391 [ + + ]: 17767800 : if (vm->T) {
2392 [ + + - + : 17767700 : if (var_occurs_inside(vm->T, var, inside || !want_inv, want_inv))
+ + ]
2393 : 2694 : return 1;
2394 [ + + + + ]: 17765000 : return vm->N && var_occurs_inside(vm->N, var, 1, want_inv);
2395 : : }
2396 : : }
2397 [ + + ]: 783080000 : else if (jl_is_datatype(v)) {
2398 : : size_t i;
2399 : 322373000 : int istuple = jl_is_tuple_type(v);
2400 [ + + ]: 626343000 : for (i=0; i < jl_nparams(v); i++) {
2401 [ + + + + : 304272000 : int ins_i = inside || !want_inv || !istuple;
+ + ]
2402 [ + + ]: 304272000 : if (var_occurs_inside(jl_tparam(v,i), var, ins_i, want_inv))
2403 : 302346 : return 1;
2404 : : }
2405 : : }
2406 : 782778000 : return 0;
2407 : : }
2408 : :
2409 : : // Caller might not have rooted `res`
2410 : 32357400 : static jl_value_t *finish_unionall(jl_value_t *res JL_MAYBE_UNROOTED, jl_varbinding_t *vb, jl_unionall_t *u, jl_stenv_t *e)
2411 : : {
2412 : 32357400 : jl_value_t *varval = NULL;
2413 : 32357400 : jl_tvar_t *newvar = vb->var;
2414 : 32357400 : JL_GC_PUSH2(&res, &newvar);
2415 : : // try to reduce var to a single value
2416 [ + + - + ]: 32357400 : if (jl_is_long(vb->ub) && jl_is_typevar(vb->lb)) {
2417 : 0 : varval = vb->ub;
2418 : : }
2419 [ + + ]: 32357400 : else if (obviously_egal(vb->lb, vb->ub)) {
2420 : : // given x<:T<:x, substitute x for T
2421 : 16918600 : varval = vb->ub;
2422 : : }
2423 : : // TODO: `vb.occurs_cov == 1` here allows substituting Tuple{<:X} => Tuple{X},
2424 : : // which is valid but changes some ambiguity errors so we don't need to do it yet.
2425 [ + + ]: 15438800 : else if ((/*vb->occurs_cov == 1 || */is_leaf_bound(vb->ub)) &&
2426 [ + + ]: 149823 : !var_occurs_invariant(u->body, u->var, 0)) {
2427 : : // replace T<:x with x in covariant position when possible
2428 : 116759 : varval = vb->ub;
2429 : : }
2430 : :
2431 [ + + ]: 32357400 : if (vb->intvalued) {
2432 [ + + + + ]: 37939 : if ((varval && jl_is_long(varval)) ||
2433 [ + + + + ]: 33473 : (vb->lb == jl_bottom_type && vb->ub == (jl_value_t*)jl_any_type) ||
2434 [ + + + - ]: 8049 : (jl_is_typevar(vb->lb) && vb->ub == vb->lb)) {
2435 : : // int-valued typevar must either be an Int, or have Bottom-Any bounds,
2436 : : // or be set equal to another typevar.
2437 : : }
2438 : : else {
2439 : 6 : JL_GC_POP();
2440 : 6 : return jl_bottom_type;
2441 : : }
2442 : : }
2443 : :
2444 : : // TODO: this can prevent us from matching typevar identities later
2445 [ + + + + : 32357400 : if (!varval && (vb->lb != vb->var->lb || vb->ub != vb->var->ub))
+ + ]
2446 : 1458890 : newvar = jl_new_typevar(vb->var->name, vb->lb, vb->ub);
2447 : :
2448 : : // remove/replace/rewrap free occurrences of this var in the environment
2449 : 32357400 : jl_varbinding_t *btemp = e->vars;
2450 : 32357400 : int wrap = 1;
2451 [ + + ]: 131715000 : while (btemp != NULL) {
2452 [ + + ]: 99357300 : if (jl_has_typevar(btemp->lb, vb->var)) {
2453 [ - + ]: 32941 : if (vb->lb == (jl_value_t*)btemp->var) {
2454 : 0 : JL_GC_POP();
2455 : 0 : return jl_bottom_type;
2456 : : }
2457 [ + + ]: 32941 : if (varval) {
2458 [ + - + + ]: 2610 : JL_TRY {
2459 : 1305 : btemp->lb = jl_substitute_var(btemp->lb, vb->var, varval);
2460 : : }
2461 [ # # ]: 0 : JL_CATCH {
2462 : 0 : res = jl_bottom_type;
2463 : : }
2464 : : }
2465 [ - + ]: 31636 : else if (btemp->lb == (jl_value_t*)vb->var)
2466 : 0 : btemp->lb = vb->lb;
2467 [ + + + - ]: 31636 : else if (btemp->depth0 == vb->depth0 && !jl_has_typevar(vb->lb, btemp->var) &&
2468 [ + - + - ]: 31631 : !jl_has_typevar(vb->ub, btemp->var) && jl_has_typevar(btemp->ub, vb->var)) {
2469 : : // if our variable is T, and some outer variable has constraint S = Ref{T},
2470 : : // move the `where T` outside `where S` instead of putting it here. issue #21243.
2471 [ + + ]: 31631 : if (btemp->innervars == NULL)
2472 : 26163 : btemp->innervars = jl_alloc_array_1d(jl_array_any_type, 0);
2473 [ + + ]: 31631 : if (newvar != vb->var) {
2474 : 17562 : btemp->lb = jl_substitute_var(btemp->lb, vb->var, (jl_value_t*)newvar);
2475 : 17562 : btemp->ub = jl_substitute_var(btemp->ub, vb->var, (jl_value_t*)newvar);
2476 : : }
2477 : 31631 : jl_array_ptr_1d_push(btemp->innervars, (jl_value_t*)newvar);
2478 : 31631 : wrap = 0;
2479 : 31631 : btemp = btemp->prev;
2480 : 31631 : continue;
2481 : : }
2482 : : else
2483 : 5 : btemp->lb = jl_new_struct(jl_unionall_type, vb->var, btemp->lb);
2484 [ - + ]: 1310 : assert((jl_value_t*)btemp->var != btemp->lb);
2485 : : }
2486 [ + + ]: 99325700 : if (jl_has_typevar(btemp->ub, vb->var)) {
2487 [ + + ]: 49827 : if (vb->ub == (jl_value_t*)btemp->var) {
2488 : 3 : JL_GC_POP();
2489 : 3 : return jl_bottom_type;
2490 : : }
2491 [ + + ]: 49824 : if (varval) {
2492 [ + - + + ]: 39020 : JL_TRY {
2493 : 19510 : btemp->ub = jl_substitute_var(btemp->ub, vb->var, varval);
2494 : : }
2495 [ # # ]: 0 : JL_CATCH {
2496 : 0 : res = jl_bottom_type;
2497 : : }
2498 : : }
2499 [ + + ]: 30314 : else if (btemp->ub == (jl_value_t*)vb->var)
2500 : 9631 : btemp->ub = vb->ub;
2501 : : else
2502 : 20683 : btemp->ub = jl_new_struct(jl_unionall_type, vb->var, btemp->ub);
2503 [ - + ]: 49824 : assert((jl_value_t*)btemp->var != btemp->ub);
2504 : : }
2505 : 99325700 : btemp = btemp->prev;
2506 : : }
2507 : :
2508 : : // if `v` still occurs, re-wrap body in `UnionAll v` or eliminate the UnionAll
2509 [ + + ]: 32357400 : if (jl_has_typevar(res, vb->var)) {
2510 [ + + ]: 16156100 : if (varval) {
2511 [ + + + + ]: 2491470 : JL_TRY {
2512 : : // you can construct `T{x} where x` even if T's parameter is actually
2513 : : // limited. in that case we might get an invalid instantiation here.
2514 : 1246720 : res = jl_substitute_var(res, vb->var, varval);
2515 : : // simplify chains of UnionAlls where bounds become equal
2516 [ + + + + ]: 1458790 : while (jl_is_unionall(res) && obviously_egal(((jl_unionall_t*)res)->var->lb,
2517 : 213809 : ((jl_unionall_t*)res)->var->ub))
2518 : 228 : res = jl_instantiate_unionall((jl_unionall_t*)res, ((jl_unionall_t*)res)->var->lb);
2519 : : }
2520 [ + + ]: 3932 : JL_CATCH {
2521 : 1966 : res = jl_bottom_type;
2522 : : }
2523 : : }
2524 : : else {
2525 [ + + ]: 14909400 : if (newvar != vb->var)
2526 : 1446630 : res = jl_substitute_var(res, vb->var, (jl_value_t*)newvar);
2527 : 14909400 : varval = (jl_value_t*)newvar;
2528 [ + + ]: 14909400 : if (wrap)
2529 : 14878600 : res = jl_type_unionall((jl_tvar_t*)newvar, res);
2530 : : }
2531 : : }
2532 : :
2533 [ + + + + ]: 32357400 : if (res != jl_bottom_type && vb->innervars != NULL) {
2534 : : int i;
2535 [ + + ]: 61508 : for(i=0; i < jl_array_len(vb->innervars); i++) {
2536 : 33963 : jl_tvar_t *var = (jl_tvar_t*)jl_array_ptr_ref(vb->innervars, i);
2537 [ + + ]: 33963 : if (jl_has_typevar(res, var))
2538 : 28922 : res = jl_type_unionall((jl_tvar_t*)var, res);
2539 : : }
2540 : : }
2541 : :
2542 [ + + + + ]: 32357400 : if (vb->right && e->envidx < e->envsz) {
2543 : 1981660 : jl_value_t *oldval = e->envout[e->envidx];
2544 [ + + + + : 1981660 : if (!varval || (!is_leaf_bound(varval) && !vb->occurs_inv))
+ + ]
2545 : 669359 : e->envout[e->envidx] = (jl_value_t*)vb->var;
2546 [ + + + + : 1312300 : else if (!(oldval && jl_is_typevar(oldval) && jl_is_long(varval)))
+ + ]
2547 : 1312300 : e->envout[e->envidx] = fix_inferred_var_bound(vb->var, varval);
2548 : : }
2549 : :
2550 : 32357400 : JL_GC_POP();
2551 : 32357400 : return res;
2552 : : }
2553 : :
2554 : 149350000 : static jl_value_t *intersect_unionall_(jl_value_t *t, jl_unionall_t *u, jl_stenv_t *e, int8_t R, int param, jl_varbinding_t *vb)
2555 : : {
2556 : 149350000 : jl_varbinding_t *btemp = e->vars;
2557 : : // if the var for this unionall (based on identity) already appears somewhere
2558 : : // in the environment, rename to get a fresh var.
2559 : : // TODO: might need to look inside types in btemp->lb and btemp->ub
2560 : 149350000 : int envsize = 0;
2561 [ + + ]: 483295000 : while (btemp != NULL) {
2562 : 339982000 : envsize++;
2563 [ - + ]: 339982000 : if (envsize > 120) {
2564 : 0 : vb->limited = 1;
2565 : 0 : return t;
2566 : : }
2567 [ + + + + ]: 339982000 : if (btemp->var == u->var || btemp->lb == (jl_value_t*)u->var ||
2568 [ - + ]: 333946000 : btemp->ub == (jl_value_t*)u->var) {
2569 : 6036810 : u = rename_unionall(u);
2570 : 6036810 : break;
2571 : : }
2572 : 333946000 : btemp = btemp->prev;
2573 : : }
2574 : 149350000 : JL_GC_PUSH1(&u);
2575 : 149350000 : vb->var = u->var;
2576 : 149350000 : e->vars = vb;
2577 : : jl_value_t *res;
2578 [ + + ]: 149350000 : if (R) {
2579 : 83361800 : e->envidx++;
2580 : 83361800 : res = intersect(t, u->body, e, param);
2581 : 83361800 : e->envidx--;
2582 : : }
2583 : : else {
2584 : 65987800 : res = intersect(u->body, t, e, param);
2585 : : }
2586 [ + + + + : 150126000 : vb->concrete |= (vb->occurs_cov > 1 && is_leaf_typevar(u->var) &&
+ + ]
2587 : 776444 : !var_occurs_invariant(u->body, u->var, 0));
2588 : :
2589 : : // handle the "diagonal dispatch" rule, which says that a type var occurring more
2590 : : // than once, and only in covariant position, is constrained to concrete types. E.g.
2591 : : // ( Tuple{Int, Int} <: Tuple{T, T} where T) but
2592 : : // !( Tuple{Int, String} <: Tuple{T, T} where T)
2593 : : // Then check concreteness by checking that the lower bound is not an abstract type.
2594 [ + + + + ]: 149350000 : if (res != jl_bottom_type && vb->concrete) {
2595 [ + - ]: 381432 : if (jl_is_typevar(vb->lb)) {
2596 : : }
2597 [ - + ]: 381432 : else if (!is_leaf_bound(vb->lb)) {
2598 : 0 : res = jl_bottom_type;
2599 : : }
2600 : : }
2601 : :
2602 : 149350000 : e->vars = vb->prev;
2603 : :
2604 [ + + ]: 149350000 : if (res != jl_bottom_type) {
2605 [ + + - + ]: 32357400 : if (vb->ub == jl_bottom_type && vb->occurs_cov) {
2606 : : // T=Bottom in covariant position
2607 : 0 : res = jl_bottom_type;
2608 : : }
2609 [ + + + + ]: 32357400 : else if (jl_has_typevar(vb->lb, u->var) || jl_has_typevar(vb->ub, u->var)) {
2610 : : // fail on circular constraints
2611 : 5 : res = jl_bottom_type;
2612 : : }
2613 : : }
2614 [ + + ]: 149350000 : if (res != jl_bottom_type)
2615 : : // res is rooted by callee
2616 : 32357400 : res = finish_unionall(res, vb, u, e);
2617 : 149350000 : JL_GC_POP();
2618 : 149350000 : return res;
2619 : : }
2620 : :
2621 : 147765000 : static jl_value_t *intersect_unionall(jl_value_t *t, jl_unionall_t *u, jl_stenv_t *e, int8_t R, int param)
2622 : : {
2623 : 147765000 : jl_value_t *res=NULL, *save=NULL;
2624 : : jl_savedenv_t se;
2625 [ + + ]: 147765000 : jl_varbinding_t vb = { u->var, u->var->lb, u->var->ub, R, 0, 0, 0, 0, 0, 0,
2626 : 147765000 : R ? e->Rinvdepth : e->invdepth, 0, NULL, e->vars };
2627 : 147765000 : JL_GC_PUSH5(&res, &vb.lb, &vb.ub, &save, &vb.innervars);
2628 : 147765000 : save_env(e, &save, &se);
2629 : 147765000 : res = intersect_unionall_(t, u, e, R, param, &vb);
2630 [ - + ]: 147765000 : if (vb.limited) {
2631 : : // if the environment got too big, avoid tree recursion and propagate the flag
2632 [ # # ]: 0 : if (e->vars)
2633 : 0 : e->vars->limited = 1;
2634 : : }
2635 [ + + ]: 147765000 : else if (res != jl_bottom_type) {
2636 [ + + + + : 30868100 : if (vb.concrete || vb.occurs_inv>1 || u->var->lb != jl_bottom_type || (vb.occurs_inv && vb.occurs_cov)) {
+ + + + +
+ ]
2637 : 1531460 : restore_env(e, NULL, &se);
2638 : 1531460 : vb.occurs_cov = vb.occurs_inv = 0;
2639 [ + + ]: 1531460 : vb.constraintkind = vb.concrete ? 1 : 2;
2640 : 1531460 : res = intersect_unionall_(t, u, e, R, param, &vb);
2641 : : }
2642 [ + + + + ]: 29336600 : else if (vb.occurs_cov && !var_occurs_invariant(u->body, u->var, 0)) {
2643 : 53042 : restore_env(e, save, &se);
2644 : 53042 : vb.occurs_cov = vb.occurs_inv = 0;
2645 : 53042 : vb.constraintkind = 1;
2646 : 53042 : res = intersect_unionall_(t, u, e, R, param, &vb);
2647 : : }
2648 : : }
2649 : 147765000 : free_env(&se);
2650 : 147765000 : JL_GC_POP();
2651 : 147765000 : return res;
2652 : : }
2653 : :
2654 : : // check n = (length of vararg type v)
2655 : 645491 : static int intersect_vararg_length(jl_value_t *v, ssize_t n, jl_stenv_t *e, int8_t R)
2656 : : {
2657 : 645491 : jl_value_t *N = jl_unwrap_vararg_num(v);
2658 : : // only do the check if N is free in the tuple type's last parameter
2659 [ + + + - ]: 645491 : if (N && jl_is_typevar(N)) {
2660 : 296397 : jl_value_t *len = jl_box_long(n);
2661 : 296397 : JL_GC_PUSH1(&len);
2662 [ + + ]: 296397 : jl_value_t *il = R ? intersect(len, N, e, 2) : intersect(N, len, e, 2);
2663 : 296397 : JL_GC_POP();
2664 [ + + ]: 296397 : if (il == jl_bottom_type)
2665 : 5325 : return 0;
2666 : : }
2667 : 640166 : return 1;
2668 : : }
2669 : :
2670 : : static jl_value_t *intersect_invariant(jl_value_t *x, jl_value_t *y, jl_stenv_t *e);
2671 : 114111 : static jl_value_t *intersect_varargs(jl_vararg_t *vmx, jl_vararg_t *vmy, jl_stenv_t *e, int param)
2672 : : {
2673 : : // Vararg: covariant in first parameter, invariant in second
2674 : 114111 : jl_value_t *xp1=jl_unwrap_vararg(vmx), *xp2=jl_unwrap_vararg_num(vmx),
2675 : 114111 : *yp1=jl_unwrap_vararg(vmy), *yp2=jl_unwrap_vararg_num(vmy);
2676 : : // in Vararg{T1} <: Vararg{T2}, need to check subtype twice to
2677 : : // simulate the possibility of multiple arguments, which is needed
2678 : : // to implement the diagonal rule correctly.
2679 [ + + + + ]: 114111 : if (intersect(xp1, yp1, e, param==0 ? 1 : param) == jl_bottom_type)
2680 : 22779 : return jl_bottom_type;
2681 : 91332 : jl_value_t *i2=NULL, *ii = intersect(xp1, yp1, e, 1);
2682 [ + + ]: 91332 : if (ii == jl_bottom_type) return jl_bottom_type;
2683 : 89430 : JL_GC_PUSH2(&ii, &i2);
2684 [ + + + + ]: 89430 : if (!xp2 && !yp2) {
2685 : 49125 : ii = (jl_value_t*)jl_wrap_vararg(ii, NULL);
2686 : 49125 : JL_GC_POP();
2687 : 49125 : return ii;
2688 : : }
2689 [ + + + - ]: 40305 : if (xp2 && jl_is_typevar(xp2)) {
2690 : 19608 : jl_varbinding_t *xb = lookup(e, (jl_tvar_t*)xp2);
2691 [ + + ]: 19608 : if (xb) xb->intvalued = 1;
2692 [ + + ]: 19608 : if (!yp2) {
2693 : 6882 : i2 = bound_var_below((jl_tvar_t*)xp2, xb, e);
2694 : : }
2695 : : }
2696 [ + + + - ]: 40305 : if (yp2 && jl_is_typevar(yp2)) {
2697 : 33423 : jl_varbinding_t *yb = lookup(e, (jl_tvar_t*)yp2);
2698 [ + - ]: 33423 : if (yb) yb->intvalued = 1;
2699 [ + + ]: 33423 : if (!xp2) {
2700 : 20697 : i2 = bound_var_below((jl_tvar_t*)yp2, yb, e);
2701 : : }
2702 : : }
2703 [ + + + + ]: 40305 : if (xp2 && yp2) {
2704 : : // Vararg{T,N} <: Vararg{T2,N2}; equate N and N2
2705 : 12726 : i2 = intersect_invariant(xp2, yp2, e);
2706 [ + + + - : 12726 : if (i2 == NULL || i2 == jl_bottom_type || (jl_is_long(i2) && jl_unbox_long(i2) < 0) ||
+ + + - ]
2707 [ + + + - ]: 12723 : !((jl_is_typevar(i2) && ((jl_tvar_t*)i2)->lb == jl_bottom_type &&
2708 [ - + + + ]: 12723 : ((jl_tvar_t*)i2)->ub == (jl_value_t*)jl_any_type) || jl_is_long(i2))) {
2709 : 5 : i2 = jl_bottom_type;
2710 : : }
2711 : : }
2712 [ + + ]: 40305 : ii = i2 == jl_bottom_type ? (jl_value_t*)jl_bottom_type : (jl_value_t*)jl_wrap_vararg(ii, i2);
2713 : 40305 : JL_GC_POP();
2714 : 40305 : return ii;
2715 : : }
2716 : :
2717 : :
2718 : 33007200 : static jl_value_t *intersect_tuple(jl_datatype_t *xd, jl_datatype_t *yd, jl_stenv_t *e, int param)
2719 : : {
2720 : 33007200 : size_t lx = jl_nparams(xd), ly = jl_nparams(yd);
2721 [ + + - + ]: 33007200 : if (lx == 0 && ly == 0)
2722 : 0 : return (jl_value_t*)yd;
2723 [ + + + + ]: 33007200 : int vx=0, vy=0, vvx = (lx > 0 && jl_is_vararg(jl_tparam(xd, lx-1)));
2724 [ + + + + ]: 33007200 : int vvy = (ly > 0 && jl_is_vararg(jl_tparam(yd, ly-1)));
2725 [ + + + + : 33007200 : if (!vvx && !vvy && lx != ly)
+ + ]
2726 : 4251 : return jl_bottom_type;
2727 : 33003000 : jl_svec_t *params = jl_alloc_svec(lx > ly ? lx : ly);
2728 : 33003000 : jl_value_t *res=NULL;
2729 : 33003000 : JL_GC_PUSH1(¶ms);
2730 : 33003000 : size_t i=0, j=0;
2731 : : jl_value_t *xi, *yi;
2732 : 58827300 : while (1) {
2733 : 91830200 : vx = vy = 0;
2734 [ + + ]: 91830200 : xi = i < lx ? jl_tparam(xd, i) : NULL;
2735 [ + + ]: 91830200 : yi = j < ly ? jl_tparam(yd, j) : NULL;
2736 [ + + + + ]: 91830200 : if (xi == NULL && yi == NULL) {
2737 [ + - + - ]: 4852050 : assert(i == j && i == jl_svec_len(params));
2738 : 4852050 : break;
2739 : : }
2740 [ + + + + ]: 86978200 : if (xi && jl_is_vararg(xi)) vx = 1;
2741 [ + + + + ]: 86978200 : if (yi && jl_is_vararg(yi)) vy = 1;
2742 [ + + + + ]: 86978200 : if (xi == NULL || yi == NULL) {
2743 : 954897 : res = jl_bottom_type;
2744 [ + + + + ]: 954897 : if (vx && intersect_vararg_length(xi, ly+1-lx, e, 0))
2745 : 206567 : res = (jl_value_t*)jl_apply_tuple_type_v(jl_svec_data(params), j);
2746 [ + + + + ]: 954897 : if (vy && intersect_vararg_length(yi, lx+1-ly, e, 1))
2747 : 433599 : res = (jl_value_t*)jl_apply_tuple_type_v(jl_svec_data(params), i);
2748 : 954897 : break;
2749 : : }
2750 : 86023300 : jl_varbinding_t *xb=NULL, *yb=NULL;
2751 : 86023300 : jl_value_t *ii = NULL;
2752 [ + + + + ]: 86137400 : if (vx && vy) {
2753 : : // {A^n...,Vararg{T,N}} ∩ {Vararg{S,M}} = {(A∩S)^n...,Vararg{T∩S,N}} plus N = M-n
2754 : 114111 : jl_value_t *xlen = jl_unwrap_vararg_num(xi);
2755 [ + + + - ]: 114111 : if (xlen && jl_is_typevar(xlen)) {
2756 : 23422 : xb = lookup(e, (jl_tvar_t*)xlen);
2757 [ + + ]: 23422 : if (xb)
2758 : 23416 : xb->offset = ly-lx;
2759 : : }
2760 : 114111 : jl_value_t *ylen = jl_unwrap_vararg_num(yi);
2761 [ + + + - ]: 114111 : if (ylen && jl_is_typevar(ylen)) {
2762 : 37762 : yb = lookup(e, (jl_tvar_t*)ylen);
2763 [ + - ]: 37762 : if (yb)
2764 : 37762 : yb->offset = lx-ly;
2765 : : }
2766 : 114111 : ii = intersect_varargs((jl_vararg_t*)xi,
2767 : : (jl_vararg_t*)yi,
2768 : : e, param);
2769 [ + + ]: 114111 : if (xb) xb->offset = 0;
2770 [ + + ]: 114111 : if (yb) yb->offset = 0;
2771 : : } else {
2772 [ + + ]: 85909200 : if (vx)
2773 : 448720 : xi = jl_unwrap_vararg(xi);
2774 [ + + ]: 85909200 : if (vy)
2775 : 3693210 : yi = jl_unwrap_vararg(yi);
2776 [ + + ]: 85909200 : ii = intersect(xi, yi, e, param == 0 ? 1 : param);
2777 : : }
2778 [ + + ]: 86023300 : if (ii == jl_bottom_type) {
2779 [ + + + + ]: 27141200 : if (vx && vy) {
2780 : 29659 : int len = i > j ? i : j;
2781 [ + + + + : 29659 : if ((xb && jl_is_long(xb->lb) && lx-1+jl_unbox_long(xb->lb) != len) ||
+ + + + ]
2782 [ + + + + ]: 8040 : (yb && jl_is_long(yb->lb) && ly-1+jl_unbox_long(yb->lb) != len)) {
2783 : 32 : res = jl_bottom_type;
2784 : : }
2785 [ + + - + ]: 29627 : else if (param == 2 && jl_is_unionall(xi) != jl_is_unionall(yi)) {
2786 : 0 : res = jl_bottom_type;
2787 : : }
2788 : : else {
2789 [ + + ]: 29627 : if (xb) set_var_to_const(xb, jl_box_long(len-lx+1), yb);
2790 [ + + ]: 29627 : if (yb) set_var_to_const(yb, jl_box_long(len-ly+1), xb);
2791 : 29627 : res = (jl_value_t*)jl_apply_tuple_type_v(jl_svec_data(params), len);
2792 : : }
2793 : : }
2794 : : else {
2795 : 27081900 : res = jl_bottom_type;
2796 : : }
2797 : 27111600 : break;
2798 : : }
2799 : 58911700 : jl_svecset(params, (i > j ? i : j), ii);
2800 [ + + + + ]: 58911700 : if (vx && vy)
2801 : 84452 : break;
2802 [ + + + + ]: 58827300 : if (i < lx-1 || !vx) i++;
2803 [ + + + + ]: 58827300 : if (j < ly-1 || !vy) j++;
2804 : : }
2805 : : // TODO: handle Vararg with explicit integer length parameter
2806 [ + + ]: 33003000 : if (res == NULL)
2807 : 4936500 : res = (jl_value_t*)jl_apply_tuple_type(params);
2808 : 33003000 : JL_GC_POP();
2809 : 33003000 : return res;
2810 : : }
2811 : :
2812 : 11121600 : static void flip_vars(jl_stenv_t *e)
2813 : : {
2814 : 11121600 : jl_varbinding_t *btemp = e->vars;
2815 [ + + ]: 60242900 : while (btemp != NULL) {
2816 : 49121400 : btemp->right = !btemp->right;
2817 : 49121400 : btemp = btemp->prev;
2818 : : }
2819 : 11121600 : }
2820 : :
2821 : : // intersection where xd nominally inherits from yd
2822 : 4851420 : static jl_value_t *intersect_sub_datatype(jl_datatype_t *xd, jl_datatype_t *yd, jl_stenv_t *e, int R, int param)
2823 : : {
2824 [ + + ]: 4851420 : jl_value_t *isuper = R ? intersect((jl_value_t*)yd, (jl_value_t*)xd->super, e, param) :
2825 : 3511820 : intersect((jl_value_t*)xd->super, (jl_value_t*)yd, e, param);
2826 [ + + ]: 4851420 : if (isuper == jl_bottom_type) return jl_bottom_type;
2827 [ + + + + : 4104130 : if (jl_nparams(xd) == 0 || jl_nparams(xd->super) == 0 || !jl_has_free_typevars((jl_value_t*)xd))
+ + ]
2828 : 229858 : return (jl_value_t*)xd;
2829 : 3874280 : jl_value_t *super_pattern=NULL;
2830 : 3874280 : JL_GC_PUSH2(&isuper, &super_pattern);
2831 : 3874280 : jl_value_t *wrapper = xd->name->wrapper;
2832 : 3874280 : super_pattern = jl_rewrap_unionall((jl_value_t*)((jl_datatype_t*)jl_unwrap_unionall(wrapper))->super,
2833 : : wrapper);
2834 : 3874280 : int envsz = jl_subtype_env_size(super_pattern);
2835 : 3874280 : jl_value_t *ii = jl_bottom_type;
2836 : : {
2837 : : jl_value_t **env;
2838 : 3874280 : JL_GC_PUSHARGS(env, envsz);
2839 : : jl_stenv_t tempe;
2840 : 3874280 : init_stenv(&tempe, env, envsz);
2841 : 3874280 : tempe.ignore_free = 1;
2842 [ + + ]: 3874280 : if (subtype_in_env(isuper, super_pattern, &tempe)) {
2843 : 3874270 : jl_value_t *wr = wrapper;
2844 : : int i;
2845 [ + + ]: 17227100 : for(i=0; i<envsz; i++) {
2846 : : // if a parameter is not constrained by the supertype, use the original
2847 : : // parameter value from `x`. this is detected by the value in `env` being
2848 : : // the exact typevar from the type's `wrapper`, or a free typevar.
2849 : 13352800 : jl_value_t *ei = env[i];
2850 [ + + ]: 13352800 : if (ei == (jl_value_t*)((jl_unionall_t*)wr)->var ||
2851 [ + + + + ]: 7111790 : (jl_is_typevar(ei) && lookup(e, (jl_tvar_t*)ei) == NULL))
2852 : 7098570 : env[i] = jl_tparam(xd,i);
2853 : 13352800 : wr = ((jl_unionall_t*)wr)->body;
2854 : : }
2855 [ + + + + ]: 7748540 : JL_TRY {
2856 : 3874270 : ii = jl_apply_type(wrapper, env, envsz);
2857 : : }
2858 [ + + ]: 2 : JL_CATCH {
2859 : 1 : ii = jl_bottom_type;
2860 : : }
2861 : : }
2862 : 3874280 : JL_GC_POP();
2863 : : }
2864 : 3874280 : JL_GC_POP();
2865 : 3874280 : return ii;
2866 : : }
2867 : :
2868 : 38446000 : static jl_value_t *intersect_invariant(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
2869 : : {
2870 [ + + + + ]: 38446000 : if (!jl_has_free_typevars(x) && !jl_has_free_typevars(y)) {
2871 [ + + + + ]: 7713760 : return (jl_subtype(x,y) && jl_subtype(y,x)) ? y : NULL;
2872 : : }
2873 : 30732200 : e->invdepth++;
2874 : 30732200 : e->Rinvdepth++;
2875 : 30732200 : jl_value_t *ii = intersect(x, y, e, 2);
2876 : 30732200 : e->invdepth--;
2877 : 30732200 : e->Rinvdepth--;
2878 [ + + + + : 30732200 : if (jl_is_typevar(x) && jl_is_typevar(y) && (jl_is_typevar(ii) || !jl_is_type(ii)))
+ + + + ]
2879 : 15231800 : return ii;
2880 [ + + ]: 15500400 : if (ii == jl_bottom_type) {
2881 [ + + ]: 6524310 : if (!subtype_in_env(x, jl_bottom_type, e))
2882 : 5808430 : return NULL;
2883 : 715880 : flip_vars(e);
2884 [ + + ]: 715880 : if (!subtype_in_env(y, jl_bottom_type, e)) {
2885 : 538099 : flip_vars(e);
2886 : 538099 : return NULL;
2887 : : }
2888 : 177781 : flip_vars(e);
2889 : 177781 : return jl_bottom_type;
2890 : : }
2891 : 8976070 : jl_value_t *root=NULL;
2892 : : jl_savedenv_t se;
2893 : 8976070 : JL_GC_PUSH2(&ii, &root);
2894 : 8976070 : save_env(e, &root, &se);
2895 [ + + ]: 8976070 : if (!subtype_in_env_existential(x, y, e, 0, e->invdepth)) {
2896 : 121809 : ii = NULL;
2897 : : }
2898 : : else {
2899 [ + + ]: 8854260 : if (!subtype_in_env_existential(y, x, e, 0, e->invdepth))
2900 : 185296 : ii = NULL;
2901 : : }
2902 : 8976070 : restore_env(e, root, &se);
2903 : 8976070 : free_env(&se);
2904 : 8976070 : JL_GC_POP();
2905 : 8976070 : return ii;
2906 : : }
2907 : :
2908 : : // intersection where x == Type{...} and y is not
2909 : 804539 : static jl_value_t *intersect_type_type(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int8_t R)
2910 : : {
2911 : 804539 : jl_value_t *p0 = jl_tparam0(x);
2912 [ + + ]: 804539 : if (!jl_is_typevar(p0))
2913 [ + + ]: 321365 : return (jl_typeof(p0) == y) ? x : jl_bottom_type;
2914 [ + + ]: 483174 : if (!jl_is_kind(y)) return jl_bottom_type;
2915 [ + + + + ]: 54416 : if (y == (jl_value_t*)jl_typeofbottom_type && ((jl_tvar_t*)p0)->lb == jl_bottom_type)
2916 : 4312 : return (jl_value_t*)jl_wrap_Type(jl_bottom_type);
2917 [ + + ]: 50104 : if (((jl_tvar_t*)p0)->ub == (jl_value_t*)jl_any_type)
2918 : 24853 : return y;
2919 : 25251 : return x;
2920 : : /*
2921 : : jl_value_t *ii = R ? intersect_invariant(y, jl_tparam0(x), e) : intersect_invariant(jl_tparam0(x), y, e);
2922 : : // NOTE: we cannot express e.g. DataType ∩ (UnionAll T<:Integer Type{T}), so returning `x`
2923 : : // here is a conservative over-estimate.
2924 : : if (ii == NULL || ii == jl_bottom_type) return x;
2925 : : if (ii == y) return ii;
2926 : : return (jl_value_t*)jl_wrap_Type(ii);
2927 : : */
2928 : : }
2929 : :
2930 : : // cmp <= 0: is x already <= y in this environment
2931 : : // cmp >= 0: is x already >= y in this environment
2932 : 329954 : static int compareto_var(jl_value_t *x, jl_tvar_t *y, jl_stenv_t *e, int cmp) JL_NOTSAFEPOINT
2933 : : {
2934 [ + + ]: 329954 : if (x == (jl_value_t*)y)
2935 : 7547 : return 1;
2936 [ + + ]: 322407 : if (!jl_is_typevar(x))
2937 : 157099 : return 0;
2938 : 165308 : jl_varbinding_t *xv = lookup(e, (jl_tvar_t*)x);
2939 [ + + ]: 165308 : if (xv == NULL)
2940 : 637 : return 0;
2941 : 164671 : int ans = 1;
2942 [ + + ]: 164671 : if (cmp <= 0)
2943 : 82038 : ans &= compareto_var(xv->ub, y, e, cmp);
2944 [ + + ]: 164671 : if (cmp >= 0)
2945 : 82633 : ans &= compareto_var(xv->lb, y, e, cmp);
2946 : 164671 : return ans;
2947 : : }
2948 : :
2949 : : // Check whether the environment already asserts x <: y via recorded bounds.
2950 : : // This is used to avoid adding redundant constraints that lead to cycles.
2951 : : // Note this is a semi-predicate: 1 => is a subtype, 0 => unknown
2952 : 18632400 : static int subtype_by_bounds(jl_value_t *x, jl_value_t *y, jl_stenv_t *e) JL_NOTSAFEPOINT
2953 : : {
2954 [ + + + + ]: 18632400 : if (!jl_is_typevar(x) || !jl_is_typevar(y))
2955 : 18549800 : return 0;
2956 [ + + + + ]: 82650 : return compareto_var(x, (jl_tvar_t*)y, e, -1) || compareto_var(y, (jl_tvar_t*)x, e, 1);
2957 : : }
2958 : :
2959 : : // `param` means we are currently looking at a parameter of a type constructor
2960 : : // (as opposed to being outside any type constructor, or comparing variable bounds).
2961 : : // this is used to record the positions where type variables occur for the
2962 : : // diagonal rule (record_var_occurrence).
2963 : 398724000 : static jl_value_t *intersect(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param)
2964 : : {
2965 [ + + ]: 398724000 : if (x == y) return y;
2966 [ + + ]: 359208000 : if (jl_is_typevar(x)) {
2967 [ + + ]: 22806400 : if (jl_is_typevar(y)) {
2968 : 16213200 : jl_varbinding_t *xx = lookup(e, (jl_tvar_t*)x);
2969 : 16213200 : jl_varbinding_t *yy = lookup(e, (jl_tvar_t*)y);
2970 : 16213200 : int R = 0;
2971 [ + + + + : 16213200 : if (xx && yy && var_outside(e, (jl_tvar_t*)x, (jl_tvar_t*)y)) {
+ + ]
2972 : : // to preserve variable identities correctly, always accumulate bounds
2973 : : // on the outer variable, return the outer variable, and set the inner
2974 : : // variable equal to the outer variable.
2975 : : jl_value_t *temp; jl_varbinding_t *tvb;
2976 : 13382700 : temp = x; x = y; y = temp;
2977 : 13382700 : tvb = xx; xx = yy; yy = tvb;
2978 : 13382700 : R = 1;
2979 : : }
2980 [ + + ]: 16213200 : if (param == 2) {
2981 [ + + ]: 16117700 : jl_value_t *xlb = xx ? xx->lb : ((jl_tvar_t*)x)->lb;
2982 [ + + ]: 16117700 : jl_value_t *xub = xx ? xx->ub : ((jl_tvar_t*)x)->ub;
2983 [ + + ]: 16117700 : jl_value_t *ylb = yy ? yy->lb : ((jl_tvar_t*)y)->lb;
2984 [ + + ]: 16117700 : jl_value_t *yub = yy ? yy->ub : ((jl_tvar_t*)y)->ub;
2985 : 16117700 : record_var_occurrence(xx, e, param);
2986 [ + + + + : 16117700 : if (xx && yy && xx->depth0 != yy->depth0) {
+ + ]
2987 : 255135 : record_var_occurrence(yy, e, param);
2988 [ + + ]: 255135 : return subtype_in_env(yy->ub, yy->lb, e) ? y : jl_bottom_type;
2989 : : }
2990 [ + + + + ]: 15862600 : if (xub == xlb && jl_is_typevar(xub)) {
2991 [ + + ]: 1331880 : if (y == xub) {
2992 : 1304310 : record_var_occurrence(yy, e, param);
2993 : 1304310 : return y;
2994 : : }
2995 : 27566 : return intersect(y, xub, e, param);
2996 : : }
2997 : 14530700 : record_var_occurrence(yy, e, param);
2998 [ + + + + ]: 14530700 : if (!jl_is_type(ylb) && !jl_is_typevar(ylb)) {
2999 [ + - ]: 116882 : if (xx)
3000 : 116882 : return set_var_to_const(xx, ylb, yy);
3001 [ # # # # : 0 : if ((xlb == jl_bottom_type && xub == (jl_value_t*)jl_any_type) || jl_egal(xlb, ylb))
# # ]
3002 : 0 : return ylb;
3003 : 0 : return jl_bottom_type;
3004 : : }
3005 [ + + + + ]: 14413800 : if (!jl_is_type(xlb) && !jl_is_typevar(xlb)) {
3006 [ + - ]: 63 : if (yy)
3007 : 63 : return set_var_to_const(yy, xlb, xx);
3008 [ # # # # ]: 0 : if (ylb == jl_bottom_type && yub == (jl_value_t*)jl_any_type)
3009 : 0 : return xlb;
3010 : 0 : return jl_bottom_type;
3011 : : }
3012 : : int ccheck;
3013 [ + + ]: 14413700 : if (yub == xub ||
3014 [ - + - - ]: 6284570 : (subtype_by_bounds(xlb, yub, e) && subtype_by_bounds(ylb, xub, e))) {
3015 : 8129180 : ccheck = 1;
3016 : : }
3017 : : else {
3018 [ + + ]: 6284570 : if (R) flip_vars(e);
3019 [ + + + + ]: 6284570 : ccheck = subtype_in_env(xlb, yub, e) && subtype_in_env(ylb, xub, e);
3020 [ + + ]: 6284570 : if (R) flip_vars(e);
3021 : : }
3022 [ + + ]: 14413700 : if (!ccheck)
3023 : 647199 : return jl_bottom_type;
3024 [ - + - - ]: 13766500 : if (var_occurs_inside(xub, (jl_tvar_t*)y, 0, 0) && var_occurs_inside(yub, (jl_tvar_t*)x, 0, 0)) {
3025 : : // circular constraint. the result will be Bottom, but in the meantime
3026 : : // we need to avoid computing intersect(xub, yub) since it won't terminate.
3027 : 0 : return y;
3028 : : }
3029 : 13766500 : jl_value_t *ub=NULL, *lb=NULL;
3030 : 13766500 : JL_GC_PUSH2(&lb, &ub);
3031 [ + + ]: 13766500 : ub = intersect_aside(xub, yub, e, 0, xx ? xx->depth0 : 0);
3032 [ + + ]: 13766500 : if (reachable_var(xlb, (jl_tvar_t*)y, e))
3033 : 8103 : lb = ylb;
3034 : : else
3035 : 13758400 : lb = simple_join(xlb, ylb);
3036 [ + + ]: 13766500 : if (yy) {
3037 : 13765000 : yy->lb = lb;
3038 [ + + ]: 13765000 : if (!reachable_var(ub, (jl_tvar_t*)y, e))
3039 : 13764900 : yy->ub = ub;
3040 [ - + ]: 13765000 : assert(yy->ub != y);
3041 [ - + ]: 13765000 : assert(yy->lb != y);
3042 : : }
3043 [ + + + + ]: 13766500 : if (xx && !reachable_var(y, (jl_tvar_t*)x, e)) {
3044 : 13766000 : xx->lb = y;
3045 : 13766000 : xx->ub = y;
3046 [ - + ]: 13766000 : assert(xx->ub != x);
3047 : : }
3048 : 13766500 : JL_GC_POP();
3049 : 13766500 : return y;
3050 : : }
3051 : 95476 : record_var_occurrence(xx, e, param);
3052 : 95476 : record_var_occurrence(yy, e, param);
3053 [ + - + - : 95476 : if (xx && yy && xx->concrete && !yy->concrete) {
+ + + + ]
3054 : 5814 : return intersect_var((jl_tvar_t*)x, y, e, R, param);
3055 : : }
3056 : 89662 : return intersect_var((jl_tvar_t*)y, x, e, !R, param);
3057 : : }
3058 : 6593230 : record_var_occurrence(lookup(e, (jl_tvar_t*)x), e, param);
3059 : 6593230 : return intersect_var((jl_tvar_t*)x, y, e, 0, param);
3060 : : }
3061 [ + + ]: 336402000 : if (jl_is_typevar(y)) {
3062 : 12534300 : record_var_occurrence(lookup(e, (jl_tvar_t*)y), e, param);
3063 : 12534300 : return intersect_var((jl_tvar_t*)y, x, e, 1, param);
3064 : : }
3065 [ + + + + ]: 323868000 : if (!jl_has_free_typevars(x) && !jl_has_free_typevars(y)) {
3066 [ + + ]: 95872400 : if (jl_subtype(x, y)) return x;
3067 [ + + ]: 88729200 : if (jl_subtype(y, x)) return y;
3068 : : }
3069 [ + + ]: 312012000 : if (jl_is_uniontype(x)) {
3070 [ + + + + ]: 31361700 : if (y == ((jl_uniontype_t*)x)->a || y == ((jl_uniontype_t*)x)->b)
3071 : 10 : return y;
3072 : 31361700 : return intersect_union(y, (jl_uniontype_t*)x, e, 0, param);
3073 : : }
3074 [ + + ]: 280651000 : if (jl_is_uniontype(y)) {
3075 [ + + + + ]: 39041300 : if (x == ((jl_uniontype_t*)y)->a || x == ((jl_uniontype_t*)y)->b)
3076 : 551 : return x;
3077 [ + + + + : 39040800 : if (jl_is_unionall(x) && (jl_has_free_typevars(x) || jl_has_free_typevars(y)))
+ + ]
3078 : 14808300 : return intersect_unionall(y, (jl_unionall_t*)x, e, 0, param);
3079 : 24232400 : return intersect_union(x, (jl_uniontype_t*)y, e, 1, param);
3080 : : }
3081 [ + + ]: 241609000 : if (y == (jl_value_t*)jl_any_type) return x;
3082 [ + + ]: 241534000 : if (x == (jl_value_t*)jl_any_type) return y;
3083 [ + + ]: 238607000 : if (jl_is_unionall(x)) {
3084 [ + + ]: 50697100 : if (jl_is_unionall(y)) {
3085 : 34251900 : jl_value_t *a=NULL, *b=jl_bottom_type, *res=NULL;
3086 : 34251900 : JL_GC_PUSH2(&a,&b);
3087 : : jl_savedenv_t se;
3088 : 34251900 : save_env(e, NULL, &se);
3089 : 34251900 : a = intersect_unionall(y, (jl_unionall_t*)x, e, 0, param);
3090 [ + + ]: 34251900 : if (jl_is_unionall(a)) {
3091 : 7658550 : jl_unionall_t *ua = (jl_unionall_t*)a;
3092 [ + + ]: 7658550 : if (jl_is_unionall(ua->body)) {
3093 : 3908080 : jl_unionall_t *ub = (jl_unionall_t*)ua->body;
3094 [ + + ]: 3908080 : if (jl_has_typevar(ub->var->ub, ua->var) ||
3095 [ - + ]: 3873570 : jl_has_typevar(ub->var->lb, ua->var)) {
3096 : 34510 : restore_env(e, NULL, &se); // restore counts
3097 : 34510 : b = intersect_unionall(x, (jl_unionall_t*)y, e, 1, param);
3098 : : }
3099 : : }
3100 : : }
3101 : 34251900 : free_env(&se);
3102 [ + + + + ]: 34251900 : if (!jl_has_free_typevars(a) && !jl_has_free_typevars(b)) {
3103 [ + + ]: 27035500 : if (jl_subtype(a, b))
3104 : 25808700 : res = b;
3105 [ + - ]: 1226830 : else if (jl_subtype(b, a))
3106 : 1226830 : res = a;
3107 : : }
3108 [ + + ]: 34251900 : if (!res) res = simple_join(a, b);
3109 : 34251900 : JL_GC_POP();
3110 : 34251900 : return res;
3111 : : }
3112 : 16445200 : return intersect_unionall(y, (jl_unionall_t*)x, e, 0, param);
3113 : : }
3114 [ + + ]: 187909000 : if (jl_is_unionall(y))
3115 : 82225100 : return intersect_unionall(x, (jl_unionall_t*)y, e, 1, param);
3116 [ + + + + ]: 105684000 : if (jl_is_datatype(x) && jl_is_datatype(y)) {
3117 : 105683000 : jl_datatype_t *xd = (jl_datatype_t*)x, *yd = (jl_datatype_t*)y;
3118 [ + + ]: 105683000 : if (param < 2) {
3119 [ + + ]: 104800000 : if (jl_is_type_type(x)) {
3120 [ + + ]: 9291280 : if (!jl_is_type_type(y))
3121 : 334031 : return intersect_type_type(x, y, e, 0);
3122 : : }
3123 [ + + ]: 95508400 : else if (jl_is_type_type(y)) {
3124 : 470508 : return intersect_type_type(y, x, e, 1);
3125 : : }
3126 : : }
3127 [ + + ]: 104878000 : if (xd->name == yd->name) {
3128 [ + + ]: 55611000 : if (jl_is_tuple_type(xd))
3129 : 33007200 : return intersect_tuple(xd, yd, e, param);
3130 : 22603800 : size_t i, np = jl_nparams(xd);
3131 : : jl_value_t **newparams;
3132 : 22603800 : JL_GC_PUSHARGS(newparams, np);
3133 [ + + ]: 52591000 : for (i=0; i < np; i++) {
3134 : 38433300 : jl_value_t *xi = jl_tparam(xd, i), *yi = jl_tparam(yd, i);
3135 : 38433300 : jl_value_t *ii = intersect_invariant(xi, yi, e);
3136 [ + + ]: 38433300 : if (ii == NULL)
3137 : 8446060 : break;
3138 : 29987200 : newparams[i] = ii;
3139 : : }
3140 : 22603800 : jl_value_t *res = jl_bottom_type;
3141 [ + + ]: 22603800 : if (i >= np) {
3142 [ + + + + ]: 28304400 : JL_TRY {
3143 : 14157700 : res = jl_apply_type(xd->name->wrapper, newparams, np);
3144 : : }
3145 [ + + ]: 22136 : JL_CATCH {
3146 : 11068 : res = jl_bottom_type;
3147 : : }
3148 : : }
3149 : 22603800 : JL_GC_POP();
3150 : 22603800 : return res;
3151 : : }
3152 [ + + ]: 49267300 : if (param == 2) return jl_bottom_type;
3153 [ + + + + ]: 159533000 : while (xd != jl_any_type && xd->name != yd->name)
3154 : 110497000 : xd = xd->super;
3155 [ + + ]: 49035900 : if (xd == jl_any_type) {
3156 : 45524100 : xd = (jl_datatype_t*)x;
3157 [ + + + + ]: 146199000 : while (yd != jl_any_type && yd->name != xd->name)
3158 : 100675000 : yd = yd->super;
3159 [ + + ]: 45524100 : if (yd == jl_any_type)
3160 : 44184500 : return jl_bottom_type;
3161 : 1339610 : return intersect_sub_datatype((jl_datatype_t*)y, xd, e, 1, param);
3162 : : }
3163 : 3511820 : return intersect_sub_datatype((jl_datatype_t*)x, yd, e, 0, param);
3164 : : }
3165 [ - + ]: 1429 : if (jl_egal(x, y)) return y;
3166 : 1429 : return jl_bottom_type;
3167 : : }
3168 : :
3169 : 74647900 : static jl_value_t *intersect_all(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
3170 : : {
3171 : 74647900 : e->Runions.depth = 0;
3172 : 74647900 : e->Runions.more = 0;
3173 : 74647900 : e->Runions.used = 0;
3174 : : jl_value_t **is;
3175 : 74647900 : JL_GC_PUSHARGS(is, 3);
3176 : 74647900 : jl_value_t **saved = &is[2];
3177 : : jl_savedenv_t se;
3178 : 74647900 : save_env(e, saved, &se);
3179 : 74647900 : int lastset = 0, niter = 0, total_iter = 0;
3180 : 74647900 : jl_value_t *ii = intersect(x, y, e, 0);
3181 : 74647900 : is[0] = ii; // root
3182 [ + + ]: 74647900 : if (ii == jl_bottom_type) {
3183 : 59608900 : restore_env(e, *saved, &se);
3184 : : }
3185 : : else {
3186 : 15039000 : free_env(&se);
3187 : 15039000 : save_env(e, saved, &se);
3188 : : }
3189 [ + + ]: 90226300 : while (e->Runions.more) {
3190 [ + + + + ]: 16150000 : if (e->emptiness_only && ii != jl_bottom_type)
3191 : 500116 : break;
3192 : 15649900 : e->Runions.depth = 0;
3193 : 15649900 : int set = e->Runions.more - 1;
3194 : 15649900 : e->Runions.more = 0;
3195 : 15649900 : statestack_set(&e->Runions, set, 1);
3196 [ + + ]: 21890000 : for (int i = set + 1; i <= lastset; i++)
3197 : 6240080 : statestack_set(&e->Runions, i, 0);
3198 : 15649900 : lastset = set;
3199 : :
3200 : 15649900 : is[0] = ii;
3201 : 15649900 : is[1] = intersect(x, y, e, 0);
3202 [ + + ]: 15649900 : if (is[1] == jl_bottom_type) {
3203 : 15153700 : restore_env(e, *saved, &se);
3204 : : }
3205 : : else {
3206 : 496225 : free_env(&se);
3207 : 496225 : save_env(e, saved, &se);
3208 : : }
3209 [ + + ]: 15649900 : if (is[0] == jl_bottom_type)
3210 : 12122900 : ii = is[1];
3211 [ + + ]: 3527060 : else if (is[1] == jl_bottom_type)
3212 : 3099930 : ii = is[0];
3213 : : else {
3214 : : // TODO: the repeated subtype checks in here can get expensive
3215 : 427132 : ii = jl_type_union(is, 2);
3216 : 427132 : niter++;
3217 : : }
3218 : 15649900 : total_iter++;
3219 [ + + + + ]: 15649900 : if (niter > 3 || total_iter > 400000) {
3220 : 71545 : ii = y;
3221 : 71545 : break;
3222 : : }
3223 : : }
3224 : 74647900 : free_env(&se);
3225 : 74647900 : JL_GC_POP();
3226 : 74647900 : return ii;
3227 : : }
3228 : :
3229 : : // type intersection entry points
3230 : :
3231 : 64297000 : static jl_value_t *intersect_types(jl_value_t *x, jl_value_t *y, int emptiness_only)
3232 : : {
3233 : : jl_stenv_t e;
3234 [ + + ]: 64297000 : if (obviously_disjoint(x, y, 0))
3235 : 55990400 : return jl_bottom_type;
3236 [ + + + + ]: 8306530 : if (jl_is_dispatch_tupletype(x) || jl_is_dispatch_tupletype(y)) {
3237 [ + + ]: 758196 : if (jl_subtype(x, y))
3238 : 57817 : return x;
3239 [ + + ]: 700379 : else if (jl_subtype(y, x))
3240 : 200981 : return y;
3241 : : else
3242 : 499398 : return jl_bottom_type;
3243 : : }
3244 : 7548330 : init_stenv(&e, NULL, 0);
3245 : 7548330 : e.intersection = e.ignore_free = 1;
3246 : 7548330 : e.emptiness_only = emptiness_only;
3247 : 7548330 : return intersect_all(x, y, &e);
3248 : : }
3249 : :
3250 : 77146 : JL_DLLEXPORT jl_value_t *jl_intersect_types(jl_value_t *x, jl_value_t *y)
3251 : : {
3252 : 77146 : return intersect_types(x, y, 0);
3253 : : }
3254 : :
3255 : : // TODO: this can probably be done more efficiently
3256 : 64219800 : JL_DLLEXPORT int jl_has_empty_intersection(jl_value_t *x, jl_value_t *y)
3257 : : {
3258 : 64219800 : return intersect_types(x, y, 1) == jl_bottom_type;
3259 : : }
3260 : :
3261 : : // return a SimpleVector of all vars from UnionAlls wrapping a given type
3262 : 200957 : jl_svec_t *jl_outer_unionall_vars(jl_value_t *u)
3263 : : {
3264 : 200957 : int ntvars = jl_subtype_env_size((jl_value_t*)u);
3265 : 200957 : jl_svec_t *vec = jl_alloc_svec_uninit(ntvars);
3266 : 200957 : jl_unionall_t *ua = (jl_unionall_t*)u;
3267 : : int i;
3268 [ + + ]: 232931 : for (i = 0; i < ntvars; i++) {
3269 [ - + ]: 31974 : assert(jl_is_unionall(ua));
3270 : 31974 : jl_svecset(vec, i, ua->var);
3271 : 31974 : ua = (jl_unionall_t*)ua->body;
3272 : : }
3273 : 200957 : return vec;
3274 : : }
3275 : :
3276 : : // For (possibly unions or unionalls of) tuples `a` and `b`, return the tuple of
3277 : : // pointwise unions. Note that this may in general be wider than `Union{a,b}`.
3278 : : // If `a` and `b` are not (non va-)tuples of equal length (or unions or unionalls
3279 : : // of such), return NULL.
3280 : 60335 : static jl_value_t *switch_union_tuple(jl_value_t *a, jl_value_t *b)
3281 : : {
3282 [ + + ]: 60335 : if (jl_is_unionall(a)) {
3283 : 14652 : jl_unionall_t *ua = (jl_unionall_t*)a;
3284 [ + + ]: 14652 : if (jl_is_unionall(b)) {
3285 : 6914 : jl_unionall_t *ub = (jl_unionall_t*)b;
3286 [ + - + + ]: 6914 : if (ub->var->lb == ua->var->lb && ub->var->ub == ua->var->ub) {
3287 : 6751 : jl_value_t *ub2 = jl_instantiate_unionall(ub, (jl_value_t*)ua->var);
3288 : 6751 : jl_value_t *ans = NULL;
3289 : 6751 : JL_GC_PUSH2(&ub2, &ans);
3290 : 6751 : ans = switch_union_tuple(ua->body, ub2);
3291 [ + + ]: 6751 : if (ans != NULL)
3292 : 6683 : ans = jl_type_unionall(ua->var, ans);
3293 : 6751 : JL_GC_POP();
3294 : 6751 : return ans;
3295 : : }
3296 : : }
3297 : 7901 : jl_value_t *ans = switch_union_tuple(ua->body, b);
3298 [ + + ]: 7901 : if (ans == NULL)
3299 : 104 : return NULL;
3300 : 7797 : JL_GC_PUSH1(&ans);
3301 : 7797 : ans = jl_type_unionall(ua->var, ans);
3302 : 7797 : JL_GC_POP();
3303 : 7797 : return ans;
3304 : : }
3305 [ + + ]: 45683 : if (jl_is_unionall(b)) {
3306 : 8796 : jl_value_t *ans = switch_union_tuple(a, ((jl_unionall_t*)b)->body);
3307 [ + + ]: 8796 : if (ans == NULL)
3308 : 52 : return NULL;
3309 : 8744 : JL_GC_PUSH1(&ans);
3310 : 8744 : ans = jl_type_unionall(((jl_unionall_t*)b)->var, ans);
3311 : 8744 : JL_GC_POP();
3312 : 8744 : return ans;
3313 : : }
3314 [ - + ]: 36887 : if (jl_is_uniontype(a)) {
3315 : 0 : a = switch_union_tuple(((jl_uniontype_t*)a)->a, ((jl_uniontype_t*)a)->b);
3316 [ # # ]: 0 : if (a == NULL)
3317 : 0 : return NULL;
3318 : 0 : JL_GC_PUSH1(&a);
3319 : 0 : jl_value_t *ans = switch_union_tuple(a, b);
3320 : 0 : JL_GC_POP();
3321 : 0 : return ans;
3322 : : }
3323 [ + + ]: 36887 : if (jl_is_uniontype(b)) {
3324 : 10600 : b = switch_union_tuple(((jl_uniontype_t*)b)->a, ((jl_uniontype_t*)b)->b);
3325 [ - + ]: 10600 : if (b == NULL)
3326 : 0 : return NULL;
3327 : 10600 : JL_GC_PUSH1(&b);
3328 : 10600 : jl_value_t *ans = switch_union_tuple(a, b);
3329 : 10600 : JL_GC_POP();
3330 : 10600 : return ans;
3331 : : }
3332 [ + - - + ]: 26287 : if (!jl_is_tuple_type(a) || !jl_is_tuple_type(b)) {
3333 : 0 : return NULL;
3334 : : }
3335 [ + - + + : 52419 : if (jl_nparams(a) != jl_nparams(b) || jl_is_va_tuple((jl_datatype_t*)a) ||
- + ]
3336 : 26132 : jl_is_va_tuple((jl_datatype_t*)b)) {
3337 : 155 : return NULL;
3338 : : }
3339 : 26132 : jl_svec_t *vec = jl_alloc_svec(jl_nparams(a));
3340 : 26132 : JL_GC_PUSH1(&vec);
3341 [ + + ]: 113746 : for (int i = 0; i < jl_nparams(a); i++) {
3342 : : jl_value_t *ts[2];
3343 : 87614 : ts[0] = jl_tparam(a, i);
3344 : 87614 : ts[1] = jl_tparam(b, i);
3345 : 87614 : jl_svecset(vec, i, jl_type_union(ts, 2));
3346 : : }
3347 : 26132 : jl_value_t *ans = (jl_value_t*)jl_apply_tuple_type(vec);
3348 : 26132 : JL_GC_POP();
3349 : 26132 : return ans;
3350 : : }
3351 : :
3352 : : // `a` might have a non-empty intersection with some concrete type b even if !(a<:b) and !(b<:a)
3353 : : // For example a=`Tuple{Type{<:Vector}}` and b=`Tuple{DataType}`
3354 : 21970800 : static int might_intersect_concrete(jl_value_t *a)
3355 : : {
3356 [ + + ]: 21970800 : if (jl_is_unionall(a))
3357 : 2451370 : a = jl_unwrap_unionall(a);
3358 [ + + ]: 21970800 : if (jl_is_typevar(a))
3359 : 2563 : return 1; // (maybe)
3360 [ + + ]: 21968200 : if (jl_is_uniontype(a))
3361 [ + + + + ]: 8528880 : return might_intersect_concrete(((jl_uniontype_t*)a)->a) ||
3362 : 3772110 : might_intersect_concrete(((jl_uniontype_t*)a)->b);
3363 [ + + ]: 17211500 : if (jl_is_vararg(a))
3364 : 406338 : return might_intersect_concrete(jl_unwrap_vararg(a));
3365 [ + + ]: 16805100 : if (jl_is_type_type(a))
3366 : 354350 : return 1;
3367 [ + + ]: 16450800 : if (jl_is_datatype(a)) {
3368 : 16450800 : int tpl = jl_is_tuple_type(a);
3369 : 16450800 : int i, n = jl_nparams(a);
3370 [ + + ]: 25633600 : for (i = 0; i < n; i++) {
3371 : 12973000 : jl_value_t *p = jl_tparam(a, i);
3372 [ + + ]: 12973000 : if (jl_is_typevar(p))
3373 : 2051790 : return 1;
3374 [ + + - + ]: 10921200 : if (tpl && p == jl_bottom_type)
3375 : 0 : return 1;
3376 [ + + + + ]: 10921200 : if (tpl && might_intersect_concrete(p))
3377 : 1738360 : return 1;
3378 : : }
3379 : : }
3380 : 12660600 : return 0;
3381 : : }
3382 : :
3383 : : // sets *issubty to 1 iff `a` is a subtype of `b`
3384 : 145698000 : jl_value_t *jl_type_intersection_env_s(jl_value_t *a, jl_value_t *b, jl_svec_t **penv, int *issubty)
3385 : : {
3386 [ + + ]: 145698000 : if (issubty) *issubty = 0;
3387 [ + + ]: 145698000 : if (obviously_disjoint(a, b, 0)) {
3388 [ + + - + ]: 99723100 : if (issubty && a == jl_bottom_type) *issubty = 1;
3389 : 99723100 : return jl_bottom_type;
3390 : : }
3391 : 45975000 : int szb = jl_subtype_env_size(b);
3392 : 45975000 : int sz = 0, i = 0;
3393 : : jl_value_t **env, **ans;
3394 : 45975000 : JL_GC_PUSHARGS(env, szb+1);
3395 : 45975000 : ans = &env[szb];
3396 : 45975000 : *ans = jl_bottom_type;
3397 : 45975000 : int lta = jl_is_concrete_type(a);
3398 : 45975000 : int ltb = jl_is_concrete_type(b);
3399 [ + + ]: 45975000 : if (jl_subtype_env(a, b, env, szb)) {
3400 : 23257200 : *ans = a; sz = szb;
3401 [ + + ]: 23257200 : if (issubty) *issubty = 1;
3402 : : }
3403 [ + + + + ]: 22717700 : else if (lta && ltb) {
3404 : 30 : goto bot;
3405 : : }
3406 [ + + ]: 22717700 : else if (jl_subtype(b, a)) {
3407 : 6527540 : *ans = b;
3408 : : }
3409 : : else {
3410 : : // TODO: these tests could probably be ordered better with above
3411 [ + + + + ]: 16190200 : if (lta && !might_intersect_concrete(b))
3412 : 12871600 : goto bot;
3413 [ + + + + ]: 15877500 : if (ltb && !might_intersect_concrete(a))
3414 : 590641 : goto bot;
3415 : : jl_stenv_t e;
3416 : 15286800 : init_stenv(&e, NULL, 0);
3417 : 15286800 : e.intersection = e.ignore_free = 1;
3418 : 15286800 : e.envout = env;
3419 [ + + ]: 15286800 : if (szb)
3420 : 5943770 : memset(env, 0, szb*sizeof(void*));
3421 : 15286800 : e.envsz = szb;
3422 : 15286800 : *ans = intersect_all(a, b, &e);
3423 [ + + ]: 15286800 : if (*ans == jl_bottom_type) goto bot;
3424 : : // TODO: code dealing with method signatures is not able to handle unions, so if
3425 : : // `a` and `b` are both tuples, we need to be careful and may not return a union,
3426 : : // even if `intersect` produced one
3427 : 3318540 : int env_from_subtype = 1;
3428 [ + + + + ]: 3318540 : if (jl_is_tuple_type(jl_unwrap_unionall(a)) && jl_is_tuple_type(jl_unwrap_unionall(b)) &&
3429 [ + + ]: 3296370 : !jl_is_datatype(jl_unwrap_unionall(*ans))) {
3430 : 15687 : jl_value_t *ans_unwrapped = jl_unwrap_unionall(*ans);
3431 : 15687 : JL_GC_PUSH1(&ans_unwrapped);
3432 [ + - ]: 15687 : if (jl_is_uniontype(ans_unwrapped)) {
3433 : 15687 : ans_unwrapped = switch_union_tuple(((jl_uniontype_t*)ans_unwrapped)->a, ((jl_uniontype_t*)ans_unwrapped)->b);
3434 [ + + ]: 15687 : if (ans_unwrapped != NULL) {
3435 : 15532 : *ans = jl_rewrap_unionall(ans_unwrapped, *ans);
3436 : : }
3437 : : }
3438 : 15687 : JL_GC_POP();
3439 [ + + ]: 15687 : if (!jl_is_datatype(jl_unwrap_unionall(*ans))) {
3440 : 155 : *ans = b;
3441 : 155 : env_from_subtype = 0;
3442 : : }
3443 : : }
3444 [ + + ]: 3318540 : if (env_from_subtype) {
3445 : 3318380 : sz = szb;
3446 : : // TODO: compute better `env` directly during intersection.
3447 : : // for now, we attempt to compute env by using subtype on the intersection result
3448 [ + + + + ]: 3318380 : if (szb > 0 && !jl_types_equal(b, (jl_value_t*)jl_type_type)) {
3449 [ + + ]: 990492 : if (!jl_subtype_env(*ans, b, env, szb)) {
3450 : 82414 : sz = 0;
3451 : : }
3452 : : }
3453 : : }
3454 : : }
3455 [ + + + + ]: 33103300 : if (sz == 0 && szb > 0) {
3456 [ + + ]: 1778220 : while (jl_is_unionall(b)) {
3457 : 935525 : env[i++] = (jl_value_t*)((jl_unionall_t*)b)->var;
3458 : 935525 : b = ((jl_unionall_t*)b)->body;
3459 : : }
3460 : 842697 : sz = szb;
3461 : : }
3462 [ + + ]: 33103300 : if (penv) {
3463 : 10658900 : jl_svec_t *e = jl_alloc_svec(sz);
3464 : 10658900 : *penv = e;
3465 [ + + ]: 14551600 : for(i=0; i < sz; i++)
3466 : 3892720 : jl_svecset(e, i, env[i]);
3467 : : }
3468 : 33103300 : bot:
3469 : 45975000 : JL_GC_POP();
3470 : 45975000 : return *ans;
3471 : : }
3472 : :
3473 : 27057900 : jl_value_t *jl_type_intersection_env(jl_value_t *a, jl_value_t *b, jl_svec_t **penv)
3474 : : {
3475 : 27057900 : return jl_type_intersection_env_s(a, b, penv, NULL);
3476 : : }
3477 : :
3478 : 26431000 : JL_DLLEXPORT jl_value_t *jl_type_intersection(jl_value_t *a, jl_value_t *b)
3479 : : {
3480 : 26431000 : return jl_type_intersection_env(a, b, NULL);
3481 : : }
3482 : :
3483 : 200553 : JL_DLLEXPORT jl_svec_t *jl_type_intersection_with_env(jl_value_t *a, jl_value_t *b)
3484 : : {
3485 : 200553 : jl_svec_t *env = jl_emptysvec;
3486 : 200553 : jl_value_t *ti = NULL;
3487 : 200553 : JL_GC_PUSH2(&env, &ti);
3488 : 200553 : ti = jl_type_intersection_env(a, b, &env);
3489 : 200553 : jl_svec_t *pair = jl_svec2(ti, env);
3490 : 200553 : JL_GC_POP();
3491 : 200553 : return pair;
3492 : : }
3493 : :
3494 : 2254300 : int jl_subtype_matching(jl_value_t *a, jl_value_t *b, jl_svec_t **penv)
3495 : : {
3496 [ + + ]: 2254300 : int szb = penv ? jl_subtype_env_size(b) : 0;
3497 [ + + ]: 2254300 : if (szb == 0)
3498 : 2254290 : return jl_subtype_env(a, b, NULL, szb);
3499 : :
3500 : : jl_value_t **env;
3501 : 5 : JL_GC_PUSHARGS(env, szb);
3502 : 5 : int sub = jl_subtype_env(a, b, env, szb);
3503 [ + - ]: 5 : if (sub) {
3504 : : // copy env to svec for return
3505 : 5 : int i = 0;
3506 : 5 : jl_svec_t *e = jl_alloc_svec(szb);
3507 : 5 : *penv = e;
3508 [ + + ]: 10 : for (i = 0; i < szb; i++)
3509 : 5 : jl_svecset(e, i, env[i]);
3510 : : }
3511 : 5 : JL_GC_POP();
3512 : 5 : return sub;
3513 : : }
3514 : :
3515 : :
3516 : : // specificity comparison
3517 : :
3518 : 12350400 : static int eq_msp(jl_value_t *a, jl_value_t *b, jl_typeenv_t *env)
3519 : : {
3520 [ + + + + : 24422600 : if (!(jl_is_type(a) || jl_is_typevar(a)) ||
+ + ]
3521 [ - + ]: 19304500 : !(jl_is_type(b) || jl_is_typevar(b)))
3522 : 278205 : return jl_egal(a, b);
3523 : 12072200 : JL_GC_PUSH2(&a, &b);
3524 : 12072200 : jl_typeenv_t *e = env;
3525 [ + + ]: 55445500 : while (e != NULL) {
3526 : 43373300 : a = jl_type_unionall(e->var, a);
3527 : 43373300 : b = jl_type_unionall(e->var, b);
3528 : 43373300 : e = e->prev;
3529 : : }
3530 : 12072200 : int eq = jl_types_equal(a, b);
3531 : 12072200 : JL_GC_POP();
3532 : 12072200 : return eq;
3533 : : }
3534 : :
3535 : 32647200 : static int sub_msp(jl_value_t *a, jl_value_t *b, jl_typeenv_t *env)
3536 : : {
3537 : 32647200 : JL_GC_PUSH2(&a, &b);
3538 [ + + ]: 72411800 : while (env != NULL) {
3539 [ + + + + ]: 39764500 : if (jl_is_type(a) || jl_is_typevar(a))
3540 : 39764500 : a = jl_type_unionall(env->var, a);
3541 [ + + + + ]: 39764500 : if (jl_is_type(b) || jl_is_typevar(b))
3542 : 39764500 : b = jl_type_unionall(env->var, b);
3543 : 39764500 : env = env->prev;
3544 : : }
3545 : 32647200 : int sub = jl_subtype(a, b);
3546 : 32647200 : JL_GC_POP();
3547 : 32647200 : return sub;
3548 : : }
3549 : :
3550 : : static int type_morespecific_(jl_value_t *a, jl_value_t *b, int invariant, jl_typeenv_t *env);
3551 : :
3552 : : static int num_occurs(jl_tvar_t *v, jl_typeenv_t *env);
3553 : :
3554 : 49564300 : static jl_value_t *nth_tuple_elt(jl_datatype_t *t JL_PROPAGATES_ROOT, size_t i) JL_NOTSAFEPOINT
3555 : : {
3556 : 49564300 : size_t len = jl_nparams(t);
3557 [ - + ]: 49564300 : if (len == 0)
3558 : 0 : return NULL;
3559 [ + + ]: 49564300 : if (i < len-1)
3560 : 34816600 : return jl_tparam(t, i);
3561 : 14747700 : jl_value_t *last = jl_unwrap_unionall(jl_tparam(t, len-1));
3562 [ + + ]: 14747700 : if (jl_is_vararg(last)) {
3563 : 659328 : jl_value_t *n = jl_unwrap_vararg_num(last);
3564 [ + + - + : 659328 : if (n && jl_is_long(n) && i >= len-1+jl_unbox_long(n))
- - ]
3565 : 0 : return NULL;
3566 : 659328 : return jl_unwrap_vararg(last);
3567 : : }
3568 [ + + ]: 14088400 : if (i == len-1)
3569 : 11926600 : return jl_tparam(t, i);
3570 : 2161820 : return NULL;
3571 : : }
3572 : :
3573 : 10351100 : static int tuple_morespecific(jl_datatype_t *cdt, jl_datatype_t *pdt, int invariant, jl_typeenv_t *env)
3574 : : {
3575 : 10351100 : size_t plen = jl_nparams(pdt);
3576 [ + + ]: 10351100 : if (plen == 0) return 0;
3577 : 10237500 : size_t clen = jl_nparams(cdt);
3578 [ + + ]: 10237500 : if (clen == 0) return 1;
3579 : 10203300 : int i = 0;
3580 : 10203300 : jl_value_t *clast = jl_tparam(cdt,clen-1);
3581 : 10203300 : jl_vararg_kind_t ckind = jl_vararg_kind(clast);
3582 : 10203300 : int cva = ckind > JL_VARARG_INT;
3583 : 10203300 : int pva = jl_vararg_kind(jl_tparam(pdt,plen-1)) > JL_VARARG_INT;
3584 : 10203300 : int cdiag = 0, pdiag = 0;
3585 : 10203300 : int some_morespecific = 0;
3586 : 14615000 : while (1) {
3587 [ + + + + : 24818200 : if (cva && pva && i >= clen && i >= plen)
+ + + + ]
3588 : 36065 : break;
3589 : :
3590 : 24782200 : jl_value_t *ce = nth_tuple_elt(cdt, i);
3591 : 24782200 : jl_value_t *pe = nth_tuple_elt(pdt, i);
3592 : :
3593 [ + + ]: 24782200 : if (ce == NULL) {
3594 [ + + ]: 1084900 : if (pe == NULL) break;
3595 : 287802 : return 1;
3596 : : }
3597 [ + + ]: 23697300 : if (pe == NULL) {
3598 [ + + + + ]: 279828 : if (!cva && !some_morespecific)
3599 : 115999 : return 0;
3600 : 163829 : break;
3601 : : }
3602 : :
3603 [ + + ]: 23417400 : if (type_morespecific_(pe, ce, invariant, env)) {
3604 [ - + ]: 1779680 : assert(!type_morespecific_(ce, pe, invariant, env));
3605 : 1779680 : return 0;
3606 : : }
3607 : :
3608 [ + + + + : 21637700 : if (!cdiag && jl_is_typevar(ce) && num_occurs((jl_tvar_t*)ce,env) > 1)
+ + ]
3609 : 384007 : cdiag = 1;
3610 [ + + + + : 21637700 : if (!pdiag && jl_is_typevar(pe) && num_occurs((jl_tvar_t*)pe,env) > 1)
+ + ]
3611 : 641146 : pdiag = 1;
3612 : :
3613 : : // in Tuple{a,b...} and Tuple{c,d...} allow b and d to be disjoint
3614 [ + + + + : 21637700 : if (cva && pva && i >= clen-1 && i >= plen-1 && (some_morespecific || (cdiag && !pdiag)))
+ + + + +
+ + + +
+ ]
3615 : 59246 : return 1;
3616 : :
3617 : 21578500 : int cms = type_morespecific_(ce, pe, invariant, env);
3618 : :
3619 [ + + + + ]: 21578500 : if (!cms && !sub_msp(ce, pe, env)) {
3620 : : /*
3621 : : A bound vararg tuple can be more specific despite disjoint elements in order to
3622 : : preserve transitivity. For example in
3623 : : A = Tuple{Array{T,N}, Vararg{Int,N}} where {T,N}
3624 : : B = Tuple{Array, Int}
3625 : : C = Tuple{AbstractArray, Int, Array}
3626 : : we need A < B < C and A < C.
3627 : : */
3628 [ + + + + : 6963540 : return some_morespecific && cva && ckind == JL_VARARG_BOUND && num_occurs((jl_tvar_t*)jl_unwrap_vararg_num(clast), env) > 1;
+ + + + ]
3629 : : }
3630 : :
3631 : : // Tuple{..., T} not more specific than Tuple{..., Vararg{S}} if S is diagonal
3632 [ + + + + : 14615000 : if (!cms && i == clen-1 && clen == plen && !cva && pva && eq_msp(ce, pe, env) &&
+ + + + +
+ + + ]
3633 [ + + + - : 12071 : jl_is_typevar(ce) && jl_is_typevar(pe) && !cdiag && pdiag)
+ - + - ]
3634 : 2 : return 0;
3635 : :
3636 [ + + ]: 14615000 : if (cms) some_morespecific = 1;
3637 : 14615000 : i++;
3638 : : }
3639 [ + + + + : 996989 : if (cva && pva && clen > plen && (!pdiag || cdiag))
+ + + + -
+ ]
3640 : 268 : return 1;
3641 [ + + + + : 996721 : if (cva && !pva && !some_morespecific)
+ + ]
3642 : 29496 : return 0;
3643 [ + + + + : 967225 : return some_morespecific || (cdiag && !pdiag);
+ + ]
3644 : : }
3645 : :
3646 : 283788 : static size_t tuple_full_length(jl_value_t *t)
3647 : : {
3648 : 283788 : size_t n = jl_nparams(t);
3649 [ + + ]: 283788 : if (n == 0) return 0;
3650 : 275449 : jl_value_t *last = jl_unwrap_unionall(jl_tparam(t,n-1));
3651 [ - + ]: 275449 : if (jl_is_vararg(last)) {
3652 : 0 : jl_value_t *N = jl_unwrap_vararg_num(last);
3653 [ # # ]: 0 : if (jl_is_long(N))
3654 : 0 : n += jl_unbox_long(N)-1;
3655 : : }
3656 : 275449 : return n;
3657 : : }
3658 : :
3659 : : // Called when a is a bound-vararg and b is not a vararg. Sets the vararg length
3660 : : // in a to match b, as long as this makes some earlier argument more specific.
3661 : 283788 : static int args_morespecific_fix1(jl_value_t *a, jl_value_t *b, int swap, jl_typeenv_t *env)
3662 : : {
3663 : 283788 : size_t n = jl_nparams(a);
3664 : 283788 : int taillen = tuple_full_length(b)-n+1;
3665 [ + + ]: 283788 : if (taillen <= 0)
3666 : 37230 : return -1;
3667 [ - + ]: 246558 : assert(jl_is_va_tuple((jl_datatype_t*)a));
3668 : 246558 : jl_datatype_t *new_a = NULL;
3669 : 246558 : jl_value_t *e[2] = { jl_unwrap_vararg_num(jl_unwrap_unionall(jl_tparam(a, n-1))), jl_box_long(taillen) };
3670 : 246558 : JL_GC_PUSH2(&new_a, &e[1]);
3671 : 246558 : new_a = (jl_datatype_t*)jl_instantiate_type_with((jl_value_t*)a, e, 1);
3672 : 246558 : int changed = 0;
3673 [ + + ]: 486333 : for (size_t i = 0; i < n-1; i++) {
3674 [ + + ]: 479264 : if (jl_tparam(a, i) != jl_tparam(new_a, i)) {
3675 : 239489 : changed = 1;
3676 : 239489 : break;
3677 : : }
3678 : : }
3679 : 246558 : int ret = -1;
3680 [ + + ]: 246558 : if (changed) {
3681 [ - + ]: 239489 : if (eq_msp(b, (jl_value_t*)new_a, env))
3682 : 0 : ret = swap;
3683 [ + + ]: 239489 : else if (swap)
3684 : 128196 : ret = type_morespecific_(b, (jl_value_t*)new_a, 0, env);
3685 : : else
3686 : 111293 : ret = type_morespecific_((jl_value_t*)new_a, b, 0, env);
3687 : : }
3688 : 246558 : JL_GC_POP();
3689 : 246558 : return ret;
3690 : : }
3691 : :
3692 : 351569000 : static int count_occurs(jl_value_t *t, jl_tvar_t *v)
3693 : : {
3694 [ + + ]: 351569000 : if (t == (jl_value_t*)v)
3695 : 76175600 : return 1;
3696 [ + + ]: 275393000 : if (jl_is_uniontype(t)) {
3697 : 6967040 : int a = count_occurs(((jl_uniontype_t*)t)->a, v);
3698 : 6967040 : int b = count_occurs(((jl_uniontype_t*)t)->b, v);
3699 : 6967040 : return a > b ? a : b;
3700 : : }
3701 [ + + ]: 268426000 : if (jl_is_unionall(t)) {
3702 [ + + ]: 46862900 : if (((jl_unionall_t*)t)->var == v)
3703 : 412 : return 0;
3704 : 46862500 : return count_occurs(((jl_unionall_t*)t)->body, v);
3705 : : }
3706 [ + + ]: 221563000 : if (jl_is_vararg(t)) {
3707 : 1021560 : jl_vararg_t *vm = (jl_vararg_t*)t;
3708 [ + + ]: 1021560 : if (vm->T) {
3709 [ + + ]: 1021550 : return count_occurs(vm->T, v) + (vm->N ? count_occurs(vm->N, v) : 0);
3710 : : }
3711 : : }
3712 [ + + ]: 220542000 : if (jl_is_datatype(t)) {
3713 : 107629000 : int i, c=0;
3714 [ + + ]: 327271000 : for(i=0; i < jl_nparams(t); i++)
3715 : 219643000 : c += count_occurs(jl_tparam(t,i), v);
3716 : 107629000 : return c;
3717 : : }
3718 : 112913000 : return 0;
3719 : : }
3720 : :
3721 : 1820100 : static int num_occurs(jl_tvar_t *v, jl_typeenv_t *env)
3722 : : {
3723 [ + - ]: 2036990 : while (env != NULL) {
3724 [ + + ]: 2036990 : if (env->var == v)
3725 : 1820100 : return (int)(ssize_t)env->val;
3726 : 216883 : env = env->prev;
3727 : : }
3728 : 0 : return 0;
3729 : : }
3730 : :
3731 : : #define HANDLE_UNIONALL_A \
3732 : : jl_unionall_t *ua = (jl_unionall_t*)a; \
3733 : : jl_typeenv_t newenv = { ua->var, 0x0, env }; \
3734 : : newenv.val = (jl_value_t*)(intptr_t)count_occurs(ua->body, ua->var); \
3735 : : return type_morespecific_(ua->body, b, invariant, &newenv)
3736 : :
3737 : : #define HANDLE_UNIONALL_B \
3738 : : jl_unionall_t *ub = (jl_unionall_t*)b; \
3739 : : jl_typeenv_t newenv = { ub->var, 0x0, env }; \
3740 : : newenv.val = (jl_value_t*)(intptr_t)count_occurs(ub->body, ub->var); \
3741 : : return type_morespecific_(a, ub->body, invariant, &newenv)
3742 : :
3743 : 246603000 : static int type_morespecific_(jl_value_t *a, jl_value_t *b, int invariant, jl_typeenv_t *env)
3744 : : {
3745 [ + + ]: 246603000 : if (a == b)
3746 : 42606200 : return 0;
3747 : :
3748 [ + + + + ]: 203997000 : if (jl_is_tuple_type(a) && jl_is_tuple_type(b)) {
3749 : : // When one is JL_VARARG_BOUND and the other has fixed length,
3750 : : // allow the argument length to fix the tvar
3751 : 10546800 : jl_vararg_kind_t akind = jl_va_tuple_kind((jl_datatype_t*)a);
3752 : 10546800 : jl_vararg_kind_t bkind = jl_va_tuple_kind((jl_datatype_t*)b);
3753 : 10546800 : int ans = -1;
3754 [ + + + + ]: 10546800 : if (akind == JL_VARARG_BOUND && bkind < JL_VARARG_BOUND) {
3755 : 134447 : ans = args_morespecific_fix1(a, b, 0, env);
3756 [ + + ]: 134447 : if (ans == 1) return 1;
3757 : : }
3758 [ + + + + ]: 10471200 : if (bkind == JL_VARARG_BOUND && akind < JL_VARARG_BOUND) {
3759 : 149341 : ans = args_morespecific_fix1(b, a, 1, env);
3760 [ + + ]: 149341 : if (ans == 0) return 0;
3761 : : }
3762 : 10351100 : return tuple_morespecific((jl_datatype_t*)a, (jl_datatype_t*)b, invariant, env);
3763 : : }
3764 : :
3765 [ + + ]: 193450000 : if (!invariant) {
3766 [ + + ]: 171617000 : if ((jl_datatype_t*)a == jl_any_type) return 0;
3767 [ + + + + ]: 169225000 : if ((jl_datatype_t*)b == jl_any_type && !jl_is_typevar(a)) return 1;
3768 : : }
3769 : :
3770 [ + + ]: 188364000 : if (jl_is_uniontype(a)) {
3771 [ + + ]: 16357100 : if (jl_is_unionall(b)) {
3772 : 3612840 : HANDLE_UNIONALL_B;
3773 : : }
3774 : : // Union a is more specific than b if some element of a is more specific than b, but
3775 : : // not vice-versa.
3776 [ + + ]: 12744200 : if (sub_msp(b, a, env))
3777 : 786564 : return 0;
3778 : 11957700 : jl_uniontype_t *u = (jl_uniontype_t*)a;
3779 [ + + + + ]: 11957700 : if (type_morespecific_(u->a, b, invariant, env) || type_morespecific_(u->b, b, invariant, env)) {
3780 [ + + ]: 595555 : if (jl_is_uniontype(b)) {
3781 : 111129 : jl_uniontype_t *v = (jl_uniontype_t*)b;
3782 [ + + + + ]: 111129 : if (type_morespecific_(v->a, a, invariant, env) || type_morespecific_(v->b, a, invariant, env))
3783 : 58 : return 0;
3784 : : }
3785 : 595497 : return 1;
3786 : : }
3787 : 11362100 : return 0;
3788 : : }
3789 : :
3790 [ + + + + ]: 172006000 : if (jl_is_type_type(a) && !invariant) {
3791 [ - + ]: 12090300 : if (b == (jl_value_t*)jl_typeofbottom_type)
3792 : 0 : return 0;
3793 : 12090300 : jl_value_t *tp0a = jl_tparam0(a);
3794 [ + + ]: 12090300 : if (jl_is_typevar(tp0a)) {
3795 : 8901940 : jl_value_t *ub = ((jl_tvar_t*)tp0a)->ub;
3796 [ + + + - ]: 8901940 : if (jl_is_kind(b) && !sub_msp((jl_value_t*)jl_any_type, ub, env))
3797 : 23265 : return 1;
3798 : : }
3799 [ + + ]: 3188310 : else if (tp0a == jl_bottom_type) {
3800 [ + - ]: 336700 : if (sub_msp(b, (jl_value_t*)jl_type_type, env))
3801 : 336700 : return 1;
3802 : : }
3803 [ + + + + ]: 2851610 : else if (b == (jl_value_t*)jl_datatype_type || b == (jl_value_t*)jl_unionall_type ||
3804 [ + + ]: 2851610 : b == (jl_value_t*)jl_uniontype_type) {
3805 : 233 : return 1;
3806 : : }
3807 : : }
3808 : :
3809 [ + + ]: 171646000 : if (jl_is_uniontype(b)) {
3810 [ + + ]: 22468700 : if (jl_is_unionall(a)) {
3811 : 3702460 : HANDLE_UNIONALL_A;
3812 : : }
3813 : 18766300 : jl_uniontype_t *u = (jl_uniontype_t*)b;
3814 [ + + + + ]: 18766300 : if (type_morespecific_(a, u->a, invariant, env) || type_morespecific_(a, u->b, invariant, env))
3815 : 216592 : return !type_morespecific_(b, a, invariant, env);
3816 : 18549700 : return 0;
3817 : : }
3818 : :
3819 [ + + + + ]: 149178000 : if (jl_is_datatype(a) && jl_is_datatype(b)) {
3820 : 59858800 : jl_datatype_t *tta = (jl_datatype_t*)a, *ttb = (jl_datatype_t*)b;
3821 : : // Type{Union{}} is more specific than other types, so TypeofBottom must be too
3822 [ + + + + : 59858800 : if (tta == jl_typeofbottom_type && (jl_is_kind(b) || jl_is_type_type(b)))
- + ]
3823 : 72 : return 1;
3824 : 59858700 : int super = 0;
3825 [ + + ]: 157822000 : while (tta != jl_any_type) {
3826 [ + + ]: 109741000 : if (tta->name == ttb->name) {
3827 [ + + ]: 11777300 : if (super) {
3828 [ + + ]: 1544510 : if (tta->name != jl_type_typename) return 1;
3829 : 31210 : jl_value_t *tp0 = jl_tparam0(b);
3830 [ + + ]: 31210 : if (jl_is_typevar(tp0)) {
3831 [ - + ]: 23265 : if (sub_msp((jl_value_t*)jl_any_type, ((jl_tvar_t*)tp0)->ub, env))
3832 : 0 : return 1;
3833 : : }
3834 : : }
3835 [ - + ]: 10264000 : assert(jl_nparams(tta) == jl_nparams(ttb));
3836 : 10264000 : int ascore=0, bscore=0, ascore1=0, bscore1=0, adiag=0, bdiag=0;
3837 [ + + ]: 22911400 : for(size_t i=0; i < jl_nparams(tta); i++) {
3838 : 13078200 : jl_value_t *apara = jl_tparam(tta,i);
3839 : 13078200 : jl_value_t *bpara = jl_tparam(ttb,i);
3840 : 13078200 : int afree = jl_has_free_typevars(apara);
3841 : 13078200 : int bfree = jl_has_free_typevars(bpara);
3842 [ + + + + : 13078200 : if (!afree && !bfree && !jl_types_equal(apara, bpara))
+ + ]
3843 : 430821 : return 0;
3844 [ + + + + : 12647400 : if (type_morespecific_(apara, bpara, 1, env) && (jl_is_typevar(apara) || !afree || bfree))
+ + + + ]
3845 : 1612700 : ascore += 1;
3846 [ + + + + : 11034700 : else if (type_morespecific_(bpara, apara, 1, env) && (jl_is_typevar(bpara) || !bfree || afree))
+ + + + ]
3847 : 1945730 : bscore += 1;
3848 [ + + ]: 9088970 : else if (eq_msp(apara, bpara, env)) {
3849 [ + + + + ]: 3144270 : if (!afree && bfree)
3850 : 3443 : ascore += 1;
3851 [ + + + + ]: 3140830 : else if (afree && !bfree)
3852 : 3443 : bscore += 1;
3853 : : }
3854 [ + + + + : 12647400 : if (jl_is_typevar(bpara) && !jl_is_typevar(apara) && !jl_is_type(apara))
+ + ]
3855 : 262833 : ascore1 = 1;
3856 [ + + + + : 12384600 : else if (jl_is_typevar(apara) && !jl_is_typevar(bpara) && !jl_is_type(bpara))
+ + ]
3857 : 263867 : bscore1 = 1;
3858 [ + + + + ]: 12647400 : if (!adiag && jl_is_typevar(apara)) {
3859 [ + + ]: 14528800 : for(int j=i+1; j < jl_nparams(tta); j++) {
3860 [ + + ]: 4576150 : if (jl_has_typevar(jl_tparam(tta,j), (jl_tvar_t*)apara)) {
3861 : 1646 : adiag = 1; break;
3862 : : }
3863 : : }
3864 : : }
3865 [ + + + + ]: 12647400 : if (!bdiag && jl_is_typevar(bpara)) {
3866 [ + + ]: 14247800 : for(int j=i+1; j < jl_nparams(ttb); j++) {
3867 [ + + ]: 4625730 : if (jl_has_typevar(jl_tparam(ttb,j), (jl_tvar_t*)bpara)) {
3868 : 1872 : bdiag = 1; break;
3869 : : }
3870 : : }
3871 : : }
3872 : : }
3873 [ + + ]: 9833140 : if (ascore1 > bscore1)
3874 : 203900 : return 1;
3875 [ + + + + : 9629240 : if (bscore1 > ascore1 || bscore > ascore || bdiag > adiag)
+ + ]
3876 : 1684670 : return 0;
3877 [ + + + + ]: 7944560 : return ascore > bscore || adiag > bdiag;
3878 : : }
3879 : 97963800 : tta = tta->super; super = 1;
3880 : : }
3881 : 48081400 : return 0;
3882 : : }
3883 : :
3884 [ + + ]: 89318800 : if (jl_is_typevar(a)) {
3885 [ + + ]: 19427000 : if (jl_is_typevar(b)) {
3886 : 13176500 : return (( type_morespecific_((jl_value_t*)((jl_tvar_t*)a)->ub,
3887 [ - + ]: 1498050 : (jl_value_t*)((jl_tvar_t*)b)->ub, 0, env) &&
3888 : 1498050 : !type_morespecific_((jl_value_t*)((jl_tvar_t*)a)->lb,
3889 [ + + - + ]: 26353000 : (jl_value_t*)((jl_tvar_t*)b)->lb, 0, env)) ||
3890 : 11678400 : ( type_morespecific_((jl_value_t*)((jl_tvar_t*)b)->lb,
3891 [ # # ]: 0 : (jl_value_t*)((jl_tvar_t*)a)->lb, 0, env) &&
3892 : 0 : !type_morespecific_((jl_value_t*)((jl_tvar_t*)b)->ub,
3893 : : (jl_value_t*)((jl_tvar_t*)a)->ub, 0, env)));
3894 : : }
3895 [ + + ]: 6250540 : if (!jl_is_type(b))
3896 : 263867 : return 0;
3897 [ + + ]: 5986670 : if (invariant) {
3898 [ + + ]: 3377360 : if (((jl_tvar_t*)a)->ub == jl_bottom_type)
3899 : 2 : return 1;
3900 [ + + ]: 3377360 : if (!jl_has_free_typevars(b))
3901 : 1692980 : return 0;
3902 [ + + ]: 1684380 : if (eq_msp(((jl_tvar_t*)a)->ub, b, env))
3903 : 33290 : return num_occurs((jl_tvar_t*)a, env) >= 2;
3904 : : }
3905 : : else {
3906 : : // need `{T,T} where T` more specific than `{Any, Any}`
3907 [ + + + + : 2773160 : if (b == (jl_value_t*)jl_any_type && ((jl_tvar_t*)a)->ub == (jl_value_t*)jl_any_type &&
+ + ]
3908 : 163847 : num_occurs((jl_tvar_t*)a, env) >= 2)
3909 : 148521 : return 1;
3910 : : }
3911 : 4111880 : return type_morespecific_(((jl_tvar_t*)a)->ub, b, 0, env);
3912 : : }
3913 [ + + ]: 69891800 : if (jl_is_typevar(b)) {
3914 [ + + ]: 6513400 : if (!jl_is_type(a))
3915 : 526700 : return 1;
3916 [ + + ]: 5986700 : if (invariant) {
3917 [ + + ]: 3895540 : if (((jl_tvar_t*)b)->ub == jl_bottom_type)
3918 : 1 : return 0;
3919 [ + + ]: 3895540 : if (jl_has_free_typevars(a)) {
3920 [ + + ]: 1932840 : if (type_morespecific_(a, ((jl_tvar_t*)b)->ub, 0, env))
3921 : 607343 : return 1;
3922 [ + + ]: 1325490 : if (eq_msp(a, ((jl_tvar_t*)b)->ub, env))
3923 : 18839 : return num_occurs((jl_tvar_t*)b, env) < 2;
3924 : 1306650 : return 0;
3925 : : }
3926 : : else {
3927 [ + + ]: 1962700 : if (obviously_disjoint(a, ((jl_tvar_t*)b)->ub, 1))
3928 : 1067760 : return 0;
3929 [ + + ]: 894938 : if (type_morespecific_(((jl_tvar_t*)b)->ub, a, 0, env))
3930 : 139783 : return 0;
3931 : 755155 : return 1;
3932 : : }
3933 : : }
3934 : 2091160 : return type_morespecific_(a, ((jl_tvar_t*)b)->ub, 0, env);
3935 : : }
3936 : :
3937 [ + + ]: 63378400 : if (jl_is_unionall(a)) {
3938 : 27799600 : HANDLE_UNIONALL_A;
3939 : : }
3940 [ + + ]: 35578800 : if (jl_is_unionall(b)) {
3941 : 34125300 : HANDLE_UNIONALL_B;
3942 : : }
3943 : :
3944 : 1453510 : return 0;
3945 : : }
3946 : :
3947 : 80403100 : JL_DLLEXPORT int jl_type_morespecific(jl_value_t *a, jl_value_t *b)
3948 : : {
3949 [ + + ]: 80403100 : if (obviously_disjoint(a, b, 1))
3950 : 54845300 : return 0;
3951 [ + - - + ]: 25557800 : if (jl_has_free_typevars(a) || jl_has_free_typevars(b))
3952 : 0 : return 0;
3953 [ + + ]: 25557800 : if (jl_subtype(b, a))
3954 : 7213210 : return 0;
3955 [ + + ]: 18344600 : if (jl_subtype(a, b))
3956 : 8365150 : return 1;
3957 : 9979420 : return type_morespecific_(a, b, 0, NULL);
3958 : : }
3959 : :
3960 : 0 : JL_DLLEXPORT int jl_type_morespecific_no_subtype(jl_value_t *a, jl_value_t *b)
3961 : : {
3962 : 0 : return type_morespecific_(a, b, 0, NULL);
3963 : : }
3964 : :
3965 : : #ifdef __cplusplus
3966 : : }
3967 : : #endif
|
