--- /dev/null
+(* 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
+;;
projects / helm.git / blobdiff