matita/components/ng_tactics/nDestructTac.ml

   1 (* Copyright (C) 2002, 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 (* $Id: destructTactic.ml 9774 2009-05-15 19:37:08Z sacerdot $ *)
  27
  28 open NTacStatus
  29 open Continuationals.Stack
  30
  31 let debug = true
  32 let pp =
  33   if debug then (fun x -> prerr_endline (Lazy.force x)) else (fun _ -> ())
  34
  35 let fresh_name =
  36  let i = ref 0 in
  37  function () ->
  38   incr i;
  39   "z" ^ string_of_int !i
  40 ;;
  41
  42 let mk_id id =
  43  let id = if id = "_" then fresh_name () else id in
  44   NotationPt.Ident (id,None)
  45 ;;
  46
  47 let mk_sym s = NotationPt.Symbol (s,0);;
  48
  49 let rec mk_prods l t =
  50   match l with
  51     [] -> t
  52   | hd::tl -> NotationPt.Binder (`Forall, (mk_id hd, None), mk_prods tl t)
  53 ;;
  54
  55 let mk_appl =
  56  function
  57     [] -> assert false
  58   | [x] -> x
  59   | l -> NotationPt.Appl l
  60 ;;
  61
  62 let rec iter f n acc =
  63   if n < 0 then acc
  64   else iter f (n-1) (f n acc)
  65 ;;
  66
  67 let subst_metasenv_and_fix_names status =
  68   let u,h,metasenv, subst,o = status#obj in
  69   let o =
  70     NCicUntrusted.map_obj_kind ~skip_body:true
  71      (NCicUntrusted.apply_subst status subst []) o
  72   in
  73    status#set_obj(u,h,NCicUntrusted.apply_subst_metasenv status subst metasenv,subst,o)
  74 ;;
  75
  76 (* needed to workaround a weakness of the refiner? *)
  77 let rec generalize0_tac tl s =
  78   match tl with
  79   | [] -> s
  80   | t0::tl0 -> NTactics.generalize0_tac [t0] (generalize0_tac tl0 s)
  81 ;;
  82
  83
  84 (* input: nome della variabile riscritta
  85  * output: lista dei nomi delle variabili il cui tipo dipende dall'input *)
  86 let cascade_select_in_ctx status ~subst ctx skip iname =
  87   let lctx, rctx = HExtlib.split_nth (iname - 1) ctx in
  88   let lctx = List.rev lctx in
  89   let rec rm_last = function
  90       [] | [_] -> []
  91     | hd::tl -> hd::(rm_last tl)
  92   in
  93
  94   let indices,_ = List.fold_left
  95        (fun (acc,context) item ->
  96           match item with
  97             | n,(NCic.Decl s | NCic.Def (s,_))
  98                   when (not (List.for_all (fun x -> NCicTypeChecker.does_not_occur status ~subst context (x-1) x s) acc)
  99                    && not (List.mem n skip)) ->
 100                 List.iter (fun m -> pp (lazy ("acc has " ^ (string_of_int m)))) acc;
 101                 pp (lazy ("acc occurs in the type of " ^ n));
 102                 (1::List.map ((+) 1) acc, item::context)
 103             | _ -> (List.map ((+) 1) acc, item::context))
 104        ([1], rctx) lctx in
 105     let indices = rm_last indices in
 106     let res = List.map (fun n -> let s,_ = List.nth ctx (n-1) in s) indices in
 107     List.iter (fun n -> pp (lazy n)) res;
 108     pp (lazy (status#ppcontext ~metasenv:[] ~subst ctx));
 109     res, indices
 110 ;;
 111
 112 let rec mk_fresh_name ctx firstch n =
 113   let candidate = (String.make 1 firstch) ^ (string_of_int n) in
 114   if (List.for_all (fun (s,_) -> s <> candidate) ctx) then candidate
 115   else mk_fresh_name ctx firstch (n+1)
 116 ;;
 117
 118 let arg_list nleft t =
 119   let rec drop_prods n t =
 120     if n <= 0 then t
 121     else match t with
 122       | NCic.Prod (_,_,ta) -> drop_prods (n-1) ta
 123       | _ -> raise (Failure "drop_prods")
 124   in
 125   let rec aux = function
 126     | NCic.Prod (_,so,ta) -> so::aux ta
 127     | _ -> []
 128   in aux (drop_prods nleft t)
 129 ;;
 130
 131 let nargs it nleft consno =
 132   pp (lazy (Printf.sprintf "nargs %d %d" nleft consno));
 133   let _,indname,_,cl = it in
 134   let _,_,t_k = List.nth cl consno in
 135   List.length (arg_list nleft t_k) ;;
 136
 137 let default_pattern = "",0,(None,[],Some NotationPt.UserInput);;
 138 let prod_pattern =
 139   "",0,(None,[],Some NotationPt.Binder
 140     (`Pi, (mk_id "_",Some (NotationPt.Appl
 141       [ NotationPt.Implicit `JustOne
 142       ; NotationPt.Implicit `JustOne
 143       ; NotationPt.UserInput
 144       ; NotationPt.Implicit `JustOne ])),
 145   NotationPt.Implicit `JustOne));;
 146
 147 let prod_pattern_jm =
 148   "",0,(None,[],Some NotationPt.Binder
 149     (`Pi, (mk_id "_",Some (NotationPt.Appl
 150       [ NotationPt.Implicit `JustOne
 151       ; NotationPt.Implicit `JustOne
 152       ; NotationPt.UserInput
 153       ; NotationPt.Implicit `JustOne
 154       ; NotationPt.Implicit `JustOne ])),
 155   NotationPt.Implicit `JustOne));;
 156
 157 let hp_pattern n =
 158   "",0,(None,[n, NotationPt.Appl
 159       [ NotationPt.Implicit `JustOne
 160       ; NotationPt.Implicit `JustOne
 161       ; NotationPt.UserInput
 162       ; NotationPt.Implicit `JustOne ] ],
 163   None);;
 164
 165 let hp_pattern_jm n =
 166   "",0,(None,[n, NotationPt.Appl
 167       [ NotationPt.Implicit `JustOne
 168       ; NotationPt.Implicit `JustOne
 169       ; NotationPt.UserInput
 170       ; NotationPt.Implicit `JustOne
 171       ; NotationPt.Implicit `JustOne ] ],
 172   None);;
 173
 174 (* creates the discrimination = injection+contradiction principle *)
 175 exception ConstructorTooBig of string;;
 176
 177 let mk_discriminator ~use_jmeq ?(force=false) name it leftno status baseuri =
 178   let itnargs =
 179     let _,_,arity,_ = it in
 180     List.length (arg_list 0 arity) in
 181   let _,itname,_,_ = it in
 182   let params = List.map (fun x -> "a" ^ string_of_int x) (HExtlib.list_seq 1 (itnargs+1)) in
 183   let xyty = mk_appl (List.map mk_id (itname::params)) in
 184
 185   (* PHASE 1: derive the type of the discriminator (we'll name it "principle") *)
 186
 187   let mk_eq tys ts us es n deps =
 188     if use_jmeq then
 189       mk_appl [mk_id "jmeq";
 190                NotationPt.Implicit `JustOne; List.nth ts n;
 191                NotationPt.Implicit `JustOne; List.nth us n]
 192     else
 193     (* we use deps in an attempt to remove unnecessary rewritings when the type
 194        is not maximally dependent *)
 195     (* eqty = Tn u0 e0...un-1 en-1 *)
 196     let eqty = mk_appl
 197                  (List.nth tys n :: iter
 198                    (fun i acc ->
 199                       if (List.mem (List.nth ts i) deps)
 200                          then List.nth us i::
 201                               List.nth es i::acc
 202                          else acc)
 203                    (n-1) []) in
 204
 205     (* params = [T0;t0;...;Tn;tn;u0;e0;...;un-1;en-1] *)
 206     let params = iter (fun i acc ->
 207                          if (List.mem (List.nth ts i) deps)
 208                             then List.nth tys i ::
 209                                  List.nth ts i :: acc
 210                             else acc) (n-1)
 211                      (List.nth tys n::List.nth ts n::
 212                       iter (fun i acc ->
 213                             if (List.mem (List.nth ts i) deps)
 214                                then List.nth us i::
 215                                     List.nth es i::acc
 216                                else acc) (n-1) []) in
 217     let nrewrites = List.length deps in
 218     mk_appl [mk_id "eq"; eqty;
 219              mk_appl (mk_id ("R" ^ string_of_int nrewrites) :: params);
 220              List.nth us n]
 221
 222   in
 223
 224   let _,_,_,cl = it in
 225
 226   let kname (*it*) j =
 227     let _,name,_ = List.nth cl j in
 228     name
 229   in
 230
 231   let branch i j ts us deps =
 232     let nargs = nargs it leftno i in
 233     let es = List.map (fun x -> mk_id ("e" ^ string_of_int x)) (HExtlib.list_seq 0 nargs) in
 234     let ndepargs k =
 235       let tk = List.nth ts k in
 236       List.length (List.assoc tk deps)
 237     in
 238     let tys = List.map
 239                 (fun x ->
 240                   iter
 241                   (fun i acc ->
 242                     NotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None),
 243                     NotationPt.Binder (`Lambda, (mk_id ("p" ^ string_of_int i), None),
 244                     acc))) ((ndepargs x) - 1)
 245                  (NotationPt.Implicit (`Tagged ("T" ^ (string_of_int x)))))
 246                (HExtlib.list_seq 0 nargs) in
 247     let tys = tys @
 248       [iter (fun i acc ->
 249         NotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None),
 250         NotationPt.Binder (`Lambda, (mk_id ("p" ^ string_of_int i), None),
 251         acc))) (nargs-1)
 252         (mk_appl [mk_id "eq"; NotationPt.Implicit `JustOne;
 253           mk_appl (mk_id (kname i)::
 254            List.map (fun x -> mk_id ("x" ^string_of_int x))
 255               (HExtlib.list_seq 0 (List.length ts)));
 256               mk_appl (mk_id (kname j)::us)])]
 257     in
 258     (** NotationPt.Binder (`Lambda, (mk_id "e",
 259       Some (mk_appl
 260         [mk_id "eq";
 261          NotationPt.Implicit `JustOne;
 262          mk_appl (mk_id (kname it i)::ts);
 263          mk_appl (mk_id (kname it j)::us)])),
 264     let ts = ts @ [mk_id "e"] in
 265     let refl2 = mk_appl
 266                   [mk_id "refl";
 267                    NotationPt.Implicit `JustOne;
 268                    mk_appl (mk_id (kname it j)::us)] in
 269     let us = us @ [refl2] in *)
 270     NotationPt.Binder (`Forall, (mk_id "P", Some (NotationPt.Sort (`NType "1") )),
 271       if i = j then
 272        NotationPt.Binder (`Forall, (mk_id "_",
 273         Some (iter (fun i acc ->
 274               NotationPt.Binder (`Forall, (List.nth es i, Some (mk_eq tys ts us es i (List.assoc (List.nth ts i) deps))), acc))
 275               (nargs-1)
 276               (** (NotationPt.Binder (`Forall, (mk_id "_",
 277                 Some (mk_eq tys ts us es nargs)),*)
 278                 (mk_id "P"))), mk_id "P")
 279       else mk_id "P")
 280   in
 281
 282   let inner i ts deps =
 283     NotationPt.Case
 284               (mk_id "y",None,
 285                (*Some (NotationPt.Binder (`Lambda, (mk_id "y",None),
 286                  NotationPt.Binder (`Forall, (mk_id "_", Some
 287                  (mk_appl [mk_id "eq";NotationPt.Implicit
 288                  `JustOne;(*NotationPt.Implicit `JustOne*)
 289                   mk_appl (mk_id (kname it i)::ts);mk_id "y"])),
 290                  NotationPt.Implicit `JustOne )))*)
 291                   None,
 292                   List.map
 293                   (fun j ->
 294                      let nargs_kty = nargs it leftno j in
 295                      let us = iter (fun m acc -> mk_id ("u" ^ (string_of_int m))::acc)
 296                                 (nargs_kty - 1) [] in
 297                      let nones =
 298                        iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
 299                      NotationPt.Pattern (kname j,
 300                                             None,
 301                                             List.combine us nones),
 302                                 branch i j ts us deps)
 303                   (HExtlib.list_seq 0 (List.length cl)))
 304   in
 305   let outer = NotationPt.Case
 306                 (mk_id "x",None,
 307                  None ,
 308                  List.map
 309                    (fun i ->
 310                       let _,_,kty = List.nth cl i in
 311                       let nargs_kty = nargs it leftno i in
 312                       let ts = iter (fun m acc -> ("t" ^ (string_of_int m))::acc)
 313                                  (nargs_kty - 1) [] in
 314                       (* this context is used to compute dependencies between constructor arguments *)
 315                       let kctx = List.map2 (fun t ty -> t, NCic.Decl ty) (List.rev ts) (List.rev (arg_list leftno kty)) in
 316                       let ts = List.map mk_id ts in
 317                       (* compute graph of dependencies *)
 318                       let deps,_ = List.fold_left
 319                         (fun (acc,i) (t,_) ->
 320                          let name,_ = List.nth kctx (i-1) in
 321                          (name,fst (cascade_select_in_ctx status ~subst:[] kctx [] i))::acc,i+1) ([],1) kctx
 322                       in
 323                       (* transpose graph *)
 324                       let deps = List.fold_left
 325                         (fun acc (t,_) ->
 326                            let t_deps = List.map fst (List.filter (fun (name,rev_deps) -> List.mem t rev_deps) deps) in
 327                            (t,t_deps)::acc) [] deps
 328                       in
 329                       prerr_endline ("deps dump!");
 330                       List.iter (fun (x,xs) -> prerr_endline (x ^ ": " ^ (String.concat ", " xs))) deps;
 331                       let deps = List.map (fun (x,xs) -> mk_id x, (List.map mk_id) xs) deps in
 332                       let max_dep = List.fold_left max 0 (List.map (fun (_,xs) -> List.length xs) deps) in
 333                       if (max_dep > 4 && not use_jmeq && not force) then raise (ConstructorTooBig (kname i));
 334
 335                      let nones =
 336                        iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
 337                       NotationPt.Pattern (kname i,
 338                                              None,
 339                                              List.combine ts nones),
 340                                 inner i ts deps)
 341                    (HExtlib.list_seq 0 (List.length cl))) in
 342   let principle =
 343     mk_prods params (NotationPt.Binder (`Forall, (mk_id "x",
 344                                Some xyty),
 345                            NotationPt.Binder (`Forall, (mk_id "y", Some xyty),
 346                             (if use_jmeq then
 347                              NotationPt.Binder (`Forall, (mk_id "e",
 348                               Some (mk_appl
 349                                [mk_sym "jmsimeq"; NotationPt.Implicit `JustOne; mk_id "x";
 350                                                   NotationPt.Implicit `JustOne; mk_id "y"])),
 351                                                   outer)
 352                             else
 353                               NotationPt.Binder (`Forall, (mk_id "e",
 354                               Some (mk_appl [mk_sym "eq";NotationPt.Implicit `JustOne; mk_id "x"; mk_id "y"])),
 355                              outer)))))
 356   in
 357   pp (lazy ("discriminator = " ^ (NotationPp.pp_term status principle)));
 358
 359   (* PHASE 2: create the object for the proof of the principle: we'll name it
 360    * "theorem" *)
 361   let status, theorem =
 362    GrafiteDisambiguate.disambiguate_nobj status ~baseuri
 363     (baseuri ^ name ^ ".def",0,
 364       NotationPt.Theorem
 365        (`Theorem,name,principle,
 366          Some (NotationPt.Implicit (`Tagged "inv")),`DiscriminationPrinciple))
 367   in
 368   let uri,height,nmenv,nsubst,nobj = theorem in
 369   let ninitial_stack = Continuationals.Stack.of_nmetasenv nmenv in
 370   let status = status#set_obj theorem in
 371   let status = status#set_stack ninitial_stack in
 372   let status = subst_metasenv_and_fix_names status in
 373
 374   (* PHASE 3: we finally prove the discrimination principle *)
 375   let dbranch it ~use_jmeq leftno consno =
 376     let refl_id = mk_sym "refl" in
 377     pp (lazy (Printf.sprintf "dbranch %d %d" leftno consno));
 378     let nlist = HExtlib.list_seq 0 (nargs it leftno consno) in
 379     (* (\forall ...\forall P.\forall DH : ( ... = ... -> P). P) *)
 380     let params = List.map (fun x -> NTactics.intro_tac ("a" ^ string_of_int x)) nlist in
 381         (* NTactics.reduce_tac ~reduction:(`Normalize true)
 382          * ~where:default_pattern::*)
 383         params @ [
 384         NTactics.intro_tac "P";
 385         NTactics.intro_tac "DH";
 386         NTactics.apply_tac ("",0,mk_id "DH");
 387         NTactics.apply_tac ("",0,refl_id); (* well, it works even if no goal is selected after applying DH... *)
 388     ] in
 389   let dbranches it ~use_jmeq leftno =
 390     pp (lazy (Printf.sprintf "dbranches %d" leftno));
 391     let nbranches = List.length cl in
 392     let branches = iter (fun n acc ->
 393       let m = nbranches - n - 1 in
 394       if m = 0 then acc @ (dbranch it ~use_jmeq leftno m)
 395       else acc @ NTactics.shift_tac :: (dbranch it ~use_jmeq
 396       leftno m))
 397       (nbranches-1) [] in
 398     if nbranches > 1 then
 399          NTactics.branch_tac ~force:false:: branches @ [NTactics.merge_tac]
 400     else branches
 401   in
 402   let print_tac s status = pp s ; status in
 403
 404   let status =
 405    NTactics.block_tac (
 406     [print_tac (lazy "ci sono") (*;
 407      NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern *)
 408     ]
 409   @ List.map (fun x -> NTactics.intro_tac x) params @
 410     [NTactics.intro_tac "x";
 411      NTactics.intro_tac "y";
 412      NTactics.intro_tac "Deq";
 413     print_tac (lazy "ci sono 2");
 414      NTactics.rewrite_tac ~dir:`RightToLeft ~what:("",0,mk_id "Deq") ~where:default_pattern;
 415      NTactics.cases_tac ~what:("",0,mk_id "x") ~where:default_pattern]
 416   @ dbranches it ~use_jmeq leftno) status
 417   in status, status#obj
 418 ;;
 419
 420 let hd_of_term = function
 421   | NCic.Appl (hd::_) -> hd
 422   | t -> t
 423 ;;
 424
 425 let name_of_rel ~context rel =
 426   let s, _ = List.nth context (rel-1) in s
 427 ;;
 428
 429 (* let lookup_in_ctx ~context n =
 430   List.nth context ((List.length context) - n - 1)
 431 ;;*)
 432
 433 let discriminate_tac ~context cur_eq status =
 434   pp (lazy (Printf.sprintf "discriminate: equation %s" (name_of_rel ~context cur_eq)));
 435
 436
 437   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
 438   let _,ctx' = HExtlib.split_nth cur_eq context in
 439   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
 440   let status, s = term_of_cic_term status s ctx' in
 441   let status,it,use_jmeq =
 442     let it,use_jmeq = match s with
 443       | NCic.Appl [_;it;_;_] -> it,false
 444       | NCic.Appl [_;it;_;_;_] -> it,true
 445       | _ -> assert false in
 446     (* XXX: serve? ho già fatto whd *)
 447     let status, it = whd status ctx' (mk_cic_term ctx' it) in
 448     let status, it = term_of_cic_term status it ctx' in
 449     let _uri,indtyno,its = match it with
 450       | NCic.Const (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r)
 451       | NCic.Appl (NCic.Const
 452           (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r)::_) ->
 453         uri, indtyno, NCicEnvironment.get_checked_indtys status r
 454       | _ -> pp (lazy ("discriminate: indty ="  ^ status#ppterm
 455                   ~metasenv:[] ~subst:[] ~context:[] it)) ; assert false in
 456     let _,_,its,_,_ = its in
 457     status,List.nth its indtyno, use_jmeq
 458   in
 459
 460   let itnargs =
 461     let _,_,arity,_ = it in
 462     List.length (arg_list 0 arity) in
 463   let _,itname,_,_ = it in
 464   let params = List.map (fun x -> "a" ^ string_of_int x) (HExtlib.list_seq 1 (itnargs+1)) in
 465   let principle_name =
 466     if use_jmeq then itname ^ "_jmdiscr"
 467     else itname ^ "_discr"
 468   in
 469   pp (lazy ("apply (" ^ principle_name ^ " " ^
 470             (String.concat "" (HExtlib.mk_list "?" (List.length params + 2))) ^
 471             " " ^ eq_name ^ ")"));
 472   NTactics.apply_tac ("",0,mk_appl ([mk_id principle_name]@
 473                                 HExtlib.mk_list (NotationPt.Implicit `JustOne) (List.length params + 2) @
 474                                 [mk_id eq_name ])) status
 475 ;;
 476
 477 let saturate_skip status context skip =
 478   HExtlib.list_uniq
 479     (List.fold_left
 480       (fun acc x ->
 481          let ix = HExtlib.list_index ((=) x) (List.map fst context)
 482          in match ix with
 483          | None -> acc
 484          | Some (i,_) ->
 485             fst (cascade_select_in_ctx status ~subst:(get_subst status) context [] (i+1)) @ acc) skip skip)
 486 ;;
 487
 488 let subst_tac ~context ~dir skip cur_eq =
 489   fun status as oldstatus ->
 490   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
 491   let _,ctx' = HExtlib.split_nth cur_eq context in
 492   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
 493   let status, s = term_of_cic_term status s ctx' in
 494   let skip = saturate_skip status context skip in
 495   pp (lazy (Printf.sprintf "subst: equation %s" eq_name));
 496     let l, r = match s with
 497       | NCic.Appl [_;_;t1;t2] | NCic.Appl [_;_;t1;_;t2] -> t1,t2
 498       | _ -> assert false in
 499     let var = match dir with
 500       | `LeftToRight -> l
 501       | `RightToLeft -> r in
 502     (* let var = match var with
 503       | NCic.Rel i -> i
 504       | _ -> assert false in *)
 505     let names_to_gen, _ =
 506       match var with
 507       | NCic.Rel var ->
 508         cascade_select_in_ctx status ~subst:(get_subst status) context skip (var+cur_eq)
 509       | _ -> cascade_select_in_ctx status ~subst:(get_subst status) context skip cur_eq in
 510     let varname = match var with
 511       | NCic.Rel var ->
 512           let name,_ = List.nth context (var+cur_eq-1) in
 513           HLog.warn (Printf.sprintf "destruct: trying to remove variable: %s" name);
 514           [name]
 515       | _ -> []
 516     in
 517     let names_to_gen = List.filter (fun n -> n <> eq_name) names_to_gen in
 518     if (List.exists (fun x -> List.mem x skip) names_to_gen)
 519       then oldstatus
 520     else
 521     let gen_tac x =
 522       (fun s ->
 523       let x' = String.concat " " x in
 524       let x = List.map mk_id x in
 525       (* let s = NTactics.print_tac false ("@generalize " ^ x') s in *)
 526       generalize0_tac x s) in
 527     NTactics.block_tac (
 528                 (* (List.map gen_tac names_to_gen)@ *)
 529             [gen_tac (List.rev names_to_gen);
 530                         NTactics.clear_tac names_to_gen;
 531                  NTactics.rewrite_tac ~dir
 532                    ~what:("",0,mk_id eq_name) ~where:default_pattern;
 533 (*                 NTactics.reduce_tac ~reduction:(`Normalize true)
 534                    ~where:default_pattern;*)
 535                  (* XXX: temo che la clear multipla funzioni bene soltanto se
 536                   * gli identificatori sono nell'ordine giusto.
 537                   * Per non saper né leggere né scrivere, usiamo due clear
 538                   * invece di una *)
 539                  NTactics.try_tac (NTactics.clear_tac [eq_name]);
 540                  NTactics.try_tac (NTactics.clear_tac varname);
 541 ]@
 542                  (List.map NTactics.intro_tac (List.rev names_to_gen))) status
 543 ;;
 544
 545 let clearid_tac ~context skip cur_eq =
 546   fun status ->
 547   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
 548   let _,ctx' = HExtlib.split_nth cur_eq context in
 549   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
 550   let status, s = term_of_cic_term status s ctx' in
 551   let skip = saturate_skip status context skip in
 552
 553   pp (lazy (Printf.sprintf "clearid: equation %s" eq_name));
 554   let streicher_id = mk_id "streicherK" in
 555   let names_to_gen, _ =
 556     cascade_select_in_ctx status ~subst:(get_subst status) context skip cur_eq in
 557   let gen_tac x = generalize0_tac (List.map mk_id x) in
 558
 559   match s with
 560   (* jmeq *)
 561   | NCic.Appl [_;_;_;_;_] ->
 562       let names_to_gen = List.rev names_to_gen in
 563       (*let gen_eq = NTactics.generalize_tac
 564        ~where:("",0,(Some (mk_appl [mk_id "jmeq_to_eq";
 565                                     NotationPt.Implicit `JustOne;
 566                                     NotationPt.Implicit `JustOne;
 567                                     NotationPt.Implicit `JustOne;
 568                                     mk_id eq_name]),[], Some
 569                                     NotationPt.UserInput)) in*)
 570       let gen_eq = generalize0_tac
 571                           [mk_appl [mk_id "jmeq_to_eq";
 572                                     NotationPt.Implicit `JustOne;
 573                                     NotationPt.Implicit `JustOne;
 574                                     NotationPt.Implicit `JustOne;
 575                                     mk_id eq_name]] in
 576       NTactics.block_tac ((gen_tac (List.rev names_to_gen))::gen_eq::
 577                   [NTactics.clear_tac names_to_gen;
 578                    NTactics.try_tac (NTactics.clear_tac [eq_name]);
 579                    NTactics.apply_tac ("",0, mk_appl [streicher_id;
 580                                                     NotationPt.Implicit `JustOne;
 581                                                     NotationPt.Implicit `JustOne;
 582                                                     NotationPt.Implicit `JustOne;
 583                                                     NotationPt.Implicit `JustOne]);
 584                    ] @
 585                    (List.map NTactics.intro_tac names_to_gen)) status
 586
 587     (* leibniz *)
 588   | NCic.Appl [_;_;_;_] ->
 589       begin
 590        let names_to_gen, _ =
 591          cascade_select_in_ctx status ~subst:(get_subst status) context skip cur_eq in
 592        let names_to_gen = eq_name :: (List.rev names_to_gen) in
 593        NTactics.block_tac ((gen_tac names_to_gen)::
 594                    [NTactics.clear_tac names_to_gen;
 595                     NTactics.apply_tac ("",0, mk_appl [streicher_id;
 596                                                     NotationPt.Implicit `JustOne;
 597                                                     NotationPt.Implicit `JustOne;
 598                                                     NotationPt.Implicit `JustOne;
 599                                                     NotationPt.Implicit `JustOne])
 600    (*                 NTactics.reduce_tac ~reduction:(`Normalize true)
 601                       ~where:default_pattern *)
 602                     ] @
 603                     let names_to_intro = List.tl names_to_gen in
 604                     (List.map NTactics.intro_tac names_to_intro)) status
 605      end
 606   | _ -> assert false
 607
 608 ;;
 609
 610 let get_ctx st goal =
 611     ctx_of (get_goalty st goal)
 612 ;;
 613
 614 (* = select + classify *)
 615 let select_eq ctx acc domain status goal =
 616   let classify ~use_jmeq ~subst ctx' l r =
 617     (* FIXME: metasenv *)
 618     if NCicReduction.are_convertible status ~metasenv:[] ~subst ctx' l r
 619       then status, `Identity
 620       else status, (match hd_of_term l, hd_of_term r with
 621         | NCic.Const (NReference.Ref (_,NReference.Con (_,ki,nleft)) as kref),
 622           NCic.Const (NReference.Ref (_,NReference.Con (_,kj,_))) ->
 623             if ki != kj then `Discriminate (0,true, use_jmeq)
 624             else
 625               let rit = NReference.mk_indty true kref in
 626               let _,_,its,_,itno = NCicEnvironment.get_checked_indtys status rit in
 627               let it = List.nth its itno in
 628               let newprods = nargs it nleft (ki-1) in
 629               `Discriminate (newprods, false, use_jmeq)
 630         | NCic.Rel j, _
 631             when NCicTypeChecker.does_not_occur status ~subst ctx' (j-1) j r
 632               && l = NCic.Rel j -> `Subst `LeftToRight
 633         | _, NCic.Rel j
 634             when NCicTypeChecker.does_not_occur status ~subst ctx' (j-1) j l
 635               && r = NCic.Rel j -> `Subst `RightToLeft
 636         | (NCic.Rel _, _ | _, NCic.Rel _ ) -> `Cycle (* could be a blob too... *)
 637         | _ -> `Blob) in
 638   let rec aux i =
 639     try
 640       let index = List.length ctx - i in
 641       pp (lazy ("provo classify di index = " ^string_of_int index));
 642       match (List.nth ctx (index - 1)) with
 643       | n, (NCic.Decl ty | NCic.Def (ty,_)) ->
 644           (let _,ctx_ty = HExtlib.split_nth index ctx in
 645            let status, ty = NTacStatus.whd status ctx_ty (mk_cic_term ctx_ty ty) in
 646            let status, ty = term_of_cic_term status ty ctx_ty in
 647            pp (lazy (Printf.sprintf "select_eq tries %s" (status#ppterm ~context:ctx_ty ~subst:[] ~metasenv:[] ty)));
 648            let status, kind = match ty with
 649            | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;_;l;r]
 650                when NUri.name_of_uri u = "eq" ->
 651                classify ~use_jmeq:false ~subst:(get_subst status) ctx_ty l r
 652            | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;lty;l;rty;r]
 653                when NUri.name_of_uri u = "jmeq" &&
 654                  NCicReduction.are_convertible status ~metasenv:[]
 655                    ~subst:(get_subst status) ctx_ty lty rty
 656                -> classify ~use_jmeq:true ~subst:(get_subst status) ctx_ty l r
 657            | _ -> status, `NonEq
 658            in match kind with
 659               | `Identity ->
 660                   let status, goalty = term_of_cic_term status (get_goalty status goal) ctx in
 661                      status, Some (List.length ctx - i), kind
 662               | `Cycle | `Blob | `NonEq -> aux (i+1) (* XXX: skip cyclic/blob equations for now *)
 663               | _ ->
 664                  if (List.for_all (fun x -> x <> n) acc) &&
 665                     (List.exists (fun x -> x = n) domain)
 666                  then status, Some (List.length ctx - i), kind
 667                  else aux (i+1))
 668     with Failure _ | Invalid_argument _ -> status, None, `Blob
 669   in aux 0
 670 ;;
 671
 672 let tagged_intro_tac curtag name =
 673   match curtag with
 674   | `Notag -> NTactics.intro_tac name
 675   | `Eq use_jmeq ->
 676       NTactics.block_tac
 677         [ NTactics.intro_tac name
 678         ; NTactics.reduce_tac
 679             ~reduction:(`Whd true) ~where:((if use_jmeq then hp_pattern_jm else hp_pattern) name) ]
 680
 681 (*        status in
 682       distribute_tac (fun s g ->
 683         let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
 684         let _,ctx' = HExtlib.split_nth cur_eq context in
 685         let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
 686         let status, s = term_of_cic_term status s ctx' in
 687         let use_jmeq =
 688           match s with
 689           | NCic.Appl [_;it;t1;t2] -> false
 690           | NCic.Appl [_;it;t1;_;t2] -> true
 691           | _ -> assert false in
 692       ) status
 693     let it, t1, t2, use_jmeq = match s with
 694       | NCic.Appl [_;it;t1;t2] -> it,t1,t2,false
 695       | NCic.Appl [_;it;t1;_;t2] -> it,t1,t2,true
 696       | _ -> assert false in
 697            [ NTactics.intro_tac name
 698            ; NTactics.reduce_tac ~reduction:(`Whd true) ~where:prod_pattern ]*)
 699 ;;
 700
 701 let rec destruct_tac0 tags acc domain skip status goal =
 702   let pptag = function
 703     | `Eq false -> "eq"
 704     | `Eq true -> "jmeq"
 705     | `Notag -> "reg"
 706   in
 707   let pptags tags = String.concat ", " (List.map pptag tags) in
 708   let ctx = get_ctx status goal in
 709   let subst = get_subst status in
 710   let get_newgoal os ns ogoal =
 711     let go, gc = NTactics.compare_statuses ~past:os ~present:ns in
 712     let go' = ([ogoal] @- gc) @+ go in
 713       match go' with [] -> assert false | g::_ -> g
 714   in
 715   let status, selection, kind  = select_eq ctx acc domain status goal in
 716   pp (lazy ("destruct: acc is " ^ String.concat "," acc ));
 717   match selection, kind with
 718   | None, _ ->
 719     pp (lazy (Printf.sprintf
 720        "destruct: no selection, context is %s, stack is %s"
 721        (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
 722      (match tags with
 723       | [] -> status
 724       | curtag::tags' ->
 725         let fresh = mk_fresh_name ctx 'e' 0 in
 726         let status' = NTactics.exec (tagged_intro_tac curtag fresh) status goal in
 727         destruct_tac0 tags' acc (fresh::domain) skip status'
 728           (get_newgoal status status' goal))
 729   | Some cur_eq, `Discriminate (newprods,conflict,use_jmeq) ->
 730     pp (lazy (Printf.sprintf
 731       "destruct: discriminate - nselection is %d, context is %s,stack is %s"
 732        cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
 733       let status' = NTactics.exec (discriminate_tac ~context:ctx cur_eq) status goal in
 734       if conflict then status'
 735       else
 736         let newtags = HExtlib.mk_list (`Eq use_jmeq) newprods in
 737         destruct_tac0 (newtags@tags)
 738              (name_of_rel ~context:ctx cur_eq::acc)
 739              (List.filter (fun x -> x <> name_of_rel ~context:ctx cur_eq) domain)
 740              skip
 741              status' (get_newgoal status status' goal)
 742   | Some cur_eq, `Subst dir ->
 743     pp (lazy (Printf.sprintf
 744       "destruct: subst - selection is %d, context is %s, stack is %s"
 745         cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
 746     let status' = NTactics.exec (subst_tac ~context:ctx ~dir skip cur_eq) status goal in
 747       pp (lazy (Printf.sprintf " ctx after subst = %s" (status#ppcontext ~metasenv:[] ~subst (get_ctx status' (get_newgoal status status' goal)))));
 748     let eq_name,_ = List.nth ctx (cur_eq-1) in
 749     let newgoal = get_newgoal status status' goal in
 750     let has_cleared =
 751      try
 752        let _ = NTactics.find_in_context eq_name (get_ctx status' newgoal) in false
 753      with
 754       | Sys.Break as e -> raise e
 755       |_ -> true in
 756     let rm_eq b l = if b then List.filter (fun x -> x <> eq_name) l else l in
 757     let acc = rm_eq has_cleared acc in
 758     let skip = rm_eq has_cleared skip in
 759     let domain = rm_eq has_cleared domain in
 760       destruct_tac0 tags acc domain skip status' newgoal
 761  | Some cur_eq, `Identity ->
 762     pp (lazy (Printf.sprintf
 763       "destruct: identity - selection is %d, context is %s, stack is %s"
 764         cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
 765       let eq_name,_ = List.nth ctx (cur_eq-1) in
 766       let status' = NTactics.exec (clearid_tac ~context:ctx skip cur_eq) status goal in
 767       let newgoal = get_newgoal status status' goal in
 768       let has_cleared =
 769        try
 770          let _ = NTactics.find_in_context eq_name (get_ctx status' newgoal) in false
 771        with
 772          | Sys.Break as e -> raise e
 773          | _ -> true in
 774       let rm_eq b l = if b then List.filter (fun x -> x <> eq_name) l else l in
 775       let acc = rm_eq has_cleared acc in
 776       let skip = rm_eq has_cleared skip in
 777       let domain = rm_eq has_cleared domain in
 778         destruct_tac0 tags acc domain skip status' newgoal
 779   | Some cur_eq, `Cycle -> (* TODO, should never happen *)
 780     pp (lazy (Printf.sprintf
 781       "destruct: cycle - selection is %d, context is %s, stack is %s"
 782         cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
 783       assert false
 784   | Some cur_eq, `Blob ->
 785     pp (lazy (Printf.sprintf
 786       "destruct: blob - selection is %d, context is %s, stack is %s"
 787       cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
 788       assert false
 789   | _ -> assert false
 790 ;;
 791
 792 let destruct_tac dom skip s =
 793   NTactics.distribute_tac
 794     (fun s' g ->
 795      let ctx = get_ctx s' g in
 796      let domain = match dom with
 797        | None -> List.map (fun (n,_) -> n) ctx
 798        | Some l -> l
 799      in
 800      destruct_tac0 [] [] domain skip s' g) s;;