Re: [PATCH v1] c++: Hash placeholder constraint in ctp_hasher
On Tue, 16 Jul 2024 at 17:05, Jason Merrill 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
> > 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.
Re: [PATCH v1] c++: Hash placeholder constraint in ctp_hasher
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
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
Re: [PATCH v1] c++: Hash placeholder constraint in ctp_hasher
I am sorry for the inconvenience, a fixed version was sent just now.
[PATCH 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(-)
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
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
Re: [PATCH v1] c++: Hash placeholder constraint in ctp_hasher
oint, 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 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
> > concept C1 = ...
> >
> > template
> > concept C2 = ...
> >
> >
> > "C1 auto" and "C2 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.
Re: [PATCH v1] c++: Hash placeholder constraint in ctp_hasher
tion (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 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
> > concept C1 = ...
> >
> > template
> > concept C2 = ...
> >
> >
> > "C1 auto" and "C2 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.
>
>
[PATCH v1] c++: Hash placeholder constraint in ctp_hasher
ally, 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 > concept C1 = ... > > template > concept C2 = ... > > > "C1 auto" and "C2 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.
