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