Proto/compare-operations: add comparison of valid operations
Context
When determining the content of a block to be baked,
it is relevant to sort valid operations to determine the most profitable ones,
for both the baker and the chain's liveness.
This MR implements a comparison for validated operations, providing a strict order.
This comparison is state-free as it relies on the operations' validation passes, static parameters, and hashes.
Only operations with the same hash compare as equal.
This MR also replaces acceptable_passes
by acceptable_pass
returning an optional integer instead of a list of integer.
This MR also removes relative_position_within_block
and replaces it by compare_by_passes
when only the ordering
by pass is required and by compare_operations
when a total order on operations is required.
compare_by_passes
is not exported in the environment.
Finally, this MR also implements operation generators to perform tests on generated operations.
Manually testing the MR
Test that compare_operation provides a strict order via a series of generated unit tests on generated operations:
dune exec src/proto_alpha/lib_protocol/test/unit/main.exe -- test "\[Unit\] compare operations"
Test that compare_operation
complies with its specification:
The branch pipelining@compliance-compare-operations
contains:
- The Coq specification: a Coq model of compare_operation with proof of providing a decidable strict order; in
src/proto_alpha/lib_protocol/test/pbt/spec
. - a specification compliance test validates that
compare_operation
behaves as its extracted model on the generated operation via generated unit tests on generated unit tests on generated operations.
dune exec src/proto_alpha/lib_protocol/test/pbt/test_compare_operations.exe
Checklist
-
Document the interface of any function added or modified (see the coding guidelines) -
Document any change to the user interface, including configuration parameters (see node configuration) -
Provide automatic testing (see the testing guide). -
For new features and bug fixes, add an item in the appropriate changelog ( docs/protocols/alpha.rst
for the protocol and the environment,CHANGES.rst
at the root of the repository for everything else). -
Select suitable reviewers using the Reviewers
field below. -
Select as Assignee
the next person who should take action on that MR