Over the last few months, I have written several posts on the package installation graphs specifically, Topological Sort of Packages, Installation order for opam packages and Transitive Reduction of Package Graph. In this post, I’d like to cover a alternative ordering solution.
Considering the graph above, first presented in the Topological Sort of Packages, which produces the installation order below.
- base-threads.base
- base-unix.base
- ocaml-variants
- ocaml-config
- ocaml
- dune
The code presented processed nodes when all their dependencies are satisfied (i.e., when their in-degree becomes 0). This typically means we process “leaf” nodes (nodes with no dependencies) first and then work our way up. However, it may make sense to process the leaf packages only when required rather than as soon as they can be processed. The easiest way to achieve this is to reverse the edges in the DAG, perform the topological sort, and then install the pages in reverse order.
let reverse_dag (dag : PackageSet.t PackageMap.t) : PackageSet.t PackageMap.t =
let initial_reversed = PackageMap.fold (fun package _ acc ->
PackageMap.add package PackageSet.empty acc
) dag PackageMap.empty in
PackageMap.fold (fun package dependencies reversed_dag ->
PackageSet.fold (fun dependency acc ->
let current_dependents = PackageMap.find dependency acc in
PackageMap.add dependency (PackageSet.add package current_dependents) acc
) dependencies reversed_dag
) dag initial_reversed
With such a function, we can write this:
reverse_dag dune |> topological_sort |> List.rev
- ocaml-variants
- ocaml-config
- ocaml
- base-unix.base
- base-threads.base
- dune
Now, we don’t install base-unix and base-threads until they are actually required for the installation of dune.