From patchwork Fri Feb 28 19:59:01 2020 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Patrick Palka X-Patchwork-Id: 1246820 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-520349-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha1 header.s=default header.b=c93vmBE1; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.a=rsa-sha256 header.s=mimecast20190719 header.b=c5sOgR9M; dkim-atps=neutral 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 48TgNp4mv3z9sPK for ; Sat, 29 Feb 2020 06:59:37 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:mime-version:content-type :content-transfer-encoding; q=dns; s=default; b=XBM0yNM4lYzgH1xZ wVFiTPxCwbMX5x9hcU/KFhDiNZUh83aTvoxc8WbodDN3Qpv+xoroM0YZaz9bJPDu lIeMmdWo13CqLvi2Lk5MtviTfhB1Y75p1YK8H0QTSmuTYycfUpwe8mDbxioxzhtP SAl9KeGNfqhbwPxY8C1+bnLOWd4= 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:from :to:cc:subject:date:message-id:mime-version:content-type :content-transfer-encoding; s=default; bh=BqN3oGkX0bzEed+RD72aBy c+CgY=; b=c93vmBE1UQBBCPQ2bT3ydgmG5lZ4dtMUTsg81kFnh9BIOmHoYoxfLQ bAtGGrUE8ytJS2uSK9V6PQKDWD+nIVFY/meHju4WyJ2ygagjv6BcycEas7Lwq1LU 5vQ/Qp8pZ2oK4lLCD54Ly09xin7yq/Q8/rTac0rlsof75ZRLYhP40= Received: (qmail 76711 invoked by alias); 28 Feb 2020 19:59:23 -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 76653 invoked by uid 89); 28 Feb 2020 19:59:23 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-25.4 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, RCVD_IN_DNSWL_NONE autolearn=unavailable version=3.3.1 spammy= X-HELO: us-smtp-delivery-1.mimecast.com Received: from us-smtp-2.mimecast.com (HELO us-smtp-delivery-1.mimecast.com) (207.211.31.81) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 28 Feb 2020 19:59:21 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1582919959; 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=s+wd8hnNDdSAJEkabjdmU/xtQVh4tb4vp0QtgNxz6qY=; b=c5sOgR9MSMLhgDYy2QxGV2DuUGCPawm5r36MvzwQgFTlbsRZY8cd4RZQyU0cRtuiCt5fuD cgGkL3hNWJUPmd+LtB+IRNikDNqs+tPV8WwAxFJThjLuxVj7v4sbxzFjDmcTCf/uiDZA+G FXi8voxXMg6tv+dQ3M8c72DBn9Puhc0= Received: from mail-qk1-f200.google.com (mail-qk1-f200.google.com [209.85.222.200]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-311-9zRxkFY1Po-rEAQDT-jWJQ-1; Fri, 28 Feb 2020 14:59:11 -0500 Received: by mail-qk1-f200.google.com with SMTP id 205so3876345qkg.0 for ; Fri, 28 Feb 2020 11:59:11 -0800 (PST) Received: from localhost.localdomain (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id f7sm6053310qtc.29.2020.02.28.11.59.09 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 28 Feb 2020 11:59:09 -0800 (PST) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH] libstdc++: Fix bogus use of memcmp in ranges::lexicographical_compare (PR 93972) Date: Fri, 28 Feb 2020 14:59:01 -0500 Message-Id: <20200228195901.1918627-1-ppalka@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-IsSubscribed: yes We were enabling the memcmp optimization in ranges::lexicographical_compare for signed integral types and for integral types larger than a byte. But memcmp gives the wrong answer for arrays of such types. This patch fixes this issue by refining the condition that enables the memcmp optimization. It's now consistent with the corresponding condition used in std::lexicographical_compare. libstdc++-v3/ChangeLog: PR libstdc++/93972 * include/bits/ranges_algo.h (__lexicographical_compare_fn::operator()): Fix condition for when to use memcmp, making it consistent with the corresponding condition used in std::lexicographical_compare. * testsuite/25_algorithms/lexicographical_compare/93972.cc: New test. --- libstdc++-v3/include/bits/ranges_algo.h | 8 +- .../lexicographical_compare/93972.cc | 169 ++++++++++++++++++ 2 files changed, 175 insertions(+), 2 deletions(-) create mode 100644 libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 05c0851d411..8fa4a8a9161 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -3466,9 +3466,13 @@ namespace ranges { using _ValueType1 = iter_value_t<_Iter1>; using _ValueType2 = iter_value_t<_Iter2>; + // This condition is consistent with the one in + // __lexicographical_compare_aux in . constexpr bool __use_memcmp - = ((is_integral_v<_ValueType1> || is_pointer_v<_ValueType1>) - && is_same_v<_ValueType1, _ValueType2> + = (__is_byte<_ValueType1>::__value + && __is_byte<_ValueType2>::__value + && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed + && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed && is_pointer_v<_Iter1> && is_pointer_v<_Iter2> && (is_same_v<_Comp, ranges::less> diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc new file mode 100644 index 00000000000..53c4e0daddc --- /dev/null +++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare/93972.cc @@ -0,0 +1,169 @@ +// Copyright (C) 2020 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +#include +#include + +using std::signed_integral; + +namespace ranges = std::ranges; + +template +void +test01() +{ + T i[] = { -1 }; + T j[] = { 1 }; + + VERIFY( ranges::lexicographical_compare(i, j) ); + VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) ); + + VERIFY( !ranges::lexicographical_compare(j, i) ); + VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) ); +} + +template +void +test02() +{ + T i[] = { -5 }; + T j[] = { -5, 3 }; + + VERIFY( ranges::lexicographical_compare(i, j) ); + VERIFY( ranges::lexicographical_compare(i, j, ranges::greater{}) ); + + VERIFY( !ranges::lexicographical_compare(j, i) ); + VERIFY( !ranges::lexicographical_compare(j, i, ranges::greater{}) ); +} + +template +void +test03() +{ + T i[] = { -10 }; + T j[] = { -5, 3 }; + + VERIFY( ranges::lexicographical_compare(i, j) ); + VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) ); + + VERIFY( !ranges::lexicographical_compare(j, i) ); + VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) ); +} + +template +void +test04() +{ + T i[] = { -2 }; + T j[] = { -5, 3 }; + + VERIFY( !ranges::lexicographical_compare(i, j) ); + VERIFY( ranges::lexicographical_compare(i, j, ranges::greater{}) ); + + VERIFY( ranges::lexicographical_compare(j, i) ); + VERIFY( !ranges::lexicographical_compare(j, i, ranges::greater{}) ); +} + +void +test05() +{ + unsigned i[] = { 1 }; + unsigned j[] = { 256 }; + + VERIFY( ranges::lexicographical_compare(i, j) ); + VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) ); + + VERIFY( !ranges::lexicographical_compare(j, i) ); + VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) ); +} + +void +test06() +{ + signed char i[] = { 100, 1 }; + unsigned char j[] = { 100 }; + + VERIFY( !ranges::lexicographical_compare(i, j) ); + VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) ); + + VERIFY( ranges::lexicographical_compare(j, i) ); + VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) ); +} + +void +test07() +{ + char i[] = { 95, 1 }; + unsigned char j[] = { 100 }; + + VERIFY( ranges::lexicographical_compare(i, j) ); + VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) ); + + VERIFY( !ranges::lexicographical_compare(j, i) ); + VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) ); +} + +void +test08() +{ + signed char i[] = { 112, 1 }; + signed char j[] = { 87 }; + + VERIFY( !ranges::lexicographical_compare(i, j) ); + VERIFY( ranges::lexicographical_compare(i, j, ranges::greater{}) ); + + VERIFY( ranges::lexicographical_compare(j, i) ); + VERIFY( !ranges::lexicographical_compare(j, i, ranges::greater{}) ); +} + +void +test09() +{ + char i[] = { 1 }; + unsigned char j[] = { 100 }; + + VERIFY( ranges::lexicographical_compare(i, j) ); + VERIFY( !ranges::lexicographical_compare(i, j, ranges::greater{}) ); + + VERIFY( !ranges::lexicographical_compare(j, i) ); + VERIFY( ranges::lexicographical_compare(j, i, ranges::greater{}) ); +} + +int +main() +{ + test01(); + test01(); + + test02(); + test02(); + + test03(); + test03(); + + test04(); + test04(); + + test05(); + test06(); + test07(); + test08(); + test09(); +}