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