2 files changed, 65 insertions, 0 deletions
diff --git a/test-suite/ideal-features/Case9.v b/test-suite/ideal-features/Case9.v
new file mode 100644
index 000000000..800c431ec
--- /dev/null
+++ b/test-suite/ideal-features/Case9.v
@@ -0,0 +1,12 @@
+(* Exemple soumis par Pierre Corbineau (bug #1671) *)
+
+CoInductive hdlist : unit -> Type :=
+| cons : hdlist tt -> hdlist tt.
+
+Variable P : forall bo, hdlist bo -> Prop.
+Variable all : forall bo l, P bo l.
+
+Definition F (l:hdlist tt) : P tt l := 
+match l in hdlist u return P u l with
+| cons (cons l') => all tt _
+end.
diff --git a/test-suite/ideal-features/complexity/evars_subst.v b/test-suite/ideal-features/complexity/evars_subst.v
new file mode 100644
index 000000000..6f9f86a95
--- /dev/null
+++ b/test-suite/ideal-features/complexity/evars_subst.v
@@ -0,0 +1,53 @@
+(* Bug report #932 *)
+(* Expected time < 1.00s *)
+
+(* Let n be the number of let-in. The complexity comes from the fact
+   that each implicit arguments of f was in a larger and larger
+   context. To compute the type of "let _ := f ?Tn 0 in f ?T 0", 
+   "f ?Tn 0" is substituted in the type of "f ?T 0" which is ?T. This
+   type is an evar instantiated on the n variables denoting the "f ?Ti 0".
+   One obtain "?T[1;...;n-1;f ?Tn[1;...;n-1] 0]". To compute the
+   type of "let _ := f ?Tn-1 0 in let _ := f ?Tn 0 in f ?T 0", another
+   substitution is done leading to 
+   "?T[1;...;n-2;f ?Tn[1;...;n-2] 0;f ?Tn[1;...;n-2;f ?Tn[1;...;n-2] 0] 0]"
+   and so on. At the end, we get a term of exponential size *)
+
+(* A way to cut the complexity could have been to remove the dependency in
+   anonymous variables in evars but this breaks intuitive behaviour
+   (see Case15.v); another approach could be to substitute lazily
+   and/or to simultaneously substitute let binders and evars *)
+
+Variable P : Set -> Set.
+Variable f : forall A : Set, A -> P A.
+
+Time Check
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+ 
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+  let _ := f _ 0 in
+
+    f _ 0.
+