[3/3,lambda,basic-terse-templates] Support using `auto' in a function parameter list to introduce an implicit template parameter.

diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index a837d22..08d9d5e 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -1034,6 +1034,7 @@  struct GTY(()) saved_scope {
   int x_processing_template_decl;
   int x_processing_specialization;
   BOOL_BITFIELD x_processing_explicit_instantiation : 1;
+  BOOL_BITFIELD x_fully_implicit_template : 1;
   BOOL_BITFIELD need_pop_function_context : 1;
 
   int unevaluated_operand;
@@ -1088,6 +1089,12 @@  struct GTY(()) saved_scope {
 #define processing_specialization scope_chain->x_processing_specialization
 #define processing_explicit_instantiation scope_chain->x_processing_explicit_instantiation
 
+/* Nonzero if the function being declared was made a template due to it's
+   parameter list containing generic type specifiers (`auto' or concept
+   identifiers) rather than an explicit template parameter list.  */
+
+#define fully_implicit_template scope_chain->x_fully_implicit_template
+
 /* The cached class binding level, from the most recently exited
    class, or NULL if none.  */
 
@@ -5453,12 +5460,16 @@  extern tree make_auto				(void);
 extern tree make_decltype_auto			(void);
 extern tree do_auto_deduction			(tree, tree, tree);
 extern tree type_uses_auto			(tree);
+extern tree type_uses_auto_or_concept		(tree);
 extern void append_type_to_template_for_access_check (tree, tree, tree,
 						      location_t);
 extern tree splice_late_return_type		(tree, tree);
 extern bool is_auto				(const_tree);
+extern bool is_auto_or_concept			(const_tree);
 extern tree process_template_parm		(tree, location_t, tree, 
 						 bool, bool);
+extern tree add_implicit_template_parms		(size_t, tree);
+extern tree finish_fully_implicit_template	(tree);
 extern tree end_template_parm_list		(tree);
 extern void end_template_decl			(void);
 extern tree maybe_update_decl_type		(tree, tree);
diff --git a/gcc/cp/decl.c b/gcc/cp/decl.c
index c97134c..56b49dd 100644
--- a/gcc/cp/decl.c
+++ b/gcc/cp/decl.c
@@ -10329,9 +10329,9 @@  grokdeclarator (const cp_declarator *declarator,
       if (ctype || in_namespace)
 	error ("cannot use %<::%> in parameter declaration");
 
-      if (type_uses_auto (type))
+      if (type_uses_auto (type) && cxx_dialect < cxx1y)
 	{
-	  error ("parameter declared %<auto%>");
+	  error ("parameter declared %<auto%> (unsupported prior to C++1y)");
 	  type = error_mark_node;
 	}
 
diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index 48c95e6..d6c4129 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -8933,6 +8933,11 @@  cp_parser_lambda_declarator_opt (cp_parser* parser, tree lambda_expr)
 	    finish_template_decl (template_param_list);
 	    --parser->num_template_parameter_lists;
 	  }
+	else if (fully_implicit_template)
+	  {
+	    fco = finish_fully_implicit_template (fco);
+	    --parser->num_template_parameter_lists;
+	  }
       }
 
     finish_member_declaration (fco);
@@ -16807,8 +16812,10 @@  cp_parser_direct_declarator (cp_parser* parser,
 	      /* Parse the parameter-declaration-clause.  */
 	      params = cp_parser_parameter_declaration_clause (parser);
 
+	      /* Restore saved template parameter lists accounting for implicit
+		 template parameters.  */
 	      parser->num_template_parameter_lists
-		= saved_num_template_parameter_lists;
+		+= saved_num_template_parameter_lists;
 
 	      /* Consume the `)'.  */
 	      cp_parser_require (parser, CPP_CLOSE_PAREN, RT_CLOSE_PAREN);
@@ -17908,6 +17915,7 @@  cp_parser_parameter_declaration_list (cp_parser* parser, bool *is_error)
   tree *tail = &parameters; 
   bool saved_in_unbraced_linkage_specification_p;
   int index = 0;
+  int implicit_template_parms = 0;
 
   /* Assume all will go well.  */
   *is_error = false;
@@ -17935,11 +17943,17 @@  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 (parameter->decl_specifiers.type && is_auto_or_concept
+	      (parameter->decl_specifiers.type))
+	    ++implicit_template_parms;
+
+	  decl = grokdeclarator (parameter->declarator,
+				 &parameter->decl_specifiers,
+				 PARM,
+				 parameter->default_argument != NULL_TREE,
+				 &parameter->decl_specifiers.attributes);
+	}
 
       deprecated_state = DEPRECATED_NORMAL;
 
@@ -18027,6 +18041,17 @@  cp_parser_parameter_declaration_list (cp_parser* parser, bool *is_error)
   parser->in_unbraced_linkage_specification_p
     = saved_in_unbraced_linkage_specification_p;
 
