LWG 2936: update path::compare logic and optimize string comparisons

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<value_type> __s) const;
+    int compare(const string_type& __s) const noexcept;
+    int compare(const value_type* __s) const noexcept;
+    int compare(basic_string_view<value_type> __s) const noexcept;
 
     // decomposition
 
@@ -1067,14 +1067,12 @@  _GLIBCXX_BEGIN_NAMESPACE_CXX11
   { return generic_string<char32_t>(); }
 
   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<value_type>(__s)); }
 
   inline int
-  path::compare(const value_type* __s) const { return compare(path(__s)); }
-
-  inline int
-  path::compare(basic_string_view<value_type> __s) const
-  { return compare(path(__s)); }
+  path::compare(const value_type* __s) const noexcept
+  { return compare(basic_string_view<value_type>(__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<value_type> 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<value_type> 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<value_type> 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<value_type> 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<typename Iter1, typename Iter2>
-    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<value_type> 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<value_type> s) const noexcept
+{
+  if (_M_pathname == s)
+    return 0;
+
+  _Parser parser(s);
+
+  basic_string_view<value_type> 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
+// <http://www.gnu.org/licenses/>.
+
+// 8.4.8 path compare [path.compare]
+
+#include <filesystem>
+#include <testsuite_hooks.h>
+#include <testsuite_fs.h>
+
+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();
 }