[v1] c++: Hash placeholder constraint in ctp_hasher

This patch addresses a difference between the hash function and the equality
function for canonical types of template parameters (ctp_hasher). The equality
function uses comptypes (typeck.cc) (with COMPARE_STRUCTURAL) and checks
constraint equality for two auto nodes (typeck.cc:1586), while the hash
function ignores it (pt.cc:4528). This leads to hash collisions that can be
avoided by using `hash_placeholder_constraint` (constraint.cc:1150).

* constraint.cc (hash_placeholder_constraint): Rename to
iterative_hash_placeholder_constraint.
(iterative_hash_placeholder_constraint): Rename from
hash_placeholder_constraint and add the initial val argument.
* cp-tree.h (hash_placeholder_constraint): Rename to
iterative_hash_placeholder_constraint.
(iterative_hash_placeholder_constraint): Renamed from
hash_placeholder_constraint and add the initial val argument.
* pt.cc (struct ctp_hasher): Updated to use
iterative_hash_placeholder_constraint in the case of a valid placeholder
constraint.
(auto_hash::hash): Reflect the renaming of hash_placeholder_constraint to
iterative_hash_placeholder_constraint.
---
gcc/cp/constraint.cc | 4 ++--
gcc/cp/cp-tree.h | 2 +-
gcc/cp/pt.cc | 9 +++++++--
3 files changed, 10 insertions(+), 5 deletions(-)

if (tree c = NON_ERROR (PLACEHOLDER_TYPE_CONSTRAINTS (t)))
/* Matching constrained-type-specifiers denote the same template
parameter, so hash the constraint. */
- return hash_placeholder_constraint (c);
+ return iterative_hash_placeholder_constraint (c, 0);
else
/* But unconstrained autos are all separate, so just hash the pointer. */
return iterative_hash_object (t, 0);

On Tue, 9 Jul 2024, Seyed Sajad Kahani wrote:

> This patch addresses a difference between the hash function and the equality
> function for canonical types of template parameters (ctp_hasher). The equality
> function uses comptypes (typeck.cc) (with COMPARE_STRUCTURAL) and checks
> constraint equality for two auto nodes (typeck.cc:1586), while the hash
> function ignores it (pt.cc:4528). This leads to hash collisions that can be
> avoided by using `hash_placeholder_constraint` (constraint.cc:1150).

This seems like a nice improvement, thanks!  It seems your mail client
removed leading whitespace from your inline patch, making it hard to
read or apply.  Could you resend as an attachment or e.g. via
'git send-email'?

> 
> * constraint.cc (hash_placeholder_constraint): Rename to
> iterative_hash_placeholder_constraint.
> (iterative_hash_placeholder_constraint): Rename from
> hash_placeholder_constraint and add the initial val argument.
> * cp-tree.h (hash_placeholder_constraint): Rename to
> iterative_hash_placeholder_constraint.
> (iterative_hash_placeholder_constraint): Renamed from
> hash_placeholder_constraint and add the initial val argument.
> * pt.cc (struct ctp_hasher): Updated to use
> iterative_hash_placeholder_constraint in the case of a valid placeholder
> constraint.
> (auto_hash::hash): Reflect the renaming of hash_placeholder_constraint to
> iterative_hash_placeholder_constraint.
> ---
> gcc/cp/constraint.cc | 4 ++--
> gcc/cp/cp-tree.h | 2 +-
> gcc/cp/pt.cc | 9 +++++++--
> 3 files changed, 10 insertions(+), 5 deletions(-)
> 
> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> index ebf4255e5..78aacb77a 100644
> --- a/gcc/cp/constraint.cc
> +++ b/gcc/cp/constraint.cc
> @@ -1971,13 +1971,13 @@ equivalent_placeholder_constraints (tree c1, tree c2)
> /* Return a hash value for the placeholder ATOMIC_CONSTR C. */
> hashval_t
> -hash_placeholder_constraint (tree c)
> +iterative_hash_placeholder_constraint (tree c, hashval_t val)
> {
> 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);
> + val = iterative_hash_object (DECL_UID (t), val);
> for (int i = TREE_VEC_LENGTH (a)-1; i > 0; --i)
> val = iterative_hash_template_arg (TREE_VEC_ELT (a, i), val);
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index 4bb3e9c49..294e88f75 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -8588,7 +8588,7 @@ extern tree_pair finish_type_constraints (tree,
> tree, tsubst_flags_t);
> extern tree build_constrained_parameter (tree, tree, tree = NULL_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 hashval_t iterative_hash_placeholder_constraint (tree, hashval_t);
> 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/pt.cc b/gcc/cp/pt.cc
> index d1316483e..9a80c44a5 100644
> --- a/gcc/cp/pt.cc
> +++ b/gcc/cp/pt.cc
> @@ -4525,7 +4525,12 @@ struct ctp_hasher : ggc_ptr_hash<tree_node>
> val = iterative_hash_object (TEMPLATE_TYPE_LEVEL (t), val);
> val = iterative_hash_object (TEMPLATE_TYPE_IDX (t), val);
> if (TREE_CODE (t) == TEMPLATE_TYPE_PARM)
> - val = iterative_hash_template_arg (CLASS_PLACEHOLDER_TEMPLATE (t), val);
> + {
> + val
> + = iterative_hash_template_arg (CLASS_PLACEHOLDER_TEMPLATE (t), val);
> + if (tree c = NON_ERROR (PLACEHOLDER_TYPE_CONSTRAINTS (t)))
> + val = iterative_hash_placeholder_constraint(c, val);
> + }
> if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM)
> val = iterative_hash_template_arg (TYPE_TI_ARGS (t), val);
> --comparing_specializations;
> @@ -29605,7 +29610,7 @@ auto_hash::hash (tree t)
> if (tree c = NON_ERROR (PLACEHOLDER_TYPE_CONSTRAINTS (t)))
> /* Matching constrained-type-specifiers denote the same template
> parameter, so hash the constraint. */
> - return hash_placeholder_constraint (c);
> + return iterative_hash_placeholder_constraint (c, 0);
> else
> /* But unconstrained autos are all separate, so just hash the pointer. */
> return iterative_hash_object (t, 0);
> -- 
> 2.45.2
> 
> On Tue, 9 Jul 2024 at 14:41, Seyed Sajad Kahani <sska1377@gmail.com> wrote:
> >
> > Hi.
> >
> > While investigating a fix for C++/PR115030 (a bug in constrained auto
> > deduction), I was wondering why we are not substituting constraint args of an
> > auto node in tsubst (pt.cc:16533). Instead, this substitution is delayed until
> > do_auto_deduction (pt.cc), where we attempt to find the substituted args of the
> > enclosing scope. At that point, it becomes difficult to find partially
> > specialised args, as they are erased in the process. I propose modifying tsubst
> > to eagerly substitute the constraint args of an auto node.
> >
> > By making this change, we would not need to provide outer_targs for
> > do_auto_deduction in cases where tsubst has been called for the type, which
> > covers most scenarios. However, we still need outer_targs for cases like:
> >
> > template <typename T, C<T> auto V>
> > struct S { };
> >
> > Hence, outer_targs cannot be completely removed but will be set to TREE_NULL in
> > all calls except the one in convert_template_argument (pt.cc:8788).
> > Additionally, the tmpl argument of do_auto_deduction, which helps to provide
> > outer args in the scope, will no longer be necessary and can be safely
> > removed.
> >
> > Also, the trimming hack proposed in
> > https://gcc.gnu.org/pipermail/gcc-patches/2024-June/654724.html to address
> > C++/PR114915 is no longer needed. We will add an assertion to ensure that the
> > missing levels do not become negative.
> >
> > Substituting constraint arguments earlier will slightly alter error messages
> > (see testsuite/g++.dg/cpp2a/concepts-placeholder3.C as an example).
> >
> > To summarise, I have made the following changes:
> > - Modified tsubst to substitute the constraint args.
> > - Fixed shallow checks for using the cache from TEMPLATE_TYPE_DESCENDANTS
> > (pt.cc:16513).
> > - Substituted the constraint args and the auto node itself, while retaining all
> > other parameters as is (pt.cc:16533).
> > - Removed now unnecessary code that attempted to find outer scope template info
> > and args in various locations.
> > - Updated the missing levels hack (pt.cc:31320) to work with the substituted
> > constraints.
> > - Used level instead of orig_level to find the missing levels.
> > - Added an assertion for future safety.
> >
> > Details of these changes can be found in the patch "[PATCH v1] c++: Eagerly
> > substitute auto constraint args in tsubst [PR115030]" that will be replied to
> > this thread.
> >
> > This patch, in my opinion, improves code quality by removing an argument from
> > do_auto_deduction and eliminating the out-of-scope task of finding outer_targs
> > within do_auto_deduction. It simplifies the usage of do_auto_deduction and
> > resolves C++/PR115030 without complex calculations for specialised args. It
> > also enhances the consistency of tsubst behaviour by not leaving constraints
> > un-substituted. However, these changes make args in constraints_satisfied_p
> > (being called from do_auto_deduction) a bit misleading, as it will not carry
> > the actual args of the constraint and can even be an empty vec.
> >
> > I have added a testsuite for C++/PR115030, and as far as I have tested (only
> > c++ dg.exp on x86_64-linux), there are no regressions.
> >
> > Extra:
> > While doing this, I also realised that the hash function in ctp_hasher (for
> > canonical type of template parameters) slightly differs from its equality
> > function. Specifically, the equality function uses comptypes (typeck.cc) (with
> > COMPARE_STRUCTURAL) and compares placeholder constraints (typeck.cc:1586),
> > while the hash function ignores them (pt.cc:4528). As a result, we can have two
> > types with equal hashes that are unequal. For example, assuming:
> >
> > template <typename T, typename U>
> > concept C1 = ...
> >
> > template <typename T, typename U>
> > concept C2 = ...
> >
> >
> > "C1<U> auto" and "C2<V> auto" have the same hash value but are unequal. This
> > issue does not cause any error (it is a hash collision and it is handled), but
> > it can be avoided by using hash_placeholder_constraint (constraint.cc:1150).
> >
> > Therefore, I have made the following changes:
> > - Fixed the hash function to calculate the hash of the constraint (pt.cc:4528).
> > - Slightly modified the existing hash_placeholder_constraint
> > (constraint.cc:1150) to accept the initial hash value as an argument.
> >
> > Details of these changes can be found in the patch "[PATCH v1] c++: Hash
> > placeholder constraint in ctp_hasher" that will be replied to this email.
> >
> > Thanks. I really appreciate your comments and feedback on these proposed
> > changes.
> 
>

On Tue, Jul 9, 2024 at 6:46 AM Seyed Sajad Kahani <sska1377@gmail.com> wrote:
>
> This patch addresses a difference between the hash function and the equality
> function for canonical types of template parameters (ctp_hasher). The equality
> function uses comptypes (typeck.cc) (with COMPARE_STRUCTURAL) and checks
> constraint equality for two auto nodes (typeck.cc:1586), while the hash
> function ignores it (pt.cc:4528). This leads to hash collisions that can be
> avoided by using `hash_placeholder_constraint` (constraint.cc:1150).

By the way your mailer looks to have mangled the patch by removing white spaces.

Thanks,
Andrew

>
> * constraint.cc (hash_placeholder_constraint): Rename to
> iterative_hash_placeholder_constraint.
> (iterative_hash_placeholder_constraint): Rename from
> hash_placeholder_constraint and add the initial val argument.
> * cp-tree.h (hash_placeholder_constraint): Rename to
> iterative_hash_placeholder_constraint.
> (iterative_hash_placeholder_constraint): Renamed from
> hash_placeholder_constraint and add the initial val argument.
> * pt.cc (struct ctp_hasher): Updated to use
> iterative_hash_placeholder_constraint in the case of a valid placeholder
> constraint.
> (auto_hash::hash): Reflect the renaming of hash_placeholder_constraint to
> iterative_hash_placeholder_constraint.
> ---
> gcc/cp/constraint.cc | 4 ++--
> gcc/cp/cp-tree.h | 2 +-
> gcc/cp/pt.cc | 9 +++++++--
> 3 files changed, 10 insertions(+), 5 deletions(-)
>
> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> index ebf4255e5..78aacb77a 100644
> --- a/gcc/cp/constraint.cc
> +++ b/gcc/cp/constraint.cc
> @@ -1971,13 +1971,13 @@ equivalent_placeholder_constraints (tree c1, tree c2)
> /* Return a hash value for the placeholder ATOMIC_CONSTR C. */
> hashval_t
> -hash_placeholder_constraint (tree c)
> +iterative_hash_placeholder_constraint (tree c, hashval_t val)
> {
> 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);
> + val = iterative_hash_object (DECL_UID (t), val);
> for (int i = TREE_VEC_LENGTH (a)-1; i > 0; --i)
> val = iterative_hash_template_arg (TREE_VEC_ELT (a, i), val);
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index 4bb3e9c49..294e88f75 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -8588,7 +8588,7 @@ extern tree_pair finish_type_constraints (tree,
> tree, tsubst_flags_t);
> extern tree build_constrained_parameter (tree, tree, tree = NULL_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 hashval_t iterative_hash_placeholder_constraint (tree, hashval_t);
> 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/pt.cc b/gcc/cp/pt.cc
> index d1316483e..9a80c44a5 100644
> --- a/gcc/cp/pt.cc
> +++ b/gcc/cp/pt.cc
> @@ -4525,7 +4525,12 @@ struct ctp_hasher : ggc_ptr_hash<tree_node>
> val = iterative_hash_object (TEMPLATE_TYPE_LEVEL (t), val);
> val = iterative_hash_object (TEMPLATE_TYPE_IDX (t), val);
> if (TREE_CODE (t) == TEMPLATE_TYPE_PARM)
> - val = iterative_hash_template_arg (CLASS_PLACEHOLDER_TEMPLATE (t), val);
> + {
> + val
> + = iterative_hash_template_arg (CLASS_PLACEHOLDER_TEMPLATE (t), val);
> + if (tree c = NON_ERROR (PLACEHOLDER_TYPE_CONSTRAINTS (t)))
> + val = iterative_hash_placeholder_constraint(c, val);
> + }
> if (TREE_CODE (t) == BOUND_TEMPLATE_TEMPLATE_PARM)
> val = iterative_hash_template_arg (TYPE_TI_ARGS (t), val);
> --comparing_specializations;
> @@ -29605,7 +29610,7 @@ auto_hash::hash (tree t)
> if (tree c = NON_ERROR (PLACEHOLDER_TYPE_CONSTRAINTS (t)))
> /* Matching constrained-type-specifiers denote the same template
> parameter, so hash the constraint. */
> - return hash_placeholder_constraint (c);
> + return iterative_hash_placeholder_constraint (c, 0);
> else
> /* But unconstrained autos are all separate, so just hash the pointer. */
> return iterative_hash_object (t, 0);
> --
> 2.45.2
>
> On Tue, 9 Jul 2024 at 14:41, Seyed Sajad Kahani <sska1377@gmail.com> wrote:
> >
> > Hi.
> >
> > While investigating a fix for C++/PR115030 (a bug in constrained auto
> > deduction), I was wondering why we are not substituting constraint args of an
> > auto node in tsubst (pt.cc:16533). Instead, this substitution is delayed until
> > do_auto_deduction (pt.cc), where we attempt to find the substituted args of the
> > enclosing scope. At that point, it becomes difficult to find partially
> > specialised args, as they are erased in the process. I propose modifying tsubst
> > to eagerly substitute the constraint args of an auto node.
> >
> > By making this change, we would not need to provide outer_targs for
> > do_auto_deduction in cases where tsubst has been called for the type, which
> > covers most scenarios. However, we still need outer_targs for cases like:
> >
> > template <typename T, C<T> auto V>
> > struct S { };
> >
> > Hence, outer_targs cannot be completely removed but will be set to TREE_NULL in
> > all calls except the one in convert_template_argument (pt.cc:8788).
> > Additionally, the tmpl argument of do_auto_deduction, which helps to provide
> > outer args in the scope, will no longer be necessary and can be safely
> > removed.
> >
> > Also, the trimming hack proposed in
> > https://gcc.gnu.org/pipermail/gcc-patches/2024-June/654724.html to address
> > C++/PR114915 is no longer needed. We will add an assertion to ensure that the
> > missing levels do not become negative.
> >
> > Substituting constraint arguments earlier will slightly alter error messages
> > (see testsuite/g++.dg/cpp2a/concepts-placeholder3.C as an example).
> >
> > To summarise, I have made the following changes:
> > - Modified tsubst to substitute the constraint args.
> > - Fixed shallow checks for using the cache from TEMPLATE_TYPE_DESCENDANTS
> > (pt.cc:16513).
> > - Substituted the constraint args and the auto node itself, while retaining all
> > other parameters as is (pt.cc:16533).
> > - Removed now unnecessary code that attempted to find outer scope template info
> > and args in various locations.
> > - Updated the missing levels hack (pt.cc:31320) to work with the substituted
> > constraints.
> > - Used level instead of orig_level to find the missing levels.
> > - Added an assertion for future safety.
> >
> > Details of these changes can be found in the patch "[PATCH v1] c++: Eagerly
> > substitute auto constraint args in tsubst [PR115030]" that will be replied to
> > this thread.
> >
> > This patch, in my opinion, improves code quality by removing an argument from
> > do_auto_deduction and eliminating the out-of-scope task of finding outer_targs
> > within do_auto_deduction. It simplifies the usage of do_auto_deduction and
> > resolves C++/PR115030 without complex calculations for specialised args. It
> > also enhances the consistency of tsubst behaviour by not leaving constraints
> > un-substituted. However, these changes make args in constraints_satisfied_p
> > (being called from do_auto_deduction) a bit misleading, as it will not carry
> > the actual args of the constraint and can even be an empty vec.
> >
> > I have added a testsuite for C++/PR115030, and as far as I have tested (only
> > c++ dg.exp on x86_64-linux), there are no regressions.
> >
> > Extra:
> > While doing this, I also realised that the hash function in ctp_hasher (for
> > canonical type of template parameters) slightly differs from its equality
> > function. Specifically, the equality function uses comptypes (typeck.cc) (with
> > COMPARE_STRUCTURAL) and compares placeholder constraints (typeck.cc:1586),
> > while the hash function ignores them (pt.cc:4528). As a result, we can have two
> > types with equal hashes that are unequal. For example, assuming:
> >
> > template <typename T, typename U>
> > concept C1 = ...
> >
> > template <typename T, typename U>
> > concept C2 = ...
> >
> >
> > "C1<U> auto" and "C2<V> auto" have the same hash value but are unequal. This
> > issue does not cause any error (it is a hash collision and it is handled), but
> > it can be avoided by using hash_placeholder_constraint (constraint.cc:1150).
> >
> > Therefore, I have made the following changes:
> > - Fixed the hash function to calculate the hash of the constraint (pt.cc:4528).
> > - Slightly modified the existing hash_placeholder_constraint
> > (constraint.cc:1150) to accept the initial hash value as an argument.
> >
> > Details of these changes can be found in the patch "[PATCH v1] c++: Hash
> > placeholder constraint in ctp_hasher" that will be replied to this email.
> >
> > Thanks. I really appreciate your comments and feedback on these proposed
> > changes.