(* Small things *)

let ord_couple (a, b) = if a < b then a, b else b, a

(* uniq_sorted : 'a list -> 'a list *)
let rec uniq_sorted = function
  | [] -> []
  | [a] -> [a]
  | a::b::q when a = b -> uniq_sorted (b::q)
  | a::r -> a::(uniq_sorted r)

(* list_fold_op : ('a -> 'a -> 'a) -> 'a list -> 'a *)
let rec list_fold_op op = function
  | [] -> invalid_arg "list_fold_opt on empty list"
  | [a] -> a
  | x::q -> op x (list_fold_op op q)


(* Either type *)

type ('a, 'b) either =
  | Left of 'a
  | Right of 'b


(* Locations *)

type position = Lexing.position
let position_unknown = Lexing.dummy_pos

type extent = position * position
let extent_unknown = (position_unknown, position_unknown)


(* Exceptions *)

exception NoLocError of string
let error x = raise (NoLocError x)

exception LocError of extent list * string
let loc_error l f x =
  try f x with
  | NoLocError e -> raise (LocError([l], e))
  | LocError(q, e) -> raise (LocError(l::q, e))

let not_implemented e = error ("Not implemented: " ^ e)

(* Varmaps *)

module VarMap = Mapext.Make(String)
let disjoint_union k a b = match a, b with
  | Some x, None -> Some x
  | None, Some y -> Some y 
  | _ -> error ("Duplicate name in disjoint union: " ^ k)

module SSet = Set.Make(String)

(* Fixpoint *)

let rec fix equal f s =
  let fs = f s in
  if equal fs s
    then fs
    else fix equal f fs

let (@@) f x = f x

let print_list f sep fmt l =
  let rec aux = function
    | [] -> ()
    | [a] -> f fmt a
    | a::b -> f fmt a; Format.fprintf fmt "%s@," sep; aux b
  in
  aux l

let uid =
  let c = ref 0 in
  fun () -> c := !c + 1; string_of_int !c