Implement multiple 'auto' feature from Concepts TS.

	* parser.c (cp_parser_type_id_1): Allow 'auto' if -fconcepts.
	(cp_parser_template_type_arg): Likewise.
	(get_concept_from_constraint): Split out most logic to...
	* constraint.cc (placeholder_extract_concept_and_args): ...here.
	(equivalent_placeholder_constraints, hash_placeholder_constraint): New.
	* cxx-pretty-print.c (pp_cxx_constrained_type_spec): New.
	* cxx-pretty-print.h: Declare it.
	* error.c (dump_type) [TEMPLATE_TYPE_PARM]: Call it.
	* pt.c (is_auto_r, extract_autos_r, extract_autos, auto_hash): New.
	(type_uses_auto): Use is_auto_r.
	(do_auto_deduction): Handle multiple 'auto's if -fconcepts.
	* typeck.c (structural_comptypes) [TEMPLATE_TYPE_PARM]: Compare
	constraints.

git-svn-id: https://gcc.gnu.org/svn/gcc/trunk@229629 138bc75d-0d04-0410-961f-82ee72b054a4

10 files changed, 295 insertions, 31 deletions

diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 886a18968c8..d283cbe5f3a 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,5 +1,20 @@
 2015-10-31  Jason Merrill  <jason@redhat.com>
 
+	Implement multiple 'auto' feature from Concepts TS.
+	* parser.c (cp_parser_type_id_1): Allow 'auto' if -fconcepts.
+	(cp_parser_template_type_arg): Likewise.
+	(get_concept_from_constraint): Split out most logic to...
+	* constraint.cc (placeholder_extract_concept_and_args): ...here.
+	(equivalent_placeholder_constraints, hash_placeholder_constraint): New.
+	* cxx-pretty-print.c (pp_cxx_constrained_type_spec): New.
+	* cxx-pretty-print.h: Declare it.
+	* error.c (dump_type) [TEMPLATE_TYPE_PARM]: Call it.
+	* pt.c (is_auto_r, extract_autos_r, extract_autos, auto_hash): New.
+	(type_uses_auto): Use is_auto_r.
+	(do_auto_deduction): Handle multiple 'auto's if -fconcepts.
+	* typeck.c (structural_comptypes) [TEMPLATE_TYPE_PARM]: Compare
+	constraints.
+
 	* pt.c (for_each_template_parm_r): Use WALK_SUBTREE.
 	Return a meaningful value rather than error_mark_node.
 	(for_each_template_parm): Return a tree.
diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
index cb82535af49..a1fbf174ee8 100644
--- a/gcc/cp/constraint.cc
+++ b/gcc/cp/constraint.cc
@@ -1379,6 +1379,89 @@ make_constrained_auto (tree con, tree args)
   return decl;
 }
 
