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. hte list elements are
  33  * (source, list of coercions to follow, target)
  34  *)
  35 let get_closure_coercions src tgt uri coercions =
  36   let eq_carr s t =
  37     try
  38       CoercDb.eq_carr s t
  39     with
  40     | CoercDb.EqCarrNotImplemented _ | CoercDb.EqCarrOnNonMetaClosed -> false
  41   in
  42   match src,tgt with
  43   | CoercDb.Uri _, CoercDb.Uri _ ->
  44       let c_from_tgt =
  45         List.filter
  46           (fun (f,t,_) -> eq_carr f tgt (*&& not (eq_carr t src)*))
  47           coercions
  48       in
  49       let c_to_src =
  50         List.filter
  51           (fun (f,t,_) -> eq_carr t src (*&& not (eq_carr f tgt)*))
  52           coercions
  53       in
  54         (HExtlib.flatten_map
  55           (fun (_,t,ul) ->
  56              if CoercDb.eq_carr ~exact:true src t then [] else
  57              List.map (fun u -> src,[uri; u],t) ul) c_from_tgt) @
  58         (HExtlib.flatten_map
  59           (fun (s,_,ul) ->
  60              if CoercDb.eq_carr ~exact:true s tgt then [] else
  61              List.map (fun u -> s,[u; uri],tgt) ul) c_to_src) @
  62         (HExtlib.flatten_map
  63           (fun (s,_,u1l) ->
  64             HExtlib.flatten_map
  65               (fun (_,t,u2l) ->
  66                 HExtlib.flatten_map
  67                   (fun u1 ->
  68                     if CoercDb.eq_carr ~exact:true s t then [] else
  69                     List.map
  70                       (fun u2 -> (s,[u1;uri;u2],t))
  71                       u2l)
  72                   u1l)
  73               c_from_tgt)
  74           c_to_src)
  75   | _ -> [] (* do not close in case source or target is not an indty ?? *)
  76 ;;
  77
  78 let obj_attrs n = [`Class (`Coercion n); `Generated]
  79
  80 exception UnableToCompose
  81
  82 (* generate_composite (c2 (c1 s)) in the universe graph univ
  83  * both living in the same context and metasenv *)
  84 let generate_composite' (c1,sat1) (c2,sat2) context metasenv univ arity
  85  last_lam_with_inn_arg
  86 =
  87 assert (sat1 = 0);
  88 assert (sat2 = 0);
  89 let saturationsres = 0 in
  90   let original_metasenv = metasenv in
  91   let c1_ty,univ = CicTypeChecker.type_of_aux' metasenv context c1 univ in
  92   let c2_ty,univ = CicTypeChecker.type_of_aux' metasenv context c2 univ in
  93   let rec mk_implicits = function
  94     | 0 -> [] | n -> (Cic.Implicit None) :: mk_implicits (n-1)
  95   in
  96   let rec mk_lambda_spine c namer = function
  97     | 0 -> c
  98     | n ->
  99         Cic.Lambda
 100           (namer n,
 101            (Cic.Implicit None),
 102            mk_lambda_spine (CicSubstitution.lift 1 c) namer (n-1))
 103   in
 104   let count_saturations_needed t arity =
 105     let rec aux acc n = function
 106       | Cic.Prod (name,src, ((Cic.Prod _) as t)) ->
 107           aux (acc@[name]) (n+1) t
 108       | _ -> n,acc
 109     in
 110     let len,names = aux [] 0 t in
 111     let len = len - arity in
 112     List.fold_left
 113       (fun (n,l) x -> if n < len then n+1,l@[x] else n,l) (0,[])
 114       names
 115   in
 116   let compose c1 nc1 c2 nc2 =
 117     Cic.Lambda
 118       (Cic.Name "x", (Cic.Implicit (Some `Type)),
 119           (Cic.Appl (  CicSubstitution.lift 1 c2 :: mk_implicits nc2 @
 120             [ Cic.Appl (  CicSubstitution.lift 1 c1 :: mk_implicits nc1 @
 121              [if last_lam_with_inn_arg then Cic.Rel 1 else Cic.Implicit None])
 122             ])))
 123   in
 124 (*
 125   let order_metasenv metasenv =
 126     let module OT = struct type t = int let compare = Pervasives.compare end in
 127     let module S = HTopoSort.Make (OT) in
 128     let dep i =
 129       let _,_,ty = List.find (fun (j,_,_) -> j=i) metasenv in
 130       let metas = List.map fst (CicUtil.metas_of_term ty) in
 131       HExtlib.list_uniq (List.sort Pervasives.compare metas)
 132     in
 133     let om =
 134       S.topological_sort (List.map (fun (i,_,_) -> i) metasenv) dep
 135     in
 136     List.map (fun i -> List.find (fun (j,_,_) -> i=j) metasenv) om
 137   in
 138 *)
 139   let rec create_subst_from_metas_to_rels n = function
 140     | [] -> []
 141     | (metano, ctx, ty)::tl ->
 142         (metano,(ctx,Cic.Rel (n+1),ty)) ::
 143           create_subst_from_metas_to_rels (n-1) tl
 144   in
 145   let split_metasenv metasenv n =
 146     List.partition (fun (_,ctx,_) -> List.length ctx > n) metasenv
 147   in
 148   let purge_unused_lambdas metasenv t =
 149     let rec aux = function
 150         | Cic.Lambda (_, Cic.Meta (i,_), t) when
 151           List.exists (fun (j,_,_) -> j = i) metasenv ->
 152             aux (CicSubstitution.subst (Cic.Rel ~-100) t)
 153         | Cic.Lambda (name, s, t) ->
 154             Cic.Lambda (name, s, aux t)
 155         | t -> t
 156     in
 157     aux t
 158   in
 159   let order_body_menv term body_metasenv =
 160     let rec purge_lambdas = function
 161       | Cic.Lambda (_,_,t) -> purge_lambdas t
 162       | t -> t
 163     in
 164     let skip_appl = function | Cic.Appl l -> List.tl l | _ -> assert false in
 165     let metas_that_saturate l =
 166       List.fold_left
 167         (fun (acc,n) t ->
 168           let metas = CicUtil.metas_of_term t in
 169           let metas = List.map fst metas in
 170           let metas =
 171             List.filter
 172               (fun i -> List.for_all (fun (j,_) -> j<>i) acc)
 173               metas
 174           in
 175           let metas = List.map (fun i -> i,n) metas in
 176           metas @ acc, n+1)
 177         ([],0) l
 178     in
 179     let l_c2 = skip_appl (purge_lambdas term) in
 180     let l_c1 =
 181       match HExtlib.list_last l_c2 with
 182       | Cic.Appl l -> List.tl l
 183       | _ -> assert false
 184     in
 185     (* i should cut off the last elem of l_c2 *)
 186     let meta2no = fst (metas_that_saturate (l_c1 @ l_c2)) in
 187     List.sort
 188       (fun (i,ctx1,ty1) (j,ctx1,ty1) ->
 189           try List.assoc i meta2no -  List.assoc j meta2no
 190           with Not_found -> assert false)
 191       body_metasenv
 192   in
 193   let namer l n =
 194     let l = List.map (function Cic.Name s -> s | _ -> "A") l in
 195     let l = List.fold_left
 196       (fun acc s ->
 197         let rec add' s =
 198           if List.exists ((=) s) acc then add' (s^"'") else s
 199         in
 200         acc@[add' s])
 201       [] l
 202     in
 203     let l = List.rev l in
 204     Cic.Name (List.nth l (n-1))
 205   in
 206   debug_print (lazy ("\nCOMPOSING"));
 207   debug_print (lazy (" c1= "^CicPp.ppterm c1 ^"  :  "^ CicPp.ppterm c1_ty));
 208   debug_print (lazy (" c2= "^CicPp.ppterm c2 ^"  :  "^ CicPp.ppterm c2_ty));
 209   let saturations_for_c1, names_c1 = count_saturations_needed c1_ty 0 in
 210   let saturations_for_c2, names_c2 = count_saturations_needed c2_ty arity in
 211   let c = compose c1 saturations_for_c1 c2 saturations_for_c2 in
 212   let spine_len = saturations_for_c1 + saturations_for_c2 in
 213   let c = mk_lambda_spine c (namer (names_c1 @ names_c2)) spine_len in
 214   debug_print (lazy ("COMPOSTA: " ^ CicPp.ppterm c));
 215   let old_insert_coercions = !CicRefine.insert_coercions in
 216   let c, metasenv, univ =
 217     try
 218       CicRefine.insert_coercions := false;
 219       let term, ty, metasenv, ugraph =
 220         CicRefine.type_of_aux' metasenv context c univ
 221       in
 222       debug_print(lazy("COMPOSED REFINED: "^CicPp.ppterm term));
 223 (*       let metasenv = order_metasenv metasenv in *)
 224 (*       debug_print(lazy("ORDERED MENV: "^CicMetaSubst.ppmetasenv [] metasenv)); *)
 225       let body_metasenv, lambdas_metasenv =
 226         split_metasenv metasenv (spine_len + List.length context)
 227       in
 228       debug_print(lazy("B_MENV: "^CicMetaSubst.ppmetasenv [] body_metasenv));
 229       debug_print(lazy("L_MENV: "^CicMetaSubst.ppmetasenv [] lambdas_metasenv));
 230       let body_metasenv = order_body_menv term body_metasenv in
 231       debug_print(lazy("ORDERED_B_MENV: "^CicMetaSubst.ppmetasenv [] body_metasenv));
 232       let subst = create_subst_from_metas_to_rels spine_len body_metasenv in
 233       debug_print (lazy("SUBST: "^CicMetaSubst.ppsubst body_metasenv subst));
 234       let term = CicMetaSubst.apply_subst subst term in
 235       let metasenv = CicMetaSubst.apply_subst_metasenv subst metasenv in
 236       debug_print (lazy ("COMPOSED SUBSTITUTED: " ^ CicPp.ppterm term));
 237       let term, ty, metasenv, ugraph =
 238         CicRefine.type_of_aux' metasenv context term ugraph
 239       in
 240       let body_metasenv, lambdas_metasenv =
 241         split_metasenv metasenv (spine_len + List.length context)
 242       in
 243       let lambdas_metasenv =
 244         List.filter
 245           (fun (i,_,_) ->
 246             List.for_all (fun (j,_,_) -> i <> j) original_metasenv)
 247           lambdas_metasenv
 248       in
 249       let term = purge_unused_lambdas lambdas_metasenv term in
 250       let metasenv =
 251         List.filter
 252           (fun (i,_,_) ->
 253             List.for_all
 254               (fun (j,_,_) ->
 255                 i <> j || List.exists (fun (j,_,_) -> j=i) original_metasenv)
 256               lambdas_metasenv)
 257           metasenv
 258       in
 259       debug_print (lazy ("COMPOSED: " ^ CicPp.ppterm term));
 260       debug_print(lazy("MENV: "^CicMetaSubst.ppmetasenv [] metasenv));
 261       CicRefine.insert_coercions := old_insert_coercions;
 262       term, metasenv, ugraph
 263     with
 264     | CicRefine.RefineFailure s
 265     | CicRefine.Uncertain s -> debug_print s;
 266         CicRefine.insert_coercions := old_insert_coercions;
 267         raise UnableToCompose
 268     | exn ->
 269         CicRefine.insert_coercions := old_insert_coercions;
 270         raise exn
 271   in
 272   c, metasenv, univ, saturationsres
 273 ;;
 274
 275 let build_obj c univ arity =
 276   let c_ty,univ =
 277     try
 278       CicTypeChecker.type_of_aux' [] [] c univ
 279     with CicTypeChecker.TypeCheckerFailure s ->
 280       debug_print (lazy (Printf.sprintf "Generated composite coercion:\n%s\n%s"
 281         (CicPp.ppterm c) (Lazy.force s)));
 282       raise UnableToCompose
 283   in
 284   let cleaned_ty =
 285     FreshNamesGenerator.clean_dummy_dependent_types c_ty
 286   in
 287   let obj = Cic.Constant ("xxxx",Some c,cleaned_ty,[],obj_attrs arity) in
 288     obj,univ
 289 ;;
 290
 291 (* removes from l the coercions that are in !coercions *)
 292 let filter_duplicates l coercions =
 293   List.filter (
 294       fun (src,l1,tgt) ->
 295         not (List.exists (fun (s,t,l2) ->
 296           CoercDb.eq_carr s src &&
 297           CoercDb.eq_carr t tgt &&
 298           try
 299             List.for_all2 (fun (u1,_) (u2,_) -> UriManager.eq u1 u2) l1 l2
 300           with
 301           | Invalid_argument "List.for_all2" -> false)
 302         coercions))
 303   l
 304
 305 let mangle s t l =
 306   (*List.fold_left
 307     (fun s x -> s ^ "_" ^ x)
 308     (s ^ "_OF_" ^ t ^ "_BY" ^ string_of_int (List.length l)) l*)
 309   s ^ "_OF_" ^ t
 310 ;;
 311
 312 exception ManglingFailed of string
 313
 314 let number_if_already_defined buri name l =
 315   let err () =
 316     raise
 317       (ManglingFailed
 318         ("Unable to give an altenative name to " ^ buri ^ "/" ^ name ^ ".con"))
 319   in
 320   let rec aux n =
 321     let suffix = if n > 0 then string_of_int n else "" in
 322     let suri = buri ^ "/" ^ name ^ suffix ^ ".con" in
 323     let uri = UriManager.uri_of_string suri in
 324     let retry () =
 325       if n < 100 then
 326         begin
 327           HLog.warn ("Uri " ^ suri ^ " already exists.");
 328           aux (n+1)
 329         end
 330       else
 331         err ()
 332     in
 333     if List.exists (UriManager.eq uri) l then retry ()
 334     else
 335       try
 336         let _  = Http_getter.resolve' ~local:true ~writable:true uri in
 337         if Http_getter.exists' ~local:true uri then retry () else uri
 338       with
 339       | Http_getter_types.Key_not_found _ -> uri
 340       | Http_getter_types.Unresolvable_URI _ -> assert false
 341   in
 342   aux 0
 343 ;;
 344
 345 (* given a new coercion uri from src to tgt returns
 346  * a list of (new coercion uri, coercion obj, universe graph)
 347  *)
 348 let close_coercion_graph src tgt uri saturations baseuri =
 349   (* check if the coercion already exists *)
 350   let coercions = CoercDb.to_list () in
 351   let todo_list = get_closure_coercions src tgt (uri,saturations) coercions in
 352   let todo_list = filter_duplicates todo_list coercions in
 353   try
 354     let new_coercions =
 355       List.fold_left
 356         (fun acc (src, l , tgt) ->
 357           try
 358             (match l with
 359             | [] -> assert false
 360             | (he,saturations1) :: tl ->
 361                 let arity = match tgt with CoercDb.Fun n -> n | _ -> 0 in
 362                 let first_step =
 363                   Cic.Constant ("",
 364                     Some (CoercDb.term_of_carr (CoercDb.Uri he)),
 365                     Cic.Sort Cic.Prop, [], obj_attrs arity), saturations1
 366                 in
 367                 let o,_ =
 368                   List.fold_left (fun (o,univ) (coer,saturations) ->
 369                     match o with
 370                     | Cic.Constant (_,Some u,_,[],_),saturations1 ->
 371                         let t, menv, univ, saturationsres =
 372                           generate_composite' (u,saturations1)
 373                             (CoercDb.term_of_carr (CoercDb.Uri coer),
 374                              saturations)
 375                             [] [] univ arity true
 376                         in
 377                         if (menv = []) then
 378                           HLog.warn "MENV non empty after composing coercions";
 379                         let o,univ = build_obj t univ arity in
 380                          (o,saturationsres),univ
 381                     | _ -> assert false
 382                   ) (first_step, CicUniv.empty_ugraph) tl
 383                 in
 384                 let name_src = CoercDb.name_of_carr src in
 385                 let name_tgt = CoercDb.name_of_carr tgt in
 386                 let by = List.map (fun u,_ -> UriManager.name_of_uri u) l in
 387                 let name = mangle name_tgt name_src by in
 388                 let c_uri =
 389                   number_if_already_defined baseuri name
 390                     (List.map (fun (_,_,u,_,_) -> u) acc)
 391                 in
 392                 let named_obj,saturations =
 393                   match o with
 394                   | Cic.Constant (_,bo,ty,vl,attrs),saturations ->
 395                       Cic.Constant (name,bo,ty,vl,attrs),saturations
 396                   | _ -> assert false
 397                 in
 398                   (src,tgt,c_uri,saturations,named_obj))::acc
 399           with UnableToCompose -> acc
 400       ) [] todo_list
 401     in
 402     new_coercions
 403   with ManglingFailed s -> HLog.error s; []
 404 ;;
 405
 406 CicCoercion.set_close_coercion_graph close_coercion_graph;;
 407
 408 (* generate_composite (c2 (c1 s)) in the universe graph univ
 409  * both living in the same context and metasenv *)
 410 let generate_composite c1 c2 context metasenv univ arity b =
 411  let a,b,c,_ =
 412   generate_composite' (c1,0) (c2,0) context metasenv univ arity b
 413  in
 414   a,b,c
 415 ;;