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