Report index
StatProfilerHTML.jl report
Generated on Mon, 01 Apr 2024 21:01:18
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 Return the closest common ancestor of types `T` and `S`, i.e. the narrowest type from which
9 they both inherit. Recurses on additional varargs.
10
11 # Examples
12 ```jldoctest
13 julia> typejoin(Int, Float64)
14 Real
15
16 julia> typejoin(Int, Float64, ComplexF32)
17 Number
18 ```
19 """
20 typejoin() = Bottom
21 typejoin(@nospecialize(t)) = t
22 typejoin(@nospecialize(t), ts...) = (@_foldable_meta; typejoin(t, typejoin(ts...)))
23 function typejoin(@nospecialize(a), @nospecialize(b))
24 @_foldable_meta
25 if isa(a, TypeVar)
26 return typejoin(a.ub, b)
27 elseif isa(b, TypeVar)
28 return typejoin(a, b.ub)
29 elseif a <: b
30 return b
31 elseif b <: a
32 return a
33 elseif isa(a, UnionAll)
34 return UnionAll(a.var, typejoin(a.body, b))
35 elseif isa(b, UnionAll)
36 return UnionAll(b.var, typejoin(a, b.body))
37 elseif isa(a, Union)
38 return typejoin(typejoin(a.a, a.b), b)
39 elseif isa(b, Union)
40 return typejoin(a, typejoin(b.a, b.b))
41 end
42 # a and b are DataTypes
43 # We have to hide Constant info from inference, see #44390
44 a, b = inferencebarrier(a)::DataType, inferencebarrier(b)::DataType
45 if a <: Tuple
46 if !(b <: Tuple)
47 return Any
48 end
49 ap, bp = a.parameters, b.parameters
50 lar = length(ap)
51 lbr = length(bp)
52 if lar == 0
53 return Tuple{Vararg{tailjoin(bp, 1)}}
54 end
55 if lbr == 0
56 return Tuple{Vararg{tailjoin(ap, 1)}}
57 end
58 laf, afixed = full_va_len(ap)
59 lbf, bfixed = full_va_len(bp)
60 if laf < lbf
61 if isvarargtype(ap[lar]) && !afixed
62 c = Vector{Any}(undef, laf)
63 c[laf] = Vararg{typejoin(unwrapva(ap[lar]), tailjoin(bp, laf))}
64 n = laf-1
65 else
66 c = Vector{Any}(undef, laf+1)
67 c[laf+1] = Vararg{tailjoin(bp, laf+1)}
68 n = laf
69 end
70 elseif lbf < laf
71 if isvarargtype(bp[lbr]) && !bfixed
72 c = Vector{Any}(undef, lbf)
73 c[lbf] = Vararg{typejoin(unwrapva(bp[lbr]), tailjoin(ap, lbf))}
74 n = lbf-1
75 else
76 c = Vector{Any}(undef, lbf+1)
77 c[lbf+1] = Vararg{tailjoin(ap, lbf+1)}
78 n = lbf
79 end
80 else
81 c = Vector{Any}(undef, laf)
82 n = laf
83 end
84 for i = 1:n
85 ai = ap[min(i,lar)]; bi = bp[min(i,lbr)]
86 ci = typejoin(unwrapva(ai), unwrapva(bi))
87 c[i] = i == length(c) && (isvarargtype(ai) || isvarargtype(bi)) ? Vararg{ci} : ci
88 end
89 return Tuple{c...}
90 elseif b <: Tuple
91 return Any
92 end
93 while b !== Any
94 if a <: b.name.wrapper
95 while a.name !== b.name
96 a = supertype(a)::DataType
97 end
98 if a.name === Type.body.name
99 ap = a.parameters[1]
100 bp = b.parameters[1]
101 if ((isa(ap,TypeVar) && ap.lb === Bottom && ap.ub === Any) ||
102 (isa(bp,TypeVar) && bp.lb === Bottom && bp.ub === Any))
103 # handle special Type{T} supertype
104 return Type
105 end
106 end
107 aprimary = a.name.wrapper
108 # join on parameters
109 n = length(a.parameters)
110 if n == 0
111 return aprimary
112 end
113 vars = []
114 for i = 1:n
115 ai, bi = a.parameters[i], b.parameters[i]
116 if ai === bi || (isa(ai,Type) && isa(bi,Type) && ai <: bi && bi <: ai)
117 aprimary = aprimary{ai}
118 else
119 aprimary = aprimary::UnionAll
120 # pushfirst!(vars, aprimary.var)
121 _growbeg!(vars, 1)
122 arrayset(false, vars, aprimary.var, 1)
123 aprimary = aprimary.body
124 end
125 end
126 for v in vars
127 aprimary = UnionAll(v, aprimary)
128 end
129 return aprimary
130 end
131 b = supertype(b)::DataType
132 end
133 return Any
134 end
135
136 # return an upper-bound on type `a` with type `b` removed
137 # such that `return <: a` && `Union{return, b} == Union{a, b}`
138 # WARNING: this is wrong for some objects for which subtyping is broken
139 # (Core.Compiler.isnotbrokensubtype), use only simple types for `b`
140 function typesplit(@nospecialize(a), @nospecialize(b))
141 @_foldable_meta
142 if a <: b
143 return Bottom
144 end
145 if isa(a, Union)
146 return Union{typesplit(a.a, b),
147 typesplit(a.b, b)}
148 end
149 return a
150 end
151
152
153 """
154 promote_typejoin(T, S)
155
156 Compute a type that contains both `T` and `S`, which could be
157 either a parent of both types, or a `Union` if appropriate.
158 Falls back to [`typejoin`](@ref).
159
160 See instead [`promote`](@ref), [`promote_type`](@ref).
161
162 # Examples
163 ```jldoctest
164 julia> Base.promote_typejoin(Int, Float64)
165 Real
166
167 julia> Base.promote_type(Int, Float64)
168 Float64
169 ```
170 """
171 function promote_typejoin(@nospecialize(a), @nospecialize(b))
172 c = typejoin(_promote_typesubtract(a), _promote_typesubtract(b))
173 return Union{a, b, c}::Type
174 end
175 _promote_typesubtract(@nospecialize(a)) =
176 a === Any ? a :
177 a >: Union{Nothing, Missing} ? typesplit(a, Union{Nothing, Missing}) :
178 a >: Nothing ? typesplit(a, Nothing) :
179 a >: Missing ? typesplit(a, Missing) :
180 a
181
182 function promote_typejoin_union(::Type{T}) where T
183 if T === Union{}
184 return Union{}
185 elseif T isa UnionAll
186 return Any # TODO: compute more precise bounds
187 elseif T isa Union
188 return promote_typejoin(promote_typejoin_union(T.a), promote_typejoin_union(T.b))
189 elseif T isa DataType
190 T <: Tuple && return typejoin_union_tuple(T)
191 return T
192 else
193 error("unreachable") # not a type??
194 end
195 end
196
197 function typejoin_union_tuple(T::DataType)
198 @_foldable_meta
199 u = Base.unwrap_unionall(T)
200 p = (u::DataType).parameters
201 lr = length(p)::Int
202 if lr == 0
203 return Tuple{}
204 end
205 c = Vector{Any}(undef, lr)
206 for i = 1:lr
207 pi = p[i]
208 U = Core.Compiler.unwrapva(pi)
209 if U === Union{}
210 ci = Union{}
211 elseif U isa Union
212 ci = typejoin(U.a, U.b)
213 elseif U isa UnionAll
214 return Any # TODO: compute more precise bounds
215 else
216 ci = promote_typejoin_union(U)
217 end
218 if i == lr && Core.Compiler.isvarargtype(pi)
219 c[i] = isdefined(pi, :N) ? Vararg{ci, pi.N} : Vararg{ci}
220 else
221 c[i] = ci
222 end
223 end
224 return Base.rewrap_unionall(Tuple{c...}, T)
225 end
226
227 # Returns length, isfixed
228 function full_va_len(p::Core.SimpleVector)
229 isempty(p) && return 0, true
230 last = p[end]
231 if isvarargtype(last)
232 if isdefined(last, :N)
233 N = last.N
234 isa(N, Int) && return length(p) + N - 1, true
235 end
236 return length(p), false
237 end
238 return length(p), true
239 end
240
241 # reduce typejoin over A[i:end]
242 function tailjoin(A, i)
243 if i > length(A)
244 return unwrapva(A[end])
245 end
246 t = Bottom
247 for j = i:length(A)
248 t = typejoin(t, unwrapva(A[j]))
249 end
250 return t
251 end
252
253 ## promotion mechanism ##
254
255 """
256 promote_type(type1, type2, ...)
257
258 Promotion refers to converting values of mixed types to a single common type.
259 `promote_type` represents the default promotion behavior in Julia when
260 operators (usually mathematical) are given arguments of differing types.
261 `promote_type` generally tries to return a type which can at least approximate
262 most values of either input type without excessively widening. Some loss is
263 tolerated; for example, `promote_type(Int64, Float64)` returns
264 [`Float64`](@ref) even though strictly, not all [`Int64`](@ref) values can be
265 represented exactly as `Float64` values.
266
267 See also: [`promote`](@ref), [`promote_typejoin`](@ref), [`promote_rule`](@ref).
268
269 # Examples
270 ```jldoctest
271 julia> promote_type(Int64, Float64)
272 Float64
273
274 julia> promote_type(Int32, Int64)
275 Int64
276
277 julia> promote_type(Float32, BigInt)
278 BigFloat
279
280 julia> promote_type(Int16, Float16)
281 Float16
282
283 julia> promote_type(Int64, Float16)
284 Float16
285
286 julia> promote_type(Int8, UInt16)
287 UInt16
288 ```
289
290 !!! warning "Don't overload this directly"
291 To overload promotion for your own types you should overload [`promote_rule`](@ref).
292 `promote_type` calls `promote_rule` internally to determine the type.
293 Overloading `promote_type` directly can cause ambiguity errors.
294 """
295 function promote_type end
296
297 promote_type() = Bottom
298 promote_type(T) = T
299 promote_type(T, S, U, V...) = (@inline; promote_type(T, promote_type(S, U, V...)))
300
301 promote_type(::Type{Bottom}, ::Type{Bottom}) = Bottom
302 promote_type(::Type{T}, ::Type{T}) where {T} = T
303 promote_type(::Type{T}, ::Type{Bottom}) where {T} = T
304 promote_type(::Type{Bottom}, ::Type{T}) where {T} = T
305
306 function promote_type(::Type{T}, ::Type{S}) where {T,S}
307 @inline
308 # Try promote_rule in both orders. Typically only one is defined,
309 # and there is a fallback returning Bottom below, so the common case is
310 # promote_type(T, S) =>
311 # promote_result(T, S, result, Bottom) =>
312 # typejoin(result, Bottom) => result
313 promote_result(T, S, promote_rule(T,S), promote_rule(S,T))
314 end
315
316 """
317 promote_rule(type1, type2)
318
319 Specifies what type should be used by [`promote`](@ref) when given values of types `type1` and
320 `type2`. This function should not be called directly, but should have definitions added to
321 it for new types as appropriate.
322 """
323 function promote_rule end
324
325 promote_rule(::Type, ::Type) = Bottom
326 # Define some methods to avoid needing to enumerate unrelated possibilities when presented
327 # with Type{<:T}, and return a value in general accordance with the result given by promote_type
328 promote_rule(::Type{Bottom}, slurp...) = Bottom
329 promote_rule(::Type{Bottom}, ::Type{Bottom}, slurp...) = Bottom # not strictly necessary, since the next method would match unambiguously anyways
330 promote_rule(::Type{Bottom}, ::Type{T}, slurp...) where {T} = T
331 promote_rule(::Type{T}, ::Type{Bottom}, slurp...) where {T} = T
332
333 promote_result(::Type,::Type,::Type{T},::Type{S}) where {T,S} = (@inline; promote_type(T,S))
334 # If no promote_rule is defined, both directions give Bottom. In that
335 # case use typejoin on the original types instead.
336 promote_result(::Type{T},::Type{S},::Type{Bottom},::Type{Bottom}) where {T,S} = (@inline; typejoin(T, S))
337
338 """
339 promote(xs...)
340
341 Convert all arguments to a common type, and return them all (as a tuple).
342 If no arguments can be converted, an error is raised.
343
344 See also: [`promote_type`](@ref), [`promote_rule`](@ref).
345
346 # Examples
347 ```jldoctest
348 julia> promote(Int8(1), Float16(4.5), Float32(4.1))
349 (1.0f0, 4.5f0, 4.1f0)
350
351 julia> promote_type(Int8, Float16, Float32)
352 Float32
353
354 julia> reduce(Base.promote_typejoin, (Int8, Float16, Float32))
355 Real
356
357 julia> promote(1, "x")
358 ERROR: promotion of types Int64 and String failed to change any arguments
359 [...]
360
361 julia> promote_type(Int, String)
362 Any
363 ```
364 """
365 function promote end
366
367 function _promote(x::T, y::S) where {T,S}
368 @inline
369 R = promote_type(T, S)
370 return (convert(R, x), convert(R, y))
371 end
372 promote_typeof(x) = typeof(x)
373 promote_typeof(x, xs...) = (@inline; promote_type(typeof(x), promote_typeof(xs...)))
374 function _promote(x, y, z)
375 @inline
376 R = promote_typeof(x, y, z)
377 return (convert(R, x), convert(R, y), convert(R, z))
378 end
379 function _promote(x, y, zs...)
380 @inline
381 R = promote_typeof(x, y, zs...)
382 return (convert(R, x), convert(R, y), convert(Tuple{Vararg{R}}, zs)...)
383 end
384 # TODO: promote(x::T, ys::T...) where {T} here to catch all circularities?
385
386 ## promotions in arithmetic, etc. ##
387
388 promote() = ()
389 promote(x) = (x,)
390
391 function promote(x, y)
392 @inline
393 px, py = _promote(x, y)
394 not_sametype((x,y), (px,py))
395 px, py
396 end
397 function promote(x, y, z)
398 @inline
399 px, py, pz = _promote(x, y, z)
400 not_sametype((x,y,z), (px,py,pz))
401 px, py, pz
402 end
403 function promote(x, y, z, a...)
404 p = _promote(x, y, z, a...)
405 not_sametype((x, y, z, a...), p)
406 p
407 end
408
409 promote(x::T, y::T, zs::T...) where {T} = (x, y, zs...)
410
411 not_sametype(x::T, y::T) where {T} = sametype_error(x)
412
413 not_sametype(x, y) = nothing
414
415 function sametype_error(input)
416 @noinline
417 error("promotion of types ",
418 join(map(x->string(typeof(x)), input), ", ", " and "),
419 " failed to change any arguments")
420 end
421
422 +(x::Number, y::Number) = +(promote(x,y)...)
423 *(x::Number, y::Number) = *(promote(x,y)...)
424 -(x::Number, y::Number) = -(promote(x,y)...)
425 /(x::Number, y::Number) = /(promote(x,y)...)
426
427 """
428 ^(x, y)
429
430 Exponentiation operator. If `x` is a matrix, computes matrix exponentiation.
431
432 If `y` is an `Int` literal (e.g. `2` in `x^2` or `-3` in `x^-3`), the Julia code
433 `x^y` is transformed by the compiler to `Base.literal_pow(^, x, Val(y))`, to
434 enable compile-time specialization on the value of the exponent.
435 (As a default fallback we have `Base.literal_pow(^, x, Val(y)) = ^(x,y)`,
436 where usually `^ == Base.^` unless `^` has been defined in the calling
437 namespace.) If `y` is a negative integer literal, then `Base.literal_pow`
438 transforms the operation to `inv(x)^-y` by default, where `-y` is positive.
439
440 # Examples
441 ```jldoctest
442 julia> 3^5
443 243
444
445 julia> A = [1 2; 3 4]
446 2×2 Matrix{Int64}:
447 1 2
448 3 4
449
450 julia> A^3
451 2×2 Matrix{Int64}:
452 37 54
453 81 118
454 ```
455 """
456 ^(x::Number, y::Number) = ^(promote(x,y)...)
457
458 fma(x::Number, y::Number, z::Number) = fma(promote(x,y,z)...)
459 muladd(x::Number, y::Number, z::Number) = muladd(promote(x,y,z)...)
460
461 ==(x::Number, y::Number) = (==)(promote(x,y)...)
462 <( x::Real, y::Real) = (< )(promote(x,y)...)
463 <=(x::Real, y::Real) = (<=)(promote(x,y)...)
464
465 rem(x::Real, y::Real) = rem(promote(x,y)...)
466 mod(x::Real, y::Real) = mod(promote(x,y)...)
467
468 mod1(x::Real, y::Real) = mod1(promote(x,y)...)
469 fld1(x::Real, y::Real) = fld1(promote(x,y)...)
470
471 max(x::Real, y::Real) = max(promote(x,y)...)
472 min(x::Real, y::Real) = min(promote(x,y)...)
473 minmax(x::Real, y::Real) = minmax(promote(x, y)...)
474
475 if isdefined(Core, :Compiler)
476 const _return_type = Core.Compiler.return_type
477 else
478 _return_type(@nospecialize(f), @nospecialize(t)) = Any
479 end
480
481 function TupleOrBottom(tt...)
482 any(p -> p === Union{}, tt) && return Union{}
483 return Tuple{tt...}
484 end
485
486 """
487 promote_op(f, argtypes...)
488
489 Guess what an appropriate container eltype would be for storing results of
490 `f(::argtypes...)`. The guess is in part based on type inference, so can change any time.
491
492 !!! warning
493 Due to its fragility, use of `promote_op` should be avoided. It is preferable to base
494 the container eltype on the type of the actual elements. Only in the absence of any
495 elements (for an empty result container), it may be unavoidable to call `promote_op`.
496 """
497 function promote_op(f, S::Type...)
498 argT = TupleOrBottom(S...)
499 argT === Union{} && return Union{}
500 return _return_type(f, argT)
501 end
502
503
504 ## catch-alls to prevent infinite recursion when definitions are missing ##
505
506 no_op_err(name, T) = error(name," not defined for ",T)
507 (+)(x::T, y::T) where {T<:Number} = no_op_err("+", T)
508 (*)(x::T, y::T) where {T<:Number} = no_op_err("*", T)
509 (-)(x::T, y::T) where {T<:Number} = no_op_err("-", T)
510 (/)(x::T, y::T) where {T<:Number} = no_op_err("/", T)
511 (^)(x::T, y::T) where {T<:Number} = no_op_err("^", T)
512
513 fma(x::T, y::T, z::T) where {T<:Number} = no_op_err("fma", T)
514 fma(x::Integer, y::Integer, z::Integer) = x*y+z
515 muladd(x::T, y::T, z::T) where {T<:Number} = x*y+z
516
517 (&)(x::T, y::T) where {T<:Integer} = no_op_err("&", T)
518 (|)(x::T, y::T) where {T<:Integer} = no_op_err("|", T)
519 xor(x::T, y::T) where {T<:Integer} = no_op_err("xor", T)
520
521 1 (2 %) 1 (2 %)
1 (2 %) samples spent in ==
1 (100 %) (ex.), 1 (100 %) (incl.) when called from iterate line 901
(==)(x::T, y::T) where {T<:Number} = x === y
522 (< )(x::T, y::T) where {T<:Real} = no_op_err("<" , T)
523 (<=)(x::T, y::T) where {T<:Real} = (x == y) | (x < y)
524
525 rem(x::T, y::T) where {T<:Real} = no_op_err("rem", T)
526 mod(x::T, y::T) where {T<:Real} = no_op_err("mod", T)
527
528 min(x::Real) = x
529 max(x::Real) = x
530 minmax(x::Real) = (x, x)
531
532 max(x::T, y::T) where {T<:Real} = ifelse(y < x, x, y)
533 min(x::T, y::T) where {T<:Real} = ifelse(y < x, y, x)
534 minmax(x::T, y::T) where {T<:Real} = y < x ? (y, x) : (x, y)
535
536 flipsign(x::T, y::T) where {T<:Signed} = no_op_err("flipsign", T)