-
-
Notifications
You must be signed in to change notification settings - Fork 5.5k
/
subtype.c
2619 lines (2486 loc) · 94 KB
/
subtype.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// This file is a part of Julia. License is MIT: https://julialang.org/license
/*
subtyping predicate
Uses the algorithm described in section 4.2.2 of https://github.com/JeffBezanson/phdthesis/
This code adds the following features to the core algorithm:
- Type variables can be restricted to range over only concrete types.
This is done by returning false if such a variable's lower bound is not concrete.
- Diagonal rule: a type variable is concrete if it occurs more than once in
covariant position, and never in invariant position. This sounds like a syntactic
property, but actually isn't since it depends on which occurrences of a type
variable the algorithm actually uses.
- Unconstrained type vars (Bottom<:T<:Any) can match non-type values.
- Vararg types have an int-valued length parameter N (in `Vararg{T,N}`).
- Type{T}<:S if isa(T,S). Existing code assumes this, but it's not strictly
correct since a type can equal `T` without having the same representation.
- Free type variables are tolerated. This can hopefully be removed after a
deprecation period.
*/
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#ifdef _OS_WINDOWS_
#include <malloc.h>
#endif
#include "julia.h"
#include "julia_internal.h"
#ifdef __cplusplus
extern "C" {
#endif
// stack of bits to keep track of which combination of Union components we are
// looking at (0 for Union.a, 1 for Union.b). forall_exists_subtype and
// exists_subtype loop over all combinations by updating a binary count in
// this structure.
// Union type decision points are discovered while the algorithm works.
// If a new Union decision is encountered, the `more` flag is set to tell
// the forall/exists loop to grow the stack.
// TODO: the stack probably needs to be artifically large because of some
// deeper problem (see #21191) and could be shrunk once that is fixed
typedef struct {
int depth;
int more;
uint32_t stack[100]; // stack of bits represented as a bit vector
} jl_unionstate_t;
// Linked list storing the type variable environment. A new jl_varbinding_t
// is pushed for each UnionAll type we encounter. `lb` and `ub` are updated
// during the computation.
// Most of the complexity is due to the "diagonal rule", requiring us to
// identify which type vars range over only concrete types.
typedef struct _varbinding {
jl_tvar_t *var;
jl_value_t *lb;
jl_value_t *ub;
int8_t right; // whether this variable came from the right side of `A <: B`
// if another var that this one depends on is found to be concrete, store it
// here for reference in case that var is popped from the environment before this one.
// TODO: generalize this to multiple variables
jl_tvar_t *concretevar;
int8_t occurs_inv; // occurs in invariant position
int8_t occurs_cov; // # of occurrences in covariant position
int8_t concrete; // 1 if another variable has a constraint forcing this one to be concrete
// in covariant position, we need to try constraining a variable in different ways:
// 0 - unconstrained
// 1 - less than
// 2 - greater than
// 3 - inexpressible - occurs when the var has non-trivial overlap with another type,
// and we would need to return `intersect(var,other)`. in this case
// we choose to over-estimate the intersection by returning the var.
int8_t constraintkind;
int depth0; // # of invariant constructors nested around the UnionAll type for this var
// when this variable's integer value is compared to that of another,
// it equals `other + offset`. used by vararg length parameters.
int offset;
// array of typevars that our bounds depend on, whose UnionAlls need to be
// moved outside ours.
jl_array_t *innervars;
struct _varbinding *prev;
} jl_varbinding_t;
// subtype algorithm state
typedef struct {
jl_varbinding_t *vars; // type variable environment
jl_unionstate_t Lunions; // union state for unions on the left of A <: B
jl_unionstate_t Runions; // union state for unions on the right
jl_value_t **envout; // for passing caller the computed bounds of right-side variables
int envsz; // length of envout
int envidx; // current index in envout
int invdepth; // current number of invariant constructors we're nested in
int ignore_free; // treat free vars as black boxes; used during intersection
int intersection; // true iff subtype is being called from intersection
int emptiness_only; // true iff intersection only needs to test for emptiness
} jl_stenv_t;
// state manipulation utilities
// look up a type variable in an environment
static jl_varbinding_t *lookup(jl_stenv_t *e, jl_tvar_t *v)
{
jl_varbinding_t *b = e->vars;
while (b != NULL) {
if (b->var == v) return b;
b = b->prev;
}
return b;
}
static int statestack_get(jl_unionstate_t *st, int i)
{
assert(i >= 0 && i < sizeof(st->stack) * 8);
// get the `i`th bit in an array of 32-bit words
return (st->stack[i>>5] & (1<<(i&31))) != 0;
}
static void statestack_set(jl_unionstate_t *st, int i, int val)
{
assert(i >= 0 && i < sizeof(st->stack) * 8);
if (val)
st->stack[i>>5] |= (1<<(i&31));
else
st->stack[i>>5] &= ~(1<<(i&31));
}
typedef struct {
int8_t *buf;
int rdepth;
} jl_savedenv_t;
static void save_env(jl_stenv_t *e, jl_value_t **root, jl_savedenv_t *se)
{
jl_varbinding_t *v = e->vars;
int len=0;
while (v != NULL) {
len++;
v = v->prev;
}
*root = (jl_value_t*)jl_alloc_svec(len*3);
se->buf = (int8_t*)(len ? malloc(len*2) : NULL);
int i=0, j=0; v = e->vars;
while (v != NULL) {
jl_svecset(*root, i++, v->lb);
jl_svecset(*root, i++, v->ub);
jl_svecset(*root, i++, (jl_value_t*)v->innervars);
se->buf[j++] = v->occurs_inv;
se->buf[j++] = v->occurs_cov;
v = v->prev;
}
se->rdepth = e->Runions.depth;
}
static void restore_env(jl_stenv_t *e, jl_value_t *root, jl_savedenv_t *se)
{
jl_varbinding_t *v = e->vars;
int i = 0, j = 0;
while (v != NULL) {
if (root) v->lb = jl_svecref(root, i);
i++;
if (root) v->ub = jl_svecref(root, i);
i++;
if (root) v->innervars = (jl_array_t*)jl_svecref(root, i);
i++;
v->occurs_inv = se->buf[j++];
v->occurs_cov = se->buf[j++];
v = v->prev;
}
e->Runions.depth = se->rdepth;
if (e->envout && e->envidx < e->envsz)
memset(&e->envout[e->envidx], 0, (e->envsz - e->envidx)*sizeof(void*));
}
// type utilities
// quickly test that two types are identical
static int obviously_egal(jl_value_t *a, jl_value_t *b)
{
if (a == b) return 1;
if (jl_typeof(a) != jl_typeof(b)) return 0;
if (jl_is_datatype(a)) {
jl_datatype_t *ad = (jl_datatype_t*)a, *bd = (jl_datatype_t*)b;
if (ad->name != bd->name) return 0;
size_t i, np = jl_nparams(ad);
if (np != jl_nparams(bd)) return 0;
for(i=0; i < np; i++) {
if (!obviously_egal(jl_tparam(ad,i), jl_tparam(bd,i)))
return 0;
}
return 1;
}
if (jl_is_uniontype(a)) {
return obviously_egal(((jl_uniontype_t*)a)->a, ((jl_uniontype_t*)b)->a) &&
obviously_egal(((jl_uniontype_t*)a)->b, ((jl_uniontype_t*)b)->b);
}
if (jl_is_unionall(a)) {
return ((jl_unionall_t*)a)->var == ((jl_unionall_t*)b)->var &&
obviously_egal(((jl_unionall_t*)a)->body, ((jl_unionall_t*)b)->body);
}
if (jl_is_typevar(a)) return 0;
return !jl_is_type(a) && jl_egal(a,b);
}
static int obviously_unequal(jl_value_t *a, jl_value_t *b)
{
if (a == b)
return 0;
if (jl_is_leaf_type(a) && !((jl_datatype_t*)a)->abstract)
return 1;
if (jl_is_leaf_type(b) && !((jl_datatype_t*)b)->abstract)
return 1;
if (jl_is_unionall(a)) a = jl_unwrap_unionall(a);
if (jl_is_unionall(b)) b = jl_unwrap_unionall(b);
if (jl_is_datatype(a)) {
if (b == jl_bottom_type) return 1;
if (jl_is_datatype(b)) {
jl_datatype_t *ad = (jl_datatype_t*)a, *bd = (jl_datatype_t*)b;
if (ad->name != bd->name)
return 1;
size_t i, np = jl_nparams(ad);
if (np != jl_nparams(bd)) return 1;
for(i=0; i < np; i++) {
if (obviously_unequal(jl_tparam(ad,i), jl_tparam(bd,i)))
return 1;
}
}
}
else if (a == jl_bottom_type && jl_is_datatype(b)) {
return 1;
}
if (jl_is_typevar(a) && jl_is_typevar(b) && obviously_unequal(((jl_tvar_t*)a)->ub, ((jl_tvar_t*)b)->ub))
return 1;
if (jl_is_long(a)) {
if (jl_is_long(b) && jl_unbox_long(a) != jl_unbox_long(b))
return 1;
}
else if (jl_is_long(b)) return 1;
if ((jl_is_symbol(a) || jl_is_symbol(b)) && a != b)
return 1;
return 0;
}
int jl_obviously_unequal(jl_value_t *a, jl_value_t *b)
{
return obviously_unequal(a, b);
}
static int obviously_disjoint(jl_value_t *a, jl_value_t *b, int specificity)
{
if (a == b || a == (jl_value_t*)jl_any_type || b == (jl_value_t*)jl_any_type)
return 0;
if (jl_is_leaf_type(a) && !((jl_datatype_t*)a)->abstract &&
jl_is_leaf_type(b) && !((jl_datatype_t*)b)->abstract &&
// TODO: remove these 2 lines if and when Tuple{Union{}} === Union{}
(((jl_datatype_t*)a)->name != jl_tuple_typename ||
((jl_datatype_t*)b)->name != jl_tuple_typename))
return 1;
if (jl_is_unionall(a)) a = jl_unwrap_unionall(a);
if (jl_is_unionall(b)) b = jl_unwrap_unionall(b);
if (jl_is_datatype(a) && jl_is_datatype(b)) {
jl_datatype_t *ad = (jl_datatype_t*)a, *bd = (jl_datatype_t*)b;
if (ad->name != bd->name) {
jl_datatype_t *temp = ad;
while (temp != jl_any_type && temp->name != bd->name)
temp = temp->super;
if (temp == jl_any_type) {
temp = bd;
while (temp != jl_any_type && temp->name != ad->name)
temp = temp->super;
if (temp == jl_any_type)
return 1;
bd = temp;
}
else {
ad = temp;
}
if (specificity) {
// account for declared subtypes taking priority (issue #21710)
return 0;
}
}
int istuple = (ad->name == jl_tuple_typename);
size_t np;
if (istuple) {
size_t na = jl_nparams(ad), nb = jl_nparams(bd);
if (jl_is_va_tuple(ad)) {
na -= 1;
if (jl_is_va_tuple(bd))
nb -= 1;
}
else if (jl_is_va_tuple(bd)) {
nb -= 1;
}
else if (!specificity && na != nb) {
// note: some disjoint types (e.g. tuples of different lengths) can be more specific
return 1;
}
np = na < nb ? na : nb;
}
else {
np = jl_nparams(ad);
}
size_t i;
for(i=0; i < np; i++) {
jl_value_t *ai = jl_tparam(ad,i);
jl_value_t *bi = jl_tparam(bd,i);
if (jl_is_typevar(ai) || jl_is_typevar(bi))
continue;
if (jl_is_type(ai)) {
if (jl_is_type(bi)) {
if (istuple && (ai == jl_bottom_type || bi == jl_bottom_type))
; // TODO: this can return 1 if and when Tuple{Union{}} === Union{}
else if (obviously_disjoint(ai, bi, specificity))
return 1;
}
else if (!specificity) {
// Tuple{1} is more specific than Tuple{Any}
return 1;
}
}
else if (jl_is_type(bi)) {
if (!specificity)
return 1;
}
else if (!jl_egal(ai, bi)) {
return 1;
}
}
}
else if (a == jl_bottom_type || b == jl_bottom_type) {
return 1;
}
return 0;
}
static int in_union(jl_value_t *u, jl_value_t *x)
{
if (u == x) return 1;
if (!jl_is_uniontype(u)) return 0;
return in_union(((jl_uniontype_t*)u)->a, x) || in_union(((jl_uniontype_t*)u)->b, x);
}
// compute a least upper bound of `a` and `b`
static jl_value_t *simple_join(jl_value_t *a, jl_value_t *b)
{
if (a == jl_bottom_type || b == (jl_value_t*)jl_any_type || obviously_egal(a,b))
return b;
if (b == jl_bottom_type || a == (jl_value_t*)jl_any_type)
return a;
if (!(jl_is_type(a) || jl_is_typevar(a)) || !(jl_is_type(b) || jl_is_typevar(b)))
return (jl_value_t*)jl_any_type;
if (jl_is_uniontype(a) && in_union(a, b))
return a;
if (jl_is_uniontype(b) && in_union(b, a))
return b;
if (jl_is_kind(a) && jl_is_type_type(b) && jl_typeof(jl_tparam0(b)) == a)
return a;
if (jl_is_kind(b) && jl_is_type_type(a) && jl_typeof(jl_tparam0(a)) == b)
return b;
if (!jl_has_free_typevars(a) && !jl_has_free_typevars(b)) {
if (jl_subtype(a, b)) return b;
if (jl_subtype(b, a)) return a;
}
return jl_new_struct(jl_uniontype_type, a, b);
}
static jl_unionall_t *rename_unionall(jl_unionall_t *u)
{
jl_tvar_t *v = jl_new_typevar(u->var->name, u->var->lb, u->var->ub);
jl_value_t *t = NULL;
JL_GC_PUSH2(&v, &t);
t = jl_instantiate_unionall(u, (jl_value_t*)v);
t = jl_new_struct(jl_unionall_type, v, t);
JL_GC_POP();
return (jl_unionall_t*)t;
}
// main subtyping algorithm
static int subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param);
static jl_value_t *pick_union_element(jl_value_t *u, jl_stenv_t *e, int8_t R)
{
jl_unionstate_t *state = R ? &e->Runions : &e->Lunions;
do {
int ui = statestack_get(state, state->depth);
state->depth++;
if (ui == 0) {
state->more = state->depth; // memorize that this was the deepest available choice
u = ((jl_uniontype_t*)u)->a;
}
else {
u = ((jl_uniontype_t*)u)->b;
}
} while (jl_is_uniontype(u));
return u;
}
// compare the current component of `u` to `t`. `R==1` means `u` came from the right side.
static int subtype_union(jl_value_t *t, jl_uniontype_t *u, jl_stenv_t *e, int8_t R, int param)
{
jl_value_t *choice = pick_union_element((jl_value_t*)u, e, R);
return R ? subtype(t, choice, e, param) : subtype(choice, t, e, param);
}
// subtype(), but taking apart unions before handling vars
static int subtype_ufirst(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
{
if (jl_is_uniontype(x) && jl_is_typevar(y))
return subtype_union(y, (jl_uniontype_t*)x, e, 0, 0);
if (jl_is_typevar(x) && jl_is_uniontype(y))
return (x == ((jl_uniontype_t*)y)->a || x == ((jl_uniontype_t*)y)->b ||
subtype_union(x, (jl_uniontype_t*)y, e, 1, 0));
return subtype(x, y, e, 0);
}
// use the current context to record where a variable occurred, for the purpose
// of determining whether the variable is concrete.
static void record_var_occurrence(jl_varbinding_t *vb, jl_stenv_t *e, int param)
{
if (vb != NULL && param) {
if (param == 2 && e->invdepth > vb->depth0)
vb->occurs_inv++;
else
vb->occurs_cov++;
}
}
// is var x's quantifier outside y's in nesting order
static int var_outside(jl_stenv_t *e, jl_tvar_t *x, jl_tvar_t *y)
{
jl_varbinding_t *btemp = e->vars;
while (btemp != NULL) {
if (btemp->var == x) return 0;
if (btemp->var == y) return 1;
btemp = btemp->prev;
}
return 0;
}
static jl_value_t *intersect_ufirst(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int depth);
// check that type var `b` is <: `a`, and update b's upper bound.
static int var_lt(jl_tvar_t *b, jl_value_t *a, jl_stenv_t *e, int param)
{
jl_varbinding_t *bb = lookup(e, b);
if (bb == NULL)
return e->ignore_free || subtype_ufirst(b->ub, a, e);
record_var_occurrence(bb, e, param);
if (!bb->right) // check ∀b . b<:a
return subtype_ufirst(bb->ub, a, e);
if (bb->ub == a)
return 1;
if (!((bb->lb == jl_bottom_type && !jl_is_type(a) && !jl_is_typevar(a)) || subtype_ufirst(bb->lb, a, e)))
return 0;
// for contravariance we would need to compute a meet here, but
// because of invariance bb.ub ⊓ a == a here always. however for this
// to work we need to compute issub(left,right) before issub(right,left),
// since otherwise the issub(a, bb.ub) check in var_gt becomes vacuous.
if (e->intersection) {
jl_value_t *ub = intersect_ufirst(bb->ub, a, e, bb->depth0);
if (ub != (jl_value_t*)b)
bb->ub = ub;
}
else {
bb->ub = a; // meet(bb->ub, a)
}
assert(bb->ub != (jl_value_t*)b);
if (jl_is_typevar(a)) {
jl_varbinding_t *aa = lookup(e, (jl_tvar_t*)a);
if (aa && !aa->right && in_union(bb->lb, a) && bb->depth0 != aa->depth0 && var_outside(e, b, (jl_tvar_t*)a)) {
// an "exists" var cannot equal a "forall" var inside it unless the forall
// var has equal bounds.
return subtype_ufirst(aa->ub, aa->lb, e);
}
}
return 1;
}
// check that type var `b` is >: `a`, and update b's lower bound.
static int var_gt(jl_tvar_t *b, jl_value_t *a, jl_stenv_t *e, int param)
{
jl_varbinding_t *bb = lookup(e, b);
if (bb == NULL)
return e->ignore_free || subtype_ufirst(a, b->lb, e);
record_var_occurrence(bb, e, param);
if (!bb->right) // check ∀b . b>:a
return subtype_ufirst(a, bb->lb, e);
if (bb->lb == bb->ub) {
if (jl_is_typevar(bb->lb) && !jl_is_type(a) && !jl_is_typevar(a))
return var_gt((jl_tvar_t*)bb->lb, a, e, param);
if (jl_is_typevar(a) && !jl_is_type(bb->lb) && !jl_is_typevar(bb->lb))
return var_lt((jl_tvar_t*)a, bb->lb, e, param);
}
if (!((bb->ub == (jl_value_t*)jl_any_type && !jl_is_type(a) && !jl_is_typevar(a)) || subtype_ufirst(a, bb->ub, e)))
return 0;
bb->lb = simple_join(bb->lb, a);
assert(bb->lb != (jl_value_t*)b);
return 1;
}
// check that a type is concrete. this is used to check concrete typevars;
// issubtype is false if the lower bound of a concrete type var is not concrete.
static int is_leaf_bound(jl_value_t *v)
{
if (v == jl_bottom_type) return 1;
if (jl_is_datatype(v)) {
if (((jl_datatype_t*)v)->isleaftype) return 1;
if (((jl_datatype_t*)v)->abstract) {
if (jl_is_type_type(v))
return 1;//!jl_has_free_typevars(jl_tparam0(v));
return 0;
}
jl_svec_t *t = ((jl_datatype_t*)v)->parameters;
size_t l = jl_svec_len(t);
if (((jl_datatype_t*)v)->name == jl_tuple_typename) {
for(int i=0; i < l; i++) {
if (!is_leaf_bound(jl_svecref(t,i)))
return 0;
}
}
return 1;
}
return !jl_is_type(v) && !jl_is_typevar(v);
}
static int is_leaf_typevar(jl_value_t *v)
{
if (jl_is_typevar(v))
return is_leaf_typevar(((jl_tvar_t*)v)->lb);
return is_leaf_bound(v);
}
static jl_value_t *widen_Type(jl_value_t *t)
{
if (jl_is_type_type(t) && !jl_is_typevar(jl_tparam0(t)))
return jl_typeof(jl_tparam0(t));
if (jl_is_uniontype(t)) {
jl_value_t *a = widen_Type(((jl_uniontype_t*)t)->a);
jl_value_t *b = widen_Type(((jl_uniontype_t*)t)->b);
if (a == b)
return a;
}
return t;
}
// compare UnionAll type `u` to `t`. `R==1` if `u` came from the right side of A <: B.
static int subtype_unionall(jl_value_t *t, jl_unionall_t *u, jl_stenv_t *e, int8_t R, int param)
{
jl_varbinding_t *btemp = e->vars;
// if the var for this unionall (based on identity) already appears somewhere
// in the environment, rename to get a fresh var.
while (btemp != NULL) {
if (btemp->var == u->var ||
// outer var can only refer to inner var if bounds changed
(btemp->lb != btemp->var->lb && jl_has_typevar(btemp->lb, u->var)) ||
(btemp->ub != btemp->var->ub && jl_has_typevar(btemp->ub, u->var))) {
u = rename_unionall(u);
break;
}
btemp = btemp->prev;
}
jl_varbinding_t vb = { u->var, u->var->lb, u->var->ub, R, NULL, 0, 0, 0, 0, e->invdepth, 0, NULL, e->vars };
JL_GC_PUSH3(&u, &vb.lb, &vb.ub);
e->vars = &vb;
int ans;
if (R) {
e->envidx++;
ans = subtype(t, u->body, e, param);
e->envidx--;
// widen Type{x} to typeof(x) in argument position
if (!vb.occurs_inv)
vb.lb = widen_Type(vb.lb);
// fill variable values into `envout` up to `envsz`
if (e->envidx < e->envsz) {
jl_value_t *val;
if (!vb.occurs_inv && vb.lb != jl_bottom_type)
val = is_leaf_bound(vb.lb) ? vb.lb : (jl_value_t*)jl_new_typevar(u->var->name, jl_bottom_type, vb.lb);
else if (vb.lb == vb.ub)
val = vb.lb;
else if (vb.lb != jl_bottom_type)
// TODO: for now return the least solution, which is what
// method parameters expect.
val = vb.lb;
else if (vb.lb == u->var->lb && vb.ub == u->var->ub)
val = (jl_value_t*)u->var;
else
val = (jl_value_t*)jl_new_typevar(u->var->name, vb.lb, vb.ub);
jl_value_t *oldval = e->envout[e->envidx];
// if we try to assign different variable values (due to checking
// multiple union members), consider the value unknown.
if (!oldval || !jl_is_typevar(oldval) || !jl_is_long(val))
e->envout[e->envidx] = val;
// TODO: substitute the value (if any) of this variable into previous envout entries
}
}
else {
ans = subtype(u->body, t, e, param);
}
// handle the "diagonal dispatch" rule, which says that a type var occurring more
// than once, and only in covariant position, is constrained to concrete types. E.g.
// ( Tuple{Int, Int} <: Tuple{T, T} where T) but
// !( Tuple{Int, String} <: Tuple{T, T} where T)
// Then check concreteness by checking that the lower bound is not an abstract type.
if (ans && (vb.concrete || (!vb.occurs_inv && vb.occurs_cov > 1)) &&
is_leaf_typevar((jl_value_t*)u->var)) {
if (jl_is_typevar(vb.lb)) {
// TODO test case that demonstrates the need for this?
/*
jl_tvar_t *v = (jl_tvar_t*)vb.lb;
jl_varbinding_t *vlb = lookup(e, v);
if (vlb)
vlb->concrete = 1;
else // TODO handle multiple variables in vb.concretevar
ans = (v == vb.concretevar);
*/
}
else if (!is_leaf_bound(vb.lb)) {
ans = 0;
}
if (ans) {
// if we occur as another var's lower bound, record the fact that we
// were concrete so that subtype can return true for that var.
/*
btemp = vb.prev;
while (btemp != NULL) {
if (btemp->lb == (jl_value_t*)u->var)
btemp->concretevar = u->var;
btemp = btemp->prev;
}
*/
}
}
e->vars = vb.prev;
btemp = e->vars;
while (btemp != NULL) {
jl_value_t *vi = btemp->ub;
// TODO: this takes a significant amount of time
if (vi != (jl_value_t*)vb.var && btemp->var->ub != vi && jl_has_typevar(vi, vb.var)) {
btemp->ub = jl_new_struct(jl_unionall_type, vb.var, vi);
btemp->lb = jl_bottom_type;
}
btemp = btemp->prev;
}
JL_GC_POP();
return ans;
}
// unwrap <=2 layers of UnionAlls, leaving the vars in *p1 and *p2 and returning the body
static jl_value_t *unwrap_2_unionall(jl_value_t *t, jl_tvar_t **p1, jl_tvar_t **p2)
{
if (jl_is_unionall(t)) {
*p1 = ((jl_unionall_t*)t)->var;
t = ((jl_unionall_t*)t)->body;
if (jl_is_unionall(t)) {
*p2 = ((jl_unionall_t*)t)->var;
t = ((jl_unionall_t*)t)->body;
}
}
return t;
}
// check n <: (length of vararg type v)
static int check_vararg_length(jl_value_t *v, ssize_t n, jl_stenv_t *e)
{
jl_tvar_t *va_p1=NULL, *va_p2=NULL;
jl_value_t *tail = unwrap_2_unionall(v, &va_p1, &va_p2);
assert(jl_is_datatype(tail));
jl_value_t *N = jl_tparam1(tail);
// only do the check if N is free in the tuple type's last parameter
if (N != (jl_value_t*)va_p1 && N != (jl_value_t*)va_p2) {
jl_value_t *nn = jl_box_long(n);
JL_GC_PUSH1(&nn);
e->invdepth++;
int ans = subtype(nn, N, e, 2) && subtype(N, nn, e, 0);
e->invdepth--;
JL_GC_POP();
if (!ans)
return 0;
}
return 1;
}
static int subtype_tuple(jl_datatype_t *xd, jl_datatype_t *yd, jl_stenv_t *e, int param)
{
size_t lx = jl_nparams(xd), ly = jl_nparams(yd);
if (lx == 0 && ly == 0)
return 1;
size_t i=0, j=0;
int vx=0, vy=0, vvx = (lx > 0 && jl_is_vararg_type(jl_tparam(xd, lx-1)));
int vvy = (ly > 0 && jl_is_vararg_type(jl_tparam(yd, ly-1)));
if (vvx) {
if ((vvy && ly > lx) || (!vvy && ly < lx-1))
return 0;
}
else if ((vvy && ly > lx+1) || (!vvy && lx != ly)) {
return 0;
}
param = (param == 0 ? 1 : param);
jl_value_t *lastx=NULL, *lasty=NULL;
while (i < lx) {
jl_value_t *xi = jl_tparam(xd, i);
if (i == lx-1 && vvx) vx = 1;
jl_value_t *yi = NULL;
if (j < ly) {
yi = jl_tparam(yd, j);
if (j == ly-1 && vvy) vy = 1;
}
if (vx && !vy) {
if (!check_vararg_length(xi, ly+1-lx, e))
return 0;
jl_tvar_t *p1=NULL, *p2=NULL;
xi = unwrap_2_unionall(xi, &p1, &p2);
jl_value_t *N = jl_tparam1(xi);
if (N == (jl_value_t*)p1 || N == (jl_value_t*)p2)
return 0;
if (j >= ly) return 1;
xi = jl_tparam0(xi);
}
else if (j >= ly) {
return 0;
}
if (!vx && vy) {
jl_tvar_t *p1=NULL, *p2=NULL;
yi = jl_tparam0(unwrap_2_unionall(yi, &p1, &p2));
if (yi == (jl_value_t*)p1 || yi == (jl_value_t*)p2)
yi = ((jl_tvar_t*)yi)->ub;
if (!vvx && yi == (jl_value_t*)jl_any_type)
break; // if y ends in `Vararg{Any}` skip checking everything
}
if (vx && vy) {
// skip testing element type if vararg lengths are 0
if (jl_is_datatype(xi)) {
jl_value_t *xl = jl_tparam1(xi);
if (jl_is_typevar(xl)) {
jl_varbinding_t *xlv = lookup(e, (jl_tvar_t*)xl);
if (xlv && jl_is_long(xlv->lb) && jl_unbox_long(xlv->lb) == 0)
break;
}
}
if (jl_is_datatype(yi)) {
jl_value_t *yl = jl_tparam1(yi);
if (jl_is_typevar(yl)) {
jl_varbinding_t *ylv = lookup(e, (jl_tvar_t*)yl);
if (ylv && jl_is_long(ylv->lb) && jl_unbox_long(ylv->lb) == 0)
break;
}
}
}
if (xi == lastx &&
((yi == lasty && !jl_has_free_typevars(xi) && !jl_has_free_typevars(yi)) ||
(yi == lasty && !vx && vy && jl_is_leaf_type(xi)))) {
// fast path for repeated elements
}
else if (e->Runions.depth == 0 && e->Lunions.depth == 0 && !jl_has_free_typevars(xi) && !jl_has_free_typevars(yi)) {
// fast path for separable sub-formulas
if (!jl_subtype(xi, yi))
return 0;
}
else if (!subtype(xi, yi, e, param)) {
return 0;
}
if (vx && vy) break;
lastx = xi; lasty = yi;
if (i < lx-1 || !vx)
i++;
if (j < ly-1 || !vy)
j++;
}
// TODO: handle Vararg with explicit integer length parameter
vy = vy || (j < ly && jl_is_vararg_type(jl_tparam(yd,j)));
if (vy && !vx && lx+1 >= ly) {
// in Tuple{...,tn} <: Tuple{...,Vararg{T,N}}, check (lx+1-ly) <: N
if (!check_vararg_length(jl_tparam(yd,ly-1), lx+1-ly, e))
return 0;
}
return (lx==ly && vx==vy) || (vy && (lx >= (vx ? ly : (ly-1))));
}
static int forall_exists_equal(jl_value_t *x, jl_value_t *y, jl_stenv_t *e);
// `param` means we are currently looking at a parameter of a type constructor
// (as opposed to being outside any type constructor, or comparing variable bounds).
// this is used to record the positions where type variables occur for the
// diagonal rule (record_var_occurrence).
static int subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, int param)
{
if (x == jl_ANY_flag) x = (jl_value_t*)jl_any_type;
if (y == jl_ANY_flag) y = (jl_value_t*)jl_any_type;
if (jl_is_uniontype(x)) {
if (x == y) return 1;
x = pick_union_element(x, e, 0);
}
if (jl_is_uniontype(y)) {
if (x == ((jl_uniontype_t*)y)->a || x == ((jl_uniontype_t*)y)->b)
return 1;
if (jl_is_unionall(x))
return subtype_unionall(y, (jl_unionall_t*)x, e, 0, param);
int ui = 1;
if (jl_is_typevar(x)) {
// The `convert(Type{T},T)` pattern, where T is a Union, required changing priority
// of unions and vars: if matching `typevar <: union`, first try to match the whole
// union against the variable before trying to take it apart to see if there are any
// variables lurking inside.
jl_unionstate_t *state = &e->Runions;
ui = statestack_get(state, state->depth);
state->depth++;
if (ui == 0)
state->more = state->depth; // memorize that this was the deepest available choice
}
if (ui == 1)
y = pick_union_element(y, e, 1);
}
if (jl_is_typevar(x)) {
if (jl_is_typevar(y)) {
if (x == y) return 1;
jl_varbinding_t *xx = lookup(e, (jl_tvar_t*)x);
jl_varbinding_t *yy = lookup(e, (jl_tvar_t*)y);
jl_value_t *xub = xx ? xx->ub : ((jl_tvar_t*)x)->ub;
jl_value_t *ylb = yy ? yy->lb : ((jl_tvar_t*)y)->lb;
if (e->intersection) {
jl_value_t *xlb = xx ? xx->lb : ((jl_tvar_t*)x)->lb;
jl_value_t *yub = yy ? yy->ub : ((jl_tvar_t*)y)->ub;
// find equivalence class for typevars during intersection
if (xub == xlb && jl_is_typevar(xub))
return subtype(xub, y, e, param);
if (yub == ylb && jl_is_typevar(yub))
return subtype(x, yub, e, param);
}
int xr = xx && xx->right; // treat free variables as "forall" (left)
int yr = yy && yy->right;
if (xr) {
if (yy) record_var_occurrence(yy, e, param);
if (yr) {
if (xx) record_var_occurrence(xx, e, param);
return subtype(xx->lb, yy->ub, e, 0);
}
return var_lt((jl_tvar_t*)x, y, e, param);
}
else if (yr) {
if (xx) record_var_occurrence(xx, e, param);
return var_gt((jl_tvar_t*)y, x, e, param);
}
// check ∀x,y . x<:y
// the bounds of left-side variables never change, and can only lead
// to other left-side variables, so using || here is safe.
return subtype(xub, y, e, param) || subtype(x, ylb, e, param);
}
return var_lt((jl_tvar_t*)x, y, e, param);
}
if (jl_is_typevar(y))
return var_gt((jl_tvar_t*)y, x, e, param);
if (y == (jl_value_t*)jl_any_type && !jl_has_free_typevars(x))
return 1;
// handle forall ("left") vars first
if (jl_is_unionall(x)) {
if (x == y && !(e->envidx < e->envsz))
return 1;
return subtype_unionall(y, (jl_unionall_t*)x, e, 0, param);
}
if (jl_is_unionall(y))
return subtype_unionall(x, (jl_unionall_t*)y, e, 1, param);
if (jl_is_datatype(x) && jl_is_datatype(y)) {
if (x == y) return 1;
if (y == (jl_value_t*)jl_any_type) return 1;
jl_datatype_t *xd = (jl_datatype_t*)x, *yd = (jl_datatype_t*)y;
if (jl_is_type_type(x) && !jl_is_type_type(y)) {
jl_value_t *tp0 = jl_tparam0(xd);
if (!jl_is_typevar(tp0)) {
// TODO this is not strictly correct, but we don't yet have any other way for
// e.g. the argument `Int` to match a `::DataType` slot. Most correct would be:
// Int isa DataType, Int isa Type{Int}, Type{Int} more specific than DataType,
// !(Type{Int} <: DataType), !isleaftype(Type{Int}), because non-DataTypes can
// be type-equal to `Int`.
return jl_typeof(tp0) == (jl_value_t*)yd;
}
return 0;
}
if (jl_is_type_type(y) && !jl_is_type_type(x) && x != (jl_value_t*)jl_typeofbottom_type) {
jl_value_t *tp0 = jl_tparam0(yd);
if (!jl_is_typevar(tp0))
return 0;
if (!jl_is_kind(x)) return 0;
jl_varbinding_t *yy = lookup(e, (jl_tvar_t*)tp0);
jl_value_t *ub = yy ? yy->ub : ((jl_tvar_t*)tp0)->ub;
int ans;
if (ub == (jl_value_t*)jl_any_type) {
ans = subtype((jl_value_t*)jl_type_type, y, e, param);
}
else {
e->invdepth++;
ans = forall_exists_equal(x, tp0, e);
e->invdepth--;
}
return ans;
}
while (xd != jl_any_type && xd->name != yd->name) {
if (xd->super == NULL)
jl_errorf("circular type parameter constraint in definition of %s", jl_symbol_name(xd->name->name));
xd = xd->super;
}
if (xd == jl_any_type) return 0;
if (xd->name == jl_tuple_typename)
return subtype_tuple(xd, yd, e, param);
if (xd->name == jl_vararg_typename) {
// Vararg: covariant in first parameter, invariant in second
jl_value_t *xp1=jl_tparam0(xd), *xp2=jl_tparam1(xd), *yp1=jl_tparam0(yd), *yp2=jl_tparam1(yd);
// in Vararg{T1} <: Vararg{T2}, need to check subtype twice to
// simulate the possibility of multiple arguments, which is needed
// to implement the diagonal rule correctly.
if (!subtype(xp1, yp1, e, 1)) return 0;
if (!subtype(xp1, yp1, e, 1)) return 0;
// Vararg{T,N} <: Vararg{T2,N2}; equate N and N2
e->invdepth++;
int ans = forall_exists_equal(xp2, yp2, e);
e->invdepth--;
return ans;
}
size_t i, np = jl_nparams(xd);
int ans = 1;
e->invdepth++;
for (i=0; i < np; i++) {
jl_value_t *xi = jl_tparam(xd, i), *yi = jl_tparam(yd, i);
if (!(xi == yi || forall_exists_equal(xi, yi, e))) {
ans = 0; break;
}
}
e->invdepth--;
return ans;
}
if (jl_is_type(y))
return x == jl_bottom_type;
return x == y || jl_egal(x, y);
}
static int forall_exists_equal(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
{
jl_unionstate_t oldLunions = e->Lunions;
memset(e->Lunions.stack, 0, sizeof(e->Lunions.stack));
int lastset = 0;
int sub;
while (1) {
e->Lunions.more = 0;
e->Lunions.depth = 0;
sub = subtype(x, y, e, 2);
int set = e->Lunions.more;
if (!sub || !set)
break;
for (int i = set; i <= lastset; i++)
statestack_set(&e->Lunions, i, 0);
lastset = set - 1;
statestack_set(&e->Lunions, lastset, 1);
}
e->Lunions = oldLunions;
return sub && subtype(y, x, e, 0);
}
static int exists_subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e, jl_value_t *saved, jl_savedenv_t *se)
{
memset(e->Runions.stack, 0, sizeof(e->Runions.stack));
int lastset = 0;
while (1) {
e->Runions.depth = 0;
e->Runions.more = 0;
e->Lunions.depth = 0;
e->Lunions.more = 0;
if (subtype(x, y, e, 0))
return 1;
restore_env(e, saved, se);
int set = e->Runions.more;
if (!set)
return 0;
for (int i = set; i <= lastset; i++)
statestack_set(&e->Runions, i, 0);
lastset = set - 1;
statestack_set(&e->Runions, lastset, 1);
}
}
static int forall_exists_subtype(jl_value_t *x, jl_value_t *y, jl_stenv_t *e)
{
// The depth recursion has the following shape, after simplification:
// ∀₁
// ∃₁
assert(e->Runions.depth == 0);
assert(e->Lunions.depth == 0);
jl_value_t *saved=NULL; jl_savedenv_t se;
JL_GC_PUSH1(&saved);
save_env(e, &saved, &se);
memset(e->Lunions.stack, 0, sizeof(e->Lunions.stack));
int lastset = 0;
int sub;
while (1) {
sub = exists_subtype(x, y, e, saved, &se);