From patchwork Tue Dec 18 15:51:35 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 1015440 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (mailfrom) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-492744-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.b="x8CxKJ2G"; 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 43K2Zg35FBz9s3q for ; Wed, 19 Dec 2018 02:51:54 +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:date :from:to:subject:message-id:mime-version:content-type; q=dns; s= default; b=K8hGwT4BcKpuO/Pr3hM5bu38T3ZNeUyJ252I3a7/elLMB8UDW2+kO 3Ew1m77jCOLMjsuv8WEW2IBeL47didLreeUvbIugW1KyY/ybJ9dBtPvuGFNJpqUb utxUC6ITgcE2FAU0QLUDqO6GQb6YMzROQUE/cD/lRulX7WY4oZOSUU= 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:date :from:to:subject:message-id:mime-version:content-type; s= default; bh=Aq52TxU4UgBRDEZsjIpFW9ByUpM=; b=x8CxKJ2GAiq4p6hONoLT ZqQz4oXY1SnI3J0UEtdomV0kPHjCdivu1PimIeY9sEDDFwrpbL4PW7T9BbeKWNvh TUasByoiZH+hBj3B5vtq7MR6uF3jgt3y6pzPEayRY3gms6C96h3YKh8BOXfDqIVY 3WTJ0XJyp6rUeDCk9YPKV/c= Received: (qmail 93629 invoked by alias); 18 Dec 2018 15:51:46 -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 93585 invoked by uid 89); 18 Dec 2018 15:51:45 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, SPF_HELO_PASS autolearn=ham version=3.3.2 spammy=__p, distributed X-HELO: mx1.redhat.com Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 18 Dec 2018 15:51:38 +0000 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mx1.redhat.com (Postfix) with ESMTPS id 2AE423B717; Tue, 18 Dec 2018 15:51:37 +0000 (UTC) Received: from localhost (unknown [10.33.36.47]) by smtp.corp.redhat.com (Postfix) with ESMTP id 9AD4D6596E; Tue, 18 Dec 2018 15:51:36 +0000 (UTC) Date: Tue, 18 Dec 2018 15:51:35 +0000 From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Subject: [PATCH] LWG 2936: update path::compare logic and optimize string comparisons Message-ID: <20181218155135.GA8112@redhat.com> MIME-Version: 1.0 Content-Disposition: inline X-Clacks-Overhead: GNU Terry Pratchett User-Agent: Mutt/1.10.1 (2018-07-13) The resolution for LWG 2936 defines the comparison more precisely, which this patch implements. The patch also defines comparisons with strings to work without constructing a temporary path object (so avoids any memory allocations). * include/bits/fs_path.h (path::compare(const string_type&)) (path::compare(const value_type*)): Add noexcept and construct a string view to compare to instead of a path. (path::compare(basic_string_view)): Add noexcept. Remove inline definition. * src/filesystem/std-path.cc (path::_Parser): Track last type read from input. (path::_Parser::next()): Return a final empty component when the input ends in a non-root directory separator. (path::_M_append(basic_string_view)): Remove special cases for trailing non-root directory separator. (path::_M_concat(basic_string_view)): Likewise. (path::compare(const path&)): Implement LWG 2936. (path::compare(basic_string_view)): Define in terms of components returned by parser, consistent with LWG 2936. * testsuite/27_io/filesystem/path/compare/lwg2936.cc: New. * testsuite/27_io/filesystem/path/compare/path.cc: Test more cases. * testsuite/27_io/filesystem/path/compare/strings.cc: Likewise. Tested x86_64-linux, committed to trunk. commit 4e56e9d3bb31740fb65d7a46bfa9796809f971f0 Author: Jonathan Wakely Date: Tue Dec 18 14:29:14 2018 +0000 LWG 2936: update path::compare logic and optimize string comparisons The resolution for LWG 2936 defines the comparison more precisely, which this patch implements. The patch also defines comparisons with strings to work without constructing a temporary path object (so avoids any memory allocations). * include/bits/fs_path.h (path::compare(const string_type&)) (path::compare(const value_type*)): Add noexcept and construct a string view to compare to instead of a path. (path::compare(basic_string_view)): Add noexcept. Remove inline definition. * src/filesystem/std-path.cc (path::_Parser): Track last type read from input. (path::_Parser::next()): Return a final empty component when the input ends in a non-root directory separator. (path::_M_append(basic_string_view)): Remove special cases for trailing non-root directory separator. (path::_M_concat(basic_string_view)): Likewise. (path::compare(const path&)): Implement LWG 2936. (path::compare(basic_string_view)): Define in terms of components returned by parser, consistent with LWG 2936. * testsuite/27_io/filesystem/path/compare/lwg2936.cc: New. * testsuite/27_io/filesystem/path/compare/path.cc: Test more cases. * testsuite/27_io/filesystem/path/compare/strings.cc: Likewise. diff --git a/libstdc++-v3/include/bits/fs_path.h b/libstdc++-v3/include/bits/fs_path.h index c69001bcc3c..b827d85965e 100644 --- a/libstdc++-v3/include/bits/fs_path.h +++ b/libstdc++-v3/include/bits/fs_path.h @@ -341,9 +341,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 // compare int compare(const path& __p) const noexcept; - int compare(const string_type& __s) const; - int compare(const value_type* __s) const; - int compare(const basic_string_view __s) const; + int compare(const string_type& __s) const noexcept; + int compare(const value_type* __s) const noexcept; + int compare(basic_string_view __s) const noexcept; // decomposition @@ -1067,14 +1067,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CXX11 { return generic_string(); } inline int - path::compare(const string_type& __s) const { return compare(path(__s)); } + path::compare(const string_type& __s) const noexcept + { return compare(basic_string_view(__s)); } inline int - path::compare(const value_type* __s) const { return compare(path(__s)); } - - inline int - path::compare(basic_string_view __s) const - { return compare(path(__s)); } + path::compare(const value_type* __s) const noexcept + { return compare(basic_string_view(__s)); } inline path path::filename() const diff --git a/libstdc++-v3/src/filesystem/std-path.cc b/libstdc++-v3/src/filesystem/std-path.cc index b5ddbdad149..5b0318c1f58 100644 --- a/libstdc++-v3/src/filesystem/std-path.cc +++ b/libstdc++-v3/src/filesystem/std-path.cc @@ -62,6 +62,7 @@ struct path::_Parser string_view_type input; string_view_type::size_type pos = 0; size_t origin; + _Type last_type = _Type::_Multi; _Parser(string_view_type s, size_t o = 0) : input(s), origin(o) { } @@ -129,6 +130,12 @@ struct path::_Parser pos = input.find_first_not_of(L"/\\", 2); } #endif + + if (root.second.valid()) + last_type = root.second.type; + else + last_type = root.first.type; + return root; } @@ -140,15 +147,30 @@ struct path::_Parser char sep = '/'; #endif + const int last_pos = pos; + cmpt f; - pos = input.find_first_not_of(sep, pos); if (pos != input.npos) { - const auto end = input.find_first_of(sep, pos); - f.str = input.substr(pos, end - pos); - f.type = _Type::_Filename; - pos = end; + pos = input.find_first_not_of(sep, pos); + if (pos != input.npos) + { + const auto end = input.find_first_of(sep, pos); + f.str = input.substr(pos, end - pos); + f.type = _Type::_Filename; + pos = end; + } + else if (last_type == _Type::_Filename + || (last_pos == 0 && !input.empty())) + { + // [fs.path.itr]/4 An empty element, if trailing non-root + // directory-separator present. + __glibcxx_assert(is_dir_sep(input.back())); + f.str = input.substr(input.length(), 0); + f.type = _Type::_Filename; + } } + last_type = f.type; return f; } @@ -733,9 +755,6 @@ path::_M_append(basic_string_view s) while (parser2.next().valid()) ++capacity; } - - if (s.back() == '/') - ++capacity; } else if (!sep.empty()) ++capacity; @@ -787,12 +806,6 @@ path::_M_append(basic_string_view s) ++_M_cmpts._M_impl->_M_size; cmpt = parser.next(); } - - if (s.back() == '/') - { - ::new(output++) _Cmpt({}, _Type::_Filename, _M_pathname.length()); - ++_M_cmpts._M_impl->_M_size; - } } else if (!sep.empty()) { @@ -1107,8 +1120,6 @@ path::_M_concat(basic_string_view s) while (parser2.next().valid()) ++capacity; } - if (is_dir_sep(s.back())) - ++capacity; #if SLASHSLASH_IS_ROOTNAME if (orig_type == _Type::_Root_name) @@ -1165,13 +1176,6 @@ path::_M_concat(basic_string_view s) cmpt = parser.next(); } } - - if (is_dir_sep(s.back())) - { - // Empty filename at the end: - ::new(output++) _Cmpt({}, _Type::_Filename, _M_pathname.length()); - ++_M_cmpts._M_impl->_M_size; - } } __catch (...) { @@ -1266,58 +1270,168 @@ path::replace_extension(const path& replacement) return *this; } -namespace -{ - template - int do_compare(Iter1 begin1, Iter1 end1, Iter2 begin2, Iter2 end2) - { - int cmpt = 1; - while (begin1 != end1 && begin2 != end2) - { - if (begin1->native() < begin2->native()) - return -cmpt; - if (begin1->native() > begin2->native()) - return +cmpt; - ++begin1; - ++begin2; - ++cmpt; - } - if (begin1 == end1) - { - if (begin2 == end2) - return 0; - return -cmpt; - } - return +cmpt; - } -} - int path::compare(const path& p) const noexcept { - struct CmptRef - { - const path* ptr; - const string_type& native() const noexcept { return ptr->native(); } - }; - - if (empty() && p.empty()) + if (_M_pathname == p._M_pathname) return 0; - else if (_M_type() == _Type::_Multi && p._M_type() == _Type::_Multi) - return do_compare(_M_cmpts.begin(), _M_cmpts.end(), - p._M_cmpts.begin(), p._M_cmpts.end()); - else if (_M_type() == _Type::_Multi) + + basic_string_view lroot, rroot; + if (_M_type() == _Type::_Root_name) + lroot = _M_pathname; + else if (_M_type() == _Type::_Multi + && _M_cmpts.front()._M_type() == _Type::_Root_name) + lroot = _M_cmpts.front()._M_pathname; + if (p._M_type() == _Type::_Root_name) + rroot = p._M_pathname; + else if (p._M_type() == _Type::_Multi + && p._M_cmpts.front()._M_type() == _Type::_Root_name) + rroot = p._M_cmpts.front()._M_pathname; + if (int rootNameComparison = lroot.compare(rroot)) + return rootNameComparison; + + if (!this->has_root_directory() && p.has_root_directory()) + return -1; + else if (this->has_root_directory() && !p.has_root_directory()) + return +1; + + using Iterator = const _Cmpt*; + Iterator begin1, end1, begin2, end2; + if (_M_type() == _Type::_Multi) { - CmptRef c[1] = { { &p } }; - return do_compare(_M_cmpts.begin(), _M_cmpts.end(), c, c+1); - } - else if (p._M_type() == _Type::_Multi) - { - CmptRef c[1] = { { this } }; - return do_compare(c, c+1, p._M_cmpts.begin(), p._M_cmpts.end()); + begin1 = _M_cmpts.begin(); + end1 = _M_cmpts.end(); + // Find start of this->relative_path() + while (begin1 != end1 && begin1->_M_type() != _Type::_Filename) + ++begin1; } else - return _M_pathname.compare(p._M_pathname); + begin1 = end1 = nullptr; + + if (p._M_type() == _Type::_Multi) + { + begin2 = p._M_cmpts.begin(); + end2 = p._M_cmpts.end(); + // Find start of p.relative_path() + while (begin2 != end2 && begin2->_M_type() != _Type::_Filename) + ++begin2; + } + else + begin2 = end2 = nullptr; + + if (_M_type() == _Type::_Filename) + { + if (p._M_type() == _Type::_Filename) + return native().compare(p.native()); + else if (begin2 != end2) + { + if (int ret = native().compare(begin2->native())) + return ret; + else + return ++begin2 == end2 ? 0 : -1; + } + else + return +1; + } + else if (p._M_type() == _Type::_Filename) + { + if (begin1 != end1) + { + if (int ret = begin1->native().compare(p.native())) + return ret; + else + return ++begin1 == end1 ? 0 : +1; + } + else + return -1; + } + + int count = 1; + while (begin1 != end1 && begin2 != end2) + { + if (int i = begin1->native().compare(begin2->native())) + return i; + ++begin1; + ++begin2; + ++count; + } + if (begin1 == end1) + { + if (begin2 == end2) + return 0; + return -count; + } + return count; +} + +int +path::compare(basic_string_view s) const noexcept +{ + if (_M_pathname == s) + return 0; + + _Parser parser(s); + + basic_string_view lroot, rroot; + if (_M_type() == _Type::_Root_name) + lroot = _M_pathname; + else if (_M_type() == _Type::_Multi + && _M_cmpts.front()._M_type() == _Type::_Root_name) + lroot = _M_cmpts.front()._M_pathname; + auto root_path = parser.root_path(); + if (root_path.first.type == _Type::_Root_name) + rroot = root_path.first.str; + if (int rootNameComparison = lroot.compare(rroot)) + return rootNameComparison; + + const bool has_root_dir = root_path.first.type == _Type::_Root_dir + || root_path.second.type == _Type::_Root_dir; + if (!this->has_root_directory() && has_root_dir) + return -1; + else if (this->has_root_directory() && !has_root_dir) + return +1; + + using Iterator = const _Cmpt*; + Iterator begin1, end1; + if (_M_type() == _Type::_Filename) + { + auto cmpt = parser.next(); + if (cmpt.valid()) + { + if (int ret = this->native().compare(cmpt.str)) + return ret; + return parser.next().valid() ? -1 : 0; + } + else + return +1; + } + else if (_M_type() == _Type::_Multi) + { + begin1 = _M_cmpts.begin(); + end1 = _M_cmpts.end(); + while (begin1 != end1 && begin1->_M_type() != _Type::_Filename) + ++begin1; + } + else + begin1 = end1 = nullptr; + + int count = 1; + auto cmpt = parser.next(); + while (begin1 != end1 && cmpt.valid()) + { + if (int i = begin1->native().compare(cmpt.str)) + return i; + ++begin1; + cmpt = parser.next(); + ++count; + } + if (begin1 == end1) + { + if (!cmpt.valid()) + return 0; + return -count; + } + return +count; } path @@ -1718,12 +1832,9 @@ path::_M_split_cmpts() *next++ = root_path.second; } - bool got_at_least_one_filename = false; - auto cmpt = parser.next(); while (cmpt.valid()) { - got_at_least_one_filename = true; do { *next++ = cmpt; @@ -1746,15 +1857,6 @@ path::_M_split_cmpts() } } - // [fs.path.itr]/4 - // An empty element, if trailing non-root directory-separator present. - if (got_at_least_one_filename && is_dir_sep(_M_pathname.back())) - { - next->str = { _M_pathname.data() + _M_pathname.length(), 0 }; - next->type = _Type::_Filename; - ++next; - } - if (auto n = next - buf.begin()) { if (n == 1 && _M_cmpts.empty()) diff --git a/libstdc++-v3/testsuite/27_io/filesystem/path/compare/lwg2936.cc b/libstdc++-v3/testsuite/27_io/filesystem/path/compare/lwg2936.cc new file mode 100644 index 00000000000..8a11043f143 --- /dev/null +++ b/libstdc++-v3/testsuite/27_io/filesystem/path/compare/lwg2936.cc @@ -0,0 +1,80 @@ +// { dg-options "-std=gnu++17 -lstdc++fs" } +// { dg-do run { target c++17 } } +// { dg-require-filesystem-ts "" } + +// Copyright (C) 2014-2018 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 +// . + +// 8.4.8 path compare [path.compare] + +#include +#include +#include + +using std::filesystem::path; + +int norm(int i) +{ + if (i < 0) + return -1; + else if (i > 0) + return +1; + else + return 0; +} + +void +check(const path& lhs, const path& rhs, int sense) +{ + VERIFY( lhs.compare(lhs) == 0 ); + VERIFY( rhs.compare(rhs) == 0 ); + + VERIFY( norm(lhs.compare(rhs)) == sense ); + VERIFY( norm(lhs.compare(rhs.c_str())) == sense ); + + VERIFY( norm(rhs.compare(lhs)) == -sense ); + VERIFY( norm(rhs.compare(lhs.c_str())) == -sense ); +} + +void +test01() +{ + check("", "", 0); + + // These are root names on Windows (just relative paths elsewhere) + check("", "c:", -1); + check("c:", "d:", -1); + check("c:", "c:/", -1); + check("d:", "c:/", +1); + check("c:/a/b", "c:a/b", -1); + + // These are root names on Cygwin (just relative paths elsewhere) + check("", "//c", -1); + check("//c", "//d", -1); + check("//c", "//c/", -1); + check("//d", "//c/", +1); + + check("/a", "/b", -1); + check("a", "/b", -1); + check("/b", "b", +1); +} + +int +main() +{ + test01(); +} diff --git a/libstdc++-v3/testsuite/27_io/filesystem/path/compare/path.cc b/libstdc++-v3/testsuite/27_io/filesystem/path/compare/path.cc index 4aa2cd387c5..159a96c6597 100644 --- a/libstdc++-v3/testsuite/27_io/filesystem/path/compare/path.cc +++ b/libstdc++-v3/testsuite/27_io/filesystem/path/compare/path.cc @@ -44,8 +44,19 @@ test01() } } +void +test02() +{ + VERIFY( path("/").compare(path("////")) == 0 ); + VERIFY( path("/a").compare(path("/")) > 0 ); + VERIFY( path("/").compare(path("/a")) < 0 ); + VERIFY( path("/ab").compare(path("/a")) > 0 ); + VERIFY( path("/ab").compare(path("/a/b")) > 0 ); +} + int main() { test01(); + test02(); } diff --git a/libstdc++-v3/testsuite/27_io/filesystem/path/compare/strings.cc b/libstdc++-v3/testsuite/27_io/filesystem/path/compare/strings.cc index cfd73ad9e4a..a3fcb800dbf 100644 --- a/libstdc++-v3/testsuite/27_io/filesystem/path/compare/strings.cc +++ b/libstdc++-v3/testsuite/27_io/filesystem/path/compare/strings.cc @@ -42,8 +42,19 @@ test01() } } +void +test02() +{ + VERIFY( path("/").compare("////") == 0 ); + VERIFY( path("/a").compare("/") > 0 ); + VERIFY( path("/").compare("/a") < 0 ); + VERIFY( path("/ab").compare("/a") > 0 ); + VERIFY( path("/ab").compare("/a/b") > 0 ); +} + int main() { test01(); + test02(); }