Module Tree.Make

Parameters

module B : Backend.S

Signature

include S with type contents = B.Contents.value and type contents_key = B.Contents.Key.t and type hash = B.Hash.t
type contents = B.Contents.value
val contents_t : contents Type.t
type contents_key = B.Contents.Key.t
val contents_key_t : contents_key Type.t
type node
val node_t : node Type.t
type hash = B.Hash.t
val hash_t : hash Type.t

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.

type t

The type of trees.

val t : t Type.t

Constructors

val empty : unit -> t

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 singleton : Path.t -> contents -> t

singleton k c is the tree with a single binding mapping the key k to the contents c.

val of_contents : contents -> t

of_contents c is the subtree built from the contents c.

val of_node : node -> t

of_node n is the subtree built from the node n.

type elt = [
  1. | `Node of node
  2. | `Contents of contents
]

The type for tree elements.

val init : elt -> t

General-purpose constructor for trees.

type kinded_hash = [
  1. | `Contents of hash
  2. | `Node of hash
]
val kinded_hash_t : kinded_hash Type.t
val pruned : kinded_hash -> t

pruned h is a purely in-memory tree with the hash h. Such trees can be used as children of other in-memory tree nodes, for instance in order to compute the hash of the parent, but they cannot be dereferenced.

Any operation that would require loading the contents of a pruned node (e.g. calling find on one of its children) will instead raise a Pruned_hash exception. Attempting to export a tree containing pruned sub-trees to a repository will fail similarly.

val kind : t -> Path.t -> [ `Contents | `Node ] option

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 : t -> 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

val diff : t -> t -> (Path.t * contents Diff.t) list

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

Manipulating Contents

exception Dangling_hash of {
  1. context : string;
  2. hash : hash;
}

The exception raised by functions that can force lazy tree nodes but do not return an explicit or_error.

exception Pruned_hash of {
  1. context : string;
  2. hash : hash;
}

The exception raised by functions that attempts to load pruned tree nodes.

exception Portable_value of {
  1. context : string;
}

The exception raised by functions that attemps to perform IO on a portable tree.

type error = [
  1. | `Dangling_hash of hash
  2. | `Pruned_hash of hash
  3. | `Portable_value
]
type 'a or_error = ('a, error) Stdlib.result
module Contents : sig ... end

Operations on lazy tree contents.

val mem : t -> Path.t -> bool

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

val find_all : t -> Path.t -> contents option

find_all t k is Some (b, m) if k is associated to the contents b in t and None if k is not present in t.

val length : t -> ?cache:bool -> Path.t -> int

length t key is the number of files and sub-nodes stored under key in t.

It is equivalent to List.length (list t k) but backends might optimise this call: for instance it's a constant time operation in brassaia-pack.

cache defaults to true, see caching for an explanation of the parameter.

val find : t -> Path.t -> contents option

find is similar to find_all.

val get_all : t -> Path.t -> contents

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

val list : t -> ?offset:int -> ?length:int -> ?cache:bool -> Path.t -> (Path.step * t) list

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.

cache defaults to true, see caching for an explanation of the parameter.

val seq : t -> ?offset:int -> ?length:int -> ?cache:bool -> Path.t -> (Path.step * t) Import.Seq.t

seq t key follows the same behavior as list but returns a sequence.

val get : t -> Path.t -> contents

Same as get_all

val add : t -> Path.t -> contents -> 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 update : t -> Path.t -> (contents option -> contents option) -> 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.

val remove : t -> Path.t -> 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 : t -> Path.t -> bool

mem_tree t k is false iff find_tree k = None.

val find_tree : t -> Path.t -> t option

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 : t -> Path.t -> 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 : t -> Path.t -> t -> 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.

val update_tree : t -> Path.t -> (t option -> t option) -> 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).

val merge : t Merge.t

merge is the 3-way merge function for trees.

Folds

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

General-purpose destructor for trees.

type marks

The type for fold marks.

val empty_marks : unit -> marks

empty_marks () is an empty collection of marks.

type 'a force = [
  1. | `True
  2. | `False of Path.t -> 'a -> 'a
]

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.

type uniq = [
  1. | `False
  2. | `True
  3. | `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, 'b) folder = Path.t -> 'b -> 'a -> 'a

The type for fold's folders: pre, post, contents, node, and tree, where 'a is the accumulator and 'b is the item folded.

type depth = [
  1. | `Eq of int
  2. | `Le of int
  3. | `Lt of int
  4. | `Ge of int
  5. | `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.

val depth_t : depth Type.t
val fold : ?order:[ `Sorted | `Undefined | `Random of Stdlib.Random.State.t ] -> ?force:'a force -> ?cache:bool -> ?uniq:uniq -> ?pre:('a, Path.step list) folder -> ?post:('a, Path.step list) folder -> ?depth:depth -> ?contents:('a, contents) folder -> ?node:('a, node) folder -> ?tree:('a, t) folder -> t -> 'a -> 'a

