This patch addresses testcase #1 by stopping name lookup returning
duplicates. We use TREE_VISITED (via LOOKUP_SEEN_P) on the underlying
decls of an overload. This is better than what we used to do, which
was either an O(N^2) search, or use of a hash table. Furthermore, we
take advantage of the sorted nature of overload bindings, and only enter
this deduplicating mode when we see an overload containing a USING
declaration.
Thus I revert the earlier change to most_specialized_instantiation,
putting an assert there. Coincidentally this patch fixes Markus' 5th
testcase.
nathan
--
Nathan Sidwell
2017-05-29 Nathan Sidwell <nat...@acm.org>
PR c++/80891 (#1,#5)
* cp-tree.h (lookup_maybe_add): Add DEDUPING argument.
* name-lookup.c (name_lookup): Add deduping field.
(name_lookup::preserve_state, name_lookup::restore_state): Deal
with deduping.
(name_lookup::add_overload): New.
(name_lookup::add_value, name_lookup::add_fns): Call add_overload.
(name_lookup::search_adl): Set deduping. Don't unmark here.
* pt.c (most_specialized_instantiation): Revert previous change,
Assert not given duplicates.
* tree.c (lookup_mark): Just mark the underlying decls.
(lookup_maybe_add): Dedup using marked decls.
PR c++/80891 (#5)
* g++.dg/lookup/pr80891-5.C: New.
Index: cp/cp-tree.h
===================================================================
--- cp/cp-tree.h (revision 248576)
+++ cp/cp-tree.h (working copy)
@@ -6916,7 +6916,8 @@ extern tree ovl_insert (tree fn, tree
extern tree ovl_skip_hidden (tree) ATTRIBUTE_PURE;
extern void lookup_mark (tree lookup, bool val);
extern tree lookup_add (tree fns, tree lookup);
-extern tree lookup_maybe_add (tree fns, tree lookup);
+extern tree lookup_maybe_add (tree fns, tree lookup,
+ bool deduping);
extern void lookup_keep (tree lookup, bool keep);
extern int is_overloaded_fn (tree) ATTRIBUTE_PURE;
extern bool really_overloaded_fn (tree) ATTRIBUTE_PURE;
Index: cp/name-lookup.c
===================================================================
--- cp/name-lookup.c (revision 248576)
+++ cp/name-lookup.c (working copy)
@@ -48,7 +48,11 @@ static void set_identifier_type_value_wi
#define MAYBE_STAT_DECL(N) (STAT_HACK_P (N) ? STAT_DECL (N) : N)
#define MAYBE_STAT_TYPE(N) (STAT_HACK_P (N) ? STAT_TYPE (N) : NULL_TREE)
-static tree stat_hack (tree decl = NULL_TREE, tree type = NULL_TREE)
+/* Create a STAT_HACK node with DECL as the value binding and TYPE as
+ the type binding. */
+
+static tree
+stat_hack (tree decl = NULL_TREE, tree type = NULL_TREE)
{
tree result = make_node (OVERLOAD);
@@ -179,6 +183,8 @@ public:
tree value; /* A (possibly ambiguous) set of things found. */
tree type; /* A type that has been found. */
int flags; /* Lookup flags. */
+ bool deduping; /* Full deduping is needed because using declarations
+ are in play. */
vec<tree, va_heap, vl_embed> *scopes;
name_lookup *previous; /* Previously active lookup. */
@@ -191,7 +197,7 @@ protected:
public:
name_lookup (tree n, int f = 0)
: name (n), value (NULL_TREE), type (NULL_TREE), flags (f),
- scopes (NULL), previous (NULL)
+ deduping (false), scopes (NULL), previous (NULL)
{
preserve_state ();
}
@@ -235,6 +241,7 @@ private:
private:
static tree ambiguous (tree thing, tree current);
+ void add_overload (tree fns);
void add_value (tree new_val);
void add_type (tree new_type);
bool process_binding (tree val_bind, tree type_bind);
@@ -321,7 +328,8 @@ name_lookup::preserve_state ()
}
/* Unmark the outer partial lookup. */
- lookup_mark (previous->value, false);
+ if (previous->deduping)
+ lookup_mark (previous->value, false);
}
else
scopes = shared_scopes;
@@ -333,6 +341,9 @@ name_lookup::preserve_state ()
void
name_lookup::restore_state ()
{
+ if (deduping)
+ lookup_mark (value, false);
+
/* Unmark and empty this lookup's scope stack. */
for (unsigned ix = vec_safe_length (scopes); ix--;)
{
@@ -371,7 +382,8 @@ name_lookup::restore_state ()
}
/* Remark the outer partial lookup. */
- lookup_mark (previous->value, true);
+ if (previous->deduping)
+ lookup_mark (previous->value, true);
}
else
shared_scopes = scopes;
@@ -415,12 +427,36 @@ name_lookup::ambiguous (tree thing, tree
return current;
}
+/* FNS is a new overload set to add to the exising set. */
+
+void
+name_lookup::add_overload (tree fns)
+{
+ if (!deduping && TREE_CODE (fns) == OVERLOAD)
+ {
+ tree probe = fns;
+ if (flags & LOOKUP_HIDDEN)
+ probe = ovl_skip_hidden (probe);
+ if (probe && TREE_CODE (probe) == OVERLOAD && OVL_USING_P (probe))
+ {
+ /* We're about to add something found by a using
+ declaration, so need to engage deduping mode. */
+ lookup_mark (value, true);
+ deduping = true;
+ }
+ }
+
+ value = lookup_maybe_add (fns, value, deduping);
+}
+
/* Add a NEW_VAL, a found value binding into the current value binding. */
void
name_lookup::add_value (tree new_val)
{
- if (!value)
+ if (OVL_P (new_val) && (!value || OVL_P (value)))
+ add_overload (new_val);
+ else if (!value)
value = new_val;
else if (value == new_val)
;
@@ -428,10 +464,16 @@ name_lookup::add_value (tree new_val)
&& TREE_CODE (new_val) == TYPE_DECL
&& same_type_p (TREE_TYPE (value), TREE_TYPE (new_val))))
;
- else if (OVL_P (value) && OVL_P (new_val))
- value = lookup_add (new_val, value);
else
- value = ambiguous (new_val, value);
+ {
+ if (deduping)
+ {
+ /* Disengage deduping mode. */
+ lookup_mark (value, false);
+ deduping = false;
+ }
+ value = ambiguous (new_val, value);
+ }
}
/* Add a NEW_TYPE, a found type binding into the current type binding. */
@@ -703,8 +745,7 @@ name_lookup::add_fns (tree fns)
else if (!DECL_DECLARES_FUNCTION_P (fns))
return;
- /* Only add those that aren't already there. */
- value = lookup_maybe_add (fns, value);
+ add_overload (fns);
}
/* Add functions of a namespace to the lookup structure. */
@@ -1004,7 +1045,11 @@ name_lookup::adl_template_arg (tree arg)
tree
name_lookup::search_adl (tree fns, vec<tree, va_gc> *args)
{
- lookup_mark (fns, true);
+ if (fns)
+ {
+ deduping = true;
+ lookup_mark (fns, true);
+ }
value = fns;
unsigned ix;
@@ -1019,7 +1064,6 @@ name_lookup::search_adl (tree fns, vec<t
adl_expr (arg);
fns = value;
- lookup_mark (fns, false);
return fns;
}
Index: cp/pt.c
===================================================================
--- cp/pt.c (revision 248576)
+++ cp/pt.c (working copy)
@@ -21728,32 +21728,32 @@ most_specialized_instantiation (tree tem
champ = templates;
for (fn = TREE_CHAIN (templates); fn; fn = TREE_CHAIN (fn))
- if (TREE_VALUE (champ) != TREE_VALUE (fn))
- {
- int fate = more_specialized_inst (TREE_VALUE (champ), TREE_VALUE (fn));
- if (fate == -1)
+ {
+ gcc_assert (TREE_VALUE (champ) != TREE_VALUE (fn));
+ int fate = more_specialized_inst (TREE_VALUE (champ), TREE_VALUE (fn));
+ if (fate == -1)
+ champ = fn;
+ else if (!fate)
+ {
+ /* Equally specialized, move to next function. If there
+ is no next function, nothing's most specialized. */
+ fn = TREE_CHAIN (fn);
champ = fn;
- else if (!fate)
- {
- /* Equally specialized, move to next function. If there
- is no next function, nothing's most specialized. */
- fn = TREE_CHAIN (fn);
- champ = fn;
- if (!fn)
- break;
- }
- }
+ if (!fn)
+ break;
+ }
+ }
if (champ)
/* Now verify that champ is better than everything earlier in the
instantiation list. */
- for (fn = templates; fn != champ; fn = TREE_CHAIN (fn))
- if (TREE_VALUE (champ) != TREE_VALUE (fn)
- && more_specialized_inst (TREE_VALUE (champ), TREE_VALUE (fn)) != 1)
- {
- champ = NULL_TREE;
- break;
- }
+ for (fn = templates; fn != champ; fn = TREE_CHAIN (fn)) {
+ if (more_specialized_inst (TREE_VALUE (champ), TREE_VALUE (fn)) != 1)
+ {
+ champ = NULL_TREE;
+ break;
+ }
+ }
processing_template_decl--;
Index: cp/tree.c
===================================================================
--- cp/tree.c (revision 248576)
+++ cp/tree.c (working copy)
@@ -2293,21 +2293,10 @@ ovl_iterator::remove_node (tree overload
void
lookup_mark (tree ovl, bool val)
{
- /* For every node that is a lookup, mark the thing it points to. */
- for (; ovl && TREE_CODE (ovl) == OVERLOAD && OVL_LOOKUP_P (ovl);
- ovl = OVL_CHAIN (ovl))
+ for (lkp_iterator iter (ovl); iter; ++iter)
{
- tree targ = OVL_FUNCTION (ovl);
- gcc_checking_assert (LOOKUP_SEEN_P (targ) != val);
- LOOKUP_SEEN_P (targ) = val;
- }
-
- if (ovl && (TREE_CODE (ovl) == OVERLOAD ||
- TREE_CODE (ovl) == FUNCTION_DECL))
- {
- /* Mark the overload itsef. */
- gcc_checking_assert (LOOKUP_SEEN_P (ovl) != val);
- LOOKUP_SEEN_P (ovl) = val;
+ gcc_checking_assert (LOOKUP_SEEN_P (*iter) != val);
+ LOOKUP_SEEN_P (*iter) = val;
}
}
@@ -2327,73 +2316,48 @@ lookup_add (tree fns, tree lookup)
return lookup;
}
-/* FNS is a new overload set, add it to LOOKUP, if it is not already
- present there. */
+/* FNS is a new overload set, add them to LOOKUP, if they are not
+ already present there. */
tree
-lookup_maybe_add (tree fns, tree lookup)
+lookup_maybe_add (tree fns, tree lookup, bool deduping)
{
- if (LOOKUP_SEEN_P (fns))
- return lookup;
-
- if (lookup && TREE_CODE (fns) == OVERLOAD)
- {
- /* Determine if we already have some part of this overload in
- the overload set. If so fix things up so we only have the
- overload set once. */
- tree marked = NULL_TREE;
+ if (deduping)
+ for (tree next, probe = fns; probe; probe = next)
+ {
+ tree fn = probe;
+ next = NULL_TREE;
- for (tree probe = fns; probe; probe = OVL_CHAIN (probe))
- if (LOOKUP_SEEN_P (probe))
+ if (TREE_CODE (probe) == OVERLOAD)
{
- marked = probe;
- break;
+ fn = OVL_FUNCTION (probe);
+ next = OVL_CHAIN (probe);
}
- else if (TREE_CODE (probe) != OVERLOAD)
- break;
- if (marked)
- {
- /* The tail of this overload is already in the lookup
- set. Stitch out the tail case, which might involve
- copying. */
- bool rewrite = false;
-
- LOOKUP_SEEN_P (marked) = false;
- for (tree *prev = &lookup, probe = *prev;
- ; prev = &OVL_CHAIN (probe), probe = *prev)
- {
- if (probe == marked)
- {
- *prev = NULL_TREE;
- break;
- }
- gcc_checking_assert (OVL_LOOKUP_P (probe));
- if (marked == OVL_FUNCTION (probe))
- {
- *prev = OVL_CHAIN (probe);
- break;
- }
-
- /* If we're in a used part of the lookup set, copy the
- node, so as to not disturb stored uses. */
- gcc_checking_assert (!rewrite || OVL_USED_P (probe));
- if (OVL_USED_P (probe))
- {
- rewrite = true;
- probe = ovl_copy (probe);
- OVL_LOOKUP_P (probe) = true;
- *prev = probe;
- }
- }
- }
- }
+ if (!LOOKUP_SEEN_P (fn))
+ LOOKUP_SEEN_P (fn) = true;
+ else
+ {
+ /* This function was already seen. Insert all the
+ predecessors onto the lookup. */
+ for (; fns != probe; fns = OVL_CHAIN (fns))
+ {
+ lookup = lookup_add (OVL_FUNCTION (fns), lookup);
+ /* Propagate OVL_USING, but OVL_HIDDEN doesn't matter. */
+ if (OVL_USING_P (fns))
+ OVL_USING_P (lookup) = true;
+ }
- /* Finally mark the new overload and prepend it to the current
- lookup. */
- LOOKUP_SEEN_P (fns) = true;
+ /* And now skip this function. */
+ fns = next;
+ }
+ }
- return lookup_add (fns, lookup);
+ if (fns)
+ /* We ended in a set of new functions. Add them all in one go. */
+ lookup = lookup_add (fns, lookup);
+
+ return lookup;
}
/* Regular overload OVL is part of a kept lookup. Mark the nodes on
Index: testsuite/g++.dg/lookup/pr80891-5.C
===================================================================
--- testsuite/g++.dg/lookup/pr80891-5.C (revision 0)
+++ testsuite/g++.dg/lookup/pr80891-5.C (working copy)
@@ -0,0 +1,68 @@
+// PR c++/80891 part 4
+
+// ICE copying an augmented lookup during ADL
+
+struct __normal_iterator get(); // { dg-message "candidate: .__normal_iterator get\\(\\)." }
+namespace boost {
+template <class> void get(); // { dg-message "candidate: .template<class> void boost::get\\(\\)." }
+struct A {
+ A(int);
+};
+enum problem_selector { subgraph_iso };
+template <typename, typename, typename, typename,
+ typename SubGraphIsoMapCallback, problem_selector>
+struct B {
+ B(A, A, int, int, int, int);
+ void m_fn1(SubGraphIsoMapCallback p1) {
+ __normal_iterator __trans_tmp_1();
+ p1(__trans_tmp_1, 0);
+ }
+};
+template <typename Graph1, typename Graph2, typename IndexMap1,
+ typename IndexMap2, typename VertexOrder1,
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate, typename SubGraphIsoMapCallback,
+ problem_selector problem_selection>
+void match(
+ Graph1, Graph2, SubGraphIsoMapCallback p3, VertexOrder1,
+ B<IndexMap1, IndexMap2, EdgeEquivalencePredicate,
+ VertexEquivalencePredicate, SubGraphIsoMapCallback, problem_selection>
+ p5) {
+ p5.m_fn1(p3);
+}
+template <problem_selector problem_selection, typename GraphSmall,
+ typename GraphLarge, typename IndexMapSmall, typename IndexMapLarge,
+ typename VertexOrderSmall, typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate, typename SubGraphIsoMapCallback>
+void vf2_subgraph_morphism(GraphSmall, GraphLarge, SubGraphIsoMapCallback p3,
+ IndexMapSmall, IndexMapLarge, VertexOrderSmall,
+ EdgeEquivalencePredicate,
+ VertexEquivalencePredicate) {
+ B<IndexMapSmall, IndexMapLarge, EdgeEquivalencePredicate,
+ VertexEquivalencePredicate, SubGraphIsoMapCallback, problem_selection>
+ s(0, 0, 0, 0, 0, 0);
+ match(0, 0, p3, 0, s);
+}
+template <typename GraphSmall, typename GraphLarge, typename IndexMapSmall,
+ typename IndexMapLarge, typename VertexOrderSmall,
+ typename EdgeEquivalencePredicate,
+ typename VertexEquivalencePredicate, typename SubGraphIsoMapCallback>
+int vf2_subgraph_iso(GraphSmall, GraphLarge, SubGraphIsoMapCallback p3,
+ IndexMapSmall, IndexMapLarge, VertexOrderSmall,
+ EdgeEquivalencePredicate, VertexEquivalencePredicate) {
+ vf2_subgraph_morphism<subgraph_iso>(0, 0, p3, 0, 0, 0, 0, 0);
+}
+}
+using namespace boost;
+struct C {
+ C(int) : graph1_(0), graph2_(0) {}
+ template <typename CorrespondenceMap1To2, typename CorrespondenceMap2To1>
+ void operator()(CorrespondenceMap1To2 p1, CorrespondenceMap2To1) {
+ get(p1); // { dg-error "no matching function" }
+ }
+ A graph1_;
+ A graph2_;
+};
+template <typename> void get(); // { dg-message "candidate: .template<class> void get\\(\\)." }
+void test_vf2_sub_graph_iso() { C a(vf2_subgraph_iso(0, 0, a, 0, 0, 0, 0, 0));
+}
