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 [216.205.24.124]) by sourceware.org (Postfix) with ESMTP id 67F50394FC10 for ; Thu, 17 Jun 2021 15:22:29 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 67F50394FC10 Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-425-GEkdgL7uN-yRRGxZyJ5TDQ-1; Thu, 17 Jun 2021 11:22:16 -0400 X-MC-Unique: GEkdgL7uN-yRRGxZyJ5TDQ-1 Received: by mail-qt1-f198.google.com with SMTP id d7-20020ac811870000b02901e65f85117bso3437288qtj.18 for ; Thu, 17 Jun 2021 08:22:16 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=eZi0WIu7grbv5WOBsk6nL6IVg5SQxHEhwfvZL6wqL8M=; b=lu8O9c1z6AIDwC/vgfYFAnuqMcyqZ9YhSwnQj/xH8R646h53IdjNQnmkdGnhSfz8v6 Sli9sPK4B/aYx1av5oAtUYM3ZBstEpC8g2esK1we5pl6/47cGLn9zbW0qeddciB9v9kt SBXuRWs5BXh8f/m9TqOMSSYsVS9oEFsifspuusv1eqFyVw7+EzD/pnaaQClrEbnPrCtO OugiGtrM+602nOYuF3ixkznTUGYcPrrFP5z6sA6fYQTTkBxxa9FmLkP8qK2n4UIRbzJl lfomGAqluPd1yNjWhJ4Fn5SvvNfEW6NiKVoB961njZcqnsHY75lpif/wCB7jCYdB9FgL NV4w== X-Gm-Message-State: AOAM5329ZveWYCfatnVAvLLzSqFBhBXq0z5icPNA5yEM570KgWn4Pju7 yat5o58RwDfMAessaxqxuTnCrn0nq9W/jV7uGyUR34FPgDQtw19l7dIzOOVT3ZnMzTZ5fcx74UN TKzBa/bBMZ6ff2B8= X-Received: by 2002:a05:6214:2aa1:: with SMTP id js1mr438609qvb.11.1623943335778; Thu, 17 Jun 2021 08:22:15 -0700 (PDT) X-Google-Smtp-Source: ABdhPJz6IhVH0+cmrILYsmPhbEIdkWaQ31rkuqy+fnx4bTrF7KFvmziTj8KpPmklBosa+mMRFqgzVw== X-Received: by 2002:a05:6214:2aa1:: with SMTP id js1mr438565qvb.11.1623943335325; Thu, 17 Jun 2021 08:22:15 -0700 (PDT) Received: from localhost.localdomain (ool-457d493a.dyn.optonline.net. [69.125.73.58]) by smtp.gmail.com with ESMTPSA id 5sm1933230qkj.99.2021.06.17.08.22.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 17 Jun 2021 08:22:14 -0700 (PDT) From: Patrick Palka To: gcc-patches@gcc.gnu.org Cc: libstdc++@gcc.gnu.org, Patrick Palka Subject: [PATCH 5/5] libstdc++: Implement new views::split as per P2210 Date: Thu, 17 Jun 2021 11:22:06 -0400 Message-Id: <20210617152206.1408001-5-ppalka@redhat.com> X-Mailer: git-send-email 2.32.0.93.g670b81a890 In-Reply-To: <20210617152206.1408001-1-ppalka@redhat.com> References: <20210617152206.1408001-1-ppalka@redhat.com> 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-Spam-Status: No, score=-15.7 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_NUMSUBJECT, KAM_SHORT, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP, URI_HEX autolearn=unavailable autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 17 Jun 2021 15:22:31 -0000 This implements the new views::split as specified by P2210R2 "Superior string splitting". libstdc++-v3/ChangeLog: * include/std/ranges (__non_propagating_cache::operator bool): Define. (split_view): Define as per P2210. (views::__detail::__can_split_view): Define. (views::_Split, views::Split): Define. * testsuite/std/ranges/adaptors/100577.cc (test01, test02): Test views::split. * testsuite/std/ranges/adaptors/split.cc: New test. * testsuite/std/ranges/p2325.cc (test08a): New test. * testsuite/std/ranges/p2367.cc (test01): Test views::split. --- libstdc++-v3/include/std/ranges | 205 ++++++++++++++++++ .../testsuite/std/ranges/adaptors/100577.cc | 16 +- .../testsuite/std/ranges/adaptors/split.cc | 196 +++++++++++++++++ libstdc++-v3/testsuite/std/ranges/p2325.cc | 14 ++ libstdc++-v3/testsuite/std/ranges/p2367.cc | 1 + 5 files changed, 430 insertions(+), 2 deletions(-) create mode 100644 libstdc++-v3/testsuite/std/ranges/adaptors/split.cc diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 78562924bee..42278f128b8 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1195,6 +1195,10 @@ namespace views::__adaptor return *this; } + constexpr explicit + operator bool() const noexcept + { return this->_M_is_engaged(); } + constexpr _Tp& operator*() noexcept { return this->_M_get(); } @@ -3278,6 +3282,207 @@ namespace views::__adaptor inline constexpr _LazySplit lazy_split; } // namespace views + template + requires view<_Vp> && view<_Pattern> + && indirectly_comparable, iterator_t<_Pattern>, + ranges::equal_to> + class split_view : public view_interface> + { + private: + _Pattern _M_pattern = _Pattern(); + __detail::__non_propagating_cache>> _M_cached_begin; + _Vp _M_base = _Vp(); + + struct _Iterator; + struct _Sentinel; + + public: + split_view() requires (default_initializable<_Vp> + && default_initializable<_Pattern>) + = default; + + constexpr + split_view(_Vp __base, _Pattern __pattern) + : _M_pattern(std::move(__pattern)), + _M_base(std::move(__base)) + { } + + template + requires constructible_from<_Vp, views::all_t<_Range>> + && constructible_from<_Pattern, single_view>> + constexpr + split_view(_Range&& __r, range_value_t<_Range> __e) + : _M_pattern(views::single(__e)), + _M_base(views::all(std::forward<_Range>(__r))) + { } + + constexpr _Vp + base() const& requires copyable<_Vp> + { return _M_base; } + + constexpr _Vp + base() && + { return std::move(_M_base); } + + constexpr _Iterator + begin() + { + if (!_M_cached_begin) + _M_cached_begin = _M_find_next(ranges::begin(_M_base)); + return {this, ranges::begin(_M_base), *_M_cached_begin}; + } + + constexpr auto + end() + { + if constexpr (common_range<_Vp>) + return _Iterator{this, ranges::end(_M_base), {}}; + else + return _Sentinel{this}; + } + + constexpr subrange> + _M_find_next(iterator_t<_Vp> __it) + { + auto [__b, __e] = ranges::search(subrange(__it, ranges::end(_M_base)), _M_pattern); + if (__b != ranges::end(_M_base) && ranges::empty(_M_pattern)) + { + ++__b; + ++__e; + } + return {__b, __e}; + } + + private: + struct _Iterator + { + private: + split_view* _M_parent = nullptr; + iterator_t<_Vp> _M_cur = iterator_t<_Vp>(); + subrange> _M_next = subrange>(); + bool _M_trailing_empty = false; + + public: + using iterator_concept = forward_iterator_tag; + using iterator_category = input_iterator_tag; + using value_type = subrange>; + using difference_type = range_difference_t<_Vp>; + + _Iterator() requires default_initializable> = default; + + constexpr + _Iterator(split_view* __parent, + iterator_t<_Vp> __current, + subrange> __next) + : _M_parent(__parent), + _M_cur(std::move(__current)), + _M_next(std::move(__next)) + { } + + constexpr iterator_t<_Vp> + base() const + { return _M_cur; } + + constexpr value_type + operator*() const + { return {_M_cur, _M_next.begin()}; } + + constexpr _Iterator& + operator++() + { + _M_cur = _M_next.begin(); + if (_M_cur != ranges::end(_M_parent->_M_base)) + { + _M_cur = _M_next.end(); + if (_M_cur == ranges::end(_M_parent->_M_base)) + { + _M_trailing_empty = true; + _M_next = {_M_cur, _M_cur}; + } + else + _M_next = _M_parent->_M_find_next(_M_cur); + } + else + _M_trailing_empty = false; + return *this; + } + + constexpr _Iterator + operator++(int) + { + auto __tmp = *this; + ++*this; + return __tmp; + } + + friend constexpr bool + operator==(const _Iterator& __x, const _Iterator& __y) + { + return __x._M_cur == __y._M_cur + && __x._M_trailing_empty == __y._M_trailing_empty; + } + + friend struct _Sentinel; + }; + + struct _Sentinel + { + private: + sentinel_t<_Vp> _M_end = sentinel_t<_Vp>(); + + constexpr bool + _M_equal(const _Iterator& __x) const + { return __x._M_cur == _M_end && !__x._M_trailing_empty; } + + public: + constexpr explicit + _Sentinel(split_view* __parent) + : _M_end(ranges::end(__parent->_M_base)) + { } + + friend constexpr bool + operator==(const _Iterator& __x, const _Sentinel& __y) + { return __y._M_equal(__x); } + }; + }; + + template + split_view(_Range&&, _Pattern&&) + -> split_view, views::all_t<_Pattern>>; + + template + split_view(_Range&&, range_value_t<_Range>) + -> split_view, single_view>>; + + namespace views + { + namespace __detail + { + template + concept __can_split_view + = requires { split_view(std::declval<_Range>(), std::declval<_Pattern>()); }; + } // namespace __detail + + struct _Split : __adaptor::_RangeAdaptor<_Split> + { + template + requires __detail::__can_split_view<_Range, _Pattern> + constexpr auto + operator()(_Range&& __r, _Pattern&& __f) const + { + return split_view(std::forward<_Range>(__r), std::forward<_Pattern>(__f)); + } + + using _RangeAdaptor<_Split>::operator(); + static constexpr int _S_arity = 2; + template + static constexpr bool _S_has_simple_extra_args + = _LazySplit::_S_has_simple_extra_args<_Pattern>; + }; + + inline constexpr _Split split; + } // namespace views + namespace views { struct _Counted diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/100577.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/100577.cc index 5ef7f3f59a7..81f2a62cfaa 100644 --- a/libstdc++-v3/testsuite/std/ranges/adaptors/100577.cc +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/100577.cc @@ -42,8 +42,6 @@ test01() static_assert(__adaptor_has_simple_extra_args); static_assert(!__adaptor_has_simple_extra_args); - // Verify all adaptor closures except for views::lazy_split(pattern) have a simple - // operator(). using views::__adaptor::__closure_has_simple_call_op; __closure_has_simple_call_op auto a00 = views::all; __closure_has_simple_call_op auto a01 = views::transform(std::identity{}); @@ -57,6 +55,7 @@ test01() __closure_has_simple_call_op auto a09 = views::reverse; __closure_has_simple_call_op auto a10 = views::keys; __closure_has_simple_call_op auto a11 = views::lazy_split(' '); + __closure_has_simple_call_op auto a11a = views::split(' '); // Verify composition of simple closures is simple. __closure_has_simple_call_op auto b = (a00 | a01) | (a02 | a03) | (a04 | a05 | a06) | (a07 | a08 | a09 | a10) | a11; @@ -67,6 +66,12 @@ test01() static_assert(!__closure_has_simple_call_op); static_assert(!__closure_has_simple_call_op); static_assert(!__closure_has_simple_call_op); + + // Likewise views::split(non_view_range). + auto a12a = views::split(s); + static_assert(!__closure_has_simple_call_op); + static_assert(!__closure_has_simple_call_op); + static_assert(!__closure_has_simple_call_op); } void @@ -98,6 +103,13 @@ test02() auto a1 = a0 | views::all; a1(x); // { dg-error "no match" } + views::lazy_split(badarg)(x); // { dg-error "deleted function" } + (views::lazy_split(badarg) | views::all)(x); // { dg-error "deleted function" } + auto a0a = views::split(badarg); + a0a(x); // { dg-error "no match" }; + auto a1a = a0a | views::all; + a1a(x); // { dg-error "no match" } + views::take(badarg)(x); // { dg-error "deleted" } views::drop(badarg)(x); // { dg-error "deleted" } (views::take(badarg) | views::all)(x); // { dg-error "deleted" } diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc new file mode 100644 index 00000000000..9e6726cd07f --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/split.cc @@ -0,0 +1,196 @@ +// Copyright (C) 2020-2021 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 +#include +#include +#include +#include + +using __gnu_test::test_range; +using __gnu_test::forward_iterator_wrapper; +using __gnu_test::input_iterator_wrapper; + +namespace ranges = std::ranges; +namespace views = std::ranges::views; + +using namespace std::literals; + +void +test01() +{ + auto from_chars = [] (auto v) { + return std::stoi(std::string(v.data(), v.data() + v.size())); + }; + auto ints = "1.2.3.4"sv + | views::split('.') + | views::transform(from_chars); + VERIFY( ranges::equal(ints, (int[]){1,2,3,4}) ); +} + +// The following testcases were adapted from lazy_split.cc. +namespace from_lazy_split_cc +{ +void +test01() +{ + auto x = "the quick brown fox"sv; + auto p = std::string{" "}; + auto v = x | views::split(views::all(p)); // views::all is needed here after P2281. + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +void +test02() +{ + auto x = "the quick brown fox"sv; + auto v = x | views::split(' '); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +void +test03() +{ + char x[] = "the quick brown fox"; + test_range rx(x, x+sizeof(x)-1); + auto v = rx | views::split(' '); + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +void +test04() +{ + auto x = "the quick brown fox"sv; + std::initializer_list p = {' ', ' '}; + static_assert(!ranges::view); + static_assert(std::same_as>); + auto v = x | views::split(views::all(p)); // views::all is needed here after P2281. + auto i = v.begin(); + VERIFY( ranges::equal(*i++, "the"sv) ); + VERIFY( ranges::equal(*i++, "quick"sv) ); + VERIFY( ranges::equal(*i++, "brown"sv) ); + VERIFY( ranges::equal(*i++, "fox"sv) ); + VERIFY( i == v.end() ); +} + +void +test05() +{ + auto as_string = [](ranges::view auto rng) { + auto in = rng | views::common; + return std::string(in.begin(), in.end()); + }; + std::string str + = "Now is the time for all good men to come to the aid of their county."; + auto rng + = str | views::split(' ') | views::transform(as_string) | views::common; + std::vector words(rng.begin(), rng.end()); + auto not_space_p = [](char c) { return c != ' '; }; + VERIFY( ranges::equal(words | views::join, + str | views::filter(not_space_p)) ); +} + +template +void +test06() +{ + // Verify SFINAE behavior. + std::string s, p; + static_assert(!requires { split(); }); + static_assert(!requires { split(s, p, 0); }); + static_assert(!requires { split(p)(); }); + static_assert(!requires { s | split; }); + + static_assert(!requires { s | split(p); }); + static_assert(!requires { split(p)(s); }); + static_assert(!requires { s | (split(p) | views::all); }); + static_assert(!requires { (split(p) | views::all)(s); }); + + static_assert(requires { s | split(views::all(p)); }); + static_assert(requires { split(views::all(p))(s); }); + static_assert(requires { s | (split(views::all(p)) | views::all); }); + static_assert(requires { (split(views::all(p)) | views::all)(s); }); + + auto adapt = split(p); + static_assert(requires { s | adapt; }); + static_assert(requires { adapt(s); }); + + auto adapt2 = split(p) | views::all; + static_assert(requires { s | adapt2; }); + static_assert(requires { adapt2(s); }); +} + +void +test10() +{ + // LWG 3505 + auto to_string = [] (auto r) { + return std::string(r.begin(), ranges::next(r.begin(), r.end())); + }; + auto v = "xxyx"sv | views::split("xy"sv) | views::transform(to_string); + VERIFY( ranges::equal(v, (std::string_view[]){"x", "x"}) ); +} + +void +test11() +{ + // LWG 3478 + static_assert(ranges::distance(views::split("text"sv, "text"sv)) == 2); + static_assert(ranges::distance(views::split(" text "sv, ' ')) == 3); + static_assert(ranges::distance(views::split(" t e x t "sv, ' ')) == 6); + static_assert(ranges::distance(views::split(" text "sv, " "sv)) == 3); + static_assert(ranges::distance(views::split(" text "sv, " "sv)) == 4); + static_assert(ranges::distance(views::split(" text "sv, " "sv)) == 4); + static_assert(ranges::distance(views::split("t"sv, 't')) == 2); + static_assert(ranges::distance(views::split("text"sv, ""sv)) == 4); +} +} // namespace from_lazy_split_cc + +int +main() +{ + test01(); + + from_lazy_split_cc::test01(); + from_lazy_split_cc::test02(); + from_lazy_split_cc::test03(); + from_lazy_split_cc::test04(); + from_lazy_split_cc::test05(); + from_lazy_split_cc::test06(); + from_lazy_split_cc::test10(); + from_lazy_split_cc::test11(); +} diff --git a/libstdc++-v3/testsuite/std/ranges/p2325.cc b/libstdc++-v3/testsuite/std/ranges/p2325.cc index 4d075409026..d2ebe9af863 100644 --- a/libstdc++-v3/testsuite/std/ranges/p2325.cc +++ b/libstdc++-v3/testsuite/std/ranges/p2325.cc @@ -124,6 +124,20 @@ test08() static_assert(default_initializable); } +void +test08a() +{ + // Verify split_view is conditionally default constructible. + using type1 = ranges::split_view, ranges::single_view>; + static_assert(!default_initializable); + using type2 = ranges::split_view, ranges::ref_view>; + static_assert(!default_initializable); + using type3 = ranges::split_view, ranges::ref_view>; + static_assert(!default_initializable); + using type4 = ranges::split_view, ranges::single_view>; + static_assert(default_initializable); +} + void test09() { diff --git a/libstdc++-v3/testsuite/std/ranges/p2367.cc b/libstdc++-v3/testsuite/std/ranges/p2367.cc index 5228b021602..70a0304593f 100644 --- a/libstdc++-v3/testsuite/std/ranges/p2367.cc +++ b/libstdc++-v3/testsuite/std/ranges/p2367.cc @@ -45,4 +45,5 @@ test01() // Verify changes to views::lazy_split. auto v6 = views::lazy_split(x, 5u); + auto v7 = views::split(x, 5u); } -- 2.32.0.93.g670b81a890