package tezos-lwt-result-stdlib

  1. Overview
  2. Docs
package tezos-lwt-result-stdlib
Legend:
Library
Module
Module type
Parameter
Class
Class type

Hashtables with the signature S_ES are Hashtbl-like with the following differences:

First, the module exports only a few functions in an attempt to limit the likelihood of race-conditions. Of particular interest is the following: in order to insert a value, one has to use `find_or_make` which either returns an existing promise for a value bound to the given key, or makes such a promise. It is not possible to insert another value for an existing key. This limits the table (e.g., it can only hold one value for any given key), but it forces the user to *atomically* test membership and insert an element.

Second, the table is automatically cleaned. Specifically, when a promise for a value is fulfilled with an Error _, the binding is removed. This leads to the following behavior:

(* setup *)
let t = create 256 in
let () = assert (length t = 0) in

(* insert a first promise for a value *)
let p, r = Lwt.task () in
let i1 = find_or_make t 1 (fun () -> p) in
let () = assert (length t = 1) in

(* because the same key is used, the promise is not inserted. *)
let i2 = find_or_make t 1 (fun () -> assert false) in
let () = assert (length t = 1) in

(* when the original promise errors, the binding is removed *)
let () = Lwt.wakeup r (Error ..) in
let () = assert (length t = 0) in

(* and both [find_or_make] promises have the error *)
let () = match Lwt.state i1 with
  | Return (Error ..) -> ()
  | _ -> assert false
in
let () = match Lwt.state i2 with
  | Return (Error ..) -> ()
  | _ -> assert false
in

This automatic cleaning relieves the user from the responsibility of cleaning the table (which is another possible source of race condition).

For consistency, traversal functions ignore Error _ and rejections.

Third, every time a promise is removed from the table (be it by clean, reset, or just remove), the promise is canceled.

type key
type ('a, 'trace) t
val create : int -> ('a, 'trace) t
val clear : ('a, 'trace) t -> unit

clear tbl cancels and removes all the promises in tbl.

val reset : ('a, 'trace) t -> unit

reset tbl cancels and removes all the promises in tbl, and resizes tbl to its initial size.

val find_or_make : ('a, 'trace) t -> key -> (unit -> ('a, 'trace) result Lwt.t) -> ('a, 'trace) result Lwt.t

find_or_make tbl k make behaves differently depending on k being bound in tbl:

  • if k is bound in tbl then find_or_make tbl k make returns the promise p that k is bound to. This p might be already fulfilled with Ok _ or it might be pending. This p cannot be already fulfilled with Error _ or already rejected. This is because Error/rejected promises are removed from the table automatically. Note however that if this p is pending, p might become fulfilled with Error _ or become rejected.
  • if k is not bound in tbl then make () is called and the returned promise p is bound to k in tbl. Then p is returned. When p is resolved, it may be removed automatically from tbl as described above.
val remove : ('a, 'trace) t -> key -> unit

remove tbl k cancels the promise bound to k in tbl and removes it. If k is not bound in tbl it does nothing.

val find : ('a, 'trace) t -> key -> ('a, 'trace) result Lwt.t option
val mem : ('a, 'trace) t -> key -> bool
val iter_with_waiting_es : (key -> 'a -> (unit, 'trace) result Lwt.t) -> ('a, 'trace) t -> (unit, 'trace) result Lwt.t

iter_with_waiting_es f tbl iterates f over the bindings in tbl.

Specifically, for each binding (k, p) it waits for p to be fulfilled with Ok v and calls f k v. If p fulfills with Error _ or is rejected, then no call to f is made for this binding. Note however that an Error/rejection in one promise returned by f interrupts the iteration.

It processes bindings one after the other: it waits for both the bound promise to resolve and then the call promise to resolve before continuing to the next binding.

val iter_with_waiting_ep : (key -> 'a -> (unit, 'error) result Lwt.t) -> ('a, 'error) t -> (unit, 'error list) result Lwt.t

iter_with_waiting_ep f tbl iterates f over the bindings in tbl.

Specifically, for each binding (k, p) it waits for p to be fulfilled with Ok v and calls f k v. If p fulfills with Error _ or is rejected, then no call is made for this binding.

Note however that if one (or more) of the promises returned by f ends in Error/rejection, the final result of this promise is an Error/rejection. Even so, it only resolves once all the promises have.

It processes all bindings concurrently: it concurrently waits for all the bound promises to resolve and calls f as they resolve.

val fold_with_waiting_es : (key -> 'a -> 'b -> ('b, 'trace) result Lwt.t) -> ('a, 'trace) t -> 'b -> ('b, 'trace) result Lwt.t

fold_with_waiting_es f tbl init folds init with f over the bindings in tbl.

Specifically, for each binding (k, p) it waits for p to be fulfilled with Ok v and determines the next accumulator by calling f k v acc. If p fulfills with Error _ or is rejected, then no call is made for this binding.

It processes bindings one after the other.

val fold_keys : (key -> 'b -> 'b) -> ('a, 'trace) t -> 'b -> 'b
val fold_promises : (key -> ('a, 'trace) result Lwt.t -> 'b -> 'b) -> ('a, 'trace) t -> 'b -> 'b

fold_promises f tbl init folds over the table, passing the raw promises to f. This means that f can observe Error/rejections.

This can be used to, e.g., count the number of resolved/unresolved promises.

val fold_resolved : (key -> 'a -> 'b -> 'b) -> ('a, 'trace) t -> 'b -> 'b

fold_resolved f tbl init folds over the already resolved promises of tbl. More specifically, it folds over the v for all the promises fulfilled with Ok v that are bound in tbl.

val length : ('a, 'trace) t -> int
val stats : ('a, 'trace) t -> Hashtbl.statistics