#37796

Committed 04 Jun 2024 07:33AM UTC coverage: 86.908% (-0.5%) from 87.443%

Build # #37796

Build Type

push

local

Committed by

web-flow

Commit Message

fix missing uuid check on extension when finding the location of an extension (#54658)

in stacked environments with name collisions of extensions, this could
compute the path for the wrong extension

Fixes https://github.com/JuliaLang/Pkg.jl/issues/3906

Run Details

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

608 existing lines in 28 files now uncovered.

76340 of 87840 relevant lines covered (86.91%)

15275359.08 hits per line

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

82.41

/stdlib/Random/src/misc.jl

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

## rand!(::BitArray) && bitrand

function rand!(rng::AbstractRNG, B::BitArray, ::SamplerType{Bool})
    isempty(B) && return B
    Bc = B.chunks
    rand!(rng, Bc)
    Bc[end] &= Base._msk_end(B)
    return B
end

"""
    bitrand([rng=default_rng()], [dims...])

Generate a `BitArray` of random boolean values.

# Examples
```jldoctest
julia> bitrand(Xoshiro(123), 10)
10-element BitVector:
 0
 1
 0
 1
 0
 1
 0
 0
 1
 1
```
"""
bitrand(r::AbstractRNG, dims::Dims)   = rand!(r, BitArray(undef, dims))
bitrand(r::AbstractRNG, dims::Integer...) = rand!(r, BitArray(undef, convert(Dims, dims)))

bitrand(dims::Dims)   = rand!(BitArray(undef, dims))
bitrand(dims::Integer...) = rand!(BitArray(undef, convert(Dims, dims)))


## randstring (often useful for temporary filenames/dirnames)

"""
    randstring([rng=default_rng()], [chars], [len=8])

Create a random string of length `len`, consisting of characters from
`chars`, which defaults to the set of upper- and lower-case letters
and the digits 0-9. The optional `rng` argument specifies a random
number generator, see [Random Numbers](@ref).

# Examples
```jldoctest
julia> Random.seed!(3); randstring()
"Lxz5hUwn"

julia> randstring(Xoshiro(3), 'a':'z', 6)
"iyzcsm"

julia> randstring("ACGT")
"TGCTCCTC"
```

!!! note
    `chars` can be any collection of characters, of type `Char` or
    `UInt8` (more efficient), provided [`rand`](@ref) can randomly
    pick characters from it.
"""
function randstring end

let b = UInt8['0':'9';'A':'Z';'a':'z']
    global randstring

    function randstring(r::AbstractRNG, chars=b, n::Integer=8)
        T = eltype(chars)
        if T === UInt8
            str = Base._string_n(n)
            GC.@preserve str rand!(r, UnsafeView(pointer(str), n), chars)
            return str
        else
            v = Vector{T}(undef, n)
            rand!(r, v, chars)
            return String(v)
        end
    end

    randstring(r::AbstractRNG, n::Integer) = randstring(r, b, n)
    randstring(chars=b, n::Integer=8) = randstring(default_rng(), chars, n)
    randstring(n::Integer) = randstring(default_rng(), b, n)
end


## randsubseq & randsubseq!

# Fill S (resized as needed) with a random subsequence of A, where
# each element of A is included in S with independent probability p.
# (Note that this is different from the problem of finding a random
#  size-m subset of A where m is fixed!)
function randsubseq!(r::AbstractRNG, S::AbstractArray, A::AbstractArray, p::Real)
    require_one_based_indexing(S, A)
    0 <= p <= 1 || throw(ArgumentError("probability $p not in [0,1]"))
    n = length(A)
    p == 1 && return copyto!(resize!(S, n), A)
    empty!(S)
    p == 0 && return S
    nexpected = p * length(A)
    sizehint!(S, round(Int,nexpected + 5*sqrt(nexpected)))
    if p > 0.15 # empirical threshold for trivial O(n) algorithm to be better
        for i = 1:n
            rand(r) <= p && push!(S, A[i])
        end
    else
        # Skip through A, in order, from each element i to the next element i+s
        # included in S. The probability that the next included element is
        # s==k (k > 0) is (1-p)^(k-1) * p, and hence the probability (CDF) that
        # s is in {1,...,k} is 1-(1-p)^k = F(k).   Thus, we can draw the skip s
        # from this probability distribution via the discrete inverse-transform
        # method: s = ceil(F^{-1}(u)) where u = rand(), which is simply
        # s = ceil(log(rand()) / log1p(-p)).
        # -log(rand()) is an exponential variate, so can use randexp().
        L = -1 / log1p(-p) # L > 0
        i = 0
        while true
            s = randexp(r) * L
            s >= n - i && return S # compare before ceil to avoid overflow
            push!(S, A[i += ceil(Int,s)])
        end
        # [This algorithm is similar in spirit to, but much simpler than,
        #  the one by Vitter for a related problem in "Faster methods for
        #  random sampling," Comm. ACM Magazine 7, 703-718 (1984).]
    end
    return S
end

"""
    randsubseq!([rng=default_rng(),] S, A, p)

Like [`randsubseq`](@ref), but the results are stored in `S`
(which is resized as needed).

# Examples
```jldoctest
julia> S = Int64[];

julia> randsubseq!(Xoshiro(123), S, 1:8, 0.3)
2-element Vector{Int64}:
 4
 7

julia> S
2-element Vector{Int64}:
 4
 7
```
"""
randsubseq!(S::AbstractArray, A::AbstractArray, p::Real) = randsubseq!(default_rng(), S, A, p)

randsubseq(r::AbstractRNG, A::AbstractArray{T}, p::Real) where {T} =
    randsubseq!(r, T[], A, p)

"""
    randsubseq([rng=default_rng(),] A, p) -> Vector

Return a vector consisting of a random subsequence of the given array `A`, where each
element of `A` is included (in order) with independent probability `p`. (Complexity is
linear in `p*length(A)`, so this function is efficient even if `p` is small and `A` is
large.) Technically, this process is known as "Bernoulli sampling" of `A`.

# Examples
```jldoctest
julia> randsubseq(Xoshiro(123), 1:8, 0.3)
2-element Vector{Int64}:
 4
 7
```
"""
randsubseq(A::AbstractArray, p::Real) = randsubseq(default_rng(), A, p)


## rand Less Than Masked 52 bits (helper function)

"Return a sampler generating a random `Int` (masked with `mask`) in ``[0, n)``, when `n <= 2^52`."
ltm52(n::Int, mask::Int=nextpow(2, n)-1) = LessThan(n-1, Masked(mask, UInt52Raw(Int)))

## shuffle & shuffle!

"""
    shuffle!([rng=default_rng(),] v::AbstractArray)

In-place version of [`shuffle`](@ref): randomly permute `v` in-place,
optionally supplying the random-number generator `rng`.

# Examples
```jldoctest
julia> shuffle!(Xoshiro(123), Vector(1:10))
10-element Vector{Int64}:
  5
  4
  2
  3
  6
 10
  8
  1
  9
  7
```
"""
function shuffle!(r::AbstractRNG, a::AbstractArray)
    # keep it consistent with `randperm!` and `randcycle!` if possible
    require_one_based_indexing(a)
    n = length(a)
    @assert n <= Int64(2)^52
    n == 0 && return a
    mask = 3
    @inbounds for i = 2:n
        j = 1 + rand(r, ltm52(i, mask))
        a[i], a[j] = a[j], a[i]
        i == 1 + mask && (mask = 2 * mask + 1)
    end
    return a
end

function shuffle!(r::AbstractRNG, a::AbstractArray{Bool})
    old_count = count(a)
    len = length(a)
    uncommon_value = 2old_count <= len
    fuel = uncommon_value ? old_count : len - old_count
    fuel == 0 && return a
    a .= !uncommon_value
    while fuel > 0
        k = rand(r, eachindex(a))
        fuel -= a[k] != uncommon_value
        a[k] = uncommon_value
    end
    a
end

shuffle!(a::AbstractArray) = shuffle!(default_rng(), a)

"""
    shuffle([rng=default_rng(),] v::AbstractArray)

Return a randomly permuted copy of `v`. The optional `rng` argument specifies a random
number generator (see [Random Numbers](@ref)).
To permute `v` in-place, see [`shuffle!`](@ref). To obtain randomly permuted
indices, see [`randperm`](@ref).

# Examples
```jldoctest
julia> shuffle(Xoshiro(123), Vector(1:10))
10-element Vector{Int64}:
  5
  4
  2
  3
  6
 10
  8
  1
  9
  7
```
"""
shuffle(r::AbstractRNG, a::AbstractArray) = shuffle!(r, copymutable(a))
shuffle(a::AbstractArray) = shuffle(default_rng(), a)

shuffle(r::AbstractRNG, a::Base.OneTo) = randperm(r, last(a))

## randperm & randperm!

"""
    randperm([rng=default_rng(),] n::Integer)

Construct a random permutation of length `n`. The optional `rng`
argument specifies a random number generator (see [Random
Numbers](@ref)). The element type of the result is the same as the type
of `n`.

To randomly permute an arbitrary vector, see [`shuffle`](@ref) or
[`shuffle!`](@ref).

!!! compat "Julia 1.1"
    In Julia 1.1 `randperm` returns a vector `v` with `eltype(v) == typeof(n)`
    while in Julia 1.0 `eltype(v) == Int`.

# Examples
```jldoctest
julia> randperm(Xoshiro(123), 4)
4-element Vector{Int64}:
 1
 4
 2
 3
```
"""
randperm(r::AbstractRNG, n::T) where {T <: Integer} = randperm!(r, Vector{T}(undef, n))
randperm(n::Integer) = randperm(default_rng(), n)

"""
    randperm!([rng=default_rng(),] A::Array{<:Integer})

Construct in `A` a random permutation of length `length(A)`. The
optional `rng` argument specifies a random number generator (see
[Random Numbers](@ref)). To randomly permute an arbitrary vector, see
[`shuffle`](@ref) or [`shuffle!`](@ref).

# Examples
```jldoctest
julia> randperm!(Xoshiro(123), Vector{Int}(undef, 4))
4-element Vector{Int64}:
 1
 4
 2
 3
```
"""
function randperm!(r::AbstractRNG, a::Array{<:Integer})
    # keep it consistent with `shuffle!` and `randcycle!` if possible
    n = length(a)
    @assert n <= Int64(2)^52
    n == 0 && return a
    a[1] = 1
    mask = 3
    @inbounds for i = 2:n
        j = 1 + rand(r, ltm52(i, mask))
        if i != j # a[i] is undef (and could be #undef)
            a[i] = a[j]
        end
        a[j] = i
        i == 1 + mask && (mask = 2 * mask + 1)
    end
    return a
end

randperm!(a::Array{<:Integer}) = randperm!(default_rng(), a)


## randcycle & randcycle!

"""
    randcycle([rng=default_rng(),] n::Integer)

Construct a random cyclic permutation of length `n`. The optional `rng`
argument specifies a random number generator, see [Random Numbers](@ref).
The element type of the result is the same as the type of `n`.

Here, a "cyclic permutation" means that all of the elements lie within
a single cycle.  If `n > 0`, there are ``(n-1)!`` possible cyclic permutations,
which are sampled uniformly.  If `n == 0`, `randcycle` returns an empty vector.

[`randcycle!`](@ref) is an in-place variant of this function.

!!! compat "Julia 1.1"
    In Julia 1.1 and above, `randcycle` returns a vector `v` with
    `eltype(v) == typeof(n)` while in Julia 1.0 `eltype(v) == Int`.

# Examples
```jldoctest
julia> randcycle(Xoshiro(123), 6)
6-element Vector{Int64}:
 5
 4
 2
 6
 3
 1
```
"""
randcycle(r::AbstractRNG, n::T) where {T <: Integer} = randcycle!(r, Vector{T}(undef, n))
randcycle(n::Integer) = randcycle(default_rng(), n)

"""
    randcycle!([rng=default_rng(),] A::Array{<:Integer})

Construct in `A` a random cyclic permutation of length `n = length(A)`.
The optional `rng` argument specifies a random number generator, see
[Random Numbers](@ref).

Here, a "cyclic permutation" means that all of the elements lie within a single cycle.
If `A` is nonempty (`n > 0`), there are ``(n-1)!`` possible cyclic permutations,
which are sampled uniformly.  If `A` is empty, `randcycle!` leaves it unchanged.

[`randcycle`](@ref) is a variant of this function that allocates a new vector.

# Examples
```jldoctest
julia> randcycle!(Xoshiro(123), Vector{Int}(undef, 6))
6-element Vector{Int64}:
 5
 4
 2
 6
 3
 1
```
"""
function randcycle!(r::AbstractRNG, a::Array{<:Integer})
    # keep it consistent with `shuffle!` and `randperm!` if possible
    n = length(a)
    @assert n <= Int64(2)^52
    n == 0 && return a
    a[1] = 1
    mask = 3
    # Sattolo's algorithm:
    @inbounds for i = 2:n
        j = 1 + rand(r, ltm52(i-1, mask))
        a[i] = a[j]
        a[j] = i
        i == 1 + mask && (mask = 2 * mask + 1)
    end
    return a
end

randcycle!(a::Array{<:Integer}) = randcycle!(default_rng(), a)

1	# This file is a part of Julia. License is MIT: https://julialang.org/license
2
3	## rand!(::BitArray) && bitrand
4
5	function rand!(rng::AbstractRNG, B::BitArray, ::SamplerType{Bool})
6	isempty(B) && return B	137,374✔
7	Bc = B.chunks	134,415✔
8	rand!(rng, Bc)	134,415✔
9	Bc[end] &= Base._msk_end(B)	134,415✔
10	return B	134,415✔
11	end
12
13	"""
14	bitrand([rng=default_rng()], [dims...])
15
16	Generate a `BitArray` of random boolean values.
17
18	# Examples
19	```jldoctest
20	julia> bitrand(Xoshiro(123), 10)
21	10-element BitVector:
22	0
23	1
24	0
25	1
26	0
27	1
28	0
29	0
30	1
31	1
32	```
33	"""
34	bitrand(r::AbstractRNG, dims::Dims) = rand!(r, BitArray(undef, dims))	×
UNCOV 35	bitrand(r::AbstractRNG, dims::Integer...) = rand!(r, BitArray(undef, convert(Dims, dims)))	×
36
37	bitrand(dims::Dims) = rand!(BitArray(undef, dims))	55✔
38	bitrand(dims::Integer...) = rand!(BitArray(undef, convert(Dims, dims)))	85,492✔
39
40
41	## randstring (often useful for temporary filenames/dirnames)
42
43	"""
44	randstring([rng=default_rng()], [chars], [len=8])
45
46	Create a random string of length `len`, consisting of characters from
47	`chars`, which defaults to the set of upper- and lower-case letters
48	and the digits 0-9. The optional `rng` argument specifies a random
49	number generator, see [Random Numbers](@ref).
50
51	# Examples
52	```jldoctest
53	julia> Random.seed!(3); randstring()
54	"Lxz5hUwn"
55
56	julia> randstring(Xoshiro(3), 'a':'z', 6)
57	"iyzcsm"
58
59	julia> randstring("ACGT")
60	"TGCTCCTC"
61	```
62
63	!!! note
64	`chars` can be any collection of characters, of type `Char` or
65	`UInt8` (more efficient), provided [`rand`](@ref) can randomly
66	pick characters from it.
67	"""
68	function randstring end
69
70	let b = UInt8['0':'9';'A':'Z';'a':'z']
71	global randstring
72
73	function randstring(r::AbstractRNG, chars=b, n::Integer=8)	5,774✔
74	T = eltype(chars)	6,799✔
75	if T === UInt8	6,799✔
76	str = Base._string_n(n)	5,775✔
77	GC.@preserve str rand!(r, UnsafeView(pointer(str), n), chars)	32,791✔
78	return str	5,775✔
79	else
80	v = Vector{T}(undef, n)	2,100✔
81	rand!(r, v, chars)	1,100✔
82	return String(v)	1,100✔
83	end
84	end
85
86	randstring(r::AbstractRNG, n::Integer) = randstring(r, b, n)	1,100✔
87	randstring(chars=b, n::Integer=8) = randstring(default_rng(), chars, n)	402✔
88	randstring(n::Integer) = randstring(default_rng(), b, n)	4,471✔
89	end
90
91
92	## randsubseq & randsubseq!
93
94	# Fill S (resized as needed) with a random subsequence of A, where
95	# each element of A is included in S with independent probability p.
96	# (Note that this is different from the problem of finding a random
97	# size-m subset of A where m is fixed!)
98	function randsubseq!(r::AbstractRNG, S::AbstractArray, A::AbstractArray, p::Real)	2,885✔
99	require_one_based_indexing(S, A)	2,885✔
100	0 <= p <= 1 \|\| throw(ArgumentError("probability $p not in [0,1]"))	2,885✔
101	n = length(A)	2,885✔
102	p == 1 && return copyto!(resize!(S, n), A)	2,885✔
103	empty!(S)	2,863✔
104	p == 0 && return S	2,863✔
105	nexpected = p * length(A)	2,857✔
106	sizehint!(S, round(Int,nexpected + 5*sqrt(nexpected)))	2,857✔
107	if p > 0.15 # empirical threshold for trivial O(n) algorithm to be better	2,857✔
108	for i = 1:n	2,742✔
109	rand(r) <= p && push!(S, A[i])	42,372,330✔
110	end	84,741,918✔
111	else
112	# Skip through A, in order, from each element i to the next element i+s
113	# included in S. The probability that the next included element is
114	# s==k (k > 0) is (1-p)^(k-1) * p, and hence the probability (CDF) that
115	# s is in {1,...,k} is 1-(1-p)^k = F(k). Thus, we can draw the skip s
116	# from this probability distribution via the discrete inverse-transform
117	# method: s = ceil(F^{-1}(u)) where u = rand(), which is simply
118	# s = ceil(log(rand()) / log1p(-p)).
119	# -log(rand()) is an exponential variate, so can use randexp().
120	L = -1 / log1p(-p) # L > 0	115✔
121	i = 0	115✔
122	while true	117,494✔
123	s = randexp(r) * L	117,494✔
124	s >= n - i && return S # compare before ceil to avoid overflow	117,494✔
125	push!(S, A[i += ceil(Int,s)])	117,379✔
126	end	117,379✔
127	# [This algorithm is similar in spirit to, but much simpler than,
128	# the one by Vitter for a related problem in "Faster methods for
129	# random sampling," Comm. ACM Magazine 7, 703-718 (1984).]
130	end
131	return S	2,742✔
132	end
133
134	"""
135	randsubseq!([rng=default_rng(),] S, A, p)
136
137	Like [`randsubseq`](@ref), but the results are stored in `S`
138	(which is resized as needed).
139
140	# Examples
141	```jldoctest
142	julia> S = Int64[];
143
144	julia> randsubseq!(Xoshiro(123), S, 1:8, 0.3)
145	2-element Vector{Int64}:
146	4
147	7
148
149	julia> S
150	2-element Vector{Int64}:
151	4
152	7
153	```
154	"""
155	randsubseq!(S::AbstractArray, A::AbstractArray, p::Real) = randsubseq!(default_rng(), S, A, p)	×
156
157	randsubseq(r::AbstractRNG, A::AbstractArray{T}, p::Real) where {T} =	2,885✔
158	randsubseq!(r, T[], A, p)
159
160	"""
161	randsubseq([rng=default_rng(),] A, p) -> Vector
162
163	Return a vector consisting of a random subsequence of the given array `A`, where each
164	element of `A` is included (in order) with independent probability `p`. (Complexity is
165	linear in `p*length(A)`, so this function is efficient even if `p` is small and `A` is
166	large.) Technically, this process is known as "Bernoulli sampling" of `A`.
167
168	# Examples
169	```jldoctest
170	julia> randsubseq(Xoshiro(123), 1:8, 0.3)
171	2-element Vector{Int64}:
172	4
173	7
174	```
175	"""
176	randsubseq(A::AbstractArray, p::Real) = randsubseq(default_rng(), A, p)	2,131✔
177
178
179	## rand Less Than Masked 52 bits (helper function)
180
181	"Return a sampler generating a random `Int` (masked with `mask`) in ``[0, n)``, when `n <= 2^52`."
182	ltm52(n::Int, mask::Int=nextpow(2, n)-1) = LessThan(n-1, Masked(mask, UInt52Raw(Int)))	53,373✔
183
184	## shuffle & shuffle!
185
186	"""
187	shuffle!([rng=default_rng(),] v::AbstractArray)
188
189	In-place version of [`shuffle`](@ref): randomly permute `v` in-place,
190	optionally supplying the random-number generator `rng`.
191
192	# Examples
193	```jldoctest
194	julia> shuffle!(Xoshiro(123), Vector(1:10))
195	10-element Vector{Int64}:
196	5
197	4
198	2
199	3
200	6
201	10
202	8
203	1
204	9
205	7
206	```
207	"""
208	function shuffle!(r::AbstractRNG, a::AbstractArray)	2,007✔
209	# keep it consistent with `randperm!` and `randcycle!` if possible
210	require_one_based_indexing(a)	2,007✔
211	n = length(a)	2,007✔
212	@assert n <= Int64(2)^52	2,007✔
213	n == 0 && return a	2,007✔
214	mask = 3	2,007✔
215	@inbounds for i = 2:n	2,007✔
216	j = 1 + rand(r, ltm52(i, mask))	19,103✔
217	a[i], a[j] = a[j], a[i]	19,103✔
218	i == 1 + mask && (mask = 2 * mask + 1)	19,103✔
219	end	36,199✔
220	return a	2,007✔
221	end
222
UNCOV 223	function shuffle!(r::AbstractRNG, a::AbstractArray{Bool})	×
UNCOV 224	old_count = count(a)	×
UNCOV 225	len = length(a)	×
UNCOV 226	uncommon_value = 2old_count <= len	×
UNCOV 227	fuel = uncommon_value ? old_count : len - old_count	×
UNCOV 228	fuel == 0 && return a	×
UNCOV 229	a .= !uncommon_value	×
UNCOV 230	while fuel > 0	×
UNCOV 231	k = rand(r, eachindex(a))	×
UNCOV 232	fuel -= a[k] != uncommon_value	×
UNCOV 233	a[k] = uncommon_value	×
UNCOV 234	end	×
UNCOV 235	a	×
236	end
237
238	shuffle!(a::AbstractArray) = shuffle!(default_rng(), a)	2,003✔
239
240	"""
241	shuffle([rng=default_rng(),] v::AbstractArray)
242
243	Return a randomly permuted copy of `v`. The optional `rng` argument specifies a random
244	number generator (see [Random Numbers](@ref)).
245	To permute `v` in-place, see [`shuffle!`](@ref). To obtain randomly permuted
246	indices, see [`randperm`](@ref).
247
248	# Examples
249	```jldoctest
250	julia> shuffle(Xoshiro(123), Vector(1:10))
251	10-element Vector{Int64}:
252	5
253	4
254	2
255	3
256	6
257	10
258	8
259	1
260	9
261	7
262	```
263	"""
264	shuffle(r::AbstractRNG, a::AbstractArray) = shuffle!(r, copymutable(a))	5✔
265	shuffle(a::AbstractArray) = shuffle(default_rng(), a)	5✔
266
267	shuffle(r::AbstractRNG, a::Base.OneTo) = randperm(r, last(a))	×
268
269	## randperm & randperm!
270
271	"""
272	randperm([rng=default_rng(),] n::Integer)
273
274	Construct a random permutation of length `n`. The optional `rng`
275	argument specifies a random number generator (see [Random
276	Numbers](@ref)). The element type of the result is the same as the type
277	of `n`.
278
279	To randomly permute an arbitrary vector, see [`shuffle`](@ref) or
280	[`shuffle!`](@ref).
281
282	!!! compat "Julia 1.1"
283	In Julia 1.1 `randperm` returns a vector `v` with `eltype(v) == typeof(n)`
284	while in Julia 1.0 `eltype(v) == Int`.
285
286	# Examples
287	```jldoctest
288	julia> randperm(Xoshiro(123), 4)
289	4-element Vector{Int64}:
290	1
291	4
292	2
293	3
294	```
295	"""
296	randperm(r::AbstractRNG, n::T) where {T <: Integer} = randperm!(r, Vector{T}(undef, n))	44✔
297	randperm(n::Integer) = randperm(default_rng(), n)	44✔
298
299	"""
300	randperm!([rng=default_rng(),] A::Array{<:Integer})
301
302	Construct in `A` a random permutation of length `length(A)`. The
303	optional `rng` argument specifies a random number generator (see
304	[Random Numbers](@ref)). To randomly permute an arbitrary vector, see
305	[`shuffle`](@ref) or [`shuffle!`](@ref).
306
307	# Examples
308	```jldoctest
309	julia> randperm!(Xoshiro(123), Vector{Int}(undef, 4))
310	4-element Vector{Int64}:
311	1
312	4
313	2
314	3
315	```
316	"""
317	function randperm!(r::AbstractRNG, a::Array{<:Integer})	43✔
318	# keep it consistent with `shuffle!` and `randcycle!` if possible
319	n = length(a)	43✔
320	@assert n <= Int64(2)^52	43✔
321	n == 0 && return a	43✔
322	a[1] = 1	43✔
323	mask = 3	43✔
324	@inbounds for i = 2:n	43✔
325	j = 1 + rand(r, ltm52(i, mask))	34,072✔
326	if i != j # a[i] is undef (and could be #undef)	34,072✔
327	a[i] = a[j]	33,959✔
328	end
329	a[j] = i	34,072✔
330	i == 1 + mask && (mask = 2 * mask + 1)	34,072✔
331	end	68,101✔
332	return a	43✔
333	end
334
UNCOV 335	randperm!(a::Array{<:Integer}) = randperm!(default_rng(), a)	×
336
337
338	## randcycle & randcycle!
339
340	"""
341	randcycle([rng=default_rng(),] n::Integer)
342
343	Construct a random cyclic permutation of length `n`. The optional `rng`
344	argument specifies a random number generator, see [Random Numbers](@ref).
345	The element type of the result is the same as the type of `n`.
346
347	Here, a "cyclic permutation" means that all of the elements lie within
348	a single cycle. If `n > 0`, there are ``(n-1)!`` possible cyclic permutations,
349	which are sampled uniformly. If `n == 0`, `randcycle` returns an empty vector.
350
351	[`randcycle!`](@ref) is an in-place variant of this function.
352
353	!!! compat "Julia 1.1"
354	In Julia 1.1 and above, `randcycle` returns a vector `v` with
355	`eltype(v) == typeof(n)` while in Julia 1.0 `eltype(v) == Int`.
356
357	# Examples
358	```jldoctest
359	julia> randcycle(Xoshiro(123), 6)
360	6-element Vector{Int64}:
361	5
362	4
363	2
364	6
365	3
366	1
367	```
368	"""
369	randcycle(r::AbstractRNG, n::T) where {T <: Integer} = randcycle!(r, Vector{T}(undef, n))	37✔
370	randcycle(n::Integer) = randcycle(default_rng(), n)	37✔
371
372	"""
373	randcycle!([rng=default_rng(),] A::Array{<:Integer})
374
375	Construct in `A` a random cyclic permutation of length `n = length(A)`.
376	The optional `rng` argument specifies a random number generator, see
377	[Random Numbers](@ref).
378
379	Here, a "cyclic permutation" means that all of the elements lie within a single cycle.
380	If `A` is nonempty (`n > 0`), there are ``(n-1)!`` possible cyclic permutations,
381	which are sampled uniformly. If `A` is empty, `randcycle!` leaves it unchanged.
382
383	[`randcycle`](@ref) is a variant of this function that allocates a new vector.
384
385	# Examples
386	```jldoctest
387	julia> randcycle!(Xoshiro(123), Vector{Int}(undef, 6))
388	6-element Vector{Int64}:
389	5
390	4
391	2
392	6
393	3
394	1
395	```
396	"""
397	function randcycle!(r::AbstractRNG, a::Array{<:Integer})	19✔
398	# keep it consistent with `shuffle!` and `randperm!` if possible
399	n = length(a)	19✔
400	@assert n <= Int64(2)^52	19✔
401	n == 0 && return a	19✔
402	a[1] = 1	19✔
403	mask = 3	19✔
404	# Sattolo's algorithm:
405	@inbounds for i = 2:n	19✔
406	j = 1 + rand(r, ltm52(i-1, mask))	198✔
407	a[i] = a[j]	198✔
408	a[j] = i	198✔
409	i == 1 + mask && (mask = 2 * mask + 1)	198✔
410	end	377✔
411	return a	19✔
412	end
413
UNCOV 414	randcycle!(a::Array{<:Integer}) = randcycle!(default_rng(), a)	×

JuliaLang / julia / #37796

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