https://github.com/JuliaLang/julia
Tip revision: b66292bcb3a4db392991649a3cc6d3f2a9a66eaa authored by Jacob Quinn on 29 July 2023, 00:16:42 UTC
Trying ideas`
Trying ideas`
Tip revision: b66292b
promotion.jl
# This file is a part of Julia. License is MIT: https://julialang.org/license
## type join (closest common ancestor, or least upper bound) ##
"""
typejoin(T, S, ...)
Return the closest common ancestor of types `T` and `S`, i.e. the narrowest type from which
they both inherit. Recurses on additional varargs.
# Examples
```jldoctest
julia> typejoin(Int, Float64)
Real
julia> typejoin(Int, Float64, ComplexF32)
Number
```
"""
typejoin() = Bottom
typejoin(@nospecialize(t)) = t
typejoin(@nospecialize(t), ts...) = (@_foldable_meta; typejoin(t, typejoin(ts...)))
function typejoin(@nospecialize(a), @nospecialize(b))
@_foldable_meta
if isa(a, TypeVar)
return typejoin(a.ub, b)
elseif isa(b, TypeVar)
return typejoin(a, b.ub)
elseif a <: b
return b
elseif b <: a
return a
elseif isa(a, UnionAll)
return UnionAll(a.var, typejoin(a.body, b))
elseif isa(b, UnionAll)
return UnionAll(b.var, typejoin(a, b.body))
elseif isa(a, Union)
return typejoin(typejoin(a.a, a.b), b)
elseif isa(b, Union)
return typejoin(a, typejoin(b.a, b.b))
end
# a and b are DataTypes
# We have to hide Constant info from inference, see #44390
a, b = inferencebarrier(a)::DataType, inferencebarrier(b)::DataType
if a <: Tuple
if !(b <: Tuple)
return Any
end
ap, bp = a.parameters, b.parameters
lar = length(ap)
lbr = length(bp)
if lar == 0
return Tuple{Vararg{tailjoin(bp, 1)}}
end
if lbr == 0
return Tuple{Vararg{tailjoin(ap, 1)}}
end
laf, afixed = full_va_len(ap)
lbf, bfixed = full_va_len(bp)
if laf < lbf
if isvarargtype(ap[lar]) && !afixed
c = Vector{Any}(undef, laf)
c[laf] = Vararg{typejoin(unwrapva(ap[lar]), tailjoin(bp, laf))}
n = laf-1
else
c = Vector{Any}(undef, laf+1)
c[laf+1] = Vararg{tailjoin(bp, laf+1)}
n = laf
end
elseif lbf < laf
if isvarargtype(bp[lbr]) && !bfixed
c = Vector{Any}(undef, lbf)
c[lbf] = Vararg{typejoin(unwrapva(bp[lbr]), tailjoin(ap, lbf))}
n = lbf-1
else
c = Vector{Any}(undef, lbf+1)
c[lbf+1] = Vararg{tailjoin(ap, lbf+1)}
n = lbf
end
else
c = Vector{Any}(undef, laf)
n = laf
end
for i = 1:n
ai = ap[min(i,lar)]; bi = bp[min(i,lbr)]
ci = typejoin(unwrapva(ai), unwrapva(bi))
c[i] = i == length(c) && (isvarargtype(ai) || isvarargtype(bi)) ? Vararg{ci} : ci
end
return Tuple{c...}
elseif b <: Tuple
return Any
end
while b !== Any
if a <: b.name.wrapper
while a.name !== b.name
a = supertype(a)::DataType
end
if a.name === Type.body.name
ap = a.parameters[1]
bp = b.parameters[1]
if ((isa(ap,TypeVar) && ap.lb === Bottom && ap.ub === Any) ||
(isa(bp,TypeVar) && bp.lb === Bottom && bp.ub === Any))
# handle special Type{T} supertype
return Type
end
end
aprimary = a.name.wrapper
# join on parameters
n = length(a.parameters)
if n == 0
return aprimary
end
vars = []
for i = 1:n
ai, bi = a.parameters[i], b.parameters[i]
if ai === bi || (isa(ai,Type) && isa(bi,Type) && ai <: bi && bi <: ai)
aprimary = aprimary{ai}
else
aprimary = aprimary::UnionAll
# pushfirst!(vars, aprimary.var)
_growbeg!(vars, 1)
arrayset(false, vars, aprimary.var, 1)
aprimary = aprimary.body
end
end
for v in vars
aprimary = UnionAll(v, aprimary)
end
return aprimary
end
b = supertype(b)::DataType
end
return Any
end
# return an upper-bound on type `a` with type `b` removed
# such that `return <: a` && `Union{return, b} == Union{a, b}`
# WARNING: this is wrong for some objects for which subtyping is broken
# (Core.Compiler.isnotbrokensubtype), use only simple types for `b`
function typesplit(@nospecialize(a), @nospecialize(b))
@_foldable_meta
if a <: b
return Bottom
end
if isa(a, Union)
return Union{typesplit(a.a, b),
typesplit(a.b, b)}
end
return a
end
"""
promote_typejoin(T, S)
Compute a type that contains both `T` and `S`, which could be
either a parent of both types, or a `Union` if appropriate.
Falls back to [`typejoin`](@ref).
See instead [`promote`](@ref), [`promote_type`](@ref).
# Examples
```jldoctest
julia> Base.promote_typejoin(Int, Float64)
Real
julia> Base.promote_type(Int, Float64)
Float64
```
"""
function promote_typejoin(@nospecialize(a), @nospecialize(b))
c = typejoin(_promote_typesubtract(a), _promote_typesubtract(b))
return Union{a, b, c}::Type
end
_promote_typesubtract(@nospecialize(a)) =
a === Any ? a :
a >: Union{Nothing, Missing} ? typesplit(a, Union{Nothing, Missing}) :
a >: Nothing ? typesplit(a, Nothing) :
a >: Missing ? typesplit(a, Missing) :
a
function promote_typejoin_union(::Type{T}) where T
if T === Union{}
return Union{}
elseif T isa UnionAll
return Any # TODO: compute more precise bounds
elseif T isa Union
return promote_typejoin(promote_typejoin_union(T.a), promote_typejoin_union(T.b))
elseif T isa DataType
T <: Tuple && return typejoin_union_tuple(T)
return T
else
error("unreachable") # not a type??
end
end
function typejoin_union_tuple(T::DataType)
@_foldable_meta
u = Base.unwrap_unionall(T)
p = (u::DataType).parameters
lr = length(p)::Int
if lr == 0
return Tuple{}
end
c = Vector{Any}(undef, lr)
for i = 1:lr
pi = p[i]
U = Core.Compiler.unwrapva(pi)
if U === Union{}
ci = Union{}
elseif U isa Union
ci = typejoin(U.a, U.b)
elseif U isa UnionAll
return Any # TODO: compute more precise bounds
else
ci = promote_typejoin_union(U)
end
if i == lr && Core.Compiler.isvarargtype(pi)
c[i] = isdefined(pi, :N) ? Vararg{ci, pi.N} : Vararg{ci}
else
c[i] = ci
end
end
return Base.rewrap_unionall(Tuple{c...}, T)
end
# Returns length, isfixed
function full_va_len(p::Core.SimpleVector)
isempty(p) && return 0, true
last = p[end]
if isvarargtype(last)
if isdefined(last, :N)
N = last.N
isa(N, Int) && return length(p) + N - 1, true
end
return length(p), false
end
return length(p), true
end
# reduce typejoin over A[i:end]
function tailjoin(A, i)
if i > length(A)
return unwrapva(A[end])
end
t = Bottom
for j = i:length(A)
t = typejoin(t, unwrapva(A[j]))
end
return t
end
## promotion mechanism ##
"""
promote_type(type1, type2, ...)
Promotion refers to converting values of mixed types to a single common type.
`promote_type` represents the default promotion behavior in Julia when
operators (usually mathematical) are given arguments of differing types.
`promote_type` generally tries to return a type which can at least approximate
most values of either input type without excessively widening. Some loss is
tolerated; for example, `promote_type(Int64, Float64)` returns
[`Float64`](@ref) even though strictly, not all [`Int64`](@ref) values can be
represented exactly as `Float64` values.
See also: [`promote`](@ref), [`promote_typejoin`](@ref), [`promote_rule`](@ref).
# Examples
```jldoctest
julia> promote_type(Int64, Float64)
Float64
julia> promote_type(Int32, Int64)
Int64
julia> promote_type(Float32, BigInt)
BigFloat
julia> promote_type(Int16, Float16)
Float16
julia> promote_type(Int64, Float16)
Float16
julia> promote_type(Int8, UInt16)
UInt16
```
!!! warning "Don't overload this directly"
To overload promotion for your own types you should overload [`promote_rule`](@ref).
`promote_type` calls `promote_rule` internally to determine the type.
Overloading `promote_type` directly can cause ambiguity errors.
"""
function promote_type end
promote_type() = Bottom
promote_type(T) = T
promote_type(T, S, U, V...) = (@inline; promote_type(T, promote_type(S, U, V...)))
promote_type(::Type{Bottom}, ::Type{Bottom}) = Bottom
promote_type(::Type{T}, ::Type{T}) where {T} = T
promote_type(::Type{T}, ::Type{Bottom}) where {T} = T
promote_type(::Type{Bottom}, ::Type{T}) where {T} = T
function promote_type(::Type{T}, ::Type{S}) where {T,S}
@inline
# Try promote_rule in both orders. Typically only one is defined,
# and there is a fallback returning Bottom below, so the common case is
# promote_type(T, S) =>
# promote_result(T, S, result, Bottom) =>
# typejoin(result, Bottom) => result
promote_result(T, S, promote_rule(T,S), promote_rule(S,T))
end
"""
promote_rule(type1, type2)
Specifies what type should be used by [`promote`](@ref) when given values of types `type1` and
`type2`. This function should not be called directly, but should have definitions added to
it for new types as appropriate.
"""
function promote_rule end
promote_rule(::Type, ::Type) = Bottom
# Define some methods to avoid needing to enumerate unrelated possibilities when presented
# with Type{<:T}, and return a value in general accordance with the result given by promote_type
promote_rule(::Type{Bottom}, slurp...) = Bottom
promote_rule(::Type{Bottom}, ::Type{Bottom}, slurp...) = Bottom # not strictly necessary, since the next method would match unambiguously anyways
promote_rule(::Type{Bottom}, ::Type{T}, slurp...) where {T} = T
promote_rule(::Type{T}, ::Type{Bottom}, slurp...) where {T} = T
promote_result(::Type,::Type,::Type{T},::Type{S}) where {T,S} = (@inline; promote_type(T,S))
# If no promote_rule is defined, both directions give Bottom. In that
# case use typejoin on the original types instead.
promote_result(::Type{T},::Type{S},::Type{Bottom},::Type{Bottom}) where {T,S} = (@inline; typejoin(T, S))
"""
promote(xs...)
Convert all arguments to a common type, and return them all (as a tuple).
If no arguments can be converted, an error is raised.
See also: [`promote_type`](@ref), [`promote_rule`](@ref).
# Examples
```jldoctest
julia> promote(Int8(1), Float16(4.5), Float32(4.1))
(1.0f0, 4.5f0, 4.1f0)
julia> promote_type(Int8, Float16, Float32)
Float32
julia> reduce(Base.promote_typejoin, (Int8, Float16, Float32))
Real
julia> promote(1, "x")
ERROR: promotion of types Int64 and String failed to change any arguments
[...]
julia> promote_type(Int, String)
Any
```
"""
function promote end
function _promote(x::T, y::S) where {T,S}
@inline
R = promote_type(T, S)
return (convert(R, x), convert(R, y))
end
promote_typeof(x) = typeof(x)
promote_typeof(x, xs...) = (@inline; promote_type(typeof(x), promote_typeof(xs...)))
function _promote(x, y, z)
@inline
R = promote_typeof(x, y, z)
return (convert(R, x), convert(R, y), convert(R, z))
end
function _promote(x, y, zs...)
@inline
R = promote_typeof(x, y, zs...)
return (convert(R, x), convert(R, y), convert(Tuple{Vararg{R}}, zs)...)
end
# TODO: promote(x::T, ys::T...) where {T} here to catch all circularities?
## promotions in arithmetic, etc. ##
promote() = ()
promote(x) = (x,)
function promote(x, y)
@inline
px, py = _promote(x, y)
not_sametype((x,y), (px,py))
px, py
end
function promote(x, y, z)
@inline
px, py, pz = _promote(x, y, z)
not_sametype((x,y,z), (px,py,pz))
px, py, pz
end
function promote(x, y, z, a...)
p = _promote(x, y, z, a...)
not_sametype((x, y, z, a...), p)
p
end
promote(x::T, y::T, zs::T...) where {T} = (x, y, zs...)
not_sametype(x::T, y::T) where {T} = sametype_error(x)
not_sametype(x, y) = nothing
function sametype_error(input)
@noinline
error("promotion of types ",
join(map(x->string(typeof(x)), input), ", ", " and "),
" failed to change any arguments")
end
+(x::Number, y::Number) = +(promote(x,y)...)
*(x::Number, y::Number) = *(promote(x,y)...)
-(x::Number, y::Number) = -(promote(x,y)...)
/(x::Number, y::Number) = /(promote(x,y)...)
"""
^(x, y)
Exponentiation operator. If `x` is a matrix, computes matrix exponentiation.
If `y` is an `Int` literal (e.g. `2` in `x^2` or `-3` in `x^-3`), the Julia code
`x^y` is transformed by the compiler to `Base.literal_pow(^, x, Val(y))`, to
enable compile-time specialization on the value of the exponent.
(As a default fallback we have `Base.literal_pow(^, x, Val(y)) = ^(x,y)`,
where usually `^ == Base.^` unless `^` has been defined in the calling
namespace.) If `y` is a negative integer literal, then `Base.literal_pow`
transforms the operation to `inv(x)^-y` by default, where `-y` is positive.
# Examples
```jldoctest
julia> 3^5
243
julia> A = [1 2; 3 4]
2×2 Matrix{Int64}:
1 2
3 4
julia> A^3
2×2 Matrix{Int64}:
37 54
81 118
```
"""
^(x::Number, y::Number) = ^(promote(x,y)...)
fma(x::Number, y::Number, z::Number) = fma(promote(x,y,z)...)
muladd(x::Number, y::Number, z::Number) = muladd(promote(x,y,z)...)
==(x::Number, y::Number) = (==)(promote(x,y)...)
<( x::Real, y::Real) = (< )(promote(x,y)...)
<=(x::Real, y::Real) = (<=)(promote(x,y)...)
rem(x::Real, y::Real) = rem(promote(x,y)...)
mod(x::Real, y::Real) = mod(promote(x,y)...)
mod1(x::Real, y::Real) = mod1(promote(x,y)...)
fld1(x::Real, y::Real) = fld1(promote(x,y)...)
max(x::Real, y::Real) = max(promote(x,y)...)
min(x::Real, y::Real) = min(promote(x,y)...)
minmax(x::Real, y::Real) = minmax(promote(x, y)...)
if isdefined(Core, :Compiler)
const _return_type = Core.Compiler.return_type
else
_return_type(@nospecialize(f), @nospecialize(t)) = Any
end
function TupleOrBottom(tt...)
any(p -> p === Union{}, tt) && return Union{}
return Tuple{tt...}
end
"""
promote_op(f, argtypes...)
Guess what an appropriate container eltype would be for storing results of
`f(::argtypes...)`. The guess is in part based on type inference, so can change any time.
!!! warning
Due to its fragility, use of `promote_op` should be avoided. It is preferable to base
the container eltype on the type of the actual elements. Only in the absence of any
elements (for an empty result container), it may be unavoidable to call `promote_op`.
"""
function promote_op(f, S::Type...)
argT = TupleOrBottom(S...)
argT === Union{} && return Union{}
return _return_type(f, argT)
end
## catch-alls to prevent infinite recursion when definitions are missing ##
no_op_err(name, T) = error(name," not defined for ",T)
(+)(x::T, y::T) where {T<:Number} = no_op_err("+", T)
(*)(x::T, y::T) where {T<:Number} = no_op_err("*", T)
(-)(x::T, y::T) where {T<:Number} = no_op_err("-", T)
(/)(x::T, y::T) where {T<:Number} = no_op_err("/", T)
(^)(x::T, y::T) where {T<:Number} = no_op_err("^", T)
fma(x::T, y::T, z::T) where {T<:Number} = no_op_err("fma", T)
fma(x::Integer, y::Integer, z::Integer) = x*y+z
muladd(x::T, y::T, z::T) where {T<:Number} = x*y+z
(&)(x::T, y::T) where {T<:Integer} = no_op_err("&", T)
(|)(x::T, y::T) where {T<:Integer} = no_op_err("|", T)
xor(x::T, y::T) where {T<:Integer} = no_op_err("xor", T)
(==)(x::T, y::T) where {T<:Number} = x === y
(< )(x::T, y::T) where {T<:Real} = no_op_err("<" , T)
(<=)(x::T, y::T) where {T<:Real} = (x == y) | (x < y)
rem(x::T, y::T) where {T<:Real} = no_op_err("rem", T)
mod(x::T, y::T) where {T<:Real} = no_op_err("mod", T)
min(x::Real) = x
max(x::Real) = x
minmax(x::Real) = (x, x)
max(x::T, y::T) where {T<:Real} = ifelse(y < x, x, y)
min(x::T, y::T) where {T<:Real} = ifelse(y < x, y, x)
minmax(x::T, y::T) where {T<:Real} = y < x ? (y, x) : (x, y)
flipsign(x::T, y::T) where {T<:Signed} = no_op_err("flipsign", T)