Solver heuristics.
This module tries to turn an efficient solution checker (such as the one provided by the dose3 library, writen by J. Vouillon) into a relatively good solution finder.
The method we are using is the following:
Finally, we run all this in a loop, until we reach a fix point. We use a timeout to interrupt too long explorations.
These functions can be used independently of OPAM, so we document them here. It is not expected than any other file in OPAM use them, though.
A state. In our case, it is a list package we would like to see installed.
A state space. In our case, it is a collection of available packages: each cell contains all the versions available for one package, ordered by version.
The hearth of the brute-force algorithm lies here. Wwe want to iterate on the state-space (which can be hudge) and stop the first time we hit a consistant state. This means two things: (i) we don't want to build the full universe before iterating on it; (ii) we need to enumerate the states in a meaningful order, eg. an order which should reflect the optimization criteria we are intersted in.
To overcome this difficulties, we use a monotonous successor
function to compute the next state to test from a given valid
non-consistent state, see succ
for more details.
zero n
returns the tuple with n
zeros, which is the first
state to explore.
Given a list of bounds and a tuple, return the next tuple which satisfies the bounds (each component will be stricly lesser than the bounds). The enumeration respect the following invariant:
None
is
returned.|succ x| >= |x|
, where |None|
is max_int
, |Some x| = |x|
and |(x_1,...,x_n) = x_1 + ... + x_n|
.That enumeration encodes the heuristic we are trying to implement, which is: we first try to install the 'ideal' state, where all packages are installed with their most recent versions; if this does not work, we try to minimize the distance between the ideal state and the solution we are proposing.
explore is_constent state_space
explore a state space by
implicitely enumerating all the state in a sensitive order.
Build a state space from a list of package names. The filter
option helps to reduce the size of the state-space, which is
useful to deal with both user-defined constraints (added on the
command line for instance) and refined requests (see below).
Find a possible good state which satisfies a request. The idea is
call iteratively this function while refining the constraints in
the request until reaching a fix-point. This function tries to
minimize the state to explore, based on the request constraints:
the more constrained request you have, the smaller the state-space
to explore is. Once the state-space is computed using
state_space
, it calls explore
(which will use brute_force
)
to get an approximate solution to the request.
Convert a state into a series of action (withour the full closure
of reinstallations). Raise Not_reachable
is the state is not
reachable. This function is called once we get a consistent state
to build a solution than we can propose to the user.