requirement sort

requirement_sort.jl

const _default_lookup = UInt64[]
function sort_required_modules(requires::Vector{Pair{Base.PkgId, Base.PkgId}}, required_modules::Vector{Pair{Base.PkgId, UInt64}})
    require_orders =
        let require_orders = unique!(Base.PkgId[req.second for req in requires])
            @view require_orders[1:end]  # make 'require_orders' type-stable 
        end

    require_lookup = Dict{Base.PkgId, Vector{UInt64}}()

    for (req, build_id) in required_modules
        build_ids = get!(require_lookup, req) do
            UInt64[]
        end
        push!(build_ids, build_id)
    end

    result_ptr = 1
    result = Vector{Pair{Base.PkgId, UInt64}}(undef, length(required_modules))
    
    for i = 1:length(required_modules)
        (pkgid, _) = required_modules[i]
        j = findfirst(x -> x == pkgid, require_orders)
        if j !== nothing && j !== 1
            for k = 1:j-1
                dep_pkgid = require_orders[k]
                for build_id in pop!(require_lookup, dep_pkgid, _default_lookup)
                    result[result_ptr] = dep_pkgid => build_id
                    result_ptr += 1
                end
            end
            require_orders = @view require_orders[j+1:end]
        end
        for build_id in pop!(require_lookup, pkgid, _default_lookup)
            result[result_ptr] = pkgid => build_id
            result_ptr += 1
        end
    end
    result
end