Debian Codegraph @

vendor/opam/src/format/opamFormula.ml

raw
1 (**************************************************************************)
2 (* *)
3 (* Copyright 2012-2020 OCamlPro *)
4 (* Copyright 2012 INRIA *)
5 (* *)
6 (* All rights reserved. This file is distributed under the terms of the *)
7 (* GNU Lesser General Public License version 2.1, with the special *)
8 (* exception on linking described in the file LICENSE. *)
9 (* *)
10 (**************************************************************************)
11
12 type relop = [`Eq|`Neq|`Geq|`Gt|`Leq|`Lt]
13
14 let neg_relop = function
15 | `Eq -> `Neq
16 | `Neq -> `Eq
17 | `Geq -> `Lt
18 | `Gt -> `Leq
19 | `Leq -> `Gt
20 | `Lt -> `Geq
21
22 let string_of_relop = OpamPrinter.FullPos.relop_kind
23
24 type version_constraint = relop * OpamPackage.Version.t
25
26 type atom = OpamPackage.Name.t * version_constraint option
27
28 let string_of_atom = function
29 | n, None -> OpamPackage.Name.to_string n
30 | n, Some (r,c) ->
31 Printf.sprintf "%s (%s %s)"
32 (OpamPackage.Name.to_string n)
33 (string_of_relop r)
34 (OpamPackage.Version.to_string c)
35
36 let short_string_of_atom = function
37 | n, None -> OpamPackage.Name.to_string n
38 | n, Some (`Eq,c) ->
39 Printf.sprintf "%s.%s"
40 (OpamPackage.Name.to_string n)
41 (OpamPackage.Version.to_string c)
42 | n, Some (r,c) ->
43 Printf.sprintf "%s%s%s"
44 (OpamPackage.Name.to_string n)
45 (string_of_relop r)
46 (OpamPackage.Version.to_string c)
47
48 let string_of_atoms atoms =
49 OpamStd.List.concat_map " & " short_string_of_atom atoms
50
51 let atom_of_string =
52 let re = lazy Re.(compile @@ whole_string @@ seq [
53 group @@ rep1 @@ diff any (set ">=<.!");
54 group @@ alt [ seq [ set "<>"; opt @@ char '=' ];
55 set "=."; str "!="; ];
56 group @@ rep1 any;
57 ])
58 in
59 fun str ->
60 try
61 let lazy re = re in
62 let sub = Re.exec re str in
63 let sname = Re.Group.get sub 1 in
64 let sop = Re.Group.get sub 2 in
65 let sversion = Re.Group.get sub 3 in
66 let name = OpamPackage.Name.of_string sname in
67 let sop = if sop = "." then "=" else sop in
68 let op = OpamLexer.FullPos.relop sop in
69 let version = OpamPackage.Version.of_string sversion in
70 name, Some (op, version)
71 with Not_found | Failure _ | OpamLexer.Error _ ->
72 OpamPackage.Name.of_string str, None
73
74 type 'a conjunction = 'a list
75
76 let string_of_conjunction string_of_atom c =
77 Printf.sprintf "(%s)" (OpamStd.List.concat_map " & " string_of_atom c)
78
79 type 'a disjunction = 'a list
80
81 let string_of_disjunction string_of_atom c =
82 Printf.sprintf "(%s)" (OpamStd.List.concat_map " | " string_of_atom c)
83
84 type 'a cnf = 'a list list
85
86 let string_of_cnf string_of_atom cnf =
87 let string_of_clause c =
88 let left, right = match c with [_] -> "", "" | _ -> "(", ")" in
89 OpamStd.List.concat_map ~left ~right " | " string_of_atom c
90 in
91 OpamStd.List.concat_map " & " string_of_clause cnf
92
93 type 'a dnf = 'a list list
94
95 let string_of_dnf string_of_atom cnf =
96 let string_of_clause c =
97 let left, right = match c with [_] -> "", "" | _ -> "(", ")" in
98 OpamStd.List.concat_map ~left ~right " & " string_of_atom c
99 in
100 OpamStd.List.concat_map " | " string_of_clause cnf
101
102 type 'a formula =
103 | Empty
104 | Atom of 'a
105 | Block of 'a formula
106 | And of 'a formula * 'a formula
107 | Or of 'a formula * 'a formula
108
109 let make_and a b = match a, b with
110 | Empty, r | r, Empty -> r
111 | a, b -> And (a, b)
112
113 let make_or a b = match a, b with
114 | Empty, r | r, Empty -> r (* we're not assuming Empty is true *)
115 | a, b -> Or (a, b)
116
117 let string_of_formula string_of_a f =
118 let rec aux ?(in_and=false) f =
119 let paren_if ?(cond=false) s =
120 if cond || OpamFormatConfig.(!r.all_parens)
121 then Printf.sprintf "(%s)" s
122 else s
123 in
124 match f with
125 | Empty -> "[]"
126 | Atom a -> paren_if (string_of_a a)
127 | Block x -> Printf.sprintf "(%s)" (aux x)
128 | And(x,y) ->
129 paren_if
130 (Printf.sprintf "%s & %s"
131 (aux ~in_and:true x) (aux ~in_and:true y))
132 | Or(x,y) ->
133 paren_if ~cond:in_and
134 (Printf.sprintf "%s | %s" (aux x) (aux y))
135 in
136 aux f
137
138 let rec map f = function
139 | Empty -> Empty
140 | Atom x -> f x
141 | And(x,y) -> make_and (map f x) (map f y)
142 | Or(x,y) -> make_or (map f x) (map f y)
143 | Block x ->
144 match map f x with
145 | Empty -> Empty
146 | x -> Block x
147
148 (* Maps top-down *)
149 let rec map_formula f t =
150 let t = f t in
151 match t with
152 | Block x -> Block (map_formula f x)
153 | And(x,y) -> make_and (map_formula f x) (map_formula f y)
154 | Or(x,y) -> make_or (map_formula f x) (map_formula f y)
155 | x -> x
156
157 let rec map_up_formula f t =
158 let t = match t with
159 | Block x -> f (Block (map_up_formula f x))
160 | And(x,y) -> f (make_and (map_up_formula f x) (map_up_formula f y))
161 | Or(x,y) -> f (make_or (map_up_formula f x) (map_up_formula f y))
162 | Atom x -> f (Atom x)
163 | Empty -> Empty
164 in
165 f t
166
167 let neg neg_atom =
168 map_formula
169 (function
170 | And(x,y) -> Or(x,y)
171 | Or(x,y) -> And(x,y)
172 | Atom x -> Atom (neg_atom x)
173 | x -> x)
174
175 let rec iter f = function
176 | Empty -> ()
177 | Atom x -> f x
178 | Block x -> iter f x
179 | And(x,y) -> iter f x; iter f y
180 | Or(x,y) -> iter f x; iter f y
181
182 let rec fold_left f i = function
183 | Empty -> i
184 | Atom x -> f i x
185 | Block x -> fold_left f i x
186 | And(x,y) -> fold_left f (fold_left f i x) y
187 | Or(x,y) -> fold_left f (fold_left f i x) y
188
189 let rec fold_right f i = function
190 | Empty -> i
191 | Atom x -> f i x
192 | Block x -> fold_right f i x
193 | And(x,y) -> fold_right f (fold_right f i y) x
194 | Or(x,y) -> fold_right f (fold_right f i y) x
195
196 type version_formula = version_constraint formula
197
198 type t = (OpamPackage.Name.t * version_formula) formula
199
200 let rec compare_formula f x y =
201 let rec compare_atom x = function
202 | Empty -> 1
203 | Atom y -> f x y
204 | Block y -> compare_atom x y
205 | And (y,z) | Or (y,z) ->
206 let r = compare_atom x y in
207 if r <> 0 then r else compare_atom x z
208 in
209 match x, y with
210 | Empty, Empty -> 0
211 | Empty, _ -> -1
212 | _ , Empty -> 1
213 | Atom x, Atom y -> f x y
214 | Atom x, y -> compare_atom x y
215 | x , Atom y -> -1 * (compare_atom y x)
216 | Block x, y | x, Block y -> compare_formula f x y
217 | (And (x,y) | Or (x,y)) as lhs, ((And (x',y') | Or (x',y')) as rhs) ->
218 let l = compare_formula f x x' in
219 if l <> 0 then l else
220 let r = compare_formula f y y' in
221 if r <> 0 then r else
222 (match lhs, rhs with
223 | And _, And _ | Or _, Or _ -> 0
224 | And _, Or _ -> 1
225 | Or _, And _ -> -1
226 | _ -> assert false)
227
228 let compare_relop op1 op2 =
229 match op1, op2 with
230 | `Lt,`Lt | `Leq,`Leq | `Neq,`Neq | `Eq,`Eq | `Geq,`Geq | `Gt,`Gt -> 0
231 | `Lt, _ -> -1
232 | _, `Lt -> 1
233 | `Leq, _ -> -1
234 | _, `Leq -> 1
235 | `Neq, _ -> -1
236 | _, `Neq -> 1
237 | `Eq, _ -> -1
238 | _, `Eq -> 1
239 | `Geq, _ -> -1
240 | _, `Geq -> 1
241
242 let compare_version_formula =
243 compare_formula (fun (op1,v1) (op2,v2) ->
244 let c = compare v1 v2 in
245 if c <> 0 then c else
246 compare_relop op1 op2)
247
248 let compare_nc (n1, c1) (n2, c2) =
249 let c = OpamPackage.Name.compare n1 n2 in
250 if c <> 0 then c else compare_version_formula c1 c2
251
252 let compare = compare_formula compare_nc
253
254 let rec eval atom = function
255 | Empty -> true
256 | Atom x -> atom x
257 | Block x -> eval atom x
258 | And(x,y) -> eval atom x && eval atom y
259 | Or(x,y) -> eval atom x || eval atom y
260
261 let rec partial_eval atom = function
262 | Empty -> `Formula Empty
263 | Atom x -> atom x
264 | And(x,y) ->
265 (match partial_eval atom x, partial_eval atom y with
266 | `False, _ | _, `False -> `False
267 | `True, f | f, `True -> f
268 | `Formula x, `Formula y -> `Formula (And (x,y)))
269 | Or(x,y) ->
270 (match partial_eval atom x, partial_eval atom y with
271 | `True, _ | _, `True -> `True
272 | `False, f | f, `False -> f
273 | `Formula x, `Formula y -> `Formula (Or (x,y)))
274 | Block x -> partial_eval atom x
275
276 let check_relop relop c = match relop with
277 | `Eq -> c = 0
278 | `Neq -> c <> 0
279 | `Geq -> c >= 0
280 | `Gt -> c > 0
281 | `Leq -> c <= 0
282 | `Lt -> c < 0
283
284 let eval_relop relop v1 v2 =
285 check_relop relop (OpamPackage.Version.compare v1 v2)
286
287 let check_version_formula f v =
288 eval (fun (relop, vref) -> eval_relop relop v vref) f
289
290 let check (name,cstr) package =
291 name = OpamPackage.name package &&
292 match cstr with
293 | None -> true
294 | Some (relop, v) -> eval_relop relop (OpamPackage.version package) v
295
296 let packages_of_atoms ?(disj=false) pkgset atoms =
297 (* Conjunction for constraints over the same name (unless [disj] is
298 specified), but disjunction on the package names *)
299 let ffilter = if disj then List.exists else List.for_all in
300 let by_name =
301 List.fold_left (fun acc (n,_ as atom) ->
302 OpamPackage.Name.Map.update n (fun a -> atom::a) [] acc)
303 OpamPackage.Name.Map.empty atoms
304 in
305 OpamPackage.Name.Map.fold (fun name atoms acc ->
306 OpamPackage.Set.union acc @@
307 OpamPackage.Set.filter
308 (fun nv -> ffilter (fun a -> check a nv) atoms)
309 (OpamPackage.packages_of_name pkgset name))
310 by_name OpamPackage.Set.empty
311
312 let satisfies_depends pkgset f =
313 eval (fun (name, cstr) ->
314 OpamPackage.Set.exists (fun nv -> check_version_formula cstr nv.version)
315 (OpamPackage.packages_of_name pkgset name))
316 f
317
318 let to_string t =
319 let string_of_constraint (relop, version) =
320 Printf.sprintf "%s %s" (string_of_relop relop)
321 (OpamPackage.Version.to_string version) in
322 let string_of_pkg = function
323 | n, Empty -> OpamPackage.Name.to_string n
324 | n, (Atom _ as c) ->
325 Printf.sprintf "%s %s"
326 (OpamPackage.Name.to_string n)
327 (string_of_formula string_of_constraint c)
328 | n, c ->
329 Printf.sprintf "%s (%s)"
330 (OpamPackage.Name.to_string n)
331 (string_of_formula string_of_constraint c) in
332 string_of_formula string_of_pkg t
333
334 (* convert a formula to a CNF *)
335 let cnf_of_formula t =
336 let rec mk_left x y = match y with
337 | Block y -> mk_left x y
338 | And (a,b) -> And (mk_left x a, mk_left x b)
339 | Empty -> x
340 | _ -> Or (x,y) in
341 let rec mk_right x y = match x with
342 | Block x -> mk_right x y
343 | And (a,b) -> And (mk_right a y, mk_right b y)
344 | Empty -> y
345 | _ -> mk_left x y in
346 let rec mk = function
347 | Empty -> Empty
348 | Block x -> mk x
349 | Atom x -> Atom x
350 | And (x,y) -> And (mk x, mk y)
351 | Or (x,y) -> mk_right (mk x) (mk y) in
352 mk t
353
354 (* convert a formula to DNF *)
355 let dnf_of_formula t =
356 let rec mk_left x y = match y with
357 | Block y -> mk_left x y
358 | Or (a,b) -> Or (mk_left x a, mk_left x b)
359 | _ -> And (x,y) in
360 let rec mk_right x y = match x with
361 | Block x -> mk_right x y
362 | Or (a,b) -> Or (mk_right a y, mk_right b y)
363 | _ -> mk_left x y in
364 let rec mk = function
365 | Empty -> Empty
366 | Block x -> mk x
367 | Atom x -> Atom x
368 | Or (x,y) -> Or (mk x, mk y)
369 | And (x,y) -> mk_right (mk x) (mk y) in
370 mk t
371
372 let verifies f nv =
373 let name_formula =
374 map (fun ((n, _) as a) -> if n = OpamPackage.name nv then Atom a else Empty)
375 (dnf_of_formula f)
376 in
377 name_formula <> Empty &&
378 eval (fun (_name, cstr) ->
379 check_version_formula cstr (OpamPackage.version nv))
380 name_formula
381
382 let packages pkgset f =
383 let names =
384 fold_left (fun acc (name, _) ->
385 OpamPackage.Name.Set.add name acc)
386 OpamPackage.Name.Set.empty f
387 in
388 (* dnf allows us to transform the formula into a union of intervals, where
389 ignoring atoms for different package names works. *)
390 let dnf = dnf_of_formula f in
391 OpamPackage.Name.Set.fold (fun name acc ->
392 (* Ignore conjunctions where [name] doesn't appear *)
393 let name_formula =
394 map (fun ((n, _) as a) -> if n = name then Atom a else Empty) dnf
395 in
396 OpamPackage.Set.union acc @@
397 OpamPackage.Set.filter (fun nv ->
398 let v = OpamPackage.version nv in
399 eval (fun (_name, cstr) -> check_version_formula cstr v)
400 name_formula)
401 (OpamPackage.packages_of_name pkgset name))
402 names OpamPackage.Set.empty
403
404 (* Convert a t an atom formula *)
405 let to_atom_formula (t:t): atom formula =
406 map (fun (x, c) -> match c with
407 | Empty -> Atom (x, None)
408 | cs -> map (fun c -> Atom (x, Some c)) cs)
409 t
410
411 (* Convert an atom formula to a t-formula *)
412 let of_atom_formula (a:atom formula): t =
413 let atom (n, v) =
414 match v with
415 | None -> Atom (n, Empty)
416 | Some (r,v) -> Atom (n, Atom (r,v)) in
417 map atom a
418
419 let ands l = List.fold_left make_and Empty l
420
421 let rec ands_to_list = function
422 | Empty -> []
423 | And (e,f) ->
424 List.rev_append (rev_ands_to_list e) (ands_to_list f)
425 | Block f -> ands_to_list f
426 | x -> [x]
427 and rev_ands_to_list = function
428 | Empty -> []
429 | Block f -> rev_ands_to_list f
430 | And (e,f) ->
431 List.rev_append (ands_to_list f) (rev_ands_to_list e)
432 | x -> [x]
433
434 let of_conjunction c =
435 of_atom_formula (ands (List.rev_map (fun x -> Atom x) c))
436
437 let ors l = List.fold_left make_or Empty l
438
439 let rec ors_to_list = function
440 | Empty -> []
441 | Or (e,f) ->
442 List.rev_append (rev_ors_to_list e) (ors_to_list f)
443 | Block f -> ors_to_list f
444 | x -> [x]
445 and rev_ors_to_list = function
446 | Empty -> []
447 | Or (e,f) ->
448 List.rev_append (ors_to_list f) (rev_ors_to_list e)
449 | Block f -> rev_ors_to_list f
450 | x -> [x]
451
452 let is_conjunction t =
453 let rec aux = function
454 | Or _ -> false
455 | And (a,b) -> aux a && aux b
456 | Block a -> aux a
457 | _ -> true
458 in
459 aux t
460
461 let is_disjunction t =
462 let rec aux = function
463 | And _ -> false
464 | Or (a,b) -> aux a && aux b
465 | Block a -> aux a
466 | _ -> true
467 in
468 aux t
469
470 let rec sort comp f=
471 match f with
472 | (Empty | Atom _) as f -> f
473 | Block f -> Block (sort comp f)
474 | And _ as f ->
475 ands_to_list f
476 |> List.rev_map (sort comp)
477 |> List.sort (compare_formula comp)
478 |> ands
479 | Or _ as f ->
480 ors_to_list f
481 |> List.rev_map (sort comp)
482 |> List.sort (compare_formula comp)
483 |> ors
484
485 let atoms t =
486 fold_right (fun accu x -> x::accu) [] (to_atom_formula t)
487
488 let formula_to_cnf t =
489 let atoms = fold_right (fun acc a -> a::acc) [] in
490 let conj = rev_ands_to_list t in
491 if List.for_all is_disjunction conj then
492 List.rev_map atoms conj (* this gives a nice speedup *)
493 else
494 List.rev_map atoms @@ rev_ands_to_list @@ cnf_of_formula t
495
496 let to_cnf t = formula_to_cnf @@ to_atom_formula t
497
498 let formula_to_dnf t =
499 let disj = rev_ors_to_list t in
500 let atoms = fold_right (fun acc a -> a::acc) [] in
501 if List.for_all is_conjunction disj then
502 List.rev_map atoms disj
503 else
504 List.rev_map atoms @@ rev_ors_to_list @@ dnf_of_formula t
505
506 let to_dnf t = formula_to_dnf @@ to_atom_formula t
507
508 let to_conjunction t =
509 if is_conjunction t then atoms t
510 else failwith (Printf.sprintf "%s is not a valid conjunction" (to_string t))
511
512 let to_disjunction t =
513 if is_disjunction t then atoms t
514 else failwith (Printf.sprintf "%s is not a valid disjunction" (to_string t))
515
516 let of_disjunction d =
517 of_atom_formula (ors (List.rev_map (fun x -> Atom x) d))
518
519 let get_disjunction_formula version_set cstr =
520 (* rev_ors_to_list cstr |>
521 * List.fold_left *)
522
523 List.rev_map (fun ff ->
524 match ands_to_list ff with
525 | [] -> assert false
526 | [Atom _] as at -> at
527 | _ ->
528 OpamPackage.Version.Set.filter (check_version_formula ff) version_set |>
529 OpamPackage.Version.Set.elements |>
530 List.map (fun v -> Atom (`Eq, v)))
531 (rev_ors_to_list cstr) |>
532 List.flatten
533
534 let set_to_disjunction set t =
535 List.map (function
536 | And _ ->
537 failwith (Printf.sprintf "%s is not a valid disjunction" (to_string t))
538 | Or _ | Block _ | Empty -> assert false
539 | Atom (name, Empty) -> [name, None]
540 | Atom (name, Atom a) -> [name, Some a]
541 | Atom (name, cstr) ->
542 get_disjunction_formula
543 (OpamPackage.versions_of_name set name)
544 cstr |>
545 List.map (function
546 | Atom (relop, v) -> name, Some (relop, v)
547 | _ -> assert false))
548 (ors_to_list t) |>
549 List.flatten
550
551 let simplify_ineq_formula vcomp f =
552 let vals = fold_left (fun acc (_op, x) -> x::acc) [] f in
553 let vals = List.sort_uniq vcomp vals in
554 let vals_a = Array.of_list vals in
555 let val_of_int i = vals_a.(i/2) in
556 let int_of_val =
557 let m = List.mapi (fun i v -> v, 2 * i + 1) vals in
558 fun v -> OpamStd.List.assoc (fun v v' -> vcomp v v' = 0) v m
559 in
560 (* One integer for each value appearing in f, plus one for each interval *)
561 let rec mk_ranges acc n = if n < 0 then acc else mk_ranges (n::acc) (n-1) in
562 let ranges = mk_ranges [] (2 * Array.length vals_a + 2) in
563 let int_formula = map (fun (op, x) -> Atom (op, int_of_val x)) f in
564 let vals =
565 List.map (fun i ->
566 eval (fun (relop, iref) -> check_relop relop (i - iref)) int_formula,
567 i)
568 ranges
569 in
570 if List.for_all (fun (t, _) -> not t) vals then None else
571 let rec aux = function
572 | (true, _) :: ((true, _) :: _ as r) -> aux r
573 | (false, _) :: ((false, _) :: _ as r) -> aux r
574 | (true, _) :: (false, x) :: ((true, _) :: _ as r) when x mod 2 = 1 ->
575 (`Neq, x) :: aux r
576 | (false, _) :: (true, x) :: ((false, _) :: _ as r) when x mod 2 = 1 ->
577 (`Eq, x) :: aux r
578 | (true, _) :: ((false, x) :: _ as r) ->
579 (if x mod 2 = 1 then `Lt, x else `Leq, x-1) :: aux r
580 | (false, _) :: ((true, x) :: _ as r) ->
581 (if x mod 2 = 1 then `Geq, x else `Gt, x-1) :: aux r
582 | [_] | []-> []
583 in
584 let rec aux2 = function
585 | (`Geq|`Gt|`Neq as op, i) :: r ->
586 let rec find_upper acc = function
587 | (`Leq|`Lt as op, i) :: r ->
588 ands (List.rev_append acc [Atom (op, val_of_int i)]) :: aux2 r
589 | (`Neq, i) :: r ->
590 find_upper (Atom (`Neq, val_of_int i) :: acc) r
591 | r -> ands (List.rev acc) :: aux2 r
592 in
593 find_upper [Atom (op, val_of_int i)] r
594 | (op, i) :: r -> Atom (op, val_of_int i) :: aux2 r
595 | [] -> [Empty]
596 in
597 Some (ors (aux2 (aux vals)))
598
599 let simplify_version_formula f =
600 simplify_ineq_formula OpamPackage.Version.compare f
601
602 (** Takes an ordered list of atoms and a predicate, returns a formula describing
603 the subset of matching atoms *)
604 let gen_formula l f =
605 let l = List.map (fun x -> f x, x) l in
606 let rec aux (t, x as bound) l = match t, l with
607 | true, (false, y) :: (true, _) :: r
608 | false, (true, y) :: (false, _) :: r ->
609 let a = (if t then `Neq else `Eq), y in
610 (match aux bound r with
611 | b :: r -> b :: a :: r
612 | r -> a :: r)
613 | true, (true, _) :: r
614 | false, (false, _) :: r ->
615 aux bound r
616 | true, (false, _ as bound') :: r
617 | false, (true, _ as bound') :: r ->
618 ((if t then `Geq else `Lt), x) :: aux bound' r
619 | _, [] -> [(if t then `Geq else `Lt), x]
620 in
621 let rec aux2 = function
622 | (`Geq|`Neq), _ as a :: r ->
623 let rec find_upper acc = function
624 | `Lt, _ as a :: r ->
625 ands (List.rev_append acc [Atom a]) :: aux2 r
626 | `Neq, _ as a :: r ->
627 find_upper (Atom a :: acc) r
628 | r -> ands (List.rev acc) :: aux2 r
629 in
630 find_upper [Atom a] r
631 | a :: r -> Atom a :: aux2 r
632 | [] -> [Empty]
633 in
634 match l with
635 | [] -> Some Empty
636 | (t, x) :: r ->
637 match aux (t, x) r with
638 | [] -> assert false
639 | [`Geq, _] -> Some Empty
640 | [`Lt, _] -> None
641 | _ :: r -> Some (ors (aux2 r))
642
643 let formula_of_version_set set subset =
644 let module S = OpamPackage.Version.Set in
645 match
646 gen_formula (S.elements set) (fun x -> S.mem x subset)
647 with
648 | Some f -> f
649 | None -> invalid_arg "Empty subset"
650
651 let simplify_version_set set f =
652 let module S = OpamPackage.Version.Set in
653 if S.is_empty set then Empty else
654 let set = fold_left (fun set (_relop, v) -> S.add v set) set f in
655 gen_formula (S.elements set) (check_version_formula f) |>
656 OpamStd.Option.default f