helm/software/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 exception MetaSubstFailure of string Lazy.t
  15 exception Uncertain of string Lazy.t
  16
  17 let newmeta =
  18   let maxmeta = ref 0 in
  19   fun () -> incr maxmeta; !maxmeta
  20 ;;
  21
  22 exception NotInTheList;;
  23
  24 let position n (shift, lc) =
  25   match lc with
  26   | NCic.Irl len when n <= shift || n > shift + len -> raise NotInTheList
  27   | NCic.Irl _ -> n - shift
  28   | NCic.Ctx tl ->
  29       let rec aux k = function
  30          | [] -> raise NotInTheList
  31          | (NCic.Rel m)::_ when m + shift = n -> k
  32          | _::tl -> aux (k+1) tl
  33       in
  34        aux 1 tl
  35 ;;
  36
  37 let pack_lc orig =
  38   let rec are_contiguous k = function
  39     | [] -> true
  40     | (NCic.Rel j) :: tl when j = k+1 -> are_contiguous j tl
  41     | _ -> false
  42   in
  43   match orig with
  44   | _, NCic.Ctx [] -> 0, NCic.Irl 0
  45   | shift, NCic.Ctx (NCic.Rel k::tl as l) when are_contiguous k tl ->
  46       shift+k-1, NCic.Irl (List.length l)
  47   | _ -> orig
  48 ;;
  49
  50
  51
  52 let mk_perforated_irl shift len restrictions =
  53   let rec aux n =
  54     if n = 0 then [] else
  55      if List.mem (n+shift) restrictions then aux (n-1)
  56      else (NCic.Rel n) :: aux (n-1)
  57   in
  58     pack_lc (shift, NCic.Ctx (List.rev (aux len)))
  59 ;;
  60
  61 exception Occur;;
  62
  63 let rec force_does_not_occur metasenv subst restrictions t =
  64  let rec aux k ms = function
  65     | NCic.Rel r when List.mem (r - k) restrictions -> raise Occur
  66     | NCic.Rel r as orig ->
  67         let amount =
  68           List.length (List.filter (fun x -> x < r - k) restrictions)
  69         in
  70         if amount > 0 then ms, NCic.Rel (r - amount) else ms, orig
  71     | NCic.Meta (n, (shift,lc as l)) as orig ->
  72        (* we ignore the subst since restrict will take care of already
  73         * instantiated/restricted metavariabels *)
  74        let (metasenv,subst as ms), restrictions_for_n, l' =
  75          let l = NCicUtils.expand_local_context lc in
  76
  77          let ms, _, restrictions_for_n, l =
  78           List.fold_right
  79             (fun t (ms, i, restrictions_for_n, l) ->
  80               try
  81                 let ms, t = aux (k-shift) ms t in
  82                 ms, i-1, restrictions_for_n, t::l
  83               with Occur ->
  84                 ms, i-1, i::restrictions_for_n, l)
  85             l (ms, List.length l, [], [])
  86          in
  87
  88           ms, restrictions_for_n, pack_lc (shift, NCic.Ctx l)
  89        in
  90        if restrictions_for_n = [] then
  91          ms, if l = l' then orig else NCic.Meta (n, l')
  92        else
  93          let metasenv, subst, newmeta =
  94            restrict metasenv subst n restrictions_for_n
  95          in
  96            (metasenv, subst), NCic.Meta (newmeta, l')
  97     | t -> NCicUntrusted.map_term_fold_a (fun _ k -> k+1) k aux ms t
  98  in
  99    aux 0 (metasenv,subst) t
 100
 101 and force_does_not_occur_in_context metasenv subst restrictions = function
 102   | name, NCic.Decl t as orig ->
 103       let (metasenv, subst), t' =
 104         force_does_not_occur metasenv subst restrictions t in
 105       metasenv, subst, (if t == t' then orig else (name,NCic.Decl t'))
 106   | name, NCic.Def (bo, ty) as orig ->
 107       let (metasenv, subst), bo' =
 108         force_does_not_occur metasenv subst restrictions bo in
 109       let (metasenv, subst), ty' =
 110         force_does_not_occur metasenv subst restrictions ty in
 111       metasenv, subst,
 112        (if bo == bo' && ty == ty' then orig else (name, NCic.Def (bo', ty')))
 113
 114 and erase_in_context metasenv subst pos restrictions = function
 115   | [] -> metasenv, subst, restrictions, []
 116   | hd::tl as orig ->
 117       let metasenv, subst, restricted, tl' =
 118         erase_in_context metasenv subst (pos+1) restrictions tl in
 119       if List.mem pos restricted then
 120         metasenv, subst, restricted, tl'
 121       else
 122         try
 123           let metasenv, subst, hd' =
 124             let delifted_restricted =
 125               List.map ((+) ~-pos) (List.filter ((<=) pos) restricted) in
 126             force_does_not_occur_in_context
 127               metasenv subst delifted_restricted hd
 128           in
 129            metasenv, subst, restricted,
 130             (if hd' == hd && tl' == tl then orig else (hd' :: tl'))
 131         with Occur ->
 132             metasenv, subst, (pos :: restricted), tl'
 133
 134 and restrict metasenv subst i restrictions =
 135   assert (restrictions <> []);
 136   try
 137     let name, ctx, bo, ty = NCicUtils.lookup_subst i subst in
 138       try
 139         let metasenv, subst, restrictions, newctx =
 140           erase_in_context metasenv subst 1 restrictions ctx in
 141         let (metasenv, subst), newty =
 142           force_does_not_occur metasenv subst restrictions ty in
 143         let (metasenv, subst), newbo =
 144           force_does_not_occur metasenv subst restrictions bo in
 145         let j = newmeta () in
 146         let subst_entry_j = j, (name, newctx, newbo, newty) in
 147         let reloc_irl = mk_perforated_irl 0 (List.length ctx) restrictions in
 148         let subst_entry_i = i, (name, ctx, NCic.Meta (j, reloc_irl), ty) in
 149         let new_subst =
 150           subst_entry_j :: List.map
 151             (fun (n,_) as orig -> if i = n then subst_entry_i else orig) subst
 152         in
 153 (*
 154     prerr_endline ("restringo nella subst: " ^string_of_int i ^ " -> " ^
 155       string_of_int j ^ "\n" ^
 156       NCicPp.ppsubst ~metasenv [subst_entry_j] ^ "\n\n" ^
 157       NCicPp.ppsubst ~metasenv [subst_entry_i] ^ "\n" ^
 158       NCicPp.ppterm ~metasenv ~subst ~context:ctx bo ^ " ---- " ^
 159       NCicPp.ppterm ~metasenv ~subst ~context:newctx newbo
 160             );
 161 *)
 162         metasenv, new_subst, j
 163       with Occur -> raise (MetaSubstFailure (lazy (Printf.sprintf
 164             ("Cannot restrict the context of the metavariable ?%d over "^^
 165             "the hypotheses %s since ?%d is already instantiated "^^
 166             "with %s and at least one of the hypotheses occurs in "^^
 167             "the substituted term") i  (String.concat ", "
 168             (List.map (fun x -> fst (List.nth ctx (x-1))) restrictions)) i
 169             (NCicPp.ppterm ~metasenv ~subst ~context:ctx bo))))
 170   with NCicUtils.Subst_not_found _ ->
 171     try
 172       let name, ctx, ty = NCicUtils.lookup_meta i metasenv in
 173       try
 174         let metasenv, subst, restrictions, newctx =
 175           erase_in_context metasenv subst 1 restrictions ctx in
 176         let (metasenv, subst), newty =
 177           force_does_not_occur metasenv subst restrictions ty in
 178         let j = newmeta () in
 179         let metasenv_entry = j, (name, newctx, newty) in
 180         let reloc_irl =
 181           mk_perforated_irl 0 (List.length ctx) restrictions in
 182         let subst_entry = i, (name, ctx, NCic.Meta (j, reloc_irl), ty) in
 183         List.map
 184           (fun (n,_) as orig -> if i = n then metasenv_entry else orig)
 185           metasenv,
 186         subst_entry :: subst, j
 187       with Occur -> raise (MetaSubstFailure (lazy (Printf.sprintf
 188           ("Cannot restrict the context of the metavariable ?%d "^^
 189           "over the hypotheses %s since metavariable's type depends "^^
 190           "on at least one of them") i (String.concat ", "
 191           (List.map (fun x -> fst (List.nth ctx (x-1))) restrictions)))))
 192     with
 193     | NCicUtils.Meta_not_found _ -> assert false
 194 ;;
 195
 196 (* INVARIANT: we suppose that t is not another occurrence of Meta(n,_),
 197    otherwise the occur check does not make sense in case of unification
 198    of ?n with ?n *)
 199 let delift metasenv subst context n l t =
 200   let rec aux k (metasenv, subst as ms) = function
 201     | NCic.Rel n as t when n <= k -> ms, t
 202     | NCic.Rel n ->
 203         (try
 204           match List.nth context (n-k-1) with
 205           | _,NCic.Def (bo,_) ->
 206                 (try ms, NCic.Rel ((position (n-k) l) + k)
 207                  with NotInTheList ->
 208                 (* CSC: This bit of reduction hurts performances since it is
 209                  * possible to  have an exponential explosion of the size of the
 210                  * proof. required for nat/nth_prime.ma *)
 211                   aux k ms (NCicSubstitution.lift n bo))
 212           | _,NCic.Decl _ -> ms, NCic.Rel ((position (n-k) l) + k)
 213         with Failure _ -> assert false) (*Unbound variable found in delift*)
 214     | NCic.Meta (i,_) when i=n ->
 215          raise (MetaSubstFailure (lazy (Printf.sprintf (
 216            "Cannot unify the metavariable ?%d with a term that has "^^
 217            "as subterm %s in which the same metavariable "^^
 218            "occurs (occur check)") i
 219             (NCicPp.ppterm ~context ~metasenv ~subst t))))
 220     | NCic.Meta (i,l1) as orig ->
 221         (try
 222            let _,_,t,_ = NCicUtils.lookup_subst i subst in
 223            aux k ms (NCicSubstitution.subst_meta l1 t)
 224          with NCicUtils.Subst_not_found _ ->
 225            if snd l1 = NCic.Irl 0 || snd l1 = NCic.Ctx [] then ms, orig
 226            else
 227               let shift1,lc1 = l1 in
 228               let shift,lc = l in
 229               let shift = shift + k in
 230               match lc, lc1 with
 231               | NCic.Irl len, NCic.Irl len1
 232                 when shift1 + len1 < shift || shift1 > shift + len ->
 233                   let restrictions = HExtlib.list_seq 1 (len1 + 1) in
 234                   let metasenv, subst, newmeta =
 235                      restrict metasenv subst i restrictions
 236                   in
 237                   (metasenv, subst),
 238                     NCic.Meta (newmeta, (0,NCic.Irl (max 0 (k-shift1))))
 239               | NCic.Irl len, NCic.Irl len1 ->
 240                   let low_restrictions, new_shift =
 241                     if k <= shift1 && shift1 < shift then
 242                       HExtlib.list_seq 1 (shift - shift1 + 1), k
 243                     else if shift1 < k (* <= shift *) then
 244                       let save_below = k - shift1 in
 245                       HExtlib.list_seq (save_below + 1) (shift - shift1 + 1),
 246                       shift1
 247                     else [], shift1 - shift + k
 248                   in
 249                   let high_restrictions =
 250                     let last = shift + len in
 251                     let last1 = shift1 + len1 in
 252                     if last1 > last then
 253                       let high_gap = last1 - last in
 254                       HExtlib.list_seq (len1 - high_gap + 1) (len1 + 1)
 255                     else []
 256                   in
 257                   let restrictions = low_restrictions @ high_restrictions in
 258                   if restrictions = [] then
 259                     if shift = k then ms, orig
 260                     else ms, NCic.Meta (i, (new_shift, lc1))
 261                   else
 262                     let metasenv, subst, newmeta =
 263                        restrict metasenv subst i restrictions
 264                     in
 265 (* {{{
 266                   prerr_endline ("RESTRICTIONS FOR: " ^
 267                     NCicPp.ppterm ~metasenv ~subst ~context:[]
 268                     (NCic.Meta (i,l1))^" that was part of a term unified with "
 269                     ^ NCicPp.ppterm ~metasenv ~subst ~context:[] (NCic.Meta
 270                     (n,l)) ^ " ====> " ^ String.concat "," (List.map
 271                     string_of_int restrictions) ^ "\nMENV:\n" ^
 272                     NCicPp.ppmetasenv ~subst metasenv ^ "\nSUBST:\n" ^
 273                     NCicPp.ppsubst subst ~metasenv);
 274 }}} *)
 275                     let newlc_len = len1 - List.length restrictions in
 276                     let meta =
 277                        NCic.Meta(newmeta,(new_shift, NCic.Irl newlc_len))
 278                     in
 279                     assert (
 280                       let _, cctx, _ = NCicUtils.lookup_meta newmeta metasenv in
 281                       List.length cctx = newlc_len);
 282                     (metasenv, subst), meta
 283
 284               | _ ->
 285                   let lc1 = NCicUtils.expand_local_context lc1 in
 286                   let lc1 = List.map (NCicSubstitution.lift shift1) lc1 in
 287                   let rec deliftl tbr j ms = function
 288                     | [] -> ms, tbr, []
 289                     | t::tl ->
 290                         let ms, tbr, tl = deliftl tbr (j+1) ms tl in
 291                         try
 292                           let ms, t = aux k ms t in
 293                           ms, tbr, t::tl
 294                         with
 295                         | NotInTheList | MetaSubstFailure _ -> ms, j::tbr, tl
 296                   in
 297                   let (metasenv, subst), to_be_r, lc1' = deliftl [] 1 ms lc1 in
 298 (*
 299                   prerr_endline ("TO BE RESTRICTED: " ^
 300                    (String.concat "," (List.map string_of_int to_be_r)));
 301 *)
 302                   let l1 = pack_lc (0, NCic.Ctx lc1') in
 303 (*
 304                   prerr_endline ("newmeta:" ^ NCicPp.ppterm
 305                    ~metasenv ~subst ~context (NCic.Meta (999,l1)));
 306 *)
 307                   if to_be_r = [] then
 308                     (metasenv, subst),
 309                     (if lc1' = lc1 then orig else NCic.Meta (i,l1))
 310                   else
 311                     let metasenv, subst, newmeta =
 312                       restrict metasenv subst i to_be_r in
 313                     (metasenv, subst), NCic.Meta(newmeta,l1))
 314
 315     | t -> NCicUntrusted.map_term_fold_a (fun _ k -> k+1) k aux ms t
 316   in
 317    try aux 0 (metasenv,subst) t
 318    with NotInTheList ->
 319       (* This is the case where we fail even first order unification. *)
 320       (* The reason is that our delift function is weaker than first  *)
 321       (* order (in the sense of alpha-conversion). See comment above  *)
 322       (* related to the delift function.                              *)
 323       let msg = (lazy (Printf.sprintf
 324         ("Error trying to abstract %s over [%s]: the algorithm only tried to "^^
 325         "abstract over bound variables") (NCicPp.ppterm ~metasenv ~subst
 326         ~context t) (String.concat "; " (List.map (NCicPp.ppterm ~metasenv
 327         ~subst ~context) (let shift, lc = l in List.map (NCicSubstitution.lift
 328         shift) (NCicUtils.expand_local_context lc))))))
 329       in
 330       let shift, lc = l in
 331       let lc = NCicUtils.expand_local_context lc in
 332       let l = List.map (NCicSubstitution.lift shift) lc in
 333        if
 334          List.exists
 335           (fun t ->
 336                   NCicUntrusted.metas_of_term subst context t = [])
 337             l
 338        then
 339         raise (Uncertain msg)
 340        else
 341         raise (MetaSubstFailure msg)
 342 ;;
 343
 344 let mk_meta ?name metasenv context ty =
 345   let tyof = function Some s -> Some ("typeof_"^s) | None -> None in
 346   let rec mk_meta name n metasenv context = function
 347   | `WithType ty ->
 348     let len = List.length context in
 349     let menv_entry = (n, (name, context, ty)) in
 350     menv_entry :: metasenv, n, NCic.Meta (n, (0,NCic.Irl len)), ty
 351   | `Sort ->
 352     let ty = NCic.Implicit (`Typeof n) in
 353     mk_meta (tyof name) n metasenv [] (`WithType ty)
 354   | `Type ->
 355     let metasenv, _, ty, _ =
 356       mk_meta (tyof name) (newmeta ()) metasenv context `Sort in
 357     mk_meta name n metasenv context (`WithType ty)
 358   | `Term ->
 359     let metasenv, _, ty, _ =
 360       mk_meta (tyof name) (newmeta ()) metasenv context `Type in
 361     mk_meta name n metasenv context (`WithType ty)
 362   in
 363     mk_meta name (newmeta ()) metasenv context ty
 364 ;;
 365
 366 let saturate ?(delta=0) metasenv subst context ty goal_arity =
 367  assert (goal_arity >= 0);
 368   let rec aux metasenv = function
 369    | NCic.Prod (name,s,t) as ty ->
 370        let metasenv1, _, arg,_ =
 371           mk_meta ~name:name metasenv context (`WithType s) in
 372        let t, metasenv1, args, pno =
 373            aux metasenv1 (NCicSubstitution.subst arg t)
 374        in
 375        if pno + 1 = goal_arity then
 376          ty, metasenv, [], goal_arity+1
 377        else
 378          t, metasenv1, arg::args, pno+1
 379    | ty ->
 380         match NCicReduction.whd ~subst context ty ~delta with
 381         | NCic.Prod _ as ty -> aux metasenv ty
 382         | ty -> ty, metasenv, [], 0
 383   in
 384   let res, newmetasenv, arguments, _ = aux metasenv ty in
 385   res, newmetasenv, arguments
 386 ;;