[lambda] Latest experimental polymorphic lambda patches

[lambda] Latest experimental polymorphic lambda patches

[Adam Butcher]

[-- Attachment #1: Type: text/plain, Size: 2868 bytes --]

Attached are my latest experimental polymorphic lambda patches against the latest lambda branch.  Template parameters
implied by auto in the lambda's call parameter list no longer lose qualifiers.  The following examples produce
equivalent functions:

   1.   [] (auto x, auto& y, auto const& z) { return x + y + z; }
   2.   [] <typename X, typename Y, typename Z> (X x, Y& y, Z const& z) { return x + y + z; }
   3.   [] <typename Y> (auto x, Y& y, auto const& z) { return x + y + z; }

Note that using an explicit template parameter is only really useful if you wish to either a) ensure consistency among
a number of call parameters, b) use a non-type template parameter or c) specify a call parameter type constraint (or
other complex parameter type).

I have flattened the latest auto-template-inference changes with the previous one to remove complexity due to
re-arrangement.  In particular it no longer abuses decl.c -- those changes have currently moved into parser.c but it
is pretty clear that they have more in common with pt.c owing to a need to pull in some local static functions from
that file.  I intend to split or move parts (or most) into pt.c on my next attempt (if I get time to make one!)

There are currently many issues:
  - efficiency of template parameter list growing.
  - implicit return type deduction doesn't work from
    inside a template context if the lambda's return
    expression involves a dependent type.  Specifying
    decltype explicitly in these contexts is a
    workaround.
  - dependent inferred return type needs to be
    deferred and decayed.  This may go some way (all
    the way?) to solving the previous point.
  - location of implementation.
  - only a few use-cases have been considered.


Adam


Summary:

Subject: [PATCH] First pass polymorphic lambda support.

This commit adds experimental support for an optional template-parameter-list in angle-brackets at the start of a
lambda-parameter-declaration.
---
Subject: [PATCH] Restored decltype in lambda return type deduction for when expr is dependent.
---
Subject: [PATCH] Second version of typename inference from auto parameters in lambda call operator.

