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 : 100452000 : static jl_varbinding_t *lookup(jl_stenv_t *e, jl_tvar_t *v) JL_GLOBALLY_ROOTED JL_NOTSAFEPOINT
114 : : {
115 : 100452000 : jl_varbinding_t *b = e->vars;
116 [ + + ]: 210843000 : while (b != NULL) {
117 [ + + ]: 209243000 : if (b->var == v) return b;
118 : 110391000 : b = b->prev;
119 : : }
120 : 1599890 : return b;
121 : : }
122 : : #endif
123 : :
124 : 304655000 : static int statestack_get(jl_unionstate_t *st, int i) JL_NOTSAFEPOINT
125 : : {
126 [ + - + - ]: 304655000 : assert(i >= 0 && i < sizeof(st->stack) * 8);
127 : : // get the `i`th bit in an array of 32-bit words
128 : 304655000 : return (st->stack[i>>5] & (1u<<(i&31))) != 0;
129 : : }
130 : :
131 : 145967000 : static void statestack_set(jl_unionstate_t *st, int i, int val) JL_NOTSAFEPOINT
132 : : {
133 [ + - + - ]: 145967000 : assert(i >= 0 && i < sizeof(st->stack) * 8);
134 [ + + ]: 145967000 : if (val)
135 : 63534700 : st->stack[i>>5] |= (1u<<(i&31));
136 : : else
137 : 82432700 : st->stack[i>>5] &= ~(1u<<(i&31));
138 : 145967000 : }
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 : 312918000 : static void save_env(jl_stenv_t *e, jl_value_t **root, jl_savedenv_t *se)
164 : : {
165 : 312918000 : jl_varbinding_t *v = e->vars;
166 : 312918000 : int len=0;
167 [ + + ]: 457478000 : while (v != NULL) {
168 : 144559000 : len++;
169 : 144559000 : v = v->prev;
170 : : }
171 [ + + ]: 312918000 : if (root)
172 : 311008000 : *root = (jl_value_t*)jl_alloc_svec(len * 3);
173 [ + + ]: 312918000 : 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 : 312918000 : int i=0, j=0; v = e->vars;
178 [ + + ]: 457478000 : while (v != NULL) {
179 [ + + ]: 144559000 : if (root) {
180 : 141806000 : jl_svecset(*root, i++, v->lb);
181 : 141806000 : jl_svecset(*root, i++, v->ub);
182 : 141806000 : jl_svecset(*root, i++, (jl_value_t*)v->innervars);
183 : : }
184 : 144559000 : se->buf[j++] = v->occurs_inv;
185 : 144559000 : se->buf[j++] = v->occurs_cov;
186 : 144559000 : v = v->prev;
187 : : }
188 : 312918000 : se->rdepth = e->Runions.depth;
189 : 312918000 : }
190 : :
191 : 312918000 : static void free_env(jl_savedenv_t *se) JL_NOTSAFEPOINT
192 : : {
193 [ + + ]: 312918000 : if (se->buf != se->_space)
194 : 686931 : free(se->buf);
195 : 312918000 : se->buf = NULL;
196 : 312918000 : }
197 : :
198 : 281422000 : static void restore_env(jl_stenv_t *e, jl_value_t *root, jl_savedenv_t *se) JL_NOTSAFEPOINT
199 : : {
200 : 281422000 : jl_varbinding_t *v = e->vars;
201 : 281422000 : int i = 0, j = 0;
202 [ + + ]: 360709000 : while (v != NULL) {
203 [ + + ]: 79287400 : if (root) v->lb = jl_svecref(root, i);
204 : 79287400 : i++;
205 [ + + ]: 79287400 : if (root) v->ub = jl_svecref(root, i);
206 : 79287400 : i++;
207 [ + + ]: 79287400 : if (root) v->innervars = (jl_array_t*)jl_svecref(root, i);
208 : 79287400 : i++;
209 : 79287400 : v->occurs_inv = se->buf[j++];
210 : 79287400 : v->occurs_cov = se->buf[j++];
211 : 79287400 : v = v->prev;
212 : : }
213 : 281422000 : e->Runions.depth = se->rdepth;
214 [ + + + + ]: 281422000 : if (e->envout && e->envidx < e->envsz)
215 : 2103260 : memset(&e->envout[e->envidx], 0, (e->envsz - e->envidx)*sizeof(void*));
216 : 281422000 : }
217 : :
218 : : // type utilities
219 : :
220 : : // quickly test that two types are identical
221 : 102364000 : static int obviously_egal(jl_value_t *a, jl_value_t *b)
222 : : {
223 [ - + ]: 102364000 : if (a == (jl_value_t*)jl_typeofbottom_type->super)
224 : 0 : a = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
225 [ + + ]: 102364000 : if (b == (jl_value_t*)jl_typeofbottom_type->super)
226 : 169 : b = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
227 [ + + ]: 102364000 : if (a == b) return 1;
228 [ + + ]: 97017100 : if (jl_typeof(a) != jl_typeof(b)) return 0;
229 [ + + ]: 35306300 : if (jl_is_datatype(a)) {
230 : 12852700 : jl_datatype_t *ad = (jl_datatype_t*)a;
231 : 12852700 : jl_datatype_t *bd = (jl_datatype_t*)b;
232 [ + + ]: 12852700 : if (ad->name != bd->name) return 0;
233 [ + + + + ]: 3252660 : if (ad->isconcretetype || bd->isconcretetype) return 0;
234 : 2362060 : size_t i, np = jl_nparams(ad);
235 [ + + ]: 2362060 : if (np != jl_nparams(bd)) return 0;
236 [ + + ]: 2266280 : for (i = 0; i < np; i++) {
237 [ + + ]: 2260520 : if (!obviously_egal(jl_tparam(ad,i), jl_tparam(bd,i)))
238 : 2242020 : return 0;
239 : : }
240 : 5752 : return 1;
241 : : }
242 [ + + ]: 22453700 : if (jl_is_uniontype(a)) {
243 [ + + + + ]: 1183280 : return obviously_egal(((jl_uniontype_t*)a)->a, ((jl_uniontype_t*)b)->a) &&
244 : 505860 : obviously_egal(((jl_uniontype_t*)a)->b, ((jl_uniontype_t*)b)->b);
245 : : }
246 [ + + ]: 21776200 : if (jl_is_unionall(a)) {
247 [ + + + + ]: 4041920 : return ((jl_unionall_t*)a)->var == ((jl_unionall_t*)b)->var &&
248 : 1844980 : obviously_egal(((jl_unionall_t*)a)->body, ((jl_unionall_t*)b)->body);
249 : : }
250 [ + + ]: 19579300 : if (jl_is_vararg(a)) {
251 : 29813 : jl_vararg_t *vma = (jl_vararg_t *)a;
252 : 29813 : jl_vararg_t *vmb = (jl_vararg_t *)b;
253 [ + + ]: 37574 : return obviously_egal(jl_unwrap_vararg(vma), jl_unwrap_vararg(vmb)) &&
254 [ + + + + : 7761 : ((!vma->N && !vmb->N) || (vma->N && vmb->N && obviously_egal(vma->N, vmb->N)));
+ + + + +
+ ]
255 : : }
256 [ + + ]: 19549500 : if (jl_is_typevar(a)) return 0;
257 [ + - + + ]: 10906000 : return !jl_is_type(a) && jl_egal(a,b);
258 : : }
259 : :
260 : 190441000 : static int obviously_unequal(jl_value_t *a, jl_value_t *b)
261 : : {
262 [ + + ]: 190441000 : if (a == (jl_value_t*)jl_typeofbottom_type->super)
263 : 12853 : a = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
264 [ + + ]: 190441000 : if (b == (jl_value_t*)jl_typeofbottom_type->super)
265 : 14377 : b = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
266 [ + + ]: 190441000 : if (a == b)
267 : 46959300 : return 0;
268 [ + + ]: 143482000 : if (jl_is_unionall(a))
269 : 22578900 : a = jl_unwrap_unionall(a);
270 [ + + ]: 143482000 : if (jl_is_unionall(b))
271 : 28714300 : b = jl_unwrap_unionall(b);
272 [ + + ]: 143482000 : if (jl_is_datatype(a)) {
273 [ + + ]: 123401000 : if (b == jl_bottom_type)
274 : 37191 : return 1;
275 [ + + ]: 123363000 : if (jl_is_datatype(b)) {
276 : 121036000 : jl_datatype_t *ad = (jl_datatype_t*)a;
277 : 121036000 : jl_datatype_t *bd = (jl_datatype_t*)b;
278 [ + + + + ]: 121036000 : if (a == (jl_value_t*)jl_typeofbottom_type && bd->name == jl_type_typename)
279 : 11152 : return obviously_unequal(jl_bottom_type, jl_tparam(bd, 0));
280 [ + + + + ]: 121025000 : if (ad->name == jl_type_typename && b == (jl_value_t*)jl_typeofbottom_type)
281 : 10595 : return obviously_unequal(jl_tparam(ad, 0), jl_bottom_type);
282 [ + + ]: 121014000 : if (ad->name != bd->name)
283 : 34579600 : return 1;
284 : 86434700 : int istuple = (ad->name == jl_tuple_typename);
285 [ + + + + : 120301000 : if ((jl_is_concrete_type(a) || jl_is_concrete_type(b)) &&
+ + ]
286 : 33866200 : jl_type_equality_is_identity(a, b)) {
287 [ + + + - ]: 31721600 : if (!istuple && ad->name != jl_type_typename) // HACK: can't properly normalize Tuple{Float64} == Tuple{<:Float64} like types or Type{T} types
288 : 7199880 : return 1;
289 : : }
290 : : size_t i, np;
291 [ + + ]: 79234900 : if (istuple) {
292 : 53086700 : size_t na = jl_nparams(ad), nb = jl_nparams(bd);
293 [ + + ]: 53086700 : if (jl_is_va_tuple(ad)) {
294 : 3625670 : na -= 1;
295 [ + + ]: 3625670 : if (jl_is_va_tuple(bd))
296 : 2476350 : nb -= 1;
297 : : }
298 [ + + ]: 49461000 : else if (jl_is_va_tuple(bd)) {
299 : 735451 : nb -= 1;
300 : : }
301 [ + + ]: 48725500 : else if (na != nb) {
302 : 8622670 : return 1;
303 : : }
304 : 44464000 : np = na < nb ? na : nb;
305 : : }
306 : : else {
307 : 26148200 : np = jl_nparams(ad);
308 [ - + ]: 26148200 : if (np != jl_nparams(bd))
309 : 0 : return 1;
310 : : }
311 [ + + ]: 146816000 : for (i = 0; i < np; i++) {
312 [ + + ]: 123987000 : if (obviously_unequal(jl_tparam(ad, i), jl_tparam(bd, i)))
313 : 47783200 : return 1;
314 : : }
315 : : }
316 : : }
317 [ + + + + ]: 20081400 : else if (a == jl_bottom_type && jl_is_datatype(b)) {
318 : 2565 : return 1;
319 : : }
320 [ + + + + : 45235100 : if (jl_is_typevar(a) && jl_is_typevar(b) && obviously_unequal(((jl_tvar_t*)a)->ub, ((jl_tvar_t*)b)->ub))
+ + ]
321 : 516844 : return 1;
322 [ + + ]: 44718300 : if (jl_is_long(a)) {
323 [ + + + - ]: 11809 : if (jl_is_long(b) && jl_unbox_long(a) != jl_unbox_long(b))
324 : 3372 : return 1;
325 : : }
326 [ + + ]: 44706500 : else if (jl_is_long(b)) {
327 : 37462 : return 1;
328 : : }
329 [ + + + + : 44677400 : if ((jl_is_symbol(a) || jl_is_symbol(b)) && a != b)
+ - ]
330 : 112 : return 1;
331 : 44677300 : return 0;
332 : : }
333 : :
334 : 368092 : int jl_obviously_unequal(jl_value_t *a, jl_value_t *b)
335 : : {
336 : 368092 : return obviously_unequal(a, b);
337 : : }
338 : :
339 : 21370800 : static int in_union(jl_value_t *u, jl_value_t *x) JL_NOTSAFEPOINT
340 : : {
341 [ + + ]: 21370800 : if (u == x) return 1;
342 [ + + ]: 17335600 : if (!jl_is_uniontype(u)) return 0;
343 [ + + + + ]: 3506440 : return in_union(((jl_uniontype_t*)u)->a, x) || in_union(((jl_uniontype_t*)u)->b, x);
344 : : }
345 : :
346 : 137095000 : static int obviously_disjoint(jl_value_t *a, jl_value_t *b, int specificity)
347 : : {
348 [ + + + + : 137095000 : if (a == b || a == (jl_value_t*)jl_any_type || b == (jl_value_t*)jl_any_type)
+ + ]
349 : 60519900 : return 0;
350 [ + + + + ]: 76575100 : if (specificity && a == (jl_value_t*)jl_typeofbottom_type)
351 : 540 : return 0;
352 [ + + + + : 88478000 : if (jl_is_concrete_type(a) && jl_is_concrete_type(b) &&
+ + ]
353 : 11903400 : jl_type_equality_is_identity(a, b) &&
354 [ + + ]: 11896100 : (((jl_datatype_t*)a)->name != jl_tuple_typename ||
355 [ + + ]: 1776140 : ((jl_datatype_t*)b)->name != jl_tuple_typename))
356 : 10189300 : return 1;
357 [ + + ]: 66385200 : if (jl_is_unionall(a)) a = jl_unwrap_unionall(a);
358 [ + + ]: 66385200 : if (jl_is_unionall(b)) b = jl_unwrap_unionall(b);
359 [ + + + + ]: 80873100 : if (jl_is_datatype(a) && jl_is_datatype(b)) {
360 : 63554000 : jl_datatype_t *ad = (jl_datatype_t*)a, *bd = (jl_datatype_t*)b;
361 [ + + ]: 63554000 : if (ad->name != bd->name) {
362 : 18982900 : jl_datatype_t *temp = ad;
363 [ + + + + ]: 58782100 : while (temp != jl_any_type && temp->name != bd->name)
364 : 39799200 : temp = temp->super;
365 [ + + ]: 18982900 : if (temp == jl_any_type) {
366 : 18193500 : temp = bd;
367 [ + + + + ]: 52780400 : while (temp != jl_any_type && temp->name != ad->name)
368 : 34586900 : temp = temp->super;
369 [ + + ]: 18193500 : if (temp == jl_any_type)
370 : 17630500 : return 1;
371 : 563020 : bd = temp;
372 : : }
373 : : else {
374 : 789438 : ad = temp;
375 : : }
376 [ + + ]: 1352460 : if (specificity) {
377 : : // account for declared subtypes taking priority (issue #21710)
378 : 400036 : return 0;
379 : : }
380 : : }
381 : 45523500 : int istuple = (ad->name == jl_tuple_typename);
382 : : size_t np;
383 [ + + ]: 45523500 : if (istuple) {
384 : 37266700 : size_t na = jl_nparams(ad), nb = jl_nparams(bd);
385 [ + + ]: 37266700 : if (jl_is_va_tuple(ad)) {
386 : 1134100 : na -= 1;
387 [ + + ]: 1134100 : if (jl_is_va_tuple(bd))
388 : 262426 : nb -= 1;
389 : : }
390 [ + + ]: 36132600 : else if (jl_is_va_tuple(bd)) {
391 : 1025130 : nb -= 1;
392 : : }
393 [ + + + + ]: 35107500 : else if (!specificity && na != nb) {
394 : : // note: some disjoint types (e.g. tuples of different lengths) can be more specific
395 : 1901460 : return 1;
396 : : }
397 : 35365200 : np = na < nb ? na : nb;
398 : : }
399 : : else {
400 : 8256780 : np = jl_nparams(ad);
401 : : }
402 : : size_t i;
403 [ + + ]: 118892000 : for (i = 0; i < np; i++) {
404 : 104404000 : jl_value_t *ai = jl_tparam(ad, i);
405 : 104404000 : jl_value_t *bi = jl_tparam(bd, i);
406 [ + + + + ]: 104404000 : if (jl_is_typevar(ai) || jl_is_typevar(bi))
407 : 8186460 : continue; // it's possible that Union{} is in this intersection
408 [ + + ]: 96217900 : if (jl_is_type(ai)) {
409 [ + + ]: 96060700 : if (jl_is_type(bi)) {
410 [ + + + - : 96060700 : if (istuple && (ai == jl_bottom_type || bi == jl_bottom_type))
- + ]
411 : : ; // TODO: this can return 1 if and when Tuple{Union{}} === Union{}
412 [ + + ]: 96060700 : else if (obviously_disjoint(ai, bi, specificity))
413 : 29116000 : return 1;
414 : : }
415 [ - + ]: 4 : else if (ai != (jl_value_t*)jl_any_type) {
416 : 0 : return 1;
417 : : }
418 : : }
419 [ + + ]: 157242 : else if (jl_is_type(bi)) {
420 [ - + ]: 56 : if (bi != (jl_value_t*)jl_any_type)
421 : 0 : return 1;
422 : : }
423 [ + + ]: 157186 : else if (!jl_egal(ai, bi)) {
424 : 18165 : return 1;
425 : : }
426 : : }
427 : : }
428 [ + + + + ]: 2831270 : else if (a == jl_bottom_type || b == jl_bottom_type) {
429 : 132569 : return 1;
430 : : }
431 : 17186600 : return 0;
432 : : }
433 : :
434 : : // compute a least upper bound of `a` and `b`
435 : 17747500 : static jl_value_t *simple_join(jl_value_t *a, jl_value_t *b)
436 : : {
437 [ + + + + : 17747500 : if (a == jl_bottom_type || b == (jl_value_t*)jl_any_type || obviously_egal(a,b))
+ + ]
438 : 15433900 : return b;
439 [ + + + + ]: 2313580 : if (b == jl_bottom_type || a == (jl_value_t*)jl_any_type)
440 : 434941 : return a;
441 [ + + + - : 1878640 : if (!(jl_is_type(a) || jl_is_typevar(a)) || !(jl_is_type(b) || jl_is_typevar(b)))
+ + - + ]
442 : 0 : return (jl_value_t*)jl_any_type;
443 [ + + + + ]: 1878640 : if (jl_is_uniontype(a) && in_union(a, b))
444 : 119135 : return a;
445 [ + + + + ]: 1759500 : if (jl_is_uniontype(b) && in_union(b, a))
446 : 17782 : return b;
447 [ + + + - : 1741720 : if (jl_is_kind(a) && jl_is_type_type(b) && jl_typeof(jl_tparam0(b)) == a)
+ - ]
448 : 249 : return a;
449 [ + + + + : 1741470 : if (jl_is_kind(b) && jl_is_type_type(a) && jl_typeof(jl_tparam0(a)) == b)
+ - ]
450 : 8 : return b;
451 [ + + + + ]: 1741460 : if (jl_is_typevar(a) && obviously_egal(b, ((jl_tvar_t*)a)->lb))
452 : 218 : return a;
453 [ + + + + ]: 1741250 : if (jl_is_typevar(b) && obviously_egal(a, ((jl_tvar_t*)b)->lb))
454 : 104846 : return b;
455 [ + + + + : 2115270 : if (!jl_has_free_typevars(a) && !jl_has_free_typevars(b) &&
+ + ]
456 : : // issue #24521: don't merge Type{T} where typeof(T) varies
457 [ + + + + ]: 478889 : !(jl_is_type_type(a) && jl_is_type_type(b) && jl_typeof(jl_tparam0(a)) != jl_typeof(jl_tparam0(b)))) {
458 [ + + ]: 478867 : if (jl_subtype(a, b)) return b;
459 [ + + ]: 471642 : if (jl_subtype(b, a)) return a;
460 : : }
461 : 1615250 : 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 : 9197470 : static jl_value_t *simple_meet(jl_value_t *a, jl_value_t *b)
467 : : {
468 [ + + + + : 9197470 : if (a == (jl_value_t*)jl_any_type || b == jl_bottom_type || obviously_egal(a,b))
+ + ]
469 : 7844960 : return b;
470 [ + + - + ]: 1352500 : if (b == (jl_value_t*)jl_any_type || a == jl_bottom_type)
471 : 54 : return a;
472 [ + + + - : 1352450 : if (!(jl_is_type(a) || jl_is_typevar(a)) || !(jl_is_type(b) || jl_is_typevar(b)))
+ + + + ]
473 : 408 : return jl_bottom_type;
474 [ + + + + ]: 1352040 : if (jl_is_uniontype(a) && in_union(a, b))
475 : 76651 : return b;
476 [ + + - + ]: 1275390 : if (jl_is_uniontype(b) && in_union(b, a))
477 : 0 : return a;
478 [ - + - - : 1275390 : if (jl_is_kind(a) && jl_is_type_type(b) && jl_typeof(jl_tparam0(b)) == a)
- - ]
479 : 0 : return b;
480 [ + + - + : 1275390 : if (jl_is_kind(b) && jl_is_type_type(a) && jl_typeof(jl_tparam0(a)) == b)
- - ]
481 : 0 : return a;
482 [ + + - + ]: 1275390 : if (jl_is_typevar(a) && obviously_egal(b, ((jl_tvar_t*)a)->ub))
483 : 0 : return a;
484 [ + + + + ]: 1275390 : if (jl_is_typevar(b) && obviously_egal(a, ((jl_tvar_t*)b)->ub))
485 : 595652 : return b;
486 [ - + ]: 679740 : if (obviously_disjoint(a, b, 0))
487 : 0 : return jl_bottom_type;
488 [ + + + + ]: 679740 : if (!jl_has_free_typevars(a) && !jl_has_free_typevars(b)) {
489 [ + + ]: 339470 : if (jl_subtype(a, b)) return a;
490 [ + - ]: 339282 : if (jl_subtype(b, a)) return b;
491 : : }
492 : 340270 : return b;
493 : : }
494 : :
495 : 14905000 : static jl_unionall_t *rename_unionall(jl_unionall_t *u)
496 : : {
497 : 14905000 : jl_tvar_t *v = jl_new_typevar(u->var->name, u->var->lb, u->var->ub);
498 : 14905000 : jl_value_t *t = NULL;
499 : 14905000 : JL_GC_PUSH2(&v, &t);
500 : 14905000 : t = jl_instantiate_unionall(u, (jl_value_t*)v);
501 : 14905000 : t = jl_new_struct(jl_unionall_type, v, t);
502 : 14905000 : JL_GC_POP();
503 : 14905000 : 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 : 122661000 : 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 [ + + ]: 122661000 : jl_unionstate_t *state = R ? &e->Runions : &e->Lunions;
513 : : do {
514 [ + + ]: 302082000 : if (state->depth >= state->used) {
515 : 78746600 : statestack_set(state, state->used, 0);
516 : 78746600 : state->used++;
517 : : }
518 : 302082000 : int ui = statestack_get(state, state->depth);
519 : 302082000 : state->depth++;
520 [ + + ]: 302082000 : if (ui == 0) {
521 : 92345800 : state->more = state->depth; // memorize that this was the deepest available choice
522 : 92345800 : u = ((jl_uniontype_t*)u)->a;
523 : : }
524 : : else {
525 : 209736000 : u = ((jl_uniontype_t*)u)->b;
526 : : }
527 [ + + ]: 302082000 : } while (jl_is_uniontype(u));
528 : 122661000 : 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 : 29004700 : static int subtype_ccheck(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
535 : : {
536 [ + + ]: 29004700 : if (x == y)
537 : 10675400 : return 1;
538 [ + + + + ]: 18329300 : if (x == jl_bottom_type && jl_is_type(y))
539 : 902219 : return 1;
540 [ + + + + ]: 17427100 : if (y == (jl_value_t*)jl_any_type && jl_is_type(x))
541 : 3204400 : return 1;
542 [ + + + + ]: 14222700 : if (jl_is_uniontype(x) && jl_egal(x, y))
543 : 73528 : return 1;
544 [ + + + + ]: 14149200 : if (x == (jl_value_t*)jl_any_type && jl_is_datatype(y))
545 : 101205 : return 0;
546 : 14048000 : jl_saved_unionstate_t oldLunions; push_unionstate(&oldLunions, &e->Lunions);
547 : 14048000 : jl_saved_unionstate_t oldRunions; push_unionstate(&oldRunions, &e->Runions);
548 : : int sub;
549 : 14048000 : e->Lunions.used = e->Runions.used = 0;
550 : 14048000 : e->Runions.depth = 0;
551 : 14048000 : e->Runions.more = 0;
552 : 14048000 : e->Lunions.depth = 0;
553 : 14048000 : e->Lunions.more = 0;
554 : :
555 : 14048000 : sub = forall_exists_subtype(x, y, e, 0);
556 : :
557 : 14048000 : pop_unionstate(&e->Runions, &oldRunions);
558 : 14048000 : pop_unionstate(&e->Lunions, &oldLunions);
559 : 14048000 : return sub;
560 : : }
561 : :
562 : 22585100 : static int subtype_left_var(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param)
563 : : {
564 [ + + ]: 22585100 : if (x == y)
565 : 4002640 : return 1;
566 [ + + + + ]: 18582400 : if (x == jl_bottom_type && jl_is_type(y))
567 : 96 : return 1;
568 [ + + + + ]: 18582300 : if (y == (jl_value_t*)jl_any_type && jl_is_type(x))
569 : 1266310 : return 1;
570 [ + + + + ]: 17316000 : if (jl_is_uniontype(x) && jl_egal(x, y))
571 : 720 : return 1;
572 [ + + + + ]: 17315300 : if (x == (jl_value_t*)jl_any_type && jl_is_datatype(y))
573 : 2261800 : return 0;
574 : 15053500 : 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 : 72033700 : static void record_var_occurrence(jl_varbinding_t *vb, jl_stenv_t *e, int param) JL_NOTSAFEPOINT
580 : : {
581 [ + + + + ]: 72033700 : if (vb != NULL && param) {
582 : : // saturate counters at 2; we don't need values bigger than that
583 [ + + + + : 42962600 : if (param == 2 && (vb->right ? e->Rinvdepth : e->invdepth) > vb->depth0) {
+ + ]
584 [ + + ]: 35286400 : if (vb->occurs_inv < 2)
585 : 34830700 : vb->occurs_inv++;
586 : : }
587 [ + + ]: 7676190 : else if (vb->occurs_cov < 2) {
588 : 7629510 : vb->occurs_cov++;
589 : : }
590 : : }
591 : 72033700 : }
592 : :
593 : : // is var x's quantifier outside y's in nesting order
594 : 1594670 : static int var_outside(jl_stenv_t *e, jl_tvar_t *x, jl_tvar_t *y)
595 : : {
596 : 1594670 : jl_varbinding_t *btemp = e->vars;
597 [ + - ]: 2876800 : while (btemp != NULL) {
598 [ + + ]: 2876800 : if (btemp->var == x) return 0;
599 [ + + ]: 2309120 : if (btemp->var == y) return 1;
600 : 1282130 : 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 : 32940000 : static int var_lt(jl_tvar_t *b, jl_value_t *a, jl_stenv_t *e, int param)
609 : : {
610 : 32940000 : jl_varbinding_t *bb = lookup(e, b);
611 [ + + ]: 32940000 : if (bb == NULL)
612 [ + + + + ]: 219203 : return e->ignore_free || subtype_left_var(b->ub, a, e, param);
613 : 32720800 : record_var_occurrence(bb, e, param);
614 [ + + ]: 32720800 : if (!bb->right) // check ∀b . b<:a
615 : 20497400 : return subtype_left_var(bb->ub, a, e, param);
616 [ + + ]: 12223400 : if (bb->ub == a)
617 : 1445920 : return 1;
618 [ + + - + : 10777400 : if (!((bb->lb == jl_bottom_type && !jl_is_type(a) && !jl_is_typevar(a)) || subtype_ccheck(bb->lb, a, e)))
- - + + ]
619 : 1469100 : 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 [ + + ]: 9308350 : if (e->intersection) {
623 : 110879 : jl_value_t *ub = intersect_aside(bb->ub, a, e, 0, bb->depth0);
624 [ + - ]: 110879 : if (ub != (jl_value_t*)b)
625 : 110879 : bb->ub = ub;
626 : : }
627 : : else {
628 : 9197470 : bb->ub = simple_meet(bb->ub, a);
629 : : }
630 [ - + ]: 9308350 : assert(bb->ub != (jl_value_t*)b);
631 [ + + ]: 9308350 : if (jl_is_typevar(a)) {
632 : 4036350 : jl_varbinding_t *aa = lookup(e, (jl_tvar_t*)a);
633 [ + + + - : 4036350 : 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 : 0 : return subtype_left_var(aa->ub, aa->lb, e, param);
637 : : }
638 : : }
639 : 9308350 : 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 : 21824100 : static int var_gt(jl_tvar_t *b, jl_value_t *a, jl_stenv_t *e, int param)
646 : : {
647 : 21824100 : jl_varbinding_t *bb = lookup(e, b);
648 [ + + ]: 21824100 : if (bb == NULL)
649 [ + + + + ]: 278288 : return e->ignore_free || subtype_left_var(a, b->lb, e, param);
650 : 21545800 : record_var_occurrence(bb, e, param);
651 [ + + ]: 21545800 : if (!bb->right) // check ∀b . b>:a
652 : 1616120 : return subtype_left_var(a, bb->lb, e, param);
653 [ + + ]: 19929700 : if (bb->lb == bb->ub) {
654 [ + + + + : 1939530 : if (jl_is_typevar(bb->lb) && !jl_is_type(a) && !jl_is_typevar(a))
+ + ]
655 : 37015 : return var_gt((jl_tvar_t*)bb->lb, a, e, param);
656 [ + + + + : 1902510 : if (jl_is_typevar(a) && !jl_is_type(bb->lb) && !jl_is_typevar(bb->lb))
+ + ]
657 : 451 : return var_lt((jl_tvar_t*)a, bb->lb, e, param);
658 : : }
659 [ + + + + : 19892200 : if (!((bb->ub == (jl_value_t*)jl_any_type && !jl_is_type(a) && !jl_is_typevar(a)) || subtype_ccheck(a, bb->ub, e)))
+ + + + ]
660 : 6787300 : return 0;
661 : 13104900 : jl_value_t *lb = simple_join(bb->lb, a);
662 [ + + + - ]: 13104900 : if (!e->intersection || !subtype_by_bounds(lb, (jl_value_t*)b, e))
663 : 13104900 : bb->lb = lb;
664 : : // this bound should not be directly circular
665 [ - + ]: 13104900 : assert(bb->lb != (jl_value_t*)b);
666 [ + + ]: 13104900 : if (jl_is_typevar(a)) {
667 : 5333810 : jl_varbinding_t *aa = lookup(e, (jl_tvar_t*)a);
668 [ + + + - : 5333810 : if (aa && !aa->right && bb->depth0 != aa->depth0 && param == 2 && var_outside(e, b, (jl_tvar_t*)a))
+ + + + +
+ ]
669 : 111882 : return subtype_left_var(aa->ub, aa->lb, e, param);
670 : : }
671 : 12993000 : 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 : 4531030 : static int is_leaf_bound(jl_value_t *v) JL_NOTSAFEPOINT
678 : : {
679 [ + + ]: 4531030 : if (v == jl_bottom_type)
680 : 3148670 : return 1;
681 [ + + ]: 1382350 : if (jl_is_datatype(v)) {
682 [ + + ]: 831861 : if (((jl_datatype_t*)v)->name->abstract) {
683 [ + + ]: 622450 : if (jl_is_type_type(v))
684 : 99 : return 1;//!jl_has_free_typevars(jl_tparam0(v));
685 : 622351 : return 0;
686 : : }
687 : 209411 : return ((jl_datatype_t*)v)->isconcretetype;
688 : : }
689 [ + + + + ]: 550493 : return !jl_is_type(v) && !jl_is_typevar(v);
690 : : }
691 : :
692 : 1651930 : static int is_leaf_typevar(jl_tvar_t *v) JL_NOTSAFEPOINT
693 : : {
694 : 1651930 : return is_leaf_bound(v->lb);
695 : : }
696 : :
697 : 35447700 : static jl_value_t *widen_Type(jl_value_t *t JL_PROPAGATES_ROOT) JL_NOTSAFEPOINT
698 : : {
699 [ + + + + ]: 35447700 : if (jl_is_type_type(t) && !jl_is_typevar(jl_tparam0(t)))
700 : 1438 : return jl_typeof(jl_tparam0(t));
701 [ + + ]: 35446300 : if (jl_is_uniontype(t)) {
702 : 63283 : jl_value_t *a = widen_Type(((jl_uniontype_t*)t)->a);
703 : 63283 : jl_value_t *b = widen_Type(((jl_uniontype_t*)t)->b);
704 [ + + ]: 63283 : if (a == b)
705 : 48 : return a;
706 : : }
707 : 35446200 : 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 : 2541380 : static jl_value_t *fix_inferred_var_bound(jl_tvar_t *var, jl_value_t *ty JL_MAYBE_UNROOTED)
718 : : {
719 [ + + + + ]: 2541380 : if (!jl_is_typevar(ty) && jl_has_free_typevars(ty)) {
720 : 113358 : jl_value_t *ans = ty;
721 : 113358 : jl_array_t *vs = NULL;
722 : 113358 : JL_GC_PUSH2(&ans, &vs);
723 : 113358 : vs = jl_find_free_typevars(ty);
724 : : int i;
725 [ + + ]: 238172 : for (i = 0; i < jl_array_len(vs); i++) {
726 : 124814 : ans = jl_type_unionall((jl_tvar_t*)jl_array_ptr_ref(vs, i), ans);
727 : : }
728 : 113358 : ans = (jl_value_t*)jl_new_typevar(var->name, jl_bottom_type, ans);
729 : 113358 : JL_GC_POP();
730 : 113358 : return ans;
731 : : }
732 : 2428020 : 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 : 1929170 : static int var_occurs_invariant(jl_value_t *v, jl_tvar_t *var, int inv) JL_NOTSAFEPOINT
740 : : {
741 : 1929170 : return var_occurs_inside(v, var, 0, 1);
742 : : }
743 : :
744 : 117286000 : static jl_unionall_t *unalias_unionall(jl_unionall_t *u, jl_stenv_t *e)
745 : : {
746 : 117286000 : 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 : 117286000 : JL_GC_PUSH1(&u);
750 [ + + ]: 181318000 : while (btemp != NULL) {
751 [ + + ]: 78665600 : if (btemp->var == u->var ||
752 : : // outer var can only refer to inner var if bounds changed
753 [ + + + + ]: 64035600 : (btemp->lb != btemp->var->lb && jl_has_typevar(btemp->lb, u->var)) ||
754 [ + + - + ]: 64032200 : (btemp->ub != btemp->var->ub && jl_has_typevar(btemp->ub, u->var))) {
755 : 14633400 : u = rename_unionall(u);
756 : 14633400 : break;
757 : : }
758 : 64032200 : btemp = btemp->prev;
759 : : }
760 : 117286000 : JL_GC_POP();
761 : 117286000 : return u;
762 : : }
763 : :
764 : 117286000 : static int subtype_unionall(jl_value_t *t, jl_unionall_t *u, jl_stenv_t *e, int8_t R, int param)
765 : : {
766 : 117286000 : u = unalias_unionall(u, e);
767 [ + + ]: 117286000 : jl_varbinding_t vb = { u->var, u->var->lb, u->var->ub, R, 0, 0, 0, 0, 0, 0,
768 : 117286000 : R ? e->Rinvdepth : e->invdepth, 0, NULL, e->vars };
769 : 117286000 : JL_GC_PUSH4(&u, &vb.lb, &vb.ub, &vb.innervars);
770 : 117286000 : e->vars = &vb;
771 : : int ans;
772 [ + + ]: 117286000 : if (R) {
773 : 50194800 : e->envidx++;
774 : 50194800 : ans = subtype(t, u->body, e, param);
775 : 50194800 : e->envidx--;
776 : : // widen Type{x} to typeof(x) in argument position
777 [ + + ]: 50194800 : if (!vb.occurs_inv)
778 : 35321200 : vb.lb = widen_Type(vb.lb);
779 : : // fill variable values into `envout` up to `envsz`
780 [ + + ]: 50194800 : if (e->envidx < e->envsz) {
781 : : jl_value_t *val;
782 [ + + + - ]: 2316040 : if (vb.intvalued && vb.lb == (jl_value_t*)jl_any_type)
783 : 436 : val = (jl_value_t*)jl_wrap_vararg(NULL, NULL);
784 [ + + + + ]: 2315600 : else if (!vb.occurs_inv && vb.lb != jl_bottom_type)
785 [ + + ]: 49917 : val = is_leaf_bound(vb.lb) ? vb.lb : (jl_value_t*)jl_new_typevar(u->var->name, jl_bottom_type, vb.lb);
786 [ + + ]: 2265680 : else if (vb.lb == vb.ub)
787 : 895340 : val = vb.lb;
788 [ + + ]: 1370340 : else if (vb.lb != jl_bottom_type)
789 : : // TODO: for now return the least solution, which is what
790 : : // method parameters expect.
791 : 153746 : val = vb.lb;
792 [ + - + + ]: 1216600 : else if (vb.lb == u->var->lb && vb.ub == u->var->ub)
793 : 1216600 : val = (jl_value_t*)u->var;
794 : : else
795 : 2 : val = (jl_value_t*)jl_new_typevar(u->var->name, vb.lb, vb.ub);
796 : 2316040 : 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 [ + + + + ]: 2316040 : if (oldval && !jl_egal(oldval, val))
800 : 2912 : e->envout[e->envidx] = (jl_value_t*)u->var;
801 : : else
802 : 2313120 : 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 [ - + ]: 134182000 : ans = R ? subtype(t, u->body, e, param) :
808 : 67090900 : 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 [ + + + + ]: 117286000 : int diagonal = vb.occurs_cov > 1 && !var_occurs_invariant(u->body, u->var, 0);
817 [ + + + + : 117286000 : if (ans && (vb.concrete || (diagonal && is_leaf_typevar(u->var)))) {
+ + + - ]
818 [ + + - + : 1607880 : 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 : 0 : ans = 0;
822 : : }
823 [ + + ]: 1607880 : else if (jl_is_typevar(vb.lb)) {
824 : 21558 : jl_tvar_t *v = (jl_tvar_t*)vb.lb;
825 : 21558 : jl_varbinding_t *vlb = lookup(e, v);
826 [ + - ]: 21558 : if (vlb)
827 : 21558 : vlb->concrete = 1;
828 : : }
829 [ + + ]: 1586320 : else if (!is_leaf_bound(vb.lb)) {
830 : 109781 : ans = 0;
831 : : }
832 : : }
833 : :
834 : 117286000 : e->vars = vb.prev;
835 : :
836 [ + + ]: 117286000 : if (!ans) {
837 : 98549200 : JL_GC_POP();
838 : 98549200 : return 0;
839 : : }
840 : :
841 : 18736400 : jl_varbinding_t *btemp = e->vars;
842 [ + + ]: 18736400 : if (vb.lb != vb.ub) {
843 [ + + ]: 17939800 : while (btemp != NULL) {
844 : 6790140 : jl_value_t *vu = btemp->ub;
845 : 6790140 : jl_value_t *vl = btemp->lb;
846 : : // TODO: this takes a significant amount of time
847 [ + + ]: 6790140 : if (btemp->depth0 != vb.depth0 &&
848 [ + - + + : 2155160 : ((vu != (jl_value_t*)vb.var && btemp->var->ub != vu && var_occurs_inside(vu, vb.var, 0, 1)) ||
+ + ]
849 [ + - + + : 2155140 : (vl != (jl_value_t*)vb.var && btemp->var->lb != vl && var_occurs_inside(vl, vb.var, 0, 1)))) {
- + ]
850 : 20 : ans = 0; break;
851 : : }
852 : 6790120 : btemp = btemp->prev;
853 : : }
854 : : }
855 : :
856 : 18736400 : JL_GC_POP();
857 : 18736400 : return ans;
858 : : }
859 : :
860 : : // check n <: (length of vararg type v)
861 : 9455430 : static int check_vararg_length(jl_value_t *v, ssize_t n, jl_stenv_t *e)
862 : : {
863 : 9455430 : 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 [ + + ]: 9455430 : if (N) {
866 : 630054 : jl_value_t *nn = jl_box_long(n);
867 : 630054 : JL_GC_PUSH1(&nn);
868 : 630054 : e->invdepth++;
869 : 630054 : e->Rinvdepth++;
870 [ + + + - ]: 630054 : int ans = subtype(nn, N, e, 2) && subtype(N, nn, e, 0);
871 : 630054 : e->invdepth--;
872 : 630054 : e->Rinvdepth--;
873 : 630054 : JL_GC_POP();
874 [ + + ]: 630054 : if (!ans)
875 : 36299 : return 0;
876 : : }
877 : 9419130 : 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 : 508314 : 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 : 508314 : jl_value_t *xp0 = jl_unwrap_vararg(vtx); jl_value_t *xp1 = jl_unwrap_vararg_num(vtx);
899 : 508314 : jl_value_t *yp0 = jl_unwrap_vararg(vty); jl_value_t *yp1 = jl_unwrap_vararg_num(vty);
900 : :
901 [ + + ]: 508314 : if (!xp1) {
902 : 446907 : jl_value_t *yl = yp1;
903 [ + + ]: 446907 : if (yl) {
904 : : // Unconstrained on the left, constrained on the right
905 [ + - ]: 38671 : if (jl_is_typevar(yl)) {
906 : 38671 : jl_varbinding_t *ylv = lookup(e, (jl_tvar_t*)yl);
907 [ + - ]: 38671 : if (ylv)
908 : 38671 : yl = ylv->lb;
909 : : }
910 [ + + ]: 38671 : if (jl_is_long(yl)) {
911 : 1141 : return 0;
912 : : }
913 : : }
914 : : }
915 : : else {
916 : 61407 : jl_value_t *xl = jl_unwrap_vararg_num(vtx);
917 [ + - ]: 61407 : if (jl_is_typevar(xl)) {
918 : 61407 : jl_varbinding_t *xlv = lookup(e, (jl_tvar_t*)xl);
919 [ + + ]: 61407 : if (xlv)
920 : 61204 : xl = xlv->lb;
921 : : }
922 [ + + ]: 61407 : if (jl_is_long(xl)) {
923 [ + - ]: 1267 : 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 : 1267 : jl_value_t *yl = jl_unwrap_vararg_num(vty);
928 [ + + ]: 1267 : if (yl) {
929 [ + - ]: 784 : if (jl_is_typevar(yl)) {
930 : 784 : jl_varbinding_t *ylv = lookup(e, (jl_tvar_t*)yl);
931 [ + - ]: 784 : if (ylv)
932 : 784 : yl = ylv->lb;
933 : : }
934 [ + - ]: 784 : if (jl_is_long(yl)) {
935 : 784 : 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 : 483 : 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 [ + + ]: 505906 : if (!subtype(xp0, yp0, e, param)) return 0;
951 [ + + ]: 386477 : if (!subtype(xp0, yp0, e, 1)) return 0;
952 : :
953 : 341011 : constrain_length:
954 [ + + ]: 341494 : if (!yp1) {
955 : 300713 : return 1;
956 : : }
957 [ + + ]: 40781 : if (!xp1) {
958 : 28325 : jl_value_t *yl = yp1;
959 : 28325 : jl_varbinding_t *ylv = NULL;
960 [ + - ]: 28325 : if (jl_is_typevar(yl)) {
961 : 28325 : ylv = lookup(e, (jl_tvar_t*)yl);
962 [ + - ]: 28325 : if (ylv)
963 : 28325 : yl = ylv->lb;
964 : : }
965 [ - + ]: 28325 : 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 [ + - ]: 28325 : if (ylv) {
973 [ + + + + ]: 28325 : if (ylv->depth0 != e->invdepth || ylv->occurs_inv)
974 : 3796 : return 0;
975 : 24529 : ylv->intvalued = 1;
976 : : }
977 : : // set lb to Any. Since `intvalued` is set, we'll interpret that
978 : : // appropriately.
979 : 24529 : e->invdepth++;
980 : 24529 : e->Rinvdepth++;
981 : 24529 : int ans = subtype((jl_value_t*)jl_any_type, yp1, e, 2);
982 : 24529 : e->invdepth--;
983 : 24529 : e->Rinvdepth--;
984 : 24529 : return ans;
985 : : }
986 : :
987 : : // Vararg{T,N} <: Vararg{T2,N2}; equate N and N2
988 : 12456 : e->invdepth++;
989 : 12456 : e->Rinvdepth++;
990 : 12456 : JL_GC_PUSH2(&xp1, &yp1);
991 [ + - - + : 12456 : if (xp1 && jl_is_long(xp1) && vx != 1)
- - ]
992 : 0 : xp1 = jl_box_long(jl_unbox_long(xp1) - vx + 1);
993 [ - + - - ]: 12456 : if (jl_is_long(yp1) && vy != 1)
994 : 0 : yp1 = jl_box_long(jl_unbox_long(yp1) - vy + 1);
995 : 12456 : int ans = forall_exists_equal(xp1, yp1, e);
996 : 12456 : JL_GC_POP();
997 : 12456 : e->invdepth--;
998 : 12456 : e->Rinvdepth--;
999 : 12456 : return ans;
1000 : : }
1001 : :
1002 : 59833600 : static int subtype_tuple_tail(jl_datatype_t *xd, jl_datatype_t *yd, int8_t R, jl_stenv_t *e, int param)
1003 : : {
1004 : 59833600 : size_t lx = jl_nparams(xd);
1005 : 59833600 : size_t ly = jl_nparams(yd);
1006 : 59833600 : size_t i = 0, j = 0, vx = 0, vy = 0, x_reps = 1;
1007 : 59833600 : jl_value_t *lastx = NULL, *lasty = NULL;
1008 : 59833600 : jl_value_t *xi = NULL, *yi = NULL;
1009 : :
1010 : 85270200 : for (;;) {
1011 [ + + ]: 145104000 : if (i < lx) {
1012 : 138052000 : xi = jl_tparam(xd, i);
1013 [ + + + + : 138052000 : if (i == lx-1 && (vx || jl_is_vararg(xi))) {
+ + ]
1014 : 427260 : vx += 1;
1015 : : }
1016 : : }
1017 : :
1018 [ + + ]: 145104000 : if (j < ly) {
1019 : 140375000 : yi = jl_tparam(yd, j);
1020 [ + + + + : 140375000 : if (j == ly-1 && (vy || jl_is_vararg(yi))) {
+ + ]
1021 : 16222600 : vy += 1;
1022 : : }
1023 : : }
1024 : :
1025 [ + + ]: 145104000 : if (i >= lx)
1026 : 7051950 : break;
1027 : :
1028 [ + + + + ]: 138052000 : int all_varargs = vx && vy;
1029 [ + + + + ]: 138052000 : if (!all_varargs && vy == 1) {
1030 [ + + ]: 8434110 : 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 : 7248240 : xi = jl_tparam(xd, lx-1);
1034 [ + + ]: 7248240 : if (jl_is_vararg(xi)) {
1035 : 131874 : all_varargs = 1;
1036 : 131874 : vy += lx - i;
1037 : 131874 : vx = 1;
1038 : : } else {
1039 : 7116360 : break;
1040 : : }
1041 : : }
1042 : : }
1043 : :
1044 [ + + ]: 130935000 : if (all_varargs) {
1045 : : // Tuple{..., Vararg{xi, _}} <: Tuple{..., Vararg{yi, _}}
1046 : 508314 : return subtype_tuple_varargs(
1047 : : (jl_vararg_t*)xi,
1048 : : (jl_vararg_t*)yi,
1049 : : vx, vy, e, param);
1050 : : }
1051 : :
1052 [ + + ]: 130427000 : if (j >= ly)
1053 : 16257 : return !!vx;
1054 : :
1055 [ + + ]: 130411000 : xi = vx ? jl_unwrap_vararg(xi) : xi;
1056 [ + + + + ]: 130411000 : int x_same = lastx && jl_egal(xi, lastx);
1057 [ + + ]: 130411000 : if (vy) {
1058 : 6258820 : yi = jl_unwrap_vararg(yi);
1059 : : // keep track of number of consecutive identical types compared to Vararg
1060 [ + + ]: 6258820 : if (x_same)
1061 : 5032410 : x_reps++;
1062 : : else
1063 : 1226410 : x_reps = 1;
1064 : : }
1065 [ + + ]: 130411000 : 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 [ + + + + : 125922000 : else if (x_same && e->Runions.depth == 0 &&
+ + ]
1070 [ + + + + : 2492720 : ((yi == lasty && !jl_has_free_typevars(xi) && !jl_has_free_typevars(yi)) ||
+ + ]
1071 [ + - + + : 23639 : (yi == lastx && !vx && vy && jl_is_concrete_type(xi)))) {
+ - ]
1072 : : // fast path for repeated elements
1073 : : }
1074 [ + + + + : 125096000 : 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 [ + + ]: 101372000 : if (!jl_subtype(xi, yi))
1077 : 27777600 : return 0;
1078 : : }
1079 [ + + ]: 23724800 : else if (!subtype(xi, yi, e, param)) {
1080 : 17363200 : return 0;
1081 : : }
1082 : 85270200 : lastx = xi; lasty = yi;
1083 [ + + + + ]: 85270200 : if (i < lx-1 || !vx)
1084 : 85235600 : i++;
1085 [ + + + + ]: 85270200 : if (j < ly-1 || !vy)
1086 : 79441400 : j++;
1087 : : }
1088 : :
1089 [ + + + - : 14168300 : if (vy && !vx && lx+1 >= ly) {
+ - ]
1090 : : // in Tuple{...,tn} <: Tuple{...,Vararg{T,N}}, check (lx+1-ly) <: N
1091 [ + + ]: 9455430 : if (!check_vararg_length(yi, lx+1-ly, e))
1092 : 36299 : return 0;
1093 : : }
1094 [ + + + - : 14132000 : assert((lx + vx == ly + vy) || (vy && (lx >= (vx ? ly : (ly-1)))));
+ - + - ]
1095 : 14132000 : return 1;
1096 : : }
1097 : :
1098 : 61823300 : 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 : 61823300 : size_t lx = jl_nparams(xd);
1102 : 61823300 : size_t ly = jl_nparams(yd);
1103 : :
1104 [ + + - + ]: 61823300 : if (lx == 0 && ly == 0)
1105 : 0 : return 1;
1106 : :
1107 : 61823300 : jl_vararg_kind_t vvx = JL_VARARG_NONE;
1108 : 61823300 : jl_vararg_kind_t vvy = JL_VARARG_NONE;
1109 : 61823300 : jl_varbinding_t *xbb = NULL;
1110 : 61823300 : jl_value_t *xva = NULL, *yva = NULL;
1111 [ + + ]: 61823300 : if (lx > 0) {
1112 : 60260100 : xva = jl_tparam(xd, lx-1);
1113 : 60260100 : vvx = jl_vararg_kind(xva);
1114 [ + + ]: 60260100 : if (vvx == JL_VARARG_BOUND)
1115 : 354029 : xbb = lookup(e, (jl_tvar_t *)jl_unwrap_vararg_num(xva));
1116 : : }
1117 [ + + ]: 61823300 : if (ly > 0) {
1118 : 61746600 : yva = jl_tparam(yd, ly-1);
1119 : 61746600 : vvy = jl_vararg_kind(yva);
1120 : : }
1121 [ + + + - : 61823300 : if (vvx != JL_VARARG_NONE && vvx != JL_VARARG_INT &&
+ + ]
1122 [ + + ]: 353826 : (!xbb || !jl_is_long(xbb->lb))) {
1123 [ + + + + : 2556400 : if (vvx == JL_VARARG_UNBOUND || (xbb && !xbb->right)) {
+ + ]
1124 : : // Unbounded on the LHS, bounded on the RHS
1125 [ + + - + ]: 2555600 : if (vvy == JL_VARARG_NONE || vvy == JL_VARARG_INT)
1126 : 1407210 : return 0;
1127 [ + + ]: 1148390 : else if (lx < ly) // Unbounded includes N == 0
1128 : 339913 : return 0;
1129 : : }
1130 [ - + - - ]: 799 : else if (vvy == JL_VARARG_NONE && !check_vararg_length(xva, ly+1-lx, e)) {
1131 : 0 : return 0;
1132 : : }
1133 : : }
1134 : : else {
1135 : 59266800 : size_t nx = lx;
1136 [ - + ]: 59266800 : if (vvx == JL_VARARG_INT)
1137 : 0 : nx += jl_vararg_length(xva) - 1;
1138 [ + + + - ]: 59266800 : else if (xbb && jl_is_long(xbb->lb))
1139 : 17524 : nx += jl_unbox_long(xbb->lb) - 1;
1140 : : else
1141 [ - + ]: 59249300 : assert(vvx == JL_VARARG_NONE);
1142 : 59266800 : size_t ny = ly;
1143 [ - + ]: 59266800 : if (vvy == JL_VARARG_INT)
1144 : 0 : ny += jl_vararg_length(yva) - 1;
1145 [ + + ]: 59266800 : else if (vvy != JL_VARARG_NONE)
1146 : 11690100 : ny -= 1;
1147 [ + + - + ]: 59266800 : if (vvy == JL_VARARG_NONE || vvy == JL_VARARG_INT) {
1148 [ + + ]: 47576700 : if (nx != ny)
1149 : 107315 : return 0;
1150 : : }
1151 : : else {
1152 [ + + ]: 11690100 : if (ny > nx)
1153 : 135201 : return 0;
1154 : : }
1155 : : }
1156 : :
1157 [ + + ]: 59833600 : param = (param == 0 ? 1 : param);
1158 : 59833600 : int ans = subtype_tuple_tail(xd, yd, 0, e, param);
1159 : 59833600 : 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 : 521422000 : static int subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param)
1167 : : {
1168 [ + + ]: 521422000 : if (jl_is_uniontype(x)) {
1169 [ + + ]: 46573700 : if (x == y) return 1;
1170 : 46566600 : x = pick_union_element(x, e, 0);
1171 : : }
1172 [ + + ]: 521415000 : if (jl_is_uniontype(y)) {
1173 [ + + + + ]: 102314000 : if (x == ((jl_uniontype_t*)y)->a || x == ((jl_uniontype_t*)y)->b)
1174 : 7530840 : return 1;
1175 [ + + ]: 94783300 : if (jl_is_unionall(x))
1176 : 18231400 : return subtype_unionall(y, (jl_unionall_t*)x, e, 0, param);
1177 : 76551900 : int ui = 1;
1178 [ + + ]: 76551900 : 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 : 2573260 : jl_unionstate_t *state = &e->Runions;
1184 [ + + ]: 2573260 : if (state->depth >= state->used) {
1185 : 731431 : statestack_set(state, state->used, 0);
1186 : 731431 : state->used++;
1187 : : }
1188 : 2573260 : ui = statestack_get(state, state->depth);
1189 : 2573260 : state->depth++;
1190 [ + + ]: 2573260 : if (ui == 0)
1191 : 1612180 : state->more = state->depth; // memorize that this was the deepest available choice
1192 : : }
1193 [ + + ]: 76551900 : if (ui == 1)
1194 : 74939700 : y = pick_union_element(y, e, 1);
1195 : : }
1196 [ + + ]: 495653000 : if (jl_is_typevar(x)) {
1197 [ + + ]: 41640200 : if (jl_is_typevar(y)) {
1198 [ + + ]: 13815800 : if (x == y) return 1;
1199 : 13644200 : jl_varbinding_t *xx = lookup(e, (jl_tvar_t*)x);
1200 : 13644200 : jl_varbinding_t *yy = lookup(e, (jl_tvar_t*)y);
1201 [ + + ]: 13644200 : jl_value_t *xub = xx ? xx->ub : ((jl_tvar_t*)x)->ub;
1202 [ + + ]: 13644200 : jl_value_t *ylb = yy ? yy->lb : ((jl_tvar_t*)y)->lb;
1203 [ + + ]: 13644200 : if (e->intersection) {
1204 [ + + ]: 78815 : jl_value_t *xlb = xx ? xx->lb : ((jl_tvar_t*)x)->lb;
1205 [ + + ]: 78815 : jl_value_t *yub = yy ? yy->ub : ((jl_tvar_t*)y)->ub;
1206 : : // find equivalence class for typevars during intersection
1207 [ + + + + ]: 78815 : if (xub == xlb && jl_is_typevar(xub))
1208 : 25320 : return subtype(xub, y, e, param);
1209 [ + + + + ]: 53495 : if (yub == ylb && jl_is_typevar(yub))
1210 : 25376 : return subtype(x, yub, e, param);
1211 : : }
1212 [ + + + + ]: 13593600 : int xr = xx && xx->right; // treat free variables as "forall" (left)
1213 [ + + + + ]: 13593600 : int yr = yy && yy->right;
1214 [ + + ]: 13593600 : if (xr) {
1215 [ + + ]: 5115830 : if (yy) record_var_occurrence(yy, e, param);
1216 [ + + ]: 5115830 : if (yr) {
1217 : 698 : record_var_occurrence(xx, e, param);
1218 : 698 : return subtype(xx->lb, yy->ub, e, 0);
1219 : : }
1220 : 5115130 : return var_lt((jl_tvar_t*)x, y, e, param);
1221 : : }
1222 [ + + ]: 8477720 : else if (yr) {
1223 [ + + ]: 8195220 : if (xx) record_var_occurrence(xx, e, param);
1224 : 8195220 : 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 [ + + - + ]: 282505 : return subtype(xub, y, e, param) || subtype(x, ylb, e, param);
1230 : : }
1231 : 27824400 : return var_lt((jl_tvar_t*)x, y, e, param);
1232 : : }
1233 [ + + ]: 454013000 : if (jl_is_typevar(y))
1234 : 13591900 : return var_gt((jl_tvar_t*)y, x, e, param);
1235 [ + + + + ]: 440421000 : if (y == (jl_value_t*)jl_any_type && !jl_has_free_typevars(x))
1236 : 1292210 : return 1;
1237 [ + + + + ]: 439129000 : if (x == jl_bottom_type && !jl_has_free_typevars(y))
1238 : 432597 : return 1;
1239 : 438696000 : jl_value_t *ux = jl_unwrap_unionall(x);
1240 : 438696000 : jl_value_t *uy = jl_unwrap_unionall(y);
1241 [ + + + + : 575832000 : if ((x != ux || y != uy) && y != (jl_value_t*)jl_any_type && jl_is_datatype(ux) && jl_is_datatype(uy) &&
+ + + + +
+ + + ]
1242 : 137135000 : !jl_is_type_type(ux)) {
1243 [ - + ]: 121732000 : assert(ux);
1244 [ - + ]: 121732000 : if (uy == (jl_value_t*)jl_any_type)
1245 : 0 : return 1;
1246 : 121732000 : jl_datatype_t *xd = (jl_datatype_t*)ux, *yd = (jl_datatype_t*)uy;
1247 [ + - + + : 231449000 : while (xd != NULL && xd != jl_any_type && xd->name != yd->name) {
+ + ]
1248 : 109717000 : xd = xd->super;
1249 : : }
1250 [ + + ]: 121732000 : if (xd == jl_any_type)
1251 : 43544700 : return 0;
1252 : : }
1253 : : // handle forall ("left") vars first
1254 [ + + ]: 395152000 : if (jl_is_unionall(x)) {
1255 [ + + + + ]: 48864500 : if (x == y && !(e->envidx < e->envsz))
1256 : 4939 : return 1;
1257 : 48859500 : return subtype_unionall(y, (jl_unionall_t*)x, e, 0, param);
1258 : : }
1259 [ + + ]: 346287000 : if (jl_is_unionall(y))
1260 : 50194800 : return subtype_unionall(x, (jl_unionall_t*)y, e, 1, param);
1261 [ + + + + ]: 296092000 : if (jl_is_datatype(x) && jl_is_datatype(y)) {
1262 [ + + ]: 276736000 : if (x == y) return 1;
1263 [ + + ]: 273718000 : if (y == (jl_value_t*)jl_any_type) return 1;
1264 : 273508000 : jl_datatype_t *xd = (jl_datatype_t*)x, *yd = (jl_datatype_t*)y;
1265 [ + + + + ]: 273508000 : if (jl_is_type_type(x) && !jl_is_type_type(y)) {
1266 : 973803 : jl_value_t *tp0 = jl_tparam0(xd);
1267 [ + + ]: 973803 : 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 : 370893 : return jl_typeof(tp0) == (jl_value_t*)yd;
1274 : : }
1275 : 602910 : return 0;
1276 : : }
1277 [ + + + + : 272534000 : if (jl_is_type_type(y) && !jl_is_type_type(x) && x != (jl_value_t*)jl_typeofbottom_type) {
+ + ]
1278 : 2695620 : jl_value_t *tp0 = jl_tparam0(yd);
1279 [ + + + + ]: 2695620 : if (!jl_is_typevar(tp0) || !jl_is_kind(x))
1280 : 2490860 : 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 : 204765 : int saved = e->invdepth;
1286 : 204765 : e->invdepth = e->Rinvdepth;
1287 : 204765 : int issub = subtype((jl_value_t*)jl_type_type, y, e, param);
1288 : 204765 : e->invdepth = saved;
1289 : 204765 : return issub;
1290 : : }
1291 [ + + + + ]: 584326000 : while (xd != jl_any_type && xd->name != yd->name) {
1292 [ - + ]: 314488000 : if (xd->super == NULL)
1293 : 0 : jl_errorf("circular type parameter constraint in definition of %s", jl_symbol_name(xd->name->name));
1294 : 314488000 : xd = xd->super;
1295 : : }
1296 [ + + ]: 269838000 : if (xd == jl_any_type) return 0;
1297 [ + + ]: 133355000 : if (xd->name == jl_tuple_typename)
1298 : 61823300 : return subtype_tuple(xd, yd, e, param);
1299 : 71531400 : size_t i, np = jl_nparams(xd);
1300 : 71531400 : int ans = 1;
1301 : 71531400 : e->invdepth++;
1302 : 71531400 : e->Rinvdepth++;
1303 [ + + ]: 82333300 : for (i=0; i < np; i++) {
1304 : 44537300 : jl_value_t *xi = jl_tparam(xd, i), *yi = jl_tparam(yd, i);
1305 [ + + + + ]: 44537300 : if (!(xi == yi || forall_exists_equal(xi, yi, e))) {
1306 : 33735400 : ans = 0; break;
1307 : : }
1308 : : }
1309 : 71531400 : e->invdepth--;
1310 : 71531400 : e->Rinvdepth--;
1311 : 71531400 : return ans;
1312 : : }
1313 [ + + ]: 19356900 : if (jl_is_type(y))
1314 : 4056220 : return x == jl_bottom_type;
1315 : 15300600 : return jl_egal(x, y);
1316 : : }
1317 : :
1318 : 44633900 : static int is_indefinite_length_tuple_type(jl_value_t *x)
1319 : : {
1320 : 44633900 : x = jl_unwrap_unionall(x);
1321 [ + + ]: 44633900 : if (!jl_is_tuple_type(x))
1322 : 43980800 : return 0;
1323 : 653082 : size_t n = jl_nparams(x);
1324 [ + + + + ]: 653082 : return n > 0 && jl_vararg_kind(jl_tparam(x, n-1)) == JL_VARARG_UNBOUND;
1325 : : }
1326 : :
1327 : 43657700 : static int is_definite_length_tuple_type(jl_value_t *x)
1328 : : {
1329 [ + + ]: 43657700 : if (jl_is_typevar(x))
1330 : 14196700 : x = ((jl_tvar_t*)x)->ub;
1331 : 43657700 : x = jl_unwrap_unionall(x);
1332 [ + + ]: 43657700 : if (!jl_is_tuple_type(x))
1333 : 41775400 : return 0;
1334 : 1882260 : size_t n = jl_nparams(x);
1335 [ + + ]: 1882260 : if (n == 0)
1336 : 71848 : return 1;
1337 : 1810410 : jl_vararg_kind_t k = jl_vararg_kind(jl_tparam(x, n-1));
1338 [ + + - + ]: 1810410 : return k == JL_VARARG_NONE || k == JL_VARARG_INT;
1339 : : }
1340 : :
1341 : 43636400 : static int forall_exists_equal(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
1342 : : {
1343 [ + + ]: 43636400 : if (obviously_egal(x, y)) return 1;
1344 : :
1345 [ + + + + : 87247300 : if ((is_indefinite_length_tuple_type(x) && is_definite_length_tuple_type(y)) ||
+ + ]
1346 [ + + ]: 44612800 : (is_definite_length_tuple_type(x) && is_indefinite_length_tuple_type(y)))
1347 : 42108 : return 0;
1348 : :
1349 : 43592100 : jl_saved_unionstate_t oldLunions; push_unionstate(&oldLunions, &e->Lunions);
1350 : 43592100 : e->Lunions.used = 0;
1351 : : int sub;
1352 : :
1353 [ + + + + ]: 43592100 : if (!jl_has_free_typevars(x) || !jl_has_free_typevars(y)) {
1354 : 31284600 : jl_saved_unionstate_t oldRunions; push_unionstate(&oldRunions, &e->Runions);
1355 : 31284600 : e->Runions.used = 0;
1356 : 31284600 : e->Runions.depth = 0;
1357 : 31284600 : e->Runions.more = 0;
1358 : 31284600 : e->Lunions.depth = 0;
1359 : 31284600 : e->Lunions.more = 0;
1360 : :
1361 : 31284600 : sub = forall_exists_subtype(x, y, e, 2);
1362 : :
1363 : 31284600 : pop_unionstate(&e->Runions, &oldRunions);
1364 : : }
1365 : : else {
1366 : 12307400 : int lastset = 0;
1367 : 57804 : while (1) {
1368 : 12365200 : e->Lunions.more = 0;
1369 : 12365200 : e->Lunions.depth = 0;
1370 : 12365200 : sub = subtype(x, y, e, 2);
1371 : 12365200 : int set = e->Lunions.more;
1372 [ + + + + ]: 12365200 : if (!sub || !set)
1373 : : break;
1374 [ - + ]: 57804 : for (int i = set; i <= lastset; i++)
1375 : 0 : statestack_set(&e->Lunions, i, 0);
1376 : 57804 : lastset = set - 1;
1377 : 57804 : statestack_set(&e->Lunions, lastset, 1);
1378 : : }
1379 : : }
1380 : :
1381 : 43592100 : pop_unionstate(&e->Lunions, &oldLunions);
1382 [ + + + + ]: 43592100 : return sub && subtype(y, x, e, 0);
1383 : : }
1384 : :
1385 : 284584000 : 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 : 284584000 : e->Runions.used = 0;
1388 : 284584000 : int lastset = 0;
1389 : 52967100 : while (1) {
1390 : 337551000 : e->Runions.depth = 0;
1391 : 337551000 : e->Runions.more = 0;
1392 : 337551000 : e->Lunions.depth = 0;
1393 : 337551000 : e->Lunions.more = 0;
1394 [ + + ]: 337551000 : if (subtype(x, y, e, param))
1395 : 70014000 : return 1;
1396 : 267537000 : restore_env(e, saved, se);
1397 : 267537000 : int set = e->Runions.more;
1398 [ + + ]: 267537000 : if (!set)
1399 : 214570000 : return 0;
1400 [ + + ]: 54351900 : for (int i = set; i <= lastset; i++)
1401 : 1384790 : statestack_set(&e->Runions, i, 0);
1402 : 52967100 : lastset = set - 1;
1403 : 52967100 : statestack_set(&e->Runions, lastset, 1);
1404 : : }
1405 : : }
1406 : :
1407 : 274675000 : 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 [ - + ]: 274675000 : assert(e->Runions.depth == 0);
1413 [ - + ]: 274675000 : assert(e->Lunions.depth == 0);
1414 : 274675000 : jl_value_t *saved=NULL; jl_savedenv_t se;
1415 : 274675000 : JL_GC_PUSH1(&saved);
1416 : 274675000 : save_env(e, &saved, &se);
1417 : :
1418 : 274675000 : e->Lunions.used = 0;
1419 : 274675000 : int lastset = 0;
1420 : : int sub;
1421 : 9908610 : while (1) {
1422 : 284584000 : sub = exists_subtype(x, y, e, saved, &se, param);
1423 : 284584000 : int set = e->Lunions.more;
1424 [ + + + + ]: 284584000 : if (!sub || !set)
1425 : : break;
1426 : 9908610 : free_env(&se);
1427 : 9908610 : save_env(e, &saved, &se);
1428 [ + + ]: 11346400 : for (int i = set; i <= lastset; i++)
1429 : 1437770 : statestack_set(&e->Lunions, i, 0);
1430 : 9908610 : lastset = set - 1;
1431 : 9908610 : statestack_set(&e->Lunions, lastset, 1);
1432 : : }
1433 : :
1434 : 274675000 : free_env(&se);
1435 : 274675000 : JL_GC_POP();
1436 : 274675000 : return sub;
1437 : : }
1438 : :
1439 : 232971000 : static void init_stenv(jl_stenv_t *e, jl_value_t **env, int envsz)
1440 : : {
1441 : 232971000 : e->vars = NULL;
1442 [ + + - + ]: 232971000 : assert(env != NULL || envsz == 0);
1443 : 232971000 : e->envsz = envsz;
1444 : 232971000 : e->envout = env;
1445 [ + + ]: 232971000 : if (envsz)
1446 : 1615020 : memset(env, 0, envsz*sizeof(void*));
1447 : 232971000 : e->envidx = 0;
1448 : 232971000 : e->invdepth = e->Rinvdepth = 0;
1449 : 232971000 : e->ignore_free = 0;
1450 : 232971000 : e->intersection = 0;
1451 : 232971000 : e->emptiness_only = 0;
1452 : 232971000 : e->triangular = 0;
1453 : 232971000 : e->Lunions.depth = 0; e->Runions.depth = 0;
1454 : 232971000 : e->Lunions.more = 0; e->Runions.more = 0;
1455 : 232971000 : e->Lunions.used = 0; e->Runions.used = 0;
1456 : 232971000 : }
1457 : :
1458 : : // subtyping entry points
1459 : :
1460 : 6307990 : JL_DLLEXPORT int jl_subtype_env_size(jl_value_t *t)
1461 : : {
1462 : 6307990 : int sz = 0;
1463 [ + + ]: 8721750 : while (jl_is_unionall(t)) {
1464 : 2413760 : sz++;
1465 : 2413760 : t = ((jl_unionall_t*)t)->body;
1466 : : }
1467 : 6307990 : 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 : 73362 : static int concrete_min(jl_value_t *t)
1473 : : {
1474 [ + + ]: 73362 : if (jl_is_unionall(t))
1475 : 1300 : t = jl_unwrap_unionall(t);
1476 [ - + ]: 73362 : if (t == (jl_value_t*)jl_bottom_type)
1477 : 0 : return 1;
1478 [ + + ]: 73362 : if (jl_is_datatype(t)) {
1479 [ + + ]: 67550 : if (jl_is_type_type(t))
1480 : 982 : return 0; // Type{T} may have the concrete supertype `typeof(T)`, so don't try to handle them here
1481 [ + + ]: 66568 : return jl_is_concrete_type(t) ? 1 : 2;
1482 : : }
1483 [ - + ]: 5812 : if (jl_is_vararg(t))
1484 : 0 : return 0;
1485 [ + + ]: 5812 : if (jl_is_typevar(t))
1486 : 92 : return 0; // could be 0 or more, since we didn't track if it was unbound
1487 [ + - ]: 5720 : if (jl_is_uniontype(t)) {
1488 : 5720 : int count = concrete_min(((jl_uniontype_t*)t)->a);
1489 [ + + ]: 5720 : if (count > 1)
1490 : 40 : return count;
1491 : 5680 : return count + concrete_min(((jl_uniontype_t*)t)->b);
1492 : : }
1493 [ # # ]: 0 : assert(!jl_is_kind(t));
1494 : 0 : return 1; // a non-Type is also considered concrete
1495 : : }
1496 : :
1497 : 612999 : static jl_value_t *find_var_body(jl_value_t *t, jl_tvar_t *v)
1498 : : {
1499 [ + + ]: 612999 : if (jl_is_unionall(t)) {
1500 [ + + ]: 261389 : if (((jl_unionall_t*)t)->var == v)
1501 : 130961 : return ((jl_unionall_t*)t)->body;
1502 : 130428 : jl_value_t *b = find_var_body(((jl_unionall_t*)t)->var->lb, v);
1503 [ - + ]: 130428 : if (b) return b;
1504 : 130428 : b = find_var_body(((jl_unionall_t*)t)->var->ub, v);
1505 [ - + ]: 130428 : if (b) return b;
1506 : 130428 : return find_var_body(((jl_unionall_t*)t)->body, v);
1507 : : }
1508 [ + + ]: 351610 : else if (jl_is_uniontype(t)) {
1509 : 2 : jl_value_t *b = find_var_body(((jl_uniontype_t*)t)->a, v);
1510 [ - + ]: 2 : if (b) return b;
1511 : 2 : return find_var_body(((jl_uniontype_t*)t)->b, v);
1512 : : }
1513 [ - + ]: 351608 : else if (jl_is_vararg(t)) {
1514 : 0 : jl_vararg_t *vm = (jl_vararg_t *)t;
1515 [ # # ]: 0 : if (vm->T) {
1516 : 0 : jl_value_t *b = find_var_body(vm->T, v);
1517 [ # # ]: 0 : if (b) return b;
1518 [ # # ]: 0 : if (vm->N) {
1519 : 0 : return find_var_body(vm->N, v);
1520 : : }
1521 : : }
1522 : : }
1523 [ + + ]: 351608 : else if (jl_is_datatype(t)) {
1524 : : size_t i;
1525 [ + + ]: 266800 : for (i=0; i < jl_nparams(t); i++) {
1526 : 90562 : jl_value_t *b = find_var_body(jl_tparam(t, i), v);
1527 [ + + ]: 90562 : if (b)
1528 : 43476 : return b;
1529 : : }
1530 : : }
1531 : 308132 : 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 : 810548000 : static int obvious_subtype(jl_value_t *x, jl_value_t *y, jl_value_t *y0, int *subtype)
1540 : : {
1541 [ + + + + ]: 810548000 : if (x == y || y == (jl_value_t*)jl_any_type) {
1542 : 164493000 : *subtype = 1;
1543 : 164493000 : return 1;
1544 : : }
1545 [ + + ]: 677982000 : while (jl_is_unionall(x)) {
1546 [ + + ]: 83876600 : if (!jl_is_unionall(y)) {
1547 [ + + + + ]: 51950100 : if (obvious_subtype(jl_unwrap_unionall(x), y, y0, subtype) && !*subtype)
1548 : 18308300 : return 1;
1549 : 33641800 : return 0;
1550 : : }
1551 : 31926500 : x = ((jl_unionall_t*)x)->body;
1552 : 31926500 : y = ((jl_unionall_t*)y)->body;
1553 : : }
1554 [ + + ]: 594105000 : if (jl_is_unionall(y))
1555 : 71873500 : y = jl_unwrap_unionall(y);
1556 [ + + ]: 594105000 : if (x == (jl_value_t*)jl_typeofbottom_type->super)
1557 : 1290930 : x = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
1558 [ + + ]: 594105000 : if (y == (jl_value_t*)jl_typeofbottom_type->super)
1559 : 576072 : y = (jl_value_t*)jl_typeofbottom_type; // supertype(typeof(Union{})) is equal to, although distinct from, itself
1560 [ + + - + ]: 594105000 : if (x == y || y == (jl_value_t*)jl_any_type) {
1561 : 81018 : *subtype = 1;
1562 : 81018 : return 1;
1563 : : }
1564 [ + + ]: 594024000 : if (jl_is_typevar(x)) {
1565 [ + + ]: 30992400 : if (((jl_tvar_t*)x)->lb != (jl_value_t*)jl_bottom_type)
1566 : 1664060 : return 0;
1567 [ + + + + ]: 29328300 : if (obvious_subtype(((jl_tvar_t*)x)->ub, y, y0, subtype) && *subtype)
1568 : 235625 : return 1;
1569 : 29092700 : return 0;
1570 : : }
1571 [ + + ]: 563032000 : if (jl_is_typevar(y)) {
1572 [ + + ]: 36402600 : if (((jl_tvar_t*)y)->lb != (jl_value_t*)jl_bottom_type)
1573 : 2496620 : return 0;
1574 [ + + + + ]: 33906000 : if (obvious_subtype(x, ((jl_tvar_t*)y)->ub, y0, subtype) && !*subtype)
1575 : 11015800 : return 1;
1576 : 22890200 : return 0;
1577 : : }
1578 [ + + ]: 526629000 : if (x == (jl_value_t*)jl_bottom_type) {
1579 : 27977 : *subtype = 1;
1580 : 27977 : return 1;
1581 : : }
1582 [ + + ]: 526601000 : if (y == (jl_value_t*)jl_bottom_type) {
1583 : 227090 : *subtype = 0;
1584 : 227090 : return 1;
1585 : : }
1586 [ - + ]: 526374000 : 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 [ + + + + ]: 526374000 : if (!jl_is_type(x) || !jl_is_type(y)) {
1594 : 19705600 : *subtype = jl_egal(x, y);
1595 : 19705600 : return 1;
1596 : : }
1597 [ + + ]: 506668000 : if (jl_is_uniontype(x)) {
1598 : : // TODO: consider handling more LHS unions, being wary of covariance
1599 [ + + + + ]: 26403400 : if (obvious_subtype(((jl_uniontype_t*)x)->a, y, y0, subtype) && *subtype) {
1600 [ + + + + ]: 9082800 : if (obvious_subtype(((jl_uniontype_t*)x)->b, y, y0, subtype) && *subtype)
1601 : 2343100 : 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 : 24060200 : return 0;
1614 : : }
1615 [ + + ]: 480265000 : if (jl_is_uniontype(y)) {
1616 [ + + ]: 78095800 : if (obvious_subtype(x, ((jl_uniontype_t*)y)->a, y0, subtype)) {
1617 [ + + ]: 77359700 : if (*subtype)
1618 : 9676830 : return 1;
1619 [ + + ]: 67682900 : if (obvious_subtype(x, ((jl_uniontype_t*)y)->b, y0, subtype))
1620 : 67537900 : return 1;
1621 : : }
1622 [ + + ]: 736117 : else if (obvious_subtype(x, ((jl_uniontype_t*)y)->b, y0, subtype)) {
1623 [ + + ]: 516505 : if (*subtype)
1624 : 6774 : return 1;
1625 : : }
1626 : 874338 : return 0;
1627 : : }
1628 [ + + ]: 402169000 : if (x == (jl_value_t*)jl_any_type) {
1629 : 19064600 : *subtype = 0;
1630 : 19064600 : return 1;
1631 : : }
1632 [ + - ]: 383104000 : if (jl_is_datatype(y)) {
1633 : 383104000 : int istuple = (((jl_datatype_t*)y)->name == jl_tuple_typename);
1634 : 383104000 : 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 [ + - ]: 383104000 : 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 : 383104000 : int uncertain = 0;
1649 [ + + ]: 383104000 : if (((jl_datatype_t*)x)->name != ((jl_datatype_t*)y)->name) {
1650 [ + + + + ]: 265069000 : if (jl_is_type_type(x) && jl_is_kind(y)) {
1651 : 605320 : jl_value_t *t0 = jl_tparam0(x);
1652 [ + + ]: 605320 : if (jl_is_typevar(t0))
1653 : 510057 : return 0;
1654 : 95263 : *subtype = jl_typeof(t0) == y;
1655 : 95263 : return 1;
1656 : : }
1657 [ + + ]: 264464000 : if (jl_is_type_type(y)) {
1658 : 19804600 : jl_value_t *t0 = jl_tparam0(y);
1659 [ - + ]: 19804600 : assert(!jl_is_type_type(x));
1660 [ + + + + ]: 19804600 : if (jl_is_kind(x) && jl_is_typevar(t0))
1661 : 1238780 : return 0;
1662 : 18565800 : *subtype = 0;
1663 : 18565800 : return 1;
1664 : : }
1665 : 244660000 : jl_datatype_t *temp = (jl_datatype_t*)x;
1666 [ + + ]: 511902000 : while (temp->name != ((jl_datatype_t*)y)->name) {
1667 : 467566000 : temp = temp->super;
1668 [ - + ]: 467566000 : if (temp == NULL) // invalid state during type declaration
1669 : 0 : return 0;
1670 [ + + ]: 467566000 : if (temp == jl_any_type) {
1671 : 200323000 : *subtype = 0;
1672 : 200323000 : return 1;
1673 : : }
1674 : : }
1675 [ + + + + ]: 44336100 : if (obvious_subtype((jl_value_t*)temp, y, y0, subtype) && *subtype)
1676 : 42866600 : return 1;
1677 : 1469480 : return 0;
1678 : : }
1679 [ + + + + ]: 118035000 : 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 [ - + - - ]: 13440000 : if (obvious_subtype(((jl_datatype_t*)x)->name->wrapper, y, y0, subtype) && *subtype)
1682 : 0 : return 1;
1683 : : }
1684 : 118035000 : int i, npx = jl_nparams(x), npy = jl_nparams(y);
1685 : 118035000 : jl_vararg_kind_t vx = JL_VARARG_NONE;
1686 : 118035000 : jl_vararg_kind_t vy = JL_VARARG_NONE;
1687 : 118035000 : jl_value_t *vxt = NULL;
1688 : 118035000 : int nparams_expanded_x = npx;
1689 : 118035000 : int nparams_expanded_y = npy;
1690 [ + + ]: 118035000 : if (istuple) {
1691 [ + + ]: 61114500 : if (npx > 0) {
1692 : 59488500 : jl_value_t *xva = jl_tparam(x, npx - 1);
1693 : 59488500 : vx = jl_vararg_kind(xva);
1694 [ + + ]: 59488500 : if (vx != JL_VARARG_NONE) {
1695 : 4861510 : vxt = jl_unwrap_vararg(xva);
1696 : 4861510 : nparams_expanded_x -= 1;
1697 [ - + ]: 4861510 : if (vx == JL_VARARG_INT)
1698 : 0 : nparams_expanded_x += jl_vararg_length(xva);
1699 : : }
1700 : : }
1701 [ + + ]: 61114500 : if (npy > 0) {
1702 : 60995300 : jl_value_t *yva = jl_tparam(y, npy - 1);
1703 : 60995300 : vy = jl_vararg_kind(yva);
1704 [ + + ]: 60995300 : if (vy != JL_VARARG_NONE) {
1705 : 14522400 : nparams_expanded_y -= 1;
1706 [ - + ]: 14522400 : if (vy == JL_VARARG_INT)
1707 : 0 : 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 [ + + + + : 61114500 : 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 [ + + - + ]: 17843400 : if (vy == JL_VARARG_NONE || vy == JL_VARARG_INT) { // the bound on y is certain
1714 [ + + + - : 3320960 : if (vx == JL_VARARG_NONE || vx == JL_VARARG_INT || vx == JL_VARARG_UNBOUND || // and the bound on x is also certain
+ + + + ]
1715 [ + + ]: 333189 : nparams_expanded_x > nparams_expanded_y || npx > nparams_expanded_y) { // or x is unknown, but definitely longer than y
1716 : 3001010 : *subtype = 0;
1717 : 3001010 : return 1; // number of fixed parameters in x are more than declared in y
1718 : : }
1719 : : }
1720 [ + + ]: 14842400 : if (nparams_expanded_x < nparams_expanded_y) {
1721 : 1166050 : *subtype = 0;
1722 : 1166050 : return 1; // number of fixed parameters in x could be fewer than in y
1723 : : }
1724 : 13676300 : uncertain = 1;
1725 : : }
1726 : : }
1727 [ - + ]: 56920500 : else if (npx != npy) {
1728 : 0 : *subtype = 0;
1729 : 0 : return 1;
1730 : : }
1731 : :
1732 : : // inspect the fixed parameters in y against x
1733 [ + + ]: 240858000 : for (i = 0; i < npy - (vy == JL_VARARG_NONE ? 0 : 1); i++) {
1734 [ + - ]: 186253000 : jl_value_t *a = i >= (npx - (vx == JL_VARARG_NONE ? 0 : 1)) ? vxt : jl_tparam(x, i);
1735 : 186253000 : jl_value_t *b = jl_tparam(y, i);
1736 [ + + + + ]: 186253000 : if (iscov || jl_is_typevar(b)) {
1737 [ + + ]: 142072000 : if (obvious_subtype(a, b, y0, subtype)) {
1738 [ + + ]: 100144000 : if (!*subtype)
1739 : 33788800 : return 1;
1740 [ + + ]: 66355500 : if (jl_has_free_typevars(b)) // b is actually more constrained that this
1741 : 1406140 : uncertain = 1;
1742 : : }
1743 : : else {
1744 : 41927700 : uncertain = 1;
1745 : : }
1746 : : }
1747 : : else {
1748 [ + + ]: 44180800 : if (!obviously_egal(a, b)) {
1749 [ + + ]: 42828600 : if (obvious_subtype(a, b, y0, subtype)) {
1750 [ + + ]: 24379100 : if (!*subtype)
1751 : 22990500 : return 1;
1752 [ + + ]: 1388580 : if (jl_has_free_typevars(b)) // b is actually more constrained that this
1753 : 46 : uncertain = 1;
1754 : : }
1755 : : else {
1756 : 18449500 : uncertain = 1;
1757 : : }
1758 [ + + + + ]: 19838100 : if (!jl_has_free_typevars(b) && obvious_subtype(b, a, y0, subtype)) {
1759 [ + + ]: 2521010 : if (!*subtype)
1760 : 2483900 : return 1;
1761 [ + + ]: 37107 : if (jl_has_free_typevars(a)) // a is actually more constrained that this
1762 : 52 : uncertain = 1;
1763 : : }
1764 : : else {
1765 : 17317000 : uncertain = 1;
1766 : : }
1767 : : }
1768 : : }
1769 : : }
1770 [ + + ]: 54604700 : 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 [ + - + - : 9866480 : assert(vy != JL_VARARG_NONE && istuple && iscov);
+ - ]
1773 [ + + + - ]: 9866480 : jl_value_t *a1 = (vx != JL_VARARG_NONE && i >= npx - 1) ? vxt : jl_tparam(x, i);
1774 : 9866480 : jl_value_t *b = jl_unwrap_vararg(jl_tparam(y, i));
1775 [ + + ]: 9866480 : if (jl_is_typevar(b)) {
1776 : 131149 : jl_value_t *body = find_var_body(y0, (jl_tvar_t*)b);
1777 [ + + ]: 131149 : if (body == NULL)
1778 : 188 : body = y0;
1779 [ + + ]: 131149 : if (var_occurs_invariant(body, (jl_tvar_t*)b, 0))
1780 : 104 : return 0;
1781 : : }
1782 [ + + + + : 9866380 : 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 : 5658 : *subtype = 0;
1785 : 5658 : return 1;
1786 : : }
1787 : 9860720 : jl_value_t *a1u = jl_unwrap_unionall(a1);
1788 [ + + + + ]: 9860720 : if (jl_is_type_type(a1u) && jl_is_type(jl_tparam0(a1u))) {
1789 : 7256 : a1 = jl_typeof(jl_tparam0(a1u));
1790 : : }
1791 [ + + ]: 40511900 : for (; i < nparams_expanded_x; i++) {
1792 [ + + + - ]: 31557000 : jl_value_t *a = (vx != JL_VARARG_NONE && i >= npx - 1) ? vxt : jl_tparam(x, i);
1793 [ + + + + ]: 31557000 : 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 : 30578 : jl_value_t *a2 = a;
1796 : 30578 : jl_value_t *au = jl_unwrap_unionall(a);
1797 [ + + + - ]: 30578 : 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 : 285 : a2 = jl_typeof(jl_tparam0(au));
1800 : : }
1801 [ + + ]: 30578 : if (!obviously_egal(a1, a2)) {
1802 [ + + ]: 14503 : if (obvious_subtype(a2, a1, y0, subtype)) {
1803 [ + - ]: 9385 : if (!*subtype)
1804 : 9385 : return 1;
1805 [ # # ]: 0 : if (jl_has_free_typevars(a1)) // a1 is actually more constrained that this
1806 : 0 : uncertain = 1;
1807 : : }
1808 : : else {
1809 : 5118 : uncertain = 1;
1810 : : }
1811 [ + + ]: 5118 : if (obvious_subtype(a1, a2, y0, subtype)) {
1812 [ + + ]: 5033 : if (!*subtype)
1813 : 2009 : return 1;
1814 [ - + ]: 3024 : if (jl_has_free_typevars(a2)) // a2 is actually more constrained that this
1815 : 0 : uncertain = 1;
1816 : : }
1817 : : else {
1818 : 85 : uncertain = 1;
1819 : : }
1820 : : }
1821 : : }
1822 [ + + ]: 31545600 : if (obvious_subtype(a, b, y0, subtype)) {
1823 [ + + ]: 30910100 : if (!*subtype)
1824 : 894418 : return 1;
1825 [ + + ]: 30015600 : if (jl_has_free_typevars(b)) // b is actually more constrained that this
1826 : 31 : uncertain = 1;
1827 : : }
1828 : : else {
1829 : 635525 : uncertain = 1;
1830 : : }
1831 : : }
1832 : : }
1833 [ + + ]: 53693100 : if (uncertain)
1834 : 52364600 : return 0;
1835 : 1328580 : *subtype = 1;
1836 : 1328580 : return 1;
1837 : : }
1838 : : }
1839 : 0 : return 0;
1840 : : }
1841 : :
1842 : 224486000 : JL_DLLEXPORT int jl_obvious_subtype(jl_value_t *x, jl_value_t *y, int *subtype)
1843 : : {
1844 : 224486000 : 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 : 278139000 : 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 [ + + + + ]: 278139000 : if (y == (jl_value_t*)jl_any_type || x == jl_bottom_type)
1855 : 14756300 : return 1;
1856 [ + + ]: 263382000 : if (x == y ||
1857 [ + + ]: 195522000 : (jl_typeof(x) == jl_typeof(y) &&
1858 [ + + + + : 136989000 : (jl_is_unionall(y) || jl_is_uniontype(y)) &&
+ + ]
1859 : 9938760 : jl_types_egal(x, y))) {
1860 [ + + ]: 68015500 : if (envsz != 0) { // quickly copy env from x
1861 : 91240 : jl_unionall_t *ua = (jl_unionall_t*)x;
1862 : : int i;
1863 [ + + ]: 206082 : for (i = 0; i < envsz; i++) {
1864 [ - + ]: 114842 : assert(jl_is_unionall(ua));
1865 : 114842 : env[i] = (jl_value_t*)ua->var;
1866 : 114842 : ua = (jl_unionall_t*)ua->body;
1867 : : }
1868 : : }
1869 : 68015500 : return 1;
1870 : : }
1871 : 195367000 : int obvious_subtype = 2;
1872 [ + + ]: 195367000 : 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 : 37408400 : obvious_subtype = 3;
1882 : : }
1883 : 195367000 : init_stenv(&e, env, envsz);
1884 : 195367000 : int subtype = forall_exists_subtype(x, y, &e, 0);
1885 [ + + - + : 195367000 : assert(obvious_subtype == 3 || obvious_subtype == subtype || jl_has_free_typevars(x) || jl_has_free_typevars(y));
- - - - ]
1886 : : #ifndef NDEBUG
1887 [ + + + + : 195367000 : if (obvious_subtype == 0 || (obvious_subtype == 1 && envsz == 0))
+ + ]
1888 : 157953000 : subtype = obvious_subtype; // this ensures that running in a debugger doesn't change the result
1889 : : #endif
1890 : 195367000 : return subtype;
1891 : : }
1892 : :
1893 : 4842440 : 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 : 4842440 : init_stenv(&e2, NULL, 0);
1897 : 4842440 : e2.vars = e->vars;
1898 : 4842440 : e2.intersection = e->intersection;
1899 : 4842440 : e2.ignore_free = e->ignore_free;
1900 : 4842440 : e2.invdepth = invdepth;
1901 : 4842440 : e2.Rinvdepth = Rinvdepth;
1902 : 4842440 : e2.envsz = e->envsz;
1903 : 4842440 : e2.envout = e->envout;
1904 : 4842440 : e2.envidx = e->envidx;
1905 : 4842440 : return forall_exists_subtype(x, y, &e2, 0);
1906 : : }
1907 : :
1908 : 2528460 : static int subtype_in_env(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
1909 : : {
1910 : 2528460 : return subtype_in_env_(x, y, e, e->invdepth, e->Rinvdepth);
1911 : : }
1912 : :
1913 : 2313980 : static int subtype_bounds_in_env(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int R, int d)
1914 : : {
1915 [ + + + + ]: 2313980 : return subtype_in_env_(x, y, e, R ? e->invdepth : d, R ? d : e->Rinvdepth);
1916 : : }
1917 : :
1918 : 272539000 : JL_DLLEXPORT int jl_subtype(jl_value_t *x, jl_value_t *y)
1919 : : {
1920 : 272539000 : return jl_subtype_env(x, y, NULL, 0);
1921 : : }
1922 : :
1923 : 69546400 : JL_DLLEXPORT int jl_types_equal(jl_value_t *a, jl_value_t *b)
1924 : : {
1925 [ + + ]: 69546400 : if (a == b)
1926 : 3323690 : return 1;
1927 [ + + + + ]: 66222700 : if (jl_typeof(a) == jl_typeof(b) && jl_types_egal(a, b))
1928 : 1309180 : return 1;
1929 [ + + ]: 64913500 : if (obviously_unequal(a, b))
1930 : 50346800 : 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 [ + + + + ]: 14566700 : 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 : 2921440 : jl_value_t *temp = a;
1938 : 2921440 : a = b;
1939 : 2921440 : b = temp;
1940 : : }
1941 : : // first check if a <: b has an obvious answer
1942 : 14566700 : int subtype_ab = 2;
1943 [ + + - + ]: 14566700 : if (b == (jl_value_t*)jl_any_type || a == jl_bottom_type) {
1944 : 14222 : subtype_ab = 1;
1945 : : }
1946 [ + + ]: 14552500 : 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 : 5863770 : subtype_ab = 3;
1954 : : }
1955 : : // next check if b <: a has an obvious answer
1956 : 14566700 : int subtype_ba = 2;
1957 [ + - + + ]: 14566700 : if (a == (jl_value_t*)jl_any_type || b == jl_bottom_type) {
1958 : 16 : subtype_ba = 1;
1959 : : }
1960 [ + + ]: 14566700 : 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 : 5424360 : 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 : 14566700 : init_stenv(&e, NULL, 0);
1976 : 14566700 : int subtype = forall_exists_subtype(a, b, &e, 0);
1977 [ + + - + : 14566700 : assert(subtype_ab == 3 || subtype_ab == subtype || jl_has_free_typevars(a) || jl_has_free_typevars(b));
- - - - ]
1978 : : #ifndef NDEBUG
1979 [ + + + + ]: 14566700 : if (subtype_ab != 0 && subtype_ab != 1) // ensures that running in a debugger doesn't change the result
1980 : : #endif
1981 : 5863770 : 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 : 14566700 : init_stenv(&e, NULL, 0);
1992 : 14566700 : int subtype = forall_exists_subtype(b, a, &e, 0);
1993 [ + + - + : 14566700 : assert(subtype_ba == 3 || subtype_ba == subtype || jl_has_free_typevars(a) || jl_has_free_typevars(b));
- - - - ]
1994 : : #ifndef NDEBUG
1995 [ + + + + ]: 14566700 : if (subtype_ba != 0 && subtype_ba != 1) // ensures that running in a debugger doesn't change the result
1996 : : #endif
1997 : 5424360 : subtype_ba = subtype;
1998 : : }
1999 : : // all tests successful
2000 [ + + + + ]: 14566700 : return subtype_ab && subtype_ba;
2001 : : }
2002 : :
2003 : 1052770 : 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 [ + + + + ]: 1052770 : return !jl_is_kind(b) || !jl_is_type_type(a); // || jl_is_datatype_singleton((jl_datatype_t*)jl_tparam0(a));
2008 : : }
2009 : :
2010 : 33510900 : int jl_tuple1_isa(jl_value_t *child1, jl_value_t **child, size_t cl, jl_datatype_t *pdt)
2011 : : {
2012 [ + - + + ]: 33510900 : if (jl_is_tuple_type(pdt) && !jl_is_va_tuple(pdt)) {
2013 [ + + ]: 32708200 : if (cl != jl_nparams(pdt))
2014 : 11994 : return 0;
2015 : : size_t i;
2016 [ + + ]: 32696200 : if (!jl_isa(child1, jl_tparam(pdt, 0)))
2017 : 189 : return 0;
2018 [ + + ]: 71383900 : for (i = 1; i < cl; i++) {
2019 [ + + ]: 43268600 : if (!jl_isa(child[i - 1], jl_tparam(pdt, i)))
2020 : 4580680 : return 0;
2021 : : }
2022 : 28115300 : return 1;
2023 : : }
2024 : 802759 : jl_value_t *tu = (jl_value_t*)arg_type_tuple(child1, child, cl);
2025 : : int ans;
2026 : 802759 : JL_GC_PUSH1(&tu);
2027 : 802759 : ans = jl_subtype(tu, (jl_value_t*)pdt);
2028 : 802759 : JL_GC_POP();
2029 : 802759 : return ans;
2030 : : }
2031 : :
2032 : 12 : int jl_tuple_isa(jl_value_t **child, size_t cl, jl_datatype_t *pdt)
2033 : : {
2034 [ - + ]: 12 : if (cl == 0) {
2035 [ # # ]: 0 : if (pdt == jl_emptytuple_type)
2036 : 0 : 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 : 12 : 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 : 2438450 : int jl_has_intersect_type_not_kind(jl_value_t *t)
2047 : : {
2048 : 2438450 : t = jl_unwrap_unionall(t);
2049 [ - + ]: 2438450 : if (t == (jl_value_t*)jl_any_type)
2050 : 0 : return 1;
2051 [ + + ]: 2438450 : if (jl_is_uniontype(t)) {
2052 [ + + + + ]: 84784 : return jl_has_intersect_type_not_kind(((jl_uniontype_t*)t)->a) ||
2053 : 36934 : jl_has_intersect_type_not_kind(((jl_uniontype_t*)t)->b);
2054 : : }
2055 [ - + ]: 2390600 : if (jl_is_typevar(t)) {
2056 : 0 : return jl_has_intersect_type_not_kind(((jl_tvar_t*)t)->ub);
2057 : : }
2058 [ + - ]: 2390600 : if (jl_is_datatype(t)) {
2059 [ + + ]: 2390600 : if (((jl_datatype_t*)t)->name == jl_type_typename)
2060 : 2015470 : return 1;
2061 : : }
2062 : 375127 : return 0;
2063 : : }
2064 : :
2065 : 287785000 : JL_DLLEXPORT int jl_isa(jl_value_t *x, jl_value_t *t)
2066 : : {
2067 [ + + + + ]: 287785000 : if (jl_typeis(x,t) || t == (jl_value_t*)jl_any_type)
2068 : 208798000 : return 1;
2069 [ + + ]: 78986800 : if (jl_is_type(x)) {
2070 [ + + ]: 52959300 : if (t == (jl_value_t*)jl_type_type)
2071 : 46306900 : return 1;
2072 [ + + ]: 6652350 : if (!jl_has_free_typevars(x)) {
2073 [ + + ]: 6652110 : if (jl_is_concrete_type(t))
2074 : 1121270 : return 0;
2075 [ + + ]: 5530840 : if (jl_is_type_type(t))
2076 : 1701580 : return jl_types_equal(x, jl_tparam0(t));
2077 : 3829260 : jl_value_t *t2 = jl_unwrap_unionall(t);
2078 [ + + ]: 3829260 : if (jl_is_datatype(t2)) {
2079 [ + + ]: 3794770 : if (((jl_datatype_t*)t2)->name == jl_type_typename) {
2080 : 3764510 : jl_value_t *tp = jl_tparam0(t2);
2081 [ + + ]: 3764510 : if (jl_is_typevar(tp)) {
2082 [ + + ]: 1765290 : if (((jl_tvar_t*)tp)->lb == jl_bottom_type) {
2083 [ + + ]: 3530340 : while (jl_is_typevar(tp))
2084 : 1765170 : tp = ((jl_tvar_t*)tp)->ub;
2085 [ + + ]: 1765170 : if (!jl_has_free_typevars(tp))
2086 : 1765020 : return jl_subtype(x, tp);
2087 : : }
2088 [ + - ]: 114 : else if (((jl_tvar_t*)tp)->ub == (jl_value_t*)jl_any_type) {
2089 [ + + ]: 228 : while (jl_is_typevar(tp))
2090 : 114 : tp = ((jl_tvar_t*)tp)->lb;
2091 [ + - ]: 114 : if (!jl_has_free_typevars(tp))
2092 : 114 : return jl_subtype(tp, x);
2093 : : }
2094 : : }
2095 : : }
2096 : : else {
2097 : 30257 : return 0;
2098 : : }
2099 : : }
2100 [ + + ]: 2033860 : if (jl_subtype(jl_typeof(x), t))
2101 : 222 : return 1;
2102 [ + + ]: 2033640 : if (jl_has_intersect_type_not_kind(t2)) {
2103 : 2010710 : JL_GC_PUSH1(&x);
2104 : 2010710 : x = (jl_value_t*)jl_wrap_Type(x); // TODO jb/subtype avoid jl_wrap_Type
2105 : 2010710 : int ans = jl_subtype(x, t);
2106 : 2010710 : JL_GC_POP();
2107 : 2010710 : return ans;
2108 : : }
2109 : 22926 : return 0;
2110 : : }
2111 : : }
2112 [ + + + + ]: 26027800 : if (jl_is_concrete_type(t) && jl_type_equality_is_identity(jl_typeof(x), t))
2113 : 425134 : return 0;
2114 : 25602700 : 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 : 2425130 : 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 [ + + + + ]: 2425130 : if (x == (jl_value_t*)jl_any_type && !jl_is_typevar(y))
2128 : 720384 : return y;
2129 [ + + + - ]: 1704740 : if (y == (jl_value_t*)jl_any_type && !jl_is_typevar(x))
2130 : 179110 : return x;
2131 : :
2132 : 1525630 : jl_saved_unionstate_t oldRunions; push_unionstate(&oldRunions, &e->Runions);
2133 : 1525630 : int savedepth = e->invdepth, Rsavedepth = e->Rinvdepth;
2134 : : // TODO: this doesn't quite make sense
2135 : 1525630 : e->invdepth = e->Rinvdepth = d;
2136 : :
2137 : 1525630 : jl_value_t *res = intersect_all(x, y, e);
2138 : :
2139 : 1525630 : pop_unionstate(&e->Runions, &oldRunions);
2140 : 1525630 : e->invdepth = savedepth;
2141 : 1525630 : e->Rinvdepth = Rsavedepth;
2142 : 1525630 : return res;
2143 : : }
2144 : :
2145 : 4684110 : 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 [ + + + + : 4684110 : if (param == 2 || (!jl_has_free_typevars(x) && !jl_has_free_typevars((jl_value_t*)u))) {
+ + ]
2148 : 3529910 : jl_value_t *a=NULL, *b=NULL;
2149 : 3529910 : JL_GC_PUSH2(&a, &b);
2150 : 3529910 : jl_saved_unionstate_t oldRunions; push_unionstate(&oldRunions, &e->Runions);
2151 [ + + ]: 3529910 : a = R ? intersect_all(x, u->a, e) : intersect_all(u->a, x, e);
2152 [ + + ]: 3529910 : b = R ? intersect_all(x, u->b, e) : intersect_all(u->b, x, e);
2153 : 3529910 : pop_unionstate(&e->Runions, &oldRunions);
2154 : 3529910 : jl_value_t *i = simple_join(a,b);
2155 : 3529910 : JL_GC_POP();
2156 : 3529910 : return i;
2157 : : }
2158 : 1154200 : 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 [ + + ]: 1154200 : return R ? intersect(x, choice, e, param) : intersect(choice, x, e, param);
2161 : : }
2162 : :
2163 : : // set a variable to a non-type constant
2164 : 199444 : 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 : 199444 : int offset = bb->offset;
2167 [ + + + - ]: 199444 : if (othervar && offset == 0)
2168 : 20773 : offset = -othervar->offset;
2169 [ + + - + ]: 199444 : assert(!othervar || othervar->offset == -offset);
2170 [ + + + + ]: 199444 : if (bb->lb == jl_bottom_type && bb->ub == (jl_value_t*)jl_any_type) {
2171 [ + + ]: 136563 : if (jl_is_long(v))
2172 : 102812 : v = jl_box_long(jl_unbox_long(v) + offset);
2173 : 136563 : bb->lb = bb->ub = v;
2174 : : }
2175 [ + + + + ]: 62881 : else if (jl_is_long(v) && jl_is_long(bb->lb)) {
2176 [ + + ]: 60449 : if (jl_unbox_long(v) != jl_unbox_long(bb->lb))
2177 : 232 : return jl_bottom_type;
2178 : : }
2179 [ + + ]: 2432 : else if (!jl_egal(v, bb->lb)) {
2180 : 1534 : return jl_bottom_type;
2181 : : }
2182 : 197678 : return v;
2183 : : }
2184 : :
2185 : 2159 : static jl_value_t *bound_var_below(jl_tvar_t *tv, jl_varbinding_t *bb, jl_stenv_t *e) {
2186 [ - + ]: 2159 : if (!bb)
2187 : 0 : return (jl_value_t*)tv;
2188 [ + + ]: 2159 : if (bb->depth0 != e->invdepth)
2189 : 705 : return jl_bottom_type;
2190 : 1454 : record_var_occurrence(bb, e, 2);
2191 [ + + ]: 1454 : if (jl_is_long(bb->lb)) {
2192 [ + - ]: 70 : if (bb->offset == 0)
2193 : 70 : return bb->lb;
2194 [ # # ]: 0 : if (jl_unbox_long(bb->lb) < bb->offset)
2195 : 0 : return jl_bottom_type;
2196 : 0 : return jl_box_long(jl_unbox_long(bb->lb) - bb->offset);
2197 : : }
2198 : 1384 : return (jl_value_t*)tv;
2199 : : }
2200 : :
2201 : 178209 : static int try_subtype_in_env(jl_value_t *a, jl_value_t *b, jl_stenv_t *e, int R, int d)
2202 : : {
2203 : 178209 : jl_value_t *root=NULL; jl_savedenv_t se;
2204 : 178209 : JL_GC_PUSH1(&root);
2205 : 178209 : save_env(e, &root, &se);
2206 : 178209 : int ret = subtype_bounds_in_env(a, b, e, R, d);
2207 : 178209 : restore_env(e, root, &se);
2208 : 178209 : free_env(&se);
2209 : 178209 : JL_GC_POP();
2210 : 178209 : return ret;
2211 : : }
2212 : :
2213 : 59747 : static void set_bound(jl_value_t **bound, jl_value_t *val, jl_tvar_t *v, jl_stenv_t *e) JL_NOTSAFEPOINT
2214 : : {
2215 [ - + ]: 59747 : if (in_union(val, (jl_value_t*)v))
2216 : 0 : return;
2217 : 59747 : jl_varbinding_t *btemp = e->vars;
2218 [ + + ]: 146688 : while (btemp != NULL) {
2219 [ + + + + : 96911 : if ((btemp->lb == (jl_value_t*)v || btemp->ub == (jl_value_t*)v) &&
- + ]
2220 : 9970 : in_union(val, (jl_value_t*)btemp->var))
2221 : 0 : return;
2222 : 86941 : btemp = btemp->prev;
2223 : : }
2224 : 59747 : *bound = val;
2225 : : }
2226 : :
2227 : : // subtype, treating all vars as existential
2228 : 3289920 : static int subtype_in_env_existential(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int R, int d)
2229 : : {
2230 : 3289920 : jl_varbinding_t *v = e->vars;
2231 : 3289920 : int len = 0;
2232 [ + + + + ]: 3289920 : if (x == jl_bottom_type || y == (jl_value_t*)jl_any_type)
2233 : 1154150 : return 1;
2234 [ + + ]: 9637320 : while (v != NULL) {
2235 : 7501550 : len++;
2236 : 7501550 : v = v->prev;
2237 : : }
2238 : 2135770 : int8_t *rs = (int8_t*)malloc_s(len);
2239 : 2135770 : int n = 0;
2240 : 2135770 : v = e->vars;
2241 [ + + ]: 9637320 : while (n < len) {
2242 [ - + ]: 7501550 : assert(v != NULL);
2243 : 7501550 : rs[n++] = v->right;
2244 : 7501550 : v->right = 1;
2245 : 7501550 : v = v->prev;
2246 : : }
2247 : 2135770 : int issub = subtype_bounds_in_env(x, y, e, R, d);
2248 : 2135770 : n = 0; v = e->vars;
2249 [ + + ]: 9637320 : while (n < len) {
2250 [ - + ]: 7501550 : assert(v != NULL);
2251 : 7501550 : v->right = rs[n++];
2252 : 7501550 : v = v->prev;
2253 : : }
2254 : 2135770 : free(rs);
2255 : 2135770 : return issub;
2256 : : }
2257 : :
2258 : : // See if var y is reachable from x via bounds; used to avoid cycles.
2259 : 9555000 : static int reachable_var(jl_value_t *x, jl_tvar_t *y, jl_stenv_t *e)
2260 : : {
2261 [ + + ]: 9555000 : if (in_union(x, (jl_value_t*)y))
2262 : 56 : return 1;
2263 [ + + ]: 9554940 : if (!jl_is_typevar(x))
2264 : 8569670 : return 0;
2265 : 985269 : jl_varbinding_t *xv = lookup(e, (jl_tvar_t*)x);
2266 [ + + ]: 985269 : if (xv == NULL)
2267 : 446 : return 0;
2268 [ + - - + ]: 984823 : 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 : 74372 : static int check_unsat_bound(jl_value_t *t, jl_tvar_t *v, jl_stenv_t *e) JL_NOTSAFEPOINT
2273 : : {
2274 [ + + ]: 74372 : if (var_occurs_inside(t, v, 0, 0))
2275 : 24 : return 1;
2276 : 74348 : jl_varbinding_t *btemp = e->vars;
2277 [ + + ]: 272513 : while (btemp != NULL) {
2278 [ + + + - : 198181 : if (btemp->lb == (jl_value_t*)v && btemp->ub == (jl_value_t*)v &&
+ - ]
2279 : 8 : var_occurs_inside(t, btemp->var, 0, 0))
2280 : 8 : return 1;
2281 : 198165 : btemp = btemp->prev;
2282 : : }
2283 : 74340 : return 0;
2284 : : }
2285 : :
2286 : 2468270 : 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 : 2468270 : jl_varbinding_t *bb = lookup(e, b);
2289 [ + + ]: 2468270 : if (bb == NULL)
2290 [ + - ]: 530 : return R ? intersect_aside(a, b->ub, e, 1, 0) : intersect_aside(b->ub, a, e, 0, 0);
2291 [ + - - + ]: 2467740 : if (reachable_var(bb->lb, b, e) || reachable_var(bb->ub, b, e))
2292 : 0 : return a;
2293 [ + + + + ]: 2467740 : if (bb->lb == bb->ub && jl_is_typevar(bb->lb)) {
2294 : 31103 : return intersect(a, bb->lb, e, param);
2295 : : }
2296 [ + + + + ]: 2436630 : if (!jl_is_type(a) && !jl_is_typevar(a))
2297 : 177593 : return set_var_to_const(bb, a, NULL);
2298 : 2259040 : int d = bb->depth0;
2299 : 2259040 : jl_value_t *root=NULL; jl_savedenv_t se;
2300 [ + + ]: 2259040 : if (param == 2) {
2301 : 1433190 : jl_value_t *ub = NULL;
2302 : 1433190 : JL_GC_PUSH2(&ub, &root);
2303 [ + + ]: 1433190 : if (!jl_has_free_typevars(a)) {
2304 : 828809 : save_env(e, &root, &se);
2305 [ + + + + ]: 828809 : int issub = subtype_in_env_existential(bb->lb, a, e, 0, d) && subtype_in_env_existential(a, bb->ub, e, 1, d);
2306 : 828809 : restore_env(e, root, &se);
2307 : 828809 : free_env(&se);
2308 [ + + ]: 828809 : if (!issub) {
2309 : 490449 : JL_GC_POP();
2310 : 490449 : return jl_bottom_type;
2311 : : }
2312 : 338360 : ub = a;
2313 : : }
2314 : : else {
2315 : 604379 : e->triangular++;
2316 [ + + ]: 604379 : ub = R ? intersect_aside(a, bb->ub, e, 1, d) : intersect_aside(bb->ub, a, e, 0, d);
2317 : 604379 : e->triangular--;
2318 : 604379 : save_env(e, &root, &se);
2319 : 604379 : int issub = subtype_in_env_existential(bb->lb, ub, e, 0, d);
2320 : 604379 : restore_env(e, root, &se);
2321 : 604379 : free_env(&se);
2322 [ + + ]: 604379 : if (!issub) {
2323 : 85533 : JL_GC_POP();
2324 : 85533 : return jl_bottom_type;
2325 : : }
2326 : : }
2327 [ + - ]: 857206 : if (ub != (jl_value_t*)b) {
2328 [ + + ]: 857206 : if (jl_has_free_typevars(ub)) {
2329 [ + + ]: 74182 : if (check_unsat_bound(ub, b, e)) {
2330 : 32 : JL_GC_POP();
2331 : 32 : return jl_bottom_type;
2332 : : }
2333 : : }
2334 : 857174 : bb->ub = ub;
2335 : 857174 : bb->lb = ub;
2336 : : }
2337 : 857174 : JL_GC_POP();
2338 : 857174 : return ub;
2339 : : }
2340 [ + + ]: 825852 : jl_value_t *ub = R ? intersect_aside(a, bb->ub, e, 1, d) : intersect_aside(bb->ub, a, e, 0, d);
2341 [ + + ]: 825852 : if (ub == jl_bottom_type)
2342 : 528104 : return jl_bottom_type;
2343 [ + + + + ]: 297748 : if (bb->constraintkind == 1 || e->triangular) {
2344 [ + + - + ]: 37907 : if (e->triangular && check_unsat_bound(ub, b, e))
2345 : 0 : return jl_bottom_type;
2346 : 37907 : set_bound(&bb->ub, ub, b, e);
2347 : 37907 : return (jl_value_t*)b;
2348 : : }
2349 [ + + ]: 259841 : else if (bb->constraintkind == 0) {
2350 : 179061 : JL_GC_PUSH1(&ub);
2351 [ + + + + ]: 179061 : if (!jl_is_typevar(a) && try_subtype_in_env(bb->ub, a, e, 0, d)) {
2352 : 99053 : JL_GC_POP();
2353 : 99053 : return (jl_value_t*)b;
2354 : : }
2355 : 80008 : JL_GC_POP();
2356 : 80008 : return ub;
2357 : : }
2358 [ - + ]: 80780 : assert(bb->constraintkind == 2);
2359 [ + + ]: 80780 : if (!jl_is_typevar(a)) {
2360 [ + + + + ]: 80502 : if (ub == a && bb->lb != jl_bottom_type)
2361 : 39111 : return ub;
2362 [ + + ]: 41391 : else if (jl_egal(bb->ub, bb->lb))
2363 : 19551 : return ub;
2364 : 21840 : set_bound(&bb->ub, ub, b, e);
2365 : : }
2366 : 22118 : 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 : 33622200 : static int var_occurs_inside(jl_value_t *v, jl_tvar_t *var, int inside, int want_inv) JL_NOTSAFEPOINT
2373 : : {
2374 [ + + ]: 33622200 : if (v == (jl_value_t*)var) {
2375 : 3674200 : return inside;
2376 : : }
2377 [ + + ]: 29948000 : else if (jl_is_uniontype(v)) {
2378 [ + - + + ]: 2266500 : return var_occurs_inside(((jl_uniontype_t*)v)->a, var, inside, want_inv) ||
2379 : 1133250 : var_occurs_inside(((jl_uniontype_t*)v)->b, var, inside, want_inv);
2380 : : }
2381 [ + + ]: 28814700 : else if (jl_is_unionall(v)) {
2382 : 4596810 : jl_unionall_t *ua = (jl_unionall_t*)v;
2383 [ + + ]: 4596810 : if (ua->var == var)
2384 : 308 : return 0;
2385 [ + - + + ]: 4596500 : if (var_occurs_inside(ua->var->lb, var, inside, want_inv) || var_occurs_inside(ua->var->ub, var, inside, want_inv))
2386 : 552 : return 1;
2387 : 4595950 : return var_occurs_inside(ua->body, var, inside, want_inv);
2388 : : }
2389 [ + + ]: 24217900 : else if (jl_is_vararg(v)) {
2390 : 976739 : jl_vararg_t *vm = (jl_vararg_t*)v;
2391 [ + - ]: 976739 : if (vm->T) {
2392 [ + + - + : 976739 : if (var_occurs_inside(vm->T, var, inside || !want_inv, want_inv))
+ + ]
2393 : 64 : return 1;
2394 [ + + + + ]: 976675 : return vm->N && var_occurs_inside(vm->N, var, 1, want_inv);
2395 : : }
2396 : : }
2397 [ + + ]: 23241200 : else if (jl_is_datatype(v)) {
2398 : : size_t i;
2399 : 11917400 : int istuple = jl_is_tuple_type(v);
2400 [ + + ]: 24117500 : for (i=0; i < jl_nparams(v); i++) {
2401 [ + + + + : 12226000 : int ins_i = inside || !want_inv || !istuple;
+ + ]
2402 [ + + ]: 12226000 : if (var_occurs_inside(jl_tparam(v,i), var, ins_i, want_inv))
2403 : 25872 : return 1;
2404 : : }
2405 : : }
2406 : 23215300 : return 0;
2407 : : }
2408 : :
2409 : : // Caller might not have rooted `res`
2410 : 2227340 : 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 : 2227340 : jl_value_t *varval = NULL;
2413 : 2227340 : jl_tvar_t *newvar = vb->var;
2414 : 2227340 : JL_GC_PUSH2(&res, &newvar);
2415 : : // try to reduce var to a single value
2416 [ + + - + ]: 2227340 : if (jl_is_long(vb->ub) && jl_is_typevar(vb->lb)) {
2417 : 0 : varval = vb->ub;
2418 : : }
2419 [ + + ]: 2227340 : else if (obviously_egal(vb->lb, vb->ub)) {
2420 : : // given x<:T<:x, substitute x for T
2421 : 1318140 : 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 [ + + ]: 909192 : else if ((/*vb->occurs_cov == 1 || */is_leaf_bound(vb->ub)) &&
2426 [ + + ]: 16129 : !var_occurs_invariant(u->body, u->var, 0)) {
2427 : : // replace T<:x with x in covariant position when possible
2428 : 8582 : varval = vb->ub;
2429 : : }
2430 : :
2431 [ + + ]: 2227340 : if (vb->intvalued) {
2432 [ + + + + ]: 3663 : if ((varval && jl_is_long(varval)) ||
2433 [ + + + - ]: 2963 : (vb->lb == jl_bottom_type && vb->ub == (jl_value_t*)jl_any_type) ||
2434 [ + - + - ]: 802 : (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 : 0 : JL_GC_POP();
2440 : 0 : return jl_bottom_type;
2441 : : }
2442 : : }
2443 : :
2444 : : // TODO: this can prevent us from matching typevar identities later
2445 [ + + + + : 2227340 : if (!varval && (vb->lb != vb->var->lb || vb->ub != vb->var->ub))
+ + ]
2446 : 139154 : 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 : 2227340 : jl_varbinding_t *btemp = e->vars;
2450 : 2227340 : int wrap = 1;
2451 [ + + ]: 7756600 : while (btemp != NULL) {
2452 [ + + ]: 5529260 : if (jl_has_typevar(btemp->lb, vb->var)) {
2453 [ - + ]: 2289 : if (vb->lb == (jl_value_t*)btemp->var) {
2454 : 0 : JL_GC_POP();
2455 : 0 : return jl_bottom_type;
2456 : : }
2457 [ + + ]: 2289 : if (varval) {
2458 [ + - + + ]: 56 : JL_TRY {
2459 : 28 : btemp->lb = jl_substitute_var(btemp->lb, vb->var, varval);
2460 : : }
2461 [ # # ]: 0 : JL_CATCH {
2462 : 0 : res = jl_bottom_type;
2463 : : }
2464 : : }
2465 [ - + ]: 2261 : else if (btemp->lb == (jl_value_t*)vb->var)
2466 : 0 : btemp->lb = vb->lb;
2467 [ + - + - ]: 2261 : else if (btemp->depth0 == vb->depth0 && !jl_has_typevar(vb->lb, btemp->var) &&
2468 [ + - + - ]: 2261 : !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 [ + + ]: 2261 : if (btemp->innervars == NULL)
2472 : 1207 : btemp->innervars = jl_alloc_array_1d(jl_array_any_type, 0);
2473 [ + + ]: 2261 : if (newvar != vb->var) {
2474 : 138 : btemp->lb = jl_substitute_var(btemp->lb, vb->var, (jl_value_t*)newvar);
2475 : 138 : btemp->ub = jl_substitute_var(btemp->ub, vb->var, (jl_value_t*)newvar);
2476 : : }
2477 : 2261 : jl_array_ptr_1d_push(btemp->innervars, (jl_value_t*)newvar);
2478 : 2261 : wrap = 0;
2479 : 2261 : btemp = btemp->prev;
2480 : 2261 : continue;
2481 : : }
2482 : : else
2483 : 0 : btemp->lb = jl_new_struct(jl_unionall_type, vb->var, btemp->lb);
2484 [ - + ]: 28 : assert((jl_value_t*)btemp->var != btemp->lb);
2485 : : }
2486 [ + + ]: 5527000 : if (jl_has_typevar(btemp->ub, vb->var)) {
2487 [ - + ]: 1911 : if (vb->ub == (jl_value_t*)btemp->var) {
2488 : 0 : JL_GC_POP();
2489 : 0 : return jl_bottom_type;
2490 : : }
2491 [ + + ]: 1911 : if (varval) {
2492 [ + - + + ]: 1552 : JL_TRY {
2493 : 776 : btemp->ub = jl_substitute_var(btemp->ub, vb->var, varval);
2494 : : }
2495 [ # # ]: 0 : JL_CATCH {
2496 : 0 : res = jl_bottom_type;
2497 : : }
2498 : : }
2499 [ + + ]: 1135 : else if (btemp->ub == (jl_value_t*)vb->var)
2500 : 195 : btemp->ub = vb->ub;
2501 : : else
2502 : 940 : btemp->ub = jl_new_struct(jl_unionall_type, vb->var, btemp->ub);
2503 [ - + ]: 1911 : assert((jl_value_t*)btemp->var != btemp->ub);
2504 : : }
2505 : 5527000 : btemp = btemp->prev;
2506 : : }
2507 : :
2508 : : // if `v` still occurs, re-wrap body in `UnionAll v` or eliminate the UnionAll
2509 [ + + ]: 2227340 : if (jl_has_typevar(res, vb->var)) {
2510 [ + + ]: 977536 : if (varval) {
2511 [ + + + + ]: 302694 : 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 : 152268 : res = jl_substitute_var(res, vb->var, varval);
2515 : : // simplify chains of UnionAlls where bounds become equal
2516 [ + + - + ]: 163052 : while (jl_is_unionall(res) && obviously_egal(((jl_unionall_t*)res)->var->lb,
2517 : 12626 : ((jl_unionall_t*)res)->var->ub))
2518 : 0 : res = jl_instantiate_unionall((jl_unionall_t*)res, ((jl_unionall_t*)res)->var->lb);
2519 : : }
2520 [ + + ]: 3684 : JL_CATCH {
2521 : 1842 : res = jl_bottom_type;
2522 : : }
2523 : : }
2524 : : else {
2525 [ + + ]: 825268 : if (newvar != vb->var)
2526 : 139070 : res = jl_substitute_var(res, vb->var, (jl_value_t*)newvar);
2527 : 825268 : varval = (jl_value_t*)newvar;
2528 [ + + ]: 825268 : if (wrap)
2529 : 823015 : res = jl_type_unionall((jl_tvar_t*)newvar, res);
2530 : : }
2531 : : }
2532 : :
2533 [ + + + + ]: 2227340 : if (res != jl_bottom_type && vb->innervars != NULL) {
2534 : : int i;
2535 [ + + ]: 4509 : for(i=0; i < jl_array_len(vb->innervars); i++) {
2536 : 2885 : jl_tvar_t *var = (jl_tvar_t*)jl_array_ptr_ref(vb->innervars, i);
2537 [ + + ]: 2885 : if (jl_has_typevar(res, var))
2538 : 2057 : res = jl_type_unionall((jl_tvar_t*)var, res);
2539 : : }
2540 : : }
2541 : :
2542 [ + + + + ]: 2227340 : if (vb->right && e->envidx < e->envsz) {
2543 : 331442 : jl_value_t *oldval = e->envout[e->envidx];
2544 [ + + + + : 331442 : if (!varval || (!is_leaf_bound(varval) && !vb->occurs_inv))
+ + ]
2545 : 103191 : e->envout[e->envidx] = (jl_value_t*)vb->var;
2546 [ + + + + : 228251 : else if (!(oldval && jl_is_typevar(oldval) && jl_is_long(varval)))
+ - ]
2547 : 228251 : e->envout[e->envidx] = fix_inferred_var_bound(vb->var, varval);
2548 : : }
2549 : :
2550 : 2227340 : JL_GC_POP();
2551 : 2227340 : return res;
2552 : : }
2553 : :
2554 : 11226900 : 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 : 11226900 : 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 : 11226900 : int envsize = 0;
2561 [ + + ]: 27979700 : while (btemp != NULL) {
2562 : 17024500 : envsize++;
2563 [ - + ]: 17024500 : if (envsize > 120) {
2564 : 0 : vb->limited = 1;
2565 : 0 : return t;
2566 : : }
2567 [ + + + - ]: 17024500 : if (btemp->var == u->var || btemp->lb == (jl_value_t*)u->var ||
2568 [ - + ]: 16752800 : btemp->ub == (jl_value_t*)u->var) {
2569 : 271621 : u = rename_unionall(u);
2570 : 271621 : break;
2571 : : }
2572 : 16752800 : btemp = btemp->prev;
2573 : : }
2574 : 11226900 : JL_GC_PUSH1(&u);
2575 : 11226900 : vb->var = u->var;
2576 : 11226900 : e->vars = vb;
2577 : : jl_value_t *res;
2578 [ + + ]: 11226900 : if (R) {
2579 : 6620520 : e->envidx++;
2580 : 6620520 : res = intersect(t, u->body, e, param);
2581 : 6620520 : e->envidx--;
2582 : : }
2583 : : else {
2584 : 4606350 : res = intersect(u->body, t, e, param);
2585 : : }
2586 [ + + + - : 11292500 : vb->concrete |= (vb->occurs_cov > 1 && is_leaf_typevar(u->var) &&
+ + ]
2587 : 65605 : !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 [ + + + + ]: 11226900 : if (res != jl_bottom_type && vb->concrete) {
2595 [ + - ]: 32748 : if (jl_is_typevar(vb->lb)) {
2596 : : }
2597 [ - + ]: 32748 : else if (!is_leaf_bound(vb->lb)) {
2598 : 0 : res = jl_bottom_type;
2599 : : }
2600 : : }
2601 : :
2602 : 11226900 : e->vars = vb->prev;
2603 : :
2604 [ + + ]: 11226900 : if (res != jl_bottom_type) {
2605 [ + + - + ]: 2227340 : if (vb->ub == jl_bottom_type && vb->occurs_cov) {
2606 : : // T=Bottom in covariant position
2607 : 0 : res = jl_bottom_type;
2608 : : }
2609 [ + - - + ]: 2227340 : else if (jl_has_typevar(vb->lb, u->var) || jl_has_typevar(vb->ub, u->var)) {
2610 : : // fail on circular constraints
2611 : 0 : res = jl_bottom_type;
2612 : : }
2613 : : }
2614 [ + + ]: 11226900 : if (res != jl_bottom_type)
2615 : : // res is rooted by callee
2616 : 2227340 : res = finish_unionall(res, vb, u, e);
2617 : 11226900 : JL_GC_POP();
2618 : 11226900 : return res;
2619 : : }
2620 : :
2621 : 10968500 : 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 : 10968500 : jl_value_t *res=NULL, *save=NULL;
2624 : : jl_savedenv_t se;
2625 [ + + ]: 10968500 : jl_varbinding_t vb = { u->var, u->var->lb, u->var->ub, R, 0, 0, 0, 0, 0, 0,
2626 : 10968500 : R ? e->Rinvdepth : e->invdepth, 0, NULL, e->vars };
2627 : 10968500 : JL_GC_PUSH5(&res, &vb.lb, &vb.ub, &save, &vb.innervars);
2628 : 10968500 : save_env(e, &save, &se);
2629 : 10968500 : res = intersect_unionall_(t, u, e, R, param, &vb);
2630 [ - + ]: 10968500 : 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 [ + + ]: 10968500 : else if (res != jl_bottom_type) {
2636 [ + + + + : 1979910 : if (vb.concrete || vb.occurs_inv>1 || u->var->lb != jl_bottom_type || (vb.occurs_inv && vb.occurs_cov)) {
+ + + + +
+ ]
2637 : 254300 : restore_env(e, NULL, &se);
2638 : 254300 : vb.occurs_cov = vb.occurs_inv = 0;
2639 [ + + ]: 254300 : vb.constraintkind = vb.concrete ? 1 : 2;
2640 : 254300 : res = intersect_unionall_(t, u, e, R, param, &vb);
2641 : : }
2642 [ + + + + ]: 1725610 : else if (vb.occurs_cov && !var_occurs_invariant(u->body, u->var, 0)) {
2643 : 4020 : restore_env(e, save, &se);
2644 : 4020 : vb.occurs_cov = vb.occurs_inv = 0;
2645 : 4020 : vb.constraintkind = 1;
2646 : 4020 : res = intersect_unionall_(t, u, e, R, param, &vb);
2647 : : }
2648 : : }
2649 : 10968500 : free_env(&se);
2650 : 10968500 : JL_GC_POP();
2651 : 10968500 : return res;
2652 : : }
2653 : :
2654 : : // check n = (length of vararg type v)
2655 : 70449 : static int intersect_vararg_length(jl_value_t *v, ssize_t n, jl_stenv_t *e, int8_t R)
2656 : : {
2657 : 70449 : 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 [ + + + - ]: 70449 : if (N && jl_is_typevar(N)) {
2660 : 50783 : jl_value_t *len = jl_box_long(n);
2661 : 50783 : JL_GC_PUSH1(&len);
2662 [ + + ]: 50783 : jl_value_t *il = R ? intersect(len, N, e, 2) : intersect(N, len, e, 2);
2663 : 50783 : JL_GC_POP();
2664 [ + + ]: 50783 : if (il == jl_bottom_type)
2665 : 133 : return 0;
2666 : : }
2667 : 70316 : return 1;
2668 : : }
2669 : :
2670 : : static jl_value_t *intersect_invariant(jl_value_t *x, jl_value_t *y, jl_stenv_t *e);
2671 : 7931 : 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 : 7931 : jl_value_t *xp1=jl_unwrap_vararg(vmx), *xp2=jl_unwrap_vararg_num(vmx),
2675 : 7931 : *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 [ + + + + ]: 7931 : if (intersect(xp1, yp1, e, param==0 ? 1 : param) == jl_bottom_type)
2680 : 1664 : return jl_bottom_type;
2681 : 6267 : jl_value_t *i2=NULL, *ii = intersect(xp1, yp1, e, 1);
2682 [ + + ]: 6267 : if (ii == jl_bottom_type) return jl_bottom_type;
2683 : 6123 : JL_GC_PUSH2(&ii, &i2);
2684 [ + + + + ]: 6123 : if (!xp2 && !yp2) {
2685 : 2029 : ii = (jl_value_t*)jl_wrap_vararg(ii, NULL);
2686 : 2029 : JL_GC_POP();
2687 : 2029 : return ii;
2688 : : }
2689 [ + + + - ]: 4094 : if (xp2 && jl_is_typevar(xp2)) {
2690 : 2702 : jl_varbinding_t *xb = lookup(e, (jl_tvar_t*)xp2);
2691 [ + - ]: 2702 : if (xb) xb->intvalued = 1;
2692 [ + + ]: 2702 : if (!yp2) {
2693 : 767 : i2 = bound_var_below((jl_tvar_t*)xp2, xb, e);
2694 : : }
2695 : : }
2696 [ + + + - ]: 4094 : if (yp2 && jl_is_typevar(yp2)) {
2697 : 3327 : jl_varbinding_t *yb = lookup(e, (jl_tvar_t*)yp2);
2698 [ + - ]: 3327 : if (yb) yb->intvalued = 1;
2699 [ + + ]: 3327 : if (!xp2) {
2700 : 1392 : i2 = bound_var_below((jl_tvar_t*)yp2, yb, e);
2701 : : }
2702 : : }
2703 [ + + + + ]: 4094 : if (xp2 && yp2) {
2704 : : // Vararg{T,N} <: Vararg{T2,N2}; equate N and N2
2705 : 1935 : i2 = intersect_invariant(xp2, yp2, e);
2706 [ + - + - : 1935 : if (i2 == NULL || i2 == jl_bottom_type || (jl_is_long(i2) && jl_unbox_long(i2) < 0) ||
+ + + - ]
2707 [ + + + - ]: 1935 : !((jl_is_typevar(i2) && ((jl_tvar_t*)i2)->lb == jl_bottom_type &&
2708 [ - + - + ]: 1935 : ((jl_tvar_t*)i2)->ub == (jl_value_t*)jl_any_type) || jl_is_long(i2))) {
2709 : 0 : i2 = jl_bottom_type;
2710 : : }
2711 : : }
2712 [ + + ]: 4094 : ii = i2 == jl_bottom_type ? (jl_value_t*)jl_bottom_type : (jl_value_t*)jl_wrap_vararg(ii, i2);
2713 : 4094 : JL_GC_POP();
2714 : 4094 : return ii;
2715 : : }
2716 : :
2717 : :
2718 : 3863000 : static jl_value_t *intersect_tuple(jl_datatype_t *xd, jl_datatype_t *yd, jl_stenv_t *e, int param)
2719 : : {
2720 : 3863000 : size_t lx = jl_nparams(xd), ly = jl_nparams(yd);
2721 [ + + - + ]: 3863000 : if (lx == 0 && ly == 0)
2722 : 0 : return (jl_value_t*)yd;
2723 [ + + + + ]: 3863000 : int vx=0, vy=0, vvx = (lx > 0 && jl_is_vararg(jl_tparam(xd, lx-1)));
2724 [ + + + + ]: 3863000 : int vvy = (ly > 0 && jl_is_vararg(jl_tparam(yd, ly-1)));
2725 [ + + + + : 3863000 : if (!vvx && !vvy && lx != ly)
+ + ]
2726 : 163 : return jl_bottom_type;
2727 : 3862830 : jl_svec_t *params = jl_alloc_svec(lx > ly ? lx : ly);
2728 : 3862830 : jl_value_t *res=NULL;
2729 : 3862830 : JL_GC_PUSH1(¶ms);
2730 : 3862830 : size_t i=0, j=0;
2731 : : jl_value_t *xi, *yi;
2732 : 6722860 : while (1) {
2733 : 10585700 : vx = vy = 0;
2734 [ + + ]: 10585700 : xi = i < lx ? jl_tparam(xd, i) : NULL;
2735 [ + + ]: 10585700 : yi = j < ly ? jl_tparam(yd, j) : NULL;
2736 [ + + + + ]: 10585700 : if (xi == NULL && yi == NULL) {
2737 [ + - + - ]: 711598 : assert(i == j && i == jl_svec_len(params));
2738 : 711598 : break;
2739 : : }
2740 [ + + + + ]: 9874090 : if (xi && jl_is_vararg(xi)) vx = 1;
2741 [ + + + + ]: 9874090 : if (yi && jl_is_vararg(yi)) vy = 1;
2742 [ + + + + ]: 9874090 : if (xi == NULL || yi == NULL) {
2743 : 98540 : res = jl_bottom_type;
2744 [ + + + + ]: 98540 : if (vx && intersect_vararg_length(xi, ly+1-lx, e, 0))
2745 : 27382 : res = (jl_value_t*)jl_apply_tuple_type_v(jl_svec_data(params), j);
2746 [ + + + + ]: 98540 : if (vy && intersect_vararg_length(yi, lx+1-ly, e, 1))
2747 : 42934 : res = (jl_value_t*)jl_apply_tuple_type_v(jl_svec_data(params), i);
2748 : 98540 : break;
2749 : : }
2750 : 9775550 : jl_varbinding_t *xb=NULL, *yb=NULL;
2751 : 9775550 : jl_value_t *ii = NULL;
2752 [ + + + + ]: 9783480 : if (vx && vy) {
2753 : : // {A^n...,Vararg{T,N}} ∩ {Vararg{S,M}} = {(A∩S)^n...,Vararg{T∩S,N}} plus N = M-n
2754 : 7931 : jl_value_t *xlen = jl_unwrap_vararg_num(xi);
2755 [ + + + - ]: 7931 : if (xlen && jl_is_typevar(xlen)) {
2756 : 3301 : xb = lookup(e, (jl_tvar_t*)xlen);
2757 [ + - ]: 3301 : if (xb)
2758 : 3301 : xb->offset = ly-lx;
2759 : : }
2760 : 7931 : jl_value_t *ylen = jl_unwrap_vararg_num(yi);
2761 [ + + + - ]: 7931 : if (ylen && jl_is_typevar(ylen)) {
2762 : 3979 : yb = lookup(e, (jl_tvar_t*)ylen);
2763 [ + - ]: 3979 : if (yb)
2764 : 3979 : yb->offset = lx-ly;
2765 : : }
2766 : 7931 : ii = intersect_varargs((jl_vararg_t*)xi,
2767 : : (jl_vararg_t*)yi,
2768 : : e, param);
2769 [ + + ]: 7931 : if (xb) xb->offset = 0;
2770 [ + + ]: 7931 : if (yb) yb->offset = 0;
2771 : : } else {
2772 [ + + ]: 9767620 : if (vx)
2773 : 43580 : xi = jl_unwrap_vararg(xi);
2774 [ + + ]: 9767620 : if (vy)
2775 : 66259 : yi = jl_unwrap_vararg(yi);
2776 [ + + ]: 9767620 : ii = intersect(xi, yi, e, param == 0 ? 1 : param);
2777 : : }
2778 [ + + ]: 9775550 : if (ii == jl_bottom_type) {
2779 [ + + + + ]: 3049790 : if (vx && vy) {
2780 : 2513 : int len = i > j ? i : j;
2781 [ + + + + : 2513 : if ((xb && jl_is_long(xb->lb) && lx-1+jl_unbox_long(xb->lb) != len) ||
+ - + + ]
2782 [ + + - + ]: 1034 : (yb && jl_is_long(yb->lb) && ly-1+jl_unbox_long(yb->lb) != len)) {
2783 : 0 : res = jl_bottom_type;
2784 : : }
2785 [ + + - + ]: 2513 : else if (param == 2 && jl_is_unionall(xi) != jl_is_unionall(yi)) {
2786 : 0 : res = jl_bottom_type;
2787 : : }
2788 : : else {
2789 [ + + ]: 2513 : if (xb) set_var_to_const(xb, jl_box_long(len-lx+1), yb);
2790 [ + + ]: 2513 : if (yb) set_var_to_const(yb, jl_box_long(len-ly+1), xb);
2791 : 2513 : res = (jl_value_t*)jl_apply_tuple_type_v(jl_svec_data(params), len);
2792 : : }
2793 : : }
2794 : : else {
2795 : 3044760 : res = jl_bottom_type;
2796 : : }
2797 : 3047280 : break;
2798 : : }
2799 : 6728270 : jl_svecset(params, (i > j ? i : j), ii);
2800 [ + + + + ]: 6728270 : if (vx && vy)
2801 : 5418 : break;
2802 [ + + + + ]: 6722860 : if (i < lx-1 || !vx) i++;
2803 [ + + + + ]: 6722860 : if (j < ly-1 || !vy) j++;
2804 : : }
2805 : : // TODO: handle Vararg with explicit integer length parameter
2806 [ + + ]: 3862830 : if (res == NULL)
2807 : 717016 : res = (jl_value_t*)jl_apply_tuple_type(params);
2808 : 3862830 : JL_GC_POP();
2809 : 3862830 : return res;
2810 : : }
2811 : :
2812 : 990310 : static void flip_vars(jl_stenv_t *e)
2813 : : {
2814 : 990310 : jl_varbinding_t *btemp = e->vars;
2815 [ + + ]: 4183020 : while (btemp != NULL) {
2816 : 3192710 : btemp->right = !btemp->right;
2817 : 3192710 : btemp = btemp->prev;
2818 : : }
2819 : 990310 : }
2820 : :
2821 : : // intersection where xd nominally inherits from yd
2822 : 283553 : 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 [ + + ]: 283553 : jl_value_t *isuper = R ? intersect((jl_value_t*)yd, (jl_value_t*)xd->super, e, param) :
2825 : 64472 : intersect((jl_value_t*)xd->super, (jl_value_t*)yd, e, param);
2826 [ + + ]: 283553 : if (isuper == jl_bottom_type) return jl_bottom_type;
2827 [ + + + + : 245371 : if (jl_nparams(xd) == 0 || jl_nparams(xd->super) == 0 || !jl_has_free_typevars((jl_value_t*)xd))
+ + ]
2828 : 17911 : return (jl_value_t*)xd;
2829 : 227460 : jl_value_t *super_pattern=NULL;
2830 : 227460 : JL_GC_PUSH2(&isuper, &super_pattern);
2831 : 227460 : jl_value_t *wrapper = xd->name->wrapper;
2832 : 227460 : super_pattern = jl_rewrap_unionall((jl_value_t*)((jl_datatype_t*)jl_unwrap_unionall(wrapper))->super,
2833 : : wrapper);
2834 : 227460 : int envsz = jl_subtype_env_size(super_pattern);
2835 : 227460 : jl_value_t *ii = jl_bottom_type;
2836 : : {
2837 : : jl_value_t **env;
2838 : 227460 : JL_GC_PUSHARGS(env, envsz);
2839 : : jl_stenv_t tempe;
2840 : 227460 : init_stenv(&tempe, env, envsz);
2841 : 227460 : tempe.ignore_free = 1;
2842 [ + + ]: 227460 : if (subtype_in_env(isuper, super_pattern, &tempe)) {
2843 : 227450 : jl_value_t *wr = wrapper;
2844 : : int i;
2845 [ + + ]: 866319 : 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 : 638869 : jl_value_t *ei = env[i];
2850 [ + + ]: 638869 : if (ei == (jl_value_t*)((jl_unionall_t*)wr)->var ||
2851 [ + + + + ]: 387930 : (jl_is_typevar(ei) && lookup(e, (jl_tvar_t*)ei) == NULL))
2852 : 268779 : env[i] = jl_tparam(xd,i);
2853 : 638869 : wr = ((jl_unionall_t*)wr)->body;
2854 : : }
2855 [ + - + + ]: 454900 : JL_TRY {
2856 : 227450 : ii = jl_apply_type(wrapper, env, envsz);
2857 : : }
2858 [ # # ]: 0 : JL_CATCH {
2859 : 0 : ii = jl_bottom_type;
2860 : : }
2861 : : }
2862 : 227460 : JL_GC_POP();
2863 : : }
2864 : 227460 : JL_GC_POP();
2865 : 227460 : return ii;
2866 : : }
2867 : :
2868 : 3219930 : static jl_value_t *intersect_invariant(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
2869 : : {
2870 [ + + + + ]: 3219930 : if (!jl_has_free_typevars(x) && !jl_has_free_typevars(y)) {
2871 [ + + + + ]: 331028 : return (jl_subtype(x,y) && jl_subtype(y,x)) ? y : NULL;
2872 : : }
2873 : 2888900 : e->invdepth++;
2874 : 2888900 : e->Rinvdepth++;
2875 : 2888900 : jl_value_t *ii = intersect(x, y, e, 2);
2876 : 2888900 : e->invdepth--;
2877 : 2888900 : e->Rinvdepth--;
2878 [ + + + + : 2888900 : if (jl_is_typevar(x) && jl_is_typevar(y) && (jl_is_typevar(ii) || !jl_is_type(ii)))
+ + + + ]
2879 : 1056320 : return ii;
2880 [ + + ]: 1832580 : if (ii == jl_bottom_type) {
2881 [ + + ]: 1191390 : if (!subtype_in_env(x, jl_bottom_type, e))
2882 : 1013720 : return NULL;
2883 : 177672 : flip_vars(e);
2884 [ + + ]: 177672 : if (!subtype_in_env(y, jl_bottom_type, e)) {
2885 : 148736 : flip_vars(e);
2886 : 148736 : return NULL;
2887 : : }
2888 : 28936 : flip_vars(e);
2889 : 28936 : return jl_bottom_type;
2890 : : }
2891 : 641194 : jl_value_t *root=NULL;
2892 : : jl_savedenv_t se;
2893 : 641194 : JL_GC_PUSH2(&ii, &root);
2894 : 641194 : save_env(e, &root, &se);
2895 [ + + ]: 641194 : if (!subtype_in_env_existential(x, y, e, 0, e->invdepth)) {
2896 : 31758 : ii = NULL;
2897 : : }
2898 : : else {
2899 [ + + ]: 609436 : if (!subtype_in_env_existential(y, x, e, 0, e->invdepth))
2900 : 35696 : ii = NULL;
2901 : : }
2902 : 641194 : restore_env(e, root, &se);
2903 : 641194 : free_env(&se);
2904 : 641194 : JL_GC_POP();
2905 : 641194 : return ii;
2906 : : }
2907 : :
2908 : : // intersection where x == Type{...} and y is not
2909 : 75236 : static jl_value_t *intersect_type_type(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int8_t R)
2910 : : {
2911 : 75236 : jl_value_t *p0 = jl_tparam0(x);
2912 [ + + ]: 75236 : if (!jl_is_typevar(p0))
2913 [ + + ]: 20487 : return (jl_typeof(p0) == y) ? x : jl_bottom_type;
2914 [ + + ]: 54749 : if (!jl_is_kind(y)) return jl_bottom_type;
2915 [ + + + - ]: 1077 : if (y == (jl_value_t*)jl_typeofbottom_type && ((jl_tvar_t*)p0)->lb == jl_bottom_type)
2916 : 102 : return (jl_value_t*)jl_wrap_Type(jl_bottom_type);
2917 [ + + ]: 975 : if (((jl_tvar_t*)p0)->ub == (jl_value_t*)jl_any_type)
2918 : 289 : return y;
2919 : 686 : 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 : 54338 : static int compareto_var(jl_value_t *x, jl_tvar_t *y, jl_stenv_t *e, int cmp) JL_NOTSAFEPOINT
2933 : : {
2934 [ - + ]: 54338 : if (x == (jl_value_t*)y)
2935 : 0 : return 1;
2936 [ + + ]: 54338 : if (!jl_is_typevar(x))
2937 : 27122 : return 0;
2938 : 27216 : jl_varbinding_t *xv = lookup(e, (jl_tvar_t*)x);
2939 [ + + ]: 27216 : if (xv == NULL)
2940 : 94 : return 0;
2941 : 27122 : int ans = 1;
2942 [ + + ]: 27122 : if (cmp <= 0)
2943 : 13514 : ans &= compareto_var(xv->ub, y, e, cmp);
2944 [ + + ]: 27122 : if (cmp >= 0)
2945 : 13608 : ans &= compareto_var(xv->lb, y, e, cmp);
2946 : 27122 : 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 : 1248890 : static int subtype_by_bounds(jl_value_t *x, jl_value_t *y, jl_stenv_t *e) JL_NOTSAFEPOINT
2953 : : {
2954 [ + + - + ]: 1248890 : if (!jl_is_typevar(x) || !jl_is_typevar(y))
2955 : 1235280 : return 0;
2956 [ + - - + ]: 13608 : 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 : 38005300 : static jl_value_t *intersect(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param)
2964 : : {
2965 [ + + ]: 38005300 : if (x == y) return y;
2966 [ + + ]: 33080600 : if (jl_is_typevar(x)) {
2967 [ + + ]: 2331480 : if (jl_is_typevar(y)) {
2968 : 1212380 : jl_varbinding_t *xx = lookup(e, (jl_tvar_t*)x);
2969 : 1212380 : jl_varbinding_t *yy = lookup(e, (jl_tvar_t*)y);
2970 : 1212380 : int R = 0;
2971 [ + + + + : 1212380 : 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 : 915106 : temp = x; x = y; y = temp;
2977 : 915106 : tvb = xx; xx = yy; yy = tvb;
2978 : 915106 : R = 1;
2979 : : }
2980 [ + + ]: 1212380 : if (param == 2) {
2981 [ + + ]: 1206020 : jl_value_t *xlb = xx ? xx->lb : ((jl_tvar_t*)x)->lb;
2982 [ + + ]: 1206020 : jl_value_t *xub = xx ? xx->ub : ((jl_tvar_t*)x)->ub;
2983 [ + + ]: 1206020 : jl_value_t *ylb = yy ? yy->lb : ((jl_tvar_t*)y)->lb;
2984 [ + + ]: 1206020 : jl_value_t *yub = yy ? yy->ub : ((jl_tvar_t*)y)->ub;
2985 : 1206020 : record_var_occurrence(xx, e, param);
2986 [ + + + + : 1206020 : if (xx && yy && xx->depth0 != yy->depth0) {
+ + ]
2987 : 30872 : record_var_occurrence(yy, e, param);
2988 [ - + ]: 30872 : return subtype_in_env(yy->ub, yy->lb, e) ? y : jl_bottom_type;
2989 : : }
2990 [ + + + + ]: 1175150 : if (xub == xlb && jl_is_typevar(xub)) {
2991 [ + + ]: 143951 : if (y == xub) {
2992 : 143743 : record_var_occurrence(yy, e, param);
2993 : 143743 : return y;
2994 : : }
2995 : 208 : return intersect(y, xub, e, param);
2996 : : }
2997 : 1031200 : record_var_occurrence(yy, e, param);
2998 [ + + + + ]: 1031200 : if (!jl_is_type(ylb) && !jl_is_typevar(ylb)) {
2999 [ + - ]: 19888 : if (xx)
3000 : 19888 : 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 [ + + + + ]: 1011310 : if (!jl_is_type(xlb) && !jl_is_typevar(xlb)) {
3006 [ + - ]: 7 : if (yy)
3007 : 7 : 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 [ + + ]: 1011300 : if (yub == xub ||
3014 [ - + - - ]: 462184 : (subtype_by_bounds(xlb, yub, e) && subtype_by_bounds(ylb, xub, e))) {
3015 : 549118 : ccheck = 1;
3016 : : }
3017 : : else {
3018 [ + + ]: 462184 : if (R) flip_vars(e);
3019 [ + + + + ]: 462184 : ccheck = subtype_in_env(xlb, yub, e) && subtype_in_env(ylb, xub, e);
3020 [ + + ]: 462184 : if (R) flip_vars(e);
3021 : : }
3022 [ + + ]: 1011300 : if (!ccheck)
3023 : 127816 : return jl_bottom_type;
3024 [ - + - - ]: 883486 : 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 : 883486 : jl_value_t *ub=NULL, *lb=NULL;
3030 : 883486 : JL_GC_PUSH2(&lb, &ub);
3031 [ + + ]: 883486 : ub = intersect_aside(xub, yub, e, 0, xx ? xx->depth0 : 0);
3032 [ + + ]: 883486 : if (reachable_var(xlb, (jl_tvar_t*)y, e))
3033 : 56 : lb = ylb;
3034 : : else
3035 : 883430 : lb = simple_join(xlb, ylb);
3036 [ + + ]: 883486 : if (yy) {
3037 : 883040 : yy->lb = lb;
3038 [ + - ]: 883040 : if (!reachable_var(ub, (jl_tvar_t*)y, e))
3039 : 883040 : yy->ub = ub;
3040 [ - + ]: 883040 : assert(yy->ub != y);
3041 [ - + ]: 883040 : assert(yy->lb != y);
3042 : : }
3043 [ + + + - ]: 883486 : if (xx && !reachable_var(y, (jl_tvar_t*)x, e)) {
3044 : 883354 : xx->lb = y;
3045 : 883354 : xx->ub = y;
3046 [ - + ]: 883354 : assert(xx->ub != x);
3047 : : }
3048 : 883486 : JL_GC_POP();
3049 : 883486 : return y;
3050 : : }
3051 : 6356 : record_var_occurrence(xx, e, param);
3052 : 6356 : record_var_occurrence(yy, e, param);
3053 [ + - + - : 6356 : if (xx && yy && xx->concrete && !yy->concrete) {
+ + + + ]
3054 : 164 : return intersect_var((jl_tvar_t*)x, y, e, R, param);
3055 : : }
3056 : 6192 : return intersect_var((jl_tvar_t*)y, x, e, !R, param);
3057 : : }
3058 : 1119100 : record_var_occurrence(lookup(e, (jl_tvar_t*)x), e, param);
3059 : 1119100 : return intersect_var((jl_tvar_t*)x, y, e, 0, param);
3060 : : }
3061 [ + + ]: 30749200 : if (jl_is_typevar(y)) {
3062 : 1342810 : record_var_occurrence(lookup(e, (jl_tvar_t*)y), e, param);
3063 : 1342810 : return intersect_var((jl_tvar_t*)y, x, e, 1, param);
3064 : : }
3065 [ + + + + ]: 29406300 : if (!jl_has_free_typevars(x) && !jl_has_free_typevars(y)) {
3066 [ + + ]: 13617200 : if (jl_subtype(x, y)) return x;
3067 [ + + ]: 12987000 : if (jl_subtype(y, x)) return y;
3068 : : }
3069 [ + + ]: 28270300 : if (jl_is_uniontype(x)) {
3070 [ + - - + ]: 3375000 : if (y == ((jl_uniontype_t*)x)->a || y == ((jl_uniontype_t*)x)->b)
3071 : 0 : return y;
3072 : 3375000 : return intersect_union(y, (jl_uniontype_t*)x, e, 0, param);
3073 : : }
3074 [ + + ]: 24895300 : if (jl_is_uniontype(y)) {
3075 [ + + + + ]: 1798600 : if (x == ((jl_uniontype_t*)y)->a || x == ((jl_uniontype_t*)y)->b)
3076 : 357 : return x;
3077 [ + + + + : 1798240 : if (jl_is_unionall(x) && (jl_has_free_typevars(x) || jl_has_free_typevars(y)))
+ + ]
3078 : 489130 : return intersect_unionall(y, (jl_unionall_t*)x, e, 0, param);
3079 : 1309120 : return intersect_union(x, (jl_uniontype_t*)y, e, 1, param);
3080 : : }
3081 [ + + ]: 23096700 : if (y == (jl_value_t*)jl_any_type) return x;
3082 [ + + ]: 23071500 : if (x == (jl_value_t*)jl_any_type) return y;
3083 [ + + ]: 23028800 : if (jl_is_unionall(x)) {
3084 [ + + ]: 4040350 : if (jl_is_unionall(y)) {
3085 : 1910620 : jl_value_t *a=NULL, *b=jl_bottom_type, *res=NULL;
3086 : 1910620 : JL_GC_PUSH2(&a,&b);
3087 : : jl_savedenv_t se;
3088 : 1910620 : save_env(e, NULL, &se);
3089 : 1910620 : a = intersect_unionall(y, (jl_unionall_t*)x, e, 0, param);
3090 [ + + ]: 1910620 : if (jl_is_unionall(a)) {
3091 : 283277 : jl_unionall_t *ua = (jl_unionall_t*)a;
3092 [ + + ]: 283277 : if (jl_is_unionall(ua->body)) {
3093 : 72821 : jl_unionall_t *ub = (jl_unionall_t*)ua->body;
3094 [ + + ]: 72821 : if (jl_has_typevar(ub->var->ub, ua->var) ||
3095 [ - + ]: 71110 : jl_has_typevar(ub->var->lb, ua->var)) {
3096 : 1711 : restore_env(e, NULL, &se); // restore counts
3097 : 1711 : b = intersect_unionall(x, (jl_unionall_t*)y, e, 1, param);
3098 : : }
3099 : : }
3100 : : }
3101 : 1910620 : free_env(&se);
3102 [ + + + - ]: 1910620 : if (!jl_has_free_typevars(a) && !jl_has_free_typevars(b)) {
3103 [ + + ]: 1681390 : if (jl_subtype(a, b))
3104 : 1514750 : res = b;
3105 [ + - ]: 166639 : else if (jl_subtype(b, a))
3106 : 166639 : res = a;
3107 : : }
3108 [ + + ]: 1910620 : if (!res) res = simple_join(a, b);
3109 : 1910620 : JL_GC_POP();
3110 : 1910620 : return res;
3111 : : }
3112 : 2129730 : return intersect_unionall(y, (jl_unionall_t*)x, e, 0, param);
3113 : : }
3114 [ + + ]: 18988400 : if (jl_is_unionall(y))
3115 : 6437350 : return intersect_unionall(x, (jl_unionall_t*)y, e, 1, param);
3116 [ + + + + ]: 12551100 : if (jl_is_datatype(x) && jl_is_datatype(y)) {
3117 : 12551000 : jl_datatype_t *xd = (jl_datatype_t*)x, *yd = (jl_datatype_t*)y;
3118 [ + + ]: 12551000 : if (param < 2) {
3119 [ + + ]: 12475200 : if (jl_is_type_type(x)) {
3120 [ + + ]: 1801620 : if (!jl_is_type_type(y))
3121 : 33326 : return intersect_type_type(x, y, e, 0);
3122 : : }
3123 [ + + ]: 10673600 : else if (jl_is_type_type(y)) {
3124 : 41910 : return intersect_type_type(y, x, e, 1);
3125 : : }
3126 : : }
3127 [ + + ]: 12475700 : if (xd->name == yd->name) {
3128 [ + + ]: 6322670 : if (jl_is_tuple_type(xd))
3129 : 3863000 : return intersect_tuple(xd, yd, e, param);
3130 : 2459670 : size_t i, np = jl_nparams(xd);
3131 : : jl_value_t **newparams;
3132 : 2459670 : JL_GC_PUSHARGS(newparams, np);
3133 [ + + ]: 4304900 : for (i=0; i < np; i++) {
3134 : 3218000 : jl_value_t *xi = jl_tparam(xd, i), *yi = jl_tparam(yd, i);
3135 : 3218000 : jl_value_t *ii = intersect_invariant(xi, yi, e);
3136 [ + + ]: 3218000 : if (ii == NULL)
3137 : 1372770 : break;
3138 : 1845230 : newparams[i] = ii;
3139 : : }
3140 : 2459670 : jl_value_t *res = jl_bottom_type;
3141 [ + + ]: 2459670 : if (i >= np) {
3142 [ + + + + ]: 2169690 : JL_TRY {
3143 : 1086900 : res = jl_apply_type(xd->name->wrapper, newparams, np);
3144 : : }
3145 [ + + ]: 8240 : JL_CATCH {
3146 : 4120 : res = jl_bottom_type;
3147 : : }
3148 : : }
3149 : 2459670 : JL_GC_POP();
3150 : 2459670 : return res;
3151 : : }
3152 [ + + ]: 6153080 : if (param == 2) return jl_bottom_type;
3153 [ + + + + ]: 18546400 : while (xd != jl_any_type && xd->name != yd->name)
3154 : 12405300 : xd = xd->super;
3155 [ + + ]: 6141110 : if (xd == jl_any_type) {
3156 : 6076640 : xd = (jl_datatype_t*)x;
3157 [ + + + + ]: 18829900 : while (yd != jl_any_type && yd->name != xd->name)
3158 : 12753200 : yd = yd->super;
3159 [ + + ]: 6076640 : if (yd == jl_any_type)
3160 : 5857560 : return jl_bottom_type;
3161 : 219081 : return intersect_sub_datatype((jl_datatype_t*)y, xd, e, 1, param);
3162 : : }
3163 : 64472 : return intersect_sub_datatype((jl_datatype_t*)x, yd, e, 0, param);
3164 : : }
3165 [ - + ]: 104 : if (jl_egal(x, y)) return y;
3166 : 104 : return jl_bottom_type;
3167 : : }
3168 : :
3169 : 11986700 : static jl_value_t *intersect_all(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
3170 : : {
3171 : 11986700 : e->Runions.depth = 0;
3172 : 11986700 : e->Runions.more = 0;
3173 : 11986700 : e->Runions.used = 0;
3174 : : jl_value_t **is;
3175 : 11986700 : JL_GC_PUSHARGS(is, 3);
3176 : 11986700 : jl_value_t **saved = &is[2];
3177 : : jl_savedenv_t se;
3178 : 11986700 : save_env(e, saved, &se);
3179 : 11986700 : int lastset = 0, niter = 0, total_iter = 0;
3180 : 11986700 : jl_value_t *ii = intersect(x, y, e, 0);
3181 : 11986700 : is[0] = ii; // root
3182 [ + + ]: 11986700 : if (ii == jl_bottom_type) {
3183 : 10794200 : restore_env(e, *saved, &se);
3184 : : }
3185 : : else {
3186 : 1192420 : free_env(&se);
3187 : 1192420 : save_env(e, saved, &se);
3188 : : }
3189 [ + + ]: 12585700 : while (e->Runions.more) {
3190 [ + + + + ]: 601429 : if (e->emptiness_only && ii != jl_bottom_type)
3191 : 218 : break;
3192 : 601211 : e->Runions.depth = 0;
3193 : 601211 : int set = e->Runions.more - 1;
3194 : 601211 : e->Runions.more = 0;
3195 : 601211 : statestack_set(&e->Runions, set, 1);
3196 [ + + ]: 733294 : for (int i = set + 1; i <= lastset; i++)
3197 : 132083 : statestack_set(&e->Runions, i, 0);
3198 : 601211 : lastset = set;
3199 : :
3200 : 601211 : is[0] = ii;
3201 : 601211 : is[1] = intersect(x, y, e, 0);
3202 [ + + ]: 601211 : if (is[1] == jl_bottom_type) {
3203 : 577744 : restore_env(e, *saved, &se);
3204 : : }
3205 : : else {
3206 : 23467 : free_env(&se);
3207 : 23467 : save_env(e, saved, &se);
3208 : : }
3209 [ + + ]: 601211 : if (is[0] == jl_bottom_type)
3210 : 418102 : ii = is[1];
3211 [ + + ]: 183109 : else if (is[1] == jl_bottom_type)
3212 : 160795 : ii = is[0];
3213 : : else {
3214 : : // TODO: the repeated subtype checks in here can get expensive
3215 : 22314 : ii = jl_type_union(is, 2);
3216 : 22314 : niter++;
3217 : : }
3218 : 601211 : total_iter++;
3219 [ + + - + ]: 601211 : if (niter > 3 || total_iter > 400000) {
3220 : 2191 : ii = y;
3221 : 2191 : break;
3222 : : }
3223 : : }
3224 : 11986700 : free_env(&se);
3225 : 11986700 : JL_GC_POP();
3226 : 11986700 : return ii;
3227 : : }
3228 : :
3229 : : // type intersection entry points
3230 : :
3231 : 9375650 : static jl_value_t *intersect_types(jl_value_t *x, jl_value_t *y, int emptiness_only)
3232 : : {
3233 : : jl_stenv_t e;
3234 [ + + ]: 9375650 : if (obviously_disjoint(x, y, 0))
3235 : 8040170 : return jl_bottom_type;
3236 [ + + + + ]: 1335480 : if (jl_is_dispatch_tupletype(x) || jl_is_dispatch_tupletype(y)) {
3237 [ + + ]: 135718 : if (jl_subtype(x, y))
3238 : 15602 : return x;
3239 [ + + ]: 120116 : else if (jl_subtype(y, x))
3240 : 5922 : return y;
3241 : : else
3242 : 114194 : return jl_bottom_type;
3243 : : }
3244 : 1199770 : init_stenv(&e, NULL, 0);
3245 : 1199770 : e.intersection = e.ignore_free = 1;
3246 : 1199770 : e.emptiness_only = emptiness_only;
3247 : 1199770 : return intersect_all(x, y, &e);
3248 : : }
3249 : :
3250 : 0 : JL_DLLEXPORT jl_value_t *jl_intersect_types(jl_value_t *x, jl_value_t *y)
3251 : : {
3252 : 0 : return intersect_types(x, y, 0);
3253 : : }
3254 : :
3255 : : // TODO: this can probably be done more efficiently
3256 : 9375650 : JL_DLLEXPORT int jl_has_empty_intersection(jl_value_t *x, jl_value_t *y)
3257 : : {
3258 : 9375650 : 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 : 118966 : jl_svec_t *jl_outer_unionall_vars(jl_value_t *u)
3263 : : {
3264 : 118966 : int ntvars = jl_subtype_env_size((jl_value_t*)u);
3265 : 118966 : jl_svec_t *vec = jl_alloc_svec_uninit(ntvars);
3266 : 118966 : jl_unionall_t *ua = (jl_unionall_t*)u;
3267 : : int i;
3268 [ + + ]: 136892 : for (i = 0; i < ntvars; i++) {
3269 [ - + ]: 17926 : assert(jl_is_unionall(ua));
3270 : 17926 : jl_svecset(vec, i, ua->var);
3271 : 17926 : ua = (jl_unionall_t*)ua->body;
3272 : : }
3273 : 118966 : 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 : 8904 : static jl_value_t *switch_union_tuple(jl_value_t *a, jl_value_t *b)
3281 : : {
3282 [ + + ]: 8904 : if (jl_is_unionall(a)) {
3283 : 2773 : jl_unionall_t *ua = (jl_unionall_t*)a;
3284 [ + + ]: 2773 : if (jl_is_unionall(b)) {
3285 : 1425 : jl_unionall_t *ub = (jl_unionall_t*)b;
3286 [ + - + + ]: 1425 : if (ub->var->lb == ua->var->lb && ub->var->ub == ua->var->ub) {
3287 : 1419 : jl_value_t *ub2 = jl_instantiate_unionall(ub, (jl_value_t*)ua->var);
3288 : 1419 : jl_value_t *ans = NULL;
3289 : 1419 : JL_GC_PUSH2(&ub2, &ans);
3290 : 1419 : ans = switch_union_tuple(ua->body, ub2);
3291 [ + - ]: 1419 : if (ans != NULL)
3292 : 1419 : ans = jl_type_unionall(ua->var, ans);
3293 : 1419 : JL_GC_POP();
3294 : 1419 : return ans;
3295 : : }
3296 : : }
3297 : 1354 : jl_value_t *ans = switch_union_tuple(ua->body, b);
3298 [ - + ]: 1354 : if (ans == NULL)
3299 : 0 : return NULL;
3300 : 1354 : JL_GC_PUSH1(&ans);
3301 : 1354 : ans = jl_type_unionall(ua->var, ans);
3302 : 1354 : JL_GC_POP();
3303 : 1354 : return ans;
3304 : : }
3305 [ + + ]: 6131 : if (jl_is_unionall(b)) {
3306 : 1380 : jl_value_t *ans = switch_union_tuple(a, ((jl_unionall_t*)b)->body);
3307 [ - + ]: 1380 : if (ans == NULL)
3308 : 0 : return NULL;
3309 : 1380 : JL_GC_PUSH1(&ans);
3310 : 1380 : ans = jl_type_unionall(((jl_unionall_t*)b)->var, ans);
3311 : 1380 : JL_GC_POP();
3312 : 1380 : return ans;
3313 : : }
3314 [ - + ]: 4751 : 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 [ + + ]: 4751 : if (jl_is_uniontype(b)) {
3324 : 1588 : b = switch_union_tuple(((jl_uniontype_t*)b)->a, ((jl_uniontype_t*)b)->b);
3325 [ - + ]: 1588 : if (b == NULL)
3326 : 0 : return NULL;
3327 : 1588 : JL_GC_PUSH1(&b);
3328 : 1588 : jl_value_t *ans = switch_union_tuple(a, b);
3329 : 1588 : JL_GC_POP();
3330 : 1588 : return ans;
3331 : : }
3332 [ + - - + ]: 3163 : if (!jl_is_tuple_type(a) || !jl_is_tuple_type(b)) {
3333 : 0 : return NULL;
3334 : : }
3335 [ + - + - : 6326 : if (jl_nparams(a) != jl_nparams(b) || jl_is_va_tuple((jl_datatype_t*)a) ||
- + ]
3336 : 3163 : jl_is_va_tuple((jl_datatype_t*)b)) {
3337 : 0 : return NULL;
3338 : : }
3339 : 3163 : jl_svec_t *vec = jl_alloc_svec(jl_nparams(a));
3340 : 3163 : JL_GC_PUSH1(&vec);
3341 [ + + ]: 13559 : for (int i = 0; i < jl_nparams(a); i++) {
3342 : : jl_value_t *ts[2];
3343 : 10396 : ts[0] = jl_tparam(a, i);
3344 : 10396 : ts[1] = jl_tparam(b, i);
3345 : 10396 : jl_svecset(vec, i, jl_type_union(ts, 2));
3346 : : }
3347 : 3163 : jl_value_t *ans = (jl_value_t*)jl_apply_tuple_type(vec);
3348 : 3163 : JL_GC_POP();
3349 : 3163 : 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 : 2479040 : static int might_intersect_concrete(jl_value_t *a)
3355 : : {
3356 [ + + ]: 2479040 : if (jl_is_unionall(a))
3357 : 171516 : a = jl_unwrap_unionall(a);
3358 [ + + ]: 2479040 : if (jl_is_typevar(a))
3359 : 66 : return 1; // (maybe)
3360 [ + + ]: 2478980 : if (jl_is_uniontype(a))
3361 [ + + + + ]: 1373010 : return might_intersect_concrete(((jl_uniontype_t*)a)->a) ||
3362 : 654169 : might_intersect_concrete(((jl_uniontype_t*)a)->b);
3363 [ + + ]: 1760140 : if (jl_is_vararg(a))
3364 : 12926 : return might_intersect_concrete(jl_unwrap_vararg(a));
3365 [ + + ]: 1747220 : if (jl_is_type_type(a))
3366 : 2835 : return 1;
3367 [ + - ]: 1744380 : if (jl_is_datatype(a)) {
3368 : 1744380 : int tpl = jl_is_tuple_type(a);
3369 : 1744380 : int i, n = jl_nparams(a);
3370 [ + + ]: 2662950 : for (i = 0; i < n; i++) {
3371 : 1160410 : jl_value_t *p = jl_tparam(a, i);
3372 [ + + ]: 1160410 : if (jl_is_typevar(p))
3373 : 160620 : return 1;
3374 [ + + - + ]: 999793 : if (tpl && p == jl_bottom_type)
3375 : 0 : return 1;
3376 [ + + + + ]: 999793 : if (tpl && might_intersect_concrete(p))
3377 : 81227 : return 1;
3378 : : }
3379 : : }
3380 : 1502530 : return 0;
3381 : : }
3382 : :
3383 : : // sets *issubty to 1 iff `a` is a subtype of `b`
3384 : 18562000 : jl_value_t *jl_type_intersection_env_s(jl_value_t *a, jl_value_t *b, jl_svec_t **penv, int *issubty)
3385 : : {
3386 [ + + ]: 18562000 : if (issubty) *issubty = 0;
3387 [ + + ]: 18562000 : if (obviously_disjoint(a, b, 0)) {
3388 [ + + - + ]: 13293600 : if (issubty && a == jl_bottom_type) *issubty = 1;
3389 : 13293600 : return jl_bottom_type;
3390 : : }
3391 : 5268400 : int szb = jl_subtype_env_size(b);
3392 : 5268400 : int sz = 0, i = 0;
3393 : : jl_value_t **env, **ans;
3394 : 5268400 : JL_GC_PUSHARGS(env, szb+1);
3395 : 5268400 : ans = &env[szb];
3396 : 5268400 : *ans = jl_bottom_type;
3397 : 5268400 : int lta = jl_is_concrete_type(a);
3398 : 5268400 : int ltb = jl_is_concrete_type(b);
3399 [ + + ]: 5268400 : if (jl_subtype_env(a, b, env, szb)) {
3400 : 2223320 : *ans = a; sz = szb;
3401 [ + + ]: 2223320 : if (issubty) *issubty = 1;
3402 : : }
3403 [ + + + + ]: 3045080 : else if (lta && ltb) {
3404 : 8 : goto bot;
3405 : : }
3406 [ + + ]: 3045070 : else if (jl_subtype(b, a)) {
3407 : 710902 : *ans = b;
3408 : : }
3409 : : else {
3410 : : // TODO: these tests could probably be ordered better with above
3411 [ + + + + ]: 2334170 : if (lta && !might_intersect_concrete(b))
3412 : 1908190 : goto bot;
3413 [ + + + + ]: 2313180 : if (ltb && !might_intersect_concrete(a))
3414 : 111738 : goto bot;
3415 : : jl_stenv_t e;
3416 : 2201440 : init_stenv(&e, NULL, 0);
3417 : 2201440 : e.intersection = e.ignore_free = 1;
3418 : 2201440 : e.envout = env;
3419 [ + + ]: 2201440 : if (szb)
3420 : 908792 : memset(env, 0, szb*sizeof(void*));
3421 : 2201440 : e.envsz = szb;
3422 : 2201440 : *ans = intersect_all(a, b, &e);
3423 [ + + ]: 2201440 : 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 : 425976 : int env_from_subtype = 1;
3428 [ + + + + ]: 425976 : if (jl_is_tuple_type(jl_unwrap_unionall(a)) && jl_is_tuple_type(jl_unwrap_unionall(b)) &&
3429 [ + + ]: 421946 : !jl_is_datatype(jl_unwrap_unionall(*ans))) {
3430 : 1575 : jl_value_t *ans_unwrapped = jl_unwrap_unionall(*ans);
3431 : 1575 : JL_GC_PUSH1(&ans_unwrapped);
3432 [ + - ]: 1575 : if (jl_is_uniontype(ans_unwrapped)) {
3433 : 1575 : ans_unwrapped = switch_union_tuple(((jl_uniontype_t*)ans_unwrapped)->a, ((jl_uniontype_t*)ans_unwrapped)->b);
3434 [ + - ]: 1575 : if (ans_unwrapped != NULL) {
3435 : 1575 : *ans = jl_rewrap_unionall(ans_unwrapped, *ans);
3436 : : }
3437 : : }
3438 : 1575 : JL_GC_POP();
3439 [ - + ]: 1575 : if (!jl_is_datatype(jl_unwrap_unionall(*ans))) {
3440 : 0 : *ans = b;
3441 : 0 : env_from_subtype = 0;
3442 : : }
3443 : : }
3444 [ + - ]: 425976 : if (env_from_subtype) {
3445 : 425976 : 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 [ + + + + ]: 425976 : if (szb > 0 && !jl_types_equal(b, (jl_value_t*)jl_type_type)) {
3449 [ + + ]: 169387 : if (!jl_subtype_env(*ans, b, env, szb)) {
3450 : 15771 : sz = 0;
3451 : : }
3452 : : }
3453 : : }
3454 : : }
3455 [ + + + + ]: 3360190 : if (sz == 0 && szb > 0) {
3456 [ + + ]: 189319 : while (jl_is_unionall(b)) {
3457 : 100322 : env[i++] = (jl_value_t*)((jl_unionall_t*)b)->var;
3458 : 100322 : b = ((jl_unionall_t*)b)->body;
3459 : : }
3460 : 88997 : sz = szb;
3461 : : }
3462 [ + + ]: 3360190 : if (penv) {
3463 : 1065870 : jl_svec_t *e = jl_alloc_svec(sz);
3464 : 1065870 : *penv = e;
3465 [ + + ]: 1460070 : for(i=0; i < sz; i++)
3466 : 394203 : jl_svecset(e, i, env[i]);
3467 : : }
3468 : 3360190 : bot:
3469 : 5268400 : JL_GC_POP();
3470 : 5268400 : return *ans;
3471 : : }
3472 : :
3473 : 2398740 : jl_value_t *jl_type_intersection_env(jl_value_t *a, jl_value_t *b, jl_svec_t **penv)
3474 : : {
3475 : 2398740 : return jl_type_intersection_env_s(a, b, penv, NULL);
3476 : : }
3477 : :
3478 : 2369400 : JL_DLLEXPORT jl_value_t *jl_type_intersection(jl_value_t *a, jl_value_t *b)
3479 : : {
3480 : 2369400 : return jl_type_intersection_env(a, b, NULL);
3481 : : }
3482 : :
3483 : 452 : JL_DLLEXPORT jl_svec_t *jl_type_intersection_with_env(jl_value_t *a, jl_value_t *b)
3484 : : {
3485 : 452 : jl_svec_t *env = jl_emptysvec;
3486 : 452 : jl_value_t *ti = NULL;
3487 : 452 : JL_GC_PUSH2(&env, &ti);
3488 : 452 : ti = jl_type_intersection_env(a, b, &env);
3489 : 452 : jl_svec_t *pair = jl_svec2(ti, env);
3490 : 452 : JL_GC_POP();
3491 : 452 : return pair;
3492 : : }
3493 : :
3494 : 161971 : int jl_subtype_matching(jl_value_t *a, jl_value_t *b, jl_svec_t **penv)
3495 : : {
3496 [ + + ]: 161971 : int szb = penv ? jl_subtype_env_size(b) : 0;
3497 [ + - ]: 161971 : if (szb == 0)
3498 : 161971 : return jl_subtype_env(a, b, NULL, szb);
3499 : :
3500 : : jl_value_t **env;
3501 : 0 : JL_GC_PUSHARGS(env, szb);
3502 : 0 : int sub = jl_subtype_env(a, b, env, szb);
3503 [ # # ]: 0 : if (sub) {
3504 : : // copy env to svec for return
3505 : 0 : int i = 0;
3506 : 0 : jl_svec_t *e = jl_alloc_svec(szb);
3507 : 0 : *penv = e;
3508 [ # # ]: 0 : for (i = 0; i < szb; i++)
3509 : 0 : jl_svecset(e, i, env[i]);
3510 : : }
3511 : 0 : JL_GC_POP();
3512 : 0 : return sub;
3513 : : }
3514 : :
3515 : :
3516 : : // specificity comparison
3517 : :
3518 : 2997210 : static int eq_msp(jl_value_t *a, jl_value_t *b, jl_typeenv_t *env)
3519 : : {
3520 [ + + + + : 5977490 : if (!(jl_is_type(a) || jl_is_typevar(a)) ||
+ + ]
3521 [ - + ]: 4684330 : !(jl_is_type(b) || jl_is_typevar(b)))
3522 : 16930 : return jl_egal(a, b);
3523 : 2980280 : JL_GC_PUSH2(&a, &b);
3524 : 2980280 : jl_typeenv_t *e = env;
3525 [ + + ]: 13357600 : while (e != NULL) {
3526 : 10377400 : a = jl_type_unionall(e->var, a);
3527 : 10377400 : b = jl_type_unionall(e->var, b);
3528 : 10377400 : e = e->prev;
3529 : : }
3530 : 2980280 : int eq = jl_types_equal(a, b);
3531 : 2980280 : JL_GC_POP();
3532 : 2980280 : return eq;
3533 : : }
3534 : :
3535 : 5825070 : static int sub_msp(jl_value_t *a, jl_value_t *b, jl_typeenv_t *env)
3536 : : {
3537 : 5825070 : JL_GC_PUSH2(&a, &b);
3538 [ + + ]: 11362100 : while (env != NULL) {
3539 [ + + + - ]: 5537020 : if (jl_is_type(a) || jl_is_typevar(a))
3540 : 5537020 : a = jl_type_unionall(env->var, a);
3541 [ + + + - ]: 5537020 : if (jl_is_type(b) || jl_is_typevar(b))
3542 : 5537020 : b = jl_type_unionall(env->var, b);
3543 : 5537020 : env = env->prev;
3544 : : }
3545 : 5825070 : int sub = jl_subtype(a, b);
3546 : 5825070 : JL_GC_POP();
3547 : 5825070 : 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 : 9013580 : static jl_value_t *nth_tuple_elt(jl_datatype_t *t JL_PROPAGATES_ROOT, size_t i) JL_NOTSAFEPOINT
3555 : : {
3556 : 9013580 : size_t len = jl_nparams(t);
3557 [ - + ]: 9013580 : if (len == 0)
3558 : 0 : return NULL;
3559 [ + + ]: 9013580 : if (i < len-1)
3560 : 6003480 : return jl_tparam(t, i);
3561 : 3010100 : jl_value_t *last = jl_unwrap_unionall(jl_tparam(t, len-1));
3562 [ + + ]: 3010100 : if (jl_is_vararg(last)) {
3563 : 42397 : jl_value_t *n = jl_unwrap_vararg_num(last);
3564 [ + + - + : 42397 : if (n && jl_is_long(n) && i >= len-1+jl_unbox_long(n))
- - ]
3565 : 0 : return NULL;
3566 : 42397 : return jl_unwrap_vararg(last);
3567 : : }
3568 [ + + ]: 2967700 : if (i == len-1)
3569 : 2673080 : return jl_tparam(t, i);
3570 : 294627 : return NULL;
3571 : : }
3572 : :
3573 : 1866630 : static int tuple_morespecific(jl_datatype_t *cdt, jl_datatype_t *pdt, int invariant, jl_typeenv_t *env)
3574 : : {
3575 : 1866630 : size_t plen = jl_nparams(pdt);
3576 [ + + ]: 1866630 : if (plen == 0) return 0;
3577 : 1838480 : size_t clen = jl_nparams(cdt);
3578 [ + + ]: 1838480 : if (clen == 0) return 1;
3579 : 1834990 : int i = 0;
3580 : 1834990 : jl_value_t *clast = jl_tparam(cdt,clen-1);
3581 : 1834990 : jl_vararg_kind_t ckind = jl_vararg_kind(clast);
3582 : 1834990 : int cva = ckind > JL_VARARG_INT;
3583 : 1834990 : int pva = jl_vararg_kind(jl_tparam(pdt,plen-1)) > JL_VARARG_INT;
3584 : 1834990 : int cdiag = 0, pdiag = 0;
3585 : 1834990 : int some_morespecific = 0;
3586 : 2672860 : while (1) {
3587 [ + + + + : 4507850 : if (cva && pva && i >= clen && i >= plen)
+ + + + ]
3588 : 1058 : break;
3589 : :
3590 : 4506790 : jl_value_t *ce = nth_tuple_elt(cdt, i);
3591 : 4506790 : jl_value_t *pe = nth_tuple_elt(pdt, i);
3592 : :
3593 [ + + ]: 4506790 : if (ce == NULL) {
3594 [ + + ]: 145984 : if (pe == NULL) break;
3595 : 5835 : return 1;
3596 : : }
3597 [ + + ]: 4360800 : if (pe == NULL) {
3598 [ + + + + ]: 8494 : if (!cva && !some_morespecific)
3599 : 685 : return 0;
3600 : 7809 : break;
3601 : : }
3602 : :
3603 [ + + ]: 4352310 : if (type_morespecific_(pe, ce, invariant, env)) {
3604 [ - + ]: 285992 : assert(!type_morespecific_(ce, pe, invariant, env));
3605 : 285992 : return 0;
3606 : : }
3607 : :
3608 [ + + + + : 4066320 : if (!cdiag && jl_is_typevar(ce) && num_occurs((jl_tvar_t*)ce,env) > 1)
+ + ]
3609 : 50620 : cdiag = 1;
3610 [ + + + + : 4066320 : if (!pdiag && jl_is_typevar(pe) && num_occurs((jl_tvar_t*)pe,env) > 1)
+ + ]
3611 : 75802 : pdiag = 1;
3612 : :
3613 : : // in Tuple{a,b...} and Tuple{c,d...} allow b and d to be disjoint
3614 [ + + + + : 4066320 : if (cva && pva && i >= clen-1 && i >= plen-1 && (some_morespecific || (cdiag && !pdiag)))
+ + + + +
+ - + -
- ]
3615 : 2398 : return 1;
3616 : :
3617 : 4063920 : int cms = type_morespecific_(ce, pe, invariant, env);
3618 : :
3619 [ + + + + ]: 4063920 : 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 [ + + + + : 1391070 : 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 [ + + + + : 2672860 : if (!cms && i == clen-1 && clen == plen && !cva && pva && eq_msp(ce, pe, env) &&
+ + + + +
+ + - ]
3633 [ - + - - : 3460 : jl_is_typevar(ce) && jl_is_typevar(pe) && !cdiag && pdiag)
- - - - ]
3634 : 0 : return 0;
3635 : :
3636 [ + + ]: 2672860 : if (cms) some_morespecific = 1;
3637 : 2672860 : i++;
3638 : : }
3639 [ + + + + : 149016 : if (cva && pva && clen > plen && (!pdiag || cdiag))
+ + - + -
- ]
3640 : 37 : return 1;
3641 [ + + + + : 148979 : if (cva && !pva && !some_morespecific)
+ + ]
3642 : 1839 : return 0;
3643 [ + + - + : 147140 : return some_morespecific || (cdiag && !pdiag);
- - ]
3644 : : }
3645 : :
3646 : 43860 : static size_t tuple_full_length(jl_value_t *t)
3647 : : {
3648 : 43860 : size_t n = jl_nparams(t);
3649 [ + + ]: 43860 : if (n == 0) return 0;
3650 : 42910 : jl_value_t *last = jl_unwrap_unionall(jl_tparam(t,n-1));
3651 [ - + ]: 42910 : 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 : 42910 : 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 : 43860 : static int args_morespecific_fix1(jl_value_t *a, jl_value_t *b, int swap, jl_typeenv_t *env)
3662 : : {
3663 : 43860 : size_t n = jl_nparams(a);
3664 : 43860 : int taillen = tuple_full_length(b)-n+1;
3665 [ + + ]: 43860 : if (taillen <= 0)
3666 : 1978 : return -1;
3667 [ - + ]: 41882 : assert(jl_is_va_tuple((jl_datatype_t*)a));
3668 : 41882 : jl_datatype_t *new_a = NULL;
3669 : 41882 : jl_value_t *e[2] = { jl_unwrap_vararg_num(jl_unwrap_unionall(jl_tparam(a, n-1))), jl_box_long(taillen) };
3670 : 41882 : JL_GC_PUSH2(&new_a, &e[1]);
3671 : 41882 : new_a = (jl_datatype_t*)jl_instantiate_type_with((jl_value_t*)a, e, 1);
3672 : 41882 : int changed = 0;
3673 [ + + ]: 81552 : for (size_t i = 0; i < n-1; i++) {
3674 [ + + ]: 79438 : if (jl_tparam(a, i) != jl_tparam(new_a, i)) {
3675 : 39768 : changed = 1;
3676 : 39768 : break;
3677 : : }
3678 : : }
3679 : 41882 : int ret = -1;
3680 [ + + ]: 41882 : if (changed) {
3681 [ - + ]: 39768 : if (eq_msp(b, (jl_value_t*)new_a, env))
3682 : 0 : ret = swap;
3683 [ + + ]: 39768 : else if (swap)
3684 : 13942 : ret = type_morespecific_(b, (jl_value_t*)new_a, 0, env);
3685 : : else
3686 : 25826 : ret = type_morespecific_((jl_value_t*)new_a, b, 0, env);
3687 : : }
3688 : 41882 : JL_GC_POP();
3689 : 41882 : return ret;
3690 : : }
3691 : :
3692 : 39432800 : static int count_occurs(jl_value_t *t, jl_tvar_t *v)
3693 : : {
3694 [ + + ]: 39432800 : if (t == (jl_value_t*)v)
3695 : 9767840 : return 1;
3696 [ + + ]: 29665000 : if (jl_is_uniontype(t)) {
3697 : 69324 : int a = count_occurs(((jl_uniontype_t*)t)->a, v);
3698 : 69324 : int b = count_occurs(((jl_uniontype_t*)t)->b, v);
3699 : 69324 : return a > b ? a : b;
3700 : : }
3701 [ + + ]: 29595700 : if (jl_is_unionall(t)) {
3702 [ - + ]: 4258330 : if (((jl_unionall_t*)t)->var == v)
3703 : 0 : return 0;
3704 : 4258330 : return count_occurs(((jl_unionall_t*)t)->body, v);
3705 : : }
3706 [ + + ]: 25337300 : if (jl_is_vararg(t)) {
3707 : 120726 : jl_vararg_t *vm = (jl_vararg_t*)t;
3708 [ + - ]: 120726 : if (vm->T) {
3709 [ + + ]: 120726 : return count_occurs(vm->T, v) + (vm->N ? count_occurs(vm->N, v) : 0);
3710 : : }
3711 : : }
3712 [ + + ]: 25216600 : if (jl_is_datatype(t)) {
3713 : 15897100 : int i, c=0;
3714 [ + + ]: 40776000 : for(i=0; i < jl_nparams(t); i++)
3715 : 24878900 : c += count_occurs(jl_tparam(t,i), v);
3716 : 15897100 : return c;
3717 : : }
3718 : 9319450 : return 0;
3719 : : }
3720 : :
3721 : 327172 : static int num_occurs(jl_tvar_t *v, jl_typeenv_t *env)
3722 : : {
3723 [ + - ]: 348395 : while (env != NULL) {
3724 [ + + ]: 348395 : if (env->var == v)
3725 : 327172 : return (int)(ssize_t)env->val;
3726 : 21223 : 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 : 42252700 : static int type_morespecific_(jl_value_t *a, jl_value_t *b, int invariant, jl_typeenv_t *env)
3744 : : {
3745 [ + + ]: 42252700 : if (a == b)
3746 : 8403110 : return 0;
3747 : :
3748 [ + + + + ]: 33849600 : 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 : 1897170 : jl_vararg_kind_t akind = jl_va_tuple_kind((jl_datatype_t*)a);
3752 : 1897170 : jl_vararg_kind_t bkind = jl_va_tuple_kind((jl_datatype_t*)b);
3753 : 1897170 : int ans = -1;
3754 [ + + + + ]: 1897170 : if (akind == JL_VARARG_BOUND && bkind < JL_VARARG_BOUND) {
3755 : 27551 : ans = args_morespecific_fix1(a, b, 0, env);
3756 [ + + ]: 27551 : if (ans == 1) return 1;
3757 : : }
3758 [ + + + + ]: 1878460 : if (bkind == JL_VARARG_BOUND && akind < JL_VARARG_BOUND) {
3759 : 16309 : ans = args_morespecific_fix1(b, a, 1, env);
3760 [ + + ]: 16309 : if (ans == 0) return 0;
3761 : : }
3762 : 1866630 : return tuple_morespecific((jl_datatype_t*)a, (jl_datatype_t*)b, invariant, env);
3763 : : }
3764 : :
3765 [ + + ]: 31952400 : if (!invariant) {
3766 [ + + ]: 26843500 : if ((jl_datatype_t*)a == jl_any_type) return 0;
3767 [ + + + + ]: 26377900 : if ((jl_datatype_t*)b == jl_any_type && !jl_is_typevar(a)) return 1;
3768 : : }
3769 : :
3770 [ + + ]: 30898200 : if (jl_is_uniontype(a)) {
3771 [ + + ]: 2225740 : if (jl_is_unionall(b)) {
3772 : 242193 : 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 [ + + ]: 1983550 : if (sub_msp(b, a, env))
3777 : 48479 : return 0;
3778 : 1935070 : jl_uniontype_t *u = (jl_uniontype_t*)a;
3779 [ + + + + ]: 1935070 : if (type_morespecific_(u->a, b, invariant, env) || type_morespecific_(u->b, b, invariant, env)) {
3780 [ + + ]: 18289 : if (jl_is_uniontype(b)) {
3781 : 1384 : jl_uniontype_t *v = (jl_uniontype_t*)b;
3782 [ + - - + ]: 1384 : if (type_morespecific_(v->a, a, invariant, env) || type_morespecific_(v->b, a, invariant, env))
3783 : 0 : return 0;
3784 : : }
3785 : 18289 : return 1;
3786 : : }
3787 : 1916780 : return 0;
3788 : : }
3789 : :
3790 [ + + + - ]: 28672400 : if (jl_is_type_type(a) && !invariant) {
3791 [ - + ]: 3277780 : if (b == (jl_value_t*)jl_typeofbottom_type)
3792 : 0 : return 0;
3793 : 3277780 : jl_value_t *tp0a = jl_tparam0(a);
3794 [ + + ]: 3277780 : if (jl_is_typevar(tp0a)) {
3795 : 2470330 : jl_value_t *ub = ((jl_tvar_t*)tp0a)->ub;
3796 [ + + + - ]: 2470330 : if (jl_is_kind(b) && !sub_msp((jl_value_t*)jl_any_type, ub, env))
3797 : 116 : return 1;
3798 : : }
3799 [ + + ]: 807448 : else if (tp0a == jl_bottom_type) {
3800 [ + - ]: 67347 : if (sub_msp(b, (jl_value_t*)jl_type_type, env))
3801 : 67347 : return 1;
3802 : : }
3803 [ + - + - ]: 740101 : else if (b == (jl_value_t*)jl_datatype_type || b == (jl_value_t*)jl_unionall_type ||
3804 [ + + ]: 740101 : b == (jl_value_t*)jl_uniontype_type) {
3805 : 120 : return 1;
3806 : : }
3807 : : }
3808 : :
3809 [ + + ]: 28604900 : if (jl_is_uniontype(b)) {
3810 [ + + ]: 2527980 : if (jl_is_unionall(a)) {
3811 : 241169 : HANDLE_UNIONALL_A;
3812 : : }
3813 : 2286810 : jl_uniontype_t *u = (jl_uniontype_t*)b;
3814 [ + + + + ]: 2286810 : if (type_morespecific_(a, u->a, invariant, env) || type_morespecific_(a, u->b, invariant, env))
3815 : 3714 : return !type_morespecific_(b, a, invariant, env);
3816 : 2283100 : return 0;
3817 : : }
3818 : :
3819 [ + + + + ]: 26076900 : if (jl_is_datatype(a) && jl_is_datatype(b)) {
3820 : 10561200 : 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 [ + + + + : 10561200 : if (tta == jl_typeofbottom_type && (jl_is_kind(b) || jl_is_type_type(b)))
- + ]
3823 : 8 : return 1;
3824 : 10561200 : int super = 0;
3825 [ + + ]: 24665900 : while (tta != jl_any_type) {
3826 [ + + ]: 16646100 : if (tta->name == ttb->name) {
3827 [ + + ]: 2541430 : if (super) {
3828 [ + + ]: 109328 : if (tta->name != jl_type_typename) return 1;
3829 : 580 : jl_value_t *tp0 = jl_tparam0(b);
3830 [ + + ]: 580 : if (jl_is_typevar(tp0)) {
3831 [ - + ]: 116 : if (sub_msp((jl_value_t*)jl_any_type, ((jl_tvar_t*)tp0)->ub, env))
3832 : 0 : return 1;
3833 : : }
3834 : : }
3835 [ - + ]: 2432680 : assert(jl_nparams(tta) == jl_nparams(ttb));
3836 : 2432680 : int ascore=0, bscore=0, ascore1=0, bscore1=0, adiag=0, bdiag=0;
3837 [ + + ]: 5279650 : for(size_t i=0; i < jl_nparams(tta); i++) {
3838 : 2880500 : jl_value_t *apara = jl_tparam(tta,i);
3839 : 2880500 : jl_value_t *bpara = jl_tparam(ttb,i);
3840 : 2880500 : int afree = jl_has_free_typevars(apara);
3841 : 2880500 : int bfree = jl_has_free_typevars(bpara);
3842 [ + + + + : 2880500 : if (!afree && !bfree && !jl_types_equal(apara, bpara))
+ + ]
3843 : 33542 : return 0;
3844 [ + + + + : 2846960 : if (type_morespecific_(apara, bpara, 1, env) && (jl_is_typevar(apara) || !afree || bfree))
+ + + + ]
3845 : 358474 : ascore += 1;
3846 [ + + + + : 2488490 : else if (type_morespecific_(bpara, apara, 1, env) && (jl_is_typevar(bpara) || !bfree || afree))
+ + + + ]
3847 : 392941 : bscore += 1;
3848 [ + + ]: 2095550 : else if (eq_msp(apara, bpara, env)) {
3849 [ + + + + ]: 528097 : if (!afree && bfree)
3850 : 308 : ascore += 1;
3851 [ + + + + ]: 527789 : else if (afree && !bfree)
3852 : 308 : bscore += 1;
3853 : : }
3854 [ + + + + : 2846960 : if (jl_is_typevar(bpara) && !jl_is_typevar(apara) && !jl_is_type(apara))
+ + ]
3855 : 55494 : ascore1 = 1;
3856 [ + + + + : 2791470 : else if (jl_is_typevar(apara) && !jl_is_typevar(bpara) && !jl_is_type(bpara))
+ + ]
3857 : 55457 : bscore1 = 1;
3858 [ + + + + ]: 2846960 : if (!adiag && jl_is_typevar(apara)) {
3859 [ + + ]: 3078320 : for(int j=i+1; j < jl_nparams(tta); j++) {
3860 [ + + ]: 815583 : if (jl_has_typevar(jl_tparam(tta,j), (jl_tvar_t*)apara)) {
3861 : 24 : adiag = 1; break;
3862 : : }
3863 : : }
3864 : : }
3865 [ + + + + ]: 2846960 : if (!bdiag && jl_is_typevar(bpara)) {
3866 [ + + ]: 3015980 : for(int j=i+1; j < jl_nparams(ttb); j++) {
3867 [ + + ]: 815391 : if (jl_has_typevar(jl_tparam(ttb,j), (jl_tvar_t*)bpara)) {
3868 : 24 : bdiag = 1; break;
3869 : : }
3870 : : }
3871 : : }
3872 : : }
3873 [ + + ]: 2399140 : if (ascore1 > bscore1)
3874 : 39884 : return 1;
3875 [ + + + + : 2359260 : if (bscore1 > ascore1 || bscore > ascore || bdiag > adiag)
- + ]
3876 : 348542 : return 0;
3877 [ + + - + ]: 2010720 : return ascore > bscore || adiag > bdiag;
3878 : : }
3879 : 14104700 : tta = tta->super; super = 1;
3880 : : }
3881 : 8019760 : return 0;
3882 : : }
3883 : :
3884 [ + + ]: 15515700 : if (jl_is_typevar(a)) {
3885 [ + + ]: 4310620 : if (jl_is_typevar(b)) {
3886 : 3069970 : return (( type_morespecific_((jl_value_t*)((jl_tvar_t*)a)->ub,
3887 [ - + ]: 288972 : (jl_value_t*)((jl_tvar_t*)b)->ub, 0, env) &&
3888 : 288972 : !type_morespecific_((jl_value_t*)((jl_tvar_t*)a)->lb,
3889 [ + + - + ]: 6139930 : (jl_value_t*)((jl_tvar_t*)b)->lb, 0, env)) ||
3890 : 2780990 : ( 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 [ + + ]: 1240650 : if (!jl_is_type(b))
3896 : 55457 : return 0;
3897 [ + + ]: 1185190 : if (invariant) {
3898 [ - + ]: 810384 : if (((jl_tvar_t*)a)->ub == jl_bottom_type)
3899 : 0 : return 1;
3900 [ + + ]: 810384 : if (!jl_has_free_typevars(b))
3901 : 326815 : return 0;
3902 [ + + ]: 483569 : if (eq_msp(((jl_tvar_t*)a)->ub, b, env))
3903 : 6790 : return num_occurs((jl_tvar_t*)a, env) >= 2;
3904 : : }
3905 : : else {
3906 : : // need `{T,T} where T` more specific than `{Any, Any}`
3907 [ + + + + : 408742 : if (b == (jl_value_t*)jl_any_type && ((jl_tvar_t*)a)->ub == (jl_value_t*)jl_any_type &&
+ + ]
3908 : 33934 : num_occurs((jl_tvar_t*)a, env) >= 2)
3909 : 33574 : return 1;
3910 : : }
3911 : 818013 : return type_morespecific_(((jl_tvar_t*)a)->ub, b, 0, env);
3912 : : }
3913 [ + + ]: 11205100 : if (jl_is_typevar(b)) {
3914 [ + + ]: 1357100 : if (!jl_is_type(a))
3915 : 110951 : return 1;
3916 [ + + ]: 1246150 : if (invariant) {
3917 [ - + ]: 939660 : if (((jl_tvar_t*)b)->ub == jl_bottom_type)
3918 : 0 : return 0;
3919 [ + + ]: 939660 : if (jl_has_free_typevars(a)) {
3920 [ + + ]: 565773 : if (type_morespecific_(a, ((jl_tvar_t*)b)->ub, 0, env))
3921 : 190910 : return 1;
3922 [ + + ]: 374863 : if (eq_msp(a, ((jl_tvar_t*)b)->ub, env))
3923 : 3413 : return num_occurs((jl_tvar_t*)b, env) < 2;
3924 : 371450 : return 0;
3925 : : }
3926 : : else {
3927 [ + + ]: 373887 : if (obviously_disjoint(a, ((jl_tvar_t*)b)->ub, 1))
3928 : 197619 : return 0;
3929 [ + + ]: 176268 : if (type_morespecific_(((jl_tvar_t*)b)->ub, a, 0, env))
3930 : 43622 : return 0;
3931 : 132646 : return 1;
3932 : : }
3933 : : }
3934 : 306491 : return type_morespecific_(a, ((jl_tvar_t*)b)->ub, 0, env);
3935 : : }
3936 : :
3937 [ + + ]: 9847980 : if (jl_is_unionall(a)) {
3938 : 4839090 : HANDLE_UNIONALL_A;
3939 : : }
3940 [ + + ]: 5008880 : if (jl_is_unionall(b)) {
3941 : 4600320 : HANDLE_UNIONALL_B;
3942 : : }
3943 : :
3944 : 408566 : return 0;
3945 : : }
3946 : :
3947 : 12043100 : JL_DLLEXPORT int jl_type_morespecific(jl_value_t *a, jl_value_t *b)
3948 : : {
3949 [ + + ]: 12043100 : if (obviously_disjoint(a, b, 1))
3950 : 8340600 : return 0;
3951 [ + - - + ]: 3702460 : if (jl_has_free_typevars(a) || jl_has_free_typevars(b))
3952 : 0 : return 0;
3953 [ + + ]: 3702460 : if (jl_subtype(b, a))
3954 : 848718 : return 0;
3955 [ + + ]: 2853740 : if (jl_subtype(a, b))
3956 : 1038030 : return 1;
3957 : 1815710 : 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
|
