]> matita.cs.unibo.it Git - helm.git/blob - matita/components/ng_tactics/nDestructTac.ml
Remove the daemon :-)
[helm.git] / 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 = false
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 rec mk_prods l t =
48   match l with
49     [] -> t
50   | hd::tl -> NotationPt.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 -> NotationPt.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 status subst []) o
70   in
71    status#set_obj(u,h,NCicUntrusted.apply_subst_metasenv status 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 status ~subst ctx skip 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 status ~subst context (x-1) x s) acc)
89                    && not (List.mem n skip)) ->
90                 List.iter (fun m -> pp (lazy ("acc has " ^ (string_of_int m)))) acc;
91                 pp (lazy ("acc occurs in the type of " ^ n));
92                 (1::List.map ((+) 1) acc, item::context)
93             | _ -> (List.map ((+) 1) acc, item::context))
94        ([1], rctx) lctx in
95     let indices = rm_last indices in
96     let res = List.map (fun n -> let s,_ = List.nth ctx (n-1) in s) indices in
97     List.iter (fun n -> pp (lazy n)) res;
98     pp (lazy (status#ppcontext ~metasenv:[] ~subst ctx));
99     res, indices
100 ;;
101
102 let rec mk_fresh_name ctx firstch n =
103   let candidate = (String.make 1 firstch) ^ (string_of_int n) in
104   if (List.for_all (fun (s,_) -> s <> candidate) ctx) then candidate
105   else mk_fresh_name ctx firstch (n+1)
106 ;;
107
108 let arg_list nleft t =
109   let rec drop_prods n t =
110     if n <= 0 then t
111     else match t with
112       | NCic.Prod (_,_,ta) -> drop_prods (n-1) ta
113       | _ -> raise (Failure "drop_prods")
114   in
115   let rec aux = function
116     | NCic.Prod (_,so,ta) -> so::aux ta
117     | _ -> []
118   in aux (drop_prods nleft t)
119 ;;
120
121 let nargs it nleft consno =
122   pp (lazy (Printf.sprintf "nargs %d %d" nleft consno));
123   let _,indname,_,cl = it in
124   let _,_,t_k = List.nth cl consno in
125   List.length (arg_list nleft t_k) ;;
126
127 let default_pattern = "",0,(None,[],Some NotationPt.UserInput);;
128
129 (* returns the discrimination = injection+contradiction principle *)
130
131 let mk_discriminator it ~use_jmeq nleft xyty status =
132   let _,indname,_,cl = it in
133
134
135   let mk_eq tys ts us es n =
136     if use_jmeq then
137       mk_appl [mk_id "jmeq";
138                NotationPt.Implicit `JustOne; List.nth ts n;
139                NotationPt.Implicit `JustOne; List.nth us n] 
140     else
141     (* eqty = Tn u0 e0...un-1 en-1 *)
142     let eqty = mk_appl 
143                  (List.nth tys n :: iter (fun i acc -> 
144                                            List.nth us i::
145                                            List.nth es i:: acc) 
146                                      (n-1) []) in
147
148     (* params = [T0;t0;...;Tn;tn;u0;e0;un-1;en-1] *)
149     let params = iter (fun i acc -> 
150                          List.nth tys i ::
151                          List.nth ts i :: acc) n
152                      (iter (fun i acc ->
153                             List.nth us i::
154                             List.nth es i:: acc) (n-1) []) in
155     mk_appl [mk_id "eq"; eqty;
156                         mk_appl (mk_id ("R" ^ string_of_int n) :: params);
157                         List.nth us n]
158
159   in
160
161   let kname it j =
162     let _,_,_,cl = it in
163     let _,name,_ = List.nth cl j in
164     name
165   in
166
167   let branch i j ts us = 
168     let nargs = nargs it nleft i in
169     let es = List.map (fun x -> mk_id ("e" ^ string_of_int x)) (HExtlib.list_seq 0 nargs) in
170     let tys = List.map 
171                 (fun x -> iter 
172                   (fun i acc -> 
173                     NotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None),
174                     NotationPt.Binder (`Lambda, (mk_id ("p" ^ string_of_int i), None),
175                     acc))) (x-1) 
176                  (NotationPt.Implicit (`Tagged ("T" ^ (string_of_int x)))))
177                (HExtlib.list_seq 0 nargs) in
178     let tys = tys @ 
179       [iter (fun i acc -> 
180         NotationPt.Binder (`Lambda, (mk_id ("x" ^ string_of_int i), None),
181         NotationPt.Binder (`Lambda, (mk_id ("p" ^ string_of_int i), None),
182         acc))) (nargs-1)
183         (mk_appl [mk_id "eq"; NotationPt.Implicit `JustOne;
184           mk_appl (mk_id (kname it i)::
185            List.map (fun x -> mk_id ("x" ^string_of_int x))
186               (HExtlib.list_seq 0 (List.length ts)));
187               mk_appl (mk_id (kname it j)::us)])]
188     in
189     (** NotationPt.Binder (`Lambda, (mk_id "e", 
190       Some (mk_appl 
191         [mk_id "eq";
192          NotationPt.Implicit `JustOne;
193          mk_appl (mk_id (kname it i)::ts);
194          mk_appl (mk_id (kname it j)::us)])),
195     let ts = ts @ [mk_id "e"] in 
196     let refl2 = mk_appl
197                   [mk_id "refl";
198                    NotationPt.Implicit `JustOne;
199                    mk_appl (mk_id (kname it j)::us)] in
200     let us = us @ [refl2] in *)
201     NotationPt.Binder (`Forall, (mk_id "P", Some (NotationPt.Sort (`NType "1") )),
202       if i = j then 
203        NotationPt.Binder (`Forall, (mk_id "_",
204         Some (iter (fun i acc -> 
205               NotationPt.Binder (`Forall, (List.nth es i, Some (mk_eq tys ts us es i)), acc))
206               (nargs-1) 
207               (** (NotationPt.Binder (`Forall, (mk_id "_", 
208                 Some (mk_eq tys ts us es nargs)),*)
209                 (mk_id "P"))), mk_id "P")
210       else mk_id "P")
211   in
212
213   let inner i ts = NotationPt.Case 
214               (mk_id "y",None,
215                (*Some (NotationPt.Binder (`Lambda, (mk_id "y",None), 
216                  NotationPt.Binder (`Forall, (mk_id "_", Some
217                  (mk_appl [mk_id "eq";NotationPt.Implicit
218                  `JustOne;(*NotationPt.Implicit `JustOne*)
219                   mk_appl (mk_id (kname it i)::ts);mk_id "y"])),
220                  NotationPt.Implicit `JustOne )))*)
221                   None,
222                   List.map
223                   (fun j -> 
224                      let nargs_kty = nargs it nleft j in
225                      let us = iter (fun m acc -> mk_id ("u" ^ (string_of_int m))::acc) 
226                                 (nargs_kty - 1) [] in
227                      let nones = 
228                        iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
229                      NotationPt.Pattern (kname it j,
230                                             None,
231                                             List.combine us nones), 
232                                 branch i j ts us)
233                   (HExtlib.list_seq 0 (List.length cl)))
234   in
235   let outer = NotationPt.Case
236                 (mk_id "x",None,
237                  None ,
238                  List.map
239                    (fun i -> 
240                       let nargs_kty = nargs it nleft i in
241                       let ts = iter (fun m acc -> mk_id ("t" ^ (string_of_int m))::acc)
242                                  (nargs_kty - 1) [] in
243                      let nones = 
244                        iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
245                       NotationPt.Pattern (kname it i,
246                                              None,
247                                              List.combine ts nones),
248                                 inner i ts)
249                    (HExtlib.list_seq 0 (List.length cl))) in
250   let principle = NotationPt.Binder (`Lambda, (mk_id "x", Some xyty),
251                         NotationPt.Binder (`Lambda, (mk_id "y", Some xyty), outer))
252   in
253   pp (lazy ("discriminator = " ^ (NotationPp.pp_term status principle)));
254   
255   status, principle 
256 ;;
257
258 let hd_of_term = function
259   | NCic.Appl (hd::_) -> hd
260   | t -> t
261 ;;
262
263 let name_of_rel ~context rel =
264   let s, _ = List.nth context (rel-1) in s
265 ;;
266
267 (* let lookup_in_ctx ~context n =
268   List.nth context ((List.length context) - n - 1)
269 ;;*)
270
271 let discriminate_tac ~context cur_eq status =
272   pp (lazy (Printf.sprintf "discriminate: equation %s" (name_of_rel ~context cur_eq)));
273
274   let dbranch it ~use_jmeq leftno consno =
275     let refl_id = mk_id (if use_jmeq then "refl_jmeq" else "refl") in
276     pp (lazy (Printf.sprintf "dbranch %d %d" leftno consno));
277     let nlist = HExtlib.list_seq 0 (nargs it leftno consno) in
278     (* (\forall ...\forall P.\forall DH : ( ... = ... -> P). P) *)
279     let params = List.map (fun x -> NTactics.intro_tac ("a" ^ string_of_int x)) nlist in
280         NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern::
281         params @ [
282         NTactics.intro_tac "P";
283         NTactics.intro_tac "DH";
284         NTactics.apply_tac ("",0,mk_id "DH");
285         NTactics.apply_tac ("",0,refl_id); (* well, it works even if no goal is selected after applying DH... *)
286     ] in
287   let dbranches it ~use_jmeq leftno =
288     pp (lazy (Printf.sprintf "dbranches %d" leftno));
289     let _,_,_,cl = it in
290     let nbranches = List.length cl in 
291     let branches = iter (fun n acc -> 
292       let m = nbranches - n - 1 in
293       if m = 0 then acc @ (dbranch it ~use_jmeq leftno m)
294       else acc @ NTactics.shift_tac :: (dbranch it ~use_jmeq
295       leftno m))
296       (nbranches-1) [] in
297     if nbranches > 1 then
298          NTactics.branch_tac ~force:false:: branches @ [NTactics.merge_tac]
299     else branches
300   in
301   
302   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
303   let _,ctx' = HExtlib.split_nth cur_eq context in
304   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
305   let status, s = term_of_cic_term status s ctx' in
306   let status, leftno, it, use_jmeq =
307     let it, t1, t2, use_jmeq = match s with
308       | NCic.Appl [_;it;t1;t2] -> it,t1,t2,false
309       | NCic.Appl [_;it;t1;_;t2] -> it,t1,t2,true
310       | _ -> assert false in
311     (* XXX: serve? ho già fatto whd *)
312     let status, it = whd status ctx' (mk_cic_term ctx' it) in
313     let status, it = term_of_cic_term status it ctx' in
314     let _uri,indtyno,its = match it with
315       | NCic.Const (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r) 
316       | NCic.Appl (NCic.Const 
317           (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r)::_) -> 
318         uri, indtyno, NCicEnvironment.get_checked_indtys status r
319       | _ -> pp (lazy ("discriminate: indty ="  ^ status#ppterm
320                   ~metasenv:[] ~subst:[] ~context:[] it)) ; assert false in
321     let _,leftno,its,_,_ = its in
322     status, leftno, List.nth its indtyno, use_jmeq
323   in
324   
325   let itnargs = 
326     let _,_,arity,_ = it in 
327     List.length (arg_list 0 arity) in
328   let _,itname,_,_ = it in
329   let params = List.map (fun x -> "a" ^ string_of_int x) (HExtlib.list_seq 1 (itnargs+1)) in
330   let xyty = mk_appl (List.map mk_id (itname::params)) in
331   let print_tac s status = pp s ; status in 
332   NTactics.block_tac (
333     [(fun status ->
334      let status, discr = mk_discriminator it ~use_jmeq leftno xyty status in
335      let cut_term = mk_prods params (NotationPt.Binder (`Forall, (mk_id "x",
336                              Some xyty),
337                          NotationPt.Binder (`Forall, (mk_id "y", Some xyty),
338                           NotationPt.Binder (`Forall, (mk_id "e",
339                            Some (mk_appl [mk_id "eq";NotationPt.Implicit `JustOne; mk_id "x"; mk_id "y"])),
340                            mk_appl [discr; mk_id "x"; mk_id "y"(*;mk_id "e"*)])))) in
341      let status = print_tac (lazy ("cut_term = "^ NotationPp.pp_term status cut_term)) status in
342       NTactics.cut_tac ("",0, cut_term)
343       status);
344     NTactics.branch_tac;
345     print_tac (lazy "ci sono");
346      NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern]
347   @ List.map (fun x -> NTactics.intro_tac x) params @
348     [NTactics.intro_tac "x";
349      NTactics.intro_tac "y";
350      NTactics.intro_tac "Deq";
351     print_tac (lazy "ci sono 2");
352      NTactics.rewrite_tac ~dir:`RightToLeft ~what:("",0,mk_id "Deq") ~where:default_pattern;
353      NTactics.cases_tac ~what:("",0,mk_id "x") ~where:default_pattern]
354   @ dbranches it ~use_jmeq leftno @ 
355    [NTactics.shift_tac;
356     print_tac (lazy "ci sono 3");
357     NTactics.intro_tac "#discriminate";
358     NTactics.apply_tac ("",0,mk_appl ([mk_id "#discriminate"]@
359                                 HExtlib.mk_list (NotationPt.Implicit `JustOne) (List.length params + 2) @
360                                 [mk_id eq_name ]));
361     NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern;
362     NTactics.clear_tac ["#discriminate"];
363     NTactics.merge_tac; print_tac (lazy "the end of discriminate")] 
364   ) status
365 ;;
366
367 let saturate_skip status context skip =
368   HExtlib.list_uniq
369     (List.fold_left
370       (fun acc x -> 
371          let ix = HExtlib.list_index ((=) x) (List.map fst context)
372          in match ix with
373          | None -> acc
374          | Some (i,_) -> 
375             fst (cascade_select_in_ctx status ~subst:(get_subst status) context [] (i+1)) @ acc) skip skip)
376 ;;
377       
378 let subst_tac ~context ~dir skip cur_eq =
379   fun status as oldstatus ->
380   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
381   let _,ctx' = HExtlib.split_nth cur_eq context in
382   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
383   let status, s = term_of_cic_term status s ctx' in
384   let skip = saturate_skip status context skip in
385   pp (lazy (Printf.sprintf "subst: equation %s" eq_name));
386     let l, r = match s with
387       | NCic.Appl [_;_;t1;t2] | NCic.Appl [_;_;t1;_;t2] -> t1,t2
388       | _ -> assert false in
389     let var = match dir with
390       | `LeftToRight -> l
391       | `RightToLeft -> r in
392     (* let var = match var with
393       | NCic.Rel i -> i
394       | _ -> assert false in *)
395     let names_to_gen, _ = 
396       match var with 
397       | NCic.Rel var ->
398         cascade_select_in_ctx status ~subst:(get_subst status) context skip (var+cur_eq)
399       | _ -> cascade_select_in_ctx status ~subst:(get_subst status) context skip cur_eq in
400     let names_to_gen = List.filter (fun n -> n <> eq_name) names_to_gen in
401     if (List.exists (fun x -> List.mem x skip) names_to_gen)
402       then oldstatus
403     else 
404     let gen_tac x = 
405       NTactics.generalize_tac 
406       ~where:("",0,(Some (mk_id x),[], Some NotationPt.UserInput)) in
407     NTactics.block_tac ((List.map gen_tac names_to_gen)@
408                 [NTactics.clear_tac names_to_gen;
409                  NTactics.rewrite_tac ~dir 
410                    ~what:("",0,mk_id eq_name) ~where:default_pattern;
411                  NTactics.reduce_tac ~reduction:(`Normalize true)
412                    ~where:default_pattern;
413                  NTactics.try_tac (NTactics.clear_tac [eq_name])]@
414                  (List.map NTactics.intro_tac (List.rev names_to_gen))) status
415 ;;
416
417 let clearid_tac ~context skip cur_eq =
418   fun status ->
419   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
420   let _,ctx' = HExtlib.split_nth cur_eq context in
421   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
422   let status, s = term_of_cic_term status s ctx' in
423   let skip = saturate_skip status context skip in
424   (* 
425   let streicher_id = 
426     match s with
427     | NCic.Appl [_;_;_;_] -> mk_id "streicherK"
428     | NCic.Appl [_;_;_;_;_] -> mk_id "streicherKjmeq"
429     | _ -> assert false
430   in
431   pp (lazy (Printf.sprintf "clearid: equation %s" eq_name));
432     let names_to_gen, _ = 
433       cascade_select_in_ctx ~subst:(get_subst status) context cur_eq in
434     let names_to_gen = names_to_gen @ [eq_name] in
435     let gen_tac x = 
436       NTactics.generalize_tac 
437       ~where:("",0,(Some (mk_id x),[], Some NotationPt.UserInput)) in
438     NTactics.block_tac ((List.map gen_tac names_to_gen)@
439                 [NTactics.clear_tac names_to_gen;
440                  NTactics.apply_tac ("",0, mk_appl [streicher_id;
441                                                     NotationPt.Implicit `JustOne;
442                                                     NotationPt.Implicit `JustOne;
443                                                     NotationPt.Implicit `JustOne;
444                                                     NotationPt.Implicit `JustOne]);
445                  NTactics.reduce_tac ~reduction:(`Normalize true)
446                    ~where:default_pattern] @
447                  (let names_to_intro = 
448                     match List.rev names_to_gen with
449                     | [] -> []
450                     | _::tl -> tl in
451                   List.map NTactics.intro_tac names_to_intro)) status
452 *)
453
454   pp (lazy (Printf.sprintf "clearid: equation %s" eq_name));
455     match s with
456     | NCic.Appl [_;_;_;_] -> 
457       (* leibniz *)
458   let streicher_id = mk_id "streicherK"
459   in
460     let names_to_gen, _ = 
461       cascade_select_in_ctx status ~subst:(get_subst status) context skip cur_eq in
462     let names_to_gen = names_to_gen @ [eq_name] in
463     let gen_tac x = 
464       NTactics.generalize_tac 
465       ~where:("",0,(Some (mk_id x),[], Some NotationPt.UserInput)) in
466     NTactics.block_tac ((List.map gen_tac names_to_gen)@
467                 [NTactics.clear_tac names_to_gen;
468                  NTactics.apply_tac ("",0, mk_appl [streicher_id;
469                                                     NotationPt.Implicit `JustOne;
470                                                     NotationPt.Implicit `JustOne;
471                                                     NotationPt.Implicit `JustOne;
472                                                     NotationPt.Implicit `JustOne]);
473                  NTactics.reduce_tac ~reduction:(`Normalize true)
474                    ~where:default_pattern] @
475                  (let names_to_intro = 
476                     match List.rev names_to_gen with
477                     | [] -> []
478                     | _::tl -> tl in
479                   List.map NTactics.intro_tac names_to_intro)) status
480     | NCic.Appl [_;_;_;_;_] -> 
481       (* JMeq *) 
482   let streicher_id = mk_id "streicherK"
483   in
484     let names_to_gen, _ = 
485       cascade_select_in_ctx status ~subst:(get_subst status) context skip cur_eq in
486     let names_to_gen = names_to_gen (* @ [eq_name]*) in
487     let gen_tac x = 
488       NTactics.generalize_tac 
489       ~where:("",0,(Some (mk_id x),[], Some NotationPt.UserInput)) in
490     let gen_eq = NTactics.generalize_tac
491      ~where:("",0,(Some (mk_appl [mk_id "jmeq_to_eq";
492                                   NotationPt.Implicit `JustOne; 
493                                   NotationPt.Implicit `JustOne; 
494                                   NotationPt.Implicit `JustOne; 
495                                   mk_id eq_name]),[], Some NotationPt.UserInput)) in
496     NTactics.block_tac ((List.map gen_tac names_to_gen)@gen_eq::
497                 [NTactics.clear_tac names_to_gen;
498                  NTactics.try_tac (NTactics.clear_tac [eq_name]);
499                  NTactics.apply_tac ("",0, mk_appl [streicher_id;
500                                                     NotationPt.Implicit `JustOne;
501                                                     NotationPt.Implicit `JustOne;
502                                                     NotationPt.Implicit `JustOne;
503                                                     NotationPt.Implicit `JustOne]);
504                  NTactics.reduce_tac ~reduction:(`Normalize true)
505                    ~where:default_pattern] @
506                  (let names_to_intro = List.rev names_to_gen in
507                   List.map NTactics.intro_tac names_to_intro)) status
508     | _ -> assert false
509 ;;
510
511 let get_ctx st goal =
512     ctx_of (get_goalty st goal)
513 ;;
514
515 (* = select + classify *)
516 let select_eq ctx acc domain status goal =
517   let classify ~subst ctx' l r =
518     (* FIXME: metasenv *)
519     if NCicReduction.are_convertible status ~metasenv:[] ~subst ctx' l r 
520       then status, `Identity
521       else status, (match hd_of_term l, hd_of_term r with
522         | NCic.Const (NReference.Ref (_,NReference.Con (_,ki,nleft)) as kref),
523           NCic.Const (NReference.Ref (_,NReference.Con (_,kj,_))) -> 
524             if ki != kj then `Discriminate (0,true)
525             else
526               let rit = NReference.mk_indty true kref in
527               let _,_,its,_,itno = NCicEnvironment.get_checked_indtys status rit in 
528               let it = List.nth its itno in
529               let newprods = nargs it nleft (ki-1) in
530               `Discriminate (newprods, false) 
531         | NCic.Rel j, _  
532             when NCicTypeChecker.does_not_occur status ~subst ctx' (j-1) j r
533               && l = NCic.Rel j -> `Subst `LeftToRight
534         | _, NCic.Rel j 
535             when NCicTypeChecker.does_not_occur status ~subst ctx' (j-1) j l 
536               && r = NCic.Rel j -> `Subst `RightToLeft
537         | (NCic.Rel _, _ | _, NCic.Rel _ ) -> `Cycle (* could be a blob too... *)
538         | _ -> `Blob) in
539   let rec aux i =
540     try
541       let index = List.length ctx - i in
542       pp (lazy ("provo classify di index = " ^string_of_int index));
543       match (List.nth ctx (index - 1)) with
544       | n, (NCic.Decl ty | NCic.Def (ty,_)) ->
545           (let _,ctx_ty = HExtlib.split_nth index ctx in 
546            let status, ty = NTacStatus.whd status ctx_ty (mk_cic_term ctx_ty ty) in
547            let status, ty = term_of_cic_term status ty ctx_ty in
548            pp (lazy (Printf.sprintf "select_eq tries %s" (status#ppterm ~context:ctx_ty ~subst:[] ~metasenv:[] ty)));
549            let status, kind = match ty with
550            | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;_;l;r] 
551                when NUri.name_of_uri u = "eq" ->
552                classify ~subst:(get_subst status) ctx_ty l r
553            | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;lty;l;rty;r]
554                when NUri.name_of_uri u = "jmeq" && 
555                  NCicReduction.are_convertible status ~metasenv:[] 
556                    ~subst:(get_subst status) ctx_ty lty rty
557                -> classify ~subst:(get_subst status) ctx_ty l r
558            | _ -> status, `NonEq 
559            in match kind with
560               | `Identity ->
561                   let status, goalty = term_of_cic_term status (get_goalty status goal) ctx in
562                      status, Some (List.length ctx - i), kind
563               | `Cycle | `Blob | `NonEq -> aux (i+1) (* XXX: skip cyclic/blob equations for now *)
564               | _ -> 
565                  if (List.for_all (fun x -> x <> n) acc) && 
566                     (List.exists (fun x -> x = n) domain) 
567                  then status, Some (List.length ctx - i), kind
568                  else aux (i+1))
569     with Failure _ | Invalid_argument _ -> status, None, `Blob
570   in aux 0
571 ;;
572
573 let rec destruct_tac0 nprods acc domain skip status goal =
574   let ctx = get_ctx status goal in
575   let subst = get_subst status in
576   let get_newgoal os ns ogoal =
577     let go, gc = NTactics.compare_statuses ~past:os ~present:ns in
578     let go' = ([ogoal] @- gc) @+ go in
579       match go' with [] -> assert false | g::_ -> g
580   in
581   let status, selection, kind  = select_eq ctx acc domain status goal in
582   pp (lazy ("destruct: acc is " ^ String.concat "," acc ));
583   match selection, kind with
584   | None, _ -> 
585     pp (lazy (Printf.sprintf "destruct: nprods is %d, no selection, context is %s" nprods (status#ppcontext ~metasenv:[] ~subst ctx)));
586       if nprods > 0  then
587         let fresh = mk_fresh_name ctx 'e' 0 in 
588         let status' = NTactics.exec (NTactics.intro_tac fresh) status goal in
589         destruct_tac0 (nprods-1) acc (fresh::domain) skip status' (get_newgoal status status' goal)
590       else
591         status
592   | Some cur_eq, `Discriminate (newprods,conflict) -> 
593     pp (lazy (Printf.sprintf "destruct: discriminate - nprods is %d, selection is %d, context is %s" nprods cur_eq (status#ppcontext ~metasenv:[] ~subst ctx)));
594       let status' = NTactics.exec (discriminate_tac ~context:ctx cur_eq) status goal in
595       if conflict then status'
596       else 
597         destruct_tac0 (nprods+newprods) 
598              (name_of_rel ~context:ctx cur_eq::acc) 
599              (List.filter (fun x -> x <> name_of_rel ~context:ctx cur_eq) domain)
600              skip 
601              status' (get_newgoal status status' goal)
602   | Some cur_eq, `Subst dir ->
603     pp (lazy (Printf.sprintf "destruct: subst - nprods is %d, selection is %d, context is %s" nprods cur_eq (status#ppcontext ~metasenv:[] ~subst ctx)));
604     let status' = NTactics.exec (subst_tac ~context:ctx ~dir skip cur_eq) status goal in
605       pp (lazy (Printf.sprintf " ctx after subst = %s" (status#ppcontext ~metasenv:[] ~subst (get_ctx status' (get_newgoal status status' goal)))));
606     let eq_name,_ = List.nth ctx (cur_eq-1) in
607     let newgoal = get_newgoal status status' goal in
608     let has_cleared = 
609      try 
610        let _ = NTactics.find_in_context eq_name (get_ctx status' newgoal) in false
611      with _ -> true in
612     let rm_eq b l = if b then List.filter (fun x -> x <> eq_name) l else l in
613     let acc = rm_eq has_cleared acc in
614     let skip = rm_eq has_cleared skip in
615     let domain = rm_eq has_cleared domain in
616       destruct_tac0 nprods acc domain skip status' newgoal
617  | Some cur_eq, `Identity ->
618     pp (lazy (Printf.sprintf "destruct: identity - nprods is %d, selection is %d, context is %s" nprods cur_eq (status#ppcontext ~metasenv:[] ~subst ctx)));
619       let eq_name,_ = List.nth ctx (cur_eq-1) in
620       let status' = NTactics.exec (clearid_tac ~context:ctx skip cur_eq) status goal in
621       let newgoal = get_newgoal status status' goal in
622       let has_cleared = 
623        try 
624          let _ = NTactics.find_in_context eq_name (get_ctx status' newgoal) in false
625        with _ -> true in
626       let rm_eq b l = if b then List.filter (fun x -> x <> eq_name) l else l in
627       let acc = rm_eq has_cleared acc in
628       let skip = rm_eq has_cleared skip in
629       let domain = rm_eq has_cleared domain in
630         destruct_tac0 nprods acc domain skip status' newgoal
631   | Some cur_eq, `Cycle -> (* TODO, should never happen *)
632     pp (lazy (Printf.sprintf "destruct: cycle - nprods is %d, selection is %d, context is %s" nprods cur_eq (status#ppcontext ~metasenv:[] ~subst ctx)));
633       assert false
634   | Some cur_eq, `Blob ->
635     pp (lazy (Printf.sprintf "destruct: blob - nprods is %d, selection is %d, context is %s" nprods cur_eq (status#ppcontext ~metasenv:[] ~subst ctx)));
636       assert false
637   | _ -> assert false
638 ;;
639
640 let destruct_tac dom skip s = 
641   NTactics.distribute_tac 
642     (fun s' g -> 
643      let ctx = get_ctx s' g in
644      let domain = match dom with
645        | None -> List.map (fun (n,_) -> n) ctx
646        | Some l -> l 
647      in
648      destruct_tac0 0 [] domain skip s' g) s;;