+/* Given the predicate constraint T from a placeholder type, extract its
+   TMPL and ARGS.  */
+
+void
+placeholder_extract_concept_and_args (tree t, tree &tmpl, tree &args)
+{
+  gcc_assert (TREE_CODE (t) == PRED_CONSTR);
+  t = PRED_CONSTR_EXPR (t);
+  gcc_assert (TREE_CODE (t) == CALL_EXPR
+              || TREE_CODE (t) == TEMPLATE_ID_EXPR
+              || VAR_P (t));
+
+  if (TREE_CODE (t) == CALL_EXPR)
+    t = CALL_EXPR_FN (t);
+  if (TREE_CODE (t) == TEMPLATE_ID_EXPR)
+    {
+      tmpl = TREE_OPERAND (t, 0);
+      if (TREE_CODE (tmpl) == OVERLOAD)
+	{
+	  gcc_assert (OVL_CHAIN (tmpl) == NULL_TREE);
+	  tmpl = OVL_FUNCTION (tmpl);
+	}
+      args = TREE_OPERAND (t, 1);
+    }
+  else if (DECL_P (t))
+    {
+      tmpl = DECL_TI_TEMPLATE (t);
+      args = DECL_TI_ARGS (t);
+    }
+  else
+    gcc_unreachable ();
+}
+
+/* Returns true iff the placeholders C1 and C2 are equivalent.  C1
+   and C2 can be either PRED_CONSTR_EXPR or TEMPLATE_TYPE_PARM.  */
+
+bool
+equivalent_placeholder_constraints (tree c1, tree c2)
+{
+  if (TREE_CODE (c1) == TEMPLATE_TYPE_PARM)
+    c1 = PLACEHOLDER_TYPE_CONSTRAINTS (c1);
+  if (TREE_CODE (c2) == TEMPLATE_TYPE_PARM)
+    c2 = PLACEHOLDER_TYPE_CONSTRAINTS (c2);
+
+  if (c1 == c2)
+    return true;
+  if (!c1 || !c2)
+    return false;
+
+  tree t1, t2, a1, a2;
+  placeholder_extract_concept_and_args (c1, t1, a1);
+  placeholder_extract_concept_and_args (c2, t2, a2);
+
+  if (t1 != t2)
+    return false;
+  int len = TREE_VEC_LENGTH (a1);
+  if (len != TREE_VEC_LENGTH (a2))
+    return false;
+  /* Skip the first argument to avoid infinite recursion on the
+     placeholder auto itself.  */
+  for (int i = len-1; i > 0; --i)
+    if (!cp_tree_equal (TREE_VEC_ELT (a1, i),
+			TREE_VEC_ELT (a2, i)))
+      return false;
+  return true;
+}
+
+/* Return a hash value for the placeholder PRED_CONSTR C.  */
+
+hashval_t
+hash_placeholder_constraint (tree c)
+{
+  tree t, a;
+  placeholder_extract_concept_and_args (c, t, a);
+
+  /* Like hash_tmpl_and_args, but skip the first argument.  */
+  hashval_t val = iterative_hash_object (DECL_UID (t), 0);
+
+  for (int i = TREE_VEC_LENGTH (a)-1; i > 0; --i)
+    val = iterative_hash_template_arg (TREE_VEC_ELT (a, i), val);
+
+  return val;
+}
 
 /*---------------------------------------------------------------------------
                         Constraint substitution
diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
index 6202cab621d..adb4bae0a22 100644
--- a/gcc/cp/cp-tree.h
+++ b/gcc/cp/cp-tree.h
@@ -6729,6 +6729,9 @@ extern tree get_shorthand_constraints           (tree);
 extern tree build_concept_check                 (tree, tree, tree = NULL_TREE);
 extern tree build_constrained_parameter         (tree, tree, tree = NULL_TREE);
 extern tree make_constrained_auto               (tree, tree);
+extern void placeholder_extract_concept_and_args (tree, tree&, tree&);
+extern bool equivalent_placeholder_constraints  (tree, tree);
+extern hashval_t hash_placeholder_constraint	(tree);
 extern bool deduce_constrained_parameter        (tree, tree&, tree&);
 extern tree resolve_constraint_check            (tree);
 extern tree check_function_concept              (tree);
diff --git a/gcc/cp/cxx-pretty-print.c b/gcc/cp/cxx-pretty-print.c
index ea6b4c56b63..72bbfc5c318 100644
--- a/gcc/cp/cxx-pretty-print.c
+++ b/gcc/cp/cxx-pretty-print.c
@@ -2195,6 +2195,26 @@ pp_cxx_canonical_template_parameter (cxx_pretty_printer *pp, tree parm)
   pp_cxx_end_template_argument_list (pp);
 }
 
+/* Print a constrained-type-specifier.  */
+
+void
+pp_cxx_constrained_type_spec (cxx_pretty_printer *pp, tree c)
+{
+  tree t, a;
+  placeholder_extract_concept_and_args (c, t, a);
+  pp->id_expression (t);
+  if (TREE_VEC_LENGTH (a) > 1)
+    {
+      pp_cxx_begin_template_argument_list (pp);
+      tree args = make_tree_vec (TREE_VEC_LENGTH (a) - 1);
+      for (int i = TREE_VEC_LENGTH (a) - 1; i > 0; --i)
+	TREE_VEC_ELT (args, i-1) = TREE_VEC_ELT (a, i);
+      pp_cxx_template_argument_list (pp, args);
+      ggc_free (args);
+      pp_cxx_end_template_argument_list (pp);
+    }
+}
+
 /*
   template-declaration:
      export(opt) template < template-parameter-list > declaration
diff --git a/gcc/cp/cxx-pretty-print.h b/gcc/cp/cxx-pretty-print.h
index e5161df0644..9bb9ccf6e66 100644
--- a/gcc/cp/cxx-pretty-print.h
+++ b/gcc/cp/cxx-pretty-print.h
@@ -107,5 +107,6 @@ void pp_cxx_parameterized_constraint (cxx_pretty_printer *, tree);
 void pp_cxx_conjunction (cxx_pretty_printer *, tree);
 void pp_cxx_disjunction (cxx_pretty_printer *, tree);
 void pp_cxx_constraint (cxx_pretty_printer *, tree);
+void pp_cxx_constrained_type_spec (cxx_pretty_printer *, tree);
 
 #endif /* GCC_CXX_PRETTY_PRINT_H */
