From patchwork Sun Oct 30 16:48:41 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Lance Taylor X-Patchwork-Id: 688977 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 3t6Nk72yl4z9t1H for ; Mon, 31 Oct 2016 03:49:03 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b=gFNcHfL0; 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 :mime-version:from:date:message-id:subject:to:content-type; q= dns; s=default; b=gaIHEELGdqboX75gqGLrw4LvB53POaETc6bKO0AUlA9BRn priMbhmZ5BOBG4QuyuwVTp5NnOJ6W27mAGxZ8lOalo3HZl2AeHpcZJ6HjlSoNPLI pL7JnPuuls8X77kD8pf75P4RXkkSff1PP8kEQgoajR3EHsHYnAg0qWZ9qKGog= 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 :mime-version:from:date:message-id:subject:to:content-type; s= default; bh=nMYurd0XoBzeYrgVteeMum8zed0=; b=gFNcHfL0OfVqPDLQNfPi 3PbnjLyZ4OQoAxwmVMhaSlcpln/kf7PkZuO8Yip8Akcz+VPhHAnMbI6RZ1KPllZr 1isRQy4CpvyLjN3R2kSpItszrYnVjRLXwyOe8khq82hPicJP093M7xf1hbqk1b0h Afwn+ikX0gx2cDC1vJ+elpA= Received: (qmail 103729 invoked by alias); 30 Oct 2016 16:48:54 -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 103714 invoked by uid 89); 30 Oct 2016 16:48:53 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=1.3 required=5.0 tests=AWL, BAYES_50, KAM_ASCII_DIVIDERS, RCVD_IN_DNSWL_LOW, RCVD_IN_SORBS_SPAM, SPF_PASS autolearn=no version=3.3.2 spammy=H*Ad:D*googlegroups.com, Class, ownership, Extra X-HELO: mail-it0-f53.google.com Received: from mail-it0-f53.google.com (HELO mail-it0-f53.google.com) (209.85.214.53) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Sun, 30 Oct 2016 16:48:43 +0000 Received: by mail-it0-f53.google.com with SMTP id q124so63508872itd.1 for ; Sun, 30 Oct 2016 09:48:43 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=qEXyVTUk/9rGUHzNXyu/o/piNCspmqSGofBFk6+49tc=; b=jm+pSqfXaCBIeyf8BZGIs4PpKnXqA5k8eWJ73e1Qw6/SI1IT0ca4L6qcHDJ4i/HBI8 Yyv/OVVNwvdpeSvI4UkrCDzEP7UkklLiwQgA8+I4z4lxdNaOitZBxaOKKHrJpxvIstJ6 Gx7G382QSBGqYjpav7PfElqELyhKLjG3JRs0IB5s5AoCdjy8bZhBr533GqELlA5WBW3K RP0EamkzFoF/4rTL1UQ8nPVvf+ohAA5mHUyz5F+mAkLbI2tciOy+oPL25RU7MQ9YGaxG zrzAKJETFUUgfWGQMI9gBo9Ue+JuAy07TsVzeW1zJ9Ay3fCx75sgkgO/w5Ibc6tzURTK qNkw== X-Gm-Message-State: ABUngvfnIWKal1iwhyG/0PiW8Kb759Ct/v8ZCKuZzUjKGlEO3VnnYNMSAK3Bk6faBvWgySwItELV/IAsvpa9cA== X-Received: by 10.107.28.148 with SMTP id c142mr17207132ioc.45.1477846121993; Sun, 30 Oct 2016 09:48:41 -0700 (PDT) MIME-Version: 1.0 Received: by 10.79.154.155 with HTTP; Sun, 30 Oct 2016 09:48:41 -0700 (PDT) From: Ian Lance Taylor Date: Sun, 30 Oct 2016 09:48:41 -0700 Message-ID: Subject: Go patch committed: Fix slice/array evaluation order bug To: gcc-patches , "gofrontend-dev@googlegroups.com" This patch to the Go frontend by Than McIntosh fixes an order-of-evaluation bug in slice/array composite literals. There was a phase ordering issue in the handling of "keyed" array literal expressions: the lowering phase was canonicalizing the indices/vals before the phase that fixed evaluation order, meaning that the evaluation order was incorrect. The fix is to capture the original ordering and use that ordering when doing traversals (there is already something similar being done for struct literal expressions). This fixes https://golang.org/issue/17640. Bootstrapped and ran Go testsuite on x86_64-pc-linux-gnu. Committed to mainline. Ian Index: gcc/go/gofrontend/MERGE =================================================================== --- gcc/go/gofrontend/MERGE (revision 241687) +++ gcc/go/gofrontend/MERGE (working copy) @@ -1,4 +1,4 @@ -4ca21c94f00c620bfde2f924e214c78fe2e1ff69 +c353ffbe18d1538cac7f2a3fcefb846dbf1a6591 The first line of this file holds the git revision number of the last merge done from the gofrontend repository. Index: gcc/go/gofrontend/expressions.cc =================================================================== --- gcc/go/gofrontend/expressions.cc (revision 241667) +++ gcc/go/gofrontend/expressions.cc (working copy) @@ -12202,12 +12202,10 @@ Expression::make_allocation(Type* type, return new Allocation_expression(type, location); } -// Class Struct_construction_expression. - -// Traversal. +// Class Ordered_value_list. int -Struct_construction_expression::do_traverse(Traverse* traverse) +Ordered_value_list::traverse_vals(Traverse* traverse) { if (this->vals_ != NULL) { @@ -12218,8 +12216,8 @@ Struct_construction_expression::do_trave } else { - for (std::vector::const_iterator p = - this->traverse_order_->begin(); + for (std::vector::const_iterator p = + this->traverse_order_->begin(); p != this->traverse_order_->end(); ++p) { @@ -12229,6 +12227,18 @@ Struct_construction_expression::do_trave } } } + return TRAVERSE_CONTINUE; +} + +// Class Struct_construction_expression. + +// Traversal. + +int +Struct_construction_expression::do_traverse(Traverse* traverse) +{ + if (this->traverse_vals(traverse) == TRAVERSE_EXIT) + return TRAVERSE_EXIT; if (Type::traverse(this->type_, traverse) == TRAVERSE_EXIT) return TRAVERSE_EXIT; return TRAVERSE_CONTINUE; @@ -12239,10 +12249,10 @@ Struct_construction_expression::do_trave bool Struct_construction_expression::is_constant_struct() const { - if (this->vals_ == NULL) + if (this->vals() == NULL) return true; - for (Expression_list::const_iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv) { if (*pv != NULL @@ -12270,10 +12280,10 @@ Struct_construction_expression::is_const bool Struct_construction_expression::do_is_immutable() const { - if (this->vals_ == NULL) + if (this->vals() == NULL) return true; - for (Expression_list::const_iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv) { if (*pv != NULL && !(*pv)->is_immutable()) @@ -12287,15 +12297,15 @@ Struct_construction_expression::do_is_im void Struct_construction_expression::do_determine_type(const Type_context*) { - if (this->vals_ == NULL) + if (this->vals() == NULL) return; const Struct_field_list* fields = this->type_->struct_type()->fields(); - Expression_list::const_iterator pv = this->vals_->begin(); + Expression_list::const_iterator pv = this->vals()->begin(); for (Struct_field_list::const_iterator pf = fields->begin(); pf != fields->end(); ++pf, ++pv) { - if (pv == this->vals_->end()) + if (pv == this->vals()->end()) return; if (*pv != NULL) { @@ -12305,7 +12315,7 @@ Struct_construction_expression::do_deter } // Extra values are an error we will report elsewhere; we still want // to determine the type to avoid knockon errors. - for (; pv != this->vals_->end(); ++pv) + for (; pv != this->vals()->end(); ++pv) (*pv)->determine_type_no_context(); } @@ -12314,24 +12324,24 @@ Struct_construction_expression::do_deter void Struct_construction_expression::do_check_types(Gogo*) { - if (this->vals_ == NULL) + if (this->vals() == NULL) return; Struct_type* st = this->type_->struct_type(); - if (this->vals_->size() > st->field_count()) + if (this->vals()->size() > st->field_count()) { this->report_error(_("too many expressions for struct")); return; } const Struct_field_list* fields = st->fields(); - Expression_list::const_iterator pv = this->vals_->begin(); + Expression_list::const_iterator pv = this->vals()->begin(); int i = 0; for (Struct_field_list::const_iterator pf = fields->begin(); pf != fields->end(); ++pf, ++pv, ++i) { - if (pv == this->vals_->end()) + if (pv == this->vals()->end()) { this->report_error(_("too few expressions for struct")); break; @@ -12355,7 +12365,7 @@ Struct_construction_expression::do_check this->set_is_error(); } } - go_assert(pv == this->vals_->end()); + go_assert(pv == this->vals()->end()); } // Flatten a struct construction expression. Store the values into @@ -12365,7 +12375,7 @@ Expression* Struct_construction_expression::do_flatten(Gogo*, Named_object*, Statement_inserter* inserter) { - if (this->vals_ == NULL) + if (this->vals() == NULL) return this; // If this is a constant struct, we don't need temporaries. @@ -12373,8 +12383,8 @@ Struct_construction_expression::do_flatt return this; Location loc = this->location(); - for (Expression_list::iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv) { if (*pv != NULL) @@ -12404,18 +12414,18 @@ Struct_construction_expression::do_get_b Gogo* gogo = context->gogo(); Btype* btype = this->type_->get_backend(gogo); - if (this->vals_ == NULL) + if (this->vals() == NULL) return gogo->backend()->zero_expression(btype); const Struct_field_list* fields = this->type_->struct_type()->fields(); - Expression_list::const_iterator pv = this->vals_->begin(); + Expression_list::const_iterator pv = this->vals()->begin(); std::vector init; for (Struct_field_list::const_iterator pf = fields->begin(); pf != fields->end(); ++pf) { Btype* fbtype = pf->type()->get_backend(gogo); - if (pv == this->vals_->end()) + if (pv == this->vals()->end()) init.push_back(gogo->backend()->zero_expression(fbtype)); else if (*pv == NULL) { @@ -12441,8 +12451,8 @@ Struct_construction_expression::do_expor { exp->write_c_string("convert("); exp->write_type(this->type_); - for (Expression_list::const_iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv) { exp->write_c_string(", "); @@ -12460,7 +12470,7 @@ Struct_construction_expression::do_dump_ { ast_dump_context->dump_type(this->type_); ast_dump_context->ostream() << "{"; - ast_dump_context->dump_expression_list(this->vals_); + ast_dump_context->dump_expression_list(this->vals()); ast_dump_context->ostream() << "}"; } @@ -12481,8 +12491,7 @@ Expression::make_struct_composite_litera int Array_construction_expression::do_traverse(Traverse* traverse) { - if (this->vals_ != NULL - && this->vals_->traverse(traverse) == TRAVERSE_EXIT) + if (this->traverse_vals(traverse) == TRAVERSE_EXIT) return TRAVERSE_EXIT; if (Type::traverse(this->type_, traverse) == TRAVERSE_EXIT) return TRAVERSE_EXIT; @@ -12494,15 +12503,15 @@ Array_construction_expression::do_traver bool Array_construction_expression::is_constant_array() const { - if (this->vals_ == NULL) + if (this->vals() == NULL) return true; // There are no constant constructors for interfaces. if (this->type_->array_type()->element_type()->interface_type() != NULL) return false; - for (Expression_list::const_iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv) { if (*pv != NULL @@ -12519,10 +12528,10 @@ Array_construction_expression::is_consta bool Array_construction_expression::do_is_immutable() const { - if (this->vals_ == NULL) + if (this->vals() == NULL) return true; - for (Expression_list::const_iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv) { if (*pv != NULL && !(*pv)->is_immutable()) @@ -12536,11 +12545,11 @@ Array_construction_expression::do_is_imm void Array_construction_expression::do_determine_type(const Type_context*) { - if (this->vals_ == NULL) + if (this->vals() == NULL) return; Type_context subcontext(this->type_->array_type()->element_type(), false); - for (Expression_list::const_iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv) { if (*pv != NULL) @@ -12553,14 +12562,14 @@ Array_construction_expression::do_determ void Array_construction_expression::do_check_types(Gogo*) { - if (this->vals_ == NULL) + if (this->vals() == NULL) return; Array_type* at = this->type_->array_type(); int i = 0; Type* element_type = at->element_type(); - for (Expression_list::const_iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv, ++i) { if (*pv != NULL @@ -12581,7 +12590,7 @@ Expression* Array_construction_expression::do_flatten(Gogo*, Named_object*, Statement_inserter* inserter) { - if (this->vals_ == NULL) + if (this->vals() == NULL) return this; // If this is a constant array, we don't need temporaries. @@ -12589,8 +12598,8 @@ Array_construction_expression::do_flatte return this; Location loc = this->location(); - for (Expression_list::iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv) { if (*pv != NULL) @@ -12623,14 +12632,14 @@ Array_construction_expression::get_const std::vector indexes; std::vector vals; Gogo* gogo = context->gogo(); - if (this->vals_ != NULL) + if (this->vals() != NULL) { size_t i = 0; std::vector::const_iterator pi; if (this->indexes_ != NULL) pi = this->indexes_->begin(); - for (Expression_list::const_iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv, ++i) { if (this->indexes_ != NULL) @@ -12670,13 +12679,13 @@ Array_construction_expression::do_export { exp->write_c_string("convert("); exp->write_type(this->type_); - if (this->vals_ != NULL) + if (this->vals() != NULL) { std::vector::const_iterator pi; if (this->indexes_ != NULL) pi = this->indexes_->begin(); - for (Expression_list::const_iterator pv = this->vals_->begin(); - pv != this->vals_->end(); + for (Expression_list::const_iterator pv = this->vals()->begin(); + pv != this->vals()->end(); ++pv) { exp->write_c_string(", "); @@ -12717,10 +12726,10 @@ Array_construction_expression::do_dump_e this->dump_slice_storage_expression(ast_dump_context); ast_dump_context->ostream() << "{" ; if (this->indexes_ == NULL) - ast_dump_context->dump_expression_list(this->vals_); + ast_dump_context->dump_expression_list(this->vals()); else { - Expression_list::const_iterator pv = this->vals_->begin(); + Expression_list::const_iterator pv = this->vals()->begin(); for (std::vector::const_iterator pi = this->indexes_->begin(); pi != this->indexes_->end(); @@ -13349,7 +13358,7 @@ Composite_literal_expression::lower_stru size_t field_count = st->field_count(); std::vector vals(field_count); - std::vector* traverse_order = new(std::vector); + std::vector* traverse_order = new(std::vector); Expression_list::const_iterator p = this->vals_->begin(); Expression* external_expr = NULL; const Named_object* external_no = NULL; @@ -13481,7 +13490,7 @@ Composite_literal_expression::lower_stru type->named_type()->message_name().c_str()); vals[index] = val; - traverse_order->push_back(index); + traverse_order->push_back(static_cast(index)); } if (!this->all_are_names_) @@ -13512,15 +13521,16 @@ Composite_literal_expression::lower_stru return ret; } -// Used to sort an index/value array. +// Index/value/traversal-order triple. -class Index_value_compare -{ - public: - bool - operator()(const std::pair& a, - const std::pair& b) - { return a.first < b.first; } +struct IVT_triple { + unsigned long index; + unsigned long traversal_order; + Expression* expr; + IVT_triple(unsigned long i, unsigned long to, Expression *e) + : index(i), traversal_order(to), expr(e) { } + bool operator<(const IVT_triple& other) const + { return this->index < other.index; } }; // Lower an array composite literal. @@ -13624,35 +13634,45 @@ Composite_literal_expression::lower_arra indexes = NULL; } + std::vector* traverse_order = NULL; if (indexes_out_of_order) { - typedef std::vector > V; + typedef std::vector V; V v; v.reserve(indexes->size()); std::vector::const_iterator pi = indexes->begin(); + unsigned long torder = 0; for (Expression_list::const_iterator pe = vals->begin(); pe != vals->end(); - ++pe, ++pi) - v.push_back(std::make_pair(*pi, *pe)); + ++pe, ++pi, ++torder) + v.push_back(IVT_triple(*pi, torder, *pe)); - std::sort(v.begin(), v.end(), Index_value_compare()); + std::sort(v.begin(), v.end()); delete indexes; delete vals; + indexes = new std::vector(); indexes->reserve(v.size()); vals = new Expression_list(); vals->reserve(v.size()); + traverse_order = new std::vector(); + traverse_order->reserve(v.size()); for (V::const_iterator p = v.begin(); p != v.end(); ++p) { - indexes->push_back(p->first); - vals->push_back(p->second); + indexes->push_back(p->index); + vals->push_back(p->expr); + traverse_order->push_back(p->traversal_order); } } - return this->make_array(type, indexes, vals); + Expression* ret = this->make_array(type, indexes, vals); + Array_construction_expression* ace = ret->array_literal(); + if (ace != NULL && traverse_order != NULL) + ace->set_traverse_order(traverse_order); + return ret; } // Actually build the array composite literal. This handles Index: gcc/go/gofrontend/expressions.h =================================================================== --- gcc/go/gofrontend/expressions.h (revision 241341) +++ gcc/go/gofrontend/expressions.h (working copy) @@ -3232,31 +3232,64 @@ class Composite_literal_expression : pub std::vector key_path_; }; -// Construct a struct. +// Helper/mixin class for struct and array construction expressions; +// encapsulates a list of values plus an optional traversal order +// recording the order in which the values should be visited. -class Struct_construction_expression : public Expression +class Ordered_value_list { public: - Struct_construction_expression(Type* type, Expression_list* vals, - Location location) - : Expression(EXPRESSION_STRUCT_CONSTRUCTION, location), - type_(type), vals_(vals), traverse_order_(NULL) + Ordered_value_list(Expression_list* vals) + : vals_(vals), traverse_order_(NULL) { } + Expression_list* + vals() const + { return this->vals_; } + + int + traverse_vals(Traverse* traverse); + + // Get the traversal order (may be NULL) + std::vector* + traverse_order() + { return traverse_order_; } + // Set the traversal order, used to ensure that we implement the // order of evaluation rules. Takes ownership of the argument. void - set_traverse_order(std::vector* traverse_order) + set_traverse_order(std::vector* traverse_order) { this->traverse_order_ = traverse_order; } - // Return whether this is a constant initializer. + private: + // The list of values, in order of the fields in the struct or in + // order of indices in an array. A NULL value of vals_ means that + // all fields/slots should be zero-initialized; a single NULL entry + // in the list means that the corresponding field or array slot + // should be zero-initialized. + Expression_list* vals_; + // If not NULL, the order in which to traverse vals_. This is used + // so that we implement the order of evaluation rules correctly. + std::vector* traverse_order_; +}; + +// Construct a struct. + +class Struct_construction_expression : public Expression, + public Ordered_value_list +{ + public: + Struct_construction_expression(Type* type, Expression_list* vals, + Location location) + : Expression(EXPRESSION_STRUCT_CONSTRUCTION, location), + Ordered_value_list(vals), + type_(type) + { } + + // Return whether this is a constant initializer. bool is_constant_struct() const; - Expression_list* - vals() const - { return this->vals_; } - protected: int do_traverse(Traverse* traverse); @@ -3279,12 +3312,12 @@ class Struct_construction_expression : p { Struct_construction_expression* ret = new Struct_construction_expression(this->type_, - (this->vals_ == NULL + (this->vals() == NULL ? NULL - : this->vals_->copy()), + : this->vals()->copy()), this->location()); - if (this->traverse_order_ != NULL) - ret->set_traverse_order(this->traverse_order_); + if (this->traverse_order() != NULL) + ret->set_traverse_order(this->traverse_order()); return ret; } @@ -3303,19 +3336,14 @@ class Struct_construction_expression : p private: // The type of the struct to construct. Type* type_; - // The list of values, in order of the fields in the struct. A NULL - // entry means that the field should be zero-initialized. - Expression_list* vals_; - // If not NULL, the order in which to traverse vals_. This is used - // so that we implement the order of evaluation rules correctly. - std::vector* traverse_order_; }; // Construct an array. This class is not used directly; instead we // use the child classes, Fixed_array_construction_expression and // Slice_construction_expression. -class Array_construction_expression : public Expression +class Array_construction_expression : public Expression, + public Ordered_value_list { protected: Array_construction_expression(Expression_classification classification, @@ -3323,7 +3351,8 @@ class Array_construction_expression : pu const std::vector* indexes, Expression_list* vals, Location location) : Expression(classification, location), - type_(type), indexes_(indexes), vals_(vals) + Ordered_value_list(vals), + type_(type), indexes_(indexes) { go_assert(indexes == NULL || indexes->size() == vals->size()); } public: @@ -3334,12 +3363,7 @@ class Array_construction_expression : pu // Return the number of elements. size_t element_count() const - { return this->vals_ == NULL ? 0 : this->vals_->size(); } - - // The list of values. - Expression_list* - vals() const - { return this->vals_; } + { return this->vals() == NULL ? 0 : this->vals()->size(); } protected: virtual int @@ -3385,8 +3409,6 @@ protected: // The list of indexes into the array, one for each value. This may // be NULL, in which case the indexes start at zero and increment. const std::vector* indexes_; - // The list of values. This may be NULL if there are no values. - Expression_list* vals_; }; // Construct a fixed array.