libstdc++-v3/src/c++17/fs_path.cc

   1 // Class filesystem::path -*- C++ -*-
   2
   3 // Copyright (C) 2014-2024 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 #ifndef _GLIBCXX_USE_CXX11_ABI
  26 # define _GLIBCXX_USE_CXX11_ABI 1
  27 #endif
  28
  29 #ifdef __CYGWIN__
  30 // Interpret "//x" as a root-name, not root-dir + filename
  31 # define SLASHSLASH_IS_ROOTNAME 1
  32 #endif
  33
  34 #include <filesystem>
  35 #include <algorithm>
  36 #include <array>
  37 #include <bits/stl_uninitialized.h>
  38 #include <ext/numeric_traits.h> // __gnu_cxx::__int_traits
  39
  40 namespace fs = std::filesystem;
  41 using fs::path;
  42
  43 static inline bool is_dir_sep(path::value_type ch)
  44 {
  45 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
  46     return ch == L'/' || ch == path::preferred_separator;
  47 #else
  48     return ch == '/';
  49 #endif
  50 }
  51
  52 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
  53 static inline bool is_disk_designator(std::wstring_view s)
  54 {
  55   return s.length() == 2 && s[1] == L':';
  56 }
  57 #endif
  58
  59 struct path::_Parser
  60 {
  61   using string_view_type = std::basic_string_view<value_type>;
  62
  63   struct cmpt
  64   {
  65     string_view_type str;
  66     _Type type = _Type::_Multi;
  67
  68     bool valid() const { return type != _Type::_Multi; }
  69   };
  70
  71   string_view_type input;
  72   string_view_type::size_type pos = 0;
  73   size_t origin;
  74   _Type last_type = _Type::_Multi;
  75
  76   _Parser(string_view_type s, size_t o = 0) : input(s), origin(o) { }
  77
  78   pair<cmpt, cmpt> root_path() noexcept
  79   {
  80     pos = 0;
  81     pair<cmpt, cmpt> root;
  82
  83     const size_t len = input.size();
  84
  85     // look for root name or root directory
  86     if (len && is_dir_sep(input[0]))
  87       {
  88 #if SLASHSLASH_IS_ROOTNAME
  89         // look for root name, such as "//foo"
  90         if (len > 2 && input[1] == input[0])
  91           {
  92             if (!is_dir_sep(input[2]))
  93               {
  94                 // got root name, find its end
  95                 pos = 3;
  96                 while (pos < len && !is_dir_sep(input[pos]))
  97                   ++pos;
  98                 root.first.str = input.substr(0, pos);
  99                 root.first.type = _Type::_Root_name;
 100
 101                 if (pos < len) // also got root directory
 102                   {
 103                     root.second.str = input.substr(pos, 1);
 104                     root.second.type = _Type::_Root_dir;
 105                     ++pos;
 106                   }
 107               }
 108             else
 109               {
 110                 // got something like "///foo" which is just a root directory
 111                 // composed of multiple redundant directory separators
 112                 root.first.str = input.substr(0, 1);
 113                 root.first.type = _Type::_Root_dir;
 114                 pos += 2;
 115               }
 116           }
 117         else
 118 #endif
 119           {
 120             root.first.str = input.substr(0, 1);
 121             root.first.type = _Type::_Root_dir;
 122             ++pos;
 123           }
 124         // Find the start of the first filename
 125         while (pos < len && is_dir_sep(input[pos]))
 126           ++pos;
 127       }
 128 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
 129     else if (is_disk_designator(input.substr(0, 2)))
 130       {
 131         // got disk designator
 132         root.first.str = input.substr(0, 2);
 133         root.first.type = _Type::_Root_name;
 134         if (len > 2 && is_dir_sep(input[2]))
 135           {
 136             root.second.str = input.substr(2, 1);
 137             root.second.type = _Type::_Root_dir;
 138           }
 139         pos = input.find_first_not_of(L"/\\", 2);
 140       }
 141 #endif
 142
 143     if (root.second.valid())
 144       last_type = root.second.type;
 145     else
 146       last_type = root.first.type;
 147
 148     return root;
 149   }
 150
 151   cmpt next() noexcept
 152   {
 153 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
 154     string_view_type sep = L"/\\";
 155 #else
 156     char sep = '/';
 157 #endif
 158
 159     const int last_pos = pos;
 160
 161     cmpt f;
 162     if (pos != input.npos)
 163       {
 164         pos = input.find_first_not_of(sep, pos);
 165         if (pos != input.npos)
 166           {
 167             const auto end = input.find_first_of(sep, pos);
 168             f.str = input.substr(pos, end - pos);
 169             f.type = _Type::_Filename;
 170             pos = end;
 171           }
 172         else if (last_type == _Type::_Filename
 173             || (last_pos == 0 && !input.empty()))
 174           {
 175             // [fs.path.itr]/4 An empty element, if trailing non-root
 176             // directory-separator present.
 177             __glibcxx_assert(is_dir_sep(input.back()));
 178             f.str = input.substr(input.length(), 0);
 179             f.type = _Type::_Filename;
 180           }
 181       }
 182     last_type = f.type;
 183     return f;
 184   }
 185
 186   string_view_type::size_type
 187   offset(const cmpt& c) const noexcept
 188   { return origin + c.str.data() - input.data(); }
 189 };
 190
 191 inline
 192 path::path(basic_string_view<value_type> __str, _Type __type)
 193 : _M_pathname(__str)
 194 {
 195   __glibcxx_assert(__type != _Type::_Multi);
 196   _M_cmpts.type(__type);
 197 }
 198
 199 inline
 200 path::_Cmpt::_Cmpt(basic_string_view<value_type> __s, _Type __t, size_t __pos)
 201 : path(__s, __t), _M_pos(__pos)
 202 { }
 203
 204 struct path::_List::_Impl
 205 {
 206   using value_type = _Cmpt;
 207
 208   _Impl(int cap) : _M_size(0), _M_capacity(cap) { }
 209
 210   alignas(value_type) int _M_size;
 211   int _M_capacity;
 212
 213   using iterator = value_type*;
 214   using const_iterator = const value_type*;
 215
 216   iterator begin() { return reinterpret_cast<value_type*>(this + 1); }
 217   iterator end() { return begin() + size(); }
 218
 219   const_iterator begin() const
 220   { return reinterpret_cast<const value_type*>(this + 1); }
 221   const_iterator end() const { return begin() + size(); }
 222
 223   const value_type& front() const { return *begin(); }
 224   const value_type& back() const { return end()[-1]; }
 225
 226   int size() const { return _M_size; }
 227   int capacity() const { return _M_capacity; }
 228   bool empty() const { return _M_size == 0; }
 229
 230   void clear() { std::destroy_n(begin(), _M_size); _M_size = 0; }
 231
 232   void pop_back()
 233   {
 234     back().~_Cmpt();
 235     --_M_size;
 236   }
 237
 238   void _M_erase_from(const_iterator pos)
 239   {
 240     iterator first = begin() + (pos - begin());
 241     iterator last = end();
 242     std::destroy(first, last);
 243     _M_size -= last - first;
 244   }
 245
 246   unique_ptr<_Impl, _Impl_deleter> copy() const
 247   {
 248     const auto n = size();
 249     void* p = ::operator new(sizeof(_Impl) + n * sizeof(value_type));
 250     unique_ptr<_Impl, _Impl_deleter> newptr(::new (p) _Impl{n});
 251     std::uninitialized_copy_n(begin(), n, newptr->begin());
 252     newptr->_M_size = n;
 253     return newptr;
 254   }
 255
 256   // Clear the lowest two bits from the pointer (i.e. remove the _Type value)
 257   static _Impl* notype(_Impl* p)
 258   {
 259     constexpr uintptr_t mask = ~(uintptr_t)0x3;
 260     return reinterpret_cast<_Impl*>(reinterpret_cast<uintptr_t>(p) & mask);
 261   }
 262 };
 263
 264 void path::_List::_Impl_deleter::operator()(_Impl* p) const noexcept
 265 {
 266   p = _Impl::notype(p);
 267   if (p)
 268     {
 269       __glibcxx_assert(p->_M_size <= p->_M_capacity);
 270       p->clear();
 271       ::operator delete(p, sizeof(*p) + p->_M_capacity * sizeof(value_type));
 272     }
 273 }
 274
 275 path::_List::_List() : _M_impl(reinterpret_cast<_Impl*>(_Type::_Filename)) { }
 276
 277 path::_List::_List(const _List& other)
 278 {
 279   if (!other.empty())
 280     _M_impl = other._M_impl->copy();
 281   else
 282     type(other.type());
 283 }
 284
 285 path::_List&
 286 path::_List::operator=(const _List& other)
 287 {
 288   if (!other.empty())
 289     {
 290       // copy in-place if there is capacity
 291       const int newsize = other._M_impl->size();
 292       auto impl = _Impl::notype(_M_impl.get());
 293       if (impl && impl->capacity() >= newsize)
 294         {
 295           const int oldsize = impl->_M_size;
 296           auto to = impl->begin();
 297           auto from = other._M_impl->begin();
 298           const int minsize = std::min(newsize, oldsize);
 299           for (int i = 0; i < minsize; ++i)
 300             to[i]._M_pathname.reserve(from[i]._M_pathname.length());
 301           if (newsize > oldsize)
 302             {
 303               std::uninitialized_copy_n(from + oldsize, newsize - oldsize,
 304                                         to + oldsize);
 305               impl->_M_size = newsize;
 306             }
 307           else if (newsize < oldsize)
 308             impl->_M_erase_from(impl->begin() + newsize);
 309           std::copy_n(from, minsize, to);
 310           type(_Type::_Multi);
 311         }
 312       else
 313         _M_impl = other._M_impl->copy();
 314     }
 315   else
 316     {
 317       clear();
 318       type(other.type());
 319     }
 320   return *this;
 321 }
 322
 323 inline void
 324 path::_List::type(_Type t) noexcept
 325 {
 326   auto val = reinterpret_cast<uintptr_t>(_Impl::notype(_M_impl.release()));
 327   _M_impl.reset(reinterpret_cast<_Impl*>(val | (unsigned char)t));
 328 }
 329
 330 inline int
 331 path::_List::size() const noexcept
 332 {
 333   if (auto* ptr = _Impl::notype(_M_impl.get()))
 334     return ptr->size();
 335   return 0;
 336 }
 337
 338 inline int
 339 path::_List::capacity() const noexcept
 340 {
 341   if (auto* ptr = _Impl::notype(_M_impl.get()))
 342     return ptr->capacity();
 343   return 0;
 344 }
 345
 346 inline bool
 347 path::_List::empty() const noexcept
 348 {
 349   return size() == 0;
 350 }
 351
 352 inline auto
 353 path::_List::begin() noexcept
 354 -> iterator
 355 {
 356   __glibcxx_assert(!empty());
 357   if (auto* ptr = _Impl::notype(_M_impl.get()))
 358     return ptr->begin();
 359   return nullptr;
 360 }
 361
 362 inline auto
 363 path::_List::end() noexcept
 364 -> iterator
 365 {
 366   __glibcxx_assert(!empty());
 367   if (auto* ptr = _Impl::notype(_M_impl.get()))
 368     return ptr->end();
 369   return nullptr;
 370 }
 371
 372 auto
 373 path::_List::begin() const noexcept
 374 -> const_iterator
 375 {
 376   __glibcxx_assert(!empty());
 377   if (auto* ptr = _Impl::notype(_M_impl.get()))
 378     return ptr->begin();
 379   return nullptr;
 380 }
 381
 382 auto
 383 path::_List::end() const noexcept
 384 -> const_iterator
 385 {
 386   __glibcxx_assert(!empty());
 387   if (auto* ptr = _Impl::notype(_M_impl.get()))
 388     return ptr->end();
 389   return nullptr;
 390 }
 391
 392 inline auto
 393 path::_List::front() noexcept
 394 -> value_type&
 395 {
 396   return *_M_impl->begin();
 397 }
 398
 399 inline auto
 400 path::_List::back() noexcept
 401 -> value_type&
 402 {
 403   return _M_impl->begin()[_M_impl->size() - 1];
 404 }
 405
 406 inline auto
 407 path::_List::front() const noexcept
 408 -> const value_type&
 409 {
 410   return *_M_impl->begin();
 411 }
 412
 413 inline auto
 414 path::_List::back() const noexcept
 415 -> const value_type&
 416 {
 417   return _M_impl->begin()[_M_impl->size() - 1];
 418 }
 419
 420 inline void
 421 path::_List::pop_back()
 422 {
 423   __glibcxx_assert(size() > 0);
 424   _M_impl->pop_back();
 425 }
 426
 427 inline void
 428 path::_List::_M_erase_from(const_iterator pos)
 429 {
 430   _M_impl->_M_erase_from(pos);
 431 }
 432
 433 inline void
 434 path::_List::clear()
 435 {
 436   if (auto ptr = _Impl::notype(_M_impl.get()))
 437     ptr->clear();
 438 }
 439
 440 void
 441 path::_List::reserve(int newcap, bool exact = false)
 442 {
 443   // __glibcxx_assert(type() == _Type::_Multi);
 444
 445   _Impl* curptr = _Impl::notype(_M_impl.get());
 446
 447   int curcap = curptr ? curptr->capacity() : 0;
 448
 449   if (curcap < newcap)
 450     {
 451       if (!exact)
 452         {
 453           const int nextcap = curcap + curcap / 2;
 454           if (newcap < nextcap)
 455             newcap = nextcap;
 456         }
 457
 458       using __gnu_cxx::__int_traits;
 459       // Nobody should need paths with this many components.
 460       if (newcap >= __int_traits<int>::__max / 4)
 461         std::__throw_bad_alloc();
 462
 463       size_t bytes;
 464       if constexpr (__int_traits<int>::__max >= __int_traits<size_t>::__max)
 465         {
 466           size_t components;
 467           if (__builtin_mul_overflow(newcap, sizeof(value_type), &components)
 468                 || __builtin_add_overflow(sizeof(_Impl), components, &bytes))
 469             std::__throw_bad_alloc();
 470         }
 471       else // This won't overflow, even for 20-bit size_t on msp430.
 472         bytes = sizeof(_Impl) + newcap * sizeof(value_type);
 473
 474       void* p = ::operator new(bytes);
 475       std::unique_ptr<_Impl, _Impl_deleter> newptr(::new(p) _Impl{newcap});
 476       const int cursize = curptr ? curptr->size() : 0;
 477       if (cursize)
 478         {
 479           std::uninitialized_move_n(curptr->begin(), cursize, newptr->begin());
 480           newptr->_M_size = cursize;
 481         }
 482       std::swap(newptr, _M_impl);
 483     }
 484 }
 485
 486 path&
 487 path::operator=(const path& p)
 488 {
 489   if (&p == this) [[__unlikely__]]
 490     return *this;
 491
 492   _M_pathname.reserve(p._M_pathname.length());
 493   _M_cmpts = p._M_cmpts;        // might throw
 494   _M_pathname = p._M_pathname;  // won't throw because we reserved enough space
 495   return *this;
 496 }
 497
 498 path&
 499 path::operator/=(const path& __p)
 500 {
 501 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
 502   if (__p.is_absolute()
 503       || (__p.has_root_name() && __p.root_name() != root_name()))
 504     return operator=(__p);
 505
 506   basic_string_view<value_type> __lhs = _M_pathname;
 507   bool __add_sep = false;
 508
 509   if (__p.has_root_directory())
 510     {
 511       // Remove any root directory and relative path
 512       if (_M_type() != _Type::_Root_name)
 513         {
 514           if (!_M_cmpts.empty()
 515               && _M_cmpts.front()._M_type() == _Type::_Root_name)
 516             __lhs = _M_cmpts.front()._M_pathname;
 517           else
 518             __lhs = {};
 519         }
 520     }
 521   else if (has_filename() || (!has_root_directory() && is_absolute()))
 522     __add_sep = true;
 523
 524   basic_string_view<value_type> __rhs = __p._M_pathname;
 525   // Omit any root-name from the generic format pathname:
 526   if (__p._M_type() == _Type::_Root_name)
 527     __rhs = {};
 528   else if (!__p._M_cmpts.empty()
 529       && __p._M_cmpts.front()._M_type() == _Type::_Root_name)
 530     __rhs.remove_prefix(__p._M_cmpts.front()._M_pathname.size());
 531
 532   const size_t __len = __lhs.size() + (int)__add_sep + __rhs.size();
 533   const int __maxcmpts = _M_cmpts.size() + __p._M_cmpts.size();
 534   if (_M_pathname.capacity() < __len || _M_cmpts.capacity() < __maxcmpts)
 535     {
 536       // Construct new path and swap (strong exception-safety guarantee).
 537       string_type __tmp;
 538       __tmp.reserve(__len);
 539       __tmp = __lhs;
 540       if (__add_sep)
 541         __tmp += preferred_separator;
 542       __tmp += __rhs;
 543       path __newp = std::move(__tmp);
 544       swap(__newp);
 545     }
 546   else
 547     {
 548       _M_pathname = __lhs;
 549       if (__add_sep)
 550         _M_pathname += preferred_separator;
 551       _M_pathname += __rhs;
 552       __try
 553         {
 554           _M_split_cmpts();
 555         }
 556       __catch (...)
 557         {
 558           __try
 559             {
 560               // try to restore original state
 561               _M_pathname.resize(__lhs.length());
 562               _M_split_cmpts();
 563             }
 564           __catch (...)
 565             {
 566               // give up, basic exception safety guarantee only:
 567               clear();
 568               __throw_exception_again;
 569             }
 570         }
 571     }
 572 #else
 573   // POSIX version is simpler than the specification in the standard,
 574   // as any path with root-name or root-dir is absolute.
 575
 576   if (__p.is_absolute() || this->empty())
 577     {
 578       return operator=(__p);
 579     }
 580
 581   using string_view_type = basic_string_view<value_type>;
 582
 583   string_view_type sep;
 584   if (has_filename())
 585     sep = { &preferred_separator, 1 };  // need to add a separator
 586 #if SLASHSLASH_IS_ROOTNAME
 587   else if (_M_type() == _Type::_Root_name) // root-name with no root-dir
 588     sep = { &preferred_separator, 1 };  // need to add a separator
 589 #endif
 590   else if (__p.empty())
 591     return *this;                           // nothing to do
 592
 593   const auto orig_pathlen = _M_pathname.length();
 594   const auto orig_size = _M_cmpts.size();
 595   const auto orig_type = _M_type();
 596
 597   int capacity = 0;
 598   if (_M_type() == _Type::_Multi)
 599     capacity += _M_cmpts.size();
 600   else if (!empty())
 601     capacity += 1;
 602   if (__p._M_type() == _Type::_Multi)
 603     capacity += __p._M_cmpts.size();
 604   else if (!__p.empty() || !sep.empty())
 605     capacity += 1;
 606 #if SLASHSLASH_IS_ROOTNAME
 607   if (orig_type == _Type::_Root_name)
 608     ++capacity; // Need to insert root-directory after root-name
 609 #endif
 610
 611   _M_pathname.reserve(_M_pathname.length() + sep.length()
 612                       + __p._M_pathname.length());
 613
 614   __try
 615     {
 616       _M_pathname += sep;
 617       const auto basepos = _M_pathname.length();
 618       _M_pathname += __p.native();
 619
 620       _M_cmpts.type(_Type::_Multi);
 621       _M_cmpts.reserve(capacity);
 622       _Cmpt* output = _M_cmpts._M_impl->end();
 623
 624       if (orig_type == _Type::_Multi)
 625         {
 626           // Remove empty final component
 627           if (_M_cmpts._M_impl->back().empty())
 628             {
 629               _M_cmpts.pop_back();
 630               --output;
 631             }
 632         }
 633       else if (orig_pathlen != 0)
 634         {
 635           // Create single component from original path
 636           string_view_type s(_M_pathname.data(), orig_pathlen);
 637           ::new(output++) _Cmpt(s, orig_type, 0);
 638           ++_M_cmpts._M_impl->_M_size;
 639 #if SLASHSLASH_IS_ROOTNAME
 640           if (orig_type == _Type::_Root_name)
 641             {
 642               ::new(output++) _Cmpt(sep, _Type::_Root_dir,
 643                                     orig_pathlen + sep.length());
 644               ++_M_cmpts._M_impl->_M_size;
 645             }
 646 #endif
 647         }
 648
 649       if (__p._M_type() == _Type::_Multi)
 650         {
 651           for (auto& c : *__p._M_cmpts._M_impl)
 652             {
 653               ::new(output++) _Cmpt(c._M_pathname, _Type::_Filename,
 654                                     c._M_pos + basepos);
 655               ++_M_cmpts._M_impl->_M_size;
 656             }
 657         }
 658       else if (!__p.empty() || !sep.empty())
 659         {
 660           __glibcxx_assert(__p._M_type() == _Type::_Filename);
 661           ::new(output) _Cmpt(__p._M_pathname, __p._M_type(), basepos);
 662           ++_M_cmpts._M_impl->_M_size;
 663         }
 664     }
 665   __catch (...)
 666     {
 667       _M_pathname.resize(orig_pathlen);
 668       if (orig_type == _Type::_Multi)
 669         _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
 670       else
 671         _M_cmpts.clear();
 672       _M_cmpts.type(orig_type);
 673       __throw_exception_again;
 674     }
 675 #endif
 676   return *this;
 677 }
 678
 679 // [fs.path.append]
 680 void
 681 path::_M_append(basic_string_view<value_type> s)
 682 {
 683   _Parser parser(s);
 684   auto root_path = parser.root_path();
 685
 686 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
 687   bool is_absolute = root_path.second.type == _Type::_Root_dir;
 688   bool has_root_name = root_path.first.type == _Type::_Root_name;
 689   if (is_absolute || (has_root_name && root_path.first.str != root_name()))
 690     {
 691       operator=(s);
 692       return;
 693     }
 694
 695   basic_string_view<value_type> lhs = _M_pathname;
 696   bool add_sep = false;
 697
 698   bool has_root_directory = root_path.first.type == _Type::_Root_dir
 699     || root_path.second.type == _Type::_Root_dir;
 700
 701   if (has_root_directory)
 702     {
 703       // Remove any root directory and relative path
 704       if (_M_type() != _Type::_Root_name)
 705         {
 706           if (!_M_cmpts.empty()
 707               && _M_cmpts.front()._M_type() == _Type::_Root_name)
 708             lhs = _M_cmpts.front()._M_pathname;
 709           else
 710             lhs = {};
 711         }
 712     }
 713   else if (has_filename() || (!has_root_directory && is_absolute))
 714     add_sep = true;
 715
 716   basic_string_view<value_type> rhs = s;
 717   // Omit any root-name from the generic format pathname:
 718   if (has_root_name)
 719     rhs.remove_prefix(root_path.first.str.length());
 720
 721   // Construct new path and swap (strong exception-safety guarantee).
 722   string_type tmp;
 723   tmp.reserve(lhs.size() + (int)add_sep + rhs.size());
 724   tmp = lhs;
 725   if (add_sep)
 726     tmp += preferred_separator;
 727   tmp += rhs;
 728   path newp = std::move(tmp);
 729   swap(newp);
 730 #else
 731
 732   bool is_absolute = root_path.first.type == _Type::_Root_dir
 733     || root_path.second.type == _Type::_Root_dir;
 734   if (is_absolute || this->empty())
 735     {
 736       operator=(s);
 737       return;
 738     }
 739
 740   const auto orig_pathlen = _M_pathname.length();
 741   const auto orig_size = _M_cmpts.size();
 742   const auto orig_type = _M_type();
 743
 744   basic_string_view<value_type> sep;
 745   if (has_filename())
 746     sep = { &preferred_separator, 1 };  // need to add a separator
 747 #if SLASHSLASH_IS_ROOTNAME
 748   else if (_M_type() == _Type::_Root_name) // root-name with no root-dir
 749     sep = { &preferred_separator, 1 };  // need to add a separator
 750 #endif
 751   else if (s.empty())
 752     return;                         // nothing to do
 753
 754   // Copy the input into _M_pathname:
 755   _M_pathname += s;
 756   _M_pathname.insert(orig_pathlen, sep);
 757   // Update s to refer to the new copy (this ensures s is not a dangling
 758   // reference to deallocated characters, in the case where it was referring
 759   // into _M_pathname or a member of _M_cmpts).
 760   s = _M_pathname;
 761   const auto orig_pathname = s.substr(0, orig_pathlen);
 762   s.remove_prefix(orig_pathlen + sep.length());
 763
 764   parser.input = s; // reset parser to use updated string view
 765   const auto basepos = orig_pathname.length() + sep.length();
 766   parser.origin = basepos;
 767
 768   std::array<_Parser::cmpt, 64> buf;
 769   auto next = buf.begin();
 770
 771   int capacity = 0;
 772   if (_M_type() == _Type::_Multi)
 773     capacity += _M_cmpts.size();
 774   else if (!empty())
 775     capacity += 1;
 776
 777   auto cmpt = parser.next();
 778   if (cmpt.valid())
 779     {
 780       do
 781         {
 782           *next++ = cmpt;
 783           cmpt = parser.next();
 784         }
 785       while (cmpt.valid() && next != buf.end());
 786
 787       capacity += next - buf.begin();
 788       if (cmpt.valid()) // filled buffer before parsing whole input
 789         {
 790           ++capacity;
 791           _Parser parser2(parser);
 792           while (parser2.next().valid())
 793             ++capacity;
 794         }
 795     }
 796   else if (!sep.empty())
 797     ++capacity;
 798
 799 #if SLASHSLASH_IS_ROOTNAME
 800   if (orig_type == _Type::_Root_name)
 801     ++capacity; // Need to insert root-directory after root-name
 802 #endif
 803
 804   __try
 805     {
 806       _M_cmpts.type(_Type::_Multi);
 807       _M_cmpts.reserve(capacity);
 808       _Cmpt* output = _M_cmpts._M_impl->end();
 809
 810       if (orig_type == _Type::_Multi)
 811         {
 812           // Remove empty final component
 813           if (_M_cmpts._M_impl->back().empty())
 814             {
 815               _M_cmpts.pop_back();
 816               --output;
 817             }
 818         }
 819       else if (orig_pathlen != 0)
 820         {
 821           // Create single component from original path
 822           ::new(output++) _Cmpt(orig_pathname, orig_type, 0);
 823           ++_M_cmpts._M_impl->_M_size;
 824
 825 #if SLASHSLASH_IS_ROOTNAME
 826           if (!sep.empty() && orig_type == _Type::_Root_name)
 827             {
 828               ::new(output++) _Cmpt(sep, _Type::_Root_dir,
 829                                     orig_pathlen + sep.length());
 830               ++_M_cmpts._M_impl->_M_size;
 831             }
 832 #endif
 833         }
 834
 835       if (next != buf.begin())
 836         {
 837           for (auto it = buf.begin(); it != next; ++it)
 838             {
 839               auto c = *it;
 840               ::new(output++) _Cmpt(c.str, c.type, parser.offset(c));
 841               ++_M_cmpts._M_impl->_M_size;
 842             }
 843           while (cmpt.valid())
 844             {
 845               ::new(output++) _Cmpt(cmpt.str, cmpt.type, parser.offset(cmpt));
 846               ++_M_cmpts._M_impl->_M_size;
 847               cmpt = parser.next();
 848             }
 849         }
 850       else if (!sep.empty())
 851         {
 852           // Empty filename at the end:
 853           ::new(output) _Cmpt({}, _Type::_Filename, basepos);
 854           ++_M_cmpts._M_impl->_M_size;
 855         }
 856     }
 857   __catch (...)
 858     {
 859       _M_pathname.resize(orig_pathlen);
 860       if (orig_type == _Type::_Multi)
 861         _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
 862       else
 863         _M_cmpts.clear();
 864       _M_cmpts.type(orig_type);
 865       __throw_exception_again;
 866     }
 867 #endif
 868 }
 869
 870 // [fs.path.concat]
 871 path&
 872 path::operator+=(const path& p)
 873 {
 874   if (p.empty())
 875     return *this;
 876
 877   if (this->empty())
 878     {
 879       operator=(p);
 880       return *this;
 881     }
 882
 883 #if _GLIBCXX_FILESYSTEM_IS_WINDOWS
 884   if (_M_type() == _Type::_Root_name
 885       || (_M_type() == _Type::_Filename && _M_pathname.size() == 1))
 886     {
 887       // Handle path("C") += path(":") and path("C:") += path("/x")
 888       // FIXME: do this more efficiently
 889       *this = path(_M_pathname + p._M_pathname);
 890       return *this;
 891     }
 892 #endif
 893 #if SLASHSLASH_IS_ROOTNAME
 894   if (_M_type() == _Type::_Root_dir)
 895     {
 896       // Handle path("/") += path("/x") and path("//") += path("x")
 897       // FIXME: do this more efficiently
 898       *this = path(_M_pathname + p._M_pathname);
 899       return *this;
 900     }
 901 #endif
 902
 903   const auto orig_pathlen = _M_pathname.length();
 904   const auto orig_type = _M_type();
 905   const auto orig_size = _M_cmpts.size();
 906   int orig_filenamelen = -1;
 907   basic_string_view<value_type> extra;
 908
 909   // Ensure that '_M_pathname += p._M_pathname' won't throw:
 910   _M_pathname.reserve(orig_pathlen + p._M_pathname.length());
 911
 912   _Cmpt c;
 913   _Cmpt* it = nullptr;
 914   _Cmpt* last = nullptr;
 915   if (p._M_type() == _Type::_Multi)
 916     {
 917       it = p._M_cmpts._M_impl->begin();
 918       last = p._M_cmpts._M_impl->end();
 919     }
 920   else
 921     {
 922       c = _Cmpt(p._M_pathname, p._M_type(), 0);
 923       it = &c;
 924       last = it + 1;
 925     }
 926
 927   if (it->_M_type() == _Type::_Filename)
 928     {
 929       // See if there's a filename or root-name at the end of the original path
 930       // that we can add to.
 931       if (_M_type() == _Type::_Filename
 932 #if SLASHSLASH_IS_ROOTNAME
 933           || _M_type() == _Type::_Root_name
 934 #endif
 935           )
 936         {
 937           if (p._M_type() == _Type::_Filename)
 938             {
 939               // Simplest case where we just add the whole of p to the
 940               // original path.
 941               _M_pathname += p._M_pathname;
 942               return *this;
 943             }
 944           // Only the first component of s should be appended, do so below:
 945           extra = it->_M_pathname;
 946           ++it;
 947         }
 948       else if (_M_type() == _Type::_Multi
 949           && _M_cmpts.back()._M_type() == _Type::_Filename)
 950         {
 951           auto& back = _M_cmpts.back();
 952           if (p._M_type() == _Type::_Filename)
 953             {
 954               basic_string_view<value_type> s = p._M_pathname;
 955               back._M_pathname += s;
 956               _M_pathname += s;
 957               return *this;
 958             }
 959
 960           orig_filenamelen = back._M_pathname.length();
 961           back._M_pathname += it->_M_pathname;
 962           extra = it->_M_pathname;
 963           ++it;
 964         }
 965     }
 966   else if (is_dir_sep(_M_pathname.back()) && _M_type() == _Type::_Multi
 967       && _M_cmpts.back()._M_type() == _Type::_Filename)
 968     orig_filenamelen = 0; // current path has empty filename at end
 969
 970   int capacity = 0;
 971   if (_M_type() == _Type::_Multi)
 972     capacity += _M_cmpts.size();
 973   else
 974     capacity += 1;
 975   if (p._M_type() == _Type::_Multi)
 976     capacity += p._M_cmpts.size();
 977   else
 978     capacity += 1;
 979
 980   __try
 981     {
 982       _M_cmpts.type(_Type::_Multi);
 983       _M_cmpts.reserve(capacity);
 984       _Cmpt* output = _M_cmpts._M_impl->end();
 985
 986       if (orig_type != _Type::_Multi)
 987         {
 988           // Create single component from original path
 989           auto ptr = ::new(output++) _Cmpt({}, orig_type, 0);
 990           ++_M_cmpts._M_impl->_M_size;
 991           ptr->_M_pathname.reserve(_M_pathname.length() + extra.length());
 992           ptr->_M_pathname = _M_pathname;
 993           ptr->_M_pathname += extra;
 994
 995 #if SLASHSLASH_IS_ROOTNAME
 996           if (orig_type == _Type::_Root_name)
 997             {
 998               basic_string_view<value_type> s(p._M_pathname);
 999               ::new(output++) _Cmpt(s.substr(extra.length(), 1),
1000                   _Type::_Root_dir, orig_pathlen + extra.length());
1001               ++_M_cmpts._M_impl->_M_size;
1002             }
1003 #endif
1004         }
1005       else if (orig_filenamelen == 0 && it != last)
1006         {
1007           // Remove empty filename at end of original path.
1008           _M_cmpts.pop_back();
1009           --output;
1010         }
1011
1012       if (it != last && it->_M_type() == _Type::_Root_name)
1013         {
1014           basic_string_view<value_type> s = it->_M_pathname;
1015           auto pos = orig_pathlen;
1016 #if SLASHSLASH_IS_ROOTNAME
1017           s.remove_prefix(2);
1018           pos += 2;
1019 #endif
1020           ::new(output++) _Cmpt(s, _Type::_Filename, pos);
1021           ++_M_cmpts._M_impl->_M_size;
1022           ++it;
1023         }
1024
1025       if (it != last && it->_M_type() == _Type::_Root_dir)
1026         ++it;
1027
1028       while (it != last)
1029         {
1030           auto pos = it->_M_pos + orig_pathlen;
1031           ::new(output++) _Cmpt(it->_M_pathname, _Type::_Filename, pos);
1032           ++_M_cmpts._M_impl->_M_size;
1033           ++it;
1034         }
1035
1036       _M_pathname += p._M_pathname;
1037
1038       if (is_dir_sep(_M_pathname.back()))
1039         {
1040           ::new(output++) _Cmpt({}, _Type::_Filename, _M_pathname.length());
1041           ++_M_cmpts._M_impl->_M_size;
1042         }
1043       }
1044   __catch (...)
1045     {
1046       _M_pathname.resize(orig_pathlen);
1047       if (orig_type == _Type::_Multi)
1048         {
1049           if (_M_cmpts.size() > orig_size)
1050             _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
1051           if (orig_filenamelen != -1)
1052             {
1053               if (_M_cmpts.size() == orig_size)
1054                 {
1055                   auto& back = _M_cmpts.back();
1056                   back._M_pathname.resize(orig_filenamelen);
1057                   if (orig_filenamelen == 0)
1058                     back._M_pos = orig_pathlen;
1059                 }
1060               else
1061                 {
1062                   auto output = _M_cmpts._M_impl->end();
1063                   ::new(output) _Cmpt({}, _Type::_Filename, orig_pathlen);
1064                   ++_M_cmpts._M_impl->_M_size;
1065                 }
1066             }
1067         }
1068       else
1069         _M_cmpts.clear();
1070       _M_cmpts.type(orig_type);
1071       __throw_exception_again;
1072     }
1073   return *this;
1074 }
1075
1076 // [fs.path.concat]
1077 void
1078 path::_M_concat(basic_string_view<value_type> s)
1079 {
1080   if (s.empty())
1081     return;
1082
1083   if (this->empty())
1084     {
1085       operator=(s);
1086       return;
1087     }
1088
1089 #if _GLIBCXX_FILESYSTEM_IS_WINDOWS
1090   if (_M_type() == _Type::_Root_name
1091       || (_M_type() == _Type::_Filename && _M_pathname.size() == 1))
1092     {
1093       // Handle path("C") += ":" and path("C:") += "/x"
1094       // FIXME: do this more efficiently
1095       *this = path(_M_pathname + string_type(s));
1096       return;
1097     }
1098 #endif
1099 #if SLASHSLASH_IS_ROOTNAME
1100   if (_M_type() == _Type::_Root_dir)
1101     {
1102       // Handle path("/") += "/x" and path("//") += "x"
1103       // FIXME: do this more efficiently
1104       *this = path(_M_pathname + string_type(s));
1105       return;
1106     }
1107 #endif
1108
1109   const auto orig_pathlen = _M_pathname.length();
1110   const auto orig_type = _M_type();
1111   const auto orig_size = _M_cmpts.size();
1112   int orig_filenamelen = -1;
1113   basic_string_view<value_type> extra;
1114
1115   // Copy the input into _M_pathname:
1116   _M_pathname += s;
1117   // Update s to refer to the new copy (this ensures s is not a dangling
1118   // reference to deallocated characters, in the case where it was referring
1119   // into _M_pathname or a member of _M_cmpts).
1120   s = _M_pathname;
1121   const auto orig_pathname = s.substr(0, orig_pathlen);
1122   s.remove_prefix(orig_pathlen);
1123
1124   _Parser parser(s, orig_pathlen);
1125   auto cmpt = parser.next();
1126
1127   if (cmpt.str.data() == s.data())
1128     {
1129       // See if there's a filename or root-name at the end of the original path
1130       // that we can add to.
1131       if (_M_type() == _Type::_Filename
1132 #if SLASHSLASH_IS_ROOTNAME
1133           || _M_type() == _Type::_Root_name
1134 #endif
1135           )
1136         {
1137           if (cmpt.str.length() == s.length())
1138             {
1139               // Simplest case where we just need to add the whole of s
1140               // to the original path, which was already done above.
1141               return;
1142             }
1143           // Only the first component of s should be appended, do so below:
1144           extra = cmpt.str;
1145           cmpt = {}; // so we don't process it again
1146         }
1147       else if (_M_type() == _Type::_Multi
1148           && _M_cmpts.back()._M_type() == _Type::_Filename)
1149         {
1150           auto& back = _M_cmpts.back();
1151           if (cmpt.str.length() == s.length())
1152             {
1153               back._M_pathname += s;
1154               return;
1155             }
1156
1157           orig_filenamelen = back._M_pathname.length();
1158           back._M_pathname += cmpt.str;
1159           extra = cmpt.str;
1160           cmpt = {};
1161         }
1162     }
1163   else if (is_dir_sep(orig_pathname.back()) && _M_type() == _Type::_Multi
1164       && _M_cmpts.back()._M_type() == _Type::_Filename)
1165     orig_filenamelen = 0; // original path had empty filename at end
1166
1167   std::array<_Parser::cmpt, 64> buf;
1168   auto next = buf.begin();
1169
1170   if (cmpt.valid())
1171     *next++ = cmpt;
1172
1173   cmpt = parser.next();
1174   while (cmpt.valid() && next != buf.end())
1175     {
1176       *next++ = cmpt;
1177       cmpt = parser.next();
1178     }
1179
1180   int capacity = 0;
1181   if (_M_type() == _Type::_Multi)
1182     capacity += _M_cmpts.size();
1183   else
1184     capacity += 1;
1185
1186   capacity += next - buf.begin();
1187
1188   if (cmpt.valid()) // filled buffer before parsing whole input
1189     {
1190       ++capacity;
1191       _Parser parser2(parser);
1192       while (parser2.next().valid())
1193         ++capacity;
1194     }
1195
1196 #if SLASHSLASH_IS_ROOTNAME
1197   if (orig_type == _Type::_Root_name)
1198     ++capacity; // Need to insert root-directory after root-name
1199 #endif
1200
1201   __try
1202     {
1203       _M_cmpts.type(_Type::_Multi);
1204       _M_cmpts.reserve(capacity);
1205       _Cmpt* output = _M_cmpts._M_impl->end();
1206       auto it = buf.begin();
1207
1208       if (orig_type != _Type::_Multi)
1209         {
1210           // Create single component from original path
1211           auto p = ::new(output++) _Cmpt({}, orig_type, 0);
1212           ++_M_cmpts._M_impl->_M_size;
1213           p->_M_pathname.reserve(orig_pathname.length() + extra.length());
1214           p->_M_pathname = orig_pathname;
1215           p->_M_pathname += extra;
1216
1217 #if SLASHSLASH_IS_ROOTNAME
1218           if (orig_type == _Type::_Root_name)
1219             {
1220               ::new(output++) _Cmpt(s.substr(extra.length(), 1),
1221                   _Type::_Root_dir, orig_pathlen + extra.length());
1222               ++_M_cmpts._M_impl->_M_size;
1223             }
1224 #endif
1225         }
1226       else if (orig_filenamelen == 0 && extra.empty())
1227         {
1228           // Replace empty filename at end of original path.
1229           std::prev(output)->_M_pathname = it->str;
1230           std::prev(output)->_M_pos = parser.offset(*it);
1231           ++it;
1232         }
1233
1234       while (it != next)
1235         {
1236           ::new(output++) _Cmpt(it->str, _Type::_Filename, parser.offset(*it));
1237           ++_M_cmpts._M_impl->_M_size;
1238           ++it;
1239         }
1240
1241       if (next == buf.end())
1242         {
1243           while (cmpt.valid())
1244             {
1245               auto pos = parser.offset(cmpt);
1246               ::new(output++) _Cmpt(cmpt.str, _Type::_Filename, pos);
1247               ++_M_cmpts._M_impl->_M_size;
1248               cmpt = parser.next();
1249             }
1250         }
1251     }
1252   __catch (...)
1253     {
1254       _M_pathname.resize(orig_pathlen);
1255       if (orig_type == _Type::_Multi)
1256         {
1257           _M_cmpts._M_erase_from(_M_cmpts.begin() + orig_size);
1258           if (orig_filenamelen != -1)
1259             {
1260               auto& back = _M_cmpts.back();
1261               back._M_pathname.resize(orig_filenamelen);
1262               if (orig_filenamelen == 0)
1263                 back._M_pos = orig_pathlen;
1264             }
1265         }
1266       else
1267         _M_cmpts.clear();
1268       _M_cmpts.type(orig_type);
1269       __throw_exception_again;
1270     }
1271 }
1272
1273 path&
1274 path::remove_filename()
1275 {
1276   if (_M_type() == _Type::_Multi)
1277     {
1278       if (!_M_cmpts.empty())
1279         {
1280           auto cmpt = std::prev(_M_cmpts.end());
1281           if (cmpt->_M_type() == _Type::_Filename && !cmpt->empty())
1282             {
1283               _M_pathname.erase(cmpt->_M_pos);
1284               auto prev = std::prev(cmpt);
1285               if (prev->_M_type() == _Type::_Root_dir
1286                   || prev->_M_type() == _Type::_Root_name)
1287                 {
1288                   _M_cmpts.pop_back();
1289                   if (_M_cmpts.size() == 1)
1290                     {
1291                       _M_cmpts.type(_M_cmpts.front()._M_type());
1292                       _M_cmpts.clear();
1293                     }
1294                 }
1295               else
1296                 cmpt->clear();
1297             }
1298         }
1299     }
1300   else if (_M_type() == _Type::_Filename)
1301     clear();
1302   return *this;
1303 }
1304
1305 path&
1306 path::replace_filename(const path& replacement)
1307 {
1308   remove_filename();
1309   operator/=(replacement);
1310   return *this;
1311 }
1312
1313 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
1314 const fs::path::value_type dot = L'.';
1315 #else
1316 const fs::path::value_type dot = '.';
1317 #endif
1318
1319 path&
1320 path::replace_extension(const path& replacement)
1321 {
1322   auto ext = _M_find_extension();
1323   // Any existing extension() is removed
1324   if (ext.first && ext.second != string_type::npos)
1325     {
1326       if (ext.first == &_M_pathname)
1327         _M_pathname.erase(ext.second);
1328       else
1329         {
1330           auto& back = _M_cmpts.back();
1331           __glibcxx_assert( ext.first == &back._M_pathname );
1332           back._M_pathname.erase(ext.second);
1333           _M_pathname.erase(back._M_pos + ext.second);
1334         }
1335     }
1336    // If replacement is not empty and does not begin with a dot character,
1337    // a dot character is appended
1338   if (!replacement.empty() && replacement.native()[0] != dot)
1339     operator+=(".");
1340   operator+=(replacement);
1341   return *this;
1342 }
1343
1344 int
1345 path::compare(const path& p) const noexcept
1346 {
1347   if (_M_pathname == p._M_pathname)
1348     return 0;
1349
1350   basic_string_view<value_type> lroot, rroot;
1351   if (_M_type() == _Type::_Root_name)
1352     lroot = _M_pathname;
1353   else if (_M_type() == _Type::_Multi
1354       && _M_cmpts.front()._M_type() == _Type::_Root_name)
1355     lroot = _M_cmpts.front()._M_pathname;
1356   if (p._M_type() == _Type::_Root_name)
1357     rroot = p._M_pathname;
1358   else if (p._M_type() == _Type::_Multi
1359       && p._M_cmpts.front()._M_type() == _Type::_Root_name)
1360     rroot = p._M_cmpts.front()._M_pathname;
1361   if (int rootNameComparison = lroot.compare(rroot))
1362     return rootNameComparison;
1363
1364   if (!this->has_root_directory() && p.has_root_directory())
1365     return -1;
1366   else if (this->has_root_directory() && !p.has_root_directory())
1367     return +1;
1368
1369   using Iterator = const _Cmpt*;
1370   Iterator begin1, end1, begin2, end2;
1371   if (_M_type() == _Type::_Multi)
1372     {
1373       begin1 = _M_cmpts.begin();
1374       end1 = _M_cmpts.end();
1375       // Find start of this->relative_path()
1376       while (begin1 != end1 && begin1->_M_type() != _Type::_Filename)
1377         ++begin1;
1378     }
1379   else
1380     begin1 = end1 = nullptr;
1381
1382   if (p._M_type() == _Type::_Multi)
1383     {
1384       begin2 = p._M_cmpts.begin();
1385       end2 = p._M_cmpts.end();
1386       // Find start of p.relative_path()
1387       while (begin2 != end2 && begin2->_M_type() != _Type::_Filename)
1388         ++begin2;
1389     }
1390   else
1391     begin2 = end2 = nullptr;
1392
1393   if (_M_type() == _Type::_Filename)
1394     {
1395       if (p._M_type() == _Type::_Filename)
1396         return native().compare(p.native());
1397       else if (begin2 != end2)
1398         {
1399           if (int ret = native().compare(begin2->native()))
1400             return ret;
1401           else
1402             return ++begin2 == end2 ? 0 : -1;
1403         }
1404       else
1405         return +1;
1406     }
1407   else if (p._M_type() == _Type::_Filename)
1408     {
1409       if (begin1 != end1)
1410         {
1411           if (int ret = begin1->native().compare(p.native()))
1412             return ret;
1413           else
1414             return ++begin1 == end1 ? 0 : +1;
1415         }
1416       else
1417         return -1;
1418     }
1419
1420   int count = 1;
1421   while (begin1 != end1 && begin2 != end2)
1422     {
1423       if (int i = begin1->native().compare(begin2->native()))
1424         return i;
1425       ++begin1;
1426       ++begin2;
1427       ++count;
1428     }
1429   if (begin1 == end1)
1430     {
1431       if (begin2 == end2)
1432         return 0;
1433       return -count;
1434     }
1435   return count;
1436 }
1437
1438 int
1439 path::compare(basic_string_view<value_type> s) const noexcept
1440 {
1441   if (_M_pathname == s)
1442     return 0;
1443
1444   _Parser parser(s);
1445
1446   basic_string_view<value_type> lroot, rroot;
1447   if (_M_type() == _Type::_Root_name)
1448     lroot = _M_pathname;
1449   else if (_M_type() == _Type::_Multi
1450       && _M_cmpts.front()._M_type() == _Type::_Root_name)
1451     lroot = _M_cmpts.front()._M_pathname;
1452   auto root_path = parser.root_path();
1453   if (root_path.first.type == _Type::_Root_name)
1454     rroot = root_path.first.str;
1455   if (int rootNameComparison = lroot.compare(rroot))
1456     return rootNameComparison;
1457
1458   const bool has_root_dir = root_path.first.type == _Type::_Root_dir
1459     || root_path.second.type == _Type::_Root_dir;
1460   if (!this->has_root_directory() && has_root_dir)
1461     return -1;
1462   else if (this->has_root_directory() && !has_root_dir)
1463     return +1;
1464
1465   using Iterator = const _Cmpt*;
1466   Iterator begin1, end1;
1467   if (_M_type() == _Type::_Filename)
1468     {
1469       auto cmpt = parser.next();
1470       if (cmpt.valid())
1471         {
1472           if (int ret = this->native().compare(cmpt.str))
1473             return ret;
1474           return parser.next().valid() ? -1 : 0;
1475         }
1476       else
1477         return +1;
1478     }
1479   else if (_M_type() == _Type::_Multi)
1480     {
1481       begin1 = _M_cmpts.begin();
1482       end1 = _M_cmpts.end();
1483       while (begin1 != end1 && begin1->_M_type() != _Type::_Filename)
1484         ++begin1;
1485     }
1486   else
1487     begin1 = end1 = nullptr;
1488
1489   int count = 1;
1490   auto cmpt = parser.next();
1491   while (begin1 != end1 && cmpt.valid())
1492     {
1493       if (int i = begin1->native().compare(cmpt.str))
1494         return i;
1495       ++begin1;
1496       cmpt = parser.next();
1497       ++count;
1498     }
1499   if (begin1 == end1)
1500     {
1501       if (!cmpt.valid())
1502         return 0;
1503       return -count;
1504     }
1505   return +count;
1506 }
1507
1508 path
1509 path::root_name() const
1510 {
1511   path __ret;
1512   if (_M_type() == _Type::_Root_name)
1513     __ret = *this;
1514   else if (_M_cmpts.size() && _M_cmpts.begin()->_M_type() == _Type::_Root_name)
1515     __ret = *_M_cmpts.begin();
1516   return __ret;
1517 }
1518
1519 path
1520 path::root_directory() const
1521 {
1522   path __ret;
1523   if (_M_type() == _Type::_Root_dir)
1524     {
1525       __ret._M_cmpts.type(_Type::_Root_dir);
1526       __ret._M_pathname.assign(1, preferred_separator);
1527     }
1528   else if (!_M_cmpts.empty())
1529     {
1530       auto __it = _M_cmpts.begin();
1531       if (__it->_M_type() == _Type::_Root_name)
1532         ++__it;
1533       if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1534         __ret = *__it;
1535     }
1536   return __ret;
1537 }
1538
1539 path
1540 path::root_path() const
1541 {
1542   path __ret;
1543   if (_M_type() == _Type::_Root_name)
1544     __ret = *this;
1545   else if (_M_type() == _Type::_Root_dir)
1546     {
1547       __ret._M_pathname.assign(1, preferred_separator);
1548       __ret._M_cmpts.type(_Type::_Root_dir);
1549     }
1550   else if (!_M_cmpts.empty())
1551     {
1552       auto __it = _M_cmpts.begin();
1553       if (__it->_M_type() == _Type::_Root_name)
1554         {
1555           __ret = *__it++;
1556           if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1557             __ret /= *__it;
1558         }
1559       else if (__it->_M_type() == _Type::_Root_dir)
1560         __ret = *__it;
1561     }
1562   return __ret;
1563 }
1564
1565 path
1566 path::relative_path() const
1567 {
1568   path __ret;
1569   if (_M_type() == _Type::_Filename)
1570     __ret = *this;
1571   else if (!_M_cmpts.empty())
1572     {
1573       auto __it = _M_cmpts.begin();
1574       if (__it->_M_type() == _Type::_Root_name)
1575         ++__it;
1576       if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1577         ++__it;
1578       if (__it != _M_cmpts.end())
1579         __ret.assign(_M_pathname.substr(__it->_M_pos));
1580     }
1581   return __ret;
1582 }
1583
1584 path
1585 path::parent_path() const
1586 {
1587   path __ret;
1588   if (!has_relative_path())
1589     __ret = *this;
1590   else if (_M_cmpts.size() >= 2)
1591     {
1592       const auto parent = std::prev(_M_cmpts.end(), 2);
1593       const auto len = parent->_M_pos + parent->_M_pathname.length();
1594       __ret.assign(_M_pathname.substr(0, len));
1595     }
1596   return __ret;
1597 }
1598
1599 bool
1600 path::has_root_name() const noexcept
1601 {
1602   if (_M_type() == _Type::_Root_name)
1603     return true;
1604   if (!_M_cmpts.empty() && _M_cmpts.begin()->_M_type() == _Type::_Root_name)
1605     return true;
1606   return false;
1607 }
1608
1609 bool
1610 path::has_root_directory() const noexcept
1611 {
1612   if (_M_type() == _Type::_Root_dir)
1613     return true;
1614   if (!_M_cmpts.empty())
1615     {
1616       auto __it = _M_cmpts.begin();
1617       if (__it->_M_type() == _Type::_Root_name)
1618         ++__it;
1619       if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1620         return true;
1621     }
1622   return false;
1623 }
1624
1625 bool
1626 path::has_root_path() const noexcept
1627 {
1628   if (_M_type() == _Type::_Root_name || _M_type() == _Type::_Root_dir)
1629     return true;
1630   if (!_M_cmpts.empty())
1631     {
1632       auto __type = _M_cmpts.front()._M_type();
1633       if (__type == _Type::_Root_name || __type == _Type::_Root_dir)
1634         return true;
1635     }
1636   return false;
1637 }
1638
1639 bool
1640 path::has_relative_path() const noexcept
1641 {
1642   if (_M_type() == _Type::_Filename && !_M_pathname.empty())
1643     return true;
1644   if (!_M_cmpts.empty())
1645     {
1646       auto __it = _M_cmpts.begin();
1647       if (__it->_M_type() == _Type::_Root_name)
1648         ++__it;
1649       if (__it != _M_cmpts.end() && __it->_M_type() == _Type::_Root_dir)
1650         ++__it;
1651       if (__it != _M_cmpts.end() && !__it->_M_pathname.empty())
1652         return true;
1653     }
1654   return false;
1655 }
1656
1657
1658 bool
1659 path::has_parent_path() const noexcept
1660 {
1661   if (!has_relative_path())
1662     return !empty();
1663   return _M_cmpts.size() >= 2;
1664 }
1665
1666 bool
1667 path::has_filename() const noexcept
1668 {
1669   if (empty())
1670     return false;
1671   if (_M_type() == _Type::_Filename)
1672     return !_M_pathname.empty();
1673   if (_M_type() == _Type::_Multi)
1674     {
1675       if (_M_pathname.back() == preferred_separator)
1676         return false;
1677       return _M_cmpts.back().has_filename();
1678     }
1679   return false;
1680 }
1681
1682 namespace
1683 {
1684   inline bool is_dot(fs::path::value_type c) { return c == dot; }
1685
1686   inline bool is_dot(const fs::path& path)
1687   {
1688     const auto& filename = path.native();
1689     return filename.size() == 1 && is_dot(filename[0]);
1690   }
1691
1692   inline bool is_dotdot(const fs::path& path)
1693   {
1694     const auto& filename = path.native();
1695     return filename.size() == 2 && is_dot(filename[0]) && is_dot(filename[1]);
1696   }
1697 } // namespace
1698
1699 path
1700 path::lexically_normal() const
1701 {
1702   /*
1703   C++17 [fs.path.generic] p6
1704   - If the path is empty, stop.
1705   - Replace each slash character in the root-name with a preferred-separator.
1706   - Replace each directory-separator with a preferred-separator.
1707   - Remove each dot filename and any immediately following directory-separator.
1708   - As long as any appear, remove a non-dot-dot filename immediately followed
1709     by a directory-separator and a dot-dot filename, along with any immediately
1710     following directory-separator.
1711   - If there is a root-directory, remove all dot-dot filenames and any
1712     directory-separators immediately following them.
1713   - If the last filename is dot-dot, remove any trailing directory-separator.
1714   - If the path is empty, add a dot.
1715   */
1716   path ret;
1717   // If the path is empty, stop.
1718   if (empty())
1719     return ret;
1720   for (auto& p : *this)
1721     {
1722 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
1723       // Replace each slash character in the root-name
1724       if (p._M_type() == _Type::_Root_name || p._M_type() == _Type::_Root_dir)
1725         {
1726           string_type s = p.native();
1727           std::replace(s.begin(), s.end(), L'/', L'\\');
1728           ret /= s;
1729           continue;
1730         }
1731 #endif
1732       if (is_dotdot(p))
1733         {
1734           if (ret.has_filename())
1735             {
1736               // remove a non-dot-dot filename immediately followed by /..
1737               if (!is_dotdot(ret.filename()))
1738                 ret.remove_filename();
1739               else
1740                 ret /= p;
1741             }
1742           else if (!ret.has_relative_path())
1743             {
1744               // remove a dot-dot filename immediately after root-directory
1745               if (!ret.has_root_directory())
1746                 ret /= p;
1747             }
1748           else
1749             {
1750               // Got a path with a relative path (i.e. at least one non-root
1751               // element) and no filename at the end (i.e. empty last element),
1752               // so must have a trailing slash. See what is before it.
1753               auto elem = ret._M_cmpts.end() - 2;
1754               if (elem->has_filename() && !is_dotdot(*elem))
1755                 {
1756                   // Remove the filename before the trailing slash
1757                   // (equiv. to ret = ret.parent_path().remove_filename())
1758
1759                   if (elem == ret._M_cmpts.begin())
1760                     ret.clear();
1761                   else
1762                     {
1763                       ret._M_pathname.erase(elem->_M_pos);
1764                       // Remove empty filename at the end:
1765                       ret._M_cmpts.pop_back();
1766                       // If we still have a trailing non-root dir separator
1767                       // then leave an empty filename at the end:
1768                       if (std::prev(elem)->_M_type() == _Type::_Filename)
1769                         elem->clear();
1770                       else // remove the component completely:
1771                         ret._M_cmpts.pop_back();
1772                     }
1773                 }
1774               else
1775                 // Append the ".." to something ending in "../" which happens
1776                 // when normalising paths like ".././.." and "../a/../.."
1777                 ret /= p;
1778             }
1779         }
1780       else if (is_dot(p))
1781         ret /= path();
1782 #if SLASHSLASH_IS_ROOTNAME
1783       else if (p._M_type() == _Type::_Root_dir)
1784         ret += '/'; // using operator/=('/') would replace whole of ret
1785 #endif
1786       else
1787         ret /= p;
1788     }
1789
1790   if (ret._M_cmpts.size() >= 2)
1791     {
1792       auto back = std::prev(ret.end());
1793       // If the last filename is dot-dot, ...
1794       if (back->empty() && is_dotdot(*std::prev(back)))
1795         // ... remove any trailing directory-separator.
1796         ret = ret.parent_path();
1797     }
1798   // If the path is empty, add a dot.
1799   else if (ret.empty())
1800     ret = ".";
1801
1802   return ret;
1803 }
1804
1805 path
1806 path::lexically_relative(const path& base) const
1807 {
1808   path ret;
1809   if (root_name() != base.root_name())
1810     return ret;
1811   if (is_absolute() != base.is_absolute())
1812     return ret;
1813   if (!has_root_directory() && base.has_root_directory())
1814     return ret;
1815   auto [a, b] = std::mismatch(begin(), end(), base.begin(), base.end());
1816 #ifdef _GLIBCXX_FILESYSTEM_IS_WINDOWS
1817   // _GLIBCXX_RESOLVE_LIB_DEFECTS
1818   // 3070. path::lexically_relative causes surprising results if a filename
1819   // can also be a root-name
1820   if (!empty())
1821     for (auto& p : _M_cmpts)
1822       if (p._M_type() == _Type::_Filename && is_disk_designator(p.native()))
1823         return ret;
1824   if (!base.empty())
1825     for (auto i = b, end = base.end(); i != end; ++i)
1826       if (i->_M_type() == _Type::_Filename && is_disk_designator(i->native()))
1827         return ret;
1828 #endif
1829   if (a == end() && b == base.end())
1830     ret = ".";
1831   else
1832   {
1833     int n = 0;
1834     for (; b != base.end(); ++b)
1835     {
1836       const path& p = *b;
1837       if (is_dotdot(p))
1838         --n;
1839       else if (!p.empty() && !is_dot(p))
1840         ++n;
1841     }
1842     if (n == 0 && (a == end() || a->empty()))
1843       ret = ".";
1844     else if (n >= 0)
1845     {
1846       const path dotdot("..");
1847       while (n--)
1848         ret /= dotdot;
1849       for (; a != end(); ++a)
1850         ret /= *a;
1851     }
1852   }
1853   return ret;
1854 }
1855
1856 path
1857 path::lexically_proximate(const path& base) const
1858 {
1859   path rel = lexically_relative(base);
1860   if (rel.empty())
1861     rel = *this;
1862   return rel;
1863 }
1864
1865 std::pair<const path::string_type*, std::size_t>
1866 path::_M_find_extension() const noexcept
1867 {
1868   const string_type* s = nullptr;
1869
1870   if (_M_type() == _Type::_Filename)
1871     s = &_M_pathname;
1872   else if (_M_type() == _Type::_Multi && !_M_cmpts.empty())
1873     {
1874       const auto& c = _M_cmpts.back();
1875       if (c._M_type() == _Type::_Filename)
1876         s = &c._M_pathname;
1877     }
1878
1879   if (s)
1880     {
1881       if (auto sz = s->size())
1882         {
1883           if (sz <= 2 && (*s)[0] == dot)
1884             return { s, string_type::npos };
1885           if (const auto pos = s->rfind(dot))
1886             return { s , pos };
1887           return { s, string_type::npos };
1888         }
1889     }
1890   return {};
1891 }
1892
1893 void
1894 path::_M_split_cmpts()
1895 {
1896   _M_cmpts.clear();
1897
1898   if (_M_pathname.empty())
1899     {
1900       _M_cmpts.type(_Type::_Filename);
1901       return;
1902     }
1903
1904   _Parser parser(_M_pathname);
1905
1906   std::array<_Parser::cmpt, 64> buf;
1907   auto next = buf.begin();
1908
1909   // look for root name or root directory
1910   auto root_path = parser.root_path();
1911   if (root_path.first.valid())
1912     {
1913       *next++ = root_path.first;
1914       if (root_path.second.valid())
1915         *next++ = root_path.second;
1916     }
1917
1918   auto cmpt = parser.next();
1919   while (cmpt.valid())
1920     {
1921       do
1922         {
1923           *next++ = cmpt;
1924           cmpt = parser.next();
1925         }
1926       while (cmpt.valid() && next != buf.end());
1927
1928       if (next == buf.end())
1929         {
1930           _M_cmpts.type(_Type::_Multi);
1931           _M_cmpts.reserve(_M_cmpts.size() + buf.size());
1932           auto output = _M_cmpts._M_impl->end();
1933           for (const auto& c : buf)
1934             {
1935               ::new(output++) _Cmpt(c.str, c.type, parser.offset(c));
1936               ++_M_cmpts._M_impl->_M_size;
1937             }
1938           next = buf.begin();
1939         }
1940     }
1941
1942   if (auto n = next - buf.begin())
1943     {
1944       if (n == 1 && _M_cmpts.empty())
1945         {
1946           _M_cmpts.type(buf.front().type);
1947           return;
1948         }
1949
1950       _M_cmpts.type(_Type::_Multi);
1951       _M_cmpts.reserve(_M_cmpts.size() + n, true);
1952       auto output = _M_cmpts._M_impl->end();
1953       for (int i = 0; i < n; ++i)
1954         {
1955           const auto& c = buf[i];
1956           ::new(output++) _Cmpt(c.str, c.type, parser.offset(c));
1957           ++_M_cmpts._M_impl->_M_size;
1958         }
1959     }
1960 }
1961
1962 path::string_type
1963 path::_S_convert_loc(const char* __first, const char* __last,
1964                      [[maybe_unused]] const std::locale& __loc)
1965 {
1966 #if _GLIBCXX_USE_WCHAR_T
1967   auto& __cvt = std::use_facet<codecvt<wchar_t, char, mbstate_t>>(__loc);
1968   basic_string<wchar_t> __ws;
1969   if (!__str_codecvt_in_all(__first, __last, __ws, __cvt))
1970     _GLIBCXX_THROW_OR_ABORT(filesystem_error(
1971           "Cannot convert character sequence",
1972           std::make_error_code(errc::illegal_byte_sequence)));
1973   return _S_convert(std::move(__ws));
1974 #else
1975   return {__first, __last};
1976 #endif
1977 }
1978
1979 std::size_t
1980 fs::hash_value(const path& p) noexcept
1981 {
1982   // [path.non-member]
1983   // "If for two paths, p1 == p2 then hash_value(p1) == hash_value(p2)."
1984   // Equality works as if by traversing the range [begin(), end()), meaning
1985   // e.g. path("a//b") == path("a/b"), so we cannot simply hash _M_pathname
1986   // but need to iterate over individual elements. Use the hash_combine from
1987   // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3876.pdf
1988   size_t seed = 0;
1989   for (const auto& x : p)
1990     {
1991       seed ^= std::hash<path::string_type>()(x.native()) + 0x9e3779b9
1992         + (seed<<6) + (seed>>2);
1993     }
1994   return seed;
1995 }
1996
1997 struct fs::filesystem_error::_Impl
1998 {
1999   _Impl(string_view what_arg, const path& p1, const path& p2)
2000   : path1(p1), path2(p2), what(make_what(what_arg, &p1, &p2))
2001   { }
2002
2003   _Impl(string_view what_arg, const path& p1)
2004   : path1(p1), path2(), what(make_what(what_arg, &p1, nullptr))
2005   { }
2006
2007   _Impl(string_view what_arg)
2008   : what(make_what(what_arg, nullptr, nullptr))
2009   { }
2010
2011   static std::string
2012   make_what(string_view s, const path* p1, const path* p2)
2013   {
2014     const std::string pstr1 = p1 ? p1->u8string() : std::string{};
2015     const std::string pstr2 = p2 ? p2->u8string() : std::string{};
2016     const size_t len = 18 + s.length()
2017       + (pstr1.length() ? pstr1.length() + 3 : 0)
2018       + (pstr2.length() ? pstr2.length() + 3 : 0);
2019     std::string w;
2020     w.reserve(len);
2021     w = "filesystem error: ";
2022     w += s;
2023     if (p1)
2024       {
2025         w += " [";
2026         w += pstr1;
2027         w += ']';
2028         if (p2)
2029           {
2030             w += " [";
2031             w += pstr2;
2032             w += ']';
2033           }
2034       }
2035     return w;
2036   }
2037
2038   path path1;
2039   path path2;
2040   std::string what;
2041 };
2042
2043 template class std::__shared_ptr<const fs::filesystem_error::_Impl>;
2044
2045 fs::filesystem_error::
2046 filesystem_error(const string& what_arg, error_code ec)
2047 : system_error(ec, what_arg),
2048   _M_impl(std::__make_shared<_Impl>(system_error::what()))
2049 { }
2050
2051 fs::filesystem_error::
2052 filesystem_error(const string& what_arg, const path& p1, error_code ec)
2053 : system_error(ec, what_arg),
2054   _M_impl(std::__make_shared<_Impl>(system_error::what(), p1))
2055 { }
2056
2057 fs::filesystem_error::
2058 filesystem_error(const string& what_arg, const path& p1, const path& p2,
2059                  error_code ec)
2060 : system_error(ec, what_arg),
2061   _M_impl(std::__make_shared<_Impl>(system_error::what(), p1, p2))
2062 { }
2063
2064 fs::filesystem_error::~filesystem_error() = default;
2065
2066 const fs::path&
2067 fs::filesystem_error::path1() const noexcept
2068 { return _M_impl->path1; }
2069
2070 const fs::path&
2071 fs::filesystem_error::path2() const noexcept
2072 { return _M_impl->path2; }
2073
2074 const char*
2075 fs::filesystem_error::what() const noexcept
2076 { return _M_impl->what.c_str(); }