Keyed unification option, compiling the whole standard library

(but deactivated still).

Set Keyed Unification to activate the option, which changes
subterm selection to _always_ use full conversion _after_ finding a
subterm whose head/key matches the key of the term we're looking for.
This applies to rewrite and higher-order unification in
apply/elim/destruct.

Most proof scripts already abide by these semantics. For those that
don't, it's usually only a matter of using:

Declare Equivalent Keys f g.

This make keyed unification consider f and g to match as keys.
This takes care of most cases of abbreviations: typically Def foo :=
bar and rewriting with a bar-headed lhs in a goal mentioning foo works
once they're set equivalent.
For canonical structures, these hints should be automatically declared.

For non-global-reference headed terms, the key is the constructor name
(Sort, Prod...). Evars and metas are no keys.

INCOMPATIBILITIES:
In FMapFullAVL, a Function definition doesn't go through with keyed
unification on.

10 files changed, 23 insertions, 7 deletions

diff --git a/theories/FSets/FMapFullAVL.v b/theories/FSets/FMapFullAVL.v
index dea23d68c..a7be32328 100644
--- a/theories/FSets/FMapFullAVL.v
+++ b/theories/FSets/FMapFullAVL.v
@@ -674,6 +674,8 @@ Module IntMake_ord (I:Int)(X: OrderedType)(D : OrderedType) <:
   Definition cardinal_e_2 ee :=
    (cardinal_e (fst ee) + cardinal_e (snd ee))%nat.
 
+  Local Unset Keyed Unification.
+
   Function compare_aux (ee:Raw.enumeration D.t * Raw.enumeration D.t)
    { measure cardinal_e_2 ee } : comparison :=
   match ee with
diff --git a/theories/FSets/FSetCompat.v b/theories/FSets/FSetCompat.v
index 6b3d86d39..b1769da3d 100644
--- a/theories/FSets/FSetCompat.v
+++ b/theories/FSets/FSetCompat.v
@@ -283,6 +283,8 @@ Module Update_WSets
 
   Lemma is_empty_spec : is_empty s = true <-> Empty s.
   Proof. intros; symmetry; apply MF.is_empty_iff. Qed.
+  
+  Declare Equivalent Keys In M.In.
 
   Lemma add_spec : In y (add x s) <-> E.eq y x \/ In y s.
   Proof. intros. rewrite MF.add_iff. intuition. Qed.
diff --git a/theories/FSets/FSetPositive.v b/theories/FSets/FSetPositive.v
index 88011ff1c..7398c6d65 100644
--- a/theories/FSets/FSetPositive.v
+++ b/theories/FSets/FSetPositive.v
@@ -306,6 +306,9 @@ Module PositiveSet <: S with Module E:=PositiveOrderedTypeBits.
   Notation "s  [<=]  t" := (Subset s t) (at level 70, no associativity).
 
   Definition eq := Equal.
+
+  Declare Equivalent Keys Equal eq.
+
   Definition lt m m' := compare_fun m m' = Lt.
 
   (** Specification of [In] *)
diff --git a/theories/MSets/MSetGenTree.v b/theories/MSets/MSetGenTree.v
index 901574235..d1d9897fb 100644
--- a/theories/MSets/MSetGenTree.v
+++ b/theories/MSets/MSetGenTree.v
@@ -970,6 +970,8 @@ Definition lt (s1 s2 : tree) : Prop :=
  exists s1' s2', Ok s1' /\ Ok s2' /\ eq s1 s1' /\ eq s2 s2'
    /\ L.lt (elements s1') (elements s2').
 
+Declare Equivalent Keys L.eq equivlistA.
+
 Instance lt_strorder : StrictOrder lt.
 Proof.
  split.
diff --git a/theories/Numbers/Cyclic/Abstract/NZCyclic.v b/theories/Numbers/Cyclic/Abstract/NZCyclic.v
index 1d5b78ec4..c9f3a774d 100644
--- a/theories/Numbers/Cyclic/Abstract/NZCyclic.v
+++ b/theories/Numbers/Cyclic/Abstract/NZCyclic.v
@@ -126,9 +126,7 @@ Let B (n : Z) := A (ZnZ.of_Z n).
 
 Lemma B0 : B 0.
 Proof.
