#37474

pending completion

Build # #37474

Build Type

push

local

Committed by

web-flow

Commit Message

irinterp: Allow setting all IR flags (#48993)

Currently, `IR_FLAG_NOTHROW` is the only flag that irinterp is allowed to
set on statements, under the assumption that in order for a call to
be irinterp-eligible, it must have been proven `:foldable`, thus `:effect_free`,
and thus `IR_FLAG_EFFECT_FREE` was assumed to have been set. That reasoning
was sound at the time this code was written, but have since introduced
`EFFECT_FREE_IF_INACCESSIBLEMEMONLY`, which breaks the reasoning that
an `:effect_free` inference for the whole function implies the flag on
every statement. As a result, we were failing to DCE otherwise dead
statements if the IR came from irinterp.

Run Details

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

70258 of 82316 relevant lines covered (85.35%)

32461773.51 hits per line

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

96.23

/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

    BitSet() = new(sizehint!(zeros(UInt64, 0), 4), NO_OFFSET)
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

eltype(::Type{BitSet}) = Int

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

sizehint!(s::BitSet, n::Integer) = (sizehint!(s.bits, (n+63) >> 6); s)

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

JuliaLang / julia / #37474

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