Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : /*
4 : : Types
5 : : . type union, type cache, and instantiation
6 : : . builtin type definitions
7 : : */
8 : : #include <stdlib.h>
9 : : #include <string.h>
10 : : #ifdef _OS_WINDOWS_
11 : : #include <malloc.h>
12 : : #endif
13 : : #include "julia.h"
14 : : #include "julia_internal.h"
15 : : #include "builtin_proto.h"
16 : : #include "julia_assert.h"
17 : :
18 : : #ifdef __cplusplus
19 : : extern "C" {
20 : : #endif
21 : :
22 : : _Atomic(jl_value_t*) cmpswap_names JL_GLOBALLY_ROOTED;
23 : :
24 : : // compute empirical max-probe for a given size
25 : : #define max_probe(size) ((size) <= 1024 ? 16 : (size) >> 6)
26 : : #define h2index(hv, sz) (size_t)((hv) & ((sz)-1))
27 : :
28 : : // --- type properties and predicates ---
29 : :
30 :11465600000 : static int typeenv_has(jl_typeenv_t *env, jl_tvar_t *v) JL_NOTSAFEPOINT
31 : : {
32 [ + + ]:22701000000 : while (env != NULL) {
33 [ + + ]:18389800000 : if (env->var == v)
34 : 7154390000 : return 1;
35 :11235500000 : env = env->prev;
36 : : }
37 : 4311190000 : return 0;
38 : : }
39 : :
40 : 7039 : static int layout_uses_free_typevars(jl_value_t *v, jl_typeenv_t *env)
41 : : {
42 [ + + ]: 7039 : if (jl_typeis(v, jl_tvar_type))
43 : 5622 : return !typeenv_has(env, (jl_tvar_t*)v);
44 [ + + ]: 1417 : if (jl_is_uniontype(v))
45 [ + - + + ]: 12 : return layout_uses_free_typevars(((jl_uniontype_t*)v)->a, env) ||
46 : 6 : layout_uses_free_typevars(((jl_uniontype_t*)v)->b, env);
47 [ - + ]: 1411 : if (jl_is_vararg(v)) {
48 : 0 : jl_vararg_t *vm = (jl_vararg_t*)v;
49 [ # # # # ]: 0 : if (vm->T && layout_uses_free_typevars(vm->T, env))
50 : 0 : return 1;
51 [ # # # # ]: 0 : if (vm->N && layout_uses_free_typevars(vm->N, env))
52 : 0 : return 1;
53 : 0 : return 0;
54 : : }
55 [ + + ]: 1411 : if (jl_is_unionall(v)) {
56 : 9 : jl_unionall_t *ua = (jl_unionall_t*)v;
57 : 9 : jl_typeenv_t newenv = { ua->var, NULL, env };
58 : 9 : return layout_uses_free_typevars(ua->body, &newenv);
59 : : }
60 [ + + ]: 1402 : if (jl_is_datatype(v)) {
61 : 977 : jl_datatype_t *dt = (jl_datatype_t*)v;
62 [ + + + - : 977 : if (dt->layout || dt->isconcretetype || !dt->name->mayinlinealloc)
+ + ]
63 : 862 : return 0;
64 [ + + ]: 115 : if (dt->name == jl_namedtuple_typename)
65 [ - + - - ]: 76 : return layout_uses_free_typevars(jl_tparam0(dt), env) || layout_uses_free_typevars(jl_tparam1(dt), env);
66 [ + + ]: 39 : if (dt->name == jl_tuple_typename)
67 : : // conservative, since we don't want to inline an abstract tuple,
68 : : // and we currently declare !has_fixed_layout for these, but that
69 : : // means we also won't be able to inline a tuple which is concrete
70 : : // except for the use of free type-vars
71 : 34 : return 1;
72 [ - + ]: 5 : jl_svec_t *types = jl_get_fieldtypes(dt);
73 : 5 : size_t i, l = jl_svec_len(types);
74 [ + + ]: 8 : for (i = 0; i < l; i++) {
75 : 7 : jl_value_t *ft = jl_svecref(types, i);
76 [ + + ]: 7 : if (layout_uses_free_typevars(ft, env)) {
77 : : // This might be inline-alloc, but we don't know the layout
78 : 4 : return 1;
79 : : }
80 : : }
81 : : }
82 : 426 : return 0;
83 : : }
84 : :
85 :38502100000 : static int has_free_typevars(jl_value_t *v, jl_typeenv_t *env) JL_NOTSAFEPOINT
86 : : {
87 [ + + ]:38502100000 : if (jl_typeis(v, jl_tvar_type)) {
88 : 8046350000 : return !typeenv_has(env, (jl_tvar_t*)v);
89 : : }
90 [ + + ]:30455700000 : if (jl_is_uniontype(v))
91 [ + + + + ]: 3879050000 : return has_free_typevars(((jl_uniontype_t*)v)->a, env) ||
92 : 1875300000 : has_free_typevars(((jl_uniontype_t*)v)->b, env);
93 [ + + ]:28452000000 : if (jl_is_vararg(v)) {
94 : 16716900 : jl_vararg_t *vm = (jl_vararg_t*)v;
95 [ + + ]: 16716900 : if (vm->T) {
96 [ + + ]: 16707300 : if (has_free_typevars(vm->T, env))
97 : 41463 : return 1;
98 [ + + + + ]: 16665800 : return vm->N && has_free_typevars(vm->N, env);
99 : : }
100 : : }
101 [ + + ]:28435300000 : if (jl_is_unionall(v)) {
102 : 6828740000 : jl_unionall_t *ua = (jl_unionall_t*)v;
103 : 6828740000 : jl_typeenv_t newenv = { ua->var, NULL, env };
104 [ + + + + :13622300000 : return has_free_typevars(ua->var->lb, env) || has_free_typevars(ua->var->ub, env) ||
+ + ]
105 : 6793530000 : has_free_typevars(ua->body, &newenv);
106 : : }
107 [ + + ]:21606500000 : if (jl_is_datatype(v)) {
108 :13069000000 : int expect = ((jl_datatype_t*)v)->hasfreetypevars;
109 [ + + + + ]:13069000000 : if (expect == 0 || env == NULL)
110 :10063500000 : return expect;
111 : : size_t i;
112 [ + + ]:11293900000 : for (i = 0; i < jl_nparams(v); i++) {
113 [ + + ]: 8422080000 : if (has_free_typevars(jl_tparam(v, i), env)) {
114 : 133700000 : return 1;
115 : : }
116 : : }
117 : : }
118 :11409400000 : return 0;
119 : : }
120 : :
121 : 5718640000 : JL_DLLEXPORT int jl_has_free_typevars(jl_value_t *v) JL_NOTSAFEPOINT
122 : : {
123 : 5718640000 : return has_free_typevars(v, NULL);
124 : : }
125 : :
126 : 4944530 : static void find_free_typevars(jl_value_t *v, jl_typeenv_t *env, jl_array_t *out)
127 : : {
128 [ + + ]: 4944530 : if (jl_typeis(v, jl_tvar_type)) {
129 [ + + ]: 1941010 : if (!typeenv_has(env, (jl_tvar_t*)v))
130 : 1936040 : jl_array_ptr_1d_push(out, v);
131 : : }
132 [ + + ]: 3003520 : else if (jl_is_uniontype(v)) {
133 : 349190 : find_free_typevars(((jl_uniontype_t*)v)->a, env, out);
134 : 349190 : find_free_typevars(((jl_uniontype_t*)v)->b, env, out);
135 : : }
136 [ + + ]: 2654330 : else if (jl_is_vararg(v)) {
137 : 23681 : jl_vararg_t *vm = (jl_vararg_t *)v;
138 [ + - ]: 23681 : if (vm->T) {
139 : 23681 : find_free_typevars(vm->T, env, out);
140 [ + + ]: 23681 : if (vm->N) {
141 : 23677 : find_free_typevars(vm->N, env, out);
142 : : }
143 : : }
144 : : }
145 [ + + ]: 2630650 : else if (jl_is_unionall(v)) {
146 : 4958 : jl_unionall_t *ua = (jl_unionall_t*)v;
147 : 4958 : jl_typeenv_t newenv = { ua->var, NULL, env };
148 : 4958 : find_free_typevars(ua->var->lb, env, out);
149 : 4958 : find_free_typevars(ua->var->ub, env, out);
150 : 4958 : find_free_typevars(ua->body, &newenv, out);
151 : : }
152 [ + + ]: 2625690 : else if (jl_is_datatype(v)) {
153 [ + + ]: 2583600 : if (!((jl_datatype_t*)v)->hasfreetypevars)
154 : 1104890 : return;
155 : : size_t i;
156 [ + + ]: 3900030 : for (i=0; i < jl_nparams(v); i++)
157 : 2421330 : find_free_typevars(jl_tparam(v,i), env, out);
158 : : }
159 : : }
160 : :
161 : 1762590 : JL_DLLEXPORT jl_array_t *jl_find_free_typevars(jl_value_t *v)
162 : : {
163 : 1762590 : jl_array_t *out = jl_alloc_vec_any(0);
164 : 1762590 : JL_GC_PUSH1(&out);
165 : 1762590 : find_free_typevars(v, NULL, out);
166 : 1762590 : JL_GC_POP();
167 : 1762590 : return out;
168 : : }
169 : :
170 : : // test whether a type has vars bound by the given environment
171 :14556100000 : static int jl_has_bound_typevars(jl_value_t *v, jl_typeenv_t *env) JL_NOTSAFEPOINT
172 : : {
173 [ + + ]:14556100000 : if (jl_typeis(v, jl_tvar_type))
174 : 3417280000 : return typeenv_has(env, (jl_tvar_t*)v);
175 [ + + ]:11138900000 : if (jl_is_uniontype(v))
176 [ + + + + ]: 1820270000 : return jl_has_bound_typevars(((jl_uniontype_t*)v)->a, env) ||
177 : 908075000 : jl_has_bound_typevars(((jl_uniontype_t*)v)->b, env);
178 [ + + ]:10226700000 : if (jl_is_vararg(v)) {
179 : 1600370 : jl_vararg_t *vm = (jl_vararg_t *)v;
180 [ + - + + ]: 2750310 : return vm->T && (jl_has_bound_typevars(vm->T, env) ||
181 [ + + + + ]: 1149950 : (vm->N && jl_has_bound_typevars(vm->N, env)));
182 : : }
183 [ + + ]:10225100000 : if (jl_is_unionall(v)) {
184 : 2785190000 : jl_unionall_t *ua = (jl_unionall_t*)v;
185 [ + + + + ]: 2785190000 : if (jl_has_bound_typevars(ua->var->lb, env) || jl_has_bound_typevars(ua->var->ub, env))
186 : 4708680 : return 1;
187 : 2780480000 : jl_typeenv_t *te = env;
188 [ + + ]: 5512330000 : while (te != NULL) {
189 [ + + ]: 2780480000 : if (te->var == ua->var)
190 : 48632600 : break;
191 : 2731850000 : te = te->prev;
192 : : }
193 [ + + ]: 2780480000 : if (te) te->var = NULL; // temporarily remove this var from env
194 : 2780480000 : int ans = jl_has_bound_typevars(ua->body, env);
195 [ + + ]: 2780480000 : if (te) te->var = ua->var;
196 : 2780480000 : return ans;
197 : : }
198 [ + + ]: 7439870000 : if (jl_is_datatype(v)) {
199 [ + + ]: 4057800000 : if (!((jl_datatype_t*)v)->hasfreetypevars)
200 : 2532930000 : return 0;
201 : : size_t i;
202 [ + + ]: 5173530000 : for (i=0; i < jl_nparams(v); i++) {
203 [ + + ]: 3717400000 : if (jl_has_bound_typevars(jl_tparam(v,i), env))
204 : 68743600 : return 1;
205 : : }
206 : : }
207 : 4838200000 : return 0;
208 : : }
209 : :
210 : 665184000 : JL_DLLEXPORT int jl_has_typevar(jl_value_t *t, jl_tvar_t *v) JL_NOTSAFEPOINT
211 : : {
212 : 665184000 : jl_typeenv_t env = { v, NULL, NULL };
213 : 665184000 : return jl_has_bound_typevars(t, &env);
214 : : }
215 : :
216 : 267244 : static int _jl_has_typevar_from_ua(jl_value_t *t, jl_unionall_t *ua, jl_typeenv_t *prev)
217 : : {
218 : 267244 : jl_typeenv_t env = { ua->var, NULL, prev };
219 [ + + ]: 267244 : if (jl_is_unionall(ua->body))
220 : 101778 : return _jl_has_typevar_from_ua(t, (jl_unionall_t*)ua->body, &env);
221 : : else
222 : 165466 : return jl_has_bound_typevars(t, &env);
223 : : }
224 : :
225 : 165466 : JL_DLLEXPORT int jl_has_typevar_from_unionall(jl_value_t *t, jl_unionall_t *ua)
226 : : {
227 : 165466 : return _jl_has_typevar_from_ua(t, ua, NULL);
228 : : }
229 : :
230 : 399704 : int jl_has_fixed_layout(jl_datatype_t *dt)
231 : : {
232 [ + + - + ]: 399704 : if (dt->layout || dt->isconcretetype)
233 : 1183 : return 1;
234 [ + + ]: 398521 : if (dt->name->abstract)
235 : 347829 : return 0;
236 [ + + ]: 50692 : if (dt->name == jl_namedtuple_typename)
237 [ + + - + ]: 458 : return !layout_uses_free_typevars(jl_tparam0(dt), NULL) && !layout_uses_free_typevars(jl_tparam1(dt), NULL);
238 [ + + ]: 50234 : if (dt->name == jl_tuple_typename)
239 : 44923 : return 0;
240 [ + + ]: 5311 : jl_svec_t *types = jl_get_fieldtypes(dt);
241 : 5311 : size_t i, l = jl_svec_len(types);
242 [ + + ]: 6165 : for (i = 0; i < l; i++) {
243 : 6052 : jl_value_t *ft = jl_svecref(types, i);
244 [ + + ]: 6052 : if (layout_uses_free_typevars(ft, NULL)) {
245 : : // This might be inline-alloc, but we don't know the layout
246 : 5198 : return 0;
247 : : }
248 : : }
249 : 113 : return 1;
250 : : }
251 : :
252 : 15541 : int jl_type_mappable_to_c(jl_value_t *ty)
253 : : {
254 [ + - + - ]: 15541 : assert(!jl_is_typevar(ty) && jl_is_type(ty));
255 [ + + ]: 15541 : if (jl_is_structtype(ty))
256 [ + - + - ]: 1183 : return jl_has_fixed_layout((jl_datatype_t*)ty) && ((jl_datatype_t*)ty)->name->atomicfields == NULL;
257 [ + + ]: 14358 : if (jl_is_primitivetype(ty))
258 : 9834 : return 1;
259 [ + + + + ]: 4524 : if (ty == (jl_value_t*)jl_any_type || ty == (jl_value_t*)jl_bottom_type)
260 : 872 : return 1; // as boxed
261 [ - + - - ]: 3652 : if (jl_is_abstract_ref_type(ty) || jl_is_array_type(ty) ||
262 [ # # # # : 0 : (jl_is_datatype(ty) && ((jl_datatype_t*)ty)->layout != NULL &&
# # ]
263 : 0 : jl_is_layout_opaque(((jl_datatype_t*)ty)->layout)))
264 : 3652 : return 1; // as boxed
265 : 0 : return 0; // refuse to map Union and UnionAll to C
266 : : }
267 : :
268 : : // Return true for any type (Integer or Unsigned) that can fit in a
269 : : // size_t and pass back value, else return false
270 : 0 : JL_DLLEXPORT int jl_get_size(jl_value_t *val, size_t *pnt)
271 : : {
272 [ # # ]: 0 : if (jl_is_long(val)) {
273 : 0 : ssize_t slen = jl_unbox_long(val);
274 [ # # ]: 0 : if (slen < 0)
275 : 0 : jl_errorf("size or dimension is negative: %d", slen);
276 : 0 : *pnt = slen;
277 : 0 : return 1;
278 : : }
279 : 0 : return 0;
280 : : }
281 : :
282 : : // --- type union ---
283 : :
284 : 8814560 : static int count_union_components(jl_value_t **types, size_t n)
285 : : {
286 : 8814560 : size_t i, c=0;
287 [ + + ]: 22112200 : for(i=0; i < n; i++) {
288 : 13297600 : jl_value_t *e = types[i];
289 [ + + ]: 13297600 : if (jl_is_uniontype(e)) {
290 : 2318770 : jl_uniontype_t *u = (jl_uniontype_t*)e;
291 : 2318770 : c += count_union_components(&u->a, 1);
292 : 2318770 : c += count_union_components(&u->b, 1);
293 : : }
294 : : else {
295 : 10978900 : c++;
296 : : }
297 : : }
298 : 8814560 : return c;
299 : : }
300 : :
301 : 0 : int jl_count_union_components(jl_value_t *v)
302 : : {
303 [ # # ]: 0 : if (!jl_is_uniontype(v)) return 1;
304 : 0 : jl_uniontype_t *u = (jl_uniontype_t*)v;
305 : 0 : return jl_count_union_components(u->a) + jl_count_union_components(u->b);
306 : : }
307 : :
308 : : // Return the `*pi`th element of a nested type union, according to a
309 : : // standard traversal order. Anything that is not itself a `Union` is
310 : : // considered an "element". `*pi` is destroyed in the process.
311 : 19089700 : static jl_value_t *nth_union_component(jl_value_t *v, int *pi) JL_NOTSAFEPOINT
312 : : {
313 [ + + ]: 19089700 : if (!jl_is_uniontype(v)) {
314 [ + + ]: 11666900 : if (*pi == 0)
315 : 7401110 : return v;
316 : 4265800 : (*pi)--;
317 : 4265800 : return NULL;
318 : : }
319 : 7422750 : jl_uniontype_t *u = (jl_uniontype_t*)v;
320 : 7422750 : jl_value_t *a = nth_union_component(u->a, pi);
321 [ + + ]: 7422750 : if (a) return a;
322 : 4265800 : return nth_union_component(u->b, pi);
323 : : }
324 : :
325 : 7401110 : jl_value_t *jl_nth_union_component(jl_value_t *v, int i) JL_NOTSAFEPOINT
326 : : {
327 : 7401110 : return nth_union_component(v, &i);
328 : : }
329 : :
330 : : // inverse of jl_nth_union_component
331 : 9522330 : int jl_find_union_component(jl_value_t *haystack, jl_value_t *needle, unsigned *nth) JL_NOTSAFEPOINT
332 : : {
333 [ + + ]: 9522330 : if (jl_is_uniontype(haystack)) {
334 [ + + ]: 3181840 : if (jl_find_union_component(((jl_uniontype_t*)haystack)->a, needle, nth))
335 : 7128 : return 1;
336 [ + - ]: 3174710 : if (jl_find_union_component(((jl_uniontype_t*)haystack)->b, needle, nth))
337 : 3174710 : return 1;
338 : 0 : return 0;
339 : : }
340 [ + + ]: 6340490 : if (needle == haystack)
341 : 3165780 : return 1;
342 : 3174710 : (*nth)++;
343 : 3174710 : return 0;
344 : : }
345 : :
346 : 8814560 : static void flatten_type_union(jl_value_t **types, size_t n, jl_value_t **out, size_t *idx) JL_NOTSAFEPOINT
347 : : {
348 : : size_t i;
349 [ + + ]: 22112200 : for(i=0; i < n; i++) {
350 : 13297600 : jl_value_t *e = types[i];
351 [ + + ]: 13297600 : if (jl_is_uniontype(e)) {
352 : 2318770 : jl_uniontype_t *u = (jl_uniontype_t*)e;
353 : 2318770 : flatten_type_union(&u->a, 1, out, idx);
354 : 2318770 : flatten_type_union(&u->b, 1, out, idx);
355 : : }
356 : : else {
357 : 10978900 : out[*idx] = e;
358 : 10978900 : (*idx)++;
359 : : }
360 : : }
361 : 8814560 : }
362 : :
363 : 9787910 : STATIC_INLINE const char *datatype_module_name(jl_value_t *t) JL_NOTSAFEPOINT
364 : : {
365 [ + + ]: 9787910 : if (((jl_datatype_t*)t)->name->module == NULL)
366 : 57 : return NULL;
367 : 9787850 : return jl_symbol_name(((jl_datatype_t*)t)->name->module->name);
368 : : }
369 : :
370 : 19034100 : STATIC_INLINE const char *str_(const char *s) JL_NOTSAFEPOINT
371 : : {
372 [ + + ]: 19034100 : return s == NULL ? "" : s;
373 : : }
374 : :
375 : 1938580 : STATIC_INLINE int cmp_(int a, int b) JL_NOTSAFEPOINT
376 : : {
377 [ + + ]: 1938580 : return a < b ? -1 : a > b;
378 : : }
379 : :
380 : : // a/b are jl_datatype_t* & not NULL
381 : 4895490 : static int datatype_name_cmp(jl_value_t *a, jl_value_t *b) JL_NOTSAFEPOINT
382 : : {
383 [ + + ]: 4895490 : if (!jl_is_datatype(a))
384 : 1361 : return jl_is_datatype(b) ? 1 : 0;
385 [ + + ]: 4894130 : if (!jl_is_datatype(b))
386 : 174 : return -1;
387 : 4893960 : int cmp = strcmp(str_(datatype_module_name(a)), str_(datatype_module_name(b)));
388 [ + + ]: 4893960 : if (cmp != 0)
389 : 270844 : return cmp;
390 : 4623110 : cmp = strcmp(str_(jl_typename_str(a)), str_(jl_typename_str(b)));
391 [ + + ]: 4623110 : if (cmp != 0)
392 : 2684530 : return cmp;
393 : 1938580 : cmp = cmp_(jl_nparams(a), jl_nparams(b));
394 [ + + ]: 1938580 : if (cmp != 0)
395 : 41081 : return cmp;
396 : : // compare up to 3 type parameters
397 [ + + + + ]: 5947750 : for (int i = 0; i < 3 && i < jl_nparams(a); i++) {
398 : 4433130 : jl_value_t *ap = jl_tparam(a, i);
399 : 4433130 : jl_value_t *bp = jl_tparam(b, i);
400 [ + + ]: 4433130 : if (ap == bp) {
401 : 2516760 : continue;
402 : : }
403 [ + + + + ]: 1916370 : else if (jl_is_datatype(ap) && jl_is_datatype(bp)) {
404 : 390636 : cmp = datatype_name_cmp(ap, bp);
405 [ + + ]: 390636 : if (cmp != 0)
406 : 350441 : return cmp;
407 : : }
408 [ + + + + ]: 1525730 : else if (jl_is_unionall(ap) && jl_is_unionall(bp)) {
409 : 67424 : cmp = datatype_name_cmp(jl_unwrap_unionall(ap), jl_unwrap_unionall(bp));
410 [ + + ]: 67424 : if (cmp != 0)
411 : 32439 : return cmp;
412 : : }
413 : : else {
414 : : // give up
415 : 1458310 : cmp = 0;
416 : : }
417 : : }
418 : 1514620 : return cmp;
419 : : }
420 : :
421 : : // sort singletons first, then DataTypes, then UnionAlls,
422 : : // ties broken alphabetically including module name & type parameters
423 : 7171540 : static int union_sort_cmp(jl_value_t *a, jl_value_t *b) JL_NOTSAFEPOINT
424 : : {
425 [ + + ]: 7171540 : if (a == NULL)
426 : 256101 : return b == NULL ? 0 : 1;
427 [ + + ]: 6915430 : if (b == NULL)
428 : 1102150 : return -1;
429 [ + + ]: 5813290 : if (jl_is_datatype(a)) {
430 [ + + ]: 2439000 : if (!jl_is_datatype(b))
431 : 174802 : return -1;
432 [ + + ]: 2264200 : if (jl_is_datatype_singleton((jl_datatype_t*)a)) {
433 [ + + ]: 162691 : if (jl_is_datatype_singleton((jl_datatype_t*)b))
434 : 47117 : return datatype_name_cmp(a, b);
435 : 115574 : return -1;
436 : : }
437 [ + + ]: 2101510 : else if (jl_is_datatype_singleton((jl_datatype_t*)b)) {
438 : 279976 : return 1;
439 : : }
440 [ + + ]: 1821540 : else if (jl_isbits(a)) {
441 [ + + ]: 226241 : if (jl_isbits(b))
442 : 139962 : return datatype_name_cmp(a, b);
443 : 86279 : return -1;
444 : : }
445 [ + + ]: 1595300 : else if (jl_isbits(b)) {
446 : 69576 : return 1;
447 : : }
448 : : else {
449 : 1525720 : return datatype_name_cmp(a, b);
450 : : }
451 : : }
452 : : else {
453 [ + + ]: 3374280 : if (jl_is_datatype(b))
454 : 649650 : return 1;
455 : 2724630 : return datatype_name_cmp(jl_unwrap_unionall(a), jl_unwrap_unionall(b));
456 : : }
457 : : }
458 : :
459 : 4177010 : static void isort_union(jl_value_t **a, size_t len) JL_NOTSAFEPOINT
460 : : {
461 : : size_t i, j;
462 [ + + ]: 10978900 : for (i = 1; i < len; i++) {
463 : 6801860 : jl_value_t *x = a[i];
464 [ + + ]: 8505360 : for (j = i; j > 0; j--) {
465 : 7171540 : jl_value_t *y = a[j - 1];
466 [ + + ]: 7171540 : if (!(union_sort_cmp(x, y) < 0))
467 : 5468040 : break;
468 : 1703500 : a[j] = y;
469 : : }
470 : 6801860 : a[j] = x;
471 : : }
472 : 4177010 : }
473 : :
474 : 4182130 : JL_DLLEXPORT jl_value_t *jl_type_union(jl_value_t **ts, size_t n)
475 : : {
476 [ + + ]: 4182130 : if (n == 0)
477 : 2979 : return (jl_value_t*)jl_bottom_type;
478 : : size_t i;
479 [ + + ]: 12841400 : for (i = 0; i < n; i++) {
480 : 8662240 : jl_value_t *pi = ts[i];
481 [ + + + + ]: 8662240 : if (!(jl_is_type(pi) || jl_is_typevar(pi)))
482 : 7 : jl_type_error("Union", (jl_value_t*)jl_type_type, pi);
483 : : }
484 [ + + ]: 4179140 : if (n == 1)
485 : 2133 : return ts[0];
486 : :
487 : 4177010 : size_t nt = count_union_components(ts, n);
488 : : jl_value_t **temp;
489 : 4177010 : JL_GC_PUSHARGS(temp, nt+1);
490 : 4177010 : size_t count = 0;
491 : 4177010 : flatten_type_union(ts, n, temp, &count);
492 [ - + ]: 4177010 : assert(count == nt);
493 : : size_t j;
494 [ + + ]: 15155900 : for (i = 0; i < nt; i++) {
495 [ + - + + ]: 10978900 : int has_free = temp[i] != NULL && jl_has_free_typevars(temp[i]);
496 [ + + ]: 47426800 : for (j = 0; j < nt; j++) {
497 [ + + + + : 36447900 : if (j != i && temp[i] && temp[j]) {
+ + ]
498 [ + + ]: 24190500 : if (temp[i] == jl_bottom_type ||
499 [ + + + + ]: 46313500 : temp[j] == (jl_value_t*)jl_any_type ||
500 [ + + ]: 45993800 : jl_egal(temp[i], temp[j]) ||
501 [ + + + + ]: 13482800 : (!has_free && !jl_has_free_typevars(temp[j]) &&
502 : 6739910 : jl_subtype(temp[i], temp[j]))) {
503 : 1276600 : temp[i] = NULL;
504 : : }
505 : : }
506 : : }
507 : : }
508 : 4177010 : isort_union(temp, nt);
509 : 4177010 : jl_value_t **ptu = &temp[nt];
510 : 4177010 : *ptu = jl_bottom_type;
511 : : int k;
512 [ + + ]: 15155900 : for (k = (int)nt-1; k >= 0; --k) {
513 [ + + ]: 10978900 : if (temp[k] != NULL) {
514 [ + + ]: 9702270 : if (*ptu == jl_bottom_type)
515 : 4177010 : *ptu = temp[k];
516 : : else
517 : 5525260 : *ptu = jl_new_struct(jl_uniontype_type, temp[k], *ptu);
518 : : }
519 : : }
520 [ - + ]: 4177010 : assert(*ptu != NULL);
521 : 4177010 : jl_value_t *tu = *ptu;
522 : 4177010 : JL_GC_POP();
523 : 4177010 : return tu;
524 : : }
525 : :
526 : : // unionall types -------------------------------------------------------------
527 : :
528 : 184775000 : JL_DLLEXPORT jl_value_t *jl_type_unionall(jl_tvar_t *v, jl_value_t *body)
529 : : {
530 [ + + ]: 184775000 : if (jl_is_vararg(body)) {
531 [ + - ]: 1 : if (jl_options.depwarn) {
532 [ + - ]: 1 : if (jl_options.depwarn == JL_OPTIONS_DEPWARN_ERROR)
533 : 1 : jl_error("Wrapping `Vararg` directly in UnionAll is deprecated (wrap the tuple instead).");
534 : 0 : jl_printf(JL_STDERR, "WARNING: Wrapping `Vararg` directly in UnionAll is deprecated (wrap the tuple instead).\n");
535 : : }
536 : 0 : jl_vararg_t *vm = (jl_vararg_t*)body;
537 [ # # # # ]: 0 : int T_has_tv = vm->T && jl_has_typevar(vm->T, v);
538 [ # # # # ]: 0 : int N_has_tv = vm->N && jl_has_typevar(vm->N, v);
539 [ # # # # ]: 0 : if (!T_has_tv && !N_has_tv) {
540 : 0 : return body;
541 : : }
542 [ # # # # ]: 0 : if (T_has_tv && N_has_tv) {
543 : 0 : jl_error("Wrapping `Vararg` directly in UnionAll is disallowed if the typevar occurs in both `T` and `N`");
544 : : }
545 [ # # ]: 0 : if (T_has_tv) {
546 : 0 : jl_value_t *wrapped = jl_type_unionall(v, vm->T);
547 : 0 : JL_GC_PUSH1(&wrapped);
548 : 0 : wrapped = (jl_value_t*)jl_wrap_vararg(wrapped, vm->N);
549 : 0 : JL_GC_POP();
550 : 0 : return wrapped;
551 : : }
552 : : else {
553 [ # # ]: 0 : assert(N_has_tv);
554 [ # # ]: 0 : assert(vm->N == (jl_value_t*)v);
555 : 0 : return (jl_value_t*)jl_wrap_vararg(vm->T, NULL);
556 : : }
557 : : }
558 [ + + + + ]: 184775000 : if (!jl_is_type(body) && !jl_is_typevar(body))
559 : 3 : jl_type_error("UnionAll", (jl_value_t*)jl_type_type, body);
560 : : // normalize `T where T<:S` => S
561 [ + + ]: 184775000 : if (body == (jl_value_t*)v)
562 : 16383700 : return v->ub;
563 : : // where var doesn't occur in body just return body
564 [ + + ]: 168392000 : if (!jl_has_typevar(body, v))
565 : 121670000 : return body;
566 : : //if (v->lb == v->ub) // TODO maybe
567 : : // return jl_substitute_var(body, v, v->ub);
568 : 46722100 : return jl_new_struct(jl_unionall_type, v, body);
569 : : }
570 : :
571 : : // --- type instantiation and cache ---
572 : :
573 : 451293000 : static int typekey_eq(jl_datatype_t *tt, jl_value_t **key, size_t n)
574 : : {
575 : : size_t j;
576 : : // TOOD: This shouldn't be necessary
577 : : JL_GC_PROMISE_ROOTED(tt);
578 : 451293000 : size_t tnp = jl_nparams(tt);
579 [ + + ]: 451293000 : if (n != tnp)
580 : 433 : return 0;
581 [ + + ]: 451293000 : if (tt->name == jl_type_typename) {
582 : : // for Type{T}, require `typeof(T)` to match also, to avoid incorrect
583 : : // dispatch from changing the type of something.
584 : : // this should work because `Type`s don't have uids, and aren't the
585 : : // direct tags of values so we don't rely on pointer equality.
586 : 372564000 : jl_value_t *kj = key[0];
587 : 372564000 : jl_value_t *tj = jl_tparam0(tt);
588 [ + + + + : 372564000 : return (kj == tj || (jl_typeof(tj) == jl_typeof(kj) && jl_types_equal(tj, kj)));
+ + ]
589 : : }
590 [ + + ]: 233729000 : for (j = 0; j < n; j++) {
591 : 161023000 : jl_value_t *kj = key[j];
592 : 161023000 : jl_value_t *tj = jl_svecref(tt->parameters, j);
593 [ + + ]: 161023000 : if (tj != kj) {
594 : : // require exact same Type{T}. see e.g. issue #22842
595 [ + + + + ]: 6311920 : if (jl_is_type_type(tj) || jl_is_type_type(kj))
596 : 5461 : return 0;
597 [ + + + + : 6435960 : if ((jl_is_concrete_type(tj) || jl_is_concrete_type(kj)) &&
+ + ]
598 : 129501 : jl_type_equality_is_identity(tj, kj))
599 : 91054 : return 0;
600 [ + + ]: 6215410 : if (!jl_types_equal(tj, kj))
601 : 5926370 : return 0;
602 : : }
603 : : }
604 : 72705400 : return 1;
605 : : }
606 : :
607 : : // These `value` functions return the same values as the primary functions,
608 : : // but operate on the typeof/Typeof each object in an array
609 : 150154000 : static int typekeyvalue_eq(jl_datatype_t *tt, jl_value_t *key1, jl_value_t **key, size_t n, int leaf)
610 : : {
611 : : size_t j;
612 : : // TOOD: This shouldn't be necessary
613 : : JL_GC_PROMISE_ROOTED(tt);
614 : 150154000 : size_t tnp = jl_nparams(tt);
615 [ + + ]: 150154000 : if (n != tnp)
616 : 346 : return 0;
617 [ + + - + ]: 150153000 : if (leaf && tt->name == jl_type_typename) {
618 : : // for Type{T}, require `typeof(T)` to match also, to avoid incorrect
619 : : // dispatch from changing the type of something.
620 : : // this should work because `Type`s don't have uids, and aren't the
621 : : // direct tags of values so we don't rely on pointer equality.
622 : 0 : jl_value_t *kj = key1;
623 : 0 : jl_value_t *tj = jl_tparam0(tt);
624 [ # # # # : 0 : return (kj == tj || (jl_typeof(tj) == jl_typeof(kj) && jl_types_equal(tj, kj)));
# # ]
625 : : }
626 [ + + ]: 549690000 : for (j = 0; j < n; j++) {
627 [ + + ]: 399537000 : jl_value_t *kj = j == 0 ? key1 : key[j - 1];
628 : 399537000 : jl_value_t *tj = jl_svecref(tt->parameters, j);
629 [ + + + + ]: 481034000 : if (leaf && jl_is_type_type(tj)) {
630 : 81497200 : jl_value_t *tp0 = jl_tparam0(tj);
631 [ + + + + : 81497200 : if (!(kj == tp0 || (jl_typeof(tp0) == jl_typeof(kj) && jl_types_equal(tp0, kj))))
+ + ]
632 : 13 : return 0;
633 : : }
634 [ + + ]: 318040000 : else if (jl_typeof(kj) != tj) {
635 : 39 : return 0;
636 : : }
637 [ + + + + ]: 318040000 : else if (leaf && jl_is_kind(tj)) {
638 : 520 : return 0;
639 : : }
640 : : }
641 : 150153000 : return 1;
642 : : }
643 : :
644 : : static unsigned typekey_hash(jl_typename_t *tn, jl_value_t **key, size_t n, int nofail) JL_NOTSAFEPOINT;
645 : : static unsigned typekeyvalue_hash(jl_typename_t *tn, jl_value_t *key1, jl_value_t **key, size_t n, int leaf) JL_NOTSAFEPOINT;
646 : :
647 : : /* returns val if key is in hash, otherwise NULL */
648 : 82251500 : static jl_datatype_t *lookup_type_set(jl_svec_t *cache, jl_value_t **key, size_t n, uint_t hv)
649 : : {
650 : 82251500 : size_t sz = jl_svec_len(cache);
651 [ + + ]: 82251500 : if (sz == 0)
652 : 13804 : return NULL;
653 [ + + ]: 82237700 : size_t maxprobe = max_probe(sz);
654 : 82237700 : _Atomic(jl_datatype_t*) *tab = (_Atomic(jl_datatype_t*)*)jl_svec_data(cache);
655 : 82237700 : size_t index = h2index(hv, sz);
656 : 82237700 : size_t orig = index;
657 : 82237700 : size_t iter = 0;
658 : : do {
659 : 169478000 : jl_datatype_t *val = jl_atomic_load_relaxed(&tab[index]);
660 [ + + ]: 169478000 : if (val == NULL)
661 : 4379230 : return NULL;
662 [ + + + + : 165099000 : if ((jl_value_t*)val != jl_nothing && val->hash == hv && typekey_eq(val, key, n))
+ + ]
663 : 77856800 : return val;
664 : 87242400 : index = (index + 1) & (sz - 1);
665 : 87242400 : iter++;
666 [ + + + - ]: 87242400 : } while (iter <= maxprobe && index != orig);
667 : 1636 : return NULL;
668 : : }
669 : :
670 : : /* returns val if key is in hash, otherwise NULL */
671 : 161757000 : static jl_datatype_t *lookup_type_setvalue(jl_svec_t *cache, jl_value_t *key1, jl_value_t **key, size_t n, uint_t hv, int leaf)
672 : : {
673 : 161757000 : size_t sz = jl_svec_len(cache);
674 [ - + ]: 161757000 : if (sz == 0)
675 : 0 : return NULL;
676 [ + + ]: 161757000 : size_t maxprobe = max_probe(sz);
677 : 161757000 : _Atomic(jl_datatype_t*) *tab = (_Atomic(jl_datatype_t*)*)jl_svec_data(cache);
678 : 161757000 : size_t index = h2index(hv, sz);
679 : 161757000 : size_t orig = index;
680 : 161757000 : size_t iter = 0;
681 : : do {
682 : 278698000 : jl_datatype_t *val = jl_atomic_load_relaxed(&tab[index]);
683 [ + + ]: 278698000 : if (val == NULL)
684 : 11604300 : return NULL;
685 [ + + + + : 267093000 : if ((jl_value_t*)val != jl_nothing && val->hash == hv && typekeyvalue_eq(val, key1, key, n, leaf))
+ + ]
686 : 150153000 : return val;
687 : 116941000 : index = (index + 1) & (sz - 1);
688 : 116941000 : iter++;
689 [ + + + # ]: 116941000 : } while (iter <= maxprobe && index != orig);
690 : 381 : return NULL;
691 : : }
692 : :
693 : : // look up a type in a cache by binary or linear search.
694 : : // if found, returns the index of the found item. if not found, returns
695 : : // ~n, where n is the index where the type should be inserted.
696 : 1136230 : static ssize_t lookup_type_idx_linear(jl_svec_t *cache, jl_value_t **key, size_t n)
697 : : {
698 [ - + ]: 1136230 : if (n == 0)
699 : 0 : return -1;
700 : 1136230 : _Atomic(jl_datatype_t*) *data = (_Atomic(jl_datatype_t*)*)jl_svec_data(cache);
701 : 1136230 : size_t cl = jl_svec_len(cache);
702 : : ssize_t i;
703 [ + + ]: 373461000 : for (i = 0; i < cl; i++) {
704 : 373460000 : jl_datatype_t *tt = jl_atomic_load_relaxed(&data[i]);
705 [ + + ]: 373460000 : if (tt == NULL)
706 : 30459 : return ~i;
707 [ + + ]: 373429000 : if (typekey_eq(tt, key, n))
708 : 1104000 : return i;
709 : : }
710 : 1767 : return ~cl;
711 : : }
712 : :
713 : 6625900 : static ssize_t lookup_type_idx_linearvalue(jl_svec_t *cache, jl_value_t *key1, jl_value_t **key, size_t n)
714 : : {
715 [ - + ]: 6625900 : if (n == 0)
716 : 0 : return -1;
717 : 6625900 : _Atomic(jl_datatype_t*) *data = (_Atomic(jl_datatype_t*)*)jl_svec_data(cache);
718 : 6625900 : size_t cl = jl_svec_len(cache);
719 : : ssize_t i;
720 [ - + ]: 6625900 : for (i = 0; i < cl; i++) {
721 : 0 : jl_datatype_t *tt = jl_atomic_load_relaxed(&data[i]);
722 [ # # ]: 0 : if (tt == NULL)
723 : 0 : return ~i;
724 [ # # ]: 0 : if (typekeyvalue_eq(tt, key1, key, n, 1))
725 : 0 : return i;
726 : : }
727 : 6625900 : return ~cl;
728 : : }
729 : :
730 : 117501000 : static jl_value_t *lookup_type(jl_typename_t *tn JL_PROPAGATES_ROOT, jl_value_t **key, size_t n)
731 : : {
732 : : JL_TIMING(TYPE_CACHE_LOOKUP);
733 [ + + ]: 117501000 : if (tn == jl_type_typename) {
734 [ - + ]: 40604000 : assert(n == 1);
735 : 40604000 : jl_value_t *uw = jl_unwrap_unionall(key[0]);
736 [ + + + + ]: 40604000 : if (jl_is_datatype(uw) && key[0] == ((jl_datatype_t*)uw)->name->wrapper)
737 : 34123700 : return jl_atomic_load_acquire(&((jl_datatype_t*)uw)->name->Typeofwrapper);
738 : : }
739 : 83377300 : unsigned hv = typekey_hash(tn, key, n, 0);
740 [ + + ]: 83377300 : if (hv) {
741 : 82251500 : jl_svec_t *cache = jl_atomic_load_relaxed(&tn->cache);
742 : 82251500 : return (jl_value_t*)lookup_type_set(cache, key, n, hv);
743 : : }
744 : : else {
745 : 1125760 : jl_svec_t *linearcache = jl_atomic_load_relaxed(&tn->linearcache);
746 : 1125760 : ssize_t idx = lookup_type_idx_linear(linearcache, key, n);
747 [ + + ]: 1125760 : return (idx < 0) ? NULL : jl_svecref(linearcache, idx);
748 : : }
749 : : }
750 : :
751 : 168383000 : static jl_value_t *lookup_typevalue(jl_typename_t *tn, jl_value_t *key1, jl_value_t **key, size_t n, int leaf)
752 : : {
753 : : JL_TIMING(TYPE_CACHE_LOOKUP);
754 : 168383000 : unsigned hv = typekeyvalue_hash(tn, key1, key, n, leaf);
755 [ + + ]: 168383000 : if (hv) {
756 : 161757000 : jl_svec_t *cache = jl_atomic_load_relaxed(&tn->cache);
757 : 161757000 : return (jl_value_t*)lookup_type_setvalue(cache, key1, key, n, hv, leaf);
758 : : }
759 : : else {
760 [ - + ]: 6625900 : assert(leaf);
761 : 6625900 : jl_svec_t *linearcache = jl_atomic_load_relaxed(&tn->linearcache);
762 : 6625900 : ssize_t idx = lookup_type_idx_linearvalue(linearcache, key1, key, n);
763 [ - + ]: 6625900 : return (idx < 0) ? NULL : jl_svecref(linearcache, idx);
764 : : }
765 : : }
766 : :
767 : 3383830 : static int cache_insert_type_set_(jl_svec_t *a, jl_datatype_t *val, uint_t hv, int atomic)
768 : : {
769 : 3383830 : _Atomic(jl_value_t*) *tab = (_Atomic(jl_value_t*)*)jl_svec_data(a);
770 : 3383830 : size_t sz = jl_svec_len(a);
771 [ + + ]: 3383830 : if (sz <= 1)
772 : 6921 : return 0;
773 : : size_t orig, index, iter;
774 : 3376910 : iter = 0;
775 : 3376910 : index = h2index(hv, sz);
776 : 3376910 : orig = index;
777 [ + + ]: 3376910 : size_t maxprobe = max_probe(sz);
778 : : do {
779 : 15627700 : jl_value_t *tab_i = jl_atomic_load_relaxed(&tab[index]);
780 [ + + + + ]: 15627700 : if (tab_i == NULL || tab_i == jl_nothing) {
781 [ + + ]: 3376130 : if (atomic)
782 : 2186650 : jl_atomic_store_release(&tab[index], (jl_value_t*)val);
783 : : else
784 : 1189480 : jl_atomic_store_relaxed(&tab[index], (jl_value_t*)val);
785 : 3376130 : jl_gc_wb(a, val);
786 : 3376130 : return 1;
787 : : }
788 : 12251500 : index = (index + 1) & (sz - 1);
789 : 12251500 : iter++;
790 [ + + + - ]: 12251500 : } while (iter <= maxprobe && index != orig);
791 : :
792 : 785 : return 0;
793 : : }
794 : :
795 : : static jl_svec_t *cache_rehash_set(jl_svec_t *a, size_t newsz);
796 : :
797 : 2186650 : static void cache_insert_type_set(jl_datatype_t *val, uint_t hv)
798 : : {
799 : 2186650 : jl_svec_t *a = jl_atomic_load_relaxed(&val->name->cache);
800 : 7706 : while (1) {
801 : : JL_GC_PROMISE_ROOTED(a);
802 [ + + ]: 2194350 : if (cache_insert_type_set_(a, val, hv, 1))
803 : 2186650 : return;
804 : :
805 : : /* table full */
806 : : /* rehash to grow and retry the insert */
807 : : /* it's important to grow the table really fast; otherwise we waste */
808 : : /* lots of time rehashing all the keys over and over. */
809 : : size_t newsz;
810 : 7706 : size_t sz = jl_svec_len(a);
811 [ + + ]: 7706 : if (sz < HT_N_INLINE)
812 : 6921 : newsz = HT_N_INLINE;
813 [ + - + + ]: 785 : else if (sz >= (1 << 19) || (sz <= (1 << 8)))
814 : 612 : newsz = sz << 1;
815 : : else
816 : 173 : newsz = sz << 2;
817 : 7706 : a = cache_rehash_set(a, newsz);
818 : 7706 : jl_atomic_store_release(&val->name->cache, a);
819 : 7706 : jl_gc_wb(val->name, a);
820 : : }
821 : : }
822 : :
823 : 7706 : static jl_svec_t *cache_rehash_set(jl_svec_t *a, size_t newsz)
824 : : {
825 : 7706 : jl_value_t **ol = jl_svec_data(a);
826 : 7706 : size_t sz = jl_svec_len(a);
827 : 0 : while (1) {
828 : : size_t i;
829 : 7706 : jl_svec_t *newa = jl_alloc_svec(newsz);
830 : 7706 : JL_GC_PUSH1(&newa);
831 [ + + ]: 1313020 : for (i = 0; i < sz; i += 1) {
832 : 1305310 : jl_value_t *val = ol[i];
833 [ + + + + ]: 1305310 : if (val != NULL && val != jl_nothing) {
834 : 1189480 : uint_t hv = ((jl_datatype_t*)val)->hash;
835 [ - + ]: 1189480 : if (!cache_insert_type_set_(newa, (jl_datatype_t*)val, hv, 0)) {
836 : 0 : break;
837 : : }
838 : : }
839 : : }
840 : 7706 : JL_GC_POP();
841 [ + - ]: 7706 : if (i == sz)
842 : 7706 : return newa;
843 : 0 : newsz <<= 1;
844 : : }
845 : : }
846 : :
847 : 10467 : static void cache_insert_type_linear(jl_datatype_t *type, ssize_t insert_at)
848 : : {
849 : 10467 : jl_svec_t *cache = jl_atomic_load_relaxed(&type->name->linearcache);
850 [ - + ]: 10467 : assert(jl_is_svec(cache));
851 : 10467 : size_t n = jl_svec_len(cache);
852 [ + + + + ]: 10467 : if (n == 0 || jl_svecref(cache, n - 1) != NULL) {
853 [ + + ]: 314 : jl_svec_t *nc = jl_alloc_svec(n < 8 ? 8 : (n*3)>>1);
854 : 314 : memcpy(jl_svec_data(nc), jl_svec_data(cache), sizeof(void*) * n);
855 : 314 : jl_atomic_store_release(&type->name->linearcache, nc);
856 : 314 : jl_gc_wb(type->name, nc);
857 : 314 : cache = nc;
858 : 314 : n = jl_svec_len(nc);
859 : : }
860 [ - + ]: 10467 : assert(jl_svecref(cache, insert_at) == NULL);
861 : 10467 : jl_svecset(cache, insert_at, (jl_value_t*)type); // todo: make this an atomic-store
862 : 10467 : }
863 : :
864 : : #ifndef NDEBUG
865 : 3793370 : static int is_cacheable(jl_datatype_t *type)
866 : : {
867 : : // ensure cache only contains types whose behavior will not depend on the
868 : : // identities of contained TypeVars
869 : 3793370 : return !jl_has_free_typevars((jl_value_t*)type);
870 : : }
871 : : #endif
872 : :
873 : :
874 : 2206160 : void jl_cache_type_(jl_datatype_t *type)
875 : : {
876 : : JL_TIMING(TYPE_CACHE_INSERT);
877 [ - + ]: 2206160 : assert(is_cacheable(type));
878 : 2206160 : jl_value_t **key = jl_svec_data(type->parameters);
879 : 2206160 : int n = jl_svec_len(type->parameters);
880 [ + + ]: 2206160 : if (type->name == jl_type_typename) {
881 [ - + ]: 121556 : assert(n == 1);
882 : 121556 : jl_value_t *uw = jl_unwrap_unionall(key[0]);
883 [ + + + + ]: 121556 : if (jl_is_datatype(uw) && key[0] == ((jl_datatype_t*)uw)->name->wrapper) {
884 : 9047 : jl_typename_t *tn2 = ((jl_datatype_t*)uw)->name;
885 : 9047 : jl_atomic_store_release(&tn2->Typeofwrapper, (jl_value_t*)type);
886 : 9047 : jl_gc_wb(tn2, type);
887 : 9047 : return;
888 : : }
889 : : }
890 : 2197110 : unsigned hv = typekey_hash(type->name, key, n, 0);
891 [ + + ]: 2197110 : if (hv) {
892 [ - + ]: 2186650 : assert(hv == type->hash);
893 : 2186650 : cache_insert_type_set(type, hv);
894 : : }
895 : : else {
896 : 10467 : ssize_t idx = lookup_type_idx_linear(jl_atomic_load_relaxed(&type->name->linearcache), key, n);
897 [ - + ]: 10467 : assert(idx < 0);
898 : 10467 : cache_insert_type_linear(type, ~idx);
899 : : }
900 : : }
901 : :
902 : 1587210 : jl_datatype_t *jl_lookup_cache_type_(jl_datatype_t *type)
903 : : {
904 [ - + ]: 1587210 : assert(is_cacheable(type));
905 : 1587210 : jl_value_t **key = jl_svec_data(type->parameters);
906 : 1587210 : int n = jl_svec_len(type->parameters);
907 : 1587210 : return (jl_datatype_t*)lookup_type(type->name, key, n);
908 : : }
909 : :
910 : 2233280000 : JL_DLLEXPORT int jl_type_equality_is_identity(jl_value_t *t1, jl_value_t *t2)
911 : : {
912 [ - + ]: 2233280000 : if (t1 == t2)
913 : 0 : return 1;
914 [ + + + + ]: 2233280000 : if (!jl_is_datatype(t1) || !jl_is_datatype(t2))
915 : 21004 : return 0;
916 : 2233260000 : jl_datatype_t *dt1 = (jl_datatype_t *) t1;
917 : 2233260000 : jl_datatype_t *dt2 = (jl_datatype_t *) t2;
918 : :
919 : 2233260000 : return dt1->cached_by_hash == dt2->cached_by_hash;
920 : : }
921 : :
922 : : // type instantiation
923 : :
924 : 415663000 : static int within_typevar(jl_value_t *t, jl_value_t *vlb, jl_value_t *vub)
925 : : {
926 : 415663000 : jl_value_t *lb = t, *ub = t;
927 [ + + + + ]: 415663000 : if (jl_is_typevar(t) || jl_has_free_typevars(t)) {
928 : : // TODO: automatically restrict typevars in method definitions based on
929 : : // types they are used in.
930 : 247794000 : return 1;
931 : : //lb = ((jl_tvar_t*)t)->lb;
932 : : //ub = ((jl_tvar_t*)t)->ub;
933 : : }
934 [ + + ]: 167869000 : else if (!jl_is_type(t)) {
935 [ + - + + ]: 125620000 : return vlb == jl_bottom_type && vub == (jl_value_t*)jl_any_type;
936 : : }
937 [ + - + + : 126614000 : return ((jl_has_free_typevars(vlb) || jl_subtype(vlb, lb)) &&
+ + ]
938 [ + + ]: 84365100 : (jl_has_free_typevars(vub) || jl_subtype(ub, vub)));
939 : : }
940 : :
941 : : struct _jl_typestack_t;
942 : : typedef struct _jl_typestack_t jl_typestack_t;
943 : :
944 : : static jl_value_t *inst_datatype_inner(jl_datatype_t *dt, jl_svec_t *p, jl_value_t **iparams, size_t ntp,
945 : : jl_typestack_t *stack, jl_typeenv_t *env);
946 : :
947 : : // Build an environment mapping a TypeName's parameters to parameter values.
948 : : // This is the environment needed for instantiating a type's supertype and field types.
949 : 92999000 : static jl_value_t *inst_datatype_env(jl_value_t *dt, jl_svec_t *p, jl_value_t **iparams, size_t ntp,
950 : : jl_typestack_t *stack, jl_typeenv_t *env, int c)
951 : : {
952 [ + + ]: 92999000 : if (jl_is_datatype(dt))
953 : 26605900 : return inst_datatype_inner((jl_datatype_t*)dt, p, iparams, ntp, stack, env);
954 [ - + ]: 66393100 : assert(jl_is_unionall(dt));
955 : 66393100 : jl_unionall_t *ua = (jl_unionall_t*)dt;
956 : 66393100 : jl_typeenv_t e = { ua->var, iparams[c], env };
957 : 66393100 : return inst_datatype_env(ua->body, p, iparams, ntp, stack, &e, c + 1);
958 : : }
959 : :
960 : 62900300 : jl_value_t *jl_apply_type(jl_value_t *tc, jl_value_t **params, size_t n)
961 : : {
962 [ + + ]: 62900300 : if (tc == (jl_value_t*)jl_anytuple_type)
963 : 20486 : return (jl_value_t*)jl_apply_tuple_type_v(params, n);
964 [ - + ]: 62879900 : if (tc == (jl_value_t*)jl_uniontype_type)
965 : 0 : return (jl_value_t*)jl_type_union(params, n);
966 : : size_t i;
967 [ + + ]: 62879900 : if (n > 1) {
968 : : // detect common case of applying a wrapper, where we know that all parameters will
969 : : // end up as direct parameters of a certain datatype, which can be optimized.
970 : 26632300 : jl_value_t *u = jl_unwrap_unionall(tc);
971 [ + + + + ]: 26632300 : if (jl_is_datatype(u) && n == jl_nparams((jl_datatype_t*)u) &&
972 [ + + ]: 26606000 : ((jl_datatype_t*)u)->name->wrapper == tc) {
973 : 26605900 : return inst_datatype_env(tc, NULL, params, n, NULL, NULL, 0);
974 : : }
975 : : }
976 : 36273900 : JL_GC_PUSH1(&tc);
977 : 36273900 : jl_value_t *tc0 = tc;
978 [ + + ]: 72564300 : for (i=0; i < n; i++) {
979 [ + + ]: 36290500 : if (!jl_is_unionall(tc0))
980 : 4 : jl_error("too many parameters for type");
981 : 36290500 : jl_value_t *pi = params[i];
982 : :
983 : 36290500 : tc0 = ((jl_unionall_t*)tc0)->body;
984 : : // doing a substitution can cause later UnionAlls to be dropped,
985 : : // as in `NTuple{0,T} where T` => `Tuple{}`. allow values to be
986 : : // substituted for these missing parameters.
987 : : // TODO: figure out how to get back a type error for e.g.
988 : : // S = Tuple{Vararg{T,N}} where T<:NTuple{N} where N
989 : : // S{0,Int}
990 [ + + ]: 36290500 : if (!jl_is_unionall(tc)) continue;
991 : :
992 : 36290500 : jl_unionall_t *ua = (jl_unionall_t*)tc;
993 [ + - + + : 72580800 : if (!jl_has_free_typevars(ua->var->lb) && !jl_has_free_typevars(ua->var->ub) &&
+ + ]
994 : 36290300 : !within_typevar(pi, ua->var->lb, ua->var->ub)) {
995 : 17 : jl_datatype_t *inner = (jl_datatype_t*)jl_unwrap_unionall(tc);
996 : 17 : int iswrapper = 0;
997 [ + - ]: 17 : if (jl_is_datatype(inner)) {
998 : 17 : jl_value_t *temp = inner->name->wrapper;
999 [ + + ]: 19 : while (jl_is_unionall(temp)) {
1000 [ + + ]: 18 : if (temp == tc) {
1001 : 16 : iswrapper = 1;
1002 : 16 : break;
1003 : : }
1004 : 2 : temp = ((jl_unionall_t*)temp)->body;
1005 : : }
1006 : : }
1007 : : // if this is a wrapper, let check_datatype_parameters give the error
1008 [ + + ]: 17 : if (!iswrapper)
1009 [ + - ]: 1 : jl_type_error_rt(jl_is_datatype(inner) ? jl_symbol_name(inner->name->name) : "Type",
1010 : 1 : jl_symbol_name(ua->var->name), (jl_value_t*)ua->var, pi);
1011 : : }
1012 : :
1013 : 36290400 : tc = jl_instantiate_unionall(ua, pi);
1014 : : }
1015 : 36273900 : JL_GC_POP();
1016 : 36273900 : return tc;
1017 : : }
1018 : :
1019 : 1575550 : JL_DLLEXPORT jl_value_t *jl_apply_type1(jl_value_t *tc, jl_value_t *p1)
1020 : : {
1021 : 1575550 : return jl_apply_type(tc, &p1, 1);
1022 : : }
1023 : :
1024 : 10095000 : JL_DLLEXPORT jl_value_t *jl_apply_type2(jl_value_t *tc, jl_value_t *p1, jl_value_t *p2)
1025 : : {
1026 : : jl_value_t *args[2];
1027 : 10095000 : args[0] = p1;
1028 : 10095000 : args[1] = p2;
1029 : 10095000 : return jl_apply_type(tc, args, 2);
1030 : : }
1031 : :
1032 : 197 : jl_datatype_t *jl_apply_modify_type(jl_value_t *dt)
1033 : : {
1034 : 197 : jl_datatype_t *rettyp = (jl_datatype_t*)jl_apply_type2(jl_pair_type, dt, dt);
1035 : : JL_GC_PROMISE_ROOTED(rettyp); // (JL_ALWAYS_LEAFTYPE)
1036 : 197 : return rettyp;
1037 : : }
1038 : :
1039 : 7350 : jl_datatype_t *jl_apply_cmpswap_type(jl_value_t *dt)
1040 : : {
1041 : : jl_value_t *params[2];
1042 : 7350 : jl_value_t *names = jl_atomic_load_relaxed(&cmpswap_names);
1043 [ + + ]: 7350 : if (names == NULL) {
1044 : 26 : params[0] = (jl_value_t*)jl_symbol("old");
1045 : 26 : params[1] = (jl_value_t*)jl_symbol("success");
1046 : 26 : jl_value_t *lnames = jl_f_tuple(NULL, params, 2);
1047 [ + - ]: 26 : if (jl_atomic_cmpswap(&cmpswap_names, &names, lnames))
1048 : 26 : names = jl_atomic_load_relaxed(&cmpswap_names); // == lnames
1049 : : }
1050 : 7350 : params[0] = dt;
1051 : 7350 : params[1] = (jl_value_t*)jl_bool_type;
1052 : 7350 : jl_datatype_t *tuptyp = jl_apply_tuple_type_v(params, 2);
1053 : : JL_GC_PROMISE_ROOTED(tuptyp); // (JL_ALWAYS_LEAFTYPE)
1054 : 7350 : jl_datatype_t *rettyp = (jl_datatype_t*)jl_apply_type2((jl_value_t*)jl_namedtuple_type, names, (jl_value_t*)tuptyp);
1055 : : JL_GC_PROMISE_ROOTED(rettyp); // (JL_ALWAYS_LEAFTYPE)
1056 : 7350 : return rettyp;
1057 : : }
1058 : :
1059 : 53591 : JL_DLLEXPORT jl_value_t *jl_tupletype_fill(size_t n, jl_value_t *v)
1060 : : {
1061 : : // TODO: replace with just using NTuple
1062 : 53591 : jl_value_t *p = NULL;
1063 : 53591 : JL_GC_PUSH1(&p);
1064 : 53591 : p = (jl_value_t*)jl_svec_fill(n, v);
1065 : 53591 : p = (jl_value_t*)jl_apply_tuple_type((jl_svec_t*)p);
1066 : 53591 : JL_GC_POP();
1067 : 53591 : return p;
1068 : : }
1069 : :
1070 : : JL_EXTENSION struct _jl_typestack_t {
1071 : : jl_datatype_t *tt;
1072 : : struct _jl_typestack_t *prev;
1073 : : };
1074 : :
1075 : : static jl_value_t *inst_type_w_(jl_value_t *t, jl_typeenv_t *env, jl_typestack_t *stack, int check);
1076 : : static jl_svec_t *inst_ftypes(jl_svec_t *p, jl_typeenv_t *env, jl_typestack_t *stack);
1077 : :
1078 : 169676000 : JL_DLLEXPORT jl_value_t *jl_instantiate_unionall(jl_unionall_t *u, jl_value_t *p)
1079 : : {
1080 : 169676000 : jl_typeenv_t env = { u->var, p, NULL };
1081 : 169676000 : return inst_type_w_(u->body, &env, NULL, 1);
1082 : : }
1083 : :
1084 : 147504000 : jl_value_t *jl_substitute_var(jl_value_t *t, jl_tvar_t *var, jl_value_t *val)
1085 : : {
1086 : 147504000 : jl_typeenv_t env = { var, val, NULL };
1087 : 147504000 : return inst_type_w_(t, &env, NULL, 1);
1088 : : }
1089 : :
1090 :13407100000 : jl_value_t *jl_unwrap_unionall(jl_value_t *v)
1091 : : {
1092 [ + + ]:22497800000 : while (jl_is_unionall(v))
1093 : 9090650000 : v = ((jl_unionall_t*)v)->body;
1094 :13407100000 : return v;
1095 : : }
1096 : :
1097 : : // wrap `t` in the same unionalls that surround `u`
1098 : 17245700 : jl_value_t *jl_rewrap_unionall(jl_value_t *t, jl_value_t *u)
1099 : : {
1100 [ + + ]: 17245700 : if (!jl_is_unionall(u))
1101 : 3892820 : return t;
1102 : 13352900 : JL_GC_PUSH1(&t);
1103 : 13352900 : t = jl_rewrap_unionall(t, ((jl_unionall_t*)u)->body);
1104 : 13352900 : t = jl_new_struct(jl_unionall_type, ((jl_unionall_t*)u)->var, t);
1105 : 13352900 : JL_GC_POP();
1106 : 13352900 : return t;
1107 : : }
1108 : :
1109 : 187502000 : static jl_value_t *lookup_type_stack(jl_typestack_t *stack, jl_datatype_t *tt, size_t ntp,
1110 : : jl_value_t **iparams)
1111 : : {
1112 : : // if an identical instantiation is already in process somewhere up the
1113 : : // stack, return it. this computes a fixed point for recursive types.
1114 : 187502000 : jl_typename_t *tn = tt->name;
1115 [ + + ]: 215414000 : while (stack != NULL) {
1116 : : JL_GC_PROMISE_ROOTED(stack->tt);
1117 [ + + ]: 27912500 : if (stack->tt->name == tn &&
1118 [ + - + + ]: 3164 : ntp == jl_svec_len(stack->tt->parameters) &&
1119 : 1582 : typekey_eq(stack->tt, iparams, ntp)) {
1120 : 59 : return (jl_value_t*)stack->tt;
1121 : : }
1122 : 27912500 : stack = stack->prev;
1123 : : }
1124 : 187501000 : return NULL;
1125 : : }
1126 : :
1127 : : // stable numbering for types--starts with name->hash, then falls back to objectid
1128 : : // sets failed if the hash value isn't stable (if not set on entry)
1129 : 826989000 : static unsigned type_hash(jl_value_t *kj, int *failed) JL_NOTSAFEPOINT
1130 : : {
1131 [ + + ]: 826989000 : jl_value_t *uw = jl_is_unionall(kj) ? jl_unwrap_unionall(kj) : kj;
1132 [ + + ]: 826989000 : if (jl_is_datatype(uw)) {
1133 : 570487000 : jl_datatype_t *dt = (jl_datatype_t*)uw;
1134 : 570487000 : unsigned hash = dt->hash;
1135 [ + + ]: 570487000 : if (!hash) {
1136 [ + + ]: 21859100 : if (!*failed) {
1137 : 21857000 : *failed = 1;
1138 : 21857000 : return 0;
1139 : : }
1140 : 2110 : hash = typekey_hash(dt->name, jl_svec_data(dt->parameters), jl_svec_len(dt->parameters), *failed);
1141 : : }
1142 : 548630000 : return hash;
1143 : : }
1144 [ + + ]: 256502000 : else if (jl_is_typevar(uw)) {
1145 [ + + ]: 157081000 : if (!*failed) {
1146 : 157079000 : *failed = 1;
1147 : 157079000 : return 0;
1148 : : }
1149 : : // ignore var and lb, since those might get normalized out in equality testing
1150 : 1733 : return type_hash(((jl_tvar_t*)uw)->ub, failed);
1151 : : }
1152 [ + + ]: 99421400 : else if (jl_is_vararg(uw)) {
1153 [ + + ]: 680493 : if (!*failed) {
1154 : 680304 : *failed = 1;
1155 : 680304 : return 0;
1156 : : }
1157 : 189 : jl_vararg_t *vm = (jl_vararg_t *)uw;
1158 : : // 0x064eeaab is just a randomly chosen constant
1159 [ + + + - ]: 189 : return bitmix(type_hash(vm->T ? vm->T : (jl_value_t*)jl_any_type, failed), vm->N ? type_hash(vm->N, failed) : 0x064eeaab);
1160 : : }
1161 [ + + ]: 98740900 : else if (jl_is_uniontype(uw)) {
1162 [ + + ]: 2694150 : if (!*failed) {
1163 : 2692270 : *failed = 1;
1164 : 2692270 : return 0;
1165 : : }
1166 : 1874 : unsigned hasha = type_hash(((jl_uniontype_t*)uw)->a, failed);
1167 : 1874 : unsigned hashb = type_hash(((jl_uniontype_t*)uw)->b, failed);
1168 : : // use a associative mixing function, with well-defined overflow
1169 : : // since Union is associative
1170 : 1874 : return hasha + hashb;
1171 : : }
1172 : : else {
1173 : 96046700 : return jl_object_id(uw);
1174 : : }
1175 : : }
1176 : :
1177 : 377931000 : static unsigned typekey_hash(jl_typename_t *tn, jl_value_t **key, size_t n, int nofail) JL_NOTSAFEPOINT
1178 : : {
1179 [ + + + + ]: 377931000 : if (tn == jl_type_typename && key[0] == jl_bottom_type)
1180 : 708166 : return jl_typeofbottom_type->hash;
1181 : : size_t j;
1182 : 377222000 : unsigned hash = 3;
1183 : 377222000 : int failed = nofail;
1184 [ + + ]: 1021900000 : for (j = 0; j < n; j++) {
1185 : 826983000 : hash = bitmix(type_hash(key[j], &failed), hash);
1186 [ + + + + ]: 826983000 : if (failed && !nofail)
1187 : 182309000 : return 0;
1188 : : }
1189 : 194914000 : hash = bitmix(~tn->hash, hash);
1190 [ + - ]: 194914000 : return hash ? hash : 1;
1191 : : }
1192 : :
1193 : 168383000 : static unsigned typekeyvalue_hash(jl_typename_t *tn, jl_value_t *key1, jl_value_t **key, size_t n, int leaf) JL_NOTSAFEPOINT
1194 : : {
1195 : : size_t j;
1196 : 168383000 : unsigned hash = 3;
1197 [ + + ]: 663712000 : for (j = 0; j < n; j++) {
1198 [ + + ]: 501955000 : jl_value_t *kj = j == 0 ? key1 : key[j - 1];
1199 : : uint_t hj;
1200 [ + + + + ]: 501955000 : if (leaf && jl_is_kind(jl_typeof(kj))) {
1201 : 103257000 : hj = typekey_hash(jl_type_typename, &kj, 1, 0);
1202 [ + + ]: 103257000 : if (hj == 0)
1203 : 6625900 : return 0;
1204 : : }
1205 : : else {
1206 : 398697000 : hj = ((jl_datatype_t*)jl_typeof(kj))->hash;
1207 : : }
1208 : 495329000 : hash = bitmix(hj, hash);
1209 : : }
1210 : 161757000 : hash = bitmix(~tn->hash, hash);
1211 [ + - ]: 161757000 : return hash ? hash : 1;
1212 : : }
1213 : :
1214 : 187220000 : void jl_precompute_memoized_dt(jl_datatype_t *dt, int cacheable)
1215 : : {
1216 : 187220000 : int istuple = (dt->name == jl_tuple_typename);
1217 : 187220000 : dt->hasfreetypevars = 0;
1218 : 187220000 : dt->isconcretetype = !dt->name->abstract;
1219 : 187220000 : dt->isdispatchtuple = istuple;
1220 : 187220000 : size_t i, l = jl_nparams(dt);
1221 [ + + ]: 684561000 : for (i = 0; i < l; i++) {
1222 : 497341000 : jl_value_t *p = jl_tparam(dt, i);
1223 [ + + ]: 497341000 : if (!dt->hasfreetypevars) {
1224 : 364120000 : dt->hasfreetypevars = jl_has_free_typevars(p);
1225 [ + + ]: 364120000 : if (dt->hasfreetypevars)
1226 : 168084000 : dt->isconcretetype = 0;
1227 : : }
1228 [ + + + + ]: 497341000 : if (istuple && dt->isconcretetype)
1229 [ + + + + : 88220100 : dt->isconcretetype = (jl_is_datatype(p) && ((jl_datatype_t*)p)->isconcretetype) || p == jl_bottom_type;
+ + ]
1230 [ + + ]: 497341000 : if (dt->isdispatchtuple) {
1231 [ + + + + ]: 300342000 : dt->isdispatchtuple = jl_is_datatype(p) &&
1232 [ + + ]: 196309000 : ((!jl_is_kind(p) && ((jl_datatype_t*)p)->isconcretetype) ||
1233 [ + + ]: 18330900 : (p == (jl_value_t*)jl_typeofbottom_type) || // == Type{Union{}}, so needs to be consistent
1234 [ + + + + ]: 18321100 : (((jl_datatype_t*)p)->name == jl_type_typename && !((jl_datatype_t*)p)->hasfreetypevars));
1235 : : }
1236 [ + + + + ]: 497341000 : if (istuple && dt->has_concrete_subtype) {
1237 [ + + ]: 117987000 : if (jl_is_vararg(p))
1238 : 934779 : p = ((jl_vararg_t*)p)->T;
1239 : : // tuple types like Tuple{:x} cannot have instances
1240 [ + + + + : 117987000 : if (p && !jl_is_type(p) && !jl_is_typevar(p))
+ + ]
1241 : 151 : dt->has_concrete_subtype = 0;
1242 : : }
1243 : : }
1244 [ + + ]: 187220000 : if (dt->name == jl_type_typename) {
1245 : 3812870 : cacheable = 0; // the cache for Type ignores parameter normalization, so it can't be used as a regular hash
1246 : 3812870 : jl_value_t *p = jl_tparam(dt, 0);
1247 [ + + + + ]: 3812870 : if (!jl_is_type(p) && !jl_is_typevar(p)) // Type{v} has no subtypes, if v is not a Type
1248 : 2 : dt->has_concrete_subtype = 0;
1249 : : }
1250 : 187220000 : dt->hash = typekey_hash(dt->name, jl_svec_data(dt->parameters), l, cacheable);
1251 [ + + ]: 187220000 : dt->cached_by_hash = cacheable ? (typekey_hash(dt->name, jl_svec_data(dt->parameters), l, 0) != 0) : (dt->hash != 0);
1252 : 187220000 : }
1253 : :
1254 : 163658000 : static void check_datatype_parameters(jl_typename_t *tn, jl_value_t **params, size_t np)
1255 : : {
1256 : 163658000 : jl_value_t *wrapper = tn->wrapper;
1257 : : jl_value_t **bounds;
1258 : 163658000 : JL_GC_PUSHARGS(bounds, np*2);
1259 : 163658000 : int i = 0;
1260 [ + + ]: 543031000 : while (jl_is_unionall(wrapper)) {
1261 : 379373000 : jl_tvar_t *tv = ((jl_unionall_t*)wrapper)->var;
1262 : 379373000 : bounds[i++] = tv->lb;
1263 : 379373000 : bounds[i++] = tv->ub;
1264 : 379373000 : wrapper = ((jl_unionall_t*)wrapper)->body;
1265 : : }
1266 [ - + ]: 163658000 : assert(i == np*2);
1267 : 163658000 : wrapper = tn->wrapper;
1268 [ + + ]: 543029000 : for (i = 0; i < np; i++) {
1269 [ - + ]: 379373000 : assert(jl_is_unionall(wrapper));
1270 : 379373000 : jl_tvar_t *tv = ((jl_unionall_t*)wrapper)->var;
1271 [ + + ]: 379373000 : if (!within_typevar(params[i], bounds[2*i], bounds[2*i+1])) {
1272 [ + + + + ]: 2005 : if (tv->lb != bounds[2*i] || tv->ub != bounds[2*i+1])
1273 : : // pass a new version of `tv` containing the instantiated bounds
1274 : 5 : tv = jl_new_typevar(tv->name, bounds[2*i], bounds[2*i+1]);
1275 : 2005 : JL_GC_PUSH1(&tv);
1276 : 2005 : jl_type_error_rt(jl_symbol_name(tn->name), jl_symbol_name(tv->name), (jl_value_t*)tv, params[i]);
1277 : : }
1278 : : int j;
1279 [ + + ]: 1023270000 : for (j = 2*i + 2; j < 2*np; j++) {
1280 : 643896000 : jl_value_t *bj = bounds[j];
1281 [ + + + + ]: 643896000 : if (bj != (jl_value_t*)jl_any_type && bj != jl_bottom_type)
1282 : 144755000 : bounds[j] = jl_substitute_var(bj, tv, params[i]);
1283 : : }
1284 : 379371000 : wrapper = ((jl_unionall_t*)wrapper)->body;
1285 : : }
1286 : 163656000 : JL_GC_POP();
1287 : 163656000 : }
1288 : :
1289 : 19850100 : static jl_value_t *extract_wrapper(jl_value_t *t JL_PROPAGATES_ROOT) JL_GLOBALLY_ROOTED
1290 : : {
1291 : 19850100 : t = jl_unwrap_unionall(t);
1292 [ + + ]: 19850100 : if (jl_is_datatype(t))
1293 : 2435460 : return ((jl_datatype_t*)t)->name->wrapper;
1294 [ + + ]: 17414600 : if (jl_is_uniontype(t)) {
1295 : 515435 : jl_value_t *n1 = extract_wrapper(((jl_uniontype_t*)t)->a);
1296 [ + - ]: 515435 : if (n1 != NULL) return n1;
1297 : 0 : return extract_wrapper(((jl_uniontype_t*)t)->b);
1298 : : }
1299 [ - + ]: 16899200 : if (jl_is_typevar(t))
1300 : 0 : return extract_wrapper(((jl_tvar_t*)t)->ub);
1301 : 16899200 : return NULL;
1302 : : }
1303 : :
1304 : 124069000 : int _may_substitute_ub(jl_value_t *v, jl_tvar_t *var, int inside_inv, int *cov_count) JL_NOTSAFEPOINT
1305 : : {
1306 [ + + ]: 124069000 : if (v == (jl_value_t*)var) {
1307 [ + + ]: 8967780 : if (inside_inv) {
1308 : 8856860 : return 0;
1309 : : }
1310 : : else {
1311 : 110915 : (*cov_count)++;
1312 [ + + + + ]: 110915 : return *cov_count <= 1 || jl_is_concrete_type(var->ub);
1313 : : }
1314 : : }
1315 [ + + ]: 115101000 : else if (jl_is_uniontype(v)) {
1316 [ + + + + ]: 8455780 : return _may_substitute_ub(((jl_uniontype_t*)v)->a, var, inside_inv, cov_count) &&
1317 : 4184880 : _may_substitute_ub(((jl_uniontype_t*)v)->b, var, inside_inv, cov_count);
1318 : : }
1319 [ + + ]: 110831000 : else if (jl_is_unionall(v)) {
1320 : 19470700 : jl_unionall_t *ua = (jl_unionall_t*)v;
1321 [ + + ]: 19470700 : if (ua->var == var)
1322 : 4352 : return 1;
1323 [ + + ]: 38932700 : return _may_substitute_ub(ua->var->lb, var, inside_inv, cov_count) &&
1324 [ + + + + ]: 38932700 : _may_substitute_ub(ua->var->ub, var, inside_inv, cov_count) &&
1325 : 19166200 : _may_substitute_ub(ua->body, var, inside_inv, cov_count);
1326 : : }
1327 [ + + ]: 91359800 : else if (jl_is_datatype(v)) {
1328 [ + + + + ]: 39579900 : int invar = inside_inv || !jl_is_tuple_type(v);
1329 [ + + ]: 75981900 : for (size_t i = 0; i < jl_nparams(v); i++) {
1330 [ + + ]: 45465800 : if (!_may_substitute_ub(jl_tparam(v,i), var, invar, cov_count))
1331 : 9063810 : return 0;
1332 : : }
1333 : : }
1334 [ + + ]: 51779900 : else if (jl_is_vararg(v)) {
1335 : 3015110 : jl_vararg_t *va = (jl_vararg_t*)v;
1336 : 3015110 : int old_count = *cov_count;
1337 [ + - + + ]: 3015110 : if (va->T && !_may_substitute_ub(va->T, var, inside_inv, cov_count))
1338 : 228 : return 0;
1339 [ + + + + ]: 3014880 : if (*cov_count > old_count && !jl_is_concrete_type(var->ub))
1340 : 49730 : return 0;
1341 [ + + + + ]: 2965150 : if (va->N && !_may_substitute_ub(va->N, var, 1, cov_count))
1342 : 85731 : return 0;
1343 : : }
1344 : 82160300 : return 1;
1345 : : }
1346 : :
1347 : : // Check whether `var` may be replaced with its upper bound `ub` in `v where var<:ub`
1348 : : // Conditions:
1349 : : // * `var` does not appear in invariant position
1350 : : // * `var` appears at most once (in covariant position) and not in a `Vararg`
1351 : : // unless the upper bound is concrete (diagonal rule)
1352 : 8929120 : int may_substitute_ub(jl_value_t *v, jl_tvar_t *var) JL_NOTSAFEPOINT
1353 : : {
1354 : 8929120 : int cov_count = 0;
1355 : 8929120 : return _may_substitute_ub(v, var, 0, &cov_count);
1356 : : }
1357 : :
1358 : 661309000 : jl_value_t *normalize_unionalls(jl_value_t *t)
1359 : : {
1360 : 661309000 : JL_GC_PUSH1(&t);
1361 [ + + ]: 661309000 : if (jl_is_uniontype(t)) {
1362 : 3314980 : jl_uniontype_t *u = (jl_uniontype_t*)t;
1363 : 3314980 : jl_value_t *a = NULL;
1364 : 3314980 : jl_value_t *b = NULL;
1365 : 3314980 : JL_GC_PUSH2(&a, &b);
1366 : 3314980 : a = normalize_unionalls(u->a);
1367 : 3314980 : b = normalize_unionalls(u->b);
1368 [ + + - + ]: 3314980 : if (a != u->a || b != u->b) {
1369 : 902 : t = jl_new_struct(jl_uniontype_type, a, b);
1370 : : }
1371 : 3314980 : JL_GC_POP();
1372 : : }
1373 [ + + ]: 657994000 : else if (jl_is_unionall(t)) {
1374 : 8931160 : jl_unionall_t *u = (jl_unionall_t*)t;
1375 : 8931160 : jl_value_t *body = normalize_unionalls(u->body);
1376 [ + + ]: 8931160 : if (body != u->body) {
1377 : 9155 : JL_GC_PUSH1(&body);
1378 : 9155 : t = jl_new_struct(jl_unionall_type, u->var, body);
1379 : 9155 : JL_GC_POP();
1380 : 9155 : u = (jl_unionall_t*)t;
1381 : : }
1382 : :
1383 [ + + + + ]: 8931160 : if (u->var->lb == u->var->ub || may_substitute_ub(body, u->var)) {
1384 [ + + + + ]: 37566 : JL_TRY {
1385 : 18784 : t = jl_instantiate_unionall(u, u->var->ub);
1386 : : }
1387 [ + + ]: 4 : JL_CATCH {
1388 : : // just skip normalization
1389 : : // (may happen for bounds inconsistent with the wrapper's bounds)
1390 : : }
1391 : : }
1392 : : }
1393 : 661309000 : JL_GC_POP();
1394 : 661309000 : return t;
1395 : : }
1396 : :
1397 : : static jl_value_t *_jl_instantiate_type_in_env(jl_value_t *ty, jl_unionall_t *env, jl_value_t **vals, jl_typeenv_t *prev, jl_typestack_t *stack);
1398 : :
1399 : 299396000 : static jl_value_t *inst_datatype_inner(jl_datatype_t *dt, jl_svec_t *p, jl_value_t **iparams, size_t ntp,
1400 : : jl_typestack_t *stack, jl_typeenv_t *env)
1401 : : {
1402 : : jl_typestack_t top;
1403 : 299396000 : jl_typename_t *tn = dt->name;
1404 : 299396000 : int istuple = (tn == jl_tuple_typename);
1405 : 299396000 : int isnamedtuple = (tn == jl_namedtuple_typename);
1406 [ + + ]: 299396000 : if (tn != jl_type_typename) {
1407 : : size_t i;
1408 [ + + ]: 900973000 : for (i = 0; i < ntp; i++)
1409 : 645748000 : iparams[i] = normalize_unionalls(iparams[i]);
1410 : : }
1411 : :
1412 : : // check type cache, if applicable
1413 : 299396000 : int cacheable = 1;
1414 [ + + ]: 299396000 : if (istuple) {
1415 : : size_t i;
1416 [ + + + + ]: 246012000 : for (i = 0; cacheable && i < ntp; i++)
1417 [ + + + + ]: 188045000 : if (!jl_is_concrete_type(iparams[i]) && iparams[i] != jl_bottom_type)
1418 : 22074000 : cacheable = 0;
1419 : : }
1420 : : else {
1421 : : size_t i;
1422 [ + + + + ]: 589454000 : for (i = 0; cacheable && i < ntp; i++)
1423 [ + + ]: 348024000 : if (jl_has_free_typevars(iparams[i]))
1424 : 163417000 : cacheable = 0;
1425 : : }
1426 [ + + ]: 299396000 : if (cacheable) {
1427 : : size_t i;
1428 [ + + ]: 356931000 : for (i = 0; i < ntp; i++) {
1429 : 243025000 : jl_value_t *pi = iparams[i];
1430 [ + + ]: 243025000 : if (pi == jl_bottom_type)
1431 : 824939 : continue;
1432 [ + + ]: 242200000 : if (jl_is_datatype(pi))
1433 : 222866000 : continue;
1434 [ - + ]: 19334600 : if (jl_is_vararg(pi)) {
1435 : 0 : pi = jl_unwrap_vararg(pi);
1436 [ # # ]: 0 : if (jl_has_free_typevars(pi))
1437 : 0 : continue;
1438 : : }
1439 : : // normalize types equal to wrappers (prepare for wrapper_id)
1440 : 19334600 : jl_value_t *tw = extract_wrapper(pi);
1441 [ + + + + : 20302000 : if (tw && tw != pi && (tn != jl_type_typename || jl_typeof(pi) == jl_typeof(tw)) &&
+ + + + +
+ ]
1442 : 967347 : jl_types_equal(pi, tw)) {
1443 : : // This would require some special handling, but is never used at
1444 : : // the moment.
1445 [ - + ]: 4322 : assert(!jl_is_vararg(iparams[i]));
1446 : 4322 : iparams[i] = tw;
1447 [ - + ]: 4322 : if (p) jl_gc_wb(p, tw);
1448 : : }
1449 : : }
1450 [ + + + + : 113905000 : if (tn == jl_type_typename && jl_is_datatype(iparams[0]) && ((jl_datatype_t*)iparams[0])->name == jl_type_typename &&
+ + ]
1451 [ + + ]: 16396 : jl_tparam0(iparams[0]) == jl_bottom_type) {
1452 : : // normalize Type{Type{Union{}}} to Type{TypeofBottom}
1453 : 648 : iparams[0] = (jl_value_t*)jl_typeofbottom_type;
1454 : : }
1455 : 113905000 : jl_value_t *lkup = (jl_value_t*)lookup_type(tn, iparams, ntp);
1456 [ + + ]: 113905000 : if (lkup != NULL)
1457 : 111895000 : return lkup;
1458 : : }
1459 : 187502000 : jl_value_t *stack_lkup = lookup_type_stack(stack, dt, ntp, iparams);
1460 [ + + ]: 187502000 : if (stack_lkup)
1461 : 59 : return stack_lkup;
1462 : :
1463 [ + + ]: 187501000 : if (!istuple) {
1464 : : // check parameters against bounds in type definition
1465 : 163658000 : check_datatype_parameters(tn, iparams, ntp);
1466 : : }
1467 [ + + - + ]: 23843500 : else if (ntp == 0 && jl_emptytuple_type != NULL) {
1468 : : // empty tuple type case
1469 : 0 : return (jl_value_t*)jl_emptytuple_type;
1470 : : }
1471 : :
1472 : 187499000 : jl_datatype_t *ndt = NULL;
1473 : 187499000 : jl_value_t *last = iparams[ntp - 1];
1474 : 187499000 : JL_GC_PUSH3(&p, &ndt, &last);
1475 : :
1476 [ + + + + : 187499000 : if (istuple && ntp > 0 && jl_is_vararg(last)) {
+ + ]
1477 : : // normalize Tuple{..., Vararg{Int, 3}} to Tuple{..., Int, Int, Int}
1478 : 1245270 : jl_value_t *va = jl_unwrap_unionall(last);
1479 : 1245270 : jl_value_t *va0 = jl_unwrap_vararg(va), *va1 = jl_unwrap_vararg_num(va);
1480 : : // return same `Tuple` object for types equal to it
1481 [ + + + + : 1245270 : if (ntp == 1 && va0 == (jl_value_t*)jl_any_type && !va1) {
+ + ]
1482 : 25715 : JL_GC_POP();
1483 : 25715 : return (jl_value_t*)jl_anytuple_type;
1484 : : }
1485 [ + + + + ]: 1219550 : if (va1 && jl_is_long(va1)) {
1486 : 285446 : ssize_t nt = jl_unbox_long(va1);
1487 [ - + ]: 285446 : assert(nt >= 0);
1488 [ + + + + ]: 285446 : if (nt == 0 || !jl_has_free_typevars(va0)) {
1489 [ + + ]: 284771 : if (ntp == 1) {
1490 : 43186 : JL_GC_POP();
1491 : 43186 : return jl_tupletype_fill(nt, va0);
1492 : : }
1493 : : size_t i, l;
1494 : 241585 : p = jl_alloc_svec(ntp - 1 + nt);
1495 [ + + ]: 879016 : for (i = 0, l = ntp - 1; i < l; i++)
1496 : 637431 : jl_svecset(p, i, iparams[i]);
1497 : 241585 : l = ntp - 1 + nt;
1498 [ + + ]: 535691 : for (; i < l; i++)
1499 : 294106 : jl_svecset(p, i, va0);
1500 : 241585 : jl_value_t *ndt = (jl_value_t*)jl_apply_tuple_type(p);
1501 : 241585 : JL_GC_POP();
1502 : 241585 : return ndt;
1503 : : }
1504 : : }
1505 : : }
1506 : :
1507 : : // move array of instantiated parameters to heap; we need to keep it
1508 [ + + ]: 187189000 : if (p == NULL) {
1509 : 179267000 : p = jl_alloc_svec_uninit(ntp);
1510 [ + + ]: 605613000 : for (size_t i = 0; i < ntp; i++)
1511 : 426346000 : jl_svecset(p, i, iparams[i]);
1512 : : }
1513 : :
1514 : : // acquire the write lock now that we know we need a new object
1515 : : // since we're going to immediately leak it globally via the instantiation stack
1516 [ + + ]: 187189000 : if (cacheable) {
1517 : 2008430 : JL_LOCK(&typecache_lock); // Might GC
1518 : 2008430 : jl_value_t *lkup = (jl_value_t*)lookup_type(tn, iparams, ntp);
1519 [ + + ]: 2008430 : if (lkup != NULL) {
1520 : 3 : JL_UNLOCK(&typecache_lock); // Might GC
1521 : 3 : JL_GC_POP();
1522 : 3 : return lkup;
1523 : : }
1524 : : }
1525 : :
1526 : : // create and initialize new type
1527 : 187189000 : ndt = jl_new_uninitialized_datatype();
1528 : : // associate these parameters with the new type on
1529 : : // the stack, in case one of its field types references it.
1530 : 187189000 : top.tt = (jl_datatype_t*)ndt;
1531 : 187189000 : top.prev = stack;
1532 : 187189000 : stack = ⊤
1533 : 187189000 : ndt->name = tn;
1534 : 187189000 : jl_gc_wb(ndt, ndt->name);
1535 : 187189000 : ndt->super = NULL;
1536 : 187189000 : ndt->parameters = p;
1537 : 187189000 : jl_gc_wb(ndt, ndt->parameters);
1538 : 187189000 : ndt->types = NULL; // to be filled in below
1539 [ + + ]: 187189000 : if (istuple) {
1540 : 23533000 : ndt->types = p; // TODO: this may need to filter out certain types
1541 : : }
1542 [ + + ]: 163656000 : else if (isnamedtuple) {
1543 : 77104000 : jl_value_t *names_tup = jl_svecref(p, 0);
1544 : 77104000 : jl_value_t *values_tt = jl_svecref(p, 1);
1545 [ + + + + ]: 77107300 : if (!jl_has_free_typevars(names_tup) && !jl_has_free_typevars(values_tt)) {
1546 [ + + ]: 14457 : if (!jl_is_tuple(names_tup))
1547 : 1 : jl_type_error_rt("NamedTuple", "names", (jl_value_t*)jl_anytuple_type, names_tup);
1548 : 14456 : size_t nf = jl_nfields(names_tup);
1549 [ + + ]: 38886 : for (size_t i = 0; i < nf; i++) {
1550 : 24440 : jl_value_t *ni = jl_fieldref(names_tup, i);
1551 [ + + ]: 24440 : if (!jl_is_symbol(ni))
1552 : 1 : jl_type_error_rt("NamedTuple", "name", (jl_value_t*)jl_symbol_type, ni);
1553 [ + + ]: 42134 : for (size_t j = 0; j < i; j++) {
1554 [ + + ]: 17704 : if (ni == jl_fieldref_noalloc(names_tup, j))
1555 : 9 : jl_errorf("duplicate field name in NamedTuple: \"%s\" is not unique", jl_symbol_name((jl_sym_t*)ni));
1556 : : }
1557 : : }
1558 [ + + ]: 14446 : if (!jl_is_datatype(values_tt))
1559 : 11047 : jl_error("NamedTuple field type must be a tuple type");
1560 [ + + + + ]: 3399 : if (jl_is_va_tuple((jl_datatype_t*)values_tt) || jl_nparams(values_tt) != nf)
1561 : 22 : jl_error("NamedTuple names and field types must have matching lengths");
1562 : 3377 : ndt->types = ((jl_datatype_t*)values_tt)->parameters;
1563 : 3377 : jl_gc_wb(ndt, ndt->types);
1564 : : }
1565 : : else {
1566 : 77089500 : ndt->types = jl_emptysvec; // XXX: this is essentially always false
1567 : : }
1568 : : }
1569 : :
1570 : 187178000 : jl_datatype_t *primarydt = ((jl_datatype_t*)jl_unwrap_unionall(tn->wrapper));
1571 : 187178000 : jl_precompute_memoized_dt(ndt, cacheable);
1572 : 187178000 : ndt->size = 0;
1573 [ + + ]: 187178000 : if (primarydt->layout)
1574 : 3234960 : jl_compute_field_offsets(ndt);
1575 : :
1576 [ + + + + ]: 187178000 : if (istuple || isnamedtuple) {
1577 : 100626000 : ndt->super = jl_any_type;
1578 : : }
1579 [ + + ]: 86552100 : else if (dt->super) {
1580 : 86552100 : ndt->super = (jl_datatype_t*)inst_type_w_((jl_value_t*)dt->super, env, stack, 1);
1581 : 86552000 : jl_gc_wb(ndt, ndt->super);
1582 : : }
1583 : 187178000 : jl_svec_t *ftypes = dt->types;
1584 [ + + ]: 187178000 : if (ftypes == NULL)
1585 : 20517400 : ftypes = primarydt->types;
1586 [ + + + + ]: 187178000 : if (ftypes == NULL || dt->super == NULL) {
1587 : : // in the process of creating this type definition:
1588 : : // need to instantiate the super and types fields later
1589 [ + + ]: 41 : if (tn->partial == NULL) {
1590 : 39 : tn->partial = jl_alloc_vec_any(0);
1591 : 39 : jl_gc_wb(tn, tn->partial);
1592 : : }
1593 : 41 : jl_array_ptr_1d_push(tn->partial, (jl_value_t*)ndt);
1594 : : }
1595 [ + + + + ]: 187178000 : else if (!isnamedtuple && !istuple) {
1596 [ + + - + ]: 86552000 : assert(ftypes != jl_emptysvec || jl_field_names(ndt) == jl_emptysvec);
1597 [ + + - + ]: 86552000 : assert(ftypes == jl_emptysvec || !ndt->name->abstract);
1598 [ + + ]: 86552000 : if (ftypes == jl_emptysvec) {
1599 : 54573800 : ndt->types = ftypes;
1600 : : }
1601 [ + + ]: 31978200 : else if (cacheable) {
1602 : : // recursively instantiate the types of the fields
1603 [ + + ]: 83478 : if (dt->types == NULL)
1604 : 826 : ndt->types = jl_compute_fieldtypes(ndt, stack);
1605 : : else
1606 : 82652 : ndt->types = inst_ftypes(ftypes, env, stack);
1607 : 83478 : jl_gc_wb(ndt, ndt->types);
1608 : : }
1609 : : }
1610 : :
1611 : : // now publish the finished result
1612 : : // XXX: if the stack was used, this will publish in the wrong order,
1613 : : // leading to incorrect layouts and data races (#40050: the A{T} should be
1614 : : // an isbitstype singleton of size 0)
1615 [ + + ]: 187178000 : if (cacheable) {
1616 [ + + + + : 1997350 : if (ndt->layout == NULL && ndt->types != NULL && ndt->isconcretetype)
+ + ]
1617 : 1854920 : jl_compute_field_offsets(ndt);
1618 : 1997350 : jl_cache_type_(ndt);
1619 : 1997350 : JL_UNLOCK(&typecache_lock); // Might GC
1620 : : }
1621 : :
1622 : 187178000 : JL_GC_POP();
1623 : 187178000 : return (jl_value_t*)ndt;
1624 : : }
1625 : :
1626 : 55124900 : static jl_tupletype_t *jl_apply_tuple_type_v_(jl_value_t **p, size_t np, jl_svec_t *params)
1627 : : {
1628 : 55124900 : return (jl_datatype_t*)inst_datatype_inner(jl_anytuple_type, params, p, np, NULL, NULL);
1629 : : }
1630 : :
1631 : 8507150 : JL_DLLEXPORT jl_tupletype_t *jl_apply_tuple_type(jl_svec_t *params)
1632 : : {
1633 : 8507150 : return jl_apply_tuple_type_v_(jl_svec_data(params), jl_svec_len(params), params);
1634 : : }
1635 : :
1636 : 46617700 : JL_DLLEXPORT jl_tupletype_t *jl_apply_tuple_type_v(jl_value_t **p, size_t np)
1637 : : {
1638 : 46617700 : return jl_apply_tuple_type_v_(p, np, NULL);
1639 : : }
1640 : :
1641 : 76664900 : jl_tupletype_t *jl_lookup_arg_tuple_type(jl_value_t *arg1, jl_value_t **args, size_t nargs, int leaf)
1642 : : {
1643 : 76664900 : return (jl_datatype_t*)lookup_typevalue(jl_tuple_typename, arg1, args, nargs, leaf);
1644 : : }
1645 : :
1646 : 91718400 : jl_tupletype_t *jl_inst_arg_tuple_type(jl_value_t *arg1, jl_value_t **args, size_t nargs, int leaf)
1647 : : {
1648 : 91718400 : jl_tupletype_t *tt = (jl_datatype_t*)lookup_typevalue(jl_tuple_typename, arg1, args, nargs, leaf);
1649 [ + + ]: 91718400 : if (tt == NULL) {
1650 : : size_t i;
1651 : 357042 : jl_svec_t *params = jl_alloc_svec(nargs);
1652 : 357043 : JL_GC_PUSH1(¶ms);
1653 [ + + ]: 47417900 : for (i = 0; i < nargs; i++) {
1654 [ + + ]: 47060800 : jl_value_t *ai = (i == 0 ? arg1 : args[i - 1]);
1655 [ + + + + ]: 47060800 : if (leaf && jl_is_type(ai)) {
1656 : : // if `ai` has free type vars this will not be a valid (concrete) type.
1657 : : // TODO: it would be really nice to only dispatch and cache those as
1658 : : // `jl_typeof(ai)`, but that will require some redesign of the caching
1659 : : // logic.
1660 : 207691 : ai = (jl_value_t*)jl_wrap_Type(ai);
1661 : : }
1662 : : else {
1663 : 46853100 : ai = jl_typeof(ai);
1664 : : }
1665 : 47060800 : jl_svecset(params, i, ai);
1666 : : }
1667 : 357043 : tt = (jl_datatype_t*)inst_datatype_inner(jl_anytuple_type, params, jl_svec_data(params), nargs, NULL, NULL);
1668 : 357044 : JL_GC_POP();
1669 : : }
1670 : 91718400 : return tt;
1671 : : }
1672 : :
1673 : 102224 : static jl_svec_t *inst_ftypes(jl_svec_t *p, jl_typeenv_t *env, jl_typestack_t *stack)
1674 : : {
1675 : : size_t i;
1676 : 102224 : size_t lp = jl_svec_len(p);
1677 : 102224 : jl_svec_t *np = jl_alloc_svec(lp);
1678 : 102224 : JL_GC_PUSH1(&np);
1679 [ + + ]: 354263 : for (i = 0; i < lp; i++) {
1680 : 252039 : jl_value_t *pi = jl_svecref(p, i);
1681 [ + + + + ]: 504075 : JL_TRY {
1682 : 252039 : pi = inst_type_w_(pi, env, stack, 1);
1683 [ + + + + ]: 252036 : if (!jl_is_type(pi) && !jl_is_typevar(pi)) {
1684 : 5 : pi = jl_bottom_type;
1685 : : }
1686 : : }
1687 [ + + ]: 6 : JL_CATCH {
1688 : 3 : pi = jl_bottom_type;
1689 : : }
1690 : 252039 : jl_svecset(np, i, pi);
1691 : : }
1692 : 102224 : JL_GC_POP();
1693 : 102224 : return np;
1694 : : }
1695 : :
1696 : 119241000 : static jl_value_t *inst_tuple_w_(jl_value_t *t, jl_typeenv_t *env, jl_typestack_t *stack, int check)
1697 : : {
1698 : 119241000 : jl_datatype_t *tt = (jl_datatype_t*)t;
1699 : 119241000 : jl_svec_t *tp = tt->parameters;
1700 : 119241000 : size_t ntp = jl_svec_len(tp);
1701 : : // Instantiate NTuple{3,Int}
1702 : : // Note this does not instantiate Tuple{Vararg{Int,3}}; that's done in inst_datatype_inner
1703 [ + + + + ]: 119241000 : if (jl_is_va_tuple(tt) && ntp == 1) {
1704 : : // If this is a Tuple{Vararg{T,N}} with known N, expand it to
1705 : : // a fixed-length tuple
1706 : 114178000 : jl_value_t *T=NULL, *N=NULL;
1707 : 114178000 : jl_value_t *va = jl_unwrap_unionall(jl_tparam0(tt));
1708 : 114178000 : jl_value_t *ttT = jl_unwrap_vararg(va);
1709 : 114178000 : jl_value_t *ttN = jl_unwrap_vararg_num(va);
1710 : 114178000 : jl_typeenv_t *e = env;
1711 [ + + ]: 245263000 : while (e != NULL) {
1712 [ + + ]: 131085000 : if ((jl_value_t*)e->var == ttT)
1713 : 35387 : T = e->val;
1714 [ + + ]: 131049000 : else if ((jl_value_t*)e->var == ttN)
1715 : 126660 : N = e->val;
1716 : 131085000 : e = e->prev;
1717 : : }
1718 [ + + + + : 114178000 : if (T != NULL && N != NULL && jl_is_long(N)) {
+ + ]
1719 : 10406 : ssize_t nt = jl_unbox_long(N);
1720 [ + + ]: 10406 : if (nt < 0)
1721 : 1 : jl_errorf("size or dimension is negative: %zd", nt);
1722 : 10405 : return (jl_value_t*)jl_tupletype_fill(nt, T);
1723 : : }
1724 : : }
1725 : : jl_value_t **iparams;
1726 : 119231000 : int onstack = ntp < jl_page_size/sizeof(jl_value_t*);
1727 [ + + + + : 119231000 : JL_GC_PUSHARGS(iparams, onstack ? ntp : 1);
+ + ]
1728 : 119231000 : jl_svec_t *ip_heap = NULL;
1729 [ + + ]: 119231000 : if (!onstack) {
1730 : 6 : ip_heap = jl_alloc_svec(ntp);
1731 : 6 : iparams[0] = (jl_value_t*)ip_heap;
1732 : 6 : iparams = jl_svec_data(ip_heap);
1733 : : }
1734 : 119231000 : int bound = 0;
1735 : : int i;
1736 [ + + ]: 246640000 : for (i = 0; i < ntp; i++) {
1737 : 127411000 : jl_value_t *elt = jl_svecref(tp, i);
1738 : 127411000 : jl_value_t *pi = inst_type_w_(elt, env, stack, 0);
1739 : 127410000 : iparams[i] = pi;
1740 [ + + ]: 127410000 : if (ip_heap)
1741 : 6144 : jl_gc_wb(ip_heap, pi);
1742 : 127410000 : bound |= (pi != elt);
1743 : : }
1744 [ + + ]: 119229000 : if (bound)
1745 : 2484650 : t = inst_datatype_inner(tt, ip_heap, iparams, ntp, stack, env);
1746 : 119229000 : JL_GC_POP();
1747 : 119229000 : return t;
1748 : : }
1749 : :
1750 : 1594620000 : static jl_value_t *inst_type_w_(jl_value_t *t, jl_typeenv_t *env, jl_typestack_t *stack, int check)
1751 : : {
1752 : : size_t i;
1753 [ + + ]: 1594620000 : if (jl_is_typevar(t)) {
1754 : 404745000 : jl_typeenv_t *e = env;
1755 [ + + ]: 647067000 : while (e != NULL) {
1756 [ + + ]: 582736000 : if (e->var == (jl_tvar_t*)t) {
1757 : 340414000 : jl_value_t *val = e->val;
1758 : 340414000 : return val;
1759 : : }
1760 : 242322000 : e = e->prev;
1761 : : }
1762 : 64330400 : return t;
1763 : : }
1764 [ + + ]: 1189870000 : if (jl_is_unionall(t)) {
1765 : 113578000 : jl_unionall_t *ua = (jl_unionall_t*)t;
1766 : 113578000 : jl_value_t *lb = NULL;
1767 : 113578000 : jl_value_t *var = NULL;
1768 : 113578000 : jl_value_t *newbody = NULL;
1769 : 113578000 : JL_GC_PUSH3(&lb, &var, &newbody);
1770 : 113578000 : lb = inst_type_w_(ua->var->lb, env, stack, check);
1771 : 113578000 : var = inst_type_w_(ua->var->ub, env, stack, check);
1772 [ + + + + ]: 113578000 : if (lb != ua->var->lb || var != ua->var->ub) {
1773 : 5722980 : var = (jl_value_t*)jl_new_typevar(ua->var->name, lb, var);
1774 : : }
1775 : : else {
1776 : 107855000 : var = (jl_value_t*)ua->var;
1777 : : }
1778 : 113578000 : jl_typeenv_t newenv = { ua->var, var, env };
1779 : 113578000 : newbody = inst_type_w_(ua->body, &newenv, stack, check);
1780 [ + + ]: 113578000 : if (newbody == (jl_value_t*)jl_emptytuple_type) {
1781 : : // NTuple{0} => Tuple{} can make a typevar disappear
1782 : 22 : t = (jl_value_t*)jl_emptytuple_type;
1783 : : }
1784 [ + + - + ]: 113578000 : else if (newbody != ua->body || var != (jl_value_t*)ua->var) {
1785 : : // if t's parameters are not bound in the environment, return it uncopied (#9378)
1786 : 32660100 : t = jl_new_struct(jl_unionall_type, var, newbody);
1787 : : }
1788 : 113578000 : JL_GC_POP();
1789 : 113578000 : return t;
1790 : : }
1791 [ + + ]: 1076290000 : if (jl_is_uniontype(t)) {
1792 : 15500600 : jl_uniontype_t *u = (jl_uniontype_t*)t;
1793 : 15500600 : jl_value_t *a = inst_type_w_(u->a, env, stack, check);
1794 : 15500600 : jl_value_t *b = NULL;
1795 : 15500600 : JL_GC_PUSH2(&a, &b);
1796 : 15500600 : b = inst_type_w_(u->b, env, stack, check);
1797 [ + + + + ]: 15500600 : if (a != u->a || b != u->b) {
1798 : 954317 : jl_value_t *uargs[2] = {a, b};
1799 : 954317 : t = jl_type_union(uargs, 2);
1800 : : }
1801 : 15500600 : JL_GC_POP();
1802 : 15500600 : return t;
1803 : : }
1804 [ + + ]: 1060790000 : if (jl_is_vararg(t)) {
1805 : 117053000 : jl_vararg_t *v = (jl_vararg_t*)t;
1806 : 117053000 : jl_value_t *T = NULL;
1807 : 117053000 : jl_value_t *N = NULL;
1808 : 117053000 : JL_GC_PUSH2(&T, &N);
1809 [ + + ]: 117053000 : if (v->T) {
1810 : 117053000 : T = inst_type_w_(v->T, env, stack, check);
1811 [ + + ]: 117053000 : if (v->N)
1812 : 542540 : N = inst_type_w_(v->N, env, stack, check);
1813 : : }
1814 [ + + + + ]: 117053000 : if (T != v->T || N != v->N) {
1815 : 391530 : t = (jl_value_t*)jl_wrap_vararg(T, N);
1816 : : }
1817 : 117053000 : JL_GC_POP();
1818 : 117053000 : return t;
1819 : : }
1820 [ + + ]: 943740000 : if (!jl_is_datatype(t))
1821 : 246683000 : return t;
1822 : 697058000 : jl_datatype_t *tt = (jl_datatype_t*)t;
1823 : 697058000 : jl_svec_t *tp = tt->parameters;
1824 [ + + ]: 697058000 : if (tp == jl_emptysvec)
1825 : 273105000 : return t;
1826 : 423953000 : jl_typename_t *tn = tt->name;
1827 [ + + ]: 423953000 : if (tn == jl_tuple_typename)
1828 : 119241000 : return inst_tuple_w_(t, env, stack, check);
1829 : 304712000 : size_t ntp = jl_svec_len(tp);
1830 : : jl_value_t **iparams;
1831 : 304712000 : JL_GC_PUSHARGS(iparams, ntp);
1832 : 304712000 : int bound = 0;
1833 [ + + ]: 876852000 : for (i = 0; i < ntp; i++) {
1834 : 572140000 : jl_value_t *elt = jl_svecref(tp, i);
1835 : 572140000 : jl_value_t *pi = inst_type_w_(elt, env, stack, check);
1836 : 572140000 : iparams[i] = pi;
1837 : 572140000 : bound |= (pi != elt);
1838 : : }
1839 : : // if t's parameters are not bound in the environment, return it uncopied (#9378)
1840 [ + + ]: 304712000 : if (bound)
1841 : 214824000 : t = inst_datatype_inner(tt, NULL, iparams, ntp, stack, env);
1842 : 304709000 : JL_GC_POP();
1843 : 304709000 : return t;
1844 : : }
1845 : :
1846 : 493116 : static jl_value_t *instantiate_with(jl_value_t *t, jl_value_t **env, size_t n, jl_typeenv_t *te)
1847 : : {
1848 [ + + ]: 493116 : if (n > 0) {
1849 : 246558 : jl_typeenv_t en = { (jl_tvar_t*)env[0], env[1], te };
1850 : 246558 : return instantiate_with(t, &env[2], n-1, &en );
1851 : : }
1852 : 246558 : return inst_type_w_(t, te, NULL, 1);
1853 : : }
1854 : :
1855 : 246558 : jl_value_t *jl_instantiate_type_with(jl_value_t *t, jl_value_t **env, size_t n)
1856 : : {
1857 : 246558 : return instantiate_with(t, env, n, NULL);
1858 : : }
1859 : :
1860 : 1912200 : static jl_value_t *_jl_instantiate_type_in_env(jl_value_t *ty, jl_unionall_t *env, jl_value_t **vals, jl_typeenv_t *prev, jl_typestack_t *stack)
1861 : : {
1862 : 1912200 : jl_typeenv_t en = { env->var, vals[0], prev };
1863 [ + + ]: 1912200 : if (jl_is_unionall(env->body))
1864 : 408089 : return _jl_instantiate_type_in_env(ty, (jl_unionall_t*)env->body, vals + 1, &en, stack);
1865 : : else
1866 : 1504110 : return inst_type_w_(ty, &en, stack, 1);
1867 : : }
1868 : :
1869 : 3573360 : JL_DLLEXPORT jl_value_t *jl_instantiate_type_in_env(jl_value_t *ty, jl_unionall_t *env, jl_value_t **vals)
1870 : : {
1871 : 3573360 : jl_value_t *typ = ty;
1872 [ + + ]: 3573360 : if (jl_is_unionall(env)) {
1873 [ + - + + ]: 3008230 : JL_TRY {
1874 : 1504110 : typ = _jl_instantiate_type_in_env(ty, env, vals, NULL, NULL);
1875 : : }
1876 [ # # ]: 0 : JL_CATCH {
1877 : 0 : typ = jl_bottom_type;
1878 : : }
1879 : : }
1880 : 3573360 : return typ;
1881 : : }
1882 : :
1883 : 28389300 : jl_datatype_t *jl_wrap_Type(jl_value_t *t)
1884 : : {
1885 : 28389300 : return (jl_datatype_t*)jl_instantiate_unionall(jl_type_type, t);
1886 : : }
1887 : :
1888 : 868716 : jl_vararg_t *jl_wrap_vararg(jl_value_t *t, jl_value_t *n)
1889 : : {
1890 [ + + ]: 868716 : if (n) {
1891 [ + + ]: 419507 : if (jl_is_typevar(n)) {
1892 : : // TODO: this is disabled due to #39698; it is also inconsistent
1893 : : // with other similar checks, where we usually only check substituted
1894 : : // values and not the bounds of variables.
1895 : : /*
1896 : : jl_tvar_t *N = (jl_tvar_t*)n;
1897 : : if (!(N->lb == jl_bottom_type && N->ub == (jl_value_t*)jl_any_type))
1898 : : jl_error("TypeVar in Vararg length must have bounds Union{} and Any");
1899 : : */
1900 : : }
1901 [ + + ]: 285458 : else if (!jl_is_long(n)) {
1902 : 3 : jl_type_error_rt("Vararg", "count", (jl_value_t*)jl_long_type, n);
1903 : : }
1904 [ + + ]: 285455 : else if (jl_unbox_long(n) < 0) {
1905 : 3 : jl_errorf("Vararg length is negative: %zd", jl_unbox_long(n));
1906 : : }
1907 : : }
1908 [ + + ]: 868710 : if (t) {
1909 [ - + ]: 860079 : if (!jl_valid_type_param(t)) {
1910 : 0 : jl_type_error_rt("Vararg", "type", (jl_value_t*)jl_type_type, t);
1911 : : }
1912 : : }
1913 : 868710 : jl_task_t *ct = jl_current_task;
1914 : 868710 : jl_vararg_t *vm = (jl_vararg_t *)jl_gc_alloc(ct->ptls, sizeof(jl_vararg_t), jl_vararg_type);
1915 : 868710 : vm->T = t;
1916 : 868710 : vm->N = n;
1917 : 868710 : return vm;
1918 : : }
1919 : :
1920 : 19557 : JL_DLLEXPORT jl_svec_t *jl_compute_fieldtypes(jl_datatype_t *st JL_PROPAGATES_ROOT, void *stack)
1921 : : {
1922 [ + - + - ]: 19557 : assert(st->name != jl_namedtuple_typename && st->name != jl_tuple_typename);
1923 : 19557 : jl_datatype_t *wt = (jl_datatype_t*)jl_unwrap_unionall(st->name->wrapper);
1924 : 19557 : size_t i, n = jl_svec_len(wt->parameters);
1925 [ - + ]: 19557 : assert(n > 0 && "expected empty case to be handled during construction");
1926 : : //if (n == 0)
1927 : : // return ((st->types = jl_emptysvec));
1928 [ - + ]: 19557 : if (wt->types == NULL)
1929 : 0 : jl_errorf("cannot determine field types of incomplete type %s",
1930 : 0 : jl_symbol_name(st->name->name));
1931 : 19557 : jl_typeenv_t *env = (jl_typeenv_t*)alloca(n * sizeof(jl_typeenv_t));
1932 [ + + ]: 82370 : for (i = 0; i < n; i++) {
1933 : 62813 : env[i].var = (jl_tvar_t*)jl_svecref(wt->parameters, i);
1934 : 62813 : env[i].val = jl_svecref(st->parameters, i);
1935 [ + + ]: 62813 : env[i].prev = i == 0 ? NULL : &env[i - 1];
1936 : : }
1937 : : jl_typestack_t top;
1938 : 19557 : top.tt = st;
1939 : 19557 : top.prev = (jl_typestack_t*)stack;
1940 : 19557 : st->types = inst_ftypes(wt->types, &env[n - 1], &top);
1941 : 19557 : jl_gc_wb(st, st->types);
1942 : 19557 : return st->types;
1943 : : }
1944 : :
1945 : :
1946 : 26092 : void jl_reinstantiate_inner_types(jl_datatype_t *t) // can throw!
1947 : : {
1948 [ - + ]: 26092 : assert(jl_is_datatype(t));
1949 : : jl_typestack_t top;
1950 : 26092 : top.tt = t;
1951 : 26092 : top.prev = NULL;
1952 : 26092 : size_t i, j, n = jl_svec_len(t->parameters);
1953 : 26092 : jl_array_t *partial = t->name->partial;
1954 [ + + ]: 26092 : if (partial == NULL)
1955 : 26078 : return;
1956 [ - + ]: 14 : if (n == 0) {
1957 [ # # ]: 0 : assert(jl_array_len(partial) == 0);
1958 : 0 : return;
1959 : : }
1960 : :
1961 : 14 : jl_typeenv_t *env = (jl_typeenv_t*)alloca(n * sizeof(jl_typeenv_t));
1962 [ + + ]: 40 : for (i = 0; i < n; i++) {
1963 : 26 : env[i].var = (jl_tvar_t*)jl_svecref(t->parameters, i);
1964 : 26 : env[i].val = NULL;
1965 [ + + ]: 26 : env[i].prev = i == 0 ? NULL : &env[i - 1];
1966 : : }
1967 : :
1968 [ + + ]: 30 : for (j = 0; j < jl_array_len(partial); j++) {
1969 : 16 : jl_datatype_t *ndt = (jl_datatype_t*)jl_array_ptr_ref(partial, j);
1970 [ - + ]: 16 : assert(jl_unwrap_unionall(ndt->name->wrapper) == (jl_value_t*)t);
1971 [ + + ]: 47 : for (i = 0; i < n; i++)
1972 : 31 : env[i].val = jl_svecref(ndt->parameters, i);
1973 : :
1974 : 16 : ndt->super = (jl_datatype_t*)inst_type_w_((jl_value_t*)t->super, &env[n - 1], &top, 1);
1975 : 16 : jl_gc_wb(ndt, ndt->super);
1976 : : }
1977 : :
1978 [ + + ]: 14 : if (t->types != jl_emptysvec) {
1979 [ + + ]: 28 : for (j = 0; j < jl_array_len(partial); j++) {
1980 : 15 : jl_datatype_t *ndt = (jl_datatype_t*)jl_array_ptr_ref(partial, j);
1981 [ + + ]: 45 : for (i = 0; i < n; i++)
1982 : 30 : env[i].val = jl_svecref(ndt->parameters, i);
1983 [ - + ]: 15 : assert(ndt->types == NULL);
1984 : 15 : ndt->types = inst_ftypes(t->types, &env[n - 1], &top);
1985 : 15 : jl_gc_wb(ndt, ndt->types);
1986 [ + + ]: 15 : if (ndt->isconcretetype) { // cacheable
1987 : 2 : jl_compute_field_offsets(ndt);
1988 : : }
1989 : : }
1990 : : }
1991 : : else {
1992 [ - + ]: 1 : assert(jl_field_names(t) == jl_emptysvec);
1993 : : }
1994 : : }
1995 : :
1996 : : // initialization -------------------------------------------------------------
1997 : :
1998 : 15 : static jl_tvar_t *tvar(const char *name)
1999 : : {
2000 : 15 : return jl_new_typevar(jl_symbol(name), (jl_value_t*)jl_bottom_type,
2001 : : (jl_value_t*)jl_any_type);
2002 : : }
2003 : :
2004 : 1 : void jl_init_types(void) JL_GC_DISABLED
2005 : : {
2006 : 1 : jl_module_t *core = NULL; // will need to be assigned later
2007 : :
2008 : : // create base objects
2009 : 1 : jl_datatype_type = jl_new_uninitialized_datatype();
2010 : 1 : jl_set_typeof(jl_datatype_type, jl_datatype_type);
2011 : 1 : jl_typename_type = jl_new_uninitialized_datatype();
2012 : 1 : jl_symbol_type = jl_new_uninitialized_datatype();
2013 : 1 : jl_simplevector_type = jl_new_uninitialized_datatype();
2014 : 1 : jl_methtable_type = jl_new_uninitialized_datatype();
2015 : :
2016 : 1 : jl_emptysvec = (jl_svec_t*)jl_gc_permobj(sizeof(void*), jl_simplevector_type);
2017 : 1 : jl_svec_set_len_unsafe(jl_emptysvec, 0);
2018 : :
2019 : 1 : jl_any_type = (jl_datatype_t*)jl_new_abstracttype((jl_value_t*)jl_symbol("Any"), core, NULL, jl_emptysvec);
2020 : 1 : jl_any_type->super = jl_any_type;
2021 : 1 : jl_nonfunction_mt = jl_any_type->name->mt;
2022 : 1 : jl_any_type->name->mt = NULL;
2023 : :
2024 : 1 : jl_type_type = (jl_unionall_t*)jl_new_abstracttype((jl_value_t*)jl_symbol("Type"), core, jl_any_type, jl_emptysvec);
2025 : 1 : jl_type_typename = ((jl_datatype_t*)jl_type_type)->name;
2026 : 1 : jl_type_type_mt = jl_new_method_table(jl_type_typename->name, core);
2027 : 1 : jl_type_typename->mt = jl_type_type_mt;
2028 : :
2029 : : // initialize them. lots of cycles.
2030 : : // NOTE: types are not actually mutable, but we want to ensure they are heap-allocated with stable addresses
2031 : 1 : jl_datatype_type->name = jl_new_typename_in(jl_symbol("DataType"), core, 0, 1);
2032 : 1 : jl_datatype_type->name->wrapper = (jl_value_t*)jl_datatype_type;
2033 : 1 : jl_datatype_type->super = (jl_datatype_t*)jl_type_type;
2034 : 1 : jl_datatype_type->parameters = jl_emptysvec;
2035 : 1 : jl_datatype_type->name->n_uninitialized = 9 - 3;
2036 : 1 : jl_datatype_type->name->names = jl_perm_symsvec(9,
2037 : : "name",
2038 : : "super",
2039 : : "parameters",
2040 : : "types",
2041 : : "instance",
2042 : : "layout",
2043 : : "size",
2044 : : "hash",
2045 : : "flags"); // "hasfreetypevars", "isconcretetype", "isdispatchtuple", "isbitstype", "zeroinit", "has_concrete_subtype", "cached_by_hash"
2046 : 1 : jl_datatype_type->types = jl_svec(9,
2047 : : jl_typename_type,
2048 : : jl_datatype_type,
2049 : : jl_simplevector_type,
2050 : : jl_simplevector_type,
2051 : : jl_any_type, // instance
2052 : : jl_any_type /*jl_voidpointer_type*/,
2053 : : jl_any_type /*jl_int32_type*/,
2054 : : jl_any_type /*jl_int32_type*/,
2055 : : jl_any_type /*jl_uint8_type*/);
2056 : : const static uint32_t datatype_constfields[1] = { 0x00000097 }; // (1<<0)|(1<<1)|(1<<2)|(1<<4)|(1<<7)
2057 : 1 : jl_datatype_type->name->constfields = datatype_constfields;
2058 : 1 : jl_precompute_memoized_dt(jl_datatype_type, 1);
2059 : :
2060 : 1 : jl_typename_type->name = jl_new_typename_in(jl_symbol("TypeName"), core, 0, 1);
2061 : 1 : jl_typename_type->name->wrapper = (jl_value_t*)jl_typename_type;
2062 : 1 : jl_typename_type->name->mt = jl_nonfunction_mt;
2063 : 1 : jl_typename_type->super = jl_any_type;
2064 : 1 : jl_typename_type->parameters = jl_emptysvec;
2065 : 1 : jl_typename_type->name->n_uninitialized = 15 - 2;
2066 : 1 : jl_typename_type->name->names = jl_perm_symsvec(15, "name", "module",
2067 : : "names", "atomicfields", "constfields",
2068 : : "wrapper", "Typeofwrapper", "cache", "linearcache",
2069 : : "mt", "partial",
2070 : : "hash", "n_uninitialized",
2071 : : "flags", // "abstract", "mutable", "mayinlinealloc",
2072 : : "max_methods");
2073 : 1 : jl_typename_type->types = jl_svec(15, jl_symbol_type, jl_any_type /*jl_module_type*/,
2074 : : jl_simplevector_type, jl_any_type/*jl_voidpointer_type*/, jl_any_type/*jl_voidpointer_type*/,
2075 : : jl_type_type, jl_type_type, jl_simplevector_type, jl_simplevector_type,
2076 : : jl_methtable_type, jl_any_type,
2077 : : jl_any_type /*jl_long_type*/, jl_any_type /*jl_int32_type*/,
2078 : : jl_any_type /*jl_uint8_type*/,
2079 : : jl_any_type /*jl_uint8_type*/);
2080 : : const static uint32_t typename_constfields[1] = { 0x00003a3f }; // (1<<0)|(1<<1)|(1<<2)|(1<<3)|(1<<4)|(1<<5)|(1<<9)|(1<<11)|(1<<12)|(1<<13)
2081 : 1 : jl_typename_type->name->constfields = typename_constfields;
2082 : 1 : jl_precompute_memoized_dt(jl_typename_type, 1);
2083 : :
2084 : 1 : jl_methtable_type->name = jl_new_typename_in(jl_symbol("MethodTable"), core, 0, 1);
2085 : 1 : jl_methtable_type->name->wrapper = (jl_value_t*)jl_methtable_type;
2086 : 1 : jl_methtable_type->name->mt = jl_nonfunction_mt;
2087 : 1 : jl_methtable_type->super = jl_any_type;
2088 : 1 : jl_methtable_type->parameters = jl_emptysvec;
2089 : 1 : jl_methtable_type->name->n_uninitialized = 12 - 5;
2090 : 1 : jl_methtable_type->name->names = jl_perm_symsvec(12, "name", "defs",
2091 : : "leafcache", "cache", "max_args",
2092 : : "kwsorter", "module",
2093 : : "backedges", "", "", "offs", "");
2094 : 1 : jl_methtable_type->types = jl_svec(12, jl_symbol_type, jl_any_type, jl_any_type,
2095 : : jl_any_type, jl_any_type/*jl_long*/,
2096 : : jl_any_type, jl_any_type/*module*/,
2097 : : jl_any_type/*any vector*/, jl_any_type/*voidpointer*/, jl_any_type/*int32*/,
2098 : : jl_any_type/*uint8*/, jl_any_type/*uint8*/);
2099 : : const static uint32_t methtable_constfields[1] = { 0x00000040 }; // (1<<6);
2100 : 1 : jl_methtable_type->name->constfields = methtable_constfields;
2101 : 1 : jl_precompute_memoized_dt(jl_methtable_type, 1);
2102 : :
2103 : 1 : jl_symbol_type->name = jl_new_typename_in(jl_symbol("Symbol"), core, 0, 1);
2104 : 1 : jl_symbol_type->name->wrapper = (jl_value_t*)jl_symbol_type;
2105 : 1 : jl_symbol_type->name->mt = jl_nonfunction_mt;
2106 : 1 : jl_symbol_type->super = jl_any_type;
2107 : 1 : jl_symbol_type->parameters = jl_emptysvec;
2108 : 1 : jl_symbol_type->name->n_uninitialized = 0;
2109 : 1 : jl_symbol_type->name->names = jl_emptysvec;
2110 : 1 : jl_symbol_type->types = jl_emptysvec;
2111 : 1 : jl_symbol_type->size = 0;
2112 : 1 : jl_precompute_memoized_dt(jl_symbol_type, 1);
2113 : :
2114 : 1 : jl_simplevector_type->name = jl_new_typename_in(jl_symbol("SimpleVector"), core, 0, 1);
2115 : 1 : jl_simplevector_type->name->wrapper = (jl_value_t*)jl_simplevector_type;
2116 : 1 : jl_simplevector_type->name->mt = jl_nonfunction_mt;
2117 : 1 : jl_simplevector_type->super = jl_any_type;
2118 : 1 : jl_simplevector_type->parameters = jl_emptysvec;
2119 : 1 : jl_simplevector_type->name->n_uninitialized = 0;
2120 : 1 : jl_simplevector_type->name->names = jl_emptysvec;
2121 : 1 : jl_simplevector_type->types = jl_emptysvec;
2122 : 1 : jl_precompute_memoized_dt(jl_simplevector_type, 1);
2123 : :
2124 : : // now they can be used to create the remaining base kinds and types
2125 : 1 : jl_nothing_type = jl_new_datatype(jl_symbol("Nothing"), core, jl_any_type, jl_emptysvec,
2126 : : jl_emptysvec, jl_emptysvec, jl_emptysvec, 0, 0, 0);
2127 : 1 : jl_void_type = jl_nothing_type; // deprecated alias
2128 : 1 : jl_astaggedvalue(jl_nothing)->header = ((uintptr_t)jl_nothing_type) | GC_OLD_MARKED;
2129 : 1 : jl_nothing_type->instance = jl_nothing;
2130 : :
2131 : 1 : jl_datatype_t *type_type = (jl_datatype_t*)jl_type_type;
2132 : 1 : jl_typeofbottom_type = jl_new_datatype(jl_symbol("TypeofBottom"), core, type_type, jl_emptysvec,
2133 : : jl_emptysvec, jl_emptysvec, jl_emptysvec, 0, 0, 0);
2134 : 1 : jl_bottom_type = jl_new_struct(jl_typeofbottom_type);
2135 : 1 : jl_typeofbottom_type->instance = jl_bottom_type;
2136 : :
2137 : 1 : jl_uniontype_type = jl_new_datatype(jl_symbol("Union"), core, type_type, jl_emptysvec,
2138 : 1 : jl_perm_symsvec(2, "a", "b"),
2139 : 1 : jl_svec(2, jl_any_type, jl_any_type),
2140 : : jl_emptysvec, 0, 0, 2);
2141 : :
2142 : 1 : jl_tvar_type = jl_new_datatype(jl_symbol("TypeVar"), core, jl_any_type, jl_emptysvec,
2143 : 1 : jl_perm_symsvec(3, "name", "lb", "ub"),
2144 : 1 : jl_svec(3, jl_symbol_type, jl_any_type, jl_any_type),
2145 : : jl_emptysvec, 0, 1, 3);
2146 : :
2147 : 1 : jl_unionall_type = jl_new_datatype(jl_symbol("UnionAll"), core, type_type, jl_emptysvec,
2148 : 1 : jl_perm_symsvec(2, "var", "body"),
2149 : 1 : jl_svec(2, jl_tvar_type, jl_any_type),
2150 : : jl_emptysvec, 0, 0, 2);
2151 : :
2152 : 1 : jl_vararg_type = jl_new_datatype(jl_symbol("TypeofVararg"), core, jl_any_type, jl_emptysvec,
2153 : 1 : jl_perm_symsvec(2, "T", "N"),
2154 : 1 : jl_svec(2, jl_any_type, jl_any_type),
2155 : : jl_emptysvec, 0, 0, 0);
2156 : :
2157 : 1 : jl_svec_t *anytuple_params = jl_svec(1, jl_wrap_vararg((jl_value_t*)jl_any_type, (jl_value_t*)NULL));
2158 : 1 : jl_anytuple_type = jl_new_datatype(jl_symbol("Tuple"), core, jl_any_type, anytuple_params,
2159 : : jl_emptysvec, anytuple_params, jl_emptysvec, 0, 0, 0);
2160 : 1 : jl_tuple_typename = jl_anytuple_type->name;
2161 : : // fix some miscomputed values, since we didn't know this was going to be a Tuple in jl_precompute_memoized_dt
2162 : 1 : jl_tuple_typename->wrapper = (jl_value_t*)jl_anytuple_type; // remove UnionAll wrappers
2163 : 1 : jl_anytuple_type->isconcretetype = 0;
2164 : 1 : jl_anytuple_type->layout = NULL;
2165 : 1 : jl_anytuple_type->size = 0;
2166 : 1 : jl_anytuple_type->cached_by_hash = 0;
2167 : :
2168 : 1 : jl_tvar_t *tttvar = tvar("T");
2169 : 1 : ((jl_datatype_t*)jl_type_type)->parameters = jl_svec(1, tttvar);
2170 : 1 : ((jl_datatype_t*)jl_type_type)->hasfreetypevars = 1;
2171 : 1 : ((jl_datatype_t*)jl_type_type)->cached_by_hash = 0;
2172 : 1 : jl_type_typename->wrapper = jl_new_struct(jl_unionall_type, tttvar, (jl_value_t*)jl_type_type);
2173 : 1 : jl_type_type = (jl_unionall_t*)jl_type_typename->wrapper;
2174 : :
2175 : 1 : jl_typeofbottom_type->super = jl_wrap_Type(jl_bottom_type);
2176 : :
2177 : 1 : jl_emptytuple_type = jl_apply_tuple_type(jl_emptysvec);
2178 : 1 : jl_emptytuple = jl_gc_permobj(0, jl_emptytuple_type);
2179 : 1 : jl_emptytuple_type->instance = jl_emptytuple;
2180 : :
2181 : : // non-primitive definitions follow
2182 : 1 : jl_int32_type = jl_new_primitivetype((jl_value_t*)jl_symbol("Int32"), core,
2183 : : jl_any_type, jl_emptysvec, 32);
2184 : 1 : jl_int64_type = jl_new_primitivetype((jl_value_t*)jl_symbol("Int64"), core,
2185 : : jl_any_type, jl_emptysvec, 64);
2186 : 1 : jl_uint32_type = jl_new_primitivetype((jl_value_t*)jl_symbol("UInt32"), core,
2187 : : jl_any_type, jl_emptysvec, 32);
2188 : 1 : jl_uint64_type = jl_new_primitivetype((jl_value_t*)jl_symbol("UInt64"), core,
2189 : : jl_any_type, jl_emptysvec, 64);
2190 : 1 : jl_uint8_type = jl_new_primitivetype((jl_value_t*)jl_symbol("UInt8"), core,
2191 : : jl_any_type, jl_emptysvec, 8);
2192 : 1 : jl_uint16_type = jl_new_primitivetype((jl_value_t*)jl_symbol("UInt16"), core,
2193 : : jl_any_type, jl_emptysvec, 16);
2194 : :
2195 : 2 : jl_ssavalue_type = jl_new_datatype(jl_symbol("SSAValue"), core, jl_any_type, jl_emptysvec,
2196 : 1 : jl_perm_symsvec(1, "id"),
2197 : : jl_svec1(jl_long_type),
2198 : : jl_emptysvec, 0, 0, 1);
2199 : :
2200 : 1 : jl_abstractslot_type = jl_new_abstracttype((jl_value_t*)jl_symbol("Slot"), core, jl_any_type,
2201 : : jl_emptysvec);
2202 : :
2203 : 2 : jl_slotnumber_type = jl_new_datatype(jl_symbol("SlotNumber"), core, jl_abstractslot_type, jl_emptysvec,
2204 : 1 : jl_perm_symsvec(1, "id"),
2205 : : jl_svec1(jl_long_type),
2206 : : jl_emptysvec, 0, 0, 1);
2207 : :
2208 : 1 : jl_typedslot_type = jl_new_datatype(jl_symbol("TypedSlot"), core, jl_abstractslot_type, jl_emptysvec,
2209 : 1 : jl_perm_symsvec(2, "id", "typ"),
2210 : 1 : jl_svec(2, jl_long_type, jl_any_type),
2211 : : jl_emptysvec, 0, 0, 2);
2212 : :
2213 : 2 : jl_argument_type = jl_new_datatype(jl_symbol("Argument"), core, jl_any_type, jl_emptysvec,
2214 : 1 : jl_perm_symsvec(1, "n"),
2215 : : jl_svec1(jl_long_type),
2216 : : jl_emptysvec, 0, 0, 1);
2217 : :
2218 : 1 : jl_init_int32_int64_cache();
2219 : :
2220 : 1 : jl_bool_type = NULL;
2221 : 1 : jl_bool_type = jl_new_primitivetype((jl_value_t*)jl_symbol("Bool"), core,
2222 : : jl_any_type, jl_emptysvec, 8);
2223 : 1 : jl_false = jl_permbox8(jl_bool_type, 0);
2224 : 1 : jl_true = jl_permbox8(jl_bool_type, 1);
2225 : :
2226 : 1 : jl_abstractstring_type = jl_new_abstracttype((jl_value_t*)jl_symbol("AbstractString"), core, jl_any_type, jl_emptysvec);
2227 : 1 : jl_string_type = jl_new_datatype(jl_symbol("String"), core, jl_abstractstring_type, jl_emptysvec,
2228 : : jl_emptysvec, jl_emptysvec, jl_emptysvec, 0, 1, 0);
2229 : 1 : jl_string_type->instance = NULL;
2230 : 1 : jl_compute_field_offsets(jl_string_type);
2231 : 1 : jl_an_empty_string = jl_pchar_to_string("\0", 1);
2232 : 1 : *(size_t*)jl_an_empty_string = 0;
2233 : :
2234 : 1 : jl_typemap_level_type =
2235 : 1 : jl_new_datatype(jl_symbol("TypeMapLevel"), core, jl_any_type, jl_emptysvec,
2236 : 1 : jl_perm_symsvec(6,
2237 : : "arg1",
2238 : : "targ",
2239 : : "name1",
2240 : : "tname",
2241 : : "list",
2242 : : "any"),
2243 : 1 : jl_svec(6,
2244 : : jl_any_type,
2245 : : jl_any_type,
2246 : : jl_any_type,
2247 : : jl_any_type,
2248 : : jl_any_type,
2249 : : jl_any_type),
2250 : : jl_emptysvec,
2251 : : 0, 1, 6);
2252 : :
2253 : 1 : jl_typemap_entry_type =
2254 : 1 : jl_new_datatype(jl_symbol("TypeMapEntry"), core, jl_any_type, jl_emptysvec,
2255 : 1 : jl_perm_symsvec(10,
2256 : : "next",
2257 : : "sig",
2258 : : "simplesig",
2259 : : "guardsigs",
2260 : : "min_world",
2261 : : "max_world",
2262 : : "func",
2263 : : "isleafsig",
2264 : : "issimplesig",
2265 : : "va"),
2266 : 1 : jl_svec(10,
2267 : : jl_any_type, // Union{TypeMapEntry, Nothing}
2268 : : jl_type_type, // TupleType
2269 : : jl_any_type, // TupleType
2270 : : jl_any_type, // SimpleVector{TupleType}
2271 : : jl_ulong_type, // UInt
2272 : : jl_ulong_type, // UInt
2273 : : jl_any_type, // Any
2274 : : jl_bool_type,
2275 : : jl_bool_type,
2276 : : jl_bool_type),
2277 : : jl_emptysvec,
2278 : : 0, 1, 4);
2279 : : const static uint32_t typemap_entry_constfields[1] = { 0x000003fe }; // (1<<1)|(1<<2)|(1<<3)|(1<<4)|(1<<5)|(1<<6)|(1<<7)|(1<<8)|(1<<9);
2280 : 1 : jl_typemap_entry_type->name->constfields = typemap_entry_constfields;
2281 : :
2282 : 1 : jl_function_type = jl_new_abstracttype((jl_value_t*)jl_symbol("Function"), core, jl_any_type, jl_emptysvec);
2283 : 1 : jl_builtin_type = jl_new_abstracttype((jl_value_t*)jl_symbol("Builtin"), core, jl_function_type, jl_emptysvec);
2284 : 1 : jl_function_type->name->mt = NULL; // subtypes of Function have independent method tables
2285 : 1 : jl_builtin_type->name->mt = NULL; // so they don't share the Any type table
2286 : :
2287 : 1 : jl_svec_t *tv = jl_svec2(tvar("T"), tvar("N"));
2288 : 1 : jl_abstractarray_type = (jl_unionall_t*)
2289 : 1 : jl_new_abstracttype((jl_value_t*)jl_symbol("AbstractArray"), core,
2290 : 1 : jl_any_type, tv)->name->wrapper;
2291 : :
2292 : 1 : tv = jl_svec2(tvar("T"), tvar("N"));
2293 : 1 : jl_densearray_type = (jl_unionall_t*)
2294 : 1 : jl_new_abstracttype((jl_value_t*)jl_symbol("DenseArray"), core,
2295 : 1 : (jl_datatype_t*)jl_apply_type((jl_value_t*)jl_abstractarray_type, jl_svec_data(tv), 2),
2296 : 1 : tv)->name->wrapper;
2297 : :
2298 : 1 : tv = jl_svec2(tvar("T"), tvar("N"));
2299 : 1 : jl_array_type = (jl_unionall_t*)
2300 : 1 : jl_new_datatype(jl_symbol("Array"), core,
2301 : 1 : (jl_datatype_t*)jl_apply_type((jl_value_t*)jl_densearray_type, jl_svec_data(tv), 2),
2302 : 1 : tv, jl_emptysvec, jl_emptysvec, jl_emptysvec, 0, 1, 0)->name->wrapper;
2303 : 1 : jl_array_typename = ((jl_datatype_t*)jl_unwrap_unionall((jl_value_t*)jl_array_type))->name;
2304 : 1 : jl_compute_field_offsets((jl_datatype_t*)jl_unwrap_unionall((jl_value_t*)jl_array_type));
2305 : :
2306 : 1 : jl_array_any_type = jl_apply_type2((jl_value_t*)jl_array_type, (jl_value_t*)jl_any_type, jl_box_long(1));
2307 : 1 : jl_array_symbol_type = jl_apply_type2((jl_value_t*)jl_array_type, (jl_value_t*)jl_symbol_type, jl_box_long(1));
2308 : 1 : jl_array_uint8_type = jl_apply_type2((jl_value_t*)jl_array_type, (jl_value_t*)jl_uint8_type, jl_box_long(1));
2309 : 1 : jl_array_int32_type = jl_apply_type2((jl_value_t*)jl_array_type, (jl_value_t*)jl_int32_type, jl_box_long(1));
2310 : 1 : jl_array_uint64_type = jl_apply_type2((jl_value_t*)jl_array_type, (jl_value_t*)jl_uint64_type, jl_box_long(1));
2311 : 1 : jl_an_empty_vec_any = (jl_value_t*)jl_alloc_vec_any(0); // used internally
2312 : 1 : jl_atomic_store_relaxed(&jl_nonfunction_mt->leafcache, (jl_array_t*)jl_an_empty_vec_any);
2313 : 1 : jl_atomic_store_relaxed(&jl_type_type_mt->leafcache, (jl_array_t*)jl_an_empty_vec_any);
2314 : :
2315 : 1 : jl_expr_type =
2316 : 1 : jl_new_datatype(jl_symbol("Expr"), core,
2317 : : jl_any_type, jl_emptysvec,
2318 : 1 : jl_perm_symsvec(2, "head", "args"),
2319 : 1 : jl_svec(2, jl_symbol_type, jl_array_any_type),
2320 : : jl_emptysvec, 0, 1, 2);
2321 : :
2322 : 1 : jl_module_type =
2323 : 1 : jl_new_datatype(jl_symbol("Module"), core, jl_any_type, jl_emptysvec,
2324 : : jl_emptysvec, jl_emptysvec, jl_emptysvec, 0, 1, 0);
2325 : 1 : jl_module_type->instance = NULL;
2326 : 1 : jl_compute_field_offsets(jl_module_type);
2327 : :
2328 : 1 : jl_value_t *symornothing[2] = { (jl_value_t*)jl_symbol_type, (jl_value_t*)jl_void_type };
2329 : 1 : jl_linenumbernode_type =
2330 : 2 : jl_new_datatype(jl_symbol("LineNumberNode"), core, jl_any_type, jl_emptysvec,
2331 : 1 : jl_perm_symsvec(2, "line", "file"),
2332 : 1 : jl_svec(2, jl_long_type, jl_type_union(symornothing, 2)),
2333 : : jl_emptysvec, 0, 0, 2);
2334 : :
2335 : 1 : jl_lineinfonode_type =
2336 : 1 : jl_new_datatype(jl_symbol("LineInfoNode"), core, jl_any_type, jl_emptysvec,
2337 : 1 : jl_perm_symsvec(5, "module", "method", "file", "line", "inlined_at"),
2338 : 1 : jl_svec(5, jl_module_type, jl_any_type, jl_symbol_type, jl_int32_type, jl_int32_type),
2339 : : jl_emptysvec, 0, 0, 5);
2340 : :
2341 : 1 : jl_gotonode_type =
2342 : 1 : jl_new_datatype(jl_symbol("GotoNode"), core, jl_any_type, jl_emptysvec,
2343 : 1 : jl_perm_symsvec(1, "label"),
2344 : 1 : jl_svec(1, jl_long_type),
2345 : : jl_emptysvec, 0, 0, 1);
2346 : :
2347 : 1 : jl_gotoifnot_type =
2348 : 1 : jl_new_datatype(jl_symbol("GotoIfNot"), core, jl_any_type, jl_emptysvec,
2349 : 1 : jl_perm_symsvec(2, "cond", "dest"),
2350 : 1 : jl_svec(2, jl_any_type, jl_long_type),
2351 : : jl_emptysvec, 0, 0, 2);
2352 : :
2353 : 1 : jl_returnnode_type =
2354 : 1 : jl_new_datatype(jl_symbol("ReturnNode"), core, jl_any_type, jl_emptysvec,
2355 : 1 : jl_perm_symsvec(1, "val"),
2356 : 1 : jl_svec(1, jl_any_type),
2357 : : jl_emptysvec, 0, 0, 0);
2358 : :
2359 : 1 : jl_pinode_type =
2360 : 1 : jl_new_datatype(jl_symbol("PiNode"), core, jl_any_type, jl_emptysvec,
2361 : 1 : jl_perm_symsvec(2, "val", "typ"),
2362 : 1 : jl_svec(2, jl_any_type, jl_any_type),
2363 : : jl_emptysvec, 0, 0, 2);
2364 : :
2365 : 1 : jl_phinode_type =
2366 : 1 : jl_new_datatype(jl_symbol("PhiNode"), core, jl_any_type, jl_emptysvec,
2367 : 1 : jl_perm_symsvec(2, "edges", "values"),
2368 : 1 : jl_svec(2, jl_array_int32_type, jl_array_any_type),
2369 : : jl_emptysvec, 0, 0, 2);
2370 : :
2371 : 1 : jl_phicnode_type =
2372 : 1 : jl_new_datatype(jl_symbol("PhiCNode"), core, jl_any_type, jl_emptysvec,
2373 : 1 : jl_perm_symsvec(1, "values"),
2374 : 1 : jl_svec(1, jl_array_any_type),
2375 : : jl_emptysvec, 0, 0, 1);
2376 : :
2377 : 1 : jl_upsilonnode_type =
2378 : 1 : jl_new_datatype(jl_symbol("UpsilonNode"), core, jl_any_type, jl_emptysvec,
2379 : 1 : jl_perm_symsvec(1, "val"),
2380 : 1 : jl_svec(1, jl_any_type),
2381 : : jl_emptysvec, 0, 0, 0);
2382 : :
2383 : 1 : jl_quotenode_type =
2384 : 1 : jl_new_datatype(jl_symbol("QuoteNode"), core, jl_any_type, jl_emptysvec,
2385 : 1 : jl_perm_symsvec(1, "value"),
2386 : 1 : jl_svec(1, jl_any_type),
2387 : : jl_emptysvec, 0, 0, 1);
2388 : :
2389 : 1 : jl_newvarnode_type =
2390 : 1 : jl_new_datatype(jl_symbol("NewvarNode"), core, jl_any_type, jl_emptysvec,
2391 : 1 : jl_perm_symsvec(1, "slot"),
2392 : 1 : jl_svec(1, jl_slotnumber_type),
2393 : : jl_emptysvec, 0, 0, 1);
2394 : :
2395 : 1 : jl_globalref_type =
2396 : 1 : jl_new_datatype(jl_symbol("GlobalRef"), core, jl_any_type, jl_emptysvec,
2397 : 1 : jl_perm_symsvec(2, "mod", "name"),
2398 : 1 : jl_svec(2, jl_module_type, jl_symbol_type),
2399 : : jl_emptysvec, 0, 0, 2);
2400 : :
2401 : 1 : jl_code_info_type =
2402 : 1 : jl_new_datatype(jl_symbol("CodeInfo"), core,
2403 : : jl_any_type, jl_emptysvec,
2404 : 1 : jl_perm_symsvec(20,
2405 : : "code",
2406 : : "codelocs",
2407 : : "ssavaluetypes",
2408 : : "ssaflags",
2409 : : "method_for_inference_limit_heuristics",
2410 : : "linetable",
2411 : : "slotnames",
2412 : : "slotflags",
2413 : : "slottypes",
2414 : : "rettype",
2415 : : "parent",
2416 : : "edges",
2417 : : "min_world",
2418 : : "max_world",
2419 : : "inferred",
2420 : : "inlineable",
2421 : : "propagate_inbounds",
2422 : : "pure",
2423 : : "constprop",
2424 : : "purity"),
2425 : 1 : jl_svec(20,
2426 : : jl_array_any_type,
2427 : : jl_array_int32_type,
2428 : : jl_any_type,
2429 : : jl_array_uint8_type,
2430 : : jl_any_type,
2431 : : jl_any_type,
2432 : : jl_array_symbol_type,
2433 : : jl_array_uint8_type,
2434 : : jl_any_type,
2435 : : jl_any_type,
2436 : : jl_any_type,
2437 : : jl_any_type,
2438 : : jl_ulong_type,
2439 : : jl_ulong_type,
2440 : : jl_bool_type,
2441 : : jl_bool_type,
2442 : : jl_bool_type,
2443 : : jl_bool_type,
2444 : : jl_uint8_type,
2445 : : jl_uint8_type),
2446 : : jl_emptysvec,
2447 : : 0, 1, 20);
2448 : :
2449 : 1 : jl_method_type =
2450 : 1 : jl_new_datatype(jl_symbol("Method"), core,
2451 : : jl_any_type, jl_emptysvec,
2452 : 1 : jl_perm_symsvec(29,
2453 : : "name",
2454 : : "module",
2455 : : "file",
2456 : : "line",
2457 : : "primary_world",
2458 : : "deleted_world", // !const
2459 : : "sig",
2460 : : "specializations", // !const
2461 : : "speckeyset", // !const
2462 : : "slot_syms",
2463 : : "external_mt",
2464 : : "source", // !const
2465 : : "unspecialized", // !const
2466 : : "generator", // !const
2467 : : "roots", // !const
2468 : : "root_blocks", // !const
2469 : : "nroots_sysimg",
2470 : : "ccallable", // !const
2471 : : "invokes", // !const
2472 : : "recursion_relation", // !const
2473 : : "nargs",
2474 : : "called",
2475 : : "nospecialize",
2476 : : "nkw",
2477 : : "isva",
2478 : : "pure",
2479 : : "is_for_opaque_closure",
2480 : : "constprop",
2481 : : "purity"),
2482 : 1 : jl_svec(29,
2483 : : jl_symbol_type,
2484 : : jl_module_type,
2485 : : jl_symbol_type,
2486 : : jl_int32_type,
2487 : : jl_ulong_type,
2488 : : jl_ulong_type,
2489 : : jl_type_type,
2490 : : jl_simplevector_type,
2491 : : jl_array_type,
2492 : : jl_string_type,
2493 : : jl_any_type,
2494 : : jl_any_type,
2495 : : jl_any_type, // jl_method_instance_type
2496 : : jl_any_type,
2497 : : jl_array_any_type,
2498 : : jl_array_uint64_type,
2499 : : jl_int32_type,
2500 : : jl_simplevector_type,
2501 : : jl_any_type,
2502 : : jl_any_type,
2503 : : jl_int32_type,
2504 : : jl_int32_type,
2505 : : jl_int32_type,
2506 : : jl_int32_type,
2507 : : jl_bool_type,
2508 : : jl_bool_type,
2509 : : jl_bool_type,
2510 : : jl_uint8_type,
2511 : : jl_uint8_type),
2512 : : jl_emptysvec,
2513 : : 0, 1, 10);
2514 : : //const static uint32_t method_constfields[1] = { 0x03fc065f }; // (1<<0)|(1<<1)|(1<<2)|(1<<3)|(1<<4)|(1<<6)|(1<<9)|(1<<10)|(1<<18)|(1<<19)|(1<<20)|(1<<21)|(1<<22)|(1<<23)|(1<<24)|(1<<25);
2515 : : //jl_method_type->name->constfields = method_constfields;
2516 : :
2517 : 1 : jl_method_instance_type =
2518 : 2 : jl_new_datatype(jl_symbol("MethodInstance"), core,
2519 : : jl_any_type, jl_emptysvec,
2520 : 1 : jl_perm_symsvec(9,
2521 : : "def",
2522 : : "specTypes",
2523 : : "sparam_vals",
2524 : : "uninferred",
2525 : : "backedges",
2526 : : "callbacks",
2527 : : "cache",
2528 : : "inInference",
2529 : : "precompiled"),
2530 : 1 : jl_svec(9,
2531 : : jl_new_struct(jl_uniontype_type, jl_method_type, jl_module_type),
2532 : : jl_any_type,
2533 : : jl_simplevector_type,
2534 : : jl_any_type,
2535 : : jl_any_type,
2536 : : jl_any_type,
2537 : : jl_any_type,
2538 : : jl_bool_type,
2539 : : jl_bool_type),
2540 : : jl_emptysvec,
2541 : : 0, 1, 3);
2542 : : //const static uint32_t method_instance_constfields[1] = { 0x00000007 }; // (1<<0)|(1<<1)|(1<<2);
2543 : : //jl_method_instance_type->name->constfields = method_instance_constfields;
2544 : :
2545 : 1 : jl_code_instance_type =
2546 : 1 : jl_new_datatype(jl_symbol("CodeInstance"), core,
2547 : : jl_any_type, jl_emptysvec,
2548 : 1 : jl_perm_symsvec(15,
2549 : : "def",
2550 : : "next",
2551 : : "min_world",
2552 : : "max_world",
2553 : : "rettype",
2554 : : "rettype_const",
2555 : : "inferred",
2556 : : //"edges",
2557 : : //"absolute_max",
2558 : : "ipo_purity_bits", "purity_bits",
2559 : : "argescapes",
2560 : : "isspecsig", "precompile", "invoke", "specptr", // function object decls
2561 : : "relocatability"),
2562 : 1 : jl_svec(15,
2563 : : jl_method_instance_type,
2564 : : jl_any_type,
2565 : : jl_ulong_type,
2566 : : jl_ulong_type,
2567 : : jl_any_type,
2568 : : jl_any_type,
2569 : : jl_any_type,
2570 : : //jl_any_type,
2571 : : //jl_bool_type,
2572 : : jl_uint32_type, jl_uint32_type,
2573 : : jl_any_type,
2574 : : jl_bool_type,
2575 : : jl_bool_type,
2576 : : jl_any_type, jl_any_type, // fptrs
2577 : : jl_uint8_type),
2578 : : jl_emptysvec,
2579 : : 0, 1, 1);
2580 : 1 : jl_svecset(jl_code_instance_type->types, 1, jl_code_instance_type);
2581 : : const static uint32_t code_instance_constfields[1] = { 0x00000001 }; // (1<<1);
2582 : 1 : jl_code_instance_type->name->constfields = code_instance_constfields;
2583 : :
2584 : 2 : jl_const_type = jl_new_datatype(jl_symbol("Const"), core, jl_any_type, jl_emptysvec,
2585 : 1 : jl_perm_symsvec(1, "val"),
2586 : : jl_svec1(jl_any_type),
2587 : : jl_emptysvec, 0, 0, 1);
2588 : :
2589 : 2 : jl_partial_struct_type = jl_new_datatype(jl_symbol("PartialStruct"), core, jl_any_type, jl_emptysvec,
2590 : 1 : jl_perm_symsvec(2, "typ", "fields"),
2591 : : jl_svec2(jl_datatype_type, jl_array_any_type),
2592 : : jl_emptysvec, 0, 0, 2);
2593 : :
2594 : 1 : jl_interconditional_type = jl_new_datatype(jl_symbol("InterConditional"), core, jl_any_type, jl_emptysvec,
2595 : 1 : jl_perm_symsvec(3, "slot", "thentype", "elsetype"),
2596 : 1 : jl_svec(3, jl_long_type, jl_any_type, jl_any_type),
2597 : : jl_emptysvec, 0, 0, 3);
2598 : :
2599 : 1 : jl_method_match_type = jl_new_datatype(jl_symbol("MethodMatch"), core, jl_any_type, jl_emptysvec,
2600 : 1 : jl_perm_symsvec(4, "spec_types", "sparams", "method", "fully_covers"),
2601 : 1 : jl_svec(4, jl_type_type, jl_simplevector_type, jl_method_type, jl_bool_type),
2602 : : jl_emptysvec, 0, 0, 4);
2603 : :
2604 : : // all Kinds share the Type method table (not the nonfunction one)
2605 : 1 : jl_unionall_type->name->mt = jl_uniontype_type->name->mt = jl_datatype_type->name->mt =
2606 : : jl_type_type_mt;
2607 : :
2608 : 1 : jl_intrinsic_type = jl_new_primitivetype((jl_value_t*)jl_symbol("IntrinsicFunction"), core,
2609 : : jl_builtin_type, jl_emptysvec, 32);
2610 : :
2611 : 1 : tv = jl_svec1(tvar("T"));
2612 : 1 : jl_ref_type = (jl_unionall_t*)
2613 : 1 : jl_new_abstracttype((jl_value_t*)jl_symbol("Ref"), core, jl_any_type, tv)->name->wrapper;
2614 : :
2615 : 1 : tv = jl_svec1(tvar("T"));
2616 : 1 : jl_pointer_type = (jl_unionall_t*)
2617 : 1 : jl_new_primitivetype((jl_value_t*)jl_symbol("Ptr"), core,
2618 : 1 : (jl_datatype_t*)jl_apply_type((jl_value_t*)jl_ref_type, jl_svec_data(tv), 1), tv,
2619 : 1 : sizeof(void*)*8)->name->wrapper;
2620 : 1 : jl_pointer_typename = ((jl_datatype_t*)jl_unwrap_unionall((jl_value_t*)jl_pointer_type))->name;
2621 : :
2622 : : // LLVMPtr{T, AS} where {T, AS}
2623 : 1 : tv = jl_svec2(tvar("T"), tvar("AS"));
2624 : 1 : jl_svec_t *tv_base = jl_svec1(tvar("T"));
2625 : 1 : jl_llvmpointer_type = (jl_unionall_t*)
2626 : 1 : jl_new_primitivetype((jl_value_t*)jl_symbol("LLVMPtr"), core,
2627 : 1 : (jl_datatype_t*)jl_apply_type((jl_value_t*)jl_ref_type, jl_svec_data(tv_base), 1), tv,
2628 : 1 : sizeof(void*)*8)->name->wrapper;
2629 : 1 : jl_llvmpointer_typename = ((jl_datatype_t*)jl_unwrap_unionall((jl_value_t*)jl_llvmpointer_type))->name;
2630 : :
2631 : : // Type{T} where T<:Tuple
2632 : 1 : tttvar = jl_new_typevar(jl_symbol("T"),
2633 : : (jl_value_t*)jl_bottom_type,
2634 : : (jl_value_t*)jl_anytuple_type);
2635 : 1 : jl_anytuple_type_type = (jl_unionall_t*)jl_new_struct(jl_unionall_type,
2636 : 1 : tttvar, (jl_value_t*)jl_wrap_Type((jl_value_t*)tttvar));
2637 : :
2638 : 1 : jl_tvar_t *ntval_var = jl_new_typevar(jl_symbol("T"), (jl_value_t*)jl_bottom_type,
2639 : : (jl_value_t*)jl_anytuple_type);
2640 : 1 : tv = jl_svec2(tvar("names"), ntval_var);
2641 : 1 : jl_datatype_t *ntt = jl_new_datatype(jl_symbol("NamedTuple"), core, jl_any_type, tv,
2642 : : jl_emptysvec, jl_emptysvec, jl_emptysvec, 0, 0, 0);
2643 : 1 : jl_namedtuple_type = (jl_unionall_t*)ntt->name->wrapper;
2644 : 1 : ((jl_datatype_t*)jl_unwrap_unionall((jl_value_t*)jl_namedtuple_type))->layout = NULL;
2645 : 1 : jl_namedtuple_typename = ntt->name;
2646 : :
2647 : 1 : jl_task_type = (jl_datatype_t*)
2648 : : jl_new_datatype(jl_symbol("Task"),
2649 : : NULL,
2650 : : jl_any_type,
2651 : : jl_emptysvec,
2652 : 1 : jl_perm_symsvec(15,
2653 : : "next",
2654 : : "queue",
2655 : : "storage",
2656 : : "donenotify",
2657 : : "result",
2658 : : "logstate",
2659 : : "code",
2660 : : "rngState0",
2661 : : "rngState1",
2662 : : "rngState2",
2663 : : "rngState3",
2664 : : "_state",
2665 : : "sticky",
2666 : : "_isexception",
2667 : : "priority"),
2668 : 1 : jl_svec(15,
2669 : : jl_any_type,
2670 : : jl_any_type,
2671 : : jl_any_type,
2672 : : jl_any_type,
2673 : : jl_any_type,
2674 : : jl_any_type,
2675 : : jl_any_type,
2676 : : jl_uint64_type,
2677 : : jl_uint64_type,
2678 : : jl_uint64_type,
2679 : : jl_uint64_type,
2680 : : jl_uint8_type,
2681 : : jl_bool_type,
2682 : : jl_bool_type,
2683 : : jl_uint16_type),
2684 : : jl_emptysvec,
2685 : : 0, 1, 6);
2686 : 1 : jl_value_t *listt = jl_new_struct(jl_uniontype_type, jl_task_type, jl_nothing_type);
2687 : 1 : jl_svecset(jl_task_type->types, 0, listt);
2688 : 1 : jl_astaggedvalue(jl_current_task)->header = (uintptr_t)jl_task_type | jl_astaggedvalue(jl_current_task)->header;
2689 : :
2690 : 1 : jl_value_t *pointer_void = jl_apply_type1((jl_value_t*)jl_pointer_type, (jl_value_t*)jl_nothing_type);
2691 : :
2692 : 1 : tv = jl_svec2(tvar("A"), tvar("R"));
2693 : 1 : jl_opaque_closure_type = (jl_unionall_t*)jl_new_datatype(jl_symbol("OpaqueClosure"), core, jl_function_type, tv,
2694 : 1 : jl_perm_symsvec(5, "captures", "world", "source", "invoke", "specptr"),
2695 : 1 : jl_svec(5, jl_any_type, jl_long_type, jl_any_type, pointer_void, pointer_void),
2696 : 1 : jl_emptysvec, 0, 0, 5)->name->wrapper;
2697 : 1 : jl_opaque_closure_typename = ((jl_datatype_t*)jl_unwrap_unionall((jl_value_t*)jl_opaque_closure_type))->name;
2698 : 1 : jl_compute_field_offsets((jl_datatype_t*)jl_unwrap_unionall((jl_value_t*)jl_opaque_closure_type));
2699 : :
2700 : 1 : jl_partial_opaque_type = jl_new_datatype(jl_symbol("PartialOpaque"), core, jl_any_type, jl_emptysvec,
2701 : 1 : jl_perm_symsvec(4, "typ", "env", "parent", "source"),
2702 : 1 : jl_svec(4, jl_type_type, jl_any_type, jl_method_instance_type, jl_method_type),
2703 : : jl_emptysvec, 0, 0, 4);
2704 : :
2705 : : // complete builtin type metadata
2706 : 1 : jl_voidpointer_type = (jl_datatype_t*)pointer_void;
2707 : 1 : jl_uint8pointer_type = (jl_datatype_t*)jl_apply_type1((jl_value_t*)jl_pointer_type, (jl_value_t*)jl_uint8_type);
2708 : 1 : jl_svecset(jl_datatype_type->types, 5, jl_voidpointer_type);
2709 : 1 : jl_svecset(jl_datatype_type->types, 6, jl_int32_type);
2710 : 1 : jl_svecset(jl_datatype_type->types, 7, jl_int32_type);
2711 : 1 : jl_svecset(jl_datatype_type->types, 8, jl_uint8_type);
2712 : 1 : jl_svecset(jl_typename_type->types, 1, jl_module_type);
2713 : 1 : jl_svecset(jl_typename_type->types, 3, jl_voidpointer_type);
2714 : 1 : jl_svecset(jl_typename_type->types, 4, jl_voidpointer_type);
2715 : 1 : jl_svecset(jl_typename_type->types, 5, jl_type_type);
2716 : 1 : jl_svecset(jl_typename_type->types, 6, jl_type_type);
2717 : 1 : jl_svecset(jl_typename_type->types, 11, jl_long_type);
2718 : 1 : jl_svecset(jl_typename_type->types, 12, jl_int32_type);
2719 : 1 : jl_svecset(jl_typename_type->types, 13, jl_uint8_type);
2720 : 1 : jl_svecset(jl_typename_type->types, 14, jl_uint8_type);
2721 : 1 : jl_svecset(jl_methtable_type->types, 4, jl_long_type);
2722 : 1 : jl_svecset(jl_methtable_type->types, 6, jl_module_type);
2723 : 1 : jl_svecset(jl_methtable_type->types, 7, jl_array_any_type);
2724 : 1 : jl_svecset(jl_methtable_type->types, 8, jl_long_type); // voidpointer
2725 : 1 : jl_svecset(jl_methtable_type->types, 9, jl_long_type); // uint32_t plus alignment
2726 : 1 : jl_svecset(jl_methtable_type->types, 10, jl_uint8_type);
2727 : 1 : jl_svecset(jl_methtable_type->types, 11, jl_uint8_type);
2728 : 1 : jl_svecset(jl_method_type->types, 12, jl_method_instance_type);
2729 : 1 : jl_svecset(jl_method_instance_type->types, 6, jl_code_instance_type);
2730 : 1 : jl_svecset(jl_code_instance_type->types, 12, jl_voidpointer_type);
2731 : 1 : jl_svecset(jl_code_instance_type->types, 13, jl_voidpointer_type);
2732 : :
2733 : 1 : jl_compute_field_offsets(jl_datatype_type);
2734 : 1 : jl_compute_field_offsets(jl_typename_type);
2735 : 1 : jl_compute_field_offsets(jl_uniontype_type);
2736 : 1 : jl_compute_field_offsets(jl_tvar_type);
2737 : 1 : jl_compute_field_offsets(jl_methtable_type);
2738 : 1 : jl_compute_field_offsets(jl_module_type);
2739 : 1 : jl_compute_field_offsets(jl_method_instance_type);
2740 : 1 : jl_compute_field_offsets(jl_code_instance_type);
2741 : 1 : jl_compute_field_offsets(jl_unionall_type);
2742 : 1 : jl_compute_field_offsets(jl_simplevector_type);
2743 : 1 : jl_compute_field_offsets(jl_symbol_type);
2744 : :
2745 : : // override the preferred layout for a couple types
2746 : 1 : jl_lineinfonode_type->name->mayinlinealloc = 0; // FIXME: assumed to be a pointer by codegen
2747 : : // It seems like we probably usually end up needing the box for kinds (used in an Any context)--but is that true?
2748 : 1 : jl_uniontype_type->name->mayinlinealloc = 0;
2749 : 1 : jl_unionall_type->name->mayinlinealloc = 0;
2750 : 1 : }
2751 : :
2752 : : #ifdef __cplusplus
2753 : : }
2754 : : #endif
|
