From patchwork Fri May 13 22:22:18 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jason Merrill X-Patchwork-Id: 95534 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 8C63AB6EED for ; Sat, 14 May 2011 08:22:43 +1000 (EST) Received: (qmail 8188 invoked by alias); 13 May 2011 22:22:39 -0000 Received: (qmail 8179 invoked by uid 22791); 13 May 2011 22:22:37 -0000 X-SWARE-Spam-Status: No, hits=-6.3 required=5.0 tests=AWL, BAYES_00, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, TW_FN, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Fri, 13 May 2011 22:22:20 +0000 Received: from int-mx10.intmail.prod.int.phx2.redhat.com (int-mx10.intmail.prod.int.phx2.redhat.com [10.5.11.23]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id p4DMMJdO020294 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Fri, 13 May 2011 18:22:19 -0400 Received: from [127.0.0.1] (ovpn-113-120.phx2.redhat.com [10.3.113.120]) by int-mx10.intmail.prod.int.phx2.redhat.com (8.14.4/8.14.4) with ESMTP id p4DMMIYI011973 for ; Fri, 13 May 2011 18:22:19 -0400 Message-ID: <4DCDAF1A.1060802@redhat.com> Date: Fri, 13 May 2011 18:22:18 -0400 From: Jason Merrill User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.17) Gecko/20110428 Fedora/3.1.10-1.fc14 Lightning/1.0b2 Thunderbird/3.1.10 MIME-Version: 1.0 To: gcc-patches List Subject: C++ PATCH for c++/48969 (infinite template recursion with enum scope) Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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. commit ec136d9e1be788f0045a9adbd58cba6014fe0405 Author: Jason Merrill 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 +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 struct Pair { }; +struct Foo { enum { Mask = 1 }; } foo; +template class Pair +operator|(const A &, const B &) +{ } + +Pair f = foo|foo;