type t = String.t
type var = [ `Var of t ]
type 'a pairvar = [ `Atm of 'a | var ]

let compare (x : var) (y : var) = Pervasives.compare x y
let hash (v : var) = Hashtbl.hash v

module Make (X : Custom.T) = struct
  type t = X.t pairvar
  let hash = function `Atm t -> X.hash t | `Var s -> hash (`Var s)
  let check = function `Atm t -> X.check t | `Var _ -> ()
  let compare t1 t2 =
    match t1,t2 with
    |`Var x, `Var y -> compare (`Var x) (`Var y)
    |`Atm x, `Atm y -> X.compare x y
    |`Var _, `Atm _ -> -1
    |`Atm _, `Var _ -> 1

  let equal t1 t2 = (compare t1 t2) = 0

  let dump ppf = function
    |`Atm x -> X.dump ppf x
    |`Var x -> Format.fprintf ppf "`$%s" x
end

let fresh : unit -> var =
  let counter = ref 0 in
  fun _ ->
    let v = `Var (Printf.sprintf "_fresh_%d" !counter) in
    incr counter;
    v

module Set = Set.Make(
  struct 
    type t = var
    let compare = Pervasives.compare
  end)