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

module type HS = sig

   (** A subset of {!Hashtbl.S}. *)

    type key
    type 'a t
    val create: int -> 'a t
    val remove: 'a t -> key -> unit
    val find_opt: 'a t -> key -> 'a option
    val replace : 'a t -> key -> 'a -> unit
    val length: 'a t -> int
    val clear: 'a t -> unit

end

module type TABLER = functor (H: Hashtbl.HashedType) -> (HS with type key = H.t)

(** {1 Caches}

    Vache is a cache library. Below are signatures for caches.

    A [MAP] is a collection of key-value bindings. A [SET] is a
    simple value store.

*)


module type MAP = sig

  (** A Mutable structure akin to a hash-table, but with a size bound. 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 Aches are intended to be used in settings that
      do not require strict, by-the-number, extremely-predictable behaviors.

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

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

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

  (** [create 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 : int -> 'a t

  (** [replace c k v] binds the key [k] to the value [v] in the cache [c]. This
      may or may not cause another binding to be removed from the cache,
      depending on the number of bindings already present in the cache [c], the
      size-bound of the cache [c], and the policy of the cache [c] towards its
      size-bound.

      If [k] is already bound to a value in [c], the previous binding disappears
      and is replaced by the new binding to [v].

      Note that in caches with a [Sloppy] accounting policy, the old (removed)
      binding may still count towards the size bound for some time. *)
  val replace : 'a t -> key -> 'a -> unit

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

      Note that for caches with a [Weak] overflow policy, this function may fold
      over a subset of the bindings of [c]. See [Vache] (or [Functors]) for more
      details. *)
  val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

  (** [fold_oldest_first] is like [fold] but in reversed order: oldest elements
      of [c] first. This function has the same limitation as [fold]. *)
  val fold_oldest_first : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

  (** [find_opt c k] is [Some v] if [k] is bound to [v] in [c]. It is [None]
      otherwise.

      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 find_opt : 'a t -> key -> 'a option

  (** [remove c k] removes the binding from [k] in [c]. If [k] is not bound in
      [c], it does nothing.

      Note that in caches with a [Sloppy] accounting policy, removed bindings
      can still count towards the size bound for some time. *)
  val remove : 'a t -> key -> unit

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

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

  (** [clear c] removes all bindings from [c]. *)
  val clear : 'a t -> unit

  module H: Hashtbl.HashedType with type t = key

end

module type SET = sig

  (** A Mutable structure akin to a set, but with a size bound. 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 Vache are intended to be used in settings that
      do not require strict, by-the-number, extremely-predictable behaviors.

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

  (** The type of values held by the cache. *)
  type elt

  (** The type of caches holding values of type [elt]. *)
  type t

  (** [create n] creates a unit-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 : int -> t

  (** [add c v] adds the value [v] to the cache [c]. This may or may not cause
      another element to be removed from the cache, depending on the number of
      elements already present in the cache [c], the size-bound of the cache
      [c], and the policy of the cache [c] towards its size-bound.

      Note that after the [add c v] call returns, [v] is the most recent element
      in the cache. This is true whether or not the element was already in the
      cache before the call. This is true for whichever replacement policy
      (see {!Vache.replacement}) the cache has.

      If [v] is already present in [c], and the accounting policy of the cache
      is [Sloppy], the element may or may not count twice towards the size bound
      for some time. On the other hand, if the cache accounting is [Precise]
      then the element [v] only counts once. See {!Vache.accounting} for more
      details. *)
  val add : t -> elt -> unit

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

      Note that for caches with a [Weak] overflow policy, this function may fold
      over a subset of the elements of [c]. See [Vache] (or [Functors]) for more
      details. *)
  val fold : (elt -> 'a -> 'a) -> t -> 'a -> 'a

  (** [fold_oldest_first] is like [fold] but in reversed order: oldest elements
      of [c] first. This function has the same limitation as [fold]. *)
  val fold_oldest_first : (elt -> 'a -> 'a) -> t -> 'a -> 'a

  (** [mem c v] is [true] if [v] is present in [c]. It is [false] otherwise.

      Note that the in caches with a non-[FIFO] replacement policy, this may
      have a side effect on the [v] element. Specifically, in those caches, it
      might make it less likely to be removed when supernumerary elements are
      inserted. *)
  val mem : t -> elt -> bool

  (** [remove c v] removes the element [v] from [c]. If [v] is not present in
      [c], it does nothing.

      Note that in caches with a [Sloppy] accounting policy, removed elements
      can still count towards the size bound for some time. On the other hand,
      if the cache's accounting policy is [Precise] then the element immediately
      stops counting towards the size bound. *)
  val remove : t -> elt -> unit

  (** [length c] is the number of elements present in [c]. *)
  val length : t -> int

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

  (** [clear c] removes all elements from [c]. *)
  val clear : t -> unit

end