]> matita.cs.unibo.it Git - helm.git/blob - helm/software/components/tactics/closeCoercionGraph.ml
more composites to make all happy!
[helm.git] / helm / software / components / tactics / closeCoercionGraph.ml
1 (* Copyright (C) 2005, HELM Team.
2  * 
3  * This file is part of HELM, an Hypertextual, Electronic
4  * Library of Mathematics, developed at the Computer Science
5  * Department, University of Bologna, Italy.
6  * 
7  * HELM is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  * 
12  * HELM is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with HELM; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20  * MA  02111-1307, USA.
21  * 
22  * For details, see the HELM World-Wide-Web page,
23  * http://helm.cs.unibo.it/
24  *)
25
26 (* $Id: cicCoercion.ml 7077 2006-12-05 15:44:54Z fguidi $ *)
27
28 let debug = false 
29 let debug_print s = if debug then prerr_endline (Lazy.force s) else ()
30
31 (* given the new coercion uri from src to tgt returns the list 
32  * of new coercions to create. the list elements are
33  * (source, list of coercions to follow, target)
34  *)
35 let get_closure_coercions src tgt uri coercions =
36   let enrich (uri,sat,_) tgt =
37    let arity = match tgt with CoercDb.Fun n -> n | _ -> 0 in
38     uri,sat,arity
39   in
40   let uri = enrich uri tgt in
41   let eq_carr ?exact s t = 
42     debug_print(lazy(CoercDb.string_of_carr s^" VS "^CoercDb.string_of_carr t));
43     let rc = CoercDb.eq_carr ?exact s t in
44     debug_print(lazy(string_of_bool rc));
45     rc
46   in
47   match src,tgt with
48   | CoercDb.Uri _, CoercDb.Uri _ ->
49       debug_print (lazy ("Uri, Uri4"));
50       let c_from_tgt = 
51         List.filter 
52           (fun (f,t,_) -> 
53              debug_print (lazy ("Uri, Uri3"));
54              eq_carr f tgt) 
55           coercions 
56       in
57       let c_to_src = 
58         List.filter 
59           (fun (f,t,_) -> 
60              debug_print (lazy ("Uri, Uri2"));
61              eq_carr t src) 
62           coercions 
63       in
64         (HExtlib.flatten_map 
65           (fun (_,t,ul) -> 
66              if eq_carr ~exact:true src t then [] else
67              List.map (fun u -> src,[uri; enrich u t],t) ul) c_from_tgt) @
68         (HExtlib.flatten_map 
69           (fun (s,t,ul) -> 
70              if eq_carr ~exact:true s tgt then [] else
71              List.map (fun u -> s,[enrich u t; uri],tgt) ul) c_to_src) @
72         (HExtlib.flatten_map 
73           (fun (s,t1,u1l) ->
74             HExtlib.flatten_map 
75               (fun (_,t,u2l) ->
76                 HExtlib.flatten_map
77                   (fun u1 ->
78                   debug_print (lazy ("Uri, Uri1"));
79                     if  eq_carr ~exact:true s t
80                      || eq_carr ~exact:true s tgt
81                      || eq_carr ~exact:true src t
82                     then [] else
83                     List.map 
84                       (fun u2 -> (s,[enrich u1 t1;uri;enrich u2 t],t)) 
85                       u2l)
86                   u1l) 
87               c_from_tgt) 
88           c_to_src)
89   | _ -> [] (* do not close in case source or target is not an indty ?? *)
90 ;;
91
92 let obj_attrs n = [`Class (`Coercion n); `Generated]
93
94 exception UnableToCompose
95
96 (* generate_composite (c2 (c1 s)) in the universe graph univ
97    both living in the same context and metasenv
98
99     c2 ?p2 (c1 ?p1 ?x ?s1) ?s2
100
101     where:
102      ?pn + 1 + ?sn = count_pi n - arity n
103 *)
104 let generate_composite' (c1,sat1,arity1) (c2,sat2,arity2) context metasenv univ=
105   let original_metasenv = metasenv in 
106   let c1_ty,univ = CicTypeChecker.type_of_aux' metasenv context c1 univ in
107   let c2_ty,univ = CicTypeChecker.type_of_aux' metasenv context c2 univ in
108   let rec mk_implicits = function
109     | 0 -> [] | n -> (Cic.Implicit None) :: mk_implicits (n-1)
110   in
111   let rec mk_lambda_spine c namer = function
112     | 0 -> c
113     | n -> 
114         Cic.Lambda 
115           (namer n,
116            (Cic.Implicit None), 
117            mk_lambda_spine (CicSubstitution.lift 1 c) namer (n-1))
118   in 
119   let count_pis t arity = 
120     let rec aux acc n = function
121       | Cic.Prod (name,src,tgt) -> aux (acc@[name]) (n+1) tgt
122       | _ -> n,acc
123     in
124     let len,names = aux [] 0 t in
125     let len = len - arity in
126     List.fold_left 
127       (fun (n,l) x -> if n < len then n+1,l@[x] else n,l) (0,[]) 
128       names
129   in
130   let compose c1 nc1 c2 nc2 =
131    Cic.Appl ((*CicSubstitution.lift 1*) c2 :: mk_implicits (nc2 - sat2 - 1) @
132      Cic.Appl ((*CicSubstitution.lift 1*) c1 :: mk_implicits nc1 ) ::
133      mk_implicits sat2)
134   in
135   let rec create_subst_from_metas_to_rels n = function 
136     | [] -> []
137     | (metano, ctx, ty)::tl -> 
138         (metano,(ctx,Cic.Rel n,ty)) ::
139           create_subst_from_metas_to_rels (n-1) tl
140   in
141   let split_metasenv metasenv n =
142     List.partition (fun (_,ctx,_) -> List.length ctx >= n) metasenv
143   in
144   let purge_unused_lambdas metasenv t =
145     let rec aux = function
146         | Cic.Lambda (_, Cic.Meta (i,_), t) when  
147           List.exists (fun (j,_,_) -> j = i) metasenv ->
148             aux (CicSubstitution.subst (Cic.Rel ~-100) t)
149         | Cic.Lambda (name, s, t) -> 
150             Cic.Lambda (name, s, aux t)
151         | t -> t
152     in
153     aux t
154   in
155   let order_body_menv term body_metasenv c1_pis c2_pis =
156     let rec purge_lambdas = function
157       | Cic.Lambda (_,_,t) -> purge_lambdas t
158       | t -> t
159     in
160     let skip_appl = function | Cic.Appl l -> List.tl l | _ -> assert false in
161     let rec metas_of_term_and_types t =
162       let metas = CicUtil.metas_of_term t in
163       let types = 
164        List.flatten       
165         (List.map 
166           (fun (i,_) -> try 
167             let _,_,ty = CicUtil.lookup_meta i body_metasenv in metas_of_term_and_types ty
168             with CicUtil.Meta_not_found _ -> []) 
169           metas)
170       in
171       metas @ types
172     in
173     let sorted_metas_of_term world t = 
174       let metas = metas_of_term_and_types t in
175       (* this check should be useless *)
176       let metas = List.filter (fun (i,_)->List.exists (fun (j,_,_) -> j=i) world) metas in
177       let order_metas metasenv metas = 
178         let module OT = struct type t = int let compare = Pervasives.compare end in
179         let module S = HTopoSort.Make (OT) in
180         let dep i = 
181           try 
182             let _,_,ty = List.find (fun (j,_,_) -> j=i) metasenv in
183             let metas = List.map fst (CicUtil.metas_of_term ty) in
184             HExtlib.list_uniq (List.sort Pervasives.compare metas)
185           with Not_found -> []
186         in
187           S.topological_sort (List.map (fun (i,_) -> i) metas) dep 
188       in 
189       order_metas world metas
190     in
191     let metas_that_saturate l =
192       List.fold_left 
193         (fun (acc,n) t ->
194           let metas = sorted_metas_of_term body_metasenv t in
195           let metas = 
196             List.filter (fun i -> List.for_all (fun (j,_) -> j<>i) acc) metas in
197           let metas = List.map (fun i -> i,n) metas in
198           metas @ acc, n+1)
199         ([],0) l
200     in
201     let l_c2 = skip_appl (purge_lambdas term) in
202     let l_c2_b,l_c2_a =
203      try
204       HExtlib.split_nth (c2_pis - sat2 - 1) l_c2
205      with
206       Failure _ -> assert false in
207     let l_c1,l_c2_a =
208      match l_c2_a with
209         Cic.Appl (_::l_c1)::tl -> l_c1,tl
210       | _ -> assert false in
211     let meta_to_be_coerced =
212      try
213       match List.nth l_c1 (c1_pis - sat1 - 1) with
214        | Cic.Meta (i,_) -> Some i
215        | t -> 
216           debug_print 
217             (lazy("meta_to_be_coerced: " ^ CicPp.ppterm t));
218           debug_print 
219             (lazy("c1_pis: " ^ string_of_int c1_pis ^ 
220              " sat1:" ^ string_of_int sat1));
221           None
222      with
223       Failure _ -> assert false
224     in
225     (* BIG HACK ORRIBLE:
226      * it should be (l_c2_b @ l_c1 @ l_c2_a), but in this case sym (eq_f) gets
227      *  \A,B,f,x,y,Exy and not \B,A,f,x,y,Exy
228      * as an orrible side effect, the other composites get a type lyke
229      *  \A,x,y,Exy,B,f with 2 saturations
230      *)
231     let meta2no = fst (metas_that_saturate (l_c1 @ l_c2_b @ l_c2_a)) in
232     let sorted =
233      List.sort 
234       (fun (i,ctx1,ty1) (j,ctx1,ty1) -> 
235           try List.assoc i meta2no -  List.assoc j meta2no 
236           with Not_found -> assert false) 
237       body_metasenv
238     in
239     let rec position_of n acc =
240      function
241         [] -> assert false
242       | (i,_,_)::_ when i = n -> acc
243       | _::tl -> position_of n (acc + 1) tl
244     in
245     let saturations_res, position_of_meta_to_be_coerced = 
246       match meta_to_be_coerced with
247       | None -> 0,0
248       | Some meta_to_be_coerced -> 
249           debug_print
250             (lazy ("META_TO_BE_COERCED: " ^ string_of_int meta_to_be_coerced));
251           let position_of_meta_to_be_coerced =
252             position_of meta_to_be_coerced 0 sorted in
253           debug_print (lazy ("POSITION_OF_META_TO_BE_COERCED: " ^
254             string_of_int position_of_meta_to_be_coerced));
255           List.length sorted - position_of_meta_to_be_coerced - 1,
256           position_of_meta_to_be_coerced
257     in
258     debug_print (lazy ("SATURATIONS: " ^ string_of_int saturations_res));
259     sorted, saturations_res, position_of_meta_to_be_coerced
260   in
261   let namer l n = 
262     let l = List.map (function Cic.Name s -> s | _ -> "A") l in
263     let l = List.fold_left
264       (fun acc s -> 
265         let rec add' s =
266           if List.exists ((=) s) acc then add' (s^"'") else s
267         in
268         acc@[add' s])
269       [] l
270     in
271     let l = List.rev l in 
272     Cic.Name (List.nth l (n-1))
273   in 
274   debug_print (lazy ("\nCOMPOSING"));
275   debug_print (lazy (" c1= "^CicPp.ppterm c1 ^"  :  "^ CicPp.ppterm c1_ty));
276   debug_print (lazy (" c2= "^CicPp.ppterm c2 ^"  :  "^ CicPp.ppterm c2_ty));
277   let c1_pis, names_c1 = count_pis c1_ty arity1 in 
278   let c2_pis, names_c2 = count_pis c2_ty arity2 in
279   let c = compose c1 c1_pis c2 c2_pis in
280   let spine_len = c1_pis + c2_pis in
281   let c = mk_lambda_spine c (namer (names_c1 @ names_c2)) spine_len in
282   debug_print (lazy ("COMPOSTA: " ^ CicPp.ppterm c));
283   let old_insert_coercions = !CicRefine.insert_coercions in
284   let old_pack_coercions = !CicRefine.pack_coercions in
285   let c, metasenv, univ, saturationsres, cpos =
286     try
287       CicRefine.insert_coercions := false;
288       CicRefine.pack_coercions := false;
289       let term, ty, metasenv, ugraph = 
290         CicRefine.type_of_aux' metasenv context c univ
291       in
292       debug_print(lazy("COMPOSED REFINED: "^CicPp.ppterm term));
293       debug_print(lazy("COMPOSED REFINED (pretty): "^
294         CicMetaSubst.ppterm_in_context [] ~metasenv term context));
295 (*       let metasenv = order_metasenv metasenv in *)
296 (*       debug_print(lazy("ORDERED MENV: "^CicMetaSubst.ppmetasenv [] metasenv)); *)
297       let body_metasenv, lambdas_metasenv = 
298         split_metasenv metasenv (spine_len + List.length context)
299       in
300       debug_print(lazy("B_MENV: "^CicMetaSubst.ppmetasenv [] body_metasenv));
301       debug_print(lazy("L_MENV: "^CicMetaSubst.ppmetasenv [] lambdas_metasenv));
302       let body_metasenv, saturationsres, cpos =
303        order_body_menv term body_metasenv c1_pis c2_pis
304       in
305       debug_print(lazy("ORDERED_B_MENV: "^CicMetaSubst.ppmetasenv [] body_metasenv));
306       let subst = create_subst_from_metas_to_rels spine_len body_metasenv in
307       debug_print (lazy("SUBST: "^CicMetaSubst.ppsubst body_metasenv subst));
308       let term = CicMetaSubst.apply_subst subst term in
309       let metasenv = CicMetaSubst.apply_subst_metasenv subst metasenv in
310       debug_print (lazy ("COMPOSED SUBSTITUTED: " ^ CicPp.ppterm term));
311       let term, ty, metasenv, ugraph = 
312         CicRefine.type_of_aux' metasenv context term ugraph
313       in
314       let body_metasenv, lambdas_metasenv = 
315         split_metasenv metasenv (spine_len + List.length context)
316       in
317       let lambdas_metasenv = 
318         List.filter 
319           (fun (i,_,_) -> 
320             List.for_all (fun (j,_,_) -> i <> j) original_metasenv)
321           lambdas_metasenv
322       in
323       let term = purge_unused_lambdas lambdas_metasenv term in
324       let metasenv = 
325         List.filter 
326           (fun (i,_,_) -> 
327             List.for_all 
328               (fun (j,_,_) ->
329                 i <> j || List.exists (fun (j,_,_) -> j=i) original_metasenv) 
330               lambdas_metasenv) 
331           metasenv 
332       in
333       debug_print (lazy ("####################"));
334       debug_print (lazy ("COMPOSED: " ^ CicPp.ppterm term));
335       debug_print (lazy ("SATURATIONS: " ^ string_of_int saturationsres));
336       debug_print (lazy ("MENV: "^CicMetaSubst.ppmetasenv [] metasenv));
337       debug_print (lazy ("####################"));
338       CicRefine.insert_coercions := old_insert_coercions;
339       CicRefine.pack_coercions := old_pack_coercions;
340       term, metasenv, ugraph, saturationsres, cpos
341     with
342     | CicRefine.RefineFailure s 
343     | CicRefine.Uncertain s -> debug_print s; 
344         CicRefine.insert_coercions := old_insert_coercions;
345         CicRefine.pack_coercions := old_pack_coercions;
346         raise UnableToCompose
347     | exn ->
348         CicRefine.insert_coercions := old_insert_coercions;
349         CicRefine.pack_coercions := old_pack_coercions;
350         raise exn
351   in
352   c, metasenv, univ, saturationsres, arity2, cpos
353 ;;
354
355 let build_obj c univ arity =
356   let c_ty,univ = 
357     try 
358       CicTypeChecker.type_of_aux' [] [] c univ
359     with CicTypeChecker.TypeCheckerFailure s ->
360       debug_print (lazy (Printf.sprintf "Generated composite coercion:\n%s\n%s" 
361         (CicPp.ppterm c) (Lazy.force s)));
362       raise UnableToCompose
363   in
364   let cleaned_ty =
365     FreshNamesGenerator.clean_dummy_dependent_types c_ty 
366   in
367   let obj = Cic.Constant ("xxxx",Some c,cleaned_ty,[],obj_attrs arity) in 
368     obj,univ
369 ;;
370
371 (* removes from l the coercions that are in !coercions *)
372 let filter_duplicates l coercions =
373   List.filter (
374    fun (src,l1,tgt) ->
375      not (List.exists (fun (s,t,l2) -> 
376        CoercDb.eq_carr s src && 
377        CoercDb.eq_carr t tgt &&
378        try 
379          List.for_all2 (fun (u1,_,_) (u2,_,_) -> UriManager.eq u1 u2) l1 l2
380        with
381        | Invalid_argument "List.for_all2" -> 
382            debug_print (lazy("XXX")); false)
383      coercions))
384   l
385 ;;
386
387 let mangle s t l = 
388   (*List.fold_left
389     (fun s x -> s ^ "_" ^ x)
390     (s ^ "_OF_" ^ t ^ "_BY" ^ string_of_int (List.length l)) l*)
391   s ^ "_OF_" ^ t
392 ;;
393
394 exception ManglingFailed of string 
395
396 let number_if_already_defined buri name l =
397   let err () =
398     raise 
399       (ManglingFailed 
400         ("Unable to give an altenative name to " ^ buri ^ "/" ^ name ^ ".con"))
401   in
402   let rec aux n =
403     let suffix = if n > 0 then string_of_int n else "" in
404     let suri = buri ^ "/" ^ name ^ suffix ^ ".con" in
405     let uri = UriManager.uri_of_string suri in
406     let retry () = 
407       if n < 100 then 
408         begin
409           HLog.warn ("Uri " ^ suri ^ " already exists.");
410           aux (n+1)
411         end
412       else
413         err ()
414     in
415     if List.exists (UriManager.eq uri) l then retry ()
416     else
417       try
418         let _  = Http_getter.resolve' ~local:true ~writable:true uri in
419         if Http_getter.exists' ~local:true uri then retry () else uri
420       with 
421       | Http_getter_types.Key_not_found _ -> uri
422       | Http_getter_types.Unresolvable_URI _ -> assert false
423   in
424   aux 0
425 ;;
426   
427 (* given a new coercion uri from src to tgt returns 
428  * a list of (new coercion uri, coercion obj, universe graph) 
429  *)
430 let close_coercion_graph src tgt uri saturations baseuri =
431   (* check if the coercion already exists *)
432   let coercions = CoercDb.to_list () in
433   let todo_list = get_closure_coercions src tgt (uri,saturations,0) coercions in
434   debug_print (lazy("composed " ^ string_of_int (List.length todo_list)));
435   let todo_list = filter_duplicates todo_list coercions in
436   try
437     let new_coercions = 
438       List.fold_left 
439         (fun acc (src, l , tgt) ->
440           try 
441             match l with
442             | [] -> assert false 
443             | (he,saturations1,arity1) :: tl ->
444                 let first_step = 
445                   Cic.Constant ("", Some (CicUtil.term_of_uri he),
446                     Cic.Sort Cic.Prop, [], obj_attrs arity1),
447                   saturations1,
448                   arity1,0
449                 in
450                 let o,_ = 
451                   List.fold_left (fun (o,univ) (coer,saturations2,arity2) ->
452                     match o with 
453                     | Cic.Constant (_,Some u,_,[],_),saturations1,arity1,_ ->
454                         let t, menv, univ, saturationsres, arityres, cposres = 
455                           generate_composite' (u,saturations1,arity1) 
456                             (CicUtil.term_of_uri coer,
457                              saturations2, arity2) [] [] univ
458                         in
459                         if (menv <> []) then
460                           HLog.warn "MENV non empty after composing coercions";
461                         let o,univ = build_obj t univ arityres in
462                          (o,saturationsres,arityres,cposres),univ
463                     | _ -> assert false 
464                   ) (first_step, CicUniv.oblivion_ugraph) tl
465                 in
466                 let name_src = CoercDb.string_of_carr src in
467                 let name_tgt = CoercDb.string_of_carr tgt in
468                 let by = List.map (fun u,_,_ -> UriManager.name_of_uri u) l in
469                 let name = mangle name_tgt name_src by in
470                 let c_uri = 
471                   number_if_already_defined baseuri name 
472                     (List.map (fun (_,_,u,_,_,_,_) -> u) acc) 
473                 in
474                 let named_obj,saturations,arity,cpos = 
475                   match o with
476                   | Cic.Constant (_,bo,ty,vl,attrs),saturations,arity,cpos ->
477                       Cic.Constant (name,bo,ty,vl,attrs),saturations,arity,cpos
478                   | _ -> assert false 
479                 in
480                   (src,tgt,c_uri,saturations,named_obj,arity,cpos)::acc
481           with UnableToCompose -> acc
482       ) [] todo_list
483     in
484     new_coercions
485   with ManglingFailed s -> HLog.error s; []
486 ;;
487
488 CicCoercion.set_close_coercion_graph close_coercion_graph;;
489
490 (* generate_composite (c2 (c1 s)) in the universe graph univ
491  * both living in the same context and metasenv *)
492 let generate_composite c1 c2 context metasenv univ sat1 sat2 =
493  let a,b,c,_,_,_ =
494   generate_composite' (c1,sat1,0) (c2,sat2,0) context metasenv univ
495  in
496   a,b,c
497 ;;