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. */;
+ 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
+ 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 != NULL_TREE
+ && 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)
+ {
+ 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 verify the instability 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
