From patchwork Fri May 13 22:21:23 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Lance Taylor X-Patchwork-Id: 53983 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 841F3395B417 for ; Fri, 13 May 2022 22:22:21 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 841F3395B417 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1652480541; bh=RjUkV180RYu1XVZk0DI/WzO4k/mPE79B+bo9UnXlK48=; h=Date:Subject:To:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=lyHkYLT3cCt6Dd8JgEa2qeSkkEdxp9SebZXQHq+6U6c1i9Fk4UK4X0OMhuRBDuXBC D8Z1Xz6H57y23yIl+9xG+OwTvqHzG3+Nv3Ttx+YT5dRlLonLZlbpxWbEJsaDPv2AGI aCWQbmPrwl0G5U4Zg9NteqO/7I5i4iku20qITAmo= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-ed1-x52f.google.com (mail-ed1-x52f.google.com [IPv6:2a00:1450:4864:20::52f]) by sourceware.org (Postfix) with ESMTPS id CB349395B44F for ; Fri, 13 May 2022 22:21:35 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org CB349395B44F Received: by mail-ed1-x52f.google.com with SMTP id s11so7691726edy.6 for ; Fri, 13 May 2022 15:21:35 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=RjUkV180RYu1XVZk0DI/WzO4k/mPE79B+bo9UnXlK48=; b=SQdLuIs3XLbSRoMeg1VTI+sd9au6RbJ3CTQXIQ5biYgr4dxxO3YByL6NkPp9PE16Z2 nU0RawPpsazehwWBiGydrqZO/BdJSC0RFKmqcBt/omHRnO6QTMQAOtXLUK6yHylG4OoH NGrg9XoyGSGp5GUOAh1NfroFRBnxjULxbGYg8n4noyI878+1Z9IgpOq6XdYXGfv6gOCc pjAtQxFZpDvR1ss2VQo6qNXsC/QGxJqHgYp405Fc1dg2Y6Nm1e+iqRonMnarGOZWnCPu eNt4NV9ULGSDbmw6c6KxuqrFaP2StRKyf4A6sUSqUgO7Se4BZ1tu7hI+LKdTJnOHwNM4 pMHQ== X-Gm-Message-State: AOAM533moFwNJs+QjuHNWYrab2Fqubv4c07AwtouZbGBZPGbBIvwpC46 MplasDd2FHUTAs0v0A12pCMR+d6J2niu3RxAqyH2RvhQhA85RA== X-Google-Smtp-Source: ABdhPJwWdKjpIoklwYZpjGl6CcQAoGigmBSY/PEFVLm5xfs/WkxFsKgGXOru0HJ2xrIy+j4fmDolSpxslv2KodP50XE= X-Received: by 2002:a05:6402:1941:b0:413:2b7e:676e with SMTP id f1-20020a056402194100b004132b7e676emr868212edz.114.1652480494396; Fri, 13 May 2022 15:21:34 -0700 (PDT) MIME-Version: 1.0 Date: Fri, 13 May 2022 15:21:23 -0700 Message-ID: Subject: Go patch committed: Always sort interface parse methods To: gcc-patches , gofrontend-dev X-Spam-Status: No, score=-10.2 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Ian Lance Taylor via Gcc-patches From: Ian Lance Taylor Reply-To: Ian Lance Taylor Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" This patch to the Go frontend always sorts interface parse methods. The exporter relies on sorting interface parse methods. It would sort them as it encountered interface types. However, when an interface type is an element of a struct or array type, the exporter might encounter that interface type before sorting the parse methods. If it then encountered an identical interface type again, it could get confused about whether the two types are identical or not. Fix the problem by always sorting the parse methods in the finalize_methods pass. Also firm up the export type sorting to make sure we never have this kind of confusion again. Doing this revealed that we need to be more careful about sorting in order to handle aliases correctly. Also fix the interface type hash computation to use the right hash value when looking at parse methods rather than all methods. The test case for this is https://go.dev/cl/405759. This fixes https://go.dev/issue/52841. Bootstrapped and ran Go testsuite on x86_64-pc-linux-gnu. Committed to mainline. Ian 59d8d7177a02a71b385c233bd4605098d21069ec diff --git a/gcc/go/gofrontend/MERGE b/gcc/go/gofrontend/MERGE index 3ec315f6892..daa725f9de9 100644 --- a/gcc/go/gofrontend/MERGE +++ b/gcc/go/gofrontend/MERGE @@ -1,4 +1,4 @@ -6a33e7e30c89edc12340dc470b44791bb1066feb +f5bc28a30b7503015bbef38afb5812313184e822 The first line of this file holds the git revision number of the last merge done from the gofrontend repository. diff --git a/gcc/go/gofrontend/export.cc b/gcc/go/gofrontend/export.cc index 3d11334884d..70d3f708d32 100644 --- a/gcc/go/gofrontend/export.cc +++ b/gcc/go/gofrontend/export.cc @@ -360,16 +360,6 @@ Collect_export_references::type(Type* type) if (type->is_abstract()) return TRAVERSE_SKIP_COMPONENTS; - // For interfaces make sure that embedded methods are sorted, since the - // comparison function we use for indexing types relies on it (this call has - // to happen before the record_type call below). - if (type->classification() == Type::TYPE_INTERFACE) - { - Interface_type* it = type->interface_type(); - if (it != NULL) - it->sort_embedded(); - } - if (!this->exp_->record_type(type)) { // We've already seen this type. @@ -501,6 +491,11 @@ should_export(Named_object* no) return true; } +// Compare Typed_identifier_list's. + +static int +compare_til(const Typed_identifier_list*, const Typed_identifier_list*); + // A functor to sort Named_object pointers by name. struct Sort_bindings @@ -514,10 +509,57 @@ struct Sort_bindings return true; if (n2->package() == NULL) return false; - return n1->package()->pkgpath() < n2->package()->pkgpath(); + + // Make sure we don't see the same pkgpath twice. + const std::string& p1(n1->package()->pkgpath()); + const std::string& p2(n2->package()->pkgpath()); + go_assert(p1 != p2); + + return p1 < p2; } - return n1->name() < n2->name(); + if (n1->name() != n2->name()) + return n1->name() < n2->name(); + + // We shouldn't see the same name twice, but it can happen for + // nested type names. + + go_assert(n1->is_type() && n2->is_type()); + + unsigned int ind1; + const Named_object* g1 = n1->type_value()->in_function(&ind1); + unsigned int ind2; + const Named_object* g2 = n2->type_value()->in_function(&ind2); + + if (g1 == NULL) + { + go_assert(g2 != NULL); + return true; + } + else if (g2 == NULL) + return false; + else if (g1 == g2) + { + go_assert(ind1 != ind2); + return ind1 < ind2; + } + else if ((g1->package() != g2->package()) || (g1->name() != g2->name())) + return Sort_bindings()(g1, g2); + else + { + // This case can happen if g1 or g2 is a method. + if (g1 != NULL && g1->func_value()->is_method()) + { + const Typed_identifier* r = g1->func_value()->type()->receiver(); + g1 = r->type()->named_type()->named_object(); + } + if (g2 != NULL && g2->func_value()->is_method()) + { + const Typed_identifier* r = g2->func_value()->type()->receiver(); + g2 = r->type()->named_type()->named_object(); + } + return Sort_bindings()(g1, g2); + } } }; @@ -528,17 +570,20 @@ struct Sort_types bool operator()(const Type* t1, const Type* t2) const { + t1 = t1->forwarded(); + t2 = t2->forwarded(); + const Named_type* nt1 = t1->named_type(); const Named_type* nt2 = t2->named_type(); if (nt1 != NULL) { - if (nt2 != NULL) - { - Sort_bindings sb; - return sb(nt1->named_object(), nt2->named_object()); - } - else - return true; + if (nt2 != NULL) + { + Sort_bindings sb; + return sb(nt1->named_object(), nt2->named_object()); + } + else + return true; } else if (nt2 != NULL) return false; @@ -549,10 +594,218 @@ struct Sort_types gogo->type_descriptor_backend_name(t1, NULL, &b1); Backend_name b2; gogo->type_descriptor_backend_name(t2, NULL, &b2); - return b1.name() < b2.name(); + + std::string n1 = b1.name(); + std::string n2 = b2.name(); + if (n1 != n2) + return n1 < n2; + + // We should never see equal types here. If we do, we may not + // generate an identical output file for identical input. But the + // backend names can be equal because we want to treat aliases + // differently while type_descriptor_backend_name does not. In + // that case we need to traverse the type elements. + + // t1 == t2 in case std::sort compares elements to themselves. + if (t1 == t2) + return false; + + Sort_types sort; + Type_alias_identical identical; + go_assert(!identical(t1, t2)); + + switch (t1->classification()) + { + case Type::TYPE_ERROR: + return false; + + case Type::TYPE_VOID: + case Type::TYPE_BOOLEAN: + case Type::TYPE_INTEGER: + case Type::TYPE_FLOAT: + case Type::TYPE_COMPLEX: + case Type::TYPE_STRING: + case Type::TYPE_SINK: + case Type::TYPE_NIL: + case Type::TYPE_CALL_MULTIPLE_RESULT: + case Type::TYPE_NAMED: + case Type::TYPE_FORWARD: + default: + go_unreachable(); + + case Type::TYPE_FUNCTION: + { + const Function_type* ft1 = t1->function_type(); + const Function_type* ft2 = t2->function_type(); + const Typed_identifier* r1 = ft1->receiver(); + const Typed_identifier* r2 = ft2->receiver(); + if (r1 == NULL) + go_assert(r2 == NULL); + else + { + go_assert(r2 != NULL); + const Type* rt1 = r1->type()->forwarded(); + const Type* rt2 = r2->type()->forwarded(); + if (!identical(rt1, rt2)) + return sort(rt1, rt2); + } + + const Typed_identifier_list* p1 = ft1->parameters(); + const Typed_identifier_list* p2 = ft2->parameters(); + if (p1 == NULL || p1->empty()) + go_assert(p2 == NULL || p2->empty()); + else + { + go_assert(p2 != NULL && !p2->empty()); + int i = compare_til(p1, p2); + if (i < 0) + return false; + else if (i > 0) + return true; + } + + p1 = ft1->results(); + p2 = ft2->results(); + if (p1 == NULL || p1->empty()) + go_assert(p2 == NULL || p2->empty()); + else + { + go_assert(p2 != NULL && !p2->empty()); + int i = compare_til(p1, p2); + if (i < 0) + return false; + else if (i > 0) + return true; + } + + go_unreachable(); + } + + case Type::TYPE_POINTER: + { + const Type* p1 = t1->points_to()->forwarded(); + const Type* p2 = t2->points_to()->forwarded(); + go_assert(!identical(p1, p2)); + return sort(p1, p2); + } + + case Type::TYPE_STRUCT: + { + const Struct_type* s1 = t1->struct_type(); + const Struct_type* s2 = t2->struct_type(); + const Struct_field_list* f1 = s1->fields(); + const Struct_field_list* f2 = s2->fields(); + go_assert(f1 != NULL && f2 != NULL); + Struct_field_list::const_iterator p1 = f1->begin(); + Struct_field_list::const_iterator p2 = f2->begin(); + for (; p2 != f2->end(); ++p1, ++p2) + { + go_assert(p1 != f1->end()); + go_assert(p1->field_name() == p2->field_name()); + go_assert(p1->is_anonymous() == p2->is_anonymous()); + const Type* ft1 = p1->type()->forwarded(); + const Type* ft2 = p2->type()->forwarded(); + if (!identical(ft1, ft2)) + return sort(ft1, ft2); + } + go_assert(p1 == f1->end()); + go_unreachable(); + } + + case Type::TYPE_ARRAY: + { + const Type* e1 = t1->array_type()->element_type()->forwarded(); + const Type* e2 = t2->array_type()->element_type()->forwarded(); + go_assert(!identical(e1, e2)); + return sort(e1, e2); + } + + case Type::TYPE_MAP: + { + const Map_type* m1 = t1->map_type(); + const Map_type* m2 = t2->map_type(); + const Type* k1 = m1->key_type()->forwarded(); + const Type* k2 = m2->key_type()->forwarded(); + if (!identical(k1, k2)) + return sort(k1, k2); + const Type* v1 = m1->val_type()->forwarded(); + const Type* v2 = m2->val_type()->forwarded(); + go_assert(!identical(v1, v2)); + return sort(v1, v2); + } + + case Type::TYPE_CHANNEL: + { + const Type* e1 = t1->channel_type()->element_type()->forwarded(); + const Type* e2 = t2->channel_type()->element_type()->forwarded(); + go_assert(!identical(e1, e2)); + return sort(e1, e2); + } + + case Type::TYPE_INTERFACE: + { + const Interface_type* it1 = t1->interface_type(); + const Interface_type* it2 = t2->interface_type(); + const Typed_identifier_list* m1 = it1->local_methods(); + const Typed_identifier_list* m2 = it2->local_methods(); + + // We know the full method lists are the same, because the + // mangled type names were the same, but here we are looking + // at the local method lists, which include embedded + // interfaces, and we can have an embedded empty interface. + if (m1 == NULL || m1->empty()) + { + go_assert(m2 != NULL && !m2->empty()); + return true; + } + else if (m2 == NULL || m2->empty()) + { + go_assert(m1 != NULL && !m1->empty()); + return false; + } + + int i = compare_til(m1, m2); + if (i < 0) + return false; + else if (i > 0) + return true; + else + go_unreachable(); + } + } } }; +// Compare Typed_identifier_list's with Sort_types, returning -1, 0, +1. + +static int +compare_til( + const Typed_identifier_list* til1, + const Typed_identifier_list* til2) +{ + Type_alias_identical identical; + Sort_types sort; + Typed_identifier_list::const_iterator p1 = til1->begin(); + Typed_identifier_list::const_iterator p2 = til2->begin(); + for (; p2 != til2->end(); ++p1, ++p2) + { + if (p1 == til1->end()) + return -1; + const Type* t1 = p1->type()->forwarded(); + const Type* t2 = p2->type()->forwarded(); + if (!identical(t1, t2)) + { + if (sort(t1, t2)) + return -1; + else + return +1; + } + } + if (p1 != til1->end()) + return +1; + return 0; +} + // Export those identifiers marked for exporting. void @@ -714,17 +967,9 @@ bool Export::record_type(Type* type) { type = type->forwarded(); - std::pair ins = this->impl_->type_refs.insert(std::make_pair(type, 0)); - if (!ins.second) - { - // We've already seen this type. - return false; - } - ins.first->second = 0; - - return true; + return ins.second; } // Assign the specified type an index. @@ -733,13 +978,12 @@ void Export::set_type_index(const Type* type) { type = type->forwarded(); - std::pair ins = - this->impl_->type_refs.insert(std::make_pair(type, 0)); - go_assert(!ins.second); + Type_refs::iterator p = this->impl_->type_refs.find(type); + go_assert(p != this->impl_->type_refs.end()); int index = this->type_index_; ++this->type_index_; - go_assert(ins.first->second == 0); - ins.first->second = index; + go_assert(p->second == 0); + p->second = index; } // This helper assigns type indices to all types mentioned directly or @@ -758,9 +1002,6 @@ Export::assign_type_indices(const std::vector& sorted_exports) { if (!(*p)->is_type()) continue; - Interface_type* it = (*p)->type_value()->interface_type(); - if (it != NULL) - it->sort_embedded(); this->record_type((*p)->type_value()); this->set_type_index((*p)->type_value()); } diff --git a/gcc/go/gofrontend/types.cc b/gcc/go/gofrontend/types.cc index ef656705037..a8e309041e7 100644 --- a/gcc/go/gofrontend/types.cc +++ b/gcc/go/gofrontend/types.cc @@ -9031,6 +9031,9 @@ Interface_type::finalize_methods() if (this->parse_methods_ == NULL) return; + // The exporter uses parse_methods_. + this->parse_methods_->sort_by_name(); + this->all_methods_ = new Typed_identifier_list(); this->all_methods_->reserve(this->parse_methods_->size()); Typed_identifier_list inherit; @@ -9318,15 +9321,17 @@ Interface_type::is_compatible_for_assign(const Interface_type* t, // Hash code. unsigned int -Interface_type::do_hash_for_method(Gogo*, int) const +Interface_type::do_hash_for_method(Gogo*, int flags) const { go_assert(this->methods_are_finalized_); + Typed_identifier_list* methods = (((flags & COMPARE_EMBEDDED_INTERFACES) != 0) + ? this->parse_methods_ + : this->all_methods_); unsigned int ret = 0; - if (this->all_methods_ != NULL) + if (methods != NULL) { - for (Typed_identifier_list::const_iterator p = - this->all_methods_->begin(); - p != this->all_methods_->end(); + for (Typed_identifier_list::const_iterator p = methods->begin(); + p != methods->end(); ++p) { ret = Gogo::hash_string(p->name(), ret); diff --git a/gcc/go/gofrontend/types.h b/gcc/go/gofrontend/types.h index 6d72e09ecf1..49404bd6127 100644 --- a/gcc/go/gofrontend/types.h +++ b/gcc/go/gofrontend/types.h @@ -3272,15 +3272,6 @@ class Interface_type : public Type methods_are_finalized() const { return this->methods_are_finalized_; } - // Sort embedded interfaces by name. Needed when we are preparing - // to emit types into the export data. - void - sort_embedded() - { - if (parse_methods_ != NULL) - parse_methods_->sort_by_name(); - } - protected: int do_traverse(Traverse*);