Re: [PATCH] c++: Incomplete parameter mappings during normalization

[Jason Merrill <jason@redhat.com>]

On 9/25/20 4:44 PM, Patrick Palka wrote:
> In the testcase concepts7.C below, we currently reject the call to f1
> but we accept the call to f2, even though their associated constraints
> are functionally equivalent.

Rather, because they are not functionally equivalent.

> The reason satisfaction differs for (!!C<typename T::type) and
> C<typename T::type> is due to normalization: the former is already an
> atom, and the latter is not.  Normalization of the former yields itself,
> whereas normalization of the latter yields the atom 'true' with an empty
> parameter mapping (since the atom uses no template parameters).

Yes.

> So when
> building the latter atom we threw away the T::type term that would later
> result in substitution failure during satisfaction.
> 
> However, [temp.constr.normal]/1 says:
> 
>    - ...
>    - The normal form of a concept-id C<A1, A2, ..., An> is the normal
>      form of the constraint-expression of C, after substituting A1, A2,
>      ..., An for C's respective template parameters in the parameter
>      mappings in each atomic constraint.
>    - The normal form of any other expression E is the atomic constraint
>      whose expression is E and whose parameter mapping is the identity
>      mapping.
> 
> I believe these two bullet points imply that the atom 'true' in the
> normal form of C<typename T::type> should have the mapping R |-> T::type
> instead of the empty mapping that we give it, because according to the
> last bullet point, each atom should start out with the identity mapping
> that includes all template parameters.

But [temp.constr.atomic] says,

An atomic constraint is formed from an expression E and a mapping from 
the template parameters that appear within E...

So the identity mapping only includes template parameters that appear 
within the expression, which in this case is none.

Also, the discussion of the example in [temp.constr.normal] says,

"Normalization of B’s constraint-expression is valid and results in 
T::value (with the mapping T → U*) V true (with an empty mapping)."

So I think the testcase is already handled as specified.

