#37632

Committed 26 Sep 2023 06:44AM UTC coverage: 86.999% (-0.9%) from 87.914%

Build # #37632

Build Type

push

local

Committed by

web-flow

Commit Message

inference: make `throw` block deoptimization concrete-eval friendly (#49235)

The deoptimization can sometimes destroy the effects analysis and
disable [semi-]concrete evaluation that is otherwise possible. This is
because the deoptimization was designed with the type domain
profitability in mind (#35982), and hasn't been adequately considering
the effects domain.

This commit makes the deoptimization aware of the effects domain more
and enables the `throw` block deoptimization only when the effects
already known to be ineligible for concrete-evaluation.

In our current effect system, `ALWAYS_FALSE`/`false` means that the
effect can not be refined to `ALWAYS_TRUE`/`true` anymore (unless given
user annotation later). Therefore we can enable the `throw` block
deoptimization without hindering the chance of concrete-evaluation when
any of the following conditions are met:
- `effects.consistent === ALWAYS_FALSE`
- `effects.effect_free === ALWAYS_FALSE`
- `effects.terminates === false`
- `effects.nonoverlayed === false`

Here are some numbers:

| Metric | master | this commit | #35982 reverted (set
`unoptimize_throw_blocks=false`) |

|-------------------------|-----------|-------------|--------------------------------------------|
| Base (seconds) | 15.579300 | 15.206645 | 15.296319 |
| Stdlibs (seconds) | 17.919013 | 17.667094 | 17.738128 |
| Total (seconds) | 33.499279 | 32.874737 | 33.035448 |
| Precompilation (seconds) | 49.967516 | 49.421121 | 49.999998 |
| First time `plot(rand(10,3))` [^1] | `2.476678 seconds (11.74 M
allocations)` | `2.430355 seconds (11.77 M allocations)` | `2.514874
seconds (11.64 M allocations)` |
| First time `solve(prob, QNDF())(5.0)` [^2] | `4.469492 seconds (15.32
M allocations)` | `4.499217 seconds (15.41 M allocations)` | `4.470772
seconds (15.38 M allocations)` |

[^1]: With disabling precompilation of Plots.jl.
[^2]: With disabling precompilation of OrdinaryDiffEq.

These numbers ma... (continued)

Run Details

7 of 7 new or added lines in 1 file covered. (100.0%)

73407 of 84377 relevant lines covered (87.0%)

11275130.05 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

85.79

/base/reshapedarray.jl

# This file is a part of Julia. License is MIT: https://julialang.org/license

using  Base.MultiplicativeInverses: SignedMultiplicativeInverse

struct ReshapedArray{T,N,P<:AbstractArray,MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int}}}} <: AbstractArray{T,N}
    parent::P
    dims::NTuple{N,Int}
    mi::MI
end
ReshapedArray(parent::AbstractArray{T}, dims::NTuple{N,Int}, mi) where {T,N} = ReshapedArray{T,N,typeof(parent),typeof(mi)}(parent, dims, mi)

# IndexLinear ReshapedArray
const ReshapedArrayLF{T,N,P<:AbstractArray} = ReshapedArray{T,N,P,Tuple{}}

# Fast iteration on ReshapedArrays: use the parent iterator
struct ReshapedArrayIterator{I,M}
    iter::I
    mi::NTuple{M,SignedMultiplicativeInverse{Int}}
end
ReshapedArrayIterator(A::ReshapedArray) = _rs_iterator(parent(A), A.mi)
function _rs_iterator(P, mi::NTuple{M}) where M
    iter = eachindex(P)
    ReshapedArrayIterator{typeof(iter),M}(iter, mi)
end

struct ReshapedIndex{T}
    parentindex::T
end

# eachindex(A::ReshapedArray) = ReshapedArrayIterator(A)  # TODO: uncomment this line
@inline function iterate(R::ReshapedArrayIterator, i...)
    item, inext = iterate(R.iter, i...)
    ReshapedIndex(item), inext
end
length(R::ReshapedArrayIterator) = length(R.iter)
eltype(::Type{<:ReshapedArrayIterator{I}}) where {I} = @isdefined(I) ? ReshapedIndex{eltype(I)} : Any

## reshape(::Array, ::Dims) returns an Array, except for isbitsunion eltypes (issue #28611)
# reshaping to same # of dimensions
function reshape(a::Array{T,M}, dims::NTuple{N,Int}) where {T,N,M}
    throw_dmrsa(dims, len) =
        throw(DimensionMismatch("new dimensions $(dims) must be consistent with array size $len"))

    if prod(dims) != length(a)
        throw_dmrsa(dims, length(a))
    end
    isbitsunion(T) && return ReshapedArray(a, dims, ())
    if N == M && dims == size(a)
        return a
    end
    ccall(:jl_reshape_array, Array{T,N}, (Any, Any, Any), Array{T,N}, a, dims)
end

