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. hte list elements are
33 * (source, list of coercions to follow, target)
35 let get_closure_coercions src tgt uri coercions =
40 | CoercDb.EqCarrNotImplemented _ | CoercDb.EqCarrOnNonMetaClosed -> false
43 | CoercDb.Uri _, CoercDb.Uri _ ->
46 (fun (f,t,_) -> eq_carr f tgt (*&& not (eq_carr t src)*))
51 (fun (f,t,_) -> eq_carr t src (*&& not (eq_carr f tgt)*))
55 (fun (_,t,ul) -> List.map (fun u -> src,[uri; u],t) ul) c_from_tgt) @
57 (fun (s,_,ul) -> List.map (fun u -> s,[u; uri],tgt) ul) c_to_src) @
65 (fun u2 -> (s,[u1;uri;u2],t))
70 | _ -> [] (* do not close in case source or target is not an indty ?? *)
73 let obj_attrs n = [`Class (`Coercion n); `Generated]
75 exception UnableToCompose
77 (* generate_composite (c2 (c1 s)) in the universe graph univ
78 * both living in the same context and metasenv *)
79 let generate_composite c1 c2 context metasenv univ arity last_lam_with_inn_arg =
80 let module RT = RefinementTool in
81 let original_metasenv = metasenv in
82 let c1_ty,univ = CicTypeChecker.type_of_aux' metasenv context c1 univ in
83 let c2_ty,univ = CicTypeChecker.type_of_aux' metasenv context c2 univ in
84 let rec mk_implicits = function
85 | 0 -> [] | n -> (Cic.Implicit None) :: mk_implicits (n-1)
87 let rec mk_lambda_spline c namer = function
93 mk_lambda_spline (CicSubstitution.lift 1 c) namer (n-1))
95 let count_saturations_needed t arity =
96 let rec aux acc n = function
97 | Cic.Prod (name,src, ((Cic.Prod _) as t)) ->
98 aux (acc@[name]) (n+1) t
101 let len,names = aux [] 0 t in
102 let len = len - arity in
104 (fun (n,l) x -> if n < len then n+1,l@[x] else n,l) (0,[])
107 let compose c1 nc1 c2 nc2 =
109 (Cic.Name "x", (Cic.Implicit None),
110 (Cic.Appl ( CicSubstitution.lift 1 c2 :: mk_implicits nc2 @
111 [ Cic.Appl ( CicSubstitution.lift 1 c1 :: mk_implicits nc1 @
112 [if last_lam_with_inn_arg then Cic.Rel 1 else Cic.Implicit None])
116 let order_metasenv metasenv =
117 let module OT = struct type t = int let compare = Pervasives.compare end in
118 let module S = HTopoSort.Make (OT) in
120 let _,_,ty = List.find (fun (j,_,_) -> j=i) metasenv in
121 let metas = List.map fst (CicUtil.metas_of_term ty) in
122 HExtlib.list_uniq (List.sort Pervasives.compare metas)
125 S.topological_sort (List.map (fun (i,_,_) -> i) metasenv) dep
127 List.map (fun i -> List.find (fun (j,_,_) -> i=j) metasenv) om
130 let rec create_subst_from_metas_to_rels n = function
132 | (metano, ctx, ty)::tl ->
133 (metano,(ctx,Cic.Rel (n+1),ty)) ::
134 create_subst_from_metas_to_rels (n-1) tl
136 let split_metasenv metasenv n =
137 List.partition (fun (_,ctx,_) -> List.length ctx > n) metasenv
139 let purge_unused_lambdas metasenv t =
140 let rec aux = function
141 | Cic.Lambda (_, Cic.Meta (i,_), t) when
142 List.exists (fun (j,_,_) -> j = i) metasenv ->
143 aux (CicSubstitution.subst (Cic.Rel ~-100) t)
144 | Cic.Lambda (name, s, t) ->
145 Cic.Lambda (name, s, aux t)
150 let order_body_menv term body_metasenv =
151 let rec purge_lambdas = function
152 | Cic.Lambda (_,_,t) -> purge_lambdas t
155 let skip_appl = function | Cic.Appl l -> List.tl l | _ -> assert false in
156 let metas_that_saturate l =
159 let metas = CicUtil.metas_of_term t in
160 let metas = List.map fst metas in
163 (fun i -> List.for_all (fun (j,_) -> j<>i) acc)
166 let metas = List.map (fun i -> i,n) metas in
170 let l_c2 = skip_appl (purge_lambdas term) in
172 match HExtlib.list_last l_c2 with
173 | Cic.Appl l -> List.tl l
176 (* i should cut off the laet elem of l_c2 *)
177 let meta2no = fst (metas_that_saturate (l_c1 @ l_c2)) in
179 (fun (i,ctx1,ty1) (j,ctx1,ty1) ->
180 try List.assoc i meta2no - List.assoc j meta2no
181 with Not_found -> assert false)
185 let l = List.map (function Cic.Name s -> s | _ -> "A") l in
186 let l = List.fold_left
189 if List.exists ((=) s) acc then add' (s^"'") else s
194 let l = List.rev l in
195 Cic.Name (List.nth l (n-1))
197 debug_print (lazy ("\nCOMPOSING"));
198 debug_print (lazy (" c1= "^CicPp.ppterm c1 ^" : "^ CicPp.ppterm c1_ty));
199 debug_print (lazy (" c2= "^CicPp.ppterm c2 ^" : "^ CicPp.ppterm c2_ty));
200 let saturations_for_c1, names_c1 = count_saturations_needed c1_ty 0 in
201 let saturations_for_c2, names_c2 = count_saturations_needed c2_ty arity in
202 let c = compose c1 saturations_for_c1 c2 saturations_for_c2 in
203 let spline_len = saturations_for_c1 + saturations_for_c2 in
204 let c = mk_lambda_spline c (namer (names_c1 @ names_c2)) spline_len in
205 debug_print (lazy ("COMPOSTA: " ^ CicPp.ppterm c));
206 let c, metasenv, univ =
208 let term, ty, metasenv, ugraph =
209 CicRefine.type_of_aux' metasenv context c univ
211 debug_print(lazy("COMPOSED REFINED: "^CicPp.ppterm term));
212 (* let metasenv = order_metasenv metasenv in *)
213 (* debug_print(lazy("ORDERED MENV: "^CicMetaSubst.ppmetasenv [] metasenv)); *)
214 let body_metasenv, lambdas_metasenv =
215 split_metasenv metasenv (spline_len + List.length context)
217 debug_print(lazy("B_MENV: "^CicMetaSubst.ppmetasenv [] body_metasenv));
218 debug_print(lazy("L_MENV: "^CicMetaSubst.ppmetasenv [] lambdas_metasenv));
219 let body_metasenv = order_body_menv term body_metasenv in
220 debug_print(lazy("ORDERED_B_MENV: "^CicMetaSubst.ppmetasenv [] body_metasenv));
221 let subst = create_subst_from_metas_to_rels spline_len body_metasenv in
222 debug_print (lazy("SUBST: "^CicMetaSubst.ppsubst body_metasenv subst));
223 let term = CicMetaSubst.apply_subst subst term in
224 let metasenv = CicMetaSubst.apply_subst_metasenv subst metasenv in
225 debug_print (lazy ("COMPOSED SUBSTITUTED: " ^ CicPp.ppterm term));
226 let term, ty, metasenv, ugraph =
227 CicRefine.type_of_aux' metasenv context term ugraph
229 let body_metasenv, lambdas_metasenv =
230 split_metasenv metasenv (spline_len + List.length context)
232 let term = purge_unused_lambdas lambdas_metasenv term in
238 i <> j || List.exists (fun (j,_,_) -> j=i) original_metasenv)
242 debug_print (lazy ("COMPOSED: " ^ CicPp.ppterm term));
243 debug_print(lazy("MENV: "^CicMetaSubst.ppmetasenv [] metasenv));
244 term, metasenv, ugraph
246 | CicRefine.RefineFailure s
247 | CicRefine.Uncertain s -> debug_print s;
248 raise UnableToCompose
253 let build_obj c univ arity =
256 CicTypeChecker.type_of_aux' [] [] c univ
257 with CicTypeChecker.TypeCheckerFailure s ->
258 debug_print (lazy (Printf.sprintf "Generated composite coercion:\n%s\n%s"
259 (CicPp.ppterm c) (Lazy.force s)));
260 raise UnableToCompose
263 FreshNamesGenerator.clean_dummy_dependent_types c_ty
265 let obj = Cic.Constant ("xxxx",Some c,cleaned_ty,[],obj_attrs arity) in
269 (* removes from l the coercions that are in !coercions *)
270 let filter_duplicates l coercions =
273 not (List.exists (fun (s,t,l2) ->
274 CoercDb.eq_carr s src &&
275 CoercDb.eq_carr t tgt &&
277 List.for_all2 (fun u1 u2 -> UriManager.eq u1 u2) l1 l2
279 | Invalid_argument "List.for_all2" -> false)
285 (fun s x -> s ^ "_" ^ x)
286 (s ^ "_OF_" ^ t ^ "_BY" ^ string_of_int (List.length l)) l*)
290 exception ManglingFailed of string
292 let number_if_already_defined buri name l =
296 ("Unable to give an altenative name to " ^ buri ^ "/" ^ name ^ ".con"))
299 let suffix = if n > 0 then string_of_int n else "" in
300 let suri = buri ^ "/" ^ name ^ suffix ^ ".con" in
301 let uri = UriManager.uri_of_string suri in
305 HLog.warn ("Uri " ^ suri ^ " already exists.");
311 if List.exists (UriManager.eq uri) l then retry ()
314 let _ = Http_getter.resolve' ~writable:true uri in
315 if Http_getter.exists' uri then retry () else uri
317 | Http_getter_types.Key_not_found _ -> uri
318 | Http_getter_types.Unresolvable_URI _ -> assert false
323 (* given a new coercion uri from src to tgt returns
324 * a list of (new coercion uri, coercion obj, universe graph)
326 let close_coercion_graph src tgt uri baseuri =
327 (* check if the coercion already exists *)
328 let coercions = CoercDb.to_list () in
329 let todo_list = get_closure_coercions src tgt uri coercions in
330 let todo_list = filter_duplicates todo_list coercions in
334 (fun acc (src, l , tgt) ->
339 let arity = match tgt with CoercDb.Fun n -> n | _ -> 0 in
342 Some (CoercDb.term_of_carr (CoercDb.Uri he)),
343 Cic.Sort Cic.Prop, [], obj_attrs arity)
346 List.fold_left (fun (o,univ) coer ->
348 | Cic.Constant (_,Some c,_,[],_) ->
351 (CoercDb.term_of_carr (CoercDb.Uri coer))
352 [] [] univ arity true
356 "MENV non empty after composing coercions";
357 build_obj t univ arity
359 ) (first_step, CicUniv.empty_ugraph) tl
361 let name_src = CoercDb.name_of_carr src in
362 let name_tgt = CoercDb.name_of_carr tgt in
363 let by = List.map UriManager.name_of_uri l in
364 let name = mangle name_tgt name_src by in
366 number_if_already_defined baseuri name
367 (List.map (fun (_,_,u,_) -> u) acc)
371 | Cic.Constant (_,bo,ty,vl,attrs) ->
372 Cic.Constant (name,bo,ty,vl,attrs)
375 (src,tgt,c_uri,named_obj))::acc
376 with UnableToCompose -> acc
380 with ManglingFailed s -> HLog.error s; []
383 CicCoercion.set_close_coercion_graph close_coercion_graph;;