[lib] Split auxiliary libraries into Coq-specific and general.

Up to this point the `lib` directory contained two different library
archives, `clib.cma` and `lib.cma`, which a rough splitting between
Coq-specific libraries and general-purpose ones.

We know split the directory in two, as to make the distinction clear:

- `clib`: contains libraries that are not Coq specific and implement
  common data structures and programming patterns. These libraries
  could be eventually replace with external dependencies and the rest
  of the code base wouldn't notice much.

- `lib`: contains Coq-specific common libraries in widespread use
  along the codebase, but that are not considered part of other
  components. Examples are printing, error handling, or flags.

In some cases we have coupling due to utility files depending on Coq
specific flags, however this commit doesn't modify any files, but only
moves them around, further cleanup is welcome, as indeed a few files
in `lib` should likely be placed in `clib`.

Also note that `Deque` is not used ATM.

1 files changed, 79 insertions, 0 deletions

diff --git a/clib/int.mli b/clib/int.mli
new file mode 100644
index 000000000..b65367f7d
--- /dev/null
+++ b/clib/int.mli
@@ -0,0 +1,79 @@
+(************************************************************************)
+(*  v      *   The Coq Proof Assistant  /  The Coq Development Team     *)
+(* <O___,, *   INRIA - CNRS - LIX - LRI - PPS - Copyright 1999-2017     *)
+(*   \VV/  **************************************************************)
+(*    //   *      This file is distributed under the terms of the       *)
+(*         *       GNU Lesser General Public License Version 2.1        *)
+(************************************************************************)
+
+(** A native integer module with usual utility functions. *)
+
+type t = int
+
+external equal : t -> t -> bool = "%eq"
+
+external compare : t -> t -> int = "caml_int_compare"
+
+val hash : t -> int
+
+module Set : Set.S with type elt = t
+module Map : CMap.ExtS with type key = t and module Set := Set
+
+module List : sig
+  val mem : int -> int list -> bool
+  val assoc : int -> (int * 'a) list -> 'a
+  val mem_assoc : int -> (int * 'a) list -> bool
+  val remove_assoc : int -> (int * 'a) list -> (int * 'a) list
+end
+
+module PArray :
+sig
+  type 'a t
+  (** Persistent, auto-resizable arrays. The [get] and [set] functions never
+      fail whenever the index is between [0] and [Sys.max_array_length - 1]. *)
+  val empty : int -> 'a t
+  (** The empty array, with a given starting size. *)
+  val get : 'a t -> int -> 'a option
+  (** Get a value at the given index. Returns [None] if undefined. *)
+  val set : 'a t -> int -> 'a option -> 'a t
+  (** Set/unset a value at the given index. *)
+end
+
+module PMap :
+sig
+  type key = int
+  type 'a t
+  val empty : 'a t
+  val is_empty : 'a t -> bool
+  val mem : key -> 'a t -> bool
+  val add : key -> 'a -> 'a t -> 'a t
+  val singleton : key -> 'a -> 'a t
+  val remove : key -> 'a t -> 'a t
+(*   val merge : (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t *)
+(*   val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int *)
+(*   val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool *)
+  val iter : (key -> 'a -> unit) -> 'a t -> unit
+  val fold : (key -> 'a -> 'b -> 'b) -> 'a t -> 'b -> 'b
+  val for_all : (key -> 'a -> bool) -> 'a t -> bool
+  val exists : (key -> 'a -> bool) -> 'a t -> bool
+(*   val filter : (key -> 'a -> bool) -> 'a t -> 'a t *)
+(*   val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t *)
+(*   val cardinal : 'a t -> int *)
+(*   val bindings : 'a t -> (key * 'a) list *)
+(*   val min_binding : 'a t -> key * 'a *)
+(*   val max_binding : 'a t -> key * 'a *)
+(*   val choose : 'a t -> key * 'a *)
+(*   val split : key -> 'a t -> 'a t * 'a option * 'a t *)
+  val find : key -> 'a t -> 'a
+(*   val map : ('a -> 'b) -> 'a t -> 'b t *)
+(*   val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t *)
+  val domain : 'a t -> Set.t
+  val cast : 'a t -> 'a Map.t
+end
+(** This is a (partial) implementation of a [Map] interface on integers, except
+    that it internally uses persistent arrays. This ensures O(1) accesses in
+    non-backtracking cases. It is thus better suited for zero-starting,
+    contiguous keys, or otherwise a lot of space will be empty. To keep track of
+    the present keys, a binary tree is also used, so that adding a key is
+    still logarithmic. It is therefore essential that most of the operations
+    are accesses and not add/removes. *)