matita/components/ng_refiner/nCicMetaSubst.ml

   1 (*
   2     ||M||  This file is part of HELM, an Hypertextual, Electronic
   3     ||A||  Library of Mathematics, developed at the Computer Science
   4     ||T||  Department, University of Bologna, Italy.
   5     ||I||
   6     ||T||  HELM is free software; you can redistribute it and/or
   7     ||A||  modify it under the terms of the GNU General Public License
   8     \   /  version 2 or (at your option) any later version.
   9      \ /   This software is distributed as is, NO WARRANTY.
  10       V_______________________________________________________________ *)
  11
  12 (* $Id$ *)
  13
  14 let debug = ref false;;
  15 let indent = ref "";;
  16 let times = ref [];;
  17 let pp s =
  18  if !debug then
  19   prerr_endline (Printf.sprintf "%-20s" !indent ^ " " ^ Lazy.force s)
  20 ;;
  21 let inside c =
  22  if !debug then
  23   begin
  24    let time1 = Unix.gettimeofday () in
  25    indent := !indent ^ String.make 1 c;
  26    times := time1 :: !times;
  27    prerr_endline ("{{{" ^ !indent ^ " ")
  28   end
  29 ;;
  30 let outside exc_opt =
  31  if !debug then
  32   begin
  33    let time2 = Unix.gettimeofday () in
  34    let time1 =
  35     match !times with time1::tl -> times := tl; time1 | [] -> assert false in
  36    prerr_endline ("}}} " ^ string_of_float (time2 -. time1));
  37    (match exc_opt with
  38    | Some e ->  prerr_endline ("exception raised: " ^ Printexc.to_string e)
  39    | None -> ());
  40    try
  41     indent := String.sub !indent 0 (String.length !indent -1)
  42    with
  43     Invalid_argument _ -> indent := "??"; ()
  44   end
  45 ;;
  46
  47 exception MetaSubstFailure of string Lazy.t
  48 exception Uncertain of string Lazy.t
  49
  50 let newmeta,maxmeta,pushmaxmeta,popmaxmeta =
  51   let maxmeta = ref 0 in
  52   let pushedmetas = ref [] in
  53   (fun () -> incr maxmeta; !maxmeta),
  54   (fun () -> !maxmeta),
  55   (fun () -> pushedmetas := !maxmeta::!pushedmetas; maxmeta := 0),
  56   (fun () -> match !pushedmetas with [] -> assert false | _hd::tl -> pushedmetas := tl)
  57 ;;
  58
  59 exception NotFound of [`NotInTheList | `NotWellTyped];;
  60
  61 let position to_skip n (shift, lc) =
  62   match lc with
  63   | NCic.Irl len when n <= shift + to_skip || n > shift + len ->
  64      raise (NotFound `NotInTheList)
  65   | NCic.Irl _ -> n - shift
  66   | NCic.Ctx tl ->
  67       let rec aux to_skip k = function
  68          | [] -> raise (NotFound `NotInTheList)
  69          | _ :: tl when to_skip > 0 -> aux (to_skip - 1) (k+1) tl
  70          | (NCic.Rel m)::_ when m + shift = n -> k
  71          | _::tl -> aux to_skip (k+1) tl
  72       in
  73        aux to_skip 1 tl
  74 ;;
  75
  76 let pack_lc orig =
  77   let rec are_contiguous k = function
  78     | [] -> true
  79     | (NCic.Rel j) :: tl when j = k+1 -> are_contiguous j tl
  80     | _ -> false
  81   in
  82   match orig with
  83   | _, NCic.Ctx [] -> 0, NCic.Irl 0
  84   | shift, NCic.Ctx (NCic.Rel k::tl as l) when are_contiguous k tl ->
  85       shift+k-1, NCic.Irl (List.length l)
  86   | _ -> orig
  87 ;;
  88
  89
  90
  91 let mk_perforated_irl shift len restrictions =
  92   let rec aux n =
  93     if n = 0 then [] else
  94      if List.mem (n+shift) restrictions then aux (n-1)
  95      else (NCic.Rel n) :: aux (n-1)
  96   in
  97     pack_lc (shift, NCic.Ctx (List.rev (aux len)))
  98 ;;
  99
 100 exception Occur;;
 101
 102 let purge_restricted restrictions more_restrictions l =
 103  if more_restrictions = [] then l
 104  else
 105   begin
 106    pp (lazy ("TO BE RESTRICTED: " ^
 107     (String.concat "," (List.map string_of_int restrictions))));
 108    pp (lazy ("MORE RESTRICTIONS: " ^
 109     (String.concat "," (List.map string_of_int more_restrictions))));
 110    let shift,lc = l in
 111    let lc = NCicUtils.expand_local_context lc in
 112     let rec aux n lc =
 113      match lc with
 114         [] -> []
 115       | _ when List.mem n restrictions -> aux (n+1) lc
 116       | _::tl when List.mem n more_restrictions -> aux (n+1) tl
 117       | he::tl -> he::aux (n+1) tl
 118     in
 119     pack_lc (shift, NCic.Ctx (aux 1 lc))
 120   end
 121 ;;
 122
 123 let rec force_does_not_occur status metasenv subst restrictions t =
 124  let rec aux k ms = function
 125     | NCic.Rel r when List.mem (r - k) restrictions -> raise Occur
 126     | NCic.Rel r as orig ->
 127         let amount =
 128           List.length (List.filter (fun x -> x < r - k) restrictions)
 129         in
 130         if amount > 0 then ms, NCic.Rel (r - amount) else ms, orig
 131     | NCic.Meta (n, (shift,lc as l)) as orig ->
 132        (try
 133          let _,_,bo,_ = NCicUtils.lookup_subst n subst in
 134           aux k ms (NCicSubstitution.subst_meta status l bo)
 135         with
 136          NCicUtils.Subst_not_found _ ->
 137           (* we ignore the subst since restrict will take care of already
 138            * instantiated/restricted metavariabels *)
 139           let l = NCicUtils.expand_local_context lc in
 140           let sl = List.map (NCicSubstitution.lift status shift) l in
 141           let (metasenv,subst as ms), _, restrictions_for_n, l' =
 142              List.fold_right
 143                (fun t (ms, i, restrictions_for_n, l) ->
 144                  try
 145               (*pp (lazy ("L'ORLO DELLA FOSSA: k= " ^ string_of_int k ^ " shift=" ^
 146                string_of_int shift ^ " t=" ^ status#ppterm ~metasenv ~subst ~context:[] t));*)
 147                    let ms, t = aux k ms t in
 148               (*pp (lazy ("LA FOSSA: " ^ status#ppterm ~metasenv ~subst ~context:[] t));*)
 149                    ms, i-1, restrictions_for_n, t::l
 150                  with Occur ->
 151                    ms, i-1, i::restrictions_for_n, l)
 152                sl (ms, List.length l, [], [])
 153           in
 154           if restrictions_for_n = [] then
 155             ms, if sl = l' then orig else (
 156                 (*pp (lazy ("FINITO: " ^ status#ppterm ~metasenv:[] ~subst:[]
 157                   ~context:[] (NCic.Meta (n,pack_lc (0, NCic.Ctx l')))));*)
 158               NCic.Meta (n, pack_lc (0, NCic.Ctx l'))
 159             )
 160           else
 161             let l' = pack_lc (0, NCic.Ctx l') in
 162             let _ = pp (lazy ("restrictions for n are:" ^ String.concat "," (List.map string_of_int restrictions_for_n))) in
 163             let metasenv, subst, newmeta, more_restricted =
 164               restrict status metasenv subst n restrictions_for_n in
 165             let _ = pp (lazy ("more restricted: " ^String.concat "," (List.map string_of_int more_restricted))) in
 166             let l' = purge_restricted restrictions more_restricted l' in
 167               (metasenv, subst), NCic.Meta (newmeta, l'))
 168     | t -> NCicUntrusted.map_term_fold_a status (fun _ k -> k+1) k aux ms t
 169  in
 170    aux 0 (metasenv,subst) t
 171
 172 and force_does_not_occur_in_context status metasenv subst restrictions = function
 173   | name, NCic.Decl t as orig ->
 174       (* pp (lazy ("CCC: hd is" ^ status#ppterm ~metasenv:[] ~subst:[] ~context:[] t ^
 175       "\nCCC: restrictions are:" ^ String.concat "," (List.map string_of_int restrictions)));*)
 176       let (metasenv, subst), t' =
 177         force_does_not_occur status metasenv subst restrictions t in
 178       metasenv, subst, (if t == t' then orig else (name,NCic.Decl t'))
 179   | name, NCic.Def (bo, ty) as orig ->
 180       let (metasenv, subst), bo' =
 181         force_does_not_occur status metasenv subst restrictions bo in
 182       let (metasenv, subst), ty' =
 183         force_does_not_occur status metasenv subst restrictions ty in
 184       metasenv, subst,
 185        (if bo == bo' && ty == ty' then orig else (name, NCic.Def (bo', ty')))
 186
 187 and erase_in_context status metasenv subst pos restrictions = function
 188   | [] -> metasenv, subst, restrictions, []
 189   | hd::tl as orig ->
 190       let metasenv, subst, restricted, tl' =
 191         erase_in_context status metasenv subst (pos+1) restrictions tl in
 192       if List.mem pos restricted then
 193         metasenv, subst, restricted, tl'
 194       else
 195         try
 196           let metasenv, subst, hd' =
 197             let delifted_restricted =
 198               List.map ((+) ~-pos) (List.filter ((<=) pos) restricted) in
 199             force_does_not_occur_in_context
 200               status metasenv subst delifted_restricted hd
 201           in
 202            metasenv, subst, restricted,
 203             (if hd' == hd && tl' == tl then orig else (hd' :: tl'))
 204         with Occur ->
 205             metasenv, subst, (pos :: restricted), tl'
 206
 207 and restrict status metasenv subst i (restrictions as orig) =
 208   assert (restrictions <> []);
 209   try
 210     let name, ctx, bo, ty = NCicUtils.lookup_subst i subst in
 211       try
 212         let metasenv, subst, restrictions, newctx =
 213           erase_in_context status metasenv subst 1 restrictions ctx in
 214         let (metasenv, subst), newty =
 215           force_does_not_occur status metasenv subst restrictions ty in
 216         let (metasenv, subst), newbo =
 217           force_does_not_occur status metasenv subst restrictions bo in
 218         let j = newmeta () in
 219         let subst_entry_j = j, (name, newctx, newbo, newty) in
 220         let reloc_irl = mk_perforated_irl 0 (List.length ctx) restrictions in
 221         let subst_entry_i = i, (name, ctx, NCic.Meta (j, reloc_irl), ty) in
 222         let new_subst =
 223           subst_entry_j :: List.map
 224             (fun ((n,_) as orig) -> if i = n then subst_entry_i else orig) subst
 225         in
 226         let diff = List.filter (fun x -> not (List.mem x orig)) restrictions in
 227         metasenv, new_subst, j, diff
 228       with Occur -> raise (MetaSubstFailure (lazy (Printf.sprintf
 229             ("Cannot restrict the context of the metavariable ?%d over "^^
 230             "the hypotheses %s since ?%d is already instantiated "^^
 231             "with %s and at least one of the hypotheses occurs in "^^
 232             "the substituted term") i  (String.concat ", "
 233             (List.map (fun x -> fst (List.nth ctx (x-1))) restrictions)) i
 234             (status#ppterm ~metasenv ~subst ~context:ctx bo))))
 235   with NCicUtils.Subst_not_found _ ->
 236     try
 237       let name, ctx, ty = NCicUtils.lookup_meta i metasenv in
 238       try
 239         let metasenv, subst, restrictions, newctx =
 240           erase_in_context status metasenv subst 1 restrictions ctx in
 241         let (metasenv, subst), newty =
 242           force_does_not_occur status metasenv subst restrictions ty in
 243         let j = newmeta () in
 244         let metasenv_entry = j, (name, newctx, newty) in
 245         let reloc_irl =
 246           mk_perforated_irl 0 (List.length ctx) restrictions in
 247         let subst_entry = i, (name, ctx, NCic.Meta (j, reloc_irl), ty) in
 248          (* pp (lazy ("BBB: dopo1 \n" ^  NCicPp.ppsubst ~metasenv [subst_entry]));
 249           pp (lazy ("BBB: dopo2 \n" ^  NCicPp.ppsubst ~metasenv (subst_entry::subst)));
 250           pp (lazy ("BBB: dopo metasenv\n" ^  NCicPp.ppmetasenv ~subst [metasenv_entry]));*)
 251         let diff = List.filter (fun x -> not (List.mem x orig)) restrictions in
 252         List.map
 253           (fun ((n,_) as orig) -> if i = n then metasenv_entry else orig)
 254           metasenv,
 255         subst_entry :: subst, j, diff
 256       with Occur -> raise (MetaSubstFailure (lazy (Printf.sprintf
 257           ("Cannot restrict the context of the metavariable ?%d "^^
 258           "over the hypotheses %s since metavariable's type depends "^^
 259           "on at least one of them") i (String.concat ", "
 260           (List.map (fun x -> fst (List.nth ctx (x-1))) restrictions)))))
 261     with
 262     | NCicUtils.Meta_not_found _ -> assert false
 263 ;;
 264
 265 let rec is_flexible status context ~subst = function
 266   | NCic.Meta (i,lc) ->
 267        (try
 268           let _,_,t,_ = NCicUtils.lookup_subst i subst in
 269           let t = NCicSubstitution.subst_meta status lc t in
 270           is_flexible status context ~subst t
 271         with NCicUtils.Subst_not_found _ -> true)
 272   | NCic.Appl (NCic.Meta (i,lc) :: args)->
 273       (try
 274         let _,_,t,_ = NCicUtils.lookup_subst i subst in
 275         let t = NCicSubstitution.subst_meta status lc t in
 276         is_flexible status context ~subst
 277           (NCicReduction.head_beta_reduce status ~delta:max_int
 278             (NCic.Appl (t :: args)))
 279       with NCicUtils.Subst_not_found _ -> true)
 280    (* this is a cheap whd, it only performs zeta-reduction.
 281     *
 282     * it works when the **omissis** disambiguation algorithm
 283     * is run on `let x := K a b in t`, K is substituted for a
 284     * ? and thus in t metavariables have a flexible Rel
 285     *)
 286   | NCic.Rel i ->
 287       (try
 288          match List.nth context (i-1)
 289          with
 290          | _,NCic.Def (bo,_) ->
 291                is_flexible status context ~subst
 292                  (NCicSubstitution.lift status i bo)
 293          | _ -> false
 294       with
 295       | Failure _ ->
 296           prerr_endline (Printf.sprintf "Rel %d inside context:\n%s" i
 297             (status#ppcontext ~subst ~metasenv:[] context));
 298           assert false
 299       | Invalid_argument _ -> assert false)
 300   | _ -> false
 301 ;;
 302
 303 let is_out_scope = function `OutScope _ -> true | _ -> false;;
 304 let is_out_scope_tag = List.exists is_out_scope;;
 305 let int_of_out_scope_tag tag =
 306  match List.filter is_out_scope tag with [`OutScope n] -> n | _ -> assert false
 307 ;;
 308
 309
 310 exception Found;;
 311 exception TypeNotGood;;
 312
 313 (* INVARIANT: we suppose that t is not another occurrence of Meta(n,_),
 314    otherwise the occur check does not make sense in case of unification
 315    of ?n with ?n *)
 316 let delift status ~unify metasenv subst context n l t =
 317   (*D*)  inside 'D'; try let rc =
 318   let is_in_scope_meta subst = function
 319     | NCic.Meta (i,_) ->
 320         (try
 321            let tag, _, _, _ = NCicUtils.lookup_subst i subst in
 322             List.mem `InScope tag
 323         with NCicUtils.Subst_not_found _ -> false)
 324     | _ -> false
 325   in
 326   let contains_in_scope subst t =
 327     let rec aux _ () = function
 328       | NCic.Meta _ as t ->
 329           if is_in_scope_meta subst t then raise Found
 330           else ()
 331       | t ->
 332           if is_in_scope_meta subst t then raise Found
 333           else NCicUtils.fold (fun _ () -> ()) () aux () t
 334     in
 335     try aux () () t; false with Found -> true
 336   in
 337   let unify_list in_scope =
 338     match l with
 339     | _, NCic.Irl _ -> fun _ _ _ _ _ -> None
 340     | shift, NCic.Ctx l -> fun metasenv subst context k t ->
 341        if is_flexible status context ~subst t || contains_in_scope subst t then None else
 342          let lb =
 343            List.map (fun t ->
 344             let t = NCicSubstitution.lift status (k+shift) t in
 345             t, is_flexible status context ~subst t)
 346            l
 347          in
 348          HExtlib.list_findopt
 349           (fun (li,flexible) i ->
 350             if flexible || i < in_scope then None else
 351              match unify metasenv subst context li t with
 352              | Some (metasenv,subst) ->
 353                  Some ((metasenv, subst), NCic.Rel (i+1+k))
 354              | None -> None)
 355           lb
 356   in
 357   let rec aux (context,k,in_scope) (metasenv, subst as ms) t =
 358    match unify_list in_scope metasenv subst context k t with
 359    | Some x -> x
 360    | None ->
 361     match t with
 362     | NCic.Rel n as t when n <= k -> ms, t
 363     | NCic.Rel n ->
 364         (try
 365           match List.nth context (n-1) with
 366           | _,NCic.Def (bo,_) ->
 367                 (try ms, NCic.Rel ((position in_scope (n-k) l) + k)
 368                  with (NotFound `NotInTheList) ->
 369                 (* CSC: This bit of reduction hurts performances since it is
 370                  * possible to  have an exponential explosion of the size of the
 371                  * proof. required for nat/nth_prime.ma *)
 372                   aux (context,k,in_scope) ms (NCicSubstitution.lift status n bo))
 373           | _,NCic.Decl _ -> ms, NCic.Rel ((position in_scope (n-k) l) + k)
 374         with Failure _ -> assert false) (*Unbound variable found in delift*)
 375     | NCic.Meta (i,_) when i=n ->
 376          raise (MetaSubstFailure (lazy (Printf.sprintf (
 377            "Cannot unify the metavariable ?%d with a term that has "^^
 378            "as subterm %s in which the same metavariable "^^
 379            "occurs (occur check)") i
 380             (status#ppterm ~context ~metasenv ~subst t))))
 381     | NCic.Meta (i,l1) as orig ->
 382         (try
 383            let tag,c,t,ty = NCicUtils.lookup_subst i subst in
 384            let in_scope, clear =
 385             if List.mem `InScope tag then 0, true
 386             else if is_out_scope_tag tag then int_of_out_scope_tag tag,true
 387             else in_scope, false
 388            in
 389            let ms =
 390              if not clear then ms
 391              else
 392                metasenv,
 393                (i,([],c,t,ty)) :: List.filter (fun (j,_) -> i <> j) subst
 394            in
 395            aux (context,k,in_scope) ms (NCicSubstitution.subst_meta status l1 t)
 396          with NCicUtils.Subst_not_found _ ->
 397            if snd l1 = NCic.Irl 0 || snd l1 = NCic.Ctx [] then ms, orig
 398            else
 399               let shift1,lc1 = l1 in
 400               let shift,lc = l in
 401               let shift = shift + k in
 402               match lc, lc1 with
 403               | NCic.Irl len, NCic.Irl len1
 404                 when shift1 + len1 < shift || shift1 > shift + len ->
 405                   let restrictions = HExtlib.list_seq 1 (len1 + 1) in
 406                   let metasenv, subst, newmeta, more_restricted =
 407                    restrict status metasenv subst i restrictions in
 408                   let l' = (0,NCic.Irl (max 0 (k-shift1))) in
 409                   let l' = purge_restricted restrictions more_restricted l' in
 410                   (metasenv, subst),NCic.Meta (newmeta,l')
 411               | NCic.Irl len, NCic.Irl len1 ->
 412                   let low_restrictions, new_shift =
 413                     if k <= shift1 && shift1 < shift then
 414                       HExtlib.list_seq 1 (shift - shift1 + 1), k
 415                     else if shift1 < k (* <= shift *) then
 416                       let save_below = k - shift1 in
 417                       HExtlib.list_seq (save_below + 1) (shift - shift1 + 1),
 418                       shift1
 419                     else [], shift1 - shift + k
 420                   in
 421                   let high_restrictions =
 422                     let last = shift + len in
 423                     let last1 = shift1 + len1 in
 424                     if last1 > last then
 425                       let high_gap = last1 - last in
 426                       HExtlib.list_seq (len1 - high_gap + 1) (len1 + 1)
 427                     else []
 428                   in
 429                   let restrictions = low_restrictions @ high_restrictions in
 430                   if restrictions = [] then
 431                     if shift = k then ms, orig
 432                     else ms, NCic.Meta (i, (new_shift, lc1))
 433                   else
 434                     let metasenv, subst, newmeta, more_restricted =
 435                      restrict status metasenv subst i restrictions in
 436                     let newlc_len = len1 - List.length restrictions in
 437                     let l' = new_shift, NCic.Irl newlc_len in
 438                     let l' = purge_restricted restrictions more_restricted l' in
 439                     (metasenv, subst),NCic.Meta(newmeta,l')
 440
 441               | _ ->
 442                   let lc1 = NCicUtils.expand_local_context lc1 in
 443                   let lc1 = List.map (NCicSubstitution.lift status shift1) lc1 in
 444                   let rec deliftl tbr j ms = function
 445                     | [] -> ms, tbr, []
 446                     | t::tl ->
 447                         let ms, tbr, tl = deliftl tbr (j+1) ms tl in
 448                         try
 449                           let ms, t = aux (context,k,in_scope) ms t in
 450                           ms, tbr, t::tl
 451                         with
 452                         | (NotFound `NotInTheList) | MetaSubstFailure _ -> ms, j::tbr, tl
 453                   in
 454                   let (metasenv, subst), to_be_r, lc1' = deliftl [] 1 ms lc1 in
 455                   pp (lazy ("TO BE RESTRICTED: " ^
 456                    (String.concat "," (List.map string_of_int to_be_r))));
 457                   let l1 = pack_lc (0, NCic.Ctx lc1') in
 458                   pp (lazy ("newmeta:" ^ status#ppterm
 459                    ~metasenv ~subst ~context (NCic.Meta (999,l1))));
 460                   pp (lazy (status#ppmetasenv ~subst metasenv));
 461                   if to_be_r = [] then
 462                     (metasenv, subst),
 463                     (if lc1' = lc1 then orig else NCic.Meta (i,l1))
 464                   else
 465                     let metasenv, subst, newmeta, more_restricted =
 466                      restrict status metasenv subst i to_be_r in
 467                     let l1 = purge_restricted to_be_r more_restricted l1 in
 468                      (metasenv, subst), NCic.Meta(newmeta,l1))
 469
 470     | t ->
 471         NCicUntrusted.map_term_fold_a status
 472           (fun e (c,k,s) -> (e::c,k+1,s)) (context,k,in_scope) aux ms t
 473   in
 474 (*
 475   prerr_endline (
 476     "DELIFTO " ^ status#ppterm ~metasenv ~subst ~context t ^ " w.r.t. " ^
 477     status#ppterm ~metasenv ~subst ~context (NCic.Meta(n,l)) ^ " i.e. " ^
 478     String.concat ", " (List.map (status#ppterm ~metasenv ~subst ~context) (
 479       let shift, lc = l in
 480       (List.map (NCicSubstitution.lift status shift)
 481         (NCicUtils.expand_local_context lc))
 482   )));
 483 *)
 484    try
 485 (*assert (try n = -1 or (ignore(NCicUtils.lookup_meta n metasenv); true) with NCicUtils.Meta_not_found _ -> false);*)
 486     let ((metasenv,subst),t) as res = aux (context,0,0) (metasenv,subst) t in
 487     if (try n <> -1 && (ignore(NCicUtils.lookup_meta n metasenv); false)
 488         with NCicUtils.Meta_not_found _ -> true)
 489     then
 490      let _,context,bo,_ = NCicUtils.lookup_subst n subst in
 491       match unify metasenv subst context bo t with
 492          None -> raise (NotFound `NotWellTyped)
 493        | Some (metasenv,subst) -> (metasenv,subst),t
 494     else
 495     (try
 496       let _,context,ty = NCicUtils.lookup_meta n metasenv in
 497       let ty' =
 498        match t with
 499           NCic.Sort _ -> (* could be algebraic *) NCic.Implicit `Closed
 500         | _ -> NCicTypeChecker.typeof status ~subst ~metasenv context t in
 501        (match ty,ty' with
 502            NCic.Implicit _,_ ->
 503             (match ty' with
 504                 NCic.Sort _ | NCic.Meta _ | NCic.Implicit _ -> res
 505               | _ -> raise TypeNotGood)
 506          | _,NCic.Implicit _ ->
 507             (match ty with
 508                 NCic.Sort _ | NCic.Meta _ | NCic.Implicit _ -> res
 509               | _ -> raise TypeNotGood)
 510          | _ ->
 511            if
 512             NCicReduction.are_convertible status ~metasenv ~subst context ty' ty
 513            then
 514             res
 515            else
 516             raise TypeNotGood)
 517      with
 518         NCicUtils.Meta_not_found _ ->
 519          (* Fake metavariable used in NTacStatus and NCicRefiner :-( *)
 520          assert (n = -1); res
 521       | NCicTypeChecker.TypeCheckerFailure msg ->
 522          HLog.error "----------- Problem with Dependent Types ----------";
 523          HLog.error (Lazy.force msg) ;
 524          HLog.error "---------------------------------------------------";
 525          raise (NotFound `NotWellTyped)
 526       | TypeNotGood
 527       | NCicTypeChecker.AssertFailure _
 528       | NCicReduction.AssertFailure _ ->
 529          raise (NotFound `NotWellTyped))
 530    with NotFound reason ->
 531       (* This is the case where we fail even first order unification. *)
 532       (* The reason is that our delift function is weaker than first  *)
 533       (* order (in the sense of alpha-conversion). See comment above  *)
 534       (* related to the delift function.                              *)
 535       let reason =
 536        match reason with
 537           `NotInTheList -> "some variable cannot be delifted"
 538         | `NotWellTyped -> "the unifier found is not well typed" in
 539       let msg = (lazy (Printf.sprintf
 540         ("Error trying to abstract %s over [%s]: %s")
 541         (status#ppterm ~metasenv ~subst
 542         ~context t) (String.concat "; " (List.map (status#ppterm ~metasenv
 543         ~subst ~context) (let shift, lc = l in List.map (NCicSubstitution.lift
 544         status shift) (NCicUtils.expand_local_context lc)))) reason))
 545       in
 546       let shift, lc = l in
 547       let lc = NCicUtils.expand_local_context lc in
 548       let l = List.map (NCicSubstitution.lift status shift) lc in
 549        if
 550         List.exists (fun t-> NCicUntrusted.metas_of_term status subst context t <> [])l
 551        then
 552         raise (Uncertain msg)
 553        else
 554         raise (MetaSubstFailure msg)
 555  (*D*)  in outside None; rc with exn -> outside (Some exn); raise exn
 556 ;;
 557
 558 let mk_meta ?(attrs=[]) metasenv context ?with_type kind =
 559   assert(kind <> `IsSort || context = []);
 560   let n = newmeta () in
 561   let ty= match with_type with None-> NCic.Implicit (`Typeof n)| Some x ->x in
 562   let len = List.length context in
 563   let attrs = NCicUntrusted.set_kind kind attrs in
 564   let menv_entry = (n, (attrs, context, ty)) in
 565   menv_entry :: metasenv, n, NCic.Meta (n, (0,NCic.Irl len)), ty
 566 ;;
 567
 568 let extend_meta metasenv n =
 569  try
 570   let attrs,cc,ty = NCicUtils.lookup_meta n metasenv in
 571   (match ty with
 572   | NCic.Implicit (`Typeof _) ->
 573       let mk_meta context kind =
 574         let metasenv, _, ty, _ = mk_meta metasenv context kind in
 575         (n, (attrs, cc, ty)) :: List.filter (fun (x,_) -> x <> n) metasenv, ty
 576       in
 577       (match NCicUntrusted.kind_of_meta attrs with
 578        | `IsSort
 579        | `IsType -> mk_meta [] `IsSort
 580        | `IsTerm -> mk_meta cc `IsType)
 581   | ty -> metasenv, ty)
 582  with NCicUtils.Meta_not_found _ -> assert false
 583 ;;
 584
 585 let saturate status ?(delta=0) metasenv subst context ty goal_arity =
 586  assert (goal_arity >= 0);
 587   let rec aux metasenv = function
 588    | NCic.Prod (name,s,t) as ty ->
 589        let metasenv1, _, arg,_ =
 590           mk_meta ~attrs:[`Name name] metasenv context ~with_type:s `IsTerm in
 591        let t, metasenv1, args, pno =
 592            aux metasenv1 (NCicSubstitution.subst status arg t)
 593        in
 594        if pno + 1 = goal_arity then
 595          ty, metasenv, [], goal_arity+1
 596        else
 597          t, metasenv1, arg::args, pno+1
 598    | ty ->
 599         match NCicReduction.whd status ~subst context ty ~delta with
 600         | NCic.Prod _ as ty -> aux metasenv ty
 601         | ty -> ty, metasenv, [], 0
 602   in
 603   let res, newmetasenv, arguments, _ = aux metasenv ty in
 604   res, newmetasenv, arguments
 605 ;;