• en

Module OpamHeuristic

val resolve : ?verbose:bool -> version_map:int OpamPackage.Map.t -> Cudf.universe -> Cudf.universe -> Cudf.universe -> Cudf_types.vpkg OpamTypes.request -> (Cudf.package OpamTypes.action list, OpamCudf.conflict) OpamTypes.result
Optimized resolution
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| 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.
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 explore : ?verbose:bool -> Cudf.universe -> Cudf.package state_space -> Cudf.package state option
Explore the given package state-space using the brute_force strategy. We assume that all the packages belong to the given universe.
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.