From f92612641a7780f67bd7aee415c0549d7761d883 Mon Sep 17 00:00:00 2001
From: "iguerNL@Functori" <iguer@functori.com>
Date: Thu, 27 Oct 2022 09:28:19 +0200
Subject: [PATCH 1/3] Proto: Provide Bitset.fill to set all the bits of a
 bitset to 1

---
 src/proto_alpha/bin_sc_rollup_node/dal_slots_tracker.ml | 4 ++--
 src/proto_alpha/lib_protocol/bitset.ml                  | 4 ++++
 src/proto_alpha/lib_protocol/bitset.mli                 | 9 +++++++++
 3 files changed, 15 insertions(+), 2 deletions(-)

diff --git a/src/proto_alpha/bin_sc_rollup_node/dal_slots_tracker.ml b/src/proto_alpha/bin_sc_rollup_node/dal_slots_tracker.ml
index 13d15947fd07..e9c87204e6ff 100644
--- a/src/proto_alpha/bin_sc_rollup_node/dal_slots_tracker.ml
+++ b/src/proto_alpha/bin_sc_rollup_node/dal_slots_tracker.ml
@@ -181,8 +181,8 @@ let download_and_save_slots
     {published_block_hash; confirmed_slots_indexes} =
   let open Lwt_result_syntax in
   let*? all_slots =
-    Misc.(0 --> (protocol_constants.parametric.dal.number_of_slots - 1))
-    |> Bitset.from_list |> Environment.wrap_tzresult
+    Bitset.fill ~length:protocol_constants.parametric.dal.number_of_slots
+    |> Environment.wrap_tzresult
   in
   let*? not_confirmed =
     Environment.wrap_tzresult
diff --git a/src/proto_alpha/lib_protocol/bitset.ml b/src/proto_alpha/lib_protocol/bitset.ml
index e9facb7e132a..19fc428d10ca 100644
--- a/src/proto_alpha/lib_protocol/bitset.ml
+++ b/src/proto_alpha/lib_protocol/bitset.ml
@@ -41,6 +41,10 @@ let add field pos =
 
 let from_list positions = List.fold_left_e add empty positions
 
+let fill ~length =
+  error_when Compare.Int.(length < 0) (Invalid_position length) >>? fun () ->
+  ok Z.(pred (shift_left one length))
+
 let inter = Z.logand
 
 let diff b1 b2 = Z.logand b1 (Z.lognot b2)
diff --git a/src/proto_alpha/lib_protocol/bitset.mli b/src/proto_alpha/lib_protocol/bitset.mli
index a8c23b1f4290..35ad4daef41b 100644
--- a/src/proto_alpha/lib_protocol/bitset.mli
+++ b/src/proto_alpha/lib_protocol/bitset.mli
@@ -49,6 +49,15 @@ val add : t -> int -> t tzresult
     [positions]. *)
 val from_list : int list -> t tzresult
 
+(** [fill ~length] is equivalent to setting all bits for positions in
+    [0, length - 1] to [one]. i.e., to [from_list (0 -- size -1)] or to
+    [(2 ^ length) - 1]. But it's more efficient than folding on individual
+    positions to set them.
+
+    The function returns [Invalid_position length] if [length] is negative.
+*)
+val fill : length:int -> t tzresult
+
 (** [inter set_l set_r] returns [set] which is result of the
     intersection of [set_l] and [set_r]. *)
 val inter : t -> t -> t
-- 
GitLab


From 777a1b1f0c5055075cd22a837e1a4c4b02567103 Mon Sep 17 00:00:00 2001
From: "iguerNL@Functori" <iguer@functori.com>
Date: Fri, 28 Oct 2022 16:42:20 +0200
Subject: [PATCH 2/3] Tests: refactor Bitset pbt tests

---
 .../lib_protocol/test/pbt/test_bitset.ml      | 73 +++++++------------
 1 file changed, 26 insertions(+), 47 deletions(-)

diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml b/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml
index 5099909ada02..5baa2ad0b5d8 100644
--- a/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml
+++ b/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml
@@ -35,74 +35,53 @@ open Protocol.Bitset
 
 let gen_ofs = QCheck2.Gen.int_bound (64 * 10)
 
-let gen_storage =
-  let open QCheck2.Gen in
-  let* int_vector = list @@ int_bound 64 in
-  match from_list int_vector with
-  | Ok v -> return v
+let value_of res =
+  match res with
+  | Ok v -> v
   | Error e ->
       Alcotest.failf
         "An unxpected error %a occurred when generating Bitset.t"
         Environment.Error_monad.pp_trace
         e
 
