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