+  if (parameters != error_mark_node && implicit_template_parms)
+    {
+      parameters = add_implicit_template_parms (implicit_template_parms,
+						parameters);
+
+      // Let the parser know that there's an extra parameter list active if this
+      // function has become a template.
+      if (fully_implicit_template)
+	++parser->num_template_parameter_lists;
+    }
+
   return parameters;
 }
 
@@ -20033,7 +20058,14 @@  cp_parser_member_declaration (cp_parser* parser)
 							      attributes);
 		  /* If the member was not a friend, declare it here.  */
 		  if (!friend_p)
-		    finish_member_declaration (decl);
+		    {
+		      if (fully_implicit_template)
+			{
+			  decl = finish_fully_implicit_template (decl);
+			  --parser->num_template_parameter_lists;
+			}
+		      finish_member_declaration (decl);
+		    }
 		  /* Peek at the next token.  */
 		  token = cp_lexer_peek_token (parser->lexer);
 		  /* If the next token is a semicolon, consume it.  */
@@ -20049,6 +20081,11 @@  cp_parser_member_declaration (cp_parser* parser)
 				  initializer, /*init_const_expr_p=*/true,
 				  asm_specification,
 				  attributes);
+		if (fully_implicit_template)
+		  {
+		    decl = finish_fully_implicit_template (decl);
+		    --parser->num_template_parameter_lists;
+		  }
 	    }
 
 	  /* Reset PREFIX_ATTRIBUTES.  */
@@ -22316,6 +22353,12 @@  cp_parser_function_definition_after_declarator (cp_parser* parser,
     = saved_num_template_parameter_lists;
   parser->in_function_body = saved_in_function_body;
 
+  if (fully_implicit_template)
+    {
+      finish_fully_implicit_template (/*member_decl_opt=*/0);
+      --parser->num_template_parameter_lists;
+    }
+
   return fn;
 }
 
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 3694ccc..549430a 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -21022,31 +21022,65 @@  is_auto (const_tree type)
     return false;
 }
 
-/* Returns true iff TYPE contains a use of 'auto'.  Since auto can only
-   appear as a type-specifier for the declaration in question, we don't
-   have to look through the whole type.  */
+/* Returns the first tree within T that is directly matched by PRED.  T may be a
+   type or PARM_DECL and is incrementally decomposed toward it's type-specifier
+   until a match is found.  NULL_TREE is returned if PRED does not match any
+   part of T.
 
-tree
-type_uses_auto (tree type)
+   This is primarily intended for detecting whether T uses `auto' or a concept
+   identifier.  Since either of these can only appear as a type-specifier for
+   the declaration in question, only top-level qualifications are traversed;
+   find_type_usage does not look through the whole type.  */
+
+static inline tree
+find_type_usage (tree t, bool (*pred) (const_tree))
 {
   enum tree_code code;
-  if (is_auto (type))
-    return type;
+  if (pred (t))
+    return t;
 
-  code = TREE_CODE (type);
+  code = TREE_CODE (t);
 
   if (code == POINTER_TYPE || code == REFERENCE_TYPE
-      || code == OFFSET_TYPE || code == FUNCTION_TYPE
-      || code == METHOD_TYPE || code == ARRAY_TYPE)
-    return type_uses_auto (TREE_TYPE (type));
+      || code == PARM_DECL || code == OFFSET_TYPE
+      || code == FUNCTION_TYPE || code == METHOD_TYPE
+      || code == ARRAY_TYPE)
+    return find_type_usage (TREE_TYPE (t), pred);
 
-  if (TYPE_PTRMEMFUNC_P (type))
-    return type_uses_auto (TREE_TYPE (TREE_TYPE
-				   (TYPE_PTRMEMFUNC_FN_TYPE (type))));
+  if (TYPE_PTRMEMFUNC_P (t))
+    return find_type_usage
+      (TREE_TYPE (TREE_TYPE (TYPE_PTRMEMFUNC_FN_TYPE (t))), pred);
 
   return NULL_TREE;
 }
 
