Module Proxy_getter.RequestsTree

The point of this data structure is as follows:

Suppose Make.cache is like this, because key A has been requested already and the tree at A has two nodes B and C:

A-B \ C

If proxy_getter receives a request for A-D, there's no point doing a request, even if it's not there; because as A has been requested already; if A-D was available, it would be there already.

This is a crucial optimisation that reduces the number of .../raw/bytes RPC requests by 90% when executing baking_rights&?all=true locally, after the chain starts having more than a few cycles. More specifically, in baking_rights, the client keeps looking for (missing) keys of the form rolls;owner;snapshot;10;1;74;5;1354 while the parent key rolls;owner;snapshot;10;1 has been obtained before.

This structure has the invariant that all leaves are All nodes. If requests A;B and A;C have been done, the tree is as follows:

APartial -> BAll \ \-------> CAll

If then request A is done, the tree becomes:

AAll

type tree =
  1. | Partial of tree StringMap.t
  2. | All
val empty : tree
val add : tree -> string list -> tree
val find_opt : tree -> string list -> tree option