helm/software/components/acic_content/acic2content.ml

   1 (* Copyright (C) 2000, 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://cs.unibo.it/helm/.
  24  *)
  25
  26 (**************************************************************************)
  27 (*                                                                        *)
  28 (*                           PROJECT HELM                                 *)
  29 (*                                                                        *)
  30 (*                Andrea Asperti <asperti@cs.unibo.it>                    *)
  31 (*                             16/6/2003                                   *)
  32 (*                                                                        *)
  33 (**************************************************************************)
  34
  35 (* $Id$ *)
  36
  37 let object_prefix = "obj:";;
  38 let declaration_prefix = "decl:";;
  39 let definition_prefix = "def:";;
  40 let inductive_prefix = "ind:";;
  41 let joint_prefix = "joint:";;
  42 let proof_prefix = "proof:";;
  43 let conclude_prefix = "concl:";;
  44 let premise_prefix = "prem:";;
  45 let lemma_prefix = "lemma:";;
  46
  47 let hide_coercions = ref true;;
  48
  49 (* e se mettessi la conversione di BY nell'apply_context ? *)
  50 (* sarebbe carino avere l'invariante che la proof2pres
  51 generasse sempre prove con contesto vuoto *)
  52
  53 let gen_id prefix seed =
  54  let res = prefix ^ string_of_int !seed in
  55   incr seed ;
  56   res
  57 ;;
  58
  59 let name_of = function
  60     Cic.Anonymous -> None
  61   | Cic.Name b -> Some b;;
  62
  63 exception Not_a_proof;;
  64 exception NotImplemented;;
  65 exception NotApplicable;;
  66
  67 (* we do not care for positivity, here, that in any case is enforced by
  68    well typing. Just a brutal search *)
  69
  70 let rec occur uri =
  71   let module C = Cic in
  72   function
  73       C.Rel _ -> false
  74     | C.Var _ -> false
  75     | C.Meta _ -> false
  76     | C.Sort _ -> false
  77     | C.Implicit _ -> assert false
  78     | C.Prod (_,s,t) -> (occur uri s) or (occur uri t)
  79     | C.Cast (te,ty) -> (occur uri te)
  80     | C.Lambda (_,s,t) -> (occur uri s) or (occur uri t) (* or false ?? *)
  81     | C.LetIn (_,s,t) -> (occur uri s) or (occur uri t)
  82     | C.Appl l ->
  83         List.fold_left
  84           (fun b a ->
  85              if b then b
  86              else (occur uri a)) false l
  87     | C.Const (_,_) -> false
  88     | C.MutInd (uri1,_,_) -> if uri = uri1 then true else false
  89     | C.MutConstruct (_,_,_,_) -> false
  90     | C.MutCase _ -> false (* presuming too much?? *)
  91     | C.Fix _ -> false (* presuming too much?? *)
  92     | C.CoFix (_,_) -> false (* presuming too much?? *)
  93 ;;
  94
  95 let get_id =
  96   let module C = Cic in
  97   function
  98       C.ARel (id,_,_,_) -> id
  99     | C.AVar (id,_,_) -> id
 100     | C.AMeta (id,_,_) -> id
 101     | C.ASort (id,_) -> id
 102     | C.AImplicit _ -> raise NotImplemented
 103     | C.AProd (id,_,_,_) -> id
 104     | C.ACast (id,_,_) -> id
 105     | C.ALambda (id,_,_,_) -> id
 106     | C.ALetIn (id,_,_,_) -> id
 107     | C.AAppl (id,_) -> id
 108     | C.AConst (id,_,_) -> id
 109     | C.AMutInd (id,_,_,_) -> id
 110     | C.AMutConstruct (id,_,_,_,_) -> id
 111     | C.AMutCase (id,_,_,_,_,_) -> id
 112     | C.AFix (id,_,_) -> id
 113     | C.ACoFix (id,_,_) -> id
 114 ;;
 115
 116 let test_for_lifting ~ids_to_inner_types ~ids_to_inner_sorts=
 117   let module C = Cic in
 118   let module C2A = Cic2acic in
 119   (* atomic terms are never lifted, according to my policy *)
 120   function
 121       C.ARel (id,_,_,_) -> false
 122     | C.AVar (id,_,_) ->
 123          (try
 124             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 125             true;
 126           with Not_found -> false)
 127     | C.AMeta (id,_,_) ->
 128          (try
 129             Hashtbl.find ids_to_inner_sorts id = `Prop
 130           with Not_found -> assert false)
 131     | C.ASort (id,_) -> false
 132     | C.AImplicit _ -> raise NotImplemented
 133     | C.AProd (id,_,_,_) -> false
 134     | C.ACast (id,_,_) ->
 135          (try
 136             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 137             true;
 138           with Not_found -> false)
 139     | C.ALambda (id,_,_,_) ->
 140          (try
 141             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 142             true;
 143           with Not_found -> false)
 144     | C.ALetIn (id,_,_,_) ->
 145          (try
 146             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 147             true;
 148           with Not_found -> false)
 149     | C.AAppl (id,_) ->
 150          (try
 151             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 152             true;
 153           with Not_found -> false)
 154     | C.AConst (id,_,_) ->
 155          (try
 156             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 157             true;
 158           with Not_found -> false)
 159     | C.AMutInd (id,_,_,_) -> false
 160     | C.AMutConstruct (id,_,_,_,_) ->
 161        (try
 162             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 163             true;
 164           with Not_found -> false)
 165         (* oppure: false *)
 166     | C.AMutCase (id,_,_,_,_,_) ->
 167          (try
 168             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 169             true;
 170           with Not_found -> false)
 171     | C.AFix (id,_,_) ->
 172           (try
 173             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 174             true;
 175           with Not_found -> false)
 176     | C.ACoFix (id,_,_) ->
 177          (try
 178             ignore (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized;
 179             true;
 180           with Not_found -> false)
 181 ;;
 182
 183 (* transform a proof p into a proof list, concatenating the last
 184 conclude element to the apply_context list, in case context is
 185 empty. Otherwise, it just returns [p] *)
 186
 187 let flat seed p =
 188  let module K = Content in
 189   if (p.K.proof_context = []) then
 190     if p.K.proof_apply_context = [] then [p]
 191     else
 192       let p1 =
 193         { p with
 194           K.proof_context = [];
 195           K.proof_apply_context = []
 196         } in
 197       p.K.proof_apply_context@[p1]
 198   else
 199     [p]
 200 ;;
 201
 202 let rec serialize seed =
 203   function
 204     [] -> []
 205   | a::l -> (flat seed a)@(serialize seed l)
 206 ;;
 207
 208 (* top_down = true if the term is a LAMBDA or a decl *)
 209 let generate_conversion seed top_down id inner_proof ~ids_to_inner_types =
 210  let module C2A = Cic2acic in
 211  let module K = Content in
 212  let exp = (try ((Hashtbl.find ids_to_inner_types id).C2A.annexpected)
 213             with Not_found -> None)
 214  in
 215  match exp with
 216      None -> inner_proof
 217    | Some expty ->
 218        if inner_proof.K.proof_conclude.K.conclude_method = "Intros+LetTac" then
 219          { K.proof_name = inner_proof.K.proof_name;
 220             K.proof_id   = gen_id proof_prefix seed;
 221             K.proof_context = [] ;
 222             K.proof_apply_context = [];
 223             K.proof_conclude =
 224               { K.conclude_id = gen_id conclude_prefix seed;
 225                 K.conclude_aref = id;
 226                 K.conclude_method = "TD_Conversion";
 227                 K.conclude_args =
 228                   [K.ArgProof {inner_proof with K.proof_name = None}];
 229                 K.conclude_conclusion = Some expty
 230               };
 231           }
 232         else
 233           { K.proof_name =  inner_proof.K.proof_name;
 234             K.proof_id   = gen_id proof_prefix seed;
 235             K.proof_context = [] ;
 236             K.proof_apply_context = [{inner_proof with K.proof_name = None}];
 237             K.proof_conclude =
 238               { K.conclude_id = gen_id conclude_prefix seed;
 239                 K.conclude_aref = id;
 240                 K.conclude_method = "BU_Conversion";
 241                 K.conclude_args =
 242                  [K.Premise
 243                   { K.premise_id = gen_id premise_prefix seed;
 244                     K.premise_xref = inner_proof.K.proof_id;
 245                     K.premise_binder = None;
 246                     K.premise_n = None
 247                   }
 248                  ];
 249                 K.conclude_conclusion = Some expty
 250               };
 251           }
 252 ;;
 253
 254 let generate_exact seed t id name ~ids_to_inner_types =
 255   let module C2A = Cic2acic in
 256   let module K = Content in
 257     { K.proof_name = name;
 258       K.proof_id   = gen_id proof_prefix seed ;
 259       K.proof_context = [] ;
 260       K.proof_apply_context = [];
 261       K.proof_conclude =
 262         { K.conclude_id = gen_id conclude_prefix seed;
 263           K.conclude_aref = id;
 264           K.conclude_method = "Exact";
 265           K.conclude_args = [K.Term (false, t)];
 266           K.conclude_conclusion =
 267               try Some (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 268               with Not_found -> None
 269         };
 270     }
 271 ;;
 272
 273 let generate_intros_let_tac seed id n s is_intro inner_proof name ~ids_to_inner_types =
 274   let module C2A = Cic2acic in
 275   let module C = Cic in
 276   let module K = Content in
 277     { K.proof_name = name;
 278       K.proof_id  = gen_id proof_prefix seed ;
 279       K.proof_context = [] ;
 280       K.proof_apply_context = [];
 281       K.proof_conclude =
 282         { K.conclude_id = gen_id conclude_prefix seed;
 283           K.conclude_aref = id;
 284           K.conclude_method = "Intros+LetTac";
 285           K.conclude_args = [K.ArgProof inner_proof];
 286           K.conclude_conclusion =
 287             try Some
 288              (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 289             with Not_found ->
 290               (match inner_proof.K.proof_conclude.K.conclude_conclusion with
 291                  None -> None
 292               | Some t ->
 293                   if is_intro then Some (C.AProd ("gen"^id,n,s,t))
 294                   else Some (C.ALetIn ("gen"^id,n,s,t)))
 295         };
 296     }
 297 ;;
 298
 299 let build_decl_item seed id n s ~ids_to_inner_sorts =
 300  let module K = Content in
 301  let sort =
 302    try
 303     Some (Hashtbl.find ids_to_inner_sorts (Cic2acic.source_id_of_id id))
 304    with Not_found -> None
 305  in
 306  match sort with
 307  | Some `Prop ->
 308     `Hypothesis
 309       { K.dec_name = name_of n;
 310         K.dec_id = gen_id declaration_prefix seed;
 311         K.dec_inductive = false;
 312         K.dec_aref = id;
 313         K.dec_type = s
 314       }
 315  | _ ->
 316     `Declaration
 317       { K.dec_name = name_of n;
 318         K.dec_id = gen_id declaration_prefix seed;
 319         K.dec_inductive = false;
 320         K.dec_aref = id;
 321         K.dec_type = s
 322       }
 323 ;;
 324
 325 let infer_dependent ~headless context metasenv = function
 326   | [] -> assert false
 327   | [t] -> [false, t]
 328   | he::tl as l ->
 329      if headless then
 330       List.map (function s -> false,s) l
 331      else
 332      try
 333        let hety,_ =
 334          CicTypeChecker.type_of_aux'
 335            metasenv context (Deannotate.deannotate_term he)
 336            CicUniv.oblivion_ugraph
 337        in
 338        let fstorder t =
 339          match CicReduction.whd context t with
 340          | Cic.Prod _ -> false
 341          | _ -> true
 342        in
 343        let rec dummify_last_tgt t =
 344          match CicReduction.whd context t with
 345          | Cic.Prod (n,s,tgt) -> Cic.Prod(n,s, dummify_last_tgt tgt)
 346          | _ -> Cic.Implicit None
 347        in
 348        let rec aux ty = function
 349          | [] -> []
 350          | t::tl ->
 351               match
 352                FreshNamesGenerator.clean_dummy_dependent_types
 353                  (dummify_last_tgt ty)
 354               with
 355               | Cic.Prod (n,src,tgt) ->
 356                   (n <> Cic.Anonymous && fstorder src, t) ::
 357                   aux (CicSubstitution.subst
 358                         (Deannotate.deannotate_term t) tgt) tl
 359               | _ -> assert false
 360        in
 361        (false, he) :: aux hety tl
 362      with CicTypeChecker.TypeCheckerFailure _ -> assert false
 363 ;;
 364
 365 let rec build_subproofs_and_args ?(headless=false) seed context metasenv l ~ids_to_inner_types ~ids_to_inner_sorts =
 366   let module C = Cic in
 367   let module K = Content in
 368   let rec aux =
 369     function
 370       [] -> [],[]
 371     | (dep, t)::l1 ->
 372        let subproofs,args = aux l1 in
 373         if (test_for_lifting t ~ids_to_inner_types ~ids_to_inner_sorts) then
 374           let new_subproof =
 375             acic2content
 376               seed context metasenv
 377                ~name:"H" ~ids_to_inner_types ~ids_to_inner_sorts t in
 378           let new_arg =
 379             K.Premise
 380               { K.premise_id = gen_id premise_prefix seed;
 381                 K.premise_xref = new_subproof.K.proof_id;
 382                 K.premise_binder = new_subproof.K.proof_name;
 383                 K.premise_n = None
 384               } in
 385           new_subproof::subproofs,new_arg::args
 386         else
 387           let hd =
 388             (match t with
 389                C.ARel (idr,idref,n,b) ->
 390                  let sort =
 391                    (try
 392                      Hashtbl.find ids_to_inner_sorts idr
 393                     with Not_found -> `Type (CicUniv.fresh())) in
 394                  if sort = `Prop then
 395                     K.Premise
 396                       { K.premise_id = gen_id premise_prefix seed;
 397                         K.premise_xref = idr;
 398                         K.premise_binder = Some b;
 399                         K.premise_n = Some n
 400                       }
 401                  else (K.Term (dep,t))
 402              | C.AConst(id,uri,[]) ->
 403                  let sort =
 404                    (try
 405                      Hashtbl.find ids_to_inner_sorts id
 406                     with Not_found -> `Type (CicUniv.fresh())) in
 407                  if sort = `Prop then
 408                     K.Lemma
 409                       { K.lemma_id = gen_id lemma_prefix seed;
 410                         K.lemma_name = UriManager.name_of_uri uri;
 411                         K.lemma_uri = UriManager.string_of_uri uri
 412                       }
 413                  else (K.Term (dep,t))
 414              | C.AMutConstruct(id,uri,tyno,consno,[]) ->
 415                  let sort =
 416                    (try
 417                      Hashtbl.find ids_to_inner_sorts id
 418                     with Not_found -> `Type (CicUniv.fresh())) in
 419                  if sort = `Prop then
 420                     let inductive_types =
 421                       (let o,_ =
 422                          CicEnvironment.get_obj CicUniv.empty_ugraph uri
 423                        in
 424                          match o with
 425                            | Cic.InductiveDefinition (l,_,_,_) -> l
 426                            | _ -> assert false
 427                       ) in
 428                     let (_,_,_,constructors) =
 429                       List.nth inductive_types tyno in
 430                     let name,_ = List.nth constructors (consno - 1) in
 431                     K.Lemma
 432                       { K.lemma_id = gen_id lemma_prefix seed;
 433                         K.lemma_name = name;
 434                         K.lemma_uri =
 435                           UriManager.string_of_uri uri ^ "#xpointer(1/" ^
 436                           string_of_int (tyno+1) ^ "/" ^ string_of_int consno ^
 437                           ")"
 438                       }
 439                  else (K.Term (dep,t))
 440              | _ -> (K.Term (dep,t))) in
 441           subproofs,hd::args
 442   in
 443   match (aux (infer_dependent ~headless context metasenv l)) with
 444     [p],args ->
 445       [{p with K.proof_name = None}],
 446         List.map
 447           (function
 448               K.Premise prem when prem.K.premise_xref = p.K.proof_id ->
 449                K.Premise {prem with K.premise_binder = None}
 450             | i -> i) args
 451   | p,a as c -> c
 452
 453 and
 454
 455 build_def_item seed context metasenv id n t ~ids_to_inner_sorts ~ids_to_inner_types =
 456  let module K = Content in
 457   try
 458    let sort = Hashtbl.find ids_to_inner_sorts id in
 459    if sort = `Prop then
 460        (let p =
 461         (acic2content seed context metasenv ?name:(name_of n) ~ids_to_inner_sorts  ~ids_to_inner_types t)
 462        in
 463         `Proof p;)
 464    else
 465       `Definition
 466         { K.def_name = name_of n;
 467           K.def_id = gen_id definition_prefix seed;
 468           K.def_aref = id;
 469           K.def_term = t
 470         }
 471   with
 472    Not_found -> assert false
 473
 474 (* the following function must be called with an object of sort
 475 Prop. For debugging purposes this is tested again, possibly raising an
 476 Not_a_proof exception *)
 477
 478 and acic2content seed context metasenv ?name ~ids_to_inner_sorts ~ids_to_inner_types t =
 479   let rec aux ?name context t =
 480   let module C = Cic in
 481   let module K = Content in
 482   let module C2A = Cic2acic in
 483   let t1 =
 484     match t with
 485       C.ARel (id,idref,n,b) as t ->
 486         let sort = Hashtbl.find ids_to_inner_sorts id in
 487         if sort = `Prop then
 488           generate_exact seed t id name ~ids_to_inner_types
 489         else raise Not_a_proof
 490     | C.AVar (id,uri,exp_named_subst) as t ->
 491         let sort = Hashtbl.find ids_to_inner_sorts id in
 492         if sort = `Prop then
 493           generate_exact seed t id name ~ids_to_inner_types
 494         else raise Not_a_proof
 495     | C.AMeta (id,n,l) as t ->
 496         let sort = Hashtbl.find ids_to_inner_sorts id in
 497         if sort = `Prop then
 498           generate_exact seed t id name ~ids_to_inner_types
 499         else raise Not_a_proof
 500     | C.ASort (id,s) -> raise Not_a_proof
 501     | C.AImplicit _ -> raise NotImplemented
 502     | C.AProd (_,_,_,_) -> raise Not_a_proof
 503     | C.ACast (id,v,t) -> aux context v
 504     | C.ALambda (id,n,s,t) ->
 505         let sort = Hashtbl.find ids_to_inner_sorts id in
 506         if sort = `Prop then
 507           let proof =
 508             aux ((Some (n,Cic.Decl (Deannotate.deannotate_term s)))::context) t
 509           in
 510           let proof' =
 511             if proof.K.proof_conclude.K.conclude_method = "Intros+LetTac" then
 512                match proof.K.proof_conclude.K.conclude_args with
 513                  [K.ArgProof p] -> p
 514                | _ -> assert false
 515             else proof in
 516           let proof'' =
 517             { proof' with
 518               K.proof_name = None;
 519               K.proof_context =
 520                 (build_decl_item seed id n s ids_to_inner_sorts)::
 521                   proof'.K.proof_context
 522             }
 523           in
 524           generate_intros_let_tac seed id n s true proof'' name ~ids_to_inner_types
 525         else
 526           raise Not_a_proof
 527     | C.ALetIn (id,n,s,t) ->
 528         let sort = Hashtbl.find ids_to_inner_sorts id in
 529         if sort = `Prop then
 530           let proof = (* XXX TIPAMI!!! *)
 531             aux ((Some (n,Cic.Def (Deannotate.deannotate_term s,None)))::context) t
 532           in
 533           let proof' =
 534             if proof.K.proof_conclude.K.conclude_method = "Intros+LetTac" then
 535                match proof.K.proof_conclude.K.conclude_args with
 536                  [K.ArgProof p] -> p
 537                | _ -> assert false
 538             else proof in
 539           let proof'' =
 540             { proof' with
 541                K.proof_name = None;
 542                K.proof_context =
 543                  ((build_def_item seed context metasenv (get_id s) n s ids_to_inner_sorts
 544                    ids_to_inner_types):> Cic.annterm K.in_proof_context_element)
 545                  ::proof'.K.proof_context;
 546             }
 547           in
 548           generate_intros_let_tac seed id n s false proof'' name ~ids_to_inner_types
 549         else
 550           raise Not_a_proof
 551     | C.AAppl (id,li) ->
 552         (try coercion
 553            seed context metasenv li ~ids_to_inner_types ~ids_to_inner_sorts
 554          with NotApplicable ->
 555          try rewrite
 556            seed context metasenv name id li ~ids_to_inner_types ~ids_to_inner_sorts
 557          with NotApplicable ->
 558          try inductive
 559           seed context metasenv name id li ~ids_to_inner_types ~ids_to_inner_sorts
 560          with NotApplicable ->
 561          try transitivity
 562            seed context metasenv name id li ~ids_to_inner_types ~ids_to_inner_sorts
 563          with NotApplicable ->
 564           let subproofs, args =
 565             build_subproofs_and_args
 566               seed context metasenv li ~ids_to_inner_types ~ids_to_inner_sorts in
 567 (*
 568           let args_to_lift =
 569             List.filter (test_for_lifting ~ids_to_inner_types) li in
 570           let subproofs =
 571             match args_to_lift with
 572                 [_] -> List.map aux args_to_lift
 573             | _ -> List.map (aux ~name:"H") args_to_lift in
 574           let args = build_args seed li subproofs
 575                  ~ids_to_inner_types ~ids_to_inner_sorts in *)
 576             { K.proof_name = name;
 577               K.proof_id   = gen_id proof_prefix seed;
 578               K.proof_context = [];
 579               K.proof_apply_context = serialize seed subproofs;
 580               K.proof_conclude =
 581                 { K.conclude_id = gen_id conclude_prefix seed;
 582                   K.conclude_aref = id;
 583                   K.conclude_method = "Apply";
 584                   K.conclude_args = args;
 585                   K.conclude_conclusion =
 586                      try Some
 587                        (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 588                      with Not_found -> None
 589                  };
 590             })
 591     | C.AConst (id,uri,exp_named_subst) as t ->
 592         let sort = Hashtbl.find ids_to_inner_sorts id in
 593         if sort = `Prop then
 594           generate_exact seed t id name ~ids_to_inner_types
 595         else raise Not_a_proof
 596     | C.AMutInd (id,uri,i,exp_named_subst) -> raise Not_a_proof
 597     | C.AMutConstruct (id,uri,i,j,exp_named_subst) as t ->
 598         let sort = Hashtbl.find ids_to_inner_sorts id in
 599         if sort = `Prop then
 600           generate_exact seed t id name ~ids_to_inner_types
 601         else raise Not_a_proof
 602     | C.AMutCase (id,uri,typeno,ty,te,patterns) ->
 603         let inductive_types,noparams =
 604           (let o, _ = CicEnvironment.get_obj CicUniv.empty_ugraph uri in
 605              match o with
 606                  Cic.Constant _ -> assert false
 607                | Cic.Variable _ -> assert false
 608                | Cic.CurrentProof _ -> assert false
 609                | Cic.InductiveDefinition (l,_,n,_) -> l,n
 610           ) in
 611         let (_,_,_,constructors) = List.nth inductive_types typeno in
 612         let name_and_arities =
 613           let rec count_prods =
 614             function
 615                C.Prod (_,_,t) -> 1 + count_prods t
 616              | _ -> 0 in
 617           List.map
 618             (function (n,t) -> Some n,((count_prods t) - noparams)) constructors in
 619         let pp =
 620           let build_proof p (name,arity) =
 621             let rec make_context_and_body c p n =
 622               if n = 0 then c,(aux context p)
 623               else
 624                 (match p with
 625                    Cic.ALambda(idl,vname,s1,t1) ->
 626                      let ce =
 627                        build_decl_item
 628                          seed idl vname s1 ~ids_to_inner_sorts in
 629                      make_context_and_body (ce::c) t1 (n-1)
 630                    | _ -> assert false) in
 631              let context,body = make_context_and_body [] p arity in
 632                K.ArgProof
 633                 {body with K.proof_name = name; K.proof_context=context} in
 634           List.map2 build_proof patterns name_and_arities in
 635         let context,term =
 636           (match
 637              build_subproofs_and_args ~headless:true
 638                seed context metasenv ~ids_to_inner_types ~ids_to_inner_sorts [te]
 639            with
 640              l,[t] -> l,t
 641            | _ -> assert false) in
 642         { K.proof_name = name;
 643           K.proof_id   = gen_id proof_prefix seed;
 644           K.proof_context = [];
 645           K.proof_apply_context = serialize seed context;
 646           K.proof_conclude =
 647             { K.conclude_id = gen_id conclude_prefix seed;
 648               K.conclude_aref = id;
 649               K.conclude_method = "Case";
 650               K.conclude_args =
 651                 (K.Aux (UriManager.string_of_uri uri))::
 652                 (K.Aux (string_of_int typeno))::(K.Term (false,ty))::term::pp;
 653               K.conclude_conclusion =
 654                 try Some
 655                   (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 656                 with Not_found -> None
 657              }
 658         }
 659     | C.AFix (id, no, funs) ->
 660         let context' =
 661           List.fold_left
 662             (fun ctx (_,n,_,ty,_) ->
 663               let ty = Deannotate.deannotate_term ty in
 664               Some (Cic.Name n,Cic.Decl ty) :: ctx)
 665             [] funs @ context
 666         in
 667         let proofs =
 668           List.map
 669             (function (_,name,_,_,bo) -> `Proof (aux context' ~name bo)) funs in
 670         let fun_name =
 671           List.nth (List.map (fun (_,name,_,_,_) -> name) funs) no
 672         in
 673         let decreasing_args =
 674           List.map (function (_,_,n,_,_) -> n) funs in
 675         let jo =
 676           { K.joint_id = gen_id joint_prefix seed;
 677             K.joint_kind = `Recursive decreasing_args;
 678             K.joint_defs = proofs
 679           }
 680         in
 681           { K.proof_name = name;
 682             K.proof_id  = gen_id proof_prefix seed;
 683             K.proof_context = [`Joint jo];
 684             K.proof_apply_context = [];
 685             K.proof_conclude =
 686               { K.conclude_id = gen_id conclude_prefix seed;
 687                 K.conclude_aref = id;
 688                 K.conclude_method = "Exact";
 689                 K.conclude_args =
 690                 [ K.Premise
 691                   { K.premise_id = gen_id premise_prefix seed;
 692                     K.premise_xref = jo.K.joint_id;
 693                     K.premise_binder = Some fun_name;
 694                     K.premise_n = Some no;
 695                   }
 696                 ];
 697                 K.conclude_conclusion =
 698                    try Some
 699                      (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 700                    with Not_found -> None
 701               }
 702         }
 703     | C.ACoFix (id,no,funs) ->
 704         let context' =
 705           List.fold_left
 706             (fun ctx (_,n,ty,_) ->
 707               let ty = Deannotate.deannotate_term ty in
 708               Some (Cic.Name n,Cic.Decl ty) :: ctx)
 709             [] funs @ context
 710         in
 711         let proofs =
 712           List.map
 713             (function (_,name,_,bo) -> `Proof (aux context' ~name bo)) funs in
 714         let jo =
 715           { K.joint_id = gen_id joint_prefix seed;
 716             K.joint_kind = `CoRecursive;
 717             K.joint_defs = proofs
 718           }
 719         in
 720           { K.proof_name = name;
 721             K.proof_id   = gen_id proof_prefix seed;
 722             K.proof_context = [`Joint jo];
 723             K.proof_apply_context = [];
 724             K.proof_conclude =
 725               { K.conclude_id = gen_id conclude_prefix seed;
 726                 K.conclude_aref = id;
 727                 K.conclude_method = "Exact";
 728                 K.conclude_args =
 729                 [ K.Premise
 730                   { K.premise_id = gen_id premise_prefix seed;
 731                     K.premise_xref = jo.K.joint_id;
 732                     K.premise_binder = Some "tiralo fuori";
 733                     K.premise_n = Some no;
 734                   }
 735                 ];
 736                 K.conclude_conclusion =
 737                   try Some
 738                     (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 739                   with Not_found -> None
 740               };
 741         }
 742      in
 743      let id = get_id t in
 744      generate_conversion seed false id t1 ~ids_to_inner_types
 745 in aux ?name context t
 746
 747 and inductive seed context metasenv name id li ~ids_to_inner_types ~ids_to_inner_sorts =
 748   let aux context ?name =
 749     acic2content seed context metasenv ~ids_to_inner_types ~ids_to_inner_sorts
 750   in
 751   let module C2A = Cic2acic in
 752   let module K = Content in
 753   let module C = Cic in
 754   match li with
 755     C.AConst (idc,uri,exp_named_subst)::args ->
 756       let uri_str = UriManager.string_of_uri uri in
 757       let suffix = Str.regexp_string "_ind.con" in
 758       let len = String.length uri_str in
 759       let n = (try (Str.search_backward suffix uri_str len)
 760                with Not_found -> -1) in
 761       if n<0 then raise NotApplicable
 762       else
 763         let method_name =
 764           if UriManager.eq uri HelmLibraryObjects.Logic.ex_ind_URI then "Exists"
 765           else if UriManager.eq uri HelmLibraryObjects.Logic.and_ind_URI then "AndInd"
 766           else if UriManager.eq uri HelmLibraryObjects.Logic.false_ind_URI then "FalseInd"
 767           else "ByInduction" in
 768         let prefix = String.sub uri_str 0 n in
 769         let ind_str = (prefix ^ ".ind") in
 770         let ind_uri = UriManager.uri_of_string ind_str in
 771         let inductive_types,noparams =
 772           (let o,_ = CicEnvironment.get_obj CicUniv.empty_ugraph ind_uri in
 773              match o with
 774                | Cic.InductiveDefinition (l,_,n,_) -> (l,n)
 775                | _ -> assert false
 776           ) in
 777         let rec split n l =
 778           if n = 0 then ([],l) else
 779           let p,a = split (n-1) (List.tl l) in
 780           ((List.hd l::p),a) in
 781         let params_and_IP,tail_args = split (noparams+1) args in
 782         let constructors =
 783             (match inductive_types with
 784               [(_,_,_,l)] -> l
 785             | _ -> raise NotApplicable) (* don't care for mutual ind *) in
 786         let constructors1 =
 787           let rec clean_up n t =
 788              if n = 0 then t else
 789              (match t with
 790                 (label,Cic.Prod (_,_,t)) -> clean_up (n-1) (label,t)
 791               | _ -> assert false) in
 792           List.map (clean_up noparams) constructors in
 793         let no_constructors= List.length constructors in
 794         let args_for_cases, other_args =
 795           split no_constructors tail_args in
 796         let subproofs,other_method_args =
 797           build_subproofs_and_args ~headless:true seed context metasenv
 798            other_args ~ids_to_inner_types ~ids_to_inner_sorts in
 799         let method_args=
 800           let rec build_method_args =
 801             function
 802                 [],_-> [] (* extra args are ignored ???? *)
 803               | (name,ty)::tlc,arg::tla ->
 804                   let idarg = get_id arg in
 805                   let sortarg =
 806                     (try (Hashtbl.find ids_to_inner_sorts idarg)
 807                      with Not_found -> `Type (CicUniv.fresh())) in
 808                   let hdarg =
 809                     if sortarg = `Prop then
 810                       let (co,bo) =
 811                         let rec bc context =
 812                           function
 813                             Cic.Prod (_,s,t),Cic.ALambda(idl,n,s1,t1) ->
 814                               let context' =
 815                                 Some (n,Cic.Decl(Deannotate.deannotate_term s1))
 816                                   ::context
 817                               in
 818                               let ce =
 819                                 build_decl_item
 820                                   seed idl n s1 ~ids_to_inner_sorts in
 821                               if (occur ind_uri s) then
 822                                 ( match t1 with
 823                                    Cic.ALambda(id2,n2,s2,t2) ->
 824                                      let context'' =
 825                                        Some
 826                                          (n2,Cic.Decl
 827                                            (Deannotate.deannotate_term s2))
 828                                        ::context'
 829                                      in
 830                                      let inductive_hyp =
 831                                        `Hypothesis
 832                                          { K.dec_name = name_of n2;
 833                                            K.dec_id =
 834                                             gen_id declaration_prefix seed;
 835                                            K.dec_inductive = true;
 836                                            K.dec_aref = id2;
 837                                            K.dec_type = s2
 838                                          } in
 839                                      let (context,body) = bc context'' (t,t2) in
 840                                      (ce::inductive_hyp::context,body)
 841                                  | _ -> assert false)
 842                               else
 843                                 (
 844                                 let (context,body) = bc context' (t,t1) in
 845                                 (ce::context,body))
 846                             | _ , t -> ([],aux context t) in
 847                         bc context (ty,arg) in
 848                       K.ArgProof
 849                        { bo with
 850                          K.proof_name = Some name;
 851                          K.proof_context = co;
 852                        };
 853                     else (K.Term (false,arg)) in
 854                   hdarg::(build_method_args (tlc,tla))
 855               | _ -> assert false in
 856           build_method_args (constructors1,args_for_cases) in
 857           { K.proof_name = name;
 858             K.proof_id   = gen_id proof_prefix seed;
 859             K.proof_context = [];
 860             K.proof_apply_context = serialize seed subproofs;
 861             K.proof_conclude =
 862               { K.conclude_id = gen_id conclude_prefix seed;
 863                 K.conclude_aref = id;
 864                 K.conclude_method = method_name;
 865                 K.conclude_args =
 866                   K.Aux (string_of_int no_constructors)
 867                   ::K.Term (false,(C.AAppl(id,((C.AConst(idc,uri,exp_named_subst))::params_and_IP))))
 868                   ::method_args@other_method_args;
 869                 K.conclude_conclusion =
 870                    try Some
 871                      (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 872                    with Not_found -> None
 873               }
 874           }
 875   | _ -> raise NotApplicable
 876
 877 and coercion seed context metasenv li ~ids_to_inner_types ~ids_to_inner_sorts =
 878   match li with
 879     | ((Cic.AConst _) as he)::tl
 880     | ((Cic.AMutInd _) as he)::tl
 881     | ((Cic.AMutConstruct _) as he)::tl when
 882        CoercDb.is_a_coercion' (Deannotate.deannotate_term he) &&
 883        !hide_coercions ->
 884         let rec last =
 885          function
 886             [] -> assert false
 887           | [t] -> t
 888           | _::tl -> last tl
 889         in
 890           acic2content
 891             seed context metasenv ~ids_to_inner_types ~ids_to_inner_sorts (last tl)
 892     | _ -> raise NotApplicable
 893
 894 and rewrite seed context metasenv name id li ~ids_to_inner_types ~ids_to_inner_sorts =
 895   let aux context ?name =
 896     acic2content seed context metasenv ~ids_to_inner_types ~ids_to_inner_sorts
 897   in
 898   let module C2A = Cic2acic in
 899   let module K = Content in
 900   let module C = Cic in
 901   match li with
 902     C.AConst (sid,uri,exp_named_subst)::args ->
 903       if UriManager.eq uri HelmLibraryObjects.Logic.eq_ind_URI or
 904          UriManager.eq uri HelmLibraryObjects.Logic.eq_ind_r_URI or
 905          LibraryObjects.is_eq_ind_URI uri or
 906          LibraryObjects.is_eq_ind_r_URI uri then
 907         let subproofs,arg =
 908           (match
 909              build_subproofs_and_args
 910                seed context metasenv
 911                  ~ids_to_inner_types ~ids_to_inner_sorts [List.nth args 3]
 912            with
 913              l,[p] -> l,p
 914            | _,_ -> assert false) in
 915         let method_args =
 916           let rec ma_aux n = function
 917               [] -> []
 918             | a::tl ->
 919                 let hd =
 920                   if n = 0 then arg
 921                   else
 922                     let aid = get_id a in
 923                     let asort = (try (Hashtbl.find ids_to_inner_sorts aid)
 924                       with Not_found -> `Type (CicUniv.fresh())) in
 925                     if asort = `Prop then
 926                       K.ArgProof (aux context a)
 927                     else K.Term (false,a) in
 928                 hd::(ma_aux (n-1) tl) in
 929           (ma_aux 3 args) in
 930           { K.proof_name = name;
 931             K.proof_id  = gen_id proof_prefix seed;
 932             K.proof_context = [];
 933             K.proof_apply_context = serialize seed subproofs;
 934             K.proof_conclude =
 935               { K.conclude_id = gen_id conclude_prefix seed;
 936                 K.conclude_aref = id;
 937                 K.conclude_method = "Rewrite";
 938                 K.conclude_args =
 939                   K.Term (false,(C.AConst (sid,uri,exp_named_subst)))::method_args;
 940                 K.conclude_conclusion =
 941                    try Some
 942                      (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 943                    with Not_found -> None
 944               }
 945           }
 946       else raise NotApplicable
 947   | _ -> raise NotApplicable
 948
 949 and transitivity
 950   seed context metasenv name id li ~ids_to_inner_types ~ids_to_inner_sorts
 951 =
 952   let module C2A = Cic2acic in
 953   let module K = Content in
 954   let module C = Cic in
 955   match li with
 956     | C.AConst (sid,uri,exp_named_subst)::args
 957         when LibraryObjects.is_trans_eq_URI uri ->
 958         let exp_args = List.map snd exp_named_subst in
 959         let t1,t2,t3,p1,p2 =
 960           match exp_args@args with
 961             | [_;t1;t2;t3;p1;p2] -> t1,t2,t3,p1,p2
 962             | _ -> raise NotApplicable
 963         in
 964           { K.proof_name = name;
 965             K.proof_id  = gen_id proof_prefix seed;
 966             K.proof_context = [];
 967             K.proof_apply_context = [];
 968             K.proof_conclude =
 969               { K.conclude_id = gen_id conclude_prefix seed;
 970                 K.conclude_aref = id;
 971                 K.conclude_method = "Eq_chain";
 972                 K.conclude_args =
 973                    K.Term (false,t1)::
 974                      (transitivity_aux
 975                         seed context metasenv ~ids_to_inner_types ~ids_to_inner_sorts p1)
 976                      @ [K.Term (false,t2)]@
 977                      (transitivity_aux
 978                         seed context metasenv ~ids_to_inner_types ~ids_to_inner_sorts p2)
 979                      @ [K.Term (false,t3)];
 980                 K.conclude_conclusion =
 981                    try Some
 982                      (Hashtbl.find ids_to_inner_types id).C2A.annsynthesized
 983                    with Not_found -> None
 984               }
 985           }
 986     | _ -> raise NotApplicable
 987
 988 and transitivity_aux seed context metasenv ~ids_to_inner_types ~ids_to_inner_sorts t =
 989   let module C2A = Cic2acic in
 990   let module K = Content in
 991   let module C = Cic in
 992   match t with
 993     | C.AAppl (_,C.AConst (sid,uri,exp_named_subst)::args)
 994         when LibraryObjects.is_trans_eq_URI uri ->
 995         let exp_args = List.map snd exp_named_subst in
 996         let t1,t2,t3,p1,p2 =
 997           match exp_args@args with
 998             | [_;t1;t2;t3;p1;p2] -> t1,t2,t3,p1,p2
 999             | _ -> raise NotApplicable
1000         in
1001           (transitivity_aux
1002             seed context metasenv ~ids_to_inner_types ~ids_to_inner_sorts p1)
1003           @[K.Term (false,t2)]
1004           @(transitivity_aux
1005             seed context metasenv ~ids_to_inner_types ~ids_to_inner_sorts p2)
1006     | _ -> [K.ArgProof
1007         (acic2content seed context metasenv ~ids_to_inner_sorts ~ids_to_inner_types t)]
1008
1009 ;;
1010
1011
1012 let map_conjectures
1013  seed ~ids_to_inner_sorts ~ids_to_inner_types (id,n,context,ty)
1014 =
1015  let module K = Content in
1016  let context' =
1017   List.map
1018    (function
1019        (id,None) -> None
1020      | (id,Some (name,Cic.ADecl t)) ->
1021          Some
1022           (* We should call build_decl_item, but we have not computed *)
1023           (* the inner-types ==> we always produce a declaration      *)
1024           (`Declaration
1025             { K.dec_name = name_of name;
1026               K.dec_id = gen_id declaration_prefix seed;
1027               K.dec_inductive = false;
1028               K.dec_aref = get_id t;
1029               K.dec_type = t
1030             })
1031      | (id,Some (name,Cic.ADef t)) ->
1032          Some
1033           (* We should call build_def_item, but we have not computed *)
1034           (* the inner-types ==> we always produce a declaration     *)
1035           (`Definition
1036              { K.def_name = name_of name;
1037                K.def_id = gen_id definition_prefix seed;
1038                K.def_aref = get_id t;
1039                K.def_term = t
1040              })
1041    ) context
1042  in
1043   (id,n,context',ty)
1044 ;;
1045
1046 (* map_sequent is similar to map_conjectures, but the for the hid
1047 of the hypothesis, which are preserved instead of generating
1048 fresh ones. We shall have to adopt a uniform policy, soon or later *)
1049
1050 let map_sequent ((id,n,context,ty):Cic.annconjecture) =
1051  let module K = Content in
1052  let context' =
1053   List.map
1054    (function
1055        (id,None) -> None
1056      | (id,Some (name,Cic.ADecl t)) ->
1057          Some
1058           (* We should call build_decl_item, but we have not computed *)
1059           (* the inner-types ==> we always produce a declaration      *)
1060           (`Declaration
1061             { K.dec_name = name_of name;
1062               K.dec_id = id;
1063               K.dec_inductive = false;
1064               K.dec_aref = get_id t;
1065               K.dec_type = t
1066             })
1067      | (id,Some (name,Cic.ADef t)) ->
1068          Some
1069           (* We should call build_def_item, but we have not computed *)
1070           (* the inner-types ==> we always produce a declaration     *)
1071           (`Definition
1072              { K.def_name = name_of name;
1073                K.def_id = id;
1074                K.def_aref = get_id t;
1075                K.def_term = t
1076              })
1077    ) context
1078  in
1079   (id,n,context',ty)
1080 ;;
1081
1082 let rec annobj2content ~ids_to_inner_sorts ~ids_to_inner_types =
1083   let module C = Cic in
1084   let module K = Content in
1085   let module C2A = Cic2acic in
1086   let seed = ref 0 in
1087   function
1088       C.ACurrentProof (_,_,n,conjectures,bo,ty,params,_) ->
1089         (gen_id object_prefix seed, params,
1090           Some
1091            (List.map
1092              (map_conjectures seed ~ids_to_inner_sorts ~ids_to_inner_types)
1093              conjectures),
1094           `Def (K.Const,ty,
1095            build_def_item
1096              seed [] (Deannotate.deannotate_conjectures conjectures)
1097              (get_id bo) (C.Name n) bo
1098              ~ids_to_inner_sorts ~ids_to_inner_types))
1099     | C.AConstant (_,_,n,Some bo,ty,params,_) ->
1100          (gen_id object_prefix seed, params, None,
1101            `Def (K.Const,ty,
1102            build_def_item seed [] [] (get_id bo) (C.Name n) bo
1103                ~ids_to_inner_sorts ~ids_to_inner_types))
1104     | C.AConstant (id,_,n,None,ty,params,_) ->
1105          (gen_id object_prefix seed, params, None,
1106            `Decl (K.Const,
1107              build_decl_item seed id (C.Name n) ty
1108                ~ids_to_inner_sorts))
1109     | C.AVariable (_,n,Some bo,ty,params,_) ->
1110          (gen_id object_prefix seed, params, None,
1111            `Def (K.Var,ty,
1112            build_def_item seed [] [] (get_id bo) (C.Name n) bo
1113                ~ids_to_inner_sorts ~ids_to_inner_types))
1114     | C.AVariable (id,n,None,ty,params,_) ->
1115          (gen_id object_prefix seed, params, None,
1116            `Decl (K.Var,
1117              build_decl_item seed id (C.Name n) ty
1118               ~ids_to_inner_sorts))
1119     | C.AInductiveDefinition (id,l,params,nparams,_) ->
1120          (gen_id object_prefix seed, params, None,
1121             `Joint
1122               { K.joint_id = gen_id joint_prefix seed;
1123                 K.joint_kind = `Inductive nparams;
1124                 K.joint_defs = List.map (build_inductive seed) l
1125               })
1126
1127 and
1128     build_inductive seed =
1129      let module K = Content in
1130       fun (_,n,b,ty,l) ->
1131         `Inductive
1132           { K.inductive_id = gen_id inductive_prefix seed;
1133             K.inductive_name = n;
1134             K.inductive_kind = b;
1135             K.inductive_type = ty;
1136             K.inductive_constructors = build_constructors seed l
1137            }
1138
1139 and
1140     build_constructors seed l =
1141      let module K = Content in
1142       List.map
1143        (fun (n,t) ->
1144            { K.dec_name = Some n;
1145              K.dec_id = gen_id declaration_prefix seed;
1146              K.dec_inductive = false;
1147              K.dec_aref = "";
1148              K.dec_type = t
1149            }) l
1150 ;;
1151
1152 (*
1153 and 'term cinductiveType =
1154  id * string * bool * 'term *                (* typename, inductive, arity *)
1155    'term cconstructor list                   (*  constructors        *)
1156
1157 and 'term cconstructor =
1158  string * 'term
1159 *)
1160
1161