[C++] Fix lambda capture duplicate handling (PR c++/89767)

Hi!

add_capture when parsing a lambda introducer uses the IDENTIFIER_MARKED
bit to detect duplicate captures.
I guess in strict C++11 that could have worked, if the introducer could
contain just identifiers, but in C++14 it has 2 problems:

1) lambda initializers can contain arbitrary expressions and
IDENTIFIER_MARKED is used during the name lookup, if we set it, then
anything we do while parsing something in the initializer will affect
name lookup of __X identifiers nested inside if there is X capture
(see the last testcase, where there is t capture and __t argument
of a constexpr template function called in the lambda initializer
and another __t argument in another constexpr template function that calls)

2) if the lambda initializer contains another lambda, the IDENTIFIER_MARKED
bit will affect also this nested lambda while it shouldn't (see
lambda-init18.C testcase)

The following patch stops using IDENTIFIER_MARKED for this and uses a
hash_set instead.  But, as I believe lambdas with 0 (or very few) explicit
captures are extremely common, I've tried not to slow down those with
allocation of a hash_set and deallocating it again, so it uses
a linear search if there are up to 8 captures and starts using a hash_set
only when getting above that count.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Or do you think allocation of an hash_set and deallocation would be in a
noise?

2019-03-19  Jakub Jelinek  <jakub@redhat.com>

	PR c++/89767
	* cp-tree.h (add_capture): Add ids argument.
	* parser.c (cp_parser_lambda_introducer): Add ids variable and pass
	its address to add_capture calls, delete it at the end.
	* lambda.c (add_capture): Add ids argument, don't use
	IDENTIFIER_MARKED, instead walk capture list linearly to find
	duplicates if short, or use hash_set otherwise.
	(register_capture_members): Don't clear IDENTIFIER_MARKED here.
	(add_default_capture): Adjust add_capture caller.

	* g++.dg/cpp1y/lambda-init18.C: New test.
	* g++.dg/cpp1y/lambda-init19.C: New test.
	* g++.dg/cpp1y/pr89767.C: New test.


	Jakub

On 3/19/19 2:14 PM, Jakub Jelinek wrote:
> Hi!
> 
> add_capture when parsing a lambda introducer uses the IDENTIFIER_MARKED
> bit to detect duplicate captures.
> I guess in strict C++11 that could have worked, if the introducer could
> contain just identifiers, but in C++14 it has 2 problems:

> The following patch stops using IDENTIFIER_MARKED for this and uses a
> hash_set instead.  But, as I believe lambdas with 0 (or very few) explicit
> captures are extremely common, I've tried not to slow down those with
> allocation of a hash_set and deallocating it again, so it uses
> a linear search if there are up to 8 captures and starts using a hash_set
> only when getting above that count.
> 
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
> 
> Or do you think allocation of an hash_set and deallocation would be in a
> noise?

I think it'd be in the noise.  The high bit is between zero and more 
than zero captures. The next most common after zero would be 1. 
Besides, identifiers are trivial to hash.

nathan

On Wed, Mar 20, 2019 at 10:34:51AM -0400, Nathan Sidwell wrote:
> On 3/19/19 2:14 PM, Jakub Jelinek wrote:
> > add_capture when parsing a lambda introducer uses the IDENTIFIER_MARKED
> > bit to detect duplicate captures.
> > I guess in strict C++11 that could have worked, if the introducer could
> > contain just identifiers, but in C++14 it has 2 problems:
> 
> > The following patch stops using IDENTIFIER_MARKED for this and uses a
> > hash_set instead.  But, as I believe lambdas with 0 (or very few) explicit
> > captures are extremely common, I've tried not to slow down those with
> > allocation of a hash_set and deallocating it again, so it uses
> > a linear search if there are up to 8 captures and starts using a hash_set
> > only when getting above that count.
> > 
> > Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
> > 
> > Or do you think allocation of an hash_set and deallocation would be in a
> > noise?
> 
> I think it'd be in the noise.  The high bit is between zero and more than
> zero captures. The next most common after zero would be 1. Besides,
> identifiers are trivial to hash.

