1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
open Query.Private
let pkg = Db.Entry.Package.v ~name:"" ~version:""
let elt cost =
Db.Entry.v ~cost ~name:"" ~kind:Db.Entry.Kind.Doc ~rhs:None ~doc_html:"" ~url:"" ~pkg ()
(** This module does the same thing as Succ, but its correctness is obvious
and its performance terrible. *)
module Reference = struct
include Set.Make (Db.Entry)
let of_array arr = arr |> Array.to_seq |> of_seq
end
(** This module is used to construct a pair of a "set array" using [Reference]
and a Succ that are exactly the same. *)
module Both = struct
let empty = Reference.empty, Succ.empty
let union (l, l') (r, r') = Reference.union l r, Succ.union l' r'
let inter (l, l') (r, r') = Reference.inter l r, Succ.inter l' r'
let of_array arr = Reference.of_array arr, Succ.of_array arr
end
(** This is a problematic exemple that was found randomly. It is saved here
to check for regressions. *)
let extra_succ =
let open Both in
let of_array arr = Both.of_array (Array.map elt arr) in
union
(inter (of_array [| 0; 1 |]) (of_array [| 0; 1 |]))
(inter (of_array [| 0; 2; 3 |]) (of_array [| 1; 3; 5; 7 |]))
let random_array size =
List.init size (fun _ -> elt @@ Random.int (size * 2))
|> List.sort_uniq Db.Entry.compare
|> Array.of_list
let rec random_set ~empty ~union ~inter ~of_array size =
let random_set = random_set ~empty ~union ~inter ~of_array in
if size = 0
then empty
else (
match Random.int 3 with
| 0 -> of_array @@ random_array size
| 1 -> inter (random_set (size / 2)) (random_set (size / 2))
| 2 -> union (random_set (size / 2)) (random_set (size / 2))
| _ -> assert false)
let to_costs lst = List.map (fun e -> e.Db.Entry.cost) (List.of_seq lst)
let test_to_seq tree () =
let ref = fst tree |> Reference.to_seq |> to_costs in
let real = snd tree |> Succ.to_seq |> to_costs in
Alcotest.(check (list int)) "same int list" ref real
let tests_to_seq =
[ Alcotest.test_case "Succ.to_seq extra" `Quick (test_to_seq extra_succ) ]
@ List.init 50 (fun i ->
let i = i * 7 in
let succ = i |> Both.(random_set ~empty ~union ~inter ~of_array) in
Alcotest.test_case (Printf.sprintf "Succ.to_seq size %i" i) `Quick (test_to_seq succ))
|
