diff options
Diffstat (limited to 'test-suite/ideal-features')
-rw-r--r-- | test-suite/ideal-features/Case9.v | 12 | ||||
-rw-r--r-- | test-suite/ideal-features/complexity/evars_subst.v | 53 |
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. + |