StatProfilerHTML.jl report
Generated on tor 10 okt 2019 11:38:33
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 aprimary = aprimary.body
109 end
110 end
111 for v in vars
112 aprimary = UnionAll(v, aprimary)
113 end
114 return aprimary
115 end
116 b = supertype(b)
117 end
118 return Any
119 end
120
121 """
122 promote_typejoin(T, S)
123
124 Compute a type that contains both `T` and `S`, which could be
125 either a parent of both types, or a `Union` if appropriate.
126 Falls back to [`typejoin`](@ref).
127 """
128 promote_typejoin(@nospecialize(a), @nospecialize(b)) = _promote_typejoin(a, b)::Type
129 _promote_typejoin(@nospecialize(a), @nospecialize(b)) = typejoin(a, b)
130 _promote_typejoin(::Type{Nothing}, ::Type{T}) where {T} =
131 isconcretetype(T) || T === Union{} ? Union{T, Nothing} : Any
132 _promote_typejoin(::Type{T}, ::Type{Nothing}) where {T} =
133 isconcretetype(T) || T === Union{} ? Union{T, Nothing} : Any
134 _promote_typejoin(::Type{Missing}, ::Type{T}) where {T} =
135 isconcretetype(T) || T === Union{} ? Union{T, Missing} : Any
136 _promote_typejoin(::Type{T}, ::Type{Missing}) where {T} =
137 isconcretetype(T) || T === Union{} ? Union{T, Missing} : Any
138 _promote_typejoin(::Type{Nothing}, ::Type{Missing}) = Union{Nothing, Missing}
139 _promote_typejoin(::Type{Missing}, ::Type{Nothing}) = Union{Nothing, Missing}
140 _promote_typejoin(::Type{Nothing}, ::Type{Nothing}) = Nothing
141 _promote_typejoin(::Type{Missing}, ::Type{Missing}) = Missing
142
143 # Returns length, isfixed
144 function full_va_len(p)
145 isempty(p) && return 0, true
146 last = p[end]
147 if isvarargtype(last)
148 N = unwrap_unionall(last).parameters[2]
149 if isa(N, Integer)
150 return (length(p) + N - 1)::Int, true
151 end
152 return length(p)::Int, false
153 end
154 return length(p)::Int, true
155 end
156
157 # reduce typejoin over A[i:end]
158 function tailjoin(A, i)
159 if i > length(A)
160 return unwrapva(A[end])
161 end
162 t = Bottom
163 for j = i:length(A)
164 t = typejoin(t, unwrapva(A[j]))
165 end
166 return t
167 end
168
169 ## promotion mechanism ##
170
171 """
172 promote_type(type1, type2)
173
174 Promotion refers to converting values of mixed types to a single common type.
175 `promote_type` represents the default promotion behavior in Julia when
176 operators (usually mathematical) are given arguments of differing types.
177 `promote_type` generally tries to return a type which can at least approximate
178 most values of either input type without excessively widening. Some loss is
179 tolerated; for example, `promote_type(Int64, Float64)` returns
180 [`Float64`](@ref) even though strictly, not all [`Int64`](@ref) values can be
181 represented exactly as `Float64` values.
182
183 ```jldoctest
184 julia> promote_type(Int64, Float64)
185 Float64
186
187 julia> promote_type(Int32, Int64)
188 Int64
189
190 julia> promote_type(Float32, BigInt)
191 BigFloat
192
193 julia> promote_type(Int16, Float16)
194 Float16
195
196 julia> promote_type(Int64, Float16)
197 Float16
198
199 julia> promote_type(Int8, UInt16)
200 UInt16
201 ```
202 """
203 function promote_type end
204
205 promote_type() = Bottom
206 promote_type(T) = T
207 promote_type(T, S, U, V...) = (@_inline_meta; promote_type(T, promote_type(S, U, V...)))
208
209 promote_type(::Type{Bottom}, ::Type{Bottom}) = Bottom
210 promote_type(::Type{T}, ::Type{T}) where {T} = T
211 promote_type(::Type{T}, ::Type{Bottom}) where {T} = T
212 promote_type(::Type{Bottom}, ::Type{T}) where {T} = T
213
214 function promote_type(::Type{T}, ::Type{S}) where {T,S}
215 @_inline_meta
216 # Try promote_rule in both orders. Typically only one is defined,
217 # and there is a fallback returning Bottom below, so the common case is
218 # promote_type(T, S) =>
219 # promote_result(T, S, result, Bottom) =>
220 # typejoin(result, Bottom) => result
221 promote_result(T, S, promote_rule(T,S), promote_rule(S,T))
222 end
223
224 """
225 promote_rule(type1, type2)
226
227 Specifies what type should be used by [`promote`](@ref) when given values of types `type1` and
228 `type2`. This function should not be called directly, but should have definitions added to
229 it for new types as appropriate.
230 """
231 function promote_rule end
232
233 promote_rule(::Type{<:Any}, ::Type{<:Any}) = Bottom
234 # To fix ambiguities
235 promote_rule(::Type{Any}, ::Type{<:Any}) = Any
236 promote_rule(::Type{<:Any}, ::Type{Any}) = Any
237 promote_rule(::Type{Any}, ::Type{Any}) = Any
238
239 promote_result(::Type{<:Any},::Type{<:Any},::Type{T},::Type{S}) where {T,S} = (@_inline_meta; promote_type(T,S))
240 # If no promote_rule is defined, both directions give Bottom. In that
241 # case use typejoin on the original types instead.
242 promote_result(::Type{T},::Type{S},::Type{Bottom},::Type{Bottom}) where {T,S} = (@_inline_meta; typejoin(T, S))
243
244 """
245 promote(xs...)
246
247 Convert all arguments to a common type, and return them all (as a tuple).
248 If no arguments can be converted, an error is raised.
249
250 # Examples
251 ```jldoctest
252 julia> promote(Int8(1), Float16(4.5), Float32(4.1))
253 (1.0f0, 4.5f0, 4.1f0)
254 ```
255 """
256 function promote end
257
258 function _promote(x::T, y::S) where {T,S}
259 @_inline_meta
260 R = promote_type(T, S)
261 return (convert(R, x), convert(R, y))
262 end
263 promote_typeof(x) = typeof(x)
264 promote_typeof(x, xs...) = (@_inline_meta; promote_type(typeof(x), promote_typeof(xs...)))
265 function _promote(x, y, z)
266 @_inline_meta
267 R = promote_typeof(x, y, z)
268 return (convert(R, x), convert(R, y), convert(R, z))
269 end
270 function _promote(x, y, zs...)
271 @_inline_meta
272 R = promote_typeof(x, y, zs...)
273 return (convert(R, x), convert(R, y), convert(Tuple{Vararg{R}}, zs)...)
274 end
275 # TODO: promote(x::T, ys::T...) where {T} here to catch all circularities?
276
277 ## promotions in arithmetic, etc. ##
278
279 promote() = ()
280 promote(x) = (x,)
281
282 function promote(x, y)
283 @_inline_meta
284 px, py = _promote(x, y)
285 not_sametype((x,y), (px,py))
286 px, py
287 end
288 function promote(x, y, z)
289 @_inline_meta
290 px, py, pz = _promote(x, y, z)
291 not_sametype((x,y,z), (px,py,pz))
292 px, py, pz
293 end
294 function promote(x, y, z, a...)
295 p = _promote(x, y, z, a...)
296 not_sametype((x, y, z, a...), p)
297 p
298 end
299
300 promote(x::T, y::T, zs::T...) where {T} = (x, y, zs...)
301
302 not_sametype(x::T, y::T) where {T} = sametype_error(x)
303
304 not_sametype(x, y) = nothing
305
306 function sametype_error(input)
307 @_noinline_meta
308 error("promotion of types ",
309 join(map(x->string(typeof(x)), input), ", ", " and "),
310 " failed to change any arguments")
311 end
312
313 +(x::Number, y::Number) = +(promote(x,y)...)
314 *(x::Number, y::Number) = *(promote(x,y)...)
315 -(x::Number, y::Number) = -(promote(x,y)...)
316 /(x::Number, y::Number) = /(promote(x,y)...)
317
318 """
319 ^(x, y)
320
321 Exponentiation operator. If `x` is a matrix, computes matrix exponentiation.
322
323 If `y` is an `Int` literal (e.g. `2` in `x^2` or `-3` in `x^-3`), the Julia code
324 `x^y` is transformed by the compiler to `Base.literal_pow(^, x, Val(y))`, to
325 enable compile-time specialization on the value of the exponent.
326 (As a default fallback we have `Base.literal_pow(^, x, Val(y)) = ^(x,y)`,
327 where usually `^ == Base.^` unless `^` has been defined in the calling
328 namespace.)
329
330 ```jldoctest
331 julia> 3^5
332 243
333
334 julia> A = [1 2; 3 4]
335 2×2 Array{Int64,2}:
336 1 2
337 3 4
338
339 julia> A^3
340 2×2 Array{Int64,2}:
341 37 54
342 81 118
343 ```
344 """
345 ^(x::Number, y::Number) = ^(promote(x,y)...)
346
347 fma(x::Number, y::Number, z::Number) = fma(promote(x,y,z)...)
348 muladd(x::Number, y::Number, z::Number) = muladd(promote(x,y,z)...)
349
350 ==(x::Number, y::Number) = (==)(promote(x,y)...)
351 <( x::Real, y::Real) = (< )(promote(x,y)...)
352 <=(x::Real, y::Real) = (<=)(promote(x,y)...)
353
354 div(x::Real, y::Real) = div(promote(x,y)...)
355 fld(x::Real, y::Real) = fld(promote(x,y)...)
356 cld(x::Real, y::Real) = cld(promote(x,y)...)
357 rem(x::Real, y::Real) = rem(promote(x,y)...)
358 mod(x::Real, y::Real) = mod(promote(x,y)...)
359
360 mod1(x::Real, y::Real) = mod1(promote(x,y)...)
361 fld1(x::Real, y::Real) = fld1(promote(x,y)...)
362
363 max(x::Real, y::Real) = max(promote(x,y)...)
364 min(x::Real, y::Real) = min(promote(x,y)...)
365 minmax(x::Real, y::Real) = minmax(promote(x, y)...)
366
367 # "Promotion" that takes a function into account and tries to preserve
368 # non-concrete types. These are meant to be used mainly by elementwise
369 # operations, so it is advised against overriding them
370 _default_type(T::Type) = T
371
372 if isdefined(Core, :Compiler)
373 const _return_type = Core.Compiler.return_type
374 else
375 _return_type(@nospecialize(f), @nospecialize(t)) = Any
376 end
377
378 """
379 promote_op(f, argtypes...)
380
381 Guess what an appropriate container eltype would be for storing results of
382 `f(::argtypes...)`. The guess is in part based on type inference, so can change any time.
383
384 !!! warning
385 In pathological cases, the type returned by `promote_op(f, argtypes...)` may not even
386 be a supertype of the return value of `f(::argtypes...)`. Therefore, `promote_op`
387 should _not_ be used e.g. in the preallocation of an output array.
388
389 !!! warning
390 Due to its fragility, use of `promote_op` should be avoided. It is preferable to base
391 the container eltype on the type of the actual elements. Only in the absence of any
392 elements (for an empty result container), it may be unavoidable to call `promote_op`.
393 """
394 promote_op(::Any...) = Any
395 function promote_op(f, ::Type{S}) where S
396 TT = Tuple{_default_type(S)}
397 T = _return_type(f, TT)
398 isdispatchtuple(Tuple{S}) && return isdispatchtuple(Tuple{T}) ? T : Any
399 return typejoin(S, T)
400 end
401 function promote_op(f, ::Type{R}, ::Type{S}) where {R,S}
402 TT = Tuple{_default_type(R), _default_type(S)}
403 T = _return_type(f, TT)
404 isdispatchtuple(Tuple{R}) && isdispatchtuple(Tuple{S}) && return isdispatchtuple(Tuple{T}) ? T : Any
405 return typejoin(R, S, T)
406 end
407
408 ## catch-alls to prevent infinite recursion when definitions are missing ##
409
410 no_op_err(name, T) = error(name," not defined for ",T)
411 (+)(x::T, y::T) where {T<:Number} = no_op_err("+", T)
412 (*)(x::T, y::T) where {T<:Number} = no_op_err("*", T)
413 (-)(x::T, y::T) where {T<:Number} = no_op_err("-", T)
414 (/)(x::T, y::T) where {T<:Number} = no_op_err("/", T)
415 (^)(x::T, y::T) where {T<:Number} = no_op_err("^", T)
416
417 fma(x::T, y::T, z::T) where {T<:Number} = no_op_err("fma", T)
418 fma(x::Integer, y::Integer, z::Integer) = x*y+z
419 muladd(x::T, y::T, z::T) where {T<:Number} = x*y+z
420
421 (&)(x::T, y::T) where {T<:Integer} = no_op_err("&", T)
422 (|)(x::T, y::T) where {T<:Integer} = no_op_err("|", T)
423 xor(x::T, y::T) where {T<:Integer} = no_op_err("xor", T)
424
425 1 (2.38%) 1 (2.38%)
1 (2.38%) samples spent in ==
1 (100.00%) (ex.), 1 (100.00%) (incl.) when called from == line 432
(==)(x::T, y::T) where {T<:Number} = x === y
426 (< )(x::T, y::T) where {T<:Real} = no_op_err("<" , T)
427 (<=)(x::T, y::T) where {T<:Real} = no_op_err("<=", T)
428
429 rem(x::T, y::T) where {T<:Real} = no_op_err("rem", T)
430 mod(x::T, y::T) where {T<:Real} = no_op_err("mod", T)
431
432 min(x::Real) = x
433 max(x::Real) = x
434 minmax(x::Real) = (x, x)
435
436 max(x::T, y::T) where {T<:Real} = ifelse(y < x, x, y)
437 min(x::T, y::T) where {T<:Real} = ifelse(y < x, y, x)
438 minmax(x::T, y::T) where {T<:Real} = y < x ? (y, x) : (x, y)
439
440 flipsign(x::T, y::T) where {T<:Signed} = no_op_err("flipsign", T)