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
|
# This file is a part of Julia. License is MIT: https://julialang.org/license
#####################
# lattice utilities #
#####################
function rewrap(@nospecialize(t), @nospecialize(u))
isa(t, Const) && return t
isa(t, Conditional) && return t
return rewrap_unionall(t, u)
end
isType(@nospecialize t) = isa(t, DataType) && t.name === _TYPE_NAME
# true if Type{T} is inlineable as constant T
# requires that T is a singleton, s.t. T == S implies T === S
isconstType(@nospecialize t) = isType(t) && issingletontype(t.parameters[1])
# test whether T is a singleton type, s.t. T == S implies T === S
function issingletontype(@nospecialize t)
# typeof(Bottom) is special since even though it is a leaftype,
# at runtime, it might be Type{Union{}} instead, so don't attempt inference of it
t === typeof(Union{}) && return false
t === Union{} && return true
isa(t, TypeVar) && return false # TypeVars are identified by address, not equality
iskindtype(typeof(t)) || return true # non-types are always compared by egal in the type system
isconcretetype(t) && return true # these are also interned and pointer comparable
if isa(t, DataType) && t.name !== Tuple.name && !isvarargtype(t) # invariant DataTypes
return _all(issingletontype, t.parameters)
end
return false
end
# Subtyping currently intentionally answers certain queries incorrectly for kind types. For
# some of these queries, this check can be used to somewhat protect against making incorrect
# decisions based on incorrect subtyping. Note that this check, itself, is broken for
# certain combinations of `a` and `b` where one/both isa/are `Union`/`UnionAll` type(s)s.
isnotbrokensubtype(@nospecialize(a), @nospecialize(b)) = (!iskindtype(b) || !isType(a) || issingletontype(a.parameters[1]))
argtypes_to_type(argtypes::Array{Any,1}) = Tuple{anymap(widenconst, argtypes)...}
function isknownlength(t::DataType)
isvatuple(t) || return true
return length(t.parameters) > 0 && isa(unwrap_unionall(t.parameters[end]).parameters[2], Int)
end
# test if non-Type, non-TypeVar `x` can be used to parameterize a type
function valid_tparam(@nospecialize(x))
if isa(x, Tuple)
for t in x
isa(t, Symbol) || isbits(t) || return false
end
return true
end
return isa(x, Symbol) || isbits(x)
end
# return an upper-bound on type `a` with type `b` removed
# such that `return <: a` && `Union{return, b} == Union{a, b}`
function typesubtract(@nospecialize(a), @nospecialize(b))
if a <: b && isnotbrokensubtype(a, b)
return Bottom
end
if isa(a, Union)
return Union{typesubtract(a.a, b),
typesubtract(a.b, b)}
end
return a # TODO: improve this bound?
end
function tvar_extent(@nospecialize t)
while t isa TypeVar
t = t.ub
end
return t
end
_typename(@nospecialize a) = Union{}
_typename(a::TypeVar) = Core.TypeName
function _typename(a::Union)
ta = _typename(a.a)
tb = _typename(a.b)
ta === tb && return ta # same type-name
(ta === Union{} || tb === Union{}) && return Union{} # threw an error
(ta isa Const && tb isa Const) && return Union{} # will throw an error (different type-names)
return Core.TypeName # uncertain result
end
_typename(union::UnionAll) = _typename(union.body)
_typename(a::DataType) = Const(a.name)
function tuple_tail_elem(@nospecialize(init), ct::Vector{Any})
# FIXME: this is broken: it violates subtyping relations and creates invalid types with free typevars
tmerge_maybe_vararg(@nospecialize(a), @nospecialize(b)) = tmerge(a, tvar_extent(unwrapva(b)))
t = init
for x in ct
t = tmerge_maybe_vararg(t, x)
end
return Vararg{widenconst(t)}
end
function countunionsplit(atypes::Union{SimpleVector,Vector{Any}})
nu = 1
for ti in atypes
if isa(ti, Union)
nu, ovf = Core.Intrinsics.checked_smul_int(nu, unionlen(ti::Union))
if ovf
return typemax(Int)
end
end
end
return nu
end
# take a Tuple where one or more parameters are Unions
# and return an array such that those Unions are removed
# and `Union{return...} == ty`
function switchtupleunion(@nospecialize(ty))
tparams = (unwrap_unionall(ty)::DataType).parameters
return _switchtupleunion(Any[tparams...], length(tparams), [], ty)
end
function _switchtupleunion(t::Vector{Any}, i::Int, tunion::Vector{Any}, @nospecialize(origt))
if i == 0
tpl = rewrap_unionall(Tuple{t...}, origt)
push!(tunion, tpl)
else
ti = t[i]
if isa(ti, Union)
for ty in uniontypes(ti::Union)
t[i] = ty
_switchtupleunion(t, i - 1, tunion, origt)
end
t[i] = ti
else
_switchtupleunion(t, i - 1, tunion, origt)
end
end
return tunion
end
# unioncomplexity estimates the number of calls to `tmerge` to obtain the given type by
# counting the Union instances, taking also into account those hidden in a Tuple or UnionAll
unioncomplexity(u::Union) = 1 + unioncomplexity(u.a) + unioncomplexity(u.b)
function unioncomplexity(t::DataType)
t.name === Tuple.name || return 0
c = 0
for ti in t.parameters
ci = unioncomplexity(ti)
if ci > c
c = ci
end
end
return c
end
unioncomplexity(u::UnionAll) = max(unioncomplexity(u.body), unioncomplexity(u.var.ub))
unioncomplexity(@nospecialize(x)) = 0
|
