1 (* Copyright (C) 2005, HELM Team.
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.
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.
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.
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,
22 * For details, see the HELM World-Wide-Web page,
23 * http://helm.cs.unibo.it/
26 (* $Id: cicCoercion.ml 7077 2006-12-05 15:44:54Z fguidi $ *)
29 let debug_print s = if debug then prerr_endline (Lazy.force s) else ()
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)
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
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));
48 | CoercDb.Uri _, CoercDb.Uri _ ->
49 debug_print (lazy ("Uri, Uri4"));
53 debug_print (lazy ("Uri, Uri3"));
60 debug_print (lazy ("Uri, Uri2"));
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) @
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) @
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
84 (fun u2 -> (s,[enrich u1 t1;uri;enrich u2 t],t))
89 | _ -> [] (* do not close in case source or target is not an indty ?? *)
92 let obj_attrs n = [`Class (`Coercion n); `Generated]
94 exception UnableToCompose
96 (* generate_composite (c2 (c1 s)) in the universe graph univ
97 both living in the same context and metasenv
99 c2 ?p2 (c1 ?p1 ?x ?s1) ?s2
102 ?pn + 1 + ?sn = count_pi n - arity n
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)
111 let rec mk_lambda_spine c namer = function
117 mk_lambda_spine (CicSubstitution.lift 1 c) namer (n-1))
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
124 let len,names = aux [] 0 t in
125 let len = len - arity in
127 (fun (n,l) x -> if n < len then n+1,l@[x] else n,l) (0,[])
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 ) ::
135 let rec create_subst_from_metas_to_rels n = function
137 | (metano, ctx, ty)::tl ->
138 (metano,(ctx,Cic.Rel n,ty)) ::
139 create_subst_from_metas_to_rels (n-1) tl
141 let split_metasenv metasenv n =
142 List.partition (fun (_,ctx,_) -> List.length ctx >= n) metasenv
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)
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
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
167 let _,_,ty = CicUtil.lookup_meta i body_metasenv in metas_of_term_and_types ty
168 with CicUtil.Meta_not_found _ -> [])
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
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)
187 S.topological_sort (List.map (fun (i,_) -> i) metas) dep
189 order_metas world metas
191 let metas_that_saturate l =
194 let metas = sorted_metas_of_term body_metasenv t in
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
201 let l_c2 = skip_appl (purge_lambdas term) in
204 HExtlib.split_nth (c2_pis - sat2 - 1) l_c2
206 Failure _ -> assert false in
209 Cic.Appl (_::l_c1)::tl -> l_c1,tl
210 | _ -> assert false in
211 let meta_to_be_coerced =
213 match List.nth l_c1 (c1_pis - sat1 - 1) with
214 | Cic.Meta (i,_) -> Some i
217 (lazy("meta_to_be_coerced: " ^ CicPp.ppterm t));
219 (lazy("c1_pis: " ^ string_of_int c1_pis ^
220 " sat1:" ^ string_of_int sat1));
223 Failure _ -> assert false
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
231 let meta2no = fst (metas_that_saturate (l_c1 @ l_c2_b @ l_c2_a)) in
234 (fun (i,ctx1,ty1) (j,ctx1,ty1) ->
235 try List.assoc i meta2no - List.assoc j meta2no
236 with Not_found -> assert false)
239 let rec position_of n acc =
242 | (i,_,_)::_ when i = n -> acc
243 | _::tl -> position_of n (acc + 1) tl
245 let saturations_res, position_of_meta_to_be_coerced =
246 match meta_to_be_coerced with
248 | Some meta_to_be_coerced ->
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
258 debug_print (lazy ("SATURATIONS: " ^ string_of_int saturations_res));
259 sorted, saturations_res, position_of_meta_to_be_coerced
262 let l = List.map (function Cic.Name s -> s | _ -> "A") l in
263 let l = List.fold_left
266 if List.exists ((=) s) acc then add' (s^"'") else s
271 let l = List.rev l in
272 Cic.Name (List.nth l (n-1))
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 =
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
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)
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
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
314 let body_metasenv, lambdas_metasenv =
315 split_metasenv metasenv (spine_len + List.length context)
317 let lambdas_metasenv =
320 List.for_all (fun (j,_,_) -> i <> j) original_metasenv)
323 let term = purge_unused_lambdas lambdas_metasenv term in
329 i <> j || List.exists (fun (j,_,_) -> j=i) original_metasenv)
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
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
348 CicRefine.insert_coercions := old_insert_coercions;
349 CicRefine.pack_coercions := old_pack_coercions;
352 c, metasenv, univ, saturationsres, arity2, cpos
355 let build_obj c univ arity =
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
365 FreshNamesGenerator.clean_dummy_dependent_types c_ty
367 let obj = Cic.Constant ("xxxx",Some c,cleaned_ty,[],obj_attrs arity) in
371 (* removes from l the coercions that are in !coercions *)
372 let filter_duplicates l coercions =
375 not (List.exists (fun (s,t,l2) ->
376 CoercDb.eq_carr s src &&
377 CoercDb.eq_carr t tgt &&
379 List.for_all2 (fun (u1,_,_) (u2,_,_) -> UriManager.eq u1 u2) l1 l2
381 | Invalid_argument "List.for_all2" ->
382 debug_print (lazy("XXX")); false)
389 (fun s x -> s ^ "_" ^ x)
390 (s ^ "_OF_" ^ t ^ "_BY" ^ string_of_int (List.length l)) l*)
394 exception ManglingFailed of string
396 let number_if_already_defined buri name l =
400 ("Unable to give an altenative name to " ^ buri ^ "/" ^ name ^ ".con"))
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
409 HLog.warn ("Uri " ^ suri ^ " already exists.");
415 if List.exists (UriManager.eq uri) l then retry ()
418 let _ = Http_getter.resolve' ~local:true ~writable:true uri in
419 if Http_getter.exists' ~local:true uri then retry () else uri
421 | Http_getter_types.Key_not_found _ -> uri
422 | Http_getter_types.Unresolvable_URI _ -> assert false
427 (* given a new coercion uri from src to tgt returns
428 * a list of (new coercion uri, coercion obj, universe graph)
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
439 (fun acc (src, l , tgt) ->
443 | (he,saturations1,arity1) :: tl ->
445 Cic.Constant ("", Some (CicUtil.term_of_uri he),
446 Cic.Sort Cic.Prop, [], obj_attrs arity1),
451 List.fold_left (fun (o,univ) (coer,saturations2,arity2) ->
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
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
464 ) (first_step, CicUniv.oblivion_ugraph) tl
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
471 number_if_already_defined baseuri name
472 (List.map (fun (_,_,u,_,_,_,_) -> u) acc)
474 let named_obj,saturations,arity,cpos =
476 | Cic.Constant (_,bo,ty,vl,attrs),saturations,arity,cpos ->
477 Cic.Constant (name,bo,ty,vl,attrs),saturations,arity,cpos
480 (src,tgt,c_uri,saturations,named_obj,arity,cpos)::acc
481 with UnableToCompose -> acc
485 with ManglingFailed s -> HLog.error s; []
488 CicCoercion.set_close_coercion_graph close_coercion_graph;;
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 =
494 generate_composite' (c1,sat1,0) (c2,sat2,0) context metasenv univ