Patchwork C++ PATCH for c++/48969 (infinite template recursion with enum scope)

login
register
mail settings
Submitter Jason Merrill
Date May 13, 2011, 10:22 p.m.
Message ID <4DCDAF1A.1060802@redhat.com>
Download mbox | patch
Permalink /patch/95534/
State New
Headers show

Comments

Jason Merrill - May 13, 2011, 10:22 p.m.
In C++0x there are a couple of ways for a function signature to depend 
on itself, leading to infinite recursion in substitution during template 
argument deduction.  This patch adds checking for that.

My initial implementation used a VEC to keep track of current deductions 
in process, but I switched it to use a hash table instead; the overhead 
for using a hash table rather than a VEC on the most common case (very 
low deduction nesting) is small, but on highly recursive template 
metaprogramming the difference in complexity can make a difference.

Unfortunately, the difference one way or the other is dwarfed by the 
overhead from doing this checking at all (about 2% of compile time 
compiling stdc++.h), but I don't see how to avoid it.

Tested x86_64-pc-linux-gnu, applying to trunk.

Patch

commit ec136d9e1be788f0045a9adbd58cba6014fe0405
Author: Jason Merrill <jason@redhat.com>
Date:   Fri May 13 10:43:05 2011 -0400

    	PR c++/48969
    	* pt.c (deduction_tsubst_fntype): New.
    	(fn_type_unification): Use it.

diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 50ed180..f155c1a 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -13525,6 +13525,53 @@  check_instantiated_args (tree tmpl, tree args, tsubst_flags_t complain)
   return result;
 }
 
+static GTY((param_is (spec_entry))) htab_t current_deduction_substs;
+
+/* In C++0x, it's possible to have a function template whose type depends
+   on itself recursively.  This is most obvious with decltype, but can also
+   occur with enumeration scope (c++/48969).  So we need to catch infinite
+   recursion and reject the substitution at deduction time.  */
+
+static tree
+deduction_tsubst_fntype (tree fn, tree targs)
+{
+  spec_entry **slot;
+  spec_entry elt;
+  tree r;
+  hashval_t hash;
+
+  tree fntype = TREE_TYPE (fn);
+
+  /* We don't need to worry about this in C++98.  */
+  if (cxx_dialect < cxx0x)
+    return tsubst (fntype, targs, tf_none, NULL_TREE);
+
+  elt.tmpl = fn;
+  elt.args = targs;
+  elt.spec = NULL_TREE;
+  hash = hash_specialization (&elt);
+
+  slot = (spec_entry **)
+    htab_find_slot_with_hash (current_deduction_substs, &elt, hash, INSERT);
+  if (*slot)
+    /* We already have an entry for this.  */
+    (*slot)->spec = r = error_mark_node;
+  else
+    {
+      /* Create a new entry.  */
+      spec_entry *p = *slot = ggc_alloc_spec_entry ();
+      *p = elt;
+
+      r = tsubst (fntype, targs, tf_none, NULL_TREE);
+      if (p->spec == error_mark_node)
+	r = error_mark_node;
+
+      htab_remove_elt_with_hash (current_deduction_substs, p, hash);
+    }
+
+  return r;
+}
+
 /* Instantiate the indicated variable or function template TMPL with
    the template arguments in TARG_PTR.  */
 
@@ -13788,7 +13835,7 @@  fn_type_unification (tree fn,
         incomplete = NUM_TMPL_ARGS (explicit_targs) != NUM_TMPL_ARGS (targs);
 
       processing_template_decl += incomplete;
-      fntype = tsubst (fntype, converted_args, tf_none, NULL_TREE);
+      fntype = deduction_tsubst_fntype (fn, converted_args);
       processing_template_decl -= incomplete;
 
       if (fntype == error_mark_node)
@@ -13859,7 +13906,7 @@  fn_type_unification (tree fn,
        substitution results in an invalid type, as described above,
        type deduction fails.  */
     {
-      tree substed = tsubst (TREE_TYPE (fn), targs, tf_none, NULL_TREE);
+      tree substed = deduction_tsubst_fntype (fn, targs);
       if (substed == error_mark_node)
 	return 1;
 
@@ -19283,6 +19330,10 @@  init_template_processing (void)
 					  hash_specialization,
 					  eq_specializations,
 					  ggc_free);
+  if (cxx_dialect >= cxx0x)
+    current_deduction_substs = htab_create_ggc (37, hash_specialization,
+						eq_specializations,
+						ggc_free);
 }
 
 /* Print stats about the template hash tables for -fstats.  */
@@ -19298,6 +19349,10 @@  print_template_statistics (void)
 	   "%f collisions\n", (long) htab_size (type_specializations),
 	   (long) htab_elements (type_specializations),
 	   htab_collisions (type_specializations));
+  fprintf (stderr, "current_deduction_substs: size %ld, %ld elements, "
+	   "%f collisions\n", (long) htab_size (current_deduction_substs),
+	   (long) htab_elements (current_deduction_substs),
+	   htab_collisions (current_deduction_substs));
 }
 
 #include "gt-cp-pt.h"
diff --git a/gcc/testsuite/g++.dg/cpp0x/decltype26.C b/gcc/testsuite/g++.dg/cpp0x/decltype26.C
new file mode 100644
index 0000000..9eb9411
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp0x/decltype26.C
@@ -0,0 +1,16 @@ 
+// { dg-options -std=c++0x }
+
+struct A { };
+
+template <class T>
+decltype(f(T())) f(T t)
+{
+  return f(t);
+}
+
+int main()
+{
+  f(A());			// { dg-error "no match" }
+}
+
+// { dg-prune-output "note" }
diff --git a/gcc/testsuite/g++.dg/cpp0x/enum11.C b/gcc/testsuite/g++.dg/cpp0x/enum11.C
new file mode 100644
index 0000000..98b6b00
--- /dev/null
+++ b/gcc/testsuite/g++.dg/cpp0x/enum11.C
@@ -0,0 +1,10 @@ 
+// PR c++/48969
+// { dg-options -std=c++0x }
+
+template<unsigned int N> struct Pair { };
+struct Foo { enum { Mask = 1 }; } foo;
+template<typename A, typename B> class Pair<A::Mask | B::Mask>
+operator|(const A &, const B &)
+{ }
+
+Pair<Foo::Mask> f = foo|foo;