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 13d15947fd0705ec4068a74e743a2245e4dfee7d..e9c87204e6ff043c6d19ca8cea573f70ca87822a 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 e9facb7e132aad4417f1786adad9348c8215ac34..6a1511e9336edace437109b500a6d4174e7fe9ae 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) @@ -57,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 a8c23b1f42904d6a95c6379a3831d3e5ca4d0a04..1c4a69db2d13d5e3f1acf9bc9b65880aca66be3e 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 @@ -60,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 5099909ada027184951f091bb65ce02d19aaf515..68f3d776ad52bbbf9fc8847425e6d5ba6efb3758 100644 --- a/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml +++ b/src/proto_alpha/lib_protocol/test/pbt/test_bitset.ml @@ -35,76 +35,65 @@ 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 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" @@ -127,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; ] ); ]