← Back to branch summary

~ubuntu-branches/ubuntu/wily/coq-doc/wily

« back to all changes in this revision

Viewing changes to test-suite/ideal-features/evars_subst.v

  • Committer: Bazaar Package Importer
  • Author(s): Stéphane Glondu, Stéphane Glondu, Samuel Mimram
  • Date: 2010-01-07 22:50:39 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20100107225039-n3cq82589u0qt0s2
Tags: 8.2pl1-1
http://bugs.debian.org/563669
http://bugs.debian.org/543545
[ Stéphane Glondu ]
* New upstream release (Closes: #563669)
  - remove patches
* Packaging overhaul:
  - use git, advertise it in Vcs-* fields of debian/control
  - use debhelper 7 and dh with override
  - use source format 3.0 (quilt)
* debian/control:
  - set Maintainer to d-o-m, set Uploaders to Sam and myself
  - add Homepage field
  - bump Standards-Version to 3.8.3
* Register PDF documentation into doc-base
* Add debian/watch
* Update debian/copyright

[ Samuel Mimram ]
* Change coq-doc's description to mention that it provides documentation in
  pdf format, not postscript, closes: #543545.

Show diffs side-by-side

added added

removed removed

Lines of Context:
test-suite/ideal-features/evars_subst.v
 
1
(* Bug report #932 *)
 
2
(* Expected time < 1.00s *)
 
3
 
 
4
(* Let n be the number of let-in. The complexity comes from the fact
 
5
   that each implicit arguments of f was in a larger and larger
 
6
   context. To compute the type of "let _ := f ?Tn 0 in f ?T 0", 
 
7
   "f ?Tn 0" is substituted in the type of "f ?T 0" which is ?T. This
 
8
   type is an evar instantiated on the n variables denoting the "f ?Ti 0".
 
9
   One obtain "?T[1;...;n-1;f ?Tn[1;...;n-1] 0]". To compute the
 
10
   type of "let _ := f ?Tn-1 0 in let _ := f ?Tn 0 in f ?T 0", another
 
11
   substitution is done leading to 
 
12
   "?T[1;...;n-2;f ?Tn[1;...;n-2] 0;f ?Tn[1;...;n-2;f ?Tn[1;...;n-2] 0] 0]"
 
13
   and so on. At the end, we get a term of exponential size *)
 
14
 
 
15
(* A way to cut the complexity could have been to remove the dependency in
 
16
   anonymous variables in evars but this breaks intuitive behaviour
 
17
   (see Case15.v); another approach could be to substitute lazily
 
18
   and/or to simultaneously substitute let binders and evars *)
 
19
 
 
20
Variable P : Set -> Set.
 
21
Variable f : forall A : Set, A -> P A.
 
22
 
 
23
Time Check
 
24
  let _ := f _ 0 in
 
25
  let _ := f _ 0 in
 
26
  let _ := f _ 0 in
 
27
  let _ := f _ 0 in
 
28
 
 
29
  let _ := f _ 0 in
 
30
  let _ := f _ 0 in
 
31
  let _ := f _ 0 in
 
32
  let _ := f _ 0 in
 
33
 
 
34
  let _ := f _ 0 in
 
35
  let _ := f _ 0 in
 
36
  let _ := f _ 0 in
 
37
  let _ := f _ 0 in
 
38
  let _ := f _ 0 in
 
39
 
 
40
  let _ := f _ 0 in
 
41
  let _ := f _ 0 in
 
42
  let _ := f _ 0 in
 
43
  let _ := f _ 0 in
 
44
  let _ := f _ 0 in
 
45
 
 
46
  let _ := f _ 0 in
 
47
  let _ := f _ 0 in
 
48
  let _ := f _ 0 in
 
49
  let _ := f _ 0 in
 
50
  let _ := f _ 0 in
 
51
 
 
52
    f _ 0.
 
53