> This patch fixes this issue by always giving the first atom in the
> normal form of each concept a 'complete' parameter mapping, i.e. one
> that includes all template parameters.  I think it suffices to do this
> only for the first atom so that we catch substitution failures like in
> concepts7.C at the right time.  For the other atoms, their mappings can
> continue to include only template parameters used in the atom.
> 
> I noticed that PR92268 alludes to this issue, so this patch refers to
> that PR and adds the PR's first testcase which we now accept.
> 
> Is the above interpretation of the standard correct here?  If so, does
> this seem like a good approach?
> 
> gcc/cp/ChangeLog:
> 
> 	PR c++/92268
> 	* constraint.cc (build_parameter_mapping): Add a bool parameter
> 	'complete'.  When 'complete' is true, then include all in-scope
> 	template parameters in the mapping.
> 	(norm_info::update_context): Pass false as the 'complete'
> 	argument to build_parameter_mapping.
> 	(norm_info::normalized_first_atom_p): New bool data member.
> 	(normalize_logical_operation): Set info.normalized_first_atom_p
> 	after normalizing the left operand.
> 	(normalize_concept_check): Reset info.normalized_first_atom_p
> 	before normalizing this concept.
> 	(normalize_atom): Always give the first atom of a concept
> 	definition a complete parameter mapping.
> 
> gcc/testsuite/ChangeLog:
> 
> 	PR c++/92268
> 	* g++.dg/cpp2a/concepts-pr92268.C: New test.
> 	* g++.dg/cpp2a/concepts-return-req1.C: Don't expect an error,
> 	as the call is no longer ambiguous.
> 	* g++.dg/cpp2a/concepts7.C: New test.
> 	* g++.dg/cpp2a/concepts8.C: New test.
> ---
>   gcc/cp/constraint.cc                          | 44 ++++++++++++++++---
>   gcc/testsuite/g++.dg/cpp2a/concepts-pr92268.C | 42 ++++++++++++++++++
>   .../g++.dg/cpp2a/concepts-return-req1.C       |  2 +-
>   gcc/testsuite/g++.dg/cpp2a/concepts7.C        |  9 ++++
>   gcc/testsuite/g++.dg/cpp2a/concepts8.C        | 25 +++++++++++
>   5 files changed, 116 insertions(+), 6 deletions(-)
>   create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-pr92268.C
>   create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts7.C
>   create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts8.C
> 
> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> index d49957a6c4a..729d02b73d7 100644
> --- a/gcc/cp/constraint.cc
> +++ b/gcc/cp/constraint.cc
> @@ -559,10 +559,14 @@ map_arguments (tree parms, tree args)
>     return parms;
>   }
>   
> -/* Build the parameter mapping for EXPR using ARGS.  */
> +/* Build the parameter mapping for EXPR using ARGS.
> +
> +   If COMPLETE then return the complete parameter mapping that includes
> +   all in-scope template parameters.  Otherwise include only the
> +   parameters used by EXPR.  */
>   
>   static tree
> -build_parameter_mapping (tree expr, tree args, tree decl)
> +build_parameter_mapping (tree expr, tree args, tree decl, bool complete)
>   {
>     tree ctx_parms = NULL_TREE;
>     if (decl)
> @@ -579,6 +583,24 @@ build_parameter_mapping (tree expr, tree args, tree decl)
>         ctx_parms = current_template_parms;
>       }
>   
> +  if (!ctx_parms)
> +    return NULL_TREE;
> +
> +  if (complete)
> +    {
> +      if (!processing_template_parmlist)
> +	/* Search through ctx_parms to build a complete mapping.  */
> +	expr = template_parms_to_args (ctx_parms);
> +      else
> +	/* The expression might use parameters introduced in the currently
> +	   open template parameter list, which ctx_parms doesn't yet have.
> +	   So we need to search through the expression in addition to
> +	   ctx_parms.  */
> +	expr = tree_cons (NULL_TREE, expr,
> +			  build_tree_list (NULL_TREE,
> +					   template_parms_to_args (ctx_parms)));
> +    }
> +
>     tree parms = find_template_parameters (expr, ctx_parms);
>     tree map = map_arguments (parms, args);
>     return map;
> @@ -635,7 +657,8 @@ struct norm_info : subst_info
>     {
>       if (generate_diagnostics ())
>         {
> -	tree map = build_parameter_mapping (expr, args, in_decl);
> +	tree map = build_parameter_mapping (expr, args, in_decl,
> +					    /*complete=*/false);
>   	context = tree_cons (map, expr, context);
>         }
>       in_decl = get_concept_check_template (expr);
> @@ -647,6 +670,9 @@ struct norm_info : subst_info
>        for that check.  */
>   
>     tree context;
> +
> +  /* True if we've normalized the first atom of this concept.  */
> +  bool normalized_first_atom_p = false;
>   };
>   
>   static tree normalize_expression (tree, tree, norm_info);
> @@ -658,6 +684,7 @@ static tree
>   normalize_logical_operation (tree t, tree args, tree_code c, norm_info info)
>   {
>     tree t0 = normalize_expression (TREE_OPERAND (t, 0), args, info);
> +  info.normalized_first_atom_p = true;
>     tree t1 = normalize_expression (TREE_OPERAND (t, 1), args, info);
>   
>     /* Build a new info object for the constraint.  */
> @@ -706,6 +733,7 @@ normalize_concept_check (tree check, tree args, norm_info info)
>       return error_mark_node;
>   
>     info.update_context (check, args);
> +  info.normalized_first_atom_p = false;
>     return normalize_expression (def, subst, info);
>   }
>   
> @@ -722,8 +750,14 @@ normalize_atom (tree t, tree args, norm_info info)
>     if (concept_check_p (t))
>       return normalize_concept_check (t, args, info);
>   
> -  /* Build the parameter mapping for the atom.  */
> -  tree map = build_parameter_mapping (t, args, info.in_decl);
> +  /* Build the parameter mapping for the atom.  If T is the first
> +     atom of a concept definition then we want this mapping to be
> +     complete, so that during satisfaction we check all substituted
> +     template parameters first and foremost.  */
> +  bool complete = (!info.normalized_first_atom_p
> +		   && info.in_decl != NULL_TREE
> +		   && concept_definition_p (info.in_decl));
> +  tree map = build_parameter_mapping (t, args, info.in_decl, complete);
>   
>     /* Build a new info object for the atom.  */
>     tree ci = build_tree_list (t, info.context);
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-pr92268.C b/gcc/testsuite/g++.dg/cpp2a/concepts-pr92268.C
> new file mode 100644
> index 00000000000..817cd3187bd
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-pr92268.C
> @@ -0,0 +1,42 @@
> +// PR c++/92268
> +// { dg-do compile { target c++20 } }
> +
> +template<typename T, typename U>
> +  struct common_reference { };
> +
> +template<typename T, typename U>
> +  using common_reference_t = typename common_reference<T, U>::type;
> +
> +template<typename T, typename U> concept foo = true;
> +template<typename T, typename U> concept bar = true;
> +template<typename T, typename U> concept baz = true;
> +
> +template<typename T, typename U>
> +  concept common_reference_with
> +    =  foo<common_reference_t<T, U>, common_reference_t<U, T>>
> +    && bar<common_reference_t<T, U>, common_reference_t<U, T>>
> +    && baz<common_reference_t<T, U>, common_reference_t<U, T>>;
> +
> +template<typename T>
> +  using iter_reference_t = decltype(((T*)0)->f());
> +
> +template<typename I>
> +  concept forward_iterator
> +    = common_reference_with<iter_reference_t<I>&&, typename I::value_type&>;
> +
> +struct test_range
> +{
> +  struct iterator
> +  {
> +    using value_type = int;
> +
> +    char f() const;
> +  };
> +
> +  iterator begin();
> +};
> +
> +template<typename T>
> +concept F = requires (T& t) { { t.begin() } -> forward_iterator; };
> +
> +static_assert( !F<test_range> );
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-return-req1.C b/gcc/testsuite/g++.dg/cpp2a/concepts-return-req1.C
> index d21a49be14e..84c9ae9d6da 100644
> --- a/gcc/testsuite/g++.dg/cpp2a/concepts-return-req1.C
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-return-req1.C
> @@ -15,5 +15,5 @@ int f(...);
>   
>   int main()
>   {
> -  f<int>();			// { dg-error "ambiguous" }
> +  f<int>();
>   }
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts7.C b/gcc/testsuite/g++.dg/cpp2a/concepts7.C
> new file mode 100644
> index 00000000000..780cfc859ce
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts7.C
> @@ -0,0 +1,9 @@
> +// { dg-do compile { target c++20 } }
> +
> +template<class R> concept C = true;
> +
> +template<class T> int f1(T) requires (!!C<typename T::type>); // { dg-error "'int'" }
> +template<class T> int f2(T) requires C<typename T::type>;
> +
> +int i1 = f1(0); // { dg-error "no match" }
> +int i2 = f2(0); // { dg-error "no match|'int'" }
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts8.C b/gcc/testsuite/g++.dg/cpp2a/concepts8.C
> new file mode 100644
> index 00000000000..29d3e24e323
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts8.C
> @@ -0,0 +1,25 @@
> +// { dg-do compile { target c++20 } }
> +
> +template<class... T> concept C = true;
> +
> +template<class T> struct W { using type = T::type; };
> +
> +struct S { using type = int; };
> +
> +template<class T, class U=T> int f1() requires (C<typename T::type>
> +						&& C<typename W<U>::type>);
> +
> +int i1 = f1<int>(); // { dg-error "no match|'int'" }
> +int i2 = f1<S>();
> +
> +template<class T, class U=T> int f2() requires (C<typename U::type>
> +						&& C<typename W<T>::type>);
> +
> +int i3 = f2<int>(); // { dg-error "no match|'int'" }
> +int i4 = f2<S>();
> +int i5 = f2<S, int>(); // { dg-error "no match|'int" }
> +
> +template<class T> int f3() requires C<typename T::type, typename W<T>::type>;
> +
> +int i6 = f3<int>(); // { dg-error "no match|'int'" }
> +int i7 = f3<S>();
>