Module OpamCudf
module Set : sig
Cudf sets
type t
val empty : t
val is_empty : t -> bool
val mem : elt -> t -> bool
val add : elt -> t -> t
val singleton : elt -> t
val remove : elt -> t -> t
val union : t -> t -> t
val inter : t -> t -> t
val diff : t -> t -> t
val compare : t -> t -> int
val equal : t -> t -> bool
val subset : t -> t -> bool
val iter : elt -> unit -> t -> unit
val fold : elt -> 'a -> 'a -> t -> 'a -> 'a
val for_all : elt -> bool -> t -> bool
val exists : elt -> bool -> t -> bool
val filter : elt -> bool -> t -> t
val partition : elt -> bool -> t -> (t * t)
val cardinal : t -> int
val elements : t -> elt list
val min_elt : t -> elt
val max_elt : t -> elt
val choose : t -> elt
val split : elt -> t -> (t * bool * t)
val map : elt -> elt -> t -> t
auto-map
val choose_one : t -> elt
Return one element. Fail if the set is not a singleton.
val of_list : elt list -> t
Make a set from a list
val to_string : t -> string
Pretty-print a set
val find : elt -> bool -> t -> elt
Find an element in the list
module Op : sig
val (++) : t -> t -> t
Infix set union
val (--) : t -> t -> t
Infix set difference
val (%%) : t -> t -> t
Infix set intersection
end
end
module Map : sig
Cudf maps
type 'a t
val empty : 'a t
val is_empty : 'a t -> bool
val mem : key -> 'a t -> bool
val add : key -> 'a -> 'a t -> 'a t
val singleton : key -> 'a -> 'a t
val remove : key -> 'a t -> 'a t
val merge : key -> 'a option -> 'b option -> 'c option -> 'a t -> 'b t -> 'c t
val compare : 'a -> 'a -> int -> 'a t -> 'a t -> int
val equal : 'a -> 'a -> bool -> 'a t -> 'a t -> bool
val iter : key -> 'a -> unit -> 'a t -> unit
val fold : key -> 'a -> 'b -> 'b -> 'a t -> 'b -> 'b
val for_all : key -> 'a -> bool -> 'a t -> bool
val exists : key -> 'a -> bool -> 'a t -> bool
val filter : key -> 'a -> bool -> 'a t -> 'a t
val partition : key -> 'a -> bool -> 'a t -> ('a t * 'a t)
val cardinal : 'a t -> int
val bindings : 'a t -> (key * 'a) list
val min_binding : 'a t -> (key * 'a)
val max_binding : 'a t -> (key * 'a)
val choose : 'a t -> (key * 'a)
val split : key -> 'a t -> ('a t * 'a option * 'a t)
val find : key -> 'a t -> 'a
val map : 'a -> 'b -> 'a t -> 'b t
val mapi : key -> 'a -> 'b -> 'a t -> 'b t
val to_string : 'a -> string -> 'a t -> string
Pretty-printing
val values : 'a t -> 'a list
Return the values in the map.
val keys : 'a t -> key list
Return the keys in the map.
val union : 'a -> 'a -> 'a -> 'a t -> 'a t -> 'a t
A key will be in the union of
m1
and m2
if it is appears
either m1
or m2
, with the corresponding value. If a key
appears in both m1
and m2
, then the resulting value is built
using the function given as argument.
val of_list : (key * 'a) list -> 'a t
Convert an assoc list to a map
end
module Graph : sig
Cudf graph
type t
Graph of cudf packages
val transitive_closure : t -> t
Return the transitive closure of
g
end
module Diff : sig
Difference between universes
type package = {
installed : Set.t;
removed : Set.t;
reinstalled : Set.t;
}
Differences between the versions of a given package
end
module ActionGraph : sig
Cudf action graph
type t
Abstract type of graphs
module V : sig
Vertices have type
V.t
and are labeled with type V.label
(note that an implementation may identify the vertex with its
label)
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label
val create : label -> t
val label : t -> label
end
type vertex = V.t
module E : sig
Edges have type
E.t
and are labeled with type E.label
.
src
(resp. dst
) returns the origin (resp. the destination) of a
given edge.
type t
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2
creates an edge from v1
to v2
with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val is_directed : bool
Is this an implementation of directed graphs?
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
out_degree g v
returns the out-degree of v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val in_degree : t -> vertex -> int
in_degree g v
returns the in-degree of v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2
returns the edge from v1
to v2
if it exists.
Unspecified behaviour if g
has several edges from v1
to v2
.
Raises
Not_found
if no such edge exists.
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
succ g v
returns the successors of v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val pred : t -> vertex -> vertex list
pred g v
returns the predecessors of v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val succ_e : t -> vertex -> edge list
succ_e g v
returns the edges going from v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val pred_e : t -> vertex -> edge list
pred_e g v
returns the edges going to v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val iter_vertex : vertex -> unit -> t -> unit
Iter on all vertices of a graph.
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all vertices of a graph.
val iter_edges : vertex -> vertex -> unit -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
val fold_edges : vertex -> vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph. Edge label is ignored.
val iter_edges_e : edge -> unit -> t -> unit
Iter on all edges of a graph.
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph.
val map_vertex : vertex -> vertex -> t -> t
Map on all vertices of a graph.
val iter_succ : vertex -> unit -> t -> vertex -> unit
val iter_pred : vertex -> unit -> t -> vertex -> unit
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val fold_pred : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_succ_e : edge -> unit -> t -> vertex -> unit
val fold_succ_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_pred_e : edge -> unit -> t -> vertex -> unit
val fold_pred_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val create : ?size:int -> unit -> t
create ()
returns an empty graph. Optionally, a size can be
given, which should be on the order of the expected number of
vertices that will be in the graph (for hash tables-based
implementations). The graph grows as needed, so size
is
just an initial guess.
val clear : t -> unit
val copy : t -> t
copy g
returns a copy of g
. Vertices and edges (and eventually
marks, see module Mark
) are duplicated.
val add_vertex : t -> vertex -> unit
add_vertex g v
adds the vertex v
to the graph g
.
Do nothing if v
is already in g
.
val remove_vertex : t -> vertex -> unit
Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
remove g v
removes the vertex v
from the graph g
(and all the edges going from v
in g
).
Do nothing if v
is not in g
.Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
val add_edge : t -> vertex -> vertex -> unit
add_edge g v1 v2
adds an edge from the vertex v1
to the vertex v2
in the graph g
.
Add also v1
(resp. v2
) in g
if v1
(resp. v2
) is not in g
.
Do nothing if this edge is already in g
.
val add_edge_e : t -> edge -> unit
add_edge_e g e
adds the edge e
in the graph g
.
Add also E.src e
(resp. E.dst e
) in g
if E.src e
(resp. E.dst
e
) is not in g
.
Do nothing if e
is already in g
.
val remove_edge : t -> vertex -> vertex -> unit
remove_edge g v1 v2
removes the edge going from v1
to v2
from the
graph g
. If the graph is labelled, all the edges going from v1
to
v2
are removed from g
.
Do nothing if this edge is not in g
.
Raises
Invalid_argument
if v1
or v2
are not in g
.
val remove_edge_e : t -> edge -> unit
remove_edge_e g e
removes the edge e
from the graph g
.
Do nothing if e
is not in g
.
Raises
Invalid_argument
if E.src e
or E.dst e
are not in g
.
type g = t
val transitive_closure : ?reflexive:bool -> g -> g
transitive_closure ?reflexive g
returns the transitive closure
of g
(as a new graph). Loops (i.e. edges from a vertex to itself)
are added only if reflexive
is true
(default is false
).
val add_transitive_closure : ?reflexive:bool -> g -> g
add_transitive_closure ?reflexive g
replaces g
by its
transitive closure. Meaningless for persistent implementations
(then acts as transitive_closure
).
val transitive_reduction : ?reflexive:bool -> g -> g
transitive_reduction ?reflexive g
returns the transitive reduction
of g
(as a new graph). Loops (i.e. edges from a vertex to itself)
are removed only if reflexive
is true
(default is false
).
val replace_by_transitive_reduction : ?reflexive:bool -> g -> g
replace_by_transitive_reduction ?reflexive g
replaces g
by its
transitive reduction. Meaningless for persistent implementations
(then acts as transitive_reduction
).
val mirror : g -> g
mirror g
returns a new graph which is the mirror image of g
:
each edge from u
to v
has been replaced by an edge from v
to u
.
For undirected graphs, it simply returns g
.
Note: Vertices are shared between g
and mirror g
; you may need to
make a copy of g
before using mirror
val complement : g -> g
complement g
returns a new graph which is the complement of g
:
each edge present in g
is not present in the resulting graph and
vice-versa. Edges of the returned graph are unlabeled.
val intersect : g -> g -> g
intersect g1 g2
returns a new graph which is the intersection of g1
and g2
: each vertex and edge present in g1
*and* g2
is present
in the resulting graph.
val union : g -> g -> g
union g1 g2
returns a new graph which is the union of g1
and g2
:
each vertex and edge present in g1
*or* g2
is present in the
resulting graph.
module Topological : sig
val fold : V.t -> 'a -> 'a -> t -> 'a -> 'a
val iter : V.t -> unit -> t -> unit
end
module Parallel : sig
module G : sig
type t = t
module V : sig
Vertices have type
V.t
and are labeled with type V.label
(note that an implementation may identify the vertex with its
label)
type t = vertex
val compare : t -> t -> int
val hash : t -> int
val equal : t -> t -> bool
type label
val create : label -> t
val label : t -> label
end
type vertex = V.t
module E : sig
Edges have type
E.t
and are labeled with type E.label
.
src
(resp. dst
) returns the origin (resp. the destination) of a
given edge.
type t
val compare : t -> t -> int
type vertex = vertex
val src : t -> vertex
Edge origin.
val dst : t -> vertex
Edge destination.
type label
val create : vertex -> label -> vertex -> t
create v1 l v2
creates an edge from v1
to v2
with label l
val label : t -> label
Get the label of an edge.
end
type edge = E.t
val is_directed : bool
Is this an implementation of directed graphs?
val is_empty : t -> bool
val nb_vertex : t -> int
val nb_edges : t -> int
val out_degree : t -> vertex -> int
out_degree g v
returns the out-degree of v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val in_degree : t -> vertex -> int
in_degree g v
returns the in-degree of v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val mem_vertex : t -> vertex -> bool
val mem_edge : t -> vertex -> vertex -> bool
val mem_edge_e : t -> edge -> bool
val find_edge : t -> vertex -> vertex -> edge
find_edge g v1 v2
returns the edge from v1
to v2
if it exists.
Unspecified behaviour if g
has several edges from v1
to v2
.
Raises
Not_found
if no such edge exists.
val find_all_edges : t -> vertex -> vertex -> edge list
val succ : t -> vertex -> vertex list
succ g v
returns the successors of v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val pred : t -> vertex -> vertex list
pred g v
returns the predecessors of v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val succ_e : t -> vertex -> edge list
succ_e g v
returns the edges going from v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val pred_e : t -> vertex -> edge list
pred_e g v
returns the edges going to v
in g
.
Raises
Invalid_argument
if v
is not in g
.
val fold_vertex : vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all vertices of a graph.
val iter_edges : vertex -> vertex -> unit -> t -> unit
Iter on all edges of a graph. Edge label is ignored.
val fold_edges : vertex -> vertex -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph. Edge label is ignored.
val iter_edges_e : edge -> unit -> t -> unit
Iter on all edges of a graph.
val fold_edges_e : edge -> 'a -> 'a -> t -> 'a -> 'a
Fold on all edges of a graph.
val map_vertex : vertex -> vertex -> t -> t
Map on all vertices of a graph.
val iter_pred : vertex -> unit -> t -> vertex -> unit
val fold_succ : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val fold_pred : vertex -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_succ_e : edge -> unit -> t -> vertex -> unit
val fold_succ_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val iter_pred_e : edge -> unit -> t -> vertex -> unit
val fold_pred_e : edge -> 'a -> 'a -> t -> vertex -> 'a -> 'a
val create : ?size:int -> unit -> t
create ()
returns an empty graph. Optionally, a size can be
given, which should be on the order of the expected number of
vertices that will be in the graph (for hash tables-based
implementations). The graph grows as needed, so size
is
just an initial guess.
val clear : t -> unit
val copy : t -> t
copy g
returns a copy of g
. Vertices and edges (and eventually
marks, see module Mark
) are duplicated.
val add_vertex : t -> vertex -> unit
add_vertex g v
adds the vertex v
to the graph g
.
Do nothing if v
is already in g
.
val remove_vertex : t -> vertex -> unit
Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
remove g v
removes the vertex v
from the graph g
(and all the edges going from v
in g
).
Do nothing if v
is not in g
.Time complexity for ocamlgraph implementations: O(|V|*ln(D)) for unlabeled graphs and O(|V|*D) for labeled graphs. D is the maximal degree of the graph.
val add_edge : t -> vertex -> vertex -> unit
add_edge g v1 v2
adds an edge from the vertex v1
to the vertex v2
in the graph g
.
Add also v1
(resp. v2
) in g
if v1
(resp. v2
) is not in g
.
Do nothing if this edge is already in g
.
val add_edge_e : t -> edge -> unit
add_edge_e g e
adds the edge e
in the graph g
.
Add also E.src e
(resp. E.dst e
) in g
if E.src e
(resp. E.dst
e
) is not in g
.
Do nothing if e
is already in g
.
val remove_edge : t -> vertex -> vertex -> unit
remove_edge g v1 v2
removes the edge going from v1
to v2
from the
graph g
. If the graph is labelled, all the edges going from v1
to
v2
are removed from g
.
Do nothing if this edge is not in g
.
Raises
Invalid_argument
if v1
or v2
are not in g
.
val remove_edge_e : t -> edge -> unit
remove_edge_e g e
removes the edge e
from the graph g
.
Do nothing if e
is not in g
.
Raises
Invalid_argument
if E.src e
or E.dst e
are not in g
.
val iter_vertex : V.t -> unit -> t -> unit
val iter_succ : V.t -> unit -> t -> V.t -> unit
val has_cycle : t -> bool
val scc_list : t -> V.t list list
val string_of_vertex : V.t -> string
end
val iter : int -> G.t -> pre:G.V.t -> unit -> child:G.V.t -> unit -> post:G.V.t -> unit -> unit
val iter_l : int -> G.vertex list -> pre:G.V.t -> unit -> child:G.V.t -> unit -> post:G.V.t -> unit -> unit
val map_reduce : int -> G.t -> map:G.V.t -> 'a -> merge:'a -> 'a -> 'a -> init:'a -> 'a
val map_reduce_l : int -> G.vertex list -> map:G.V.t -> 'a -> merge:'a -> 'a -> 'a -> init:'a -> 'a
val create : G.V.t list -> G.t
exception Cyclic of G.V.t list list
end
end
type conflict
Abstract type that may be returned in case of conflicts
val check_request : ?explain:bool -> version_map:int OpamPackage.Map.t -> Cudf.universe -> Cudf_types.vpkg OpamTypes.request -> (Cudf.universe, conflict) OpamTypes.result
Check if a request is satisfiable and return the reasons why not unless
explain
is set to false
val get_final_universe : version_map:int OpamPackage.Map.t -> Cudf.universe -> Cudf_types.vpkg OpamTypes.request -> (Cudf.universe, conflict) OpamTypes.result
Compute the final universe state using the external solver.
val actions_of_diff : Diff.universe -> Cudf.package OpamTypes.action list
Compute the list of actions to match the difference between two
universe. Remark: the result order is unspecified, ie. need to use
solution_of_actions
to get a solution which respects the
topological order induced by dependencies.
val solution_of_actions : simple_universe:Cudf.universe -> complete_universe:Cudf.universe -> requested:OpamPackage.Name.Set.t -> Cudf.package OpamTypes.action list -> solution
Computes the actions to process from a solution, from the actions
obtained by a simple universe diff. The 'simple' universe
should not contain build dependencies and will be used for resolution ;
May raise
complete_universe
should include build-deps, it's used for ordering
of actions and, together with the requested
set of package names,
for computing the reasons of the actions.May raise
Cyclic_actions
.
val resolve : extern:bool -> version_map:int OpamPackage.Map.t -> Cudf.universe -> Cudf_types.vpkg OpamTypes.request -> (Cudf.universe, conflict) OpamTypes.result
Resolve a CUDF request. The result is either a conflict holding
an explanation of the error, or a resulting universe.
~extern
specifies whether the external solver should be used
val to_actions : Cudf.universe -> Cudf.universe -> Cudf.universe -> (Cudf.universe, conflict) OpamTypes.result -> (Cudf.package OpamTypes.action list, conflict) OpamTypes.result
Computes a list of actions to proceed from the result of
resolve
.
Note however than the action list is not yet complete: the transitive closure
of reinstallations is not yet completed, as it requires to fold over the
dependency graph in considering the optional dependencies.
The first argument specifies a function that will be applied to the starting
universe before computation: useful to re-add orphan packages.
val remove : Cudf.universe -> Cudf_types.pkgname -> Cudf_types.constr -> Cudf.universe
remove universe name constr
Remove all the packages called
name
satisfying the constraints constr
in the universe
universe
.
val s_source : string
Cudf labels for package fields in the cudf format
(use for the field Cudf.pkg_extra and with Cudf.lookup_package_property)
the original OPAM package name (as string)
the original OPAM package name (as string)
val s_source_number : string
the original OPAM package version (as string)
val s_reinstall : string
a package to be reinstalled (a bool)
val s_installed_root : string
true if this package belongs to the roots
("installed manually") packages
val s_pinned : string
true if the package is pinned to this version
val string_of_vpkgs : Cudf_types.vpkg list -> string
Convert a package constraint to something readable.
val string_of_conflict : OpamTypes.atom -> string -> conflict -> string
Convert a conflict to something readable by the user. The first argument
should return a string like "lwt<3.2.1 is not available because..." when called
on an unavailable package (the reason can't be known this deep in the solver)
val strings_of_conflict : OpamTypes.atom -> string -> conflict -> (string list * string list * string list)
Returns three lists of strings:
- the final reasons why the request can't be satisfied
- the dependency chains explaining it
- the cycles in the actions to process (exclusive with the other two)
val dump_universe : Pervasives.out_channel -> Cudf.universe -> unit
Dumps the given cudf universe to the given channel
val external_solver_available : unit -> bool
External solver
val check_cudf_version : unit -> TODO: a
Runs a test to check the version of the optimisation criteria accepted by
the external solver. Result is cached for subsequent queries.