var.ml

module V = struct


  type kind = Source | Internal

  type t = { name : Ident.U.t ;
	     id : int ;
	     kind : kind }

  let print_kind ppf k = Format.fprintf ppf "%s"
    (match k with Source -> "Source" | Internal -> "Internal")

  let compare_kind k1 k2 = if k1 == k2 then 0 else if k1 < k2 then -1 else 1

  let dump ppf t =
    Format.fprintf ppf "%a(%d_%a)" Ident.U.print t.name t.id print_kind t.kind

  let compare x y =
    let c = compare_kind x.kind y.kind in
    if c == 0 then
      let c = Pervasives.compare x.id y.id in
      if c == 0 then Ident.U.compare x.name y.name
      else c
    else c

  let equal x y =
    x == y || (x.kind == y.kind && x.id == y.id && Ident.U.equal x.name y.name)

  let hash x = Hashtbl.hash (x.id,x.name,x.kind)

  let check x = assert (x.id >= 0)

  let refresh v =
    (* according to Alain, a thread safe way to generate a unique ID *)
    { v with id = Oo.id (object end) }

  let mk ?(internal=false) id = { name = Ident.U.mk id;
				  id = 0;
				  kind = if internal then Internal else Source;
				}
  let is_internal x = x.kind == Internal

  let ident x = Ident.U.get_str x.name
  let print ppf x = Format.fprintf ppf "'%a" Ident.U.print x.name
end



module Set = struct
  include SortedList.Make(V)
  let dump ppf s = Utils.pp_list ~sep:";" ~delim:("{","}") V.dump ppf (get s)
  let print ppf s = Utils.pp_list ~sep:";" ~delim:("{","}") V.print ppf (get s)
end


include V
let gen set =
  let idx = ref 0 in
  let rec freshvar () =
    let rec pretty i acc =
      let ni,nm = i/26, i mod 26 in
      let acc = acc ^
        (String.make 1 (Char.chr (Char.code 'a' + nm)))
      in
      if ni == 0 then acc else pretty ni acc
    in
    let x = mk (pretty !idx "") in
    if Set.mem set x then
      (* if the name is taken by a variable in delta, restart *)
      (incr idx; freshvar ())
    else x
  in
  freshvar ()

type 'a var_or_atom = [ `Atm of 'a | `Var of t ]

module Make (X : Custom.T) = struct
  type t = X.t var_or_atom
  let hash = function `Atm t -> 17 + 17 * X.hash t | `Var x -> 997 + 17 * V.hash x

  let check = function `Atm t -> X.check t | `Var _ -> ()

  let compare t1 t2 =
    match t1,t2 with
    |`Var x, `Var y -> compare x 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 -> V.dump ppf x
end