From 467f3e7742cee3722d87bb50697a460d71fe9870 Mon Sep 17 00:00:00 2001
From: Edwin Ansari <edwin.ansari@lambda-coins.com>
Date: Wed, 8 Jun 2022 15:41:10 +0200
Subject: [PATCH 1/2] Proto/Skip_list: bug discovery, test_minimal_back_path

---
 .../test/unit/test_skip_list_repr.ml          | 37 +++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml b/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml
index d10d1345d799..c1e67cb7200d 100644
--- a/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml
+++ b/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml
@@ -162,6 +162,39 @@ let test_skip_list_nat_check_invalid_path (basis, i) =
   end) in
   M.check_invalid_paths i
 
+let test_minimal_back_path () =
+  let basis = 2 in
+  let module M = TestNat (struct
+    let basis = basis
+  end) in
+  let l = M.nlist basis 20 in
+  let check_minimal_path = function
+    | None, _ -> failwith "empty path"
+    | Some path, expected_path ->
+        if path = expected_path then return ()
+        else
+          failwith
+            "non-minimal path:[%s] != expected_path:[%s]"
+            (M.show_path path)
+            (M.show_path expected_path)
+  in
+  let cases =
+    [
+      (6, 1, [6; 3; 1]);
+      (6, 3, [6; 3]);
+      (10, 3, [10; 7; 3]);
+      (10, 5, [10; 7; 5]);
+      (10, 7, [10; 7]);
+      (10, 9, [10; 9]);
+    ]
+  in
+  List.iter_es
+    check_minimal_path
+    (List.map
+       (fun (start, target, expected_path) ->
+         (M.back_path l start target, expected_path))
+       cases)
+
 let tests =
   [
     Tztest.tztest_qcheck2
@@ -181,4 +214,8 @@ let tests =
         let* i = 0 -- 100 in
         return (basis, i))
       test_skip_list_nat_check_invalid_path;
+    Tztest.tztest
+      "Skip list: check if the back_path is minimal"
+      `Quick
+      test_minimal_back_path;
   ]
-- 
GitLab


From 8ba5a4a121cd03466d0b94b84c05c6a66655a648 Mon Sep 17 00:00:00 2001
From: Edwin Ansari <edwin.ansari@lambda-coins.com>
Date: Wed, 8 Jun 2022 15:44:25 +0200
Subject: [PATCH 2/2] Proto/Skip_list: fix non-minimal back_path bug in
 best_skip

---
 src/proto_alpha/lib_protocol/skip_list_repr.ml | 14 +++++---------
 1 file changed, 5 insertions(+), 9 deletions(-)

diff --git a/src/proto_alpha/lib_protocol/skip_list_repr.ml b/src/proto_alpha/lib_protocol/skip_list_repr.ml
index 56f0d73cc4f4..cc65a1d5e6e6 100644
--- a/src/proto_alpha/lib_protocol/skip_list_repr.ml
+++ b/src/proto_alpha/lib_protocol/skip_list_repr.ml
@@ -188,25 +188,21 @@ end) : S = struct
       aux 1 [] 0
     in
     let back_pointers =
-      FallbackArray.of_list ~fallback:None ~proj:(fun x -> Some x) back_pointers
+      FallbackArray.of_list ~fallback:None ~proj:Option.some back_pointers
     in
     {index; content; back_pointers}
 
   let best_skip cell target_index =
     let index = cell.index in
-    let rec aux idx pow best_idx best_skip =
+    let rec aux idx pow best_idx =
       if Compare.Int.(idx >= FallbackArray.length cell.back_pointers) then
         best_idx
       else
         let idx_index = index - (index mod pow) - 1 in
-        let skip = index - idx_index in
-        if
-          Compare.Int.(idx_index < target_index)
-          || Option.equal Compare.Int.equal (Some skip) best_skip
-        then best_idx
-        else aux (idx + 1) (basis * pow) (Some idx) (Some skip)
+        if Compare.Int.(idx_index < target_index) then best_idx
+        else aux (idx + 1) (basis * pow) (Some idx)
     in
-    aux 0 1 None None
+    aux 0 1 None
 
   let back_path ~deref ~cell_ptr ~target_index =
     let rec aux path ptr =
-- 
GitLab