On Thu, 10 Dec 2020, Patrick Palka wrote:
> On Thu, 10 Dec 2020, Jason Merrill wrote:
>
> > On 12/10/20 11:21 AM, Patrick Palka wrote:
> > > This implements lightweight heuristical detection and diagnosing of
> > > satisfaction results that change at different points in the program,
> > > which renders the program as ill-formed NDR as of P2014. We've recently
> > > started to more aggressively cache satisfaction results, and so the goal
> > > here is to make this caching behavior more transparent to users.
> > >
> > > A satisfaction result is flagged as "potentially unstable" (at the atom
> > > granularity) if during its computation, some type completion failure
> > > occurs. This is detected by making complete_type_or_maybe_complain
> > > increment a counter upon failure and comparing the value of the counter
> > > before and after satisfaction. (We don't instrument complete_type
> > > directly because it's used "opportunistically" in many spots where type
> > > completion failure doesn't necessary lead to substitution failure.)
> > >
> > > Flagged satisfaction results are always recomputed from scratch, even
> > > when performing satisfaction quietly. We then compare the recomputed
> > > result with the cached result, and if they differ, proceed with
> > > diagnosing the instability. (We may also unflag a result if it turned
> > > out to be independent of the previously detected type completion
> > > failure.) When performing satisfaction noisily, we always check
> > > instability.
> > >
> > > Most of the implementation is confined to the satisfaction_cache class,
> > > which has been completely rewritten.
> > >
> > > Bootstrapped and regtested on x86_64-pc-linux-gnu, and also tested on
> > > cmcstl2 and range-v3. The static_assert failures in the view.join test
> > > from cmcstl2 are now elaborated on after this patch, and additionally
> > > the alg.equal_range test now fails for the same reason as the view.join
> > > test.
> > >
> > > gcc/cp/ChangeLog:
> > >
> > > * constraint.cc (failed_type_completion_count): New.
> > > (note_failed_type_completion_for_satisfaction): New.
> > > (sat_entry::constr): Rename to ...
> > > (sat_entry::atom): ... this.
> > > (sat_entry::location): New member.
> > > (sat_entry::maybe_unstable): New member.
> > > (sat_entry::diagnose_instability): New member.
> > > (struct sat_hasher): Adjust after the above renaming.
> > > (get_satisfaction, save_satisfaction): Remove.
> > > (satisfaction_cache): Rewrite completely.
> > > (satisfy_atom): When instantiation of the parameter mapping
> > > fails, set diagnose_instability. Propagate location from
> > > inst_cache.entry to cache.entry if the secondary lookup
> > > succeeded.
> > > (satisfy_declaration_constraints): When
> > > failed_type_completion_count differs before and after
> > > satisfaction, then don't cache the satisfaction result.
> > > * cp-tree.h (note_failed_type_completion_for_satisfaction):
> > > Declare.
> > > * pt.c (tsubst) <case TYPENAME_TYPE>: Use
> > > complete_type_or_maybe_complain instead of open-coding it.
> > > * typeck.c (complete_type_or_maybe_complain): Call
> > > note_failed_type_completion_for_satisfaction when type
> > > completion fails.
> > >
> > > gcc/testsuite/ChangeLog:
> > >
> > > * g++.dg/cpp2a/concepts-complete1.C: New test.
> > > * g++.dg/cpp2a/concepts-complete2.C: New test.
> > > * g++.dg/cpp2a/concepts-complete3.C: New test.
> > > ---
> > > gcc/cp/constraint.cc | 283 ++++++++++++++----
> > > gcc/cp/cp-tree.h | 2 +
> > > gcc/cp/pt.c | 9 +-
> > > gcc/cp/typeck.c | 1 +
> > > .../g++.dg/cpp2a/concepts-complete1.C | 18 ++
> > > .../g++.dg/cpp2a/concepts-complete2.C | 23 ++
> > > .../g++.dg/cpp2a/concepts-complete3.C | 16 +
> > > 7 files changed, 282 insertions(+), 70 deletions(-)
> > > create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-complete1.C
> > > create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-complete2.C
> > > create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-complete3.C
> > >
> > > diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> > > index 73c038e3afe..ee702b34d01 100644
> > > --- a/gcc/cp/constraint.cc
> > > +++ b/gcc/cp/constraint.cc
> > > @@ -2374,35 +2374,82 @@ tsubst_parameter_mapping (tree map, tree args,
> > > tsubst_flags_t complain, tree in_
> > > Constraint satisfaction
> > >
> > > ---------------------------------------------------------------------------*/
> > > -/* Hash functions for satisfaction entries. */
> > > +/* A counter incremented by
> > > note_failed_type_completion_for_satisfaction().
> > > + It's used by the satisfaction caches in order to flag "potentially
> > > unstable"
> > > + satisfaction results. */
> > > +
> > > +static unsigned failed_type_completion_count;
> > > +
> > > +/* Called whenever a type completion failure occurs that definitely
> > > affects
> > > + the semantics of the program, by e.g. inducing substitution failure.
> > > */
> > > +
> > > +void
> > > +note_failed_type_completion_for_satisfaction (tree type)
> > > +{
> > > + gcc_checking_assert (!COMPLETE_TYPE_P (type));
> > > + if (CLASS_TYPE_P (type)
> > > + && CLASSTYPE_TEMPLATE_INSTANTIATION (type))
> > > + /* After instantiation, an incomplete class template specialization
> > > + will always be incomplete, so we don't increment the counter in
> > > this
> > > + case. */;
> >
> > Hmm? If a class template is declared early in the TU and defined later, a
> > later attempt will succeed in instantiating it.
>
> But shouldn't the result of the first instantiation, the one that yields
> an incomplete class type, prevail for the entire TU? At least, that's
> how I understand [temp.inst]/1 and [temp.point]/7.
Oops, I meant to refer to [temp.inst]/2 here instead. In particular,
the sentences
from [temp.inst]/2:
If a class template has been declared, but not defined, at the point
of instantiation, the instantiation yields an incomplete class type.
from [temp.point]/7:
A specialization for a class template has at most one point of
instantiation within a translation unit.
together seem to imply it's impossible to complete a class template
specialization after an earlier instantiation yielded an incomplete
type, for then there would be two different points of instantiation
for the same specialization.
>
> FWIW, this "optimization" was added in order to avoid a significant
> performance regression in cmcstl's view.take testcase, which ends up
> frequently checking an unsatisfiable atom that wants completeness of
> std::tuple_size<T>.
>
> >
> > > + else
> > > + ++failed_type_completion_count;
> > > +}
> > > +
> > > +/* Hash functions and data types for satisfaction cache entries. */
> > > struct GTY((for_user)) sat_entry
> > > {
> > > - tree constr;
> > > + /* The relevant ATOMIC_CONSTR. */
> > > + tree atom;
> > > +
> > > + /* The relevant template arguments. */
> > > tree args;
> > > +
> > > + /* The result of satisfaction of ATOM+ARGS.
> > > + This is either boolean_true_node, boolean_false_node or
> > > error_mark_node,
> > > + where error_mark_node indicates ill-formed satisfaction.
> > > + It's set to NULL_TREE while computing satisfaction of ATOM+ARGS for
> > > + the first time. */
> > > tree result;
> > > +
> > > + /* The value of input_location when satisfaction of ATOM+ARGS was first
> > > + performed. */
> > > + location_t location;
> > > +
> > > + /* True if this satisfaction result is flagged as "potentially
> > > unstable",
> > > + i.e. the result might change at different points in the program if
> > > + recomputed from scratch (which would be UB). This flag is used to
> > > + heuristically diagnose such UB when it occurs, by recomputing this
> > > + satisfaction from scratch even when evaluating quietly. */
> > > + bool maybe_unstable;
> > > +
> > > + /* True if we want to diagnose the above instability when it's
> > > detected.
> > > + We don't always want to do so, in order to avoid emitting duplicate
> > > + diagnostics in some cases. */
> > > + bool diagnose_instability;
> > > };
> > > struct sat_hasher : ggc_ptr_hash<sat_entry>
> > > {
> > > static hashval_t hash (sat_entry *e)
> > > {
> > > - if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e->constr))
> > > + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e->atom))
> > > {
> > > /* Atoms with instantiated mappings are built during
> > > satisfaction.
> > > They live only inside the sat_cache, and we build one to
> > > query
> > > the cache with each time we instantiate a mapping. */
> > > gcc_assert (!e->args);
> > > - return hash_atomic_constraint (e->constr);
> > > + return hash_atomic_constraint (e->atom);
> > > }
> > > /* Atoms with uninstantiated mappings are built during
> > > normalization.
> > > Since normalize_atom caches the atoms it returns, we can assume
> > > pointer-based identity for fast hashing and comparison. Even if
> > > this
> > > assumption is violated, that's okay, we'll just get a cache miss.
> > > */
> > > - hashval_t value = htab_hash_pointer (e->constr);
> > > + hashval_t value = htab_hash_pointer (e->atom);
> > > - if (tree map = ATOMIC_CONSTR_MAP (e->constr))
> > > + if (tree map = ATOMIC_CONSTR_MAP (e->atom))
> > > /* Only the parameters that are used in the targets of the mapping
> > > affect the satisfaction value of the atom. So we consider only
> > > the arguments for these parameters, and ignore the rest. */
> > > @@ -2425,21 +2472,21 @@ struct sat_hasher : ggc_ptr_hash<sat_entry>
> > > static bool equal (sat_entry *e1, sat_entry *e2)
> > > {
> > > - if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->constr)
> > > - != ATOMIC_CONSTR_MAP_INSTANTIATED_P (e2->constr))
> > > + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom)
> > > + != ATOMIC_CONSTR_MAP_INSTANTIATED_P (e2->atom))
> > > return false;
> > > /* See sat_hasher::hash. */
> > > - if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->constr))
> > > + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom))
> > > {
> > > gcc_assert (!e1->args && !e2->args);
> > > - return atomic_constraints_identical_p (e1->constr, e2->constr);
> > > + return atomic_constraints_identical_p (e1->atom, e2->atom);
> > > }
> > > - if (e1->constr != e2->constr)
> > > + if (e1->atom != e2->atom)
> > > return false;
> > > - if (tree map = ATOMIC_CONSTR_MAP (e1->constr))
> > > + if (tree map = ATOMIC_CONSTR_MAP (e1->atom))
> > > for (tree target_parms = TREE_TYPE (map);
> > > target_parms;
> > > target_parms = TREE_CHAIN (target_parms))
> > > @@ -2467,59 +2514,146 @@ static GTY((deletable)) hash_table<sat_hasher>
> > > *sat_cache;
> > > /* Cache the result of constraint_satisfaction_value. */
> > > static GTY((deletable)) hash_map<tree, tree> *decl_satisfied_cache;
> > > -static tree
> > > -get_satisfaction (tree constr, tree args)
> > > -{
> > > - if (!sat_cache)
> > > - return NULL_TREE;
> > > - sat_entry elt = { constr, args, NULL_TREE };
> > > - sat_entry* found = sat_cache->find (&elt);
> > > - if (found)
> > > - return found->result;
> > > - else
> > > - return NULL_TREE;
> > > -}
> > > -
> > > -static void
> > > -save_satisfaction (tree constr, tree args, tree result)
> > > -{
> > > - if (!sat_cache)
> > > - sat_cache = hash_table<sat_hasher>::create_ggc (31);
> > > - sat_entry elt = {constr, args, result};
> > > - sat_entry** slot = sat_cache->find_slot (&elt, INSERT);
> > > - sat_entry* entry = ggc_alloc<sat_entry> ();
> > > - *entry = elt;
> > > - *slot = entry;
> > > -}
> > > -
> > > -/* A tool to help manage satisfaction caching in satisfy_constraint_r.
> > > - Note the cache is only used when not diagnosing errors. */
> > > +/* A tool used by satisfy_atom to help manage satisfaction caching and to
> > > + diagnose "unstable" satisfaction values. We insert into the cache
> > > only
> > > + when performing satisfaction quietly. */
> > > struct satisfaction_cache
> > > {
> > > - satisfaction_cache (tree constr, tree args, tsubst_flags_t complain)
> > > - : constr(constr), args(args), complain(complain)
> > > - { }
> > > + satisfaction_cache (tree, tree, sat_info);
> > > + tree get ();
> > > + tree save (tree);
> > > - tree get ()
> > > - {
> > > - if (complain == tf_none)
> > > - return get_satisfaction (constr, args);
> > > - return NULL_TREE;
> > > - }
> > > -
> > > - tree save (tree result)
> > > - {
> > > - if (complain == tf_none)
> > > - save_satisfaction (constr, args, result);
> > > - return result;
> > > - }
> > > -
> > > - tree constr;
> > > - tree args;
> > > - tsubst_flags_t complain;
> > > + sat_entry *entry;
> > > + sat_info info;
> > > + unsigned ftc_count;
> > > };
> > > +/* Constructor for the satisfaction_cache class. We're performing
> > > satisfaction
> > > + of ATOM+ARGS according to INFO. */
> > > +
> > > +satisfaction_cache
> > > +::satisfaction_cache (tree atom, tree args, sat_info info)
> > > + : entry(nullptr), info(info), ftc_count(failed_type_completion_count)
> > > +{
> > > + if (!sat_cache)
> > > + sat_cache = hash_table<sat_hasher>::create_ggc (31);
> > > +
> > > + /* When noisy, we query the satisfaction cache in order to diagnose
> > > + "unstable" satisfaction values. */
> > > + if (info.noisy ())
> > > + {
> > > + /* When noisy, constraints have been re-normalized, and that breaks
> > > the
> > > + pointer-based identity assumption of sat_cache (for atoms with
> > > + uninstantiated mappings). So undo this re-normalization by looking
> > > in
> > > + the atom_cache for the corresponding atom that was used during quiet
> > > + satisfaction. */
> > > + if (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom))
> > > + {
> > > + if (tree found = atom_cache->find (atom))
> > > + atom = found;
> > > + else
> > > + /* The lookup should always succeed, but if it fails then let's
> > > + just leave 'entry' empty, effectively disabling the cache. */
> > > + return;
> > > + }
> > > + }
> > > +
> > > + /* Look up or create the corresponding satisfaction entry. */
> > > + sat_entry elt;
> > > + elt.atom = atom;
> > > + elt.args = args;
> > > + sat_entry **slot = sat_cache->find_slot (&elt, INSERT);
> > > + if (*slot)
> > > + entry = *slot;
> > > + else if (info.quiet ())
> > > + {
> > > + entry = ggc_alloc<sat_entry> ();
> > > + entry->atom = atom;
> > > + entry->args = args;
> > > + entry->result = NULL_TREE;
> > > + entry->location = input_location;
> > > + entry->maybe_unstable = false;
> > > + entry->diagnose_instability = false;
> > > + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom))
> > > + /* We always want to diagnose instability of an atom with an
> > > + instantiated parameter mapping. For atoms with an uninstiantiated
> >
> > Extra 'i' in "uninstantiated"
>
> Fixed, as well as applied David's suggestion to use
> auto_diagnostic_group. Here's an updated patch which improves some
> comments too, no functional changes:
>
> -- >8 --
>
> Subject: [PATCH] c++: Diagnose unstable satisfaction
>
> This implements lightweight heuristical detection and diagnosing of
> satisfaction whose result changes at different points in the program,
> which renders the program ill-formed NDR as of P2104. We've recently
> started to more aggressively cache satisfaction results, and so the goal
> with this patch is to make this caching behavior more transparent to
> the user.
>
> A satisfaction result is flagged as "potentially unstable" (at the atom
> granularity) if during its computation, some type completion failure
> occurs. This is detected by making complete_type_or_maybe_complain
> increment a counter upon failure and comparing the value of the counter
> before and after satisfaction. (We don't instrument complete_type
> directly because it's used "opportunistically" in many spots where type
> completion failure doesn't necessary lead to substitution failure.)
>
> Such flagged satisfaction results are always recomputed from scratch,
> even when performing satisfaction quietly. When saving a satisfaction
> result, we now compare the computed result with the cached result, and
> if they differ, proceed with diagnosing the instability.
>
> Most of the implementation is confined to the satisfaction_cache class,
> which has been completely rewritten.
>
> Bootstrapped and regtested on x86_64-pc-linux-gnu, and also tested on
> cmcstl2 and range-v3. The static_assert failures in the view.join test
> from cmcstl2 are now elaborated on after this patch, and additionally
> the alg.equal_range test now fails for the same reason as the view.join
> test.
>
> gcc/cp/ChangeLog:
>
> * constraint.cc (failed_type_completion_count): New.
> (note_failed_type_completion_for_satisfaction): New.
> (sat_entry::constr): Rename to ...
> (sat_entry::atom): ... this.
> (sat_entry::location): New member.
> (sat_entry::maybe_unstable): New member.
> (sat_entry::diagnose_instability): New member.
> (struct sat_hasher): Adjust after the above renaming.
> (get_satisfaction, save_satisfaction): Remove.
> (satisfaction_cache): Rewrite completely.
> (satisfy_atom): When instantiation of the parameter mapping
> fails, set diagnose_instability. Propagate location from
> inst_cache.entry to cache.entry if the secondary lookup
> succeeded.
> (satisfy_declaration_constraints): When
> failed_type_completion_count differs before and after
> satisfaction, then don't cache the satisfaction result.
> * cp-tree.h (note_failed_type_completion_for_satisfaction):
> Declare.
> * pt.c (tsubst) <case TYPENAME_TYPE>: Use
> complete_type_or_maybe_complain instead of open-coding it.
> * typeck.c (complete_type_or_maybe_complain): Call
> note_failed_type_completion_for_satisfaction when type
> completion fails.
>
> gcc/testsuite/ChangeLog:
>
> * g++.dg/cpp2a/concepts-complete1.C: New test.
> * g++.dg/cpp2a/concepts-complete2.C: New test.
> * g++.dg/cpp2a/concepts-complete3.C: New test.
> ---
> gcc/cp/constraint.cc | 283 ++++++++++++++----
> gcc/cp/cp-tree.h | 2 +
> gcc/cp/pt.c | 9 +-
> gcc/cp/typeck.c | 1 +
> .../g++.dg/cpp2a/concepts-complete1.C | 18 ++
> .../g++.dg/cpp2a/concepts-complete2.C | 23 ++
> .../g++.dg/cpp2a/concepts-complete3.C | 16 +
> 7 files changed, 282 insertions(+), 70 deletions(-)
> create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-complete1.C
> create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-complete2.C
> create mode 100644 gcc/testsuite/g++.dg/cpp2a/concepts-complete3.C
>
> diff --git a/gcc/cp/constraint.cc b/gcc/cp/constraint.cc
> index 73c038e3afe..b98befaf71b 100644
> --- a/gcc/cp/constraint.cc
> +++ b/gcc/cp/constraint.cc
> @@ -2374,35 +2374,82 @@ tsubst_parameter_mapping (tree map, tree args,
> tsubst_flags_t complain, tree in_
> Constraint satisfaction
> ---------------------------------------------------------------------------*/
>
> -/* Hash functions for satisfaction entries. */
> +/* A counter incremented by note_failed_type_completion_for_satisfaction().
> + It's used by the satisfaction caches in order to flag "potentially
> unstable"
> + satisfaction results. */
> +
> +static unsigned failed_type_completion_count;
> +
> +/* Called whenever a type completion failure occurs that definitely affects
> + the semantics of the program, by e.g. inducing substitution failure. */
> +
> +void
> +note_failed_type_completion_for_satisfaction (tree type)
> +{
> + gcc_checking_assert (!COMPLETE_TYPE_P (type));
> + if (CLASS_TYPE_P (type)
> + && CLASSTYPE_TEMPLATE_INSTANTIATION (type))
> + /* After instantiation, a class template specialization that's
> + incomplete will remain incomplete, so for our purposes we can
> + ignore this completion failure event. */;
> + else
> + ++failed_type_completion_count;
> +}
> +
> +/* Hash functions and data types for satisfaction cache entries. */
>
> struct GTY((for_user)) sat_entry
> {
> - tree constr;
> + /* The relevant ATOMIC_CONSTR. */
> + tree atom;
> +
> + /* The relevant template arguments. */
> tree args;
> +
> + /* The result of satisfaction of ATOM+ARGS.
> + This is either boolean_true_node, boolean_false_node or error_mark_node,
> + where error_mark_node indicates ill-formed satisfaction.
> + It's set to NULL_TREE while computing satisfaction of ATOM+ARGS for
> + the first time. */
> tree result;
> +
> + /* The value of input_location when satisfaction of ATOM+ARGS was first
> + performed. */
> + location_t location;
> +
> + /* True if this satisfaction result is flagged as "potentially unstable",
> + i.e. the result might change at different points in the program if
> + recomputed from scratch (which would be ill-formed). This flag controls
> + whether to recompute a cached satisfaction result from scratch even when
> + evaluating quietly. */
> + bool maybe_unstable;
> +
> + /* True if we want to diagnose the above instability when it's detected.
> + We don't always want to do so, in order to avoid emitting duplicate
> + diagnostics in some cases. */
> + bool diagnose_instability;
> };
>
> struct sat_hasher : ggc_ptr_hash<sat_entry>
> {
> static hashval_t hash (sat_entry *e)
> {
> - if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e->constr))
> + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e->atom))
> {
> /* Atoms with instantiated mappings are built during satisfaction.
> They live only inside the sat_cache, and we build one to query
> the cache with each time we instantiate a mapping. */
> gcc_assert (!e->args);
> - return hash_atomic_constraint (e->constr);
> + return hash_atomic_constraint (e->atom);
> }
>
> /* Atoms with uninstantiated mappings are built during normalization.
> Since normalize_atom caches the atoms it returns, we can assume
> pointer-based identity for fast hashing and comparison. Even if this
> assumption is violated, that's okay, we'll just get a cache miss. */
> - hashval_t value = htab_hash_pointer (e->constr);
> + hashval_t value = htab_hash_pointer (e->atom);
>
> - if (tree map = ATOMIC_CONSTR_MAP (e->constr))
> + if (tree map = ATOMIC_CONSTR_MAP (e->atom))
> /* Only the parameters that are used in the targets of the mapping
> affect the satisfaction value of the atom. So we consider only
> the arguments for these parameters, and ignore the rest. */
> @@ -2425,21 +2472,21 @@ struct sat_hasher : ggc_ptr_hash<sat_entry>
>
> static bool equal (sat_entry *e1, sat_entry *e2)
> {
> - if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->constr)
> - != ATOMIC_CONSTR_MAP_INSTANTIATED_P (e2->constr))
> + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom)
> + != ATOMIC_CONSTR_MAP_INSTANTIATED_P (e2->atom))
> return false;
>
> /* See sat_hasher::hash. */
> - if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->constr))
> + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (e1->atom))
> {
> gcc_assert (!e1->args && !e2->args);
> - return atomic_constraints_identical_p (e1->constr, e2->constr);
> + return atomic_constraints_identical_p (e1->atom, e2->atom);
> }
>
> - if (e1->constr != e2->constr)
> + if (e1->atom != e2->atom)
> return false;
>
> - if (tree map = ATOMIC_CONSTR_MAP (e1->constr))
> + if (tree map = ATOMIC_CONSTR_MAP (e1->atom))
> for (tree target_parms = TREE_TYPE (map);
> target_parms;
> target_parms = TREE_CHAIN (target_parms))
> @@ -2467,59 +2514,146 @@ static GTY((deletable)) hash_table<sat_hasher>
> *sat_cache;
> /* Cache the result of constraint_satisfaction_value. */
> static GTY((deletable)) hash_map<tree, tree> *decl_satisfied_cache;
>
> -static tree
> -get_satisfaction (tree constr, tree args)
> -{
> - if (!sat_cache)
> - return NULL_TREE;
> - sat_entry elt = { constr, args, NULL_TREE };
> - sat_entry* found = sat_cache->find (&elt);
> - if (found)
> - return found->result;
> - else
> - return NULL_TREE;
> -}
> -
> -static void
> -save_satisfaction (tree constr, tree args, tree result)
> -{
> - if (!sat_cache)
> - sat_cache = hash_table<sat_hasher>::create_ggc (31);
> - sat_entry elt = {constr, args, result};
> - sat_entry** slot = sat_cache->find_slot (&elt, INSERT);
> - sat_entry* entry = ggc_alloc<sat_entry> ();
> - *entry = elt;
> - *slot = entry;
> -}
> -
> -/* A tool to help manage satisfaction caching in satisfy_constraint_r.
> - Note the cache is only used when not diagnosing errors. */
> +/* A tool used by satisfy_atom to help manage satisfaction caching and to
> + diagnose "unstable" satisfaction values. We insert into the cache only
> + when performing satisfaction quietly. */
>
> struct satisfaction_cache
> {
> - satisfaction_cache (tree constr, tree args, tsubst_flags_t complain)
> - : constr(constr), args(args), complain(complain)
> - { }
> + satisfaction_cache (tree, tree, sat_info);
> + tree get ();
> + tree save (tree);
>
> - tree get ()
> - {
> - if (complain == tf_none)
> - return get_satisfaction (constr, args);
> - return NULL_TREE;
> - }
> -
> - tree save (tree result)
> - {
> - if (complain == tf_none)
> - save_satisfaction (constr, args, result);
> - return result;
> - }
> -
> - tree constr;
> - tree args;
> - tsubst_flags_t complain;
> + sat_entry *entry;
> + sat_info info;
> + unsigned ftc_count;
> };
>
> +/* Constructor for the satisfaction_cache class. We're performing
> satisfaction
> + of ATOM+ARGS according to INFO. */
> +
> +satisfaction_cache
> +::satisfaction_cache (tree atom, tree args, sat_info info)
> + : entry(nullptr), info(info), ftc_count(failed_type_completion_count)
> +{
> + if (!sat_cache)
> + sat_cache = hash_table<sat_hasher>::create_ggc (31);
> +
> + /* When noisy, we query the satisfaction cache in order to diagnose
> + "unstable" satisfaction values. */
> + if (info.noisy ())
> + {
> + /* When noisy, constraints have been re-normalized, and that breaks the
> + pointer-based identity assumption of sat_cache (for atoms with
> + uninstantiated mappings). So undo this re-normalization by looking in
> + the atom_cache for the corresponding atom that was used during quiet
> + satisfaction. */
> + if (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom))
> + {
> + if (tree found = atom_cache->find (atom))
> + atom = found;
> + else
> + /* The lookup should always succeed, but if it fails then let's
> + just leave 'entry' empty, effectively disabling the cache. */
> + return;
> + }
> + }
> +
> + /* Look up or create the corresponding satisfaction entry. */
> + sat_entry elt;
> + elt.atom = atom;
> + elt.args = args;
> + sat_entry **slot = sat_cache->find_slot (&elt, INSERT);
> + if (*slot)
> + entry = *slot;
> + else if (info.quiet ())
> + {
> + entry = ggc_alloc<sat_entry> ();
> + entry->atom = atom;
> + entry->args = args;
> + entry->result = NULL_TREE;
> + entry->location = input_location;
> + entry->maybe_unstable = false;
> + entry->diagnose_instability = false;
> + if (ATOMIC_CONSTR_MAP_INSTANTIATED_P (atom))
> + /* We always want to diagnose instability of an atom with an
> + instantiated parameter mapping. For atoms with an uninstantiated
> + mapping, we set this flag (in satisfy_atom) only if substitution
> + into its mapping previously failed. */
> + entry->diagnose_instability = true;
> + *slot = entry;
> + }
> + else
> + /* We shouldn't get here, but if we do, let's just leave 'entry'
> + empty, effectively disabling the cache. */
> + return;
> +}
> +
> +/* Returns the cached satisfaction result if we have one and we're not
> + recomputing the satisfaction result from scratch. Otherwise returns
> + NULL_TREE. */
> +
> +tree
> +satisfaction_cache::get ()
> +{
> + if (!entry)
> + return NULL_TREE;
> +
> + if (info.noisy () || entry->maybe_unstable)
> + /* We're recomputing the satisfaction result from scratch. */
> + return NULL_TREE;
> + else
> + return entry->result;
> +}
> +
> +/* RESULT is the computed satisfaction result. If RESULT differs from the
> + previously cached result, this routine issues an appropriate error.
> + Otherwise, when evaluating quietly, updates the cache appropriately. */
> +
> +tree
> +satisfaction_cache::save (tree result)
> +{
> + if (!entry)
> + return result;
> +
> + if (entry->result && result != entry->result)
> + {
> + if (info.quiet ())
> + /* Return error_mark_node to force satisfaction to get replayed
> + noisily. */
> + return error_mark_node;
> + else
> + {
> + if (entry->diagnose_instability)
> + {
> + auto_diagnostic_group d;
> + error_at (EXPR_LOCATION (ATOMIC_CONSTR_EXPR (entry->atom)),
> + "satisfaction value of atomic constraint %qE changed "
> + "from %qE to %qE", entry->atom, entry->result, result);
> + inform (entry->location,
> + "satisfaction value first evaluated to %qE from here",
> + entry->result);
> + }
> + /* For sake of error recovery, allow this latest satisfaction result
> + to prevail. */
> + entry->result = result;
> + return result;
> + }
> + }
> +
> + if (info.quiet ())
> + {
> + entry->result = result;
> + /* We heuristically flag this satisfaction result as potentially
> unstable
> + iff during its computation, completion of a type failed. Note that
> + this may also clear the flag if the result turned out to be
> + independent of the previously detected type completion failure. */
> + entry->maybe_unstable = (ftc_count != failed_type_completion_count);
> + }
> +
> + return result;
> +}
> +
> static int satisfying_constraint = 0;
>
> /* Returns true if we are currently satisfying a constraint.
> @@ -2731,7 +2865,7 @@ static void diagnose_atomic_constraint (tree, tree,
> tree, subst_info);
> static tree
> satisfy_atom (tree t, tree args, sat_info info)
> {
> - satisfaction_cache cache (t, args, info.complain);
> + satisfaction_cache cache (t, args, info);
> if (tree r = cache.get ())
> return r;
>
> @@ -2751,6 +2885,11 @@ satisfy_atom (tree t, tree args, sat_info info)
> not satisfied. Replay the substitution. */
> if (info.diagnose_unsatisfaction_p ())
> tsubst_parameter_mapping (ATOMIC_CONSTR_MAP (t), args, info);
> + if (info.quiet ())
> + /* Since instantiation of the parameter mapping failed, we
> + want to diagnose potential instability of this satisfaction
> + result. */
> + cache.entry->diagnose_instability = true;
> return cache.save (boolean_false_node);
> }
>
> @@ -2762,9 +2901,12 @@ satisfy_atom (tree t, tree args, sat_info info)
> ATOMIC_CONSTR_MAP (t) = map;
> gcc_assert (!ATOMIC_CONSTR_MAP_INSTANTIATED_P (t));
> ATOMIC_CONSTR_MAP_INSTANTIATED_P (t) = true;
> - satisfaction_cache inst_cache (t, /*args=*/NULL_TREE, info.complain);
> + satisfaction_cache inst_cache (t, /*args=*/NULL_TREE, info);
> if (tree r = inst_cache.get ())
> - return cache.save (r);
> + {
> + cache.entry->location = inst_cache.entry->location;
> + return cache.save (r);
> + }
>
> /* Rebuild the argument vector from the parameter mapping. */
> args = get_mapped_args (map);
> @@ -2955,6 +3097,8 @@ satisfy_declaration_constraints (tree t, sat_info info)
> norm = normalize_nontemplate_requirements (t, info.noisy ());
> }
>
> + unsigned ftc_count = failed_type_completion_count;
> +
> tree result = boolean_true_node;
> if (norm)
> {
> @@ -2966,7 +3110,20 @@ satisfy_declaration_constraints (tree t, sat_info info)
> pop_tinst_level ();
> }
>
> - if (info.quiet ())
> + /* True if this satisfaction is (heuristically) potentially unstable, i.e.
> + if its result may depend on where in the program it was performed. */
> + bool maybe_unstable_satisfaction = false;
> +
> + if (ftc_count != failed_type_completion_count)
> + /* Type completion failure occurred during satisfaction. The
> satisfaction
> + result may (or may not) materially depend on the completeness of a
> type,
> + so we consider it potentially unstable. */
> + maybe_unstable_satisfaction = true;
> +
> + if (maybe_unstable_satisfaction)
> + /* Don't cache potentially unstable satisfaction, to allow satisfy_atom
> + to check the stability the next time around. */;
> + else if (info.quiet ())
> hash_map_safe_put<hm_ggc> (decl_satisfied_cache, saved_t, result);
>
> return result;
> diff --git a/gcc/cp/cp-tree.h b/gcc/cp/cp-tree.h
> index f59591aa865..209efd4b251 100644
> --- a/gcc/cp/cp-tree.h
> +++ b/gcc/cp/cp-tree.h
> @@ -8075,6 +8075,8 @@ extern hashval_t iterative_hash_constraint (tree,
> hashval_t);
> extern hashval_t hash_atomic_constraint (tree);
> extern void diagnose_constraints (location_t, tree, tree);
>
> +extern void note_failed_type_completion_for_satisfaction (tree);
> +
> /* A structural hasher for ATOMIC_CONSTRs. */
>
> struct atom_hasher : default_hash_traits<tree>
> diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
> index 2d3ab92dfd1..a2f1fdeb4f5 100644
> --- a/gcc/cp/pt.c
> +++ b/gcc/cp/pt.c
> @@ -15948,13 +15948,8 @@ tsubst (tree t, tree args, tsubst_flags_t complain,
> tree in_decl)
> But, such constructs have already been resolved by this
> point, so here CTX really should have complete type, unless
> it's a partial instantiation. */
> - ctx = complete_type (ctx);
> - if (!COMPLETE_TYPE_P (ctx))
> - {
> - if (complain & tf_error)
> - cxx_incomplete_type_error (NULL_TREE, ctx);
> - return error_mark_node;
> - }
> + if (!complete_type_or_maybe_complain (ctx, NULL_TREE, complain))
> + return error_mark_node;
> }
>
> f = make_typename_type (ctx, f, typename_type,
> diff --git a/gcc/cp/typeck.c b/gcc/cp/typeck.c
> index 267b284ea40..d961f719110 100644
> --- a/gcc/cp/typeck.c
> +++ b/gcc/cp/typeck.c
> @@ -154,6 +154,7 @@ complete_type_or_maybe_complain (tree type, tree value,
> tsubst_flags_t complain)
> {
> if (complain & tf_error)
> cxx_incomplete_type_diagnostic (value, type, DK_ERROR);
> + note_failed_type_completion_for_satisfaction (type);
> return NULL_TREE;
> }
> else
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-complete1.C
> b/gcc/testsuite/g++.dg/cpp2a/concepts-complete1.C
> new file mode 100644
> index 00000000000..e8487bf9c09
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-complete1.C
> @@ -0,0 +1,18 @@
> +// Verify we diagnose an unstable satisfaction result that depends on
> +// completeness of the type A below.
> +//
> +// { dg-do compile { target c++20 } }
> +
> +template <class T> concept has_mem_type = requires { typename T::type; };
> +// { dg-message "satisfaction of 'has_mem_type<T>' .with T = A." "" { target
> *-*-* } .-1 }
> +// { dg-error "satisfaction value of atomic constraint 'requires.typename
> T::type;. .with T = A.' changed from 'false' to 'true'" "" { target *-*-* }
> .-2 }
> +
> +template <has_mem_type T> int f () { return 0; }
> +template <class T> char f() { return 0; }
> +
> +struct A;
> +static_assert (sizeof (f<A>()) == 1); // { dg-message "first evaluated to
> 'false' from here" }
> +struct A { typedef int type; };
> +static_assert (sizeof (f<A>()) > 1); // { dg-error "assert" }
> +// { dg-message "required from here" "" { target *-*-* } .-1 }
> +static_assert (sizeof (f<A>()) > 1);
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-complete2.C
> b/gcc/testsuite/g++.dg/cpp2a/concepts-complete2.C
> new file mode 100644
> index 00000000000..b2c11606737
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-complete2.C
> @@ -0,0 +1,23 @@
> +// Verify we diagnose an unstable satisfaction result that depends on
> +// completeness of the type A below.
> +//
> +// Like in the previous test, here satisfaction also initially fails,
> +// but this time due to failed substitution into the atom's parameter
> mapping.
> +//
> +// { dg-do compile { target c++20 } }
> +
> +template <class T> concept valid_type = requires { typename T; };
> +// { dg-message "satisfaction of 'valid_type<typename T::type>' .with T =
> A." "" { target *-*-* } .-1 }
> +// { dg-error "satisfaction value of atomic constraint 'requires.T;. .with T
> = typename T::type.' changed from 'false' to 'true'" "" { target *-*-* } .-2 }
> +
> +template <class T> concept has_mem_type = valid_type<typename T::type>;
> +// { dg-message "satisfaction of 'has_mem_type<T>' .with T = A." "" { target
> *-*-* } .-1 }
> +
> +template <has_mem_type T> int f () { return 0; }
> +template <class T> char f() { return 0; }
> +
> +struct A;
> +static_assert (sizeof (f<A>()) == 1); // { dg-message "first evaluated to
> 'false' from here" }
> +struct A { typedef int type; };
> +static_assert (sizeof (f<A>()) > 1); // { dg-error "assert" }
> +static_assert (sizeof (f<A>()) > 1);
> diff --git a/gcc/testsuite/g++.dg/cpp2a/concepts-complete3.C
> b/gcc/testsuite/g++.dg/cpp2a/concepts-complete3.C
> new file mode 100644
> index 00000000000..5b07371a6be
> --- /dev/null
> +++ b/gcc/testsuite/g++.dg/cpp2a/concepts-complete3.C
> @@ -0,0 +1,16 @@
> +// Verify we diagnose an unstable satisfaction result that depends on
> +// return type deduction of the member function A::foo() below.
> +//
> +// { dg-do compile { target c++20 } }
> +
> +template <class T> concept fooable = requires (T t) { t.foo(); };
> +// { dg-error "'false' to 'true'" "" { target *-*-* } .-1 }
> +
> +template <fooable T> int f () { return 0; }
> +template <class T> char f() { return 0; }
> +
> +struct A { auto foo(); };
> +static_assert (sizeof (f<A>()) == 1); // { dg-message "first evaluated to
> 'false' from here" }
> +auto A::foo() { }
> +static_assert (sizeof (f<A>()) > 1); // { dg-error "assert" }
> +static_assert (sizeof (f<A>()) > 1);
> --
> 2.29.2.404.ge67fbf927d
>
>
