OCaml implementation of PubGrub
anil.recoil.org
1(** PubGrub: A Dependency Resolution Algorithm
2
3 This library implements the PubGrub algorithm, a next-generation version solving algorithm
4 designed for package managers. It efficiently finds a set of package versions that satisfy
5 all dependencies, or provides a clear explanation of why no solution exists.
6*)
7
8(** {1 Core Types} *)
9
10(** Package identifier. Must be comparable and displayable. *)
11module type PACKAGE_ID = sig
12 type t
13 (** The package identifier type. *)
14
15 val compare : t -> t -> int
16 (** Compare two package identifiers. *)
17
18 val to_string : t -> string
19 (** Convert a package identifier to a string. *)
20end
21
22(** Version type. Must be orderable and displayable. *)
23module type VERSION = sig
24 type t
25 (** The version type. *)
26
27 val compare : t -> t -> int
28 (** Compare two versions. Newer versions should be greater. *)
29
30 val to_string : t -> string
31 (** Convert a version to a string. *)
32end
33
34(** {1 Version Sets and Ranges} *)
35
36(** A set or range of versions. *)
37module type VERSION_SET = sig
38 type t
39 (** The version set type. *)
40
41 type version
42 (** The version type. *)
43
44 val empty : t
45 (** The empty set. *)
46
47 val any : t
48 (** The set of all versions. *)
49
50 val singleton : version -> t
51 (** A set containing exactly one version. *)
52
53 val union : t -> t -> t
54 (** Union of two version sets. *)
55
56 val intersection : t -> t -> t
57 (** Intersection of two version sets. *)
58
59 val complement : t -> t
60 (** Complement of a version set. *)
61
62 val is_empty : t -> bool
63 (** Whether the set is empty. *)
64
65 val contains : version -> t -> bool
66 (** Whether a version is in the set. *)
67
68 val subset_of : t -> t -> bool
69 (** Whether the first set is a subset of the second. *)
70
71 val is_disjoint : t -> t -> bool
72 (** Whether two sets are disjoint. *)
73
74 val to_string : t -> string
75 (** Convert a version set to a string. *)
76end
77
78(** {1 Terms and Constraints} *)
79
80(** A term is either a positive or negative constraint on a package version. *)
81type ('v, 'vs) term =
82 | Positive of 'vs (** The package version must be in this set. *)
83 | Negative of 'vs (** The package version must not be in this set. *)
84
85(** Term operations. *)
86module Term : sig
87 type ('v, 'vs) t = ('v, 'vs) term
88
89 val any : 'vs -> ('v, 'vs) t
90 (** A term that matches any version in the given set. *)
91
92 val empty : 'vs -> ('v, 'vs) t
93 (** A term that matches no version in the given set. *)
94
95 val exact : 'v -> ('v -> 'vs) -> ('v, 'vs) t
96 (** A term requiring exactly this version. *)
97
98 val negate : ('v, 'vs) t -> ('v, 'vs) t
99 (** Negate a term. *)
100
101 val contains : 'v -> ('v -> 'vs -> bool) -> ('v, 'vs) t -> bool
102 (** Whether a version satisfies a term. *)
103
104 val intersection : ('vs -> 'vs -> 'vs) -> ('vs -> 'vs) -> ('v, 'vs) t -> ('v, 'vs) t -> ('v, 'vs) t
105 (** Intersection of two terms. *)
106
107 val union : ('vs -> 'vs -> 'vs) -> ('vs -> 'vs -> 'vs) -> ('vs -> 'vs) -> ('vs -> bool) -> ('v, 'vs) t -> ('v, 'vs) t -> ('v, 'vs) t
108 (** Union of two terms. *)
109
110 val is_positive : ('v, 'vs) t -> bool
111 (** Whether a term is positive. *)
112
113 val to_string : ('v -> string) -> ('vs -> string) -> ('v, 'vs) t -> string
114 (** Convert a term to a string. *)
115end
116
117(** {1 Incompatibilities} *)
118
119(** An incompatibility is a set of terms that cannot be satisfied together. *)
120type ('p, 'v, 'vs, 'meta) incompatibility = {
121 terms : (('p * ('v, 'vs) term) list);
122 (** The terms that cannot be satisfied together. *)
123
124 cause : ('p, 'v, 'vs, 'meta) incompatibility_cause;
125 (** The reason this incompatibility exists. *)
126}
127
128(** The cause of an incompatibility. *)
129and ('p, 'v, 'vs, 'meta) incompatibility_cause =
130 | Root of 'p * 'v
131 (** Incompatibility derived from root package requirement. *)
132
133 | NoVersions of 'p * 'vs
134 (** No versions satisfy the constraint. *)
135
136 | Dependency of 'p * 'vs * 'p * 'vs
137 (** Package depends on another package. *)
138
139 | Derived of int * int
140 (** Derived from two other incompatibilities. *)
141
142 | External of 'p * 'vs * 'meta
143 (** External incompatibility with custom metadata. *)
144
145(** {1 Partial Solutions} *)
146
147(** A partial solution represents the current state of the solver. *)
148type ('p, 'v, 'vs) partial_solution = {
149 decision_level : int;
150 (** Current decision level. *)
151
152 decisions : ('p * 'v) list;
153 (** Package versions that have been selected. *)
154
155 assignments : ('p * ('v, 'vs) term * int * bool) list;
156 (** Terms derived from decisions. Each tuple contains:
157 - The package
158 - The term
159 - The decision level
160 - Whether this is a decision (true) or derived (false) *)
161}
162
163(** {1 Dependency Provider} *)
164
165(** Interface for a dependency provider. *)
166module type DEPENDENCY_PROVIDER = sig
167 type package_id
168 (** The package identifier type. *)
169
170 type version
171 (** The package version type. *)
172
173 type version_set
174 (** The version set type. *)
175
176 type error
177 (** The type of errors that can occur. *)
178
179 val get_root_package : unit -> package_id
180 (** Get the root package identifier. *)
181
182 val get_root_version : unit -> version
183 (** Get the version of the root package. *)
184
185 val available_versions : package_id -> version list
186 (** List all available versions of a package in descending order (newest first). *)
187
188 val get_dependencies :
189 package_id -> version -> ((package_id * version_set) list, error) result
190 (** Get the dependencies of a package at a specific version. *)
191
192 val choose_version :
193 package_id -> version_set -> version option
194 (** Choose a version for a package given a constraint. *)
195end
196
197(** {1 Solver Configuration} *)
198
199(** Configuration options for the solver. *)
200type 'a config = {
201 max_iterations : int option;
202 (** Maximum number of iterations before giving up. None means no limit. *)
203}
204
205(** Default configuration with no iteration limit. *)
206val default_config : 'a config
207
208(** {1 Main Solver Interface} *)
209
210(** Types and operations for the PubGrub solver. *)
211module type SOLVER = sig
212 type package_id
213 (** Package identifier type. *)
214
215 type version
216 (** Version type. *)
217
218 type version_set
219 (** Version set type. *)
220
221 type metadata
222 (** Custom metadata type for external incompatibilities. *)
223
224 (** Error types. *)
225 type error =
226 | Unsatisfiable of {
227 explanation : string;
228 (** A human-readable explanation of why no solution exists. *)
229 }
230 | DependencyProviderError of {
231 package : package_id;
232 version : version;
233 message : string;
234 (** An error from the dependency provider. *)
235 }
236 | MaxIterationsExceeded
237 (** The solver exceeded the maximum number of iterations. *)
238
239 (** The solution type: a list of packages and their selected versions. *)
240 type solution = (package_id * version) list
241
242 (** Solve dependencies for a package.
243 Returns either a solution or an error explaining why no solution exists. *)
244 val solve :
245 (module DEPENDENCY_PROVIDER with
246 type package_id = package_id and
247 type version = version and
248 type version_set = version_set and
249 type error = string) ->
250 'a config ->
251 (solution, error) result
252
253 (** Generate a human-readable explanation of an error. *)
254 val explain_error : error -> string
255end
256
257(** {1 Functor Interface} *)
258
259(** Create a solver with the given types. *)
260module Make
261 (P : PACKAGE_ID)
262 (V : VERSION)
263 (VS : VERSION_SET with type version = V.t) :
264 SOLVER
265 with type package_id = P.t
266 and type version = V.t
267 and type version_set = VS.t
268 and type metadata = string