Source file hashable_intf.ml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
open! Import

module type Key = sig
  type t [@@deriving_inline compare, sexp_of]
  include
  sig
    [@@@ocaml.warning "-32"]
    val compare : t -> t -> int
    val sexp_of_t : t -> Ppx_sexp_conv_lib.Sexp.t
  end[@@ocaml.doc "@inline"]
  [@@@end]

  (** Values returned by [hash] must be non-negative.  An exception will be raised in the
      case that [hash] returns a negative value. *)
  val hash : t -> int
end

module Hashable = struct
  type 'a t =
    { hash : 'a -> int;
      compare : 'a -> 'a -> int;
      sexp_of_t : 'a -> Sexp.t;
    }

  (** This function is sound but not complete, meaning that if it returns [true] then it's
      safe to use the two interchangeably.  If it's [false], you have no guarantees.  For
      example:

      {[
        > utop
        open Core;;
        let equal (a : 'a Hashtbl_intf.Hashable.t) b =
          phys_equal a b
          || (phys_equal a.hash b.hash
              && phys_equal a.compare b.compare
              && phys_equal a.sexp_of_t b.sexp_of_t)
        ;;
        let a = Hashtbl_intf.Hashable.{ hash; compare; sexp_of_t = Int.sexp_of_t };;
        let b = Hashtbl_intf.Hashable.{ hash; compare; sexp_of_t = Int.sexp_of_t };;
        equal a b;;  (* false?! *)
      ]}
  *)
  let equal a b =
    phys_equal a b
    || (phys_equal a.hash b.hash
        && phys_equal a.compare b.compare
        && phys_equal a.sexp_of_t b.sexp_of_t)
  ;;

  let hash_param = Caml.Hashtbl.hash_param
  let hash       = Caml.Hashtbl.hash

  let poly = { hash;
               compare = Poly.compare;
               sexp_of_t = (fun _ -> Sexp.Atom "_");
             }

  let of_key (type a) (module Key : Key with type t = a) =
    { hash = Key.hash;
      compare = Key.compare;
      sexp_of_t = Key.sexp_of_t;
    }
  ;;

  let to_key (type a) { hash; compare; sexp_of_t } =
    (module struct
      type t = a
      let hash = hash
      let compare = compare
      let sexp_of_t = sexp_of_t
    end : Key with type t = a)
  ;;
end
include Hashable

module type Hashable = sig
  type 'a t = 'a Hashable.t =
    { hash : 'a -> int;
      compare : 'a -> 'a -> int;
      sexp_of_t : 'a -> Sexp.t;
    }

  val equal : 'a t -> 'a t -> bool

  val poly : 'a t

  val of_key : (module Key with type t = 'a) -> 'a t
  val to_key : 'a t -> (module Key with type t = 'a)

  val hash_param : int -> int -> 'a -> int

  val hash : 'a -> int
end