Module OpamHeuristic
type 'a state = 'a list
A state. In our case, it is a list package we would like to see
installed.
type 'a state_space = 'a array list
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.
val zero : int -> int state
zero n
returns the tuple with n
zeros, which is the first
state to explore.
val succ : bounds:int list -> int state -> int state option
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:
- it is complete, eg. all the state are enumerated until
None
is returned.
- it it monotonous: the sum of components always increase, eg.
|succ x| >= |x|
, where|None|
ismax_int
,|Some x| = |x|
and|(x_1,...,x_n) = x_1 + ... + x_n|
.
val brute_force : ?verbose:bool -> dump:'a state -> unit -> 'a state -> bool -> 'a state_space -> 'a state option
explore is_constent state_space
explore a state space by
implicitely enumerating all the state in a sensitive order.
val state_space : ?filters:Cudf_types.pkgname -> Cudf_types.constr -> Cudf.universe -> Cudf_types.vpkglist -> Cudf_types.pkgname list -> Cudf.package state_space
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).
val state_of_request : ?verbose:bool -> version_map:int OpamPackage.Map.t -> Cudf.universe -> Cudf_types.vpkg OpamTypes.request -> Cudf.package state option
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.
val actions_of_state : version_map:int OpamPackage.Map.t -> Cudf.universe -> Cudf.universe -> Cudf.universe -> Cudf_types.vpkg OpamTypes.request -> Cudf.package state -> Cudf.package OpamTypes.action list
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.