(* Copyright (C) 2006, HELM Team.
 * 
 * This file is part of HELM, an Hypertextual, Electronic
 * Library of Mathematics, developed at the Computer Science
 * Department, University of Bologna, Italy.
 * 
 * HELM is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * HELM is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HELM; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA  02111-1307, USA.
 * 
 * For details, see the HELM World-Wide-Web page,
 * http://helm.cs.unibo.it/
 *)

type substitution 

type rule = SuperpositionRight | SuperpositionLeft |Demodulation

type equality 

and proof = new_proof * old_proof

and new_proof =
    Exact of Cic.term
  | Step of substitution * (rule * int * (Utils.pos * int) * Cic.term)

and old_proof =
    NoProof
  | BasicProof of substitution * Cic.term
  | ProofBlock of substitution * UriManager.uri * (Cic.name * Cic.term) *
      Cic.term * (Utils.pos * equality) * old_proof
  | ProofGoalBlock of old_proof * old_proof
  | ProofSymBlock of Cic.term list * old_proof
  | SubProof of Cic.term * int * old_proof

and goal_proof = (Utils.pos * int * substitution * Cic.term) list
	

val empty_subst : substitution
val apply_subst : substitution -> Cic.term -> Cic.term
val apply_subst_metasenv : substitution -> Cic.metasenv -> Cic.metasenv
val ppsubst : substitution -> string
val buildsubst : 
  int -> Cic.context -> Cic.term -> Cic.term -> substitution -> 
    substitution
val flatten_subst : substitution -> substitution 
val lookup_subst : Cic.term -> substitution -> Cic.term
val filter : substitution -> Cic.metasenv -> Cic.metasenv
val is_in_subst : int -> substitution -> bool
val merge_subst_if_possible: 
  substitution -> substitution -> 
    substitution option

val reset : unit -> unit

val mk_equality :
  int * proof * 
  (Cic.term * Cic.term * Cic.term * Utils.comparison) *
  Cic.metasenv -> 
    equality
    
val open_equality :
  equality ->
    int * proof * 
    (Cic.term * Cic.term * Cic.term * Utils.comparison) *
    Cic.metasenv * int
val compare : equality -> equality -> int
val string_of_equality : ?env:Utils.environment -> equality -> string
val string_of_proof_old : ?names:(Cic.name option)list -> old_proof -> string
val string_of_proof_new : 
  ?names:(Cic.name option)list -> new_proof -> goal_proof -> string
val build_proof_term_new: new_proof -> Cic.term 
val build_proof_term_old: ?noproof:Cic.term -> old_proof -> Cic.term
val build_goal_proof: goal_proof -> Cic.term -> Cic.term
val refl_proof: Cic.term -> Cic.term -> Cic.term 
(** ensures that metavariables in equality are unique *)
val fix_metas: int -> equality -> int * equality
val metas_of_proof: proof -> int list

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

(**
   Re-builds the term corresponding to this equality
*)
val term_of_equality: equality -> Cic.term
val term_is_equality: Cic.term -> bool

(** tests a sort of alpha-convertibility between the two terms, but on the
    metavariables *)
val meta_convertibility: Cic.term -> Cic.term -> bool

(** meta convertibility between two equations *)
val meta_convertibility_eq: equality -> equality -> bool

val is_weak_identity: equality -> bool
val is_identity: Utils.environment -> equality -> bool