Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : #include <stdlib.h>
4 : : #include <string.h>
5 : : #include "julia.h"
6 : : #include "julia_internal.h"
7 : : #ifndef _OS_WINDOWS_
8 : : #include <unistd.h>
9 : : #endif
10 : : #include "julia_assert.h"
11 : :
12 : : #define MAX_METHLIST_COUNT 12 // this can strongly affect the sysimg size and speed!
13 : :
14 : : #ifdef __cplusplus
15 : : extern "C" {
16 : : #endif
17 : :
18 : : // compute whether the specificity of this type is equivalent to Any in the sort order
19 : 595936 : static int jl_is_any(jl_value_t *t1)
20 : : {
21 [ + + ]: 597243 : while (jl_is_typevar(t1))
22 : 1307 : t1 = ((jl_tvar_t*)t1)->ub;
23 : 595936 : return t1 == (jl_value_t*)jl_any_type;
24 : : }
25 : :
26 : 16152400 : static jl_value_t *jl_type_extract_name(jl_value_t *t1 JL_PROPAGATES_ROOT)
27 : : {
28 [ + + ]: 16152400 : if (jl_is_unionall(t1))
29 : 6964460 : t1 = jl_unwrap_unionall(t1);
30 [ - + ]: 16152400 : if (jl_is_vararg(t1)) {
31 : 0 : return jl_type_extract_name(jl_unwrap_vararg(t1));
32 : : }
33 [ + + ]: 16152400 : else if (jl_is_typevar(t1)) {
34 : 45438 : return jl_type_extract_name(((jl_tvar_t*)t1)->ub);
35 : : }
36 [ + + ]: 16107000 : else if (jl_is_datatype(t1)) {
37 : 15276900 : jl_datatype_t *dt = (jl_datatype_t*)t1;
38 [ + + ]: 15276900 : if (!jl_is_kind(t1))
39 : 15242700 : return (jl_value_t*)dt->name;
40 : 34243 : return NULL;
41 : : }
42 [ + + ]: 830051 : else if (jl_is_uniontype(t1)) {
43 : 822588 : jl_uniontype_t *u1 = (jl_uniontype_t*)t1;
44 : 822588 : jl_value_t *tn1 = jl_type_extract_name(u1->a);
45 : 822588 : jl_value_t *tn2 = jl_type_extract_name(u1->b);
46 [ + + ]: 822588 : if (tn1 == tn2)
47 : 4974 : return tn1;
48 : : // TODO: if invariant is false, instead find the nearest common ancestor
49 : 817614 : return NULL;
50 : : }
51 : 7463 : return NULL;
52 : : }
53 : :
54 : : // return false if the name extracted above is an over-approximation
55 : : // (such that intersection also needs to consider the subtypes)
56 : 2455100 : static int jl_type_extract_name_precise(jl_value_t *t1, int invariant)
57 : : {
58 [ + + ]: 2455100 : if (jl_is_unionall(t1))
59 : 458265 : t1 = jl_unwrap_unionall(t1);
60 [ - + ]: 2455100 : if (jl_is_vararg(t1)) {
61 : 0 : return jl_type_extract_name_precise(jl_unwrap_vararg(t1), invariant);
62 : : }
63 [ - + ]: 2455100 : else if (jl_is_typevar(t1)) {
64 : 0 : return jl_type_extract_name_precise(((jl_tvar_t*)t1)->ub, 0);
65 : : }
66 [ + + ]: 2455100 : else if (jl_is_datatype(t1)) {
67 : 2453380 : jl_datatype_t *dt = (jl_datatype_t*)t1;
68 [ + + + + : 2453380 : if ((invariant || !dt->name->abstract) && !jl_is_kind(t1))
+ - ]
69 : 1837600 : return 1;
70 : 615781 : return 0;
71 : : }
72 [ + - ]: 1727 : else if (jl_is_uniontype(t1)) {
73 : 1727 : jl_uniontype_t *u1 = (jl_uniontype_t*)t1;
74 [ + + ]: 1727 : if (!jl_type_extract_name_precise(u1->a, invariant))
75 : 693 : return 0;
76 [ - + ]: 1034 : if (!jl_type_extract_name_precise(u1->b, invariant))
77 : 0 : return 0;
78 : 1034 : jl_value_t *tn1 = jl_type_extract_name(u1->a);
79 : 1034 : jl_value_t *tn2 = jl_type_extract_name(u1->b);
80 [ + - ]: 1034 : if (tn1 == tn2)
81 : 1034 : return 1;
82 : 0 : return 0;
83 : : }
84 : 0 : return 1;
85 : : }
86 : :
87 : :
88 : : // ----- Type Signature Subtype Testing ----- //
89 : :
90 : 136 : static int sig_match_by_type_leaf(jl_value_t **types, jl_tupletype_t *sig, size_t n)
91 : : {
92 : : size_t i;
93 [ + + ]: 286 : for (i = 0; i < n; i++) {
94 : 284 : jl_value_t *decl = jl_tparam(sig, i);
95 : 284 : jl_value_t *a = types[i];
96 [ + + ]: 284 : if (jl_is_type_type(a)) // decl is not Type, because it wouldn't be leafsig
97 : 1 : a = jl_typeof(jl_tparam0(a));
98 [ + + ]: 284 : if (!jl_types_equal(a, decl))
99 : 134 : return 0;
100 : : }
101 : 2 : return 1;
102 : : }
103 : :
104 : 10169200 : static int sig_match_by_type_simple(jl_value_t **types, size_t n, jl_tupletype_t *sig, size_t lensig, int va)
105 : : {
106 : : size_t i;
107 [ + + ]: 10169200 : if (va) lensig -= 1;
108 [ + + ]: 29880000 : for (i = 0; i < lensig; i++) {
109 : 24595300 : jl_value_t *decl = jl_tparam(sig, i);
110 : 24595300 : jl_value_t *a = types[i];
111 [ - + ]: 24595300 : jl_value_t *unw = jl_is_unionall(decl) ? ((jl_unionall_t*)decl)->body : decl;
112 [ + + ]: 24595300 : if (jl_is_vararg(a))
113 : 144 : return 0;
114 [ + + ]: 24595100 : if (jl_is_type_type(unw)) {
115 : 1881040 : jl_value_t *tp0 = jl_tparam0(unw);
116 [ + - ]: 1881040 : if (jl_is_type_type(a)) {
117 [ - + ]: 1881040 : if (jl_is_typevar(tp0)) {
118 : : // in the case of Type{_}, the types don't have to match exactly.
119 : : // this is cached as `Type{T} where T`.
120 [ # # # # ]: 0 : if (((jl_tvar_t*)tp0)->ub != (jl_value_t*)jl_any_type &&
121 : 0 : !jl_subtype(jl_tparam0(a), ((jl_tvar_t*)tp0)->ub))
122 : 0 : return 0;
123 : : }
124 [ + + ]: 1881040 : else if (!jl_types_equal(jl_tparam0(a), tp0)) {
125 : 1172290 : return 0;
126 : : }
127 : : }
128 [ # # # # : 0 : else if (!jl_is_kind(a) || !jl_is_typevar(tp0) || ((jl_tvar_t*)tp0)->ub != (jl_value_t*)jl_any_type) {
# # ]
129 : : // manually unroll jl_subtype(a, decl)
130 : : // where `a` can be a subtype and decl is Type{T}
131 : 0 : return 0;
132 : : }
133 : : }
134 [ + + ]: 22714100 : else if (decl == (jl_value_t*)jl_any_type) {
135 : : }
136 : : else {
137 [ + + ]: 18801300 : if (jl_is_type_type(a)) // decl is not Type, because it would be caught above
138 : 4415740 : a = jl_typeof(jl_tparam0(a));
139 [ + + ]: 18801300 : if (!jl_types_equal(a, decl))
140 : 3712050 : return 0;
141 : : }
142 : : }
143 [ + + ]: 5284720 : if (va) {
144 : 289031 : jl_value_t *decl = jl_unwrap_unionall(jl_tparam(sig, i));
145 [ - + ]: 289031 : if (jl_vararg_kind(decl) == JL_VARARG_INT) {
146 [ # # ]: 0 : if (n - i != jl_unbox_long(jl_tparam1(decl)))
147 : 0 : return 0;
148 : : }
149 : 289031 : jl_value_t *t = jl_unwrap_vararg(decl);
150 [ - + ]: 289031 : if (jl_is_typevar(t))
151 : 0 : t = ((jl_tvar_t*)t)->ub;
152 [ + + ]: 5113840 : for (; i < n; i++) {
153 : 4835010 : jl_value_t *ti = types[i];
154 [ + + + + ]: 4835010 : if (i == n - 1 && jl_is_vararg(ti))
155 : 1782 : ti = jl_unwrap_vararg(ti);
156 [ + + ]: 4835010 : if (!jl_subtype(ti, t))
157 : 10198 : return 0;
158 : : }
159 : 278833 : return 1;
160 : : }
161 : 4995680 : return 1;
162 : : }
163 : :
164 : 1636 : static inline int sig_match_leaf(jl_value_t *arg1, jl_value_t **args, jl_value_t **sig, size_t n)
165 : : {
166 : : // NOTE: This function is a huge performance hot spot!!
167 : : size_t i;
168 [ - + ]: 1636 : if (jl_typeof(arg1) != sig[0])
169 : 0 : return 0;
170 [ + + ]: 9643 : for (i = 1; i < n; i++) {
171 : 8053 : jl_value_t *decl = sig[i];
172 : 8053 : jl_value_t *a = args[i - 1];
173 [ + + ]: 8053 : if (jl_typeof(a) != decl) {
174 : : /*
175 : : we are only matching concrete types here, and those types are
176 : : hash-consed, so pointer comparison should work.
177 : : */
178 : 46 : return 0;
179 : : }
180 : : }
181 : 1590 : return 1;
182 : : }
183 : :
184 : 1411870000 : static inline int sig_match_simple(jl_value_t *arg1, jl_value_t **args, size_t n, jl_value_t **sig,
185 : : int va, size_t lensig)
186 : : {
187 : : // NOTE: This function is a performance hot spot!!
188 : : size_t i;
189 [ + + ]: 1411870000 : if (va)
190 : 765703000 : lensig -= 1;
191 [ + + ]: 2909290000 : for (i = 0; i < lensig; i++) {
192 : 1648180000 : jl_value_t *decl = sig[i];
193 [ + + ]: 1648180000 : jl_value_t *a = (i == 0 ? arg1 : args[i - 1]);
194 [ + + + + ]: 1648180000 : if (jl_typeof(a) == decl || decl == (jl_value_t*)jl_any_type) {
195 : : /*
196 : : we are only matching concrete types here, and those types are
197 : : hash-consed, so pointer comparison should work.
198 : : */
199 : 1465080000 : continue;
200 : : }
201 [ - + ]: 183099000 : jl_value_t *unw = jl_is_unionall(decl) ? ((jl_unionall_t*)decl)->body : decl;
202 [ + + + + ]: 215440000 : if (jl_is_type_type(unw) && jl_is_type(a)) {
203 : 39440800 : jl_value_t *tp0 = jl_tparam0(unw);
204 [ - + ]: 39440800 : if (jl_is_typevar(tp0)) {
205 : : // in the case of Type{_}, the types don't have to match exactly.
206 : : // this is cached as `Type{T} where T`.
207 [ # # # # ]: 0 : if (((jl_tvar_t*)tp0)->ub != (jl_value_t*)jl_any_type &&
208 : 0 : !jl_subtype(a, ((jl_tvar_t*)tp0)->ub))
209 : 0 : return 0;
210 : : }
211 : : else {
212 [ + + ]: 39440800 : if (a != tp0) {
213 : 8902220 : jl_datatype_t *da = (jl_datatype_t*)a;
214 : 8902220 : jl_datatype_t *dt = (jl_datatype_t*)tp0;
215 [ + + ]: 11927900 : while (jl_is_unionall(da))
216 : 3025720 : da = (jl_datatype_t*)((jl_unionall_t*)da)->body;
217 [ + + ]: 11743000 : while (jl_is_unionall(dt))
218 : 2840760 : dt = (jl_datatype_t*)((jl_unionall_t*)dt)->body;
219 [ + + + - : 8902220 : if (jl_is_datatype(da) && jl_is_datatype(dt) && da->name != dt->name)
+ + ]
220 : 3472920 : return 0;
221 [ + + ]: 5429300 : if (!jl_types_equal(a, tp0))
222 : 3626750 : return 0;
223 : : }
224 : : }
225 : : }
226 : : else {
227 : 143658000 : return 0;
228 : : }
229 : : }
230 [ + + ]: 1261110000 : if (va) {
231 : 762214000 : jl_value_t *decl = sig[i];
232 [ - + ]: 762214000 : if (jl_vararg_kind(decl) == JL_VARARG_INT) {
233 [ # # ]: 0 : if (n - i != jl_unbox_long(jl_tparam1(decl)))
234 : 0 : return 0;
235 : : }
236 : 762214000 : jl_value_t *t = jl_unwrap_vararg(decl);
237 [ + + ]: 3227630000 : for (; i < n; i++) {
238 [ + + ]: 2465430000 : jl_value_t *a = (i == 0 ? arg1 : args[i - 1]);
239 [ + + ]: 2465430000 : if (!jl_isa(a, t))
240 : 14225 : return 0;
241 : : }
242 : 762199000 : return 1;
243 : : }
244 : 498898000 : return 1;
245 : : }
246 : :
247 : :
248 : : // ----- MethodCache helper functions ----- //
249 : :
250 : : // predicate to fast-test if this type is a leaf type that can exist in the cache
251 : : // and does not need a more expensive linear scan to find all intersections
252 : : // be careful not to put non-leaf types or DataType/UnionAll/Union in the
253 : : // argument cache, since they should have a lower priority and so will go in some
254 : : // later list
255 : 33910500 : static int is_cache_leaf(jl_value_t *ty, int tparam)
256 : : {
257 [ + + ]: 33910500 : if (ty == jl_bottom_type)
258 : 9672 : return 1;
259 [ + + + + : 33900800 : return (jl_is_concrete_type(ty) && (tparam || !jl_is_kind(ty)));
+ + ]
260 : : }
261 : :
262 : 521207 : static _Atomic(jl_typemap_t*) *mtcache_hash_lookup_bp(jl_array_t *cache JL_PROPAGATES_ROOT, jl_value_t *ty) JL_NOTSAFEPOINT
263 : : {
264 [ + + ]: 521207 : if (cache == (jl_array_t*)jl_an_empty_vec_any)
265 : 4935 : return NULL;
266 : 516272 : _Atomic(jl_typemap_t*) *pml = jl_table_peek_bp(cache, ty);
267 : : JL_GC_PROMISE_ROOTED(pml); // clang-sa doesn't trust our JL_PROPAGATES_ROOT claim
268 : 516272 : return pml;
269 : : }
270 : :
271 : 183123 : static void mtcache_hash_insert(_Atomic(jl_array_t*) *cache, jl_value_t *parent, jl_value_t *key, jl_typemap_t *val)
272 : : {
273 : 183123 : int inserted = 0;
274 : 183123 : jl_array_t *a = jl_atomic_load_relaxed(cache);
275 [ + + ]: 183123 : if (a == (jl_array_t*)jl_an_empty_vec_any) {
276 : 4935 : a = jl_alloc_vec_any(16);
277 : 4935 : jl_atomic_store_release(cache, a);
278 : 4935 : jl_gc_wb(parent, a);
279 : : }
280 : 183123 : a = jl_eqtable_put(a, key, val, &inserted);
281 [ - + ]: 183123 : assert(inserted);
282 [ + + ]: 183123 : if (a != jl_atomic_load_relaxed(cache)) {
283 : 5377 : jl_atomic_store_release(cache, a);
284 : 5377 : jl_gc_wb(parent, a);
285 : : }
286 : 183123 : }
287 : :
288 : 51217500 : static jl_typemap_t *mtcache_hash_lookup(jl_array_t *cache JL_PROPAGATES_ROOT, jl_value_t *ty) JL_NOTSAFEPOINT
289 : : {
290 [ - + ]: 51217500 : if (cache == (jl_array_t*)jl_an_empty_vec_any)
291 : 0 : return (jl_typemap_t*)jl_nothing;
292 : 51217500 : jl_typemap_t *ml = (jl_typemap_t*)jl_eqtable_get(cache, ty, jl_nothing);
293 : : JL_GC_PROMISE_ROOTED(ml); // clang-sa doesn't trust our JL_PROPAGATES_ROOT claim
294 : 51217500 : return ml;
295 : : }
296 : :
297 : : // ----- Sorted Type Signature Lookup Matching ----- //
298 : :
299 : 71915 : static int jl_typemap_array_visitor(jl_array_t *a, jl_typemap_visitor_fptr fptr, void *closure)
300 : : {
301 : 71915 : size_t i, l = jl_array_len(a);
302 : 71915 : _Atomic(jl_typemap_t*) *data = (_Atomic(jl_typemap_t*)*)jl_array_data(a);
303 [ + + ]: 4544270 : for (i = 1; i < l; i += 2) {
304 : 4472360 : jl_value_t *d = jl_atomic_load_relaxed(&data[i]);
305 : : JL_GC_PROMISE_ROOTED(d);
306 [ + + + + ]: 4472360 : if (d && !jl_typemap_visitor(d, fptr, closure))
307 : 4 : return 0;
308 : : }
309 : 71911 : return 1;
310 : : }
311 : :
312 : :
313 : : // calls fptr on each jl_typemap_entry_t in cache in sort order, until fptr return false
314 : 2571240 : static int jl_typemap_node_visitor(jl_typemap_entry_t *ml, jl_typemap_visitor_fptr fptr, void *closure)
315 : : {
316 [ + + ]: 6628220 : while (ml != (void*)jl_nothing) {
317 [ + + ]: 4056990 : if (!fptr(ml, closure))
318 : 18 : return 0;
319 : 4056970 : ml = jl_atomic_load_relaxed(&ml->next);
320 : : }
321 : 2571230 : return 1;
322 : : }
323 : :
324 : 2571250 : int jl_typemap_visitor(jl_typemap_t *cache, jl_typemap_visitor_fptr fptr, void *closure)
325 : : {
326 [ + + ]: 2571250 : if (jl_typeof(cache) == (jl_value_t*)jl_typemap_level_type) {
327 : 51907 : jl_typemap_level_t *node = (jl_typemap_level_t*)cache;
328 : : jl_array_t *a;
329 : 51907 : JL_GC_PUSH1(&a);
330 : 51907 : a = jl_atomic_load_relaxed(&node->targ);
331 [ + + ]: 51907 : if (a != (jl_array_t*)jl_an_empty_vec_any)
332 [ + + ]: 4254 : if (!jl_typemap_array_visitor(a, fptr, closure))
333 : 4 : goto exit;
334 : 51906 : a = jl_atomic_load_relaxed(&node->arg1);
335 [ + + ]: 51906 : if (a != (jl_array_t*)jl_an_empty_vec_any)
336 [ + + ]: 41724 : if (!jl_typemap_array_visitor(a, fptr, closure))
337 : 3 : goto exit;
338 : 51903 : a = jl_atomic_load_relaxed(&node->tname);
339 [ + + ]: 51903 : if (a != (jl_array_t*)jl_an_empty_vec_any)
340 [ - + ]: 6308 : if (!jl_typemap_array_visitor(a, fptr, closure))
341 : 0 : goto exit;
342 : 51903 : a = jl_atomic_load_relaxed(&node->name1);
343 [ + + ]: 51903 : if (a != (jl_array_t*)jl_an_empty_vec_any)
344 [ - + ]: 19629 : if (!jl_typemap_array_visitor(a, fptr, closure))
345 : 0 : goto exit;
346 [ - + ]: 51903 : if (!jl_typemap_node_visitor(jl_atomic_load_relaxed(&node->linear), fptr, closure))
347 : 0 : goto exit;
348 [ - + ]: 51903 : if (!jl_typemap_visitor(jl_atomic_load_relaxed(&node->any), fptr, closure))
349 : 0 : goto exit;
350 : 51903 : JL_GC_POP();
351 : 51903 : return 1;
352 : : }
353 : : else {
354 : 2519340 : return jl_typemap_node_visitor((jl_typemap_entry_t*)cache, fptr, closure);
355 : : }
356 : :
357 : 4 : exit:
358 : 4 : JL_GC_POP();
359 : 4 : return 0;
360 : : }
361 : :
362 : 755412 : static unsigned jl_supertype_height(jl_datatype_t *dt)
363 : : {
364 : 755412 : unsigned height = 1;
365 [ + + ]: 1311680 : while (dt != jl_any_type) {
366 : 556269 : height++;
367 : 556269 : dt = dt->super;
368 : : }
369 : 755412 : return height;
370 : : }
371 : :
372 : : // return true if a and b might intersect in the type domain (over just their type-names)
373 : 2244020 : static int tname_intersection(jl_datatype_t *a, jl_typename_t *bname, unsigned ha)
374 : : {
375 : 2244020 : jl_datatype_t *b = (jl_datatype_t*)jl_unwrap_unionall(bname->wrapper);
376 : 2244020 : unsigned hb = 1;
377 [ + + ]: 5416880 : while (b != jl_any_type) {
378 [ + + ]: 4105290 : if (a->name == b->name)
379 : 932437 : return 1;
380 : 3172860 : hb++;
381 : 3172860 : b = b->super;
382 : : }
383 [ + + ]: 1564950 : while (ha > hb) {
384 : 253362 : a = a->super;
385 : 253362 : ha--;
386 : : }
387 : 1311590 : return a->name == bname;
388 : : }
389 : :
390 : : // tparam bit 1 is ::Type{T} (vs. T)
391 : : // tparam bit 2 is typename(T) (vs. T)
392 : 1484360 : static int jl_typemap_intersection_array_visitor(jl_array_t *a, jl_value_t *ty, int tparam,
393 : : int offs, struct typemap_intersection_env *closure)
394 : : {
395 : 1484360 : JL_GC_PUSH1(&a);
396 : 1484360 : size_t i, l = jl_array_len(a);
397 : 1484360 : _Atomic(jl_typemap_t*) *data = (_Atomic(jl_typemap_t*)*)jl_array_data(a);
398 [ + + ]: 1484360 : unsigned height = tparam & 2 ? jl_supertype_height((jl_datatype_t*)ty) : 0;
399 [ + + ]: 189436000 : for (i = 0; i < l; i += 2) {
400 : 188034000 : jl_value_t *t = jl_atomic_load_relaxed(&data[i]);
401 : : JL_GC_PROMISE_ROOTED(t);
402 [ + - + + ]: 188034000 : if (t == jl_nothing || t == NULL)
403 : 141020000 : continue;
404 [ + + ]: 47013400 : if (tparam & 2) {
405 : 7051420 : jl_typemap_t *ml = jl_atomic_load_relaxed(&data[i + 1]);
406 : : JL_GC_PROMISE_ROOTED(ml);
407 [ + + + + ]: 9295440 : if (ty == (jl_value_t*)jl_any_type || // easy case: Any always matches
408 : 2244020 : tname_intersection((jl_datatype_t*)ty, (jl_typename_t*)t, height)) {
409 [ + + ]: 5750420 : if (!jl_typemap_intersection_visitor(ml, offs + 1, closure))
410 : 224 : goto exit;
411 : : }
412 : : }
413 : : else {
414 : : // `t` is a leaftype, so intersection test becomes subtype
415 [ + + + + : 77993200 : if (ty == (jl_value_t*)jl_any_type || // easy case: Any always matches
+ + ]
416 [ + + ]: 38031300 : (tparam & 1
417 [ + + + + ]: 29603900 : ? (jl_typeof(t) == ty || jl_isa(t, ty)) // (Type{t} <: ty), where is_leaf_type(t) => isa(t, ty)
418 [ + - + + ]: 8427360 : : (t == ty || jl_subtype(t, ty)))) {
419 : 5324870 : jl_typemap_t *ml = jl_atomic_load_relaxed(&data[i + 1]);
420 : : JL_GC_PROMISE_ROOTED(ml);
421 : : // NOTE: ml might be NULL if we're racing with the thread that's inserting the item
422 [ + - + + ]: 5324870 : if (ml != NULL && !jl_typemap_intersection_visitor(ml, offs + 1, closure))
423 : 81213 : goto exit;
424 : : }
425 : : }
426 : : }
427 : 1402920 : JL_GC_POP();
428 : 1402920 : return 1;
429 : :
430 : 81437 : exit:
431 : 81437 : JL_GC_POP();
432 : 81437 : return 0;
433 : : }
434 : :
435 : : // calls fptr on each jl_typemap_entry_t in cache in sort order
436 : : // for which type ∩ ml->type != Union{}, until fptr return false
437 : 22301000 : static int jl_typemap_intersection_node_visitor(jl_typemap_entry_t *ml, struct typemap_intersection_env *closure)
438 : : {
439 : : // slow-path scan everything in ml
440 : : // mark this `register` because (for branch prediction)
441 : : // that can be absolutely critical for speed
442 : 22301000 : register jl_typemap_intersection_visitor_fptr fptr = closure->fptr;
443 [ + + ]: 73003400 : while (ml != (void*)jl_nothing) {
444 [ + + ]: 50790000 : if (closure->type == (jl_value_t*)ml->sig) {
445 : : // fast-path for the intersection of a type with itself
446 [ + - ]: 131126 : if (closure->env)
447 : 131126 : closure->env = jl_outer_unionall_vars((jl_value_t*)ml->sig);
448 : 131126 : closure->ti = closure->type;
449 : 131126 : closure->issubty = 1;
450 [ - + ]: 131126 : if (!fptr(ml, closure))
451 : 0 : return 0;
452 : : }
453 : : else {
454 : 50658900 : jl_svec_t **penv = NULL;
455 [ + - ]: 50658900 : if (closure->env) {
456 : 50658900 : closure->env = jl_emptysvec;
457 : 50658900 : penv = &closure->env;
458 : : }
459 : 50658900 : closure->ti = jl_type_intersection_env_s(closure->type, (jl_value_t*)ml->sig, penv, &closure->issubty);
460 [ + + ]: 50658900 : if (closure->ti != (jl_value_t*)jl_bottom_type) {
461 : : // In some corner cases type intersection is conservative and returns something
462 : : // for intersect(A, B) even though A is a dispatch tuple and !(A <: B).
463 : : // For dispatch purposes in such a case we know there's no match. This check
464 : : // fixes issue #30394.
465 [ + + + + ]: 10034900 : if (closure->issubty || !jl_is_dispatch_tupletype(closure->type))
466 [ + + ]: 10033600 : if (!fptr(ml, closure))
467 : 87603 : return 0;
468 : : }
469 : : }
470 : 50702400 : ml = jl_atomic_load_relaxed(&ml->next);
471 : : }
472 : 22213400 : return 1;
473 : : }
474 : :
475 : 22460500 : int jl_typemap_intersection_visitor(jl_typemap_t *map, int offs,
476 : : struct typemap_intersection_env *closure)
477 : : {
478 : 22460500 : jl_value_t *ttypes = jl_unwrap_unionall(closure->type);
479 [ - + ]: 22460500 : assert(jl_is_datatype(ttypes));
480 : : //TODO: fast-path for leaf-type tuples?
481 : : //if (ttypes->isdispatchtuple) {
482 : : // register jl_typemap_intersection_visitor_fptr fptr = closure->fptr;
483 : : // struct jl_typemap_assoc search = {(jl_value_t*)closure->type, world, closure->env, 0, ~(size_t)0};
484 : : // jl_typemap_entry_t *ml = jl_typemap_assoc_by_type(map, search, offs, /*subtype*/1);
485 : : // if (ml) {
486 : : // closure->env = search->env;
487 : : // if (!fptr(ml, closure))
488 : : // return 0;
489 : : // }
490 : : // }
491 : : // return 1;
492 : : //}
493 [ + + ]: 22460500 : if (jl_typeof(map) == (jl_value_t *)jl_typemap_level_type) {
494 : 3570690 : jl_typemap_level_t *cache = (jl_typemap_level_t*)map;
495 : : jl_value_t *ty;
496 : 3570690 : size_t l = jl_nparams(ttypes);
497 [ + + + + ]: 3570690 : if (closure->va && l <= offs + 1) {
498 : 2745 : ty = closure->va;
499 : : }
500 [ + + ]: 3567940 : else if (l > offs) {
501 : 3559060 : ty = jl_tparam(ttypes, offs);
502 : : }
503 : : else {
504 : 8879 : ty = NULL;
505 : : }
506 [ + + ]: 3570690 : if (ty == (jl_value_t*)jl_typeofbottom_type)
507 : 101 : ty = (jl_value_t*)jl_assume(jl_typeofbottom_type)->super;
508 [ + + ]: 3570690 : if (ty) {
509 [ + + ]: 3563650 : while (jl_is_typevar(ty))
510 : 1844 : ty = ((jl_tvar_t*)ty)->ub;
511 : 3561810 : jl_value_t *typetype = jl_unwrap_unionall(ty);
512 [ + + ]: 3561810 : typetype = jl_is_type_type(typetype) ? jl_tparam0(typetype) : NULL;
513 : : // approxify the tparam until we have a valid type
514 [ + + ]: 3561810 : if (jl_has_free_typevars(ty)) {
515 : 16748 : ty = jl_unwrap_unionall(ty);
516 [ + + ]: 16748 : if (jl_is_datatype(ty))
517 : 16136 : ty = ((jl_datatype_t*)ty)->name->wrapper;
518 : : else
519 : 612 : ty = (jl_value_t*)jl_any_type;
520 : : }
521 : 3561810 : jl_array_t *targ = jl_atomic_load_relaxed(&cache->targ);
522 [ + + ]: 3561810 : if (targ != (jl_array_t*)jl_an_empty_vec_any) {
523 [ + + + + ]: 712621 : if (typetype && !jl_has_free_typevars(typetype)) {
524 [ + + ]: 563968 : if (is_cache_leaf(typetype, 1)) {
525 : : // direct lookup of leaf types
526 : 352806 : jl_typemap_t *ml = mtcache_hash_lookup(targ, typetype);
527 [ + + ]: 352806 : if (ml != jl_nothing) {
528 [ + + ]: 104546 : if (!jl_typemap_intersection_visitor(ml, offs+1, closure)) return 0;
529 : : }
530 : : }
531 : : }
532 : : else {
533 : : // else an array scan is required to check subtypes
534 : : // first, fast-path: optimized pre-intersection test to see if `ty` could intersect with any Type
535 [ + + + + ]: 148653 : if (typetype || !jl_has_empty_intersection((jl_value_t*)jl_type_type, ty)) {
536 : 104316 : targ = jl_atomic_load_relaxed(&cache->targ); // may be GC'd during type-intersection
537 [ + + ]: 104316 : if (!jl_typemap_intersection_array_visitor(targ, ty, 1, offs, closure)) return 0;
538 : : }
539 : : }
540 : : }
541 : 3544830 : jl_array_t *cachearg1 = jl_atomic_load_relaxed(&cache->arg1);
542 [ + + ]: 3544830 : if (cachearg1 != (jl_array_t*)jl_an_empty_vec_any) {
543 [ + + ]: 2549250 : if (is_cache_leaf(ty, 0)) {
544 : : // direct lookup of leaf types
545 : 1924620 : jl_typemap_t *ml = mtcache_hash_lookup(cachearg1, ty);
546 [ + + ]: 1924620 : if (ml != jl_nothing) {
547 [ + + ]: 1435440 : if (!jl_typemap_intersection_visitor(ml, offs+1, closure)) return 0;
548 : : }
549 : : }
550 : : else {
551 : : // else an array scan is required to check subtypes
552 [ + + ]: 624630 : if (!jl_typemap_intersection_array_visitor(cachearg1, ty, 0, offs, closure)) return 0;
553 : : }
554 : : }
555 : 3402680 : jl_array_t *tname = jl_atomic_load_relaxed(&cache->tname);
556 [ + + ]: 3402680 : if (tname != (jl_array_t*)jl_an_empty_vec_any) {
557 [ + + ]: 1126620 : jl_value_t *name = typetype ? jl_type_extract_name(typetype) : NULL;
558 [ + + + + ]: 1738230 : if (name && !jl_is_typevar(typetype)) {
559 : : // semi-direct lookup of types
560 : : // TODO: the possibility of encountering `Type{Union{}}` in this intersection may
561 : : // be forcing us to do some extra work here whenever we see a typevar, even though
562 : : // the likelyhood of that value actually occurring is frequently likely to be
563 : : // zero (or result in an ambiguous match)
564 : 611811 : jl_datatype_t *super = (jl_datatype_t*)jl_unwrap_unionall(((jl_typename_t*)name)->wrapper);
565 [ + - ]: 611811 : if (jl_type_extract_name_precise(typetype, 1)) {
566 : : // just consider the type and its direct super types
567 : 1130840 : while (1) {
568 : 1742650 : tname = jl_atomic_load_relaxed(&cache->tname); // reload after callback
569 : 1742650 : jl_typemap_t *ml = mtcache_hash_lookup(tname, (jl_value_t*)super->name);
570 [ + + ]: 1742650 : if (ml != jl_nothing) {
571 [ + + ]: 1151250 : if (!jl_typemap_intersection_visitor(ml, offs+1, closure)) return 0;
572 : : }
573 [ + + ]: 1742450 : if (super == jl_any_type)
574 : 611607 : break;
575 : 1130840 : super = super->super;
576 : : }
577 : : }
578 : : else {
579 : : // consider all of the possible subtypes
580 [ # # ]: 0 : if (!jl_typemap_intersection_array_visitor(tname, (jl_value_t*)super, 3, offs, closure)) return 0;
581 : : }
582 : : }
583 : : else {
584 : : // else an array scan is required to check subtypes
585 : : // first, fast-path: optimized pre-intersection test to see if `ty` could intersect with any Type
586 [ + + + + ]: 514808 : if (name || !jl_has_empty_intersection((jl_value_t*)jl_type_type, ty)) {
587 : 99929 : tname = jl_atomic_load_relaxed(&cache->tname); // may be GC'd during type-intersection
588 [ + + ]: 99929 : if (!jl_typemap_intersection_array_visitor(tname, (jl_value_t*)jl_any_type, 3, offs, closure)) return 0;
589 : : }
590 : : }
591 : : }
592 : 3402250 : jl_array_t *name1 = jl_atomic_load_relaxed(&cache->name1);
593 [ + + ]: 3402250 : if (name1 != (jl_array_t*)jl_an_empty_vec_any) {
594 : 1880230 : jl_value_t *name = jl_type_extract_name(ty);
595 [ + + ]: 1880230 : if (name) {
596 : 1840530 : jl_datatype_t *super = (jl_datatype_t*)jl_unwrap_unionall(((jl_typename_t*)name)->wrapper);
597 [ + + ]: 1840530 : if (jl_type_extract_name_precise(ty, 0)) {
598 : : // direct lookup of concrete types
599 : 2631350 : while (1) {
600 : 3856100 : name1 = jl_atomic_load_relaxed(&cache->name1); // reload after callback
601 : 3856100 : jl_typemap_t *ml = mtcache_hash_lookup(name1, (jl_value_t*)super->name);
602 [ + + ]: 3856100 : if (ml != jl_nothing) {
603 [ - + ]: 1321880 : if (!jl_typemap_intersection_visitor(ml, offs+1, closure)) return 0;
604 : : }
605 [ + + ]: 3856100 : if (super == jl_any_type)
606 : 1224750 : break;
607 : 2631350 : super = super->super;
608 : : }
609 : : }
610 : : else {
611 : : // consider all of the possible subtypes too
612 [ - + ]: 615781 : if (!jl_typemap_intersection_array_visitor(name1, (jl_value_t*)super, 2, offs, closure)) return 0;
613 : : }
614 : : }
615 : : else {
616 : : // else an array scan is required to check subtypes
617 [ - + ]: 39702 : if (!jl_typemap_intersection_array_visitor(name1, (jl_value_t*)jl_any_type, 2, offs, closure)) return 0;
618 : : }
619 : : }
620 : : }
621 [ + + ]: 3411130 : if (!jl_typemap_intersection_node_visitor(jl_atomic_load_relaxed(&cache->linear), closure))
622 : 28 : return 0;
623 : 3411100 : return jl_typemap_intersection_visitor(jl_atomic_load_relaxed(&cache->any), offs+1, closure);
624 : : }
625 : : else {
626 : 18889800 : return jl_typemap_intersection_node_visitor(
627 : : (jl_typemap_entry_t*)map, closure);
628 : : }
629 : : }
630 : :
631 : :
632 : : /*
633 : : Method caches are divided into three parts: one for signatures where
634 : : the first argument is a singleton kind (Type{Foo}), one indexed by the
635 : : UID of the first argument's type in normal cases, and a fallback
636 : : table of everything else.
637 : :
638 : : Note that the "primary key" is the type of the first *argument*, since
639 : : there tends to be lots of variation there. The type of the 0th argument
640 : : (the function) is always the same for most functions.
641 : : */
642 : 10447200 : static jl_typemap_entry_t *jl_typemap_entry_assoc_by_type(
643 : : jl_typemap_entry_t *ml,
644 : : struct jl_typemap_assoc *search)
645 : : {
646 : 10447200 : jl_value_t *types = search->types;
647 : : JL_GC_PROMISE_ROOTED(types);
648 : 10447200 : jl_value_t *unw = jl_unwrap_unionall((jl_value_t*)types);
649 : 10447200 : int isua = jl_is_unionall(types);
650 : 10447200 : size_t n = jl_nparams(unw);
651 [ + - ]: 10447200 : int typesisva = n == 0 ? 0 : jl_is_vararg(jl_tparam(unw, n-1));
652 [ + + ]: 17825800 : for (; ml != (void*)jl_nothing; ml = jl_atomic_load_relaxed(&ml->next)) {
653 : 9673480 : size_t lensig = jl_nparams(jl_unwrap_unionall((jl_value_t*)ml->sig));
654 [ + + + + : 9673480 : if (lensig == n || (ml->va && lensig <= n+1)) {
+ + ]
655 : 8151760 : int resetenv = 0, ismatch = 1;
656 [ + + + - ]: 8151760 : if (ml->simplesig != (void*)jl_nothing && !isua) {
657 : 7667190 : size_t lensimplesig = jl_nparams(ml->simplesig);
658 [ + - + + ]: 7667190 : int isva = lensimplesig > 0 && jl_is_vararg(jl_tparam(ml->simplesig, lensimplesig - 1));
659 [ + + + - : 7667190 : if (lensig == n || (isva && lensimplesig <= n + 1))
+ - ]
660 : 7667190 : ismatch = sig_match_by_type_simple(jl_svec_data(((jl_datatype_t*)types)->parameters), n,
661 : : ml->simplesig, lensimplesig, isva);
662 : : else
663 : 0 : ismatch = 0;
664 : : }
665 : :
666 [ + + ]: 8151760 : if (ismatch == 0)
667 : : ; // nothing
668 [ + + + - : 4756420 : else if (ml->isleafsig && !typesisva && !isua)
+ - ]
669 : 136 : ismatch = sig_match_by_type_leaf(jl_svec_data(((jl_datatype_t*)types)->parameters),
670 : : ml->sig, lensig);
671 [ + + + + : 4756290 : else if (ml->issimplesig && !typesisva && !isua)
+ - ]
672 : 2502010 : ismatch = sig_match_by_type_simple(jl_svec_data(((jl_datatype_t*)types)->parameters), n,
673 : 2502010 : ml->sig, lensig, ml->va);
674 : : else {
675 [ + + ]: 2254280 : ismatch = jl_subtype_matching(types, (jl_value_t*)ml->sig, search->env ? &search->env : NULL);
676 [ + + + + ]: 2254280 : if (ismatch && search->env)
677 : 1293710 : resetenv = 1;
678 : : }
679 : :
680 [ + + ]: 8151760 : if (ismatch) {
681 : : size_t i, l;
682 [ + + ]: 2454970 : for (i = 0, l = jl_svec_len(ml->guardsigs); i < l; i++) {
683 : : // see corresponding code in jl_typemap_entry_assoc_exact
684 [ + + ]: 158763 : if (jl_subtype(types, jl_svecref(ml->guardsigs, i))) {
685 : 10352 : ismatch = 0;
686 : 10352 : break;
687 : : }
688 : : }
689 [ + + ]: 2306560 : if (ismatch) {
690 [ + + ]: 2296200 : if (search->world < ml->min_world) {
691 : : // ignore method table entries that are part of a later world
692 [ + - ]: 8 : if (search->max_valid >= ml->min_world)
693 : 8 : search->max_valid = ml->min_world - 1;
694 : : }
695 [ + + ]: 2296200 : else if (search->world > ml->max_world) {
696 : : // ignore method table entries that have been replaced in the current world
697 [ + - ]: 1335 : if (search->min_valid <= ml->max_world)
698 : 1335 : search->min_valid = ml->max_world + 1;
699 : : }
700 : : else {
701 : : // intersect the env valid range with method's valid range
702 [ + + ]: 2294860 : if (search->min_valid < ml->min_world)
703 : 2294420 : search->min_valid = ml->min_world;
704 [ - + ]: 2294860 : if (search->max_valid > ml->max_world)
705 : 0 : search->max_valid = ml->max_world;
706 : 2294860 : return ml;
707 : : }
708 : : }
709 : : }
710 [ + + ]: 5856900 : if (resetenv)
711 : 2452 : search->env = jl_emptysvec;
712 : : }
713 : : }
714 : 8152330 : return NULL;
715 : : }
716 : :
717 : 303558 : static jl_typemap_entry_t *jl_typemap_entry_lookup_by_type(
718 : : jl_typemap_entry_t *ml, struct jl_typemap_assoc *search)
719 : : {
720 [ + + ]: 1178270 : for (; ml != (void*)jl_nothing; ml = jl_atomic_load_relaxed(&ml->next)) {
721 [ + + + + ]: 891863 : if (search->world < ml->min_world || search->world > ml->max_world)
722 : 11006 : continue;
723 : : // unroll the first few cases here, to the extent that is possible to do fast and easily
724 : 880857 : jl_value_t *types = search->types;
725 : : JL_GC_PROMISE_ROOTED(types);
726 : 880857 : jl_value_t *a = jl_unwrap_unionall(types);
727 : 880857 : jl_value_t *b = jl_unwrap_unionall((jl_value_t*)ml->sig);
728 : 880857 : size_t na = jl_nparams(a);
729 : 880857 : size_t nb = jl_nparams(b);
730 [ + - + + ]: 880857 : int va_a = na > 0 && jl_is_vararg(jl_tparam(a, na - 1));
731 [ + - + + ]: 880857 : int va_b = nb > 0 && jl_is_vararg(jl_tparam(b, nb - 1));
732 [ + + + + ]: 880857 : if (!va_a && !va_b) {
733 [ + + ]: 834810 : if (na != nb)
734 : 435156 : continue;
735 : : }
736 [ + - + - ]: 445701 : if (na - va_a > 0 && nb - va_b > 0) {
737 [ + + ]: 445701 : if (jl_obviously_unequal(jl_tparam(a, 0), jl_tparam(b, 0)))
738 : 193530 : continue;
739 [ + + + + ]: 252171 : if (na - va_a > 1 && nb - va_b > 1) {
740 [ + + ]: 245263 : if (jl_obviously_unequal(jl_tparam(a, 1), jl_tparam(b, 1)))
741 : 79273 : continue;
742 [ + + + + ]: 165990 : if (na - va_a > 2 && nb - va_b > 2) {
743 [ + + ]: 138319 : if (jl_obviously_unequal(jl_tparam(a, 2), jl_tparam(b, 2)))
744 : 62578 : continue;
745 : : }
746 : : }
747 : : }
748 [ + + ]: 110320 : if (jl_types_equal(types, (jl_value_t*)ml->sig))
749 : 17150 : return ml;
750 : : }
751 : 286408 : return NULL;
752 : : }
753 : :
754 : :
755 : : // this is the general entry point for looking up a type in the cache
756 : : // as a subtype, or with type_equal
757 : 13166500 : jl_typemap_entry_t *jl_typemap_assoc_by_type(
758 : : jl_typemap_t *ml_or_cache,
759 : : struct jl_typemap_assoc *search,
760 : : int8_t offs, uint8_t subtype)
761 : : {
762 [ + + ]: 13166500 : if (jl_typeof(ml_or_cache) == (jl_value_t *)jl_typemap_level_type) {
763 : 4890440 : jl_typemap_level_t *cache = (jl_typemap_level_t*)ml_or_cache;
764 : : // called object is the primary key for constructors, otherwise first argument
765 : : jl_value_t *ty;
766 : 4890440 : jl_value_t *ttypes = jl_unwrap_unionall((jl_value_t*)search->types);
767 : : JL_GC_PROMISE_ROOTED(ttypes);
768 [ - + ]: 4890440 : assert(jl_is_datatype(ttypes));
769 : 4890440 : size_t l = jl_nparams(ttypes);
770 : 4890440 : int isva = 0;
771 : : // compute the type at offset `offs` into `types`, which may be a Vararg
772 [ + + ]: 4890440 : if (l <= offs + 1) {
773 : 1196030 : ty = jl_tparam(ttypes, l - 1);
774 [ + + ]: 1196030 : if (jl_is_vararg(ty)) {
775 : 2122 : ty = jl_unwrap_vararg(ty);
776 : 2122 : isva = 1;
777 : : }
778 [ + + ]: 1193910 : else if (l <= offs) {
779 : 131173 : ty = NULL;
780 : : }
781 : : }
782 [ + + ]: 3694410 : else if (l > offs) {
783 : 3694380 : ty = jl_tparam(ttypes, offs);
784 : : }
785 : : else {
786 : 36 : ty = NULL;
787 : : }
788 [ + + ]: 4890440 : if (ty == (jl_value_t*)jl_typeofbottom_type)
789 : 2388 : ty = (jl_value_t*)jl_assume(jl_typeofbottom_type)->super;
790 : : // If there is a type at offs, look in the optimized leaf type caches
791 [ + + + + ]: 4890440 : if (ty && !subtype) {
792 [ + + ]: 64203 : if (jl_is_any(ty))
793 : 9784 : return jl_typemap_assoc_by_type(jl_atomic_load_relaxed(&cache->any), search, offs + 1, subtype);
794 [ + + ]: 54419 : if (isva) // in lookup mode, want to match Vararg exactly, not as a subtype
795 : 181 : ty = NULL;
796 : : }
797 [ + + ]: 4880660 : if (ty) {
798 : : // now look at the optimized leaftype caches
799 [ + + ]: 4749270 : if (jl_is_type_type(ty)) {
800 : 1449080 : jl_value_t *a0 = jl_tparam0(ty);
801 [ + + ]: 1449080 : if (is_cache_leaf(a0, 1)) {
802 : 601438 : jl_array_t *targ = jl_atomic_load_relaxed(&cache->targ);
803 [ + + ]: 601438 : if (targ != (jl_array_t*)jl_an_empty_vec_any) {
804 : 537591 : jl_typemap_t *ml = mtcache_hash_lookup(targ, a0);
805 [ + + ]: 537591 : if (ml != jl_nothing) {
806 : 212373 : jl_typemap_entry_t *li = jl_typemap_assoc_by_type(ml, search, offs + 1, subtype);
807 [ + + ]: 212373 : if (li) return li;
808 : : }
809 : : }
810 [ + + ]: 432237 : if (!subtype) return NULL;
811 : : }
812 : : }
813 [ + + ]: 4576310 : if (is_cache_leaf(ty, 0)) {
814 : 3186340 : jl_array_t *cachearg1 = jl_atomic_load_relaxed(&cache->arg1);
815 [ + + ]: 3186340 : if (cachearg1 != (jl_array_t*)jl_an_empty_vec_any) {
816 : 2954190 : jl_typemap_t *ml = mtcache_hash_lookup(cachearg1, ty);
817 [ + + ]: 2954190 : if (ml != jl_nothing) {
818 : 1477950 : jl_typemap_entry_t *li = jl_typemap_assoc_by_type(ml, search, offs + 1, subtype);
819 [ + + ]: 1477950 : if (li) return li;
820 : : }
821 : : }
822 [ + + ]: 2374910 : if (!subtype) return NULL;
823 : : }
824 : : }
825 [ + + + + ]: 3879550 : if (ty || subtype) {
826 : : // now look at the optimized TypeName caches
827 : 3876550 : jl_array_t *tname = jl_atomic_load_relaxed(&cache->tname);
828 [ + + ]: 3876550 : if (tname != (jl_array_t*)jl_an_empty_vec_any) {
829 [ + + + + ]: 2454290 : jl_value_t *a0 = ty && jl_is_type_type(ty) ? jl_type_extract_name(jl_tparam0(ty)) : NULL;
830 [ + + ]: 2454290 : if (a0) { // TODO: if we start analyzing Union types in jl_type_extract_name, then a0 might be over-approximated here, leading us to miss possible subtypes
831 : 1231460 : jl_datatype_t *super = (jl_datatype_t*)jl_unwrap_unionall(((jl_typename_t*)a0)->wrapper);
832 : 1454930 : while (1) {
833 : 2686390 : tname = jl_atomic_load_relaxed(&cache->tname); // reload after tree descent (which may hit safepoints)
834 : 2686390 : jl_typemap_t *ml = mtcache_hash_lookup(tname, (jl_value_t*)super->name);
835 [ + + ]: 2686390 : if (ml != (void*)jl_nothing) {
836 : 1737700 : jl_typemap_entry_t *li = jl_typemap_assoc_by_type(ml, search, offs + 1, subtype);
837 [ + + ]: 2558790 : if (li) return li;
838 : : }
839 [ + + + + ]: 2102580 : if (super == jl_any_type || !subtype)
840 : : break;
841 : 1454930 : super = super->super;
842 : : }
843 : : }
844 : : else {
845 [ + + + + ]: 1222830 : if (!ty || !jl_has_empty_intersection((jl_value_t*)jl_type_type, ty)) {
846 : : // couldn't figure out unique `a0` initial point, so scan all for matches
847 : 31652 : size_t i, l = jl_array_len(tname);
848 : 31652 : _Atomic(jl_typemap_t*) *data = (_Atomic(jl_typemap_t*)*)jl_array_ptr_data(tname);
849 : 31652 : JL_GC_PUSH1(&tname);
850 [ + + ]: 906913 : for (i = 1; i < l; i += 2) {
851 : 892068 : jl_typemap_t *ml = jl_atomic_load_relaxed(&data[i]);
852 [ + + - + ]: 892068 : if (ml == NULL || ml == jl_nothing)
853 : 524346 : continue;
854 : 367722 : jl_typemap_entry_t *li = jl_typemap_assoc_by_type(ml, search, offs + 1, subtype);
855 [ + + ]: 367722 : if (li) {
856 : 16807 : JL_GC_POP();
857 : 16807 : return li;
858 : : }
859 : : }
860 : 14845 : JL_GC_POP();
861 : : }
862 : : }
863 : : }
864 : 3275930 : jl_array_t *name1 = jl_atomic_load_relaxed(&cache->name1);
865 [ + + ]: 3275930 : if (name1 != (jl_array_t*)jl_an_empty_vec_any) {
866 [ + + ]: 1210080 : if (ty) {
867 : 1208470 : jl_value_t *a0 = jl_type_extract_name(ty);
868 [ + + ]: 1208470 : if (a0) { // TODO: if we start analyzing Union types in jl_type_extract_name, then a0 might be over-approximated here, leading us to miss possible subtypes
869 : 1206460 : jl_datatype_t *super = (jl_datatype_t*)jl_unwrap_unionall(((jl_typename_t*)a0)->wrapper);
870 : 889493 : while (1) {
871 : 2095960 : name1 = jl_atomic_load_relaxed(&cache->name1); // reload after tree descent (which may hit safepoints)
872 : 2095960 : jl_typemap_t *ml = mtcache_hash_lookup(name1, (jl_value_t*)super->name);
873 [ + + ]: 2095960 : if (ml != (void*)jl_nothing) {
874 : : jl_typemap_entry_t *li =
875 : 1053270 : jl_typemap_assoc_by_type(ml, search, offs + 1, subtype);
876 [ + + ]: 1053270 : if (li) return li;
877 : : }
878 [ + + + + ]: 1291670 : if (super == jl_any_type || !subtype)
879 : : break;
880 : 889493 : super = super->super;
881 : : }
882 : : }
883 : : }
884 : : else {
885 : : // doing subtype, but couldn't figure out unique `ty`, so scan all for supertypes
886 : 1608 : size_t i, l = jl_array_len(name1);
887 : 1608 : _Atomic(jl_typemap_t*) *data = (_Atomic(jl_typemap_t*)*)jl_array_ptr_data(name1);
888 : 1608 : JL_GC_PUSH1(&name1);
889 [ + + ]: 14480 : for (i = 1; i < l; i += 2) {
890 : 12872 : jl_typemap_t *ml = jl_atomic_load_relaxed(&data[i]);
891 [ + + - + ]: 12872 : if (ml == NULL || ml == jl_nothing)
892 : 11252 : continue;
893 : 1620 : jl_typemap_entry_t *li = jl_typemap_assoc_by_type(ml, search, offs + 1, subtype);
894 [ - + ]: 1620 : if (li) {
895 : 0 : JL_GC_POP();
896 : 0 : return li;
897 : : }
898 : : }
899 : 1608 : JL_GC_POP();
900 : : }
901 : : }
902 : : }
903 : : // Always check the list (since offs doesn't always start at 0)
904 [ + + ]: 2474640 : if (subtype) {
905 : 2451740 : jl_typemap_entry_t *li = jl_typemap_entry_assoc_by_type(jl_atomic_load_relaxed(&cache->linear), search);
906 [ + + ]: 2451740 : if (li) return li;
907 : 2359500 : return jl_typemap_assoc_by_type(jl_atomic_load_relaxed(&cache->any), search, offs + 1, subtype);
908 : : }
909 : : else {
910 : 22907 : return jl_typemap_entry_lookup_by_type(jl_atomic_load_relaxed(&cache->linear), search);
911 : : }
912 : : }
913 : : else {
914 : 8276100 : jl_typemap_entry_t *leaf = (jl_typemap_entry_t*)ml_or_cache;
915 : : return subtype ?
916 [ + + ]: 8556750 : jl_typemap_entry_assoc_by_type(leaf, search) :
917 : 280651 : jl_typemap_entry_lookup_by_type(leaf, search);
918 : : }
919 : : }
920 : :
921 : 1187930000 : jl_typemap_entry_t *jl_typemap_entry_assoc_exact(jl_typemap_entry_t *ml, jl_value_t *arg1, jl_value_t **args, size_t n, size_t world)
922 : : {
923 : : // some manually-unrolled common special cases
924 [ + + + + : 1187930000 : while (ml->simplesig == (void*)jl_nothing && ml->guardsigs == jl_emptysvec && ml->isleafsig) {
+ + ]
925 : : // use a tight loop for as long as possible
926 [ + - + - ]: 3109 : if (world >= ml->min_world && world <= ml->max_world) {
927 [ + + + - ]: 3109 : if (n == jl_nparams(ml->sig) && jl_typeof(arg1) == jl_tparam(ml->sig, 0)) {
928 [ - + ]: 3103 : if (n == 1)
929 : 0 : return ml;
930 [ + + ]: 3103 : if (n == 2) {
931 [ + + ]: 113 : if (jl_typeof(args[0]) == jl_tparam(ml->sig, 1))
932 : 53 : return ml;
933 : : }
934 [ + + ]: 2990 : else if (n == 3) {
935 [ + + + - ]: 2526 : if (jl_typeof(args[0]) == jl_tparam(ml->sig, 1) &&
936 : 1165 : jl_typeof(args[1]) == jl_tparam(ml->sig, 2))
937 : 1172 : return ml;
938 : : }
939 : : else {
940 [ + + ]: 1636 : if (sig_match_leaf(arg1, args, jl_svec_data(ml->sig->parameters), n))
941 : 1590 : return ml;
942 : : }
943 : : }
944 : : }
945 : 301 : ml = jl_atomic_load_relaxed(&ml->next);
946 [ + + ]: 301 : if (ml == (void*)jl_nothing)
947 : 60 : return NULL;
948 : : }
949 : :
950 [ + + ]: 1558500000 : for (; ml != (void*)jl_nothing; ml = jl_atomic_load_relaxed(&ml->next)) {
951 [ + + + + ]: 1543360000 : if (world < ml->min_world || world > ml->max_world)
952 : 18765 : continue; // ignore replaced methods
953 : 1543340000 : size_t lensig = jl_nparams(ml->sig);
954 [ + + + + : 1543340000 : if (lensig == n || (ml->va && lensig <= n+1)) {
+ + ]
955 [ + + ]: 1330860000 : if (ml->simplesig != (void*)jl_nothing) {
956 : 430030000 : size_t lensimplesig = jl_nparams(ml->simplesig);
957 [ + # + + ]: 430030000 : int isva = lensimplesig > 0 && jl_is_vararg(jl_tparam(ml->simplesig, lensimplesig - 1));
958 [ + + + - : 430030000 : if (lensig == n || (isva && lensimplesig <= n + 1)) {
+ - ]
959 [ + + ]: 430030000 : if (!sig_match_simple(arg1, args, n, jl_svec_data(ml->simplesig->parameters), isva, lensimplesig))
960 : 68929900 : continue;
961 : : }
962 : : else {
963 : 0 : continue;
964 : : }
965 : : }
966 : :
967 [ - + ]: 1261930000 : if (ml->isleafsig) {
968 [ # # ]: 0 : if (!sig_match_leaf(arg1, args, jl_svec_data(ml->sig->parameters), n))
969 : 0 : continue;
970 : : }
971 [ + + ]: 1261930000 : else if (ml->issimplesig) {
972 [ + + ]: 981840000 : if (!sig_match_simple(arg1, args, n, jl_svec_data(ml->sig->parameters), ml->va, lensig))
973 : 81842400 : continue;
974 : : }
975 : : else {
976 [ + + ]: 280086000 : if (!jl_tuple1_isa(arg1, args, n, ml->sig))
977 : 6998200 : continue;
978 : : }
979 : :
980 : : size_t i, l;
981 [ + + ]: 1173090000 : if (ml->guardsigs != jl_emptysvec) {
982 [ + + ]: 38869800 : for (i = 0, l = jl_svec_len(ml->guardsigs); i < l; i++) {
983 : : // checking guard entries require a more
984 : : // expensive subtype check, since guard entries added for @nospecialize might be
985 : : // abstract. this fixed issue #12967.
986 [ + + ]: 33010600 : if (jl_tuple1_isa(arg1, args, n, (jl_tupletype_t*)jl_svecref(ml->guardsigs, i))) {
987 : 303546 : goto nomatch;
988 : : }
989 : : }
990 : : }
991 : 1172780000 : return ml;
992 : 303546 : nomatch:
993 : 303546 : continue;
994 : : }
995 : : }
996 : 15146700 : return NULL;
997 : : }
998 : :
999 : 31072900 : jl_typemap_entry_t *jl_typemap_level_assoc_exact(jl_typemap_level_t *cache, jl_value_t *arg1, jl_value_t **args, size_t n, int8_t offs, size_t world)
1000 : : {
1001 [ + + ]: 31072900 : if (n > offs) {
1002 [ + + ]: 30768200 : jl_value_t *a1 = (offs == 0 ? arg1 : args[offs - 1]);
1003 : 30768200 : jl_value_t *ty = jl_typeof(a1);
1004 [ - + ]: 30768200 : assert(jl_is_datatype(ty));
1005 : 30768200 : jl_array_t *targ = jl_atomic_load_relaxed(&cache->targ);
1006 [ + + + + : 30768200 : if (ty == (jl_value_t*)jl_datatype_type && targ != (jl_array_t*)jl_an_empty_vec_any && is_cache_leaf(a1, 1)) {
+ + ]
1007 : 5818520 : jl_typemap_t *ml_or_cache = mtcache_hash_lookup(targ, a1);
1008 : 5818520 : jl_typemap_entry_t *ml = jl_typemap_assoc_exact(ml_or_cache, arg1, args, n, offs+1, world);
1009 [ + + ]: 30510800 : if (ml) return ml;
1010 : : }
1011 : 25373500 : jl_array_t *cachearg1 = jl_atomic_load_relaxed(&cache->arg1);
1012 [ + + + + ]: 25373500 : if (cachearg1 != (jl_array_t*)jl_an_empty_vec_any && is_cache_leaf(ty, 0)) {
1013 : 15871800 : jl_typemap_t *ml_or_cache = mtcache_hash_lookup(cachearg1, ty);
1014 : 15871800 : jl_typemap_entry_t *ml = jl_typemap_assoc_exact(ml_or_cache, arg1, args, n, offs+1, world);
1015 [ + + ]: 15871800 : if (ml) return ml;
1016 : : }
1017 : 11549700 : jl_array_t *tname = jl_atomic_load_relaxed(&cache->tname);
1018 [ + + + + ]: 11549700 : if (jl_is_kind(ty) && tname != (jl_array_t*)jl_an_empty_vec_any) {
1019 : 9269600 : jl_value_t *name = jl_type_extract_name(a1);
1020 [ + + ]: 9269600 : if (name) {
1021 [ + + ]: 8664790 : if (ty != (jl_value_t*)jl_datatype_type)
1022 : 5674200 : a1 = jl_unwrap_unionall(((jl_typename_t*)name)->wrapper);
1023 : 2477130 : while (1) {
1024 : 11141900 : tname = jl_atomic_load_relaxed(&cache->tname); // reload after tree descent (which may hit safepoints)
1025 : 11141900 : jl_typemap_t *ml_or_cache = mtcache_hash_lookup(
1026 : 11141900 : tname, (jl_value_t*)((jl_datatype_t*)a1)->name);
1027 : 11141900 : jl_typemap_entry_t *ml = jl_typemap_assoc_exact(ml_or_cache, arg1, args, n, offs+1, world);
1028 [ + + ]: 11141900 : if (ml) return ml;
1029 [ + + ]: 2497650 : if (a1 == (jl_value_t*)jl_any_type)
1030 : 20514 : break;
1031 : 2477130 : a1 = (jl_value_t*)((jl_datatype_t*)a1)->super;
1032 : : }
1033 : : }
1034 : : else {
1035 : : // couldn't figure out unique `name` initial point, so must scan all for matches
1036 : 604816 : size_t i, l = jl_array_len(tname);
1037 : 604816 : _Atomic(jl_typemap_t*) *data = (_Atomic(jl_typemap_t*)*)jl_array_ptr_data(tname);
1038 : 604816 : JL_GC_PUSH1(&tname);
1039 [ + + ]: 4321860 : for (i = 1; i < l; i += 2) {
1040 : 4319630 : jl_typemap_t *ml_or_cache = jl_atomic_load_relaxed(&data[i]);
1041 [ + + - + ]: 4319630 : if (ml_or_cache == NULL || ml_or_cache == jl_nothing)
1042 : 2976440 : continue;
1043 : 1343190 : jl_typemap_entry_t *ml = jl_typemap_assoc_exact(ml_or_cache, arg1, args, n, offs + 1, world);
1044 [ + + ]: 1343190 : if (ml) {
1045 : 602594 : JL_GC_POP();
1046 : 602594 : return ml;
1047 : : }
1048 : : }
1049 : 2222 : JL_GC_POP();
1050 : : }
1051 : : }
1052 : 2302840 : jl_array_t *name1 = jl_atomic_load_relaxed(&cache->name1);
1053 [ + + ]: 2302840 : if (name1 != (jl_array_t*)jl_an_empty_vec_any) {
1054 : 575476 : while (1) {
1055 : 2234930 : name1 = jl_atomic_load_relaxed(&cache->name1); // reload after tree descent (which may hit safepoints)
1056 : 2234930 : jl_typemap_t *ml_or_cache = mtcache_hash_lookup(
1057 : 2234930 : name1, (jl_value_t*)((jl_datatype_t*)ty)->name);
1058 : 2234940 : jl_typemap_entry_t *ml = jl_typemap_assoc_exact(ml_or_cache, arg1, args, n, offs+1, world);
1059 [ + + ]: 2234940 : if (ml) return ml;
1060 [ + + ]: 613275 : if (ty == (jl_value_t*)jl_any_type)
1061 : 37799 : break;
1062 : 575476 : ty = (jl_value_t*)((jl_datatype_t*)ty)->super;
1063 : : }
1064 : : }
1065 : : }
1066 : 985927 : jl_typemap_entry_t *linear = jl_atomic_load_relaxed(&cache->linear);
1067 [ + + ]: 985927 : if (linear != (jl_typemap_entry_t*)jl_nothing) {
1068 : 229454 : jl_typemap_entry_t *ml = jl_typemap_entry_assoc_exact(linear, arg1, args, n, world);
1069 [ + + ]: 229454 : if (ml) return ml;
1070 : : }
1071 : 765452 : jl_typemap_t *cacheany = jl_atomic_load_relaxed(&cache->any);
1072 [ + + ]: 765452 : if (cacheany != (jl_typemap_t*)jl_nothing)
1073 : 588435 : return jl_typemap_assoc_exact(cacheany, arg1, args, n, offs+1, world);
1074 : 177017 : return NULL;
1075 : : }
1076 : :
1077 : :
1078 : : // ----- Method List Insertion Management ----- //
1079 : :
1080 : 190254 : static unsigned jl_typemap_list_count_locked(jl_typemap_entry_t *ml) JL_NOTSAFEPOINT
1081 : : {
1082 : 190254 : unsigned count = 0;
1083 [ + + ]: 826284 : while (ml != (void*)jl_nothing) {
1084 : 636030 : count++;
1085 : 636030 : ml = jl_atomic_load_relaxed(&ml->next);
1086 : : }
1087 : 190254 : return count;
1088 : : }
1089 : :
1090 : : static void jl_typemap_level_insert_(jl_typemap_t *map, jl_typemap_level_t *cache, jl_typemap_entry_t *newrec, int8_t offs);
1091 : :
1092 : 4544 : static jl_typemap_level_t *jl_new_typemap_level(void)
1093 : : {
1094 : 4544 : jl_task_t *ct = jl_current_task;
1095 : : jl_typemap_level_t *cache =
1096 : 4544 : (jl_typemap_level_t*)jl_gc_alloc(ct->ptls, sizeof(jl_typemap_level_t),
1097 : : jl_typemap_level_type);
1098 : 4544 : jl_atomic_store_relaxed(&cache->arg1, (jl_array_t*)jl_an_empty_vec_any);
1099 : 4544 : jl_atomic_store_relaxed(&cache->targ, (jl_array_t*)jl_an_empty_vec_any);
1100 : 4544 : jl_atomic_store_relaxed(&cache->name1, (jl_array_t*)jl_an_empty_vec_any);
1101 : 4544 : jl_atomic_store_relaxed(&cache->tname, (jl_array_t*)jl_an_empty_vec_any);
1102 : 4544 : jl_atomic_store_relaxed(&cache->linear, (jl_typemap_entry_t*)jl_nothing);
1103 : 4544 : jl_atomic_store_relaxed(&cache->any, jl_nothing);
1104 : 4544 : return cache;
1105 : : }
1106 : :
1107 : 4544 : static jl_typemap_level_t *jl_method_convert_list_to_cache(
1108 : : jl_typemap_t *map, jl_typemap_entry_t *ml, int8_t offs)
1109 : : {
1110 : 4544 : jl_typemap_level_t *cache = jl_new_typemap_level();
1111 : 4544 : jl_typemap_entry_t *next = NULL;
1112 : 4544 : JL_GC_PUSH3(&cache, &next, &ml);
1113 [ + + ]: 63616 : while (ml != (void*)jl_nothing) {
1114 : 59072 : next = jl_atomic_load_relaxed(&ml->next);
1115 : 59072 : jl_atomic_store_relaxed(&ml->next, (jl_typemap_entry_t*)jl_nothing);
1116 : : // n.b. this is being done concurrently with lookups!
1117 : : // TODO: is it safe to be doing this concurrently with lookups?
1118 : 59072 : jl_typemap_level_insert_(map, cache, ml, offs);
1119 : 59072 : ml = next;
1120 : : }
1121 : 4544 : JL_GC_POP();
1122 : 4544 : return cache;
1123 : : }
1124 : :
1125 : 193189 : static void jl_typemap_list_insert_(
1126 : : jl_typemap_t *map, _Atomic(jl_typemap_entry_t*) *pml, jl_value_t *parent,
1127 : : jl_typemap_entry_t *newrec)
1128 : : {
1129 : 193189 : jl_typemap_entry_t *l = jl_atomic_load_relaxed(pml);
1130 [ + + ]: 215184 : while ((jl_value_t*)l != jl_nothing) {
1131 [ + + + + ]: 164444 : if (newrec->isleafsig || !l->isleafsig)
1132 [ + + + + ]: 155143 : if (newrec->issimplesig || !l->issimplesig)
1133 : : break;
1134 : 21995 : pml = &l->next;
1135 : 21995 : parent = (jl_value_t*)l;
1136 : 21995 : l = jl_atomic_load_relaxed(&l->next);
1137 : : }
1138 : 193189 : jl_atomic_store_relaxed(&newrec->next, l);
1139 : 193189 : jl_gc_wb(newrec, l);
1140 : 193189 : jl_atomic_store_release(pml, newrec);
1141 : 193189 : jl_gc_wb(parent, newrec);
1142 : 193189 : }
1143 : :
1144 : 663606 : static void jl_typemap_insert_generic(
1145 : : jl_typemap_t *map, _Atomic(jl_typemap_t*) *pml, jl_value_t *parent,
1146 : : jl_typemap_entry_t *newrec, int8_t offs)
1147 : : {
1148 : 663606 : jl_typemap_t *ml = jl_atomic_load_relaxed(pml);
1149 [ + + ]: 663606 : if (jl_typeof(ml) == (jl_value_t*)jl_typemap_level_type) {
1150 : 473352 : jl_typemap_level_insert_(map, (jl_typemap_level_t*)ml, newrec, offs);
1151 : 473352 : return;
1152 : : }
1153 : :
1154 : 190254 : unsigned count = jl_typemap_list_count_locked((jl_typemap_entry_t*)ml);
1155 [ + + ]: 190254 : if (count > MAX_METHLIST_COUNT) {
1156 : 4544 : ml = (jl_typemap_t*)jl_method_convert_list_to_cache(
1157 : : map, (jl_typemap_entry_t*)ml, offs);
1158 : 4544 : jl_atomic_store_release(pml, ml);
1159 : 4544 : jl_gc_wb(parent, ml);
1160 : 4544 : jl_typemap_level_insert_(map, (jl_typemap_level_t*)ml, newrec, offs);
1161 : 4544 : return;
1162 : : }
1163 : :
1164 : 185710 : jl_typemap_list_insert_(map, (_Atomic(jl_typemap_entry_t*)*)pml,
1165 : : parent, newrec);
1166 : : }
1167 : :
1168 : 521207 : static void jl_typemap_array_insert_(
1169 : : jl_typemap_t *map, _Atomic(jl_array_t*) *pcache, jl_value_t *key, jl_typemap_entry_t *newrec,
1170 : : jl_value_t *parent, int8_t offs)
1171 : : {
1172 : 521207 : jl_array_t *cache = jl_atomic_load_relaxed(pcache);
1173 : 521207 : _Atomic(jl_typemap_t*) *pml = mtcache_hash_lookup_bp(cache, key);
1174 [ + + ]: 521207 : if (pml != NULL)
1175 : 338084 : jl_typemap_insert_generic(map, pml, (jl_value_t*)cache, newrec, offs+1);
1176 : : else
1177 : 183123 : mtcache_hash_insert(pcache, parent, key, (jl_typemap_t*)newrec);
1178 : 521207 : }
1179 : :
1180 : 536968 : static void jl_typemap_level_insert_(
1181 : : jl_typemap_t *map, jl_typemap_level_t *cache, jl_typemap_entry_t *newrec, int8_t offs)
1182 : : {
1183 : 536968 : jl_value_t *ttypes = jl_unwrap_unionall((jl_value_t*)newrec->sig);
1184 : 536968 : size_t l = jl_nparams(ttypes);
1185 : : // compute the type at offset `offs` into `sig`, which may be a Vararg
1186 : : jl_value_t *t1;
1187 : 536968 : int isva = 0;
1188 [ + + ]: 536968 : if (l <= offs + 1) {
1189 : 108232 : t1 = jl_tparam(ttypes, l - 1);
1190 [ + + ]: 108232 : if (jl_is_vararg(t1)) {
1191 : 5714 : isva = 1;
1192 : 5714 : t1 = jl_unwrap_vararg(t1);
1193 : : }
1194 [ + + ]: 102518 : else if (l <= offs) {
1195 : 5214 : t1 = NULL;
1196 : : }
1197 : : }
1198 [ + + ]: 428736 : else if (l > offs) {
1199 : 428715 : t1 = jl_tparam(ttypes, offs);
1200 : : }
1201 : : else {
1202 : 21 : t1 = NULL;
1203 : : }
1204 [ + + ]: 536968 : if (t1 == (jl_value_t*)jl_typeofbottom_type)
1205 : 219 : t1 = (jl_value_t*)jl_assume(jl_typeofbottom_type)->super;
1206 : : // If the type at `offs` is Any, put it in the Any list
1207 [ + + + + ]: 536968 : if (t1 && jl_is_any(t1)) {
1208 : 8282 : jl_typemap_insert_generic(map, &cache->any, (jl_value_t*)cache, newrec, offs+1);
1209 : 8282 : return;
1210 : : }
1211 : : // Don't put Varargs in the optimized caches (too hard to handle in lookup and bp)
1212 [ + + + + ]: 528686 : if (t1 && !isva) {
1213 : : // try to put in leaf type caches
1214 [ + + ]: 523232 : if (jl_is_type_type(t1)) {
1215 : : // if the argument is Type{...}, this method has specializations for singleton kinds
1216 : : // and we use the table indexed for that purpose.
1217 : 162158 : jl_value_t *a0 = jl_tparam0(t1);
1218 [ + + ]: 162158 : if (is_cache_leaf(a0, 1)) {
1219 : 53683 : jl_typemap_array_insert_(map, &cache->targ, a0, newrec, (jl_value_t*)cache, offs);
1220 : 53683 : return;
1221 : : }
1222 : : }
1223 [ + + ]: 469549 : if (is_cache_leaf(t1, 0)) {
1224 : 280867 : jl_typemap_array_insert_(map, &cache->arg1, t1, newrec, (jl_value_t*)cache, offs);
1225 : 280867 : return;
1226 : : }
1227 : :
1228 : : // try to put in TypeName caches
1229 : : jl_value_t *a0;
1230 : 188682 : t1 = jl_unwrap_unionall(t1);
1231 [ + + ]: 188682 : if (jl_is_type_type(t1)) {
1232 : 112386 : a0 = jl_type_extract_name(jl_tparam0(t1));
1233 [ + + ]: 112386 : jl_datatype_t *super = a0 ? (jl_datatype_t*)jl_unwrap_unionall(((jl_typename_t*)a0)->wrapper) : jl_any_type;
1234 : 112386 : jl_typemap_array_insert_(map, &cache->tname, (jl_value_t*)super->name, newrec, (jl_value_t*)cache, offs);
1235 : 112386 : return;
1236 : : }
1237 : 76296 : a0 = jl_type_extract_name(t1);
1238 [ + + + - ]: 76296 : if (a0 && a0 != (jl_value_t*)jl_any_type->name) {
1239 : 74271 : jl_typemap_array_insert_(map, &cache->name1, a0, newrec, (jl_value_t*)cache, offs);
1240 : 74271 : return;
1241 : : }
1242 : : }
1243 : 7479 : jl_typemap_list_insert_(map, &cache->linear, (jl_value_t*)cache, newrec);
1244 : : }
1245 : :
1246 : 1680760 : jl_typemap_entry_t *jl_typemap_alloc(
1247 : : jl_tupletype_t *type, jl_tupletype_t *simpletype, jl_svec_t *guardsigs,
1248 : : jl_value_t *newvalue, size_t min_world, size_t max_world)
1249 : : {
1250 : 1680760 : jl_task_t *ct = jl_current_task;
1251 [ + - + - ]: 1680760 : assert(min_world > 0 && max_world > 0);
1252 [ + + ]: 1680760 : if (!simpletype)
1253 : 1238270 : simpletype = (jl_tupletype_t*)jl_nothing;
1254 : 1680760 : jl_value_t *ttype = jl_unwrap_unionall((jl_value_t*)type);
1255 [ - + ]: 1680760 : assert(jl_is_tuple_type(ttype));
1256 : : // compute the complexity of this type signature
1257 : 1680760 : int isva = jl_is_va_tuple((jl_datatype_t*)ttype);
1258 : 1680760 : int issimplesig = !jl_is_unionall(type); // a TypeVar environment needs a complex matching test
1259 [ + + + + ]: 1680760 : int isleafsig = issimplesig && !isva; // entirely leaf types don't need to be sorted
1260 : : size_t i, l;
1261 [ + + + + ]: 6739290 : for (i = 0, l = jl_nparams(ttype); i < l && issimplesig; i++) {
1262 : 5058520 : jl_value_t *decl = jl_tparam(ttype, i);
1263 [ + + ]: 5058520 : if (jl_is_kind(decl))
1264 : 2382 : isleafsig = 0; // Type{} may have a higher priority than a kind
1265 [ + + ]: 5056140 : else if (jl_is_type_type(decl))
1266 : 402236 : isleafsig = 0; // Type{} may need special processing to compute the match
1267 [ + + ]: 4653910 : else if (jl_is_vararg(decl))
1268 : 20950 : isleafsig = 0; // makes iteration easier when the endpoints are the same
1269 [ + + ]: 4632960 : else if (decl == (jl_value_t*)jl_any_type)
1270 : 31866 : isleafsig = 0; // Any needs to go in the general cache
1271 [ + + ]: 4601090 : else if (!jl_is_concrete_type(decl)) // anything else needs to go through the general subtyping test
1272 : 133044 : isleafsig = issimplesig = 0;
1273 : : }
1274 : :
1275 : : jl_typemap_entry_t *newrec =
1276 : 1680760 : (jl_typemap_entry_t*)jl_gc_alloc(ct->ptls, sizeof(jl_typemap_entry_t),
1277 : : jl_typemap_entry_type);
1278 : 1680760 : newrec->sig = type;
1279 : 1680760 : newrec->simplesig = simpletype;
1280 : 1680760 : newrec->func.value = newvalue;
1281 : 1680760 : newrec->guardsigs = guardsigs;
1282 : 1680760 : jl_atomic_store_relaxed(&newrec->next, (jl_typemap_entry_t*)jl_nothing);
1283 : 1680760 : newrec->min_world = min_world;
1284 : 1680760 : newrec->max_world = max_world;
1285 : 1680760 : newrec->va = isva;
1286 : 1680760 : newrec->issimplesig = issimplesig;
1287 : 1680760 : newrec->isleafsig = isleafsig;
1288 : 1680760 : return newrec;
1289 : : }
1290 : :
1291 : 317240 : void jl_typemap_insert(_Atomic(jl_typemap_t *) *pcache, jl_value_t *parent,
1292 : : jl_typemap_entry_t *newrec, int8_t offs)
1293 : : {
1294 : 317240 : jl_typemap_t *cache = jl_atomic_load_relaxed(pcache);
1295 : 317240 : jl_typemap_insert_generic(cache, pcache, parent, newrec, offs);
1296 : 317240 : }
1297 : :
1298 : : #ifdef __cplusplus
1299 : : }
1300 : : #endif
|