"""
    reshape(A, dims...) -> AbstractArray
    reshape(A, dims) -> AbstractArray

Return an array with the same data as `A`, but with different
dimension sizes or number of dimensions. The two arrays share the same
underlying data, so that the result is mutable if and only if `A` is
mutable, and setting elements of one alters the values of the other.

The new dimensions may be specified either as a list of arguments or
as a shape tuple. At most one dimension may be specified with a `:`,
in which case its length is computed such that its product with all
the specified dimensions is equal to the length of the original array
`A`. The total number of elements must not change.

# Examples
```jldoctest
julia> A = Vector(1:16)
16-element Vector{Int64}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16

julia> reshape(A, (4, 4))
4×4 Matrix{Int64}:
 1  5   9  13
 2  6  10  14
 3  7  11  15
 4  8  12  16

julia> reshape(A, 2, :)
2×8 Matrix{Int64}:
 1  3  5  7   9  11  13  15
 2  4  6  8  10  12  14  16

julia> reshape(1:6, 2, 3)
2×3 reshape(::UnitRange{Int64}, 2, 3) with eltype Int64:
 1  3  5
 2  4  6
```
"""
reshape

reshape(parent::AbstractArray, dims::IntOrInd...) = reshape(parent, dims)
reshape(parent::AbstractArray, shp::Tuple{Union{Integer,OneTo}, Vararg{Union{Integer,OneTo}}}) = reshape(parent, to_shape(shp))
reshape(parent::AbstractArray, dims::Dims)        = _reshape(parent, dims)

# Allow missing dimensions with Colon():
reshape(parent::AbstractVector, ::Colon) = parent
reshape(parent::AbstractVector, ::Tuple{Colon}) = parent
reshape(parent::AbstractArray, dims::Int...) = reshape(parent, dims)
reshape(parent::AbstractArray, dims::Union{Int,Colon}...) = reshape(parent, dims)
reshape(parent::AbstractArray, dims::Tuple{Vararg{Union{Int,Colon}}}) = reshape(parent, _reshape_uncolon(parent, dims))
@inline function _reshape_uncolon(A, dims)
    @noinline throw1(dims) = throw(DimensionMismatch(string("new dimensions $(dims) ",
        "may have at most one omitted dimension specified by `Colon()`")))
    @noinline throw2(A, dims) = throw(DimensionMismatch(string("array size $(length(A)) ",
        "must be divisible by the product of the new dimensions $dims")))
    pre = _before_colon(dims...)
    post = _after_colon(dims...)
    _any_colon(post...) && throw1(dims)
    sz, remainder = divrem(length(A), prod(pre)*prod(post))
    remainder == 0 || throw2(A, dims)
    (pre..., Int(sz), post...)
end
@inline _any_colon() = false
@inline _any_colon(dim::Colon, tail...) = true
@inline _any_colon(dim::Any, tail...) = _any_colon(tail...)
@inline _before_colon(dim::Any, tail...) = (dim, _before_colon(tail...)...)
@inline _before_colon(dim::Colon, tail...) = ()
@inline _after_colon(dim::Any, tail...) =  _after_colon(tail...)
@inline _after_colon(dim::Colon, tail...) = tail

reshape(parent::AbstractArray{T,N}, ndims::Val{N}) where {T,N} = parent
function reshape(parent::AbstractArray, ndims::Val{N}) where N
    reshape(parent, rdims(Val(N), axes(parent)))
end

# Move elements from inds to out until out reaches the desired
# dimensionality N, either filling with OneTo(1) or collapsing the
# product of trailing dims into the last element
rdims_trailing(l, inds...) = length(l) * rdims_trailing(inds...)
rdims_trailing(l) = length(l)
rdims(out::Val{N}, inds::Tuple) where {N} = rdims(ntuple(Returns(OneTo(1)), Val(N)), inds)
rdims(out::Tuple{}, inds::Tuple{}) = () # N == 0, M == 0
rdims(out::Tuple{}, inds::Tuple{Any}) = ()
rdims(out::Tuple{}, inds::NTuple{M,Any}) where {M} = ()
rdims(out::Tuple{Any}, inds::Tuple{}) = out # N == 1, M == 0
rdims(out::NTuple{N,Any}, inds::Tuple{}) where {N} = out # N > 1, M == 0
rdims(out::Tuple{Any}, inds::Tuple{Any}) = inds # N == 1, M == 1
rdims(out::Tuple{Any}, inds::NTuple{M,Any}) where {M} = (oneto(rdims_trailing(inds...)),) # N == 1, M > 1
rdims(out::NTuple{N,Any}, inds::NTuple{N,Any}) where {N} = inds # N > 1, M == N
rdims(out::NTuple{N,Any}, inds::NTuple{M,Any}) where {N,M} = (first(inds), rdims(tail(out), tail(inds))...) # N > 1, M > 1, M != N


# _reshape on Array returns an Array
_reshape(parent::Vector, dims::Dims{1}) = parent
_reshape(parent::Array, dims::Dims{1}) = reshape(parent, dims)
_reshape(parent::Array, dims::Dims) = reshape(parent, dims)

# When reshaping Vector->Vector, don't wrap with a ReshapedArray
function _reshape(v::AbstractVector, dims::Dims{1})
    require_one_based_indexing(v)
    len = dims[1]
    len == length(v) || _throw_dmrs(length(v), "length", len)
    v
end
# General reshape
function _reshape(parent::AbstractArray, dims::Dims)
    n = length(parent)
    prod(dims) == n || _throw_dmrs(n, "size", dims)
    __reshape((parent, IndexStyle(parent)), dims)
end

@noinline function _throw_dmrs(n, str, dims)
    throw(DimensionMismatch("parent has $n elements, which is incompatible with $str $dims"))
