From patchwork Thu Jan 27 22:29:34 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 50504 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 302293858039 for ; Thu, 27 Jan 2022 22:30:09 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 302293858039 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1643322609; bh=gBHcxoNrLbianYyimbvWEkmFU7zVnT2hMBGLLH41PIo=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=kl5AfuA1pjzZB+XzEQcmDWMghk+kMCUT14WnFv1WKjt2IQBz7oXN47guq5PPWHP66 uu2bOppXDo7GYkuPS2fTrb4TIrCfn8LAPIQl2MqB7OMMsXIINdQvDUCtuJjzgY5elK J0Pycx807wrzsIe3/v8rF3y869H+wVSz0AsxvA3A= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 3024B3858430 for ; Thu, 27 Jan 2022 22:29:40 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 3024B3858430 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-646-YMmgdoRgNf-nJwz-z330Aw-1; Thu, 27 Jan 2022 17:29:37 -0500 X-MC-Unique: YMmgdoRgNf-nJwz-z330Aw-1 Received: from smtp.corp.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id F08978143EA; Thu, 27 Jan 2022 22:29:35 +0000 (UTC) Received: from localhost (unknown [10.33.37.88]) by smtp.corp.redhat.com (Postfix) with ESMTP id 9077B5DB94; Thu, 27 Jan 2022 22:29:35 +0000 (UTC) To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [committed] libstdc++: Avoid overflow in ranges::advance(i, n, bound) Date: Thu, 27 Jan 2022 22:29:34 +0000 Message-Id: <20220127222934.1104717-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.11 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com 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_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) 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: Jonathan Wakely via Gcc-patches From: Jonathan Wakely Reply-To: Jonathan Wakely Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" Tested powerpc64le-linux, pushed to trunk. Should be backported too. When (bound - i) or n is the most negative value of its type, the negative of the value will overflow. Instead of abs(n) >= abs(bound - i) use n >= (bound - i) when positive and n <= (bound - i) when negative. The function has a precondition that they must have the same sign, so this works correctly. The precondition check can be moved into the else branch, and simplified. The standard requires calling ranges::advance(i, bound) even if i==bound is already true, which is technically observable, but that's pointless. We can just return n in that case. Similarly, for i!=bound but n==0 we are supposed to call ranges::advance(i, n), but that's pointless. An LWG issue to allow omitting the pointless calls is expected to be filed. libstdc++-v3/ChangeLog: * include/bits/ranges_base.h (ranges::advance): Avoid signed overflow. Do nothing if already equal to desired result. * testsuite/24_iterators/range_operations/advance_overflow.cc: New test. --- libstdc++-v3/include/bits/ranges_base.h | 15 +++++--- .../range_operations/advance_overflow.cc | 37 +++++++++++++++++++ 2 files changed, 46 insertions(+), 6 deletions(-) create mode 100644 libstdc++-v3/testsuite/24_iterators/range_operations/advance_overflow.cc diff --git a/libstdc++-v3/include/bits/ranges_base.h b/libstdc++-v3/include/bits/ranges_base.h index 08e99ebc5d3..3c5f4b1790a 100644 --- a/libstdc++-v3/include/bits/ranges_base.h +++ b/libstdc++-v3/include/bits/ranges_base.h @@ -756,20 +756,23 @@ namespace ranges { const auto __diff = __bound - __it; - // n and bound must not lead in opposite directions: - __glibcxx_assert(__n == 0 || __diff == 0 || (__n < 0 == __diff < 0)); - const auto __absdiff = __diff < 0 ? -__diff : __diff; - const auto __absn = __n < 0 ? -__n : __n;; - if (__absn >= __absdiff) + if (__diff == 0) + return __n; + else if (__diff > 0 ? __n >= __diff : __n <= __diff) { (*this)(__it, __bound); return __n - __diff; } - else + else if (__n != 0) [[likely]] { + // n and bound must not lead in opposite directions: + __glibcxx_assert(__n < 0 == __diff < 0); + (*this)(__it, __n); return 0; } + else + return 0; } else if (__it == __bound || __n == 0) return __n; diff --git a/libstdc++-v3/testsuite/24_iterators/range_operations/advance_overflow.cc b/libstdc++-v3/testsuite/24_iterators/range_operations/advance_overflow.cc new file mode 100644 index 00000000000..0fadcd6e99a --- /dev/null +++ b/libstdc++-v3/testsuite/24_iterators/range_operations/advance_overflow.cc @@ -0,0 +1,37 @@ +// { dg-options "-std=gnu++20" } +// { dg-do compile { target c++20 } } + +// Public domain testcase from Casey Carter, send to LWG list on 2021-07-24. +// +// Here's a compile-only test case for which n is INT_MIN, which will overflow +// if simply negated to get |n|: https://godbolt.org/z/M7Wz1nW58. + +#include +#include +#include + +struct I { + using difference_type = int; + using value_type = int; + + int x; + + constexpr int operator*() const { return x; } + constexpr I& operator++() { ++x; return *this; } + constexpr I operator++(int) { ++x; return {x - 1}; } + constexpr bool operator==(const I&) const = default; + + constexpr int operator-(const I& that) const { return x - that.x; } + + constexpr I& operator--() { --x; return *this; } + constexpr I operator--(int) { --x; return {x - 1}; } +}; +static_assert(std::bidirectional_iterator); +static_assert(std::sized_sentinel_for); + +constexpr bool test() { + using L = std::numeric_limits; + I i{-2}; + return std::ranges::advance(i, L::min(), I{-4}) == L::min() + 2; +} +static_assert(test());