Report index
StatProfilerHTML.jl report
Generated on Thu, 26 Mar 2020 19:09:01
File source code
Line Exclusive Inclusive Code
1 # This file is a part of Julia. License is MIT: https://julialang.org/license
2
3 ## type join (closest common ancestor, or least upper bound) ##
4
5 """
6 typejoin(T, S)
7
8
9 Return the closest common ancestor of `T` and `S`, i.e. the narrowest type from which
10 they both inherit.
11 """
12 typejoin() = (@_pure_meta; Bottom)
13 typejoin(@nospecialize(t)) = (@_pure_meta; t)
14 typejoin(@nospecialize(t), ts...) = (@_pure_meta; typejoin(t, typejoin(ts...)))
15 function typejoin(@nospecialize(a), @nospecialize(b))
16 @_pure_meta
17 if isa(a, TypeVar)
18 return typejoin(a.ub, b)
19 elseif isa(b, TypeVar)
20 return typejoin(a, b.ub)
21 elseif a <: b
22 return b
23 elseif b <: a
24 return a
25 elseif isa(a, UnionAll)
26 return UnionAll(a.var, typejoin(a.body, b))
27 elseif isa(b, UnionAll)
28 return UnionAll(b.var, typejoin(a, b.body))
29 elseif isa(a, Union)
30 return typejoin(typejoin(a.a, a.b), b)
31 elseif isa(b, Union)
32 return typejoin(a, typejoin(b.a, b.b))
33 elseif a <: Tuple
34 if !(b <: Tuple)
35 return Any
36 end
37 ap, bp = a.parameters, b.parameters
38 lar = length(ap)::Int
39 lbr = length(bp)::Int
40 if lar == 0
41 return Tuple{Vararg{tailjoin(bp, 1)}}
42 end
43 if lbr == 0
44 return Tuple{Vararg{tailjoin(ap, 1)}}
45 end
46 laf, afixed = full_va_len(ap)
47 lbf, bfixed = full_va_len(bp)
48 if laf < lbf
49 if isvarargtype(ap[lar]) && !afixed
50 c = Vector{Any}(undef, laf)
51 c[laf] = Vararg{typejoin(unwrapva(ap[lar]), tailjoin(bp, laf))}
52 n = laf-1
53 else
54 c = Vector{Any}(undef, laf+1)
55 c[laf+1] = Vararg{tailjoin(bp, laf+1)}
56 n = laf
57 end
58 elseif lbf < laf
59 if isvarargtype(bp[lbr]) && !bfixed
60 c = Vector{Any}(undef, lbf)
61 c[lbf] = Vararg{typejoin(unwrapva(bp[lbr]), tailjoin(ap, lbf))}
62 n = lbf-1
63 else
64 c = Vector{Any}(undef, lbf+1)
65 c[lbf+1] = Vararg{tailjoin(ap, lbf+1)}
66 n = lbf
67 end
68 else
69 c = Vector{Any}(undef, laf)
70 n = laf
71 end
72 for i = 1:n
73 ai = ap[min(i,lar)]; bi = bp[min(i,lbr)]
74 ci = typejoin(unwrapva(ai), unwrapva(bi))
75 c[i] = i == length(c) && (isvarargtype(ai) || isvarargtype(bi)) ? Vararg{ci} : ci
76 end
77 return Tuple{c...}
78 elseif b <: Tuple
79 return Any
80 end
81 while b !== Any
82 if a <: b.name.wrapper
83 while a.name !== b.name
84 a = supertype(a)
85 end
86 if a.name === Type.body.name
87 ap = a.parameters[1]
88 bp = b.parameters[1]
89 if ((isa(ap,TypeVar) && ap.lb === Bottom && ap.ub === Any) ||
90 (isa(bp,TypeVar) && bp.lb === Bottom && bp.ub === Any))
91 # handle special Type{T} supertype
92 return Type
93 end
94 end
95 aprimary = a.name.wrapper
96 # join on parameters
97 n = length(a.parameters)
98 if n == 0
99 return aprimary
100 end
101 vars = []
102 for i = 1:n
103 ai, bi = a.parameters[i], b.parameters[i]
104 if ai === bi || (isa(ai,Type) && isa(bi,Type) && ai <: bi && bi <: ai)
105 aprimary = aprimary{ai}
106 else
107 # pushfirst!(vars, aprimary.var)
108 _growbeg!(vars, 1)
109 arrayset(false, vars, aprimary.var, 1)
110 aprimary = aprimary.body
111 end
112 end
113 for v in vars
114 aprimary = UnionAll(v, aprimary)
115 end
116 return aprimary
117 end
118 b = supertype(b)
119 end
120 return Any
121 end
122
123 """
124 promote_typejoin(T, S)
125
126 Compute a type that contains both `T` and `S`, which could be
127 either a parent of both types, or a `Union` if appropriate.
128 Falls back to [`typejoin`](@ref).
129 """
130 promote_typejoin(@nospecialize(a), @nospecialize(b)) = _promote_typejoin(a, b)::Type
131 _promote_typejoin(@nospecialize(a), @nospecialize(b)) = typejoin(a, b)
132 _promote_typejoin(::Type{Nothing}, ::Type{T}) where {T} =
133 isconcretetype(T) || T === Union{} ? Union{T, Nothing} : Any
134 _promote_typejoin(::Type{T}, ::Type{Nothing}) where {T} =
135 isconcretetype(T) || T === Union{} ? Union{T, Nothing} : Any
136 _promote_typejoin(::Type{Missing}, ::Type{T}) where {T} =
137 isconcretetype(T) || T === Union{} ? Union{T, Missing} : Any
138 _promote_typejoin(::Type{T}, ::Type{Missing}) where {T} =
139 isconcretetype(T) || T === Union{} ? Union{T, Missing} : Any
140 _promote_typejoin(::Type{Nothing}, ::Type{Missing}) = Union{Nothing, Missing}
141 _promote_typejoin(::Type{Missing}, ::Type{Nothing}) = Union{Nothing, Missing}
142 _promote_typejoin(::Type{Nothing}, ::Type{Nothing}) = Nothing
143 _promote_typejoin(::Type{Missing}, ::Type{Missing}) = Missing
144
145 # Returns length, isfixed
146 function full_va_len(p)
147 isempty(p) && return 0, true
148 last = p[end]
149 if isvarargtype(last)
150 N = unwrap_unionall(last).parameters[2]
151 if isa(N, Integer)
152 return (length(p) + N - 1)::Int, true
153 end
154 return length(p)::Int, false
155 end
156 return length(p)::Int, true
157 end
158
159 # reduce typejoin over A[i:end]
160 function tailjoin(A, i)
161 if i > length(A)
162 return unwrapva(A[end])
163 end
164 t = Bottom
165 for j = i:length(A)
166 t = typejoin(t, unwrapva(A[j]))
167 end
168 return t
169 end
170
171 ## promotion mechanism ##
172
173 """
174 promote_type(type1, type2)
175
176 Promotion refers to converting values of mixed types to a single common type.
177 `promote_type` represents the default promotion behavior in Julia when
178 operators (usually mathematical) are given arguments of differing types.
179 `promote_type` generally tries to return a type which can at least approximate
180 most values of either input type without excessively widening. Some loss is
181 tolerated; for example, `promote_type(Int64, Float64)` returns
182 [`Float64`](@ref) even though strictly, not all [`Int64`](@ref) values can be
183 represented exactly as `Float64` values.
184
185 ```jldoctest
186 julia> promote_type(Int64, Float64)
187 Float64
188
189 julia> promote_type(Int32, Int64)
190 Int64
191
192 julia> promote_type(Float32, BigInt)
193 BigFloat
194
195 julia> promote_type(Int16, Float16)
196 Float16
197
198 julia> promote_type(Int64, Float16)
199 Float16
200
201 julia> promote_type(Int8, UInt16)
202 UInt16
203 ```
204 """
205 function promote_type end
206
207 promote_type() = Bottom
208 promote_type(T) = T
209 promote_type(T, S, U, V...) = (@_inline_meta; promote_type(T, promote_type(S, U, V...)))
210
211 promote_type(::Type{Bottom}, ::Type{Bottom}) = Bottom
212 promote_type(::Type{T}, ::Type{T}) where {T} = T
213 promote_type(::Type{T}, ::Type{Bottom}) where {T} = T
214 promote_type(::Type{Bottom}, ::Type{T}) where {T} = T
215
216 function promote_type(::Type{T}, ::Type{S}) where {T,S}
217 @_inline_meta
218 # Try promote_rule in both orders. Typically only one is defined,
219 # and there is a fallback returning Bottom below, so the common case is
220 # promote_type(T, S) =>
221 # promote_result(T, S, result, Bottom) =>
222 # typejoin(result, Bottom) => result
223 promote_result(T, S, promote_rule(T,S), promote_rule(S,T))
224 end
225
226 """
227 promote_rule(type1, type2)
228
229 Specifies what type should be used by [`promote`](@ref) when given values of types `type1` and
230 `type2`. This function should not be called directly, but should have definitions added to
231 it for new types as appropriate.
232 """
233 function promote_rule end
234
235 promote_rule(::Type{<:Any}, ::Type{<:Any}) = Bottom
236
237 promote_result(::Type{<:Any},::Type{<:Any},::Type{T},::Type{S}) where {T,S} = (@_inline_meta; promote_type(T,S))
238 # If no promote_rule is defined, both directions give Bottom. In that
239 # case use typejoin on the original types instead.
240 promote_result(::Type{T},::Type{S},::Type{Bottom},::Type{Bottom}) where {T,S} = (@_inline_meta; typejoin(T, S))
241
242 """
243 promote(xs...)
244
245 Convert all arguments to a common type, and return them all (as a tuple).
246 If no arguments can be converted, an error is raised.
247
248 # Examples
249 ```jldoctest
250 julia> promote(Int8(1), Float16(4.5), Float32(4.1))
251 (1.0f0, 4.5f0, 4.1f0)
252 ```
253 """
254 function promote end
255
256 function _promote(x::T, y::S) where {T,S}
257 @_inline_meta
258 R = promote_type(T, S)
259 return (convert(R, x), convert(R, y))
260 end
261 promote_typeof(x) = typeof(x)
262 promote_typeof(x, xs...) = (@_inline_meta; promote_type(typeof(x), promote_typeof(xs...)))
263 function _promote(x, y, z)
264 @_inline_meta
265 R = promote_typeof(x, y, z)
266 return (convert(R, x), convert(R, y), convert(R, z))
267 end
268 function _promote(x, y, zs...)
269 @_inline_meta
270 R = promote_typeof(x, y, zs...)
271 return (convert(R, x), convert(R, y), convert(Tuple{Vararg{R}}, zs)...)
272 end
273 # TODO: promote(x::T, ys::T...) where {T} here to catch all circularities?
274
275 ## promotions in arithmetic, etc. ##
276
277 promote() = ()
278 promote(x) = (x,)
279
280 function promote(x, y)
281 @_inline_meta
282 px, py = _promote(x, y)
283 not_sametype((x,y), (px,py))
284 px, py
285 end
286 function promote(x, y, z)
287 @_inline_meta
288 px, py, pz = _promote(x, y, z)
289 not_sametype((x,y,z), (px,py,pz))
290 px, py, pz
291 end
292 function promote(x, y, z, a...)
293 p = _promote(x, y, z, a...)
294 not_sametype((x, y, z, a...), p)
295 p
296 end
297
298 promote(x::T, y::T, zs::T...) where {T} = (x, y, zs...)
299
300 not_sametype(x::T, y::T) where {T} = sametype_error(x)
301
302 not_sametype(x, y) = nothing
303
304 function sametype_error(input)
305 @_noinline_meta
306 error("promotion of types ",
307 join(map(x->string(typeof(x)), input), ", ", " and "),
308 " failed to change any arguments")
309 end
310
311 +(x::Number, y::Number) = +(promote(x,y)...)
312 *(x::Number, y::Number) = *(promote(x,y)...)
313 -(x::Number, y::Number) = -(promote(x,y)...)
314 /(x::Number, y::Number) = /(promote(x,y)...)
315
316 """
317 ^(x, y)
318
319 Exponentiation operator. If `x` is a matrix, computes matrix exponentiation.
320
321 If `y` is an `Int` literal (e.g. `2` in `x^2` or `-3` in `x^-3`), the Julia code
322 `x^y` is transformed by the compiler to `Base.literal_pow(^, x, Val(y))`, to
323 enable compile-time specialization on the value of the exponent.
324 (As a default fallback we have `Base.literal_pow(^, x, Val(y)) = ^(x,y)`,
325 where usually `^ == Base.^` unless `^` has been defined in the calling
326 namespace.)
327
328 ```jldoctest
329 julia> 3^5
330 243
331
332 julia> A = [1 2; 3 4]
333 2×2 Array{Int64,2}:
334 1 2
335 3 4
336
337 julia> A^3
338 2×2 Array{Int64,2}:
339 37 54
340 81 118
341 ```
342 """
343 ^(x::Number, y::Number) = ^(promote(x,y)...)
344
345 fma(x::Number, y::Number, z::Number) = fma(promote(x,y,z)...)
346 muladd(x::Number, y::Number, z::Number) = muladd(promote(x,y,z)...)
347
348 ==(x::Number, y::Number) = (==)(promote(x,y)...)
349 <( x::Real, y::Real) = (< )(promote(x,y)...)
350 <=(x::Real, y::Real) = (<=)(promote(x,y)...)
351
352 rem(x::Real, y::Real) = rem(promote(x,y)...)
353 mod(x::Real, y::Real) = mod(promote(x,y)...)
354
355 mod1(x::Real, y::Real) = mod1(promote(x,y)...)
356 fld1(x::Real, y::Real) = fld1(promote(x,y)...)
357
358 max(x::Real, y::Real) = max(promote(x,y)...)
359 min(x::Real, y::Real) = min(promote(x,y)...)
360 minmax(x::Real, y::Real) = minmax(promote(x, y)...)
361
362 if isdefined(Core, :Compiler)
363 const _return_type = Core.Compiler.return_type
364 else
365 _return_type(@nospecialize(f), @nospecialize(t)) = Any
366 end
367
368 """
369 promote_op(f, argtypes...)
370
371 Guess what an appropriate container eltype would be for storing results of
372 `f(::argtypes...)`. The guess is in part based on type inference, so can change any time.
373
374 !!! warning
375 Due to its fragility, use of `promote_op` should be avoided. It is preferable to base
376 the container eltype on the type of the actual elements. Only in the absence of any
377 elements (for an empty result container), it may be unavoidable to call `promote_op`.
378 """
379 promote_op(f, S::Type...) = _return_type(f, Tuple{S...})
380
381 ## catch-alls to prevent infinite recursion when definitions are missing ##
382
383 no_op_err(name, T) = error(name," not defined for ",T)
384 (+)(x::T, y::T) where {T<:Number} = no_op_err("+", T)
385 (*)(x::T, y::T) where {T<:Number} = no_op_err("*", T)
386 (-)(x::T, y::T) where {T<:Number} = no_op_err("-", T)
387 (/)(x::T, y::T) where {T<:Number} = no_op_err("/", T)
388 (^)(x::T, y::T) where {T<:Number} = no_op_err("^", T)
389
390 fma(x::T, y::T, z::T) where {T<:Number} = no_op_err("fma", T)
391 fma(x::Integer, y::Integer, z::Integer) = x*y+z
392 muladd(x::T, y::T, z::T) where {T<:Number} = x*y+z
393
394 (&)(x::T, y::T) where {T<:Integer} = no_op_err("&", T)
395 (|)(x::T, y::T) where {T<:Integer} = no_op_err("|", T)
396 xor(x::T, y::T) where {T<:Integer} = no_op_err("xor", T)
397
398 53 (6 %) 53 (6 %)
53 (6 %) samples spent in ==
4 (8 %) (ex.), 4 (8 %) (incl.) when called from iszero line 40
9 (17 %) (ex.), 9 (17 %) (incl.) when called from < line 334
40 (75 %) (ex.), 40 (75 %) (incl.) when called from _eq line 288
(==)(x::T, y::T) where {T<:Number} = x === y
399 (< )(x::T, y::T) where {T<:Real} = no_op_err("<" , T)
400 (<=)(x::T, y::T) where {T<:Real} = no_op_err("<=", T)
401
402 rem(x::T, y::T) where {T<:Real} = no_op_err("rem", T)
403 mod(x::T, y::T) where {T<:Real} = no_op_err("mod", T)
404
405 min(x::Real) = x
406 max(x::Real) = x
407 minmax(x::Real) = (x, x)
408
409 max(x::T, y::T) where {T<:Real} = ifelse(y < x, x, y)
410 min(x::T, y::T) where {T<:Real} = ifelse(y < x, y, x)
411 minmax(x::T, y::T) where {T<:Real} = y < x ? (y, x) : (x, y)
412
413 flipsign(x::T, y::T) where {T<:Signed} = no_op_err("flipsign", T)