diff options
-rw-r--r-- | pretyping/evarutil.ml | 7 | ||||
-rw-r--r-- | test-suite/complexity/evars_subst.v | 54 |
2 files changed, 21 insertions, 40 deletions
diff --git a/pretyping/evarutil.ml b/pretyping/evarutil.ml index 53c619912..207ad88b3 100644 --- a/pretyping/evarutil.ml +++ b/pretyping/evarutil.ml @@ -168,15 +168,20 @@ let push_rel_context_to_named_context env typ = fold_named_context (fun env (id,b,_) l -> mkVar id :: l) env ~init:[] in (* move the rel context to a named context and extend the instance with vars of the rel context *) +(* let fv = free_rels typ in +*) let avoid = ids_of_named_context (named_context env) in let n = rel_context_length (rel_context env) in let (subst, _, _, inst, env) = Sign.fold_rel_context - (fun (na,c,t) (subst, n, avoid, inst, env) -> match na with + (fun (na,c,t) (subst, n, avoid, inst, env) -> +(* + match na with | Anonymous when not (Intset.mem n fv) -> (dummy_var::subst, n-1, avoid, inst, env) | _ -> +*) let id = next_name_away na avoid in ((mkVar id)::subst, n-1, id::avoid, mkRel n::inst, push_named (id,option_map (substl subst) c,substl subst t) env)) diff --git a/test-suite/complexity/evars_subst.v b/test-suite/complexity/evars_subst.v index 58a09dd3f..d79d9f0e0 100644 --- a/test-suite/complexity/evars_subst.v +++ b/test-suite/complexity/evars_subst.v @@ -2,20 +2,20 @@ (* 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 is to remove the dependency in - anonymous variables in evars; another approach would be to - substitute lazily and/or to simultaneously substitute let binders - and evars *) + 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. @@ -24,36 +24,12 @@ 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 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 |