diff --git a/gcc/cp/error.c b/gcc/cp/error.c
index b0280d27ed0..75f6abb415f 100644
--- a/gcc/cp/error.c
+++ b/gcc/cp/error.c
@@ -494,7 +494,9 @@ dump_type (cxx_pretty_printer *pp, tree t, int flags)
 
     case TEMPLATE_TYPE_PARM:
       pp_cxx_cv_qualifier_seq (pp, t);
-      if (TYPE_IDENTIFIER (t))
+      if (tree c = PLACEHOLDER_TYPE_CONSTRAINTS (t))
+	pp_cxx_constrained_type_spec (pp, c);
+      else if (TYPE_IDENTIFIER (t))
 	pp_cxx_tree_identifier (pp, TYPE_IDENTIFIER (t));
       else
 	pp_cxx_canonical_template_parameter
diff --git a/gcc/cp/parser.c b/gcc/cp/parser.c
index 3c6b2b14690..19e306df4ba 100644
--- a/gcc/cp/parser.c
+++ b/gcc/cp/parser.c
@@ -19442,6 +19442,8 @@ cp_parser_type_id_1 (cp_parser* parser, bool is_template_arg,
     abstract_declarator = NULL;
 
   if (type_specifier_seq.type
+      /* The concepts TS allows 'auto' as a type-id.  */
+      && !flag_concepts
       /* None of the valid uses of 'auto' in C++14 involve the type-id
 	 nonterminal, but it is valid in a trailing-return-type.  */
       && !(cxx_dialect >= cxx14 && is_trailing_return)
@@ -19484,7 +19486,7 @@ cp_parser_template_type_arg (cp_parser *parser)
     = G_("types may not be defined in template arguments");
   r = cp_parser_type_id_1 (parser, true, false);
   parser->type_definition_forbidden_message = saved_message;
-  if (cxx_dialect >= cxx14 && type_uses_auto (r))
+  if (cxx_dialect >= cxx14 && !flag_concepts && type_uses_auto (r))
     {
       error ("invalid use of %<auto%> in template argument");
       r = error_mark_node;
@@ -36557,23 +36559,9 @@ tree_type_is_auto_or_concept (const_tree t)
 static tree
 get_concept_from_constraint (tree t)
 {
-  gcc_assert (TREE_CODE (t) == PRED_CONSTR);
-  t = PRED_CONSTR_EXPR (t);
-  gcc_assert (TREE_CODE (t) == CALL_EXPR
-              || TREE_CODE (t) == TEMPLATE_ID_EXPR
-              || VAR_P (t));
-
-  if (TREE_CODE (t) == TEMPLATE_ID_EXPR)
-    return DECL_TEMPLATE_RESULT (TREE_OPERAND (t, 0));
-  if (VAR_P (t))
-    return DECL_TEMPLATE_RESULT (DECL_TI_TEMPLATE (t));
-  else
-    {
-      tree fn = CALL_EXPR_FN (t);
-      tree ovl = TREE_OPERAND (fn, 0);
-      tree tmpl = OVL_FUNCTION (ovl);
-      return DECL_TEMPLATE_RESULT (tmpl);
-    }
+  tree tmpl, args;
+  placeholder_extract_concept_and_args (t, tmpl, args);
+  return DECL_TEMPLATE_RESULT (tmpl);
 }
 
 /* Add an implicit template type parameter to the CURRENT_TEMPLATE_PARMS
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index 3d3e4a65cc9..e836ec747d0 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -23394,6 +23394,100 @@ listify_autos (tree type, tree auto_node)
   return tsubst (type, argvec, tf_warning_or_error, NULL_TREE);
 }
 
+/* Hash traits for hashing possibly constrained 'auto'
+   TEMPLATE_TYPE_PARMs for use by do_auto_deduction.  */
+
+struct auto_hash : default_hash_traits<tree>
+{
+  static inline hashval_t hash (tree);
+  static inline bool equal (tree, tree);
+};
+
+/* Hash the 'auto' T.  */
+
+inline hashval_t
+auto_hash::hash (tree t)
+{
+  if (tree c = PLACEHOLDER_TYPE_CONSTRAINTS (t))
+    /* Matching constrained-type-specifiers denote the same template
+       parameter, so hash the constraint.  */
+    return hash_placeholder_constraint (c);
+  else
+    /* But unconstrained autos are all separate, so just hash the pointer.  */
+    return iterative_hash_object (t, 0);
+}
+
+/* Compare two 'auto's.  */
+
+inline bool
+auto_hash::equal (tree t1, tree t2)
+{
+  if (t1 == t2)
+    return true;
+
+  tree c1 = PLACEHOLDER_TYPE_CONSTRAINTS (t1);
+  tree c2 = PLACEHOLDER_TYPE_CONSTRAINTS (t2);
+
+  /* Two unconstrained autos are distinct.  */
+  if (!c1 || !c2)
+    return false;
+
+  return equivalent_placeholder_constraints (c1, c2);
+}
+
+/* for_each_template_parm callback for extract_autos: if t is a (possibly
+   constrained) auto, add it to the vector.  */
+
+static int
+extract_autos_r (tree t, void *data)
+{
+  hash_table<auto_hash> &hash = *(hash_table<auto_hash>*)data;
+  if (is_auto_or_concept (t))
+    {
+      /* All the autos were built with index 0; fix that up now.  */
+      tree *p = hash.find_slot (t, INSERT);
+      unsigned idx;
+      if (*p)
+	/* If this is a repeated constrained-type-specifier, use the index we
+	   chose before.  */
+	idx = TEMPLATE_PARM_IDX (TEMPLATE_TYPE_PARM_INDEX (*p));
+      else
+	{
+	  /* Otherwise this is new, so use the current count.  */
+	  *p = t;
+	  idx = hash.elements () - 1;
+	}
+      TEMPLATE_PARM_IDX (TEMPLATE_TYPE_PARM_INDEX (t)) = idx;
+    }
+
+  /* Always keep walking.  */
+  return 0;
+}
+
+/* Return a TREE_VEC of the 'auto's used in type under the Concepts TS, which
+   says they can appear anywhere in the type.  */
+
+static tree
+extract_autos (tree type)
+{
+  hash_set<tree> visited;
+  hash_table<auto_hash> hash (2);
+
+  for_each_template_parm (type, extract_autos_r, &hash, &visited, true);
+
+  tree tree_vec = make_tree_vec (hash.elements());
+  for (hash_table<auto_hash>::iterator iter = hash.begin();
+       iter != hash.end(); ++iter)
+    {
+      tree elt = *iter;
+      unsigned i = TEMPLATE_PARM_IDX (TEMPLATE_TYPE_PARM_INDEX (elt));
+      TREE_VEC_ELT (tree_vec, i)
+	= build_tree_list (NULL_TREE, TYPE_NAME (elt));
+    }
+
+  return tree_vec;
+}
+
 /* Replace occurrences of 'auto' in TYPE with the appropriate type deduced
    from INIT.  AUTO_NODE is the TEMPLATE_TYPE_PARM used for 'auto' in TYPE.  */
 
@@ -23450,11 +23544,11 @@ do_auto_deduction (tree type, tree init, tree auto_node,
 
   init = resolve_nondeduced_context (init);
 
-  targs = make_tree_vec (1);
   if (AUTO_IS_DECLTYPE (auto_node))
     {
       bool id = (DECL_P (init) || (TREE_CODE (init) == COMPONENT_REF
 				   && !REF_PARENTHESIZED_P (init)));
+      targs = make_tree_vec (1);
       TREE_VEC_ELT (targs, 0)
 	= finish_decltype_type (init, id, tf_warning_or_error);
       if (type != auto_node)
@@ -23467,14 +23561,21 @@ do_auto_deduction (tree type, tree init, tree auto_node,
   else
     {
       tree parms = build_tree_list (NULL_TREE, type);
-      tree tparms = make_tree_vec (1);
-      int val;
-
-      TREE_VEC_ELT (tparms, 0)
-	= build_tree_list (NULL_TREE, TYPE_NAME (auto_node));
-      val = type_unification_real (tparms, targs, parms, &init, 1, 0,
-				   DEDUCE_CALL, LOOKUP_NORMAL,
-				   NULL, /*explain_p=*/false);
+      tree tparms;
+
+      if (flag_concepts)
+	tparms = extract_autos (type);
+      else
+	{
+	  tparms = make_tree_vec (1);
+	  TREE_VEC_ELT (tparms, 0)
+	    = build_tree_list (NULL_TREE, TYPE_NAME (auto_node));
+	}
+
+      targs = make_tree_vec (TREE_VEC_LENGTH (tparms));
+      int val = type_unification_real (tparms, targs, parms, &init, 1, 0,
+				       DEDUCE_CALL, LOOKUP_NORMAL,
+				       NULL, /*explain_p=*/false);
       if (val > 0)
 	{
 	  if (processing_template_decl)
@@ -23503,7 +23604,7 @@ do_auto_deduction (tree type, tree init, tree auto_node,
      of each declared variable is determined as described above. If the
      type deduced for the template parameter U is not the same in each
      deduction, the program is ill-formed.  */
-  if (TREE_TYPE (auto_node)
+  if (!flag_concepts && TREE_TYPE (auto_node)
       && !same_type_p (TREE_TYPE (auto_node), TREE_VEC_ELT (targs, 0)))
     {
       if (cfun && auto_node == current_function_auto_return_pattern
@@ -23516,7 +23617,7 @@ do_auto_deduction (tree type, tree init, tree auto_node,
 	       auto_node, TREE_TYPE (auto_node), TREE_VEC_ELT (targs, 0));
       return error_mark_node;
     }
-  if (context != adc_requirement)
+  if (!flag_concepts)
     TREE_TYPE (auto_node) = TREE_VEC_ELT (targs, 0);
 
   /* Check any placeholder constraints against the deduced type. */
@@ -23592,13 +23693,33 @@ is_auto (const_tree type)
     return false;
 }
 
+/* for_each_template_parm callback for type_uses_auto.  */
+
+int
+is_auto_r (tree tp, void */*data*/)
+{
+  return is_auto_or_concept (tp);
+}
+
 /* 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);
+  if (flag_concepts)
+    {
+      /* The Concepts TS allows multiple autos in one type-specifier; just
+	 return the first one we find, do_auto_deduction will collect all of
+	 them.  */
+      if (uses_template_parms (type))
+	return for_each_template_parm (type, is_auto_r, /*data*/NULL,
+				       /*visited*/NULL, /*nondeduced*/true);
+      else
+	return NULL_TREE;
+    }
+  else
+    return find_type_usage (type, is_auto);
 }
 
 /* Returns true iff TYPE is a TEMPLATE_TYPE_PARM representing 'auto',
diff --git a/gcc/cp/typeck.c b/gcc/cp/typeck.c
index 9d043e0411f..e68e9df02a4 100644
--- a/gcc/cp/typeck.c
+++ b/gcc/cp/typeck.c
@@ -1333,6 +1333,10 @@ structural_comptypes (tree t1, tree t2, int strict)
 	 template parameters set, they can't be equal.  */
       if (!comp_template_parms_position (t1, t2))
 	return false;
+      /* Constrained 'auto's are distinct from parms that don't have the same
+	 constraints.  */
+      if (!equivalent_placeholder_constraints (t1, t2))
+	return false;
       break;
 
     case TYPENAME_TYPE:
diff --git a/gcc/testsuite/g++.dg/concepts/auto1.C b/gcc/testsuite/g++.dg/concepts/auto1.C
new file mode 100644
index 00000000000..6068e4cc486
--- /dev/null
+++ b/gcc/testsuite/g++.dg/concepts/auto1.C
@@ -0,0 +1,27 @@
+// { dg-options "-std=c++1z" }
+
+template <class T1, class T2> class A { };
+
+A<int, int> a;
+A<double, float> a2;
+A<double, double> a22;
+
+A<auto, auto> b = a;
+A<auto, auto> b1 = a2;
+
+template <class T> concept bool C = __is_same_as (T, int);
+
+A<C,C> b2 = a;
+A<C,C> b3 = a2;			// { dg-error "" }
+A<C,C> b32 = a22;		// { dg-error "" }
+
+template <class T> concept bool C2() { return __is_enum (T); }
+
+enum E1 { };
+enum E2 { };
+
+A<E1,E1> a3;
+A<C2,C2> b4 = a3;
+
+A<E1,E2> a4;
+A<C2,C2> b5 = a4;		// { dg-error "" }