end

# Reshaping a ReshapedArray
_reshape(v::ReshapedArray{<:Any,1}, dims::Dims{1}) = _reshape(v.parent, dims)
_reshape(R::ReshapedArray, dims::Dims) = _reshape(R.parent, dims)

function __reshape(p::Tuple{AbstractArray,IndexStyle}, dims::Dims)
    parent = p[1]
    strds = front(size_to_strides(map(length, axes(parent))..., 1))
    strds1 = map(s->max(1,Int(s)), strds)  # for resizing empty arrays
    mi = map(SignedMultiplicativeInverse, strds1)
    ReshapedArray(parent, dims, reverse(mi))
end

function __reshape(p::Tuple{AbstractArray{<:Any,0},IndexCartesian}, dims::Dims)
    parent = p[1]
    ReshapedArray(parent, dims, ())
end

function __reshape(p::Tuple{AbstractArray,IndexLinear}, dims::Dims)
    parent = p[1]
    ReshapedArray(parent, dims, ())
end

size(A::ReshapedArray) = A.dims
length(A::ReshapedArray) = length(parent(A))
similar(A::ReshapedArray, eltype::Type, dims::Dims) = similar(parent(A), eltype, dims)
IndexStyle(::Type{<:ReshapedArrayLF}) = IndexLinear()
parent(A::ReshapedArray) = A.parent
parentindices(A::ReshapedArray) = map(oneto, size(parent(A)))
reinterpret(::Type{T}, A::ReshapedArray, dims::Dims) where {T} = reinterpret(T, parent(A), dims)
elsize(::Type{<:ReshapedArray{<:Any,<:Any,P}}) where {P} = elsize(P)

unaliascopy(A::ReshapedArray) = typeof(A)(unaliascopy(A.parent), A.dims, A.mi)
dataids(A::ReshapedArray) = dataids(A.parent)

@inline ind2sub_rs(ax, ::Tuple{}, i::Int) = (i,)
@inline ind2sub_rs(ax, strds, i) = _ind2sub_rs(ax, strds, i - 1)
@inline _ind2sub_rs(ax, ::Tuple{}, ind) = (ind + first(ax[end]),)
@inline function _ind2sub_rs(ax, strds, ind)
    d, r = divrem(ind, strds[1])
    (_ind2sub_rs(front(ax), tail(strds), r)..., d + first(ax[end]))
end
offset_if_vec(i::Integer, axs::Tuple{<:AbstractUnitRange}) = i + first(axs[1]) - 1
offset_if_vec(i::Integer, axs::Tuple) = i

@inline function isassigned(A::ReshapedArrayLF, index::Int)
    @boundscheck checkbounds(Bool, A, index) || return false
    @inbounds ret = isassigned(parent(A), index)
    ret
end
@inline function isassigned(A::ReshapedArray{T,N}, indices::Vararg{Int, N}) where {T,N}
    @boundscheck checkbounds(Bool, A, indices...) || return false
    axp = axes(A.parent)
    i = offset_if_vec(_sub2ind(size(A), indices...), axp)
    I = ind2sub_rs(axp, A.mi, i)
    @inbounds isassigned(A.parent, I...)
end

@inline function getindex(A::ReshapedArrayLF, index::Int)
    @boundscheck checkbounds(A, index)
    @inbounds ret = parent(A)[index]
    ret
end
@inline function getindex(A::ReshapedArray{T,N}, indices::Vararg{Int,N}) where {T,N}
    @boundscheck checkbounds(A, indices...)
    _unsafe_getindex(A, indices...)
end
@inline function getindex(A::ReshapedArray, index::ReshapedIndex)
    @boundscheck checkbounds(parent(A), index.parentindex)
    @inbounds ret = parent(A)[index.parentindex]
    ret
end

@inline function _unsafe_getindex(A::ReshapedArray{T,N}, indices::Vararg{Int,N}) where {T,N}
    axp = axes(A.parent)
    i = offset_if_vec(_sub2ind(size(A), indices...), axp)
    I = ind2sub_rs(axp, A.mi, i)
    _unsafe_getindex_rs(parent(A), I)
end
@inline _unsafe_getindex_rs(A, i::Integer) = (@inbounds ret = A[i]; ret)
@inline _unsafe_getindex_rs(A, I) = (@inbounds ret = A[I...]; ret)

@inline function setindex!(A::ReshapedArrayLF, val, index::Int)
    @boundscheck checkbounds(A, index)
    @inbounds parent(A)[index] = val
    val
end
@inline function setindex!(A::ReshapedArray{T,N}, val, indices::Vararg{Int,N}) where {T,N}
    @boundscheck checkbounds(A, indices...)
    _unsafe_setindex!(A, val, indices...)
end
@inline function setindex!(A::ReshapedArray, val, index::ReshapedIndex)
    @boundscheck checkbounds(parent(A), index.parentindex)
    @inbounds parent(A)[index.parentindex] = val
    val
end

@inline function _unsafe_setindex!(A::ReshapedArray{T,N}, val, indices::Vararg{Int,N}) where {T,N}
    axp = axes(A.parent)
    i = offset_if_vec(_sub2ind(size(A), indices...), axp)
    @inbounds parent(A)[ind2sub_rs(axes(A.parent), A.mi, i)...] = val
    val