+let gen_storage =
+  let open QCheck2.Gen in
+  let* int_vector = list @@ int_bound 64 in
+  from_list int_vector |> value_of |> return
+
 let test_get_set (c, ofs) =
   List.for_all
     (fun ofs' ->
-      let res =
-        let open Result_syntax in
-        let* c' = add c ofs in
-        let* v = mem c ofs' in
-        let* v' = mem c' ofs' in
-        return (if ofs = ofs' then v' = true else v = v')
-      in
-      match res with
-      | Error e ->
-          Alcotest.failf
-            "Unexpected error: %a"
-            Environment.Error_monad.pp_trace
-            e
-      | Ok res -> res)
+      let open Result_syntax in
+      value_of
+      @@ let* c' = add c ofs in
+         let* v = mem c ofs' in
+         let* v' = mem c' ofs' in
+         return (if ofs = ofs' then v' = true else v = v'))
     (0 -- 63)
 
 let test_inter (c1, c2) =
   let c3 = inter c1 c2 in
   List.for_all
     (fun ofs ->
-      let res =
-        let open Result_syntax in
-        let* v1 = mem c1 ofs in
-        let* v2 = mem c2 ofs in
-        let* v3 = mem c3 ofs in
-        return ((v1 && v2) = v3)
-      in
-      match res with
-      | Error e ->
-          Alcotest.failf
-            "Unexpected error: %a"
-            Environment.Error_monad.pp_trace
-            e
-      | Ok res -> res)
+      let open Result_syntax in
+      value_of
+      @@ let* v1 = mem c1 ofs in
+         let* v2 = mem c2 ofs in
+         let* v3 = mem c3 ofs in
+         return ((v1 && v2) = v3))
     (0 -- 63)
 
 let test_diff (c1, c2) =
   let c3 = diff c1 c2 in
   List.for_all
     (fun ofs ->
-      let res =
-        let open Result_syntax in
-        let* v1 = mem c1 ofs in
-        let* v2 = mem c2 ofs in
-        let* v3 = mem c3 ofs in
-        return ((v1 && not v2) = v3)
-      in
-      match res with
-      | Error e ->
-          Alcotest.failf
-            "Unexpected error: %a"
-            Environment.Error_monad.pp_trace
-            e
-      | Ok res -> res)
+      let open Result_syntax in
+      value_of
+      @@ let* v1 = mem c1 ofs in
+         let* v2 = mem c2 ofs in
+         let* v3 = mem c3 ofs in
+         return ((v1 && not v2) = v3))
     (0 -- 63)
 
 let () =
-- 
GitLab


From 897638b20cbd266b33c41d8ae70b338a41c36aa5 Mon Sep 17 00:00:00 2001
From: "iguerNL@Functori" <iguer@functori.com>
Date: Fri, 28 Oct 2022 16:42:45 +0200
Subject: [PATCH 3/3] Tests: add pbt tests for Bitset.fill

---
 src/proto_alpha/lib_protocol/bitset.ml            |  4 ++++
 src/proto_alpha/lib_protocol/bitset.mli           |  4 ++++
 .../lib_protocol/test/pbt/test_bitset.ml          | 15 +++++++++++++++
 3 files changed, 23 insertions(+)

diff --git a/src/proto_alpha/lib_protocol/bitset.ml b/src/proto_alpha/lib_protocol/bitset.ml
index 19fc428d10ca..6a1511e9336e 100644
--- a/src/proto_alpha/lib_protocol/bitset.ml
+++ b/src/proto_alpha/lib_protocol/bitset.ml
@@ -61,3 +61,7 @@ let () =
     (fun i -> Invalid_position i)
 
 let occupied_size_in_bits = Z.numbits
+
+module Internal_for_tests = struct
+  let to_z z = z
+end
diff --git a/src/proto_alpha/lib_protocol/bitset.mli b/src/proto_alpha/lib_protocol/bitset.mli
index 35ad4daef41b..1c4a69db2d13 100644
--- a/src/proto_alpha/lib_protocol/bitset.mli
+++ b/src/proto_alpha/lib_protocol/bitset.mli
@@ -69,3 +69,7 @@ val diff : t -> t -> t
 (** [occupied_size_in_bits bitset] returns the current number of bits
    occupied by the [bitset]. *)
 val occupied_size_in_bits : t -> int
+
+module Internal_for_tests : sig
+  val to_z : t -> Z.t
+end
diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml b/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml
index 5baa2ad0b5d8..68f3d776ad52 100644
--- a/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml
+++ b/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml
@@ -84,6 +84,16 @@ let test_diff (c1, c2) =
          return ((v1 && not v2) = v3))
     (0 -- 63)
 
+let test_fill =
+  let two = Z.of_int 2 in
+  fun length ->
+    let f1 = fill ~length |> value_of |> Internal_for_tests.to_z in
+    let f2 =
+      from_list (0 -- (length - 1)) |> value_of |> Internal_for_tests.to_z
+    in
+    let f3 = Z.(pow two length |> pred) in
+    Z.equal f1 f2 && Z.equal f2 f3
+
 let () =
   Alcotest.run
     "bits"
@@ -106,5 +116,10 @@ let () =
               ~name:"diff"
               QCheck2.Gen.(pair gen_storage gen_storage)
               test_diff;
+            QCheck2.Test.make
+              ~count:10000
+              ~name:"fill"
+              QCheck2.Gen.(small_nat)
+              test_fill;
           ] );
     ]
-- 
GitLab