+/* Returns the TEMPLATE_TYPE_PARM in TYPE representing `auto' iff TYPE contains
+   a use of `auto'.  Returns NULL_TREE otherwise.  */
+
+tree type_uses_auto (tree type)
+{
+  return find_type_usage (type, is_auto);
+}
+
+/* Returns true iff TYPE is a TEMPLATE_TYPE_PARM representing 'auto',
+   'decltype(auto)' or a concept.  */
+
+bool
+is_auto_or_concept (const_tree type)
+{
+  return is_auto (type); // or concept
+}
+
+/* Returns the TEMPLATE_TYPE_PARM in TYPE representing a generic type (`auto' or
+   a concept identifier) iff TYPE contains a use of a generic type.  Returns
+   NULL_TREE otherwise.  */
+
+tree type_uses_auto_or_concept (tree type)
+{
+  return find_type_usage (type, is_auto_or_concept);
+}
+
+
 /* For a given template T, return the vector of typedefs referenced
    in T for which access check is needed at T instantiation time.
    T is either  a FUNCTION_DECL or a RECORD_TYPE.
@@ -21197,4 +21231,124 @@  print_template_statistics (void)
 	   htab_collisions (type_specializations));
 }
 
+/* Create an identifier for a generic parameter type (a synthesized
+   template parameter implied by `auto' or a concept identifier). */
+
+static tree
+make_generic_type_name (int i)
+{
+  char buf[32];
+  sprintf (buf, "__GenT%d", i);
+  return get_identifier (buf);
+}
+
+/* Predicate that behaves as is_auto_or_concept but matches the parent
+   node of the generic type rather than the generic type itself.  This
+   allows for type transformation in add_implicit_template_parms.  */
+
+static inline bool
+tree_type_is_auto_or_concept (const_tree t)
+{
+  return TREE_TYPE (t) && is_auto_or_concept (TREE_TYPE (t));
+}
+
+/* Add COUNT implicit template parameters gleaned from the generic
+   type parameters in PARAMETERS to the CURRENT_TEMPLATE_PARMS
+   (creating a new template parameter list if necessary).  Returns
+   PARAMETERS suitably rewritten to reference the newly created types
+   or ERROR_MARK_NODE on failure.  */
+
+tree
+add_implicit_template_parms (size_t count, tree parameters)
+{
+  gcc_assert (current_binding_level->kind == sk_function_parms);
+
+  cp_binding_level *fn_parms_scope = current_binding_level;
+
+  bool become_template =
+    fn_parms_scope->level_chain->kind != sk_template_parms;
+
+  size_t synth_idx = 0;
+  tree tparms = NULL_TREE;
+
+  // Roll back a scope level and either introduce a new template parameter list
+  // or update an existing one.  The function scope is added back after template
+  // parameter synthesis below.
+  current_binding_level = fn_parms_scope->level_chain;
+
+  if (become_template)
+    {
+      ++fully_implicit_template;
+      push_deferring_access_checks (dk_deferred);
+      begin_template_parm_list ();
+    }
+  else // extend current template parameter list
+    {
+      gcc_assert (current_template_parms);
+
+      // pop the innermost template parms into tparms
+      tree inner_vec = INNERMOST_TEMPLATE_PARMS (current_template_parms);
+      current_template_parms = TREE_CHAIN (current_template_parms);
+      for (size_t n = 0, end = TREE_VEC_LENGTH (inner_vec); n < end; ++n)
+	tparms = chainon (tparms, TREE_VEC_ELT (inner_vec, n));
+
+      ++processing_template_parmlist;
+    }
+
+  for (tree p = parameters; p && synth_idx < count; p = TREE_CHAIN (p))
+    {
+      tree generic_type_ptr
+	= find_type_usage (TREE_VALUE (p), tree_type_is_auto_or_concept);
+
+      if (!generic_type_ptr)
+	continue;
+
+      tree synth_id = make_generic_type_name (synth_idx++);
+      tree synth_tmpl_parm = finish_template_type_parm (class_type_node,
+							synth_id);
+      tparms = process_template_parm (tparms, DECL_SOURCE_LOCATION (TREE_VALUE
+								    (p)),
+				      build_tree_list (NULL_TREE,
+						       synth_tmpl_parm),
+				      /*non_type=*/false,
+				      /*param_pack=*/false); // TODO: support 'auto...'
+
+      // Rewrite the type of P to be the template_parm added above (getdecls is
+      // used to retrieve it since it is the most recent declaration in this
+      // scope).
+      TREE_TYPE (generic_type_ptr) = TREE_TYPE (getdecls ());
+    }
+
+  gcc_assert (synth_idx == count);
+
+  push_binding_level (fn_parms_scope);
+
+  end_template_parm_list (tparms);
+
+  return parameters;
+}
+
+/* Finish the declaration of a fully implicit function template.  Such a
+   template has no explicit template parameter list so has not been through the
+   normal template head and tail processing.  add_implicit_template_parms tries
+   to do the head; this tries to do the tail.  MEMBER_DECL_OPT should be
+   provided if the declaration is a class member such that it's template
+   declaration can be completed.  If MEMBER_DECL_OPT is provided the finished
+   form is returned.  Otherwise NULL_TREE is returned. */
+
+tree
+finish_fully_implicit_template (tree member_decl_opt)
+{
+  gcc_assert (fully_implicit_template > 0);
+
+  pop_deferring_access_checks ();
+  if (member_decl_opt)
+    member_decl_opt = finish_member_template_decl (member_decl_opt);
+  end_template_decl ();
+
+  --fully_implicit_template;
+
+  return member_decl_opt;
+}
+
 #include "gt-cp-pt.h"