end

# helpful error message for a common failure case
const ReshapedRange{T,N,A<:AbstractRange} = ReshapedArray{T,N,A,Tuple{}}
setindex!(A::ReshapedRange, val, index::Int) = _rs_setindex!_err()
setindex!(A::ReshapedRange{T,N}, val, indices::Vararg{Int,N}) where {T,N} = _rs_setindex!_err()
setindex!(A::ReshapedRange, val, index::ReshapedIndex) = _rs_setindex!_err()

@noinline _rs_setindex!_err() = error("indexed assignment fails for a reshaped range; consider calling collect")

unsafe_convert(::Type{Ptr{T}}, a::ReshapedArray{T}) where {T} = unsafe_convert(Ptr{T}, parent(a))

# Add a few handy specializations to further speed up views of reshaped ranges
const ReshapedUnitRange{T,N,A<:AbstractUnitRange} = ReshapedArray{T,N,A,Tuple{}}
viewindexing(I::Tuple{Slice, ReshapedUnitRange, Vararg{ScalarIndex}}) = IndexLinear()
viewindexing(I::Tuple{ReshapedRange, Vararg{ScalarIndex}}) = IndexLinear()
compute_stride1(s, inds, I::Tuple{ReshapedRange, Vararg{Any}}) = s*step(I[1].parent)
compute_offset1(parent::AbstractVector, stride1::Integer, I::Tuple{ReshapedRange}) =
    (@inline; first(I[1]) - first(axes1(I[1]))*stride1)
substrides(strds::NTuple{N,Int}, I::Tuple{ReshapedUnitRange, Vararg{Any}}) where N =
    (size_to_strides(strds[1], size(I[1])...)..., substrides(tail(strds), tail(I))...)
unsafe_convert(::Type{Ptr{T}}, V::SubArray{T,N,P,<:Tuple{Vararg{Union{RangeIndex,ReshapedUnitRange}}}}) where {T,N,P} =
    unsafe_convert(Ptr{T}, V.parent) + (first_index(V)-1)*sizeof(T)


_checkcontiguous(::Type{Bool}, A::AbstractArray) = false
# `strides(A::DenseArray)` calls `size_to_strides` by default.
# Thus it's OK to assume all `DenseArray`s are contiguously stored.
_checkcontiguous(::Type{Bool}, A::DenseArray) = true
_checkcontiguous(::Type{Bool}, A::ReshapedArray) = _checkcontiguous(Bool, parent(A))
_checkcontiguous(::Type{Bool}, A::FastContiguousSubArray) = _checkcontiguous(Bool, parent(A))

function strides(a::ReshapedArray)
    _checkcontiguous(Bool, a) && return size_to_strides(1, size(a)...)
    apsz::Dims = size(a.parent)
    apst::Dims = strides(a.parent)
    msz, mst, n = merge_adjacent_dim(apsz, apst) # Try to perform "lazy" reshape
    n == ndims(a.parent) && return size_to_strides(mst, size(a)...) # Parent is stridevector like
    return _reshaped_strides(size(a), 1, msz, mst, n, apsz, apst)
end

function _reshaped_strides(::Dims{0}, reshaped::Int, msz::Int, ::Int, ::Int, ::Dims, ::Dims)
    reshaped == msz && return ()
    throw(ArgumentError("Input is not strided."))
end
function _reshaped_strides(sz::Dims, reshaped::Int, msz::Int, mst::Int, n::Int, apsz::Dims, apst::Dims)
    st = reshaped * mst
    reshaped = reshaped * sz[1]
    if length(sz) > 1 && reshaped == msz && sz[2] != 1
        msz, mst, n = merge_adjacent_dim(apsz, apst, n + 1)
        reshaped = 1
    end
    sts = _reshaped_strides(tail(sz), reshaped, msz, mst, n, apsz, apst)
    return (st, sts...)
end

merge_adjacent_dim(::Dims{0}, ::Dims{0}) = 1, 1, 0
merge_adjacent_dim(apsz::Dims{1}, apst::Dims{1}) = apsz[1], apst[1], 1
function merge_adjacent_dim(apsz::Dims{N}, apst::Dims{N}, n::Int = 1) where {N}
    sz, st = apsz[n], apst[n]
    while n < N
        szₙ, stₙ = apsz[n+1], apst[n+1]
        if sz == 1
            sz, st = szₙ, stₙ
        elseif stₙ == st * sz || szₙ == 1
            sz *= szₙ
        else
            break
        end
        n += 1
    end
    return sz, st, n
