sig
  type name = string
  type qname = Type.name list
  module NameMap :
    sig
      type key = string
      type +'a t
      val empty : 'a t
      val is_empty : 'a t -> bool
      val mem : key -> 'a t -> bool
      val add : key -> '-> 'a t -> 'a t
      val singleton : key -> '-> '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 union : (key -> '-> '-> 'a option) -> 'a t -> 'a t -> 'a t
      val compare : ('-> '-> int) -> 'a t -> 'a t -> int
      val equal : ('-> '-> bool) -> 'a t -> 'a t -> bool
      val iter : (key -> '-> unit) -> 'a t -> unit
      val fold : (key -> '-> '-> 'b) -> 'a t -> '-> 'b
      val for_all : (key -> '-> bool) -> 'a t -> bool
      val exists : (key -> '-> bool) -> 'a t -> bool
      val filter : (key -> '-> bool) -> 'a t -> 'a t
      val partition : (key -> '-> 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 min_binding_opt : 'a t -> (key * 'a) option
      val max_binding : 'a t -> key * 'a
      val max_binding_opt : 'a t -> (key * 'a) option
      val choose : 'a t -> key * 'a
      val choose_opt : 'a t -> (key * 'a) option
      val split : key -> 'a t -> 'a t * 'a option * 'a t
      val find : key -> 'a t -> 'a
      val find_opt : key -> 'a t -> 'a option
      val find_first : (key -> bool) -> 'a t -> key * 'a
      val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
      val find_last : (key -> bool) -> 'a t -> key * 'a
      val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
      val map : ('-> 'b) -> 'a t -> 'b t
      val mapi : (key -> '-> 'b) -> 'a t -> 'b t
      exception Not_found of key
      val fromList : (key * 'a) list -> 'a t
      val union_disjoint : 'a t list -> 'a t
      val union_disjoint2 : 'a t -> 'a t -> 'a t
    end
  module NameSet :
    sig
      type elt = string
      type t
      val empty : t
      val is_empty : t -> bool
      val mem : elt -> t -> bool
      val add : elt -> t -> t
      val singleton : elt -> t
      val remove : elt -> t -> t
      val union : t -> t -> t
      val inter : t -> t -> t
      val diff : t -> t -> t
      val compare : t -> t -> int
      val equal : t -> t -> bool
      val subset : t -> t -> bool
      val iter : (elt -> unit) -> t -> unit
      val map : (elt -> elt) -> t -> t
      val fold : (elt -> '-> 'a) -> t -> '-> 'a
      val for_all : (elt -> bool) -> t -> bool
      val exists : (elt -> bool) -> t -> bool
      val filter : (elt -> bool) -> t -> t
      val partition : (elt -> bool) -> t -> t * t
      val cardinal : t -> int
      val elements : t -> elt list
      val min_elt : t -> elt
      val min_elt_opt : t -> elt option
      val max_elt : t -> elt
      val max_elt_opt : t -> elt option
      val choose : t -> elt
      val choose_opt : t -> elt option
      val split : elt -> t -> t * bool * t
      val find : elt -> t -> elt
      val find_opt : elt -> t -> elt option
      val find_first : (elt -> bool) -> t -> elt
      val find_first_opt : (elt -> bool) -> t -> elt option
      val find_last : (elt -> bool) -> t -> elt
      val find_last_opt : (elt -> bool) -> t -> elt option
      val of_list : elt list -> t
      val toList : t -> elt list
      val fromList : elt list -> t
    end
  type param = Type.name * [ `Minus | `Plus ] option
  type decl =
      Type.name * Type.param list * Type.rhs * Type.constraint_ list * bool
  and rhs =
      [ `Expr of Type.expr
      | `Fresh of Type.expr option * Type.repr * [ `Private | `Public ]
      | `Nothing
      | `Variant of Type.variant * [ `Private | `Public ] ]
  and repr =
      Sum of Type.summand list
    | GSum of Type.name * Type.gsummand list
    | Record of Type.field list
  and field = Type.name * Type.poly_expr * [ `Immutable | `Mutable ]
  and summand = Type.name * Type.expr list
  and gsummand = Type.name * Type.expr list * Type.expr list
  and constraint_ = Type.expr * Type.expr
  and expr =
      [ `Class of [ `NYI ]
      | `Constr of Type.qname * Type.expr list
      | `Function of Type.expr * Type.expr
      | `GParam of Type.param * Type.expr
      | `Label of
          [ `NonOptional | `Optional ] * Type.name * Type.expr * Type.expr
      | `Object of [ `NYI ]
      | `Param of Type.param
      | `Tuple of Type.expr list ]
  and poly_expr = Type.param list * Type.expr
  and variant = [ `Eq | `Gt | `Lt ] * Type.tagspec list
  and tagspec = Tag of Type.name * Type.expr list | Extends of Type.expr
  module ParamSet :
    sig
      type elt = param
      type t
      val empty : t
      val is_empty : t -> bool
      val mem : elt -> t -> bool
      val add : elt -> t -> t
      val singleton : elt -> t
      val remove : elt -> t -> t
      val union : t -> t -> t
      val inter : t -> t -> t
      val diff : t -> t -> t
      val compare : t -> t -> int
      val equal : t -> t -> bool
      val subset : t -> t -> bool
      val iter : (elt -> unit) -> t -> unit
      val map : (elt -> elt) -> t -> t
      val fold : (elt -> '-> 'a) -> t -> '-> 'a
      val for_all : (elt -> bool) -> t -> bool
      val exists : (elt -> bool) -> t -> bool
      val filter : (elt -> bool) -> t -> t
      val partition : (elt -> bool) -> t -> t * t
      val cardinal : t -> int
      val elements : t -> elt list
      val min_elt : t -> elt
      val min_elt_opt : t -> elt option
      val max_elt : t -> elt
      val max_elt_opt : t -> elt option
      val choose : t -> elt
      val choose_opt : t -> elt option
      val split : elt -> t -> t * bool * t
      val find : elt -> t -> elt
      val find_opt : elt -> t -> elt option
      val find_first : (elt -> bool) -> t -> elt
      val find_first_opt : (elt -> bool) -> t -> elt option
      val find_last : (elt -> bool) -> t -> elt
      val find_last_opt : (elt -> bool) -> t -> elt option
      val of_list : elt list -> t
      val toList : t -> elt list
      val fromList : elt list -> t
    end
  module ParamMap :
    sig
      type key = param
      type +'a t
      val empty : 'a t
      val is_empty : 'a t -> bool
      val mem : key -> 'a t -> bool
      val add : key -> '-> 'a t -> 'a t
      val singleton : key -> '-> '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 union : (key -> '-> '-> 'a option) -> 'a t -> 'a t -> 'a t
      val compare : ('-> '-> int) -> 'a t -> 'a t -> int
      val equal : ('-> '-> bool) -> 'a t -> 'a t -> bool
      val iter : (key -> '-> unit) -> 'a t -> unit
      val fold : (key -> '-> '-> 'b) -> 'a t -> '-> 'b
      val for_all : (key -> '-> bool) -> 'a t -> bool
      val exists : (key -> '-> bool) -> 'a t -> bool
      val filter : (key -> '-> bool) -> 'a t -> 'a t
      val partition : (key -> '-> 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 min_binding_opt : 'a t -> (key * 'a) option
      val max_binding : 'a t -> key * 'a
      val max_binding_opt : 'a t -> (key * 'a) option
      val choose : 'a t -> key * 'a
      val choose_opt : 'a t -> (key * 'a) option
      val split : key -> 'a t -> 'a t * 'a option * 'a t
      val find : key -> 'a t -> 'a
      val find_opt : key -> 'a t -> 'a option
      val find_first : (key -> bool) -> 'a t -> key * 'a
      val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
      val find_last : (key -> bool) -> 'a t -> key * 'a
      val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
      val map : ('-> 'b) -> 'a t -> 'b t
      val mapi : (key -> '-> 'b) -> 'a t -> 'b t
      exception Not_found of key
      val fromList : (key * 'a) list -> 'a t
      val union_disjoint : 'a t list -> 'a t
      val union_disjoint2 : 'a t -> 'a t -> 'a t
    end
  module ExprSet :
    sig
      type elt = expr
      type t
      val empty : t
      val is_empty : t -> bool
      val mem : elt -> t -> bool
      val add : elt -> t -> t
      val singleton : elt -> t
      val remove : elt -> t -> t
      val union : t -> t -> t
      val inter : t -> t -> t
      val diff : t -> t -> t
      val compare : t -> t -> int
      val equal : t -> t -> bool
      val subset : t -> t -> bool
      val iter : (elt -> unit) -> t -> unit
      val map : (elt -> elt) -> t -> t
      val fold : (elt -> '-> 'a) -> t -> '-> 'a
      val for_all : (elt -> bool) -> t -> bool
      val exists : (elt -> bool) -> t -> bool
      val filter : (elt -> bool) -> t -> t
      val partition : (elt -> bool) -> t -> t * t
      val cardinal : t -> int
      val elements : t -> elt list
      val min_elt : t -> elt
      val min_elt_opt : t -> elt option
      val max_elt : t -> elt
      val max_elt_opt : t -> elt option
      val choose : t -> elt
      val choose_opt : t -> elt option
      val split : elt -> t -> t * bool * t
      val find : elt -> t -> elt
      val find_opt : elt -> t -> elt option
      val find_first : (elt -> bool) -> t -> elt
      val find_first_opt : (elt -> bool) -> t -> elt option
      val find_last : (elt -> bool) -> t -> elt
      val find_last_opt : (elt -> bool) -> t -> elt option
      val of_list : elt list -> t
      val toList : t -> elt list
      val fromList : elt list -> t
    end
  module ExprMap :
    sig
      type key = expr
      type +'a t
      val empty : 'a t
      val is_empty : 'a t -> bool
      val mem : key -> 'a t -> bool
      val add : key -> '-> 'a t -> 'a t
      val singleton : key -> '-> '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 union : (key -> '-> '-> 'a option) -> 'a t -> 'a t -> 'a t
      val compare : ('-> '-> int) -> 'a t -> 'a t -> int
      val equal : ('-> '-> bool) -> 'a t -> 'a t -> bool
      val iter : (key -> '-> unit) -> 'a t -> unit
      val fold : (key -> '-> '-> 'b) -> 'a t -> '-> 'b
      val for_all : (key -> '-> bool) -> 'a t -> bool
      val exists : (key -> '-> bool) -> 'a t -> bool
      val filter : (key -> '-> bool) -> 'a t -> 'a t
      val partition : (key -> '-> 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 min_binding_opt : 'a t -> (key * 'a) option
      val max_binding : 'a t -> key * 'a
      val max_binding_opt : 'a t -> (key * 'a) option
      val choose : 'a t -> key * 'a
      val choose_opt : 'a t -> (key * 'a) option
      val split : key -> 'a t -> 'a t * 'a option * 'a t
      val find : key -> 'a t -> 'a
      val find_opt : key -> 'a t -> 'a option
      val find_first : (key -> bool) -> 'a t -> key * 'a
      val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
      val find_last : (key -> bool) -> 'a t -> key * 'a
      val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
      val map : ('-> 'b) -> 'a t -> 'b t
      val mapi : (key -> '-> 'b) -> 'a t -> 'b t
      exception Not_found of key
      val fromList : (key * 'a) list -> 'a t
      val union_disjoint : 'a t list -> 'a t
      val union_disjoint2 : 'a t -> 'a t -> 'a t
    end
  module ESet :
    sig
      type elt = name * expr list
      type t
      val empty : t
      val is_empty : t -> bool
      val mem : elt -> t -> bool
      val add : elt -> t -> t
      val singleton : elt -> t
      val remove : elt -> t -> t
      val union : t -> t -> t
      val inter : t -> t -> t
      val diff : t -> t -> t
      val compare : t -> t -> int
      val equal : t -> t -> bool
      val subset : t -> t -> bool
      val iter : (elt -> unit) -> t -> unit
      val map : (elt -> elt) -> t -> t
      val fold : (elt -> '-> 'a) -> t -> '-> 'a
      val for_all : (elt -> bool) -> t -> bool
      val exists : (elt -> bool) -> t -> bool
      val filter : (elt -> bool) -> t -> t
      val partition : (elt -> bool) -> t -> t * t
      val cardinal : t -> int
      val elements : t -> elt list
      val min_elt : t -> elt
      val min_elt_opt : t -> elt option
      val max_elt : t -> elt
      val max_elt_opt : t -> elt option
      val choose : t -> elt
      val choose_opt : t -> elt option
      val split : elt -> t -> t * bool * t
      val find : elt -> t -> elt
      val find_opt : elt -> t -> elt option
      val find_first : (elt -> bool) -> t -> elt
      val find_first_opt : (elt -> bool) -> t -> elt option
      val find_last : (elt -> bool) -> t -> elt
      val find_last_opt : (elt -> bool) -> t -> elt option
      val of_list : elt list -> t
      val toList : t -> elt list
      val fromList : elt list -> t
    end
  module EMap :
    sig
      type key = name * expr list
      type +'a t
      val empty : 'a t
      val is_empty : 'a t -> bool
      val mem : key -> 'a t -> bool
      val add : key -> '-> 'a t -> 'a t
      val singleton : key -> '-> '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 union : (key -> '-> '-> 'a option) -> 'a t -> 'a t -> 'a t
      val compare : ('-> '-> int) -> 'a t -> 'a t -> int
      val equal : ('-> '-> bool) -> 'a t -> 'a t -> bool
      val iter : (key -> '-> unit) -> 'a t -> unit
      val fold : (key -> '-> '-> 'b) -> 'a t -> '-> 'b
      val for_all : (key -> '-> bool) -> 'a t -> bool
      val exists : (key -> '-> bool) -> 'a t -> bool
      val filter : (key -> '-> bool) -> 'a t -> 'a t
      val partition : (key -> '-> 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 min_binding_opt : 'a t -> (key * 'a) option
      val max_binding : 'a t -> key * 'a
      val max_binding_opt : 'a t -> (key * 'a) option
      val choose : 'a t -> key * 'a
      val choose_opt : 'a t -> (key * 'a) option
      val split : key -> 'a t -> 'a t * 'a option * 'a t
      val find : key -> 'a t -> 'a
      val find_opt : key -> 'a t -> 'a option
      val find_first : (key -> bool) -> 'a t -> key * 'a
      val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
      val find_last : (key -> bool) -> 'a t -> key * 'a
      val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
      val map : ('-> 'b) -> 'a t -> 'b t
      val mapi : (key -> '-> 'b) -> 'a t -> 'b t
      exception Not_found of key
      val fromList : (key * 'a) list -> 'a t
      val union_disjoint : 'a t list -> 'a t
      val union_disjoint2 : 'a t -> 'a t -> 'a t
    end
  val free_tvars : Type.expr -> Type.ParamSet.t
  val contains_tvars : Type.expr -> bool
  val contains_tvars_decl : Type.decl -> bool
  type subst = Type.expr Type.NameMap.t
  val build_subst : (Type.name * Type.expr) list -> Type.subst
  val substitute_decl : Type.subst -> Type.decl -> Type.decl
  val substitute_expr : Type.subst -> Type.expr -> Type.expr
  val substitute_rhs : Type.subst -> Type.rhs -> Type.rhs
  val substitute_constraint :
    Type.subst -> Type.constraint_ -> Type.constraint_
  val rename_rhs : Type.name Type.NameMap.t -> Type.rhs -> Type.rhs
  val rename_constraint :
    Type.name Type.NameMap.t -> Type.constraint_ -> Type.constraint_
  class virtual ['a] fold :
    object
      method constraint_ : Type.constraint_ -> 'a
      method virtual crush : 'a list -> 'a
      method decl : Type.decl -> 'a
      method expr : Type.expr -> 'a
      method field : Type.field -> 'a
      method gsummand : Type.gsummand -> 'a
      method poly_expr : Type.poly_expr -> 'a
      method repr : Type.repr -> 'a
      method rhs : Type.rhs -> 'a
      method summand : Type.summand -> 'a
      method tagspec : Type.tagspec -> 'a
      method variant : Type.variant -> 'a
    end
  class transform :
    object
      method constraint_ : Type.constraint_ -> Type.constraint_
      method decl : Type.decl -> Type.decl
      method expr : Type.expr -> Type.expr
      method field : Type.field -> Type.field
      method gsummand : Type.gsummand -> Type.gsummand
      method poly_expr : Type.poly_expr -> Type.poly_expr
      method repr : Type.repr -> Type.repr
      method rhs : Type.rhs -> Type.rhs
      method summand : Type.summand -> Type.summand
      method tagspec : Type.tagspec -> Type.tagspec
      method variant : Type.variant -> Type.variant
    end
  module Translate :
    sig
      val param :
        Camlp4.PreCast.Ast.ctyp -> string * [> `Minus | `Plus ] option
      val params :
        Camlp4.PreCast.Ast.ctyp list ->
        (string * [> `Minus | `Plus ] option) list
      val split_and :
        Camlp4.PreCast.Ast.ctyp ->
        (Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp,
         Camlp4.PreCast.Ast.ctyp)
        Utils.either
      val split_comma :
        Camlp4.PreCast.Ast.ctyp ->
        (Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp,
         Camlp4.PreCast.Ast.ctyp)
        Utils.either
      val split_semi :
        Camlp4.PreCast.Ast.ctyp ->
        (Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp,
         Camlp4.PreCast.Ast.ctyp)
        Utils.either
      val split_or :
        Camlp4.PreCast.Ast.ctyp ->
        (Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp,
         Camlp4.PreCast.Ast.ctyp)
        Utils.either
      val split_amp :
        Camlp4.PreCast.Ast.ctyp ->
        (Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp,
         Camlp4.PreCast.Ast.ctyp)
        Utils.either
      val split_ofamp :
        Camlp4.PreCast.Ast.ctyp ->
        (Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp,
         Camlp4.PreCast.Ast.ctyp)
        Utils.either
      val split_star :
        Camlp4.PreCast.Ast.ctyp ->
        (Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp,
         Camlp4.PreCast.Ast.ctyp)
        Utils.either
      val list :
        (Camlp4.PreCast.Ast.ctyp -> 'a) ->
        (Camlp4.PreCast.Ast.ctyp ->
         (Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp,
          Camlp4.PreCast.Ast.ctyp)
         Utils.either) ->
        Camlp4.PreCast.Ast.ctyp -> 'a list
      val ident : Camlp4.PreCast.Ast.ident -> Type.name
      val qident : Camlp4.PreCast.Ast.ident -> Type.qname
      type vmap = (Type.name * Type.variant * Type.name option) list
      val fresh_name : unit -> string
      val set_name_prefix : Type.name -> unit
      module WithParams :
        functor (P : sig val params : Type.param list end->
          sig
            val params : Type.param list
            val apply_t :
              '-> [> `Constr of 'a list * [> `Param of Type.param ] list ]
            val expr :
              Camlp4.PreCast.Ast.ctyp -> Type.expr * Type.Translate.vmap
            val tagspec :
              Camlp4.PreCast.Ast.ctyp -> Type.tagspec * Type.Translate.vmap
            val application :
              Camlp4.PreCast.Ast.ctyp ->
              (Type.qname * Type.expr list) * Type.Translate.vmap
            val variant :
              Camlp4.PreCast.Ast.ctyp ->
              ?alias:Type.name ->
              [ `Eq | `Gt | `Lt ] -> Type.expr * Type.Translate.vmap
            val polyexpr :
              Camlp4.PreCast.Ast.ctyp -> Type.poly_expr * Type.Translate.vmap
            val field :
              Camlp4.PreCast.Ast.ctyp -> Type.field * Type.Translate.vmap
            val summand :
              Camlp4.PreCast.Ast.ctyp -> Type.summand * Type.Translate.vmap
            val repr :
              Camlp4.PreCast.Ast.ctyp ->
              Type.repr * (Type.name * Type.variant * Type.name option) list
            val toplevel :
              Camlp4.PreCast.Ast.ctyp -> Type.rhs * Type.Translate.vmap
            val constraints :
              (Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp) list ->
              Type.constraint_ list * Type.Translate.vmap
            val declify :
              (Type.name * Type.variant * Type.name option) list ->
              (Type.decl * (Type.name * Type.expr) option) list
          end
      type alias_map = Type.expr Type.NameMap.t
      val build_alias_map :
        (Type.NameMap.key * Type.expr) option list ->
        Type.Translate.alias_map
      val split : Camlp4.PreCast.Ast.ctyp -> Camlp4.PreCast.Ast.ctyp list
      val decl :
        Camlp4.PreCast.Ast.ctyp -> Type.decl list * Type.Translate.alias_map
      val substitute_aliases :
        Type.Translate.alias_map -> Type.decl -> Type.decl
      val decls : Camlp4.PreCast.Ast.ctyp -> Type.decl list
    end
  module type Untranslate =
    sig
      val param :
        string * [< `Minus | `Plus ] option -> Camlp4.PreCast.Ast.ctyp
      val qname : string list -> Camlp4.PreCast.Ast.ident
      val qName : string list -> Camlp4.PreCast.Ast.ident
      val expr : Type.expr -> Camlp4.PreCast.Ast.ctyp
      val poly : Type.param list * Type.expr -> Camlp4.PreCast.Ast.ctyp
      val rhs : Type.rhs -> Camlp4.PreCast.Ast.ctyp
      val tagspec : Type.tagspec -> Camlp4.PreCast.Ast.ctyp
      val summand : Type.summand -> Camlp4.PreCast.Ast.ctyp
      val field : Type.field -> Camlp4.PreCast.Ast.ctyp
      val repr : Type.repr -> Camlp4.PreCast.Ast.ctyp
      val constraint_ :
        Type.expr * Type.expr ->
        Camlp4.PreCast.Ast.ctyp * Camlp4.PreCast.Ast.ctyp
      val decl : Type.decl -> Camlp4.PreCast.Ast.ctyp
      val sigdecl : Type.decl -> Camlp4.PreCast.Ast.ctyp list
    end
  module Untranslate :
    functor (C : sig val _loc : Camlp4.PreCast.Ast.Loc.t end-> Untranslate
  val print_expr : Type.expr -> string
  val print_rhs : Type.rhs -> string
end