Source file hashtbl.ml

open! Import

include Hashtbl_intf

let with_return = With_return.with_return

let hash_param = Hashable.hash_param
let hash       = Hashable.hash


type ('k, 'v) t =
  { mutable table            : ('k, 'v) Avltree.t array
  ; mutable length           : int
  (* [recently_added] is the reference passed to [Avltree.add]. We put it in the hash
     table to avoid allocating it at every [set]. *)
  ; recently_added           : bool ref
  ; growth_allowed           : bool
  ; hashable                 : 'k Hashable.t
  ; mutable mutation_allowed : bool (* Set during all iteration operations *)
  }

type 'a key = 'a

let sexp_of_key t = t.hashable.Hashable.sexp_of_t
let compare_key t = t.hashable.Hashable.compare

let ensure_mutation_allowed t =
  if not t.mutation_allowed then failwith "Hashtbl: mutation not allowed during iteration"
;;

let without_mutating t f =
  if t.mutation_allowed
  then
    begin
      t.mutation_allowed <- false;
      match f () with
      | x             -> t.mutation_allowed <- true; x
      | exception exn -> t.mutation_allowed <- true; raise exn
    end
  else
    f ()
;;

(** Internally use a maximum size that is a power of 2. Reverses the above to find the
    floor power of 2 below the system max array length *)
let max_table_length = Int.floor_pow2 Array.max_length ;;

let create ?(growth_allowed = true) ?(size = 128) ~hashable () =
  let size = Int.min (Int.max 1 size) max_table_length in
  let size = Int.ceil_pow2 size in
  { table            = Array.create ~len:size Avltree.empty
  ; length           = 0
  ; growth_allowed   = growth_allowed
  ; recently_added   = ref false
  ; hashable
  ; mutation_allowed = true
  }
;;

(** Supplemental hash. This may not be necessary, it is intended as a defense against poor
    hash functions, for which the power of 2 sized table will be especially sensitive.
    With some testing we may choose to add it, but this table is designed to be robust to
    collisions, and in most of my testing this degrades performance. *)
let _supplemental_hash h =
  let h = h lxor ((h lsr 20) lxor (h lsr 12)) in
  h lxor (h lsr 7) lxor (h lsr 4)
;;

let slot t key =
  let hash = t.hashable.Hashable.hash key in
  (* this is always non-negative because we do [land] with non-negative number *)
  hash land ((Array.length t.table) - 1)
;;

