Fix flakyness of test handle_operations in test_prevalidator_classification_operations.ml

Fixes #2281 (closed)

Context

@vch9 discovered that a QCheck test of the mempool was flaky (#2281 (closed)). This was caused by the generators of block to be more general than the production case: in production, two different blocks cannot contain an operation with the same hash. If this case was being hit by the generator of trees of blocks, a test of test_prevalidator_classification_operations.ml was failing.

This MR fixes this flakyness by ensuring that, in generated trees of blocks, all operations hashes of all blocks are different. This is done in a postprocessing step, by checking that this property holds; and if not; removing the offending blocks. This could have been done alternatively by generating lists of unique operations but this would have been a more drastic change: it would change the shape of most trees generated. The chosen approach of fixing the existing trees on the other hand mostly preserves the existing trees, since the case being ruled out is rare. I also remember from my PhD days than fixing a randomly structure to ensure an invariant rather than ensuring the invariant by construction is usually way cheaper (although I have no reference anymore to assess this claim). This approach seems better here since the invariant is rarely broken.

Manually testing the MR

Test 1

• Execute QCHECK_SEED=295469715 dune exec src/lib_shell/test/test_prevalidator_classification_operations.exe -- test 'handle_operations' '1' on master, witness it fails.
• Execute the same command on this MR, witness it works.

Test 2

To see that our analysis of the duplication of an operation is right, add this change to master (this code is in this MR, you may as well slightly edit HEAD to reach this state):

• Execute QCHECK_SEED=295469715 dune exec src/lib_shell/test/test_prevalidator_classification_operations.exe -- test 'handle_operations' '1' and witness it fails

Test 3

Patch the code as follows:

--- a/src/lib_shell/test/test_prevalidator_classification_operations.ml
+++ b/src/lib_shell/test/test_prevalidator_classification_operations.ml
@@ -335,7 +335,17 @@ module Generators = struct
                       (* If operation hash is mapped, extend the list of blocks
                          to which it is mapped, to record that [block] also
                          contains it. *)
-                      Some Block.Set.(union (singleton block) blocks_value))
+                      let new_ =
+                        Block.Set.(union (singleton block) blocks_value)
+                      in
+                      Block.Set.iter
+                        (function
+                          | block ->
+                              Stdlib.print_endline
+                                ("Removing "
+                                ^ Block_hash.to_string (Block.to_hash block)))
+                        new_ ;
+                      Some new_)

• Execute QCHECK_SEED=295469715 dune exec src/lib_shell/test/test_prevalidator_classification_operations.exe -- test 'handle_operations' '1'
• Notice that the Removing step occurs in the command above (execute cat ~/dev/trezos/_build/_tests/Prevalidator/* for that), meaning that our postprocessing step has an effect.
• Execute again multiple times without specifying QCHECK_SEED, witness that Removing doesn't get printed: as expected the postprocessing step usually doesn't do anything.

Test 4

• Compare the execution times of the entire file on master and on this MR (with dune exec src/lib_shell/test/test_prevalidator_classification_operations.exe) and observe they are similar (circa 160 seconds on my machine ©️)

Test 5

Observe that the generated trees are still non trivial (besides being slightly trimmed sometimes):

• Instrument the code as follows:

--- a/src/lib_shell/test/test_prevalidator_classification_operations.ml
+++ b/src/lib_shell/test/test_prevalidator_classification_operations.ml
@@ -467,6 +467,9 @@ module Generators = struct
       QCheck.Gen.t =
     let open QCheck.Gen in
     let* tree = tree_gen ?blocks in
+    Stdlib.print_endline
+      ("Generated tree of size "
+      ^ Int.to_string (List.length (Tree.values tree))) ;

• Execute dune exec src/lib_shell/test/test_prevalidator_classification_operations.exe on master, and run the following command that sums the sizes of all generated trees: cat ~/dev/trezos/_build/_tests/Prevalidator/* | awk '{print $5}' | xargs | tr ' ' '+' | bc
• Repeat on this MR, observe that the obtained number is roughly similar (around 18000)

Checklist

• NA Document the interface of any function added or modified (see the coding guidelines)
• NA Document any change to the user interface, including configuration parameters (see node configuration)
• Provide automatic testing (see the testing guide).
• NA For new features and bug fixes, add an item in the appropriate changelog (docs/protocols/alpha.rst for the protocol and the environment, the Development Version section of CHANGES.md for everything else).
• Select suitable reviewers using the Reviewers field below.
• Select as Assignee the next person who should take action on that MR