-unfold B.
-setoid_replace (ZnZ.of_Z 0) with zero. assumption.
-red; zify. apply ZnZ.of_Z_correct. auto using gt_wB_0 with zarith.
+unfold B. apply A0.
 Qed.
 
 Lemma BS : forall n : Z, 0 <= n -> n < wB - 1 -> B n -> B (n + 1).
diff --git a/theories/Numbers/Natural/BigN/NMake_gen.ml b/theories/Numbers/Natural/BigN/NMake_gen.ml
index 8df4b7c64..dc35d087b 100644
--- a/theories/Numbers/Natural/BigN/NMake_gen.ml
+++ b/theories/Numbers/Natural/BigN/NMake_gen.ml
@@ -961,6 +961,11 @@ pr "  end.";
 pr "";
 
 pr " Ltac unfold_red := unfold reduce, %s." (iter_name 1 size "reduce_" ",");
+pr "";
+for i = 0 to size do
+pr " Declare Equivalent Keys reduce reduce_%i." i;
+done;
+pr " Declare Equivalent Keys reduce_n reduce_%i." (size + 1);
 
 pr "
  Ltac solve_red :=
diff --git a/theories/Numbers/Natural/BigN/Nbasic.v b/theories/Numbers/Natural/BigN/Nbasic.v
index 161f523ca..e8a9940bd 100644
--- a/theories/Numbers/Natural/BigN/Nbasic.v
+++ b/theories/Numbers/Natural/BigN/Nbasic.v
@@ -320,6 +320,7 @@ Section CompareRec.
  Let double_to_Z_pos: forall n x, 0 <= double_to_Z n x < double_wB n :=
    (spec_double_to_Z wm_base wm_to_Z wm_to_Z_pos).
 
+ Declare Equivalent Keys compare0_mn compare0_m.
 
  Lemma spec_compare0_mn: forall n x,
    compare0_mn n x = (0 ?= double_to_Z n x).
diff --git a/theories/Numbers/Rational/BigQ/BigQ.v b/theories/Numbers/Rational/BigQ/BigQ.v
index e866a52d6..b304b339b 100644
--- a/theories/Numbers/Rational/BigQ/BigQ.v
+++ b/theories/Numbers/Rational/BigQ/BigQ.v
@@ -88,6 +88,8 @@ exact BigQ.add_opp_diag_r. exact BigQ.neq_1_0.
 exact BigQ.div_mul_inv. exact BigQ.mul_inv_diag_l.
 Qed.
 
+Declare Equivalent Keys pow_N pow_pos.
+
 Lemma BigQpowerth :
  power_theory 1 BigQ.mul BigQ.eq Z.of_N BigQ.power.
 Proof.
diff --git a/theories/Reals/Binomial.v b/theories/Reals/Binomial.v
index ad076c488..16f2661fe 100644
--- a/theories/Reals/Binomial.v
+++ b/theories/Reals/Binomial.v
@@ -172,13 +172,12 @@ Proof.
   apply sum_eq.
   intros; apply H1.
   unfold N; apply le_lt_trans with n; [ assumption | apply lt_n_Sn ].
-  intros; unfold Bn, Cn.
-  replace (S N - S i)%nat with (N - i)%nat; reflexivity.
+  reflexivity.
   unfold An; fold N; rewrite <- minus_n_n; rewrite H0;
     simpl; ring.
   apply sum_eq.
-  intros; unfold An, Bn; replace (S N - S i)%nat with (N - i)%nat;
-    [ idtac | reflexivity ].
+  intros; unfold An, Bn.
+  change (S N - S i)%nat with (N - i)%nat.
   rewrite <- pascal;
     [ ring
       | apply le_lt_trans with n; [ assumption | unfold N; apply lt_n_Sn ] ].
diff --git a/theories/Reals/Rlimit.v b/theories/Reals/Rlimit.v
index 375cc2752..cf7b91af8 100644
--- a/theories/Reals/Rlimit.v
+++ b/theories/Reals/Rlimit.v
@@ -174,6 +174,8 @@ Definition limit_in (X X':Metric_Space) (f:Base X -> Base X')
 Definition R_met : Metric_Space :=
   Build_Metric_Space R R_dist R_dist_pos R_dist_sym R_dist_refl R_dist_tri.
 
+Declare Equivalent Keys dist R_dist.
+
 (*******************************)
 (** *      Limit 1 arg         *)
 (*******************************)