#38182

Committed 15 Aug 2025 03:55AM UTC coverage: 77.87% (-0.4%) from 78.28%

Build # #38182

Build Type

push

local

Committed by

web-flow

Commit Message

🤖 [master] Bump the SparseArrays stdlib from 30201ab to bb5ecc0 (#59263)

Stdlib: SparseArrays
URL: https://github.com/JuliaSparse/SparseArrays.jl.git
Stdlib branch: main
Julia branch: master
Old commit: 30201ab
New commit: bb5ecc0
Julia version: 1.13.0-DEV
SparseArrays version: 1.13.0
Bump invoked by: @ViralBShah
Powered by:
[BumpStdlibs.jl](https://github.com/JuliaLang/BumpStdlibs.jl)

Diff:
https://github.com/JuliaSparse/SparseArrays.jl/compare/30201abcb...bb5ecc091

```
$ git log --oneline 30201ab..bb5ecc0
bb5ecc0 fast quadratic form for dense matrix, sparse vectors (#640)
34ece87 Extend 3-arg `dot` to generic `HermOrSym` sparse matrices (#643)
095b685 Exclude unintended complex symmetric sparse matrices from 3-arg `dot` (#642)
8049287 Fix signature for 2-arg matrix-matrix `dot` (#641)
cff971d Make cond(::SparseMatrix, 1 / Inf) discoverable from 2-norm error (#629)
```

Co-authored-by: ViralBShah <744411+ViralBShah@users.noreply.github.com>

Run Details

48274 of 61993 relevant lines covered (77.87%)

9571166.83 hits per line

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

72.93

/base/bitset.jl

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

const Bits = Vector{UInt64}
const CHK0 = zero(UInt64)
const NO_OFFSET = Int === Int64 ? -one(Int) << 60 : -one(Int) << 29
# + NO_OFFSET must be small enough to stay < 0 when added with any offset.
#   An offset is in the range -2^57:2^57 (64-bits architectures)
#   or -2^26:2^26 (32-bits architectures)
# + when the offset is NO_OFFSET, the bits field *must* be empty
# + NO_OFFSET could be made to be > 0, but a negative one allows
#   a small optimization in the in(x, ::BitSet) method

mutable struct BitSet <: AbstractSet{Int}
    const bits::Vector{UInt64}
    # 1st stored Int equals 64*offset
    offset::Int

    function BitSet()
        a = Vector{UInt64}(undef, 4) # start with some initial space for holding 0:255 without additional allocations later
        setfield!(a, :size, (0,)) # aka `empty!(a)` inlined
        return new(a, NO_OFFSET)
   end
end

"""
    BitSet([itr])

Construct a sorted set of `Int`s generated by the given iterable object, or an
empty set. Implemented as a bit string, and therefore designed for dense integer sets.
If the set will be sparse (for example, holding a few
very large integers), use [`Set`](@ref) instead.
"""
BitSet(itr) = union!(BitSet(), itr)

# Special implementation for BitSet, which lacks a fast `length` method.
function union!(s::BitSet, itr)
    for x in itr
        push!(s, x)
    end
    return s
end

@inline intoffset(s::BitSet) = s.offset << 6

empty(s::BitSet, ::Type{Int}=Int) = BitSet()
emptymutable(s::BitSet, ::Type{Int}=Int) = BitSet()

copy(s1::BitSet) = copy!(BitSet(), s1)
copymutable(s::BitSet) = copy(s)

function copy!(dest::BitSet, src::BitSet)
    resize!(dest.bits, length(src.bits))
    copyto!(dest.bits, src.bits)
    dest.offset = src.offset
    dest
end

function sizehint!(s::BitSet, n::Integer; first::Bool=false, shrink::Bool=true)
    sizehint!(s.bits, (n+63) >> 6; first, shrink)
    s
end

function _bits_getindex(b::Bits, n::Int, offset::Int)
    ci = _div64(n) - offset + 1
    1 <= ci <= length(b) || return false
    @inbounds r = (b[ci] & (one(UInt64) << _mod64(n))) != 0
    r
end

function _bits_findnext(b::Bits, start::Int)
    # start is 0-based
    # @assert start >= 0
    _div64(start) + 1 > length(b) && return -1
    ind = unsafe_bitfindnext(b, start+1)
    ind === nothing ? -1 : ind - 1
end

function _bits_findprev(b::Bits, start::Int)
    # start is 0-based
    # @assert start <= 64 * length(b) - 1
    start >= 0 || return -1
    ind = unsafe_bitfindprev(b, start+1)
    ind === nothing ? -1 : ind - 1
end

# An internal function for setting the inclusion bit for a given integer
@inline function _setint!(s::BitSet, idx::Int, b::Bool)
    cidx = _div64(idx)
    len = length(s.bits)
    diff = cidx - s.offset
    if diff >= len
        b || return s # setting a bit to zero outside the set's bits is a no-op

        # we put the following test within one of the two branches,
        # with the NO_OFFSET trick, to avoid having to perform it at
        # each and every call to _setint!
        if s.offset == NO_OFFSET # initialize the offset
            # we assume isempty(s.bits)
            s.offset = cidx
            diff = 0
        end
        _growend0!(s.bits, diff - len + 1)
    elseif diff < 0
        b || return s
        _growbeg0!(s.bits, -diff)
        s.offset += diff
        diff = 0
    end
    _unsafe_bitsetindex!(s.bits, b, diff+1, _mod64(idx))
    s
end


# An internal function to resize a Bits object and ensure the newly allocated
# elements are zeroed (will become unnecessary if this behavior changes)
@inline function _growend0!(b::Bits, nchunks::Int)
    len = length(b)
    _growend!(b, nchunks)
    for i in len+1:length(b)
        @inbounds b[i] = CHK0 # resize! gives dirty memory
    end
end

@inline function _growbeg0!(b::Bits, nchunks::Int)
    _growbeg!(b, nchunks)
    for i in 1:nchunks
        @inbounds b[i] = CHK0
    end
end

function union!(s::BitSet, r::AbstractUnitRange{<:Integer})
    isempty(r) && return s
    a, b = Int(first(r)), Int(last(r))
    cidxa = _div64(a)
    cidxb = _div64(b)
    if s.offset == NO_OFFSET
        s.offset = cidxa
    end
    len = length(s.bits)
    diffa = cidxa - s.offset
    diffb = cidxb - s.offset

    # grow s.bits as necessary
    if diffb >= len
        _growend0!(s.bits, diffb - len + 1)
    end
    if diffa < 0
        _growbeg0!(s.bits, -diffa)
        s.offset = cidxa # s.offset += diffa
        diffb -= diffa
        diffa = 0
    end

    # update s.bits
    i = _mod64(a)
    j = _mod64(b)
    @inbounds if diffa == diffb
        s.bits[diffa + 1] |= (((~CHK0) >> i) << (i+63-j)) >> (63-j)
    else
        s.bits[diffa + 1] |= ((~CHK0) >> i) << i
        s.bits[diffb + 1] |= (~CHK0  << (63-j)) >> (63-j)
        for n = diffa+1:diffb-1
            s.bits[n+1] = ~CHK0
        end
    end
    s
end

function _matched_map!(f, s1::BitSet, s2::BitSet)
    left_false_is_false = f(false, false) == f(false, true) == false
    right_false_is_false = f(false, false) == f(true, false) == false

    # we must first handle the NO_OFFSET case; we could test for
    # isempty(s1) but it can be costly, so the user has to call
    # empty!(s1) herself before-hand to re-initialize to NO_OFFSET
    if s1.offset == NO_OFFSET
        return left_false_is_false ? s1 : copy!(s1, s2)
    elseif s2.offset == NO_OFFSET
        return right_false_is_false ? empty!(s1) : s1
    end
    s1.offset = _matched_map!(f, s1.bits, s1.offset, s2.bits, s2.offset,
                              left_false_is_false, right_false_is_false)
    s1
end

# An internal function that takes a pure function `f` and maps across two BitArrays
# allowing the lengths and offsets to be different and altering b1 with the result
# WARNING: the assumptions written in the else clauses must hold
function _matched_map!(f, a1::Bits, b1::Int, a2::Bits, b2::Int,
                       left_false_is_false::Bool, right_false_is_false::Bool)
    l1, l2 = length(a1), length(a2)
    bdiff = b2 - b1
    e1, e2 = l1+b1, l2+b2
    ediff = e2 - e1

    # map! over the common indices
    @inbounds for i = max(1, 1+bdiff):min(l1, l2+bdiff)
        a1[i] = f(a1[i], a2[i-bdiff])
    end

    if ediff > 0
        if left_false_is_false
            # We don't need to worry about the trailing bits — they're all false
        else # @assert f(false, x) == x
            _growend!(a1, ediff)
            # if a1 and a2 are not overlapping, we infer implied "false" values from a2
            for outer l1 = l1+1:bdiff
                @inbounds a1[l1] = CHK0
            end
            # update ediff in case l1 was updated
            ediff = e2 - l1 - b1
            # copy actual chunks from a2
            unsafe_copyto!(a1, l1+1, a2, l2+1-ediff, ediff)
            l1 = length(a1)
        end
    elseif ediff < 0
        if right_false_is_false
            # We don't need to worry about the trailing bits — they're all false
            _deleteend!(a1, min(l1, -ediff))
            # no need to update l1, as if bdiff > 0 (case below), then bdiff will
            # be smaller anyway than an updated l1
        else # @assert f(x, false) == x
            # We don't need to worry about the trailing bits — they already have the
            # correct value
        end
    end

    if bdiff < 0
        if left_false_is_false
            # We don't need to worry about the leading bits — they're all false
        else # @assert f(false, x) == x
            _growbeg!(a1, -bdiff)
            # if a1 and a2 are not overlapping, we infer implied "false" values from a2
            for i = l2+1:-bdiff
                @inbounds a1[i] = CHK0
            end
            b1 += bdiff # updated return value

            # copy actual chunks from a2
            unsafe_copyto!(a1, 1, a2, 1, min(-bdiff, l2))
        end
    elseif bdiff > 0
        if right_false_is_false
            # We don't need to worry about the trailing bits — they're all false
            _deletebeg!(a1, min(l1, bdiff))
            b1 += bdiff
        else # @assert f(x, false) == x
            # We don't need to worry about the trailing bits — they already have the
            # correct value
        end
    end
    b1 # the new offset
end

@inline push!(s::BitSet, n::Integer) = _setint!(s, Int(n), true)

push!(s::BitSet, ns::Integer...) = (for n in ns; push!(s, n); end; s)

@inline pop!(s::BitSet) = pop!(s, last(s))

@inline function pop!(s::BitSet, n::Integer)
    if n in s
        delete!(s, n)
        n
    else
        throw(KeyError(n))
    end
end

@inline function pop!(s::BitSet, n::Integer, default)
    if n in s
        delete!(s, n)
        n
    else
        default
    end
end

@inline _is_convertible_Int(n) = typemin(Int) <= n <= typemax(Int)
@inline delete!(s::BitSet, n::Int) = _setint!(s, n, false)
@inline delete!(s::BitSet, n::Integer) = _is_convertible_Int(n) ? delete!(s, Int(n)) : s

popfirst!(s::BitSet) = pop!(s, first(s))

function empty!(s::BitSet)
    empty!(s.bits)
    s.offset = NO_OFFSET
    s
end

isempty(s::BitSet) = _check0(s.bits, 1, length(s.bits))

# Mathematical set functions: union!, intersect!, setdiff!, symdiff!

union(s::BitSet, sets...) = union!(copy(s), sets...)
union!(s1::BitSet, s2::BitSet) = _matched_map!(|, s1, s2)

intersect(s1::BitSet, s2::BitSet) =
    length(s1.bits) < length(s2.bits) ? intersect!(copy(s1), s2) : intersect!(copy(s2), s1)

intersect!(s1::BitSet, s2::BitSet) = _matched_map!(&, s1, s2)

setdiff!(s1::BitSet, s2::BitSet) = _matched_map!((p, q) -> p & ~q, s1, s2)

function symdiff!(s::BitSet, ns)
    for x in ns
        int_symdiff!(s, x)
    end
    return s
end

function symdiff!(s::BitSet, ns::AbstractSet)
    for x in ns
        int_symdiff!(s, x)
    end
    return s
end

function int_symdiff!(s::BitSet, n::Integer)
    n0 = Int(n)
    val = !(n0 in s)
    _setint!(s, n0, val)
    s
end

symdiff!(s1::BitSet, s2::BitSet) = _matched_map!(xor, s1, s2)

filter!(f, s::BitSet) = unsafe_filter!(f, s)

@inline in(n::Int, s::BitSet) = _bits_getindex(s.bits, n, s.offset)
@inline in(n::Integer, s::BitSet) = _is_convertible_Int(n) ? in(Int(n), s) : false

function iterate(s::BitSet, (word, idx) = (CHK0, 0))
    while word == 0
        idx == length(s.bits) && return nothing
        idx += 1
        word = @inbounds s.bits[idx]
    end
    trailing_zeros(word) + (idx - 1 + s.offset) << 6, (_blsr(word), idx)
end

@noinline _throw_bitset_notempty_error() =
    throw(ArgumentError("collection must be non-empty"))

function first(s::BitSet)
    idx = _bits_findnext(s.bits, 0)
    idx == -1 ? _throw_bitset_notempty_error() : idx + intoffset(s)
end

function last(s::BitSet)
    idx = _bits_findprev(s.bits, (length(s.bits) << 6) - 1)
    idx == -1 ? _throw_bitset_notempty_error() : idx + intoffset(s)
end

length(s::BitSet) = bitcount(s.bits) # = mapreduce(count_ones, +, s.bits; init=0)

function show(io::IO, s::BitSet)
    print(io, "BitSet([")
    first = true
    for n in s
        !first && print(io, ", ")
        print(io, n)
        first = false
    end
    print(io, "])")
end

function _check0(a::Vector{UInt64}, b::Int, e::Int)
    @inbounds for i in b:e
        a[i] == CHK0 || return false
    end
    true
end

function ==(s1::BitSet, s2::BitSet)
    # Swap so s1 has always the smallest offset
    if s1.offset > s2.offset
        s1, s2 = s2, s1
    end
    a1 = s1.bits
    a2 = s2.bits
    b1, b2 = s1.offset, s2.offset
    l1, l2 = length(a1), length(a2)
    e1 = l1+b1
    overlap0 = max(0, e1 - b2)
    included = overlap0 >= l2  # whether a2's indices are included in a1's
    overlap  = included ? l2 : overlap0

    # Ensure non-overlap chunks are zero (unlikely)
    _check0(a1, 1, l1-overlap0) || return false
    if included
        _check0(a1, b2-b1+l2+1, l1) || return false
    else
        _check0(a2, 1+overlap, l2) || return false
    end

    # compare overlap values
    if overlap > 0
        t1 = @_gc_preserve_begin a1
        t2 = @_gc_preserve_begin a2
        memcmp(pointer(a1, b2-b1+1), pointer(a2), overlap<<3) == 0 || return false
        @_gc_preserve_end t2
        @_gc_preserve_end t1
    end

    return true
end

function issubset(a::BitSet, b::BitSet)
    n = length(a.bits)
    shift = b.offset - a.offset
    i, j = shift, shift + length(b.bits)

    f(a, b) = a == a & b
    return (
        all(@inbounds iszero(a.bits[i]) for i in 1:min(n, i)) &&
        all(@inbounds f(a.bits[i], b.bits[i - shift]) for i in max(1, i+1):min(n, j)) &&
        all(@inbounds iszero(a.bits[i]) for i in max(1, j+1):n))
end
⊊(a::BitSet, b::BitSet) = a <= b && a != b


minimum(s::BitSet) = first(s)
maximum(s::BitSet) = last(s)
extrema(s::BitSet) = (first(s), last(s))
issorted(s::BitSet) = true

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	const Bits = Vector{UInt64}
4	const CHK0 = zero(UInt64)
5	const NO_OFFSET = Int === Int64 ? -one(Int) << 60 : -one(Int) << 29
6	# + NO_OFFSET must be small enough to stay < 0 when added with any offset.
7	# An offset is in the range -2^57:2^57 (64-bits architectures)
8	# or -2^26:2^26 (32-bits architectures)
9	# + when the offset is NO_OFFSET, the bits field must be empty
10	# + NO_OFFSET could be made to be > 0, but a negative one allows
11	# a small optimization in the in(x, ::BitSet) method
12
13	mutable struct BitSet <: AbstractSet{Int}
14	const bits::Vector{UInt64}
15	# 1st stored Int equals 64*offset
16	offset::Int
17
18	function BitSet()
19	a = Vector{UInt64}(undef, 4) # start with some initial space for holding 0:255 without additional allocations later	1,624,250✔
20	setfield!(a, :size, (0,)) # aka `empty!(a)` inlined	1,624,250✔
21	return new(a, NO_OFFSET)	1,624,250✔
22	end
23	end
24
25	"""
26	BitSet([itr])
27
28	Construct a sorted set of `Int`s generated by the given iterable object, or an
29	empty set. Implemented as a bit string, and therefore designed for dense integer sets.
30	If the set will be sparse (for example, holding a few
31	very large integers), use [`Set`](@ref) instead.
32	"""
33	BitSet(itr) = union!(BitSet(), itr)	179,045✔
34
35	# Special implementation for BitSet, which lacks a fast `length` method.
36	function union!(s::BitSet, itr)	42,978✔
37	for x in itr	43,019✔
38	push!(s, x)	44,697✔
39	end	46,462✔
40	return s	42,978✔
41	end
42
43	@inline intoffset(s::BitSet) = s.offset << 6	11,000✔
44
45	empty(s::BitSet, ::Type{Int}=Int) = BitSet()	×
46	emptymutable(s::BitSet, ::Type{Int}=Int) = BitSet()	11✔
47
48	copy(s1::BitSet) = copy!(BitSet(), s1)	62,029✔
49	copymutable(s::BitSet) = copy(s)	61,980✔
50
51	function copy!(dest::BitSet, src::BitSet)	42,032✔
52	resize!(dest.bits, length(src.bits))	52,040✔
53	copyto!(dest.bits, src.bits)	104,079✔
54	dest.offset = src.offset	52,040✔
55	dest	42,032✔
56	end
57
58	function sizehint!(s::BitSet, n::Integer; first::Bool=false, shrink::Bool=true)	3✔
59	sizehint!(s.bits, (n+63) >> 6; first, shrink)	3✔
60	s	3✔
61	end
62
63	function _bits_getindex(b::Bits, n::Int, offset::Int)
64	ci = _div64(n) - offset + 1	1,042,112✔
65	1 <= ci <= length(b) \|\| return false	1,443,206✔
66	@inbounds r = (b[ci] & (one(UInt64) << _mod64(n))) != 0	641,018✔
67	r	557,907✔
68	end
69
70	function _bits_findnext(b::Bits, start::Int)
71	# start is 0-based
72	# @assert start >= 0
73	_div64(start) + 1 > length(b) && return -1	302,211✔
74	ind = unsafe_bitfindnext(b, start+1)	293,211✔
75	ind === nothing ? -1 : ind - 1	293,211✔
76	end
77
78	function _bits_findprev(b::Bits, start::Int)
79	# start is 0-based
80	# @assert start <= 64 * length(b) - 1
81	start >= 0 \|\| return -1	8,974✔
82	ind = unsafe_bitfindprev(b, start+1)	8,974✔
83	ind === nothing ? -1 : ind - 1	17,948✔
84	end
85
86	# An internal function for setting the inclusion bit for a given integer
87	@inline function _setint!(s::BitSet, idx::Int, b::Bool)
88	cidx = _div64(idx)	2,413,679✔
89	len = length(s.bits)	2,413,696✔
90	diff = cidx - s.offset	2,413,696✔
91	if diff >= len	2,413,696✔
92	b \|\| return s # setting a bit to zero outside the set's bits is a no-op	801,189✔
93
94	# we put the following test within one of the two branches,
95	# with the NO_OFFSET trick, to avoid having to perform it at
96	# each and every call to _setint!
97	if s.offset == NO_OFFSET # initialize the offset	819,644✔
98	# we assume isempty(s.bits)
99	s.offset = cidx	694,179✔
100	diff = 0	675,860✔
101	end
102	_growend0!(s.bits, diff - len + 1)	829,808✔
103	elseif diff < 0	1,581,004✔
104	b \|\| return s	9✔
105	_growbeg0!(s.bits, -diff)	×
106	s.offset += diff	×
107	diff = 0	×
108	end
109	_unsafe_bitsetindex!(s.bits, b, diff+1, _mod64(idx))	2,400,639✔
110	s	1,871,614✔
111	end
112
113
114	# An internal function to resize a Bits object and ensure the newly allocated
115	# elements are zeroed (will become unnecessary if this behavior changes)
116	@inline function _growend0!(b::Bits, nchunks::Int)
117	len = length(b)	861,676✔
118	_growend!(b, nchunks)	861,676✔
119	for i in len+1:length(b)	1,691,841✔
120	@inbounds b[i] = CHK0 # resize! gives dirty memory	871,840✔
121	end	882,004✔
122	end
123
124	@inline function _growbeg0!(b::Bits, nchunks::Int)
125	_growbeg!(b, nchunks)	×
126	for i in 1:nchunks	×
127	@inbounds b[i] = CHK0	×
128	end	×
129	end
130
131	function union!(s::BitSet, r::AbstractUnitRange{<:Integer})	42,034✔
132	isempty(r) && return s	42,034✔
133	a, b = Int(first(r)), Int(last(r))	42,035✔
134	cidxa = _div64(a)	42,032✔
135	cidxb = _div64(b)	42,032✔
136	if s.offset == NO_OFFSET	42,032✔
137	s.offset = cidxa	42,032✔
138	end
139	len = length(s.bits)	42,032✔
140	diffa = cidxa - s.offset	42,032✔
141	diffb = cidxb - s.offset	42,032✔
142
143	# grow s.bits as necessary
144	if diffb >= len	42,032✔
145	_growend0!(s.bits, diffb - len + 1)	42,032✔
146	end
147	if diffa < 0	42,032✔
148	_growbeg0!(s.bits, -diffa)	×
149	s.offset = cidxa # s.offset += diffa	×
150	diffb -= diffa	×
151	diffa = 0	×
152	end
153
154	# update s.bits
155	i = _mod64(a)	42,032✔
156	j = _mod64(b)	42,032✔
157	@inbounds if diffa == diffb	42,032✔
158	s.bits[diffa + 1] \|= (((~CHK0) >> i) << (i+63-j)) >> (63-j)	42,032✔
159	else
160	s.bits[diffa + 1] \|= ((~CHK0) >> i) << i	×
161	s.bits[diffb + 1] \|= (~CHK0 << (63-j)) >> (63-j)	×
162	for n = diffa+1:diffb-1	×
163	s.bits[n+1] = ~CHK0	×
164	end	×
165	end
166	s	42,032✔
167	end
168
169	function _matched_map!(f, s1::BitSet, s2::BitSet)
170	left_false_is_false = f(false, false) == f(false, true) == false	42,032✔
171	right_false_is_false = f(false, false) == f(true, false) == false	42,032✔
172
173	# we must first handle the NO_OFFSET case; we could test for
174	# isempty(s1) but it can be costly, so the user has to call
175	# empty!(s1) herself before-hand to re-initialize to NO_OFFSET
176	if s1.offset == NO_OFFSET	52,027✔
177	return left_false_is_false ? s1 : copy!(s1, s2)	18✔
178	elseif s2.offset == NO_OFFSET	52,018✔
179	return right_false_is_false ? empty!(s1) : s1	×
180	end
181	s1.offset = _matched_map!(f, s1.bits, s1.offset, s2.bits, s2.offset,	52,018✔
182	left_false_is_false, right_false_is_false)
183	s1	42,032✔
184	end
185
186	# An internal function that takes a pure function `f` and maps across two BitArrays
187	# allowing the lengths and offsets to be different and altering b1 with the result
188	# WARNING: the assumptions written in the else clauses must hold
189	function _matched_map!(f, a1::Bits, b1::Int, a2::Bits, b2::Int,	42,032✔
190	left_false_is_false::Bool, right_false_is_false::Bool)
191	l1, l2 = length(a1), length(a2)	42,032✔
192	bdiff = b2 - b1	42,032✔
193	e1, e2 = l1+b1, l2+b2	42,032✔
194	ediff = e2 - e1	42,032✔
195
196	# map! over the common indices
197	@inbounds for i = max(1, 1+bdiff):min(l1, l2+bdiff)	84,064✔
198	a1[i] = f(a1[i], a2[i-bdiff])	42,032✔
199	end	42,032✔
200
201	if ediff > 0	42,032✔
202	if left_false_is_false	×
203	# We don't need to worry about the trailing bits — they're all false
204	else # @assert f(false, x) == x
205	_growend!(a1, ediff)	×
206	# if a1 and a2 are not overlapping, we infer implied "false" values from a2
207	for outer l1 = l1+1:bdiff	×
208	@inbounds a1[l1] = CHK0	×
209	end	×
210	# update ediff in case l1 was updated
211	ediff = e2 - l1 - b1	×
212	# copy actual chunks from a2
213	unsafe_copyto!(a1, l1+1, a2, l2+1-ediff, ediff)	×
214	l1 = length(a1)	×
215	end
216	elseif ediff < 0	42,032✔
217	if right_false_is_false	×
218	# We don't need to worry about the trailing bits — they're all false
219	_deleteend!(a1, min(l1, -ediff))	×
220	# no need to update l1, as if bdiff > 0 (case below), then bdiff will
221	# be smaller anyway than an updated l1
222	else # @assert f(x, false) == x
223	# We don't need to worry about the trailing bits — they already have the
224	# correct value
225	end
226	end
227
228	if bdiff < 0	42,032✔
229	if left_false_is_false	×
230	# We don't need to worry about the leading bits — they're all false
231	else # @assert f(false, x) == x
232	_growbeg!(a1, -bdiff)	×
233	# if a1 and a2 are not overlapping, we infer implied "false" values from a2
234	for i = l2+1:-bdiff	×
235	@inbounds a1[i] = CHK0	×
236	end	×
237	b1 += bdiff # updated return value	×
238
239	# copy actual chunks from a2
240	unsafe_copyto!(a1, 1, a2, 1, min(-bdiff, l2))	×
241	end
242	elseif bdiff > 0	42,032✔
243	if right_false_is_false	×
244	# We don't need to worry about the trailing bits — they're all false
245	_deletebeg!(a1, min(l1, bdiff))	×
246	b1 += bdiff	×
247	else # @assert f(x, false) == x
248	# We don't need to worry about the trailing bits — they already have the
249	# correct value
250	end
251	end
252	b1 # the new offset	42,032✔
253	end
254
255	@inline push!(s::BitSet, n::Integer) = _setint!(s, Int(n), true)	1,916,606✔
256
257	push!(s::BitSet, ns::Integer...) = (for n in ns; push!(s, n); end; s)	4✔
258
259	@inline pop!(s::BitSet) = pop!(s, last(s))	×
260
261	@inline function pop!(s::BitSet, n::Integer)
262	if n in s	87,036✔
263	delete!(s, n)	174,072✔
264	n	87,036✔
265	else
266	throw(KeyError(n))	×
267	end
268	end
269
270	@inline function pop!(s::BitSet, n::Integer, default)	4✔
271	if n in s	4✔
272	delete!(s, n)	2✔
273	n	1✔
274	else
275	default	3✔
276	end
277	end
278
279	@inline _is_convertible_Int(n) = typemin(Int) <= n <= typemax(Int)	6✔
280	@inline delete!(s::BitSet, n::Int) = _setint!(s, n, false)	879,473✔
281	@inline delete!(s::BitSet, n::Integer) = _is_convertible_Int(n) ? delete!(s, Int(n)) : s	2✔
282
283	popfirst!(s::BitSet) = pop!(s, first(s))	×
284
285	function empty!(s::BitSet)
286	empty!(s.bits)	52,188✔
287	s.offset = NO_OFFSET	52,004✔
288	s	42,032✔
289	end
290
291	isempty(s::BitSet) = _check0(s.bits, 1, length(s.bits))	887,144✔
292
293	# Mathematical set functions: union!, intersect!, setdiff!, symdiff!
294
295	union(s::BitSet, sets...) = union!(copy(s), sets...)	8✔
296	union!(s1::BitSet, s2::BitSet) = _matched_map!(\|, s1, s2)	4✔
297
298	intersect(s1::BitSet, s2::BitSet) =	×
299	length(s1.bits) < length(s2.bits) ? intersect!(copy(s1), s2) : intersect!(copy(s2), s1)
300
301	intersect!(s1::BitSet, s2::BitSet) = _matched_map!(&, s1, s2)	4✔
302
303	setdiff!(s1::BitSet, s2::BitSet) = _matched_map!((p, q) -> p & ~q, s1, s2)	230,104✔
304
305	function symdiff!(s::BitSet, ns)	9✔
306	for x in ns	11✔
307	int_symdiff!(s, x)	20✔
308	end	18✔
309	return s	9✔
310	end
311
312	function symdiff!(s::BitSet, ns::AbstractSet)	×
313	for x in ns	×
314	int_symdiff!(s, x)	×
315	end	×
316	return s	×
317	end
318
319	function int_symdiff!(s::BitSet, n::Integer)	18✔
320	n0 = Int(n)	18✔
321	val = !(n0 in s)	18✔
322	_setint!(s, n0, val)	18✔
323	s	18✔
324	end
325
326	symdiff!(s1::BitSet, s2::BitSet) = _matched_map!(xor, s1, s2)	25✔
327
328	filter!(f, s::BitSet) = unsafe_filter!(f, s)	×
329
330	@inline in(n::Int, s::BitSet) = _bits_getindex(s.bits, n, s.offset)	1,041,759✔
331	@inline in(n::Integer, s::BitSet) = _is_convertible_Int(n) ? in(Int(n), s) : false	4✔
332
333	function iterate(s::BitSet, (word, idx) = (CHK0, 0))
334	while word == 0	2,249,662✔
335	idx == length(s.bits) && return nothing	1,061,192✔
336	idx += 1	458,636✔
337	word = @inbounds s.bits[idx]	458,636✔
338	end	458,636✔
339	trailing_zeros(word) + (idx - 1 + s.offset) << 6, (_blsr(word), idx)	581,082✔
340	end
341
342	@noinline _throw_bitset_notempty_error() =	×
343	throw(ArgumentError("collection must be non-empty"))
344
345	function first(s::BitSet)
346	idx = _bits_findnext(s.bits, 0)	4,052✔
347	idx == -1 ? _throw_bitset_notempty_error() : idx + intoffset(s)	2,026✔
348	end
349
350	function last(s::BitSet)
351	idx = _bits_findprev(s.bits, (length(s.bits) << 6) - 1)	17,948✔
352	idx == -1 ? _throw_bitset_notempty_error() : idx + intoffset(s)	8,974✔
353	end
354
355	length(s::BitSet) = bitcount(s.bits) # = mapreduce(count_ones, +, s.bits; init=0)	237,649✔
356
357	function show(io::IO, s::BitSet)	3✔
358	print(io, "BitSet([")	3✔
359	first = true	3✔
360	for n in s	4✔
361	!first && print(io, ", ")	3✔
362	print(io, n)	3✔
363	first = false	3✔
364	end	3✔
365	print(io, "])")	3✔
366	end
367
368	function _check0(a::Vector{UInt64}, b::Int, e::Int)
369	@inbounds for i in b:e	1,228,471✔
370	a[i] == CHK0 \|\| return false	1,390,857✔
371	end	329,538✔
372	true
373	end
374
375	function ==(s1::BitSet, s2::BitSet)	2✔
376	# Swap so s1 has always the smallest offset
377	if s1.offset > s2.offset	2✔
378	s1, s2 = s2, s1	×
379	end
380	a1 = s1.bits	2✔
381	a2 = s2.bits	2✔
382	b1, b2 = s1.offset, s2.offset	2✔
383	l1, l2 = length(a1), length(a2)	2✔
384	e1 = l1+b1	2✔
385	overlap0 = max(0, e1 - b2)	2✔
386	included = overlap0 >= l2 # whether a2's indices are included in a1's	2✔
387	overlap = included ? l2 : overlap0	2✔
388
389	# Ensure non-overlap chunks are zero (unlikely)
390	_check0(a1, 1, l1-overlap0) \|\| return false	2✔
391	if included	2✔
392	_check0(a1, b2-b1+l2+1, l1) \|\| return false	2✔
393	else
394	_check0(a2, 1+overlap, l2) \|\| return false	×
395	end
396
397	# compare overlap values
398	if overlap > 0	2✔
399	t1 = @_gc_preserve_begin a1	2✔
400	t2 = @_gc_preserve_begin a2	2✔
401	memcmp(pointer(a1, b2-b1+1), pointer(a2), overlap<<3) == 0 \|\| return false	2✔
402	@_gc_preserve_end t2	2✔
403	@_gc_preserve_end t1	2✔
404	end
405
406	return true	2✔
407	end
408
409	function issubset(a::BitSet, b::BitSet)	×
410	n = length(a.bits)	×
411	shift = b.offset - a.offset	×
412	i, j = shift, shift + length(b.bits)	×
413
414	f(a, b) = a == a & b	×
415	return (	×
416	all(@inbounds iszero(a.bits[i]) for i in 1:min(n, i)) &&	×
417	all(@inbounds f(a.bits[i], b.bits[i - shift]) for i in max(1, i+1):min(n, j)) &&	×
418	all(@inbounds iszero(a.bits[i]) for i in max(1, j+1):n))	×
419	end
420	⊊(a::BitSet, b::BitSet) = a <= b && a != b	4✔
421
422
423	minimum(s::BitSet) = first(s)	140✔
424	maximum(s::BitSet) = last(s)	17,948✔
425	extrema(s::BitSet) = (first(s), last(s))	×
426	issorted(s::BitSet) = true	×

JuliaLang / julia / #38182

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