Module KV.Tree

Managing store's trees.

Constructors

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.

val of_contents : ?⁠metadata:metadata -> contents -> tree

of_contents c is the subtree built from the contents c.

val of_node : node -> tree

of_node n is the subtree built from the node n.

val v : [< `Node of node | `Contents of contents * metadata ] -> tree

General-purpose constructor for trees.

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

General-purpose destructor for trees.

val kind : tree -> key -> [ `Contents | `Node ] option Lwt.t

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 list : tree -> key -> (step * [ `Contents | `Node ]) list Lwt.t

list t key is the list of files and sub-nodes stored under k in t.

Diffs

val diff : tree -> tree -> (key * (contents * metadata) Diff.t) list Lwt.t

diff x y is the difference of contents between x and y.

Manipulating Contents

val mem : tree -> key -> bool Lwt.t

mem t k is true iff k is associated to some contents in t.

val find_all : tree -> key -> (contents * metadata) option Lwt.t

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 find : tree -> key -> contents option Lwt.t

find is similar to find_all but it discards metadata.

val get_all : tree -> key -> (contents * metadata) Lwt.t

Same as find_all but raise Invalid_arg if k is not present in t.

val get : tree -> key -> contents Lwt.t

Same as get_all but ignore the metadata.

val add : tree -> key -> ?⁠metadata:metadata -> contents -> tree Lwt.t

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 remove : tree -> key -> tree Lwt.t

remove t k is the tree where k bindings has been removed but is similar to t for other bindings.

Manipulating Subtrees

val mem_tree : tree -> key -> bool Lwt.t

mem_tree t k is false iff find_tree k = None.

val find_tree : tree -> key -> tree option Lwt.t

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.

val get_tree : tree -> key -> tree Lwt.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.

val add_tree : tree -> key -> tree -> tree Lwt.t

add_tree t k v is the tree where the key k is bound to the tree v but is similar to t for other bindings

val merge : tree Merge.t

merge is the 3-way merge function for trees.

Folds

type marks

The type for fold marks.

val empty_marks : unit -> marks

empty_marks () is an empty collection of marks.

type 'a force = [
| `True
| `False of key -> 'a -> 'a Lwt.t
]

The type for fold's force parameter. `True forces the fold to read the objects of the lazy nodes. `False f is applying f on every lazy node instead.

type uniq = [
| `False
| `True
| `Marks of marks
]

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.

type 'a node_fn = key -> step list -> 'a -> 'a Lwt.t

The type for fold's pre and post parameters.

val fold : ?⁠force:'a force -> ?⁠uniq:uniq -> ?⁠pre:'a node_fn -> ?⁠post:'a node_fn -> (key -> contents -> '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 `True.

See uniq for details about the uniq parameters. By default it is `False.

Stats

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.

val pp_stats : stats Fmt.t

pp_stats is the pretty printer for tree statistics.

val stats : ?⁠force:bool -> tree -> stats Lwt.t

stats ~force t are t's statistics. If force is true, this will force the reading of lazy nodes. By default it is false.

Concrete Trees

type concrete = [
| `Tree of (step * concrete) list
| `Contents of contents * metadata
]

The type for concrete trees.

val concrete_t : concrete Type.t

The value-type for concrete.

val of_concrete : concrete -> tree

of_concrete c is the subtree equivalent to the concrete tree c.

val to_concrete : tree -> concrete Lwt.t

to_concrete t is the concrete tree equivalent to the subtree t.

Caches

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

clear ?depth t clears all the cache in the tree t for subtrees with a depth higher than depth. If depth is not set, all the subtrees are cleared.

Performance counters

type counters = {
mutable contents_hash : int;
mutable contents_find : int;
mutable contents_add : int;
mutable node_hash : int;
mutable node_mem : int;
mutable node_add : int;
mutable node_find : int;
mutable node_val_v : int;
mutable node_val_find : int;
mutable node_val_list : int;
}
val counters : unit -> counters
val dump_counters : unit Fmt.t
val reset_counters : unit -> unit
val inspect : tree -> [ `Contents | `Node of [ `Map | `Hash | `Value ] ]

Import/Export

val hash : tree -> hash

hash r c it c's hash in the repository r.

val of_hash : Repo.t -> 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 -> 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.