From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id 7649938618EE for ; Fri, 27 Oct 2023 20:01:23 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 7649938618EE Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 7649938618EE Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.129.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698436885; cv=none; b=C0lZBwfAKxHcOBX+0VIG+Y0KnsE5VGzeXsTRhxUt40UlNR+uyAOJZVM7qEmjgMHbF2a84KwP8Nc7PIDjOA9QXNl2SmJP9ihrcRrw4DV6bkCBSmniXw81vsjg2ifrELWfXCRVFu25grnI5dKmc+Yxx9ieUTanOxnBpHZRKsCjIr8= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1698436885; c=relaxed/simple; bh=GWtJipD6Hla5dVEVj1ZUSehRr8vyNawZvsg1DkmkCUg=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=sk/sOwPFOhEiWkaz+tdRMDr1OL+WuInavbZAkbp6DkWAArC9bjEXstwMI9QA+FfH/HTxuCgapg0jPAwB/EzF8Dh5Hb/QyAZZQ0Xu+qMMOmszH36D+pv2z/vu/lXOdngCUgcv5RhYhn8msiHpmAUlpqYyvnUc+fy1wBXFiCp83p0= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1698436883; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=cIv0OgmG0aQfexfv/Qbapm8c1yGfJNql2aeIKbvGQBk=; b=AH16DwwkFW5G7zqNDTwNZ/afaS6liBU/ueLslStDHzWqonUaNPhTBWW4Xp+AF8E3LWO019 zL9XeXJuQ7S5uEFdiO/xt45E5y1W3P//nZ8Q92dZfq4uZFFloNJUl+aCfzwmaGRSB5zHdR /5CDc+d5R40FznSFdAlrCrmZi/FNY2Y= Received: from mail-qv1-f71.google.com (mail-qv1-f71.google.com [209.85.219.71]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-315-YRR-sc_pP_mb-TlJCO8MsQ-1; Fri, 27 Oct 2023 16:01:12 -0400 X-MC-Unique: YRR-sc_pP_mb-TlJCO8MsQ-1 Received: by mail-qv1-f71.google.com with SMTP id 6a1803df08f44-66d062708b0so34344496d6.1 for ; Fri, 27 Oct 2023 13:01:12 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1698436871; x=1699041671; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=cIv0OgmG0aQfexfv/Qbapm8c1yGfJNql2aeIKbvGQBk=; b=SXsoFbdtK4tn8cC5R/ThUz20AfTD9pUX8nf716Y2VFTL+oWxIlOTJlQ9iWpSJiZQDq UWbds6PDRfqBu7pTBMW6WJoaf8A6FpaunTy1Dex7DjdL/09Ed/Xv2WLZJvi/JKO2mcg4 s9uC07lmMxQEhENX8RPhVsDyAdUhIH8+4+gl/pYvNJbaXxkkxWR4hA3kCYmYSmAkfyM0 STj+KWKHdoHqdyLY6EqP95h2MOW9K3ArmRwc3XThm3rEnXf7nIvobMEjrZjoLvVJ3stK ssqkVEoL6Y7sncqsfI1x7DClmuLi9B3wvytVfT2PMCo5Tm3m6gTEFUhfLfSuuMEMdsqH z5Pw== X-Gm-Message-State: AOJu0Yx2Z7hxbFg2edfUWh3FENBYpBG2IeTkdPD645FsHA8yV1RD0ZgE 7zOeGc7xCrpfYO7SjnQkOo9jLB/e4MuEMS2SNNS1FOCGEg1udatLmmEBdgxhf/N9nMuDEQGDhHN I+X4L48MxSxifGJ58yqKm+oEbehW5eZvbPqZQmR/T9h1BaJZRTsOZjAWw5iO8ntHAsWujrLPqeh I= X-Received: by 2002:a05:6214:2468:b0:66d:11e7:d4fe with SMTP id im8-20020a056214246800b0066d11e7d4femr5802943qvb.40.1698436870933; Fri, 27 Oct 2023 13:01:10 -0700 (PDT) X-Google-Smtp-Source: AGHT+IH6I2Y9X1u3NW9Hkl5akfJxykQw0zehYcnAwRd9Uaulc6PdmoN6CwvHSn0Dw8xaTFVUOhEo0g== X-Received: by 2002:a05:6214:2468:b0:66d:11e7:d4fe with SMTP id im8-20020a056214246800b0066d11e7d4femr5802894qvb.40.1698436870443; Fri, 27 Oct 2023 13:01:10 -0700 (PDT) Received: from localhost.localdomain (ool-457670bb.dyn.optonline.net. [69.118.112.187]) by smtp.gmail.com with ESMTPSA id l20-20020a0ce514000000b0065b17b925d0sm910777qvm.38.2023.10.27.13.01.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 27 Oct 2023 13:01:09 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: jason@redhat.com, Patrick Palka Subject: [PATCH v3 1/3] c++: sort candidates according to viability Date: Fri, 27 Oct 2023 15:55:29 -0400 Message-ID: <20231027195532.2566822-1-ppalka@redhat.com> X-Mailer: git-send-email 2.42.0.482.g2e8e77cbac MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII"; x-default=true X-Spam-Status: No, score=-13.6 required=5.0 tests=BAYES_00,DKIMWL_WL_HIGH,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H4,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_NONE,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: New in patch 1/3: * consistently use "non-viable" instead of "unviable" throughout * make 'champ' and 'challenger' in 'tourney' be z_candidate** to simplify moving 'champ' to the front of the list. drive-by cleanups in tourney, including renaming 'champ_compared_to_predecessor' to 'previous_worse_champ' for clarity. New in patch 2/3: * consistently use "non-viable" instead of "unviable" throughout New in patch 3/3: * introduce new -fnote-all-cands flag that controls noting other candidates when diagnosing deletedness, and also controls noting "ignored" candidates in general. -- >8 -- This patch: * changes splice_viable to move the non-viable candidates to the end of the list instead of removing them outright * makes tourney move the best candidate to the front of the candidate list * adjusts print_z_candidates to preserve our behavior of printing only viable candidates when diagnosing ambiguity * adds a parameter to print_z_candidates to control this default behavior (the follow-up patch will want to print all candidates when diagnosing deletedness) Thus after this patch we have access to the entire candidate list through the best viable candidate. This change also happens to fix diagnostics for the below testcase where we currently neglect to note the third candidate, since the presence of the two unordered non-strictly viable candidates causes splice_viable to prematurely get rid of the non-viable third candidate. gcc/cp/ChangeLog: * call.cc: Include "tristate.h". (splice_viable): Sort the candidate list according to viability. Don't remove non-viable candidates from the list. (print_z_candidates): Add defaulted only_viable_p parameter. By default only print non-viable candidates if there is no viable candidate. (tourney): Make 'candidates' parameter a reference. Ignore non-viable candidates. Move the true champ to the front of the candidates list, and update 'candidates' to point to the front. Drive-by cleanups, including renaming 'champ_compared_to_predecessor' to 'previous_worse_champ'. gcc/testsuite/ChangeLog: * g++.dg/overload/error5.C: New test. --- gcc/cp/call.cc | 181 ++++++++++++++----------- gcc/testsuite/g++.dg/overload/error5.C | 12 ++ 2 files changed, 117 insertions(+), 76 deletions(-) create mode 100644 gcc/testsuite/g++.dg/overload/error5.C diff --git a/gcc/cp/call.cc b/gcc/cp/call.cc index 2eb54b5b6ed..5d175b93a47 100644 --- a/gcc/cp/call.cc +++ b/gcc/cp/call.cc @@ -43,6 +43,7 @@ along with GCC; see the file COPYING3. If not see #include "attribs.h" #include "decl.h" #include "gcc-rich-location.h" +#include "tristate.h" /* The various kinds of conversion. */ @@ -160,7 +161,7 @@ static struct obstack conversion_obstack; static bool conversion_obstack_initialized; struct rejection_reason; -static struct z_candidate * tourney (struct z_candidate *, tsubst_flags_t); +static struct z_candidate * tourney (struct z_candidate *&, tsubst_flags_t); static int equal_functions (tree, tree); static int joust (struct z_candidate *, struct z_candidate *, bool, tsubst_flags_t); @@ -176,7 +177,8 @@ static void op_error (const op_location_t &, enum tree_code, enum tree_code, static struct z_candidate *build_user_type_conversion_1 (tree, tree, int, tsubst_flags_t); static void print_z_candidate (location_t, const char *, struct z_candidate *); -static void print_z_candidates (location_t, struct z_candidate *); +static void print_z_candidates (location_t, struct z_candidate *, + tristate = tristate::unknown ()); static tree build_this (tree); static struct z_candidate *splice_viable (struct z_candidate *, bool, bool *); static bool any_strictly_viable (struct z_candidate *); @@ -3700,68 +3702,60 @@ add_template_conv_candidate (struct z_candidate **candidates, tree tmpl, } /* The CANDS are the set of candidates that were considered for - overload resolution. Return the set of viable candidates, or CANDS - if none are viable. If any of the candidates were viable, set + overload resolution. Sort CANDS so that the strictly viable + candidates appear first, followed by non-strictly viable candidates, + followed by non-viable candidates. Returns the first candidate + in this sorted list. If any of the candidates were viable, set *ANY_VIABLE_P to true. STRICT_P is true if a candidate should be - considered viable only if it is strictly viable. */ + considered viable only if it is strictly viable when setting + *ANY_VIABLE_P. */ static struct z_candidate* splice_viable (struct z_candidate *cands, bool strict_p, bool *any_viable_p) { - struct z_candidate *viable; - struct z_candidate **last_viable; - struct z_candidate **cand; - bool found_strictly_viable = false; + z_candidate *strictly_viable = nullptr; + z_candidate **strictly_viable_tail = &strictly_viable; + + z_candidate *non_strictly_viable = nullptr; + z_candidate **non_strictly_viable_tail = &non_strictly_viable; + + z_candidate *non_viable = nullptr; + z_candidate **non_viable_tail = &non_viable; /* Be strict inside templates, since build_over_call won't actually do the conversions to get pedwarns. */ if (processing_template_decl) strict_p = true; - viable = NULL; - last_viable = &viable; - *any_viable_p = false; - - cand = &cands; - while (*cand) + for (z_candidate *cand = cands; cand; cand = cand->next) { - struct z_candidate *c = *cand; if (!strict_p - && (c->viable == 1 || TREE_CODE (c->fn) == TEMPLATE_DECL)) - { - /* Be strict in the presence of a viable candidate. Also if - there are template candidates, so that we get deduction errors - for them instead of silently preferring a bad conversion. */ - strict_p = true; - if (viable && !found_strictly_viable) - { - /* Put any spliced near matches back onto the main list so - that we see them if there is no strict match. */ - *any_viable_p = false; - *last_viable = cands; - cands = viable; - viable = NULL; - last_viable = &viable; - } - } + && (cand->viable == 1 || TREE_CODE (cand->fn) == TEMPLATE_DECL)) + /* Be strict in the presence of a viable candidate. Also if + there are template candidates, so that we get deduction errors + for them instead of silently preferring a bad conversion. */ + strict_p = true; - if (strict_p ? c->viable == 1 : c->viable) - { - *last_viable = c; - *cand = c->next; - c->next = NULL; - last_viable = &c->next; - *any_viable_p = true; - if (c->viable == 1) - found_strictly_viable = true; - } - else - cand = &c->next; + /* Move this candidate to the appropriate list according to + its viability. */ + auto& tail = (cand->viable == 1 ? strictly_viable_tail + : cand->viable == -1 ? non_strictly_viable_tail + : non_viable_tail); + *tail = cand; + tail = &cand->next; } - return viable ? viable : cands; + *any_viable_p = (strictly_viable != nullptr + || (!strict_p && non_strictly_viable != nullptr)); + + /* Combine the lists. */ + *non_viable_tail = nullptr; + *non_strictly_viable_tail = non_viable; + *strictly_viable_tail = non_strictly_viable; + + return strictly_viable; } static bool @@ -3995,8 +3989,13 @@ print_z_candidate (location_t loc, const char *msgstr, } } +/* Print information about each overload candidate in CANDIDATES, + which is assumed to have gone through splice_viable and tourney + (if splice_viable succeeded). */ + static void -print_z_candidates (location_t loc, struct z_candidate *candidates) +print_z_candidates (location_t loc, struct z_candidate *candidates, + tristate only_viable_p /* = tristate::unknown () */) { struct z_candidate *cand1; struct z_candidate **cand2; @@ -4041,8 +4040,19 @@ print_z_candidates (location_t loc, struct z_candidate *candidates) } } + /* Unless otherwise specified, if there's a (strictly) viable candidate + then we assume we're being called as part of diagnosing ambiguity, in + which case we want to print only viable candidates since non-viable + candidates couldn't have contributed to the ambiguity. */ + if (only_viable_p.is_unknown ()) + only_viable_p = candidates->viable == 1; + for (; candidates; candidates = candidates->next) - print_z_candidate (loc, N_("candidate:"), candidates); + { + if (only_viable_p.is_true () && candidates->viable != 1) + break; + print_z_candidate (loc, N_("candidate:"), candidates); + } } /* USER_SEQ is a user-defined conversion sequence, beginning with a @@ -13169,57 +13179,76 @@ tweak: /* Given a list of candidates for overloading, find the best one, if any. This algorithm has a worst case of O(2n) (winner is last), and a best case of O(n/2) (totally ambiguous); much better than a sorting - algorithm. */ + algorithm. The candidates list is assumed to be sorted according + to viability (via splice_viable). */ static struct z_candidate * -tourney (struct z_candidate *candidates, tsubst_flags_t complain) +tourney (struct z_candidate *&candidates, tsubst_flags_t complain) { - struct z_candidate *champ = candidates, *challenger; + struct z_candidate **champ = &candidates, **challenger; int fate; - struct z_candidate *champ_compared_to_predecessor = nullptr; + struct z_candidate *previous_worse_champ = nullptr; /* Walk through the list once, comparing each current champ to the next candidate, knocking out a candidate or two with each comparison. */ - for (challenger = champ->next; challenger; ) + for (challenger = &candidates->next; *challenger && (*challenger)->viable; ) { - fate = joust (champ, challenger, 0, complain); + fate = joust (*champ, *challenger, 0, complain); if (fate == 1) - challenger = challenger->next; + challenger = &(*challenger)->next; + else if (fate == -1) + { + previous_worse_champ = *champ; + champ = challenger; + challenger = &(*challenger)->next; + } else { - if (fate == 0) + previous_worse_champ = nullptr; + champ = &(*challenger)->next; + if (!*champ || !(*champ)->viable) { - champ = challenger->next; - if (champ == 0) - return NULL; - champ_compared_to_predecessor = nullptr; - } - else - { - champ_compared_to_predecessor = champ; - champ = challenger; + champ = nullptr; + break; } - - challenger = champ->next; + challenger = &(*champ)->next; } } /* Make sure the champ is better than all the candidates it hasn't yet been compared to. */ - for (challenger = candidates; - challenger != champ; - challenger = challenger->next) + if (champ) + for (challenger = &candidates; + challenger != champ; + challenger = &(*challenger)->next) + { + if (*challenger == previous_worse_champ) + /* We already know this candidate this worse than the champ. */ + continue; + fate = joust (*champ, *challenger, 0, complain); + if (fate != 1) + { + champ = nullptr; + break; + } + } + + if (!champ) + return nullptr; + + /* Move the champ to the front of the candidate list. */ + + if (champ != &candidates) { - if (challenger == champ_compared_to_predecessor) - continue; - fate = joust (champ, challenger, 0, complain); - if (fate != 1) - return NULL; + z_candidate *saved_champ = *champ; + *champ = saved_champ->next; + saved_champ->next = candidates; + candidates = saved_champ; } - return champ; + return candidates; } /* Returns nonzero if things of type FROM can be converted to TO. */ diff --git a/gcc/testsuite/g++.dg/overload/error5.C b/gcc/testsuite/g++.dg/overload/error5.C new file mode 100644 index 00000000000..6a2f3b5ba35 --- /dev/null +++ b/gcc/testsuite/g++.dg/overload/error5.C @@ -0,0 +1,12 @@ +// Verify we note all three candidates when diagnosing overload +// resolution failure. The presence of the first two (ambiguous) +// non-strictly viable candidates used to make us prune the third +// and not note it. + +void f(int, int*); // { dg-message "candidate" } +void f(int*, int); // { dg-message "candidate" } +void f(int, int, int); // { dg-message "candidate" } + +int main() { + f(1, 2); // { dg-error "no match|invalid conversion" } +} -- 2.42.0.482.g2e8e77cbac