Implement LWG 2936: Path comparison is defined in terms of the generic format

This patch implements path::compare according to the current spec. The
only observable change is the ordering of "/foo" and "foo", which orders
the two paths based on having or not having a root directory (instead
of lexically comparing "/" to "foo").

3 files changed, 139 insertions, 15 deletions

diff --git a/libcxx/src/filesystem/operations.cpp b/libcxx/src/filesystem/operations.cpp
index c9396b59cae..0b79ef1cdac 100644
--- a/libcxx/src/filesystem/operations.cpp
+++ b/libcxx/src/filesystem/operations.cpp
@@ -206,8 +206,20 @@ public:
     return *this;
   }
 
+  bool atEnd() const noexcept {
+    return State == PS_AtEnd;
+  }
+
+  bool inRootDir() const noexcept {
+    return State == PS_InRootDir;
+  }
+
+  bool inRootName() const noexcept {
+    return State == PS_InRootName;
+  }
+
   bool inRootPath() const noexcept {
-    return State == PS_InRootDir || State == PS_InRootName;
+    return inRootName() || inRootDir();
   }
 
 private:
@@ -1294,7 +1306,19 @@ string_view_t path::__root_path_raw() const {
   return {};
 }
 
+static bool ConsumeRootName(PathParser *PP) {
+  static_assert(PathParser::PS_BeforeBegin == 1 &&
+      PathParser::PS_InRootName == 2,
+      "Values for enums are incorrect");
+  while (PP->State <= PathParser::PS_InRootName)
+    ++(*PP);
+  return PP->State == PathParser::PS_AtEnd;
+}
+
 static bool ConsumeRootDir(PathParser* PP) {
+  static_assert(PathParser::PS_BeforeBegin == 1 &&
+                PathParser::PS_InRootName == 2 &&
+                PathParser::PS_InRootDir == 3, "Values for enums are incorrect");
   while (PP->State <= PathParser::PS_InRootDir)
     ++(*PP);
   return PP->State == PathParser::PS_AtEnd;
@@ -1514,21 +1538,68 @@ path path::lexically_relative(const path& base) const {
 
 ////////////////////////////////////////////////////////////////////////////
 // path.comparisons
-int path::__compare(string_view_t __s) const {
-  auto PP = PathParser::CreateBegin(__pn_);
-  auto PP2 = PathParser::CreateBegin(__s);
-  while (PP && PP2) {
-    int res = (*PP).compare(*PP2);
-    if (res != 0)
+static int CompareRootName(PathParser *LHS, PathParser *RHS) {
+  if (!LHS->inRootName() && !RHS->inRootName())
+    return 0;
+
+  auto GetRootName = [](PathParser *Parser) -> string_view_t {
+    return Parser->inRootName() ? **Parser : "";
+  };
+  int res = GetRootName(LHS).compare(GetRootName(RHS));
+  ConsumeRootName(LHS);
+  ConsumeRootName(RHS);
+  return res;
+}
+
+static int CompareRootDir(PathParser *LHS, PathParser *RHS) {
+  if (!LHS->inRootDir() && RHS->inRootDir())
+    return -1;
+  else if (LHS->inRootDir() && !RHS->inRootDir())
+    return 1;
+  else {
+    ConsumeRootDir(LHS);
+    ConsumeRootDir(RHS);
+    return 0;
+  }
+}
+
+static int CompareRelative(PathParser *LHSPtr, PathParser *RHSPtr) {
+  auto &LHS = *LHSPtr;
+  auto &RHS = *RHSPtr;
+  
+  int res;
+  while (LHS && RHS) {
+    if ((res = (*LHS).compare(*RHS)) != 0)
       return res;
-    ++PP;
-    ++PP2;
+    ++LHS;
+    ++RHS;
   }
-  if (PP.State == PP2.State && !PP)
-    return 0;
-  if (!PP)
+  return 0;
+}
+
+static int CompareEndState(PathParser *LHS, PathParser *RHS) {
+  if (LHS->atEnd() && !RHS->atEnd())
     return -1;
-  return 1;
+  else if (!LHS->atEnd() && RHS->atEnd())
+    return 1;
+  return 0;
+}
+
+int path::__compare(string_view_t __s) const {
+  auto LHS = PathParser::CreateBegin(__pn_);
+  auto RHS = PathParser::CreateBegin(__s);
+  int res;
+
+  if ((res = CompareRootName(&LHS, &RHS)) != 0)
+    return res;
+
+  if ((res = CompareRootDir(&LHS, &RHS)) != 0)
+    return res;
+
+  if ((res = CompareRelative(&LHS, &RHS)) != 0)
+    return res;
+
+  return CompareEndState(&LHS, &RHS);
 }
 
 ////////////////////////////////////////////////////////////////////////////
diff --git a/libcxx/test/std/input.output/filesystems/class.path/path.member/path.compare.pass.cpp b/libcxx/test/std/input.output/filesystems/class.path/path.member/path.compare.pass.cpp
index 7791097dcd1..2be6122a0f8 100644
--- a/libcxx/test/std/input.output/filesystems/class.path/path.member/path.compare.pass.cpp
+++ b/libcxx/test/std/input.output/filesystems/class.path/path.member/path.compare.pass.cpp
@@ -65,6 +65,8 @@ const PathCompareTest CompareTestCases[] =
     {"//foo//bar///baz////", "//foo/bar/baz/", 0}, // duplicate separators
     {"///foo/bar", "/foo/bar", 0}, // "///" is not a root directory
     {"/foo/bar/", "/foo/bar", 1}, // trailing separator
+    {"foo", "/foo", -1}, // if !this->has_root_directory() and p.has_root_directory(), a value less than 0.
+    {"/foo", "foo", 1}, //  if this->has_root_directory() and !p.has_root_directory(), a value greater than 0.
     {"//" LONGA "////" LONGB "/" LONGC "///" LONGD, "//" LONGA "/" LONGB "/" LONGC "/" LONGD, 0},
     { LONGA "/" LONGB "/" LONGC, LONGA "/" LONGB "/" LONGB, 1}
 
@@ -79,7 +81,7 @@ static inline int normalize_ret(int ret)
   return ret < 0 ? -1 : (ret > 0 ? 1 : 0);
 }
 
-int main()
+void test_compare_basic()
 {
   using namespace fs;
   for (auto const & TC : CompareTestCases) {
@@ -136,3 +138,54 @@ int main()
     }
   }
 }
+
+int CompareElements(std::vector<std::string> const& LHS, std::vector<std::string> const& RHS) {
+  bool IsLess = std::lexicographical_compare(LHS.begin(), LHS.end(), RHS.begin(), RHS.end());
+  if (IsLess)
+    return -1;
+
+  bool IsGreater = std::lexicographical_compare(RHS.begin(), RHS.end(), LHS.begin(), LHS.end());
+  if (IsGreater)
+    return 1;
+
+  return 0;
+}
+
+void test_compare_elements() {
+  struct {
+    std::vector<std::string> LHSElements;
+    std::vector<std::string> RHSElements;
+    int Expect;
+  } TestCases[] = {
+      {{"a"}, {"a"}, 0},
+      {{"a"}, {"b"}, -1},
+      {{"b"}, {"a"}, 1},
+      {{"a", "b", "c"}, {"a", "b", "c"}, 0},
+      {{"a", "b", "c"}, {"a", "b", "d"}, -1},
+      {{"a", "b", "d"}, {"a", "b", "c"}, 1},
+      {{"a", "b"}, {"a", "b", "c"}, -1},
+      {{"a", "b", "c"}, {"a", "b"}, 1},
+
+  };
+
+  auto BuildPath = [](std::vector<std::string> const& Elems) {
+    fs::path p;
+    for (auto &E : Elems)
+      p /= E;
+    return p;
+  };
+
+  for (auto &TC : TestCases) {
+    fs::path LHS = BuildPath(TC.LHSElements);
+    fs::path RHS = BuildPath(TC.RHSElements);
+    const int ExpectCmp = CompareElements(TC.LHSElements, TC.RHSElements);
+    assert(ExpectCmp == TC.Expect);
+    const int GotCmp = normalize_ret(LHS.compare(RHS));
+    assert(GotCmp == TC.Expect);
+  }
+}
+
+int main() {
+  test_compare_basic();
+  test_compare_elements();
+}
diff --git a/libcxx/www/cxx2a_status.html b/libcxx/www/cxx2a_status.html
index f8a5a831f6b..25e6cdfe4e4 100644
--- a/libcxx/www/cxx2a_status.html
+++ b/libcxx/www/cxx2a_status.html
@@ -258,7 +258,7 @@
 	<tr><td><a href="https://wg21.link/LWG2682">2682</a></td><td><code>filesystem::copy()</code> won't create a symlink to a directory</td><td>San Diego</td><td>Nothing to do</td></tr>
 	<tr><td><a href="https://wg21.link/LWG2697">2697</a></td><td>[concurr.ts] Behavior of <tt>future/shared_future</tt> unwrapping constructor when given an invalid <tt>future</tt></td><td>San Diego</td><td></td></tr>
 	<tr><td><a href="https://wg21.link/LWG2797">2797</a></td><td>Trait precondition violations</td><td>San Diego</td><td>Resolved by 1285R0</td></tr>
-	<tr><td><a href="https://wg21.link/LWG2936">2936</a></td><td>Path comparison is defined in terms of the generic format</td><td>San Diego</td><td></td></tr>
+	<tr><td><a href="https://wg21.link/LWG2936">2936</a></td><td>Path comparison is defined in terms of the generic format</td><td>San Diego</td><td>Complete</td></tr>
 	<tr><td><a href="https://wg21.link/LWG2943">2943</a></td><td>Problematic specification of the wide version of <tt>basic_filebuf::open</tt></td><td>San Diego</td><td>Nothing to do</td></tr>
 	<tr><td><a href="https://wg21.link/LWG2960">2960</a></td><td>[fund.ts.v3] <tt>nonesuch</tt> is insufficiently useless</td><td>San Diego</td><td></td></tr>
 	<tr><td><a href="https://wg21.link/LWG2995">2995</a></td><td><tt>basic_stringbuf</tt> default constructor forbids it from using SSO capacity</td><td>San Diego</td><td></td></tr>