helm/software/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   CicNotationPt.Ident (id,None)
  45 ;;
  46
  47 let rec mk_prods l t =
  48   match l with
  49     [] -> t
  50   | hd::tl -> CicNotationPt.Binder (`Forall, (mk_id hd, None), mk_prods tl t)
  51 ;;
  52
  53 let mk_appl =
  54  function
  55     [] -> assert false
  56   | [x] -> x
  57   | l -> CicNotationPt.Appl l
  58 ;;
  59
  60 let rec iter f n acc =
  61   if n < 0 then acc
  62   else iter f (n-1) (f n acc)
  63 ;;
  64
  65 let subst_metasenv_and_fix_names status =
  66   let u,h,metasenv, subst,o = status#obj in
  67   let o =
  68     NCicUntrusted.map_obj_kind ~skip_body:true
  69      (NCicUntrusted.apply_subst subst []) o
  70   in
  71    status#set_obj(u,h,NCicUntrusted.apply_subst_metasenv subst metasenv,subst,o)
  72 ;;
  73
  74 (* input: nome della variabile riscritta
  75  * output: lista dei nomi delle variabili il cui tipo dipende dall'input *)
  76 let cascade_select_in_ctx ~subst ctx iname =
  77   let lctx, rctx = HExtlib.split_nth (iname - 1) ctx in
  78   let lctx = List.rev lctx in
  79   let rec rm_last = function
  80       [] | [_] -> []
  81     | hd::tl -> hd::(rm_last tl)
  82   in
  83
  84   let indices,_ = List.fold_left
  85        (fun (acc,context) item ->
  86           match item with
  87             | n,(NCic.Decl s | NCic.Def (s,_))
  88                   when not (List.for_all (fun x -> NCicTypeChecker.does_not_occur ~subst context (x-1) x s) acc) ->
  89                 List.iter (fun m -> pp (lazy ("acc has " ^ (string_of_int m)))) acc;
  90                 pp (lazy ("acc occurs in the type of " ^ n));
  91                 (1::List.map ((+) 1) acc, item::context)
  92             | _ -> (List.map ((+) 1) acc, item::context))
  93        ([1], rctx) lctx in
  94     let indices = rm_last indices in
  95     let res = List.map (fun n -> let s,_ = List.nth ctx (n-1) in s) indices in
  96     List.iter (fun n -> pp (lazy n)) res;
  97     pp (lazy (NCicPp.ppcontext ~metasenv:[] ~subst ctx));
  98     res, indices
  99 ;;
 100
 101 let rec mk_fresh_name ctx firstch n =
 102   let candidate = (String.make 1 firstch) ^ (string_of_int n) in
 103   if (List.for_all (fun (s,_) -> s <> candidate) ctx) then candidate
 104   else mk_fresh_name ctx firstch (n+1)
 105 ;;
 106
 107 let arg_list nleft t =
 108   let rec drop_prods n t =
 109     if n <= 0 then t
 110     else match t with
 111       | NCic.Prod (_,_,ta) -> drop_prods (n-1) ta
 112       | _ -> raise (Failure "drop_prods")
 113   in
 114   let rec aux = function
 115     | NCic.Prod (_,so,ta) -> so::aux ta
 116     | _ -> []
 117   in aux (drop_prods nleft t)
 118 ;;
 119
 120 let nargs it nleft consno =
 121   pp (lazy (Printf.sprintf "nargs %d %d" nleft consno));
 122   let _,indname,_,cl = it in
 123   let _,_,t_k = List.nth cl consno in
 124   List.length (arg_list nleft t_k) ;;
 125
 126 let default_pattern = "",0,(None,[],Some CicNotationPt.UserInput);;
 127
 128 (* returns the discrimination = injection+contradiction principle *)
 129
 130 let mk_discriminator it ~use_jmeq nleft xyty status =
 131   let _,indname,_,cl = it in
 132
 133
 134   let mk_eq tys ts us es n =
 135     if use_jmeq then
 136       mk_appl [mk_id "jmeq";
 137                CicNotationPt.Implicit `JustOne; List.nth ts n;
 138                CicNotationPt.Implicit `JustOne; List.nth us n]
 139     else
 140     (* eqty = Tn u0 e0...un-1 en-1 *)
 141     let eqty = mk_appl
 142                  (List.nth tys n :: iter (fun i acc ->
 143                                            List.nth us i::
 144                                            List.nth es i:: acc)
 145                                      (n-1) []) in
 146
 147     (* params = [T0;t0;...;Tn;tn;u0;e0;un-1;en-1] *)
 148     let params = iter (fun i acc ->
 149                          List.nth tys i ::
 150                          List.nth ts i :: acc) n
 151                      (iter (fun i acc ->
 152                             List.nth us i::
 153                             List.nth es i:: acc) (n-1) []) in
 154     mk_appl [mk_id "eq"; eqty;
 155                         mk_appl (mk_id ("R" ^ string_of_int n) :: params);
 156                         List.nth us n]
 157
 158   in
 159
 160   let kname it j =
 161     let _,_,_,cl = it in
 162     let _,name,_ = List.nth cl j in
 163     name
 164   in
 165
 166   let branch i j ts us =
 167     let nargs = nargs it nleft i in
 168     let es = List.map (fun x -> mk_id ("e" ^ string_of_int x)) (HExtlib.list_seq 0 nargs) in
 169     let tys = List.map
 170                 (fun x -> iter
 171                   (fun i acc ->
 172                     CicNotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None),
 173                     CicNotationPt.Binder (`Lambda, (mk_id ("p" ^ string_of_int i), None),
 174                     acc))) (x-1)
 175                  (CicNotationPt.Implicit (`Tagged ("T" ^ (string_of_int x)))))
 176                (HExtlib.list_seq 0 nargs) in
 177     let tys = tys @
 178       [iter (fun i acc ->
 179         CicNotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None),
 180         CicNotationPt.Binder (`Lambda, (mk_id ("p" ^ string_of_int i), None),
 181         acc))) (nargs-1)
 182         (mk_appl [mk_id "eq"; CicNotationPt.Implicit `JustOne;
 183           mk_appl (mk_id (kname it i)::
 184            List.map (fun x -> mk_id ("x" ^string_of_int x))
 185               (HExtlib.list_seq 0 (List.length ts)));
 186               mk_appl (mk_id (kname it j)::us)])]
 187     in
 188     (** CicNotationPt.Binder (`Lambda, (mk_id "e",
 189       Some (mk_appl
 190         [mk_id "eq";
 191          CicNotationPt.Implicit `JustOne;
 192          mk_appl (mk_id (kname it i)::ts);
 193          mk_appl (mk_id (kname it j)::us)])),
 194     let ts = ts @ [mk_id "e"] in
 195     let refl2 = mk_appl
 196                   [mk_id "refl";
 197                    CicNotationPt.Implicit `JustOne;
 198                    mk_appl (mk_id (kname it j)::us)] in
 199     let us = us @ [refl2] in *)
 200     CicNotationPt.Binder (`Forall, (mk_id "P", Some (CicNotationPt.Sort (`NType "1") )),
 201       if i = j then
 202        CicNotationPt.Binder (`Forall, (mk_id "_",
 203         Some (iter (fun i acc ->
 204               CicNotationPt.Binder (`Forall, (List.nth es i, Some (mk_eq tys ts us es i)), acc))
 205               (nargs-1)
 206               (** (CicNotationPt.Binder (`Forall, (mk_id "_",
 207                 Some (mk_eq tys ts us es nargs)),*)
 208                 (mk_id "P"))), mk_id "P")
 209       else mk_id "P")
 210   in
 211
 212   let inner i ts = CicNotationPt.Case
 213               (mk_id "y",None,
 214                (*Some (CicNotationPt.Binder (`Lambda, (mk_id "y",None),
 215                  CicNotationPt.Binder (`Forall, (mk_id "_", Some
 216                  (mk_appl [mk_id "eq";CicNotationPt.Implicit
 217                  `JustOne;(*CicNotationPt.Implicit `JustOne*)
 218                   mk_appl (mk_id (kname it i)::ts);mk_id "y"])),
 219                  CicNotationPt.Implicit `JustOne )))*)
 220                   None,
 221                   List.map
 222                   (fun j ->
 223                      let nargs_kty = nargs it nleft j in
 224                      let us = iter (fun m acc -> mk_id ("u" ^ (string_of_int m))::acc)
 225                                 (nargs_kty - 1) [] in
 226                      let nones =
 227                        iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
 228                      CicNotationPt.Pattern (kname it j,
 229                                             None,
 230                                             List.combine us nones),
 231                                 branch i j ts us)
 232                   (HExtlib.list_seq 0 (List.length cl)))
 233   in
 234   let outer = CicNotationPt.Case
 235                 (mk_id "x",None,
 236                  None ,
 237                  List.map
 238                    (fun i ->
 239                       let nargs_kty = nargs it nleft i in
 240                       let ts = iter (fun m acc -> mk_id ("t" ^ (string_of_int m))::acc)
 241                                  (nargs_kty - 1) [] in
 242                      let nones =
 243                        iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
 244                       CicNotationPt.Pattern (kname it i,
 245                                              None,
 246                                              List.combine ts nones),
 247                                 inner i ts)
 248                    (HExtlib.list_seq 0 (List.length cl))) in
 249   let principle = CicNotationPt.Binder (`Lambda, (mk_id "x", Some xyty),
 250                         CicNotationPt.Binder (`Lambda, (mk_id "y", Some xyty), outer))
 251   in
 252   pp (lazy ("discriminator = " ^ (CicNotationPp.pp_term principle)));
 253
 254   status, principle
 255 ;;
 256
 257 let hd_of_term = function
 258   | NCic.Appl (hd::_) -> hd
 259   | t -> t
 260 ;;
 261
 262 let name_of_rel ~context rel =
 263   let s, _ = List.nth context (rel-1) in s
 264 ;;
 265
 266 (* let lookup_in_ctx ~context n =
 267   List.nth context ((List.length context) - n - 1)
 268 ;;*)
 269
 270 let discriminate_tac ~context cur_eq status =
 271   pp (lazy (Printf.sprintf "discriminate: equation %s" (name_of_rel ~context cur_eq)));
 272
 273   let dbranch it ~use_jmeq leftno consno =
 274     let refl_id = mk_id (if use_jmeq then "refl_jmeq" else "refl") in
 275     pp (lazy (Printf.sprintf "dbranch %d %d" leftno consno));
 276     let nlist = HExtlib.list_seq 0 (nargs it leftno consno) in
 277     (* (\forall ...\forall P.\forall DH : ( ... = ... -> P). P) *)
 278     let params = List.map (fun x -> NTactics.intro_tac ("a" ^ string_of_int x)) nlist in
 279         NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern::
 280         params @ [
 281         NTactics.intro_tac "P";
 282         NTactics.intro_tac "DH";
 283         NTactics.apply_tac ("",0,mk_id "DH");
 284         NTactics.apply_tac ("",0,refl_id); (* well, it works even if no goal is selected after applying DH... *)
 285     ] in
 286   let dbranches it ~use_jmeq leftno =
 287     pp (lazy (Printf.sprintf "dbranches %d" leftno));
 288     let _,_,_,cl = it in
 289     let nbranches = List.length cl in
 290     let branches = iter (fun n acc ->
 291       let m = nbranches - n - 1 in
 292       if m = 0 then acc @ (dbranch it ~use_jmeq leftno m)
 293       else acc @ NTactics.shift_tac :: (dbranch it ~use_jmeq
 294       leftno m))
 295       (nbranches-1) [] in
 296     if nbranches > 1 then
 297          NTactics.branch_tac ~force:false:: branches @ [NTactics.merge_tac]
 298     else branches
 299   in
 300
 301   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
 302   let _,ctx' = HExtlib.split_nth cur_eq context in
 303   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
 304   let status, s = term_of_cic_term status s ctx' in
 305   let status, leftno, it, use_jmeq =
 306     let it, t1, t2, use_jmeq = match s with
 307       | NCic.Appl [_;it;t1;t2] -> it,t1,t2,false
 308       | NCic.Appl [_;it;t1;_;t2] -> it,t1,t2,true
 309       | _ -> assert false in
 310     (* XXX: serve? ho già fatto whd *)
 311     let status, it = whd status ctx' (mk_cic_term ctx' it) in
 312     let status, it = term_of_cic_term status it ctx' in
 313     let _uri,indtyno,its = match it with
 314       | NCic.Const (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r)
 315       | NCic.Appl (NCic.Const
 316           (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r)::_) ->
 317         uri, indtyno, NCicEnvironment.get_checked_indtys r
 318       | _ -> pp (lazy ("discriminate: indty ="  ^ NCicPp.ppterm
 319                   ~metasenv:[] ~subst:[] ~context:[] it)) ; assert false in
 320     let _,leftno,its,_,_ = its in
 321     status, leftno, List.nth its indtyno, use_jmeq
 322   in
 323
 324   let itnargs =
 325     let _,_,arity,_ = it in
 326     List.length (arg_list 0 arity) in
 327   let _,itname,_,_ = it in
 328   let params = List.map (fun x -> "a" ^ string_of_int x) (HExtlib.list_seq 1 (itnargs+1)) in
 329   let xyty = mk_appl (List.map mk_id (itname::params)) in
 330   let print_tac s status = pp s ; status in
 331   NTactics.block_tac (
 332     [(fun status ->
 333      let status, discr = mk_discriminator it ~use_jmeq leftno xyty status in
 334      let cut_term = mk_prods params (CicNotationPt.Binder (`Forall, (mk_id "x",
 335                              Some xyty),
 336                          CicNotationPt.Binder (`Forall, (mk_id "y", Some xyty),
 337                           CicNotationPt.Binder (`Forall, (mk_id "e",
 338                            Some (mk_appl [mk_id "eq";CicNotationPt.Implicit `JustOne; mk_id "x"; mk_id "y"])),
 339                            mk_appl [discr; mk_id "x"; mk_id "y"(*;mk_id "e"*)])))) in
 340      let status = print_tac (lazy ("cut_term = "^ CicNotationPp.pp_term cut_term)) status in
 341       NTactics.cut_tac ("",0, cut_term)
 342       status);
 343     NTactics.branch_tac;
 344     print_tac (lazy "ci sono");
 345      NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern]
 346   @ List.map (fun x -> NTactics.intro_tac x) params @
 347     [NTactics.intro_tac "x";
 348      NTactics.intro_tac "y";
 349      NTactics.intro_tac "Deq";
 350     print_tac (lazy "ci sono 2");
 351      NTactics.rewrite_tac ~dir:`RightToLeft ~what:("",0,mk_id "Deq") ~where:default_pattern;
 352      NTactics.cases_tac ~what:("",0,mk_id "x") ~where:default_pattern]
 353   @ dbranches it ~use_jmeq leftno @
 354    [NTactics.shift_tac;
 355     print_tac (lazy "ci sono 3");
 356     NTactics.intro_tac "#discriminate";
 357     NTactics.apply_tac ("",0,mk_appl ([mk_id "#discriminate"]@
 358                                 HExtlib.mk_list (CicNotationPt.Implicit `JustOne) (List.length params + 2) @
 359                                 [mk_id eq_name ]));
 360     NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern;
 361     NTactics.clear_tac ["#discriminate"];
 362     NTactics.merge_tac; print_tac (lazy "the end of discriminate")]
 363   ) status
 364 ;;
 365
 366 let subst_tac ~context ~dir cur_eq =
 367   fun status ->
 368   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
 369   let _,ctx' = HExtlib.split_nth cur_eq context in
 370   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
 371   let status, s = term_of_cic_term status s ctx' in
 372   pp (lazy (Printf.sprintf "subst: equation %s" eq_name));
 373     let l, r = match s with
 374       | NCic.Appl [_;_;t1;t2] | NCic.Appl [_;_;t1;_;t2] -> t1,t2
 375       | _ -> assert false in
 376     let var = match dir with
 377       | `LeftToRight -> l
 378       | `RightToLeft -> r in
 379     (* let var = match var with
 380       | NCic.Rel i -> i
 381       | _ -> assert false in *)
 382     let names_to_gen, _ =
 383       match var with
 384       | NCic.Rel var ->
 385         cascade_select_in_ctx ~subst:(get_subst status) context (var+cur_eq)
 386       | _ -> cascade_select_in_ctx ~subst:(get_subst status) context cur_eq in
 387     let names_to_gen = List.filter (fun n -> n <> eq_name) names_to_gen in
 388     let gen_tac x =
 389       NTactics.generalize_tac
 390       ~where:("",0,(Some (mk_id x),[], Some CicNotationPt.UserInput)) in
 391     NTactics.block_tac ((List.map gen_tac names_to_gen)@
 392                 [NTactics.clear_tac names_to_gen;
 393                  NTactics.rewrite_tac ~dir
 394                    ~what:("",0,mk_id eq_name) ~where:default_pattern;
 395                  NTactics.reduce_tac ~reduction:(`Normalize true)
 396                    ~where:default_pattern;
 397                  NTactics.clear_tac [eq_name]]@
 398                  (List.map NTactics.intro_tac (List.rev names_to_gen))) status
 399 ;;
 400
 401 let clearid_tac ~context cur_eq =
 402   fun status ->
 403   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
 404   let _,ctx' = HExtlib.split_nth cur_eq context in
 405   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
 406   let status, s = term_of_cic_term status s ctx' in
 407   let streicher_id =
 408     match s with
 409     | NCic.Appl [_;_;_;_] -> mk_id "streicherK"
 410     | NCic.Appl [_;_;_;_;_] -> mk_id "streicherKjmeq"
 411     | _ -> assert false
 412   in
 413   pp (lazy (Printf.sprintf "clearid: equation %s" eq_name));
 414     let names_to_gen, _ =
 415       cascade_select_in_ctx ~subst:(get_subst status) context cur_eq in
 416     let names_to_gen = names_to_gen @ [eq_name] in
 417     let gen_tac x =
 418       NTactics.generalize_tac
 419       ~where:("",0,(Some (mk_id x),[], Some CicNotationPt.UserInput)) in
 420     NTactics.block_tac ((List.map gen_tac names_to_gen)@
 421                 [NTactics.clear_tac names_to_gen;
 422                  NTactics.apply_tac ("",0, mk_appl [streicher_id;
 423                                                     CicNotationPt.Implicit `JustOne;
 424                                                     CicNotationPt.Implicit `JustOne;
 425                                                     CicNotationPt.Implicit `JustOne;
 426                                                     CicNotationPt.Implicit `JustOne]);
 427                  NTactics.reduce_tac ~reduction:(`Normalize true)
 428                    ~where:default_pattern] @
 429                  (let names_to_intro =
 430                     match List.rev names_to_gen with
 431                     | [] -> []
 432                     | _::tl -> tl in
 433                   List.map NTactics.intro_tac names_to_intro)) status
 434 ;;
 435
 436 let get_ctx st goal =
 437     ctx_of (get_goalty st goal)
 438 ;;
 439
 440 (* = select + classify *)
 441 let select_eq ctx acc status goal =
 442   let classify ~subst ctx' l r =
 443     (* FIXME: metasenv *)
 444     if NCicReduction.are_convertible ~metasenv:[] ~subst ctx' l r
 445       then status, `Identity
 446       else status, (match hd_of_term l, hd_of_term r with
 447         | NCic.Const (NReference.Ref (_,NReference.Con (_,ki,nleft)) as kref),
 448           NCic.Const (NReference.Ref (_,NReference.Con (_,kj,_))) ->
 449             if ki != kj then `Discriminate (0,true)
 450             else
 451               let rit = NReference.mk_indty true kref in
 452               let _,_,its,_,itno = NCicEnvironment.get_checked_indtys rit in
 453               let it = List.nth its itno in
 454               let newprods = nargs it nleft (ki-1) in
 455               `Discriminate (newprods, false)
 456         | NCic.Rel j, _
 457             when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j r
 458               && l = NCic.Rel j -> `Subst `LeftToRight
 459         | _, NCic.Rel j
 460             when NCicTypeChecker.does_not_occur ~subst ctx' (j-1) j l
 461               && r = NCic.Rel j -> `Subst `RightToLeft
 462         | (NCic.Rel _, _ | _, NCic.Rel _ ) -> `Cycle (* could be a blob too... *)
 463         | _ -> `Blob) in
 464   let rec aux i =
 465     try
 466       let index = List.length ctx - i in
 467       pp (lazy ("provo classify di index = " ^string_of_int index));
 468       match (List.nth ctx (index - 1)) with
 469       | n, (NCic.Decl ty | NCic.Def (ty,_)) ->
 470           (let _,ctx_ty = HExtlib.split_nth index ctx in
 471            let status, ty = NTacStatus.whd status ctx_ty (mk_cic_term ctx_ty ty) in
 472            let status, ty = term_of_cic_term status ty ctx_ty in
 473            pp (lazy (Printf.sprintf "select_eq tries %s" (NCicPp.ppterm ~context:ctx_ty ~subst:[] ~metasenv:[] ty)));
 474            let status, kind = match ty with
 475            | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;_;l;r]
 476                when NUri.name_of_uri u = "eq" ->
 477                classify ~subst:(get_subst status) ctx_ty l r
 478            | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;lty;l;rty;r]
 479                when NUri.name_of_uri u = "jmeq" &&
 480                  NCicReduction.are_convertible ~metasenv:[]
 481                    ~subst:(get_subst status) ctx_ty lty rty
 482                -> classify ~subst:(get_subst status) ctx_ty l r
 483            | _ -> status, `NonEq
 484            in match kind with
 485               | `Identity ->
 486                   let status, goalty = term_of_cic_term status (get_goalty status goal) ctx in
 487                      status, Some (List.length ctx - i), kind
 488               | `Cycle | `Blob | `NonEq -> aux (i+1) (* XXX: skip cyclic/blob equations for now *)
 489               | _ ->
 490                  if (List.for_all (fun x -> x <> n) acc) then
 491                    status, Some (List.length ctx - i), kind
 492                  else aux (i+1))
 493     with Failure _ | Invalid_argument _ -> status, None, `Blob
 494   in aux 0
 495 ;;
 496
 497 let rec destruct_tac0 nprods acc status goal =
 498   let ctx = get_ctx status goal in
 499   let subst = get_subst status in
 500   let get_newgoal os ns ogoal =
 501     let go, gc = NTactics.compare_statuses ~past:os ~present:ns in
 502     let go' = ([ogoal] @- gc) @+ go in
 503       match go' with [] -> assert false | g::_ -> g
 504   in
 505   let status, selection, kind  = select_eq ctx acc status goal in
 506   pp (lazy ("destruct: acc is " ^ String.concat "," acc ));
 507   match selection, kind with
 508   | None, _ ->
 509     pp (lazy (Printf.sprintf "destruct: nprods is %d, no selection, context is %s" nprods (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
 510       if nprods > 0  then
 511         let status' = NTactics.exec (NTactics.intro_tac (mk_fresh_name ctx 'e' 0)) status goal in
 512         destruct_tac0 (nprods-1) acc status' (get_newgoal status status' goal)
 513       else
 514         status
 515   | Some cur_eq, `Discriminate (newprods,conflict) ->
 516     pp (lazy (Printf.sprintf "destruct: discriminate - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
 517       let status' = NTactics.exec (discriminate_tac ~context:ctx cur_eq) status goal in
 518       if conflict then status'
 519       else destruct_tac0 (nprods+newprods)
 520              (name_of_rel ~context:ctx cur_eq::acc) status' (get_newgoal status status' goal)
 521   | Some cur_eq, `Subst dir ->
 522     pp (lazy (Printf.sprintf "destruct: subst - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
 523     let status' = NTactics.exec (subst_tac ~context:ctx ~dir cur_eq) status goal in
 524       pp (lazy (Printf.sprintf " ctx after subst = %s" (NCicPp.ppcontext ~metasenv:[] ~subst (get_ctx status' (get_newgoal status status' goal)))));
 525     let eq_name,_ = List.nth ctx (cur_eq-1) in
 526       destruct_tac0 nprods (List.filter (fun x -> x <> eq_name) acc) status' (get_newgoal status status' goal)
 527   | Some cur_eq, `Identity ->
 528     pp (lazy (Printf.sprintf "destruct: identity - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
 529       let eq_name,_ = List.nth ctx (cur_eq-1) in
 530       let status' = NTactics.exec (clearid_tac ~context:ctx cur_eq) status goal in
 531         destruct_tac0 nprods (List.filter (fun x -> x <> eq_name) acc) status' (get_newgoal status status' goal)
 532   | Some cur_eq, `Cycle -> (* TODO, should never happen *)
 533     pp (lazy (Printf.sprintf "destruct: cycle - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
 534       assert false
 535   | Some cur_eq, `Blob ->
 536     pp (lazy (Printf.sprintf "destruct: blob - nprods is %d, selection is %d, context is %s" nprods cur_eq (NCicPp.ppcontext ~metasenv:[] ~subst ctx)));
 537       assert false
 538   | _ -> assert false
 539 ;;
 540
 541 let destruct_tac s = NTactics.distribute_tac (destruct_tac0 0 []) s;;