What I meant is that even just hash_set<tree> var; implies a xcalloc (13,
sizeof (void*)) or so and destroying it a free of that.
So, if 90% of all lambdas in the headers have zero captures and 5% have 1,
then simplifying the patch by adding that hash_set<tree> var; into the
lambda introducer parsing routine and just always using the hash set would
add those to the parsing of all those 95%+ lambda parsings that don't really
need that.

Here is attached completely untested variant that does that unconditional
xcalloc/free for every lambda introducer parsing.
The previously posted patch was:
 cp/cp-tree.h                           |    3 +
 cp/lambda.c                            |   54 ++++++++++++++++++++++++++++-----
 cp/parser.c                            |   10 ++++--
this variant is:
 cp/cp-tree.h                           |    3 ++-
 cp/lambda.c                            |   14 +++++++-------
 cp/parser.c                            |    7 ++++---

2019-03-20  Jakub Jelinek  <jakub@redhat.com>

	PR c++/89767
	* cp-tree.h (add_capture): Add ids argument.
	* parser.c (cp_parser_lambda_introducer): Add ids variable and pass
	its address to add_capture calls.
	* lambda.c (add_capture): Add ids argument, don't use
	IDENTIFIER_MARKED, instead use ids hash_set for that.
	(register_capture_members): Don't clear IDENTIFIER_MARKED here.
	(add_default_capture): Adjust add_capture caller.

	* g++.dg/cpp1y/lambda-init18.C: New test.
	* g++.dg/cpp1y/lambda-init19.C: New test.
	* g++.dg/cpp1y/pr89767.C: New test.

--- gcc/cp/cp-tree.h.jj	2019-03-19 17:10:03.135143659 +0100
+++ gcc/cp/cp-tree.h	2019-03-20 15:41:53.561214488 +0100
@@ -7150,7 +7150,8 @@ extern tree lambda_return_type			(tree);
 extern tree lambda_proxy_type			(tree);
 extern tree lambda_function			(tree);
 extern void apply_deduced_return_type           (tree, tree);
-extern tree add_capture                         (tree, tree, tree, bool, bool);
+extern tree add_capture                         (tree, tree, tree, bool, bool,
+						 hash_set<tree> *);
 extern tree add_default_capture                 (tree, tree, tree);
 extern void insert_capture_proxy		(tree);
 extern void insert_pending_capture_proxies	(void);
--- gcc/cp/parser.c.jj	2019-03-19 17:10:03.074144632 +0100
+++ gcc/cp/parser.c	2019-03-20 15:42:44.165434239 +0100
@@ -10547,6 +10547,7 @@ cp_parser_lambda_introducer (cp_parser*
 	error ("non-local lambda expression cannot have a capture-default");
     }
 
+  hash_set<tree> ids;
   while (cp_lexer_next_token_is_not (parser->lexer, CPP_CLOSE_SQUARE))
     {
       cp_token* capture_token;
@@ -10586,7 +10587,7 @@ cp_parser_lambda_introducer (cp_parser*
 		       /*id=*/this_identifier,
 		       /*initializer=*/finish_this_expr (),
 		       /*by_reference_p=*/true,
-		       explicit_init_p);
+		       explicit_init_p, &ids);
 	  continue;
 	}
 
@@ -10604,7 +10605,7 @@ cp_parser_lambda_introducer (cp_parser*
 		       /*id=*/this_identifier,
 		       /*initializer=*/finish_this_expr (),
 		       /*by_reference_p=*/false,
-		       explicit_init_p);
+		       explicit_init_p, &ids);
 	  continue;
 	}
 
@@ -10757,7 +10758,7 @@ cp_parser_lambda_introducer (cp_parser*
 		   capture_id,
 		   capture_init_expr,
 		   /*by_reference_p=*/capture_kind == BY_REFERENCE,
-		   explicit_init_p);
+		   explicit_init_p, &ids);
 
       /* If there is any qualification still in effect, clear it
 	 now; we will be starting fresh with the next capture.  */