fold t acc folds over t's nodes with node-specific folders: contents, node, and tree, based on a node's kind.

The default for all folders is identity.

For every node n of t, including itself:

  • If n is a `Contents kind, call contents path c where c is the contents of n.
  • If n is a `Node kind, (1) call pre path steps; (2) call node path n; (3) recursively fold on each child; (4) call post path steps.
  • If n is any kind, call tree path t' where t' is the tree of n.

See examples/fold.ml for a demo of the different folders.

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.

The fold depth is controlled by the depth parameter.

cache defaults to false, see caching for an explanation of the parameter.

If order is `Sorted (the default), the elements are traversed in lexicographic order of their keys. If `Random state, they are traversed in a random order. For large nodes, these two modes are memory-consuming, use `Undefined for a more memory efficient fold.

Stats

type stats = {
  1. nodes : int;
    (*

    Number of node.

    *)
  2. leafs : int;
    (*

    Number of leafs.

    *)
  3. skips : int;
    (*

    Number of lazy nodes.

    *)
  4. depth : int;
    (*

    Maximal depth.

    *)
  5. width : int;
    (*

    Maximal width.

    *)
}

The type for tree stats.

val stats_t : stats Type.t
val stats : ?force:bool -> t -> 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.

Concrete Trees

type concrete = [
  1. | `Tree of (Path.step * concrete) list
  2. | `Contents of contents
]

The type for concrete trees.

val concrete_t : concrete Type.t
val of_concrete : concrete -> t

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

  • raises Invalid_argument

    if c contains duplicate bindings for a given path.

val to_concrete : t -> concrete

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

Proofs

module Proof : sig ... end

Caches

val clear : ?depth:int -> t -> 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.

A call to clear doesn't discard the subtrees of t, only their cache are discarded. Even the lazily loaded and unmodified subtrees remain.

Performance counters

type counters = {
  1. contents_hash : int;
  2. contents_find : int;
  3. contents_add : int;
  4. contents_mem : int;
  5. node_hash : int;
  6. node_mem : int;
  7. node_index : int;
  8. node_add : int;
  9. node_find : int;
  10. node_val_v : int;
  11. node_val_find : int;
  12. node_val_list : int;
}
val counters : unit -> counters
val dump_counters : unit Fmt.t
val reset_counters : unit -> unit
val inspect : t -> [ `Contents | `Node of [ `Map | `Key | `Value | `Portable_dirty | `Pruned ] ]

inspect t is similar to kind, with additional state information for nodes. It is primarily useful for debugging and testing.

If t holds a node, additional information about its state is included:

  • `Map, if t is from of_concrete.
  • `Value, if t's node has modifications that have not been persisted to a store.
  • `Portable_dirty, if t's node has modifications and is Node.Portable. Currently only used with Proof.
  • `Pruned, if t is from pruned.
  • Otherwise `Key, the default state for a node loaded from a store.
module Private : sig ... end
type kinded_key = [
  1. | `Contents of B.Contents.Key.t
  2. | `Node of B.Node.Key.t
]
val kinded_key_t : kinded_key Type.t
val import : B.Repo.t -> kinded_key -> t option
val import_no_check : B.Repo.t -> kinded_key -> t
val export : ?clear:bool -> B.Repo.t -> [> Import.write ] B.Contents.t -> [> Import.read_write ] B.Node.t -> node -> B.Node.key
val dump : t Fmt.t
val equal : t -> t -> bool
val key : t -> kinded_key option
val hash : ?cache:bool -> t -> kinded_hash
val to_backend_node : node -> B.Node.Val.t
val to_backend_portable_node : node -> B.Node_portable.t
val of_backend_node : B.Repo.t -> B.Node.value -> node
type 'result producer := B.Repo.t -> kinded_key -> (t -> t * 'result) -> Proof.t * 'result
type verifier_error = [
  1. | `Proof_mismatch of string
]
val verifier_error_t : verifier_error Type.t
type 'result verifier := Proof.t -> (t -> t * 'result) -> (t * 'result, verifier_error) Stdlib.result
val produce_proof : 'a producer
val verify_proof : 'a verifier
val hash_of_proof_state : Proof.tree -> kinded_hash