Still quite hacky -- though better than previous.  No longer loses
qualifiers on replaced auto parameters so is functionally closer to
what's really needed.

 - This is just a behavioural proof to find out how things work.
 - Need to shuffle some stuff into pt.c and do away with code dup.
 - Not sure how to free tree_vec's and tidy up the counts and sizes
   (looks like they're only intended to grow.)
 - Added `type_decays_to (non_reference (finish_decltype_type' as
   suggested by Jason.  Currently doesn't remove cv-quals from
   non-class types though.  Need to treat implicit return type
   differently for dependent types -- should defer and mark that it
   needs to be computed later.
---

[-- Attachment #2: 0001-First-pass-polymorphic-lambda-support.patch --]
[-- Type: application/octet-stream, Size: 3943 bytes --]

From f5c7881b713058d8dfdbf36081e5fb976c67d372 Mon Sep 17 00:00:00 2001
From: Adam Butcher <ajb@ccrvm001a.(none)>
Date: Tue, 4 Aug 2009 13:42:25 +0100
Subject: [PATCH] First pass polymorphic lambda support.

This commit adds experimental support for an optional template-parameter-list in angle-brackets at the start of a lambda-parameter-declaration.
---
 gcc/cp/parser.c    |   48 +++++++++++++++++++++++++++++++++++++++++++++++-
 gcc/cp/semantics.c |    3 +++
 2 files changed, 50 insertions(+), 1 deletions(-)

diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index ec1dfec..36762ef 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -7160,9 +7160,13 @@ cp_parser_lambda_introducer (cp_parser* parser,
 /* Parse the (optional) middle of a lambda expression.
 
    lambda-parameter-declaration:
+       lambda-template-param-decl [opt]
      ( lambda-parameter-declaration-list [opt] ) exception-specification [opt]
        lambda-return-type-clause [opt]
 
+   lambda-template-param-decl:
+     < template-parameter-list >
+
    LAMBDA_EXPR is the current representation of the lambda expression.  */
 
 static void
@@ -7171,8 +7175,30 @@ cp_parser_lambda_parameter_declaration_opt (cp_parser* parser,
 {
   tree param_list = NULL_TREE;
   tree exception_spec = NULL_TREE;
+  tree template_param_list = NULL_TREE;
 
-  if (cp_lexer_next_token_is (parser->lexer, CPP_OPEN_PAREN))
+  if (cp_lexer_next_token_is (parser->lexer, CPP_LESS))
+    {
+      VEC (deferred_access_check,gc) *checks;
+    
+      cp_parser_require (parser, CPP_LESS, "%<<%>");
+
+      push_deferring_access_checks (dk_deferred);
+
+      template_param_list = cp_parser_template_parameter_list (parser);
+      
+      /* TODO: Actually use this at the pop site.  */
+      checks = get_deferred_access_checks ();
+
+      cp_parser_skip_to_end_of_template_parameter_list (parser);
+
+      /* We just processed one more parameter list.  */
+      ++parser->num_template_parameter_lists;
+
+      push_deferring_access_checks (dk_no_check);
+    }
+
+  if (cp_lexer_next_token_is (parser->lexer, CPP_OPEN_PAREN) || template_param_list != NULL_TREE)
     {
       cp_parser_require (parser, CPP_OPEN_PAREN, "%<(%>");
 
@@ -7277,6 +7303,23 @@ cp_parser_lambda_parameter_declaration_opt (cp_parser* parser,
     DECL_INITIALIZED_IN_CLASS_P (fco) = 1;
     finish_method (fco);
 
+    if (template_param_list != NULL_TREE)
+      {
+        tree saved_current_function_decl = current_function_decl;
+        pop_deferring_access_checks ();
+
+        /* Clear current function decl to allow check_member_template
+           to pass.  Currently it rejects templates inside functions.
+           Couldn't figure out a clean way to test for lambda inside
+           check_member_template.  */
+        current_function_decl = NULL_TREE;
+        fco = finish_member_template_decl (fco);
+        current_function_decl = saved_current_function_decl;
+
+        --parser->num_template_parameter_lists;
+        pop_deferring_access_checks ();
+        finish_template_decl (template_param_list);
+      }
     finish_member_declaration (fco);
 
     LAMBDA_EXPR_FUNCTION (lambda_expr) = fco;
@@ -7315,6 +7358,9 @@ cp_parser_lambda_body (cp_parser* parser,
     tree fco = LAMBDA_EXPR_FUNCTION (lambda_expr);
     tree body;
 
+    if (DECL_FUNCTION_TEMPLATE_P (fco))
+      fco = DECL_TEMPLATE_RESULT (fco);
+
     /* Let the front end know that we are going to be defining this
        function.  */
     start_preparsed_function (fco,
diff --git a/gcc/cp/semantics.c b/gcc/cp/semantics.c
index e6f79c1..8318c46 100644
--- a/gcc/cp/semantics.c
+++ b/gcc/cp/semantics.c
@@ -5272,6 +5272,9 @@ deduce_lambda_return_type (tree lambda, tree expr)
   tree return_type;
   tree result;
 
+  if( TREE_CODE (fco) == TEMPLATE_DECL )
+    fco = DECL_TEMPLATE_RESULT (fco);
+
   return_type = type_decays_to (unlowered_expr_type (expr));
 
   /* Set the DECL_RESULT.
-- 
1.5.6.GIT


[-- Attachment #3: 0002-Restored-decltype-in-lambda-return-type-deduction-fo.patch --]
[-- Type: application/octet-stream, Size: 1060 bytes --]

From d6e34759c83abb6165c6ea4bfda902e39a825983 Mon Sep 17 00:00:00 2001
From: Adam Butcher <ajb@ccrvm001a.(none)>
Date: Fri, 7 Aug 2009 14:52:16 +0100
Subject: [PATCH] Restored decltype in lambda return type deduction for when expr is dependent.

---
 gcc/cp/semantics.c |    8 ++++++--
 1 files changed, 6 insertions(+), 2 deletions(-)

diff --git a/gcc/cp/semantics.c b/gcc/cp/semantics.c
index 8318c46..5f1aab0 100644
--- a/gcc/cp/semantics.c
+++ b/gcc/cp/semantics.c
@@ -5272,10 +5272,14 @@ deduce_lambda_return_type (tree lambda, tree expr)
   tree return_type;
   tree result;
 
-  if( TREE_CODE (fco) == TEMPLATE_DECL )
+  if (TREE_CODE (fco) == TEMPLATE_DECL)
     fco = DECL_TEMPLATE_RESULT (fco);
 
-  return_type = type_decays_to (unlowered_expr_type (expr));
+  if (type_dependent_expression_p (expr))
+    return_type = finish_decltype_type
+		   (expr, /*id_expression_or_member_access_p=*/false);
+  else
+    return_type = type_decays_to (unlowered_expr_type (expr));
 
   /* Set the DECL_RESULT.
      - start_preparsed_function
-- 
1.5.6.GIT


[-- Attachment #4: 0003-Second-version-of-typename-inference-from-auto-param.patch --]
[-- Type: application/octet-stream, Size: 12950 bytes --]

From 8d8f7c4b504df982a81d4ed95961a256d22f8367 Mon Sep 17 00:00:00 2001
From: Adam Butcher <ajb@localhost.(none)>
Date: Mon, 10 Aug 2009 23:45:06 +0100
Subject: [PATCH] Second version of typename inference from auto parameters in lambda call operator.

Still quite hacky -- though better than previous.  No longer loses
qualifiers on replaced auto parameters so is functionally closer to
what's really needed.

 - This is just a behavioural proof to find out how things work.
 - Need to shuffle some stuff into pt.c and do away with code dup.
 - Not sure how to free tree_vec's and tidy up the counts and sizes
   (looks like they're only intended to grow.)
 - Added `type_decays_to (non_reference (finish_decltype_type' as
   suggested by Jason.  Currently doesn't remove cv-quals from
   non-class types though.  Need to treat implicit return type
   differently for dependent types -- should defer and mark that it
   needs to be computed later.
---
 gcc/cp/parser.c    |  225 +++++++++++++++++++++++++++++++++++++++++++++++++---
 gcc/cp/pt.c        |    8 ++
 gcc/cp/semantics.c |    6 +-
 3 files changed, 226 insertions(+), 13 deletions(-)

diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index 36762ef..1461309 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -7032,7 +7032,7 @@ cp_parser_lambda_introducer (cp_parser* parser,
   /* Eat the leading `['.  */
   cp_parser_require (parser, CPP_OPEN_SQUARE, "%<[%>");
 
-  /* Record default capture mode.  "[&" "[=" "[&," "[=,"  */
+  /* Record default capture mode.  `[&' `[=' `[&,' `[=,'  */
   if (cp_lexer_next_token_is (parser->lexer, CPP_AND)
       && cp_lexer_peek_nth_token (parser->lexer, 2)->type != CPP_NAME)
     LAMBDA_EXPR_DEFAULT_CAPTURE_MODE (lambda_expr) = CPLD_REFERENCE;
@@ -7157,6 +7157,189 @@ cp_parser_lambda_introducer (cp_parser* parser,
 
 }
 
+
+/* The struct auto_parm_handler_t defines an interface for customizing
+   the behaviour when a C++0x `auto' type is found as the primary type
+   specifier of a function parameter declaration.
+   If auto_parm_handler is set whilst parsing a function parameter
+   list, the function auto_parm_handler->hook will be called for each
+   parameter having `auto' as its primary type; in each case the
+   result of the hook will be used to replace `auto' as the primary
+   type.  */
+typedef struct auto_parm_handler_t auto_parm_handler_t;
+typedef tree (*auto_parm_hook_t) (auto_parm_handler_t*);
+struct auto_parm_handler_t
+{
+   auto_parm_hook_t hook;
+};
+/* Set to a structure that provides the above interface to be called
+   if a type containing `auto' is found during
+   cp_parser_parameter_declaration_list.  */
+auto_parm_handler_t* auto_parm_handler = 0;
+
+/* Handler state for processing `auto' found in lambda function call
+   parameter list.  Supports implicit polymorphic lambdas.  */
+typedef struct lambda_auto_handler_t
+{
+   auto_parm_hook_t hook;
+   tree* template_param_list;
+   VEC (deferred_access_check,gc)* checks;
+   cp_parser* parser;
+   int i;
+}
+lambda_auto_handler_t;
+
+/* FIXME: Much of this would appear to fit better in pt.c.  */
+
+/* FIXME: It would also mean the copied function
+          build_template_parm_index and rudely extern'd
+          x_canonical_type_parameter would be unnecessary.  */
+
+tree lambda_parameter_make_auto_type_name
+  (lambda_auto_handler_t*);
+tree lambda_auto_handler
+  (lambda_auto_handler_t*);
+
+tree
+lambda_parameter_make_auto_type_name (lambda_auto_handler_t* handler)
+{
+  char buf[32];
+  sprintf (buf, "__AutoT%d", ++handler->i);
+  return get_identifier (buf);
+}
+
+/* Return a new TEMPLATE_PARM_INDEX with the indicated INDEX, LEVEL,
+   ORIG_LEVEL, DECL, and TYPE.  
+   FIXME: Remove this copy from here; i.e. probably move rest into
+          pt.c.  */
+
+static tree
+build_template_parm_index (int index,
+			   int level,
+			   int orig_level,
+			   tree decl,
+			   tree type)
+{
+  tree t = make_node (TEMPLATE_PARM_INDEX);
+  TEMPLATE_PARM_IDX (t) = index;
+  TEMPLATE_PARM_LEVEL (t) = level;
+  TEMPLATE_PARM_ORIG_LEVEL (t) = orig_level;
+  TEMPLATE_PARM_DECL (t) = decl;
+  TREE_TYPE (t) = type;
+  TREE_CONSTANT (t) = TREE_CONSTANT (decl);
+  TREE_READONLY (t) = TREE_READONLY (decl);
+
+  return t;
+}
+
+tree
+lambda_auto_handler (lambda_auto_handler_t* handler)
+{
+  struct cp_binding_level* scope = current_binding_level;
+  location_t param_loc = cp_lexer_peek_token (handler->parser->lexer)->location; /* XXX: Any way to get current location? */
+
+  /* First auto parameter may need to start a template parameter list.  */
+  bool become_template = *handler->template_param_list == NULL_TREE;
+
+  tree synth_id = lambda_parameter_make_auto_type_name (handler);
+  tree synth_tmpl_parm = finish_template_type_parm (class_type_node, synth_id);
+  synth_tmpl_parm = build_tree_list (NULL_TREE, synth_tmpl_parm);
+
+  if (become_template)
+    {
+      /* do something rude and pretend that the template parameter
+	 scope surrounds the function definition.  XXX: can we
+	 guarantee that the immediate-outer scope /is/ the fco? */
+      current_binding_level = current_binding_level->level_chain;
+
+      /*if (ENABLE_SCOPE_CHECKING)
+	--binding_depth;*/
+
+      push_deferring_access_checks (dk_deferred);
+      begin_template_parm_list ();
+    }
+
+  synth_tmpl_parm = process_template_parm (0,
+				       param_loc,
+				       synth_tmpl_parm,
+				       /*non_type=*/false,
+				       /*param_pack=*/false);
+
+  /* Re-index based on last existing parameter.  */
+  if (!become_template)
+    {
+      tree old = *handler->template_param_list;
+      size_t len = TREE_VEC_LENGTH (old);
+      size_t idx;
+      extern tree x_canonical_type_parameter (tree);
+
+      tree p = TREE_VALUE (TREE_VEC_ELT (old, --len));
+      if (TREE_CODE (p) == TYPE_DECL || TREE_CODE (p) == TEMPLATE_DECL)
+	idx = TEMPLATE_TYPE_IDX (TREE_TYPE (p));
+      else
+	idx = TEMPLATE_PARM_IDX (DECL_INITIAL (p));
+
+      ++idx;
+
+      TEMPLATE_TYPE_PARM_INDEX (TREE_TYPE (synth_id))
+	= build_template_parm_index (idx, processing_template_decl,
+				     processing_template_decl,
+				     TYPE_NAME (TREE_TYPE (synth_id)),
+				     TREE_TYPE (synth_id));
+      TYPE_CANONICAL (TREE_TYPE (synth_id)) = x_canonical_type_parameter (TREE_TYPE (synth_id));
+    }
+
+  if (become_template)
+    {
+      /* Initial template parameter, create new list.  */
+      *handler->template_param_list = end_template_parm_list (synth_tmpl_parm);
+      ++handler->parser->num_template_parameter_lists;
+      push_deferring_access_checks (dk_no_check);
+      push_binding_level (scope);
+    }
+  else /* Add to existing template parameter list.  */
+    {
+      tree old = *handler->template_param_list;
+      tree new_vec;
+      size_t len;
+
+      gcc_assert (TREE_CODE (old) == TREE_VEC);
+
+      len = TREE_VEC_LENGTH (old);
+
+      /* XXX: Maybe do doubling and store real length in handler
+	 state, there doesn't seem to be any way to free these; or
+	 rather no way to free them that tidies up the
+	 tree_node_counts and sizes.  Ideally just want a
+	 realloc_tree_vec or some such thing that would do realloc and
+	 housekeeping.  Maybe there's some reason why this
+         would be a bad thing. (?)  In fact it would be better
+         to keep building a tree list and only flatten into
+         a vector after parsing the parameter list. */
+      new_vec = make_tree_vec (len+1);
+      {
+	size_t n;
+	for (n = 0; n != len; ++n)
+	  TREE_VEC_ELT (new_vec, n) = TREE_VEC_ELT (old, n);
+      }
+      TREE_VEC_ELT (new_vec, len) = synth_tmpl_parm;
+     /* memcpy (new_vec, old, sizeof (struct tree_vec) + sizeof (tree) * (len-1));
+      TREE_VEC_LENGTH (new_vec) = ++len;
+      */
+
+      /* XXX: free old one - how?  maybe ggc_free? but how to tidy up
+       * the node counts and sizes? */
+      ggc_free (old);
+
+      *handler->template_param_list = new_vec;
+
+      TREE_VALUE (current_template_parms) = new_vec;
+    }
+
+  /* Return synthesized type as a substitute for `auto'. */
+  return TREE_TYPE (synth_id);
+}
+
 /* Parse the (optional) middle of a lambda expression.
 
    lambda-parameter-declaration:
@@ -7176,11 +7359,10 @@ cp_parser_lambda_parameter_declaration_opt (cp_parser* parser,
   tree param_list = NULL_TREE;
   tree exception_spec = NULL_TREE;
   tree template_param_list = NULL_TREE;
+  VEC (deferred_access_check,gc) *checks = 0;
 
   if (cp_lexer_next_token_is (parser->lexer, CPP_LESS))
     {
-      VEC (deferred_access_check,gc) *checks;
-    
       cp_parser_require (parser, CPP_LESS, "%<<%>");
 
       push_deferring_access_checks (dk_deferred);
@@ -7208,10 +7390,23 @@ cp_parser_lambda_parameter_declaration_opt (cp_parser* parser,
       if (cp_lexer_next_token_is_not (parser->lexer, CPP_CLOSE_PAREN))
         {
           bool is_error = false;
+
+	  /* Set up handler for auto being used in function parameter list.  */
+	  lambda_auto_handler_t auto_handler;
+	  auto_handler.hook = (auto_parm_hook_t) lambda_auto_handler;
+	  auto_handler.template_param_list = &template_param_list;
+	  auto_handler.checks = 0;
+	  auto_handler.parser = parser;
+	  auto_handler.i = 0;
+	  auto_parm_handler = (auto_parm_handler_t*) &auto_handler;
+
           param_list = cp_parser_parameter_declaration_list (parser, &is_error);
           /* TODO: better way to handle this error?  */
           if (is_error)
             param_list = NULL_TREE;
+
+	  /* TODO: copy auto_handler.checks out */
+	  auto_parm_handler = 0;
         }
 
       cp_parser_require (parser, CPP_CLOSE_PAREN, "%<)%>");
@@ -7307,6 +7502,7 @@ cp_parser_lambda_parameter_declaration_opt (cp_parser* parser,
       {
         tree saved_current_function_decl = current_function_decl;
         pop_deferring_access_checks ();
+	/* TODO: do checks */
 
         /* Clear current function decl to allow check_member_template
            to pass.  Currently it rejects templates inside functions.
@@ -7316,16 +7512,14 @@ cp_parser_lambda_parameter_declaration_opt (cp_parser* parser,
         fco = finish_member_template_decl (fco);
         current_function_decl = saved_current_function_decl;
 
-        --parser->num_template_parameter_lists;
+	--parser->num_template_parameter_lists;
         pop_deferring_access_checks ();
         finish_template_decl (template_param_list);
       }
     finish_member_declaration (fco);
 
     LAMBDA_EXPR_FUNCTION (lambda_expr) = fco;
-
   }
-
 }
 
 /* Parse the body of a lambda expression, which is simply
@@ -14656,11 +14850,20 @@ cp_parser_parameter_declaration_list (cp_parser* parser, bool *is_error)
       deprecated_state = DEPRECATED_SUPPRESS;
 
       if (parameter)
-	decl = grokdeclarator (parameter->declarator,
-			       &parameter->decl_specifiers,
-			       PARM,
-			       parameter->default_argument != NULL_TREE,
-			       &parameter->decl_specifiers.attributes);
+	{
+	  /* If there is a custom `auto' handler and the primary type
+	     of this parameter is `auto', then invoke the hook and
+	     replace `auto' with the result. */
+	  if (auto_parm_handler && is_auto (parameter->decl_specifiers.type))
+	    {
+	      parameter->decl_specifiers.type = auto_parm_handler->hook (auto_parm_handler);
+	    }
+	  decl = grokdeclarator (parameter->declarator,
+				 &parameter->decl_specifiers,
+				 PARM,
+				 parameter->default_argument != NULL_TREE,
+				 &parameter->decl_specifiers.attributes);
+	}
 
       deprecated_state = DEPRECATED_NORMAL;
 
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index ed45324..2d8380c 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -3150,6 +3150,13 @@ canonical_type_parameter (tree type)
     }
 }
 
+/* FIXME: Cleanup this mess */
+tree x_canonical_type_parameter (tree type);
+tree x_canonical_type_parameter (tree type)
+{
+  return canonical_type_parameter (type);
+}
+
 /* Return a TEMPLATE_PARM_INDEX, similar to INDEX, but whose
    TEMPLATE_PARM_LEVEL has been decreased by LEVELS.  If such a
    TEMPLATE_PARM_INDEX already exists, it is returned; otherwise, a
@@ -17480,6 +17487,7 @@ is_auto (const_tree type)
 tree
 type_uses_auto (tree type)
 {
+  /* XXX: Maybe to loop rather than recurse here? */
   enum tree_code code;
   if (is_auto (type))
     return type;
diff --git a/gcc/cp/semantics.c b/gcc/cp/semantics.c
index 5f1aab0..482887c 100644
--- a/gcc/cp/semantics.c
+++ b/gcc/cp/semantics.c
@@ -5276,8 +5276,10 @@ deduce_lambda_return_type (tree lambda, tree expr)
     fco = DECL_TEMPLATE_RESULT (fco);
 
   if (type_dependent_expression_p (expr))
-    return_type = finish_decltype_type
-		   (expr, /*id_expression_or_member_access_p=*/false);
+    /* TODO: Should defer this until instantiation rather than using
+             decltype.  */
+    return_type = type_decays_to (non_reference (finish_decltype_type
+		   (expr, /*id_expression_or_member_access_p=*/false)));
   else
     return_type = type_decays_to (unlowered_expr_type (expr));
 
-- 
1.5.6.GIT

Re: [lambda] Latest experimental polymorphic lambda patches

[Jason Merrill]

A few comments:

> /* XXX: Any way to get current location? */

input_location

> The following examples produce
> equivalent functions:
>
>    1.   [] (auto x, auto& y, auto const& z) { return x + y + z; }
>    2.   [] <typename X, typename Y, typename Z> (X x, Y& y, Z const& z) { return x + y + z; }
>    3.   [] <typename Y> (auto x, Y& y, auto const& z) { return x + y + z; }

IMO #3 should not be equivalent to the others; the auto template parms 
should come after Y.  And I believe that's currently the case with your 
patch.

> In fact it would be better
> +         to keep building a tree list and only flatten into
> +         a vector after parsing the parameter list. */

If you save up all the auto parms until the end and then assign indices 
and adjust the parm vector then, that will avoid reallocating the vector 
each time.

But don't worry about tidying tree_node_counts; it just tracks how many 
of a particular tree code we create, not how many we currently have. 
Normal GC throws away lots of stuff without adjusting the counts.

> +  /* XXX: Maybe to loop rather than recurse here? */

At -O2, the GCC optimizers should convert tail recursion into looping.

> +  if (type_dependent_expression_p (expr))
> +    /* TODO: Should defer this until instantiation rather than using
> +             decltype.  */
> +    return_type = type_decays_to (non_reference (finish_decltype_type
> +                  (expr, /*id_expression_or_member_access_p=*/false)));

Definitely need to defer it; type_decays_to and non_reference don't work 
on DECLTYPE_TYPE.

Jason

Re: [lambda] Latest experimental polymorphic lambda patches

[Adam Butcher]

Thanks for the feedback.

Jason Merrill wrote:
>Adam Butcher wrote:
>> The following examples produce
>> equivalent functions:
>>
>>    1.   [] (auto x, auto& y, auto const& z) { return x + y + z; }
>>    2.   [] <typename X, typename Y, typename Z> (X x, Y& y, Z const& z) { return x + y + z; }
>>    3.   [] <typename Y> (auto x, Y& y, auto const& z) { return x + y + z; }
>
> IMO #3 should not be equivalent to the others; the auto template parms
> should come after Y.  And I believe that's currently the case with your
> patch.
>
Sorry, I wasn't clear.  I meant that they generate the same function from the user's point of view, not that their
internals are the same.  I didn't mean to suggest that the order of their template parameters would be the same.  It
was meant to demonstrate that using 'auto' and specifying an explicit unique typename are equivalent from a client
point-of-view.  You are correct that in #3's case the generated lambda is equivalent to:

   [] <typename Y, typename __AutoT1, typename __AutoT2> (__AutoT1 x, Y& y, __AutoT2 const& z) { return x + y + z; }

Which is, from the user's perspective, equivalent to the lambda functions defined by #1 and #2, just that the order of
the template arguments are different.

I accept that this does give a different function signature in terms of template parameter indexes.  I've assumed that
explicit specialization of the call operator is not useful and therefore the user would never see the final template
parameter list and would not need to understand its ordering.

> If you save up all the auto parms until the end and then assign indices
> and adjust the parm vector then, that will avoid reallocating the vector
> each time.
>
Yes that would be better.

> But don't worry about tidying tree_node_counts; it just tracks how many
> of a particular tree code we create, not how many we currently have.
> Normal GC throws away lots of stuff without adjusting the counts.
>
Ah okay.  Would it be worth enhancing the tree-vec interface to include block reallocation with size doubling and end
marking to allow for more efficient reallocation?  Such a structural change maybe hidden by the macro front-end.  I
wonder how many uses of make_tree_vec don't ggcfree their previous tree-vec when using it in a 'realloc' way.

A quick grep for 'make_tree_vec\>' in gcc reveals about 80 uses, many of which with an arithmetic expression as its
argument.  I wonder how many of these might benefit from such an allocation scheme and how many would be impaired by
it?

Maybe its an insignificant issue.

>> +  /* XXX: Maybe to loop rather than recurse here? */
>
> At -O2, the GCC optimizers should convert tail recursion into looping.
>
Great, no worries there then.

>> +  if (type_dependent_expression_p (expr))
>> +    /* TODO: Should defer this until instantiation rather than using
>> +             decltype.  */
>> +    return_type = type_decays_to (non_reference (finish_decltype_type
>> +                  (expr, /*id_expression_or_member_access_p=*/false)));
>
> Definitely need to defer it; type_decays_to and non_reference don't work
> on DECLTYPE_TYPE.
>
I thought as much -- I assume it's just trying to strip non-existent qualifiers from `decltype(expr)' which amounts to
a no-op.

Thanks again for the feedback.  I'll try to get deferred return type deduction working when I get some time.  Working
through that will probably end up sorting some of the issues with dependent return type deduction inside templates.

Cheers,
Adam

Re: [lambda] Latest experimental polymorphic lambda patches

[Jason Merrill]

On 08/11/2009 11:20 AM, Adam Butcher wrote:
> Ah okay.  Would it be worth enhancing the tree-vec interface to include block reallocation with size doubling and end
> marking to allow for more efficient reallocation?

I don't think so; I expect that would end up being less space-efficient, 
since in most cases we know in advance exactly how much space we need.

Feel free to add a realloc_tree_vec function to gcc/tree.c, though.

> Such a structural change maybe hidden by the macro front-end.  I
> wonder how many uses of make_tree_vec don't ggc_free their previous tree-vec when using it in a 'realloc' way.

That just means they'll live until the next GC pass, not a big deal.

Jason

Re: [lambda] Latest experimental polymorphic lambda patches

[Ian Lance Taylor]

On Tue, Aug 11, 2009 at 7:05 AM, Jason Merrill <jason@redhat.com> wrote:
> A few comments:
>
>> /* XXX: Any way to get current location? */
>
> input_location

Just a late comment: using input_location is generally not a good
idea.  Every token in the parser has a location.  That should be the
source of all location information.  Using input_location generally
gives you the wrong column and sometimes even gives you the wrong
line.  We should eventually eliminate it.

Ian

Re: [lambda] Latest experimental polymorphic lambda patches

[Jason Merrill]

On 08/10/2009 08:33 PM, Adam Butcher wrote:
> Attached are my latest experimental polymorphic lambda patches against the latest lambda branch.

Polymorphic lambdas were voted in for C++14 at the meeting this past 
week; are you interested in resuming this work?

The proposal will be at

   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3649.html

once the post-meeting mailing is released, or I can send you a copy if 
you'd like to see it sooner.

Jason

Re: [lambda] Latest experimental polymorphic lambda patches

[Jason Merrill]

On 04/22/2013 12:42 PM, Jason Merrill wrote:
> The proposal will be at
>
>    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3649.html

It's now been posted at http://isocpp.org/files/papers/N3649.html

Jason

Re: [lambda] Latest experimental polymorphic lambda patches

[Adam Butcher]

Hi Jason,

On 23.04.2013 14:42, Jason Merrill wrote:
> On 22.04.2013 17:42, Jason Merrill wrote:
> > On 08/10/2009 08:33 PM, Adam Butcher wrote:
> > > Attached are my latest experimental polymorphic lambda patches
> > > against the latest lambda branch.
> >
> > Polymorphic lambdas were voted in for C++14 at the meeting this 
> past
> > week; are you interested in resuming this work?
> >
Yes very interested.  I have been meaning to get around to remaking
the patch against 4.8 (and previously 4.7) for ages now.  Though
getting the time to do so has been, and will likely continue to be, a
problem what with work, fatherhood and other commitments.

Since the gcc/cp code base is significantly different now from the old
lambda branch where the changes were originally made in 2009, my
intent was to remake the changes from scratch implementing the
entirety of N3559 (now N3649) and, at least, the explicit template
parameter specifier syntax from N3560 (though I'm very interested
getting the single expression body syntax working also).

I have no problem with someone else getting on with this as I can't
guarantee consistent availability for it but I will try to get some
time to at least look at my previous aborted efforts to get the
changes applied to the more recent mainlines (I have some git repos
around here and at work with some incomplete changes).  I will see how
far I got with these and maybe post a few patches.  It is highly
likely though that these were just abortive attempts to merge the
previous stuff or incomplete restarts.

> > The proposal will be at
> >
> >  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3649.html
> >
> It's now been posted at http://isocpp.org/files/papers/N3649.html
>

Cheers,
Adam

[PATCH] Remake initial changes from old lambda branch to support explicit lambda template support and fixup against mainline gcc/cp changes.

[Adam Butcher]

This only supports the explicit template parameter syntax and does not
correctly support conversion to static ptr-to-function for generic
stateless lambdas.
---
 gcc/cp/mangle.c    |  2 ++
 gcc/cp/parser.c    | 43 +++++++++++++++++++++++++++++++++++++++++--
 gcc/cp/semantics.c | 24 ++++++++++++++++++++----
 3 files changed, 63 insertions(+), 6 deletions(-)

diff --git a/gcc/cp/mangle.c b/gcc/cp/mangle.c
index 8da62b5..4d4c0fd 100644
--- a/gcc/cp/mangle.c
+++ b/gcc/cp/mangle.c
@@ -1438,6 +1438,8 @@ write_closure_type_name (const tree type)
   MANGLE_TRACE_TREE ("closure-type-name", type);
 
   write_string ("Ul");
+  if (TREE_CODE (fn) == TEMPLATE_DECL) // XXX: should we bother mangling generic lambdas?
+    fn = DECL_TEMPLATE_RESULT (fn);
   write_method_parms (parms, /*method_p=*/1, fn);
   write_char ('E');
   write_compact_number (LAMBDA_EXPR_DISCRIMINATOR (lambda));
diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index 319da21..407dca3 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -8668,6 +8668,7 @@ cp_parser_lambda_introducer (cp_parser* parser, tree lambda_expr)
 /* Parse the (optional) middle of a lambda expression.
 
    lambda-declarator:
+     < template-parameter-list [opt] >
      ( parameter-declaration-clause [opt] )
        attribute-specifier [opt]
        mutable [opt]
@@ -8687,10 +8688,26 @@ cp_parser_lambda_declarator_opt (cp_parser* parser, tree lambda_expr)
   tree param_list = void_list_node;
   tree attributes = NULL_TREE;
   tree exception_spec = NULL_TREE;
+  tree template_param_list = NULL_TREE;
   tree t;
 
-  /* The lambda-declarator is optional, but must begin with an opening
-     parenthesis if present.  */
+  /* The template-parameter-list is optional, but must begin with
+     an opening angle if present.  */
+  if (cp_lexer_next_token_is (parser->lexer, CPP_LESS))
+    {
+      cp_lexer_consume_token (parser->lexer);
+
+      template_param_list = cp_parser_template_parameter_list (parser);
+
+      cp_parser_skip_to_end_of_template_parameter_list (parser);
+
+      /* We just processed one more parameter list.  */
+      ++parser->num_template_parameter_lists;
+    }
+
+  /* The parameter-declaration-clause is optional (unless
+     template-parameter-list was given), but must begin with an
+     opening parenthesis if present.  */
   if (cp_lexer_next_token_is (parser->lexer, CPP_OPEN_PAREN))
     {
       cp_lexer_consume_token (parser->lexer);
@@ -8736,6 +8753,8 @@ cp_parser_lambda_declarator_opt (cp_parser* parser, tree lambda_expr)
 
       leave_scope ();
     }
+  else if (template_param_list != NULL_TREE) // generate diagnostic
+    cp_parser_require (parser, CPP_OPEN_PAREN, RT_OPEN_PAREN);
 
   /* Create the function call operator.
 
@@ -8779,6 +8798,23 @@ cp_parser_lambda_declarator_opt (cp_parser* parser, tree lambda_expr)
 	DECL_ARTIFICIAL (fco) = 1;
 	/* Give the object parameter a different name.  */
 	DECL_NAME (DECL_ARGUMENTS (fco)) = get_identifier ("__closure");
+	if (template_param_list != NULL_TREE)
+	  {
+	    tree saved_current_function_decl = current_function_decl;
+
+	    /* Clear current function decl to allow check_member_template
+	       to pass.  Currently it rejects templates inside functions.
+	       Couldn't figure out a clean way to test for lambda inside
+	       check_member_template.  */
+	    current_function_decl = NULL_TREE;
+	    fco = finish_member_template_decl (fco);
+	    current_function_decl = saved_current_function_decl;
+
+	    --parser->num_template_parameter_lists;
+
+	    finish_template_decl (template_param_list);
+
+	  }
       }
 
     finish_member_declaration (fco);
@@ -8822,6 +8858,9 @@ cp_parser_lambda_body (cp_parser* parser, tree lambda_expr)
     tree compound_stmt;
     tree cap;
 
+    if (TREE_CODE (fco) == TEMPLATE_DECL)
+      fco = DECL_TEMPLATE_RESULT (fco);
+
     /* Let the front end know that we are going to be defining this
        function.  */
     start_preparsed_function (fco,
diff --git a/gcc/cp/semantics.c b/gcc/cp/semantics.c
index b5c3b0a..db5ba7b 100644
--- a/gcc/cp/semantics.c
+++ b/gcc/cp/semantics.c
@@ -9135,7 +9135,7 @@ lambda_function (tree lambda)
 			  /*protect=*/0, /*want_type=*/false,
 			  tf_warning_or_error);
   if (lambda)
-    lambda = BASELINK_FUNCTIONS (lambda);
+    lambda = OVL_CURRENT (BASELINK_FUNCTIONS (lambda));
   return lambda;
 }
 
