From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 104487 invoked by alias); 29 May 2017 19:44:38 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Received: (qmail 104468 invoked by uid 89); 29 May 2017 19:44:36 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-10.6 required=5.0 tests=BAYES_00,FREEMAIL_FROM,GIT_PATCH_2,GIT_PATCH_3,KAM_ASCII_DIVIDERS,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM,SPF_PASS autolearn=ham version=3.3.2 spammy=engage X-HELO: mail-yw0-f180.google.com Received: from mail-yw0-f180.google.com (HELO mail-yw0-f180.google.com) (209.85.161.180) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Mon, 29 May 2017 19:44:33 +0000 Received: by mail-yw0-f180.google.com with SMTP id p73so31854536ywp.0 for ; Mon, 29 May 2017 12:44:37 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:to:cc:from:subject:message-id:date :user-agent:mime-version:content-language; bh=Q2WfLwB1zbWWS0/8pY+kp751UBtWvaMVVErx1ErCkYI=; b=AbkQf75C9CFlr+YuSTkZ3HzZ+4TZzGKK1RuUi5gfL94Pwl2/ko5c1gIDSlItZa8E5+ b7Q5CUBEcgTedqL3powK96kZERY8vTfxyfXfaxbzlrxtvYhUb2WdSXjuPfF0C8SHZQm7 9Dq6bo15HJp+mmh53/VBZhnEhOikFz8kN2B1cDAmYhg20NstOKutwjqRpcJyBmkDvM58 3/mlTZ7Q5TTJBY7kuHGBaCMKQoTOXOg+PKkNKwlIPnFoV5K3ghC62yC16lPvorGPVsDH 9rGI1V271kBLxfhR50VgZ/sawhDnEW+jiWMKoQyp9AC/deGG3+QT6DGJ+NBAd5n8wpFy wg9w== X-Gm-Message-State: AODbwcAuTmtAKGP6ngpEdZxPdFurev8L5fQJmaPwFSfcUIvHU8N9HuB8 jSgRMc/4sni+TA== X-Received: by 10.129.75.150 with SMTP id y144mr12657722ywa.8.1496087075467; Mon, 29 May 2017 12:44:35 -0700 (PDT) Received: from ?IPv6:2620:10d:c0a1:1102:b9b0:1beb:d21c:b3f4? ([2620:10d:c091:180::d0e1]) by smtp.googlemail.com with ESMTPSA id c198sm5120334ywh.79.2017.05.29.12.44.34 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 29 May 2017 12:44:34 -0700 (PDT) To: GCC Patches Cc: Markus Trippelsdorf From: Nathan Sidwell Subject: [C++ PATCH] PR c++/80891 #1 & #5 Message-ID: <3c0df69d-c85e-754e-8449-a65eed8bb8a7@acm.org> Date: Mon, 29 May 2017 20:22:00 -0000 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.1.0 MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="------------235125FB1ED5598CF4136669" X-SW-Source: 2017-05/txt/msg02213.txt.bz2 This is a multi-part message in MIME format. --------------235125FB1ED5598CF4136669 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Content-length: 615 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 --------------235125FB1ED5598CF4136669 Content-Type: text/x-patch; name="80891-5.diff" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="80891-5.diff" Content-length: 14645 2017-05-29 Nathan Sidwell 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 *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 *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 void get(); // { dg-message "candidate: .template void boost::get\\(\\)." } +struct A { + A(int); +}; +enum problem_selector { subgraph_iso }; +template +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 +void match( + Graph1, Graph2, SubGraphIsoMapCallback p3, VertexOrder1, + B + p5) { + p5.m_fn1(p3); +} +template +void vf2_subgraph_morphism(GraphSmall, GraphLarge, SubGraphIsoMapCallback p3, + IndexMapSmall, IndexMapLarge, VertexOrderSmall, + EdgeEquivalencePredicate, + VertexEquivalencePredicate) { + B + s(0, 0, 0, 0, 0, 0); + match(0, 0, p3, 0, s); +} +template +int vf2_subgraph_iso(GraphSmall, GraphLarge, SubGraphIsoMapCallback p3, + IndexMapSmall, IndexMapLarge, VertexOrderSmall, + EdgeEquivalencePredicate, VertexEquivalencePredicate) { + vf2_subgraph_morphism(0, 0, p3, 0, 0, 0, 0, 0); +} +} +using namespace boost; +struct C { + C(int) : graph1_(0), graph2_(0) {} + template + void operator()(CorrespondenceMap1To2 p1, CorrespondenceMap2To1) { + get(p1); // { dg-error "no matching function" } + } + A graph1_; + A graph2_; +}; +template void get(); // { dg-message "candidate: .template void get\\(\\)." } +void test_vf2_sub_graph_iso() { C a(vf2_subgraph_iso(0, 0, a, 0, 0, 0, 0, 0)); +} --------------235125FB1ED5598CF4136669--