type equality =
    int *                (* weight *)
    proof * 
    (Cic.term *          (* type *)
     Cic.term *          (* left side *)
     Cic.term *          (* right side *)
     Utils.comparison) * (* ordering *)  
    Cic.metasenv *       (* environment for metas *)
    Cic.term list        (* arguments *)

and proof =
  | NoProof
  | BasicProof of Cic.term
  | ProofBlock of
      Cic.substitution * UriManager.uri *
        (Cic.name * Cic.term) * Cic.term * 
        (* name, ty, eq_ty, left, right *)
(*         (Cic.name * Cic.term * Cic.term * Cic.term * Cic.term) *  *)
        (Utils.pos * equality) * proof
  | ProofGoalBlock of proof * proof (* equality *)
(*   | ProofSymBlock of Cic.term Cic.explicit_named_substitution * proof *)
  | ProofSymBlock of Cic.term list * proof
  | SubProof of Cic.term * int * proof

type environment = Cic.metasenv * Cic.context * CicUniv.universe_graph


exception MatchingFailure

val matching:
  Cic.metasenv -> Cic.context -> Cic.term -> Cic.term ->
  CicUniv.universe_graph ->
  Cic.substitution * Cic.metasenv * CicUniv.universe_graph

val unification:
  Cic.metasenv -> Cic.context -> Cic.term -> Cic.term ->
  CicUniv.universe_graph ->
  Cic.substitution * Cic.metasenv * CicUniv.universe_graph

    
(**
   Performs the beta expansion of the term "where" w.r.t. "what",
   i.e. returns the list of all the terms t s.t. "(t what) = where".
*)
val beta_expand:
  ?metas_ok:bool -> ?match_only:bool -> Cic.term -> Cic.term -> Cic.term ->
  Cic.context -> Cic.metasenv -> CicUniv.universe_graph ->
  (Cic.term * Cic.substitution * Cic.metasenv * CicUniv.universe_graph) list

    
(**
   scans the context to find all Declarations "left = right"; returns a
   list of tuples (proof, (type, left, right), newmetas). Uses
   PrimitiveTactics.new_metasenv_for_apply to replace bound variables with
   fresh metas...
*)
val find_equalities:
  Cic.context -> ProofEngineTypes.proof -> int list * equality list * int


exception TermIsNotAnEquality;;

(**
   raises TermIsNotAnEquality if term is not an equation.
   The first Cic.term is a proof of the equation
*)
val equality_of_term: Cic.term -> Cic.term -> equality

val term_is_equality: Cic.term -> bool

(**
   superposition_left env target source
   returns a list of new clauses inferred with a left superposition step
   the negative equation "target" and the positive equation "source"
*)
(* val superposition_left: environment -> equality -> equality -> equality list *)

(**
   superposition_right newmeta env target source
   returns a list of new clauses inferred with a right superposition step
   the positive equations "target" and "source"
   "newmeta" is the first free meta index, i.e. the first number above the
   highest meta index: its updated value is also returned
*)
(* val superposition_right: *)
(*   int -> environment -> equality -> equality -> int * equality list *)

(* val demodulation: int -> environment -> equality -> equality -> int * equality *)

val meta_convertibility: Cic.term -> Cic.term -> bool
  
val meta_convertibility_eq: equality -> equality -> bool

val is_identity: environment -> equality -> bool

val string_of_equality: ?env:environment -> equality -> string

(* val subsumption: environment -> equality -> equality -> bool *)

val metas_of_term: Cic.term -> int list

val fix_metas: int -> equality -> int * equality

val extract_differing_subterms:
  Cic.term -> Cic.term -> (Cic.term * Cic.term) option

val build_proof_term: proof (* equality *) -> Cic.term

val find_library_equalities:
  HMysql.dbd -> Cic.context -> ProofEngineTypes.status -> int ->
  UriManager.UriSet.t * equality list * int

val find_library_theorems:
  HMysql.dbd -> environment -> ProofEngineTypes.status -> UriManager.UriSet.t ->
  (Cic.term * Cic.term * Cic.metasenv) list

val find_context_hypotheses:
  environment -> int list -> (Cic.term * Cic.term * Cic.metasenv) list

val string_of_proof: proof -> string