(*
 * Env library
 * Copyright (C) 2006 Julien SIGNOLES
 * 
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License version 2, as published by the Free Software Foundation.
 * 
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * 
 * See the GNU Library General Public License version 2 for more details
 *)

(** This library defines generic environments used to deal with symbolic
    manipulation. An environment contain a stack of tables (often 1 or 2)
    mapping keys (usually identifiers) to values. Each table is whether a
    persistent (i.e. immutable) suited to represent local context or an
    imperative (i.e. mutable) datastructure suited to represent global context.

    For example, in a simplified caml language, there is global (let) and local
    (let in) definitions. Typing requires an environment mapping identifier to
    types. This environnement contains an imperative table for the global
    context and, for each declaration, a persistent table (on the top of the
    stack) for the local context: if you search a value, first check the local
    context and, if the value is not found, check the global one. *)

(** Signature of keys: input signature of the functor [Make]. *)
module type COMPARABLE = sig
  type t
  val compare: t -> t -> int
  val equal: t -> t -> bool
  val hash: t -> int
end

(** Signature of an environment: output signature of the functor [Make]. *)
module type S = sig

  (** {1 Datatypes} *)

  (** Type of keys. *)
  type key

  (** A table in an environment may be wether persistent (i.e. immutable) or
      imperative (i.e. mutable). An imperative table is more efficient but a
      persistent one is useful for backtracking. *)
  type kind = Persistent | Imperative

  (** Type of an environment containing values of type ['a]. *)
  type 'a t

  (** {1 Global operations} *)

  (** Create a new environment containing one table of the specified kind. *)
  val create: kind -> 'a t

  (** Check emptyness of an environment. *)
  val is_empty: 'a t -> bool

  (** Copy of an environment. No sharing between the environment and its
      copy. *)
  val copy: 'a t -> 'a t

  (** {1 Operations on keys} *)

  (** [add key data env] maps [key] to [data] in the table [t] on the top of
      [env]. The previous binding of [key] in [t] disappears and the current
      binding of [key] in [env], if any, is simply hidden. That is, after
      performing [remove key env] or [pop env], this binding is restored (it is
      again visible). Raise [Empty] if [env] contains no table. *) 
  val add: key -> 'a -> 'a t -> 'a t
    
  (** [remove key env] removes the current binding of [key] in [env], restoring
      the previous binding of [key], if it exists. It does nothing if [key] is
      unbound in [env]. *)
  val remove: key -> 'a t -> 'a t

  (** [find key env] returns the current binding of [key] in [env]. Raise
      [Not_found] if no such binding exists. *)
  val find: key -> 'a t -> 'a

  (** [find_all key env] returns the list of all data associated with [key] in
      [env]. The current binding is returned first, then the previous bindings,
      in reverse order of introduction in the environment. *) 
  val find_all: key -> 'a t -> 'a list

  (** [mem key env] checks if [key] is bound in [env]. *)
  val mem: key -> 'a t -> bool

  (** {1 Iterators} *)

  (** [iter f env] applies f to all current bindings in [env]. [f] receives the
      key as first argument, and the associated value as second argument. Each
      binding is presented exactly once to f. The order in which the bindings
      are passed to [f] is unspecified. *) 
  val iter: (key -> 'a -> unit) -> 'a t -> unit

  (** [iter_all f env] is similar to [iter f env] but applies [f] to all
      bindings in [env] (and not only to the current bindings). Morever, if the
      environment contains several bindings for the same key, they are passed
      to [f] in reverse order of introduction, that is, the most recent binding
      is passed first. *) 
  val iter_all: (key -> 'a -> unit) -> 'a t -> unit

  (** [fold f env init] computes [f kN dN ... (f k1 d1 init) ...], where
      [k1 ... kN] are the keys of all current bindings in [env], and [d1
      ... dN] are the associated values. Each binding is presented exactly once
      to [f]. The order in which the bindings are passed to [f] is
      unspecified. *)
  val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

  (**  [fold_all f env init] is similar to [fold f env] but applies [f] to all
       bindings in [env] (and not only to the current bindings). Morever, if
       the environment contains several bindings for the same key, they are
       passed to [f] in reverse order of introduction, that is, the most recent
       binding is passed first. *) 
  val fold_all: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b

  (** {1 Operations on tables} *)

  exception Empty

  (** [push k env] returns a new environment with a new table of the specified
      kind on the top of [env]. *)
  val push: kind -> 'a t -> 'a t

  (** [pop env] returns a new environment which is [env] without the top
      table. The bindings hidde by the popped table are restored. Raise [Empty]
      if [env] contains no table. Be aware of sharing if you use imperative
      tables. *)
  val pop: 'a t -> 'a t

  (** [top env] returns an environment containing only the table on the top of
      [env]. Raise [Empty] if [env] contains no table. Be aware of sharing if
      you use imperative tables. *)
  val top: 'a t -> 'a t

end

(** Build an implementation of an environment given an ordered and hashable
    type. *)
module Make(Key : COMPARABLE) : S with type key = Key.t

(** {1 Generic version} *)

(** This version may be used if you have optimised data structures dealing with
    your keys, e.g. patricia trees. *)

(** Signature of maps of keys (subtype of Map.S) *)
module type MAP = sig
  type key
  type 'a t
  val empty: 'a t
  val is_empty: 'a t -> bool
  val add: key -> 'a -> 'a t -> 'a t
  val remove: key -> 'a t -> 'a t
  val find: key -> 'a t -> 'a
  val mem: key -> 'a t -> bool
  val iter: (key -> 'a -> unit) -> 'a t -> unit
  val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
end

(** Signature of hashtbl of keys (subtype of Hashtbl.S) *)
module type HASHTBL = sig
  type key
  type 'a t
  val create: int -> 'a t
  val length: 'a t -> int
  val add: 'a t -> key -> 'a -> unit
  val remove: 'a t -> key -> unit
  val find: 'a t -> key -> 'a
  val find_all: 'a t -> key -> 'a list
  val mem: 'a t -> key -> bool
  val iter: (key -> 'a -> unit) -> 'a t -> unit
  val fold: (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b   
end

(** Build an implementation of an environment given an implementation of maps
    and hashtables. *)
module Build(Map : MAP)(Hashtbl : HASHTBL with type key = Map.key) :
  S with type key = Map.key

This document was generated using caml2html