let add_worker t ~replace ~key ~data =
  let i = slot t key in
  let root = t.table.(i) in
  let added = t.recently_added in
  added := false;
  let new_root =
    (* The avl tree might replace the value [replace=true] or do nothing [replace=false]
       to the entry, in that case the table did not get bigger, so we should not
       increment length, we pass in the bool ref t.added so that it can tell us whether
       it added or replaced. We do it this way to avoid extra allocation. Since the bool
       is an immediate it does not go through the write barrier. *)
    Avltree.add ~replace root ~compare:(compare_key t) ~added ~key ~data
  in
  if !added then
    t.length <- t.length + 1;
  (* This little optimization saves a caml_modify when the tree
     hasn't been rebalanced. *)
  if not (phys_equal new_root root) then
    t.table.(i) <- new_root
;;

let maybe_resize_table t =
  let len = Array.length t.table in
  let should_grow = t.length > len in
  if should_grow && t.growth_allowed then begin
    let new_array_length = Int.min (len * 2) max_table_length in
    if new_array_length > len then begin
      let new_table =
        Array.create ~len:new_array_length Avltree.empty
      in
      let old_table = t.table in
      t.table <- new_table;
      t.length <- 0;
      let f ~key ~data = add_worker ~replace:true t ~key ~data in
      for i = 0 to Array.length old_table - 1 do
        Avltree.iter old_table.(i) ~f
      done
    end
  end
;;

let set t ~key ~data =
  ensure_mutation_allowed t;
  add_worker ~replace:true t ~key ~data;
  maybe_resize_table t
;;

let replace = set

let add t ~key ~data =
  ensure_mutation_allowed t;
  add_worker ~replace:false t ~key ~data;
  if !(t.recently_added) then begin
    maybe_resize_table t;
    `Ok
  end else
    `Duplicate
;;

let add_exn t ~key ~data =
  match add t ~key ~data with
  | `Ok -> ()
  | `Duplicate ->
    let sexp_of_key = sexp_of_key t in
    let error = Error.create "Hashtbl.add_exn got key already present" key sexp_of_key in
    Error.raise error
;;

let clear t =
  ensure_mutation_allowed t;
  for i = 0 to Array.length t.table - 1 do
    t.table.(i) <- Avltree.empty;
  done;
  t.length <- 0
;;

let find_and_call t key ~if_found ~if_not_found =
  (* with a good hash function these first two cases will be the overwhelming majority,
     and Avltree.find is recursive, so it can't be inlined, so doing this avoids a
     function call in most cases. *)
  match t.table.(slot t key) with
  | Avltree.Empty -> if_not_found key
  | Avltree.Leaf { key = k; value = v } ->
    if compare_key t k key = 0 then if_found v
    else if_not_found key
  | tree ->
    Avltree.find_and_call tree ~compare:(compare_key t) key ~if_found ~if_not_found
;;

let findi_and_call t key ~if_found ~if_not_found =
  (* with a good hash function these first two cases will be the overwhelming majority,
     and Avltree.find is recursive, so it can't be inlined, so doing this avoids a
     function call in most cases. *)
  match t.table.(slot t key) with
  | Avltree.Empty -> if_not_found key
  | Avltree.Leaf { key = k; value = v } ->
    if compare_key t k key = 0 then if_found ~key:k ~data:v
    else if_not_found key
  | tree ->
    Avltree.findi_and_call tree ~compare:(compare_key t) key ~if_found ~if_not_found
;;

let find =
  let if_found v = Some v in
  let if_not_found _ = None in
  fun t key ->
    find_and_call t key ~if_found ~if_not_found
;;

let mem t key =
  match t.table.(slot t key) with
  | Avltree.Empty -> false
  | Avltree.Leaf { key = k; value = _ } -> compare_key t k key = 0
  | tree -> Avltree.mem tree ~compare:(compare_key t) key
;;

let remove t key =
  ensure_mutation_allowed t;
  let i = slot t key in
  let root = t.table.(i) in
  let added_or_removed = t.recently_added in
  added_or_removed := false;
  let new_root =
    Avltree.remove root
      ~removed:added_or_removed ~compare:(compare_key t) key
  in
  if not (phys_equal root new_root) then
    t.table.(i) <- new_root;
  if !added_or_removed then
    t.length <- t.length - 1
;;

let length t = t.length

let is_empty t = length t = 0

let fold t ~init ~f =
  if length t = 0 then init
  else begin
    let n = Array.length t.table in
    let acc = ref init in
    let m = t.mutation_allowed in
    match
      t.mutation_allowed <- false;
      for i = 0 to n - 1 do
        match Array.unsafe_get t.table i with
        | Avltree.Empty -> ()
        | Avltree.Leaf { key; value = data } -> acc := f ~key ~data !acc
        | bucket -> acc := Avltree.fold bucket ~init:!acc ~f
      done
    with
    | () ->
      t.mutation_allowed <- m;
      !acc
    | exception exn ->
      t.mutation_allowed <- m;
      raise exn
  end
;;

let iteri t ~f =
  if t.length = 0 then ()
  else begin
    let n = Array.length t.table in
    let m = t.mutation_allowed in
    match
      t.mutation_allowed <- false;
      for i = 0 to n - 1 do
        match Array.unsafe_get t.table i with
        | Avltree.Empty -> ()
        | Avltree.Leaf { key; value = data } -> f ~key ~data
        | bucket -> Avltree.iter bucket ~f
      done
    with
    | () ->
      t.mutation_allowed <- m
    | exception exn ->
      t.mutation_allowed <- m;
      raise exn
  end
;;

let iter t ~f = iteri t ~f:(fun ~key:_ ~data -> f data)
let iter_keys t ~f = iteri t ~f:(fun ~key ~data:_ -> f key)

let invariant invariant_key invariant_data t =
  for i = 0 to Array.length t.table - 1 do
    Avltree.invariant t.table.(i) ~compare:(compare_key t)
  done;
  let real_len =
    fold t ~init:0 ~f:(fun ~key ~data i ->
      invariant_key key;
      invariant_data data;
      i + 1)
  in
  assert (real_len = t.length);
;;

let find_exn =
  let if_found v = v in
  let if_not_found _ = raise Caml.Not_found in
  fun t key ->
    find_and_call t key ~if_found ~if_not_found
;;

let existsi t ~f =
  with_return (fun r ->
    iteri t ~f:(fun ~key ~data -> if f ~key ~data then r.return true);
    false)
;;

let exists t ~f = existsi t ~f:(fun ~key:_ ~data -> f data)
;;

let for_alli t ~f = not (existsi t ~f:(fun ~key   ~data -> not (f ~key ~data)))
let for_all  t ~f = not (existsi t ~f:(fun ~key:_ ~data -> not (f       data)))

let counti t ~f =
  fold t ~init:0 ~f:(fun ~key ~data acc -> if f ~key ~data then acc+1 else acc)
let count t ~f =
  fold t ~init:0 ~f:(fun ~key:_ ~data acc -> if f data then acc+1 else acc)

let mapi t ~f =
  let new_t =
    create ~growth_allowed:t.growth_allowed
      ~hashable:t.hashable ~size:t.length ()
  in
  iteri t ~f:(fun ~key ~data -> replace new_t ~key ~data:(f ~key ~data));
  new_t

let map t ~f = mapi t ~f:(fun ~key:_ ~data -> f data)

let copy t = map t ~f:Fn.id

let filter_mapi t ~f =
  let new_t =
    create ~growth_allowed:t.growth_allowed
      ~hashable:t.hashable ~size:t.length ()
  in
  iteri t ~f:(fun ~key ~data ->
    match f ~key ~data with
    | Some new_data -> replace new_t ~key ~data:new_data
    | None -> ());
  new_t

let filter_map t ~f = filter_mapi t ~f:(fun ~key:_ ~data -> f data)

let filteri t ~f =
  filter_mapi t ~f:(fun ~key ~data -> if f ~key ~data then Some data else None)
;;

let filter t ~f = filteri t ~f:(fun ~key:_ ~data -> f data)
let filter_keys t ~f = filteri t ~f:(fun ~key ~data:_ -> f key)

let partition_mapi t ~f =
  let t0 =
    create ~growth_allowed:t.growth_allowed
      ~hashable:t.hashable ~size:t.length ()
  in
  let t1 =
    create ~growth_allowed:t.growth_allowed
      ~hashable:t.hashable ~size:t.length ()
  in
  iteri t ~f:(fun ~key ~data ->
    match f ~key ~data with
    | `Fst new_data -> replace t0 ~key ~data:new_data
    | `Snd new_data -> replace t1 ~key ~data:new_data);
  (t0, t1)
;;

let partition_map t ~f = partition_mapi t ~f:(fun ~key:_ ~data -> f data)

let partitioni_tf t ~f =
  partition_mapi t ~f:(fun ~key ~data -> if f ~key ~data then `Fst data else `Snd data)
;;

let partition_tf t ~f = partitioni_tf t ~f:(fun ~key:_ ~data -> f data)

let find_or_add t id ~default =
  match find t id with
  | Some x -> x
  | None ->
    let default = default () in
    replace t ~key:id ~data:default;
    default

let findi_or_add t id ~default =
  match find t id with
  | Some x -> x
  | None ->
    let default = default id in
    replace t ~key:id ~data:default;
    default

(* Some hashtbl implementations may be able to perform this more efficiently than two
   separate lookups *)
let find_and_remove t id =
  let result = find t id in
  if Option.is_some result then remove t id;
  result


let change t id ~f =
  match f (find t id) with
  | None -> remove t id
  | Some data -> replace t ~key:id ~data
;;

let update t id ~f =
  set t ~key:id ~data:(f (find t id))
;;

let incr_by ~remove_if_zero t key by =
  if remove_if_zero
  then
    change t key ~f:(fun opt ->
      match by + Option.value opt ~default:0 with
      | 0 -> None
      | n -> Some n)
  else
    update t key ~f:(function
      | None   -> by
      | Some i -> by + i)
;;

let incr ?(by = 1) ?(remove_if_zero = false) t key = incr_by ~remove_if_zero t key by
let decr ?(by = 1) ?(remove_if_zero = false) t key = incr_by ~remove_if_zero t key (-by)
;;

let add_multi t ~key ~data =
  update t key ~f:(function
    | None   -> [ data ]
    | Some l -> data :: l)
;;

let remove_multi t key =
  match find t key with
  | None -> ()
  | Some [] | Some [_] -> remove t key
  | Some (_ :: tl) -> replace t ~key ~data:tl

let find_multi t key =
  match find t key with
  | None -> []
  | Some l -> l

let create_mapped ?growth_allowed ?size ~hashable ~get_key ~get_data rows =
  let size = match size with Some s -> s | None -> List.length rows in
  let res = create ?growth_allowed ~hashable ~size () in
  let dupes = ref [] in
  List.iter rows ~f:(fun r ->
    let key = get_key r in
    let data = get_data r in
    if mem res key then
      dupes := key :: !dupes
    else
      replace res ~key ~data);
  match !dupes with
  | [] -> `Ok res
  | keys -> `Duplicate_keys (List.dedup_and_sort ~compare:hashable.Hashable.compare keys)
;;

(*
   {[
     let create_mapped_exn ?growth_allowed ?size ~hashable ~get_key ~get_data rows =
       let size = match size with Some s -> s | None -> List.length rows in
       let res = create ?growth_allowed ~size ~hashable () in
       List.iter rows ~f:(fun r ->
         let key = get_key r in
         let data = get_data r in
         if mem res key then
           let sexp_of_key = hashable.Hashable.sexp_of_t in
           failwiths "Hashtbl.create_mapped_exn: duplicate key" key <:sexp_of< key >>
         else
           replace res ~key ~data);
       res
     ;;
   ]} *)

let create_mapped_multi ?growth_allowed ?size ~hashable ~get_key ~get_data rows =
  let size = match size with Some s -> s | None -> List.length rows in
  let res = create ?growth_allowed ~size ~hashable () in
  List.iter rows ~f:(fun r ->
    let key = get_key r in
    let data = get_data r in
    add_multi res ~key ~data);
  res
;;

let of_alist ?growth_allowed ?size ~hashable lst =
  match create_mapped ?growth_allowed ?size ~hashable ~get_key:fst ~get_data:snd lst with
  | `Ok t -> `Ok t
  | `Duplicate_keys k -> `Duplicate_key (List.hd_exn k)
;;

let of_alist_report_all_dups ?growth_allowed ?size ~hashable lst =
  create_mapped ?growth_allowed ?size ~hashable ~get_key:fst ~get_data:snd lst
;;

let of_alist_or_error ?growth_allowed ?size ~hashable lst =
  match of_alist ?growth_allowed ?size ~hashable lst with
  | `Ok v -> Result.Ok v
  | `Duplicate_key key ->
    let sexp_of_key = hashable.Hashable.sexp_of_t in
    Or_error.error "Hashtbl.of_alist_exn: duplicate key" key sexp_of_key
;;

let of_alist_exn ?growth_allowed ?size ~hashable lst =
  match of_alist_or_error ?growth_allowed ?size ~hashable lst with
  | Result.Ok v -> v
  | Result.Error e -> Error.raise e
;;

let of_alist_multi ?growth_allowed ?size ~hashable lst =
  create_mapped_multi ?growth_allowed ?size ~hashable ~get_key:fst ~get_data:snd lst
;;

let to_alist t = fold ~f:(fun ~key ~data list -> (key, data) :: list) ~init:[] t

let sexp_of_t sexp_of_key sexp_of_data t =
  t
  |> to_alist
  |> List.sort ~compare:(fun (k1, _) (k2, _) -> t.hashable.compare k1 k2)
  |> sexp_of_list (sexp_of_pair sexp_of_key sexp_of_data)
;;

let t_of_sexp ~hashable k_of_sexp d_of_sexp sexp =
  let alist = list_of_sexp (pair_of_sexp k_of_sexp d_of_sexp) sexp in
  of_alist_exn ~hashable alist ~size:(List.length alist)
;;

let validate ~name f t = Validate.alist ~name f (to_alist t)

let keys t = fold t ~init:[] ~f:(fun ~key ~data:_ acc -> key :: acc)

let data t = fold ~f:(fun ~key:_ ~data list -> data::list) ~init:[] t

let add_to_groups groups ~get_key ~get_data ~combine ~rows =
  List.iter rows ~f:(fun row ->
    let key = get_key row in
    let data = get_data row in
    let data =
      match find groups key with
      | None -> data
      | Some old -> combine old data
    in
    replace groups ~key ~data)
;;

let group ?growth_allowed ?size ~hashable ~get_key ~get_data ~combine rows =
  let res = create ?growth_allowed ?size ~hashable () in
  add_to_groups res ~get_key ~get_data ~combine ~rows;
  res
;;

let create_with_key ?growth_allowed ?size ~hashable ~get_key rows =
  create_mapped ?growth_allowed ?size ~hashable ~get_key ~get_data:Fn.id rows
;;

let create_with_key_or_error ?growth_allowed ?size ~hashable ~get_key rows =
  match create_with_key ?growth_allowed ?size ~hashable ~get_key rows with
  | `Ok t -> Result.Ok t
  | `Duplicate_keys keys ->
    let sexp_of_key = hashable.Hashable.sexp_of_t in
    Or_error.error_s
      (Sexp.message "Hashtbl.create_with_key: duplicate keys"
         [ "keys", sexp_of_list sexp_of_key keys ])
;;

let create_with_key_exn ?growth_allowed ?size ~hashable ~get_key rows =
  Or_error.ok_exn (create_with_key_or_error ?growth_allowed ?size ~hashable ~get_key rows)
;;

let merge =
  let maybe_set t ~key ~f d =
    match f ~key d with
    | None -> ()
    | Some v ->
      set t ~key ~data:v
  in
  fun t_left t_right ~f ->
    if not (Hashable.equal t_left.hashable t_right.hashable)
    then invalid_arg "Hashtbl.merge: different 'hashable' values";
    let new_t =
      create ~growth_allowed:t_left.growth_allowed
        ~hashable:t_left.hashable ~size:t_left.length ()
    in
    without_mutating t_left (fun () ->
      without_mutating t_right (fun () ->
        iteri t_left ~f:(fun ~key ~data:left ->
          match find t_right key with
          | None ->
            maybe_set new_t ~key ~f (`Left left)
          | Some right ->
            maybe_set new_t ~key ~f (`Both (left, right))
        );
        iteri t_right ~f:(fun ~key ~data:right ->
          match find t_left key with
          | None ->
            maybe_set new_t ~key ~f (`Right right)
          | Some _ -> () (* already done above *)
        )));
    new_t
;;

type 'a merge_into_action = Remove | Set_to of 'a

let merge_into ~src ~dst ~f =
  iteri src ~f:(fun ~key ~data ->
    let dst_data = find dst key in
    let action = without_mutating dst (fun () -> f ~key data dst_data) in
    match action with
    | Remove   -> remove dst key
    | Set_to data ->
      match dst_data with
      | None -> replace dst ~key ~data
      | Some dst_data ->
        if not (phys_equal dst_data data)
        then replace dst ~key ~data)
;;

let filteri_inplace t ~f =
  let to_remove =
    fold t ~init:[] ~f:(fun ~key ~data ac ->
      if f ~key ~data then ac else key :: ac)
  in
  List.iter to_remove ~f:(fun key -> remove t key);
;;

let filter_inplace t ~f =
  filteri_inplace t ~f:(fun ~key:_ ~data -> f data)
;;

let filter_keys_inplace t ~f =
  filteri_inplace t ~f:(fun ~key ~data:_ -> f key)
;;

let filter_mapi_inplace t ~f =
  let map_results =
    fold t ~init:[] ~f:(fun ~key ~data ac -> (key, f ~key ~data) :: ac)
  in
  List.iter map_results ~f:(fun (key,result) ->
    match result with
    | None -> remove t key
    | Some data -> set t ~key ~data
  );
;;

let filter_map_inplace t ~f =
  filter_mapi_inplace t ~f:(fun ~key:_ ~data -> f data)

let mapi_inplace t ~f =
  ensure_mutation_allowed t;
  without_mutating t (fun () -> Array.iter t.table ~f:(Avltree.mapi_inplace ~f))

let map_inplace t ~f =
  mapi_inplace t ~f:(fun ~key:_ ~data -> f data)

let equal t t' equal =
  length t = length t' &&
  with_return (fun r ->
    without_mutating t' (fun () ->
      iteri t ~f:(fun ~key ~data ->
        match find t' key with
        | None       -> r.return false
        | Some data' ->
          if not (equal data data')
          then r.return false));
    true)
;;

let similar = equal

module Accessors = struct

  type nonrec 'a merge_into_action = 'a merge_into_action = Remove | Set_to of 'a

  let invariant           = invariant
  let clear               = clear
  let copy                = copy
  let remove              = remove
  let set                 = set
  let add                 = add
  let add_exn             = add_exn
  let change              = change
  let update              = update
  let add_multi           = add_multi
  let remove_multi        = remove_multi
  let find_multi          = find_multi
  let mem                 = mem
  let iter_keys           = iter_keys
  let iter                = iter
  let iteri               = iteri
  let exists              = exists
  let existsi             = existsi
  let for_all             = for_all
  let for_alli            = for_alli
  let count               = count
  let counti              = counti
  let fold                = fold
  let length              = length
  let is_empty            = is_empty
  let map                 = map
  let mapi                = mapi
  let filter_map          = filter_map
  let filter_mapi         = filter_mapi
  let filter_keys         = filter_keys
  let filter              = filter
  let filteri             = filteri
  let partition_map       = partition_map
  let partition_mapi      = partition_mapi
  let partition_tf        = partition_tf
  let partitioni_tf       = partitioni_tf
  let find_or_add         = find_or_add
  let findi_or_add        = findi_or_add
  let find                = find
  let find_exn            = find_exn
  let find_and_call       = find_and_call
  let findi_and_call      = findi_and_call
  let find_and_remove     = find_and_remove
  let to_alist            = to_alist
  let validate            = validate
  let merge               = merge
  let merge_into          = merge_into
  let keys                = keys
  let data                = data
  let filter_keys_inplace = filter_keys_inplace
  let filter_inplace      = filter_inplace
  let filteri_inplace     = filteri_inplace
  let map_inplace         = map_inplace
  let mapi_inplace        = mapi_inplace
  let filter_map_inplace  = filter_map_inplace
  let filter_mapi_inplace = filter_mapi_inplace
  let equal               = equal
  let similar             = similar
  let incr                = incr
  let decr                = decr
  let sexp_of_key         = sexp_of_key
end

module Creators (Key : sig
    type 'a t

    val hashable : 'a t Hashable.t
  end) : sig

  type ('a, 'b) t_ = ('a Key.t, 'b) t

  val t_of_sexp : (Sexp.t -> 'a Key.t) -> (Sexp.t -> 'b) -> Sexp.t -> ('a, 'b) t_

  include Creators_generic
    with type ('a, 'b) t := ('a, 'b) t_
    with type 'a key := 'a Key.t
    with type ('key, 'data, 'a) create_options :=
      ('key, 'data, 'a) create_options_without_first_class_module

end = struct

  let hashable = Key.hashable

  type ('a, 'b) t_ = ('a Key.t, 'b) t

  let create ?growth_allowed ?size () = create ?growth_allowed ?size ~hashable ()

  let of_alist ?growth_allowed ?size l =
    of_alist ?growth_allowed ~hashable ?size l
  ;;

  let of_alist_report_all_dups ?growth_allowed ?size l =
    of_alist_report_all_dups ?growth_allowed ~hashable ?size l
  ;;

  let of_alist_or_error ?growth_allowed ?size l =
    of_alist_or_error ?growth_allowed ~hashable ?size l
  ;;

  let of_alist_exn ?growth_allowed ?size l =
    of_alist_exn ?growth_allowed ~hashable ?size l
  ;;

  let t_of_sexp k_of_sexp d_of_sexp sexp =
    t_of_sexp ~hashable k_of_sexp d_of_sexp sexp
  ;;

  let of_alist_multi ?growth_allowed ?size l =
    of_alist_multi ?growth_allowed ~hashable ?size l
  ;;

  let create_mapped ?growth_allowed ?size ~get_key ~get_data l =
    create_mapped ?growth_allowed ~hashable ?size ~get_key ~get_data l
  ;;

  let create_with_key ?growth_allowed ?size ~get_key l =
    create_with_key ?growth_allowed ~hashable ?size ~get_key l
  ;;

  let create_with_key_or_error ?growth_allowed ?size ~get_key l =
    create_with_key_or_error ?growth_allowed ~hashable ?size ~get_key l
  ;;

  let create_with_key_exn ?growth_allowed ?size ~get_key l =
    create_with_key_exn ?growth_allowed ~hashable ?size ~get_key l
  ;;

  let group ?growth_allowed ?size ~get_key ~get_data ~combine l =
    group ?growth_allowed ~hashable ?size ~get_key ~get_data ~combine l
  ;;
end

module Poly = struct

  type nonrec ('a, 'b) t = ('a, 'b) t

  type 'a key = 'a

  let hashable = Hashable.poly

  include Creators (struct
      type 'a t = 'a
      let hashable = hashable
    end)

  include Accessors

  let sexp_of_t = sexp_of_t
end

module Private = struct
  module type Creators_generic = Creators_generic
  module type Hashable = Hashable.Hashable

  type nonrec ('key, 'data, 'z) create_options_without_first_class_module =
    ('key, 'data, 'z) create_options_without_first_class_module

  let hashable t = t.hashable
end

let create ?growth_allowed ?size m =
  create ~hashable:(Hashable.of_key m) ?growth_allowed ?size ()
let of_alist ?growth_allowed ?size m l =
  of_alist ~hashable:(Hashable.of_key m) ?growth_allowed ?size l
let of_alist_report_all_dups ?growth_allowed ?size m l =
  of_alist_report_all_dups ~hashable:(Hashable.of_key m) ?growth_allowed ?size l
let of_alist_or_error ?growth_allowed ?size m l =
  of_alist_or_error ~hashable:(Hashable.of_key m) ?growth_allowed ?size l
let of_alist_exn ?growth_allowed ?size m l =
  of_alist_exn ~hashable:(Hashable.of_key m) ?growth_allowed ?size l
let of_alist_multi ?growth_allowed ?size m l =
  of_alist_multi ~hashable:(Hashable.of_key m) ?growth_allowed ?size l
let create_mapped ?growth_allowed ?size m ~get_key ~get_data l =
  create_mapped ~hashable:(Hashable.of_key m) ?growth_allowed ?size ~get_key ~get_data l
let create_with_key ?growth_allowed ?size m ~get_key l =
  create_with_key ~hashable:(Hashable.of_key m) ?growth_allowed ?size ~get_key l
let create_with_key_or_error ?growth_allowed ?size m ~get_key l =
  create_with_key_or_error ~hashable:(Hashable.of_key m) ?growth_allowed ?size ~get_key l
let create_with_key_exn ?growth_allowed ?size m ~get_key l =
  create_with_key_exn ~hashable:(Hashable.of_key m) ?growth_allowed ?size ~get_key l
let group ?growth_allowed ?size m ~get_key ~get_data ~combine l =
  group ~hashable:(Hashable.of_key m) ?growth_allowed ?size ~get_key ~get_data ~combine l

let hashable_s t = Hashable.to_key t.hashable

module M (K : T.T) = struct
  type nonrec 'v t = (K.t, 'v) t
end
module type Sexp_of_m = sig type t [@@deriving_inline sexp_of]
  include
  sig [@@@ocaml.warning "-32"] val sexp_of_t : t -> Ppx_sexp_conv_lib.Sexp.t
  end[@@ocaml.doc "@inline"]
  [@@@end] end
module type M_of_sexp = sig
  type t [@@deriving_inline of_sexp]
  include
  sig [@@@ocaml.warning "-32"] val t_of_sexp : Ppx_sexp_conv_lib.Sexp.t -> t
  end[@@ocaml.doc "@inline"]
  [@@@end] include Key with type t := t
end

let sexp_of_m__t (type k) (module K : Sexp_of_m with type t = k) sexp_of_v t =
  sexp_of_t K.sexp_of_t sexp_of_v t

let m__t_of_sexp (type k) (module K : M_of_sexp with type t = k) v_of_sexp sexp =
  t_of_sexp ~hashable:(Hashable.of_key (module K)) K.t_of_sexp v_of_sexp sexp

(* typechecking this code is a compile-time test that [Creators] is a specialization of
   [Creators_generic].  *)
module Check : sig end = struct
  module Make_creators_check (Type : T.T2) (Key : T.T1) (Options : T.T3)
      (M : Creators_generic
       with type ('a, 'b) t := ('a, 'b) Type.t
       with type 'a key := 'a Key.t
       with type ('a, 'b, 'z) create_options := ('a, 'b, 'z) Options.t)
  = struct end

  module Check_creators_is_specialization_of_creators_generic (M : Creators) =
    Make_creators_check
      (struct type ('a, 'b) t = ('a, 'b) M.t end)
      (struct type 'a t = 'a end)
      (struct type ('a, 'b, 'z) t = ('a, 'b, 'z) create_options end)
      (struct
        include M

        let create ?growth_allowed ?size m () =
          create ?growth_allowed ?size m
      end)
end