Skip to content

Instantly share code, notes, and snippets.

@thautwarm
Created July 1, 2022 10:25
Show Gist options
  • Save thautwarm/7105bd273eaefcf8cf43c375497a9b75 to your computer and use it in GitHub Desktop.
Save thautwarm/7105bd273eaefcf8cf43c375497a9b75 to your computer and use it in GitHub Desktop.
requirement sort
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment