diff mbox series

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

Message ID 20240712204230.303515-1-sska1377@gmail.com
State New
Headers
Series [v1] c++: Hash placeholder constraint in ctp_hasher |

Checks

Context Check Description
linaro-tcwg-bot/tcwg_gcc_build--master-arm success Build passed
linaro-tcwg-bot/tcwg_gcc_build--master-aarch64 success Build passed
linaro-tcwg-bot/tcwg_gcc_check--master-arm success Test passed
linaro-tcwg-bot/tcwg_gcc_check--master-aarch64 success Test passed

Commit Message

Seyed Sajad Kahani July 12, 2024, 8:42 p.m. UTC 
  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(-)

Comments

Seyed Sajad Kahani July 12, 2024, 8:44 p.m. UTC | #1 
I am sorry for the inconvenience, a fixed version was sent just now.
Jason Merrill July 16, 2024, 4:05 p.m. UTC | #2 
On 7/12/24 4:42 PM, 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).

The change looks good, just a couple of whitespace tweaks needed.  But 
what happened to the testcase?

> --- 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

Extra space at end of line.

> +	  = 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);

Missing space before paren.

Jason
Seyed Sajad Kahani July 17, 2024, 12:07 p.m. UTC | #3 
On Tue, 16 Jul 2024 at 17:05, Jason Merrill <jason@redhat.com> wrote:
> The change looks good, just a couple of whitespace tweaks needed.  But
> what happened to the testcase?

I was unable to design any testcase that differs by applying this
patch, due to the proper handling of hash collisions
(hash-table.h:1059).

> > --- 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
>
> Extra space at end of line.
>
> > +       = 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);
>
> Missing space before paren.

My apologies. Thank you for pointing those out.
diff mbox series

Patch

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);