`KV_MAKER.Tree`

Managing store's trees.

`Tree`

provides immutable, in-memory partial mirror of the store, with lazy reads and delayed writes.

Trees are like staging area in Git: they are immutable temporary non-persistent areas (they disappear if the host crash), held in memory for efficiency, where reads are done lazily and writes are done only when needed on commit: if you modify a key twice, only the last change will be written to the store when you commit.

`val empty : tree`

`empty`

is the empty tree. The empty tree does not have associated backend configuration values, as they can perform in-memory operation, independently of any given backend.

`of_contents c`

is the subtree built from the contents `c`

.

`kind t k`

is the type of `s`

in `t`

. It could either be a tree node or some file contents. It is `None`

if `k`

is not present in `t`

.

`val is_empty : tree -> bool`

`diff x y`

is the difference of contents between `x`

and `y`

.

`type 'a or_error = ('a, [ `Dangling_hash of hash ]) Stdlib.result`

Operations on lazy nodes can fail if the underlying store does not contain the expected hash.

`module Contents : sig ... end`

Operations on lazy tree contents.

`find_all t k`

is `Some (b, m)`

if `k`

is associated to the contents `b`

and metadata `m`

in `t`

and `None`

if `k`

is not present in `t`

.

`val length : node -> int Lwt.t`

`find n`

is the number of entries in `n`

.

`find`

is similar to `find_all`

but it discards metadata.

Same as `find_all`

but raise `Invalid_arg`

if `k`

is not present in `t`

.

`list t key`

is the list of files and sub-nodes stored under `k`

in `t`

. The result order is not specified but is stable.

`offset`

and `length`

are used for pagination.

`add t k c`

is the tree where the key `k`

is bound to the contents `c`

but is similar to `t`

for other bindings.

`val update : tree -> key -> ?metadata:metadata -> (contents option -> contents option) -> tree Lwt.t`

`update t k f`

is the tree `t'`

that is the same as `t`

for all keys except `k`

, and whose binding for `k`

is determined by `f (find t k)`

.

If `k`

refers to an internal node of `t`

, `f`

is called with `None`

to determine the value with which to replace it.

`remove t k`

is the tree where `k`

bindings has been removed but is similar to `t`

for other bindings.

`find_tree t k`

is `Some v`

if `k`

is associated to `v`

in `t`

. It is `None`

if `k`

is not present in `t`

.

`get_tree t k`

is `v`

if `k`

is associated to `v`

in `t`

. Raise `Invalid_arg`

if `k`

is not present in `t`

.

`add_tree t k v`

is the tree where the key `k`

is bound to the non-empty tree `v`

but is similar to `t`

for other bindings.

If `v`

is empty, this is equivalent to `remove t k`

.

`update_tree t k f`

is the tree `t'`

that is the same as `t`

for all subtrees except under `k`

, and whose subtree at `k`

is determined by `f (find_tree t k)`

.

`f`

returning either `None`

or `Some empty`

causes the subtree at `k`

to be unbound (i.e. it is equivalent to `remove t k`

).

`val destruct : tree -> [ `Node of node | `Contents of Contents.t * metadata ]`

General-purpose destructor for trees.

`val empty_marks : unit -> marks`

`empty_marks ()`

is an empty collection of marks.

The type for `fold`

's `force`

parameter. ``True`

forces the fold to read the objects of the lazy nodes and contents. ``False f`

is applying `f`

on every lazy node and content value instead. ``And_clear`

is like ``True`

but also eagerly empties the Tree caches when traversing sub-nodes.

The type for `fold`

's `uniq`

parameters. ``False`

folds over all the nodes. ``True`

does not recurse on nodes already seen. ``Marks m`

uses the collection of marks `m`

to store the cache of keys: the fold will modify `m`

. This can be used for incremental folds.

The type for fold depths.

`Eq d`

folds over nodes and contents of depth exactly`d`

.`Lt d`

folds over nodes and contents of depth strictly less than`d`

.`Gt d`

folds over nodes and contents of depth strictly more than`d`

.

`Le d`

is `Eq d`

and `Lt d`

. `Ge d`

is `Eq d`

and `Gt d`

.

```
val fold : ?force:'a force -> ?uniq:uniq -> ?pre:'a node_fn -> ?post:'a node_fn -> ?depth:depth ->
?contents:(key -> contents -> 'a -> 'a Lwt.t) -> ?node:(key -> node -> 'a -> 'a Lwt.t) -> tree -> 'a -> 'a Lwt.t
```

`fold f t acc`

folds `f`

over `t`

's leafs.

For every node `n`

, ui `n`

is a leaf node, call `f path n`

. Otherwise:

- Call
`pre path n`

. By default`pre`

is the identity; - Recursively call
`fold`

on each children, in lexicographic order; - Call
`post path n`

; By default`post`

is the identity.

See `force`

for details about the `force`

parameters. By default it is ``And_clear`

.

See `uniq`

for details about the `uniq`

parameters. By default it is ``False`

.

The fold depth is controlled by the `depth`

parameter.

`type stats = {`

`nodes : int;` | (* Number of node. *) |

`leafs : int;` | (* Number of leafs. *) |

`skips : int;` | (* Number of lazy nodes. *) |

`depth : int;` | (* Maximal depth. *) |

`width : int;` | (* Maximal width. *) |

`}`

The type for tree stats.

`stats ~force t`

are `t`

's statistics. If `force`

is true, this will force the reading of lazy nodes. By default it is `false`

.

The type for concrete trees.

`to_concrete t`

is the concrete tree equivalent of the subtree `t`

.

`val clear : ?depth:int -> tree -> unit`

`clear ?depth t`

clears all caches in the tree `t`

for subtrees with a depth higher than `depth`

. If `depth`

is not set, all of the subtrees are cleared.

`val counters : unit -> counters`

`val inspect : tree -> [ `Contents | `Node of [ `Map | `Hash | `Value ] ]`

`val of_hash : Repo.t -> kinded_hash -> tree option Lwt.t`

`of_hash r h`

is the the tree object in `r`

having `h`

as hash, or `None`

is no such tree object exists.

`val shallow : Repo.t -> kinded_hash -> tree`

`shallow r h`

is the shallow tree object with the hash `h`

. No check is performed to verify if `h`

actually exists in `r`

.