From patchwork Fri May 26 15:08:13 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Nathan Sidwell X-Patchwork-Id: 767434 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3wZ8f94fvvz9s7r for ; Sat, 27 May 2017 01:08:33 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="pxsWv7nQ"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; q=dns; s=default; b=dGEDSZQYy/0EB0Ud+XQH+o3aToP5JOFsnA9FUez22mINUy4yrk 7qHnVCAXNDIM/BcGPow5Z37Nf4yXON/EIrJXP545mkfJ9dOTJMnhB32TbZm/x3tn gbqcV7zJLCofJOhQlRJRg5oSr//UNm041Nf5GYHJbquRDcI1mT5Vxc/sk= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:to :from:subject:message-id:date:mime-version:content-type; s= default; bh=Ju0085q7iiE37yaJT0KEIzV1Ux8=; b=pxsWv7nQbIgIXwTh4Kdu Pe3o7IgZvIYwNtsyfujg9sA+UhMlKXXiotLBMPD5h3UCUq53Txu6wQSbkIgB16uv u5xctvj9Og+m9EgYgK1VPMLQ4kRPPyqPcN2R4SwWoGbkd/b9XYRZuG2c5X1g39Jw Hv4lEKJkxjM/TzKz5TGb8mM= Received: (qmail 89113 invoked by alias); 26 May 2017 15:08:18 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 87103 invoked by uid 89); 26 May 2017 15:08:16 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-11.1 required=5.0 tests=BAYES_00, FREEMAIL_FROM, GIT_PATCH_2, GIT_PATCH_3, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=ham version=3.3.2 spammy=escaping X-HELO: mail-yb0-f178.google.com Received: from mail-yb0-f178.google.com (HELO mail-yb0-f178.google.com) (209.85.213.178) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 26 May 2017 15:08:14 +0000 Received: by mail-yb0-f178.google.com with SMTP id 187so2971084ybg.0 for ; Fri, 26 May 2017 08:08:17 -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:from:subject:message-id:date :user-agent:mime-version:content-language; bh=abemHbtamsZpe8hGGH9XbYLfSwaD9f39Kv7l9JYyBnw=; b=etYpmp0NgZQvgACysid0d/R1oIm98rZgGn+etIMa8pdtawdSYpUW5YKmn8cpALYZVO 1NGy0kq1ASKi5KAWha1rgyTDB5IwNSKImG7mN7PHVNSNhDqgjGCGuEx2w5LSNfgKTTX5 PlsRAutea+AxG9qE/lXUgv4dATA5FrxXVF8BpiSktevLOkPfTW5lEbN3CEHKt8gxkOb2 IErI3Zq1f7UUyAUfanA5yX5DlH9jewY5uP0nX2ceztpGJ7gniIKHNNx+8Nf5TNUxcObZ ew97eeFP0SZS3GdDn+/L8Q5VI3vEngLjl4GpbPaIYqMUEbF/A1aueruCcKF/QIDEb9MD sp3g== X-Gm-Message-State: AODbwcDG016z5YqhBkKUN3Q8OlngRniArzpScnHthhT6zcWXEHfEr11g IYZO70bQScIsqrH1 X-Received: by 10.37.172.19 with SMTP id w19mr18828981ybi.14.1495811296089; Fri, 26 May 2017 08:08:16 -0700 (PDT) Received: from ?IPv6:2620:10d:c0a3:20fb:f6d0:5ac5:64cd:f102? ([2620:10d:c091:200::2:a1d1]) by smtp.googlemail.com with ESMTPSA id n1sm486550ywd.33.2017.05.26.08.08.14 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 26 May 2017 08:08:15 -0700 (PDT) To: GCC Patches From: Nathan Sidwell Subject: [C++ PATCH] lookup iterators come alive Message-ID: Date: Fri, 26 May 2017 11:08:13 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.1.0 MIME-Version: 1.0 This patch enables the 2D nature of lookup results. Previously whenever we had to combine overload sets from multiple places, we'd prepend one of them, one function at a time, to the other. This patch changes that. We can prepend an entire overload set as a single entry to another set. This nesting is only ever 1 deep, and only ever applies to lookup results -- the symbol binding remains a 1 dimensional overload. Other than the using-declaration case I discussed yesterday, the only place we might meet the same overload as before is in ADL lookup, where we re-search the same namespaces as we searched in the non-adl lookup. The most common case is we'll see the exact same overload again. We detect this in lookup_maybe_add, by using LOOKUP_SEEN_P on the overload nodes themselves. A rarer case is that between the first lookup and the later one, we added new functions to the symbol binding. We detect this too, and replace the older lookup with the newer one. As ADL is recursive, we have to unmark and mark any partial lookup result, when we discover a recursive lookup. Hopefully I already captured all the places an overload iterator should be lkp_iterator rather than ovl_iterator. The latter will assert it's not looking at a nested overload now. nathan 2017-05-26 Nathan Sidwell * cp-tree.h (OVL_CHAIN): Check looking at OVERLOAD. (ovl_iterator): Add allow_inner field. Adjust ctor. Make unduplicatable. (ovl_iterator::maybe_push, ovl_iterator::pop): New. (lkp_iterator): Add outer field. Adjust ctor. (lkp_iterator::operator++): New. (lookup_mark, lookup_maybe_add): Declare. * name-lookup.c (name_lookup): Delete fn_set member. (name_lookup::preserve_state, name_lookup::restore_state): Unmark and mark lookup. (name_lookup::add_value): Use lookup_add directly. (name_lookup::add_fns: Use lookup_maybe_add. (name_lookup::search_adl): Mark and unmark fns. (pushdecl): Adjust. * pt.c (check_explicit_specialization): Use lookup_add directly. * ptree.c (cxx_print_xnode): Show complete overload structure. * tree.c (lookup_mark, lookup_maybe_add): New. Index: cp/cp-tree.h =================================================================== --- cp/cp-tree.h (revision 248506) +++ cp/cp-tree.h (working copy) @@ -657,7 +657,8 @@ typedef struct ptrmem_cst * ptrmem_cst_t Other users should use iterators and convenience functions. */ #define OVL_FUNCTION(NODE) \ (((struct tree_overload*)OVERLOAD_CHECK (NODE))->function) -#define OVL_CHAIN(NODE) TREE_CHAIN (NODE) +#define OVL_CHAIN(NODE) \ + (((struct tree_overload*)OVERLOAD_CHECK (NODE))->common.chain) /* If set, this was imported in a using declaration. */ #define OVL_USING_P(NODE) TREE_LANG_FLAG_1 (OVERLOAD_CHECK (NODE)) @@ -684,6 +685,9 @@ typedef struct ptrmem_cst * ptrmem_cst_t #define OVL_SINGLE_P(NODE) \ (TREE_CODE (NODE) != OVERLOAD || !OVL_CHAIN (NODE)) +/* OVL_HIDDEN_P nodes come first, then OVL_USING_P nodes, then regular + fns. */ + struct GTY(()) tree_overload { struct tree_common common; tree function; @@ -694,19 +698,19 @@ struct GTY(()) tree_overload { class ovl_iterator { tree ovl; + const bool allow_inner; /* Only used when checking. */ public: - ovl_iterator (tree o) - :ovl (o) - {} - - ovl_iterator &operator= (const ovl_iterator &from) + explicit ovl_iterator (tree o, bool allow = false) + : ovl (o), allow_inner (allow) { - ovl = from.ovl; - - return *this; } + private: + /* Do not duplicate. */ + ovl_iterator &operator= (const ovl_iterator &); + ovl_iterator (const ovl_iterator &); + public: operator bool () const { @@ -722,7 +726,7 @@ class ovl_iterator tree fn = TREE_CODE (ovl) != OVERLOAD ? ovl : OVL_FUNCTION (ovl); /* Check this is not an unexpected 2-dimensional overload. */ - gcc_checking_assert (TREE_CODE (fn) != OVERLOAD); + gcc_checking_assert (allow_inner || TREE_CODE (fn) != OVERLOAD); return fn; } @@ -748,6 +752,27 @@ class ovl_iterator return reveal_node (head, ovl); } + protected: + /* If we have a nested overload, point at the inner overload and + return the next link on the outer one. */ + tree maybe_push () + { + tree r = NULL_TREE; + + if (ovl && TREE_CODE (ovl) == OVERLOAD && OVL_NESTED_P (ovl)) + { + r = OVL_CHAIN (ovl); + ovl = OVL_FUNCTION (ovl); + } + return r; + } + /* Restore an outer nested overload. */ + void pop (tree outer) + { + gcc_checking_assert (!ovl); + ovl = outer; + } + private: /* We make these static functions to avoid the address of the iterator escaping the local context. */ @@ -758,18 +783,34 @@ class ovl_iterator /* Iterator over a (potentially) 2 dimensional overload, which is produced by name lookup. */ -/* Note this is currently a placeholder, as the name-lookup changes - are not yet committed. */ - class lkp_iterator : public ovl_iterator { typedef ovl_iterator parent; + tree outer; + public: - lkp_iterator (tree o) - : parent (o) + explicit lkp_iterator (tree o) + : parent (o, true), outer (maybe_push ()) { } + + public: + lkp_iterator &operator++ () + { + bool repush = !outer; + + if (!parent::operator++ () && !repush) + { + pop (outer); + repush = true; + } + + if (repush) + outer = maybe_push (); + + return *this; + } }; struct GTY(()) tree_template_decl { @@ -6865,7 +6906,9 @@ extern tree ovl_make (tree fn, extern tree ovl_insert (tree fn, tree maybe_ovl, bool using_p = false); 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 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 248506) +++ cp/name-lookup.c (working copy) @@ -161,7 +161,6 @@ public: int flags; /* Lookup flags. */ vec *scopes; name_lookup *previous; /* Previously active lookup. */ - hash_set *fn_set; protected: /* Marked scope stack for outermost name lookup. */ @@ -172,13 +171,12 @@ protected: public: name_lookup (tree n, int f = 0) : name (n), value (NULL_TREE), type (NULL_TREE), flags (f), - scopes (NULL), previous (NULL), fn_set (NULL) + scopes (NULL), previous (NULL) { preserve_state (); } ~name_lookup () { - gcc_checking_assert (!fn_set); restore_state (); } @@ -299,6 +297,9 @@ name_lookup::preserve_state () previous->scopes->quick_push (decl); } } + + /* Unmark the outer partial lookup. */ + lookup_mark (previous->value, false); } else scopes = shared_scopes; @@ -322,6 +323,8 @@ name_lookup::restore_state () active = previous; if (previous) { + free (scopes); + unsigned length = vec_safe_length (previous->scopes); for (unsigned ix = 0; ix != length; ix++) { @@ -345,7 +348,8 @@ name_lookup::restore_state () LOOKUP_SEEN_P (decl) = true; } - free (scopes); + /* Remark the outer partial lookup. */ + lookup_mark (previous->value, true); } else shared_scopes = scopes; @@ -403,10 +407,7 @@ name_lookup::add_value (tree new_val) && same_type_p (TREE_TYPE (value), TREE_TYPE (new_val)))) ; else if (OVL_P (value) && OVL_P (new_val)) - { - for (ovl_iterator iter (new_val); iter; ++iter) - value = lookup_add (*iter, value); - } + value = lookup_add (new_val, value); else value = ambiguous (new_val, value); } @@ -684,9 +685,7 @@ name_lookup::add_fns (tree fns) return; /* Only add those that aren't already there. */ - for (ovl_iterator iter (fns); iter; ++iter) - if (!fn_set->add (*iter)) - value = lookup_add (*iter, value); + value = lookup_maybe_add (fns, value); } /* Add functions of a namespace to the lookup structure. */ @@ -987,13 +986,9 @@ name_lookup::adl_template_arg (tree arg) tree name_lookup::search_adl (tree fns, vec *args) { + lookup_mark (fns, true); value = fns; - /* Add the current overload set into the hash table. */ - fn_set = new hash_set; - for (lkp_iterator iter (fns); iter; ++iter) - fn_set->add (*iter); - unsigned ix; tree arg; @@ -1005,10 +1000,8 @@ name_lookup::search_adl (tree fns, vec