On Fri, 11 Dec 2020, Jason Merrill wrote:
> On 12/11/20 10:31 AM, Patrick Palka wrote:
> > 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.
>
> Interesting. No implementation I know of shares this interpretation; existing
> practice is that subsequent potential points of instantiation will try again.
> For instance, this is accepted by g++, clang, EDG, and VC++:
>
> template <class T> struct A;
> struct B { };
>
> int f(...);
> int f(B*);
>
> A<int> *p;
>
> int i = f(p); // can't instantiate A<int>, calls f(...)
> template <class T> struct A: B { };
> int j = f(p); // instantiates A<int>, calls f(B*)
>
> So the compilers don't treat the first call as an actual point of
> instantiation for A<int>.
I see. I wonder if the standard could use some clarification here then,
perhaps [temp.point] could say "... has at most one point of
instantiation within a translate unit _that yields a complete type_"
or something like that.
> I'm curious how much code would break if we
> enforced your interpretation.
I ran a bootstrap and regtest with the following that prevents us from
attempting to instantiate an incomplete class template
specialization more than once:
-- >8 --
diff --git a/gcc/cp/pt.c b/gcc/cp/pt.c
index e5f18d23ea0..d1fe621e311 100644
--- a/gcc/cp/pt.c
+++ b/gcc/cp/pt.c
@@ -11704,6 +11704,8 @@ perform_instantiation_time_access_checks (tree tmpl,
tree targs)
}
}
+static GTY(()) hash_set<tree, false, tree_type_hash> *incomplete_at_poi;
+
static tree
instantiate_class_template_1 (tree type)
{
@@ -11717,8 +11719,12 @@ instantiate_class_template_1 (tree type)
if (type == error_mark_node)
return error_mark_node;
+ if (!incomplete_at_poi)
+ incomplete_at_poi = hash_set<tree, false, tree_type_hash>::create_ggc (31);
+
if (COMPLETE_OR_OPEN_TYPE_P (type)
- || uses_template_parms (type))
+ || uses_template_parms (type)
+ || incomplete_at_poi->contains (type))
return type;
/* Figure out which template is being instantiated. */
@@ -11764,6 +11770,7 @@ instantiate_class_template_1 (tree type)
{
/* We can try again later. */
TYPE_BEING_DEFINED (type) = 0;
+ incomplete_at_poi->add (type);
return type;
}
-- >8 --
and the only FAILs were excess incompleteness errors in the invalid
testcases template/nontype[45].C.
So far I noticed the patch breaks clang, because a couple of header
files use an incomplete class template specialization inside a function
declaration before later defining the class and using the function, e.g.
template <class> struct S;
void foo (S<int>);
...
// define S
...
// call foo()
I reckon this pattern is not uncommon in the wild..
So I guess this assumption in note_failed_type_completion_for_satisfaction
is unsound in practice, sadly. It was added to avoid a pretty big
compile time/memory use regression for the view.take cmcstl2 testcase,
due to a frequently used atom that checks for completeness of
std::tuple_size<T>, and is frequently applied to a non-tuple T, so we
end up recomputing, in vain, the corresponding cached satisfaction
result.
An earlier prototype of this patch kept precise track of the types for
which completion failed during satisfaction (as a pair of integer
offsets into a global failed_type_completions vector). And the
prototype recomputed the cached satisfaction result only when one of
these incomplete types became complete.
Later, for the sake of simplicity, I replaced this with the
failed_type_completion_count counter and the coarse-grained
sat_entry::maybe_unstable_p flag. But I will look into re-adding this
more fine-grained tracking since I think it should resolve the
performance regression.
>
> > > 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
> > >
> > >
> >
>
>
