Module `KV.Tree`Source

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.

Constructors

Sourceval 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.

Sourceval of_contents : ?metadata:metadata -> contents -> tree

of_contents c is the subtree built from the contents c.

Sourceval of_node : node -> tree

of_node n is the subtree built from the node n.

Sourcetype elt = [

| `Node of node
| `Contents of contents * metadata

]

The type for tree elements.

Sourceval v : elt -> tree

General-purpose constructor for trees.

Sourceval 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.

Sourceval is_empty : tree -> bool

is_empty t is true iff t is empty (i.e. a tree node with no children). Trees with kind = `Contents are never considered empty.

Diffs

Source

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

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

Manipulating Contents

Sourcetype 'a or_error = ('a, [ `Dangling_hash of hash ]) result

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

Sourcemodule Contents : sig ... end

Operations on lazy tree contents.

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

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

Sourceval 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.

Sourceval find : tree -> key -> contents option Lwt.t

find is similar to find_all but it discards metadata.

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

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

Source

val list : 
  tree ->
  ?offset:int ->
  ?length:int ->
  key ->
  (step * tree) list Lwt.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.

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

Same as get_all but ignore the metadata.

Sourceval 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.

Source

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.

Sourceval 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

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

mem_tree t k is false iff find_tree k = None.

Sourceval 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.

Sourceval 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.

Sourceval add_tree : tree -> key -> tree -> tree Lwt.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.

Sourceval update_tree : tree -> key -> (tree option -> tree option) -> tree Lwt.t

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).

Sourceval merge : tree Irmin.Merge.t

merge is the 3-way merge function for trees.

Folds

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

General-purpose destructor for trees.

Sourcetype marks

The type for fold marks.

Sourceval empty_marks : unit -> marks

empty_marks () is an empty collection of marks.

Sourcetype 'a force = [

| `True
| `False of key -> 'a -> 'a Lwt.t
| `And_clear

]

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.

Sourcetype 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.

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

The type for fold's pre and post parameters.

Sourcetype depth = [

| `Eq of int
| `Le of int
| `Lt of int
| `Ge of int
| `Gt of int

]

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.

Sourceval depth_t : depth Irmin.Type.t

Source

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.

Stats

Sourcetype 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.

Sourceval stats_t : stats Irmin.Type.t

Sourceval 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

Sourcetype concrete = [

| `Tree of (step * concrete) list
| `Contents of contents * metadata

]

The type for concrete trees.

Sourceval concrete_t : concrete Irmin.Type.t

The value-type for concrete.

Sourceval of_concrete : concrete -> tree

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

raises Invalid_argument
if c contains duplicate bindings for a given path.

Sourceval to_concrete : tree -> concrete Lwt.t

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

Caches

Sourceval 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.

Performance counters

Sourcetype 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;

}

Sourceval counters : unit -> counters

Sourceval dump_counters : unit Fmt.t

Sourceval reset_counters : unit -> unit

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

Import/Export

Sourceval hash : tree -> hash

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

type kinded_hash := [

| `Contents of hash * metadata
| `Node of hash

]

Hashes in the Irmin store are tagged with the type of the value they reference (either contents or node). In the contents case, the hash is paired with corresponding metadata.

Sourceval 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.

Sourceval 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.

Install

Dune Dependency

Authors

Maintainers

Sources

doc/irmin.mem/Irmin_mem/KV/Tree/index.html

Module `KV.Tree`Source

Constructors

Diffs

Manipulating Contents

Manipulating Subtrees

Folds

Stats

Concrete Trees

Caches

Performance counters

Import/Export

package irmin

Install

Dune Dependency

Authors

Maintainers

Sources

doc/irmin.mem/Irmin_mem/KV/Tree/index.html

Module KV.TreeSource

Constructors

Diffs

Manipulating Contents

Manipulating Subtrees

Folds

Stats

Concrete Trees

Caches

Performance counters

Import/Export

Module `KV.Tree`Source