Source file sigs.ml

(*****************************************************************************)
(*                                                                           *)
(* Open Source License                                                       *)
(* Copyright (c) 2022 Nomadic Labs, <contact@nomadic-labs.com>               *)
(*                                                                           *)
(* Permission is hereby granted, free of charge, to any person obtaining a   *)
(* copy of this software and associated documentation files (the "Software"),*)
(* to deal in the Software without restriction, including without limitation *)
(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
(* and/or sell copies of the Software, and to permit persons to whom the     *)
(* Software is furnished to do so, subject to the following conditions:      *)
(*                                                                           *)
(* The above copyright notice and this permission notice shall be included   *)
(* in all copies or substantial portions of the Software.                    *)
(*                                                                           *)
(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
(* DEALINGS IN THE SOFTWARE.                                                 *)
(*                                                                           *)
(*****************************************************************************)

(** {1 Caches}

    Rache is a cache library for resources.

    Because these caches are intended for resources, they are careful about
    ownership. There are more details about this in the documentation of each
    function; briefly it means that when you put a value in the cache, the cache
    becomes responsible for cleaning the resource (would the cache happen to
    overflow and discard it), and when you take a value from the cache you
    become responsible for cleaning it.

    A [TRANSFER] is a collection of key-resource bindings which
    automatically cleans-up resources. You can borrow resources or take
    ownership of them. It is unsafe to use a resource that you don't have
    ownership of or that you haven't borrowed.

    A [BORROW] is a collection of key-resources bindings in which
    resources are both automatically generated and cleaned-up. You can only
    borrow resources from this cache.

*)


module type TRANSFER = sig

  (** A Mutable structure akin to a hash-table, but with a size bound. When an
      element is added that would cause the size to overflow the bound, a
      different element is removed.

      [TRANSFER] caches are intended to hold resources (think
      file-descriptors or database connections). To that end, a [TRANSFER]
      cleans-up resources when they are removed. When using this cache, be
      mindful about ownership and ownership transfer as detailed in the
      documentation of each function bellow.

      Note that, different caches have different policies towards the size
      bounds: some uphold the bound strictly, some treat the bound as a
      suggestion. In addition, some caches count their elements somewhat
      sloppily.

      In general, the caches of Rache are intended to be used in settings that
      do not require strict, by-the-number, extremely-predictable behaviors.

      See [Rache] (or [Functors]) for more information. *)

  (** The type of keys on which resources in the cache are indexed. *)
  type key

  (** The type of caches holding bindings from [key] to ['resource] *)
  type 'resource t

  (** [create destroy n] creates a cache with a size-bound of [n]. Remember that the
      size-bound is not upheld strictly by all caches. Moreover, caches
      instantiated with a specialised size (i.e., empty and singleton caches)
      ignore the size parameter entirely. *)
  val create : (key -> 'resource -> unit) -> int -> 'resource t

  (** {2 Transferring ownership} *)

  (** [put c k v] binds the key [k] to the resource [r] in the cache [c] and
      transfer the ownership of [r] to the cache. After [put], it is the cache's
      responsibility (not yours) to clean-up the resource.

      If [k] is already bound to a value in [c], the previous binding disappears
      and is replaced by the new binding to [r]. If this happens, the resource
      for the previous binding is cleaned-up by the cache.

      If the cache is already at capacity, [put] may cause another binding to be
      removed from the cache to make room for the new one. If this happens, the
      resource of the removed binding is cleaned-up by the cache. *)
  val put : 'resource t -> key -> 'resource -> unit

  (** [take c k] removes the binding of [k] from [c] and returns it to the
      caller along with the ownership of the associated resource: you are now
      responsible for cleaning-up the resource.

      If [k] is not bound in [c], then [take c k] does nothing. *)
  val take : 'resource t -> key -> 'resource option

  (** [take_all c] returns the list of bindings held by the cache along with the
      ownership of their resources (you are now responsible for cleaning-up) and
      clears the cache entirely. *)
  val take_all : 'resource t -> (key * 'resource) list

  (** [take_some c f] returns a list of bindings [(k,r)] such that [f k r] is
      [true]. The returned bindings are removed from the cache and the ownership
      of their resources is transfered to the caller (you). *)
  val take_some : 'resource t -> (key -> 'resource -> bool) -> (key * 'resource) list

  (** {2 Borrowing resources} *)

  (** [borrow c k f] calls [f] with [r] if [k] is bound to [r] in [c].
      This does not remove the resource from the cache: the cache is still
      responsible for cleaning-up the resource.

      It is unsafe to clean-up the borrowed resource from within [f].

      It is unsafe to use the cache [c] from within the function [f]. If you
      need to do so, you can adopt either of these two approaches:
      - use [take], use the resource, and use [put],
      - make [f] returns a list of operations to perform on the cache and
        process this after [f] has returned.

      Note that the in caches with a non-[FIFO] replacement policy, this may
      have a side effect on the [k]-to-[r] binding. Specifically, in those
      caches, it might make it less likely to be removed when supernumerary
      bindings are inserted. *)
  val borrow : 'resource t -> key -> ('resource -> 'b) -> 'b option

  (** [fold f c init] folds the function [f] and value [init] over the bindings
      of [c] from newest to oldest.

      At each called to [f], the resource of the traversed binding is borrowed
      by [f]. Consequently, the same limitations apply for [fold] as for
      [borrow].

      It is unsafe to clean-up any of the borrowed resources.

      It is unsafe to use the cache from within [f]. If you need to do so, you
      can adopt either of these two approaches:
      - use [take_all], fold over the list of bindings, use [put] on each
        binding,
      - maintain a list of operations to perform on the cache within the fold
        accumulator and process this list once the folding is over.
  *)
  val fold : (key -> 'resource -> 'b -> 'b) -> 'resource t -> 'b -> 'b

  (** [fold_oldest_first] is like [fold] but in reversed order: the elements
      that would be the first to be removed are traversed first. In a [FIFO]
      cache, it is oldest-first traversal.

      The same limitations and warning applies as for [fold]. *)
  val fold_oldest_first : (key -> 'resource -> 'b -> 'b) -> 'resource t -> 'b -> 'b

  (** {2 Removing elements from the cache}

      The removal functions ([remove], [clear], and [filter]) remove the
      specified elements from the cache. In all cases, the resources are
      cleaned-up by the cache.

      Calling removal functions is equivalent to calling the [take*] functions
      and cleaning up the resources yourself.
      *)

  (** [remove c k] removes and cleans-up the binding from [k] in [c].
      If [k] is not bound in [c], it does nothing. *)
  val remove : 'resource t -> key -> unit

  (** [clear c] removes and cleans-up all bindings from [c]. *)
  val clear : 'resource t -> unit

  (** [filter c f] removes and cleans-up all the bindings [(k, v)] such that
      [f k v = false]. *)
  val filter : 'resource t -> (key -> 'resource -> bool) -> unit

  (** {2 Introspecting the cache's state} *)

  (** [length c] is the number of bindings held by [c]. *)
  val length : 'resource t -> int

  (** [capacity c] is the number of bindings [c] can hold:
      [capacity (create n) = n] *)
  val capacity : 'resource t -> int

  module H: Hashtbl.HashedType with type t = key

end

module type BORROW = sig

  (** A Mutable structure akin to a hash-table, but with a size bound. When an
      element is added that would cause the size to overflow the bound, a
      different element is removed.

      [BORROW] caches are intended to hold resources (think
      file-descriptors or database connections). To that end, a [BORROW]
      cleans-up resources when they are removed. When using this cache, be
      mindful about ownership: the cache is the owner of the resources, you can
      only borrow them. You can find more details the documentation of each
      function bellow.

      In other words, a [BORROW] is similar to a [TRANSFER] except that:
      - It only allows borrowing of resources. All resources are under the
        ownership of the cache. Always.
      - It is always unsafe to clean-up resources obtained from a [BORROW].
      - Resources are created by the cache, on-demand. This allows the cache to
        have ownership of the resources from the beginning of their lifetime.

      Note that, different caches have different policies towards the size
      bounds: some uphold the bound strictly, some treat the bound as a
      suggestion. In addition, some caches count their elements somewhat
      sloppily.

      In general, the caches of Rache are intended to be used in settings that
      do not require strict, by-the-number, extremely-predictable behaviors.

      See [Rache] (or [Functors]) for more information. *)

  (** The type of keys on which resources in the cache are indexed. *)
  type key

  (** The type of caches holding bindings from [key] to ['resource] *)
  type 'resource t

  (** [create destroy n] creates a cache with a size-bound of [n]. Remember that
      size-bound is not upheld strictly by all caches. Moreover, caches
      instantiated with a specialised size (i.e., empty and singleton caches)
      ignore the size parameter entirely. *)
  val create : (key -> 'resource -> unit) -> int -> 'resource t

  (** {2 Accessing (and implicitly adding elements)} *)

  (** [borrow_or_make c k mk f]

      If [k] is bound to [r] in [c] then it calls [f r].

      Otherwise, it generates [r] using [mk], then inserts the binding
      [k]-to-[r] in [c], then calls [f r].

      Note that inserting the binding in [c] may cause another binding to be
      removed and its associated resource to be cleaned-up.

      It is unsafe to make use of [c] during the evaluation of [f].

      It is unsafe to clean-up [r].

      Note that the in caches with a non-[FIFO] replacement policy, this may
      have a side effect on the [k]-to-[r] binding. Specifically, in those
      caches, it might make it less likely to be removed when supernumerary
      bindings are inserted. *)
  val borrow_or_make : 'resource t -> key -> (key -> 'resource) -> ('resource -> 'a) -> 'a

  (** [borrow c k f] calls [f] with [r] if [k] is bound to [r] in [c].
      This does not remove the resource from the cache: the cache is still
      responsible for cleaning-up the resource.

      It is unsafe to use the cache from within the function [f].

      It is unsafe to clean-up [r].

      Note that the in caches with a non-[FIFO] replacement policy, this may
      have a side effect on the [k]-to-[v] binding. Specifically, in those
      caches, it might make it less likely to be removed when supernumerary
      bindings are inserted. *)
  val borrow : 'resource t -> key -> ('resource -> 'b) -> 'b option

  (** [fold f c init] folds the function [f] and value [init] over the bindings
      of [c] from newest to oldest.

      At each called to [f], the resource of the traversed binding is borrowed
      by [f]. Consequently, the same limitations apply for [fold] as for
      [borrow].

      It is unsafe to clean-up any of the borrowed resources.

      It is unsafe to use the cache from within [f]. *)
  val fold : (key -> 'resource -> 'b -> 'b) -> 'resource t -> 'b -> 'b

  (** [fold_oldest_first] is like [fold] but in reversed order: the elements
      that would be the first to be removed are traversed first. In a [FIFO]
      cache, it is oldest-first traversal.

      The same limitations and warning applies as for [fold]. *)
  val fold_oldest_first : (key -> 'resource -> 'b -> 'b) -> 'resource t -> 'b -> 'b


  (** {2 Removing elements from the cache}

      The removal functions ([remove], [clear], and [filter]) remove the
      specified elements from the cache. In all cases, the resources are
      cleaned-up by the cache. *)

  (** [remove c k] removes and cleans-up the binding from [k] in [c].
      If [k] is not bound in [c], it does nothing. *)
  val remove : 'resource t -> key -> unit

  (** [clear c] removes and cleans-up all bindings from [c]. *)
  val clear : 'resource t -> unit

  (** [filter c f] removes and cleans-up all the bindings [(k, v)] such that
      [f k v = false]. *)
  val filter : 'resource t -> (key -> 'resource -> bool) -> unit

  (** {2 Introspecting the cache's state} *)

  (** [length c] is the number of bindings held by [c]. *)
  val length : 'resource t -> int

  (** [capacity c] is the number of bindings [c] can hold:
      [capacity (create n) = n] *)
  val capacity : 'resource t -> int

  module H: Hashtbl.HashedType with type t = key

end