Draft: Proto/Michelson: `big_map` caching

Why

Context: Adding references to Michelson

Presently, fetching values for a big map will always involve deserializing a Micheline value from the Alpha_context. This poses an issue for references since fetching the same value would not result in the same reference.

# string (ref int) big_map : 'S
DUP
# string (ref int) big_map : string (ref int) big_map : 'S
# fetch ref for "Alistair"
PUSH string "Alistair"
GET
ASSERT_SOME
# ref int : string (ref int) big_map : 'S
# fetch ref for "Alistair" again
SWAP
PUSH STRING "Alistair" 
GET
ASSERT_SOME
# ref int : ref int : 'S
# += 1 the first ref 
DUP 
DUP 
GET_REF
PUSH int 1
ADD
SET_REF
# ref int : ref int : 'S
ASSERT_NEQ

What

This MR aims to solve the above issue by maintaining a cache for each big map, stored in the big map cache context.

How

We introduce a big map cache with the interface:

type ('key, 'value) t = ('key, 'value) Script_typed_ir.big_map_cache

type ('k, 'v, 'vc) tid = Big_map.Id.t * 'k comparable_ty * ('v, 'vc) ty

val find_and_cache_by_hash :
  context ->
  Script_expr_hash.t ->
  ('k, 'v) t ->
  ('v option * ('k, 'v) t * context) tzresult Lwt.t

module Context : sig
  type t = Script_typed_ir.big_map_cache_context

  val init : t

  val find_and_cache_by_hash :
    context ->
    ('k, 'v, _) tid ->
    Script_expr_hash.t ->
    t ->
    ('v option * t * context) tzresult Lwt.t
end

The context is passed around monadically in the Script_interpreter.step function. Script_big_map.get (and get_and_update) is modified to lookup the key in the cache first before looking up the key in the Alpha_context.

Manually testing the MR

make test-proto-unit

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

added 5 commits

• dec85afc - Proto/Michelson: add plumbing for big map cache contexts
• 9779f698 - Proto: implement big map caches and big map cache contexts
• b9462902 - Proto/Michelson: update big map functions to use the big map cache context
• dcf53bd5 - Proto/Gas: add cache context plumbing to `lib_benchmark{_proto}`
• c7dd5597 - fixup! Testing/Proto: promote tests

Compare with previous version

added michelson ⚗ label

assigned to @alistair.obrien

changed the description

added 1 commit

• e57b8f98 - fixup! Style: fix formatting (lib_benchmarks_proto)

Compare with previous version

mentioned in merge request !13299

changed title from Draft: Proto/Michelson: big map caching to Draft: Proto/Michelson: {++}big{+_+}map{++} caching

added proto label

added 12 commits

• e57b8f98...9ec8de5c - 2 earlier commits
• f29f8c43 - Devtools: Update `parse_ty` to require a `allow_ref` argument
• e66a81a6 - Testing/Proto: Add tests
• ad7b5c1e - Kaitai: Update encodings
• b3fddb42 - Proto: refactor `Carbonated_map.Make_builder`
• 260a1238 - Proto/Michelson: add plumbing for big map cache contexts
• 1eeba0a9 - Proto: implement big map caches and big map cache contexts
• 6761af6e - Proto/Michelson: update big map functions to use the big map cache context
• f161f095 - Proto/Gas: add cache context plumbing to `lib_benchmark{_proto}`
• 5f98a670 - fixup! Testing/Proto: promote tests
• b2af338e - fixup! Style: fix formatting (lib_benchmarks_proto)

Compare with previous version