Repository: JuliaLang/julia
File: stdlib/Random/src/misc.jl (Julia)

Code before:
## shuffle & shuffle!

function _tuple_without_element_at_index(tup::(Tuple{T, Vararg{T, N}} where {T}), i::Int) where {N}
    clo = let tup = tup, i = i
        function closure(j::Int)
            k = if j < i
                j
            else
                j + 1
            end
            tup[k]
        end
    end
    ntuple(clo, Val{N}())
end

function shuffle(rng::AbstractRNG, tup::(Tuple{Vararg{T, N}} where {T})) where {N}
    if tup isa Tuple{Any, Vararg}
        let i = rand(rng, Base.OneTo(N))  # Fisher–Yates shuffle
            s = _tuple_without_element_at_index(tup, i)
            t = shuffle(rng, s)
            (tup[i], t...)
        end
    else
        tup
    end::typeof(tup)
end

function shuffle(tup::NTuple)
    shuffle(default_rng(), tup)
end

"""
    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

Review comment (security):
It's also possible to rely on `Memory` getting stack-allocated, avoiding recursion:

```suggestion
function shuffle(rng::AbstractRNG, tup::(Tuple{Vararg{T, N}} where {T})) where {N}
    if tup isa Tuple{Any, Vararg}
        @inline let  # `@inline` and `@inbounds` are here to help escape analysis
            clo = @inbounds let mem = Memory{UInt16}(undef, N)  # use `UInt16` to save stack space/prevent heap allocation
                copyto!(mem, Base.OneTo(N))
                shuffle!(mem)
                let mem = mem, tup = tup
                    function closure(i::Int)
                        @inbounds tup[mem[i]]
                    end
                end
            end
            ntuple(clo, Val{N}())
        end
```

This suggestion depends on #56847 getting merged first.

Code after:
## shuffle & shuffle!

function shuffle(rng::AbstractRNG, tup::NTuple{N}) where {N}
    # `@inline` and `@inbounds` are here to help escape analysis eliminate the `Memory` allocation
    #
    # * `@inline` might be necessary because escape analysis relies on everything
    #   touching the `Memory` being inlined because there's no interprocedural escape
    #   analysis yet, relevant WIP PR: https://github.com/JuliaLang/julia/pull/56849
    #
    # * `@inbounds` might be necessary because escape analysis requires any throws of
    #   `BoundsError` to be eliminated as dead code, because `BoundsError` stores the
    #   array itself, making the throw escape the array from the function, relevant
    #   WIP PR: https://github.com/JuliaLang/julia/pull/56167
    @inline let
        # use a narrow integer type to save stack space and prevent heap allocation
        Ind = if N ≤ typemax(UInt8)
            UInt8
        elseif N ≤ typemax(UInt16)
            UInt16
        else
            UInt
        end
        mem = @inbounds randperm!(rng, Memory{Ind}(undef, N))
        function closure(i::Int)
            @inbounds tup[mem[i]]
        end
        ntuple(closure, Val{N}())
    end
end

"""
    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
```