#37527

pending completion

Build # #37527

Build Type

push

local

Committed by

web-flow

Commit Message

make `IRShow.method_name` inferrable (#49607)

Run Details

18 of 18 new or added lines in 3 files covered. (100.0%)

68710 of 81829 relevant lines covered (83.97%)

33068903.12 hits per line

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

0.58

/stdlib/LinearAlgebra/src/bitarray.jl

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

function dot(x::BitVector, y::BitVector)
    # simplest way to mimic Array dot behavior
    length(x) == length(y) || throw(DimensionMismatch())
    s = 0
    xc = x.chunks
    yc = y.chunks
    @inbounds for i = 1:length(xc)
        s += count_ones(xc[i] & yc[i])
    end
    s
end

## slower than the unpacked version, which is MUCH slower
#  than blas'd (this one saves storage though, keeping it commented
#  just in case)
#function aTb(A::BitMatrix, B::BitMatrix)
    #(mA, nA) = size(A)
    #(mB, nB) = size(B)
    #C = falses(nA, nB)
    #if mA != mB; throw(DimensionMismatch()) end
    #if mA == 0; return C; end
    #col_ch = num_bit_chunks(mA)
    ## TODO: avoid using aux chunks and copy (?)
    #aux_chunksA = zeros(UInt64, col_ch)
    #aux_chunksB = [zeros(UInt64, col_ch) for j=1:nB]
    #for j = 1:nB
        #Base.copy_chunks!(aux_chunksB[j], 1, B.chunks, (j-1)*mA+1, mA)
    #end
    #for i = 1:nA
        #Base.copy_chunks!(aux_chunksA, 1, A.chunks, (i-1)*mA+1, mA)
        #for j = 1:nB
            #for k = 1:col_ch
                ## TODO: improve
                #C[i, j] += count_ones(aux_chunksA[k] & aux_chunksB[j][k])
            #end
        #end
    #end
    #C
#end

#aCb(A::BitMatrix{T}, B::BitMatrix{S}) where {T,S} = aTb(A, B)

function triu(B::BitMatrix, k::Integer=0)
    m,n = size(B)
    if !(-m + 1 <= k <= n + 1)
        throw(ArgumentError(string("the requested diagonal, $k, must be at least",
            "$(-m + 1) and at most $(n + 1) in an $m-by-$n matrix")))
    end
    A = falses(m,n)
    Ac = A.chunks
    Bc = B.chunks
    for i = max(k+1,1):n
        j = clamp((i - 1) * m + 1, 1, i * m)
        Base.copy_chunks!(Ac, j, Bc, j, min(i-k, m))
    end
    A
end

function tril(B::BitMatrix, k::Integer=0)
    m,n = size(B)
    if !(-m - 1 <= k <= n - 1)
        throw(ArgumentError(string("the requested diagonal, $k, must be at least ",
            "$(-m - 1) and at most $(n - 1) in an $m-by-$n matrix")))
    end
    A = falses(m, n)
    Ac = A.chunks
    Bc = B.chunks
    for i = 1:min(n, m+k)
        j = clamp((i - 1) * m + i - k, 1, i * m)
        Base.copy_chunks!(Ac, j, Bc, j, max(m-i+k+1, 0))
    end
    A
end

## diag

function diag(B::BitMatrix)
    n = minimum(size(B))
    v = similar(B, n)
    for i = 1:n
        v[i] = B[i,i]
    end
    v
end

## norm and rank

svd(A::BitMatrix) = svd(float(A))
qr(A::BitMatrix) = qr(float(A))

## kron

@inline function kron!(R::BitVector, a::BitVector, b::BitVector)
    m = length(a)
    n = length(b)
    @boundscheck length(R) == n*m || throw(DimensionMismatch())
    Rc = R.chunks
    bc = b.chunks
    for j = 1:m
        a[j] && Base.copy_chunks!(Rc, (j-1)*n+1, bc, 1, n)
    end
    return R
end

function kron(a::BitVector, b::BitVector)
    m = length(a)
    n = length(b)
    R = falses(n * m)
    return @inbounds kron!(R, a, b)
end

function kron!(R::BitMatrix, a::BitMatrix, b::BitMatrix)
    mA,nA = size(a)
    mB,nB = size(b)
    @boundscheck size(R) == (mA*mB, nA*nB) || throw(DimensionMismatch())

    for i = 1:mA
        ri = (1:mB) .+ ((i-1)*mB)
        for j = 1:nA
            if a[i,j]
                rj = (1:nB) .+ ((j-1)*nB)
                R[ri,rj] = b
            end
        end
    end
    return R
end

function kron(a::BitMatrix, b::BitMatrix)
    mA,nA = size(a)
    mB,nB = size(b)
    R = falses(mA*mB, nA*nB)
    return @inbounds kron!(R, a, b)
end

## Structure query functions

issymmetric(A::BitMatrix) = size(A, 1)==size(A, 2) && count(!iszero, A - copy(A'))==0
ishermitian(A::BitMatrix) = issymmetric(A)

function nonzero_chunks(chunks::Vector{UInt64}, pos0::Int, pos1::Int)
    k0, l0 = Base.get_chunks_id(pos0)
    k1, l1 = Base.get_chunks_id(pos1)

    delta_k = k1 - k0

    z = UInt64(0)
    u = ~z
    if delta_k == 0
        msk_0 = (u << l0) & ~(u << l1 << 1)
    else
        msk_0 = (u << l0)
        msk_1 = ~(u << l1 << 1)
    end

    @inbounds begin
        (chunks[k0] & msk_0) == z || return true
        delta_k == 0 && return false
        for i = k0 + 1 : k1 - 1
            chunks[i] == z || return true
        end
        (chunks[k1] & msk_1)==z || return true
    end
    return false
end

function istriu(A::BitMatrix)
    m, n = size(A)
    for j = 1:min(n,m-1)
        stride = (j-1) * m
        nonzero_chunks(A.chunks, stride+j+1, stride+m) && return false
    end
    return true
end

function istril(A::BitMatrix)
    m, n = size(A)
    (m == 0 || n == 0) && return true
    for j = 2:n
        stride = (j-1) * m
        nonzero_chunks(A.chunks, stride+1, stride+min(j-1,m)) && return false
    end
    return true
end

# fast 8x8 bit transpose from Henry S. Warrens's "Hacker's Delight"
# http://www.hackersdelight.org/hdcodetxt/transpose8.c.txt
function transpose8x8(x::UInt64)
    y = x
    t = xor(y, y >>> 7) & 0x00aa00aa00aa00aa
    y = xor(y, t, t << 7)
    t = xor(y, y >>> 14) & 0x0000cccc0000cccc
    y = xor(y, t, t << 14)
    t = xor(y, y >>> 28) & 0x00000000f0f0f0f0
    return xor(y, t, t << 28)
end

function form_8x8_chunk(Bc::Vector{UInt64}, i1::Int, i2::Int, m::Int, cgap::Int, cinc::Int, nc::Int, msk8::UInt64)
    x = UInt64(0)

    k, l = Base.get_chunks_id(i1 + (i2 - 1) * m)
    r = 0
    for j = 1:8
        k > nc && break
        x |= ((Bc[k] >>> l) & msk8) << r
        if l + 8 >= 64 && nc > k
            r0 = 8 - Base._mod64(l + 8)
            x |= (Bc[k + 1] & (msk8 >>> r0)) << (r + r0)
        end
        k += cgap + (l + cinc >= 64 ? 1 : 0)
        l = Base._mod64(l + cinc)
        r += 8
    end
    return x
end

# note: assumes B is filled with 0's
function put_8x8_chunk(Bc::Vector{UInt64}, i1::Int, i2::Int, x::UInt64, m::Int, cgap::Int, cinc::Int, nc::Int, msk8::UInt64)
    k, l = Base.get_chunks_id(i1 + (i2 - 1) * m)
    r = 0
    for j = 1:8
        k > nc && break
        Bc[k] |= ((x >>> r) & msk8) << l
        if l + 8 >= 64 && nc > k
            r0 = 8 - Base._mod64(l + 8)
            Bc[k + 1] |= ((x >>> (r + r0)) & (msk8 >>> r0))
        end
        k += cgap + (l + cinc >= 64 ? 1 : 0)
        l = Base._mod64(l + cinc)
        r += 8
    end
    return
end

adjoint(B::Union{BitVector,BitMatrix}) = Adjoint(B)
transpose(B::Union{BitVector,BitMatrix}) = Transpose(B)
Base.copy(B::Adjoint{Bool,BitMatrix}) = transpose!(falses(size(B)), B.parent)
Base.copy(B::Transpose{Bool,BitMatrix}) = transpose!(falses(size(B)), B.parent)
function transpose!(C::BitMatrix, B::BitMatrix)
    @boundscheck size(C) == reverse(size(B)) || throw(DimensionMismatch())
    l1, l2 = size(B)

    cgap1, cinc1 = Base._div64(l1), Base._mod64(l1)
    cgap2, cinc2 = Base._div64(l2), Base._mod64(l2)

    Bc = B.chunks
    Cc = C.chunks

    nc = length(Bc)

    for i = 1:8:l1
        msk8_1 = UInt64(0xff)
        if (l1 < i + 7)
            msk8_1 >>>= i + 7 - l1
        end

        for j = 1:8:l2
            x = form_8x8_chunk(Bc, i, j, l1, cgap1, cinc1, nc, msk8_1)
            x = transpose8x8(x)

            msk8_2 = UInt64(0xff)
            if (l2 < j + 7)
                msk8_2 >>>= j + 7 - l2
            end

            put_8x8_chunk(Cc, j, i, x, l2, cgap2, cinc2, nc, msk8_2)
        end
    end
    return C
end

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	function dot(x::BitVector, y::BitVector)	×
4	# simplest way to mimic Array dot behavior
5	length(x) == length(y) \|\| throw(DimensionMismatch())	×
6	s = 0	×
7	xc = x.chunks	×
8	yc = y.chunks	×
9	@inbounds for i = 1:length(xc)	×
10	s += count_ones(xc[i] & yc[i])	×
11	end	×
12	s	×
13	end
14
15	## slower than the unpacked version, which is MUCH slower
16	# than blas'd (this one saves storage though, keeping it commented
17	# just in case)
18	#function aTb(A::BitMatrix, B::BitMatrix)
19	#(mA, nA) = size(A)
20	#(mB, nB) = size(B)
21	#C = falses(nA, nB)
22	#if mA != mB; throw(DimensionMismatch()) end
23	#if mA == 0; return C; end
24	#col_ch = num_bit_chunks(mA)
25	## TODO: avoid using aux chunks and copy (?)
26	#aux_chunksA = zeros(UInt64, col_ch)
27	#aux_chunksB = [zeros(UInt64, col_ch) for j=1:nB]
28	#for j = 1:nB
29	#Base.copy_chunks!(aux_chunksB[j], 1, B.chunks, (j-1)*mA+1, mA)
30	#end
31	#for i = 1:nA
32	#Base.copy_chunks!(aux_chunksA, 1, A.chunks, (i-1)*mA+1, mA)
33	#for j = 1:nB
34	#for k = 1:col_ch
35	## TODO: improve
36	#C[i, j] += count_ones(aux_chunksA[k] & aux_chunksB[j][k])
37	#end
38	#end
39	#end
40	#C
41	#end
42
43	#aCb(A::BitMatrix{T}, B::BitMatrix{S}) where {T,S} = aTb(A, B)
44
45	function triu(B::BitMatrix, k::Integer=0)	×
46	m,n = size(B)	×
47	if !(-m + 1 <= k <= n + 1)	×
48	throw(ArgumentError(string("the requested diagonal, $k, must be at least",	×
49	"$(-m + 1) and at most $(n + 1) in an $m-by-$n matrix")))
50	end
51	A = falses(m,n)	×
52	Ac = A.chunks	×
53	Bc = B.chunks	×
54	for i = max(k+1,1):n	×
55	j = clamp((i - 1) * m + 1, 1, i * m)	×
56	Base.copy_chunks!(Ac, j, Bc, j, min(i-k, m))	×
57	end	×
58	A	×
59	end
60
61	function tril(B::BitMatrix, k::Integer=0)	×
62	m,n = size(B)	×
63	if !(-m - 1 <= k <= n - 1)	×
64	throw(ArgumentError(string("the requested diagonal, $k, must be at least ",	×
65	"$(-m - 1) and at most $(n - 1) in an $m-by-$n matrix")))
66	end
67	A = falses(m, n)	×
68	Ac = A.chunks	×
69	Bc = B.chunks	×
70	for i = 1:min(n, m+k)	×
71	j = clamp((i - 1) * m + i - k, 1, i * m)	×
72	Base.copy_chunks!(Ac, j, Bc, j, max(m-i+k+1, 0))	×
73	end	×
74	A	×
75	end
76
77	## diag
78
79	function diag(B::BitMatrix)	×
80	n = minimum(size(B))	×
81	v = similar(B, n)	×
82	for i = 1:n	×
83	v[i] = B[i,i]	×
84	end	×
85	v	×
86	end
87
88	## norm and rank
89
90	svd(A::BitMatrix) = svd(float(A))	×
91	qr(A::BitMatrix) = qr(float(A))	×
92
93	## kron
94
95	@inline function kron!(R::BitVector, a::BitVector, b::BitVector)	×
96	m = length(a)	×
97	n = length(b)	×
98	@boundscheck length(R) == n*m \|\| throw(DimensionMismatch())	×
99	Rc = R.chunks	×
100	bc = b.chunks	×
101	for j = 1:m	×
102	a[j] && Base.copy_chunks!(Rc, (j-1)*n+1, bc, 1, n)	×
103	end	×
104	return R	×
105	end
106
107	function kron(a::BitVector, b::BitVector)	×
108	m = length(a)	×
109	n = length(b)	×
110	R = falses(n * m)	×
111	return @inbounds kron!(R, a, b)	×
112	end
113
114	function kron!(R::BitMatrix, a::BitMatrix, b::BitMatrix)	×
115	mA,nA = size(a)	×
116	mB,nB = size(b)	×
117	@boundscheck size(R) == (mAmB, nAnB) \|\| throw(DimensionMismatch())	×
118
119	for i = 1:mA	×
120	ri = (1:mB) .+ ((i-1)*mB)	×
121	for j = 1:nA	×
122	if a[i,j]	×
123	rj = (1:nB) .+ ((j-1)*nB)	×
124	R[ri,rj] = b	×
125	end
126	end	×
127	end	×
128	return R	×
129	end
130
131	function kron(a::BitMatrix, b::BitMatrix)	×
132	mA,nA = size(a)	×
133	mB,nB = size(b)	×
134	R = falses(mAmB, nAnB)	×
135	return @inbounds kron!(R, a, b)	×
136	end
137
138	## Structure query functions
139
140	issymmetric(A::BitMatrix) = size(A, 1)==size(A, 2) && count(!iszero, A - copy(A'))==0	×
141	ishermitian(A::BitMatrix) = issymmetric(A)	×
142
143	function nonzero_chunks(chunks::Vector{UInt64}, pos0::Int, pos1::Int)	×
144	k0, l0 = Base.get_chunks_id(pos0)	×
145	k1, l1 = Base.get_chunks_id(pos1)	×
146
147	delta_k = k1 - k0	×
148
149	z = UInt64(0)	×
150	u = ~z	×
151	if delta_k == 0	×
152	msk_0 = (u << l0) & ~(u << l1 << 1)	×
153	else
154	msk_0 = (u << l0)	×
155	msk_1 = ~(u << l1 << 1)	×
156	end
157
158	@inbounds begin	×
159	(chunks[k0] & msk_0) == z \|\| return true	×
160	delta_k == 0 && return false	×
161	for i = k0 + 1 : k1 - 1	×
162	chunks[i] == z \|\| return true	×
163	end	×
164	(chunks[k1] & msk_1)==z \|\| return true	×
165	end
166	return false	×
167	end
168
169	function istriu(A::BitMatrix)	×
170	m, n = size(A)	×
171	for j = 1:min(n,m-1)	×
172	stride = (j-1) * m	×
173	nonzero_chunks(A.chunks, stride+j+1, stride+m) && return false	×
174	end	×
175	return true	×
176	end
177
178	function istril(A::BitMatrix)	×
179	m, n = size(A)	×
180	(m == 0 \|\| n == 0) && return true	×
181	for j = 2:n	×
182	stride = (j-1) * m	×
183	nonzero_chunks(A.chunks, stride+1, stride+min(j-1,m)) && return false	×
184	end	×
185	return true	×
186	end
187
188	# fast 8x8 bit transpose from Henry S. Warrens's "Hacker's Delight"
189	# http://www.hackersdelight.org/hdcodetxt/transpose8.c.txt
190	function transpose8x8(x::UInt64)	×
191	y = x	×
192	t = xor(y, y >>> 7) & 0x00aa00aa00aa00aa	×
193	y = xor(y, t, t << 7)	×
194	t = xor(y, y >>> 14) & 0x0000cccc0000cccc	×
195	y = xor(y, t, t << 14)	×
196	t = xor(y, y >>> 28) & 0x00000000f0f0f0f0	×
197	return xor(y, t, t << 28)	×
198	end
199
200	function form_8x8_chunk(Bc::Vector{UInt64}, i1::Int, i2::Int, m::Int, cgap::Int, cinc::Int, nc::Int, msk8::UInt64)	×
201	x = UInt64(0)	×
202
203	k, l = Base.get_chunks_id(i1 + (i2 - 1) * m)	×
204	r = 0	×
205	for j = 1:8	×
206	k > nc && break	×
207	x \|= ((Bc[k] >>> l) & msk8) << r	×
208	if l + 8 >= 64 && nc > k	×
209	r0 = 8 - Base._mod64(l + 8)	×
210	x \|= (Bc[k + 1] & (msk8 >>> r0)) << (r + r0)	×
211	end
212	k += cgap + (l + cinc >= 64 ? 1 : 0)	×
213	l = Base._mod64(l + cinc)	×
214	r += 8	×
215	end	×
216	return x	×
217	end
218
219	# note: assumes B is filled with 0's
220	function put_8x8_chunk(Bc::Vector{UInt64}, i1::Int, i2::Int, x::UInt64, m::Int, cgap::Int, cinc::Int, nc::Int, msk8::UInt64)	×
221	k, l = Base.get_chunks_id(i1 + (i2 - 1) * m)	×
222	r = 0	×
223	for j = 1:8	×
224	k > nc && break	×
225	Bc[k] \|= ((x >>> r) & msk8) << l	×
226	if l + 8 >= 64 && nc > k	×
227	r0 = 8 - Base._mod64(l + 8)	×
228	Bc[k + 1] \|= ((x >>> (r + r0)) & (msk8 >>> r0))	×
229	end
230	k += cgap + (l + cinc >= 64 ? 1 : 0)	×
231	l = Base._mod64(l + cinc)	×
232	r += 8	×
233	end	×
234	return	×
235	end
236
237	adjoint(B::Union{BitVector,BitMatrix}) = Adjoint(B)	5✔
238	transpose(B::Union{BitVector,BitMatrix}) = Transpose(B)	×
239	Base.copy(B::Adjoint{Bool,BitMatrix}) = transpose!(falses(size(B)), B.parent)	×
240	Base.copy(B::Transpose{Bool,BitMatrix}) = transpose!(falses(size(B)), B.parent)	×
241	function transpose!(C::BitMatrix, B::BitMatrix)	×
242	@boundscheck size(C) == reverse(size(B)) \|\| throw(DimensionMismatch())	×
243	l1, l2 = size(B)	×
244
245	cgap1, cinc1 = Base._div64(l1), Base._mod64(l1)	×
246	cgap2, cinc2 = Base._div64(l2), Base._mod64(l2)	×
247
248	Bc = B.chunks	×
249	Cc = C.chunks	×
250
251	nc = length(Bc)	×
252
253	for i = 1:8:l1	×
254	msk8_1 = UInt64(0xff)	×
255	if (l1 < i + 7)	×
256	msk8_1 >>>= i + 7 - l1	×
257	end
258
259	for j = 1:8:l2	×
260	x = form_8x8_chunk(Bc, i, j, l1, cgap1, cinc1, nc, msk8_1)	×
261	x = transpose8x8(x)	×
262
263	msk8_2 = UInt64(0xff)	×
264	if (l2 < j + 7)	×
265	msk8_2 >>>= j + 7 - l2	×
266	end
267
268	put_8x8_chunk(Cc, j, i, x, l2, cgap2, cinc2, nc, msk8_2)	×
269	end	×
270	end	×
271	return C	×
272	end

JuliaLang / julia / #37527

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