(*
    ||M||  This file is part of HELM, an Hypertextual, Electronic        
    ||A||  Library of Mathematics, developed at the Computer Science     
    ||T||  Department, University of Bologna, Italy.                     
    ||I||                                                                
    ||T||  HELM is free software; you can redistribute it and/or         
    ||A||  modify it under the terms of the GNU General Public License   
    \   /  version 2 or (at your option) any later version.      
     \ /   This software is distributed as is, NO WARRANTY.     
      V_______________________________________________________________ *)

(* $Id$ *)

exception MetaSubstFailure of string Lazy.t
exception Uncertain of string Lazy.t

(*
exception AssertFailure of string Lazy.t
exception DeliftingARelWouldCaptureAFreeVariable;;
val apply_subst : Cic.substitution -> Cic.term -> Cic.term 
val apply_subst_context : Cic.substitution -> Cic.context -> Cic.context 
val apply_subst_metasenv: Cic.substitution -> Cic.metasenv -> Cic.metasenv 

(*** delifting ***)

val restrict :
  Cic.substitution -> (int * int) list -> Cic.metasenv -> 
  Cic.metasenv * Cic.substitution 
*)

(* the delift function takes in input a metavariable index, a local_context
 * and a term t, and substitutes every Rel in t with its position in
 * the local_context (which is the Rel moved to the canonical context).
 * Typically, the list of optional terms is the explicit
 * substitution that is applied to a metavariable occurrence and the result of
 * the delift function is a term the implicit variable can be substituted with
 * to make the term [t] unifiable with the metavariable occurrence.  In general,
 * the problem is undecidable if we consider equivalence in place of alpha
 * convertibility. Our implementation, though, is even weaker than alpha
 * convertibility, since it replace the term [tk] if and only if [tk] is a Rel
 * (missing all the other cases). Does this matter in practice?
 * The metavariable index is the index of the metavariable that must not occur
 * in the term (for occur check).
 *)
val delift : 
  unify:(NCic.metasenv -> NCic.substitution -> NCic.context ->
    NCic.term -> NCic.term -> (NCic.metasenv * NCic.substitution) option) -> 
  NCic.metasenv -> NCic.substitution -> NCic.context -> 
  int -> NCic.local_context -> NCic.term ->
    (NCic.metasenv * NCic.substitution) * NCic.term

val restrict: 
    NCic.metasenv ->
    NCic.substitution ->
      int -> int list -> NCic.metasenv * NCic.substitution * int

(* bool = true if the type of the new meta is closed *)
val mk_meta: 
   ?name:string -> 
   NCic.metasenv -> NCic.context -> 
    [ `WithType of NCic.term | `Term | `Type | `Sort ] -> 
    NCic.metasenv * int * NCic.term * NCic.term (* menv,metano,instance,type *)

(* returns the resulting type, the metasenv and the arguments *)
val saturate:
    ?delta:int -> NCic.metasenv -> NCic.substitution -> 
    NCic.context -> NCic.term -> int ->
       NCic.term * NCic.metasenv * NCic.term list

val flexible: NCic.substitution -> NCic.term list -> bool

val in_scope_tag : string
val out_scope_tag : int -> string
val is_out_scope_tag : string -> bool
val int_of_out_scope_tag : string -> int