@@ -9381,6 +9381,8 @@ build_capture_proxy (tree member)
 
   closure = DECL_CONTEXT (member);
   fn = lambda_function (closure);
+  if (TREE_CODE (fn) == TEMPLATE_DECL)
+    fn = DECL_TEMPLATE_RESULT (fn);
   lam = CLASSTYPE_LAMBDA_EXPR (closure);
 
   /* The proxy variable forwards to the capture field.  */
@@ -9795,7 +9797,8 @@ maybe_add_lambda_conv_op (tree type)
   if (processing_template_decl)
     return;
 
-  if (DECL_INITIAL (callop) == NULL_TREE)
+  if (TREE_CODE (callop) != TEMPLATE_DECL
+      && DECL_INITIAL (callop) == NULL_TREE)
     {
       /* If the op() wasn't instantiated due to errors, give up.  */
       gcc_assert (errorcount || sorrycount);
@@ -9830,6 +9833,10 @@ maybe_add_lambda_conv_op (tree type)
   if (nested)
     DECL_INTERFACE_KNOWN (fn) = 1;
 
+  // FIXME: generalize/respell add_inherited_template_parms
+  if (TREE_CODE (callop) == TEMPLATE_DECL)
+    fn = add_inherited_template_parms (fn, callop);
+
   add_method (type, fn, NULL_TREE);
 
   /* Generic thunk code fails for varargs; we'll complain in mark_used if
@@ -9856,7 +9863,11 @@ maybe_add_lambda_conv_op (tree type)
   DECL_NOT_REALLY_EXTERN (fn) = 1;
   DECL_DECLARED_INLINE_P (fn) = 1;
   DECL_STATIC_FUNCTION_P (fn) = 1;
-  DECL_ARGUMENTS (fn) = copy_list (DECL_CHAIN (DECL_ARGUMENTS (callop)));
+  if (TREE_CODE (callop) == TEMPLATE_DECL)
+    DECL_ARGUMENTS (fn) =
+      copy_list (DECL_CHAIN (DECL_ARGUMENTS (DECL_TEMPLATE_RESULT (callop))));
+  else
+    DECL_ARGUMENTS (fn) = copy_list (DECL_CHAIN (DECL_ARGUMENTS (callop)));
   for (arg = DECL_ARGUMENTS (fn); arg; arg = DECL_CHAIN (arg))
     {
       /* Avoid duplicate -Wshadow warnings.  */
@@ -9866,6 +9877,11 @@ maybe_add_lambda_conv_op (tree type)
   if (nested)
     DECL_INTERFACE_KNOWN (fn) = 1;
 
+  // FIXME: refactor/respell add_inherited_template_parms... it is
+  // FIXME: functionally what we want here
+  if (TREE_CODE (callop) == TEMPLATE_DECL)
+    fn = add_inherited_template_parms (fn, callop);
+
   add_method (type, fn, NULL_TREE);
 
   if (nested)
@@ -9889,7 +9905,7 @@ maybe_add_lambda_conv_op (tree type)
   body = begin_function_body ();
   compound_stmt = begin_compound_stmt (0);
 
-  arg = build1 (NOP_EXPR, TREE_TYPE (DECL_ARGUMENTS (callop)),
+  arg = build1 (NOP_EXPR, TREE_TYPE (DECL_ARGUMENTS (statfn)),
 		null_pointer_node);
   argvec = make_tree_vector ();
   argvec->quick_push (arg);
-- 
1.8.3

Re: [lambda] First stage remake of old lambda patches

[Adam Butcher]

Hi Jason,

I did find some code in the end but it wasn't much use due to the
changes in gcc/cp since the old lambda branch from which the original
patch was based.

I've since been finding 10 minutes here and there to have a hack about
and have finally got the first stage of generic lambda support
functional against GCC's trunk.

It currently only supports the explicit template-style syntax of the
second (non approved) paper (and my original patch) but I believe this
is good place to start even if it is considered a GNU extension for
now.  I will try to reapply the 'auto' syntax patch at some point but
that is syntactic rather than a behavioral.

I want to fix up the stateless lambda ptr-to-fn conversion-op stuff
next which, I think, is currently the biggest wheel off mechanically.

I've no idea how well this will deal with parameter packs or more
exotic use cases than the simple test program below but I'd welcome
any feedback at this stage.

I do feel like I've gone backward with this but I think it's worth
getting the mechanical side working right with the latest GCC before
integrating the 'auto' parameter patch.

Cheers,
Adam

########## begin test program ##############

// to check generated asm
//
volatile int E = 1;
volatile int F = 2;
volatile int G = 3;
volatile int H = 4;

// instantiation generates a -Wwrite-strings warning showing the type
// bindings for T and U (currently not displayed in generic lambda
// diagnostics) as part of the synthesized constructor.
//
template <typename T, typename U>
struct diagnostic { char* x = ""; };

int main()
{
  int i = 1;

  // e: monomorphic stateless lambda
  // f: monomorphic closure
  // g: polymorphic stateless lambda
  //     (Note: explicit return type specified to avoid current
  //            conversion-op bug)
  // h: polymorphic closure
  //
  auto e = []  (char a, char b) { return E + a + b; };
  auto f = [i] (char a, char b) { return F + i + a + b; };
  auto g = []  <typename T, typename U> (T a, U b) -> double { diagnostic<T,U>(); return G + a + b; };
  auto h = [i] <typename T, typename U> (T a, U b) { diagnostic<T,U>(); return H + i + a + b; };

  // SEGV currently: conversion-op not implemented correctly yet:
  //   int (*p) (char, float) = g;
  //   int (*q) (int, double) = g;
  
  return g (1.0, 2) + h (2.f, '\003');
}

########## end test program ##############