]> matita.cs.unibo.it Git - helm.git/blob - matita/components/ng_tactics/nDestructTac.ml
Removes debug prints that were left from last commit.
[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 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                       let deps = List.map (fun (x,xs) -> mk_id x, (List.map mk_id) xs) deps in
330                       let max_dep = List.fold_left max 0 (List.map (fun (_,xs) -> List.length xs) deps) in
331                       if (max_dep > 4 && not use_jmeq && not force) then raise (ConstructorTooBig (kname i)); 
332                       
333                      let nones =
334                        iter (fun _ acc -> None::acc) (nargs_kty - 1) [] in
335                       NotationPt.Pattern (kname i,
336                                              None,
337                                              List.combine ts nones),
338                                 inner i ts deps)
339                    (HExtlib.list_seq 0 (List.length cl))) in
340   let principle = 
341     mk_prods params (NotationPt.Binder (`Forall, (mk_id "x",
342                                Some xyty),
343                            NotationPt.Binder (`Forall, (mk_id "y", Some xyty),
344                             (if use_jmeq then
345                              NotationPt.Binder (`Forall, (mk_id "e",
346                               Some (mk_appl
347                                [mk_sym "jmsimeq"; NotationPt.Implicit `JustOne; mk_id "x";
348                                                   NotationPt.Implicit `JustOne; mk_id "y"])),
349                                                   outer)
350                             else 
351                               NotationPt.Binder (`Forall, (mk_id "e",
352                               Some (mk_appl [mk_sym "eq";NotationPt.Implicit `JustOne; mk_id "x"; mk_id "y"])),
353                              outer)))))
354   in
355   pp (lazy ("discriminator = " ^ (NotationPp.pp_term status principle)));
356
357   (* PHASE 2: create the object for the proof of the principle: we'll name it
358    * "theorem" *)
359   let status, theorem =
360    GrafiteDisambiguate.disambiguate_nobj status ~baseuri 
361     (baseuri ^ name ^ ".def",0,
362       NotationPt.Theorem
363        (`Theorem,name,principle,
364          Some (NotationPt.Implicit (`Tagged "inv")),`DiscriminationPrinciple))
365   in 
366   let uri,height,nmenv,nsubst,nobj = theorem in
367   let ninitial_stack = Continuationals.Stack.of_nmetasenv nmenv in
368   let status = status#set_obj theorem in
369   let status = status#set_stack ninitial_stack in
370   let status = subst_metasenv_and_fix_names status in
371
372   (* PHASE 3: we finally prove the discrimination principle *)
373   let dbranch it ~use_jmeq leftno consno =
374     let refl_id = mk_sym "refl" in
375     pp (lazy (Printf.sprintf "dbranch %d %d" leftno consno));
376     let nlist = HExtlib.list_seq 0 (nargs it leftno consno) in
377     (* (\forall ...\forall P.\forall DH : ( ... = ... -> P). P) *)
378     let params = List.map (fun x -> NTactics.intro_tac ("a" ^ string_of_int x)) nlist in
379         (* NTactics.reduce_tac ~reduction:(`Normalize true)
380          * ~where:default_pattern::*)
381         params @ [
382         NTactics.intro_tac "P";
383         NTactics.intro_tac "DH";
384         NTactics.apply_tac ("",0,mk_id "DH");
385         NTactics.apply_tac ("",0,refl_id); (* well, it works even if no goal is selected after applying DH... *)
386     ] in
387   let dbranches it ~use_jmeq leftno =
388     pp (lazy (Printf.sprintf "dbranches %d" leftno));
389     let nbranches = List.length cl in 
390     let branches = iter (fun n acc -> 
391       let m = nbranches - n - 1 in
392       if m = 0 then acc @ (dbranch it ~use_jmeq leftno m)
393       else acc @ NTactics.shift_tac :: (dbranch it ~use_jmeq
394       leftno m))
395       (nbranches-1) [] in
396     if nbranches > 1 then
397          NTactics.branch_tac ~force:false:: branches @ [NTactics.merge_tac]
398     else branches
399   in
400   let print_tac s status = pp s ; status in 
401
402   let status =
403    NTactics.block_tac (
404     [print_tac (lazy "ci sono") (*;
405      NTactics.reduce_tac ~reduction:(`Normalize true) ~where:default_pattern *)
406     ]
407   @ List.map (fun x -> NTactics.intro_tac x) params @
408     [NTactics.intro_tac "x";
409      NTactics.intro_tac "y";
410      NTactics.intro_tac "Deq";
411     print_tac (lazy "ci sono 2");
412      NTactics.rewrite_tac ~dir:`RightToLeft ~what:("",0,mk_id "Deq") ~where:default_pattern;
413      NTactics.cases_tac ~what:("",0,mk_id "x") ~where:default_pattern]
414   @ dbranches it ~use_jmeq leftno) status
415   in status, status#obj
416 ;;
417
418 let hd_of_term = function
419   | NCic.Appl (hd::_) -> hd
420   | t -> t
421 ;;
422
423 let name_of_rel ~context rel =
424   let s, _ = List.nth context (rel-1) in s
425 ;;
426
427 (* let lookup_in_ctx ~context n =
428   List.nth context ((List.length context) - n - 1)
429 ;;*)
430
431 let discriminate_tac ~context cur_eq status =
432   pp (lazy (Printf.sprintf "discriminate: equation %s" (name_of_rel ~context cur_eq)));
433
434   
435   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
436   let _,ctx' = HExtlib.split_nth cur_eq context in
437   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
438   let status, s = term_of_cic_term status s ctx' in
439   let status,it,use_jmeq = 
440     let it,use_jmeq = match s with
441       | NCic.Appl [_;it;_;_] -> it,false
442       | NCic.Appl [_;it;_;_;_] -> it,true
443       | _ -> assert false in
444     (* XXX: serve? ho già fatto whd *)
445     let status, it = whd status ctx' (mk_cic_term ctx' it) in
446     let status, it = term_of_cic_term status it ctx' in
447     let _uri,indtyno,its = match it with
448       | NCic.Const (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r) 
449       | NCic.Appl (NCic.Const 
450           (NReference.Ref (uri, NReference.Ind (_,indtyno,_)) as r)::_) -> 
451         uri, indtyno, NCicEnvironment.get_checked_indtys status r
452       | _ -> pp (lazy ("discriminate: indty ="  ^ status#ppterm
453                   ~metasenv:[] ~subst:[] ~context:[] it)) ; assert false in
454     let _,_,its,_,_ = its in
455     status,List.nth its indtyno, use_jmeq
456   in
457   
458   let itnargs = 
459     let _,_,arity,_ = it in 
460     List.length (arg_list 0 arity) in
461   let _,itname,_,_ = it in
462   let params = List.map (fun x -> "a" ^ string_of_int x) (HExtlib.list_seq 1 (itnargs+1)) in
463   let principle_name = 
464     if use_jmeq then itname ^ "_jmdiscr"
465     else itname ^ "_discr"
466   in
467   pp (lazy ("apply (" ^ principle_name ^ " " ^
468             (String.concat "" (HExtlib.mk_list "?" (List.length params + 2))) ^
469             " " ^ eq_name ^ ")"));
470   NTactics.apply_tac ("",0,mk_appl ([mk_id principle_name]@
471                                 HExtlib.mk_list (NotationPt.Implicit `JustOne) (List.length params + 2) @
472                                 [mk_id eq_name ])) status
473 ;;
474
475 let saturate_skip status context skip =
476   HExtlib.list_uniq
477     (List.fold_left
478       (fun acc x -> 
479          let ix = HExtlib.list_index ((=) x) (List.map fst context)
480          in match ix with
481          | None -> acc
482          | Some (i,_) -> 
483             fst (cascade_select_in_ctx status ~subst:(get_subst status) context [] (i+1)) @ acc) skip skip)
484 ;;
485       
486 let subst_tac ~context ~dir skip cur_eq =
487   fun status as oldstatus ->
488   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
489   let _,ctx' = HExtlib.split_nth cur_eq context in
490   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
491   let status, s = term_of_cic_term status s ctx' in
492   let skip = saturate_skip status context skip in
493   pp (lazy (Printf.sprintf "subst: equation %s" eq_name));
494     let l, r = match s with
495       | NCic.Appl [_;_;t1;t2] | NCic.Appl [_;_;t1;_;t2] -> t1,t2
496       | _ -> assert false in
497     let var = match dir with
498       | `LeftToRight -> l
499       | `RightToLeft -> r in
500     (* let var = match var with
501       | NCic.Rel i -> i
502       | _ -> assert false in *)
503     let names_to_gen, _ = 
504       match var with 
505       | NCic.Rel var ->
506         cascade_select_in_ctx status ~subst:(get_subst status) context skip (var+cur_eq)
507       | _ -> cascade_select_in_ctx status ~subst:(get_subst status) context skip cur_eq in
508     let varname = match var with
509       | NCic.Rel var -> 
510           let name,_ = List.nth context (var+cur_eq-1) in
511           HLog.warn (Printf.sprintf "destruct: trying to remove variable: %s" name);
512           [name]
513       | _ -> []
514     in      
515     let names_to_gen = List.filter (fun n -> n <> eq_name) names_to_gen in
516     if (List.exists (fun x -> List.mem x skip) names_to_gen)
517       then oldstatus
518     else 
519     let gen_tac x =
520       (fun s -> 
521       let x' = String.concat " " x in
522       let x = List.map mk_id x in
523       (* let s = NTactics.print_tac false ("@generalize " ^ x') s in *)
524       generalize0_tac x s) in
525     NTactics.block_tac (
526                 (* (List.map gen_tac names_to_gen)@ *)
527             [gen_tac (List.rev names_to_gen);
528                         NTactics.clear_tac names_to_gen;
529                  NTactics.rewrite_tac ~dir 
530                    ~what:("",0,mk_id eq_name) ~where:default_pattern;
531 (*                 NTactics.reduce_tac ~reduction:(`Normalize true)
532                    ~where:default_pattern;*)
533                  (* XXX: temo che la clear multipla funzioni bene soltanto se
534                   * gli identificatori sono nell'ordine giusto.
535                   * Per non saper né leggere né scrivere, usiamo due clear
536                   * invece di una *)
537                  NTactics.try_tac (NTactics.clear_tac [eq_name]);
538                  NTactics.try_tac (NTactics.clear_tac varname);
539 ]@
540                  (List.map NTactics.intro_tac (List.rev names_to_gen))) status
541 ;;
542
543 let clearid_tac ~context skip cur_eq =
544   fun status ->
545   let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
546   let _,ctx' = HExtlib.split_nth cur_eq context in
547   let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
548   let status, s = term_of_cic_term status s ctx' in
549   let skip = saturate_skip status context skip in
550
551   pp (lazy (Printf.sprintf "clearid: equation %s" eq_name));
552   let streicher_id = mk_id "streicherK" in
553   let names_to_gen, _ = 
554     cascade_select_in_ctx status ~subst:(get_subst status) context skip cur_eq in
555   let gen_tac x = generalize0_tac (List.map mk_id x) in
556   
557   match s with
558   (* jmeq *)
559   | NCic.Appl [_;_;_;_;_] ->
560       let names_to_gen = List.rev names_to_gen in
561       (*let gen_eq = NTactics.generalize_tac
562        ~where:("",0,(Some (mk_appl [mk_id "jmeq_to_eq";
563                                     NotationPt.Implicit `JustOne; 
564                                     NotationPt.Implicit `JustOne; 
565                                     NotationPt.Implicit `JustOne; 
566                                     mk_id eq_name]),[], Some
567                                     NotationPt.UserInput)) in*)
568       let gen_eq = generalize0_tac 
569                           [mk_appl [mk_id "jmeq_to_eq";
570                                     NotationPt.Implicit `JustOne; 
571                                     NotationPt.Implicit `JustOne; 
572                                     NotationPt.Implicit `JustOne; 
573                                     mk_id eq_name]] in
574       NTactics.block_tac ((gen_tac (List.rev names_to_gen))::gen_eq::
575                   [NTactics.clear_tac names_to_gen;
576                    NTactics.try_tac (NTactics.clear_tac [eq_name]);
577                    NTactics.apply_tac ("",0, mk_appl [streicher_id;
578                                                     NotationPt.Implicit `JustOne;
579                                                     NotationPt.Implicit `JustOne;
580                                                     NotationPt.Implicit `JustOne;
581                                                     NotationPt.Implicit `JustOne]);
582                    ] @
583                    (List.map NTactics.intro_tac names_to_gen)) status
584
585     (* leibniz *)
586   | NCic.Appl [_;_;_;_] ->
587       begin
588        let names_to_gen, _ = 
589          cascade_select_in_ctx status ~subst:(get_subst status) context skip cur_eq in
590        let names_to_gen = eq_name :: (List.rev names_to_gen) in
591        NTactics.block_tac ((gen_tac names_to_gen)::
592                    [NTactics.clear_tac names_to_gen;
593                     NTactics.apply_tac ("",0, mk_appl [streicher_id;
594                                                     NotationPt.Implicit `JustOne;
595                                                     NotationPt.Implicit `JustOne;
596                                                     NotationPt.Implicit `JustOne;
597                                                     NotationPt.Implicit `JustOne])
598    (*                 NTactics.reduce_tac ~reduction:(`Normalize true) 
599                       ~where:default_pattern *)
600                     ] @
601                     let names_to_intro = List.tl names_to_gen in
602                     (List.map NTactics.intro_tac names_to_intro)) status
603      end
604   | _ -> assert false
605
606 ;;
607
608 let get_ctx st goal =
609     ctx_of (get_goalty st goal)
610 ;;
611
612 (* = select + classify *)
613 let select_eq ctx acc domain status goal =
614   let classify ~use_jmeq ~subst ctx' l r =
615     (* FIXME: metasenv *)
616     if NCicReduction.are_convertible status ~metasenv:[] ~subst ctx' l r 
617       then status, `Identity
618       else status, (match hd_of_term l, hd_of_term r with
619         | NCic.Const (NReference.Ref (_,NReference.Con (_,ki,nleft)) as kref),
620           NCic.Const (NReference.Ref (_,NReference.Con (_,kj,_))) -> 
621             if ki != kj then `Discriminate (0,true, use_jmeq)
622             else
623               let rit = NReference.mk_indty true kref in
624               let _,_,its,_,itno = NCicEnvironment.get_checked_indtys status rit in 
625               let it = List.nth its itno in
626               let newprods = nargs it nleft (ki-1) in
627               `Discriminate (newprods, false, use_jmeq) 
628         | NCic.Rel j, _  
629             when NCicTypeChecker.does_not_occur status ~subst ctx' (j-1) j r
630               && l = NCic.Rel j -> `Subst `LeftToRight
631         | _, NCic.Rel j 
632             when NCicTypeChecker.does_not_occur status ~subst ctx' (j-1) j l 
633               && r = NCic.Rel j -> `Subst `RightToLeft
634         | (NCic.Rel _, _ | _, NCic.Rel _ ) -> `Cycle (* could be a blob too... *)
635         | _ -> `Blob) in
636   let rec aux i =
637     try
638       let index = List.length ctx - i in
639       pp (lazy ("provo classify di index = " ^string_of_int index));
640       match (List.nth ctx (index - 1)) with
641       | n, (NCic.Decl ty | NCic.Def (ty,_)) ->
642           (let _,ctx_ty = HExtlib.split_nth index ctx in 
643            let status, ty = NTacStatus.whd status ctx_ty (mk_cic_term ctx_ty ty) in
644            let status, ty = term_of_cic_term status ty ctx_ty in
645            pp (lazy (Printf.sprintf "select_eq tries %s" (status#ppterm ~context:ctx_ty ~subst:[] ~metasenv:[] ty)));
646            let status, kind = match ty with
647            | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;_;l;r] 
648                when NUri.name_of_uri u = "eq" ->
649                classify ~use_jmeq:false ~subst:(get_subst status) ctx_ty l r
650            | NCic.Appl [NCic.Const (NReference.Ref (u,_)) ;lty;l;rty;r]
651                when NUri.name_of_uri u = "jmeq" && 
652                  NCicReduction.are_convertible status ~metasenv:[] 
653                    ~subst:(get_subst status) ctx_ty lty rty
654                -> classify ~use_jmeq:true ~subst:(get_subst status) ctx_ty l r
655            | _ -> status, `NonEq 
656            in match kind with
657               | `Identity ->
658                   let status, goalty = term_of_cic_term status (get_goalty status goal) ctx in
659                      status, Some (List.length ctx - i), kind
660               | `Cycle | `Blob | `NonEq -> aux (i+1) (* XXX: skip cyclic/blob equations for now *)
661               | _ -> 
662                  if (List.for_all (fun x -> x <> n) acc) && 
663                     (List.exists (fun x -> x = n) domain) 
664                  then status, Some (List.length ctx - i), kind
665                  else aux (i+1))
666     with Failure _ | Invalid_argument _ -> status, None, `Blob
667   in aux 0
668 ;;
669
670 let tagged_intro_tac curtag name =
671   match curtag with
672   | `Notag -> NTactics.intro_tac name
673   | `Eq use_jmeq ->
674       NTactics.block_tac
675         [ NTactics.intro_tac name 
676         ; NTactics.reduce_tac 
677             ~reduction:(`Whd true) ~where:((if use_jmeq then hp_pattern_jm else hp_pattern) name) ]
678         
679 (*        status in
680       distribute_tac (fun s g ->
681         let eq_name,(NCic.Decl s | NCic.Def (s,_)) = List.nth context (cur_eq-1) in
682         let _,ctx' = HExtlib.split_nth cur_eq context in
683         let status, s = NTacStatus.whd status ctx' (mk_cic_term ctx' s) in
684         let status, s = term_of_cic_term status s ctx' in
685         let use_jmeq =
686           match s with
687           | NCic.Appl [_;it;t1;t2] -> false
688           | NCic.Appl [_;it;t1;_;t2] -> true
689           | _ -> assert false in
690       ) status
691     let it, t1, t2, use_jmeq = match s with
692       | NCic.Appl [_;it;t1;t2] -> it,t1,t2,false
693       | NCic.Appl [_;it;t1;_;t2] -> it,t1,t2,true
694       | _ -> assert false in
695            [ NTactics.intro_tac name
696            ; NTactics.reduce_tac ~reduction:(`Whd true) ~where:prod_pattern ]*)
697 ;;
698
699 let rec destruct_tac0 tags acc domain skip status goal =
700   let pptag = function
701     | `Eq false -> "eq"
702     | `Eq true -> "jmeq"
703     | `Notag -> "reg"
704   in
705   let pptags tags = String.concat ", " (List.map pptag tags) in
706   let ctx = get_ctx status goal in
707   let subst = get_subst status in
708   let get_newgoal os ns ogoal =
709     let go, gc = NTactics.compare_statuses ~past:os ~present:ns in
710     let go' = ([ogoal] @- gc) @+ go in
711       match go' with [] -> assert false | g::_ -> g
712   in
713   let status, selection, kind  = select_eq ctx acc domain status goal in
714   pp (lazy ("destruct: acc is " ^ String.concat "," acc ));
715   match selection, kind with
716   | None, _ -> 
717     pp (lazy (Printf.sprintf 
718        "destruct: no selection, context is %s, stack is %s" 
719        (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
720      (match tags with 
721       | [] -> status
722       | curtag::tags' ->
723         let fresh = mk_fresh_name ctx 'e' 0 in 
724         let status' = NTactics.exec (tagged_intro_tac curtag fresh) status goal in
725         destruct_tac0 tags' acc (fresh::domain) skip status' 
726           (get_newgoal status status' goal))
727   | Some cur_eq, `Discriminate (newprods,conflict,use_jmeq) -> 
728     pp (lazy (Printf.sprintf 
729       "destruct: discriminate - nselection is %d, context is %s,stack is %s" 
730        cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
731       let status' = NTactics.exec (discriminate_tac ~context:ctx cur_eq) status goal in
732       if conflict then status'
733       else 
734         let newtags = HExtlib.mk_list (`Eq use_jmeq) newprods in
735         destruct_tac0 (newtags@tags) 
736              (name_of_rel ~context:ctx cur_eq::acc) 
737              (List.filter (fun x -> x <> name_of_rel ~context:ctx cur_eq) domain)
738              skip 
739              status' (get_newgoal status status' goal)
740   | Some cur_eq, `Subst dir ->
741     pp (lazy (Printf.sprintf 
742       "destruct: subst - selection is %d, context is %s, stack is %s" 
743         cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
744     let status' = NTactics.exec (subst_tac ~context:ctx ~dir skip cur_eq) status goal in
745       pp (lazy (Printf.sprintf " ctx after subst = %s" (status#ppcontext ~metasenv:[] ~subst (get_ctx status' (get_newgoal status status' goal)))));
746     let eq_name,_ = List.nth ctx (cur_eq-1) in
747     let newgoal = get_newgoal status status' goal in
748     let has_cleared = 
749      try 
750        let _ = NTactics.find_in_context eq_name (get_ctx status' newgoal) in false
751      with 
752       | Sys.Break as e -> raise e
753       |_ -> true in
754     let rm_eq b l = if b then List.filter (fun x -> x <> eq_name) l else l in
755     let acc = rm_eq has_cleared acc in
756     let skip = rm_eq has_cleared skip in
757     let domain = rm_eq has_cleared domain in
758       destruct_tac0 tags acc domain skip status' newgoal
759  | Some cur_eq, `Identity ->
760     pp (lazy (Printf.sprintf 
761       "destruct: identity - selection is %d, context is %s, stack is %s" 
762         cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
763       let eq_name,_ = List.nth ctx (cur_eq-1) in
764       let status' = NTactics.exec (clearid_tac ~context:ctx skip cur_eq) status goal in
765       let newgoal = get_newgoal status status' goal in
766       let has_cleared = 
767        try 
768          let _ = NTactics.find_in_context eq_name (get_ctx status' newgoal) in false
769        with 
770          | Sys.Break as e -> raise e         
771          | _ -> true in
772       let rm_eq b l = if b then List.filter (fun x -> x <> eq_name) l else l in
773       let acc = rm_eq has_cleared acc in
774       let skip = rm_eq has_cleared skip in
775       let domain = rm_eq has_cleared domain in
776         destruct_tac0 tags acc domain skip status' newgoal
777   | Some cur_eq, `Cycle -> (* TODO, should never happen *)
778     pp (lazy (Printf.sprintf 
779       "destruct: cycle - selection is %d, context is %s, stack is %s" 
780         cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
781       assert false
782   | Some cur_eq, `Blob ->
783     pp (lazy (Printf.sprintf 
784       "destruct: blob - selection is %d, context is %s, stack is %s"
785       cur_eq (status#ppcontext ~metasenv:[] ~subst ctx) (pptags tags)));
786       assert false
787   | _ -> assert false
788 ;;
789
790 let destruct_tac dom skip s = 
791   NTactics.distribute_tac 
792     (fun s' g -> 
793      let ctx = get_ctx s' g in
794      let domain = match dom with
795        | None -> List.map (fun (n,_) -> n) ctx
796        | Some l -> l 
797      in
798      destruct_tac0 [] [] domain skip s' g) s;;