package irmin-unix

  1. Overview
  2. Docs
package irmin-unix
Legend:
Library
Module
Module type
Parameter
Class
Class type

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

val empty : unit -> 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.

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

The type for tree elements.

val v : elt -> tree

General-purpose constructor for trees.

val kinded_hash_t : [ `Contents of hash * metadata | `Node of hash ] Irmin.Type.t
val pruned : [ `Contents of hash * metadata | `Node of hash ] -> tree

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

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

type error = [
  1. | `Dangling_hash of hash
  2. | `Pruned_hash of hash
]

The type for errors.

type 'a or_error = ('a, error) Stdlib.result

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

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

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

module Contents : sig ... end

Operations on lazy tree 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 length : tree -> ?cache:bool -> key -> int Lwt.t

length t key is the number of files and sub-nodes stored under k 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 irmin-pack.

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

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 list : tree -> ?offset:int -> ?length:int -> ?cache:bool -> 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.

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

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

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

val merge : tree Irmin.Merge.t

merge is the 3-way merge function for trees.

Folds

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

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 key -> 'a -> 'a Lwt.t
]

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 node_fn = key -> step list -> 'a -> 'a Lwt.t

The type for fold's pre and post parameters.

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 Irmin.Type.t
val fold : ?order:[ `Sorted | `Undefined | `Random of Stdlib.Random.State.t ] -> ?force:'a force -> ?cache:bool -> ?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:(key -> tree -> '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.
  • 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.

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 Irmin.Type.t
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 = [
  1. | `Tree of (step * concrete) list
  2. | `Contents of contents * metadata
]

The type for concrete trees.

val concrete_t : concrete Irmin.Type.t

The value-type for concrete.

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

val to_concrete : tree -> concrete Lwt.t

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

Proofs

module Proof : sig ... end

Caches

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.

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. mutable contents_hash : int;
  2. mutable contents_find : int;
  3. mutable contents_add : int;
  4. mutable node_hash : int;
  5. mutable node_mem : int;
  6. mutable node_add : int;
  7. mutable node_find : int;
  8. mutable node_val_v : int;
  9. mutable node_val_find : int;
  10. 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 | `Pruned ] ]

/

Internals Useful for testing purposes only.

module Env : sig ... end
val get_env : tree -> Env.t

Import/Export

val hash : ?cache:bool -> tree -> hash

hash c is c's hash.

type kinded_hash := [
  1. | `Contents of hash * metadata
  2. | `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.

val kinded_hash : ?cache:bool -> tree -> kinded_hash

kinded_hash t is c's kinded hash.

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.

Proofs

type ('proof, 'result) producer := repo -> kinded_hash -> (tree -> (tree * 'result) Lwt.t) -> ('proof * 'result) Lwt.t

produce r h f runs f on top of a real store r, producing a proof and a reulst using the initial root hash h.

The trees produced during f's computation will carry the full history of reads. This history will be reset when f is complete so subtrees escaping the scope of f will not cause memory leaks.

It is possible to call produce_proof recursively. In that case, each input trees will have their own history of reads and will contain only the reads needed to unshallow that corresponding trees. Proof trees proof should then interact as if they were all unshallowed (note: in the case of nested proofs, it's unclear what verify_proof should do...).

type ('proof, 'result) verifier := 'proof -> (tree -> (tree * 'result) Lwt.t) -> (tree * 'result, [ `Msg of string ]) Stdlib.result Lwt.t

verify t f runs f in checking mode, loading data from the proof as needed.

When the result is Ok (t, r), t is the generated tree after f has completed and r is the result of the computation. More operations can be run on t, but it won't be able to access the underlying storage and will raise Dangling_hash when trying to read unloaded parts of t.

When the result is Error msg, the proof is rejected.

type tree_proof := Proof.tree Proof.t

The type for tree proofs.

Guarantee that the given computation performs exactly the same state operations as the generating computation, *in some order*.

val produce_proof : (tree_proof, 'a) producer

produce_proof is the producer of tree proofs.

val verify_proof : (tree_proof, 'a) verifier

verify_proof is the verifier of tree proofs.

type stream_proof := Proof.stream Proof.t

The type for stream proofs.

Guarantee that the given computation performs exactly the same state operations as the generating computation, in the exact same order.*in some order*.

val produce_stream : (stream_proof, 'a) producer

produce_stream is the producer of stream proofs.

val verify_stream : (stream_proof, 'a) verifier

verify_stream is the verifier of stream proofs.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct