| 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 |