end

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	using Base.MultiplicativeInverses: SignedMultiplicativeInverse
4
5	struct ReshapedArray{T,N,P<:AbstractArray,MI<:Tuple{Vararg{SignedMultiplicativeInverse{Int}}}} <: AbstractArray{T,N}
6	parent::P	125,223✔
7	dims::NTuple{N,Int}
8	mi::MI
9	end
10	ReshapedArray(parent::AbstractArray{T}, dims::NTuple{N,Int}, mi) where {T,N} = ReshapedArray{T,N,typeof(parent),typeof(mi)}(parent, dims, mi)	125,217✔
11
12	# IndexLinear ReshapedArray
13	const ReshapedArrayLF{T,N,P<:AbstractArray} = ReshapedArray{T,N,P,Tuple{}}
14
15	# Fast iteration on ReshapedArrays: use the parent iterator
16	struct ReshapedArrayIterator{I,M}
17	iter::I
18	mi::NTuple{M,SignedMultiplicativeInverse{Int}}
19	end
20	ReshapedArrayIterator(A::ReshapedArray) = _rs_iterator(parent(A), A.mi)	×
21	function _rs_iterator(P, mi::NTuple{M}) where M	×
22	iter = eachindex(P)	×
23	ReshapedArrayIterator{typeof(iter),M}(iter, mi)	×
24	end
25
26	struct ReshapedIndex{T}
27	parentindex::T	4✔
28	end
29
30	# eachindex(A::ReshapedArray) = ReshapedArrayIterator(A) # TODO: uncomment this line
31	@inline function iterate(R::ReshapedArrayIterator, i...)	×
32	item, inext = iterate(R.iter, i...)	×
33	ReshapedIndex(item), inext	×
34	end
35	length(R::ReshapedArrayIterator) = length(R.iter)	×
36	eltype(::Type{<:ReshapedArrayIterator{I}}) where {I} = @isdefined(I) ? ReshapedIndex{eltype(I)} : Any	×
37
38	## reshape(::Array, ::Dims) returns an Array, except for isbitsunion eltypes (issue #28611)
39	# reshaping to same # of dimensions
40	function reshape(a::Array{T,M}, dims::NTuple{N,Int}) where {T,N,M}	5,012✔
41	throw_dmrsa(dims, len) =	5,016✔
42	throw(DimensionMismatch("new dimensions $(dims) must be consistent with array size $len"))
43
44	if prod(dims) != length(a)	5,012✔
45	throw_dmrsa(dims, length(a))	4✔
46	end
47	isbitsunion(T) && return ReshapedArray(a, dims, ())	5,008✔
48	if N == M && dims == size(a)	5,253✔
49	return a	285✔
50	end
51	ccall(:jl_reshape_array, Array{T,N}, (Any, Any, Any), Array{T,N}, a, dims)	4,681✔
52	end
53
54	"""
55	reshape(A, dims...) -> AbstractArray
56	reshape(A, dims) -> AbstractArray
57
58	Return an array with the same data as `A`, but with different
59	dimension sizes or number of dimensions. The two arrays share the same
60	underlying data, so that the result is mutable if and only if `A` is
61	mutable, and setting elements of one alters the values of the other.
62
63	The new dimensions may be specified either as a list of arguments or
64	as a shape tuple. At most one dimension may be specified with a `:`,
65	in which case its length is computed such that its product with all
66	the specified dimensions is equal to the length of the original array
67	`A`. The total number of elements must not change.
68
69	# Examples
70	```jldoctest
71	julia> A = Vector(1:16)
72	16-element Vector{Int64}:
73	1
74	2
75	3
76	4
77	5
78	6
79	7
80	8
81	9
82	10
83	11
84	12
85	13
86	14
87	15
88	16
89
90	julia> reshape(A, (4, 4))
91	4×4 Matrix{Int64}:
92	1 5 9 13
93	2 6 10 14
94	3 7 11 15
95	4 8 12 16
96
97	julia> reshape(A, 2, :)
98	2×8 Matrix{Int64}:
99	1 3 5 7 9 11 13 15
100	2 4 6 8 10 12 14 16
101
102	julia> reshape(1:6, 2, 3)
103	2×3 reshape(::UnitRange{Int64}, 2, 3) with eltype Int64:
104	1 3 5
105	2 4 6
106	```
107	"""
108	reshape
109
110	reshape(parent::AbstractArray, dims::IntOrInd...) = reshape(parent, dims)	1✔
111	reshape(parent::AbstractArray, shp::Tuple{Union{Integer,OneTo}, Vararg{Union{Integer,OneTo}}}) = reshape(parent, to_shape(shp))	2,083✔
112	reshape(parent::AbstractArray, dims::Dims) = _reshape(parent, dims)	7,066✔
113
114	# Allow missing dimensions with Colon():
115	reshape(parent::AbstractVector, ::Colon) = parent	3✔
116	reshape(parent::AbstractVector, ::Tuple{Colon}) = parent	2✔
117	reshape(parent::AbstractArray, dims::Int...) = reshape(parent, dims)	8,730✔
118	reshape(parent::AbstractArray, dims::Union{Int,Colon}...) = reshape(parent, dims)	69✔
119	reshape(parent::AbstractArray, dims::Tuple{Vararg{Union{Int,Colon}}}) = reshape(parent, _reshape_uncolon(parent, dims))	77✔
120	@inline function _reshape_uncolon(A, dims)	75✔
121	@noinline throw1(dims) = throw(DimensionMismatch(string("new dimensions $(dims) ",	77✔
122	"may have at most one omitted dimension specified by `Colon()`")))
123	@noinline throw2(A, dims) = throw(DimensionMismatch(string("array size $(length(A)) ",	78✔
124	"must be divisible by the product of the new dimensions $dims")))
125	pre = _before_colon(dims...)	75✔
126	post = _after_colon(dims...)	75✔
127	_any_colon(post...) && throw1(dims)	75✔
128	sz, remainder = divrem(length(A), prod(pre)*prod(post))	73✔
129	remainder == 0 \|\| throw2(A, dims)	76✔
130	(pre..., Int(sz), post...)	70✔
131	end
132	@inline _any_colon() = false	73✔
133	@inline _any_colon(dim::Colon, tail...) = true	2✔
134	@inline _any_colon(dim::Any, tail...) = _any_colon(tail...)	35✔
135	@inline _before_colon(dim::Any, tail...) = (dim, _before_colon(tail...)...)	21✔
136	@inline _before_colon(dim::Colon, tail...) = ()	75✔
137	@inline _after_colon(dim::Any, tail...) = _after_colon(tail...)	21✔
138	@inline _after_colon(dim::Colon, tail...) = tail	75✔
139
140	reshape(parent::AbstractArray{T,N}, ndims::Val{N}) where {T,N} = parent	422,808✔
141	function reshape(parent::AbstractArray, ndims::Val{N}) where N	2,062✔
142	reshape(parent, rdims(Val(N), axes(parent)))	2,062✔
143	end
144
145	# Move elements from inds to out until out reaches the desired
146	# dimensionality N, either filling with OneTo(1) or collapsing the
147	# product of trailing dims into the last element
148	rdims_trailing(l, inds...) = length(l) * rdims_trailing(inds...)	1,888✔
149	rdims_trailing(l) = length(l)	1,554✔
150	rdims(out::Val{N}, inds::Tuple) where {N} = rdims(ntuple(Returns(OneTo(1)), Val(N)), inds)	2,062✔
151	rdims(out::Tuple{}, inds::Tuple{}) = () # N == 0, M == 0	×
152	rdims(out::Tuple{}, inds::Tuple{Any}) = ()	6✔
153	rdims(out::Tuple{}, inds::NTuple{M,Any}) where {M} = ()	×
154	rdims(out::Tuple{Any}, inds::Tuple{}) = out # N == 1, M == 0	494✔
155	rdims(out::NTuple{N,Any}, inds::Tuple{}) where {N} = out # N > 1, M == 0	8✔
156	rdims(out::Tuple{Any}, inds::Tuple{Any}) = inds # N == 1, M == 1	×
157	rdims(out::Tuple{Any}, inds::NTuple{M,Any}) where {M} = (oneto(rdims_trailing(inds...)),) # N == 1, M > 1	1,554✔
158	rdims(out::NTuple{N,Any}, inds::NTuple{N,Any}) where {N} = inds # N > 1, M == N	×
159	rdims(out::NTuple{N,Any}, inds::NTuple{M,Any}) where {N,M} = (first(inds), rdims(tail(out), tail(inds))...) # N > 1, M > 1, M != N	546✔
160
161
162	# _reshape on Array returns an Array
163	_reshape(parent::Vector, dims::Dims{1}) = parent	2✔
164	_reshape(parent::Array, dims::Dims{1}) = reshape(parent, dims)	×
165	_reshape(parent::Array, dims::Dims) = reshape(parent, dims)	×
166
167	# When reshaping Vector->Vector, don't wrap with a ReshapedArray
168	function _reshape(v::AbstractVector, dims::Dims{1})	26✔
169	require_one_based_indexing(v)	26✔
170	len = dims[1]	26✔
171	len == length(v) \|\| _throw_dmrs(length(v), "length", len)	27✔
172	v	25✔
173	end
174	# General reshape
175	function _reshape(parent::AbstractArray, dims::Dims)	7,030✔
176	n = length(parent)	7,030✔
177	prod(dims) == n \|\| _throw_dmrs(n, "size", dims)	7,043✔
178	__reshape((parent, IndexStyle(parent)), dims)	7,017✔
179	end
180
181	@noinline function _throw_dmrs(n, str, dims)	14✔
182	throw(DimensionMismatch("parent has $n elements, which is incompatible with $str $dims"))	14✔
183	end
184
185	# Reshaping a ReshapedArray
186	_reshape(v::ReshapedArray{<:Any,1}, dims::Dims{1}) = _reshape(v.parent, dims)	2✔
187	_reshape(R::ReshapedArray, dims::Dims) = _reshape(R.parent, dims)	19✔
188
189	function __reshape(p::Tuple{AbstractArray,IndexStyle}, dims::Dims)	2,511✔
190	parent = p[1]	2,511✔
191	strds = front(size_to_strides(map(length, axes(parent))..., 1))	2,511✔
192	strds1 = map(s->max(1,Int(s)), strds) # for resizing empty arrays	5,043✔
193	mi = map(SignedMultiplicativeInverse, strds1)	2,511✔
194	ReshapedArray(parent, dims, reverse(mi))	2,511✔
195	end
196
197	function __reshape(p::Tuple{AbstractArray{<:Any,0},IndexCartesian}, dims::Dims)	4✔
198	parent = p[1]	4✔
199	ReshapedArray(parent, dims, ())	4✔
200	end
201
202	function __reshape(p::Tuple{AbstractArray,IndexLinear}, dims::Dims)	4,502✔
203	parent = p[1]	4,502✔
204	ReshapedArray(parent, dims, ())	4,502✔
205	end
206
207	size(A::ReshapedArray) = A.dims	1,821,465✔
208	length(A::ReshapedArray) = length(parent(A))	4,038,187✔
209	similar(A::ReshapedArray, eltype::Type, dims::Dims) = similar(parent(A), eltype, dims)	638✔
210	IndexStyle(::Type{<:ReshapedArrayLF}) = IndexLinear()	21,509✔
211	parent(A::ReshapedArray) = A.parent	8,648,510✔
212	parentindices(A::ReshapedArray) = map(oneto, size(parent(A)))	2✔
213	reinterpret(::Type{T}, A::ReshapedArray, dims::Dims) where {T} = reinterpret(T, parent(A), dims)	×
214	elsize(::Type{<:ReshapedArray{<:Any,<:Any,P}}) where {P} = elsize(P)	1,420✔
215
216	unaliascopy(A::ReshapedArray) = typeof(A)(unaliascopy(A.parent), A.dims, A.mi)	6✔
217	dataids(A::ReshapedArray) = dataids(A.parent)	4,520✔
218
219	@inline ind2sub_rs(ax, ::Tuple{}, i::Int) = (i,)	44,145✔
220	@inline ind2sub_rs(ax, strds, i) = _ind2sub_rs(ax, strds, i - 1)	687,931✔
221	@inline _ind2sub_rs(ax, ::Tuple{}, ind) = (ind + first(ax[end]),)	687,931✔
222	@inline function _ind2sub_rs(ax, strds, ind)	1,244,053✔
223	d, r = divrem(ind, strds[1])	1,244,053✔
224	(_ind2sub_rs(front(ax), tail(strds), r)..., d + first(ax[end]))	1,244,053✔
225	end
226	offset_if_vec(i::Integer, axs::Tuple{<:AbstractUnitRange}) = i + first(axs[1]) - 1	36,186✔
227	offset_if_vec(i::Integer, axs::Tuple) = i	565,384✔
228
229	@inline function isassigned(A::ReshapedArrayLF, index::Int)	×
230	@boundscheck checkbounds(Bool, A, index) \|\| return false	×
231	@inbounds ret = isassigned(parent(A), index)	×
232	ret	×
233	end
234	@inline function isassigned(A::ReshapedArray{T,N}, indices::Vararg{Int, N}) where {T,N}	14,100✔
235	@boundscheck checkbounds(Bool, A, indices...) \|\| return false	14,100✔
236	axp = axes(A.parent)	14,100✔
237	i = offset_if_vec(_sub2ind(size(A), indices...), axp)	14,100✔
238	I = ind2sub_rs(axp, A.mi, i)	14,100✔
239	@inbounds isassigned(A.parent, I...)	14,100✔
240	end
241
242	@inline function getindex(A::ReshapedArrayLF, index::Int)	4,018,946✔
243	@boundscheck checkbounds(A, index)	4,018,946✔
244	@inbounds ret = parent(A)[index]	4,019,400✔
245	ret	4,018,946✔
246	end
247	@inline function getindex(A::ReshapedArray{T,N}, indices::Vararg{Int,N}) where {T,N}	586,039✔
248	@boundscheck checkbounds(A, indices...)	586,041✔
249	_unsafe_getindex(A, indices...)	587,720✔
250	end
251	@inline function getindex(A::ReshapedArray, index::ReshapedIndex)	2✔
252	@boundscheck checkbounds(parent(A), index.parentindex)	2✔
253	@inbounds ret = parent(A)[index.parentindex]	2✔
254	ret	2✔
255	end
256
257	@inline function _unsafe_getindex(A::ReshapedArray{T,N}, indices::Vararg{Int,N}) where {T,N}	586,037✔
258	axp = axes(A.parent)	586,037✔
259	i = offset_if_vec(_sub2ind(size(A), indices...), axp)	586,037✔
260	I = ind2sub_rs(axp, A.mi, i)	586,037✔
261	_unsafe_getindex_rs(parent(A), I)	587,720✔
262	end
263	@inline _unsafe_getindex_rs(A, i::Integer) = (@inbounds ret = A[i]; ret)	×
264	@inline _unsafe_getindex_rs(A, I) = (@inbounds ret = A[I...]; ret)	1,173,757✔
265
266	@inline function setindex!(A::ReshapedArrayLF, val, index::Int)	242✔
267	@boundscheck checkbounds(A, index)	242✔
268	@inbounds parent(A)[index] = val	242✔
269	val	242✔
270	end
271	@inline function setindex!(A::ReshapedArray{T,N}, val, indices::Vararg{Int,N}) where {T,N}	1,433✔
272	@boundscheck checkbounds(A, indices...)	1,433✔
273	_unsafe_setindex!(A, val, indices...)	1,433✔
274	end
275	@inline function setindex!(A::ReshapedArray, val, index::ReshapedIndex)	1✔
276	@boundscheck checkbounds(parent(A), index.parentindex)	1✔
277	@inbounds parent(A)[index.parentindex] = val	1✔
278	val	1✔
279	end
280
281	@inline function _unsafe_setindex!(A::ReshapedArray{T,N}, val, indices::Vararg{Int,N}) where {T,N}	1,433✔
282	axp = axes(A.parent)	1,433✔
283	i = offset_if_vec(_sub2ind(size(A), indices...), axp)	1,433✔
284	@inbounds parent(A)[ind2sub_rs(axes(A.parent), A.mi, i)...] = val	1,433✔
285	val	1,433✔
286	end
287
288	# helpful error message for a common failure case
289	const ReshapedRange{T,N,A<:AbstractRange} = ReshapedArray{T,N,A,Tuple{}}
290	setindex!(A::ReshapedRange, val, index::Int) = _rs_setindex!_err()	1✔
291	setindex!(A::ReshapedRange{T,N}, val, indices::Vararg{Int,N}) where {T,N} = _rs_setindex!_err()	1✔
292	setindex!(A::ReshapedRange, val, index::ReshapedIndex) = _rs_setindex!_err()	1✔
293
294	@noinline _rs_setindex!_err() = error("indexed assignment fails for a reshaped range; consider calling collect")	3✔
295
296	unsafe_convert(::Type{Ptr{T}}, a::ReshapedArray{T}) where {T} = unsafe_convert(Ptr{T}, parent(a))	1,454✔
297
298	# Add a few handy specializations to further speed up views of reshaped ranges
299	const ReshapedUnitRange{T,N,A<:AbstractUnitRange} = ReshapedArray{T,N,A,Tuple{}}
300	viewindexing(I::Tuple{Slice, ReshapedUnitRange, Vararg{ScalarIndex}}) = IndexLinear()	×
301	viewindexing(I::Tuple{ReshapedRange, Vararg{ScalarIndex}}) = IndexLinear()	×
302	compute_stride1(s, inds, I::Tuple{ReshapedRange, Vararg{Any}}) = s*step(I[1].parent)	×
303	compute_offset1(parent::AbstractVector, stride1::Integer, I::Tuple{ReshapedRange}) =	×
304	(@inline; first(I[1]) - first(axes1(I[1]))*stride1)	×
305	substrides(strds::NTuple{N,Int}, I::Tuple{ReshapedUnitRange, Vararg{Any}}) where N =	×
306	(size_to_strides(strds[1], size(I[1])...)..., substrides(tail(strds), tail(I))...)
307	unsafe_convert(::Type{Ptr{T}}, V::SubArray{T,N,P,<:Tuple{Vararg{Union{RangeIndex,ReshapedUnitRange}}}}) where {T,N,P} =	×
308	unsafe_convert(Ptr{T}, V.parent) + (first_index(V)-1)*sizeof(T)
309
310
311	_checkcontiguous(::Type{Bool}, A::AbstractArray) = false	6,901✔
312	# `strides(A::DenseArray)` calls `size_to_strides` by default.
313	# Thus it's OK to assume all `DenseArray`s are contiguously stored.
314	_checkcontiguous(::Type{Bool}, A::DenseArray) = true	60,440✔
315	_checkcontiguous(::Type{Bool}, A::ReshapedArray) = _checkcontiguous(Bool, parent(A))	1,551✔
316	_checkcontiguous(::Type{Bool}, A::FastContiguousSubArray) = _checkcontiguous(Bool, parent(A))	3,026✔
317
318	function strides(a::ReshapedArray)	1,487✔
319	_checkcontiguous(Bool, a) && return size_to_strides(1, size(a)...)	1,487✔
320	apsz::Dims = size(a.parent)	1,465✔
321	apst::Dims = strides(a.parent)	1,465✔
322	msz, mst, n = merge_adjacent_dim(apsz, apst) # Try to perform "lazy" reshape	1,465✔
323	n == ndims(a.parent) && return size_to_strides(mst, size(a)...) # Parent is stridevector like	1,465✔
324	return _reshaped_strides(size(a), 1, msz, mst, n, apsz, apst)	581✔
325	end
326
327	function _reshaped_strides(::Dims{0}, reshaped::Int, msz::Int, ::Int, ::Int, ::Dims, ::Dims)	581✔
328	reshaped == msz && return ()	581✔
329	throw(ArgumentError("Input is not strided."))	5✔
330	end
331	function _reshaped_strides(sz::Dims, reshaped::Int, msz::Int, mst::Int, n::Int, apsz::Dims, apst::Dims)	2,924✔
332	st = reshaped * mst	2,924✔
333	reshaped = reshaped * sz[1]	2,924✔
334	if length(sz) > 1 && reshaped == msz && sz[2] != 1	2,924✔
335	msz, mst, n = merge_adjacent_dim(apsz, apst, n + 1)	576✔
336	reshaped = 1	576✔
337	end
338	sts = _reshaped_strides(tail(sz), reshaped, msz, mst, n, apsz, apst)	2,937✔
339	return (st, sts...)	2,908✔
340	end
341
342	merge_adjacent_dim(::Dims{0}, ::Dims{0}) = 1, 1, 0	1✔
343	merge_adjacent_dim(apsz::Dims{1}, apst::Dims{1}) = apsz[1], apst[1], 1	3,092✔
344	function merge_adjacent_dim(apsz::Dims{N}, apst::Dims{N}, n::Int = 1) where {N}	1,997✔
345	sz, st = apsz[n], apst[n]	1,980✔
346	while n < N	1,415✔
347	szₙ, stₙ = apsz[n+1], apst[n+1]	720✔
348	if sz == 1	720✔
349	sz, st = szₙ, stₙ	3✔
350	elseif stₙ == st * sz \|\| szₙ == 1	1,317✔
351	sz *= szₙ	134✔
352	else
353	break	583✔
354	end
355	n += 1	137✔
356	end	137✔
357	return sz, st, n	1,278✔
358	end

JuliaLang / julia / #37632

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous