X-Git-Url: http://matita.cs.unibo.it/gitweb/?p=helm.git;a=blobdiff_plain;f=components%2Ftactics%2FcloseCoercionGraph.ml;fp=components%2Ftactics%2FcloseCoercionGraph.ml;h=7ed3c36e6b86d24d4a46b753a750e11597d919c0;hp=0000000000000000000000000000000000000000;hb=f61af501fb4608cc4fb062a0864c774e677f0d76;hpb=58ae1809c352e71e7b5530dc41e2bfc834e1aef1 diff --git a/components/tactics/closeCoercionGraph.ml b/components/tactics/closeCoercionGraph.ml new file mode 100644 index 000000000..7ed3c36e6 --- /dev/null +++ b/components/tactics/closeCoercionGraph.ml @@ -0,0 +1,497 @@ +(* Copyright (C) 2005, HELM Team. + * + * This file is part of HELM, an Hypertextual, Electronic + * Library of Mathematics, developed at the Computer Science + * Department, University of Bologna, Italy. + * + * HELM is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * HELM is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with HELM; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + * + * For details, see the HELM World-Wide-Web page, + * http://helm.cs.unibo.it/ + *) + +(* $Id: cicCoercion.ml 7077 2006-12-05 15:44:54Z fguidi $ *) + +let debug = false +let debug_print s = if debug then prerr_endline (Lazy.force s) else () + +(* given the new coercion uri from src to tgt returns the list + * of new coercions to create. the list elements are + * (source, list of coercions to follow, target) + *) +let get_closure_coercions src tgt uri coercions = + let enrich (uri,sat) tgt = + let arity = match tgt with CoercDb.Fun n -> n | _ -> 0 in + uri,sat,arity + in + let uri = enrich uri tgt in + let eq_carr ?exact s t = + debug_print (lazy(CoercDb.name_of_carr s^" VS "^CoercDb.name_of_carr t)); + try + let rc = CoercDb.eq_carr ?exact s t in + debug_print(lazy(string_of_bool rc)); + rc + with + | CoercDb.EqCarrNotImplemented _ | CoercDb.EqCarrOnNonMetaClosed -> + debug_print (lazy("false")); + false + in + match src,tgt with + | CoercDb.Uri _, CoercDb.Uri _ -> + debug_print (lazy ("Uri, Uri4")); + let c_from_tgt = + List.filter + (fun (f,t,_) -> + + debug_print (lazy ("Uri, Uri3")); + eq_carr f tgt (*&& not (eq_carr t src)*)) + coercions + in + let c_to_src = + List.filter + (fun (f,t,_) -> + + debug_print (lazy ("Uri, Uri2")); + eq_carr t src (*&& not (eq_carr f tgt)*)) + coercions + in + (HExtlib.flatten_map + (fun (_,t,ul) -> + if eq_carr ~exact:true src t then [] else + List.map (fun u -> src,[uri; enrich u t],t) ul) c_from_tgt) @ + (HExtlib.flatten_map + (fun (s,t,ul) -> + if eq_carr ~exact:true s tgt then [] else + List.map (fun u -> s,[enrich u t; uri],tgt) ul) c_to_src) @ + (HExtlib.flatten_map + (fun (s,t1,u1l) -> + HExtlib.flatten_map + (fun (_,t,u2l) -> + HExtlib.flatten_map + (fun u1 -> + debug_print (lazy ("Uri, Uri1")); + if eq_carr ~exact:true s t + || eq_carr ~exact:true s tgt + || eq_carr ~exact:true src t + then [] else + List.map + (fun u2 -> (s,[enrich u1 t1;uri;enrich u2 t],t)) + u2l) + u1l) + c_from_tgt) + c_to_src) + | _ -> [] (* do not close in case source or target is not an indty ?? *) +;; + +let obj_attrs n = [`Class (`Coercion n); `Generated] + +exception UnableToCompose + +(* generate_composite (c2 (c1 s)) in the universe graph univ + both living in the same context and metasenv + + c2 ?p2 (c1 ?p1 ?x ?s1) ?s2 + + where: + ?pn + 1 + ?sn = count_pi n - arity n +*) +let generate_composite' (c1,sat1,arity1) (c2,sat2,arity2) context metasenv univ= + let original_metasenv = metasenv in + let c1_ty,univ = CicTypeChecker.type_of_aux' metasenv context c1 univ in + let c2_ty,univ = CicTypeChecker.type_of_aux' metasenv context c2 univ in + let rec mk_implicits = function + | 0 -> [] | n -> (Cic.Implicit None) :: mk_implicits (n-1) + in + let rec mk_lambda_spine c namer = function + | 0 -> c + | n -> + Cic.Lambda + (namer n, + (Cic.Implicit None), + mk_lambda_spine (CicSubstitution.lift 1 c) namer (n-1)) + in + let count_pis t arity = + let rec aux acc n = function + | Cic.Prod (name,src,tgt) -> aux (acc@[name]) (n+1) tgt + | _ -> n,acc + in + let len,names = aux [] 0 t in + let len = len - arity in + List.fold_left + (fun (n,l) x -> if n < len then n+1,l@[x] else n,l) (0,[]) + names + in + let compose c1 nc1 c2 nc2 = + Cic.Appl ((*CicSubstitution.lift 1*) c2 :: mk_implicits (nc2 - sat2 - 1) @ + Cic.Appl ((*CicSubstitution.lift 1*) c1 :: mk_implicits nc1 ) :: + mk_implicits sat2) + in + let rec create_subst_from_metas_to_rels n = function + | [] -> [] + | (metano, ctx, ty)::tl -> + (metano,(ctx,Cic.Rel n,ty)) :: + create_subst_from_metas_to_rels (n-1) tl + in + let split_metasenv metasenv n = + List.partition (fun (_,ctx,_) -> List.length ctx >= n) metasenv + in + let purge_unused_lambdas metasenv t = + let rec aux = function + | Cic.Lambda (_, Cic.Meta (i,_), t) when + List.exists (fun (j,_,_) -> j = i) metasenv -> + aux (CicSubstitution.subst (Cic.Rel ~-100) t) + | Cic.Lambda (name, s, t) -> + Cic.Lambda (name, s, aux t) + | t -> t + in + aux t + in + let order_body_menv term body_metasenv c1_pis c2_pis = + let rec purge_lambdas = function + | Cic.Lambda (_,_,t) -> purge_lambdas t + | t -> t + in + let skip_appl = function | Cic.Appl l -> List.tl l | _ -> assert false in + let rec metas_of_term_and_types t = + let metas = CicUtil.metas_of_term t in + let types = + List.flatten + (List.map + (fun (i,_) -> try + let _,_,ty = CicUtil.lookup_meta i body_metasenv in metas_of_term_and_types ty + with CicUtil.Meta_not_found _ -> []) + metas) + in + metas @ types + in + let sorted_metas_of_term world t = + let metas = metas_of_term_and_types t in + (* this check should be useless *) + let metas = List.filter (fun (i,_)->List.exists (fun (j,_,_) -> j=i) world) metas in + let order_metas metasenv metas = + let module OT = struct type t = int let compare = Pervasives.compare end in + let module S = HTopoSort.Make (OT) in + let dep i = + try + let _,_,ty = List.find (fun (j,_,_) -> j=i) metasenv in + let metas = List.map fst (CicUtil.metas_of_term ty) in + HExtlib.list_uniq (List.sort Pervasives.compare metas) + with Not_found -> [] + in + S.topological_sort (List.map (fun (i,_) -> i) metas) dep + in + order_metas world metas + in + let metas_that_saturate l = + List.fold_left + (fun (acc,n) t -> + let metas = sorted_metas_of_term body_metasenv t in + let metas = + List.filter (fun i -> List.for_all (fun (j,_) -> j<>i) acc) metas in + let metas = List.map (fun i -> i,n) metas in + metas @ acc, n+1) + ([],0) l + in + let l_c2 = skip_appl (purge_lambdas term) in + let l_c2_b,l_c2_a = + try + HExtlib.split_nth (c2_pis - sat2 - 1) l_c2 + with + Failure _ -> assert false in + let l_c1,l_c2_a = + match l_c2_a with + Cic.Appl (_::l_c1)::tl -> l_c1,tl + | _ -> assert false in + let meta_to_be_coerced = + try + match List.nth l_c1 (c1_pis - sat1 - 1) with + | Cic.Meta (i,_) -> Some i + | t -> + debug_print + (lazy("meta_to_be_coerced: " ^ CicPp.ppterm t)); + debug_print + (lazy("c1_pis: " ^ string_of_int c1_pis ^ + " sat1:" ^ string_of_int sat1)); + None + with + Failure _ -> assert false + in + (* BIG HACK ORRIBLE: + * it should be (l_c2_b @ l_c1 @ l_c2_a), but in this case sym (eq_f) gets + * \A,B,f,x,y,Exy and not \B,A,f,x,y,Exy + * as an orrible side effect, the other composites get a type lyke + * \A,x,y,Exy,B,f with 2 saturations + *) + let meta2no = fst (metas_that_saturate (l_c1 @ l_c2_b @ l_c2_a)) in + let sorted = + List.sort + (fun (i,ctx1,ty1) (j,ctx1,ty1) -> + try List.assoc i meta2no - List.assoc j meta2no + with Not_found -> assert false) + body_metasenv + in + let rec position_of n acc = + function + [] -> assert false + | (i,_,_)::_ when i = n -> acc + | _::tl -> position_of n (acc + 1) tl + in + let saturations_res = + match meta_to_be_coerced with + | None -> 0 + | Some meta_to_be_coerced -> + debug_print + (lazy ("META_TO_BE_COERCED: " ^ string_of_int meta_to_be_coerced)); + let position_of_meta_to_be_coerced = + position_of meta_to_be_coerced 0 sorted in + debug_print (lazy ("POSITION_OF_META_TO_BE_COERCED: " ^ + string_of_int position_of_meta_to_be_coerced)); + List.length sorted - position_of_meta_to_be_coerced - 1 + in + debug_print (lazy ("SATURATIONS: " ^ string_of_int saturations_res)); + sorted, saturations_res + in + let namer l n = + let l = List.map (function Cic.Name s -> s | _ -> "A") l in + let l = List.fold_left + (fun acc s -> + let rec add' s = + if List.exists ((=) s) acc then add' (s^"'") else s + in + acc@[add' s]) + [] l + in + let l = List.rev l in + Cic.Name (List.nth l (n-1)) + in + debug_print (lazy ("\nCOMPOSING")); + debug_print (lazy (" c1= "^CicPp.ppterm c1 ^" : "^ CicPp.ppterm c1_ty)); + debug_print (lazy (" c2= "^CicPp.ppterm c2 ^" : "^ CicPp.ppterm c2_ty)); + let c1_pis, names_c1 = count_pis c1_ty arity1 in + let c2_pis, names_c2 = count_pis c2_ty arity2 in + let c = compose c1 c1_pis c2 c2_pis in + let spine_len = c1_pis + c2_pis in + let c = mk_lambda_spine c (namer (names_c1 @ names_c2)) spine_len in + debug_print (lazy ("COMPOSTA: " ^ CicPp.ppterm c)); + let old_insert_coercions = !CicRefine.insert_coercions in + let c, metasenv, univ, saturationsres = + try + CicRefine.insert_coercions := false; + let term, ty, metasenv, ugraph = + CicRefine.type_of_aux' metasenv context c univ + in + debug_print(lazy("COMPOSED REFINED: "^CicPp.ppterm term)); + debug_print(lazy("COMPOSED REFINED (pretty): "^ + CicMetaSubst.ppterm_in_context [] ~metasenv term context)); +(* let metasenv = order_metasenv metasenv in *) +(* debug_print(lazy("ORDERED MENV: "^CicMetaSubst.ppmetasenv [] metasenv)); *) + let body_metasenv, lambdas_metasenv = + split_metasenv metasenv (spine_len + List.length context) + in + debug_print(lazy("B_MENV: "^CicMetaSubst.ppmetasenv [] body_metasenv)); + debug_print(lazy("L_MENV: "^CicMetaSubst.ppmetasenv [] lambdas_metasenv)); + let body_metasenv, saturationsres = + order_body_menv term body_metasenv c1_pis c2_pis + in + debug_print(lazy("ORDERED_B_MENV: "^CicMetaSubst.ppmetasenv [] body_metasenv)); + let subst = create_subst_from_metas_to_rels spine_len body_metasenv in + debug_print (lazy("SUBST: "^CicMetaSubst.ppsubst body_metasenv subst)); + let term = CicMetaSubst.apply_subst subst term in + let metasenv = CicMetaSubst.apply_subst_metasenv subst metasenv in + debug_print (lazy ("COMPOSED SUBSTITUTED: " ^ CicPp.ppterm term)); + let term, ty, metasenv, ugraph = + CicRefine.type_of_aux' metasenv context term ugraph + in + let body_metasenv, lambdas_metasenv = + split_metasenv metasenv (spine_len + List.length context) + in + let lambdas_metasenv = + List.filter + (fun (i,_,_) -> + List.for_all (fun (j,_,_) -> i <> j) original_metasenv) + lambdas_metasenv + in + let term = purge_unused_lambdas lambdas_metasenv term in + let metasenv = + List.filter + (fun (i,_,_) -> + List.for_all + (fun (j,_,_) -> + i <> j || List.exists (fun (j,_,_) -> j=i) original_metasenv) + lambdas_metasenv) + metasenv + in + debug_print (lazy ("####################")); + debug_print (lazy ("COMPOSED: " ^ CicPp.ppterm term)); + debug_print (lazy ("SATURATIONS: " ^ string_of_int saturationsres)); + debug_print (lazy ("MENV: "^CicMetaSubst.ppmetasenv [] metasenv)); + debug_print (lazy ("####################")); + CicRefine.insert_coercions := old_insert_coercions; + term, metasenv, ugraph, saturationsres + with + | CicRefine.RefineFailure s + | CicRefine.Uncertain s -> debug_print s; + CicRefine.insert_coercions := old_insert_coercions; + raise UnableToCompose + | exn -> + CicRefine.insert_coercions := old_insert_coercions; + raise exn + in + c, metasenv, univ, saturationsres, arity2 +;; + +let build_obj c univ arity = + let c_ty,univ = + try + CicTypeChecker.type_of_aux' [] [] c univ + with CicTypeChecker.TypeCheckerFailure s -> + debug_print (lazy (Printf.sprintf "Generated composite coercion:\n%s\n%s" + (CicPp.ppterm c) (Lazy.force s))); + raise UnableToCompose + in + let cleaned_ty = + FreshNamesGenerator.clean_dummy_dependent_types c_ty + in + let obj = Cic.Constant ("xxxx",Some c,cleaned_ty,[],obj_attrs arity) in + obj,univ +;; + +(* removes from l the coercions that are in !coercions *) +let filter_duplicates l coercions = + List.filter ( + fun (src,l1,tgt) -> + not (List.exists (fun (s,t,l2) -> + CoercDb.eq_carr s src && + CoercDb.eq_carr t tgt && + try + List.for_all2 (fun (u1,_,_) (u2,_) -> UriManager.eq u1 u2) l1 l2 + with + | Invalid_argument "List.for_all2" -> debug_print (lazy("XXX")); false) + coercions)) + l + +let mangle s t l = + (*List.fold_left + (fun s x -> s ^ "_" ^ x) + (s ^ "_OF_" ^ t ^ "_BY" ^ string_of_int (List.length l)) l*) + s ^ "_OF_" ^ t +;; + +exception ManglingFailed of string + +let number_if_already_defined buri name l = + let err () = + raise + (ManglingFailed + ("Unable to give an altenative name to " ^ buri ^ "/" ^ name ^ ".con")) + in + let rec aux n = + let suffix = if n > 0 then string_of_int n else "" in + let suri = buri ^ "/" ^ name ^ suffix ^ ".con" in + let uri = UriManager.uri_of_string suri in + let retry () = + if n < 100 then + begin + HLog.warn ("Uri " ^ suri ^ " already exists."); + aux (n+1) + end + else + err () + in + if List.exists (UriManager.eq uri) l then retry () + else + try + let _ = Http_getter.resolve' ~local:true ~writable:true uri in + if Http_getter.exists' ~local:true uri then retry () else uri + with + | Http_getter_types.Key_not_found _ -> uri + | Http_getter_types.Unresolvable_URI _ -> assert false + in + aux 0 +;; + +(* given a new coercion uri from src to tgt returns + * a list of (new coercion uri, coercion obj, universe graph) + *) +let close_coercion_graph src tgt uri saturations baseuri = + (* check if the coercion already exists *) + let coercions = CoercDb.to_list () in + let todo_list = get_closure_coercions src tgt (uri,saturations) coercions in + debug_print (lazy("composed " ^ string_of_int (List.length todo_list))); + let todo_list = filter_duplicates todo_list coercions in + try + let new_coercions = + List.fold_left + (fun acc (src, l , tgt) -> + try + (match l with + | [] -> assert false + | (he,saturations1,arity1) :: tl -> + let first_step = + Cic.Constant ("", + Some (CoercDb.term_of_carr (CoercDb.Uri he)), + Cic.Sort Cic.Prop, [], obj_attrs arity1), + saturations1, + arity1 + in + let o,_ = + List.fold_left (fun (o,univ) (coer,saturations2,arity2) -> + match o with + | Cic.Constant (_,Some u,_,[],_),saturations1,arity1 -> + let t, menv, univ, saturationsres, arityres = + generate_composite' (u,saturations1,arity1) + (CoercDb.term_of_carr (CoercDb.Uri coer), + saturations2, arity2) [] [] univ + in + if (menv = []) then + HLog.warn "MENV non empty after composing coercions"; + let o,univ = build_obj t univ arityres in + (o,saturationsres,arityres),univ + | _ -> assert false + ) (first_step, CicUniv.empty_ugraph) tl + in + let name_src = CoercDb.name_of_carr src in + let name_tgt = CoercDb.name_of_carr tgt in + let by = List.map (fun u,_,_ -> UriManager.name_of_uri u) l in + let name = mangle name_tgt name_src by in + let c_uri = + number_if_already_defined baseuri name + (List.map (fun (_,_,u,_,_,_) -> u) acc) + in + let named_obj,saturations,arity = + match o with + | Cic.Constant (_,bo,ty,vl,attrs),saturations,arity -> + Cic.Constant (name,bo,ty,vl,attrs),saturations,arity + | _ -> assert false + in + (src,tgt,c_uri,saturations,named_obj,arity))::acc + with UnableToCompose -> acc + ) [] todo_list + in + new_coercions + with ManglingFailed s -> HLog.error s; [] +;; + +CicCoercion.set_close_coercion_graph close_coercion_graph;; + +(* generate_composite (c2 (c1 s)) in the universe graph univ + * both living in the same context and metasenv *) +let generate_composite c1 c2 context metasenv univ sat1 sat2 = + let a,b,c,_,_ = + generate_composite' (c1,sat1,0) (c2,sat2,0) context metasenv univ + in + a,b,c +;;