--- gcc/cp/lambda.c.jj	2019-03-19 17:10:03.181142924 +0100
+++ gcc/cp/lambda.c	2019-03-20 15:43:50.901409146 +0100
@@ -500,11 +500,12 @@ vla_capture_type (tree array_type)
 /* From an ID and INITIALIZER, create a capture (by reference if
    BY_REFERENCE_P is true), add it to the capture-list for LAMBDA,
    and return it.  If ID is `this', BY_REFERENCE_P says whether
-   `*this' is captured by reference.  */
+   `*this' is captured by reference.  IDS is used during introducer
+   parsing to detect duplicate captures if there are many captures.  */
 
 tree
 add_capture (tree lambda, tree id, tree orig_init, bool by_reference_p,
-	     bool explicit_init_p)
+	     bool explicit_init_p, hash_set<tree> *ids)
 {
   char *buf;
   tree type, member, name;
@@ -605,13 +606,14 @@ add_capture (tree lambda, tree id, tree
      for duplicates.  */
   if (!LAMBDA_EXPR_CLOSURE (lambda))
     {
-      if (IDENTIFIER_MARKED (name))
+      gcc_assert (ids);
+      if (ids->contains (name))
 	{
 	  pedwarn (input_location, 0,
 		   "already captured %qD in lambda expression", id);
 	  return NULL_TREE;
 	}
-      IDENTIFIER_MARKED (name) = true;
+      ids->add (name);
     }
 
   if (variadic)
@@ -674,8 +676,6 @@ register_capture_members (tree captures)
   if (PACK_EXPANSION_P (field))
     field = PACK_EXPANSION_PATTERN (field);
 
-  /* We set this in add_capture to avoid duplicates.  */
-  IDENTIFIER_MARKED (DECL_NAME (field)) = false;
   finish_member_declaration (field);
 }
 
@@ -706,7 +706,7 @@ add_default_capture (tree lambda_stack,
 			    (this_capture_p
 			     || (LAMBDA_EXPR_DEFAULT_CAPTURE_MODE (lambda)
 				 == CPLD_REFERENCE)),
-			    /*explicit_init_p=*/false);
+			    /*explicit_init_p=*/false, NULL);
       initializer = convert_from_reference (var);
 
       /* Warn about deprecated implicit capture of this via [=].  */
--- gcc/testsuite/g++.dg/cpp1y/lambda-init18.C.jj	2019-03-19 16:42:04.191881745 +0100
+++ gcc/testsuite/g++.dg/cpp1y/lambda-init18.C	2019-03-19 16:40:46.133128103 +0100
@@ -0,0 +1,12 @@
+// PR c++/89767
+// { dg-do compile { target c++14 } }
+
+void bar (int);
+
+void
+foo ()
+{
+  int x = 0;
+  auto z = [x, y = [x] { bar (x); }] { y (); bar (x); };
+  z ();
+}
--- gcc/testsuite/g++.dg/cpp1y/lambda-init19.C.jj	2019-03-19 16:45:11.348904338 +0100
+++ gcc/testsuite/g++.dg/cpp1y/lambda-init19.C	2019-03-19 16:46:40.365488200 +0100
@@ -0,0 +1,15 @@
+// PR c++/89767
+// { dg-do compile { target c++14 } }
+
+void bar (int);
+
+void
+foo ()
+{
+  int x = 0;
+  int a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0;
+  auto z = [x, y = [x] { bar (x); }, x] { y (); bar (x); };	// { dg-error "already captured 'x' in lambda expression" }
+  auto w = [x, a, b, c, d, y = [x] { bar (x); }, e, f, g, h, x] { y (); bar (x + a + b + c + d + e + f + g + h); };	// { dg-error "already captured 'x' in lambda expression" }
+  z ();
+  w ();
+}
--- gcc/testsuite/g++.dg/cpp1y/pr89767.C.jj	2019-03-19 16:42:22.734586765 +0100
+++ gcc/testsuite/g++.dg/cpp1y/pr89767.C	2019-03-19 16:39:24.641433848 +0100
@@ -0,0 +1,32 @@
+// PR c++/89767
+// { dg-do compile { target c++14 } }
+// { dg-options "-O2 -Wall" }
+
+template <typename d> struct e { using g = d; };
+template <typename d, template <typename> class> using h = e<d>;
+template <typename d, template <typename> class i>
+using j = typename h<d, i>::g;
+template <typename c> int k(c);
+template <typename...> class au;
+struct l { template <typename c> using m = typename c::f; };
+struct s : l { using af = j<au<int, int> *, m>; };
+template <unsigned long, typename> struct o;
+template <long p, typename c> using q = typename o<p, c>::g;
+template <typename> struct r;
+template <typename c> struct r<c *> { typedef c aj; };
+template <typename ak, typename> struct al { typename r<ak>::aj operator*(); void operator++(); };
+template <typename am, typename an, typename ao>
+bool operator!=(al<am, ao>, al<an, ao>);
+template <unsigned long, typename...> struct ap;
+template <unsigned long aq, typename ar, typename... as>
+struct ap<aq, ar, as...> : ap<1, as...> {};
+template <unsigned long aq, typename ar> struct ap<aq, ar> {};
+template <typename... at> class au : public ap<0, at...> {};
+template <unsigned long p, typename ar, typename... as>
+struct o<p, au<ar, as...>> : o<p - 1, au<as...>> {};
+template <typename ar, typename... as> struct o<0, au<ar, as...>> { typedef ar g; };
+template <long p, typename ar> constexpr ar av(ap<p, ar> __t) { return ar (); }
+template <int p, typename... at> constexpr q<p, au<at...>> aw(au<at...> __t) { av<p>(__t); return q<p, au<at...>> (); }
+struct bg { typedef s::af af; };
+struct F { typedef al<bg::af, int> bk; bk begin(); bk end(); };
+void bo() { int t = 0; F cv; for (auto bp : cv) [t, n = k(aw<1>(bp))] {}; }


	Jakub

On 3/20/19 10:48 AM, Jakub Jelinek wrote:
> On Wed, Mar 20, 2019 at 10:34:51AM -0400, Nathan Sidwell wrote:
>> On 3/19/19 2:14 PM, Jakub Jelinek wrote:
>>> add_capture when parsing a lambda introducer uses the IDENTIFIER_MARKED
>>> bit to detect duplicate captures.
>>> I guess in strict C++11 that could have worked, if the introducer could
>>> contain just identifiers, but in C++14 it has 2 problems:
>>
>>> The following patch stops using IDENTIFIER_MARKED for this and uses a
>>> hash_set instead.  But, as I believe lambdas with 0 (or very few) explicit
>>> captures are extremely common, I've tried not to slow down those with
>>> allocation of a hash_set and deallocating it again, so it uses
>>> a linear search if there are up to 8 captures and starts using a hash_set
>>> only when getting above that count.
>>>
>>> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>>>
>>> Or do you think allocation of an hash_set and deallocation would be in a
>>> noise?
>>
>> I think it'd be in the noise.  The high bit is between zero and more than
>> zero captures. The next most common after zero would be 1. Besides,
>> identifiers are trivial to hash.
> 
> What I meant is that even just hash_set<tree> var; implies a xcalloc (13,
> sizeof (void*)) or so and destroying it a free of that.
> So, if 90% of all lambdas in the headers have zero captures and 5% have 1,
> then simplifying the patch by adding that hash_set<tree> var; into the
> lambda introducer parsing routine and just always using the hash set would
> add those to the parsing of all those 95%+ lambda parsings that don't really
> need that.
> 
> Here is attached completely untested variant that does that unconditional
> xcalloc/free for every lambda introducer parsing.

I was unclear.  I was for the lazy creation of the hash.  I just think 
it can be lazily created at either the first or second explicit capture.

nathan